Hierarchical Parallel Placement Using a Genetic Algorithm for Realizing Low Power Consumption
Masaya Yoshikawa and Hidekazu Terai
Department of VLSI System Design, Ritsumeikan University, 1-1-1 Nojihigashi, Kusatsu, Shiga 525-8577, Japan
With portable information devices now widely disseminated, low power consumption LSIs are increasingly needed in battery, implementation, and heat generation applications. We propose parallel placement to realize low power consumption and confirm its effectiveness in experiments with a commercial electronic design automation (EDA) tool for designing LSIs. Our proposal hierarchically combines outline and detail placement based on genetic algorithm. In selection operators, new evaluation functions are introduced for realizing the reduction of power consumption focusing on the signal transition probability. Considering a parallel processing, in which a processing speed has a scalable relation with the number of processors, and by implementing it in a parallel computer, its effect is demonstrated.
-  R. H. Denner, F. H. Gaensslen, H. N. Yu, V. L. Rideout, E. B. Bassous, and A. R. LeBlance, “Design of Iom-Implanted MOFETs with Very Small Physical Dimensions,” IEEE JSSC, Vol.SC-9, No.5, pp. 256-268, 1974.
-  Semiconductor Industry Association: National Technology Roadmap for semiconductors, 1999.
-  J. Holland, “Adaptation in Natural Artificial Systems,” the University of Michigan Press (Second edition; MIT Press), 1992.
-  D. Goldberg and R. Lingle Jr., “Alleles, loci, and the traveling salesman problem,” Proc.of 1st Int. Conf. On Genetic Algorithms and Their Applications, pp. 154-159, 1985.
-  W.-L. Hung, Y. Xie, N. Vijaykrishnan, C. Addo-Quaye, T. Theocharides, and M. J. Irwin, “Thermal-aware floorplanning using genetic algorithms,” Proc. IEEE Sixth International Symposium on Quality of Electronic Design, pp. 634-639, 2005.
-  Z. Lihong, R. Raut, W. Ling, and J. Yingtao, “Analog module placement realizing symmetry constraints based on a radiation decoder,” Proc. IEEE 47th Midwest Symposium on Circuits and Systems, Vol.1, pp. 481-484, 2004.
-  J. Inagaki and M. Haseyama, “GA-based applications for routing with an upper bound constraint,” Proc. IEEE International Symposium on Circuits and Systems, Vol.3, pp. 2239-2242, 2005.
-  M. Alabau, L. Idoumghar, and R. Schott, “New hybrid genetic algorithms for the frequency assignment problem,” IEEE Transactions on Broadcasting, Vol.48, No.1, pp. 27-34, 2002.
-  C.-C. Lo and W.-H. Chang, “A multiobjective hybrid genetic algorithm for the capacitated multipoint network design problem,” Proc. IEEE Transactions on Systems, Man and Cybernetics, Part B, Vol.30, No.3, pp. 461-470, 2000.
-  B. de Andres y Toro, J. M. Giron-Sierra, P. Fernandez-Blanco, J. M. de la Cruz, and J. A. Lopez-Orozco, “Parallel genetic algorithms with a continuity operator that allows for knowledge inclusion,” Proc. Congress on Evolutionary Computation, Vol.2, pp. 1137-1143, 2000.
-  M. Golub and D. Jakobovic, “A new model of global parallel genetic algorithm,” Proc. 22nd International Information Technology Interfaces, pp. 363-368, 2000.
-  Z. Konfrst, “Parallel genetic algorithms: advances, computing trends, applications and perspectives,” Proc. 18th International Parallel and Distributed Processing Symposium, p. 162, 2004.
-  G. Singh Baicher, “A two stage genetic algorithm for optimisation of causal IIR perfect reconstruction multirate filter banks,” Proc. Congress on Evolutionary Computation, Vol.2, pp. 897-903, 1999.
-  Q. Zhong, T. Xie, and H. Chen, “Task matching and scheduling based on co-evolutionary model,” Proc. of the 3rd World Congress on Intelligent Control and Automation, Vol.3, pp. 1910- 1915, 2000.
-  H. Handa, K. Watanabe, O. Katai, T. Konishi, and M. Baba, “Coevolutionary genetic algorithm for constraint satisfaction with a genetic repair operator for effective schemata formation,” Proc. of IEEE International Conference on Systems, Man, and Cybernetics, Vol.3, pp. 616-621, 1999.