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

30th Symposium on Principles and Practice of Parallel Programming

作者： Singh, Ajay Brown, Trevor Univ Waterloo Waterloo ON Canada

ISBN: (纸本)9798400714436

Safe memory reclamation techniques that utilize per read reservations, such as hazard pointers and hazard eras, often cause significant overhead in traversals of linked concurrent data structures. This is primarily due to the need to announce a reservation, and fence to make it globally visible (and enforce appropriate ordering), before each read. In real world read-intensive workloads, this overhead is amplified because, even if relatively little memory reclamation actually occurs, the full overhead of reserving records before use is still incurred while traversing data structures. In this paper, we propose a novel memory reclamation technique by combining POSIX signals and delayed reclamation, introducing a publish-on-ping approach. This method eliminates the need to make reservations globally visible before use. Instead, threads privately track which records they are accessing, and share this information on demand with threads that intend to reclaim memory. The approach can serve as a drop-in replacement for hazard pointers and hazard eras. Furthermore, the capability to retain reservations during traversals in data structure operations and publish them on demand facilitates the construction of a variant of hazard pointers (EpochPOP). This variant uses epochs to approach the performance of epoch-based reclamation in the common case where threads are not frequently delayed (while retaining the robustness of hazard pointers). Our publish-on-ping implementations based on hazard pointers and hazard eras, when applied to various data structures, exhibit significant performance improvements. The improvements across various workloads and data structures range from 1.2X to 4X over the original HP, up to 20% compared to a heavily optimized HP implementation similar to the one in the Folly open-source library, and up to 3X faster than hazard eras. EpochPOP delivers performance similar to epoch-based reclamation while providing stronger guarantees.

关键词： safe memory reclamation concurrent data structures memory management Fast Hazard Pointers

来源：评论

学校读者我要写书评

暂无评论

How to Relax Instantly: Elastic Relaxation of concurrent data structures 30th

How to Relax Instantly: Elastic Relaxation of Concurrent Dat...

引用

30th European Conference on Parallel and Distributed Processing (Euro-Par)

作者： von Geijer, Kare Tsigas, Philippas Chalmers Univ Technol Gothenburg Sweden

ISBN: (纸本)9783031695827;9783031695834

The sequential semantics of many concurrent data structures, such as stacks and queues, inevitably lead to memory contention in parallel environments, thus limiting scalability. Semantic relaxation has the potential to address this issue, increasing the parallelism at the expense of weakened semantics. Although prior research has shown that improved performance can be attained by relaxing concurrent data structure semantics, there is no one-size-fits-all relaxation that adequately addresses the varying needs of dynamic executions. In this paper, we first introduce the concept of elastic relaxation and consequently present the Lateral structure, which is an algorithmic component capable of supporting the design of elastically relaxed concurrent data structures. Using the Lateral, we design novel elastically relaxed, lock-free queues and stacks capable of reconfiguring relaxation during run-time. We establish linearizability and define upper bounds for relaxation errors in our designs. Experimental evaluations show that our elastic designs hold up against state-of-the-art statically relaxed designs, while also swiftly managing trade-offs between relaxation and operational latency. We also outline how to use the Lateral to design elastically relaxed lock-free counters and deques.

关键词： concurrent data structures lock-free relaxed semantics

来源：评论

学校读者我要写书评

暂无评论

Opportunities and Limitations of Hardware Timestamps in concurrent data structures 37

Opportunities and Limitations of Hardware Timestamps in Conc...

引用

37th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Grimes, Olivia Nelson-Slivon, Jacob Hassan, Ahmed Palmieri, Roberto Lehigh Univ Bethlehem PA 18015 USA

ISBN: (纸本)9798350337662

Designing high-performance, highly-concurrent linearizable data structures is complex, especially when bulk operations (e.g., range queries) are included. Relying on a single source of synchronization, such as a logical global timestamp, unequivocally eases the design of the synchronization schemes. However, such a design creates a single point of contention, and thus carries performance downsides. As a result, designers often face the dilemma between a simple design and a performance bottleneck. Recently, modern commodity architectures have enabled low-level mechanisms that guarantee that the timestamp registers of all CPUs are synchronized, thus enabling the use of hardware timestamps in data structure designs. Although recent work already exploits this, this work aims at understanding the opportunities and limitations of using hardware timestamps in existing data structure designs. We address this challenge by applying hardware timestamping to three recent state-of-the-art algorithms that use logical timestamps to support range queries in concurrent data structures. Our evaluation shows that the use of hardware timestamps does indeed improve performance compared to the original designs, achieving up to 5.5x improvement. More importantly, by removing the bottleneck of using global logical timestamps in these algorithms, we highlight the design choices that most significantly impact the use of hardware timestamps. Specifically, we show that the mechanism of labeling objects with timestamps plays an important role in maximizing the benefits of leveraging hardware timestamps.

关键词： concurrent data structures Linearizability Range Query

来源：评论

学校读者我要写书评

暂无评论

HybriDS: Cache-Conscious concurrent data structures for Near-Memory Processing Architectures 22

HybriDS: Cache-Conscious Concurrent Data Structures for Near...

引用

34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Choe, Jiwon Crotty, Andrew Moreshet, Tali Herlihy, Maurice Bahar, R. Iris Brown Univ Providence RI 02912 USA Northwestern Univ Evanston IL USA

ISBN: (纸本)9781450391467

In recent years, the ever-increasing impact of memory access bottlenecks has brought forth a renewed interest in near-memory processing (NMP) architectures. In this work, we propose and empirically evaluate hybrid data structures, which are concurrent data structures custom-designed for these new NMP architectures. We focus on cache-optimized data structures, such as skiplists and B+ trees, that are often used as index structures in online transaction processing (OLTP) systems to enable fast key-based lookups. These data structures are hierarchical, where lookups begin at a small number of top-level nodes and diverge to many different node paths as they move down the hierarchy, such that nodes in higher levels benefit more from caching. Our proposed hybrid data structures split traditional hierarchical data structures into a host-managed portion consisting of higher-level nodes and an NMP-managed portion consisting of the remaining lower-level nodes, thus retaining and further enhancing the cache-conscious optimizations of their conventional implementations. Although the idea might seem relatively simple, the splitting of the data structure prompts new synchronization problems, and careful implementation is required to ensure high concurrency and correctness. We provide implementations of a hybrid skiplist and a hybrid B+ tree, and we empirically evaluate them on a cycle-accurate full-system architecture simulator. Our results show that the hybrid data structures have the potential to improve performance by more than 2x compared to state-of-the-art concurrent data structures.

关键词： near-memory processing concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

Verifying correctness of persistent concurrent data structures: a sound and complete method

引用

FORMAL ASPECTS OF COMPUTING 2021年第4-5期33卷 547-573页

作者： Derrick, John Doherty, Simon Dongol, Brijesh Schellhorn, Gerhard Wehrheim, Heike Univ Sheffield Dept Comp Sheffield S Yorkshire England Univ Surrey Dept Comp Sci London England Univ Augsburg Inst Informat D-86135 Augsburg Germany Univ Paderborn Inst Informat D-33098 Paderborn Germany

Non-volatile memory (NVM), aka persistent memory, is a new memory paradigm that preserves its contents even after power loss. The expected ubiquity of NVM has stimulated interest in the design of persistent concurrent data structures, together with associated notions of correctness. In this paper, we present a formal proof technique for durable linearizability, which is a correctness criterion that extends linearizability to handle crashes and recovery in the context *** proofs are based on refinement of Input/Output automata (IOA) representations of concurrent data structures. To this end, we develop a generic procedure for transforming any standard sequential data structure into a durable specification and prove that this transformation is both sound and complete. Since the durable specification only exhibits durably linearizable behaviours, it serves as the abstract specification in our refinement proof. We exemplify our technique on a recently proposed persistentmemory queue that builds on Michael and Scott's lock-free queue. To support the proofs, we describe an automated translation procedure from code to IOA and a thread-local proof technique for verifying correctness of invariants.

关键词： Non-volatile memory concurrent data structures Refinement Linearizability

来源：评论

学校读者我要写书评

暂无评论

Memory Tagging: Minimalist Synchronization for Scalable concurrent data structures 20

Memory Tagging: Minimalist Synchronization for Scalable Conc...

引用

32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)

作者： Alistarh, Dan Brown, Trevor Singhal, Nandini IST Austria Klosterneuburg Austria Univ Waterloo Waterloo ON Canada Microsoft R&D India New Delhi India

ISBN: (纸本)9781450369350

There has been a significant amount of research on hardware and software support for efficient concurrent data structures;yet, the question of how to build correct, simple, and scalable data structures has not yet been definitively settled. In this paper, we revisit this question from a minimalist perspective, and ask: what is the smallest amount of synchronization required for correct and efficient concurrent search data structures, and how could this minimal synchronization support be provided in hardware? To address these questions, we introduce memory tagging, a simple hardware mechanism which enables the programmer to "tag" a dynamic set of memory locations, at cache-line granularity, and later validate whether the memory has been concurrently modified, with the possibility of updating one of the underlying locations atomically if validation succeeds. We provide several examples showing that this mechanism can enable fast and arguably simple concurrent data structure designs, such as lists, binary search trees, balanced search trees, range queries, and Software Transactional Memory (STM) implementations. We provide an implementation of memory tags in the Graphite multi-core simulator, showing that the mechanism can be implemented entirely at the level of L1 cache, and that it can enable non-trivial speedups versus existing implementations of the above data structures.

关键词： concurrent data structures synchronization techniques transactional memory search data structures hardware mechanisms

来源：评论

学校读者我要写书评

暂无评论

concurrent data structures with Near-data-Processing: an Architecture-Aware Implementation 19

Concurrent Data Structures with Near-Data-Processing: an Arc...

引用

31st ACM Symposium on Parallelism in Algorithms and Architecturess (SPAA)

作者： Choe, Jiwon Huang, Amy Moreshet, Tali Herlihy, Maurice Bahar, R. Iris Brown Univ Providence RI 02912 USA Boston Univ Boston MA 02215 USA

ISBN: (纸本)9781450361842

Recent advances in memory architectures have provoked renewed interest in near-data-processing (NDP) as way to alleviate the "memory wall" problem. An NDP architecture places logic circuits, such as simple processors, in close proximity to memory. Effective use of NDP architectures requires rethinking data structures and their algorithms. Here, we provide an empirical evaluation of several NDP-aware algorithms for general-purpose concurrent data structures such as linked-lists, skiplists, and FIFO queues. The empirical analysis reveals that the potential benefits of NDP-based concurrent data structures are less than what had been expected in earlier studies. In turn, we introduce lightweight NDP hardware modifications, inspired by initial observations on data access patterns and underlying DRAM activity. Even the minimal changes to hardware significantly improve the performance and energy consumption of NDP-based concurrent data structures, and in many cases, the resulting data structures outperform state-of-the-art concurrent data structures.

关键词： near-data-processing hardware-software co-design concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

PathCAS: An Efficient Middle Ground for concurrent Search data structures 22

PathCAS: An Efficient Middle Ground for Concurrent Search Da...

引用

27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP)

作者： Brown, Trevor Sigouin, William Alistarh, Dan Univ Waterloo Canada Waterloo ON Canada

ISBN: (纸本)9781450392044

To maximize the performance of concurrent data structures, researchers have often turned to highly complex fine-grained techniques, resulting in efficient an d elegant algorithms, which can however be often difficult to understand and prove correct. While simpler techniques exist, such as transactional memory, they can have limited performance or portability relative to their fine-grained counterparts. Approaches at both ends of this complexity-performance spectrum have been extensively explored, but relatively less is known about the middle ground: approaches that are willing to sacrifice some performance for simplicity, while remaining competitive with state-of-the-art handcrafted designs. In this paper, we explore this middle ground, and present PathCAS, a primitive that combines ideas from multi-word CAS (KCAS) and transactional memory approaches, while carefully avoiding overhead. We show how PathCAS can be used to implement efficient search data structures relatively simply, using an internal binary search tree as an example, then extending this to an AVL tree. Our best implementations outperform many handcrafted search trees: in search-heavy workloads, it rivals the BCCO tree [5], the fastest known concurrent binary tree in terms of search performance [3]. Our results suggest that PathCAS can yield concurrent data structures that are relatively easy to build and prove correct, while offering surprisingly high performance.

关键词： concurrent data structures search trees non-blocking algorithms lock-free synchronization primitives

来源：评论

学校读者我要写书评

暂无评论

concurrent data structures 16

Concurrent Data Structures

引用

35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Ellen, Faith Brown, Trevor Univ Toronto Dept Comp Sci Toronto ON M5S 1A1 Canada

ISBN: (纸本)9781450339643

data structures are an important component of efficient and well-structured programs. In shared memory distributed computing, correct data structures are difficult to construct because concurrent accesses by different processes can conflict with one another. One simple approach is to use a global lock to restrict access to one process at a time. But this can severely affect performance. This talk will present a survey of some of the interesting techniques that have been developed to build efficient concurrent data structures. It will also discuss how we think concurrent data structures should be evaluated.

关键词： correctness experiments concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

Constructing concurrent data structures on FPGA with Channels 19

Constructing Concurrent Data Structures on FPGA with Channel...

引用

ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA)

作者： Yan, Hui Li, Zhaoshi Liu, Leibo Yin, Shouyi Wei, Shaojun Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450361378

The performance of High-Level Synthesis (HLS) applications with irregular data structures is limited by its imperative programming paradigm like C/C++. In this paper, we show that constructing concurrent data structures with channels, a programming construct derived from CSP (communicating sequential processes) paradigm, is an effective approach to improve the performance of these applications. We evaluate concurrent data structure for FPGA by synthesizing a K-means clustering algorithm on the Intel HARP2 platform. A fully pipelined KMC processing element can be synthesized from OpenCL with the help of a SPSC (single-producer-single-consumer) queue and stack built from channels, achieving 15.2x speedup over a sequential baseline. The number of processing element can be scaled up by leveraging a MPMC (multiple-producer-multiple-consumer) stack with work distribution for dynamic load balance. Evaluation shows that an additional 3.5x speedup can be achieved when 4 processing element is instantiated. These results show that the concurrent data structure built with channels has great potential for improving the parallelism of HLS applications. We hope that our study will stimulate further research into the potential of channel-based HLS.

关键词： High-Level Synthesis concurrent data structures Communicating Sequential Processes K-means clustering Parallelism

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：