article

Free access

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

Author:

Sven-Bodo ScholzAuthors Info & Claims

ACM SIGAPL APL Quote Quad, Volume 29, Issue 3

Pages 32 - 38

https://doi.org/10.1145/327600.327613

Published: 27 July 1998 Publication History

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

[1]

J.C. _ADAMS, W.S. BRAINERD, J.T. ~aRTIN, ET AL:. FortrangO Handbook- Complete ANSI/ISO Reference. McGraw-H_ill, 1992. ISBN 0-07-000406-4.

Digital Library

[2]

W.B. ACKERMAN and J.B. DENNIS: VAL-A Value-O,iented Algo,ithrai~ Language: Prea'mina~y Refire~ee Manual. TR 218, bflT, Cambridge, MA, 1979.

Digital Library

[3]

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.

[4]

A.V. AltO, R. SETIII, and J.D. ULLMAN: Compikrs - Prindples, Techniquie, and Tools. Addison~Wesley, 1986. ISBN 0-201-10194-7.

Digital Library

[5]

D. BAILEY, E. BARSZCZ, J. BARTON, et al.: The NAS Parallel Benchmarks. RNR 94-007, NASA Ames Research Center, 1994.

[6]

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.

[7]

R. BERNECKY: An Overview of the APEX Compiler. Technical Repm-t 305/97, University of Toronto, 1997.

[8]

R. BERNECKY: APEX: The APE Parattel Executor. Master's thesis, University of Toronto, 1997.

[9]

D.F. BACON, S.L. GRAHAM, and O.J. SHARP: Compiter Transformations for High-Pe{formance Computing. ACM Computing Surveys, Vol. 26(4), 1994, pp. 345-- 420.

Digital Library

[10]

J. BROWN: Inside the APL2 Work~ace. SIGAPL Quote Quad, Vol. 1 S, 1985, pp. 277-282.

Digital Library

[11]

T. BUDD: An APL Compiler. Springer, 1988.

Digital Library

[12]

D.C. CANN: The Optimizing SISAL Compiler: Version /Z0. Lawrence Livermore National Laboratory, / i2qL, Livermore California, 1993. par~ of the SISAL distribution.

[13]

K.E. IVERSON: A Programming Language. Wiley, New York, 1962.

Digital Library

[14]

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.

[15]

L.M. RESTIFO MULLIN: A Mathematics of Arrays. PhD thesis, Syracuse Univetsity, 1988.

Digital Library

[16]

D.A. PADUA and M.J. WOLI;{-.;: Advanced Compikr Optimizations for Supercomputer,. Comm. ACM, Vol. 29(12), 1986, pp. 1184--1201.

Digital Library

[17]

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.

[18]

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.

[19]

S.-B. SCHOLZ: On Programming Sdenlific Applications m Sac- A Functional Language Extended by a Subgystem for High-Level Array Operalions. In Wemer Kluge (Ed.):, Implementation of Functional Languages, 8th International Workshop Bad Godesberg, Germany, September 1996, Selected Papers, LNCS, Vol. 1268. Springer, 1997, pp. 85--104.

Digital Library

[20]

S.-B. SCHOLZ: With&op-folding in SAC--Condensing ConsecuIive Arr~ Operation,. In C. Clack, T. Davie, and K. Hammond (Eds.): Proceedings of the 9th International Workshop on Implementation of Functional Languages. University of St. Andrews, 1997, lap. 225--242.

Digital Library

[21]

M.J. WOLFE: High-Poformance Compilers .for Parallel Compuling. Addison-Wesley, 1995. ISBN 0-8053-2730- 4.

Digital Library

[22]

H. ZIMA and B. CHAPMAN: Supercompilersfor Parallel and Veclor Computers. Addison-Wesley, 1991.

Cited By

Weuster AWeuster A(2004)Die Vorauswahl von BewerbernPersonalauswahl10.1007/978-3-663-07661-2_4(97-171)Online publication date: 2004
https://doi.org/10.1007/978-3-663-07661-2_4
Sathe SShrimankar DJena SKumar RTuruk ADash M(2011)Parallelization of DNA sequence alignment using OpenMPProceedings of the 2011 International Conference on Communication, Computing & Security10.1145/1947940.1947983(200-203)Online publication date: 12-Feb-2011
https://dl.acm.org/doi/10.1145/1947940.1947983
Breitbart J(2010)An approach for semiautomatic locality optimizations using OpenMPProceedings of the 10th international conference on Applied Parallel and Scientific Computing - Volume 210.1007/978-3-642-28145-7_29(291-301)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-28145-7_29
Show More Cited By

Index Terms

On defining application-specific high-level array operations by means of shape-invariant programming facilities
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation

Recommendations

On defining application-specific high-level array operations by means of shape-invariant programming facilities
APL '98: Proceedings of the APL98 conference on Array Processing Languages

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 ...
Declaratively defining domain-specific language debuggers
GCPE '11

Tool support is vital to the effectiveness of domain-specific languages. With language workbenches, domain-specific languages and their tool support can be generated from a combined, high-level specification. This paper shows how such a specification ...
Declaratively defining domain-specific language debuggers
GPCE '11: Proceedings of the 10th ACM international conference on Generative programming and component engineering

Tool support is vital to the effectiveness of domain-specific languages. With language workbenches, domain-specific languages and their tool support can be generated from a combined, high-level specification. This paper shows how such a specification ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGAPL APL Quote Quad

ACM SIGAPL APL Quote Quad Volume 29, Issue 3

March 1999

243 pages

ISSN:0163-6006

DOI:10.1145/327600

Editor:
Lynne C. Shaw

Issue’s Table of Contents

APL '98: Proceedings of the APL98 conference on Array Processing Languages
July 1998
247 pages
ISBN:158113181X
DOI:10.1145/327559
Chairmen:
Paolo di Chio,
Antonio Annibali,
Robert Bernecky
Snake Island Research Inc., Toronto, Ont., Canada
,
James Brown
Snake Island Research Inc., Toronto, Ont., Canada
,
Gitte Christensen,
Editors:
Sergio Picchi,
Marco Micocci

Copyright © 1998 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 July 1998

Published in SIGAPL Volume 29, Issue 3

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
321
Total Downloads

Downloads (Last 12 months)50
Downloads (Last 6 weeks)13

Reflects downloads up to 24 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Weuster AWeuster A(2004)Die Vorauswahl von BewerbernPersonalauswahl10.1007/978-3-663-07661-2_4(97-171)Online publication date: 2004
https://doi.org/10.1007/978-3-663-07661-2_4
Sathe SShrimankar DJena SKumar RTuruk ADash M(2011)Parallelization of DNA sequence alignment using OpenMPProceedings of the 2011 International Conference on Communication, Computing & Security10.1145/1947940.1947983(200-203)Online publication date: 12-Feb-2011
https://dl.acm.org/doi/10.1145/1947940.1947983
Breitbart J(2010)An approach for semiautomatic locality optimizations using OpenMPProceedings of the 10th international conference on Applied Parallel and Scientific Computing - Volume 210.1007/978-3-642-28145-7_29(291-301)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1007/978-3-642-28145-7_29
Gan GWang XManzano JGao G(2009)Tile ReductionProceedings of the 5th International Workshop on OpenMP: Evolving OpenMP in an Age of Extreme Parallelism10.1007/978-3-642-02303-3_12(140-153)Online publication date: 22-May-2009
https://dl.acm.org/doi/10.1007/978-3-642-02303-3_12
Bernecky RWooster P(2003)BitsliceProceedings of the 2003 conference on APL: stretching the mind10.1145/882067.882072(33-42)Online publication date: 11-Jun-2003
https://dl.acm.org/doi/10.1145/882067.882072
Bernecky R(2003)An SPMD/SIMD parallel tokenizer for APLProceedings of the 2003 conference on APL: stretching the mind10.1145/882067.882071(21-32)Online publication date: 11-Jun-2003
https://dl.acm.org/doi/10.1145/882067.882071
Scholz S(2003)Single Assignment C: efficient support for high-level array operations in a functional settingJournal of Functional Programming10.1017/S095679680200445813:6(1005-1059)Online publication date: 1-Nov-2003
https://dl.acm.org/doi/10.1017/S0956796802004458
Grelck C(2002)Implementing the NAS benchmark MG in SACProceedings 16th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2002.1016488(10 pp)Online publication date: 2002
https://doi.org/10.1109/IPDPS.2002.1016488
Deitz SChamberlain BSnyder L(2002)High-level Language Support for User-defined ReductionsThe Journal of Supercomputing10.1023/A:101578101844923:1(23-37)Online publication date: 1-Aug-2002
https://dl.acm.org/doi/10.1023/A%3A1015781018449
Grelck C(2002)Shared Memory Multiprocessor Support for SACImplementation of Functional Languages10.1007/3-540-48515-5_3(38-53)Online publication date: 28-Mar-2002
https://doi.org/10.1007/3-540-48515-5_3
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents