Fast multidimension multichoice knapsack heuristic for MP-SoC runtime management

Since the application complexity is growing and applications can be dynamically activated, the major challenge for heterogeneous multiprocessor platforms is to select at runtime an energy-efficient mapping of these applications. Taking into account that many different possible implementations per application can be available, and that the selection must meet the application deadlines under the available platform resources, this runtime optimization problem can be modeled as a Multidimension Multichoice Knapsack Problem (MMKP), which is known to be NP-hard. Not only algorithms for an optimal solution, but also state-of-the-art heuristics for real-time systems are still too slow for runtime management of multiprocessor platforms. This article provides a new fast and lightweight heuristic for finding near-optimal solutions for MMKP problems. The main contribution of this heuristic is: (i) the Pareto filtering of each initial MMKP set to reduce the search space, (ii) the sorting of all Pareto points together in a single two-dimension search space, where (iii) a very fast greedy algorithm solves the MMKP. Experiments show that our heuristic finds solutions close (within 0% to 0.4%) to the ones obtained by the fastest state-of-the-art heuristics, in just a fraction of the execution time (more than 97.5% gain on a StrongARM processor) and can run in less than 1ms for multiprocessor problem sizes. This is required for realistic OS reaction times in video and wireless application sets.