This paper presents a novel variant of work stealing for load balancing in a distributed graph reducer, executing a semi-explicit parallel dialect of Haskell. The key concept of this load-balancer is colocating related sparks (potential parallelism) using maximum prefix matching on the encoding of the spark’s ancestry within the computation tree, reconstructed at run time, in spark selection decisions. We evaluate spark colocation in terms of performance and scalability on a set of five benchmarks on a Beowulf-class cluster of multi-core machines using upÂ to 256 cores. In comparison to the baseline mechanism, we achieve speedup increase of upÂ to 46% for three out of five applications, due to improved locality and load balance throughout the execution as demonstrated by profiling data. For one less scalable program and one program with excessive amounts of very fine-grained parallelism we observe drops in speedup by 17% and 42%, respectively. Overall, spark colocation results in reduced mean time to fetch the required data and in higher degree of parallelism of finer granularity, which is most beneficial on higher PE numbers.
|Title of host publication||Trends in Functional Programming|
|Subtitle of host publication||19th International Symposium, TFP 2018, Gothenburg, Sweden, June 11–13, 2018, Revised Selected Papers|
|Editors||Michał Pałka, Magnus Myreen|
|Number of pages||19|
|Publication status||E-pub ahead of print - 24 Apr 2019|
|Event||19th International Symposium on Trends in Functional Programming 2018 - Chalmers University, Gothenburg, Sweden|
Duration: 11 Jun 2018 → 13 Jun 2018
|Name||Lecture Notes in Computer Science|
|Conference||19th International Symposium on Trends in Functional Programming 2018|
|Abbreviated title||TFP 2018|
|Period||11/06/18 → 13/06/18|
- Adaptive parallelism
- Distributed-memory work stealing
- Graph reduction
- Load balancing
- Parallel functional programming
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science(all)
FingerprintDive into the research topics of 'Colocation of Potential Parallelism in a Distributed Adaptive Run-Time System for Parallel Haskell'. Together they form a unique fingerprint.
Dataset for paper "Colocation of Potential Parallelism in a Distributed Adaptive Run-Time System for Parallel Haskell"
Loidl, H. (Creator) & Belikov, E. (Creator), Heriot-Watt University, 26 Jun 2019