編譯器支持下的推測多線程內存數據同步執行方法及裝置的製作方法

2023-09-18 07:21:35 1

專利名稱：編譯器支持下的推測多線程內存數據同步執行方法及裝置的製作方法
技術領域：
本發明屬於計算機領域，涉及線程級並行與推測多線程技術，特別涉及編譯器支 持下對內存數據進行同步的推測多線內存數據同步執行方法及裝置。
背景技術：
當前線程級並行已成為並行處理和並行計算的發展趨勢。一方面，多核處理器已 經得到了普遍的應用。另一方面，片上多處理器因為其核之間更大的帶寬和更低的通信延 遲，為線程級並行技術提供了巨大的應用平臺。但是，處理器核的利用效率往往受到各種因 素的制約，而一些並行程序設計方法又給用戶和編程人員帶來了額外的負擔。推測多線程 技術(SpMT，SpeculativeMultithreading)就是在這樣的背景下被提出的。對於推測多線程技術，編譯器採用激進的策略，自動將高級語言編寫的串行程序 劃分為多線程程序，並允許線程間存在一定的數據依賴。當多個線程並行執行時，由硬體動 態檢測線程間的數據依賴違規，緩存推測數據並實現數據一致性的維護，通過線程的提交、 撤銷、驗證等機制，保證程序並行執行的正確性。線程間的數據依賴程度，是影響推測多線程執行效率的關鍵因素之一。線程間的 數據依賴主要包括寄存器數據依賴和內存數據依賴；這兩種數據依賴在運行時都會發生讀 後寫(RAW，Read After Write)內存數據依賴違規。在運行時發生的讀後寫內存數據依賴 違規，將直接導致線程的重啟，並且讀取了錯誤數據的線程的所有後繼子線程將會被直接 撤銷。這就造成了處理器資源的浪費，制約了程序並行執行加速比的提高。解決數據依賴的方法主要有兩種值預測技術和數據同步技術。對於寄存器數據 依賴，可通過傳統的編譯數據流分析技術，如到達定值分析，活躍變量分析等技術結合值預 測技術等予以解決。而對於內存數據依賴，往往不能通過靜態的數據流分析技術得到精確 的依賴結果。這使得值預測技術和數據同步技術不能有效地解決線程間的內存數據依賴。

發明內容
本發明解決的問題在於提供一種編譯器支持下的推測多線程內存數據同步執行 方法及裝置，能在程序運行時對選定的讀寫內存指令進行同步，降低讀後寫數據依賴違規 發生的次數，提高多線程程序並行運行的加速比。本發明是採取以下的技術方案來實現一種編譯器支持下的推測多線程內存數據同步執行方法，包括以下步驟1)程序由硬體線程劃分器劃分生成多線程彙編程序後，作為硬體程序剖析器的輸 入，並在其上運行；2)硬體程序剖析器在運行程序時統計內存數據依賴違規情況，並將統計結果信息 反饋給同步編譯模塊；3)同步編譯模塊讀取統計結果信息，通過計算同步代價獲取進行多線程同步操作 的候選讀/寫指令對；然後通過數據流分析之後，在讀指令前添加一條stall指令，並將讀指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令；在寫指令所在 線程的線程發起指令spawn後添加一條synset指令；最後經彙編連結生成可執行文件加載 後在模擬器上運行；當同步子線程執行到stall指令時，停止執行後續指令，等待一段時間；直至對應 的同步父線程執行完相應的寫指令和forward指令，收到同步父線程發送的含有內存地址 和寫入數據的同步消息，再根據接收到的同步信息和此前同步子線程對同一內存地址的寫 入情況，對Sbuffer中的USe_flag進行置位或復位，根據該標誌位決定是否使用同步父線 程發送來的數據，而後停止等待，繼續執行後續指令；
同步子線程在接收同步消息後的操作由synload指令的執行完成，同步父線程在 寫入數據後發送同步消息的操作由forward指令完成；4)多線程程序以同步的方式推測執行，模擬器輸出程序運行的結果。所述的統計內存數據依賴違規情況包括讀/寫指令被執行的次數及其PC值，讀 /寫指令發生讀後寫內存數據依賴違規的次數，發生讀後寫內存數據依賴違規的讀/寫指 令執行的間隔時間；統計結果信息被寫入到一個文件中，反饋給同步編譯模塊。所述的計算同步代價，是計算多線程的讀/寫指令對進行同步操作後帶來加速比 提高的潛力，獲取加速比提高潛力大的候選讀/寫指令對。所述的加速比提高潛力通過內存讀/寫指令對發生數據依賴的頻率，線程體入口 到讀指令的代碼距離以及讀指令到寫指令之間的代碼距離來判定。所述的數據流分析是在程序的控制流圖上進行，以找到stall指令和forward指 令的插入位置；其中，stall指令插入到需要同步的讀指令前，forward指令插入到需要同 步的寫指令和和線程出口之間的每一條路徑上。所述的同步父線程發送同步消息的操作步驟為(1)在同步父線程發起同步子線程後，同步父線程執行synset指令，向同步子線 程發送消息，將同步子線程Sbuffer的syn_flag位置位；(2)執行Store*p操作，常規的寫內存操作；(3)執行Save_addreSS(p)操作，將寫入數據的內存地址p保存到發送地址緩衝 區；(4)執行 receiver_id = get_immed_successor ，獲取同步子線程的處理器編 號；(5)執行mesg. value = *p操作，將寫內存操作寫入的數據寫入同步消息mesg的 value 域；(6)執行mesg. addr = p操作，將寫入數據的內存地址p寫入同步消息的addr域；(7)執行sendOnesg，receiver_id)操作，將構造好的同步消息發送給同步子線程。所述的同步子線程接收同步消息的操作步驟為(1)執行stall 0操作，同步子線程查詢Sbuffer的ready_flag位是否被置位； 如果否，則同步子線程繼續處於阻塞狀態；如果是，則同步子線程結束阻塞狀態，進行後續 操作；(2)執行receive (mesg)操作，收到同步消息後，Sbuffer的ready_flag位被置位；(3)執行message_addr = mesg. addr，獲取同步消息的內存地址，存放於Sbuffer StJ message_addr _ ；(4)執行message_value = mesg. value，獲取同步消息的內存數據值，存放於 Sbuffer 的 message_value _ ；(5)執行verify(q，meSSage_addr)操作，檢查收到同步消息的內存地址是否與寫 指令操作所要讀取的內存地址q是同一地址，如果是則將Sbuffer的uSe_flag標誌位置 位；(6)執行loadecLvalue = load*q操作，進行常規的讀內存操作，將讀到的寫入數 據放入memory—value中；在進行讀操作的同時，檢查當前線程是否已經向內存地址q處寫 入數據，如果是，則將Sbuffer的uSe_flag標誌位復位；(7)執行 result = choose (loaded_value,message_value)操作，如果 Sbuffer 的 USe_flag標誌位被置位，則同步子線程採用同步消息中的內存數據值作為線程同步讀操作 最後讀取數據的結果；如果uSe_flag標誌位被復位，則使用loadecLvalue的值作為線程同 步讀操作最後讀取數據的結果；(8)執行 quit 操作,將 Sbuffer 的 ready_flag 位復位,將 Sbuffer 的 use_flag 位復位。一種完成編譯器支持下的推測多線程內存數據同步執行方法的裝置，包括以下模 塊線程劃分器，將程序劃分生成多線程彙編程序後，作為硬體程序剖析器的輸入，並 在其上運行；硬體程序剖析器，硬體程序剖析器在運行程序時統計內存數據依賴違規情況，並 將統計結果信息反饋給同步編譯模塊；同步編譯模塊，同步編譯模塊讀取統計結果信息，通過計算同步代價獲取進行多 線程同步操作的候選讀/寫指令對；然後通過數據流分析之後，在讀指令前添加一條stall 指令，並將讀指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令， 在寫指令所在線程的線程發起指令spawn後添加一條synset指令；彙編連結器，彙編程序經彙編連結後生成二進位的可執行文件；模擬器，可執行文件加載後在模擬器上運行；包括對同步機制下內存讀指令和內 存寫指令的擴展支持；同步機制下獲取內存數據的操作為當同步子線程執行到stall指令時，停止執 行後續指令，等待一段時間；直至對應的同步父線程執行完相應的寫指令和forward指令， 收到同步父線程發送的含有內存地址和寫入數據的同步消息，再根據接收到的同步信息 和此前同步子線程對同一內存地址的寫入情況，對Sbuffer中的uSe_flag進行置位或復 位，根據該標誌位決定是否使用同步父線程發送來的數據，而後停止等待，繼續執行後續指 令；同步機制下寫入和發送數據的操作為當同步父線程執行完相應的寫指令和 forward指令時，將含有寫指令對應的內存地址保存到發送地址緩衝區，將內存地址和寫入 數據以消息的形式發送給同步子線程；
多線程程序以同步的方式推測執行，模擬器輸出程序運行的結果。所述的發送地址緩衝區是記錄所有已經由forward指令發送過的數據的地址的 數據緩衝區。
所述的Sbuffer是用於接收同步消息和控制同步操作的寄存器文件；Sbuffer由 五個域組成三個控制標誌位sync_flag, ready_flag禾口 use_flag,兩個消息域message_ addr和message_value ；線程處理單元在初始化時會將Sbuffer的所有標誌位復位；synC_flag位表示是否按同步方法執行，當該標誌位被置位，表示按照同步方法執 行；當該標誌位被復位，表示按常規的方法執行，此時stall指令被跳過，synload指令完成 的操作等同於常規的load指令，消息域中的數據無效；ready_flag位表示同步消息是否已經準備好，當該標誌位被置位表示同步消息已 經準備好；USe_flag位表示同步子線程是否使用消息中的數據，當該標誌位被置位表示同步 子線程將使用消息中的數據，當該標誌位被復位表示同步子線程將使用常規讀操作獲得內 存數據；message_addr用來存儲同步消息的addr域；message_value用來存儲同步消息的value域。與現有技術相比，本發明具有以下有益的技術效果本發明提供的編譯器支持下的推測多線程內存數據同步執行方法及其裝置，能在 運行時對選定的讀/寫內存指令進行同步，降低讀後寫數據依賴違規發生的次數，提高多 線程程序並行運行的加速比。本發明對進行多線程同步操作的候選讀/寫指令對的獲取，通過硬體程序剖析器 獲得，在運行程序時統計內存數據依賴違規情況，並將統計結果信息反饋給同步編譯模塊， 進而通過計算同步代價獲取進行多線程同步操作的候選讀/寫指令對。當硬體程序剖析器 在運行程序時，其目的主要是剖析程序的動態訪存特徵，程序以輕量級方式運行，不會帶來 過多的額外開銷；而獲取提高加速比潛力大的候選讀/寫指令對，對於頻繁發生數據依賴 的內存讀寫指令對，對其進行同步往往能帶來較高的加速比提升；而對於非頻繁發生數據 依賴的內存讀寫指令對，針對其添加同步指令後，運行時往往會出現一些不必要同步，或過 度同步現象。另一方面，對於一個線程，如果線程體入口到同步候選讀指令的代碼距離較 大，並且同步候選讀指令到同步候選寫指令之間的代碼距離較小，則同步效果會更顯著。為了降低讀後寫數據依賴違規發生的次數，本發明通過讀指令前添加一條stall 指令。執行stall指令後，同步子線程被阻塞，等待同步父線程產生需要的內存數據；在寫 指令後添加一條或多條forward指令；同步子線程在接收同步消息後的操作由synload指 令的執行完成，同步父線程在寫入數據後發送同步消息的操作由forward指令完成；當同步子線程執行到stall指令時，停止執行後續指令，等待一段時間；直至對應 的同步父線程執行完相應的寫指令和forward指令，收到發送含有內存地址和寫入數據的 消息，再根據接收到的同步信息和此前同步子線程對同一內存地址的寫入情況，對Sbuffer 中的use_f lag進行置位或復位，根據該標誌位決定是否使用同步父線程發送來的數據，而 後停止等待，繼續執行後續指令；按照本發明的同步執行方法，同步讀線程在進行數據同步後，可獲取正確的內存數據，避免因讀後寫數據依賴違規而被撤銷，保留了在stall指令執行前處理器核完成的 工作，降低了線程的重啟和撤銷所造成的處理器資源的浪費。除了硬體程序剖析器對獲取候選讀/寫指令對的統計支持，為了支持同步子線程 與同步父線程的同步操作，本發明的模擬器新擴展的功能模塊主要包括一個發送地址緩衝 區和一個本地寄存器文件Sbuffer。發送地址緩衝區是一個很小的數據緩衝區，用於記錄本線程中所有已經由 forward指令發送過的數據的地址。本地寄存器文件Sbuffer是用於接收同步消息和控制 同步操作的寄存器文件。對於內存讀/寫指令發生數據依賴的頻率，可通過大量實驗獲得的經驗值。本發 明具體從Olden基準程序選取了 7個測試程序，按Prophet線程劃分方法，在4核的模擬器 上推測執行的測試，可獲得平均34%的加速比提高。採用同步方法執行，數據依賴頻率的最 小值設定為15%，線程體入口到讀指令的代碼距離與寫指令到線程出口的代碼距離比最小 值定位1，選取讀/寫內存指令同步執行，與非同步的推測執行相比，加速比可獲得平均
的提升。可見本發明的同步方法對推測執行的加速比有較明顯的提升。


圖1為編譯器支持下的推測多線程內存數據同步執行方法的流程示意圖。圖2為同步父線程與同步子線程的讀/寫指令對同步操作示意圖。圖3為多線程內存數據執行的多處理單元(多核體系)結構框架示意圖。圖4為Sbuffer設計示意圖。圖5為同步子線程同步讀操作實施的操作示意圖。
具體實施例方式下面結合附圖對本發明作進一步詳細說明。所述是對本發明的解釋而不是限定。參見圖1，所示的編譯器支持的推測多線程系統，主要由編譯器和模擬器兩部分組 成；其中，硬體程序剖析器可以是通過在模擬器上擴展程序內存讀寫指令統計模塊得到的 模塊。硬體程序剖析器在程序運行時記錄程序執行的歷史讀寫信息，以及內存數據依賴信 息，通過指令的pc值，藉助彙編連結器確定讀寫指令的位置。當硬體程序剖析器在運行程 序時，其目的主要是剖析程序的動態訪存特徵，程序以輕量級方式運行，並不會帶來過多的 額外開銷。編譯器支持下的推測多線程內存數據同步執行方法，包括以下步驟1)程序由硬體線程劃分器劃分生成多線程彙編程序後，作為硬體程序剖析器的輸 入，並在其上運行；2)硬體程序剖析器在運行程序時統計內存數據依賴違規情況，並將統計結果信息 反饋給同步編譯模塊；3)同步編譯模塊讀取統計結果信息，通過計算同步代價獲取進行多線程同步操作 的候選讀/寫指令對；然後通過數據流分析之後，在讀指令前添加一條stall指令，並將讀 指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令；在寫指令所在 線程的線程發起指令spawn後添加一條synset指令；最後經彙編連結生成可執行文件加載後在模擬器上運行；當同步子線程執行到stall指令時，停止執行後續指令，等待一段時間；直至對應 的同步父線程執行完相應的寫指令和forward指令，收到同步父線程發送的含有內存地址 和寫入數據的同步消息，再根據接收到的同步信息和此前同步子線程對同一內存地址的寫 入情況，對Sbuffer中的USe_flag進行置位或復位，根據該標誌位決定是否使用同步父線 程發送來的數據，而後停止等待，繼續執行後續指令；同步子線程在接收同步消息後的操作由synload指令的執行完成，同步父線程在 寫入數據後發送同步消息的操作由forward指令完成；4)多線程程序以同步的方式推測執行，模擬器輸出程序運行的結果。上述步驟3)所述的同步編譯模塊進行的計算同步代價，是計算多線程的讀/寫 指令對進行同步操作後帶來加速比提高的潛力，獲取加速比提高潛力大的候選讀/寫指令 對。所述的加速比提高潛力大的讀/寫指令對為對於頻繁發生數據依賴的內存讀/寫指令對，對其進行同步往往能帶來較高的加 速比提升；而對於非頻繁發生數據依賴的內存讀寫指令對，針對其添加同步指令後，運行時 往往會出現一些不必要同步，或過度同步現象；除了數據依賴發生的頻率，線程入口到寫指令之間的代碼距離等也被作為評價同 步代價的考慮因素。如果線程體入口到同步候選讀指令的代碼距離較大，並且同步候選讀 指令到同步候選寫指令之間的代碼距離較小，則同步效果會更顯著。綜合考慮上述因素，選 取具有較大加速比提升潛力的讀/寫指令對。對於內存讀/寫指令發生數據依賴的頻率，以及線程體入口到讀指令的代碼距 離，寫指令到線程出口的代碼距離，均依賴於具體的執行程序。本方法通過實驗數據確定合 適的閥值，作為內存讀/寫指令的同步標準。所述的同步編譯模塊進行的數據流分析，是在程序的控制流圖上進行，以找到 stall指令和forward指令的插入位置；其中，stall指令插入到需要同步的讀指令前， forward指令插入到需要同步的寫指令和和線程出口之間的每一條路徑上。基於上述方法，完成編譯器支持下的推測多線程內存數據同步執行方法的裝置的具體實施方式
，包括以下模塊線程劃分器，將程序劃分生成多線程彙編程序後，作為硬體程序剖析器的輸入，並 在其上運行；硬體程序剖析器，硬體程序剖析器在運行程序時統計內存數據依賴違規情況，並 將統計結果信息反饋給同步編譯模塊；同步編譯模塊，同步編譯模塊讀取統計結果信息，通過計算同步代價獲取進行多 線程同步操作的候選讀/寫指令對；然後通過數據流分析之後，在讀指令前添加一條stall 指令，並將讀指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令， 在寫指令所在線程的線程發起指令spawn後添加一條synset指令；彙編連結器，彙編程序經彙編連結後生成二進位的可執行文件；模擬器，可執行文件加載後在模擬器上運行；包括對同步機制下內存讀指令和內 存寫指令的擴展支持；同步機制下獲取內存數據的操作為當同步子線程執行到stall指令時，停止執
10行後續指令，等待一段時間；直至對應的同步父線程執行完相應的寫指令和forward指令， 收到同步父線程發送的含有內存地址和寫入數據的同步消息，再根據接收到的同步信息 和此前同步子線程對同一內存地址的寫入情況，對Sbuffer中的USe_flag進行置位或復 位，根據該標誌位決定是否使用同步父線程發送來的數據，而後停止等待，繼續執行後續指 令；同步機制下寫入和發送數據的操作為當同步父線程執行完相應的寫指令和 forward指令時，將含有寫指令對應的內存地址保存到發送地址緩衝區，將內存地址和寫入 數據以同步消息的形式發送給同步子線程；多線程程序以同步的方式推測執行，模擬器輸出程序運行的結果。所述的發送地址緩衝區是記錄所有已經由forward指令發送過的數據的地址的 數據緩衝區。參見圖3，該實施方式所示的由片上總線連接的多處理單元(多核)體系結構框 架，模擬器按照此結構框架實現，包括硬體程序剖析器對於內存數據依賴違規情況的統計， 以及為了支持子線程與父線程的同步操作，擴展的功能模塊發送地址緩衝區(FAB)和本 地寄存器文件Sbuffer ；另外，線程控制器，推測數據緩存和線程總控是為了支持多線程推 測擴展的模塊，與常規的推測多線程片上多核處理器等同或相當。由片上總線連接多個處 理單元，多線程在多個處理單元以同步的方式推測執行。圖3所示的實施方式，處理單元的硬體程序剖析器具體由一個核內程序剖析控制 器和剖析統計緩存構成。發送地址緩衝區是一個很小的數據緩衝區，用於記錄本線程中所有已經由 forward指令發送過的數據的地址。發送地址緩衝區的主要作用是記錄下發送的同步數 據的內存地址，同步寫線程在隨後的操作中，若執行到寫操作(store操作)，則需將本次寫 操作的地址與發送地址緩衝區中存儲的地址一一比較，看發送地址緩衝區中是否存儲了相 同的內存地址。如果查詢到相同的地址，則表明已發送給同步讀線程的數據仍不是最新的 數據。在這種情況下，同步寫線程會向同步讀線程發送消息，重啟同步讀線程。在寫完發送 地址緩衝區後，同步寫線程會以此將寫入的數據以及寫入數據的內存地址分別以消息的方 式發送給同步讀線程。經過硬體程序剖析器統計，一個線程需要同步的數據最多不超過8 個，因此發送地址緩衝區很小，不會在運行時給系統帶來過多的額外開銷。所述的Sbuffer是用於接收同步消息和控制同步操作的寄存器文件。該文件為處 理器核私有。參見圖4所示的Sbuffer設計示意圖，Sbuffer由五個域組成三個控制標誌 位 sync_f lag, ready_f lag 禾口 use_f lag，兩個消息域 message_addr 禾口 message_value ；線禾呈 處理單元在初始化時會將Sbuffer的所有標誌位復位。synC_flag位表示是否按同步方法執行，當該標誌位被置位，表示按照同步方法執 行；當該標誌位被復位，表示按常規的方法執行，此時stall指令被跳過，synload指令完成 的操作等同於常規的load指令，消息域中的數據無效；ready_flag位表示同步消息是否已經準備好，當該標誌位被置位表示同步消息已 經準備好；USe_flag位表示同步子線程是否使用消息中的數據，當該標誌位被置位表示同步 子線程將使用消息中的數據，當該標誌位被復位表示同步子線程將使用常規讀操作獲得內
11存數據；message_addr用來存儲消息的addr域；message_value 用來存儲消息的 value 域。下面給出候選讀/寫指令對在同步父線程與同步子線程進行同步執行的具體操 作的一種實現方式。其中，synset指令是新擴展的同步操作輔助指令，其作用是保證在進 行數據同步時同步父線程和同步子線程的同時存在。當一個線程執行spawn指令發起一個 新的線程後，會通過synset指令的執行，將其子線程Sbuffer的syn_flag位置位。只有當 一個線程的Sbuffer的syruflag位被位置後，該線程執行stall指令才會進入等待狀態。 否則，stall指令會被跳過，不進行任何操作。同步父線程發送同步消息的操作步驟為(1)在同步父線程發起同步子線程後，同步父線程執行synset指令，向同步子線 程發送消息，將同步子線程Sbuffer的syruflag位置位；(2)執行stored操作，常規的寫內存操作；(3)執行Save_addreSS(p)操作，將寫入數據的內存地址p保存到發送地址緩衝 區；(4)執行 receiver_id = get_immed_successor ，獲取同步子線程的處理器編 號；(5)執行mesg. value = *p操作，將寫內存操作寫入的數據寫入同步消息mesg的 value 域；(6)執行mesg. addr = p操作，將寫入數據的內存地址p寫入同步消息的addr域；(7)執行sendOnesg，receiver_id)操作，將構造好的同步消息發送給同步子線程。對於同步寫操作，當執行到store指令後，硬體執行常規的寫內存操作。在完成寫 內存操作後，同步寫線程需要將寫操作的內存地址存儲到FAB中。在執行store操作後，其 他的操作均由forward指令完成，forward指令的功能是將內存寫指令所寫的值和對應的 內存地址發送給子線程。同步父線程發送給同步父線程的同步消息，包括addr和value兩 個域，addr域中存放內存地址，value域中存放寫入數據。參見圖5，同步子線程接收同步消息的操作步驟為(1)執行stall 0操作，同步子線程查詢Sbuffer的ready_flag位是否被置位； 如果否，則同步子線程繼續處於阻塞狀態；如果是，則同步子線程結束阻塞狀態，進行後續 操作；(2)執行receive (mesg)操作，收到同步消息後，Sbuffer的ready_flag位被置 位；(3)執行message_addr = mesg. addr，獲取同步消息的內存地址，存放於Sbuffer StJ message_addr _ ；(4)執行message_value = mesg. value，獲取同步消息的內存數據值，存放於 Sbuffer 的 message_value _ ；(5)執行verify(q，meSSage_addr)操作，檢查收到同步消息的內存地址是否與寫 指令操作所要讀取的內存地址q是同一地址，如果是則將Sbuffer的uSe_flag標誌位置位；(6)執行loadecLvalue = load*q操作，進行常規的讀內存操作，將讀到的寫入數 據放入memory—value中；在進行讀操作的同時，檢查當前線程是否已經向內存地址q處寫 入數據，如果是，則將Sbuffer的uSe_flag標誌位復位；(7)執行 result = choose (loaded_value，message_value)操作，如果 Sbuffer 的 USe_flag標誌位被置位，則同步子線程採用同步消息中的內存數據值作為線程同步讀操作 最後讀取數據的結果；如果uSe_flag標誌位被復位，則使用loadecLvalue的值作為線程同 步讀操作最後讀取數據的結果；(8)執行 quit操作，將 Sbuffer 的 ready_flag 位復位，將 Sbuffer 的 use_flag 位復位。對於同步讀操作，首先，當同步讀線程執行stall指令後，會進入等待狀態 (Sbuffer的ready_flag位沒有被置位，同步子線程處於阻塞狀態)，等待同步父線程發送 消息。在收到消息後，同步子線程的Sbuffer的ready_flag位被置位，結束等待。獲取消息 後，同步子線程通過常規的load操作，讀取到一個內存數據值。在進行常規的讀操作時，處 理器將檢查在此之前處理器是否對同一地址進行過寫操作。如果是，則將Sbuffer的use_ flag標誌位復位，以避免使用舊數據替換新數據。然後進行verifyO操作，檢查將要執行 的讀操作要讀取數據的地址與發送來的數據中包含的內存地址是否相等。如果相等，則將 Sbuffer的uSe_flag位置位。然後，通過choose 操作，選取合適的值，作為同步讀操作的 最後結果。按照上述同步操作，具體從Olden基準程序選取了 7個測試程序mst，bh，tsp, em3d,bisort,vovonoi和health，按Prophet線程劃分方法，在4核的模擬器上推測執行的 測試，可獲得平均34%的加速比提高。而將數據依賴頻率的最小值設定為15%，線程體入口到讀指令的代碼距離與寫指 令到線程出口的代碼距離比最小值定位1，選取讀/寫內存指令同步執行，與非同步的推測 執行相比，加速比可獲得平均7 %的提升。可見本發明的同步方法對推測執行的加速比有較 明顯的提升。
權利要求
一種編譯器支持下的推測多線程內存數據同步執行方法，其特徵在於，多線程程序實現內存數據同步包括以下步驟1)程序由硬體線程劃分器劃分生成多線程彙編程序後，作為硬體程序剖析器的輸入，並在其上運行；2)硬體程序剖析器在運行程序時統計內存數據依賴違規情況，並將統計結果信息反饋給同步編譯模塊；3)同步編譯模塊讀取統計結果信息，通過計算同步代價獲取進行多線程同步操作的候選讀/寫指令對；然後通過數據流分析之後，在讀指令前添加一條stall指令，並將讀指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令；在寫指令所在線程的線程發起指令spawn後添加一條synset指令；最後經彙編連結生成可執行文件加載後在模擬器上運行；當同步子線程執行到stall指令時，停止執行後續指令，等待一段時間；直至對應的同步父線程執行完相應的寫指令和forward指令，收到同步父線程發送的含有內存地址和寫入數據的同步消息，再根據接收到的同步信息和此前同步子線程對同一內存地址的寫入情況，對Sbuffer中的use_flag進行置位或復位，根據該標誌位決定是否使用同步父線程發送來的數據，而後停止等待，繼續執行後續指令；同步子線程在接收同步消息後的操作由synload指令的執行完成，同步父線程在寫入數據後發送同步消息的操作由forward指令完成；4)多線程程序以同步的方式推測執行，模擬器輸出程序運行的結果。
2.如權利要求1所述的編譯器支持下的推測多線程內存數據同步執行方法，其特徵在 於，所述的統計內存數據依賴違規情況包括讀/寫指令被執行的次數及其PC值，讀/寫指 令發生讀後寫內存數據依賴違規的次數，發生讀後寫內存數據依賴違規的讀/寫指令執行 的間隔時間；統計結果信息被寫入到一個文件中，反饋給同步編譯模塊。
3.如權利要求1所述的編譯器支持下的推測多線程內存數據同步執行方法，其特徵在 於，所述的計算同步代價，是計算多線程的讀/寫指令對進行同步操作後帶來加速比提高 的潛力，獲取加速比提高潛力大的候選讀/寫指令對。
4.如權利要求3所述的編譯器支持下的推測多線程內存數據同步執行方法，其特徵在 於，所述的加速比提高潛力通過內存讀/寫指令對發生數據依賴的頻率，線程體入口到讀 指令的代碼距離以及讀指令到寫指令之間的代碼距離來判定。
5.如權利要求1所述的編譯器支持下的推測多線程內存數據同步執行方法，其特徵在 於，所述的數據流分析是在程序的控制流圖上進行，以找到stall指令和forward指令的插 入位置；其中，stall指令插入到需要同步的讀指令前，forward指令插入到需要同步的寫 指令和和線程出口之間的每一條路徑上。
6.如權利要求1所述的編譯器支持下的推測多線程內存數據同步執行方法，其特徵在 於，所述的同步父線程發送同步消息的操作步驟為(1)在同步父線程發起同步子線程後，同步父線程執行synset指令，向同步子線程發 送消息，將同步子線程Sbuffer的Syn_flag位置位；(2)執行store*p操作，常規的寫內存操作；(3)執行Save_addreSS(p)操作，將寫入數據的內存地址p保存到發送地址緩衝區；(4)執行receiver_id= get_immed_successor ，獲取同步子線程的處理器編號；(5)執行mesg.value = *p操作，將寫內存操作寫入的數據寫入同步消息mesg的value域；(6)執行mesg.addr = p操作，將寫入數據的內存地址p寫入同步消息的addr域；(7)執行send(mesg，receiver_id)操作，將構造好的同步消息發送給同步子線程。
7.如權利要求1所述的編譯器支持下的推測多線程內存數據同步執行方法，其特徵在 於，所述的同步子線程接收同步消息的操作步驟為(1)執行stall操作，同步子線程查詢Sbuffer的ready_flag位是否被置位；如 果否，則同步子線程繼續處於阻塞狀態；如果是，則同步子線程結束阻塞狀態，進行後續操 作；(2)執行receive(mesg)操作，收到同步消息後，Sbuffer的ready_flag位被置位；(3)執行message_addr= mesg. addr,獲取同步消息的內存地址，存放於Sbuffer的 message_addr _ ；(4)執行message_value= mesg. value，獲取同步消息的內存數據值，存放於Sbuffer 的 message_value 域；(5)執行verify(q，meSSage_addr)操作，檢查收到同步消息的內存地址是否與寫指令 操作所要讀取的內存地址q是同一地址，如果是則將Sbuffer的uSe_flag標誌位置位；(6)執行loadecLvalue= load*q操作，進行常規的讀內存操作，將讀到的寫入數據放 入memory—value中；在進行讀操作的同時，檢查當前線程是否已經向內存地址q處寫入數 據，如果是，則將Sbuffer的uSe_flag標誌位復位；(7)執行result = choose (loaded_value,message_value)操作，如果 Sbuffer 的 use_ flag標誌位被置位，則同步子線程採用同步消息中的內存數據值作為線程同步讀操作最後 讀取數據的結果；如果uSe_flag標誌位被復位，則使用loadecLvalue的值作為線程同步讀 操作最後讀取數據的結果；(8)執行quit 操作，將 Sbuffer 的 ready_f lag 位復位，將 Sbuffer 的 use_f lag 位復位。
8.一種完成編譯器支持下的推測多線程內存數據同步執行方法的裝置，其特徵在於， 包括以下模塊線程劃分器，將程序劃分生成多線程彙編程序後，作為硬體程序剖析器的輸入，並在其 上運行；硬體程序剖析器，硬體程序剖析器在運行程序時統計內存數據依賴違規情況，並將統 計結果信息反饋給同步編譯模塊；同步編譯模塊，同步編譯模塊讀取統計結果信息，通過計算同步代價獲取進行多線程 同步操作的候選讀/寫指令對；然後通過數據流分析之後，在讀指令前添加一條stall指 令，並將讀指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令，在 寫指令所在線程的線程發起指令spawn後添加一條synset指令； 彙編連結器，彙編程序經彙編連結後生成二進位的可執行文件； 模擬器，可執行文件加載後在模擬器上運行；包括對同步機制下內存讀指令和內存寫 指令的擴展支持；同步機制下獲取內存數據的操作為當同步子線程執行到stall指令時，停止執行後 續指令，等待一段時間；直至對應的同步父線程執行完相應的寫指令和forward指令，收到 同步父線程發送的含有內存地址和寫入數據的同步消息，再根據接收到的同步信息和此前 同步子線程對同一內存地址的寫入情況，對Sbuffer中的USe_flag進行置位或復位，根據 該標誌位決定是否使用同步父線程發送來的數據，而後停止等待，繼續執行後續指令；同步機制下寫入和發送數據的操作為當同步父線程執行完相應的寫指令和forward 指令時，將含有寫指令對應的內存地址保存到發送地址緩衝區，將內存地址和寫入數據以 同步消息的形式發送給同步子線程；多線程程序以同步的方式推測執行，模擬器輸出程序運行的結果。
9.如權利要求8所述的完成編譯器支持下的推測多線程內存數據同步執行方法的裝 置，其特徵在於，所述的發送地址緩衝區是記錄所有已經由forward指令發送過的數據的 地址的數據緩衝區。
10.如權利要求8所述的完成編譯器支持下的推測多線程內存數據同步執行方法的 裝置，其特徵在於，所述的Sbuffer是用於接收同步消息和控制同步操作的寄存器文件； Sbuffer由五個域組成三個控制標誌位sync_flag，ready_flag和use_flag，兩個消息域 message_addr和message_value ；線程處理單元在初始化時會將Sbuffer的所有標誌位復 位；synC_flag位表示是否按同步方法執行，當該標誌位被置位，表示按照同步方法執行； 當該標誌位被復位，表示按常規的方法執行，此時stall指令被跳過，synload指令完成的 操作等同於常規的load指令，消息域中的數據無效；ready_flag位表示同步消息是否已經準備好，當該標誌位被置位表示同步消息已經準 備好；USe_flag位表示同步子線程是否使用消息中的數據，當該標誌位被置位表示同步子線 程將使用消息中的數據，當該標誌位被復位表示同步子線程將使用常規讀操作獲得內存數 據；message_addr用來存儲同步消息的addr域； message_value用來存儲同步消息的value域。
全文摘要
本發明公開了一種編譯器支持下的推測多線程內存數據同步執行方法及其裝置，能在程序運行時對選定的讀寫內存指令進行同步，降低讀後寫數據依賴違規發生的次數，提高多線程同步操作的整體加速比。在獲取候選讀/寫指令對之後，在讀指令前添加一條stall指令，並將讀指令替換為同步讀指令synload，在寫指令後添加一條或多條forward指令，在寫指令所在線程的線程發起指令spawn後添加一條synset指令；最後經彙編連結生成可執行文件加載後在模擬器上運行；多線程程序以同步的方式推測執行，得到運行結果，並獲得較高的加速比。
文檔編號G06F9/38GK101833440SQ20101016053
公開日2010年9月15日 申請日期2010年4月30日 優先權日2010年4月30日
發明者宋少龍, 王旭昊, 趙銀亮, 韋遠科 申請人:西安交通大學