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

50th International Conference on Parallel Processing (ICPP)

作者： Yi, Zhengming Yao, Yiping Chen, Kai Natl Univ Def Technol Coll Comp Changsha Peoples R China Natl Univ Def Technol Coll Syst Engn Changsha Peoples R China

ISBN: (纸本)9781450390682

Universal constructions are attractive as they can turn a sequential implementation of any data structure into a concurrent implementation. However, existing universal constructions have limitations, such as imposing high copying overhead, or poor scalability on NUMA systems mainly due to their lack of NUMA-aware design principles. To overcome these limitations, this paper introduces CR, a universal construction that provides highly scalable updates on NUMA systems while offering fast read-side performance. CR achieves NUMA-awareness by utilizing delegation within a NUMA node and a global shared log to maintain the consistency of replicas of data structures across nodes. Using CR does not require expertise in concurrent data structure design. Our evaluation shows that CR has up to 11.2 times better performance compared to a state-ofthe-art universal construction CX on our tested sequential data structures. To demonstrate the effectiveness and applicability of CR, we have applied CR to an in-memory database system. The database shows up to 18.1 times better performance compared to the original version.

关键词： concurrent data structure synchronization universal construction NUMA multicore

来源：评论

学校读者我要写书评

暂无评论

MEMENTO: A Framework for Detectable Recoverability in Persistent Memory

引用

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2023年第PLDI期7卷 292-317页

作者： Cho, Kyeongmin Jeon, Seungmin Raad, Azalea Kang, Jeehoon Korea Adv Inst Sci & Technol Daejeon South Korea Imperial Coll London London England

Persistent memory (PM) is an emerging class of storage technology that combines the performance of DRAM with the durability of SSD, offering the best of both worlds. This had led to a surge of research on persistent objects in PM. Among such persistent objects, concurrent data structures (DSs) are particularly interesting thanks to their performance and scalability. One of the most widely used correctness criteria for persistent concurrent DSs is detectable recoverability, ensuring both thread safety (for correctness in non-crashing concurrent executions) and crash consistency (for correctness in crashing executions). However, the existing approaches to designing detectably recoverable concurrent DSs are either limited to simple algorithms or suffer from high runtime overheads. We present Memento: a general and high-performance programming framework for detectably recoverable concurrent DSs in PM. To ensure general applicability to various DSs, Memento supports primitive operations such as checkpoint and compare-and-swap and their composition with control constructs. To ensure high performance, Memento employs a timestamp-based recovery strategy that requires fewer writes and flushes to PM than the existing approaches. We formally prove that Memento ensures detectable recoverability in the presence of crashes. To showcase Memento, we implement a lock-free stack, list, queue, and hash table, and a combining queue that detectably recovers from random crashes in stress tests and performs comparably to existing hand-tuned persistent DSs with and without detectable recoverability.

关键词： persistent memory detectable recovery concurrent data structure

来源：评论

学校读者我要写书评

暂无评论

concurrent linearizable nearest neighbour search in LockFree-kD-tree

引用

THEORETICAL COMPUTER SCIENCE 2021年 886卷 27-48页

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

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 the 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. (C) 2021 Elsevier B.V. All rights reserved.

关键词： concurrent data structure kD-tree Nearest neighbour search Similarity search Lock-free Linearizability

来源：评论

学校读者我要写书评

暂无评论

Lock-free Contention Adapting Search Trees

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2021年第2期8卷 1–38页

作者： Winblad, Kjell Sagonas, Konstantinos Jonsson, Bengt Ericsson AB Isafjordsgatan 10 S-16440 Kista Sweden Uppsala Univ Dept Informat Technol S-75105 Uppsala Sweden

concurrent key-value stores with range query support are crucial for the scalability and performance ofmany applications. Existing lock-free data structures of this kind use a fixed synchronization granularity. Using a fixed synchronization granularity in a concurrent key-value store with range query support is problematic as the best performing synchronization granularity depends on a number of factors that are difficult to predict, such as the level of contention and the number of items that are accessed by range queries. We present the first linearizable lock-free key-value store with range query support that dynamically adapts its synchronization granularity. This data structure is called the lock-free contention adapting search tree (LFCA tree). An LFCA tree automatically performs local adaptations of its synchronization granularity based on heuristics that take contention and the performance of range queries into account. We show that the operations of LFCA trees are linearizable, that the lookup operation is wait-free, and that the remaining operations (insert, remove and range query) are lock-free. Our experimental evaluation shows that LFCA trees achieve more than twice the throughput of related lock-free data structures in many scenarios. Furthermore, LFCA trees are able to perform substantially better than data structures with a fixed synchronization granularity over a wide range of scenarios due to their ability to adapt to the scenario at hand.

关键词： concurrent data structure range query lock-freedom wait-freedom linearizability adaptivity

来源：评论

学校读者我要写书评

暂无评论

DACHash: A Dynamic, Cache-Aware and concurrent Hash Table on GPUs 33

DACHash: A Dynamic, Cache-Aware and Concurrent Hash Table on...

引用

33rd IEEE International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD)

作者： Zhou, Hao Troendle, David Jang, Byunghyun Univ Mississippi Comp & Informat Sci University MS 38677 USA

ISBN: (纸本)9781665443012

GPU acceleration of hash tables in high-volume transaction applications such as computational geometry and bio-informatics are emerging. Recently, several hash table designs have been proposed on GPUs, but our analysis shows that they still do not adequately factor in several important aspects of a GPU's execution environment, leaving large room for further optimization. To that end, we present a dynamic, cache-aware, concurrent hash table named DACHash. It is specifically designed to improve memory efficiency and reduce thread divergence on GPUs. We propose several novel techniques including a GPU-friendly data structure & sizing, a reorder algorithm, and dynamic thread-data mapping schemes that make the operations of hash table more amendable to GPU architecture. Testing DACHash on an NVIDIA GTX 3090 achieves a peak performance of 8.65 billion queries/second in static searching and 5.54 billion operations/second in concurrent operation execution. It outperforms the state-of-the-art SlabHash by 41.53% and 19.92% respectively. We also verify that our proposed technique improves L2 cache bandwidth and L2 cache hit rate by 9.18x and 2.68x respectively.

关键词： hash table GPGPU concurrent data structure

来源：评论

学校读者我要写书评

暂无评论

Intelligent manufacturing security model based on improved blockchain

引用

MATHEMATICAL BIOSCIENCES AND ENGINEERING 2020年第5期17卷 5633-5650页

作者： Xu, Jiahe Tian, Yuan Ma, Tinghuai Al-Nabhan, Najla Southeast Univ Sch Automat Nanjing 211189 Peoples R China Nanjing Inst Technol Nanjing 211167 Peoples R China Nanjing Univ Informat Sci & Technol Nanjing 210044 Peoples R China King Saud Univ Dept Comp Sci Riyadh Saudi Arabia

The Industrial Internet of Things (IIoT) plays an important role in the development of smart factories. However, the existing IIoT systems are prone to suffering from single points of failure and unable to provide stable service. Meanwhile, with the increase of node scale and network quantity, the maintenance cost presents to be higher. Such a disadvantage can be effectively compensated by the features such as security, privacy, non-tamperability and distributed deployment supported by the blockchain. In this paper, first, an intelligent manufacturing security model based on blockchain was proposed. Due to the high power consumption and low throughput of the traditional blockchain, IoT devices with limited power consumption can not work independently. Therefore, in this paper, a new Merkle Patricia tree (MPT) was adopted to extend the blockchain structure and provide fast query of node status. Second, since the MPT does not support concurrent operation and the data operation performance deteriorates with high data volume, a lock-free concurrent and cache-based Merkle Patricia tree was proposed (CMPT) to support lock-free concurrent data operation, which can improve the data operation efficiency in multi-core system. The experimental results indicate that, compared with the original MPT, the CMPT proposed in this paper effectively reduced the time complexity of data insertion and data query and improved the speed of block construction and data query.

关键词： smart manufacturing Industrial Internet of Things blockchain Merkle Patricia tree concurrent data structure

来源：评论

学校读者我要写书评

暂无评论

FEAST: A Lightweight Lock-free concurrent Binary Search Tree

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2020年第2期7卷 1–64页

作者： Natarajan, Aravind Ramachandran, Arunmoezhi Mittal, Neeraj Qualcomm Res Santa Clara CA 95051 USA Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

We present a lock-free algorithm for concurrent manipulation of a binary search tree (BST) in an asynchronous shared memory system that supports search, insert, and delete operations. In addition to read and write instructions, our algorithm uses (single-word) compare-and-swap (CAS) and bit-test-and-set (BTS) read-modify-write (RMW) instructions, both of which are commonly supported by many modern processors including Intel 64 and AMD64. In contrast to most of the existing concurrent algorithms for a binary search tree, our algorithm is edge-based rather than node-based. When compared to other concurrent algorithms for a binary search tree, modify (insert and delete) operations in our algorithm (a) work on a smaller section of the tree, (b) execute fewer RMW instructions, or (c) use fewer dynamically allocated objects. In our experiments, our lock-free algorithm significantly outperformed all other algorithms for a concurrent binary search tree especially when the contention was high. We also describe modifications to our basic lock-free algorithm so that the amortized complexity of any operation in the modified algorithm can be bounded by the sum of the tree height and the point contention to within a constant factor while preserving the other desirable features of our algorithm.

关键词： Multicore system concurrent data structure lock-free algorithm binary search tree

来源：评论

学校读者我要写书评

暂无评论

Fast Wait-Free Construction for Pool-Like Objects with Weakened Internal Order: Stacks as an Example

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2019年第7期30卷 1596-1612页

作者： Peng, Yaqiong Yun, Xiaochun Hao, Zhiyu Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China

This paper focuses on a large class of concurrent data structures that we call pool-like objects (e.g., stack, double-ended queue, and queue). Performance and progress guarantee are two important characteristics for concurrent data structures. In the aspect of performance, weakening the internal order in a pool-like object is an effective technique to reduce the synchronization cost among threads accessing the object, but no objects with weakened internal order provide a progress guarantee as strong as wait-freedom. Meanwhile, wait-free algorithms tend to be inefficient, which is mainly attributed to the helping mechanisms. Based on the philosophy of existing helping mechanisms, a wait-free pool-like object with weakened internal order would suffer from unnecessary process of getting the latest object state and synchronization. This paper takes a state-of-the-art implementation of stacks with weakened internal order as an example, and transforms it into a highly-efficient wait-free stack named WF-TS-Stack. The transformation method includes a helping mechanism with state reuse and a relaxed removal scheme. In addition, we use a simple and effective scheme to further improve the performance of WF-TS-Stack in Non-Uniform Memory Access (NUMA) architectures. Our evaluation with representative benchmarks shows that WF-TS-Stack outperforms its original building blocks by up to 1.45X at maximum concurrency. We also discuss how to yield an efficient double-ended queue (deque) variant of WF-TS-Stack, because deque is a more generalized pool-like object.

关键词： concurrent data structure stack double-ended queue performance wait-freedom

来源：评论

学校读者我要写书评

暂无评论

Non-blocking Patricia tries with replace operations

引用

DISTRIBUTED COMPUTING 2019年第5期32卷 423-442页

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

This paper presents a non-blocking Patricia trie implementation for an asynchronous shared-memory system using Compare&Swap. The trie is a linearizable implementation of a set and supports three update operations: insert adds an element to the trie, delete removes an element from the trie and replace replaces one element by another. The replace operation is interesting because it changes two different locations of a trie. We design a mechanism that allows the two changes of a replace operation to appear to be executed 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. Our implementation and its correctness proof are modular and can be adapted for other data structures. Empirically, we compare our algorithms to some existing tree-based set implementations and our results show that our trie performs consistently well in different scenarios.

关键词： Patricia trie Non-blocking Shared memory Lock-free concurrent data structure Dictionary Set

来源：评论

学校读者我要写书评

暂无评论

concurrent Unrolled Skiplist 39

Concurrent Unrolled Skiplist

引用

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

作者： Platz, Kenneth Mittal, Neeraj Venkatesan, S. Univ Texas Dallas Dept Comp Sci Richardson TX 75080 USA

ISBN: (纸本)9781728125190

Skiplist is an important data structure used for storing and managing ordered data. It provides logarithmic time complexity (in list size) for lookup, insert and remove operations with high probability without the need for complex balancing actions. Several algorithms have been proposed for concurrent maintenance of a skiplist using both blocking and non-blocking synchronization techniques. In this work, we propose a new algorithm for maintaining a concurrent skiplist that uses two techniques to boost performance. The first technique, referred to as unrolling, involves storing multiple key-value pairs in the same node. The second technique involves using an advanced locking primitive, based on group mutual exclusion, to allow certain operations to work on the same node concurrently. In our experiments, our concurrent skiplist consistently outperformed existing concurrent skiplists by as much as 90% in some cases.

关键词： concurrent data structure skiplist unrolling group mutual exclusion

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：