Time-Constrained Instruction Scheduling
Overview
This project investigates the problem of scheduling
instructions (or unit-execution-time tasks) in the presence of arbitrary
release-times and deadlines, precedence and latency constraints.
Release-times and deadlines constraints occur naturally in
real-time applications, and can also be generated from decomposing
a complex resource allocation problem typical in compiler optimizations.
For example, by imposing an early
deadline or a late release-time on an instruction using a critical
register, the scheduler can reduce register pressure. Similarly,
a complex global instruction scheduling problem may be decomposed into two or
more simpler problems, such that latencies that cross the boundaries of the
decomposed problems can be treated as release-times and deadlines in each
of the subproblems.
Polynomial Solvability Results
In the paper
A fast algorithm for scheduling time-constrained
instructions on processors with ILP (PACT '98),
I presented a generic algorithm
for optimally scheduling basic block instances of the following forms:
- (a) 1 pipeline, arbitrary precedence constraints, arbitrary release-times
and deadlines, and latencies of 0 and 1,
- (b) m pipelines, interval order
precedence constraints, arbitrary release-times
and deadlines, and monotone latencies,
- (c) 2 processors, arbitrary precedence constraints, arbitrary release-times
and deadlines, and zero latencies,
- (d) m pipelines, outtree precedence constraints, arbitrary release-times
and latencies = k ,
- (e) m pipelines, intree precedence constraints, arbitrary deadlines and
latencies = k .
- (f) 1 pipeline, arbitrary processing times that are greater than 1,
latencies of 0 and 1, and arbitrary precedence constraints.
Algorithmic Results
The polynomial complexity of instances (a), (b) and (f) are previously unknown.
The above results subsume almost all previous known polynomially solvable
instances in the area of deterministic scheduling with pipelines, latencies,
deadlines and release-times, including previous results
obtained by Bruno Jones and So [1980],
Garey and Johnson [1976, 1977], Palem and Simons [1993] and,
Finta and Liu[1999].
The generic algorithm is based on
deadline modification
and list-scheduling.
Modified deadlines are computed via a
particular relaxation method which can be shown to be a generalization
of almost all previously deadline modification schemes, i.e. our algorithm
can be seen as a unification result.
This algorithm runs in O(n^3 alpha(n)) time, where alpha(n) is the functional
inverse of the Ackermann function. The runtime has since been improved
to O(n^2 log(n) alpha(n)), and also extended to instances of the form:
- (g) 2 processors, arbitrary precedence constraints, arbitrary release-times
and deadlines, and latencies of 0 and -1.
Latencies of -1 can be used to model output-
and anti-
dependences, in situations
where an instruction is allowed to start before or concurrent
with another, but no later. These newer results are described in the
following full report:
Related Applications
Some addition research, such as a time-constraint specification language
for real-time compilation,
have been done using this algorithm as a starting point.
- TimeC: A Time Specification Language for ILP Processor Compilation,
with Krishna K. Palem, Amir Pnueli, 1998.
In The 5th Annual Australasian Conference on
Parallel And Real-Time Systems, 1998.
Electronic copies of this and other related papers can be obtained from the
Trimaran
project home page.
