Scheduling DAGs for Fixed-point DSP Processors by Using Worm Partitions

This paper concerns a code generation for directed acyclic graphs (DAGs). The set of edges that connect consecutively scheduled operations along with the nodes that correspond to the consecutively scheduled operations constitutes a worm. We propose an algorithm to construct a partitioning of a DAG into a collection of worms. This is done by finding the longest worm at the moment and maintaining the legality of worm partitioning. We characterize a legality of worm partitioning by introducing a simple set notation and proving its property. Based on that notation and its property, we prove that our algorithm correctly works. We also show that our algorithm works even in a DAG which contains interleaved sharing. Experimental results on several DAGS show that our technique generates worm partitioning of DAGs with small cardinality.