An ILP Approach to the Slack Driven Scheduling Problem

Shih-Hsu HUANG  Chun-Hua CHENG  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.6   pp.1852-1858
Publication Date: 2006/06/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.6.1852
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: VLSI Design Technology and CAD
high-level synthesis,  integer linear programming,  scheduling,  slack optimization,  

Full Text: PDF>>
Buy this Article

With the advent of deep sub-micron era, there is a demand to consider the design closure problem in high-level synthesis. It is well known that the slack is an effective means of tolerating the uncertainties in operation delays. Previous work ever attempted to increase the usable slack based on a given initial schedule. Instead of the post-processing approach, this paper is the first attempt to the simultaneous application of operation scheduling and slack optimization. We use a 0-1 integer linear programming (0-1 ILP) approach to formally formulate the problem. Under the design constraints (timing and resource), our approach is applicable to two different objective functions: the maximization of the total usable slack and the maximization of the number of non-zero slack operations. Compared with previous work, our approach has the following two advantages: first, our approach guarantees the optimality; second, our approach is more suitable for the design space exploration.