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

劉金碩，黃朔，鄧娟

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

0 概述

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

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

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

1 自動兩級并行翻譯方法

1.1 總體結構

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

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

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

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

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

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

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

1.2 基于ANTLR 的源C 代碼解析

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

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

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

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

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

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

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

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

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

1.3 數據依賴分析

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

根據對同一內存區域的讀寫操作，數據依賴關系可以由流依賴關系、反依賴關系和輸出依賴關系組成。在循環結構中：流依賴關系指的是一個存儲單元在一次迭代中寫入，然后在后續迭代中讀取；反依賴關系指的是在一個迭代中讀取一個存儲單元，然后在隨后的迭代中寫入一個存儲單元；輸出依賴關系指的是一個存儲單元是一次迭代寫入，然后在后續迭代中再次寫入。

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

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

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

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

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

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

1.4 循環數組私有化

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

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

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

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

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

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

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

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

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

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

1.5 兩級并行映射

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

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

在圖像處理算法中，把高分辨率輸入圖像分割成塊。對于同一個可并行化循環語句，一部分圖像塊會在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）驗證線程數目對本文方法的影響。

2.1 基準實驗

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

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

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

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

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

2.2 圖像處理算法實驗

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

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

對于輸入數據集，選用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 像素。基于PMVS 算法，將本文方法與PPCG 和OpenACC 進行對比，實驗結果如圖6 所示。

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

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

2.3 多線程實驗

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

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

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

3 結束語

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