Parallel Algorithms: Difference between revisions
| Line 13: | Line 13: | ||
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> | ||
You tell each processor what to do at each time step.<br> | |||
====Types of PRAM==== | ====Types of PRAM==== | ||
| Line 21: | Line 22: | ||
** Priority CRCW - the lowest numbered processor writing succeeds | ** Priority CRCW - the lowest numbered processor writing succeeds | ||
** Common CRCW - writing succeeds only if all processors write the same value | ** Common CRCW - writing succeeds only if all processors write the same value | ||
===Work Depth=== | |||
You provide a sequence of instructions. At each time step, you specify the number of parallel operations. | |||
Revision as of 19:56, 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.
You tell each processor what to do at each time step.
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
Work Depth
You provide a sequence of instructions. At each time step, you specify the number of parallel operations.