Title :
Algorithmic aspects of uncertainty driven scheduling
Author :
Memik, Seda Ogrenci ; Srivastava, Ankur ; Kursun, Eren ; Sarrafzadeh, Majid
Author_Institution :
Dept. of Comput. Sci., California Univ., Los Angeles, CA, USA
Abstract :
In this paper we discuss the algorithmic aspects of uncertainty driven scheduling which is a new design paradigm. Slack oriented design flow could be used to address the uncertainty problem in high level synthesis. We formalize the concept of slack and discuss different variations of the slack driven scheduling problem. The complexity issues are studied in detail and algorithms are proposed to solve the problem. These algorithms and proofs heavily exploit the concepts and techniques of graph theory and combinatorial optimization problems
Keywords :
VLSI; circuit CAD; circuit optimisation; computational complexity; data flow graphs; high level synthesis; integrated circuit design; scheduling; DFG; NP-complete problem; VLSI design; algorithmic aspects; automated design; combinatorial optimization problems; complexity issues; data flow graph; design paradigm; graph theory; high level synthesis; resource constrained scheduling; resource unconstrained scheduling; slack oriented design flow; uncertainty driven scheduling; Clocks; Computer science; Cost function; Data flow computing; Flow graphs; Processor scheduling; Robustness; Scheduling algorithm; Timing; Uncertainty;
Conference_Titel :
Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on
Conference_Location :
Phoenix-Scottsdale, AZ
Print_ISBN :
0-7803-7448-7
DOI :
10.1109/ISCAS.2002.1010336
