Aaron W. Hsu
ABSTRACT
We present a language-driven strategy for the construction of compilers that are inherently data-parallel in their design and implementation. Using an encoding of the inter-node relationships between nodes in an AST called a Node Coordinate Matrix, we demonstrate how an operator called the Key operator, that applies a function over groupings of array cells grouped and ordered by their keys, when used in conjunction with a Node Coordinate Matrix, permits arbitrary computation over sub-trees of an AST using purely data-parallel array programming techniques. We discuss the use of these techniques when applied to an experimental commercial compiler called Co-dfns, which is a fully data-parallel compiler developed using the techniques discussed here.
- R. Bernecky. An introduction to function rank. ACM SIGAPL APL Quote Quad, 18(2):39–43, 1987. Google Scholar
Digital Library
- R. Bernecky. Apex: The apl parallel executor. 1997.Google Scholar
- R. Bernecky. Reducing computational complexity with array predicates. ACM SIGAPL APL Quote Quad, 29(3):39–43, 1999. Google ScholarDigital Library
- R. Bernecky. An spmd/simd parallel tokenizer for apl. In Proceedings of the 2003 conference on APL: stretching the mind, pages 21–32. ACM, 2003. Google ScholarDigital Library
- R. Bernecky and S.-B. Scholz. Abstract expressionism for parallel performance. In Proceedings of the 2Nd ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, ARRAY 2015, pages 54–59, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3584-3. doi: 10.1145/2774959.2774962. URL http://doi.acm.org/10.1145/2774959.2774962. Google ScholarDigital Library
- T. Budd. An APL compiler. Springer Science & Business Media, 2012.Google Scholar
- T. A. Budd. An apl compiler for a vector processor. ACM Transactions on Programming Languages and Systems (TOPLAS), 6(3):297–313, 1984. Google ScholarDigital Library
- J. Bunda and J. Gerth. Apl two by two-syntax analysis by pairwise reduction. In ACM SIGAPL APL Quote Quad, volume 14, pages 85–94. ACM, 1984. Google ScholarDigital Library
- W.-M. Ching. Automatic parallelization of apl-style programs. In ACM SIGAPL APL Quote Quad, volume 20, pages 76–80. ACM, 1990. Google ScholarDigital Library
- W. M. Ching and A. Katz. An experimental apl compiler for a distributed memory parallel machine. In Proceedings of the 1994 ACM/IEEE conference on Supercomputing, pages 59–68. IEEE Computer Society Press, 1994. Google ScholarDigital Library
- W.-M. Ching, P. Carini, and D.-C. Ju. A primitive-based strategy for producing efficient code for very high level programs. Computer languages, 19(1):41–50, 1993. Google ScholarDigital Library
- F. Henglein and R. Hinze. Sorting and Searching by Distribution: From Generic Discrimination to Generic Tries. In Programming Languages and Systems, pages 315–332. Springer, Dec. 2013. Google ScholarDigital Library
- A. W. Hsu. Co-dfns: Ancient language, modern compiler. In Proceedings of ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, page 62. ACM, 2014. Google ScholarDigital Library
- A. W. Hsu. Accelerating information experts through compiler design. In Proceedings of the 2nd ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming, pages 37–42. ACM, 2015. Google ScholarDigital Library
- R. Hui. Essays/key. URL http://www.jsoftware.com/ jwiki/Essays/Key.Google Scholar
- R. K. Hui. Rank and uniformity. In ACM SIGAPL APL Quote Quad, volume 25, pages 83–90. ACM, 1995. Google ScholarDigital Library
- K. E. Iverson. Rationalized APL. IP Sharp Associates, 1983.Google Scholar
- D.-C. Ju and W.-M. Ching. Exploitation of apl data parallelism on a shared-memory mimd machine. In ACM SIGPLAN Notices, volume 26, pages 61–72. ACM, 1991. Google ScholarDigital Library
- D.-c. Ju, W.-M. Ching, and C.-l. Wu. On performance and space usage improvements for parallelized compiled apl code. ACM SIGAPL APL Quote Quad, 21(4):234–243, 1991. Google ScholarDigital Library
- A. W. Keep and R. K. Dybvig. A nanopass framework for commercial compiler development. In ACM SIGPLAN Notices, volume 48, pages 343–350. ACM, 2013. Google ScholarDigital Library
- M. Mendez-Lojo, M. Burtscher, and K. Pingali. A gpu implementation of inclusion-based points-to analysis. ACM SIGPLAN Notices, 47(8): 107–116, 2012. Google ScholarDigital Library
- T. Prabhu, S. Ramalingam, M. Might, and M. Hall. Eigencfa: accelerating flow analysis with gpus. ACM SIGPLAN Notices, 46(1):511–522, 2011. Google ScholarDigital Library
- W. Schwarz. Acorn run-time system for the cm-2. In Arrays, Functional Languages, and Parallel Systems, pages 35–57. Springer, 1991.Google Scholar
Index Terms
- The key to a data parallel compiler
Recommendations
A Surprisingly Simple Lua Compiler
SBLP '21: Proceedings of the 25th Brazilian Symposium on Programming LanguagesDynamically-typed programming languages are often implemented using interpreters, which offer several advantages in terms of portability and flexibility of the implementation. However, as a language matures and its programs get bigger, programmers may ...
An open-source compiler and runtime implementation for Coarray Fortran
PGAS '10: Proceedings of the Fourth Conference on Partitioned Global Address Space Programming ModelCoarray Fortran (CAF) comprises a set of proposed language extensions to Fortran that are expected to be adopted as part of the Fortran 2008 standard. In contrast to prior open-source implementation efforts, our approach is to use a single, unified ...
Comments