1 引言

隨著信息化社會(huì)的飛速發(fā)展，圖形處理芯片 GPU芯片的功能越來(lái)越豐富，性能要求越來(lái)越高，應(yīng)用領(lǐng)域也越來(lái)越多源化。相應(yīng)地，在 GPU 架構(gòu)設(shè)計(jì)環(huán)節(jié)，功能級(jí)仿真 C-model 的規(guī)模和復(fù)雜度也不斷增大。整個(gè)項(xiàng)目設(shè)計(jì)周期內(nèi)，任何新版本的引入，無(wú)論是源于對(duì)已有錯(cuò)誤的修正，還是為支持新功能而增加模塊，都可能對(duì)原有 C-model 帶來(lái)影響。如果無(wú)限制地任由研發(fā)團(tuán)隊(duì)的每個(gè)人隨意檢出檢入，就會(huì)給項(xiàng)目帶來(lái)風(fēng)險(xiǎn)，因此就需要對(duì)代碼進(jìn)行版本控制和有效管理。

與此同時(shí)，代碼的頻繁修改，理論上都需要更高頻率的測(cè)試來(lái)驗(yàn)證，才能避免新錯(cuò)誤的引入，確保芯片的正常功能。其過(guò)程十分重要，但是需要大量的人力、物力成本。因此，要確保項(xiàng)目高效正向推進(jìn)，有必要在代碼提交前對(duì)其進(jìn)行有效的預(yù)檢，為后續(xù)的回歸測(cè)試和錯(cuò)誤跟蹤節(jié)省成本。

眾所周知，測(cè)試用例決定了測(cè)試的成本及效果，針對(duì)版本控制系統(tǒng)端的測(cè)試用例，時(shí)效性顯得尤為重要。因此，如何在時(shí)間有限的約束條件下，在代碼預(yù)檢端優(yōu)選出能保障代碼質(zhì)量的測(cè)試用例集合，成為本文研究的重點(diǎn)。

2 CIMS 原理框架和集合覆蓋問(wèn)題

2.1 CIMS原理框架

作為我們自行研發(fā)的自動(dòng)化測(cè)試框架的一部分，檢入管理系統(tǒng) CIMS（Check In Management System）相當(dāng)于軟件版本管理系統(tǒng)的前置過(guò)濾器。圖 1 為其工作流程圖。該系統(tǒng)利用 Perforce 提供的trigger 功能，將我們自定義的腳本嵌入。當(dāng)研發(fā)人員修改代碼并檢入時(shí)，p4server 自動(dòng)調(diào)用腳本對(duì)修改的代碼進(jìn)行編譯和測(cè)試。只有通過(guò)所有編譯和測(cè)試項(xiàng)的修改，才可過(guò)關(guān)進(jìn)而被成功提交至 Perforce 存儲(chǔ)庫(kù)，并獲得版本號(hào)。否則，修改將被退回，開(kāi)發(fā)員可以通過(guò) CIMS 系統(tǒng)提供的網(wǎng)頁(yè)界面查詢(xún)編譯和測(cè)試狀態(tài)，便于進(jìn)一步自查和完善代碼。雖然通過(guò) CIMS這套機(jī)制，對(duì)代碼質(zhì)量設(shè)置了一定的門(mén)檻，但是也需要兼顧時(shí)間成本，為了讓 CIMS 發(fā)揮更大的作用，測(cè)試集的優(yōu)選算法值得重點(diǎn)研究。

目前，測(cè)試人員普遍采用回歸測(cè)試來(lái)保證代碼修改的正確性，并避免代碼修改給被測(cè)程序其他模塊帶來(lái)的副作用。CIMS 系統(tǒng)中測(cè)試用例集的優(yōu)選問(wèn)題在以往的項(xiàng)目開(kāi)發(fā)中，往往憑經(jīng)驗(yàn)從已有的回歸測(cè)試集合中，分模塊挑選，以提高整個(gè) pipeline 的功能覆蓋，并無(wú)任何指標(biāo)來(lái)評(píng)判其效用之優(yōu)劣。本文從集合覆蓋角度，對(duì)如何從已有回歸測(cè)試集中篩選子集作為 CIMS 系統(tǒng)內(nèi)的測(cè)試集展開(kāi)研究。

2.2 集合覆蓋問(wèn)題

在集合論中，集合覆蓋定義為：假設(shè) A 是非空集合，如果 A 的若干非空子集的并集等于 A，則由這些子集構(gòu)成的集合 C 稱(chēng)為 A 的覆蓋。即非空集 A的一個(gè)覆蓋 C 是 A 的非空子集的集合。

經(jīng)典的集合覆蓋問(wèn)題 SCP（Set Covering Problem）描述如下：給定兩個(gè)集合 R 和 S，元素的集合 R 和 R 的子集的集合 S，目標(biāo)是找到 S 的一個(gè)子集 C，使得 C 中所有集合的并等于 R，且使 |C| 最小。這是 NP-hard 類(lèi)的最優(yōu)化組合問(wèn)題。

早期回歸測(cè)試工具大都基于黑盒測(cè)試。當(dāng)時(shí)，還沒(méi)有任何回歸測(cè)試工具能在程序修改后自動(dòng)在原始用例集中選擇出一個(gè)用例子集進(jìn)行回歸測(cè)試，而是再測(cè)試全部已有用例進(jìn)行回歸測(cè)試。在這種情況下，F(xiàn)ischer 等人研究了如何在原始用例集中選擇出一個(gè)最小的子集，用于回歸測(cè)試，且不會(huì)降低測(cè)試效果和程序的可靠性，最早提出了測(cè)試用例最小化的思想[1]。對(duì)測(cè)試用例集最小化的定義如下：給定測(cè)試需求集 R{R1，R2，R3.....Rm}，測(cè)試用例集 T{T1，T2，T3....Tn}，該測(cè)試用例集 T 能夠用來(lái)充分測(cè)試 R。問(wèn)題：從 T 中找到一個(gè)最小子集 T'，該子集 T' 能夠用來(lái)充分測(cè)試給定的測(cè)試需求集 R。

1993 年，Harrold 等人[2]首次提出了測(cè)試用例集約簡(jiǎn)的概念，也就是要在原始的測(cè)試用例中尋找一個(gè)子集，實(shí)現(xiàn)測(cè)試需求的充分覆蓋。隨后研究人員圍繞測(cè)試用例集約減問(wèn)題提出了貪心算法[3]、整數(shù)規(guī)劃算法、遺傳算法、HGS 等算法。這些方法各有優(yōu)勢(shì)和局限性，更多趨向于去除冗余的測(cè)試用例，沒(méi)有考慮到要縮減用例的根本原因是資源有限，而且約減的目的并不單是測(cè)試用例的個(gè)數(shù)越少越好，也要考慮約減后測(cè)試用例集的錯(cuò)誤檢測(cè)能力是否保持在一定的水平上。為了充分利用資源，又兼顧資源的約束條件。

本文提出了一種改進(jìn)的測(cè)試集優(yōu)選算法，尋求能使代碼覆蓋率達(dá)到最大的用例集。

3 基于SCP原理的優(yōu)化方案

3.1 集合覆蓋貪心算法

最早提出用貪心算法來(lái)求解測(cè)試用例集合覆蓋問(wèn)題的是 V.Chvatal[4]。集合覆蓋貪心算法是測(cè)試用例集約減問(wèn)題的一個(gè)常用近似算法。貪心策略的思路是從問(wèn)題的初始狀態(tài)出發(fā)，通過(guò)若干次的貪心選擇而得出最優(yōu)解(或較優(yōu)解)。其算法執(zhí)行過(guò)程如下：逐次從 T 中選擇一個(gè)測(cè)試用例，使之能盡可能多地滿(mǎn)足 R 中的測(cè)試需求，然后從 R 中刪除這些已被滿(mǎn)足的測(cè)試需求，循環(huán)幾次上述操作，直到所有測(cè)試需求都能被滿(mǎn)足（即 R 為空集）。

該算法的時(shí)間復(fù)雜度是 O (m,n,min(m，n))。算法如下。

input A：包含 m 個(gè)元素的集合

C(A)：A 的 n 個(gè)子集的集合

output C：從 C(A) 中選擇的元素的集合

declare U：A 中所有未覆蓋元素的集合

X：從 C(A) 中選中的元素

Begin

/初始化/

U=A；

C=Φ；

While(U≠Φ )

/選擇一個(gè)能滿(mǎn)足未覆蓋元素的最大數(shù)目的子集/

select{X} C(A) such that |{X}∩ U| is maximum；

U=U{X}；

C=C ∪ {X}；

End-while

End

貪心算法所做出的選擇雖然只是在某種意義上的局部最優(yōu)解，但許多問(wèn)題自身的特性決定了該問(wèn)題運(yùn)用貪心策略可以得到最優(yōu)解或較優(yōu)解。CIMS 系統(tǒng)中測(cè)試集的集合覆蓋問(wèn)題可以用貪心算法求解。即通過(guò)一系列當(dāng)前狀態(tài)下某種意義的最好選擇(貪心選擇)來(lái)得到一個(gè)問(wèn)題的解。最小化問(wèn)題的貪心選擇性質(zhì)表現(xiàn)為：?jiǎn)栴}的整體最優(yōu)解是通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到的。

3.2 測(cè)試用例約減模型

針對(duì) CIMS 系統(tǒng)中測(cè)試集的集合覆蓋問(wèn)題[4,5]，本文定義了資源約束條件下的測(cè)試用例約減模型為：假設(shè)給定一個(gè)回歸測(cè)試用例集 R={r1，r2.....rn}，其中每個(gè)測(cè)試用例對(duì)應(yīng)的運(yùn)行時(shí)間為 T={t1,t2....tn}，每個(gè)測(cè)試用例對(duì)應(yīng)的函數(shù)覆蓋率為 C={c1,c2....cn}，假定約束時(shí)間為 Tsum，我們要找出一個(gè)測(cè)試用例集的子集 P={ p1，p2.....pm }，其中 m

（3）

3.3 算法實(shí)現(xiàn)

根據(jù)測(cè)試用例約減模型，假設(shè)已有回歸測(cè)試用例集為 R={r1，r2.....rn}，其對(duì)應(yīng)的函數(shù)覆蓋率為 Ctotal，其中，每個(gè)測(cè)試用例 rn 對(duì)應(yīng)了不同的函數(shù)覆蓋率 cn 和不同的測(cè)試時(shí)間 tn，取函數(shù)覆蓋率和測(cè)試時(shí)間的比值 cn/tn 作為該測(cè)試用例 rn 的優(yōu)先級(jí)系數(shù)，需要選出最佳測(cè)試子集 P，使得該集合所對(duì)應(yīng)的函數(shù)覆蓋率盡可能接近 Ctotal、該集合中所有測(cè)試用例運(yùn)行時(shí)間之和不大于約束值 Tsum。算法流程如圖 2 所示，具體實(shí)現(xiàn)步驟如下。

（1）設(shè)定時(shí)間約束條件為 Tsum。

（2）將測(cè)試用例按其函數(shù)覆蓋率 Cn 從大到小排序，將排位第一的測(cè)試用例選入 P。

（3）在余下的測(cè)試用例中，篩選與已選中的測(cè)試用例對(duì)應(yīng)的被覆蓋函數(shù)交集最小的測(cè)試用例，若其值相同，則選取優(yōu)先級(jí)系數(shù)最大的測(cè)試用例。

（4）以此類(lèi)推,依次選取，累加被選中的測(cè)試用例的運(yùn)行時(shí)間，直到運(yùn)行時(shí)間之和 ∑mi=1 ti 超過(guò)約束時(shí)間 Tsum 為止。

4 實(shí)驗(yàn)驗(yàn)證

本文研究的重點(diǎn)是基于函數(shù)覆蓋率的測(cè)試用例篩選，所以覆蓋率信息收集的是函數(shù)覆蓋率相關(guān)信息，包括覆蓋到的函數(shù)塊數(shù)量，總共的函數(shù)塊數(shù)量，以及兩者之間的比值即函數(shù)覆蓋率。另外，計(jì)算出每個(gè)測(cè)試用例覆蓋到的函數(shù)塊數(shù)量與其運(yùn)行時(shí)間的比值，作為優(yōu)先級(jí)系數(shù)。在算法中我們會(huì)優(yōu)先考慮選擇運(yùn)行時(shí)間盡可能短、而覆蓋率盡可能高的測(cè)試用例，從而來(lái)保證時(shí)間約束條件下，覆蓋更多的函數(shù)塊，得到的覆蓋率百分比盡可能地接近完全測(cè)試的覆蓋率百分比。

根據(jù) 3.2 中提出的用例約減模型，本文選取已有回歸測(cè)試用例 13 067 個(gè)進(jìn)行實(shí)驗(yàn)，圖 3 是利用工具 Bullseye 獲取單個(gè)測(cè)試用例的覆蓋率信息。

并且，編寫(xiě)程序自動(dòng)化采集下列相關(guān)信息。

（1）測(cè)試用例名稱(chēng)。

（2）測(cè)試用例的函數(shù)覆蓋率信息。

（3）測(cè)試用例運(yùn)行的時(shí)間。

（4）測(cè)試用例優(yōu)先級(jí)系數(shù)等，部分?jǐn)?shù)據(jù)如表 1 所示。

本文選取的 C-model 代碼擁有 13 216 個(gè)函數(shù)功能塊，實(shí)驗(yàn)時(shí)所取的完全測(cè)試所得到的函數(shù)覆蓋率為 84%。實(shí)驗(yàn)結(jié)果顯示：相同運(yùn)行時(shí)間下，改進(jìn)前 CIMS 測(cè)試集對(duì)應(yīng)的函數(shù)覆蓋率為 49%，而采用本文算法后獲得的測(cè)試集所對(duì)應(yīng)的函數(shù)覆蓋率可達(dá) 76%（參見(jiàn)圖 4）。

實(shí)驗(yàn)證明，采用本文的改進(jìn)算法后，在原有測(cè)試運(yùn)行時(shí)間不變的情況下，算法篩選出的測(cè)試集所對(duì)應(yīng)的函數(shù)覆蓋率提高了 27%。說(shuō)明在時(shí)間有限的約束下，采用本文的算法能合理挑選符合條件的測(cè)試用例集，使得到的測(cè)試用例子集的函數(shù)覆蓋率更接近完全測(cè)試所對(duì)應(yīng)的覆蓋率。

5 結(jié)語(yǔ)

本文針對(duì) CIMS 系統(tǒng)中測(cè)試集的篩選問(wèn)題，結(jié)合集合覆蓋原理展開(kāi)研究，定義了一個(gè)資源約束條件下的測(cè)試用例約減模型，并實(shí)現(xiàn)了一種改進(jìn)的算法，使得 CIMS 測(cè)試集在規(guī)定時(shí)間內(nèi)覆蓋更多函數(shù)塊，提升了代碼質(zhì)量預(yù)檢的性能，對(duì)保證項(xiàng)目質(zhì)量有著積極的實(shí)際意義。

隨著項(xiàng)目的推進(jìn)，測(cè)試集的篩選也需要定期動(dòng)態(tài)調(diào)整。如何進(jìn)一步完善算法，使其能優(yōu)選出可以覆蓋代碼修改部分的測(cè)試用例，更好地滿(mǎn)足測(cè)試需求，是下一步值得研究的方向。