基于社区特性的并行离散事件仿真对象分发方法

摘要

本发明公开了一种基于社区特性的并行离散事件仿真对象分发方法，目的是提出一种新型并行仿真对象分发方法，提高并行仿真在多个处理器上的运行效率。技术方案是：构造复杂系统的模型图G(V,E)，提取出仿真对象及仿真对象间的事件调度关系；采用不断移除最高中心度边的方法对图G进行社区发现，将各个节点聚合到不同社区；构造带权重的社区聚合图G’(V’,E’)；采用多层次K划分方法对G’(V’,E’)进行K划分；根据K划分结果进行并行仿真对象的分发，将划分的各个等份指定分发到具体的计算节点。采用本发明能根据并行仿真所使用的计算资源获得仿真对象分发结果，能有效平衡多计算节点的计算负载和通信负载，显著提高并行仿真的运行效率。

主权项

一种基于社区特性的并行离散事件仿真对象分发方法，其特征在于包括以下步骤： 第一步，从复杂系统中提取出仿真对象及仿真对象间的事件调度关系，构造复杂系统的模型图G(V，E)，模型图G(V，E)由节点和连接边组成，其中节点代表仿真对象，连接边代表仿真对象间存在事件调度关系，V表示节点的集合，E表示边的集合；复杂系统中m个仿真对象间共有n条边，用Nodei 表示模型图中对应于第i个仿真对象的节点，用Edgek表示第k条边，同时用Edgei，j表示连接节点i和j的边，其中0n，则转2.2.7步； 2.2.5判断SWk>value，如为真，则l＝k，value=SWk； 2.2.6k=k+1，转2.2.2步； 2.2.7将第l边的Removed设为1，标记为移除； 2.2.8重新计算模型图中所有边的最短路径权重SW值，ii=ii+1，转2.2.2步； 2.3提取并输出模型图G(V，E)中的社区及社区所包含的节点，由于已经连续移除了具有最高SW值的NumEdgesRemove条边，使整个图分割成多个互不连通的子图，这些子图就是通过社区发现结果得到的社区，用c表示所发现社区的个数，用Commp表示第p个社区，输出模型图G(V，E)中每个节点Nodei 及其所属的社区号Commp，0c，转3.3步； 3.2.3对应于社区Commp，新建一个节点Node′p，Weight′p=SizeCommp，将Node’p加入到图G’(V′，E′)中； 3.2.4p＝p+1，转3.2.2步； 3.3构建社区聚合图的边及其权重，具体步骤如下： 3.3.1令k＝1； 3.3.2若k≤n，执行3.3.3步；若k>n，转3.4步； 3.3.3对模型图G(V，E)中的边Edgek，查找其两个连接节点，设为Nodei 和Nodej；并查询该两节点所处的社区，设为Commp和Commq； 3.3.4若Commp等同于Commq，表明Nodei和Nodej位于同一个社区，Edgek为社区内部的连接边，转3.3.7步；若Commp与Commq不相等，则Edgek 为Commp和Commq不同社区间的连接边，执行3.3.5步； 3.3.5判断社区Commp和Commq在社区聚合图中对应的节点Node′p与Node′q间是否已存在边Edge′pq，若存在，则Weight′pq＝Weight′pq+1，执行3.3.7步；若不存在，则执行3.3.6步； 3.3.6此时Node′p与Node’q间不存在边，向图G’(V′，E′)中增加一条连接Node′p与Node′q的边Edge′pq，并设置Weight′pq＝1，执行3.3.7步； 3.3.7k＝k+1，转3.3.2步； 3.4结束，得到社区聚合图G’(V′，E′)； 第四步：采用基于多层次K划分的METIS方法对社区聚合图G’(V′，E′)进行K划分，得到K个等份，用Parth表示，其中0