進(jìn)程基于確定性的并行程序調(diào)試及容錯(cuò)

1、基于確定性的并行程序調(diào)試及容錯(cuò)周軍蕊 BA11011005指導(dǎo)老師 安虹教授ACSAUSTC1研究背景研究動(dòng)機(jī)研究現(xiàn)狀研究內(nèi)容技術(shù)路線實(shí)驗(yàn)方案可行性分析創(chuàng)新性大綱ACSAUSTC2多核、眾核硬件發(fā)展功耗限制晶體管工藝，摩爾定律繞過功耗限制，多核、眾核硬件平臺(tái)受益于不斷發(fā)展的晶體管工藝帶來的處理器能力的提升。并行編程語言命令式語言非命令式語言, 如Cilk、StreamIt內(nèi)存模型共享內(nèi)存，如Pthreads事務(wù)內(nèi)存，如投機(jī)并行研究背景 ACSAUSTC3并行編程墻易出錯(cuò)數(shù)據(jù)沖突死鎖原子違反順序違反難調(diào)試（不確定性）線程交互調(diào)度敏感輸入敏感研究動(dòng)機(jī)ACSAUSTC4原子違反錯(cuò)誤示例研究動(dòng)機(jī)ACS

2、AUSTC5 class Queue Queue( ) 46: items = ;47: qsize = 0; synchronized dequeue( ) 115: if (qsize =0) return null;117: qsize - -;118: return items . . .; synchronized size()133: return qsize; (a) 源代碼 class Spider public void run( ) 167: while () 168: if (q.size( ) =0) 170: continue; 189: item = q.deque

3、ue( ); 195: x = item.getD( ); Thread 046： item = ;47: qsize = 0;Thread 1133: return qsize; 115: if (qsize =0)115: return null;195: item.getD();Thread 2133: return qsize; 117: qsize -;1（b）執(zhí)行trace168-真依賴-189原子操作 (168,189)234NullPointerException!易出錯(cuò)Ad hoc同步使用次數(shù)及出錯(cuò)率統(tǒng)計(jì)研究動(dòng)機(jī)ACSAUSTC6應(yīng)用#ad hoc同步#錯(cuò)誤同步Apache3

4、36 (22%)OpenLDAP1510 (67%)Cherokee63 (50%)Mozilla-js175 (30%)Transmission138 (62%)難調(diào)試并行錯(cuò)誤測試空間研究動(dòng)機(jī)ACSAUSTC7Thread1 Thread2 Thread3 Thread4rrwwrwrwrrwwrwrw(a)所有的交互標(biāo)準(zhǔn)訪問變量U訪問變量V難調(diào)試并行錯(cuò)誤測試空間研究動(dòng)機(jī)ACSAUSTC8Thread1 Thread2 Thread3 Thread4rrwwrwrwrrwwrwrw(b)線程對的交互標(biāo)準(zhǔn)訪問變量U訪問變量V難調(diào)試并行錯(cuò)誤測試空間研究動(dòng)機(jī)ACSAUSTC9Thread1 Thr

5、ead2 Thread3 Thread4rrwwrwrwrrwwrwrw(a)單個(gè)變量的交互標(biāo)準(zhǔn)訪問變量U訪問變量V難調(diào)試并行錯(cuò)誤測試空間研究動(dòng)機(jī)ACSAUSTC10Thread1 Thread2 Thread3 Thread4rrwwrwrwrrwwrwrw(c)多個(gè)變量的交互標(biāo)準(zhǔn)訪問變量U訪問變量V難調(diào)試調(diào)度敏感，并行錯(cuò)誤只在特定的調(diào)度中發(fā)生研究動(dòng)機(jī)ACSAUSTC11Thread1Thread2v=1;(a)源代碼1. v=12. v=2(b) Trace 12. v=11. v=2(c) Trace 2Thread1使用的CPU被搶占正確的出錯(cuò)v=2;Heisenbug難調(diào)試并行錯(cuò)誤的

6、危害Blackout 造成供大范圍電故障研究動(dòng)機(jī)ACSAUSTC12所有可能的調(diào)度空間和交互空間出錯(cuò)的子空間并行程序測試系統(tǒng)枚舉搶占(PLDI07)，控制背景切換次數(shù)壓力測試多次運(yùn)行或長時(shí)間運(yùn)行時(shí)，增加錯(cuò)誤發(fā)生機(jī)會(huì)調(diào)度控制靜態(tài)調(diào)度(ASPLOS09)，插入睡眠操作，增加錯(cuò)誤發(fā)生機(jī)會(huì)動(dòng)態(tài)調(diào)度(ASPLOS10, PLDI12)，動(dòng)態(tài)調(diào)整線程優(yōu)先級(jí)，使錯(cuò)誤以一定概率發(fā)生研究現(xiàn)狀A(yù)CSAUSTC13并行程序檢錯(cuò)動(dòng)態(tài)分析Happen-before graphLockset algorithm靜態(tài)分析Point to分析別名分析研究現(xiàn)狀A(yù)CSAUSTC14確定性并行系統(tǒng)運(yùn)行時(shí)麻省理工學(xué)院-Kendo 麻

7、省大學(xué)-Grace 、DTHREADS 運(yùn)行時(shí)+編譯器華盛頓大學(xué)-CoreDet 操作系統(tǒng)內(nèi)核華盛頓大學(xué)-dOS 記錄與重放華盛頓大學(xué)-Tom Bergan (OOPSLA13)哥倫比亞大學(xué)-Junfeng Yang (SOSP11)硬件華盛頓大學(xué)-DMP研究現(xiàn)狀A(yù)CSAUSTC15確定性并行系統(tǒng)性能及實(shí)現(xiàn)總結(jié)研究現(xiàn)狀A(yù)CSAUSTC16確定性系統(tǒng)確定性強(qiáng)度實(shí)現(xiàn)手段兼容Pthreads庫運(yùn)行時(shí)開銷Kendo弱運(yùn)行時(shí)庫部分支持1x-1.6xCoreDet強(qiáng)編譯器和運(yùn)行時(shí)庫是1.2x-10 xDMP強(qiáng)硬件是1x-1.7xGrace強(qiáng)運(yùn)行時(shí)庫否1.2x-3.6xDTHREADS強(qiáng)運(yùn)行時(shí)庫是1x-1.

8、16x確定性并行系統(tǒng)實(shí)現(xiàn)策略狀態(tài)隔離完全隔離，e.g. 事務(wù)內(nèi)存（DMP），進(jìn)程（Grace、DTHREADS）共享內(nèi)存操作限制（CoreDet）確定提交版本控制，與事務(wù)內(nèi)存提交版本控制原理相同fork/join，利用任務(wù)創(chuàng)建次序隱含的串行語義研究現(xiàn)狀A(yù)CSAUSTC17確定性并行評(píng)估優(yōu)勢減少并行錯(cuò)誤的發(fā)生減小并行測試空間開放性問題運(yùn)行時(shí)開銷性能可擴(kuò)展性，調(diào)度機(jī)制影響串行階段的比例穩(wěn)定性并行程序開發(fā)效率，e.g. 增量式開發(fā)可調(diào)試性輸入敏感研究現(xiàn)狀A(yù)CSAUSTC18并行程序調(diào)試測試覆蓋率數(shù)據(jù)交互空間覆蓋調(diào)度空間覆蓋輸入覆蓋并行編程并行錯(cuò)誤避免順序違反原子違反數(shù)據(jù)沖突死鎖研究內(nèi)容ACSAUST

9、C19Thread2v=1;(a)源代碼v=2;Heisenbug1. v=12. v=2(b) 唯一的交互行為正確的Thread1自容錯(cuò)部分并行錯(cuò)誤自容錯(cuò)Thread2Thread1確定性并行系統(tǒng)利用確定性并行系統(tǒng)提供并行軟件開發(fā)環(huán)境，提高并行軟件開發(fā)效率、可靠性，并保證性能。降低編程難度可靠性性能及可擴(kuò)展性研究內(nèi)容ACSAUSTC20確定性運(yùn)行時(shí)狀態(tài)隔離利用進(jìn)程替代線程執(zhí)行并行任務(wù)確定性調(diào)度訪存計(jì)數(shù)，利用訪存數(shù)量上限作為并行執(zhí)行階段劃分依據(jù)令牌調(diào)度，利用token控制進(jìn)程順序地提交技術(shù)路線ACSAUSTC21確定性調(diào)度算法并行階段同步點(diǎn)訪存數(shù)量串行階段順序訪問技術(shù)路線ACSAUSTC22內(nèi)

10、存管理獨(dú)立內(nèi)存分配技術(shù)路線ACSAUSTC23內(nèi)存管理內(nèi)存狀態(tài)隔離技術(shù)路線ACSAUSTC24內(nèi)存管理共享內(nèi)存更新技術(shù)路線ACSAUSTC25確定性并行程序測試測試空間劃分框架-計(jì)算一個(gè)確定性trace切片的前提條件技術(shù)路線ACSAUSTC26記錄tracetrace切片抽取同步點(diǎn)調(diào)度指導(dǎo)程序簡化簡化的程序別名分析符號(hào)執(zhí)行前提條件確定性并行程序測試測試空間劃分框架-根據(jù)前提條件檢查結(jié)果劃分測試輸入空間技術(shù)路線ACSAUSTC27輸入滿足已生成前提條件PreCj原始輸入將輸入添加到子空間Ij是執(zhí)行前提條件生產(chǎn)模塊生成新的輸入子空間否Bouncer Checker實(shí)驗(yàn)工具Pin插樁工具記錄軟件，記

11、錄調(diào)度過程指令和調(diào)度事件KLEE，管理符號(hào)執(zhí)行過程，生成一個(gè)調(diào)度trace需要的前提條件序列Bouncer，檢查輸入是否滿足已知調(diào)度的前提條件基準(zhǔn)測試程序集RADBenchPARSEC實(shí)驗(yàn)方案ACSAUSTC28充分調(diào)研并行程序多線程運(yùn)行時(shí)庫程序靜態(tài)分析程序調(diào)試技術(shù)框架實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)狀態(tài)隔離及內(nèi)存管理修改運(yùn)行時(shí)庫接口，實(shí)現(xiàn)確定性運(yùn)行時(shí)可借鑒KLEE、Bouncer實(shí)現(xiàn)的并行程序切片技術(shù)、符號(hào)執(zhí)行以及前提條件檢查可行性分析ACSAUSTC29確定性運(yùn)行時(shí)穩(wěn)定性訪存以外的代碼改動(dòng)不改變調(diào)度和內(nèi)存交互可調(diào)試性狀態(tài)隔離，控制了共享數(shù)據(jù)交互空間確定調(diào)度順序，保證了錯(cuò)誤可重現(xiàn)確定性的并行程序測試降低確定性并行程序的測試輸入敏感性，提高測試效率創(chuàng)新性ACSAUSTC302013/12-2014/1搭建實(shí)驗(yàn)環(huán)境，熟悉各實(shí)驗(yàn)工具，完成系統(tǒng)詳細(xì)設(shè)計(jì)2014/2-2014/3實(shí)現(xiàn)確定性運(yùn)行時(shí)系統(tǒng)，并進(jìn)行性能