Runtime Optimization of Parallel and Distributed Applications

Parallel and distributed applications are difficult to optimize because their performancedepends on the interactions between distributed tasks and the resources available to each task. In such dynamic and unpredictable settings, compile-time optimizations must be augmented with runtime optimizations. I have explored two approaches to runtime optimization --- deferred program analysis and program adaptation.

Deferred program analysis defers certain parts of compiler analysis, to run-time. In particular, deferring communication analysis to runtime allows efficient parallelization of irregular and adaptive programs. Deferred communication analysis has been implemented in Chaos, a library built by myself and others in the HPSL research group. Deferred dataflow analysis (DDFA) is a another example of deferring program analysis can optimize performance. DDFA dynamically prunes feasible execution paths, allowing it to sharpen optimizations that depend on dataflow information. Overheads are kept low by pre-analyzing regions of the program ahead of time, and stitching these pre-computed results together at runtime.

The second technique, called program adaptation, allows a program to change its behavior in response to changes in available resources. We have demonstrated how adaptalk, an internet chat application, can adapt to changes in network latencies by repositioning the chat server dynamically. Similarly, parallel applications can adapt to memory limitations by performing its communication in stages, ensuring that incoming data does not overflow to disk.