基于GPU的FPGA并行布线算法实现

摘要

大型 FPGA设计要花费很长时间才能将硬件描述语言转化为比特流文件，其中布局和布线最为耗时。GPU可以支持高度并行计算，具有良好的通用性，因此本课题选用GPU设计实现并行FPGA布线算法。
　　FPGA布线阶段的任务是在布线资源图中，寻找从线网源端到漏端的最短路径（成本最低）。针对布线资源图在GPU上的表达方式问题，本课题采用一种改进的紧凑邻接表来表示图G(V,E,W)。
　　VPR中迷宫布线器的本质是 Dijkstra算法，本文提出了在 GPU上并行的Dijkstra算法，即可保存路径的迭代Advanced_Atomics_SSSP算法，利用GPU的原子操作特性并行扩展节点。当图中节点度比较大时，节点扩展阶段并行线程中进行有效计算的线程数多，其加速性能较优。VPR在进行一次布线迭代时，需要对多个线网进行布线，而每个线网需搜索从源端到一个或多个漏端的最短路径。该问题可建模为 APSP。本文提出了利用二叉堆优化的Heap_APSP算法，每一个线程负责搜索从一个源点到其他所有节点的最短路径。
　　将上述两种算法嵌入到VPR，然后用T-Vpack封装MCNC的大规模电路电路到逻辑单元块，然后进行布局得到.net文件。读入.net文件进行并行布线。实验结果表明：Advanced_Atomics_SSSP算法并没有起到加速的效果； Heap_APSP算法在启动8个线程时，与VPR中串行的布线算法相比可达到3至7倍的加速效果。

目录

封面

中文摘要

英文摘要

目录

第1章 绪 论

1.1 课题背景及研究的目的和意义

1.2 国内外关于FPGA布线算法的研究现状

1.3国内外关于GPU并行搜索最短路径的研究状况

1.4 本文的主要研究内容

第2章 GPU并行计算简介

2.1引言

2.2 GPU介绍

2.3 CUDA简介

2.4 本章小结

第3章 FPGA结构及其软件系统

3.1引言

3.2 FPGA CAD流程及相关工具使用

3.3 FPGA结构及其描述

3.4 FPGA结构描述

3.5 本章小结

第4章 基于GPU的并行最短路径搜索算法实现

4.1GPU上图的表达方式和二叉堆(Binary heap)的实现方法

4.2 SSSP并行实现

4.3 APSP并行实现

4.4实验结果

4.5 本章小结

第5章 FPGA布线算法及其并行实现

5.1 VPR中串行布线算法-Pathfinder

5.2成本函数和布线策略

5.3 基于GPU的FPGA布线算法实现

5.4 实验结果

5.5 本章小结

结论

参考文献

攻读硕士学位期间发表的学术论文

声明

致谢