For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
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
Publication Date: 2006/06/01
Online ISSN: 1745-1337
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>>
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.