Performance of periodic real-time processes: a vertex-removing synchronised graph product

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

20 Downloads (Pure)

Abstract

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. For this reason it can be advantageous to combine processes, to reduce the number of context switches. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these configurations to periodic real-time processes executing on a single-core mono-processor. These processes can be represented by finite directed acyclic labelled multi-graphs. The vertex-removing synchronised product of such graphs gives graphs that represent processes which have less context switches. To reduce the memory occupancy, the vertex-removing synchronised product removes vertices that are not reachable; i.e. represents states that can never occur. By means of a lattice, we show all possible products of a set of graphs, where the number of products is given by the Bell number. We finish with heuristics from which a set of graphs can be calculated that represents a set of processes that will not miss their deadline and which fits in the available memory.
Original languageUndefined
Title of host publication36th WoTUG conference on concurrent and parallel programming
Place of PublicationOxford
PublisherOpen Channel Publishing Ltd
Pages119-138
Number of pages20
ISBN (Print)978-0-9565409-8-0
Publication statusPublished - 27 Aug 2014
EventCommunicating Process Architectures, CPA 2014: 36th WoTUG Conference on Concurrent and Parallel Programming 2014 - University of Oxford, Oxford, United Kingdom
Duration: 24 Aug 201427 Aug 2014
Conference number: 36
http://www.wotug.org/cpa2014/

Publication series

Name
PublisherOpen Channel Publishing Ltd.

Conference

ConferenceCommunicating Process Architectures, CPA 2014
Abbreviated titleCPA
CountryUnited Kingdom
CityOxford
Period24/08/1427/08/14
Internet address

Keywords

  • CE-Advanced Robotics
  • Graph transformationVertex removing synchronised productPerformance of real-time periodic processesProcess Algebra
  • Vertex Removing Synchronised Product
  • Performance of real-time periodic processes
  • METIS-309851
  • IR-93938
  • Graph Transformation
  • Process Algebra
  • EWI-25632

Cite this

Boode, A. H., & Broenink, J. F. (2014). Performance of periodic real-time processes: a vertex-removing synchronised graph product. In 36th WoTUG conference on concurrent and parallel programming (pp. 119-138). Oxford: Open Channel Publishing Ltd.
Boode, Antoon Hendrik ; Broenink, Johannes F. / Performance of periodic real-time processes: a vertex-removing synchronised graph product. 36th WoTUG conference on concurrent and parallel programming. Oxford : Open Channel Publishing Ltd, 2014. pp. 119-138
@inproceedings{51db9db9e90442509167f811d68a0839,
title = "Performance of periodic real-time processes: a vertex-removing synchronised graph product",
abstract = "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. For this reason it can be advantageous to combine processes, to reduce the number of context switches. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these configurations to periodic real-time processes executing on a single-core mono-processor. These processes can be represented by finite directed acyclic labelled multi-graphs. The vertex-removing synchronised product of such graphs gives graphs that represent processes which have less context switches. To reduce the memory occupancy, the vertex-removing synchronised product removes vertices that are not reachable; i.e. represents states that can never occur. By means of a lattice, we show all possible products of a set of graphs, where the number of products is given by the Bell number. We finish with heuristics from which a set of graphs can be calculated that represents a set of processes that will not miss their deadline and which fits in the available memory.",
keywords = "CE-Advanced Robotics, Graph transformationVertex removing synchronised productPerformance of real-time periodic processesProcess Algebra, Vertex Removing Synchronised Product, Performance of real-time periodic processes, METIS-309851, IR-93938, Graph Transformation, Process Algebra, EWI-25632",
author = "Boode, {Antoon Hendrik} and Broenink, {Johannes F.}",
note = "eemcs-eprint-25632",
year = "2014",
month = "8",
day = "27",
language = "Undefined",
isbn = "978-0-9565409-8-0",
publisher = "Open Channel Publishing Ltd",
pages = "119--138",
booktitle = "36th WoTUG conference on concurrent and parallel programming",

}

Boode, AH & Broenink, JF 2014, Performance of periodic real-time processes: a vertex-removing synchronised graph product. in 36th WoTUG conference on concurrent and parallel programming. Open Channel Publishing Ltd, Oxford, pp. 119-138, Communicating Process Architectures, CPA 2014, Oxford, United Kingdom, 24/08/14.

Performance of periodic real-time processes: a vertex-removing synchronised graph product. / Boode, Antoon Hendrik; Broenink, Johannes F.

36th WoTUG conference on concurrent and parallel programming. Oxford : Open Channel Publishing Ltd, 2014. p. 119-138.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Performance of periodic real-time processes: a vertex-removing synchronised graph product

AU - Boode, Antoon Hendrik

AU - Broenink, Johannes F.

N1 - eemcs-eprint-25632

PY - 2014/8/27

Y1 - 2014/8/27

N2 - 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. For this reason it can be advantageous to combine processes, to reduce the number of context switches. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these configurations to periodic real-time processes executing on a single-core mono-processor. These processes can be represented by finite directed acyclic labelled multi-graphs. The vertex-removing synchronised product of such graphs gives graphs that represent processes which have less context switches. To reduce the memory occupancy, the vertex-removing synchronised product removes vertices that are not reachable; i.e. represents states that can never occur. By means of a lattice, we show all possible products of a set of graphs, where the number of products is given by the Bell number. We finish with heuristics from which a set of graphs can be calculated that represents a set of processes that will not miss their deadline and which fits in the available memory.

AB - 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. For this reason it can be advantageous to combine processes, to reduce the number of context switches. Reducing the number of context switches decreases the execution time and thereby increases the performance of the application. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these configurations to periodic real-time processes executing on a single-core mono-processor. These processes can be represented by finite directed acyclic labelled multi-graphs. The vertex-removing synchronised product of such graphs gives graphs that represent processes which have less context switches. To reduce the memory occupancy, the vertex-removing synchronised product removes vertices that are not reachable; i.e. represents states that can never occur. By means of a lattice, we show all possible products of a set of graphs, where the number of products is given by the Bell number. We finish with heuristics from which a set of graphs can be calculated that represents a set of processes that will not miss their deadline and which fits in the available memory.

KW - CE-Advanced Robotics

KW - Graph transformationVertex removing synchronised productPerformance of real-time periodic processesProcess Algebra

KW - Vertex Removing Synchronised Product

KW - Performance of real-time periodic processes

KW - METIS-309851

KW - IR-93938

KW - Graph Transformation

KW - Process Algebra

KW - EWI-25632

M3 - Conference contribution

SN - 978-0-9565409-8-0

SP - 119

EP - 138

BT - 36th WoTUG conference on concurrent and parallel programming

PB - Open Channel Publishing Ltd

CY - Oxford

ER -

Boode AH, Broenink JF. Performance of periodic real-time processes: a vertex-removing synchronised graph product. In 36th WoTUG conference on concurrent and parallel programming. Oxford: Open Channel Publishing Ltd. 2014. p. 119-138