A bound analysis of scheduling instructions on pipelined processors with a maximal delay of one cycle

Hong Chich Chou*, Chung-Ping Chung

*Corresponding author for this work

Research output: Contribution to journalArticle

Abstract

In this paper we study the problem of scheduling a set of partially ordered instructions with a maximal pipeline delay of one cycle on m processors (or functional units). The ultimate criterion is to minimize the execution of time of the set of instructions. This problem is NP-hard, hence we analyze the worst case of a greedy schedule, since the optimal schedule of this problem is also greedy. Let wg and wo be the completion times of an arbitrary greedy schedule and the optimal schedule respectively. We find that the bound is wg/wo ≤ (2-1/2m).

Original languageEnglish
Pages (from-to)393-399
Number of pages7
JournalParallel Computing
Volume18
Issue number4
DOIs
StatePublished - 1 Jan 1992

Keywords

  • algorithm analysis
  • Instruction scheduling
  • NP-completeness

Fingerprint Dive into the research topics of 'A bound analysis of scheduling instructions on pipelined processors with a maximal delay of one cycle'. Together they form a unique fingerprint.

  • Cite this