Multi-objective design space exploration using genetic algorithms

ABSTRACT

In this work, we provide a technique for efficiently exploring a parameterized system-on-a-chip (SoC) architecture to find all Pareto-optimal configurations in a multi-objective design space. Globally, our approach uses a parameter dependency model of our target parameterized SoC architecture to extensively prune non-optimal sub-spaces. Locally, our approach applies Genetic Algorithms (GAs) to discover Pareto-optimal configurations within the remaining design points. The computed Pareto-optimal configurations will represent the range of performance (e.g., timing and power) tradeoffs that are obtainable by adjusting parameter values for a fixed application that is mapped on the parameterized SoC architecture. We have successfully applied our technique to explore Pareto-optimal configurations for a number of applications mapped on a parameterized SoC architecture.

REFERENCES

• 1: David H. Albonesi, Selective cache ways: on-demand cache resource allocation, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.248-259, November 16-18, 1999, Haifa, Israel
• 2: C. J. Alpert, L. W. Hagen, and A. B. Kahng. A hybrid multilevel/genetic approach for circuit partitioning. In Fifth ACM/SIGDA Physical Design Workshop, pages 100--105, Apr. 1996.
• 3: Charles J. Alpert , Andrew B. Kahng, Recent directions in netlist partitioning: a survey, Integration, the VLSI Journal, v.19 n.1-2, p.1-81, Aug. 1995 [doi>10.1016/0167-9260(95)00008-4]
• 4: C. A. C. Coello. A comprehensive survey of evolutionary-based multiobjective optimization techniques. Knowledge and Information Systems. An International Journal, 1(3):269--308, Aug. 1999.
• 5: Tony D. Givargis , Frank Vahid , Jörg Henkel, Fast cache and bus power estimation for parameterized system-on-a-chip design, Proceedings of the conference on Design, automation and test in Europe, p.333-339, March 27-30, 2000, Paris, France [doi>10.1145/343647.343791]
• 6: Tony Givargis , Frank Vahid , Jörg Henkel, System-level exploration for pareto-optimal configurations in parameterized systems-on-a-chip, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
• 7: Ricardo E. Gonzalez, Xtensa: A Configurable and Extensible Processor, IEEE Micro, v.20 n.2, p.60-70, March 2000 [doi>10.1109/40.848473]
• 8: J. Heitkötter and D. Beasley. The hitch-hiker's guide to evolutionary computation. http://surf.de.uu.net/encore/www/, Apr. 12 2001.
• 9: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 10: Y.-M. Jiang, K.-T. Cheng, and A. Krstic. Estimation of maximum power and instantaneous current using a genetic algorithm. In Proceedings of IEEE Custom Integrated Circuits Conference, pages 135--138, May 1997.
• 11: V. Kommu and I. Pomenraz. GAFAP: Genetic algorithm for FPGA technology mapping. In European Design Automation Conference, pages 300--305, 1993.
• 12: J. Lienig and K. Thulasiraman. A genetic algorithm for channel routing in VLSI circuits. Evolutionary Computation, 1(4):293--311, 1993.
• 13: Afzal Malik , Bill Moyer , Dan Cermak, A programmable unified cache architecture for embedded applications, Proceedings of the 2000 international conference on Compilers, architecture, and synthesis for embedded systems, p.165-171, November 17-19, 2000, San Jose, California, United States [doi>10.1145/354880.354903]
• 14: Pinaki Mazumder , Elizabeth M. Rudnick, Genetic algorithms for VLSI design, layout & test automation, Prentice Hall PTR, Upper Saddle River, NJ, 1999
• 15: D. Saab, Y. Saab, and J. Abraham. Automatic test vector cultivation for sequential vlsi circuits using genetic algorithms. IEEE Transactionsn Computer-Aided Design, 15(10):1278--1285, Oct. 1996.
• 16: K. Shahookar and P. Mazumder. A genetic approach to standard cell placement using metagenetic parameter optimization. IEEE Transactions on Computer-Aided Design, 9:500--511, May 1990.
• 17: Tajana Šimunić , Luca Benini , Giovanni De Micheli, Cycle-accurate simulation of energy consumption in embedded systems, Proceedings of the 36th ACM/IEEE conference on Design automation, p.867-872, June 21-25, 1999, New Orleans, Louisiana, United States [doi>10.1145/309847.310090]
• 18: Mircea R. Stan , Wayne P. Burleson, Bus-invert coding for low-power I/O, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.3 n.1, p.49-58, March 1995 [doi>10.1109/92.365453]
• 19: E. Zitzler, M. Laumanns, and L. Thiele. SPEA2: Improving the performance of the strength pareto evolutionary algorithm. Technical Report TIK-Report 103, Computer Engineering and Communication Networks Lab, Swiss Federal Institute of Technology (ETH) Zurich, Gloriastrasse 35, CH-8092, May 2001.
• 20: E. Zitzler and L. Thiele. Multiobjective evolutionary algorithms: A comparative case study and the strength pareto approach. IEEE transactions on Evolutionary Computation, 4(3):257--271, Nov. 1999.

INDEX TERMS

Primary Classification:
  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.1 Project and People Management
          Subjects: Systems analysis and design

Additional Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: System architectures

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.7 Organization and Design

General Terms:
Algorithms, Design, Performance

Keywords:
Pareto-optimal configurations, design space exploration, genetic algorithms, low power design, system-on-a-chip architectures