Software Engineering Commons^™

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 …

A Comparison Of Relativistic And Reader-Writer Locking Approaches To Shared Data Access, Philip William Howard, Josh Triplett, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper explores the relationship between reader-writer locking and relativistic programming approaches to managing accesses to shared data. It demonstrates that by placing certain restrictions on writers, relativistic programming allows more concurrency than reader-writer locking while still providing the same isolation guarantees. Relativistic programming also allows for a straightforward model for reasoning about the correctness of programs that allow concurrent read-write accesses.

Haskell For The Cloud, Andrew P. Black

Computer Science Faculty Publications and Presentations

We present Cloud Haskell, a domain specific language for developing programs for a distributed-memory computing environment. Implemented as a shallow embedding in Haskell, it provides a message-passing communication model, inspired by Erlang, without introducing incompatibility with Haskell's established sharedmemory concurrency. A key contribution is a method for serializing function closures for transmission across the network. Cloud Haskell has been implemented; we present example code and some preliminary performance measurements.

Better Refactoring Tools For A Better Refactoring Strategy, Andrew P. Black

Computer Science Faculty Publications and Presentations

Refactoring tools can improve the speed and accuracy with which we create and maintain software – but only if they are used. In practice, tools are not used as much as they could be; this seems to be because they do not align with the refactoring strategy preferred by the majority of programmers: floss refactoring. We propose five principles that characterize successful floss refactoring tools – principles that can help programmers to choose the most appropriate refactoring tools and also help toolsmiths to design more usable tools.

A Framework For Relationship Pattern Languages, Sudarshan Murthy, David Maier

Computer Science Faculty Publications and Presentations

A relationship pattern is an abstraction of a recurring need when establishing relationships among information elements in specific contexts. By developing or leveraging a relationship pattern, modelers can solve a class of problems once and describe many relationship types at once. We have developed a framework for specifying relationship patterns and pattern languages (sets of patterns) in both modeling-language-independent and modeling-language-specific ways. We describe this framework both informally and formally. We provide examples of some commonly observed relationship patterns and show how to use them in ER with the help of a relationship pattern language called Exemplar. We also provide …

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 …

Refactoring Tools: Fitness For Purpose, Emerson Murphy-Hill, Andrew P. Black

Computer Science Faculty Publications and Presentations

Refactoring tools can improve the speed and accuracy with which we create and maintain software -- but only if they are used. In practice, tools are not used as much as they could be: this seems to be because sometimes they do not align with the refactoring tactic preferred by the majority of programmers, a tactic we call floss refactoring. We propose five principles that characterize successful floss refactoring tools -- principles that can help programmers to choose the most appropriate refactoring tools and also help toolsmiths to design tools that fit the programmer's purpose.

Cache Coherence Protocol Verification Using Ωmega, Ki Yung Ahn

Computer Science Faculty Publications and Presentations

We verify some correctness properties of the DASH cache coherence protocol using Ωmega. Ωmega is a language with a rich type system featuring GADTs, type functions, and user-guided type checking rules. Cache coherence protocols have both safety properties and liveness properties. We show how to describe some of the safety properties of DASH cache coherence protocol in mega. Since liveness properties are not easily expressed by types, we investigate invariants sufficient to imply some of the liveness properties of concern, and assert those invariants as well in the type system of Ωmega. Using Ωmega, we can have both a working …

A Pattern Language For Extensible Program Representation, Andrew P. Black, Daniel Vainsencher

Computer Science Faculty Publications and Presentations

For the last 15 years, implementors of multiple view programming environments have sought a single code model that would form a suitable basis for all of the program analyses and tools that might be applied to the code. They have been unsuccessful. The consequences are a tendency to build monolithic, single-purpose tools, each of which implements its own specialized analyses and optimized representation. This restricts the availability of the analyses, and also limits the reusability of the representation by other tools. Unintegrated tools also produce inconsistent views, which reduce the value of multiple views. This article describes a set of …

India’S Rise As A Software Power: Governmental Policy Factors, Tad Drozdowski, Hai Huynh, Brian Lininger, Yicheng Peng, Naruedom Sakulyong

Engineering and Technology Management Student Projects

The Indian government’s policies toward an open, global market, support of educational institutions, and enhancement of appropriate infrastructure helped enable their software industry to become critical components of India’s economic growth in the 1990s. The Technical, Organizational, and Personal perspective (T, O, and P) model is utilized to examine different affects that each perspective, inclusive of government policies, has on a socio-technical system (Software development in India). The Indian government has provided substantial economic liberalization to support their software industries, though continued reform is necessary to ensure that they remain a software superpower.

Toward A Sound Integration Of Isabelle With A Combined Decision Procedure, Tom Harke

Computer Science Faculty Publications and Presentations

I present work on a project to integrate Isabelle, an extremely versatile interactive proof assistant, with a combined decision procedure, the Cooperating Validity Checker (CVC). Isabelle is sound and flexible, however it is often tedious to use. CVC is fully automatic, but only handles decision problems expressible over a relatively weak set of theories including linear arithmetic, uninterpreted functions, data types, and firstorder quantifier-free logic. My goal is to increase the amount of automation in Isabelle, by making it use CVC as an oracle for such problems, but without compromising Isabelle’s soundness.

In this paper I report on the progress …

A Software Architecture For Reconstructability Analysis, Kenneth Willett, Martin Zwick

Complex Systems Faculty Publications and Presentations

Software packages for reconstructability analysis (RA), as well as for related log linear modeling, generally provide a fixed set of functions. Such packages are suitable for end‐users applying RA in various domains, but do not provide a platform for research into the RA methods themselves. A new software system, Occam3, is being developed which is intended to address three goals which often conflict with one another to provide: a general and flexible infrastructure for experimentation with RA methods and algorithms; an easily‐configured system allowing methods to be combined in novel ways, without requiring deep software expertise; and a system which …

A Browser For Incremental Programming, Andrew P. Black

Computer Science Faculty Publications and Presentations

Much of the elegance and power of Smalltalk comes from its programming environment and tools. First introduced more than 20 years ago, the Smalltalk browser enables programmers to “home in” on particular methods using a hierarchy of manually-defined classifications. By its nature, this classification scheme says a lot about the desired state of the code, but little about the actual state of the code as it is being developed. We have extended the Smalltalk browser with dynamically computed virtual categories that dramatically improve the browser’s support for incremental programming. We illustrate these improvements by example, and describe the algorithms used …

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.

Gscope: A Visualization Tool For Time-Sensitive Software, Ashvin Goel, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper describes gscope, a visualization tool for time-sensitive applications. Gscope provides an oscilloscope-like interface that can be integrated with applications. It focuses on software visualization and is thus designed to handle various types of signal waveforms, periodic or event-driven, in single or multithreaded environments as well as local or distributed applications. Gscope helps in visually verifying system correctness and modifying system parameters and thus can complement standard debugging techniques and be used to build compelling software demos. Initial experiments with using gscope show that the library has low overhead.

Control Challenges In Multi-Level Adaptive Video Streaming, Dylan Mcnamee, Charles Krasic, Kang Li, Ashvin Goel, Erik Walthinsen, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Streaming video is one of the fastest-growing applications of the Internet. The Internet’s diversity and dynamism demands that video streams adapt to ensure maximum quality at all times. This paper describes the control challenges we have encountered in the Quasar project’s “multi-level” adaptive streaming video player. We first describe the framework and environment of the player. This framework uses software feedback to control resource allocation as well as the quality of media delivery. We present the control challenges raised by our framework, which include horizontal and vertical feedback composition, difficult to model systems, and unpredictable, non-linear actuators. We describe some …

Adaptive Prefetching For Device-Independent File I/O, Dan Revel, Dylan Mcnamee, David Steere, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Device independent I/O has been a holy grail to operating system designers since the early days of UNIX. Unfortunately, existing operating systems fall short of this goal for multimedia applications. Techniques such as caching and sequential read-ahead can help mask I/O latency in some cases, but in others they increase latency and add substantial jitter. Multimedia applications, such as video players, are sensitive to vagaries in performance since I/O latency and jitter affect the quality of presentation. Our solution uses adaptive prefetching to reduce both latency and jitter. Applications submit file access plans to the prefetcher, which then generates I/O …

A Cognitively Motivated System For Software Component Reuse, Michael Joseph Mateas

Dissertations and Theses

Software reuse via component libraries suffers from the twin problems of code location and comprehension. The Intelligent Code Object Planner (ICOP) is a cognitively motivated system that facilitates code reuse by answering queries about how to produce an effect with the library. It can plan for effects which are not primitive with respect to the library by building a plan that incorporates multiple components. The primary subsystems of ICOP are a knowledge base which describes the ontology of the library, a natural language interface which translates user queries into a formal effect language (predicates), a planner which accepts the effect …

Benchmarking Parallel Machines Via A Software Architecture, Srikanth Kambhatla, Jon Inouye, Jonathan Walpole

Computer Science Faculty Publications and Presentations

The diversity in parallel architectures and the programming styles induced thereof, make benchmarking of parallel machines a hard problem. Current benchmarking techniques are limited in applicability due to the issues of portability. We present a different approach to benchmarking parallel machines, which would make the resulting benchmarks portable, easy to use and widely applicable. The approach involves the use of a software architecture to mask the diversities of the underlying architectures. The benchmarks are based on the Linda Tuple Space, and is called BeLinda. In this report, we motivate the use of a software architecture, give a specification of the …

Moment-Curvature-Thrust Relationships In Hybrid Members, Douglas Wrenn Fiala

Dissertations and Theses

In order to overcome the difficulties encountered in closed form solutions, moment-curvature-thrust relationships are developed for hybrid and nonhybrid cross sections utilizing an open form method. The use of horizontal sectors permits the inclusion of residual stresses and/or nonbilinear stress-strain relationships, if desired. Theoretical and experimental data are compared. Applications to circular tubes and other cross sections are discussed. Results indicate that open form solutions are feasible for calculating moment-curvature-thrust data. Hybrid cross sections are easily treated by open form solutions.