一種用於消除存儲訪問擁塞的同構計算任務分組方法
2023-05-01 03:31:26 1
一種用於消除存儲訪問擁塞的同構計算任務分組方法
【專利摘要】一種用於消除存儲訪問擁塞的同構計算任務分組方法，該方法依據同構計算任務執行的並行收益進行分組，通過重疊不同分組的計算區域和訪存區域，減輕或消除應用在眾核處理器系統運行時的存儲訪問擁塞。本發明不需要在算法層面對是否發生存儲訪問擁塞進行分析，為具有同構計算任務特徵應用的訪存性能分析和優化提供了統一有效的方法。
【專利說明】一種用於消除存儲訪問擁塞的同構計算任務分組方法
【技術領域】
[0001]本發明屬於計算機系統結構領域，涉及一種計算任務分組方法，尤其涉及一種用於消除存儲訪問擁塞的同構計算任務分組方法。
【背景技術】
[0002]高性能計算發展水平是衡量一個國家綜合國力與國際競爭力的重要指標，是一個國家科技實力的綜合體現，在航空航天、核武研製、石油勘探、氣象預報、生命科學、海嘯與地震自然災害預測等關鍵領域有著巨大應用需求。因此，世界各國都競相將高性能計算作為技術與經濟爭奪的戰略制高點。目前，眾核處理器為解決高性能計算提供了契機，它採用大量處理器核加速應用執行。然而，由於受成本和硬體技術的制約，眾核處理器的存儲部件不能有效的滿足眾核系統大量處理器核的訪存需求，使得眾核處理器系統的存儲訪問成為其性能提升的瓶頸。儘管眾核系統使用GDDR5存儲、高速片上總線、以及多存儲訪問通道等硬體技術提升性能，存儲訪問瓶頸並沒有得到根本性的改善。
[0003]眾核處理器晶片集成數量巨大的處理器核，通過眾多處理器核並行運行加速應用程式的執行。然而，當運行於不同處理器核上的計算任務是同構計算任務時，由於所有計算任務幾乎是在同一時間段內請求存儲訪問，大量的存儲訪問超出了眾核處理器存儲部件的正常處理能力，導致存儲訪問擁塞，降低了應用程式的整體執行性能。
[0004]目前消除眾核處理器存儲訪問擁塞的最簡單的方法是僅在眾核處理器運行計算密集型任務，比如矩陣相乘，以減輕眾核處理器存儲部件的壓力。該方法忽略了其他類型應用利用眾核處理器加速執行的需求，比如訪存密集型應用、介於訪存密集型和計算密集型之間的應用。折中方法是將訪存密集型應用和計算密集型應用按一定比例混合後加載到眾核處理器運行。由於計算密集型應用佔用訪存資源有限，訪存密集型應用可以使用大部分訪存資源加速其執行。這些方法從資源有效利用層面解決眾核系統的訪存牆問題，存在以下不足:
[0005](I)沒有考慮具有同構計算任務特徵的應用，比如MapReduce應用。具有同構計算任務特徵的MapReduce應用是大數據時代的主流應用，該類應用包含大量的同構計算任務，而這些計算任務在大部分情況下屬於訪存密集任務，其並行執行時，存儲訪問擁塞不可避免。
[0006](2)該類方法僅考慮了如何有效利用訪存資源，沒有考慮在存儲訪問擁塞不可避免的情況下，如何通過對同構計算任務進行合理分組，減輕或避免存儲訪問擁塞對計算任務執行的影響。
[0007]由於這些問題的存在，針對目前主流應用，這類方法不能有效解決眾核處理器系統的存儲訪問擁塞問題。
【發明內容】
[0008]本發明的目的在於提供一種用於消除存儲訪問擁塞的同構計算任務分組方法，該分組方法解決了具有同構計算任務特徵的應用在眾核系統上運行時的存儲訪問擁塞問題。
[0009]為了達到上述目的，本發明採用的技術方案包括如下步驟:
[0010]I)設置並行執行的同構計算任務數nl =處理器核最多能夠支持的硬體線程數；設置預期並行收益pb_exp = I ;
[0011]2)設置n2 = 2Xnl ;然後分別以nl個同構計算任務和n2個同構計算任務並行執行應用，記錄並行執行的同構計算任務數為nl時的運行時間為Tl，並行執行的同構計算任務數為n2時的運行時間為T2 ；
[0012]3)利用並行執行的同構計算任務數為nl時的運行時間Tl以及並行執行的同構計算任務數為n2時的運行時間T2得到實際並行收益為pb_real，且pb_real = T1/T2，若pb_real>2,則將n2的值賦值給nl，返回步驟2);否則轉入步驟4)；
[0013]4)若pb_real≥pb_exp- Δ，則將n2的值賦值給η I,將pb_real的值賦值給pb_exp，返回步驟2);否則，將nl作為一個分組中最多能夠包括的同構計算任務數，其中，Δ =表示可容忍的實際並行收益低於預期並行收益的最大幅度；
[0014]5)利用一個分組中最多能夠包括的同構計算任務數對所有等待執行的同構計算任務進行分組，每間隔Ts時間，順序的將一個分組內的同構計算任務映射到對應的處理器核上開始執行任務；其中，Ts是所有同構計算任務訪存區域的平均執行時間。
[0015]所述的步驟4)中，對於Intel Phi?眾核處理器以及Phoenix++運行時系統，Ts為Oms≤Ts≤IOOms ;對於由計算密集型同構計算任務組成的分組,Ts = IOOms ;對於由其它類型的同構計算任務組成的分組，Ts〈100ms。
[0016]所述的步驟4)中，Δ =O-10
[0017]與現有技術相比，本發明的有益效果在於:
[0018]本發明通過迭代的方式合理確定在不發生存儲訪問擁塞的情況下最多可以同時啟動的同構計算任務的數目，並以此為依據對同構計算任務進行分組。同時通過預期並行收益pb_eXp和實際並行收益pb_real的對比用於判斷一個分組中的同構計算任務數nl是否合理；當pb_exp_ Δ >pb_real時,說明分組中的同構計算任務數繼續增加,不僅不會帶來預期的或好於預期的並行收益，而且還會導致存儲訪問擁塞，所以將nl作為一個分組在不發生存儲訪問擁塞的情況下最多可以包括的同構計算任務數。
[0019]另外，該方法基於不同分組計算任務之間的計算和訪存可以異步執行的特徵，採用流水線的方式重疊不同分組的存儲訪問和計算，減少了大量同構計算任務同時請求存儲訪問的機會。該分組方法使得眾核處理器的存儲訪問部件最大可能的工作在非擁塞狀態，避免了同構計算任務並行執行導致的存儲訪問擁塞。
【專利附圖】
【附圖說明】
[0020]圖1為本發明的流程圖；
[0021]圖2為Word Count的pb_real變化趨勢圖
[0022]圖3為使用分組和未使用分組的對比圖。
【具體實施方式】
[0023]以下結合附圖對本發明作進一步的詳細描述。[0024]參見圖1，本發明能夠對等待執行的同構計算任務進行分組，以減少或避免存儲訪問擁塞，分組流程如圖1所示，具體包括以下步驟:
[0025]I)設置並行執行的同構計算任務數nl =處理器核最多能夠支持的硬體線程數；設置預期並行收益pb_exp = I ;
[0026]2)設置n2 = 2Xnl ;然後分別以nl個同構計算任務和n2個同構計算任務並行執行應用，記錄並行執行的同構計算任務數為nl時的運行時間為Tl，並行執行的同構計算任務數為n2時的運行時間為T2 ；
[0027]3)利用並行執行的同構計算任務數為nl時的運行時間Tl以及並行執行的同構計算任務數為n2時的運行時間T2得到實際並行收益為pb_real，且pb_real = T1/T2，若pb_real>2,則將n2的值賦值給nl，返回步驟2);否則轉入步驟4)；
[0028]4)若pb_real≤pb_exp- Δ，則將n2的值賦值給η I,將pb_real的值賦值給pb_exp，返回步驟2);否則，將nl作為一個分組中最多能夠包括的同構計算任務數，其中，Δ =表示可容忍的實際並行收益低於預期並行收益的最大幅度，其值取0.1 ；
[0029]5)利用一個分組中最多能夠包括的同構計算任務數對所有等待執行的同構計算任務進行分組，每間隔Ts時間，順序的將一個分組內的同構計算任務映射到對應的處理器核上開始執行任務；其中，Ts是所有同構計算任務訪存區域的平均執行時間；其中，對於Intel Phi?眾核處理器以及Phoenix++運行時系統,Ts為Oms ^ Ts ^ IOOms ;對於由計算密集型同構計算任務組成的分組，Ts = IOOms ;對於由其它類型的同構計算任務組成的分組，Ts〈100ms。
[0030]本發明中的同構 計算任務是指:那些計算量相同且訪存區域和計算區域的分布相同或非常接近，且能夠在同一時間啟動的計算任務。
[0031]處理器核最多能夠支持的硬體線程數指一個處理器的每個處理核能夠最多支持的硬體線程的數目。
[0032]預期並行收益pb_eXp是指:當並行執行的計算任務數量增加一倍時，程序執行時間預期減少的倍數。
[0033]實際並行收益pb_real指:當並行執行的計算任務數量增加一倍時，程序執行時間實際減少的倍數，即pb_real (η) = T(2n)/T(n) ；Τ(η)表示當並行執行的計算任務數為η時，應用並行執行需要的時間。
[0034]本發明預期並行收益pb_exp和實際並行收益pb_real的對比用於判斷一個分組中的同構計算任務數nl是否合理。當pb_exp_ Δ >pb_real時,說明分組中的同構計算任務數繼續增加，不僅不會帶來預期的或好於預期的並行收益，而且還會導致存儲訪問擁塞。故nl為一個分組在不發生存儲訪問擁塞的情況下最多可以包括的同構計算任務數。
[0035]下面以Word Count應用和支持240硬體線程的Intel Phi?處理器為例，說明分組過程。其中，每個計算任務對應一個硬體線程，Word Count的實際並行收益pb_real如圖2所示，由於所有的pb_real值都不大於1.7，因此，關於pb_real>2的條件判斷可以直接跳過。
[0036]首先，nl = 4, pb_exp = I。
[0037]當nl = 4 時,n2 = 8,由圖 2 可知，pb_real = T (4)/T (8) >pb_exp = 1- Δ.因此，設置 pb_exp = pb_real, nl = n2,繼續迭代。[0038]當nl = 8 時，n2 = 16,由圖 2 可知，pb_real = T (8) /T (16) >pb_exp = T (4) /T (8) - Δ ,設置 pb_exp = pb_real, η I = n2,繼續迭代。
[0039]當nl = 16時，由於Intel Phi?支持的有效硬體線程數為240，為了便於計算，我用使用n2 = 30個計算任務的並行執行近似表示nl = 16個計算任務數翻倍後的執行。由圖2可知，pb_real = T (16)/T (30) <pb_exp = T⑶/T (16)-Δ ,說明計算任務數繼續增加不會進一步增加並行收益pb_real，反而會誘發存儲訪問擁塞，因此，結束迭代，將nl賦值給Group_Size,表示一個分組最多能夠包括Group_Size = 16個同構計算任務。
[0040]利用一個分組中最多能夠包括的同構計算任務數對所有等待執行的同構計算任務進行分組；每間隔Ts時間，將一個分組內的同構計算任務映射到對應的處理器核上開始執行任務，目的是在某一時間段Ts內只執行一個分組的訪存區域。使用分組方法和未使用分組方法的應用程式執行區別如圖3所示。
[0041]由圖3可以看出，由於不同分組的訪存區域分布在不同的時間段內，而執行單個分組的訪存區域不會誘發存儲訪問擁塞，因此，存儲訪問部件可以一直工作在非擁塞狀態，避免了存儲訪問擁塞的發生。儘管Ts推遲了部分計算任務的執行，然而基於分組的執行明顯縮短了同構計算任務的存儲訪問時間，使得運行完所有同構計算任務整體所用的時間更短。
[0042]本發明通過迭代方式計算出在不發生存儲訪問擁塞的情況下允許的最大分組，通過流水線控制不同分組之間的計算和訪存重疊，有效減少了並行應用在眾核系統執行時存儲訪問擁塞發生的機會。該分組方法不需要在算法層面對是否發生存儲訪問擁塞進行分析，為具有同構計算任務特徵的大數據應用的訪存性能分析和優化提供了統一有效的方法。
【權利要求】
1.一種用於消除存儲訪問擁塞的同構計算任務分組方法，其特徵在於，包括如下步驟: 1)設置並行執行的同構計算任務數nl=處理器核最多能夠支持的硬體線程數；設置預期並行收益pb_exp = I ； 2)設置n2= 2Xnl ;然後分別以nl個同構計算任務和n2個同構計算任務並行執行應用，記錄並行執行的同構計算任務數為nl時的運行時間為Tl，並行執行的同構計算任務數為n2時的運行時間為T2 ； 3)利用並行執行的同構計算任務數為nl時的運行時間Tl以及並行執行的同構計算任務數為n2時的運行時間T2得到實際並行收益為pb_real，且pb_real = T1/T2，若pb_real>2,則將n2的值賦值給nl，返回步驟2);否則轉入步驟4)； 4)若pb_real≥ pb_exp- Δ，則將η2的值賦值給η I,將pb_real的值賦值給pb_exp,返回步驟2);否則，將nl作為一個分組中最多能夠包括的同構計算任務數，其中，Δ =表示可容忍的實際並行收益低於預期並行收益的最大幅度； 5)利用一個分組中最多能夠包括的同構計算任務數對所有等待執行的同構計算任務進行分組，每間隔Ts時間，順序的將一個分組內的同構計算任務映射到對應的處理器核上開始執行任務；其中，Ts是所有同構計算任務訪存區域的平均執行時間。
2.根據權利要求1用於消除存儲訪問擁塞的同構計算任務分組方法，其特徵在於:所述的步驟4)中，對於Intel Phi?眾核處理器以及Phoenix++運行時系統，Ts為Oms≤Ts≤100ms ;對於由計算密集型同構計算任務組成的分組,Ts = IOOms ;對於由其它類型的同構計算任務組成的分組，Ts〈100ms。
3.根據權利要求1用於消除存儲訪問擁塞的同構計算任務分組方法，其特徵在於:所述的步驟4)中，Δ =O-10
【文檔編號】G06F9/48GK103995744SQ201410219408
【公開日】2014年8月20日 申請日期:2014年5月22日 優先權日:2014年5月22日
【發明者】董小社, 李亮, 朱正東, 張興軍, 巨濤, 白秀秀, 顏康 申請人:西安交通大學