On optimal loop unrolling in two-processor scheduling

Hesham El-Rewini, Hesham H. Ali

Research output: Contribution to journalArticle

Abstract

In this paper, we study the problem of scheduling loop task graphs onto two processor systems to minimize the exceution time. We use the idea of loop unrolling to uncover dependence among different loop iterations in loop task graphs. The scheduling is divided into two stages: determining an optimal unrolling factor, and constructing an optimal schedule for this unrolling factor. We propose a criterion for optimal loop unrolling for unit-delay task graphs, where the tasks are enclosed in a single loop. Our main theorem presents a useful test for detecting optimal unrolling factors. A scheduling algorithm that employs the concept of optimal loop unrolling is introduced. We also present serial and parallel algorithms to find the best unrolling factor.

Original languageEnglish (US)
Pages (from-to)107-119
Number of pages13
JournalParallel Algorithms and Applications
Volume7
Issue number1-2
DOIs
StatePublished - Jan 1 1995

Keywords

  • Loop unrolling
  • Optimal scheduling
  • Parallel programs
  • Replicated task graphs
  • Scheduling loops
  • Two processor scheduling

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'On optimal loop unrolling in two-processor scheduling'. Together they form a unique fingerprint.

  • Cite this