Zobrazeno 1 - 10
of 253
pro vyhledávání: '"Blelloch, Guy E."'
Autor:
Anderson, Daniel, Blelloch, Guy E.
Dynamic trees are a well-studied and fundamental building block of dynamic graph algorithms dating back to the seminal work of Sleator and Tarjan [STOC'81, (1981), pp. 114-122]. The problem is to maintain a tree subject to online edge insertions and
Externí odkaz:
http://arxiv.org/abs/2306.08786
Autor:
Manohar, Magdalen Dobson, Shen, Zheqi, Blelloch, Guy E., Dhulipala, Laxman, Gu, Yan, Simhadri, Harsha Vardhan, Sun, Yihan
Approximate nearest-neighbor search (ANNS) algorithms are a key part of the modern deep learning stack due to enabling efficient similarity search over high-dimensional vector space representations (i.e., embeddings) of data. Among various ANNS algor
Externí odkaz:
http://arxiv.org/abs/2305.04359
Multiversioning is widely used in databases, transactional memory, and concurrent data structures. It can be used to support read-only transactions that appear atomic in the presence of concurrent update operations. Any system that maintains multiple
Externí odkaz:
http://arxiv.org/abs/2212.13557
Autor:
Kang, Hongbo, Zhao, Yiwei, Blelloch, Guy E., Dhulipala, Laxman, Gu, Yan, McGuffey, Charles, Gibbons, Phillip B.
The performance of today's in-memory indexes is bottlenecked by the memory latency/bandwidth wall. Processing-in-memory (PIM) is an emerging approach that potentially mitigates this bottleneck, by enabling low-latency memory access whose aggregate me
Externí odkaz:
http://arxiv.org/abs/2211.10516
Many modern programming languages are shifting toward a functional style for collection interfaces such as sets, maps, and sequences. Functional interfaces offer many advantages, including being safe for parallelism and providing simple and lightweig
Externí odkaz:
http://arxiv.org/abs/2204.06077
Safe memory reclamation (SMR) schemes are an essential tool for lock-free data structures and concurrent programming. However, manual SMR schemes are notoriously difficult to apply correctly, and automatic schemes, such as reference counting, have be
Externí odkaz:
http://arxiv.org/abs/2204.05985
This paper presents a new and practical approach to lock-free locks based on helping, which allows the user to write code using fine-grained locks, but run it in a lock-free manner. Although lock-free locks have been suggested in the past, they are w
Externí odkaz:
http://arxiv.org/abs/2201.00813
Autor:
Ben-David, Naama, Blelloch, Guy E.
We present a randomized approach for wait-free locks with strong bounds on time and fairness in a context in which any process can be arbitrarily delayed. Our approach supports a tryLock operation that is given a set of locks, and code to run when al
Externí odkaz:
http://arxiv.org/abs/2108.04520
Non-volatile random access memory (NVRAM) offers byte-addressable persistence at speeds comparable to DRAM. However, with caches remaining volatile, automatic cache evictions can reorder updates to memory, potentially leaving persistent memory in an
Externí odkaz:
http://arxiv.org/abs/2108.04202
Autor:
Ben-David, Naama, Blelloch, Guy E., Fatourou, Panagiota, Ruppert, Eric, Sun, Yihan, Wei, Yuanhao
We present a general technique for garbage collecting old versions for multiversion concurrency control that simultaneously achieves good time and space complexity. Our technique takes only $O(1)$ time on average to reclaim each version and maintains
Externí odkaz:
http://arxiv.org/abs/2108.02775