On defining application-specific high-level array operations by means of shape-invariant programming facilities

ABSTRACT

Most of the existing high-level array-processing languages support a fixed set of pre-defined array operations and a few higher-order functions for constructing new array operations from existing ones. In this paper, we discuss a more general approach made feasible by SAC (for Single Assignement C), a functional variant of C.SAC provides a meta-level language construct called WITH-loop which may be considered a sophisticated variant of the FORALL-loops in HPF or of array comprehensions in functional languages. It allows for the element-wise specification of high-level operations on arrays of any dimensionality: any set of high-level array operations can be specified by means of WITH-loops and be made available in a library. This not only improves the flexibility of specifications, but also simplifies the compilation process.By means of a few examples it is shown that the high-level operations that are typically available in array processing languages such as APL or FORTRAN90 can be easily specified as WITH-loops in SAC. Furthermore, we briefly outline the most important optimization techniques used in the current SAC compiler for achieving efficiently executable code.The paper finally presents a performance comparison between a high-level specification for the multigrid relaxation kernel of the NAS benchmarks in SAC on the one hand and low-level specifications in SISAL and in FORTRAN77 on the other hand. It shows that the SAC implementation, despite its higher level of abstraction, is competitive with the other two both in terms of program runtimes and memory consumption.

REFERENCES

• ABM+92: Jeanne C. Adams , Walter S. Brainerd , Jeanne T. Martin , Brian T. Smith , Jerrold L. Wagener, Fortran 90 handbook: complete ANSI/ISO reference, Intertext Publications, Inc.,/McGraw-Hill, Inc., New York, NY, 1993
• AD79: W. B. Acherman , J. B. Dennis , William B Ackerman, VAL- ORIENTED ALGORITHMIC LANGUAGE, PRELIMINARY REFERENCE MANUAL, Massachusetts Institute of Technology, Cambridge, MA, 1979
• AGP78: ARVIND, K.P. GOSTELOW, and W. PLOUFFE: The ID-Report: An asynchronous Programming Language aad Computing Machine. Technical Report 114, University of California at Irvine, 1978.
• ASU86: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• BBB+94: D. BAILEY, E. BARSZCZ, J. BARTON, et al.: The NAS Parallel Benchmarks. RNR 94-007, NASA Ames Research Center, 1994.
• BCOF91: A.P.W. BOHM, D.C. CANN, R.R_ OLDEHOEFT, and J.T. FEO: SISAL Refirenee Manual Language Version 2.0. CS 91-118, Colorado State University, Fort Collins, Colorado, 1991.
• Ber97a: R. BERNECKY: An Overview of the APEX Compiler. Technical Repm-t 305/97, University of Toronto, 1997.
• Ber97b: R. BERNECKY: APEX: The APE Parattel Executor. Master's thesis, University of Toronto, 1997.
• BGS94: David F. Bacon , Susan L. Graham , Oliver J. Sharp, Compiler transformations for high-performance computing, ACM Computing Surveys (CSUR), v.26 n.4, p.345-420, Dec. 1994 [doi>10.1145/197405.197406]
• Bro85: James A. Brown, Inside the APL2 workspace, ACM SIGAPL APL Quote Quad, v.15 n.4, p.277-282, May 12, 1985
• Bud88: Timothy Budd, An APL compiler, Springer-Verlag New York, Inc., New York, NY, 1988
• Can93: D.C. CANN: The Optimizing SISAL Compiler: Version /Z0. Lawrence Livermore National Laboratory, / i2qL, Livermore California, 1993. par~ of the SISAL distribution.
• Ive62: Kenneth E. Iverson, A Programming Language., John Wiley & Sons, 1962
• MSA+85: J.R. MCGRAw, S.K. SKEDZ1ELEWSKI, S.J. 2kLL.a2q, R.R. OLDEHOEFT, et al.: Sisal: Streams and Ileratiou in a Single Assignment Language: Reference Manual Version 1.2. M 146, Lawrence Livermore National Laboratory, LLNL, Livermore California, 1985.
• Mul88: Lenore Marie Restifo Mullin, A mathematics of arrays, 1988
• PW86: David A. Padua , Michael J. Wolfe, Advanced compiler optimizations for supercomputers, Communications of the ACM, v.29 n.12, p.1184-1201, Dec. 1986 [doi>10.1145/7902.7904]
• Sch96: S.-B. SCHOLZ" Single Assignment C-- E~twu~{ und Impkmentierung einer funktionalen C-Variaute mit ~e~jeller Unterstutzu~g shape-invatiaater Array-Operationen. PhD thesis, Institut fur Infozmatik und Praktische Mathematik, Universitat KAel, 1996.
• Sch97a: S.-B. SCHOLZ: An Overview of SAC-- a Funclional Language for NumeKca/Applications. In R. Bezghammer and F. Simon (Eds.): Programming Languages and Fm~damentals of Programming, Technical Report 97t7. Institut flax Irtformatik urLd Prakfische Mathemafik, Universitat Kid, 1997.
• Sch97b: 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
• Sch97c: Sven-Bodo Scholz, WITH-Loop-Folding in SAC - Condensing Consecutive Array Operations, Selected Papers from the 9th International Workshop on Implementation of Functional Languages, p.72-91, September 10-12, 1997
• Wol95: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• ZC91: Hans Zima , Barbara Chapman, Supercompilers for parallel and vector computers, ACM Press, New York, NY, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Design, Languages, Theory

Keywords:
compilation, high-level array operations, meta-level programming, performance comparison, shape-invariant programming