BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CSL-TR-76-125
       ENTRY:: December 01, 1994
ORGANIZATION:: Stanford University, Computer Systems Laboratory
       TITLE:: PERFORMANCE BOUNDS FOR PARALLEL PROCESSORS
        TYPE:: Technical Report
      AUTHOR:: Lee, Ruby Bei-Loh
        DATE:: November 1976
       PAGES:: 34
    ABSTRACT:: A general model of computation on a p-parallel processor is
               proposed, distinguishing clearly between the logical
               parallelism (p* processes) inherent in a computation, and the
               physical parallelism (p processors) available in the computer
               organization. This shows the dependence of performance bounds
               on both the computation being executed and the computer
               architecture. We formally derive necessary and sufficient
               conditions for the maximum attainable speedup of a p-parallel
               processor over a uniprocessor to be Sp 2 min(F(p,ln
               p),F(p*,ln p*)), where ln p approximates Hp , the pth.
               harmonic number. We also verify that empirically-derived
               speedups are 0(F(p*,ln p*)). Finally, we discuss related
               performance measures of minimum execution time, maximum
               efficiency and minimum space-time product.
       NOTES:: [Adminitrivia V1/Prg/19941201]
         END:: STAN//CSL-TR-76-125