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

34th Annual ACM Symposium on Principles of Distributed Computing (PODC)

作者： Alistarh, Dan Sauerwald, Thomas Vojnovic, Milan Microsoft Res Cambridge England Univ Cambridge Comp Lab Cambridge England

ISBN: (纸本)9781450336178

In this work, we consider the following random process, motivated by the analysis of lock-free concurrent algorithms under high memory contention. In each round, a new scheduling step is allocated to one of n threads, according to a distribution p = (p(1), p(2),..., p(n)), where thread i is scheduled with probability pi. When some thread first reaches a set threshold of executed steps, it registers a win, completing its current operation, and resets its step count to 1. At the same time, threads whose step count was close to the threshold also get reset because of the win, but to 0 steps, being penalized for almost winning. We are interested in two questions: how often does some thread complete an operation (system latency), and how often does a specific thread complete an operation (individual latency)? We provide asymptotically tight bounds for the system and individual latency of this general concurrency pattern, for arbitrary scheduling distributions p. Surprisingly, a simple characterization exists: in expectation, the system will complete a new operation every Theta(1/parallel to p parallel to 2) steps, while thread i will complete a new operation every Theta(parallel to p parallel to 2/p(i)(2)) steps. The proof is interesting in its own right, as it requires a careful analysis of how the higher norms of the vector p influence the thread step counts and latencies in this random process. Our result offers a simple connection between the scheduling distribution and the average performance of concurrent algorithms, which has several applications.

关键词： Shared memory lock-free algorithms scheduling

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Trace-based derivation of a scalable lock-free stack algorithm

引用

FORMAL ASPECTS OF COMPUTING 2009年第1-2期21卷 187-223页

作者： Groves, Lindsay Colvin, Robert Victoria Univ Wellington Sch Math Stat & Comp Sci Wellington New Zealand Univ Queensland ARC Ctr Complex Syst Sch Informat Technol & Elect Engn Brisbane Qld Australia

We show how a sophisticated, lock-free concurrent stack implementation can be derived from an abstract specification in a series of verifiable steps. The algorithm is based on the scalable stack algorithm of Hendler et al. (Proceedings of the sixteenth annual ACM symposium on parallel algorithms, 27-30 June 2004, Barcelona, Spain, pp 206-215), which allows push and pop operations to be paired off and eliminated without affecting the central stack, thus reducing contention on the stack, and allowing multiple pairs of push and pop operations to be performed in parallel. Our algorithm uses a simpler data structure than Hendler, Shavit and Yerushalmi's, and avoids an ABA problem. We first derive a simple lock-free stack algorithm using a linked-list implementation, and discuss issues related to memory management and the ABA problem. We then add an abstract model of the elimination process, from which we derive our elimination algorithm. This allows the basic algorithmic ideas to be separated from implementation details, and provides a basis for explaining and comparing different variants of the algorithm. We show that the elimination stack algorithm is linearisable by showing that any execution of the implementation can be transformed into an equivalent execution of an abstract model of a linearisable stack. Each step in the derivation is either a data refinement which preserves the level of atomicity, an operational refinement which may alter the level of atomicity, or a refactoring step which alters the structure of the system resulting from the preceding derivation. We verify our refinements using an extension of Lipton's reduction method, allowing concurrent and non-concurrent aspects to be considered separately.

关键词： Refinement Derivation lock-free algorithms Concurrency Stack Elimination Reduction, Linearisability Atomicity

来源：评论

学校读者我要写书评

暂无评论

lock-free GARBAGE COLLECTION FOR MULTIPROCESSORS

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1992年第3期3卷 304-311页

作者： HERLIHY, MP MOSS, JEB UNIV MASSACHUSETTS DEPT COMP SCIAMHERSTMA 01003

Garbage collection algorithms for shared-memory multiprocessors typically rely on some form of global synchronization to preserve consistency. Such global synchronization may lead to problems on asynchronous architectures: if one process is halted or delayed, other, nonfaulty processes will be unable to progress. By contrast, a storage management algorithm is lock-free if (in the absence of resource exhaustion) a process that is allocating or collecting memory can be delayed at any point without forcing other processes to block. This paper presents the first algorithm for lock-free garbage collection in a realistic model. The algorithm assumes that processes synchronize by applying read, write, and compare&swap operations to shared memory. This algorithm uses no locks, busy-waiting, or barrier synchronization, it does not assume that processes can observe or modify one another's local variables or registers, and it does not use inter-process interrupts.

关键词： GARBAGE COLLECTION lock-free algorithms MEMORY MANAGEMENT MULTIPROCESSORS SHARED MEMORY WAIT-free algorithms

来源：评论

学校读者我要写书评

暂无评论

Adaptive lock-free Data Structures in Haskell: A General Method for Concurrent Implementation Swapping 10

Adaptive Lock-Free Data Structures in Haskell: A General Met...

引用

10th ACM SIGPLAN Symposium on Haskell (Haskell) co-located with ICFP Conference

作者： Chen, Chao-Hong Choudhury, Vikraman Newton, Ryan R. Indiana Univ Bloomington IN 47405 USA

ISBN: (纸本)9781450351829

A key part of implementing high-level languages is providing built-in and default data structures. Yet selecting good defaults is hard. A mutable data structure's workload is not known in advance, and it may shift over its lifetime-e.g., between read-heavy and write-heavy, or from heavy contention by multiple threads to single-threaded or low-frequency use. One idea is to switch implementations adaptively, but it is nontrivial to switch the implementation of a concurrent data structure at runtime. Performing the transition requires a concurrent snapshot of data structure contents, which normally demands special engineering in the data structure's design. However, in this paper we identify and formalize an relevant property of lock-free algorithms. Namely, lock-freedom is sufficient to guarantee that freezing memory locations in an arbitrary order will result in a valid snapshot. Several functional languages have data structures that freeze and thaw, transitioning between mutable and immutable, such as Haskell vectors and Clojure transients, but these enable only single-threaded writers. We generalize this approach to augment an arbitrary lock-free data structure with the ability to gradually freeze and optionally transition to a new representation. This augmentation doesn't require changing the algorithm or code for the data structure, only replacing its datatype for mutable references with a freezable variant. In this paper, we present an algorithm for lifting plain to adaptive data and prove that the resulting hybrid data structure is itself lock-free, linearizable, and simulates the original. We also perform an empirical case study in the context of heating up and cooling down concurrent maps.

关键词： lock-free algorithms concurrent data structures concurrency parallelism

来源：评论

学校读者我要写书评

暂无评论

lock-free Vertex Clustering for Multicore Mesh Reduction 23

Lock-free Vertex Clustering for Multicore Mesh Reduction

引用

SIGGRAPH Asia Conference on Technical Communications (SA Technical Communications)

作者： Fathollahi, Nima Chester, Sean Univ Victoria Victoria BC Canada

ISBN: (纸本)9798400703157

Modern data collection methods can capture representations of 3D objects at resolutions much greater than they can be discretely rendered as an image. To improve the efficiency of storage, transmission, rendering, and editing of 3D models constructed from such data, it is beneficial to first employ a mesh reduction technique to reduce the size of a mesh. Vertex clustering, a technique that merges close vertices together, has particularly wide applicability, because it operates only on vertices and their spatial proximity. However, it is also very difficult to accelerate with parallelisation in a deterministic manner because it contains extensive algorithmic dependencies. Prior work treats the non-trivial clustering step of this process serially to preserve vertex priorities, which fundamentally limits to mid-single digits the acceleration rates that are possible for the process overall. This paper introduces a novel lock-free parallel algorithm, P-Weld, that exposes parallelism with a graph-theoretic lens that iteratively peels away layers of a mesh that have no remaining dependencies. Concurrent updates to shared data are managed with a linearisable sequence of atomic instructions that exactly reproduces the serial clustering. The resulting parallelism and improved spatial locality yield a 3.86x speedup on a standard 14-million vertex mesh and a 2.93x speedup on a 400-million vertex LiDaR point cloud covering the city of Vancouver, Canada, relative to a popular open source library.

关键词： lock-free algorithms mesh simplification spatial clustering multi-core parallelism

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Adaptive lock-free Maps: Purely-Functional to Scalable 2015

Adaptive Lock-Free Maps: Purely-Functional to Scalable

引用

20th ACM SIGPLAN International Conference on Functional Programming (ICFP)

作者： Newton, Ryan R. Fogg, Peter P. Varamesh, Ali Indiana Univ Bloomington IN 47405 USA

ISBN: (纸本)9781450336697

Purely functional data structures stored inside a mutable variable provide an excellent concurrent data structure-obviously correct, cheap to create, and supporting snapshots. They are not, however, scalable. We provide a way to retain the benefits of these pure-in-a-box data structures while dynamically converting to a more scalable lock-free data structure under contention. Our solution scales to any pair of pure and lock-free container types with key/value set semantics, while retaining lock-freedom. We demonstrate the principle in action on two very different platforms: first in the Glasgow Haskell Compiler and second in Java. To this end we extend GHC to support lock-free data structures and introduce a new approach for safe CAS in a lazy language.

关键词： Languages Performance lock-free algorithms Concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：