Browse Prior Art Database

An Efficient Parallel Strong Orientation

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

Publishing Venue

Software Patent Institute

Related People

Uzi Vishkin: AUTHOR [+3]

Abstract

The family of models of computation used in this paper is the parallel random-access-machines (PRAMs). All members of this family employ p synchronous processors all having access to a common memory. We mention 3 members of the PRAM family in descending order of strength. 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-83] for a recent survey of results concerning the PRAM family. Recall that a bridge in a connected graph is an edge whose removal disconnects the graph and a digraph is strongly connected if for every two vertices a and v there is a directed path from a to v. The following problem is considered. Input. A connected bridgeless undirected graph [Equation ommitted] . The strong orientation problem. Assign directions to its edges so that the resulting digraph is strongly connected. It is known that such strong orientation exists iff the input graph is connected and bridgeless. [At-84] indicates that this problem has a simple linear time serial solution: Apply depth-first search to the graph. Orient tree edges away from the root and back edges towards the root. Since depth=first search seems to be inherently serial (see [R-83] for some evidence) another approach is required for designing efficient parallel algorithms. [At-84) gave an 0(log n) time algorithm for this problem using n3 processors on a CRCW PRAM. Atallah's algorithm runs in [Equation ommitted] time using p processors on a CREW PRAM. Our algorithm runs in 0(logn) time using only n+m processors on a CRCW PRAM. An alternative implementation of the algorithm runs in [Equation ommitted] processors

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

Page 1 of 7

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

An Efficient Parallel Strong Orientation

(February 1984

Technical Report 109 ~~x'~

G Vii`.; Ultracomputer Note 67 ALE

Uzi Vishkin

Department of Computer Science

Courant Institute of Mathematical Sciences

New York University

251 Mercer St., New York, NY 10012

*This research was supported by DOE grant DE-~AC02-76ER03077 and by NSF grant NSF- MCS79-21258. w~t~

Introduction

The family of models of computation used in this paper is the parallel random-access-machines (PRAMs). All members of this family employ p synchronous processors all having access to a common memory. We mention 3 members of the PRAM family in descending order of strength. 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-83] for a recent survey of results concerning the PRAM family. Recall that a bridge in a connected graph is an edge whose removal disconnects the graph and a digraph is strongly connected if for every two vertices a and v there is a directed path from a to v. The following problem is considered. Input. A connected bridgeless undirected graph

(Equation Omitted)

. The strong orientation problem. Assign directions to its edges so that the resulting digraph is strongly connected. It is known that such strong orientation exists iff the input graph is connected and bridgeless. [At-84] indicates that this problem has a simple linear time serial solution: Apply depth-first search to the graph. Orient tree edges away from the root and back edges towards the root. Since depth=first search seems to be inherently serial (see [R-83] for some evidence) another approach is required for designing efficient parallel algorithms. [At-84) gave an 0(log n) time algorithm for this problem using n3 processors on a CRCW PRAM. Atallah's algorithm runs in

New York University Page 1 Dec 31, 1984

Page 2 of 7

An Efficient Parallel Strong Orientation

(Equation Omitted)

time using p processors on a CREW PRAM. Our algorithm runs in 0(logn) time using only n+m processors on a CRCW PRAM. An alternative implementation of the algorithm runs in

(Equation Omitted)

processors -t- on an CREW PRAM. This is optimal for dense graphs. A very high-level description of our algorithm is close to Atallah's algorithm. However, only a complete and drastic change in the way parallelism is approached allows the claimed improvements in efficiency. Algorithmic methods that reduce the number of processors without changing the running time are of great importance for the design of parallel algorithms. The survey [Vi-83] mentions many parallel algorithm that achieved a previously known runni...