Synchronization aspects in the method of large-scale simulation, known as parallel discrete event simulation (PDES), analyzed using the models of the time profile evolutions. Time profile is formed with the local virtual times of the processes. Time profile evolution in the simplest cases reminds the growth of the surface in the models of statistical physics. This simplest case considers only local dependences, the message exchange with the nearest neighbors. In the real simulations, the exchange can be with any of the processes, and we can consider the communication network of messages forms the small-world network. We found the enhancement of synchronization with the growing average shortest path of the small-world network. At the same time, the utilization drops down, although on the moderate level. We present the preliminary results of our study. The work is supported by grant 14-21-00158 of the Russian Science Foundation.
The computational platforms for simulations have undergone dramatic changes in recent
years. A number of cores in modern supercomputers has grown up to millions, and computers have
become rather heterogeneous as they consist of a number of CPUs, GPGPUs, and numerical
accelerators [
Parallel discrete event simulation method can be viewed as an interacting set of sequential
simulations of parts of the simulated system, without changing the original dynamics of the simulated
system [
The synchronization protocols [
Model of the conservative algorithm was studied in references [
Consider a system of N logical processes. The communication between LPs is arranged in small-world topology, schematically shown in Figure 1. We create the SW topology as follows. We build a ring of LPs (i.e. each LP has exactly two neighbors), and then randomly add links between different LPs above the regular lattice. The parameter is responsible for the fraction of long-range connections. The so build communication graph can be described by adjutancy matrix , such that ( , ) = 1, if LPi and LPj depend on each other’s state, and ( , ) = 0, if LPi and LPj are independent.
Evolution of LVT profile { }, = 1. . is simulated in this communication topology. We start
from a flat profile: { (0) = 0}, = 1. . , and update it each computational step. After each update we
calculate observables. We average our results over 1000 independent realizations. In our simulation
program, we use library RNGAVXLIB [
Education" (GRID 2018), Dubna, Moscow region, Russia, September 10 - 14, 2018
Conservative synchronization algorithm is based on the idea of preserving all “insecure” actions of LPs, i.e. the actions, which potentially may violate the causality of computation. It is usually implemented with using “block-resume” constructions. The simplest conservative scheme is to let LP processing events, only if its local virtual time is less or equal to the LVT of its neighbors. If the condition is satisfied, this LP is called active, otherwise, the LP is idle. Assuming, that events are Poisson arrivals, one may describe the evolution of LVT profile by the following rule. ( + 1) = { ( ) + ,
≤ { ( )} ( , )=1 , ( ), otherwise, where is a random variable drawn from the Poisson distribution. At each update step we calculate the following observables: 1) Average speed: 2) Average width: 1
∑ =1 ( ) = 〈
[ ( ) − ( − 1)]〉 2( ) = 1 〈∑ =1( ( ) − ̅( ))2〉, where ̅is the average value of LVT: ̅( ) = the paper mean the average over independent copies of the simulation programs.
∑ =1 ( ). The triangular brackets here and further in
The fundamental synchronization primitive in the optimistic algorithm is a rollback, instead of
blocking constructions [
The recovery is usually implemented by passing anti-messages. Message and anti-message carry the same information and differ only by the sign. If both, message and anti-message, meet in the same queue, they annihilate. For example, if an error has occurred at LPi, but it has already sent erroneous messages to LP2, after detecting an error, the LPi sends anti-message to LP2, and rolls back its LVT. But LP2, in its turn, may have already processed the erroneous message and sent the events to others LPs. This causes the avalanche of rollbacks. (1) (2) (3)
Simulation of the behavior of the optimistic algorithm consists of two parts: simulation of forwarding evolution of the LVT profile, and simulation of rollbacks. During the forward evolution, each LPi updates its LVT , increasing it by value , taken from the Poisson distribution with unit mean: ( + 1) = + , ∀ = 1. . .
(4)
To simulate rollbacks, we make each PEs decrease its LVT to the value of LVT of one of its neighbor, chosen with equal probability. We assume that the avalanche length (i.e. number of rollbacks) follows the Poisson distribution with mean . The algorithm of simulation rollbacks is presented by the following pseudocode: = Poisson( ) For = 1 to do:
Choose random LPi Choose random neighbor of LPi LPr
If ( ) > ( ), then ( ): = ( ),
At each update step , consisting of forwarding evolution and rollbacks, we calculate the average speed (2) and the average time profile (3). The parameter of the model is = 1/(1 + ), the ratio of the forward sub-steps to the total number of sub-steps, constituting the one step in .
We show how adding a small fraction of long-range links affects properties of the algorithm.
The speed of the profile for a conservative algorithm in case of regular topology ( = 0) is
approximately equal to ¼ [
The width of the profile grows with time and saturates at value 〈 ∞2 〉. In case of regular topology ( = 0) this saturation value 〈 ∞2 〉 increases with the number of LPs as 2 , with = 1/2. Adding even very small amount of long-range communication links between LPs suppress the desynchronization: 〈 ∞2 〉 does not increase any more with the number of LPs (Figure 2, right).
So, the conservative algorithm on SW networks becomes fully scalable.
We found the average speed of the profile increases as power of q: u(q) = u0(q − qc)v (6)
The critical value qc and the exponent ν does depend on the parameter of SW network p. For the regular lattice (p = 0) qc = 0.143(1) and ν = 1.66(1), and they increase with the number of long-range connections. There is no qualitative difference in the behavior of the width profile (Figure 3, left).
The behavior of the average width also does not change qualitatively with changing the communicational topology. The desynchronization increases with time and saturates at value 〈w∞2〉. The saturation value 〈w∞2〉 growth with the parameter q (Figure 3, right), that means that the higher the progress rate, the less the LPs are synchronized.
The main results of the simulation of LVT profile for conservative algorithms on SW networks are: 1) the speed of the profile is positive and reduces slowly with ; 2) the profile width is finite in the limit of infinite number of LP, i.e. the LPs are well synchronized.
The main results of the simulation of LVT profile for optimistic algorithms on SW networks are: 1) the behavior of the speed and the width of the LVT profile qualitatively does not change with introducing of the long-range communicational links; 2) the average speed of the profile increases as the power of the parameter q; 3) there is a critical value qc, below which the progress of simulation fluctuates around zero; 4) the desynchronization degree grows with the progress rate q.