New global routing algorithm for FPGAs

Yao Wen Chang, Shashidhar Thakur, Kai Zhu, Martin D F Wong

Research output: Contribution to journalArticle

Abstract

As in traditional ASIC technologies, FPGA routing usually consists of two steps: global routing and detailed routing. Unlike existing FPGA detailed routers, which can take full advantage of the special structures of the programmable routing resources, FPGA global routing algorithms still greatly resemble their counter-parts in the traditional ASIC technologies. In particular, the routing congestion information of a switch block essentially is still measured by the numbers of available rows and columns in the switch block. Since the internal architecture of a switch block decides what can route through the block, the traditional measure of routing capacity is no longer accurate. In this paper, we present an accurate measure of switch block routing capacity. Our new measure considers the exact positions of the switches inside a switch block. Experiments with a global router based on these ideas show an average improvement of 38% in the channel width required to route some benchmark circuits using a popular switch block, compared with an algorithm based on the traditional methods for congestion control.

Original languageEnglish (US)
Pages (from-to)356-361
Number of pages6
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
StatePublished - 1994
Externally publishedYes

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Computer Science Applications
  • Hardware and Architecture
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'New global routing algorithm for FPGAs'. Together they form a unique fingerprint.

  • Cite this