基于性能势理论对闭排队网络进行梯度估计的并行仿真算法

对Ｍａｒｋｏｖ性能势理论在一类闭排队网络中的应用给出了一种高效的并行仿真算法．针对仿真中占总运算量７０％以上的一类参数矩阵运算的特点，提出了一种新的矩阵元素对处理器的分配方法：“螺旋式”划分法，使该部分矩阵运算在所有处理器上达到了完全负载平衡；针对仿真中样本轨道数据的大量的广播通讯开销，该文提出用“公共随机数”使所有处理器产生相同的样本轨道，从而以增加很小工作量的代价去掉了这部分通讯开销．另外，由于仿真中占总运算量９０％以上的两部分矩阵计算的特征：没有矩阵元素在各处理器间相互交换的通讯开销，该文算法能广泛地适用于各种体系结构的并行机．最后给出了该并行算法在一台ＳＰＭＤ并行机上的计算结果，显示出该算法能取得接近线性的加速比和较高的并行效率．

Derivative Estimates Parallel Simulation Algorithm Based on Performance Potentials for a Class of CQNs

An efficient parallel simulation algorithm is presented for the application of Markov Performance Potential theory to the sensitivity analysis of a class of closed queuing networks. According to the feature of parameter matrix computation, which occupies more than 70% CPU time, a new processor partitioning pattern on matrix entries, Screwy Partitioning, is introdnced, which can make complete load balance among all processors on this part. Inview of the large amount of communication cost to broadcast the data of simulated sample path, we use the Common Random Number (CRN) is adopted to let all processors generate the same sample path, large amount of broadcasting cost by adding a just little workload. In addition, since the two parts of matrix computation that occupy more than 90% CPU time do not need communication cost to exchange matrix's entries, this algorithm is widely applicable to various types of parallel computers. The simulation experiments on an SPMD parallel computer show that this algorithm can achieve near linear speedup.