More Like this

1. Synchronous Message-Passing with Priority

   https://doi.org/10.1007/978-3-030-67438-0_3  

   Chuang, CE.; Iraci, G.; Ziarek, L. (January 2021, Practical Aspects of Declarative Languages. PADL 2021)

   Morales, J.F.; Orchard, D. (Ed.)

   In this paper we introduce a tiered-priority mechanism for a synchronous message-passing language with support for selective communication and first-class communication protocols. Crucially our mechanism allows higher priority threads to communicate with lower priority threads, providing the ability to express programs that would be rejected by classic priority mechanisms that disallow any (potentially) blocking interactions between threads of differing priorities. We provide a prototype implementation of our tiered-priority mechanism capable of expressing Concurrent ML and built in the MLton SML compiler and runtime. We evaluate the viability of our implementation by implementing a safe and predictable shutdown mechanisms in the Swerve webserver and eXene windowing toolkit. Our experiments show that priority can be easily added to existing CML programs without degrading performance. Our system exhibits negligible overheads on more modest workloads. 

   more » « less
2. Responsive Parallelism with Synchronization

   https://doi.org/10.1145/3591249  

   Muller, Stefan_K; Singer, Kyle; Keeney, Devyn_Terra; Neth, Andrew; Agrawal, Kunal; Lee, I-Ting_Angelina; Acar, Umut_A (June 2023, Proceedings of the ACM on Programming Languages)

   Many concurrent programs assign priorities to threads to improve responsiveness. When used in conjunction with synchronization mechanisms such as mutexes and condition variables, however, priorities can lead to priority inversions, in which high-priority threads are delayed by low-priority ones. Priority inversions in the use of mutexes are easily handled using dynamic techniques such as priority inheritance, but priority inversions in the use of condition variables are not well-studied and dynamic techniques are not suitable. In this work, we use a combination of static and dynamic techniques to prevent priority inversion in code that uses mutexes and condition variables. A type system ensures that condition variables are used safely, even while dynamic techniques change thread priorities at runtime to eliminate priority inversions in the use of mutexes. We prove the soundness of our system, using a model of priority inversions based on cost models for parallel programs. To show that the type system is practical to implement, we encode it within the type systems of Rust and C++, and show that the restrictions are not overly burdensome by writing sizeable case studies using these encodings, including porting the Memcached object server to use our C++ implementation. 

   more » « less
3. Processor-Oblivious Record and Replay

   https://doi.org/10.1145/3018743.3018764  

   Utterback, Robert; Agrawal, Kunal; Lee, I-Ting Angelina; Kulkarni, Milind (February 2017, Proceedings of the 22Nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming)

   Record-and-replay systems are useful tools for debugging non-deterministic parallel programs by first recording an execution and then replaying that execution to produce the same access pattern. Existing record-and-replay systems generally target thread-based execution models, and record the behaviors and interleavings of individual threads. Dynamic multithreaded languages and libraries, such as the Cilk family, OpenMP, TBB, etc., do not have a notion of threads. Instead, these languages provide a processor-oblivious model of programming, where programs expose task-parallelism using high-level constructs such as spawn/sync without regard to the number of threads/cores available to run the program. Thread-based record-and-replay would violate the processor-oblivious nature of these programs, as they incorporate the number of threads into the recorded information, constraining the replayed execution to the same number of threads. In this paper, we present a processor-oblivious record-and-replay scheme for such languages where record and replay can use different number of processors and both are scheduled using work stealing. We provide theoretical guarantees for our record and replay scheme --- namely that record is optimal for programs with one lock and replay is near-optimal for all cases. In addition, we implemented this scheme in the Cilk Plus runtime system and our evaluation indicates that processor-obliviousness does not cause substantial overheads. 

   more » « less
4. Design of a Portable Implementation of Partitioned Point-to-Point Communication Primitives

   https://doi.org/10.1145/3458744.3474046  

   Worley, Andrew; Prema Soundararajan, Prema; Schafer, Derek; Bangalore, Purushotham; Grant, Ryan; Dosanjh, Matthew; Skjellum, Anthony; Ghafoor, Sheikh (July 2021, ICPP Workshops '21: 50th International Conference on Parallel Processing Workshop)

   null (Ed.)

   The Message Passing Interface (MPI) has been the dominant message passing solution for scientific computing for decades. MPI point-to-point communications are highly efficient mechanisms for process-to- process communication. However, MPI performance is slowed by concurrency protections in the MPI library when processes utilize multiple threads. MPI’s current thread-level interface imposes these overheads throughout the library when thread safety is needed. While much work has been done to reduce multithreading overheads in MPI, a solution is needed that reduces the number of messages exchanged in a threaded environment. Partitioned communication is included in the MPI 4.0 standard as an alternative that addresses the challenges of multithreaded communication in MPI today. Partitioned communication reduces overall message volume by creating a buffer-sharing mechanism between threads such that they can indicate when portions of a communication buffer are available to be sent. Separation of the control and data planes in MPI is enabled by allowing persistent initialization and single occurrence message buffer matching from the indication that the data is ready to be sent. This enables the usage commands (destination, size, etc.) can be set up prior to data buffer readiness with readiness triggered by a simple doorbell/counter later. This approach is useful for future development of MPI operations in environments where traditional networking commands can have performance challenges, like accelerators (GPUs, FPGAs). In this paper,we detail the design and implementation of a layered library (built on top of MPI-3.1) and an integrated Open MPI solution that supports the new, MPI-4.0 partitioned communication feature set. The library will enable applications to use currently released MPI implementations and older legacy libraries to provide partitioned communication support while also enabling further exploration of this new communication model in new applications and use cases. We will compare the designs of the library and native Open MPI support, provide performance results and comparisons between the two approaches, and lessons learned from the implementation of partitioned communication in both library and native forms. We find that the native implementation and library have similar performance with a percentage difference under 0.94% in microbenchmarks and performance within 5% for a partitioned communication enabled proxy application. 

   more » « less
5. Traffic Priority-Aware 5G NR-U/Wi-Fi Coexistence with Deep Reinforcement Learning

   https://doi.org/10.1109/VTC2024-Fall63153.2024.10757867  

   Fasihi, Mohammad Reza; Mark, Brian L (October 2024, IEEE)

   Coexistence of 5G new radio unlicensed (NR-U) and Wi-Fi is highly prone to the collisions among NR-U gNBs (5G base stations) and Wi-Fi APs (access points). To improve performance and fairness for both networks, various collision resolution mechanisms have been proposed to replace the simple listen-before-talk (LBT) scheme used in the current 5G standard. We address two gaps in the literature: first, the lack of a comprehensive performance comparison among the proposed collision resolution mechanisms and second, the impact of multiple traffic priority classes. Through extensive simulations, we compare the performance of several recently proposed collision resolution mechanisms for NR-U/Wi-Fi coexistence. We extend one of these mechanisms to handle multiple traffic priorities. We then develop a traffic-aware multi-objective deep reinforcement learning algorithm for the scenario of coexistence of high-priority traffic gNB user equipment (UE) with multiple lower-priority traffic UEs and Wi-Fi stations. The objective is to ensure low latency for high-priority gNB traffic while increasing the airtime fairness among the NR-U and Wi-Fi networks. Our simulation results show that the proposed algorithm lowers the channel access delay of high-priority traffic while improving the fairness among both networks. 

   more » « less