Memory Optimization for Embedded Systems Using Worm-Partition Scheduling

Abstract

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 thesis deals with scheduling directed acyclic graph (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 0 (lVI +JED time. This is in contrast to the known method [12] for producing the minimum number of worms that runs in O(JVJ2+JVIIEI) steps. We apply the algorithm to well-known benchmarks and show its comparable result to the previous method. The.n 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 bounds are tight ones for these claSses of DAGs.