| It takes a long time to transform a large FPGA hardware description languagedesign into bitstream file. Furthermore placement and routing consume the most time.GPU can support highly parallel computing and owns good versatility. Thus thisdissertation selects GPU to design the parallel FPGA routing algorithm.The objective of FPGA routing phase is to search every nets’ shortest path fromsource to sink on a routing resource graph. In order to represent routing resource graphin GPU, we use a compact adjacency list.The maze router’s essence is Dijkstra algorithm in VPR. This paper presents aparallel Dijkstra algorithm in GPU, called Advanced_Atomics_SSSP. This algorithmutilizes the atomic operation to parallel extent nodes. When the degree of graph nodes isrelatively large, the performance of this algorithm is better. There are more threadsrunning in expansion phase, and its acceleration performance is better. In an iterationrouter, VPR needs to route multiple nets, and search the shortest path from the source tosinks. The problem can be modeled as APSP. This paper presents Heap_APSP algorithmusing binary heap. Each thread routes one net.This project uses MCNC large circuits to verify algorithms performance. T-Vpackpackages circuits to CLB, and places CLB to get.net placement files. After embeddingtwo algorithms into VPR, start routing circuits. Experimental results show thatAdvanced_Atomics_SSSP algorithm doesn’t play the effect of acceleration due to nodesof FPGA routing resource graph have low degree; the algorithm is to find the short pathfrom the source to all other nodes, and Dijstra algorithm in VPR only searches fromsource to sinks’ shortest path. Heap_APSP algorithm achieves3to7acceleration effectwhen using8threads. |
