Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1145/1952522.1952528 | ACM Trans. Embedded Comput. Syst. |
Keywords | Field | DocType |
multidimension multichoice knapsack heuristic,optimization,runtime management,wireless application set,lightweight heuristic,mp-soc runtime management,heterogeneous multiprocessor platform,application mapping,multiprocessor platform,initial mmkp,multiprocessor mappings,multiprocessor problem size,application complexity,application deadline,mmkp problem,reaction time,energy efficient,optimization problem,knapsack problem,search space,greedy algorithm,two dimensions,real time systems | Mathematical optimization,Heuristic,Computer science,Parallel computing,Real-time computing,Greedy algorithm,Sorting,Multiprocessing,Heuristics,Knapsack problem,Optimization problem,Pareto principle | Journal |
Volume | Issue | ISSN |
10 | 3 | 1539-9087 |
Citations | PageRank | References |
24 | 0.95 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ch. Ykman-Couvreur | 1 | 48 | 3.57 |
| V. Nollet | 2 | 305 | 20.40 |
| F. Catthoor | 3 | 897 | 83.95 |
| H. Corporaal | 4 | 161 | 12.77 |