基于多目標PSO算法的DSP防護優化設計

,,

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

0 概述

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

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

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

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

1 系統防護優化模型

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

1.1 系統代價和可靠性評估

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

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

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

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

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

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

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

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

圖1 模塊拓撲關系

5)計算系統代價與可靠性。

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

(1)

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

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

(2)

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

(3)

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

(4)

其中,g1表示系統代價,g2表示系統可靠性。

1.2 多目標系統防護組合模型

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

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

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

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

(5)

2 改進的粒子群優化算法

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

(6)

(7)

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

2.1 內部種群

2.2 外部種群

2.3 粒子更新位置速度公式

2.3.1 參數定義

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

c1+c2=1-ω

(8)

λ=c1/c2

(9)

經變形可以求得:

c1=(1-ω)-c2

(10)

(11)

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

(12)

(13)

2.3.2 輪盤賭法實現

2.3.3 粒子更新

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

2.4 算法步驟

利用改進的粒子群優化算法求解系統防護組合模型,具體步驟如下:

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

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

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

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

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

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

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

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

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

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

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

3 實驗與結果分析

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

3.1 系統防護實驗

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

表1 快速排序功能模塊相關數據

本文對上述原始數據進行系統防護,得到優化算法的實驗結果以及防護組合,分別如圖2、表2和表3所示。

圖2 快速排序防護優化結果

表2 快速排序工程系統防護組合

表3 快速排序工程防護后相關數據

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

表2給出的12種系統防護組合對應圖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系統防護組合所對應的數據,包括系統可靠性、系統代價加權、代碼量和系統執行時間,同時對應圖2中PF-100線上的12個點。

3.2 算法對比

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

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

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

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

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

圖3 堆排序工程防護優化結果

圖4 FFT工程防護優化結果

圖5 通信系統工程防護優化結果

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

4 結束語

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

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

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

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

[9] 姚 睿,王友仁,于盛林,等.具有在線修復能力的強冗余三模冗余系統設計及實驗研究[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] 范小芹,蔣昌俊,方賢文,等.基于離散微粒群算法的動態Web服務選擇[J].計算機研究與發展,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].李建中,張守旭,譯.北京:機械工業出版社,2008.

[17] 周國昌,郭寶龍,高 翔,等.基于分布函數的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.