CN107015861A - A kind of Cascade Reservoirs Optimized Operation multi-core parallel concurrent based on Fork/Join frameworks calculates design method - Google Patents

Abstract

The invention discloses a multi-core parallel computing design method for cascade reservoir group optimal scheduling based on the Fork/Join framework, comprising the following steps: (1) constructing the Fork/Join parallel framework; (2) realizing the Fork/Join parallel framework; (3) Parallel design of typical intelligent methods in coarse-grained mode; (4) Parallel design of typical dynamic programming methods in fine-grained mode. Through the test results of PSCWAGA, PAHPSO, PDP, and PDDDP method examples, the use of Fork/Join multi-core parallel framework can give full play to the parallel performance of multi-core CPU, greatly reduce the calculation time consumption, and significantly improve the calculation efficiency of the algorithm; the larger the calculation scale of the parallel method, The more time-consuming the calculation is reduced, the more obvious the advantages of parallel computing are; and as the calculation scale gradually increases, the speedup ratio and parallel efficiency gradually increase, and the speedup ratio is closer to the ideal speedup ratio.

Description

A multi-core parallel computer for cascade reservoir group optimal scheduling based on Fork/Join framework Computational design method

technical field

The invention relates to the field of refined scheduling of cascade reservoir groups, in particular to a multi-core parallel computing design method for optimal scheduling of cascade reservoir groups based on the Fork/Join framework.

Background technique

In recent years, my country's hydropower industry has developed very rapidly. By the end of 2015, the total installed capacity of hydropower in China had reached 320 million kW, accounting for about 1/4 of the total installed capacity of hydropower in the world, making it a well-deserved super power in the world. At present, my country's hydropower energy is mainly distributed in the 13 major hydropower bases. The development of these hydropower bases is gradually forming a large number of cascade reservoirs on the main stream, which generally present the characteristics of a large number of cascade reservoirs and large installed capacity. The scale of power stations in river basins is often more than ten or even dozens of levels. For example, 11 power stations are planned in the Wujiang River Basin, and 9 have been built; 15 power stations are planned for the Lancang River, and 6 have been built; 10-level power stations are planned for the Hongshui River, and 9 power stations have been built; 28 power stations are planned for Dadu River, and more than 10 have been built. For such a large-scale cascade reservoir group joint optimal dispatching problem, the difficulties in solving it are mainly reflected in the following three aspects:

(1) Large-scale high-dimensionality: The high-dimensionality problem is the main difficulty that restricts the solution of the optimal dispatching problem of large-scale hydropower station groups. With the continuous expansion of the calculation scale of the hydropower system, the number of calculations required to solve the problem, the amount of computer storage, and the time spent on calculation increase rapidly for each additional level of power station. For some methods, the growth rate increases exponentially, making the algorithm solution very difficult. , the computational efficiency is significantly reduced, and it has a great impact on the scalability of the algorithm. This problem is called the "curse of dimensionality" in dynamic programming. In fact, in other solving algorithms, the limitation of the system scale to the solution also exists to varying degrees, and has become the main bottleneck restricting the application of hydropower optimal dispatching engineering.

(2) Multi-stage dynamic optimization: The optimal scheduling of hydropower station groups is a multi-stage dynamic optimization problem. Usually, it is discretized into multiple time periods in the time dimension, and each time period needs to meet the connection constraints such as reservoir water balance constraints or water level output fluctuations, and the operation mode of the previous time period directly affects the power generation head and power generation amount of the subsequent time period, so each stage is closely related. Connection; at the same time, the global equality control conditions such as the water level at the end of the dispatching period and the total output limit of the hydropower system make the system decomposition and the relaxation of multivariable correlation constraints very difficult.

(3) Complex hydroelectric power connection: The optimal scheduling of hydropower station groups needs to consider the hydraulic connection between power stations. The power station located upstream and with high regulation performance regulates the natural water flow, thus changing the inflow of downstream power stations. When dispatching the outbound flow of the upstream power station, the inbound flow of the downstream power station is composed of the outbound flow of the upstream power station and the interval flow between the two power stations, and the inbound flow is the main input for optimal scheduling, which directly affects the current power station scheduling decision. Therefore, the inbound flow of each power station is affected by the scheduling of its direct upstream power station. If the current power station has multiple upstream power stations, the optimization problem is more complicated. In addition, because hydropower plays a very important scheduling task in the power system, the optimal scheduling of hydropower station groups needs to consider the constraints related to the power system, such as the minimum output of the system that needs to be met to balance the power load, the safe power transmission limit of the transmission section, etc. As a result, there is a close power connection in the hydropower station group, and it also increases the difficulty of solving the optimal dispatching of the hydropower station group.

Facing the situation of such a large-scale joint scheduling of reservoirs and groups in my country's hydropower system, the use of traditional optimization methods has certain limitations, and it has been unable to meet the refined scheduling needs of power grids, hydropower companies, and river basin organizations. Important scientific problems to be solved urgently in scheduling work.

At present, dynamic programming methods and emerging intelligent algorithms are two major types of methods mainly used in the field of cascade reservoir group optimal dispatching. However, the dynamic programming method is limited by the solution scale. Large-scale problems easily lead to the curse of dimensionality. The calculation scale increases exponentially with the increase in the number of power station calculations. There is a certain competition between the solution accuracy of the swarm algorithm and the calculation scale, that is, the population size or The greater the number of iterations, the greater the probability of finding a global optimal solution in the solution space, and the higher the accuracy of the solution, but it also means that the calculation will take more time and the solution efficiency will be lower, especially for the current large-scale cascade hydropower station groups in my country. When optimizing the schedule, the solution efficiency drops very significantly. Therefore, in order to make it possible to solve the optimal dispatching problem of large-scale hydropower station groups in a limited time, and at the same time ensure the quality of the optimization results, it is of great scientific significance to study how to improve the computational efficiency of these two common optimization methods.

Parallel computing has always been a research hotspot in the field of computer science. Multi-core parallel technology based on multi-core processors has been widely used in practical projects due to its unique advantages such as easy parallel implementation, stable operating environment, and low cost. As an entry point, designing a parallel optimization method with appropriate granularity will be a feasible way to improve the efficiency of the system solution. At present, there are many research results on parallel optimization methods in the field of optimal dispatching of cascade hydropower station groups. The method parallelization method is mainly realized through two modes: coarse-grained design and fine-grained design, and the results generally use the mature OpenMP, MPI or .NET Parallel models or frameworks that are effectively compatible with languages such as Fortran, C++, and C# provide convenience for the parallelization of serial methods developed in languages such as Fortran, C++, and C#. However, these frameworks cannot effectively adapt to the serial method developed by the Java language (one of the mainstream assembly languages), and are difficult to apply to the parallel development and transformation of Java coded programs. The Fork/Join parallel framework is a multi-core parallel framework developed based on Java source code, and has been integrated into the concurrent program package of Java version 7 as a standard program, which can simplify the programming work of developers to the greatest extent and facilitate the serialization of Java coding development. Moreover, since the framework was put forward late, there are few achievements in the parallel calculation of the cascade reservoir group optimal dispatching method, and there is no related achievement that systematically expounds its implementation method and performance influencing factors. Therefore, the applicant developed the language based on the Java language, applied the Fork/Join multi-core parallel framework, adopted the coarse-grained design mode and the fine-grained design mode respectively, realized the parallel computing of various methods, and invented a method based on Fork/Join Multi-core parallel computing design method for optimal dispatching of cascade reservoir groups in the framework.

Contents of the invention

The purpose of the present invention is to provide a multi-core parallel computing design method based on the Fork/Join framework for cascade reservoir group optimization scheduling. This process can give full play to the acceleration performance of the multi-core configuration without changing the existing computer configuration. Calculation time, improve solution efficiency.

To achieve the above object, the present invention provides the following technical solutions:

A multi-core parallel computing design method for cascade reservoir group optimal scheduling based on Fork/Join framework, comprising the following steps:

(1) Constructing the Fork/Join parallel framework: The core of the Fork/Join parallel framework inherits the characteristics of the "divide and conquer method". By recursively dividing the original problem, several smaller, independent and parallel computing sub-problems are formed; After each sub-problem is independently and parallelly calculated, the sub-results of each sub-problem can be combined to output the final result of the original problem; the Fork/Join framework has designed a unique thread pool technology. When the program starts to execute, the default created and available processing The number of active threads with the same number of processors; in the execution process of the "divide and conquer method", a threshold that can be freely set to control the size of the sub-problem is defined as the upper limit of the sub-problem size, that is, when the sub-problem size is less than or equal to the threshold When the execution of the "divide and conquer method" ends, each sub-problem is evenly distributed to different threads to start parallel computing; in addition, in the process of sub-problem parallel computing, Fork/Join designed a unique double-ended queue sorting mode, and adopted "Work stealing" algorithm, that is, when a thread's queue computing tasks are empty, it will "steal" computing tasks from the tail of other thread queues in the working state;

(2) Realize the Fork/Join parallel framework: 1) The code class implemented by the algorithm needs to inherit the Fork/Join application interface class java.util.concurrent.RecursiveAction or java.util.concurrent.RecursiveTask; 2) Select the threshold to divide tasks; 3 ) Implement the void compute() method of the Fork/Join interface class; 4) Set the task division method;

(3) Parallel design of typical intelligent methods in coarse-grained mode: 1) Parallel adaptive chaotic global annealing genetic algorithm:

Step 1 parameter initialization. Set the population size m, the number of chaotic sequences d, the maximum number of population iterations Kmax, the initial temperature T0 and the adaptive parameters Pc1, Pc2, Pm1, Pm2;

Step 2 population initialization. According to the Logistic mapping formula, n groups of chaotic sequences are randomly generated in the chaotic space, which are mapped to the solution space to generate m different individuals to form a population. The population individuals are composed of the water level values (zil, zi2, ..., zin) of each power station in different periods;

Step 3 Create a thread pool. The number of worker threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join at the same time;

Step 4 starts the parallel computing process;

Parallel Step① According to the set calculation threshold, the parent population is divided into multiple smaller sub-populations according to the recursive mode;

The subpopulation sets divided by Parallel Step② are evenly distributed to different logical threads. To maintain CPU load balance, ensure that each logical thread is assigned the same number of subtasks;

Parallel Step③ The subpopulation assigned to each thread runs calculations independently, and the main calculation steps are as follows:

A evaluates individual fitness;

B selection operation: adopt the overall annealing selection mechanism, allow the parent to participate in the competition, and screen out the next generation of individuals;

C interleave operation: use the arithmetic interleave method to perform the interleave operation;

D mutation operation: use non-uniform mutation method to perform mutation operation;

E Calculate the individual fitness of the parent and offspring: when the parent individual Xi generates offspring X′ _i through crossover and mutation, if f(X′ _i )>f(X _i ), replace Xi with X′ _i ; otherwise, Retain Xi with probability exp[(f(X′ _i )-f(X _i ))/T _k ];

F parameter update. The number of iterations k=k+1, the temperature Tk=1/ln(k/T0+1).

G judges whether the subpopulation iteration is over; according to the annealing temperature Tk or the maximum number of iterations as the convergence condition, when any one of the two reaches the initially set convergence condition, return A; otherwise, the subpopulation calculation convergence ends;

Parallel Step④ summarizes and merges the optimized solutions of each subpopulation as a result set and returns to the main thread.

Step 5 Filter out the optimal solution from the result set, and the calculation is completed and the thread pool is destroyed.

2) Parallel Adaptive Hybrid Particle Swarm Optimization (PAHPSO)

Step1 parameter initialization;

Step2 population initialization;

Step3 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join at the same time;

Step4 starts the parallel computing process;

Parallel Step① According to the set calculation threshold, the parent population is divided into multiple smaller sub-populations according to the recursive mode;

The subpopulation sets divided by Parallel Step② are evenly distributed to different logical threads. To maintain CPU load balance, ensure that each logical thread is assigned the same number of subtasks;

Parallel Step③ The subpopulation assigned to each thread runs calculations independently, and the main calculation steps are as follows:

A Calculate particle fitness, particle individual optimal solution and population global optimal solution; particle fitness is compared with its individual optimal solution, if the particle fitness is better than its individual optimal solution, the current particle position is taken as the individual optimal position ; Particle fitness is compared with the global optimal solution of the population, if the particle fitness is better than the global optimal solution of the population, the current particle position is taken as the global optimal position of the population;

B Calculate the particle energy and the particle energy threshold; if the particle energy is lower than the current particle energy threshold, perform a mutation operation on the current position and velocity of the particle;

C calculates the particle similarity and the particle similarity threshold; if the similarity of two adjacent particles is less than the current particle similarity threshold, perform a mutation operation on the historical optimal position of the worse particle;

D introduces a neighborhood-based greedy random search strategy to update the individual optimal position of the particle; if the current position searched in the neighborhood is greater than the fitness of the particle before the search, replace the individual position of the particle before the search, and then use the post-search The individual particle position is compared with the optimal position of the particle history and the global optimal position of the population, and the optimal position of the particle history and the optimal position of the population are updated;

E updates the speed and position of the particle population;

F judges whether the subpopulation iteration is over; if the current iteration number is less than the maximum iteration number, return (1); otherwise, the subpopulation calculation convergence ends;

Parallel Step④ Summarize and merge the calculation results of each subpopulation as a result set and return to the main thread;

Step5 Screen out the optimal solution from the result set, and the calculation is completed and the thread pool is destroyed;

3) Coarse-grained parallel design pattern and method of Fork/Join framework

According to the calculation process of PSCWAGA and PAHPSO methods, the coarse-grained parallel design mode and method of the Fork/Join framework are summarized:

Step1 initialize algorithm parameters and population size;

Step2 Create a thread pool and set the calculation threshold;

Step3 uses the Fork/Join parallel framework to divide the parent population into multiple sub-populations in a recursive mode, and distribute them equally to each child thread;

Step4 Each sub-population is optimized and calculated according to the original serial method flow until the iteration of each sub-population ends;

Step5 summarizes and merges the calculation results of each subpopulation as a result set and returns to the main thread;

Step6 Filter out the optimal solution from the result set, finish the calculation and destroy the thread pool;

(4) Parallel design of typical dynamic programming method in fine-grained mode: 1) Parallel dynamic programming method:

Step1 data preparation; obtain the characteristic values and characteristic curves of the basic properties of the power station required for calculation, including the characteristic water level of the power station, output coefficient, water level-storage capacity curve, discharge-tail water level curve, etc. The number determines the discrete state variable St;

Step2 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logic threads, and set the calculation threshold of Fork/Join at the same time;

Step3 starts the parallel computing process;

Parallel Step① Construct the parent task of parallel calculation; the solution calculation of all water storage state variables combined in Bt(St, It, Nt) in the iterative cycle is taken as the parent task, and the water level, output, power generation and other indicators during the calculation process are created storage;

Parallel Step② divides the parent task into multiple smaller sub-tasks in a recursive mode according to the set calculation threshold;

The set of subtasks divided by Parallel Step③ is evenly distributed to different logical threads. To maintain CPU load balance, ensure that each logical thread is assigned the same number of subtasks;

Parallel Step④ The subtasks assigned to each thread run calculations independently, that is, all the discrete combinations of states in the subtasks are solved and calculated in the recursive formula;

Parallel Step⑤ Summarize and merge the calculation results of each subtask as a result set and return to the main thread;

Step4 Filter out the optimal solution from the result set, and the calculation is completed and the thread pool is destroyed;

2) Parallel discrete differential dynamic programming method:

Step1 data preparation; obtain the characteristic values and characteristic curves of the basic properties of the power station required for calculation, including the characteristic water level of the power station, output coefficient, water level-storage capacity curve, discharge-tail water level curve, etc. The number determines the discrete state variable St;

Step2 sets the number of iterative corridors, and generates an initial feasible solution as the initial trajectory for calculation;

Step3 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join at the same time;

Step4 selects the maximum corridor width as the current corridor;

Step5 starts the parallel computing process;

Parallel Step①Construct the parent task of parallel computing in the current corridor; combine all the water storage state variables in the corridor in Bt(St, It, Nt) to solve the calculation as the parent task, and provide the calculation process for the water level, output, and power generation and other indicators to create storage space;

Parallel Step② divides the parent task into multiple smaller sub-tasks in a recursive mode according to the set calculation threshold;

The set of subtasks divided by Parallel Step③ is evenly distributed to different logical threads; in order to maintain CPU load balance, ensure that the number of subtasks assigned to each logical thread is the same;

Parallel Step④ The subtasks assigned to each thread run calculations independently, that is, all the discrete combinations of states in the subtasks are solved and calculated in the recursive formula;

Parallel Step⑤ Summarize and merge the calculation results of each subtask as a result set and return to the main thread;

Step 5 Output the current optimal trajectory according to the result set, and judge whether the current optimal trajectory is the same as the initial trajectory; if they are the same, enter Step 6; if not, enter Step 7;

Step 6 Determine whether the current corridor is the last corridor; if not, set the next smaller corridor width as the current corridor width, and enter Step 7; if so, the calculation is terminated, and the optimal trajectory is output as the calculated optimal solution and Destroy the thread pool;

Step 7 sets the current optimal trajectory as the initial trajectory for the next iteration, and returns to Step 5;

3) Fork/Join framework fine-grained parallel design pattern and method:

According to the calculation process of PDP and PDDDP method, the fine-grained parallel design mode and method of Fork/Join framework are summarized:

Step1 data preparation. Including initialization parameters and setting the number of state discrete points;

Step2 Create a thread pool and set the calculation threshold;

Step3 is executed according to the serial process until the return value of the combination of state discrete points starts to be calculated, and enters into parallel calculation;

Step4 uses the Fork/Join parallel framework to divide the parent task into multiple sub-tasks in a recursive mode, and distribute them equally to each sub-thread;

Step5 The combination of state discrete points in each subtask is solved and calculated according to the recursive formula of dynamic programming until the calculation of each subtask ends;

Step6 summarizes and merges the calculation results of each subtask as a result set and returns to the main thread;

Step7 Filter out the current optimal solution from the result set, and continue to execute the method serially until the calculation ends, and destroy the thread pool.

As a further solution of the present invention: the threshold division task in step (2) is specifically that when the threshold setting is too small, it means that the scale of the sub-problems is smaller and the number of divisions is larger, which is likely to cause excessive resource management consumption; when the threshold setting is too large , which means that the scale of sub-problems is larger and the number of divisions is less, even when the number of sub-problems is smaller than the number of worker threads, it is easy to cause some worker threads to be idle. Therefore, in order to ensure that all worker threads can be assigned to sub-problems, the general threshold setting formula (I) is as follows:

In the formula (I): Take an integer for the calculation result; μ is the scale control threshold; S _c is the original problem scale; w is the number of logical threads of the multi-core processor.

As a further solution of the present invention: the task division method set in step (2) is specifically that the parent task can be divided into multiple subtasks for each task division, and the number of divided subtasks is implemented by developers writing codes.

Compared with prior art, the beneficial effect of the present invention is:

The present invention adopts the PSCWAGA, PAHPSO, PDP, PDDDP method instance test results, adopts the Fork/Join multi-core parallel framework, can give full play to the multi-core CPU parallel performance, greatly reduce the calculation time consumption, and significantly improve the calculation efficiency of the algorithm; the calculation scale of the parallel method is larger The larger the calculation time is, the more obvious the advantages of parallel computing will be; and as the calculation scale gradually increases, the speedup ratio and parallel efficiency will gradually increase, and the speedup ratio will be closer to the ideal speedup ratio.

Description of drawings

Figure 1 is a schematic diagram of the "divide and conquer" method;

Fig. 2 is a schematic diagram of the threshold control mode;

Figure 3 is a schematic diagram of the "work stealing" algorithm;

Figure 4 is a schematic diagram of Fork/Join pseudocode;

Figure 5 shows the coarse-grained parallel design pattern and method of the Fork/Join framework;

Figure 6 shows the fine-grained parallel design pattern and method of the Fork/Join framework;

Figure 7 is a topological structure diagram of the Hongshuihe cascade reservoir;

Fig. 8 is a schematic diagram of a corridor with 3 discrete state points.

detailed description

The technical solutions in the embodiments of the present invention will be clearly and completely described below in conjunction with the embodiments of the present invention. Apparently, the described embodiments are only some of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without making creative efforts belong to the protection scope of the present invention.

1. Optimal dispatching model of cascade hydropower station group

(1) Objective function

Take the maximum total power generation model of cascade reservoirs as an example. The model can be described as: under the conditions of the inflow flow of each power station in the known dispatch period, considering various constraints such as water balance, water storage, discharge, and output, and taking into account the comprehensive requirements of flood control, irrigation, and shipping, the optimal Optimizing the scheduling decision-making process to maximize the power generation of the reservoir group during the scheduling period. The mathematical expression of the objective function is as follows:

In the formula: E is the total power generation of the hydropower station group (100 million kW.h); N is the number of power stations; i is the serial number of the power station; T is the number of time periods; t is the number of time periods; is the average output of hydropower station i in period t; _Δt is the number of hours in period t.

(2) Constraints

Water balance constraints:

Reservoir water storage constraints:

Generation flow constraints:

Outbound flow constraints:

Output constraints:

End water level constraints:

The total output constraints of the hydropower system:

In the formula: is the water storage capacity of the reservoir at the beginning of period t of hydropower station i (m3); is the inflow flow of hydropower station i in period t (m3/s); is the discharge flow of hydropower station i in period t (m3/s); is the interval flow of hydropower station i in the t period (m3/s); K _i is the number of upstream power stations of hydropower station i; k is the serial number of upstream power stations; is the outflow flow of the upstream reservoir k of the hydropower station i in the period t (m3/s); is the power generation flow (m3/s) of hydropower station i in period t; is the discarded water flow (m3/s) of hydropower station i in the tth period; Respectively, the upper and lower limits of reservoir water storage capacity of hydropower station i in period t (m3); Respectively, the upper and lower limits of the power generation flow of hydropower station i in the tth period (m3/s); Respectively, the upper and lower limits of outflow flow of hydropower station i in period t (m3/s); Respectively, the upper and lower limits of output of hydropower station i in period t (MW); are the initial water storage state of hydropower station i and the water storage state at T time respectively; SB _i and SE _i are the initial water storage state specified by hydropower station i and the expected water storage state at the end of the period, respectively; Respectively, the upper and lower limits of the total output of the hydropower system in the t-th period (MW).

2. Fork/Join Parallel Framework

The interface classes and implementation classes of the Fork/Join parallel framework are encapsulated in Java.util.concurrent. Although the parallel efficiency of Fork/Join is not optimal compared with other parallel frameworks, its biggest advantage is that it provides developers with a very simple interface for implementing application programs. Developers no longer need to deal with various parallel related affairs, such as synchronization, communication, etc., and can avoid errors such as deadlock and data contention that are difficult to debug, and only need to write a few programs according to the implementation of a given interface Completing the connection between the algorithm and the framework interface greatly simplifies the trivial work of writing concurrent programs, which can greatly save the workload of developers and improve work efficiency. Fork/Join pseudo-code schematic diagram is shown in Figure 4. For developers, the application of the Fork/Join parallel framework to realize algorithm parallel computing mainly needs to pay attention to the following four issues.

1) The code class implemented by the algorithm needs to inherit the Fork/Join application interface class java.util.concurrent.RecursiveAction or java.util.concurrent.RecursiveTask.

2) Choose an appropriate threshold to divide the task. According to the example in Figure 2, the size of the threshold directly affects the number of sub-problems divided. When the threshold is set too small, it means that the sub-problems are smaller in scale and the number of divisions is larger, which can easily lead to excessive consumption of resource management; When the number of sub-problems is less than the number of worker threads, it is easy to cause some worker threads to be idle. Therefore, in order to ensure that all worker threads can be assigned to sub-problems, the general threshold setting formula is as follows:

In the formula: Take an integer for the calculation result; μ is the scale control threshold; S _c is the scale of the original problem; w is the number of logical threads of the multi-core processor (the processor with "hyper-threading" technology can simulate 2 logical threads in one core) . In addition, the framework application interface class provides a method interface for dividing sub-problems. Therefore, developers only need to provide an appropriate threshold to implement the provided interface. As for how the program implements task division and thread allocation, developers do not need to care.

3) Implement the void compute() method of the Fork/Join interface class. This method interface mainly implements the calculation of each subtask, that is, the code program of the parallelizable part of the algorithm is written into this method interface.

4) Set the task division method. Each task division can divide the parent task into multiple subtasks, and the number of divided subtasks is implemented by the developer writing code. Generally speaking, the method of decomposing the parent task in half is beneficial to the hardware to achieve load balancing.

3. Definition of important parameters of instance method

(1) Adaptive Chaotic Global Annealing Genetic Algorithm (PSCWAGA)

Logistic mapping formula: x _n+1 ＝μx _n (1-x _n ) (3.1)

J _k (f _i )＝exp(f _i /T _k ) (3.4)

In the formula: xn is a random number on [0, 1], which is the nth iteration value of variable x; μ is a control parameter, and μ∈[0,4]. Wherein when =4, the Logistic mapping formula is completely in a chaotic state, and the initial value of μ cannot be 0, 0.25, 0.5, 0.75 and 1; Pcl, Pc2, Pm1, Pm2 are the control on the interval (0, 1) Parameters; f' is the larger fitness value of the two crossover individuals; f is the fitness of the current individual; fmax and favg respectively represent the maximum fitness and the average fitness of the population; P(Xi) is the selection probability, Jk( fi) is the fitness function; fi is the objective function value of individual Xi; m is the population size; k is the number of iterations of the genetic algorithm; Tk is the annealing temperature tending to zero. Wherein, the temperature decreases according to Tk=1/ln(k/T0+1).

(2) Adaptive Hybrid Particle Swarm Optimization (PAHPSO)

particle energy

in

In the formula: Pibest is the historical optimal position of particle xi; Pgbest is the global optimal position of the population; n is the dimension; Xi(k) is the particle position; Vi(k) is the particle flight speed. It can be seen that e(P _i )∈[0,1]. Particle energy describes the search ability of particles and plays a key role in algorithm adaptation. In the formula (3.6), it can be seen that the particle energy calculation is related to the similarity of the particle's current position and velocity, as well as the similarity of the particle's historical optimal position and the population's global optimal position.

particle energy threshold

Where: speed(P _i (curG))=P _ibest (curG)/P _ibest (curG-1)

In the formula: maxG is the maximum number of iterations; curG is the current number of iterations; e is a predetermined constant used to control the change trend of the energy threshold; eIni is the upper limit of particle energy; eFin is the lower limit of particle energy.

The particle energy threshold is closely related to the degree and speed of population evolution. It can be seen from the formula (3.5) that the particle energy threshold is related to the optimal position of the particle and the upper and lower limits of the particle energy. The particle energy threshold is constantly changing during the iterative process. When the particle energy is less than the current particle energy threshold, the velocity and position are mutated, see formulas (3.8) and (3.9).

V _i (k) = mutation (V _i (k)) (3.8)

X _i (k) = mutation (X _i (k)) (3.9)

particle similarity

in

In the formula: Pibest is the historical optimal position of particle xi; Pjbest is the historical optimal position of particle xj. It can be seen from the formula (3.10) that the calculation of the similarity of adjacent particles is related to its corresponding historical optimal position.

Particle Similarity Threshold

In the formula: sIni is the upper limit of particle similarity; sFin is the lower limit of particle similarity; s is a constant, which controls the variation range of the similarity threshold.

(3) Dynamic programming method (DP)

S _t =T _t+1 (S _t+1 , Q _t , N _t ); t=T, T-1, . . . , 1 (3.13)

In the formula: t and T are the serial number and number of time periods respectively; St, Qt and Nt are the storage capacity, inflow flow and output of hydropower stations in M dimension (the number of power stations), all of which are vectors; f _t ^* (S _t ) is the time period When the t state is St, the maximum power generation of the system from period t to the end period is 100 million kWh; Bt(St, Qt, Nt) is when the initial water storage state is St in period t, the inflow flow is Qt, and the decision-making output is Nt The power generation of the system in this period is 100 million kWh; Tt+1(St+1, Qt, Nt) is the state transition equation from t+1 to t, usually a water balance equation, see formula (1.2).

(4) Discrete Differential Dynamic Programming (DDDP)

Corridor: When each iterative search starts, a certain range of "corridors" is constructed for the current initial solution within the state feasible region, and the optimal trajectory is searched in the current "corridor". In the corridor, there are generally less discrete states Number, usually discrete 3 state points, can greatly reduce the calculation scale, see Figure 8. In Fig. 8, Δ ₁ and Δ ₂ are the width of the upper corridor and the width of the lower corridor respectively, and the width of the entire corridor is Δ=Δ ₁ +Δ ₂ . For the convenience of calculation, Δ ₁ = Δ ₂ can be set. In addition, the upper boundary and lower boundary of the corridor cannot exceed the feasible region of the state variable.

4. Parallel design and implementation of typical intelligent methods in coarse-grained mode

For many emerging intelligent algorithms, the solution process of different optimization algorithms is different. For example, the main process of genetic algorithm is to optimize through steps such as population individual selection, crossover, and mutation; The global extreme point continuously updates the individual position to search for the global optimal solution; the main process of the ant colony algorithm continuously evolves to the global optimal solution through the pheromone left by the individual. However, the optimization mechanism of these intelligent algorithms is generally to gradually search from the individual optimum to the global optimum. Their common feature is that when the algorithm starts to execute, a certain-scale individual population is initially generated, and each individual in the population is a single independent initial solution, and the iterative calculation of each individual in the optimization process is independent of each other, therefore, the coarse-grained mode of decomposing the initial population into smaller populations can be used for parallel design and calculation. The present invention mainly takes the parallelized design of two typical intelligent methods of parallel adaptive chaotic global annealing genetic algorithm and parallel adaptive mixed particle swarm algorithm as examples, and summarizes the coarse-grained parallelized design method based on the Fork/Join multi-core parallel framework.

(1) Parallel adaptive chaotic global annealing genetic algorithm (PSCWAGA)

Step 1 parameter initialization. Set the population size m, the number of chaotic sequences d, the maximum iteration number Kmax of the population, the initial temperature T0 and the adaptive parameters Pc1, Pc2, Pm1, Pm2.

Step 2 population initialization. According to the Logistic mapping formula, n groups of chaotic sequences are randomly generated in the chaotic space, which are mapped to the solution space to generate m different individuals to form a population.

Step 3 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join.

Step 4 starts the parallel computing process.

Parallel Step① divides the parent population into multiple smaller sub-populations according to the recursive mode according to the set calculation threshold.

The subpopulation sets divided by Parallel Step② are evenly distributed to different logical threads. To keep the CPU load balanced, make sure each logical thread is assigned the same number of subtasks.

Parallel Step③ The subpopulation assigned to each thread runs calculations independently, and the main calculation steps are as follows:

(1) Evaluate individual fitness. Directly use the objective function as the fitness evaluation function, and adopt the optimal preservation strategy at the same time, that is, record the best individual of each generation, do not participate in the crossover operation and mutation operation, and replace the individual with the worst fitness after the calculation of this generation is completed to ensure It passed smoothly into the next generation.

(2) Select operation. The overall annealing selection mechanism is adopted to allow the parents to participate in the competition, and each individual selects the next generation through the relative fitness function formula (5) and the selection probability formula (6).

(3) Cross operation. The arithmetic crossover method is used to perform the crossover operation, and the crossover operator is obtained by formula (2).

(4) Variation operation. The non-uniform mutation method is used to perform the mutation operation, and the mutation operator is obtained from the formula (3).

(5) Calculate the individual fitness of the parent and offspring. Assuming that parent individual Xi generates offspring X′ _i through crossover and mutation, if f(X′ _i )>f(X _i ), replace Xi with X′ _i ; otherwise, use probability exp[(f(X′ _i )-f(X _i ))/T _k ] retain Xi.

(6) Parameter update. The number of iterations k=k+1, the temperature Tk=1/ln(k/T0+1).

(7) Determine whether the subpopulation iteration is over. According to the annealing temperature Tk or the maximum number of iterations as the convergence condition. When any one of the two reaches the initially set convergence condition, return (1); otherwise, the convergence of the subpopulation calculation ends.

Parallel Step④ summarizes and merges the optimized solutions of each subpopulation as a result set and returns to the main thread.

Step 5 Filter out the optimal solution from the result set, and the calculation is completed and the thread pool is destroyed.

The flow chart of PSCWAGA algorithm is shown in Figure 5.

(2) Parallel Adaptive Hybrid Particle Swarm Optimization (PAHPSO)

Step1 parameter initialization. Set the population size m, the number of chaotic sequences d, the maximum number of population iterations Kmax, flight acceleration c1, c2, inertia factor w, constant e, constant s, particle energy upper limit eIni, particle energy lower limit eFin and particle similarity upper limit sIni and The lower limit of particle similarity sFin.

Step2 population initialization. According to the Logistic mapping formula, the individual positions (zi1, zi2, ..., zin) and particle flight speeds (Vi1, Vi2, ..., Vin) of the particle population are randomly initialized within the allowable range of the water level in each time period. Among them, the particle position element is the water level, and the flight speed element is the water level fluctuation speed.

Step3 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join.

Step4 starts the parallel computing process.

Parallel Step① divides the parent population into multiple smaller sub-populations according to the recursive mode according to the set calculation threshold.

The subpopulation sets divided by Parallel Step② are evenly distributed to different logical threads. To keep the CPU load balanced, make sure each logical thread is assigned the same number of subtasks.

Parallel Step③ The subpopulation assigned to each thread runs calculations independently, and the main calculation steps are as follows:

(1) Calculate particle fitness, particle individual optimal solution and population global optimal solution. The particle fitness is compared with its individual optimal solution, if the particle fitness is better than its individual optimal solution, the current particle position is taken as the individual optimal position; the particle fitness is compared with the global optimal solution of the population, if the particle fitness is better than the population If the global optimal solution is better, the current particle position is taken as the global optimal position of the population.

(2) Calculate particle energy and particle energy threshold. If the particle energy is lower than the current particle energy threshold, perform a mutation operation on the particle's current position and velocity.

(3) Calculate particle similarity and particle similarity threshold. If the similarity between two adjacent particles is less than the current particle similarity threshold, the mutation operation is performed on the historical optimal position of the worse particle.

(4) A neighborhood-based greedy random search strategy is introduced to update the individual optimal position of particles. If the current position searched in the neighborhood is greater than the fitness of the particle before the search, replace the individual particle position before the search, and then compare the individual particle position after the search with the optimal position of the particle history and the global optimal position of the population to update the particle The historical optimal position and the population optimal position.

(5) Update the velocity and position of the particle population.

(6) Determine whether the subpopulation iteration is over. If the current number of iterations is less than the maximum number of iterations, return (1); otherwise, the convergence of the subpopulation calculation ends.

Parallel Step④ summarizes and merges the calculation results of each subpopulation as a result set and returns to the main thread.

Step5 filters out the optimal solution from the result set, and the calculation is completed and the thread pool is destroyed.

The flow chart of PAHPSO algorithm is shown in Fig. 5.

(3) Coarse-grained parallel design pattern and method of Fork/Join framework

According to the calculation process of PSCWAGA and PAHPSO methods, the coarse-grained parallel design mode and method of the Fork/Join framework are summarized:

Step1 initialize algorithm parameters and population size.

Step2 Create a thread pool and set the calculation threshold.

Step3 uses the Fork/Join parallel framework to divide the parent population into multiple sub-populations in a recursive mode, and distribute them equally to each child thread.

Step4 Each sub-population is optimized and calculated according to the original serial method flow until the iteration of each sub-population ends.

Step5 summarizes and merges the calculation results of each subpopulation as a result set and returns to the main thread.

Step6 Filter out the optimal solution from the result set, and destroy the thread pool after the calculation is completed.

The coarse-grained parallel design pattern of the Fork/Join framework is shown in Figure 5.

5. Parallel design implementation of typical dynamic programming method in fine-grained mode

Classical dynamic programming methods are currently one of the most widely used optimization methods for optimal scheduling of reservoir groups, mainly including traditional dynamic programming methods, discrete differential dynamic programming methods, successive approximation dynamic programming methods and other dynamic programming methods. This type of dynamic programming method has different optimization iteration methods, but the core of the method is the solution optimization of different state discrete point combinations in the dynamic programming recursive formula, and the different state discrete point combination iterative calculations are independent of each other. . Therefore, classical dynamic programming methods are suitable for parallel design in fine-grained mode. The present invention mainly takes the parallel design of two typical dynamic programming methods, the parallel dynamic programming method and the parallel discrete differential dynamic programming method, as examples, and summarizes the fine-grained parallel design method based on the Fork/Join multi-core parallel framework.

(1) Parallel dynamic programming method (PDP)

Step1 data preparation. Obtain the characteristic values and characteristic curves of the basic properties of the power station required for calculation, including the characteristic water level of the power station, output coefficient, water level-storage capacity curve, discharge-tail water level curve, etc., and determine the discrete The state variable St.

Step2 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join.

Step3 starts the parallel computing process.

Parallel Step① Construct the parent task of parallel computing. The solution calculation of all water storage state variables combined in Bt(S t, It, Nt) in the iterative cycle is taken as the parent task, and storage space is created for indicators such as water level, output, and power generation during the calculation process.

Parallel Step② divides the parent task into multiple smaller subtasks in a recursive mode according to the set calculation threshold.

The set of subtasks divided by Parallel Step③ is evenly distributed to different logical threads. To keep the CPU load balanced, make sure each logical thread is assigned the same number of subtasks.

Parallel Step④ The subtasks assigned to each thread run calculations independently, that is, all the discrete combinations of states in the subtasks are solved and calculated in the recursive formula.

Parallel Step ⑤ Summarize and merge the calculation results of each subtask as a result set and return to the main thread.

Step4 filters out the optimal solution from the result set, and the calculation is completed and the thread pool is destroyed.

The PDP algorithm flow chart is shown in Figure 6.

(2) Parallel discrete differential dynamic programming method (PDDDP)

Step1 data preparation. Obtain the characteristic values and characteristic curves of the basic properties of the power station required for calculation, including the characteristic water level of the power station, output coefficient, water level-storage capacity curve, discharge-tail water level curve, etc., and determine the discrete State variable St (the discrete number of states of the DDDP method is generally selected as 3).

Step2 sets the number of iterative corridors, and generates an initial feasible solution as the initial trajectory for calculation.

Step3 Create a thread pool. The number of working threads in the default generated thread pool is the same as the number of CPU logical threads, and set the calculation threshold of Fork/Join.

Step4 selects the maximum corridor width as the current corridor.

Step5 starts the parallel computing process.

Parallel Step①Construct the parent task of parallel computing in the current corridor. Combine all storage state variables in the corridor in Bt(St, It, Nt) to solve the calculation as the parent task, and create storage space for indicators such as water level, output, and power generation during the calculation process.

Parallel Step② divides the parent task into multiple smaller subtasks in a recursive mode according to the set calculation threshold.

The set of subtasks divided by Parallel Step③ is evenly distributed to different logical threads. To keep the CPU load balanced, make sure each logical thread is assigned the same number of subtasks.

Parallel Step④ The subtasks assigned to each thread run calculations independently, that is, all the discrete combinations of states in the subtasks are solved and calculated in the recursive formula.

Parallel Step ⑤ Summarize and merge the calculation results of each subtask as a result set and return to the main thread.

Step 5 Output the current optimal trajectory according to the result set, and judge whether the current optimal trajectory is the same as the initial trajectory. If they are the same, go to Step 6; if not, go to Step 7.

Step 6 judges whether the current corridor is the last corridor. If not, set the next smaller corridor width as the current corridor width, and enter Step 7; if so, the calculation is terminated, and the optimal trajectory is output as the optimal solution for calculation and the thread pool is destroyed.

Step 7 sets the current optimal trajectory as the initial trajectory for the next iteration, and returns to Step 5.

The flow chart of PDDDP algorithm is shown in Figure 6.

(3) Fork/Join framework fine-grained parallel design pattern and method

According to the calculation process of PDP and PDDDP method, the fine-grained parallel design mode and method of Fork/Join framework are summarized:

Step1 data preparation. Including initialization parameters and setting the number of state discrete points.

Step2 Create a thread pool and set the calculation threshold.

Step3 is executed in a serial process until the return value of the combination of state discrete points is calculated, and then parallel calculation is entered.

Step4 uses the Fork/Join parallel framework to divide the parent task into multiple sub-tasks in a recursive mode, and distribute them equally to each sub-thread.

Step5 The combination of state discrete points in each subtask is solved and calculated according to the recursive formula of dynamic programming until the calculation of each subtask ends.

Step6 summarizes and merges the calculation results of each subtask as a result set and returns to the main thread.

Step7 Filter out the current optimal solution from the result set, and continue to execute the method serially until the calculation ends, and destroy the thread pool.

The fine-grained parallel design pattern of the Fork/Join framework is shown in Figure 6.

(1) Basic information

In order to verify the parallel efficiency of PSCWAGA, PAHPSO, PDP, and PDDDP methods, the model of the maximum annual power generation of cascade reservoirs (see "Specific Implementation") is used as a calculation example, and according to the optimization characteristics of each method, different dispatching objects (participating Optimized reservoir group) for testing, and the scheduling object used for the test is the Hongshui River cascade reservoir group. See Figure 7 for the topological structure of the reservoir group. The CPU configuration of the computer used for the test is Intel Xeon E31245@3.30GHz (4 cores), and the test status is "hyperthreading" off.

(2) Parallel performance index

Speedup ratio Sp and efficiency Ep are two commonly used indicators to measure the performance of parallel algorithms, and their mathematical expressions are as follows:

S _p =T ₁ /T _p (1)

E _p =S _p /p (2)

In the formula: T1 represents the execution time of the algorithm in the serial environment, s; Tp represents the execution time of the algorithm in the environment of p kernels, s.

(3) Test plan

①PSCWAGA method

The reservoirs participating in the optimization are Lubuge, Yunpeng, Tianshengqiao No. 1, Guangzhao, Longtan and Yantan 6 seasonal regulation and above power stations, and set up three groups of schemes with different population sizes for simulation tests. See Table 1 for the population size setting of each scheme.

Table 1 Population size of the three groups of simulation schemes of PSCWAGA algorithm

②PAHPSO method

The reservoirs participating in the optimization are four seasonal regulation and above power stations of Tianshengqiao, Guangzhao, Longtan and Yantan, and set up three groups of schemes with different population sizes for simulation tests. See Table 2 for the population size setting of each scheme.

Table 2 Population size of three groups of simulation schemes of PAHPSO algorithm

③PDP method

The reservoirs participating in the optimization are Longtan and Yantan 2 seasonal regulation and above power stations, and three sets of schemes with different numbers of discrete points are set up for simulation testing. The number of discrete points for each scheme is set in Table 3.

Table 3 Number of discrete points of the three groups of simulation schemes of PDP algorithm

④ PDDDP method

The reservoirs participating in the optimization are Tianyi, Longtan and Yantan 3 seasonal regulation and above power stations, and three groups of different scheduling cycles (calculation scales) are set up for simulation testing. See Table 4 for the scheduling period settings of each scheme.

Table 4 Number of discrete points of the three groups of simulation schemes of PDDDP algorithm

(4) Parallel results of each program

①PSCWAGA method

The test results of the PSCWAGA method are shown in Table 5. The minimum time consumption of the three schemes appears in the 4-core environment, which are 582s, 881s and 1173s respectively, which is 1583s, 2425s and 3355s shorter than the serial time, and the maximum speedup ratio reaches 3.72, 3.75 and 3.86, give full play to the acceleration performance of multi-core CPU, and significantly improve the calculation efficiency of the algorithm.

Table 5 Comparison of serial and parallel results in different multi-core environments for each simulation scheme of the PSCWAGA method

②PAHPSO method

The test results of the PAHPSO method are shown in Table 6. The minimum time consumption of the three schemes appears in the 4-core environment, which are 139.7s, 263.9s and 382.7s respectively, which are 363.4s, 723.5s and 1075.9s shorter than the serial time, and the maximum acceleration The ratios reached 3.60, 3.74 and 3.81 respectively, giving full play to the acceleration performance of the multi-core CPU and significantly improving the computational efficiency of the algorithm.

Table 6 Comparison of serial-parallel results in different multi-core environments for each simulation scheme of the PAHPSO method

③PDP method

The test results of the PDP method are shown in Table 7. The minimum time consumption of the three schemes appears in the 4-core environment, which are 25.1s, 91.5s, and 187.5s, which are 64.1s, 251.7s, and 532.1s shorter than the serial time, and the maximum acceleration The ratios reached 3.56, 3.75 and 3.84 respectively, giving full play to the acceleration performance of the multi-core CPU and significantly improving the computational efficiency of the algorithm.

Table 7 Comparison of serial and parallel results in different multi-core environments for each simulation scheme of the PDP method

④ PDDDP method

The test results of the PDDDP method are shown in Table 8. The minimum time consumption of the three schemes appears in the 4-core environment, which are 15.1s, 362.3s, and 928.4s, which are 6.7s, 258.0s, and 669.7s shorter than the serial time, and the maximum acceleration The ratios reached 1.80, 3.48, and 3.59 respectively, giving full play to the acceleration performance of the multi-core CPU and significantly improving the computational efficiency of the algorithm.

Table 8 Comparison of serial and parallel results in different multi-core environments for each simulation scheme of the PDDDP method

(5) Summary

1) Through the PSCWAGA, PAHPSO, PDP, PDDDP method instance test results, using the Fork/Join multi-core parallel framework, can give full play to the multi-core CPU parallel performance, greatly reduce the calculation time consumption, and significantly improve the calculation efficiency of the algorithm.

2) The larger the calculation scale of the parallel method, the more time-consuming the calculation will be reduced, and the advantages of parallel computing will be more obvious; and as the calculation scale gradually increases, the speedup ratio and parallel efficiency will gradually increase, and the speedup ratio will be closer to the ideal speedup ratio.

It will be apparent to those skilled in the art that the invention is not limited to the details of the above-described exemplary embodiments, but that the invention can be embodied in other specific forms without departing from the spirit or essential characteristics of the invention. Accordingly, the embodiments should be regarded in all points of view as exemplary and not restrictive, the scope of the invention being defined by the appended claims rather than the foregoing description, and it is therefore intended that the scope of the invention be defined by the appended claims rather than by the foregoing description. All changes within the meaning and range of equivalents of the elements are embraced in the present invention.

In addition, it should be understood that although this specification is described according to implementation modes, not each implementation mode only includes an independent technical solution, and this description in the specification is only for clarity, and those skilled in the art should take the specification as a whole , the technical solutions in the various embodiments can also be properly combined to form other implementations that can be understood by those skilled in the art.

Claims (3)

1. a kind of Cascade Reservoirs Optimized Operation multi-core parallel concurrent based on Fork/Join frameworks calculates design method, its feature exists In comprising the following steps：

(1) the parallel frameworks of Fork/Join are built：The core of the parallel frameworks of Fork/Join inherits the characteristic of " divide and conquer ", passes through Recursive subdivision original problem, formed several scales it is smaller, separate and can parallel computation subproblem；When each subproblem is carried out After independent parallel is calculated, the sub- result for combining each subproblem is the final result of exportable former problem；Fork/Join Frame Designs Unique Thread Pool Technology, when program starts to perform, acquiescence is created and available processor the same number of active threads Number；In " divide and conquer " implementation procedure, the threshold value of the control that can freely set a subproblem scale is defined as son When the higher limit of problem scale, i.e. group problem scale are less than or equal to threshold value, " divide and conquer ", which is performed, to be terminated, and each subproblem is put down It is assigned in different threads and starts parallel computation；In addition, during subproblem parallel computation, Fork/Join is devised solely Special deque sequencing model, and employ " work is stolen " algorithm, i.e., when the queue calculating task of a thread is space-time, Calculating task " will be stolen " from other in running order thread queue afterbodys；

(2) the parallel frameworks of Fork/Join are realized：1) code word that algorithm is realized need to inherit Fork/Join application interface classes Java.util.concurrent.RecursiveAction or java.util.concurrent.RecursiveTask；2) Threshold value is selected to divide task；3) void compute () method of Fork/Join interface classes is realized；4) task division side is set Formula；

(3) typical intelligent method paralell design under coarseness pattern：1) parallel adaptive chaos overall annealing genetic algorithm：

The parameter initializations of Step 1.Set population scale m, chaos sequence number d, population maximum iteration Kmax, initial temperature Spend T0 and auto-adaptive parameter Pc1, Pc2, Pm1, Pm2；

The initialization of population of Step 2.According to Logistic mapping equations, n group chaos sequences are generated at random in chaotic space, are mapped The different individuals of m are generated in solution space and constitute populations, population at individual by each power station different periods water level value (zi1, Zi2 ..., zin) constitute；

Step 3 creates thread pool, and the worker thread number for giving tacit consent to the thread pool of generation is identical with cpu logic number of threads, simultaneously Fork/Join calculating threshold value is set；

Step 4 starts parallel computation flow；

1. father population is divided into the smaller son of multiple scales by Parallel Step according to the calculating threshold value of setting by recursive schema Population；

The sub- population set that 2. Parallel Step divide is evenly distributed to Different Logic thread.In order to keep cpu load to put down Weighing apparatus, it is ensured that the subtask number of each logic thread distribution is identical；

The Parallel Step population independent operatings that 3. each thread is assigned to are calculated, and main calculation procedure is as follows：

A evaluates individual adaptation degree；

B Selecting operations：Using integrally annealed selection mechanism, it is allowed to which parent participates in competition, and filters out individual of future generation；

C crossing operations：Crossover operation is performed using arithmetic crossover method；

D mutation operators：Mutation operation is performed using non-uniform mutation mode；

E calculates parent and offspring individual fitness：When parent individuality Xi is by the generation filial generation X ' that intersects, makes a variation_iIf, f (X '_i) ＞ f (X_i), then with X '_iInstead of Xi；Otherwise, with probability exp [(f (X '_i)-f(X_i))/T_k] retain Xi；

F parameters update.Iterations k=k+1, temperature Tk=1/ln (k/T0+1).

G judges whether sub- population iteration terminates；According to annealing temperature Tk or maximum iteration as the condition of convergence, when both appoint When meaning one reaches the condition of convergence of initial setting up, A is returned；Otherwise, sub- population calculates convergence and terminated；

4. Parallel Step, which collect, merges the optimization solution of each sub- population and collects as a result, returns to main thread.

Step 5 filters out optimal solution from result set, calculates and terminates and destroying threads pond.

2) parallel adaptive Hybrid Particle Swarm (PAHPSO)

Step1 parameter initializations；

Step2 initialization of population；

Step3 creates thread pool, and the worker thread number for giving tacit consent to the thread pool of generation is identical with cpu logic number of threads, simultaneously Fork/Join calculating threshold value is set；

Step4 starts parallel computation flow；

1. father population is divided into the smaller son of multiple scales by Parallel Step according to the calculating threshold value of setting by recursive schema Population；

The sub- population set that 2. Parallel Step divide is evenly distributed to Different Logic thread.In order to keep cpu load to put down Weighing apparatus, it is ensured that the subtask number of each logic thread distribution is identical；

The Parallel Step population independent operatings that 3. each thread is assigned to are calculated, and main calculation procedure is as follows：

A calculates particle fitness, particle individual optimal solution and population globally optimal solution；Particle fitness and its individual optimal solution Compare, if particle fitness is more excellent than its individual optimal solution, current particle position is used as personal best particle；Particle fitness Compared with population globally optimal solution, if particle fitness is more excellent than population globally optimal solution, current particle position is used as population Global optimum position；

B calculates particle energy and particle energy threshold value；If particle energy is less than current particle energy threshold, to particle present bit Put and perform mutation operation with speed；

C calculates particle similarity and particle similarity threshold；If two adjacent particles similarities are less than current particle similarity threshold Value, then perform mutation operation to the history optimal location of poor particle；

D introduces the greedy random searching strategy based on neighborhood and the personal best particle of particle is updated；If in neighborhood search The current location arrived is bigger than searching for preceding particle fitness, then instead of particle body position before search, then individual with particle after search Body position is made comparisons with particle history optimal location and population global optimum position, more new particle history optimal location and kind Group's optimal location；

E updates speed and the position of particle populations；

F judges whether sub- population iteration terminates；If current iteration number of times is less than maximum iteration, return (1)；Otherwise, sub- kind Group calculates convergence and terminated；

4. Parallel Step, which collect, merges the result of calculation of each sub- population and collects as a result, returns to main thread；

Step5 filters out optimal solution from result set, calculates and terminates and destroying threads pond；

3) Fork/Join frameworks coarse grain parallelism design pattern and method

According to PSCWAGA and PAHPSO method calculation process, induction and conclusion Fork/Join frameworks coarse grain parallelism design pattern and Method：

Step1 initialization algorithms parameter and population scale；

Step2, which creates thread pool and set, calculates threshold value；

Father's population dividing is many sub- populations by recursive schema using the parallel frameworks of Fork/Join by Step3, and is evenly distributed to Each sub-line journey；

Each sub- populations of Step4 press former serial approach process optimization and calculated, until each sub- population iteration terminates；

Step5, which collects, to be merged the result of calculation of each sub- population and collects as a result, returns to main thread；

Step6 filters out optimal solution from result set, calculates and terminates and destroying threads pond；

(4) exemplary dynamic planing method paralell design under fine granularity pattern：1) parallel dynamic programming method：

Step1 data prepare；Obtain the power station primary attribute characteristic value and indicatrix needed for calculating, including power station feature water Position, power factor, water level-storage-capacity curve, aerial drainage-tailwater level curve etc., and according to reservoir day part retaining bound, discrete Number determines discrete state variable St；

Step2 creates thread pool, and the worker thread number for giving tacit consent to the thread pool of generation is identical with cpu logic number of threads, simultaneously Fork/Join calculating threshold value is set；

Step3 starts parallel computation flow；

1. Parallel Step build father's task of parallel computation；By all retaining state variable combinations in iteration cycle in Bt Solution in (St, It, Nt) is calculated as father's task, and for water level in calculating process, exert oneself, the index such as generated energy creates storage Space；

2. father's task is divided into the smaller son of multiple scales by Parallel Step according to the calculating threshold value of setting by recursive schema Task；

The subtask ensemble average that 3. Parallel Step divide is assigned to Different Logic thread.In order to keep cpu load to put down Weighing apparatus, it is ensured that the subtask number of each logic thread distribution is identical；

The Parallel Step subtask independent operatings that 4. each thread is assigned to are calculated, i.e., the institute in subtask it is stateful from Dissipate combination and calculating is solved in recurrence formula；

5. Parallel Step, which collect, merges the result of calculation of each subtask and collects as a result, returns to main thread；

Step4 filters out optimal solution from result set, calculates and terminates and destroying threads pond；

2) parallel discrete differential dynamic programming method：

Step1 data prepare；Obtain the power station primary attribute characteristic value and indicatrix needed for calculating, including power station feature water Position, power factor, water level-storage-capacity curve, aerial drainage-tailwater level curve etc., and according to reservoir day part retaining bound, discrete Number determines discrete state variable St；

Step2 sets iteration gallery number, and generates initial feasible solution as calculating initial track；

Step3 creates thread pool, and the worker thread number for giving tacit consent to the thread pool of generation is identical with cpu logic number of threads, simultaneously Fork/Join calculating threshold value is set；

Step4 chooses maximum width of corridor and is used as current gallery；

Step5 starts parallel computation flow；

1. Parallel Step build father's task of parallel computation in current gallery；By all retaining state variables in gallery Solution in Bt (St, It, Nt) is combined to calculate as father's task, and for water level in calculating process, exert oneself, the index such as generated energy Create memory space；

2. father's task is divided into the smaller son of multiple scales by Parallel Step according to the calculating threshold value of setting by recursive schema Task；

The subtask ensemble average that 3. Parallel Step divide is assigned to Different Logic thread；In order to keep cpu load to put down Weighing apparatus, it is ensured that the subtask number of each logic thread distribution is identical；

The Parallel Step subtask independent operatings that 4. each thread is assigned to are calculated, i.e., the institute in subtask it is stateful from Dissipate combination and calculating is solved in recurrence formula；

5. Parallel Step, which collect, merges the result of calculation of each subtask and collects as a result, returns to main thread；

Step 5 exports current optimal trajectory according to result set, and judges whether current optimal trajectory is identical with initial track；If It is identical, then into Step 6；If differing, into Step 7；

Step 6 judges whether current gallery is last gallery；If it is not, setting next smaller width of corridor conduct Current width of corridor, into Step 7；Terminated if so, calculating, output optimal trajectory is used as calculating optimal solution and destroying threads pond；

Step 7 sets current optimal trajectory as the initial track of next iteration, returns to Step 5；

3) Fork/Join frameworks fine grained parallel design pattern and method：

According to PDP and PDDDP method calculation process, induction and conclusion Fork/Join frameworks fine grained parallel design pattern and method：

Step1 data prepare.Counted including initiation parameter and setting state discrete；

Step2, which creates thread pool and set, calculates threshold value；

Step3 is performed by serial flow until starting to calculate the return value of state discrete point combination, into parallel computation；

Father's task is divided into multiple subtasks by Step4 using the parallel frameworks of Fork/Join by recursive schema, and is evenly distributed to Each sub-line journey；

Dynamic Programming recurrence formula derivation is pressed in state discrete point combination in each subtasks of Step5, until each subtask meter Terminate；

Step6, which collects, to be merged the result of calculation of each subtask and collects as a result, returns to main thread；

Step7 filters out current optimal solution from result set, and continues to perform by the serial flow of method until calculating terminates, and sells Ruin thread pool.

Set 2. the Cascade Reservoirs Optimized Operation multi-core parallel concurrent according to claim 1 based on Fork/Join frameworks is calculated Meter method, it is characterised in that it is specially when threshold value sets less than normal that threshold value, which divides task, in step (2), it is meant that the rule of subproblem Mould is smaller and dividing number is more, easily causes resource management consumption excessive；When threshold value sets bigger than normal, it is meant that the scale of subproblem Bigger and dividing number is less, or even group problematic amount is when being less than active line number of passes, is easily caused part worker thread and is in the spare time Configuration state.Therefore, in order to ensure that all working thread can be assigned to subproblem, general threshold value sets public formula (I) as follows：

In public formula (I)：Upper integer is taken for result of calculation；μ is scale domination threshold value；S_cFor former problem scale；W is multinuclear processing Device logic line number of passes.

Set 3. the Cascade Reservoirs Optimized Operation multi-core parallel concurrent according to claim 1 based on Fork/Join frameworks is calculated Meter method, it is characterised in that setting task dividing mode is specially and divides that father's task can be divided into per subtask in step (2) Multiple subtasks, and the subtask number divided is write code by developer and realized.