Abstract
Shape-generic programming and high run time performance do match if generic source code is systematically specialised into nongeneric executable code. However, as soon as we drop the assumption of whole-world knowledge or refrain from specialisation for other reasons, compiled generic code is substantially less efficient. Limited effectiveness of code optimisation techniques due to the inherent lack of knowledge about the structural properties of arrays can be identified as the single most important source of inefficiency.
However, in many cases partial structural information or structural relationships between arrays would actually suffice for optimisation. We propose symbolic array attributes as a uniform scheme to infer and to represent partial and relational structural information in shape-generic array code. By reusing the regular language to express structural properties in intermediate code, existing optimisations benefit from symbolic array attributes with little or no alteration. In fact, program optimisation and identification of structural properties cross-fertilise each other. We outline our approach in the context of the functional array language SaC and demonstrate its effectiveness by a small case study.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
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)
Grelck, C., Scholz, S.B.: SAC — A Functional Array Language for Efficient Multithreaded Execution. International Journal of Parallel Programming 34(4), 383–427 (2006)
Scholz, S.B.: With-loop-folding in SAC — Condensing Consecutive Array Operations. In: Clack, C., Hammond, K., Davie, T. (eds.) IFL 1997. LNCS, vol. 1467, pp. 72–92. Springer, Heidelberg (1998)
Grelck, C., Scholz, S.B., Trojahner, K.: With-Loop Scalarization: Merging Nested Array Operations. In: Trinder, P., Michaelson, G.J., Peña, R. (eds.) IFL 2003. LNCS, vol. 3145, pp. 118–134. Springer, Heidelberg (2004)
Grelck, C., Hinckfuß, K., Scholz, S.B.: With-Loop Fusion for Data Locality and Parallelism. In: Butterfield, A., Grelck, C., Huch, F. (eds.) IFL 2005. LNCS, vol. 4015, pp. 178–195. Springer, Heidelberg (2006)
Grelck, C., Trojahner, K.: Implicit Memory Management for SAC. In: Grelck, C., Huch, F. (eds.) Hardware Specification, Verification and Synthesis: Mathematical Aspects. LNCS, vol. 408, Springer, Heidelberg (1990)
Grelck, C., Scholz, S.B., Shafarenko, A.: A Binding-Scope Analysis for Generic Programs on Arrays. In: Butterfield, A. (ed.) IFL 2005. LNCS, vol. 4015, pp. 212–230. Springer, Heidelberg (2006)
Martin-Löf, P.: Intuitionistic Type Theory. Biblio-Napoli (1984)
Bernecky, R.: Shape Cliques. In: Horváth, Z., Zsók, V. (eds.) Proceedings of the 18th International Symposium on Implementation of Functional Languages, IFL 2006, Budapest, Hungary, September 4-6, 2006, Eötvös Loránd University pp. 1–12 (2006)
Jay, C., Steckler, P.: The Functional Imperative: Shape! In: Hankin, C. (ed.) ESOP 1998 and ETAPS 1998. LNCS, vol. 1381, pp. 139–153. Springer, Heidelberg (1998)
Kreye, D.: A Compilation Scheme for a Hierarchy of Array Types. In: Arts, T., Mohnen, M. (eds.) IFL 2001. LNCS, vol. 2312, pp. 24–26. Springer, Heidelberg (2002)
de Rose, L., Padua, D.: Techniques for the translation of matlab programs into fortran 90. ACM Transactions on Programming Languages and Systems 21(2), 286–323 (1999)
Joisha, P., Banerjee, P.: An algebraic array shape inference system for matlab. ACM Transactions on Programming Languages and Systems 28(5), 848–907 (2006)
McCosh, C.: Type-based specialization in a telescoping compiler for matlab. Master Thesis TR03-412, Rice University, Houston, Texas, USA (2003)
Bernecky, R.: Reducing Computational Complexity with Array Predicates. In: Picchi, S., Micocci, M. (eds.) Proceedings of the International Conference on Array Processing Languages (APL 1998), pp. 46–54. ACM Press, New York (1998)
Augustsson, L.: Cayenne – a language with dependent types. In: International Conference on Functional Programming. pp. 239–250 (1998)
McBride, C., McKinna, J.: The view from the left. Journal of Functional Programming 14(1), 69–111 (2004)
Altenkirch, T., McBride, C., McKinna, J.: Why dependent types matter. Manuscript, available online (2005)
Xi, H., Pfenning, F.: Dependent Types in Practical Programming. In: Aiken, A. (ed.) Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 1999), pp. 214–227. ACM Press, New York (1999)
Xi, H.: Applied Type System (extended abstract). In: Berardi, S., Coppo, M., Damiani, F. (eds.) TYPES 2003. LNCS, vol. 3085, pp. 394–408. Springer, Heidelberg (2004)
Zenger, C.: Indexed types. Theorectical Computer Science 187(1-2), 147–165 (1997)
Xi, H., Pfenning, F.: Eliminating array bound checking through dependent types. In: Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation, Montreal, pp. 249–257 (1998)
Xi, H.: Dead code elimination through dependent types. In: Gupta, G. (ed.) PADL 1999. LNCS, vol. 1551, pp. 228–242. Springer, Heidelberg (1999)
McKinna, J., Brady, E.: Phase distinctions in the compilation of epigram. Draft, available online (2005)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Trojahner, K., Grelck, C., Scholz, SB. (2007). On Optimising Shape-Generic Array Programs Using Symbolic Structural Information. 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_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-74130-5_1
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)