中种学林水学计算机科学与术系 versity ResearchhIssuesna parallel computation models(3) Bulk Synchronous Parallel( BSP)model MIMD-DM, Consist of a set of processors send/receive message communication A mechanism for synchronization Bulk synchronous: to combine message into a bulk one to transfer to delay communication BSP parameters p: number of processors Barrier synchronization time g: unary packet transmission time(time steps/packet)=1/bandwidth BSP bulk synchronization can reduce the difficulty of design and analysis and ensure easily the correctness of the algorithm NHPCC at Hefei 2021/2/6
NHPCC at Hefei 11 2021/2/6 Research Issues – Parallel computation models(3) ▪ Bulk Synchronous Parallel (BSP) model ▪ MIMD-DM, Consist of a set of processors, send/receive message communication , A mechanism for synchronization. ▪ Bulk synchronous: to combine message into a bulk one to transfer, to delay communication. ▪ BSP parameters ▪ p: number of processors ▪ l: Barrier synchronization time ▪ g: unary packet transmission time (time steps/packet)=1/bandwidth ▪ BSP bulk synchronization can reduce the difficulty of design and analysis and ensure easily the correctness of the algorithm
中种学林水学计算机科学与术系 versity ResearchhIssuesna parallel computation models(4) LogP model MIMD-DM, point-to-point communication, implicit synch Parameters(LogP) L network latency), o(communication overhead) (gap=1/bandwidth), P(#processors) Advantages Capturing the communication bottleneck of parallel computers Hiding details of topology routing algorithm and network protocol Can be applicable shared variable, message passing and data parallel algorithm Disadvantages Restricting the network capacity, neglecting communication congestion Difficult to describe and design of algorithms NHPCC at Hefei 202172/6 12
NHPCC at Hefei 12 2021/2/6 Research Issues – Parallel computation models(4) ▪ LogP model ▪ MIMD-DM, point-to-point communication, implicit synch. ▪ Parameters (LogP) ▪ L (network latency), o (communication overhead), g (gap=1/bandwidth), P (#processors). ▪ Advantages ▪ Capturing the communication bottleneck of parallel computers. ▪ Hiding details of topology, routing algorithm and network protocol. ▪ Can be applicable shared variable, message passing and data parallel algorithm. ▪ Disadvantages ▪ Restricting the network capacity, neglecting communication congestion. ▪ Difficult to describe and design of algorithms
中种学林水学计算机科学与术系 versity ResearchhIssuesna parallel computation models(5) BSP(Bulk Synch)→>BSP( Subset synch)→>BSP (Pairwise synch )=logP BSP can simulate logP with constant factor and logP can simulate bsp with at most logarithmic factor BSP=LogP+Barriers-Overhead BSP offers a more convenient abstraction for design of algorithm and program and logP provides a better control of machine resources BSP seems preferable with greater simplicity and portability and more structured programming style NHPCC at Hefei 2021/2/6 13
NHPCC at Hefei 13 2021/2/6 Research Issues – Parallel computation models(5) ▪ BSP (Bulk Synch.)-> BSP (Subset synch.)-> BSP (Pairwise synch.) = logP ▪ BSP can simulate logP with constant factor and logP can simulate BSP with at most logarithmic factor ▪ BSP＝LogP+Barriers－Overhead ▪ BSP offers a more convenient abstraction for design of algorithm and program and logP provides a better control of machine resources ▪ BSP seems preferable with greater simplicity and portability and more structured programming style
中科学计算机科学节之系 Uriversity D三 PARTI三N esearchIssues- Parallel computation models(5) MH (Memory Hierarchy) model A sequential computer memory is modeled as a sequence of memory modules <MO, M1, M2, M3,...> With buses connecting adjacent modules, All buses may be active simultaneously, Mo(Central processor) M1(Cache), M2( Main memory), M3(Storage) MH is oriented address access model memory access cost function f(a)is a monotonic increasing function, a is memory address MH model is suitable for sequential memory(magnetic tape etc. NHPCC at Hefei 2021/2/6
NHPCC at Hefei 14 2021/2/6 ▪ MH (Memory Hierarchy) model: ▪ A sequential computer memory is modeled as a sequence of memory modules <M0, M1, M2, M3, …>, With buses connecting adjacent modules, All buses may be active simultaneously, M0 (Central processor), M1 (Cache), M2(Main memory), M3(Storage). ▪ MH is oriented address access model, memory access cost function f(a) is a monotonic increasing function, a is memory address. ▪ MH model is suitable for sequential memory (magnetic tape etc.) Research Issues – Parallel computation models(5)
中科学计算机科学节之系 Uriversity D三 PARTI三N esearchIssues- Parallel computation models(5) UMH (Uniform Memory Hierarchy) model UMH model captures performance-relevant aspects of the hierarchical nature of computer memory which is a tool for quantifying the efficiency of data movements Memory access cost function f(k), k is of memory hierarchy. The memory access of the algorithm is always epeatly from farther memory modules neglecting from nearer memory modules if possible Prefetching operands and overlapping computation with memory access operations are encouraged NHPCC at Hefei 2021/2/6 15
NHPCC at Hefei 15 2021/2/6 ▪ UMH (Uniform Memory Hierarchy) model: ▪ UMH model captures performance-relevant aspects of the hierarchical nature of computer memory which is a tool for quantifying the efficiency of data movements. ▪ Memory access cost function f(k), k is # of memory hierarchy. ▪ The memory access of the algorithm is always repeatly from farther memory modules neglecting from nearer memory modules if possible. ▪ Prefetching operands and overlapping computation with memory access operations are encouraged. Research Issues – Parallel computation models(5)