An improvement algorithm on general connectivity computation for VLSI placement

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.