## A Fast Algorithm for Scheduling Time-Constrained Instructions on
Processors with ILP

* A. Leung, K.V. Palem, and
A. Pnueli*
Instruction scheduling is central to achieving
performance in modern processors with {\em
instruction level parallelism (ILP)}. Classical work in
this area has spanned the theoretical foundations of
algorithms for instruction scheduling with provable
optimality, as well as heuristic approaches with
experimentally validated performance improvements.
Typically, the theoretical foundations are developed in
the context of basic-blocks of code. In this paper, we
provide the theoretical foundations for scheduling
basic-blocks of instructions {\em with
time-constraints}, which can play an important role in
compile-time ILP optimizations in embedded
applications. We present an algorithm for scheduling
unit-execution-time instructions on machines with
multiple pipelines, in the presence of precedence
constraints, release-times, deadlines, and latencies
$l_{ij}$ between any pairs of instructions $i$ and $j$.
Our algorithm runs in time $O(n^3\alpha(n))$, where
$\alpha(n)$ is the functional inverse of the Ackermann
function. It can be used construct feasible schedules for
two classes of instances: (1) one pipeline and the
latencies between instructions are restricted to the
values of 0 and 1, and (2) arbitrary number of pipelines
and monotone-interval order precedences. Our result
can be seen as a natural extension of previous work on
instruction scheduling for pipelined machines in the
presence of deadlines.

*PACT 98: The 1998 International Conference on Parallel
Architectures and Compilation Techniques.*
12nd - 18th October, 1998, Paris, France.

PostScript.