Mathematical Models for VLSI Placement with Rectilinear Embedding

Abstract:

Based on the theory of functional equations in rectilinear embedding, a mathematical model of VLSI placement design was established in this paper. The cell on the plane is conceived as a point, while the wire links the cells is assumed as lines, then the VLSI placement is transformed into quadrangulation by using graph theory. First of all, we obtained generating functions for two types of quadrangulations (quartic graphs) with graph multiple parameters and secondly derived explicit formulae by employing Lagrangian inversion. Furthermore, we found a relation between outerplanar graph and Hamilton graph, and then got the counting result of Hamilton quadrangulation. The quadrangulation calculations could provide a theoretical foundation for computerized algorithm, which can be widely used for VLSI placement optimization.

• Periodical: Advanced Materials Research (Volume 744)
• Pages: 536-539
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.744.536
• Online since: August 2013
• Authors: Li Yan Pan, Yan Pei Liu
• Keywords: Computerized Algorithm, Lagrangian Inversion, Quadrangulation, 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] Jianning Yang, Yuankui Wang and Wenbin Zhao: Journal of Jiangsu University (Natural Science edition) Vol. 25 (2003), P. 65 (In Chinese).

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

[5] Weimin Wu, Xianlong Hong, Yici Cai, etc: Tien Tzu Hsueh Pao/Acta Electronica Sinica Vol. 29(2001), P. 1018.