MPT-based branch-and-bound strategy for scheduling problem in high-level synthesis

Abstract

A branch-and-bound algorithm based on a maximum possibility table (MPT) is proposed to solve scheduling problems in high-level synthesis. Six efficient priority rules are developed as bounding functions in the algorithm. Extensions for real-world constraints are also considered, including chained operations, multicycle operations, mutually exclusive operations and pipelined data paths. Experimental results indicate that the MPT-based algorithm returns competitive scheduling results at significant savings in execution time as compared with other methods.