Track placement: Orchestrating routing structures to maximize routability

Katherine Compton; Scott Hauck

doi:10.1007/978-3-540-45234-8_13

Track placement: Orchestrating routing structures to maximize routability

Katherine Compton^*, Scott Hauck

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Chapter

2 Scopus citations

Abstract

The design of a routing channel for an FPGA is a complex process requiring a careful balance of flexibility with silicon efficiency. With a growing move towards embedding FPGAs into SoC designs, and the new opportunity to automatically generate FPGA architectures, this problem is even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks between wires on the tracks. This paper focuses on the last problem, the placement of breaks in tracks to maximize overall flexibility. Our optimal algorithm for track placement finds a best solution provided the problem meets a number of restrictions. Our relaxed algorithm is without restrictions, and finds solutions on average within 1.13% of optimal.

Original language	English (US)
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Peter Y. K. Cheung, George A. Constantinides, Jose T. de Sousa
Publisher	Springer Verlag
Pages	121-130
Number of pages	10
ISBN (Electronic)	3540408223, 9783540408222
DOIs	https://doi.org/10.1007/978-3-540-45234-8_13
State	Published - 2003

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2778
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-540-45234-8_13

Cite this

Compton, K., & Hauck, S. (2003). Track placement: Orchestrating routing structures to maximize routability. In P. Y. K. Cheung, G. A. Constantinides, & J. T. de Sousa (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 121-130). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2778). Springer Verlag. https://doi.org/10.1007/978-3-540-45234-8_13

Compton, Katherine ; Hauck, Scott. / Track placement : Orchestrating routing structures to maximize routability. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Peter Y. K. Cheung ; George A. Constantinides ; Jose T. de Sousa. Springer Verlag, 2003. pp. 121-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{05a297686e644198ac4ebc804173e5e3,

title = "Track placement: Orchestrating routing structures to maximize routability",

abstract = "The design of a routing channel for an FPGA is a complex process requiring a careful balance of flexibility with silicon efficiency. With a growing move towards embedding FPGAs into SoC designs, and the new opportunity to automatically generate FPGA architectures, this problem is even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks between wires on the tracks. This paper focuses on the last problem, the placement of breaks in tracks to maximize overall flexibility. Our optimal algorithm for track placement finds a best solution provided the problem meets a number of restrictions. Our relaxed algorithm is without restrictions, and finds solutions on average within 1.13% of optimal.",

author = "Katherine Compton and Scott Hauck",

year = "2003",

doi = "10.1007/978-3-540-45234-8_13",

language = "English (US)",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "121--130",

editor = "Cheung, {Peter Y. K.} and Constantinides, {George A.} and {de Sousa}, {Jose T.}",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

Compton, K & Hauck, S 2003, Track placement: Orchestrating routing structures to maximize routability. in PYK Cheung, GA Constantinides & JT de Sousa (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2778, Springer Verlag, pp. 121-130. https://doi.org/10.1007/978-3-540-45234-8_13

Track placement: Orchestrating routing structures to maximize routability. / Compton, Katherine; Hauck, Scott.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Peter Y. K. Cheung; George A. Constantinides; Jose T. de Sousa. Springer Verlag, 2003. p. 121-130 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2778).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

TY - CHAP

T1 - Track placement

T2 - Orchestrating routing structures to maximize routability

AU - Compton, Katherine

AU - Hauck, Scott

PY - 2003

Y1 - 2003

N2 - The design of a routing channel for an FPGA is a complex process requiring a careful balance of flexibility with silicon efficiency. With a growing move towards embedding FPGAs into SoC designs, and the new opportunity to automatically generate FPGA architectures, this problem is even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks between wires on the tracks. This paper focuses on the last problem, the placement of breaks in tracks to maximize overall flexibility. Our optimal algorithm for track placement finds a best solution provided the problem meets a number of restrictions. Our relaxed algorithm is without restrictions, and finds solutions on average within 1.13% of optimal.

AB - The design of a routing channel for an FPGA is a complex process requiring a careful balance of flexibility with silicon efficiency. With a growing move towards embedding FPGAs into SoC designs, and the new opportunity to automatically generate FPGA architectures, this problem is even more critical. The design of a routing channel requires determining the number of routing tracks, the length of the wires in those tracks, and the positioning of the breaks between wires on the tracks. This paper focuses on the last problem, the placement of breaks in tracks to maximize overall flexibility. Our optimal algorithm for track placement finds a best solution provided the problem meets a number of restrictions. Our relaxed algorithm is without restrictions, and finds solutions on average within 1.13% of optimal.

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

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

U2 - 10.1007/978-3-540-45234-8_13

DO - 10.1007/978-3-540-45234-8_13

M3 - Chapter

AN - SCOPUS:35248824686

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 130

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

A2 - Cheung, Peter Y. K.

A2 - Constantinides, George A.

A2 - de Sousa, Jose T.

PB - Springer Verlag

ER -

Compton K, Hauck S. Track placement: Orchestrating routing structures to maximize routability. In Cheung PYK, Constantinides GA, de Sousa JT, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 121-130. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-45234-8_13

Track placement: Orchestrating routing structures to maximize routability

Abstract

Publication series

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this