面向超大规模FPGA的高效并行布线方法研究

Routing is a critical step in FPGA design flow. With the increasing capacity of FPGAs, routing need to take several hours or even days to implement a larger FPGA design, significantly hindering designer productivity. Furthermore, routing is naturally sequential and parallelization is non-trivial. This project focuses on highly efficient parallel routing for very large scale FPGA. The main research contents are as follows. Firstly, we explore the parallel-friendly routing approaches, including net subgraph expansion, resource reuse in net rip-up and re-route, and routing resource preference model. Secondly, we explore the fine-grained single-net parallel routing approaches, including resource conflict-aware techniques, node-level parallelism and speculative parallelism, and edge-level parallelism and speculative parallelism. Finally, we explore the coarse-grained multi-net parallel routing approaches, including net partitioning algorithm, load balancing estimation, communication optimization, synchronization and asynchronization, and net-level parallelism. The aim of project is to optimize and parallelize the routing to significantly redure the routing time and improve the productivity of FPGA design.

布线是FPGA自动化设计流程中的关键环节。由于FPGA的规模日益增长，导致布线过程需要花费数小时甚至数天才能完成，严重影响FPGA设计的开发效率。同时布线固有的串行本质，又使得并行加速极具挑战性。本课题重点研究和探讨面向超大规模FPGA的高效并行布线方法，内容有：1)研究并行友好的布线优化方法，包括研究线网子图扩展方法，线网断开与重布时资源重用方法，以及布线过程中线网资源的偏好模型。2)研究细粒度单条线网的并行布线方法，包括研究单条线网并行时布线资源冲突感知技术，节点资源之间的并行性与预测并行性，以及边资源之间的并行性与预测并行性。3)研究粗粒度多条线网的并行布线方法，包括研究多条线网并行时线网分配算法，负载均衡的评估方法，通信开销的分析与优化，异步与同步的协同机制以及线网之间的并行性。课题目标是在布线过程中研究算法优化与并行加速，大幅度减少布线时间，提高超大规模FPGA设计效率。

现场可编程门阵列FPGA是硬件可重构体系结构能够提供高能效计算而被广泛地运用到各种计算领域中。随着芯片集成规模和设计复杂度的日益增长，电子设计自动化EDA工具需要花费很长的运行时间才能将应用自动综合到FPGA上，严重影响芯片设计的生产力。布线是FPGA EDA编译流程中最耗时的阶段之一。我们研究并提出了一种面向超大规模FPGA的高效并行布线方法。..本项目成功实现了：1）粗粒度多线网并行布线。我们提出的负载均衡分布式并行布线优化方法，实现了利用布线区域递归划分成多个子区域从而指引多线网分配到不同的计算核心以执行并行布线，完成了利用负载均衡指引线网在布线前进行合理均衡分配以及在布线运行时进行动态均衡调整的多线网并行布线，该方法使用32颗计算核心可以提供17倍运行加速并伴随轻微的质量损失，相比于最新的VTR 8串行布线器。2）细粒度单线网并行布线。我们提出的串行等价静态与动态并行布线优化方法，实现了利用线网串行布线顺序并结合运行时线网之间的资源拥塞来指引线网分配以确保并行布线顺序与串行布线顺序的一致性的并行布线，完成了在图形处理器GPU平台上利用小区域动态扩展实现单条线网动静态融合的并行布线，该方法使用单块GPU设备能够提供平均21倍的运行加速且产生轻微的质量损失，相比于VTR 7.0串行布线器。3）软硬件程序编译与运行时优化。我们在复杂应用的硬件电路高层次综合优化方面，提出一种基于信息熵的高层次综合调度方法，设计一种基于深度强化学习的高层次综合智能调度器，并研制了一款高层次综合工具原型能够实现C软件程序编译成Verilog硬件电路程序。同时，我们在深度学习应用运行时优化方面，提出了一种可扩展映射方法能够将大规模深度神经网络模型映射到多FPGA集群系统中，设计了一种分布式原位深度神经网络推理方法，实现了利用解耦的神经网络结构来应对分布式深度学习推理时进行模型并行优化，这些方法用于大规模深度神经网络模型推理时能够改善性能，减少访存开销以及提升模型推理精度。