Parallel Computing
Guoliang Chen
E-mail,glchen@ustc.edu.cn
国家高性能计算中心（合肥） 22009-7-24
可 计 算 性 与计 算 复 杂 性算 法 研 究 的数 学 基 础并 行 排 序 和选 择 算 法
V L S I 计 算 理 论与 并 行 算 法并 行 图 论 算 法分 布 式 算 法并 行 算 法 类 课程 教 学 网 站并 行 算 法 类课 程 实 践并 行 算 法 实 践并 行 计 算 机体 系 结 构并 行 计 算,
结 构,算 法,编 程高 性 能 计 算 导 论面 向 计 算 机专 业 博 士 生面 向 计 算 机 专 业 硕 士 生面 向 计 算 机 专 业 本 科 生或 计 算 科 学 的 研 究 生算 法 理 论算 法 设 计 与 分 析算 法 实 现算 法 应 用 基 础并 行 算 法 的 设 计 与 分 析国家高性能计算中心（合肥） 32009-7-24
Parallel Computing
Parallel Architectures
Parallel Algorithms
Parallel Programming
国家高性能计算中心（合肥） 42009-7-24
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.
国家高性能计算中心（合肥） 52009-7-24
Part I,Parallel Computer Systems
Hardware Platform for Parallel
Computing,
System Architectures and Models
System Interconnections
Performance Evaluation
国家高性能计算中心（合肥） 62009-7-24
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
国家高性能计算中心（合肥） 72009-7-24
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 )
国家高性能计算中心（合肥） 82009-7-24
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
国家高性能计算中心（合肥） 92009-7-24
Part II,Parallel Algorithms
Theoretical Base for Parallel
Computing,
Computational Models
Design Policy
Design Techniques
Design Methodology
Parallel Numerical Algorithms
国家高性能计算中心（合肥） 102009-7-24
Computational Models
PRAM,Parallel Random Access Machines
APRAM,Asynchronous PRAM
BSP,Bulk Synchronous Parallel
LogP,Latency,Overhead,Gap,
Processors
国家高性能计算中心（合肥） 112009-7-24
Design Policy
Parallelizing a Sequential Algorithm
Designing a new Parallel Algorithm
Borrowing Other Well-known Algorithm
国家高性能计算中心（合肥） 122009-7-24
Design Techniques
Balanced Trees
Doubling Technique
Partitioning Strategy
Divide and Conquer
Pipelining
国家高性能计算中心（合肥） 132009-7-24
Design Methodology
PCAM,Partitioning
PCAM,Communication
PCAM,Agglomeration
PCAM,Mapping
国家高性能计算中心（合肥） 142009-7-24
Parallel Numerical Algorithms
Dense Matrix Algorithms
Solving Systems of Linear Equations
Fast Fourier Transform
国家高性能计算中心（合肥） 152009-7-24
Part III,Parallel Programming
Software Support for Parallel Computing,
Programming Models
Shared-Memory Programming
Message-Passing Programming
Data-Parallel Programming
Programming Environment and Tools
国家高性能计算中心（合肥） 162009-7-24
Programming Models
Implicit Model
Data-Parallel Model
Shared-Memory Model
Message-Passing Model
国家高性能计算中心（合肥） 172009-7-24
Shared-Memory Programming
ANSI X3H5
POSIX Threads( Pthreads )
OpenMP
Shared-Variable Parallel Code to Compute
Pi
国家高性能计算中心（合肥） 182009-7-24
Message-Passing Programming
MPI,Message-Passing Interface
MPI Basics
Message-Passing Code to Compute Pi
PVM,Parallel Virtual Machine
PVM Program to Compute Pi
国家高性能计算中心（合肥） 192009-7-24
Data-Parallel Programming
HPF,High-Performance Fortran
Gaussian Elimination in HPF
国家高性能计算中心（合肥） 202009-7-24
Programming Environment and Tools
Parallelizing Compiler
Two Ways to Parallelize Compiler
SIMDizing,Vectoring
MIMDizing,Parallelizing
Dependency Analysis
Performance Analysis
Performace Prediction
Performace Monitoring
Performace Visualization
国家高性能计算中心（合肥） 212009-7-24
Programming Environment and Tools
Parallel Program Debugging
Correct Debugging
Performance Debugging
Graphical Development Environment for Parallel
Programming
Graphical Editor and Language
Pre-Compilation
Mapping
Debugging and Monitoring
国家高性能计算中心（合肥） 222009-7-24
Guoliang Chen
E-mail,glchen@ustc.edu.cn
国家高性能计算中心（合肥） 22009-7-24
可 计 算 性 与计 算 复 杂 性算 法 研 究 的数 学 基 础并 行 排 序 和选 择 算 法
V L S I 计 算 理 论与 并 行 算 法并 行 图 论 算 法分 布 式 算 法并 行 算 法 类 课程 教 学 网 站并 行 算 法 类课 程 实 践并 行 算 法 实 践并 行 计 算 机体 系 结 构并 行 计 算,
结 构,算 法,编 程高 性 能 计 算 导 论面 向 计 算 机专 业 博 士 生面 向 计 算 机 专 业 硕 士 生面 向 计 算 机 专 业 本 科 生或 计 算 科 学 的 研 究 生算 法 理 论算 法 设 计 与 分 析算 法 实 现算 法 应 用 基 础并 行 算 法 的 设 计 与 分 析国家高性能计算中心（合肥） 32009-7-24
Parallel Computing
Parallel Architectures
Parallel Algorithms
Parallel Programming
国家高性能计算中心（合肥） 42009-7-24
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.
国家高性能计算中心（合肥） 52009-7-24
Part I,Parallel Computer Systems
Hardware Platform for Parallel
Computing,
System Architectures and Models
System Interconnections
Performance Evaluation
国家高性能计算中心（合肥） 62009-7-24
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
国家高性能计算中心（合肥） 72009-7-24
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 )
国家高性能计算中心（合肥） 82009-7-24
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
国家高性能计算中心（合肥） 92009-7-24
Part II,Parallel Algorithms
Theoretical Base for Parallel
Computing,
Computational Models
Design Policy
Design Techniques
Design Methodology
Parallel Numerical Algorithms
国家高性能计算中心（合肥） 102009-7-24
Computational Models
PRAM,Parallel Random Access Machines
APRAM,Asynchronous PRAM
BSP,Bulk Synchronous Parallel
LogP,Latency,Overhead,Gap,
Processors
国家高性能计算中心（合肥） 112009-7-24
Design Policy
Parallelizing a Sequential Algorithm
Designing a new Parallel Algorithm
Borrowing Other Well-known Algorithm
国家高性能计算中心（合肥） 122009-7-24
Design Techniques
Balanced Trees
Doubling Technique
Partitioning Strategy
Divide and Conquer
Pipelining
国家高性能计算中心（合肥） 132009-7-24
Design Methodology
PCAM,Partitioning
PCAM,Communication
PCAM,Agglomeration
PCAM,Mapping
国家高性能计算中心（合肥） 142009-7-24
Parallel Numerical Algorithms
Dense Matrix Algorithms
Solving Systems of Linear Equations
Fast Fourier Transform
国家高性能计算中心（合肥） 152009-7-24
Part III,Parallel Programming
Software Support for Parallel Computing,
Programming Models
Shared-Memory Programming
Message-Passing Programming
Data-Parallel Programming
Programming Environment and Tools
国家高性能计算中心（合肥） 162009-7-24
Programming Models
Implicit Model
Data-Parallel Model
Shared-Memory Model
Message-Passing Model
国家高性能计算中心（合肥） 172009-7-24
Shared-Memory Programming
ANSI X3H5
POSIX Threads( Pthreads )
OpenMP
Shared-Variable Parallel Code to Compute
Pi
国家高性能计算中心（合肥） 182009-7-24
Message-Passing Programming
MPI,Message-Passing Interface
MPI Basics
Message-Passing Code to Compute Pi
PVM,Parallel Virtual Machine
PVM Program to Compute Pi
国家高性能计算中心（合肥） 192009-7-24
Data-Parallel Programming
HPF,High-Performance Fortran
Gaussian Elimination in HPF
国家高性能计算中心（合肥） 202009-7-24
Programming Environment and Tools
Parallelizing Compiler
Two Ways to Parallelize Compiler
SIMDizing,Vectoring
MIMDizing,Parallelizing
Dependency Analysis
Performance Analysis
Performace Prediction
Performace Monitoring
Performace Visualization
国家高性能计算中心（合肥） 212009-7-24
Programming Environment and Tools
Parallel Program Debugging
Correct Debugging
Performance Debugging
Graphical Development Environment for Parallel
Programming
Graphical Editor and Language
Pre-Compilation
Mapping
Debugging and Monitoring
国家高性能计算中心（合肥） 222009-7-24
