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

A Conflict-Resilient Lock-Free Linearizable Calendar Queue

ACM TRANSACTIONS ON PARALLEL COMPUTING 2024年第1期11卷 1-32页

作者： Marotta, Romolo Ianni, Mauro Pellegrini, Alessandro Quaglia, Francesco Univ Roma Tor Vergata I-00100 Rome Italy Lockless Srl I-00100 Rome Italy

In the last two decades, great attention has been devoted to the design of non-blocking and linearizable data structures, which enable exploiting the scaled-up degree of parallelism in off-the-shelf shared-memory multi-core machines. In this context, priority queues are highly challenging. Indeed, concurrent attempts to extract the highest-priority item are prone to create detrimental thread conflicts that lead to abort/retry of the operations. In this article, we present the first priority queue that jointly provides: (i) lock-freedom and linearizability;(ii) conflict resiliency against concurrent extractions;(iii) adaptiveness to different contention profiles;and (iv) amortized constant-time access for both insertions and extractions. Beyond presenting our solution, we also provide proof of its correctness based on an assertional approach. Also, we present an experimental study on a 64-CPU machine, showing that our proposal provides performance improvements over state-of-the-art non-blocking priority queues.

关键词： Data structures design and analysis shared memory algorithms concurrent algorithms non-blocking priority queue pending event set

来源：评论

学校读者我要写书评

暂无评论

CGCExplorer: A semi-automated search procedure for provably correct concurrent collectors

引用

ACM SIGPLAN NOTICES 2007年第6期42卷 456-467页

作者： Vechev, Martin T. Yahav, Eran Bacon, David F. Rinetzky, Noam Univ Cambridge Cambridge CB2 1TN England Tel Aviv Univ Tel Aviv Israel

concurrent garbage collectors are notoriously hard to design, implement, and verify. We present a framework for the automatic exploration of a space of concurrent mark-and-sweep collectors. In our framework, the designer specifies a set of "building blocks" from which algorithms can be constructed. These blocks reflect the designer's insights about the coordination between the collector and the mutator. Given a set of building blocks, our framework automatically explores a space of algorithms, using model checking with abstraction to verify algorithms in the space. We capture the intuition behind some common mark-and-sweep algorithms using a set of building blocks. We utilize our framework to automatically explore a space of more than 1, 600, 000 algorithms built from these blocks, and derive over 100 correct fine-grained algorithms with various space, synchronization, and precision tradeoffs.

关键词： concurrent garbage collection concurrent algorithms verification synthesis

来源：评论

学校读者我要写书评

暂无评论

Deriving linearizable fine-grained concurrent objects

引用

ACM SIGPLAN NOTICES 2008年第6期43卷 125-135页

作者： Vechev, Martin Yahav, Eran IBM Res Corp Yorktown Hts NY 10598 USA

Practical and efficient algorithms for concurrent data structures are difficult to construct and modify. algorithms in the literature are often optimized for a specific setting, making it hard to separate the algorithmic insights from implementation details. The goal of this work is to systematically construct algorithms for a concurrent data structure starting from its sequential implementation. Towards that goal, we follow a construction process that combines manual steps corresponding to high-level insights with automatic exploration of implementation details. To assist us in this process, we built a new tool called PARAGLIDER. The tool quickly explores large spaces of algorithms and uses bounded model checking to check linearizability of algorithms. Starting from a sequential implementation and assisted by the tool, we present the steps that we used to derive various highly-concurrent algorithms. Among these algorithms is a new fine-grained set data structure that provides a wait-free contains operation, and uses only the compare-and-swap ( CAS) primitive for synchronization.

关键词： algorithms verification concurrent algorithms verification synthesis model checking linearizability

来源：评论

学校读者我要写书评

暂无评论

Efficient Compute at the Edge: Optimizing Energy Aware Data Structures for Emerging Edge Hardware 16

Efficient Compute at the Edge: Optimizing Energy Aware Data ...

引用

International Conference on High Performance Computing and Simulation (HPCS)

作者： Khan, Amin M. Umar, Ibrahim Phuong Hoai Ha UiT Arctic Univ Norway Dept Comp Sci Tromso Norway

ISBN: (纸本)9781538678794

The advent of exascale computing, with the unparalleled rise in the scale of data in Internet of Things (IoT), high performance computing (HPC), and big data domains, both at the center and the edge of the system, requires optimal exploitation of energy-efficient computing hardware dedicated for edge processing. Emerging hardware for data processing at the edge must take advantage of advanced concurrent data locality-aware algorithms and data structures in order to provide better throughput and energy efficiency. Their design must be performance portable for their implementation to perform equally well on the edge hardware as well as other high performance computing, embedded and accelerator platforms. concurrent search trees are one such widely used back-end for many important big data systems, databases, and file systems. We analyze DeltaTree, a concurrent energy-efficient and locality-aware data structure based on relaxed cache-oblivious model and van Emde Boas trees, on Intel's specialized computing platform Movidius Myriad 2, designed for machine vision and computing capabilities at the edge. We compare the throughput and energy efficiency of DeltaTree with B-link tree, a highly concurrent B+tree, on Movidius Myriad 2, along with a high performance computing platform (Intel Xeon), an ARM embedded platform, and an accelerator platform (Intel Xeon Phi). The results show that DeltaTree is performance portable, providing better energy-efficiency and throughput than B-link tree on these platforms for most workloads. For Movidius Myriad 2 in particular, DeltaTree performs really well with its throughput and efficiency up to 4x better than B-link tree.

关键词： edge computing energy efficient algorithms concurrent algorithms data locality binary search trees

来源：评论

学校读者我要写书评

暂无评论

Read-Uncommitted Transactions for Smart Contract Performance 39

Read-Uncommitted Transactions for Smart Contract Performance

引用

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

作者： Cook, Victor Painter, Zachary Peterson, Christina Dechev, Damian Univ Cent Florida Comp Sci Dept Orlando FL 32816 USA

ISBN: (纸本)9781728125190

Smart contract transactions demonstrate issues of performance and correctness that application programmers must work around. Although the blockchain consensus mechanism approaches ACID compliance, use cases that rely on frequent state changes are impractical due to the block publishing interval of O(10(1)) seconds. The effective isolation level is READ COMMITTED, only revealing state transitions at the end of the block interval. Values read may be stale and not match program order, causing many transactions to fail when a block is committed. This paper perceives the blockchain as a transactional data structure, using this analogy in the development of a new algorithm, Hash-Mark-Set (HMS), that improves transaction throughput by providing a READ-UNCOMMITTED view of state variables. HMS creates a directed acyclic graph (DAG) from the pending transaction pool. The transaction order derived from the DAG is used to provide a READ-UNCOMMITTED view of the data for new transactions, which enter the DAG as they are received. An implementation of HMS is provided, interoperable with Ethereum and ready for use in smart contracts. Over a wide range of transaction mixes, HMS is demonstrated to improve throughput. A side product of the implementation is a new technique, Runtime Argument Augmentation (RAA), that allows smart contracts to communicate with external data services before submitting a transaction. RAA has use cases beyond HMS and can serve as a lightweight replacement for blockchain oracles.

关键词： Blockchain Smart contracts concurrent algorithms Transaction throughput

来源：评论

学校读者我要写书评

暂无评论

BQ: A Lock-Free Queue with Batching 18

BQ: A Lock-Free Queue with Batching

引用

30th ACM Symposium on Parallelism in algorithms and Architectures (SPAA)

作者： Milman, Gal Kogan, Alex Lev, Yossi Luchangco, Victor Petrank, Erez Technion Haifa Israel Oracle Labs Redwood Shores CA USA

ISBN: (纸本)9781450357999

concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this paper we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates a significant performance improvement of up to 16x (depending on batch lengths), compared to previous queue implementations.

关键词： concurrent algorithms concurrent Data Structures Lock-Freedom Linearizability FIFO Queue

来源：评论

学校读者我要写书评

暂无评论

Lightweight Contention Management for Efficient Compare-and-Swap Operations

Lightweight Contention Management for Efficient Compare-and-...

引用

19th International Conference on Euro-Par

作者： Dice, David Hendler, Danny Mirsky, Ilya Oracle Sun Labs Redwood City CA 94065 USA Ben Gurion Univ Negev Dept Comp Sci & Telekom Innovat IL-84105 Beer Sheva Israel Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

ISBN: (纸本)9783642400476

Many concurrent data-structure implementations use the well-known compare-and-swap (CAS) operation, supported in hardware by most modern multiprocessor architectures, for inter-thread synchronization. A key weakness of the CAS operation is the degradation in its performance in the presence of memory contention. In this work we study the following question: can software-based contention management improve the efficiency of hardware-provided CAS operations? Our performance evaluation establishes that lightweight contention management support can greatly improve performance under medium and high contention levels while typically incurring only small overhead when contention is low.

关键词： Compare-and-swap contention management concurrent algorithms

来源：评论

学校读者我要写书评

暂无评论

Functional Faults 20

Functional Faults

引用

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

作者： Sheffi, Gali Petrank, Erez Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781450369350

Hardware and software faults increasingly surface in today's computing environment and vast theoretical and practical research efforts are devoted to ameliorate the effects of malfunctionality in the computing process. Most research to date, however, has focused on how to discover and handle faulty data. In this paper we formalize and study faulty functionality in a modern multicore shared-memory environment. Functional faults have been previously studied in the architecture community. However, they have never been formally defined and lower/upper bounds were not previously proven. We present a model of functional faults, and study avenues that allow tolerating functional faults while maintaining the correctness of the entire computation. We exemplify this model by constructing a robust consensus protocol from functionally-faulty compare-and-swap objects. We then show a (tight) impossibility result for the same construction, when the number of faults exceeds a certain threshold. Interestingly, for some fault types, more functional faults can be tolerated than the analogue data faults, beating an impossibility result for data faults and demonstrating the difference between the two models.

关键词： concurrent algorithms shared memory lowerbounds fault-tolerance hardware faults software faults

来源：评论

学校读者我要写书评

暂无评论

MULTIPROCESSOR ARCHITECTURES FOR SAR DATA-PROCESSING

MULTIPROCESSOR ARCHITECTURES FOR SAR DATA-PROCESSING

引用

1991 INTERNATIONAL GEOSCIENCE AND REMOTE SENSING SYMP - REMOTE SENSING : GLOBAL MONITORING FOR EARTH MANAGEMENT ( IGARSS 91 )

作者： ALBRIZIO, R ALOISIO, G MAZZONE, A VENEZIANI, N IESI-CNR Bari Italy

ISBN: (纸本)0879426756

Distributed memory multiprocessor architectures for synthetic aperture radar (SAR) digital data compression are discussed. Using the range-Doppler approach, the main computational load occurs in the range and azimuth compressions, for which one-dimensional circular convolutions in the Fourier domain are exploited. The raw-data compression can be pipelined by means of two independent processors, one for the range and the other for the azimuth direction. From the algorithmic point of view, the inherent structure of the multidimensional discrete Fourier transform algorithms used for fast convolution suggests that their computation could be distributed to show that these principles can be exploited to perform up to real-time SAR data focusing.

关键词： SAR REAL-TIME MULTIPROCESSOR ARCHITECTURES concurrent algorithms DFT

来源：评论

学校读者我要写书评

暂无评论

An Efficient Implementation of Boolean Grobner Basis Computation 3rd

引用

3rd Latin American High-Performance Computing Conference (CARLA)

作者： Castro Campos, Rodrigo Alexander Sagols Troncoso, Feliu Davino Zaragoza Martinez, Francisco Javier Univ Autonoma Metropolitana Azcapotzalco Optimizac Mexico City DF Mexico Inst Politecn Nacl Ctr Invest & Estudios Avanzados Dept Matemat Mexico City DF Mexico Univ Autonoma Metropolitana Azcapotzalco Dept Sistemas Mexico City DF Mexico

ISBN: (纸本)9783319579726;9783319579719

The computation of boolean Grobner bases has become an increasingly popular technique for solving systems of boolean equations that appear in cryptography. This technique has been used to solve some cryptosystems for the first time. In this paper, we describe a new concurrent algorithm for boolean Grobner basis computation that is capable of solving the first HFE challenge. We also discuss implementation details, including optimal runtime parameters that depend on the CPU architecture. Our implementation is available as open source software.

关键词： Grobner basis Boolean ideals concurrent algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：