A novel scheduling approach based on binary decision diagram
LccTS 157.5 Y36 1992
LcshScheduling (Management) - Data processing
Electronic data processing - Electronic circuit design
MetadataShow full item record
AbstractIn 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.
Bibliography: p. 84-87.
CitationYang, L. (1992). A novel scheduling approach based on binary decision diagram (Unpublished master's thesis). University of Calgary, Calgary, AB. doi:10.11575/PRISM/20430
University of Calgary graduate students retain copyright ownership and moral rights for their thesis. You may use this material in any way that is permitted by the Copyright Act or through licensing that has been assigned to the document. For uses that are not allowable under copyright legislation or licensing, you are required to seek permission.