A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms

Umair F. Siddiqi; Gary Grewal; Shawki Areibi

doi:10.1109/VLSI-SoC57769.2023.10321904

A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms

Umair F. Siddiqi^*
, Gary Grewal
, Shawki Areibi

^*Corresponding author for this work

Office of Industry Collaboration

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

Routing is a time-consuming task in the FPGA design flow, and its task is to build non-overlapping routing trees for all nets. PathFinder is a popular routing algorithm, and it is implemented in the versatile-place-and-route (VPR) tool. The latest version of PathFinder, implemented in VPR 8.0, employs incremental routing in which it rip-up and re-route (RnR) only those branches of the routing trees that have a congested node or their delay has degraded significantly in the last iterations. The initial iterations have a very high workload (i.e., the number of branches to route), and the later ones have fewer branches to build. We propose a parallel-sequential hybrid router for PathFinder with incremental routing that applies deterministic parallel routing to a window of initial iterations having a high routing workload and sequential routing to the remaining iterations. It also uses an intelligent approach to select nets for sequential and parallel routing. Experiments conducted using Titan benchmarks show that it can improve the runtime of PathFinder by upto 32% with no significant degradation in solution quality.

Original language	English
Title of host publication	2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration, VLSI-SoC 2023
Publisher	IEEE Computer Society
ISBN (Electronic)	9798350325997
DOIs	https://doi.org/10.1109/VLSI-SoC57769.2023.10321904
State	Published - 2023
Event	31st IFIP/IEEE International Conference on Very Large Scale Integration, VLSI-SoC 2023 - Dubai, United Arab Emirates Duration: 16 Oct 2023 → 18 Oct 2023

Publication series

Name	IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC
ISSN (Print)	2324-8432
ISSN (Electronic)	2324-8440

Conference

Conference	31st IFIP/IEEE International Conference on Very Large Scale Integration, VLSI-SoC 2023
Country/Territory	United Arab Emirates
City	Dubai
Period	16/10/23 → 18/10/23

Bibliographical note

Publisher Copyright:
© 2023 IEEE.

UN SDGs

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

SDG 9 Industry, Innovation, and Infrastructure

Keywords

FPGA Routing
Field programmable gate arrays
Intelligent manufacturing
PathFinder

ASJC Scopus subject areas

Hardware and Architecture
Software
Electrical and Electronic Engineering

Access to Document

10.1109/VLSI-SoC57769.2023.10321904

Cite this

Siddiqi, U. F., Grewal, G., & Areibi, S. (2023). A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms. In 2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration, VLSI-SoC 2023 (IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC). IEEE Computer Society. https://doi.org/10.1109/VLSI-SoC57769.2023.10321904

@inproceedings{0d9c22739a31470c8f34925dd4831171,

title = "A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms",

abstract = "Routing is a time-consuming task in the FPGA design flow, and its task is to build non-overlapping routing trees for all nets. PathFinder is a popular routing algorithm, and it is implemented in the versatile-place-and-route (VPR) tool. The latest version of PathFinder, implemented in VPR 8.0, employs incremental routing in which it rip-up and re-route (RnR) only those branches of the routing trees that have a congested node or their delay has degraded significantly in the last iterations. The initial iterations have a very high workload (i.e., the number of branches to route), and the later ones have fewer branches to build. We propose a parallel-sequential hybrid router for PathFinder with incremental routing that applies deterministic parallel routing to a window of initial iterations having a high routing workload and sequential routing to the remaining iterations. It also uses an intelligent approach to select nets for sequential and parallel routing. Experiments conducted using Titan benchmarks show that it can improve the runtime of PathFinder by upto 32\% with no significant degradation in solution quality.",

keywords = "FPGA Routing, Field programmable gate arrays, Intelligent manufacturing, PathFinder",

author = "Siddiqi, \{Umair F.\} and Gary Grewal and Shawki Areibi",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 31st IFIP/IEEE International Conference on Very Large Scale Integration, VLSI-SoC 2023 ; Conference date: 16-10-2023 Through 18-10-2023",

year = "2023",

doi = "10.1109/VLSI-SoC57769.2023.10321904",

language = "English",

series = "IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC",

publisher = "IEEE Computer Society",

booktitle = "2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration, VLSI-SoC 2023",

address = "United States",

}

Siddiqi, UF, Grewal, G & Areibi, S 2023, A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms. in 2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration, VLSI-SoC 2023. IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC, IEEE Computer Society, 31st IFIP/IEEE International Conference on Very Large Scale Integration, VLSI-SoC 2023, Dubai, United Arab Emirates, 16/10/23. https://doi.org/10.1109/VLSI-SoC57769.2023.10321904

A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms. / Siddiqi, Umair F.; Grewal, Gary; Areibi, Shawki.
2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration, VLSI-SoC 2023. IEEE Computer Society, 2023. (IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms

AU - Siddiqi, Umair F.

AU - Grewal, Gary

AU - Areibi, Shawki

PY - 2023

Y1 - 2023

N2 - Routing is a time-consuming task in the FPGA design flow, and its task is to build non-overlapping routing trees for all nets. PathFinder is a popular routing algorithm, and it is implemented in the versatile-place-and-route (VPR) tool. The latest version of PathFinder, implemented in VPR 8.0, employs incremental routing in which it rip-up and re-route (RnR) only those branches of the routing trees that have a congested node or their delay has degraded significantly in the last iterations. The initial iterations have a very high workload (i.e., the number of branches to route), and the later ones have fewer branches to build. We propose a parallel-sequential hybrid router for PathFinder with incremental routing that applies deterministic parallel routing to a window of initial iterations having a high routing workload and sequential routing to the remaining iterations. It also uses an intelligent approach to select nets for sequential and parallel routing. Experiments conducted using Titan benchmarks show that it can improve the runtime of PathFinder by upto 32% with no significant degradation in solution quality.

AB - Routing is a time-consuming task in the FPGA design flow, and its task is to build non-overlapping routing trees for all nets. PathFinder is a popular routing algorithm, and it is implemented in the versatile-place-and-route (VPR) tool. The latest version of PathFinder, implemented in VPR 8.0, employs incremental routing in which it rip-up and re-route (RnR) only those branches of the routing trees that have a congested node or their delay has degraded significantly in the last iterations. The initial iterations have a very high workload (i.e., the number of branches to route), and the later ones have fewer branches to build. We propose a parallel-sequential hybrid router for PathFinder with incremental routing that applies deterministic parallel routing to a window of initial iterations having a high routing workload and sequential routing to the remaining iterations. It also uses an intelligent approach to select nets for sequential and parallel routing. Experiments conducted using Titan benchmarks show that it can improve the runtime of PathFinder by upto 32% with no significant degradation in solution quality.

KW - FPGA Routing

KW - Field programmable gate arrays

KW - Intelligent manufacturing

KW - PathFinder

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

U2 - 10.1109/VLSI-SoC57769.2023.10321904

DO - 10.1109/VLSI-SoC57769.2023.10321904

M3 - Conference contribution

AN - SCOPUS:85179842336

T3 - IEEE/IFIP International Conference on VLSI and System-on-Chip, VLSI-SoC

BT - 2023 IFIP/IEEE 31st International Conference on Very Large Scale Integration, VLSI-SoC 2023

PB - IEEE Computer Society

T2 - 31st IFIP/IEEE International Conference on Very Large Scale Integration, VLSI-SoC 2023

Y2 - 16 October 2023 through 18 October 2023

ER -

A Deterministic Parallel Routing Approach for Accelerating Pathfinder-based Algorithms

Abstract

Publication series

Conference

Bibliographical note

UN SDGs

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this