Document Type
Conference Proceeding
Language
eng
Publication Date
12-2014
Publisher
Institute of Electrical and Electronics Engineers
Source Publication
2014 International Conference on ReConFigurable Computing and FPGAs (ReConFig)
Source ISSN
978-1-4799-5943-3
Original Item ID
doi: 10.1109/ReConFig.2014.7032540
Abstract
The most popular algorithm for solving the routing problem for field programmable gate arrays (FPGAs) has virtually remained the same for the past two decades. It is essentially an iterative maze technique, such as Dijkstra's algorithm, applied to each net in the circuit repeatedly. During multiple routing iterations, nets are ripped-up and rerouted via different paths to resolve competition for routing resources or to improve circuit delay. The most popular implementation of such a routing approach is the PathFinder algorithm used inside the VPR tool [1]. The quality of the routing solution depends however on the order in which nets are processed during each of the routing iterations. This is commonly referred to as the net ordering problem. PathFinder addresses this problem through continuous updates of the cost associated with overusing routing resources. After each routing iteration, the cost of overusing a routing resource is increased based on the routing so far, so that probability of resolving all congestion during future iterations increases. To further address the net ordering problem, in this paper, we investigate the effectiveness of two combined techniques to enhance PathFinder. We change the order in which nets are ripped-up and rerouted to give higher priority to nets with two, three, and more than eleven pins because these nets have the largest impact on the quality of the routing solution. Also, we alter the cost calculation during wave expansions for two-pin nets based on the global routing solution obtained by solving an equivalent multicommodity flow problem. Preliminary results suggest that the conventional FPGA routing solutions can still be improved.
Recommended Citation
Ababei, Cristinel; Kavasseri, Rajesh G.; and Zare, Mohammad A., "Net Reordering and Multicommodity Flow Based Global Routing for FPGAs" (2014). Electrical and Computer Engineering Faculty Research and Publications. 77.
https://epublications.marquette.edu/electric_fac/77
Comments
Accepted version. Published as part of the proceedings of the conference, 2014 International Conference on ReConFigurable Computing and FPGAs (ReConFig), 2014. DOI. © 2014 Institute of Electrical and Electronics Engineers (IEEE). Used with permission.