常政威，謝曉娜，桑 楠，熊光澤

(1. 四川電力試驗研究院 成都 610072; 2. 電子科技大學(xué)計算機科學(xué)與工程學(xué)院 成都 610054; 3. 鄭州大學(xué)體育學(xué)院 鄭州 450044)

片上系統(tǒng)(system-on-chip，SoC)已廣泛應(yīng)用于網(wǎng)絡(luò)通信、信號處理、多媒體等嵌入式電子產(chǎn)品中，單處理器SoC無法滿足片上系統(tǒng)日益增長的功能和性能需求，多處理器SoC (multi-processor SoC，MPSoC)[1-2]成為高性能嵌入式系統(tǒng)發(fā)展的必然趨勢。目前，國際上已有多家公司建立了MPSoC平臺[2]，如Philips的Nexperia、TI的OMAP以及Xilinix的Vertex-II Pro。

為提高設(shè)計和生產(chǎn)效率，MPSoC基于設(shè)計重用的思想，普遍采用經(jīng)過預(yù)先驗證、測試的可交易組件，如軟件采用商業(yè)成品(commercial-off-the-shelf，COTS)構(gòu)件，硬件采用知識產(chǎn)權(quán)(intellectual property，IP)核。對于系統(tǒng)中的每個功能模塊，不同的提供商可能有不同的軟硬件組件解決方案以及不同的性能參數(shù)，如功耗、面積、成本、運行時間等。在設(shè)計過程中如何兼顧系統(tǒng)的功能需求和性能約束，確定各模塊的實現(xiàn)方式，使MPSoC的性能指標(biāo)最優(yōu)，即軟硬件劃分問題。

針對嵌入式系統(tǒng)軟硬件劃分問題，研究人員已提出了許多算法[3-6]，大都把軟硬件劃分看作二路劃分問題，將系統(tǒng)中的計算模塊劃分為軟件和硬件兩個子集。早期的嵌入式系統(tǒng)主要考慮“CPU+ASIC”的單一架構(gòu)，分配到CPU上的模塊用軟件方式執(zhí)行，否則為硬件。但是在MPSoC平臺中，系統(tǒng)結(jié)構(gòu)呈多元化，迫切需要面向MPSoC高效、自動化的劃分工具和算法。

脈沖耦合神經(jīng)網(wǎng)絡(luò)(pulse coupled neural networks，PCNN)是一種具有生物學(xué)背景的全新神經(jīng)網(wǎng)絡(luò)模型，已在圖像處理、模式識別和優(yōu)化等領(lǐng)域得到了廣泛的應(yīng)用[7]。文獻[8]借鑒PCNN中自動波產(chǎn)生與傳播的機理，進一步提出了用于求解最短路徑問題的自動波競爭神經(jīng)網(wǎng)絡(luò)(autowave competition neural networks，ACNN)。

本文針對基于可重用組件(軟件構(gòu)件和IP核)的MPSoC平臺，定義了系統(tǒng)成本和實時性約束的低功耗軟硬件劃分問題，將其轉(zhuǎn)化為一個有向圖中的多約束最短路徑問題，并提出了一種新的ACNN算法用于獲得問題的優(yōu)化解。最后，通過一個MPSoC實例驗證了算法的有效性和求解效率。

1 MPSoC軟硬件劃分問題

1.1 系統(tǒng)模型

如圖1所示，MPSoC平臺由一個或多個可編程的CPU、存儲器以及若干硬件單元即IP核組成。軟件保存在存儲器中，由CPU執(zhí)行。假設(shè)平臺中CPU與存儲器的數(shù)量已經(jīng)固定，可以滿足嵌入式應(yīng)用的計算和存儲能力需求，但單純用軟件方式無法滿足系統(tǒng)的性能需求，需要選擇若干IP核完成一些計算功能。本文對MPSoC的通信平臺不作考慮，計算節(jié)點間可采用總線、點對點或片上網(wǎng)絡(luò)等各種通信方式。

圖1 MPSoC平臺系統(tǒng)結(jié)構(gòu)

MPSoC應(yīng)用的設(shè)計需求用一個任務(wù)流圖表示，如圖2所示。任務(wù)流圖中的每個節(jié)點表示一個計算任務(wù)模塊，節(jié)點間的有向邊表示任務(wù)模塊之間的控制依賴關(guān)系。任務(wù)流圖中有一個入度為0的開始節(jié)點和一個出度為0的終止節(jié)點。從開始節(jié)點到終止節(jié)點之間的一條通路稱為系統(tǒng)的一次處理過程。

圖2 MPSoC應(yīng)用的任務(wù)流圖

對MPSoC軟硬件劃分問題作如下假設(shè)：

(1) MPSoC平臺有一個可供選擇的組件庫，每個組件是一個軟件構(gòu)件或IP核。

(2) 對于任意一個任務(wù)模塊，組件庫中包含多個可以實現(xiàn)對應(yīng)功能的組件。不同的組件執(zhí)行該任務(wù)有不同的性能參數(shù)，包括成本、運行時間和功耗。

(3) MPSoC的總功耗(成本)定義為所有任務(wù)模塊的功耗(成本)之和，即成本和功耗具有累加性。

(4) 一次處理過程的運行時間定義為其中所有任務(wù)的運行時間之和。MPSoC的運行時間定義為所有處理過程運行時間中的最大值。

(5) 給定任務(wù)流圖和組件庫，MPSoC低功耗軟硬件劃分問題就是在MPSoC總成本和實時性約束下，確定每個任務(wù)模塊采用具體的軟件(構(gòu)件)或硬件(IP核)組件實現(xiàn)，使得MPSoC的功耗最優(yōu)。

1.2 問題定義

本文給出以上低功耗MPSoC軟硬件劃分問題(簡稱MPSoC劃分)的形式化描述。

1.3 轉(zhuǎn)化為多約束最短路徑問題

根據(jù)MPSoC劃分的定義，可以構(gòu)造出一個賦權(quán)有向圖，將MPSoC劃分問題轉(zhuǎn)化為一個多約束最短路徑(multi- constrained shortest path，MCSP)問題，如圖3所示。

構(gòu)造賦權(quán)有向圖的具體規(guī)則如下。

(1) 每個組件Coreij對應(yīng)圖中的一個頂點，Corei中所有組件對應(yīng)的頂點排成一列。Coreij與下一列每個頂點Corei+1,k之間有一條有向邊連接，邊的權(quán)重為Pi+1,k，即Corei+1,k的功耗。

(2) 除此之外，增加起始頂點Start和目標(biāo)頂點End兩個虛擬頂點，頂點Start到Core1j(1≤j≤|Core1|)之間有一條有向邊，權(quán)重為P1i。Corenj(1≤j≤|Coren|)到頂點End之間有一條有向邊，權(quán)重為PEnd= 0。

圖3 由MPSoC劃分構(gòu)造的賦權(quán)有向圖

2 基于ACNN的MPSoC劃分算法

ACNN的相關(guān)概念如神經(jīng)元的激活勢U、閾值θ、輸出Y和自動波強度A以及自動波傳播機制參見文獻[8]，本文限于篇幅不再贅述。

(1) 每個神經(jīng)元只點火一次；

(2) 每個神經(jīng)元的閾值僅更新一次，從∞變?yōu)橐粋€具體的數(shù)值后，不再改變；

(3) 除Start外，每列神經(jīng)元均由上一列中的同一個神經(jīng)元點火。

為求解圖3中的MCSP問題，在自動波向目標(biāo)頂點End前進的過程中，必須考慮對應(yīng)路徑的約束條件。因此，在ACNN的每次迭代中，只有滿足約束的自動波才能繼續(xù)前進。不滿足約束的自動波要及時被剔除，才能確保網(wǎng)絡(luò)中強度較大或約束條件較輕的自動波有繼續(xù)競爭前進的機會。

為了提供對MCSP問題中各約束條件的支持，下面對ACNN進行重新設(shè)計。

(1) 一個神經(jīng)元在點火以后，可以再次“熄火”，即神經(jīng)元的閾值從一個具體的數(shù)值重置為∞。熄火后的神經(jīng)元可以再次點火，即一個神經(jīng)元可以多次點火和熄火。

(4) 當(dāng)End點火以后，獲得了一條滿足約束條件的路徑，但不一定是最優(yōu)的受約束路徑。為此，首先將End熄火，然后將上一列神經(jīng)元傳播來的相應(yīng)自動波強度也設(shè)置為∞，以便其他的自動波能夠繼續(xù)競爭前進。

當(dāng)神經(jīng)元I點火以后，由式(4)得到它向下一列各神經(jīng)元傳播的自動波強度。但是，若下一列的某神經(jīng)元不符合約束條件，則對應(yīng)的強度將置為∞。另外，當(dāng)下一列的神經(jīng)元被某自動波點火又熄火以后，也將對應(yīng)的自動波強度置為∞。若I產(chǎn)生的所有自動波強度都為∞，則該自動波已無法再前進，因此將I熄火。

下面給出采用ACNN求解MSCP問題的步驟。

//t：網(wǎng)絡(luò)的迭代時刻。

由以上算法可以遍歷所有從Start到End滿足約束條件的路徑，從而獲得最優(yōu)的MCSP，對應(yīng)地得到最優(yōu)的MPSoC劃分方案。為了減少ACNN的求解時間，也可以限定算法的最大迭代次數(shù)或Power的更新次數(shù)，獲得滿足約束的次優(yōu)解。

3 應(yīng)用實例

MPSoC平臺的組件庫以及由本實例所構(gòu)造的賦權(quán)有向圖參見文獻[10]。給定不同的系統(tǒng)成本和實時性約束，分別用ACNN求解從頂點Start到終點End的最短路徑，得到的優(yōu)化結(jié)果如表1所示。

表1 不同約束下的優(yōu)化結(jié)果

當(dāng)Cmax=1 500 元和Tmax=200 ms時，獲得的功耗最優(yōu)MPSoC劃分解為SP=(Core12, Core23, Core33,Core44, Core54, Core63)，對應(yīng)的功耗為1.53 W，除τ1外的任務(wù)模塊均采用硬件實現(xiàn)。

當(dāng)改變約束為Cmax=1 000 元和Tmax=700 ms時，ACNN獲得了另一個不同的MPSoC劃分結(jié)果，功耗為1.73 W。與上次的選擇不同，τ2和τ3用硬件實現(xiàn)，其他的4個模塊采用軟件實現(xiàn)。

以第2組約束為例，在ACNN首次獲得受約束路徑時，各神經(jīng)元的點火與熄火過程如表2所示。

表2 ACNN神經(jīng)元點火與熄火過程

文獻[10]提出一個采用PCNN的SoC劃分算法，同樣是基于自動波的傳播機制。用PCNN[10]求解表1中不同約束下的MPSoC劃分，獲得的結(jié)果與ACNN算法相同，但是要耗費數(shù)十倍的迭代時間，如表3所示。表中的求解時間以獲得受約束最優(yōu)路徑的網(wǎng)絡(luò)迭代次數(shù)表示。分析其原因，是因為PCNN中自動波在兩個神經(jīng)元間的傳播時間與神經(jīng)元間的連接強度成正比，求解效率較低。ACNN中，自動波在相連接神經(jīng)元間的傳播只需要一次迭代，與神經(jīng)元間的連接強度(對應(yīng)構(gòu)造圖中有向邊的權(quán)值)無關(guān)，所以求解速度很快。

表3 ACNN與PCNN求解時間對比

4 結(jié) 論

針對基于可重用組件的MPSoC平臺中成本和實時性約束的低功耗軟硬件劃分問題，本文提出了一種新的ACNN求解算法。

該文算法具有高度的并行性，ACNN無需訓(xùn)練和設(shè)置參數(shù)，可以獲得問題的全局最優(yōu)解。ACNN的網(wǎng)絡(luò)和神經(jīng)元結(jié)構(gòu)簡單，易于用VLSI硬件實現(xiàn)，可推廣到大規(guī)模的MPSoC系統(tǒng)設(shè)計中。如國外的研究人員已經(jīng)用電子陣列芯片實現(xiàn)了32×32的PCNN[7]。與PCNN相比，ACNN的神經(jīng)元結(jié)構(gòu)更簡單，更容易實現(xiàn)，可以顯著降低運行時間，具有較高的求解效率，是一個很有前景的優(yōu)化手段。

另外，本文雖然將功耗作為優(yōu)化目標(biāo)，將成本和時間作為約束條件，但也可將成本作為優(yōu)化目標(biāo)，功耗作為約束條件，由于MPSoC的總成本仍然具有累加性，則本文的算法仍然適用；將功耗、成本等特性分配相應(yīng)的權(quán)重，每個組件得到一個總的特性值，只要MPSoC的系統(tǒng)優(yōu)化目標(biāo)仍然是累加的，本文的算法同樣可用于此類多目標(biāo)的最優(yōu)軟硬件劃分。

[1] WOLF W, JERRAYA A A, MARTIN G. Multiprocessor system-on-chip (MPSoC) technology[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2008, 27(10): 1701-1713.

[2] JERRAYA A A, WOLF W. Multiprocessor systems on chips[M]. San Francisco: Elsevier Morgan Kaufmann, 2005.

[3] ARATO P, MANN Z, ORBAN A. Algorithmic aspects of hardware/software partitioning[J]. ACM Transactions on Design Automation of Electronic Systems, 2005, 10(1):136-156.

[4] ELES P, PENG Z, KUCHCINSKI K, et al. System level hardware/software partitioning based on simulated annealing and tabu search[J]. Design Automation for Embedded Systems, 1997, 2(1): 5-32.

[5] ZHANG Y, LUO W, ZHANG Z, et al. A hardware/software partitioning algorithm based on artificial immune principles[J]. Applied Soft Computing, 2008, 8(1): 383-391.

[6] GUO B, WANG D, SHEN Y, et al. Hardware-software partitioning of real-time operating systems using hopfield neural networks[J]. Neurocomputing, 2006, 69(16-18):2379-2384.

[7] JOHNSON J L, PADGETT M L, MICOM U S, et al. PCNN models and applications[J]. IEEE Transactions on Neural Networks, 1999, 10(3): 480-498.

[8] 董繼揚, 張軍英, 陳 忠. 自動波競爭神經(jīng)網(wǎng)絡(luò)及其在單源最短路問題中的應(yīng)用[J]. 物理學(xué)報, 2007, 56(9): 5013-5020.DONG Ji-yang, ZHANG Jun-ying, CHEN Zhong.Autowave-competition neural network and its application to the single-source shortest-paths problem[J]. Acta Physica Sinica, 2007, 56(9): 5013-5020.

[9] ZHAN J, XIONG G. Optimal hardware/software co-synthesis for core-based soc designs[J]. Journal of Systems Engineering and Electronics, 2006, 17(2): 402-409.

[10] CHANG Z, XIONG G. Hardware/software partitioning of core-based systems using pulse coupled neural networks[C]//Advances in Neural Networks, ISNN 2007. [S.l.]:[s.n.], 2007: 1015-1023.