96
edits
Changes
→Identifying False Sharing
#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]]
According to Amdahl's Law the potential speedup of any application is given by Sn = 1 / ( 1 - P + P/n ). Assuming 95% of our application is parallelizable, Amdahl's law tell's use there is a maximum potential speedup of 3.478 times. This is not the case according to our results. We reach a speedup of 2.275 times the original speed. As you can tell from the graph our code is not scalable and these are results are very underwhelming.
</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 =