Wavesched: A novel scheduling technique for control-flow intensive behavioral descriptions

Ganesh Lakshminarayana, Kamal S. Khouri, Niraj K. Jha

Research output: Contribution to journalConference article

18 Scopus citations

Abstract

In this paper, we present a novel scheduling algorithm targeted towards minimizing the average execution time of control-flow intensive behavioral descriptions. Our algorithm uses a control-data flow graph (CDFG) model, which preserves the parallelism inherent in the application. It explores previously unexplored regions of the solution space through its ability to overlap the schedules of independent iterative constructs, whose bodies share resources. It also incorporates well-known optimization techniques like loop unrolling in a natural fashion. This is made possible by a general loop-handling technique, which we have devised. Application of the algorithm to several common benchmarks demonstrates up to 4.8-fold improvement in expected schedule length over existing scheduling algorithms, without paying a price in terms of the best- and worst-case schedule lengths required to execute the behavioral description (in fact, frequently, the best/worst-case schedule lengths are also better for our algorithm).

Original languageEnglish (US)
Pages (from-to)244-250
Number of pages7
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
DOIs
StatePublished - Jan 1 1997
EventProceedings of the 1997 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, USA
Duration: Nov 9 1997Nov 13 1997

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Wavesched: A novel scheduling technique for control-flow intensive behavioral descriptions'. Together they form a unique fingerprint.

  • Cite this