黃式東　劉勇　姚建峰　薛瑞

摘要：可重構(gòu)陣列通過重構(gòu)的方式實現(xiàn)其高容錯能力，不同的重構(gòu)方案對其性能有著重要的影響。該文基于貪心算法的應(yīng)用，針對可重構(gòu)電路的重構(gòu)優(yōu)化問題，實現(xiàn)了基于貪心思想的重構(gòu)優(yōu)化算法，并與同步優(yōu)化算法在性能上進行了對比。實驗表明，基于貪心的重構(gòu)優(yōu)化算法在性能上具有一定的優(yōu)勢。

關(guān)鍵詞：可重構(gòu)陣列；貪心；優(yōu)化算法

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2017）13-0091-02

1概述

傳統(tǒng)的計算方式有兩種，一種是采用對通用微處理器進行軟件編程的方式；一種是采用ASIC的方式。軟件編程的方式通用性好，但運算速度不高；ASIC方式處理速度快，但只能針對特定的應(yīng)用，通用性不好。可重構(gòu)計算（reconfigurable eom-puting）是以上兩種求算方式的一種折中。這種求算方式是通過對結(jié)構(gòu)可變的硬件進行軟件配置，以適應(yīng)不同的應(yīng)用需求，故其既具有了軟件的靈活性，又具備了ASIC硬件的高速性。可重構(gòu)計算的思想最早由加利福尼亞大學洛杉磯分校的Estrin教授在其論文中提出。當時的計算機還是電子管計算機，電子存儲器也剛剛出現(xiàn)，計算機處理速度很慢，存儲容量也很小，因此許多算法是當時通用計算機所不能解決的。為了解決這些受限計算問題，其第一次提出了可重構(gòu)計算的思想，即設(shè)計一種可變的計算機體系結(jié)構(gòu)，通過特定的指令集配置，該計算機結(jié)構(gòu)可變?yōu)獒槍μ囟ㄋ惴ǖ膶Ｓ糜嬎銠C結(jié)構(gòu)。

剛開始可重構(gòu)設(shè)備是作為板路邏輯使用的，隨著發(fā)展，現(xiàn)在的可重構(gòu)硬件以不同的粒度出現(xiàn)在系統(tǒng)中，尤其是在片上系統(tǒng)中的使用越來越多了。主要是因為可重構(gòu)硬件的能夠提供彈性的功能，能夠減少設(shè)計開銷和投向市場的時間，并且在容錯方面有著更好的特性。主要的應(yīng)用在Software-defined ra-dio，醫(yī)學圖形圖像處理，網(wǎng)絡(luò)處理器，加解密M，科研數(shù)據(jù)獲取和處理，航天飛行器，機器人，汽車電子，圖像視屏處理設(shè)備等。除了這些特定領(lǐng)域的一些應(yīng)用，現(xiàn)在可重構(gòu)計算技術(shù)在通用計算領(lǐng)域的應(yīng)用也變得越來越廣泛。因為計算技術(shù)在人們生活中各個方面的滲透正在逐步的深入并在深刻地改變著人們的生活方式，同時也產(chǎn)了大量數(shù)據(jù)，為了支持計算技術(shù)進一步的方便人們的生活和處理這些海量信息，云計算技術(shù)在此背景下產(chǎn)生了。云計算技術(shù)中很多都使用了虛擬技術(shù)，如Ama—zon的EC2、微軟的Azure等。但虛擬技術(shù)同時帶來了性能的損失，云計算需要尋找新的出路一高效能，但是高效能的必然之路是體系結(jié)構(gòu)的創(chuàng)新。鄔江興院士在此背景下提出了基于認知的計算機體系結(jié)構(gòu)PRCA，該體系結(jié)構(gòu)使用的關(guān)鍵技術(shù)就是可重構(gòu)計算技術(shù)。按照不同的劃分標準，可重構(gòu)系統(tǒng)可以劃分為不同的類型。按照重構(gòu)的方式劃分可以分為靜態(tài)重構(gòu)和動態(tài)重構(gòu)；按照與主處理器的耦合關(guān)系劃分可以分為緊耦合重構(gòu)和松耦合重構(gòu)；按照重構(gòu)的粒度劃分可以分為細粒度重構(gòu)和粗粒度重構(gòu)。當然針對每種劃分方式也可以劃分的更細，如按照重構(gòu)粒度又可以劃分為電路級可重構(gòu)、芯片級可重構(gòu)、處理核級別的可重構(gòu)和節(jié)點級別的可重構(gòu)。電路級別的可重構(gòu)是從基本門級別人手的重構(gòu)，計算系統(tǒng)將功能部件的邏輯用FP-GA實現(xiàn)，當應(yīng)用算法改變時，通過改變FPGA的配置來改變其功能，這種重構(gòu)也稱為門級別可重構(gòu)。部件級可重構(gòu)是從功能部件如手，通過對功能部件的重新組合來適應(yīng)不同的計算需求。核級別可重構(gòu)在標準處理器單元的基礎(chǔ)上增加一些計算設(shè)備，為通用計算提供特殊的計算支持，以實現(xiàn)大計算量指令和子程序的執(zhí)行；或者是在多核互連的基礎(chǔ)上，使處理器位數(shù)可變、處理器的個數(shù)可變或處理器間互連結(jié)構(gòu)可變以達到重構(gòu)的目的。節(jié)點級別的可重構(gòu)是在多節(jié)點互連的基礎(chǔ)上，使節(jié)點的個數(shù)和互聯(lián)結(jié)構(gòu)可變以達到重構(gòu)的目的。

對于電路級可重構(gòu)，不同的重構(gòu)方案對計算性能有著重要的影響。原始物理陣列是一個4x5的陣列，如圖1所示，圖中的方格表示重構(gòu)單元，實心圓點表示開關(guān)，重構(gòu)單元之間通過線路和開關(guān)實現(xiàn)互通互聯(lián)。為了方便描述問題，此處省略了重構(gòu)單元之間的部分連線?，F(xiàn)對開關(guān)出現(xiàn)的位置信息進行編號，即行號，如圖1中1，2，3；重構(gòu)單元之間只經(jīng)過一個開關(guān)的連接稱為短連接，經(jīng)過兩個開關(guān)的連接稱為長連接，如圖1中x1，x2，x3。如果兩個重構(gòu)單元之間通過短連接進行互聯(lián)，那么它們之間的通信時間要比通過長連接實現(xiàn)互聯(lián)的重構(gòu)單元之間的通信時間要短，假設(shè)一個長連接比短連接多1個通信延遲，如果按照圖1中的重構(gòu)方案，因為3個長連接x1，x2，x3分別出現(xiàn)在不同的行中，這樣會造成增加3個通信延遲；如果按照圖2中的重構(gòu)方案，因為3個長連接x1，x2，x3都出現(xiàn)在同一行，最終造成只增加1個通信延遲。當陣列規(guī)模很大時，可見不同的重構(gòu)方案會造成很大的性能差異。現(xiàn)有多個長連接可以出現(xiàn)在多個位置（這里用行號表示）上，那么最終這些長連接如何分布，才能使電路性能達到最優(yōu)。關(guān)于貪心算法及其應(yīng)用，楊書影在文獻中進行了闡述；Chor Ping Low在文獻中介紹了貪心思想在可重構(gòu)電路優(yōu)化方面的應(yīng)用。張元瑞，武繼剛等人針對可重構(gòu)電路的優(yōu)化問題，提出了同步優(yōu)化算法；本文在同步算法問題表述形式的基礎(chǔ)上，采用貪心的優(yōu)化思想，實現(xiàn)可重構(gòu)電路的優(yōu)化算法，然后在性能上與同步優(yōu)化算法進行了比較，發(fā)現(xiàn)基于貪心的優(yōu)化算法在速性能上具有一定的優(yōu)勢。

2基于貪心重構(gòu)優(yōu)化算法

算法描述如下：

Algorithm Greed_OPT；/*貪心優(yōu)化算法。/

輸入：每個長連接及其分布情況；

輸出：優(yōu)化后長連接的分布情況；

Begin

（1）根據(jù)輸入，統(tǒng)計每個位置（行號）總共出現(xiàn)的次數(shù)；

（2）選取出現(xiàn)次數(shù)最多的行號；

（3）找出哪些長連接的位置包含該行號；如果包含，則把該長連接的最終位置記為該行號，然后在輸入中刪除該長連接及其分布信息，更新輸入后，轉(zhuǎn)到步驟（1），直到輸入中所有的長連接都被刪除，算法終止。

End

為了具體說明算法執(zhí)行過程，現(xiàn)舉例如下?，F(xiàn)有長連接{[X1]（2，3，4），[X2]（7，8），[X3]（4，5，6），[X4]（5，6，7），[X5]（4，5，6），[X6]（6，7，8）]，它們的具體分布情況如圖3所示。統(tǒng)計每個行號出現(xiàn)的次數(shù)，得到{1行→0次；2行→1次；3行→1次；4行→3次；5行→3次；6行→4次；7行→3次；8行→2次1。發(fā)現(xiàn)第6行出現(xiàn)的次數(shù)最多，然后把包含6的長連接在輸入中刪除，它們是[X3]（4，5，6），[X4]（5，6，7），[X5]（4，5，6），[X6]（6，7，8），刪除后新的輸入情況是{[X1]（2，3，4），[X2]（7，8）}；在新的輸入基礎(chǔ)上統(tǒng)計每個行號出現(xiàn)的次數(shù)，得到{1行+0次，2行→1次；3行→1次；4行→1次；5行→0次；6行→0次；7行→1次；8行→1次1；從中選取出現(xiàn)次數(shù)最大的為第2行（出現(xiàn)次數(shù)相同時，選擇行號最小的），刪除包含第2行的長連接[X1]（2，3，4），然后更新當前的輸入，得到{[X2]（7，8）}；重復(fù)執(zhí)行上述過程，直到所有的長連接都被刪除，算法結(jié)束。采用貪心優(yōu)化算法，長連接的最終分布情況如圖4所示，表示為[X3，X4，x5，x6]（6），[X1]（2），[X2]（7）。

采用同步優(yōu)化算法na得到的最終分布情況是[X1，X3，X5]（4），[X2，X4，X6]（7）。長連接只需要分布在兩個不同的行中，是本實例的一個最優(yōu)解。

3實驗結(jié)果說明

測試機器處理器配置為4核Intel（R）Core（TM）i3-3240，內(nèi)存8GB，Windos7操作系統(tǒng)，在此平臺下進行的測試?？偟目芍貥?gòu)單元數(shù)為1千萬，分別比較了貪心優(yōu)化算法和同步優(yōu)化算法在長連接個數(shù)為10萬、20萬、30萬、40萬、50萬時的性能，結(jié)果如圖5所示。結(jié)果表明貪心算法在速度上有明顯的優(yōu)勢。從圖5可以看出，隨著長連接數(shù)目的增加，優(yōu)化算法所花費的時間基本上成線性增長，說明實驗結(jié)果能夠真實地反映實際情況。

4結(jié)束語

本文針對可重構(gòu)電路的優(yōu)化問題，詳細介紹了基于貪心的可重構(gòu)優(yōu)化算法，并與同步優(yōu)化算法做了性能比較，實驗結(jié)果說明基于貪心的優(yōu)化算法在性能上有明顯的優(yōu)勢，但是基于貪心的優(yōu)化算法得到長連接的最終分布情況不一定是最優(yōu)的?；谕絻?yōu)化算法得到長連接的最終分布情況是最優(yōu)的，但是在速度上沒有貪心優(yōu)化算法快。同時本文給出的優(yōu)化實例，只涉及了長連接的縱向移動，沒考慮長連接的橫向移動情況；擬計劃做進一步研究，同時還可以利用其他的優(yōu)化算法來解決重構(gòu)電路的重構(gòu)優(yōu)化問題。