Changes

In an ideal world, the CPU would have lightning-fast access to all data on your machine at any given time to maximize the power and speed of modern-day CPUs. In reality, there are limitations and trade-offs when balancing speed, storage size, locationcapacity, and cost. To compromise, a computer utilizes many types of memory. To name the important ones in the hierarchy, we have secondary memory like hard drives and SSDs which can permanently hold vast quantities of data but are slow. Next is Dynamic Random Access Memory(DRAM) which is much smaller, faster, and volatile. Last, we have the cache or Static Random Access Memory(SRAM), which is extremely fast, but even smaller and more expensive.

Near the bottom, we have secondary memory like hard drives, flash drives and SSDs which can permanently hold vast quantities of data, but are relatively slow. Hard drives in particular have mechanical parts that must physically move. If the CPU solely relied on getting data from secondary this memorytype, the slow access speed of the storage device speeds would become a massive bottleneck in computation time. There would be huge gaps The CPU will spend a majority of time where the CPU sits around doing nothing idling waiting for data. To the end user, your machine would appear to be extremely sluggish and non-responsive.

At the same timeNext is Dynamic Random Access Memory(DRAM) which use capacitors, only small amounts piece of transistors and electricity to store data. They require constant refreshing with electricity to store data making them volatile as their data disappears when power is needed at a given momentcut. Even if you brought everything in from memoryDRAM is more expensive, most of it will be unusedbut smaller and faster. Utilizing However, this is still not fast enough for the hierarchy CPU. Last, we have Static Random Access Memory(SRAM), which is extremely fast, but even smaller and more expensive. This type of memory storage, the most relevant data can be siphoned from secondary memory ahead of time and stored is what is used in the cache and RAM.  When searching for it needs data, the CPU can grab it from looks in the cachefirst. If it is there, it is a cache hit. If it is not there, it is a cache miss, then it looks moves and the CPU must search main memory or even further down the hierarchy until it finds it. Minimizing the number of cache misses ensures the CPU has a steady flow of data it can quickly retrieve and compute. The cache operates on locality of reference which refers to the tendency of programs to access the same set of memory locations repeatedly over a short period of time. From here, there are two major types. Temporal locality is when one memory location is accessed, it will likely be accessed again in the near future. Spatial locality means if one memory locations is accessed, nearby memory locations will likely be needed as well. Using these principles and complex algorithms, data is brought into the cache ahead of time to minimize the number of cache misses.

Each processor has their own local cache. When data is needed, a fixed block blocks of memory is are transferred to the cache; this these block is are known as a cache linelines.

The answer is we need cache coherence. '''Cache coherence''' is defined as the '''uniformity of shared resource data that ends up stored in multiple local caches'''. In other words, we must keep all the local caches synchronized. The challenge of doing so is known as the Cache Coherence Problemcache coherence problem. To solve this problem, multi-processor systems rely on cache coherence protocols to manage and maintain the cache. While the details of these protocols are beyond the scope of this assignment, more information on cache coherence protocols can be found here: https://en.wikipedia.org/wiki/Cache_coherency_protocols_(examples).

False sharing occurs when multiple processors modify data that resides on the same cache line. When this data is written back to memory, the shared cache lines are marked as invalid or dirty. Processors must fetch an updated copy introducing from memory resulting in significant delays due to memory access speeds. As you increase the number of processorsIf false sharing is not minimized, this issue quickly spirals out of control as there is an when increasing chance the cache line is invalidnumber of processors.

<br><br><br><br><br>

We were asked to multi-thread a serial version of a simple algorithm that calculated PI by integrating 1/(1 + x^2). The serial version utilized a scalar sum variable to accumulate the calculations. For our naïve attempt, we identified a potential issue with using a scalar sum in a multi-threaded program. We have no direct control on the order a thread finishes their assigned work and leaving it up to chance resulted in a race condition. This is not good, but we still need a global variable, so the threads can return their values. To get around this we came up with the idea to change sum to an array. Now, each thread can store their calculations in the array indexed by their individual thread ids id instead of competing against each other to update the scalar sum.

[[File:naive_implementation.png|600px500px|thumb|Execution time of naive implementation without any optimization levels (Od).]] The algorithm calculates the correct answer, but the performance is absolutely terrible. The reason is that an int array is a contiguous block of memory with each integer taking up 4 bytes. Assuming a 64 byte cache line, our entire array only takes up half of the cache opening up the possibility for multiple threads to share the same cache line resulting in false sharing. Although there were cases where higher thread count produced better results, there were many cases that performed worse than a single thread. This is due to the scheduling of thread execution that is out of the programmer's hands. It is possible that the selected schedule managed to minimize the frequency of false sharing giving better performance. However, this is extremely unreliable, so we need a better solution to false sharing.                 

Assuming a 64 byte cache line, what if each element in the array was the only piece of data in the cache line for each thread? [[File:naive_vs_padded_arr.png|700px600px|thumb|<br>Array comparison between naïve and padded implementation. Colored blocks represent index handled by individual threads. Grey blocks represent empty space.]]Assuming a 64 byte cache line, what if each element in the array was the only piece of data in the cache line for each thread?

While our the idea works, there were several issues that prevented it from being an ideal solution: [[File:padded_implementation.png|600px500px|thumb|Execution time of padded implementation without optimization (Od).]]

'''- tons of wasted memory'''

For every 4 bytes for storing a thread's calculation, 60 bytes is empty paddingwhich grows for every new thread that is added. This empty space rapidly increases as the number of threads increasesEven though it is not a lot, it is still very inefficient.

'''- the cache line only contains one piece of data with the rest being completely emptypadding'''

This is incredibly inefficient. The whole point of the cache is to improve performance by contain relevant data We want to minimize cache misses. In practice, but by hogging valuable cache space this reduces the scheduler will be juggling many threads with their own data that may or may not be related to this program. By padding out effectiveness of the cache line. If we had a more complex program, we are hogging this valuable space and are forcing could have tons of other data the thread could have fit on the same cache misses to occurline.

* OpenMP. (2013, December 6). ''Introduction to OpenMP: 06 Discussion 2 '' [Video]. Youtube. https://www.youtube.com/watch?v=OuzYICZUthM* OpenMP. (2013, December 6). ''Introduction to OpenMP: 08 Discussion 3 '' [Video]. YouTube. https://www.youtube.com/watch?v=pLa972Rgl1I