An Open-Source Fast Parallel Routing Approach for Commercial FPGAs

Xinshi Zang; Wenhao Lin; Shiju Lin; Jinwei Liu; Evangeline F.Y. Young

doi:10.1145/3649476.3658714

An Open-Source Fast Parallel Routing Approach for Commercial FPGAs

Xinshi Zang
, Wenhao Lin
, Shiju Lin
, Jinwei Liu
, Evangeline F.Y. Young

Department of Computer Science

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

5 Citations (Scopus)

Abstract

In the face of escalating complexity and size of contemporary FPGAs and circuits, routing emerges as a pivotal and time-intensive phase in FPGA compilation flows. In response to this challenge, we present an open-source parallel routing methodology designed to expedite routing procedures for commercial FPGAs. Our approach introduces a novel recursive partitioning ternary tree to augment the parallelism of multi-net routing. Additionally, we propose a hybrid updating strategy for congestion coefficients within the routing cost function to accelerate congestion resolution in negotiation-based routing algorithms. Evaluation on public benchmarks from the FPGA24 routing contest demonstrates the efficacy of our parallel router. It achieves a 2 × speedup compared to the academic serial router RWRoute. Furthermore, when compared to the industry-standard tool Vivado, our approach not only delivers a 2 × acceleration but also yields a notable 31% enhancement in critical-path wirelength.

Original language	English
Title of host publication	GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024
Editors	Inna Partin-Vaisband, Srinivas Katkoori, Lu Peng, Boris Vaisband, Tooraj Nikoubin
Publisher	Association for Computing Machinery (ACM)
Pages	164-169
Number of pages	6
ISBN (Electronic)	9798400706059
DOIs	https://doi.org/10.1145/3649476.3658714
Publication status	Published - 12 Jun 2024
Event	34th Great Lakes Symposium on VLSI 2024, GLSVLSI 2024 - Clearwater, United States Duration: 12 Jun 2024 → 14 Jun 2024 https://dl.acm.org/doi/proceedings/10.1145/3649476

Publication series

Name	Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI
Publisher	Association for Computing Machinery

Conference

Conference	34th Great Lakes Symposium on VLSI 2024, GLSVLSI 2024
Country/Territory	United States
City	Clearwater
Period	12/06/24 → 14/06/24
Internet address	https://dl.acm.org/doi/proceedings/10.1145/3649476

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1145/3649476.3658714

Cite this

Zang, X., Lin, W., Lin, S., Liu, J., & Young, E. F. Y. (2024). An Open-Source Fast Parallel Routing Approach for Commercial FPGAs. In I. Partin-Vaisband, S. Katkoori, L. Peng, B. Vaisband, & T. Nikoubin (Eds.), GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024 (pp. 164-169). (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI). Association for Computing Machinery (ACM). https://doi.org/10.1145/3649476.3658714

Zang, Xinshi ; Lin, Wenhao ; Lin, Shiju et al. / An Open-Source Fast Parallel Routing Approach for Commercial FPGAs. GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024. editor / Inna Partin-Vaisband ; Srinivas Katkoori ; Lu Peng ; Boris Vaisband ; Tooraj Nikoubin. Association for Computing Machinery (ACM), 2024. pp. 164-169 (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI).

@inproceedings{51ddfe479b5b4410b76eb893b4dfb5ea,

title = "An Open-Source Fast Parallel Routing Approach for Commercial FPGAs",

abstract = "In the face of escalating complexity and size of contemporary FPGAs and circuits, routing emerges as a pivotal and time-intensive phase in FPGA compilation flows. In response to this challenge, we present an open-source parallel routing methodology designed to expedite routing procedures for commercial FPGAs. Our approach introduces a novel recursive partitioning ternary tree to augment the parallelism of multi-net routing. Additionally, we propose a hybrid updating strategy for congestion coefficients within the routing cost function to accelerate congestion resolution in negotiation-based routing algorithms. Evaluation on public benchmarks from the FPGA24 routing contest demonstrates the efficacy of our parallel router. It achieves a 2 × speedup compared to the academic serial router RWRoute. Furthermore, when compared to the industry-standard tool Vivado, our approach not only delivers a 2 × acceleration but also yields a notable 31\% enhancement in critical-path wirelength.",

author = "Xinshi Zang and Wenhao Lin and Shiju Lin and Jinwei Liu and Young, \{Evangeline F.Y.\}",

note = "The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK14218422). Publisher Copyright: {\textcopyright} 2024 Copyright held by the owner/author(s).; 34th Great Lakes Symposium on VLSI 2024, GLSVLSI 2024 ; Conference date: 12-06-2024 Through 14-06-2024",

year = "2024",

month = jun,

day = "12",

doi = "10.1145/3649476.3658714",

language = "English",

series = "Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI",

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

pages = "164--169",

editor = "Inna Partin-Vaisband and Srinivas Katkoori and Lu Peng and Boris Vaisband and Tooraj Nikoubin",

booktitle = "GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/3649476",

}

Zang, X, Lin, W, Lin, S, Liu, J & Young, EFY 2024, An Open-Source Fast Parallel Routing Approach for Commercial FPGAs. in I Partin-Vaisband, S Katkoori, L Peng, B Vaisband & T Nikoubin (eds), GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024. Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI, Association for Computing Machinery (ACM), pp. 164-169, 34th Great Lakes Symposium on VLSI 2024, GLSVLSI 2024, Clearwater, United States, 12/06/24. https://doi.org/10.1145/3649476.3658714

An Open-Source Fast Parallel Routing Approach for Commercial FPGAs. / Zang, Xinshi; Lin, Wenhao; Lin, Shiju et al.
GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024. ed. / Inna Partin-Vaisband; Srinivas Katkoori; Lu Peng; Boris Vaisband; Tooraj Nikoubin. Association for Computing Machinery (ACM), 2024. p. 164-169 (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI).

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

TY - GEN

T1 - An Open-Source Fast Parallel Routing Approach for Commercial FPGAs

AU - Zang, Xinshi

AU - Lin, Wenhao

AU - Lin, Shiju

AU - Liu, Jinwei

AU - Young, Evangeline F.Y.

N1 - The work described in this paper was partially supported by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CUHK14218422). Publisher Copyright: © 2024 Copyright held by the owner/author(s).

PY - 2024/6/12

Y1 - 2024/6/12

N2 - In the face of escalating complexity and size of contemporary FPGAs and circuits, routing emerges as a pivotal and time-intensive phase in FPGA compilation flows. In response to this challenge, we present an open-source parallel routing methodology designed to expedite routing procedures for commercial FPGAs. Our approach introduces a novel recursive partitioning ternary tree to augment the parallelism of multi-net routing. Additionally, we propose a hybrid updating strategy for congestion coefficients within the routing cost function to accelerate congestion resolution in negotiation-based routing algorithms. Evaluation on public benchmarks from the FPGA24 routing contest demonstrates the efficacy of our parallel router. It achieves a 2 × speedup compared to the academic serial router RWRoute. Furthermore, when compared to the industry-standard tool Vivado, our approach not only delivers a 2 × acceleration but also yields a notable 31% enhancement in critical-path wirelength.

AB - In the face of escalating complexity and size of contemporary FPGAs and circuits, routing emerges as a pivotal and time-intensive phase in FPGA compilation flows. In response to this challenge, we present an open-source parallel routing methodology designed to expedite routing procedures for commercial FPGAs. Our approach introduces a novel recursive partitioning ternary tree to augment the parallelism of multi-net routing. Additionally, we propose a hybrid updating strategy for congestion coefficients within the routing cost function to accelerate congestion resolution in negotiation-based routing algorithms. Evaluation on public benchmarks from the FPGA24 routing contest demonstrates the efficacy of our parallel router. It achieves a 2 × speedup compared to the academic serial router RWRoute. Furthermore, when compared to the industry-standard tool Vivado, our approach not only delivers a 2 × acceleration but also yields a notable 31% enhancement in critical-path wirelength.

UR - https://www.scopus.com/pages/publications/85197906728

U2 - 10.1145/3649476.3658714

DO - 10.1145/3649476.3658714

M3 - Conference proceeding

AN - SCOPUS:85197906728

T3 - Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI

SP - 164

EP - 169

BT - GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024

A2 - Partin-Vaisband, Inna

A2 - Katkoori, Srinivas

A2 - Peng, Lu

A2 - Vaisband, Boris

A2 - Nikoubin, Tooraj

PB - Association for Computing Machinery (ACM)

T2 - 34th Great Lakes Symposium on VLSI 2024, GLSVLSI 2024

Y2 - 12 June 2024 through 14 June 2024

ER -

Zang X, Lin W, Lin S, Liu J, Young EFY. An Open-Source Fast Parallel Routing Approach for Commercial FPGAs. In Partin-Vaisband I, Katkoori S, Peng L, Vaisband B, Nikoubin T, editors, GLSVLSI 2024 - Proceedings of the Great Lakes Symposium on VLSI 2024. Association for Computing Machinery (ACM). 2024. p. 164-169. (Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI). doi: 10.1145/3649476.3658714

An Open-Source Fast Parallel Routing Approach for Commercial FPGAs

Abstract

Publication series

Conference

UN SDGs

Access to Document

Other files and links

Fingerprint

Cite this