Optimal Distribution and Scheduling of Parallel WorMoads with Synchronization Delays.
Emile Hadaad · 1994
Optimal program module distributions are determined for a parallel workload to be run on the processors of a homogeneous multiple-processor system. The optimization minimizes a weighted combination of cost and performance metrics: workload completion time, processors total idle time , execution cost, communication cost, and load imbalance. The time-related metrics are formulated based on a realistic modeling of the serial and concurrent time activities of the system processors including synchronization delays. Exact analysis leads to closed-form analytical criteria and eficient algorithms for determining the optimal load distributions which are found to be of four types: balancing all modules over all processors, assigning all modules to one processor, balancing all modules over some processors, and balancing all modules over all except one processor with a peak load. The algorithms have linear time-complexity . For a given optimal load distribution, further optimization leads to the elimination of sync delay for the busiest processor by selecting a specific module assignment.