User:Lsalgo/Synchronous Relaxation for Parallel Discrete Event Simulations

Synchronous Relaxation for Parallel Discrete Event Simulations is a method to perform a discrete event simulation on a parallel computer. The Synchronous Relaxation (SR) method is general in that it makes no use of specifics of the simulated system and it is computationally efficient in that it typically delivers the speedup of the order of $\ N/\log(N)$, where $\ {N}$ is the number of processors in the parallel computer.

When the SR is applicable

A model of a multi-component dynamic system with discrete events might be suitable for a SR simulation. The time is assumed to be continuous in such a model. The system state can change only instantaneosly and only by changing the state of a component. This is identified as a discrete event that occurs in that component. The event may affect future events in this and other components. Examples of such models are numerous: telephone networks models, models of Ising spins, models of collision detection of particles, to name a few.

In a circuit-switched telephone network, an event is a change of the occupancy levels of trunks (channels) along a path or a network of trunks, this path or network is called a circuit, when a phone call is allocated (placed) to or de-allocated (removed) from the circuit. Occupancy level of a trunk affects future allocations or de-allocations of this and other trunks via the logic of the allocation algorithm. The comparative behavior of various allocation algorithms is a subject of the study in this simulation, where both, the SR method of parallel simulations and the term "Synchronous Relaxation" itself in the application to parallel simulations, were originally introduced .

A system of Ising spins is a set of atoms in space so that each atom has a few neighbors. Each atom has a state, called "spin". Atoms change spins at asynchronous random times, which the model assumes to be independent of spins. When an atom changes its spin, the new spin is a function of the existing spins of its neighbors and itself .

In a collision detection model, for example, in a model of chaotically colliding billiard balls, the motion of each ball is independent of other balls as long as the paths do not cross. Occupancy conflicts in pairs of balls are resolved through collisions. At a collision, which the model assumes to be instantaneous, the two participating balls change the directions and speeds of their motions and then each continues with the next independent segment of its trajectory .

How the SR works

Having a parallel computer with $\ N$ processing elements (PEs) and assuming the number of system components is not smaller than $\ N$, each component is made a responsibility of a PE, so that the PE is supposed to produce the history of the events of the component.

Each PE will keep track of the simulated time $\ t$ such that on the interval $\ [0,t)$ all histories are known; this $\ t$ is called committed time. Committed time increases in steps, in synchrony among all PEs; its value is common to all PEs. Each step consists of several iterations.

At each iteration, each PE produces a tentative or speculative history of the subsystem it hosts beyond the current $\ t$ . The PE extends its local history until its local time reaches $\ t+\Delta t$, where $\ \Delta t$ is the step size of committed time increases. Since subsystems are, in general, connected, in order to produce a correct local history, a PE needs to know the correct local histories of other PEs. But they are not known, because other PEs are in the same quandary.

Under the condition that somehow a PE knew the correct histories of all others, it would produce a correct history for itself; when all PEs produce correct histories, then the next committed time will become $\ t+\Delta t$ . So all that is left to explain is how to achieve this condition.

The mechanism is by iterations. During the first iteration, each PE makes the simplest assumption about the histories of the other PEs. For example, it may assume that the states of the other subsystems do not change on the interval $\ [t,t+\Delta t)$ . This assumption will enable it to produce its own history on the interval $\ [t,t+\Delta t)$ .

After all the PEs generate local history on the interval $\ [t,t+\Delta t)$ , they compare their histories. This comparison is done in synchrony, in the sense that the PEs perform the comparison only after they have all completed the previous task of generating their histories.

As a rule, there will be inconsistencies between the assumed and actual (generated) histories of other PEs. If so, the PEs need to perform more iterations. During subsequent iterations, if a PE needs to know the local history of another PE, it uses that history generated in the last iteration. The goal of producing correct histories on the interval $\ [t,t+\Delta t)$ is achieved if no PE detects any inconsistencies between the assumed and actual history of any other PE. Once this happens, the new committed time for all PEs becomes $\ t+\Delta t$ , and the parallel computer can begin to work over the next increase of the committed time.

External links

• example.com