Mixed heuristic and mathematical programming using reference points for dynamic data types optimization in multimedia embedded systems

ABSTRACT

New multimedia embedded applications are becoming increasingly dynamic. Thus, they cannot only rely on static data allocation, and must employ Dynamically-allocated Data Types (DDTs) to store their data and efficiently use the limited physical resources of embedded devices. However, the optimization of the DDTs for each target embedded system is a very time-consuming process due to the large design space of possible DDTs implementations and selection for the memory hierarchy of each specific embedded device. Thus, new suitable exploration methods for embedded design metrics (memory accesses, usage and power consumption) need to be developed. In this paper we analyze the benefits of two different exploration techniques for DDTs optimization: Multi-Objective Particle Swarm Optimization (MOPSO) and a Mixed Integer Linear Program (MILP). Furthermore, we propose a novel MOPSO exploration method, OMOPSO*, which uses MILP solutions, as reference points, to guide a MOPSO exploration and reach solutions closer to the real Pareto front of solutions. Our experiments with two real-life embedded applications show that our algorithm achieves 40% better coverage and set of solutions than state-of-the-art optimization methods for DDTs (MOGAs and other MOPSOs).

REFERENCES

• 1: ILOG CPLEX. http://www.ilog.com, 2008.
• 2: VDrift racing simulator. http://vdrift.net, 2008.
• 3: David Atienza , Christos Baloukas , Lazaros Papadopoulos , Christophe Poucet , Stylianos Mamagkakis , Jose I. Hidalgo , Francky Catthoor , Dimitrios Soudris , Juan Lanchares, Optimization of dynamic data structures in multimedia embedded systems using evolutionary computation, Proceedingsof the 10th international workshop on Software & compilers for embedded systems, April 20-20, 2007, Nice, France [doi>10.1145/1269843.1269849]
• 4: F. Catthoor, K. Danckaert, C. Kulkarni, E. Brockmeyer, P.G. Kjeldsberg, T.V. Achteren, and T. Omnes. Data access and storage management for embedded programmable processors. Kluwer Academic Publishers, 2002.
• 5: J.M. Cruz, J.L. Risco-Martín, A. Herrán-González, and P. Fernández-Blanco. Hybrid heuristic and mathematical programming in oil pipelines networks. In CEC'04: Proceedings of the 2004 Congress On Evolutionary Computation, volume 2, pages 1479--1486, June 2004.
• 6: E.G. Daylight, D. Atienza, A. Vandecappelle, F. Catthoor, and J.M. Mendias. Memory-access-aware data structure transformations for embedded software with dynamic data accesses. IEEE Transactions on VLSI Systems, 12:269--280, 2004.
• 7: K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2):182--197, 2002.
• 8: K. Hardee, F. Jones, D. Butler, M. Parris, M. Mound, H. Calendar, G. Jones, L. Aldrich, C. Gruenschlaeger, M. Miyabayashil, K. Taniguchi, and I. Arakawa. A 0.6V 205MHz 19.5ns tRC 16Mb embedded DRAM. In IEEE International Solid-State Circuits Conference (ISSCC), 2004.
• 9: J. Ignacio Hidalgo , José L. Risco-Martín , David Atienza , Juan Lanchares, Analysis of multi-objective evolutionary algorithms to optimize dynamic data types in embedded systems, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389388]
• 10: L. Kharevych and R. Khan. 3D physics engine for elastic and deformable bodies. University of Maryland, College Park, 2002.
• 11: X. Li. A non-dominated sorting particle swarm optimizer for multiobjective optimization. In Genetic and Evolutionary Computation -- GECCO-2003, volume 2723 of LNCS, pages 37--48, Chicago, 2003. Springer-Verlag.
• 12: F.A. Lootsma. Multi-Criteria Decision Analysis via Ratio and Difference Judgement, chapter Multi-Objective Linear Programming, pages 1384--6485. Springer, 1999.
• 13: Kaisa Miettinen, Some Methods for Nonlinear Multi-objective Optimization, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.1-20, March 07-09, 2001
• 14: P. R. Panda , F. Catthoor , N. D. Dutt , K. Danckaert , E. Brockmeyer , C. Kulkarni , A. Vandercappelle , P. G. Kjeldsberg, Data and memory optimization techniques for embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.2, p.149-206, April 2001 [doi>10.1145/375977.375978]
• 15: M. Reyes-Sierra and C.A.C. Coello. Improving PSO-based multi-objective optimization using crowding, mutation and epsilon-dominance. In EMO, pages 505--519, 2005.
• 16: M. Reyes-Sierra and C.A.C. Coello. Multi-objective particle swarm optimizers: A survey of the state-of-the-art. International Journal of Computational Intelligence Research, 2(3):287--308, 2006.
• 17: J.L. Risco-Martín. Java Evolutionary COmputation library (JECO). Available at: https://sourceforge.net/projects/jeco, 2008.
• 18: P. Shivakumar and N.P. Jouppi. Cacti 3.0: An integrated cache timing, power, and area model. Technical Report 2001/2, Compaq Computer Corporation, 2001.
• 19: Upali K. Wickramasinghe , Xiaodong Li, Integrating user preferences with particle swarms for multi-objective optimization, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389237]
• 20: L.A. Wolsey. Integer Programming. John Wiley and Sons, 1998.
• 21: E. Zitzler. Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications. PhD thesis, Swiss Federal Institute of Technology (ETH), 1999.
• 22: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the strength Pareto evolutionary algorithm for multiobjective optimization. In Proceedings of the Evolutionary Methods for Design, Optimization and Control with Application to Industrial Problems, pages 95--100, Barcelona, Spain, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Design, Performance

Keywords:
embedded systems design, evolutionary computation, mathematical programming, multi-objective optimization, particle swarm optimization