基于逐步細化快照序列的多核并行程序調(diào)試

王博弘 劉 軼 張國振 錢德沛

(北京航空航天大學(xué)中德軟件技術(shù)聯(lián)合研究所 北京 100191)

(turtlemax2009@gmail.com)

隨著現(xiàn)代處理器技術(shù)的發(fā)展，在單個芯片上集成多個處理器核[1]，形成多核處理器，已經(jīng)成為芯片工業(yè)發(fā)展的主要趨勢.在這種架構(gòu)下，能夠?qū)Χ嗪颂幚砥髻Y源進行充分利用的多核并行程序也得到了越來越多的應(yīng)用.然而面對多核架構(gòu)，并行程序的開發(fā)和部署面臨著諸多的困難.在這些困難之中，最為嚴峻的就是多核并行程序的調(diào)試問題.為了表示的方便和簡潔，在第1～3節(jié)和第5節(jié)中，并行程序即指代多核架構(gòu)下的并行程序，而非多節(jié)點架構(gòu)下如基于MPI實現(xiàn)的廣義并行程序.

在調(diào)試并行程序時，存在2個嚴重的問題：

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

2) 調(diào)試的方法存在問題.用戶所熟悉的傳統(tǒng)調(diào)試方法無法應(yīng)用于并行程序的調(diào)試.例如在多線程的環(huán)境下，用戶所設(shè)置的斷點無法實現(xiàn)和串行程序調(diào)試一樣的控制效果，并且很難從整體上采用由粗到細的方式發(fā)現(xiàn)錯誤.

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

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

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

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

3) 關(guān)注于調(diào)試基礎(chǔ)，即確定性的保證，而忽略了對并行調(diào)試方法性的支持.

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

1 相關(guān)工作

可重現(xiàn)調(diào)試技術(shù)所應(yīng)用的具體領(lǐng)域有很多.根據(jù)硬件體系結(jié)構(gòu)和軟件體系結(jié)構(gòu)的不同，可以主要分為3類：

1) 單核處理器可重現(xiàn)調(diào)試;

2) 多核處理器消息傳遞可重現(xiàn)調(diào)試;

3) 多核處理器共享存儲可重現(xiàn)調(diào)試.

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

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

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

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

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

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

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

3) 忽略了調(diào)試方法問題.現(xiàn)有的可重現(xiàn)調(diào)試技術(shù)，其關(guān)注點都在于如何保證程序執(zhí)行的確定性，使得程序中的錯誤能夠重現(xiàn).但是在錯誤重現(xiàn)的基礎(chǔ)上，卻并沒有提出指導(dǎo)用戶發(fā)現(xiàn)錯誤的具體調(diào)試方法，沒有實現(xiàn)真正的實用性.

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

2 SDT調(diào)試方法設(shè)計

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

調(diào)試基礎(chǔ)方面，需要保證的關(guān)鍵點是多核并行程序運行和調(diào)試時的確定性.SDT利用了運行快照序列，通過運行快照序列的捕捉和重現(xiàn)，保證了并行程序調(diào)試時的確定性.

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

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

2.1 基于快照序列的并行程序調(diào)試方法

傳統(tǒng)的可重現(xiàn)調(diào)試技術(shù)方案，無論采用確定性重現(xiàn)或是確定性并行的方法，所注重的都是并行程序執(zhí)行過程的重現(xiàn).而在SDT的設(shè)計中，我們認為，用戶在調(diào)試過程中真正關(guān)注的是在調(diào)試過程固定時所能觀察到的固定的運行結(jié)果.例如在調(diào)試存在寫突的多線程程序時，用戶所關(guān)注的并不是線程中所有指令的執(zhí)行先后順序，而是寫沖突是否會導(dǎo)致某些可以被觀察到并影響程序正確執(zhí)行的運行結(jié)果.

因此，SDT并不記錄程序的執(zhí)行過程，轉(zhuǎn)而記錄程序的執(zhí)行結(jié)果.在SDT中，我們所記錄的運行結(jié)果為運行快照序列，通過對運行快照的記錄和重現(xiàn)來實現(xiàn)并行程序調(diào)試中的可重現(xiàn).傳統(tǒng)可重現(xiàn)調(diào)試方法實現(xiàn)的是基于運行過程的物理重現(xiàn)，而SDT中所實現(xiàn)的則是基于觀察結(jié)果的邏輯重現(xiàn).

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

Fig. 1 The concept of SDT logical replay圖1 SDT邏輯重現(xiàn)概念示意圖

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

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

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

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

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

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

Level：快照保存的層次；

Class：快照保存的類別；

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

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

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

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

Fig. 2 Process of refined replay execution圖2 細粒度重現(xiàn)過程示意圖

2.2 快照序列的逐步細化

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

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

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

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

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

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

3 SDT調(diào)試系統(tǒng)實現(xiàn)

SDT系統(tǒng)在實現(xiàn)中可以分解為3個核心的功能部分：快照的捕捉、快照展示和分析、快照的恢復(fù)和細粒度重現(xiàn).

3.1 快照捕捉

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

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

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

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

SDT程序庫和SDT輔助服務(wù)進程都會通過系統(tǒng)調(diào)用與SDT內(nèi)核模塊進行交互.SDT內(nèi)核模塊共定義了如表1所示的3個系統(tǒng)調(diào)用，用以完成SDT用戶空間模塊和SDT內(nèi)核空間模塊之間的交互.

Table 1 Software and Hardware Information of Evaluation表1 測試軟硬件環(huán)境清單

3.1.1 快照捕捉觸發(fā)

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

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

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

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

3.1.2 快照捕捉執(zhí)行

在完成了對所有處理器核的識別和控制后，SDT的捕捉過程將進入執(zhí)行狀態(tài).如圖4所示，core0為當前的觸發(fā)核，core1和core2為當前的響應(yīng)核.

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

在進入捕捉執(zhí)行狀態(tài)后，觸發(fā)核首先執(zhí)行快照捕捉配置檢查.當前離線斷點的屬性會由用戶程序所包含的SDT程序庫通過TriggerSnapshot系統(tǒng)調(diào)用，在快照捕捉觸發(fā)時傳遞給響應(yīng)核.而當前使用的快照捕捉配置則會在用戶程序開始運行前，由SDT輔助服務(wù)進程通過RegisterSnapshot傳遞給SDT內(nèi)核模塊.快照配置檢查的具體過程可參見4.1節(jié).

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

在觸發(fā)核完成了全部的快照捕捉以及快照數(shù)據(jù)傳輸?shù)墓ぷ骱?，會與其他所有的響應(yīng)核再進行一次同步，隨后同時恢復(fù)進程P的各個子進程的執(zhí)行.所有的響應(yīng)核在快照捕捉的過程中都會處于同步等待的狀態(tài)，這樣的處理雖然在一定程度上會影響系統(tǒng)的整體性能，但是能夠有效地避免快照的捕捉對用戶并行程序執(zhí)行產(chǎn)生的影響.

3.1.3 快照增量處理與保存

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

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

算法1. 創(chuàng)建增量塊.

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

3.2 快照展示及分析

在快照展示及分析模塊中，我們需要把SDT已經(jīng)捕捉到的快照數(shù)據(jù)展示給用戶.考慮到用戶的使用習(xí)慣問題，我們在實現(xiàn)上選擇將SDT與GDB相結(jié)合.

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

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

3.3 快照的恢復(fù)及細粒度重現(xiàn)

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

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

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

在后續(xù)的改進計劃中，我們將添加細粒度執(zhí)行的執(zhí)行路徑控制功能.這一方法目前已經(jīng)在可重現(xiàn)調(diào)試中得到了成功的應(yīng)用[14].

4 實 驗

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

4.1 實驗準備

我們選擇了PARSEC[15]和SPLASH-2[14]測試集中的7個并行計算應(yīng)用：4個PARSEC測試程序包括blackscholes，fluidanimate，bodytrack和swaption；3個SPLASH-2中的測試程序包括FFT，LU，F(xiàn)MM.

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

Table 2 Original Data of SDT Efficiency Test表2 SDT效率測試原始數(shù)據(jù)

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

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

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

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

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

4.2 時間效率測試

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

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

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

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

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

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

4.3 空間效率測試

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

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

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

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

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

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

Fig. 9 Comparison of memory page change rate圖9 內(nèi)存頁面變化示意圖

5 結(jié)論及展望

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

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

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

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