Computer Engineering Commons^™

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 …

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 …

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 …

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 …

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 …

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 …

Demonstrating "Data Near Here": Scientific Data Search, Veronika Margaret Megler, David Maier

Computer Science Faculty Publications and Presentations

Prior work proposed "Data Near Here" (DNH), a data search engine for scientific archives that is modeled on Internet search engines. DNH performs a periodic, asynchronous scan of each dataset in an archive, extracting lightweight features that are combined to form a dataset summary. During a search, DNH assesses the similarity of the search terms to the summary features and returns to the user, at interactive timescales, a ranked list of datasets for further exploration and analysis. We will demonstrate the search capabilities and ancillary metadata-browsing features for an archive of observational oceanographic data. While comparing search terms to complete …

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 …

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 …

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 …

Detection Of Variable Retention Time In Dram, Neraj Kumar

Dissertations and Theses

This thesis investigates a test method to detect the presence of Variable Retention Time (VRT) bits in manufactured DRAM. The VRT bits retention time is modeled as a 2-state random telegraph process that includes miscorrelation between test and use. The VRT defect is particularly sensitive to test and use conditions. A new test method is proposed to screen the VRT bits by simulating the use conditions during manufacturing test. Evaluation of the proposed test method required a bit-level VRT model to be parameterized as a function of temperature and voltage conditions. The complete 2-state VRT bit model combines models for …

System-Wide Performance Analysis For Virtualization, Deron Eugene Jensen

Dissertations and Theses

With the current trend in cloud computing and virtualization, more organizations are moving their systems from a physical host to a virtual server.

Although this can significantly reduce hardware, power, and administration costs, it can increase the cost of analyzing performance problems. With virtualization, there is an initial performance overhead, and as more virtual machines are added to a physical host the interference increases between various guest machines. When this interference occurs, a virtualized guest application may not perform as expected. There is little or no information to the virtual OS about the interference, and the current performance tools in …

Ranked Similarity Search Of Scientific Datasets: An Information Retrieval Approach, Veronika Margaret Megler

Dissertations and Theses

In the past decade, the amount of scientific data collected and generated by scientists has grown dramatically. This growth has intensified an existing problem: in large archives consisting of datasets stored in many files, formats and locations, how can scientists find data relevant to their research interests? We approach this problem in a new way: by adapting Information Retrieval techniques, developed for searching text documents, into the world of (primarily numeric) scientific data. We propose an approach that uses a blend of automated and curated methods to extract metadata from large repositories of scientific data. We then perform searches over …

Building A Better Computer For The Aging Generation, Gretchen Baird, Boryeon Kwon, Dylan Lasner, Parker Swensen, Zane Ross, Adrik Gurganus

PSU High School Innovation Challenge

The problem which we have ventured out to solve is that the aging community does not have easily accessible computers and technologies.

Lifebrace: The Advanced Health Tracking Wristband, Jeremy Ferrando, Dylan O'Brien, Daniel Ortiz, Jonah Paivarinta

PSU High School Innovation Challenge

Over 28 million Americans have diabetes or pre-diabetes. Every 33 seconds someone dies of heart disease, claiming more lives than AIDS and all forms of cancer combined. Falls are the leading cause of fatal and non fatal injuries to elderly people.

These problems require constant supervision and frequent treatments to keep a patient stable, and they all become more serious with age. People with diabetes, heart conditions, or other debilitating conditions need frequent check-ups, and are always in danger of accidents. They also often need frequent doses of medicine.

The only way that these conditions can be monitored properly is …

Tech For Arthritis, Alex Gaiovych, Anna Velikoretskikh, Ephraim Lee, Karl Stephenson, Kevin Wu, Miguel Campos, Veyda Campos

PSU High School Innovation Challenge

In an era where technological advances are made on almost a daily basis, there are still many people who aren’t able or are scared to use modern technology. While computers and phones get smarter and more powerful, they are also getting smaller and more precise. Trying to push a tiny button, either real or virtual, can be a real problem for those who suffer from arthritis.

According to www.arthritis.org, over 50 million people are diagnosed with arthritis, most of which are senior citizens. Many of these seniors don’t use technology to its full potential because they simply can’t. For some, …

Mobile Robot Localization Based On Kalman Filter, Omar Q. Mohsin

Dissertations and Theses

Robot localization is one of the most important subjects in the Robotics science. It is an interesting and complicated topic. There are many algorithms to solve the problem of localization. Each localization system has its own set of features, and based on them, a solution will be chosen. In my thesis, I want to present a solution to find the best estimate for a robot position in certain space for which a map is available. The thesis started with an elementary introduction to the probability and the Gaussian theories. Simple and advanced practical examples are presented to illustrate each concept …

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 …

Trust-But-Verify: Guaranteeing The Integrity Of User-Generated Content In Online Applications, Akshay Dua

Dissertations and Theses

Online applications that are open to participation lack reliable methods to establish the integrity of user-generated information. Users may unknowingly own compromised devices, or intentionally publish forged information. In these scenarios, applications need some way to determine the "correctness" of autonomously generated information. Towards that end, this thesis presents a "trust-but-verify" approach that enables open online applications to independently verify the information generated by each participant. In addition to enabling independent verification, our framework allows an application to verify less information from more trustworthy users and verify more information from less trustworthy ones. Thus, an application can trade-off performance for …

Self-Timed Dram Data Interface, Rajesh Nerkar

Dissertations and Theses

A DRAM communicates with a processing unit via two interfaces: a data interface and a command interface. In today's DRAMs, also known as synchronous DRAMs (SDRAMs), both interfaces use a clock to communicate with the processing unit. The clock times the communication between the processing unit and the SDRAM on both the data interface and the command interface.

We propose a self-timed DRAM. The self-timed DRAM introduces more flexibility into the DRAM interface by eliminating the clock. The command interface and the data interface each communicate with the processing unit using a handshake protocol rather than a clock.

This thesis …

Equivalence Checking For High-Assurance Behavioral Synthesis, Kecheng Hao

Dissertations and Theses

The rapidly increasing complexities of hardware designs are forcing design methodologies and tools to move to the Electronic System Level (ESL), a higher abstraction level with better productivity than the state-of-the-art Register Transfer Level (RTL). Behavioral synthesis, which automatically synthesizes ESL behavioral specifications to RTL implementations, plays a central role in this transition. However, since behavioral synthesis is a complex and error-prone translation process, the lack of designers' confidence in its correctness becomes a major barrier to its wide adoption. Therefore, techniques for establishing equivalence between an ESL specification and its synthesized RTL implementation are critical to bring behavioral synthesis …

Designing A Low Cost Prosthetic Arm Device, Samira Rezaei, Frank Fields, Tamara J. Depue

Student Research Symposium

The goal of the project is to build a functional low-cost prosthetic arm that is easily maintained. The focus is on prostheses that attach to the forearm. This design must perform daily life tasks such as picking up, holding and carrying objects while playing and working. To begin the design, a mechanical finger was built with wooden tongue depressors as bone material; rubber bands, string, and drinking straws as muscle material; and masking tape as ligament and tendon material. The length of each joint was set to the golden ratio. Using this method, a basic "hand" was created that could …

A Quantitative Analysis Of Memory Controller Page Policies, Matthew Blackmore

Dissertations and Theses

Two common goals in computing system design are increasing performance and decreasing power consumption. DRAM-based memory subsystems are a major component of both system performance and power consumption. Memory controllers employ strategies to efficiently schedule DRAM operations to reduce latency and to utilize DRAM low power modes when possible. One of the most important of these is the page policy, which determines when to close pages in DRAM. An effective DRAM memory controller page policy is important to minimizing power consumption and increasing system performance. This thesis explores the impact memory controller page policy has on performance as measured by …

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 …

Optimal Network Topologies And Resource Mappings For Heterogeneous Networks-On-Chip, Haera Chung

Dissertations and Theses

Communication has become a bottleneck for modern microprocessors and multi-core chips because metal wires don't scale. The problem becomes worse as the number of components increases and chips become bigger. Traditional Systems-on-Chips (SoCs) interconnect architectures are based on shared-bus communication, which can carry only one communication transaction at a time. This limits the communication bandwidth and scalability. Networks-on-Chip (NoC) were proposed as a promising solution for designing large and complex SoCs. The NoC paradigm provides better scalability and reusability for future SoCs, however, long-distance multi-hop communication through traditional metal wires suffers from both high latency and power consumption. A radical …

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

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

Measurement And Modeling Of Passive Surface Mount Devices On Fr4 Substrates, Rahulkumar Sadanand Koche

Dissertations and Theses

Passive components like resistors, capacitors and inductors are used in every electronic system. These are the very basic components which affect the system performance at higher frequencies and it is necessary to understand and model the behavior of these components in a very accurate manner. This work focuses on utilizing Printed Circuit Board (PCB) test boards, or fixtures, made of FR4 for characterizing Surface Mount Device (SMD) components. Agilent's Advanced Design System (ADS) microwave circuit simulation software was used for designing the microstrip transmission lines as well as for generating the layout for manufacturing of the PCB. SMD resistors, capacitors …

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

Complex Systems 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, …