The paper presents the implementation of the code generation mechanism in the Green-Marl domain-speci c language compiler targeted at the Charm++ framework. Green-Marl is used for parallel static graph analysis and adopts imperative shared memory programming model, while Charm++ implements a message-driven execution model. The description of the graph representation in the generated Charm++ code, as well as of the translation of the common Green-Marl constructs to Charm++, is presented. The evaluation of the typical graph algorithms (Single-Source Shortest Path, Connected Components, and PageRank) showed that the Green-Marl programs translated to the Charm++ have almost the same performance as their native implementations in Charm++.
A parallel static graph analysis on high-performance
computing systems (supercomputers) is one of the
recent application domains which is characterized by a
domination of irregular data processing rather than
massive bulks of oating point operations which are
common in other scienti c applications used for
supercomputers. The key challenges of parallel graph
processing are discussed in [
The paper presents the results of the e orts to integrate a Charm++ support to the Green-Marl compiler. Green-Marl is an open-source domainspeci c programming language (DSL) designed for static graph processing. Charm++ is an asynchronous message-driven execution model developed to execute parallel programs on multiprocessor computing systems. Charm++ relies on its runtime system to schedule computation, as well as perform dynamic load balancing.
For the translation of Green-Marl programs to Charm++ a code generation module has been developed in the Green-Marl compiler that uses the existing internal representation of a Green-Marl program for Charm++ code generation. For performance evaluation we used three well-known graph problems: SingleSource Shortest Path (SSSP), Connected Components (CC), and PageRank. We compared the performance of the generated code to the hand-coded reference implementations.
In the next section an overview of research e orts on asynchronous computation models and graph-speci c DSLs is presented. In section 3 a brief description of the Green-Marl DSL is presented, section 4 contains an overview of the Charm++ programming model. Section 5 shows the main technical aspects of translating Green-Marl programs to Charm++. Section 6 presents results of the performance evaluation. The nal section contains conclusion and future work. 2
A usage of common approaches to the development
of parallel graph applications for massive parallel,
distributed memory systems such as MPI or Shmem in
combination with OpenMP is complicated due to its
limited support for expressing irregular parallelism
and implicit orientation on statically balanced
parallel bulk-synchronous problems, and, therefore, the
complexity of implementing parallel graph algorithms
falls on the application developer. In contrast, the
asynchronous data- ow computational models enable
almost transparent mapping of the graph algorithms.
The examples of such models which are built on top of
asynchronous active messages concept are Charm++
[
Even better productivity of the graph application
development can be achieved with a usage of
highlevel domain-speci c languages which enable to shift a
major part of work on the control of parallel execution,
including task spawning, communication,
synchronization, etc. to the compiler and dynamic load
balancing and a failure resiliency { to the runtime system.
There are few DSLs speci cally developed for a
parallel static graph analysis such as Green-Marl [
Green-Marl [
Green-Marl supports special types for declaration of graphs (Graph), vertices (Node), and edges (Edge), as well as declaration of vertex properties (N P<type >) and edges properties (E P<type >).
Besides the While and Do-While constructs used for de ning sequential loops and If and If-Else for branches, Green-Marl provides statements for parallel execution such as For and Foreach loops. The semantics of the parallel loops assumes that all computations should be nished before the rst operation after the loop is executed. However, the order of the iteration execution is not de ned.
Green-Marl supports the following reduction operators +=, *=, max=, min=, &&=, ||=. These operators can be used in parallel loops to produce reduction assignments. 1 Procedure sssp(G:Graph, dist:N_P<Int>, len:E_P<Int>, 2 root: Node) 3 { 4 N_P<Bool> updated; 5 N_P<Bool> updated_nxt; 6 N_P<Int> dist_nxt; 7 8 Bool fin = False; 9 G.dist = (G == root) ? 0 : +INF; 10 G.updated = (G == root) ? True: False; 11 G.dist_nxt = G.dist; 12 G.updated_nxt = G.updated; 13 14 While(!fin) { 15 fin = True; 16 Foreach(n: G.Nodes)(n.updated) { 17 Foreach(s: n.Nbrs) { 18 Edge e = s.ToEdge(); 19 <s.dist_nxt; s.updated_nxt> 20 min= <n.dist + e.len; True, n>; 21 } 22 } 23 G.dist = G.dist_nxt; 24 G.updated = G.updated_nxt; 25 G.updated_nxt = False; 26 fin = ! Exist(n: G.Nodes){n.updated}; 27 } 28 }
In Figure 1 an implementation of the Bellman-Ford algorithm for nding the shortest paths from the speci ed vertex to other vertices in the graph is presented. The program consists of a single procedure (sssp) with four parameters: G is a graph to be analyzed, dist is a vertex property storing the distance from the source vertex, len is an edge property storing the edge length (or weight), and root is a source vertex.
In the initialization step (lines 8-12) dist is set to +INF for all vertices except the root vertex which dist is set to zero. Also, the root vertex is marked by setting its update property to true which signi es that the vertex will be processed in the rst iteration of the While loop (lines 14-17). Then the While loop is executed. It completes when fin is set to true that is there is no more updated vertices in the graph. In each iteration of the While loop a parallel Foreach loop is executed (lines 16-22), which scans vertices and for each previously updated vertex (i.e. its updated property is set to true) checks neighbour vertices by executing a relaxation operation: if dist[v] + weight(v,u) < dist[u] for the (v,u) edge then dist[u] is assigned to dist[v] + weight(v,u) (lines 19-20). The number of iterations of the While loop is restricted to jV j 1 (upper bound).
Therefore, Green-Marl is an imperative domainspeci c programming language designed for a parallel static graph analysis. Green-Marl allows to signi cantly simplify the development of parallel graph applications by its builtin specialized high-level abstractions as well as the diverse set of the compiler optimizations. However, it still lacks the support of the translation to e ective programming platform for HPC systems with distributed memory. 4
Charm++ [
In Charm++ a program consists of a set of chares, implemented as C++ objects, that have an interface of prede ned methods (entry methods) which can be used to transfer data between chares and initiating asynchronous computations, that is caller thread will proceed its execution. A mapping of chares to process elements (PEs) is done statically by the Charm++ runtime (by default) or by application developer. Typically, PE can be regarded as a CPU core (or an operating system process assigned to a CPU core). Additionally to stand-alone chares, single-dimensional and multi-dimensional chare arrays are supported.
For addressing chares special proxy objects are used that provide an abstraction of global address space and enable the Charm++ runtime to manage location and distribution of chares transparently for application. This allows to use dynamic load balancing by migrating chares from more loaded nodes to less loaded by the runtime system. A migratability of chares is another base concept of the Charm++ programming model.
The following properties of the Charm++ model: rst, an entry method can only access data which belong to the chare that it is called on, and, second, that only single entry method can be executed on a chare at a time, guarantee the atomicity of modi cations of chare's data in Charm++ that signi cantly simpli es application development. 5
5.1
Compiler Overview
The Green-Marl compiler performs a source-to-source
translation from Green-Marl to one of the possible
equivalent representations: a sequential C++ code,
a parallel code for shared memory systems in C++
with OpenMP pragmas, a parallel code for distributed
memory systems in Java on top of Pregel [
The general scheme of Green-Marl is shown in Figure 2. The main stages of translation are the following: a lexical and syntax analysis (type checking, a syntactic sugar expansion etc.), platform independent optimizations (such as loop splitting and merging, loop-invariant code motion etc.), platform speci c optimizations and a nal code generation.
An internal representation of the program in the Green-Marl compiler includes an abstract syntax tree (AST) and a control- ow graph (a nite state machine, FSM), the nodes of the graph (or extended basic blocks, EBB) correspond to linear blocks of code in the translated program. Each EBB contains information about local variables, incoming and outgoing dependencies, code statements, etc.
The FSM states can be of two types: sequential
(SEQ) and parallel (PAR). The sequential nodes
correspond to the code blocks in which the statements
should be executed in the strict order. The parallel
nodes correspond to the code blocks which suggest
execution for each vertex of the graph in parallel (Foreach
and For loops).
The developed Charm++ code generator is based on
the GPS generator developed for translating
GreenMarl programs to the Pregel execution model, a full
description of the GPS generator can be found in [
At the same time, to prove the concept of the possibility to translate Green-Marl programs to Charm++ it was su cient to implement the last stage of the compiler { code generation from the internal program representation (IR). Further, a description of the translation methods is presented for main Green-Marl constructs. As an example, a program for calculating a mean age of all registered users of a social network whose age is less than K. The source code of the GreenMarl program and the generated code in Charm++ are shown in Figure 3.
Graph representation in the generated code For a graph representation in the generated code in Charm++ the most simple and natural approach has been chosen: vertices of the graph are mapped to the chares (i.e. the elements of the chare array), which are de ned in the code by the name vertex class, name is a name of the translated Green-Marl procedure.
The vertex properties data structure is used for storing vertex attributes, while edges is used for { an edge list of the vertex, each edge is a pair of a neighbour identi er and its attributes (edge properties). As a 1-dimensional chare array (array [1D]) is used for storing graph vertices then the vertices are distributed in contiguous blocks over parallel processes (or cores) by the Charm++ runtime system.
In the example (see Figure 3) the vertices are represented by the count vertex class (Figure 3 (b), lines 14{18, 3, lines 26{52). The vertices have a single attribute age, which is stored in the vertex properties class. As the attributes for edges are not de ned in the Green-Marl program then edge properties does not have any eld.
As it has already been mentioned, after the controlow analysis the Green-Marl compiler creates a nite state machine (FSM). For managing the execution of FSM a special chare (name master) is created, each state of FSM is mapped to one of the entry methods: ep state i, where i is a number of the FSM state. The program starts with the execution of ep state 0 then the states are switched according to FSM. When PAR states are executed, an appropriate call is initiated to all chares of the name vertex class (i.e. array elements). Then master (name master) waits until all computation are done (by using a quiescence detection) and then an entry method correspondent to the next FSM state is executed. The process continues until the terminal ( nal) state is called.
In the example FSM consists of three states (see Figure 4) which correspond to the following entry methods of the count master: ep state 0, ep state 1 and ep state 2. As the state 1 is parallel, then it has a correspondent entry method in the count vertex class ( ep state 1). In the terminal state (state 2) the callback (done callback) is triggered to move control ow to the boiler-plate code (or code of the Green-Marl program loader).
In Green-Marl, all variables can be of two types: global and local (for vertices). The global variables are declared in the sequential code blocks and can be accessed from the parallel code blocks. All global variables are stored in the name master class as its member variables. In case of a read access to the global variable from the Foreach loop, its value is passed as a parameter of the correspondent entry method to all vertices (name vertex). In case of a write access then the correspondent entry method of name master is called, however, when write accesses operations are performed to the same global variable from the multiple vertices then race conditions occur and the behaviour is unde ned.
The Green-Marl compiler applies the contribute operation supported in Charm++ to implement reductions which can be used in Green-Marl programs. In Charm++ there are several supported reductions operations which can be applied to the chare array elements, the mechanism suggests that a speci ed entry method (of the speci ed chare) is called when reduction is completed which has to be marked with reductiontarget keyword and has a single parameter which will store the result of the reduction.
In the example (see Figure 3) three global variables are used (S, C, K). The K value is used inside the Foreach loop, therefore ep state 2 in count vertex receives K as one of the parameters of the ep state2 msg structure, which is a Charm++ message (message). S and C are used for the reduction results (lines 7, 8). In the generated code there are two methods in the count master class: reduction S (line 3) and reduction (line 4) which are used for passing the reduction results to the S and C variables.
In conclusion of this section we can say that for implementing Charm++ support in the Green-Marl compiler it was su cient to add a new code generation module to the existing backend chain for GPS code generation. However, as it has been mentioned, Charm++ has signi cantly more exibility and generality than Pregel that is why it provides wider possibilities to the compiler as well as to the domain-speci c language itself. Using of these possibilities is the topic of further research. 6
For benchmarking a 32-node Angara-K1 cluster has
been used, we used its 24-node segment with dual
6core Intel Xeon E5-2630 processors and 64 GB of
memory in each node. The nodes are connected by a
custom 4D-torus Angara interconnect [
The benchmarks used for the performance evaluation include: Single-Source Shortest paths (SSSP), Connected Components (CC), and PageRank. We compared the performance of Green-Marl programs to their hand-written Charm++ invariants (or reference implementations).
We used two types of synthetic graphs: RMAT [
The performance results are shown in Figure 5. In all plots the graph size is 222 vertices. For SSSP and PageRank directed graphs have been used, while for CC { undirected.
For SSSP (as well as for CC) the two di erent reference implementations in Charm++ have been used. The rst is sssp-async (cc-async) and it implements a fully asynchronous algorithm which employs a label updating approach. For SSSP the updated label is a distance from the root vertex (dist) in each vertex, while for CC { identi er of connected component (CC). The computation process continues until any update is possible. When there is no more updates in the graph then the algorithm nishes, this is controlled by a quiescence detection mechanism, supported in Charm++. Another reference implementation sssp-adapt (cc-adapt) is similar to the rst except that a global synchronization is used to control label propagation (the new labels are sent only to the neighbour vertices of the front and then a global synchronization is performed). In Green-Marl implementations of the tests it is achieved by the outer loop While.
As can be seen from Figure 5, for SSSP and CC the performance of Green-Marl implementations is very close to the performance of the reference implementation with a partially synchronized algorithm (sssp-adapt for SSSP and cc-adapt for CC). For CC the adapted reference implementation shows even better performance than asynchronous one. It can look unexpected, but the following reasons of such behaviour are possible: rst, while the partially synchronized algorithms (sssp-adapt and cc-adapt) restrict the amount of available parallelism, at the same time the number of active messages sent during execution of the programs is also signi cantly restricted, thus resulting in less overheads from the runtime system and less memory consumption, and, second, the fully asynchronous implementations (sssp-async and cc-async) generate many speculative computations (speculative wavefronts), for example propagating of the distance which is not minimal for SSSP. It results in large amount of unnecessary computations and degradation of performance. For the partially synchronized implementations the amount of speculative computations is signi cantly lesser.
The evaluation of PageRank has not revealed any signi cant di erence in performance between reference and Green-Marl versions. In the rst order, it is explained by the fact that for both cases the algorithms are very close (almost the same). 7
In the paper the Charm++ code generator developed for the compiler of the domain-speci c language Green-Marl is presented. Therefore, the Green-Marl DSL is extended to HPC clusters with distributed memory: Charm++ is added to already supported OpenMP, GPS, and Giraph target platforms.
The performance evaluation shows that Green-Marl
programs compiled to Charm++ have the same
performance as native Charm++ programs assuming that
the same algorithms are used in the generated code
and the reference implementation. In the future we
plan to add a support of the Topological Routing and
Aggregation Module (TRAM) [
This work is partially supported by Russian Foundation for Basic Research (RFBR) under Contract 1507-09368. 8 16 (c) PageRank, RMAT-22 pagerank (Green-Marl) pagerank (Charm++)
4 nodes 4 nodes (a) SSSP, RMAT-22
sssp (Green-Marl) sssp-async (Charm++) sssp-adapt (Charm++) 0 1 2 (b) CC, RMAT-22
cc (Green-Marl) cc-async (Charm++) cc-adapt (Charm++) 4 nodes 2 8 16 1 2 8 16 1 2 8 16 (d) SSSP, Random-22 (e) CC, Random-22 sssp (Green-Marl) sssp-async (Charm++) sssp-adapt (Charm++) cc (Green-Marl) cc-async (Charm++) cc-adapt (Charm++) pagerank (Green-Marl) pagerank (Charm++)
4 nodes