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 mainraining 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 resuits on several DAGS show that our technique generates worm partitioning of DAGs with small cardinality.
Jinpyo Hong J. Ramanujam
School of Internet-Media Korea University of Technology and Education Cheonan,KOREA Dept.of Electrical and Computer Engineering Louisiana State University Baton Rouge,LA,USA
国际会议
成都
英文
567-574
2008-01-01（万方平台首次上网日期，不代表论文的发表时间）