Please use this identifier to cite or link to this item: https://scholarbank.nus.edu.sg/handle/10635/115382
Title: An improvement algorithm on general connectivity computation for VLSI placement
Authors: Shen, Z.X.
Song, J. 
Zhuang, W.J. 
Issue Date: 1997
Citation: Shen, Z.X.,Song, J.,Zhuang, W.J. (1997). An improvement algorithm on general connectivity computation for VLSI placement. International Symposium on IC Technology, Systems and Applications 7 : 684-686. ScholarBank@NUS Repository.
Abstract: A model of general connectivity and its application to placement was presented previously [Zhuang94]. Its performance on the resulting circuit designs was better than traditional models by 19.2% to 37.8%. However, the computation time of the previous algorithm in the worst case was O(Nk+4), where N is the number of cells in a connection graph and k is the order of general connectivity. An example of previous computation for the 4th-order general connectivities and clustering iteration on a circuit with 1906 cells took 202 CPU hours on an IBM RS6000 workstation. In this paper a new algorithm, called Concurrent Group Search Algorithm (CGSA), is proposed. The algorithm is O(N) times faster than the old one. Experimental results show that it can result in up to 12 times speedup for an example circuit.
Source Title: International Symposium on IC Technology, Systems and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/115382
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

83
checked on Nov 8, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.