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

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 201010160536.1
• 申請(qǐng)日: 2010-04-30
• 公開（公告）號(hào): CN101833440A
• 公開（公告）日: 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)壽

1.一種編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，其特征在于，多線程程序?qū)崿F(xiàn)內(nèi)存數(shù)據(jù)同步包括以下步驟：

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)行多線程同步操作的候選讀/寫指令對(duì)；然后通過(guò)數(shù)據(jù)流分析之后，在讀指令前添加一條stall指令，并將讀指令替換為同步讀指令synload，在寫指令后添加一條或多條forward指令；在寫指令所在線程的線程發(fā)起指令spawn后添加一條synset指令；最后經(jīng)匯編鏈接生成可執(zhí)行文件加載后在模擬器上運(yùn)行；

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

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

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

2.如權(quán)利要求1所述的編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，其特征在于，所述的統(tǒng)計(jì)內(nèi)存數(shù)據(jù)依賴違規(guī)情況包括：讀/寫指令被執(zhí)行的次數(shù)及其PC值，讀/寫指令發(fā)生讀后寫內(nèi)存數(shù)據(jù)依賴違規(guī)的次數(shù)，發(fā)生讀后寫內(nèi)存數(shù)據(jù)依賴違規(guī)的讀/寫指令執(zhí)行的間隔時(shí)間；統(tǒng)計(jì)結(jié)果信息被寫入到一個(gè)文件中，反饋給同步編譯模塊。

3.如權(quán)利要求1所述的編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，其特征在于，所述的計(jì)算同步代價(jià)，是計(jì)算多線程的讀/寫指令對(duì)進(jìn)行同步操作后帶來(lái)加速比提高的潛力，獲取加速比提高潛力大的候選讀/寫指令對(duì)。

4.如權(quán)利要求3所述的編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，其特征在于，所述的加速比提高潛力通過(guò)內(nèi)存讀/寫指令對(duì)發(fā)生數(shù)據(jù)依賴的頻率，線程體入口到讀指令的代碼距離以及讀指令到寫指令之間的代碼距離來(lái)判定。

5.如權(quán)利要求1所述的編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，其特征在于，所述的數(shù)據(jù)流分析是在程序的控制流圖上進(jìn)行，以找到stall指令和forward指令的插入位置；其中，stall指令插入到需要同步的讀指令前，forward指令插入到需要同步的寫指令和和線程出口之間的每一條路徑上。

6.如權(quán)利要求1所述的編譯器支持下的推測(cè)多線程內(nèi)存數(shù)據(jù)同步執(zhí)行方法，其特征在于，所述的同步父線程發(fā)送同步消息的操作步驟為：

(1)在同步父線程發(fā)起同步子線程后，同步父線程執(zhí)行synset指令，向同步子線程發(fā)送消息，將同步子線程Sbuffer的syn_flag位置位；

(2)執(zhí)行store*p操作，常規(guī)的寫內(nèi)存操作；

(3)執(zhí)行save_address(p)操作，將寫入數(shù)據(jù)的內(nèi)存地址p保存到發(fā)送地址緩沖區(qū)；

(4)執(zhí)行receiver_id＝get_immed_successor()，獲取同步子線程的處理器編號(hào)；

(5)執(zhí)行mesg.value＝*p操作，將寫內(nèi)存操作寫入的數(shù)據(jù)寫入同步消息mesg的value域；

(6)執(zhí)行mesg.addr＝p操作，將寫入數(shù)據(jù)的內(nèi)存地址p寫入同步消息的addr域；

(7)執(zhí)行send(mesg，receiver_id)操作，將構(gòu)造好的同步消息發(fā)送給同步子線程。