Abstract
Summary In certain singlecore monoprocessor 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 endtoend 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 processalgebraic specification language Communicating Sequential Processes (CSP), we are able to reduce the endtoend 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 realtime processes executing on a singlecore monoprocessor.
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 Vertex Removing Synchronised Product (VRSP), the Dot VertexRemoving Synchronised Product (DVRSP) and the Extended Dot VertexRemoving 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 endtoend 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 (represent ing periodic realtime 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 contextswitch 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 RealTime 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 processorcoprocessor combination, the endtoend 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.
Furthermore, the endtoend 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 processalgebraic specification language Communicating Sequential Processes (CSP), we are able to reduce the endtoend 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 realtime processes executing on a singlecore monoprocessor.
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 Vertex Removing Synchronised Product (VRSP), the Dot VertexRemoving Synchronised Product (DVRSP) and the Extended Dot VertexRemoving 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 endtoend 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 (represent ing periodic realtime 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 contextswitch 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 RealTime 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 processorcoprocessor combination, the endtoend 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.
Original language  English 

Qualification  Doctor of Philosophy 
Awarding Institution 

Supervisors/Advisors 

Thesis sponsors  
Award date  6 Jun 2018 
Place of Publication  Enschede 
Edition  1 
Publisher  
Print ISBNs  9789036545518 
DOIs  
Publication status  Published  6 Jun 2018 
Fingerprint
Keywords
 Process algebra
 Graph theory
 Synchronised product
 Graph decomposition
 Periodic hard realtime systems
Cite this
Boode, A. H. (2018). On the automation of periodic hard realtime processes: a graphtheoretical approach. (1 ed.). Enschede: University of Twente. https://doi.org/10.3990/1.9789036545518