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

Recoverable mutual exclusion with abortability

COMPUTING 2022年第10期104卷 2225-2252页

作者： Jayanti, Prasad Joshi, Anup Dartmouth Coll Hanover NH 03755 USA

Recent advances in non-volatile main memory (NVM) technology have spurred research on algorithms that are resilient to intermittent failures that cause processes to crash and subsequently restart. In this paper we present a Recoverable Mutual Exclusion (RME) algorithm that supports abortability. Our algorithm guarantees FCFS and a strong liveness property: processes do not starve even in runs consisting of infinitely many crashes, provided that a process crashes at most a finite number of times in each of its attempts. On DSM and Relaxed-CC multiprocessors, a process incurs O (min(k, log n)) RMRs in a passage and O(f + min (k, log n)) RMRs in an attempt, where n is the number of processes that the algorithm is designed for, k is the point contention of the passage or the attempt, and f is the number of times that p crashes during the attempt. On a Strict CC multiprocessor, the passage and attempt complexities are O(n) and 0(f + n), respectively. Our algorithm uses only the read, write, and CAS operations, which are commonly supported by multiprocessors. Attiya, Hendler, and Woelfel proved that, with any mutual exclusion algorithm, a process incurs at least 52 (log n) RMRs in a passage, if the algorithm uses only the read, write, and CAS operations (in: Proc. of the Fortieth ACM Symposium on Theory of Computing, New York, NY, USA, 2008). This lower bound implies that the worst-case RMR complexity of our algorithm is optimal for the DSM and Relaxed CC multiprocessors. This paper is an expanded version of our conference paper as reported by Jayanti and Joshi (in: Atig and Schwarzmann (eds) Networked Systems. Springer International Publishing, Cham, 2019), which presented the first Recoverable Mutual Exclusion (RME) algorithm that supports abortability. This algorithm from our conference paper (in: Atig and Schwarzmann (eds) Networked Systems. Springer International Publishing, Cham, 2019) admits starvation when there are infinitely many aborts in a run. In this paper,

关键词： Concurrent algorithm Synchronization Mutual exclusion Recoverable algorithm Fault tolerance Non-volatile main memory Shared memory multi-core algorithms

来源：评论

学校读者我要写书评

暂无评论

Recoverable mutual exclusion

引用

DISTRIBUTED COMPUTING 2019年第6期32卷 535-564页

作者： Golab, Wojciech Ramaraju, Aditya Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada

Mutex locks have traditionally been the most common mechanism for protecting shared data structures in concurrent programs. However, the robustness of such locks against process failures has not been studied thoroughly. The vast majority of mutex algorithms are designed around the assumption that processes are reliable, meaning that a process may not fail while executing the lock acquisition and release code, or while inside the critical section. If such a failure does occur, then the liveness properties of a conventional mutex lock may cease to hold until the application or operating system intervenes by cleaning up the internal structure of the lock. For example, a process that is attempting to acquire an otherwise starvation-free mutex may be blocked forever waiting for a failed process to release the critical section. Adding to the difficulty, if the failed process recovers and attempts to acquire the same mutex again without appropriate cleanup, then the mutex may become corrupted to the point where it loses safety, notably the mutual exclusion property. We address this challenge by formalizing the problem of recoverable mutual exclusion, and proposing several solutions that vary both in their assumptions regarding hardware support for synchronization, and in their efficiency. Compared to known solutions, our algorithms are more robust as they do not restrict where or when a process may crash, and provide stricter guarantees in terms of efficiency, which we define in terms of remote memory references.

关键词： Mutual exclusion Fault tolerance Recovery Concurrency Synchronization Shared memory Non-volatile main memory multi-core algorithms Durable data structures

来源：评论

学校读者我要写书评

暂无评论

Novel multi-Layer Network Decomposition Boosting Acceleration of multi-core algorithms

Novel Multi-Layer Network Decomposition Boosting Acceleratio...

引用

IEEE International Conference on Application-specific Systems, Architectures and Processors

作者： Athanasios K. Grivas Terrence Mak Alex Yakovlev Jonny Wray School of Electrical and Electronic Engineering Newcastle University UK Department of Computer Science and Engineering The Chinese University of Hong Kong China

ISBN: (纸本)9781479904945

Complex networks are a technique for the modeling and analysis of large data sets in many scientific and engineering disciplines. Due to their excessive size conventional algorithms and single core processors struggle with the efficient processing of such networks. Employing multi-core graphic processing units (CPUs) could provide sufficient processing power for the analysis of such networks. However, commonly designed algorithms cannot exploit these massively parallel processing power for the analysis of such networks. In this paper, we present the multi Layer Network Decomposition (MLND) approach which provides a general approach for parallel network analysis using multi-core processors via efficient partitioning and mapping of networks onto GPU architectures. Evaluation using a 336 core GPU graphic card demonstrated a 16x speed-up in complex network analysis relative to a CPU based approach.

关键词： MLND GPU multi-core algorithms GRAPPER PICK UP Graphics Processing Unit processing power complex networks central processing units Network multilayer network multi-core processors Network analysis

来源：评论

学校读者我要写书评

暂无评论

A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Both CC and DSM 19

A Recoverable Mutex Algorithm with Sub-logarithmic RMR on Bo...

引用

38th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Jayanti, Prasad Jayanti, Siddhartha Joshi, Anup Dartmouth Coll Hanover NH 03755 USA MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450362177

In light of recent advances in non-volatilemain memory technology, Golab and Ramaraju reformulated the traditional mutex problem into the novel Recoverable Mutual Exclusion (RME) problem. In the best known solution for RME, due to Golab and Hendler from PODC 2017, a process incurs at most O(log n/log log n) remote memory references (RMRs) per passage on a system with n processes, where a passage is an interval from when a process enters the Try section to when it subsequently returns to Remainder. Their algorithm, however, guarantees this bound only for cache-coherent (CC) multiprocessors, leaving open the question of whether a similar bound is possible for distributed shared memory (DSM) multiprocessors. We answer this question affirmatively by designing an algorithm for a system with n processes, such that, it satisfies the same complexity bound as Golab and Hendler's for both CC and DSM multiprocessors. Our algorithm has some additional advantages over Golab and Hendler's: (i) its Exit section is wait-free, (ii) it uses only the Fetch-and-Store instruction, and (iii) on a CC machine our algorithm needs each process to have a cache of only O(1) words, while their algorithm needs a cache of size that is a function of n.

关键词： concurrent algorithm synchronization mutual exclusion recoverable algorithm fault tolerance non-volatile main memory shared memory multi-core algorithms

来源：评论

学校读者我要写书评

暂无评论

Recoverable Mutual Exclusion with Abortability 7th

Recoverable Mutual Exclusion with Abortability

引用

7th International Conference on Networked Systems (NETYS)

作者： Jayanti, Prasad Joshi, Anup Dartmouth Coll Hanover NH 03755 USA

ISBN: (纸本)9783030312770;9783030312763

In light of recent advances in non-volatile main memory technology, there has been a flurry of research in designing algorithms that are resilient to process crashes. As a result of main memory non-volatility, a process is allowed to crash any time during the execution, without affecting the state of the data stored in the main memory. With the assumption that a process eventually restarts after a crash, prior works have focused on designing mutual exclusion algorithms that use the non-volatile main memory to recover from such crashes. Such mutual exclusion algorithms that provide multiple processes with a mutually exclusive access to a shared resource in the presence of process crashes are called Recoverable Mutual Exclusion (RME) algorithms. We present the first RME algorithm where a process has the ability to abort executing the algorithm, if it decides to give up its request for a shared resource before being granted access to that resource. With n being the maximum number of processes for which the algorithm is designed, in the absence of a crash our algorithm guarantees a worst-case remote memory references (RMR) complexity of O(log n) per passage on the Distributed Shared Memory (DSM) machines, and a complexity of O(log n) or O(n) on Cache Coherent (CC) machines, depending on how caches are managed.

关键词： Concurrent algorithm Synchronization Mutual exclusion Recoverable algorithm Fault tolerance Non-volatile main memory Shared memory multi-core algorithms

来源：评论

学校读者我要写书评

暂无评论

Nesting-Safe Recoverable Linearizability: Modular Constructions for Non-Volatile Memory 18

Nesting-Safe Recoverable Linearizability: Modular Constructi...

引用

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

作者： Attiya, Hagit Ben-Baruch, Ohad Hendler, Danny Technion Dept Comp Sci Haifa Israel Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450357951

We presents a novel abstract individual-process crash-recovery model for non-volatile memory, which enables modularity, so that complex recoverable objects can be constructed in a modular manner from simpler recoverable base objects. Within the framework of this model, we define nesting-safe recoverable linearizability (NRL) - a novel correctness condition that captures the requirements for nesting recoverable objects. Informally, NRL allows the recovery code to extend the interval of the failed operation until the recovery code succeeds to complete (possibly after multiple failures and recovery attempts). Unlike previous correctness definitions, the NRL condition implies that, following recovery, an implemented (higher-level) recoverable operation is able to complete its invocation of a base-object operation and obtain its response. We present algorithms for nesting-safe recoverable primitives, namely, recoverable versions of widely-used primitive shared-memory operations such as read, write, test-and-set and compare-and-swap, which can be used to implement higher-level recoverable objects. We then exemplify how these recoverable base objects can be used for constructing a recoverable counter object. Finally, we prove an impossibility result on wait-free implementations of recoverable test-and-set (TAS) objects from read, write and TAS operations, thus demonstrating that our model also facilitates rigorous analysis of the limitations of recoverable concurrent objects.

关键词： Concurrency shared memory multi-core algorithms wait-freedom lock-freedom nonblocking

来源：评论

学校读者我要写书评

暂无评论

Recoverable Mutual Exclusion Under System-Wide Failures 18

Recoverable Mutual Exclusion Under System-Wide Failures

引用

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

作者： Golab, Wojciech Hendler, Danny Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450357951

Recoverable mutual exclusion (RME) is a variation on the classic mutual exclusion (ME) problem that allows processes to crash and recover. The time complexity of RME algorithms is quantified in the same way as for ME, namely by counting remote memory references-expensive memory operations that traverse the processor-to-memory interconnect. Prior work has established that the RMR complexity of the RME problem for n processes is T(logn) for the class of algorithms that use read/write registers and single-word comparison primitives such as Compare-And-Swap (Golab and Ramaraju 2016), O(logn/log logn) for the class of algorithms that use read/write registers and additional single-word read-modify-primitives such as Fetch-And-Store (Golab and Hendler 2017), and T(1) for the class of algorithms that use read/write registers and specialized double-word read-modify-write primitives (Golab and Hendler 2017). These complexity bounds hold in a model of computation where processes may fail independently, and where a process that fails while accessing the mutex is required to recover eventually. This body of work leaves open two important questions: (i) what is the tight bound on the RMR complexity of RME for the class of algorithms that use read/write registers and commonly supported single-word read-modify-primitives;and (ii) how is the RMR complexity of RME affected by variations in the failure model? This paper answers both questions partially by showing that RME can be solved using O(1) RMRs per passage in the worst case in a model where failures are system-wide (i.e., all processes crash simultaneously), and processes receive additional information from the environment regarding the occurrence of the failure. The upper bound algorithm we present relies crucially on a novel RMR-efficient barrier that processes use to synchronize recovery actions after each failure. The barrier uses read/write registers and single-word Compare-And-Swap only. Additionally, we present a transfo

关键词： Mutual exclusion recovery fault tolerance concurrency shared memory multi-core algorithms non-volatile main memory persistent data structures

来源：评论

学校读者我要写书评

暂无评论

Separating Lock-Freedom from Wait-Freedom 18

Separating Lock-Freedom from Wait-Freedom

引用

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

作者： Attiya, Hagit Castaneda, Armando Hendler, Danny Perrin, Matthieu Technion Dept Comp Sci Haifa Israel Univ Nacl Autonoma Mexico Inst Matemat Mexico City DF Mexico Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel Univ Nantes LS2N Nantes France

ISBN: (纸本)9781450357951

A long-standing open question has been whether lock-freedom and wait-freedom are fundamentally different progress conditions, namely, can the former be provided in situations where the latter cannot? This paper answers the question in the affirmative, by proving that there are objects with lock-free implementations, but without wait-free implementations-using objects of any finite power. We precisely define an object called n-process long-lived approximate agreement (n-LLAA), in which two sets of processes associated with two sides, 0 or 1, need to decide on a sequence of increasingly closer outputs. We prove that 2-LLAA has a lock-free implementation using reads and writes only, while n-LLAA has a lock-free implementation using reads, writes and (n - 1)-process consensus objects. In contrast, we prove that there is no wait-free implementation of the n-LLAA object using reads, writes and specific (n - 1)-process consensus objects, called (n - 1)-window registers.

关键词： concurrency shared memory multi-core algorithms wait-freedom lock-freedom nonblocking

来源：评论

学校读者我要写书评

暂无评论

Scalable training of 3D convolutional networks on multi- and many-cores

引用

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING 2017年 106卷 195-204页

作者： Zlateski, Aleksandar Lee, Kisuk Seung, H. Sebastian MIT Elect Engn & Comp Sci Dept Cambridge MA 02139 USA MIT Brain & Cognit Sci Dept Cambridge MA 02139 USA Princeton Univ Princeton Neurosci Inst Princeton NJ 08540 USA Princeton Univ Comp Sci Dept Princeton NJ 08540 USA

Convolutional networks (ConvNets) have become a popular approach to computer vision. Here we consider the parallelization of ConvNet training, which is computationally costly. Our novel parallel algorithm is based on decomposition into a set of tasks, most of which are convolutions or FFTs. Theoretical analysis suggests that linear speedup with the number of processors is attainable. To attain such performance on real shared-memory machines, our algorithm computes convolutions converging on the same node of the network with temporal locality to reduce cache misses, and sums the convergent convolution outputs via an almost wait-free concurrent method to reduce time spent in critical sections. Benchmarking with multi-core CPUs shows speedup roughly equal to the number of physical cores. We also demonstrate 90x speedup on a many-core CPU (Xeon Phi Knights Corner). Our algorithm can be either faster or slower than certain GPU implementations depending on specifics of the network architecture, kernel sizes, and density and size of the output patch. (C) 2017 Elsevier Inc. All rights reserved.

关键词： Convolutional neural networks Deep learning FFT convolution Dynamic scheduling multi-core algorithms Wait-free summation

来源：评论

学校读者我要写书评

暂无评论

Recoverable Mutual Exclusion in Sub-logarithmic Time 17

Recoverable Mutual Exclusion in Sub-logarithmic Time

引用

36th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Golab, Wojciech Hendler, Danny Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450349925

关键词： Mutual exclusion recovery fault tolerance concurrency shared memory multi-core algorithms non-volatile main memory persistent data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：