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).
- algorithm analysis
- Instruction scheduling