A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model
檔案
- 000241963200010.pdf (386.0 KB, Adobe PDF)
日期
2006-11-01
類型
系所
期刊名稱
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING
卷期與頁次
第 66 卷第 11 期,頁 1455–1471
ISSN
0743-7315
語言
英文
摘要
In distributed shared memory multiprocessors, remote memory references generate processor-to-memory traffic, which may result in a bottleneck. It is therefore important to design algorithms that minimize the number of remote memory references. We establish a lower bound of three on remote reference time complexity for mutual exclusion algorithms in a model where processes communicate by means of a general read-modify-write primitive that accesses at most one shared variable in one instruction. Since the general read-modify-write primitive is a generalization of a variety of atomic primitives that have been implemented in multiprocessor systems, our lower bound holds for all mutual exclusion algorithms that use such primitives. Furthermore, this lower bound is shown to be tight by presenting an algorithm with the matching upper bound. (C) 2006 Elsevier Inc. All rights reserved.
所屬典藏
期刊論文引用此條目
Chen, S.-H., & Huang, T.-L. (2006). A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model. JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 66(11), 1455–1471. https://doi.org/10.1016/j.jpdc.2006.07.002
引用文字依 APA 第 7 版格式自動產生,使用前請再核對。
分享
永久網址:https://ir.lib.nycu.edu.tw/handle/11536/11570