A parameterized compositional multi-dimensional multiple-choice knapsack heuristic for CMP run-time management

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.

REFERENCES

• 1: M. Akbar et al. Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls. Computers and Operations Research, 33(5):1259--1273, 2006.
• 2: M. Geilen et al. An algebra of Pareto points. Fundamenta Informaticae, 78(1):35--74, 2007.
• 3: S. V. Gheorghita et al. Application Scenarios in Streaming-Oriented Embedded-System Design. IEEE Design and Test of Computers, 25(6):581--589, 2008.
• 4: S. Khan et al. The utility model for adaptive multimedia systems. Int. Workshop on Multimedia Modeling, p. 111--126, 1997.
• 5: S. Khan et al. Solving the knapsack problem for adaptive multimedia systems. Studia Informatica Universalis, p. 161--182, 2002.
• 6: S. Khuri et al. The zero/one multiple knapsack problem and genetic algorithms. ACM Symp. of applied computation, 1994.
• 7: Lp_solve. http://lpsolve.sourceforge.net.
• 8: M. Moser et al. An algorithm for the multidimensional multiple-choice knapsack problem. IEICE Trans. on Fundamentals of Electronics, E80-A(3):582--589, 1997.
• 9: MMKP Problems. ftp://cermsem.univparisl.fr/pub/CERMSEM/hifi/MMKP/MMKP.html.
• 10: R. Parra-Hemandez and N. Dimopoulos. A new heuristic for solving the multichoice multidimensional knapsack problem. IEEE Trans. on Systems, Man, Cybernetics, 35(5):708--717, 2005.
• 11: SimIt-ARM. http://simit-arm.sourceforge.net.
• 12: Ch. Ykman-Couvreur et al. Fast Multi-Dimension Multi-Choice Knapsack Heuristic for MP-SoC Run-Time Management. In SoC 2006, p. 1--4. IEEE, 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION
      C.5.4 VLSI Systems

General Terms:
Algorithms, Design, Performance

Keywords:
CMP run-time management, MMKP, Pareto algebra