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

concurrent, Parallel Garbage Collection in Linear Time

ACM SIGPLAN NOTICES 2014年第11期49卷 47-58页

作者： Brandt, Steven R. Krishnan, Hari Sharma, Gokarna Busch, Costas Louisiana State Univ Ctr Computat & Technol Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA Louisiana State Univ Sch Elect Engn & Comp Sci Baton Rouge LA 70803 USA

This paper presents a new concurrent garbage collection algorithm based on two types of reference, strong and weak, to link the graph of objects. Strong references connect the roots to all the nodes in the graph but do not contain cycles. Weak references may, however, contain cycles. Advantages of this system include: (1) reduced processing, nontrivial garbage collection work is only required when the last strong reference is lost;(2) fewer memory traces to delete objects, a garbage cycle only needs to be traversed twice to be deleted;(3) fewer memory traces to retain objects, since the collector can often prove objects are reachable without fully tracing support cycles to which the objects belong;(4) concurrency, it can run in parallel with a live system without "stopping the world;" (5) parallel, because collection operations in different parts of the memory can proceed at the same time. Previous variants of this technique required exponential cleanup time [27, 31], but our algorithm is linear in total time, i.e. any changes in the graph take only O(N) time steps, where N is the number of edges in the affected subgraph (e.g. the subgraph whose strong support is affected by the operations).

关键词： Algorithms Performance Experimentation Languages Design Termination Garbage Collection Parallel programming theory and models Compilers and runtime systems Software for productivity parallel programming Parallel algorithms concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

CheckFence: Checking consistency of concurrent data types on relaxed memory models

引用

ACM SIGPLAN NOTICES 2007年第6期42卷 12-21页

作者： Burckhardt, Sebastian Alur, Rajeev Martin, Milo M. K. Univ Penn Philadelphia PA 19104 USA

Concurrency libraries can facilitate the development of multi-threaded programs by providing concurrent implementations of familiar data types such as queues or sets. There exist many optimized algorithms that can achieve superior performance on multiprocessors by allowing concurrent data accesses without using locks. Unfortunately, such algorithms can harbor subtle concurrency bugs. Moreover, they require memory ordering fences to function correctly on relaxed memory models. To address these difficulties, we propose a verification approach that can exhaustively check all concurrent executions of a given test program on a relaxed memory model and can verify that they are observationally equivalent to a sequential execution. Our Check-Fence prototype automatically translates the C implementation code and the test program into a SAT formula, hands the latter to a standard SAT solver, and constructs counterexample traces if there exist incorrect executions. Applying CheckFence to five previously published algorithms, we were able to (1) find several bugs (some not previously known), and (2) determine how to place memory ordering fences for relaxed memory models.

关键词： verification concurrent data structures multi-threading shared-memory multiprocessors memory models lock-free synchronization sequential consistency software model checking

来源：评论

学校读者我要写书评

暂无评论

Read/write fence-free work-stealing with multiplicity

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2024年 186卷

作者： Castaneda, Armando Pina, Miguel Univ Nacl Autonoma Mexico Inst Matemat Ciudad Univ Mexico City 04510 Mexico Univ Nacl Autonoma Mexico Programa Doctorado Ciencia & Ingn Comp Ciudad Univ Mexico City 04510 Mexico

It has been shown that any nonblocking algorithm for work-stealing in the standard asynchronous shared memory model of computation must use expensive Read-After-Write synchronization patterns or atomic Read-Modify -Write instructions. Algorithms for relaxations of work-stealing have been proposed, which only partially avoid this impossibility result. In restricted models of computation, work-stealing algorithms have been designed that avoid Read-After-Write patterns and atomic Read-Modify-Write instructions. This paper considers work-stealing with multiplicity, a relaxation in which every task is taken by at least one process, and any process can take any task at most once. We study two variants of the relaxation, for each variant designing a Read/Write wait-free algorithm in the standard asynchronous shared memory model. The two algorithms are devoid of Read-After-Write synchronization patterns in all their operations, and additionally, the algorithm for the second variant has constant step complexity and is fence-free. Namely, no specific ordering among the algorithm's instructions is required beyond what is implied by data dependence. To our knowledge, these are the first algorithms for relaxations of work-stealing possessing all these properties. The algorithms are also solutions to relaxed versions of single-enqueuer multi-dequeuer queues. The theoretical results are complemented with an experimental evaluation showing that the benefits of relaxed work-stealing vary depending on the application, concretely on the complexity of the work associated with each task.

关键词： concurrent data structures Linearizability Relaxed data types Set-linearizability Work-stealing

来源：评论

学校读者我要写书评

暂无评论

Semantic Conflict Detection for Transactional data Structure Libraries 21

Semantic Conflict Detection for Transactional Data Structure...

引用

Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

作者： Yaodong Sheng Ahmed Hassan Michael Spear Lehigh University Bethlehem PA USA

ISBN: (纸本)9781450380706

The Transactional data Structure Library (TDSL) methodology improves the programmability and performance of concurrent software by making it possible for programmers to compose multiple concurrent data structure operations into coarse-grained transactions. Like transactional memory, TDSL enables arbitrarily many operations on arbitrarily many data structures to appear to other threads as a single atomic, isolated transaction. Like concurrent data structures, the individual operations on a TDSL data structure are optimized to avoid artificial contention. We introduce techniques for reducing false conflicts in TDSL implementations. Our approach allows expressing the postconditions of operations entirely via semantic properties, instead of through low-level structural properties. Our design is general enough to support lists, deques, ordered and unordered maps, and vectors. It supports richer programming interfaces than are available in existing TDSL implementations. It is also capable of precise memory management, which is necessary in low-level languages like C++.

关键词： synchronization transactional memory concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

Hyaline: Fast and Transparent Lock-Free Memory Reclamation 19

Hyaline: Fast and Transparent Lock-Free Memory Reclamation

引用

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing

作者： Ruslan Nikolaev Binoy Ravindran Virginia Tech Blacksburg VA USA

ISBN: (纸本)9781450362177

We present a new lock-free safe memory reclamation algorithm, Hyaline, which is fast, scalable, and transparent to the underlying data structures. Hyaline easily handles virtually unbounded number of threads that can be created and deleted dynamically, while retaining O(1) reclamation cost. We also extend Hyaline to avoid situations where stalled threads prevent others from reclaiming newly allocated objects, a common problem with epoch-based reclamation. Our evaluation reveals that Hyaline's throughput is high -- it steadily outperformed other reclamation schemes by >10% in one test and yielded even higher gains in oversubscribed scenarios.

关键词： memory reclamation lock-free concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

A predictable synchronisation algorithm 18

A predictable synchronisation algorithm

引用

Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

作者： Stefan Reif Wolfgang Schröder-Preikschat Friedrich-Alexander University Erlangen-Nürnberg

ISBN: (纸本)9781450349826

Interaction with physical objects often imposes latency requirements to multi-core embedded systems. One consequence is the need for synchronisation algorithms that provide predictable latency, in addition to high throughput. We present a synchronisation algorithm that needs at most 7 atomic memory operations per asynchronous critical section. The performance is competitive, at least, to locks.

关键词： concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

VBR: Version Based Reclamation 21

VBR: Version Based Reclamation

引用

Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures

作者： Gali Sheffi Maurice Herlihy Erez Petrank Technion Haifa Israel Brown University Providence RI USA

ISBN: (纸本)9781450380706

Safe lock-free memory reclamation is a difficult problem. Existing solutions follow three basic methods: epoch based reclamation, hazard pointers, and optimistic reclamation. Epoch-based methods are fast, but do not guarantee lock-freedom. Hazard pointer solutions are lock-free but typically do not provide high performance. Optimistic methods are lock-free and fast, but previous optimistic methods did not go all the way. While reads were executed optimistically, writes were protected by hazard pointers. In this work we present a new reclamation scheme called version based reclamation (VBR), which provides a full optimistic solution to lock-free memory reclamation, obtaining lock-freedom and high efficiency. Speculative execution is known as a fundamental tool for improving performance in various areas of computer science, and indeed evaluation with a lock-free linked-list, hash-table and skip-list shows that VBR outperforms state-of-the-art existing solutions.

关键词： shared memory concurrent data structures lock freedom safe memory reclamation

来源：评论

学校读者我要写书评

暂无评论

Drop the Anchor: Lightweight Memory Management for Non-Blocking data structures 13

Drop the Anchor: Lightweight Memory Management for Non-Block...

引用

Annual ACM Symposium on Parallel Algorithms and Architectures

作者： Anastasia Braginsky Alex Kogan Erez Petrank Computer Science Technion Oracle Labs

ISBN: (纸本)9781450315722

Efficient memory management of dynamic non-blocking data structures remains an important open question. Existing methods either sacrifice the ability to deallocate objects or reduce performance notably. In this paper, we present a novel technique, called Drop the Anchor, which significantly reduces the overhead associated with the memory management while reclaiming objects even in the presence of thread failures. We demonstrate this memory management scheme on the common linked list data structure. Using extensive evaluation, we show that Drop the Anchor significantly outperforms Hazard Pointers, the widely used technique for non-blocking memory management.

关键词： concurrent data structures progress guarantee lock-freedom parallel programming linked list memory management hazard pointers timestamps freezing

来源：评论

学校读者我要写书评

暂无评论

A concurrent multiway tree using the lazy locking mechanism 16

A concurrent multiway tree using the lazy locking mechanism

引用

Proceedings of the 26th Annual International Conference on Computer Science and Software Engineering

作者： Bing Yang Kenneth B. Kent Eric Aubanel Tobi Ajila Angela Lin University of New Brunswick Fredericton NB Canada IBM Ottawa Ottawa ON Canada

In this paper, we present a concurrent multiway tree algorithm using the lazy locking mechanism introduced in the lazy-list algorithm for concurrent linked lists. The multiway tree is represented in a left-child right-sibling tree, in which the keys are defined to represent the containing or ordering relationship among the nodes. We enhance the lazy locking mechanism by applying it to a concurrent left-child right-sibling tree algorithm, which deals with more complicated scenarios than linked lists. Our algorithm also optimized the lazy locking mechanism by simplifying the validation process and allowing threads to traverse fewer nodes to locate the target node when validation failed. The experimental results show that our optimization improves the throughput slightly over the Lazy-tree algorithm which uses the lazy locking mechanism in updating of the LCRS tree without our optimization, and both the Optimized and Lazy-tree algorithms significantly overtake the Global-rwLock approach, which uses a single reader-writer lock to ensure concurrent manipulation of the multiway tree.

关键词： left-child right-sibling tree representation parallel programming multiway tree concurrent data structures

来源：评论

学校读者我要写书评

暂无评论

A selective and biased choice of techniques for building a distributed data store 23

A selective and biased choice of techniques for building a d...

引用

Proceedings of the 17th ACM International Conference on Distributed and Event-based Systems

作者： Paweł Tomasz Wojciechowski Faculty of Computing and Telecommunications Institute of Computing Science Poznan University of Technology Poznań Poland

ISBN: (纸本)9798400701221

Single-machine data stores cannot support the scale and ubiquity of data today. The Internet applications and services must process a huge number of concurrent requests and events per second. So, they use distributed (or replicated) data stores which store and process data on multiple machines, offering key advantages in performance, scalability, and *** purpose of the talk is to present a selective and biased choice of techniques and results which can be used for building an efficient distributed data store. Biased, because I only present solutions and results developed within a research project that I did with my PhD students. Selective, because an exhaustive description would be too exhausting to fit into a single talk. Therefore I will be discussing in detail just the design of our novel database index for key-value data store systems, and only skim our other contributions that are directly related to distributed *** index, called Jiffy, has been designed with performance and scalability in mind. Therefore it has been designed as a lock-free concurrent data structure, which can dynamically adapt to the changing workload. It achieves superior performance despite built-in atomic operations (batch updates, snapshots, and range scans). During the talk I will be presenting Jiffy's architecture, the algorithms for inserting and looking up the key-value pairs, and the operations used for resizing the data structure *** other contributions of our project include: efficient support for replica state recovery after failures, either by extending the classic Paxos consensus algorithm, or through the use of persistent memory, and some surprising theoretical results which are applicable to distributed data store systems that compromise consistency in favour of high availability and speed, but also support operations ensuring strong consistency (which requires consensus among replicas).

关键词： mixed consistency paxos concurrent data structures lock-free skip list replica state recovery ordered index

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：