Computer Engineering Commons^™

The Design And Implementation Of Mcflow: A Real-Time Multi-Core Aware Middleware For Dependent Task Graphs, Huang-Ming Huang, Christopher Gill, Chenyang Lu

All Computer Science and Engineering Research

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 core, across cores of a common host, or spanning multiple …

What Do Collaborations With The Arts Have To Say About Human-Robot Interaction?, William D. Smart, Annamaria Pileggi, Leila Takayama

All Computer Science and Engineering Research

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.

Multi-Tier Diversified Service Architecture For Internet 3.0: The Next Generation Internet, Subharthi Paul, Raj Jain, Jianli Pan, Chakchai So-In

All Computer Science and Engineering Research

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 is a generalized three-tier object model. The bottom tier consists …

Cloud Computing For Scalable Planning By Stochastic Search, Qiang Lu, You Xu, Ruoyun Huang, Yixin Chen

All Computer Science and Engineering Research

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 computing platforms. In this paper, we first show that the …

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

All Computer Science and Engineering Research

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 formulation of the scheduling problem. We use this formulation to …

A Scalable Method For Solving High-Dimensional Continuous Pomdps Using Local Approximation, Tom Erez, William D. Smart

All Computer Science and Engineering Research

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. By using feedback control and state estimation during policy execution, …

Atomic Transfer For Distributed Systems, Haraldur Darri Thorvaldsson

McKelvey School of Engineering Graduate Student Theses & Dissertations

Building applications and information systems increasingly means dealing with concurrency and faults stemming from distribution of system components. Atomic transactions are a well-known method for transferring the responsibility for handling concurrency and faults from developers to the software's execution environment, but incur considerable execution overhead. This dissertation investigates methods that shift some of the burden of concurrency control into the network layer, to reduce response times and increase throughput. It anticipates future programmable network devices, enabling customized high-performance network protocols.

We propose Atomic Transfer (AT), a distributed algorithm to prevent race conditions due to messages crossing on a path of …

Augmented Lagrangian Algorithms Under Constraint Partitioning, You Xu, Yixin Chen

All Computer Science and Engineering Research

We present a novel constraint-partitioning approach for solving continuous nonlinear optimization based on augmented Lagrange method. In contrast to previous work, our approach is based on a new constraint partitioning theory and can handle global constraints. We employ a hyper-graph partitioning method to recognize the problem structure. We prove global convergence under assumptions that are much more relaxed than previous work and solve problems as large as 40,000 variables that other solvers such as IPOPT [11] cannot solve.

Geodesic Grassfire For Computing Mixed-Dimensional Skeletons, Lu Liu, Tao Ju

All Computer Science and Engineering Research

Skeleton descriptors are commonly used to represent, understand and process shapes. While existing methods produce skeletons at a fixed dimension, such as surface or curve skeletons for a 3D object, often times objects are better described using skeleton geometry at a mixture of dimensions. In this paper we present a novel algorithm for computing mixed-dimensional skeletons. Our method is guided by a continuous analogue that extends the classical grassfire erosion. This analogue allows us to identify medial geometry at multiple dimensions, and to formulate a measure that captures how well an object part is described by medial geometry at a …

The Virtual Network Scheduling Problem For Heterogeneous Network Emulation Testbeds, Charlie Wisemen, Jonathan Turner

All Computer Science and Engineering Research

Network testbeds such as Emulab and the Open Network Laboratory use virtualization to enable users to define end user virtual networks within a shared substrate. This involves mapping users' virtual network nodes onto distinct substrate components and mapping virtual network links onto substrate paths. The mappings guarantee that different users' activities can not interfere with one another. The problem of mapping virtual networks onto a shared substrate is a variant of the general graph embedding problem, long known to be NP-hard. In this paper, we focus on a more general version of the problem that supports advance scheduling of virtual …

Online Bayesian Analysis, Ruibin Xi, Yongjin Kim, Nan Lin, Yixin Chen, Gruia-Catalin Roman

All Computer Science and Engineering Research

In the last few years, there has been active research on aggregating advanced statistical measures in multidimensional data cubes from partitioned subsets of data. In this paper, we propose an online compression and aggregation scheme to support Bayesian estimations in data cubes based on the asymptotic properties of Bayesian statistics. In the proposed approach, we compress each data segment by retaining only the model parameters and a small amount of auxiliary measures. We then develop an aggregation formula that allows us to reconstruct the Bayesian estimation from partitioned segments with a small approximation error. We show that the Bayesian estimates …

Efficient Tracking Of Many Objects In Structured Environments, Nathan Jacobs, Michael Dixon, Scott Satkin, Robert Pless

All Computer Science and Engineering Research

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; we believe both of these may be of independent interest. …

Throughput-Optimal Systolic Arrays From Recurrence Equations, Arpith C. Jacob, Jeremy D. Buhler, Roger D. Chamberlain

All Computer Science and Engineering Research

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 a design that is latency-space optimal. However, we instead wish …

Supercharged Planetlab Platform Architecture, Jonathan Turner, Patrick Crowley, John Dehart, Mart Haitjema, Fred Kuhns Kuhns, Ritun Patney, Michael Wilson, Charlie Wiseman, David Zar

All Computer Science and Engineering Research

This report describes the Supercharged Planetlab Platform (SPP), a system designed as a prototype of an internet-scale overlay hosting platform. Overlay networks have become an important vehicle for delivering Internet applications. Overlay network nodes are typically implemented using general purpose servers or clusters. The SPP offers a more integrated architecture, combining general-purpose servers with high performance Network Processor (NP) subsystems. SPP nodes have recently been deployed as part of the Global Environment for Network Innovation (GENI) and are available for use by research users.

Submodular Utility Optimization In Sensor Networks For Capacity Constraints, You Xu, Yixin Chen, Chenyang Lu, Sangeeta Bhattacharya, Abu Saifullah

All Computer Science and Engineering Research

With the fast development of wireless sensor network (WSN) technologies, WSNs have widely shifted from a specialized platform for a single application to an integrated infrastructure supporting multiple applications. It is hence a critical problem to allocate multiple applications to multiple sensors in order to maximize user utility subject to various resource constraints. The resulting constrained optimization problem is difficult since it is discrete, nonlinear, and not in closed-form. In this report, we develop an efficient optimization algorithm with rigorous approximation bounds for submodular monotonic optimization with multiple knapsack constraints. Based on a variance reduction formulation, we prove several important …

Feedback Thermal Control For Real-Time Systems, Yong Fu, Nicholas Kottenstette, Yingming Chen, Chenyang Lu, Xenofon D. Koutsoukos, Hongan Wang

All Computer Science and Engineering Research

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 controls both processor temperature and CPU utilization through task rate …

The Design And Performance Of Cyber-Physical Middleware For Real-Time Hybrid Structural Testing, Huang-Ming Huang, Xiuyu Gao, Terry Tidewell, Christopher Gill

All Computer Science and Engineering Research

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 three main contributions to the state of the art in …

Achieving Coordination Through Dynamic Construction Of Open Workflows ** Please See Wucse-2009-14 **, Louis Thomas, Justin Luner, Grui-Catalin Roman, Christopher Gill

All Computer Science and Engineering Research

Workflows, widely used on the Internet today, typically consist of a graph-like structure that defines the orchestration rules for executing a set of tasks, each of which is matched at run-rime to a corresponding service. The graph is static, specialized directories enable the discovery of services, and the wired infrastructure supports routing of results among tasks. In this paper we introduce a radically new paradigm for workflow construction and execution called open workflow. It is motivated by the growing reliance on wireless ad hoc networks in settings such as emergency response, field hospitals, and military operations. Open workflows facilitate goal-directed …

Design And Evaluation Of A Practical, High Performance Crossbar Scheduler, Jonathan Turner

All Computer Science and Engineering Research

The Least Occupied Output First (LOOFA) scheduler is one of several unbuffered crossbar schedulers that provides strong performance guarantees when operated with a speedup of 2 or more. Because LOOFA requires the computation of a maximal matching, it has been considered too slow for use in systems with link rates of 10 Gb/s or more. This paper studies an approximate variant of LOOFA described briefly in [16]. We introduce a general family of schedulers that allows for partial sorting and that includes the LOOFA scheduler as a special case. We show that all schedulers in this class are work-conserving and …

Enabling A Low-Delay Internet Service Via Built-In Performance Incentives, Maxim Podlesny, Sergey Gorinsky

All Computer Science and Engineering Research

The single best-effort service of the Internet struggles to accommodate divergent needs of different distributed applications. Numerous alternative network architectures have been proposed to offer diversified network services. These innovative solutions failed to gain wide deployment primarily due to economic and legacy issues rather than technical shortcomings. Our paper presents a new simple paradigm for network service differentiation that accounts explicitly for the multiplicity of Internet service providers and users as well as their economic interests in environments with partly deployed new services. Our key idea is to base the service differentiation on performance itself, rather than price. We design …

Partial Order Based Reduction In Planning: A Unifying Theory And New Algorithms, You Xi, Yixin Chen

All Computer Science and Engineering Research

Partial order based reduction (POR) has recently attracted research in planning. POR algorithms reduce search space by recognizing interchangable orders between actions and expanding only a subset of all possible orders during the search. POR has been extensively studied in model checking and proved to be an enabling technique for reducing the search space and costs. Recently, two POR algorithms, including the expansion core (EC) and stratified planning (SP) algorithms, have been proposed. Being orthogonal to the development of accurate heuristic functions, these reduction methods show great potential to improve the planning efficiency from a new perspective. However, it is …

On Unusual Pixel Shapes And Image Motion, Nathan Jacobs, Stephen Schuh, Robert Pless

All Computer Science and Engineering Research

We introduce the integral-pixel camera model, where measurements integrate over large and potentially overlapping parts of the visual field. This models a wide variety of novel camera designs, including omnidirectional cameras, compressive sensing cameras, and novel programmable-pixel imaging chips. We explore the relationship of integral-pixel measurements with image motion and find (a) that direct motion estimation using integral-pixels is possible and in some cases quite good, (b) standard compressive-sensing reconstructions are not good for estimating motion, and (c) when we design image reconstruction algorithms that explicitly reason about image motion, they outperform standard compressive-sensing video reconstruction. We show experimental results …

A Simple Algorithm For Triconnectivity Of A Multigraph, Abusayeed Saifullah, Alper Ungor

All Computer Science and Engineering Research

Vertex-connectivity and edge-connectivity represent the extent to which a graph is connected. Study of these key properties of graphs plays an important role in varieties of computer science applications. Recent years have witnessed a number of linear time 3-edge-connectivity algorithms - with increasing simplicity. In contrast, the state-of-the-art algorithm for 3-vertex-connectivity due to Hopcroft and Tarjan lacks the simplicity in the sense of ease of implementation as well as the number of passes over the graph although its time and space complexity is theoretically linear. In this paper, we propose a linear time reduction from 3-vertex-connectivity to 3-edge- connectivity of …

Defending Against Distributed Denial-Of-Service Attacks With Weight-Fair Router Throttling, Abusayeed Saifullah

All Computer Science and Engineering Research

A high profile internet server is always a target of denial-of-service attacks. In this paper, we propose a novel technique for protecting an internet server from distributed denial-of-service attacks. The defense mechanism is based on a distributed algorithm that performs weight-fair throttling at the upstream routers. The throttling is weight-fair because the traffics destined for the server are controlled increased or decreased ) by the leaky-buckets at the routers based on the number of users connected, directly or through other routers, to each router. To the best of our knowledge, this is the first weight-fair technique for saving an internet …

Architectures For The Future Networks And The Next Generation Internet: A Survey, Subharthi Paul, Jianli Pan, Raj Jain

All Computer Science and Engineering Research

Networking research funding agencies in the USA, Europe, Japan, and other countries are encouraging research on revolutionary networking architectures that may or may not be bound by the restrictions of the current TCP/IP based Internet. We present a comprehensive survey of such research projects and activities. The topics covered include various testbeds for experimentations for new architectures, new security mechanisms, content delivery mechanisms, management and control frameworks, service architectures, and routing mechanisms. Delay/Disruption tolerant networks, which allow communications even when complete end-to-end path is not available, are also discussed.

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

All Computer Science and Engineering Research

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 open soft real-time systems with these properties. However, these methods …

Scheduling Design With Unknown Execution Time Distributions Or Modes, Robert Glaubius, Terry Tidwell, Christopher Gill, William D. Smart

All Computer Science and Engineering Research

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 efficient optimal scheduling policies over those state spaces. This paper …

Enhanced Coordination In Sensor Networks Through Flexible Service Provisioning, Chien-Liang Fok, Gruia-Catalin Roman, Chenyang Lu

All Computer Science and Engineering Research

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 resource-constrained devices to provide services while leveraging the capabilities of …

Volumeviewer: An Interactive Tool For Fitting Surfaces To Volume Data, Ross Sowell, Lu Liu, Tao Ju, Cindy Grimm, Christopher Abraham, Garima Gokhroo, D Low

All Computer Science and Engineering Research

Recent advances in surface reconstruction algorithms allow surfaces to be built from contours lying on non-parallel planes. Such algorithms allow users to construct surfaces of similar quality more efficiently by using a small set of oblique contours, rather than many parallel contours. However, current medical imaging systems do not provide tools for sketching contours on oblique planes. In this paper, we take the first steps towards bridging the gap between the new surface reconstruction technologies and putting those methods to use in practice. We develop a novel interface for modeling surfaces from volume data by allowing the user to sketch …

Robust Sensor Networks In Homes Via Reactive Channel Hopping, Mo Sha, Greg Hackmann, Chenyang Lu

All Computer Science and Engineering Research

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 in deploying robust wireless sensor networks (WSNs) for home automation applications is the need to provide long-term, reliable operation in the face of the varied sources of interference found in typical residential settings. To better understand the channel dynamics in these environments, we performed an in-depth empirical study of the performance of HANs in ten real-life apartments. Our empirical study leads to several key insights into designing robust HANs for residential environments. …