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

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

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

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

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

解決并行編程問題有兩種基本方法:一種是程序員手工編寫并行程序；另一種是使用并行化編譯系統(tǒng).程序員手工編寫的并行程序在經(jīng)過精心優(yōu)化后往往有很高的運行效率,但手工編寫并行程序需要程序員熟悉相關(guān)領(lǐng)域,精通并行編程模型,了解硬件的體系結(jié)構(gòu)和指令集特點等,對程序員要求很高.而且,手工編寫并行程序的效率很低,對于過去數(shù)十年來積累的大量優(yōu)秀的應(yīng)用程序,將其進行手工改寫需要花費大量的時間和人力.并行化編譯系統(tǒng)是一個自動發(fā)掘程序中潛在并行性并將其轉(zhuǎn)換為并行程序的編譯工具,相比手工編寫并行程序,能夠快速地完成串行程序到并行程序的轉(zhuǎn)換,效率更高.基于高性能計算領(lǐng)域?qū)Σ⑿谐绦虻钠惹行枨笠约安⑿谢幾g的巨大應(yīng)用前景,大量的研究人員開始對并行化編譯技術(shù)進行研究,并行化編譯成為當(dāng)前高性能計算領(lǐng)域的一個研究熱點.但是由于并行化編譯技術(shù)本身的復(fù)雜性,目前并行化編譯得到的并行程序與手工編寫的相比,運行效率仍有較大差距.

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

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

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

1 研究基礎(chǔ)

1.1 目標平臺

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

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

Fig.1 SW26010 processor structure diagram圖1 SW26010處理器結(jié)構(gòu)圖

Fig.2 SW26010 memory hierarchy of each group圖2 SW26010單核組存儲系統(tǒng)結(jié)構(gòu)圖

1.2 編程模型

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

在“太湖之光”計算機上開發(fā)和移植程序,一個主要的工作就是添加Sunway OpenACC指示,實現(xiàn)程序在運算核心上的并行執(zhí)行.Sunway OpenACC程序要想獲得好的性能,需要仔細分析哪些循環(huán)適合在運算核心上運行,還需要根據(jù)程序特征和處理器特性對程序的數(shù)據(jù)傳輸?shù)茸魃钊雰?yōu)化.本文的研究工作即是在編譯器中通過程序分析,自動添加Sunway OpenACC指示.本文編譯框架通過“源-源”方式生成的Sunway OpenACC程序,還需要經(jīng)過 Sunway OpenACC編譯工具的二次編譯.本文的編譯框架判斷哪些代碼適合加載到運算核心進行加速計算,以及哪些數(shù)據(jù)是運算核心加速計算時需要的,而Sunway OpenACC編譯工具則完成異構(gòu)代碼的生成,以及數(shù)據(jù)在存儲系統(tǒng)中的分布.

2 并行編譯框架

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

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

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

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

3 任務(wù)劃分

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

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

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

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

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

算法.Parallel_LoopNest_Recognition(L,m).

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

4 數(shù)據(jù)布局

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

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

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

4.1 數(shù)組邊界分析

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

圖5所示為數(shù)組邊界分析示例.

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

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

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

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

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

4.2 指針范圍分析

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

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

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

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

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

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

(3) 在初始DFCG上按照拓撲后續(xù)依次分析,并不斷加入待分析的符號變量存在的控制依賴和數(shù)據(jù)依賴對應(yīng)的節(jié)點和邊,當(dāng)所有可達節(jié)點依次加入到該流圖后,針對該循環(huán)的DCFG構(gòu)建完畢；

(4) 在構(gòu)造的需求驅(qū)動控制流圖上進行迭代數(shù)據(jù)流分析,當(dāng)某個節(jié)點的變量存在控制范圍約束時,對控制范圍和數(shù)據(jù)范圍信息進行合并.

5 傳輸優(yōu)化

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

5.1 數(shù)據(jù)傳輸合并

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

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

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

5.2 數(shù)據(jù)傳輸外提

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

針對外層串行內(nèi)層并行的嵌套循環(huán),本框架使用數(shù)據(jù)傳輸外提將嵌套循環(huán)內(nèi)層被多次執(zhí)行的數(shù)據(jù)區(qū)代碼轉(zhuǎn)移到嵌套循環(huán)外,減少數(shù)據(jù)傳輸次數(shù).數(shù)據(jù)傳輸外提采用自底向上的分析過程,當(dāng)數(shù)據(jù)區(qū)包含在循環(huán)內(nèi)部,且數(shù)據(jù)區(qū)滿足以下兩個條件時進行外提:第一,數(shù)據(jù)區(qū)中數(shù)據(jù)復(fù)制子句復(fù)制數(shù)據(jù)的范圍在外層循環(huán)執(zhí)行過程中是不變的,即外層循環(huán)的每次執(zhí)行都復(fù)制同樣的數(shù)據(jù)；第二,數(shù)據(jù)區(qū)傳輸?shù)淖兞吭谕鈱友h(huán)除數(shù)據(jù)區(qū)以外的代碼中沒有引用,即這些變量只在數(shù)據(jù)區(qū)內(nèi)使用,一直保留在 SPM 內(nèi)不會影響外層循環(huán)內(nèi)其他代碼段的執(zhí)行,也不會受其他代碼段的影響.重復(fù)執(zhí)行以上外提過程,直至不滿足外提條件或數(shù)據(jù)區(qū)外層沒有循環(huán)為止.

5.3 數(shù)據(jù)打包傳輸

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

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

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

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

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

Fig.8 Example of packaging transmission圖8 數(shù)據(jù)打包傳輸示例

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

5.4 數(shù)組轉(zhuǎn)置

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

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

數(shù)組轉(zhuǎn)置子句的使用方式與數(shù)據(jù)復(fù)制子句相同,其含義如下.

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

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

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

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

Fig.9 Exampe of array transpose圖9 數(shù)組轉(zhuǎn)置代碼示例

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

6 收益評估

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

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

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

6.1 代價模型的建立

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

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

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

6.1.1 串行模型

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

(1) 處理器開銷

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

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

(2) 訪存開銷

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

6.1.2 并行模型

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

(1) 并行控制開銷

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

(2) 數(shù)據(jù)傳輸開銷

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

(3) 并行計算開銷

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

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

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

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

6.2 收益評估方法

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

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

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

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

7 實驗測試

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

7.1 優(yōu)化效果測試

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

7.1.1 多維并行測試

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

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

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

7.1.2 傳輸優(yōu)化測試

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

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

Fig.13 Effect of transmission optimization method圖13 傳輸優(yōu)化方法效果圖

7.1.3 收益評估測試

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

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

Table1 Comparison of the number of parallel loops before and after benifit estimate表1 收益評估前后并行循環(huán)數(shù)目對比結(jié)果

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

7.2 整體性能測試

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

7.2.1 NPB測試分析

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

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

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

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并行循環(huán)數(shù)目對比圖

7.2.2 科學(xué)計算程序測試分析

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

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

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

8 總 結(jié)

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