𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Randomized parallel speedups for list ranking

✍ Scribed by Uzi Vishkin

Publisher
Elsevier Science
Year
1987
Tongue
English
Weight
946 KB
Volume
4
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

The following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O((n log n)/p + log n) time parallel algorithm using p processors. We present a randomized parallel algorithm for the problem. The algorithm is designed for an exclusive-read exclusive-write parallel random access machine (EREW PRAM). It runs almost surely in time O(n/p + log n log* n) usingp processors. Using a recently published parallel prefix sums algorithm the list-ranking algorithm can be adapted to run on a concurrent-read concurrent-write parallel random access machine (CRCW PRAM) almost surely in time @n/p + log n) using p processors. Q 1987 Academic Fws, Inc.

πŸ“œ SIMILAR VOLUMES

Practical Parallel List Ranking
Practical Parallel List Ranking
✍ Jop F Sibeyn; Frank Guillaume; Tillmann Seidel πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 546 KB

Parallel list ranking is a hard problem due to its extreme degree of irregularity. Also, because of its linear sequential complexity, it requires considerable effort just to reach speed-up one (break even). In this paper, we address the question of how to solve the list-ranking problem for lists of

A parallelization technique for the spee
A parallelization technique for the speedup of configuration interaction computing
✍ Nobumitsu Honjou; Kazumasa Ohtsuki; Masahiro Sekiya; Fukashi Sasaki πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 878 KB

Honjou, N., K. Ohtsuki, M. Sekiya and F. Sasaki, A parallelization technique for the speedup of configuration interaction computing, Parallel Computing 17 (1991) 297-310 In order to speed up configuration interaction (CI) computing by means of fork/join based parallel processing, we have considered

Rank Tests for correlated Random Variabl
Rank Tests for correlated Random Variables
✍ Prof. Dr. E. Brunner; N. Neumann πŸ“‚ Article πŸ“… 1982 πŸ› John Wiley and Sons 🌐 English βš– 612 KB

## Abstract In this paper we consider the asymptotic distribution of linear rank‐statistics allowing certain dependencies between the random variables. General theorems will be given, from which the results contained in SEN (1967a, 1967b, 1968), MEHRA/SEN (1969) and PURI/SEN (1971) can be derived.

An optimal parallel algorithm for node r
An optimal parallel algorithm for node ranking of cographs
✍ Liu Chuan-Ming; Yu Ming-Shing πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 885 KB

A ranking of a graph G is a mapping, p, from the vertices of G to the natural numbers such that for every path between any two vertices u and u, uf II, with p(u) = p(u), there exists at least one vertex w on that path with p(w) > p(u) = p(u). The value p(u) of a vertex u is the rank of vertex II. A