Parallel Processing & Distributed Systems - Chapter 2: Parallel Computer Models & Classification - Thoai Na

Nội dung text: Parallel Processing & Distributed Systems - Chapter 2: Parallel Computer Models & Classification - Thoai Na

1. Chapter 2 Parallel Computer Models & Classification Thoai Nam Faculty of Computer Science and Engineering HCMC University of Technology
2. Abstract Machine Models Thoai Nam Faculty of Computer Science and Engineering HCMC University of Technology
3. RAM (1)  RAM (Random Access Machine) Read-only x x x input tape 1 2 n r0 Location r1 counter Program r2 r3 Memory Write-only x1 x2 output tape Khoa KH&KT MT - ĐHBK TP.HCM
4. PRAM (1) Parallel Random Access Machine (Introduced by Fortune and Wyllie, 1978) Control P1 P2 Pn Private memory Private memory Private memory Interconnection network Global memory Khoa KH&KT MT - ĐHBK TP.HCM
5. PRAM(3) PRAM composed of: – P processors, each with its own unmodifiable program – A single shared memory composed of a sequence of words, each capable of containing an arbitrary integer – a read-only input tape – a write-only output tape PRAM model is a synchronous, MIMD, shared address space parallel computer – Processors share a common clock but may execute different instructions in each cycle Khoa KH&KT MT - ĐHBK TP.HCM
6. Time Complexity Problem  Time complexity of a PRAM algorithm is often expressed in the big-O notation  Machine size n is usually small in existing parallel computers  Ex: – Three PRAM algorithms A, B and C have time complexities if 7n, (n log n)/4, n log log n. – Big-O notation: A(O(n)) < C(O(n log log n)) < B(O(n log n)) – Machines with no more than 1024 processors: log n ≤ log 1024 = 10 and log log n ≤ log log 1024 < 4 and thus: B < C < A Khoa KH&KT MT - ĐHBK TP.HCM
7. Conflicts Resolution Schemes(2)  Common/Identical CRCW – All processors writing to the same memory location must be writing the same value. – The software must ensure that different values are not attempted to be written.  Arbitrary CRCW – Different values may be written to the same memory location, and an arbitrary one succeeds.  Priority CRCW – An index is associated with the processors and when more than one processor write occurs, the lowest-numbered processor succeeds. – The hardware must resolve any conflicts Khoa KH&KT MT - ĐHBK TP.HCM
8. Parallel Reduction (1) 4 3 8 2 9 1 0 5 6 3 7 10 10 5 9 17 15 9 32 9 41 Khoa KH&KT MT - ĐHBK TP.HCM
9. Broadcasting on a PRAM  “Broadcast” can be done on CREW PRAM in O(1) steps: – Broadcaster sends value to shared memory – Processors read from shared memory  Requires logP steps on EREW PRAM M S P P P P Khoa KH&KT MT - ĐHBK TP.HCM
10. BSP Model  A set of n nodes (processor/memory pairs)  Communication Network – Point-to-point, message passing (or shared variable)  Barrier synchronizing facility – All or subset  Distributed memory architecture Khoa KH&KT MT - ĐHBK TP.HCM
11. A Figure of BSP Programs P1 P2 P3 P4 Superstep 1 Computation Communication Barrier Superstep 2 Computation Communication Barrier Khoa KH&KT MT - ĐHBK TP.HCM
12. Time Complexity of BSP Algorithms  Execution time of a superstep: – Sequence of the computation, the communication, and the synchronization operations: w + gh + l – Overlapping the computation, the communication, and the synchronization operations: max{w, gh, l} Khoa KH&KT MT - ĐHBK TP.HCM
13. Parallel Computer Models (1)  A parallel machine model (also known as programming model, type architecture, conceptual model, or idealized model) is an abstract parallel computer from programmer‘s viewpoint, analogous to the von Neumann model for sequential computing.  The abstraction need not imply any structural information, such as the number of processors and interprocessor communication structure, but it should capture implicitly the relative costs of parallel computation.  Every parallel computer has a native model that closely reflects its own architecture. Khoa KH&KT MT - ĐHBK TP.HCM