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$ processors and assuming the number of system components is not smaller than $N$, each component is made a responsibility of a processor, so that the processor is supposed to produce the history of the events of the component.

External links

• example.com