Computer Engineering Commons^™

Calibration Of Complex System Dynamics Models: A Practioner's Report, Rod Walker, Wayne Wakeland

Complex Systems Faculty Publications and Presentations

This paper is not a typical academic paper that is solidly grounded in the literature. Instead, this paper reports practitioner’s experiences in rebuilding and calibrating a very large system dynamics model. A prior version of this model had been in use for over 10 years in an ongoing executive training simulation. That model had never worked correctly in several key areas, requiring the outputs to be manually adjusted by very experienced facilitators during the course of the simulation. The present project rebuilt the system dynamics model, redesigned the parts that weren’t working, and calibrated the resulting model to match the …

Evolving Machine Morality Strategies Through Multiagent Simulations, David Burke

Systems Science Friday Noon Seminar Series

There is a general consensus among robotics researchers that the world of the future will be filled with autonomous and semi-autonomous machines. There is less of a consensus, though, on the best approach to instilling a sense of 'machine morality' in these systems so that they will be able to have effective interactions with humans in an increasingly complex world. In my talk, we take a brief look at some existing approaches to computational ethics, and then describe work we've undertaken creating multiagent simulations involving moral decision-making during strategic interactions. In these simulations, agents make choices about whether to cooperate …

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.

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 …

Efficient Support Of Consistent Cyclic Search With Read-Copy-Update And Parallel Updates, Jonathan Walpole, Paul E. Mckenney

Computer Science Faculty Publications and Presentations

A method, system and computer program product for supporting concurrent updates to a shared data element group while preserving group integrity on behalf of one or more readers that are concurrently referencing group data elements without using locks or atomic instructions. Two or more updaters may be invoked to generate new group data elements. Each new data element created by the same up dater is assigned a new generation number that is different than a global generation number associated with the data element group and which allows a reader of the data element group to determine whether the new data …

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 …

Biological Computation, Melanie Mitchell

Computer Science Faculty Publications and Presentations

In this article, the term biological computation refers to the proposal that living organisms themselves perform computations, and, more specifically, that the abstract ideas of information and computation may be key to understanding biology in a more unified manner. It is important to point out that the study of biological computation is typically not the focus of the field of computational biology, which applies computing tools to the solution of specific biological problems. Likewise, biological computation is distinct from the field of biologically-inspired computing, which borrows ideas from biological systems such as the brain, insect colonies, and the immune system …

Comparing Discrete Simulation And System Dynamics: Modeling An Anti-Insurgency Influence Operation, Wayne Wakeland, Una E. Medina

Complex Systems Faculty Publications and Presentations

This paper contrasts the tradeoffs of modeling the same dynamic problem at a micro scale and at a macro scale of analysis: discrete system simulation (DS) versus continuous system simulation or system dynamics (SD). Both are employed to model the influence of entertainment education on terrorist system decay, with implications for field application. Each method optimizes different design, scope/scale, data availability/accuracy, parameter settings, and system sensitivities. Whether the research served by the computer model is applied or theoretical, DS tends to be useful for understand low-level individual unit/step influences on system change over time, whereas SD tends to shine when …

System Dynamics Implementation Of An Extended Brander And Taylor-Like Easter Island Model, Takuro Uehara, Yoko Nagase, Wayne Wakeland

Complex Systems Faculty Publications and Presentations

We provide a system dynamics implementation of a dynamic ecological economics model. Dynamic economic models are often constrained to use functions, such as the Cobb-Douglas function, chosen “conveniently” to allow for analytic solutions. The C-D function, however, suffers from its fixed elasticity that does not allow for the substitutability between man-made capital and natural capital to change, which is vital for economic sustainability. Using system dynamics removes this constraint and enables more realistic ecological economics models containing functions not amenable to analytic solution. The base model is the natural resource and population growth model developed by Brander and Taylor (1998) …

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 …

Programmer Friendly Refactoring Tools, Emerson Murphy-Hill

Dissertations and Theses

Tools that perform semi-automated refactoring are currently under-utilized by programmers. If more programmers adopted refactoring tools, software projects could make enormous productivity gains. However, as more advanced refactoring tools are designed, a great chasm widens between how the tools must be used and how programmers want to use them. This dissertation begins to bridge this chasm by exposing usability guidelines to direct the design of the next generation of programmer-friendly refactoring tools, so that refactoring tools fit the way programmers behave, not vice-versa.

Computational Techniques For Reducing Spectra Of The Giant Planets In Our Solar System, Holly L. Grimes

Dissertations and Theses

The dynamic atmospheres of Jupiter, Saturn, Uranus, and Neptune provide a rich source of meteorological phenomena for scientists to study. To investigate these planets, scientists obtain spectral images of these bodies using various instruments including the Cooled Mid-Infrared Camera and Spectrometer (COMICS) at the Subaru Telescope Facility at Mauna Kea, Hawaii. These spectral images are two-dimensional arrays of double precision floating point values that have been read from a detector array. Such images must be reduced before the information they contain can be analyzed. The reduction process for spectral images from COMICS involves several steps:

1. Sky subtraction: the …

Dynamic Task Prediction For An Spmt Architecture Based On Control Independence, Komal Jothi

Dissertations and Theses

Exploiting better performance from computer programs translates to finding more instructions to execute in parallel. Since most general purpose programs are written in an imperatively sequential manner, closely lying instructions are always data dependent, making the designer look far ahead into the program for parallelism. This necessitates wider superscalar processors with larger instruction windows. But superscalars suffer from three key limitations, their inability to scale, sequential fetch bottleneck and high branch misprediction penalty. Recent studies indicate that current superscalars have reached the end of the road and designers will have to look for newer ideas to build computer processors.

Speculative …

Graphical User Interfaces As Updatable Views, James Felger Terwilliger

Dissertations and Theses

In contrast to a traditional setting where users express queries against the database schema, we assert that the semantics of data can often be understood by viewing the data in the context of the user interface (UI) of the software tool used to enter the data. That is, we believe that users will understand the data in a database by seeing the labels, dropdown menus, tool tips, help text, control contents, and juxtaposition or arrangement of controls that are built in to the user interface. Our goal is to allow domain experts with little technical skill to understand and query …

Irrelevance, Polymorphism, And Erasure In Type Theory, Richard Nathan Mishra-Linger

Dissertations and Theses

Dependent type theory is a proven technology for verified functional programming in which programs and their correctness proofs may be developed using the same rules in a single formal system. In practice, large portions of programs developed in this way have no computational relevance to the ultimate result of the program and should therefore be removed prior to program execution. In previous work on identifying and removing irrelevant portions of programs, computational irrelevance is usually treated as an intrinsic property of program expressions. We find that such an approach forces programmers to maintain two copies of commonly used datatypes: a …

Window Queries Over Data Streams, Jin Li

Dissertations and Theses

Evaluating queries over data streams has become an appealing way to support various stream-processing applications. Window queries are commonly used in many stream applications. In a window query, certain query operators, especially blocking operators and stateful operators, appear in their windowed versions. Previous research work in evaluating window queries typically requires ordered streams and this order requirement limits the implementations of window operators and also carries performance penalties. This thesis presents efficient and flexible algorithms for evaluating window queries. We first present a new data model for streams, progressing streams, that separates stream progress from physical-arrival order. Then, we …

Semantic Components: A Model For Enhancing Retrieval Of Domain- Specific Information, Susan Loucette Price

Dissertations and Theses

Despite the success of general Internet search engines, information retrieval remains an incompletely solved problem. Our research focuses on supporting domain experts when they search domain-specific libraries to satisfy targeted information needs. The semantic components model introduces a schema specific to a particular document collection. A semantic component schema consists of a two-level hierarchy, document classes and semantic components. A document class represents a document grouping, such as topic type or document purpose. A semantic component is a characteristic type of information that occurs in a particular document class and represents an important aspect of the document’s main topic. …

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 …

An Emotional Mimicking Humanoid Biped Robot And Its Quantum Control Based On The Constraint Satisfaction Model, Quay Williams, Scott Bogner, Michael Kelley, Carolina Castillo, Martin Lukac, Dong Hwa Kim, Jeff S. Allen, Mathias I. Sunardi, Sazzad Hossain, Marek Perkowski

Electrical and Computer Engineering Faculty Publications and Presentations

The paper presents a humanoid robot that responds to human gestures seen by a camera. The behavior of the robot can be completely deterministic as specified by a Finite State Machine that maps the sensor signals to the effector signals. This model is further extended to the constraints-satisfaction based model that links robots vision, motion, emotional behavior and planning. One way of implementing this model is to use adiabatic quantum computer which quadratically speeds-up every constraint problem and will be thus necessary to solve large problems of this type. We propose to use the remotely-connected Orion system by DWAVE Corporation.

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 …

A Hybrid Simulation Model For Studying Acute Inflammatory Response, Wayne W. Wakeland, Louis Macovsky, Gary An

Complex Systems Faculty Publications and Presentations

The modeling of complex biological systems presents a significant challenge. Central to this challenge is striking a balance between the degree of abstraction required to facilitate analysis and understanding, and the degree of comprehensiveness required for fidelity of the model to its reference-system. It is likely necessary to utilize multiple modeling methods in order to achieve this balance. Our research created a hybrid simulation model by melding an agent-based model of acute local infection with a system dynamics model that reflects key systemic properties. The agent based model was originally developed to simulate global inflammation in response to injury or …

Gridfields: Model-Driven Data Transformation In The Physical Sciences, Bill Howe

Dissertations and Theses

Scientists' ability to generate and store simulation results is outpacing their ability to analyze them via ad hoc programs. We observe that these programs exhibit an algebraic structure that can be used to facilitate reasoning and improve performance. In this dissertation, we present a formal data model that exposes this algebraic structure, then implement the model, evaluate it, and use it to express, optimize, and reason about data transformations in a variety of scientific domains.

Simulation results are defined over a logical grid structure that allows a continuous domain to be represented discretely in the computer. Existing approaches for manipulating …

Efficient Support For Application-Specific Video Adaptation, Jie Huang

Dissertations and Theses

As video applications become more diverse, video must be adapted in different ways to meet the requirements of different applications when there are insufficient resources. In this dissertation, we address two sorts of requirements that cannot be addressed by existing video adaptation technologies: (i) accommodating large variations in resolution and (ii) collecting video effectively in a multi-hop sensor network. In addition, we also address requirements for implementing video adaptation in a sensor network.

Accommodating large variation in resolution is required by the existence of display devices with widely disparate screen sizes. Existing resolution adaptation technologies usually aim at adapting video …

An Agent-Based Model Of Trade With Distance-Based Transaction Cost, Kumar Venkat, Wayne W. Wakeland

Complex Systems Faculty Publications and Presentations

This paper describes an application of agent-based modeling to investigate the effect of a distance-based transaction cost on trade. Long-distance trade is rapidly increasing, but may ultimately be constrained by our ability to move material goods between sellers and buyers. Unlike information exchange, trade in material goods is dependent on the price of oil and vulnerable to future scarcities of oil. In addition, there are growing concerns about greenhouse gas emissions from long-distance transportation. Our purpose in this study is to take the first step in understanding the impact of a distance constraint on free global trade using a simple …

Analysis Of Relay-Based Cellular Systems, Ansuya Negi

Dissertations and Theses

Relays can be used in cellular systems to increase coverage as well as reduce the total power consumed by mobiles in a cell. This latter benefit is particularly useful for mobiles operating on a depleted battery. The relay can be a mobile, a car or any other device with the appropriate communication capabilities. In thesis we analyze the impact of using relays under different situations. We first consider the problem of reducing total power consumed in the system by employing relays intelligently. We find that in a simulated, fully random, mobile cellular network for CDMA (Code Division Multiple Access), significant …

Addressing Cheating And Workload Characterization In Online Games, Christopher Chambers

Dissertations and Theses

The Internet has enabled the popular pastime of playing video games to grow rapidly by connecting game players in disparate locations. However, with popularity have come the two challenges of hosting a large number of users and detecting cheating among users. For reasons of control, security, and ease of development, the most popular system for hosting on-line games is the client server architecture. This is also the most expensive and least scalable architecture for the game publisher, which drives hosting costs upwards with the success of the game. In addition to the expense of hosting, as a particular game grows …