一種面向異構眾核處理器的并行編譯框架*

李雁冰,趙榮彩,韓 林,趙 捷,徐金龍,李穎穎

(數學工程與先進計算國家重點實驗室,河南 鄭州 450001)

雖然處理器一直在遵循著摩爾定律快速發展,但是目前計算機系統的計算能力仍然不能滿足人類社會的需求,在氣象預報、石油勘探、材料合成、藥物研究、地球模擬等眾多領域仍然亟需更快的計算速度來進行科學研究.高性能計算已經成為繼理論研究、科學實驗之后的第三大科學手段,并且發揮的作用越來越重要[1].傳統的單核處理器主要依靠提高主頻來獲得更快的計算速度,但是由于主頻提高后帶來的功耗和散熱等問題的限制,主頻已很難繼續提高.因此,增加計算資源成為提高計算速度的主要方式,在單個芯片上集成更多的處理器核心已經成為當前處理器設計的主流.目前處理器核心的數目增長很快,尤其是面向高性能計算領域的處理器已經進入眾核時代[2].相比通用的多核處理器,眾核處理器在片上集成了超出數量級的簡化核心,可以提供更高的計算能力、計算密度和性能功耗比.眾核已被業界視為繼單核、多核之后處理器發展的第三個時代,它為在今后的一段時間內繼續維持摩爾定律提供了可能.2016年6月,我國自主研制的“神威太湖之光”計算機發布,其峰值性能、持續性能、性能功耗比3項關鍵指標均居世界第一[3],“太湖之光”的核心器件之一便是自主設計的SW26010眾核處理器.

按照集成處理器核種類的不同,眾核處理器主要分為兩類:同構眾核處理器和異構眾核處理器.同構眾核處理器是在一個芯片內集成了多個結構相同、地位對等的處理器核.異構眾核處理器則是在一個芯片內集成了多個不同結構的處理器核.目前,主流的商用眾核處理器多為同構眾核結構,如 Intel的至強 Phi協處理器[4]和NVIDIA公司的 GPGPU系列的產品[5].同構眾核主要作為加速器,與通用CPU一起構成高性能計算系統,對應用的計算密集部分進行加速.但這種方式存在一些不足:CPU與眾核處理器通過PCI-E接口連接,二者之間的數據傳輸有較大的延遲,并且數據傳輸帶來了額外的功耗,松耦合的系統架構降低了高性能計算系統的組裝密度.異構眾核處理器則在同一芯片內集成了具有控制管理功能的通用處理器核心和大量用于加速計算的精簡計算核心,能夠實現較高的性能功耗比和計算密度,彌補了上述同構眾核的不足[2].首先在處理器內部采用異構結構的是索尼、東芝和IBM等公司聯合開發的Cell處理器[6].目前各主要處理器廠商已經開始異構眾核處理器的開發或研究工作,如AMD公司的APU[7]、NVIDIA公司牽頭的Echolen[8]項目、Intel公司牽頭的Runnemede項目[9]等,采用異構眾核處理器是未來構建高性能計算系統的重要趨勢.

異構眾核架構雖然具有諸多優勢,但在單個計算節點內集成大量不同類型的處理器核心,使得體系結構更加復雜,這給程序設計和編譯優化都帶來了更大的挑戰.從程序設計和編譯優化的角度看,異構眾核處理器結構主要有以下特點:一是異構眾核處理器內集成了更多的處理器核心,能夠提供更多的計算資源,需要發掘出應用程序中更多的并行性；二是異構眾核處理器為了控制功耗,大多使用了軟件管理的SPM(scratch pad memory),編程時需要用戶程序管理SPM空間,顯式地控制數據在通用核心和加速計算核心之間的傳輸；三是異構眾核處理器的SPM由軟件管理,不同于以往的硬件Cache,傳統的面向Cache結構的編譯優化技術不再適用.這種結構上的復雜性使得在異構眾核處理器上的并行程序開發面臨著巨大的挑戰.

解決并行編程問題有兩種基本方法:一種是程序員手工編寫并行程序；另一種是使用并行化編譯系統.程序員手工編寫的并行程序在經過精心優化后往往有很高的運行效率,但手工編寫并行程序需要程序員熟悉相關領域,精通并行編程模型,了解硬件的體系結構和指令集特點等,對程序員要求很高.而且,手工編寫并行程序的效率很低,對于過去數十年來積累的大量優秀的應用程序,將其進行手工改寫需要花費大量的時間和人力.并行化編譯系統是一個自動發掘程序中潛在并行性并將其轉換為并行程序的編譯工具,相比手工編寫并行程序,能夠快速地完成串行程序到并行程序的轉換,效率更高.基于高性能計算領域對并行程序的迫切需求以及并行化編譯的巨大應用前景,大量的研究人員開始對并行化編譯技術進行研究,并行化編譯成為當前高性能計算領域的一個研究熱點.但是由于并行化編譯技術本身的復雜性,目前并行化編譯得到的并行程序與手工編寫的相比,運行效率仍有較大差距.

目前,在面向眾核結構的并行化編譯領域,大多數的研究工作是面向GPU平臺的.比如,Lee等人在文獻[10]中實現了一個“源-源”的把面向共享存儲結構的OpenMP程序轉換成GPGPU程序的自動轉換和優化框架,能夠將已有的OpenMP程序移植到GPU眾核平臺.在文獻[11]中又將其擴展為OpenMPC框架,通過添加指導語句和使用環境變量等方式實現了更多的性能優化.Han等人[12]提出了一種基于指導語句的高級語言hi CUDA,并利用“源-源”編譯技術為用戶提供了一種完成一般應用程序到CUDA程序轉換的方式.Baskaran等人[13]實現了一種通用串行 C程序直接轉換為 CUDA程序的自動轉換系統,與之類似,本文實現的也是一個將串行的 C和Fortran程序直接轉換為異構眾核程序的編譯框架.針對Intel Phi協處理器典型的研究工作是Ravi等人提出的優化編譯器 Apricot[14],能夠將已有的 OpenMP程序和串行程序轉換為適合 MIC結構的 LEO(language extensions for offload)程序,并使用了多種訪存及數據傳輸優化方法以及一個運行時代價模型來進一步優化性能.目前已有的針對異構處理器的研究大多是基于 Cell處理器的.Eichenberger等人[15]為 Cell處理器設計的Octopiler編譯器實現了Cell處理器代碼的自動生成,并包括線程級并行、自動向量化等多種優化.王淼等人[16]針對 Cell處理器提出了一個異構多核編譯框架,該框架通過執行數據對齊、數據分布、計算分布等操作,將數據并行程序直接映射到Cell處理器上.

為了緩解在我國自主設計的異構眾核處理器 SW26010上遇到的編程難的問題,本文設計實現了一個面向異構眾核處理器體系結構的并行化編譯框架.該并行化框架基于開源的 Open64[17]編譯器開發,采用“源-源”的方式將C和Fortran程序轉換為SW26010上運行的Sunway OpenACC異構并行程序.該框架主要包括4個模塊:任務劃分模塊用來識別適合進行加速計算的程序段,在該模塊中首次提出了嵌套循環的多維并行的識別方法；數據布局模塊完成數據在主存和SPM之間的布局,該模塊將指針范圍分析的方法應用到異構眾核處理器的數據布局中,并提出了一種需求驅動的指針范圍分析方法；傳輸優化模塊針對SW26010處理器的結構特征實現了數據傳輸合并、傳輸外提、打包傳輸、數組轉置等多種數據傳輸優化方法；收益評估模塊通過構建面向SW26010處理器的代價模型,實現了一種將編譯時靜態獲取的信息與程序運行時得到的信息相結合的動靜結合的收益評估方法.本文的主要貢獻包括:(1) 設計和實現了一個面向SW26010處理器的并行化編譯框架,該框架的創新性工作有:提出了嵌套循環的多維并行識別方法、面向異構眾核結構數據布局的需求驅動的指針范圍分析方法和一種動靜結合的收益評估方法,以及多種針對SW26010特性的數據傳輸優化方法；(2) 為Open64編譯器提供了一個OpenACC代碼生成模塊,使其能夠生成適于異構系統上的并行代碼；(3) 為設計實現面向異構眾核處理器的并行編譯框架提供了一種可行的參考方案.

本文第1節介紹我們的研究的目標平臺SW26010處理器及其使用的編程模型.第2節總體說明本文提出的并行編譯框架.第3節～第6節詳細介紹任務劃分、數據布局、傳輸優化和收益評估模塊的實現.第7節為實驗測試與結果分析.第8節對本文進行總結.

1 研究基礎

1.1 目標平臺

本文的研究基于國產SW26010處理器,SW26010是面向高性能計算領域開發的處理器,其結構如圖1所示,芯片主要由4個核組(group)、片上互聯網絡(network on chip,簡稱NoC)和系統接口(system interface,簡稱SI)組成[18].單個核組內采用異構眾核結構,包括1個管理核心MPE(management processing element)、1個運算核心簇CPE cluster(computing processing elements cluster)和存儲控制器MC(memory controller).運算核心簇則包含64個運算核心,采用拓撲為8×8的簇通信網絡進行連接.管理核心是功能完整的64位RISC核心,支持32/64位整數運算、單/雙精度浮點運算和原子操作,可以高效處理程序的串行段,并完成計算資源和功耗的管理,提供監控、消息、文件、調試等服務.運算核心也是64位RISC結構,其指令集在管理核心指令集的基礎上進行了精簡,并針對運算核心結構特征增加了通道操作、寄存器通信、行列同步等特殊指令.

SW26010的核組是進行計算資源管理的基本單位.單個核組的存儲系統結構如圖2所示[18],管理核心擁有L1和L2兩級硬件Cache,運算核心則支持軟件管理的SPM.同時,管理核心和運算核心還共享片外主存.運算核心的SPM與主存統一編址,管理核心和運算核心都可以通過訪存指令訪問SPM和主存,還可以通過DMA命令實現 SPM 和主存之間的批量數據傳輸.但是,處理器核訪問不同存儲器的延遲有很大差別,運算核心訪問 SPM的延遲遠低于訪問主存的延遲,而由于芯片面積及功耗的限制導致 SPM 的空間有限.在實際應用中,充分利用訪問時延短的SPM才能充分發揮SW26010處理器的性能優勢.

Fig.1 SW26010 processor structure diagram圖1 SW26010處理器結構圖

Fig.2 SW26010 memory hierarchy of each group圖2 SW26010單核組存儲系統結構圖

1.2 編程模型

SW26010處理器4個核組之間的并行,既可以使用OpenMP,也可以使用MPI實現；單個核組內管理核心和運算核心簇之間的并行則通過Sunway OpenACC實現[18].Sunway OpenACC是在OpenACC標準[19]的基礎上針對 SW26010處理器的結構特性作了一些擴展.OpenACC是一個針對加速設備的異構編程模型標準,通過編譯指示將指定的程序段加載到加速設備上執行,程序的其他部分仍然在主處理上執行.Sunway OpenACC對OpenACC的擴展主要有:針對零散數據傳輸的數據打包拷貝、針對不連續訪存的數據轉置拷貝等.

在“太湖之光”計算機上開發和移植程序,一個主要的工作就是添加Sunway OpenACC指示,實現程序在運算核心上的并行執行.Sunway OpenACC程序要想獲得好的性能,需要仔細分析哪些循環適合在運算核心上運行,還需要根據程序特征和處理器特性對程序的數據傳輸等作深入優化.本文的研究工作即是在編譯器中通過程序分析,自動添加Sunway OpenACC指示.本文編譯框架通過“源-源”方式生成的Sunway OpenACC程序,還需要經過 Sunway OpenACC編譯工具的二次編譯.本文的編譯框架判斷哪些代碼適合加載到運算核心進行加速計算,以及哪些數據是運算核心加速計算時需要的,而Sunway OpenACC編譯工具則完成異構代碼的生成,以及數據在存儲系統中的分布.

2 并行編譯框架

本文的并行編譯框架用來開發應用程序在 SW26010處理器單個核組內運行的并行性,通過在原始程序中自動插入Sunway OpenACC編譯指示,將串行程序轉換為異構并行程序.該框架基于開源編譯器Open64實現,以C和Fortran程序作為輸入,以Sunway OpenACC并行程序作為輸出,主要包括任務劃分、數據布局、傳輸優化、收益分析模塊,如圖3所示.

并行化編譯之前首先需要對程序進行預優化,預優化包括常量傳播、歸納變量替換、死代碼消除、循環正規化等簡單優化,為后續的分析和優化作準備,本框架使用了 Open64中原有的預優化方法.任務劃分模塊用來識別適合在運算核心上進行加速的程序段,通常是計算量足夠且可以并行執行的循環.數據布局模塊根據數據流分析的結果,分析在運算核心上進行加速計算時哪些數據是運算核心需要的.傳輸優化模塊則對數據在主存和SPM之間的傳輸過程進行優化,盡可能地減少不必要的數據傳輸和提高傳輸效率.在運算核心上并行執行程序需要一定的啟動和數據傳輸等開銷,并不是所有的循環并行執行都能獲得收益,所以需要收益評估模塊進行收益分析,避免計算量太小無法獲得收益的循環被加載到運算核心上執行.“源-源”翻譯過程則將編譯器中間語言表示形式轉換為高級語言源程序,Open64中有一個實驗性的“源-源”翻譯模塊,本文框架在其基礎上開發了用于生成Sunway OpenACC并行程序的“源-源”翻譯模塊,并做了大量的優化和BUG修復工作,使其能夠正確翻譯大型程序.目前“源-源”翻譯模塊僅支持C和Fortran77程序.

Fig.3 Parallel compilation framework圖3 并行編譯框架圖

本文是一個“源-源”的編譯框架,輸出的是添加了Sunway OpenACC編譯指示的C和Fortran程序,本文框架并不直接完成計算劃分和數據分布,而是在程序中加入指導計算劃分和數據分布的編譯指示,指導 Sunway OpenACC編譯工具在二次編譯時生成計算劃分和數據分布代碼.

3 任務劃分

SW26010處理器的性能優勢主要來自于數量眾多的精簡運算核心.任務劃分模塊用來識別適合在運算核心上進行加速的程序段,并在中間表示中插入相應的指示.適合在運算核心上運行的程序段,通常是計算量較大且可以并行執行的循環.Open64編譯器能夠自動生成OpenMP并行程序,在LNO(loop nest optimizer)階段已有一個能力較強的并行循環識別模塊[20].Open64的并行識別方法是一種一維并行識別方法,用于眾核處理器時存在一定不足,當選擇的并行維迭代數較少時可能導致嚴重的負載不均衡.圖 4(a)所示的矩陣乘法核心代碼通過Open64原有的并行識別階段后生成的并行代碼如圖4(b)所示,這里,矩陣的規模為32,并行層i層只有32次迭代,在擁有64個運算核心的SW26010處理器上運行時無法做到負載均衡,會使部分運算核心處于空閑狀態.

Fig.4 Multi dimension parallelization of nested loop example圖4 嵌套循環多維并行示例

針對這一問題,本文在Open64已有并行識別方法的基礎上提出了一種多維并行識別方法,在現有并行識別方法無法做到較好的負載均衡時,選擇嵌套循環的多個維進行并行,將多個并行維的迭代空間合并后再做任務劃分,減少負載不均衡對程序并行效率的影響.現有的解決這一問題的方法主要有兩種:一種是通過循環交換把迭代量大的可以并行的維交換到外層,這種方法的缺點是循環交換可能影響數據局部性,而且使用的范圍受限,可能嵌套循環的各個維迭代數都比較少,這時循環交換無法解決問題；另一種是直接對循環的多個維進行合并以便有足夠的迭代數,這種方法與本文提出的多維并行在本質上是類似的,但是需要對循環進行合并變換,較為激進,可能對后續優化產生較大影響.本文是目前最早在并行識別階段直接將循環的多個維識別為并行的方法,有別于以往通過循環交換或者合并后仍然進行單層并行識別的方法.

在手工編寫的并行程序中,多維并行的思想已有很多的應用.典型的例子是 OpenMP、OpenACC等基于編譯指示的并行編程模型中使用的collapse指示.OpenMP和OpenACC中的collapse指示在語法和功能上基本相同,都是作為loop指示的子句,用來指定有多少層緊嵌套循環與loop指示相關聯,這些循環的迭代空間將被合并后做任務劃分,本質上即是多維并行.如圖4(c)所示,代碼即表示將i、j兩層循環合并后并行執行,此時進行并行任務劃分的迭代空間變成了32×32,在SW26010上運行時則可以有較好的負載均衡.

任務劃分模塊的主要貢獻是在Open64單維并行識別算法的基礎上首次實現了嵌套循環的多維并行識別.在進行并行識別前,會對循環次序按照程序局部性最優的原則進行排序,即訪存跨步小的層位于內層.在實現嵌套循環多維并行時需要解決的兩個關鍵問題是:第一,什么情況需要進行多維并行；第二,滿足什么條件的多個循環層能夠進行多維并行.針對第 1個問題,需要進行多維并行識別的條件是當前識別的并行循環的迭代次數小于運算核心數目的4倍(即小于256),并且迭代次數不能被64整除,這通常意味著沒有好的負載均衡.這里遵循了一個基本假設,即不同迭代的計算量是相當的,這個假設在科學計算類程序中大多數時候是滿足的.在這個假設下,當迭代數能被核心數整除時,不會有負載不均衡的情況發生；當迭代數目較大時,這里設定為大于運算核心數的4倍,負載不均衡現象常也表現得不那么明顯.針對第2個問題,多維并行的多個循環層需要滿足每一維都可并行,且相互之間可置換.該嵌套循環多維并行識別算法具體描述如下.

算法.Parallel_LoopNest_Recognition(L,m).

該并行識別算法中第 1層循環用來遍歷循環的位置,優先識別外層的并行性,通常,外層并行有更大的并行粒度,效果更好；第2層循環遍歷循環的各個層,在當前位置優先并行訪存跨步大的層,以便內層循環的訪存有更好的數據局部性；第3層在需要進行多維并行時,選定能夠多維并行的維.該算法的時間復雜度為o(n3),n為嵌套循環層數.在編譯系統中實現多維并行的自動識別,優勢在于編譯工具能夠結合循環交換選擇更有利于數據局部性的層進行并行,以及能夠通過多種程序變換將部分非完美嵌套循環轉換為完美嵌套循環,增加程序中多維并行的比例.

4 數據布局

運算核心訪問SPM的延遲遠小于訪問主存的延遲,所以在利用運算核心進行加速計算時,將所需數據在計算開始前使用DMA方式批量傳輸到SPM中能夠顯著提高程序的運行效率.對每一段要加載到運算核心上并行執行的代碼,數據布局模塊根據數據流分析的結果,判斷哪些數據在計算開始前需要從主存復制到SPM,哪些數據在計算結束后需要從SPM復制回主存,并在生成相應的數據傳輸指示.

Open64的 LNO階段會對每個循環進行局部數據流分析,將循環中引用的數據根據定義-使用關系劃分為def、use、pri等集合.def集合表示在循環內重新定義變量的集合,在循環內的定義消除了變量的原有定義.use集合表示在循環中使用變量的集合,這些變量是向上暴露的.pri集合表示在循環內定義并且只在循環內使用的變量的集合.需要說明的是,這些集合的交集并非總是為空,即一些變量可能在多個集合中出現.Open64中的上述信息封裝在 ARA_LOOP_INFO類中,其 OpenMP自動并行化階段即是根據這些信息判斷變量的屬性為shared還是 private.本框架同樣也是根據這些信息判斷哪些數據是運算核心需要的,并生成 copy、copyin、copyout和create等數據子句.本框架判斷的方法如下:屬于pri集合的變量使用create子句；屬于use集合中的變量使用copyin子句；屬于def但是不屬于pri集合的變量使用copyout子句；同時,將在copyin和copyout子句中的變量替換為copy子句.

Sunway OpenACC編譯工具根據數據復制子句決定數據在存儲系統的分布以及生成傳輸數據的DMA命令.但數據傳輸過程需要較大的開銷,而且運算核心的 SPM 空間有限,所以在生成數據子句時需要精確計算傳輸數據的范圍,避免冗余數據的傳輸.數據管理模塊使用了數組邊界分析和指針范圍分析來確定數組和指針數據的起始和結束位置.

4.1 數組邊界分析

計算數組傳輸范圍最簡單的方法是根據數組的定義獲得整個數組的大小,將其全部傳輸到 SPM.但是這樣可能導致冗余數據的傳輸,增加數據傳輸的開銷和降低 SPM 的利用率.因此,對在并行區使用的數組進行邊界分析能夠有效避免冗余數據的傳輸.Open64在 LNO階段使用了一種基于區域分析的數組訪問分析方法,將數組元素劃分為不同的區域,每個區域是一個用凸多邊形表示的訪問集合,凸多邊形則是由從數組元素邊界信息得到的簡化線性方程組表示的.這些信息保存在Open64的ARA_REF結構中.在ARA_REF結構中可以方便地取到數組訪問的下標線性表達式,將循環的上下界信息帶入下標表達式即可得到數組訪問的邊界信息.

圖5所示為數組邊界分析示例.

圖5(a)所示代碼為原始代碼；

圖5(b)所示為根據ARA_REF中信息得到的A數組下標線性表達式,以及計算得到的A數組下標邊界；

圖5(c)所示為根據數組邊界信息生成的并行代碼(B數組的分析過程與A數組相同).

目前的數組邊界分析方法僅能分析線性數組下標.

Fig.5 Array boundary analysis example圖5 數組邊界分析示例

4.2 指針范圍分析

OpenACC中數據復制子句的參數也可以是用指針聲明的動態數組.對循環引用的指針變量的范圍進行分析,而不是簡單地使用動態申請的空間大小,也是減少冗余通信和節省 SPM 空間的重要手段.指針范圍分析多用于安全分析、BUG檢測和硬件綜合等方向[21],本框架將指針范圍分析的方法用于異構眾核處理器的數據布局,并提出了一種需求驅動的指針范圍分析方法.

圖6所示為指針范圍分析的代碼示例,圖6(a)所示代碼為原始代碼；圖6(b)所示為指針范圍分析過程；圖6(c)所示為根據指針范圍信息生成的并行代碼.圖6(b)所示分析過程采用范圍描述符域(descriptor-offset domain)[22]進行符號范圍表示,在每條語句后,給出了整型變量i、k和指針變量p、q范圍分析的結果,分析過程使用了前向數據流分析.其中,范圍描述符域p→〈x:τ[σ],[min,max]〉表示指針p的指向為數組x,x為元素類型為τ、大小為σ的數組,偏移范圍為[min,max],即:指針p指向內存空間的范圍從x+min×sizeof(τ)到x+max×sizeof(τ).特別地,如果x:τ[σ]為null,則表示p為整數,取值范圍為[min,max].在 if-else分支交匯處,需要對符號范圍進行合并,取兩者范圍的并集.

Fig.6 Pointer range analysis example圖6 指針范圍分析代碼示例

傳統的數據流分析技術通常是在控制流圖上進行迭代,更新每個程序點的信息直至到達定點.指針分析是數據流分析的一種,本框架的指針范圍分析也采用經典的數據流分析方式,并針對面向異構眾核處理器并行化編譯的需求,在精度和效率之間加以折中,是一種需求驅動的方法.本框架提出的需求驅動的指針范圍分析方法的主要步驟如下.

(1) 收集待分析循環的指針變量引用點,并構造待分析符號變量集合RPset；

(2) 根據 RPset構建循環的初始需求驅動控制流圖 DCFG,DCFG中僅包含對待分析符號變量有副作用的語句；

(3) 在初始DFCG上按照拓撲后續依次分析,并不斷加入待分析的符號變量存在的控制依賴和數據依賴對應的節點和邊,當所有可達節點依次加入到該流圖后,針對該循環的DCFG構建完畢；

(4) 在構造的需求驅動控制流圖上進行迭代數據流分析,當某個節點的變量存在控制范圍約束時,對控制范圍和數據范圍信息進行合并.

5 傳輸優化

在任務劃分和數據布局完成后就可以得到能夠在 SW26010處理器上運行的異構并行程序,但是要想獲得更好的性能,還需要對主存和 SPM 之間數據的傳輸進行優化,盡量減少不必要的數據傳輸和提高傳輸效率.在實際應用中,不當的數據傳輸往往是影響程序性能的關鍵因素.本節提出的面向SW26010處理器結構特征的數據傳輸優化方法有數據傳輸外提、數據傳輸合并、離散傳輸聚合和數組轉置等.

5.1 數據傳輸合并

在實際程序中,兩個相鄰的并行區使用相同數據的情況是很常見的.在這種情況下,每個并行區的開始和結尾都進行數據復制的方式往往能夠找到優化的機會.如圖7(a)所示為jacobi迭代核心的OpenACC并行程序,在這段代碼中有兩個相鄰的parallel并行區,第 1個并行區的結尾需要將數組 Anew從 SPM復制回主存,而第 2個并行區的開始處又需要將數組Anew復制到SPM.如果在這兩個并行區計算過程中把數組Anew一直都存放在SPM中,則可以減少數組Anew的一次拷出和一次拷入操作.要實現這個目的,一種可行的方法是將這兩個并行區的數據傳輸進行合并,只在第1個并行區的開始和第2個并行區的結尾傳輸數據,即如圖7(b)所示的代碼.

Fig.7 Example of merging and hoisting transmission圖7 數據傳輸合并及外提示例

數據傳輸合并面臨的第 1個問題是什么情況下進行合并是有利的?如果兩個并行區使用的數據不同,則數據傳輸的合并會使得傳輸的數據量增大,占用更多的 SPM 存儲空間,這可能影響程序的執行效率.考慮到有利性,本框架只對兩種情況進行數據傳輸合并:一種情況是兩個連續并行區使用的數組變量完全相同；另一種情況是兩個并行區使用的數據總量不超過SPM空間大小.數據傳輸合并需要解決的第2個問題是什么情況下合并是安全的,即不會引起程序運行錯誤?如果在兩個并行區之間,有 MPE端的代碼對兩個并行區共同使用數據的引用,則數據傳輸合并可能導致程序運行錯誤.所以在進行數據傳輸合并時,必須保證前一個并行區的 copyout子句和后一個并行區的copyin子句共有的變量,在兩個并行區之間的MPE端代碼中沒有對其的引用.在滿足有利性和安全性的前提下,數據傳輸合并的過程則較為簡單:用OpenACC的data指示創建一個數據區,包含需要合并的并行區,并根據待合并并行區的數據子句生成data指示的數據子句,然后刪除并行區的parallel指示的數據子句.

5.2 數據傳輸外提

圖7(b)所示進行數據傳輸合并后的代碼,數據區位于外層的while循環內,while循環的每次執行都會進行數據傳輸.如果把數據區移到循環外,如圖7(c)所示,則在整個外層while循環的執行過程中只在循環計算開始和結束后進行數據傳輸,可以極大地減少數據傳輸的開銷,程序執行效率會有大幅提升.

針對外層串行內層并行的嵌套循環,本框架使用數據傳輸外提將嵌套循環內層被多次執行的數據區代碼轉移到嵌套循環外,減少數據傳輸次數.數據傳輸外提采用自底向上的分析過程,當數據區包含在循環內部,且數據區滿足以下兩個條件時進行外提:第一,數據區中數據復制子句復制數據的范圍在外層循環執行過程中是不變的,即外層循環的每次執行都復制同樣的數據；第二,數據區傳輸的變量在外層循環除數據區以外的代碼中沒有引用,即這些變量只在數據區內使用,一直保留在 SPM 內不會影響外層循環內其他代碼段的執行,也不會受其他代碼段的影響.重復執行以上外提過程,直至不滿足外提條件或數據區外層沒有循環為止.

5.3 數據打包傳輸

在數據傳輸過程中,DMA命令緩沖有限,零散數據的多次傳輸會占用DMA命令緩沖,也會增加DMA多次啟動的開銷,進而降低數據的傳輸效率.因此,把零散變量打包成一個大的變量進行傳輸,可以減少數據傳輸次數,降低開銷.Sunway OpenACC在標準OpenACC的基礎上增加了數據打包子句pack/packin/packout,用來實現零散變量打包之后的傳輸.數組打包子句的格式和使用方式與數據復制子句相同,其含義如下.

(1) pack子句:先對參數列表中的數據進行打包,然后操作步驟同copy子句,之后進行解包；

(2) packin子句:先對參數列表中的數據進行打包,之后操作步驟同copyin子句；

(3) packout子句:前部分操作同copyout,之后對數據進行解包.

圖8所示即為一個數據打包的示例,將標量x、y、z以及數組coef打包為一個大的變量,通過一次數據復制傳輸到SPM,減少了數據復制的次數,能夠提高傳輸效率.

Fig.8 Example of packaging transmission圖8 數據打包傳輸示例

但在數據打包時需要在主存中申請存放打包后數據的空間,并且打包過程還需要一些時間開銷.所以,使用數據打包傳輸優化的關鍵問題是確定哪些數據的打包傳輸能夠帶來收益?對于標量,其打包過程需要的內存及其他開銷較小,認為其打包傳輸總是有收益的.對于數組,根據經驗,當數組的數據量小于DMA的帶寬(DMA通道一個時鐘周期傳輸的數據量)時,打包傳輸是有收益的.數據打包傳輸的分析過程較為簡單,依次對數據復制子句中的變量進行分析:對于標量,直接將其放入數據打包子句；對于數組,計算其數據量大小,如果小于DMA帶寬,則放入數據打包子句.

5.4 數組轉置

對訪存不連續的數組進行復制,會使編譯器生成帶跨步的 DMA傳輸命令,其性能相對較差.Sunway OpenACC在標準OpenACC的基礎上增加了數組轉置子句swap/swapin/swapout.數組轉置子句的格式為

swap/swapin/swapout(數組名(dim order:…),…)

數組轉置子句的使用方式與數據復制子句相同,其含義如下.

(1) swap子句:先對數組按照dim order進行轉置,然后操作步驟同copy子句,之后再轉置回原數組；

(2) swapin子句:先對數組按照dim order進行轉置,然后操作步驟同copyin子句；

(3) swapout子句:先把程序中的數組訪問替換成對轉置后數組的訪問,然后操作同 copyout,之后再對數組按照dim order進行轉置.

在圖9(a)所示的代碼段中,最內層循環k的下標出現在FDV數組的最高維,也就是說,對FDV的訪問是不連續的,使用 copyin(FDV)子句則會生成帶跨步的 DMA 命令,數據傳輸效率較低.如圖 9(b)所示代碼,使用swapin(dim order:2,1,3)替換copyin(FDV),對數組FDV進行轉置,轉置后數組的維度順序為(2,1,3),這使得數組存儲順序與訪問順序一致.數組轉置后,一方面可以使用連續的DMA命令替換帶跨步的DMA命令傳輸數據,提高了數據傳輸的效率；另一方面,在運算核心端連續的訪存也會提高訪存效率.但需要注意的是,數組轉置功能需要在主存中申請存放轉置后數組的空間,并且轉置過程需要一定的開銷.

Fig.9 Exampe of array transpose圖9 數組轉置代碼示例

數組轉置優化的分析過程為:依次分析數據復制子句中的數組,當循環中數組的下標索引次序和循環嵌套迭代次序不一致時,即要按循環嵌套的迭代順序對數組進行轉置,則生成相應的數組轉置子句,將該數組放入數組轉置子句中.轉置的維度順序按照如下方法分析:首先對復制子句中的數組的下標索引變量從低維到高維依次存到數組ref_order中(訪存跨步小的為低維),再將循環嵌套索引變量從外層到內層依次存到數組loop_order中,然后從最后一個元素,即最內層循環索引開始遍歷,查找其在數組中的編號,存到數組swap_order中,若swap_order與ref_order不一致,說明數組需要轉置,并將swap_order作為數組轉置時的維度順序.

6 收益評估

將循環加載到運算核心上運行需要一定的啟動和數據傳輸等開銷,所以需要通過收益評估來判斷循環的并行執行是否能帶來收益.目前,收益分析主要有兩種方法:一種是通過構建代價模型[23],評估串行執行和并行執行的時間開銷,確定是否有收益；另一種是使用機器學習的方法[24],基于已有的經驗,根據循環的迭代次數、循環體大小等程序信息判斷是否有收益.代價模型是一種編譯器中普遍使用的用來判斷各種程序優化是否有收益的方法,比如GCC、LLVM、Open64等優秀編譯器都使用了代價模型.用機器學習的方法進行收益評估是一種比較新的方法,但是由于需要構建學習模型,進行大量訓練,而且基于經驗的預測存在判斷失誤的情況,目前在產品級編譯器中較少使用該方法.本框架選擇代價模型進行收益評估,通過比較循環在單個管理核心上的串行執行代價和在運算核心簇上的并行執行代價,決定是否將循環加載到運算核心上運行.

Ravi等人針對Intel Phi協處理器提出的優化編譯器Apricot[14]中使用了一個簡單的代價模型來優化性能,該代價模型主要通過循環迭代次數、CPU操作數、訪存操作數以及 CPU操作和訪存操作占總操作數的比例等與經驗值進行比較來評估收益.Grosser等人[25]開發了一個Polly-ACC編譯框架,將通用程序移植到異構結構上,其中使用了一個簡單的代價模型,也是通過一些條件判斷來篩選適合在加速器上進行加速計算的代碼段.在這些面向眾核結構的并行化系統中,使用的代價模型較為簡單,在開發產品級編譯系統時無法滿足實際需求.Open64編譯器中包含了一個層次化代價模型,用于對程序中的循環代價進行評估[23].與本文工作最為接近的是黃品豐等人[26]在 Open64代價模型的基礎上所做的面向 Cell處理器的代價模型,本文借鑒了其基本思路,將其擴展為面向核數更多的SW26010處理器的代價模型.

本節首先構建面向 SW26010處理器的準確的代價模型,再在代價模型的基礎上實現了一種動靜結合的并行收益評估方法.對于循環信息在編譯時可全部獲取的情況,在編譯時即可根據并行代價模型靜態確定是否有收益；對于循環信息在編譯時無法全部獲取的情況(比如循環邊界根據程序輸入確定),生成 if子句,根據編譯時靜態收集的信息和運行時動態得到的信息,在運行時確定是否將該循環加載到運算核心并行執行.

6.1 代價模型的建立

代價模型通常由一組底層模型組成,反映了應用程序在計算機系統上的具體執行細節,并且使用執行開銷(一般是時間)對程序的執行效率進行評估.許多編譯器和運行庫中都包含有代價模型,用于評估編譯器中的程序變換,指導編譯優化的過程.Open64編譯器的 LNO中包含了一組代價模型[27],用于對程序中的 SNL(singly nested loop)循環代價進行評估,如圖 10所示.Open64中的循環代價模型包括了串行模型和并行模型兩個子模型,分別用來評估程序在單個處理器上串行執行的開銷和在多個處理器上使用OpenMP的fork-join模式多線程并行執行的開銷.每個子模型的開銷可以進一步分為粒度更細的開銷類型,并且分別建模.其中,串行執行開銷依賴于與處理器、存儲相關的開銷；并行執行開銷則在串行開銷的基礎上還要考慮并行所帶來的額外開銷,主要是并行啟動開銷和線程同步開銷.

Fig.10 The structure of cost model in Open64圖10 Open64中的代價模型框圖

構建面向 SW26010處理器的代價模型也需要構建兩個子代價模型,分別是程序在單個管理核心上運行時的串行模型和在運算核心簇上運行時的并行模型.管理核心的結構,以及程序在管理核心上的運行方式與通用X86處理器類似,所以串行代價模型可以借鑒Open64已有的串行模型.而程序在運算核心簇上并行執行的方式與在多核上的OpenMP并行執行方式有較大不同,而且運算核心沒有傳統的硬件Cache,所以并行模型需要重新構建.

6.1.1 串行模型

循環串行執行時間是評估循環并行收益的基準.在SW26010處理器上,循環串行執行開銷是指循環在管理核心上的運行的時鐘周期數,主要包含處理器開銷、存儲訪問開銷,可用公式(1)表示.

(1) 處理器開銷

處理器開銷Tprocessor是指在忽略Cache和TLB不命中等訪存開銷的情況下,循環指令在處理器上執行的開銷.在編譯過程中,可以通過分析循環的中間表示語法樹獲得循環語句(包括循環頭和循環體)中各類指令的數目,并根據各類指令的執行周期數,通過累加得到循環一次迭代的運行時間Tmachine_per_iter,然后通過與循環迭代次數Nloop_iter相乘就能得到循環的處理器開銷,如公式(2)所示.

指令的執行周期可以通過查閱處理器資料獲得.循環迭代次數Nloop_iter的獲取則需要根據程序的具體情況來定,有些循環的上下界為常數或常數表達式,可以在編譯時就靜態分析得到；而有些循環的循環上下界則取決于程序輸入,只能在運行時得到,這時將循環迭代次數用變量代替,將處理器開銷表示為循環迭代次數的函數.

(2) 訪存開銷

訪存開銷Tmemory是指一級數據Cache不命中情況下的數據訪問開銷,與循環的數據局部性以及Cache行大小及Cache失效開銷緊密關聯.編譯過程可以通過分析循環的數據訪問特征以及Cache行大小和Cache配置策略來預測Cache失效次數.在計算Cache失效次數時,考慮到空間局部性,對相鄰數組元素的訪問只計算1次失效.SW26010處理器上管理核心擁有兩級數據 Cache,因此存儲訪問開銷為數據在一級 Cache失效二級 Cache命中,以及兩級Cache都失效的情況下的訪存開銷.如公式(3)所示,TL2為一級Cache失效二級Cache命中情況下的訪問開銷,Tmain_mem為兩級Cache都失效情況下直接訪問主存的開銷,NL2為二級Cache命中次數,Nmain_mem為主存訪問次數,兩者之和為一級 Cache失效次數.TL2和Tmain_mem可通過簡單測試得到.其中,TL2和Tmain_mem可通過簡單測試得到,NL2和Nmain_mem可通過程序分析進行預測.

6.1.2 并行模型

循環在 SW26010處理器上的并行執行過程為:首先,加載程序段和傳輸數據到運算核心；然后,由運算核心完成計算；最后,把計算結果返回主存.根據程序在 SW26010上的運行方式,可以將并行代價分解為并行控制開銷、數據傳輸開銷和并行計算開銷,用公式表示為

(1) 并行控制開銷

并行控制開銷主要是并行執行時的啟動和管理開銷,包括初始化并行計算環境、創建加速線程組、加載工作任務到運算核心并啟動任務執行等的開銷.并行控制開銷Tpara_overhead可以表示為公式(5),是啟動的運算核心數p的線性函數.其中,Tc為并行啟動開銷,Tp為單個運算核心的并行管理開銷.Tc、Tp可通過運行簡單循環進行測定.

(2) 數據傳輸開銷

數據傳輸開銷主要取決于兩個方面:傳輸的數據量；DMA的數據傳輸帶寬.在處理器總線帶寬一定的情況下,傳輸的數據量決定了傳輸的開銷.通過分析數據傳輸子句,就能得到傳輸的數據量.數據傳輸開銷Tdata_trans可用公式(6)表示.其中,Ts為 DMA操作的初始化時間,To為數據的數據傳輸過程中所做的數據打包和轉置的開銷,in和out分別為計算開始前從主存拷入SPM和計算結束后從SPM拷回主存的數據集合,x、y分別為in和out集合中的元素,x.size和y.size為它們占用的存儲空間大小,w為DMA通道數據傳輸帶寬,其中,Ts可以通過構造測試程序測試得到.數據打包和轉置實際上是管理核心上執行的操作,所以,To可以通過調用串行模型得到.

(3) 并行計算開銷

并行計算開銷實際上是循環在多個運算核心上運行時,從第 1個運算核心開始執行到最后一個運算核心執行結束的時間.由于運行時的不確定性,這個值無法在編譯時準確預測,這里使用循環在單個運算核心上的運行時間除以計算所用核心數的值近似表示.單個運算核心上運行開銷的計算過程與管理核心類似,但是由于運算核心的結構和性能與管理核心不同,各部分消耗的計算方法有所不同.并行計算開銷Tcompute可以用公式(7)表示.T′processor、T′memory分別為運算核心的處理器開銷和訪存開銷.

T′processor的計算過程和在管理核心上Tprocessor的計算過程相同,只需將各類指令的執行周期替換為管理核心的指令周期,管理核心指令周期數也可以通過查閱系統手冊得到.因為運算核心沒有硬件 Cache,只有軟件管理的SPM,所以T′memory的計算方式有所不同,計算過程如公式(8)所示.

其中,Tspm為SPM訪問延遲,Nspm為SPM訪問次數,Tmem為運算核心訪問主存延遲,Nmem為訪問主存次數.Nspm和Nmem可以通過程序分析得到,加速循環中訪問的數據如果是在數據復制子句copy/copyin/copyout和create子句中,則在訪問時數據在SPM中,否則,加速循環訪問的數據則需要從主存中取得.

目前,本文給出的并行編譯框架只能處理器迭代間無依賴的DOALL循環,無需考慮進行核間通信開銷.

6.2 收益評估方法

在代價模型的基礎上,就可以通過比較程序串行執行的代價和并行執行的代價來判斷循環的并行執行是否能夠帶來收益,公式(9)即為判斷循環并行是否有收益的標準.

對于循環信息在編譯時可全部獲取的情況,在編譯時即可根據公式(9)靜態確定是否有收益.然而,對于循環信息在編譯時無法全部獲取的情況,比如循環邊界根據程序輸入確定,編譯時無法判斷循環并行是否有收益,本框架提出了一種將編譯時靜態得到的信息與運行時動態獲得的信息相結合的動靜結合的收益評估方法.如圖11(a)所示為SPEC CPU2006[28]中程序462.libquantum中的一個熱點循環,該循環的上界reg→size是通過函數參數reg傳入的,無法在編譯時確定其值.在一個極端的情況下,循環被調用多次,而不同調用的循環邊界有所不同,這樣可能會有一部分調用并行執行有收益,而另一部分調用并行執行無收益甚至嚴重影響程序執行效率.對于這種情況,無論編譯時保守地選擇不并行,還是激進地選擇并行,都可能無法獲得好的效果.本框架對編譯時循環邊界未知的情況生成 if子句,根據編譯時靜態收集的信息和運行時動態得到的信息,在運行時確定是否將該循環并行執行.以圖11(a)中所示代碼為例,對該循環分別調用串行模型和并行模型,得到串行代價和并行代價分別為f(reg→x)和g(reg→x).利用公式(9)進行收益評估,當f(reg→x)＞g(reg→x)時,并行是有收益的,此時可以求得reg→x的臨界值X.于是我們生成if子句,如圖11(b)所示,在運行時根據re→x的值決定是否將該循環加載到運算核心.

Fig.11 Example of benifit estimate圖11 收益評估代碼示例

本文使用的編譯時靜態建模的方法雖然無法做到足夠精確,但在應用于并行化編譯系統時,只要考慮到精度上的不足,就能在實際應用時提升并行代碼的性能,所以,Open64、GCC、LLVM等很多優秀的編譯器中也都使用了代價模型作為收益評估的手段.

7 實驗測試

實驗測試部分包括優化效果測試和整體性能測試.優化效果測試通過選取一些典型的測試程序,對本文提出的多維并行、傳輸優化、收益評估等方法進行對比測試；整體性能測試則使用基準測試集和一些典型的科學計算程序,驗證本框架的整體效果.實驗平臺為“神威太湖之光”計算機系統,其計算節點為SW26010異構眾核處理器,并配備有完整的編譯工具鏈和性能分析工具.

7.1 優化效果測試

本文提出的多維并行、傳輸優化、收益評估等優化方法只對具備一定特征的程序有效,本節所選測試程序為符合相應特征的程序,比如多維并行測試部分選擇了嵌套層數較多的循環,傳輸優化測試選擇了數據傳輸較多的程序,收益評估測試則選擇了有大量較小并行循環的程序.這里對每種優化方法選擇了 4個典型的程序進行測試分析,測試程序主要來自于SPEC CPU 2006測試集、NPB3.3.1測試集、PGI OpenACC SDK和一些科學計算程序.

7.1.1 多維并行測試

本節對任務劃分模塊實現的嵌套循環多維并行的有效性進行測試,測試選擇了科學計算常用的矩陣乘法(規模為100×100)、PGI OpenACC SDK中的三維空間時域有限差分程序FDTD3d以及NPB3.3.1中的LU(B規模)和BT(B規模)4個程序.這4個程序中都存在多層嵌套循環,且外層循環迭代次數較少,容易導致負載不均衡,因此適合用本文提出的多維并行識別方法進行優化.測試過程對比了這 4個程序在使用單維并行以及本文實現的多維并行后程序的加速比,測試結果如圖12所示.

Fig.12 Comparison of speedup before and after multi dimension parallelization圖12 多維并行前后程序加速比對比圖

從圖12可以看出,本文實現的多維并行識別方法,能夠有效解決嵌套循環單維并行時并行層迭代次數較少導致的負載不均衡問題,有效地提升程序性能,這4個程序的加速比平均提升了1.49倍.

7.1.2 傳輸優化測試

本節對傳輸優化模塊提出的傳輸合并、傳輸外提、數據打包和數組轉置優化方法進行了測試分析.測試程序選擇了Jacobi迭代、一個科學計算程序飛行器繞流應用gkufs[29]、NPB3.3.1中的BT(B規模)以及SPEC CPU 2006中的410.bwaves(ref規模).這4個程序中有較多的并行區,且并行區的數據傳輸量較大,有較多數據傳輸優化的機會.通過測試每種優化方法之后程序運行時間的變化,驗證優化方法的有效性.圖 13(a)～圖 13(d)分別為Jacobi迭代、gkufs、BT和410.bwaves的測試結果,圖中給出了程序優化前的原始運行時間、每種優化之后的運行時間以及4種優化同時使用的整體時間.

在圖 13所示的測試結果中,由于程序特征不同,不同的優化方法對不同的程序優化效果也有所不同.比如傳輸合并和傳輸外提能夠較大地提升Jacobi迭代程序的性能；傳輸合并、數據打包和數組轉置3種方法對gkufs都有一定效果；而傳輸合并、傳輸外提和數組轉置對 410.bwaves有一定效果；傳輸合并和傳輸外提則對BT能夠取得較好的效果.本文提出的各種優化方法只適用于某一類程序特征,故測試結果中有些方法對某些程序沒有效果,而效果的好壞則主要取決于程序特征.數據傳輸優化后,Jacobi迭代整體上性能提升 3.91倍,gkufs整體上提升1.64倍,410.bwaves整體上提升1.15倍,BT整體上提升1.27倍.

Fig.13 Effect of transmission optimization method圖13 傳輸優化方法效果圖

7.1.3 收益評估測試

本節對收益評估模塊的有效性進行測試,測試用例選擇了 SPEC CPU 2006中的 462.libquantum和 436.cacatusADM,以及NPB3.3.1中的BT(B規模)和SP(B規模)4個程序,分別測試了這4個程序在進行收益評估前后并行循環的數量和程序獲得的加速比.這 4個程序有大量無收益的規模較小的并行循環,需要收益評估.表 1中的數據給出了進行收益評估前的并行循環數目以及收益評估后的并行循環數目.圖14給出了收益分析前后程序獲得加速比的對比情況.從表1和圖14的結果可知,本框架的收益評估模塊能夠有效地過濾計算量不足的循環,避免其加載到運算核心上導致程序性能下降,對程序性能提升效果明顯.其中,程序462.libquantum由于存在大量計算量較小的內層并行循環導致程序加載到運算核心上的運行時性能下降明顯,收益分析后能夠將計算量不足的循環過濾掉,程序加速比大幅提升27.27倍.

優化效果測試部分并沒有對數據布局模塊使用的數組邊界分析以及指針范圍分析方法進行測試.這里沒有對其進行測試主要是因為在標準測試集或者經過精心優化的成熟科學計算程序里,數組大小的定義以及指針變量內存空間的申請都是根據程序需要進行的,通常沒有進一步優化的空間.然而,在編譯框架的實際使用場景中,編譯的經常是沒有經過充分優化的程序,可能是一個新手程序員編寫的程序,也可能是一個程序初步的版本,在這樣的程序中申請了過大的內存空間是一種常見的現象.所以,這兩種優化方法在編譯框架的實際應用中是非常有用的,本文給出的編譯框架會在數組邊界分析和指針范圍分析后,將實際使用空間小于定義或申請空間大小的變量在輸出信息中進行提示,方便程序員檢查優化程序.

Table1 Comparison of the number of parallel loops before and after benifit estimate表1 收益評估前后并行循環數目對比結果

Fig.14 Comparison of speedup before and after benifit estimate圖14 收益分析前后程序加速比對比圖

7.2 整體性能測試

整體性能測試選擇了NPB3.3.1測試集和3個典型的科學計算程序進行測試與分析.NPB是用于測評大規模并行機和超級計算機的標準測試程序集.所選 3個科學計算程序分別為計算流體動力學程序 openCFD[30]、地震波模擬和反演程序3DWING[31]、飛行器繞流應用gkufs.

7.2.1 NPB測試分析

本節使用NPB3.3.1測試集(B規模)對本文框架的并行化效果進行測試與分析.圖15展示了NPB3.3.1測試集各個程序通過本文框架并行化后的運行時間相比于原始串行程序運行時間的加速比.NPB3.3.1測試集中的全部10個程序通過本文框架的并行化編譯在SW26010單個核組上運行時平均能夠獲得5.19的加速,其中加速比超過10的有CG和SP,而DC、EP和IS這3個程序則沒有獲得明顯的加速.這3個程序沒有獲得有效加速的原因分別為:DC的程序熱點中沒有循環,無法實現并行化；EP熱點循環中有較多函數調用,影響了依賴分析以及并行識別；IS熱點循環內有較多復雜的間接數組訪問,無法進行有效的依賴分析和并行識別.

各個異構眾核平臺結構差異較大,軟件系統不兼容,很難與其他平臺的研究成果直接進行對比.NPB3.3.1測試集提供了串行、OpenMP并行和MPI并行等多個版本,OpenMP與OpenACC有很多相似性,用OpenMP編譯指示標注的并行循環經過改寫一般也能成為OpenACC程序,所以我們將NPB3.3.1 OpenMP版本中標注的并行循環認為是手工并行的循環,作為與本文框架識別情況對比分析的對象.圖16則給出了NPB3.3.1測試集中各個程序手工并行的循環數目與本文框架自動識別出的并行循環數目的對比情況,這里所提自動并行的循環數是在關掉收益評估模塊后得到的.SW26010處理器的結構特殊,收益評估模塊過濾掉了較多計算量較小的循環,為真實反映本文框架的并行識別能力,測試自動識別的并行循環數時暫時關掉了收益分析模塊.可以看到,除了EP、IS和UA這3個程序,其他程序自動并行化識別出的并行循環數都多于手工并行.

NPB3.3.1中的程序根據并行識別情況可以將其分為4類:第1類,CG和SP兩個程序自動識別的并行循環數多于手工并行的,而且自動并行識別的并行循環基本上全部覆蓋手工并行,這兩個程序的自動并行的識別情況與手工并行基本一致；第2類,BT、LU和MG這3個程序自動識別的并行循環數目雖然多于手工,但原因是手工并行選擇了外層的循環,而自動并行由于程序主要循環過于復雜未能識別出外層的并行,而是識別出了大量內層循環,這3個程序自動并行的識別情況弱于手工并行；第3類,EP、IS和UA這3個程序,自動識別時未能將手工并行的循環識別出來,原因分別是EP主要循環有較多函數調用,IS循環內有復雜的間接數下標,UA的熱點循環程序復雜且有函數調用,自動并行目前無法很好地處理函數調用和間接數組下標等問題；第 4類,DC和FT兩個程序的情況較為特別,DC的程序熱點中沒有循環,而FT手工并行的版本對程序結構改動較大,不便于進行對比.整體來看,本文框架對 NPB3.3.1的自動并行識別與手工并行相比有較大差距,主要原因是編譯系統不能很好地處理函數調用引起的過程間問題和間接數組下標等非規則訪存問題,這也是目前編譯領域面臨的最為困難的問題中的兩個.

Fig.15 Parallization speedup of NPB3.3.1圖15 NPB3.3.1并行化加速比

Fig.16 Comparison of the number of parallel loops NPB3.3.1圖16 NPB3.3.1并行循環數目對比圖

7.2.2 科學計算程序測試分析

本節的測試選擇了 3個實際應用的科學計算程序作為測試用例,計算其加速比,并與手工編寫的并行程序進行對比,通過并行化效率反映編譯框架的能力.并行化效率則是指并行化編譯得到的自動并行程序獲得的加速比與程序員手工編寫的并行程序獲得的加速比的比值.表2給出了這 3個大型應用程序的測試結果.這3個程序都是MPI程序,節點數是運行程序使用的SW26010處理器計算節點(SW26010處理器一個核組為一個計算節點)的數目.為了方便測試和分析,程序測試時使用了較小的輸入規模.

Table 2 Test results of scientific computing program表2 科學計算程序并行化測試結果

由表 2可知,本文編譯能夠對大型的科學計算程序進行一定的加速,而加速效果取決于程序本身的并行性,其中,3DWING加速比達到32.33.這3個科學計算程序代碼量大、程序結構復雜,通過對這3個程序的測試,說明本文的并行編譯框架具有較好的健壯性,因而具有一定的實際應用價值.然而,由并行化效率可以看到,目前,本文給出的編譯框架的并行化效率仍然較低,這3個程序獲得的加速比平均僅為手工并行程序的53.44%.通過與手工并行代碼對比可以看到,自動并行效率較低的主要原因有兩個:一是手工并行主要是外層的循環,而自動并行的循環很多是內層的計算量較小的循環,這主要是因為函數調用等影響了自動并行發掘更粗粒度的并行；二是手工并行時程序員知道更多的信息,可以對代碼做更大的改動,而自動并行使用的程序靜態分析和變換都有一定的局限性.

8 總 結

高性能計算機在現代科學研究中的作用越來越重要且不可替代.異構眾核處理器在構建高性能計算機系統時低功耗、高性能的優勢使其成為高性能計算領域處理器發展的重要趨勢,但其更為復雜的結構也使得原本就存在的編程難的問題更加突出.面向異構系統的自動并行化研究時間較短,因異構系統多種多樣,各種面向異構系統并行化研究工作的側重點也各不相同,其應用效果取決于具體的程序特征和平臺特性.本文的研究旨在通過自動化的編譯工具減輕編程人員將應用移植到“太湖之光”計算機上的工作負擔.本文基于開源編譯器Open64,設計和實現了面向SW26010異構眾核處理器的一個并行編譯框架,能夠實現一些程序到異構眾核并行程序的轉換且獲得較好的加速.但該框架目前的實現仍有很多不足,比如只能處理規則的數組及指針訪問形式,而且本框架使用的主要是靜態程序分析方法,具有一定的局限性,限制了本框架在一些程序中的應用.后續的研究工作:第一,要改進現有方法,彌補不足,比如用機器學習的方法進行收益評估,能夠克服靜態代價模型的一些不足；第二,異構眾核處理器仍在不斷發展,面對新的體系結構,需要不斷探索新的方法；第三,過程間分析、指針分析、依賴分析等編譯領域的通用技術直接影響并行識別的能力,目前這些技術還比較薄弱,需要繼續深入研究.雖然本文提出的具體方法大多是針對SW26010處理器的,但其基本思路對于其他異構眾核架構處理器的并行化編譯工作也有一定的參考價值.