An Optimal Scheduling Method for Numerical Weather Model Assimilation with Dense Observations

In this paper, the scheduling problem of dense observation data in a numerical weather model assimilation system is studied and an algorithm of "deal-reveal" is proposed. The algorithm identifies the area where all dense observation stations are located, and then obtains a certain number of grid point on which the value represents the stations quantity overlaid on it. The algorithm selects the stations with maximum value corresponding to the dense observation data iteratively and make the amount of each batch of dense observation stations as more as possible to reduce the batch number, enhances the overall performance of the system finally.


Introduction
In recent decades, there has been a great improvement in weather forecasting. The calculation of modern meteorological numerical prediction is usually completed by high-performance computer platform, which involves many disciplines, such as atmospheric science, computational mathematics, highperformance computer structure system, etc. [1]. And Data assimilation is one of the key techniques to improve the effectiveness of numerical weather prediction. Since Panofsky [2] put forward the differential polynomial method in 1949, the objective analysis method of data assimilation has been greatly developed. Current meteorological applications are usually built on high-performance computer platforms. So parallel computing technology is an important part of them. In a numerical weather model assimilation system, the parallel processing of dense observations is a key factor in determining system performance. The fundamental problem discussed in this paper is to use an appropriate scheduling strategy to complete the scheduling of dense observation data in the shortest time.
Scheduling problem refers to the process of allocating shared resources and scheduling production tasks within a certain period of time [3]. Scheduling problems involve various fields, such as mathematics, operations research and so on. Scientists have studied and solved many important scheduling and optimization problems by using the planning and analysis methods in various fields. Generally speaking, people regard the study of scheduling by Conway, Maxwell and Miller [4] as the beginning of the study of scheduling theory, on the basis of which the study of scheduling theory has made greater progress. Later, the study of scheduling complexity begins to enter people's horizon, and scientists find that the essence of various scheduling problems is NP hard problem [5].
In scheduling problems, resources are usually referred to as machines and tasks as artifacts. Tasks that need to be completed can be called artifacts, while machines are objects that provide processing, which are resources needed to complete tasks [6]. Among all scheduling problems, the workshop scheduling problem is one of the most classic scheduling problems. From the first issue of flow workshop published by Johnson [7] to the open workshop model proposed by Gonzalea & Sahni [8], people's research on the workshop scheduling problem has become more and more in-depth. Parallel machine scheduling problem is another branch of the scheduling problem, and it is also an important research area. Parallel machine scheduling is the study of task allocation to parallel machines and task ordering on parallel machines [9]. Research on parallel scheduling problem originated from the 1950s. After Mcnaughton [10] and Hu [11] published their research on the problems related to parallel scheduling, the parallel scheduling problem gradually came into people's field of vision.
The typical scheduling problem of parallel multi-machine is the scheduling problem of parallel multimachine with the minimum completion time. For the small-scale scheduling problem of parallel multimachine with a minimum completion time, heuristic algorithm is usually used to solve it [12]. However, it is usually a NP hard problem for the large-scale scheduling problem of parallel multi-machine with minimum completion time, and an effective scheduling strategy is needed in order to solve the problem. At present, intelligent optimization algorithms such as genetic algorithms are usually used to solve this kind of algorithm, but in practice, a new method is needed to solve the scheduling problem of parallel multi-machine with minimum completion time under special constraints.
Scheduling of dense observations is an important part of the parallel processing of a numerical weather model assimilation system. The essence of this scheduling problem is to minimize the completion time of a parallel multi-machine scheduling problem with special constraints. In this paper, the algorithm of "deal-reveal" is proposed to solve the scheduling problem of parallel multi-machine with minimum completion time under this special constraint.

Problem Description
Dense observation data refers to the observation data collected by actual observation sites that are densely distributed and unevenly distributed in a certain area. Consider N dense observation data assimilation system allocated to M is calculated in the parallel machine, each machine at the same time only for calculation, a dense observation data for each dense observation data can be calculated on any machine, processing time of each dense observation data consistent and calculate it only once, every batch of dense observations must be assigned to a machine to compute each other. In this assimilation system, the influence of dense observations is a rectangular area centered on the frank observation site. The calculation of the same batch of dense observation data needs to be independent of each other for the maximum efficiency of parallel machines. If there is conflict in the influence area of the same batch of dense observation data, the conflict observation data will be transferred to serial processing. The calculation of the next batch of observations cannot be conducted until all the current batch of dense observations have been calculated.
The distribution of dense observation data is dense and unbalanced. Each batch of dense observation data allocated to parallel machine calculation needs to be independent of each other, so the number of dense observation data that can be simultaneously calculated in parallel is bound to decrease. From this, important constraints of computing performance can be obtained, one is the number of parallel machines. The second is the number of batches calculated. The hardware limits the number of parallel machines and there is an upper limit to the number of each batch of mutually independent dense observation data. Therefore, when the number of parallel machines reaches this upper limit, the restriction condition is to calculate the number of batches. The number of calculated batches depends on the designed scheduling strategy. That is, the selection of dense observation data calculated for each batch. Therefore, the scheduling strategy has a significant impact on the performance of the system. The better the scheduling strategy, the higher the parallelism of the system in the calculation of dense observation data.
On the least finish time is parallel machine scheduling problem, the more "artifact" is a dense observation data, special constraints for each batch of dense observation data to each other and each batch of dense observation data must be finished all processing to the calculation of the next batch of dense observation data, so in this problem need to find the optimal scheduling strategy in order to handle all dense observation data through the shortest time.
In the traditional algorithm, there is no simple and easy-to-use algorithm that can be directly applied to this scheduling problem. The simpler method can adopt the random scheduling strategy, but the random scheduling strategy has great randomness, and it cannot guarantee that each scheduling can reduce the density of the dense observation data, so it cannot obtain better processing performance of the dense observation data.
In this paper, aiming at the scheduling problem of dense observation data, a "deal-reveal" scheduling algorithm is designed. Through the interaction between the map area and the real observation site, the algorithm guarantees that each scheduling will reduce the density of the dense observation data to the greatest extent, thus making the computation highly parallel and improving the performance of the system.

Problem Analysis
In the scheduling problem of the assimilation system, the key to improve the performance of the system is tantamount to complete the scheduling calculation of the dense observation data in a shorter time. The distribution of dense observation data is unbalanced, the density of each region is unique, and the same batch of dense observation data must not affect each other, in order to carry out parallel calculation normally.
The mutual non-influence of the dense observation data refers to the non-overlap of the influence areas of the same batch of dense observation data. Therefore, when there are enough parallel machines, the number of each batch of dense observation data that can be computed by parallel is limited. At this time, the scheduling strategy is the factor determining the performance of the assimilation system. The key point of this scheduling strategy is how to make the number of dense observations in each batch of parallel computation large enough.
On the basis of the above problem description and analysis, the following definition is made: there are N dense observation data, M parallel machines, the influence range of each dense observation data is the longitude and latitude range of the k*k size map centered on the location of the dense observation data, and all dense observation data fall within the map area S. The resolution of map region S is defined as S ratio , the number of grid points on the meridian line is Lon total , the number of grid points on the latitude line is Lat total , and the number of grid points on the map area is Grid total . When two populous area overlap between the influence of the observation data, said the two dense observation data conflict, define the influence of the i-th a dense observation data dense observation data of N i number, when all the dense observation data after being placed on the map region S, the influence of high density of each observation data will overwrite the grid points on the map. Set the freeze point value G ij to represent the number of dense observation data covering the grid point in the influence range, set the number of batches to be scheduled as C total , The number of dense observations processed in batch i is d i , the processing time of each batch of dense observation data as T deal , and the total processing time as T total .
The scheduling problem is described as follows:  In order to minimize T total , the number of batches to be processed, C total , should be minimized if the T deal value of each batch of observations is constant. To reduce the size of the C total , the amount of dense observations processed in each batch should be as large as possible d i for further analysis.
From the above description, it can be seen that making d i as large as possible is the key to the scheduling problem. The value of d i ranges from 1 to M, where M is the number of parallel machines. The essence of making d i as large as possible is to reduce the density of dense observations each time dense observations are scheduled. Dense intensive observation data distribution to a certain extent available maximum G max point value and maximum of dense observation data conflict R max described, when a lattice has a value of 0, represent the scope includes the lattice of all dense observation data calculation has been finished, so each batch of dense observation data calculation is the best result can make G max and R max to reduce to a great extent, when G max is 0, on behalf of all of the dense observation data are calculated.
In this paper, the corresponding influence range of each dense observation data is regarded as a "card", and the corresponding lattice point value is the number of "card" covering the lattice point. The scheduling and calculation of each batch of dense observation data can be regarded as taking out a certain number of "card" in the map area. After all the "card" are taken out from the map area, it represents that the dense observation data are all scheduled.
After the above analysis, the final scheduling strategy can be obtained, that is, when taking out the dense observation data in each round, the dense observation data corresponding to the lattice point value G max should be taken out first, and when G max corresponds to multiple dense observation data, the dense observation data corresponding to R max should be selected. This algorithm is named for the "deal-reveal" scheduling algorithm.

"deal-reveal" Algorithm
In this paper, the whole steps of the "deal-reveal" scheduling algorithm are divided into two steps, the first step is the "deal" step, the second step is the "reveal" step. In this algorithm, the influence range of observation data is regarded as a "card". "deal" places all observation data on the corresponding map area, and "reveal" puts the observation data into parallel machine for calculation according to certain strategies.
The "deal" step initializes the model as a whole, including initializing the region lattice, observation data, lattice matrix and relational matrix. The specific algorithm steps are as follows: 1) Initialize a map area to include all observation data, and set the resolution of the area, which is generally 0.01, indicating that every two adjacent grid points in the area are 0.01 longitude or 0.01 latitude apart; 2) Set the attributes of the observed data as id, lat, lon and qty, where id represents the sequence number, lat represents the latitude value, lon represents the longitude value, and qty represents the number of observed data in conflict with the observed data; 3) Three copies are obtained by copying all the observation data, named as lat-copy, lon-copy and qty-copy respectively. Among them, lat-copy is sorted in ascending order according to lat value, lon-copy in ascending order according to lon value, and qty-copy in descending order according to qty value; 4) The lattice point matrix G is initialized, where g ij is the value of row i and column j in G.
According to the influence range of observation data, the lattice point g ij on the map area is assigned a value, which is the number of observation data covering the lattice point; 5) Initialize the relationship matrix R, where r ij is the value of row i and column j in R. The value represents whether the observed data with id i is affected by the observed data with id j. If affected, the value is true, otherwise the value is false; 6) Initialize the selection array C, where C i is the value of index i in the relational matrix R, which represents whether the observation data with id i has been selected. If it has been selected, the value is true; otherwise, the value is false; In the "deal" process, the higher the value of the lattice point matrix G, the higher the density of the region, and the relational matrix R is rapidly initialized by two copies of the full observation data ordered by the values of lat and lon.
In the "reveal" step, observation data are taken out according to certain strategies. The observation data of each round are scheduled as follows: 1) Initialize the optional array O according to the selection array C, where O i if true means that the observation data with id of i has been selected, if false means that the data has not been selected; 2) According to the maximum lattice value in lattice matrix G, obtain the observation data with the highest quality value corresponding to all observation data that can be selected as the first observation data selected in this batch. The optional array O is updated by the relation matrix R and the array C is selected by the selected observation data update. If O i is true, it means that the observation data with id i has been selected or it conflicts with other selected observation data of the batch; 3) According to the optional array O, select the observation data with the largest qty value among the optional observation data as the next observation data, update the optional array O and selection array C; 4) Repeat step 3) until the number of observations required by the round is obtained or the round has no selected observations; 5) At the end of this round, the lattice point matrix G and the qty-copy are updated for the next round of scheduling; In the "reveal" step, the optional array O represents the optional array for this round, and the observations that are not optional for this round may be optional for the next round. Therefore, before each round, the optional array O should be cleared, and then initialized by the selection array C. The overall flow of this algorithm is shown in Figure. 1.

Experimental Result
The following results are produced by running the assimilation system using different scheduling methods with the same hardware configuration. From Figure. 2 experimental observation sites, and the number of dense observation data is thousands. The traditional scheduling algorithm and the "license-uncovered" scheduling algorithm are used to conduct scheduling tests on the same observation data respectively, and the first-round scheduling effect is shown in Figure. 3 and Figure. 4.
The overall time output of the assimilation system scheduled by the random scheduling algorithm is presented in Figure. 5, with a total time of about 34,200 seconds. The overall time output of the assimilation system scheduled by the "deal-reveal" scheduling algorithm is presented in Figure. 6, with a total time of about 4,300 seconds and an acceleration ratio of 7.95.
By contrast can be found that compared with the traditional random scheduling algorithm, when selecting observation data in each round, the "deal-reveal" scheduling algorithm takes into account the conflict relationship between observation data, and ensures that after each round of scheduling, the overall density of observation data is effectively reduced, thus reducing the overall number of scheduling rounds. By scheduling the observation data with this algorithm, the parallelization degree of each round of the scheduled observation data significantly increases, and the overall performance of the system is further greatly enhanced.

Conclusions
In this paper, we study a kind of numerical weather model dense observation data assimilation system scheduling problem. The essence of the problem is with special constraint conditions to minimize the completion time of parallel machine scheduling problem. It is difficult for traditional methods to solve the scheduling problem of the parallel multi-machine with the minimum completion time with this special constraint, so this paper proposes a "deal-reveal" scheduling algorithm to solve the scheduling problem of the parallel multi-machine with the minimum completion time under this special constraint. In this algorithm, the influence area of observation data is represented by "card", and the number of "card"s covering the grid point is recorded by the grid point value, so as to ensure that each scheduling can select non-conflicting observation data from the most dense map area. After each round of scheduling, the density of observation data decreases continuously, so a lower number of scheduling rounds can be obtained to reduce the overall processing time and effectively improve the performance of the assimilation system.
The results show that the algorithm can be effectively applied to a large scale parallel scheduling problem with minimum completion time under special constraints, and the algorithm can be further applied to other parallel scheduling problems with minimum completion time similar to this problem.