Circuit partitioning with complex resource constraints in FPGAs

Huiqun Liu; Kai Zhu; D. F. Wong

doi:10.1145/275107.275122

Circuit partitioning with complex resource constraints in FPGAs

Huiqun Liu, Kai Zhu, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

8 Citations (Scopus)

Abstract

In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing capacity and diverse resource types in the new FPGA architectures. We propose a network flow based method to optimally check whether a circuit or a sub-circuit is feasible for a set of available heterogeneous resources. The feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementation. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g. logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g. Actel's ES6500 FPGA family).

Original language	English
Title of host publication	FPGA '98
Subtitle of host publication	Proceedings of the 1998 ACM/SIGDA 6th International Symposium on Field Programmable Gate Arrays
Publisher	Association for Computing Machinery (ACM)
Pages	77-84
Number of pages	8
ISBN (Print)	9780897919784
DOIs	https://doi.org/10.1145/275107.275122
Publication status	Published - 22 Feb 1998
Event	6th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 1998 - Monterey , United States Duration: 22 Feb 1998 → 25 Feb 1998 https://dl.acm.org/doi/proceedings/10.1145/275107 (Conference proceedings )

Publication series

Name	Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA

Conference

Conference	6th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 1998
Country/Territory	United States
City	Monterey
Period	22/02/98 → 25/02/98
Internet address	https://dl.acm.org/doi/proceedings/10.1145/275107 (Conference proceedings )

Scopus Subject Areas

General Computer Science

Access to Document

10.1145/275107.275122

Cite this

Liu, H., Zhu, K., & Wong, D. F. (1998). Circuit partitioning with complex resource constraints in FPGAs. In FPGA '98 : Proceedings of the 1998 ACM/SIGDA 6th International Symposium on Field Programmable Gate Arrays (pp. 77-84). (Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA). Association for Computing Machinery (ACM). https://doi.org/10.1145/275107.275122

@inproceedings{b52c205638884ce68c9f540be05865f2,

title = "Circuit partitioning with complex resource constraints in FPGAs",

abstract = "In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing capacity and diverse resource types in the new FPGA architectures. We propose a network flow based method to optimally check whether a circuit or a sub-circuit is feasible for a set of available heterogeneous resources. The feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementation. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g. logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g. Actel's ES6500 FPGA family).",

author = "Huiqun Liu and Kai Zhu and Wong, {D. F.}",

year = "1998",

month = feb,

day = "22",

doi = "10.1145/275107.275122",

language = "English",

isbn = "9780897919784",

series = "Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA",

publisher = "Association for Computing Machinery (ACM)",

pages = "77--84",

booktitle = "FPGA '98",

address = "United States",

note = "6th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 1998 ; Conference date: 22-02-1998 Through 25-02-1998",

url = "https://dl.acm.org/doi/proceedings/10.1145/275107",

}

Liu, H, Zhu, K & Wong, DF 1998, Circuit partitioning with complex resource constraints in FPGAs. in FPGA '98 : Proceedings of the 1998 ACM/SIGDA 6th International Symposium on Field Programmable Gate Arrays. Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA, Association for Computing Machinery (ACM), pp. 77-84, 6th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 1998, Monterey , California, United States, 22/02/98. https://doi.org/10.1145/275107.275122

Circuit partitioning with complex resource constraints in FPGAs. / Liu, Huiqun; Zhu, Kai; Wong, D. F.
FPGA '98 : Proceedings of the 1998 ACM/SIGDA 6th International Symposium on Field Programmable Gate Arrays. Association for Computing Machinery (ACM), 1998. p. 77-84 (Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Circuit partitioning with complex resource constraints in FPGAs

AU - Liu, Huiqun

AU - Zhu, Kai

AU - Wong, D. F.

PY - 1998/2/22

Y1 - 1998/2/22

N2 - In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing capacity and diverse resource types in the new FPGA architectures. We propose a network flow based method to optimally check whether a circuit or a sub-circuit is feasible for a set of available heterogeneous resources. The feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementation. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g. logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g. Actel's ES6500 FPGA family).

AB - In this paper, we present an algorithm for circuit partitioning with complex resource constraints in large FPGAs. Traditional partitioning methods estimate the capacity of an FPGA device by counting the number of logic blocks, however this is not accurate with the increasing capacity and diverse resource types in the new FPGA architectures. We propose a network flow based method to optimally check whether a circuit or a sub-circuit is feasible for a set of available heterogeneous resources. The feasibility checking procedure is integrated in the FM-based algorithm for circuit partitioning. Incremental flow technique is employed for efficient implementation. Experimental results on the MCNC benchmark circuits show that our partitioning algorithm not only yields good results, but also is efficient. Our algorithm for partitioning with complex resource constraints is applicable for both multiple FPGA designs (e.g. logic emulation systems) and partitioning-based placement algorithms for a single large hierarchical FPGA (e.g. Actel's ES6500 FPGA family).

UR - http://www.scopus.com/inward/record.url?scp=0031641267&partnerID=8YFLogxK

U2 - 10.1145/275107.275122

DO - 10.1145/275107.275122

M3 - Conference proceeding

AN - SCOPUS:0031641267

SN - 9780897919784

T3 - Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA

SP - 77

EP - 84

BT - FPGA '98

PB - Association for Computing Machinery (ACM)

T2 - 6th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 1998

Y2 - 22 February 1998 through 25 February 1998

ER -

Liu H, Zhu K, Wong DF. Circuit partitioning with complex resource constraints in FPGAs. In FPGA '98 : Proceedings of the 1998 ACM/SIGDA 6th International Symposium on Field Programmable Gate Arrays. Association for Computing Machinery (ACM). 1998. p. 77-84. (Proceedings of the International Symposium on Field Programmable Gate Arrays, FPGA). doi: 10.1145/275107.275122

Circuit partitioning with complex resource constraints in FPGAs

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this