【正文】 1 譯 文 VPR：一種新的包裝，布局和布線工具的 FPGA研究 沃恩貝茨和喬納森羅斯 系電氣與計(jì)算機(jī)工程系，多倫多大學(xué) 多倫多， ON，加拿大 M5S3G4{沃恩， jayar} @ 摘 要 我們描述了一個(gè)基于 FPGA新的功能和 CAD工具使用的算法，各種途徑和方（ VPR）。在減少路由面積計(jì)算方面， VPR優(yōu)于所有的 FPGA布局布線工具，我們可以比較。雖然常用的算法是基于已知的方法，是我們目前而言改善運(yùn)行時(shí)間和質(zhì)量的幾個(gè)有效方法。我們目前的版圖和路由上的大型電路的一套新的 結(jié)果，讓未來的基準(zhǔn)電路尺寸上的設(shè)計(jì)方法更多，用于今天的典型的 FPGA布局布線工具工業(yè)品外觀設(shè)計(jì)。VPR是針對(duì)一個(gè)范圍廣泛的 FPGA架構(gòu)的能力，并且源代碼是公開的。它和相關(guān)的網(wǎng)表翻譯 /群集工具 VPACK已經(jīng)被用在世界各地的一些研究項(xiàng)目，并且是有用的 FPGA體系結(jié)構(gòu)的研究。 1 簡(jiǎn)介 在 FPGA 的研究中，人們通常必須評(píng)估新結(jié)構(gòu)特色的實(shí)用工具而做評(píng)估實(shí)驗(yàn)。也就是說評(píng)估基準(zhǔn)電路技術(shù)映射，放置和 FPGA的布線結(jié)構(gòu)上的關(guān)系和措施的架構(gòu)質(zhì)量，如運(yùn)算速度或區(qū)域，然后可以很容易地提取出來。因此，有相當(dāng)大的對(duì)于靈活 CAD工具的 需求，這樣才可以針對(duì)各種架構(gòu)的 FPGA 做高效的設(shè)計(jì)，從而便于比較均勻的設(shè)計(jì)架構(gòu)。本文介紹了通用的地點(diǎn)和路線（ VPR）工具，設(shè)計(jì)很靈活，足夠讓許多 FPGA架構(gòu)的比較 VPR可以執(zhí)行的位置，要么全球路由或合并后的全球詳細(xì)路由。這是公開的 jayar/軟件。 為了使 FPGA體系結(jié)構(gòu)的比較有意義，它是至關(guān)重要的 CAD工具用于將每個(gè)電路架構(gòu)，以地圖的高品質(zhì)展現(xiàn)。路由相優(yōu)于所有的 VPR在查看 FPGA的路由器方面，任何標(biāo)準(zhǔn)基準(zhǔn)測(cè)試的結(jié)果都可用，并且指出 VPR的砂礦和路 由器的組合勝過所有出版的FPGA布局和布線工具。本文結(jié)構(gòu)如下： 在第 2節(jié)我們描述了一些 VPR功能的 FPGA架構(gòu)和范圍與它可能被使用的地方。在第 3和第 4節(jié)，我們描述了布局布線法。在第 5節(jié)講述了比較有必要的 VPR曲目數(shù)量和該電路成功的布線所要求的其他已發(fā)表的工具。在第 6 節(jié)得出了我們的結(jié)論，并提出一些 VPR將來的升級(jí)。 2 2 概述 VPR 圖 1 概括了 VPR 的 CAD 流程。 VPR 投入到由一個(gè) technologymapped 網(wǎng)表和一個(gè)文本文件描述了的 FPGA架構(gòu)中。 VPR可以放置電路，或一個(gè)預(yù)先存在的位置，可以讀入 VPR 可以執(zhí)行或者是全局的路線或合并后的全球 /詳細(xì)的安置途徑。 VPR 的輸出由布局、布線和統(tǒng)計(jì)組成，評(píng)估一項(xiàng)有用的工具 FPGA 架構(gòu)，如路由線長(zhǎng)，跟蹤計(jì)數(shù)最大凈長(zhǎng)度。給出一些可指定的建筑結(jié)構(gòu)參數(shù)描述文件： ?邏輯塊輸入和輸出的數(shù)量， ?對(duì)每個(gè)邏輯塊的輸入和輸出端訪問（ S）之和 ?邏輯等價(jià)性不同的輸入和輸出引腳（例如，所有對(duì)照表輸入功能當(dāng)量）， ?對(duì) I /成一行或一列的 FPGA適合 O引腳數(shù)， ?邏輯塊陣列的尺寸（如 23 30的邏輯塊）。此外，如果全球路由要執(zhí)行，你也可以指定： ?橫向和縱向通道的相對(duì)寬 度之和 ?在不同區(qū)域的 FPGA的渠道相對(duì)寬度。最后，如 果合并后的全球和詳細(xì)的路由被執(zhí)行，一個(gè)也會(huì)進(jìn)行求值： ?開關(guān)塊 [1]架構(gòu)（即為何路由曲目是相互關(guān)聯(lián)的）， ?曲目號(hào)碼，每個(gè)邏輯塊的輸入引腳連接（ [1]）， ?為邏輯塊輸出 FC值， ?對(duì) I / O口 FC值。 3 當(dāng)前的體系結(jié)構(gòu)描述格式不允許跨越多個(gè)領(lǐng)域和多個(gè)邏輯塊和被列入路由體系結(jié)構(gòu)，但我們目前加入此功能。添加新的路由架構(gòu)的功能 VPR相對(duì)容易，因?yàn)?VPR使用體系結(jié)構(gòu)描述來創(chuàng)建路由資源圖。每個(gè)路由跟蹤和建設(shè)中的每一個(gè)腳成為在這個(gè)圖中的節(jié)點(diǎn)， 圖邊表示為允許的連接。路由器，圖形可視化和統(tǒng)計(jì)計(jì)算程序都與此路由資源圖的工作相關(guān)，所以添加新的路由架構(gòu)功能僅涉及更改的子程序來建設(shè)這個(gè)圖。雖然 VPR最初是島式 FPGA的開發(fā) [2， 3]，它也可以和以行為為基礎(chǔ)的 FPGA應(yīng)用 [4]。 VPR目前沒有能力為目標(biāo)的層次 FPGA的 [5]，顯然增加一個(gè)適當(dāng)?shù)奈恢煤统杀竞瘮?shù)設(shè)計(jì)所需的布線資源圖形程序?qū)⑹蛊淠軌蚪鉀Q這些問題。最后， VPR的內(nèi)置圖形允許交互式可視化的布局，路由可用資源和互連的可能途徑路由資源。 VPACK邏輯塊包裝程序 /網(wǎng)絡(luò)表翻譯 VPACK讀取一個(gè)已 經(jīng)技術(shù)映射電路網(wǎng)表格式 blif 到 LUT和觸發(fā)器，包裝成所需的 FPGA邏輯 LUT和觸發(fā)器塊，并輸出在 VPR的網(wǎng)表。 VPACK可以針對(duì)邏輯塊組成一個(gè) LUT，如圖 2所示，因?yàn)檫@是一種常見的 FPGA邏輯元件。 VPACK也針對(duì)邏輯塊包含幾個(gè)有用的 LUT和幾個(gè)拖動(dòng)程序，有或沒有共享 LUT的輸入 [6]。這些“clusterbased”邏輯塊類似于最近由 Altera FPGA開發(fā)的工具類型。 3 布局算法 VPR采用模擬退火算法 [7]。我們已經(jīng)嘗試與幾個(gè)不同的成本函數(shù)聯(lián)系，發(fā)現(xiàn)我們稱之為線性擠塞的成本函數(shù)提供了一個(gè)合理 的計(jì)算時(shí)間，最好的結(jié)果 [8]。此成本函數(shù)的函數(shù)形式就是對(duì)所有的求和電路中的網(wǎng)進(jìn)行計(jì)算。對(duì)于每一個(gè)網(wǎng)，北方新宇和 bby指出在其邊界框的水平和垂直跨度分別為 Q（ n）的因數(shù)補(bǔ)償。邊界線長(zhǎng)度模型中的實(shí)際低估所需的布線，就可以看成超過三個(gè)終端網(wǎng)，作為建議 [10]。它的價(jià)值取決于凈 N兩端號(hào)碼 。 Q是對(duì)總體 1有 3個(gè)或更少的終端，并慢慢增加了 50臺(tái)網(wǎng)邏輯與上 。 4 賈夫常數(shù) x（ n）、 ?（ n）為平均信道容量（在首部）在 X和 Y方向，分別比較全凈邊框和成本函數(shù)的余量，需要更多的調(diào)配路由的領(lǐng)域， FPGA具有窄渠道。本文中的所有結(jié) 果的得到，是利用 FPGA中的所有通道都有相同的原則。在這種情況下，賈夫是一個(gè)常數(shù)，函數(shù)的線性阻塞耗費(fèi)降低到一個(gè)包圍盒的成本函數(shù)。一個(gè)良好的退火算法的必要條件是時(shí)間表取得一個(gè)合理的高品質(zhì)的解決方案與模擬退火的計(jì)算時(shí)間相關(guān)聯(lián)。我們已經(jīng)開發(fā)出一種新的退火附表，導(dǎo)致非常高品質(zhì)的展示位置，并在其中給出退火參數(shù)的自動(dòng)調(diào)節(jié)功能，不同的成本和電路尺寸。我們計(jì)算在初始溫度相同的方式為 [11]。讓 Nblocks 是總數(shù)邏輯塊加的 I / O口電路中的數(shù)量。我們首先創(chuàng)建一個(gè)隨機(jī)安置的電路。接下來，我們執(zhí)行 Nblocks 移動(dòng)（成對(duì)掉期 ）的邏輯塊或 I / O口，并計(jì)算出不同的成本，這些 Nblocks 標(biāo)準(zhǔn)偏差配置。初始溫度設(shè)定為 20倍標(biāo)準(zhǔn)差，確保最初幾乎所有的行動(dòng)是在退火算法范圍內(nèi)被系統(tǒng)接受。正如在 [12]，默認(rèn)號(hào)碼的行為在每個(gè)溫度都有評(píng)價(jià)。這個(gè)默認(rèn)的數(shù)字可以在命令行被取代，從而讓不同的 CPU時(shí)間和填筑質(zhì)量權(quán)衡。減少溫度每秒移動(dòng)數(shù)的 10倍，例如，加快安置到 10倍，并降低了大約只有 10％的最終填筑質(zhì)量。當(dāng)溫度是如此之高，幾乎任何舉動(dòng)都可以被接受時(shí)，我們基本上從一個(gè)位置隨機(jī)移動(dòng)到另一個(gè)位置所改善獲得的成本都是小成本。相反，如果動(dòng)作是很少被接受（ 因溫度當(dāng)前正處于低位，安置相當(dāng)高的品質(zhì)），也有不少改善成本。有了這個(gè)動(dòng)機(jī)，我們提出了一個(gè)新的溫度更新附表，在溫度增加的時(shí)間花費(fèi)在一個(gè)重要的小區(qū)域上，但不是全部動(dòng)作都被接受。如表 1： 最后，它表明在 [12， 13]，這是可取的 Raccept保證作為近似 值。為此，就需要利用 Raccept值來控制這個(gè)范圍限制器。塊是小于或等于交匯處的值，Dlimit單位除了在 X和 Y方向嘗試。一個(gè)小的 Dlimit增加值由 Raccept確保這僅僅是塊進(jìn)行交換考慮。而這些 “本地交換 “往往導(dǎo)致安置成本相對(duì)較小的變 化，越來越多被接受的可能性增加。最初， Dlimit設(shè)置為整個(gè)芯片。每當(dāng)溫度降低， Dlimit整個(gè)芯片的尺寸為這個(gè)結(jié)果退火的第一部分，逐漸萎縮退火過程中的中間階段，并正在為退火低溫第 1部分最后設(shè)計(jì)余量，當(dāng) T退火終止 “*成本 / Ns。該運(yùn)動(dòng)的邏輯塊總是至少影響到一個(gè)網(wǎng)。當(dāng)溫度高于平均凈成本的一個(gè)單位時(shí)，它是不可能接受任何成本增 5 加的調(diào)配結(jié)果的，所以我們終止了退火。 4路由算法 VPR的路由器是基于試探談判的擁塞算法 [14， 8]。 基本上該算法由最初各條線路的最短路徑找到網(wǎng)， 無論任何接線段或邏輯 塊管腳，都可能會(huì)導(dǎo)致過度使用。路由器的迭代過程包含順序抓取行動(dòng)和重新路由（由最低成本路徑中找到）中的每個(gè)電路網(wǎng)。對(duì)使用路由資源成本的函數(shù)，其對(duì)資源的任何過度使用都會(huì)讓當(dāng)前路由發(fā)生事先迭代。通過逐漸增加的多余認(rèn)購路由資源成本，該算法勢(shì)力替代路線網(wǎng)，以避免使用超額認(rèn)購資源，只剩下網(wǎng)最需要一個(gè)給定的資源。對(duì)于本文的實(shí)驗(yàn)結(jié)果，我們?cè)O(shè)置路由器的最大數(shù)量迭代為 45，如果電路中路由沒有成功，一定數(shù)目的目錄中 45迭代就被假定為不可路由通道的寬度。為了避免過于迂回路線以節(jié)省 CPU時(shí)間，我們讓一個(gè)去凈路由最外的 3 個(gè)通道的凈終端 邊界框。一個(gè)重要的執(zhí)行細(xì)節(jié)值得一提。無論是原探路者算法和 Vpr 路由器使用的 Dijkstra 算法（即一個(gè)迷宮路由器 [15]），以每個(gè)網(wǎng)絡(luò)連接和AK用線網(wǎng)為依據(jù)，路由器調(diào)用通道的 k 1次執(zhí)行所有需要的連接。在第一次調(diào)用迷宮路由波從凈源擴(kuò)大，直到它到達(dá)任何的 K – 1值之后。路徑從源到接收器作為現(xiàn)在這個(gè)網(wǎng)的路由的第一部分。波前的迷宮路由被清空，新波前擴(kuò)展是從整個(gè)網(wǎng)絡(luò)布線開始發(fā)出的。之后的 K 1路由器的迷宮調(diào)用凈終端將所有 k值連接。不幸的是，這種方法需要高扇出網(wǎng)絡(luò)相當(dāng)多的 CPU時(shí)間。高扇出網(wǎng)絡(luò)通常跨越大部分 或所有的 FPGA。因此，后者調(diào)用迷宮路由器的路由部分作為凈源會(huì)非常大，它將需要相當(dāng)長(zhǎng)的時(shí)間以擴(kuò)大迷宮路由器波前部分到下一個(gè)接收器。幸好，有一個(gè)更有效的方法。當(dāng)達(dá)到凈水槽值時(shí)，加入所有路由資源分部需要連接水槽和目前的局部路由成本為 0 的波前（即擴(kuò)展列表）。當(dāng)前不要空迷宮路由波前，只要保證繼續(xù)擴(kuò)大正常。由于增加新的路徑路由的部分有一個(gè)零成本，由于這項(xiàng)新路徑通常相當(dāng)小迷宮路由器將首先擴(kuò)大它范圍，也需要相對(duì)較少的時(shí)間來添加此新波，如果整個(gè)波前擴(kuò)展了能實(shí)現(xiàn)那么下一個(gè)接收器 6 將達(dá)到的速度遠(yuǎn)遠(yuǎn)超過現(xiàn)在。圖 3說明了差異圖形。 5實(shí)驗(yàn)結(jié)果 各種 FPGA在本節(jié)中使用的參數(shù)，總是選擇與先前參數(shù)有明顯對(duì)比的那些參數(shù)。所得結(jié)果在本節(jié)獲得了邏輯的 4輸入 LUT加上一個(gè)觸發(fā)器組成的塊，如圖所示在圖 2。時(shí)鐘網(wǎng)和時(shí)序電路沒有遞交，因?yàn)樗ǔＪ锹酚赏ㄟ^專用 FPGA的商業(yè)網(wǎng)絡(luò)中的路由。每個(gè) LUT的輸入出現(xiàn)在一個(gè)邏輯塊的一面，而邏輯塊輸出一般訪問底部和右側(cè)，如圖4。每個(gè)邏輯塊的輸入或輸出連接任何相鄰?fù)ǖ溃?s）（即 Fc的 =寬）。每根電線段和其他布線連接到三段，而在通道交叉口（即值 = 3）和開關(guān)箱拓?fù)涫?“不相交 ” 這是因?yàn)樵?0磁道接線段只連接在 0磁道的其他 布線段。 Doglegs 以往大多數(shù) FPGA布線結(jié)果認(rèn)為 “輸入引腳 doglegs”是可能。如果輸入引腳之間的音軌和它連接接線盒的 Fc 通過獨(dú)立的 SRAM位控制晶體所組成，為了驗(yàn)證兩條軌道上的這些開關(guān)通過電氣連接的可能性。我們將把這個(gè)作為一個(gè)輸入管腳 doglegs。作為商業(yè)化的 FPGA，實(shí)現(xiàn)從一個(gè)輸入引腳接線盒到多路通道，只有一個(gè)軌道可以連接到輸入引腳，使用多路復(fù)用器而不是獨(dú)立通過在 FPGA中的晶體管布局來保存相當(dāng)?shù)拿娣e。另外，通常有一個(gè)緩沖軌道之間的連接塊和它連接多路復(fù) 用這樣做的目的是為了提高速度，同時(shí)這也意味著緩沖輸入引腳 doglegs 不能被使用。因此，如果在未來 FPGA的路由器測(cè)試時(shí)沒有輸入引腳 doglegs 那么我們必須讓輸入引腳 doglegs 和過去 的結(jié)果公平的比較這樣是最好的。在本節(jié)中我們比較了所需的最低數(shù)目，每一條成功的路徑和CAD工具的路由設(shè)置。所有的基準(zhǔn) 2給出結(jié)果，得到了路由 Altor [16]，制作了一個(gè)基于位置的工具 min。列出三兩步（全球和詳細(xì)）路由與其它路由器進(jìn)行合并后的全球和詳細(xì)的路由。 VPR要求比第二，第三最 佳路由器降低 10％的資源數(shù)目，表 3列出了音軌需要執(zhí)行這些標(biāo)準(zhǔn)時(shí)數(shù)新的 CAD工具，同時(shí)允許地方和路線的電路的連接。列出所有電路邏輯快的消息清單。 VPR使用少于 13％資源數(shù)目的同時(shí)，它將執(zhí)行合并后的全球和詳細(xì)的路由，世嘉比用于執(zhí)行詳細(xì)路由對(duì) AA VPR生成全版圖走線。執(zhí)行安置和全局路 7 由，在試圖改善繞線同時(shí)需要超過 87％以上 VPR總資源數(shù)目。最后，讓 VPR配置電路而不是強(qiáng)迫它使用 Altor 內(nèi)存來減少資源數(shù)目的 40％，這表明 VPR的模擬退火算法單元遠(yuǎn)較 Altor 最小單元更好。 8 Doglegs 實(shí)驗(yàn) 比較了 VPR與 SPLACE / SROUTE工具，不允許輸入引腳 doglegs 的性能。當(dāng)這兩個(gè)工具都只能使用路線一，比起 SROUTE軌道 Altor產(chǎn)生的安置需求 VPR減少 13％。當(dāng)然這些工具都支持允許布局和布線的電路，對(duì)于 SPLACE / SROUTE組合 VPR還需要少 29％資源數(shù)目。無論是基于 VPR和 SPLACE只要是使用模擬退火算法，我們相信 VPR單元在一方面優(yōu)于 SPLACE是因?yàn)樗幚砀呱瘸鼍W(wǎng)絡(luò)更有效率，讓更多的動(dòng)作進(jìn)行評(píng)估，另一方面是因?yàn)樗行У耐嘶饡r(shí) 間表給