Scheduling tree-structured programs in the LogP model
J.H. Verriet · 1997
The LogP model is a model of parallel computation that characterises a parallel computer architecture by four parameters: the latency L, the overhead o, the gap g and the number of processors P. We study the problem of constructing minimum-length schedules for treestructured programs in the LogP model. This problem is proved to be NP-hard, even for outtrees of height two in LogP models with an unlimited number of processors. For outtrees of height two, a 2-approximation algorithm is presented. For intrees of height two, two approximation algorithms are presented: a 3-approximation algorithm for LogP models with an unrestricted number of processors and a 4, 2-approximation algorithm for P LogP models with a nite number of processors. For the problem of constructing minimum-length schedules for d-ary intrees in a LogP model with a nite number of processors, three approximation algorithms are presented that are applicable in many models of parallel computation. The rst constructs schedules for full d-ary intrees of length at most 2 + 2 times the length of an optimal schedule plus the time d required for (d +1)P, 1 communication operations. The second constructs schedules on P processors of length at most d +1, d2 +d times the length of a minimum-length schedule plus d+P the time needed for d(P, 1) , 1 communication operations. The third constructs schedules of length at most 3, 6 P +2 of d(d, 1)(P, 1) , 1 communication operations.