An ILP Approach to the Slack Driven Scheduling Problem

Shih-Hsu HUANG; Chun-Hua CHENG

doi:10.1093/ietfec/e89-a.6.1852

An ILP Approach to the Slack Driven Scheduling Problem

Shih-Hsu HUANG, Chun-Hua CHENG

Full Text Views

0

Share
Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.6 pp.1852-1858

Publication Date: 2006/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.6.1852

Type of Manuscript: LETTER

Category: VLSI Design Technology and CAD

Cite this

Copy

Shih-Hsu HUANG, Chun-Hua CHENG, "An ILP Approach to the Slack Driven Scheduling Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 6, pp. 1852-1858, June 2006, doi: 10.1093/ietfec/e89-a.6.1852.
Abstract: 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.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.6.1852/_p

Copy

@ARTICLE{e89-a_6_1852,
author={Shih-Hsu HUANG, Chun-Hua CHENG, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An ILP Approach to the Slack Driven Scheduling Problem},
year={2006},
volume={E89-A},
number={6},
pages={1852-1858},
abstract={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.},
keywords={},
doi={10.1093/ietfec/e89-a.6.1852},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - An ILP Approach to the Slack Driven Scheduling Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1852
EP - 1858
AU - Shih-Hsu HUANG
AU - Chun-Hua CHENG
PY - 2006
DO - 10.1093/ietfec/e89-a.6.1852
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2006
AB - 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.
ER -