Directed Acyclic Graph Topology Generators: A Survey

Directed Acyclic Graphs (DAGs) are essential for modelling task dependencies across various domains, including industrial automation, autonomous systems, and many-core processors. DAG generators are widely used to evaluate the performance of scheduling algorithms. This survey systematically analyzes existing DAG generation algorithms, evaluating their search space, efficiency, and uniformity. We categorize existing DAG generators into three primary methodologies: Triangular Matrix-Based (TMB), Layer-by-Layer (LBL), and Poset-Based (POB) methods. Furthermore, we introduce a dedicated testing tool that quantitatively assesses various DAG generators’ performance. Experimental results show each DAG generator’s strengths and limitations, offering insights into their applicability in real-world scheduling and resource allocation problems. These findings provide a foundation for selecting suitable DAG generation methods for benchmarking scheduling heuristics and improving DAG task modelling.