Overview
Understanding the difference between blocking and non-blocking execution and under what circumstances to use each is key in developing efficient applications. CLIP makes it easy to use both forms and is especially focused on easy implementation of the more efficient non-blocking execution that is less well catered for by alternative technologies.
What is the Difference Between Blocking and Non-Blocking Execution?
Traditional programs will launch a task and then that task might stop and wait for another task to complete half way through its execution. The problem with this kind of blocking execution is that it causes the executing thread to be stalled, which could mean that there aren't enough active threads to keep all of the cores busy. Alternatively, if another thread is started to resolve the inactive core problem then that incurs additional overhead due to the thread context switching and memory requirements and avoiding huge thread proliferation can be difficult for non-trivial applications.
Non-blocking execution is different because once a task has been launched it does not block. The task runs through to completion and control returns to the scheduler, which then initiates another task. This means that tasks can run continuously, keeping all cores busy unless there is a shortage of available tasks. Provided that the program generates enough tasks it is theoretically possible to maintain 100% CPU utilization on all cores. This is the key benefit of non-blocking execution.
How Does Collection Provide Non-Blocking Execution?
The idea behind non-blocking execution is simple: collect together all of the resources that the task is going to require beforehand and only when they are all available do we schedule it for execution. In order to achieve this, some assumptions must be made about the task code, its inputs and its outputs:
- The maximum number of inputs and outputs must be known
- The variability of number of inputs and outputs should be fairly small
- The task code must not block on devices or O/S calls
If all of these conditions can be satisfied then collection can be used to achieve non-blocking execution.
How is this supported in CLIP?
CLIP uses a nodal object called a collector to wait for all of the inputs and outputs to a method to arrive and then produce an output event that triggers the task code using a method. It is important to note that the collector object is passive (it does not require a thread) and the collection is asynchronous so as soon as the events arrive, the method becomes available to run.
The following example shows a method with two inputs, S1 and S2 and a single output, S3. A collector is used to collect up the inputs and outputs and then the compound event generated when they all arrive is used to trigger the method, Mthd that contains the task code:
Of course, it is not always possible to satisfy all of the conditions required for non-blocking execution and so CLIP supports a form of blocking execution in the cases where it is essential. Blocking execution is achieved through the use of manual connections, which allow you to block mid-task on a CLIP object. You should always try and avoid blocking execution wherever possible because it potentially compromises the CPU utilization and load-balancing characteristics of your application. The most common cases for using blocking execution are dealing with devices and when an unknown number of outputs must be generated by a task.
Why is Collection Sequence Important?
Collection sequence is the order in which each input to the collector is collected and is shown on the diagram using an arrow on the collector's consuming face. The following diagram shows an ordered collector with numbers to show the sequence of the collection marked on each link:
Most of the time collection sequence does not matter but there are a couple of exceptions that you need to be aware of:
- Writes are typically available before reads and so collecting writes first can reduce latency
- Two methods collecting the same two (or more) arbitrated stores but in different orders can end up in a deadly-embrace, deadlocking the circuit
Deadly embraces are discussed in more detail in Avoiding Deadly Embraces.
Implicit Collection
The example below provides an alternative way of collecting inputs and outputs. The double-ended method hides an implicit collector and when translated, a method and collector are generated in its place. This is a short-hand notation that makes it easier to layout circuits with inputs on the left and outputs on the right:
