Algorithms for a switch module routing problem

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

Algorithms for a switch module routing problem

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

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

1 Citation (Scopus)

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 language	English
Title of host publication	EURO-DAC '94: Proceedings of the Conference on European Design Automation
Publisher	Association for Computing Machinery (ACM)
Pages	265-270
Number of pages	6
ISBN (Print)	9780897916851
Publication status	Published - Sept 1994
Event	1994 European Design Automation Conference, EDAC 1994 - Grenoble, France Duration: 19 Sept 1994 → 23 Sept 1994 https://dl.acm.org/doi/proceedings/10.5555/198174

Publication series

Name	Proceedings of the Conference on European Design Automation

Conference

Conference	1994 European Design Automation Conference, EDAC 1994
Country/Territory	France
City	Grenoble
Period	19/09/94 → 23/09/94
Internet address	https://dl.acm.org/doi/proceedings/10.5555/198174

Scopus Subject Areas

Control and Systems Engineering

Access to Document

https://dl.acm.org/doi/10.5555/198174.198259

Cite this

@inproceedings{143366c7e385458cb674f7515aafa9b4,

title = "Algorithms for a switch module routing problem",

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.",

author = "Shashidhar Thakur and Wong, {D. F.} and S. Muthukrishnan",

note = "This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by a DAC Design Automation Scholarship, and by a grant from the AT&T Bell Laboratories.; 1994 European Design Automation Conference, EDAC 1994 ; Conference date: 19-09-1994 Through 23-09-1994",

year = "1994",

month = sep,

language = "English",

isbn = "9780897916851",

series = "Proceedings of the Conference on European Design Automation",

publisher = "Association for Computing Machinery (ACM)",

pages = "265--270",

booktitle = "EURO-DAC '94: Proceedings of the Conference on European Design Automation",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.5555/198174",

}

Thakur, S, Wong, DF & Muthukrishnan, S 1994, Algorithms for a switch module routing problem. in EURO-DAC '94: Proceedings of the Conference on European Design Automation. Proceedings of the Conference on European Design Automation, Association for Computing Machinery (ACM), pp. 265-270, 1994 European Design Automation Conference, EDAC 1994, Grenoble, France, 19/09/94. <https://dl.acm.org/doi/10.5555/198174.198259>

Algorithms for a switch module routing problem. / Thakur, Shashidhar; Wong, D. F.; Muthukrishnan, S.
EURO-DAC '94: Proceedings of the Conference on European Design Automation. Association for Computing Machinery (ACM), 1994. p. 265-270 (Proceedings of the Conference on European Design Automation).

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

TY - GEN

T1 - Algorithms for a switch module routing problem

AU - Thakur, Shashidhar

AU - Wong, D. F.

AU - Muthukrishnan, S.

N1 - This work was partially supported by the Texas Advanced Research Program under Grant No. 003658459, by a DAC Design Automation Scholarship, and by a grant from the AT&T Bell Laboratories.

PY - 1994/9

Y1 - 1994/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0028713843&partnerID=8YFLogxK

M3 - Conference proceeding

AN - SCOPUS:0028713843

SN - 9780897916851

T3 - Proceedings of the Conference on European Design Automation

SP - 265

EP - 270

BT - EURO-DAC '94: Proceedings of the Conference on European Design Automation

PB - Association for Computing Machinery (ACM)

T2 - 1994 European Design Automation Conference, EDAC 1994

Y2 - 19 September 1994 through 23 September 1994

ER -

Algorithms for a switch module routing problem

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this