Modeling Algorithmic Skeletons for Automatic Parallelization Using Template Metaprogramming

This article presents a framework for algorithmic skeletons that aims at representing a whole algorithm, both its sequential and possibly parallelizable parts, in order to enable making global decisions about its implementation. With our modeling, a skeleton is described by an algorithmic structure and a data flow graph, built from the composition of bones and other skeletons. We introduce this notion of bones which represent elementary sequential or parallel patterns whose implementation is available (from the library or designed by well-aware developers), whereas skeletons are automatically implemented from their description. The proposed design, implemented with template metaprogramming, is able to operate both at compile- and run-time. It allows implementing new bones, describing new skeletons, or simply the instantiation of a skeleton by providing muscles in the form of sequential functions.

Once a skeleton is instantiated, one can decide to generate either a sequential or a parallel code of the algorithm. To optimize the parallelization process, we propose orchestrators, in the form of C++ templates that can analyze a skeleton at compile-time and tune its execution.

A C++ library-based solution is presented, and its mechanisms and usage are illustrated by implementing a GRASPxELS algorithm, a common operational research metaheuristic, that enables two levels of parallelism. Performance results show that this approach presents negligible run-time overhead.