Algorithms for an FPGA switch module routing problem with application to global routing

Shashidhar Thakur, Yao Wen Chang, D. F. Wong, S. Muthukrishnan

Research output: Contribution to journalArticlepeer-review


We consider a switch module routing problem for symmetrical-array field-programmable gate arrays (FPGA's). This problem was first introduced in [21]. They used it to evaluate the routability properties of switch modules which they proposed. Only an approximation algorithm for the problem was proposed by them. We give an optimal algorithm for the problem based on integer linear programming (ILP). Experiments show that this formulation leads to fast and efficient solutions to practical-sized problems. We then propose a precomputation that eliminates the need to use ILP on-line. We also identify special cases of this problem that reduce to problems for whom efficient algorithms are known. Thus, the switch module routing problem can be solved in polynomial time for these special cases. Using our solution to the switch module routing problem, we propose a new metric to estimate the congestion in each switch module in the FPGA. We demonstrate the use of this metric in a global router. A comparison with a global router guided by the density of the routing channels shows that our metric leads to far superior global and detailed routing solutions.

Original languageEnglish (US)
Pages (from-to)32-46
Number of pages15
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number1
StatePublished - 1997
Externally publishedYes


  • Field-programmable gate array
  • Global routing

ASJC Scopus subject areas

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


Dive into the research topics of 'Algorithms for an FPGA switch module routing problem with application to global routing'. Together they form a unique fingerprint.

Cite this