面向PMVS 算法的自動兩級并行翻譯方法

劉金碩，黃朔，鄧娟

（1.武漢大學國家網(wǎng)絡安全學院 空天信息安全與可信計算教育部重點實驗室，武漢 430072；2.武漢大學 計算機學院，武漢 430072）

0 概述

基于面片的三維多視角立體視覺（Patch-based Multiple View Stereo，PMVS）算法將已知內(nèi)外參數(shù)的多幅圖像作為輸入，重建出真實世界中物體/場景的三維模型。由于該算法原理以及圖像分辨率和規(guī)模的增大，會導致計算時間過長，因此可將其并行化，使輸入圖像分別在CPU 和GPU 上處理來降低計算時間。目前，加快計算速度的并行編程方法主要有MPI［1-3］、OpenCL［4-5］、OpenMP［6-8］、OpenACC［9］和CUDA［10-12］。然而，手動或半自動翻譯大量串行程序仍是一個巨大的挑戰(zhàn)，一些已有的自動翻譯工具的加速效率不理想，并且翻譯效果甚至比人工翻譯的結果差很多，因此亟須開發(fā)和改進從串行程序到并行程序的自動翻譯方法［13-15］。

目前，研究人員已提出許多自動并行翻譯工具與方法。BASKARAN等［16］提出一種基于Pluto［17］和ClooG［18］的C到CUDA的自動轉換框架，以生成目標CUDA代碼。PPCG［19］是一種基于多面體編譯技術的源到源編譯器，結合仿射變換以使用代碼生成器提取數(shù)據(jù)并行性。Bones［20］是一種基于骨架的源到源的自動并行化方法，用于將C轉換為5種類型的目標代碼。此外，還包括Cetus［21-23］、Par4All［24］和ROSE［25-26］等工具。Cetus和ROSE支持CPU粗粒度并行化與OpenMP；Pluto和Par4All支持OpenMP和CUDA。劉松等［27］根據(jù)程序的控制流和數(shù)據(jù)依賴信息將源程序代碼映射成可計算單元圖，從中提取出可并行執(zhí)行的非規(guī)則代碼段。李雁冰等［28］基于開源編譯器Open64，提出一種面向異構眾核處理器的并行編譯框架，將程序自動轉換為異構并行程序。王鵬翔等［29］對Intel編譯器、Open64編譯器和GCC編譯器3個典型編譯器自動并行化的效果進行評估。丁麗麗等［30］提出一種能夠處理分支嵌套循環(huán)的依賴測試方法，并通過檢測距離向量判斷循環(huán)是否存在依賴。高雨辰等［31］對循環(huán)并行方式進行分析。

這些自動并行翻譯工具與方法一般遵循解析源代碼、執(zhí)行并行化分析、重構適合GPU 并行化的循環(huán)結構和優(yōu)化生成目標代碼4 個步驟。它們多數(shù)僅用GPU來執(zhí)行計算密集型任務。然而，盡管GPU 具有出色的加速能力，但CPU 必須等待GPU 完成其計算任務，這樣就浪費了多核CPU 的計算資源。針對這些問題，本文提出一種面向PMVS算法的自動兩級并行翻譯方法?；贏NTLR（Another Tool for Language Recognition）［32-33］的分析器自動識別圖像處理算法源C 程序中的可并行化循環(huán)結構，映射成多線程CPU 代碼和CUDA 代碼，對于高分辨率圖像在CPU 和GPU 上進行分別處理，以降低圖像處理算法的總計算時間。

1 自動兩級并行翻譯方法

1.1 總體結構

本文提出的一種用于PMVS 算法的自動兩級并行翻譯模型如圖1 所示，以源C 程序為輸入，經(jīng)過基于ANTLR 的解析、數(shù)據(jù)依賴性分析、循環(huán)數(shù)組私有化和映射階段，把可并行化的程序分別映射到多核CPU 和GPU 架構上，最終輸出生成多線程CPU 和GPU 兩級代碼。

圖1 自動兩級并行翻譯模型Fig.1 Automatic two-level parallel translation model

自動兩級并行翻譯方法的主要步驟如下：

1）通過ANTLR 解析源C 代碼。首先掃描源代碼，然后可以自動生成擴展Backus-Naur 范式（Extended Backus-Naur Form，EBNF）語法描述，最后根據(jù)EBNF 描述，ANTLR 為抽象語法樹（Abstract Syntax Tree，AST）生成相應的詞法分析器。

2）分析數(shù)據(jù)依賴關系。分析從分析器中提取的循環(huán)信息。如果找到流依賴項，則包含這些依賴項的循環(huán)語句是不可并行的。如果發(fā)現(xiàn)數(shù)據(jù)之間的反依賴和輸出依賴，則在第3 步處理循環(huán)結構以消除依賴。如果沒有數(shù)據(jù)依賴，這樣的循環(huán)語句是可并行的。

3）循環(huán)數(shù)組私有化。需要消除變量重用引起的反依賴和輸出依賴。循環(huán)數(shù)組私有化技術將與循環(huán)迭代相關的存儲單元本地化，使其與其他循環(huán)迭代的存儲單元的交互分離。

4）映射。首先，將可并行化的循環(huán)結構映射到CUDA 架構和CPU 多線程架構；然后，生成對應的CUDA 代碼和CPU 多線程代碼；最后，多核CPU 創(chuàng)建相應數(shù)量的線程，一個線程負責GPU 調度，其他線程執(zhí)行分配給CPU 的并行任務，同時GPU 執(zhí)行分配給它的任務。

1.2 基于ANTLR 的源C 代碼解析

ANTLR 是一種可根據(jù)輸入自動生成語法樹并可視化顯示的開源語法分析器，其前身是PCCTS，它為包括Java、C++、C#在內(nèi)的語言提供了一個通過語法描述來自動構造自定義語言的識別器、編譯器和解釋器的框架。ANTLR 使用EBNF 規(guī)則生成源C代碼的語法描述，根據(jù)語法的屬性，對源程序執(zhí)行詞法分析和句法分析，然后生成AST。ANTLR 提供了一種遍歷AST 的機制，可以幫助提取循環(huán)相關信息。使用ANTLR 解析C 源代碼以生成AST 并提取循環(huán)相關信息的流程如圖2 所示。

圖2 使用ANTLR 解析C 源代碼的流程Fig.2 Procedure of parsing source C code using ANTLR

首先，利用ANTLR 創(chuàng)建串行源代碼的EBNF 描述。EBNF 描述的語法可以用四元組表示如下：

其中，Vn是非終結符號的有限集合；Vt是終結符號的有限集合；S是起始符號語法；P是生產(chǎn)集，也包括規(guī)則集；Z是源代碼。語法中最重要的是P，用“A：a”的形式表示，其中，A 是生產(chǎn)的左側部分，表示非終端符號，a 是生產(chǎn)的右側部分，表示終端符號。ANTLR 中EBNF 使用的語法符號如表1 所示。

表1 EBNF 語法符號Table 1 EBNF syntax symbol

然后，執(zhí)行詞法分析，匹配輸入流中的字符，掩蓋或過濾不相關的內(nèi)容，并生成用于語法分析的標記。為了達到這個目的，ANTLR 在詞法分析的語法中增加了一系列過濾方法。在源代碼中，空格、制表符、回車符和換行符等字符通常是無意義的冗余字符。ANTLR 提供了skip（）方法來跳過這些無意義的符號，例如，在使用WS：（''|' t'|' n'|' r'）+｛skip（）；｝遍歷這些字符時，將調用skip（）方法以跳過相應的字符。在源代碼中的注釋在編譯時毫無意義，在生成最終文檔時需要重新使用。ANTLR 提供了一種在編譯時隱藏注釋的渠道機制，例如，使用COMMENT：'/*'.*'*/'｛$channel=HIDDEN；｝可以將匹配的注釋塊放入HIDDEN 通道中，而不會出現(xiàn)在后續(xù)的語法分析中。

其次，分析上一步語法中的標記，ANTLR 在默認情況下無上下文規(guī)則，可以添加規(guī)則參數(shù)以實現(xiàn)上下文信息的傳遞，以彌補上下文無關文法的不足。例如，使用規(guī)則參數(shù)的代碼片段確定變量分配的類型是否滿足要求：

在變量聲明語法中，定義規(guī)則參數(shù)idList［$type.text］，因此在以下語法中，idList 攜帶類型信息。為了提取與循環(huán)相關的變量信息，將返回值添加到循環(huán)語句聲明的語法表達式中，以便可以直接從各種循環(huán)聲明中提取與變量相關的信息。在while 語句聲明中添加返回值int 的示例代碼具體如下：

最后，AST 是在語法分析后形成的，以樹的形式存儲句子的數(shù)據(jù)結構，樹上的每個節(jié)點代表源代碼中的結構。串行C 代碼抽象語法樹的遍歷主要用于遍歷循環(huán)結構。本文使用ANTLR 提供的Visitors 方法來遍歷AST，并重載visitForStatement（）方法。該方法存儲循環(huán)嵌套級別和與循環(huán)相關的變量信息source C 代碼，包括變量名稱、變量類型和存儲循環(huán)位置的行號，并將收集的變量信息移交給下一個階段進行處理。

1.3 數(shù)據(jù)依賴分析

數(shù)據(jù)依賴關系是指程序中語句的部分順序關系，反映了維護程序語義所需的固有順序。影響程序并行性的是對數(shù)據(jù)的讀寫訪問，因此并行翻譯中需要考慮數(shù)據(jù)依賴關系。

根據(jù)對同一內(nèi)存區(qū)域的讀寫操作，數(shù)據(jù)依賴關系可以由流依賴關系、反依賴關系和輸出依賴關系組成。在循環(huán)結構中：流依賴關系指的是一個存儲單元在一次迭代中寫入，然后在后續(xù)迭代中讀?。环匆蕾囮P系指的是在一個迭代中讀取一個存儲單元，然后在隨后的迭代中寫入一個存儲單元；輸出依賴關系指的是一個存儲單元是一次迭代寫入，然后在后續(xù)迭代中再次寫入。

假設在循環(huán)語句F（循環(huán)結構）中，I是迭代空間，i（i∈I）是I中一次迭代的循環(huán)控制變量。在迭代i下，RReadi表示所有讀取變量的集合，而表示所有寫入變量的集合。那么F可以并行化的充要條件如式（2）所示：

式（2）表示該循環(huán)結構不存在流依賴關系，并且不存在反依賴關系或者輸出依賴關系，其中，i，j∈I并且i≠j。如果F中存在流依賴關系，則應滿足以下條件：

其中：i，j∈I并且i＞j。在相同的存儲區(qū)域上進行寫入操作，并且需在讀取操作之前執(zhí)行。這個寫入操作和讀取操作類似于生產(chǎn)者和消費者之間的關系，包含流依賴關系的循環(huán)結構不能在GPU 上并行執(zhí)行。

如果F中存在反依賴關系，則應滿足以下條件：

其中：k，l∈I并且k＜l。對同一存儲區(qū)的讀取操作發(fā)生在寫入操作之前，這是由于重復引用同一存儲區(qū)引起的。自動并行翻譯可以通過創(chuàng)建一個臨時存儲區(qū)來實現(xiàn)。如果輸出依賴項存在于F（循環(huán)結構F包含輸出依賴關系）中，則應滿足以下條件：

其中：m，n∈I并且m≠n。在同一存儲區(qū)域上的寫入操作至少發(fā)生2 次。對于反依賴關系和輸出依賴關系，都可以通過創(chuàng)建一個臨時存儲區(qū)來實現(xiàn)自動并行轉換。具體地，以從解析器中提取的與循環(huán)相關的信息為輸入，然后對輸入進行數(shù)據(jù)依賴關系分析。通過數(shù)據(jù)依賴關系分析，如果找到數(shù)據(jù)之間的反依賴關系或輸出依賴關系，則將包含這些依賴關系的循環(huán)結構傳遞到下一個循環(huán)數(shù)組私有化階段進行處理。如果找到流依賴關系，則會標記諸如無法并行化的循環(huán)結構之類的語句。如果找不到數(shù)據(jù)依賴關系，則可以直接并行化這種循環(huán)結構。

1.4 循環(huán)數(shù)組私有化

在串行C 代碼中，重復使用相同的變量會給自動并行轉換帶來巨大困難。變量的使用使得存儲地址具有數(shù)據(jù)依賴關系、反依賴關系和輸出依賴關系。循環(huán)數(shù)組私有化可以消除這些依賴關系。循環(huán)語句中存儲單元的顯式表示形式是變量和數(shù)組。變量也可以看作是數(shù)組的一種特殊表示形式，表示只有一個元素數(shù)組。在串行C 代碼中，全局數(shù)組通常用于存儲數(shù)據(jù)，從而減少了存儲空間。全局數(shù)組將在循環(huán)語句中的每次迭代中使用。循環(huán)數(shù)組私有化在每次迭代中使用新的存儲空間來私有化原始重用空間，因此不存在交叉迭代依賴項。

除了數(shù)組的初始化之外，循環(huán)語句中數(shù)組重新分配的位置可以分為3 類：1）在當前迭代中為數(shù)組分配新值，然后在下一次迭代中使用；2）在循環(huán)外為數(shù)組分配一個值，并在迭代中重用；3）先分配數(shù)組，再在同一迭代中重復使用。

第1 類的示例代碼具體如下：

在此循環(huán)語句中：當i=0 時，在第5 行為數(shù)組A分配值“temp2+2”；當i=1 時，在第4 行的語句“temp1=A+1”中使用數(shù)組A。這是一個具有流依賴關系的循環(huán)，因此該循環(huán)不能通過循環(huán)數(shù)組私有化來翻譯。

第2 類的示例代碼具體如下：

在此代碼段中，除在循環(huán)第5 行中使用的循環(huán)語句外，為數(shù)組A分配了值“1”。在這種情況下，數(shù)組A可以私有化，對第2 類的數(shù)組私有化代碼具體如下：

第3 類的示例代碼具體如下：

在此循環(huán)語句中，當i=0 時，首先在第4 行中為數(shù)組A賦值“temp2+2”，然后在第5 行的語句“temp1=A+1”中對其進行調用。在同一迭代中分配并重用該數(shù)組。在這種情況下，可以將數(shù)組A私有化，對第3 類的數(shù)組私有化代碼具體如下：

循環(huán)語句私有化的第一個條件是迭代之間不存在流依賴關系，第二個條件是在循環(huán)外重新分配數(shù)組，或者在相同迭代中使用之前重新分配的數(shù)組。結合反依賴關系和輸出依賴關系的條件，采用數(shù)組私有化的必要條件如式（6）所示：

其中：i，j，k，l，m，n∈I并且i>j，l＞k，m≠n。式（6）表示不存在流依賴關系，但是存在反依賴關系或者輸出依賴關系。

1.5 兩級并行映射

為了不浪費任何計算資源，需要獲得目標的兩級并行化代碼CPU 多線程和GPU CUDA，RAHTP將可并行化的循環(huán)結構映射到C 多線程代碼和CUDA 代碼，具體如下：

標記為“parallel”的是經(jīng)過解析的可并行代碼塊。“kthread”表示應該在CPU 上創(chuàng)建的線程數(shù)，“ctasks”和“gtasks”分別表示將在CPU 和GPU 上處理的任務。如第1 行～第14 行所示，循環(huán)函數(shù)包括可并行化的循環(huán)結構，CPU 創(chuàng)建相應數(shù)量的線程，其中一個線程負責GPU調度，而其他線程則執(zhí)行并行任務。如第15行～第21行所示，CUDA 內(nèi)核處于CPU 線程的調度之下，并且包含相同的可并行循環(huán)來執(zhí)行。映射的實現(xiàn)過程具體為：首先，將循環(huán)結構的串行代碼映射為CUDA 并行代碼，創(chuàng)建CUDA 核心kernel 函數(shù)，在GPU 上運行；其次，在CPU 上創(chuàng)建線程來調度GPU 和執(zhí)行串行代碼。

在圖像處理算法中，把高分辨率輸入圖像分割成塊。對于同一個可并行化循環(huán)語句，一部分圖像塊會在CPU 上并行處理，而其他塊會在GPU 上處理，如圖3所示。

圖3 圖像兩級并行處理Fig.3 Two-level parallel processing for the images

2 實驗結果與分析

使用8核Intel i7-9700 CPU 和12GB顯存的Nvidia Tesla p4 GPU，編譯器是NVCC 10.0。實驗主要包括以下3 個部分：1）將本文方法與其他自動并行翻譯方法在Poly-Bench/C4.2.1 的10 個基準測試程序上進行有效性驗證；2）選擇PMVS 算法進行圖像處理，將本文方法與其他自動并行翻譯方法進行性能比較；3）驗證線程數(shù)目對本文方法的影響。

2.1 基準實驗

將本文方法與PPCG、OpenACC 這兩種自動并行翻譯方法進行比較。PolyBench 是俄亥俄州立大學創(chuàng)建的一組基準測試套件，包含30 個帶有靜態(tài)控制流的數(shù)值計算，提取自線性代數(shù)計算、圖像處理、物理模擬、動態(tài)編程、統(tǒng)計信息等應用領域。

從PolyBench/C 4.2.1 中選擇10 個程序作為基準測試，其中，correlation、covariance 是數(shù)據(jù)挖掘領域的程序，jacobi-1d、jacobi-2d 是stencils計算程序，nussinov、floyd-warshall 是動態(tài)規(guī)劃程序，atax、bicg、doitgen、mvt 是線性代數(shù)核函數(shù)程序。這些測試程序包含可并行化的循環(huán)結構，具有良好的數(shù)據(jù)重用性，適合作為自動并行翻譯方法的測試基準。輸入數(shù)據(jù)集為LARGE_DATASET。每個算法設置的任務數(shù)量為1 000。測試程序信息如表2 所示。每種自動并行翻譯方法對每種算法的執(zhí)行時間與加速比如圖4所示。

表2 測試程序信息Table 2 Test program information

圖4 基準實驗結果Fig.4 Benchmark experimental results

在圖4 中，加速比是指CPU 串行和并行方法的執(zhí)行時間之比，在10 個測試程序的運行中，PPCG、OpenACC、本文方法分別平均獲得了19.81、22.25、31.62 的加速比，可以看出本文方法的加速比最高，PPCG 和OpenACC 的性能接近。本文方法有最高加速比的原因是使用了GPU 以外的CPU 多線程，在GPU 上執(zhí)行任務的同時，一部分任務會在CPU 上執(zhí)行，降低了所有任務的總執(zhí)行時間，而PPCG 和OpenACC 只在GPU 上執(zhí)行任務。通過基準實驗，證明了本文方法比其他自動并行翻譯方法具有更優(yōu)越的性能。

2.2 圖像處理算法實驗

將PMVS 算法作為圖像處理示例算法進行分析與研究。PMVS 是圖像處理領域的使用2D 圖像重建3D 場景的算法，從不同角度使用同一對象的多個2D 圖像進行3D 建模，基于匹配點還原場景的立體信息。PMVS 包括許多可并行處理的過程，包括高斯函數(shù)的Harris 差分（Harris-DOG），可以從2D 圖像序列中提取特征點。PMVS 算法流程如圖5 所示。

圖5 PMVS 算法流程Fig.5 Procedure of PMVS algorithm

對于輸入數(shù)據(jù)集，選用10 張不同分辨率的圖片進行實驗，分別為100×120像素、520×560像素、1 136×1 250 像素、6 230×6 582 像素、12 175×14 210 像素、22 450×26 712 像素、47 565×48 865 像素、64 174×69 210 像素、73 212×72 520 像素、81 511×94 753 像素?；赑MVS 算法，將本文方法與PPCG 和OpenACC 進行對比，實驗結果如圖6 所示。

圖6 PMVS 實驗結果Fig.6 PMVS experimental result

在圖6 中，圖像分辨率從100×120 像素到81 511×94 753 像素逐漸增加。PPCG 和OpenACC 的加速比先是增加，因為GPU 并行效率隨著輸入數(shù)據(jù)的增大而提升，當圖像分辨率達到12 175×14 210 像素時，加速比達到最大，分別是19.47 和21.76，此后圖片再增大加速比也不再增加，在最大值附近波動。本文方法也呈現(xiàn)相同的趨勢，但是在每一種圖像分辨率上，加速比都大于PPCG 和OpenACC，最高值在64 174×69 210 像素附近，達到32.03，這是因為本文方法使用了兩級并行策略，輸入圖像的一部分在CPU 上處理，降低了整個圖片的處理時間，并且隨著圖像分辨率的增加，分配在CPU上處理的任務也會增加，當圖像分辨率達到64 174×69 210 像素時，CPU 發(fā)揮最大性能，當再增加圖像分辨率時，任務會串行執(zhí)行，總執(zhí)行時間不會再縮短，最大加速比穩(wěn)定在32.15 左右。通過圖像處理實驗證明了在處理高分辨率圖像時，本文方法比其他自動并行翻譯方法的效率更高。從100×120 像素開始，隨著圖像分辨率的增加，加速比的增幅不斷提升，當圖像分辨率達到64 174×69 210 像素時性能最優(yōu)。

2.3 多線程實驗

為確定線程數(shù)目對本文方法的影響，通過改變CPU 線程數(shù)目評估本文方法的性能，實驗條件與設置同圖像處理算法實驗，輸入圖像分辨率分別為520×560 像素、12 175×14 210 像素和64 174×69 210 像素，實驗結果如圖7 所示。

圖7 多線程實驗結果Fig.7 Multi-thread experimental results

在圖7 中，加速比是指CPU 串行與本文方法執(zhí)行時間之比。3 種不同分辨率的圖像呈現(xiàn)相同的變化，當線程數(shù)目從1 增加到8 時，三者的加速比都持續(xù)增加，圖像分辨率為520×560 像素的圖像加速比從11.83 增加到14.67，圖像分辨率為12 175×14 210 像素的圖像加速比從19.13 增加到24.61，圖像分辨率為64 174×69 210 像素的圖像加速比從23.24 增加到31.62，這是因為多線程并行執(zhí)行任務，可以提高CPU的負載能力。當線程數(shù)目達到8 時，因為CPU 核心數(shù)目為8，所以此時CPU 并行能力最強，加速比最高，之后隨著線程數(shù)目增加，超過了CPU核心數(shù)目后，加速比不再增加。因此，當線程數(shù)目等于CPU 核心數(shù)目時，本文方法達到最優(yōu)性能。

3 結束語

本文提出一種用于PMVS 算法的自動兩級并行翻譯方法，可自動將串行C 程序轉換為CPU 多線程和CUDA 的兩級并行程序。經(jīng)過本文方法并行化后，PMVS 算法可使高分辨率圖像在CPU 和GPU 上分別進行處理，降低了算法計算時間。實驗結果表明，與其他自動并行翻譯方法相比，本文方法能更有效地提升圖像處理算法的性能。后續(xù)將在任務分配過程中考慮CPU 與GPU 之間的任務負載量，使CPU與GPU 達到負載均衡狀態(tài)，進一步提升圖像處理算法的性能。