Real-Time Fine-grained Adaptivity on Multiprocessors: Acoustic Tracking as a Test Case

Principal Investigator: James H.Anderson
Funding Agency: National Science Foundation
Agency Number: CNS-0408996

Abstract
Two trends are evident in recent work on real-time systems. First, multiprocessor designs are becoming quite common. This is due both to the advent of reasonably priced multiprocessor platforms and also to the prevalence of computation-intensive applications that have pushed beyond the capabilities of singleprocessor systems. Second. applications are emerging that require fine-grained adaptivity, i. e., the ability to react to external events within short time scales by adjusting system parameters. Examples of such applications include systems that track people and machines, many computer-vision systems, and signalprocessing applications such as synthetic aperture imaging. In practice, the most common approach by far for implementing such systems is by overprovisioning hardware resources, and by validating timing requirements through ad-hoc testing. A more formal approach would clearly be desirable. Prior work on formal frameworks for implementing realtime multiprocessor systems has mostly focused on task-partitioning approaches. Unfortunately, online partitioning is often impractical for computation-intensive applications, due to the overhead involved. This is especially problematic for highly-adaptive systems because the addition of a new task, or a change in the timing parameters of an existing task, may necessitate a re-partitioning of the entire system. These observations point to a significant need for research to be conducted on techniques for ensuring timing constraints in highly-adaptive applications implemented on multiprocessor platforms. In this project, it is our goal to fill this need by developing and experimentally evaluating multiprocessor scheduling algorithms that are very flexible in their ability to react to task-set changes, faults, and overload conditions. The proposed research will build upon recent research conducted at UNC on fair multiprocessor scheduling algorithms for real-time systems. Such algorithms are designed to mimic the allocations of an ideal fluid scheduler, which can react instantaneously to task-set changes. In prior work, we developed an efficient fair multiprocessor scheduling algorithm that is optimal under even very lax notions of recurrent execution that allow a task's instantaneous execution rate to deviate significantly from its average or worstcase rate. Such flexibility is critical in the design of highly-adaptive systems. For instance, a change in a task's execution parameters can be modeled as an increase or decrease in its prescribed execution rate. In this project, we propose to extend this prior work by developing mechanisms (i) for efficiently supporting soft-real-time tasks, (ii) for supporting fine-grained adaptation, and (iii) for efficiently synchronizing tasks and supporting intertask communication. In addition, (iv) we will devise mechanisms for determining how and when to adapt by extending prior work on using feedback-control mechanisms to induce adaptations in uniprocessor real-time scheduling algorithms. We propose to evaluate the algorithms we develop by using them to implement a spread-spectrum acoustic tracking system for virtual-reality (VR) applications. The resulting system will be able to track a VR user's hands, elbows, feet, and knees to allow interaction with the virtual environment and proper animation of the user's avatar (virtual representation). We expect this experimental effort to be of independent interest, as it will provide researchers interested in tracking applications with new techniques that can be applied to deploy and analyze their systems. In a broader sense, tracking is a good surrogate for the wide range of highly-adaptive computation-intensive real-time applications that exist.