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.

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.

Share

COinS