面向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 达到负载均衡状态，进一步提升图像处理算法的性能。