Follow


Theses/Dissertations from 2012

PDF

MCFlow: Middleware for Mixed-Criticality Distributed Real-Time Systems, Huang-Ming Huang

PDF

Building a Skeleton of a Human Hand Using Microsoft Kinect
Jed Jackoway
Technical Report

Abstract:

The goal of the project was to reconstruct the skeleton of a Microsoft Kinect user’s hand. Out of the box, Kinect reconstruct the skeleton of users’ bodies, but it only does large joints, such that the hand is given a location on the general skeleton, but the specifics of the fingers and fist are not actually calculated.

PDF

RIDE: A Mixed-Mode Control Interface for Mobile Robot Teams
Erik Karulf, Marshall Strother, Parker Dunton, and William D. Smart
Technical Report

Abstract:

There is a growing need for robot control interfaces that allow a single user to effectively control a large number of mostly-autonomous robots. The challenges in controlling such a collection of robots are very similar to the challenges of controlling characters in some genres of video games. In this paper, we argue that interfaces based on elements from computer video games are effective tools for the control of large robot teams. We present RIDE, the Robot Interactive Display Environment, an example of such an interface, and give the results of... Read More

PDF

The Clear Channel Prior
Devorah Langsam
Technical Report

Abstract:

Capturing imagery from outdoor cameras provides a large amount of information about a scene. The true surface appearances of elements in a scene, however, are often incorrectly represented in images. To get a better representation of the scene it is necessary to separate the effects of the underlying reflectance, illumination, and fog in the image. The goal of the dark channel prior is to eliminate the effects of haze in outdoor images and recover the true surface reflectance image for the scene.

... Read More

PDF

Data collection and performance monitoring of real-time parallel systems
Mahesh Mahadevan
Technical Report

Abstract:

Instrumentation and log data monitoring are important features present in many different applications today that are used in analysis of a system behaviour. They are largely used in collection of key information from the system which might allow us to describe or establish certain facts about the behavior of the system. Instrumentation in any application usually comes along with its overheads. In some cases , code for instrumentation might become more expensive on the underlying resources than the application itself. For many applications, especially real-time applications , this overhead can... Read More

PDF

A Memory Access Model for Highly-threaded Many-core Architectures
Lin Ma, Kunal Agrawal, and Roger D. Chamberlain
Technical Report

Abstract:

Many-core architectures are excellent in hiding memory-access latency by low-overhead context switching among a large number of threads. The speedup of algorithms carried out on these machines depends on how well the latency is hidden. If the number of threads were infinite, then theoretically these machines should provide the performance predicted by the PRAM analysis of the programs. However, the number of allowable threads per processor is not infinite. In this paper, we introduce the Threaded Many-core Memory (TMM) model which is meant to capture the important characteristics of these... Read More

PDF

An Integrated Data Mining Approach to Real-time Clinical Monitoring and Deterioration Warning
Yi Mao, Wenlin Chen, Yixin Chen, and Chenyang Lu
Technical Report

Abstract:

Clinical study found that early detection and intervention are essential for preventing clinical deterioration in patients, for patients both in intensive care units (ICU) as well as in general wards but under real-time data sensing (RDS). In this paper, we develop an integrated data mining approach to give early deterioration warnings for patients under real-time monitoring in ICU and RDS. Existing work on mining real-time clinical data often focus on certain single vital sign and specific disease. In this paper, we consider an integrated data mining approach for general sudden... Read More

PDF

A 3D Selection & Query Tool for the GeneAtlas Project
Donald McCurdy
Technical Report

Abstract:

In this project, I present an application to view, interact with, and search 3D medical volumes as part of the GeneAtlas project.

PDF

Youpon
Garrison Prinslow
Technical Report

Abstract:

This project was motivated by two related ideas: what can be learned about the unique issues involved with developing cloud-based mobile applications; and, what application could be developed to evaluate these characteristics that would also be innovative and provide value to users. After vetting ideas for the latter objective, it was clear that a new digital coupon system could offer value and apply interesting technologies to computer science problems, such as shortest path calculation, position-aware authentication, game theory, and statistical reasoning. A brief summary of the motivation for developing the... Read More

PDF

Self-Stabilization in the Distributed Systems of Finite State Machines
Abusayeed Saifullah
Technical Report

Abstract:

The notion of self-stabilization was first proposed by Dijkstra in 1974 in his classic paper. The paper defines a system as self-stabilizing if, starting at any, possibly illegitimate, state the system can automatically adjust itself to eventually converge to a legitimate state in finite amount of time and once in a legitimate state it will remain so unless it incurs a subsequent transient fault. Dijkstra limited his attention to a ring of finite-state machines and provided its solution for self-stabilization. In the years following his introduction, very few papers were... Read More

PDF

Studying Network Optimization in the Context of Self-Stabilization
Abusayeed Saifullah
Technical Report

Abstract:

Self-stabilization is a theoretical framework of non-masking fault-tolerance for distributed networks. A self-stabilizing system is capable of tolerating any unexpected transient fault without outside intervention and, regardless of the initial state, it can converge to a legitimate global state, a predefined vector of local states, in finite time. Self-stabilization has rendered a good problem solving paradigm of networks over the last decade. In this paper, we survey the self-stabilizing solutions for various network optimization problems such as network flow, load balancing, load and resource distribution, routing, file distribution, shortest paths... Read More

PDF

Correction of an Augmentation Bound Analysis for Parallel Real-Time Tasks
Abusayeed Saifullah, Kunal Agrawal, Chenyang Lu, and Christopher Gill
Technical Report

Abstract:

This paper proposes some significant corrections in a recent work of Lakshmanan et al on parallel task scheduling. Lakshmanan et al have proposed a transformation of parallel tasks into sequential tasks, and have claimed a resource augmentation bound of 3:42 for partitioned deadline monotonic (DM) scheduling of the transformed tasks. We demonstrate that their analysis for resource augmentation bound is incorrect. We propose a different technique for task transformation that requires a resource augmentation bound of 5 for partitioned DM scheduling.

... Read More

PDF

Real-Time Scheduling of Parallel Tasks under a General DAG Model
Abusayeed Saifullah, David Ferry, Chenyang Lu, and Christopher Gill
Technical Report

Abstract:

Due to their potential to deliver increased performance over single-core processors, multi-core processors have become mainstream in processor design. Computation-intensive real-time systems must exploit intra-task parallelism to take full advantage of multi-core processing. However, existing results in real-time scheduling of parallel tasks focus on restrictive task models such as the synchronous model where a task is a sequence of alternating parallel and sequential segments, and parallel segments have threads of execution that are of equal length. In this paper, we address a general model for deterministic parallel tasks, where a... Read More

PDF

Accounting for Failures in Delay Analysis for WirelessHART Networks
Abusayeed Saifullah, Paras Babu Tiwari, Bo Li, and Chenyang Lu lu@wustl.edu
Technical Report

Abstract:

WirelessHART networks are gaining ground as a real-time communication infrastructure in industrial wireless control systems. Because wireless communication is often susceptible to transmission failures in industrial environments, it is essential to account for failures in the delay analysis for realtime flows between sensors and actuators in process control. WirelessHART networks handle transmission failures through retransmissions using dedicated and shared time slots through different paths in the routing graphs. While these mechanisms for handling transmission failures are critical for process control requiring reliable communication, they introduce substantial challenges to worst-case end-to-end... Read More

PDF

Foveon F13 Camera
David Shelley
Technical Report

Abstract:

Most high-fidelity digital cameras currently available obtain their images using technology where individual pixels can only acquire a single color. Since the acquisition of multiple colors is necessary to capture a full colored image, picture resolution is lost due to difficulties in interpolation between non-adjacent, same color pixels. The resulting unsharp images create the need to find a new way to obtain these images without requiring interpolation between adjacent pixels. An innovative method to capture images with individual pixel cells consisting of three layers of photodetectors stacked vertically upon one... Read More

PDF

Modeling Surfaces from Volume Data Using Nonparallel Contours, Ross Taylor Sowell

PDF

Specializing Interfaces for Citizen Science Segmentation of Volumetric Data
Michelle Vaughan, Cindy Grimm, Ruth Sowell, Robert Pless, and Stephen Kobourov
Technical Report

Abstract:

Segmentation of 3D and time-varying volumetric (4D) image data is considered a time and resource intensive bottleneck in scientific endeavors. Automatic methods are becoming more reliable, but many data sets still require manual intervention. This can mainly be attributed to the characteristics of the image data not being amenable to automated methods, the existence of variations in or poor image quality, or the need for an expert to review and edit results from an automatic technique. Manually segmenting volumetric data is a challenge even for those more experienced. Understanding the... Read More

PDF

Limitations and Solutions for Real-Time Local Inter-Domain Communication in Xen
Sisu Xi, Chong Li, Chenyang Lu, and Christopher Gill
Technical Report

Abstract:

As computer hardware becomes increasingly powerful, there is an ongoing trend towards integrating complex, legacy real-time systems using fewer hosts through virtualization. Especially in embedded systems domains such as avionics and automotive engineering, this kind of system integration can greatly reduce system weight, cost, and power requirements. When systems are integrated in this manner, network communication may become local inter-domain communication (IDC) within the same host. This paper examines the limitations of inter-domain communication in Xen, a widely used open-source virtual machine monitor (VMM) that recently has been extended to... Read More

PDF

Early Warning System: Relay Sensor Deployment & Network Reliability Analysis
Zhicheng Yang
Technical Report

Abstract:

In this project, we continued Dr. Chipara's study, which developed an early warning system (EWS) to detect the vital signs of patients in order to help doctors to intervene in time [1]. Since the number of wards increased, the environment our system faced with became more complicated and our network became more sensitive. This project focused on finding reasons on the relays that didn't work and doing a reliability analysis on the network in one ward our study covered.

... Read More

PDF

Delaunay-restricted Optimal Triangulation of 3D Polygons
Ming Zou, Tao Ju, and Nathan Carr
Technical Report

Abstract:

Triangulation of 3D polygons is a well studied topic of research. Existing methods for finding triangulations that minimize given metrics (e.g., sum of triangle areas or dihedral angles) run in a costly O(n4) time [BS95,BDE96], while the triangulations are not guaranteed to be free of intersections. To address these limitations, we restrict our search to the space of triangles in the Delaunay tetrahedralization of the polygon. The restriction allows us to reduce the running time down to O(n2) in practice (O(n3) worst case) while guaranteeing that the solutions are intersection... Read More

Research from 2011

PDF

Hierarchical Scheduling for Multicores with Multilevel Cache Hierarchies
Kunal Agrawal and Jim Sukha
Technical Report

Abstract:

Cache-locality is an important consideration for the performance in multicore systems. In modern and future multicore systems with multilevel cache hierarchies, caches may be arranged in a tree of caches, where a level k cache is shared between Pk processors, called a processor group, and Pk increases with k. In order to get good performance, as much as possible, subcomputations that share more data should execute on processors which share a lower-level cache. Therefore, the number of cache misses in these systems depends on the scheduling decisions, and a scheduler... Read More

PDF

Motion-Based Video Games for Stroke Rehabilitation with Reduced Compensatory Motions, Gazihan Alankus

PDF

Generating Muscle Driven Arm Movements Using Reinforcement Learning
Alex S. Broad
Technical Report

Abstract:

This project focuses on using Reinforcement Learning to optimize arm dynamics through muscle control for desired trajectories. The goal of this project was to create a tool that can be used to gain a better understanding of the arm’s muscles and collect information that is useful in many other disciplines such as biomechanics, anthropology, medicine and robotics. I developed biologically realistic models of primate arm's using Stanford’s SimTK software, an open-source tool for modeling musculoskeletal structures. I then made use of Differential Dynamic Programming in order to generate novel movements... Read More

PDF

Mercury BLASTN Biosequence Similarity Search System: Technical Reference Guide
Jeremy Buhler
Technical Report

Abstract:

This guide documents the operation of the Mercury BLASTN system for hardware-accelerated DNA similarity search. It includes detailed information on the syntax and limitations of the system's component commands, as well as a description of the system's hardware platform suitable for administrators who need to maintain a Mercury BLASTN system. Mercury BLASTN is a product of the High Performance COmputational Biology Group at Washington University.

... Read More

PDF

Efficient Deadlock Avoidance for Streaming Computation with Filtering
Jeremy Buhler, Kunal Agrawal, Peng Li, and Roger D. Chamberlain
Technical Report

Abstract:

In this report, we show that deadlock avoidance for streaming computations with filtering can be performed efficiently for a large class of DAG topologies. We first give efficient algorithms for dummy interval computation in series-parallel DAGs, then generalize our results to a larger graph family, the CS4DAGs, in which every undirected cycle has exactly one source and one sink. Our results show that, for a large set of application topologies that are both intuitively useful and formalizable, the streaming model with filtering can be implemented safely with reasonable compilation overhead.

... Read More

PDF

Clinical Interpretation of Novel Copy Number Variations, Clifton Carey

PDF

Optimal Control for Autonomous Motor Behavior, Tom Erez

PDF

Flux Balance Analysis of Dynamic Metabolism in Shewanella oneidensis MR-1 Using a Static Optimization Approach
Xueyang Feng, You Xu, Yixin Chen, and Yinjie Tang
Technical Report

Abstract:

Shewanella bacteria are facultative anaerobes isolated from aquatic and sedimentary environments (Hau and Gralnick 2007) with a broad capacity for reduction of multiple electron receptors (Pinchuk et al. 2009; Serres and Riley 2006), including Fe(III), Mn(IV), sulfur, nitrate, and fumarate. With the accomplishment of complete genome sequencing of several Shewanella bacteria, the general pictures of the carbon metabolism have been revealed (Serres and Riley 2006). metabolism. One of the most physiological methods to decipher the time-variant metabolic regulation is to determine the dynamic distribution of intracellular metabolic fluxes since it... Read More

PDF

Feedback Thermal Control of Real-time Systems on Multicore Processors
Yong Fu, Nicholas Kottenstette, Chenyang Lu, and Xenofon D. Koutsoukos
Technical Report

Abstract:

Real-time systems face significant challenges in thermal management with their adoption of modern multicore processors. While earlier research on feedback thermal control has shown promise in dealing with the uncertainties in the thermal characteristics, multicore processors introduce new challenges that cannot be handled by previous solutions designed for single-core processors. Multicore processors require the temperatures and real-time performance of multiple cores to be controlled simultaneously, leading to multi-input-multi-output (MIMO) control problems with inter-core thermal coupling. Furthermore, current Dynamic Voltage and Frequency Scaling (DVFS) mechanisms only support a finite set of... Read More

PDF

Results of an observational study on sketching
Cindy Grimm
Technical Report

Abstract:

We present the results of an observational study on sketching. Artists were asked to sketch a small number of objects and comment on how and why they made the marks they did. We summarize these findings, from low-level details on individual marks through the drawing construction order. Based on these observations we provide suggestions for future research directions in 3D sketching.

... Read More

PDF

Practical and Robust Power Management for Wireless Sensor Networks, Gregory Hackmann

PDF

Implementation and Evaluation of Mixed-Criticality Scheduling Approaches for Periodic Tasks
Huang-Ming Huang, Christopher Gill, and Chenyang Lu
Technical Report

Abstract:

Traditional fixed-priority scheduling analysis for periodic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the scheduling policy, and estimates of tasks’ worst case execution times must be conservative in case a task runs longer than is usual. To address the significant under-utilization of a system’s resources under normal operating conditions that can arise from these assumptions, three main approaches have been proposed: priority assignment, period transformation, and zero-slack scheduling. However,... Read More

PDF

Efficient Automated Planning with New Formulations, Ruoyun Huang

PDF

Mixed-Mode Control Interfaces of Mobile Robot Teams, Erik Karulf

PDF

Webcam Image Alignment
Matthew Klein
Technical Report

PDF

Real Time Baseball Augmented Reality
Adam Kraft
Technical Report

Abstract:

As computer hardware becomes increasingly powerful, there is an ongoing trend towards integrating complex, legacy real-time systems using fewer hosts through virtualization. Especially in embedded systems domains such as avionics and automotive engineerin

PDF

Computational Methods for Accelerated Discovery and Characterization of Genes in Emerging Model Organisms, Alan Kwan

PDF

Low-Impact Profiling of Streaming, Heterogeneous Applications, Joseph Lancaster

PDF

Multi-Dimensional Medial Geometry: Formulation, Computation, and Applications, Lu Liu

PDF

Decoding Brain Activation from Ipsilateral Cortex using ECoG Signals in Humans, Yuzong Liu

PDF

A Survey on Communication Networks in Emergency Warning Systems
Yan Li
Technical Report

PDF

Optimization of Gene Prediction via More Accurate Phylogenetic Substitution Models
Ezekiel Maier, Randall H. Brown, and Michael R. Brent
Technical Report

Abstract:

Determining the beginning and end positions of each exon in each protein coding gene within a genome can be difficult because the DNA patterns that signal a gene’s presence have multiple weakly related alternate forms and the DNA fragments that comprise a gene are generally small in comparison to the size of the genome. In response to this challenge, automated gene predictors were created to generate putative gene structures. N SCAN identifies gene structures in a target DNA sequence and can use conservation patterns learned from alignments between a target... Read More

PDF

How Can Robots Adapt To A Social Human World? A Study Into The Role Gestures Can Play In Human-Robot Relations, Bradley Matherne

PDF

Simplifying The Non-Manifold Topology Of Multi-Partitioning Surface Networks, Trung Nguyen

PDF

2-Edge-Connectivity and 2-Vertex-Connectivity with Fault Containment
Abusayeed Saifullah
Technical Report

Abstract:

Self-stabilization for non-masking fault-tolerant distributed system has received considerable research interest over the last decade. In this paper, we propose a self-stabilizing algorithm for 2-edge-connectivity and 2-vertex-connectivity of an asynchronous distributed computer network. It is based on a self-stabilizing depth-first search, and is not a composite algorithm in the sense that it is not composed of a number of self-stabilizing algorithms that run concurrently. The time and space complexities of the algorithm are the same as those of the underlying self-stabilizing depth-first search algorithm.

... Read More

PDF

Multi-core Real-Time Scheduling for Generalized Parallel Task Models
Abusayeed Saifullah, Kunal Agrawal, Chenyang Lu, and Christopher Gill
Technical Report

Abstract:

Multi-core processors over a significant performance increase over single-core processors. Therefore, they have the potential to enable computation-intensive real-time applications with stringent timing constraints that cannot be met on traditional single-core processors. However, most results in traditional multiprocessor real-time scheduling are limited to sequential programming models and ignore intra-task parallelism. In this paper, we address the problem of scheduling periodic parallel tasks with implicit deadlines on multi-core processors. We first consider a synchronous task model where each task consists of segments, each segment having an arbitrary number of parallel threads... Read More

PDF

Near Optimal Rate Selection for Wireless Control Systems
Abusayeed Saifullah, Chengjie Wu, Paras Babu Tiwari, You Xu, Yong Fu, Chenyang Lu, and Yixin Chen
Technical Report

Abstract:

With the advent of industrial standards such as WirelessHART, process industries are now gravitating towards wireless control systems. Due to limited bandwidth in a wireless network shared by multiple control loops, it is critical to optimize the overall control performance. In this paper, we address the scheduling-control co-design problem of determining the optimal sampling rates of feedback control loops sharing a WirelessHART network. The objective is to minimize the overall control cost while ensuring that all data flows meet their end-to-end deadlines. The resulting constrained optimization based on existing delay... Read More

PDF

Distributed Channel Allocation Algorithms for Wireless Sensor Networks
Abusayeed Saifullah, You Xu, Chenyang Lu, and Yixin Chen
Technical Report

Abstract:

Interference between concurrent transmissions can cause severe performance degradation in wireless sensor networks (WSNs). While multiple channels available in WSN technology such as IEEE 802.15.4 can be exploited to mitigate interference, channel allocation can have a significant impact on the performance of multi-channel communication. This paper proposes a set of distributed algorithms for near-optimal channel allocation in WSNs with theoretical bounds. We first consider the problem of minimizing the number of channels needed to remove interference in a WSN, and propose both receiver-based and link-based distributed channel allocation protocols. For... Read More

PDF

End-to-End Communication Delay Analysis in WirelessHART Networks
Abusayeed Saifullah, You Xu, Chenyang Lu, and Yixin Chen
Technical Report

Abstract:

WirelessHART is a new standard specifically designed for real-time and reliable communication between sensor and actuator devices for industrial process monitoring and control applications. End-to-end communication delay analysis for WirelessHART networks is required to determine the schedulability of real-time data flows from sensors to actuators for the purpose of acceptance test or workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We then exploit the response time analysis for multiprocessor scheduling and... Read More

PDF

A Graph-Based Algorithm to Determine Protein Structure from Cryo-EM Data, Stephen Schuh

PDF

Empirical Studies for Reliable Home Area Wireless Sensor Networks, Mo Sha

PDF

Energy-Efficient Low Power Listening for Wireless Sensor Networks in Noisy Environments
Mo Sha, Gregory Hackmann, and Chenyang Lu
Technical Report

Abstract:

Low Power Listening (LPL) is a common MAC-layer technique for reducing energy consumption in wireless sensor networks, where nodes periodically wake up to sample the wireless channel to detect activity. However, LPL is highly susceptible to false wakeups caused by environmental noise being detected as activity on the channel, causing nodes to spuriously wake up in order to receive nonexistent transmissions. In empirical studies in residential environments, we observe that the false wakeup problem can significantly increase a node's duty cycle, compromising the benefit of LPL. We also find that... Read More

PDF

The Forest Overlay Network
Logan Stafman
Technical Report

Abstract:

Forest is an overlay network designed for large real-time distributed systems. In particular, we’re interested in virtual worlds that provide high-quality interaction over a constantly changing pattern of communication. Forest is suitable for applications in which many entities send data to a large set of constantly changing entities. By using tree-structured channels, we can create logically isolated private networks which support both unicast and multicast routing. In this paper, we will discuss the core components of Forest and measure the performance of the control elements of the network. We will... Read More

PDF

NS-3 Simulation of WiMAX Networks, Christopher Thomas

PDF

Utility-Aware Scheduling of Stochastic Real-Time Systems, Terry Tidwell

PDF

High Speed Networking In The Multi-Core Era, Benjamin Wun

Theses/Dissertations from 2010

PDF

A Geometric Approach for Deciphering Protein Structure from Cryo-EM Volumes, Sasakthi Abeysinghe

PDF

Split and Merge Functions for Supporting Multiple Processing Pipelines in Mercury BLASTN
Jwalant Ahir, Jeremy Buhler, and Roger D. Chamberlain
Technical Report

Abstract:

Biosequence similarity search is an important application in computational biology. Mercury BLASTN, an FPGA-based implementation of BLAST for DNA, is one of the alternatives for fast DNA sequence comparison. The re-design of BLAST into a streaming application combined with a high-throughput hardware pipeline have enabled Mercury BLAST to emerge as one of the fastest implementations of bio-sequence similarity search. This performance can be further enhanced by exploiting the data-level parallelism present within the application. Here we present a multiple FPGA-based Mercury BLASTN design in order to double the speed and... Read More

PDF

Modeling And Dynamic Resource Allocation For High Definition And Mobile Video Streams, Abdel-Karim Al-Tamimi

PDF

Sorting as a Streaming Application Executing on Chip Multiprocessors
Roger D. Chamberlain, Greg A. Galloway, and Mark A. Franklin
Technical Report

Abstract:

Expressing concurrency in applications has always been a difficult and error-prone endeavor, yet effective utilization of multi-core processors requires that the concurrency in applications be understood. One approach to the expression of concurrency is streaming, which has shown real promise as a safe and effective method for many application classes. Here, we express a classic problem, sorting, in the streaming paradigm and explore the implications of various algorithm and architectural design parameters on the performance of the application.

... Read More

PDF

Towards Real-time Wireless Sensor Networks, Octav Chipara

PDF

Against All Probabilities: A modeling paradigm for streaming applications that goes against common notions
Rahav Dor
Technical Report

Abstract:

Hardware and software design requires the right portion of skills and mental faculties. The design of a good system is an exercise in rational thinking, engineering, and art. The design process is further complicated when we aspire to build systems that exploit parallelism or are targeted to be deployed on architecturally diverse computing devices, FPGAs or GPUs to name just a few. The need to develop systems that can take advantage of computing devices beyond general purpose CPUs is real. There are several application domains and research efforts that will... Read More

PDF

A Scalable Method for Solving High-Dimensional Continuous POMDPs Using Local Approximation
Tom Erez and William D. Smart
Technical Report

Abstract:

Partially-Observable Markov Decision Processes (POMDPs) are typically solved by finding an approximate global solution to a corresponding belief-MDP. In this paper, we offer a new planning algorithm for POMDPs with continuous state, action and observation spaces. Since such domains have an inherent notion of locality, we can find an approximate solution using local optimization methods. We parameterize the belief distribution as a Gaussian mixture, and use the Extended Kalman Filter (EKF) to approximate the belief update. Since the EKF is a first-order filter, we can marginalize over the observations analytically.... Read More

PDF

On Motion Parameterizations in Image Sequences from Fixed Viewpoints, Manfred Georg

PDF

Global Constructive Optimization of Vascular Systems
Manfred Georg, Tobias Preusser, and Horst K. Hahn
Technical Report

Abstract:

We present a framework for the construction of vascular systems based on optimality principles of theoretical physiology. Given the position and flow distribution of end points of a vascular system, we construct the topology and positions of internal nodes to complete the vascular system in a realistic manner. Optimization is driven by intravascular volume minimization with constraints derived from physiological principles. Direct optimization of a vascular system, including topological changes, is used instead of simulating vessel growth. A good initial topology is found by extracting key information from a previously... Read More

PDF

Toward a Two-Tier Clinical Warning System for Hospitalized Patients
Gregory Hackmann, Minmin Chen, Octav Chipara, Chenyang Lu, Yixin Chen, Marin Kollef, and Thomas C. Bailey
Technical Report

Abstract:

Clinical study has found early detection and intervention to be essential for preventing clinical deterioration in patients at general hospital units. In this paper, we envision a two-tiered early warning system designed to identify the signs of clinical deterioration and provide early warning of serious clinical events. The first tier of the system automatically identifies patients at risk of clinical deterioration from existing electronic medical record databases. The second tier performs real-time clinical event detection based on real-time vital sign data collected from on-body wireless sensors attached to those high-risk... Read More

PDF

The Design and Implementation of MCFlow: a Real-time Multi-core Aware Middleware for Dependent Task Graphs
Huang-Ming Huang, Christopher Gill, and Chenyang Lu
Technical Report

Abstract:

Modern computer architectures have evolved from uni-processor platforms to multi-processor and multi-core plat- forms, but traditional real-time distributed middleware such as RT-CORBA has not kept pace with that evolution. To address those issues, this paper describes the design and implementation of MCFlow, a new real-time distributed middleware for dependent task graphs running on multi-core platforms. MCFlow provides the following contributions to the state of the art in real-time middleware: (1) it provides an efficient C++ based component model through which computations can be configured flexibly for execution within a single... Read More

PDF

Parallelization of dynamic programming recurrences in computational biology, Arpith Jacob

PDF

An Inexpensive Robot Platform for Teleoperation and Experimentation
Daniel A. Lazewatsky and William D. Smart
Technical Report

Abstract:

Most commercially-available robots are either aimed at the research community, or are designed with a single purpose in mind. The extensive hobbyist community has tended to focus on the hardware and the low-level software aspects. We claim that there is a need for a low-cost, general-purpose robot, accessible to the hobbyist community, with sufficient computation and sensing to run ``research-grade'' software. In this paper, we describe the design and implementation of such a robot. We explicitly outline our design goals, and show how a capable robot can be assembled from... Read More

PDF

Cloud Computing for Scalable Planning by Stochastic Search
Qiang Lu, You Xu, Ruoyun Huang, and Yixin Chen
Technical Report

Abstract:

Graph search has been employed by many AI techniques and applications. A natural way to improve the efficiency of search is to utilize ad- vanced, more powerful computing platforms. However, expensive computing infrastructures, such as supercomputers and large-scale clusters, are traditionally available to only a limited number of projects and researchers. As a results, most AI applications, with access to only commodity com- puters and clusters, cannot benefit from the efficiency improvements of high-performance parallel search algorithms. Cloud computing provides an attractive, highly accessible alternative to other traditional high- performance... Read More

PDF

An Empirical Analysis on Point-wise Machine Learning Techniques using Regression Trees for Web-search Ranking, Ananth Mohan

PDF

Performance Tuning of Streaming Applications via Search-space Decomposition
Shobana Padmanabhan, Roger D. Chamberlain, and Yixin Chen
Technical Report

Abstract:

High-performance streaming applications are typically pipelined and deployed on architecturally diverse (hybrid)systems. Developers of such applications are interested in customizing components used, so as to benefit application performance. We present an efficient and automatic technique for design-space exploration of applications in this problem domain. We solve performance tuning as an optimization problem by formulating cost functions using results from queueing theory. This results in a mixed-integer nonlinear optimization problem which is NP-hard. We reduce the search complexity by decomposing the search space. We have developed a domain-specific decomposition technique using... Read More

PDF

Optimal Design-space Exploration of Streaming Applications
Shobana Padmanabhan, Yixin Chen, and Roger D. Chamberlain
Technical Report

Abstract:

Many embedded and scientific applications are frequently pipelined asynchronously and deployed on architecturally diverse systems to meet performance requirements and resource constraints. We call such pipelined applications streaming applications. Typically, there are several design parameters in the algorithms and architectures used that, when customized, impact the tradeoff between different metrics of application performance as well as resource utilization. Automatic exploration of this design space is the goal of this research. When using architecturally diverse systems to accelerate streaming applications, the design search space is often complex. We present a global... Read More

PDF

Multi-Tier Diversified Service Architecture for Internet 3.0: The Next Generation Internet
Subharthi Paul, Raj Jain, Jianli Pan, and Chakchai So-in
Technical Report

Abstract:

The next generation Internet needs to support multiple diverse application contexts. In this paper, we present Internet 3.0, a diversified, multi-tier architecture for the next generation Internet. Unlike the current Internet, Internet 3.0 defines a new set of primitives that allows diverse applications to compose and optimize their specific contexts over resources belonging to multiple ownerships. The key design philosophy is to enable diversity through explicit representation, negotiation and enforcement of policies at the granularity of network infrastructure, compute resources, data and users. The basis of the Internet 3.0 architecture... Read More

PDF

Priority Assignment for Real-Time Flows in WirelessHART Sensor-Actuator Networks
Abusayeed Saifullah, You Chenyang, and Yixin Chen
Technical Report

Abstract:

Recent years have witnessed the adoption of wireless sensor-actuator networks as a communication infrastructure for process control applications. An important enabling technology for industrial process control is WirelessHART, an open wireless sensor-actuator network standard specifically developed for process industries. A key challenge faced byWirelessHART networks is to meet the stringent real-time communication requirements imposed by feedback control systems in process industries. Fixed priority scheduling, a popular scheduling policy in real-time networks, has recently been shown to be an effective real-time transmission scheduling policy in WirelessHART networks. Priority assignment has a... Read More

Real-Time Scheduling for WirelessHART Networks
Abusayeed Saifullah, Chenyang Lu, You Xu, and Yixin Chen
Technical Report

Abstract:

WirelessHART is an open wireless sensor-actuator network standard for industrial process monitoring and control that requires real-time data communication between sensor and actuator devices. Salient features of a WirelessHART network include a centralized network management architecture, multi-channel TDMA transmission, redundant routes, and avoidance of spatial reuse of channels for enhanced reliability and real-time performance. This paper makes several key contributions to real-time transmission scheduling in WirelessHART networks: (1) formulation of the end-to-end real-time transmission scheduling problem based on the characteristics of WirelessHART; (2) proof of NP-hardness of the problem; (3)... Read More

PDF

End-to-End Delay Analysis for Fixed Priority Scheduling in WirelessHART Networks
Abusayeed Saifullah, You Xu, Chenyang Lu, and Yixin Chen
Technical Report

Abstract:

The WirelessHART standard has been specifically designed for real-time communication between sensor and actuator devices for industrial process monitoring and control. End-to-end communication delay analysis for WirelessHART networks is required for acceptance test of real-time data flows from sensors to actuators and for workload adjustment in response to network dynamics. In this paper, we map the scheduling of real-time periodic data flows in a WirelessHART network to real-time multiprocessor scheduling. We, then, exploit the response time analysis for multiprocessor scheduling and propose a novel method for the end-to-end delay analysis... Read More

PDF

ARCH: Practical Channel Hopping for Reliable Home-Area Sensor Networks
Mo Sha, Gregory Hackmann, and Chenyang Lu
Technical Report

Abstract:

Home area networks (HANs) promise to enable sophisticated home automation applications such as smart energy usage and assisted living. However, recent empirical study of HAN reliability in real-world residential environments revealed significant challenges to achieving reliable performance in the face of significant and variable interference from a multitude of coexisting wireless devices. We propose the Adaptive and Robust Channel Hopping (ARCH) protocol: a lightweight receiveroriented protocol which handles the dynamics of residential environments by reactively channel hopping when channel conditions have degraded. ARCH has several key features. First, ARCH is... Read More

PDF

Multi-Channel Reliability and Spectrum Usage in Real Homes: Empirical Studies for Home-Area Sensor Networks
Mo Sha, Gregory Hackmann, and Chenyang Lu
Technical Report

Abstract:

Home area networks (HANs) consisting of wireless sensors have emerged as the enabling technology for important applications such as smart energy and assisted living. A key challenge faced by HANs is maintaining reliable operation in real-world residential environments. This paper presents two in-depth empirical studies on the wireless channels in real homes. The spectrum study analyzes the spectrum usage in the 2.4 GHz band where wireless sensor networks based on the IEEE 802.15.4 standard must coexist with existing wireless devices. We characterize the ambient wireless environment in six apartments through... Read More

PDF

What do Collaborations with the Arts Have to Say About Human-Robot Interaction?
William D. Smart, Annamaria Pileggi, and Leila Takayama
Technical Report

Abstract:

This is a collection of papers presented at the workshop "What Do Collaborations with the Arts Have to Say About HRI", held at the 2010 Human-Robot Interaction Conference, in Osaka, Japan.

PDF

An Environment for Stroke Therapy Game Authoring, Simon Tam

PDF

Optimal Time Utility Based Scheduling Policy Design for Cyber-Physical Systems
Terry Tidwell, Robert Glaubius, Christopher D. Gill, and William D. Smart
Technical Report

Abstract:

Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, but designing utility-aware scheduling policies using them is an open research problem. In particular, optimal utility accrual scheduling design is needed for real-time cyber-physical domains. In this paper we design optimal utility accrual scheduling policies for cyber-physical systems with periodic, non-preemptable tasks that run with stochastic duration. These policies are derived by solving a Markov Decision Process... Read More

PDF

Abstractions and Algorithms for Control of Extensible and Heterogeneous Virtualized Network Infrastructures, Charles Wiseman

RT-Xen: Real-Time Virtualization Based on Fixed-Priority Hierarchical Scheduling
Sisu Xi, Justin Wilson, Chenyang Lu, and Christopher Gill
Technical Report

Abstract:

The ability to build systems of systems is vital to the real-time community as we endeavor to build increasingly sophisticated systems. Subsystems must be modular and isolated to ensure desired real-time performance when assembled by the system integrator. While virtualization has gained broad adoption and success for system integration in non-real-time domains, no existing virtual machine manager is designed to enforce real-time performance. On the other hand, while a rich body of promising theories on hierarchical real-time scheduling algorithms has been proposed in the literature to support composable real-time performance... Read More

Research from 2009

PDF

Radio Mapping for Indoor Environments
Octav Chipara, Gregory Hackmann, Chenyang Lu, and William D. Smart
Technical Report

Abstract:

The efficient deployment and robust operation of many sensor network applications depend on deploying relays to ensure wireless coverage. Radio mapping aims to predict network coverage based on a small number of link measurements from sampled locations. Radio mapping is particularly challenging in complex indoor environments where walls significantly affect radio signal propagation. This paper makes the following key contributions to indoor radio mapping. First, our empirical study in an office building identifies a wall-classification model as the most effective model for indoor environments due to its balance between model... Read More

PDF

Reliable Patient Monitoring: A Clinical Study in a Step-down Hospital Unit
Octav Chipara, Chenyang Lu, Thomas C. Bailey, and Gruia-Catalin Roman
Technical Report

Abstract:

This paper presents the design, deployment, and empirical study of a wireless clinical monitoring system that collects pulse and oxygen saturation readings from patients. The primary contribution of this paper is an in-depth clinical trial that assesses the feasibility of wireless sensor networks for patient monitoring in general (non-ICU) hospital units. The trial involved 32 patients monitored in a step-down cardiology unit at Barnes-Jewish Hospital, St. Louis. During a total of 31 days of monitoring, the network achieved high reliability (median 99.92%, range 95.21% - 100%). The overall reliability of... Read More

PDF

Adaptive Middleware for Resource-Constrained Mobile Ad Hoc and Wireless Sensor Networks, Chien-Liang Fok

PDF

Adaptive Service Provisioning for Wireless Sensor Networks
Chien-Liang Fok, Gruia-Catalin Roman, and Chenyang Lu
Technical Report

Abstract:

Service provisioning has gained significant attention as a promising programming model for heterogeneous wireless sensor networks. Its key idea is to exploit the decoupling of service providers and consumers to enable platform-independent applications that are dynamically bound to platform-specific services. We explore novel adaptive service binding strategies that are able to cope with network dynamics and to promote energy conservation. To achieve this goal, we developed policies and algorithms that automatically switch providers in response to network topology changes and adapt application behavior when opportunities for energy savings surface. The... Read More

PDF

Enhanced Coordination in Sensor Networks through Flexible Service Provisioning
Chien-Liang Fok, Gruia-Catalin Roman, and Chenyang Lu
Technical Report

Abstract:

Heterogeneous wireless sensor networks represent a challenging programming environment. Servilla addresses this by offering a new middleware framework that provides service provisioning. Using Servilla, developers can construct platform-independent applications over a dynamic set of devices with diverse computational resources and sensors. A salient feature of Servilla is its support for dynamic discovery and binding to local and remote services, which enables flexible and energy-efficient in-network collaboration among heterogeneous devices. Furthermore, Servilla provides a modular middleware architecture that can be easily tailored for devices with a wide range of resources, allowing... Read More

PDF

Feedback Thermal Control for Real-time Systems
Yong Fu, Nicholas Kottenstette, Yingming Chen, Chenyang Lu, Xenofon D. Koutsoukos, and Hongan Wang
Technical Report

Abstract:

Thermal control is crucial to real-time systems as excessive processor temperature can cause system failure or unacceptable performance degradation due to hardware throttling. Real-time systems face significant challenges in thermal management as they must avoid processor overheating while still delivering desired real-time performance. Furthermore, many real-time systems must handle a broad range of uncertainties in system and environmental conditions. To address these challenges, this paper presents Thermal Control under Utilization Bound (TCUB), a novel thermal control algorithm specifically designed for real-time systems. TCUB employs a feedback control loop that dynamically... Read More

PDF

Scheduling Policy Design using Stochastic Dynamic Programming, Robert Glaubius

PDF

Scalable Scheduling Policy Design for Open Soft Real-Time Systems
Robert Glaubius, Terry Tidewell, Braden Sidoti, David Pilla, Justin Meden, Christopher Gill, and William D. Smart
Technical Report

Abstract:

Open soft real-time systems, such as mobile robots, must respond adaptively to varying operating conditions, while balancing the need to perform multiple mission specific tasks against the requirement that those tasks complete in a timely manner. Setting and enforcing a utilization target for shared resources is a key mechanism for achieving this behavior. However, because of the uncertainty and non-preemptability of some tasks, key assumptions of classical scheduling approaches do not hold. In previous work we presented foundational methods for generating task scheduling policies to enforce proportional resource utilization for... Read More

PDF

Scheduling Design with Unknown Execution Time Distributions or Modes
Robert Glaubius, Terry Tidwell, Christopher Gill, and William D. Smart
Technical Report

Abstract:

Open soft real-time systems, such as mobile robots, experience unpredictable interactions with their environments and yet must respond both adaptively and with reasonable temporal predictability. Because of the uncertainty inherent in such interactions, many of the assumptions of the real-time scheduling techniques traditionally used to ensure predictable timing of system actions do not hold in those environments. In previous work we have developed novel techniques for scheduling policy design where up-front knowledge of execution time distributions can be used to produce both compact representations of resource utilization state spaces and... Read More

PDF

Non-programmers Identifying Functionality in Unfamiliar Code: Strategies and Barriers
Paul Gross and Caitlin Kelleher
Technical Report

Abstract:

Source code on the web is a widely available and potentially rich learning resource for non-programmers. However, unfamiliar code can be daunting to end-users without programming experience. This paper describes the results of an exploratory study in which we asked non-programmers to find and modify the code responsible for specific functionality within unfamiliar programs. We present two interacting models of how non-programmers approach this problem: the Task Process Model and the Landmark-Mapping model. Using these models, we describe code search strategies non-programmers employed and the difficulties they encountered. Finally, we... Read More

PDF

Design And Evaluation of Flexibility-Based Structural Damage Localization Using Wireless Sensor Networks, Weijun Guo

PDF

Performance-Engineered Network Overlays for High Quality Interaction in Virtual Worlds
Mart Haitjema, Ritun Patney, Jon Turner, Charlie Wiseman, and John DeHart
Technical Report

Abstract:

Overlay hosting systems such as PlanetLab, and cloud computing environments such as Amazon’s EC2, provide shared infrastructures within which new applications can be developed and deployed on a global scale. This paper ex-plores how systems of this sort can be used to enable ad-vanced network services and sophisticated applications that use those services to enhance performance and provide a high quality user experience. Specifically, we investigate how advanced overlay hosting environments can be used to provide network services that enable scalable virtual world applications and other large-scale distributed applications requiring... Read More

PDF

Globally Clocked Magnetic Logic Circuits
Michael Hall, Albrecht Jander, Roger D. Chamberlain, and Pallavi Dhagat
Technical Report

Abstract:

Magnetic spin valve devices enable the design of logic and memory elements that are suitable for use when constructing digital systems. A master-slave flip-flop design is proposed that can be clocked using an externally applied global magnetic field. With an external global clock, the digital system no longer needs to deliver the clock on-chip, thereby eliminating the need for a clock distribution network. We assess the power, area, and speed implications associated with the ability to eliminate the clock distribution network on a hybrid CMOS-magnetologic digital system.

... Read More

PDF

The Design and Performance of Cyber-Physical Middleware for Real-Time Hybrid Structural Testing
Huang-Ming Huang, Xiuyu Gao, Terry Tidewell, and Christopher Gill
Technical Report

Abstract:

Real-time hybrid testing of civil structures, in which computational models and physical components must be integrated with high fidelity at run-time represents a grand challenge in the emerging area of cyber-physical systems. Actuator dynamics, complex interactions among computers and physical components, and computation and communication delays all must be managed carefully to achieve accurate tests. To address these challenges, we have developed a novel middleware for integrating cyber and physical components flexibly and with suitable timing behavior within a Cyber-physical Instrument for Real-time hybrid Structural Testing (CIRST). This paper makes... Read More

PDF

Throughput-optimal systolic arrays from recurrence equations
Arpith C. Jacob, Jeremy D. Buhler, and Roger D. Chamberlain
Technical Report

Abstract:

Many compute-bound software kernels have seen order-of-magnitude speedups on special-purpose accelerators built on specialized architectures such as field-programmable gate arrays (FPGAs). These architectures are particularly good at implementing dynamic programming algorithms that can be expressed as systems of recurrence equations, which in turn can be realized as systolic array designs. To efficiently find good realizations of an algorithm for a given hardware platform, we pursue software tools that can search the space of possible parallel array designs to optimize various design criteria. Most existing design tools in this area produce... Read More

PDF

Efficient Tracking of Many Objects in Structured Environments
Nathan Jacobs, Michael Dixon, Scott Satkin, and Robert Pless
Technical Report

Abstract:

We consider the special case of tracking objects in highly structured scenes. In the context of vehicle tracking in urban environments, we offer a fully automatic, end-to-end system that discovers and parametrizes the lanes along which vehicles drive, then uses just these pixels to simultaneously track dozens of objects. This system includes a novel active contour energy function used to parametrize the lanes of travel based only on the accumulation of spatio-temporal image derivatives, and a tracking algorithm that exploits longer temporal constraints made possible by our compact data representation;... Read More