A fine-grained data migration approach to application load balancing on MP mind machines
Stephen R. Wheat · 1992
Massively Parallel (MP) computing technologies, in particular Multiple-Instruction, Multiple-Data (MIMD) machines, have enabled the development of applications that require computational resources previously unobtainable. However, applications must be tailored to effectively use MP MIMD machines. Often this tailoring effort resembles that taken years ago with the introduction of vector super-computers. That is, application programmers must work at the machine's level of abstraction, resulting in application programs that are difficult to develop, maintain, and modify. In particular, programmers must spend a great amount of effort addressing load balancing issues to achieve the desired application performance. This dissertation addresses this issue by providing an automatic, dynamic load balancing facility for MP MIMD machines. Previous load balancing approaches have migrated entire tasks or data sets within the tasks. Approaches that migrate entire tasks are not fine-grained enough to evenly distribute the load of applications that consume the complete set of available processing resources. Approaches that migrate data sets have not effectively addressed the issue of data locality and, as such, are not appropriate for distributed memory MIMD machines. The research presented in this dissertation has resulted in a fine grained data migration approach, called tiling, to dynamic load balancing. Tiling effectively addresses the issues of processor load imbalances and data locality to achieve global processor load balance. Tiling is applicable to a large class of real-world applications. Furthermore, tiling is applicable to commercially available MIMD machines. Tiling does not require special hardware, nor does it require a particular vendor's MIMD implementation.