Code Generation: On the Scheduling of DAGs Using Worm-Partition

Code generation consists of three main stages, instruction selection, scheduling and register allocation. The scheduling stage is very important because it affects the execution time of resulting code as well as the associated memory space needed to store the program. This paper deals with scheduling directed acyclic graphs (DAGs) using worm-partition. First, we develop a new algorithm to partition DAGs into a collection of worms while ensuring that the worm-partition is legal. Although the algorithm does not guarantee the minimum number of worms, it runs in optimal O(|V| + |E|) time. This is in contrast to the known method for producing the minimum number of worms that runs in O(^|V|2 + |V| |E|). We apply the algorithm to benchmark real problems and show its comparable results to the previous method. Then we study some DAG properties that are related to worm partitioning. We derive a necessary condition for the minimum number of worms in a given DAG. In other words, a lower bound for the number of worms. Then we identify two important classes of DAGs, for which this necessary condition is sufficient as well; i.e. we show that the lower bound is a tight one. Finally, we show that our algorithm generates the minimum number of worms for theses classes of DAGs.