Parallel Performance Project Research Paper

Research Paper

Modeling Load Imbalance and Fuzzy Barriers for Scalable Shared-Memory Multiprocessors
A. E. Eichenberger and S. G. Abraham
Proceeding of the 28th Hawaii International Conference on System Sciences, pp 262-271, January 95.

Abstract

We propose an analytical model that quantifies the overall execution time of a parallel region in the presence of non-deterministic load imbalance introduced by network contention and by random replacement policy in processor caches. We present a novel model that evaluates the expected hit ratio and variance introduced by a cache accessed with a cyclic access stream. We also model the performance improvement of fuzzy barriers, where the synchronization between processors at the end of a parallel region is relaxed. Experiments on a 64-processor KSR system which has random first-level caches confirms the general nature of the analytic results.