This paper analyzes the implementation of a parallel algorithm for finding the optimal solution of a transport problem by the potential method using OpenMP technology on dual- and quad-core processor systems. The results are obtained, which indicate the possibility of further optimization of the computational process of finding the optimal solution of the transport problem by varying the number of parallel streams and processor cores of the computer. A number of numerical experiments have been performed to confirm the effectiveness and reliability of the approach witch proposed in the paper.
It should be noted that many problems in their mathematical formulation are reduced to a transport problem.
Thus, with this method you can find the optimal organization of work in the planning of construction sites, the distribution of a given volume of work between different people, the delivery of goods and more.
Finding the optimal solution to a transport problem can find application in different areas: in economic in logistics planning; in the educational process; when developing databases; in programming.
Such a wide range of applications testifies to the relevance of the subject under study task.
The rapid expansion of the spheres of application of the methods of mathematical
modeling and optimization, which has been happening in recent years, creates the
need for solving new classes of problems of increased complexity and dimension [
The article proposes the application of a parallel algorithm for finding a solution to a transport problem with current trends in the development of a computer system.
The main advantage of parallel algorithms over sequential ones is the speed of
execution [
Therefore, the purpose of this article is to parallelize the algorithm of finding the optimal solution of a transport problem by the potential method by using OpenMP parallel programming technology, that is, to take maximum account of current trends in the development of multi-core processors.
At the present stage of development of society and economy, specialists must constantly improve the principles and methods of managing complex economic systems.
In these circumstances, the manager must have the basic principles and techniques of mathematical programming, and be able to apply them in practice.
Thus, a wide range of economic problems associated with managing complex processes require the use of modern methods of optimization and management decisionmaking.
It is the application of the transport problem to solve the distribution tasks in various fields of economic activity that enables to obtain the most effective results and to put them into practice successfully.
The transport problem (1) - (3) [
m n min
i1j1cij xij m i1xij b j , j 1,2,..., n, m i1xij ai , i 1,2,..., m, xij 0 (1) (2) (3) Here xij - the volume of production, cij - the rate of delivery of products from the i - supplier to the j - consumer, b j - the needs of consumers for products, ai - the inventory of products from suppliers.
There are two steps to solving a transport problem:
1) building a reference plan [
When solving a transport problem, you must have an initial reference plan.
The work of finding this plan was implemented using the least cost method.
The rules for finding an initial reference plan for a transport problem by the least cost method differ from the rules for finding such a plan diagonally by the sequence of cell selection that you want to fill.
According to the method of least cost, the cell with the least cost of transporting a unit of cargo from the supplier to the consumer is selected first.
If there are several such cells, then we choose the one for which the quantity of transportable cargo is the largest.
After constructing the initial reference plan, each of the methods in the table must be filled in (m n 1) by cells, because the rank of the matrix of the transport task constraint system is equal r m n 1 , where m - the number of suppliers, n - the number of consumers.
If the number of cells filled is less (m n 1) , then the plan is degenerate.
Then it is necessary to fill in an appropriate number of empty (nonbasic) cells, recording in them "zero transportation", and to consider these cells basic.
However, when the number of cells filled exceeds (m n 1) , the initial reference plan is not properly constructed and is not the reference one.
Next we focus on a detailed analysis of the potential method to obtain the optimal solution.
1. Optimality criterion of the reference plan by the method of potentials.
We already know the methods of finding the initial support plans of a transport problem, but we do not know if these basic plans are optimal, ie, giving the lowest total cost of transportation of all cargo from suppliers to consumers.
The reference plan is tested for potential optimality.
According to each supplier Ai we put the potential ui , a to each consumer B j j .
Optimality criterion for the transport plan reference plan: if for some reference plan ( xij ) of a transport problem there are such potential numbers ui and j that for basic cells the equality ui j cij , is fulfilled and for non-core cells the inequality ui j cij is satisfied for all i 1, m, j 1, n , then such reference plan is optimal.
The reference plan potentials are determined from the system ui j cij that write down for each filled cell of the transport task table. equations
Using the calculated potentials, we check the optimality condition ui j cij for unfilled cells in the table.
If this condition is not met for at least one non-core cell, that is ui j cij , the current plan is not optimal and you need to move to a new reference plan. 2. Transport task recalculation cycles
The transition from one reference plan to another is performed by filling a noncore cell for which the optimality condition is violated.
If there are several outlined cells, then the one that has the most disturbance is selected for filling, that is max ij (ui j ) cij .
A recalculation cycle is built for the selected empty cell.
The redistribution of products within the cycle is carried out according to the following rules:
a) to each vertex of the cycle is assigned a specific sign, with an unfilled cell a sign "+", and all others alternately signs "-" and "+"; b) enter into the empty cell the least of the numbers in cells with the sign "-".
At the same time, this number is added to the corresponding numbers in cells with the sign "+" and subtracted from the numbers in cells with the sign "-".
Thus, the free cell became full and the corresponding cell with the smallest number (at the top with "-") became blank.
As a result of this redistribution of products, we will receive a new reference plan for the transport problem, which we again test for optimality.
If the solution is optimal, then we calculate the minimum value of the objective function (the minimum cost of transporting the entire load), and if not optimal, then again build the recalculation cycle and move to the new reference plan using the cycle shift.
The process is repeated until the optimal solution to the transport problem is obtained.
The values of the base cells that did not participate in the recalculation cycle remain unchanged in the new table.
If at some point the needs coincide with the stocks, then the needs are set to true zero, and in the stocks - dummy (zero with a dot).
Then a complete system of equations for finding the potential values is immediately constructed.
In degenerate plan problems, the cycle shift often needs to be set to 0.
Then, when moving to the next table, the values of the base cells that participated in the conversion cycle did not change.
Only this "base zero" is transferred to a non-base cell, for which it essentially did a recalculation cycle, and the cell that contained this 0 becomes free.
Without reducing the generality of the approach proposed in the paper, let us consider the model problem of minimizing the cost of drinking water delivery.
Delivery of drinking water to vending machines will always be necessary, most people use them several times a week.
Therefore, there may be problems with the transportation and filling of the machines in a timely manner and with minimal gasoline costs.
The volume of drinking water is determined by the presence of a certain number of liters of water from the storage.
When delivering water to fill an automatic machine, there are situations where one machine can fill multiple automatic machines because it contains more water than necessary.
Alternatively, it is necessary for one machine to transport water to machines that are closest to each other and contain a volume so that the machine can fill them with the least residue.
When carrying out such operations with a large number of consumers, there are certain difficulties in finding the best option among the many existing ones that would provide for the needs of consumers and the costs of carriers would be minimal.
To solve this problem, you can build an economic-mathematical model that boils down to a transport-type problem.
Suppose we have n drinking water storage facilities that are in demand at a particular time, and it is planned to distribute water from them to m consumers (drinking water dispensers).
To construct an economic and mathematical model of the problem we introduce the following notation: i - water storage index, i 1, n, j - vending machine index, j 1, m , b j - volume of water to be delivered to the j vending machine; cij - the cost of transporting water to the j vending machine from i storage; ai - volume of water in the i storage in liters; xij - the number of liters that will be delivered to the vending machine from its storage.
It is necessary to find a solution to problem (1) - (3), that is, an optimal strategy for the distribution of available water resources, which will minimize the cost of the carrier during the water delivery. 4
In the paper, the potential method is chosen to parallel the solution of a given
problem, because it allows to solve the transport problem for a finite number of steps
(iterations) according to the constructed reference plan, which uses the least cost method
[
The advantages of the potential method over other methods are that there is no need to construct cycles for each of the empty cells and simplify the calculation of the algebraic sums of tariffs.
Only one cycle is being built - the one that is being recalculated.
Applying the method of potentials, we can speak not of the sign of algebraic sums of tariffs, but of the comparison of indirect tariffs with the true ones.
The requirement for the inalienability of algebraic sums of tariffs is replaced by the condition that indirect tariffs do not exceed the true ones.
It should be borne in mind that the potentials (as well as cycles) for each new baseline plan are redefined.
To understand this, we first present a sequential algorithm for solving a problem, and then build a parallel algorithm based on it.
The sequential algorithm for solving the transport problem (1) - (3) by the potential method for obtaining the optimal solution is as follows: 1. Let u1 0, Dmin c11 u1 1 2. Let's find out ui , j , i 2, n, j 1, m .
3. For each cell (i, j) we calculate Dij cij ui j , incidentally searching Dmin .
4. If not Dmin
0 , then the plan is optimal and the method ends. 5. We select the cell (imin , jmin ) with the smallest Dij Dmin and construct the loop, while at the same time finding the least xmin of the values xij in the cells that have an even number in the cycle.
6. We assume that xij xij xmin if the sequence number of a cell in a loop is odd xij xij xmin , if the sequence number of a cell in a cycle is even, then i, j the coordinates of the cell.
7. Go to step 3.
Analyzing the algorithm for the possibility of parallelization, we came to the following conclusions:
1) Steps 1-2 are inappropriate to parallelize, since the potential value can only be obtained if the potential value is available and vice versa.
2) Steps 3-4 are convenient to parallelize since the shared data are arrays C ,U and V , and do not change during execution, but are read-only.
The value Dmin changes during execution, however, announcing local variables Dmin for each of the threads allows for proper synchronization.
Therefore, steps 3-4 are subject to parallelization by distributing iterations between threads.
3) Step 5 is inappropriate to parallelize, the fragments of the search of the -this cell can only be performed if the -this cell of the cycle is present.
4) Step 6 is easy to parallelize using read-only shared data xmin .
Therefore, step 6 is subject to parallelization by distributing iterations between threads.
So, the parallel algorithm will look like this:
Items 1), 2), 4), 6), 7), 9), 10) coincide with the sequential algorithm, and the following items are different:
3. We divide many cells into portions in proportion to the number of processor cores. We pass information to computing nodes.
5. Based on the data obtained from the computing nodes, we select the smallest Dmin .
8. We divide many cells into portions in proportion to the number of processor cores.
We pass the position of the cycle cells to the computing nodes.
C ++ compiled applications are mobile, namely it can be run on computers from different manufacturers and operating systems, making C ++ particularly popular.
Application interface (see Fig. 1) 1) Was designed in C ++ Builder6.
This allows you to edit the number of rows and columns of the matrix - add or delete them, fill in the data manually through the application interface, or read from a file.
In the absence of redundancy, no intermediate results are output, only a postdegeneration reference plan, U and V potentials, a free cell estimation matrix, an optimal plan and minimal transportation costs. Also, we output all the intermediate and final results in a text file, in it you can see the dimension of the matrix, the initial matrix, all stages of its modification and such end results as the execution time, the reference plan and the minimum costs.
In Fig.2 you can see the initial matrix and the final results of the execution.
To parallel the computational process, a parallel programming software with OpenMP
specification was used [
OpenMP is a standard that includes compiler directives, libraries, and system variables that can be used to indicate concurrency on shared memory systems.
This is a technology that can be considered as a high-level add-on over Pthreads (or similar thread libraries).
OpenMP provides SPMD - a Model (Single Program Multiple Data) of parallel
programming, which uses the same code for all parallel streams [
OpenMP is easy to use and includes only two basic types of designs: directives and functions of the OpenMP runtime that connect as an additional “omp.h” library. Graphic description language was used to represent the diagrams for object modeling in software development area - UML, namely in Draw IO.
It is known [
From here you can see that the parallel algorithm gives an acceleration of more than one unit (gain) when the input matrix size is about 10,000 elements.
The graphs shown in Fig. 3 and Fig.4 it can be seen that, indeed, the larger the dimension, the better the advantage of the larger the number of processor cores.
Amdal's law [
1000 10000 100000 0,0312 0,495 1,003 4,537 14,527
Time 0,221 1,184 1,562 3,917 11,91 0,14 0,413 0,642 1,158 1,219 0,282 1,029 1,483 3,437 10,15 0,11 0,467 0,676 1,32 1,431 Testing on the dimension of Problem 100000 obtained acceleration rates of 1,219 (2 processors) and 1,431 (4 processors).
This relatively low acceleration is related to the amount of concurrent code in the algorithm.
The results obtained confirm Amdal's law; the acceleration of the system cannot exceed the inverse of the proportion of successive calculations. Conducted testing of the developed software allows to conclude that the parallel algorithm for solving the transport problem can be used to effectively find the optimal solution by the potential method only with a large amount of input data with an increased number of processor cores.
The latter is especially relevant for the modern development of multi-core systems. 7
In this work we propose an algorithm for finding the optimal solution of a transport problem that can be used on multi-core systems.
The latter are increasingly used in various subject areas and are a better opportunity to increase the power of processors.
The parallelization was done using OpenMP parallel programming technology.
The efficiency of this algorithm is tested by running it on dual- and quad-core processors.
The validity of the results obtained in the article is confirmed by the theoretically obtained estimates by Amdal's law.
You can also conclude that this algorithm allows you to get the best solution for a transport problem for large dimensions of input with greater efficiency.
This study is particularly relevant in the current rapid development of multi-core systems.