Engineering Commons^™

Three Dimensional Panoramic Fast Flourescence Imaging Of Cardiac Arryhtymias In The Rabbit Heart, Fujian Qu, Vladimir P. Nikolski, Cindy Grimm, Igor R. Efimov

All Computer Science and Engineering Research

Cardiac high spatio-temporal optical mapping provides a unique opportunity to investigate the dynamics of propagating waves of excitation during ventricular arrhythmia and defibrillation. However, studies using single camera imaging systems are hampered by the inability to monitor electrical activity from the entire surface of the heart. We have developed a three dimensional panoramic imaging system which allows high-resolution and high-dynamic-range optical mapping from the entire surface of the heart. Rabbit hearts (n=4) were Langendorff perfused and imaged by the system during sinus rhythm, epicardial pacing, and arrhythmias. The reconstructed 3D electrical activity provides us with a powerful tool to investigate …

Knuth-Bendix Completion With Modern Termination Checking, Master's Thesis, August 2006, Ian Wehrman

All Computer Science and Engineering Research

Knuth-Bendix completion is a technique for equational automated theorem proving based on term rewriting. This classic procedure is parametrized by an equational theory and a (well-founded) reduction order used at runtime to ensure termination of intermediate rewriting systems. Any reduction order can be used in principle, but modern completion tools typically implement only a few classes of such orders (e.g., recursive path orders and polynomial orders). Consequently, the theories for which completion can possibly succeed are limited to those compatible with an instance of an implemented class of orders. Finding and specifying a compatible order, even among a small number …

A View-Based Deformation Tool-Kit, Master's Thesis, August 2006, Nisha Sudarsanam

All Computer Science and Engineering Research

Camera manipulation is a hard problem since a graphics camera is defined by specifying 11 independent parameters. Manipulating such a high-dimensional space to accomplish specific tasks is difficult and requires a certain amount of expertise. We present an intuitive interface that allows novice users to perform camera operations in terms of the change they want see in the image. In addition to developing a natural means for camera interaction, our system also includes a novel interface for viewing and organizing previously saved views. When exploring complex 3D data-sets a single view is not sufficient. Instead, a composite view built from …

Acceleration Of Gapped Alignment In Blastp Using The Mercury System, Brandon B. Harris

All Computer Science and Engineering Research

Protein databases have grown exponentially over the last decade. This exponential growth has made extracting valuable information from these databases increasingly time consuming. This project presents a new method of accelerating a commonly used program for performing similarity searching on protein databases, BLASTP. This project describes the design and implementation of Mercury BLASTP, a customized hardware accelerated variant of BLASTP. This project focuses on the gapped alignment stage of Mercury BLASTP and provides design details and implementation results.

Design And Analysis Of An Accelerated Seed Generation Stage For Blastp On The Mercury System - Master's Thesis, August 2006, Arpith Jacob

All Computer Science and Engineering Research

NCBI BLASTP is a popular sequence analysis tool used to study the evolutionary relationship between two protein sequences. Protein databases continue to grow exponentially as entire genomes of organisms are sequenced, making sequence analysis a computationally demanding task. For example, a search of the E. coli. k12 proteome against the GenBank Non-Redundant database takes 36 hours on a standard workstation. In this thesis, we look to address the problem by accelerating protein searching using Field Programmable Gate Arrays. We focus our attention on the BLASTP heuristic, building on work done earlier to accelerate DNA searching on the Mercury platform. We …

Auto-Pipe And The X Language: A Toolset And Language For The Simulation, Analysis, And Synthesis Of Heterogeneous Pipelined Architectures, Master's Thesis, August 2006, Eric J. Tyson

All Computer Science and Engineering Research

Pipelining an algorithmis a popularmethod of increasing the performance of many computation-intensive applications. Often, one wants to form pipelines composed mostly of commonly used simple building blocks such as DSP components, simple math operations, encryption, or pattern matching stages. Additionally, one may desire to map these processing tasks to different computational resources based on their relative performance attributes (e.g., DSP operations on an FPGA). Auto-Pipe is composed of the X Language, a flexible interface language that aids the description of complex dataflow topologies (including pipelines); X-Com, a compiler for the X Language; X-Sim, a tool for modeling pipelined architectures based …

Preserving Performance Of Byzantine Fault Tolerant Replica Groups In The Presence Of Malicious Clients, Sajeeva L. Pallemulle, Haraldur D. Thorvaldsson, Kenneth J. Goldman

All Computer Science and Engineering Research

The Castro and Liskov Byzantine Fault Tolerance protocol for replicated state machines (CLBFT) provides a practical means of tolerating arbitrary replica failures in replicated passive data servers. For better performance, CLBFT uses Message Authentication Codes (MAC) instead of public Key cryptography to authenticate messages and preserves replica consistency even in the presence of malicious clients. However, CLBFT is susceptible to potential attacks by malicious clients using corrupted MACs to force replica groups into expensive configuration changes repeatedly. While not affecting correctness, this vulnerability can seriously impair the performance of the replica group. We propose modifications to CLBFT that address this …

Design And Evaluation Of Packet Classification Systems, Doctoral Dissertation, December 2006, Haoyu Song

All Computer Science and Engineering Research

Although many algorithms and architectures have been proposed, the design of efficient packet classification systems remains a challenging problem. The diversity of filter specifications, the scale of filter sets, and the throughput requirements of high speed networks all contribute to the difficulty. We need to review the algorithms from a high-level point-of-view in order to advance the study. This level of understanding can lead to significant performance improvements. In this dissertation, we evaluate several existing algorithms and present several new algorithms as well. The previous evaluation results for existing algorithms are not convincing because they have not been done in …

Manifold Learning For Natural Image Sets, Doctoral Dissertation August 2006, Richard Souvenir

All Computer Science and Engineering Research

The field of manifold learning provides powerful tools for parameterizing high-dimensional data points with a small number of parameters when this data lies on or near some manifold. Images can be thought of as points in some high-dimensional image space where each coordinate represents the intensity value of a single pixel. These manifold learning techniques have been successfully applied to simple image sets, such as handwriting data and a statue in a tightly controlled environment. However, they fail in the case of natural image sets, even those that only vary due to a single degree of freedom, such as a …

Dynamic Resource Management In A Static Network Operating System, Kevin Klues, Vlado Handziski, David Culler, David Gay, Phillip Levis Levis, Chenyang Lu, Adam Wolisz

All Computer Science and Engineering Research

We present novel approaches to managing three key resources in an event-driven sensornet OS: memory, energy, and peripherals. We describe the factors that necessitate using these new approaches rather than existing ones. A combination of static allocation and compile-time virtualization isolates resources from one another, while dynamic management provides the flexibility and sharing needed to minimize worst-case overheads. We evaluate the effectiveness and efficiency of these management policies in comparison to those of TinyOS 1.x, SOS, MOS, and Contiki. We show that by making memory, energy, and peripherals first-class abstractions, an OS can quickly, efficiently, and accurately adjust itself to …

A Thesis On Sketch-Based Techniques For Mesh Deformation And Editing, Raquel Bujans

All Computer Science and Engineering Research

The goal of this research is to develop new and more intuitive ways for editing a mesh from a static camera angle. I present two ways to edit a mesh via a simple sketching system. The first method is a gray-scale editor which allows the user to specify a fall off function for the region being deformed. The second method is a profile editor in which the user can re-sketch a mesh’s profile. Lastly, the types of edits possible will be discussed and our results will be presented.

Unified Power Management In Wireless Sensor Networks, Doctoral Dissertation, August 2006, Guoliang Xing

All Computer Science and Engineering Research

Radio power management is of paramount concern in wireless sensor networks (WSNs) that must achieve long lifetimes on scarce amount of energy. Previous work has treated communication and sensing separately, which is insufficient for a common class of sensor networks that must satisfy both sensing and communication requirements. Furthermore, previous approaches focused on reducing energy consumption in individual radio states resulting in suboptimal solutions. Finally, existing power management protocols often assume simplistic models that cannot accurately reflect the sensing and communication properties of real-world WSNs. We develop a unified power management approach to address these issues. We first analyze the …

A Unified Architecture For Flexible Radio Power Management In Wireless Sensor Networks, Kevin Klues, Guoliang Xing, Chenyang Lu

All Computer Science and Engineering Research

A challenge for many wireless sensor networks is to remain operational for long periods of time on a very limited power supply. While many power management protocols have been proposed, a solution does not yet exist that allows them to be seamlessly integrated into the existing systems. In this paper we study the architectural support required to resolve this issue. We propose a framework that separates sleep scheduling from the basic MAC layer functionality and provide a set of unified interfaces between them. This framework enables different sleep scheduling policies to be easily implemented on top of multiple MAC layers. …

Use Of Gene Expression Profiling And Machine Learning To Understand And Predict Primary Graft Dysfunction, Monika Ray, Sekhar Dharmarajan, Johannes Freudenberg, Weixiong Zhang, Alexander G. Patterson

All Computer Science and Engineering Research

No abstract provided.

Virtualization For A Network Processor Runtime System, Brandon Heller, Jonathan Turner, John Dehart, Patrick Crowley

All Computer Science and Engineering Research

The continuing ossification of the Internet is slowing the pace of network innovation. Network diversification presents one solution to this problem, by virtualizing the network at multiple layers. Diversified networks consist of a shared physical substrate, virtual routers (metarouters), and virtual links (metalinks). Virtualizing routers enables smooth and incremental upgrades to new network services. Our current priority for a diversified router prototype is to enable reserved slices of the network for researchers to perform repeatable, high-speed network experiments. General-purpose processors have well established techniques for virtualization, but do not scale efficiently to multi-gigabit speeds. To achieve these speeds, we employ …

Extending Byzantine Fault Tolerance To Replicated Clients, Ian Wehrman, Sajeeva L. Pallemulle, Kenneth J. Goldman

All Computer Science and Engineering Research

Byzantine agreement protocols for replicated deterministic state machines guarantee that externally requested operations continue to execute correctly even if a bounded number of replicas fail in arbitrary ways. The state machines are passive, with clients responsible for any active ongoing application behavior. However, the clients are unreplicated and outside the fault-tolerance boundary. Consequently, agreement protocols for replicated state machines do not guarantee continued correct execution of long-running client applications. Building on the Castro and Liskov Byzantine Fault Tolerance protocol for unreplicated clients (CLBFT), we present a practical algorithm for Byzantine fault-tolerant execution of long-running distributed applications in which replicated deterministic …

Supporting Collaborative Behavior In Manets Using Workflows, Rohan Sen, Gregory Hackmann, Mart Haitjema, Gruia-Catalin Roman, Gill

All Computer Science and Engineering Research

Groupware activities provide a powerful representation for many collaborative tasks. Today, the technologies that support typical groupware applications often assume a stable wired network infrastructure. The potential for collaboration in scenarios that lack this fixed infrastructure remains largely untapped. Such scenarios include activities on construction sites, wilderness exploration, disaster recovery, and rapid intervention teams. Communication in these scenarios can be supported using wireless ad hoc networks, an emerging technology whose full potential is yet to be understood and realized. In this paper, we consider the fundamental technical issues that need to be addressed in order to introduce groupware concepts into …

A Dyadic Composition To Foster Virtual Team Effectiveness: An Experimental Study, Gamze Karayaz

Engineering Management & Systems Engineering Theses & Dissertations

The importance of effectiveness for virtual teamwork continues to gain momentum as technology and globalization of work accelerate. The implementation of virtual teams provides one approach to enhance competitiveness, overcoming the disadvantages of space and time differences through collaborative technologies. The influence of structure to virtual team performance has not been clearly established in the literature. The purpose of this research study was to investigate the effectiveness of a dyad structured approach for virtual teams using a quasi-experimental research design.

This research investigated four questions related to the influence of structure on virtual team effectiveness related to task performance, communication …

Limit Crossing For Decision Problems, Sharlee Climer, Weixiong Zhang

All Computer Science and Engineering Research

Limit crossing is a methodology in which modified versions of a problem are solved and compared, yielding useful information about the original problem. Pruning rules that are used to exclude portions of search trees are excellent examples of the limit-crossing technique. In our previous work, we examined limit crossing for optimization problems. In this paper, we extend this methodology to decision problems. We demonstrate the use of limit crossing in our design of a tool for identifying K-SAT backbones. This tool is guaranteed to identify all of the backbone variables by solving at most n+1 formulae, where n is the …

Automatic Application-Specific Customization Of Softcore Processor Microarchitecture, Masters Thesis, May 2006, Shobana Padmanabhan

All Computer Science and Engineering Research

Applications for constrained embedded systems are subject to strict runtime and resource utilization bounds. With soft core processors, application developers can customize the processor for their application, constrained by available hardware resources but aimed at high application performance. The more reconfigurable the processor is, the more options the application developers will have for customization and hence increased potential for improving application performance. However, such customization entails developing in-depth familiarity with all the parameters, in order to configure them effectively. This is typically infeasible, given the tight time-to-market pressure on the developers. Alternatively, developers could explore all possible configurations, but being …

Virtualizing Network Processors, Ben Wun, Jonathan Turner, Patrick Crowley

All Computer Science and Engineering Research

This paper considers the problem of virtualizing the resources of a network processor (NP) in order to allow multiple third-parties to execute their own virtual router software on a single physical router at the same time. Our broad interest is in designing such a router capable of supporting virtual networking. We discuss the issues and challenges involved in this virtualization, and then describe specific techniques for virtualizing both the control and data-plane processors on NPs. For Intel IXP NPs in particular, we present a dynamic, macro-based technique for virtualization that allows multiple virtual routers to run on multiple data plane …

A Proposed Architecture For The Geni Backbone Platform, Jonathan Turner

All Computer Science and Engineering Research

The GENI Project (Global Environment for Network Innovation) is a major NSF-sponsored initiative that seeks to create a national research facility to enable experimental deployment of innovative new network architectures on a sufficient scale to enable realistic evaluation. One key component of the GENI system will be the GENI Backbone Platform (GBP) that provides the resources needed to allow multiple experimental networks to co-exist within the shared GENI infrastructure. This report reviews the objectives for the GBP, reviews the key issues that affect its design and develops a detailed reference architecture in order to provide a concrete example for how …

Agilla: A Mobile Agent Middleware For Sensor Networks, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu

All Computer Science and Engineering Research

Agilla is a mobile agent middleware for sensor networks. Mobile agents are special processes that can migrate across sensors. They increase network flexibility by enabling active in-network reprogramming. Neighbor lists and tuple spaces are used for agent coordination. Agilla was originally implemented on Mica2 motes, but has been ported to other platforms. Its Mica2 implementation consumes 41.6KB of code and 3.59KB of data memory. Agents can move five hops in less than 1.1s with over 92% success. Agilla was used to develop multiple applications related to fire detection and tracking, cargo container monitoring, and robot navigation.

Acceleration Of Profile-Hmm Search For Protein Sequences In Reconfigurable Hardware - Master's Thesis, May 2006 , Rahul Pratap Maddimsetty

All Computer Science and Engineering Research

Profile Hidden Markov models are highly expressive representations of functional units, or motifs, conserved across protein sequences. Profile-HMM search is a powerful computational technique that is used to annotate new sequences by identifying occurrences of known motifs in them. With the exponential growth of protein databases, there is an increasing demand for acceleration of such techniques. We describe an accelerator for the Viterbi algorithm using a two-stage pipelined design in which the first stage is implemented in parallel reconfigurable hardware for greater speedup. To this end, we identify algorithmic modifications that expose a high level of parallelism and characterize their …

Fair Efficiency, Or Low Average Delay Without Starvation, Christoph Jechlitschek, Sergey Gorinksky

All Computer Science and Engineering Research

Elastic applications are primarily interested in minimal delay achievable for their messages under current network load. In this paper, we investigate how to transmit such messages over a bottleneck link efficiently and fairly.

The Meta-Theory Of Q_0 In The Calculus Of Inductive Constructions, Master's Thesis, May 2006, Li-Yang Tan

All Computer Science and Engineering Research

The notion of a proof is central to all of mathematics. In the language of formal logic, a proof is a finite sequence of inferences from a set of axioms, and any statement one yields from such a finitistic procedure is called a theorem. For better or for worse, this is far from the form a traditional mathematical proof takes. Mathematicians write proofs that omit routine logical steps, and details deemed tangential to the central result are often elided. These proofs are fuzzy and human-centric, and a great amount of context is assumed on the part of the reader. While …

Control Of Decoherence In Open Quantum Systems, Narayan Ganesan

All Computer Science and Engineering Research

No abstract provided.

Dynamic Conflict-Free Query Scheduling For Wireless Sensor Networks, Octav Chipara, Chenyang Lu, John Stankovic

All Computer Science and Engineering Research

With the emergence of high data rate sensor network applications, there is an increasing demand for high-performance query services in such networks. To meet this challenge, we present Dynamic Conflict-free Query Scheduling (DCQS), a novel scheduling technique for queries in wireless sensor networks. In contrast to earlier TDMA protocols designed for general-purpose networks and workloads, DCQS is specifically designed for query services supporting in-network data aggregation. DCQS has several important features. First, it optimizes the query performance and energy efficiency by exploiting the temporal properties and precedence constraints introduced by data aggregation. Second, it can efficiently adapt to dynamic workloads …

Reusable Models For Timing And Liveness Analysis Of Middleware For Distributed Real-Time And Embedded Systems, Venkita Subramonian, Christopher Gill, Cesar Sanchez, Henny Sipma

All Computer Science and Engineering Research

Distributed real-time and embedded (DRE) systems have stringent constraints on timeliness and other properties whose assurance is crucial to correct system behavior. Formal tools and techniques play a key role in verifying and validating system properties. However, many DRE systems are built using middleware frameworks that have grown increasingly complex to address the diverse requirements of a wide range of applications. How to apply formal tools and techniques effectively to these systems, given the range of middleware configuration options available, is therefore an important research problem. This paper makes three contributions to research on formal verification and validation of middleware-based …

Distributed Utilization Control For Real-Time Clusters With Load Balancing, Yong Fu, Hongan Wang, Chenyang Lu, Ramu S. Chandra

All Computer Science and Engineering Research

Recent years have seen rapid growth of online services that rely on large-scale server clusters to handle high volume of requests. Such clusters must adaptively control the CPU utilizations of many processors in order to maintain desired soft real-time performance and prevent system overload in face of unpredictable workloads. This paper presents DUC-LB, a novel distributed utilization control algorithm for cluster-based soft real-time applications. Compared to earlier works on utilization control, a distinguishing feature of DUC-LB is its capability to handle system dynamics caused by load balancing, which is a common and essential component of most clusters today. Simulation results …