Serial-Equivalent Static and Dynamic Parallel Routing for FPGAs

作     者：Shen, Minghua Zhang, Wentai Luo, Guojie Xiao, Nong 

作者机构：Sun Yat Sen Univ Sch Data & Comp Sci Guangzhou 510275 Peoples R China Sun Yat Sen Univ Key Lab Machine Intelligence & Adv Comp Minist Educ Guangzhou 510275 Peoples R China Peking Univ Ctr Energy Efficient Comp & Applicat Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China 

出 版 物：《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS》 (IEEE集成电路与系统的计算机辅助设计汇刊)

年 卷 期：2020年第39卷第2期

页      面：411-423页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Key Research and Development Program of China [2018YFB1003502] National Natural Science Foundation of China [61433019, 61802446] Program for Guangdong Introducing Innovative and Entrepreneurial Teams [2016ZT06D211] 

主　　题：Field-programmable gate array (FPGA) FPGA CAD parallel routing routing serial equivalency 

摘      要：Serial equivalency enables easier regression testing and customer support in production-grade parallel CAD tools. While existing parallel routing techniques have become sufficiently advanced to provide good speedup, support for serial equivalency still has been very limited or ignored because it was considered costly. In this paper, we present a serial-equivalent parallel router that not only provides significant speedup but also produces the same result as the serial router. This parallel router primarily leverages a dependency-aware scheduling algorithm to facilitate the serial equivalency. Moreover, regardless of how many processor cores are used, this scheduling algorithm also enables parallel router to have the same result as the serial router. In scheduling algorithm, according to the original net order of serial router, all of the nets are scheduled to a series of different stages. Specifically, the independent nets are scheduled to the same stage and they can be routed in parallel while the dependent nets are scheduled in different stages and they are processed in serial. Note that the parallel routing of independent nets can be explored in static and dynamic fashions, and the data synchronization between dependent stages is implemented in MPI-based message queue. Experimental evaluations using ten large designs from the academic VTR benchmark suite show that our parallel router can scale to 32 processor cores at least to provide an average 19.13x speedup compared to the state-ofthe-art academic VPR router. And most importantly, our parallel router can maintain the serial equivalency which achieves the same results as the serial router. To the best of our knowledge, it is the first parallel router that provides significant speedup with a serial equivalency guarantee.