Ba. Malloy et al., SCHEDULING DAGS FOR ASYNCHRONOUS MULTIPROCESSOR EXECUTION, IEEE transactions on parallel and distributed systems, 5(5), 1994, pp. 498-508
Citations number
27
Categorie Soggetti
System Science","Engineering, Eletrical & Electronic","Computer Science Theory & Methods
A new approach is given for scheduling a sequential instruction stream
for execution ''in parallel'' on asynchronous multiprocessors. The ke
y idea in our approach is to exploit the fine grained parallelism pres
ent in the instruction stream. In this context, schedules are construc
ted by a careful balancing of execution and communication costs at the
level of individual instructions, and their data dependencies. Three
methods are used to evaluate our approach. First, several existing met
hods are extended to the fine grained situation considered here. Our a
pproach is then compared to these methods using both static schedule l
ength analyses, and simulated executions of the scheduled code. In eac
h instance, our method is found to provide significantly shorter sched
ules. Second, by varying parameters such as the speed of the instructi
on set, and the speed/parallelism in the interconnection structure, si
mulation techniques are used to examine the effects of various archite
ctural considerations on the executions of the schedules. These result
s show that our approach provides significant speedups in a wide-range
of situations. Third, schedules produced by our approach are executed
on a two-processor Data General shared memory multiprocessor system.
These experiments show that there is a strong correlation between our
simulation results (those parameterized to ''model'' the Data General
system), and these actual executions, and thereby serve to validate th
e simulation studies. Together, our results establish that fine graine
d parallelism can be exploited in a substantial manner when scheduling
a sequential instruction stream for execution ''in parallel'' on asyn
chronous multiprocessors.