Browse Prior Art Database

Randomized Speed-ups in Parallel Computation

IP.com Disclosure Number: IPCOM000128190D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 16 page(s) / 47K

Publishing Venue

Software Patent Institute

Related People

Uzi Vishkin: AUTHOR [+3]

Abstract

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 0((nlog n)/p + log n) time parallel algorithm using p processors. A known conjecture states that it is impossible to design an 0(log n) time deterministic parallel algorithm that uses only n/log n processors. We present three randomized parallel algorithms for the problem. One of these algorithms runs almost-surely in time of 0(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM. *This research was supported by DOE grant DE-AC02-76ER03077 and by NSF grant NSF-MCS79-21258. **To be presented at the 16th STOC.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 9% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Randomized Speed-ups in Parallel Computation

(February 1984)

Uzi Vishkin

' Department of Computer Science Courant Institute of Mathematical Sciences New York University

251 Mercer St., New York, NY 10012 Ultra Canputer Note 66 Technical Report 107

ABSTRACT

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 0((nlog n)/p + log n) time parallel algorithm using p processors. A known conjecture states that it is impossible to design an 0(log
n) time deterministic parallel algorithm that uses only n/log n processors. We present three randomized parallel algorithms for the problem. One of these algorithms runs almost-surely in time of 0(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM. *This research was supported by DOE grant DE-AC02-76ER03077 and by NSF grant NSF-MCS79-21258. **To be presented at the 16th STOC.

I. Introduction

The family of models of computation used in this paper is the parallel random-access-machines (PR.AMs). All members of this family employ p synchronous processors all having access to a common memory. The PRAM family has 3 notable members. In a concurrent-read concurrent- write (CRCW) PRAM simultaneous reading from the same memory location is allowed as well as simultaneous writing. In the latter case the lowest numbered processor succeeds. A concurrent-read exclusive-write (CREW) PRAM allows simultaneous reading into the same memory location but not simultaneous writing. An EREW PRAM does not allow simultaneous reading or writing. See [Vi-83a] for a recent survey of results concerning the PRAM family. Let Seq(n) be the fastest known worst-case running time of a sequential algorithm, where n is the length of the input for the problem being considered. Obviously, the best upper bound on the parallel time achievable using p processors without improving the sequential result is of the form 0(Seq(n)/p). A parallel algorithm that achieves this running time is said to have optimal speed- up or more simply to be optimal. An ideal goal for serial computation is to design linear time algorithms (O(n) time) An analogous ideal goal for parallel computation is to design algorithms whose running time is proportional to n/p , where p is the number of processors used. In this case we say that a parallel algorithm achieves parallel linear running time.

The following problem is considered. (See also Fig. 1). Input. A linked list of length n. It is given in an array of length n, not necessarily in the order of the linked list. Each of the n elements (except the last element in the linked list) has a pointer to its subsequent element in the linked list. The list-ranking problem. Compute for each element its distance, counting elements, fro...