检索结果-内蒙古大学图书馆

Accelerating wait-free algorithms: Pragmatic Solutions on Cache-Coherent Multicore Architectures

IEEE ACCESS 2019年 7卷 74653-74669页

作者： Wang, Junchang Jin, Qi Fu, Xiong Li, Yun Shi, Peichang Nanjing Univ Posts & Telecommun Sch Comp Sci Nanjing 210023 Jiangsu Peoples R China Jiangsu Key Lab Big Data Secur & Intelligent Proc Nanjing 210023 Jiangsu Peoples R China Natl Univ Def Technol Coll Comp Sci Changsha 410073 Hunan Peoples R China

Parallelizing performance-critical applications are of critical importance for harnessing the power of multicore processors, which are now ubiquitous. Even though wait-free algorithms offer the appeal of completing each operation of a parallelized application in a finite number of steps, high-performance wait-free algorithms at high levels of concurrency are still rare. In this paper, we demonstrate one primary reason for this inefficiency: existing wait-free algorithms are not optimized for processors' caches and write buffers, two key components in modern hardware to accelerate memory accesses. As an example, a wait-free multi-producer-single-consumer queue algorithm, which faces common performance problems of wait-free algorithms, is studied in this paper. We accelerate the queue algorithm by (1) allowing producers to buffer enqueue requests in their local buffers and to write them into the shared queue in batch, to exhibit the spatial locality of the program, and (2) eliminating expensive atomic operations, by giving up some degree of internal consistency to avoid write buffers being drained frequently. The outcome is a write-buffer and cache-friendly queue algorithm which is wait-free and efficient on off-the-shelf multicore processors. The experiments show that the optimized queue algorithm outperforms prior queue algorithms on three different architectures (x86, Power8, and ARMv8). On x86, it outperforms WFQueue, the state-of-the-art solution, by 2-3x, and outperforms CCQueue, the representative of combining solution, by 4-12x. Applying the techniques presented in this paper to other wait-free algorithms is straightforward;our queue example demonstrates that these techniques can be applied to other wait-free algorithms while maintaining the control flow of the original algorithms without dramatic changes.

关键词： Multicore wait-free algorithm MPSC queue

来源：评论

学校读者我要写书评

暂无评论

In search of the holy grail: Looking for the weakest failure detector for wait-free set agreement

引用

10th International Conference on Principles of Distributed Systems

作者： Raynal, Michel Travers, Corentin Univ Rennes 1 IRISA Campus Beaulieu F-35042 Rennes France

ISBN: (纸本)9783540499909

Asynchronous failure detector-based set agreement algorithms proposed so far assume that all the processes participate in the algorithm. This means that (at least) the processes that do not crash propose a value and consequently execute the algorithm. It follows that these algorithms can block forever (preventing the correct processes from terminating) when there are correct processes that do not participate in the algorithm. This paper investigates the wait-free set agreement problem, i.e., the case where the correct participating processes have to decide a value whatever the behavior of the other processes (i.e., the processes that crash and the processes that are correct but do not participate in the algorithm). The paper presents a wait-free set agreement algorithm. This algorithm is based on a leader failure detector class that takes into account the notion of participating processes. Interestingly, this algorithm enjoys a first class property, namely, design simplicity.

关键词： asynchronous algorithm asynchronous system atomic register consensus leader oracle participating process set agreement shared object wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

From adaptive renaming to set agreement

引用

THEORETICAL COMPUTER SCIENCE 2009年第14期410卷 1328-1335页

作者： Gafni, Eli Mostefaoui, Achour Raynal, Michel TraverS, Corentin IRISA F-35042 Rennes France Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA

The adaptive M-renaming problem consists of providing processes with a new name taken from a name space whose size M depends only oil the number p of processes that participate in the renaming (and not oil the total number n of processes that could ask for a new name). The k-set agreement problem allows each process that proposes a value to decide a proposed Value in such a way that at most k different values are decided. In an asynchronous system prone to up to t process crash failures. and where processes can cooperate by accessing atomic read/write registers only, the best that can be done is a renaming space of size M = p + t. In the same setting, the k-set agreement problem cannot be solved when t >= k. This paper focuses oil the way a solution to the adaptive renaming problem can help in solving the k-set agreement problem when t >= k. It has two contributions. Considering the case k = t (1 <= t < n). the first contribution is a t-resilient algorithm that solves the k-set agreement problem from any adaptive (p + k - 1)-renaming algorithm. The second contribution considers the case k < t. It shows that there is no such wait-free algorithm when k < n/2 (wait-free means t = n - 1). So, while a solution to the adaptive (,p + k - 1)renaming problem allows t-resiliently solving the k-set agreement problem despite t = k failures, when k < t such an additional power becomes useless for the values of n > 2k (i.e. adaptive (p + k - 1)-renaming allows progressing from k > t to k = t, but does not allow bypassing the "k = t" frontier when n > 2k). (C) 2008 Elsevier B.V. All rights reserved.

关键词： Adaptive renaming Asynchronous algorithm Atomic register Atomic snapshot Participating process Reduction Set agreement Shared object t-resilient algorithm wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Help when needed, but no more: Efficient read/write partial snapshot

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第1期72卷 1-12页

作者： Imbs, Damien Raynal, Michel Inst Univ France F-35042 Rennes France Univ Rennes 1 IRISA F-35042 Rennes France

An atomic snapshot object is an object that can be concurrently accessed by asynchronous processes prone to crash. It is made of m components (base atomic registers) and is defined by two operations: an update operation that allows a process to atomically assign a new value to a component and a snapshot operation that atomically reads and returns the values of all the components. To cope with the net effect of concurrency, asynchrony and failures, the algorithm implementing the update operation has to help concurrent snapshot operations so that they always terminate. This paper is on partial snapshot objects. Such an object provides a snapshot operation that can take any subset of the components as input parameter, and atomically reads and returns the values of this subset of components. The paper has two contributions. The first is the introduction of two properties for partial snapshot object algorithms, called help-locality and freshness. Help-locality requires that an update operation helps only the concurrent partial snapshot operations that read the component it writes. When an update of a component r helps a partial snapshot, freshness requires that the update provides the partial snapshot with a value of the component r that is at least as recent as the value it writes into that component. (No snapshot algorithm proposed so far satisfies these properties). The second contribution consists of an update and a partial snapshot algorithm that are wait-free, linearizable and satisfy the previous efficiency properties. Interestingly, the principle that underlies the proposed algorithms is different from the one used so far, namely, it is based on the "write first, and help later" strategy. An improvement of the previous algorithms is also presented. Based on LL/SC atomic registers (instead of read/write registers), this improvement decreases the number of base registers from O(n(2)) to O(n). This shows an interesting tradeoff relating the synchronization power of

关键词： Adaptive algorithm Asynchronous shared memory system Asynchrony Atomicity Efficiency Concurrency Linearizability LL/SC atomic registers Locality Partial snapshot Process crash Read/write atomic register wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Shared Memory Synchronization in Presence of Failures: an Exercise-based Introduction for the Sophomore

Shared Memory Synchronization in Presence of Failures: an Ex...

引用

3rd International Conference on Complex, Intelligent and Software Intensive Systems

作者： Raynal, Michel Univ Rennes IRISA F-35042 Rennes France

ISBN: (纸本)9781424435692

In the recent past, lots of papers have addressed synchronization in asynchronous shared memory systems prone to process crashes. Unfortunately, to date, nearly all these results have appeared only in theory-oriented journals and conferences, very few being presented and studied in textbooks. This aim of this paper is to give a flavor of a few of these fundamental results. To that end, it considers three problems and presents solutions proposed to solve them, emphasizing the basic concepts and techniques these solutions rely on. These problems have been selected because they address distinct facets of synchronization in presence of failures. So, the spirit of this introductory paper is mainly pedagogical (with an algorithmic taste).

关键词： Asynchronous shared memory system Compare&Swap Load-Linked/Store-conditional Process crash Read/Write atomic register Synchronization Swap Test&Set wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Trying to Unify the LL/SC Synchronization Primitive and the Notion of a Timed Register

Trying to Unify the LL/SC Synchronization Primitive and the ...

引用

26th IEEE International Conference on Advanced Information Networking and Applications (AINA)

作者： Imbs, Damien Raynal, Michel IRISA F-35042 Rennes France

ISBN: (纸本)9780769546513

The aim of this short paper is to show that both the LL/SC (Linked Load/Store Conditional) synchronization primitive and the notion of a Timed register can be seen as two instances of a general abstract synchronization object type that we called a predicate-based read/ write synchronization object. More precisely, LL/SC corresponds to its time-free instance while a timed register corresponds to its timed instance. It follows that the notion of a predicate-based read/ write synchronization object constitutes a unifying notion that allows for a deeper insight into synchronization objects proposed for multicore architectures.

关键词： Asynchronous shared memory system Atomicity Compare&swap Consensus object Linked Load/Store Conditional Modularity Multicore Process crash Read/Write atomic register Synchronization objects Timed registers wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Help When Needed, But No More: Efficient Read/Write Partial Snapshot

引用

23rd International Symposium on Distributed Computing (DISC)

作者： Imbs, Damien Raynal, Michel Univ Rennes 1 IRISA F-35042 Rennes France

ISBN: (纸本)9783642043543

An atomic snapshot object is in object that can be concurrently accessed by asynchronous processes prone to crash. it is made of m components (base atomic registers) and is defined by two operations;an update operation that allows a process to atomically assign a new value to a component and a snapshot operation that atomically reads and returns the values of all the components. To cope with the net effect of concurrency, asynchrony and failures, the algorithm implementing the update operation hits to help concurrent snapshot operations so that they always terminate. This paper is on partial snapshot objects. Such an object provides a snapshot operation that can take any subset of the components as input parameter, and atomically reads and returns the values of this subset of components. The paper has two contributions. The first is the introduction of two properties for partial snapshot object algorithms, called help-locality and freshness. Help-locality requires that an Update operation helps only the concurrent partial snapshot operations that read the component it writes. When an update of a component tau helps a partial snapshot, freshness requires that the update Provides the partial snapshot with a value of the component v that is at least as recent its the value it writes into that component. (No snapshot algorithm proposed so far satisfies these properties.) The second contribution Consists of an update and a partial snapshot algorithms that are wait-free, linearizable and satisfy the previous efficiency properties. Interestingly, the principle that Underlies the proposed algorithms is different front the One Used so far. namely it is based on the "write first, and help later" strategy. An improvement of the previous algorithms is also presented. Based on LL/SC atomic registers (instead of read/write registers) this improvement decreases the number of base registers front O(n(2)) to O(n). This shows an interesting tradeoff relating the synchronization power

来源：评论

学校读者我要写书评

暂无评论

FFQ: A Fast Single-Producer/Multiple-Consumer Concurrent FIFO Queue 31

FFQ: A Fast Single-Producer/Multiple-Consumer Concurrent FIF...

引用

31st IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Arnautov, Sergei Fetzer, Christof Trach, Bohdan Felber, Pascal Tech Univ Dresden Dresden Germany Univ Neuchatel Neuchatel Switzerland

ISBN: (纸本)9781538639146

With the spreading of multi-core architectures, operating systems and applications are becoming increasingly more concurrent and their scalability is often limited by the primitives used to synchronize the different hardware threads. In this paper, we address the problem of how to optimize the throughput of a system with multiple producer and consumer threads. Such applications typically synchronize their threads via multiproducer/ multi-consumer FIFO queues, but existing solutions have poor scalability, as we could observe when designing a secure application framework that requires high-throughput communication between many concurrent threads. In our target system, however, the items enqueued by different producers do not necessarily need to be FIFO ordered. Hence, we propose a fast FIFO queue, FFQ, that aims at maximizing throughput by specializing the algorithm for single-producer/multiple-consumer settings: each producer has its own queue from which multiple consumers can concurrently dequeue. Furthermore, while we provide a wait-free interface for producers, we limit ourselves to lockfree consumers to eliminate the need for helping. We also propose a multi-producer variant to show which synchronization operations we were able to remove by focusing on a single producer variant. Our evaluation analyses the performance using microbenchmarks and compares our results with other state-of-the-art solutions: FFQ exhibits excellent performance and scalability.

关键词： concurrent FIFO queue concurrent queue FIFO queue lock-free algorithm SPMC queue wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

Test&Set, adaptive renaming and set agreement: a guided visit to asynchronous computability

Test&Set, adaptive renaming and set agreement: a guided visi...

引用

26th IEEE International Symposium on Reliable Distributed Systems

作者： Gafni, Eli Raynal, Michel Travers, Corentin Univ Calif Los Angeles Dept Comp Sci Los Angeles CA 90095 USA IRISA Campus Beaulieu F-35042 Rennes France

ISBN: (纸本)9780769529950

An important issue in fault-tolerant asynchronous computing is the respective power of an object type with respect to another object type. This question has received a lot of attention, mainly in the context of the consensus problem where a major advance has been the introduction of the consensus number notion that allows ranking the synchronization power of base object types (atomic registers, queues, test&set objects, compare&swap objects, etc.) with respect to the consensus problem. This has given rise to the well-known Herlihy's hierarchy. Due to its very definition, the consensus number notion is irrelevant for studying the respective power of object types that are too weak to solve consensus for an arbitrary number of processes (these objects are usually called subconsensus objects). Considering an asynchonous system made up of n processes prone to crash, this paper addresses the power of such object types, namely, the k-test&set object type, the k-set agreement object type, and the adaptive M-renaming object type for M = 2p - [p/k] and M = min (2p - 1, p + k - 1), where p <= n is the number of processes that want to acquire a new name. It investigates their respective power stating the necessary and sufficient conditions to build objects of any of these types from objects of any of the other types. More precisely, the paper shows that (1) these object types define a strict hierarchy when k not equal 1, n - 1, (2) they all are equivalent when k = n - 1, and (3) they all are equivalent except k-set agreement that is stronger when k = 1 not equal n - 1 (a side effect of these results is that that the consensus number of the renaming problem is 2.).

关键词： adaptive renaming asynchronous system atomic register atomic snapshot process crash reduction set agreement shared memory test&set t-resilience wait-free algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：