SAM
From SoOS
Speculative Access to Memory
Contents |
[edit] What is SAM?
Speculative Access to Memory (SAM) is a library that allows programmers to create threads that allow to memory regions (read and/or write) speculatively. This means that the read data is not validated until the system is sure that all dependencies have been resolved, in case a dependency is detected then the thread that is accessing speculatively is restored back to a previous "safe" status. As for speculative writing, if a conflict is detected, then the written memory is not committed and shared among the other threads.
[edit] Intro
Computing industry relied on increasing the clock frequency and on uniprocessor architectural enhancements to improve performance. The situation has changed nowadays, small architectural improvements continue, but power an thermal issues have made the approach of increasing clock frequency non feasible anymore. Semiconductor fabrics continue developing the manufacturing technology and according to the still valid Moore's law, the number of transistor per unit area double every few months. Processors designers use the additional transistor density to place multiple cores in the same die.
This creates a situation in which only multi-threaded applications will take advantage of the new available resources and increase performance. To be able to produce parallel programs is the main concern of the new multicore era.
Many applications exhibit irregular access to memory, a complex control flow and dynamic loop limits. Normal code parallelization and optimization need to take a pessimistic approach to guarantee correctness of execution due to data and control dependencies. Being able to resolve and remove data dependencies in run-time can dramatically improve parallelization.
SAM can potentially widen the scope of single threaded applications that can be parallelized by resolving data dependencies at run-time that otherwise would prevent parallelism from being extracted. SAM is a parallelization technique that is applied to regions of code that might contain a great amount of parallelism but cannot be statically proven to preserve the sequential behaviour under parallel execution. Speculative worker threads execute code out of the sequential order even when these may contain a true data dependencies.
The master thread keeps the correct sequence of state and control flow. While the speculative worker threads, may consume and produce "dirty" values, that is the reason it is necessary to track the inter threads dependencies and memory accesses to revert to a safe point and restart the computation when a dependency violation happens, this is known as a flash back recovery.
To obtain correct execution threads merge their memory changes into the global non-speculative memory space when it can be proven that no dependency violation was generated. The commit is controlled by the non-speculative master thread and that is the reason why they are usually serialized, simulating the behaviour of the sequential program. This can limit the scalability in the number of processors contributing to speed-up.