基于多目標PSO算法的DSP防護優(yōu)化設計

,,

(西安電子科技大學 空間科學與技術學院,西安 710071)

0 概述

近年來,芯片朝著微型化、低功耗和高性能方向發(fā)展。然而在其性能得到提高的同時,微處理器的可靠性更容易受到外界環(huán)境的干擾,由此引發(fā)的軟錯誤已不可忽視[1-3]。文獻[4]通過故障注入法指出80%～90%的計算機故障由軟錯誤所造成;文獻[5]則預測軟錯誤將以每代8%的速度增長。可見,軟錯誤已成為阻礙計算領域發(fā)展的一個日益嚴峻的問題。

為消除軟錯誤對計算機的影響,研究者提出多種針對軟防護的容錯方式。不同的軟防護方法可以提高可靠性,但同時也會帶來代價開銷。文獻[6]指出,三模冗余可以提高系統(tǒng)可靠性,但冗余所引起的代價制約了并行計算的可擴展性;文獻[7]指出,冗余技術可使系統(tǒng)可靠性得到提高,但同時也會使資源開銷比原始電路增加200%;文獻[8]指出,漢明碼技術通過增加冗余代碼可實現(xiàn)抗干擾。由此可知,防護的可靠性與代價是對系統(tǒng)進行防護時面臨的一對矛盾。現(xiàn)有研究多數(shù)針對某種防護方法進行改進,研究如何提高防護的可靠性,降低額外代價,較少有針對系統(tǒng)防護組合的研究。文獻[9]提出了一種具有芯片級在線修復能力的強容錯TMR系統(tǒng)結構及設計方法;文獻[10]則針對軟件測試進行研究,將測試資源合理分配給系統(tǒng)的不同模塊,使系統(tǒng)可靠性和測試成本2個方面同時得到優(yōu)化。

在對系統(tǒng)進行軟防護的過程中,需要設計合適的算法提高可靠性并減少資源消耗。目前粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法主要針對連續(xù)空間,關于離散解的研究較少,用于求解防護模型的研究更少。例如:文獻[11]是對離散粒子群算法應用背包問題的研究;文獻[12-13]將離散粒子群算法應用于Web服務組合,算法復雜度較高;文獻[14]提出針對連續(xù)空間的PSO算法,同時設計空間超格和變異策略以提高算法收斂速度,保證解的均勻性與廣泛性。

本文以數(shù)字信號處理器(Digital Signal Processor,DSP) C6701芯片為研究對象,設計一種基于多目標PSO的DSP防護優(yōu)化方法。首先對系統(tǒng)程序進行模塊劃分,然后建立以功能模塊所采取防護方法構成的組合為自變量,以系統(tǒng)性能和代價為優(yōu)化目標的系統(tǒng)優(yōu)化模型,最后利用文獻[14]算法改進粒子群速度位置公式,使其可以求解本文模型。

1 系統(tǒng)防護優(yōu)化模型

為找到一種合適的系統(tǒng)防護組合優(yōu)化系統(tǒng)防護的可靠性及防護代價,需要建立與防護方法選擇有關的系統(tǒng)代價與性能的多目標優(yōu)化模型。為此,本節(jié)首先給出系統(tǒng)代價與可靠性的評估方法,然后結合模塊防護方案的選擇建立系統(tǒng)防護優(yōu)化模型。

1.1 系統(tǒng)代價和可靠性評估

根據(jù)系統(tǒng)模塊之間的拓撲關系計算系統(tǒng)的代價與可靠性,具體步驟如下:

1)模塊劃分。根據(jù)DSP匯編指令的特點[15]和基本塊的概念[16],對系統(tǒng)匯編代碼進行功能模塊劃分(每個功能模塊就是順序執(zhí)行的一段匯編代碼),將模塊編號為1～N。

2)根據(jù)模塊跳轉指令B跳轉到的模塊地址確定模塊之間的拓撲關系。

3)計算模塊的代價與可靠性。

(1)計算模塊M(M=1,2,…,N)的代碼量并做線性歸一化處理,歸一化后將模塊M代碼量記為CM。

(2)計算模塊M的執(zhí)行時間[17]并做線性歸一化處理,歸一化后將模塊M執(zhí)行時間記為TM。

(3)計算模塊M的可靠性[18],記為RM。

4)確定執(zhí)行路徑。根據(jù)模塊的拓撲關系,利用深度優(yōu)先搜索算法求系統(tǒng)的執(zhí)行路徑,每條路徑由部分功能模塊組成:p表示執(zhí)行路徑,S表示執(zhí)行路徑條數(shù)。如圖1所示,模塊1為起始模塊,模塊N為終止模塊,則模塊1→2→5→7→N為一條包含5個模塊的路徑,模塊1～模塊N的所有路徑條數(shù)即為執(zhí)行路徑條數(shù)。

圖1 模塊拓撲關系

5)計算系統(tǒng)代價與可靠性。

(1)計算系統(tǒng)代碼量C。系統(tǒng)代碼量為各個模塊代碼量之和:

(1)

其中,CM表示模塊M的代碼量。

(2)計算系統(tǒng)執(zhí)行時間T。系統(tǒng)執(zhí)行時間為各路徑執(zhí)行時間的均值,而單條路徑各功能模塊為級聯(lián)的方式,因此,單條路徑執(zhí)行時間為該路徑模塊執(zhí)行時間之和:

(2)

(3)計算系統(tǒng)可靠性R。系統(tǒng)可靠性為各路徑可靠性的均值,而單條路徑各模塊為級聯(lián)的方式,因此,單條路徑可靠性為各個模塊可靠性的乘積:

(3)

通常人們只會關注系統(tǒng)代價和可靠性。代價和可靠性為2個目標,因此,本文將各個代價的加權平均看作一種代價。系統(tǒng)代碼量加權系數(shù)為a,系統(tǒng)時間量系數(shù)為b,且a+b=1,工程人員可以根據(jù)自己更看重的代價而調整加權系數(shù)。綜合式(1)～式(3)可以得到以下評估系統(tǒng)代價、可靠性的模型:

(4)

其中,g1表示系統(tǒng)代價,g2表示系統(tǒng)可靠性。

1.2 多目標系統(tǒng)防護組合模型

對系統(tǒng)中的各個模塊進行防護,可以選擇的防護方法有多種,如何為系統(tǒng)中的各個模塊選擇合適的防護方法,使得防護后系統(tǒng)的可靠性得到提高,并且使防護后系統(tǒng)的代價盡可能小,成為系統(tǒng)防護的關鍵。針對該問題,本文建立系統(tǒng)防護的多目標優(yōu)化模型,具體步驟如下:

1)根據(jù)各種模塊軟防護后代價和性能的變化特點,建立如下模型:

2)建立系統(tǒng)防護組合k=[k1,k2,…,kM,…,kN],其中,限制條件為{k|kM∈{1,2,…,Q}},kM表示標號為M的模塊采用編號為kM的防護方法。

3)建立系統(tǒng)自變量為k的多目標優(yōu)化模型,將加入防護后的各個模塊替換式(4)中模塊的數(shù)據(jù),可以得到系統(tǒng)代價和可靠性的多目標模型。同時,為與標準多目標優(yōu)化公式統(tǒng)一,以系統(tǒng)出錯率為優(yōu)化目標,系統(tǒng)出錯率為1減去系統(tǒng)可靠性,如式(5)所示。

(5)

2 改進的粒子群優(yōu)化算法

標準粒子群優(yōu)化算法的設計思想是:隨機初始化一群沒有質量和體積的粒子,將每個粒子看作待求問題的一個解,利用適應度函數(shù)衡量粒子的優(yōu)劣,所有粒子在可行解空間內按照位置速度公式更新自己的位置,追隨粒子最優(yōu)解,經過若干代搜索后得到該問題的最優(yōu)解[19]。粒子群優(yōu)化算法中粒子更新的運動方程[20]如下:

(6)

(7)

本文提出一種離散多目標粒子群優(yōu)化算法,基于自適應概率選擇機制進行粒子位置更新,使用粒子群優(yōu)化算法求解所構建的系統(tǒng)防護模型,使系統(tǒng)防護代價和性能2個目標函數(shù)盡量達到最優(yōu)。本文借用文獻[14]對連續(xù)空間的粒子群優(yōu)化所用的技術,其中包括內部種群用于存儲所迭代粒子的當前位置和個體歷史最優(yōu)位置,外部種群的存儲以自適應網格外部檔案維護的方式來盡量使Pareto面上的解分布均勻,提高種群多樣性。此外,本文對連續(xù)空間所用的位置速度公式和參數(shù)進行改進,使其可以求解所構建的離散空間模型。

2.1 內部種群

2.2 外部種群

2.3 粒子更新位置速度公式

2.3.1 參數(shù)定義

首先定義粒子自適應飛行參數(shù)λ=c1/c2以及ω。其中,c1表示粒子向個體歷史最優(yōu)位置變化的權重因子,c2表示粒子向全局歷史最優(yōu)位置變化的權重因子,ω表示粒子向一般位置(除個體歷史最優(yōu)及全局歷史最優(yōu)以外的位置)變化的權重因子。本文利用c1、c2、ω共同控制粒子位置的更新,定義公式如下:

c1+c2=1-ω

(8)

λ=c1/c2

(9)

經變形可以求得:

c1=(1-ω)-c2

(10)

(11)

模仿連續(xù)空間粒子群算法參數(shù)的設置方法,設置如下離散粒子群算法的參數(shù):

(12)

(13)

2.3.2 輪盤賭法實現(xiàn)

2.3.3 粒子更新

1)定義概率權重向量RM=[r1,r2,…,ri,…,rQ],其中,ri表示kM取值為i的概率權重,即模塊M的所有可用防護方法中第i種防護方法被選中的概率。

2.4 算法步驟

利用改進的粒子群優(yōu)化算法求解系統(tǒng)防護組合模型,具體步驟如下:

1)粒子群優(yōu)化算法位置編碼,構建防護方法組合k。

2)粒子算法參數(shù)設置,包括粒子群算法最大進化迭代次數(shù)G、參數(shù)λ0、λG、ω0、ωG。

3)初始化內部種群POP,隨機選擇L個步驟1)中防護組合作為內部種群。

4)評價內部種群,根據(jù)系統(tǒng)防護組合優(yōu)化模型,計算各個粒子2個目標函數(shù)f1(k)、f2(k)的值,并將兩者組合在一起作為POP中各粒子的適應值向量,進一步根據(jù)Pareto占優(yōu)準則評價內部種群POP中粒子對應的系統(tǒng)防護組合方法的優(yōu)劣。

5)初始化外部種群REP,將內部種群中各粒子進行兩兩比較,并根據(jù)Pareto占優(yōu)準則將內部種群中對應非劣解的所有粒子復制到外部種群REP中,完成對REP的初始化。

6)初始化內部種群中各個粒子的個體歷史最優(yōu)位置。將內部種群POP中的粒子依次復制到pbest中,得到POP中各個粒子的個體歷史最優(yōu)構成的種群pbest,完成對pbest的初始化。

7)更新內部種群。按本文粒子更新的公式進行內部種群更新。

8)重新評價內部種群。按步驟4)的方式重新評價內部種群。

9)更新外部種群。利用空間超格進行更新。

10)更新每個粒子的個體歷史最優(yōu)構成的種群pbest。如果內部種群POP中的某個粒子優(yōu)于其在pbest中的個體歷史最優(yōu)粒子,則用這個粒子替換pbest中該粒子的個體歷史最優(yōu)粒子;否則,pbest中該粒子的個體歷史最優(yōu)粒子保持不變。

11)判斷迭代是否到達G次,若未結束,則迭代次數(shù)加1并轉步驟7);否則迭代結束,將外部種群REP中的Pareto最優(yōu)解導出,作為系統(tǒng)防護組合的一組Pareto最優(yōu)解,該解集可用于指導最終防護方法的選擇。

3 實驗與結果分析

為了驗證本文建模與算法的可行性,分別針對多個DSP C6701的工程進行實驗并對結果進行分析。實驗中算法的相關參數(shù)設置為:防護方法種類Q為6,系統(tǒng)代價的權重系數(shù)a為0.5,b為0.5,空間超格劃分數(shù)目為15,自適應飛行參數(shù)λ取值0.8～0.2,ω取值0.95～0.5,均隨著進化代數(shù)線性變化,內部種群POP,外部種群REP大小均設置為60,迭代次數(shù)G設置為100。運行系統(tǒng)為ubuntu 16.04,64位操作系統(tǒng),8 GB運行內存,編譯運行軟件為qt5.5.0。

3.1 系統(tǒng)防護實驗

對在CCS上實現(xiàn)的DSP工程快速排序程序進行分析。該程序中有31個功能單元模塊,模塊編號為1～31,表1中列出了程序優(yōu)化前10個模塊的相關數(shù)據(jù),分別為各個功能單元模塊防護前的可靠性、代碼量、時間量,從而構成建模前的原始數(shù)據(jù)。

表1 快速排序功能模塊相關數(shù)據(jù)

本文對上述原始數(shù)據(jù)進行系統(tǒng)防護,得到優(yōu)化算法的實驗結果以及防護組合,分別如圖2、表2和表3所示。

圖2 快速排序防護優(yōu)化結果

表2 快速排序工程系統(tǒng)防護組合

表3 快速排序工程防護后相關數(shù)據(jù)

在圖2中,PF-0、PF-25、PF-50、PF-75、PF-100分別代表未進行系統(tǒng)防護的系統(tǒng)出錯率,以及系統(tǒng)加權代價和系統(tǒng)防護且算法迭代次數(shù)為25代、50代、75代、100代所形成的Pareto前沿。圖中每一個點對應一種防護組合,通過各個優(yōu)化結果的點可以看出,不同的防護組合,都會增加系統(tǒng)的代價開銷,降低系統(tǒng)的出錯率。PF-100線上有12個點,代表優(yōu)化到100代所得到的12種防護組合,并且系統(tǒng)防護效果好于其他迭代代數(shù)。

表2給出的12種系統(tǒng)防護組合對應圖2中的PF-100線上的12種防護組合(每種防護組合中的防護方法編號1、2、3、4、5、6分別對應無防護、關鍵指令的三模冗余、關鍵變量的三模冗余、模塊的時間冗余、模塊的時空冗余、關鍵變量的漢明碼這6種防護方法)。每種防護組合分別代表功能模塊1～模塊31所采用的防護方法,以表2中防護編號1為例,其表示對快速排序模塊編號為1～31的模塊依次采取防護方法編號為4、5、4、4、…、5、4對應的防護方法。

表3給出了采用表2系統(tǒng)防護組合所對應的數(shù)據(jù),包括系統(tǒng)可靠性、系統(tǒng)代價加權、代碼量和系統(tǒng)執(zhí)行時間,同時對應圖2中PF-100線上的12個點。

3.2 算法對比

由于粒子群優(yōu)化算法一般針對連續(xù)空間,目前對于離散算法的研究較少,雖然現(xiàn)已存在離散版二進制粒子群優(yōu)化算法BPSO[21]以及一些對該版本的改進方案用于求解組合優(yōu)化問題,但是這些算法的效果并不理想,另一方面也不適用于求解本文所構建的模型。為驗證本文所提粒子迭代更新公式的有效性,將對比實驗算法設置如下:

實驗1:應用本文設計的粒子迭代更新公式進行粒子尋優(yōu)位置的更新。

實驗2:不應用本文設計的粒子迭代更新公式,對粒子迭代更新的位置在可行解中隨機選取。

下面分別給出針對DSP C6701程序而設計的堆排序、FFT(64位快速傅里葉變換)和一個DSP與FPGA進行通信的系統(tǒng)進行實驗對比,以驗證本文方法的可行性。

在實驗對比中,堆排序的功能模塊數(shù)量較少,當優(yōu)化代數(shù)夠大時,實驗1與實驗2數(shù)據(jù)都會接近Pareto最優(yōu)面。從圖3中可以看出,實驗1數(shù)據(jù)略好于實驗2。圖4和圖5對應的64位快速傅里葉變換和通信系統(tǒng)都為200個～300個功能模塊數(shù)量,可以看出,改進粒子群優(yōu)化算法得到的實驗1數(shù)據(jù)明顯好于實驗2數(shù)據(jù),另外,由于改進的粒子群優(yōu)化算法需要迭代更新公式進行更新,時間會略微低于粒子更新時在可行解空間隨機產生粒子進行位置更新的時間,表4給出的運行時間也驗證了此結論,但是時間消耗在同一量級,影響不大。通過以上實驗可以看出,本文提出的改進離散粒子群優(yōu)化算法在一定程度上可以有效尋找最優(yōu)解。

圖3 堆排序工程防護優(yōu)化結果

圖4 FFT工程防護優(yōu)化結果

圖5 通信系統(tǒng)工程防護優(yōu)化結果

表4 實驗1與實驗2運行時間對比 s

4 結束語

本文針對系統(tǒng)軟防護引起的可靠性與代價這一矛盾,設計了基于粒子群優(yōu)化算法的DSP系統(tǒng)防護解決方案,以指導工程設計人員針對系統(tǒng)功能模塊進行防護方法的選擇。由實驗結果可知,本文針對系統(tǒng)各個模塊建立的以代價和可靠性為2個優(yōu)化目標,以各個模塊防護方案所組成的向量為自變量的模型,可以準確地反映出不同防護組合對應的系統(tǒng)代價和可靠性的關系。為求解所建模型,提出基于自適應概率選擇機制的離散多目標粒子群優(yōu)化算法,并通過實驗對比驗證了該算法的可行性與有效性。同時,從系統(tǒng)防護實驗的分析結果也可以看出,利用本文優(yōu)化方法選取的系統(tǒng)防護組合對系統(tǒng)進行防護,能夠得到比較滿意的系統(tǒng)可靠性和系統(tǒng)代價。

[1] BORKAR S.Designing reliable systems from unreliable components:the challenges of transistor cariability and degradation[J].IEEE Micro,2005,25(6):10-16.

[2] ZIEGLER J F.IBM experiments in soft fails in computer electronics(1978—1994)[J].IBM Journal of Research Development,1994,40(1):3-18.

[3] BAUMANN R C.Radiation-induced soft errors in advanced semiconductor technologies[J].IEEE Transactions on Device and Materials Reliability,2004,5(3):305-316.

[4] CLARK J A,PRADHAN D K.Fault:a method for validating computer system dependability[J].IEEE Computer,1995,28(6):47-56.

[5] SHIVAKUMAR P,KISTLER M,KECKLER S W,et al.Modeling the effect of technology trends on the soft error rate of combinational logic[C]//Proceedings of International Conference on Dependable Systems and Networks.Washington D.C.,USA:IEEE Press,2002:389-398.

[6] 王之元,楊學軍,周 云.大規(guī)模MPI并行計算的可擴展三模冗余容錯機制[J].軟件學報,2012,23(4):1022-1035.

[7] 張 超,趙 偉,劉 崢.基于FPGA的三模冗余容錯技術研究[J].現(xiàn)代電子技術,2011,34(5):167-171.

[8] 趙建武,周航慈.提高漢明碼對突發(fā)干擾的糾錯能力[J].單片機與嵌入式系統(tǒng)應用,2004,4(1):15-16.

[9] 姚 睿,王友仁,于盛林,等.具有在線修復能力的強冗余三模冗余系統(tǒng)設計及實驗研究[J].電子學報,2010,38(1):177-183.

[10] WANG Z,TANG K,YAO X.Multi-objective approaches to optimal testing resource allocation in modular software systems[J].IEEE Transactions on Reliability,2010,59(3):563-575.

[11] 劉建芹,賀毅朝,顧茜茜.基于離散微粒群算法求解背包問題研究[J].計算機工程與設計,2007,28(13):3189-3191.

[12] 范小芹,蔣昌俊,方賢文,等.基于離散微粒群算法的動態(tài)Web服務選擇[J].計算機研究與發(fā)展,2011,47(1):147-156.

[13] 于明遠,朱藝華,梁榮華.基于混合微粒群算法的網格服務工作流調度[J].華中科技大學學報(自然科學版),2008,36(4):46-47.

[14] COELLO C A C,PULIDO G T,LECHUGA M S.Handling multiple objectives with particle swarm optimization[J].IEEE Transactions on Evolutionary Computation,2004,8(3):256-279.

[15] Texax Instruments.TMS320C6000 CPU and instruction set reference guide[EB/OL].(2006-07-10)[2017-02-10].http://www.ti.com/lit/ug/spru189g/spru189g.pdf.

[16] AHO V A,SETHI R,ULLMAN J D.編譯原理[M].李建中,張守旭,譯.北京:機械工業(yè)出版社,2008.

[17] 周國昌,郭寶龍,高 翔,等.基于分布函數(shù)的WCET快速估計[J].計算機科學,2016,43(5):157-161.

[18] 唐 柳,黃樟欽,侯義斌,等.微處理器可靠性 AVF 評估方法研究綜述[J].計算機應用研究,2014,31(3):651-657.

[19] SALAZAR-LECHUGA M,ROWE J E.Particle swarm optimization and fitness sharing to solve multi-objective optimization problems[C]//Proceedings of 2005 IEEE Congress on Evolutionary Computation.Washington D.C.,USA:IEEE Press,2005:1204-1211.

[20] POLI R,KENNEDY J,BLACKWELL T.Particle swarm optimization:an overview[J].Swarm Intelligence,2007,1(1):33-57.

[21] KENNEDY J,EBERHART R C.A discrete binary version of the particle swarm algorithm[C]//Proceedings of IEEE International Conference on Systems,Man,and Cybernetics.Washington D.C.,USA:IEEE Press,1997:4104-4108.