5,323
edits
Parallel Algorithms: Difference between revisions
→Minimum Spanning Forest
| Line 523: | Line 523: | ||
===Minimum Spanning Forest=== | ===Minimum Spanning Forest=== | ||
==Hardware/Architecture== | |||
[http://users.umiacs.umd.edu/~vishkin/XMT/vCarageaLeebook.pdf Models for Advancing PRAM and Other Algorithms into Parallel Algorithms for PRAM] | |||
[[File:Pram hardware diagram.jpg | 400px]] | |||
* MTCU - Master Thread Control Unit - runs in serial mode | |||
* TCU Cluster - Thread Control Unit | |||
;Procedure | |||
* Spawn broadcasts your spawn code in the block to every thread control unit (TCU). | |||
* Data is shared through the interconnection network | |||
;Performance Penalty | |||
<math>\text{Execution Depth} = \text{Computation Depth} + LSRTM \times R + QD</math> | |||
* <math>LSTRM</math> - length of sequence of round trips to memory | |||
* <math>R</math> - time for round trip to memory | |||
* <math>QD</math> - queuing delay | |||
** If multiple threads access the same memory module, they are queued at the memory module | |||
==Resources== | ==Resources== | ||