A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model

檔案

日期

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

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/11570