Algorithmic species revisited : a program code classification based on array references

C. Nugteren, R. Corvino, H. Corporaal

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)
3 Downloads (Pure)

Abstract

The shift towards parallel processor architectures has made programming, performance prediction and code generation increasingly challenging. Abstract representations of program code (i.e. classifications) have been introduced to address this challenge. An example is `algorithmic species', a memory access pattern classification of loop nests. It provides an architecture-agnostic structured view of program code, allowing programmers and compilers to take for example parallelisation decisions or perform memory hierarchy optimisations. The existing algorithmic species theory is based on the polyhedral model and is limited to static affine loop nests. In this work, we first present a revised theory of algorithmic species that overcomes this limitation. The theory consists of a 5-tuple characterisation of individual array references and their corresponding merging operation. Second, we present an extension of this theory named SPECIES+, providing a more detailed 6-tuple characterisation. With this, we are able to retain relevant access pattern information not captured by the original algorithmic species, such as column-major versus row-major matrix accesses. We implement both new theories into a tool, enabling automatic classification of program code.
Original languageEnglish
Title of host publicationProceedings of MuCoCoS-6: Internation Workshop on Multi-/Many-core Computing Systems, 7 September 2013, Edinburgh, Scotland, UK
Pages1-8
DOIs
Publication statusPublished - 2013
Eventconference; MuCoCoS-6, 2013; 2013-09-07; 2013-09-07 -
Duration: 7 Sep 20137 Sep 2013

Conference

Conferenceconference; MuCoCoS-6, 2013; 2013-09-07; 2013-09-07
Period7/09/137/09/13
OtherMuCoCoS-6, 2013

Fingerprint

Dive into the research topics of 'Algorithmic species revisited : a program code classification based on array references'. Together they form a unique fingerprint.

Cite this