FT-DAG: An Efficient Full-Topology DAG Generator with Controllable Parameters
Open Access
- 26 September 2025
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 24 (5s) , 1-25
Abstract
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.Keywords
Funding Information
- National Key Research and Development Program of China (2023YFB4503704)
This publication has 40 references indexed in Scilit:
- Graph isomorphism: physical resources, optimization models, and algebraic characterizationsMathematical Programming, 2023
- A spectral version of Mantel's theoremDiscrete Mathematics, 2022
- A Comparative Survey of Big Data Computing and HPC: From a Parallel Programming Model to a Cluster ArchitectureInternational Journal of Parallel Programming, 2021
- Fast uniform generation of random graphs with given degree sequencesRandom Structures & Algorithms, 2021
- Analytic combinatorics of connected graphsRandom Structures & Algorithms, 2019
- Uniform random generation of large acyclic digraphsStatistics and Computing, 2013
- A standard task graph set for fair evaluation of multiprocessor scheduling algorithmsJournal of Scheduling, 2002
- Counting acyclic digraphs by sources and sinksDiscrete Mathematics, 1996
- Enumerative applications of a decomposition for graphs and digraphsDiscrete Mathematics, 1995
- On the number of labeled acyclic digraphsDiscrete Mathematics, 1992