Design and Implementation of a Deterministic FPGA Router on a CPU+FPGA Acceleration Platform

FPGA routing is one the longest steps in FPGA compilation, often preventing fast edit-compile-test cycles in prototyping and development. There have been attempts to accelerate FPGA routing using algorithmic improvements, multi-core or multi-CPU platforms. Instead, we propose porting FPGA routing to a CPU+FPGA platform. Motivated by the approaches in FPGA-accelerated graph processing, we propose and implement three acceleration strategies: (1) reducing the number of expensive random memory accesses, (2) parallel and pipelined computation, and (3) efficient hardware priority queues. To reduce irregular memory accesses we first allow wire-to-pin wavefront expansion only when a net is reaching one of its destination pins and, second, we group in sets all the wires starting at the same (x, y) coordinate of the FPGA grid and going in the same direction. Consequently, it becomes possible to design an FPGA accelerator that performs streaming memory accesses and parallel wavefront expansion on all wires in two connected sets. To test and evaluate our FPGA-accelerated PathFinder-based router, we implement it on DE1-SoC, Intel's ARM+FPGA platform and run a set of benchmarks from the VTR suite. The results show that our implementation produces deterministic and good quality output. It is also successful in accelerating a purely software version on the same CPU+FPGA platform, but not against VPR running on a powerful Intel Core-i5 CPU, due to the limitations of the chosen mid-end DE1-SoC platform. Yet, our performance prediction model suggests that higher memory bandwidth and faster FP units would render our router superior to the software alternative.