on the automation of periodic hard real-time processes - a graph-theoretical approach
Ton Boode is a PhD student in the research group Robotics and Mechatronics. His supervisors are dr.ir. J.F. Broenink and prof.dr.ir. H.J. Broersma from the faculty of Electrical Engineering, Mathematics and Computer Science (EEMCS).
In certain single-core mono-processor configurations, e.g. embedded control systems like robotic applications comprising many short processes, process context switches may consume a considerable amount of the available processing power. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application.
Furthermore, the end-to-end processing time suffers from the idle time of the processor, because, for example, processes have to wait for controllers executing some task. By relaxing the rules for synchronous communication via channels in the process-algebraic specification language Communicating Sequential Processes (CSP), we are able to reduce the end-to-end processing time.
As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these applications to periodic real-time processes executing on a single-core mono-processor.
Because these processes can be represented by finite, deterministic, labelled, acyclic, directed multigraphs, we address these two problems using graph theory. We introduce a model of computation that, based on these graphs, shows an improved performance when we multiply these graphs. This multiplication is based on a synchronised graph product for which we have developed three versions; the VertexRemoving Synchronised Product (VRSP), the Dot Vertex-Removing Synchronised
Product (DVRSP) and the Extended Dot Vertex-Removing Synchronised Product (EVRSP). The VRSP is solely developed to reduce the number of context switches. The DVRSP and the EVRSP are an extension of the VRSP and deal with the reduction of the end-to-end execution time of a set of Periodic Hard RealTime Control Processes (PHRCPs). Of course, these multiplications preserve the behaviour of the PHRCPs represented by these graphs.
Our research is based on three research questions, where we define the various graph products, prove that these products will give a performance gain (under certain conditions) and elaborate the numerical and combinatorial aspects of these graph products.
We introduce the notion of a consistent and an inconsistent set of graphs (representing periodic real-time processes). Consistency is based on the contraction of graphs together with the sink and the source of the Cartesian Product of these graphs, where the sink and the source have to be invariant over the graph multiplication by the synchronised product, VRSP. We show that consistency and associativity of the VRSP are closely related in the sense that a set of graphs under the VRSP is associative if all pairs of graphs in the set of graphs and their products under the VRSP are consistent.
Whether or not a significant performance gain is achieved by combining processes depends on the ratio of the context-switch time and the calculation time of the processes itself; clearly, this depends on the type of hardware and operating system used. But still, if the Periodic Hard Real-Time Control System (PHRCS) does not fulfil the requirements with respect to the deadline of its PHRCPs, calculating all possible products of two or more graphs may produce a set of graphs for which the processes they represent comprise a PHRCS that will fulfil the requirements with respect to deadline and memory occupancy.
To increase the chance that such a PHRCS exists, we develop two theorems that decompose the graphs into smaller graphs. Decomposition of the graphs gives a new set of graphs from which the VRSP gives outcomes that were not available in the original set of graphs. It could well be that these new outcomes contain a solution for the PHRCPs, whereas the original set of graphs did not contain a solution.
We show that the number of possible combinations of multiplications of graphs by the VRSP follows the Bell number (Bn) series if the multiplication is associative. Therefore we develop heuristics that calculate a set of multiplied graphs that may fulfil the requirements with respect to deadline and memory occupancy.
To emphasize the necessity of associativity, we study the multiplication by the VRSP when the multiplication is not associative. We give proof that this multiplication follows the Bessel number (B˜n) series by calculating the number of different forests, where a set of multiplied graphs under the VRSP is represented by a binary tree. The numbers in the Bessel number series are a magnitude larger than the numbers in the Bell number series and this is, as for consistency, a reason
why associativity is necessary.
All in all, we have five advantages provided by our graph theoretical approach:
- the length of the longest paths of the graphs is reduced, thereby reducing the number of context switches of the processes represented by these graphs,
- in a distributed computing system, for example, a processor-coprocessor combination, the end-to-end processing time of processes can be reduced.
- it eases the design by taking away the burden of separating the writing actions and reading actions in time, which eliminates the necessity of the modelling of a buffer,
- it gives more flexibility by indexing the reading actions, - it allows multiple write actions to the same channel.
- it allows multiple write actions to the same channel.
