Circuit clustering for delay minimization under area and pin constraints

Honghua Hannah Yang, D.F. Wong

Research output: Contribution to journalJournal articlepeer-review

21 Citations (Scopus)


We consider the problem of circuit partitioning for multiple-chip implementations. One motivation for studying this problem is the current need for good partitioning tools for implementing a circuit on multiple field programmable gate array (FPGA) chips. We allow duplication of logic gates as it could be used to reduce circuit delay. Circuit partitioning with duplication of logic gates is also called circuit clustering. In this paper, we present a circuit clustering algorithm that minimizes circuit delay subject to both area and pin constraints on each chip, using the general delay model. We develop a repeated network cut technique for finding a cluster that is bounded by both area and pin constraints. Our algorithm achieves optimal delay under either the area constraint only or the pin constraint only. Under both area and pin constraints, our algorithm achieves optimal delay in most cases. We outline the condition under which the nonoptimality occurs, and we show that the condition rarely occurs in practice. We tested our algorithm on a set of benchmark circuits, and consistently obtained optimal or near-optimal delays.
Original languageEnglish
Article number658566
Pages (from-to)976-986
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number9
Publication statusPublished - Sept 1997


Dive into the research topics of 'Circuit clustering for delay minimization under area and pin constraints'. Together they form a unique fingerprint.

Cite this