Estimation of the minimum time of executing tasks at optimal distribution of load among processors

25.03.2009 Andrey Karpov

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 Picture 1907789 calculations to each processor.

Picture 1884204

Figure 1.

But this solution is proper only in that case if N contains P Picture 1882798 . Otherwise there remain from 1 to Picture 1932280 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 Picture 1932281 . It is better to distribute the remaining calculations by one for each of Picture 1933086 processors. In this case the time of termination of all the calculations will equal Picture 1931960 . It is obvious that Picture 1932301 , 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 Picture 1932349 (figure 2).

Picture 1932373

Figure 2.

The time the processor with computational power Picture 1932600 spends on executing one calculation equals Picture 1932484 . Thus, we need to split the calculations into P groups with Picture 1932523 calculations in each so that the time of termination of all the calculations be minimum, i.e.:

Picture 1932563

3. Independent calculations of different difficulty on homogeneous computational nodes

Suppose we have N independent calculations of different difficulty Picture 1932632 .We need to distribute them among P processors which have equal computational power (figure 3).

Picture 1932518

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 Picture 1932818 calculations in each Picture 1932745 , so that: Picture 1932808 where Picture 1932738 — difficulty of j-calculation in Picture 1932841 -group.

4. Independent calculations of different difficulty on heterogeneous computational nodes

Suppose we have N independent calculations of different difficulty Picture 1932853 (figure 4).

Picture 1932958

Figure 4.

The time the processor with computational power Picture 1932991 spends on executing one calculation with difficulty Picture 1933253 equals Picture 1933087 .
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 Picture 1933175 calculations in each Picture 1933210 , so that:

Picture 1933265

where Picture 1933128 — difficulty of j-calculation in Picture 1933303 -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 Picture 1933283 -calculation, Picture 1933388 preserving the sequence of elements in such a way that:

Picture 1933506

where Picture 2026042 — — power of Picture 2026024 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 Picture 2026000 -calculation, i.e. Picture 2025987 . Suppose also we have P processors which have different computational powers Picture 2025969 .
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 Picture 2025935 preserving the sequence of elements in such a way that:

Picture 2025911

where Picture 2025890 — power of Picture 2025873 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 Picture 2025849 -calculation, i.e. Picture 2025834 . 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 Picture 2025796 preserving the sequence of elements in such a way that:

Picture 2025767

where Picture 2025752 — difficulty of calculations making part of Picture 2025735 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 Picture 2025708 -calculation, i.e. Picture 2025699 . 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 Picture 2025639 preserving the sequence of elements in such a way that:

Picture 2025629

where Picture 2025620 — difficulty of calculations making part of Picture 2025610 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.