| Methods for speeding up the modified Pathfinder routing algorithm for island-style FPGA |
|
 |
|
|
| Authors |
| | Zapletina M.A. |
| Date of publication |
| | 2021 |
| DOI |
| | 10.31114/2078-7707-2021-4-27-33 |
|
| Abstract |
| | The paper presents two methods of speeding up the interconnection routing stage within the layout design flow for field-programmable gate arrays with an island-style architecture. The basic algorithm used in this work is Pathfinder algorithm, modified to support the representation of the routing resources of an FPGA chip in the form of a mixed route graph. The first method is based on reducing the number of rip-up & reroute iterations. It was found that a reroute of congested nets only allows reducing the routing times by 38% on average while increasing the critical path delay up to 10% only. The second method expands the idea of directed pathfinding on a route graph with spatial characteristics known. Various directed search adjustment factors were investigated and the optimal one was discovered. It was found that a decrease in the adjustment factor depending on the iteration of the routing algorithm leads to an acceleration of a routing task solution but causes a significant drop in routes quality at the same time. The introduced method adjusted by an optimal factor is capable of doubling a routing speedup without routability degradation. |
| Keywords |
| | routing, interconnect, FPGA, rip-up and reroute, place & route, directed search, Pathfinder. |
| Library reference |
| | Zapletina M.A. Methods for speeding up the modified Pathfinder routing algorithm for island-style FPGA // Problems of Perspective Micro- and Nanoelectronic Systems Development - 2021. Issue 4. P. 27-33. doi:10.31114/2078-7707-2021-4-27-33 |
| URL of paper |
| | http://www.mes-conference.ru/data/year2021/pdf/D058.pdf |
