[發明專利]一種可控重復執行次數的多線程事務存儲編程模型方法

有效

• 申請號: 201711308530.2
• 申請日: 2017-12-11
• 公開（公告）號: CN109901913B
• 公開（公告）日: 2023-08-22
• 發明（設計）人: 曾璇;周海;嚴昌浩;陸昆
• 申請（專利權）人: 復旦大學
• 主分類號: G06F9/46
• 分類號: G06F9/46;G06F9/48;G06F9/52
• 代理公司: 上海元一成知識產權代理事務所(普通合伙) 31268
• 代理人: 吳桂琴

本發明屬于計算機多線程并行編程領域，涉及一種執行失敗后，可控重復執行次數(N?retry)的多線程事務存儲編程模型方法。本發明將原事務存儲編程模型進行修改，對執行失敗的事務控制重復執行次數，并通過構建任務隊列，若事務執行失敗，則將該事務執行的任務返回至任務隊列尾部的方式，確保并行模型的正確性，并避開多線程程序中的熱點資源，減少事務總執行失敗次數，提高程序并發效率。本方法易用性高，能在高沖突并行算法中顯著提高并行效率。

技術領域

本發明屬于計算機并行編程領域，涉及一種執行失敗后可控重復執行次數的多線程事務存儲(Transaction?Memory)編程模型方法。

背景技術

現有技術公開了摩爾定律在芯片的尺寸，頻率，功耗等方面均被驗證，但隨著IC芯片的晶體管尺寸已達7納米，晶體管尺寸很難再依照摩爾定律不斷縮小，單核CPU的頻率由于功耗的限制也難以大幅提升，因此單核CPU的計算能力提升較為困難；業內認為，并行多核處理器將成為處理器的計算能力沿摩爾定律增長的關鍵技術之一。

多線程編程是在多核處理器平臺上實現并行計算的常用編程技術。然而將現有程序從單線程移植到多線程，同時又具備較高的并行效率卻是一件極具挑戰性的工作，其難點主要體現在易用的并行編程模型和高的并行效率方面。

業內認為，多核并行編程模型需要解決的核心問題是多線程共享內存的沖突。常見的共享內存沖突有兩種，一種是寫后讀沖突，即當兩個線程同時讀寫同一塊內存，其中一個線程在讀取并使用共享內存的過程中，該內存值被另一線程覆寫改變；另一種是寫后寫沖突，兩個線程同時對一塊共享內存進行寫操作；實踐顯示，在多線程編程中這些沖突需要仔細處理，否則多線程程序將得到錯誤結果。

通常解決上述共享內存沖突主要有三種方法：鎖機制、無鎖編程和事務存儲；鎖機制是在信號量[1]的基礎上發展而來的，通過定義互斥的信號量來控制線程的開啟和阻塞以避免兩個(或多個)線程同時使用同一塊內存，它是最常見的解決數據沖突的方法，然而在使用該方法時，存在如下缺陷：如果使用粗粒度鎖，編程相對簡單，但是可能會大幅降低程序的并行效率，若使用細粒度鎖，可增加程序的并行效率，但編程復雜、代碼工作量大、可能會產生死鎖等問題；無鎖式編程[2]是基于CPU的比較交換操作(compare-and-swap)實現事務的原子執行，適用于復雜度不高且比較小的并行程序；

事務存儲[3]源于數據庫的事務特性，事務可讓一段臨界區代碼能夠原子化、并行、獨立地在多線程中執行，其編程模型簡單易用，且具有較高的并行效率；目前，事務存儲的實現方式主要分為三大類：軟件事務存儲[4][5][6][7][8]、硬件事務存儲[9][10][11][12]和混合事務存儲[13][14]，其中Sun公司的Dave?Dice、Ori?Shalev和Nir?Shavit提出并實現的TL2模型是最具有代表性的軟件事務存儲模型，而新型Intel處理器中的TSX(Transactional?Synchronization?Extensions)指令集，是當前工業界在硬件事務存儲方面的典型代表，Intel與密歇根大學聯合開發的ISA指令集則為混合事務存儲的經典模型。

現有技術公開了(如圖1所示)一個簡單的基于TL2軟件事務存儲的并行編程應用示例，它在多線程環境中執行y＝x+10的功能，其中假設x為共享讀變量，y為共享寫變量，變量x和y均可能與其它線程發生共享數據沖突；在圖1中，編寫應用層面的并行程序僅需簡單地使用TM_BEGIN()和TM_END()來包含可能發生共享沖突的語句，構成一個完整事務，并通過調用TM_READ()和TM_WRITE()來指明可能共享沖突的讀變量和寫變量，從這個應用層的示例可以看出，基于事務存儲模型的并行編程無顯式的使用鎖機制、不會發生死鎖問題，可大幅降低編寫并行程序的難度，且從應用層看，一個事務在多線程環境中的執行只會成功，而沒有失敗后的執行路徑，簡化了編程模型；