樹搜索優(yōu)化算法在FPGA中的應(yīng)用與實現(xiàn)①

陳建國， 方振國，*， 柏雪婷

(1.淮北師范大學(xué)物理與電子信息學(xué)院，安徽 淮北 235000；2.上海旗升電氣有限公司，上海 200000)

0 引 言

科技的發(fā)展帶動了集成電路集成度的提升，組合邏輯電路是集成電路的重要組成部分，所以對組合電路優(yōu)化的要求也隨之增加。在人工智能技術(shù)日驅(qū)成熟的環(huán)境下，將人工智能在集成電路設(shè)計上應(yīng)用具有光明的前景，而組合電路優(yōu)化是集成電路優(yōu)化的基礎(chǔ)，所以用人工智能完成組合電路的優(yōu)化是集成電路發(fā)展的又一次突破[1]。組合電路的傳統(tǒng)優(yōu)化算法包括公式法、卡諾圖法、Q-M算法，雖然這些算法可以對組合電路進行優(yōu)化，但它們都有各自的缺點，如公式法化簡過程較隨機，可能有多個結(jié)果，無法判定結(jié)果是否為最優(yōu)解；卡諾圖能夠快速的化簡邏輯表達式，但是當(dāng)輸入變量大于5之后復(fù)雜度呈指數(shù)上升，且不適合編程；Q-M算法是適用于計算機編程的化簡方式并且在前兩種方法的問題上有很大的優(yōu)勢，但是每次只能合并一項不同的邏輯表達式，增加了算法的冗余度[2]。人工智能理論應(yīng)用在硬件當(dāng)中可以解決很多大規(guī)模、復(fù)雜度不確定的問題。將人工智能中的樹搜索算法進行優(yōu)化應(yīng)用在組合電路優(yōu)化問題中，不僅解決了傳統(tǒng)優(yōu)化算法不易編程、計算量大、冗余度高等問題，而且在多輸入變量時優(yōu)化速度也會大大提升。因此本設(shè)計采用樹搜索算法優(yōu)化組合電路并在FPGA上實現(xiàn)，以最小項集合作為樹搜索的起始節(jié)點，并利用啟發(fā)式策略向下搜索，搜索完成后葉子節(jié)點的集合即組合邏輯電路的最簡邏輯表達式[3]。

1 組合電路最小項的概念

表1 五輸入一輸出真值表

如表1所示，隨機選擇了一個五輸入一輸出的組合邏輯電路的真值表，由真值表可以得出輸入變量與輸出變量之間的邏輯關(guān)系。把Y輸出為1的項稱為最小項，這些最小項的集合，能組成關(guān)于Y的邏輯表達式，如下

(1)

2 樹搜索優(yōu)化算法

傳統(tǒng)的蒙特卡洛樹搜索是通過構(gòu)造符合一定規(guī)則的隨機數(shù)解決一些數(shù)學(xué)上的問題，也應(yīng)用在棋盤游戲與即時電子游戲方面，樹搜索過程的每個循環(huán)主要包括選擇、拓展、仿真、反向傳播這四個步驟，從根節(jié)點開始在啟發(fā)式策略下向下搜索，選擇合適節(jié)點向最優(yōu)化方向拓展，若搜索到最優(yōu)解搜索結(jié)束,否則向下拓展一個或多個節(jié)點，然后從拓展的節(jié)點中選擇一個進行仿真，即進行隨機游戲，最后是反向傳播更新隨機游戲的結(jié)果與路徑信息。

樹搜索算法在組合電路優(yōu)化上的應(yīng)用需要對傳統(tǒng)的樹搜索算法進行改進，每個循環(huán)包括的步驟有優(yōu)化、選擇、拓展、反向傳播。將邏輯表達式的最小項集合作為根節(jié)點，組合電路邏輯表達式中的每一項設(shè)為節(jié)點，最簡邏輯表達式為樹搜索搜索完成后的葉子節(jié)點的集合。樹搜索在組合電路優(yōu)化過程的具體過程如下：首先是優(yōu)化，利用啟發(fā)式策略優(yōu)化搜索過程，即搜索同級節(jié)點中是否有相同節(jié)點，若有合并相同節(jié)點，若無進行選擇；選擇則是按順序的規(guī)則選擇節(jié)點進行拓展；拓展將節(jié)點中的某一項取反(將最小項中的某項字母取反)，然后搜索同級節(jié)點是否有相同項，若有去除取反字母并拓展為下級節(jié)點，若每個字母取反后都無則進入反向傳播；反向傳播即是把最后的葉子節(jié)點反饋，作為組成最簡邏輯表達式的一部分。

圖1 算法實現(xiàn)樹形圖

3 算法應(yīng)用

如圖1所示，是表1中的真值表對應(yīng)組合邏輯電路智能設(shè)計的過程，按照樹搜索算法實現(xiàn)的樹形圖，從圖1中可以清晰的看到各級節(jié)點以及葉子節(jié)點的情況[5]。標(biāo)紅的部分是同級節(jié)點中已有的相同項，當(dāng)該節(jié)點不是葉子節(jié)點時，這些節(jié)點往下拓展對應(yīng)的葉子節(jié)點與同級中的相同節(jié)點對應(yīng)的葉子節(jié)點相同，相同葉子節(jié)點組成的組合電路最簡邏輯表達式也是需要合并相同項的，所以同級中的相同節(jié)點只需保留一個；同理相同項節(jié)點為葉子節(jié)點時只需保留一個組成邏輯表達式即可[6]。

以表1對應(yīng)的真值表為例，邏輯表達式對應(yīng)為公式(1)，算法實現(xiàn)步驟如下：

(2)

4 算法實現(xiàn)

為驗證該方案，使用FPGA開發(fā)平臺進行驗證測試，使用Quartus II中的邏輯分析Signal Tap II來觀察各級節(jié)點數(shù)據(jù)以及優(yōu)化結(jié)果。首先是真值表的輸入，先輸入Y，然后對Y進行編碼就可以將Y對應(yīng)的邏輯表達式用二進制數(shù)組表示[9]。

圖2 編碼后的輸入(一級節(jié)點圖)

圖3 二級節(jié)點結(jié)果圖

如圖3所示和圖1中的二級節(jié)點相同，這是一輪優(yōu)化后的結(jié)果，g_2是節(jié)點數(shù)量，generation_2是用來存放二級節(jié)點的數(shù)組。從圖1與圖3可得一級節(jié)點中只有ABCDE(0000011111b)是葉子節(jié)點，ABCDE無法化簡，直接賦給最簡邏輯表達式數(shù)組中的generation[0]如圖5所示。當(dāng)然在這些二級節(jié)點中有很多是重復(fù)的節(jié)點，所以相同項的節(jié)點中分別只保留了一個，如圖1中標(biāo)紅部分(不進行繼續(xù)拓展的節(jié)點也不是葉子節(jié)點)[8]。

圖4 三級節(jié)點結(jié)果圖

圖5 葉子節(jié)點

如圖5所示，是組合邏輯電路優(yōu)化過程的結(jié)果，也是樹搜索過程中合并后的葉子節(jié)點的集合，g為優(yōu)化后邏輯表達式的項數(shù)，generation是存放葉子節(jié)點的數(shù)組，可得化簡后的邏輯表達式為式(2)，式(2)在功能上等價于最初的(冗長)等式(1)。

對輸入進行編碼后以二進制代碼的形式表示邏輯表達式，在FPGA上更易實現(xiàn)且速度更快，功耗更低[10]。為了驗證本算法的效率，分別對傳統(tǒng)算法和本文算法進行分析，數(shù)據(jù)如表2所示。

表2 算法比較

M代表輸入量數(shù)，N代表最小項個數(shù)。

5 結(jié) 語

樹搜索優(yōu)化算法應(yīng)用在組合電路優(yōu)化方面不僅克服了傳統(tǒng)優(yōu)化算法的不足，也在計算速度上體現(xiàn)了明顯的優(yōu)勢，特別是在多輸入變量的情況下。樹搜索算法優(yōu)化組合電路在FPGA上的實現(xiàn)與傳統(tǒng)算法相比較，證明了該算法具有速度快、空間復(fù)雜度低等特點。