A modular and parameterisable classification of algorithms

Multi-core and many-core were already major trends for the past six years, and are expected to continue for the next decades. With this trend of parallel computing, it becomes increasingly difficult to decide on which architecture to run a certain application or algorithm. Additionally, it brings forth the problem of parallel programming, leading to the so-called software engineering crisis. In this work we present a new algorithm classification. This algorithm classification is designed for programmers and tools to capture and reason about parallel algorithms. The classification is initially intended to be used to address two challenges: 1) the challenge of parallel programming, and 2), performance prediction for parallel and heterogeneous systems. In order to address these two challenges, we introduce a new algorithm classification in this work. The classification uses a limited vocabulary and a well-defined grammar, creating a modular classification. Additionally, the classification is parameterisable. Both the modularity and the parameterisability of the algorithm classification make it possible to enable a very fine-grained and widely applicable classification. We furthermore illustrate the new algorithm classification by classifying a number of example algorithms from the field of image processing. We also show a number of code snippets to give an intuitive feel for the classification