A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model
顯示簡易詮釋資料 統計資料| 欄位 | 內容 | 語言 |
|---|---|---|
dc.citation.epage |
1471 | en_US |
dc.citation.issue |
11 | en_US |
dc.citation.spage |
1455 | en_US |
dc.citation.volume |
66 | en_US |
dc.citation.woscount |
0 | |
dc.contributor.author |
Chen, Sheng-Hsiung | en_US |
dc.contributor.author |
Huang, Ting-Lu | en_US |
dc.contributor.department |
資訊工程學系 | zh_TW |
dc.contributor.department |
Department of Computer Science | en_US |
dc.date.accessioned |
2014-12-08T15:15:27Z | |
dc.date.available |
2014-12-08T15:15:27Z | |
dc.date.issued |
2006-11-01 | en_US |
dc.description.abstract |
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. | en_US |
dc.identifier.doi |
10.1016/j.jpdc.2006.07.002 | en_US |
dc.identifier.issn |
0743-7315 | en_US |
dc.identifier.journal |
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | en_US |
dc.identifier.uri |
http://dx.doi.org/10.1016/j.jpdc.2006.07.002 | en_US |
dc.identifier.uri |
https://ir.lib.nycu.edu.tw/handle/11536/11570 | |
dc.identifier.wosnumber |
WOS:000241963200010 | |
dc.language.iso |
en_US | en_US |
dc.subject |
mutual exclusion | en_US |
dc.subject |
atomic instructions | en_US |
dc.subject |
shared memory systems | en_US |
dc.subject |
time complexity | en_US |
dc.subject |
tight bounds | en_US |
dc.title |
A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model | en_US |
dc.type |
Article | en_US |
檔案
- 000241963200010.pdf (386.0 KB, Adobe PDF)
所屬典藏: 期刊論文
引用此條目
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