Kv. Palem et Bb. Simons, SCHEDULING TIME-CRITICAL INSTRUCTIONS ON RISC MACHINES, ACM transactions on programming languages and systems, 15(4), 1993, pp. 632-658
We present a polynomial time algorithm for constructing a minimum comp
letion time schedule of instructions from a basic block on RISC machin
es such as the Sun SPARC, the IBM 801, the Berkeley RISC machine, and
the HP Precision Architecture. Our algorithm can be used as a heuristi
c for RISC processors with longer pipelines, for which there is no kno
wn optimal algorithm. Our algorithm can also handle time-critical inst
ructions, which are instructions that have to be completed by a specif
ic time. Time-critical instructions occur in some real-time computatio
ns, and can also be used to make shared resources such as registers qu
ickly available for reuse. We also prove that in the absence of time-c
ritical constraints, a greedy scheduling algorithm always produces a s
chedule for a target machine with multiple identical pipelines that ha
s a length less than twice that of an optimal schedule. The behavior o
f the heuristic is of interest because, as we show, the instruction sc
heduling problem becomes NP-hard for arbitrary length pipelines, even
when the basic block of code being input consists of only several inde
pendent streams of straightline code, and there are no time-critical c
onstraints. Finally, we prove that the problem becomes NP-hard even fo
r small pipelines, no time-critical constraints, and input of several
independent streams of straightline code if either there is only a sin
gle register or if no two instructions are allowed to complete simulta
neously because of some shared resource such as a bus.