Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 4 of 4
Full-Text Articles in Computer Engineering
A Relativistic Enhancement To Software Transactional Memory, Philip William Howard, Jonathan Walpole
A Relativistic Enhancement To Software Transactional Memory, Philip William Howard, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Relativistic Programming is a technique that allows low overhead, linearly-scalable concurrent reads. It also allows joint access parallelism between readers and a writer. Unfortunately, it has so far been limited to a single writer so it does not scale on the write side. Software Transactional Memory (STM) is a technique that allows programs to take advantage of disjoint access parallelism on both the read-side and write-side. Unfortunately, STM systems have a higher overhead than many other synchronization mechanisms so although STM scales, STM starts from a lower baseline. We propose combining relativistic programming and software transactional memory in a way …
Scalable Correct Memory Ordering Via Relativistic Programming, Josh Triplett, Philip William Howard, Paul E. Mckenney, Jonathan Walpole
Scalable Correct Memory Ordering Via Relativistic Programming, Josh Triplett, Philip William Howard, Paul E. Mckenney, Jonathan Walpole
Computer Science Faculty Publications and Presentations
We propose and document a new concurrent programming model, relativistic programming. This model allows readers to run concurrently with writers, without blocking or using expensive synchronization. Relativistic programming builds on existing synchronization primitives that allow writers to wait for current readers to finish with minimal reader overhead. Our methodology models data structures as graphs, and reader algorithms as traversals of these graphs; from this foundation we show how writers can implement arbitrarily strong ordering guarantees for the visibility of their writes, up to and including total ordering.
Relativistic Red-Black Trees, Philip William Howard, Jonathan Walpole
Relativistic Red-Black Trees, Philip William Howard, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Operating system performance and scalability on sharedmemory many-core systems depends critically on efficient access to shared data structures. Scalability has proven difficult to achieve for many data structures. In this paper we present a novel and highly scalable concurrent red-black tree. Red-black trees are widely used in operating systems, but typically exhibit poor scalability. Our red-black tree has linear read scalability, uncontended read performance that is at least 25% faster than other known approaches, and deterministic lookup times for a given tree size, making it suitable for realtime applications.
Adaptation Space: Surviving Non-Maskable Failures, Crispin Cowan, Lois Delcambre, Anne-Francoise Le Meur, Ling Liu, David Maier, Dylan Mcnamee, Michael Miller, Calton Pu, Perry Wagle, Jonathan Walpole
Adaptation Space: Surviving Non-Maskable Failures, Crispin Cowan, Lois Delcambre, Anne-Francoise Le Meur, Ling Liu, David Maier, Dylan Mcnamee, Michael Miller, Calton Pu, Perry Wagle, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Some failures cannot be masked by redundancies, because an unanticipated situation occurred, because fault-tolerance measures were not adequate, or because there was a security breach (which is not amenable to replication). Applications that wish to continue to offer some service despite nonmaskable failure must adapt to the loss of resources. When numerous combinations of non-maskable failure modes are considered, the set of possible adaptations becomes complex. This paper presents adaptation spaces, a formalism for navigating among combinations of adaptations. An adaptation space describes a collection of possible adaptations of a software component or system, and provides a uniform way of …