Technical Reports and MS Project Reports

This paper presents the Distributed End-to-end Utiization CONtrol (DEUCON) algorithm. DEUCON can dynamically enforce desired CPU utilizations on all processors in a dis-tributed real-time system despite uncertainties in the system workload. In contrast to earlier centralized control schemes, DEUCON is a distributed control algorithm that is system-atically designed based on the Distributed Model Predictive Control theory. We decompose the global multi-processor utilization control problem into a set of localized subprob-lems, and design a peer-to-peer control structure where each local controller only needs to coordinate with a small number of neighbor ...Read More

This paper proposes the minimum power configuration (MPC) approach to energy conservation in wireless sensor networks. In sharp contrast to earlier research that treats topology control, power-aware routing, and sleep management in isolation, MPC integrates them as a joint optimization prob-lem in which the power configurationof a network consists of a set of active nodes and the transmission powers of the nodes. We show through analysis that the minimum power configu-ration of a network is inherently dependent on the data rates of sources. We propose several approximation algorithms with provable ...Read More

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Fur-thermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to ...Read More

Maximum Boolean satisfiability (max-SAT) is the optimization counterpart of Boolean satisfiability (SAT), in which a variable assignment is sought to satisfy the maximum number of clauses in a logical formula. A branch-and-bound algorithm based on the Davis-Putnam-Logemann-Loveland procedure (DPLL) is one of the most efficient complete algorithms for solving max-SAT. In this paper, We propose and investigate a number of new strategies for max-SAT. Our first strategy is a set of unit propagation rules for max-SAT. As unit propaga-tion is a very efficient strategy for SAT, we show that it ...Read More

The goal of this research is to explore techniques for shading 3D computer generated models using scanned images of actual paint samples. The techniques presented emphasize artistic control of brush stroke texture and color. We first demonstrate how the texture of a paint sample can be separated from its color transition. Four methods, three real-time and one off-line, for producing rendered images from the paint samples are then presented. Finally, we develop metrics for evaluating how well each method achieves our goal in terms of texture similarity, shading correctness, and ...Read More

We describe a new method for determining when an object can be garbage collected. The method does not require marking live objects. Instead, each object X is dynamically associated with a stack frame M, such that X is collectable when M pops. Because X could have been dead earlier, our method is conservative. Our results demonstrate that the method nonetheless identifies a large percentage of collectable objects. The method has been implemented in Sun's Java Virtual Machine interpreter, and results are presented based on this implementation.

In many data mining applications, the size of the database is not only extremely large, it is also growing rapidly. Even for relatively simple searches, the time required to move the data off magnetic media, cross the system bus into main memory, copy into processor cache, and then execute code to perform a search is prohibitive. We are building a system in which a significant portion of the data mining task (i.e., the portion that examines the bulk of the raw data) is implemented in fast hardware, close to the ...Read More

The goal of packet-switched networks has conventionally been delivering data to users. This concept is changing rapidly as current technologies make it possible to build network processing engines that apply intermediary services to data traffic. This trend introduces an extensive range of ways to develop and operate applications by allowing processing services customized for applications' needs at intermediate network users, as it can relieve individuals from the need to acquire, install, and maintain software in end systems to perform required functions. As such network services become more widely used, it ...Read More

The correctness of a real-time system is very much dependent on the time at which a specific task is completed. Hence, satisfying a storage allocation request within bounded time is important. Fragmentation of the heap after repeated allocations and deallocations is a major issue for real-time systems, as most allocators depend on garbage collection for defragmentation of the heap, which might not finish in time to honor deadlines. We present the storage requirement for a defragmentation-free binary-buddy allocator. We also study a localized defragmentation algorithm to satisfy a single allocation ...Read More

Chip Multi-Processors(CMPs) are now available in a variety of systems. They provide the opportunity to achieve high computational performance by exploiting application-level parallelism within a single chip form factor. In the communications environment, network processors (NPs) are often designed around CMP architectures and, in this context, the processors may be used in a pipelined manner. This leads to the issue of scheduling tasks on such processor pipelines. A tool and algorithm called Greedy pipe has been developed that determines the nearly optimal schedules for such multiprocessor pipelines. The tool offers ...Read More

Chip Multi-Processors (CMPs) are now available in a variety of systems and provide the opportunity for achieving high computational performance by exploiting application-level parallelism. In the communications environment, network processors (NPs) are often designed around CMP architectures and in this context the processors may be used in a pipelined manner. This leads to the issue of scheduling tasks on processor pipelines. This paper considers problems associated with determining optimal application task assignments for such pipelines. A system and algorithm called Greedy Pipe is presented and its performance analyzed. The algorithm ...Read More

Typically, when a program executes, it creates objects dynamically and requests storage for its objects from the underlying storage allocator. The patterns of such requests can potentially lead to internal fragmentation as well as external fragmentation. Internal fragmentation occurs when the storage allocator allocates a contiguous block of storage to a program, but the program uses only a fraction of that block to satisfy a request. The unused portion of that block is wasted since the allocator cannot use it to satisfy a subsequent allocation request. External fragmentation, on the ...Read More

Advances in middleware, operating systems, and popular, general-purpose languages have brought the ideal of reasonably-bound execution time closer to developers who need such assurances for real-time and embedded systems applications. Extensions to the Java libraries and virtual machine have been proposed in a real-time Java standard, which provides for specification of release times, execution costs, and deadlines for a restricted class of threads. To use such features, the programmer is required to use unwieldy code constructs to create region-like areas of storage, associate them with execution scopes, and allocate objects ...Read More

We explain how to use simple composition rules to drive an automated, mobile photography system. The composition rules are used to determine both the location for a good photograph, and how to frame that photograph. We describe the composition component in the context of a larger application, a robotic photographer. The robot moves around an area with people in it, opportunistically looking for faces and taking photographs. We describe both how to find faces in the world and how to create “good” photographs of those faces.

With the advent of operating systems and programming languages that can evaluate and guarantee real-time specifications, applications with real-time requirements can be authored in higher-level languages. For example, a version of Java suitable for real-time (RTSJ) has recently reached the status of a reference implementation, and it is likely that other implementations will follow. Analysis to show the feasibility of a given set of tasks must take into account their worst-case execution time, including any storage allocation or deallocation associated with those tasks. In this thesis, we present a hardware-based ...Read More

A complete mapping from genome to proteome would constitute a foundation for genome-based biology and provide targets for pharmaceutical and therapeutic intervention. This is one reason gene structure prediction has been a major subfield of computational biology for over 20 years. Many of the widely used gene prediction systems were developed in the 1990s and are unable to take advantage of the revolution in comparative genomics brought on by the sequencing of the entire genomes of an increasing numbers of vertebrates. Twinscan is a new system for high-throughput gene-structure prediction ...Read More

Limone is a new coordination model and middleware that enables rapid application development for wireless ad hoc networks entailing logical mobility of agents and physical mobility of hosts. Designed to function in open environments, Limone performs automatic agent discovery but filters the results to define for each agent an individualized acquaintance list in accordance with run-time policies that are customizable by the application. This asymmetry among participants represents a new direction in coordination research and is dictated by the need to accommodate settings involving large numbers of agents and hosts ...Read More

This paper presents Limone, a new coordination model that facilitates rapid application development over ad hoc networks consisting of logically mobile agents and physically mobile hosts. Limone assumes an agent-centric perspective on coordination by allowing each agent to define its own acquaintance policy and by limiting all agent-initiated interactions to agents that satisfy the policy. Agents that satisfy this acquaintance policy are stored in an acquaintance list, which is automat-ically maintained by the system. This asymmetric style of coordination allows each agent to focus only on relevant peers. Coordination activi-ties ...Read More

We identify common storage-referencing gestures in Java bytecode and machine-level code, so that a gesture comprising a sequence of storage dereferences can be condensed into a single instruction. Because these gestures access memory in a recognizable pattern, the pattern can be preloaded into and executed by a “smart” memory. This approach can improve program execution time by making memory accesses more efficient, by saving CPU cycles, bus cycles, and power. We introduce a language of valid gesture types and conduct a series of experiments to analyze the characteristics of gestures ...Read More

We describe techniques for identifying and optimizing memory-accessing instruction sequences. We capture a sequence of such instructions, with the goal of sending the sequence as a single instruction from the CPU to a smart memory subsystem (IRAM or PIM). With a software/hardware codesign, the memory-accessing gestures can be rewritten as succinct superoperator instructions, and the gestures themselves could vary at runtime. As a result, the CPU executes fewer instructions and the CPU-memory bus is charged less often, resulting in lower power consumption. Reduction in power can be crucial for constrained, ...Read More

Chip Multi-Processors (CMPs) are now available in a variety of systems and provide the opportunity for achieving high computational performance by exploiting application-level parallelism. In the communications environment, network processors (NPs), designed around CMP architectures, are generally usable in a pipelined manner. This leads to the issue of scheduling tasks on processor pipelines. This paper considers problems associated with determining optimal schedules for such pipelines. A system and algorithm called Greedy Pipe is presented. The algorithm employs a greedy heuristic to schedule tasks derived from multiple application flows on pipelines ...Read More

Common collection objects such as hash tables are included in modern runtime libraries because of their widespread use and efficient implementation. While operating systems and programming languages continue to improve their real-time features, common implementations of hash tables and other collection objects are not necessarily suitable for real-time or embedded-systems. In this paper, we present an algorithm for managing hash tables that is suitable for such systems. The algorithm has been implemented and deployed in place of Java’s Hashtable class. We present evidence of the algorithm’s performance, experimental results documenting ...Read More

We present a system for painting how the appearance of an object changes under different lighting and viewing conditions. The user paints what the object should look like under different lighting conditions (dark, partially dark, fully lit, etc.) and (optionally) different viewing angles. The system renders the object under new lighting conditions and a new viewing angle by combining these paintings. We also provide a technique for constructing texture maps directly from the user’s paintings.

Language support of dynamic storage management simplifies the application programming task immensely. As a result, dynamic storage allocation and garbage collection have become common in general purpose computing. Garbage collection research has led to the development of algorithms for locating program memory that is no longer in use and returning the unused memory to the run-time system for late use by the program. While many programming languages have adopted automatic memory reclamation features, this has not been the trend in Real-Time systems. Many garbage collection methods involve some form of ...Read More

This paper addresses the design and implementation of thin coordination veneers for use in the development of applications over ad hoc wireless networks. A coordination veneer is defined as an adaptation layer that customizes a general-purpose coordination middleware to a particular domain with minimal development effort. This technique allows developers to build highly-tailored coordination models while leveraging established models and middleware. We present three such veneers, the coordination models they embody, and the manner in which they were implemented. The LIME middleware, which supplies tuple space based coordination in the ...Read More

Ad hoc networks are formed opportunistically as mobile devices come within wireless communication range of each other. Since individual devices are typically subject to severe resource limitations, it is both possible and desirable for a device to enhance its functionality by taking advantage (in a cooperative manner) of capabilities available on other devices. Service provision refers to the process by which devices advertise their willingness to offer specific services and discover other of services. This paper describes a service provision model designed specifically for use in ad hoc settings. Security ...Read More

Security is emerging as a growing concern throughout the distributed computing community. Typical solutions entail specialized infrastructure support for authentication, encryption and access control. Mobile applications executing over ad hoc wireless networks present designers with a rather distinct set of security requirements. A totally open setting and limited resources call for lightweight and highly decentralized security solutions. In this paper we propose an approach that relies on extending an existing coordination middleware for mobility (Lime). The need to continue to offer a very simple model of coordination that assures rapid ...Read More

This thesis examines the effects of changing the numerical representation of audio signals in digital hearing aids to minimize power consumption. Within the hearing aid design a majority of the power used is consumed in the many finite impulse response filters. The main processing involved in these filters is a multiply-accumulate function. We examine the power consumption of 12 different multiply-accumulate units that use the following numerical representations: a 16-bit linear representation, a 9-bit logarithmic representation, and 10 different floating-point rep-representations ranging from 9 to 13 bits. A selection of ...Read More

Rate control, in conjunction with congestion control, is important and necessary to maintain both stability of overall network and high quality of individual data transfer flows. In this paper, we study stable rate control algorithms for streaming data, based on control theory. We introduce various control rules to maintain both sending rate and receiver buffer stable. We also propose an adaptive two-state control mechanism to ensure the rate control algorithms are compatible to TCP traffics. Extensive experimental results are shown to demonstrate the effectiveness of the rate control algorithms.

Sensor network presents us many new challenging practical and theoretical problems. This paper is concerned with minimal exposure problem in sensor networks. Exposure, proposed by Megerian and others [3] as a useful metric to describe the sensor coverage of a path in a sensor field, exhibits interesting properties and induces related open problems. In this paper, we present a solution to an open one-sensor exposure problem [2, 3] using variational calculus as our first step in further understanding of the exposure problem in multiple sensor scenarios.

The recent advent of wireless mobile ad hoc networks and sensor networks creates many opportunities and challenges. This thesis explores some of them. In light of new application requirements in such environments, it proposes a new multicast paradigm called spatiotemporal multicast for supporting ad hoc network applications which require both spatial and temporal coordination. With a focus on a special case of spatiotemporal multicast, called mobicast, this work proposes several novel protocols and analyzes their performances. This dissertation also investigates implications of mobility on the classical group membership problem in ...Read More

We propose a new multicast communication paradigm called “spatiotemporal multicast” for supporting applications which require spatiotemporal coordination in wireless sensor networks. In this paper we focus on a special class of spatiotemporal multicast called “mobicast” featuring a message delivery zone that moves at a constant velocity v. The key contributions of this work are: (1) the specification of mobicast and its performance metrics, (2) the introduction of four different mobicast protocols along with the analysis of their performance, (3) the introduction of two topological network compactness metrics for facilitating the ...Read More

This paper presents a novel protocol for a spatiotemporal variant of multicast called mobicast, designed to support message delivery in sensor and mobile ad hoc networks. The spatiotemporal character of mobicast relates to the obligation to deliver a message to all the nodes that will be present at time t in some geographic zone Z, where both the location and shape of the delivery zone are a function of time over some interval (tstart, tend). The protocol, called Face-Aware Routing (FAR), exploits ideas adapted from existing applications of face routing ...Read More

Sensor networks often involve the monitoring of mobile phenomena, which can be facilitated by a spatiotemporal multicast protocol we call “mobicast”. Mobicast is a novel spatiotemporal multicast protocol featuring a delivery zone that evolves over time. Mobicast can in theory provide absolute spatiotemporal delivery guarantees by limiting communication to a mobile forwarding zone whose size is determined by the global worst-case value associated with a compactness metric defined over the geometry of the network. In this work, we first studied the compactness properties of sensor networks with uniform distribution. The ...Read More

SimplePipe is a simulation framework/tool for analyzing performance effects of alternative task allocations in network processors having multiple pipelines where pipeline stages are either processors or dedicated hardware functions. Tasks are defined in terms of sequence of separate C program executions with each sequence representing the functional requirements of a flow, where a flow is defined as the set of packets having the same processing requirements. The assignment of tasks to pipeline stages, selection of number of stages, and determination of processor cache sizes are important designing decisions impacting performance.

Context-awareness is emerging as an important computing paradigm designed to address the special needs of applications that must accommodate or exploit the highly dynamic environments that occur in the presence of physical or logical mobility. A number of formal models are available for reasoning about concurrency. Models designed to capture the specifics of mobility are fewer but still well represented (e.g., Mobile Ambients, π-Calculus, and Mobile UNITY). These models do not, however, provide constructs necessary for explicit modeling of context-aware interactions. This paper builds upon earlier efforts on state-based formal ...Read More

The increasing ubiquity of communicating mobile devices and vastly different mobile application needs have led to the emergence of middleware models for ad hoc networks that simplify application programming. One such system, EgoSpaces, addresses specific needs of individual applications, allowing them to define what data is included in their operating context using declarative specifications constraining properties of data, agents that own the data, hosts on which those agents are running, and attributes of the ad hoc network. In the resulting coordination model, application agents interact with a dynamically changing environment ...Read More

The increasing ubiquity of mobile devices has led to an explosion in the development of applications tailored to the particular needs of individual users. As the research community gains experience in the development of these applications, the need for middleware to simplify such software development is rapidly expanding. Vastly different needs of these various applications, however, have led to the emergence of many different middleware models, each of which approaches the dissemination of contextual information in a distinct way. The EgoSpaces model consists of logically mobile agents that operate over ...Read More

The increasing ubiquity of mobile computing devices has made ad hoc networks everyday occurrences. In these highly dynamic environments, the multitude of devices provides a varied and rapidly changing environment in which applications must learn to operate. Successful end-user applications will not only learn to function in this environment but will take advantage of the variety of information available. Protocols for gathering an application’s contextual information must be built into the network to function in a timely and adaptive fashion. This paper presents a protocol for providing context information to ...Read More

Context-aware computing is characterized by the ability of a software system to continuously adapt its behavior to a changing environment over which it has little or no control. Previous work along these lines presumed a rather narrow definition of context that centered on resources immediately available to the component in question, e.g., communication bandwidth, physical location, etc. This paper explores context-aware computing in the setting of ad hoc networks consisting of numerous mobile hosts interacting with each other opportunistically via transient wireless interconnections. We extend a component’s context to encompass ...Read More

Context-aware mobile applications require constant adaptation to their changing environments. Technological advancements have increased the pervasiveness of mobile computing devices such as laptops, handhelds, cellular phones, and embedded sensors. The sheer amount of context information necessary for adaptation places a heightened burden on application developers as they must manage and utilize vast amounts of data from diverse sources. Facilitating programming in this data-rich environment requires an infrastructure for sensing, collecting, and providing context information to applications. In this paper, we demonstrate the feasibility of providing such an infrastructure. It allows ...Read More

The increased pervasiveness of wireless mobile computing devices draws new attention to the need for coordination among small, networked components. The very nature of the environment requires devices to interact even when they meet unpredictably. Because these networks are often decoupled from a fixed infrastructure, reliance on centralized servers for authentication and access policies is impractical. Access control is crucial in such systems, and applications must directly manipulate and examine access policies because they require full control of their data. In this paper, we explore the essential features of general ...Read More

The emerging mobile computing environment draws new attention to the need for co-ordination among networked components. The very nature of this environment requires parties to interact even when they have never met before, and subsequent encounters are totally unpredictable. Because mobile networks are often decoupled from any fixed network infrastructure, reliance on centralized servers to authenticate agents and to establish data access policies is impractical. Access control is a key component of security in such systems, and application agents must be able to directly manipulate and examine policies because they ...Read More

Recent studies have shown that suitably-designed packet discard policies can dramatically improve the performance of fair queueing mechanisms in internet routers. The Queue State Deficit Round Robin algorithm (QSDRR) preferentially discards from long queues, but in-troduces hysteresis into the discard policy to minimize synchronization among TCP flows. QSDRR provides higher throughput and much better fairness than simpler queueing mech-anisms, such as Tail-Drop, RED and Blue. However, because QSDRR discards packets that have previously been queued, it can signficantly increase the memory bandwidth require-ments of high performance routers. In this paper, ...Read More

Real-time are beginning to appear in advanced, high-level programming languages such as Java. When complemented by a real-time operating system, the Real-Time Specification for Java (RTSJ) offers strong execution constraints for applications developed in Java. While the RTSJ make the basic services of Java such as storage and thread management ready for many real-time applications, the collection objects, and the rest of the application run-time library, cannot be used by RTSJ applications until their run-time properties are examined and modified as necessary to make them suitable for use by real-time ...Read More

This paper presents several methods for shading meshes from scanned paint samples that represent dark to light transitions. Our techniques emphasize artistic control of brush stroke texture and color. We first demonstrate how the texture of the paint sample can be separated from its color gradient. We demonstrate three methods, two real-time and one off-line for producing rendered, shaded images from the texture samples. All three techniques use texture synthesis to generate additional paint samples. Finally, we develop metrics for evaluating how well each method achieves our goal in terms ...Read More

Most modern application programs depend on dynamic storage management to handle allocation and deallocation of memory. Unfortunately conventional software-based storage managers are relatively low performance due to the latency associated with accessing DRAM memory. Consequently, developers of programs with very specialized memory requirements, such a real-time systems, often choose to manage memory manually at the application-code level. This practice can greatly increase performance but it can also significantly complicate the development process. In this thesis we present the design, VHDL implementation and performance evaluation of hardware-based storage manager called the ...Read More

This thesis reports on experience with PCESjava, a collection of tools which we have developed for the purpose of aiding programmers. Particular applications optimize and instrument JAVA bytecode programs. Using these tools, we have successfully identified impediments to real-time performance in a popular JAVA collections object. Our approach here is based on automatic instruction to obtain traces that show paths whose execution time is not reasonably bounded. We also report on the application of our tool to reduce program footprint in JAVA programs by rewriting the bytecodes to occupy less ...Read More

We investigate the impact of numerical representation on the power consumption of digital hearing aids. A fundamental building block, a non-linear amplifier, is implemented using traditional 16-bit linear or customized 9-bit logarithmic and 10-bit floating point numerical representations. An individual channel of a multi-channel hearing aid is constructed, targeting both FPGA and ASIC deployment options. Using signal transition counts in the post-synthesis simulation to model power consumption, we compare the relative power consumption of the non-linear amplifiers, a full hearing aid channel, and the complete hearing aid signal processing for ...Read More

The rather large feature set of current Distributed Object Computing (DOC) middleware can be a liability for certain applications which have a need for only a certain subset of these features but have to suffer performance degradation and code bloat due to all the present features. To address this concern, a unique approach to building fully customizable middleware was undertaken in FACET, a CORBA event channel written using AspectJ. FACET consists of a small, essential core that represents the basic structure and functionality of an event channel into which additional ...Read More