面向異構(gòu)多核處理器的的循環(huán)分塊

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

（1.信息工程大學(xué)，河南 鄭州450001；2.數(shù)學(xué)工程與先進(jìn)計(jì)算國家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州450001）

0 引 言

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

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

要將已有的大量串行程序改寫成OpenACC并行程序并非易事，使用自動(dòng)并行化技術(shù)［9］將串行程序自動(dòng)變換成適合異構(gòu)系統(tǒng)的OpenACC并行程序，是獲得OpenACC 并行程序的一條有效途徑。因此，本文提出了一個(gè)針對(duì)異構(gòu)多核處理器的循環(huán)分塊子句自動(dòng)生成算法，并在基于Open64開發(fā)的面向異構(gòu)多核處理器的 “源－源”自動(dòng)并行化系統(tǒng)Auto－ACC中進(jìn)行了實(shí)現(xiàn)。

1 異構(gòu)多核處理器

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

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

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

圖1 Cell處理器結(jié)構(gòu)

2 循環(huán)分塊子句的引入

為了讓OpenACC能夠更好地發(fā)揮異構(gòu)多核處理器的計(jì)算優(yōu)勢(shì)，盡量克服異構(gòu)多核處理器存儲(chǔ)方面的弱點(diǎn)，本節(jié)對(duì)OpenACC進(jìn)行擴(kuò)展，引入了循環(huán)分塊子句block。block子句對(duì)循環(huán)的分塊信息進(jìn)行說明，指導(dǎo)編譯器將循環(huán)按照指定的分塊大小進(jìn)行分割，同時(shí)將循環(huán)對(duì)應(yīng)的數(shù)據(jù)按照同樣的塊進(jìn)行分割。

下面給出block子句：

（1）語法：

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

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

（2）說明：

block子句對(duì)循環(huán)各層進(jìn)行分塊，循環(huán)在執(zhí)行時(shí)各層只能以指定的塊大小劃分給加速線程，并且循環(huán)引用的數(shù)組對(duì)應(yīng)的各維也按照同樣的塊大小進(jìn)行分割。恰當(dāng)?shù)姆謮K方案則能使各數(shù)組的數(shù)據(jù)塊加載到設(shè)備內(nèi)存，并且每個(gè)加速線程執(zhí)行的循環(huán)塊有良好的數(shù)據(jù)局部性。

（3）示例：

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

下面說明block子句針對(duì)該示例，指導(dǎo)編譯器進(jìn)行循環(huán)分塊的過程。

第1步：對(duì)第1層 （i－循環(huán)）以塊大小1進(jìn)行劃分，得到100個(gè)循環(huán)塊，其中第m （m＝1，2，…，100）塊為：

每個(gè)循環(huán)塊仍是3層嵌套循環(huán)，第1層迭代量為1，第2、第3層同原循環(huán)。

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

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

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

這里我們把異構(gòu)多核處理器中的加速器陣列看做是線性陣列，則循環(huán)塊、數(shù)據(jù)塊到加速器的映射過程如圖2所示。

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

圖2 循環(huán)塊、數(shù)據(jù)塊到加速器的映射

3 循環(huán)分塊子句生成算法

生成循環(huán)分塊子句的關(guān)鍵是找到最優(yōu)的循環(huán)分塊方案，即在保證循環(huán)塊所需數(shù)據(jù)加載進(jìn)設(shè)備內(nèi)存的同時(shí)，盡可能地提高分塊后循環(huán)塊的局部性。對(duì)這兩個(gè)方面分別進(jìn)行分析：一是構(gòu)建數(shù)學(xué)模型描述循環(huán)分塊和對(duì)應(yīng)的數(shù)組分塊情況，以便分塊方案能夠保證循環(huán)塊所需數(shù)據(jù)加載進(jìn)設(shè)備內(nèi)存并且盡可能充滿設(shè)備內(nèi)存；二是在分塊過程中利用數(shù)據(jù)重用理論［11］保證分塊是有利的，即能夠提高程序的局部性。

3.1 問題的數(shù)學(xué)模型

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

不同數(shù)組的數(shù)據(jù)塊加載到設(shè)備內(nèi)存時(shí)，其總大小不能超過設(shè)備內(nèi)存容量。于是，循環(huán)分塊方案的求解問題可以建模為以下最優(yōu)解問題

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

3.2 數(shù)據(jù)重用理論

這里直接引用了文獻(xiàn) ［11］中數(shù)據(jù)重用相關(guān)的部分。一個(gè)準(zhǔn)確的數(shù)據(jù)依賴代表兩個(gè)訪問同一內(nèi)存單元的不同語句實(shí)例，因此依賴就可以被看成指示那些經(jīng)常被重用的存儲(chǔ)單元。就這一點(diǎn)來說，程序中越多的依賴意味著越多的重用。

關(guān)于循環(huán)分塊的有利性，有以下結(jié)論：

通常，如果在一個(gè)非最內(nèi)層的循環(huán)的不同迭代間有重用，則分塊是有利的。

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

3.3 算法的具體實(shí)現(xiàn)

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

要求解3.1節(jié)中模型的最優(yōu)解較為復(fù)雜，這里我們采用了貪心算法進(jìn)行求解：

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

然后，從外到內(nèi)依次求解循環(huán)每一層的分塊值，即解向量b的每一維的值。在求解嵌套循環(huán)每一層的分塊值時(shí)，都使該層的分塊值是滿足約束條件的最大值，及一個(gè)局部最優(yōu)解；

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

一個(gè)n層循環(huán)嵌套的循環(huán)分塊方案的求解算法為：

算法：循環(huán)分塊方案求解算法

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

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

3.4 實(shí)例分析

本小節(jié)通過下面矩陣乘法的核心對(duì)循環(huán)分塊子句生成算法進(jìn)行說明。

首先我們對(duì)循環(huán)次序進(jìn)行調(diào)整，使得內(nèi)層循環(huán)具有小跨距的訪問，到得的循環(huán)如下：

假設(shè)A、B、C數(shù)組為整型數(shù)組，整型數(shù)據(jù)大小為4字節(jié)，設(shè)備內(nèi)存空間為16KB （16384字節(jié)），矩陣規(guī)模N 為128。循環(huán)分塊方案求解算法實(shí)施過如下：

第1步：計(jì)算該循環(huán)使用數(shù)組的總大小。其值為 （3＊128＊128）＊4＝196608字節(jié)，遠(yuǎn)遠(yuǎn)超出設(shè)備內(nèi)存空間的大小，必須分塊后才能裝入設(shè)備內(nèi)存。

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

第3步：計(jì)算次外層循環(huán) （K－循環(huán)）的分塊大小。由于對(duì)C（I，J）的重用和對(duì)B（K，J）的鄰接引用，所以K－循環(huán)也帶有重用，對(duì)該層循環(huán)的分塊是有利的。先令該層的分塊大小為1，這時(shí)A 數(shù)組的第2維按塊大小1劃分，B數(shù)組第1維、第2維都按塊大小1劃分，C數(shù)組仍是第2維按塊大小1劃分，3個(gè)數(shù)組數(shù)據(jù)塊的總大小為 （128＊1＋1＊1＋128＊1）＊4＝1028字節(jié)，遠(yuǎn)小于設(shè)備內(nèi)存空間大小。為充分利用存儲(chǔ)空間，應(yīng)增大分塊值。當(dāng)該層的分塊值增大到31時(shí)，3個(gè)數(shù)組數(shù)據(jù)塊的總大小為 （128＊31＋31＊1＋128＊1）＊4＝16508，大于設(shè)備內(nèi)存空間，已達(dá)到臨界值，所以該層分塊大小應(yīng)為30，算法結(jié)束。

所以該算法得到的循環(huán)分塊方案為 （1，30，0），即最外層按塊大小1劃分，次外層按塊大小30劃分，最內(nèi)層不劃分。上述矩陣乘法的核心代碼段對(duì)應(yīng)的擴(kuò)展了循環(huán)分塊子句的OpenACC代碼為：

4 實(shí)驗(yàn)結(jié)果與分析

課題開發(fā)的自動(dòng)并行化系統(tǒng)Auto－ACC 已實(shí)現(xiàn)了含有循環(huán)分塊子句的OpenACC 程序的自動(dòng)生成。本節(jié)使用的測(cè)試平臺(tái)為某國產(chǎn)異構(gòu)多核處理器構(gòu)成的計(jì)算機(jī)系統(tǒng)，該國產(chǎn)異構(gòu)多核處理器采用主從核結(jié)構(gòu)，由通用處理主核和精簡的計(jì)算從核組成。單個(gè)計(jì)算節(jié)點(diǎn)包含一個(gè)主核和一個(gè)從核陣列。從核陣列有64個(gè)從核，每個(gè)從核運(yùn)行輕量級(jí)操作系統(tǒng)，擁有大小為16KB 的局部存儲(chǔ)器。并安裝有江南計(jì)算所研發(fā)的支持OpenACC 擴(kuò)展規(guī)范的編譯器JC－ACC。

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

圖3給出了針對(duì)上文中矩陣乘法在12種不同分塊方案下的程序運(yùn)行時(shí)間對(duì)比?？梢钥闯霰疚乃惴ㄇ蟮玫姆綁K方案 （1，30，0）是一個(gè)較優(yōu)的方案，但存在另一較優(yōu)的分塊方案 （2，30，0）。這是因?yàn)楸疚牡乃惴樨澬乃惴?，不能總是求得總體最優(yōu)解，但本文算法求得的方案十分接近最優(yōu)解，引起的程序運(yùn)行時(shí)間的差異很小。其中，方案（1，0，0）和 （2，0，0）因分塊過大，導(dǎo)致循環(huán)塊所需數(shù)據(jù)大部分需要加速器發(fā)起DMA 從主存移動(dòng)到設(shè)備內(nèi)存，運(yùn)行時(shí)間較長。方案 （1，1，0）和 （2，1，0）因?yàn)榉謮K太小，導(dǎo)致了過多的調(diào)度開銷。

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

圖4 不同矩陣規(guī)模分塊算法效果對(duì)比

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

圖5 科學(xué)計(jì)算程序分塊前后加速比對(duì)比

5 結(jié)束語

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

［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）.［杜靜，敖富江，唐滔，等.流處理器上基于參數(shù)模型的長流分段技術(shù) ［J］.軟件學(xué)報(bào)，2009，20 （9）：2320－2331.］

［6］Li L，Wu H，F(xiàn)eng 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）. ［劉勇，陸林生，何王全.一種面向軟件管理內(nèi)存層次的簡易數(shù)據(jù)分塊方法 ［J］.軟件學(xué)報(bào)，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.