Network flow based circuit partitioning for time-multiplexed FPGAs

Huiqun Liu; D. F. Wong

doi:10.1145/288548.289077

Network flow based circuit partitioning for time-multiplexed FPGAs

Huiqun Liu, D. F. Wong

Office of the Provost

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

42 Citations (Scopus)

Abstract

Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for time-multiplexed FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them, and the widely used iterative improvement partitioning methods such as K&L, FM are no longer applicable. All previous approaches used list scheduling heuristics. In this paper, we present a network flow based algorithm for multi-way precedence constrained partitioning, which can handle the precedence constraints while minimizing the net-cut size. The experimental results on the MCNC benchmark circuits show that our algorithm out-performs list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi-way partitioning.

Original language	English
Title of host publication	ICCAD '98
Subtitle of host publication	Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design
Publisher	Association for Computing Machinery (ACM)
Pages	497-504
Number of pages	8
ISBN (Print)	9781581130089
DOIs	https://doi.org/10.1145/288548.289077
Publication status	Published - 8 Nov 1998
Event	1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998 - San Jose, United States Duration: 8 Nov 1998 → 12 Nov 1998 https://dl.acm.org/doi/proceedings/10.1145/288548 (Conference proceedings)

Publication series

Name	IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
ISSN (Print)	1092-3152
ISSN (Electronic)	1558-2434

Conference

Conference	1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998
Country/Territory	United States
City	San Jose
Period	8/11/98 → 12/11/98
Internet address	https://dl.acm.org/doi/proceedings/10.1145/288548 (Conference proceedings)

Access to Document

10.1145/288548.289077

Cite this

Liu, H., & Wong, D. F. (1998). Network flow based circuit partitioning for time-multiplexed FPGAs. In ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design (pp. 497-504). (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers). Association for Computing Machinery (ACM). https://doi.org/10.1145/288548.289077

@inproceedings{4ef37f68883642a1a70a3fe368f82936,

title = "Network flow based circuit partitioning for time-multiplexed FPGAs",

abstract = "Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for time-multiplexed FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them, and the widely used iterative improvement partitioning methods such as K&L, FM are no longer applicable. All previous approaches used list scheduling heuristics. In this paper, we present a network flow based algorithm for multi-way precedence constrained partitioning, which can handle the precedence constraints while minimizing the net-cut size. The experimental results on the MCNC benchmark circuits show that our algorithm out-performs list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi-way partitioning.",

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

note = "This work was partially supported by the Texas Adwnced Research Program under Grant No. 0036582SS and by a grant from the Intel Corporation.; 1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998 ; Conference date: 08-11-1998 Through 12-11-1998",

year = "1998",

month = nov,

day = "8",

doi = "10.1145/288548.289077",

language = "English",

isbn = "9781581130089",

series = "IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers",

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

pages = "497--504",

booktitle = "ICCAD '98",

address = "United States",

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

}

Liu, H & Wong, DF 1998, Network flow based circuit partitioning for time-multiplexed FPGAs. in ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design. IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, Association for Computing Machinery (ACM), pp. 497-504, 1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998, San Jose, California, United States, 8/11/98. https://doi.org/10.1145/288548.289077

Network flow based circuit partitioning for time-multiplexed FPGAs. / Liu, Huiqun; Wong, D. F.
ICCAD '98: Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design. Association for Computing Machinery (ACM), 1998. p. 497-504 (IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers).

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

TY - GEN

T1 - Network flow based circuit partitioning for time-multiplexed FPGAs

AU - Liu, Huiqun

AU - Wong, D. F.

N1 - This work was partially supported by the Texas Adwnced Research Program under Grant No. 0036582SS and by a grant from the Intel Corporation.

PY - 1998/11/8

Y1 - 1998/11/8

N2 - Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for time-multiplexed FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them, and the widely used iterative improvement partitioning methods such as K&L, FM are no longer applicable. All previous approaches used list scheduling heuristics. In this paper, we present a network flow based algorithm for multi-way precedence constrained partitioning, which can handle the precedence constraints while minimizing the net-cut size. The experimental results on the MCNC benchmark circuits show that our algorithm out-performs list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi-way partitioning.

AB - Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic, and have become an active research for reconfigurable computing. The partitioning problem for time-multiplexed FPGAs is different from the traditional partitioning problem in that the nodes have precedence constraints among them, and the widely used iterative improvement partitioning methods such as K&L, FM are no longer applicable. All previous approaches used list scheduling heuristics. In this paper, we present a network flow based algorithm for multi-way precedence constrained partitioning, which can handle the precedence constraints while minimizing the net-cut size. The experimental results on the MCNC benchmark circuits show that our algorithm out-performs list scheduling by a big margin, with an average improvement of over 50% for bipartitioning and 20% for multi-way partitioning.

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

U2 - 10.1145/288548.289077

DO - 10.1145/288548.289077

M3 - Conference proceeding

AN - SCOPUS:0032306328

SN - 9781581130089

T3 - IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers

SP - 497

EP - 504

BT - ICCAD '98

PB - Association for Computing Machinery (ACM)

T2 - 1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998

Y2 - 8 November 1998 through 12 November 1998

ER -

Network flow based circuit partitioning for time-multiplexed FPGAs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this