An Evaluation of Parallel Algorithms on Current Memory Consistency Models

G. Cong (USA)


Consistency Models, Parallel Algor ithms, Shared Memory.


Memory consistency model is crucial to the performance of shared-memory multiprocessors, and in current architec tures several different models are adopted. In this paper, us ing graph algorithms for illustrative purposes, we consider the impact of memory model on the implementation and performance of parallel algorithms on shared-memorymul tiprocessors. We show that the implementation of PRAM algorithms is largely “oblivious” of the underlying mem ory model, and has good performance on relaxed models. More importantly, we show that different memory models can favor drastically different algorithm designs.

Important Links:

Go Back