基于占優關系的并行程序通信覆蓋約減方法

張 辰，田 甜*，楊秀婷，鞏敦衛

（1.山東建筑大學計算機科學與技術學院，濟南 250101；2.中國礦業大學信息與控制工程學院，江蘇徐州 221116）

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

0 引言

消息傳遞程序具有開發簡單、實現便捷、求解高效的特性，是一種應用廣泛的并行程序?；诜植际酱鎯軜嫞鬟f并行程序基于通信語句實現進程之間的交互。通信是消息傳遞并行程序的主要特征體現，而通信測試的核心是高效生成覆蓋通信的測試數據。因此，研究通信覆蓋的測試數據生成問題對于消息傳遞并行程序的測試具有重要意義。

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

本文的主要工作如下:1）給出通信約減問題的轉換理論，將通信約減問題轉換為通信語句約減問題；2）基于占優關系約減通信語句集，進而選擇目標通信；3）將本文所提出的方法應用到基準程序，并與其他方法進行對比，實驗結果驗證了本文方法的可行性和高效性。

1 相關工作

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

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

作為一種重要的軟件測試方法，結構覆蓋測試要求生成覆蓋程序中某種元素的測試數據，如路徑覆蓋、語句覆蓋以及分支覆蓋等。將結構覆蓋問題轉換為優化問題，并采用進化優化方法求解上述問題，進而生成期望的測試數據，成為目前軟件測試領域的重要研究方向之一。

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

2 問題背景

2.1 基本概念

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

定義1通信語句。具有數據發送或接收功能的語句為通信語句，記為n。其中，發送數據的通信語句為發送語句；接收數據的通信語句為接收語句。

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

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

定義4占優。對于i進程中的兩個通信語句ni?j和ni?k，若ni?j和ni?k構成順序結構，且ni?j位于ni?k之前執行，則稱ni?j占優ni?k，記為ni?j→ni?k。此時，若ni?j被執行，則ni?k也必然被執行。

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

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

2.2 通信圖

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

定義7通信圖（G）。以程序中的通信語句為頂點，以同一進程中通信語句間的執行關系為有向虛邊，以不同進程中通信語句間的通信為有向實邊構成的控制流圖，稱之為通信圖。在通信圖中，每個進程有各自的入口及出口。

針對位于順序結構的通信語句，按照通信語句的執行順序構建其對應的頂點，如圖2 所示。圖2～4 中，（a）圖是位于3種控制結構的通信語句，（b）圖的每個頂點分別對應（a）圖中的一條通信語句。

圖2 順序結構Fig.2 Sequence structure

對位于每個分支中的首個通信語句，將其作為分支結構前一個通信語句的分支頂點，分支中的其他通信語句按結構依次構建相應的頂點，如圖3所示。

圖3 分支結構Fig.3 Branch structure

對于循環結構的通信語句，為了能夠清楚并且完整地體現結構特點，借助于輔助頂點，使得循環中通信語句對應的頂點介于兩輔助頂點之間，輔助頂點不具備通信功能，如圖4所示。

圖4 循環結構Fig.4 Loop structure

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

通信圖的構建方法如下:首先，提取各進程中通信語句對應的頂點，并且根據通信語句之間的執行關系構建有向虛邊；然后，根據通信語句的參數信息，構建頂點之間的有向實邊。由此得到程序對應的通信圖。

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

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

示例程序的通信如圖5（b）所示。其中，頂點對應圖5（a）中的進程入口s、出口e及通信語句，如S1的頂點1 對應n1-1。有向虛邊表示通信語句間的執行，以〈n1-1，n1-2〉為例，它表示n1-2在n1-1之后執行。有向實邊則對應頂點間的通信，如〈n0-1，n1-1〉表示S0中n0-1發送的數據由S1的n1-1接收。

3 基于占優關系的通信覆蓋約減方法

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

3.1 通信約減問題的轉換

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

1）確定通信約減問題的轉換。

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

2）不確定通信約減問題的轉換。

在不確定通信組中，一個發送語句可以與多個接收語句通信，同樣地，一個不確定接收語句可以與多個發送語句通信。因此，當不確定通信〈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通信，當n1-2和n0-2被覆蓋時，不能判定〈n1-2，n0-2〉被覆蓋。影響不確定通信〈ni-j，nk-l〉覆蓋的因素為程序輸入及調度序列。調度序列指進程的執行順序。當進程調度遵循影響〈ni-j，nk-l〉覆蓋的調度序列時，若通信語句ni-j和nk-l被覆蓋，則不確定通信〈ni-j，nk-l〉被覆蓋。例如示例程序中，當調度序列為S1S2S3時，若n0-2與n1-2被覆蓋，則不確定通信〈n1-2，n0-2〉被覆蓋。由此，將不確定通信的約減問題轉換為通信語句的約減問題。

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

算法1 目標調度序列集生成。

輸入 被測程序S；

輸出S的目標調度序列集Δ。

3.2 目標通信的選擇

將通信的覆蓋問題轉換為通信語句的覆蓋問題后，本節給出通信語句集的約減方法，基于約減后的通信語句，得到目標通信集?；谕ㄐ耪Z句的占優關系，構造占優關系圖。由占優定義可知，當占優頂點被執行時，被占優頂點也將被執行。因此，占優關系圖的占優頂點組成了通信語句集的約減集，以占優頂點為發送或接收語句的通信即為目標通信。當目標通信被覆蓋時，以被占優頂點為發送或接收語句的通信也將被覆蓋?；谡純炾P系的通信約減算法如算法2所示。

算法2 基于占優關系的通信約減。

輸入 被測程序S；

輸出 目標通信集Φ={Φ0，Φ1，???，Φnum-1}。

3.3 實例分析

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

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

示例程序的5 個進程S0、S1、S2、S3和S4，對應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，根據占優關系得到示例程序的目標通信集。借助于圖5（b）通信圖，首先，分析S0。以s為占優頂點構造D0。關于n0-1，由通信圖可知，n0-1與s構成順序結構，所以將n0-1作為D0的被占優頂點。同樣地，n0-2，n0-3和n0-4為D0的被占優頂點。對于n0-5，由于不被s占優，所以構造占優頂點為n0-5的D1，并將n0-5添加到N0，將與n0-5相關的通信并入S0目標通信集Φ0。類似地，構造以n0-6為占優頂點的D2。關于n0-7，則作為D0的被占優頂點。至此，S0包含的占優關系圖（圖6）構造結束。R0=｛n0-5，n0-6｝，Φ0=｛〈n0-5，n4-1〉，〈n0-6，n4-1〉｝。

圖6 S0的占優關系圖Fig.6 Dominant relation diagram of S0

類似地，可以得到S1、S2和S4的占優關系圖，如圖7 所示。對應地，約減集R1=?，R2=?，R4=?。目標通信集Φ1=?，Φ2=?，Φ4=?。S3的占優關系圖如圖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｝?；赗中的通信語句得到目標通信集Φ=｛〈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的占優關系圖Fig.7 Dominant relation diagram of S1，S2 and S4

圖8 S3的占優關系圖Fig.8 Dominant relation diagram of S3

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

4 實驗與結果分析

4.1 驗證問題

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

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

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

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

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

4.2 實驗設計

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

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

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

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

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

4.3 實驗過程

實驗環境配置如下:硬件為Intel Core i5 處理器、500 GB硬盤和8 GB 內存；軟件采用Windows 10 操作系統、Visual Studio 2017 編譯器，以及消息傳遞接口標準工具Microsoft MPI v9.0.1。

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

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

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

4.4 結果分析

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

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

本文方法的目標通信集、全部通信集以及對比方法全部通信集的平均覆蓋率如表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 可知，當被測程序目標通信覆蓋率為100%時，全部通信覆蓋率同為100%。這表明以本文所提方法得到的通信作為覆蓋目標，生成的測試數據能夠覆蓋全部通信，驗證了本文方法的可行性。此外，對于Triangle程序，由于在第3 次實驗中，有一條目標通信沒有被覆蓋，導致當次實驗的目標通信及全部通信覆蓋率分別為75%和96.2%，其余9 次實驗的目標通信及全部通信覆蓋率均為100%，因此，平均目標通信覆蓋率和全部通信覆蓋率分別為97.5%和99.6%。

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

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

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

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

5 結語

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

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