CN103885839A

CN103885839A - Cloud computing task scheduling method based on multilevel division method and empowerment directed hypergraphs

Info

Publication number: CN103885839A
Application number: CN201410136320.XA
Authority: CN
Inventors: 冷明; 孙凌宇; 冷子阳
Original assignee: Individual
Current assignee: Individual
Priority date: 2014-04-06
Filing date: 2014-04-06
Publication date: 2014-06-25
Anticipated expiration: 2034-04-06
Also published as: CN103885839B

Abstract

The invention relates to a cloud computing task scheduling method based on a multilevel division method and empowerment directed hypergraphs in a cloud computing environment. The empowerment directed hypergraphs are adopted to describe the resource demand and dependency relationship of a task, and corresponding empowerment directed hypergraph files are generated; then, an empowerment directed hypergraph division program based on the multilevel division method is started, and the generated empowerment directed hypergraphs are divided; finally, task subsets are constructed according to the division result of the empowerment directed hypergraphs, and the task subsets are mapped and scheduled through a MapReduce task scheduling model. Through the cloud computing task scheduling method based on the multilevel division method and the empowerment directed hypergraphs, task scheduling efficiency is improved effectively, task division performance is obviously improved, and good practicality is achieved.

Description

Based on the cloud computing method for scheduling task of multilevel partitioning and tax power Directed Hypergraph

Technical field

The present invention relates to the cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph under a kind of cloud computing environment.

Background technology

Cloud computing is as the product of the new technique fusion developments such as the conventional arts such as Distributed Calculation, parallel computation, grid computing and network programming model, Distributed Storage technology, Intel Virtualization Technology, be the strategic technology of key and the means of the innovation of the Fashion of Future information industry, will China's developing new and high-tech industry be had to important strategic importance.Cloud computing is by being divided in calculation task on large-scale low-cost server cluster, people can be utilized be distributed in the unused resource of various places to process comparatively complicated application program, drops into and obtains high calculating quality with extremely low cost.

Meeting under the prerequisite of cloud computing environment requirement, the application program task division of disperseing is in a large number become to multiple task subsets with certain restriction relation, be dispatched on different virtual machines, acquisition for the shorter time span of the task scheduling algorithm of grid computing or parallel computation and better running quality, is to realize the high performance key core technology of cloud computing than some other.

In the dividing system of prior art, there is the partitioning of several task, the different aspects such as the task number of these partitionings task subset from dependence number minimum, division is uniformly distributed realize, and mainly contain the methods such as the partitioning based on migration, horizontal Nested dissection method, multilevel partitioning.

based on the partitioning of migration.first the method produces the random initial division of task, and same task can not belong to two task subsets simultaneously.In the migration optimizing phase, from two task subsets, respectively to choose a task and exchange in pairs, these two tasks belong to respectively two different task subset and Income Maximums, thereby all utilize exchange process to improve to greatest extent task division quality at every turn.Record cuts off the task division result that reaches the minimum value moment, once and exchanged selected two tasks, in the optimization of whole transition process remainder improves, make them no longer selected these two task lockings.Repeat said process until after all possible task all pass through and move, roll back to accumulated earnings maximal value and cut off the moment of minimum value.The task division unstable result that this partitioning obtains, discreteness is very large, has therefore limited the scale that this partitioning can be dealt with problems.

horizontal Nested dissection method.first the method selects a task, this task is put on to number 0, then all being connected with this task of tasks are put on to number 1, also do not put on number for those afterwards, but the task that the task of having put on number is connected is to be connected on the number of task to add 1 by its label.Until the task of half is put on number, label procedure just finishes.Those set of tasks of having put on number are made as a task subset, and other tasks are another task subset.This partitioning is only in the time that the initiating task of choosing approaches periphery, and the task division result obtaining is relatively better, and generally speaking this task division result is also unstable.

multilevel partitioning.karypis reaches millions of partition problems for node scale, has proposed the concept of multilevel division, within the relatively short time, can obtain high-quality division.The method comprises alligatoring, initial division and migration and optimizes three phases.First, it adopts random fit strategy that some task is combined, and obtains the alligatoring task image of next flat seam, repeats this process until alligatoring task image is enough little, obtains a minimum task figure.Then, adopt partitioning to carry out, to dividing, obtaining an initial division to minimum task figure.Afterwards, minimum task figure projection is returned to initiating task figure, in the refinement task division of each flat seam, select the task of financial value maximum to move optimization according to greedy principle, obtain last task division result.

the application of multilevel partitioning in circuit is divided.since the concept of multilevel division proposes, obtain paying attention to widely, and be applied in many research fields such as circuit division.

Being declared by cold bright, Yu Songnian and Sun Lingyu of the Decree of Patent Office of China in 2008, China Patent No. is the patent of invention of No. 200710043765.3 " the large scale integrated circuit division methods based on multilevel partitioning ", for moving optimization because adopting randomized policy to mate with greedy principle in prior art scheme, the division that causes fleeing from local optimum, provides one the improved large scale integrated circuit division methods based on multilevel partitioning, effectively improved efficiency and performance that large scale integrated circuit is divided.This patent of invention is in the alligatoring stage of multilevel partitioning, solve sequence by the core value of node attribute being composed to all nodes in power non-directed graph, according to the non-strict descending access based on node core value in the node of matching status not, according to certain rule, it is mated, thereby the good node of connectivity is combined; In the optimizing phase of multilevel partitioning, adopt immune clone optimizer to improve the local search approach of greedy principle, to being optimized in the division of each flat seam projection, by clone operations, clonal vaviation operation, the operation of immunoprophylaxis vaccine, Immune Clone Selection operation, make method after improving in utilizing heuristic information search locally optimal solution, more freely the potential solution space of tool is searched for, increase ability of searching optimum.

The Decree of Patent Office of China in 2012 by Sun Lingyu, cold bright and hail is positive declares, China Patent No. is the patent of invention of No. 201210155738.6 " based on the large scale integrated circuit division methods of multilevel partitioning and tax power hypergraph ", compose the mathematical model of power non-directed graph as large scale integrated circuit partition problem for adopting, exist the inconsistency of composing power non-directed graph optimal dividing and large scale integrated circuit optimal dividing, one is provided based on the large scale integrated circuit division methods of multilevel partitioning and the undirected hypergraph of tax power, further improved efficiency and performance that large scale integrated circuit is divided.This invention adopts the undirected hypergraph of tax power to carry out mathematical modeling to Circuit Partitioning Problem, and wherein circuit logic cell list is shown the node of composing in the undirected hypergraph of power, and the wire list between circuit unit is shown composes the super limit of weighing in undirected hypergraph.Compare and compose power non-directed graph, compose the undirected hypergraph of power and provide more accurate model for circuit: every super limit can connect plural node, can connect plural circuit logic unit corresponding to the signal between circuit unit.This invention is converted to large scale integrated circuit partition problem to compose the undirected hypergraph partition problem of power, its Large and middle scale IC partition problem requires the circuit logic number of unit that each circuit subset comprises to equate, corresponding to the equilibrium constraint of composing the undirected hypergraph partition problem of power, division result makes the intraconnections data between these circuit subsets reach minimum, cuts off corresponding to composing always minimizing of undirected hypergraph partition problem of power.

The Decree of Patent Office of China in 2012 by Sun Lingyu, cold bright and hail is positive declares, China Patent No. is the patent of invention of No. 201210150329.7 " the core value calculating methods of the large scale integrated circuit based on node attribute function " , adopting multilevel partitioning to solve in the alligatoring stage of composing the undirected hypergraph partition problem of power, provide the core value calculating method of the required large scale integrated circuit based on node attribute function.this patent of invention is conducive in the node matching process of the undirected hypergraph of tax power, the effect of performance node core value guidance quality, make after alligatoring node weights in hypergraph be tending towards in the same size, and farthest reduce number and the super limit weights sum on super limit, for the follow-up phase of the multilevel division of large scale integrated circuit provides more excellent alligatoring hypergraph.

Being declared by cold bright, Sun Lingyu and hail sun of the Decree of Patent Office of China in 2012, China Patent No. is the patent of invention of No. 201210154573.0 " based on cellular automaton and compose the large scale integrated circuit division methods of power hypergraph ", adopt cellular automaton to carry out mathematical modeling to composing the undirected hypergraph partition problem of power.Wherein, cellular is corresponding to the node of composing in the undirected hypergraph of power, the node comprising corresponding to the super limit of adjacency in abutting connection with cellular, the state of cellular is corresponding to the dividing subset at place, and then adopt cellular financial value and the computing method of dividing the value of cuing off fast, effectively reduce space complexity and the time complexity of large scale integrated circuit division methods.

Summary of the invention

In the cloud computing environment the present invention relates to task schedulingcomprise the scheduling of first task and the scheduling of dependence task.Separate between unit's task, data correlation and the priority constraint relationship between task do not considered in its scheduling, and therefore it has just partly solved resource isomerism and availability issue, lacks general applicability.And between dependence task, there is successively dependence, could start to carry out after requiring a task must receive its all predecessor task message.

The present invention adopts compose power Directed Hypergraphconstruct the mathematical model of task division problem, task list is shown the node of composing power Directed Hypergraph, and the priority dependence between task node is expressed as the oriented super limit of composing in power Directed Hypergraph .The many-to-many relationship of composing power Directed Hypergraph provides the means of accurate description user task, its node is corresponding to the process level user task after decomposing, oriented super limit is corresponding to the priority dependence between task node, arbitrarily the tail end node on super limit whole predecessor tasks of corresponding task source terminal of being included in this super limit concentrate. compare weighted and directed diagraph and compose the undirected hypergraph of power, compose the scheduling that power Directed Hypergraph is dependence task more accurate model is provided, can represent all sidedly the feature such as isomerism, distributivity, wide regional coverage of cloud computing environment, thereby improve accuracy and the execution efficiency of task scheduling.

Compare weighted and directed diagraph, composing power Directed Hypergraph is task node dependenceprovide more accurate model: every limit only connects two nodes, can only connect two tasks corresponding to the dependence between task node, and every super limit can connect plural node, can connect plural task corresponding to the priority dependence between task node, arbitrarily the tail end node on super limit whole (more than two) predecessor task of corresponding task source terminal of being included in this super limit concentrate.

Compare compose the undirected hypergraph of power, composing power Directed Hypergraph is task node successively dependenceprovide more accurate model: undirected super limit connects plural node, but cannot represent the priority dependence between task node, and every oriented super limit can connect plural node, all direct precursor nodes of super limit tail end node are included in the source terminal on this super limit and concentrate, corresponding to the priority dependence between task node.

The object of the invention is to the deficiency existing for prior art, a kind of cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph is provided, effectively shorten the time span that task completes, realize the reasonable utilization of cloud computing resources, for cloud computing provides efficient Task Scheduling Mechanism.For achieving the above object, design of the present invention is as follows.

One, in cloud computing environment, the task of disperseing is in a large number divided into the task subset that multiple scales are less according to specific constraint condition, make each task subset calculating scale after dividing suitable, but the dependence number between task subset reaches minimum, thereby farthest realize the load balancing of cloud computing platform, and shorten the time span that whole task completes.The key link as cloud computing Task Scheduling Mechanism is divided in the optimization of task subset, and its result has important impact to the operational efficiency of whole cloud computing environment, can effectively reduce resource free time, improves the benefit of utilizing of resource.

The optimization partition problem of the task subset of two, cloud computing task scheduling is converted to composes power Directed Hypergraph partition problem, the optimization partition problem that is task subset requires the task number that each task subset comprises to equate, corresponding to the equilibrium constraint of composing power Directed Hypergraph partition problem, division result makes the dependence number between task subset reach minimum, cuts off corresponding to composing always minimizing of power Directed Hypergraph partition problem.Wherein, the division of composing power Directed Hypergraph requires the task number that each task subset comprises to equate, corresponding to the equilibrium constraint under many resource constraints, and division result makes the dependence number between these task subsets reach minimum, cuts off corresponding to always minimizing of multiple-objection optimization partition problem.

Three, adopt tax power Directed Hypergraph to describe resource requirement and the dependence of task, and corresponding tax of generation weighed Directed Hypergraph file; Then start the tax power Directed Hypergraph partition program based on multilevel partitioning, the tax power Directed Hypergraph generating is divided; The last division result structure task subset according to composing power Directed Hypergraph, shines upon it by MapReduce Task Scheduling Model and dispatches.

Four, in alligatoring stage of multilevel partitioning, by solving sequence to composing the core value that in power Directed Hypergraph, all nodes carry out based on node attribute function, and then non-strict descending access based on node core value is in the node of matching status not, according to certain rule, it is mated, thereby the node that connectivity is good combines, for providing more excellent alligatoring, the follow-up phase of multilevel division composes power Directed Hypergraph.

Five, in optimizing phase of multilevel partitioning, adopt multiobject discrete group intelligent search program to improve the local search approach of greedy principle, the division of composing the projection of power Directed Hypergraph in each flat seam alligatoring is optimized, wherein colony intelligence particle is of living in | and V| dimension space position (node set in power Directed Hypergraph is composed in V representative) is corresponding to a splitting scheme, be the position of colony intelligence particle in each dimensional space, represent the node subset of the corresponding node of this dimensional space division of living in; Be accompanied by the thinning process of optimizing phase, the division of each colony intelligence particle solution representative projects to the refinement of present level layer and composes on power Directed Hypergraph, and the degree of freedom of colony intelligence particle is along with Spatial Dimension | the increase of V| and increasing; Between colony intelligence particle, carry out direct communication or indirect communication, utilize them to assemble the collaborative intelligent behavior showing, the Pareto efficient solution that effectively search under multi-constraint condition, multiple goal combines, non-bad migration optimization solution is approached towards the optimum face of Pareto-, strengthen the multiple goal search capability of migration optimized algorithm.

According to above-mentioned inventive concept, technical scheme of the present invention is achieved in that a kind of cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph, it is characterized in that, concrete steps are as follows.

Step 1, class types degree is analyzed, the task that under input cloud computing environment, user submits to, and the analysis that it is carried out to type and class degree, determines parallelization degree and the feature of task.

Step 2, proceeding graininess decomposes, according to parallelization degree and the feature of user task, and the peculiar property such as the resource sharing allocation scheme of cloud computing, user task is decomposed according to proceeding graininess rank.

Step 3, resource characteristics is analyzed, according to peculiar properties such as the resource sharing allocation scheme of cloud computing, the task after decomposing is carried out to resource characteristics analysis.

Step 4, compose power Directed Hypergraph file generated, according to the analysis result to task resource characteristic, set up the tax power Directed Hypergraph model of describing its resource requirement and dependence, and save as and compose power Directed Hypergraph file according to the file memory format that improves compression.

Step 5, composing power Directed Hypergraph dividesstart the tax power Directed Hypergraph partition program based on multilevel partitioning, read and compose power Directed Hypergraph file, adopt the memory form that improves compression to store composing power Directed Hypergraph, the tax power Directed Hypergraph generating is divided, the division result finally obtaining is stored in and is composed in power Directed Hypergraph division file.

Step 6, task subset construction, after detecting that tax power Directed Hypergraph partition program based on multilevel partitioning completes division, divide file and read corresponding division result from composing power Directed Hypergraph, according to the division result structure process level task subset of composing power Directed Hypergraph.

Step 7, duty mapping schedulingby MapReduce Task Scheduling Model, task subset based on composing power Directed Hypergraph optimization and divide structure is shone upon and dispatch, realize job invocation and execution in cloud computing environment, the time span that the load of balanced cloud computing platform and the whole task of shortening complete effectively.

In above-mentioned step 4, the file memory format of the improvement compression of described tax power Directed Hypergraph as follows.

Step 4.1, the 1st parameter of the 1st row of file layout representing the number m on oriented tax Quan Chao limit, the 2nd parameter representing the number n that composes power node.

Step 4.2, the 2nd row of file layout starts representing one article of oriented relevant information of composing Quan Chao limit to the capable every row of m+1, the 1st numerical value is the weights information on oriented tax Quan Chao limit, its remainder values is the node information on oriented tax Quan Chao limit, wherein last numerical value of every row represents the tail end node information on oriented tax Quan Chao limit, and between the weights information and tail end node information of the source node information on oriented tax Quan Chao limit in oriented tax Quan Chao limit.

Step 4.3, the capable beginning of m+2 of file layout representing a weights information of composing power node to the capable every row of m+n+1.

In above-mentioned step 5, the step of the described power of the tax based on multilevel partitioning Directed Hypergraph partition program is as follows.

Step 5.1, reads and composes power Directed Hypergraph file, adopts the memory form that improves compression to store composing power Directed Hypergraph.

Step 5.2, enter into the alligatoring stage of multilevel partitioning, some node that adopts the node matcher of composing power Directed Hypergraph that the alligatoring of present level layer composed to power Directed Hypergraph combines, power Directed Hypergraph is composed in the alligatoring that obtains next flat seam, repeat this process until alligatoring tax power Directed Hypergraph is enough little, obtain a minimum power Directed Hypergraph of composing.

Step 5.3, enters into initial division stage of multilevel partitioning, and the tax power Directed Hypergraph partition program of operation based on FM method, obtains the minimum initial division of composing power Directed Hypergraph.

Step 5.4, the discrete group intelligent search program initialization of multilevel partitioning optimizing phase, the self-position vector of the each colony intelligence particle of global history optimal location vector sum of all colony intelligence particles of initialization, self velocity vector, self historical optimal location vector.

Step 5.5, enter into the optimizing phase of multilevel partitioning, compose the projection of power Directed Hypergraph from minimum and return initial tax power Directed Hypergraph, in the refinement tax power Directed Hypergraph of each flat seam, the projection division that adopts discrete group intelligent search program to compose power Directed Hypergraph to refinement is optimized.

Step 5.6, enters into equilibrium stage, the tax power Directed Hypergraph partition program of operation based on FM-EE method.Due in the tax power Directed Hypergraph partition process based on multilevel partitioning, may run counter to the equilibrium constraint of composing power Directed Hypergraph partition problem, therefore divide on the basis solving at the tax power Directed Hypergraph based on multilevel partitioning, the tax power Directed Hypergraph division methods of operation based on FM-EE method, make to divide solution and meet equilibrium constraint, thereby obtain composing the division solution of weighing Directed Hypergraph partition problem.

Step 5.7, is stored in the tax power Directed Hypergraph division result finally obtaining to compose in power Directed Hypergraph division file.

In above-mentioned step 5.1, the memory form of the improvement compression of described tax power Directed Hypergraph is as follows.

Step 5.1.1, uses vwgts storage of array to compose the weights information of node in power Directed Hypergraph, and the size of vwgts array is the node number of composing in power Directed Hypergraph.

Step 5.1.2, use the start position information of the oriented super limit list of the each node all of its neighbor of xadj storage of array, the reference position that the final position of i node is i+1 node subtracts 1, and the size of xadj array is that the node number of composing in power Directed Hypergraph adds last element of 1, xadj array for depositing the final position of last node.

Step 5.1.3, uses the list information on the oriented super limit of the each node all of its neighbor of adjncy storage of array, i node in abutting connection with oriented super limit list storage in adjncy array, from adjncy[xadj[i]] to adjncy[xadj[i+1]-1].

Step 5.1.4, the start position information of the node list that use every oriented super limit of eptr storage of array comprises, the reference position that the final position on j article of oriented super limit is j+1 article of oriented super limit subtracts 1, and the size of eptr array is that the oriented super edge strip number of composing in power Directed Hypergraph adds last element of 1, eptr array for depositing the final position on the oriented super limit of the last item.

Step 5.1.5, use the list information of eind storage of array node that every oriented super limit comprises, wherein the tail end node on every oriented super limit only has 1, and all direct precursor nodes of every oriented super limit tail end node be included in this oriented super limit source terminal concentrate.The node list storage on j article of oriented super limit is in eind array, from eind[eptr[j]] to eind[eptr[j+1]-1], wherein the source node on j article of oriented super limit is eind[eptr[j]] to eind[eptr[j+1]-2], the tail end node on j article of oriented super limit is eind[eptr[j+1]-1].

Step 5.1.6, the weights information on the use oriented super limit of hewgts storage of array, and the size of hewgts array is the oriented super limit number of composing in power Directed Hypergraph.

In above-mentioned step 5.2, the step that the node matcher of weighing Directed Hypergraph is composed in described present level layer alligatoring is as follows.

Step 5.2.1, the alligatoring of mark present level layer composed in power Directed Hypergraph all nodes in matching status not.

Step 5.2.2, the node core value calculation procedure of power Directed Hypergraph is composed in operation, and the core value of carrying out all nodes in present level layer alligatoring tax power Directed Hypergraph based on node attribute function value solves, and carries out non-strict descending sort according to the core value of node.

Step 5.2.3, according to the non-strict descending access of node core value in the node v of matching status not; If node v also has adjacent node not mate, choose so in there is no the adjacent node u in abutting connection with super limit matching status and weights maximum and node v coupling, and to mark these two nodes be matching status; If node v all of its neighbor matched nodes is in matching status, node v is still in matching status not so, and in coarsening process, direct copying is composed in power Directed Hypergraph to the alligatoring of next flat seam.

Step 5.2.4, step repeats previous step, until the access of all nodes finishes.

In above-mentioned step 5.2.2, the step of the node core value calculation procedure of described tax power Directed Hypergraph is as follows.

Step 5.2.2.1, calculates the attribute function value of all nodes.

Step 5.2.2.2, carries out non-strict descending sort to the attribute function value of all nodes.

Step 5.2.2.3, accesses each node according to the non-strict descending order of node attribute function value, calculates the core value of each node.

In above-mentioned step 5.2.2.2, the step of the non-strict descending sort of described node attribute function value is as follows.

Step 5.2.2.2.1, belongs to integer within the specific limits according to the attribute function value of node, scans the attribute function value of all nodes, adds up the node number of each attribute function value, is stored in counting supplementary number group bin.

Step 5.2.2.2.2, for each attribute function value, by counting supplementary number group bin, calculates in the attribute function value of all nodes, is less than the node number of this attribute function value, is stored in location aided rebroadcast array pos.

Step 5.2.2.2.3, scan the attribute function value of all nodes, for the attribute function value of each node, by location aided rebroadcast array pos, obtain the attribute function value of this node at the order of non-strict descending sort, and this order is stored in the auxiliary array vert of order.

In above-mentioned step 5.2.2.3, the step that the core value of described node v is calculated is as follows.

Step 5.2.2.3.1, exports the attribute function value of node v as core value.

Step 5.2.2.3.2, mark node v deletes from the super limit e at place.

Step 5.2.2.3.3, if super limit e deletes after node v, still comprises two and the above node that is not labeled deletion, and super limit e still exists, otherwise deletes super limit e.

Step 5.2.2.3.4, recalculates the attribute function value of the adjacent node u of node v.

Step 5.2.2.3.5, if the attribute function value of adjacent node u is greater than the attribute function value of node v, upgrade the attribute function value of adjacent node u, and by the information of counting supplementary number group bin, location aided rebroadcast array pos and the auxiliary array vert of order, upgrade fast the order of adjacent node u in the non-strict descending sort of attribute function value of all nodes; Otherwise do not upgrade the attribute function value of adjacent node u and the order of sequence thereof.

In above-mentioned step 5.4, the initialization step of described discrete group intelligent search program is as follows.

Step 5.4.1, the global history optimal location vector of all colony intelligence particles of initialization, setting global history optimal location vector is the minimum initial division of composing power Directed Hypergraph.

Step 5.4.2, the self-position vector of the each colony intelligence particle of initialization, travel through each colony intelligence particle and set the self-position vector of each colony intelligence particle for the initial division of minimum tax power Directed Hypergraph, colony intelligence particle is composed the position of each dimensional space of power Directed Hypergraph in minimum.Colony intelligence particle is composed the position of certain dimensional space of power Directed Hypergraph in minimum, representing the node subset of minimum tax power Directed Hypergraph node division of living in corresponding to this dimensional space.

Step 5.4.3, self velocity vector of the each colony intelligence particle of initialization, travels through each colony intelligence particle and within the scope of threshold speed, random given each colony intelligence particle is at the velocity vector of each dimensional space.

Step 5.4.4, self historical optimal location vector of the each colony intelligence particle of initialization, the self-position vector that travels through each colony intelligence particle and set each colony intelligence particle is self historical optimal location vector.

In above-mentioned step 5.5, the step of described discrete group intelligent search program is as follows.

Step 5.5.1, the self-position vector of the each colony intelligence particle of projection, the self-position vector projection that travels through each colony intelligence particle and compose power Directed Hypergraph according to a upper flat seam alligatoring of each colony intelligence particle is to the refinement tax power Directed Hypergraph of present level layer, obtain each colony intelligence particle and compose the self-position vector of power Directed Hypergraph in the refinement of present level layer, colony intelligence particle is composed the position of each dimensional space of power Directed Hypergraph in the refinement of present level layer.Colony intelligence particle is composed the position of certain dimensional space of power Directed Hypergraph in the refinement of present level layer, representing that the node subset of weighing the division of living in of Directed Hypergraph node is composed in the refinement of present level layer corresponding to this dimensional space.

Step 5.5.2, self velocity vector of the each colony intelligence particle of projection, travel through each colony intelligence particle and compose on power Directed Hypergraph according to the refinement that self velocity vector that power Directed Hypergraph is composed in a upper flat seam alligatoring of each colony intelligence particle projects to present level layer, obtain each colony intelligence particle and compose self velocity vector of power Directed Hypergraph in the refinement of present level layer, colony intelligence particle is composed the speed of each dimensional space of power Directed Hypergraph in the refinement of present level layer.

Step 5.5.3, calculate the auxiliary array EDG[n of two dimension of each colony intelligence particle] [m], travel through each colony intelligence particle and compose according to the present level layer refinement of each colony intelligence particle the self-position vector of weighing Directed Hypergraph, calculate the auxiliary array EDG[n of two dimension of each colony intelligence particle] [m].

Step 5.5.4, calculate fast each colony intelligence particle and compose the value of cuing off of the self-position vector of power Directed Hypergraph in the refinement of present level layer, travel through each colony intelligence particle the auxiliary array EDG[n of two dimension according to each colony intelligence particle] [m], calculate fast each colony intelligence particle value of cuing off at the self-position vector of the refinement tax power Directed Hypergraph of present level layer.

Step 5.5.5, loop initialization, loop initialization counter COUNT is 0.

Step 5.5.6, upgrade self velocity vector of each colony intelligence particle, travel through each colony intelligence particle and according to the historical optimal location vector of each colony intelligence particle self, the global history optimal location vector of all colony intelligence particles, within the scope of threshold speed, upgrade self velocity vector.

Step 5.5.7, upgrade the auxiliary array EDG[n of self-position vector sum two dimension of each colony intelligence particle] [m], travel through each colony intelligence particle and calculate the vector sum of each colony intelligence particle self-position vector sum self velocity vector, renewal self-position vector, and then according to the auxiliary array EDG[n of two dimension of the self-position vector calculation colony intelligence particle of colony intelligence particle] [m].

Step 5.5.8, calculate fast the value of cuing off of the self-position vector of each colony intelligence particle, travel through each colony intelligence particle the auxiliary array EDG[n of self-position vector sum two dimension according to each colony intelligence particle] [m], the value of cuing off of the self-position vector of power Directed Hypergraph is composed in the present level layer refinement of calculating fast each colony intelligence particle.If the value of cuing off of the self-position vector of this colony intelligence particle is less than the value of cuing off of self historical optimal location vector, the historical optimal location vector that upgrades this colony intelligence particle is current self-position vector.If the value of cuing off of the self-position vector of this colony intelligence particle is less than the value of cuing off of the global history optimal location vector of all colony intelligence particles, the global history optimal location vector that upgrades all colony intelligence particles is the current self-position vector of this colony intelligence particle.

Step 5.5.9, repeating step 5.5.6,5.5.7,5.5.8, until cycle counter COUNT arrives the given upper limit.

In above-mentioned step 5.5.3 and step 5.5.7, the two dimension of described calculating colony intelligence particle is assisted array EDG[n] step of [m] is as follows.

Step 5.5.3.1, the auxiliary array EDG[n of two dimension] [m] zero clearing.

Step 5.5.3.2, read every node information that super limit comprises of eptr array and eind storage of array, the self-position vector of power Directed Hypergraph is composed in present level layer refinement based on colony intelligence particle, calculate every super limit at n dividing subset V1 ... the node number of Vn, the i.e. auxiliary array EDG[n of two dimension] two row of [m] deposit respectively the node number of the super limit of m bar n dividing subset.

In above-mentioned step 5.5.4 and step 5.5.8, the step of the value of cuing off of the self-position vector of described quick calculating colony intelligence particle is as follows.

Step 5.5.4.1, divides the value of cuing off zero clearing.

Whether step 5.5.4.2, travel through every super limit and finish, if access does not finish, exists super limit e not accessed, goes to step 5.5.4.3; Otherwise access finishes, return and divide the value of cuing off.

Step 5.5.4.3, if meet EDG[i] condition 1 and the EDG[j of [e] >=1] when the condition 2 of [e] >=1, mean that super limit e is more than or equal to 1 in the node number of dividing subset Vi and Vj, can judge that super limit e is amphibious limit, and by the weights on the cumulative current super limit of the division value of cuing off; Otherwise judge that super limit e is not amphibious limit, the division value of cuing off is constant.

Step 5.5.4.4, goes to step 5.5.4.2.

In above-mentioned step 5.5.6, the step of updating of self velocity vector of described colony intelligence particle is as follows.

Step 5.5.6.1, calculates current self velocity vector of colony intelligence particle and the product of inertia weight parameter.

Step 5.5.6.2, calculates the vectorial difference of the current self-position vector of the historical optimal location vector sum colony intelligence particle of colony intelligence particle, then multiplies each other with cognitive parameter.

Step 5.5.6.3, calculates the vectorial difference of the current self-position vector of the global history optimal location vector sum colony intelligence particle of all colony intelligence particles, then multiplies each other with social parameter.

Step 5.5.6.4, calculates the vector sum of three products that step 5.5.6.1, step 5.5.6.2, step 5.5.6.3 obtain, and upgrades self velocity vector of colony intelligence particle.

The present invention compared with prior art, has following apparent outstanding substantive distinguishing features and remarkable advantage.

1, improved the efficiency of task scheduling.

The present invention is based on multilevel partitioning and compose the cloud computing method for scheduling task of weighing Directed Hypergraph, arrive the conversion of composing power Directed Hypergraph file by task on the one hand, start the tax power Directed Hypergraph partition program based on multilevel partitioning, the tax power Directed Hypergraph generating is divided, avoided division methods directly in task, to divide; Can obtain preferably after division result by the inertia weight parameter in division methods, cognitive parameter and social parameter are set on the other hand, carry out again mapping and the scheduling of task, thereby effectively improve the efficiency of task scheduling, shorten the time span that task completes, realize the reasonable utilization of cloud computing resources, for cloud computing provides efficient Task Scheduling Mechanism.

2, improved the performance of task division.

The present invention is based on multilevel partitioning and compose the task optimization division methods of weighing Directed Hypergraph, by the auxiliary array EDG[n of two dimension] [m] store the node number of every super limit in dividing subset, realize the computing method of dividing the value of cuing off, effectively avoided the node in the super limit of traversal.Compare and compose the undirected hypergraph division methods of power and weighted and directed diagraph division methods, the method finds the task division result more excellent than prior art effectively, has reduced space complexity and time complexity, has finally improved significantly the performance that task optimization is divided.

By the description in conjunction with its accompanying drawing to the example of the cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph under cloud computing environment of the present invention below, can further understand object of the present invention, specific structural features and advantage.

Fig. 1 is the process flow diagram of the cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph under cloud computing environment of the present invention.

Fig. 2 is the memory form of the improvement compression of tax power Directed Hypergraph of the present invention.

Fig. 3 is the process flow diagram that the present invention is based on multilevel partitioning and compose the discrete group intelligent search program of optimizing phase in the cloud computing task division process of weighing Directed Hypergraph.

Embodiment.

In order more clearly to understand the technology contents of the cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph under cloud computing environment of the present invention, describe in detail especially exemplified by following instance.

The process flow diagram of the cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph of the present embodiment as shown in Figure 1.Under cloud computing environment, the task 101 that input user submits to, carries out the analysis 102 of type and class degree to user task, determine parallelization degree and the feature of task; According to parallelization degree and the feature of user task, and the peculiar property such as the resource sharing allocation scheme of cloud computing, user task is decomposed to 103 according to proceeding graininess rank; And then the task after decomposing is carried out to resource characteristics and analyze 104; According to the analysis result to task resource characteristic, set up the tax power Directed Hypergraph model 105 of describing its resource requirement and dependence; Save as and compose power Directed Hypergraph file 109 according to the file memory format that improves compression; Start the tax power Directed Hypergraph partition program 115 based on multilevel partitioning, read and compose power Directed Hypergraph file 109, obtain adopting the tax power Directed Hypergraph 111 of the memory form that improves compression; Enter into the alligatoring stage of multilevel partitioning, call the node matcher 116 of composing power Directed Hypergraph, the node that some is composed to power Directed Hypergraph combines, and power Directed Hypergraph 112 is composed in the alligatoring that obtains each flat seam; Enter into the initial division stage of multilevel partitioning, call the minimum initial division program 117 of composing power Directed Hypergraph minimum tax power Directed Hypergraph is divided, obtain the minimum initial division 113 of composing power Directed Hypergraph; Enter into the projection optimization stage of multilevel partitioning, compose the projection of power Directed Hypergraph from minimum and return initial tax power Directed Hypergraph, compose in power Directed Hypergraph in the refinement of each flat seam, the migration Partitioning optimization program 118 of calling refinement tax power Directed Hypergraph is optimized dividing, and obtains each flat seam refinement and composes the approximate non-bad optimal dividing 114 of weighing Directed Hypergraph; Enter into equilibrium stage, the tax power Directed Hypergraph partition program 115 of operation based on FM-EE method, makes the division result of initially composing power Directed Hypergraph meet equilibrium constraint, and the division result finally obtaining is stored as and composes power Directed Hypergraph division file 110; After detecting that tax power Directed Hypergraph partition program 115 based on multilevel partitioning completes division, divide file 110 and read corresponding division result from composing power Directed Hypergraph, according to the division result structure process level task subset 106 of composing power Directed Hypergraph; By MapReduce Task Scheduling Model, the task subset based on composing power Directed Hypergraph optimization division structure is shone upon and dispatched 107; In cloud computing environment, to based on composing power Directed Hypergraph optimization and divide job invocation in the task subset of structure and carrying out 108, the load of balanced cloud computing platform shorten the time span that whole task completes effectively.

The file memory format that the tax power Directed Hypergraph of the present embodiment improves compression referring to technology [1] formerly " G. Karypis and V. Kumar. HMetis 1.5.3:A Hypergraph Partitioning Package [R]. Technical report, Department of Computer Science, University of Minnesota, 1998. " and formerly technology [2] " Sun Lingyu, cold bright, Guo Kaiqiang, Zhu Ping. a kind of VLSI is designed into the converting system [J] of hypergraph. computer engineering and application, 2012, Vol.29, Issue.2, Pages 7-16. ".With technology [1,2] identical point formerly: the 1st parameter of the 1st row of file layout representing the number m on oriented tax Quan Chao limit, and the 2nd parameter representing the number n that composes power node; The 2nd row of file layout starts representing one article of oriented relevant information of composing Quan Chao limit to the capable every row of m+1; The capable beginning of m+2 of file layout representing a weights information of composing power node to the capable every row of m+n+1.With technology [1 formerly, 2] distinctive points: the 2nd row of file layout start capable to m+1 in, its remainder values except the 1st numerical value is the node information on oriented tax Quan Chao limit, wherein last numerical value of every row represents the tail end node information on oriented tax Quan Chao limit, and between the weights information and tail end node information of the source node information on oriented tax Quan Chao limit in oriented tax Quan Chao limit.

The memory form of the improvement compression of the tax power Directed Hypergraph of the present embodiment as shown in Figure 2.Storage organization uses adjncy array 204 to store the list information on the oriented super limit of each node all of its neighbor.Use xadj array 203 to store the start position information of the oriented super limit list of each node all of its neighbor, the reference position that the final position of i node is i+1 node subtracts 1, and the size of xadj array 203 is that the node number of composing in power Directed Hypergraph adds 1, xadj array, 203 last element for depositing the final position of last node.Use eind array 207 to store the list information of node that every oriented super limit comprises.Use eptr array 206 to store the start position information of the node list that every oriented super limit comprises, the reference position that the final position on j article of oriented super limit is j+1 article of oriented super limit subtracts 1, and the size of eptr array 206 is that the oriented super edge strip number of composing in power Directed Hypergraph adds 1, eptr array, 206 last element for depositing the final position on the oriented super limit of the last item.Use the weights information of vwgts array 202 storage nodes, and the size of vwgts array 202 is the node number of composing in power Directed Hypergraph.The weights information that uses hewgts array 205 to store to super limit, and the size of hewgts array 205 is the oriented super edge strip number of composing in power Directed Hypergraph.Suppose that group address starts from scratch, node numbering is started from scratch, i node in abutting connection with oriented super limit list storage in adjncy array 204, from adjncy[xadj[i]] to adjncy[xadj[i+1]-1]; The adjacent node list storage on j article of oriented super limit is in eind array 207, from eind[eptr[j]] to eind[eptr[j+1]-1], wherein the source node on j article of oriented super limit is eind[eptr[j]] to eind[eptr[j+1]-2], the tail end node on j article of oriented super limit is eind[eptr[j+1]-1].Legend 201 comprises 7 nodes and 8 oriented super limits altogether, and wherein the weights of the 6th node are 7, has 2 the oriented super limit f of adjacency, h, wherein weights corresponding to oriented super limit f are 4, and corresponding adjacent node is respectively node 7,3,6, and source node is node 7 and 3, and tail end node is node 6; Weights corresponding to oriented super limit h are 1, and adjacent node is respectively node 4,6 accordingly, and source node is node 4, and tail end node is node 6.

The node core value calculation procedure of the tax power Directed Hypergraph of the present embodiment referring to technology [3] formerly " Sun Lingyu; cold bright, hail sun. task core value calculating method [P] the .2014. patent of invention based on node attribute function in cloud computing environment. on April 6th, 2014 submit applications ".

Tax based on the FM method power Directed Hypergraph partition program of the present embodiment referring to technology [4] formerly " Fiduccia C; Mattheyses R. A linear-time heuristics for improving network partitions[C]. Proceedings of the 19th Design Automation Conference. Los Alamitos:IEEE Computer Society Press; 1982, Pages 175-181. ".

Tax based on the FM-EE method power Directed Hypergraph partition program of the present embodiment referring to technology [5] formerly " Karypis G; Aggarwal R; Kumar V; Shekhar S. Multilevel hypergraph partitioning:Applications in VLSI domain[J]. IEEE transactions on very large scale integration systems; 1999; Vol.7, Issue.1, Pages 69-79. ".

In tax based on the multilevel partitioning power Directed Hypergraph partition process of the present embodiment, as shown in Figure 3, step is as follows for the process flow diagram of the discrete group intelligent search program of optimizing phase.

A01: the global history optimal location vector of all colony intelligence particles of initialization, setting global history optimal location vector is the minimum initial division of composing power Directed Hypergraph.

A02: the self-position vector of the each colony intelligence particle of initialization, travel through each colony intelligence particle and set the self-position vector of each colony intelligence particle for the initial division of minimum tax power Directed Hypergraph, colony intelligence particle is composed the position of each dimensional space of power Directed Hypergraph in minimum.Colony intelligence particle is composed the position of certain dimensional space of power Directed Hypergraph in minimum, representing the node subset of minimum tax power Directed Hypergraph node division of living in corresponding to this dimensional space.

A03: self velocity vector of the each colony intelligence particle of initialization, travels through each colony intelligence particle and within the scope of threshold speed, random given each colony intelligence particle is at the velocity vector of each dimensional space.

A04: self historical optimal location vector of the each colony intelligence particle of initialization, the self-position vector that travels through each colony intelligence particle and set each colony intelligence particle is self historical optimal location vector.

A05: the self-position vector of the each colony intelligence particle of projection, the self-position vector projection that travels through each colony intelligence particle and compose power Directed Hypergraph according to a upper flat seam alligatoring of each colony intelligence particle is to the refinement tax power Directed Hypergraph of present level layer, obtain each colony intelligence particle and compose the self-position vector of power Directed Hypergraph in the refinement of present level layer, colony intelligence particle is composed the position of each dimensional space of power Directed Hypergraph in the refinement of present level layer.Colony intelligence particle is composed the position of certain dimensional space of power Directed Hypergraph in the refinement of present level layer, representing that the node subset of weighing the division of living in of Directed Hypergraph node is composed in the refinement of present level layer corresponding to this dimensional space.

A06: self velocity vector of the each colony intelligence particle of projection, travel through each colony intelligence particle and compose on power Directed Hypergraph according to the refinement that self velocity vector that power Directed Hypergraph is composed in a upper flat seam alligatoring of each colony intelligence particle projects to present level layer, obtain each colony intelligence particle and compose self velocity vector of power Directed Hypergraph in the refinement of present level layer, colony intelligence particle is composed the speed of each dimensional space of power Directed Hypergraph in the refinement of present level layer.

A07: the auxiliary array EDG[n of two dimension that calculates each colony intelligence particle] [m], travel through each colony intelligence particle and compose according to the present level layer refinement of each colony intelligence particle the self-position vector of weighing Directed Hypergraph, calculate the auxiliary array EDG[n of two dimension of each colony intelligence particle] [m].

A08: calculate fast each colony intelligence particle value of cuing off at the self-position vector of the refinement tax power Directed Hypergraph of present level layer, travel through each colony intelligence particle the auxiliary array EDG[n of two dimension according to each colony intelligence particle] [m], calculate fast each colony intelligence particle value of cuing off at the self-position vector of the refinement tax power Directed Hypergraph of present level layer.

A09: loop initialization, loop initialization counter COUNT is 0.

A10: self velocity vector that upgrades each colony intelligence particle, travel through each colony intelligence particle and according to the historical optimal location vector of each colony intelligence particle self, the global history optimal location vector of all colony intelligence particles, within the scope of threshold speed, upgrade self velocity vector.

A11: the auxiliary array EDG[n of self-position vector sum two dimension that upgrades each colony intelligence particle] [m], travel through each colony intelligence particle and calculate the vector sum of each colony intelligence particle self-position vector sum self velocity vector, renewal self-position vector, and then according to the auxiliary array EDG[n of two dimension of the self-position vector calculation colony intelligence particle of colony intelligence particle] [m].

A12: the value of cuing off of calculating fast the self-position vector of each colony intelligence particle, travel through each colony intelligence particle the auxiliary array EDG[n of self-position vector sum two dimension according to each colony intelligence particle] [m], the value of cuing off of the self-position vector of power Directed Hypergraph is composed in the present level layer refinement of calculating fast each colony intelligence particle.If the value of cuing off of the self-position vector of this colony intelligence particle is less than the value of cuing off of self historical optimal location vector, the historical optimal location vector that upgrades this colony intelligence particle is current self-position vector.If the value of cuing off of the self-position vector of this colony intelligence particle is less than the value of cuing off of the global history optimal location vector of all colony intelligence particles, the global history optimal location vector that upgrades all colony intelligence particles is the current self-position vector of this colony intelligence particle.

A13: repeating step A10, A11, A12, cycle counter COUNT adds 1, until cycle counter COUNT arrives the given upper limit.

A14: power Directed Hypergraph is composed in the alligatoring that projects to a flat seam.

A15: repeating step A05, A06, A07, A08, A09, A10, A11, A12, A13, A14, until initial tax power Directed Hypergraph is got back in projection.

Claims

1. the cloud computing method for scheduling task based on multilevel partitioning and tax power Directed Hypergraph, is characterized in that, concrete steps are as follows:

Step 1, class types degree is analyzed, the task that under input cloud computing environment, user submits to, and the analysis that it is carried out to type and class degree, determines parallelization degree and the feature of task;

Step 2, proceeding graininess decomposes, according to parallelization degree and the feature of user task, and the peculiar property such as the resource sharing allocation scheme of cloud computing, user task is decomposed according to proceeding graininess rank;

Step 3, resource characteristics is analyzed, according to peculiar properties such as the resource sharing allocation scheme of cloud computing, the task after decomposing is carried out to resource characteristics analysis;

Step 4, compose power Directed Hypergraph file generated, according to the analysis result to task resource characteristic, set up the tax power Directed Hypergraph model of describing its resource requirement and dependence, and save as and compose power Directed Hypergraph file according to the file memory format that improves compression;

Step 5, composing power Directed Hypergraph dividesstart the tax power Directed Hypergraph partition program based on multilevel partitioning, read and compose power Directed Hypergraph file, adopt the memory form that improves compression to store composing power Directed Hypergraph, the tax power Directed Hypergraph generating is divided, the division result finally obtaining is stored in and is composed in power Directed Hypergraph division file;

Step 6, task subset construction, after detecting that tax power Directed Hypergraph partition program based on multilevel partitioning completes division, divide file and read corresponding division result from composing power Directed Hypergraph, according to the division result structure process level task subset of composing power Directed Hypergraph;

Step 7, duty mapping schedulingby MapReduce Task Scheduling Model, task subset based on composing power Directed Hypergraph optimization and divide structure is shone upon and dispatch, realize job invocation and execution in cloud computing environment, the time span that the load of balanced cloud computing platform and the whole task of shortening complete effectively;

In above-mentioned step 4, the file memory format of the improvement compression of described tax power Directed Hypergraph as follows:

Step 4.1, the 1st parameter of the 1st row of file layout representing the number m on oriented tax Quan Chao limit, the 2nd parameter representing the number n that composes power node;

Step 4.2, the 2nd row of file layout starts representing one article of oriented relevant information of composing Quan Chao limit to the capable every row of m+1, the 1st numerical value is the weights information on oriented tax Quan Chao limit, its remainder values is the node information on oriented tax Quan Chao limit, wherein last numerical value of every row represents the tail end node information on oriented tax Quan Chao limit, and between the weights information and tail end node information of the source node information on oriented tax Quan Chao limit in oriented tax Quan Chao limit;

Step 4.3, the capable beginning of m+2 of file layout representing a weights information of composing power node to the capable every row of m+n+1;

In above-mentioned step 5, the step of the described power of the tax based on multilevel partitioning Directed Hypergraph partition program is as follows:

Step 5.1, reads and composes power Directed Hypergraph file, adopts the memory form that improves compression to store composing power Directed Hypergraph;

Step 5.2, enter into the alligatoring stage of multilevel partitioning, some node that adopts the node matcher of composing power Directed Hypergraph that the alligatoring of present level layer composed to power Directed Hypergraph combines, power Directed Hypergraph is composed in the alligatoring that obtains next flat seam, repeat this process until alligatoring tax power Directed Hypergraph is enough little, obtain a minimum power Directed Hypergraph of composing;

Step 5.3, enters into initial division stage of multilevel partitioning, and the tax power Directed Hypergraph partition program of operation based on FM method, obtains the minimum initial division of composing power Directed Hypergraph;

Step 5.4, the discrete group intelligent search program initialization of multilevel partitioning optimizing phase, the self-position vector of the each colony intelligence particle of global history optimal location vector sum of all colony intelligence particles of initialization, self velocity vector, self historical optimal location vector;

Step 5.5, enter into the optimizing phase of multilevel partitioning, compose the projection of power Directed Hypergraph from minimum and return initial tax power Directed Hypergraph, in the refinement tax power Directed Hypergraph of each flat seam, the projection division that adopts discrete group intelligent search program to compose power Directed Hypergraph to refinement is optimized;

Step 5.6, enters into equilibrium stage, the tax power Directed Hypergraph partition program of operation based on FM-EE method; Due in the tax power Directed Hypergraph partition process based on multilevel partitioning, may run counter to the equilibrium constraint of composing power Directed Hypergraph partition problem, therefore divide on the basis solving at the tax power Directed Hypergraph based on multilevel partitioning, the tax power Directed Hypergraph division methods of operation based on FM-EE method, make to divide solution and meet equilibrium constraint, thereby obtain composing the division solution of weighing Directed Hypergraph partition problem;

Step 5.7, is stored in the tax power Directed Hypergraph division result finally obtaining to compose in power Directed Hypergraph division file;

In above-mentioned step 5.1, the memory form of the improvement compression of described tax power Directed Hypergraph is as follows;

Step 5.1.1, uses vwgts storage of array to compose the weights information of node in power Directed Hypergraph, and the size of vwgts array is the node number of composing in power Directed Hypergraph;

Step 5.1.2, use the start position information of the oriented super limit list of the each node all of its neighbor of xadj storage of array, the reference position that the final position of i node is i+1 node subtracts 1, and the size of xadj array is that the node number of composing in power Directed Hypergraph adds last element of 1, xadj array for depositing the final position of last node;

Step 5.1.3, uses the list information on the oriented super limit of the each node all of its neighbor of adjncy storage of array, i node in abutting connection with oriented super limit list storage in adjncy array, from adjncy[xadj[i]] to adjncy[xadj[i+1]-1];

Step 5.1.4, the start position information of the node list that use every oriented super limit of eptr storage of array comprises, the reference position that the final position on j article of oriented super limit is j+1 article of oriented super limit subtracts 1, and the size of eptr array is that the oriented super limit number of composing in power Directed Hypergraph adds last element of 1, eptr array for depositing the final position on the oriented super limit of the last item;

Step 5.1.5, use the list information of eind storage of array node that every oriented super limit comprises, wherein the tail end node on every oriented super limit only has 1, and all direct precursor nodes of every oriented super limit tail end node be included in this oriented super limit source terminal concentrate; The node list storage on j article of oriented super limit is in eind array, from eind[eptr[j]] to eind[eptr[j+1]-1], wherein the source node on j article of oriented super limit is eind[eptr[j]] to eind[eptr[j+1]-2], the tail end node on j article of oriented super limit is eind[eptr[j+1]-1];

Step 5.1.6, the weights information on the use oriented super limit of hewgts storage of array, and the size of hewgts array is the oriented super limit number of composing in power Directed Hypergraph;

In above-mentioned step 5.2, the step that the node matcher of weighing Directed Hypergraph is composed in described present level layer alligatoring is as follows:

Step 5.2.1, the alligatoring of mark present level layer composed in power Directed Hypergraph all nodes in matching status not;

Step 5.2.2, the node core value calculation procedure of power Directed Hypergraph is composed in operation, and the core value of carrying out all nodes in present level layer alligatoring tax power Directed Hypergraph based on node attribute function value solves, and carries out non-strict descending sort according to the core value of node;

Step 5.2.3, according to the non-strict descending access of node core value in the node v of matching status not; If node v also has adjacent node not mate, choose so in there is no the adjacent node u in abutting connection with super limit matching status and weights maximum and node v coupling, and to mark these two nodes be matching status; If node v all of its neighbor matched nodes is in matching status, node v is still in matching status not so, and in coarsening process, direct copying is composed in power Directed Hypergraph to the alligatoring of next flat seam;

Step 5.2.4, step repeats previous step, until the access of all nodes finishes;

In above-mentioned step 5.2.2, the step of the node core value calculation procedure of described tax power Directed Hypergraph is as follows:

Step 5.2.2.1, calculates the attribute function value of all nodes;

Step 5.2.2.2, carries out non-strict descending sort to the attribute function value of all nodes;

Step 5.2.2.3, accesses each node according to the non-strict descending order of node attribute function value, calculates the core value of each node;

In above-mentioned step 5.2.2.2, the step of the non-strict descending sort of described node attribute function value is as follows:

Step 5.2.2.2.1, belongs to integer within the specific limits according to the attribute function value of node, scans the attribute function value of all nodes, adds up the node number of each attribute function value, is stored in counting supplementary number group bin;

Step 5.2.2.2.2, for each attribute function value, by counting supplementary number group bin, calculates in the attribute function value of all nodes, is less than the node number of this attribute function value, is stored in location aided rebroadcast array pos;

Step 5.2.2.2.3, scan the attribute function value of all nodes, for the attribute function value of each node, by location aided rebroadcast array pos, obtain the attribute function value of this node at the order of non-strict descending sort, and this order is stored in the auxiliary array vert of order;

In above-mentioned step 5.2.2.3, the step that the core value of described node v is calculated is as follows:

Step 5.2.2.3.1, exports the attribute function value of node v as core value;

Step 5.2.2.3.2, mark node v deletes from the super limit e at place;

Step 5.2.2.3.3, if super limit e deletes after node v, still comprises two and the above node that is not labeled deletion, and super limit e still exists, otherwise deletes super limit e;

Step 5.2.2.3.4, recalculates the attribute function value of the adjacent node u of node v;

Step 5.2.2.3.5, if the attribute function value of adjacent node u is greater than the attribute function value of node v, upgrade the attribute function value of adjacent node u, and by the information of counting supplementary number group bin, location aided rebroadcast array pos and the auxiliary array vert of order, upgrade fast the order of adjacent node u in the non-strict descending sort of attribute function value of all nodes; Otherwise do not upgrade the attribute function value of adjacent node u and the order of sequence thereof;

In above-mentioned step 5.4, the initialization step of described discrete group intelligent search program is as follows:

Step 5.4.1, the global history optimal location vector of all colony intelligence particles of initialization, setting global history optimal location vector is the minimum initial division of composing power Directed Hypergraph;

Step 5.4.2, the self-position vector of the each colony intelligence particle of initialization, travel through each colony intelligence particle and set the self-position vector of each colony intelligence particle for the initial division of minimum tax power Directed Hypergraph, colony intelligence particle is composed the position of each dimensional space of power Directed Hypergraph in minimum; Colony intelligence particle is composed the position of certain dimensional space of power Directed Hypergraph in minimum, representing the node subset of minimum tax power Directed Hypergraph node division of living in corresponding to this dimensional space;

Step 5.4.3, self velocity vector of the each colony intelligence particle of initialization, travels through each colony intelligence particle and within the scope of threshold speed, random given each colony intelligence particle is at the velocity vector of each dimensional space;

Step 5.4.4, self historical optimal location vector of the each colony intelligence particle of initialization, the self-position vector that travels through each colony intelligence particle and set each colony intelligence particle is self historical optimal location vector;

In above-mentioned step 5.5, the step of described discrete group intelligent search program is as follows:

Step 5.5.1, the self-position vector of the each colony intelligence particle of projection, the self-position vector projection that travels through each colony intelligence particle and compose power Directed Hypergraph according to a upper flat seam alligatoring of each colony intelligence particle is to the refinement tax power Directed Hypergraph of present level layer, obtain each colony intelligence particle and compose the self-position vector of power Directed Hypergraph in the refinement of present level layer, colony intelligence particle is composed the position of each dimensional space of power Directed Hypergraph in the refinement of present level layer; Colony intelligence particle is composed the position of certain dimensional space of power Directed Hypergraph in the refinement of present level layer, representing that the node subset of weighing the division of living in of Directed Hypergraph node is composed in the refinement of present level layer corresponding to this dimensional space;

Step 5.5.2, self velocity vector of the each colony intelligence particle of projection, travel through each colony intelligence particle and compose on power Directed Hypergraph according to the refinement that self velocity vector that power Directed Hypergraph is composed in a upper flat seam alligatoring of each colony intelligence particle projects to present level layer, obtain each colony intelligence particle and compose self velocity vector of power Directed Hypergraph in the refinement of present level layer, colony intelligence particle is composed the speed of each dimensional space of power Directed Hypergraph in the refinement of present level layer;

Step 5.5.3, calculate the auxiliary array EDG[n of two dimension of each colony intelligence particle] [m], travel through each colony intelligence particle and compose according to the present level layer refinement of each colony intelligence particle the self-position vector of weighing Directed Hypergraph, calculate the auxiliary array EDG[n of two dimension of each colony intelligence particle] [m];

Step 5.5.4, calculate fast each colony intelligence particle and compose the value of cuing off of the self-position vector of power Directed Hypergraph in the refinement of present level layer, travel through each colony intelligence particle the auxiliary array EDG[n of two dimension according to each colony intelligence particle] [m], calculate fast each colony intelligence particle value of cuing off at the self-position vector of the refinement tax power Directed Hypergraph of present level layer;

Step 5.5.5, loop initialization, loop initialization counter COUNT is 0;

Step 5.5.6, upgrade self velocity vector of each colony intelligence particle, travel through each colony intelligence particle and according to the historical optimal location vector of each colony intelligence particle self, the global history optimal location vector of all colony intelligence particles, within the scope of threshold speed, upgrade self velocity vector;

Step 5.5.7, upgrade the auxiliary array EDG[n of self-position vector sum two dimension of each colony intelligence particle] [m], travel through each colony intelligence particle and calculate the vector sum of each colony intelligence particle self-position vector sum self velocity vector, renewal self-position vector, and then according to the auxiliary array EDG[n of two dimension of the self-position vector calculation colony intelligence particle of colony intelligence particle] [m];

Step 5.5.8, calculate fast the value of cuing off of the self-position vector of each colony intelligence particle, travel through each colony intelligence particle the auxiliary array EDG[n of self-position vector sum two dimension according to each colony intelligence particle] [m], the value of cuing off of the self-position vector of power Directed Hypergraph is composed in the present level layer refinement of calculating fast each colony intelligence particle; If the value of cuing off of the self-position vector of this colony intelligence particle is less than the value of cuing off of self historical optimal location vector, the historical optimal location vector that upgrades this colony intelligence particle is current self-position vector; If the value of cuing off of the self-position vector of this colony intelligence particle is less than the value of cuing off of the global history optimal location vector of all colony intelligence particles, the global history optimal location vector that upgrades all colony intelligence particles is the current self-position vector of this colony intelligence particle;

Step 5.5.9, repeating step 5.5.6,5.5.7,5.5.8, until cycle counter COUNT arrives the given upper limit;

In above-mentioned step 5.5.3 and step 5.5.7, the two dimension of described calculating colony intelligence particle is assisted array EDG[n] step of [m] is as follows:

Step 5.5.3.1, the auxiliary array EDG[n of two dimension] [m] zero clearing;

Step 5.5.3.2, read every node information that super limit comprises of eptr array and eind storage of array, the self-position vector of power Directed Hypergraph is composed in present level layer refinement based on colony intelligence particle, calculate every super limit at n dividing subset V1 ... the node number of Vn, the i.e. auxiliary array EDG[n of two dimension] two row of [m] deposit respectively the node number of the super limit of m bar n dividing subset;

In above-mentioned step 5.5.4 and step 5.5.8, the step of the value of cuing off of the self-position vector of described quick calculating colony intelligence particle is as follows:

Step 5.5.4.1, divides the value of cuing off zero clearing;

Whether step 5.5.4.2, travel through every super limit and finish, if access does not finish, exists super limit e not accessed, goes to step 5.5.4.3; Otherwise access finishes, return and divide the value of cuing off;

Step 5.5.4.3, if meet EDG[i] condition 1 and the EDG[j of [e] >=1] when the condition 2 of [e] >=1, mean that super limit e is more than or equal to 1 in the node number of dividing subset Vi and Vj, can judge that super limit e is amphibious limit, and by the weights on the cumulative current super limit of the division value of cuing off; Otherwise judge that super limit e is not amphibious limit, the division value of cuing off is constant;

Step 5.5.4.4, goes to step 5.5.4.2;

In above-mentioned step 5.5.6, the step of updating of self velocity vector of described colony intelligence particle is as follows:

Step 5.5.6.1, calculates current self velocity vector of colony intelligence particle and the product of inertia weight parameter;

Step 5.5.6.2, calculates the vectorial difference of the current self-position vector of the historical optimal location vector sum colony intelligence particle of colony intelligence particle, then multiplies each other with cognitive parameter;

Step 5.5.6.3, calculates the vectorial difference of the current self-position vector of the global history optimal location vector sum colony intelligence particle of all colony intelligence particles, then multiplies each other with social parameter;