Load Balance-Centric Distributed Parallel Routing for Large-Scale FPGAs

Routing is one of the most time-consuming stages in the FPGA design flow. Parallelization can accelerate the routing process but suffering from load imbalance, further resulting in a low scalability. In this paper, we propose a load balance-centric parallel router in a distributed computing environment. First, we explore regular and irregular region partitioning so that routing tasks are assigned to different cores for static load balance before parallel routing. Second, we explore message propagation and task migration between underloaded and overloaded cores so that load balance can be dynamically maintained at parallel routing runtime. Finally, we demonstrate the effectiveness of the parallel router using large-scale Titan designs. Experimental results show that our parallel router achieves about 17 × speedup on average using 32 cores, compared with VTR 8 router.