ID:: STAN//CSL-TR-87-333
       ENTRY:: November 08, 1994
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: MANAGING AND MEASURING TWO PARALLEL PROGRAMS ON A
               MULTIPROCESSOR
        TYPE:: Technical Report
      AUTHOR:: Yan, Jerry C
        DATE:: June 1987
       PAGES:: 71
    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.
       NOTES:: [Adminitrivia V1/Prg/19941108]
         END:: STAN//CSL-TR-87-333