A BOUND ANALYSIS OF SCHEDULING INSTRUCTIONS ON PIPELINED PROCESSORS WITH A MAXIMAL DELAY OF ONE CYCLE

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 w(g) and w(o) be the completion times of an arbitrary greedy schedule and the optimal schedule respectively. We find that the bound is w(g)/w(o) less-than-or-equal-to (2-1/2m).