Regions: an abstraction for expressing array computation

ABSTRACT

Most array languages, including Fortran 90, Matlab, and APL, provide support for referencing arrays by extending the traditional array subscripting construct found in scalar languages. We present an alternative to subscripting that exploits the concept of regions---an index set representation that can be named, manipulated with high-level operators, and syntactically separated from array references. This paper develops the concept of region-based programming and describes its benefits in the context of an idealized array language called RL. We show that regions simplify programming, reduce the likelihood of errors, and enable code reuse. Furthermore, we describe how regions accentuate the locality of array expressions and how this locality is important when targeting parallel computers. We also show how the concepts of region-based programming have been used in ZPL, a fully-implemented practical parallel programming language in use by scientists and engineers. In addition, we contrast region-based programming with the array reference constructs of other array languages.

REFERENCES

• 1: Jeanne C. Adams, Walter S. Brainerd, Jean T. Martin, Brian T. Smith, and Jerrold L. Wagener. Fortran 90 Handbook. McGraw-Hill, 1992.
• 2: Thomas Brtiunl. ParaUaxis-iII: A language for structured data-parallel programming. In Proceedings of the IEEE First International Conference on Algorithms and Architectures for Parallel Processing, pages 43-52. IEEE, April 1995.
• 3: B. Chamberlain , S. Choi , E. Lewis , C. Lin , L. Snyder , W. Weathersby, ZPL's WYSIWYG Performance Model, Proceedings of the High-Level Parallel Programming Models and Supportive Environments, p.50, March 30-April 03, 1998
• 4: Stephen J. Fink , Scott B. Baden , Scott R. Kohn, Efficient run-time support for irregular block-structured applications, Journal of Parallel and Distributed Computing, v.50 n.1-2, p.61-82, April 1998 [doi>10.1006/jpdc.1998.1437]
• 5: Raymond Greenlaw , Lawrence Snyder, Achieving speedups for APL on an SIMD distributed memory machine, International Journal of Parallel Programming, v.19 n.2, p.111-127, April 1991 [doi>10.1007/BF01407833]
• 6: Duane Hanselman and Bruce Littlefield. Mastering MATLAB. Prentice-Hall, 1996.
• 7: High Performance Fortran Forum. High Performance Fortran Langauge Specification, Version 2.0. January 1997.
• 8: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• 9: S. C. Johnson and C. Mohler. Compiling MATLAB. In Proceedings of the USENIX Symposium on Very High Level Languages (VHLL), pages 119-27, Santa Fe, New Mexico, October 1994. USENIX Association.
• 10: Calvin Lin , Lawrence Snyder, ZPL: An Array Sublanguage, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.96-114, August 12-14, 1993
• 11: Bruce J. MacLennan, Principles of programming languages: design, evaluation, and implementation (2nd ed.), Holt, Rinehart & Winston, Austin, TX, 1986
• 12: Luiz De Rose , Kyle Gallivan , Efstratios Gallopoulos , Bret A. Marsolf , David A. Padua, FALCON: A MATLAB Interactive Restructuring Compiler, Proceedings of the 8th International Workshop on Languages and Compilers for Parallel Computing, p.269-288, August 10-12, 1995
• 13: Sven-Bodo Scholz, On Programming Scientific Applications in SAC - A Functional Language Extended by a Subsystem for High-Level Array Operations, Selected Papers from the 8th International Workshop on Implementation of Functional Languages, p.85-104, September 16-18, 1996
• 14: Luigi Semenzato and Paul Hilfinger. Arrays in FID1L. In Robert Grossman, editor, Symbolic Computation: Applications to Scientific Computing, pages 155-169. SIAM, 1989.
• 15: Lawrence Snyder, A programmer's guide to ZPL, MIT Press, Cambridge, MA, 1999
• 16: C* Programming Guide, Version 6.0.2. Thinking Machines Corporation, Cambridge, Massachusetts, June 1991.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: APL

General Terms:
Languages