【摘要】：隨著多核處理器的流行，共享內(nèi)存多線程程序成為挖掘多核處理器系統(tǒng)并行性的重要手段。然而，共享內(nèi)存多線程程序在執(zhí)行時存在不確定性，即在相同輸入下，同一程序在同一臺多核處理器系統(tǒng)上運行多次，運行的結(jié)果可能會不同。這種執(zhí)行時的不確定性給共享內(nèi)存多線程程序的編寫、調(diào)試和應(yīng)用等都帶來了很大挑戰(zhàn)。 劃分為記錄和重演兩個階段的確定性重演機制是解決共享內(nèi)存多線程程序執(zhí)行不確定性的有效手段。確定性重演機制通過在記錄階段記錄程序運行時存在的不確定性信息，在重演階段使用所記錄的不確定性信息強迫程序再現(xiàn)原始的執(zhí)行結(jié)果。內(nèi)存競爭作為不確定性信息的主要來源，記錄的信息量大、記錄時帶來的開銷大，使得內(nèi)存競爭記錄成為實現(xiàn)多核處理器確定性重演的關(guān)鍵。本文研究高效的、硬件實現(xiàn)的內(nèi)存競爭記錄機制，針對當(dāng)前硬件實現(xiàn)的內(nèi)存競爭記錄機制面臨的挑戰(zhàn)，力求在內(nèi)存競爭日志、硬件資源消耗、帶寬開銷、重演速度等方面取得好的研究成果。 首先，本文提出了分段式內(nèi)存競爭記錄機制。點到點的內(nèi)存競爭記錄方式在重演方面具有優(yōu)勢，具有良好的應(yīng)用前景，但其硬件實現(xiàn)帶來了較大的硬件資源消耗。因此，本文開展了低硬件消耗的點到點內(nèi)存競爭記錄方式的研究，提出了支持并發(fā)重演的分段式內(nèi)存競爭記錄機制。該機制用當(dāng)前發(fā)生序—沖突發(fā)生時沖突雙方所在處理器核的當(dāng)前指令計數(shù)值構(gòu)成的依賴關(guān)系表示沖突，無需保存沖突雙方對應(yīng)內(nèi)存操作的指令計數(shù)值；采用分段的可推導(dǎo)約減算法，約減掉可以被已記錄的當(dāng)前發(fā)生序推導(dǎo)出來的沖突；對于已被替換出cache的內(nèi)存塊對應(yīng)的沖突，則使用最大近似段時戳法進行檢測。在硬件實現(xiàn)中，該機制為每個內(nèi)存塊存儲一個用具有更小尺寸的段號標(biāo)記的cache塊時戳，降低了硬件消耗；同時，采用間隔指令計數(shù)值替換指令計數(shù)值，進一步優(yōu)化了內(nèi)存競爭日志。仿真結(jié)果表明，該機制帶來的硬件消耗低，也減小了內(nèi)存競爭日志，降低了帶寬開銷。 其次，本文提出了基于簽名的循環(huán)式內(nèi)存競爭記錄機制。通過在cache中增加時戳字段實現(xiàn)內(nèi)存競爭記錄功能，會影響系統(tǒng)原有的cache結(jié)構(gòu)，給多核處理器的設(shè)計帶來很大挑戰(zhàn)。因此，為了所添加的內(nèi)存競爭記錄功能不影響原有系統(tǒng)的cache結(jié)構(gòu)，本文研究了基于簽名的循環(huán)式內(nèi)存競爭記錄機制。簽名是一種高效的硬件實現(xiàn)機制，在內(nèi)存競爭檢測方面可以獲得較好的時間和空間效率。該記錄機制僅為每個處理器核添加若干個小尺寸的讀簽名和寫簽名，通過使用簽名的插入和查找操作實現(xiàn)沖突的檢測，在無需更改原有cache結(jié)構(gòu)的同時，進一步降低了硬件消耗。在此基礎(chǔ)上，，該機制又采用循環(huán)發(fā)生序約減連續(xù)同向的當(dāng)前發(fā)生序，在能夠?qū)崿F(xiàn)并發(fā)確定性重演的前提下，進一步優(yōu)化了內(nèi)存競爭日志。在硬件實現(xiàn)中，該記錄機制采用一種簡潔的方向檢測機制檢測連續(xù)同向的當(dāng)前發(fā)生序，無需添加太多額外的硬件資源就可以實現(xiàn)循環(huán)發(fā)生序的記錄。仿真結(jié)果表明，該機制相比已有的點到點內(nèi)存競爭記錄機制，在無需更改原有cache結(jié)構(gòu)的前提下，硬件消耗、內(nèi)存競爭日志和帶寬開銷都得到了很大改善。 第三，本文提出了同步敏感的內(nèi)存競爭記錄機制。內(nèi)存競爭只是內(nèi)存沖突的一部分，也并非所有的內(nèi)存競爭都影響確定性重演，因此，如果在內(nèi)存競爭記錄時過濾掉不影響確定性重演的沖突，將會有效減小內(nèi)存競爭日志。因此，本文研究了同步敏感的內(nèi)存競爭記錄機制。該機制通過離線的方式分析同步操作帶來的沖突對確定性重演的影響，將同步操作引入的沖突劃分為有害的同步?jīng)_突和無害的同步?jīng)_突，無害的同步?jīng)_突不會影響確定性重演，可以不予記錄。該機制通過添加兩條新的指令能夠識別常用的鎖和障礙兩種同步操作，并將它們引入的不影響確定性重演的同步?jīng)_突在沖突檢測階段過濾掉。仿真結(jié)果表明，該機制有效減小了內(nèi)存競爭日志，也進一步降低了帶寬開銷。 第四，本文提出了分離式內(nèi)存競爭記錄機制。重演速度是衡量內(nèi)存競爭記錄機制優(yōu)劣的一個非常重要的方面，而原有的并發(fā)重演算法存在效率低下問題。因此，為了進一步提高并發(fā)重演的速度，本文提出了分離式內(nèi)存競爭記錄機制。該機制分別在一致性協(xié)議的應(yīng)答方和請求方分開記錄當(dāng)前發(fā)生序?qū)?yīng)的先發(fā)生方和后發(fā)生方，僅在需要記錄內(nèi)存競爭時向一致性協(xié)議的應(yīng)答消息中添加一位沖突記錄標(biāo)志位，減小了記錄階段的通信開銷。同時引入一種大小自適應(yīng)的記錄格式，在記錄內(nèi)存競爭時，處理器核根據(jù)先發(fā)生方及后發(fā)生方的大小選擇合適的記錄格式，減小了單個記錄的尺寸。更重要的是，在這種分離式內(nèi)存競爭記錄方式下，沖突先發(fā)生方所在處理器核能夠在重演時積極主動的為沖突后發(fā)生方創(chuàng)建并發(fā)送喚醒消息，提高了重演的速度。仿真結(jié)果表明，該機制在重演速度、內(nèi)存競爭日志及帶寬開銷方面均具有較高的性能。 本文在以下5個方面明顯改善了已有點到點內(nèi)存競爭記錄機制的性能：內(nèi)存競爭日志、硬件資源消耗、帶寬開銷、重演速度及可應(yīng)用性。相比其他記錄方式，也在以下方面具有明顯的優(yōu)勢：內(nèi)存競爭日志、帶寬開銷、重演速度及可應(yīng)用性。
[Abstract]:......
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：博士
【學(xué)位授予年份】：2013
【分類號】：TP332

【相似文獻】

相關(guān)期刊論文 前10條

1 ;英特爾公司推出新一代Pentium Pro處理器[J];中國電子商情;1996年02期

2 ;Altera宣布為Nios Ⅱ處理器系統(tǒng)提供新的C語言至硬件加速工具[J];電子與電腦;2006年05期

3 ;汽車用GPS導(dǎo)航系統(tǒng)解決方案[J];世界電子元器件;2006年09期

4 徐鳳英;;Quad FX反戈一擊[J];新電腦;2007年02期

5 ;MCU應(yīng)用新世界：Cortex-M1微控制器和FPGA[J];世界電子元器件;2008年05期

6 岳陽;;領(lǐng)略英特爾“超線程”技術(shù)[J];電腦采購周刊;2002年46期

7 付漢杰;;利用NIOS Ⅱ處理器構(gòu)建節(jié)省成本的嵌入式系統(tǒng)[J];今日電子;2007年05期

8 ;要聞速遞[J];電腦采購周刊;2001年34期

9 劉磊;;對片上多核系統(tǒng)的系統(tǒng)結(jié)構(gòu)的研究[J];電腦知識與技術(shù);2008年29期

10 張越;;圖形工作站 升級雙核 Dell Precision 670[J];個人電腦;2006年02期

相關(guān)會議論文 前10條

1 單書暢;胡瑜;李曉維;;多核處理器的核級冗余容錯技術(shù)[A];第六屆中國測試學(xué)術(shù)會議論文集[C];2010年

2 譚小彬;孔德光;奚宏生;;多線程程序時序的統(tǒng)計分析[A];第二十七屆中國控制會議論文集[C];2008年

3 張曉輝;程歸鵬;從明;;龍芯處理器上的TLB性能優(yōu)化技術(shù)[A];2010年第16屆全國信息存儲技術(shù)大會（IST2010）論文集[C];2010年

4 李雙權(quán);陳火炎;孫玉霞;;一種Java多線程可達性測試框架系統(tǒng)的研究與實現(xiàn)[A];第十屆全國容錯計算學(xué)術(shù)會議論文集[C];2003年

5 李震宇;王秀波;;艦船噪聲測量現(xiàn)場實時監(jiān)測系統(tǒng)[A];第十一屆船舶水下噪聲學(xué)術(shù)討論會論文集[C];2007年

6 周志遠(yuǎn);張大方;繆力;趙丹;黃谷;;基于Java內(nèi)存模型的并發(fā)程序模型檢測[A];第五屆中國測試學(xué)術(shù)會議論文集[C];2008年

7 祁舒U

本文編號：2302010