Coarse-Grained Parallel Routing With Recursive Partitioning for FPGAs

Routing is a very time-consuming stage in the FPGA design flow, significantly hindering the productivity. This article proposes CPRS, a coarse-grained parallel routing scheme in a distributed computing environment. First, we partition entire routing region to guide the assignment of nets for parallel processing. The partitioning is a recursive fashion, and at each recursive partitioning, the region is partitioned into two subregions forming three subsets of nets. The first subset consists of potentially dependent nets and they are distributed in different subregions. The remaining two subsets consist of potentially independent nets and they are distributed in their own subregions. Second, we route the nets of first subset in serial and process the remaining two subsets in parallel. The parallel processing is a coarse-grained fashion, which is implemented by MPI parallel programming model. Finally, we explore the optimization of both partitioning and parallel processing to further improve the overall speedup of parallel routing. In addition, we adopt MPI message to synchronize the intermediate results between different cores in parallel routing for a feasible solution. Experiments use a set of commonly used benchmarks to demonstrate the effectiveness of CPRS. Notably, CPRS achieves about 18× speedup on average using 32 processor cores with minor loss of quality, compared with the VTR 7.0 serial router. There is about 1.6× improvement over the state-of-the-art parallel router.