DAARM: Design-time application analysis and run-time mapping for predictable execution in many-core systems

Future many-core systems are envisaged to support the concurrent execution of varying mixes of different applications. Because of the vast number of binding options for such mixes on heterogeneous resources, enabling predictable application execution is far from trivial. Hybrid application mapping is an efficient way of achieving run-time predictability by combining design-time analysis of application mappings with run-time management. Existing hybrid mapping strategies focus on computation resources and either ignore communication details or make significantly simplifying assumptions like unlimited bandwidth or exclusive usage. But, actual many-core systems consist of constrained and shared computation and communication resources where the run-time decision of whether a feasible application binding on a set of preoccupied resources exists or not is an NP-complete problem. As a remedy, we present a novel hybrid application mapping approach that considers constrained shared communication and computation resources. Here, (a) a design space exploration coupled with a formal performance analysis delivers several resource reservation configurations with verified real-time guarantees for each individual application. The configurations are then transformed to (b) a novel efficient intermediate representation that is passed to the run-time management where we (c) formulate run-time resource reservation and application binding as a constraint satisfaction problem and present an adequate solving mechanism. Our experimental evaluation shows that existing approaches may produce infeasible outcomes and are thus not applicable for predictable application execution, while the proposed approach enables predictable and efficient run-time management of dynamic application mixes.