On the automation of periodic hard real-time processes: a graph-theoretical approach

Research output: ThesisPhD Thesis - Research UT, graduation UT

Abstract

Summary 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 Vertex- Removing 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 Real-Time 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 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.
LanguageEnglish
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broenink, Johannes F., Supervisor
  • Broersma, Haitze J., Supervisor
Thesis sponsors
Award date6 Jun 2018
Place of PublicationEnschede
Edition1
Print ISBNs978-90-365-4551-8
DOIs
StatePublished - 6 Jun 2018

Fingerprint

Real time control
Automation
Real-time
Graph in graph theory
Switches
Control systems
Vertex of a graph
Multiplication
Processing
Robotics
Time switches
Data storage equipment
Deadline
Switch
Graph Products
Process Control
Binary trees
Specification languages
Graph theory
Associativity

Keywords

  • Process Algebra
  • Graph Theory
  • Synchronised Product
  • Graph Decomposition
  • Periodic Hard Real-Time Systems

Cite this

@phdthesis{199a12888adb43dcae59f10423e92eca,
title = "On the automation of periodic hard real-time processes: a graph-theoretical approach",
abstract = "Summary 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 Vertex- Removing 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 Real-Time 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 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.",
keywords = "Process Algebra, Graph Theory, Synchronised Product, Graph Decomposition, Periodic Hard Real-Time Systems",
author = "Boode, {Antoon Hendrik}",
note = "IDS Ph.D.-Thesis Series No. 18-466",
year = "2018",
month = "6",
day = "6",
doi = "10.3990/1.9789036545518",
language = "English",
isbn = "978-90-365-4551-8",
series = "IDS Ph.D-Thesis Series",
publisher = "University of Twente",
number = "18-466",
edition = "1",
school = "University of Twente",

}

On the automation of periodic hard real-time processes : a graph-theoretical approach. / Boode, Antoon Hendrik.

1 ed. Enschede, 2018. 154 p.

Research output: ThesisPhD Thesis - Research UT, graduation UT

TY - THES

T1 - On the automation of periodic hard real-time processes

T2 - a graph-theoretical approach

AU - Boode,Antoon Hendrik

N1 - IDS Ph.D.-Thesis Series No. 18-466

PY - 2018/6/6

Y1 - 2018/6/6

N2 - Summary 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 Vertex- Removing 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 Real-Time 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 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.

AB - Summary 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 Vertex- Removing 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 Real-Time 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 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.

KW - Process Algebra

KW - Graph Theory

KW - Synchronised Product

KW - Graph Decomposition

KW - Periodic Hard Real-Time Systems

U2 - 10.3990/1.9789036545518

DO - 10.3990/1.9789036545518

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-4551-8

T3 - IDS Ph.D-Thesis Series

CY - Enschede

ER -

Boode AH. On the automation of periodic hard real-time processes: a graph-theoretical approach. 1 ed. Enschede, 2018. 154 p. ( IDS Ph.D-Thesis Series ; 18-466). Available from, DOI: 10.3990/1.9789036545518