3 years ago

Parallel Combining: Making Use of Free Cycles.

Vitaly Aksenov, Petr Kuznetsov

There are two intertwined factors that affect performance of concurrent data structures: the ability of processes to access the shared data in parallel and the cost of synchronization. It has been observed that for a class of "concurrency-averse" data structures, the use of fine-grained locking for parallelization does not pay off: an implementation based on a single global lock outperforms fine-grained solutions. The combining paradigm exploits this by ensuring that a thread holding the global lock combines requests and then executes the combined requests sequentially on behalf of other (waiting) concurrent threads. The downside here is that the waiting threads are unused even when concurrently applied requests can be potentially performed in parallel.

In this paper, we propose parallel combining, a technique that leverages the computational power of waiting threads. The idea is that the combiner thread assigns waiting threads to perform requests synchronously using a parallel algorithm. We discuss two applications of the technique. First, we use it to transform a sequential data structure into a concurrent one optimized for read-dominated workloads. Second, we use it to construct a concurrent data structure from a batched one that allows synchronous invocations of sets of operations. In both cases, we obtain significant performance gains with respect to the state-of-the-art algorithms

Publisher URL: http://arxiv.org/abs/1710.07588

DOI: arXiv:1710.07588v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.