李志軍, 王 昊, 馬鳴霄, 郭繼坤

(黑龍江科技學(xué)院 電氣與信息工程學(xué)院,哈爾濱 150027)

軟硬件協(xié)同設(shè)計(jì)中模擬退火劃分算法的改進(jìn)

李志軍, 王 昊, 馬鳴霄, 郭繼坤

(黑龍江科技學(xué)院 電氣與信息工程學(xué)院,哈爾濱 150027)

針對(duì)傳統(tǒng)軟硬件劃分算法對(duì)硬件資源的使用效率考慮不足的問題,提出改進(jìn)的模擬退火劃分算法。該算法對(duì)成本函數(shù)中的執(zhí)行時(shí)間和面積使用提供附加權(quán)、減少權(quán)值的動(dòng)態(tài)加權(quán)策略,并考慮了一個(gè)移動(dòng)的性能改變對(duì)系統(tǒng)面積的影響。實(shí)驗(yàn)表明,改進(jìn)的模擬退火劃分算法收斂速度快,得到的解更優(yōu),保證了系統(tǒng)硬件資源的有效利用。

軟硬件協(xié)同設(shè)計(jì);軟硬件劃分;模擬退火算法

0 引 言

軟硬件協(xié)同設(shè)計(jì)是 SOPC(System on a Programmable Chip)研究的一項(xiàng)重要內(nèi)容,廣泛存在于嵌入式系統(tǒng)、指令集體系結(jié)構(gòu) ISA和基于 IP的設(shè)計(jì)中。軟硬件劃分是確定系統(tǒng)功能用軟件實(shí)現(xiàn)或用硬件實(shí)現(xiàn)的過程,是軟硬件協(xié)同設(shè)計(jì)的一個(gè)關(guān)鍵步驟,劃分結(jié)果直接影響系統(tǒng)性能[1-2]。

軟硬件劃分問題的關(guān)鍵技術(shù)是多目標(biāo)優(yōu)化求解,即采用何種方法確定軟硬件劃分方案,以及如何評(píng)估劃分方案的優(yōu)劣程度。該問題屬于 NP-hard問題[3]。衡量劃分算法優(yōu)劣的關(guān)鍵指標(biāo)是成本、性能和硬件的面積。研究者可以通過將對(duì)象的功能移到硬件、把對(duì)象移出硬件等方式達(dá)到提高性能、減少硬件面積的目的,但成本函數(shù)優(yōu)化卻不易實(shí)現(xiàn)。它是一個(gè)復(fù)雜的、啟發(fā)式的權(quán)和過程。文獻(xiàn)[4]提供了模擬退火和禁忌搜索兩種啟發(fā)式算法。文獻(xiàn)[5]采用模擬退火算法進(jìn)行軟硬件劃分,并通過隨機(jī)選定源節(jié)點(diǎn)和目的節(jié)點(diǎn)來實(shí)現(xiàn)系統(tǒng)的空間設(shè)計(jì)。該文獻(xiàn)采用傳統(tǒng)方法接受和拒絕節(jié)點(diǎn)的移動(dòng),沒有考慮硬件資源的利用效率和任務(wù)的關(guān)鍵性?；诖?筆者考慮成本函數(shù),提出了改進(jìn)的模擬退火劃分算法,以提高軟硬件劃分算法對(duì)硬件資源的使用效率。

1 模擬退火算法原理

模擬退火算法來源于固體退火原理,即將固體加溫至充分高,再讓其緩慢冷卻。加溫時(shí),固體內(nèi)部粒子隨溫度升高變?yōu)闊o序狀,內(nèi)能增大,而緩慢冷卻時(shí)粒子漸趨有序,在每個(gè)溫度均能達(dá)到平衡態(tài),最后在常溫時(shí)達(dá)到基態(tài),內(nèi)能減為最小。根據(jù)Metropolis準(zhǔn)則,粒子在溫度T時(shí)趨于平衡的概率為 e-ΔE/(kT),其中,E為溫度T時(shí)的內(nèi)能,ΔE為其改變量,k為Boltzmann常數(shù)。用固體退火模擬組合優(yōu)化問題,將內(nèi)能E模擬為目標(biāo)函數(shù)值f,溫度T演化成控制參數(shù)T′,可得到解組合優(yōu)化問題的模擬退火算法,即由初始解i和控制參數(shù)初值T′開始,對(duì)當(dāng)前解重復(fù)“產(chǎn)生新解→計(jì)算目標(biāo)函數(shù)差→接受或舍棄”的迭代,并逐步衰減T′值,算法終止時(shí)的當(dāng)前解即為所得近似最優(yōu)解。這是基于蒙特卡羅迭代求解法的一種啟發(fā)式隨機(jī)搜索過程。退火過程由冷卻進(jìn)度表(Cooling Schedule)控制,該表主要控制參數(shù)初值T′、衰減因子ΔT′、每個(gè)T′值時(shí)的迭代次數(shù)n和停止條件S[4]。

模擬退火算法是一種以概率 1收斂于全局最優(yōu)解的全局優(yōu)化算法,具有漸近收斂性和并行性。

2 改進(jìn)算法

2.1 算法

文中改進(jìn)的模擬退火劃分算法如下:

UPDATE()(從退火表中);

估計(jì)平衡條件();

算法中提到的擾動(dòng)一般被定義為一個(gè)節(jié)點(diǎn)從軟件移動(dòng)到硬件或從硬件移動(dòng)到軟件。

典型的成本函數(shù)是歸一化的指標(biāo)的線性組合,文中只考慮執(zhí)行時(shí)間和硬件面積兩個(gè)指標(biāo)。

傳統(tǒng)模擬退火算法 (SA)的時(shí)間復(fù)雜性主要由成本函數(shù)的計(jì)算決定。每種劃分,計(jì)算系統(tǒng)的執(zhí)行時(shí)間時(shí)需遍歷整個(gè)模型圖,對(duì)節(jié)點(diǎn)多的復(fù)雜系統(tǒng)來說耗時(shí)太長。文中改進(jìn)的模擬退火算法是基于過程模型圖的,計(jì)算成本函數(shù)的時(shí)間改變只需要計(jì)算移動(dòng)節(jié)點(diǎn)的執(zhí)行時(shí)間改變及由于該節(jié)點(diǎn)的移動(dòng)而帶來的節(jié)點(diǎn)與相鄰節(jié)點(diǎn)之間的通信時(shí)間改變。移動(dòng)的成本函數(shù)可表示為

其中,Δt、ΔA分別為移動(dòng)引起的系統(tǒng)執(zhí)行時(shí)間變化和面積變化,A、B分別為它們的權(quán)。移動(dòng)引起的執(zhí)行時(shí)間變化Δt為

其中,X表示一種劃分,tX為對(duì)應(yīng)X的系統(tǒng)執(zhí)行時(shí)間,Xi表示節(jié)點(diǎn)i改用硬件實(shí)現(xiàn)的一種劃分,tXi為對(duì)應(yīng)Xi的系統(tǒng)執(zhí)行時(shí)間。節(jié)點(diǎn)從硬件移動(dòng)到軟件,系統(tǒng)執(zhí)行時(shí)間的變化值為 -Δt。由于移動(dòng)的平均計(jì)算成本很低,改進(jìn)的 SA算法可以對(duì)整個(gè)設(shè)計(jì)空間進(jìn)行快速估計(jì)。

2.2 成本函數(shù)

傳統(tǒng) SA算法在處理局部最優(yōu)時(shí),常將指標(biāo)靜態(tài)權(quán)的線性組合作為 SA算法的成本函數(shù),文中采用動(dòng)態(tài)權(quán)值的方法。

目前，沒有研究調(diào)查過病恥感在帕金森病患者整體健康中所起的作用，但有研究表明病恥感可以預(yù)測患者生活質(zhì)量變化[28]。且研究發(fā)現(xiàn)帕金森病患者的病恥感是決定患者健康相關(guān)生活質(zhì)量的關(guān)鍵因素，有較高病恥感的患者常伴有更嚴(yán)重的疾病程度、更多的運(yùn)動(dòng)困難以及生活質(zhì)量問題[4]。全面評(píng)估帕金森病患者的病恥感，可能有助于帕金森病患者的生活質(zhì)量研究和社會(huì)心理學(xué)干預(yù)研究。

2.2.1 動(dòng)態(tài)變化策略

傳統(tǒng)的 SA算法通過隨機(jī)選擇、以某種概率接受次優(yōu)的移動(dòng)來避免局部最小化。劃分的目標(biāo)是,在圖 1中找最左上角的一個(gè)點(diǎn),在面積限制條件下,使執(zhí)行時(shí)間最小、面積得到充分有效的利用。文中使用動(dòng)態(tài)權(quán)值的目標(biāo)是,明確強(qiáng)迫算法接受壞的移動(dòng),引導(dǎo)算法向更有潛力的設(shè)計(jì)點(diǎn)的方向進(jìn)行。同時(shí),以某一概率拒絕一些明顯好的、顯然被大多數(shù)啟發(fā)式方法接受的移動(dòng),比如,當(dāng)離最優(yōu)目標(biāo)很遠(yuǎn)時(shí),不接受硬件面積消耗大而執(zhí)行時(shí)間提高較少的移動(dòng)。

對(duì)給定的一個(gè)移動(dòng),按參數(shù)(執(zhí)行時(shí)間、硬件面積)定義這種改變的成本函數(shù)。一個(gè)移動(dòng)的執(zhí)行時(shí)間改變?chǔ)與一個(gè)移動(dòng)節(jié)點(diǎn)的執(zhí)行時(shí)間改變一樣,對(duì)于節(jié)點(diǎn)由軟件到硬件的移動(dòng),執(zhí)行時(shí)間thi和面積改變?chǔ)為正,而對(duì)于節(jié)點(diǎn)由硬件到軟件的移動(dòng),thi為負(fù)。

圖1 解空間Fig.1 Solution space

把劃分P中的節(jié)點(diǎn)vi從軟件移動(dòng)到硬件或從硬件移動(dòng)到軟件,產(chǎn)生一個(gè)新的劃分。這種移動(dòng)可以分為四種情況,如圖 2所示,P1表示移動(dòng)減少了執(zhí)行時(shí)間,增加了面積,落入(-t,+th)象限;P2表示一個(gè)節(jié)點(diǎn)由硬件移動(dòng)到軟件,改進(jìn)了執(zhí)行時(shí)間,減少了面積,落入(-t,-th)象限。P3、P4以此類推。

圖2 鄰域的移動(dòng)Fig.2 Neighborhood mobile

成本函數(shù)估計(jì)為A×Δt+B×ΔA,是一簡單直線。傳統(tǒng)的成本函數(shù)忽略了面積(只要面積滿足限制),使每個(gè)能改進(jìn)執(zhí)行時(shí)間的隨機(jī)移動(dòng)被以概率 1接受。對(duì)于圖 3中的移動(dòng),改進(jìn)算法的指標(biāo)加權(quán)采用如下動(dòng)態(tài)變化策略:

(1)對(duì)類似Px的移動(dòng)提供附加權(quán)。這類移動(dòng)執(zhí)行時(shí)間略有增加,但節(jié)省了大量硬件面積。傳統(tǒng)的模擬退火算法中成本函數(shù)忽略了面積,對(duì)這類移動(dòng)以概率接受,文中明確引入成本函數(shù)A×Δt+B× ΔA(A>>B),強(qiáng)迫接受這種移動(dòng)。

(2)對(duì)類似Py的移動(dòng)減小權(quán)值。移動(dòng)執(zhí)行時(shí)間略有改進(jìn),但消耗了大量的硬件面積。通過減少A的值,使探索向更有潛力的方向進(jìn)行。

圖3 成本函數(shù)Fig.3 Cost function

2.2.2 成本函數(shù)

成本函數(shù)主要考慮違背界限的影響,如當(dāng)一個(gè)移動(dòng)使硬件面積超出范圍限制時(shí),通過與超出界限成比例的因子懲罰這種移動(dòng)。這可以通過提高面積指標(biāo)的權(quán)來達(dá)到,如函數(shù)A×Δt+B×(Anew-Aconstr),B>>A。相似的,如果一個(gè)移動(dòng)從無效劃分到較小的劃分,通過低于這個(gè)范圍的比例因子對(duì)它進(jìn)行獎(jiǎng)勵(lì)。

當(dāng)距離界限很近時(shí),需要成本函數(shù)與元素表示的執(zhí)行時(shí)間有一個(gè)小的偏差,改進(jìn)算法的成本函數(shù)中,時(shí)間元素根據(jù)到界限的距離動(dòng)態(tài)權(quán)衡。實(shí)驗(yàn)證明,靠近界限區(qū)域,時(shí)間元素的理想權(quán)比成本函數(shù)提供的低。這樣,在很靠近界限的區(qū)域需要添加閾值區(qū)域,同時(shí)還需要在這個(gè)區(qū)域明確地為成本函數(shù)的執(zhí)行時(shí)間分配一個(gè)小的權(quán)。

代碼中,A1、A2根據(jù)到界限的距離動(dòng)態(tài)權(quán)衡,成本函數(shù)的硬件面積元素用面積限制歸一化。

2.3 關(guān)鍵參數(shù)

改進(jìn)算法中的關(guān)鍵參數(shù)包括溫度、停止標(biāo)準(zhǔn)、內(nèi)部循環(huán)。溫度由Tnew=α×T得到,其中控制參數(shù)α為常數(shù),介于 0.90～0.99之間,實(shí)驗(yàn)證明選擇 0.96時(shí)效果最佳。停止標(biāo)準(zhǔn)是個(gè)重要參數(shù),該算法中移動(dòng)停止的條件是移動(dòng)中的大多數(shù)不能對(duì)解有所改進(jìn)。停止標(biāo)準(zhǔn)與問題的規(guī)模有很大的關(guān)系。內(nèi)部循環(huán)即在每個(gè)溫度的多次迭代。實(shí)驗(yàn)證明在每個(gè)溫度單次迭代比多次迭代方法得到解的質(zhì)量低。

3 結(jié)果分析

圖 4為改進(jìn)模擬退火劃分算法和傳統(tǒng)模擬退火劃分算法的運(yùn)行結(jié)果比較。

圖 4 模擬退火劃分算法改進(jìn)前后的運(yùn)行結(jié)果比較Fig.4 Operation results comparison before and after improved s imulated annealing partition algorithm

從圖中可以看出,改進(jìn)模擬退火算法比傳統(tǒng)模擬退火算法收斂速度快,得到的解更優(yōu)。傳統(tǒng)模擬退火算法使用簡單的靜態(tài)加權(quán)指標(biāo)的線性組合,權(quán)值有很大主觀性。改進(jìn)的模擬退火劃分算法對(duì)成本函數(shù)中的兩個(gè)指標(biāo)——執(zhí)行時(shí)間和面積使用動(dòng)態(tài)加權(quán)的方法,通過動(dòng)態(tài)改變指標(biāo)的權(quán),對(duì)移動(dòng)進(jìn)行明顯的拒絕或接受,引導(dǎo)劃分向好的劃分方向移動(dòng),加快了算法的收斂速度,保證了系統(tǒng)資源的有效利用。另外,對(duì)成本函數(shù)的計(jì)算只考慮移動(dòng)對(duì)系統(tǒng)成本的改變部分,也節(jié)省了計(jì)算時(shí)間,加快了劃分速度。

4 結(jié)束語

筆者對(duì)傳統(tǒng)模擬退火劃分算法進(jìn)行了改進(jìn)。改進(jìn)算法對(duì)成本函數(shù)中的兩個(gè)指標(biāo)——執(zhí)行時(shí)間和面積使用動(dòng)態(tài)加權(quán)策略,并充分考慮了一個(gè)移動(dòng)的性能改變對(duì)系統(tǒng)面積的影響,從而保證了系統(tǒng)硬件資源的有效利用,加快了收斂速度。實(shí)驗(yàn)證明改進(jìn)的模擬退火劃分算法在執(zhí)行時(shí)間和劃分結(jié)果上優(yōu)于傳統(tǒng)模擬退火劃分算法。

[1] 詹瑾瑜.SoC軟/硬件協(xié)同設(shè)計(jì)方法研究[D].成都:電子科技大學(xué),2006.

[2] 王秀芹.軟硬件協(xié)同設(shè)計(jì)中的劃分算法研究[D].哈爾濱:哈爾濱工程大學(xué),2005.

[3] 王培東,徐海濤.遺傳退火算法在軟硬件劃分中的應(yīng)用[J].計(jì)算機(jī)工程,2009,35(15):179-181.

[4] ELES P,PENG Z,KUCHC INSKI K,et al.Hardware/software partitioning of VHDL system specifications[C]//Proceedings of EURODAC.USA:IEEE Computer Society Press Los Alamitos, 1996:176-178.

[5] BENO^ITM I RAMOND,JEAN MARC DELOS ME.Design space exploration method applied to a motion detection application[M]. EvryMars:[s.n.],2004:45-48.

[6] 劉志民.基于最大外權(quán)重的一種啟發(fā)式屬性約簡算法[J].河北工程大學(xué)學(xué)報(bào):自然科學(xué)版,2008(3):110-112.

Improved s imulated annealing partition algorithm for hardware and software co-design

L I Zhijun,WANG Hao,MA M ingxiao,GUO Jikun
(College of Electric&Infor mation Engineering,Heilongjiang Institute of Science&Technology,Harbin 150027,China)

Aimed at a solution to traditional hardware and software partitioning algorithm affected by the insufficient consideration of efficient use of hardware resources,this paper proposes an improved simulated annealing algorithm.The algorithm works by providing additional weighting and reducing the dynamic weighting strategy of theweight in execution t ime and area in the cost function,with the accompanying consideration of the effect of a moving perfo rmance changes on the system area.Exper iments show that the improved simulated annealing algorithm exhibits a faster convergence and better solutions,ensuring the efficient use of hardware resources.

hardware-software co-design;hardware-sof tware partitioning;s imulated annealing algorithm

TP301.6

A

1671-0118(2011)02-0138-04

2011-03-11

黑龍江省教育廳科學(xué)技術(shù)研究項(xiàng)目(11553109)

李志軍(1973-),男,黑龍江省龍江人,副教授,碩士,研究方向:嵌入式系統(tǒng)、數(shù)字信號(hào)處理,E-mail:zhijun-dl@163.com。

(編輯荀海鑫)