香港中文大学(深圳)数据科学院 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
Message-Passing Computing
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
3
4
Goals
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
4
5
Single Program Multiple Data (SPMD) Model
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
5
6
Multiple Program Multiple Data (MPMD) Model
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
6
7
Basic Send and Receive Routines
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
7
8
Synchronous Message Passing (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
8
9
Synchronous Message Passing (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
9
10
Blocking and Nonblocking Message Passing
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
10
11
MPI Definitions pf Blocking and Nonblocking
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
11
12
How Message-Passing Routines Can Return Before the Message Transfer Has Been Completed
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
12
13
Message Tag
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
13
14
Broadcast
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
14
15
Scatter
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
15
16
Gather
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
16
17
Reduce
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
17
18
Using Workstation Clusters – Software Tools
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
18
19
PVM (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
19
20
PVM (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
20
21
PVM (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
21
22
Basic Message-Passing Routines (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
22
23
Basic Message-Passing Routines (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
23
24
Sending Data Composed of Various Types
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
24
25
Broadcast, Multicast, Scatter, Gather, and Reduce
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
25
26
Example – PVM Program (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
26
27
Example – PVM Program (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
27
28
MPI
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
28
29
Using the SPMD Computational Model
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
29
30
Global and Local Variables
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
30
31
Unsafe Message Passing with Library
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
31
32
MPI Solution
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
32
33
Communication Types
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
33
34
Point-to-Point Communication
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
34
35
MPI Blocking Send and Receive
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
35
36
Example
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
36
37
Nonblocking Routines
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
37
38
Example
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
38
39
Send Communication Modes
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
39
40
Collective Communication
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
40
41
Example
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
41
42
Barrier
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
42
43
Example
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
43
44
Pseudocode Constructs
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
44
45
Time Complexity of MPI Program
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
45
46
Communication Time
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
46
47
Important Note on Interpretation of Equations
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
47
48
Latency Hidden
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
48
49
Time Complexity (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
49
50
Time Complexity (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
50
51
Time Complexity (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
51
52
Example
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
52
53
Time Complexity of a Parallel Algorithm
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
53
54
Cost Optimal Algorithms
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
54
55
Time Complexity of Broadcast (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
55
56
Time Complexity of Broadcast (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
56
57
Time Complexity of Broadcast (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
57
58
Time Complexity of Broadcast (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
58
59
Broadcast on a Workstation Cluster
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
59
60
1-to-N Fan-Out Broadcast
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
60
61
1-to-N Fan-Out Broadcast on a Tree
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
61
62
Gather on a Hypercube Network
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
62
63
Debugging and Evaluating Parallel Programs
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
63
64
Debugging Strategies
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
64
65
Evaluating Programs Empirically
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
65
66
Communication Time by the Ping-Pong Method
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
66
67
Profiling
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
67
/docProps/thumbnail.jpeg