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 …

Emerging Adaptive Architectures For Biomolecular Computation, Matthew Fleetwood

Undergraduate Research & Mentoring Program

The goal of this work is to explore applications of reservoir computing in biomolecular computation. Reservoir computing is a unique model for representing a mapping from one instance in time to a specific output. A neural network of randomly connected neurons is linked with a single output neuron or multiple output neurons. The output neurons are capable of mapping inputs to desired outputs using adaptable algorithms. This framework is investigated by using the Python programming language and object oriented design and programming. Neurons are created in programs by bundling information like input data and attributes of the network, which utilize …

High-Performance Computing For Drought Prediction, Henry Cooney

Undergraduate Research & Mentoring Program

In recent decades, there has been considerable interest in using satellite soil moisture data to examine the global water-energy cycle and manage water resources. Current satellites are limited in their sensing depth, and can only directly measure top soil layers. Using a particle filter, this data may be fused with the output of a hydrologic simulation to improve simulation results, and characterize a hydrologic system at the watershed level. However, this approach increases computational requirements dramatically, and requires rethinking to accommodate data scaling and achieve good performance.

We present a detailed performance study of several alternative implementations of the hybrid …

A Verified Information-Flow Architecture, Arthur Azevedo De Amorim, Nathan Collins, André Dehon, Delphine Demange, Cătălin Hriţcu, David Pichardie, Benjamin C. Pierce, Randy Pollack, Andrew Tolmach

Computer Science Faculty Publications and Presentations

SAFE is a clean-slate design for a highly secure computer system, with pervasive mechanisms for tracking and limiting information flows. At the lowest level, the SAFE hardware supports fine-grained programmable tags, with efficient and flexible propagation and combination of tags as instructions are executed. The operating system virtualizes these generic facilities to present an information-flow abstract machine that allows user programs to label sensitive data with rich confidentiality policies. We present a formal, machine-checked model of the key hardware and software mechanisms used to dynamically control information flow in SAFE and an end-to-end proof of noninterference for this model. We …

Sparse Encoding Of Binocular Images For Depth Inference, Sheng Y. Lundquist, Dylan M. Paiton, Peter F. Schultz, Garrett T. Kenyon

Computer Science Faculty Publications and Presentations

Sparse coding models have been widely used to decompose monocular images into linear combinations of small numbers of basis vectors drawn from an overcomplete set. However, little work has examined sparse coding in the context of stereopsis. In this paper, we demonstrate that sparse coding facilitates better depth inference with sparse activations than comparable feed-forward networks of the same size. This is likely due to the noise and redundancy of feed-forward activations, whereas sparse coding utilizes lateral competition to selectively encode image features within a narrow band of depths.

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 …

Computational Capacity And Energy Consumption Of Complex Resistive Switch Networks, Jens Bürger, Alireza Goudarzi, Darko Stefanovic, Christof Teuscher

Electrical and Computer Engineering Faculty Publications and Presentations

Resistive switches are a class of emerging nanoelectronics devices that exhibit a wide variety of switching characteristics closely resembling behaviors of biological synapses. Assembled into random networks, such resistive switches produce emerging behaviors far more complex than that of individual devices. This was previously demonstrated in simulations that exploit information processing within these random networks to solve tasks that require nonlinear computation as well as memory. Physical assemblies of such networks manifest complex spatial structures and basic processing capabilities often related to biologically-inspired computing. We model and simulate random resistive switch networks and analyze their computational capacities. We provide a …

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 …

Semi-Modular Delay Model Revisited In Context Of Relative Timing, Hoon Park, Anping He, Marly Roncken, Xiaoyu Song

Electrical and Computer Engineering Faculty Publications and Presentations

A new definition of semi-modularity to accommodate relative timing constraints in self-timed circuits is presented. While previous definitions ignore such constraints, the new definition takes them into account. The difference on a design solution for a well-known speed-independent circuit implementation of the Muller C element and a set of relative timing constraints that renders the implementation hazard free is illustrated. The old definition produces a false semi-modularity conflict that cannot exist due to the set of imposed constraints. The new definition correctly accepts the solution.

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 …

Evolution And Usage Of The Portal Data Archive: 10-Year Retrospective, Kristin A. Tufte, Robert Bertini, Morgan Harvey

Civil and Environmental Engineering Faculty Publications and Presentations

The Portal transportation data archive (http://portal.its.pdx.edu/) was begun in June 2004 in collaboration with the Oregon Department of Transportation, with a single data source: freeway loop detector data. In 10 years, Portal has grown to contain approximately 3 TB of transportation-related data from a wide variety of systems and sources, including freeway data, arterial signal data, travel times from Bluetooth detection systems, transit data, and bicycle count data. Over its 10-year existence, Portal has expanded both in the type of data that it receives and in the geographic regions from which it gets data. This paper discusses the …

Creating A National Nonmotorized Traffic Count Archive: Process And Progress, Krista Nordback, Kristin A. Tufte, Morgan Harvey, Nathan Mcneil, Elizabeth Stolz, Jolene Liu

Civil and Environmental Engineering Faculty Publications and Presentations

Robust bicycle and pedestrian data on a national scale would help promote effective planning and engineering of walking and bicycling facilities, build the evidence-based case for funding such projects, and dispel notions that walking and cycling are not occurring. To organize and promote the collection of nonmotorized traffic data, a team of transportation professionals and computer scientists is creating a national bicycle and pedestrian count archive. This archive will enable data sharing by centralizing continuous and short-duration traffic counts in a publicly available online archive. Although other archives exist, this will be the first archive that will be national in …

Modular Timing Constraints For Delay-Insensitive Systems, Hoon Park, Anping He, Marly Roncken, Xiaoyu Song, Ivan Sutherland

Electrical and Computer Engineering Faculty Publications and Presentations

This paper introduces ARCtimer, a framework for modeling, generating, verifying, and enforcing timing constraints for individual self-timed handshake components. The constraints guarantee that the component’s gate-level circuit implementation obeys the component’s handshake protocol specification. Because the handshake protocols are delayinsensitive, self-timed systems built using ARCtimer-verified components are also delay-insensitive. By carefully considering time locally, we can ignore time globally. ARCtimer comes early in the design process as part of building a library of verified components for later system use. The library also stores static timing analysis (STA) code to validate and enforce the component’s constraints in any self-timed system built …

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 …

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 …

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

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 …

Using System Dynamics To Contribute To Ecological Economics, Takuro Uehara, Yoko Nagase, Wayne Wakeland

Systems Science Faculty Publications and Presentations

This paper demonstrates the usefulness of the system dynamics approach to the development of ecological economics, the study of the interactions between economic systems and ecological systems. We build and analyze an ecological economic model: an extension of a population–resource dynamics model developed by Brander and Taylor and published in American Economic Review in 1998. The focus of the present paper is on the model building and analysis to contribute to theory building rather than eliciting policy implications from the model. Hence, this is an example of model-based theory building using system dynamics. Our analysis sheds light on several problems …

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

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

A System Dynamics Model Of Pharmaceutical Opioids: Medical Use, Diversion, And Nonmedical Use, Teresa Schmidt, Wayne Wakeland, J. David Haddox

Systems Science Faculty Publications and Presentations

A dramatic rise in the nonmedical of pharmaceutical opioids has presented the United States with a substantial public health problem. Nonmedical use of prescription pain relievers has become increasingly prevalent in the US over the last two decades, and diversion of medicines obtained by prescription is assumed to be a major source of supply for nonmedical opioid use. Policymakers striving to protect population health by ameliorating the adverse outcomes of nonmedical use of opioid analgesics could benefit from a systems-level model which reflects the complexity of the system and incorporates the full range of available data. To address this need, …

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.