Title :
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
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;
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
DOI :
10.1109/ISCAS.1999.780174
