Convergent Scheduling
Authors:
Walter Lee, Diego Puppin, Shane Swenson, Saman Amarasinghe
Address: 200 Technology Square, 626A
Cambridge, Ma 02139
Affiliation: MIT
Abstract:
Convergent scheduling is a general framework for cluster assignment
and instruction scheduling on spatial architectures. A convergent
scheduler is composed of independent passes, each implementing a
heuristic that addresses a particular problem or constraint. The
passes share a simple, common interface that provides spatial and
temporal preference for each instruction. Preferences are not
absolute; instead, the interface allows a pass to express the
confidence of its preferences, as well as preferences for multiple
space and time slots. A pass operates by modifying these preferences.
By applying a series of passes that address all the relevant
constraints, the convergent scheduler can produce a schedule that
satisfies all the important constraints. Because all passes are
independent and need to understand only one interface to interact with
each other, convergent scheduling simplifies the problem of handling
multiple constraints and co-developing different heuristics. We have
applied convergent scheduling to two spatial architectures: the Raw
processor and a clustered VLIW machine. It is able to successfully
handle traditional constraints such as parallelism, load balancing,
and communication minimization, as well as constraints due to
preplaced instructions, which are instructions with predetermined
cluster assignment. Convergent scheduling is able to obtain an
average performance improvement of 21% over the existing space-time
scheduler of the Raw processor, and an improvement of 14% over
state-of-the-art assignment and scheduling techniques on a clustered
VLIW architecture.
Web Site:
cag.lcs.mit.edu/commit