王博弘 劉 軼 張國振 錢德沛

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

(turtlemax2009@gmail.com)

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

在調(diào)試并行程序時(shí)，存在2個(gè)嚴(yán)重的問題：

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

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

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

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

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

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

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

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

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) 多核處理器共享存儲(chǔ)可重現(xiàn)調(diào)試.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Level：快照保存的層次；

Class：快照保存的類別；

Id：快照保存的獨(dú)立編號(hào)；

Multiple_mark：該快照是否會(huì)被保存多次；

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

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

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

2.2 快照序列的逐步細(xì)化

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

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

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

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

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

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

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

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

3.1 快照捕捉

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

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

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

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

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

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

3.1.1 快照捕捉觸發(fā)

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

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

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

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

3.1.2 快照捕捉執(zhí)行

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

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

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

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

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

3.1.3 快照增量處理與保存

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

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

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

3.2 快照展示及分析

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

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

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

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

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

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

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

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

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

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

4.1 實(shí)驗(yàn)準(zhǔn)備

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

選用上述7個(gè)測試程序的原因?yàn)椋哼@些測試程序基本覆蓋了PARSEC和SPLASH-2中的所有不同的計(jì)算特性.例如fluidanimate中包含大量的同步操作，且整體內(nèi)存占用量較大，可以達(dá)到400 MB;而blackscholes則是典型的計(jì)算密集型應(yīng)用，對內(nèi)存的占用量最小，僅有4 MB.實(shí)驗(yàn)中用到的軟硬件環(huán)境詳細(xì)信息如表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進(jìn)行測試時(shí)，由于SDT調(diào)試過程的第1步是由用戶設(shè)定離線斷點(diǎn)，所以此時(shí)必須對所有的benchmark應(yīng)用程序進(jìn)行一定的改造.

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

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

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

4.2 時(shí)間效率測試

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

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

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

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

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

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

4.3 空間效率測試

在測試空間效率時(shí)，我們的重點(diǎn)在于測試SDT所使用的增量快照保存機(jī)制的效果.

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

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

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

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

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

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

5 結(jié)論及展望

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

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

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

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