A lower bound on general minimal resource interval scheduling with arbitrary component selection

Author

Shen, Z.X. ; Jong, C.C.

Author_Institution

Inst. of High Performance Comput., Nat. Univ. of Singapore, Singapore

Volume

6

fYear

1999

fDate

36342

Firstpage

378

Abstract

Exploring lower bound of scheduling is an important problem in high-level synthesis, In this paper, we address the problem of computing lower bound on the general minimal resource interval scheduling problem, called n-n-MRIS, in which arbitrary component selections are allowed in stead of the traditional unicomponent selection. The problem of n-n-MRIS is proved to be strongly NP hard. An efficient ILP model and a surrogate relaxation technique are proposed to produce a lower bound for the n-n-MRIS problem

Keywords

computational complexity; high level synthesis; scheduling; ILP model; arbitrary component selection; complexity; differential equation; elliptic wave filter; high-level synthesis; lower bound of scheduling; minimal resource interval scheduling; n-n-MRIS; surrogate relaxation; Algorithm design and analysis; Costs; Hardware; High level synthesis; High performance computing; Integer linear programming; Magnetic resonance imaging; Performance loss; Processor scheduling; Space exploration;

fLanguage

English

Publisher

ieee

Conference_Titel

Circuits and Systems, 1999. ISCAS '99. Proceedings of the 1999 IEEE International Symposium on

Conference_Location

Orlando, FL

Print_ISBN

0-7803-5471-0

Type

conf

DOI

10.1109/ISCAS.1999.780174

Filename

780174