Content deleted Content added
Tags: Mobile edit Mobile web edit |
Tags: Mobile edit Mobile web edit |
||
Line 18:
*Exclusive Read Exclusive Write (EREW): The same block in main memory cannot be read or written by multiple processors concurrently. Only one processor can access a block at a time.
The following two algorithms<ref name=":0">{{Cite journal|last=Arge|first=Lars|last2=Goodrich|first2=Michael T.|last3=Nelson|first3=Michael|last4=Sitchinava|first4=Nodari|date=2008|title=Fundamental parallel algorithms for private-cache chip multiprocessors|url=http://dx.doi.org/10.1145/1378533.1378573|journal=Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures - SPAA '08|___location=New York, New York, USA|publisher=ACM Press|doi=10.1145/1378533.1378573|isbn=9781595939739}}</ref> solve the CREW and EREW problem if <math>P \leq B</math> processors write to the same block simultaneously.
A first approach is to serialize the write operations. Only one processor after the other writes to the block. This results in a total of <math>P</math> parallel block transfers. A second approach needs <math>O(\log(P))</math> parallel block transfers and an additional block for each processor. The main idea is to schedule the write operations in a [[Reduce (parallel pattern) | binary tree fashion]] and gradually combine the data into a single block. In the first round <math>P</math> processors combine their blocks into <math>P/2</math> blocks. Then <math>P/2</math> processors combine the <math>P/2</math> blocks into <math>P/4</math>. This procedure is continued until all the data is combined in one block.
=== Comparison to other models ===
| |||