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 level of a trunk (channel), when a phone call is allocated to this trunk. Allocation status of a trunk affects future 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 segment of its independent trajectory .

External links

• example.com