Engineering Commons^™

Needed Computations Shortcutting Needed Steps, Sergio Antoy, Jacob Johannsen, Steven Libby

Computer Science Faculty Publications and Presentations

We define a compilation scheme for a constructor-based, strongly-sequential, graph rewriting system which shortcuts some needed steps. The object code is another constructor-based graph rewriting system. This system is normalizing for the original system when using an innermost strategy. Consequently, the object code can be easily implemented by eager functions in a variety of programming languages. We modify this object code in a way that avoids total or partial construction of the contracta of some needed steps of a computation. When computing normal forms in this way, both memory consumption and execution time are reduced compared to ordinary rewriting computations …

S-Store: Streaming Meets Transaction Processing, John Meehan, Nesime Tatbul, Cansu Aslantas, Ugur Cetintemel, Jiang Du, Tim Kraska, Samuel Madden, David Maier, Andrew Pavlo, Michael Stonebraker, Kristin A. Tufte, Hao Wang

Computer Science Faculty Publications and Presentations

Stream processing addresses the needs of real-time applications. Transaction processing addresses the coordination and safety of short atomic computations. Heretofore, these two modes of operation existed in separate, stove-piped systems. In this work, we attempt to fuse the two computational paradigms in a single system called S-Store. In this way, S-Store can simultaneously accommodate OLTP and streaming applications. We present a simple transaction model for streams that integrates seamlessly with a traditional OLTP system. We chose to build S-Store as an extension of H-Store, an open-source, in-memory, distributed OLTP database system. By implementing S-Store in this way, we can make …

A Theory Of Name Resolution, Pierre Néron, Andrew Tolmach, Eelco Visser, Guido Wachsmuth

Computer Science Faculty Publications and Presentations

We describe a language-independent theory for name binding and resolution, suitable for programming languages with complex scoping rules including both lexical scoping and modules. We formulate name resolution as a two-stage problem. First a language-independent scope graph is constructed using language-specific rules from an abstract syntax tree. Then references in the scope graph are resolved to corresponding declarations using a language-independent resolution process. We introduce a resolution calculus as a concise, declarative, and language- independent specification of name resolution. We develop a resolution algorithm that is sound and complete with respect to the calculus. Based on the resolution calculus we …

Usage Based Topology For Dcns, Qing Yi, Suresh Singh

Computer Science Faculty Publications and Presentations

Many data center network topologies are designed to provide full bisection bandwidth for tens of thousands of servers in order to achieve high network throughput and server agility. However, the utilization rate of DCNs on average is below 10%, which results in a significant waste of network resources and energy. Many researchers propose consolidating network traffic flows to maximize the set of idle network equipment and switching them to low power mode to save energy. In this paper, we propose using skinnier network topologies to meet performance requirements of realistic loads thus saving not only energy but capital cost as …

Desiderata For A Big Data Language, David Maier

Computer Science Faculty Publications and Presentations

Data management and analytics systems for big data have proliferated, including column stores, array databases, graphanalysis environments and linear-algebra packages. This burgeoning of systems has lead to a surfeit of language and APIs. It is time to consider a new framework that can span these systems and simplify the programming and maintenance of Big Data applications. There are two key goals for such a framework:

Portability: It should be relatively easy to move an application or tool developed on one platform to operate against another. As a corollary, back-end data and analytics services should be swappable in a particular …

A Demonstration Of The Bigdawg Polystore System, Aaron J. Elmore, Jennie Duggan, Michael Stonebraker, Magdalena Balazinska, Ugur Cetintemel, Vijay Gadepally, J. Heer, Bill Howe, Jeremy Kepner, Tim Kraska, Samuel Madden, David Maier, Timothy G. Mattson, S. Papadopoulos, J. Parkhurst, Nesime Tatbul, Manasi Vartak, Stan Zdonik

Computer Science Faculty Publications and Presentations

This paper presents BigDAWG, a reference implementation of a new architecture for “Big Data” applications. Such applications not only call for large-scale analytics, but also for real-time streaming support, smaller analytics at interactive speeds, data visualization, and cross-storage-system queries. Guided by the principle that “one size does not fit all”, we build on top of a variety of storage engines, each designed for a specialized use case. To illustrate the promise of this approach, we demonstrate its effectiveness on a hospital application using data from an intensive care unit (ICU). This complex application serves the needs of doctors and researchers …

Query From Examples: An Iterative, Data-Driven Approach To Query Construction, Hao Li, Chee-Yong Chan, David Maier

Computer Science Faculty Publications and Presentations

In this paper, we propose a new approach, called Query from Examples (QFE), to help non-expert database users construct SQL queries. Our approach, which is designed for users who might be unfamiliar with SQL, only requires that the user is able to determine whether a given output table is the result of his or her intended query on a given input database. To kick-start the construction of a target query Q, the user first provides a pair of inputs: a sample database D and an output table R which is the result of Q on D. As there will be …

A Comparative Study Of Reservoir Computing For Temporal Signal Processing, Alireza Goudarzi, Peter Banda, Matthew R. Lakin, Christof Teuscher, Darko Stefanovic

Computer Science Faculty Publications and Presentations

Reservoir computing (RC) is a novel approach to time series prediction using recurrent neural networks. In RC, an input signal perturbs the intrinsic dynamics of a medium called a reservoir. A readout layer is then trained to reconstruct a target output from the reservoir's state. The multitude of RC architectures and evaluation metrics poses a challenge to both practitioners and theorists who study the task-solving performance and computational power of RC. In addition, in contrast to traditional computation models, the reservoir is a dynamical system in which computation and memory are inseparable, and therefore hard to analyze. Here, we compare …

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent …

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.

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

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.

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, …

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.

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 …

Is Parallel Programming Hard, And If So, Why?, Paul E. Mckenney, Maged M. Michael, Manish Gupta, Philip William Howard, Josh Triplett, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Of the 200+ parallel-programming languages and environments created in the 1990s, almost all are now defunct. Given that parallel systems are now well within the budget of the typical hobbyist or graduate student, it is not unreasonable to expect a new cohort in excess of several thousand parallel languages and environments to appear in the 2010s. If this expected new cohort is to have more practical impact than did its 1990s counterpart, a robust and widely applicable framework will be required that encompasses exactly what, if anything, is hard about parallel programming. This paper revisits the fundamental precepts of concurrent …

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 …

Directflow: A Domain-Specific Language For Information-Flow Systems, Andrew P. Black, Chuan-Kai Lin

Computer Science Faculty Publications and Presentations

Programs that process streams of information are commonly built by assembling reusable information-flow components. In some systems the components must be chosen from a pre-defined set of primitives; in others the programmer can create new custom components using a general-purpose programming language. Neither approach is ideal: restricting programmers to a set of primitive components limits the expressivity of the system, while allowing programmers to define new components in a general-purpose language makes it difficult or impossible to reason about the composite system. We advocate defining information-flow components in a domain-specific language (DSL) that enables us to infer the properties of …

Binary Decision Diagrams And Crisp Possibilistic Reconstructability Analysis, Martin Zwick, Alan Mishchenko

Systems Science Faculty Publications and Presentations

The paper discusses the application of Binary Decision Diagrams (BDDs) in the reconstructability analysis of crisp possibilistic systems. In particular, we show how BDDs can be used to represent set-theoretic relations and implement the three basic operations of reconstructability analysis.

Can Infopipes Facilitate Reuse In A Traffic Application?, Emerson Murphy-Hill, Chuan-Kai Lin, Andrew P. Black, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Infopipes are presented as reusable building blocks for streaming applications. To evaluate this claim, we have built a significant traffic application in Smalltalk using Infopipes. This poster presents a traffic problem and solution, a short introduction to Infopipes, and the types of reuse Infopipes facilitate in our implementation.

Using Dynamic Optimization For Control Of Real Rate Cpu Resource Management Applications, Varin Vahia, Ashvin Goel, David Steere, Jonathan Walpole, Molly H. Shor

Computer Science Faculty Publications and Presentations

In this paper we design a proportional-period optimal controller for allocating CPU to real rate multimedia applications on a general-purpose computer system. We model this computer system problem in to state space form. We design a controller based on dynamic optimization LQR tracking techniques to minimize short term and long term time deviation from the current time stamp and also CPU usage. Preliminary results on an experimental set up are encouraging.

Adaptive Live Video Streaming By Priority Drop, Jie Huang, Charles Krasic, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In this paper we explore the use of Priority-progress streaming (PPS) for video surveillance applications. PPS is an adaptive streaming technique for the delivery of continuous media over variable bit-rate channels. It is based on the simple idea of reordering media components within a time window into priority order before transmission. The main concern when using PPS for live video streaming is the time delay introduced by reordering. In this paper we describe how PPS can be extended to support live streaming and show that the delay inherent in the approach can be tuned to satisfy a wide range of …

Under The Plastic: A Quantitative Look At Dvd Video Encoding And Its Impact On Video Modeling, Wu-Chi Feng, Jin Choi, Wu-Chang Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

In this paper, we examine the DVD encoding process and the implications this process has video modeling and network traffic analysis. We have assembled a system that allows us to extract the video data from the DVDs as they were encoded for distribution. Analyzing the resulting video trace data, we describe how DVD encodings have evolved over time. In addition, our findings show that the underlying video content is fundamentally different than those produced by basic consumer video capture boards. We demonstrate how this affects current video modeling proposals and their affect on network traffic characterization. This research is based …

Provisioning On-Line Games: A Traffic Analysis Of A Busy Counter-Strike Server, Wu-Chang Feng, Francis Chang, Wu-Chi Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper describes the results of a 500 million packet trace of a popular on-line, multi-player, game server. The results show that the traffic behavior of this heavily loaded game server is highly predictable and can be attributed to the fact that current game designs target the saturation of the narrowest, last-mile link. Specifically, in order to maximize the interactivity of the game itself and to provide relatively uniform experiences between players playing over different network speeds, on-line games typically fix their usage requirements in such a way as to saturate the network link of their lowest speed players. While …

Supporting Low-Latency Tcp-Based Media Streams, Ashvin Goel, Charles Krasic, Kang Li, Jonathan Walpole

Computer Science Faculty Publications and Presentations

The dominance of the TCP protocol on the Internet and its success in maintaining Internet stability has led to several TCP-based stored media-streaming approaches. The success of these approaches raises the question whether TCP can be used for low-latency streaming. Low latency streaming allows responsive control operations for media streaming and can make interactive applications feasible. We examined adapting the TCP send buffer size based on TCP's congestion window to reduce application perceived network latency. Our results show that this simple idea significantly improves the number of packets that can be delivered within 200 ms and 500 ms thresholds.

Poster: Provisioning On-Line Games: A Traffic Analysis Of A Busy Counter-Strike Server, Francis Chang, Wu-Chang Feng, Wu-Chi Feng, Jonathan Walpole

Computer Science Faculty Publications and Presentations

A poster that illustrates the client/server model employed by an multiplayer online game, focusing on bandwidth usage.

Infopipes: An Abstraction For Multimedia Streaming, Andrew P. Black, Huang Jie, Rainer Koster, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

To simplify the task of building distributed streaming applications, we propose a new abstraction for information flow – Infopipes. Infopipes make information flow primary, not an auxiliary mechanism that is hidden away. Systems are built by connecting predefined component Infopipes such as sources, sinks, buffers, filters, broadcasting pipes, and multiplexing pipes. The goal of Infopipes is not to hide communication, like an RPC system, but to reify it: to represent communication explicitly as objects that the program can interrogate and manipulate. Moreover, these objects represent communication in application-level terms, not in terms of network or process implementation.

Thread Transparency In Information Flow Middleware, Rainer Koster, Andrew P. Black, Jie Huang, Jonathan Walpole, Calton Pu

Computer Science Faculty Publications and Presentations

Existing middleware is based on control-flow centric interaction models such as remote method invocations, poorly matching the structure of applications that process continuous information flows. Difficulties cultiesin building this kind of application on conventional platforms include flow-specific concurrency and timing requirements, necessitating explicit management of threads, synchronization, and timing by the application programmer. We propose Infopipes as a high-level abstraction for information flows, and we are developing a middleware framework that supports this abstraction. Infopipes transparently handle complexities associated with control flow and multi-threading. From high-level configuration descriptions the platform determines what parts of a pipeline require separate threads or …

Reifying Communication At The Application Level, Andrew P. Black, Jie Huang, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Middleware, from the earliest RPC systems to recent Object-Oriented Remote Message Sending (RMS) systems such as Java RMI and CORBA, claims transparency as one of its main attributes. Coulouris et al. define transparency as “the concealment from the … application programmer of the separation of components in a distributed system.” They go on to identify eight different kinds of transparency.

We considered titling this paper “Transparency Considered Harmful”, but that title is misleading because it implies that all kinds of transparency are bad. This is not our view. Rather, we believe that the choice of which transparencies should be offered …

Globally Convergent Approximate Dynamic Programming Applied To An Autolander, J.J. Murray, Richard Saeks, C.J. Cox, George G. Lendaris

Systems Science Faculty Publications and Presentations

A globally convergent nonlinear Approximate Dynamic Programming algorithm is described, and an implementation of the algorithm in the linear case is developed. The resultant linear Approximate Dynamic Programming algorithm is illustrated via the design of an autolander for the NASA X-43 research aircraft, without a priori knowledge of the X-43's flight dynamics.