Parallel Processing & Distributed Systems - Chapter 4+5: Parallel Computer Architectures - Thoai Nam

Nội dung text: Parallel Processing & Distributed Systems - Chapter 4+5: Parallel Computer Architectures - Thoai Nam

1. Parallel Computer Architectures Thoai Nam
2. Flynn’s Taxonomy  Based on notions of instruction and data streams – SISD (a Single Instruction stream, a Single Data stream ) – SIMD (Single Instruction stream, Multiple Data streams ) – MISD (Multiple Instruction streams, a Single Data stream) – MIMD (Multiple Instruction streams, Multiple Data stream)  Popularity – MIMD > SIMD > MISD Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
3. SIMD  SIMD – Vector computers, processor arrays – Special purpose computations PE : Processing Element LM : Local Memory DS DS PE1 LM1 IS CU IS Data sets DS DS loaded from host Program loaded PEn LMn from host SIMD architecture with distributed memory Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
4. MIMD  MIMD – General purpose parallel computers IS IS DS CU1 PU1 I/O Shared Memory IS DS I/O CUn PUn IS MIMD architecture with shared memory Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
5. Pipeline Computers (1)  Instructions are divided into a number of steps (segments, stages)  At the same time, several instructions can be loaded in the machine and be executed in different steps Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
6. Dataflow Architecture  Data-driven model – A program is represented as a directed acyclic graph in which a node represents an instruction and an edge represents the data dependency relationship between the connected nodes – Firing rule » A node can be scheduled for execution if and only if its input data become valid for consumption  Dataflow languages – Id, SISAL, Silage, LISP, – Single assignment, applicative(functional) language – Explicit parallelism Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
7. Dataflow Computer  Execution of instructions is driven by data availability – What is the difference between this and normal (control flow) computers?  Advantages – Very high potential for parallelism – High throughput – Free from side-effect  Disadvantages – Time lost waiting for unneeded arguments – High control overhead – Difficult in manipulating data structures Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
8. Execution on a Control Flow Machine Assume all the external inputs are available before entering do loop + : 1 cycle, * : 2 cycles, / : 3 cycles, a1 b1 c1 a2 b2 c2 a4 b4 c4 Sequential execution on a uniprocessor in 24 cycles How long will it take to execute this program on a dataflow computer with 4 processors? Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
9. Data Parallel Systems (1)  Programming model – Operations performed in parallel on each element of data structure – Logically single thread of control, performs sequential or parallel steps – Conceptually, a processor associated with each data element Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
10. Vector Processors  Instruction set includes operations on vectors as well as scalars  2 types of vector computers – Processor arrays – Pipelined vector processors Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
11. Pipeline Vector Processor  Stream vector from memory to the CPU  Use pipelined arithmetic units to manipulate data  Eg: Cray-1, Cyber-205 Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
12. UMA Multiprocessor (1)  Uses a central switching mechanism to reach a centralized shared memory  All processors have equal access time to global memory  Tightly coupled system  Problem: cache consistency Processor i Pi C1 C2 Cn P1 P2 Pn Cache i Ci Switching mechanism I/O Memory banks Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
13. UMA Multiprocessor (3)  Shared-bus switching mechanism Mem Mem Mem Mem Cache Cache I/O I/O P P Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
14. NUMA Multiprocessor  Distributed shared P P memory combined by local memory of Mem Cache Mem Cache all processors  Memory access time depends on Network whether it is local to the processor Mem Cache Mem Cache  Caching shared (particularly P P nonlocal) data? Distributed Memory Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
15. PVP (Parallel Vector Processor) VP : Vector Processor SM : Shared Memory VP VP VP Crossbar Switch SM SM SM Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
16. DSM (Distributed Shared Memory) MB: Memory Bus MB MB P/C: Microprocessor & Cache P/C P/C LM: Local Memory DIR: Cache Directory LM LM NIC: Network Interface Circuitry DIR DIR NIC NIC Custom-Designed Network Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
17. Current Types of Multicomputers  MPP (Massively Parallel Processing) – Total number of processors > 1000  Cluster – Each node in system has less than 16 processors.  Constellation – Each node in system has more than 16 processors Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
18. Clusters MB: Memory Bus MB MB P/C: Microprocessor & P/C P/C Cache M: Memory M M LD: Local Disk IOB: I/O Bus Bridge Bridge NIC: Network Interface LD IOB LD IOB Circuitry NIC NIC Commodity Network (Ethernet, ATM, Myrinet, VIA) Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM
19. Trend in Parallel Computer Architectures MPPs Constellations Clusters SMPs 400 350 300 250 200 150 Number of HPCsof Number 100 50 0 1997 1998 1999 2000 2001 2002 Years Khoa Khoa học và Kỹ thuật Máy tính – ĐH Bách Khoa TP.HCM