栗 磊,姜明富

（信陽農(nóng)林學(xué)院計(jì)算機(jī)科學(xué)系，河南信陽,464000）

FPGA引腳分配方案的分析與改進(jìn)

栗 磊,姜明富

（信陽農(nóng)林學(xué)院計(jì)算機(jī)科學(xué)系，河南信陽,464000）

本文研究了二分圖算法和蟻群算法，在FPGA引腳分配上的應(yīng)用，這兩種算法各有優(yōu)缺點(diǎn)。本文在這兩種算法的基礎(chǔ)上提出了一種混合算法，用于提高FPGA引腳分配的效率。經(jīng)過驗(yàn)證得知，混合算法能有效提高FPGA引腳的實(shí)際分配效率。

二分圖算法；蟻群算法；混合算法；FPGA引腳

0 引言

ASIC按照制造工藝、設(shè)計(jì)思路和作用的不同可分為：(1)定制型ASIC (2)半定制型ASIC (3)可編程邏輯芯片ASIC，可編程邏輯器件經(jīng)歷了PAL、GAL、CPLD、FPGA幾個(gè)發(fā)展階段。目前可運(yùn)行加密算法的硬件實(shí)現(xiàn)分為兩種：一種是采用數(shù)字信號處理芯片DSP來實(shí)現(xiàn)，另一種是采用現(xiàn)場可編程門陣列邏輯芯片（FPGA）來實(shí)現(xiàn)。DSP芯片上實(shí)現(xiàn)加密算法，在算法實(shí)現(xiàn)上比FPGA要復(fù)雜，成本也較高。采用在FPGA芯片上實(shí)現(xiàn)加密算法芯片可擦寫、允許無限次編程成本較低、開發(fā)設(shè)計(jì)的復(fù)雜程度也較低。FPGA的低功耗、可擦除、可重寫、高可靠性、開發(fā)周期短、開發(fā)軟件投入少、價(jià)格減低等優(yōu)點(diǎn)使得其占據(jù)了大部分的世界市場。FPGA生產(chǎn)廠家主要有ALTERA，賽靈思公司，LATTICE和ACTEL。每個(gè)廠家的產(chǎn)品都有各自的特色和適用領(lǐng)域。本文對主要對FPGA發(fā)明者賽靈思公司生產(chǎn)的FPGA引腳分配方法做性能分析并進(jìn)一步的優(yōu)化引腳分配方案。

1 FPGA引腳技術(shù)分析

1.1 賽靈思公司提供設(shè)計(jì)分析技術(shù)方案

賽靈思公司是可編程邏輯綜合解決方案的提供商。賽靈思公司提供的產(chǎn)品集成了FPGA開發(fā)需要的所有功能。賽靈思公司的提供的開發(fā)設(shè)計(jì)工具由初期的Foundation系列升級到現(xiàn)在ISE 9.1i系列，ISE是目前功能和效率較高的EDA開發(fā)設(shè)計(jì)工具集合。輸入工具包括HDL語音和ISE文本的輸入。其中實(shí)現(xiàn)包括翻譯、時(shí)序分析、管腳分配、映射、布局布線和增量設(shè)計(jì)等功能。下載功能可以將程序燒寫到FPGA芯片中去。在FPGA運(yùn)行時(shí)不同的管腳分配會影響FPFA的效率。

1.2 FPGA引腳分類和分配方式

FPGA的大部分引腳屬于“用戶引腳”用戶可以完全自定制用戶IO。在所有引腳中數(shù)目最多的是GPIO引腳，總共有640個(gè)。

定義引腳布局要求，一旦了解了主要的FPGA接口并創(chuàng)建了物理布局的原型，就可以定義引腳布局了。如果使用包含所有I/ O信號數(shù)據(jù)表來保持與引腳的對應(yīng)，可以按電壓、時(shí)鐘、接口或總線對它們進(jìn)行分組。這種方式在分配引腳時(shí)可以按組進(jìn)行。另外有些關(guān)鍵接口必須置于器件的某個(gè)邊，或者利用外部物理引腳。

在考慮到FPGA和PCB要求并確定了主要的接口位置以后，然后根據(jù)所有這些條件將引腳分配給I/O組。在設(shè)計(jì)流程中，引腳分配耗費(fèi)時(shí)間較多，尤其在性能和信號完整性方面。

2 二分圖匹配算法和蟻群算法的引腳分配

2.1 二分圖算法及其對應(yīng)的pin分配方式

二分圖算法：任意兩條邊不相交于同一頂點(diǎn)的邊數(shù)，用最少的點(diǎn)讓每一條邊都至少和其中的一個(gè)點(diǎn)相關(guān)聯(lián)。兩兩之間沒有邊的點(diǎn)的最大數(shù)量。（最小為圖中大的一個(gè)點(diǎn)集數(shù)）點(diǎn)數(shù)=總點(diǎn)數(shù)-最大匹配數(shù)。用最小不相交的路徑覆蓋有向無環(huán)圖的所有節(jié)點(diǎn)。通常將二分圖的問題轉(zhuǎn)化成網(wǎng)絡(luò)圖中的最大流問題，只需要將兩個(gè)頂點(diǎn)集的旁邊增加一個(gè)超級起點(diǎn)和一個(gè)超級終點(diǎn)即可，這樣就構(gòu)造出了網(wǎng)絡(luò)流圖，再利用二分圖的性質(zhì)將流量加上，即可將二分圖中的最大匹配數(shù)的求法轉(zhuǎn)化為網(wǎng)絡(luò)流圖中的最大流問題。

從實(shí)驗(yàn)中提取的數(shù)據(jù)可以用到二分圖匹配算法，得到引腳的的集合與位置的集合進(jìn)行建模分析。一般最佳匹配問題與引腳分配問題都需要首先求得最大匹配；另外他們有不同只出在于一般最佳匹配問題需要得出權(quán)和最大匹配，pin分配可以提高器件的工作頻率，所以找出延時(shí)最小引腳分配。求最大匹配算法是先找出全部匹配然后保留匹配數(shù)最多的的項(xiàng)目。通過對這些匹配的路徑比較，找出最大匹配，從而發(fā)現(xiàn)成本最小的匹配。

2.2 蟻群算法及其對應(yīng)的pin分配方式

蟻群算法,本質(zhì)上是一種并行算法。每個(gè)螞蟻搜索過程是相互獨(dú)立的,而且只有通過相互通信的信息激素.所以蟻群算法可以被視為一種分布式多代理系統(tǒng),在問題空間有更多的也開始獨(dú)立解決方案的搜索,不僅增加算法的可靠性,也使該算法具有很強(qiáng)的全局搜索能力。蟻群算法的正反饋,螞蟻可以找到最短的路徑,直接取決于最短路徑信息素積累,和信息素積累是一個(gè)正反饋的過程。蟻群算法初始路線不高,也就是說,蟻群算法的結(jié)果不依賴于初始路徑選擇,并在搜索過程中不需要人工調(diào)整如下圖1。其次,蟻群算法的參數(shù)的數(shù)量不多,很簡單,很容易適用于其它組合優(yōu)化問題。

圖1 蟻群覓食分布圖

蟻群算法在解決TSP問題中的時(shí)間復(fù)雜度和空間復(fù)雜度分別為T(n)=O(N?n2?m),

S(n)=o(n2)+O(n?m),其中n為TSP問題的規(guī)模,即節(jié)點(diǎn)數(shù)目；m為蟻群算法所采用的螞蟻數(shù)目,循環(huán)變量為Nc,最大循環(huán)次數(shù)為Ncmax。

蟻群算法的計(jì)算流程是：(1)初始化（2）為所有螞蟻設(shè)計(jì)下一個(gè)節(jié)點(diǎn)。（3）更新信息節(jié)點(diǎn)的矩陣（4）匹配終止條件（5）形成最優(yōu)值

FPGA的快速發(fā)展,導(dǎo)致規(guī)模和面積不斷增加,而系統(tǒng)功能復(fù)雜度的提高客觀上加重了布局布線階段的負(fù)擔(dān),致使仿真時(shí)間不斷變長,尋找一種能夠提高布局布線性能,大幅度縮短布局布線仿真時(shí)間的算法成為熱點(diǎn)問題。在傳統(tǒng)的SA布局算法中,前后兩次布局調(diào)整沒有信息量的繼承關(guān)系,因此不能有效利用前一次的有效信息。而蟻群算法在充分考慮啟發(fā)因子的同時(shí),利用了前一次尋找的有效信息,是一種新的實(shí)現(xiàn)FPGA布局布線的算法。

FPGA布局問題實(shí)際上就是一個(gè)二次分配問題(Quadratic Assignment Problem,QAP), 進(jìn)一步QAP問題就是要求使得各種路徑組合對應(yīng)的總代價(jià)最小。這樣就可以寫為。依據(jù)QAP問題的一般解法,解決FPGA布局問題的思路如下:FPGA布局問題實(shí)際上就是把電路網(wǎng)表文件中的n個(gè)子模塊放入m個(gè)CLB的過程,假設(shè)螞蟻的數(shù)量為a。按照蟻群算法的基本思想,QAP問題中一般選擇工廠作為蟻群算法中信息素的載體。對應(yīng)地,我們選擇CLB作為FPGA布局信息素的載體,并且每個(gè)CLB中具有n個(gè)分別對應(yīng)n個(gè)電路子模塊的信息素載體。n個(gè)信息素載體。當(dāng)螞蟻在尋找最優(yōu)布局時(shí),不在禁忌表中的而且對應(yīng)的信息素濃度相對最大的CLB被選為該子模塊放置的位置的概率最大。單純的蟻群算法實(shí)際上是一個(gè)隨機(jī)尋找的過程,會耗費(fèi)大量的優(yōu)化時(shí)間,我們必須指定一些優(yōu)化方向,結(jié)合FPGA布局的實(shí)際特點(diǎn),與別的模塊發(fā)生作用最多的哪個(gè)子模塊應(yīng)該防止在靠近FPGA中心位置的CLB上,依據(jù)這個(gè)思路,我們便可以設(shè)定啟發(fā)信息的表達(dá)式。

2.3 二分圖算法引腳分配和蟻群算法引腳分配的不足之處

二分圖算法來進(jìn)行引腳分配不一定能夠找出最小成本的引腳分配方案。

蟻群算法是雖然收斂速度加快了,但會使算法的全局性能降低,算法的穩(wěn)定性差,容易出現(xiàn)過早停滯現(xiàn)象。

3 基于混合優(yōu)化算法的引腳分配

針對二分圖算法在引腳分配和蟻群算法在引腳分配中的不足之處，對這兩種算法進(jìn)行融合，提出新的混合算法用于引腳的分配，新的算法具備較少的成本、硬件路徑最短、結(jié)點(diǎn)分布最優(yōu)、魯棒性較強(qiáng)，引腳分配速度快等優(yōu)點(diǎn)。混合算法基于最低開銷FPGA引腳分配算法和自學(xué)習(xí)型FPGA引腳分配算法。

3.1 混合優(yōu)化算法的原理

蟻群算法在運(yùn)算過程中尋求解決方案,主要反映在探索新路徑和使用歷史經(jīng)驗(yàn)之間的關(guān)系,找到最佳的解決方案是讓蟻群算法搜索空間盡可能大,以找到那些可能最優(yōu)解解決區(qū)間;同時(shí),還充分利用有效信息的蟻群,使得蟻群算法搜索重點(diǎn)放在那些可能具有高適應(yīng)個(gè)體的值的范圍內(nèi)。因此,更大的概率收斂到全局最優(yōu)的解決方案。

因此,在蟻群算法的基礎(chǔ)上,本文提出了一種新的算法——自主學(xué)習(xí)蟻群算法,該算法主要在以下方面的原始蟻群算法改進(jìn)了:

①改變局部更新策略.

②動態(tài)選取α值

③螞蟻每代初始位置隨機(jī)

④自適應(yīng)調(diào)整信息素?fù)]發(fā)因子ρ

所以，新的自學(xué)習(xí)性蟻群算法自我學(xué)習(xí)和組織的運(yùn)算效率高、魯棒性較強(qiáng)。

在自學(xué)習(xí)型蟻群算法的基礎(chǔ)上，還需要對蟻群尋找基于二分圖的最優(yōu)、最短、開銷最低的路徑進(jìn)行改進(jìn)。

最低開銷的二分圖算法正確性基于以下定理:

片刻思慮之后，他關(guān)閉了手機(jī)，此刻輕重緩急不言而喻。他打量自己在鏡前的面相，左看看右看看，除了膚色黑點(diǎn)并不見老，辛娜有時(shí)說到兒子的膚色是遺傳他，簡直是亂扣帽子，膚色黑也是前些年采購奔波使然，王樹林的父母都是皮膚偏白的中學(xué)老師。不惑之年，王樹林對自己的外形還是比較有自信的，雖然這兩年肚腩大了一圈。

若由二分圖中所有滿足A[ i ]+B[j]=w[i,j]的邊(i,j)構(gòu)成的子圖（稱做相等子圖）有完備匹配，那么這個(gè)完備匹配就是二分圖的最大權(quán)匹配。

把交錯(cuò)樹中X頂點(diǎn)的頂標(biāo)全都減小某個(gè)值d，Y頂點(diǎn)的頂標(biāo)全都增加同一個(gè)值d，那么會得到：

1）兩端都在交錯(cuò)樹中的邊(i,j)，A[ i ]+B[j]的值沒有變化。也就是說，它原來屬于相等子圖，現(xiàn)在仍屬于相等子圖。

2）兩端都不在交錯(cuò)樹中的邊(i,j)，A[ i ]和B[j]都沒有變化。也就是說，它原來屬于（或不屬于）相等子圖，現(xiàn)在仍屬于（或不屬于）相等子圖。

3）X端不在交錯(cuò)樹中，Y端在交錯(cuò)樹中的邊(i,j)，它的A[ i ]+B[j]的值有所增大。它原來不屬于相等子圖，現(xiàn)在仍不屬于相等子圖。

4）X端在交錯(cuò)樹中，Y端不在交錯(cuò)樹中的邊(i,j)，它的A[ i ]+B[j]的值有所減小。也就說，它原來不屬于相等子圖，現(xiàn)在可能進(jìn)入了相等子圖，因而使相等子圖得到了擴(kuò)大。（針對之后例子中x1->y4這條邊）

現(xiàn)在的問題就是求d值了。為了使A[ i ]+B[j]>=w[i,j]始終成立，且至少有一條邊進(jìn)入相等子圖，d應(yīng)該等于：

Min{A[i]+B[j]-w[i,j] | Xi在交錯(cuò)樹中，Yi不在交錯(cuò)樹中。

(1)初始化可行頂標(biāo)的值

(2)用匈牙利算法尋找完備匹配

(3)若未找到完備匹配則修改可行頂標(biāo)的值

(4)重復(fù)(2)(3)直到找到相等子圖的完備匹配為止

3.2 使用混合優(yōu)化算法模擬仿真

算法模擬是通過模塊化的步驟來進(jìn)行，模塊化的設(shè)計(jì)方法,模塊是指一組程序語句(或描述),包括輸入和輸出、邏輯功能,內(nèi)部信息和操作環(huán)境。模塊的輸入源和輸出一樣調(diào)用者在正常情況下,模塊。從調(diào)用者獲取輸入信息,經(jīng)過處理模塊,然后輸出給調(diào)用者。的邏輯功能模塊描述該模塊可以做什么樣的事情,它是什么功能的,也就是說,輸入信息可以加工成什么樣的輸出信息。模塊的內(nèi)部信息的指令和模塊運(yùn)行模塊。模塊的操作環(huán)境描述模塊的調(diào)用關(guān)系和調(diào)用模塊。

在系統(tǒng)級設(shè)計(jì),重要的是外部模塊的信息,也就是說,學(xué)習(xí)的功能模塊來完成,完成特定的功能如何實(shí)現(xiàn)在系統(tǒng)實(shí)施階段的Bw -蟻群算法處理過程是:基于閾值模型的蟻群搜索每個(gè)標(biāo)記的閾值規(guī)則結(jié)構(gòu)閾值候選方案。通過評價(jià)的評價(jià)函數(shù),加權(quán)信息元素和轉(zhuǎn)移概率更新和前輪定位世代在搜索空間越來越好,直到獲得最優(yōu)的解決方案。根據(jù)算法和硬件架構(gòu)的過程應(yīng)該是一個(gè)候選解決方案產(chǎn)生適應(yīng)治療,主要和轉(zhuǎn)移概率加權(quán)信息更新和硬件結(jié)構(gòu)的被動輪定位操作,所以根據(jù)實(shí)現(xiàn)的功能劃分為七個(gè)模塊,當(dāng)小模塊設(shè)計(jì)完成驗(yàn)證,然后組合成一個(gè)完整的設(shè)計(jì)。

4 總結(jié)

目前在FPGA銷分配問題主要是FPGA設(shè)計(jì)的發(fā)展和應(yīng)用的輔助和FPGA部分引腳分配.本文開發(fā)了一種對FPGA設(shè)計(jì)有用的引腳分配計(jì)算方法和過程。在本文中,我們研究了兩個(gè)方面:第一,研究不同的FPGA銷分布的影響在其頻率,另一個(gè)是基于以前的研究獲得銷的優(yōu)化配置方案。第一目標(biāo),通過研究FPGA的結(jié)構(gòu)和接口電路輸入和輸出滿足設(shè)計(jì)規(guī)則的引腳分配方案,優(yōu)化配置之間的銷和最壞的引腳分配,7%左右的頻率不同。第二目標(biāo),基于Xilinx FPGA結(jié)構(gòu)及其設(shè)計(jì)流程,利用ISE合成工具、仿真工具、位置和路由工具來到了實(shí)驗(yàn)數(shù)據(jù)。最后提出新的混合算法，新的算法基于二分圖最低算法和自學(xué)習(xí)型蟻群算法進(jìn)行研究。

這種新的混合算法用于解決FPGA引腳匹配的穩(wěn)定性、高效、最小開銷的問題，新算法只是做了初步研究，今后這方面的研究還有待深化。

[1] 李軍克．基于 FPGA 的 SoC/IP 驗(yàn)證平臺的設(shè)計(jì)與實(shí)現(xiàn)[D].哈爾濱工業(yè)大學(xué)研究生畢業(yè)論文．2006．

[2] 葉建軍．基于 FPGA 的低成本圖像采集處理系統(tǒng)的開發(fā)[D].北京郵電大學(xué)畢業(yè)論文．2007．

[3] 馬平．可重構(gòu)系統(tǒng)中的任務(wù)劃分和任務(wù)調(diào)度的研究[D].河北工業(yè)大學(xué)碩士畢業(yè)論文．2006．

[4] 奇海兵．自適應(yīng)濾波器算法設(shè)計(jì)及其 FPGA 實(shí)現(xiàn)的研究與應(yīng)用[D].中南大學(xué)碩士畢業(yè)論文．2006．

[5] 段海濱．蟻群算法原理及其應(yīng)用[M]．北京：科學(xué)出版社，2005．

栗磊（1980－），信陽農(nóng)林學(xué)院，男（漢族），河南信陽人，本科，實(shí)驗(yàn)師，主要研究方向：計(jì)算機(jī)應(yīng)用技術(shù)

Analysis and improvement of FPGA pin assignment scheme

Li Lei,Jiang Mingfu
（Xinyang College of Agriculture and Forestry，Xin Yang Henan,464000)

This paper studies two graph algorithm and ant colony algorithm, applied to the FPGA pin on the distribution,the two algorithms have advantages and disadvantages.This paper proposes a hybrid algorithm based on these two algorithms,to improve the efficiency of FPGA pin assignment.Verified that,hybrid algorithm can effectively improve the efficiency of the actual distribution of the FPGA pin.

two graph algorithm;ant colony algorithm;hybrid algorithm;FPGA pin