Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 17 of 17
Full-Text Articles in Entire DC Network
Resizable, Scalable, Concurrent Hash Tables Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Jonathan Walpole
Resizable, Scalable, Concurrent Hash Tables Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Presentation focusing on software synchronization, thread locking, transactional memory, and relativistic programming. Hash table algorithms are presented with examples of relativistic list insertion and removal, and related data structures. Existing approaches are compared to new methodologies and future work with relativistic data structures.
Generalized Construction Of Scalable Concurrent Data Structures Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Philip W. Howard, Jonathan Walpole
Generalized Construction Of Scalable Concurrent Data Structures Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Philip W. Howard, Jonathan Walpole
Computer Science Faculty Publications and Presentations
We present relativistic programming, a concurrent programming model based on shared addressing, which supports efficient, scalable operation on either uniform shared-memory or distributed shared- memory systems. Relativistic programming provides a strong causal ordering property, allowing a series of read operations to appear as an atomic transaction that occurs entirely between two ordered write operations. This preserves the simple immutable-memory programming model available via mutual exclusion or transactional memory. Furthermore, relativistic programming provides joint-access parallelism, allowing readers to run concurrently with a writer on the same data. We demonstrate a generalized construction technique for concurrent data structures based on relativistic programming, …
The Ordering Requirements Of Relativistic And Reader-Writer Locking Approaches To Shared Data Access, Philip William Howard, Josh Triplett, Jonathan Walpole, Paul E. Mckenney
The Ordering Requirements Of Relativistic And Reader-Writer Locking Approaches To Shared Data Access, Philip William Howard, Josh Triplett, Jonathan Walpole, Paul E. Mckenney
Computer Science Faculty Publications and Presentations
The semantics of reader-writer locks allow read-side concurrency. Unfortunately, the locking primitives serialize access to the lock variable to an extent that little or no concurrency is realized in practice for small critical sections. Relativistic programming is a methodology that also allows read- side concurrency. Relativistic programming uses dfferent ordering constraints than reader-writer locking. The different ordering constraints allow relativistic readers to proceed without synchronization so relativistic readers scale even for very short critical sections. In this paper we explore the diferences between the ordering constraints for reader-writer locking and relativistic programs. We show how and why the dfferent ordering …
Xpu: A Distributed Architecture For Metaverses, Francis Chang, C. Mic Bowman, Wu-Chi Feng
Xpu: A Distributed Architecture For Metaverses, Francis Chang, C. Mic Bowman, Wu-Chi Feng
Computer Science Faculty Publications and Presentations
A significant problem of designing 3D virtual worlds (such as metaverses) is developing a scalable architecture that can manage millions of simultaneous users in an interactive 3D environment. This paper presents XPU (Extremely Partitioned Universe), a hierarchical client-server architecture for developing highly scalable metaverses. This design addresses the problem of dynamically partitioning the world to manage network and computing resources.
Pvw: Designing Virtual World Server Infrastructure, Francis Chang, C. Mic Bowman, Wu-Chi Feng
Pvw: Designing Virtual World Server Infrastructure, Francis Chang, C. Mic Bowman, Wu-Chi Feng
Computer Science Faculty Publications and Presentations
This paper presents a high level overview of PVW (Partitioned Virtual Worlds), a distributed system architecture for the management of virtual worlds. PVW is designed to support arbitrarily large and complex virtual worlds while accommodating dynamic and highly variable user population and content distribution density. The PVW approach enables the task of simulating and managing the virtual world to be distributed over many servers by spatially partitioning the environment into a hierarchical structure. This structure is useful both for balancing the simulation load across many nodes, as well as features such as geometric simplification and distribution of dynamic content.
Scalable Concurrent Hash Tables Via Relativistic Programming, Josh Triplett
Scalable Concurrent Hash Tables Via Relativistic Programming, Josh Triplett
Computer Science Faculty Publications and Presentations
Existing approaches to concurrent programming often fail to account for synchronization costs on modern shared-memory multipro- cessor architectures. A new approach to concurrent programming, known as relativistic programming, can reduce or in some cases eliminate synchronization overhead on such architectures. This approach avoids the costs of inter-processor communication and memory access by permitting processors to operate from a relativistic view of memory provided by their own caches, rather than from an absolute reference frame of memory as seen by all processors. This research shows how relativistic programming techniques can provide the perceived advantages of optimistic synchronization without the useless parallelism …
What Is Rcu, Fundamentally?, Paul E. Mckenney, Jonathan Walpole
What Is Rcu, Fundamentally?, Paul E. Mckenney, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Read-copy update (RCU) is a synchronization mechanism that was added to the Linux kernel in October of 2002. RCU achieves scalability improvements by allowing reads to occur concurrently with updates. In contrast with conventional locking primitives that ensure mutual exclusion among concurrent threads regardless of whether they be readers or updaters, or with reader-writer locks that allow concurrent reads but not in the presence of updates, RCU supports concurrency between a single updater and multiple readers. RCU ensures that reads are coherent by maintaining multiple versions of objects and ensuring that they are not freed up until all pre-existing read-side …
Rcu Semantics: A First Attempt, Paul E. Mckenney, Jonathan Walpole
Rcu Semantics: A First Attempt, Paul E. Mckenney, Jonathan Walpole
Computer Science Faculty Publications and Presentations
There is not yet a formal statement of RCU (read-copy update) semantics. While this lack has thus far not been an impediment to adoption and use of RCU, it is quite possible that formal semantics would point the way towards tools that automatically validate uses of RCU or that permit RCU algorithms to be automatically generated by a parallel compiler. This paper is a first attempt to supply a formal definition of RCU. Or at least a semi-formal definition: although RCU does not yet wear a tux (though it does run in Linux), at least it might yet wear some …
Implementing Infopipes: The Sip/Xip Experiment, Calton Pu, Galen Swint, Charles Consel, Younggyun Koh, Ling Liu, Koichi Moriyama, Jonathan Walpole, Wenchang Yan
Implementing Infopipes: The Sip/Xip Experiment, Calton Pu, Galen Swint, Charles Consel, Younggyun Koh, Ling Liu, Koichi Moriyama, Jonathan Walpole, Wenchang Yan
Computer Science Faculty Publications and Presentations
We describe an implementation of the Infopipe abstraction for information flow applications. We have implemented software tools that translate the SIP/XIP variant of Infopipe specification into executable code. These tools are evaluated through the rewriting of two realistic applications using Infopipes: a multimedia streaming program and a web source combination application. Measurements show that Infopipe-generated code has the same execution overhead as the manually written original version. Source code of Infopipe version is reduced by 36% to 85% compared to the original.
Infofilter: Supporting Quality Of Service For Fresh Information Delivery, Ling Liu, Calton Pu, Karsten Schwan, Jonathan Walpole
Infofilter: Supporting Quality Of Service For Fresh Information Delivery, Ling Liu, Calton Pu, Karsten Schwan, Jonathan Walpole
Computer Science Faculty Publications and Presentations
With the explosive growth of the Internet and World Wide Web comes a dramatic increase in the number of users that compete for the shared resources of distributed system environments. Most implementations of application servers and distributed search software do not distinguish among requests to different web pages. This has the implication that the behavior of application servers is quite unpredictable. Applications that require timely delivery of fresh information consequently suffer the most in such competitive environments. This paper presents a model of quality of service (QoS) and the design of a QoS-enabled information delivery system that implements such a …
Quality Of Service Semantics For Multimedia Database Systems, Jonathan Walpole, Charles Krasic, Ling Liu, David Maier, Calton Pu, Dylan Mcnamee, David Steere
Quality Of Service Semantics For Multimedia Database Systems, Jonathan Walpole, Charles Krasic, Ling Liu, David Maier, Calton Pu, Dylan Mcnamee, David Steere
Computer Science Faculty Publications and Presentations
Quality of service (QoS) support has been a hot research topic in multimedia databases, and multimedia systems in general, for the past several years. However, there remains little consensus on how QoS support should be provided. At the resource-management level, systems designers are still debating the suitability of reservation- based versus adaptive QoS management. The design of higher system layers is less clearly understood, and the specification of QoS requirements in domain-specific terms is still an open research topic. To address these issues, we propose a QoS model for multimedia databases. The model covers the specification of user-level QoS preferences …
Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole
Dynamic Load Distribution In Mist, K. Al-Saqabi, R. M. Prouty, Dylan Mcnamee, Steve Otto, Jonathan Walpole
Computer Science Faculty Publications and Presentations
This paper presents an algorithm for scheduling parallel applications in large-scale, multiuser, heterogeneous distributed systems. The approach is primarily targeted at systems that harvest idle cycles in general-purpose workstation networks, but is also applicable to clustered computer systems and massively parallel processors. The algorithm handles unequal processor capacities, multiple architecture types and dynamic variations in the number of processes and available processors. Scheduling decisions are driven by the desire to minimize turnaround time while maintaining fairness among competing applications. For efficiency, the virtual processors (VPs) of each application are gang scheduled on some subset of the available physical processors.
Predictable File Access Latency For Multimedia, Dan Revel, Crispin Cowan, Dylan Mcnamee, Calton Pu, Jonathan Walpole
Predictable File Access Latency For Multimedia, Dan Revel, Crispin Cowan, Dylan Mcnamee, Calton Pu, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Multimedia applications are sensitive to I/O latency and jitter when accessing data in secondary storage. Transparent adaptive prefetching (TAP) uses software feedback to provide multimedia applications with file system quality of service (QoS) guarantees. We are investigating how QoS requirements can be communicated and how they can be met by adaptive resource management. A preliminary test of adaptive prefetching is presented.
Device And Physical Data Independence For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier
Device And Physical Data Independence For Multimedia Presentations, Richard Staehli, Jonathan Walpole, David Maier
Computer Science Faculty Publications and Presentations
Multimedia computing promises access to any type of visual or aural medium on the desktop. But in this networked future, will every type of media be accessible from every terminal device? Current multimedia standards do not allow content that is authored for high-bandwidth workstations to scale down for low-bandwidth applications. The problem is that application requests are commonly interpreted as requests for the highest possible quality and resource overloads are handled by ad hoc methods. We can begin to solve this problem by specifying Quality of Service (QOS) requirements based on functionality rather than on content encoding and device capabilities.
Scheduling Of Parallel Jobs On Dynamic, Heterogenous Networks, Dan Clark, Jeremy Casas, Steve Otto, Robert Prouty, Jonathan Walpole
Scheduling Of Parallel Jobs On Dynamic, Heterogenous Networks, Dan Clark, Jeremy Casas, Steve Otto, Robert Prouty, Jonathan Walpole
Computer Science Faculty Publications and Presentations
In using a shared network of workstations for parallel processing, it is not only important to consider heterogeneity and differences in processing power between the workstations but also the dynamics of the system as a whole. In such a computing environment where the use of resources vary as other applications consume and release resources, intelligent scheduling of the parallel jobs onto the available resources is essential to maximize resource utilization. Despite this realization, however, there are few systems available that provide an infrastructure for the easy development and testing of these intelligent schedulers. In this paper, an infrastructure is presented …
A User-Level Process Package For Concurrent Computing, Ravi Konuru, Steve Otto, Jonathan Walpole, Robert Prouty, Jeremy Casas
A User-Level Process Package For Concurrent Computing, Ravi Konuru, Steve Otto, Jonathan Walpole, Robert Prouty, Jeremy Casas
Computer Science Faculty Publications and Presentations
A lightweight user-level process(ULP) package for parallel computing is described. Each ULP has its own register context, stack, data and heap space and communication with other ULPs is performed using locally synchronous, location transparent, message passing primitives. The aim of the package is to provide support for lightweight over-decomposition, optimized local communication and transparent dynamic migration. The package supports a subset of the Parallel Virtual Machine(PVM) interface[Sun90).
Script-Based Qos Specifications For Multimedia Presentations, Richard Staehli, Jonathan Walpole
Script-Based Qos Specifications For Multimedia Presentations, Richard Staehli, Jonathan Walpole
Computer Science Faculty Publications and Presentations
Multimedia presentations can convey information not only by the sequence of events but by their timing. The correctness of such presentations thus depends on the timing of events as well as their sequence and content. This paper introduces a formal specification language for playback of real-time presentations. The main contribution of this language is a quality of service (QOS) specification that relaxes resolution and synchronization requirements for playback. Our definitions give a precise meaning to the correctness of a presentation. This specification language will form the basis for a QOS interface for reservation of operating system resources.