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

20th International Conference on Distributed Computing and Networking (ICDCN)

作者： Chatterjee, Bapi Peri, Sathya Sa, Muktikanta Singhal, Nandini Inst Sci & Technol Vienna Austria Indian Inst Technol Hyderabad Dept Comp Sci & Engn Hyderabad Telangana India Microsoft R&D Pvt Ltd Bangalore Karnataka India

ISBN: (纸本)9781450360944

Graph algorithms applied in many applications, including social networks, communication networks, VLSI design, graphics, and several others, require dynamic modifications - addition and removal of vertices and/or edges - in the graph. This paper presents a novel concurrent non-blocking algorithm to implement a dynamic unbounded directed graph in a shared-memory machine. The addition and removal operations of vertices and edges are lock-free. For a finite sized graph, the lookup operations are wait-free. Most significant component of the presented algorithm is the reachability query in a concurrent graph. The reachability queries in our algorithm are obstruction-free and thus impose minimal additional synchronization cost over other operations. We prove that each of the data structure operations are linearizable. We extensively evaluate a sample C/C++ implementation of the algorithm through a number of micro-benchmarks. The experimental results show that the proposed algorithm scales well with the number of threads and on an average provides 5 to 7x performance improvement over a concurrent graph implementation using coarse-grained locking.

关键词： concurrent data structure linearizability linearization points lock-free wait-free directed graph reachable path

来源：评论

学校读者我要写书评

暂无评论

Improving Efficacy of concurrent Internal Binary Search Trees using Local Recovery 19

Improving Efficacy of Concurrent Internal Binary Search Tree...

引用

20th International Conference on Distributed Computing and Networking (ICDCN)

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

ISBN: (纸本)9781450360944

Binary Search Tree (BST) is an important data structure for managing ordered data. Many algorithms 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 failures occurring due to other processes performing concurrent updates on the tree. Most concurrent algorithms that have been 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 for certain types of concurrent binary search tree algorithms using local recovery by restarting the traversal from the "middle" of the tree in order to locate an operation's window (tree section of interest). Our approach is sufficiently general in the sense that it can be applied to most of the existing concurrent binary search trees using internal representation based on both blocking as well as non-blocking approaches. Using experimental evaluation, we demonstrate that our local recovery approach can significantly improve the performance of a concurrent internal BST by up to 124.7% when the contention is high.

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

来源：评论

学校读者我要写书评

暂无评论

A Pragmatic Non-blocking concurrent Directed Acyclic Graph 7th

A Pragmatic Non-blocking Concurrent Directed Acyclic Graph

引用

7th International Conference on Networked Systems (NETYS)

作者： Peri, Sathya Sa, Muktikanta Singhal, Nandini Indian Inst Technol Hyderabad Dept Comp Sci & Engn Sangareddy India Microsoft R&D Pvt Ltd Bangalore India

ISBN: (纸本)9783030312770;9783030312763

In this paper, we have developed two non-blocking algorithms for maintaining acyclicity in a concurrent directed graph. The first algorithm is based on a wait-free reachability query and the second one on partial snapshot-based obstruction-free reachability query. Interestingly, we are able to achieve the acyclic property in a dynamic setting without (1) making use of helping descriptors by other threads, or (2) clean double collect mechanism. We present a proof to show that the graph remains acyclic at all times in the concurrent setting. We also prove that the acyclic graph data-structure operations are linearizable. We implement both the algorithms in C++ and test through several micro-benchmarks. Our experimental results illustrate an average of 7x improvement over the sequential and global-lock implementation.

关键词： Acyclic graph concurrent data structure Linearizability Lock-freedom

来源：评论

学校读者我要写书评

暂无评论

Help-optimal and Language-portable Lock-free concurrent data structures 45

Help-optimal and Language-portable Lock-free Concurrent Data...

引用

45th International Conference on Parallel Processing (ICPP)

作者： Chatterjee, Bapi Walulya, Ivan Tsigas, Philippas Chalmers Univ Technol Gothenburg Sweden

ISBN: (纸本)9781509028238

Helping is a widely used technique to guarantee lock-freedom in many concurrent data structures. An optimized helping strategy improves the overall performance of a lock-free algorithm. In this paper, we propose help-optimality, which essentially implies that no operation step is accounted for exclusive helping in the lock-free synchronization of concurrent operations. To describe the concept, we revisit the designs of a lock-free linked-list and a lock-free binary search tree and present improved algorithms. Our algorithms employ atomic single-word compare-and-swap (CAS) primitives and are linearizable. We design the algorithms without using any language/platform specific mechanism. Specifically, we use neither bit-stealing from a pointer nor runtime type introspection of objects. Thus, our algorithms are language-portable. Further, to optimize the amortized number of steps per operation, if a CAS execution to modify a shared pointer fails, we obtain a fresh set of thread-local variables without restarting an operation from scratch. We use several micro-benchmarks in both C/C++ and Java to validate the efficiency of our algorithms against existing state-of-the-art. The experiments show that the algorithms are scalable. Our implementations perform on a par with highly optimized ones and in many cases yield 10%-50% higher throughput.

关键词： concurrent data structure linked-list binary search tree lock-free linearizability help language-portable

来源：评论

学校读者我要写书评

暂无评论

concurrent Linearizable Nearest Neighbour Search in LockFree-kD-tree 18

Concurrent Linearizable Nearest Neighbour Search in LockFree...

引用

19th International Conference on Distributed Computing and Networking (ICDCN)

作者： Chatterjee, Bapi Walulya, Ivan Tsigas, Philippas Chalmers Univ Technol Gothenburg Sweden

ISBN: (纸本)9781450363723

The Nearest neighbour search (NNS) is a fundamental problem in many application domains dealing with multidimensional data. In a concurrent setting, where dynamic modifications are allowed, a linearizable implementation of NNS is highly desirable. This paper introduces the LockFree-kD-tree (LFkD-tree): a lock-free concurrent kD-tree, which implements an abstract data type (ADT) that provides the operations ADD, REMOVE, CONTAINS, and NNS. Our implementation is linearizable. The operations in the LFkD-tree use single-word read and compare-and-swap (CAS) atomic primitives, which are readily supported on available multi-core processors. We experimentally evaluate the LFkD-tree using several benchmarks comprising real-world and synthetic datasets. The experiments show that the presented design is scalable and achieves significant speed-up compared to the implementations of an existing sequential kD-tree and a recently proposed multidimensional indexing structure, PH-tree.

关键词： concurrent data structure kD-tree nearest neighbor search similarity search lock-free linearizability data structure

来源：评论

学校读者我要写书评

暂无评论

Branching Bisimulation and concurrent Object Verification 48

Branching Bisimulation and Concurrent Object Verification

引用

48th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN)

作者： Yang, Xiaoxiao Katoen, Joost-Pieter Lin, Huimin Liu, Gaoang Wu, Hao Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Rhein Westfal TH Aachen Software Modeling & Verificat Grp Aachen Germany

ISBN: (纸本)9781538655962

Linearizability and progress properties are key correctness notions for concurrent objects. This paper presents novel verification techniques for both property classes. The key of our techniques is based on the branching bisimulation equivalence. We first show that it suffices to check linearizability on the quotient object program under branching bisimulation. This is appealing, as it does not rely on linearization points. Further, by exploiting divergence-sensitive branching bisimilarity, our approach proves progress properties (e.g., lock-, wait-freedom) by comparing the concurrent to-be-verified object program against an abstract program consisting of atomic blocks. Our work thus enables the usage of well-known proof techniques for branching bisimulation to check the correctness of concurrent objects. The potential of our approach is illustrated by verifying linearizability and lock-freedom of 14 benchmark algorithms from the literature. Our experiments confirm one known bug and reveals one new bug.

关键词： concurrent data structure verification branching bisimulation lock-free linearizability

来源：评论

学校读者我要写书评

暂无评论

Scalable Lock-Free Vector with Combining 31

Scalable Lock-Free Vector with Combining

引用

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

作者： Walulya, Ivan Tsigas, Philippas Chalmers Univ Technol Gothenburg Sweden

ISBN: (纸本)9781538639146

Dynamic vectors are among the most commonly used data structures in programming. They provide constant time random access and resizable data storage. Additionally, they provide constant time insertion (pushback) and deletion (popback) at the end of the sequence. However, in a multithreaded system, concurrent pushback and popback operations attempt to update the same shared object, creating a synchronization bottleneck. In this paper, we present a lock-free vector design that efficiently addresses the synchronization bottlenecks by utilizing a combining technique on pushback operations. Typical combining techniques come with the price of blocking. Our design introduces combining without sacrificing lock-freedom. We evaluate the performance of our design on a dual socket NUMA Intel server. The results show that our design performs comparably at low loads, and out-performs prior concurrent blocking and non-blocking vector implementations at high contention, by as much as 2.7x.

关键词： concurrent data structure dynamic resizable arrays vectors lock free scalability combining backoff

来源：评论

学校读者我要写书评

暂无评论

A HIERARCHICAL SYSTEM VIEW AND ITS USE IN THE data DISTRIBUTION OF COMPOSED CONTAINERS IN STAPL

A HIERARCHICAL SYSTEM VIEW AND ITS USE IN THE DATA DISTRIBUT...

引用

作者： Shen, Junjie Texas A&M University

In parallel programming, a concurrent container usually distributes its elements to all processing units (locations) equally to maximize the processing ability. However, this distribution strategy does not perform well when we apply nested parallel func- tions on a composed concurrent container, such as a concurrent vector of vectors or a concurrent map of lists. The distribution of the inner concurrent containers across the system will mess up the locality of the elements in the composed containers, generating a lot of inter-process communication when the nested parallel operations are called to access the container’s elements. As the hierarchy in modern high per- formance computing (HPC) systems become large and complex, a large amount of inter-process communication, especially those between two remote processing units (such as two cores on different nodes), will have dramatic negative impact on the performance of the parallel applications. In this thesis, we introduce a hierarchical system view that represents the topol- ogy of the processing units in a HPC system, and use it to guide the distribution of the composed concurrent containers. It reduces the number of processing elements involved in storing in the inner concurrent containers, which reduces memory usage and improves construction time. It also reduces the amount of inter-process com- munication by improving the locality of the elements when we apply nested parallel functions on a composed concurrent container. To evaluate our approach, we implement two concurrent associative multi-key containers, multimap and multiset, in the Standard Template Adaptive Parallel Li- brary (STAPL), and use the hierarchical system view on the distribution of composed 2D and 3D containers. Finally, we show great improvement on both the construction time and the execution time of the nested parallel functions with various numbers of cores and hierarchies.

关键词： concurrent data structure hierarchical distribution Parallel programming framework Thesis

来源：评论

学校读者我要写书评

暂无评论

A Lock-Free Priority Queue Design Based on Multi-Dimensional Linked Lists

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2016年第3期27卷 613-626页

作者： Zhang, Deli Dechev, Damian Univ Cent Florida Dept Elect Engn & Comp Sci Orlando FL 32826 USA

The throughput of concurrent priority queues is pivotal to multiprocessor applications such as discrete event simulation, best-first search and task scheduling. Existing lock-free priority queues are mostly based on skiplists, which probabilistically create shortcuts in an ordered list for fast insertion of elements. The use of skiplists eliminates the need of global rebalancing in balanced search trees and ensures logarithmic sequential search time on average, but the worst-case performance is linear with respect to the input size. In this paper, we propose a quiescently consistent lock-free priority queue based on a multi-dimensional list that guarantees worst-case search time of O(log N) for key universe of size N. The novel multi-dimensional list (MDList) is composed of nodes that contain multiple links to child nodes arranged by their dimensionality. The insertion operation works by first injectively mapping the scalar key to a high-dimensional vector, then uniquely locating the target position by using the vector as coordinates. Nodes in MDList are ordered by their coordinate prefixes and the ordering property of the data structure is readily maintained during insertion without rebalancing nor randomization. In our experimental evaluation using a micro-benchmark, our priority queue achieves an average of 50 percent speedup over the state of the art approaches under high concurrency.

关键词： concurrent data structure priority queue lock-freedom multi-dimensional List skiplist

来源：评论

学校读者我要写书评

暂无评论

Verifying a quantitative relaxation of linearizability via refinement

引用

INTERNATIONAL JOURNAL ON SOFTWARE TOOLS FOR TECHNOLOGY TRANSFER 2016年第4期18卷 393-407页

作者： 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

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：