香港中文大学(深圳)数据科学院 School of Data Science
CSC4005 – Distributed and Parallel Computing
Prof. Yeh-Ching Chung
School of Data Science
Chinese University of Hong Kong, Shenzhen
1
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
Outline
2
Introduction to Parallel Computers
Message Passing Computing and Programming
Multithreaded Programming
OpenMP Programming
Embarrassingly Parallel Computations
Partitioning and Divide-and-Conquer Strategies
Pipelined Computations
Synchronous Computations
Load Balancing and Termination Detection
Sorting Algorithms
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
2
3
Parallel Computers
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
3
4
Weather Forecast
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
4
5
Modeling Motion of Astronomical Bodies (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
5
6
Modeling Motion of Astronomical Bodies (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
6
7
Parallel Computers and Programming
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
7
8
Types of Parallel Computers
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
8
9
Shared Memory Multiprocessor Systems
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
9
10
Programming Shared Memory Multiprocessor
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
10
11
Message Passing Multiprocessor Systems
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
11
12
Programming
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
12
13
Distributed Shared Memory
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
13
14
MIMD and SIMD Classifications
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
14
15
Single Instruction Streaming-Multiple Data Streaming (SIMD) Computers
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
15
16
Multiple Program Multiple Data Streaming (MPMD) Structure
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
16
17
Single Program Multiple Data (SPMD) Structure
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
17
18
Message-Passing Multicomputers (1)
Static network message-passing multicomputers
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
18
19
Message-Passing Multicomputers (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
19
20
Message-Passing Multicomputers (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
20
21
Network Criteria
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
21
22
Interconnection Networks (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
22
23
Interconnection Networks (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
23
24
Embedding (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
24
25
Embedding (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
25
26
Embedding (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
26
27
Communication Methods – Circuit Switching
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
27
28
Communication Methods – Packing Switching
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
28
29
Communication Methods – Virtual Cut-Through
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
29
30
Communication Methods – Wormhole Routing (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
30
31
Communication Methods – Wormhole Routing (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
31
32
Communication Methods – Wormhole Routing (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
32
33
Deadlock
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
33
34
Virtual Channel
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
34
35
Network Computers as a Multicomputer Platform
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
35
36
Ring Structures
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
36
37
Point-to-Point Communication
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
37
38
Overlapping Connectivity Networks
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
38
39
Speedup Factor
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
39
40
Super-linear Speedup
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
40
41
Space-Time Diagram
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
41
42
Amdahl’s Law (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
42
43
Amdahl’s Law (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
43
44
Amdahl’s Law (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
44
45
Efficiency
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
45
46
Cost
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
46
47
Scalability
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
47
48
Problem Size
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
48
49
Gustafson’s Law
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
49
/docProps/thumbnail.jpeg