cfaed Seminar Series

Chin Hau Hoo

ParaFRo: A Hybrid Parallel FPGA Router using Fine Grained Synchronization and Partitioning

04.05.2016 (Wednesday) , 16:00 - 17:00
GS7a, Room 204 , Georg-Schumann-Str. 7A , 01187 Dresden

Routing of nets is one of the most time consuming steps in the FPGA design flow. While existing works have described ways of accelerating the process through parallelization, they are not scalable. In this paper, we propose ParaFRo, a two-phase hybrid parallel FPGA router using fine grained synchronization and partitioning. The first phase of the router aims to exploit the maximum parallelism available by routing nets while minimizing load imbalance. Instead of resolving contention with expensive software transactional memory, synchronization among threads are realized using lightweight spin mutexes.

In the case where the algorithm detects that convergence is not possible in phase one, it transitions into phase two where convergence is prioritized over maximum parallelism. To achieve convergence, each thread in phase two routes only congested nets that have been assigned to it by a partitioner. The partitioner aims to reduce the contention among threads at the cost of unbalanced load. In addition, periodic rip up of the entire route tree is employed to break the algorithm out from local minimum. ParaFRo achieves an average speed-up of up to 5.50X with 8 threads. In contrast, existing works managed to obtain an average speed-up of up to 5.46X with 8 threads. In addition, ParaFRo yields an average speed-up of up to 13.8X when only congested nets are rerouted. Moreover, ParaFRo is able to maintain the high speedups while producing similar quality of result as VTR in terms of critical path delay. Finally, the quality of result is relatively independent of the number of the threads.

Go back