A Tree-Based Scheduling Algorithm for Control-Dominated Circuits

Scheduling algorithms for control dominated applications have not been widely published. Path-based scheduling was the first attempt to tackle this problem. This approach works well on the benchmark examples. However, it imposes a restriction on the execution order of the operations before scheduling. We alleviate this restriction by representing all the execution paths by a tree. Tree representation not only inherits all the advantages of the path representation, but also releases the execution order constraint. A two phase algorithm is proposed to solve the scheduling problem on the tree representation. In the first phase, a partitioning algorithm is performed on the tree in a top down manner in order to optimally execute every path. In the second phase, the corresponding state transition graph is constructed in a bottom-up manner in order to minimize the total number of states as well as the control logic. By utilizing node unification, the complexity of the algorithm can be restricted to O(pbn²), where p is the number of paths, b is the number of blocks and n is the number of operations. We tested the algorithm on a set of benchmarks and achieved reductions on the number of states as compared with previous algorithms.