118
edits
Changes
→Solutions Of False Sharing
== Cache Coherence ==
[[File:cacheCoherence.jpg|center|800px]]<br />
When the CPU accesses the data at that time data goes into the cache and this memory block is known as the cache line. But it is not possible that modify the original data when changes in the cache line. Here cache coherence helps that stored in multiple local caches. Cache coherence connects all cache. == MESI ==First, we know that the cache line has four different states. Like, exclusive, shared, modified, and invalid. So MESI is an acronym for all four states. To understand it well we throw light on this example. [[File:MESI1.jpg|400px]]<br /> This picture shows that the core A read value a from the main memory. So this core also fetches some nearby values from the main memory and stores these values in the cache line and makes it exclusive because only core A operates this cache line. [[File:MESI2.jpg|400px]]<br /> Later, core B also reads the value of b from memory. Now, a and b both read the same cache line and close so, both cores are shared. [[File:MESI3.jpg|400px]]<br /> Moreover, core A change the value of a so, this change is stored in the buffer and cache line tagged as modified. In the end, it communicates with core B and is known as an invalid cache line.
= '''What is False Sharing?''' =
To our surprise, the serial block took much less time, no matter how many times I ran it. This turned our existing knowledge upside down, but don't worry, it's because you don't understand False Sharing yet.
= '''Solutions Of False Sharing''' =
== Use local variables for each thread ==
As we said above, the smallest unit of CPU operation on the cache is the size of a cache line, which is 64 bytes. As you can see in our program code, the sum is a vector that stores two data with long data type. The two long data are in fact located on the same cache line. When two threads read and write sum[0] and sum[1] separately, it looks like they are not using the same variable, but in fact, they are affecting each other.For example, if a thread updates sum[0] in CPU0, this causes the cache line of sum[1] in CPU1 to be invalidated. This causes the program to take longer to run, as it needs to re-read the data.
We try to change the sizeOfSum to 8, which means that changing the size of the vector sum to 8 and the if condition in the sumUp function to i%8==id will give the program more data to process. Nevertheless, the result still does not bring the time between the Serial block and Thread block closer and the Serial block still takes less time.
Also, we add the following code to our main function:
cout << endl << "----new Local variable block---" << endl; // new Local variable block
{
vector<long> sum(sizeOfSum, 0);
}
auto end = chrono::steady_clock::now();
cout << "New Local variable block consumption: " << chrono::duration_cast<chrono::microseconds>(end - start).count() << "ms" << endl;
}
[[File:newBlockOutput5.jpg|400px]]<br />
We can see that the new Local variable block is already much faster than the Thread block, and even comparable to the Serial block is almost the same. But overall the Serial block is still the least time-consuming because the new Local variable block still needs to incur extra overhead for thread creation and scheduling.
We could try increasing sizeOfNumbers to 1000000 as well, which would allow the program to process more data, thus compensating for the extra overhead of thread creation and scheduling.
Now we can already see the advantage of multi-threading. Even when the vector numbers reach the size of 1000000, the Thread block even runs faster than the Serial block.
So the problem of false sharing sometimes cannot be generalized, and the occurrence of false sharing does not necessarily make performance lower. But no matter how the new Local variable block is the optimal solution.
== Byte alignment ==
}
In this program code, we can easily see that the Number struct has two member variables (num1 and num2). They are for loop in two different threads to execute the increment operator 1000000 times. This time we use Linux with multiple cores to compile (note that here we are not using any optimization).
g++ -std=c++11 -pthread false_sharing.cpp
Have you learned? The so-called false sharing can make performance worse in fact this cannot be generalized. We can see that with O2 on, the CPU and compiler are able to optimize the serial version of the code very well, while the multi-threaded code is not well optimized, which leads to higher performance of the serial version of the code. Even using a byte-aligned cache line size does not help. In the first example, we increased the number of vector numbers, which caused the serial code to slow down significantly. The differences in the two examples are related to the specific execution logic.
So don't treat pseudo-false sharing as a beast, and don't treat 64-byte alignment as a panacea. Everything has to be actually tested to know. Don't throw out the conclusion under O0 and then take it as a guideline, that makes no sense ......
= '''Conclusion''' =
https://wiki.cdot.senecacollege.ca/wiki/GPU621/False_Sharing
https://www.baeldung.com/java-false-sharing-contended#:~:text=In%20the%20MESI%20protocol%2C%20each,the%20acronym%20of%20these%20states.
https://learn.microsoft.com/en-us/archive/msdn-magazine/2008/october/net-matters-false-sharing
http://www.nic.uoregon.edu/~khuck/ts/acumem-report/manual_html/multithreading_problems.html
