基于GPU的FPGA并行布線算法實(shí)現(xiàn).pdf

1、大型 FPGA設(shè)計(jì)要花費(fèi)很長(zhǎng)時(shí)間才能將硬件描述語(yǔ)言轉(zhuǎn)化為比特流文件，其中布局和布線最為耗時(shí)。GPU可以支持高度并行計(jì)算，具有良好的通用性，因此本課題選用GPU設(shè)計(jì)實(shí)現(xiàn)并行FPGA布線算法。
　　FPGA布線階段的任務(wù)是在布線資源圖中，尋找從線網(wǎng)源端到漏端的最短路徑（成本最低）。針對(duì)布線資源圖在GPU上的表達(dá)方式問(wèn)題，本課題采用一種改進(jìn)的緊湊鄰接表來(lái)表示圖G(V,E,W)。
　　VPR中迷宮布線器的本質(zhì)是 Dijkstra算法

2、，本文提出了在 GPU上并行的Dijkstra算法，即可保存路徑的迭代Advanced_Atomics_SSSP算法，利用GPU的原子操作特性并行擴(kuò)展節(jié)點(diǎn)。當(dāng)圖中節(jié)點(diǎn)度比較大時(shí)，節(jié)點(diǎn)擴(kuò)展階段并行線程中進(jìn)行有效計(jì)算的線程數(shù)多，其加速性能較優(yōu)。VPR在進(jìn)行一次布線迭代時(shí)，需要對(duì)多個(gè)線網(wǎng)進(jìn)行布線，而每個(gè)線網(wǎng)需搜索從源端到一個(gè)或多個(gè)漏端的最短路徑。該問(wèn)題可建模為 APSP。本文提出了利用二叉堆優(yōu)化的Heap_APSP算法，每一個(gè)線程負(fù)責(zé)搜索從一