TY - GEN
T1 - Circuit clustering for delay minimization under area and pin constraints
AU - Yang, Honghua
AU - Wong, D. F.
N1 - Funding Information:
*This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by an Intel Foundation Graduate Fellowship, by a DAC Design Automation Scholarship, and by grant from AT&T Bell Laboratories.
PY - 1995/3/6
Y1 - 1995/3/6
N2 - We consider the problem of circuit partitioning for multiple-chip implementation. One motivation for studying this problem is the current needs of good partitioning tools for implementing a circuit on multiple FPGA chips. We allow duplication of logic gates as it would 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 show that the condition occurs rarely in practice. We tested our algorithm on a set of benchmark circuits and consistently obtained optimal or near-optimal delays.
AB - We consider the problem of circuit partitioning for multiple-chip implementation. One motivation for studying this problem is the current needs of good partitioning tools for implementing a circuit on multiple FPGA chips. We allow duplication of logic gates as it would 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 show that the condition occurs rarely in practice. We tested our algorithm on a set of benchmark circuits and consistently obtained optimal or near-optimal delays.
UR - http://www.scopus.com/inward/record.url?scp=33746372654&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33746372654&partnerID=8YFLogxK
U2 - 10.1109/edtc.1995.470418
DO - 10.1109/edtc.1995.470418
M3 - Conference contribution
AN - SCOPUS:33746372654
T3 - Proceedings of the 1995 European Conference on Design and Test, EDTC 1995
SP - 65
EP - 70
BT - Proceedings of the 1995 European Conference on Design and Test, EDTC 1995
PB - Association for Computing Machinery
T2 - 1995 European Conference on Design and Test, EDTC 1995
Y2 - 6 March 1995 through 9 March 1995
ER -