1Algorithmic Species: Classifying Program Code for Parallel Computing

Abstract—Performance growth of single-core processors has come to a halt in the past decade, but was re-enabled by the introduction of paral-lelism in processors. Emerging processor architectures such as multi-cores and many-cores exploit an increasing amount of parallelism, requiring programmers and compilers to deal with issues such as threading, concurrency and synchronization. We advocate that programmers and compilers can greatly benefit from a structured classification of program code. Such a classification can help programmers to find opportunities for parallelization or can serve as front-end to performance prediction models or parallelizing-compilers for example. In this paper, we introduce a new algorithm classification, ‘Algorithmic Species’, which encapsulates relevant information for parallelization in classes, and embeds memory transfer requirements to optimize commu-nication on heterogeneous platforms. We evaluate our work by manually classifying 134 algorithmic species in a benchmark set and two real-life applications. For the automatic identification of algorithmic species in program code we design ASET, which is able to automatically identify 99 % of the algorithmic species and to automatically extract memory transfer requirements. We conclude that algorithmic species are a solid base for current and future work on parallel programming, capable of solving many problems related to parallel computing