Graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning

Huiqun Liu, D. F. Wong

Research output: Contribution to journalConference articlepeer-review


This paper presents an optimal algorithm to solve the schedule compression problem, which is an open problem proposed by Trimberger for time-multiplexed FPGA partitioning. Time-multiplexed FPGAs have the potential to dramatically improve logic density by time-sharing logic. Schedule compression is an important step in partitioning for time-multiplexed FPGAs [1,4,9,10] and can greatly influence the quality of the partitioning solution. We exactly solve the schedule compression problem by converting it to a constrained min-max path problem. We further extend our algorithm to minimize the communication cost during schedule compression. Experiments show that our optimal algorithm outperforms the existing heuristics and runs very efficiently.

Original languageEnglish (US)
Pages (from-to)400-405
Number of pages6
JournalIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
StatePublished - Dec 1 1999
Externally publishedYes
EventProceedings of the 1999 IEEE/ACM International Conference on Computer-Aided Design (ICCAD-99) - San Jose, CA, USA
Duration: Nov 7 1999Nov 11 1999

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Graph theoretic optimal algorithm for schedule compression in time-multiplexed FPGA partitioning'. Together they form a unique fingerprint.

Cite this