HaVaSHet: Handling Variability and Scalability in the presence of Heterogeneity
Since mid 2000s we have seen an increased amount of multi-processor systems being deployed in commercial embedded systems. Today, mobile phones, car infotainment systems and the mobile infrastructure (e.g., base-stations) have computing engines composed of multiple processing elements. Often, these systems are heterogeneous for energy efficiency reasons and to overcome the power density barrier of CMOS systems. Examples are the famous Big.LITTLE architecture from ARM or several platforms from Texas Instruments that combine multiple scalar and digital signal processors on one chip. With heterogeneity, the already hard problem of parallel programming became even more challenging.
Silexica is an innovative company that set up to address the programming challenge for heterogeneous multi-processor systems. Silexica offers a tool suite for analysis, parallelization, optimization and code generation for applications, mainly in the signal processing and multimedia domains. The SLX Mapper tool, in particular, optimizes parallel applications written in a so-called dataflow-programming language, called “C for Process Networks” (CPN). This is an expressive language that allows to represent parallel communicating tasks, in which the communication pattern may be determined by the data itself. This expressiveness makes it impossible to fully analyze applications at compile time, for which run-time information is collected in form of traces to steer the optimizations in the SLX Mapper. To support heterogeneous systems, Silexica defined a detailed architecture model, currently undergoing a standardization process.
As applications become more complex, variability increases, i.e., the behavior becomes more dependent on the input data. As an example, the amount of computational power required for a video decoder can change considerably depending on the video feed. At the same time, larger applications and target platforms will demand for new, more scalable techniques in the SLX Mapper. In this TTP we address both the variability and scalability issues in the SLX Mapper. For variability, we add support for analyzing multiple traces of a single application. For scalability, we exploit symmetries in both the application and the target platform to reduce the search space for the optimization algorithms.
Multiple-traces support for variability includes extensions for reading multiple traces, trace theory methods for quantifying and classifying these traces and an extension to the mapping flow in the SLX Mapper. With the latter, it is possible to generate different mappings for different traces, or to export the single mapping that better performs across all traces. For scalability, we enhanced the SLX Mapper by including methods to leverage architectural symmetries of the hardware. Hardware platforms, even heterogeneous ones, usually have some degree of symmetry, for example by having several processors of a given type. We use these symmetries to reduce the amount of mappings that have to be analyzed while searching for a near-optimal solution, thereby improving the scalability of the techniques within the SLX Mapper. When testing the symmetry-approach for two applications from Silexica, we observed a reduction of 2-3 orders of magnitude in the exploration time.