EREW

AcronymDefinition
EREWExclusive Read Exclusive Write
References in periodicals archive ?
Notice that EREW algorithms are actually more practical in the sense that they can be adapted to other more realistic parallel models like the Queuing Shared Memory (QSM) [Gibbons et al.
In Section 6, we adapt algorithm to run on the EREW PRAM and reduce the processor bound to linear.
Precisely, their algorithm is the first one to run, with high probability, in O(log n) time and linear work on the EREW PRAM.
Using standard parallel algorithmic techniques, each stage can be implemented in O(log n) time on the EREW PRAM using a linear number of processors (see e.
Then we illustrate how to modify the algorithm to run on the EREW PRAM and reduce the processor bound to linear.
The minimum spanning tree of a weighted undirected graph can be found in O(log n) time using m + n log n processors on the EREW PRAM.
The minimum spanning tree of an undirected graph can be found in O(log n) time using a linear number of processors on the EREW PRAM.
Finding connected components in O(log n loglog n) time on the EREW PRAM.
As mentioned earlier, Dietzfelbinger and Meyer auf der Heide [1993] have presented a protocol using three hash functions that emulates an n-processor EREW PRAM in O(lg lg n) time on an n-processor c-collision crossbar.
Furthermore, our analysis goes through with [Epsilon] = 1, that is, we consider the most basic form of the protocol in which the action of all n EREW PRAM processors is emulated at once.
It is worth noting that by the above result, a 1-collision crossbar can solve the 3 out of 5 problem and hence can simulate an EREW PRAM with n processors in O(log log n) time whp using 5 hash functions.
For appropriate choices of a and b, the a out of b protocol can be used to emulate a single step of an n-processor EREW PRAM on an n-processor crossbar.