An Evolutionary Toolchain for Morphological Filter Mapping on Many-Core Architectures

Many-core systems are systolic architectures consisting of an arbitrarily large number of processing nodes connected by a point-to-point communication network. Their architecture makes them ideally suited for the implementation of data-flow algorithms, of which Mathematical Morphology (MM) filters are a typical example. However, the performance of data-flow applications on many-core systems is highly dependent on the quality of the mapping of the application tasks to the computational cores. Decomposing the structuring elements of morphological operations improves their performance, however, performing such decomposition on many-core systems leads to increased communication. The need to find a balance between performance and communication is a representative example of the general problem of mapping optimizations. The approach presented in this paper explores a two-phase design-time optimization toolchain based on evolutionary algorithms: a front-end single-objective algorithm decomposes a MM filter using smaller operators, while a back-end multi-objective (fault-tolerance, energy, and communication) algorithm searches for optimal mappings of the filter on a specific many-core system, taking into account the architectural parameters of the hardware. The output of the toolchain is a Pareto front of mapping solutions, allowing the designer to select an implementation that matches application-specific requirements. A set of standard benchmark applications was used to determine the optimal parameters for the algorithms, which were then validated on two real-world application examples involving the detection of features in high-resolution PCB images. Two application mapping experiments focusing on energy constraints were conducted, in which the proposed procedure was compared to deterministic mapping techniques. The evolutionary procedure was observed to offer a significant advantage over the deterministic approach, with percentage gains of up to 73.78% for smaller grids.