Browse Prior Art Database

An Efficient Parallel Strong Orientation

IP.com Disclosure Number: IPCOM000149422D
Original Publication Date: 1984-Feb-29
Included in the Prior Art Database: 2007-Apr-01

Publishing Venue

Software Patent Institute

Related People

Authors:
Vishkin, Uzi
Other Related People:

Abstract

An Efficient Parallel Strong Orientation (February 1984) Technical Report 109 Ultracomputer Note 67 Uzi Vishkin Department of Computer ScienceCourant Institute of Mathematical Sciences New York University251 Mercer St., New York, NY 10012 *This research was supported by DOE grant DE-.AC02-76E~03077 and by NSF grant NSF-MCS79-21258. The family of models of computation used in this paper is the parallel random-access-machines (PRAMS). All members o.E 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 sam; 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-831 for a recent survey of results concerning the PRAM family.