ترغب بنشر مسار تعليمي؟ اضغط هنا

Relaxed Queues and Stacks from Read/Write Operations

122   0   0.0 ( 0 )
 نشر من قبل Armando Casta\\~neda
 تاريخ النشر 2020
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

Considering asynchronous shared memory systems in which any number of processes may crash, this work identifies and formally defines relaxations of queues and stacks that can be non-blocking or wait-free while being implemented using only read/write operations. Set-linearizability and Interval-linearizability are used to specify the relaxations formally, and precisely identify the subset of executions which preserve the original sequential behavior. The relaxations allow for an item to be returned more than once by different operations, but only in case of concurrency; we call such a property multiplicity. The stack implementation is wait-free, while the queue implementation is non-blocking. Interval-linearizability is used to describe a queue with multiplicity, with the additional relaxation that a dequeue operation can return weak-empty, which means that the queue might be empty. We present a read/write wait-free interval-linearizable algorithm of a concurrent queue. As far as we know, this work is the first that provides formalizations of the notions of multiplicity and weak-emptiness, which can be implemented on top of read/write registers only.



قيم البحث

اقرأ أيضاً

128 - Ted Herman , Morten Mjelde 2008
Designing protocols and formulating convenient programming units of abstraction for sensor networks is challenging due to communication errors and platform constraints. This paper investigates properties and implementation reliability for a emph{loca l read-write} abstraction. Local read-write is inspired by the class of read-modify-write operations defined for shared-memory multiprocessor architectures. The class of read-modify-write operations is important in solving consensus and related synchronization problems for concurrency control. Local read-write is shown to be an atomic abstraction for synchronizing neighborhood states in sensor networks. The paper compares local read-write to similar lightweight operations in wireless sensor networks, such as read-all, write-all, and a transaction-based abstraction: for some optimistic scenarios, local read-write is a more efficient neighborhood operation. A partial implementation is described, which shows that three outcomes characterize operation response: success, failure, and cancel. A failure response indicates possible inconsistency for the operation result, which is the result of a timeout event at the operations initiator. The paper presents experimental results on operation performance with different timeout values and situations of no contention, with some tests also on various neighborhood sizes.
216 - Li Liu , Mengge He , Guanghui Xu 2021
Reading and writing research papers is one of the most privileged abilities that a qualified researcher should master. However, it is difficult for new researchers (eg{students}) to fully {grasp} this ability. It would be fascinating if we could trai n an intelligent agent to help people read and summarize papers, and perhaps even discover and exploit the potential knowledge clues to write novel papers. Although there have been existing works focusing on summarizing (emph{i.e.}, reading) the knowledge in a given text or generating (emph{i.e.}, writing) a text based on the given knowledge, the ability of simultaneously reading and writing is still under development. Typically, this requires an agent to fully understand the knowledge from the given text materials and generate correct and fluent novel paragraphs, which is very challenging in practice. In this paper, we propose a Deep ReAder-Writer (DRAW) network, which consists of a textit{Reader} that can extract knowledge graphs (KGs) from input paragraphs and discover potential knowledge, a graph-to-text textit{Writer} that generates a novel paragraph, and a textit{Reviewer} that reviews the generated paragraph from three different aspects. Extensive experiments show that our DRAW network outperforms considered baselines and several state-of-the-art methods on AGENDA and M-AGENDA datasets. Our code and supplementary are released at https://github.com/menggehe/DRAW.
We report the realization of a read-write device out of the ferromagnetic semiconductor (Ga,Mn)As as the first step to fundamentally new information processing paradigm. Writing the magnetic state is achieved by current-induced switching and read-out of the state is done by the means of the tunneling anisotropic magneto resistance (TAMR) effect. This one bit demonstrator device can be used to design a electrically programmable memory and logic device.
DNA sequencing is the physical/biochemical process of identifying the location of the four bases (Adenine, Guanine, Cytosine, Thymine) in a DNA strand. As semiconductor technology revolutionized computing, modern DNA sequencing technology (termed Nex t Generation Sequencing, NGS)revolutionized genomic research. As a result, modern NGS platforms can sequence hundreds of millions of short DNA fragments in parallel. The sequenced DNA fragments, representing the output of NGS platforms, are termed reads. Besides genomic variations, NGS imperfections induce noise in reads. Mapping each read to (the most similar portion of) a reference genome of the same species, i.e., read mapping, is a common critical first step in a diverse set of emerging bioinformatics applications. Mapping represents a search-heavy memory-intensive similarity matching problem, therefore, can greatly benefit from near-memory processing. Intuition suggests using fast associative search enabled by Ternary Content Addressable Memory (TCAM) by construction. However, the excessive energy consumption and lack of support for similarity matching (under NGS and genomic variation induced noise) renders direct application of TCAM infeasible, irrespective of volatility, where only non-volatile TCAM can accommodate the large memory footprint in an area-efficient way. This paper introduces GeNVoM, a scalable, energy-efficient and high-throughput solution. Instead of optimizing an algorithm developed for general-purpose computers or GPUs, GeNVoM rethinks the algorithm and non-volatile TCAM-based accelerator design together from the ground up. Thereby GeNVoM can improve the throughput by up to 113.5 times (3.6); the energy consumption, by up to 210.9 times (1.36), when compared to a GPU (accelerator) baseline, which represents one of the highest-throughput implementations known.
The Message Queue (MQ) architecture is an asynchronous communication scheme that provides an attractive solution for certain scenarios in a distributed computing model. The introduction of MQ as an intermediate component in-between the interacting pr ocesses allows to decouple the end-points making the system more flexible and providing high scalability and redundancy. DIRAC is a general-purpose interware software for distributed computing systems, which offers a common interface to a number of heterogeneous providers and guarantees transparent and reliable usage of the resources. The DIRAC platform has been adapted by several scientific projects, including High Energy Physics communities like LHCb, the Linear Collider and Belle2. A Message Queue generic interface has been incorporated into the DIRAC framework to help solving the scalability challenges that must be addressed during LHC Run3, starting in 2021. It allows to use the MQ scheme for a message exchange among the DIRAC components or to communicate with third-party services. Within this contribution we describe the integration of MQ systems with DIRAC and several use cases are shown. Message Queues are foreseen to be used in the pilot logging system, and as a backbone of the DIRAC component logging system and monitoring.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا