unboundedly parallel simulations via recurrence relations
New methods are presented for parallel simulation of discrete event systems that, when applicable, can usefully employ a number of processors much larger than the number of objects in the system being simulated. Abandoning the distributed event list approach, the simulation problem is posed using recurrence relations. We bring three algorithmic ideas to bear on parallel simulation: parallel prefix computation, parallel merging , and iterative folding . Efficient parallel simulations are given for (in turn) the G/G/1 queue, a variety of queueing networks having a global first come first served structure (e.g., a series of queues with finite buffers), acyclic networks of queues, and networks of queues with feedbacks and cycles. In particular, the problem of simulating the arrival and departure times for the first N jobs to a single G/G/1 queue is solved in time proportional to N/P + log P using P processors.
parallel simulation parallel simulation method event systems processor object distributed computation efficiency queue queueing networks network global structure buffers feedback timing log