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

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

来源：评论

学校读者我要写书评

暂无评论

Publish on Ping: A Better Way to Publish Reservations in Memory Reclamation for concurrent data structures 25

Publish on Ping: A Better Way to Publish Reservations in Mem...

引用

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

concurrent data structures for Near-Memory Computing 17

Concurrent Data Structures for Near-Memory Computing

引用

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

作者： Liu, Zhiyu Calciu, Irina Herlihy, Maurice Mutlu, Onur Brown Univ Comp Sci Dept Providence RI 02912 USA VMware Res Grp Palo Alto CA USA Swiss Fed Inst Technol Comp Sci Dept Zurich Switzerland

ISBN: (纸本)9781450345934

The performance gap between memory and CPU has grown exponentially. To bridge this gap, hardware architects have proposed near-memory computing (also called processing-in-memory, or PIM), where a lightweight processor (called a PIM core) is located close to memory. Due to its proximity to memory, a memory access from a PIM core is much faster than that from a CPU core. New advances in 3D integration and die-stacked memory make PIM viable in the near future. Prior work has shown significant performance improvements by using PIM for embarrassingly parallel and data-intensive applications, as well as for pointer-chasing traversals in sequential data structures. However, current server machines have hundreds of cores, and algorithms for concurrent data structures exploit these cores to achieve high throughput and scalability, with significant benefits over sequential data structures. Thus, it is important to examine how PIM performs with respect to modern concurrent data structures and understand how concurrent data structures can be developed to take advantage of PIM. This is paper is the first to examine the design of concurrent data structures for PIM. We show two main results: (1) naive PIM data structures cannot outperform state-of-the-art concurrent data structures, such as pointer-chasing data structures and FIFO queues, (2) novel designs for PIM data structures, using techniques such as combining, partitioning and pipelining, can outperform traditional concurrent data structures, with a significantly simpler design.

关键词： concurrent data structures parallel programs processing-in-memory near-memory computing

来源：评论

学校读者我要写书评

暂无评论

Diversity driven adaptive test generation for concurrent data structures

引用

INFORMATION AND SOFTWARE TECHNOLOGY 2018年 103卷 162-173页

作者： Ma, Linhai Wu, Peng Chen, Tsong Yueh Chinese Acad Sci Inst Software State Key Lab Comp Sci Beijing Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Swinburne Univ Technol Dept Comp Sci & Software Engn Hawthorn Vic Australia Univ Miami Dept Comp Sci Coral Gables FL 33124 USA

Context Testing concurrent data structures remains a notoriously challenging task, due to the nondeterminism of multi-threaded tests and the exponential explosion on the number of thread schedules. Objective: We propose an automated approach to generate a series of concurrent test cases in an adaptive manner, i.e., the next test cases are generated with the guarantee to discover the thread schedules that have not yet been activated by the previous test cases. Method Two diversity metrics are presented to induce such adaptive test cases from a static and a dynamic perspective, respectively. The static metric enforces the diversity in the program structures of the test cases;while the dynamic one enforces the diversity in their capabilities of exposing untested thread schedules. We implement three adaptive test generation approaches for C/C + + concurrent data structures, based on the stateof-the-art active testing engine Maple. Results: We then report an empirical study with 9 real-world C/C + + concurrent data structures, which demonstrates the efficiency of our test generation approaches in terms of the number of thread schedules discovered, as well as the time and the number of tests required for testing a concurrent data structure. Conclusion: Hence, by using diverse test cases derived from the static and dynamic perspectives, our adaptive test generation approaches can deliver a more efficient coverage of the thread schedules of the concurrent data structure under test.

关键词： concurrent data structures Test case diversity Test case generation Active testing Adaptive random testing

来源：评论

学校读者我要写书评

暂无评论

A Systematic Methodology for Optimization of Applications Utilizing concurrent data structures

引用

IEEE TRANSACTIONS ON COMPUTERS 2016年第7期65卷 2019-2031页

作者： Papadopoulos, Lazaros Walulya, Ivan Tsigas, Philippas Soudris, Dimitrios Natl Tech Univ Athens Sch Elect & Comp Engn Athens Greece Chalmers Univ Technol Sch Comp Sci & Engn S-41296 Gothenburg Sweden

Modern multicore embedded systems often execute applications that rely heavily on concurrent data structures. The selection of efficient concurrent data structure implementations for a specific application is usually a complex and time consuming task, because each design decision often affects the performance and the energy consumption of the embedded system in various and occasionally unpredictable ways. The complexity is normally addressed by developers by adopting ad-hoc design solutions, which are often suboptimal and yield poor results. To face this problem, we propose a semi-automated methodology for the optimization of applications that utilize concurrent data structures that is based on design space exploration. The proposed approach is evaluated by using both microbenchmarks and real-world applications that are executed on multicore embedded systems with different architectural specifications. Our results show that we can identify various trade-offs between different data structure implementations that can be used to optimize applications that rely on concurrent data structures.

关键词： concurrent data structures design space exploration embedded systems performance energy

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Black-box concurrent data structures for NUMA Architectures 17

Black-box Concurrent Data Structures for NUMA Architectures

引用

22nd ACM International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS)

作者： Calciu, Irina Sen, Siddhartha Balakrishnan, Mahesh Aguilera, Marcos K. VMware Res Palo Alto CA 94304 USA Microsoft Res Beijing Peoples R China Yale Univ New Haven CT 06520 USA

ISBN: (纸本)9781450344654

High-performance servers are non-uniform memory access (NUMA) machines. To fully leverage these machines, programmers need efficient concurrent data structures that are aware of the NUMA performance artifacts. We propose Node Replication (NR), a black-box approach to obtaining such data structures. NR takes an arbitrary sequential data structure and automatically transforms it into a NUMA-aware concurrent data structure satisfying linearizability. Using NR requires no expertise in concurrent data structure design, and the result is free of concurrency bugs. NR draws ideas from two disciplines: shared-memory algorithms and distributed systems. Briefly, NR implements a NUMA-aware shared log, and then uses the log to replicate data structures consistently across NUMA nodes. NR is best suited for contended data structures, where it can outperform lock-free algorithms by 3.1x, and lock-based solutions by 30x. To show the benefits of NR to a real application, we apply NR to the data structures of Redis, an in-memory storage system. The result outperforms other methods by up to 14x. The cost of NR is additional memory for its log and replicas.

关键词： numa architecture log replication black-box techniques concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

Fast Non-intrusive Memory Reclamation for Highly-concurrent data structures 2016

Fast Non-intrusive Memory Reclamation for Highly-Concurrent ...

引用

15th ACM SIGPLAN International Symposium on Memory Management (ISMM 2016)

作者： Dice, Dave Herlihy, Maurice Kogan, Alex Oracle Labs Austin TX 75085 USA Brown Univ Providence RI 02912 USA

ISBN: (纸本)9781450343176

Current memory reclamation mechanisms for highly-concurrent data structures present an awkward trade-off. Techniques such as epoch-based reclamation perform well when all threads are running on dedicated processors, but the delay or failure of a single thread will prevent any other thread from reclaiming memory. Alternatives such as hazard pointers are highly robust, but they are expensive because they require a large number of memory barriers. This paper proposes three novel ways to alleviate the costs of the memory barriers associated with hazard pointers and related techniques. These new proposals are backward-compatible with existing code that uses hazard pointers. They move the cost of memory management from the principal code path to the infrequent memory reclamation procedure, significantly reducing or eliminating memory barriers executed on the principal code path. These proposals include (1) exploiting the operating system's memory protection ability, (2) exploiting certain x86 hardware features to trigger memory barriers only when needed, and (3) a novel hardware-assisted mechanism, called a hazard lookaside buffer (HLB) that allows a reclaiming thread to query whether there are hazardous pointers that need to be flushed to memory. We evaluate our proposals using a few fundamental data structures (linked lists and skiplists) and libcuckoo, a recent high-throughput hash-table library, and show significant improvements over the hazard pointer technique.

关键词： memory reclamation concurrent data structures hazard pointers memory barriers

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：