Algorithms for a switch module routing problem

Shashidhar Thakur, D. F. Wong, S. Muthukrishnan

Research output: Contribution to conferencePaper

Abstract

We consider a switch module routing problem for symmetric array FPGAs. The work is motivated by two applications. The first is that of efficiently evaluating switch module designs. The second is that of evaluating the routability of global routing paths for a placement on this architecture. Only an approximate algorithm was previously known for this problem. In this paper, we present an optimal algorithm for the problem based on integer linear programming. Experimental results consistently show that our algorithm is very efficient for practical sized switch modules. We further improve this technique, by doing some pre-processing on the given switch module. We also identify interesting special cases of the problem which can be solved optimally in polynomial time.

Original languageEnglish (US)
Pages265-270
Number of pages6
StatePublished - Dec 1 1994
Externally publishedYes
EventProceedings of the 1994 European Design Automation Conference - Grenoble, Fr
Duration: Sep 19 1994Sep 23 1994

Other

OtherProceedings of the 1994 European Design Automation Conference
CityGrenoble, Fr
Period9/19/949/23/94

    Fingerprint

ASJC Scopus subject areas

  • Control and Systems Engineering

Cite this

Thakur, S., Wong, D. F., & Muthukrishnan, S. (1994). Algorithms for a switch module routing problem. 265-270. Paper presented at Proceedings of the 1994 European Design Automation Conference, Grenoble, Fr, .