More Like this

1. Concurrency groups: a new way to look at real-time multiprocessor lock nesting

   https://doi.org/10.1145/3356401.3356404  

   Nemitz, Catherine E.; Amert, Tanya; Goyal, Manish; Anderson, James H. (November 2019, Proceedings of the 27th International Conference on Real-Time Networks and Systems)

   When designing a real-time multiprocessor locking protocol, the allowance of lock nesting creates complications that can kill parallelism. Such protocols are typically designed by focusing on the arbitration of resource requests that should be prohibited from executing concurrently. This paper proposes "concurrency groups," a new concept that reflects an alternative point of view that focuses instead on requests that can be allowed to execute concurrently. A concurrency group is simply a group of lock requests, determined offline, that can safely execute together. This paper's main contribution is the CGLP, a new real-time multiprocessor locking protocol that supports lock nesting through the use of concurrency groups. The CGLP is able to reap runtime parallelism benefits that have eluded prior protocols by investing effort offline in the construction of concurrency groups. A schedulability study is presented to quantify these benefits, as well as an efficient approach to determining such groups using an Integer Linear Program (ILP) solver. 

   more » « less
2. Real-Time Multiprocessor Locks with Nesting: Optimizing the Common Case

   Nemitz, C; Amert, T; Anderson, J (April 2019, Real-Time Systems, special issue of outstanding papers from the 25th International Conference on Real-Time Networks and Systems (RTNS 2017))

   In prior work on multiprocessor real-time locking protocols, only protocols within the RNLP family support unrestricted lock nesting while guaranteeing asymptotically optimal priority-inversion blocking bounds. However, these protocols support nesting at the expense of increasing the cost of processing non-nested lock requests, which tend to be the common case in practice. To remedy this situation, a newfast-path mechanism is presented herein that extends prior RNLP variants by ensuring that non-nested requests are processed efficiently. This mechanism yields overhead and blocking costs for such requests that are nearly identical to those seen in the most efficient single-resource locking protocols. In experiments, the proposed fast-path mechanism enabled observed blocking times for non-nested requests that were up to 17 times lower than under an existing RNLP variant. 

   more » « less
3. Predictable GPU Sharing in Component-Based Real-Time Systems

   https://doi.org/10.4230/LIPICS.ECRTS.2024.15  

   Ali, Syed W; Tong, Zelin; Goh, Joseph; Anderson, James H (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Pellizzoni, Rodolfo (Ed.)

   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. 

   more » « less
4. GOLDYLOC: Global Optimizations & Lightweight Dynamic Logic for Concurrency

   https://doi.org/10.1145/3730584  

   Pati, Suchita; Aga, Shaizeen; Jayasena, Nuwan; Sinclair, Matthew (May 2025, ACM Transactions on Architecture and Code Optimization)

   Modern accelerators like GPUs increasingly execute independent operations concurrently to improve the device’s compute utilization. However, effectively harnessing it on GPUs for important primitives such as general matrix multiplications (GEMMs) remains challenging. Although modern GPUs have significant hardware and software GEMM support, their kernel implementations and optimizations typically assume each kernel executes inisolationand can utilize all GPU resources. This approach is highly efficient when kernels execute in isolation, but causes significant resource contention and slowdowns when kernels execute concurrently. Moreover, current approaches often onlystaticallyexpose and control parallelism within an application, without considering runtime information such as varying input size and concurrent applications – often exacerbating contention. These issues limit performance benefits from concurrently executing independent operations. Accordingly, we propose GOLDYLOC, which considers theglobalresources across all concurrent operations to identify performant GEMM kernels, which we call globally optimized (GO)-Kernels. GOLDYLOC also introduces a lightweight dynamic logic which considers thedynamicexecution environment for available parallelism and input sizes to execute performant combinations of concurrent GEMMs on the GPU. Overall, GOLDYLOC improves performance of concurrent GEMMs on a real GPU by up to 2 × (18% geomean per workload) versus the default concurrency approach and provides up to 2.5 × (43% geomean per workload) speedup over sequential execution. 

   more » « less
5. Leibniz International Proceedings in Informatics (LIPIcs):35th Euromicro Conference on Real-Time Systems (ECRTS 2023)

   https://doi.org/10.4230/LIPIcs.ECRTS.2023.16  

   Ahmed, Shareef; Anderson, James H. (January 2023, Proceedings of the 35th Euromicro Conference on Real-Time Systems)

   Papadopoulos, Alessandro V. (Ed.)

   Real-time locking protocols are typically designed to reduce any priority-inversion blocking (pi-blocking) a task may incur while waiting to access a shared resource. For the multiprocessor case, a number of such protocols have been developed that ensure asymptotically optimal pi-blocking bounds under job-level fixed-priority scheduling. Unfortunately, no optimal multiprocessor real-time locking protocols are known that ensure tight pi-blocking bounds under any scheduler. This paper presents the first such protocols. Specifically, protocols are presented for mutual exclusion, reader-writer synchronization, and k-exclusion that are optimal under first-in-first-out (FIFO) scheduling when schedulability analysis treats suspension times as computation. Experiments are presented that demonstrate the effectiveness of these protocols. 

   more » « less