Dedicated Floorplanning Engine Architecture Based on Genetic Algorithm and Evaluation

Masaya Yoshikawa; Hidekazu Terai

doi:10.20965/jaciii.2006.p0112

single-jc.php

« previous

JACIII Vol.10 No.1 pp. 112-120

doi: 10.20965/jaciii.2006.p0112

(2006)

Paper:

Views over last 60 days: 581

Dedicated Floorplanning Engine Architecture Based on Genetic Algorithm and Evaluation

Masaya Yoshikawa, and Hidekazu Terai

Department of VLSI System Design, Ritsumeikan University, 1-1-1 Nojihigashi, Kusatsu, Shiga 525-8577, Japan

Received:

June 24, 2005

Accepted:

October 7, 2005

Published:

January 20, 2006

Keywords:

Genetic Algorithm, floorplanning, dedicated hardware, evolutionary pipeline, sequence pair

Abstract

The floorplanning problem, a basic design step in layout design of very large-scale integrated circuit (VLSI), deals with placing rectangular modules at maximum density. Many studies have dealt with conducted this problem using sequence pairs based on genetic algorithms (GAs), but this generally requires much calculation time. We propose an architecture for high-speed floorplanning using a sequence pair based on GA. The proposed architecture, implemented on the field-programmable gate array (FPGA), achieves high-speed processing. Measurement evaluating the proposed architecture demonstrated speeds 37.1 times greater than software processing.

Cite this article as:

M. Yoshikawa and H. Terai, “Dedicated Floorplanning Engine Architecture Based on Genetic Algorithm and Evaluation,” J. Adv. Comput. Intell. Intell. Inform., Vol.10, No.1, pp. 112-120, 2006.

Data files:

References

[1] J. Cong, Z. Pan, L. Hei, C. K. Koh, and K. Y. Khoo, “Interconnect design for deep submicron ICs,” Dig.Tech.Papers ICCAD, pp. 478-485, 1997.
[2] K. Bazargan, S. Kim, and M. Sarrafzadeh, “A floorplanner of uncertaindesigns,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol.18, No.4, pp. 389-397, 1997.
[3] S. M. Sait, and H. Youssef, “VLSI Physical Design Automation,” IEEE Press, 1995.
[4] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “VLSI module placement based on rectangle-packing by the sequence-pair,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol.15, No.12, pp. 1518-1524, 1996.
[5] K. Hatta, S. Wakabayashi, and T. Koide, “Solving the rectangular packing problem by an adaptive GA based on sequence pair,” Proc. Asia-South Pacific Design Automation Conference, pp. 181-184, 1999.
[6] S. Nakaya, T. Koide, and S. Wakabayashi, “An adaptive genetic algorithm for VLSI floorplanning based on sequence-pair,” Proc. IEEE International Symposium on Circuits and Systems, Vol.3, pp. 65-68, 2000.
[7] J. Holland, “Adaptation in Natural Artificial Systems,” the University of Michigan Press (Second edition; MIT Press), 1992.
[8] S. D. Scott, A. Samal, and S. Seth, “HGA: A Hardware-Based Genetic Algorithm,” Int. Symposium on Field-Programmable Gate Array, pp. 53-59, 1995.
[9] P. Graham, and B. Nelson, “Genetic Algorithm in Software and in Hardware A performance Analysis of Workstation and custom Computing Machine Implementations,” FPGAs for Custom Computing Machines, pp. 216-225, 1996.
[10] N. Yoshida, T. Moriki, and T. Yasuoka, “GAP: Genetic VLSI Processor for Genetic Algorithms,” Proc. Second Int7l ICSC Sym. On Soft Computing, pp. 341-345, 1997-9.
[11] “GSRC: Gigascale System Research Center”
( http://www.gigascale.org )

This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

[1] [1] J. Cong, Z. Pan, L. Hei, C. K. Koh, and K. Y. Khoo, “Interconnect design for deep submicron ICs,” Dig.Tech.Papers ICCAD, pp. 478-485, 1997.

[2] [2] K. Bazargan, S. Kim, and M. Sarrafzadeh, “A floorplanner of uncertaindesigns,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol.18, No.4, pp. 389-397, 1997.

[3] [3] S. M. Sait, and H. Youssef, “VLSI Physical Design Automation,” IEEE Press, 1995.

[4] [4] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “VLSI module placement based on rectangle-packing by the sequence-pair,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol.15, No.12, pp. 1518-1524, 1996.

[5] [5] K. Hatta, S. Wakabayashi, and T. Koide, “Solving the rectangular packing problem by an adaptive GA based on sequence pair,” Proc. Asia-South Pacific Design Automation Conference, pp. 181-184, 1999.

[6] [6] S. Nakaya, T. Koide, and S. Wakabayashi, “An adaptive genetic algorithm for VLSI floorplanning based on sequence-pair,” Proc. IEEE International Symposium on Circuits and Systems, Vol.3, pp. 65-68, 2000.

[7] [7] J. Holland, “Adaptation in Natural Artificial Systems,” the University of Michigan Press (Second edition; MIT Press), 1992.

[8] [8] S. D. Scott, A. Samal, and S. Seth, “HGA: A Hardware-Based Genetic Algorithm,” Int. Symposium on Field-Programmable Gate Array, pp. 53-59, 1995.

[9] [9] P. Graham, and B. Nelson, “Genetic Algorithm in Software and in Hardware A performance Analysis of Workstation and custom Computing Machine Implementations,” FPGAs for Custom Computing Machines, pp. 216-225, 1996.

[10] [10] N. Yoshida, T. Moriki, and T. Yasuoka, “GAP: Genetic VLSI Processor for Genetic Algorithms,” Proc. Second Int7l ICSC Sym. On Soft Computing, pp. 341-345, 1997-9.

[11] [11] “GSRC: Gigascale System Research Center”
( http://www.gigascale.org )