A Comparison of Task Partitioning Techniques
M. E. McArdle, Carolyn L. McCreary · 1991
Automatically converting a program into a version for execution on a multiprocessor system involves partitioning and scheduling the tasks of the computation onto processors. Given a program dependence graph representing the computational tasks in a program and the dependencies between those tasks, they must be mapped onto the multiprocessor architecture in order to minimize the total execution time. Three methods of task partitioning are compared: linear clustering, the LAST algorithm, and clan decomposition. It is shown that the partitioning strategy based upon clan decomposition produces superior schedules than those generated by the other techniques.