Query: Synchronization mechanisms on modern multi-core architectures

Candidate papers:

abstract: While the semiconductor industry has provided us with powerful systems for personal supercomputing, how to efficiently harness the computing power of these systems still remains a major unsolved problem. This challenge must be approached by simultaneously solving the synchronization problem and the parallel programmability problem. This paper reviews the synchronization issues in modern parallel computer architectures, surveys the state of the art approaches used to alleviate these problems, and proposes our Request Store Forward (RSF) model of synchronization. This model splits the atomic synchronization operations into two phases, thus freeing the processing elements from polling operations. Finally, we show how we could learn from nature and improve the overall system performance by closely coupling peripheral computing units and functional units.
author_names: Shaoshan Liu

Jean-Luc Gaudiot
title: Synchronization Mechanisms on Modern Multi core Architectures
venue: Asia Pacific Computer Systems Architecture Conference
year: 2007

abstract: The goal of this paper is to review some of the several approaches that have been proposed in recent years to address the synchronization problems in both multiprocessor and the multi core processor. Here also propose some synchronization model to address the challenges faced by synchronization mechanisms on modern parallel computing architectures. Shared memory multiprocessors are frequently used as compute servers with multiple parallel applications executing at the same time. In such environments, the efficiency of a parallel application can be significantly affected by the operating system scheduling policy. In this paper, we use detailed simulation studies to evaluate the performance of several different scheduling strategies, these include regular priority scheduling, co scheduling or gang scheduling, process control with processor partitioning, handoff scheduling, and affinity based scheduling. We also explore tradeoffs between the use of busy waiting and blocking synchronization primitives and their interactions with the scheduling strategies.
author_names: M Rahman
title: Process synchronization in multiprocessor and multi core processor
venue: 2012 International Conference on Informatics, Electronics Vision (ICIEV)
year: 2012

abstract: The use of efficient synchronization mechanisms is crucial for implementing fine grained parallel programs on modern shared cache multi core architectures. In this paper we study this problem by considering Single Producer/Single Consumer (SPSC) coordination using unbounded queues. A novel unbounded SPSC algorithm capable of reducing the row synchronization latency and speeding up Producer Consumer coordination is presented. The algorithm has been extensively tested on a shared cache multi core platform and a sketch proof of correctness is presented. The queues proposed have been used as basic building blocks to implement the FastFlow parallel framework, which has been demonstrated to offer very good performance for fine grain parallel applications.
author_names: Marco Aldinucci

Marco Danelutto

Peter Kilpatrick

Massimiliano Meneghin

Massimo Torquati
title: An Efficient Unbounded Lock Free Queue for Multi core Systems
venue: Euro Par
year: 2012

abstract: The use of efficient synchronization mechanisms is crucial for implementing fine grained parallel programs on modern shared cache multi core architectures. In this paper we study this problem by considering Single Producer/Single Consumer (SPSC) coordination using unbounded queues. A novel unbounded SPSC algorithm capable of reducing the row synchronization latency and speeding up Producer Consumer coordination is presented. The algorithm has been proven correctand extensively tested on a shared cache multi core platform. The queues proposed have been used as basic building blocks to implement the FastFlow parallel framework, which has been demonstrated to offer very good performance for fine grain parallel applications.
author_names: Marco Aldinucci

Marco Danelutto

Peter Kilpatrick

Massimiliano Meneghin

Massimo Torquati
title: An Efficient Synchronisation Mechanism for Multi Core Systems
year: 2012

abstract: Although Ant Colony Systems (ACS) have gained much attention in last two decades but slow execution and convergence speed are still two challenges for these metaheuristic algorithms. Many parallel implementations have been proposed for faster execution. However, most of available implementations use coarse grained synchronization mechanisms that are not efficient and scalable. In this work, we have taken a fine grained (ant level) approach that is more efficient and scalable. We have used traveling salesman problem as a test case and have presented a parallel finegrained implementation for shared memory multi core systems. Our experimental results show that our proposed parallel implementation can achieve considerably higher speedup values on modern multicore processors. General Terms Optimization, Parallel Processing.
author_names: Ali Hadian

Saeed Shahrivari

Behrouz Minaei-Bidgoli
title: Fine grained Parallel Ant Colony System for Shared Memory Architectures
year: 2012

abstract: Whether to use multiple threads in one process (MPI+X) or multiple processes (pure MPI) has long been an important question in HPC. Techniques like in situ analysis and visualization further complicate matters, as it may be very difficult to couple the different components in a way that would allow them to run in the same process. Combined with the growing interest in task based programming models, which often rely on fine grained tasks and synchronization, a question arises: Is it possible to run two tightly coupled task based applications in two separate processes efficiently or do they have to be combined into one application? Through a range of experiments on the latest Intel Xeon Scalable (Skylake) and AMD EPYC (Zen) many core architectures, we have compared performance of fine grained synchronization and data exchange between threads in the same process and threads in two different processes. Our experiments show that although there may be a small price to pay for having two processes, it is still possible to achieve very good performance. The key factors are utilizing shared memory, selecting the right thread affinity, and carefully selecting the way the processes are synchronized.
author_names: Jiri Dokulil

Siegfried Benkner
title: Exploring the Performance of Fine Grained Synchronization and Data Exchange Across Process Boundaries on Modern Multi core Architectures
venue: ICCS
year: 2019

abstract: In this paper, we propose a new approach for the predictability and optimality of the inter core communication and execution of tasks allocated on different cores of multicore architectures. Our approach is based on the execution of synchronous programs written in the ForeC programming language on deterministic architectures called PREcision Timed. The originality of the work resides in the time triggered model of computation and communication that allows for a very precise control over the thread execution. Synchronization is done via configurable Time Division Multiple Access (TDMA) arbitrations where the optimal size and offset of the time slots are computed to reduce the inter core synchronization costs. We implemented a robotic application and simulated it using MORSE, a robotic simulation environment. Results show that the model we propose guarantees time predictable inter core communication, the absence of concurrent accesses (without relying on hardware mechanisms) and allows for optimized execution throughput.
author_names: Nicolas Hili

Alain Girault

Eric Jenn
title: Worst Case Reaction Time Optimization on Deterministic Multi Core Architectures with Synchronous Languages
venue: 2019 IEEE 25th International Conference on Embedded and Real Time Computing Systems and Applications (RTCSA)
year: 2019

abstract: Ever since mass market processors transitioned from single core to multi core architectures, software could no longer rely on an increase in sequential performance for an increase in software performance. Now, developing high performance software on multi core architectures requires to exploit the apparent parallelism. Concurrent programming is the main tool for developing such software, but programmers struggle to create correct and scalable concurrent systems. It is argued in this thesis Communicating Sequential Processes (CSP) is a great model for creating correct and expressive concurrent systems. Further, it is argued combining the parallel nature of CSP with a dynamic multithreaded runtime system sets the foundation for creating high performant and scalable software for multicore architectures. This thesis details the development of ProXC+ a CSP influenced concurrency library for modern C+ which is built around dynamic multithreading. Dynamic multithreading is implemented as a collection of lightweight processes cooperatively scheduled on multiple schedulers. The runtime system follows the hybrid threading model, where processes are implemented as user threads, and each runtime scheduler runs on its own kernel thread. Runtime schedulers employ randomized work stealing for load balancing ready processes to idle schedulers. A detailed design and implementation of ProXC+ is presented, with focus on dynamic multithreading. New and existing algorithms are described, mostly for how process management, inter process communication and synchronization is administered by the runtime schedulers. A series of benchmarks with various degrees of parallelism is performed. ProXC+ yields promising performance results, however some issues with the work stealing algorithm are highlighted and discussed. ProXC+ is concluded as a successful project, providing expressive and correct abstractions for creating concurrent programs and is able to exploit the parallelism in multi core architectures. Some potential candidates for future work is outlined, including implementing support for networking. The ProXC+ library is publicly released as an open source project with an MIT license, available free of charge on GitHub.
author_names: Edvard Severin Pettersen
title: ProXC+ A CSP inspired Concurrency Library for Modern C+ with Dynamic Multithreading for Multi Core Architectures
year: 2017

abstract: Abstract Modern processors contain several specific hardware modules and multiple cores to ensure performance for a wide range of applications. In this context, FPGAs are frequently used as the implementation platform, since they offer architecture customization and fast time to market. However, many of them may not have the needed resources to implement all the necessary features, because of costs or complexity of the system to be implemented. When some needed functionalities do not fit in the target, they must be mapped into the much slower software domain. In this work, we exploit the fact these designs usually underuse their available BRAMs and propose a low cost hardware based function reuse mechanism for FPGAs, recovering some of the performance lost from the software part of applications that could not be implemented in hardware logic, with minimal impact on LUT usage. This is achieved by saving the inputs and outputs of the most frequently executed functions in a BRAM based reuse table, so the next function executions with the same arguments can be skipped. This mechanism supports both precise and approximate modes and is evaluated with a 4 issue VLIW processor implemented in HDL, also considering a multi core environment. Precise reuse, in single and multi core scenarios, is assessed by running applications that use a software library to emulate floating point operations. Approximate reuse is evaluated over a single core image processing application that tolerates a certain level of error. Our scheme achieves 1.39 x geomean speedup in the precise single core, while the multi core case demonstrates application improvements from 1.25 x to 1.9 x when we start sharing the reuse table. In the approximate scenario, we achieve 1.52 x speedup with less than 10% error.
author_names: Pedro Henrique Exenberger Becker

Anderson Luiz Sartor

Marcelo Brandalero

A C S Beck
title: BRAM based function reuse for multi core architectures in FPGAs
venue: Microprocess. Microsystems
year: 2018

abstract: Modern high performance server systems are typically built as several multi core chips put together in a single system. Each chip is connected to its local memory via an integrated memory controller (IMC) behaving as a node and hence the single machine behaving as non uniform memory architecture (NUMA) Various user level run time systems adapt work stealing load balancing technique in multi core processors. The work stealing run times have to be aware of the topology of the processor on which they are running. Work stealing run times on multi core processors typically rely on lock based synchronization to guarantee the coherency of shared mutable state. Synchronization constructs such as mutex locks, condition variables, and barriers are extensively used in implementation of these user level work stealing run times. The locality of these lock variables in multi socket NUMA processors has considerable impact on the performance of these run time systems. This paper studies the effect of locality of these synchronization constructs and proposes NUMA awareness to them. The proposed methodology is implemented using a source to source translator of OpenMP run time, evaluated using OpenMP microbenchmark programs.
author_names: B Vikranth

Rajeev Wankar

C Raghavendra Rao
title: Affinity Aware Synchronization in Work Stealing Run Times for NUMA Multi core Processors
year: 2019