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.

TitelIFL 2006: Implementation and Application of Functional Languages
Band4449 LNCS
Herausgeber (Verlag)Springer Verlag
ISBN (Print)978-3-540-74129-9
ISBN (elektronisch)978-3-540-74130-5
PublikationsstatusVeröffentlicht - 01.12.2007
Veranstaltung18th International Symposium on Implementation and Application of Functional Languages - Budapest, Ungarn
Dauer: 04.09.200606.09.2006
Konferenznummer: 71089


Untersuchen Sie die Forschungsthemen von „On Optimising Shape-Generic Array Programs using Symbolic Structural Information“. Zusammen bilden sie einen einzigartigen Fingerprint.