Novel methods are presented for parallel simulation of discrete event systems that, when applicable, can use a number of processors much larger than the number of objects in the system being simulated. The simulation problem is posed using recurrence relations, and three algorithmic ideas are brought to bear on its solution: parallel prefix computation, parallel merging, and iterative folding. Efficient parallel simulations are given for the G/G/1 queue, a variety of queuing 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.
展开▼
机译：提出了新的方法，用于对离散事件系统的并行模拟，当适用时，可以使用多个处理器大于正在模拟系统中的系统数量的处理器。 仿真问题是使用复发关系构成的，并在其解决方案上承担了三种算法思路：并行前缀计算，并行合并和迭代折叠。 给出了高效的并行模拟，给出了G / G / 1队列，各种具有全局首先来到的第一服务结构（例如，一系列带有有限缓冲区的队列），队列网络的队列网络以及具有反馈的队列网络 和周期。 特别地，使用P处理器与N / P + LOG P的时间成比例解决了将前N个作业的到达和出发时间模拟到单个G / G / 1队列的问题。
展开▼
