Optimization of dynamic data structures in multimedia embedded systems using evolutionary computation

ABSTRACT

Embedded consumer devices are increasing their capabilities and can now implement new multimedia applications reserved only for powerful desktops a few years ago. These applications share complex and intensive dynamic memory use. Thus, dynamic memory optimizations are a requirement when porting these applications. Within these optimizations, the refinement of the Dynamically (de)allocated Data Type (or DDT) implementations is one of the most important and difficult parts for an efficient mapping onto low-power embedded devices.

In this paper, we describe a new automatic optimization approach for the DDTs of object-oriented multimedia applications. It is based on an analytical pre-characterization of the possible elementary DDT blocks, and a multi-objective genetic algorithm to explore the design space and to select the best implementation according to different optimization criteria (i.e., memory accesses, memory footprint and energy consumption). Our results in real-life multimedia applications show that the best implementations of DDTs can be obtained in an automated way in few hours, while typically designers would require days to find a suitable implementation, achieving important savings in exploration time with respect to other state-of-the-art heuristics-based optimization methods for this task.

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: Sven Wuytack, Francky Catthoor, and Hugo De Man. Transforming set data types to power optimal data structures. IEEE Transactions on Computer-aided Design, 15(6):619--629, June 1996.
• 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: C++ Standardisation Comittee. Programming languages - C++ - ISO/IEC 14882. Technical report, American National Standards Institutes, 11 West 42nd Street, New York, New York 10036, USA, September 1998.
• 5: Francky Catthoor, K. Danckaert, C. Kulkarni, Eric Brockmeyer, P. G. Kjeldsberg, Tanja Van Achteren, and T. Omnes. Data access and storage management for embedded programmable processors. Kluwer Academic Publishers, Boston, USA, 2002.
• 6: Carlos A. Coello Coello , Gary B. Lamont , David A. Van Veldhuizen, Evolutionary Algorithms for Solving Multi-Objective Problems (Genetic and Evolutionary Computation), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 7: Christophe Poucet, David Atienza, and Francky Catthoor, Template-Based Semi-Automatic Profiling of Multimedia Applications, In Proceedings of the IEEE International Conference on Multimedia and Expo, Toronto, Canada, July 2006. IEEE Computer and Systems Societies.
• 8: E. G. Daylight, David Atienza, Anrout Vandecappelle, Francky Catthoor, and Jose M. Mendias. Memory-access-aware data structure transformations for embedded software with dynamic data accesses. IEEE Transactions on VLSI Systems, pages 269--280, 2004.
• 9: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 10: Ahmed Jerraya and Wayne Wolf. Multiprocessor Systems-on-Chips. Morgan Kaufmann, Elsevier, 2005.
• 11: Marc Leeman , Chantal Ykman , David Atienza , Vincenzo De Florio , Geert Deconinck, Automated Dynamic Memory Data Type Implementation Exploration and Optimization, Proceedings of the IEEE Computer Society Annual Symposium on VLSI (ISVLSI'03), p.222, February 20-21, 2003
• 12: Mark Leeman. Interactive Strategies and Analysis Method for Dynamic Data Type Transformation and Refinement in Multimedia Applications. PhD thesis, Katholieke Universiteit Leuven, October 2003.
• 13: Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (3rd ed.), Springer-Verlag, London, 1996
• 14: Chris Houck, Jeff Joines, and Mike Kay. A Genetic Algorithm for Function Optimization: A Matlab Implementation. NCSU-IE Technical Report 95-09, 1995.
• 15: Melanie Mitchell, An introduction to genetic algorithms, MIT Press, Cambridge, MA, 1996
• 16: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 17: Andrzej Osyczka. Multicriteria optimization for engineering design. In John S. Gero, editor, Design Optimization, pages 193--227. Academic Press, 1985.
• 18: 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
• 19: SGI. Standard template library, 2006. http://www.sgi.com/tech/stl/.
• 20: Asim Smailagic , Daniel P. Siewiorek , Drew Anderson , Chris Kasaback , Tom Martin , John Stivoric, Benchmarking an interdisciplinary concurrent design methodology for electronic/mechanical systems, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.514-519, June 12-16, 1995, San Francisco, California, United States [doi>10.1145/217474.217580]
• 21: Sourceforge. Simblob - the 3d environment builder framework. http://sourceforge.net/projects/simblob.
• 22: Sourceforge. Vdrift racing simulator. http://sourceforge.net/projects/vdrift.
• 23: Derick Wood, Data structures, algorithms, and performance, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993