Wire type assignment for FPGA routing

Seokjin Lee; Hua Xiang; D. F. Wong; Richard Y. Sun

doi:10.1145/611817.611828

Wire type assignment for FPGA routing

Seokjin Lee, Hua Xiang, D. F. Wong, Richard Y. Sun

Office of the Provost

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

5 Citations (Scopus)

Abstract

The routing channels of an FPGA consist of wire segments of various types providing the tradeoff between performance and routability. In the routing architectures of recently developed FPGAs (e.g., Virtex-II), there are more versatile wire types and richer connections between them than those of the older generations of FPGAs (e.g. XC4000). To fully exploit the potential of the new routing architectures, it is beneficial to perform wire type assignment for all channels as an intermediate stage between global routing and detailed routing. In this paper, we present a wire-type assignment algorithm that is based on iteratively applying min-cost maxflow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and delay cost. We use the routing architecture of the Virtex-II FPGAs from Xilinx as a target architecture in our experiments. Experimental results show that our algorithm outperforms the traditional sequential net-by-net approach.

Original language	English
Title of host publication	FPGA '03
Subtitle of host publication	Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays
Place of Publication	United States
Publisher	Association for Computing Machinery (ACM)
Pages	61-67
Number of pages	7
ISBN (Print)	9781581136517
DOIs	https://doi.org/10.1145/611817.611828
Publication status	Published - Feb 2003
Event	11th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2003 - Monterey Beach Hotel, Monterey, United States Duration: 23 Feb 2003 → 25 Feb 2003 https://www.isfpga.org/past/fpga2003/ (Conference website) https://www.isfpga.org/past/fpga2003/AdvProg.pdf (Conference programme) https://dl.acm.org/doi/proceedings/10.1145/611817 (Conference proceedings)

Publication series

Name	Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA

Symposium

Symposium	11th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2003
Country/Territory	United States
City	Monterey
Period	23/02/03 → 25/02/03
Internet address	https://www.isfpga.org/past/fpga2003/ (Conference website) https://www.isfpga.org/past/fpga2003/AdvProg.pdf (Conference programme) https://dl.acm.org/doi/proceedings/10.1145/611817 (Conference proceedings)

Scopus Subject Areas

Computer Science(all)

User-Defined Keywords

FPGA routing
Min-cost flow algorithm
Wire type assignment

Access to Document

10.1145/611817.611828

Cite this

Lee, S., Xiang, H., Wong, D. F., & Sun, R. Y. (2003). Wire type assignment for FPGA routing. In FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays (pp. 61-67). (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA). Association for Computing Machinery (ACM). https://doi.org/10.1145/611817.611828

Lee, Seokjin ; Xiang, Hua ; Wong, D. F. et al. / Wire type assignment for FPGA routing. FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays. United States : Association for Computing Machinery (ACM), 2003. pp. 61-67 (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA).

@inproceedings{e882f923be2440fc95a11ff685af929b,

title = "Wire type assignment for FPGA routing",

abstract = "The routing channels of an FPGA consist of wire segments of various types providing the tradeoff between performance and routability. In the routing architectures of recently developed FPGAs (e.g., Virtex-II), there are more versatile wire types and richer connections between them than those of the older generations of FPGAs (e.g. XC4000). To fully exploit the potential of the new routing architectures, it is beneficial to perform wire type assignment for all channels as an intermediate stage between global routing and detailed routing. In this paper, we present a wire-type assignment algorithm that is based on iteratively applying min-cost maxflow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and delay cost. We use the routing architecture of the Virtex-II FPGAs from Xilinx as a target architecture in our experiments. Experimental results show that our algorithm outperforms the traditional sequential net-by-net approach.",

keywords = "FPGA routing, Min-cost flow algorithm, Wire type assignment",

author = "Seokjin Lee and Hua Xiang and Wong, {D. F.} and Sun, {Richard Y.}",

note = "Publisher copyright: {\textcopyright} 2003 ACM; 11th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2003 ; Conference date: 23-02-2003 Through 25-02-2003",

year = "2003",

month = feb,

doi = "10.1145/611817.611828",

language = "English",

isbn = "9781581136517",

series = "Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA",

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

pages = "61--67",

booktitle = "FPGA '03",

address = "United States",

url = "https://www.isfpga.org/past/fpga2003/, https://www.isfpga.org/past/fpga2003/AdvProg.pdf, https://dl.acm.org/doi/proceedings/10.1145/611817",

}

Lee, S, Xiang, H, Wong, DF & Sun, RY 2003, Wire type assignment for FPGA routing. in FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays. Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA, Association for Computing Machinery (ACM), United States, pp. 61-67, 11th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2003, Monterey, California, United States, 23/02/03. https://doi.org/10.1145/611817.611828

Wire type assignment for FPGA routing. / Lee, Seokjin; Xiang, Hua; Wong, D. F. et al.
FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays. United States: Association for Computing Machinery (ACM), 2003. p. 61-67 (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA).

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

TY - GEN

T1 - Wire type assignment for FPGA routing

AU - Lee, Seokjin

AU - Xiang, Hua

AU - Wong, D. F.

AU - Sun, Richard Y.

PY - 2003/2

Y1 - 2003/2

N2 - The routing channels of an FPGA consist of wire segments of various types providing the tradeoff between performance and routability. In the routing architectures of recently developed FPGAs (e.g., Virtex-II), there are more versatile wire types and richer connections between them than those of the older generations of FPGAs (e.g. XC4000). To fully exploit the potential of the new routing architectures, it is beneficial to perform wire type assignment for all channels as an intermediate stage between global routing and detailed routing. In this paper, we present a wire-type assignment algorithm that is based on iteratively applying min-cost maxflow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and delay cost. We use the routing architecture of the Virtex-II FPGAs from Xilinx as a target architecture in our experiments. Experimental results show that our algorithm outperforms the traditional sequential net-by-net approach.

AB - The routing channels of an FPGA consist of wire segments of various types providing the tradeoff between performance and routability. In the routing architectures of recently developed FPGAs (e.g., Virtex-II), there are more versatile wire types and richer connections between them than those of the older generations of FPGAs (e.g. XC4000). To fully exploit the potential of the new routing architectures, it is beneficial to perform wire type assignment for all channels as an intermediate stage between global routing and detailed routing. In this paper, we present a wire-type assignment algorithm that is based on iteratively applying min-cost maxflow technique to simultaneously route many nets. At each stage of the network flow computation, we have guaranteed optimal result in terms of routability and delay cost. We use the routing architecture of the Virtex-II FPGAs from Xilinx as a target architecture in our experiments. Experimental results show that our algorithm outperforms the traditional sequential net-by-net approach.

KW - FPGA routing

KW - Min-cost flow algorithm

KW - Wire type assignment

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

U2 - 10.1145/611817.611828

DO - 10.1145/611817.611828

M3 - Conference proceeding

AN - SCOPUS:0037673253

SN - 9781581136517

T3 - Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA

SP - 61

EP - 67

BT - FPGA '03

PB - Association for Computing Machinery (ACM)

CY - United States

T2 - 11th ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA 2003

Y2 - 23 February 2003 through 25 February 2003

ER -

Lee S, Xiang H, Wong DF, Sun RY. Wire type assignment for FPGA routing. In FPGA '03: Proceedings of the 2003 ACM/SIGDA eleventh international symposium on Field programmable gate arrays. United States: Association for Computing Machinery (ACM). 2003. p. 61-67. (Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, FPGA). doi: 10.1145/611817.611828

Wire type assignment for FPGA routing

Abstract

Publication series

Symposium

Scopus Subject Areas

User-Defined Keywords

Access to Document

Other files and links

Fingerprint

Cite this