Syntax Tree Development for Automated Serial-to-Parallel Code Translator for Multicore Processors

IntroductionRecently, in order to improve the performance of computing systems, there has been an increase in the number of multiprocessor complexes that allow operating with a large amount of computing.

To solve computationally complex problems in an acceptable time, the development of software modules using multithreaded programming is required. To write parallel programs, highly qualified programmers are needed: an analyst, a programmer, and a testing specialist are required to participate in the work. Companies incur significant financial costs by paying for the work of IT specialists of this class.

Specialized languages, such as Cilk, are useful for parallel programming. Using this language, it is possible to provide function calls asynchronously until the synchronization point is reached in the parent function. This style of parallelism is called divide and conquer, or fork-join parallelism. In it, the program is divided into smaller tasks that are planned for parallel execution. In addition to Cilk, there are specialized libraries, for example, Java Fork Join.

Often, due to the complexity of debugging, a programmer initially has to write a sequential (single-threaded) program, and then adapt the solution into a parallel (multithreaded) equivalent. Therefore, the question of automated (or automatic) conversion of serial code into parallel is relevant. Automatic conversion does not require human intervention, but is accompanied by a number of difficulties in achieving an unambiguous solution (sequential code may have various parallel equivalents). An automated translator uses a dialogue with a programmer to clarify the properties of a serial program in order to obtain the best parallel equivalent, which is thread-safe and optimized for the use of hardware resources and performance criteria.

Currently, there are no programs that allow you to successfully cope with automatic parallelization. This is due, for example, to the presence of nested functions in programs, complex expressions for the formation of cycles, which complicate the analysis of data dependencies. The most well-known software products implementing the automated approach are ^[1,2]: Parawise, Polaris, Cetus, Pluto, Polly, Par4All, CAPO, WPP, SUIF, VAST/PARALLEL, OSCAR, SAPPHIRE. Let's conduct a comparative analysis using the example of Parawise.

Let's consider the steps of the algorithm responsible for converting serial to parallel code in the Parawise software product (see Fig. 1):

1. Getting a sequential code. 
2. Analysis of serial code dependencies based on user data and recording of information in the database.
3. Splitting the input code into tokens (objects created from a token in the process of lexical analysis, for example, “{”, “}”, “ case”, “do”, “else”, “for”, “if”, “sizeof”, etc.) and recording information in the database with the participation of the user.
4. Control of masks (control of maximum and minimum values for conditions) and recording of information in the database with the participation of the user.
5. Calculation and generation of the syntax tree structure and recording of information in the database.
6. Code optimization (reducing memory usage) and writing information to the database.
7. Code generation and the transition to the next section of the code in paragraph 3, or the formation of the result of converting serial code into parallel code.

Figure 1. Parawise algorithmFigure 2 shows the steps for converting serial code into parallel code for the CAPO software product.

Figure 2. CAPO operation algorithm

1. Getting sequential code that needs to be parallelized.
2. Analysis of dependencies in the received sequential code with the processed user data and data entry in the database.
3. Based on input dependencies, DB, user interaction data and variables used in the analysis, the analysis is formed at the level of parallel domain cycles.
4. Optimization of areas and cycles based on analysis at the level of cycles of parallel areas and variables used in the analysis, the formation of optimization of areas and cycles.
5. Based on the data obtained, duplication in blocks is detected. Intermediate data is entered into the database and the user is interviewed for data correction.
6. Performing direct insertion of the received data, code generation, data exchange with the database. 

Note that Parawise and CAPO work according to a similar algorithm, as do the programs Cetus, Pluto, Polly, Par4All, CAPO, WPP, SUIF, VAST/PARALLEL, OSCAR, SAPPHIRE. One of the disadvantages is that these software products are desktop, i.e. they are dependent on the target platform (they cannot be run on different operating systems), and it is also required to monitor software updates. Separately, the user interaction block should be highlighted, in which the user selects the required solution.  The implementation of this block, presented in CAPO and Parawise, eliminates the possibility of automatic parallelism.  This requires the programmer to have knowledge in the field of parallel programming ^[3,4]. The approach proposed in the article allows us to switch to automating the translation of parallel program code with the least operator involvement, since the user interaction unit is self-learning, based on deep learning ^[5,6].

Translator Architecture When developing a translator that allows you to convert serial code into parallel, it was decided to make a web application.

This decision is caused by the following factors:

• the web application does not require installation; 
• all updates occur on the server, are delivered to the user immediately (it is enough to reload the web page); 
• The web application is accessible from anywhere in the world, from any device, and user files will always be at hand if there is an Internet connection. 

The translator project has a microservice architecture (Fig. 3). The application consists of several programs (services):

• request processing service (request handler), 
• syntax tree building service, 
• code conversion service, 
• the database is based on the PostgreSQL DBMS.  

The request processing service allows you to accept user REST requests, namely a request to convert serial code into parallel ^[7,8]. The request specifies the sequential code required for parallelization, as well as the programming language in which it is written. The service also allows you to make queries to the database to get data about the syntax tree and the transformed code.

Figure 3. Translator architecture

The tree building service converts sequential code into a syntactic tree. Writes data about the syntax tree to the database, after writing data to the database, sends a request to complete the construction of the syntax tree to the code conversion service.

Parallel Program generation services The code conversion service takes data about the constructed syntax tree from the database, builds various parallelization schemes for the source program.

Next, the constructed scheme is evaluated according to a set of rules obtained from the database corresponding to the syntax of the text conversion language from the syntax tree, and builds the program text using the principles of parallel programming and writes it to the database ^{[9, 10]}. The creation of a parallel program can be viewed in the sequence diagram (Fig. 4). We will give a description of this diagram.

Figure 4. Diagram of parallel program creation sequences

The client sends a REST (GET ‘/code') request to convert serial code to parallel. The query processor inserts new data into the database code table and gets the ID value of the new field. The next step is for the request handler to send data about the recorded identifier to the syntax tree building service by POST request. The tree building service receives data about the sequential code from the database and converts it into a syntactic tree. The result of the conversion is recorded in the database and transmitted to the code conversion service by a POST request with an identifier. The code conversion service converts the syntax tree into parallel code and writes it to the database.

The program is built in accordance with the microservice architecture. As a plus of microservices, we can highlight the availability of additional features for adding new program functionality to work with other languages: adding a syntax tree or converting to parallel code. In case of a greater load on the part of users, a RabbitMQ or Kafka message broker is added, which allows converting a message (for RabbitMQ – AMQP, Kafka – Kafka protocol) from the source application to the receiver application, thereby acting as an intermediary between them. In this case, the client sends a request to convert the code to the request handler service. The query processor writes data to the database, sends code to the message broker with an identifier and a programming language that needs to be converted into a syntax tree. The tree building service transforms the syntax tree into the required code for a given programming language. After that, data is recorded in the database and the identifier and name of the programming language are sent to the message broker (a system that converts a message from the data source “producer” into a message from the receiving party “consumer"). The code conversion service via a message broker converts the code into a parallel equivalent of the required programming language.

Figure 5. Translator architecture using a message broker

Figure 6. Diagram of the sequences of creating a parallel program using a message broker

Building a syntax tree During the design, various syntax tree formats were considered.

 The most popular is ANTLR4, a lexical analysis library for Another Tool for Language Recognition (ANTLR).

The principle of operation of ANTLR is based on the syntactic analysis of the input data stream, building a syntax tree, traversing this tree and providing a generated API for implementing logic for each of the traversal events. The API is generated based on a “grammar” that defines the structure of a sentence, individual phrases/words and specific symbols. However, this library has been written for a long time, as a result of which it lacks support for modern programming languages and requires additional libraries at runtime. The next common syntax tree format is Babel AST.

The disadvantages of this format include the lack of support for the C programming language and a large amount of transmitted data. Based on the identified shortcomings of the considered solutions, it was decided to develop a syntax tree with its own format.

 The developed syntax tree is characterized by the following stages:

• Lexical analysis of the input program. This process is characterized by analytical analysis of the input sequence of characters into recognized groups – tokens – in order to obtain identified sequences called "tokens" at the output (similar to grouping letters in words). 
• Syntactic analysis or syntactic parsing is the process of matching a linear sequence of lexemes (words, tokens) of a natural or formal language with its formal grammar.
• Semantic analysis is applied to the resulting structure, the process of identifying the "meaning" of syntactic constructions. An example is associating an identifier with its declaration, data type, definition of the resulting expression data type.
• Next, the conversion is performed to intermediate code (in our case, this is code in JSON format).  

Let's look at a simple example of conversion to a syntax tree. We send a JSON parcel with a sequential code to the input: 

{

  "code": "int main()n {n for(int i=0; i<=4; i++)n{n printf("Text"); n} n return 0;n}",
  "language": "C"
}Where code is sequential code intended for parallelization; language is the programming language in which the code is written. 

We get the formed syntax tree:

{  "tree": [

    {
      "type": "Program"
    },
    {
      "type": "FunctionDeclaration",
      "typeVar": "int",
      "id": "main",
      "params": [],
      "body": [
        {
          "type": "ForStatement",
          "init": [
            {
              "type": "VariableDeclaration",
              "id": "i",
              "value": "0",
              "variable": "int"
            },
            {
              "type": "CompareExpression",
              "id": "i",
              "mark": "<=",
              "number": "4"
            },
            {
              "type": "UpdateExpression",
              "id": "i",
              "operator": "++",
              "prefix": "false"
            }
          ],
          "body": [
            {
              "type": "StringFunctionDeclared",
              "value": "Text"
            }
          ]
        },
        {
          "type": "ReturnStatement",
          "argument": {
            "type": "Literal",
            "value": "0"
          }
        }
      ]
    }
  ]
}Description of the fields used:

tree – the root tree of the project;

• type – the type of the described block;
• TypeVar – data type;
• id – the name of the identifier;
• params – parameters of the described object;
• body – the body of the described block;
• init – initialized parameters;
• value – the value of the specified parameter;
• variable – type of variable;
• mark – the meaning of the sign;
• number – the value of the number;
• operator – the value of the operator;
• prefix – using the prefix;
• argument – the value of the argument. 
• Conclusion 

This article analyzes the existing implementations of serial code translators into parallel code, presents the architecture of a fundamentally new translator, and describes the syntax tree.

An example of the formation of a syntactic tree is also demonstrated, the construction of which is provided by the performance of lexical, syntactic and semantic analyses. In the future, it is planned to expand the structural representation of the syntactic tree, to supplement the code conversion service with modules for converting serial code into parallel code using a neural network approach ^[11,12].