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

25th International Conference on Parallel and Distributed Computing (Euro-Par)

作者： van Der Grinten, Alexander Angriman, Eugenio Meyerhenke, Henning Humboldt Univ Dept Comp Sci Berlin Germany

ISBN: (纸本)9783030294007;9783030293994

Approximation via sampling is a widespread technique whenever exact solutions are too expensive. In this paper, we present techniques for an efficient parallelization of adaptive (a.k.a. progressive) sampling algorithms on multi-threaded shared-memory machines. Our basic algorithmic technique requires no synchronization except for atomic load-acquire and store-release operations. It does, however, require O(n) memory per thread, where n is the size of the sampling state. We present variants of the algorithm that either reduce this memory consumption to O(1) or ensure that deterministic results are obtained. Using the KADABRA algorithm for betweenness centrality (a popular measure in network analysis) approximation as a case study, we demonstrate the empirical performance of our techniques. In particular, on a 32-core machine, our best algorithm is 2.9x faster than what we could achieve using a straightforward OpenMP-based parallelization and 65.3x faster than the existing implementation of KADABRA.

关键词： Parallel approximation algorithms Adaptive sampling wait-free algorithms Betweenness centrality

来源：评论

学校读者我要写书评

暂无评论

Are Lock-free Concurrent algorithms Practically wait-free?

引用

JOURNAL OF THE ACM 2016年第4期63卷 31-31页

作者： Alistarh, Dan Censor-Hillel, Keren Shavit, Nir ETH Inst Theoret Informat CAB J 21-5Univ Str 6 CH-8092 Zurich Switzerland Technion Dept Comp Sci IL-32000 Haifa Israel MIT 32 Vassar St32-G622 Cambridge MA 02139 USA Tel Aviv Univ Comp Sci & Artificial Intelligence Lab Stata Ctr 32 Vassar St32-G622 Cambridge MA 02139 USA

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. Although obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most nonblocking commercial code is only lock-free. This article suggests a simple solution to this problem. We show that for a large class of lock-free algorithms, under scheduling conditions that approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can continue to design simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes to the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1 but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst-case adversary, in a stochastic model capturing their expected asymptotic behavior.

关键词： Distributed computing shared memory wait-free algorithms lock-free algorithms progress properties schedulers

来源：评论

学校读者我要写书评

暂无评论

Counting-based impossibility proofs for set agreement and renaming

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2016年 87卷 1-12页

作者： Attiya, Hagit Paz, Ami Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

Set agreement and renaming are two tasks that allow processes to coordinate, even when agreement is impossible. In k-set agreement, n processes must decide on at most k of their input values. While n-set agreement is trivially wait-free solvable by each process deciding on its input, (n - 1)-set agreement is not wait-free solvable. In M-renaming, processes must decide on distinct names in a range of size M. For any number n of processes, (2n - 1)-renaming is wait-free solvable, but surprisingly, (2n - 2)-renaming is wait-free solvable if and only if n is not a prime power;the only previous lower bound on the number of names necessary for renaming, when a is not a prime power, is n + 1. In adaptive renaming, M decreases when the number p of participants in the execution decreases. It is known that (2p - 1)-adaptive renaming is wait-free solvable, while (2p - left perpendicularp/n-1right perpendicular)-adaptive renaming is not. This paper presents counting-based proofs for the above mentioned impossibility results: n processes can wait-free solve neither (n - 1)-set agreement nor (2p - left perpendicularp/n-1right perpendicular)-adaptive renaming;if n is a prime power, n processes cannot wait-free solve (2n - 2)-renaming. For an arbitrary number of processes, we give a lower bound for renaming, by reduction from renaming for a different number of processes, and relying on the distribution of prime numbers. Our proofs combine simple operational properties of a restricted set of executions with elementary counting arguments to show the existence of an execution violating the task's conditions. This makes the proofs easier to understand, verify, and, we hope, extend. (C) 2015 Elsevier Inc. All rights reserved.

关键词： Lower bounds wait-free algorithms Adaptive and nonadaptive renaming Weak and strong symmetry breaking

来源：评论

学校读者我要写书评

暂无评论

Are Lock-free Concurrent algorithms Practically wait-free? 14

Are Lock-Free Concurrent Algorithms Practically Wait-Free?

引用

46th Annual ACM Symposium on Theory of Computing (STOC)

作者： Alistarh, Dan Censor-Hillel, Keren Shavit, Nir MSR Cambridge Cambridge England Technion Haifa Israel MIT Cambridge MA 02139 USA Tel Aviv Univ Tel Aviv Israel MIT CSAIL Cambridge MA 02139 USA

ISBN: (纸本)9781450327107

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is generally a very complex task, and the resulting algorithms are not always efficient. While obtaining efficient wait-free algorithms has been a long-time goal for the theory community, most non-blocking commercial code is only lock-free. This paper suggests a simple solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a general subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

关键词： Distributed computing shared memory wait-free algorithms lock-free algorithms progress properties schedulers

来源：评论

学校读者我要写书评

暂无评论

Brief Announcement: Are Lock-free Concurrent algorithms Practically wait-free? 14

Brief Announcement: Are Lock-Free Concurrent Algorithms Prac...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Alistarh, Dan Censor-Hillel, Keren Shavit, Nir Microsoft Res Redmond WA 98052 USA Technion Haifa Israel MIT Cambridge MA 02139 USA Tel Aviv Univ Tel Aviv Israel

ISBN: (纸本)9781450329446

Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes. To the best of our knowledge, this is the first attempt to analyze progress conditions, typically stated in relation to a worst case adversary, in a stochastic model capturing their expected asymptotic behavior.

关键词： Distributed computing shared memory wait-free algorithms lock-free algorithms progress properties schedulers

来源：评论

学校读者我要写书评

暂无评论

An Efficient Unbounded Lock-free Queue for Multi-core Systems

引用

18th International Conference on Euro-Par Parallel Processing

作者： Aldinucci, Marco Danelutto, Marco Kilpatrick, Peter Meneghin, Massimiliano Torquati, Massimo Univ Turin Dept Comp Sci I-10124 Turin Italy Univ Pisa Dept Comp Sci Pisa Italy Queens Univ Belfast Dept Comp Sci Belfast Antrim North Ireland IBM Dublin Res Lab Dublin Ireland

ISBN: (纸本)9783642328206

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.

关键词： Lock-free algorithms wait-free algorithms bounded and unbounded SPSC queues cache-coherent multi-cores

来源：评论

学校读者我要写书评

暂无评论

wait-free Queues With Multiple Enqueuers and Dequeuers 11

Wait-Free Queues With Multiple Enqueuers and Dequeuers

引用

16th ACM Symposium on Principles and Practice of Parallel Programming

作者： Kogan, Alex Petrank, Erez Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9781450301190

The queue data structure is fundamental and ubiquitous. Lock-free versions of the queue are well known. However, an important open question is whether practical wait-free queues exist. Until now, only versions with limited concurrency were proposed. In this paper we provide a design for a practical wait-free queue. Our construction is based on the highly efficient lock-free queue of Michael and Scott. To achieve wait-freedom, we employ a priority-based helping scheme in which faster threads help the slower peers to complete their pending operations. We have implemented our scheme on multicore machines and present performance measurements comparing our implementation with that of Michael and Scott in several system configurations.

关键词： concurrent queues wait-free algorithms algorithms Performance

来源：评论

学校读者我要写书评

暂无评论

Synchronization for fast and reentrant operating system kernel tracing

引用

SOFTWARE-PRACTICE & EXPERIENCE 2010年第12期40卷 1053-1072页

作者： Desnoyers, Mathieu Dagenais, Michel R. Ecole Polytech Montreal Dept Comp & Software Engn Montreal PQ H3C 3A4 Canada

To effectively trace an operating system, a performance monitoring and debugging infrastructure needs the ability to trace various execution contexts. These contexts range from kernel running as a thread to Non-Maskable Interrupt (NMI) contexts. Given that any part of the kernel infrastructure used by a kernel tracer could lead to infinite recursion if traced, and because most kernel primitives require synchronization unsuitable for some execution contexts, all interactions of the tracing code with the existing kernel infrastructure must be considered in order to correctly inter-operate with the existing operating system kernel. This paper presents a new low overhead tracing mechanism and motivates the choice of synchronization sequences suitable for operating system kernel tracing, namely local atomic instructions as main buffer synchronization primitive and the Read-Copy Update (RCU) mechanism to control tracing. It also proposes a wait-free algorithm extending the time-base needed by the tracer to 64-bit on architectures that lack hardware 64-bit time-base support. Copyright (C) 2010 John Wiley & Sons, Ltd.

关键词： tracing operating system synchronization wait-free algorithms low overhead clock

来源：评论

学校读者我要写书评

暂无评论

On the Time-Complexity of Robust and Amnesic Storage

On the Time-Complexity of Robust and Amnesic Storage

引用

12th International Conference on Principles of Distributed Systems

作者： Dobre, Dan Majuntke, Matthias Suri, Neeraj Tech Univ Darmstadt D-64289 Darmstadt Germany

ISBN: (纸本)9783540922209

We consider wait-free implementations of a regular read/write register for unauthenticated data using a collection of 3t + k base objects, t of which can be subject to Byzantine failures. We focus on amnesic algorithms that store only a limited number of values in the base objects. In contrast, non-amnesic algorithms store an unbounded number of values, which can eventually lead to problems of space exhaustion. Lower bounds on the time-complexity of read and write operations are currently met only by non-amnesic algorithms. In this paper, we show for the first time that amnesic algorithms can also meet these lower bounds. We do this by giving two amnesic constructions: for k = 1, we show that the lower bound of two communication rounds is also sufficient for every read operation to complete and for k = t + 1 we show that the lower bound of one round is also sufficient for every operation to complete.

关键词： distributed storage Byzantine failures wait-free algorithms

来源：评论

学校读者我要写书评

暂无评论

Generalized irreducibility of consensus and the equivalence of t-resilient and wait-free implementations of consensus

引用

SIAM JOURNAL ON COMPUTING 2004年第2期34卷 333-357页

作者： Chandra, T Hadzilacos, V Jayanti, P Toueg, S IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Univ Toronto Dept Comp Sci Toronto ON MSS 3H5 Canada Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA

We study the consensus problem, which requires multiple processes with different input values to agree on one of these values, in the context of asynchronous shared memory systems. Prior research focussed either on t-resilient solutions of this problem (which must be correct even if up to t processes crash) or on wait-free solutions (which must be correct despite the crash of any number of processes). In this paper, we show that these two forms of solvability are closely related. Specifically, for all n > t >= 2 and all sets S of shared object types (that include simple read/write registers), there is a t-resilient solution to n-process consensus using objects of types in S if and only if there is a wait-free solution to (t+1)-process consensus using objects of types in S. Our proof of this equivalence uses another result derived in this paper, which is of independent interest. Roughly speaking, this result states that a wait-free solution to (n-1)-process consensus is never necessary in designing a wait-free solution to n-process consensus, regardless of the types of objects available. More precisely, for all n >= 2 and all sets S of shared object types (that include simple read/write registers), if there is a wait-free solution to n-process consensus that uses a wait-free solution to (n-1)-process consensus and objects of types in S, then there is a wait-free solution to n-process consensus that uses only objects of types in S.

关键词： asynchronous distributed computation consensus wait-free algorithms fault tolerant algorithms impossibility results

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：