Please use this identifier to cite or link to this item:
|Title:||An improvement algorithm on general connectivity computation for VLSI placement||Authors:||Shen, Z.X.
|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.
checked on Nov 18, 2021
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.