research-article

Open access

Parallel scan as a multidimensional array problem

Authors:

ARRAY 2022: Proceedings of the 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming

Pages 1 - 11

https://doi.org/10.1145/3520306.3534500

Published: 13 June 2022 Publication History

PDF eReader

Abstract

For many algorithms, it is challenging to identify a suitable parallel version, as the design space is typically very large. In this paper we demonstrate how rank-polymorphic array languages can be used as a tool to explore such design spaces through concise high-level specifications. If input data can be organised into a multi-dimensional array, and the algorithm can be stated as a recursive traversal over sub-arrays, array languages offer a lot of expressive power. The reason for this is that array shapes can be used to guide recursive traversals. Conciseness of specifications comes from array reshapes that move the desired elements into canonical hyperplanes.

As a case study, we discuss several variants of implementing prefix sums (also known as scans) in SaC. We demonstrate how small code adjustments suffice to change the concurrency pattern exposed to the compiler. It turns out that variability that is typically achieved by generic inductive data types such as binary trees is a special case of what is offered by the array paradigm.

References

[1]

Guy E. Blelloch. 1990. Prefix Sums and Their Applications. Carnegie Mellon University, USA.

Google Scholar

[2]

Guy E. Blelloch. 1992. NESL: A Nested Data-Parallel Language. Carnegie Mellon University, USA.

Digital Library

Google Scholar

[3]

Conal Elliott. 2017. Generic Functional Parallel Algorithms: Scan and FFT. Proc. ACM Program. Lang., 1, ICFP (2017), Article 7, aug, 25 pages. https://doi.org/10.1145/3110251

Digital Library

Google Scholar

[4]

Message Passing Interface Forum. 1994. MPI: A Message-Passing Interface Standard. University of Tennessee, USA.

Google Scholar

[5]

Clemens Grelck. 2005. Shared Memory Multiprocessor Support for Functional Array Processing in Sac. Journal of Functional Programming, 15, 3 (2005), 353–401. https://doi.org/10.1017/S0956796805005538

Digital Library

Google Scholar

[6]

Clemens Grelck, Sven-Bodo Scholz, and Kai Trojahner. 2005. With-Loop Scalarization – Merging Nested Array Operations. In Implementation of Functional Languages, Phil Trinder, Greg J. Michaelson, and Ricardo Peña (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 118–134. isbn:978-3-540-27861-0 https://doi.org/10.1007/978-3-540-27861-0_8

Digital Library

Google Scholar

[7]

Troels Henriksen. 2017. Design and Implementation of the Futhark Programming Language. Ph. D. Dissertation. University of Copenhagen. Universitetsparken 5, 2100 København.

Google Scholar

[8]

Kenneth E. Iverson. 1962. A Programming Language. John Wiley & Sons, Inc., New York, NY, USA. isbn:0471430145

Digital Library

Google Scholar

[9]

Sven-Bodo Scholz. 1998. With-loop-folding in Sac — Condensing Consecutive Array Operations. In Implementation of Functional Languages, 9th International Workshop (IFL’97), St. Andrews, UK, Selected Papers, Chris Clack, Tony Davie, and Kevin Hammond (Eds.) (Lecture Notes in Computer Science, Vol. 1467). Springer, 72–92. isbn:978-3-540-64849-9 https://doi.org/10.1007/BFb0055425

Crossref

Google Scholar

[10]

Sven-Bodo Scholz. 2003. Single Assignment C: Efficient Support for High-level Array Operations in a Functional Setting. J. Funct. Program., 13, 6 (2003), Nov., 1005–1059. issn:0956-7968 https://doi.org/10.1017/S0956796802004458

Digital Library

Google Scholar

[11]

Sven-Bodo Scholz and Artjoms Šinkarovs. 2019. Tensor Comprehensions in SaC. In Proceedings of the 31st Symposium on Implementation and Application of Functional Languages (IFL ’19). Association for Computing Machinery, New York, NY, USA. Article 15, 13 pages. isbn:9781450375627 https://doi.org/10.1145/3412932.3412947

Digital Library

Google Scholar

[12]

Justin Slepak, Olin Shivers, and Panagiotis Manolios. 2014. An Array-Oriented Language with Static Rank Polymorphism. In Programming Languages and Systems, Zhong Shao (Ed.). Springer, Berlin, Heidelberg. 27–46. isbn:978-3-642-54833-8 https://doi.org/10.1007/978-3-642-54833-8_3

Digital Library

Google Scholar

[13]

Roger Stokes. 15 June 2015. Learning J. An Introduction to the J Programming Language. http://www.jsoftware.com/help/learning/contents.htm [Accessed 2020/02]

Google Scholar

Cited By

View all

van Balen DKeller Gde Wolff IMcDonell TRainey MScholz S(2024)Fusing Gathers with Integer Linear ProgrammingProceedings of the 1st ACM SIGPLAN International Workshop on Functional Programming for Productivity and Performance10.1145/3677997.3678227(10-23)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1145/3677997.3678227
Šinkarovs AKoopman TScholz SKeller GWestrick S(2023)Rank-Polymorphism for Shape-Guided BlockingProceedings of the 11th ACM SIGPLAN International Workshop on Functional High-Performance and Numerical Computing10.1145/3609024.3609410(1-14)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609024.3609410

Index Terms

Parallel scan as a multidimensional array problem
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent algorithms
    2. Concurrent programming languages

Recommendations

Combinatory logic and combinators in array languages
ARRAY 2022: Proceedings of the 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming

The array language paradigm began in the 1960s when Ken Iverson created APL. After spending over 30 years working on APL, he moved on to his second array language J, a successor to APL which embeds a significant subset of combinatory logic in it. This ...
A Rosetta Stone for array languages
ARRAY 2018: Proceedings of the 5th ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming

This paper aims to foster cross-fertilisation between programming language and compiler research performed on different array programming language infrastructures. We study how to enable better comparability of concepts and techniques by looking into ...
The design and implementation of a parallel array operator for the arbitrary remapping of data
Proceedings of the ACM SIGPLAN symposium on principles and practice of parallel programming (PPoPP 2003) and workshop on partial evaluation and semantics-based program manipulation (PEPM 2003)

Gather and scatter are data redistribution functions of long-standing importance to high performance computing. In this paper, we present a highly-general array operator with powerful gather and scatter capabilities unmatched by other array languages. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ARRAY 2022: Proceedings of the 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming

June 2022

57 pages

ISBN:9781450392693

DOI:10.1145/3520306

General Chair:
Troels Henriksen
University of Copenhagen, Denmark
,
Program Chair:
Tze Meng Low
Carnegie Mellon University, USA

This work is licensed under a Creative Commons Attribution 4.0 International License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 June 2022

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ARRAY '22

Sponsor:

SIGPLAN

ARRAY '22: 8th ACM SIGPLAN International Workshop on Libraries, Languages and Compilers for Array Programming

June 13, 2022

CA, San Diego, USA

Acceptance Rates

Overall Acceptance Rate 17 of 25 submissions, 68%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
475
Total Downloads

Downloads (Last 12 months)186
Downloads (Last 6 weeks)27

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

van Balen DKeller Gde Wolff IMcDonell TRainey MScholz S(2024)Fusing Gathers with Integer Linear ProgrammingProceedings of the 1st ACM SIGPLAN International Workshop on Functional Programming for Productivity and Performance10.1145/3677997.3678227(10-23)Online publication date: 28-Aug-2024
https://dl.acm.org/doi/10.1145/3677997.3678227
Šinkarovs AKoopman TScholz SKeller GWestrick S(2023)Rank-Polymorphism for Shape-Guided BlockingProceedings of the 11th ACM SIGPLAN International Workshop on Functional High-Performance and Numerical Computing10.1145/3609024.3609410(1-14)Online publication date: 30-Aug-2023
https://dl.acm.org/doi/10.1145/3609024.3609410

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Combinatory logic and combinators in array languages

A Rosetta Stone for array languages

The design and implementation of a parallel array operator for the arbitrary remapping of data