las3_pub / predictable_parallel_patterns

We still see very sporadic crashes, however the current version is at least a starting point for refactoring and debugging. Next steps have to be to re-enable tooling support (i.e. add code to let sanitizers do their work).

The current version has race conditions and is hard to debug (especially because of the fibers, if a wrong thread executes on a fiber we get segfalts very fast). To combat this mess we now refactor the code bit by bit while also adding tests where it can be done with reasonably effort).

The project is currently really messy and there are sporadic sigsevs. This indicates that we still have a race in our code. Thread Sanitizer does not work with our current implementation, as it needs annotations for fibers.

The next step is to clean up the project and maybe add thread sanitizer support to our fiber implementation. This should help finding the remaining bugs.

The idea is to exclude as many sources as possible that could lead to issues with contention and cache misses. After some experimentation, we think that hyperthreading is simply not working very well with our kind of workload. In the future we might simply test on other hardware.

This version runs through our initial fft and fib tests. However, it is not tested further in any way. Additionally, we added a locking deque, potentially hurting performance and moving away from our initial goal.

The main issue seems to still be the fact that we have a lock free protocol where a steal can be pending. We plan to remove this fact next by introducing a protocol that works on a single atomic update.

The start_chain property does not make sense, as chains are purely 'virtual', i.e. they only fully exist when walking through the computation (by patching them on important events). We initially added the property as a helper for better runtime and simpler implementation, but we think without it we will not get as much inconsistency in the runtime state. Performance can be 're-added' later on.

It is still not working, however we now have no more redundant code, making debugging it simpler.

This showcases the expected performance when a task executes a sub-tree without inference from other threads. We target to stay about 6x slower than a normal function call.

We changed how the memory is allocated from passing char* buffers to then store objects into to creating 'fat objects' for all scheduler state. This eases development for us, as we can make changes to data structures without too much effort (e.g. add a second array to manage tasks if required).

This allows us to more easily handle them and makes their interface closer to std::thread.

The scheduler yields if it failed to steal any work due to the task
lists being empty. This should improve performance on multiprogrammed
systems, as it potentially makes room for other worker threads which
still have work to perform.

This allows the stack and deque class to use the same offset, making it work better with each other.

Threads must be joined on scheduler termination and tasks must be pushed onto the stack to allow better memory management.

Please note that this does currently not execute, but only removed the 'old aspecs'. We are still missing launching the root fork_join task.

Use only placement new on pre-allocated memory. This makes sure that we have to have no assumptions on the inital state of the memory region.

This lead to some bug-fixes that covered move constructors not correctly assigning memory. We might clean this up further by only allowing in place creation of these types (placement new).

The current solution is not clean, but allows us to change error handling later on without missing any point in the programm where we would want to use it.

This means that high level tasks can be stolen and lays the groundwork for implementing different tasks like classic work stealing.

Right now no work can be spawned, we simply have a proove of concept that we start up each thread, work for the master to finish and then synchronize back to the main thread.