Matching-based algorithm for FPGA channel segmentation design

Yao Wen Chang, Jai Ming Lin, M. D. F. Wong

Research output: Contribution to journalJournal articlepeer-review

6 Citations (Scopus)


Process technology advances have made multimillion gate field programmable gate arrays (FPGAs) a reality. A key issue that needs to be solved in order for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. Channel segmentation designs have been studied to some degree in much of the literature; the previous methods are based on experimental studies, stochastic models, or analytical analysis. In this paper, we address a new direction for studying segmentation architectures. Our method is based on graph-theoretic formulation. We first formulate a problem of finding the optimal segmentation architecture for two input routing instances and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient multi-level matching-based algorithm for general channel segmentation designs. Experimental results show that our method significantly outperforms the previous work. For example, our method achieves average improvements of 18.2% and 8.9% in routability in comparison with other work.

Original languageEnglish
Pages (from-to)784-791
Number of pages8
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number6
Publication statusPublished - Jun 2001

Scopus Subject Areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

User-Defined Keywords

  • Detailed routing
  • Interconnect
  • Layout
  • Physical design
  • Routing


Dive into the research topics of 'Matching-based algorithm for FPGA channel segmentation design'. Together they form a unique fingerprint.

Cite this