FPGA-Assisted Deterministic Routing for FPGAs

FPGA routing is one of the most time-consuming steps of 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 used 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 test and evaluate the router performance, we implement it on DE1-SoC, a mid-end ARM+FPGA platform of Intel. Our router works and produces good quality results. Moreover, we succeed in accelerating the software router running on the embedded ARM. However, when compared to the latest VPR router running on a powerful Intel Core-i5 CPU, our CPU+FPGA router is slower. This is not unexpected, given the limited performance of the chosen hardware platform. Since this design can easily be ported to newer and higher-end CPU+FPGA systems, we estimate the performance it could achieve; the results indicate that a non-negligible speedup over the software-only router could indeed be obtained.