Report Number: CSL-TR-76-125
Institution: Stanford University, Computer Systems Laboratory
Title: Performance bounds for parallel processors
Author: Lee, Ruby Bei-Loh
Date: November 1976
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.
http://i.stanford.edu/pub/cstr/reports/csl/tr/76/125/CSL-TR-76-125.pdf