Responsive Interactive Applications 
by Dynamic Mapping of Activation Trees

Peter A. Dinda
CMU SCS


An interactive application responds to aperiodic user input with
computation that can be expressed as activation trees. By bounding the
execution time of these trees, we can improve the responsiveness of
the application.  The application runs in a typical computing
environment: a group of uncoordinated but measurable hosts
interconnected with a measurable local area network.  The environment
serves a number of independent users and we do not control it.
However, using a remote execution mechanism, we can execute each node
(procedure call) of a tree on any host on the network.  We intend to
exploit this freedom by dynamically mapping nodes to hosts in order to
maximize the number of trees that execute within their allotted time.

Our general approach to this dynamic mapping problem is history-based
prediction using local information.  In essence, the idea is to
monitor the system and the application and use the measurements to
predict how their behaviors will evolve.  Each node is then mapped to
the host which best serves to match the predicted future application
behavior to the predicted future system behavior.  By adapting the
mapping strategy as the activation tree is traversed, we can better
explore the system and handle erroneous predictions.

This talk will focus on two of our current results.  The first is an
extensive statistical analysis of host load traces from a wide variety
of host systems.  We find that load is self-similar and that it
displays epochal behavior.  The second result is a history-based
prediction algorithm that achieves near optimal performance for a
simplified variant of the problem.  Our evaluation approach is based
realistic trace-driven simulation using the load traces.

We are working to extend these results to attack the full dynamic
mapping problem.  Our current focus is on incorporating real
applications and realistic communication delays to our simulation
environment.  In both cases, our approach is to collect, characterize
and use traces.  Ideal application traces would capture activation
trees with nodes annotated with compute requirements and data
references.  We are also working on time series and other statistical
modeling of the traces.