Register binding and port assignment for multiplexer optimization

Deming Chen, Jason Cong

Research output: Contribution to conferencePaperpeer-review


Data path connection elements, such as multiplexers, consume a significant amount of area on a VLSI chip, especially for FPGA designs. Multiplexer optimization is a difficult problem because both register binding and port assignment to reduce total multiplexer connectivity during high-level synthesis are NP-complete problems. In this paper, we first formulate a k-cofamily-based register binding algorithm targeting the multiplexer optimization problem. We then further reduce the multiplexer width through an efficient port assignment algorithm. Experimental results show that we are 44% better overall than the left-edge register binding algorithm on the total usage of multiplexer inputs and 7% better than a bipartite graph-based algorithm. For large designs, we are able to achieve significantly better results consistently. After technology mapping, placement and routing for an FPGA architecture, it shows considerably positive impacts on chip area, delay and power consumption.

Original languageEnglish (US)
Number of pages6
StatePublished - 2004
Externally publishedYes
EventProceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004 - Yokohama, Japan
Duration: Jan 27 2004Jan 30 2004


OtherProceedings of the ASP - DAC 2004 Asia and South Pacific Design Automation Conference - 2004

ASJC Scopus subject areas

  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering


Dive into the research topics of 'Register binding and port assignment for multiplexer optimization'. Together they form a unique fingerprint.

Cite this