کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
432198 688740 2006 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A tight bound on remote reference time complexity of mutual exclusion in the read-modify-write model
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 66, Issue 11, November 2006, Pages 1455-1471