On Optimising Shape-Generic Array Programs using Symbolic Structural Information

Kai Trojahner, Clemens Grelck, Sven Bodo Scholz


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.

Original languageEnglish
Title of host publicationIFL 2006: Implementation and Application of Functional Languages
Number of pages18
Volume4449 LNCS
PublisherSpringer Verlag
Publication date01.12.2007
ISBN (Print)978-3-540-74129-9
ISBN (Electronic)978-3-540-74130-5
Publication statusPublished - 01.12.2007
Event18th International Symposium on Implementation and Application of Functional Languages - Budapest, Hungary
Duration: 04.09.200606.09.2006
Conference number: 71089


Dive into the research topics of 'On Optimising Shape-Generic Array Programs using Symbolic Structural Information'. Together they form a unique fingerprint.

Cite this