Report Number: CSL-TR-87-333
Institution: Stanford University, Computer Systems Laboratory
Title: Managing and measuring two parallel programs on a multiprocessor
Author: Yan, Jerry C
Date: June 1987
Abstract: Research is being conducted to determine how distributed computations can be mapped onto multiprocessors so as to minimize execution time. Instead of employing optimization techniques based on some abstract program/machine models, the approach being investigated here (called "post-game analysis") is based on placement heuristics which utilizes program execution history. Although initial experiments have demonstrated that "post-game analysis" indeed discovered mappings that exhibit significantly shorter execution times than the worst cases for the programs tested, three important issues remain to be addressed: i) the need to evaluate the performance of placement heuristics against the "optimal" speed-up attainable, ii) to find evidence to help explain why these heuristics work and iii) to develop better heuristics by understanding how and why the basic set performed well. Parallel program execution was simulated using "Axe" -- an integrated environment for computation model description, processor architecture specification, discrete-time simulation and automated data collection. Five groups of parameters are measured representing different aspects in the concurrent execution environment: (i) overall measurements, (ii) communication parameters, (iii) cpu utilization, (iv) cpu contention and (v) dependencies between players. Two programs were simulated -- a "pipe-line" of players and a "divide-and-conquer" program skeleton. The results showed that program execution time indeed correlated well with some of the parameters measured. It was also shown that "post-game" analysis achieved close to 96% optimal speed-up for both programs in most cases.
http://i.stanford.edu/pub/cstr/reports/csl/tr/87/333/CSL-TR-87-333.pdf