SCHEDULING TIME-CRITICAL INSTRUCTIONS ON RISC MACHINES

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.