基于逐步細化快照序列的多核并行程序調試

王博弘 劉 軼 張國振 錢德沛

(北京航空航天大學中德軟件技術聯合研究所 北京 100191)

(turtlemax2009@gmail.com)

隨著現代處理器技術的發展，在單個芯片上集成多個處理器核[1]，形成多核處理器，已經成為芯片工業發展的主要趨勢.在這種架構下，能夠對多核處理器資源進行充分利用的多核并行程序也得到了越來越多的應用.然而面對多核架構，并行程序的開發和部署面臨著諸多的困難.在這些困難之中，最為嚴峻的就是多核并行程序的調試問題.為了表示的方便和簡潔，在第1～3節和第5節中，并行程序即指代多核架構下的并行程序，而非多節點架構下如基于MPI實現的廣義并行程序.

在調試并行程序時，存在2個嚴重的問題：

1) 調試的基礎存在問題.并行程序的運行存在著不確定性.不確定性往往會導致程序中的錯誤變得無法追查：在某種特定的系統條件和運行順序下錯誤會出現，但是當軟件開發人員嘗試對錯誤進行調試和分析時錯誤又會消失.

2) 調試的方法存在問題.用戶所熟悉的傳統調試方法無法應用于并行程序的調試.例如在多線程的環境下，用戶所設置的斷點無法實現和串行程序調試一樣的控制效果，并且很難從整體上采用由粗到細的方式發現錯誤.

可重現調試(replay debug)是一種針對并行程序調試，可以消除并行程序運行中不確定性的調試輔助技術，其對確定性的保證還被應用于并行安全性和可靠性檢查[2]、性能預測[3]等多個領域.可重現調試在近年來已經成為了學術界和工業界關注的重點.ISCA，HPCA，MICRO，ASPLOS，SOSP，OSDI，PLDI，PPOPPT等關于體系結構、操作系統、并行計算、分布式計算、編程語言方面的頂級會議每年都會出現大量的關于可重現調試的論文.同時，IBM，Intel，Microsoft，VMware等在工業界具有影響力的公司都在確定性重現方面投入了大量的人力，他們相信可重現調試會給用戶帶來更好的可編程性.

部分現有的可重現調試研究成果，如LReplay[4]，RelaxReplay[5]，Pacifier[6]，已經將可重現調試的代價降低到了較小的程度，但是它們都是硬件輔助的解決方案，需要在處理器體系結構方面進行改動.而純軟件的實現方法往往要依托于高度定制的操作系統和運行時環境，如CoreDet[7]和Kendo[8].并且無論是軟件還是硬件的解決方案，其實現可重現的代價往往會隨著并發度的增加而超線性地增長.綜上，現有的可重現調試方法普遍存在3個缺陷：

1) 無法應用于商用的軟件和硬件平臺；

2) 隨著并行度增加的可擴展性較差；

3) 關注于調試基礎，即確定性的保證，而忽略了對并行調試方法性的支持.

基于上述的缺陷和問題，本文提出了一種新型的基于運行快照的可重現調試方案SDT(snapshot debug tool).SDT的核心思路為把物理的可重現轉為邏輯上的可重現，以犧牲部分調試上的靈活性為代價，得到一種可以在目前商用平臺上進行應用的可重現調試方法.同時，SDT在保證確定性的前提下，還額外兼顧了對調試方法的支持，提供了一種基于運行快照逐漸細化的錯誤發現方法，更為符合用戶的調試習慣，并且可以在調試的過程中與用戶建立緊密的互動，具有很好的實用性.我們在PARSEC和SPLASH-2測試集上的運行結果表明，使用SDT調試所帶來的時間性能損耗平均為51.88%，處于可接受的范圍內.同時當多核并行程序的并發度增長4倍時，使用SDT所帶來的額外時間代價最多增長1倍，具有很好的可擴展性.

1 相關工作

可重現調試技術所應用的具體領域有很多.根據硬件體系結構和軟件體系結構的不同，可以主要分為3類：

1) 單核處理器可重現調試;

2) 多核處理器消息傳遞可重現調試;

3) 多核處理器共享存儲可重現調試.

目前，單核處理器可重現調試和多核處理器消息傳遞可重現調試的實現方法已經比較成熟，并且開始進入工業化實用階段,ReVirt[3]和ReTrace[4]是其中比較具有代表性的成果;但是多處理器共享存儲的可重現調試，目前仍然存在一些技術上的困難,這一技術困難主要集中在存儲器競爭上.

針對多核處理器共享存儲條件下的可重現調試問題，現有的研究方法主要可以分為2類：確定性重現和確定性并行.

確定性重現技術的實質為實現一個重現系統.確定性重現系統包含2個階段：首次執行階段和重現執行階段.1)在首次執行階段，并行程序在執行的過程中，將所有的不確定因素記錄到日志文件中；2)在重現執行階段，系統根據首次執行階段記錄的日志文件重新執行程序，以保證重現執行和首次執行有著相同的過程.目前主流的確定性重現方法普遍都需要對硬件進行更改：RelaxReplay[5]以及Pacifier[6]都以cache一致性消息的擴展為基礎，通過硬件的改動，實現了對共享內存的所有沖突訪問進行快速的識別和記錄.而LReplay[4]的思路則是在處理器片間距離較小的情況下，引入全局時鐘.通過全局時鐘的輔助，絕大多數的指令執行序都可以被推導確定，LReplay只需要記錄少部分無法推導的執行序即可.

與確定性重現記錄的思想不同，確定性并行的根本思路為直接消除并行程序運行中所產生的不確定性，從而保證并行程序在相同的輸入下，總是能產生相同的程序執行流程和相同的結果.確定性并行技術能夠完全復現bug，實現對并行程序調試困境的突破，并且能同時對程序測試、容錯等方面提供有力支持.CoreDet[7]是一個典型的使用串并行轉化思路的確定性并行方法，使用內存持有表(memory ownership table, MOT)來判定并行讀和串行寫的邊界.如果一個線程對非自己所有的內存塊執行了寫操作，或者對非自己所有的非共享或者blank的內存塊執行了讀操作，則需要轉入串行寫狀態.Kendo[8]則只關注存儲器競爭中的同步部分，首先提出了基于軟件方法來實現確定性同步事件的解決方案.Kendo使用確定的邏輯時間(determine logical time, DLT)，計算每個同步操作的確定性交互，同時保證負載平衡.

綜上所述，面對存儲器競爭這一可重現調試實現過程中的關鍵問題，現有的研究從確定性并行和確定性重現2方面出發，給出了很多可行的解決方法.但是現有的方案普遍具有3點缺陷：

1) 泛用性問題.為了解決數據競爭的確定性問題，現有的高效率解決方案都采用了硬件輔助的實現方式，從而無法在商用的硬件平臺上使用.而對于一些采用純軟件技術實現可重現調試方法，則往往需要依賴于定制的操作系統，或者高度定制的編譯和運行時系統，同樣具有泛用性差的問題.

2) 可擴展性差.目前針對可重現調試的技術方案，在方案的測試中，大多數只使用了2～4個線程，只有少數方案測試了8線程條件下的效果，并且在現有的測試結果中，可重現調試的實現代價一般隨著線程數的增加會產生超線性的增長.

3) 忽略了調試方法問題.現有的可重現調試技術，其關注點都在于如何保證程序執行的確定性，使得程序中的錯誤能夠重現.但是在錯誤重現的基礎上，卻并沒有提出指導用戶發現錯誤的具體調試方法，沒有實現真正的實用性.

鑒于相關工作的研究現狀，我們希望提出的新型可重現調試方法應當能夠保證方法的泛用性，保證并行度增加時調試代價的可接受，同時提供給用戶一個實用的調試方法指導.本文所提出的SDT就是一種能夠同時滿足泛用性、調試代價的可擴展性以及能夠提供實用調試方法的可重現調試解決方案.在第2節中，我們將詳細說明SDT的設計初衷和所采用的具體方法.

2 SDT調試方法設計

SDT在設計時同時考慮到了編寫并行程序的用戶在調試多核并行程序時所遇到的調試基礎問題和調試方法問題.為了表示的方便，在第2～5節中所提到的用戶即指代編寫多核并行程序并對多核并行程序進行調試的程序編寫者.

調試基礎方面，需要保證的關鍵點是多核并行程序運行和調試時的確定性.SDT利用了運行快照序列，通過運行快照序列的捕捉和重現，保證了并行程序調試時的確定性.

調試方法方面，用戶所熟悉的調試方式是由粗到細，逐步定位錯誤的發生位置，并最終發現需要修改的程序代碼.SDT采用對運行快照序列進行逐步細化的方式，提供了由粗到細的調試方法支持.

在2.1節和2.2節中，我們將對SDT所使用的兩大核心方法：運行快照序列和快照序列的逐步細化進行詳細的介紹.

2.1 基于快照序列的并行程序調試方法

傳統的可重現調試技術方案，無論采用確定性重現或是確定性并行的方法，所注重的都是并行程序執行過程的重現.而在SDT的設計中，我們認為，用戶在調試過程中真正關注的是在調試過程固定時所能觀察到的固定的運行結果.例如在調試存在寫突的多線程程序時，用戶所關注的并不是線程中所有指令的執行先后順序，而是寫沖突是否會導致某些可以被觀察到并影響程序正確執行的運行結果.

因此，SDT并不記錄程序的執行過程，轉而記錄程序的執行結果.在SDT中，我們所記錄的運行結果為運行快照序列，通過對運行快照的記錄和重現來實現并行程序調試中的可重現.傳統可重現調試方法實現的是基于運行過程的物理重現，而SDT中所實現的則是基于觀察結果的邏輯重現.

如圖1所示，用戶所編寫并需要進行調試的并行程序的每一次運行，都將產生一個運行快照序列.一個運行快照序列由按照捕捉順序排列的多個運行快照組成，每個運行快照中包含了并行程序運行至某個快照捕捉點時并行程序的全部斷面信息，包括捕捉時刻的并行程序所使用的全部內存以及處理器上下文數據.運行快照的捕捉點由用戶在程序運行前根據程序的具體邏輯設置.參照傳統串行程序的調試，為了表述的清晰和簡明，并突出捕捉點在運行前設置的特性，在本節以及第3，4節中我們稱運行快照的捕捉點為離線斷點.

Fig. 1 The concept of SDT logical replay圖1 SDT邏輯重現概念示意圖

考慮2種調試場景：場景1是用戶使用了SDT進行調試，在程序運行結束后順序觀察了運行快照序列中的每一個運行快照.在完成了所有的觀察后得到了觀察結果A.場景2是用戶使用傳統的可重現調試方式完成對并行程序的物理重現，在重現的過程中，對參照場景1中離線斷點的位置，順序觀察每個位置上的程序運行斷面，得到觀察結果B.

可以發現，在SDT中每個運行快照都保存了完整的斷面信息的情況下，從觀察結果A和觀察結果B中用戶所能得到的信息量是相同的.因此，SDT中從觀察角度出發的邏輯重現與傳統可重現調試方法從運行角度出發的物理重現，實現了相同的調試效果.

綜上，SDT所使用的基于運行快照的調試方法已經十分清晰：在程序運行前由用戶在源程序中標記離線斷點；運行過程中到達每個離線斷點時，暫停并行程序的所有線程，保存當前程序的運行斷面為運行快照；運行結束后，用戶順序觀察所有的運行快照，等價于并行程序進行了邏輯重現，可以實現和傳統物理重現相同的調試效果.

但必須指出的是，為了實現程序調試的確定性，SDT提供給用戶使用的斷點設置方式為離線斷點，即斷點必須在程序運行前設置，一旦設置后就不可更改，這實際為調試過程的靈活性帶來了一定的犧牲.為了解決這一問題，SDT還額外添加了離線斷點屬性和快照捕捉配置檢查機制.

通過SetBreakpoint給出了SDT所提供的離線斷點設置接口.Level，Class，Id，Attrs等均為用戶設定的與離線斷點相關的屬性.而Multiple_mark則用來決定該離線斷點是否會被觸發多次.這樣設計的原因為在并行程序中，一段程序代碼往往會被多個線程共用，同時執行，在這種情況下用戶可以通過Multiple_mark的設置來保證只有最先達到的線程會觸發斷點，從而觸發快照保存.

SetBreakpoint(Level,Class,Id,Multiple_mark,Attrs)；

Level：快照保存的層次；

Class：快照保存的類別；

Id：快照保存的獨立編號；

Multiple_mark：該快照是否會被保存多次；

Attrs:為〈key,value〉二元組的集合，用于自定義快照過濾策略.

通過上述的離線斷點屬性和快照捕捉配置檢查機制，雖然用戶仍然必須在程序運行前設置所有的離線斷點，但是可以通過更改快照捕捉配置，使得同一并行程序的多次運行產生不同的運行快照序列，以增強SDT調試方法的靈活性.同時快照捕捉配置檢查也為之后快照序列的逐步細化提供了快照捕捉的技術基礎.

Fig. 2 Process of refined replay execution圖2 細粒度重現過程示意圖

2.2 快照序列的逐步細化

在完成了快照序列的捕捉和分析后，用戶應當可以在一定粒度上確定程序中錯誤的發生位置.如圖2所示，被調試程序P的執行共生成了S0,S1,S2,S3這4個快照，它們實際將P的執行劃分成(begin,S0),(S0,S1),(S1,S2),(S2,S3),(S3,end)共5個區間，其中begin指代P執行的起點，end指代P執行的終點.假設在完成了快照的查看和分析后，用戶確定程序中的錯誤一定發生在區間(S1,S2)中，但是仍無法明確具體的錯誤代碼段，則此時可以應用SDT快照的細粒度重現，完成錯誤的逐步細化過程.

在執行細粒度重現前，首先需要用戶提供起點快照和終點快照，并修改快照捕捉配置.在圖2中，由于用戶已經確定錯誤發生在(S1,S2)區間內，則設定S1為起點快照，S2為終點快照.之后SDT會將起點快照還原為一個可執行的進程，進程的狀態就是被調試進程在觸發起點快照對應的離線斷點時的狀態.由于快照中已經保存了足夠多的信息，包括全部的內存頁和處理器上下文，這一還原過程將不具有技術上的困難.被還原的進程將繼續正常執行，并且由于快照的捕捉配置已經被修改，還原進程在執行的過程中將能夠觸發不同的離線斷點，從而捕捉到與之前不同的運行快照.這些在細粒度重現過程中新增的運行快照被稱為細粒度快照.圖2中的S1.0，S1.1和S1.2為新生成的細粒度快照.

在被還原進程執行到達終點快照后，SDT仍將保存新版本的終點快照(圖2中的S2.new為新版本快照).隨后，SDT會在新版本和原版的終點快照之間執行一致性檢查，一致性檢查的目的為判定此次的細粒度重現執行是否重現了用戶之前通過分析終點快照而發現并粗略定位范圍的錯誤.

由于選定起點快照和終點快照的是編寫程序的用戶，用戶應當在終點快照中發現了某些標志性的變量信息，這些信息代表了錯誤的出現.因此，SDT在進行上述的一致性檢查時采用的是用戶判定一致性策略，即由用戶指定關鍵的變量，若用戶指定的變量在原版終點快照和新版終點快照中的取值完全相同，則此次執行通過一致性檢查，否則此次執行無法通過一致性檢查.

如果細粒度重現所產生的新版本終點快照未通過一致性檢查，則需要使用相同的起點快照和終點快照，再次重復，直到通過一致性檢查為止.在這里我們默認了一個假設，即在重現區間大大縮小(從程序的整體執行縮小到了2個運行快照之間的執行路徑)，一致性判定也相對較弱(只判定用戶指定的關鍵變量，而不需要保證原版和新版本終點快照之間完全一致)的情況下，在多次重試的基礎上終點快照是可以重現原版快照中的錯誤的.在當前SDT的設計中還必須保留這一假設，但是在SDT的改進計劃中，將會在細粒度重現中加入執行路徑搜索機制，以消除這一假設對SDT調試有效性的影響.

在細粒度重現執行成功且通過了一致性檢查后，用戶便可以繼續執行SDT調試過程中的邏輯重現及分析，繼續分析程序中的錯誤，如果仍無法定位則可以繼續在細粒度快照中選擇新的起點快照和終點快照，繼續下一級別的細粒度重現.雖然加入了快照保存的配置檢查機制，但是本質上用戶在SDT中使用的仍是離線斷點，當重現的粒度不斷變細時仍然可能出現斷點無法覆蓋的情況.為了解決這一問題，SDT提供了粗粒度的定時快照保存機制，當現有的離線斷點不足以產生出足夠細粒度的快照時，可以定時觸發出一些新的快照保存點.

3 SDT調試系統實現

SDT系統在實現中可以分解為3個核心的功能部分：快照的捕捉、快照展示和分析、快照的恢復和細粒度重現.

3.1 快照捕捉

快照捕捉部分在整體上可以分為3個子功能模塊：1)提供給用戶并行程序調用的SDT程序庫；2)負責快照捕捉配置注冊和快照收集的SDT輔助服務進程；3)負責快照過濾、捕捉以及傳輸轉移的SDT內核模塊.由SDT添加的系統調用如下：

1)GetSnapShot(intpid,char*buffer)，SDT輔助服務進程向SDT內核模塊注冊下一個運行快照的轉存地址；

2)RigisterSnapshot(intpid,char*optionBuffer)，SDT輔助服務進程向SDT內核模塊注冊快照捕捉配置；

3)TriggerSnapshot(intpid,char*attrBuffer)，SDT程序庫向SDT內核模塊觸發一個離線斷點.

SDT程序庫和SDT輔助服務進程都會通過系統調用與SDT內核模塊進行交互.SDT內核模塊共定義了如表1所示的3個系統調用，用以完成SDT用戶空間模塊和SDT內核空間模塊之間的交互.

Table 1 Software and Hardware Information of Evaluation表1 測試軟硬件環境清單

3.1.1 快照捕捉觸發

在觸發快照捕捉時，必須對正在執行被調試進程線程的處理器核進行控制，使被調試進程的所有子線程都暫停；否則在快照捕捉的過程中仍會有線程處于執行狀態，捕捉到的運行快照將不具有調試和分析的意義.

在控制所有其他線程暫停時，快照捕捉偏差仍是一個需要盡量規避的現象.快照捕捉偏差的概念如圖3所示.為了表示的方便，我們稱當前正在觸發快照保存的進程為P，在P的某一個子線程觸發了快照的捕捉后，正在執行該線程的處理器核稱為觸發核，正在執行P的其他子線程的處理器核稱為響應核.以觸發核接收到快照捕捉信號的時間點為理想快照捕捉點，最后一個響應核暫停P的子線程執行的時間點為實際快照捕捉點，則兩者之間的時間差為快照的捕捉偏差.為了保證快照的有效性，需要盡量縮短快照捕捉偏差.

Fig. 3 Illustration of snapshot capture deviation圖3 快照捕捉偏差說明圖

在SDT的實現中，我們摒棄了通過操作系統控制線程暫停的實現方法，而是直接使用了更為底層的IPIs(inter process interrupts)，即跨處理器中斷.IPIs是現代多核處理器架構普遍支持的一種中斷功能，在Intel的所有商業化多核產品中都有很好的支持.在實現中，觸發核接收到快照觸發的信號時會立刻向其他所有的處理器核發送IPIs，觸發其他所有的處理器核進入SDT系統定義的中斷向量.對于其他所有的處理器核，進入中斷后首先會判斷當前執行的線程是否為P的子線程，如果不是，則繼續執行原有程序，否則當前處理器核為響應核.對于響應核，需要立刻暫停當前執行的線程，循環等待觸發核發出快照捕捉結束的信號.

3.1.2 快照捕捉執行

在完成了對所有處理器核的識別和控制后，SDT的捕捉過程將進入執行狀態.如圖4所示，core0為當前的觸發核，core1和core2為當前的響應核.

Fig. 4 Illustration of snapshot capture process圖4 快照捕捉執行說明圖

在進入捕捉執行狀態后，觸發核首先執行快照捕捉配置檢查.當前離線斷點的屬性會由用戶程序所包含的SDT程序庫通過TriggerSnapshot系統調用，在快照捕捉觸發時傳遞給響應核.而當前使用的快照捕捉配置則會在用戶程序開始運行前，由SDT輔助服務進程通過RegisterSnapshot傳遞給SDT內核模塊.快照配置檢查的具體過程可參見4.1節.

如果當前離線斷點通過了快照配置檢查，則會同時進入快照捕捉的執行和快照數據傳輸階段.響應核會讀取當前捕捉的進程P所持有的所有信息，包括所有的處理器上下文以及持有的內存頁.同時，在SDT內核模塊和SDT輔助服務進程之間，會通過消息隊列和GetSnapshot相結合的方式，讓觸發核可以直接將快照數據轉存到用戶空間，以減少額外的內存讀寫操作.

在觸發核完成了全部的快照捕捉以及快照數據傳輸的工作后，會與其他所有的響應核再進行一次同步，隨后同時恢復進程P的各個子進程的執行.所有的響應核在快照捕捉的過程中都會處于同步等待的狀態，這樣的處理雖然在一定程度上會影響系統的整體性能，但是能夠有效地避免快照的捕捉對用戶并行程序執行產生的影響.

3.1.3 快照增量處理與保存

SDT所保存的運行快照中，包含了用戶并行程序所使用的全部內存頁.而在2個被觸發的離線斷點之間，用戶并行程序所能修改的內存一般而言是十分有限的.基于這一考慮，SDT在實現中添加了快照的增量保存模式，以減少最終向硬盤寫入快照的數據量.

SDT中快照的增量處理由SDT輔助服務進程完成，在接收到一個新的運行快照時，會生成針對此快照的增量片段，如算法1所示，以當前時刻快照內存頁數據PageListold和新接受的快照Snapnew為輸入，新生成的增量片段newPatch為輸出，完成增量快照的計算和維護.上述的快照增量計算均在SDT輔助服務進程中進行.

算法1. 創建增量塊.

輸入:快照PageListold，Snapnew；

輸出:增量塊newPatch.

①PageListnew←SplitMemoryPage(Snapnew)；

②Sort(PageListnew,PageListnew.size,AddrComp)；

③oldPage←PageListold.begin()；

④ for eachnewPageinPageListnew

⑤ whileoldPage.addr

⑥oldPage←oldPage.next()；

⑦ end while

⑧ ifoldPage.addr==newPage.addr

⑨pagePatch←getPagePatch(newPage,oldPage)；

⑩newPatch.insertModifiedPage(pagePatch)；

目前SDT所使用的只是一個較為粗糙的增量快照維護方式.在后續的計劃中，SDT中的快照增量存儲將更改為頁面監視模式.我們會在操作系統內核空間中額外添加頁面變更監聽模塊，使用陷阱來監控所有針對目標進程內存頁的寫入操作，從而在觸發核進行快照捕捉時，可以只捕捉較少數量的內存頁.目前基于頁面監視模式的快照保存方式已經具有了較為成熟的技術方案[9-10].

3.2 快照展示及分析

在快照展示及分析模塊中，我們需要把SDT已經捕捉到的快照數據展示給用戶.考慮到用戶的使用習慣問題，我們在實現上選擇將SDT與GDB相結合.

SDT采用了將運行快照轉化為EIF Core數據格式的方式.ELF是一種可以靈活表示二進制程序數據的數據格式[11].在Linux系統中，當程序運行崩潰時，可以生成EIF Core文件，而GDB支持對EIF Core的調試功能，SDT也就利用了這一點，使得SDT中的運行快照可以被主流調試工具解析，在符合用戶使用習慣的條件下進行分析和查看.

在靈活調試能力的實現上，由于SDT對于運行快照的查看已經與GDB整合，對程序中變量和當前執行路徑的修改均可以通過GDB中的已有命令完成.SDT將采用在GDB外層進行包裝的方式，截取所有用戶對運行快照進行的修改，并將修改應用于運行快照上.修改后的運行快照可以通過快照的恢復和細粒度重現模塊恢復為可運行的進程.

3.3 快照的恢復及細粒度重現

快照的恢復和細粒度重現模塊提供了SDT調試方法中細粒度定位錯誤的能力.在該模塊中需要實現2個核心功能：

1) 將SDT中的運行快照轉化為可運行的進程.這一功能場景與容錯領域的檢查點和恢復(checkpoint & replay)十分類似[12]，因此在實現上，我們也采用了和現有checkpoint & replay工具相結合的方式.CRIU(checkpointrestart in userspace)是一個支持檢查點恢復功能的開源軟件[13]，SDT在實現上選擇了與CRIU的整合.SDT在實現時，將運行快照轉化為CRIU需求的數據格式，并由CRIU完成從快照恢復至可運行進程的功能.

2) 細粒度重現的一致性檢查.我們使用用戶判定一致性的檢查策略，由用戶指定在運行快照中可以表示錯誤出現的關鍵變量.只要關鍵變量一致就可以認為此次細粒度重現通過了一致性檢查.

在后續的改進計劃中，我們將添加細粒度執行的執行路徑控制功能.這一方法目前已經在可重現調試中得到了成功的應用[14].

4 實 驗

在本節中，我們將在一些典型的科學計算程序集中應用SDT，對SDT的實際性能進行測試.測試的詳細軟硬件環境如表2所示.我們在該系統中安裝部署了SDT的所有組件.

4.1 實驗準備

我們選擇了PARSEC[15]和SPLASH-2[14]測試集中的7個并行計算應用：4個PARSEC測試程序包括blackscholes，fluidanimate，bodytrack和swaption；3個SPLASH-2中的測試程序包括FFT，LU，FMM.

選用上述7個測試程序的原因為：這些測試程序基本覆蓋了PARSEC和SPLASH-2中的所有不同的計算特性.例如fluidanimate中包含大量的同步操作，且整體內存占用量較大，可以達到400 MB;而blackscholes則是典型的計算密集型應用，對內存的占用量最小，僅有4 MB.實驗中用到的軟硬件環境詳細信息如表1所示.

Table 2 Original Data of SDT Efficiency Test表2 SDT效率測試原始數據

Notes: ET:Execution Time;ETS:Execution Time with SDT;TS:Total Snapshot Size;TIS:Total Incremental Snapsot Size.

在應用SDT進行測試時，由于SDT調試過程的第1步是由用戶設定離線斷點，所以此時必須對所有的benchmark應用程序進行一定的改造.

考慮到用戶在分析調試數據時所能投入的精力有限，我們選擇為每個Benchmark程序添加了10個可以通過快照捕捉配置檢查的離線斷點和10個不會通過快照捕捉檢查的無效離線斷點.在斷點的設置時，我們所秉承的準則是盡量使各有效斷點均勻分布在Benchmark程序的整體執行過程中.我們將以blackscholes程序為例，說明我們普遍采用的斷點設置策略.blackscholes的具體修改如圖5所示:

Fig. 5 Modification of blackscholes’s source code圖5 blackscholes源程序修改說明

在4.2節和4.3節中，我們將主要從時間和空間效率兩方面對SDT進行測試.時間效率為使用SDT前后Benchmark程序運行時間的差異，空間效率為SDT所產生的運行快照所占用的總存儲空間.各個應用程序在使用SDT時所消耗的時間和空間資源的原始數據如表2所示.其中ET表示不使用SDT時程序執行所花費的時間，ETS則表示在使用SDT情況下程序執行所花費的時間，TS表示采用完全保存快照的方法需要保存的數據量，TIS表示采用增量式的快照保存方法需要保存的數據量.

4.2 時間效率測試

在時間效率的測試中，我們使用未添加SDT調試功能的Benchmark的多次執行時間的平均值作為基準，測試出了添加SDT并捕捉了10個運行快照后所造成的性能損失.

圖6中顯示，在添加SDT并保存了10個運行快照后，相比于基準時間，多個測試程序在2線程、4線程、8線程下的平均性能損失為19.80%，33.62%，51.88%；最壞情況下的性能損失為76.21%；總體性能損失增長率低于并發度增長率.

Fig. 6 Comparison of total execution time圖6 總執行時間對比示意圖

設測試程序在未添加SDT調試庫時的平均運行時間為T0，添加后的平均運行時間為T1，則可以認為SDT觸發離線斷點并捕捉快照所占用的總時間為T1-T0.在下面的分析中，我們使用此種方法，得到了SDT在2線程、4線程、8線程下捕捉快照所占用的總時間.圖7中給出了各個Benchmark程序以2線程時的快照為基準，在4線程、8線程條件下的快照捕捉時間增長率.如果SDT的快照捕捉代價線性增長，則增長率的數據應符合最右邊的LINER數據項.

Fig. 7 Comparison of snapshot capture time圖7 快照捕捉時間對比示意圖

實際的數據結果顯示，各個Benchmark程序的平均快照捕捉時間增長率在4線程、8線程的情況下分別為12.57%和41.85%，遠遠低于線性增長情況下的300%.即使在最差的情況下，8線程下的增長率也小于100%，這表示SDT調試方法所帶來的性能損失遠小于隨線程數增長，具有較好的可擴展性.SDT具有上述擴展性的根本原因為SDT所捕捉的快照數據量隨線程數的增長是低于線性的.在一般情況下，多線程程序在并發度增加時，所需額外占據的內存空間僅為新增線程的運行棧，只占進程全部內存占用中的一小部分.需要額外說明的是，圖7中的LINER并不是真實Benchmark程序的測試結果，而是給出了一個在捕捉時間代價完全隨著線程數線性增長時的假想對比示例.通過與LINER圖例的對比可以看出，我們選擇的7個測試程序的平均捕捉時間增長率是遠低于線性的.

4.3 空間效率測試

在測試空間效率時，我們的重點在于測試SDT所使用的增量快照保存機制的效果.

圖8給出了各個應用在各個線程條件下，采用增量保存方式和采用全量保存方式的對比.結果顯示，在平均情況下，2線程、4線程、8線程情況下，增量存儲相比于全量存儲只會占據15.50%,14.47%,14.12%的空間.同時應當注意到，除去bodytrack和swaption外的大多數的Benchmark程序，其增量存儲都會占用小于12%的空間.

Fig. 8 Comparison of snapshot incremental effect圖8 增量快照保存對比圖

增量存儲中的數據可以分為2部分:1)所有增量開始作用的初始快照;2)多個增量片段.如果認為10個快照所占有的內存數據量是近似相同的，則除去初始快照外，所有的增量片段數據量之和小于總數據量的2%，即小于一個運行快照平均大小的20%.這一數據表明增量快照存儲在大多數的計算密集型科學計算應用中將起到非常好的效果.

我們還對各個快照之間內存頁面的差異情況進行了進一步的分析，統計出了運行快照所持有的內存頁面之間的增加和修改的關系.

設多個運行快照中，每個快照與上一個連續的運行快照相比，發生變更或增加的內存頁的數目的綜述為ChangeSum；而10個運行快照中包含的內存頁面總數為Allsum.則圖9中計算的即是ChangeSum在Allsum中所占的比例.結果顯示，2線程、4線程、8線程情況下的平均內存頁面添加修改比例分別為49.95%,66.79%,66.45%.這一結果表示，如果按照計劃實現了基于內存頁面監控的增量快照保存機制，SDT的快照保存效率在理論上還有30%以上的提升空間.

Fig. 9 Comparison of memory page change rate圖9 內存頁面變化示意圖

5 結論及展望

在多核處理器得到越來越廣泛應用的今天，學術界和工業界公認并行程序的調試存在困難，可重現調試技術可以解決調試過程中的不確定性問題，但是普遍具有泛用性差和可擴展性差的特點，且缺乏對用戶在調試方法上的指導，無法被廣大的并行程序編寫者所使用.

本文基于上述的問題，提出了一種基于運行快照序列的并行程序重現調試方法SDT.SDT犧牲了部分調試上的靈活性，但是保證了并行程序調試的確定性，并具有很好的可用性和可擴展性.SDT同時給出了一套完整的由粗到細發現并行程序中問題的調試方法指導，可以有效地指導用戶進行調試，具有很強的實用性.

測試結果顯示，SDT在8線程的情況下平均對并行程序執行時間的影響為51.88%，同時快照保存的時間消耗隨線程數增加的增長率遠遠小于線性的增長率，具有很好的可擴展性.

我們未來計劃在SDT中添加基于內存頁面監控的增量快照生成，以及細粒度重現時的執行路徑搜索控制.以上2種較為成熟的技術預計能有效地提升SDT的快照捕捉效率并減少細粒度重現時的重試次數.