2 Search Results for "Jain, Saksham"

Document

DOI: 10.4230/LIPIcs.ECRTS.2024.15

Predictable GPU Sharing in Component-Based Real-Time Systems

Authors: Syed W. Ali, Zelin Tong, Joseph Goh, and James H. Anderson

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

Abstract

This paper presents a real-time locking protocol whose design was motivated by the goal of enabling safe GPU sharing in time-sliced component-based systems. This locking protocol enables a GPU to be shared concurrently across, and utilized within, isolated components with predictable execution times. It relies on a novel resizing technique where GPU work is dimensioned on-the-fly to run on partitions of an NVIDIA GPU. This technique can be applied to any component that internally utilizes global CPU scheduling. The proposed locking protocol enables increased GPU parallelism and reduces GPU capacity loss with analytically provable benefits.

Cite as

Syed W. Ali, Zelin Tong, Joseph Goh, and James H. Anderson. Predictable GPU Sharing in Component-Based Real-Time Systems. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{ali_et_al:LIPIcs.ECRTS.2024.15,
  author =	{Ali, Syed W. and Tong, Zelin and Goh, Joseph and Anderson, James H.},
  title =	{{Predictable GPU Sharing in Component-Based Real-Time Systems}},
  booktitle =	{36th Euromicro Conference on Real-Time Systems (ECRTS 2024)},
  pages =	{15:1--15:22},
  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.15},
  URN =		{urn:nbn:de:0030-drops-203183},
  doi =		{10.4230/LIPIcs.ECRTS.2024.15},
  annote =	{Keywords: GPU locking protocols, real-time locking protocols, priority-inversion blocking, component-based systems}
}

Document

DOI: 10.4230/LIPIcs.FSTTCS.2022.17

Online Piercing of Geometric Objects

Authors: Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh

Published in: LIPIcs, Volume 250, 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Abstract

We consider the online version of the piercing set problem where geometric objects arrive one by one. The online algorithm must maintain a piercing set for the arrived objects by making irrevocable decisions. First, we show that any deterministic online algorithm that solves this problem has a competitive ratio of at least Ω(n), which even holds when the objects are one-dimensional intervals. On the other hand, piercing unit objects is equivalent to the unit covering problem which is well-studied in the online model. Due to this, all the results related to the online unit covering problem are preserved for the online unit piercing problem when the objects are translated from each other. Surprisingly, no upper bound was known for the unit covering problem when unit objects are anything other than balls and hypercubes. In this paper, we introduce the notion of α-aspect and α-aspect_∞ objects. We give an upper bound of competitive ratio for α-aspect and α-aspect_∞ objects in ℝ³ and ℝ^d, respectively, with a scaling factor in the range [1,k]. We also propose a lower bound of the competitive ratio for bounded scaled objects like α-aspect objects in ℝ², axis-aligned hypercubes in ℝ^d, and balls in ℝ² and ℝ³. For piercing α-aspect_∞ objects in ℝ^d, we show that a simple deterministic algorithm achieves a competitive ratio of at most (2/α)^d((1+α)^d-1) (⌈log_(1+α)(2k/α)⌉)+1. This result is very general in nature. One can obtain upper bounds for specific objects by specifying the value of α. By putting the value of k = 1 to the above result, we get an upper bound of the competitive ratio for the unit covering problem for various types of objects.

Cite as

Minati De, Saksham Jain, Sarat Varma Kallepalli, and Satyam Singh. Online Piercing of Geometric Objects. In 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 250, pp. 17:1-17:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{de_et_al:LIPIcs.FSTTCS.2022.17,
  author =	{De, Minati and Jain, Saksham and Kallepalli, Sarat Varma and Singh, Satyam},
  title =	{{Online Piercing of Geometric Objects}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{17:1--17:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.17},
  URN =		{urn:nbn:de:0030-drops-174090},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.17},
  annote =	{Keywords: piercing set problem, online algorithm, competitive ratio, unit covering problem, geometric objects}
}

Refine by Author
1 Ali, Syed W.
1 Anderson, James H.
1 De, Minati
1 Goh, Joseph
1 Jain, Saksham
Show More...

Refine by Classification
1 Computer systems organization → Real-time systems
1 Theory of computation → Computational geometry

Refine by Keyword
1 GPU locking protocols
1 competitive ratio
1 component-based systems
1 geometric objects
1 online algorithm
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2022
1 2024