Shulou(Shulou.com)06/02 Report--

This article focuses on "how to understand load balancing in multicore programming". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand load balancing in multicore programming.

In multi-core CPU, if you want to give full play to the performance of multiple CPU, you must ensure that the tasks assigned to each CPU have a good load balance. Otherwise, some CPU are running, while others are idle, unable to take advantage of multicore CPU.

There are usually two schemes to achieve a good load balancing, one is static load balancing, the other is dynamic load balancing.

1. Static load balancing

In static load balancing, it is necessary to manually divide the program into multiple parallel executable parts, and to ensure that the divided parts can be evenly distributed to each CPU, that is to say, the workload should be evenly distributed among multiple tasks to achieve a high acceleration coefficient.

The static load balancing problem is a NP completeness problem mathematically. Richard M. Karp, Jeffrey D. Ullman, Christos H. Papadimitriou, M. Garey, D. Johnson and others have proved the NP completeness of static load problems under several different constraints from 1972 to 1983.

Although the NP completeness problem is a difficult problem in mathematics, it is not the difficult problem mentioned in the title, because the NP completeness problem can generally find a very effective approximate algorithm to solve.

2. Dynamic load balancing

Dynamic load balancing is to distribute tasks in the running process of the program to achieve the purpose of load balancing. In practice, there are many problems that can not be solved by static load balancing. for example, in a large cycle, the number of cycles is input from the outside, and the number of cycles is not known in advance. at this time, it is difficult to achieve load balancing by using static load balancing partition strategy.

The scheduling of tasks in dynamic load balancing is generally realized by the system, programmers can only choose the scheduling strategy of dynamic balance, but can not modify the scheduling strategy, because there are many uncertain factors in the actual task, the scheduling algorithm can not do very well, so dynamic load balancing may sometimes fail to meet the established load balancing requirements.

3. What is the problem of load balancing?

The difficulty of load balancing does not lie in the degree of load balancing, because even if there are some differences in the task execution time allocated on each CPU, the total execution time decreases with the increase of the number of CPU cores, thus the acceleration factor increases with the increase of the number of CPU cores.

The difficulty of load balancing is that many parallel executable blocks in the program have to be divided by programmers, but when the number of CPU cores is small, such as dual-core or 4-core, this division is not very difficult. However, with the increase of the number of cores, the granularity of the partition will become finer and finer, and when it is more than 16 cores, it is estimated that programmers will be crazy about how to divide tasks. For example, a sequentially executed code, running on a 128core CPU, is manually divided into 128tasks, and the difficulty of the division can be imagined.

The error of load division will be magnified with the increase of the number of CPU cores. For example, a program that requires 16 time units is divided into 4 tasks, and the average load execution time on each task is 4 time units. If the division error is 1 time unit, then the acceleration coefficient becomes 16 / (4 / 1) = 3.2, which is 80% of the ideal acceleration coefficient 4. However, if you run on a 16-core CPU, if the partition error of a task is 0.5 time units, then the acceleration coefficient becomes 16 / (1 / 0.5) = 10.67, only 66.7% of the ideal acceleration coefficient 16. If the number of cores increases again, the ratio of the acceleration coefficient to the ideal acceleration coefficient will decrease due to the amplification of the error.

The problem of load sharing is also reflected in the upgrade of CPU and software, for example, the load sharing on 4-core CPU is balanced, but on 8-core and 16-core, the load may become unbalanced again. The same is true of software upgrade, when the software adds functions, the load balance will be destroyed, and the load needs to be redivided to achieve balance, so the difficulty and trouble of software design is greatly increased.

If locks are used, some loads that appear to be balanced may also become unbalanced due to lock competition

4. Coping strategies for load balancing.

For the software with small amount of computation, the running speed is very fast even if it is put on the single-core CPU, and the poor load balancing does not have much impact. In practice, the software with large computation and large scale should be considered in load balancing. These software need to balance the load on the multi-core to improve the performance.

For large-scale software, the response strategy for load balancing is to develop a macroscopic partition method of parallel blocks, which is divided from the whole software system level. instead of parallel decomposition for some local programs and algorithms, as the traditional one, because local programs are usually difficult to decompose into more than dozens of tasks to run.

Another coping strategy is at the tool level, that is, compiling tools can help manually decompose parallel blocks and find a good decomposition solution. Intel has made some efforts in this respect, but more efforts are needed to make the tools more powerful in order to cope with the situation with more audits.

At this point, I believe you have a deeper understanding of "how to understand load balancing in multicore programming". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.