CN110363700A - A parallel enumeration method of custom instructions based on depth map segmentation - Google Patents

Abstract

The invention provides a parallel enumeration method of custom instructions based on depth map segmentation, and relates to the technical field of electronic design automation. The method first adopts the master-slave parallel mode, and the master node in the computing cluster receives the data flow graph generated in the intermediate representation generation stage of the automatic generation process of the dedicated custom instruction set as input; The graph segmentation method divides the original data flow graph into several subgraphs, and assigns the divided subgraphs to idle computing nodes in the computing cluster; at the same time, the running time of the divided subtasks is predicted, according to the predicted time of all subtasks and the number of computing nodes to determine whether it is necessary to continue to divide complex subtasks; the computing nodes use the convex subgraph enumeration algorithm to enumerate custom instructions from the received subgraph. The method of the invention can more effectively ensure the load balance among the computing nodes and achieve an approximate linear speedup ratio.

Description

A parallel enumeration method of custom instructions based on depth map segmentation

technical field

The invention relates to the technical field of electronic design automation, in particular to a parallel enumeration method of custom instructions based on depth map segmentation.

Background technique

To meet the ever-increasing demands of embedded applications for high performance and low power consumption, custom computing by using accelerators or custom function units (Custom Function Unit) is increasingly applied to embedded systems. Among them, the special-purpose processor is one of the most important solutions to realize the customized operation.

A dedicated processor is a processor with an optimized architecture and instruction set. By extending the instruction set, part of the code of the target application program is executed on the benchmark processor, and other computationally intensive codes are implemented in the hardware of custom instructions - custom executed in the functional unit. Application-specific chips are designed for a specific application and can only run a specific application, so they lack a certain degree of flexibility. A benchmark processor in an application-specific processor architecture can guarantee a certain flexibility relative to an application-specific chip (ASIC). Second, designing and producing application-specific chips has the disadvantages of long design cycles and high testing costs.

Compared with general-purpose processors, special-purpose processors use custom instructions to encapsulate a series of basic operation instructions (such as addition, subtraction, multiplication, and logical operations), so that these basic operation instructions are automatically chained according to data dependencies without data. The basic instructions of dependencies are parallelized, thereby greatly improving the speed of operations. In addition, since multiple basic instructions are encapsulated into a custom instruction, the number of instruction fetches and the number of data transfers between registers and the processor are reduced, and the power consumption of special-purpose processors is significantly lower than that of general-purpose processors.

The automatic generation of extended instruction sets is the key to the design and implementation of special-purpose processors. The automatic generation of the application-specific extended instruction set of the special-purpose processor generally includes four steps as shown in Figure 1: intermediate representation generation, user-defined instruction enumeration, user-defined instruction selection, and code generation. The intermediate representation generation phase converts the application into a suitable intermediate representation, for example, a control data flow graph; the custom instruction enumeration phase enumerates all subgraphs that satisfy the constraints as candidate custom instructions under architectural constraints; The instruction selection stage selects a part of the best subgraphs from the enumerated subgraphs (graphical representation of custom instructions) as the final custom instruction according to different design purposes. These selected custom instructions constitute the final extended instruction set. The code generation phase is responsible for automatically generating the hardware implementation code of the custom instructions, as well as converting the source code into new code containing the custom instructions.

Custom instruction enumeration and custom instruction selection are the two most critical and complex stages in the automatic generation of extended instruction sets. There has been a lot of research work on custom instruction enumeration, all of which use serial methods. However, when the problem is large, the serial method may not be able to give the optimal design in a reasonable time or The optimal design scheme cannot be given. The problem of custom instruction enumeration is to enumerate all convex subgraphs that satisfy certain design constraints or user constraints from the data flow graph corresponding to the application as candidate custom instructions. The number of subgraphs (AS) in a given dataflow graph may be at most 2n, where n is the number of nodes in the dataflow graph. It can be seen that the enumeration of custom instructions is a problem with very high algorithm complexity. In order to reduce the complexity of the problem, the previous research either introduced the constraints of the microarchitecture or artificially added some constraints. Depending on the constraints, previous studies can be categorized and analyzed as follows:

(1) Tree subgraph (TS): In order to reduce the complexity of enumeration, early research mainly focused on enumerating all tree subgraphs. However, only enumerating tree subgraphs as custom instructions can only improve performance or reduce power very limitedly.

(2) Multiple Input Single Output Subgraph (MISO): This type of research focuses on enumerating all subgraphs with multiple inputs and a single output. Although only enumerating the multi-input single-output subgraph can greatly reduce the complexity of the problem, the performance improvement or power consumption reduction brought by the multi-input single-output subgraph as a custom command is still very limited.

(3) Multiple-input multiple-output subgraphs (MIMO): Due to the limited number of read and write ports (I/O) of registers, some recent researches mainly focus on enumerating subgraphs that satisfy the I/O constraints. Among them, Pozzi et al. proposed an enumeration algorithm based on binary decision tree, which reduces the search space by using the monotonicity of the number of outputs that form subgraphs in topological order in the data flow graph. In order to make better use of the topological structure of the data flow graph, Xiao et al. proposed a more efficient algorithm. Xiao et al. proposed a parallel enumeration method of custom instructions based on the one-shot graph segmentation method. When there are few computing nodes, this method can achieve an approximate linear speedup. Chen et al. proved for the first time that the upper limit of the number of subgraphs satisfying the I/O condition is n ^IN+OUT , where n is the number of nodes in the data flow graph, and also proposed a method that can be enumerated separately through parameter settings. Algorithms for connected and separating subgraphs. However, the running time of this algorithm on enumerating all subgraphs (including connected and separating subgraphs) is only comparable to that of the algorithm proposed by Pozzi et al. Xiao et al. proposed an algorithm that can flexibly enumerate connected subgraphs or separate subgraphs according to user requirements. Experiments show that the algorithm runs one to two orders of magnitude faster than the algorithm proposed by Chen et al. on enumerating all subgraphs.

(4) Maximum convex subgraph (MaxMIMO): Through experiments, it is found that custom instructions enumerated in the case of relaxing I/O constraints can often bring higher performance improvements. Therefore, in recent years, some studies have also focused on enumerating maximal convex subgraphs without considering the I/O constraints. It should be noted that although MaxMIMO submaps can bring higher performance improvement as a custom command, they usually do not have good reusability or generality.

In addition to the research on the above types of custom instruction enumeration, in recent years, some scholars have also proposed related algorithms to enumerate all convex subgraphs (ACS). Gutin et al. proved for the first time that the upper bound on the number of convex subgraphs in a data flow graph is 2 ⁿ +n+1-d _n , where n is the number of nodes in the data flow graph, if n is an even number d _n = 2* 2 ^n/2 if _n is odd dn =3*2 ^(n-1)/2 . Wang et al. proposed an algorithm capable of enumerating all convex subgraphs or enumerating convex subgraphs satisfying size constraints, which is on average 3.29 times faster than the algorithm proposed by Balisterera et al. Wang et al. also proposed a parallel enumeration method of subgraphs based on one-shot graph segmentation. The experimental results show that compared with the serial method, when the number of computing nodes is small, the parallel method can achieve an approximate linear speedup. However, as the number of computing nodes increases, the problem of unbalanced load gradually emerges, and the speedup ratio obtained by this method tends to decrease. Rezgui et al. proposed a parallel processing method that ensures load balancing among computing nodes by decomposing the initial problem into enough sub-problems. The author found through a large number of experiments that when the number of sub-problems allocated to each computing node is usually between 30 and 100, the load balance can be better guaranteed. However, since it is difficult to determine the appropriate number of sub-problems allocated to each computing node, this method may still cause unbalanced load among computing nodes, thereby affecting the efficiency of parallel processing.

SUMMARY OF THE INVENTION

The technical problem to be solved by the present invention is to aim at the deficiencies of the above-mentioned prior art, and provide a parallel enumeration method of custom instructions based on depth map segmentation, which adopts a master-slave parallel mode to realize parallel enumeration of custom instructions.

In order to solve the above-mentioned technical problems, the technical solution adopted by the present invention is: a method for parallel enumeration of self-defined instructions based on depth map segmentation, comprising the following steps:

Step 1. Adopt the master-slave parallel mode, and the master node in the computing cluster receives the data flow graph generated in the intermediate representation generation stage of the automatic generation process of the dedicated custom instruction set as input;

The data flow graph is a directed acyclic graph G=(V, E), wherein the node set V={v ₁ , . . . , v _n } represents basic instructions, and n is the The number of edge sets E={e ₁ ,...,e _m }∈V×V represents the data dependency between instructions, and m represents the number of edges in the data flow graph;

Step 2. Using the depth map segmentation method based on the non-linear regression task runtime prediction model to divide the original data flow graph into several sub-graphs, and assign the divided sub-graphs to idle computing nodes in the computing cluster. The specific method is as follows:

Step 2.1. Divide the custom instruction enumeration task T into k subtasks at one time, as shown in the following formula:

Among them, G _k =G-{v ₁ , v ₂ ,...,v _k-1 } is the k-th subgraph generated after the data flow graph G is divided, k=1, 2,...,|v|,| v| is the number of nodes in the graph G, E(G _k , v _k ) means enumerating all custom instructions including the node v _k from the k-th subgraph G _k ;

Step 2.2, establish a task running time prediction model based on nonlinear regression, and predict the running time of the divided subtasks;

When the constraints are certain, the enumeration time of the custom instruction is related to the number of nodes and edges in the graph, and the enumeration time of the custom instruction increases with the increase of the number of nodes or edges; for a given subgraph Taking task T _k and its corresponding data flow graph G _k (V _k , E _k ), the worst running time of custom instruction enumeration is where α is a constant, |V _k | is the number of nodes in the graph G _k ; there are many generalization forms of the base in the formula, here we assume:

where f(|V _k |, |E _k |) is a polynomial function of the number of nodes |V _k | and the number of edges |E _k |;

The Taylor series expansion of formula (2) is used to obtain the task running time prediction model, as shown in the following formula:

Among them, the parameter k' is used to control the expansion of the model, and the parameters a _{i, j} are obtained by fitting the experimental data by using the nonlinear regression method;

Step 2.3. According to the predicted time of all subtasks and the number of computing nodes, determine whether it is necessary to continue to divide complex subtasks; if the predicted running time of the subtask exceeds the given time limit, continue to divide the subtask into several subtasks. Subtask, until the predicted running time of all subtasks is less than or equal to the given time upper limit, otherwise perform step 3; the given time upper limit is the average predicted running time of all current subtasks;

Assuming that the predicted running time of the subtask _Tk is greater than the given time upper limit, continue to divide _Tk , as shown in the following formula:

Among them, G _{k, l} =G _k -{w ₁ ,w ₂ ,...,w _l-1 } is the l-th subgraph generated after the subtask Tk is divided, E(G _{k , l} , {v _k , w _l }) means enumerating all custom instructions including node v _k and node w _l from the subgraph G _{k, l} ; h as the cutoff value, the prediction running time of T _{k, h-1} is greater than the current average prediction Running time, the predicted running time of T _{k, h} is less than the current average predicted running time; if the predicted running time of sub-task T _{k, l} is still greater than the upper limit, continue to divide T _{k, l} into several sub-tasks;

Step 3. The computing node uses the convex subgraph enumeration algorithm to enumerate custom instructions from the received subgraph;

The enumeration custom instruction is: from a given data flow graph G=(V, E), enumerate all subgraphs S that satisfy the following conditions: (1) the subgraph S is a convex subgraph; (2) ) subgraph S is a connected graph;

The convex subgraph is: for the subgraph S of G, v∈V _s , if any path between u and v in G only passes through the nodes in S, then S is said to be a convex subgraph of G;

The connected graph is: for the subgraph S of G, v∈V _s , there is at least one path connecting u and v, then S is a connected graph.

The beneficial effect of adopting the above technical solution is that: a method for parallel enumeration of custom commands based on depth map segmentation provided by the present invention, taking into account the high complexity of the problem of custom command enumeration, a method based on task running time is adopted. The depth map segmentation method of the prediction model divides the initial problem into several sub-problems, and the sub-problems are solved independently by the computing nodes. Compared with the existing parallel methods, the method of the present invention can more effectively ensure the load balance among the computing nodes, and achieve an approximate linear speedup ratio.

Description of drawings

1 is a flowchart of automatic generation of an application-specific extended instruction set provided by the background technology of the present invention;

2 is a flowchart of a method for parallel enumeration of custom instructions based on depth map segmentation provided by an embodiment of the present invention;

3 is a framework diagram of a method for parallel enumeration of custom instructions based on depth map segmentation according to an embodiment of the present invention;

4 is a comparison diagram of speedup ratios obtained by three parallel methods for four test benchmark programs according to an embodiment of the present invention, wherein (a) is the benchmark program MP3, (b) is the benchmark program MESA, and (c) is the benchmark program IIR, (d) is the benchmark program DES3;

5 is a comparison of the total running time of each computing node using three parallel methods provided by an embodiment of the present invention, wherein (a) is an MGP parallel method, (b) is an EPS parallel method, and (c) is an ODP parallel method;

FIG. 6 is a comparison diagram of the time predicted by the running time prediction model of the present invention and the actual running time provided by an embodiment of the present invention.

Detailed ways

The specific embodiments of the present invention will be described in further detail below with reference to the accompanying drawings and embodiments. The following examples are intended to illustrate the present invention, but not to limit the scope of the present invention.

In this embodiment, a method for parallel enumeration of custom instructions based on depth map segmentation, as shown in Figure 2 and Figure 3, includes the following steps:

Step 1. Adopt the master-slave parallel mode, and the master node in the computing cluster receives the data flow graph generated in the intermediate representation generation stage of the automatic generation process of the dedicated custom instruction set as input;

The data flow graph is a directed acyclic graph G=(V, E), wherein the node set V={v ₁ , . . . , v _n } represents basic instructions, and n is the The number of edge sets E={e ₁ ,...,e _m }∈V×V represents the data dependency between instructions, and m represents the number of edges in the data flow graph;

Step 2. Using the depth map segmentation method based on the non-linear regression task runtime prediction model to divide the original data flow graph into several sub-graphs, and assign the divided sub-graphs to idle computing nodes in the computing cluster. The specific method is as follows:

Step 2.1. Divide the custom instruction enumeration task T into k subtasks at one time, as shown in the following formula:

Among them, G _k =G-{v ₁ , v ₂ ,...,v _k-1 } is the k-th subgraph generated after the data flow graph G is divided, k=1, 2,...,|v|,| v| is the number of nodes in the graph G, E(G _k , v _k ) means enumerating all custom instructions including the node v _k from the k-th subgraph G _k ;

Step 2.2. It can be seen that the sub-tasks generated by the above segmentation are obviously more complex than other tasks, and the load balance between computing nodes cannot be guaranteed. It is necessary to select complex sub-tasks for further segmentation according to the predicted running time of the sub-tasks; therefore, Build a task running time prediction model based on nonlinear regression to predict the running time of the divided subtasks;

When the constraints are certain, the enumeration time of the custom instruction is related to the number of nodes and edges in the graph, and the enumeration time of the custom instruction increases with the increase of the number of nodes or edges; for a given subgraph Taking task T _k and its corresponding data flow graph G _k (V _k , E _k ), the worst running time of custom instruction enumeration is where α is a constant, |V _k | is the number of nodes in the graph G _k ; there are many generalization forms of the base in the formula, here we assume:

where f(|V _k |, |E _k |) is a polynomial function of the number of nodes |V _k | and the number of edges |E _k |;

The Taylor series expansion of formula (2) is used to obtain the task running time prediction model, as shown in the following formula:

Among them, the parameter k' is used to control the expansion of the model, and the parameters a _{i, j} are obtained by fitting the experimental data by using the nonlinear regression method;

Step 2.3. According to the predicted time of all subtasks and the number of computing nodes, determine whether it is necessary to continue to divide complex subtasks; if the predicted running time of the subtask exceeds the given time limit, continue to divide the subtask into several subtasks. subtasks, until the predicted running time of all subtasks is less than or equal to a given time upper limit; the given time upper limit is the average predicted running time of all current subtasks;

Assuming that the predicted running time of the subtask _Tk is greater than the given time upper limit, continue to divide _Tk , as shown in the following formula:

Among them, G _{k, l} =G _k -{w ₁ ,w ₂ ,...,w _l-1 } is the l-th subgraph generated after the subtask Tk is divided, E(G _{k , l} , {v _k , w _l }) means enumerating all custom instructions including node v _k and node w ₁ from the subgraph G _{k, l} ; h as the cutoff value, the prediction running time of T _{k, m-1} is greater than the current average prediction Running time, the predicted running time of T _{k, n} is less than the current average predicted running time; if the predicted running time of subtask T _{k, l} is still greater than the upper limit, continue to divide T _{k, l} into several subtasks;

Step 3. The computing node uses the convex subgraph enumeration algorithm to enumerate custom instructions from the received subgraph;

The enumeration custom instruction is: from a given data flow graph G=(V, E), enumerate all subgraphs S that satisfy the following conditions: (1) the subgraph S is a convex subgraph; (2) ) subgraph S is a connected graph;

The convex subgraph is: for the subgraph S of G, v∈V _s , if any path between u and v in G only passes through the nodes in S, then S is said to be a convex subgraph of G;

The connected graph is: for the subgraph S of G, v∈V _s , there is at least one path connecting u and v, then S is a connected graph.

This embodiment also provides a pseudo-code for a parallel enumeration method of custom instructions based on depth map segmentation, as shown in Algorithm 1:

Algorithm 1: Custom Instruction Parallel Enumeration Method

Input: data flow graph G(V, E)

Output: The set of subgraphs S satisfying the constraints

The environments of the computing nodes used in this embodiment are all i3-3240 3.4GHz processors and 4-GB main memory. The test benchmark set is derived from MiBench. These benchmarks are front-end compiled and simulated by the general-purpose compilation platform GeCoS. The characteristics of the data flow graph used in the embodiment and the running time of the serial algorithm are shown in Table 1. Columns NV, NE, and NS in the table represent the number of nodes, the number of edges, and the number of enumerated subgraphs in the data flow graph, respectively. The running time of the serial algorithm is recorded in the column Runtime (in milliseconds).

Table 1 Benchmark program characteristics and serial algorithm running time

benchmark program NV NE NS Runtime MP3 43 66 181,533,673 221,554 MESA 37 65 7,554,499 8,027 IIR 40 56 23,195,414 28,725 DES3 45 60 637,125,710 649,873

In this embodiment, the parallel enumeration method for custom instructions of the present invention (denoted as MGP) is respectively combined with the parallel enumeration method proposed by Wang et al. (denoted as ODP) and the parallel method proposed by Rezgui et al. ^] (denoted as EPS) ) were compared. The configuration of the computing nodes involved are all i3-32403.4GHz processors, 4-GB main memory, and the three parallel methods are all implemented using Hadoop 1.0.0. The computing node adopts the subgraph enumeration algorithm proposed by Wang et al. to perform subgraph enumeration. The test benchmark programs used in this embodiment are shown in Table 1. For the parallel method EPS, the number of subtasks allocated to each computing node is set to 50, so the total number of subtasks is 50*w, where w is the number of computing nodes.

For the four benchmark programs in Table 1, the speedup results obtained by the three parallel algorithms under different numbers of computing nodes are shown in Figure 4. By comparing the results, it can be observed that when the computing nodes are less than or equal to 10, the speedup ratios obtained by the three parallel algorithms are similar, and they are all approximately linear speedup ratios. However, as the number of computing nodes increases, the speedup obtained by the MGP method is significantly better than the other two parallel algorithms, and the EPS method is better than the ODP method. Among them, the speedup ratio achieved by EPS method and ODP method cannot keep a linear growth with the increase of computing nodes. Especially for the ODP method, when the number of computing nodes increases to 18, the growth of the acceleration ratio tends to be flat, and no longer increases linearly with the increase of computing nodes. The comparison results also show that the MGP method is better than the EPS method and ODP method in dealing with the load balancing problem.

In order to further analyze the difference in the speedup ratios obtained by the above three parallel methods, the present embodiment compares and analyzes the total running time of each computing node when the three parallel methods use the same number of computing nodes to enumerate custom instructions. Based on the previous tests, the total running time of each computing node is counted. For the benchmark test program DES3, when the number of computing nodes is 8, the total running time of each computing node using the three parallel methods is shown in Figure 5. It can be observed that using the MGP method, the total running time difference between the various computing nodes is small (the difference between the maximum running time and the minimum running time is 13.1%), while using the EPS method or the ODP method, the total running time between the various computing nodes. The time difference is obvious (the difference between the maximum running time and the minimum running time is 21.3% and 39.6%, respectively). By comparison, it is found that there is a big difference in the size of the sub-images generated by the EPS method and the ODP method. The EPS method mainly considers the number of sub-images generated after segmentation without considering the size of the sub-images. The ODP method adopts the one-time segmentation method. The difference in the size of the generated subgraphs is more obvious, while the MGP method can further divide the larger subgraph into several smaller subgraphs under the guidance of the task running time prediction model, so the subgraphs generated by this method are of relatively balanced size. The comparison results further illustrate that the MGP method of the present invention can make the tasks assigned to each computing node have similar complexity, and can ensure the load balance among the computing nodes, thereby obtaining an approximate linear speedup ratio.

At the same time, this embodiment also evaluates the running time prediction model. First, 200 data flow graphs are randomly generated. The number of nodes |V| of these data flow graphs ranges from 20 to 55, and the number of edges |E|=1.5*|V|. For each randomly generated dataflow graph, use the subgraph enumeration algorithm on a computer configured with an i3-3240 3.4GHz processor and 4-GB main memory to enumerate all convex subgraphs that satisfy the constraints, and record The corresponding actual algorithm running time. Then, use the 185 actual data (number of nodes, edges, running time) as training samples to perform multivariate nonlinear regression fitting on the parameters in formula (3). To evaluate the task runtime prediction model, the time predicted by the task runtime prediction model was compared with the actual runtime for 15 randomly generated data flow graphs. The comparison between the predicted running time given by the subgraph enumeration task running time prediction model and the actual running time is shown in Figure 6. The comparison results show that the predicted running time is very close to the actual running time, with an error range of 3% to 12%.

Since extra time is required for graph segmentation and subtask running time prediction, this embodiment analyzes in detail the proportion of the time required for graph segmentation processing based on the task running time prediction model to the total running time of the parallel enumeration method. For four different test benchmark programs, under the condition that the number of computing nodes is 12, the proportion of the time required for graph segmentation based on the task running time prediction model to the total running time is shown in Table 2. Column Benchmark, column Pre.&Par.Time, column TotalTime and column Ratio respectively represent the test benchmark program name, graph segmentation and task prediction time (in milliseconds), total running time and the ratio (%). From the results, it can be seen that the time required for graph segmentation processing based on task running time prediction is about 3.82% of the total running time on average. This also shows that the graph segmentation method based on the task time prediction model of the present invention has high efficiency, and the required time is significantly less than the total running time, and the total running time of the parallel method will not be significantly affected.

Table 2 Comparison of the time required for graph segmentation and the total running time based on the task running time prediction model

Finally, it should be noted that the above embodiments are only used to illustrate the technical solutions of the present invention, but not to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that it can still be The technical solutions described in the foregoing embodiments are modified, or some or all of the technical features thereof are equivalently replaced; and these modifications or replacements do not make the essence of the corresponding technical solutions depart from the scope defined by the claims of the present invention.

Claims (3)

1. a kind of custom instruction parallel enumerating method based on depth map segmentation, it is characterised in that: the following steps are included:

Step 1, using Master-slave parallel mode, the host node in computing cluster receives dedicated custom instruction collection and automatically generates process Intermediate representation generation phase generate data flow diagram as input；

The data flow diagram is a kind of directed acyclic graph G=(V, E), wherein nodal set V={ v₁..., v_nIndicate elementary instruction, N is the number of data flow diagram node, side collection E={ e₁..., e_m∈ V × V indicate instruction between data dependence relation, m indicate number According to the number on flow graph side；

Step 2, using the depth image segmentation method based on nonlinear regression Runtime prediction model by original data stream Figure is divided into several subgraphs, and the subgraph after segmentation is distributed to the idle calculate node in computing cluster, method particularly includes:

Step 2.1, custom instruction is enumerated task T progress be disposably divided into k subtask, shown in following formula:

Wherein, G_k=G- { v₁, v₂..., v_k-1It is k-th of subgraph generating after data flow diagram G segmentation, and k=1,2 ..., | v |, | V | for the nodal point number in figure G, E (G_k, v_k) indicate from k-th of subgraph G_kIn enumerate it is all comprising node v_kCustom instruction；

Step 2.2 establishes the Runtime prediction model based on nonlinear regression, to the runing time of the subtask of segmentation It is predicted；

Step 2.3, according to the predicted time of all subtasks and the number of calculate node, judge whether to need to continue to complicated Subtask is split；If the prediction runing time of subtask is more than given time upper limit, which is continued to divide For several subtasks, until the prediction runing time of all subtasks is less than or equal to given time upper limit, step is otherwise executed Rapid 3；The given time upper limit is the consensus forecast runing time of current all subtasks；

Step 3, calculate node enumerate custom instruction from the subgraph received using convex portion enumeration of graph algorithm；

It is described to enumerate custom instruction are as follows: the institute for meeting the following conditions is enumerated from a given data flow diagram G=(V, E) Subgraph S:(1) subgraph S is convex portion figure；(2) subgraph S is connected graph；

The convex portion figure are as follows: for the subgraph S of G,If in any path in G between u and v all only by S Node, then claiming S is the convex portion figure of G；

The connected graph are as follows: for the subgraph S of G,There are at least one paths to connect u and v, then S is connected graph.

2. a kind of custom instruction parallel enumerating method based on depth map segmentation according to claim 1, feature exist In: the step 2.2 method particularly includes:

When constraint condition is certain, custom instruction enumerate the time in figure nodal point number and number of edges it is related, customized finger Order is enumerated the time and is increased with the increase of nodal point number or number of edges；The subgraph given for one enumerates task T_kAnd its it is corresponding Data flow diagram G_k(V_k, E_k), the worst runing time that custom instruction is enumerated isWherein α is constant, | V_k| it is Scheme G_kIn nodal point number；There are many extensive forms of the truth of a matter in formula, it is assumed here that:

Wherein, f (| V_k|, | E_k|) be nodal point number | V_k| and number of edges | E_k| polynomial function；

Taylor series expansion is carried out to formula (2) and obtains Runtime prediction model, shown in following formula:

Wherein, parameter k ' is used for the expansion of Controlling model, parameter a_{I, j}By using the method for nonlinear regression, according to experiment number It is obtained according to fitting.

3. a kind of custom instruction parallel enumerating method based on depth map segmentation according to claim 2, feature exist In: the step 2.3 method particularly includes:

Assuming that subtask T_kPrediction runing time be greater than given time upper limit, to T_kContinue to divide, following formula institute Show:

Wherein, G_{K, l}=G_k-{w₁, w₂..., w_l-1It is subtask T_kFirst of the subgraph generated after segmentation, E (G_{K, l}, { v_k, w_l}) It indicates from subgraph G_{K, l}It enumerates comprising node v_kWith node w_lAll custom instructions；H is as cutoff value, T_{K, h-1}Prediction fortune The row time is greater than current consensus forecast runing time, T_{K, h}Prediction runing time be less than current consensus forecast runing time；If Subtask T_{K, l}Prediction runing time upper limit value is still greater than, then continue T_{K, l}It is divided into several subtasks.