Tom Herbert, SiPanda CTO, August5, 2024.
Previously, we discussed the dependencies synchronization mechanism and the unidirectional property that implies that deadlock is impossible with dependencies. We also looked at threads and thread sets and how they can be employed for vertical and horizontal parallelism. This week, we tie everything together. Dependencies provide synchronization between threads, both for those that are running in horizontal or vertical parallelism. The key is dependency resolution. The below diagram illustrates dependency resolution in threads and thread sets.
Example of dependencies in thread and thread sets. This example shows four thread sets running in horizontal parallelism. There are two dependencies. The red dependency is “IP layer valid” and is used to signal the transport layer thread that the IP network layer is validated so changes can be committed to the Protocol Control Block. The blue dependency is the “TCP in order” dependency and is used to ensure that the TCP critical regions are executed in order of packets being received. The “IP layer valid” is a non-propagated dependency, each thread set has its own instance independent of other thread sets; whereas the “TCP in order” dependency is a propagated dependency, it is used to synchronize processing in different thread sets. The blue and red arrows show the flow of dependency resolution.
Dependency Resolution– or Dependency Revolution? :-)
When a thread resolves a dependency, downstream threads in the thread set are informed of the dependency resolution and execution can proceed through wait points for the dependency. This is done by propagating a resolution signal to downstream threads (all threads are ordered and maintained in an ordered list).
A resolution signal propagates until one of the following conditions are met:
The end of the ordered list for the thread set is reached
A thread is encountered that blocks, that is it must resolve, the same dependency being resolved
A thread is encountered that has already resolved the same dependency
The diagram below shows dependency resolution in action.
Example of dependency resolution. Line A shows the state of dependencies before execution commences. Line B shows the initial execution allowed in the four stages-- green areas represent portions of the code path that have no dependencies and can run in parallel from the start. In Line C, Thread 1 resolves the circle dependency-- at this point the blue section in Thread 2 can now run. In Line D, Thread 2 resolves the circle dependency-- at this point the blue section in Thread 4 can run; although the circle dependency is now resolved for Thread 3, it cannot proceed since it is still waiting on the diamond dependency. Finally, in Line E Thread 2 resolves the diamond dependency so that the red portions of Thread 3 and Thread 4 can now run.
Watchers, waiters, and, blockers (“Next in line please!”)
With respect to a dependency, a thread may be a watcher, blocker, or waiter. A watcher is a thread that is interested in a dependency and may wait on it. A waiter is a thread actively waiting on a dependency to be resolved; while it’s waiting the thread is blocked and cannot proceed until the dependency is resolved. A blocker is a thread that blocks a dependency; the thread must resolve the dependency before the resolution signal is propagated to downstream threads. The diagram below shows processing of blockers and waiters.
Example of dependency watchers, blockers, and waiters. The diagram shows the list of blocker and watcher threads for a dependency. Once a blocker has resolved a dependency, it is removed from the list of blockers for the dependency. A watcher becomes a waiter when it is actively waiting on a dependency (waiters are not shown). The rows, labeled A to D, provide points in the timeline for discussion.
In the initial state, Line A, there are three blockers and three watchers: Thread 10 and Thread 17 are blockers but not watchers, Thread 13 and Thread 19 are watchers but not blockers, and Thread 12 is both a watcher and a blocker. In Line B, Thread 17 resolves the dependency. The resolution signal is propagated to Thread 19 and then stops since the end of the ordered list is reached. Note that Thread 17 is not a watcher so that it is effectively creating a new independent instance of the dependency. In Line C, Thread 10 resolves the dependency. The resolution signal is propagated to Thread 12, but stops since Thread 12 is a blocker. Subsequently in Line D, Thread 12 resolves the dependency. The resolution signal is propagated to Threads 13 and 17, but stops there since the dependency is already resolved for Thread 19.
Inter thread set dependencies (Passing the baton!)
Dependency resolution may be propagated from one thread set to another in the ordered list of thread sets. Dependencies that can be propagated between thread sets are called propagated dependencies. With regards to dependency resolution amongst threads in a thread set, propagated dependencies are indistinguishable from non-propagated dependencies.
Propagated dependencies that have been resolved and are not blocked by the last thread of a closed thread set may be resolved in the next thread set in the ordered list. Resolving a dependency in the next thread set is done by propagating a dependency resolution signal starting from the first thread in the next thread set. If a dependency resolution is propagated between thread sets and the resolution signal reaches the last thread in the following thread set, then the dependency resolution may be further propagated to the “next next” thread set.
What’s next
The properties of dependencies lend themselves to very elegant and efficient implementation. We'll talk about that in a future blog. One teaser I’ll mention is that the processing for dependency resolution can be performed without a loop– a simple set of boolean operations on bitmaps is sufficient. Stay tuned…
SiPanda
SiPanda was created to rethink the network datapath and bring both flexibility and wire-speed performance at scale to networking infrastructure. The SiPanda architecture enables data center infrastructure operators and application architects to build solutions for cloud service providers to edge compute (5G) that don’t require the compromises inherent in today’s network solutions. For more information, please visit www.sipanda.io. If you want to find out more about PANDA, you can email us at panda@sipanda.io. IP described here is covered by patent USPTO 12,026,546 and other patents pending.
Comments