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

Instruction scheduling is central to achieving performance in modern processors with 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 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:one pipeline and the latencies between instructions are restricted to the values of 0 and 1, and arbitrary number of pipelines and monotone-interval order precedences. %The algorithm can also be used to construct minimal tardiness %schedules in polynomial time. Our result can be seen as a natural extension of previous work on instruction scheduling for pipelined machines in the presence of deadlines.