An Application of Rectilinear Embedding in VLSI Placement

Abstract:

The VLSI (Very Large Scale Integrated Circuits) technology has developed rapidly in recent years, with a lot of advanced electric products emerging. Placement layout is regarded as the initial step in VLSI physical design. Its quality has a direct effect on the chip area and performance. The rectilinear embedding, which originates from graph theory, is widely employed in VLSI placement. In this paper, we set up a mathematical model for VLSI. Firstly, the issue of VLSI placement was converted to quadrangulation by using rectilinear embedding. Then we provided generating functions for two types of quadrangulations with graph multiple parameters. And the explicit formulae by employing Lagrangian inversion were obtained. Furthermore, we found the relation between outerplanar graph and Hamilton graph, so the counting result of Hamilton quadrangulation was derived. The quadrangulation calculation can be applied to the establishment of a computerized algorithm, which can be widely used for VLSI placement optimization.

• Periodical: Advanced Materials Research (Volumes 734-737)
• Pages: 2842-2845
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.734-737.2842
• Online since: August 2013
• Authors: Li Yan Pan*, Yan Pei Liu
• Keywords: Lagrangian Inversion, Quadrangulation, Rectilinear Embedding, VLSI Placement

References

[1] Ning Xu, Xianlong Hong and Sheqin Dong: Journal of computer-aided design & computer graphics Vol. 17(2005), P. 663 (In Chinese).

[2] Hoo.Chyi-Shiang, Yeo.Hock-Chai, Jeevan.Kanesan, etc: Engineering Applications of Artificial Intelligence Vol. 26(2013), P. 584.

[3] Koakutsu.Seiichi, Urushida.Yuji, and Hirata.Hironori: Electrical Engineering in Japan (English translation of Denki Gakkai Ronbunshi) Vol. 131(2000), P. 86.

[4] Gunnar Brinkmann: Discrete Mat Vol. 305(2005), P. 33.

[5] Heidi Gebauer: Theoretical computer science Vol. 412(2011), P. 4579.