S.G. Abraham, Adv. Comput. Archit. Lab., Michigan Univ., Ann Arbor, MI, USA
Proposes 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 a 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 (Kendall Square Research) system which has random first-level caches confirms the general nature of the analytic results.
Index Terms:
shared memory systems; synchronisation; resource allocation; cache storage; performance evaluation; concurrency control; network contention; fuzzy barriers; scalable shared-memory multiprocessors; overall execution time; parallel region; nondeterministic load imbalance modelling; random replacement policy; processor caches; hit ratio; variance; cyclic access stream; performance improvement; interprocessor synchronization; 64-processor KSR system; Kendall Square Research system; random first-level caches
Citation:
A.E. Eichenberger, S.G. Abraham, "Modeling load imbalance and fuzzy barriers for scalable shared-memory multiprocessors," hicss, pp.262, 28th Hawaii International Conference on System Sciences (HICSS'95), 1995
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb