In this paper, we propose the Templet - a runtime system for actor programming of high performance computing in C++. We provide a compact source code of the runtime system, which uses standard library of C++ 11 only. We demonstrate how it differs from the classic implementations of the actor model. The practical significance of the Templet was examined by comparative study on the performance of three applications: the reference code in C ++, managed by the OpenMP; the actor code in C ++, managed by the Templet; the actor code in Java, managed by the Akka. As a test problem we used a numerical algorithm for solving the heat equation.
2 { 3 for (int j=1; j<W-1; j++) field[i][j]=(field[i][j-1]+field[i][j+1]+ field[i-1][j]+field[i+1][j])*0.25; 6 }
1 double seq_alg()
2 { 3 for (int t=1;t<=T;t++) 4 for (int i=1;i<H-1;i++) op(i); 5 }
The Templet actor computing system consists of three main parts: two primitive operations (send and access) and a function for worker threads that process messages (tfunc). In the following listings we illustrate the mechanism for parallel executio n of actors in the shared memory using the C ++ standard library threads.
A message sending operation source code is shown in Listing 3. To send a message is to place the message in a shared queue and notify a thread, which may expect the message in the empty queue (line 6). The queue is protected by a mutex. It is captured in line 5. The message contains a reference to the actor-destination and the sign of being sent. They are initialized in line 4. Line 3 presents a guard of re-sending the message. Resending the message is an emergency situation, indicating that an error occurred in the application code.
1 inline void send(engine*e, message*m, actor*a)
2 { 3 if (m->sending) return; 4 m->sending = true; m->a = a; 5 std::unique_lock<std::mutex> lck(e->mtx); 6 e->ready.push(m); e->cv.notify_one();
7 }
The access to the message object during the actor processing procedure is allowed if the function access (see Listing 4) returns "true". The access is granted if (1) the message refers to the actor, which calls the function; (2) the message is no t on delivery (line 3). This condition is an invariant during the processing of a message in the context of a particular actor, otherwise the message will not be sent by the send operation. Sending messages is allowed only if the actor has access to the message (see Listing 4).
The source code of the worker thread is shown in Listing 5. It implements a thread pool pattern [
The worker thread polls the task from the queue (line 16) and starts the actor’s, message processing procedure (recv). The recv procedure is prepared by several steps: (1) determining the message’s destination actor (line 19); (2) setting the lock on the actor (line 21); (3) changing the delivery sign of message to sending = false (line 22); activating the recv procedure to pro cess the message (line 23).
7 11 8 High-Performance Computing / S.V. Vostokin, E.G. Skoryupina 17 e->ready.pop();
18 } 19 a = m->a;
20 { 21 std::unique_lock<std::mutex> lck(a->mtx); 22 m->sending = false; 23 a->recv(m, a);
}
Note that the captured locks are released implicitly when the thread leaves the syntactic scope of the object lock lck. The actor system computations are stopped when there are no active working threads.
We implemented three parallel versions of the code in Listings 1, 2. All these versions are driven by the following rules of parallelization: t is allowed to start iteration t along the time axis and i along the space axis (t, i), if (1) the iteration (t-1, i + 1) and (t, i-1) have been completed; or (2), if t = 1 and iteration (t, i-1) has been completed. We assume that if an iteration has no i+1 or i-1 neighboring iterations, the neighboring iteration is completed. The first iteration of the calculation (1,1) is performed disregarding these conditions. The algorithm stops when T iterations are performed for each coordinate. The considered computing algorithm can be implemented on the basis of OpenMP, as shown in Listing 6. The idea of parallelization is as follows: either even or odd iterations i can be calculated simultaneously on each count t. A strict compliance with the rules of calculation is guaranteed by the additional check in lines 5, 10 and 15 in Listing 6.
The actor implementations of the algorithm in listing 1, 2 enable using the rules of parallelism explicitly. For this reason, each space coordinate i is matched by an actor. There are N = H-2 actors used in both actor algorithms.
In the Templet implementation, the rules of parallelization presented in lines 5-7 of Listing 7. In lines 11 and 12, the actor informs its’ neighbors i-1 and i+1 (if any) of the completion of the iteration (t, i) by sending messages.
11 if (id != 0) send(&e, &ms[id - 1], &as[id - 1]); 12 if (id != N - 1) send(&e, &ms[id], &as[id + 1]); 13 } 14 }
Listing 7. Actor based parallel algorithm for the heat equation benchmark, Templet runtime.
In the Akka implementation, the rules of the parallelization are declared in lines 7-9 of Listing 8. In lines 13-20 the actor informs its neighbors i-1 and i+1 (if any) that the iteration is completed (t, i) by sending messages. Note that the message handling code in Listings 7 and 8 is implemented identically for the convenience of comparison. The code block in lines 22-24 is stops the computations.
22 1 public void onReceive(Object message) {
2 if (((Integer) message) == id - 1) 3 access_ms_id_minus_1 = true; 4 if (((Integer) message) == id) 5 access_ms_id = true;
6 7 if ((id == 0 || access_ms_id_minus_1) && 8 (id == N - 1 || access_ms_id) && 9 (Main.time[id] <= Main.T)) {
10 11 Main.op(id + 1); Main.ts[id]++;
12 13 if (id != 0) {
Main.actors[id - 1].tell(id - 1, getSelf()); 15 access_ms_id_minus_1 = false;
16 } 17 if (id != Main.N - 1) { 18 Main.actors[id + 1].tell(id, getSelf()); 19 access_ms_id = false; 20 } 21 } if (Main.time[id] == Main.T + 1 && id == Main.N - 1) { 23 Main.system.terminate(); 24 }
24 }
Listing 8. Actor based parallel algorithm for the heat equation benchmark, Akka.
Both actor algorithms have an initialization code, which is not considered in the paper. Complete code of the Actor Templet library and the test cases are available at https://github.com/Templet-language/newtemplet/ .
Computational experiments were performed on a computer with an Intel (R) Core (TM) i3-3220T RAM 4GB, Windows 10 x64. C ++ programs compiled in Microsoft Visual 2015. For Java programs we used the JDK version 1.8 and the Akka library version 2.4.17 deployed on the same computer.
The complexity of the problem may be denoted by H. There are two space-time domain parameters of the calculation: W=H*2, T=H*2. Both depend on H. Note that H also determines the granularity of computing. The bigger the H parameter is, the bigger chunks of data are processed sequentially.
Columns of Table 1 indicate the duration time of the algorithm in seconds: T1JAVA - a sequential Java implementation; T1NATIVE - a sequential C++ implementation; TpAKKA - a parallel Java implementation based on Akka; TpTEMPLET - a parallel C ++ implementation based on the Templet; TpOPENMP - a parallel C ++ implementation based on OpenMP.
To account for temporary fluctuations, the data presented in Table 1 has been statistically pre-processed. Each value in Table 1 is calculated by series of 19 experiments. The value includes only the significant digits, guaranteeing them from getting into the interval [min, max] with confidence factor of 90% (min - minimum, max - maximum time in a series of 19 experiments).
Table 2 shows the efficiency of the test implementation based on the proposed runtime system by the example of the implementations based on Akka and OpenMP. The EAKKA and EOPENMP values show the percentage of the Templet acceleration of reference implementations based on Akka and OpenMP.
T1JAVA, s
H 400 500 600 700 800 900 1000 H 400 500 600 700 800 900 1000
Correctness of the parallelization was checked by piecemeal test for equality of the temperature field values calculated by sequential and parallel method. We used equal random initial field values for parallel and sequential method. The physical interpretation of the calculation results was not carried out, since it is beyond the scope of this study.
The experiments confirmed the high efficiency of the proposed simple implementation of the Templet runtime system for actor calculations. The Templet system has only a slight performance gap in tests performed using OpenMP, and for the small H parameter values (400..600) it is not far behind the Akka, or even exceeds it.
The advantage of actor algorithms for the Templet and Akka is the simplicity of implementation and debugging. The parallelism of the system is described in terms of a simple behavior of each individual actor. Using the OpenMP requires the understanding of the global state of computing at each time, resulting in complex boundary conditions of the algorithm cycles in Listing 6.
Our algorithm is not inferior to the implementation of OpenMP. This result is obtained despite the fact that we used the
expressive possibilities of C ++ Standard Library 11 to simplify the code, neglecting the efficiency. If necessary, it can be
optimized by using the primitive compare-and-swap, as proposed in [
The source of the simplicity of our actor model implementation is a departure from the classical approach proposed by Agha
[
Agha’s approach assumes that the messages are some values that are passed between the actors. They are accumulated in the mailbox - a special system structure associated with the actor. The actor has an access to the message values.
In our implementation, messages are treated as variables that store values. A programmer is not bounded to syntactic rules of access to the message from any actor at any time. However, an access is meaningful and does not lead to violations of logic provided that the function access to the message-actor pair has returned a true value. This approach does not require the implementation of complex logic of copying values between the mailbox and the actor call frame from the runtime system.
The test also showed that despite the fact the native implementation of the test is superior to the Java implementation in terms of performance, the parallel implementation using Akka is the best for the dimensions of the test problem when the H parameter value is 600 or more. This can be attributed to the fact that the scheduling algorithm offered by Akka is more sophisticated than the one offered by the OpenMP.
Templet system, as well as the scheduling algorithm selected to test the implementation based on
We propose a simple implementation of the actor computation model in C ++ 11, and the possibility of its usage in high performance computing. The test example of the heat equation illustrates the high effectiveness of the proposed implementation. It approximates to the effectiveness of OpenMP, and in some cases is superior to Akka. Apart from that, it reduces the complexity of the coding.
The runtime library is used in the object-oriented Templet language [
This work is partially supported by the Russian Foundation for Basic Research (RFBR#15-08-05934-A), and by the Ministry of education and science of the Russian Federation in the framework of the State Assignments program (№ 9.1616.2017/ПЧ).