并行算法2algorithm.ppt

现代密码学理论与实践之五 Overview of Parallel Computing xxx Notice!!! Course Portal /xhshi/course/ParaProgram.htm Agenda 1.Parallel computing Model2.technical issues about Parallel computing algorithms Von Neumann Model Instruction Processing Parallel Computing Model Computing model Bridge between SW and HW general purpose HW, scalable HW transportable SW Abstract architecture for algorithm development Eg. PRAM, BSP, LogP Parallel Programming Model What programmer uses in coding applications? Specifies communication and synchronization Communication primitives exposed to used-level realizes the programming model e.g., Uniprocessor, Multiprogramming, Data parallel, message-passing, shared-address-space Aspects of Parallel Processing 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 Illustration of PRAM 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. Features (Cont’d) Operations per step Read/write a word from/to the memory Local operation An instruction could perform the following three operations in one cycle Fetch on or two words from the memory as operands Perform an arithmetic/logic operation Store the result back in memory Problems with PRAM Inaccurate description of real-world parallel systems Unaccounted costs Latency, bandwidth, non-local memory access, memory access contention issues, synchronization costs, etc Algorithms perceived to work well in PRAM may have poor performance in practice PRAM Variants Variants arise to model some of these costs Each introduces some practical aspect of machine Gives algorithm designer better idea for optimization Variants can be grouped into 4 categories Memory acces