Load balancing of irregular parallel applications on heterogeneous computing environments

Heterogeneous computing;Parallel programming (Computer science);Electronic data processing--Distributed processing;Computer algorithms

Janjic, Vladimir ; Hammond, Kevin ; Hammond, Kevin

University:University of St Andrews

Department:Computer Science (School of)

关键词: Heterogeneous computing;    Parallel programming (Computer science);    Electronic data processing--Distributed processing;    Computer algorithms;   

Others  :  https://research-repository.st-andrews.ac.uk/bitstream/handle/10023/2540/VladimirJanjicPhDThesis.pdf?sequence=3&isAllowed=y

来源: DR-NTU

【 摘 要 】

Large-scale heterogeneous distributed computing environments (such as ComputationalGrids and Clouds) offer the promise of access to a vast amount of computingresources at a relatively low cost. In order to ease the application development anddeployment on such complex environments, high-level parallel programming languagesexist that need to be supported by sophisticated runtime systems. One of the mainproblems that these runtime systems need to address is dynamic load balancing thatensures that no resources in the environment are underutilised or overloaded withwork.This thesis deals with the problem of obtaining good speedups for irregular applicationson heterogeneous distributed computing environments. It focuses on workstealingtechniques that can be used for load balancing during the execution of irregularapplications. It specifically addresses two problems that arise during work-stealing:where thieves should look for work during the application execution and how victimsshould respond to steal attempts.In particular, we describe and implement a new Feudal Stealing algorithm andalso we describe and implement new granularity-driven task selection policies in theSCALES simulator, which is a work-stealing simulator developed for this thesis. In addition,we present the comprehensive evaluation of the Feudal Stealing algorithm andthe granularity-driven task selection policies using the simulations of a large class ofregular and irregular parallel applications on a wide range of computing environments.We show how the Feudal Stealing algorithm and the granularity-driven task selectionpolicies bring significant improvements in speedups of irregular applications, comparedto the state-of-the-art work-stealing algorithms. Furthermore, we also present the implementationof the task selection policies in the Grid-GUM runtime system [AZ06]for Glasgow Parallel Haskell (GpH) [THLPJ98], in addition to the implementation inSCALES, and we also present the evaluation of this implementation on a large set ofsynthetic applications.