Optimistic Semaphores with Non-deterministic Choice Operation for Heterogeneous Manycore Systems

Abstract

The Nix operating system permits different roles to be assigned to the cores. One of the roles is to be able to run user-space code with no interrupts from the operating system, which is particularly useful for high-performance computing. System calls are especially expensive to a core playing this role. This paper presents a new implementation of optimistic semaphores that avoid performing expensive system calls in an uncontended scenario. The implementation is straightforward and somewhat unorthodox: a semaphore is based on a data structure and a lock that are shared between user space and kernel space. This study aims at evaluating if such an approach is viable. In addition, the implementation includes a non-deterministic choice operation over a collection of semaphores, altsems. This novel operation facilitates the creation of higher-level communication mechanisms, such as sockets and channels. To support this claim, we implemented a new kind of buffered communication channels named tubes, tailored for communicating processes running on different (heterogeneous) cores. The paper describes the implementation of the semaphores and the tubes, a comparative analysis of optimistic and non-optimistic semaphores on Nix, and a comparative analysis of tubes and other kinds of communication channels that are available on the Nix operating system. Copyright © 2014 John Wiley & Sons, Ltd.