TY - JOUR
T1 - Tight Bounds on Parallel List Marking
AU - Bhatt, Sandeep N.
AU - Bilardi, Gianfranco
AU - Herley, Kieran T.
AU - Pucci, Geppino
AU - Ranade, Abhiram
PY - 1998/6/15
Y1 - 1998/6/15
N2 - The list marking problem involves marking the nodes of an ℓ-node linked list stored in the memory of a (p,n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. Under the assumption that cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish anΩ(min{ℓ,n/p}) randomized lower bound for ℓ-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. Such a result implies that randomization cannot be exploited in any significant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bound still applies to deterministic algorithms, while we establish a tightΘ(min{ℓ,ℓ/p+(n/p)logn})bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values.
AB - The list marking problem involves marking the nodes of an ℓ-node linked list stored in the memory of a (p,n)-PRAM, when only the position of the head of the list is initially known, while the remaining list nodes are stored in arbitrary memory locations. Under the assumption that cells containing list nodes bear no distinctive tags distinguishing them from other cells, we establish anΩ(min{ℓ,n/p}) randomized lower bound for ℓ-node lists and present a deterministic algorithm whose running time is within a logarithmic additive term of this bound. Such a result implies that randomization cannot be exploited in any significant way in this setting. For the case where list cells are tagged in a way that differentiates them from other cells, the above lower bound still applies to deterministic algorithms, while we establish a tightΘ(min{ℓ,ℓ/p+(n/p)logn})bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values.
KW - List marking; list ranking; linked structures; shared-memory machines; parallel algorithms; randomized algorithms; lower bounds
UR - http://www.scopus.com/inward/record.url?scp=0039496753&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0039496753&partnerID=8YFLogxK
U2 - 10.1006/jpdc.1998.1447
DO - 10.1006/jpdc.1998.1447
M3 - Article
AN - SCOPUS:0039496753
SN - 0743-7315
VL - 51
SP - 75
EP - 88
JO - Journal of Parallel and Distributed Computing
JF - Journal of Parallel and Distributed Computing
IS - 2
ER -