research-article

Functional array streams

Authors:

Frederik M. Madsen,

Robert Clifton-Everest,

Manuel M. T. Chakravarty,

Gabriele KellerAuthors Info & Claims

FHPC 2015: Proceedings of the 4th ACM SIGPLAN Workshop on Functional High-Performance Computing

Pages 23 - 34

https://doi.org/10.1145/2808091.2808094

Published: 30 August 2015 Publication History

Abstract

Regular array languages for high performance computing based on aggregate operations provide a convenient parallel programming model, which enables the generation of efficient code for SIMD architectures, such as GPUs. However, the data sets that can be processed with current implementations are severely constrained by the limited amount of main memory available in these architectures. In this paper, we propose an extension of the embedded array language Accelerate with a notion of sequences, resulting in a two level hierarchy which allows the programmer to specify a partitioning strategy which facilitates automatic resource allocation. Depending on the available memory, the runtime system processes the overall data set in streams of chunks appropriate to the hardware parameters. In this paper, we present the language design for the sequence operations, as well as the compilation and runtime support, and demonstrate with a set of benchmarks the feasibility of this approach.

References

[1]

L. Bergstrom and J. Reppy. Nested data-parallelism on the GPU. In ICFP: International Conference on Functional Programming. ACM, 2012.

Digital Library

[2]

G. E. Blelloch. Prefix sums and their applications. Technical Report CMU-CS-90-190, Nov. 1990.

[3]

G. E. Blelloch. NESL: A nested data-parallel language. Technical Report CMU-CS-95-170, Carnegie Mellon University, 1995.

[4]

G. E. Blelloch and G. W. Sabot. Compiling collection-oriented languages onto massively parallel computers. In Frontiers of Massively Parallel Computation, 1988. Proceedings., 2nd Symposium on the Frontiers of, pages 575–585. IEEE, 1988.

[5]

I. Buck. Brook language specification. Outubro, 2003. URL http: //merrimac.stanford.edu/brook.

[6]

I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian, M. Houston, and P. Hanrahan. Brook for gpus: Stream computing on graphics hardware. In ACM SIGGRAPH 2004 Papers, SIGGRAPH ’04, pages 777–786, New York, NY, USA, 2004. ACM. URL http://doi. acm.org/10.1145/1186562.1015800.

Digital Library

[7]

M. M. T. Chakravarty, G. Keller, S. Lee, T. L. McDonell, and V. Grover. Accelerating Haskell array codes with multicore GPUs. In DAMP: Declarative Aspects of Multicore Programming. ACM, 2011.

Digital Library

[8]

S. Chatterjee, G. E. Blelloch, and M. Zagha. Scan primitives for vector computers. In Proc. of Supercomputing. IEEE Computer Society Press, 1990.

Digital Library

[9]

K. Claessen, M. Sheeran, and J. Svensson. Obsidian: GPU programming in Haskell. In IFL: Implementation and Application of Functional Languages, 2008.

[10]

J. P. Daniel Palmer and S. Westfold. Work-efficient nested dataparallelism. In Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Processing (Frontiers 95). IEEE, 1995.

Digital Library

[11]

C. Elliott. Programming graphics processors functionally. In Haskell Workshop. ACM Press, 2004.

Digital Library

[12]

J. GóMez-Luna, J. M. GonzáLez-Linares, J. I. Benavides, and N. Guil. Performance models for asynchronous data transfers on consumer graphics processing units. J. Parallel Distrib. Comput.

[13]

A. H. Hormati, M. Samadi, M. Woh, T. Mudge, and S. Mahlke. Sponge: Portable stream programming on graphics engines. SIGARCH Comput. Archit. News, 39(1):381–392, Mar. 2011. ISSN 0163-5964. URL http://doi.acm.org/10.1145/1961295.

Digital Library

[14]

1950409.

[15]

G. Keller, M. M. T. Chakravarty, R. Leshchinskiy, S. L. Peyton Jones, and B. Lippmeier. Regular, Shape-polymorphic, Parallel Arrays in Haskell. In ICFP: International Conference on Functional Programming. ACM, 2010.

Digital Library

[16]

G. Keller, M. M. Chakravarty, R. Leshchinskiy, B. Lippmeier, and S. Peyton Jones. Vectorisation avoidance. In ACM SIGPLAN Notices, volume 47, pages 37–48. ACM, 2012.

Digital Library

[17]

B. Larsen. Simple optimizations for an applicative array language for graphics processors. In DAMP: Declarative Aspects of Multicore Programming. ACM, 2011.

Digital Library

[18]

E. A. Lee and D. G. Messerschmi’tt. Static scheduling of synchronous data flow programs for digital signal processing. IEEE Transactions on Computers, 2(36), 1987.

Digital Library

[19]

R. Leshchinskiy, M. M. Chakravarty, and G. Keller. Higher order flattening. In Computational Science–ICCS 2006, pages 920–928. Springer, 2006.

Digital Library

[20]

B. Lippmeier, M. Chakravarty, G. Keller, and S. Peyton Jones. Guiding parallel array fusion with indexed types. In Haskell Symposium. ACM, 2012.

Digital Library

[21]

F. M. Madsen and A. Filinski. Towards a streaming model for nested data parallelism. In Proceedings of the 2Nd ACM SIGPLAN Workshop on Functional High-performance Computing, FHPC ’13, pages 13– 24, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2381-9. URL http://doi.acm.org/10.1145/2502323.2502330.

Digital Library

[22]

G. Mainland and G. Morrisett. Nikola: Embedding compiled GPU functions in Haskell. In Haskell Symposium. ACM, 2010.

Digital Library

[23]

T. L. McDonell, M. M. T. Chakravarty, G. Keller, and B. Lippmeier. Optimising Purely Functional GPU Programs. In ICFP: International Conference on Functional Programming, Sept. 2013.

Digital Library

[24]

NVIDIA. CUDA C Programming Guide, 2012.

[25]

L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. 1999.

[26]

R. Rivest. The md5 message-digest algorithm. 1992.

[27]

T. Rompf, A. K. Sujeeth, N. Amin, K. J. Brown, V. Jovanovic, H. Lee, M. Odersky, and K. Olukotun. Optimizing data structures in high-level programs: New directions for extensible compilers based on staging. In POPL’13. ACM, 2013.

Digital Library

[28]

W. Thies, M. Karczmarek, and S. Amarasinghe. StreamIt: A language for streaming applications. In Compiler Construction. Springer, 2002.

Digital Library

Cited By

Gurdeep Singh RScholliers C(2023)Gaiwan: A size-polymorphic typesystem for GPU programsScience of Computer Programming10.1016/j.scico.2023.102989230(102989)Online publication date: Aug-2023
https://doi.org/10.1016/j.scico.2023.102989
van Beurden PScholz S(2022)On Generating Out-Of-Core GPU Code for Multi-Dimensional Array OperationsProceedings of the 34th Symposium on Implementation and Application of Functional Languages10.1145/3587216.3587223(1-13)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3587216.3587223
(2018)Array streaming for array programmingInternational Journal of Computational Science and Engineering10.5555/3292750.329275217:3(263-282)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3292750.3292752
Show More Cited By

Index Terms

Functional array streams
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types

Recommendations

Accelerating Haskell array codes with multicore GPUs
DAMP '11: Proceedings of the sixth workshop on Declarative aspects of multicore programming

Current GPUs are massively parallel multicore processors optimised for workloads with a large degree of SIMD parallelism. Good performance requires highly idiomatic programs, whose development is work intensive and requires expert knowledge.

To raise ...
Type-safe runtime code generation: accelerate to LLVM
Haskell '15

Embedded languages are often compiled at application runtime; thus, embedded compile-time errors become application runtime errors. We argue that advanced type system features, such as GADTs and type families, play a crucial role in minimising such ...
Type-safe runtime code generation: accelerate to LLVM
Haskell '15: Proceedings of the 2015 ACM SIGPLAN Symposium on Haskell

Embedded languages are often compiled at application runtime; thus, embedded compile-time errors become application runtime errors. We argue that advanced type system features, such as GADTs and type families, play a crucial role in minimising such ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

FHPC 2015: Proceedings of the 4th ACM SIGPLAN Workshop on Functional High-Performance Computing

August 2015

54 pages

ISBN:9781450338073

DOI:10.1145/2808091

Program Chairs:
Tiark Rompf,
Geoffrey Mainland

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

ICFP'15

Sponsor:

SIGPLAN

ICFP'15: 20th ACM SIGPLAN International Conference on Functional Programming

September 3, 2015

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 18 of 25 submissions, 72%

Upcoming Conference

ICFP '25

Sponsor:
sigplan

ACM SIGPLAN International Conference on Functional Programming

October 12 - 18, 2025

Singapore , Singapore

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
94
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gurdeep Singh RScholliers C(2023)Gaiwan: A size-polymorphic typesystem for GPU programsScience of Computer Programming10.1016/j.scico.2023.102989230(102989)Online publication date: Aug-2023
https://doi.org/10.1016/j.scico.2023.102989
van Beurden PScholz S(2022)On Generating Out-Of-Core GPU Code for Multi-Dimensional Array OperationsProceedings of the 34th Symposium on Implementation and Application of Functional Languages10.1145/3587216.3587223(1-13)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3587216.3587223
(2018)Array streaming for array programmingInternational Journal of Computational Science and Engineering10.5555/3292750.329275217:3(263-282)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.5555/3292750.3292752
Clifton-Everest RMcDonell TChakravarty MKeller G(2017)Streaming irregular arraysACM SIGPLAN Notices10.1145/3156695.312297152:10(174-185)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3156695.3122971
Clifton-Everest RMcDonell TChakravarty MKeller GDiatchki I(2017)Streaming irregular arraysProceedings of the 10th ACM SIGPLAN International Symposium on Haskell10.1145/3122955.3122971(174-185)Online publication date: 7-Sep-2017
https://dl.acm.org/doi/10.1145/3122955.3122971
Madsen FFilinski ADuke DKameyama Y(2016)Streaming nested data parallelism on multicoresProceedings of the 5th International Workshop on Functional High-Performance Computing10.1145/2975991.2975998(44-51)Online publication date: 8-Sep-2016
https://dl.acm.org/doi/10.1145/2975991.2975998
Kristensen MAvery JBlum TLund SVinter B(2016)Battling Memory Requirements of Array Programming Through StreamingHigh Performance Computing10.1007/978-3-319-46079-6_32(451-469)Online publication date: 6-Oct-2016
https://doi.org/10.1007/978-3-319-46079-6_32

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents