基于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.）