Obtaining Responsiveness In Resource-Variable Environments

This research addresses the problem of building software that can be responsive even in environments with widely variable or unknown resource availability. Application programmers' eorts to ensure responsiveness are rendered increasingly dicult by a number of trends in modern computing environments that increase service variability, including: 1. wide scale sharing of resources, such as distributed le systems, 2. wireless networking for mobile computers, and 3. sporadic inclusion of multimedia in documents. The con uence of these trends calls for broadly applicable programming support to create applications that ensure good responsiveness in the face of widely variable service times at little or no increase in programming eort relative to the existing technology (which cannot provide this level of responsiveness). The work described here provides the design of such support, and furnishes a proof of concept that it is eective where (a) portions of the application can be decomposed into concurrent tasks, and (b) the application can produce and present its results incrementally, i.e., can trade the quality of the response against the delay required to provide it, such as with multi-resolution techniques. The key to this approach is the runtime construction of a global dependence graph that relates tasks to each other through their input and output dependencies. This graph is constructed by an application-independent system with minimal programmer eort, and is used at runtime to provide useful services, including: 1. adjusting resource allocation along the branches of the graph to improve response time for those tasks on which the user is currently focussed, 2. pruning branches of the graph that no longer represent useful work, thus freeing resources for the computations of interest, 3. managing multiple results of improving quality and their storage behind the abstraction of program variables, and 4. synchronizing the execution of threads on new input quality versions according to programmer-specied semantics. The combined eect is that it is easier to write applications that provide good responsiveness across a wide and unpredictable range of service variability.