2 Search Results for "Hua, Qi Cheng"


Document
The Omnivisor: A Real-Time Static Partitioning Hypervisor Extension for Heterogeneous Core Virtualization over MPSoCs

Authors: Daniele Ottaviano, Francesco Ciraolo, Renato Mancuso, and Marcello Cinque

Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)


Abstract
Following the needs of industrial applications, virtualization has emerged as one of the most effective approaches for the consolidation of mixed-criticality systems while meeting tight constraints in terms of space, weight, power, and cost (SWaP-C). In embedded platforms with homogeneous processors, a wealth of works have proposed designs and techniques to enforce spatio-temporal isolation by leveraging well-understood virtualization support. Unfortunately, achieving the same goal on heterogeneous MultiProcessor Systems-on-Chip (MPSoCs) has been largely overlooked. Modern hypervisors are designed to operate exclusively on main cores, with little or no consideration given to other co-processors within the system, such as small microcontroller-level CPUs or soft-cores deployed on programmable logic (FPGA). Typically, hypervisors consider co-processors as I/O devices allocated to virtual machines that run on primary cores, yielding full control and responsibility over them. Nevertheless, inadequate management of these resources can lead to spatio-temporal isolation issues within the system. In this paper, we propose the Omnivisor model as a paradigm for the holistic management of heterogeneous platforms. The model generalizes the features of real-time static partitioning hypervisors to enable the execution of virtual machines on processors with different Instruction Set Architectures (ISAs) within the same MPSoC. Moreover, the Omnivisor ensures temporal and spatial isolation between virtual machines by integrating and leveraging a variety of hardware and software protection mechanisms. The presented approach not only expands the scope of virtualization in MPSoCs but also enhances the overall system reliability and real-time performance for mixed-criticality applications. A full open-source reference implementation of the Omnivisor based on the Jailhouse hypervisor is provided, targeting ARM real-time processing units and RISC-V soft-cores on FPGA. Experimental results on real hardware show the benefits of the solution, including enabling the seamless launch of virtual machines on different ISAs and extending spatial/temporal isolation to heterogenous cores with enhanced regulation policies.

Cite as

Daniele Ottaviano, Francesco Ciraolo, Renato Mancuso, and Marcello Cinque. The Omnivisor: A Real-Time Static Partitioning Hypervisor Extension for Heterogeneous Core Virtualization over MPSoCs. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 7:1-7:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{ottaviano_et_al:LIPIcs.ECRTS.2024.7,
  author =	{Ottaviano, Daniele and Ciraolo, Francesco and Mancuso, Renato and Cinque, Marcello},
  title =	{{The Omnivisor: A Real-Time Static Partitioning Hypervisor Extension for Heterogeneous Core Virtualization over MPSoCs}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{7:1--7:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-324-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{298},
  editor =	{Pellizzoni, Rodolfo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.7},
  URN =		{urn:nbn:de:0030-drops-203107},
  doi =		{10.4230/LIPIcs.ECRTS.2024.7},
  annote =	{Keywords: Mixed-Criticality, Embedded Virtualization, Real-Time Systems, MPSoCs}
}
Document
Fully Dynamic Four-Vertex Subgraph Counting

Authors: Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)


Abstract
This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of paths of length three in deterministic amortized O(m^{1/2}) update time, and any other connected four-vertex subgraph which is not a clique in deterministic amortized update time O(m^{2/3}). Queries can be answered in constant time. We also study the query times for subgraphs containing an arbitrary edge that is supplied only with the query as well as the case where only subgraphs containing a vertex s that is fixed beforehand are considered. For length-3 paths, paws, 4-cycles, and diamonds our bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of paws, diamonds, or 4-cycles or that counts length-3 paths takes update time Ω(m^{1/2-δ}). Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of Ω(m^{1-δ}) for any small constant δ > 0 for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the O(m) algorithm by Eppstein et al. [David Eppstein et al., 2012] for these subgraphs cannot be improved by a polynomial factor.

Cite as

Kathrin Hanauer, Monika Henzinger, and Qi Cheng Hua. Fully Dynamic Four-Vertex Subgraph Counting. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{hanauer_et_al:LIPIcs.SAND.2022.18,
  author =	{Hanauer, Kathrin and Henzinger, Monika and Hua, Qi Cheng},
  title =	{{Fully Dynamic Four-Vertex Subgraph Counting}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{18:1--18:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.18},
  URN =		{urn:nbn:de:0030-drops-159608},
  doi =		{10.4230/LIPIcs.SAND.2022.18},
  annote =	{Keywords: Dynamic Graph Algorithms, Subgraph Counting, Motif Search}
}
  • Refine by Author
  • 1 Cinque, Marcello
  • 1 Ciraolo, Francesco
  • 1 Hanauer, Kathrin
  • 1 Henzinger, Monika
  • 1 Hua, Qi Cheng
  • Show More...

  • Refine by Classification
  • 1 Computer systems organization → Real-time system architecture
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 1 Dynamic Graph Algorithms
  • 1 Embedded Virtualization
  • 1 MPSoCs
  • 1 Mixed-Criticality
  • 1 Motif Search
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2022
  • 1 2024