Abstract
Compiling indexing operations on n-dimensional arrays into efficiently executable code is a challenging task. This paper focuses on the reduction of offset computations as they typically occur when transforming index vectors into offsets for linearized representations of ndimensional arrays. We present a high-level optimization to that effect which is generally applicable, even in the presence of statically unknown rank (n). Our experiments show run-time improvements between a factor of 2 and 16 on a set of real-world benchmarks.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Iverson, K.E.: Notation as a tool of thought. Communications of the ACM 23(8) (1979)
International Standards Organization: International Standard for Programming Language APL. ISO N8485 edn (1984)
Scholz, S.B.: Single Assignment C — efficient support for high-level array operations in a functional setting. Journal of Functional Programming 13(6), 1005–1059 (2003)
Hui, R.K., Iverson, K.E.: J Dictionary (1998)
Cann, D.: Compilation Techniques for High Performance Applicative Computation. Technical Report CS-89-108, Lawrence Livermore National Laboratory, LLNL, Livermore California (1989)
Cann, D., Evripidou, P.: Advanced Array Optimizations for High Performance Functional Languages. IEEE Transactions on Parallel and Distributed Systems 6(3), 229–239 (1995)
Grelck, C., Trojahner, K.: Implicit Memory Management for SaC. In: Grelck, C., Huch, F., Michaelson, G.J., Trinder, P. (eds.) IFL 2004. LNCS, vol. 3474, pp. 335–348. Springer, Heidelberg (2005)
Pierce, B.: Types and Programming Languages. MIT Press, Cambridge (2002)
Grelck, C., Scholz, S.B., Shafarenko, A.: A Binding-Scope Analysis for Generic Programs on Arrays. In: Butterfield, A., Grelck, C., Huch, F. (eds.) IFL 2005. LNCS, vol. 4015, Springer, Heidelberg (2006)
Bernecky, R.: Shape Cliques. In: Horváth, Z., Zsók, V., (eds.) Proceedings of the 18th International Symposium on Implementation of Functional Languages (IFL’06), Eötvös Loránd University (2006)
Trojahner, K., Grelck, C., Scholz, S.B.: On Optimising Shape-Generic Array Language Programs using Symbolic Structural Information. In: Horváth, Z., Zsók, V. (eds.) Proceedings of the 18th International Symposium on Implementation of Functional Languages (IFL 2006). LNCS, vol. 4449, Springer, Heidelberg (2006)
Morel, E., Renvoise, C.: Global optimization by suppression of partial redundancies. Commun. ACM 22(2), 96–103 (1979)
Bernecky, R., Brenner, C., Jaffe, S.B., Moeckel, G.P.: ACORN: APL to C on real numbers. ACM SIGAPL Quote Quad 20(4), 40–49 (1990)
Weigang, J.: An Introduction to STSC’s apl compiler. APL89 Conference Proceedings, ACM SIGAPL Quota Quad 15, 231–238 (1989)
Ching, W.M.: An APL/370 compiler and some performance comparisons with APL interpreter and FORTRAN. ACM SIGAPL Quote Quad 16(4), 143–147 (1986)
Wiedmann, C.: Field results with the APL compiler. ACM SIGAPL Quote Quad 16(4), 187–196 (1986)
Budd, T.A.: An APL compiler for the UNIX timesharing system. ACM SIGAPL Quote Quad 13(3) (1983)
Bernecky, R.: APEX: The APL parallel executor. Master’s thesis, University of Toronto (1997)
Cann, D.: The Optimizing SISAL Compiler: Version 12.0. Lawrence Livermore National Laboratory, LLNL, Livermore California. Part of the SISAL distribution (1993)
Oldehoeft, R.: Implementing Arrays in SISAL 2.0. In: Proceedings of the Second SISAL Users’ Conference. pp. 209–222 (1992)
Böhm, A., Cann, D., Oldehoeft, R., Feo, J.: SISAL Reference Manual Language Version 2.0. CS 91-118, Colorado State University, Fort Collins, Colorado (1991)
Fitzgerald, S., Oldehoeft, R.: Update-in-place Analysis for True Multidimensional Arrays. In: Böhm, A., Feo, J., (eds.) High Performance Functional Computing. pp. 105–118 (1995)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bernecky, R., Herhut, S., Scholz, SB., Trojahner, K., Grelck, C., Shafarenko, A. (2007). Index Vector Elimination – Making Index Vectors Affordable. In: Horváth, Z., Zsók, V., Butterfield, A. (eds) Implementation and Application of Functional Languages. IFL 2006. Lecture Notes in Computer Science, vol 4449. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74130-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-540-74130-5_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74129-9
Online ISBN: 978-3-540-74130-5
eBook Packages: Computer ScienceComputer Science (R0)