Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures

A. A. Zain, P. Trinder, M. Aswad, G. Michaelson, K. Hammond, J. Berthold

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

With the emergence of commodity multicore architectures, exploiting tightly-coupled parallelism has become increasingly important. Functional programming languages, such as Haskell, are, in principle, well placed to take advantage of this trend, offering the ability to easily identify large amounts of fine-grained parallelism. Unfortunately, obtaining real performance benefits has often proved hard to realise in practice.This paper reports on a new approach using middleware that has been constructed using the Eden parallel dialect of Haskell. Our approach is "low pain" in the sense that the programmer constructs a parallel program by inserting a small number of higher-order algorithmic skeletons at key points in the program. It is "high gain" in the sense that we are able to get good parallel speedups. Our approach is unusual in that we do not attempt to use shared memory directly, but rather coordinate parallel computations using a message-passing implementation. This approach has a number of advantages Firstly, coordination, i.e. locking and communication,is both confined to limited shared memory areas, essentially the communication buffers, and is also isolated within well-understood libraries. Secondly, the coarse thread granularity that we obtain reduces coordination overheads, so locks are normally needed only on (relatively large) messages, and not on individual data items, as is often the case for simple shared-memory implementations. Finally, cache coherency requirements are reduced since individual tasks do not share caches, and can garbage collect independently. We report results for two representative computational algebra problems. Computational algebra is a challenging application area that has not been widely studied in the general parallelism community. Computational algebra applications have high computational demands, and are, in principle, often suitable for parallel execution, but usually display a high degree of irregularity in terms of both task and data structure. This makes it difficu lt to construct parallel applications that perform well in practice. Using our system, we are able to obtain both extremely good processor utilisation (97%) and very good absolute speedups (up to 7.7) on an eight-core machine. © 2009 ACM.

Original languageEnglish
Title of host publicationProceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09
Pages25-36
Number of pages12
DOIs
Publication statusPublished - 2009
Event4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming - Savannah, GA, United States
Duration: 20 Jan 200920 Jan 2009

Conference

Conference4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming
Abbreviated titleDAMP'09
CountryUnited States
CitySavannah, GA
Period20/01/0920/01/09

Fingerprint

Multicore programming
Algebra
Data storage equipment
Functional programming
Communication
Message passing
Middleware
Computer programming languages
Data structures

Keywords

  • Algorithmic Skeletons
  • Computational Algebra
  • Eden
  • GAP
  • Haskell
  • Multicore Parallelism

Cite this

Zain, A. A., Trinder, P., Aswad, M., Michaelson, G., Hammond, K., & Berthold, J. (2009). Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures. In Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09 (pp. 25-36) https://doi.org/10.1145/1481839.1481843
Zain, A. A. ; Trinder, P. ; Aswad, M. ; Michaelson, G. ; Hammond, K. ; Berthold, J. / Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures. Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09. 2009. pp. 25-36
@inproceedings{5a8455b9444748f4a2473da0648c0150,
title = "Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures",
abstract = "With the emergence of commodity multicore architectures, exploiting tightly-coupled parallelism has become increasingly important. Functional programming languages, such as Haskell, are, in principle, well placed to take advantage of this trend, offering the ability to easily identify large amounts of fine-grained parallelism. Unfortunately, obtaining real performance benefits has often proved hard to realise in practice.This paper reports on a new approach using middleware that has been constructed using the Eden parallel dialect of Haskell. Our approach is {"}low pain{"} in the sense that the programmer constructs a parallel program by inserting a small number of higher-order algorithmic skeletons at key points in the program. It is {"}high gain{"} in the sense that we are able to get good parallel speedups. Our approach is unusual in that we do not attempt to use shared memory directly, but rather coordinate parallel computations using a message-passing implementation. This approach has a number of advantages Firstly, coordination, i.e. locking and communication,is both confined to limited shared memory areas, essentially the communication buffers, and is also isolated within well-understood libraries. Secondly, the coarse thread granularity that we obtain reduces coordination overheads, so locks are normally needed only on (relatively large) messages, and not on individual data items, as is often the case for simple shared-memory implementations. Finally, cache coherency requirements are reduced since individual tasks do not share caches, and can garbage collect independently. We report results for two representative computational algebra problems. Computational algebra is a challenging application area that has not been widely studied in the general parallelism community. Computational algebra applications have high computational demands, and are, in principle, often suitable for parallel execution, but usually display a high degree of irregularity in terms of both task and data structure. This makes it difficu lt to construct parallel applications that perform well in practice. Using our system, we are able to obtain both extremely good processor utilisation (97{\%}) and very good absolute speedups (up to 7.7) on an eight-core machine. {\circledC} 2009 ACM.",
keywords = "Algorithmic Skeletons, Computational Algebra, Eden, GAP, Haskell, Multicore Parallelism",
author = "Zain, {A. A.} and P. Trinder and M. Aswad and G. Michaelson and K. Hammond and J. Berthold",
year = "2009",
doi = "10.1145/1481839.1481843",
language = "English",
isbn = "9781605584171",
pages = "25--36",
booktitle = "Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09",

}

Zain, AA, Trinder, P, Aswad, M, Michaelson, G, Hammond, K & Berthold, J 2009, Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures. in Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09. pp. 25-36, 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, Savannah, GA, United States, 20/01/09. https://doi.org/10.1145/1481839.1481843

Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures. / Zain, A. A.; Trinder, P.; Aswad, M.; Michaelson, G.; Hammond, K.; Berthold, J.

Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09. 2009. p. 25-36.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures

AU - Zain, A. A.

AU - Trinder, P.

AU - Aswad, M.

AU - Michaelson, G.

AU - Hammond, K.

AU - Berthold, J.

PY - 2009

Y1 - 2009

N2 - With the emergence of commodity multicore architectures, exploiting tightly-coupled parallelism has become increasingly important. Functional programming languages, such as Haskell, are, in principle, well placed to take advantage of this trend, offering the ability to easily identify large amounts of fine-grained parallelism. Unfortunately, obtaining real performance benefits has often proved hard to realise in practice.This paper reports on a new approach using middleware that has been constructed using the Eden parallel dialect of Haskell. Our approach is "low pain" in the sense that the programmer constructs a parallel program by inserting a small number of higher-order algorithmic skeletons at key points in the program. It is "high gain" in the sense that we are able to get good parallel speedups. Our approach is unusual in that we do not attempt to use shared memory directly, but rather coordinate parallel computations using a message-passing implementation. This approach has a number of advantages Firstly, coordination, i.e. locking and communication,is both confined to limited shared memory areas, essentially the communication buffers, and is also isolated within well-understood libraries. Secondly, the coarse thread granularity that we obtain reduces coordination overheads, so locks are normally needed only on (relatively large) messages, and not on individual data items, as is often the case for simple shared-memory implementations. Finally, cache coherency requirements are reduced since individual tasks do not share caches, and can garbage collect independently. We report results for two representative computational algebra problems. Computational algebra is a challenging application area that has not been widely studied in the general parallelism community. Computational algebra applications have high computational demands, and are, in principle, often suitable for parallel execution, but usually display a high degree of irregularity in terms of both task and data structure. This makes it difficu lt to construct parallel applications that perform well in practice. Using our system, we are able to obtain both extremely good processor utilisation (97%) and very good absolute speedups (up to 7.7) on an eight-core machine. © 2009 ACM.

AB - With the emergence of commodity multicore architectures, exploiting tightly-coupled parallelism has become increasingly important. Functional programming languages, such as Haskell, are, in principle, well placed to take advantage of this trend, offering the ability to easily identify large amounts of fine-grained parallelism. Unfortunately, obtaining real performance benefits has often proved hard to realise in practice.This paper reports on a new approach using middleware that has been constructed using the Eden parallel dialect of Haskell. Our approach is "low pain" in the sense that the programmer constructs a parallel program by inserting a small number of higher-order algorithmic skeletons at key points in the program. It is "high gain" in the sense that we are able to get good parallel speedups. Our approach is unusual in that we do not attempt to use shared memory directly, but rather coordinate parallel computations using a message-passing implementation. This approach has a number of advantages Firstly, coordination, i.e. locking and communication,is both confined to limited shared memory areas, essentially the communication buffers, and is also isolated within well-understood libraries. Secondly, the coarse thread granularity that we obtain reduces coordination overheads, so locks are normally needed only on (relatively large) messages, and not on individual data items, as is often the case for simple shared-memory implementations. Finally, cache coherency requirements are reduced since individual tasks do not share caches, and can garbage collect independently. We report results for two representative computational algebra problems. Computational algebra is a challenging application area that has not been widely studied in the general parallelism community. Computational algebra applications have high computational demands, and are, in principle, often suitable for parallel execution, but usually display a high degree of irregularity in terms of both task and data structure. This makes it difficu lt to construct parallel applications that perform well in practice. Using our system, we are able to obtain both extremely good processor utilisation (97%) and very good absolute speedups (up to 7.7) on an eight-core machine. © 2009 ACM.

KW - Algorithmic Skeletons

KW - Computational Algebra

KW - Eden

KW - GAP

KW - Haskell

KW - Multicore Parallelism

UR - http://www.scopus.com/inward/record.url?scp=67650699988&partnerID=8YFLogxK

U2 - 10.1145/1481839.1481843

DO - 10.1145/1481839.1481843

M3 - Conference contribution

SN - 9781605584171

SP - 25

EP - 36

BT - Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09

ER -

Zain AA, Trinder P, Aswad M, Michaelson G, Hammond K, Berthold J. Low-pain,high-gain multicore programming in haskell coordinating irregular symbolic computations on multiCore architectures. In Proceedings of the 4th ACM SIGPLAN Workshop on Declarative Aspects of Multicore Programming, DAMP'09. 2009. p. 25-36 https://doi.org/10.1145/1481839.1481843