DocumentCode :
500889
Title :
A parameterized compositional multi-dimensional multiple-choice knapsack heuristic for CMP run-time management
Author :
Shojaei, Hamid ; Ghamarian, AmirHossein ; Basten, Twan ; Geilen, Marc ; Stuijk, Sander ; Hoes, Rob
Author_Institution :
Univ. of Wisconsin-Madison, Madison, WI, USA
fYear :
2009
fDate :
26-31 July 2009
Firstpage :
917
Lastpage :
922
Abstract :
Modern embedded systems typically contain chip-multiprocessors (CMPs) and support a variety of applications. Applications may run concurrently and can be started and stopped over time. Each application may typically have multiple feasible configurations, trading off quality aspects (energy consumption, audio-visual quality) with resource usage for various types of resources. Overall system quality needs to be guaranteed and optimized at all times. This leads to the need for a run-time management solution that selects an appropriate system configuration from all the application configurations of active applications. This run-time management problem can be phrased as a multi-dimensional multiple-choice knapsack (MMKP) problem. We present a compositional heuristic to solve MMKP, that due to the compositionality is better suited to CMP run-time management than existing heuristics that are all not compositional. Our heuristic outperforms the best-known heuristic to date. The heuristic is parameterized, leading to the additional advantage that it allows to trade off execution time vs. solution quality, and to bound the time needed to compute a solution. The latter makes it particularly well-suited for resource-constrained embedded platforms.
Keywords :
Pareto optimisation; algebra; knapsack problems; microprocessor chips; CMP run-time management; Pareto algebra; audio-visual quality; chip multiprocessors; embedded systems; energy consumption; off-line Pareto analysis; parameterized compositional multidimensional multiple-choice knapsack heuristic; resource-constrained embedded platforms; Algebra; Algorithm design and analysis; Clocks; Delay; Embedded computing; Embedded system; Energy consumption; Permission; Runtime; Technology management; CMP run-time management; MMKP; Pareto algebra;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Design Automation Conference, 2009. DAC '09. 46th ACM/IEEE
Conference_Location :
San Francisco, CA
ISSN :
0738-100X
Print_ISBN :
978-1-6055-8497-3
Type :
conf
Filename :
5227146
Link To Document :
بازگشت