并行算法概述
并 行 算 法 概述
目录 °1.并行计算模型 2.并行算法的基本设计技术
目录 • 1.并行计算模型 2.并行算法的基本设计技术 2
Von neumann mode MEMORY MAR MDR INPUT OUTPUT Keyboard Monitor Mouse PROCESSING UNIT Printer Scanner LED Disk ALU丿 [TEMP Disk CONTROL UNIT PC R
Von Neumann Model 3 MEMORY CONTROL UNIT MAR MDR IR PROCESSING UNIT ALU TEMP PC OUTPUT Monitor Printer LED Disk INPUT Keyboard Mouse Scanner Disk
Instruction Processing Fetch instruction from memory Decode instruction Evaluate address Fetch operands from memory Execute operation Store result
Instruction Processing 4 Decode instruction Evaluate address Fetch operands from memory Execute operation Store result Fetch instruction from memory
Parallel Computing model Computing model Bridge between Sw and Hw general purpose hw, scalable hw transportable sw Abstract architecture for algorithm development Ex)PRAM, BSP, LogP
Parallel Computing Model • Computing model – Bridge between SW and HW • general purpose HW, scalable HW • transportable SW – Abstract architecture for algorithm development – Ex) PRAM, BSP, LogP 5
Parallel Programming Model What programmer uses in coding applications? Specifies communication and synchronization Communication primitives exposed to user-level realizes the programming mode Ex Uniprocessor, Multiprogramming, Data parallel message-passing, shared-address-space
Parallel Programming Model • What programmer uses in coding applications? – Specifies communication and synchronization – Communication primitives exposed to user-level realizes the programming model – Ex) Uniprocessor, Multiprogramming, Data parallel, message-passing, shared-address-space 6
Aspects of Parallel Processing ③ Algorithm developer Application developer ang mode System programmer Interconnection Network Memory Memory Memory Memory Multiprocessors Multiprocessors Multiprocessors Multiprocessors Architecture designer
Aspects of Parallel Processing 7 Algorithm developer Application developer Interconnection Network Memory P P P P Memory P P P P Memory P P P P Memory P P P P Multiprocessors Multiprocessors Multiprocessors Multiprocessors Parallel computing model Parallel programming model System programmer Architecture designer 3 4 2 1 Middleware
Parallel computing models PRAM Parallel Random Access memory A set of p processors Global shared memory Each processor can access any memory location in one time step Globally synchronized Executing same program in lockstep
Parallel Computing Models • PRAM – Parallel Random Access Memory – A set of p processors – Global shared memory • Each processor can access any memory location in one time step – Globally synchronized • Executing same program in lockstep 8
lustration of pram Single program executed in MIMD mode CLK Each processor has P1 P2 P3 P a unique index p Shared memory P processors connected to a single shared memory
Illustration of PRAM 9 P1 P2 P3 Pp Shared Memory CLK P processors connected to a single shared memory Each processor has a unique index. Single program executed in MIMD mode
Features Model architecture Synchronized RAM with common clock, but not SIMD operation MIMD No local memory in each RAN One global shared memory single address space architecture Synchronization, communication, parallelism overhead are zero
Features • Model architecture – Synchronized RAM with common clock, but not SIMD operation: MIMD – No local memory in each RAM – One global shared memory • single address space architecture – Synchronization, communication, parallelism overhead are zero. 10