ParaLaR: A parallel FPGA router based on Lagrangian relaxation
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
Routing of nets is one of the most time consuming steps in the FPGA design flow. While existing works have described ways of accelerating the process through parallelization, they are not scalable. In this paper, we propose a scalable way of parallelizing the routing algorithm through Lagrangian relaxation. The FPGA routing problem is formulated as a linear programming problem, and the channel width constraints, which limit the amount of parallelism, are relaxed by incorporating them into the objective function. The result of the relaxation yields independent sub-problems that we solve using minimum Steiner tree algorithms. Our approach outperforms the state-of-The-Art FPGA parallel router by producing an average self-relative speedup of 7.05X with 8 threads, reduces the total wire length by 22.4%on average and has similar channel width requirements as VPR, albeit at the cost of 7.5%longer critical path. Another advantage of our algorithm is that the number of threads and the order in which the nets are routed has totally no impact on the quality of result.
Details
Originalsprache | Englisch |
---|---|
Titel | 25th International Conference on Field Programmable Logic and Applications, FPL 2015 |
Herausgeber (Verlag) | IEEE Xplore |
Seitenumfang | 6 |
ISBN (elektronisch) | 9780993428005 |
Publikationsstatus | Veröffentlicht - 7 Okt. 2015 |
Peer-Review-Status | Ja |
Extern publiziert | Ja |
Publikationsreihe
Reihe | International Conference on Field Programmable Logic and Applications (FPL) |
---|---|
ISSN | 1946-147X |
Konferenz
Titel | 2015 25th International Conference on Field Programmable Logic and Applications |
---|---|
Kurztitel | FPL 2015 |
Veranstaltungsnummer | 25 |
Dauer | 2 - 4 September 2015 |
Stadt | London |
Land | Großbritannien/Vereinigtes Königreich |