A novel scheduling approach based on binary decision diagram

Abstract

In integrated circuit design scheduling plays an important role in determining the overall performance of a high-level synthesis system. This thesis addresses the design of an efficient algorithm to solve the scheduling problem. The traditional integer linear programming (ILP) approach handles the scheduling problem with the combination of the number of input operations and scheduling steps. In this method, the number of input variables is a product of operations and scheduling steps of each operation. Since the valid scheduling steps depend heavily on the timing constraints of the scheduling problem, the input variables and thus the computing time grow drastically as the timing limits increase. An efficient scheduling model based on the binary decision diagram (BDD) is presented. In this approach, data dependent operations in the scheduling problem are handled as a coherent group. Therefore, many redundant variables and constraint equations in ILP formulation are removed. This has significantly improved the efficiency of previous IPL scheduling computation. The experiment results show that ILP variables and equations have been reduced by approximately 10% to 30% in our scheduling model. The advantages of this method become more evident in solving large and complicated scheduling problems.