Circuit clustering for delay minimization under area and pin constraints

Honghua Yang, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 1995 European Conference on Design and Test, EDTC 1995
PublisherAssociation for Computing Machinery, Inc
Pages65-70
Number of pages6
ISBN (Electronic)0818670398, 9780818670398
StatePublished - Mar 6 1995
Event1995 European Conference on Design and Test, EDTC 1995 - Paris, France
Duration: Mar 6 1995Mar 9 1995

Publication series

NameProceedings of the 1995 European Conference on Design and Test, EDTC 1995

Other

Other1995 European Conference on Design and Test, EDTC 1995
CountryFrance
CityParis
Period3/6/953/9/95

Fingerprint

Networks (circuits)
Delay circuits
Logic gates
Clustering algorithms
Field programmable gate arrays (FPGA)

ASJC Scopus subject areas

  • Hardware and Architecture
  • Electrical and Electronic Engineering
  • Industrial and Manufacturing Engineering

Cite this

Yang, H., & Wong, D. F. (1995). Circuit clustering for delay minimization under area and pin constraints. In Proceedings of the 1995 European Conference on Design and Test, EDTC 1995 (pp. 65-70). (Proceedings of the 1995 European Conference on Design and Test, EDTC 1995). Association for Computing Machinery, Inc.

Circuit clustering for delay minimization under area and pin constraints. / Yang, Honghua; Wong, D. F.

Proceedings of the 1995 European Conference on Design and Test, EDTC 1995. Association for Computing Machinery, Inc, 1995. p. 65-70 (Proceedings of the 1995 European Conference on Design and Test, EDTC 1995).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Yang, H & Wong, DF 1995, Circuit clustering for delay minimization under area and pin constraints. in Proceedings of the 1995 European Conference on Design and Test, EDTC 1995. Proceedings of the 1995 European Conference on Design and Test, EDTC 1995, Association for Computing Machinery, Inc, pp. 65-70, 1995 European Conference on Design and Test, EDTC 1995, Paris, France, 3/6/95.
Yang H, Wong DF. Circuit clustering for delay minimization under area and pin constraints. In Proceedings of the 1995 European Conference on Design and Test, EDTC 1995. Association for Computing Machinery, Inc. 1995. p. 65-70. (Proceedings of the 1995 European Conference on Design and Test, EDTC 1995).
Yang, Honghua ; Wong, D. F. / Circuit clustering for delay minimization under area and pin constraints. Proceedings of the 1995 European Conference on Design and Test, EDTC 1995. Association for Computing Machinery, Inc, 1995. pp. 65-70 (Proceedings of the 1995 European Conference on Design and Test, EDTC 1995).
@inproceedings{c907d02504ee4909b2878f7fb7999530,
title = "Circuit clustering for delay minimization under area and pin constraints",
abstract = "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.",
author = "Honghua Yang and Wong, {D. F.}",
year = "1995",
month = "3",
day = "6",
language = "English (US)",
series = "Proceedings of the 1995 European Conference on Design and Test, EDTC 1995",
publisher = "Association for Computing Machinery, Inc",
pages = "65--70",
booktitle = "Proceedings of the 1995 European Conference on Design and Test, EDTC 1995",

}

TY - GEN

T1 - Circuit clustering for delay minimization under area and pin constraints

AU - Yang, Honghua

AU - Wong, D. F.

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

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, Inc

ER -