Graph matching-based algorithms for array-based FPGA segmentation design and routing

Jai Ming Lin, Song Ra Pan, Yao Wen Chang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

Architecture and CAD are closely related issues in FPGA design. Routing architecture design optimizes routability and facilitates router development; on the other hand, router design considers the specific properties of routing architectures to optimize the performance of the router. In this paper, we propose effective and efficient unified matching-based algorithms for array-based FPGA routing and segmentation design. For the segmentation design, we consider the similarity of input routing instances and formulate a net-matching problem to construct the optimal segmentation architecture. For the router design, we present a matching-based timing-driven routing algorithm which can consider a versatile set of routing segments. Experimental results show that our designed segmentations significantly outperform those used in commercially available FPGAs. For example, our designed segmentations achieve, on average, 14.6% and 19.7% improvements in routability, compared with those used in the Lucent Technologies ORCA 2C-series and the Xilinx XC4000E-series FPGAs, respectively.

Original languageEnglish
Title of host publicationProceedings of the ASP-DAC 2003 Asia and South Pacific Design Automation Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages851-854
Number of pages4
ISBN (Electronic)0780376595
DOIs
Publication statusPublished - 2003
EventAsia and South Pacific Design Automation Conference, ASP-DAC 2003 - Kitakyushu, Japan
Duration: 2003 Jan 212003 Jan 24

Publication series

NameProceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC
Volume2003-January

Other

OtherAsia and South Pacific Design Automation Conference, ASP-DAC 2003
CountryJapan
CityKitakyushu
Period03-01-2103-01-24

All Science Journal Classification (ASJC) codes

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

Fingerprint Dive into the research topics of 'Graph matching-based algorithms for array-based FPGA segmentation design and routing'. Together they form a unique fingerprint.

Cite this