An evaluation of parallel algorithms on current memory consistency models

Guojing Cong

An evaluation of parallel algorithms on current memory consistency models

Guojing Cong

Research output: Contribution to journal › Conference article › peer-review

Abstract

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

Original language	English
Pages (from-to)	388-393
Number of pages	6
Journal	Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems
State	Published - 2006
Externally published	Yes
Event	18th IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2006 - Dallas, TX, United States Duration: Nov 13 2006 → Nov 15 2006

Keywords

Consistency models
Parallel algorithms
Shared memory

Cite this

@article{2fff2eecb1c445c1aa43e58a384228c8,

title = "An evaluation of parallel algorithms on current memory consistency models",

abstract = "Memory consistency model is crucial to the performance of shared-memory multiprocessors, and in current architectures several different models are adopted. In this paper, using graph algorithms for illustrative purposes, we consider the impact of memory model on the implementation and performance of parallel algorithms on shared-memory multiprocessors. We show that the implementation of PRAM algorithms is largely {"}oblivious{"} of the underlying memory model, and has good performance on relaxed models. More importantly, we show that different memory models can favor drastically different algorithm designs.",

keywords = "Consistency models, Parallel algorithms, Shared memory",

author = "Guojing Cong",

year = "2006",

language = "English",

pages = "388--393",

journal = "Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems",

issn = "1027-2658",

note = "18th IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2006 ; Conference date: 13-11-2006 Through 15-11-2006",

}

TY - JOUR

T1 - An evaluation of parallel algorithms on current memory consistency models

AU - Cong, Guojing

PY - 2006

Y1 - 2006

N2 - Memory consistency model is crucial to the performance of shared-memory multiprocessors, and in current architectures several different models are adopted. In this paper, using graph algorithms for illustrative purposes, we consider the impact of memory model on the implementation and performance of parallel algorithms on shared-memory multiprocessors. We show that the implementation of PRAM algorithms is largely "oblivious" of the underlying memory model, and has good performance on relaxed models. More importantly, we show that different memory models can favor drastically different algorithm designs.

AB - Memory consistency model is crucial to the performance of shared-memory multiprocessors, and in current architectures several different models are adopted. In this paper, using graph algorithms for illustrative purposes, we consider the impact of memory model on the implementation and performance of parallel algorithms on shared-memory multiprocessors. We show that the implementation of PRAM algorithms is largely "oblivious" of the underlying memory model, and has good performance on relaxed models. More importantly, we show that different memory models can favor drastically different algorithm designs.

KW - Consistency models

KW - Parallel algorithms

KW - Shared memory

UR - https://www.scopus.com/pages/publications/38049172934

M3 - Conference article

AN - SCOPUS:38049172934

SN - 1027-2658

SP - 388

EP - 393

JO - Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems

JF - Proceedings of the IASTED International Conference on Parallel and Distributed Computing and Systems

T2 - 18th IASTED International Conference on Parallel and Distributed Computing and Systems, PDCS 2006

Y2 - 13 November 2006 through 15 November 2006

ER -

An evaluation of parallel algorithms on current memory consistency models

Abstract

Keywords

Other files and links

Fingerprint

Cite this