Back to search

University of Ioannina

Efficient synchronization techniques for shared memory systems

Abstract

dc:description

Overcoming the difficulty of concurrent programming has never become more urgent due to the proliferation of multicore machines and the imperative necessity of exploiting their computational power. One way to achieve this is by designing efficient concurrent data structures; common structures, like stacks and queues, are the most widely used inter-thread communication mechanisms. Additionally, synchronization techniques are required to efficiently execute, in a concurrent environment, those parts of modern applications that require significant synchronization. Although the efficient parallelization of these parts is not an easy task, Amdhal's law implies that achieving this is necessary in order to avoid significant reductions in speed-up.In this dissertation three families of highly efficient synchronization algorithms, called RedBlue, Sim and Synch are presented for executing concurrently blocks of code that have originally been programmed to be executed sequentially in asynchronous shared-memory distributed systems.We start by presenting the RedBlue family of adaptive synchronization algorithms that use common base objects (LL/SC or CAS and Read-Write) provided by the majority of the real-world machines.The first of these algorithms achieves better time complexity than all previously presented algorithms. This algorithm uses large LL/SC base objects and it comprises the keystone for the design of the other RedBlue algorithms that use smaller base objects. Specifically, the second algorithm significantly reduces the size of the required base objects. The rest of the algorithms have been designed for large objects.The Sim family of synchronization algorithms achieves at (1) getting better time complexity by using base objects other than LL/SC and read-write (i.e. Swap, AtomicAdd, etc) and (2) competing in terms of performance with the state-of-the-art synchronization algorithms (i.e. high performance spin-locks, etc. Sim is a simple synchronization algorithm with constant step complexity using a Fetch&Add additional to an LL/SC object. Sim has been implemented for a real shared-memory machine architecture. Its practical version, called P-Sim, outperforms several state-of-the-art lock-based and lock-free synchronization algorithms, while being wait-free, i.e. satisfying a stronger progress condition than all the algorithms that it outperforms.We further study blocking implementations of the combining technique with the goal of discovering where their real performance power resides and whether or how performance is impacted by ensuring some desired properties (e.g. fairness in serving requests). This is accomplished by presenting two new blocking implementations of the combining technique; the first (CC-Synch) is highly-efficient in systems that support coherent caches, whereas the second (DSM-Synch) works better in cache-less NUMA machines. In comparison to previous blocking implementations, the new implementations (1) provide bounds on the number of remote memory references (RMRs) that they perform, (2) support a stronger notion of fairness, and (3) use simpler and fewer base objects. CC-Synch and DSM-Synch achieve better performance than P-Sim as well as any other algorithm provided in the past.Several modern multicore systems organize the cores into clusters and provide fast communication within the same cluster and much slower communication across clusters. A hierarchical version of CC-Synch, called H-Synch, is presented, which exploits the hierarchical communication nature of such systems to achieve better performance. Experiments show that H-Synch significantly outperforms previous state-of-the-art hierarchical approaches.Based on P-Sim, CC-Synch, DSM-Synch, and H-Synch, we provide very efficient implementations of common shared data structures like stacks and queues. Specifically, the implementations SimStack and SimQueue that are based on P-Sim are wait-free, whereas those based on CC-Synch, DSM-Synch and H-Synch are blocking but achieve better performance than SimStack and SimQueue as well as any other algorithm provided in the past. SimStack and SimQueue are the first stack and queue implementations that satisfy both wait-freedom and high performance.

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
2013

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Kallimanis, Nikolaos
  • Καλλιμάνης, Νικόλαος

Subjects

dc:subject × 24

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/30106

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Kallimanis, Nikolaos; Καλλιμάνης, Νικόλαος. Efficient synchronization techniques for shared memory systems. University of Ioannina, 2013. http://hdl.handle.net/10442/hedi/30106