A Floorplanning Algorithm with Minimum Total Length Wires

Abstract:

A floorplan is employed to represent the placement of modules in VLSI design. Floorplanning is a key step in the design of VLSI systems because it provides the first estimates of performance and cost including placement and routing. In this paper, we show an algorithm1 for initial global routing by the single-sequence (SS). The aim of our algorithm is to get a minimum chip area and the shortest total length of wires where the longest (critical) wire in every net is reduced to a minimum. The experimental results show that the design of placement and routing in floorplanning can be considered simultaneously by our algorithm, the efficiency of automatic layout in VLSI can be raised.

• Periodical: Advanced Materials Research (Volume 705)
• Pages: 630-635
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.705.630
• Online since: June 2013
• Authors: Hai Yan Yang, Hua An Zhao
• Keywords: Floorplan, Placement, Routing, VLSI

References

[1] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, "VLSI module placement based on rectangle-packing by the sequence-pair," IEEE Trans. Comput. Aided Design, vol. 15, pp.1518-1524, Dec. 1996.

DOI: 10.1109/43.552084

[2] K. Sakanushi, Y. Kajitani and D. P. Mehta, "The Quarter-State-Sequence Floorplan Representation," IEEE Trans. Circuits and Systems, vol.50, pp.376-386, March, 2003.

DOI: 10.1109/tcsi.2003.809442

[3] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C.-K. Cheng, and J. Gu, "Corner block list: an effective and efficient topological representation of nonslicing floorplan," in Proc. IEEE/ACM Int. Conf. Computer-Aided Design, 2000, pp.8-12.

DOI: 10.1109/iccad.2000.896442

[4] Xuliang Zhang, Yoji Kajitani, "Theory of T-junction floorplans in terms of single-sequence." ISCAS (5) 2004: 341-344.

DOI: 10.1109/iscas.2004.1329532

[5] H.A. Zhao, C. Liu, Y. Kajitani and K. Sakanushi, "EQ-Sequences for Coding Floorplan," EICE Trans. Fundamentals. Vol. E87-A, No. 12, pp.3233-3243, 2004.

[6] X. Zhang and Y. Kajitani, Space-planning: placement of modules with controlled empty area by single- sequence, Proc. Asia and South Pacific Design Automation Conf., p.25–30, Japan.

DOI: 10.1109/aspdac.2004.1337534

[7] M. R. Kramer and J. van Leeuwen. "The complexity of wire routing and finding minimum area layouts for arbitrary VLSI circuits." In F. P. Preparata, editor, Advances in computing research, volume 2: VLSI theory, pages 129–146. JAI, Reading, MA, 1984.

[8] A. B. Kahng and G. Robins, "On optimal interconnections for VLSI," Kluwer Academic Publishers, Boston, MA, 1995.

[9] J. Hu and S. S. Sapatnekar, "A Survey on Multi-net Global Routing for Integrated Circuits," Integration: The VLSI Journal, Vol. 31, No. 1, p.1 – 49, November 2001.

DOI: 10.1016/s0167-9260(01)00020-7

[10] H.A Zhao, Z. Yang, T. Mihara, etc, "VLSI Floorplanning with Boundary Constraints using Genetic Algorithms," Advances in Natural Computation and Data Mining, pp.59-68, 2006.

[11] C. Albrecht. Global routing by new approximation algorithms for multicommodity flow. IEEE Trans. On Computer-Aided Design of Integrated Circuits and Systems, 20(5):622–631, May 2001.

DOI: 10.1109/43.920691

[12] M. Borah, R. M. Owens, and M. J. Irwin. An edge-based heuristic for Steiner routing. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 13(12):1563–1568, December 1994.

DOI: 10.1109/43.331412