Analysis of multi-objective evolutionary algorithms to optimize dynamic data types in embedded systems

ABSTRACT

New multimedia embedded applications are increasingly dynamic, and rely on Dynamically-allocated Data Types (DDTs) to store their data. The optimization of DDTs for each target embedded system is a time-consuming process due to the large design space of possible DDTs implementations. Thus, suitable exploration methods for embedded design metrics (memory accesses, memory usage and power consumption) need to be developed. In this work we present a detailed analysis of the characteristics of different types of Multi-Objective Evolutionary Algorithms (MOEAs) to tackle the optimization of DDTs in multimedia applications and compare them with other state-of-the-art heuristics. Our results with state-of-the-art MOEAs in two object-oriented multimedia embedded applications show that more sophisticated MOEAs (SPEA2 and NSGA-II) offer better solutions than simple schemes (VEGA). Moreover, the suitable sophisticated scheme varies according to the available exploration time, namely, NSGA-II outperforms SPEA2 in the first set of solutions (300-500 generations), while SPEA2 offers better solutions afterwards.

REFERENCES

• 1: James L. Antonakos , Kenneth C. Mansfield, Practical Data Structures Using C/C++ with 3.5 Disk, Prentice Hall PTR, Upper Saddle River, NJ, 1998
• 2: 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]
• 3: Luca Benini , Giovanni de Micheli, System-level power optimization: techniques and tools, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.115-192, April 2000 [doi>10.1145/335043.335044]
• 4: F. Catthoor et al. Data access and storage management for embedded programmable processors. Kluwer Academic Publishers, 2002.
• 5: E. G. Daylight et al. Memory-access-aware data structure transformations for embedded software with dynamic data accesses. IEEE Transactions on VLSI Systems, 12:269--280, 2004.
• 6: Kalyanmoy Deb , Deb Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, Inc., New York, NY, 2001
• 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: J. Edler. Dinero IV trace-driven uniprocessor cache simulator. Available at http://pages.cs.wisc.edu/~markhill/DineroIV, 2007.
• 9: K. Hardee et al. A 0.6v 205MHz 19.5ns tRC 16Mb embedded DRAM. In IEEE International Solid-State Circuits Conference (ISSCC), 2004.
• 10: L. Kharevych and R. Khan. 3D physics engine for elastic and deformable bodies. Available at http://www.cs.umd.edu/Honors/reports/kharevych.html, 2002. University of Maryland, College Park.
• 11: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 12: 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]
• 13: S. Ranji Ranjithan , S. Kishan Chetan , Harish K. Dakshina, Constraint Method-Based Evolutionary Algorithm (CMEA) for Multiobjective Optimization, Proceedings of the First International Conference on Evolutionary Multi-Criterion Optimization, p.299-313, March 07-09, 2001
• 14: J. David Schaffer, Multiple Objective Optimization with Vector Evaluated Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms, p.93-100, July 01, 1985
• 15: J. R. Schott. Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization. PhD thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1995.
• 16: 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.
• 17: Sourceforge. Vdrift racing simulator. Available at http://sourceforge.net/projects/vdrift.
• 18: S. Wuytack, F. Catthoor, and H. De Man. Transforming set data types to power optimal data structures. IEEE Transactions on Computer-Aided Design, 15(6):619--629, 1996.
• 19: 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.
• 20: E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: a comparative case study and the strength pareto approach. IEEE Transactions on Evolutionary Computing, 3(4):257--271, 1998.

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, multi-objective optimization, pareto optimal front