外文翻譯--- fpga的安置優(yōu)化方法綜述

1、<p><b>　　附錄A</b></p><p>　　FPGA Placement Optimization Methodology Survey</p><p>　　Sang-Joon Lee and Dr. Kaamran Raahemifar</p><p>　　Department of Electrical and Com

2、puter Engineering Ryerson University</p><p>　　Toronto, ON, Canada</p><p><b>　　ABSTRACT</b></p><p>　　Field Programmable Gate Array (FPGA) is a programmable chip that can

3、be used to quickly implement any digital circuits. Placement is an important part of FPGA design step which determines physical arrangement of the logic blocks in the FPGA. The quality of placement of logic blocks determ

4、ines overall performance of the logic implemented in the FPGA. In this paper, a number of placement optimization techniques are reviewed; min-cut, quadratic, simulated annealing, and a hybrid approach of using g</p>

5、;<p>　　Index Terms Field programmable gate arrays, optimization methods, routing, quadratic programming, simulated annealing, and genetic algorithms</p><p>　　1. INTRODUCTION</p><p>　　Fie

6、ld-Programmable gate arrays (FPGA) are reprogrammable logic chips that can be configured to implement various digital circuits. The Field Programmable Gate Array (FPGA) has gained its popularity in implementing digital c

7、ircuit due to its significant low cost and fast prototyping turn around time. In this survey, an island style FPGA model is considered. Island style FPGA architecture is generally characterized by its two-dimensional sym

8、metry. The generic structure consists of four main elemen</p><p>　　1.1 The Placement Problem</p><p>　　The goal of placement is to find a valid placement for each of configuration logic blocks wh

9、ile trying to minimize the total length of interconnect required. FPGA placement algorithm requires a net-list of logic blocks, which includes</p><p>　　CLBs, I/O pads, and their interconnections. The result

10、of placement is the physical assignment of all blocks and pads on the target FPGA that minimizes one or more objective cost functions. There are three common optimization criteria for placement, time-length driven placem

11、ent, wirelength-driven placement and routability-driven placement. This paper will focus on wire-length placement as the optimization criteria.</p><p>　　1.2 Placement Optimization Techniques</p><p

12、>　　There are five different classes of FPGA placement optimization techniques currently proposed, min-cut, quadratic, simulated annealing, genetic algorithm and particle swarm optimization. In this paper, four techniq

13、ues, min-cut, quadratic, simulated annealing, and a hybrid genetic algorithm with simulated annealing technique will be presented and evaluated. The paper is organized as follows. In section 2, min-cut</p><p&g

14、t;　　placement is presented. In section 3, the quadratic placement technique is presented. In section 4, simulated annealing technique is presented. In section 5, a hybrid</p><p>　　method of using genetic alg

15、orithm and simulated annealing is presented. Lastly, an implementation of hybrid method of genetic algorithm and simulated annealing optimization technique is presented.</p><p>　　2. MIN-CUT PLACEMENT</p&g

16、t;<p>　　The min-cut optimization technique uses recursive partitioning to divide a net-list of circuits into increasingly smaller sub-circuits. The following section describes the</p><p>　　min-cut pla

17、cement approach and evaluation of the placement algorithm.</p><p>　　2.1 Min-Cut Optimization Technique</p><p>　　The min-cut optimization technique recursively apply mincut partitioning to map th

18、e net-list of the circuit into the FPGA layout region. A circuit is recursively bi-partitioned, minimizing the number of cuts of the nets that connect component between partitions, while leaving the highlyconnected block

19、s in one partition. This recursive process is repeated until each partition contains only a few blocks to group the highly-connected blocks together in order to decrease placement cost [3]. Each par</p><p>　

20、　2.2. Pros and Cons</p><p>　　The advantage of min-cut/partition based technique is that it has an open cost function which can be either wire-lengthdriven or time-driven cost function. However, it does not r

21、each global solution. Also, the solution may vary on how the min-cut/partition is performed. As well, as partition is performed, the information from previous step is lost; therefore, the solution may not be able to clim

22、b out of a local minimum.</p><p>　　3. QUADRATIC PLACEMENT</p><p>　　In this section, the quadratic optimization technique implementation for placement problem is reviewed.</p><p>　　3

23、.1. Overview of Quadratic Placement</p><p>　　The quadratic algorithm tries to minimize total squared length by solving linear equation . The cost function is the quadratic sum of the distance from source to

24、destination of each point the path. A cost function for example shown in figure 1 is as follows: This cost function is expanded for entire circuit in the FPGA. The general cost function for quadratic placement is as foll

25、ows:</p><p><b>　?。?）</b></p><p>　　This cost function is expanded for entire circuit in the FPGA.The general cost function for quadratic placement is as follows: <

26、;/p><p>　　Where x and y are the coordinates of a logic of the net-list.Wij is the weight of the edge that connects nodes (xi, yi) and node (xj, yj). Since the input of the quadratic placement is usually represe

27、nted by a hyper-graph, and two nodes can be connected by more than one net, the graph is converted to a weighted hyper-graph, and then two models are used to convert the hyper-graph into a graph .</p><p>　　

28、3.2. Optimization by Quadratic Placement</p><p>　　The following is the quadratic placement optimization technique proposed .</p><p><b>　　Stage 1</b></p><p>　　Build and s

29、olve linear equations.</p><p>　　Map the circuit to the FPGA chip.</p><p>　　Add dummy nodes and expand the placement.</p><p><b>　　Stage 2</b></p><p>　　Refine

30、ment for minimizing linear wire length. Repeat until there is not significant improvement.</p><p>　　Refinement for minimizing linear wire length based on legal placement until there is no significant impro

31、vement.</p><p>　　Re-map the circuit to the FPGA chip.</p><p>　　4. SIMULATED ANNEALING</p><p>　　In this section, first, Simulated annealing algorithm is a universal probability, used

32、 in a large search space to find the optimal solution proposition. Simulated Annealing metallurgy from hardening of the proper nouns.</p><p>　　The principle of simulated annealing and metal annealing is also

33、 similar to the principle: We will apply the theory of thermodynamics to statistical, the search space, think of every point of the air molecules; molecular energy is the kinetic energy of its own; and the search space e

34、very point, but also as the air molecules with the same "energy" to the point of the proposition that the appropriate level.</p><p>　　Algorithm to search for space to an arbitrary starting point: e

35、ach first select a "neighbor", and then calculated from the existing location to "neighbors" of probability. Simulated annealing algorithm can be decomposed into solution space, objective function and

36、 the initial solution of three parts. </p><p>　　Simulated annealing algorithm and the emergence of a new acceptable solution can be divided into the following four steps: The first step is generated by a fun

37、ction from the current solution to produce a solution space is located in the new solution; In order to facilitate the calculation of follow-up and accepted method to reduce time-consuming, usually selected by the curren

38、t after the new solution can transform a simple way to generate new solutions, constitute a new solution if all or part o</p><p>　　The objective function because the only difference arising from the transfor

39、mation part, so the calculation of the objective function worse by incremental calculation of the best. The facts show that for most applications, this is the objective function calculated the quickest way to bad. The th

40、ird step is to determine whether the new solution is accepted, determine a basis for acceptance criteria, the most commonly used criteria of acceptance criteria Metropo1is.The fourth step is to determine </p><

41、p>　　On this basis could be the beginning of the next round of tests. When the new solution was judged to be discarded, then the original basis of the current solution to continue to the next round of tests. Simulated

42、annealing algorithm has nothing to do with the initial value, the algorithm of the solution obtained with the initial solution of the state of S (the starting point is the iterative algorithm) has nothing to do; simulate

43、d annealing algorithm with asymptotic convergence has been proved i</p><p>　　5. HYBRID PLACEMENT: GENETIC ALGORITHM WITH SIMULATED ANNEALING</p><p>　　In this section, detailed information on sim

44、ulated annealing genetic algorithm. Simulated annealing algorithm in the operation of the process of integration into the genetic algorithm, genetic algorithm known as simulated annealing. Simulated annealing algorithm i

45、s based on iterative Monte Carlo method to solve the latter heuristic random search algorithm, which simulated annealing process of solids with the heat balance of random search optimization to achieve the similarity to

46、find the global </p><p>　　5.1. Overview of GASA</p><p>　　As seen in previous section, Simulated Annealing algorithm was described in detail for the placement of the symmetrical FPGA. Genetic alg

47、orithm has advantage of global search over Simulated Annealing because of its robustness of search and problem independence. However, it takes long time to converge in the late phase of the process.</p><p>

48、;　　5.2. Optimization by GASA</p><p>　　In the beginning of the algorithm, the Genetic algorithm(GA) works by using selection, crossover and mutation operators. A significant time is spent in the late phase of

49、 the process of GA in which small improvements are obtained extremely slowly.Simulated annealing (SA) is able to obtain improvements faster than GA in the late phase of the process. Therefore, after a certain numb

50、er of generations, simulated annealing is used to optimize the entire population at a low temperature.</p><p><b>　　附錄B</b></p><p>　　FPGA的安置優(yōu)化方法綜述 </p><p>　　Sang-Joon Lee

51、 和 Dr. Kaamran Raahemifar</p><p>　　電氣與計算機工程系 瑞爾森大學 </p><p><b>　　多倫多，加拿大</b></p><p><b>　　摘要</b></p><p>　　現(xiàn)場可編程門陣列( FPGA )是一種可編程的芯片，可用于快速實施任何數(shù)字電路。

52、在FPGA設(shè)計步驟中，確定物理安排邏輯模塊占據(jù)著一個重要組成部分。質(zhì)量安置邏輯塊確定總體業(yè)績的邏輯執(zhí)行的FPGA 。在本文中，將提出一些安置優(yōu)化技術(shù)：分切，二次安置，模擬退火，和一個利用遺傳算法與模擬退火技術(shù)的混合方法。該方法將對每一個優(yōu)化技術(shù)介紹及其優(yōu)點和缺點進行評估。總體而言，利用遺傳算法與模擬退火工藝的混合方法能夠生達到同類型最好成績和全局最優(yōu)解。使用遺傳算法和模擬退火優(yōu)化技術(shù)是實施利用MATLAB及其結(jié)果使用有線長度驅(qū)動安置費用

53、的功能。 </p><p>　　索引 現(xiàn)場可編程門陣列，優(yōu)化方法，路由，二次規(guī)劃，模擬退火和遺傳算法</p><p><b>　　1導言 </b></p><p>　　現(xiàn)場可編程門陣列 (FPGA)的編程邏輯芯片，可以被配置為執(zhí)行各種數(shù)字電路。現(xiàn)場可編程門陣列( FPGA ) 由于其顯著的低成本和快速原型轉(zhuǎn)換，在實施數(shù)字電路已深受歡迎。在本文中

54、，通過對一個FPGA模型考慮。FPGA架構(gòu)，一般特點是雙向?qū)ΨQ。通用結(jié)構(gòu)包括四個主要部分：配置邏輯塊（CLB），其中通常包含組合或時序邏輯電路，輸入/輸出模塊（IOB），連接外部設(shè)備的FPGA和可編程互連資源和交換機。可配置邏輯模塊能夠執(zhí)行多個邏輯功能。連接塊是通過可編程連接用來連接路由CLB的渠道。同樣，輸入/輸出模塊是通過可編程連接用來連接的縱向和橫向路由的渠道。 </p><p><b>　　1.

55、1安置</b></p><p>　　安置的目標是找到一種有效安置的每個配置邏輯塊試圖盡量減少的總長度互連需要。 FPGA的布局算法需要單獨的邏輯塊，并通過I /O端口使其互連。由于物理地址是變化的，所有模塊對目標FPGA的最小的一個或多個目標成本的職能。有三種常見的標準優(yōu)化布局，時間長度驅(qū)動布局，驅(qū)動安置和路由驅(qū)動的位置。本文將側(cè)重于時間長度安置作為優(yōu)化標準。</p><p>

56、　　1.2安置優(yōu)化技術(shù) </p><p>　　有5個不同類別的FPGA布局優(yōu)化技術(shù)，分別為：分切、二次安置、模擬退火、遺傳算法和粒子群優(yōu)化。本文介紹其中四個技術(shù)，分切，二次安置，模擬退火，模擬退火遺傳算法。本文安排如下：在第2節(jié)中，介紹分切安置技術(shù)；在第3節(jié)中，介紹二次安置技術(shù)；第4節(jié)中，介紹模擬退火技術(shù)；在第5節(jié)中，介紹模擬退火遺傳算法技術(shù)。</p><p><b>　　2 最

57、小切割配置</b></p><p>　　最小切優(yōu)化技術(shù)使用遞歸分割電路來具體分割電路，下面一節(jié)介紹了分切安置方法和布局算法。 </p><p>　　2.1最小切割優(yōu)化技術(shù) </p><p>　　最小切優(yōu)化技術(shù)適用FPGA遞歸分割的地址電路的布局區(qū)域。電路是遞歸雙向分區(qū)，盡量減少網(wǎng)絡之間連接部分的分割。在同一個部分區(qū)域，這個遞歸過程會反復進行，直至僅包含每

58、個分區(qū)幾個高度連接塊組相互結(jié)合，以減少安置費用。每個分區(qū)對應一個遞歸樹節(jié)點，在第一方式目標，分切，使其中一個部分自行分配，使其削減成為最少的線路。所有邊緣的部分將分區(qū)進行加權(quán)，并進行計時臨界。時間臨界的邊緣在使用時間計算時間延遲值始終是變化的。此外，它定義了一個臨界點的最高臨界邊緣的事件。使用時間臨界邊緣體重標準禁用劃分算法從低到高。因此，在關(guān)鍵時候，網(wǎng)絡在同一分區(qū)和電路將保持有一個較小的時間延遲。這一進程的延遲轉(zhuǎn)讓都是在每一個分區(qū)的階

59、段。因此，時機將更為準確，每個階段的時序驅(qū)動分割將更為優(yōu)秀。 </p><p><b>　　2.2 優(yōu)點和缺點</b></p><p>　　最小切割優(yōu)化技術(shù)的優(yōu)點是：它有一個開放的成本函數(shù)可以是有線或時間驅(qū)動成本函數(shù)。但是，它并沒有達成全部的解決方法。此外，該解決方案可能會有所不同的執(zhí)行方法。同時，作為分區(qū)進行，從以前的資料丟失的一步，因此，該解決方案可能無法爬出來當

60、地最低限度。 </p><p><b>　　3 二次布局 </b></p><p>　　在這一節(jié)中，將對二次優(yōu)化技術(shù)實施安置問題進行介紹。 </p><p>　　3.1二次算法概況 </p><p>　　二次算法盡量減少總長度的平方來求解線性方程組。基本函數(shù)是二次距離從原點到目的節(jié)點的每一個點的路徑的總和。基本功能，總的

61、成本函數(shù)為二次位置如下：  </p><p><b>　?。?）</b></p><p>　　整個FPGA電路中，基本函數(shù)擴大到一般函數(shù)為二次安置公式如下：</p><p>　　X和Y坐標是一個邏輯連接節(jié)點。由于輸入的二次安置通常是由一個圖形和兩個節(jié)點構(gòu)成，因此，通常可以把一個以上的網(wǎng)絡系統(tǒng)或圖表轉(zhuǎn)換為加權(quán)圖形。</p>

62、<p>　　3.2 優(yōu)化二次布局</p><p>　　以下是二次布局優(yōu)化技術(shù)建議：</p><p><b>　　第1階段 </b></p><p>　　建立并求解線性方程組</p><p>　　尋找電路的FPGA芯片。</p><p>　　新增虛擬節(jié)點和擴大安置。</p>

63、<p><b>　　第2階段 </b></p><p>　　細化為盡量減少線性線長。重復操作直到?jīng)]有明顯的改變。</p><p>　　細化為盡量減少線性線長度，并根據(jù)公式安置，直到?jīng)]有明顯的改變。 </p><p>　　重新繪制電路的FPGA芯片。 </p><p><b>　　4 模擬退火 <

64、;/b></p><p>　　在本節(jié)中，首先，模擬退火是一種通用概率算法，用來在一個大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火來自冶金學的專有名詞淬火。</p><p>　　模擬退火的原理也和金屬退火的原理近似：我們將熱力學的理論套用到統(tǒng)計學上，將搜尋空間內(nèi)每一點想像成空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點，也像空氣分子一樣帶有“能量”，以表示該點對命題的合適

65、程度。算法先以搜尋空間內(nèi)一個任意點作起始：每一部先選擇一個“鄰居”，然后再計算從現(xiàn)有位置到達“鄰居”的概率。</p><p>　　模擬退火算法可以分解為解空間、目標函數(shù)和初始解三部分。</p><p>　　模擬退火算法新解的產(chǎn)生和接受可分為如下四個步驟： </p><p>　　第一步是由一個產(chǎn)生函數(shù)從當前解產(chǎn)生一個位于解空間的新解；為便于后續(xù)的計算和接受，減少算法耗

66、時，通常選擇由當前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成新解的全部或部分元素進行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當前新解的鄰域結(jié)構(gòu)，因而對冷卻進度表的選取有一定的影響。 </p><p>　　第二步是計算與新解所對應的目標函數(shù)差。因為目標函數(shù)差僅由變換部分產(chǎn)生，所以目標函數(shù)差的計算最好按增量計算。事實表明，對大多數(shù)應用而言，這是計算目標函數(shù)差的最快方法。 </p><p&g

67、t;　　第三步是判斷新解是否被接受,判斷的依據(jù)是一個接受準則，最常用的接受準則是Metropo1is準則。 </p><p>　　第四步是當新解被確定接受時，用新解代替當前解，這只需將當前解中對應于產(chǎn)生新解時的變換部分予以實現(xiàn)，同時修正目標函數(shù)值即可。此時，當前解實現(xiàn)了一次迭代?？稍诖嘶A(chǔ)上開始下一輪試驗。而當新解被判定為舍棄時，則在原當前解的基礎(chǔ)上繼續(xù)下一輪試驗。 </p><p>　　

68、模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點)無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率l 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。</p><p>　　5 混合配置：模擬退火遺傳算法</p><p>　　在本節(jié)中，詳細介紹了模擬退火遺傳算法。在模擬退火算法的運行過程中溶入遺傳算法，稱為模擬退火遺傳算法。模擬退火算法是基于Mon

69、te Carlo迭代求解法后種啟發(fā)式隨機搜索算法，它模擬固體物質(zhì)退火過程的熱平衡問題與隨機搜索尋優(yōu)問題的相似性來達到尋找全局最優(yōu)或近似全局最優(yōu)的目的。在搜索最優(yōu)解的過程中，模擬退火法除了可以接受優(yōu)化解外，還有一個隨機接受準則（Metropolis準則）有限度地接受惡化解，并且接受惡化解的概率慢慢趨向于0，這使得算法有可能從局部極值區(qū)域中跳出，即可能找到全局最優(yōu)解，并保證了算法的收斂性。混合的遺傳算法和模擬退火（ GASA ）優(yōu)化技術(shù)用于

70、安置對稱的FPGA 。該算法包括兩個階段。首先，它利用遺傳算法優(yōu)化安置在全球范圍內(nèi)，然后模擬退火算法用于改善解決混合安置辦法是建議使用的優(yōu)勢，尋求全局最優(yōu)解的遺傳算法收斂速度慢克服遺傳算法在后期階段的過程中使用低溫模擬退火算法。</p><p>　　5.1 GASA概況</p><p>　　正如上一節(jié)所述，模擬退火算法能夠詳細描述對稱的FPGA地址 。遺傳算法模擬退火由于其穩(wěn)定的搜索和問題

71、的獨立性已經(jīng)被廣為采用。然而，它需要很長時間才能達到后期的進程階段。</p><p>　　5.2 GASA的優(yōu)化 </p><p>　　在最初的算法里，遺傳算法（ GA ）的工作原理是利用選擇，交叉來變換算法。大部分的時間都會花在后期進程階段，其中一些小的改進，得到了極為顯著的效果。退火（ SA ）是能夠獲得后期階段的進程改進遺傳算法的速度比。因此，在一定的算法里，是通過模擬退火來優(yōu)化低溫