Lock-free distributed queue in remote memory access model

In parallel programming for distributed-memory systems in MPI standard, remote memory access model (one-sided communications, MPI RMA, RMA) is used along with the message-passing. This model in many cases leverages the performance and simplifies parallel programming. Here arises the problem of synchronization of multiple parallel processes and threads accessing shared (concurrent, distributed) data structures. In shared-memory machines, non-blocking synchronization (lock-free, wait-free, obstruction-free) is widely used to solve the similar problem. In non-blocking synchronization, delays in execution of one process (thread) do not suspend execution of other threads. We suppose that this approach could also be effective in designing distributed data structures (in the RMA model particularly). In this article, we discuss the idea of building non-blocking distributed data structures in RMA model on the example of a queue, describe the designed algorithms of operations, investigate the efficiency, and provide an experimental comparison with lock-based counterparts. Contribution of the authors: the authors contributed equally to this article. The authors declare no conflicts of interests.

Keywords

Authors

References