Parallel Algorithms: Difference between revisions
| Line 8: | Line 8: | ||
==Models== | ==Models== | ||
===PRAM=== | ===PRAM=== | ||
Parallel Random-Access Machine/Model<br> | Parallel Random-Access Machine/Model<br> | ||
You're given n synchronous processors each with local memory and access to a shared memory.<br> | You're given n synchronous processors each with local memory and access to a shared memory.<br> | ||
Each processor can write to shared memory, read to shared memory, or do computation in local memory.<br> | Each processor can write to shared memory, read to shared memory, or do computation in local memory.<br> | ||
====Types of PRAM==== | |||
* exclusive-read exclusive-write (EREW) | |||
* concurrent-read exclusive-write (CREW) | |||
* concurrent-read concurrent-write (CRCW) | |||
** Arbitrary CRCW - an arbitrary processor writing succeeds | |||
** Priority CRCW - the lowest numbered processor writing succeeds | |||
** Common CRCW - writing succeeds only if all processors write the same value | |||
Revision as of 19:40, 30 January 2020
Parallel Algorithms notes from CMSC751 with Uzi Vishkin. See File:CMSC751 Classnotes.pdf
XMT Language
XMTC is a single-program multiple-data (SPMD) extension of C.
- Spawn creates threads
- Threads expire at Join
Models
PRAM
Parallel Random-Access Machine/Model
You're given n synchronous processors each with local memory and access to a shared memory.
Each processor can write to shared memory, read to shared memory, or do computation in local memory.
Types of PRAM
- exclusive-read exclusive-write (EREW)
- concurrent-read exclusive-write (CREW)
- concurrent-read concurrent-write (CRCW)
- Arbitrary CRCW - an arbitrary processor writing succeeds
- Priority CRCW - the lowest numbered processor writing succeeds
- Common CRCW - writing succeeds only if all processors write the same value