Recently, we have introduced two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes. This vertexremoving synchronised product (VRSP) is based on modifications of the well-known Cartesian product and is closely related to the synchronised product due to Wohrle and Thomas. Here, we ¨ show how we can relax the requirements of these two graph-decomposition theorems.
In this paper, the performance gain obtained by combining parallel peri- odic real-time processes is elaborated. In certain single-core mono-processor configurations, for example, embedded control systems in robotics 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 and thereby increase 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. By graph-theoretical concepts and means, we provide necessary and sufficient conditions so that the number of context switches can be reduced by combining synchronising processes.
Recently, we have introduced and modified two graph-decomposition theorems based on a new graph product, motivated by applications in the context of synchronising periodic real-time processes. This vertex-removing synchronised product (VRSP), is based on modifications of the well-known Cartesian product and is closely related to the synchronised product due to Wohrle and Thomas. Here, we recall the definition of the VRSP and the two modified graph-decompositions and introduce three new graph-decomposition theorems. The first new theorem decomposes a graph with respect to the semicomplete bipartite subgraphs of the graph. For the second new theorem, we introduce a matrix graph, which is used to decompose a graph in a manner similar to the decomposition of graphs using the Cartesian product. In the third new theorem, we combine these two types of decomposition. Ultimately, the goal of these graph-decomposition theorems is to come to a prime-graph decomposition.
MULTIFILE
