{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,2]],"date-time":"2025-10-02T00:55:15Z","timestamp":1759366515879,"version":"build-2065373602"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"5s","funder":[{"name":"National Key Research and Development Program of China","award":["2023YFB4503704"],"award-info":[{"award-number":["2023YFB4503704"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Embed. Comput. Syst."],"published-print":{"date-parts":[[2025,11,30]]},"abstract":"<jats:p>Directed Acyclic Graph (DAG) models are extensively utilized across fields such as automotive, wireless communication, and deep learning, to capture the inherent functional dependencies. Topology of DAG has a significant impact on the performance of scheduling and resource management algorithms applied to it. Hence, it is imperative to generate all DAG topologies within the parameter ranges pertinent to an application domain, for impartial evaluation of such algorithms. Unfortunately, the existing DAG generators that are capable of offering full topology coverage have limited scalability and controllable parameters. This work reports open-source FT-DAG, an efficient and formally verified full-topology DAG generator that is able to control all major parameters, including the longest length, shortest length, width, jump layer, jump level, in-degree, out-degree, shape value as well as the number of nodes and edges. Experiments show that when the number of nodes is larger than 20, FT-DAG provides at least two orders of magnitude speedup compared to the state of the art and more orders to other generators. FT-DAG scales to 100 nodes in a typical industrial case study within hours.<\/jats:p>","DOI":"10.1145\/3760781","type":"journal-article","created":{"date-parts":[[2025,8,26]],"date-time":"2025-08-26T11:26:21Z","timestamp":1756207581000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["FT-DAG: An Efficient Full-Topology DAG Generator with Controllable Parameters"],"prefix":"10.1145","volume":"24","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-2617-0073","authenticated-orcid":false,"given":"Yinjie","family":"Fang","sequence":"first","affiliation":[{"name":"Hunan University College of Computer Science and Electronic Engineering","place":["Changsha, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6348-133X","authenticated-orcid":false,"given":"Liping","family":"Yang","sequence":"additional","affiliation":[{"name":"Hunan University College of Computer Science and Electronic Engineering","place":["Changsha, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9348-4662","authenticated-orcid":false,"given":"Weichen","family":"Liu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University","place":["Singapore, Singapore"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-0096-6185","authenticated-orcid":false,"given":"Guoquan","family":"Zhang","sequence":"additional","affiliation":[{"name":"Xiaomi Corporation","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-6134-6513","authenticated-orcid":false,"given":"Yaoyao","family":"Gu","sequence":"additional","affiliation":[{"name":"Xiaomi Corporation","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5902-2284","authenticated-orcid":false,"given":"Xiang","family":"Xiao","sequence":"additional","affiliation":[{"name":"Xiaomi Corporation","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-6627-3812","authenticated-orcid":false,"given":"Wei","family":"Qin","sequence":"additional","affiliation":[{"name":"Xiaomi Corporation","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6812-4809","authenticated-orcid":false,"given":"Xiangzhen","family":"Ouyang","sequence":"additional","affiliation":[{"name":"Xiaomi Corporation","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4053-8898","authenticated-orcid":false,"given":"Wanli","family":"Chang","sequence":"additional","affiliation":[{"name":"Computer Science, Hunan University College of Computer Science and Electronic Engineering","place":["Changsha, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,26]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-28016-0_2"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10766-021-00717-y"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/AINIT61980.2024.10581455"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS58335.2023.00021"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3641289"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.84"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2019.2910525"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3177046"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS49844.2020.00022"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2019.2893250"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/DAC56929.2023.10247711"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29400-7_5"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2020.3013045"},{"key":"e_1_3_2_15_2","volume-title":"Random Generation for the Performance Evaluation of Scheduling Algorithms","author":"Sayah Mohamad El","year":"2019","unstructured":"Mohamad El Sayah. 2019. Random Generation for the Performance Evaluation of Scheduling Algorithms. Ph.D. Dissertation. Universit\u00e9 Bourgogne Franche-Comt\u00e9."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2021.11.057"},{"key":"e_1_3_2_17_2","first-page":"239","article-title":"Counting labeled acyclic digraphs","author":"Robinson Robert W.","year":"1973","unstructured":"Robert W. Robinson. 1973. Counting labeled acyclic digraphs. New Directions in the Theory of Graphs (1973), 239\u2013273.","journal-title":"New Directions in the Theory of Graphs"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0069178"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90155-9"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(95)00119-H"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(94)00135-6"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20836"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-013-9428-y"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3154979.3154984"},{"issue":"1","key":"e_1_3_2_25_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","year":"1960","unstructured":"P. Erd\u0151s and A. R\u00e9nyi. 1960. On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1 (1960), 17\u201360.","journal-title":"Publications of the Mathematical Institute of the Hungarian Academy of Sciences"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109045"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.4108\/ICST.SIMUTOOLS2010.8667"},{"issue":"213","key":"e_1_3_2_28_2","first-page":"1","article-title":"Polynomial-time algorithms for counting and sampling Markov equivalent DAGs with applications","volume":"24","author":"Wien\u00f6bst Marcel","year":"2023","unstructured":"Marcel Wien\u00f6bst, Max Bannach, and Maciej Li\u015bkiewicz. 2023. Polynomial-time algorithms for counting and sampling Markov equivalent DAGs with applications. Journal of Machine Learning Research 24, 213 (2023), 1\u201345.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01174-1_61"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.21004"},{"key":"e_1_3_2_31_2","unstructured":"Keith Vallerio. 2008. Task graphs for free (tgff v3. 0). Official Version Released in April 15 (2008)."},{"issue":"3","key":"e_1_3_2_32_2","first-page":"782","article-title":"DAGEN-a tool to generate arbitrary directed acyclic graphs used for multiprocessor scheduling","volume":"2","author":"Amalarethinam D. I. George","year":"2011","unstructured":"D. I. George Amalarethinam and G. J. Joyce Mary. 2011. DAGEN-a tool to generate arbitrary directed acyclic graphs used for multiprocessor scheduling. International Journal of Research and Reviews in Computer Science 2, 3 (2011), 782.","journal-title":"International Journal of Research and Reviews in Computer Science"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/SAMOS.2016.7818372"},{"key":"e_1_3_2_34_2","first-page":"8","article-title":"A modular approach to random task graph generation","volume":"8","author":"Ashish Mishra","year":"2016","unstructured":"Mishra Ashish, Sharma Aditya, Verma Pranet, Abhijit R Asati, and Raju Kota Solomon. 2016. A modular approach to random task graph generation. Indian Journal of Science and Technology 8 (2016), 8.","journal-title":"Indian Journal of Science and Technology"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISORC58943.2023.00015"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.3390\/math8112050"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.79"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTAS48715.2020.000-4"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201008"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035927"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01989-7"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.09.003"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2021.112630"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-80223-3_26"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/MVHI.2010.190"},{"key":"e_1_3_2_46_2","volume-title":"The Art of Computer Programming","author":"Knuth Donald Ervin","year":"1997","unstructured":"Donald Ervin Knuth. 1997. The Art of Computer Programming. Vol. 3. Pearson Education."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1002\/jos.116"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/278241.278309"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/RTSS59052.2023.00061"}],"container-title":["ACM Transactions on Embedded Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3760781","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T17:13:58Z","timestamp":1759338838000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3760781"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,26]]},"references-count":48,"journal-issue":{"issue":"5s","published-print":{"date-parts":[[2025,11,30]]}},"alternative-id":["10.1145\/3760781"],"URL":"https:\/\/doi.org\/10.1145\/3760781","relation":{},"ISSN":["1539-9087","1558-3465"],"issn-type":[{"type":"print","value":"1539-9087"},{"type":"electronic","value":"1558-3465"}],"subject":[],"published":{"date-parts":[[2025,9,26]]},"assertion":[{"value":"2025-08-06","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-09-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}