Exploiting Implicit Parallelism in Dynamic Array Programming Languages
Pages 1 - 7
Abstract
We have built an interpreter for the array programming language J. The interpreter exploits implicit data parallelism in the language to achieve good parallel speedups on a variety of benchmark applications.
Many array programming languages operate on entire arrays without the need to write loops. Writing without loops simplifies the programs. Array programs without loops allow an interpreter to parallelize the execution of the code without complex analysis or input from the programmer.
The J programming language includes the usual idioms of operations on arrays of the same size and shape, where the operations can often be performed in parallel for each individual item of the operands. Another opportunity comes from Js reduction operations, where suitable operations can be performed in parallel for all the items of an operand. J has a notion of verb rank, which allows programmers to simplify programs by declaring how operations are applied to operands. The verb rank mechanism allows us to extract further parallelism.
Our implementation of an implicitly parallelizing interpreter for J is written entirely in Java. We have written the interpreter in a framework that produces native code for the interpreter, giving good scalar performance. The interpreter itself is responsible for exploiting the parallelism available in the applications. Our results show we attain good parallel speed-up on a variety of benchmarks, including near perfect linear speed-up on inherently parallel benchmarks.
We believe that the lessons learned from our approach to exploiting data parallelism in an interpreter can be applied to other interpreted languages as well.
References
[1]
R. Bernecky. An Introduction to Function Rank. In Proceedings of the International Conference on APL, APL '88, pages 39--43, New York, NY, USA, 1988. ACM.
[2]
R. Bernecky. The Role of APL and J in High-performance Computation. In Proceedings of the international conference on APL, APL '93, pages 17--32, New York, NY, USA, 1993. ACM. ISBN 0-89791-612-3. URL http://doi.acm.org/10.1145/166197.166201.
[3]
R. Bernecky. APEX -- The APL Parallel Executor. Master's thesis, University of Toronto, 1997.
[4]
A. Chauhan and K. Kennedy. Optimizing Strategies for Telescoping Languages: Procedure Strength Reduction and Procedure Vectorization. In In ACM Intl. Conf. on Supercomputing (ICS04), pages 92--101, 2001.
[5]
W.-M. Ching. Automatic Parallelization of APL-style Programs. In Conference Proceedings on APL 90: For the Future, APL '90, pages 76--80, New York, NY, USA, 1990. ACM. ISBN 0-89791-371-X.
[6]
C. Grelck and S.-B. Scholz. SAC: off-the-shelf support for data-parallelism on multicores. In Proceedings of the 2007 Workshop on Declarative Aspects of Multicore Programming, DAMP '07, New York, NY, USA, 2007. ACM.
[7]
M. D. Hill and M. R. Marty. Amdahl's Law in the Multicore Era. Computer, 41(7):33--38, July 2008. ISSN 0018-9162. URL http://dx.doi.org/10.1109/MC.2008.209.
[8]
R. K. W. Hui, K. E. Iverson, E. E. McDonnell, and A. T. Whitney. APL\? In Conference Proceedings on APL 90: For the Future, APL '90, pages 192--200, New York, NY, USA, 1990. ACM. ISBN 0-89791-371-X.
[9]
Hui, Roger. An Implementation of J. Iverson Software Inc., 1992. URL http://www.jsoftware.com/jwiki/Doc/An%20Implementation%20of%20J.
[10]
K. E. Iverson. The Dictionary of J. Journal of the British APL Association, 7(2):99--117, October 1990.
[11]
C. Jenkins. Toward a Parallel Implementation of J: Data Parallelism in Functional, Array-Oriented Languages with Function Rank. Computer Science Honors Theses, Paper 30, Trinity University, April 2013. http://digitalcommons.trinity.edu/compsci_honors/30.
[12]
Jsoftware Inc. Jsoftware High-performance development platform,. URL http://www.jsoftware.com/.
[13]
Jsoftware Inc. Appendix B. Special Code,. URL http://www.jsoftware.com/help/dictionary/special.htm.
[14]
G. Keller, M. M. Chakravarty, R. Leshchinskiy, S. Peyton Jones, and B. Lippmeier. Regular, Shape-polymorphic, Parallel Arrays in Haskell. In Proceedings of the 15th ACM SIGPLAN International Conference on Functional Programming, ICFP '10, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-794-3.
[15]
M. Neitzel. Untying the Gordian Knot: Agreement in J. In Proceedings of the International Conference on Applied Programming Languages, APL '95, pages 145--153, New York, NY, USA, 1995. ACM.
[16]
Oracle. SPARC T5-8 Server. URL http://www.oracle.com/us/products/servers-storage/servers/sparc/oracle-sparc/t5-8/overview/index.html.
[17]
A. J. Perlis and S. Rugaber. Programming with Idioms in APL. SIGAPL APL Quote Quad, 9(4):232--235, May 1979. ISSN 0163-6006.
[18]
J. Reinders. Intel Threading Building Blocks. O'Reilly & Associates, Inc., Sebastopol, CA, USA, first edition, 2007. ISBN 9780596514808.
[19]
N. Shavit and D. Touitou. Software Transactional Memory. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, PODC '95, pages 204--213, New York, NY, USA, 1995. ACM. ISBN 0-89791-710-3. URL http://doi.acm.org/10.1145/224964.224987.
[20]
L. Snyder. The Design and Development of ZPL. In Proceedings of the Third ACM SIGPLAN Conference on History of Programming Languages, HOPL III, New York, NY, USA, 2007. ACM. ISBN 978-1-59593-766-7.
[21]
The MathWorks Inc. Parallel Computing Toolbox - MATLAB. URL http://www.mathworks.com/products/parallel-computing/.
[22]
T. White. Hadoop: The Definitive Guide. O'Reilly Media, Inc., 1st edition, 2009. ISBN 0596521979, 9780596521974.
[23]
T. Würthinger, A. Wöß, L. Stadler, G. Duboscq, D. Simon, and C. Wimmer. Self-optimizing AST Interpreters. In Proceedings of the 8th symposium on Dynamic languages, DLS '12, pages 73--82, New York, NY, USA, 2012. ACM. ISBN 978-1-4503-1564-7.
Index Terms
- Exploiting Implicit Parallelism in Dynamic Array 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 ProgrammingThe 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 ...
Debugging native extensions of dynamic languages
ManLang '18: Proceedings of the 15th International Conference on Managed Languages & RuntimesMany dynamic programming languages such as Ruby and Python enable developers to use so called native extensions, code implemented in typically statically compiled languages like C and C++. However, debuggers for these dynamic languages usually lack ...
Truffle: a self-optimizing runtime system
SPLASH '12: Proceedings of the 3rd annual conference on Systems, programming, and applications: software for humanityWe present Truffle, a novel framework for implementing managed languages in Java™. The language implementer writes an AST interpreter, which is integrated in our framework that allows tree rewriting during AST interpretation. Tree rewrites incorporate ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2014
112 pages
ISBN:9781450329378
DOI:10.1145/2627373
Copyright © 2014 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 ACM 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
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 09 June 2014
Check for updates
Author Tags
Qualifiers
- Tutorial
- Research
- Refereed limited
Conference
PLDI '14
Sponsor:
PLDI '14: ACM SIGPLAN Conference on Programming Language Design and Implementation
June 9 - 11, 2014
Edinburgh, United Kingdom
Acceptance Rates
ARRAY'14 Paper Acceptance Rate 17 of 25 submissions, 68%;
Overall Acceptance Rate 17 of 25 submissions, 68%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 201Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 28 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in