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

20th International SPIN Symposium on Model Checking of Software

作者： Adhikari, Kiran Street, James Wang, Chao Liu, Yang Zhang, Shaojie Virginia Tech Blacksburg VA 24061 USA Nanyang Technol Univ Singapore Singapore Singapore Univ Technol & Design Singapore Singapore

ISBN: (纸本)9783642391750

The recent years have seen increasingly widespread use of highly concurrent data structures in both multi-core and distributed computing environments, thereby escalating the priority for verifying their correctness. Quasi linearizability is a quantitative variation of the standard linearizability correctness condition to allow more implementation freedom for performance optimization. However, ensuring that the implementation satisfies the quantitative aspect of this new correctness condition is often an arduous task. In this paper, we propose the first automated method for formally verifying quasi linearizability of the implementation model of a concurrent data structure with respect to its sequential specification. The method is based on checking a relaxed version of the refinement relation between the implementation model and the specification model through explicit state model checking. Our method can directly handle concurrent systems where each thread or process makes infinitely many method calls. Furthermore, unlike many existing verification methods, it does not require the user to supply annotations of the linearization points. We have implemented the new method in the PAT verification framework. Our experimental evaluation shows that the method is effective in verifying the new quasi linearizability requirement and detecting violations.

关键词： Linearizability Model checking concurrent data structure Refinement Quantitative relaxation

来源：评论

学校读者我要写书评

暂无评论

An Efficient Lock-free Logarithmic Search data structure Based on Multi-dimensional List 36

An Efficient Lock-free Logarithmic Search Data Structure Bas...

引用

36th IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Zhang, Deli Dechev, Damian Univ Cent Florida Dept Comp Sci Orlando FL 32817 USA

ISBN: (纸本)9781509014828

Logarithmic search data structures, such as search trees and skiplists, are fundamental building blocks of many applications. Although the self-balancing binary search trees are among the most ubiquitous sequential search data structures, designing non-blocking rebalancing algorithms is challenging due to the required structural alternation, which may stall other concurrent operations. Skiplists, which probabilistically create multiple levels of shortcuts in an ordered list, provide practical alternatives to balanced search trees. The use of skiplists eliminates the need of rebalancing and ensures amortized logarithmic sequential search time, but concurrency is limited under write-dominated workload because the linkage between multiple distant nodes must be updated. In this paper, we present a linearizable lock-free dictionary design based on a multi-dimensional list (MDList). A node in an MDList arranges its child nodes by their dimensionality and order them by coordinate prefixes. The search operation works by first generating a one-to-one mapping from the scalar keys to a high-dimensional vectors space, then uniquely locating the target position by using the vector as coordinates. Our algorithm guarantees worst-case search time of O(logN) where N is the size of key space. Moreover, the ordering property of the data structure is readily maintained during mutations without rebalancing nor randomization. In our experimental evaluation using a micro-benchmark, our dictionary outperforms the state of the art approaches by as much as 100% when the key universe is large and an average of 30% across all scenarios.

关键词： concurrent data structure Dictionary Lock-free Multi-dimensional List Search Tree Skiplist

来源：评论

学校读者我要写书评

暂无评论

Improving Efficacy of Internal Binary Search Trees using Local Recovery 16

Improving Efficacy of Internal Binary Search Trees using Loc...

引用

21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Ramachandran, Arunmoezhi Mittal, Neeraj Univ Texas Dallas Dept Comp Sci Richardson TX 75083 USA

ISBN: (纸本)9781450340922

Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms-blocking as well as non-blocking-have been proposed for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations based on both external and internal representations of a search tree. An important step in executing an operation on a tree is to traverse the tree from top-to-down in order to locate the operation's window. A process may need to perform this traversal several times to handle any failures occurring due to other processes performing conflicting actions on the tree. Most concurrent algorithms that have proposed so far use a naive approach and simply restart the traversal from the root of the tree. In this work, we present a new approach to recover from such failures more efficiently in a concurrent binary search tree based on internal representation using local recovery by restarting the traversal from the "middle" of the tree in order to locate an operation's window. Our approach is sufficiently general in the sense that it can be applied to a variety of concurrent binary search trees based on both blocking and non-blocking approaches. Using experimental evaluation, we demonstrate that our local recovery approach can yield significant speed-ups of up to 69% for many concurrent algorithms.

关键词： concurrent data structure Binary Search Tree Internal Representation Local Recovery

来源：评论

学校读者我要写书评

暂无评论

A Fast Lock-Free Internal Binary Search Tree 15

A Fast Lock-Free Internal Binary Search Tree

引用

16th International Conference on Distributed Computing and Networking

作者： Ramachandran, Arunmoezhi Mittal, Neeraj Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

ISBN: (纸本)9781450329286

We present a new lock-free algorithm for concurrent manipulation of a binary search tree in an asynchronous shared memory system that supports search, insert and delete operations. It combines ideas from two recently proposed lock free algorithms: one of them provides good performance for a read-dominated workload and the other one for a write dominated workload. Specifically, it uses internal representation of a search tree (as in the first one) and is based on marking edges instead of nodes (as in the second one). Our experiments indicate that our new lock-free algorithm outperforms other lock-free algorithms in most cases providing up to 35% improvement in some cases over the next best algorithm.

关键词： concurrent data structure Lock-Free Algorithm Binary Search Tree

来源：评论

学校读者我要写书评

暂无评论

MultiQueues: Simple Relaxed concurrent Priority Queues 15

MultiQueues: Simple Relaxed Concurrent Priority Queues

引用

27th ACM symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Rihani, Hamza Sanders, Peter Dementiev, Roman Univ Grenoble Alpes Grenoble France Karlsruhe Inst Technol Karlsruhe Germany Intel GmbH Munich Germany

ISBN: (纸本)9781450335881

We present a simple, concurrent data structure that approximates the behavior of a priority queue and that gives very good performance guarantees. We also discuss models for the semantics of relaxed priority queues and introduce a technique for "waitfree locking" that allows to convert sequential data structures to relaxed concurrent data structures.

关键词： priority queues concurrent data structure

来源：评论

学校读者我要写书评

暂无评论

Compiler Aided Manual Speculation for High Performance concurrent data structures 13

Compiler Aided Manual Speculation for High Performance Concu...

引用

18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Xiang, Lingxiang Scott, Michael L. Univ Rochester Dept Comp Sci Rochester NY 14627 USA

ISBN: (纸本)9781450319225

Speculation is a well-known means of increasing parallelism among concurrent methods that are usually but not always independent. Traditional nonblocking data structures employ a particularly restrictive form of speculation. Software transactional memory (STM) systems employ a much more general-though typically blocking-form, and there is a wealth of options in between. Using several different concurrent data structures as examples, we show that manual addition of speculation to traditional lock-based code can lead to significant performance improvements. Successful speculation requires careful consideration of profitability, and of how and when to validate consistency. Unfortunately, it also requires substantial modifications to code structure and a deep understanding of the memory model. These latter requirements make it difficult to use in its purely manual form, even for expert programmers. To simplify the process, we present a compiler tool, CSpec, that automatically generates speculative code from baseline lock-based code with user annotations. Compiler-aided manual speculation keeps the original code structure for better readability and maintenance, while providing the flexibility to chose speculation and validation strategies. Experiments on UltraSPARC and x86 platforms demonstrate that with a small number annotations added to lock-based code, CSpec can generate speculative code that matches the performance of best-effort hand-written versions.

关键词： Manual Speculation Design Pattern concurrent data structure Compiler Assistance

来源：评论

学校读者我要写书评

暂无评论

A concurrent red-black tree

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2013年第4期73卷 434-449页

作者： Besa, Juan Eterovic, Yadran Pontificia Univ Catolica Chile Dept Comp Sci Santiago Chile

With the proliferation of multiprocessor computers, data structures capable of supporting several processes are a growing need. concurrent data structures seek to provide similar performance to sequential data structures while being accessible concurrently by several processes and providing synchronization mechanisms transparently to those processes. Red-black trees are an important data structure used in many systems. Unfortunately, it is difficult to implement an efficient concurrent red-black tree for shared memory processes;so most research efforts have been directed towards other dictionary data structures, mainly skip-lists and AVL trees. In this paper we present a new type of concurrent red-black tree that uses optimistic concurrency techniques and new balancing operations to scale well and support contention. Our tree performs favorably compared to other similar dictionaries;in particular, in high contention scenarios it performs up to 14% better than the best-known concurrent dictionary solutions. (C) 2013 Elsevier Inc. All rights reserved.

关键词： concurrent data structure Red-black tree Algorithm design

来源：评论

学校读者我要写书评

暂无评论

Non-blocking Patricia Tries with Replace Operations

Non-blocking Patricia Tries with Replace Operations

引用

33rd IEEE International Conference on Distributed Computing Systems (ICDCS)

作者： Shafiei, Niloufar York Univ Dept Comp Sci & Engn Toronto ON M3J 2R7 Canada

ISBN: (纸本)9780769550008

This paper presents a non-blocking Patricia trie implementation for an asynchronous shared-memory system using Compare&Swap. The trie implements a linearizable set and supports three update operations: insert adds an element, delete removes an element and replace replaces one element by another. The replace operation is interesting because it changes two different locations of trie atomically. If all update operations modify different parts of the trie, they run completely concurrently. The implementation also supports a wait-free find operation, which only reads shared memory and never changes the data structure. Empirically, we compare our algorithms to some existing set implementations.

关键词： Patricia trie non-blocking shared memory lock-free concurrent data structure dictionary set

来源：评论

学校读者我要写书评

暂无评论

concurrent Tries with Efficient Non-Blocking Snapshots 12

Concurrent Tries with Efficient Non-Blocking Snapshots

引用

17th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Prokopec, Aleksandar Bronson, Nathan G. Bagwell, Phil Odersky, Martin Ecole Polytech Fed Lausanne Lausanne Switzerland

ISBN: (纸本)9781450311601

We describe a non-blocking concurrent hash trie based on shared-memory single-word compare-and-swap instructions. The hash trie supports standard mutable lock-free operations such as insertion, removal, lookup and their conditional variants. To ensure space-efficiency, removal operations compress the trie when necessary. We show how to implement an efficient lock-free snapshot operation for concurrent hash tries. The snapshot operation uses a single-word compare-and-swap and avoids copying the data structure eagerly. Snapshots are used to implement consistent iterators and a linearizable size retrieval. We compare concurrent hash trie performance with other concurrent data structures and evaluate the performance of the snapshot operation.

关键词： Algorithms hash trie concurrent data structure snapshot non-blocking

来源：评论

学校读者我要写书评

暂无评论

Priority queues and sorting methods for parallel simulation

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 2000年第5期26卷 401-422页

作者： Grammatikakis, MD Liesche, S INTRACOM Dev Programmes GR-19002 Peania Greece IBM Deutschland Entwickling GMBH D-71023 Boblingen Germany

We examine the design, implementation, and experimental analysis of parallel priority queues for device and network simulation. We consider: 1) distributed splay trees using MPI, 2) concurrent heaps using shared memory atomic locks, and 3) a new, more general concurrent data structure based on distributed sorted lists, which is designed to provide dynamically balanced work allocation (with automatic or manual control) and efficient use of shared memory resources. We evaluate performance for all three data structures on a Cray-T3E900 system at KFA-Julich. Our comparisons are based on simulations of single buffers and a 64 x 64 packet switch which supports multicasting. In all implementations, PEs monitor traffic at their preassigned input/output ports, while priority queue elements are distributed across the Cray-T3E virtual shared memory. Our experiments with up to 60,000 packets and two to 64 PEs indicate that concurrent priority queues perform much better than distributed ones. Both concurrent implementations have comparable performance, while our new data structure uses less memory and has been further optimized. We also consider parallel simulation for symmetric networks by sorting integer conflict functions and implementing an interesting packet indexing scheme. The optimized message passing network simulator can process similar to 500K packet moves in one second, with an efficiency that exceeds similar to 50 percent for a few thousands packets on the Cray-TBE with 32 PEs. All developed data structures now form a parallel library. Although our concurrent implementations use the Cray-T3E ShMem library, portability can be derived from Open-MP or MPI-2 standard libraries, which will provide support for one-way communication and shared memory lock mechanisms.

关键词： concurrent data structure Cray-TBE data race distributed data structure memory lock priority queue parallel simulation virtual shared memory

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：