CN101944045A - Method for distributing parallel discrete event simulation objects based on community characteristics - Google Patents

Abstract

The invention discloses a method for distributing parallel discrete event simulation objects based on community characteristics and aims to provide a novel method for distributing parallel simulation objects and improve the operation efficiency of parallel simulation on a plurality of processors. According to the technical scheme, the method comprises the following steps of: configuring a model graph G (V,E) of a complex system; extracting the simulation objects and the event dispatching relation between the simulation objects; performing community discovery on the diagram G by a method of continuously removing an edge with a highest centrality and aggregating each node to different communities; configuring a weighted community aggregation graph G' (V', E' ); performing K division on the G' (V', E' ) by a multilevel K division method; and distributing the parallel simulation objects according to the result of the K division so as to distribute each divided part to a specific computing node. By the method, distributing results of the simulation objects can be obtained according to computing resources used by the parallel simulation; and calculation and communication loads of a plurality of computing nodes can be effectively balanced and the operation efficiency of the parallel simulation can be remarkably improved.

Description

Parallel discrete events simulation object distribution method based on community's characteristic

Technical field: the present invention relates to the simulation object distribution method of parallel discrete events simulation, especially towards division and the distribution method of parallel discrete events simulation object on multiprocessor with community's characteristic of parallel or cluster computer.

Background technology: parallel discrete events simulation (PDES, Parallel Discrete Event Simulation), can be called for short parallel artificial, it is the important method of scale complex system being carried out modeling and simulation research, it is by a plurality of ingredients with complication system---and simulation object (or artificial physical) is distributed to executed in parallel on a plurality of processors, obtain the operation speed-up ratio, improve simulation run efficient.Parallel discrete events simulation adopts discrete event to drive modeling pattern, all kinds of simulation objects (Simulation Object) of forming complication system are carried out modeling, realize data communication and mutual by event scheduling between simulation object, whole simulation system is handled by parallel event and is advanced.Parallel artificial adopts the virtualized thought of processor, when emulation is disposed the simulation object example is distributed to concrete physical computing node, therefore can carry out on the computing node of different parallel computation environments or different numbers.The parallel artificial kernel can be converted to the event scheduling between simulation object on the various computing node remote message automatically and send, event scheduling on the same computing node then directly copies to pending list of thing by the shared drive mode, and its expense is less than remote message and sends.Because the employed computing node number of parallel artificial is uncertain often before its operation,, reaches and to make full use of the target that many computing nodes resource can efficiently be moved emulation again so need the support of simulation object distribution method flexibly.

Because often comprise a large amount of objects in the scale complex system, number is thousands of, intricate alternately between object makes the division of simulation object and distribution become the key factor that influences the parallel artificial operational efficiency.At first, because the execution time of whole parallel artificial is depended on the computing node that working time is the longest, the computational load of each computer node needs balanced, and promptly the quantity of simulation object that is carried and event handling will be about equally.More existing parallel artificial platforms, as μ sik, SPEEDES, ROSS etc., the simulation object distribution method of employing has SCATTER, BLOCK, random distribution and User Defined mode.SCATTER method (also claiming round-robin method) is distributed one by one according to distributional mode, for example 10 simulation objects is distributed to 3 computing nodes, and then the Distribution Results of SCATTER is [{ 0,3,6,9}, { 1,4,7}, { 2,5,8}], be about to 0,3,6, No. 9 simulation object and be distributed to node 0, all the other and the like.The BLOCK method is to carry out the distribution of simulation object according to partitioned mode, earlier simulation object is divided into impartial piece according to numbering, distributes then.The BLOCK Distribution Results of last example can be [0,1,2}, 3,4,5}, 6,7,8,9}].The User Defined mode then is to be responsible to define the simulation object distribution policy by the emulation user, the appointment of need encoding in program.Said method can be referred to as the balanced distribution policy of computational load.The second, the communication overhead (100 μ s level) between the consideration computing node differs 100 times nearly much larger than the communication overhead (1 μ s level) of intra-node, therefore also needs to consider to minimize internodal communication on the basis of computational load equilibrium as far as possible.There is document that the interactive relation between simulation object and each object is built into a figure (Graph) at present, utilize the figure division methods (K-cut algorithm etc.) in the mathematics graph theory that this figure is carried out the K division, can with this figure approximate equality be divided into K part and minimize connection between the each several part as far as possible, according to dividing the result simulation object is distributed on K the computing node then.But it is a np problem of generally acknowledging at present that figure divides, and is difficult to try to achieve optimum solution under sweeping situation.In addition, for the Simulation Application of some particular types, it calculates and traffic load is concentrated in some zone, is fit to adopt according to space-time dividing region method, for example in the traffic simulation calculated amount of busy crossroad with communicate by letter relatively largely, can divide according to the area of space of crossroad.In addition, balancing dynamic load (Dynamic Load Balancing) method also is used widely in parallel artificial.Load on each computing node of status information Dynamic Maintenance when balancing dynamic load moves according to system, owing to simulation object need be moved between different computing nodes, therefore the expense cost and obtainable benefit that need comprehensive balance migration in use cause it to use difficulty bigger.These class methods can be described as calculating-traffic load method for equalization and distribution.

In recent years, a large amount of positive researches find that the annexation between simulation object is not a stochastic distribution often in the complication system, and present certain community structure (Community Structure) and tissue (Organization) characteristic.Some simulation objects can in the body that gathers in a flock, the connection of colony inside is dense relatively, the connection between the different groups is then sparse relatively.This group structure characteristic is commonly referred to as community (Community).Correlative study shows in the complication system (as social system, electric system, information network, military bloc etc.) of many types and all comprises community structure, even we can say that community's characteristic has universality.These community's characteristics have different implications in dissimilar application, for example community can refer to the population in family, friend or somewhere in social emulation, in biosystem emulation, can refer to the structural unit that function is relevant, the collections of web pages that in internet, applications, can refer to associated topic, or the like.Because the connection of community inside is than comparatively dense, the connection between community is sparse relatively, corresponding to Simulation Application, when emulation is carried out in the community between simulation object alternately also can be frequent relatively, the rareness alternately of simulation object between community.This is remarkable especially in emulation such as Social Dynamics, and for example in the infectious disease microscopic simulation, the virus carrier can be some more with the chance that its relatives, friend contact, and it is higher relatively to cause infecting probability.

So-called community discovery is meant that utilization community discovery algorithm excavates the middle inherent community structure of publishing picture.The basic thought of community discovery method is the cohesion tolerance according to node, recursively network chart is merged or divides, and network chart is decomposed into nested community's hierarchical structure.In this field multiple community discovery method has appearred at present, as minimum-cut figure division methods, modular approach and information flow method etc.Though community discovery and figure division methods have certain similarity, but have some key distinctions: (1) figure division methods attempts figure is divided into the part of equal sizes, this is worthless from the angle of community's characteristic, because community's number that exists among the figure and size are uncertain.Analyze and find that the size that comprises community in many illustratons of model is the distribution of power rate, wherein.This means that most communities are small-sized or medium-scale, but very large-scale community may exist also.For example, film performer's cooperative relationship model is carried out community discovery, community's size (being the simulation object number that comprises in the community) is for the community of 10-200 accounts for 62.5% altogether, and maximum community's size is 28385, but the number rareness.(2) connection between community is not that the strictness that the figure division methods requires minimizes, and some big intercommunal connection may be more.In a word, because the figure division methods also reckons without in the system the mutual characteristic of polymerization in the simulation object community, divide and pursue equal portions stiffly, therefore, community-based model division methods can more gear to actual circumstances than pure figure division methods, thereby also more superior, the scale complex system emulation that especially is fit to have social characteristic.

In the research of complication system modeling and simulation, pervasive community's characteristic will help improving the operational efficiency of complication system parallel artificial, and the community's characteristic that how the to make full use of complication system discrete events simulation object distribution that walks abreast is the major issue that those skilled in the art pay close attention to.Still no-trump community characteristic applies to the report that the parallel artificial object is distributed both at home and abroad.

Technical scheme: the technical problem to be solved in the present invention is how to utilize community's characteristic of scale complex system and a kind of novel parallel artificial object distribution method that proposes, community's characteristic is incorporated in the parallel simulation system, with the community is that unit carries out polymerization to simulation object in the analogue system, and the polymerization figure of community is divided according to the computing node number, instruct the distribution of simulation object by the division result, thereby reduce the mutual expense in the community, improve the operational efficiency of parallel artificial on a plurality of processors.

Concrete technical scheme of the present invention is:

The first step extracts the event scheduling relation between simulation object and simulation object, the illustraton of model of complex structure system from complication systemG (V, E)Illustraton of model is made up of node and fillet, and wherein node is represented simulation object, and fillet is represented and had the event scheduling relation between simulation object.Suppose in the complication system totalmIndividual simulation object, total between simulation objectnThe bar limit is usedNode_iAmong the representation model figure corresponding toiThe node of individual simulation object is usedEdge_kExpression thekThe bar limit is used simultaneouslyEdge_{I, j}The expression connected nodeiWithjThe limit, wherein0＜i≤m, 0＜j≤m, 0＜k≤nThe concrete steps that make up illustraton of model are as follows:

1.1 the non-directed graph of a newly-built sky is usedG (V, E)Expression, whereinVThe set of expression node,EThe set on expression limit.WithsThe expression node setVSize, be initially 0;

1.2 orderI=1

1.3 ifI≤m, carried out for 1.4 steps; IfI〉m, illustrate all simulation objects are disposed that illustraton of model has been constructed and finished, changeed for 1.10 steps;

1.4 toiIndividual simulation object makes up a new nodeNode_i, and willNode_iJoin figureG (V, E)In,S=s+1

1.5 orderJ=1

1.6 ifJ≤s, carried out for 1.7 steps; IfJ〉s, changeed for 1.9 steps;

1.7 judgement simulation objectiWithjBetween whether have event scheduling relation, if there is the event scheduling relation, to figureG (V, E)Add a connectionNode_iWithNode_jNonoriented edgeEdge_{I, j}

1.8J=j+1, changeed for 1.6 steps.

1.9I=i+1, changeed for 1.3 steps.

1.10 all simulation objects and relation thereof have all made up and have finished, and obtain illustraton of modelG (V, E)

Second step is according to community's characteristic of complication system, to illustraton of modelG (V, E)Carry out community discovery, obtain the community structure between simulation object.Be published in the community discovery thought that the papers " Community structure in social and biological networks " of the 99th 12 phases of volume of American National science proceedings is proposed according to Girvan in 2002 and Newman, adopt and constantly remove the method on the highest centrad (Centrality) limit illustraton of modelG (V, E)Carry out community discovery, each node is aggregated to different communities.Wherein, adopt the shortest path weightSW(Shortest-path Weight) as the estimated value of the centrad on limit, defines the number that community discovery will remove the limit simultaneously to beNumEdgesRemove,1≤NumEdgesRemove≤n, for reaching community discovery effect preferably,NumEdgesRemoveValue isN * 10%Integral part.For damage model figure notG (V, E), really the limit is not removed, but is figureG (V, E)In the limit increase a data fieldRemoved, be used for sign and whether be removed,RemovedBe that 1 expression removes,RemovedBe that 0 expression does not remove.Concrete steps are as follows:

2.1 the shortest path weight on all limits among the computation model figureSWValue, method is:

2.1.1 orderI=1

2.1.2 ifI≤m, carry out the 2.1.3 step; IfI〉m, change the 2.1.12 step;

2.1.3 make up the storehouse that going into earlier of a sky afterwards goes outStackFormation with a first-in first-outQueue,StackWithQueueEach element be node, the data structure of node comprises 4 territories: distanced(distance of representing this node and root node, initial value are-1), weightwThe set of (weighted value of node, initial value are 0), father nodeList(deposit the father node of this node, be initially sky) and relating valueDependency(weigh the strength of association between node and father node, initial value is 0).Use symbol respectivelyd_x, w_x, list_x, dependency_xExpressionNode_xDistance, weight, father node set and relating value.Be provided withNode_iDistanced_i=0, weightw_i=1, and willNode_iBe added toQueueIn;

2.1.4 judgeQueueWhether be empty, if not empty is carried out the 2.1.5 step; Otherwise change the 2.1.7 step;

2.1.5 from formationQueueHead shift out a node, be made asv, and this node is pressed into storehouseStack

2.1.6 to illustraton of modelG (V, E)InvEach neighbor nodeb, judge whetherd_b＜0If, true, then willbJoin formationQueueIn, and be provided withd_b=d_v+ 1Judge againd_bWhether equald_v+ 1If, true, then with nodebWeight increasew_v, promptlyw_b=w_b+ w_v, and willvJoinbFather node setList_bIn; Change the 2.1.4 step;

2.1.7 judgeStackWhether be empty, if not empty is carried out the 2.1.8 step; Otherwise change the 2.1.11 step;

2.1.8 from storehouseStackNode of top removal is made asu

2.1.9 successively to nodeuEach father node in the father node setfCarry out following processing:

2.1.9.1 according to nodeuRelating value and nodefWithuWeight ratio, new node morefRelating valueDependency_f:

dependency_f?=?dependency_f?+(w_f/w_u)×(1.0+dependency_u)；

2.1.9.2 from figureG (V, E)In search connected nodefWithuThe limitEdge_{F, u}, upgrade the limitEdge_{F, u}The shortest path weightSWValue:

SW_fu＝SW_fu+(w_f/w_u)*(1.0+dependenc_y)；

2.1.10 change the 2.1.7 step;

2.1.11I=i+1, change the 2.1.2 step;

2.1.12 finish, obtain the shortest path weight on all limitsSWValue.

2.2 constantly from figureG (V, E)The middle maximum of selectingSWThe limit of value, with this limitRemovedBe made as 1, be labeled as and remove, and computation model figure againG (V, E)In the shortest path weight on all limitsSWValue is carried out community discovery, reaches up to the limit number that removesNumEdgesRemoveConcrete steps are as follows:

2.2.1 orderIi=1

2.2.2 ifIi≤NumEdgesRemove, carry out the 2.2.3 step; IfIi〉NumEdgesRemove, changeed for 2.3 steps;

2.2.3 orderK=1,L=1,Value=0.0

2.2.4 ifK≤n, change the 2.2.5 step; IfK〉n, then change the 2.2.7 step;

2.2.5 judgeSW_kValue, as be true, thenL=k,Value=SW_k

2.2.6K=k+1, change the 2.2.2 step;

2.2.7 withlThe limitRemovedBe made as 1, be labeled as and remove;

2.2.8 adopt the methods in 2.1 steps to recomputate the shortest path weight SW value on all limits in the illustraton of model,Ii=ii+1, change the 2.2.2 step;

2.3 extract and output model figureG (V, E)In the node that community and community comprised.Has the highest SW value owing to removed continuouslyNumEdgesRemoveThe bar limit makes whole figure be divided into a plurality of mutual disconnected subgraphs.These subgraphs are exactly the community that obtains by the community discovery result, usecThe number of the expression community that finds is usedComm_pExpression thepIndividual community.Output model figureG (V, E)In each nodeNode_i(0＜i≤m) and affiliated society's area codeComm_p(0＜p≤c), second EOS.

The 3rd step: according to the community of second step discovery, the polymerization figure of community of structural belt weightG ' (V ', E ')Each community all is an illustraton of modelG (V, E)Subgraph, useSize_CommpExpression communitypSize, i.e. the interstitial content that this community comprised.Connection between community's internal node is called the inner connection of community, and the connection between different communities interior nodes is called between community and connects.AdoptG ' (V ', E ')The expression polymerization figure of community usesNode '_pWithEdge '_PqThe difference presentation graphsG ' (V ', E ')In node and limit, useWeight '_pWithWeight '_PqThe weight on expression node and limit_.Concrete steps are as follows:

3.1 the heavy non-directed graph of the cum rights of a newly-built skyG ' (V ', E '), whereinV 'WithE 'Represent the set on limit between community set among the polymerization figure of community and community respectively.

3.2 make up node and the weight thereof of the polymerization figure of community, wherein the weight of node is the size of this community.Concrete steps are as follows:

3.2.1 orderP=1

_{3.2.2 ifP≤c, carry out the 3.2.3 step; IfP〉c, changeed for 3.3 steps;}

_{3.2.3 corresponding to communityCommp, a newly-built nodeNode ' p,Weight ' p=SizeCommp, willNode ' pJoin figureG ' (V ', E ')In;}

_{3.2.4P=p+1, change the 3.2.2 step;}

_3.3Make up limit and the weight thereof of the polymerization figure of community, wherein the weight on limit is total linking number between this two community between community.Concrete steps are as follows:

3.3.1 orderK=1

_{3.3.2 ifK≤n, carry out the 3.3.3 step; IfK〉n, changeed for 3.4 steps;}

_{3.3.3 to illustraton of modelG (V, E)In the limitEdgek, search two connected node, be made asNodeiWithNodejAnd inquire about this residing community of two nodes, be made asCommpWithCommq}

_{3.3.4 ifCommpBe equal toCommq, showNodeiWithNodejBe positioned at same community,EdgekBe the fillet of community inside, change the 3.3.7 step; IfCommpWithCommqUnequal, thenEdgekForCommpWithCommqFillet between different communities is carried out the 3.3.5 step;}

3.3.5 judge communityComm_pWithComm_qThe node of correspondence in the polymerization figure of communityNode '_pWithNode '_qBetween whether had the limitEdge '_Pq, if exist, thenWeight '_Pq=Weight '_Pq+ 1, carry out 3.3.7; If do not exist, then carry out 3.3.6;

3.3.6 this momentNode '_pWithNode '_qBetween do not have the limit,To figureG ' (V ', E ')Connection of middle increaseNode '_pWithNode '_qThe limitEdge '_Pq, and be provided withWeight '_Pq=1, carry out 3.3.7;

_{3.3.7K=k+1, change the 3.3.2 step;}

3.4 finish, obtain the polymerization figure of communityG ' (V ', E ')

The 4th step: to the polymerization figure of communityG ' (V ', E ')Carry outKDivide.Count K according to the employed computer node of parallel artificial, adopt that people's such as the nineteen ninety-five Karypis of University of Minnesota technical report " METIS:Unstructured Graph Partitioning and Sparse Matrix Ordering System " proposes based at many levelsKThe METIS method of dividing, cum rights is heavy, the undirected polymerization figure of communityG ' (V ', E ')Carry outKDivide, obtainKIndividual equal portions are usedPart_hExpression, wherein0＜h≤KEach equal portions of dividing among the result comprise 1 to a plurality of communities node, can be expressed as with the set formPart_h=Node '_a,Node '_b...,Node '_c}, wherein the number of the label of community's node and community is divided according to METIS and is decided.WithWeight_ParthExpression thehTotal weight of equal portions is the big or small sum of contained community in these equal portions, promptlyWeight_Parth=Weight_{Node ' a}+ Weight_{Node ' b}+ ...+Weight_{Node ' c}The internodal fillet of community of same equal portions inside is an internal edges, and the limit in the different equal portions between community's node is a fillet between equal portions.Total weight that the METIS method can make each equal portions effectively is roughly balanced, and minimize fillet between all equal portions weight and, can effectively guarantee the load relative equilibrium on each computer node, and reduce the traffic between computing node as much as possible.

The 5th step: according to the 4th step polymerization figure of communityG ' (V ', E ')KDivide the result and carry out the distribution of parallel artificial object, each equal portions of dividing are specified be distributed to concrete computing node, and Distribution Results is write parallel artificial object distribution parameters file.Detailed process is earlier with the equal portions of being dividedPart_hUniquely correspond toH-1On number computing node (computing node is from 0 open numbering), correspondingly with community's node of equal portions inside, asNode '_a,Node '_b,Node '_cThe distribution calculation node Deng being distributed to is base unit with the community again, the simulation object that community comprised is all specified be distributed to this computing node, at last Distribution Results is write parallel artificial object distribution parameters file.The content of parallel artificial object distribution of document comprises the computing node numberK, simulation object and their distributions in the simulation object type, community, community the target computing node.The main part of simulation object distribution parameters file adopts the form of hierarchy type, organizes according to each simulation object of various simulation object types, each community, community inside, specifies the affiliated computing node of each simulation object.Parallel artificial by reading this simulation object distribution parameters file, generates the specified simulation object of this distribution method on a plurality of computing nodes when starting.

Core of the present invention is that community's characteristic is incorporated in the parallel simulation system, divides the distribution that realizes parallel discrete events simulation object based on community discovery and the polymerization figure of community, adopts the present invention can reach following beneficial effect:

1. owing to taken into full account the community's characteristic between simulation object in the scale complex system, at first utilize community discovery method just to get in touch closely and gather into community in the simulation object, on the level of community's polymerization, carry out againKEqual portions are divided, and can obtain the simulation object Distribution Results according to the employed computational resource of parallel artificial, are a kind of object of parallel artificial efficiently distribution methods;

2. owing to be basic Dispatching Unit with community, considered community's characteristic of event scheduling between simulation object, the computational load of the many computing nodes of balance and traffic load effectively, especially for extensive microcosmic virtual society, complex network, military combat, Social Dynamics Simulation Application such as (propagating), can significantly improve the operational efficiency of parallel artificial as disease/will of the people/rumor;

3. this method is simple and easy to usefulness, and the scope of application is wider, and the performance on Test Application such as diffusion of information, rumor propagation is better than existing computational load method for equalization and distribution and calculating-traffic load method for equalization and distribution;

4. this method is that unit specifies institute's distribution calculation node to dissimilar simulation objects with the community, and parallel artificial generates corresponding simulation object example by reading parallel artificial object distribution parameters file at each computing node at initial phase.This mode can effectively satisfy large-scale parallel simulation initialisation demand.

Description of drawings:

Fig. 1 is parallel discrete events simulation object distribution synoptic diagram;

Fig. 2 is adopt a present invention walk abreast exemplary plot that the discrete events simulation object distributes;

Fig. 3 is an overview flow chart of the present invention;

Fig. 4 is the process flow diagram that the first step of the present invention makes up illustraton of model;

Fig. 5 is the present invention's second step community discovery process flow diagram;

Fig. 6 is the process flow diagram that the present invention generates the heavy polymerization figure of community of cum rights the 3rd step.

Embodiment:

Fig. 1 is parallel discrete events simulation object distribution synoptic diagram.Simulation object in the complication system and the relation of the event scheduling between simulation object can represent that wherein node is represented simulation object with the figure on band node and limit, and the limit is represented and had the event scheduling relation between two simulation objects, shown in Fig. 1 arrow top.Parallel artificial obtains parallel speed-up ratio by simulation object being distributed to executed in parallel on a plurality of processor computing nodes, improves simulation run efficient.Because employed computing node number was often uncertain before parallel artificial was applied in operation, and different distribution methods can influence the calculating of whole parallel artificial and the equilibrium of traffic load, the therefore support of simulation object distribution mechanisms that need be flexible and efficient.Many complication systems have the community structure characteristic, and simulation object can carry out polymerization according to the dense degree that connects, and forms community, shown in circle part among Fig. 1.Based on community, the connection between simulation object can be divided into community and be connected with intercommunal inner the connection, represents with solid line and dotted line respectively.With the community is that unit distributes simulation object to a plurality of computing nodes, and its Distribution Results is shown in Fig. 1 arrow lower part.Intercommunal connection meeting sends according to the message of dividing between the possibility of result formation computing node, and the shared drive communication of computing node inside is then adopted in the connection of community inside.Because distributor formulas such as existing SCATTER, BLOCK, random approach and figure division are not considered community's characteristic of pervasive existence in the complication system, can not fully satisfy the demand of scale complex system parallel artificial, distribution then is a kind of method that efficiently, gears to actual circumstances based on the parallel artificial object of community's characteristic.

Fig. 2 adopts the present invention to carry out the exemplary plot of parallel artificial object distribution method.Fig. 2 is an example with a simple illustraton of model, described the main process based on the parallel artificial object distribution method of community's characteristic: figure (a) is abstract in simulation object with various piece relatively independent in the complication system, and these simulation objects and the event scheduling between them concern component model figureG (V, E)The node of band number designation represent corresponding simulation object among the figure, and internodal fillet represents to exist between two simulation objects the event scheduling relation, for example simulation object 1 respectively and 3,6 of simulation objects exist event scheduling to concern.Figure (b) is to illustraton of modelG (V, E)Carry out the result of community discovery, the simulation object that is positioned on the difformity piece aggregates into community respectively, and for example { 1,3,6,7}, { 8,9,10,11,12,13,14} etc. form community respectively to simulation object.The principal character of community is that the Connection Density of community inside is often greater than intercommunal connection.Figure (c) is with illustraton of modelG (V, E)In community further be abstracted into the heavy polymerization figure of community of cum rightsG ' (V ', E '), wherein circular node is represented corresponding community, and the circular node size is proportional zoom with community's size, and numeral is community's numbering in the circle, and numeral is community's node weights in the square bracket, the numeral on the fillet is the weight of fillet between community.For example label be community's node of 1 corresponding to simulation object 8,9,10,11,12,13, the community that 14} forms; Because this community comprises 7 simulation objects, so the weight of this community's node is made as 7; Because there is fillet between 1,2 community in this community respectively and between 2, No. 3 communities, therefore giving between the two respectively, the weight of fillet is 1 and 2 simultaneously.To polymerization figureG ' (V ', E ')Carry outKDivide this exampleKValue is 3, the polymerization figure of community is divided into 3 parts, as cutting apart that dotted line among the figure is done.Community 1 becomes equal portions separately, and community 2 and 4,3 and 5 forms all the other two equal portions respectively.BecauseKThe feature of partitioning algorithm, total weight of each equal portions of being divided be (this example all is 7 just) about equally, and total weight less (this example is 2+1+1+1+1=6) of fillet between the community that divides of cut-off rule.

Fig. 3 is an overview flow chart of the present invention, and flow process of the present invention comprised for five steps:

The first step extracts the event scheduling relation between simulation object and simulation object, the illustraton of model of complex structure system from complication systemG (V, E)

Second step is according to community's characteristic of complication system, to illustraton of modelG (V, E)Carry out community discovery, obtain the community structure between simulation object;

The 3rd step is according to the community of second step discovery, the polymerization figure of community of structural belt weightG ' (V ', E ')

The 4th step is to the polymerization figure of communityG ' (V ', E ')Carry outKDivide;

The 5th step is according to the 4th step polymerization figure of communityG ' (V ', E ')KDivide the result and carry out the distribution of parallel artificial object, each equal portions of dividing are specified be distributed to concrete computing node, and Distribution Results is write parallel artificial object distribution parameters file.

Fig. 4 is that the first step of the present invention makes up illustraton of modelG (V, E)Process flow diagram: make up illustraton of model according to the event scheduling between simulation object and simulation object relation in the complication system emulation, wherein node is represented simulation object, and the limit is represented and had the event scheduling relation between two simulation objects.Concrete steps are:

1.1 the non-directed graph of a newly-built sky is usedG (V, E)Expression, whereinVThe set of expression node,EThe set on expression limit.WithsThe expression node setVSize, be initially 0;

1.2 orderI=1

1.3 ifI≤m, carried out for 1.4 steps; IfI〉m, illustrate all simulation objects are disposed that illustraton of model has been constructed and finished, changeed for 1.10 steps;

1.4 toiIndividual simulation object makes up a new nodeNode_i, and willNode_iJoin figureG (V, E)In,S=s+1

1.5 orderJ=1

1.6 ifJ≤s, carried out for 1.7 steps; IfJ〉s, changeed for 1.9 steps;

1.7 judgement simulation objectiWithjBetween whether have event scheduling relation, if there is the event scheduling relation, to figureG (V, E)Add a connectionNode_iWithNode_jNonoriented edgeEdge_{I, j}

1.8J=j+1, changeed for 1.6 steps.

1.9I=i+1, changeed for 1.3 steps.

1.10 all simulation objects and relation thereof have all made up and have finished, and obtain illustraton of modelG (V, E)

Fig. 5 is the present invention's second step community discovery process flow diagram: to illustraton of modelG (V, E)Adopt the community discovery method that constantly removes the highest centrad limit, adopt the centrad on shortest path weight (SW) estimation limit.Key step is:

2.1 the shortest path weight on all limits among the computation model figureSWValue;

2.2 constantly from figureG (V, E)The middle maximum of selectingSWThe limit of value, with this limitRemovedBe made as 1, be labeled as and remove, and computation model figure againG (V, E)In the shortest path weight on all limitsSWValue is carried out community discovery, reaches up to the limit number that removesNumEdgesRemove

2.3 extract and output model figure G (V, E) node that community and community comprised in.Because according to predetermined limit numberNumEdgesRemoveRemove limit, make whole figure be divided into a plurality of mutual disconnected subgraphs with higher centrad.These subgraphs are exactly the community that obtains by the community discovery result.

Wherein, figure (a) is the process of the shortest path weight SW value on all limits among the computation model figure, and concrete steps are:

2.1.1 orderI=1

2.1.2 ifI≤m, carry out the 2.1.3 step; IfI〉m, change the 2.1.12 step;

2.1.3 make up the storehouse that going into earlier of a sky afterwards goes outStackFormation with a first-in first-outQueue,StackWithQueueEach element be node, the data structure of node comprises 4 territories: distanced(distance of representing this node and root node, initial value are-1), weightwThe set of (weighted value of node, initial value are 0), father nodeList(deposit the father node of this node, be initially sky) and relating valueDependency(weigh the strength of association between node and father node, initial value is 0).Use symbol respectivelyd_x, w_x, list_x, dependency_xExpressionNode_xDistance, weight, father node set and relating value.Be provided withNode_iDistanced_i=0, weightw_i=1, and willNode_iBe added toQueueIn;

2.1.4 judgeQueueWhether be empty, if not empty is carried out the 2.1.5 step; Otherwise change the 2.1.7 step;

2.1.5 from formationQueueHead shift out a node, be made asv, and this node is pressed into storehouseStack

2.1.6 to illustraton of modelG (V, E)InvEach neighbor nodeb, judged_b＜0If, true, then willbJoin formationQueueIn, and be provided withd_b=d_v+ 1Judge againd_bWhether equald_v+ 1If, true, then with nodebWeight increasew_v, promptlyw_b=w_b+ w_v, and willvJoinbFather node setList_bIn; Change the 2.1.4 step;

2.1.7 judgeStackWhether be empty, if not empty is carried out the 2.1.8 step; Otherwise change the 2.1.11 step;

2.1.8 from storehouseStackNode of top removal is made asu

2.1.9 successively to nodeuEach father node in the father node setfCarry out following processing:

2.1.9.1 according to nodeuRelating value and nodefWithuWeight ratio, new node morefRelating valueDependency_f:

dependency_f?=?dependency_f?+(w_f/w_u)×(1.0+dependency_u)

2.1.9.2 from figureG (V, E)In search connected nodefWithuThe limitEdge_{F, u}, upgrade the limitEdge_{F, u}The shortest path weightSWValue:

SW_fu＝SW_fu+(w_f/w_u)*(1.0+dependenc_y)；

2.1.10 change the 2.1.7 step;

2.1.11I=i+1, change the 2.1.2 step;

2.1.12 finish, obtain the shortest path weight on all limitsSWValue.

Figure (b) is the process in the 2.2nd, 2.3 steps in second step, and wherein the concrete steps in the 2nd step are:

2.2.1 orderIi=1

2.2.2 ifIi≤NumEdgesRemove, carry out the 2.2.3 step; IfIi〉NumEdgesRemove, changeed for 2.3 steps;

2.2.3 orderK=1,L=1,Value=0.0

2.2.4 ifK≤n, change the 2.2.4 step; IfK〉n, then change the 2.2.7 step;

2.2.5 judgeSW_kValue, as be true, thenL=k,Value=SW_k

2.2.6K=k+1, change the 2.2.2 step;

2.2.7 withlThe limitRemovedBe made as 1, be labeled as and remove;

2.2.8 adopt the methods in 2.1 steps to recomputate the shortest path weight SW value on all limits in the illustraton of model,Ii=ii+1, change the 2.2.2 step;

Fig. 6 is the process flow diagram that the present invention generates the heavy polymerization figure of community of cum rights the 3rd step, and concrete steps are:

3.1 the heavy non-directed graph of the cum rights of a newly-built skyG ' (V ', E '), whereinV 'WithE 'Represent the set on limit between community set among the polymerization figure of community and community respectively.

3.2 make up node and the weight thereof of the polymerization figure of community, wherein the weight of node is the size of this community.Concrete steps are as follows:

3.2.1 orderP=1

_{3.2.2 ifP≤c, carry out the 3.2.3 step; IfP〉c, then changeed for 3.3 steps;}

_{3.2.3 corresponding to communityCommp, a newly-built nodeNode ' p,}Weight_{' p}=Size_{Commp, willNode ' pJoin figureG ' (V ', E ')In;}

_{3.2.4P=p+1, change the 3.2.2 step;}

_3.3Make up limit and the weight thereof of the polymerization figure of community, wherein the weight on limit is total linking number between this two community between community.Concrete steps are as follows:

3.3.1 orderK=1

_{3.3.2 ifK≤n, carry out the 3.3.3 step; IfK〉n, changeed for 3.4 steps;}

_{3.3.3 to illustraton of modelG (V, E)In the limitEdgek, search two connected node, be made asNodeiWithNodejAnd inquire about this residing community of two nodes, be made asCommpWithCommq}

_{3.3.4 ifCommpBe equal toCommq, showNodeiWithNodejBe positioned at same community,EdgekBe the fillet of community inside, change the 3.3.7 step; IfCommpWithCommqUnequal, thenEdgekForCommpWithCommqFillet between different communities is carried out the 3.3.5 step;}

3.3.5 judge communityComm_pWithComm_qThe node of correspondence in the polymerization figure of communityNode '_pWithNode '_qBetween whether had the limitEdge '_Pq, if exist, thenWeight '_Pq=Weight '_Pq+ 1, carry out 3.3.7; If do not exist, then carry out 3.3.6;

3.3.6 this momentNode '_pWithNode '_qBetween do not have the limit,To figureG ' (V ', E ')Connection of middle increaseNode '_pWithNode '_qThe limitEdge '_Pq, and be provided withWeight '_Pq=1, carry out 3.3.7;

_{3.3.7K=k+1, change the 3.3.2 step;}

_{3.4 finish, obtain the polymerization figure of communityG ' (V ', E ')}

Claims (6)

Translated fromChinese

1.一种基于社区特性的并行离散事件仿真对象分发方法，其特征在于包括以下步骤：1. A method for distributing parallel discrete event simulation objects based on community characteristics, characterized in that it comprises the following steps:第一步，从复杂系统中提取出仿真对象及仿真对象间的事件调度关系，构造复杂系统的模型图G(V,E)，模型图G(V,E)由节点和连接边组成，其中节点代表仿真对象，连接边代表仿真对象间存在事件调度关系，V表示节点的集合，E表示边的集合；复杂系统中m个仿真对象间共有n条边，用Node_i表示模型图中对应于第i个仿真对象的节点，用Edge_k表示第k条边，同时用Edge_i,j表示连接节点i和j的边，其中0<i≤m，0<j≤m，0<k≤n；The first step is to extract the simulation objects and the event scheduling relationship between the simulation objects from the complex system, and construct the model graphG(V,E) of the complex system. The model graphG(V,E) is composed of nodes and connection edges, where Nodes represent simulation objects, connecting edges represent event scheduling relationships between simulation objects,V represents a collection of nodes,E represents a collection of edges; there aren edges amongm simulation objects in a complex system, andNode_i represents the corresponding For the node of thei- th simulation object, useEdge_k to represent thek -th edge, and useEdge_i,j to represent the edge connecting nodei andj , where0<i≤m, 0<j≤m, 0<k≤n ;第二步，根据复杂系统的社区聚合特性，采用不断移除最高中心度边的方法对图G(V,E)进行社区发现，将各个节点聚合到不同社区；采用最短路径权重SW作为边的中心度的估算值，同时定义社区发现所要移除边的数目为NumEdgesRemove，1≤NumEdgesRemove≤n，为图G(V,E)中的边增加一个数据域Removed，用于标示是否被移除，Removed为1表示已移除，Removed为0表示未移除，具体步骤如下：In the second step, according to the community aggregation characteristics of the complex system, the community discovery of the graphG(V,E) is carried out by continuously removing the highest centrality edge, and each node is aggregated into different communities; the shortest path weightSW is used as the edge The estimated value of the centrality, and define the number of edges to be removed by community discovery asNumEdgesRemove ,1≤NumEdgesRemove≤n , and add a data fieldRemoved for the edges in graphG(V,E) to indicate whether they are removed,Removed is 1 means removed,Removed is 0 means not removed, the specific steps are as follows:第1步，计算模型图G(V,E)中所有边的最短路径权重SW值；Step 1, calculate the shortest path weightSW value of all edges in the model graphG(V,E) ;第2步，不断从图G(V,E)中选择最大SW值的边，将该边的Removed设为1，标记为移除，并重新计算模型图G(V,E)中所有边的最短路径权重SW值，进行社区发现，直到移除的边数达到NumEdgesRemove；Step 2, continuously select the edge with the largestSW value from the graphG(V,E) , set theRemoved of the edge to 1, mark it as removed, and recalculate the edges of all edges in the model graphG(V,E) The shortest path weightSW value, for community discovery, until the number of removed edges reachesNumEdgesRemove ;第3步，提取并输出模型图G(V,E)中的社区及社区所包含的节点，由于已经连续移除了具有最高SW值的NumEdgesRemove条边，使整个图分割成多个互不连通的子图，这些子图就是通过社区发现结果得到的社区，用c表示所发现社区的个数，用Comm_p表示第p个社区，输出模型图G(V,E)中每个节点Node_i及其所属的社区号Comm_p，0<i≤m，0<p≤c；The third step is to extract and output the community and the nodes contained in the community in the model graphG(V,E) . Sincethe NumEdgesRemove edges with the highest SW value have been continuously removed, the entire graph is divided into multiple disconnected These subgraphs are the communities obtained through the community discovery results, usec to represent the number of discovered communities, useComm_p to represent thepth community, and output each nodeNode_i in the model graphG(V,E) And its community numberComm_p ,0<i≤m, 0<p≤c;第三步：根据第二步发现的社区，构造带权重的社区聚合图G’(V’, E’)，V’和E’分别代表社区聚合图中的社区集合和社区间边的集合，节点的权重为社区的大小，边的权重为两社区间仿真对象的连接边数；用Size_Commp表示社区p的大小，即该社区所包含的节点数目，将社区内部节点间的连接称为社区内部连接，不同社区内节点间的连接称为社区间连接；用Node’_p和Edge’_pq分别表示社区聚合图G’(V’, E’)中的节点和边，用Weight’_p和Weight’_pq表示节点和边的权重；具体步骤如下：Step 3: According to the community found in the second step, construct a weighted community aggregation graphG'(V', E') ,V' andE' represent the community set and the set of edges between communities in the community aggregation graph, respectively. The weight of the node is the size of the community, and the weight of the edge is the number of connection edges between the simulation objects between the two communities;Size_Commp is used to represent the size of the communityp , that is, the number of nodes contained in the community, and the connection between the nodes in the community is called the community Internal connection, the connection between nodes in different communities is called inter-community connection;Node'_p andEdge'_pq are used to represent the nodes and edges in the community aggregation graphG'(V', E') respectively, andWeight'_p andWeight '_pq represents the weight of nodes and edges; the specific steps are as follows:3.1 新建一个空的带权重无向图G’(V’, E’)；3.1 Create an empty weighted undirected graphG'(V', E') ;3.2 构建社区聚合图的节点及其权重，具体步骤如下：3.2 Construct the nodes and their weights of the community aggregation graph, the specific steps are as follows:3.2.1  令p=1；3.2.1 Letp=1 ;3.2.2  若p≤c，执行3.2.3步；若p>c，转3.3步；3.2.2 Ifp≤c , go to step 3.2.3; ifp>c , go to step 3.3;3.2.3  对应于社区Comm_p，新建一个节点Node’_p，Weight’_p=Size_Commp，将Node’_p加入到图G’(V’, E’)中；3.2.3 Corresponding to the communityComm_p , create a new nodeNode'_p ,Weight'_p= Size_Commp , and addNode'_p to the graphG'(V', E') ;3.2.4  p=p+1，转3.2.2步；3.2.4p=p+1 , go to step 3.2.2;3.3 构建社区聚合图的边及其权重，具体步骤如下：3.3 Construct the edges and their weights of the community aggregation graph, the specific steps are as follows:3.3.1  令k=1；3.3.1 Letk=1 ;3.3.2  若k≤n，执行3.3.3步；若k>n，转3.4步；3.3.2 Ifk≤n , go to step 3.3.3; ifk>n , go to step 3.4;3.3.3  对模型图G(V,E)中的边Edge_k，查找其两个连接节点，设为Node_i和Node_j；并查询该两节点所处的社区，设为Comm_p和Comm_q；3.3.3 ForEdge_k in the model graphG(V,E) , find its two connecting nodes, set it asNode_i andNode_j ; and query the community where the two nodes are located, set it asComm_p andComm_q ;3.3.4  若Comm_p等同于Comm_q，表明Node_i和Node_j位于同一个社区，Edge_k为社区内部的连接边，转3.3.7步；若Comm_p与Comm_q不相等，则Edge_k为Comm_p和Comm_q不同社区间的连接边，执行3.3.5步；3.3.4 IfComm_p is equal toComm_q , it means thatNode_i andNode_j are located in the same community,Edge_k is the connection edge inside the community, go to step 3.3.7; ifComm_p is not equal toComm_q , thenEdge_k is For connection edges between different communities ofComm_p andComm_q , perform step 3.3.5;3.3.5  判断社区Comm_p和Comm_q在社区聚合图中对应的节点Node’_p与Node’_q间是否已存在边Edge’_pq，若存在，则Weight’_pq=Weight’_pq+1，执行3.3.7；若不存在，则执行3.3.6；3.3.5 Determine whether there is an edgeEdge'_pq between the nodesNode'_p andNode'_q corresponding to the communityComm_p andComm_q in the community aggregation graph. If it exists, thenWeight'_pq= Weight'_pq+1 , and execute 3.3 .7; if not present, execute 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.6 At this time, there is no edge betweenNode'_p andNode'_q, add an edgeEdge'_pq connectingNode'_p andNode'_q to the graphG'(V', E') , and setWeight'_pq=1 , execute 3.3.7;3.3.7  k=k+1，转3.3.2步；3.3.7k=k+1 , go to step 3.3.2;3.4 结束，得到社区聚合图G’(V’, E’)；3.4 At the end, get the community aggregation graphG'(V', E') ;第四步：采用基于多层次K划分的METIS方法对社区聚合图G’(V’, E’)进行K划分，得到K个等份，用Part_h表示，其中0<h≤K；划分结果中的每个等份包含1至多个社区节点，用集合形式表示为Part_h={Node’_a, Node’_b, … , Node’_c}，其中社区节点的标号和社区的个数依据METIS划分结果而定；用Weight_Parth表示第h等份的总权重，为该等份内所含社区的大小之和，即Weight_Parth=Weight_Node’a+Weight_Node’b+...+ Weight_Node’c；同一等份内部的社区节点间的连接边为内部边，不同等份中社区节点之间的边为等份间连接边；Step 4: Use the METIS method based on multi-levelK partitioning toK partition the community aggregation graphG'(V', E') to obtainK equal parts, represented byPart_h , where0<h≤K ; partition results Each equal part in contains 1 to more community nodes, expressed asPart_h={Node'_a ,Node'_b , … ,Node'_c} in aggregate form, where the labels of community nodes and the number of communities are divided according to METIS It depends on the result; useWeight_Parth to represent the total weight of theh -th equal part, which is the sum of the sizes of the communities contained in the equal part, that is,Weight_Parth= Weight_Node'a+ Weight_Node'b+...+ Weight_Node'c; The connection edges between community nodes within the same equal share are internal edges, and the edges between community nodes in different equal shares are inter-equal connection edges;第五步：根据第四步社区聚合图G’(V’, E’)的K划分结果进行并行仿真对象的分发，将划分的各个等份指定分发到具体的计算节点，并将分发结果写入并行仿真对象分发参数文件，具体过程是先将所划分的等份Part_h唯一对应到第h-1号计算节点上，相应地将等份内部的社区节点等分发到所分配的计算节点，再以社区为基本单位，将社区所包含的仿真对象都指定分发到该计算节点，同时将分发结果写入并行仿真对象分发参数文件。Step 5: Distribute the parallel simulation objects according tothe K division results of the community aggregation graphG'(V', E') in the fourth step, specify and distribute the divided equal parts to specific computing nodes, and write the distribution results to Into the parallel simulation object distribution parameter file, the specific process is first to uniquely map the divided equal partPart_h to the computing nodeh-1 , and correspondingly distribute the community nodes inside the equal part to the allocated computing nodes, Then, with the community as the basic unit, all the simulation objects contained in the community are designated to be distributed to the computing node, and the distribution results are written into the parallel simulation object distribution parameter file.2.如权利要求1所述的基于社区特性的并行离散事件仿真对象分发方法，其特征在于所述构造复杂系统的模型图G(V,E)的具体步骤如下：2. the method for distributing parallel discrete event simulation objects based on community characteristics as claimed in claim 1, wherein the specific steps of the model diagramG (V, E) of the complex system are as follows:2.1）  新建一个空的无向图，用G(V,E)表示，其中V表示节点的集合，E表示边的集合，用s表示节点集合V的大小，初始为0；2.1) Create an empty undirected graph, represented byG(V,E) , whereV represents the set of nodes,E represents the set of edges, ands represents the size of the node setV , which is initially 0;2.2）  令i=1；2.2) Leti=1 ;2.3）  若i≤m，执行2.4）步；若i>m，转2.10）步；2.3) Ifi≤m , execute step 2.4); ifi>m , go to step 2.10);2.4）  对第i个仿真对象构建一个新节点Node_i，并将Node_i加入到图G(V,E)中，s=s+1；2.4) Construct a new nodeNode_i for thei -th simulation object, and addNode_i to the graphG(V,E) ,s=s+1 ;2.5）  令j=1；2.5) Letj=1 ;2.6）  若j≤s，执行2.7）步；若j>s，转2.9）步；2.6) Ifj≤s , execute step 2.7); ifj>s , go to step 2.9);2.7）  判断仿真对象i和j之间是否存在事件调度关系，若存在事件调度关系，向图G(V,E)加入一条连接Node_i和Node_j的无向边Edge_i,j；2.7) Determine whether there is an event scheduling relationship between simulation objectsi andj , if there is an event scheduling relationship, add an undirected edgeEdge i_,j connectingNode_i andNode_j to graphG(V,E) ;2.8）  j=j+1，转2.6）步；2.8)j=j+1 , go to step 2.6);2.9）  i=i+1，转2.3）步；2.9)i=i+1 , turn to 2.3) step;2.10） 所有仿真对象及其关系都已构建完毕，得到模型图G(V,E)。2.10) All simulation objects and their relationships have been constructed, and the model graphG(V,E) is obtained.3.如权利要求1所述的基于社区特性的并行离散事件仿真对象分发方法，其特征在于所述计算模型图中所有边的最短路径权重SW值方法是：3. the parallel discrete event simulation object distribution method based on community characteristics as claimed in claim 1, is characterized in that the shortest path weightSW value method of all edges in the calculation model graph is:3.1）令i=1；3.1) leti=1 ;3.2）若i≤m，进行第3.3）步；若i>m，转3.12）步；3.2) Ifi≤m , go to step 3.3); ifi>m , go to step 3.12);3.3）构建一个空的先入后出的堆栈stack和一个先入先出的队列queue，stack和queue的每个元素均为节点，节点的数据结构包括4个域：距离d，初始值为-1；权重w，初始值为0；父节点集合list，存放该节点的父节点，初始为空；衡量节点与父节点间的关联强度的关联值dependency，初始值为0；分别用符号d_x、w_x、list_x、dependency_x表示Node_x的距离、权重、父节点集合以及关联值，设置Node_i的距离d_i=0，权重w_i=1，并将Node_i加到queue中；3.3) Construct an empty first-in first-out stackstack and a first-in first-out queuequeue , each element ofthe stack andqueue is a node, and the data structure of the node includes 4 fields: distanced , the initial value is -1; Weightw , the initial value is 0; the parent node setlist , which stores the parent node of the node, is initially empty; the correlation valuedependency which measures the relationship strength between the node and the parent node, the initial value is 0; respectively use the symbolsd_x, w_x, list_x, and dependency_x indicate the distance, weight, parent node set and associated value ofNode_x , set the distanced_i=0 ofNode_i , weightw_i=1 , and addNode_i tothe queue ;3.4）判断queue是否为空，若非空，执行3.5步；否则转3.7步；3.4) Determine whetherthe queue is empty, if not, execute step 3.5; otherwise, go to step 3.7;3.5）  从队列queue的头部移出一个节点，设为v，并将该节点压入堆栈stack；3.5) Remove a node from the head ofthe queue , set it asv , and push the node into the stackstack ;3.6）  对模型图G(V,E)中v的每一个邻居节点b，判断是否d_b<0，若为真，则将b加入到队列queue中，并设置d_b=d_v+1；再判断d_b是否等于d_v+1，若为真，则将节点b的权重增加w_v，即w_b=w_b+w_v，并将v加入到b的父节点集合list_b中；转3.4步；3.6) For each neighbor nodeb ofv in the model graphG(V,E) , judge whetherd_b<0 , if it is true, addb tothe queue , and setd_b=d_v+1 ; Then judge whetherd_b is equal tod_v+1 , if it is true, increase the weight of nodeb byw_v , that is,w_b=w_b+w_v , and addv to the parent node setlist_b ofb ; turn 3.4 steps;3.7）  判断stack是否为空，若非空，执行3.8）步；否则转3.11）步；3.7) Determine whetherthe stack is empty, if not, execute step 3.8); otherwise, go to step 3.11);3.8）  从堆栈stack顶部移除一个节点，设为u；3.8) Remove a node from the top of thestack and set it tou ;3.9）  依次对节点u父节点集合中的每一个父节点f进行如下处理：3.9) Each parent nodef in the parent node set of nodeu is processed as follows in turn:3.9.1）    根据节点u的关联值及节点f与u的权重比值，更新节点f的关联值dependency_f：3.9.1) According to the associated value of nodeu and the weight ratio of nodef andu , update the associated valuedependencyf of node_f :dependency_f= dependency_f+(w_f/w_u)×(1.0+dependency_u)；dependency_f= dependency_f+(w_f/w_u)×(1.0+dependency_u) ;3.9.2）    从图G(V,E)中查找连接节点f和u的边Edge_f,u，更新边Edge_f,u的最短路径权重SW值：3.9.2) Find the edgeEdge f,u connecting nodesf andu from the graphG(V,E) ,_and update the shortest path weightSW value of the edgeEdge_f,u :SW_fu＝SW_fu+(w_f/w_u)*(1.0+dependenc_y)；SW_fu= SW_fu+(w_f/w_u)*(1.0+dependenc_y) ;3.10） 转3.7）步；3.10) Go to step 3.7);3.11） i=i+1，转3.2）步；3.11)i=i+1 , go to step 3.2);3.12） 结束，得到所有边的最短路径权重SW值。3.12) At the end, get the shortest path weightSW value of all edges.4.如权利要求1所述的基于社区特性的并行离散事件仿真对象分发方法，其特征在于所述不断从图G(V,E)中移除最大SW值的边，并重新计算模型图G(V,E)中所有边的最短路径权重SW值，进行社区发现的方法是：4. The method for distributing parallel discrete event simulation objects based on community characteristics as claimed in claim 1, wherein the edge of the maximumSW value is constantly removed from the graphG (V, E) , and the model graphG is recalculated The shortest path weightSW value of all edges in(V,E) , the method for community discovery is:4.1）  令ii=1；4.1) Letii=1 ;4.2）  若ii≤NumEdgesRemove，执行4.3）步；若ii>NumEdgesRemove，结束；4.2) Ifii≤NumEdgesRemove , execute step 4.3); ifii>NumEdgesRemove , end;4.3）  令k=1，l=1，value=0.0；4.3) Letk=1 ,l=1 ,value=0.0 ;4.4）  若k≤n，转4.5）步；若k>n，则转4.7）步；4.4) Ifk≤n , go to step 4.5); ifk>n , go to step 4.7);4.5）  判断SW_k>value，如为真，则l=k，value=SW_k；4.5) JudgeSW_k>value , if true, thenl=k ,value=SW_k ;4.6）  k=k+1，转4.2）步；4.6)k=k+1 , go to step 4.2);4.7）  将第l边的Removed设为1，标记为移除；4.7) Setthe Removed of thelth side to 1 and mark it as removed;4.8）  重新计算模型图中所有边的最短路径权重SW值，ii=ii+1，转4.2）步。4.8) Recalculate the shortest path weight SW value of all edges in the model graph,ii=ii+1 , go to step 4.2).5.如权利要求1所述的基于社区特性的并行离散事件仿真对象分发方法，其特征在于所述并行仿真对象分发文件的内容包括计算节点数目K、仿真对象类型、社区、社区内仿真对象以及它们分发的目标计算节点；仿真对象分发参数文件的主体部分采用层次式的格式，按照各种仿真对象类型、各个社区、社区内部的各个仿真对象进行组织，指定各个仿真对象所属的计算节点。5. The parallel discrete event simulation object distribution method based on community characteristics as claimed in claim 1, wherein the content of the parallel simulation object distribution file includes computing node number K, simulation object type, community, simulation object in the community, and The target computing nodes they distribute; the main part of the simulation object distribution parameter file adopts a hierarchical format, organizes according to various simulation object types, each community, and each simulation object within the community, and specifies the computing node to which each simulation object belongs.6.如权利要求1所述的基于社区特性的并行离散事件仿真对象分发方法，其特征在于所述NumEdgesRemove取值为10%×n的整数部分。6. The method for distributing parallel discrete event simulation objects based on community characteristics according to claim 1, characterized in that saidNumEdgesRemove takes an integer part of10%×n .

Images