Graph matching-based algorithms for FPGA segmentation design

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

Research output: Contribution to journalConference articlepeer-review


Process technology advances will soon make the one-million gate FPGA a reality. A key issue that needs to be solved for the large-scale FPGAs to realize their full potential lies in the design of their segmentation architectures. One-dimensional segmentation designs have been studied to some degree in much of the literature; most of the previously proposed methods are based on stochastic 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 net matching problem and present a polynomial-time optimal algorithm to solve the problem. Based on the solution to the problem, we develop an effective and efficient matching-based algorithm for FPGA segmentation designs. Experimental results show that our method significantly outperforms previous work. For example, our method achieves averages of 18.2% and 8.9% improvements in routability, compared with the work in [14] and the most recent work in [7], respectively. More importantly, our approaches are very flexible and can readily extend to higher-order segmentation designs (e.g., two- or three-dimensional segmentation design, etc), which are crucial to the design of large-scale FPGAs.

Original languageEnglish (US)
Pages (from-to)34-39
Number of pages6
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 'Graph matching-based algorithms for FPGA segmentation design'. Together they form a unique fingerprint.

Cite this