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