中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Parallel Computing Guoliang Chen E-mailglchen@ustc.edu.cn
Parallel Computing Guoliang Chen E-mail : glchen@ustc.edu.cn
中国料学火计算机科学与波术系 versity of Science and Technology of China 算法理语rrF SrER SCIENCE AND TEC 专重 可计算性与 算法研究的 计算复杂性 数学基础 算法设计与分标并行排序和 选择算法 ⅥLSI计算理论并行图论算法分布式算法 与并行算法 面向讠 并行算法类课 并行算法类 程教学网站 并行算法的设计与分析 果程实践 算实现 并行算法实践 并行计算机 体系结构 或 算法应用基础 并行计算: 结构.算法.编程 高性能计算导论 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 2 2021/2/19 可计算性与 计算复杂性 算法研究的 数学基础 并行排序和 选择算法 VLSI计算理论 与并行算法 并行图论算法 分布式算法 并行算法类课 程教学网站 并行算法类 课程实践 并行算法实践 并行计算机 体系结构 并行计算： 结构.算法.编程 高性能计算导论 专业面博向士计生算机 面向计算机专业硕士生 或计 面算 向科 计学 算的 机研 专究 业生 本科生 算法理论 算法设计与分析 算法实现 算法应用基础 并行算法的设计与分析
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Parallel Computing Paralle/ architectures Parallel Algorithms Parallel programming 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 3 2021/2/19 Parallel Computing ▪ Parallel Architectures ▪ Parallel Algorithms ▪ Parallel Programming
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Abstract Generally speaking, parallel computing deals with the parallel computer architectures, parallel algorithms and parallel programming. In this lecture we will discuss briefly them separately In part I, we will discuss the contemporary parallel computer system architectures and memory access models, parallel system interconnections and parallel system performance evaluation. In part II we will discuss the parallel computational models, the design methods, techniques and methodology of parallel algorithms, as well as some parallel numerical algorithms In part III, we will discuss the parallel programming models, shared-memory, message-passing and dataparalle programming, as well as parallel programming environment and tools 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 4 2021/2/19 Abstract ▪ Generally speaking, parallel computing deals with the parallel computer architectures, parallel algorithms and parallel programming. In this lecture we will discuss briefly them separately. In part I, we will discuss the contemporary parallel computer system architectures and memory access models, parallel system interconnections and parallel system performance evaluation. In part II, we will discuss the parallel computational models, the design methods, techniques and methodology of parallel algorithms, as well as some parallel numerical algorithms. In part III, we will discuss the parallel programming models,shared-memory, message-passing and dataparallel programming, as well as parallel programming environment and tools
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Part I: Parallel Computer Systems Hardware Platform for parallel Computing: System Architectures and Models System Interconnections Performance Evaluation 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 5 2021/2/19 Part I : Parallel Computer Systems Hardware Platform for Parallel Computing: ▪ System Architectures and Models ▪ System Interconnections ▪ Performance Evaluation
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr System Architectures and Models Parallel computer System Architectures PVP: Parallel Vector Processors SMP: Symmetric Multiprocessors MPP: Massively Parallel Processors DSM: Distributed Shared Memory CoW: Cluster Of Workstations Parallel computer memory Access models UMA: Uniform Memory Access NUMA: Non-Uniform Memory Access COMA: Cache-Only Memory Access NORMA: NO-Remote Memory Access 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 6 2021/2/19 System Architectures and Models ▪ Parallel Computer System Architectures ▪ PVP : Parallel Vector Processors ▪ SMP : Symmetric Multiprocessors ▪ MPP : Massively Parallel Processors ▪ DSM : Distributed Shared Memory ▪ COW : Cluster Of Workstations ▪ Parallel Computer Memory Access Models ▪ UMA : Uniform Memory Access ▪ NUMA : Non-Uniform Memory Access ▪ COMA : Cache-Only Memory Access ▪ NORMA : NO-Remote Memory Access
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr System Interconnections Network Environments Intra-node Interconnections( Buses, Switches) Inter-node Interconnections(SAN) Inter-system Interconnections( LAN, MAN, WAN) Interconnection Topologies Static-Connection Networks(LA, RC, MC, TC, HC, CCC) Dynamic-Connection Networks(Buses, Crossbar, MIN) Wide-Band Networks FDDI( Fiber Distributed data Interface FE/GE( Fast Ethernet / Gigabit Ethernet) ATM( Asynchronous Transfer Mode SCI( Scalable Coherence Interface) 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 7 2021/2/19 System Interconnections ▪ Network Environments ▪ Intra-node Interconnections( Buses , Switches ) ▪ Inter-node Interconnections( SAN ) ▪ Inter-system Interconnections( LAN , MAN , WAN ) ▪ Interconnection Topologies ▪ Static-Connection Networks( LA,RC,MC,TC,HC,CCC) ▪ Dynamic-Connection Networks (Buses, Crossbar, MIN) ▪ Wide-Band Networks ▪ FDDI( Fiber Distributed Data Interface ) ▪ FE/GE( Fast Ethernet / Gigabit Ethernet ) ▪ ATM( Asynchronous Transfer Mode ) ▪ SCI( Scalable Coherence Interface )
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Performance evaluation Speed up of Systems Amdahl's Law Gustafson' s Law Sun and Ni's Law Scalability of Systems Iso-efficiency Iso-speed Average Latency Performance of systems: Benchmarks ■ LINPACK SPEC PARKBENCH NAS etc 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 8 2021/2/19 Performance Evaluation ▪ Speed up of Systems ▪ Amdahl’s Law ▪ Gustafson’s Law ▪ Sun and Ni’s Law ▪ Scalability of Systems ▪ Iso-efficiency ▪ Iso-speed ▪ Average Latency ▪ Performance of Systems : Benchmarks ▪ LINPACK ▪ SPEC ▪ PARKBENCH ▪ NAS etc
中国料学火计算机科学与波术系 niversity of Science and Technology of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Part II: Parallel algorithms Theoretical Base for Parallel Computing: Computational Models Design policy Design Techniques Design Methodology Parallel Numerical Algorithms 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 9 2021/2/19 Part II : Parallel Algorithms Theoretical Base for Parallel Computing: ▪ Computational Models ▪ Design Policy ▪ Design Techniques ▪ Design Methodology ▪ Parallel Numerical Algorithms
中国料学火计算机科学与波术系 niversity of Science and Technolo ogy of China DEAT三 NT OF C口 MPUTER SCIENGE AND TECHNOLOr Computational Models PRAM: Parallel Random Access Machines APRAM: Asynchronous PRAM BSP: Bulk Synchronous Parallel LogP: Latency Overhead, Gap Processors 国家高性能计算中心(合肥 2021/2/19
国家高性能计算中心（合肥） 10 2021/2/19 Computational Models ▪ PRAM : Parallel Random Access Machines ▪ APRAM : Asynchronous PRAM ▪ BSP : Bulk Synchronous Parallel ▪ LogP : Latency , Overhead , Gap , Processors