LIU Youyao, born in 1975, Ph. D., associate professor. His research interests include embedded system, network-on-chip, design and verification of SoC.
YANG Pengcheng, born in 1992, M.S.candidate. His research interests is design and verification of SoC.
近年来,随着并行计算的快速发展和数据量的不断增长,使用传统的串行编程语言已经难以对其进行处理,人们需要寻找到一种新的技术来适应大规模数据的处理,并行处理技术便应运而生。并行处理技术的发展必然伴随着并行编程语言的产生,对此,人们也进行了非常多的尝试,从而发现了多种并行编程语言。MPI+OpenMP[1]的混合编程便是其中应用最为广泛的一种编程语言。这对编程人员的编程能力要求比较高,所以急切的需要一种设计工具可以将之前的大量遗产C代码直接转换为并行程序,降低并行程序的开发成本,减轻编程人员的编程压力。
目前,国内的自动并行化工具主要有复旦大学研发的AFT和国防科技大学研制的KD-PARPRO/V2.0。而在国外,自动并行化工具的研究已经逐步成熟,具有代表性的有美国斯坦福大学的SUIF编译器[2]以及苹果公司研发的LLVM/Clang编译器[3]。但由于这些编译工具在使用时需要有中间代码的生成,编程人员在修改编译器时也需要了解中间代码的意义。所以基于这些想法,本文寻找到一种新的编译器——JavaCC(Java Compiler Compiler)[4],其作为一种词法语法分析器的生成工具,只要按照C语言的语法定义好相应的规则,就可以对C源代码进行分析,不需要有中间代码的生成。
本文的主要工作是使用JavaCC生成的分析器作为程序前端分析的工具,得到程序中可并行化的分区模块; 再按照并行代码的生成方法,得到最终的代码; 之后在Visual Studio 2010和MPICH2搭建的环境下对其进行功能验证,并与手工编写的代码进行加速比的对比,得出其性能的优劣性。该工具的设计既能够有效解决大规模数据的处理问题,又能够节省编程人员在编程方面的时间花费,为程序并行化提供了一种高效的技术途径。
1 MPI+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所示。
具体算法的伪代码描述如下:
Program MO
recall MPI_Init()
recall MPI_Comm_rank(…)
recall MPI_Comm_size(…)
MPI_Status status;
…相关计算和MPI的通信部分
MPI_Send(…)
MPI_Recv(…)
OMP_Set_Num_Threads(4);
#pragma omp for一些相关的OpenMP编译制导语句
…可并行化的循环体
…循环体之间的通信部分
end omp parallel
…相关计算和MPI的通信部分
recall MPI_Finalize(…)
end Program MO
2 自动并行化软件的设计与实现自动并行化软件的设计[6-7]主要是从两个方面进行研究:串行程序的分析和自动转换代码的生成。而对于串行程序的分析主要有:JavaCC前端编译模块、程序结构分析和数据依赖性分析。接下来,将从以上几个方面来进行具体的描述。
2.1 系统的总体框架串行程序自动并行化软件的总体设计框架如图 2所示。
首先是自动读入串行C源程序,然后利用JavaCC生成的分析器进行前端分析,确定其语句节点的编号,之后根据编号对程序进行控制依赖性分析得到其分区模块,最终对各模块进行数据依赖性分析,寻找出可以使用MPI编程和OpenMP编译指导的部分,最后完成串行程序到并行程序的转换。由于文中是将C和MPI以及OpenMP进行绑定结合实现的。因此,所有的并行程序相比串行程序都多了两个头文件#include“mpi.h”以及#include“omp.h”。
2.2 JavaCC前端编译模块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]来决定的,所以需先确定其入度和出度,代码的描述如下:
program NODE_IN //计算语句节点的入度
int i, j, B(1:n)
//根据语句的相关性构造B(i)记录i语句的入度
i←1; j←2
while j < =number do //number是语句的个数
while i < j do
if〈i, j〉属于A
//〈i, j〉为相关性的表示, A为其一个集合,
//这部分在数据依赖性中进行介绍
then B(j)←B(j)+1
endif
i←i+1
repeat
j←j+1; i←1
repeat
end NODE_IN
program NODE_OUT //计算语句节点的出度
int i, j, b(1:n)
//根据语句的相关性构造b(i)记录i语句的出度
i←1; j←2
while i < =number do //number是程序的语句个数
for j←i+1 to number
if < i, j > 属于A then b(i)←b(i)+1 endif
repeat
i←i+1;
end NODE_OUT
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]描述如下:
procedure Dependency(i, j) //语句i, j的相关性
int i, j
if语句i至少有一个输出是语句j的输入
then A←A ∪〈i, j〉 endif
//A为一个集合,用来存储具有相关性的语句
if语句i, j输出的为同一个变量
then A←A ∪〈i, j〉 endif
if语句j的执行需要依赖于语句i
then A←A ∪〈i, j〉 endif
if语句j的输出与语句i的输入为同一变量
then A←A ∪〈i, j〉 endif
end Dependency
procedure Program_Dependency
//判断一个语句块分区内部的所有语句的相关性
integer i, j
read(module_number) //输入语句块分区的编号
A←空
i←1; j←2
while程序不结束do
while i < j do
Dependency(i, j) //判断分区内两个语句之间的相关性
i←i+1
repeat
j←j+1;i←1
repeat
number←j //记录该程序中可并行化执行的语句个数
end Program_Dependency
在生成程序语句块分区的基础上,根据数据依赖性分析算法的描述,进行依赖关系的提取处理,之后调用函数Parallelizing将得到的可并行执行语句保存于数组中,为之后的代码转换提供支持。
procedure Parallelizing
integer i, j, k, num, C(1:n)
//数组C,其中存放程序中可并行执行语句
recall Program_Dependency //调用程序依赖性代码
recall NODE_IN //调用入度函数
recall NODE_OUT 3//调用出度函数
j←1
while数组b的值不全为-1 do //b记录出度全为-1,结束
i←1
while i < =num do
if B(i)=0 then k←i+1
while k < =num do
if〈i, k〉属于A then B(k)←B(k)-1 endif
//语句i的入度数减1
k←k+1
repeat
b(i)←-1 //作标记
endif
i←i+1
repeat
C(j)←i; j←j+1 //用C(j)中的数字将语句块分开
repeat
save(C)
end Parallelizing
经过此步骤,可以完成串行程序的分析工作,即完成整个软件设计的第一个大的部分,在自动转换部分,只需要调用存放于数组中的可并行执行语句编号,即可直接进行转换。
2.5 并行程序代码生成经过程序的粗略划分得到分区模块module_number,对语句块分区和分区内的嵌套循环部分进行数据依赖性分析。具体的操作如下:
1)在头文件中插入#include < mpi.h > 和#include < omp.h > ;
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的源文件传给分析器的代码为:
File file1=new File(args[0]);
FileInputStream fs1=new FileInputStream(file1);
MiniCParser parser=new MiniCParser(fs);
//词法、语法分析,构建抽象语法树
parser.Goal() //获得AST的根节点
SimpleNode root=(SimpleNode)parser.jjtree.rootNode();
//输出抽象语法树
root.dump(">");
其中,“词法分析、语法分析、建立抽象语法树”这些都是通过调用parser.Goal()来实现的。执行它之后,可以通过parser.jjtree.rootNode()来获得所生成的抽象语法树的根节点,调用dump函数,可以查看抽象语法树。
基于这些文件,需要做的就是写若干个实现MiniCParserTranslator.java这个接口的具体的类,在这些类里实现Translator方法,来完成要进行的建立符号表的工作。这个类的主要功能是遍历抽象语法树上的各个节点,然后输出每个节点的类型.如下面的TraversalTranslator.java里的代码:
public Object Translator(ASTGoal node, Object data){
System.out.println("ASTGoal");
node.childrenAccept(new TraversalTranslator(), data);
return data;
}
这段就是当调用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++的控制台应用程序,在项目解决方案资源管理器上进行属性配置。
在验证过程中,首先使用该软件对几种不同的算法,如LU分解算法、矩阵乘算法进行转换,并与手工编写的代码进行比较,验证目标代码功能的正确性。图 3显示的是LU分解算法中的部分代码L和U矩阵的生成转换图。
矩阵乘算法的代码转换如图 4所示。
从图 3和图 4中,可以看出该软件较为良好地实现了串行代码的自动并行化,其生成的代码与手工编写的代码在搭建的环境下进行验证,可以正确地实现算法的功能。接下来,将对不同阶数下的矩阵乘算法,根据其加速比的不同来验证性能的优劣性。具体的数据如表 1所示。
通过比较不同阶数下矩阵乘算法的加速比,使用(手工编写-自动生成)/手工编写的加速比计算方式,得出其性能差异为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. ) (0) |
[2] | 孙尧.基于SUIF平台的程序自动并行化辅助系统研究[D].长春:吉林大学, 2014. ( SUN Y. The research of program automatically parallel auxiliary system based on SUIF platform [D]. Changchun: Jilin University, 2014. ) (0) |
[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. ) (0) |
[4] | DOS REIS A. Compiler Construction Using Java, JavaCC, and Yacc[M]. Hoboken, NJ: John Wiley and Sons, 2012 : 367 -417. (0) |
[5] | KLAWONN A, LANSER M, RHEINBACH O, et al. Hybrid MPI/OpenMP parallelization in FETI-DP methods [C]// Recent Trends in Computational Engineering—CE2014. Berlin: Springer, 2015: 67-84. (0) |
[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. ) (0) |
[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 Cyber-Enabled Distributed Computing and Knowledge Discovery. Washington, DC: IEEE Computer Society, 2012: 309-314. (0) |
[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. ) (0) |
[9] | 陈科.程序流程图结构分析与识别技术的研究与实现[D].西安:西安电子科技大学, 2011. ( CHEN K. Research and implementation of structure analysis and identification for program flowchart [D]. Xi'an: Xidian University, 2011. ) (0) |
[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. ) (0) |
[11] | TANG H, WANG X, ZHANG L, et al. Summary-based context-sensitive data-dependence analysis in presence of callbacks [C]// POPL '15: Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. New York: ACM, 2015: 83-95. (0) |
[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. ) (0) |
[13] | 周健, 孙丽艳. 用JavaCC和JJTree构造扩展模式文档解析器[J]. 计算机技术与发展, 2008, 18 (9) : 87-90. ( ZHOU J, SUN L Y. Designing parser of extended DTD by JavaCC and JJTree[J]. Computer Technology and Development, 2008, 18 (9) : 87-90. ) (0) |
[14] | 祝永志, 张丹丹, 曹宝香, 等. 基于SMP机群的层次化并行编程技术的研究[J]. 电子学报, 2012, 40 (11) : 2206-2210. ( ZHU Y Z, ZHANG D D, CAO B X, et al. Research of parallel programming techniques of hierarchical model based on SMP clusters[J]. Acta Electronica Sinica, 2012, 40 (11) : 2206-2210. ) (0) |