Competitive execution of sequential programs on a network of shared processors
Sung-Hyun Cho · 2002
The author proposes an alternative to process migration, called competition, to speed up distributed programs in the background on a network of shared processors. Competition protocols are transparent operating system facilities that involve creating multiple instances (called clones) p/sub 1/, p/sub 2/, etc. of a process P on different processors, and making clones "compete", i.e., attempting to guarantee that the output of the clone that is farthest "ahead" is fed to the rest of the computation, and that the entire application's performance tracks that of the clone which is farthest ahead. One clone may be ahead of or behind others depending on the current foreground loads. If for any reason there is variation in the progress of the clones, so that one clone is ahead at some times, but another is ahead at other times, then a set of competing clones may outperform any single copy. The author focuses on sequential programs, but results for sequential programs can be extended to distributed programs because one can speed up a distributed program by speeding up communicating processes in the program. The author shows that competition protocols offer performance benefits that are as good as or better than migration protocols for sequential programs under comparable assumptions. This claim is supported by analytical results and simulation results.