las3_pub / predictable_parallel_patterns

The rationale to do an custom implementation is that the existing solutions are quite a bit slower and/or require more memory.

We implement a minimal concepts of user level threads. This shows the minimum requirements for our 'staggered' stack implementation: we need to be able to switch to a new stack and allow someone else to continue the calling function right before the switch.

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.

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.

Everything so far is untested. We only made sure tha fast path still seems to function correctly. Next up is writing tests for both the fast and slow path to then introduce the slow path. After that we can look at performance optimizations.

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.

This makes the programming model a full dataflow implementation, as it allows for branching and recursion.

Recursion works by using a function node, calling the graph again. We separated an graph invocation form an function invocation within an graph, making the graph only handle one concern.

We separated the structure (input-output flow) from the rest of the architecture and reworked some template programming to have better access to the types required at compile time.

The data can now flow into a graph, follow its path on inptus/outputs and be fetched from the graph after execution.
Currently graphs are executed synchronous.

We need some tricks in template programming to have a clean user facing API while internally using our classes with more capabilities.

This is the base building block for creating the actual dataflow functions and networks, as their main functionality is having data flow through connected nodes.

Now all algorithms are used without the parallel pre-/suffix and the for_each method has an specialization for integer ranges.

We do this to properly separate the cache alginment logic in the next step, allowing us to port all cache aligned objects without worrying about portability.

There are serval ways we could optimize the calls, but for now this should be enough for first tests.

Seperate library from other parts of project (samples, playground, testing, ...). We still are in one 'toplevel' cmake project, so we can for exmaple compile everything (library and playground) in debug mode, for simple development.