香港中文大学(深圳)数据科学院 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
Load Balancing and Termination Detection (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
3
4
Load Balancing and Termination Detection (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
4
5
Static Load Balancing (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
5
6
Static Load Balancing (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
6
7
Processes and Processors
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
7
8
Dynamic Load Balancing (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
8
9
Dynamic Load Balancing (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
9
10
Dynamic Load Balancing (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
10
11
Dynamic Load Balancing (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
11
12
Dynamic Load Balancing (5)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
12
13
Decentralized Dynamic Load Balancing (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
13
14
Decentralized Dynamic Load Balancing (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
14
15
Task Transfer Mechanisms (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
15
16
Task Transfer Mechanisms (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
16
17
Task Transfer Mechanisms (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
17
18
Task Transfer Mechanisms (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
18
19
Load Balancing Using a Line Structure (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
19
20
Load Balancing Using a Line Structure (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
20
21
Load Balancing Using a Line Structure (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
21
22
Load Balancing Using a Line Structure (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
22
23
Load Balancing Using a Line Structure (5)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
23
24
Load Balancing Using A Tree Structure
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
24
25
Nonblocking Receive Routines
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
25
26
Distributed Termination Detections (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
26
27
Distributed Termination Detections (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
27
28
Distributed Termination Detections (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
28
29
Ring Termination Algorithms (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
29
30
Ring Termination Algorithms (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
30
31
Ring Termination Algorithms (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
31
32
Dual-Pass Ring Termination Algorithm (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
32
33
Dual-Pass Ring Termination Algorithm (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
33
34
Dual-Pass Ring Termination Algorithm (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
34
35
Tree Algorithm (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
35
36
Fixed Energy Distributed Termination Algorithm
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
36
37
Shortest Path Problem (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
37
38
Shortest Path Problem (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
38
39
Shortest Path Problem (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
39
40
Shortest Path Problem (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
40
41
Shortest Path Problem (5)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
41
42
Shortest Path Problem (6)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
42
43
Shortest Path Problem (7)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
43
44
Searching a Graph (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
44
45
Searching a Graph (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
45
46
Searching a Graph (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
46
47
Searching a Graph (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
47
48
Searching a Graph (5)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
48
49
Searching a Graph (6)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
49
50
Searching a Graph (7)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
50
51
Searching a Graph (8)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
51
52
Searching a Graph (9)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
52
53
Searching a Graph (10)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
53
54
Searching a Graph (11)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
54
55
Searching a Graph (12)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
55
56
Searching a Graph (13)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
56
57
Searching a Graph (14)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
57
58
Searching a Graph (15)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
58
59
Searching a Graph (16)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
59
60
Searching a Graph (17)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
60
61
Searching a Graph (18)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
61
62
Searching a Graph (19)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
62
63
Searching a Graph (20)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
63
/docProps/thumbnail.jpeg