Locality in Scheduling Models of Parallel Computation
Peter Thanisch, Michael G. Norman, Cristina Boeres, Susanna Pelagatti · Birkhäuser Basel eBooks · 1994
Effective tools for the design of parallel algorithms must be based on a computational model for parallel computing that is a trade-off between realism and simplicity. Where the underlying programming model requires the mapping and scheduling of tasks, the computational model should incorporate some notion of interprocessor communication delay. If the target architecture is massively parallel then a more complex model, including some notion of locality, may be required. When working with locality-ignoring computational models, researchers on the mapping problem have been able to discover efficient approximation techniques that are guaranteed to find a mapping with a near-optimal makespan. However, techniques with such good performance bounds have so far eluded researchers investigating locality-based computational models. In an initial attempt to explain this difference, we show that estimating the minimum makespan in locality-based models is problematic because processor requirements may become unreasonable. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.