Execution Graph

One execution graph defines many pipelines

Execution Graph Logo A project that is developing a piece of software, typically keeps the source code in a configuration management system. There is a build that compiles the source code to create a binary. The binary is then subjected to a series of dynamic tests, like unit, smoke, system, endurance, compliance and many more other tests. Some projects also extract API or other documentation from the source code, run static code analysis and verify translations. Binaries are often packaged in a format that makes them easy to distribute and deploy. And, not to forget, everything needs to be reported and documented. All these operations are executed as part of the software production line.

But there is a lot more to do: test drivers, stubs, data sets and special tools need to be developed and tested (!); external tools need to be validated; the system under test (SUT) and other equipment must be programmed; etc.

It is not an easy task to manage and keep track of all these activities. Automation will help here.

Common solutions using pipelines

Nowadays, common solutions create pipelines to implement CI/CD. Every pipeline creates a dedicated execution flow of steps or tasks through a set of activities as described above to achieve a certain goal. Now, every single goal requires its own pipeline. As many goals exist, the number of pipelines can become large.

Note: both the relations between the tasks and the way of executing the task, are part of the pipeline.

It is not evident that every individual step in a pipeline can be reused in other pipelines due to variations in the execution environment. This results in steps or tasks that look like others but are not equal at all, resulting eventually in getting caught in the maintenance trap.

Going beyond: the Execution Graph

The Execution Graph is a new graphical modelling language that describes all the processes required in a production line, in one or more directed graphs. See graph theory for the theoretical background. The nodes of a graph represent the smallest pieces of work (the so called tasks) and the edges the intermediate products (called products).

An elementary process step is a task, together with its input and output products.

In an execution graph, the tasks are represented by ovals and the products by rectangular boxes. The dependencies between the tasks and products are depicted by arrows.

This visualization shows one process step together with the products it will consume and produce:

An elementary process step

In an execution graph the dependencies between tasks are defined too, i.e. the output of one task can be the input of another. In other words, one task produces a product while an other consumes it. A certain task may consume and produce multiple products.

A pipeline can be described just by gathering all necessary elementary process steps in one graph.

A pipeline is a combination of elementary process steps.

A complete factory is described by combining all pipelines in one execution graph.

An execution graph is a combination of pipelines.

The controller, orchestrating the execution of the pipelines, determines at run-time the execution flow of individual tasks, by using the execution graph. A task is 'ready to run' if all the inputs it depends on, are produced.

Note: the relations between the tasks and the way of executing the tasks, are decoupled.

An example: a coffee maker

A well known process captured

In this example the processes of a luxurious coffee maker are captured in an execution graph.


Now, we encounter one of the biggest advantages of using the Execution Graph. At a certain moment in time the factory controller will hold a number of tasks which are able to run. These tasks may belong to one or more pipelines, it doesn't matter. When enough, possible distributed resources are available, the controller can dispatch these tasks to the resources for execution. Without designing in concurrency, you get it for free!

Less maintenance

Just by defining an execution graph, many pipelines can be created by selecting a set of tasks and products producing some kind of target product. The execution graph defines the relation between these elements and is relevant at run-time only. If the execution graph changes, the pipelines change along.

This means that the many old fashioned pipelines don't exist anymore and therefore don't require maintenance. By maintaining the execution graph as a whole all derived pipelines are maintained as well. This is a big advantage when pipelines share tasks.

Using the Execution Graph

Until now, the execution graph has been useful to design and visualise your factory. It serves as a blue print for the implementation phase and even can be of help with your planning.

For the actual implementation of your factory controller you can choose from a variety of (open source) tools but we advise you to use SoftFab since it understands the Execution Graph. The graph describes the execution model and is one of the inputs to SoftFab.

By using SoftFab you lower the maintenance effort of your pipelines and get your tasks faster done because of the implicit concurrent execution.

Building and testing openMSX

A real life example

The open source project openMSX uses SoftFab to run their builds and tests. Taking a look at their graphs shows the strength of the Execution Graph.