[發(fā)明專利]編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法及裝置

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010160536.1
• 申請(qǐng)日: 2010-04-30
• 公開(kāi)（公告）號(hào): CN101833440A
• 公開(kāi)（公告）日: 2010-09-15
• 發(fā)明（設(shè)計(jì)）人: 趙銀亮;王旭昊;韋遠(yuǎn)科;宋少龍
• 申請(qǐng)（專利權(quán)）人: 西安交通大學(xué)
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38
• 代理公司: 西安通大專利代理有限責(zé)任公司 61200
• 代理人: 陸萬(wàn)壽

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)領(lǐng)域，涉及線程級(jí)并行與推測(cè)多線程技術(shù)，特別涉及編譯器支持下對(duì)內(nèi)存數(shù)據(jù)進(jìn)行同步的推測(cè)多線內(nèi)存數(shù)據(jù)同步執(zhí)行方法及裝置。

背景技術(shù)

當(dāng)前線程級(jí)并行已成為并行處理和并行計(jì)算的發(fā)展趨勢(shì)。一方面，多核處理器已經(jīng)得到了普遍的應(yīng)用。另一方面，片上多處理器因?yàn)槠浜酥g更大的帶寬和更低的通信延遲，為線程級(jí)并行技術(shù)提供了巨大的應(yīng)用平臺(tái)。但是，處理器核的利用效率往往受到各種因素的制約，而一些并行程序設(shè)計(jì)方法又給用戶和編程人員帶來(lái)了額外的負(fù)擔(dān)。推測(cè)多線程技術(shù)(SpMT，SpeculativeMultithreading)就是在這樣的背景下被提出的。

對(duì)于推測(cè)多線程技術(shù)，編譯器采用激進(jìn)的策略，自動(dòng)將高級(jí)語(yǔ)言編寫(xiě)的串行程序劃分為多線程程序，并允許線程間存在一定的數(shù)據(jù)依賴。當(dāng)多個(gè)線程并行執(zhí)行時(shí)，由硬件動(dòng)態(tài)檢測(cè)線程間的數(shù)據(jù)依賴違規(guī)，緩存推測(cè)數(shù)據(jù)并實(shí)現(xiàn)數(shù)據(jù)一致性的維護(hù)，通過(guò)線程的提交、撤銷、驗(yàn)證等機(jī)制，保證程序并行執(zhí)行的正確性。

線程間的數(shù)據(jù)依賴程度，是影響推測(cè)多線程執(zhí)行效率的關(guān)鍵因素之一。線程間的數(shù)據(jù)依賴主要包括寄存器數(shù)據(jù)依賴和內(nèi)存數(shù)據(jù)依賴；這兩種數(shù)據(jù)依賴在運(yùn)行時(shí)都會(huì)發(fā)生讀后寫(xiě)(RAW，Read?After?Write)內(nèi)存數(shù)據(jù)依賴違規(guī)。在運(yùn)行時(shí)發(fā)生的讀后寫(xiě)內(nèi)存數(shù)據(jù)依賴違規(guī)，將直接導(dǎo)致線程的重啟，并且讀取了錯(cuò)誤數(shù)據(jù)的線程的所有后繼子線程將會(huì)被直接撤銷。這就造成了處理器資源的浪費(fèi)，制約了程序并行執(zhí)行加速比的提高。

解決數(shù)據(jù)依賴的方法主要有兩種：值預(yù)測(cè)技術(shù)和數(shù)據(jù)同步技術(shù)。對(duì)于寄存器數(shù)據(jù)依賴，可通過(guò)傳統(tǒng)的編譯數(shù)據(jù)流分析技術(shù)，如到達(dá)定值分析，活躍變量分析等技術(shù)結(jié)合值預(yù)測(cè)技術(shù)等予以解決。而對(duì)于內(nèi)存數(shù)據(jù)依賴，往往不能通過(guò)靜態(tài)的數(shù)據(jù)流分析技術(shù)得到精確的依賴結(jié)果。這使得值預(yù)測(cè)技術(shù)和數(shù)據(jù)同步技術(shù)不能有效地解決線程間的內(nèi)存數(shù)據(jù)依賴。

發(fā)明內(nèi)容

本發(fā)明解決的問(wèn)題在于提供一種編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法及裝置，能在程序運(yùn)行時(shí)對(duì)選定的讀寫(xiě)內(nèi)存指令進(jìn)行同步，降低讀后寫(xiě)數(shù)據(jù)依賴違規(guī)發(fā)生的次數(shù)，提高多線程程序并行運(yùn)行的加速比。

本發(fā)明是采取以下的技術(shù)方案來(lái)實(shí)現(xiàn)：

一種編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，包括以下步驟：

1)程序由硬件線程劃分器劃分生成多線程匯編程序后，作為硬件程序剖析器的輸入，并在其上運(yùn)行；

2)硬件程序剖析器在運(yùn)行程序時(shí)統(tǒng)計(jì)內(nèi)存數(shù)據(jù)依賴違規(guī)情況，并將統(tǒng)計(jì)結(jié)果信息反饋給同步編譯模塊；

3)同步編譯模塊讀取統(tǒng)計(jì)結(jié)果信息，通過(guò)計(jì)算同步代價(jià)獲取進(jìn)行多線程同步操作的候選讀/寫(xiě)指令對(duì)；然后通過(guò)數(shù)據(jù)流分析之后，在讀指令前添加一條stall指令，并將讀指令替換為同步讀指令synload，在寫(xiě)指令后添加一條或多條forward指令；在寫(xiě)指令所在線程的線程發(fā)起指令spawn后添加一條synset指令；最后經(jīng)匯編鏈接生成可執(zhí)行文件加載后在模擬器上運(yùn)行；

當(dāng)同步子線程執(zhí)行到stall指令時(shí)，停止執(zhí)行后續(xù)指令，等待一段時(shí)間；直至對(duì)應(yīng)的同步父線程執(zhí)行完相應(yīng)的寫(xiě)指令和forward指令，收到同步父線程發(fā)送的含有內(nèi)存地址和寫(xiě)入數(shù)據(jù)的同步消息，再根據(jù)接收到的同步信息和此前同步子線程對(duì)同一內(nèi)存地址的寫(xiě)入情況，對(duì)Sbuffer中的use_flag進(jìn)行置位或復(fù)位，根據(jù)該標(biāo)志位決定是否使用同步父線程發(fā)送來(lái)的數(shù)據(jù)，而后停止等待，繼續(xù)執(zhí)行后續(xù)指令；

同步子線程在接收同步消息后的操作由synload指令的執(zhí)行完成，同步父線程在寫(xiě)入數(shù)據(jù)后發(fā)送同步消息的操作由forward指令完成；

4)多線程程序以同步的方式推測(cè)執(zhí)行，模擬器輸出程序運(yùn)行的結(jié)果。

所述的統(tǒng)計(jì)內(nèi)存數(shù)據(jù)依賴違規(guī)情況包括：讀/寫(xiě)指令被執(zhí)行的次數(shù)及其PC值，讀/寫(xiě)指令發(fā)生讀后寫(xiě)內(nèi)存數(shù)據(jù)依賴違規(guī)的次數(shù)，發(fā)生讀后寫(xiě)內(nèi)存數(shù)據(jù)依賴違規(guī)的讀/寫(xiě)指令執(zhí)行的間隔時(shí)間；統(tǒng)計(jì)結(jié)果信息被寫(xiě)入到一個(gè)文件中，反饋給同步編譯模塊。

所述的計(jì)算同步代價(jià)，是計(jì)算多線程的讀/寫(xiě)指令對(duì)進(jìn)行同步操作后帶來(lái)加速比提高的潛力，獲取加速比提高潛力大的候選讀/寫(xiě)指令對(duì)。

所述的加速比提高潛力通過(guò)內(nèi)存讀/寫(xiě)指令對(duì)發(fā)生數(shù)據(jù)依賴的頻率，線程體入口到讀指令的代碼距離以及讀指令到寫(xiě)指令之間的代碼距離來(lái)判定。

所述的數(shù)據(jù)流分析是在程序的控制流圖上進(jìn)行，以找到stall指令和forward指令的插入位置；其中，stall指令插入到需要同步的讀指令前，forward指令插入到需要同步的寫(xiě)指令和和線程出口之間的每一條路徑上。

所述的同步父線程發(fā)送同步消息的操作步驟為：