Graph matching-based algorithms for FPGA segmentation design

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

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

7 Citations (Scopus)


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
Title of host publicationICCAD '98
Subtitle of host publicationProceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design
Place of Publication9781581130089
PublisherAssociation for Computing Machinery (ACM)
Number of pages6
Publication statusPublished - 8 Nov 1998
Event1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998 - San Jose, United States
Duration: 8 Nov 199812 Nov 1998 (Conference proceedings)

Publication series

NameIEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers
ISSN (Print)1092-3152
ISSN (Electronic)1558-2434


Conference1998 IEEE International Conference on Computer-Aided Design, ICCAD 1998
Country/TerritoryUnited States
CitySan Jose
Internet address

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