Lazy data-oriented evaluation strategies

Prabhat Totoo; Hans Wolfgang Loidl

doi:10.1145/2636228.2636234

Lazy data-oriented evaluation strategies

Prabhat Totoo^*, Hans Wolfgang Loidl

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

This paper presents a number of flexible parallelism control mechanisms in the form of evaluation strategies for tree-like data structures implemented in Glasgow parallel Haskell. We achieve additional flexibility by using laziness and circular programs in the coordination code. Heuristics-based parameter selection is employed to auto-tune these strategies for improved performance on a sharedmemory machine without programmer-specified parameters. In particular for unbalanced trees we demonstrate improved performance on a state-of-the-art multi-core server: giving a speedup of up to 37.5 on 48 cores for a constructed test program, and up to 15 for two other non-trivial applications using these strategies, a Barnes-Hut implementation of the n-body problem and a sparse matrix multiplication implementation. Copyright is held by the owner/author(s).

Original language	English
Title of host publication	Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP
Publisher	Association for Computing Machinery
Pages	63-74
Number of pages	12
ISBN (Print)	9781450330404
DOIs	https://doi.org/10.1145/2636228.2636234
Publication status	Published - 1 Jan 2014
Event	3rd ACM SIGPLAN Workshop on Functional High-Performance Computing - Gothenburg, United Kingdom Duration: 4 Sept 2014 → 4 Sept 2014

Conference

Conference	3rd ACM SIGPLAN Workshop on Functional High-Performance Computing
Abbreviated title	FHPC 2014
Country/Territory	United Kingdom
City	Gothenburg
Period	4/09/14 → 4/09/14

Keywords

Dynamic parallelism control
Parallel Haskell
Quadtrees

ASJC Scopus subject areas

Software

Access to Document

10.1145/2636228.2636234

Cite this

@inproceedings{7a772ef5f27c4ecc869dc703fcfa6927,

title = "Lazy data-oriented evaluation strategies",

abstract = "This paper presents a number of flexible parallelism control mechanisms in the form of evaluation strategies for tree-like data structures implemented in Glasgow parallel Haskell. We achieve additional flexibility by using laziness and circular programs in the coordination code. Heuristics-based parameter selection is employed to auto-tune these strategies for improved performance on a sharedmemory machine without programmer-specified parameters. In particular for unbalanced trees we demonstrate improved performance on a state-of-the-art multi-core server: giving a speedup of up to 37.5 on 48 cores for a constructed test program, and up to 15 for two other non-trivial applications using these strategies, a Barnes-Hut implementation of the n-body problem and a sparse matrix multiplication implementation. Copyright is held by the owner/author(s).",

keywords = "Dynamic parallelism control, Parallel Haskell, Quadtrees",

author = "Prabhat Totoo and Loidl, {Hans Wolfgang}",

year = "2014",

month = jan,

day = "1",

doi = "10.1145/2636228.2636234",

language = "English",

isbn = "9781450330404",

pages = "63--74",

booktitle = "Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP",

publisher = "Association for Computing Machinery",

address = "United States",

note = "3rd ACM SIGPLAN Workshop on Functional High-Performance Computing, FHPC 2014 ; Conference date: 04-09-2014 Through 04-09-2014",

}

TY - GEN

T1 - Lazy data-oriented evaluation strategies

AU - Totoo, Prabhat

AU - Loidl, Hans Wolfgang

PY - 2014/1/1

Y1 - 2014/1/1

N2 - This paper presents a number of flexible parallelism control mechanisms in the form of evaluation strategies for tree-like data structures implemented in Glasgow parallel Haskell. We achieve additional flexibility by using laziness and circular programs in the coordination code. Heuristics-based parameter selection is employed to auto-tune these strategies for improved performance on a sharedmemory machine without programmer-specified parameters. In particular for unbalanced trees we demonstrate improved performance on a state-of-the-art multi-core server: giving a speedup of up to 37.5 on 48 cores for a constructed test program, and up to 15 for two other non-trivial applications using these strategies, a Barnes-Hut implementation of the n-body problem and a sparse matrix multiplication implementation. Copyright is held by the owner/author(s).

AB - This paper presents a number of flexible parallelism control mechanisms in the form of evaluation strategies for tree-like data structures implemented in Glasgow parallel Haskell. We achieve additional flexibility by using laziness and circular programs in the coordination code. Heuristics-based parameter selection is employed to auto-tune these strategies for improved performance on a sharedmemory machine without programmer-specified parameters. In particular for unbalanced trees we demonstrate improved performance on a state-of-the-art multi-core server: giving a speedup of up to 37.5 on 48 cores for a constructed test program, and up to 15 for two other non-trivial applications using these strategies, a Barnes-Hut implementation of the n-body problem and a sparse matrix multiplication implementation. Copyright is held by the owner/author(s).

KW - Dynamic parallelism control

KW - Parallel Haskell

KW - Quadtrees

U2 - 10.1145/2636228.2636234

DO - 10.1145/2636228.2636234

M3 - Conference contribution

AN - SCOPUS:84907841544

SN - 9781450330404

SP - 63

EP - 74

BT - Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP

PB - Association for Computing Machinery

T2 - 3rd ACM SIGPLAN Workshop on Functional High-Performance Computing

Y2 - 4 September 2014 through 4 September 2014

ER -

Lazy data-oriented evaluation strategies

Abstract

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this