Dushyanth Narayanan

Thesis Title: Operating System Support for Mobile Interactive Applications
Degree Type: Ph.D. in Computer Science
Advisor(s): M. Satyanarayanan
Graduated: August 2002

Abstract:

Mobile interactive applications are becoming increasingly important. One such application alone augmented reality has enormous potential in fields ranging from entertainment to aircraft maintenance. Such applications demand good interactive response. However, their environments are resource-poor and turbulent, with frequent and dramatic changes in resource availability. To keep response times bounded, the application and system together must adapt to changing resource conditions.

In this dissertation, I present a new abstraction multi-fidelity computation and claim that it is the right abstraction for adaptation in mobile, interactive applications. I also present an API that allows a mobile interactive application to recast its core functionality as a multi-fidelity computation.

I identify one of the key problems in application adaptation: predicting application performance at any given fidelity. I solve this problem in two steps. History-based prediction predicts application resource demand as a function of fidelity. A resource model then maps application resource demand and system resource supply to performance. History-based prediction is validated through four case studies demonstrating accurate prediction of CPU, memory, network, and energy demand.

I also describe the design and implementation of runtime support for multi-fidelity computations: the overall system architecture as well as each key component. I present four application case studies: of a virtual walkthrough program, a 3-D graphics algorithm, a web browser, and a speech recognizer. In each case, I show how the application uses the multi-fidelity API; that the programming cost of using the API is small; and that the history-based prediction method accurately predicts application resource demand.

In evaluating the system prototype, I ask three questions. First, is adaptation agile in the face of changing load conditions? Second, is the system accurate in choosing the fidelity that best matches the applications' needs? Third, does the system provide substantial benefit compared to the non-adaptive case? I answer these questions through a series of experiments both with synthetic and real workloads. I show that adaptation is agile, accurate, and beneficial in bounding response time despite varying CPU and memory load. I also show that adaptation reduces the variability in response time, providing a more predictable and stable user experience.

Thesis Committee:
M. Satyanarayanan (Chair)
Christos Faloutsos
Randy Pausch
John Wilkes (Hewlett-Packard Laboratories)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Interactive applications, mobile computing, ubiquitous computing, multi-fidelity algorithm, application-aware adaptation, predictive resource management, history-based demand prediction, augmented reality, machine learning