- Abstract
- To the reader
- Introduction
- 1. Independent calculations of equal difficulty on homogeneous computational nodes
- 2. Independent calculations of equal difficulty on heterogeneous computational nodes
- 3. Independent calculations of different difficulty on homogeneous computational nodes
- 4. Independent calculations of different difficulty on heterogeneous computational nodes
- 5. Dependent calculations of equal difficulty on homogeneous computational nodes
- 6. Dependent calculations of equal difficulty on heterogeneous computational nodes
- 7. Dependent calculations of different difficulty on homogeneous computational nodes
- 8. Dependent calculations of different difficulty on heterogeneous nodes
- References
- About the Author
Abstract
The article briefly concerns methods of estimating the minimum time of executing tasks at optimal distribution of load among processors. The given methods can be used both for homogeneous and heterogeneous computer systems.
To the reader
This document is part of a series of articles devoted to the questions of creating quality and effective program solutions for modern 64-bit multi-core systems. You can see other articles on the site http://www.viva64.com.
Introduction
Despite great computational power of modern computers there are tasks solution of which in sequential mode takes much time. The time for solving such tasks can be greatly reduced by using abilities of modern multi-core processors for calculations. In order to fully use the advantages provided by these processors it is necessary to improve algorithms of solving tasks taking into consideration the possibility of parallel data processing performed by several processors simultaneously. It is also important to distribute calculations in such a way that each processor be used most fully and the total time of solving a task tend to minimum. The article gives a review of the methods of estimating the minimum time of executing tasks at their optimal distribution among computational nodes. Situations are taken into account when several parallel tasks are executed on one system taking some resources of computational nodes. In this case the system is considered heterogeneous (anisotropic) in relation to the program we're interested in.
1. Independent calculations of equal difficulty on homogeneous computational nodes
Suppose we have N independent calculations of equal difficulty. We need to distribute them among P processors which have equal computational power (figure 1). The natural solution of this task is assigning
calculations to each processor.
Figure 1.
But this solution is proper only in that case if N contains P
. Otherwise there remain from 1 to
non-assigned calculations. It will be a mistake to assign all the remaining calculations to one processor as in this case the time of termination of all the calculations will equal
. It is better to distribute the remaining calculations by one for each of
processors. In this case the time of termination of all the calculations will equal
. It is obvious that
, thats why the second method can be much better.
2. Independent calculations of equal difficulty on heterogeneous computational nodes
Suppose we have N independent calculations of equal difficulty. We need to distribute them among P processors which have different computational powers
(figure 2).
Figure 2.
The time the processor with computational power
spends on executing one calculation equals
. Thus, we need to split the calculations into P groups with
calculations in each so that the time of termination of all the calculations be minimum, i.e.:
3. Independent calculations of different difficulty on homogeneous computational nodes
Suppose we have N independent calculations of different difficulty
.We need to distribute them among P processors which have equal computational power (figure 3).
Figure 3.
For the minimum time of termination of all the calculations it is necessary that all P processors be loaded most evenly, that is all the processors should be assigned calculations of approximately equal sizes. Thus, the task comes to the following: it is necessary to split the calculations into P groups with
calculations in each
, so that:
where
— difficulty of j-calculation in
-group.
4. Independent calculations of different difficulty on heterogeneous computational nodes
Suppose we have N independent calculations of different difficulty
(figure 4).
Figure 4.
The time the processor with computational power
spends on executing one calculation with difficulty
equals
.
For the minimum time of termination of all the calculations it is necessary that all the processors end calculations approximately at the same time. Thus, the task comes to the following: it is necessary to split the calculations into P groups with
calculations in each
, so that:
where
— difficulty of j-calculation in
-group.
5. Dependent calculations of equal difficulty on homogeneous computational nodes
Suppose we have N dependent calculations so that calculation of k-step for i-calculation demands the result of k-step for
-calculation,
preserving the sequence of elements in such a way that:
where
— — power of
subset.
6. Dependent calculations of equal difficulty on heterogeneous computational nodes
Suppose we have N dependent calculations so that calculation of k-step for i-calculation demands the result of k-step for
-calculation, i.e.
. Suppose also we have P processors which have different computational powers
.
The task of distributing calculations among processors in this case can be formulated as follows: An ordered set of calculations C should be split into P non-overlapping ordered subsets
preserving the sequence of elements in such a way that:
where
— power of
subset. That is, the maximum difference in time of performing calculations in neighboring subsets must be minimum.
7. Dependent calculations of different difficulty on homogeneous computational nodes
Suppose we have N dependent calculations so that calculation of k-step for i-calculation demands the result of k-step for
-calculation, i.e.
. Suppose also we have P processors which have equal computational powers.
The task of distributing calculations among processors in this case can be formulated as follows: An ordered set of calculations C should be split into P non-overlapping ordered subsets
preserving the sequence of elements in such a way that:
where
— difficulty of calculations making part of
subset.
8. Dependent calculations of different difficulty on heterogeneous nodes
Suppose we have N dependent calculations so that calculation of k-step for i-calculation demands the result of k-step for
-calculation, i.e.
. The task of distributing calculations among processors in this case is formulated as follows: an ordered set of calculations C should be split into P non-overlapping ordered subsets
preserving the sequence of elements in such a way that:
where
— difficulty of calculations making part of
subset.
References
- M.V. Yakobovskiy, S.A. Sukov. Dynamic load balancing // Materials of the conference "High-performance calculations and their applications", Chernogolovka, 2000, pp. 34-39.
- V.P. Ivannikov, N.S. Kovalevskiy, V.M. Metelskiy. Of minimum time of implementing competitive processes in synchronous operations. // Programming. 2000, 5, pp. 44-52.
- E. Tanenbaum. Distributed systems. Principles and paradigms. - St. Petersburg: Piter, 2003. - pp. 877.
- A.A. Bukatov, V.N. Datsuk, A.I. Zhegulo. Programming of multi-processor computer systems. Rostov-on-Don. Publishing House OOO "VCRU", 2003, pp. 208.
- A. Nemnyugin, O.L. Stesik. Parallel programming for multi-processor computer systems. - St. Petersburg: BHV-Peterburg, 2002. - pp. 400.
About the Author
Andrey Nikolaevich Karpov, http://www.viva64.com
Develops program solutions in the sphere of resource-intensive applications quality and performance increase. One of the developers of Viva64 static analyzer for verifying 64-bit software. Participates in developing VivaCore open library for working with C/C++ code.
