Computer Engineering Commons^™

Multi-Agent Deep Reinforcement Learning For Radiation Localization, Benjamin Scott Totten

Dissertations and Theses

For the safety of both equipment and human life, it is important to identify the location of orphaned radioactive material as quickly and accurately as possible. There are many factors that make radiation localization a challenging task, such as low gamma radiation signal strength and the need to search in unknown environments without prior information. The inverse-square relationship between the intensity of radiation and the source location, the probabilistic nature of nuclear decay and gamma ray detection, and the pervasive presence of naturally occurring environmental radiation complicates localization tasks. The presence of obstructions in complex environments can further attenuate the …

Methodologies For Quantum Circuit And Algorithm Design At Low And High Levels, Edison Tsai

Dissertations and Theses

Although the concept of quantum computing has existed for decades, the technology needed to successfully implement a quantum computing system has not yet reached the level of sophistication, reliability, and scalability necessary for commercial viability until very recently. Significant progress on this front was made in the past few years, with IBM planning to create a 1000-qubit chip by the end of 2023, and Google already claiming to have achieved quantum supremacy. Other major industry players such as Intel and Microsoft have also invested significant amounts of resources into quantum computing research.

Any viable computing system requires both hardware and …

Digitally Reporting Trail Obstructions In Forest Park, Colton S. Maybee

REU Final Reports

The inclusion of technology on the trail can lead to better experiences for everyone involved in the hobby. Hikers can play a more prominent role in the maintenance of the trails by being able to provide better reports of obstructions while directly on the trail. This paper goes into the project of revamping the obstruction report system applied at Forest Park in Portland, Oregon. Most of my contributions to the project focus on mobile app development with some research into path planning algorithms related to the continuations of this project.

Forest Park Trail Monitoring, Adan Robles, Colton S. Maybee, Erin Dougherty

REU Final Reports

Forest Park, one of the largest public parks in the United States with over 40 trails to pick from when planning a hiking trip. One of the main problems this park has is that there are too many trails, and a lot of the trails extend over 3 miles. Due to these circumstances’ trails are not checked frequently and hikers are forced to hike trails in the area with no warnings of potential hazards they can encounter. In this paper I researched how Forest Park currently monitors its trails and then set up a goal to solve the problem. We …

Automated Statistical Structural Testing Techniques And Applications, Yang Shi

Dissertations and Theses

Statistical structural testing(SST) is an effective testing technique that produces random test inputs from probability distributions. SST shows superiority in fault-revealing power over random testing and deterministic approaches since it heritages the merits from both of them. SST ensures testing thoroughness by setting up a probability lower-bound criterion for each structural cover element and test inputs that exercise a structural cover element sampled from the probability distribution, ensuring testing randomness. Despite the advantages, SST is not a widely used approach in practice. There are two major limitations. First, to construct probability distributions, a tester must understand the underlying software's structure, …

A Method For Comparative Analysis Of Trusted Execution Environments, Stephano Cetola

Dissertations and Theses

The problem of secure remote computation has become a serious concern of hardware manufacturers and software developers alike. Trusted Execution Environments (TEEs) are a solution to the problem of secure remote computation in applications ranging from "chip and pin" financial transactions to intellectual property protection in modern gaming systems. While extensive literature has been published about many of these technologies, there exists no current model for comparing TEEs. This thesis provides hardware architects and designers with a set of tools for comparing TEEs. I do so by examining several properties of a TEE and comparing their implementations in several technologies. …

A Golden Age For Computing Frontiers, A Dark Age For Computing Education?, Christof Teuscher

Electrical and Computer Engineering Faculty Publications and Presentations

There is no doubt that the body of knowledge spanned by the computing disciplines has gone through an unprecedented expansion, both in depth and breadth, over the last century. In this position paper, we argue that this expansion has led to a crisis in computing education: quite literally the vast majority of the topics of interest of this conference are not taught at the undergraduate level and most graduate courses will only scratch the surface of a few selected topics. But alas, industry is increasingly expecting students to be familiar with emerging topics, such as neuromorphic, probabilistic, and quantum computing, …

Automated Test Generation For Validating Systemc Designs, Bin Lin

Dissertations and Theses

Modern system design involves integration of all components of a system on a single chip, namely System-on-a-Chip (SoC). The ever-increasing complexity of SoCs and rapidly decreasing time-to-market have pushed the design abstraction to the electronic system level (ESL), in order to increase design productivity. SystemC is a widely used ESL modeling language that plays a central role in modern SoCs design process. ESL SystemC designs usually serve as executable specifications for the subsequent SoCs design flow. Therefore, undetected bugs in ESL SystemC designs may propagate to low-level implementations or even final silicon products. In addition, modern SoCs design often involves …

Extending The Functional Subnetwork Approach To A Generalized Linear Integrate-And-Fire Neuron Model, Nicholas Szczecinski, Roger Quinn, Alexander J. Hunt

Mechanical and Materials Engineering Faculty Publications and Presentations

Engineering neural networks to perform specific tasks often represents a monumental challenge in determining network architecture and parameter values. In this work, we extend our previously-developed method for tuning networks of non-spiking neurons, the “Functional subnetwork approach” (FSA), to the tuning of networks composed of spiking neurons. This extension enables the direct assembly and tuning of networks of spiking neurons and synapses based on the network’s intended function, without the use of global optimization ormachine learning. To extend the FSA, we show that the dynamics of a generalized linear integrate and fire (GLIF) neuronmodel have fundamental similarities to those of …

Facilitating Mixed Self-Timed Circuits, Alexandra R. Hanson

University Honors Theses

Designers constrain the ordering of computation events in self-timed circuits to ensure the correct behavior of the circuits. Different circuit families utilize different constraints that, when families are combined, may be more difficult to guarantee in combination without inserting delay to postpone necessary events. By analyzing established constraints of different circuit families like Click and GasP, we are able to identify the small changes necessary to either 1) avoid constraints entirely; or 2) decrease the likelihood of necessary delay insertion. Because delay insertion can be tricky for novice designers and because the likelihood of its requirement increases when mixing different …

A Resource Constrained Shortest Paths Approach To Reducing Personal Pollution Exposure, Elling Payne

REU Final Reports

As wildfires surge in frequency and impact in the Pacific Northwest, in tandem with increasingly traffic-choked roads, personal exposure to harmful airborne pollutants is a rising concern. Particularly at risk are school-age children, especially those living in disadvantaged communities near major motorways and industrial centers. Many of these children must walk to school, and the choice of route can effect exposure. Route-planning applications and frameworks utilizing computational shortest paths methods have been proposed which consider personal exposure with reasonable success, but few have focused on pollution exposure, and all have been limited in scalability or geographic scope. This paper addresses …

Keyword-Based Patent Citation Prediction Via Information Theory, Farshad Madani, Martin Zwick, Tugrul U. Daim

Engineering and Technology Management Faculty Publications and Presentations

Patent citation shows how a technology impacts other inventions, so the number of patent citations (backward citations) is used in many technology prediction studies. Current prediction methods use patent citations, but since it may take a long time till a patent is cited by other inventors, identifying impactful patents based on their citations is not an effective way. The prediction method offered in this article predicts patent citations based on the content of patents. In this research, Reconstructability Analysis (RA), which is based on information theory and graph theory, is applied to predict patent citations based on keywords extracted from …

Shift-Symmetric Configurations In Two-Dimensional Cellular Automata: Irreversibility, Insolvability, And Enumeration, Peter Banda, John S. Caughman Iv, Martin Cenek, Christof Teuscher

Mathematics and Statistics Faculty Publications and Presentations

The search for symmetry as an unusual yet profoundly appealing phenomenon, and the origin of regular, repeating configuration patterns have been for a long time a central focus of complexity science, and physics.

Here, we introduce group-theoretic concepts to identify and enumerate the symmetric inputs, which result in irreversible system behaviors with undesired effects on many computational tasks. The concept of so-called configuration shift-symmetry is applied on two-dimensional cellular automata as an ideal model of computation. The results show the universal insolvability of “non-symmetric” tasks regardless of the transition function. By using a compact enumeration formula and bounding the number …

Vision-Based Motion For A Humanoid Robot, Khalid Abdullah Alkhulayfi

Dissertations and Theses

The overall objective of this thesis is to build an integrated, inexpensive, human-sized humanoid robot from scratch that looks and behaves like a human. More specifically, my goal is to build an android robot called Marie Curie robot that can act like a human actor in the Portland Cyber Theater in the play Quantum Debate with a known script of every robot behavior. In order to achieve this goal, the humanoid robot need to has degrees of freedom (DOF) similar to human DOFs. Each part of the Curie robot was built to achieve the goal of building a complete humanoid …

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 …

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 …

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 …

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 …