中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD Introduction 3) Classif ication of parallel algorithms Numerical parallel algorithms(algebraic operation: matrix operations, solving a system of linear equations etc.) Non-numerical parallel algorithms(symbolic operation sorting, searching graph algorithms etc.) Research hierarchy of parallel algorithms Parallel complexity theory (parallelizable problem, NC class problem, P-complete problem, lower bound etc.) Design and analysis of parallel algorithms(efficient parallel algorithms) Implementation of parallel algorithms (hardware platform software supporting) NHPCC at Hefei 2021/2/6
NHPCC at Hefei 6 2021/2/6 Introduction (3) ▪ Classification of parallel algorithms ▪ Numerical parallel algorithms (algebraic operation: matrix operations, solving a system of linear equations etc.). ▪ Non-numerical parallel algorithms (symbolic operation: sorting, searching, graph algorithms etc.). ▪ Research hierarchy of parallel algorithms ▪ Parallel complexity theory (parallelizable problem, NC class problem, P-complete problem, lower bound etc.) ▪ Design and analysis of parallel algorithms (efficient parallel algorithms). ▪ Implementation of parallel algorithms (hardware platform, software supporting)
中图种学学计算机科学与术系 University of Science and Technology of China DEPARTMENT。 F COMPUTE三巴 ENCE AND ECHNOLDD 工 ntroduction(4) The history of parallel algorithm research From 70's to 80's two decades, parallel algorithm research were very hot, many excellent papers, textbooks monographs of parallel algorithms were published From the middle of 90s, parallel algorithm had shifted to parallel computing New opportunity for parallel algorithm research The dramatically decrease of computer price and the rapid development of communication technology, make it possible to build PC-cluster by ourselves It is easy to get free software to support cluster from internet NHPCC at Hefei 2021/2/6
NHPCC at Hefei 7 2021/2/6 Introduction (4) ▪ The history of parallel algorithm research ▪ From 70’s to 80’s two decades, parallel algorithm research were very hot, many excellent papers, textbooks, monographs of parallel algorithms were published. ▪ From the middle of 90’s, parallel algorithm had shifted to parallel computing. ▪ New opportunity for parallel algorithm research ▪ The dramatically decrease of computer price and the rapid development of communication technology, make it possible to build PC-cluster by ourselves. ▪ It is easy to get free software to support cluster from internet
中图种学学计算机科学与术系 University of Science and Technology ef D三 PARTMENT OF C Researc chInses Parallel computation models PRAM APRAM BSP logp MH and UMH M emory-LO Design techniques Partitioning Principle Divide-and-Conquer strategy Balanced Trees Method Doubling techniques Pipelining Techniques Parallel complexity theory Nc class P-complete NHPCC at Hefei 2021/2/6 8
NHPCC at Hefei 8 2021/2/6 Research Issues ▪ Parallel computation models ▪ PRAM ▪ APRAM ▪ BSP ▪ logP ▪ MH and UMH ▪ Memory-LogP ▪ Design techniques ▪ Partitioning Principle ▪ Divide-and-Conquer Strategy ▪ Balanced Trees Method ▪ Doubling Techniques ▪ Pipelining Techniques ▪ Parallel complexity theory ▪ NC class ▪ P-complete
中种学林水学计算机科学与术系 versity ResearchhIssuesna parallel computation models(1) PRAM(Parallel Random Access Memory SIMD-SM, Used for fine grain parallel computing Centralized shared memory, Globally synchronized Advantages Suitable for representing and analyzing complexity of parallel algorithms, Simple to use, hiding the most of low level details of parallel computer(communication, ynchronizationetc) Disadvantages Unsuitable for mimd computers Unrealistic to neglect the issues of memory contention communication delay etc NHPCC at Hefei 2021/2/6
NHPCC at Hefei 9 2021/2/6 Research Issues – Parallel computation models(1) ▪ PRAM(Parallel Random Access Memory) ▪ SIMD-SM, Used for fine grain parallel computing, Centralized shared memory, Globally synchronized. ▪ Advantages ▪ Suitable for representing and analyzing complexity of parallel algorithms, Simple to use , hiding the most of lowlevel details of parallel computer (communication, synchronization etc. ). ▪ Disadvantages ▪ Unsuitable for MIMD computers, Unrealistic to neglect the issues of memory contention, communication delay etc
中种学林水学计算机科学与术系 versity ResearchhIssuesna parallel computation models(2) Asynchronous PRAM APRAM or MIMD-SM, Used for medium grain parallel computation centralized shared memory asynchronous operation, Read/write shared variable communication, Explicit synchronous(barrier, etc. Computation in APRAM Computation Consists of global phases separated by barriers: in a phase all processors execute operation asynchronized the last instruction must be a synchronization instruction Advantages: Preserving much of simplicity of PRAM, better programmability, program must be correctness, easy to analyze complexity Disadvantages: Unsuitable for MIMD computers with distributed memory NHPCC at Hefei 2021/2/6 10
NHPCC at Hefei 10 2021/2/6 Research Issues – Parallel computation models(2) ▪ Asynchronous PRAM ▪ APRAM or MIMD-SM, Used for medium grain parallel computation, Centralized shared memory, Asynchronous operation, Read/write shared variable communication, Explicit synchronous (barrier, etc.). ▪ Computation in APRAM ▪ Computation Consists of global phases separated by barriers: in a phase all processors execute operation asynchronized, the last instruction must be a synchronization instruction. ▪ Advantages: Preserving much of simplicity of PRAM, better programmability, program must be correctness, easy to analyze complexity. ▪ Disadvantages: Unsuitable for MIMD computers with distributed memory