Study on Electronic Industry with an Application of Rectilinear Embedding in VLSI Placement

Abstract:

The electronic industry has developed quickly in last few years, with the rapid growth of Very Large Scale Integration technology. Placement layout is considered as the original step in VLSI physical design. The rectilinear embedding, which originates from graph theory, has wide range of application in VLSI placement. In this paper, we constructed a mathematical model for VLSI placement. Firstly, the VLSI placement was converted to quadrangulation by using rectilinear embedding speculative knowledge. Then we provided generating functions for two types of quadrangulations with graph multiple parameters. And the explicit formulae were obtained by employing Lagrangian inversion. Furthermore, we found the relationship 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 arithmetical algorithms, which can be widely used in the optimization of VLSI placement.

• Periodical: Applied Mechanics and Materials (Volume 345)
• Pages: 355-358
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.345.355
• Online since: August 2013
• Authors: Li Yan Pan, Yan Pei Liu
• Keywords: Electronic Industry, 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.