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

Proceedings of the Programming Models and Languages for Distributed Computing

作者： Deepthi Devaki Akkoorath José Brandão Annette Bieniusa Carlos Baquero Technical University of Kaiserslautern Germany Universidade do Minho Braga Portugal HASLab Universidade do Minho & INESC TEC Braga Portugal

ISBN: (纸本)9781450363563

With the rapid growth of number of cores, together with the heterogeneous access latencies, the cost of synchronization and communication between distant components keeps growing. As more general purpose programs exploit the many-core architectures, the speedup achieved will then be limited by the synchronization needed to access shared objects [2]. When building Internet-scale systems, similar concerns lead to the design of scalable systems that limit global synchronization and operate locally when possible. CRDTs [1] succeed in capturing data types with clear concurrency semantics and are now common components in Internet-scale systems. However, they do not migrate trivially to shared-memory architectures due to high computational costs from merge functions, which becomes apparent once network communication is *** this talk, we discuss multi-view data types for shared-memory architectures, that leverages a global-local view model that distinguishes between a local fast state and a distant shared state. By executing operations on the local state without synchronization, while only synchronizing with the shared state when needed, applications can achieve better scalability at the expense of linearizability - the default correctness criteria for concurrent objects.

关键词： weak consistency concurrent data-structures linearizability

来源：评论

学校读者我要写书评

暂无评论

Efficient Lock-free Binary Search Trees 14

Efficient Lock-free Binary Search Trees

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Chatterjee, Bapi Nguyen, Nhan Tsigas, Philippas Chalmers Univ Technol Gothenburg Sweden

ISBN: (纸本)9781450329446

In this paper we present a novel algorithm for concurrent lock-free internal binary search trees (BST) and implement a Set abstract data type (ADT) based on that. We show that in the presented lock-free BST algorithm the amortized step complexity of each set operation - Add, Remove and Contains - is O(H(n)+c), where H(n) is the height of the BST with n number of nodes and c is the contention during the execution. Our algorithm adapts to contention measures according to read-write load. If the situation is read-heavy, the operations avoid helping the concurrent Remove operations during traversal, and adapt to interval contention. However, for the write-heavy situations we let an operation help a concurrent Remove, even though it is not obstructed. In that case, an operation adapts to point contention. It uses single-word compare-and-swap (CAS) operations. We show that our algorithm has improved disjoint-access-parallelism compared to similar existing algorithms. We prove that the presented algorithm is linearizable. To the best of our knowledge, this is the first algorithm for any concurrent tree datastructure in which the modify operations are performed with an additive term of contention measure.

关键词： concurrent data-structures binary search tree amortized analysis shared memory lock-free CAS

来源：评论

学校读者我要写书评

暂无评论

LCD: Local Combining on Demand 18

LCD: Local Combining on Demand

引用

18th International Conference on Principles of Distributed Systems (OPODIS)

作者： Drachsler-Cohen, Dana Petrank, Erez Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel

ISBN: (纸本)9783319144726;9783319144719

Combining methods are highly effective for implementing concurrent queues and stacks. These data structures induce a heavy competition on one or two contention points. However, it was not known whether combining methods could be made effective for parallel scalable data structures that do not have a small number of contention points. In this paper, we introduce local combining on-demand, a new combining method for highly parallel data structures. The main idea is to apply combining locally for resources on which threads contend. We demonstrate the use of local combining on-demand on the common linked-list data structure. Measurements show that the obtained linked-list induces a low overhead when contention is low and outperforms other known implementations by up to 40% when contention is high.

关键词： concurrent data-structures Multiprocessors Synchronization

来源：评论

学校读者我要写书评

暂无评论

Non-blocking parallel subset construction on shared-memory multicore architectures 13

Non-blocking parallel subset construction on shared-memory m...

引用

Proceedings of the Eleventh Australasian Symposium on Parallel and Distributed Computing - Volume 140

作者： Hyewon Choi Bernd Burgstaller Yonsei University Seoul Korea

ISBN: (纸本)9781921770258

We discuss ways to effectively parallelize the subset construction algorithm, which is used to convert non-deterministic finite automata (NFAs) to deterministic finite automata (DFAs). This conversion is at the heart of string pattern matching based on regular expressions and thus has many applications in text processing, compilers, scripting languages and web browsers, security and more recently also with DNA sequence analysis. We discuss sources of parallelism in the sequential algorithm and their profitability on shared-memory multicore architectures. Our NFA and DFA data-structures are designed to improve scalability and keep communication and synchronization overhead to a minimum. We present three different ways for synchronization; the performance of our non-blocking synchronization based on a compare-and-swap (CAS) primitive compares favorably to a lock-based approach. We consider structural NFA properties and their relationship to scalability on highly-parallel multicore architectures. We demonstrate the efficiency of our parallel subset construction algorithm through several benchmarks run on a 4-CPU (40 cores) node of the Intel Manycore Testing Lab. Achieved speedups are up to a factor of 32x with 40 cores.

关键词： shared-memory multicore architectures subset construction concurrent data-structures non-blocking synchronization

来源：评论

学校读者我要写书评

暂无评论

Interrupting snapshots and the Java™ size method

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2012年第7期72卷 880-888页

作者： Afek, Yehuda Shavit, Nir Tzafrir, Moran Tel Aviv Univ Tel Aviv Israel MIT Dept EECS Cambridge MA 02139 USA

The Java (TM) m developers kit requires a size () operation for all objects, tracking the number of elements in the object. Unfortunately, the best known solution, available in the Java concurrency package, has a blocking concurrent implementation that does not scale. This paper presents a highly scalable wait-free implementation of a concurrent size () operation based on a new lock-free interrupting snapshots algorithm. The key idea behind the new algorithm is to allow snapshot scan methods to interrupt each other until they agree on a shared linearization point with respect to update methods. This contrasts sharply with past approaches to the classical atomic snapshot problem, that have had threads coordinate the collecting of a shared global view. As we show empirically, the new algorithm scales well, significantly outperforming existing implementations. (C) 2012 Elsevier Inc. All rights reserved.

关键词： Multicore algorithms Java concurrency concurrent data-structures Wait-free Lock-free

来源：评论

学校读者我要写书评

暂无评论

Flat Combining and the Synchronization-Parallelism Tradeoff 10

Flat Combining and the Synchronization-Parallelism Tradeoff

引用

22nd ACM Symposium on Parallelism in Algorithms and Architectures

作者： Hendler, Danny Incze, Itai Tzafrir, Moran Shavit, Nir Ben Gurion Univ Negev IL-84105 Beer Sheva Israel

ISBN: (纸本)9781450300797

Traditional data structure designs, whether lock-based or lock-free, provide parallelism via fine grained synchronization among threads. We introduce a new synchronization paradigm based on coarse locking, which we call fiat combining The cost of synchronization in flat combining is so low, that having a single thread holding a lock perform the combined access requests of all others, delivers, up to a certain non-negligible concurrency level, better performance than the most effective parallel finely synchronized implementations We use fiat-combining to devise, among other structures, new linearizable stack, queue, and priority queue algorithms that greatly outperform all prior algorithms

关键词： Multiprocessors concurrent data-structures Synchronization

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：