Network flow based circuit partitioning for time-multiplexed FPGAs

Huiqun Liu, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


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 (US)
Pages (from-to)497-504
Number of pages8
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - 1998
Externally publishedYes
EventProceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design, ICCAD - San Jose, CA, USA
Duration: Nov 8 1998Nov 12 1998

ASJC 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