论文部分内容阅读
大型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倍的加速效果。