張 辰，田 甜*，楊秀婷，鞏敦衛(wèi)

（1.山東建筑大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院，濟(jì)南 250101；2.中國礦業(yè)大學(xué)信息與控制工程學(xué)院，江蘇徐州 221116）

（?通信作者電子郵箱tian_tiantian@126.com）

0 引言

消息傳遞程序具有開發(fā)簡單、實現(xiàn)便捷、求解高效的特性，是一種應(yīng)用廣泛的并行程序?；诜植际酱鎯軜?gòu)，消息傳遞并行程序基于通信語句實現(xiàn)進(jìn)程之間的交互。通信是消息傳遞并行程序的主要特征體現(xiàn)，而通信測試的核心是高效生成覆蓋通信的測試數(shù)據(jù)。因此，研究通信覆蓋的測試數(shù)據(jù)生成問題對于消息傳遞并行程序的測試具有重要意義。

隨著程序規(guī)模的增大，進(jìn)程之間的通信愈加頻繁，這使得通信測試的難度不斷提高。因此，有必要研究有效的通信約減方法，從而降低覆蓋難度，提高測試效率。占優(yōu)關(guān)系具有減小問題規(guī)模、簡化問題求解步驟、提高問題求解效率等優(yōu)點，已在優(yōu)化問題的求解中得到了有效應(yīng)用。鑒于此，本文基于占優(yōu)關(guān)系約減覆蓋測試中的目標(biāo)通信，轉(zhuǎn)換通信約減問題為通信語句約減問題，利用語句占優(yōu)關(guān)系，對通信語句集進(jìn)行約減。然后，基于約減后的語句，選擇相關(guān)通信作為覆蓋目標(biāo)，使得覆蓋這些目標(biāo)的測試數(shù)據(jù)能夠覆蓋程序的全部通信。

本文的主要工作如下:1）給出通信約減問題的轉(zhuǎn)換理論，將通信約減問題轉(zhuǎn)換為通信語句約減問題；2）基于占優(yōu)關(guān)系約減通信語句集，進(jìn)而選擇目標(biāo)通信；3）將本文所提出的方法應(yīng)用到基準(zhǔn)程序，并與其他方法進(jìn)行對比，實驗結(jié)果驗證了本文方法的可行性和高效性。

1 相關(guān)工作

不同進(jìn)程或線程之間的通信始終是研究人員關(guān)心的關(guān)鍵問題。Itoh等［1］提出了涉及進(jìn)程間通信與同步的測試標(biāo)準(zhǔn)，即有序序列準(zhǔn)則（Ordered Sequence Criteria，OSC）。Lu等［2］針對并發(fā)程序交互空間龐大而難以被徹底搜索的問題，提出具有層次結(jié)構(gòu)的交互覆蓋標(biāo)準(zhǔn)，這些標(biāo)準(zhǔn)基于不同的并發(fā)故障模型設(shè)計。?erb?nu?? 等［3］研究了多線程系統(tǒng)的因果模型，并提出了一種模型檢測算法。Vakkalanka 等［4-5］開發(fā)了驗證工具ISP（In-Situ Partial order），以覆蓋每一個有效的線程交互。Siegel 等［6］提出了一個用于消息傳遞接口（Message-Passing Interface，MPI）并行程序的形式化驗證工具TASS（Toolkit for Accurate Scientific Software），使用顯式的狀態(tài)枚舉技術(shù)來處理由消息傳遞接口引起的不確定性。此外，Siegel等［7］還提供了一個已被廣泛應(yīng)用的基準(zhǔn)并行程序集。Gotovos等［8］提出了Erlang 程序的測試驅(qū)動開發(fā)方法，并實現(xiàn)了工具Concuerror，以盡早檢測并消除執(zhí)行過程中可能出現(xiàn)的絕大多數(shù)與并發(fā)相關(guān)的錯誤，該工具探索進(jìn)程交互并提供發(fā)生錯誤的詳細(xì)信息。Souza 等［9］關(guān)注不同進(jìn)程的線程之間數(shù)據(jù)流及其相關(guān)通信和同步操作，提出了新的結(jié)構(gòu)測試模型，用以捕獲并行和分布式應(yīng)用程序交互的數(shù)據(jù)流、控制、通信和同步信息。針對共享內(nèi)存系統(tǒng)，Huang［10］提出了一種新的無狀態(tài)模型檢測技術(shù)MCR（Maximal Causality Reduction），該技術(shù)能夠系統(tǒng)地探索與給定輸入相關(guān)的狀態(tài)空間，并提供最少的執(zhí)行次數(shù)，用以避免冗余的線程交互。Terragni 等［11］提出了一種基于覆蓋驅(qū)動的測試方法AutoConTest，該方法可以生成有效的并發(fā)測試代碼，從而實現(xiàn)共享內(nèi)存訪問的交互覆蓋。針對程序的并發(fā)特性，Nguyen 等［12］利用可參數(shù)化的代碼轉(zhuǎn)換，生成與原程序相比更簡單的程序?qū)嵗?，每個實例捕獲原程序交互的簡化集，通過并行地檢查實例以驗證并發(fā)程序。Melo 等［13］介紹了共享內(nèi)存覆蓋測試的標(biāo)準(zhǔn)，并給出了測試工具ValiPthread，對測試標(biāo)準(zhǔn)的成本、有效性和強(qiáng)度進(jìn)行評估。

上述研究主要考慮了進(jìn)程或線程的交互，但是沒有考慮進(jìn)程間交互覆蓋的約減問題。通信是消息傳遞并行程序進(jìn)程間交互的主要體現(xiàn)。本文基于消息傳遞并行程序，研究通信覆蓋的約減理論與方法，將通信約減問題轉(zhuǎn)換為通信語句的約減問題，求解通信語句集的約減集，進(jìn)而選擇相關(guān)的通信作為覆蓋目標(biāo)，以實現(xiàn)通信覆蓋的約減。

作為一種重要的軟件測試方法，結(jié)構(gòu)覆蓋測試要求生成覆蓋程序中某種元素的測試數(shù)據(jù)，如路徑覆蓋、語句覆蓋以及分支覆蓋等。將結(jié)構(gòu)覆蓋問題轉(zhuǎn)換為優(yōu)化問題，并采用進(jìn)化優(yōu)化方法求解上述問題，進(jìn)而生成期望的測試數(shù)據(jù)，成為目前軟件測試領(lǐng)域的重要研究方向之一。

當(dāng)目標(biāo)較多時，采用進(jìn)化優(yōu)化方法不利于提高覆蓋測試的效率。占優(yōu)關(guān)系能夠去除冗余目標(biāo)，簡化問題規(guī)模，提高測試的效率。針對語句覆蓋問題，姚香娟等［14］提出了基于目標(biāo)語句占優(yōu)關(guān)系的軟件可測試性轉(zhuǎn)換理論與方法，利用占優(yōu)語句代替原有目標(biāo)語句生成測試數(shù)據(jù)，以消除標(biāo)記變量帶來的不利影響。為減少弱變異測試中變異體的數(shù)量，張功杰等［15］提出了基于統(tǒng)計占優(yōu)分析的變異體約減方法，該方法利用變異前后的語句構(gòu)造變異分支，并通過占優(yōu)關(guān)系約減分支集合，得到約減后的變異體，進(jìn)而提高了變異測試效率。此外，田甜等［16］還將占優(yōu)關(guān)系用于并行程序的死鎖檢測。本文基于語句占優(yōu)關(guān)系，研究通信覆蓋的約減方法，以提高通信覆蓋測試數(shù)據(jù)的生成效率。本文方法將通信約減問題轉(zhuǎn)換為通信語句的約減問題，基于占優(yōu)關(guān)系對通信語句集進(jìn)行約減，進(jìn)而選擇目標(biāo)通信，以降低通信覆蓋測試數(shù)據(jù)的生成代價。

2 問題背景

2.1 基本概念

MPI并行程序利用通信函數(shù)實現(xiàn)進(jìn)程間的消息傳遞。發(fā)送函數(shù)MPI_Send 和接收函數(shù)MPI_Recv 是實現(xiàn)通信的兩個基本函數(shù)。圖1 列出了這兩個函數(shù)中的常用參數(shù)。其中:參數(shù)*buf表示數(shù)據(jù)緩沖區(qū)的起始地址；count表示數(shù)據(jù)個數(shù)；datatype表示數(shù)據(jù)類型；dest表示著數(shù)據(jù)的接收進(jìn)程，即目的進(jìn)程；tag和comm分別表示消息標(biāo)簽和通信域；接收函數(shù)中，參數(shù)source表示數(shù)據(jù)的發(fā)送進(jìn)程，即源進(jìn)程，當(dāng)source取MPI_ANY_SOURCE 時，該接收函數(shù)可接收任意源進(jìn)程的消息；*status記錄數(shù)據(jù)的接收狀態(tài)。

定義1通信語句。具有數(shù)據(jù)發(fā)送或接收功能的語句為通信語句，記為n。其中，發(fā)送數(shù)據(jù)的通信語句為發(fā)送語句；接收數(shù)據(jù)的通信語句為接收語句。

定義2通信。若i進(jìn)程中的一個發(fā)送語句ni?j發(fā)送的數(shù)據(jù)被k進(jìn)程中的接收語句nk?l所接收，則稱ni?j與nk?l構(gòu)成通信〈ni?j，nk?l〉。對于通信〈ni?j，nk?l〉，若nk?l指定了接收數(shù)據(jù)的源進(jìn)程，則稱ni?j與nk?l之間的通信為確定通信；若nk?l未指定接收數(shù)據(jù)的源進(jìn)程，并且能夠與多個發(fā)送語句通信，則稱ni?j和nk?l之間的通信為不確定通信，nk?l為不確定接收語句。

定義3不確定通信組（Ω）。當(dāng)存在數(shù)據(jù)源進(jìn)程為MPI_ANY_SOURCE 且消息標(biāo)簽相同的i(i＞1)條接收語句時，若存在j(j≥i)條發(fā)送語句，使得這i條接收語句均能接收這j條發(fā)送語句的數(shù)據(jù)，則稱由這些通信語句及其構(gòu)成的通信組成一個不確定通信組。其中，接收語句即為不確定接收語句，位于接收進(jìn)程；發(fā)送語句位于發(fā)送進(jìn)程。語句間的通信即為不確定通信。

定義4占優(yōu)。對于i進(jìn)程中的兩個通信語句ni?j和ni?k，若ni?j和ni?k構(gòu)成順序結(jié)構(gòu)，且ni?j位于ni?k之前執(zhí)行，則稱ni?j占優(yōu)ni?k，記為ni?j→ni?k。此時，若ni?j被執(zhí)行，則ni?k也必然被執(zhí)行。

定義5占優(yōu)關(guān)系圖（D）。D=(V(D)，E(D))，其中，V（D）表示圖的頂點集，E（D）表示圖的有向邊集。令頂點集V(D)=N∪{s，e}，其中，N為通信語句集，s和e分別是進(jìn)程入口和出口。對任意頂點vj，vk∈V(D)，若vj→vk且vj不被其他頂點占優(yōu)，則有向邊〈vj，vk〉∈E（D）。另外，稱vj和vk分別為D的占優(yōu)頂點和被占優(yōu)頂點。

定義6約減集。記集合R和N為被測程序的兩個語句集，令R?N，若以R為覆蓋目標(biāo)生成的測試數(shù)據(jù)集能夠覆蓋N，則稱R是N的約減集。

2.2 通信圖

控制流圖是測試人員與學(xué)者們分析程序經(jīng)常使用的一種抽象數(shù)據(jù)結(jié)構(gòu)。由于本文研究通信的覆蓋問題，對于通信語句及通信之間的關(guān)系分析是必不可少的工作。因此，本文基于控制流圖分析被測程序的通信關(guān)系。為了清楚地反映出同一進(jìn)程中通信語句間的執(zhí)行關(guān)系，以及不同進(jìn)程中通信語句間的通信，本文以通信語句為頂點進(jìn)行構(gòu)圖，使用通信圖輔助程序分析。

定義7通信圖（G）。以程序中的通信語句為頂點，以同一進(jìn)程中通信語句間的執(zhí)行關(guān)系為有向虛邊，以不同進(jìn)程中通信語句間的通信為有向?qū)嵾厴?gòu)成的控制流圖，稱之為通信圖。在通信圖中，每個進(jìn)程有各自的入口及出口。

針對位于順序結(jié)構(gòu)的通信語句，按照通信語句的執(zhí)行順序構(gòu)建其對應(yīng)的頂點，如圖2 所示。圖2～4 中，（a）圖是位于3種控制結(jié)構(gòu)的通信語句，（b）圖的每個頂點分別對應(yīng)（a）圖中的一條通信語句。

圖2 順序結(jié)構(gòu)Fig.2 Sequence structure

對位于每個分支中的首個通信語句，將其作為分支結(jié)構(gòu)前一個通信語句的分支頂點，分支中的其他通信語句按結(jié)構(gòu)依次構(gòu)建相應(yīng)的頂點，如圖3所示。

圖3 分支結(jié)構(gòu)Fig.3 Branch structure

對于循環(huán)結(jié)構(gòu)的通信語句，為了能夠清楚并且完整地體現(xiàn)結(jié)構(gòu)特點，借助于輔助頂點，使得循環(huán)中通信語句對應(yīng)的頂點介于兩輔助頂點之間，輔助頂點不具備通信功能，如圖4所示。

圖4 循環(huán)結(jié)構(gòu)Fig.4 Loop structure

考慮并行程序S，由num(num＞1)個進(jìn)程并行執(zhí)行，分別為S0，S1，???，Snum-1，記并行程序S={S0，S1，???，Snum-1}。

通信圖的構(gòu)建方法如下:首先，提取各進(jìn)程中通信語句對應(yīng)的頂點，并且根據(jù)通信語句之間的執(zhí)行關(guān)系構(gòu)建有向虛邊；然后，根據(jù)通信語句的參數(shù)信息，構(gòu)建頂點之間的有向?qū)嵾叀Ｓ纱说玫匠绦驅(qū)?yīng)的通信圖。

以圖5（a）的示例程序為例，該程序包含5個進(jìn)程，功能是求取6個數(shù)的最大值。

進(jìn)程S0通過n0-1分別向S1、S2和S3發(fā)送2 個數(shù)；S1、S2和S3通過n1-1、n2-1和n3-1接收，求取最大值后，通過發(fā)送語句n1-2、n2-2、n3-2或n3-3將最大值發(fā)送給S0；S0通過n0-2、n0-3和n0-4接收S1、S2和S3發(fā)送來的結(jié)果后，對前兩個數(shù)值求取最大值，并將該值與第三個數(shù)值通過n0-5或n0-6發(fā)給S4；S4通過n4-1接收數(shù)值，求取最大值并通過n4-2發(fā)送給S0；S0通過n0-7接收數(shù)值，最后打印輸出。其中，接收語句n0-2，n0-3和n0-4的消息源進(jìn)程為MPI_ANY_SOURCE，并且消息標(biāo)簽相同。也就是說，n0-2、n0-3和n0-4中的每一條語句都能夠接收來自發(fā)送語句n1-2、n2-2、n3-2和n3-3的消息，這些通信語句及其構(gòu)成的不確定通信組成不確定通信組。

示例程序的通信如圖5（b）所示。其中，頂點對應(yīng)圖5（a）中的進(jìn)程入口s、出口e及通信語句，如S1的頂點1 對應(yīng)n1-1。有向虛邊表示通信語句間的執(zhí)行，以〈n1-1，n1-2〉為例，它表示n1-2在n1-1之后執(zhí)行。有向?qū)嵾厔t對應(yīng)頂點間的通信，如〈n0-1，n1-1〉表示S0中n0-1發(fā)送的數(shù)據(jù)由S1的n1-1接收。

3 基于占優(yōu)關(guān)系的通信覆蓋約減方法

本文重點研究通信覆蓋的約減理論與方法，主要思路是:首先，轉(zhuǎn)換通信約減問題為通信語句約減問題；然后，利用通信語句的占優(yōu)關(guān)系，約減通信語句集；最后，基于約減后的通信語句選擇通信作為目標(biāo)通信集。

3.1 通信約減問題的轉(zhuǎn)換

由2.2 節(jié)得到的程序通信圖，可以清晰地看出通信與通信語句之間的對應(yīng)關(guān)系，基于該對應(yīng)關(guān)系，將通信的約減問題轉(zhuǎn)換為通信語句的約減問題。下面，針對確定通信和不確定通信兩種類型分別提出通信約減問題的轉(zhuǎn)換理論。

1）確定通信約減問題的轉(zhuǎn)換。

對于確定通信〈ni-j，nk-l〉而言，當(dāng)通信〈ni-j，nk-l〉的兩個通信語句ni-j、nk-l被覆蓋時，通信〈ni-j，nk-l〉產(chǎn)生，即通信〈ni-j，nk-l〉被覆蓋。因此，通信的產(chǎn)生與這兩個通信語句的覆蓋具有一致性，可以通過這兩個通信語句的覆蓋判定通信的覆蓋，從而通過約減通信語句實現(xiàn)通信的約減。也就是說，將確定通信的約減問題轉(zhuǎn)換為通信語句的約減問題。例如，在圖5 示例程序中，當(dāng)確定通信〈n0-1，n1-1〉的兩個通信語句n0-1和n1-1被覆蓋時，該通信即被覆蓋；當(dāng)所有確定通信相關(guān)的通信語句被覆蓋時，所有的確定通信即被覆蓋。

2）不確定通信約減問題的轉(zhuǎn)換。

在不確定通信組中，一個發(fā)送語句可以與多個接收語句通信，同樣地，一個不確定接收語句可以與多個發(fā)送語句通信。因此，當(dāng)不確定通信〈ni-j，nk-l〉的兩個通信語句ni-j和nk-l被覆蓋時，不能判定〈ni-j，nk-l〉被覆蓋。如圖5 示例程序中，n1-2可與n0-2、n0-3和n0-4通信，n0-2可與n1-2、n2-2和n3-2或n3-3通信，當(dāng)n1-2和n0-2被覆蓋時，不能判定〈n1-2，n0-2〉被覆蓋。影響不確定通信〈ni-j，nk-l〉覆蓋的因素為程序輸入及調(diào)度序列。調(diào)度序列指進(jìn)程的執(zhí)行順序。當(dāng)進(jìn)程調(diào)度遵循影響〈ni-j，nk-l〉覆蓋的調(diào)度序列時，若通信語句ni-j和nk-l被覆蓋，則不確定通信〈ni-j，nk-l〉被覆蓋。例如示例程序中，當(dāng)調(diào)度序列為S1S2S3時，若n0-2與n1-2被覆蓋，則不確定通信〈n1-2，n0-2〉被覆蓋。由此，將不確定通信的約減問題轉(zhuǎn)換為通信語句的約減問題。

進(jìn)程遵循某一調(diào)度序列時，將影響不確定通信組中多個通信的覆蓋。當(dāng)不同調(diào)度序列在某一位置上的進(jìn)程相同時，相同的通信被覆蓋。例如圖5 示例程序的調(diào)度序列:S1S2S3和S1S3S2，進(jìn)程S1的調(diào)度相同，所以，兩個序列均覆蓋通信〈n1-2，n0-2〉。受此啟發(fā)，本文通過算法1實現(xiàn)調(diào)度序列的約減。在算法1 中，遍歷通信語句，若該語句為不確定接收語句，則其屬于一個不確定通信組。將發(fā)送進(jìn)程的進(jìn)程編號按照大小排序并變換，得到該通信組的目標(biāo)調(diào)度序列集?？紤]所有不確定通信組，得到整個被測程序S的目標(biāo)調(diào)度序列集。

算法1 目標(biāo)調(diào)度序列集生成。

輸入 被測程序S；

輸出S的目標(biāo)調(diào)度序列集Δ。

3.2 目標(biāo)通信的選擇

將通信的覆蓋問題轉(zhuǎn)換為通信語句的覆蓋問題后，本節(jié)給出通信語句集的約減方法，基于約減后的通信語句，得到目標(biāo)通信集。基于通信語句的占優(yōu)關(guān)系，構(gòu)造占優(yōu)關(guān)系圖。由占優(yōu)定義可知，當(dāng)占優(yōu)頂點被執(zhí)行時，被占優(yōu)頂點也將被執(zhí)行。因此，占優(yōu)關(guān)系圖的占優(yōu)頂點組成了通信語句集的約減集，以占優(yōu)頂點為發(fā)送或接收語句的通信即為目標(biāo)通信。當(dāng)目標(biāo)通信被覆蓋時，以被占優(yōu)頂點為發(fā)送或接收語句的通信也將被覆蓋?；谡純?yōu)關(guān)系的通信約減算法如算法2所示。

算法2 基于占優(yōu)關(guān)系的通信約減。

輸入 被測程序S；

輸出 目標(biāo)通信集Φ={Φ0，Φ1，???，Φnum-1}。

3.3 實例分析

下面以圖5 中的示例程序為例，說明通過算法1 和算法2得到示例程序的目標(biāo)調(diào)度序列集和目標(biāo)通信集的過程。

基于算法1，在進(jìn)程S0中，n0-1是發(fā)送語句，因而繼續(xù)遍歷n0-2。根據(jù)通信圖可知，n0-2為不確定接收語句。分析可得n0-2所在Ω0的發(fā)送進(jìn)程數(shù)及進(jìn)程編號，分別為3 和（1，2，3），并且進(jìn)程編號按照大小排序得到ψ0=S1S2S3，ψ0加入Ψ0。將ψ0首位進(jìn)程移至最后得到ψ1=S2S3S1，ψ1加入Ψ0，同理可得ψ2=S3S1S2，并添加到Ψ0，至此調(diào)度序列變換結(jié)束。將Ψ0加入到Δ，并且不再遍歷n0-3和n0-4。由于n0-5、n0-6和n0-7不是不確定接收語句，因而S0遍歷結(jié)束。同理遍歷其他進(jìn)程中的通信語句。最終可得，目標(biāo)調(diào)度序列集Δ=｛S1S2S3，S2S3S1，S3S1S2｝。

示例程序的5 個進(jìn)程S0、S1、S2、S3和S4，對應(yīng)5 個通信語句集N0=｛n0-1，n0-2，n0-3，n0-4，n0-5，n0-6，n0-7｝、N1=｛n1-1，n1-2｝、N2=｛n2-1，n2-2｝、N3=｛n3-1，n3-2，n3-3｝和N4=｛n4-1，n4-2｝。

下面通過算法2，根據(jù)占優(yōu)關(guān)系得到示例程序的目標(biāo)通信集。借助于圖5（b）通信圖，首先，分析S0。以s為占優(yōu)頂點構(gòu)造D0。關(guān)于n0-1，由通信圖可知，n0-1與s構(gòu)成順序結(jié)構(gòu)，所以將n0-1作為D0的被占優(yōu)頂點。同樣地，n0-2，n0-3和n0-4為D0的被占優(yōu)頂點。對于n0-5，由于不被s占優(yōu)，所以構(gòu)造占優(yōu)頂點為n0-5的D1，并將n0-5添加到N0，將與n0-5相關(guān)的通信并入S0目標(biāo)通信集Φ0。類似地，構(gòu)造以n0-6為占優(yōu)頂點的D2。關(guān)于n0-7，則作為D0的被占優(yōu)頂點。至此，S0包含的占優(yōu)關(guān)系圖（圖6）構(gòu)造結(jié)束。R0=｛n0-5，n0-6｝，Φ0=｛〈n0-5，n4-1〉，〈n0-6，n4-1〉｝。

圖6 S0的占優(yōu)關(guān)系圖Fig.6 Dominant relation diagram of S0

類似地，可以得到S1、S2和S4的占優(yōu)關(guān)系圖，如圖7 所示。對應(yīng)地，約減集R1=?，R2=?，R4=?。目標(biāo)通信集Φ1=?，Φ2=?，Φ4=?。S3的占優(yōu)關(guān)系圖如圖8 所示，R3=｛n3-2，n3-3｝，Φ3=｛〈n3-2，n0-2〉，〈n3-2，n0-3〉，〈n3-2，n0-4〉，〈n3-3，n0-2〉，〈n3-3，n0-3〉，〈n3-3，n0-4〉｝。程序S的約減集R=R0∪R1∪R2∪R3∪R4=｛n0-5，n0-6，n3-2，n3-3｝?；赗中的通信語句得到目標(biāo)通信集Φ=｛〈n0-5，n4-1〉，〈n0-6，n4-1〉，〈n3-2，n0-2〉，〈n3-2，n0-3〉，〈n3-2，n0-4〉，〈n3-3，n0-2〉，〈n3-3，n0-3〉，〈n3-3，n0-4〉｝。

圖7 S1、S2、S4的占優(yōu)關(guān)系圖Fig.7 Dominant relation diagram of S1，S2 and S4

圖8 S3的占優(yōu)關(guān)系圖Fig.8 Dominant relation diagram of S3

上述分析可得到示例程序的目標(biāo)調(diào)度序列集和目標(biāo)通信集，能夠初步表明本文方法的可行性。下面通過實驗進(jìn)一步驗證本文方法的有效性。

4 實驗與結(jié)果分析

4.1 驗證問題

通過回答如下問題，驗證本文所提方法的性能:

1）以本文所提方法得到的通信作為覆蓋目標(biāo)，生成的測試數(shù)據(jù)能否覆蓋全部通信？

2）采用本文所提方法，能否提高通信覆蓋測試數(shù)據(jù)生成效率？

為驗證問題1），將本文方法生成的測試數(shù)據(jù)作為輸入，運行被測程序，通過通信的覆蓋情況回答本文方法的可行性。

為驗證問題2），記以全部通信作為覆蓋目標(biāo)的測試數(shù)據(jù)生成方法為方法A；將隨機(jī)選擇目標(biāo)通信的測試數(shù)據(jù)生成方法記為方法B；此外，將隨機(jī)選擇調(diào)度序列的測試數(shù)據(jù)生成方法記為方法C。比較本文方法與方法A、B 和C 的通信覆蓋率、成功率及測試時間，驗證本文方法的高效性。

4.2 實驗設(shè)計

結(jié)合驗證問題，選取以下7 個基準(zhǔn)并行程序作為被測程序，這些程序的基本信息如表1 所示。其中:Max 為圖5 示例程序，用于求取多個輸入值的最大值；Min 用于求取多個輸入值的最小值；Triangle 用于判斷輸入值中最大的3 個值能否構(gòu)成三角形及所構(gòu)成三角形的類型；Search 用于字符檢索；Adder_par 用于對多個輸入值的求和運算，Matmat_mw 用于兩矩陣相乘運算，這兩個程序均選自FEVS 基準(zhǔn)并行程序測試集［7］；IS_Mode 對輸入值進(jìn)行排序并統(tǒng)計眾數(shù)，該程序來自于基準(zhǔn)測試程序集NPB（NAS Parallel Benchmarks）［17］。這些被測程序具有不同的功能、屬性和測試難度，能夠用來有效評價不同的通信覆蓋方法。

表1 實驗程序的基本信息Tab.1 Basic information of experimental programs

采用本文方法對被測程序的通信實施約減。為了直觀地反映出通信的約減效果，分別計算各程序通信的減少比RA，計算式如下:

其中，M1、M2分別表示全部通信集的大小和目標(biāo)通信集的大小。

為了提高被測程序的覆蓋率，已有許多研究者提出了不同的測試數(shù)據(jù)生成技術(shù)，其中，遺傳算法的應(yīng)用最為廣泛［18］。本文方法與方法A、B和C均采用遺傳算法生成測試數(shù)據(jù)。遺傳算法的相關(guān)參數(shù)設(shè)置如下:最高迭代次數(shù)為500，種群規(guī)模為30，選擇操作為輪盤賭，單點交叉概率和單點變異概率分別為0.9 和0.3［19］。遺傳算法的個體包括被測程序的輸入數(shù)據(jù)和調(diào)度序列兩部分，采用二進(jìn)制編碼方式，通過分支距離［14］計算個體適應(yīng)值。

4.3 實驗過程

實驗環(huán)境配置如下:硬件為Intel Core i5 處理器、500 GB硬盤和8 GB 內(nèi)存；軟件采用Windows 10 操作系統(tǒng)、Visual Studio 2017 編譯器，以及消息傳遞接口標(biāo)準(zhǔn)工具M(jìn)icrosoft MPI v9.0.1。

實施本文方法時，首先，根據(jù)3.1 節(jié)提出的不確定通信處理策略（算法1），求解目標(biāo)調(diào)度序列集Δ。然后，結(jié)合通信圖，依據(jù)通信約減算法（算法2），約減被測程序的通信語句集，基于此，得到目標(biāo)通信集Φ。接著，基于目標(biāo)通信集Φ及目標(biāo)調(diào)度序列集Δ，運用遺傳算法生成測試數(shù)據(jù)。最后，將生成的測試數(shù)據(jù)作為輸入運行被測程序，判斷生成的測試數(shù)據(jù)是否覆蓋全部通信。

借由通信圖分析不確定通信組，得到全部調(diào)度序列集。在方法A中，以全部調(diào)度序列作為目標(biāo)調(diào)度序列集，依次覆蓋全部通信，用以驗證本文方法的高效性。為了保證實驗對比的公平性。在方法B 中，其目標(biāo)調(diào)度序列集Δ與本文方法相同，并且其目標(biāo)通信集的數(shù)量與本文方法也相同，用以驗證本文通信約減策略的重要性。在方法C 中，其目標(biāo)通信集Δ與本文方法相同，每次實驗以全部調(diào)度序列作為目標(biāo)調(diào)度序列集，用以驗證本文約減調(diào)度序列策略的必要性。針對方法A、B和C，基于各自的目標(biāo)通信集Φ和目標(biāo)調(diào)度序列集Δ分別運行遺傳算法生成測試數(shù)據(jù)。

考慮到遺傳算法的隨機(jī)性，每一方法均運行10 次，記錄每次實驗的通信覆蓋率及測試時間，并將各項記錄的平均值作為該測試方法的最終實驗結(jié)果。需要說明的是，一次實驗中若全部通信均被覆蓋，則視該次實驗為成功，成功率值指實驗成功的次數(shù)占總實驗次數(shù)的比值。

4.4 結(jié)果分析

采用本文方法對被測程序的通信、調(diào)度序列進(jìn)行約減，得到目標(biāo)通信集和調(diào)度序列集，如表2 所示。由表2 可以得出，相較被測程序的全部通信，本文方法選擇的目標(biāo)通信數(shù)量較少，目標(biāo)通信減少比為55.6%～99.6%，其中，Min、Triangle、Search、Adder_par、Matmat_mw和IS_Mode的通信減少比較高，而Max 的通信減少比相對較低，這是因為Max 的部分非被占優(yōu)通信語句位于不確定通信組，而不確定通信組中的每一通信語句都與多條通信相關(guān)，因此，依據(jù)算法2 得到的目標(biāo)通信數(shù)較多，使得減少比相對較低。

表2 實驗程序的約減情況Tab.2 Reduction situation of experimental programs

本文方法的目標(biāo)通信集、全部通信集以及對比方法全部通信集的平均覆蓋率如表3 所示?；诿看螌嶒灥耐ㄐ鸥采w率，得到所有測試方法的成功率，如表4 所示。表5 是不同方法的測試時間對比。

表3 不同方法的通信覆蓋率比較 單位：%Tab.3 Comparison of communication coverage ratio among different methods unit:%

表4 不同方法的成功率比較 單位：%Tab.4 Comparison of success rate among different methods unit:%

表5 不同方法的測試時間比較 單位：msTab.5 Comparison of testing time among different methods unit:ms

回答問題1）由表3 可知，當(dāng)被測程序目標(biāo)通信覆蓋率為100%時，全部通信覆蓋率同為100%。這表明以本文所提方法得到的通信作為覆蓋目標(biāo)，生成的測試數(shù)據(jù)能夠覆蓋全部通信，驗證了本文方法的可行性。此外，對于Triangle程序，由于在第3 次實驗中，有一條目標(biāo)通信沒有被覆蓋，導(dǎo)致當(dāng)次實驗的目標(biāo)通信及全部通信覆蓋率分別為75%和96.2%，其余9 次實驗的目標(biāo)通信及全部通信覆蓋率均為100%，因此，平均目標(biāo)通信覆蓋率和全部通信覆蓋率分別為97.5%和99.6%。

回答問題2）首先，對比本文方法與方法A。通過表3～4能夠看出，兩者均具有較高的通信覆蓋率和成功率，但是，表5 結(jié)果表明，本文方法的測試時間明顯少于方法A 的測試時間。因此，相較于方法A而言，本文方法能夠在不降低通信覆蓋率的前提下，減少的測試數(shù)據(jù)的生成時間最高達(dá)95%。

然后，對比本文方法與方法B。由表3～4 可知，本文方法的通信覆蓋率和成功率均高于方法B。這是因為本文方法基于占優(yōu)關(guān)系選取目標(biāo)通信，以此生成的測試數(shù)據(jù)能夠覆蓋全部分支通信，而方法B不能。因此，本文方法有效地提高了通信覆蓋率。表5 結(jié)果表明，相較方法B，本文方法在程序Min、Search、Adder_par、Matmat_mw和IS_Mode的測試時間較多，原因是，所選目標(biāo)通信包含覆蓋難度較大的通信，測試數(shù)據(jù)生成難度較高，因此時間消耗較多。但是正如前文所述，所生成的測試數(shù)據(jù)對全部通信的覆蓋率較高。

接著，對比本文方法與方法C。由表3～4 可知，方法C 取得了較高的通信覆蓋率和成功率。通過表5 進(jìn)一步分析發(fā)現(xiàn)，相較于方法C，本文方法的時間消耗普遍少于方法C。但本文方法在Adder_par 的時間消耗多于方法C?？赡艿脑蚴?，本文方法所選目標(biāo)調(diào)度序列集的性能不高。

綜上所述，采用本文方法，通過占優(yōu)關(guān)系得到合理的目標(biāo)通信，并在部分調(diào)度序列下，基于遺傳算法生成覆蓋目標(biāo)通信的測試數(shù)據(jù)，能夠在保證通信覆蓋率的前提下，減少測試數(shù)據(jù)生成時間，提高測試效率。

5 結(jié)語

本文研究了并行程序通信覆蓋的約減理論與方法。首先，將通信約減問題轉(zhuǎn)換為通信語句約減問題。然后，利用占優(yōu)關(guān)系對通信語句進(jìn)行約減，基于約減后的通信語句得到目標(biāo)通信，使得以這些通信為覆蓋目標(biāo)生成的測試數(shù)據(jù)能夠覆蓋全部通信。通過設(shè)定調(diào)度序列集，消除不確定通信對于通信覆蓋的影響；基于對通信語句的占優(yōu)關(guān)系分析，減少目標(biāo)通信的數(shù)量。實驗結(jié)果表明，以本文方法選擇的通信作為覆蓋目標(biāo)，生成的測試數(shù)據(jù)能夠覆蓋被測程序的全部通信；本文方法能夠達(dá)到較高的通信覆蓋率，并減少了測試數(shù)據(jù)的生成時間。

值得說明的是，當(dāng)前工作基于靜態(tài)分析實現(xiàn)通信的約減。因此，開發(fā)基于本文方法的原型系統(tǒng)，實現(xiàn)基于占優(yōu)關(guān)系的通信覆蓋自動化約減是我們的后續(xù)研究工作。同時，本文沒有考慮調(diào)度序列性能，可以融合調(diào)度序列的性能評價，選擇性能優(yōu)異的目標(biāo)調(diào)度序列集，以便進(jìn)一步提高通信覆蓋的效率。此外，在通信覆蓋方面，本文基于單目標(biāo)覆蓋的方式實現(xiàn)通信覆蓋的測試數(shù)據(jù)進(jìn)化生成，實現(xiàn)面向多目標(biāo)覆蓋的測試數(shù)據(jù)生成也是下一步要研究的課題。