A new approach to effective circuit clustering

Abstract

The complexity of next-generation VLSI systems will exceed the capabilities of top-down layout synthesis algorithms, particularly in netlist partitioning and module placement. Bottom-up clustering is needed to “condense” the netlist so that the problem size becomes tractable to existing optimization methods. In this paper, we establish the DS qua.lity measure, the first general metric for evaluation of clustering algorithms. The DS metric in turn motivates our RWST algorithm, a new self-tuning clustering method based on random walks in the circuit netlist. RWST efficiently captures a globally good circuit clustering. When incorporated within a two-phase iterative Fiduccia-Mattheyses partitioning strategy, the RW-ST clustering method improves bisection width by an average of 17% over previous maiching-based methods.