MPSoC軟硬件劃分的自動(dòng)波競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)算法

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

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

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

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

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

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

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

1 MPSoC軟硬件劃分問(wèn)題

1.1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

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

1.2 問(wèn)題定義

本文給出以上低功耗MPSoC軟硬件劃分問(wèn)題(簡(jiǎn)稱(chēng)MPSoC劃分)的形式化描述。

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

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

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

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

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

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

2 基于ACNN的MPSoC劃分算法

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

(1) 每個(gè)神經(jīng)元只點(diǎn)火一次；

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

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

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

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

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

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

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

下面給出采用ACNN求解MSCP問(wèn)題的步驟。

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

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

3 應(yīng)用實(shí)例

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

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

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

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

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

表2 ACNN神經(jīng)元點(diǎn)火與熄火過(guò)程

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

表3 ACNN與PCNN求解時(shí)間對(duì)比

4 結(jié) 論

針對(duì)基于可重用組件的MPSoC平臺(tái)中成本和實(shí)時(shí)性約束的低功耗軟硬件劃分問(wèn)題，本文提出了一種新的ACNN求解算法。

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

另外，本文雖然將功耗作為優(yōu)化目標(biāo)，將成本和時(shí)間作為約束條件，但也可將成本作為優(yōu)化目標(biāo)，功耗作為約束條件，由于MPSoC的總成本仍然具有累加性，則本文的算法仍然適用；將功耗、成本等特性分配相應(yīng)的權(quán)重，每個(gè)組件得到一個(gè)總的特性值，只要MPSoC的系統(tǒng)優(yōu)化目標(biāo)仍然是累加的，本文的算法同樣可用于此類(lèi)多目標(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] 董繼揚(yáng), 張軍英, 陳 忠. 自動(dòng)波競(jìng)爭(zhēng)神經(jīng)網(wǎng)絡(luò)及其在單源最短路問(wèn)題中的應(yīng)用[J]. 物理學(xué)報(bào), 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.