Computer Engineering Commons^™

Incorporating Priors For Medical Image Segmentation Using A Genetic Algorithm, Payel Ghosh, Melanie Mitchell, James A. Tanyi, Arthur Y. Hung

Computer Science Faculty Publications and Presentations

Medical image segmentation is typically performed manually by a physician to delineate gross tumor volumes for treatment planning and diagnosis. Manual segmentation is performed by medical experts using prior knowledge of organ shapes and locations but is prone to reader subjectivity and inconsistency. Automating the process is challenging due to poor tissue contrast and ill-defined organ/tissue boundaries in medical images. This paper presents a genetic algorithm for combining representations of learned information such as known shapes, regional properties and relative position of objects into a single framework to perform automated three-dimensional segmentation. The algorithm has been tested for prostate segmentation …

From Boolean Equalities To Constraints, Sergio Antoy, Michael Hanus

Computer Science Faculty Publications and Presentations

Although functional as well as logic languages use equality to discriminate between logically different cases, the operational meaning of equality is different in such languages. Functional languages reduce equational expressions to their Boolean values, True or False, logic languages use unification to check the validity only and fail otherwise. Consequently, the language Curry, which amalgamates functional and logic programming features, offers two kinds of equational expressions so that the programmer has to distinguish between these uses. We show that this distinction can be avoided by providing an analysis and transformation method that automatically selects the appropriate operation. Without this distinction …

A Scaffolded, Metamorphic Ctf For Reverse Engineering, Wu-Chang Feng

Computer Science Faculty Publications and Presentations

Hands-on Capture-the-Flag (CTF) challenges tap into and cultivate the intrinsic motivation within people to solve puzzles, much in the same way Sudoku and crossword puzzles do. While the format has been successful in security competitions, there have been a limited number of attempts to integrate them into a classroom environment. This paper describes MetaCTF, a metamorphic set of CTF challenges for teaching reverse code engineering. MetaCTF is 1) scaffolded in a way that allows students to make incremental progress, 2) integrated with the course material so that students can immediately apply knowledge gained in class, 3) polymorphic and metamorphic so …

Compiling Collapsing Rules In Certain Constructor Systems, Sergio Antoy, Andy Jost

Computer Science Faculty Publications and Presentations

The implementation of functional logic languages by means of graph rewriting requires a special handling of collapsing rules. Recent advances about the notion of a needed step in some constructor systems offer a new approach to this problem. We present two results: a transformation of a certain class of constructor-based rewrite systems that eliminates collapsing rules, and a rewrite-like relation that takes advantage of the absence of collapsing rules. We formally state and prove the correctness of these results. When used together, these results simplify without any loss of efficiency an implementation of graph rewriting and consequently of functional logic …

Automatic Fault Injection For Driver Robustness Testing, Kai Cong, Li Lei, Zhenkun Yang, Fei Xie

Computer Science Faculty Publications and Presentations

Robustness testing is a crucial stage in the device driver development cycle. To accelerate driver robustness testing, effective fault scenarios need to be generated and injected without requiring much time and human effort. In this pa- per, we present a practical approach to automatic runtime generation and injection of fault scenarios for driver robust- ness testing. We identify target functions that can fail from runtime execution traces, generate effective fault scenarios on these target functions using a bounded trace-based it- erative strategy, and inject the generated fault scenarios at runtime to test driver robustness using a permutation-based injection mechanism. We …

Naturalized Communication And Testing, Marly Roncken, Swetha Mettala Gilla, Hoon Park, Navaneeth Prasannakumar Jamadagni, Christopher Cowan, Ivan Sutherland

Computer Science Faculty Publications and Presentations

We ”naturalize” the handshake communication links of a self-timed system by assigning the capabilities of filling and draining a link and of storing its full or empty status to the link itself. This contrasts with assigning these capabilities to the joints, the modules connected by the links, as was previously done. Under naturalized communication, the differences between Micropipeline, GasP, Mousetrap, and Click circuits are seen only in the links — the joints become identical; past, present, and future link and joint designs become interchangeable. We also “naturalize” the actions of a self-timed system, giving actions status equal to states — …

Micro-Policies: Formally Verified, Tag-Based Security Monitors, Arthur Azevedo De Amorim, Maxime Denes, Nick Giannarakis, Cătălin Hriţcu, Benjamin C. Pierce, Antal Spector-Zabusky, Andrew Tolmach

Computer Science Faculty Publications and Presentations

Recent advances in hardware design have demonstrated mechanisms allowing a wide range of low-level security policies (or micro-policies) to be expressed using rules on metadata tags. We propose a methodology for defining and reasoning about such tag-based reference monitors in terms of a high-level “symbolic machine,” and we use this methodology to define and formally verify micro-policies for dynamic sealing, compartmentalization, control-flow integrity, and memory safety; in addition, we show how to use the tagging mechanism to protect its own integrity. For each micro-policy, we prove by refinement that the symbolic machine instantiated with the policy’s rules embodies a high-level …

Static Conflict Detection For A Policy Language, Alix Trou, Robert Dockins, Andrew Tolmach

Computer Science Faculty Publications and Presentations

We present a static control flow analysis used in the Simple Unified Policy Programming Language (SUPPL) compiler to detect internally inconsistent policies. For example, an access control policy can decide to both “allow” and “deny” access for a user; such an inconsistency is called a conflict. Policies in Suppl. follow the Event-Condition-Action paradigm; predicates are used to model conditions and event handlers are written in an imperative way. The analysis is twofold; it first computes a superset of all conflicts by looking for a combination of actions in the event handlers that might violate a user-supplied definition of conflicts. SMT …

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 …

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 …

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 …

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

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 …

Online Learning In A Chemical Perceptron, Peter Banda, Christof Teuscher, Matthew R. Lakin

Computer Science Faculty Publications and Presentations

Autonomous learning implemented purely by means of a synthetic chemical system has not been previously realized. Learning promotes reusability and minimizes the system design to simple input-output specification. In this article we introduce a chemical perceptron, the first full-featured implementation of a perceptron in an artificial (simulated) chemistry. A perceptron is the simplest system capable of learning, inspired by the functioning of a biological neuron. Our artificial chemistry is deterministic and discrete-time, and follows Michaelis-Menten kinetics. We present two models, the weight-loop perceptron and the weight-race perceptron, which represent two possible strategies for a chemical implementation of linear integration and …

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 …

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 …