【正文】 if a circuit has not successfully routed in a given number of tracks in 45 iterations it is assumed to be unroutable with channels of that width. To avoid overly circuitous routes and to save CPU time， we allow the routing of a to go at most 3 channels outside the bounding box of the important implementation detail deserves mention. Both the original Pathfinder algorithm and VPR’s router use Dijkstra’s algorithm (. a maze router [15]) to connect each . For a k terminal ， the maze router is invoked k1 times to perform all the required connections. In the first invocation， the maze routing wavefront expands out from the source until it reaches any one of the k1 sinks. The path from source to sink is now the first part of this ’s routing. The maze routing wavefront is emptied， and a new wavefront expansion is started from the entire routing found thus far. After k1 invocations of the maze router all k terminals of the will be connected. Unfortunately， this approach requires considerable CPU time for highfanout s usually span most or all of the FPGA. Therefore， in the latter invocations of the maze router the partial routing used as the source will be very large， and it will take a long time to expand the maze router 17 wavefront out to the next there is a more efficient method. When a sink is reached， add all the routing resource segments required to connect the sink and the current partial routing to the wavefront (. the expansion list) with a cost of 0. Do not empty the current maze routing wavefront。我們希望下一代的 FPGACAD工具將優(yōu)化這些大型基點(diǎn)，因?yàn)樗麄兪且幌盗忻芮械膯栴}被映射成今天的 FPGA。因?yàn)槁酚纱箅娐樊?dāng)輸入引腳 doglegs 是不允許的。 I / O引腳數(shù)每行或列適合設(shè)置為 2，符合目前的商業(yè)化 FPGA。最后，讓 VPR配置電路而不是強(qiáng)迫它使用 Altor 內(nèi)存來減少資源數(shù)目的 40％，這表明 VPR的模擬退火算法單元遠(yuǎn)較 Altor 最小單元更好。因此，如果在未來 FPGA的路由器測試時(shí)沒有輸入引腳 doglegs 那么我們必須讓輸入引腳 doglegs 和過去 的結(jié)果公平的比較這樣是最好的。每個(gè) LUT的輸入出現(xiàn)在一個(gè)邏輯塊的一面，而邏輯塊輸出一般訪問底部和右側(cè)，如圖4。幸好，有一個(gè)更有效的方法。無論是原探路者算法和 Vpr 路由器使用的 Dijkstra 算法（即一個(gè)迷宮路由器 [15]），以每個(gè)網(wǎng)絡(luò)連接和AK用線網(wǎng)為依據(jù)，路由器調(diào)用通道的 k 1次執(zhí)行所有需要的連接。 4路由算法 VPR的路由器是基于試探談判的擁塞算法 [14， 8]。為此，就需要利用 Raccept值來控制這個(gè)范圍限制器。初始溫度設(shè)定為 20倍標(biāo)準(zhǔn)差，確保最初幾乎所有的行動是在退火算法范圍內(nèi)被系統(tǒng)接受。本文中的所有結(jié) 果的得到，是利用 FPGA中的所有通道都有相同的原則。 3 布局算法 VPR采用模擬退火算法 [7]。路由器，圖形可視化和統(tǒng)計(jì)計(jì)算程序都與此路由資源圖的工作相關(guān)，所以添加新的路由架構(gòu)功能僅涉及更改的子程序來建設(shè)這個(gè)圖。 VPR可以放置電路，或一個(gè)預(yù)先存在的位置，可以讀入 VPR 可以執(zhí)行或者是全局的路線或合并后的全球 /詳細(xì)的安置途徑。 為了使 FPGA體系結(jié)構(gòu)的比較有意義，它是至關(guān)重要的 CAD工具用于將每個(gè)電路架構(gòu)，以地圖的高品質(zhì)展現(xiàn)。我們目前的版圖和路由上的大型電路的一套新的 結(jié)果，讓未來的基準(zhǔn)電路尺寸上的設(shè)計(jì)方法更多，用于今天的典型的 FPGA布局布線工具工業(yè)品外觀設(shè)計(jì)。VPR是針對一個(gè)范圍廣泛的 FPGA架構(gòu)的能力，并且源代碼是公開的。路由相優(yōu)于所有的 VPR在查看 FPGA的路由器方面，任何標(biāo)準(zhǔn)基準(zhǔn)測試的結(jié)果都可用，并且指出 VPR的砂礦和路 由器的組合勝過所有出版的FPGA布局和布線工具。 VPR 的輸出由布局、布線和統(tǒng)計(jì)組成，評估一項(xiàng)有用的工具 FPGA 架構(gòu)，如路由線長，跟蹤計(jì)數(shù)最大凈長度。雖然 VPR最初是島式 FPGA的開發(fā) [2， 3]，它也可以和以行為為基礎(chǔ)的 FPGA應(yīng)用 [4]。我們已經(jīng)嘗試與幾個(gè)不同的成本函數(shù)聯(lián)系，發(fā)現(xiàn)我們稱之為線性擠塞的成本函數(shù)提供了一個(gè)合理 的計(jì)算時(shí)間，最好的結(jié)果 [8]。在這種情況下，賈夫是一個(gè)常數(shù)，函數(shù)的線性阻塞耗費(fèi)降低到一個(gè)包圍盒的成本函數(shù)。正如在 [12]，默認(rèn)號碼的行為在每個(gè)溫度都有評價(jià)。塊是小于或等于交匯處的值，Dlimit單位除了在 X和 Y方向嘗試。 基本上該算法由最初各條線路的最短路徑找到網(wǎng)， 無論任何接線段或邏輯 塊管腳，都可能會導(dǎo)致過度使用。在第一次調(diào)用迷宮路由波從凈源擴(kuò)大，直到它到達(dá)任何的 K – 1值之后。當(dāng)達(dá)到凈水槽值時(shí)，加入所有路由資源分部需要連接水槽和目前的局部路由成本為 0 的波前（即擴(kuò)展列表）。每個(gè)邏輯塊的輸入或輸出連接任何相鄰?fù)ǖ溃?s）（即 Fc的 =寬）。在本節(jié)中我們比較了所需的最低數(shù)目，每一條成功的路徑和CAD工具的路由設(shè)置。 8 Doglegs 實(shí)驗(yàn) 比較了 VPR與 SPLACE / SROUTE工具，不允許輸入引腳 doglegs 的性能。每個(gè)電路被放置在最小的正方形FPGA可 以包含它的路由并且輸入引腳 doglegs 是不允許的。為了鼓勵其它 FPGA研究人員公布的結(jié)果，以這些大型路由基準(zhǔn)，我們發(fā)出以下 “FPGA的挑戰(zhàn)。 VPR的主要設(shè)計(jì)目標(biāo)之一是保持足夠的靈活性，允許工具使用在很多 FPGA架構(gòu)的研究上。 just continue expanding normally. Since the new path added to the partial routing has a cost of zero， the maze router will expand around it at this new path is typically fairly small， it will take relatively little time to add this new wavefront， and the next sink will be reached much more quickly than if the entire wavefront expansion had been started from scratch. Figure 3 illustrates the difference graphically. 5 Experimental Results The various FPGA parameters used in this section were always chosen to allow a direct parison with previously published results. All the results in this section were obtained with a logic block consisting of a 4input LUT plus a flip flop， as shown in Figure 2. The clock was not routed in sequential circuits， as it is usually routed via a dedicated routing work in mercial FPGAs. Each LUT input appears on one side of the logic block， while the logic block output is accessible from both the bottom and right sides， as shown in Figure 4. Each logic block input or output can connect to any track in the adjacent channel(s) (. Fc = W). Each wire segment can connect to three other wiring segments at channel intersections ( Fs = 3) and the switch box topology is “disjoint” that is， a wiring segment in track 0 connects only to other wiring segments in track 0 and so on. Experimental Results with Input Pin Doglegs 18 Most previous FPGA routing results have assumed that “input pin doglegs” are possible. If the connection box between an input pin and the tracks to which it connects consists of Fc independent pass transistors controlled by Fc SRAM bits， it is possible to turn on two of these switches in order to electrically connect two tracks via the input pin. We will refer to this as an input pin dogleg. Commercial FPGAs， however， implement the connection box from an input pin to a channel via a multiplexer， so only one track may be connected to the input pin. Using a multiplexer rather than independent pass transistors saves considerable area in the FPGA layout. As well， normally there is a buffer between a track and the connection block multiplexers to which it connects in order to improve speed。maximum FPGA dimension. This results in Dlimit being the size of the entire chip for the first part of the anneal， shrinking gradually during the middle stages of the anneal， and being 1 for the lowtemperature part of the ， the anneal is terminated when T * Cost / Ns. The movement of a logic block will always affect at least one . When the temperature is less than a small fraction of the average cost