Tight bounds on parallel list marking

Bhatt, SN

doi:10.1006/jpdc.1998.1447

Tight bounds on parallel list marking

1998-06-01

0

PRE

AI

DOI：10.1006/jpdc.1998.1447

Original

Original request for help

Save

Abstract

En 中文

The list marking problem involves marking the nodes of an L-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 Omega(min{l, n/p}) randomized lower bound for l-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 Theta(min {l, l/p + root(n/p) log n }) bound for randomized algorithms. Therefore, in the latter case, randomization yields a better performance for a wide range of parameter values. (C) 1998 Academic Press.

Keywords:

list marking

list ranking

linked structures

shared-memory machines

parallel algorithms

randomized algorithms

lower bounds

Tight bounds on parallel list marking

Abstract

Journal

Organization