Asynchronous Shared Memory Search Structures |
| |
Authors: | M Adler |
| |
Affiliation: | (1) Computer Science Division, University of California, Berkeley, CA 94720, USA micah@cs.berkeley.edu and International Computer Science Institute, 1947 Center Street, Suite 600, Berkeley, CA 94704-1198, USA, US |
| |
Abstract: | We study the problem of storing an ordered set on an asynchronous shared memory parallel computer. We examine the case where
we want to perform successor (least upper bound) queries efficiently on the set members that are stored. We also examine the
case where processors insert and delete members of the set. Due to asynchrony, we require processors to perform queries and
to maintain the structure independently. Although several such structures have been proposed, the analysis of these structures
has been very limited. We here use the recently proposed QRQW PRAM model to provide upper and lower bounds on the performance
of such data structures.
In the asynchronous QRQW PRAM, the problem of processors concurrently and independently searching a shared data structure
is very similar to the problem of routing packets through a network. Using this as a guide, we introduce the Search-Butterfly,
a search structure that combines the efficient packet routing properties of the butterfly graph with the efficient search
structure properties of the B-Tree. We analyze the behavior of the Search-Butterfly when the following operations are performed:
arbitrary searches, random searches, and random searches, insertions, and deletions. We also provide lower bounds that show
that the results are within a factor of O(\log n) of optimal where n is the number of keys in the structure. When the searches are random, the results are within a constant factor of optimal.
Many of the proofs are derived from closely related results for packet routing. Others are of independent interest, most
notably a method of adding queues to any network belonging to a large class of queuing networks with non-Markovian routing
in a manner that allows us to bound the delay experienced by packets in the augmented network.
Received October 1996, and in final form July 1997. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|