12 Search Results for "Chen, Kuan-Hsun"

Document
DOI: 10.4230/LIPIcs.ECRTS.2023.10
On the Equivalence of Maximum Reaction Time and Maximum Data Age for Cause-Effect Chains

Authors: Mario Günzel, Harun Teper, Kuan-Hsun Chen, Georg von der Brüggen, and Jian-Jia Chen

Published in: LIPIcs, Volume 262, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

Abstract
Real-time systems require a formal guarantee of timing-constraints, not only for individual tasks but also for data-propagation. The timing behavior of data-propagation paths in a given system is typically described by its maximum reaction time and its maximum data age. This paper shows that they are equivalent. To reach this conclusion, partitioned job chains are introduced, which consist of one immediate forward and one immediate backward job chain. Such partitioned job chains are proven to describe maximum reaction time and maximum data age in a universal manner. This universal description does not only show the equivalence of maximum reaction time and maximum data age, but can also be exploited to speed up the computation of such significantly. In particular, the speed-up for synthesized task sets based on automotive benchmarks can be up to 1600. Since only very few non-restrictive assumptions are made, the equivalence of maximum data age and maximum reaction time holds for almost any scheduling mechanism and even for tasks which do not adhere to the typical periodic or sporadic task model. This observation is supported by a simulation of a ROS2 navigation system.
Cite as

Mario Günzel, Harun Teper, Kuan-Hsun Chen, Georg von der Brüggen, and Jian-Jia Chen. On the Equivalence of Maximum Reaction Time and Maximum Data Age for Cause-Effect Chains. In 35th Euromicro Conference on Real-Time Systems (ECRTS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 262, pp. 10:1-10:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gunzel_et_al:LIPIcs.ECRTS.2023.10,
  author =	{G\"{u}nzel, Mario and Teper, Harun and Chen, Kuan-Hsun and von der Br\"{u}ggen, Georg and Chen, Jian-Jia},
  title =	{{On the Equivalence of Maximum Reaction Time and Maximum Data Age for Cause-Effect Chains}},
  booktitle =	{35th Euromicro Conference on Real-Time Systems (ECRTS 2023)},
  pages =	{10:1--10:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-280-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{262},
  editor =	{Papadopoulos, Alessandro V.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2023.10},
  URN =		{urn:nbn:de:0030-drops-180392},
  doi =		{10.4230/LIPIcs.ECRTS.2023.10},
  annote =	{Keywords: End-to-End, Timing Analysis, Maximum Data Age, Maximum Reaction Time, Cause-Effect Chain, Robot Operating Systems 2 (ROS2)}
}
Document
DOI: 10.4230/LITES.8.1.3
HW-Flow: A Multi-Abstraction Level HW-CNN Codesign Pruning Methodology

Authors: Manoj-Rohit Vemparala, Nael Fasfous, Alexander Frickenstein, Emanuele Valpreda, Manfredi Camalleri, Qi Zhao, Christian Unger, Naveen-Shankar Nagaraja, Maurizio Martina, and Walter Stechele

Published in: LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1

Abstract
Convolutional neural networks (CNNs) have produced unprecedented accuracy for many computer vision problems in the recent past. In power and compute-constrained embedded platforms, deploying modern CNNs can present many challenges. Most CNN architectures do not run in real-time due to the high number of computational operations involved during the inference phase. This emphasizes the role of CNN optimization techniques in early design space exploration. To estimate their efficacy in satisfying the target constraints, existing techniques are either hardware (HW) agnostic, pseudo-HW-aware by considering parameter and operation counts, or HW-aware through inflexible hardware-in-the-loop (HIL) setups. In this work, we introduce HW-Flow, a framework for optimizing and exploring CNN models based on three levels of hardware abstraction: Coarse, Mid and Fine. Through these levels, CNN design and optimization can be iteratively refined towards efficient execution on the target hardware platform. We present HW-Flow in the context of CNN pruning by augmenting a reinforcement learning agent with key metrics to understand the influence of its pruning actions on the inference hardware. With 2× reduction in energy and latency, we prune ResNet56, ResNet50, and DeepLabv3 with minimal accuracy degradation on the CIFAR-10, ImageNet, and CityScapes datasets, respectively.
Cite as

Manoj-Rohit Vemparala, Nael Fasfous, Alexander Frickenstein, Emanuele Valpreda, Manfredi Camalleri, Qi Zhao, Christian Unger, Naveen-Shankar Nagaraja, Maurizio Martina, and Walter Stechele. HW-Flow: A Multi-Abstraction Level HW-CNN Codesign Pruning Methodology. In LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision. Leibniz Transactions on Embedded Systems, Volume 8, Issue 1, pp. 03:1-03:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{vemparala_et_al:LITES.8.1.3,
  author =	{Vemparala, Manoj-Rohit and Fasfous, Nael and Frickenstein, Alexander and Valpreda, Emanuele and Camalleri, Manfredi and Zhao, Qi and Unger, Christian and Nagaraja, Naveen-Shankar and Martina, Maurizio and Stechele, Walter},
  title =	{{HW-Flow: A Multi-Abstraction Level HW-CNN Codesign Pruning Methodology}},
  booktitle =	{LITES, Volume 8, Issue 1 (2022): Special Issue on Embedded Systems for Computer Vision},
  pages =	{03:1--03:30},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Vemparala, Manoj-Rohit and Fasfous, Nael and Frickenstein, Alexander and Valpreda, Emanuele and Camalleri, Manfredi and Zhao, Qi and Unger, Christian and Nagaraja, Naveen-Shankar and Martina, Maurizio and Stechele, Walter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.8.1.3},
  doi =		{10.4230/LITES.8.1.3},
  annote =	{Keywords: Convolutional Neural Networks, Optimization, Hardware Modeling, Pruning}
}
Document
DOI: 10.4230/LIPIcs.DNA.28.4
Exploring Material Design Space with a Deep-Learning Guided Genetic Algorithm

Authors: Kuan-Lin Chen and Rebecca Schulman

Published in: LIPIcs, Volume 238, 28th International Conference on DNA Computing and Molecular Programming (DNA 28) (2022)

Abstract
Designing complex, dynamic yet multi-functional materials and devices is challenging because the design spaces for these materials have numerous interdependent and often conflicting constraints. Taking inspiration from advances in artificial intelligence and their applications in material discovery, we propose a computational method for designing metamorphic DNA-co-polymerized hydrogel structures. The method consists of a coarse-grained simulation and a deep learning-guided optimization system for exploring the immense design space of these structures. Here, we develop a simple numeric simulation of DNA-co-polymerized hydrogel shape change and seek to find designs for structured hydrogels that can fold into the shapes of different Arabic numerals in different actuation states. We train a convolutional neural network to classify and score the geometric outputs of the coarse-grained simulation to provide autonomous feedback for design optimization. We then construct a genetic algorithm that generates and selects large batches of material designs that compete with one another to evolve and converge on optimal objective-matching designs. We show that we are able to explore the large design space and learn important parameters and traits. We identify vital relationships between the material scale size and the range of shape change that can be achieved by individual domains and we elucidate trade-offs between different design parameters. Finally, we discover material designs capable of transforming into multiple different digits in different actuation states.
Cite as

Kuan-Lin Chen and Rebecca Schulman. Exploring Material Design Space with a Deep-Learning Guided Genetic Algorithm. In 28th International Conference on DNA Computing and Molecular Programming (DNA 28). Leibniz International Proceedings in Informatics (LIPIcs), Volume 238, pp. 4:1-4:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.DNA.28.4,
  author =	{Chen, Kuan-Lin and Schulman, Rebecca},
  title =	{{Exploring Material Design Space with a Deep-Learning Guided Genetic Algorithm}},
  booktitle =	{28th International Conference on DNA Computing and Molecular Programming (DNA 28)},
  pages =	{4:1--4:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-253-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{238},
  editor =	{Ouldridge, Thomas E. and Wickham, Shelley F. J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.28.4},
  URN =		{urn:nbn:de:0030-drops-167899},
  doi =		{10.4230/LIPIcs.DNA.28.4},
  annote =	{Keywords: Machine Learning, Deep Learning, Computational Material Design, Multi-Objective Optimization, DNA Nanotechnology}
}
Document
DOI: 10.4230/OASIcs.WCET.2022.2
LLVMTA: An LLVM-Based WCET Analysis Tool

Authors: Sebastian Hahn, Michael Jacobs, Nils Hölscher, Kuan-Hsun Chen, Jian-Jia Chen, and Jan Reineke

Published in: OASIcs, Volume 103, 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022)

Abstract
We present llvmta, an academic WCET analysis tool based on the LLVM compiler infrastructure. It aims to enable the evaluation of novel WCET analysis approaches in a state-of-the-art analysis framework without dealing with the complexity of modeling real-world hardware architectures. We discuss the main design decisions and interfaces that allow to implement new analysis approaches. Finally, we highlight various existing research projects whose evaluation has been enabled by llvmta.
Cite as

Sebastian Hahn, Michael Jacobs, Nils Hölscher, Kuan-Hsun Chen, Jian-Jia Chen, and Jan Reineke. LLVMTA: An LLVM-Based WCET Analysis Tool. In 20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022). Open Access Series in Informatics (OASIcs), Volume 103, pp. 2:1-2:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{hahn_et_al:OASIcs.WCET.2022.2,
  author =	{Hahn, Sebastian and Jacobs, Michael and H\"{o}lscher, Nils and Chen, Kuan-Hsun and Chen, Jian-Jia and Reineke, Jan},
  title =	{{LLVMTA: An LLVM-Based WCET Analysis Tool}},
  booktitle =	{20th International Workshop on Worst-Case Execution Time Analysis (WCET 2022)},
  pages =	{2:1--2:17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-244-0},
  ISSN =	{2190-6807},
  year =	{2022},
  volume =	{103},
  editor =	{Ballabriga, Cl\'{e}ment},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2022.2},
  URN =		{urn:nbn:de:0030-drops-166242},
  doi =		{10.4230/OASIcs.WCET.2022.2},
  annote =	{Keywords: WCET analysis, low-level analysis, LLVM}
}
Document
Artifact
DOI: 10.4230/DARTS.8.1.2
Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization (Artifact)

Authors: Kuan-Hsun Chen, Mario Günzel, Boguslaw Jablkowski, Markus Buschhoff, and Jian-Jia Chen

Published in: DARTS, Volume 8, Issue 1, Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
This artifact provides the source code to validate and reproduce the numerical results of the associated paper "Unikernel-Based Real-Time Virtualization under Deferrable Servers: Analysis and Realization". Due to the nature of a close-source project with the company, i.e., EMVICORE GmbH, the source code of the case study in Section 6.2 is not included in this artifact.
Cite as

Kuan-Hsun Chen, Mario Günzel, Boguslaw Jablkowski, Markus Buschhoff, and Jian-Jia Chen. Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization (Artifact). In Special Issue of the 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Dagstuhl Artifacts Series (DARTS), Volume 8, Issue 1, pp. 2:1-2:2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{chen_et_al:DARTS.8.1.2,
  author =	{Chen, Kuan-Hsun and G\"{u}nzel, Mario and Jablkowski, Boguslaw and Buschhoff, Markus and Chen, Jian-Jia},
  title =	{{Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization (Artifact)}},
  pages =	{2:1--2:2},
  journal =	{Dagstuhl Artifacts Series},
  ISSN =	{2509-8195},
  year =	{2022},
  volume =	{8},
  number =	{1},
  editor =	{Chen, Kuan-Hsun and G\"{u}nzel, Mario and Jablkowski, Boguslaw and Buschhoff, Markus and Chen, Jian-Jia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DARTS.8.1.2},
  URN =		{urn:nbn:de:0030-drops-164987},
  doi =		{10.4230/DARTS.8.1.2},
  annote =	{Keywords: Unikernel, Virtualization, Reservation Servers, Deferrable Servers, Cyber-Physical Systems, Real-Time Systems}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2022.6
Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization

Authors: Kuan-Hsun Chen, Mario Günzel, Boguslaw Jablkowski, Markus Buschhoff, and Jian-Jia Chen

Published in: LIPIcs, Volume 231, 34th Euromicro Conference on Real-Time Systems (ECRTS 2022)

Abstract
For cyber-physical systems, real-time virtualization optimizes the hardware utilization by consolidating multiple systems into the same platform, while satisfying the timing constraints of their real-time tasks. This paper considers virtualization based on unikernels, i.e., single address space kernels usually constructed by using library operating systems. Each unikernel is a guest operating system in the virtualization and hosts a single real-time task. We consider deferrable servers in the virtualization platform to schedule the unikernel-based guest operating systems and analyze the worst-case response time of a sporadic real-time task under such a virtualization architecture. Throughout synthesized tasksets, we empirically show that our analysis outperforms the restated analysis derived from the state-of-the-art, which is based on Real-Time Calculus. Furthermore, we provide insights on implementation-specific issues and offer evidence that the proposed scheduling architecture can be effectively implemented on top of the Xen hypervisor while incurring acceptable overhead.
Cite as

Kuan-Hsun Chen, Mario Günzel, Boguslaw Jablkowski, Markus Buschhoff, and Jian-Jia Chen. Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization. In 34th Euromicro Conference on Real-Time Systems (ECRTS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 231, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ECRTS.2022.6,
  author =	{Chen, Kuan-Hsun and G\"{u}nzel, Mario and Jablkowski, Boguslaw and Buschhoff, Markus and Chen, Jian-Jia},
  title =	{{Unikernel-Based Real-Time Virtualization Under Deferrable Servers: Analysis and Realization}},
  booktitle =	{34th Euromicro Conference on Real-Time Systems (ECRTS 2022)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-239-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{231},
  editor =	{Maggio, Martina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2022.6},
  URN =		{urn:nbn:de:0030-drops-163239},
  doi =		{10.4230/LIPIcs.ECRTS.2022.6},
  annote =	{Keywords: Unikernel, Virtualization, Reservation Servers, Deferrable Servers, Cyber-Physical Systems, Real-Time Systems}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.43
Improved Decoding of Expander Codes

Authors: Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
We study the classical expander codes, introduced by Sipser and Spielman [M. Sipser and D. A. Spielman, 1996]. Given any constants 0 < α, ε < 1/2, and an arbitrary bipartite graph with N vertices on the left, M < N vertices on the right, and left degree D such that any left subset S of size at most α N has at least (1-ε)|S|D neighbors, we show that the corresponding linear code given by parity checks on the right has distance at least roughly {α N}/{2 ε}. This is strictly better than the best known previous result of 2(1-ε) α N [Madhu Sudan, 2000; Viderman, 2013] whenever ε < 1/2, and improves the previous result significantly when ε is small. Furthermore, we show that this distance is tight in general, thus providing a complete characterization of the distance of general expander codes. Next, we provide several efficient decoding algorithms, which vastly improve previous results in terms of the fraction of errors corrected, whenever ε < 1/4. Finally, we also give a bound on the list-decoding radius of general expander codes, which beats the classical Johnson bound in certain situations (e.g., when the graph is almost regular and the code has a high rate). Our techniques exploit novel combinatorial properties of bipartite expander graphs. In particular, we establish a new size-expansion tradeoff, which may be of independent interests.
Cite as

Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. Improved Decoding of Expander Codes. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 43:1-43:3, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2022.43,
  author =	{Chen, Xue and Cheng, Kuan and Li, Xin and Ouyang, Minghui},
  title =	{{Improved Decoding of Expander Codes}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{43:1--43:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.43},
  URN =		{urn:nbn:de:0030-drops-156394},
  doi =		{10.4230/LIPIcs.ITCS.2022.43},
  annote =	{Keywords: Expander Code, Decoding}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.50
Tight Competitive Analyses of Online Car-Sharing Problems

Authors: Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, and Kazuo Iwama

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
The car-sharing problem, proposed by Luo, Erlebach and Xu in 2018, mainly focuses on an online model in which there are two locations: 0 and 1, and k total cars. Each request which specifies its pick-up time and pick-up location (among 0 and 1, and the other is the drop-off location) is released in each stage a fixed amount of time before its specified start (i.e. pick-up) time. The time between the booking (i.e. released) time and the start time is enough to move empty cars between 0 and 1 for relocation if they are not used in that stage. The model, called kS2L-F, assumes that requests in each stage arrive sequentially regardless of the same booking time and the decision (accept or reject) must be made immediately. The goal is to accept as many requests as possible. In spite of only two locations, the analysis does not seem easy and the (tight) competitive ratio (CR) is only known to be 2.0 for k = 2 and 1.5 for a restricted value of k, i.e., a multiple of three. In this paper, we remove all the holes of unknown CR’s; namely we prove that the CR is 2k/(k + ⌊k/3⌋) for all k ≥ 2. Furthermore, if the algorithm can delay its decision until all requests have come in each stage, the CR is improved to roughly 4/3. We can take this advantage even further, precisely we can achieve a CR of (2+R)/3 if the number of requests in each stage is at most Rk, 1 ≤ R ≤ 2, where we do not have to know the value of R in advance. Finally we demonstrate that randomization also helps to get (slightly) better CR’s.
Cite as

Ya-Chun Liang, Kuan-Yun Lai, Ho-Lin Chen, and Kazuo Iwama. Tight Competitive Analyses of Online Car-Sharing Problems. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 50:1-50:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{liang_et_al:LIPIcs.ISAAC.2021.50,
  author =	{Liang, Ya-Chun and Lai, Kuan-Yun and Chen, Ho-Lin and Iwama, Kazuo},
  title =	{{Tight Competitive Analyses of Online Car-Sharing Problems}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.50},
  URN =		{urn:nbn:de:0030-drops-154835},
  doi =		{10.4230/LIPIcs.ISAAC.2021.50},
  annote =	{Keywords: Car-sharing, Competitive analysis, On-line scheduling, Randomized algorithm}
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2020.18
Offloading Safety- and Mission-Critical Tasks via Unreliable Connections

Authors: Lea Schönberger, Georg von der Brüggen, Kuan-Hsun Chen, Benjamin Sliwa, Hazem Youssef, Aswin Karthik Ramachandran Venkatapathy, Christian Wietfeld, Michael ten Hompel, and Jian-Jia Chen

Published in: LIPIcs, Volume 165, 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)

Abstract
For many cyber-physical systems, e.g., IoT systems and autonomous vehicles, offloading workload to auxiliary processing units has become crucial. However, since this approach highly depends on network connectivity and responsiveness, typically only non-critical tasks are offloaded, which have less strict timing requirements than critical tasks. In this work, we provide two protocols allowing to offload critical and non-critical tasks likewise, while providing different service levels for non-critical tasks in the event of an unsuccessful offloading operation, depending on the respective system requirements. We analyze the worst-case timing behavior of the local cyber-physical system and, based on these analyses, we provide a sufficient schedulability test for each of the proposed protocols. In the course of comprehensive experiments, we show that our protocols have reasonable acceptance ratios under the provided schedulability tests. Moreover, we demonstrate that the system behavior under our proposed protocols is strongly dependent on probability of unsuccessful offloading operations, the percentage of critical tasks in the system, and the amount of offloaded workload.
Cite as

Lea Schönberger, Georg von der Brüggen, Kuan-Hsun Chen, Benjamin Sliwa, Hazem Youssef, Aswin Karthik Ramachandran Venkatapathy, Christian Wietfeld, Michael ten Hompel, and Jian-Jia Chen. Offloading Safety- and Mission-Critical Tasks via Unreliable Connections. In 32nd Euromicro Conference on Real-Time Systems (ECRTS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 165, pp. 18:1-18:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{schonberger_et_al:LIPIcs.ECRTS.2020.18,
  author =	{Sch\"{o}nberger, Lea and von der Br\"{u}ggen, Georg and Chen, Kuan-Hsun and Sliwa, Benjamin and Youssef, Hazem and Ramachandran Venkatapathy, Aswin Karthik and Wietfeld, Christian and ten Hompel, Michael and Chen, Jian-Jia},
  title =	{{Offloading Safety- and Mission-Critical Tasks via Unreliable Connections}},
  booktitle =	{32nd Euromicro Conference on Real-Time Systems (ECRTS 2020)},
  pages =	{18:1--18:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-152-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{165},
  editor =	{V\"{o}lp, Marcus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2020.18},
  URN =		{urn:nbn:de:0030-drops-123811},
  doi =		{10.4230/LIPIcs.ECRTS.2020.18},
  annote =	{Keywords: internet of things, cyber-physical systems, real-time, mixed-criticality, self-suspension, computation offloading, scheduling, communication}
}
Document
DOI: 10.4230/LITES-v006-i001-a004
A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems

Authors: Robert I. Davis and Liliana Cucu-Grosjean

Published in: LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1

Abstract
This survey covers schedulability analysis techniques for probabilistic real-time systems. It reviews the key results in the field from its origins in the late 1980s to the latest research published up to the end of August 2018. The survey outlinesfundamental concepts and highlights key issues. It provides a taxonomy of the different methods used, and a classification of existing research. A detailed review is provided covering the main subject areas as well as research on supporting techniques. The survey concludes by identifying open issues, key challenges and possible directions for future research.
Cite as

Robert I. Davis and Liliana Cucu-Grosjean. A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems. In LITES, Volume 6, Issue 1 (2019). Leibniz Transactions on Embedded Systems, Volume 6, Issue 1, pp. 04:1-04:53, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{davis_et_al:LITES-v006-i001-a004,
  author =	{Davis, Robert I. and Cucu-Grosjean, Liliana},
  title =	{{A Survey of Probabilistic Schedulability Analysis Techniques for Real-Time Systems}},
  booktitle =	{LITES, Volume 6, Issue 1 (2019)},
  pages =	{04:1--04:53},
  journal =	{Leibniz Transactions on Embedded Systems},
  ISSN =	{2199-2002},
  year =	{2019},
  volume =	{6},
  number =	{1},
  editor =	{Davis, Robert I. and Cucu-Grosjean, Liliana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES-v006-i001-a004},
  doi =		{10.4230/LITES-v006-i001-a004},
  annote =	{Keywords: Probabilistic, real-time, schedulability analysis, scheduling, }
}
Document
DOI: 10.4230/LIPIcs.ECRTS.2018.6
Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems

Authors: Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik

Published in: LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018)

Abstract
This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses.
Cite as

Georg von der Brüggen, Nico Piatkowski, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 6:1-6:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{vonderbruggen_et_al:LIPIcs.ECRTS.2018.6,
  author =	{von der Br\"{u}ggen, Georg and Piatkowski, Nico and Chen, Kuan-Hsun and Chen, Jian-Jia and Morik, Katharina},
  title =	{{Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems}},
  booktitle =	{30th Euromicro Conference on Real-Time Systems (ECRTS 2018)},
  pages =	{6:1--6:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-075-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{106},
  editor =	{Altmeyer, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.6},
  URN =		{urn:nbn:de:0030-drops-89978},
  doi =		{10.4230/LIPIcs.ECRTS.2018.6},
  annote =	{Keywords: deadline miss probability, multinomial-based approach, analytical bound}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2016.61
An Improved Tax Scheme for Selfish Routing

Authors: Te-Li Wang, Chih-Kuan Yeh, and Ho-Lin Chen

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
We study the problem of routing traffic for independent selfish users in a congested network to minimize the total latency. The inefficiency of selfish routing motivates regulating the flow of the system to lower the total latency of the Nash Equilibrium by economic incentives or penalties. When applying tax to the routes, we follow the definition of [Christodoulou et al, Algorithmica, 2014] to define ePoA as the Nash total cost including tax in the taxed network over the optimal cost in the original network. We propose a simple tax scheme consisting of step functions imposed on the links. The tax scheme can be applied to routing games with parallel links, affine cost functions and single-commodity networks to lower the ePoA to at most 4/3 - epsilon, where epsilon only depends on the discrepancy between the links. We show that there exists a tax scheme in the two link case with an ePoA upperbound less than 1.192 which is almost tight. Moreover, we design another tax scheme that lowers ePoA down to 1.281 for routing games with groups of links such that links in the same group are similar to each other and groups are sufficiently different.
Cite as

Te-Li Wang, Chih-Kuan Yeh, and Ho-Lin Chen. An Improved Tax Scheme for Selfish Routing. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 61:1-61:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{wang_et_al:LIPIcs.ISAAC.2016.61,
  author =	{Wang, Te-Li and Yeh, Chih-Kuan and Chen, Ho-Lin},
  title =	{{An Improved Tax Scheme for Selfish Routing}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{61:1--61:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.61},
  URN =		{urn:nbn:de:0030-drops-68308},
  doi =		{10.4230/LIPIcs.ISAAC.2016.61},
  annote =	{Keywords: selfish routing, price of anarchy, tax}
}
  • Refine by Author
  • 6 Chen, Jian-Jia
  • 6 Chen, Kuan-Hsun
  • 3 Günzel, Mario
  • 3 von der Brüggen, Georg
  • 2 Buschhoff, Markus
  • Show More...

  • Refine by Classification
  • 3 Computer systems organization → Embedded and cyber-physical systems
  • 3 Computer systems organization → Real-time systems
  • 3 Software and its engineering → Real-time systems software
  • 2 Computing methodologies → Artificial intelligence
  • 1 Computer systems organization
  • Show More...

  • Refine by Keyword
  • 2 Cyber-Physical Systems
  • 2 Deferrable Servers
  • 2 Real-Time Systems
  • 2 Reservation Servers
  • 2 Unikernel
  • Show More...

  • Refine by Type
  • 12 document

  • Refine by Publication Year
  • 6 2022
  • 1 2016
  • 1 2018
  • 1 2019
  • 1 2020
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact