Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information

Umair Siddiqi; Timothy Martin; Sam Van Den Eijnden; Ahmed Shamli; Gary Grewal; Sadiq Sait; Shawki Areibi

doi:10.1145/3551901.3556492

Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information

Umair Siddiqi
, Timothy Martin
, Sam Van Den Eijnden
, Ahmed Shamli
, Gary Grewal
, Sadiq Sait
, Shawki Areibi

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

14 Scopus citations

Abstract

Field Programmable Gate Array (FPGA) routing is one of the most time consuming tasks within the FPGA design flow, requiring hours and even days to complete for some large industrial designs. This is becoming a major concern for FPGA users and tool developers. This paper proposes a simple, yet effective, framework that reduces the runtime of PathFinder based routers. A supervised Machine Learning (ML) algorithm is developed to forecast costs (from the placement phase) associated with possible congestion and hot spot creation in the routing phase. These predicted costs are used to guide the router to avoid highly congested regions while routing nets, thus reducing the total number of iterations and rip-up and reroute operations involved. Results obtained indicate that the proposed ML approach achieves on average a 43 reduction in the number of routing iterations and 28.6 reduction in runtime when implemented in the state-of-the-art enhanced PathFinder algorithm.

Original language	English
Title of host publication	MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD
Publisher	Association for Computing Machinery, Inc
Pages	15-20
Number of pages	6
ISBN (Electronic)	9781450394864
DOIs	https://doi.org/10.1145/3551901.3556492
State	Published - 12 Sep 2022
Event	4th ACM/IEEE Workshop on Machine Learning for CAD, MLCAD 2022 - Snowbird, United States Duration: 12 Sep 2022 → 13 Sep 2022

Publication series

Name	MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD

Conference

Conference	4th ACM/IEEE Workshop on Machine Learning for CAD, MLCAD 2022
Country/Territory	United States
City	Snowbird
Period	12/09/22 → 13/09/22

Bibliographical note

Publisher Copyright:
© 2022 ACM.

Keywords

FPGA routing
congestion
supervised machine learning

ASJC Scopus subject areas

Artificial Intelligence
Computer Graphics and Computer-Aided Design
Hardware and Architecture

Access to Document

10.1145/3551901.3556492

Cite this

Siddiqi, U., Martin, T., Van Den Eijnden, S., Shamli, A., Grewal, G., Sait, S., & Areibi, S. (2022). Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information. In MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD (pp. 15-20). (MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD). Association for Computing Machinery, Inc. https://doi.org/10.1145/3551901.3556492

@inproceedings{0834a9dfe5044355ae508cf30820c893,

title = "Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information",

abstract = "Field Programmable Gate Array (FPGA) routing is one of the most time consuming tasks within the FPGA design flow, requiring hours and even days to complete for some large industrial designs. This is becoming a major concern for FPGA users and tool developers. This paper proposes a simple, yet effective, framework that reduces the runtime of PathFinder based routers. A supervised Machine Learning (ML) algorithm is developed to forecast costs (from the placement phase) associated with possible congestion and hot spot creation in the routing phase. These predicted costs are used to guide the router to avoid highly congested regions while routing nets, thus reducing the total number of iterations and rip-up and reroute operations involved. Results obtained indicate that the proposed ML approach achieves on average a 43 reduction in the number of routing iterations and 28.6 reduction in runtime when implemented in the state-of-the-art enhanced PathFinder algorithm.",

keywords = "FPGA routing, congestion, supervised machine learning",

author = "Umair Siddiqi and Timothy Martin and \{Van Den Eijnden\}, Sam and Ahmed Shamli and Gary Grewal and Sadiq Sait and Shawki Areibi",

note = "Publisher Copyright: {\textcopyright} 2022 ACM.; 4th ACM/IEEE Workshop on Machine Learning for CAD, MLCAD 2022 ; Conference date: 12-09-2022 Through 13-09-2022",

year = "2022",

month = sep,

day = "12",

doi = "10.1145/3551901.3556492",

language = "English",

series = "MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD",

publisher = "Association for Computing Machinery, Inc",

pages = "15--20",

booktitle = "MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD",

}

Siddiqi, U, Martin, T, Van Den Eijnden, S, Shamli, A, Grewal, G, Sait, S & Areibi, S 2022, Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information. in MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD. MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD, Association for Computing Machinery, Inc, pp. 15-20, 4th ACM/IEEE Workshop on Machine Learning for CAD, MLCAD 2022, Snowbird, United States, 12/09/22. https://doi.org/10.1145/3551901.3556492

Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information. / Siddiqi, Umair; Martin, Timothy; Van Den Eijnden, Sam et al.
MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD. Association for Computing Machinery, Inc, 2022. p. 15-20 (MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD).

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

TY - GEN

T1 - Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information

AU - Siddiqi, Umair

AU - Martin, Timothy

AU - Van Den Eijnden, Sam

AU - Shamli, Ahmed

AU - Grewal, Gary

AU - Sait, Sadiq

AU - Areibi, Shawki

PY - 2022/9/12

Y1 - 2022/9/12

N2 - Field Programmable Gate Array (FPGA) routing is one of the most time consuming tasks within the FPGA design flow, requiring hours and even days to complete for some large industrial designs. This is becoming a major concern for FPGA users and tool developers. This paper proposes a simple, yet effective, framework that reduces the runtime of PathFinder based routers. A supervised Machine Learning (ML) algorithm is developed to forecast costs (from the placement phase) associated with possible congestion and hot spot creation in the routing phase. These predicted costs are used to guide the router to avoid highly congested regions while routing nets, thus reducing the total number of iterations and rip-up and reroute operations involved. Results obtained indicate that the proposed ML approach achieves on average a 43 reduction in the number of routing iterations and 28.6 reduction in runtime when implemented in the state-of-the-art enhanced PathFinder algorithm.

AB - Field Programmable Gate Array (FPGA) routing is one of the most time consuming tasks within the FPGA design flow, requiring hours and even days to complete for some large industrial designs. This is becoming a major concern for FPGA users and tool developers. This paper proposes a simple, yet effective, framework that reduces the runtime of PathFinder based routers. A supervised Machine Learning (ML) algorithm is developed to forecast costs (from the placement phase) associated with possible congestion and hot spot creation in the routing phase. These predicted costs are used to guide the router to avoid highly congested regions while routing nets, thus reducing the total number of iterations and rip-up and reroute operations involved. Results obtained indicate that the proposed ML approach achieves on average a 43 reduction in the number of routing iterations and 28.6 reduction in runtime when implemented in the state-of-the-art enhanced PathFinder algorithm.

KW - FPGA routing

KW - congestion

KW - supervised machine learning

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

U2 - 10.1145/3551901.3556492

DO - 10.1145/3551901.3556492

M3 - Conference contribution

AN - SCOPUS:85139250544

T3 - MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD

SP - 15

EP - 20

BT - MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD

PB - Association for Computing Machinery, Inc

T2 - 4th ACM/IEEE Workshop on Machine Learning for CAD, MLCAD 2022

Y2 - 12 September 2022 through 13 September 2022

ER -

Siddiqi U, Martin T, Van Den Eijnden S, Shamli A, Grewal G, Sait S et al. Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information. In MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD. Association for Computing Machinery, Inc. 2022. p. 15-20. (MLCAD 2022 - Proceedings of the 2022 ACM/IEEE Workshop on Machine Learning for CAD). doi: 10.1145/3551901.3556492

Faster FPGA Routing by Forecasting and Pre-Loading Congestion Information

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this