面向異構多核處理器的的循環分塊

李雁冰，趙榮彩，趙 博，黃品豐

（1.信息工程大學，河南 鄭州450001；2.數學工程與先進計算國家重點實驗室，河南 鄭州450001）

0 引 言

異構多核處理器給高性能計算提供了巨大的潛力，也同時給編程提出了更大的挑戰。解決編程問題，首先要有簡單易用的編程模型。近些年來，面向異構系統的編程模型發展迅速，出現了一大批并行編程模型［1］。其中，Nvidia等4家公司聯合發布的OpenACC［2］受到了廣泛關注。目前，OpenACC在GPU 平臺上已經取得了很好的效果［3］。但在把OpenACC用于異構多核處理器時，操作大量數據的代碼不能獲得很好的加速。原因是異構多核處理器中加速器的設備內存空間有限，代碼訪問的數據量過大時，無法一次性將所需數據加載到設備內存。當程序運行過程中設備內存失效，會由加速器發起直接存儲器訪問 （direct memory access，DMA），從主存讀入所需數據到設備內存，而這個時延通常是巨大的。針對這一問題，本文對OpenACC進行擴展，引入了循環分塊子句，對循環進行分塊處理，使得每個循環塊中的數據能夠存儲在設備內存中。

循環分塊是提高傳統處理器Cache上訪存效率的有效方法［4］，也可以用于提高異構多核處理器的性能。但是二者之間有一些差別，針對Cache的循環分塊只需要考慮如何使Cache中的數據盡可能多地得到重用。而在異構多核處理器上，不但需要考慮循環如何分塊，還需考慮數據的分塊問題，即設備內存容量對數據分塊大小的限制。使用分塊技術來優化數據的傳輸是異構系統上編譯優化技術的研究熱點。比如，文獻 ［5］提出了一種基于參數模型的長流分段技術；文獻 ［6］提出了結合循環分塊、數組分塊技術與區間著色數據布局技術的優化方法。這些分塊方法，需要通過分析程序的數據依賴關系對循環進行分塊變換，只能處理可置換循環，且實現難度大，不能充分利用原有循環結構的局部性［7］。本文引入的循環分塊子句用于指示編譯器，將循環的迭代空間按照指定的分塊大小進行分割，劃分給加速線程 （其作用類似于OpenMP［8］中的schedule子句），分塊過程不需要進行數據依賴關系的分析和程序變換，更加簡單易用，而且不改變原有循環的結構，保證了原有循環結構的局部性。

要將已有的大量串行程序改寫成OpenACC并行程序并非易事，使用自動并行化技術［9］將串行程序自動變換成適合異構系統的OpenACC并行程序，是獲得OpenACC 并行程序的一條有效途徑。因此，本文提出了一個針對異構多核處理器的循環分塊子句自動生成算法，并在基于Open64開發的面向異構多核處理器的 “源－源”自動并行化系統Auto－ACC中進行了實現。

1 異構多核處理器

異構多核處理器是在一個芯片內集成了多個不同結構或功能的處理器核，一般包含通用主處理和加速器。異構多核處理器可以使用不同類型的處理器核來完成不同類型的任務，如任務并行度較高，則使用眾多精簡的加速器提速，否則用強大的通用主處理器運行。這比用相同的處理器核執行所有任務更有效率，更利于提高處理器的性能。其典型代表有索尼、東芝和IBM 公司聯合開發的Cell處理［10］，ClearSpeed公司的CSX600處理器，AMD 的Fusion APU，Stream Processors公司的storm－1處理器等。

其中Cell處理器的結構如圖1所示，一個Cell芯片上包含 一 個PowerPC 處 理 單 元PPE （powerPC processing element）和8個協同處理單元SPE （synergistic processing element）。PPE 上 有 一 個PowerPC 核 心 和L1、L2 兩 級cache，SPE支持類AltiVec的向量指令，并且有256KB的局部存儲器LS。PPE負責SPE上計算任務的調度。SPE在計算時只能訪問自身的LS，LS和主存Memory之間的數據傳輸通過互連網絡EIB （element interconnect bus）和訪存控制 器MIC （memory interface controller）使 用DMA 方式實現。

通常，異構多核處理器的主處理器包含有容量較大的主存，加速器包含設備內存。設備內存占用的芯片面積更少，功耗更低，訪問速度更快，但容量有限，往往無法滿足使用大數組的科學計算程序的存儲需求。大部分數據存儲在主存，設備內存失效時必須通過DMA 操作完成主存與設備內存的數據傳輸。然而DMA 操作開銷較大，DMA次數過多會大大降低程序性能。因此提高設備內存空間利用率，減少DMA 次數，是發揮異構多核處理器性能的關鍵。

圖1 Cell處理器結構

2 循環分塊子句的引入

為了讓OpenACC能夠更好地發揮異構多核處理器的計算優勢，盡量克服異構多核處理器存儲方面的弱點，本節對OpenACC進行擴展，引入了循環分塊子句block。block子句對循環的分塊信息進行說明，指導編譯器將循環按照指定的分塊大小進行分割，同時將循環對應的數據按照同樣的塊進行分割。

下面給出block子句：

（1）語法：

block （index1：blocksize1，index2：blocksize2，...）

index1、index2等為嵌套循環從外到內的各層索引變量，blocksize1、blocksize2等為該層的分塊大小。某一層不需要分塊時，其索引變量和分塊大小省略不寫。block子句作為loop構造的可選子句，使用時必須出現在loop構造的子句列表中。

（2）說明：

block子句對循環各層進行分塊，循環在執行時各層只能以指定的塊大小劃分給加速線程，并且循環引用的數組對應的各維也按照同樣的塊大小進行分割。恰當的分塊方案則能使各數組的數據塊加載到設備內存，并且每個加速線程執行的循環塊有良好的數據局部性。

（3）示例：

block子句指示對該嵌套循環第1層 （i－循環）以塊大小為1的方式劃分，第2層 （j－循環）以塊大小為3的方式劃分，第3層 （k－循環）不劃分。同時，數組A 的第1 維也以塊大小為1的方式劃分，第2維以塊大小為3的方式劃分；數組B的第1維以塊大小為3的方式劃分。

下面說明block子句針對該示例，指導編譯器進行循環分塊的過程。

第1步：對第1層 （i－循環）以塊大小1進行劃分，得到100個循環塊，其中第m （m＝1，2，…，100）塊為：

每個循環塊仍是3層嵌套循環，第1層迭代量為1，第2、第3層同原循環。

第2步：對上一步得到的100個循環塊的第2層 （j－循環）以塊大小3進行劃分，每個循環塊又被劃分為34個小塊，除最后一小塊第2 層的迭代量為1，其它為3。其中，第1次分塊得到的第m 個循環塊第2次劃分以后的第n （n＝1，2，…，34）個塊記為第 （m，n）塊，為：

在將循環塊加載到加速器執行時，由于第1 層 （i－循環）為并行層，編號的第1維不同的循環塊可以按照任意順序調度執行。第2層循環 （j－循環）只能串行執行，所以第1維相同的循環塊第2維數字小的必須先執行。例如第（1，3）、（2，1）塊可按任意順序執行，第 （1，3）塊必須在第 （1，4）塊之前執行。

每個循環塊引用的數據也將是原來數組的一個數據塊，循環塊引用的數據塊會在編譯時由編譯器分析得到。（數組數據塊表示方法為數組名后跟一個方括號，方括號內的起始下標和長度用來指定數組范圍，例如a［2：n］表示元素a［2］，a［3］，…，a［2＋n－1］。）第 （m，n）塊循環引用的數組A、B的數據塊分別為A ［m－1］［3 （n－1）：3］［0：100］、B ［3 （n－1）：3］［0：100］ （當n小于34時）或A ［m－1］ ［99：3］ ［0：100］、B ［99：1］ ［0：100］（當n等于34時）。

這里我們把異構多核處理器中的加速器陣列看做是線性陣列，則循環塊、數據塊到加速器的映射過程如圖2所示。

通常的循環分塊方法需要根據程序數據依賴關系，通過進行循環分段和循環交換實現分塊，其實現過程復雜而且程序變換可能破壞原有循環結構的局部性，且只能用于可置換循環。而block子句實現的循環分塊是在把循環的迭代空間劃分給加速線程時，按照指定的塊大小進行劃分，其劃分過程不需要考慮數據依賴關系，也不需要進行程序變換，更加簡單易用，而且適用于各種循環結構。

圖2 循環塊、數據塊到加速器的映射

3 循環分塊子句生成算法

生成循環分塊子句的關鍵是找到最優的循環分塊方案，即在保證循環塊所需數據加載進設備內存的同時，盡可能地提高分塊后循環塊的局部性。對這兩個方面分別進行分析：一是構建數學模型描述循環分塊和對應的數組分塊情況，以便分塊方案能夠保證循環塊所需數據加載進設備內存并且盡可能充滿設備內存；二是在分塊過程中利用數據重用理論［11］保證分塊是有利的，即能夠提高程序的局部性。

3.1 問題的數學模型

因為循環分塊子句為loop構造的可選子句，其分塊的對象為外層可并行執行的嵌套循環。設并行嵌套循環為｛L1，L2，...，Ln｝，其 中L1為 最 外 層 循 環 （即 并 行 循 環層），Ln為最內層循環。循環引用數組Ak（k＝1，2，...，m）的維數為lk，數組元素大小為Sk。設備內存容量為M 。循環嵌套層Li（i，＝1，2，...，n）的分塊大小為bi，bi＝0表示該維不分塊。如果數組Ak第j（j＝1，2，...，lk）維的下標表達式中含有循環嵌套層Li的索引變量，當Li的分塊大小bi≠0時，數組Ak第j維的分塊大小d（k，j）＝bi；否則，該維不分 塊，則 分 塊 大 小d（k，j）＝D（k，j），其 中D（k，j）表 示 數 組Ak第j 維的元素個數。為方便表示，用x（k，j）等于1和0分別表示數組Ak第j 維分塊和不分塊。

不同數組的數據塊加載到設備內存時，其總大小不能超過設備內存容量。于是，循環分塊方案的求解問題可以建模為以下最優解問題

循環分塊方案的求解即是求滿足條件的向量b＝（b1，b2，...，bn）T，使 各 數 組 的 數 據 塊 之 和 所 占 空 間 盡 可 能地大。

3.2 數據重用理論

這里直接引用了文獻 ［11］中數據重用相關的部分。一個準確的數據依賴代表兩個訪問同一內存單元的不同語句實例，因此依賴就可以被看成指示那些經常被重用的存儲單元。就這一點來說，程序中越多的依賴意味著越多的重用。

關于循環分塊的有利性，有以下結論：

通常，如果在一個非最內層的循環的不同迭代間有重用，則分塊是有利的。

在兩種情況下，可以得到外層循環的重用：①循環攜帶一個有小的閾值的任何類型的依賴，包括輸入依賴，循環攜帶依賴；②循環的索引變量出現在一個多維數組的連續維中，而不出現在其它維中。

3.3 算法的具體實現

在實現循環分塊子句生成算法時，以3.1 節中的數學模型為基礎，計算每一層的分塊大小，并利用3.2 節中的數據重用理論決定是否對該層進行分塊，以保證對該層的分塊是有利的。在循環分塊之前，我們已經對循環的次序進行了調整，使得內層循環具有小跨距的訪問，以便程序有更好的局部性。嵌套循環的最外層為并行層，對該層劃分得到的塊將并行地執行，所以需要分塊時總是先對最外層進行分塊，而且對最外層進行分塊得到的分塊數不能少于加速部件的數目，否則將造成計算資源的浪費。分塊本身會帶來一定的調度開銷，為減少分塊數目，對盡量少的層進行分塊。本節基于以上原則設計了分塊方案求解算法。

要求解3.1節中模型的最優解較為復雜，這里我們采用了貪心算法進行求解：

首先，令b＝（0，0，...，0）T；

然后，從外到內依次求解循環每一層的分塊值，即解向量b的每一維的值。在求解嵌套循環每一層的分塊值時，都使該層的分塊值是滿足約束條件的最大值，及一個局部最優解；

最后，用每一層的局部最優分塊值合成整體分塊方案最優解的近似解。

一個n層循環嵌套的循環分塊方案的求解算法為：

算法：循環分塊方案求解算法

輸入：并行嵌套循環L＝ ｛L1，L2，…，Ln｝ （L1為并行循環層，且循環次序已做了調整，內層循環具有小跨距的訪問），嵌套層數n，設備內存大小M，加速器數目N

輸出：循環分塊方案b ［n］ （b ［i］為循環Li的分塊大小，b ［i］等于0表示該層循環不分塊）

3.4 實例分析

本小節通過下面矩陣乘法的核心對循環分塊子句生成算法進行說明。

首先我們對循環次序進行調整，使得內層循環具有小跨距的訪問，到得的循環如下：

假設A、B、C數組為整型數組，整型數據大小為4字節，設備內存空間為16KB （16384字節），矩陣規模N 為128。循環分塊方案求解算法實施過如下：

第1步：計算該循環使用數組的總大小。其值為 （3＊128＊128）＊4＝196608字節，遠遠超出設備內存空間的大小，必須分塊后才能裝入設備內存。

第2步：計算最外層循環 （J－循環）的分塊大小。由于A（I，K）的自輸入依賴，該層具有重用，對該層的分塊是有利的。先令該層的分塊大小為1，這時數組A 不劃分，數組B和C 的第2維也按塊大小1劃分，3個數組數據塊的總大小為 （128＊1＋128＊1＋128＊128）＊4＝66560 字節，超過了設備內存空間的大小。說明對數組該維的最小分塊仍會使設備存儲空間溢出，需要對下一維進行劃分。取該層的分塊值為1。

第3步：計算次外層循環 （K－循環）的分塊大小。由于對C（I，J）的重用和對B（K，J）的鄰接引用，所以K－循環也帶有重用，對該層循環的分塊是有利的。先令該層的分塊大小為1，這時A 數組的第2維按塊大小1劃分，B數組第1維、第2維都按塊大小1劃分，C數組仍是第2維按塊大小1劃分，3個數組數據塊的總大小為 （128＊1＋1＊1＋128＊1）＊4＝1028字節，遠小于設備內存空間大小。為充分利用存儲空間，應增大分塊值。當該層的分塊值增大到31時，3個數組數據塊的總大小為 （128＊31＋31＊1＋128＊1）＊4＝16508，大于設備內存空間，已達到臨界值，所以該層分塊大小應為30，算法結束。

所以該算法得到的循環分塊方案為 （1，30，0），即最外層按塊大小1劃分，次外層按塊大小30劃分，最內層不劃分。上述矩陣乘法的核心代碼段對應的擴展了循環分塊子句的OpenACC代碼為：

4 實驗結果與分析

課題開發的自動并行化系統Auto－ACC 已實現了含有循環分塊子句的OpenACC 程序的自動生成。本節使用的測試平臺為某國產異構多核處理器構成的計算機系統，該國產異構多核處理器采用主從核結構，由通用處理主核和精簡的計算從核組成。單個計算節點包含一個主核和一個從核陣列。從核陣列有64個從核，每個從核運行輕量級操作系統，擁有大小為16KB 的局部存儲器。并安裝有江南計算所研發的支持OpenACC 擴展規范的編譯器JC－ACC。

本節的測試分為3個部分：首先，針對上文中的矩陣乘法測試不同分塊方案下的運行時間，驗證本文算法求解得到的分塊方案是否為最優的分塊方案；然后，改變矩陣乘法的規模，驗證算法對不同的數據規模是否都能取得好的效果；最后，選擇了期權定價模型BlackScholes、spec2000中天氣預報建模程序swim 的calc2、雅可比迭代jacobi以及交替方向迭代adi等4個科學計算程序，這4個程序的核心循環主要是對數組的操作，需要大量的設備內存空間，通過比較含有本文算法生成的循環分塊子句的OpenACC程序和沒有循環分塊子句的OpenACC 程序的加速比，驗證了本文擴展的循環分塊子句及提出的循環分塊子句生成算法對異構多核處理器是有效的。

圖3給出了針對上文中矩陣乘法在12種不同分塊方案下的程序運行時間對比。可以看出本文算法求得的方塊方案 （1，30，0）是一個較優的方案，但存在另一較優的分塊方案 （2，30，0）。這是因為本文的算法為貪心算法，不能總是求得總體最優解，但本文算法求得的方案十分接近最優解，引起的程序運行時間的差異很小。其中，方案（1，0，0）和 （2，0，0）因分塊過大，導致循環塊所需數據大部分需要加速器發起DMA 從主存移動到設備內存，運行時間較長。方案 （1，1，0）和 （2，1，0）因為分塊太小，導致了過多的調度開銷。

圖4給出了矩陣乘法在128、256、512和1024這4個規模下，含有本文算法生成的循環分塊子句和沒有循環分塊子句的OpenACC程序的運行時間對比。有循環分塊子句的OpenACC程序運行時間和沒有循環分塊子句的相比，平均加速了6.53倍。其結果表明本文算法對不同的數據規模都能取得好的效果，而且矩陣規模越大，計算量和所需的數據量越大時，加速效果越好。

圖4 不同矩陣規模分塊算法效果對比

圖5給出了BlackScholes、calc2、jacobi、adi這4個程序，在帶有本文算法生成的循環分塊子句的情況下，加速比的提升情況，加速比平均提升2.66倍。其結果表明本文擴展的循環分塊子句及提出的循環分塊子句生成算法在異構多核處理器上能夠對程序進行明顯的加速。其中，Black－Scholes的并行循環為單層循環，對其進行分塊后無法帶來數據重用，所以性能提升不是很明顯。而其它3個程序的并行循環為二層或三層嵌套循環的外層循環，對其分塊后能帶來較多的數據重用，有效減少DMA次數，加速效果明顯。

圖5 科學計算程序分塊前后加速比對比

5 結束語

異構系統的迅速發展亟需一個簡單易用可移植的編程模型，人們對OpenACC 寄予厚望，希望它能像OpenMP（面向共享存儲結構）一樣被廣泛使用。目前OpenACC 已經在GPU 上取得了很好的效果，本文所屬課題的工作是把OpenACC運用于異構多核處理器，并針對異構多核處理器的特點對OpenACC做了相應的擴展。本文增加了循環分塊子句，并給出了一個有效的循環分塊子句生成算法。但本文算法沒有考慮分塊后加速器間的負載均衡等問題，需要進一步的完善。

［1］Duran A，AyguadéE，Badia RM，et al.Ompss：A proposal for programming heterogeneous multicore architectures ［J］.Parallel Processing Letters，2011，21 （2）：173－193.

［2］The OpenACC application programming interface ［EB／OL］.www.OpenACC－Standard.org，2013.

［3］Customer＿Stories［EB／OL］.www.openacc－standard.org，2013.

［4］Bao B，Xiang X.Defensive loop tiling for multi－core processor［C］／／Proceedings of the ACM SIGPLAN Workshop on Memory Systems Performance and Correctness.ACM，2012：76－77.

［5］DU Jing，AO Fujiang，TANG Tao，et al.Parameter model based strip－mining technique on the stream processor ［J］.Journal of Software，2009，20 （9）：2320－2331 （in Chinese）.［杜靜，敖富江，唐滔，等.流處理器上基于參數模型的長流分段技術 ［J］.軟件學報，2009，20 （9）：2320－2331.］

［6］Li L，Wu H，Feng H，et al.Towards data tiling for whole programs in scratchpad memory allocation ［G］.LNCS 4697：Advances in Computer Systems Architecture.Berlin：Springer Berlin Heidelberg，2007：63－74.

［7］LIU Yong，LU Linsheng，HE Wangquan.Easy data tiling method for software－managed memory hierarchies［J］.Journal of Software，2010，21 （Sl）：290－297 （in Chinese）. ［劉勇，陸林生，何王全.一種面向軟件管理內存層次的簡易數據分塊方法 ［J］.軟件學報，2010，21 （Sl）：290－297.］

［8］OpenMP 3.1 specifications ［EB／OL］.openmp.org／wp／openmp－specifications／，2013.

［9］Midkiff SP.Automatic parallelization：An overview of fundamental compiler techniques ［M］.Morgam ＆ Claypool Publishers，2012：1－169.

［10］Chen T，Raghavan R，Dale JN，et al.Cell broadband engine architecture and its first implementation：A performance view［J］.IBM Journal of Research and Development，2007，51（5）：559－572.

［11］Allen R，Kennedy K.Optimizing compilers for modern architectures：A dependence－based approach ［M］.1st ed.California：Morgan Kaufmann Publisher，2001：547－548.