A hierarchical algorithm for one-dimensional gate assignment based on contraction of nets

A one-dimensional gate assignment algorithm based on hierarchical contraction of nets is proposed. In this algorithm, a special feature of multiterminal nets plays an important role, namely that if the gates can be arranged such that the nets with fewer terminals are shorter, the chip area will be much reduced. The algorithm consists of two phases, hierarchical contraction of nets and partial gate assignment. In the first phase, the original problem is partitioned to multiple levels with the basis on contraction of multiterminal nets, and in the next phase, the gates at each level are placed close to one another. Experimental results on logic circuits are shown which are superior to those obtained by the method presented by T. Fujii, et al. (ibid., vol.CAD-6, no.3, p.159-64, March 1987)