【正文】 of a ， it is unlikely that any move that results in a cost increase will be accepted， so we terminate the anneal. 3 Routing Algorithm VPR’s router is based on the Pathfinder negotiated congestion algorithm [14， 8].Basically， this algorithm initially routes each by the shortest path it can find，regardless of any overuse of wiring segments or logic block pins that may result. One iteration of the router consists of sequentially rippingup and rerouting (by the lowest cost path found) every in the circuit. The cost of using a routing resource is a function of the current overuse of that resource and any overuse that occurred in prior routing iterations. By 16 gradually increasing the cost of oversubscribed routing resources， the algorithm forces s with alternative routes to avoid using oversubscribed resources， leaving only the that most needs a given resource the experimental results in this paper we set the maximum number of router iterations to 45。建立專(zhuān)門(mén)用于描述精密學(xué)術(shù)的 FPGA布局布線(xiàn)工具。顯然，世嘉處理無(wú)法進(jìn)行。我們使用 Flowmap [28]以技術(shù)圖每 4個(gè) LUT和拖動(dòng)塊并為 VPACK tobine 拖動(dòng)塊，進(jìn)入我們的基本邏輯電路塊 LUT。執(zhí)行安置和全局路 7 由，在試圖改善繞線(xiàn)同時(shí)需要超過(guò) 87％以上 VPR總資源數(shù)目。另外，通常有一個(gè)緩沖軌道之間的連接塊和它連接多路復(fù) 用這樣做的目的是為了提高速度，同時(shí)這也意味著緩沖輸入引腳 doglegs 不能被使用。時(shí)鐘網(wǎng)和時(shí)序電路沒(méi)有遞交，因?yàn)樗ǔＪ锹酚赏ㄟ^(guò)專(zhuān)用 FPGA的商業(yè)網(wǎng)絡(luò)中的路由。因此，后者調(diào)用迷宮路由器的路由部分作為凈源會(huì)非常大，它將需要相當(dāng)長(zhǎng)的時(shí)間以擴(kuò)大迷宮路由器波前部分到下一個(gè)接收器。一個(gè)重要的執(zhí)行細(xì)節(jié)值得一提。當(dāng)溫度高于平均凈成本的一個(gè)單位時(shí)，它是不可能接受任何成本增 5 加的調(diào)配結(jié)果的，所以我們終止了退火。如表 1： 最后，它表明在 [12， 13]，這是可取的 Raccept保證作為近似 值。接下來(lái)，我們執(zhí)行 Nblocks 移動(dòng)（成對(duì)掉期 ）的邏輯塊或 I / O口，并計(jì)算出不同的成本，這些 Nblocks 標(biāo)準(zhǔn)偏差配置。 4 賈夫常數(shù) x（ n）、 ?（ n）為平均信道容量（在首部）在 X和 Y方向，分別比較全凈邊框和成本函數(shù)的余量，需要更多的調(diào)配路由的領(lǐng)域， FPGA具有窄渠道。這些“clusterbased”邏輯塊類(lèi)似于最近由 Altera FPGA開(kāi)發(fā)的工具類(lèi)型。每個(gè)路由跟蹤和建設(shè)中的每一個(gè)腳成為在這個(gè)圖中的節(jié)點(diǎn)， 圖邊表示為允許的連接。 VPR 投入到由一個(gè) technologymapped 網(wǎng)表和一個(gè)文本文件描述了的 FPGA架構(gòu)中。這是公開(kāi)的 jayar/軟件。雖然常用的算法是基于已知的方法，是我們目前而言改善運(yùn)行時(shí)間和質(zhì)量的幾個(gè)有效方法。它和相關(guān)的網(wǎng)表翻譯 /群集工具 VPACK已經(jīng)被用在世界各地的一些研究項(xiàng)目，并且是有用的 FPGA體系結(jié)構(gòu)的研究。本文結(jié)構(gòu)如下： 在第 2節(jié)我們描述了一些 VPR功能的 FPGA架構(gòu)和范圍與它可能被使用的地方。給出一些可指定的建筑結(jié)構(gòu)參數(shù)描述文件： ?邏輯塊輸入和輸出的數(shù)量， ?對(duì)每個(gè)邏輯塊的輸入和輸出端訪(fǎng)問(wèn)（ S）之和 ?邏輯等價(jià)性不同的輸入和輸出引腳（例如，所有對(duì)照表輸入功能當(dāng)量）， ?對(duì) I /成一行或一列的 FPGA適合 O引腳數(shù)， ?邏輯塊陣列的尺寸（如 23 30的邏輯塊）。 VPR目前沒(méi)有能力為目標(biāo)的層次 FPGA的 [5]，顯然增加一個(gè)適當(dāng)?shù)奈恢煤统杀竞瘮?shù)設(shè)計(jì)所需的布線(xiàn)資源圖形程序?qū)⑹蛊淠軌蚪鉀Q這些問(wèn)題。此成本函數(shù)的函數(shù)形式就是對(duì)所有的求和電路中的網(wǎng)進(jìn)行計(jì)算。一個(gè)良好的退火算法的必要條件是時(shí)間表取得一個(gè)合理的高品質(zhì)的解決方案與模擬退火的計(jì)算時(shí)間相關(guān)聯(lián)。這個(gè)默認(rèn)的數(shù)字可以在命令行被取代，從而讓不同的 CPU時(shí)間和填筑質(zhì)量權(quán)衡。一個(gè)小的 Dlimit增加值由 Raccept確保這僅僅是塊進(jìn)行交換考慮。路由器的迭代過(guò)程包含順序抓取行動(dòng)和重新路由（由最低成本路徑中找到）中的每個(gè)電路網(wǎng)。路徑從源到接收器作為現(xiàn)在這個(gè)網(wǎng)的路由的第一部分。當(dāng)前不要空迷宮路由波前，只要保證繼續(xù)擴(kuò)大正常。每根電線(xiàn)段和其他布線(xiàn)連接到三段，而在通道交叉口（即值 = 3）和開(kāi)關(guān)箱拓?fù)涫?“不相交 ” 這是因?yàn)樵?0磁道接線(xiàn)段只連接在 0磁道的其他 布線(xiàn)段。所有的基準(zhǔn) 2給出結(jié)果，得到了路由 Altor [16]，制作了一個(gè)基于位置的工具 min。當(dāng)這兩個(gè)工具都只能使用路線(xiàn)一，比起 SROUTE軌道 Altor產(chǎn)生的安置需求 VPR減少 13％。請(qǐng)注意三個(gè)基準(zhǔn) bigkey，DES和 dsip，是 padlimited要求在 FPGA架構(gòu)表 5比較資源數(shù)量的地方，在完全路線(xiàn)電路與全版圖范圍內(nèi)所需地點(diǎn)與路線(xiàn)的電路與數(shù)字 VPR，然后進(jìn)行詳細(xì)的路由世嘉[23]。 ”每次驗(yàn)證結(jié)果跳動(dòng)的最好驗(yàn)證先 9 前對(duì)這些基準(zhǔn)結(jié)果公布，我們將每條信息支付 1美元給作者（對(duì)不起， 1元加幣。我們目前正進(jìn)行幾個(gè) VPR改進(jìn)，才能進(jìn)一步提高其在 FPGA架構(gòu)的研究能力。 this buffer also means that input pin doglegs can not be used. Therefore， while we allow input pin doglegs in this section in order to make a fair parison with past results， it would be best if in the future FPGA routers were tested without input pin doglegs. In this section we pare the minimum number of tracks per channel required for a successful routing by various CAD tools on a set of 9 benchmark All the results in Table 2 are obtained by routing a placement produced by Altor [16]， a mincut based placement tool. Three of the columns consist of twostep (global then detailed) routing， while the other routers perform bined global and detailed requires 10% fewer tracks than the second best router， and the third best router consists of VPR’s global route phase plus SEGA for detailed routing. Table 3 lists the number of tracks required to implement these benchmarks when new CAD tools are allowed to both place and route the circuits. The size column lists the number of logic blocks in each circuit. VPR uses 13% fewer tracks when it performs bined global and detailed routing than it does when SEGA is used to perform detailed routing on a a VPRgenerated global route. FPR， which performs placement and global routing simultaneously in an attempt to improve routability，requires 87% more total tracks than VPR. Finally， allowing VPR to place the circuits 19 instead of forcing it to use the Altor placements reduces the number of tracks VPR requires to route them by 40%， indicating that VPR’s simulated annealing based placer is considerably better than the Altor mincut placer. Experimental Results Without Input Pin Doglegs Table 4 pares the performance of VPR with that of the SPLACE/SROUTE toolset，which does not allow input pin doglegs. When both tools are only allowed to route an Altorgenerated placement VPR requires 13% fewer tracks than SROUTE. When the tools are allowed to both place and route the circuits， VPR requires 29% fewer tracks than the SPLACE/SROUTE bination. Both VPR and SPLACE are based on simulated annealing. We believe the VPR placer outperforms SPLACE partially because it handles highfanout s more efficiently， allowing more moves to be evaluated in a given time， and partially because of its more efficient annealing schedule. Experimental Results on Large Circuits The benchmarks used in Sections and range in size from 54 to 358 logic blocks， and accordingly are too small to be very representative of today’s ， in this section we present experimental results for the 20 largest MCNC benchmark circuits [27]， which range in size from 1047 to 8383 logic blocks. We use Flowmap [28] to technology map each circuit to 4LUTs and flip flops， and VPACK tobine flip flops and LUTs into our basic logic block. The number of I/O pads that fit per row or column is set to 2， in line with current mercial FPGAs. Each circuit is placed and routed in the smallest square FPGA which can contain it. Input pin doglegs are not allowed. Note that three of the benchmarks， bigkey， des， and dsip， are padlimited in the FPGA architecture 5