A novel scheduling approach based on binary decision diagram

Simple item page
dc.contributor.advisorGu, Jun
dc.contributor.authorYang, Lilie
dc.date.accessioned2005-08-05T16:55:22Z
dc.date.available2005-08-05T16:55:22Z
dc.date.issued1992
dc.descriptionBibliography: p. 84-87.en
dc.description.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.
dc.format.extentx, 87 leaves ; 30 cm.en
dc.identifier.citationYang, L. (1992). A novel scheduling approach based on binary decision diagram (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca. doi:10.11575/PRISM/20430en_US
dc.identifier.doihttp://dx.doi.org/10.11575/PRISM/20430
dc.identifier.isbn0315832908en
dc.identifier.lccTS 157.5 Y36 1992en
dc.identifier.urihttp://hdl.handle.net/1880/31165
dc.language.isoeng
dc.publisher.facultyEngineering
dc.publisher.institutionUniversity of Calgaryen
dc.publisher.placeCalgaryen
dc.rightsUniversity 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.
dc.subject.lccTS 157.5 Y36 1992en
dc.subject.lcshScheduling (Management) - Data processing
dc.subject.lcshElectronic data processing - Electronic circuit design
dc.titleA novel scheduling approach based on binary decision diagram
dc.typemaster thesis
thesis.degree.disciplineElectrical and Computer Engineering
thesis.degree.grantorUniversity of Calgary
thesis.degree.nameMaster of Science (MSc)
ucalgary.item.requestcopytrue
ucalgary.thesis.accessionTheses Collection 58.002:Box 903 520541808
ucalgary.thesis.notesoffsiteen
ucalgary.thesis.uarcreleaseyen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_Yang_1992.pdf
Size:
28.56 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Legacy Theses