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

This article mainly introduces "the analysis of lock competition phenomenon in multi-core programming". In the daily operation, I believe that many people have doubts about the analysis of lock competition phenomenon in multi-core programming. The editor consulted all kinds of data and sorted out simple and useful operation methods. I hope it will be helpful for you to answer the doubts about "lock competition phenomenon analysis in multi-core programming". Next, please follow the editor to study!

For the sake of simplicity, let's look at a simple situation where four equivalent tasks are started at the same time, and each task starts with an operation that requires lock protection, which takes 1 and the rest of each task takes 25. The operation of these tasks after starting and running is shown in the following figure:

Figure 1: lock contention diagram for peer-to-peer tasks

In the figure above, you can see that the first task was executed directly to the end without waiting, the second task waited for 1 unit of time, the third task waited for 2 units of time, and the third task waited for 3 units of time.

In this way, there are three CPU waiting for a total of six time units. If all the tasks in the OpenMP wait at the same point until all the tasks are executed, then the total running time will be the same as the fourth task is 29 time units, and the acceleration factor is: (1 × 4 × 25) / 29 = 3.48

Even if the average time of 4 tasks is 27.5, the acceleration factor is 101 max 27.5 = 3.67

If the acceleration coefficient is calculated according to Amrda's law, in the above applications, the serial time is 1, and the total time of parallel processing is converted to 100 time units after serial. If it is run on a 4-core CPU, the acceleration factor = p / (1 + (pmur1) * f) = 4 / (1 + (4-1) * 1x101) = 404ram 104 = 3.88

This gives rise to a strange problem. After using the lock, the acceleration coefficient is not even as good as that calculated by Amda's law, let alone the acceleration coefficient calculated by Gustafson's law.

In fact, the lock contention of the above four tasks can be extended to a more general case, assuming that the serialization time with lock protection is 1, and the running time of parallelizable part on a single core CPU is t CPU core p, then when p pairing tasks are running at the same time, the total waiting time caused by lock contention is 1 CPU 2 +. + p = p* (pmur1) / 2

The time spent by the most time-consuming task is: P + tUnip

If you use the time spent by the most time-consuming task as the parallel run time, the acceleration factor is as follows

S (p) = (twee1) / (pairt / p) = p* (twee1) / (p*p+t) (acceleration coefficient formula under lock competition)

This formula shows that in the case of lock competition, if the kernel number is fixed, the larger the parallelizable part is, the greater the acceleration coefficient will be. In the case of fixed parallelization time, if there are more CPU cores, the acceleration coefficient will be smaller.

Or calculate a few practical examples to illustrate the effect of the above formula:

Make tweak 100, pendant 4, acceleration coefficient = 4 × (100 + 1) / (4 × 4 × 100) = 3.48

Make tweak 100, pendant 16, acceleration coefficient = 16 × (100mm 1) / (160160100) = 4.54

Make tweak 100, pendant 64, acceleration coefficient = 64 × (100mm 1) / (64064nm 100) = 1.54

The acceleration coefficient is 128 × (100 / 100) / (128 / 128 / 100), and the acceleration coefficient is 128 × (100 / 100).

From the above calculation, it can be seen that when the number of cores reaches a certain level, the acceleration coefficient decreases instead of increasing. When the number of cores increases to 128, the acceleration coefficient is only 0.78. it is not as fast as running on a single-core CPU.

In the above example, the serial code caused by lock protection is called when the task starts, but the same is true for lock-protected serial code that is called elsewhere in the peer task.

Lock contention for peer-to-peer tasks is very common in practice, such as server software, where clients usually deal with tasks equally. If locks are used, it is easy to cause the above-mentioned acceleration factor to decrease with the increase in the number of CPU cores.

In the past, server software usually runs on dual-CPU or four-CPU machines, so the decrease of acceleration coefficient caused by lock competition is not obvious. after entering the multi-core era, with the increase of the number of CPU cores, this problem will become very serious, so the multi-core era poses a new challenge to programming. The previous idea of multitasking programming may not work on multi-core programming.

Therefore, it is impractical to simply think that multi-core programming is equivalent to previous multitasking programming or parallel computing. Some countermeasures are put forward in the article on the problem of serialization, but those countermeasures can only be achieved if the industry continues to work hard.

At this point, the study on the analysis of lock competition in multicore programming is over. I hope to be able to solve everyone's doubts. The collocation of theory and practice can better help you learn, go and try it! If you want to continue to learn more related knowledge, please continue to follow the website, the editor will continue to work hard to bring you more practical articles!

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.