ON THE UPPER BOUND OF SCHEDULING INSTRUCTIONS ON PIPELINED PROCESSORS WITH DELAY

Abstract

Several high performance microprocessor systems have been developed in recent years. Other than the fact that the system clocks were pushed to a higher rate than before, these systems were improved throughout by issuing more than one instruction within a cycle. Due to their increasingly complex pipeline structures as well as employment of multiple functional units, object codes of these systems are in general required to be reorganized in order to keep functional units busy and to avoid pipeline interlocks. Success of such a system design hence depends on not only how many hardware resources it provides, but primarily how efficiently these resources can be utilized. In this paper we analyze the worst case of applying a greedy method to schedule a set of instructions on m pipelined processors or functional units. Each instruction under discussion here will incur a delay of at most z cycles after it is issued to execute. The ultimate criterion is to minimize the completion time of the last completed instruction. The problem is NP-hard. Let w(g) be the length of an arbitrary greedy schedule on m processors, and w(o) be the length of an optimal schedule on m' processors. We prove that w(g)/w(o) less than or equal to (1+m'/m-1/((z+1)m)). The results of this research can serve as the basis for superscalar instruction scheduling as well as some other related fields, such as superscalar architecture designs.