Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 929 papers for “synchronization primitives”

Scaling synchronization primitives

Kashyap, Sanidhya · SMARTech Repository (Georgia Institute of Technology) · 2020

Over the past decade, multicore machines have become the norm. A single machine is capable of having thousands of hardware threads or cores. Even cloud providers offer such\nlarge multicore machines for data processing engines and databases. Thus, a fundamental question arises is how efficient are existing synchronization primitives— timestamping and locking—that developers use for designing concurrent, scalable, and performant applications. This dissertation focuses on understanding the scalability aspect of these primitives, and\npresents new algorithms and approaches, that either leverage the hardware or the application\ndomain knowledge, to scale up to hundreds of cores. First, the thesis presents Ordo , a scalable ordering or timestamping primitive, that forms\nthe basis of designing scalable timestamp-based concurrency control mechanisms. Ordo relies on invariant hardware clocks and provides a notion of a globally synchronized clock\nwithin a machine. We use the Ordo primitive to redesign a synchronization mechanism and concurrency control mechanisms in databases and software transactional memory. Later, this thesis focuses on the scalability aspect of locks in both virtualized and non-virtualized scenarios. In a virtualized environment, we identify that these locks suffer from\nvarious preemption issues due to a semantic gap between the hypervisor shceduler and a virtual machine scheduler—the double scheduling problem. We address this problem\nby bridging this gap, in which both the hypervisor and virtual machines share minimal scheduling information to avoid the preemption problems. Finally, we focus on the design of lock algorithms in general. We find that locks in practice have discrepancies from locks in design. For example, popular spinlocks suffer from excessive cache-line bouncing in multicore (NUMA) systems, while state-of-the-art locks exhibit sub-par single-thread performance. We classify several dominating factors that impact the performance of lock algorithms. We then propose a new technique, shuffling, that can dynamically accommodate all these factors, without slowing down the critical path of the lock. The key idea of shuffling is to re-order the queue of threads waiting to acquire the lock with some pre-established policy. Using shuffling, we propose a family of locking algorithms, called SHFLLOCKS that respect all factors, efficiently utilize waiters, and achieve the best performance.

Cited by 0

Synchronization and Communication Primitives

Subodh Kumar · 2022

Interaction between concurrently executing fragments is an essential characteristic of parallel programs and the major source of difference between sequential programming and parallel programming. Synchronization and communication are the two ways in which fragments directly interact, and these are the subjects of this chapter. We begin with a brief review of basic operating system concepts, particularly in the context of parallel and concurrent execution. If you already have a good knowledge of operating systems concepts, browse lightly or skip ahead.

Cited by 0

Synchronization and Communication Primitives

Subodh Kumar · 2023

In modern computer science, there exists no truly sequential computing system; and most advanced programming is parallel programming. This is particularly evident in modern application domains like scientific computation, data science, machine intelligence, etc. This lucid introductory textbook will be invaluable to students of computer science and technology, acting as a self-contained primer to parallel programming. It takes the reader from introduction to expertise, addressing a broad gamut of issues. It covers different parallel programming styles, describes parallel architecture, includes parallel programming frameworks and techniques, presents algorithmic and analysis techniques and discusses parallel design and performance issues. With its broad coverage, the book can be useful in a wide range of courses; and can also prove useful as a ready reckoner for professionals in the field.

Cited by 0

Synchronization Primitives for Threads

Wim H. Hesselink, Jan Eppo Jonker · 2000

The POSIX thread standard and the programming language Modula-3 both support light-weight processes called threads, with mutexes and condition variables for synchronization. The paper analyses the main primitives and shows how they can be used to implement semaphores and systems of await statements. Where necessary, the correctness is shown by means of invariants. Keywords thread, mutex, condition variable, signal, POSIX thread standard, Modula-3 1 Introduction The POSIX committee has specied a standard (1003.1c) for the handling of threads and their synchronization. Threads with these primitives are called POSIX threads or pthreads. The standard provides mutexes, condition variables and associated commands, cf. [3, 6]. The criteria for selecting these primitives seem to have been generality and ecient implementability. The main synchronization primitives are wait and signal. These primitives are also provided by the programming language Modula-3, cf. [4]. It is important to ...

Cited by 0

Synchronization Primitives for a Multiprocessor:

A. D. Birrell, J. V. Guttag, J. J. Horning et al. · 1987

educational and research purposes provided that all such whole or partial copies include the following: a notice that such copying is by permission of the Systems Research Center of Digital Equipment Corporation in Palo Alto, California; an acknowledgment of the authors and individual contributors to the work; and all applicable portions of the copyright notice. Copying, reproducing, or republishing for any other purpose shall require a license with payment of fee to the Systems Research Center. All rights reserved. ii Formal speci�cations of operating system interfaces can be a useful part of their documentation. We illustrate this by documenting the Threads synchronization primitives of the Taos operating system. We start with an informal description, present away to formally specify interfaces in concurrent systems, and then give a formal speci�cation of the synchronization primitives. We brie�y discuss both the implementation and what we have learned from using the speci�cation for more than a year. Our main conclusion is that programmers untrained in reading formal speci�cations have found this one helpful in getting their work done. iii

Cited by 0

Application-Informed Kernel Synchronization Primitives

Park, Sujin, Zhou, Diyu, Qian, Yuchen et al. · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2022

Kernel synchronization primitives are the backbone of any OS design. Kernel locks, for instance, are crucial for both application performance and correctness. However, unlike application locks, kernel locks are far from the reach of application developers, who have minimal interpolation of the kernel's behavior and cannot control or influence the policies that govern kernel synchronization behavior. This disconnect between the kernel and applications can lead to pathological scenarios in which optimizing the kernel synchronization primitives under one context, such as high contention, leads to adversarial effects under a context with no lock contention. In addition, rapid-evolving heterogeneous hardware makes kernel lock development too slow for modern applications with stringent performance requirements and frequent deployment timelines.|This paper addresses the above issues with application-informed kernel synchronization primitives. We allow application developers to deploy workload-specific and hardware-aware kernel lock policies to boost application performance, resolve pathological usage of kernel locks, and even enable dynamic profiling of locks of interest. To showcase this idea, we design SYNCORD, a framework to modify kernel locks without recompiling or rebooting the kernel. SYNCORD abstracts key behaviors of kernel locks and exposes them as APIs for designing user-defined kernel locks. SYNCORD provides the mechanisms to customize kernel locks safely and correctly from the user space. We design five lock policies specialized for new heterogeneous hardware and specific software requirements. Our evaluation shows that SYNCORD incurs minimal runtime overhead and generates kernel locks with performance comparable to that of the state-of-the-art locks.

Cited by 6Open access

Efficient Synchronization Primitives for GPUs

Jeff A. Stuart, John D. Owens · arXiv (Cornell University) · 2011

In this paper, we revisit the design of synchronization primitives---specifically barriers, mutexes, and semaphores---and how they apply to the GPU. Previous implementations are insufficient due to the discrepancies in hardware and programming model of the GPU and CPU. We create new implementations in CUDA and analyze the performance of spinning on the GPU, as well as a method of sleeping on the GPU, by running a set of memory-system benchmarks on two of the most common GPUs in use, the Tesla- and Fermi-class GPUs from NVIDIA. From our results we define higher-level principles that are valid for generic many-core processors, the most important of which is to limit the number of atomic accesses required for a synchronization operation because atomic accesses are slower than regular memory accesses. We use the results of the benchmarks to critique existing synchronization algorithms and guide our new implementations, and then define an abstraction of GPUs to classify any GPU based on the behavior of the memory system. We use this abstraction to create suitable implementations of the primitives specifically targeting the GPU, and analyze the performance of these algorithms on Tesla and Fermi. We then predict performance on future GPUs based on characteristics of the abstraction. We also examine the roles of spin waiting and sleep waiting in each primitive and how their performance varies based on the machine abstraction, then give a set of guidelines for when each strategy is useful based on the characteristics of the GPU and expected contention.

Cited by 45Open access

Primitives for Contract-based Synchronization

Massimo Bartoletti, Roberto Zunino · arXiv (Cornell University) · 2010

We investigate how contracts can be used to regulate the interaction between processes. To do that, we study a variant of the concurrent constraints calculus presented in [1], featuring primitives for multi-party synchronization via contracts. We proceed in two directions. First, we exploit our primitives to model some contract-based interactions. Then, we discuss how several models for concurrency can be expressed through our primitives. In particular, we encode the pi-calculus and graph rewriting.

Cited by 0Open access

One-sided Synchronization A new Approach to Synchronization Primitives

Christian Siebert, Prof Dr, W. Rehm et al. · 2004

Todays operating systems are designed to manage multiple processes within a uniprocessor system, within several processors and even within distributed computer systems. Fundamental to this design is concurrency, especially synchronization of the activities of multiple processes. Most books on operating systems contain large chapters for this important topic. All discussed techniques therein are designed to bother all involved processes. The first part of this paper shows an overview of the most common techniques for synchronization. A new approach with a completely different design technique will be discussed afterwards. It is not always necessary to involve all processes needing sychronization. A couple of implementations for different operating systems and user/kernel mode applications will be compared to existing techniques. 1

Cited by 0

Characterizing CUDA and OpenMP Synchronization Primitives

Brandon Alexander Burtchell, Martin Burtscher · 2024

Over the last two decades, parallelism has become the primary method for speeding up computer programs. When writing parallel code, it is often necessary to use synchronization primitives (e.g., atomics, barriers, or critical sections) to enforce correctness. However, the performance of synchronization primitives depends on a variety of complex factors that non-experts may be unaware of. Since multiple primitives can typically be used to complete the same task, choosing the best is often non-trivial. In this paper, we study the performance impact of these factors by measuring the throughput of OpenMP and CUDA synchronization primitives along multiple dimensions. We highlight interesting and non-intuitive behavior that software developers should be aware of when writing parallel programs.

Cited by 2

Efficient Bounded Timestamping from Standard Synchronization Primitives

Benyamin Bashari, Ali Jamadi, Philipp Woelfel · 2023

Bounded timestamps [10, 20] allow a temporal ordering of events in executions of concurrent algorithms. They are a fundamental and well studied building block used in many shared memory algorithms. A concurrent timestamp system keeps track of m timestamps, which is usually greater or equal to the number of processes in the system, n. A process may, at any point, obtain a new timestamp, and later determine a total order of all process's most recent timestamps. Known timestamp algorithms do not scale well in the number of processes. Getting a new timestamp takes at least a linear number of steps, and a lower bound by Israeli and Li [20] implies that each timestamp needs to be represented by at least Ω(m) bits.

Cited by 2

Communication and Synchronization Primitives for Distributed Programs

Nagarajan Natarajan · IEEE Transactions on Software Engineering · 1985

A distributed program is a collection of several processes which execute concurrently, possibly in different nodes of a distributed system, and which cooperate with each other to realize a common goal. In this paper, we present a design of communication and synchronization primitives for distributed programs. The primitives are designed such that they can be provided by a kernel of a distributed operating system. An important feature of the design is that the configuration of a process, i.e., identities of processes with which the process communicates, is specified separately from the computation performed by the process. This permits easy configuration and reconfiguration of processes. We identify different kinds of communication failures, and provide distinct mechanisms for handling them. The communication primitives are not atomic actions. To enable the construction of atomic actions, two new program components, atomic agent and manager are introduced. These are devoid of policy decisions regarding concurrency control and atomic commitment. We introduce the notion of conflicts relation using which a designer can construct either an optimistic or a pessimistic concurrency control scheme. The design also incorporates primitives for constructing nested atomic actions.

Cited by 11

Synchronization Primitives on an Optical Broadcast Ring

Martin H. Davis, Jr., Umakishore Ramachandran · 1993

The latency and bandwidth of the interconnection network are the key factors that limit the performance potential of current parallel architectures. Optical interconnect technology can help alleviate both these problems once a feasible way is found for overcoming some of the technological limitiations that are hampering its widespread use in present day computers. Handling the communication requirements of a parallel architecture is an obvious application of the optical technology; however, given the properties of optics (such as space sharing) the technology has considerably more to offer than just increased bandwidth. The research reported here has investigated novel ways in which optical technology can be applied (when the technology matures) for providing direct support for synchronization constructs used in parallel program design. An optical broadcast ring interconnect architecture is proposed, and the associated access control protocols are used to implement these synchronizatio...

Cited by 0

Improving the Scalability of GPU Synchronization Primitives

Preyesh Dalmia, Rohan Mahapatra, Jeremy Intan et al. · IEEE Transactions on Parallel and Distributed Systems · 2022

General-purpose GPU applications increasingly use synchronization to enforce ordering between many threads accessing shared data. Accordingly, recently there has been a push to establish a common set of GPU synchronization primitives. However, the expressiveness of existing GPU synchronization primitives is limited. In particular the expensive GPU atomics often used to implement fine-grained synchronization make it challenging to implement efficient algorithms. Consequently, as GPU algorithms scale to millions or billions of threads, existing GPU synchronization primitives either scale poorly or suffer from livelock or deadlock issues because of heavy contention between threads accessing shared synchronization objects. We seek to overcome these inefficiencies by designing more efficient, scalable GPU barriers and semaphores. In particular, we show how multi-level sense reversing barriers and priority mechanisms for semaphores can be designed with the GPUs unique processing model in mind to improve performance and scalability of GPU synchronization primitives. Our results show that the proposed designs significantly improve performance compared to state-of-the-art solutions like CUDA Cooperative Groups and optimized CPU-style synchronization algorithms at medium and high contention levels, scale to an order of magnitude more threads, and avoid livelock in these situations unlike prior open source algorithms. Overall, across three modern GPUs the proposed barrier algorithm improves performance by an average of 33% over a GPU tree barrier algorithm and improves performance by an average of 34% over CUDA Cooperative Groups for five full-sized benchmarks at high contention levels; the new semaphore algorithm improves performance by an average of 83% compared to prior GPU semaphores.

Cited by 14

Feedback-Driven Runtime Adaptation for Synchronization Primitives

Sanjay Mishra · International Journal of Research and Applied Innovations · 2022

Modern multithreaded applications operate under highly dynamic execution conditions, where contention patterns on shared data structures vary significantly over time due to phase changes, workload skew, and platform-specific scheduling effects. Conventional synchronization primitives—such as pure spin locks, queue-based locks, or blocking mutexes—are static by design and therefore optimized for only a narrow operating regime. As a result, developers are forced to choose a single synchronization strategy that may perform well in one phase but poorly in another. This paper presents Feedback-Driven Runtime Adaptation for Synchronization Primitives, a practical framework that treats synchronization as a closed-loop control problem. Rather than proposing a new lock algorithm, we continuously observe lightweight contention telemetry, estimate runtime pressure, and adapt synchronization behavior using simple, explainable policies augmented with explicit stability constraints. We instantiate the framework for a mutex-like primitive in portable user-space C++ and evaluate it on a modern ARM-based Apple M1 system under non-stationary workloads. Experimental results demonstrate that feedback-driven adaptation induces bounded and meaningful behavioral changes under contention, trading peak throughput for improved predictability and robustness while avoiding oscillatory behavior. The results confirm that controlled runtime adaptation provides a viable alternative to static synchronization strategies in modern systems.

Cited by 0Open access