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)


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
Publication statusPublished - 2013
Eventconference; MuCoCoS-6, 2013; 2013-09-07; 2013-09-07 -
Duration: 7 Sept 20137 Sept 2013


Conferenceconference; MuCoCoS-6, 2013; 2013-09-07; 2013-09-07
OtherMuCoCoS-6, 2013


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