基于云模型的程序時間性能評價方法

劉 瑋，李廣力，王冠成，崔天明+

(1.長春大學 旅游學院 基礎部，吉林 長春 130607；2.吉林大學 計算機科學與技術學院，吉林 長春 130012)

0 引 言

程序時間性能評價是軟件測試中非常重要的一個組成部分，對程序時間性能的評測有助于進一步提高軟件產品的質量。在程序執行過程中，運行環境往往會受到多方面因素的影響，導致程序的執行時間具有不確定性。同時，對于大型程序也很難采用多次執行計算平均值的方式來合理衡量程序的運行時間。云模型[1,2]是一種度量不確定性的定量-定性轉換模型，近年來被廣泛地應用在系統信任評估[3]、服務選擇[4]、不確定性語言和數值之間的轉換[5]、群體決策[6]、系統評價[7]、聚類分析[8]等諸多領域，利用云模型來對計算機程序時間性能進行評價是解決程序時間性能不確定性的一種新方法。

1 云模型理論

云模型理論[9,10]融合了模糊集和概率論的觀點，能夠很好地描述自然界中各種概念的不確定性，同時也體現了模糊性和隨機性之間存在的關聯。云模型是由李德毅院士在結合了概率論和模糊數學理論的基礎上，創立的一種通過特定結構算法構成的定性與定量概念轉換的模型。云模型能夠對自然界概念的不確定性進行描述，通過隨機性與模糊性的關聯，構成了概念在定性和定量之間的相互映射。

1.1 云的定義

“云”或“云滴”是云模型中的基本單元?！霸啤笔侵钙湓谡撚騏上的一個分布，用聯合概率(x,μ)來表示。x是論域中的一個定量值，μ表示該值的隸屬度或確定度，用來對某種傾向的穩定程度進行度量。

1.2 云的數字特征

在云模型中，用3個數據來對其特征進行表示[1]。

期望：期望是云在論域空間分布的期望，它是概念在整個論域空間中的中間值，是該概念中最具有代表性的一個樣本，一般使用符號Ex表示。

熵：熵用來表示概念的不確定程度，由模糊性和隨機性共同決定。隨機性的程度反映了云的離散程度，模糊性的程度反映了概念能夠接受的云取值的范圍。熵一般使用符號En表示。

超熵：超熵用來對熵的不確定性進行度量，它是熵的熵，體現了一個概念在論域空間中不確定程度的凝聚性，間接反映了云的厚度。超熵由熵的模糊性和隨機性共同決定，一般使用符合He表示。

1.3 云發生器

云發生器分為正向云發生器(CG)和逆向云發生器(CG-1)兩種，分別用來生成云滴和計算數字特征。正向云發生器根據云的3個數字特征(期望、熵、超熵)不斷產生新的云滴，它實現了概念從定性表示到一定范圍和分布的定量表示的過程。逆向云發生器是根據定量表示計算云模型的數字特征，從而轉換為定性表示的過程。

2 基于云模型的程序時間性能評價方法

程序時間性能評價在軟件測試過程中是不可或缺的一個組成部分，通常需要獲得較為準確的程序運行時間以便進一步對程序的性能進行評判。然而，由于計算機操作系統環境的復雜性，程序的運行時間往往具有不確定性，導致無法對程序時間性能進行準確的評判。針對以上問題，本文利用云模型完成程序運行時間從定量到定性評價的轉換，設計了一種基于云模型的程序時間性能評價方法。接下來，本文首先對當前程序時間性能評價中普遍存在的問題進行分析和討論，之后對基于云模型的程序時間性能評價方法進行闡述。

2.1 當前程序時間性能評價存在的問題

目前，對于程序時間性能的評價方法往往都是通過多次執行程序進行平均值計算從而獲得時間性能指標，之后利用指標進行分析，從而完成程序時間性能的評價。一方面，對于大型程序而言，運行一次程序的所需的時間較長，若多次執行，會導致測試的耗時過長；另一方面，由于計算機操作系統的復雜性，會導致多次執行程序時，得到的時間性能指標具有不確定性。

2.1.1 大型程序測試耗時過長

在對大型程序進行測試時，程序的測試時間往往是一個需要考慮的重要因素。執行一次大型程序往往要耗費幾個小時甚至幾天的時間，現有的程序時間性能評價方法往往采用多次執行程序取平均值的方法獲取時間性能指標，再對獲取到的指標進行分析得出結論，這導致了對大型程序測試的效率十分低下，延誤軟件項目整體的測試效率。

2.1.2 復雜運行環境導致的運行時間不確定性

在復雜的運行環境下，程序運行時間由很多因素決定，例如：數據傳輸、資源爭奪等。復雜的運行環境導致了程序運行時間的不確定性，這種不確定性對程序時間性能的評價存在較大影響。以LeNet神經網絡對某一特定圖片數據集進行預測的程序為例，如圖1所示，圖中包含程序10次運行時間數據，程序運行時間的平均值在圖中以虛線的方式表示出來。從圖中可以看出，該程序運行10次的時間并不穩定，較運行時間的平均值波動較大。這種普遍存在的現象對程序的時間性能評價是一個需要考慮的重要問題。

圖1 程序運行時間的不確定性

2.2 基于云模型的評價方法

針對以上問題，本文利用云模型，設計了一種程序時間性能評價方法。如圖2所示，該方法中包含了一個正向云發生器和一個逆向云發生器，首先通過執行程序獲得少量的程序運行時間數據傳入逆向云發生器產生相應的云數字特征，之后將云數字特征傳入正向云發生器生成更多的云數據，最后根據生成的云對程序時間性能進行評價。該方法的具體步驟如下，其中m和n為指定參數(本文將在實驗部分對m，n的取值問題進行探討)：

步驟1 獲取m數量的待評價程序的運行時間數據。

步驟4 以En為期望，以He2為方差，生成正態隨機數En′。

步驟5 以Ex為期望，以En′2為方差，生成正態隨機數x。

步驟7 若云滴數量達到預定數量n，結束；否則，返回步驟4繼續執行。

圖2 評價方法的整體框架

3 應用實例

為了說明本文提出的基于云模型的程序時間性能評價方法的實際應用效果，本文接下來將使用單程序時間性能評價和多程序時間性能比較兩個應用實例來進行驗證。待評價程序運行環境如下：①LeNet程序：Red Hat 4.4.7操作系統，Intel Xeon CPU，16G RAM；②Sharpness程序：CentOS 6.6操作系統，Intel Xeon CPU，32 G RAM。

3.1 單程序時間性能評價

單程序時間性能評價是對一個程序運行時間的衡量，本文選取LeNet程序進行應用實例驗證。參數設置為m=70，n=1000。

首先執行m次程序，記錄m次程序運行的時間。之后利用樣本數據計算云模型數字特征，見表1。

表1 數字特征

利用數字特征生成數量為n的云滴，結果如圖3所示。

圖3 LeNet云滴生成

對生成的云模型圖譜進行分析。首先需要觀察云模型的期望；其次是確定度，在圖譜中表現為云滴的集中程度，體現了一種傾向的穩定程度；最后是隨機性，體現了離群的程度。從圖3中可以看出，該程序的期望運行時間是在2 s 附近，生成的云滴較為集中，表示程序整體運行時間比較穩定。

為了與實際程序運行情況進行比較，執行程序1000次，生成頻數直方圖，如圖4所示。從圖4中可以看出，該程序的實際運行情況與評價的結果基本吻合。

圖4 LeNet頻數直方圖

3.2 多程序時間性能比較

多程序時間性能比較是對多個程序的運行時間進行比較，主要用于比較多個優化版本程序的優化效果。本文選取sharpness程序進行多程序時間性能比較的實例驗證。sharpness程序共有兩個SIMD優化的版本sharpness_SIMD1和sharpness_SIMD2，分別進行了不同的SIMD優化，評價的目標是找到運行時間最優的SIMD優化版本。參數設置為m=100，n=1000。

首先，每個程序執行m次，并記錄m此程序運行的時間，之后利用樣本數據計算云模型數字特征，見表2。

表2 數字特征

利用數字特征生成數量為n的云滴，最終結果如圖所示，圖5為sharpness原程序，圖6為SIMD1程序，圖7為SIMD2程序。

圖5 Sharpness程序云滴生成

圖6 SIMD1程序云滴生成

圖7 SIMD2程序云滴生成

從圖6、圖7中可以看出，SIMD1程序的優化效果明顯高于SIMD2程序的優化效果，但SIMD1程序的時間性能穩定性不如原程序和SIMD2程序，生成的云模型圖譜的云滴不是很集中。

3.3 本文方法與傳統方法的比較

傳統的程序時間性能評價方法是通過多次執行程序進行平均值計算從而獲得時間性能指標，之后利用指標進行分析，從而完成程序時間性能的評價。圖8對本文方法和傳統方法的評價結果進行了比較，該實驗使用了sharpness的SIMD1版本程序的采樣數據。

圖8 本文方法與傳統方法的結果比較

從圖8中可以看出，隨著待評價程序的樣本數量不斷增加，傳統方法和本文方法的評價結果都不斷趨于穩定，同時本文方法增加了對樣本數據的隨機性的考慮。在評價結果上來看，雖然本文方法和傳統方法的評價方式和評價結果略有不同，但兩者的整體趨勢和效果是相似的。

本文使用云模型設計了一種程序時間性能評價的方法，結合上文的應用實例和對比實驗圖表，總結該方法與傳統方法的對比情況見表3。

表3 本文方法與傳統方法的對比

在評價的核心方法上，本文的方法將云模型引入到程序時間性能評價中，充分挖掘了云模型在不確定性環境下的表示能力。在體現形式上，傳統方法的結果為平均數、中位數、方差等統計特征，而本文方法的結果為云滴生成圖，云滴生成圖能夠非常直觀地表達程序時間性能的分布，包括它的穩定性和集中區域，能夠讓使用者快速、直觀地了解到程序運行時間的總體情況。云模型能夠利用正向云發生器和逆向云發生器完成定性與定量之間的轉換，從而實現程序時間性能在定性和定量兩個方面的評價。傳統方法往往需要固定的待評價程序的樣本，在面對運行時間很長的大型程序時會消耗大量的時間，本文的方法只需要少量的待評價程序樣本即可很好地完成時間性能的評價。在執行時間方面，本文的方法相比較于傳統方法，主要增加的時間是在生成云滴的過程中。在總體評價效率上，因為傳統方法與待評價程序的運行時間有關，在面對運行時間較大的大型程序時效率較低，本文的方法只需少量樣本即可進行評價，有著很高的總體評價效率。

4 實驗評價

在實驗部分，本文對評價方法中的參數m和n對評價結果的影響進行測試。在模型中，m代表待評價程序的運行次數，n代表云滴的生成數量。

4.1 待評價程序運行次數對評價結果的影響

為了測試待評價程序運行次數對評價結果的影響，在本實驗中固定n值，對m取值為10,20,30,…,1000進行評價方法的測試，實驗結果如圖9所示。

圖9 待評價程序運行次數對評價結果的影響

圖9從上至下分別是n為100,200,400,800這4種情況下的實驗結果。從圖中可以看出具有較大n值的圖像曲線有著較少的波動，整體比較穩定，在n為600和800的情況下圖像已經差別很小，故最大n選為800。從待評價程序運行次數對評價結果影響的角度來看，最初在m較小時，因為待評價程序運行時間的樣本較小，所以評價的結果與整體情況有著一定的偏差，這導致了圖中曲線在m較小時出現了很大的波動情況。同時也可以看出，當m不斷增大時，評價結果會逐漸趨近于穩定。由此可見，在條件允許的情況下，m越大，評價方法的效果越好。

4.2 云滴生成數量對評價結果的影響

為了測試云滴生成數量對評價結果的影響，在本實驗中固定m的值，對n取值為100,200,300,…,10000進行評價方法的測試，實驗結果如圖10所示。

圖10 云滴生成數量對評價結果的影響

圖10從上至下分別是m為100,200,400,800這4種情況下的實驗結果。從圖中可以看出具有較大m值的圖像曲線也有著較少的波動，在n為600和800的情況下圖像差別很小，故最大m選取為800。從云滴生成數量對評價結果影響的角度來看，在n較小時，因為云模型圖譜中的云滴很少，并不能很好地表現出整個云模型的情況，導致評價的效果不是很好，有著較大波動，當n不斷變大以后，可以看到整體的趨勢變得穩定，此時評價效果已經基本穩定，此時再增加n的值也不會提高評價的效果。

5 結束語

本文提出了一種基于云模型的程序時間性能評價方法，該方法使用了云模型處理不確定性的優勢，改善了傳統的程序時間性能評價方法的不足，同時能夠很好地適用于大型程序的時間性能評估。實驗結果表明，本文提出的評價方法可以有效地應用在單程序性能評價和多程序時間性能比較。在下一步工作中，將在進一步提高程序時間性能評價效果的基礎上，考慮如何利用云模型來對程序的綜合性能進行評價。

[1]YE Qiong,LI Shaowen,ZHANG Youhua,et al.Cloud mo-del and application overview[J].Computer Engineering and Design,2011,32(12):4198-4201(in Chinese).[葉瓊,李紹穩,張友華,等.云模型及應用綜述[J].計算機工程與設計,2011,32(12):4198-4201.]

[2]FU Bin,LI Daoguo,WANG Mukuai.Review and prospect on research of cloud model[J].Application Research of Compu-ters,2011,28(2):420-426(in Chinese).[付斌,李道國,王慕快.云模型研究的回顧與展望[J].計算機應用研究,2011,28(2):420-426.]

[3]ZHANG Shibin,XU Chunxiang.Study on the trust evaluation approach based on cloud model[J].Chinese Journal of Computers,2013,36(2):422-431(in Chinese).[張仕斌,許春香.基于云模型的信任評估方法研究[J].計算機學報,2013,36(2):422-431.]

[4]WANG Shangguang,SUN Qibo,ZHANG Guangwei,et al.Uncertain QoS-aware Skyline service selection based on cloud model[J].Journal of Software,2012,23(6):1397-1412(in Chinese).[王尚廣,孫其博,張廣衛,等.基于云模型的不確定性QoS感知的Skyline服務選擇[J].軟件學報,2012,23(6):1397-1412.]

[5]ZHANG Qiuwen,ZHANG Yongzhi,ZHONG Ming.A cloud model based approach for multi-hierarchy fuzzy comprehensive evaluation of reservoir-indeced seismic risk[J].Journal of Hydraulic Engineering,2014,45(1):87-95(in Chinese).[張秋文,章永志,鐘鳴.基于云模型的水庫誘發地震風險多級模糊綜合評價[J].水利學報,2014,45(1):87-95.]

[6]WANG Jianqiang,PENG Juanjuan,ZHANG Hongyu,et al.An uncertain linguistic multi-criteria group decision-making method based on a cloud model[J].Group Decision and Negotiation,2015,24(1):171-192.

[7]DING Hao,WANG Dong.The evaluation method of water eutrophication based on cloud model[J].Acta Scientiae Circumstantiae,2013,33(1):251-257(in Chinese).[丁昊,王棟.基于云模型的水體富營養化程度評價方法[J].環境科學學報,2013,33(1):251-257.]

[8]Zhang Renlong,Shan Miyuan,Liu Xiaohong,et al.A novel fuzzy hybrid quantum artificial immune clustering algorithm based on cloud model[J].Engineering Applications of Artificial Intelligence,2014,35(1):1-13.

[9]Wang Guoyin,Xu Changlin,Li Deyi.Generic normal cloud model[J].Information Sciences,2014,280(1):1-15.

[10]SHEN Jinchang,DU Shuxin,LUO Yi,et al.Method and application research on fuzzy comprehensive evaluation based on cloud model[J].Fuzzy Systems and Mathematics,2012,26(6):117-123(in Chinese).[沈進昌,杜樹新,羅祎,等.基于云模型的模糊綜合評價方法及應用[J].模糊系統與數學,2012,26(6):117-123.]