Rate-Based Scheduling Technology for Latency-Sensitive Graphics Applications

Principal Investigator: James Anderson
Funding Agency: National Science Foundation
Agency Number: CCR-0082866

Abstract
Immersive virtual environments and other highly interactive, real-time graphics applications have stringent latency requirements to ensure a compelling experience. These requirements are usually met by overprovisioning the system's hardware resources (e.g., graphics accelerators and processors), and are then validated through ad-hoc testing. Recent advances in real-time processor scheduling technology could, in theory, serve as the basis for a more analytical approach. Unfortunately, conventional real-time scheduling disciplines are quite rigid and the associated analysis techniques hinge mostly on very pessimistic worst-case scenarios. In addition, these scheduling disciplines are usually implemented only within special-purpose real-time operating systems. For these reasons, real-time scheduling techniques have been largely ignored within the graphics community.

In this project, we propose to develop a real-time scheduling and analysis framework for immersive and other latency-sensitive graphics applications. This framework will extend recent work on rate-based processor scheduling. The framework we develop will allow timing requirements to be specified as average rates and will be highly tolerant of any deviance from specified rates. We will show that this framework can scale to large multiprocessor systems and workstation clusters.

In the proposed scheduling framework, a system is abstractly modeled as a flow graph: each task is a node in the graph, and producer/consumer relationships are represented by edges. We propose to develop analytical techniques for validating an application's rate-based timing properties, and for analyzing latency and memory requirements. While the idea of modeling a real-time system as a flow graph is not new, our work will differ from previous research in that we will be able to analyze complex multiple-processor systems. Moreover, our framework will differ from many previous efforts in that it will be entirely implementable at the user level.

We will use the nanoManipulator system to evaluate our rate-based framework. The nanoManipulator project is developing an improved, natural interface to scanning probe microscopes, including scanning tunneling microscopes and atomic force microscopes. The nanoManipulator couples the microscope to a virtual-reality graphics display and a haptic interface to provide a telepresence system. The nanoManipulator is working tool in daily use that has led to many new results in the study of biology, materials science, carbon nanotubes, and electrical engineering.

The main graphics loop of the existing nanoManipulator system is not multi-threaded, and thus it is quite brittle (changing one part of system can impact other parts that are handled in the same this loop) and its timing properties are difficult to analyze. We propose to develop a fully multi-threaded version of the nanoManipulator using the proposed scheduling framework. For us, the nanoManipulator is an interesting test application because acceptable fidelity is possible only if the system is implemented on multiple processors. For the nanoManipulator project, the pay-off of our work will be added flexibility in deploying and analyzing varying configurations of the system. Using our framework, functionality similar to the current nanoManipulator system should be possible with fewer hardware resources. Indeed, we expect the savings to be as high as tens of thousands of dollars per installation, allowing wider deployment of the system within collaborators' laboratories. For the real-time graphics community, the long-term payoff of this project will be a more analytical approach for realizing timing correctness in graphics systems that does not sacrifice efficiency.