96
edits
Changes
→Identifying False Sharing
== Introduction ==
Multicore processors are more prevalent now more than ever, and Multicore programming is essential to benefit from the power of the hardware as it allows to run our code different CPU cores. But it is very important to know and understand the underlying hardware to fully utilize it. One of the most important system resources is the cache. And most architectures have shared cache lines. And this is why false sharing is a well know know problem in multicore/multithreaded processes.
'''What is False Sharing (aka cache line ping-ponging)?''' <br>
False Sharing is one of the sharing pattern that affect performance when multiple threads share data. It arises when at least two threads modify or use data that happens to be close enough in memory that they end up in the same cache line. False sharing occurs when they constantly update their respective data in a way that the cache line migrates back and forth between two threads' caches.
In this article, we will look at some examples that demonstrate false sharing, tools to analyze false sharing, and the two coding techniques we can implement to eliminate false sharing.
=Cache Coherence=
#include <algorithm>
#include <omp.h>
#define NUM_THREADS 84#define DIM 100010000
using namespace std::chrono;
}
int threads_used;
omp_set_num_threads(NUM_THREADS);
double start_time = omp_get_wtime();
#pragma omp parallel
{
int tid = omp_get_thread_num(); odds_local[tid] = 0.0;
#pragma omp for
for(int i=0; i < DIM; ++i){
}
</source>
[[File:FalseSpeedupSpeedupFs.png|center|850px500px]]
=Eliminating False Sharing=
===Padding===
<source lang ="cpp">
#define CACHE_LINE_SIZE 64
</source>
[[File:Numpad0.png]][[File:Numpad7.png]][[File:Numpad15.png]]
Padding your data is one way to prevent false sharing. What this does is by adding padding to the data elements sitting in a contiguous array you separate each element from each other in memory. The goal of this method is to have less data elements sitting the same cache line so when you write to memory the invalidation of a cache line doesn't prevent you from modifying data sitting on the same cache line because of cache coherence. You're goal here is to put each array element on its own cache line so if one element is modified, cache coherence will not bottleneck modifying data because each element in the array is on its own cache line.
===Thread Local Variables===
Wasting memory to put your data on different cache lines is not ideal solution to the False Sharing problem even though it works. There are 2 problems with this solution: 1 you're wasting memory of course and 2 this solution isn't scalable because you aren't always going to know the L1 cache line size. Using variables local to each thread, instead of contiguous array locations reduces the number of times that a thread will write to a cache line that shares data with threads. The benefit to this approach is that you do not have multiple threads writing to the same cache line, invalidating the data and bottlenecking the processes.
<source lang="cpp">
#include <iostream>
}
</source>
[[File:ExecutionSpeedupLocalSpeedupTl.png|800px|center|frame]]
= Intel VTune Amplifier =
<br>
This is just a brief summary of some of the tools available within VTune Amplifier. For more details, please visit [https://software.intel.com/en-us/intel-vtune-amplifier-xe Intel VTune Amplifier website].
= Summary =
In conclusion, keep an eye out for false sharing; its a scalability killer. The general case to watch out for is when you have two objects or fields that are constantly accessed for reading or writing by different threads, at least one of the threads is doing writes, and the objects close enough in memory that they fall on the same cache line. Detecting false sharing isn' t always easy, so make use of CPU monitors and performance analysis tools. But Typical CPU monitors can completely mask memory waiting by regarding it as busy time, so look for code performance analysis tools that measure cycles per instruction (CPI) and/or cache misses. One such tool is Intel VTune Amplifier. You can also use visual studio's Performance Profiler.
<br>
Finally, you can avoid false sharing by reducing the frequency of updates to the falsely shared variables; for example, update local data instead of the shared variable. Also, you can ensure a variable is completely unshared by using padding or aligning data on cache line in such a what that it ensures that no other data precedes or follows a key object in the same cache line.