《多核平台下串列程式運行時的自動並行化加速方法》是上海交通大學於2010年8月27日申請的專利，該專利的公布號為CN101916185A，授權公布日為2010年12月15日，發明人是過敏意、楊藍麒、李陽、陳鵬宇、楊曉鵬、王穩寅、沈耀。
一種計算機技術領域的多核平台下串列程式運行時的自動並行化加速方法，新增可共享讀取的程式計數器暫存器組，並在作業系統中建立自動並行加速執行緒，選擇一個執行緒作為加速的對象，然後實時地分析此執行緒將要執行到的指令代碼，並對其中執行循環的指令代碼進行修改，達到使被加速執行緒自動並行執行的目的。該發明在運行時對程式進行自動並行，不用對程式進行預先的處理，整個過程由作業系統完成，對於用戶完全透明。該發明能夠在有空閒的CPU核時自動利用空閒資源對程式進行並行加速，免去等待預先處理程式的時間，也省去用戶手動轉換程式的麻煩。
2020年7月14日，《多核平台下串列程式運行時的自動並行化加速方法》獲得第二十一屆中國專利獎優秀獎。
基本介紹
- 中文名：多核平台下串列程式運行時的自動並行化加速方法
- 申請人：上海交通大學
- 申請日：2010年8月27日
- 申請號：2010102640748
- 公布號：CN101916185A
- 公布日：2010年12月15日
- 發明人：過敏意、楊藍麒、李陽、陳鵬宇、楊曉鵬、王穩寅、沈耀
- 地址：上海市閔行區東川路800號
- Int. Cl.：G06F9/38(2006.01)I
- 代理機構：上海交達專利事務所
- 代理人：王錫麟、王桂忠
- 類別：發明專利
專利背景,發明內容,專利目的,技術方案,改善效果,技術領域,權利要求,實施方式,榮譽表彰,
專利背景
二十一世紀以來，隨著晶片功耗的不斷提升和晶片複雜度的不斷提升，通過提升頻率等方法來提高單核處理器的性能變得非常困難。單晶片多處理器（Chip Multiprocessor，即CMP）技術成為了新的發展熱點。截至2010年8月，使用CMP技術的處理器已經占據了大部分市場，從大型商用機型，到普通桌面機，再到嵌入式系統，無論高端低端，CMP都成為了各領域處理器結構的必然選擇。
然而CMP的使用並不是套用驅動的，它的出現主要是為了有效地利用新製造工藝帶來的更多的電晶體。由於功耗和驗證難度的限制，已經難以通過設計更複雜的單核來提升處理器的性能。與此同時傳統的圖靈機串列程式模型和串列地址空間結構並沒有發生本質改變，原有的大量程式和許多新增的程式依然遵循傳統的設計方法，導致串列化的程式並不能很好的利用2010年可並行執行的物理結構以提高性能。
2010年之前技術中採用傳統的並行程式設計方法重寫已有的程式，該方法好像非常簡單，但是事實上並不可行。常用的並行化庫和編譯指令主要有OpenMP（共享存儲並行設計的庫）和MPI（訊息傳遞並行編程環境）。它們一方面難於掌握：並行程式的設計與調試都比串列程式要困難很多；另一方面也不是特別適用於多核環境。由於編寫單個並行程式代價就很高，要想把已有的各種應用程式都重寫，實際上是不可能的。
經對2010年之前文獻檢索發現，中國專利申請號為：200510026587.4，名稱為：用戶指導的程式半自動並行化方法，該技術提出了一種使用較為簡單的模型開發並行化程式，能減小開發並行程式的複雜度。但是，其使用範圍有限而且仍然需要大量精力進行重新開發，不能很好地解決大量已有的串列程式的問題。
另外一種方法是對串列程式進行自動分析翻譯，生成並行化程式，即執行緒級推測（ThreadLevel Speculation，即TLS）技術。使用該技術可以使用相應的自動並行化工具，通過對原有串列程式的原始碼、中間代碼或者二進制代碼的分析，自動劃分執行緒，並生成並行化代碼。該方法雖然可以不用重寫程式，但還是需要對原有的代碼進行重新編譯，這就要求用戶有能力進行代碼重新編譯或者要求用戶更換為已經重新編譯的程式，這一要求在一般情況下是不成立的。同時，使用推測技術，雖然在一定程度上提高了並行度，但同時也增加了硬體設計的複雜度，並且在推測級數較多時推測成功率很低。
發明內容
專利目的
《多核平台下串列程式運行時的自動並行化加速方法》的目的在於提供一種多核平台下串列程式運行時的自動並行化加速方法。該發明新增可共享讀取的程式計數器暫存器組，並在作業系統中建立自動並行加速執行緒，選擇一個執行緒作為加速的對象，然後實時地分析此執行緒將要執行到的指令代碼，並對其中執行循環的指令代碼進行修改，達到使被加速執行緒自動並行執行的目的。
技術方案
《多核平台下串列程式運行時的自動並行化加速方法》包括以下步驟：
第一步，建立一個共享讀取的程式計數暫存器組SPC，該暫存器組中暫存器的個數與CPU核的數目相同，每個暫存器分別與對應的CPU核相連以實時地儲存該CPU核的程式計數器值。
所述的共享讀取是：每個CPU核實時讀取暫存器組中每個暫存器存儲的其它CPU核的程式計數器值。
第二步，當存在空閒的CPU核時，進行加速對象選擇處理，得到自動並行加速執行緒的加速對象為執行緒P。
所述的加速對象選擇處理，是：當正在運行且未被加速的用戶執行緒中存在CPU占用率最高的執行緒時，則選擇該執行緒作為自動並行加速執行緒的加速對象；否則，時間t後，再次選擇正在運行且未被加速的用戶執行緒中CPU占用率最高的執行緒作為自動並行加速執行緒的加速對象，直至得到自動並行加速執行緒的加速對象。
第三步，當執行緒P存在已分析指令集合Sp時，載入該集合Sp；否則，為執行緒P新建一個集合Sp，對執行緒P所在的CPU核進行讀取處理，得到執行緒P所在的CPU核當前正在讀取的指令Ic，並由Ic追蹤執行緒P下一條將要執行指令的地址，將追蹤分析的指令代碼和跳轉關係加入集合Sp中。
所述的讀取處理，是：讀取執行緒P所在的CPU核的程式計數暫存器的值，將得到的虛擬地址轉換為物理地址，然後從該物理地址得到執行緒P所在的CPU核正在執行的指令Ic，當集合Sp中包括指令Ic時，刪除集合Sp中Ic以前的指令記錄，並根據集合Sp追蹤執行緒P下一條將要執行的指令；否則，清空集合Sp。
第四步，採用第三步的方法，得到執行緒P將要執行的所有指令，當集合Sp中每次加入條件轉移指令後且集合Sp中存在循環代碼時，進行進度校驗和替換處理。
所述的進度校驗，是：重新讀取指令Ic，當指令Ic不在集合Sp中時，清空集合Sp，然後從指令Ic開始追蹤；當指令Ic在集合Sp中、執行緒P走向該循環且執行緒P已經開始執行該循環，則選取循環接收後第一條語句作為待分析指令，並清空集合Sp；當指令Ic在集合Sp中、執行緒P走向該循環且執行緒P未執行該循環，則對該循環進行替換處理；當指令Ic在集合Sp中但執行緒P未走向該循環時，則刪除集合Sp中Ic以前的指令記錄，並繼續追蹤。
所述的替換處理，包括以下步驟：
1）當循環的總工作量大於閾值G時，生成並行化執行該循環的代碼，執行該循環的代碼出口語句跳轉到原循環出口對應的語句，且將新生成的代碼單獨放在一個或若干個記憶體頁中；否則，放棄替換該循環，並刪除集合Sp中Ic以前的指令記錄，繼續追蹤；
2）生成代碼後，進行進度校驗，當通過進度校驗時則中斷執行緒P，且中斷執行緒P後再次進行校驗，再次通過進度校驗後，執行3）；否則，執行緒P繼續運行；
3）將1）生成的代碼所在的記憶體頁分配給執行緒P，並修改原循環起始地址的二進制代碼為跳轉到新生成代碼的起始位置，在集合Sp中刪除原循環對應指令，加入新生成的代碼指令；
4）替換完成後通知執行緒P繼續執行，繼續分析後續代碼。
所述的通過進度校驗是指：指令Ic在集合Sp中、執行緒P走向該循環且執行緒P未執行該循環。
第五步，當執行緒P被調度出CPU核時，系統以中斷方式將該事件連同當時的SPCp值傳送給自動並行加速執行緒，當自動並行加速執行緒正在替換處理中時，則使用此時的SPCp值作為讀取Ic的依據，繼續執行替換處理直到退出該步驟；否則，自動並行加速執行緒根據當時的SPCp值讀取Ic，清空或更新集合Sp，其結果等待執行緒P被調入時繼續使用。
第六步，返回第二步，開始處理新的需要加速的執行緒。
改善效果
與2010年之前的技術相比，《多核平台下串列程式運行時的自動並行化加速方法》的有益效果是：2010年之前的技術使用不方便，需要重新開發程式或者重新編譯原來的代碼，而該發明在運行時對程式進行自動並行，不用對已有程式進行預先的處理，整個過程由作業系統完成，對於用戶完全透明。該發明能夠在有空閒的CPU核時自動利用空閒資源對程式進行並行加速，免去等待預先處理程式的時間，也省去用戶手動轉換程式的麻煩。
技術領域
《多核平台下串列程式運行時的自動並行化加速方法》涉及的是一種計算機技術領域的方法，具體是一種多核平台下串列程式運行時的自動並行化加速方法。
權利要求
1.一種多核平台下串列程式運行時的自動並行化加速方法，其特徵在於，包括以下步驟：
第一步，建立一個共享讀取的程式計數暫存器組SPC，該暫存器組中暫存器的個數與CPU核的數目相同，每個暫存器分別與對應的CPU核相連以實時地儲存該CPU核的程式計數器值；
第二步，當存在空閒的CPU核時，進行加速對象選擇處理，得到自動並行加速執行緒的加速對象為執行緒P；
第三步，當執行緒P存在已分析指令集合Sp時，載入該集合Sp；否則，為執行緒P新建一個集合Sp，對執行緒P所在的CPU核進行讀取處理，得到執行緒P所在的CPU核當前正在讀取的指令Ic，並由Ic追蹤執行緒P下一條將要執行指令的地址，將追蹤分析的指令代碼和跳轉關係加入集合Sp中；
第四步，採用第三步的方法，得到執行緒P將要執行的所有指令，當集合Sp中每次加入條件轉移指令後且集合Sp中存在循環代碼時，進行進度校驗和替換處理；
第五步，當執行緒P被調度出CPU核時，系統以中斷方式將該事件連同當時的SPCp值傳送給自動並行加速執行緒，當自動並行加速執行緒正在替換處理中時，則使用此時的SPCp值作為讀取Ic的依據，繼續執行替換處理直到退出該步驟；否則，自動並行加速執行緒根據當時的SPCp值讀取Ic，清空或更新集合Sp，其結果等待執行緒P被調入時繼續使用；
第六步，返回第二步，開始處理新的需要加速的執行緒。
2.根據權利要求1所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，第一步中所述的共享讀取是：每個CPU核實時讀取暫存器組中每個暫存器存儲的其它CPU核的程式計數器值。
3.根據權利要求1所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，第二步中所述的加速對象選擇處理，是：當正在運行且未被加速的用戶執行緒中存在CPU占用率最高的執行緒時，則選擇該執行緒作為自動並行加速執行緒的加速對象；否則，時間t後，再次選擇正在運行且未被加速的用戶執行緒中CPU占用率最高的執行緒作為自動並行加速執行緒的加速對象，直至得到自動並行加速執行緒的加速對象。
4.根據權利要求3所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，所述的時間t是系統的調度時間片大小。
5.根據權利要求1所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，第三步中所述的讀取處理，是：讀取執行緒P所在的CPU核的程式計數暫存器的值，將得到的虛擬地址轉換為物理地址，然後從該物理地址得到執行緒P所在的CPU核正在執行的指令Ic，當集合Sp中包括指令Ic時，刪除集合Sp中Ic以前的指令記錄，並根據集合Sp追蹤執行緒P下一條將要執行的指令；否則，清空集合Sp。
6.根據權利要求1所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，第四步中所述的進度校驗，是：重新讀取指令Ic，當指令Ic不在集合Sp中時，清空集合Sp，然後從指令Ic開始追蹤；當指令Ic在集合Sp中、執行緒P走向該循環且執行緒P已經開始執行該循環，則選取循環接收後第一條語句作為待分析指令，並清空集合Sp；當指令Ic在集合Sp中、執行緒P走向該循環且執行緒P未執行該循環，則對該循環進行替換處理；當指令Ic在集合Sp中但執行緒P未走向該循環時，則刪除集合Sp中Ic以前的指令記錄，並繼續追蹤。
7.根據權利要求6所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，所述的替換處理，包括以下步驟：
1）當循環的總工作量大於閾值G時，生成並行化執行該循環的代碼，執行該循環的代碼出口語句跳轉到原循環出口對應的語句，且將新生成的代碼單獨放在一個或若干個記憶體頁中；否則，放棄替換該循環，並刪除集合Sp中Ic以前的指令記錄，繼續追蹤；
2）生成代碼後，進行進度校驗，當通過進度校驗時則中斷執行緒P，且中斷執行緒P後再次進行校驗，再次通過進度校驗後，執行3）；否則，執行緒P繼續運行；
3）將1）生成的代碼所在的記憶體頁分配給執行緒P，並修改原循環起始地址的二進制代碼為跳轉到新生成代碼的起始位置，在集合Sp中刪除原循環對應指令，加入新生成的代碼指令；
4）替換完成後通知執行緒P繼續執行，繼續分析後續代碼。
8.根據權利要求7所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，所述的閾值G是單個CPU核1秒鐘執行的最大指令數。
9.根據權利要求7所述的多核平台下串列程式運行時的自動並行化加速方法，其特徵是，所述的通過進度校驗是指：指令Ic在集合Sp中、執行緒P走向該循環且執行緒P未執行該循環。
實施方式
實施例
該實施例包括以下步驟：
第一步，建立一個共享讀取的程式計數暫存器組SPC，該暫存器組中暫存器的個數與CPU核的數目相同，每個暫存器分別與對應的CPU核相連以實時地儲存該CPU核的程式計數器值。
所述的共享讀取是：每個CPU核實時讀取暫存器組中每個暫存器存儲的其它CPU核的程式計數器值。
第二步，當存在空閒的CPU核時，進行加速對象選擇處理，得到自動並行加速執行緒的加速對象為執行緒P。
所述的加速對象選擇處理，是：當正在運行且未被加速的用戶執行緒中存在CPU占用率最高的執行緒時，則選擇該執行緒作為自動並行加速執行緒的加速對象；否則，時間t後，再次選擇正在運行且未被加速的用戶執行緒中CPU占用率最高的執行緒作為自動並行加速執行緒的加速對象，直至得到自動並行加速執行緒的加速對象。
所述的時間t是系統的調度時間片大小，該實施例為20毫秒。
第三步，當執行緒P存在已分析指令集合Sp時，載入該集合Sp；否則，為執行緒P新建一個集合Sp，對執行緒P所在的CPU核進行讀取處理，得到執行緒P所在的CPU核當前正在讀取的指令Ic，並由Ic追蹤執行緒P下一條將要執行指令的地址，將追蹤分析的指令代碼和跳轉關係加入集合Sp中。
所述的讀取處理，是：讀取執行緒P所在的CPU核的程式計數暫存器的值，將得到的虛擬地址轉換為物理地址，然後從該物理地址得到執行緒P所在的CPU核正在執行的指令Ic，當集合Sp中包括指令Ic時，刪除集合Sp中Ic以前的指令記錄，並根據集合Sp追蹤執行緒P下一條將要執行的指令；否則，清空集合Sp。
第四步，採用第三步的方法，得到執行緒P將要執行的所有指令，當集合Sp中每次加入條件轉移指令後且集合Sp中存在循環代碼時，進行進度校驗和替換處理。
所述的進度校驗，是：重新讀取指令Ic，當指令Ic不在集合Sp中時，清空集合Sp，然後從指令Ic開始追蹤；當指令Ic在集合Sp中、執行緒P走向該循環且執行緒P已經開始執行該循環，則選取循環接收後第一條語句作為待分析指令，並清空集合Sp；當指令Ic在集合Sp中、執行緒P走向該循環且執行緒P未執行該循環，則對該循環進行替換處理；當指令Ic在集合Sp中但執行緒P未走向該循環時，則刪除集合Sp中Ic以前的指令記錄，並繼續追蹤。
所述的替換處理，包括以下步驟：
1）當循環的總工作量大於閾值G時，生成並行化執行該循環的代碼，執行該循環的代碼出口語句跳轉到原循環出口對應的語句，且將新生成的代碼單獨放在一個或若干個記憶體頁中；否則，放棄替換該循環，並刪除集合Sp中Ic以前的指令記錄，繼續追蹤；
2）生成代碼後，進行進度校驗，當通過進度校驗時則中斷執行緒P，且中斷執行緒P後再次進行校驗，再次通過進度校驗後，執行3）；否則，執行緒P繼續運行；
3）將1）生成的代碼所在的記憶體頁分配給執行緒P，並修改原循環起始地址的二進制代碼為跳轉到新生成代碼的起始位置，在集合Sp中刪除原循環對應指令，加入新生成的代碼指令；
4）替換完成後通知執行緒P繼續執行，繼續分析後續代碼。
所述的閾值G是單個CPU核1秒鐘執行的最大指令數。
所述的通過進度校驗是指：指令Ic在集合Sp中、執行緒P走向該循環且執行緒P未執行該循環。
第五步，當執行緒P被調度出CPU核時，系統以中斷方式將該事件連同當時的SPCp值傳送給自動並行加速執行緒，當自動並行加速執行緒正在替換處理中時，則使用此時的SPCp值作為讀取Ic的依據，繼續執行替換處理直到退出該步驟；否則，自動並行加速執行緒根據當時的SPCp值讀取Ic，清空或更新集合Sp，其結果等待執行緒P被調入時繼續使用。
第六步，返回第二步，開始處理新的需要加速的執行緒。
該實施例方法實現簡單，且完全由作業系統完成；能夠在有空閒的CPU核時自動利用空閒資源對程式進行並行加速，免去等待預先處理程式的時間，從而大大提高了多核平台下串列程式運行時的並行處理速度。
榮譽表彰
2020年7月14日，《多核平台下串列程式運行時的自動並行化加速方法》獲得第二十一屆中國專利獎優秀獎。
