[Technical] Basic knowledge in concurrency with a centralized clock

Basic knowledge in concurrency with a centralized clock - Printable Version

+- Save-Point (https://www.save-point.org)
+-- Forum: Games Development (https://www.save-point.org/forum-4.html)
+--- Forum: Tutorials (https://www.save-point.org/forum-19.html)
+--- Thread:

Basic knowledge in concurrency with a centralized clock (/thread-5849.html)

Basic knowledge in concurrency with a centralized clock - DoubleX - 07-05-2016

Those not knowing what concurrency is can check this :P

As I only know the fundamental concepts, I can only share the basics here. You're still assumed to have a basic knowledge on graphs though :)

As a centralized clock is used to process all components, there can only be 1 decided execution sequence per frame, meaning all those connected graph will be connected simple digraphs.
To keep concurrency easier, simpler and more straightforward, its focus will be solely on connected simple digraphs only involving reading states from a component and writing states to a component via atomic operations exclusively.
If an arrow is directed from component A to component B, then component A is writing some states of component B using some states read from component A at that moment.
Also, the whole concurrency graphs will be entirely generated and then immediately executed per frame, with the aid of the below additional rule set operated as a whole per frame as long as there are still at least 1 vertex in that frame:
1. Only vertexes with the min indegree or arrows directed to those vertexes right before those arrows are removed can be the 1st one to be executed in the execution sequence.
2. Executing a vertex once means executing exactly 1 arrow directed from that vertex once.
3. An arrow will be removed right after it's executed once.
4. A vertex will be removed from the graph right after it becomes disconnected.
5. The execution sequence will be finished when the graph has no more vertexes.
Now there are 3 keys factors affecting concurrency - whether the graph's acyclic/cyclic, whether the max indegree of the graph's 1/greater than 1, and whether the max outdegree of the graph's 1/greater than 1.
This leads to 8 cases to be considered:

Acyclic connected simple digraphs with max indegree/outdegree 1
This is the easiest, simplest and most straightforward case among all the 8.
The concurrency graph begins from something like this:

Code:
Component A1 -> Component A2 -> Component A3 -> ... -> Component An

The execution sequence is as follows:
1. As only Component A1 has the min indegree(0 in this case) and no arrows are executed yet, Component A1 will be executed once(Rule 1).
2. As only 1 arrow's directed from Component A1, it'll be executed once(Rule 2)
3. That arrow will be removed right after it's executed once(Rule 3).
4. As Component A1 becomes disconnected, it'll be removed from the graph(Rule 4).
Now that graph becomes this in the same frame:

Code:
Component A2 -> Component A3 -> Component A4 -> ... -> Component An

It's crystal clear that the above 4 setups will be repeated until Component An is removed from the graph.
As that graph has no more vertexes, the execution sequence is now finished(Rule 5).
It's crystal clear and obvious that there are absolutely no concurrency issues in this case at all as there are only 1 possible ordering.

Acyclic connected simple digraphs with max indegree 1
To further simplify this case, let's restrict it to be a specific example having max outdegree 2.
The concurrency graph begins from something like this:

Code:
Component A -> Component E -> Component G

     |              |

     |              V

     V         Component F

Component B -> Component D

     |

     V

Component C

The execution sequence is as follows:
1. As only Component A has the min indegree(0 in this case) and no arrows are executed yet, Component A will be executed once(Rule 1).
2. An arrow's directed from Component A, it'll be executed once(Rule 2)
3. That arrow will be removed right after it's executed once(Rule 3).
Now that graph becomes this in the same frame:

Code:
Component A -> Component E -> Component G

                    |

                    V

               Component F

Component B -> Component D

     |

     V

Component C

Note that there are now 2 connected simple digraphs and that having Component B is an acyclic connected simple digraphs with max indegree/outdegree 1.
Concentrating the other connected simple digraphs:

Code:
Component A -> Component E -> Component G

                    |

                    V

               Component F

Repeating the above 3 steps will lead to Component A being removed, as it's now disconnected from that graph(Rule 4).
Now that graph becomes this in the same frame:

Code:
Component E -> Component G

     |

     V

Component F

Repeating all the above, the execution sequence will eventually be finished due to the graphs having no more vertexes(Rule 5).
It's crystal clear and obvious that there are absolutely no concurrency issues in this case at all as the ordering certainly doesn't change any read nor write result.

Acyclic connected simple digraphs with max outdegree 1
To further simplify this case, let's restrict it to be a specific example having max indegree 2.
The concurrency graph begins from something like this:

Code:
Component A Component B

     |           |

     V           |

Component C <----+

As both Component A and B have the min indegree(0 in this case), either of them can be executed first(Rule 1).
Suppose Component A, B and C have states a, b and c respectively.
Assume that:
1. Using state a to write the state of Component C previously being state c will change it to ca.
2. Using state b to write the state of Component C previously being state c will change it to cb.
3. Using state a to write the state of Component C previously being state cb will change it to cba.
4. Using state b to write the state of Component C previously being state ca will change it to cab.
If Component A is executed first followed by executing Component B, the final state of Component C will be cab.
If Component B is executed first followed by executing Component A, the final state of Component C will be cba.
Now concurrency becomes a nontrivial issue, as the result of Component C depends on which of them will be executed first.
1 way to solve this is to implement some deterministic rules deciding which components will always run first for the exact same situation.

Acyclic connected simple digraphs
To further simplify this case, let's restrict it to be a specific example having max indegree/outdegree 2.
The concurrency graph begins from something like this:

Code:
Component A -> Component B

     |              |

     V              |

Component C <-------+

There are 3 possible choices on the execution sequence:
1. Component A -> Component B, Component A -> Component C, Component B -> Component C
2. Component A -> Component B, Component B -> Component C, Component A -> Component C
3. Component A -> Component C, Component A -> Component B, Component B -> Component C
Suppose Component A, B and C have states a, b and c respectively.
Assume that:
1. Using state a to write the state of Component B previously being state b will change it to ba.
2. Using state a to write the state of Component C previously being state c will change it to ca.
3. Using state ba to write the state of Component C previously being state c will change it to cba.
4. Using state ba to write the state of Component C previously being state ca will change it to caba.
5. Using state a to write the state of Component C previously being state cba will change it to cbaa.
Choice 1, 2 and 3 will cause Component C to have state caba, cbaa and caba respectively.
Note that both choice 1 and 3 will lead to the same result. It's because right before Component B -> Component C, the Component B will always have the state ba, meaning the ordering between Component A -> Component B and Component A -> Component C doesn't matter at all.

Connected simple digraphs with max indegree/outdegree 1
The concurrency graph can begin from something like this:

Code:
Component A1 -> Component A2 -> Component A3 -> ... -> Component An

     ^                                                      |

     |                                                      |

     +------------------------------------------------------+

As all Component Ai(1 <= i <= n) have the min indegree(1 in this case), either of them can be executed first(Rule 1).
It means there are n choices on the execution sequence.
If Component Ai is the 1st one to be executed, that graph will become this at the same frame after Component Ai has executed once:

Code:
Component Ai + 1 -> ... -> Component An -> Component A1 -> ... -> Component Ai

Suppose Component Ai has state ai and using state x to write the state of a component previously being state y will change it to yx.
If Component Ai is executed first, the state of Component Aj(1 <= j <= n) will be:
1. aja(j - 1)a(j - 2)...ai for j > i
2. aja(j - 1)a(j - 2)...a1ana(n - 1)a(n - 2)...ai for j <= i
Clearly the state of Component Aj changes as i changes.
1 way to solve this is to cache the state of each component in all cyclic connected simple directed subgraphs right before executing that graph.
Now if an arrow is directed from component A to component B, then component A is writing some states of component B using the cached state of Component A.
So if Component Ai is executed first, the state of Component Aj(1 <= j <= n) will be:
1. aja(j - 1) for a <> 1
2. a1an for for = 1
It's because the cached state of Aj will always be aj in the same frame.
Therefore the state of Component Aj becomes completely independent of i, meaning the choice on the execution sequence no longer matters.
The essence of this trick is to make cyclic connected simple digraphs effectively behave like acyclic connected simple digraphs.

Connected simple digraphs with max indegree 1
To further simplify this case, let's restrict it to be a specific example having max outdegree 2.
The concurrency graph begins from something like this:

Code:
Component A1 -> Component A2 -> Component A3 -> ... -> Component An -> Component B

     ^                                                      |

     |                                                      |

     +------------------------------------------------------+

If the state of all Component Ai(1 <= i <= n) are cached right before executing that graph, the choice on the execution sequence won't matter anymore, as it's effectively the same case as acyclic connected simple digraphs with max indegree 1.

Connected simple digraphs with max outdegree 1
To further simplify this case, let's restrict it to be a specific example having max indegree 2.
The concurrency graph begins from something like this:

Code:
Component A1 -> Component A2 -> Component A3 -> ... -> Component An <- Component B

     ^                                                      |

     |                                                      |

     +------------------------------------------------------+

If the state of all Component Ai(1 <= i <= n) are cached right before executing that graph, the choice on the execution sequence should be decided by some deterministic rules always giving the same result for the exact same situation, as it's effectively the same case as acyclic connected simple digraphs with max outdegree 1.

Connected simple digraphs
This is the most complicated, convoluted and toughest case among all the 8.
To further simplify this case, let's restrict it to be a specific example instead of using a general form.
The concurrency graph begins from something like this:

Code:
+-------------------------------------------------------------------------------+

|        +------------------------------------------------------+               |

|        |                                                      |               |

|        V                                                      |               |

+-> Component B1 -> Component B2 -> Component B3 -> ... -> Component Bn -> Component D

|        |               |               |                      |               ^

|        V               V               V                      V               |

+-> Component A1 -> Component A2 -> Component A3 -> ... -> Component An <- Component C

|        ^                                                      |               |

|        |                                                      |               |

|        +------------------------------------------------------+               |

+-------------------------------------------------------------------------------+

If the state of all Component Ai and Bi(1 <= i <= n) are cached right before executing that graph, that graph will effectively behave as a acyclic connected simple digraphs.
Nevertheless, it's better to just cache the states of all components before executing the graph, as sometimes the graph can still have rather troublesome concurrency issues even after solving all the cyclic parts.

Summary
To solve concurrency issues using a centralized clock:
1. For connected simple digraphs with max indegree greater than 1, some deterministic rules should be implemented to be always making the same choice on the execution sequence on the exact same situation.
2. For cyclic connected simple digraphs, the state of each component in all cyclic connected simple directed subgraphs should be cached right before executing the original graph. When component A is writing some states to component B, the cached state of component A instead of the state of component A at that moment should be read and used.
3. To play safe, consider just caching the states of all components before executing the graph, as sometimes the graph can still have rather troublesome concurrency issues even after solving all the cyclic parts.

For those completely mastered concurrency, feel free to correct me if I've made any mistake :D