譯文VPR一種新的包裝，布局和布線工具的FPGA研究沃恩貝茨和喬納森羅斯系電氣與計(jì)算機(jī)工程系，多倫多大學(xué)多倫多，ON，加拿大M5S3G4沃恩，JAYAREECGTORONTOEDU摘要我們描述了一個(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ì)路由。這是公開的HTTP/WWWEECGTORONTOEDU/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概述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)，如路由線長，跟蹤計(jì)數(shù)最大凈長度。給出一些可指定的建筑結(jié)構(gòu)參數(shù)描述文件邏輯塊輸入和輸出的數(shù)量，對(duì)每個(gè)邏輯塊的輸入和輸出端訪問（S）之和邏輯等價(jià)性不同的輸入和輸出引腳（例如，所有對(duì)照表輸入功能當(dāng)量），對(duì)I/成一行或一列的FPGA適合O引腳數(shù)，邏輯塊陣列的尺寸（如2330的邏輯塊）。此外，如果全球路由要執(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值。當(dāng)前的體系結(jié)構(gòu)描述格式不允許跨越多個(gè)領(lǐng)域和多個(gè)邏輯塊和被列入路由體系結(jié)構(gòu)，但我們目前加入此功能。添加新的路由架構(gòu)的功能VPR相對(duì)容易，因?yàn)閂PR使用體系結(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”邏輯塊類似于最近由ALTERAFPGA開發(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ǔ)償。邊界線長度模型中的實(shí)際低估所需的布線，就可以看成超過三個(gè)終端網(wǎng)，作為建議10。它的價(jià)值取決于凈N兩端號(hào)碼Q是對(duì)總體1有3個(gè)或更少的終端，并慢慢增加了50臺(tái)網(wǎng)邏輯與上279。賈夫常數(shù)X（N）、（N）為平均信道容量（在首部）在X和Y方向，分別比較全凈邊框和成本函數(shù)的余量，需要更多的調(diào)配路由的領(lǐng)域，F(xiàn)PGA具有窄渠道。本文中的所有結(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保證作為近似044的量有可能被取值。為此，就需要利用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退火終止“0005成本/NNETS。該運(yùn)動(dòng)的邏輯塊總是至少影響到一個(gè)網(wǎng)。當(dāng)溫度高于平均凈成本的一個(gè)單位時(shí)，它是不可能接受任何成本增加的調(diào)配結(jié)果的，所以我們終止了退火。4路由算法VPR的路由器是基于試探談判的擁塞算法14，8?；旧显撍惴ㄓ勺畛醺鳁l線路的最短路徑找到網(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)用通道的K1次執(zhí)行所有需要的連接。在第一次調(diào)用迷宮路由波從凈源擴(kuò)大，直到它到達(dá)任何的K1值之后。路徑從源到接收器作為現(xiàn)在這個(gè)網(wǎng)的路由的第一部分。波前的迷宮路由被清空，新波前擴(kuò)展是從整個(gè)網(wǎng)絡(luò)布線開始發(fā)出的。之后的K1路由器的迷宮調(diào)用凈終端將所有K值連接。不幸的是，這種方法需要高扇出網(wǎng)絡(luò)相當(dāng)多的CPU時(shí)間。高扇出網(wǎng)絡(luò)通常跨越大部分或所有的FPGA。因此，后者調(diào)用迷宮路由器的路由部分作為凈源會(huì)非常大，它將需要相當(dā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è)接收器將達(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ù)ǖ溃⊿）（即FC的寬）。每根電線段和其他布線連接到三段，而在通道交叉口（即值3）和開關(guān)箱拓?fù)涫恰安幌嘟弧边@是因?yàn)樵?磁道接線段只連接在0磁道的其他布線段。51實(shí)驗(yàn)結(jié)果與輸入引腳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)CIRCUITS1在表2給出結(jié)果，得到了路由ALTOR16，制作了一個(gè)基于位置的工具M(jìn)IN。列出三兩步（全球和詳細(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ì)AAVPR生成全版圖走線。執(zhí)行安置和全局路由，在試圖改善繞線同時(shí)需要超過87以上VPR總資源數(shù)目。最后，讓VPR配置電路而不是強(qiáng)迫它使用ALTOR內(nèi)存來減少資源數(shù)目的40，這表明VPR的模擬退火算法單元遠(yuǎn)較ALTOR最小單元更好。52不輸入引腳的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í)間表給定的時(shí)間。大電路53實(shí)驗(yàn)結(jié)果在第51和52的54至358的邏輯基準(zhǔn)塊范圍內(nèi)使用面積計(jì)算顯然太小，因?yàn)檫@是特殊的FPGA。因此在本節(jié)中我們目前的實(shí)驗(yàn)結(jié)果，20個(gè)最大的MCNC基準(zhǔn)電路27，它的大小范圍從1047到8383邏輯塊。我們使用FLOWMAP28以技術(shù)圖每4個(gè)LUT和拖動(dòng)塊并為VPACKTOCOMBINE拖動(dòng)塊，進(jìn)入我們的基本邏輯電路塊LUT。I/O引腳數(shù)每行或列適合設(shè)置為2，符合目前的商業(yè)化FPGA。每個(gè)電路被放置在最小的正方形FPGA可以包含它的路由并且輸入引腳DOGLEGS是不允許的。請(qǐng)注意三個(gè)基準(zhǔn)BIGKEY，DES和DSIP，是PADLIMITED要求在FPGA架構(gòu)表5比較資源數(shù)量的地方，在完全路線電路與全版圖范圍內(nèi)所需地點(diǎn)與路線的電路與數(shù)字VPR，然后進(jìn)行詳細(xì)的路由世嘉23。表5還給出了大小每個(gè)邏輯塊的數(shù)量計(jì)算電路。在世嘉列中的條目仿真無法成功，因?yàn)槭兰芜\(yùn)行路由內(nèi)存不足。由VPR增加路由產(chǎn)生的全版圖航線曲目總數(shù)，有超過所需68路線的電路主場(chǎng)由VPR路由完全執(zhí)行。顯然，世嘉處理無法進(jìn)行。因?yàn)槁酚纱箅娐樊?dāng)輸入引腳DOGLEGS是不允許的。為了鼓勵(lì)其它FPGA研究人員公布的結(jié)果，以這些大型路由基準(zhǔn)，我們發(fā)出以下“FPGA的挑戰(zhàn)?！泵看悟?yàn)證結(jié)果跳動(dòng)的最好驗(yàn)證先前對(duì)這些基準(zhǔn)結(jié)果公布，我們將每條信息支付1美元給作者（對(duì)不起，1元加幣。，而不是1美元），由他們來處理如果減少需要跟蹤的總數(shù)。該技術(shù)映射網(wǎng)表，由VPR生成和投放位置的目前最全的跟蹤路由在HTTP/WWWEECGTORONTOEDU/JAYAR/SOFTWAREHTML。上可以找到6結(jié)論和未來工作我們已經(jīng)提出了一個(gè)優(yōu)于所有這類工具的新的FPGA布局布線工具，它讓我們可以進(jìn)行直接的比較。此外，我們已經(jīng)提出更大的電路基準(zhǔn)測(cè)試結(jié)果。建立專門用于描述精密學(xué)術(shù)的FPGA布局布線工具。我們希望下一代的FPGACAD工具將優(yōu)化這些大型基點(diǎn)，因?yàn)樗麄兪且幌盗忻芮械膯栴}被映射成今天的FPGA。VPR的主要設(shè)計(jì)目標(biāo)之一是保持足夠的靈活性，允許工具使用在很多FPGA架構(gòu)的研究上。我們目前正進(jìn)行幾個(gè)VPR改進(jìn)，才能進(jìn)一步提高其在FPGA架構(gòu)的研究能力。在不久的將來VPR將支持緩沖和分段路由結(jié)構(gòu)，我們計(jì)劃增加定時(shí)分析儀和時(shí)序驅(qū)動(dòng)的路由。外文原文VPRANEWPACKING，PLACEMENTANDROUTINGTOOLFORFPGARESEARCH1VAUGHNBETZANDJONATHANROSEDEPARTMENTOFELECTRICALANDCOMPUTERENGINEERING，UNIVERSITYOFTORONTOTORONTO，ON，CANADAM5S3G4VAUGHN，JAYAREECGTORONTOEDUABSTRACTWEDESCRIBETHECAPABILITIESOFANDALGORITHMSUSEDINANEWFPGACADTOOL，VERSATILEPLACEANDROUTEVPRINTERMSOFMINIMIZINGROUTINGAREA，VPROUTPERFORMSALLPUBLISHEDFPGAPLACEANDROUTETOOLSTOWHICHWECANCOMPAREALTHOUGHTHEALGORITHMSUSEDAREBASEDONPREVIOUSLYKNOWNAPPROACHES，WEPRESENTSEVERALENHANCEMENTSTHATIMPROVERUNTIMEANDQUALITYWEPRESENTPLACEMENTANDROUTINGRESULTSONANEWSETOFLARGECIRCUITSTOALLOWFUTUREBENCHMARKCOMPARISONSOFFPGAPLACEANDROUTETOOLSONCIRCUITSIZESMORETYPICALOFTODAYSINDUSTRIALDESIGNSVPRISCAPABLEOFTARGETINGABROADRANGEOFFPGAARCHITECTURES，ANDTHESOURCECODEISPUBLICLYAVAILABLEITANDTHEASSOCIATEDNETLISTTRANSLATION/CLUSTERINGTOOLVPACKHAVEALREADYBEENUSEDINANUMBEROFRESEARCHPROJECTSWORLDWIDE，ANDSHOULDBEUSEFULINMANYAREASOFFPGAARCHITECTURERESEARCH1INTRODUCTIONINFPGARESEARCH，ONEMUSTTYPICALLYEVALUATETHEUTILITYOFNEWARCHITECTURALFEATURESEXPERIMENTALLYTHATIS，BENCHMARKCIRCUITSARETECHNOLOGYMAPPED，PLACEDANDROUTEDONTOTHEFPGAARCHITECTURESOFINTEREST，ANDMEASURESOFTHEARCHITECTURESQUALITY，SUCHASSPEEDORAREA，CANTHENREADILYBEEXTRACTEDACCORDINGLY，THEREISCONSIDERABLENEEDFORFLEXIBLECADTOOLSTHATCANTARGETAWIDEVARIETYOFFPGAARCHITECTURESEFFICIENTLY，ANDHENCEALLOWFAIRCOMPARISONSOFTHEARCHITECTURESTHISPAPERDESCRIBESTHEVERSATILEPLACEANDROUTEVPRTOOL，WHICHHASBEENDESIGNEDTOBEFLEXIBLEENOUGHTOALLOWCOMPARISONOFMANYDIFFERENTFPGAARCHITECTURESVPRCANPERFORMPLACEMENTANDEITHERGLOBALROUTINGORCOMBINEDGLOBALANDDETAILEDROUTINGITISPUBLICLYAVAILABLEFROMHTTP/WWWEECGTORONTOEDU/JAYAR/SOFTWAREHTMLINORDERTOMAKEMEANINGFULFPGAARCHITECTURECOMPARISONS，ITISESSENTIALTHATTHECADTOOLSUSEDTOMAPCIRCUITSINTOEACHARCHITECTUREAREOFHIGHQUALITYTHEROUTINGPHASEOFVPROUTPERFORMSALLPREVIOUSLYPUBLISHEDFPGAROUTERSFORWHICHSTANDARDBENCHMARKSRESULTSAREAVAILABLE，ANDTHATTHECOMBINATIONOFVPRSPLACERANDROUTEROUTPERFORMSALLPUBLISHEDCOMBINATIONSOFFPGAPLACEMENTANDROUTINGTOOLS2THEORGANIZATIONOFTHISPAPERISASFOLLOWSINSECTION2WEDESCRIBESOMEOFTHEFEATURESOFVPRANDTHERANGEOFFPGAARCHITECTURESWITHWHICHITMAYBEUSEDINSECTIONS3AND4WEDESCRIBETHEPLACEMENTANDROUTINGALGORITHMSINSECTION5，WECOMPARETHENUMBEROFTRACKSREQUIREDBYVPRTOSUCCESSFULLYROUTECIRCUITSWITHTHATREQUIREDBYOTHERPUBLISHEDTOOLSINSECTION6WECONCLUDEANDOUTLINESOMEFUTUREENHANCEMENTSWHICHWILLBEMADETOVPR2OVERVIEWOFVPRFIGURE1OUTLINESTHEVPRCADFLOWTHEINPUTSTOVPRCONSISTOFATECHNOLOGYMAPPEDNETLISTANDATEXTFILEDESCRIBINGTHEFPGAARCHITECTUREVPRCANPLACETHECIRCUIT，ORAPREEXISTINGPLACEMENTCANBEREADINVPRCANTHENPERFORMEITHERAGLOBALROUTEORACOMBINEDGLOBAL/DETAILEDROUTEOFTHEPLACEMENTVPRSOUTPUTCONSISTSOFTHEPLACEMENTANDROUTING，ASWELLASSTATISTICSUSEFULINASSESSINGTHEUTILITYOFANFPGAARCHITECTURE，SUCHASROUTEDWIRELENGTH，TRACKCOUNT，ANDMAXIMUMNETLENGTHSOMEOFTHEARCHITECTURALPARAMETERSTHATCANBESPECIFIEDINTHEARCHITECTUREDESCRIPTIONFILEARETHENUMBEROFLOGICBLOCKINPUTSANDOUTPUTS，THESIDESOFTHELOGICBLOCKFROMWHICHEACHINPUTANDOUTPUTISACCESSIBLE，THELOGICALEQUIVALENCEBETWEENVARIOUSINPUTANDOUTPUTPINSEGALLLUTINPUTSAREFUNCTIONALLYEQUIVALENT，THENUMBEROFI/OPADSTHATFITINTOONEROWORONECOLUMNOFTHEFPGA，ANDTHEDIMENSIONSOFTHELOGICBLOCKARRAYEG23X30LOGICBLOCKSINADDITION，IFGLOBALROUTINGISTOBEPERFORMED，ONECANALSOSPECIFYTHERELATIVEWIDTHSOFHORIZONTALANDVERTICALCHANNELS，ANDTHERELATIVEWIDTHSOFTHECHANNELSINDIFFERENTREGIONSOFTHEFPGAFINALLY，IFCOMBINEDGLOBALANDDETAILEDROUTINGISTOBEPERFORMED，ONEALSOSPECIFIESTHESWITCHBLOCK1ARCHITECTUREIEHOWTHEROUTINGTRACKSAREINTERCONNECTED，THENUMBEROFTRACKSTOWHICHEACHLOGICBLOCKINPUTPINCONNECTSFC1，THEFCVALUEFORLOGICBLOCKOUTPUTS，ANDTHEFCVALUEFORI/OPADSTHECURRENTARCHITECTUREDESCRIPTIONFORMATDOESNOTALLOWSEGMENTSTHATSPANMORETHANONELOGICBLOCKTOBEINCLUDEDINTHEROUTINGARCHITECTURE，BUTWEAREPRESENTLYADDINGTHISFEATUREADDINGNEWROUTINGARCHITECTUREFEATURESTOVPRISRELATIVELYEASY，SINCEVPRUSESTHEARCHITECTUREDESCRIPTIONTOCREATEAROUTINGRESOURCEGRAPHEVERYROUTINGTRACKANDEVERYPININTHEARCHITECTUREBECOMESANODEINTHISGRAPH，ANDTHEGRAPHEDGESREPRESENTTHEALLOWABLECONNECTIONSTHEROUTER，GRAPHICSVISUALIZATIONANDSTATISTICSCOMPUTATIONROUTINESALLWORKONLYWITHTHISROUTINGRESOURCEGRAPH，SOADDINGNEWROUTINGARCHITECTUREFEATURESONLYINVOLVESCHANGINGTHESUBROUTINESTHATBUILDTHISGRAPHALTHOUGHVPRWASINITIALLYDEVELOPEDFORISLANDSTYLEFPGAS2，3，ITCANALSOBEUSEDWITHROWBASEDFPGAS4VPRISNOTCURRENTLYCAPABLEOFTARGETINGHIERARCHICALFPGAS5，ALTHOUGHADDINGANAPPROPRIATEPLACEMENTCOSTFUNCTIONANDTHEREQUIREDROUTINGRESOURCEGRAPHBUILDINGROUTINESWOULDALLOWITTOTARGETTHEMFINALLY，VPRSBUILTINGRAPHICSALLOWINTERACTIVEVISUALIZATIONOFTHEPLACEMENT，THEROUTING，THEAVAILABLEROUTINGRESOURCESANDTHEPOSSIBLEWAYSOFINTERCONNECTINGTHEROUTINGRESOURCES21THEVPACKLOGICBLOCKPACKER/NETLISTTRANSLATORVPACKREADSINABLIFFORMATNETLISTOFACIRCUITTHATHASBEENTECHNOLOGYMAPPEDTOLUTSANDFLIPFLOPS，PACKSTHELUTSANDFLIPFLOPSINTOTHEDESIREDFPGALOGICBLOCK，ANDOUTPUTSANETLISTINVPRSNETLISTFORMATVPACKCANTARGETALOGICBLOCKCONSISTINGOFONELUTANDONEFF，ASSHOWNINFIGURE2，ASTHISISACOMMONFPGALOGICELEMENTVPACKISALSOCAPABLEOFTARGETINGLOGICBLOCKSTHATCONTAINSEVERALLUTSANDSEVERALFLIPFLOPS，WITHORWITHOUTSHAREDLUTINPUTS6THESE“CLUSTERBASED”LOGICBLOCKSARESIMILARTOTHOSEEMPLOYEDINRECENTFPGASBYALTERA，XILINXANDLUCENTTECHNOLOGIES2PLACEMENTALGORITHMVPRUSESTHESIMULATEDANNEALINGALGORITHM7FORPLACEMENTWEHAVEEXPERIMENTEDWITHSEVERALDIFFERENTCOSTFUNCTIONS，ANDFOUNDTHATWHATWECALLALINEARCONGESTIONCOSTFUNCTIONPROVIDESTHEBESTRESULTSINAREASONABLECOMPUTATIONTIME8THEFUNCTIONALFORMOFTHISCOSTFUNCTIONISWHERETHESUMMATIONISOVERALLTHENETSINTHECIRCUITFOREACHNET，BBXANDBBYDENOTETHEHORIZONTALANDVERTICALSPANSOFITSBOUNDINGBOX，RESPECTIVELYTHEQNFACTORCOMPENSATESFORTHEFACTTHATTHEBOUNDINGBOXWIRELENGTHMODELUNDERESTIMATESTHEWIRINGNECESSARYTOCONNECTNETSWITHMORETHANTHREETERMINALS，ASSUGGESTEDIN10ITSVALUEDEPENDSONTHENUMBEROFTERMINALSOFNETNQIS1FORNETSWITH3ORFEWERTERMINALS，ANDSLOWLYINCREASESTO279FORNETSWITH50TERMINALSCAV，XNANDCAV，YNARETHEAVERAGECHANNELCAPACITIESINTRACKSINTHEXANDYDIRECTIONS，RESPECTIVELY，OVERTHEBOUNDINGBOXOFNETNTHISCOSTFUNCTIONPENALIZESPLACEMENTSWHICHREQUIREMOREROUTINGINAREASOFTHEFPGATHATHAVENARROWERCHANNELSALLTHERESULTSINTHISPAPER，HOWEVER，AREOBTAINEDWITHFPGASINWHICHALLCHANNELSHAVETHESAMECAPACITYINTHISCASECAVISACONSTANTANDTHELINEARCONGESTIONCOSTFUNCTIONREDUCESTOABOUNDINGBOXCOSTFUNCTIONAGOODANNEALINGSCHEDULEISESSENTIALTOOBTAINHIGHQUALITYSOLUTIONSINAREASONABLECOMPUTATIONTIMEWITHSIMULATEDANNEALINGWEHAVEDEVELOPEDANEWANNEALINGSCHEDULEWHICHLEADSTOVERYHIGHQUALITYPLACEMENTS，ANDINWHICHTHEANNEALINGPARAMETERSAUTOMATICALLYADJUSTTODIFFERENTCOSTFUNCTIONSANDCIRCUITSIZESWECOMPUTETHEINITIALTEMPERATUREINAMANNERSIMILARTO11LETNBLOCKSBETHETOTALNUMBEROFLOGICBLOCKSPLUSTHENUMBEROFI/OPADSINACIRCUITWEFIRSTCREATEARANDOMPLACEMENTOFTHECIRCUITNEXTWEPERFORMNBLOCKSMOVESPAIRWISESWAPSOFLOGICBLOCKSORI/OPADS，ANDCOMPUTETHESTANDARDDEVIATIONOFTHECOSTOFTHESENBLOCKSDIFFERENTCONFIGURATIONSTHEINITIALTEMPERATUREISSETTO20TIMESTHISSTANDARDDEVIATION，ENSURINGTHATINITIALLYVIRTUALLYANYMOVEISACCEPTEDATTHESTARTOFTHEANNEALASIN12，THEDEFAULTNUMBEROFMOVESEVALUATEDATEACHTEMPERATUREISTHISDEFAULTNUMBERCANBEOVERRIDDENONTHECOMMANDLINE，HOWEVER，TOALLOWDIFFERENTCPUTIME/PLACEMENTQUALITYTRADEOFFSREDUCINGTHENUMBEROFMOVESPERTEMPERATUREBYAFACTOROF10，F(xiàn)OREXAMPLE，SPEEDSUPPLACEMENTBYAFACTOROF10ANDREDUCESFINALPLACEMENTQUALITYBYONLYABOUT10WHENTHETEMPERATUREISSOHIGHTHATALMOSTANYMOVEISACCEPTED，WEAREESSENTIALLYMOVINGRANDOMLYFROMONEPLACEMENTTOANOTHERANDLITTLEIMPROVEMENTINCOSTISOBTAINEDCONVERSELY，IFVERYFEWMOVESAREBEINGACCEPTEDDUETOTHETEMPERATUREBEINGLOWANDTHECURRENTPLACEMENTBEINGOFFAIRLYHIGHQUALITY，THEREISALSOLITTLEIMPROVEMENTINCOSTWITHTHISMOTIVATIONINMIND，WEPROPOSEANEWTEMPERATUREUPDATESCHEDULEWHICHINCREASESTHEAMOUNTOFTIMESPENTATTEMPERATURESWHEREASIGNIFICANTFRACTIONOF，BUTNOTALL，MOVESAREBEINGACCEPTEDANEWTEMPERATUREISCOMPUTEDASTNEWATOLD，WHERETHEVALUEOFADEPENDSONTHEFRACTIONOFATTEMPTEDMOVESTHATWEREACCEPTEDRACCEPTATTOLD，ASSHOWNINTABLE1FINALLY，ITWASSHOWNIN12，13THATITISDESIRABLETOKEEPRACCEPTNEAR044FORASLONGASPOSSIBLEWEACCOMPLISHTHISBYUSINGTHEVALUEOFRACCEPTTOCONTROLARANGELIMITERONLYINTERCHANGESOFBLOCKSTHATARELESSTHANOREQUALTODLIMITUNITSAPARTINTHEXANDYDIRECTIONSAREATTEMPTEDASMALLVALUEOFDLIMITINCREASESRACCEPTBYENSURINGTHATONLYBLOCKSWHICHARECLOSETOGETHERARECONSIDEREDFORSWAPPINGTHESE“LOCALSWAPS”TENDTORESULTINRELATIVELYSMALLCHANGESINTHEPLACEMENTCOST，INCREASINGTHEIRLIKELIHOODOFACCEPTANCEINITIALLY，DLIMITISSETTOTHEENTIRECHIPWHENEVERTHETEMPERATUREISREDUCED，THEVALUEOFDLIMITISUPDATEDACCORDINGTO，ANDTHENCLAMPEDTOTHERANGE1DLIMITMAXIMUMFPGADIMENSIONTHISRESULTSINDLIMITBEINGTHESIZEOFTHEENTIRECHIPFORTHEFIRSTPARTOFTHEANNEAL，SHRINKINGGRADUALLYDURINGTHEMIDDLESTAGESOFTHEANNEAL，ANDBEING1FORTHELOWTEMPERATUREPARTOFTHEANNEALFINALLY，THEANNEALISTERMINATEDWHENT0005COST/NNETSTHEMOVEMENTOFALOGICBLOCKWILLALWAYSAFFECTATLEASTONENETWHENTHETEMPERATUREISLESSTHANASMALLFRACTIONOFTHEAVERAGECOSTOFANET，ITISUNLIKELYTHATANYMOVETHATRESULTSINACOSTINCREASEWILLBEACCEPTED，SOWETERMINATETHEANNEAL3ROUTINGALGORITHMVPRSROUTERISBASEDONTHEPATHFINDERNEGOTIATEDCONGESTIONALGORITHM14，8BASICALLY，THISALGORITHMINITIALLYROUTESEACHNETBYTHESHORTESTPATHITCANFIND，REGARDLESSOFANYOVERUSEOFWIRINGSEGMENTSORLOGICBLOCKPINSTHATMAYRESULTONEITERATIONOFTHEROUTERCONSISTSOFSEQUENTIALLYRIPPINGUPANDREROUTINGBYTHELOWESTCOSTPATHFOUNDEVERYNETINTHECIRCUITTHECOSTOFUSINGAROUTINGRESOURCEISAFUNCTIONOFTHECURRENTOVERUSEOFTHATRESOURCEANDANYOVERUSETHATOCCURREDINPRIORROUTINGITERATIONSBYGRADUALLYINCREASINGTHECOSTOFOVERSUBSCRIBEDROUTINGRESOURCES，THEALGORITHMFORCESNETSWITHALTERNATIVEROUTESTOAVOIDUSINGOVERSUBSCRIBEDRESOURCES，LEAVINGONLYTHENETTHATMOSTNEEDSAGIVENRESOURCEBEHINDFORTHEEXPERIMENTALRESULTSINTHISPAPERWESETTHEMAXIMUMNUMBEROFROUTERITERATIONSTO45IFACIRCUITHASNOTSUCCESSFULLYROUTEDINAGIVENNUMBEROFTRACKSIN45ITERATIONSITISASSUMEDTOBEUNROUTABLEWITHCHANNELSOFTHATWIDTHTOAVOIDOVERLYCIRCUITOUSROUTESANDTOSAVECPUTIME，WEALLOWTHEROUTINGOFANETTOGOATMOST3CHANNELSOUTSIDETHEBOUNDINGBOXOFTHENETTERMINALSONEIMPORTANTIMPLEMENTATIONDETAILDESERVESMENTIONBOTHTHEORIGINALPATHFINDERALGORITHMANDVPRSROUTERUSEDIJKSTRASALGORITHMIEAMAZEROUTER15TOCONNECTEACHNETFORAKTERMINALNET，THEMAZEROUTERISINVOKEDK1TIMESTOPERFORMALLTHEREQUIREDCONNECTIONSINTHEFIRSTINVOCATION，THEMAZEROUTINGWAVEFRONTEXPANDSOUTFROMTHENETSOURCEUNTILITREACHESANYONEOFTHEK1NETSINKSTHEPATHFROMSOURCETOSINKISNOWTHEFIRSTPARTOFTHISNETSROUTINGTHEMAZEROUTINGWAVEFRONTISEMPTIED，ANDANEWWAVEFRONTEXPANSIONISSTARTEDFROMTHEENTIRENETROUTINGFOUNDTHUSFARAFTERK1INVOCATIONSOFTHEMAZEROUTERALLKTERMINALSOFTHENETWILLBECONNECTEDUNFORTUNATELY，THISAPPROACHREQUIRESCONSIDERABLECPUTIMEFORHIGHFANOUTNETSHIGHFANOUTNETSUSUALLYSPANMOSTORALLOFTHEFPGATHEREFORE，INTHELATTERINVOCATIONSOFTHEMAZEROUTERTHEPARTIALROUTINGUSEDASTHENETSOURCEWILLBEVERYLARGE，ANDITWILLTAKEALONGTIMETOEXPANDTHEMAZEROUTERWAVEFRONTOUTTOTHENEXTSINKFORTUNATELYTHEREISAMOREEFFICIENTMETHODWHENANETSINKISREACHED，ADDALLTHEROUTINGRESOURCESEGMENTSREQUIREDTOCONNECTTHESINKANDTHECURRENTPARTIALROUTINGTOTHEWAVEFRONTIETHEEXPANSIONLISTWITHACOSTOF0DONOTEMPTYTHECURRENTMAZEROUTINGWAVEFRONTJUSTCONTINUEEXPANDINGNORMALLYSINCETHENEWPATHADDEDTOTHEPARTIALROUTINGHASACOSTOFZERO，THEMAZEROUTERWILLEXPANDAROUNDITATFIRSTSINCETHISNEWPATHISTYPICALLYFAIRLYSMALL，ITWILLTAKERELATIVELYLITTLETIMETOADDTHISNEWWAVEFRONT，ANDTHENEXTSINKWILLBEREACHEDMUCHMOREQUICKLYTHANIFTHEENTIREWAVEFRONTEXPANSIONHADBEENSTARTEDFROMSCRATCHFIGURE3ILLUSTRATESTHEDIFFERENCEGRAPHICALLY5EXPERIMENTALRESULTSTHEVARIOUSFPGAPARAMETERSUSEDINTHISSECTIONWEREALWAYSCHOSENTOALLOWADIRECTCOMPARISONWITHPREVIOUSLYPUBLISHEDRESULTSALLTHERESULTSINTHISSECTIONWEREOBTAINEDWITHALOGICBLOCKCONSISTINGOFA4INPUTLUTPLUSAFLIPFLOP，ASSHOWNINFIGURE2THECLOCKNETWASNOTROUTEDINSEQUENTIALCIRCUITS，ASITISUSUALLYROUTEDVIAADEDICATEDROUTINGNETWORKINCOMMERCIALFPGASEACHLUTINPUTAPPEARSONONESIDEOFTHELOGICBLOCK，WHILETHELOGICBLOCKOUTPUTISACCESSIBLEFROMBOTHTHEBOTTOMANDRIGHTSIDES，ASSHOWNINFIGURE4EACHLOGICBLOCKINPUTOROUTPUTCANCONNECTTOANYTRACKINTHEADJACENTCHANNELSIEFCWEACHWIRESEGMENTCANCONNECTTOTHREEOTHERWIRINGSEGMENTSATCHANNELINTERSECTIONSIEFS3ANDTHESWITCHBOXTOPOLOGYIS