Network flow based circuit partitioning for time-multiplexed FPGAs

Huiqun Liu, D. F. Wong

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

42 Citations (Scopus)


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 languageEnglish
Title of host publicationICCAD '98
Subtitle of host publicationProceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design
PublisherAssociation for Computing Machinery (ACM)
Number of pages8
ISBN (Print)9781581130089
Publication statusPublished - 8 Nov 1998
Event1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998 - San Jose, United States
Duration: 8 Nov 199812 Nov 1998 (Conference proceedings)

Publication series

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


Conference1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Network flow based circuit partitioning for time-multiplexed FPGAs'. Together they form a unique fingerprint.

Cite this