CN106814994A - A kind of parallel system optimization method towards big data - Google Patents

Abstract

A kind of parallel system optimization method towards big data, the present invention relates to the parallel system optimization method towards big data.The invention aims to solve prior art both for a certain specific algorithm, without for complicated formula, and the calculating problem that time-consuming.Detailed process is：Step one：Data-intensive formula is carried out into abstract treatment；Step 2：Data-intensive formula after the treatment of step one abstract is generated into formula semantic tree；Step 3：The semantic tree that step 2 is generated is carried out abbreviation and generates formula dependency graph；Step 4：The formula dependency graph that step 3 is generated is layered and is generated task sequence；Step 5：Task dependence is generated in parallel system according to the task sequence that step 4 is generated, the result of calculation of data-intensive formula is obtained after execution.The present invention is used for data analysis field.

Description

A parallel system optimization method for big data

technical field

The invention relates to a large data-oriented parallel system optimization method.

Background technique

Data-intensive complex calculations refer to calculations that need to calculate a large amount of data and have complex dependency structures, most of which involve continuous addition and multiplication operations, such as The calculation process of this formula needs to consume a lot of time. Data-intensive complex calculations are the basis of existing big data analysis, and have very important applications in the field of data analysis. The existing technology has the following problems:

1. Existing platforms only provide basic operations. For example, Hadoop only provides Map and Reduce operations. This mode is very difficult for inexperienced programmers.

2. Existing toolkits only provide computational formula calculation methods in existing algorithms, and cannot provide universal formula calculation methods.

3. Under the existing technology, data-intensive complex calculations can only be completed through multiple rounds of data redistribution, and the running time is greatly increased.

Data-intensive (complex) formulas refer to formulas that contain multiple statistical calculations such as addition and multiplication, as well as formulas with a large amount of calculation data.

Contents of the invention

The present invention is to solve the problem that the prior art is aimed at a certain specific algorithm in the parallel system, not for complex calculation expressions, and the calculation takes a long time, and proposes a large data-oriented parallel system optimization method.

A parallel system optimization method oriented to big data is implemented in the following steps:

Step 1: Abstract data-intensive calculations;

Step 2: Generate an arithmetic semantic tree from the data-intensive formula after the abstraction in Step 1;

Step 3: Simplify the semantic tree generated in step 2 and generate an algorithm dependency graph;

Step 4: Layer the formula dependency graph generated in Step 3 and generate a task sequence;

Step 5: Generate task dependencies in the parallel system according to the task sequence generated in step 4, and obtain the calculation result of the data-intensive formula after execution.

Invention effect:

1. Experiments have proved that the algorithm shows better optimization effects when the amount of data is larger. Under the data volume of GB level, the calculation time is saved by 57.3% on average.

2. Experiments have proved that under this algorithm, the calculation time of the formula does not depend on the complexity of the formula, but depends on the number of tasks generated by the formula.

3. The algorithm is universal and can be applied to different parallel platforms, such as Hadoop and Spark; it does not require the user's programming experience, and the optimized calculation result can be obtained by giving complex expressions.

Description of drawings

Fig. 1 is a flowchart of the present invention;

Figure 2 is a semantic tree structure diagram; in the figure "/" represents the division sign, "-" represents the minus sign, "*" represents the multiplication sign, "sum" represents the addition symbol, "pow" represents the power symbol, and avg" represents Mean sign, "count" stands for count sign, "x", "y" and "2" stand for manipulated variable and operand.

Fig. 3 is a simplified process diagram;

Fig. 4 is a layered schematic diagram;

Figure 5 is the generated task sequence diagram; the task sequence in the figure is from bottom to top, MapReduce:avg() represents the map reduction operation that performs a round of average calculation; MapReduce:avg(), count() represents the execution of a round of average The map-reduce operation of calculation and counting calculation; MapReduce:sum() represents the map-reduce operation of performing one round of continuous addition calculation; a total of 4 rounds of MapReduce are the map-reduce operation.

Fig. 6 is a task sequence scheduling diagram;

Figure 7 is a simple aggregation operation configuration diagram; in the figure, the input variable x is mapped to Key:value, which is a key-value pair, and the result is reduced through reduce, the valuesum is added to the result, and the valuecount is counted. Configuration operators: sum and count, that is, continuous addition and counting operations in the reduction process.

Figure 8 is a configuration diagram of complex aggregation operations;

Figure 9 is a comparison chart of running time before optimization of CCA, MCA, and ACF;

Figure 10 is a comparison chart of running time after optimization of CCA, MCA, and ACF;

Figure 11 is a comparison chart before and after ACF optimization;

Figure 12 is a comparison chart before and after MCA optimization;

Figure 13 is a comparison chart before and after CCA optimization.

detailed description

Specific embodiment one: a kind of big data-oriented parallel system optimization method comprises the following steps:

Step 1: Abstract data-intensive and complex calculations;

Step 2: Generate an arithmetic semantic tree from the data-intensive formula after the abstraction in Step 1;

Step 3: Simplify the semantic tree generated in step 2 and generate an algorithm dependency graph;

Step 4: Layer the formula dependency graph generated in Step 3 and generate a task sequence;

Step 5: Generate task dependencies in the parallel system according to the task sequence generated in step 4, and obtain the calculation result of the data-intensive formula after execution.

Specific embodiment 2: The difference between this embodiment and specific embodiment 1 is that in the first step, the data-intensive calculation formula is abstracted as follows:

The sub-operations in data-intensive formulas are divided into two types: simple calculations and aggregation calculations. Each aggregation operation needs to be completed with a round of MapReduce, and the data-intensive calculations are functionally abstracted; the simple calculations are four arithmetic operations, multiplication Square and square root, aggregation calculation is a statistical operation, and MapReduce is a programming model for parallel operations on large-scale data sets (greater than 1TB).

Other steps and parameters are the same as those in Embodiment 1.

Embodiment 3: The difference between this embodiment and Embodiment 1 or 2 is that in Step 2, the data-intensive formula after the abstraction processing in Step 1 is generated into an arithmetic semantic tree. The specific process is as follows:

Extract the variables in the data-intensive formula, and determine the sub formula, the operator (addition, subtraction, multiplication, division, addition, multiplication, etc.) in the sub formula as the parent node, and the calculation variable corresponding to the operator as the child node to generate a computational semantic tree, and the semantic tree has only one aggregation operation on each path from a leaf node to a root node. Sub-calculation as in the formula ∑x ² etc.

Other steps and parameters are the same as those in Embodiment 1 or Embodiment 2.

Embodiment 4: The difference between this embodiment and one of Embodiments 1 to 3 is that in Step 3, the semantic tree generated in Step 2 is simplified and the specific process of generating the formula dependency graph is as follows:

Merge all the nodes corresponding to the same variable in the semantic tree into the same node, and merge the nodes that perform the same calculation on the same variable into the same node.

Other steps and parameters are the same as those in Embodiments 1 to 3.

Embodiment 5: The difference between this embodiment and one of Embodiments 1 to 4 is that in Step 4, the formula dependency graph generated in Step 3 is layered and the specific process of generating the task sequence is as follows:

Layer according to the distance between the variable and the operator in the formula dependency graph, use any variable as the initial node, and use the number of nodes passed by the variable to the operator as the number of layers of the operator. When there are multiple paths between the variable and the operator When , the path with the most nodes shall prevail, and each operator is a node;

Extract the aggregation operation of the same variable in each layer, and generate a task sequence in the order from the initial node to the final node; the aggregation operation of different variables in each layer is put into a round of MapReduce in parallel for execution; the aggregation operation sequence of the same variable in each layer Rows are put into one round of MapReduce for execution.

Other steps and parameters are the same as in one of the specific embodiments 1 to 4.

Embodiment one: as shown in Figure 1, the steps of a parallel system optimization method for big data are:

1. Abstract formula structure

Mathematical formula The sub-operations are divided into two types: simple calculation and aggregation calculation. Each aggregation operation needs to be completed by one round of MapReduce. Perform functional abstraction on the calculation, such as expressing the continuous addition symbol as sum(), and proceed to the next step after abstraction. Abstract the above formula into a functional expression:

2. Generate an arithmetic semantic tree

Generate the semantic tree structure shown in Figure 2 according to the dependency relationship of the formula.

3. Simplify and generate a formula dependency graph

Simplify the semantic tree. We adopt two principles for semantic tree simplification.

All-to-1. All nodes corresponding to the same variable are merged into the same node to eliminate redundant nodes.

Same-to-1. Nodes that perform the same calculation on the same variable are combined into the same node. In this way, the same calculation can be performed in the same task, thereby reducing the data redistribution process.

Apply these two principles to simplify the example, as shown in Figure 3. After simplification, the formula dependency graph is generated, and the task sequence of the formula is generated according to the formula dependency graph.

4. Generate task order

A calculation task plan is generated according to the calculation dependency graph, and the calculation is used for task allocation. First, we stratify according to the distance between the formula and the variable, as shown in Figure 4.

MapReduce tasks are generated according to the layers, and the same operation of each layer generates the same task. The generated task sequence is shown in Figure 5.

5. Parallel system execution

The task sequence generates the job dependency sequence in the parallel system, and puts it into the existing big data parallel system for execution. As shown in Figure 6. This formula generates three MapReduce tasks to execute in parallel.

After execution, the final calculation result of the formula is obtained. Experiments prove that the algorithm can greatly improve the computational efficiency.

The algorithm is implemented in Hadoop. System configuration is performed through the Job Configure file. We divide the configuration process into simple aggregate operations and complex aggregate operations. Simple aggregation operation configuration is directly configured in the Reduce process, as shown in Figure 7.

Complex aggregate operation configuration requires building a tree in Mapper to determine the operation process and generate calculation results, as shown in Figure 8.

The method of the present invention can be applied in existing parallel platforms, such as Sparks and Hyracks. It is only necessary to slightly modify the configuration conditions to be suitable for the above-mentioned system.

As a basic optimization algorithm for data analysis, the method of the present invention can be applied in the direction of data analysis, such as business analysis, finance, industry, agriculture and other fields.

Complex correlation analysis Complex correlation analysis (CCA):

Matrix correlation analysis Matrix correlation analysis (MCA):

Arbitrary complex formula (ACF):

The running time comparison chart, as shown in Figure 9 to Figure 13, shows that the running time has been greatly reduced before and after optimization. And it can be observed that the larger the amount of data, the more obvious the optimization effect.

Claims (5)

1. a kind of parallel system optimization method towards big data, it is characterised in that the parallel system towards big data is excellent Change method is comprised the following steps：

Step one：Data-intensive formula is carried out into abstract treatment；

Step 2：Data-intensive formula after the treatment of step one abstract is generated into formula semantic tree；

Step 3：The semantic tree that step 2 is generated is carried out abbreviation and generates formula dependency graph；

Step 4：The formula dependency graph that step 3 is generated is layered and is generated task sequence；

Step 5：Task dependence is generated in parallel system according to the task sequence that step 4 is generated, is counted after execution According to the result of calculation of intensive formula.

2. a kind of parallel system optimization method towards big data according to claim 1, it is characterised in that the step Data-intensive formula is carried out into abstract treatment in one to be specially：

Sub- computing in data-intensive formula is divided to and is defined as two kinds of simple computation and Aggregation computation, each aggregate operation will Completed with a wheel MapReduce, data-intensive formula is carried out into functional expression abstract；The simple computation is arithmetic, multiplies Side and evolution, Aggregation computation are statistical calculation, and MapReduce is programming model.

3. a kind of parallel system optimization method towards big data according to claim 1 and 2, it is characterised in that described It is by the data-intensive formula generation formula semantic tree detailed process after the treatment of step one abstract in step 2：

The variable in data-intensive formula is extracted, and determines sub- formula, using the operator in sub- formula as father node, correspondence The calculating variable of the operator generates formula semantic tree as child node, and the semantic tree is each from leaf node to root node Only one of which aggregate operation on paths.

4. a kind of parallel system optimization method towards big data according to claim 3, it is characterised in that the step The semantic tree that step 2 is generated carried out abbreviation and generates the detailed process of formula dependency graph in three be：

The node of the identical variable of all correspondences in semantic tree is merged into Same Vertices, the knot of identical calculations is carried out to identical variable Point merges into Same Vertices.

5. a kind of parallel system optimization method towards big data according to claim 1,2 or 4, it is characterised in that institute State to be layered and generated the detailed process of task sequence the formula dependency graph that step 3 is generated in step 4 and be：

Distance according to variable AND operator in formula dependency graph is layered, using aleatory variable as start node, with any The nodes that variable passes through to operator as the number of plies where operator, when having mulitpath between variable AND operator, To be defined by the path more than nodes, wherein each operator is a node；

The aggregate operation of the identical variable of each layer is extracted, task sequence is sequentially generated according to start node to terminating node；Often The aggregate operation of different variables is parallel in one layer is put into execution in a wheel MapReduce；The aggregation fortune of identical variable in each layer Calculate and be serially put into execution in a wheel MapReduce.