基于JavaCC的C代码自动并行化的设计与实现

刘有耀　杨鹏程

摘要：

针对当前大量遗产代码无法重复利用的问题，设计一种新的编译工具将C的串行代码转换为基于MPI+OpenMP的混合并行编程代码，降低了并行编程的开发成本。首先，通过对JavaCC的优化，实现一种可以解析C语言的词法和语法分析器，进行源代码分析并生成抽象语法树；其次，根据语法树对源代码进行控制依赖性和数据依赖性分析，产生可并行化的语句块分区；再次，按照提出的并行代码生成方法得到目标代码；最后，基于Visual Studio 2010构建目标代码仿真验证环境。实验结果表明，该工具可以较为理想地实现串行代码自动并行化，与手工编写的代码在加速比上的误差为8.2%～18.4%。

关键词：

JavaCC；抽象语法树；依赖性；自动并行化；MPI+OpenMP

中图分类号：

TP311

文献标志码：A

Abstract：

Aiming at the problem that a large amount of legacy code can not be reused， a new compilation tool was designed to convert the serial code of C into a hybrid parallel programming code based on MPI+OpenMP， which can reduce the development cost of parallel programming. First of all， by optimizing Java Compiler Compiler （JavaCC）， a lexical and syntax analyzer which can parse the C language was implemented， then the source code analysis was conducted and the abstract syntax tree was generated. Secondly， according to the abstract syntax tree， the control dependence and data dependence of the source code were analyzed to produce the parallelizable statement block partitions. Thirdly， the object code was obtained according to the proposed parallel code generation method. Finally， the target code simulation environment was built based on Visual Studio 2010. The experimental results show that the tool can effectively achieve automatic parallelization of the serial code， and compared with the code written by hand， its speedup of the error is between 8.2% to 18.4%.

英文关键词Key words：

Java Compiler Compiler （JavaCC）； abtract syntax tree； dependency； automatic parallelization； MPI+OpenMP

0引言

近年来，随着并行计算的快速发展和数据量的不断增长，使用传统的串行编程语言已经难以对其进行处理，人们需要寻找到一种新的技术来适应大规模数据的处理，并行处理技术便应运而生。并行处理技术的发展必然伴随着并行编程语言的产生，对此，人们也进行了非常多的尝试，从而发现了多种并行编程语言。MPI+OpenMP[1]的混合编程便是其中应用最为广泛的一种编程语言。这对编程人员的编程能力要求比较高，所以急切的需要一种设计工具可以将之前的大量遗产C代码直接转换为并行程序，降低并行程序的开发成本，减轻编程人员的编程压力。

目前，国内的自动并行化工具主要有复旦大学研发的AFT和国防科技大学研制的KDPARPRO/V2.0。而在国外，自动并行化工具的研究已经逐步成熟，具有代表性的有美国斯坦福大学的SUIF编译器[2]以及苹果公司研发的LLVM/Clang编译器[3]。但由于这些编译工具在使用时需要有中间代码的生成，编程人员在修改编译器时也需要了解中间代码的意义。所以基于这些想法，本文寻找到一种新的编译器——JavaCC（Java Compiler Compiler）[4]，其作為一种词法语法分析器的生成工具，只要按照C语言的语法定义好相应的规则，就可以对C源代码进行分析，不需要有中间代码的生成。

本文的主要工作是使用JavaCC生成的分析器作为程序前端分析的工具，得到程序中可并行化的分区模块；再按照并行代码的生成方法，得到最终的代码；之后在Visual Studio 2010和MPICH2搭建的环境下对其进行功能验证，并与手工编写的代码进行加速比的对比，得出其性能的优劣性。该工具的设计既能够有效解决大规模数据的处理问题，又能够节省编程人员在编程方面的时间花费，为程序并行化提供了一种高效的技术途径。

1MPI+OpenMP混合编程模式

消息传递接口 （Message Passing Interface， MPI）是一种有关消息传递规范的库，而不是一门语言，文中使用的实现方式是MPICH2。而OpenMP是一个共享存储并行系统上的应用编程接口，共享的内存可以被所有OpenMP线程访问，这种编程方式主要用于多核共享内存的场景，它拥有一系列的编译指导语句、运行库例程和环境变量。

MPI+OpenMP混合编程[5]利用以上两种编程模式的优势：它使用了可在多异构节点间有效通信的MPI机制，并以OpenMP轻量级线程组的方式在共享内存的多核平台上运行。在此混合并行计算模型下，MPI主要提供通信机制，OpenMP多线程则主要承担计算的部分。通常通信及计算的部分是以串行的方式实现的：OpenMP多线程的结构为fork…join…类型，在运行计算任务时MPI ranks处于等待状态，当MPI ranks得到结果时，接着就会与其他节点交换结果与此同时OpenMP线程处于等待计算任务的状态。用户可以通过更好地安排OpenMP与MPI间任务的协作来进一步改进程序的性能。混合编程模式的模型结构如图1所示。

2.2JavaCC前端编译模块

JavaCC是一个用Java开发的能生成词法和语法分析器的生成程序[8]。其输入文件为一个按照C语法规则定义的文件，且包含一些语义的描述，它的后缀名是.jj。输出为可以解析C源代码的词法和语法分析器。接下来，对JavaCC编译前端的主要操作过程进行描述。

2.2.1词法分析

词法分析，也被称为扫描。它是JavaCC编译前端模块中代码转换处理机制的首要部分。词法分析器能把输入文件中的字符串划分为一个个称为记号（token）的有意义单元并对它们进行识别和归类。

2.2.2语法分析

JavaCC不生成抽象语法树（Abstract Syntax Tree， AST），但提供建立AST生成的预处理器JJTree，JJTree采用压栈出栈的递归方法生成分析树，为JavaCC的输入进行预处理。通过JavaCC和JJTree生成的语法分析器，其输入为词法分析之后得到的具有记号形式的源代码，而输出的结果则为抽象语法树（AST），从AST中可以看出源程序的整体架构。

语法分析只是将一组单词序列按照源代码的物理结构进行编排，并不注意其语义是否正确.在此部分中，输入的是词法分析后得出的单词序列，而输出的则是未注释过的语法树。

2.2.3语义分析

语义分析是按照JavaCC生成的分析器中预定义好的符号表和类型的一种映射结构，来判断经过语法分析后得出的代码是否符合相对应的语义规则。

程序的语义确定了程序的运行，但是大多数的程序设计语言都具有在执行之前被确定，而不易由语法表示和由分析程序分析的特征。这些语义动作通常是作为注释语言加入到语法树中。

2.2.4符号表

符号表是一种数据结构，用来存储关于源程序的各种相关信息。符号表在前端分析的过程中需要不断地进行收集、记录，源程序在词法分析之后得到的结果输入到表格中存储起来，作为语法分析器的输入；而对于语义分析部分，它将一些相

关的数据类型和与之对应的说明添加到符号表中。符号表还存储语句节点的编号，语句节点的识别是按照程序的物理结构依次对每个语句先进行标记。构建符号表是使用线性链表来记录相关的数据信息。

其具体实现的操作有以下几个方面：

1）创建一个新的符号表来保存标识符的信息；

2）在当前表中加入一个新的条目，使用键值对的方式。键指的是对应于标志符的词法单元对象的引用，而值指的是其中存储的相关信息。

3）更新重复使用的某个标识符的相关信息。

2.3程序结构分析

经过JavaCC前端分析后，输出为抽象语法树（AST）以及语义分析之后的结果，接下来是根据AST进行程序结构分析，从整体上把握需要分析的程序的架构。程序结构分析的最终结果就是得到含有循环体的语句块分区。其主要包括的部分有程序控制依赖图（Control Dependence Graph， CDG）的生成和程序的分区模块的划分[9]。

2.3.1程序控制依赖图

程序控制依赖图是根据语句节点的控制域来进行创建的，而控制域的划分主要是根据语句节点的入度和出度[10]来决定的，所以需先确定其入度和出度，代码的描述如下：

2.3.2程序的语句块分区

该部分是通过对控制依赖图进行遍历而得到。首先，通过计算各个语句块的入度和出度，能够将程序中的各个语句块进行重新编号，并将其保存到符号表中；其次，对各个语句块进行控制依赖和数据依赖性分析，确定可并行执行的语句块分区，调用MPI的库实现各个语句块之间的数据通信以及开销；最后，再分别对各个语句块内的计算部分进行一次数据依赖性分析，调用OpenMP的编译指导语句对其进行并行化的处理。

2.4数据依赖性分析

如果希望对原有的串行程序进行并行化，则需要分析语句块分区中的所有语句间的依赖关系，称之为相关分析[11]。

数据的依赖关系有如下三种：

1）流依赖。

一个变量在一次表达式中赋值或修改然后用在后来的另一个表达式中。如：S1：a=b+c；S2：d=a-e。

2）反依赖。

一个变量在一个表达式中被使用然后在后来一个表达式中被修改赋值。如：S1：a=b+c；S2：b=d+e。

3）输出依赖。

一个变量在一表达式中被修改赋值然后又在后来另一个表达式中被修改赋值。如：S1：a=b+c；S2：a=d-e。

根据三种依赖关系的分类可以看出：①数据不直接存在依赖性的语句可并行执行；②存在流依赖或输出依赖的语句不可并行执行；③存在反依赖的语句（如S1反依赖与S2），只要保证S1先读S2后写，则允许其并行执行。具体实现的代码[12]描述如下：

从图3中可以更加清晰的看出此算法的运行流程。经过此步骤，可以完成串行程序的分析工作，即完成整個软件设计的第一个大的部分，在自动转换部分，只需要调用存放于数组中的可并行执行语句编号，即可直接进行转换。接下来，将对第二个部分，即并行程序代码的生成进行阐述。

2.5并行程序代码生成

经过程序的粗略划分得到分区模块module_number，对语句块分区和分区内的嵌套循环部分进行数据依赖性分析。具体的操作如下：

1）在头文件中插入#include和#include；

2）在C源程序的main函数中插入MPI_Init（）、MPI_Comm_rank（）和MPI_Comm_size（）等初始化函数。

3）将C源程序中可并行化的语句块分区module_number，按照从小到大的顺序依次往下编号，特别注意，各个语句块分区在源程序中的位置不会发生任何改变。

首先，对可并行化的分区模块进行任务分配，在每个语句块分区上只有一个MPI的进程，针对各个分区模块：

①如果含有2重以上的嵌套循环，则调用OpenMP的编译制导语句#pragma omp parallel shared（） private（）对其进行处理；

②如果该分区模块就是2的重嵌套循环，并且在相关性分析完之后，无依赖性则直接插入OpenMP制导语句#pragma omp for；

③如果该语句块分区中不含有嵌套循环或是1重循环，则不对其作任何改变。

其次，在各个进程之间，MPI可以通过调用MPI_Send（）和MPI_Recv（）函数来实现进程之间的通信问题。

最后，通过调用MPI库实现语句块分区之间的通信和并行化，而在其计算部分，使用OpenMP来实现并行化的处理。

4）在源程序的return 0之前加入MPI_Finalize（）来使得MPI程序退出执行环境。

3系统平台搭建

本文基于Eclipse的平台，使用JavaCC和JJTree作为前端的分析工具[13]，在Eclipse中编写代码对程序进行控制依赖分析和数据依赖性分析，最终调用并行代码生成方法来实现转换。

对于整个系统的前端为基于JavaCC的前端分析，其具体过程为：

用户首先按照JavaCC的输入文件格式编写一个文件（*.jjt），即文件中的内容是依据C的词法和语法规则以及各个阶段中发生的行为而编写。主要包括以下几个部分：Options{}部分，主要声明产生的语法分析器的特性；接下来是一个介于“PARSER_BEGIN（name）”和“PARSER_END（name）”之间的分析器类，其中主要包括类名以及成员的声明；下面是被定义在Input和MatchedBraces的产生式中的词法分析器；最后定义语法规则，开头是一个声明，包括返回值类型、规则名和一个冒号，紧接着是一些在花括号（{}）里的声明和语句。一个语法单元中有多个规则时，用|分开。

其次，输入*.jjt的文件，通过JJTree的编译得到*.jj文件。

再次，使用JavaCC编译*.jj文件，可以生成Java代码实现的特定词法和语法分析器；生成的源程序包含：*Parser.java（语法分析器）、*TokenManager.java（词法分析器）等文件。

最终，通过生成的词法和语法分析器对一个输入的C源文件进行词法、语法分析，建立抽象语法树。如把一个MiniC的源文件传给分析器的代码为：

这段就是当调用ASTGoal这个类型的Translator方法时，会输出“ASTGoal”，之后继续遍历它的孩子节点。在这个类里编写一个SymbolTableTranslator.java和一个TypecheckingTranslator.java，分別实现MiniCParserTranslator这个接口，其中SymbolTableTranslator中的Translator方法负责完成建立符号表的工作。

之后按照控制依赖性分析和数据依赖性分析，对源程序进行分区，得到最终的语句块分区module_number，最后调用并行代码的生成方法来实现目标代码的生成。

将生成的代码保存，最后在MPI+OpenMP构建的混合编程模式下对目标代码进行验证。

4验证平台搭建及实例验证

接下来将具体介绍MPI+OpenMP混合并行编程验证平台[14]的搭建：

首先，将Visual Studio 2010和MPI的实现软件MPICH按照步骤安装在计算机上，之后将VS 2010打开，新建一个C++的控制台应用程序，在项目解决方案资源管理器上选择项目名称，点击右键，选择“属性”，再在属性页上左侧选择“配置属性”---“VC++目录”---“包含目录”，将MPI的include和lib文件夹添加到“库目录”中；其次，展开左侧的“C/C++”，选择其中的预处理器，在右边的预处理器定义中加入“MPICH_SKIP_MPICXX”，同时选择代码生成，将右侧的运行库改为“多线程调试Multithreaded Debug（/MTd）”；最后再展开左侧的链接器，加入“mpi.lib”；这样MPI的配置才算完成。接下来配置OpenMP，先在“配置属性”---“C/C++”---“语言”，将右侧的“OpenMP支持”设定为“是”；同时也可以设置系统环境变量，只需在环境变量中加入“OMP_NUM_THREADS”变量，数值可以根据自己CPU的性能来设置，本平台设置为4。这样就将MPI与OpenMP集成在VS 2010中，完成开发环境的设定。

首先，将Visual Studio 2010和MPI的实现软件MPICH安装在计算机上，之后在VS 2010中新建一个C++的控制台应用程序，在项目解决方案资源管理器上进行属性配置。

在验证过程中，首先使用该软件对几种不同的算法，如LU分解算法、矩阵乘算法进行转换，并与手工编写的代码进行比较，验证目标代码功能的正确性。图3显示的是LU分解算法中的部分代码L和U矩阵的生成转换图。

通过比较不同阶数下矩阵乘算法的加速比，可以得出其性能差异介于8.2%～18.4%。通过比较不同阶数下矩阵乘算法的加速比，使用（手工编写自动生成）/手工编写的加速比计算方式，得出其性能差异为8.2%～18.4%。尽管在性能上不如手工编译的代码的运行效率，但该软件可以基本实现算法的功能。

5结语

随着数据量的不断增长，自动并行化软件的设计也将逐步地走向成熟。本文首先利用JavaCC和JJTree按照C语言的语法规则，生成了可以对串行C源代码进行分析的词法和语法分析器；其次，按照程序结构的分析，将其进行了语句块分区；再次，经过控制依赖性和数据依赖性分析，发现了源代码中可并行化的部分，并保存到数组中；最后，按照并行代码生成方法将其转换为基于MPI+OpenMP的并行代码。经过实验，可发现本系统可以对有关矩阵计算的程序进行很好的分析和转换，但还存在着许多的不足，如：自动生成代码性能的差异；数组和指针的使用不完善等。在接下来的工作中，还需要进一步完善对源程序中语句块的精确划分，加强数据依赖性的分析能力，从而可以更加准确地实现源代码的自动并行化，优化程序的性能。

参考文献：

[1]

王杰.基于多核机群环境的并行程序设计方法研究——MPI+OpenMP混合编程[D].郑州：中原工学院，2012.（WANG J. The research on design method based on parallel program for windows environments [D]. Zhengzhou： Zhongyuan University of Technology， 2012.）

[2]

孫尧.基于SUIF平台的程序自动并行化辅助系统研究[D].长春：吉林大学，2014.（SUN Y. The research of program automatically parallel auxiliary system based on SUIF platform [D]. Changchun： Jilin University， 2014.）

[3]

张代远.基于Clang的C语言代码并行化转换工具的设计与实现[D].长春：吉林大学，2015.（ZHANG D Y. Design and implementation of a parallel conversion tool based on Clang for C code [D]. Changchun： Jilin University， 2015.）

[4]

DOS REIS A. Compiler Construction Using Java， JavaCC， and Yacc [M]. Hoboken， NJ： John Wiley and Sons， 2012： 367-417.

[5]

KLAWONN A， LANSER M， RHEINBACH O， et al. Hybrid MPI/OpenMP parallelization in FETIDP methods [M]. Berlin： Springer， 2015.

KLAWONN A， LANSER M， RHEINBACH O， et al. Hybrid MPI/OpenMP parallelization in FETIDP methods [M]// MEHL M， BISCHOFF M， SCHFER M. Recent Trends in Computational Engineering—CE2014. Berlin： Springer， 2015： 67-84.

KLAWONN A， LANSER M， RHEINBACH O， et al. Hybrid MPI/OpenMP parallelization in FETIDP methods [C]// Recent Trends in Computational Engineering—CE2014. Berlin： Springer， 2015： 67-84.

[6]

王磊.基于MPI的串行程序自动并行化的应用研究[D].淮南：安徽理工大学，2013.（WANG L. The application research of serial program automatic parallelization based on MPI [D]. Huainan： Anhui University of Science and Technology， 2013.）

[7]

DHEERAJ D， NITISH B， RAMESH S. Optimization of automatic conversion of serial C to parallel OpenMP [C]// Proceedings of the 2012 International Conference on CyberEnabled Distributed Computing and Knowledge Discovery. Washington， DC： IEEE Computer Society， 2012： 309-314.

[8]

黄松，黄玉，惠战伟.基于JavaCC的抽象语法树的构建与实现[J].计算机工程与设计，2016，37（4）：938-943.（HUANG S， HUANG Y， HUI Z W. Construction and realization of abstract syntax tree based on JavaCC [J]. Computer Engineering and Design， 2016， 37（4）： 938-943.）

[9]

陈科.程序流程图结构分析与识别技术的研究与实现[D].西安：西安电子科技大学，2011.（CHEN K. Research and implementation of structure analysis and identification for program flowchart [D]. Xian： Xidian University， 2011.）

[10]

闫昭，刘磊.基于数据依赖关系的程序自动并行化方法[J].吉林大学学报（理学版），2010，48（1）：94-98.（YAN Z， LIU L. Method of program automatic parallelization based on data dependence [J]. Journal of Jilin University （Science Edition）， 2010， 48（1）： 94-98.）

[11]

TANG H， WANG X， ZHANG L， et al. Summarybased contextsensitive datadependence analysis in presence of callbacks [C]// POPL 15： Proceedings of the 42nd Annual ACM SIGPLANSIGACT Symposium on Principles of Programming Languages. New York： ACM， 2015： 83-95.

TANG H， WANG X， ZHANG L， et al. Summarybased contextsensitive datadependence analysis in presence of callbacks [J]. ACM SIGPLAN Notices—POPL 15， 2015， 50（1）： 83-95.

[12]

陶彬賢.CODEREBUILDER：一种自动化Java并发程序重构工具的研究与实现[D].南京：南京航空航天大学，2014.（TAO B X. CODEREBUILDER： the research and implementation of an automated Java concurrent program refactoring tool [D]. Nanjing： Nanjing University of Aeronautics and Astronautics， 2014.）