香港中文大学(深圳)数据科学院 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
Programming with Shared Memory
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
3
4
Several Alternatives for Programming (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
4
5
Several Alternatives for Programming (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
5
6
Creating Concurrent Process – FORK-JOIN Construct
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
6
7
UNIX Heavyweight Processes (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
7
8
UNIX Heavyweight Processes (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
8
9
Thread
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
9
10
Pthread
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
10
11
Pthread Barrier
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
11
12
Detached Threads
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
12
13
Statement Execution Order (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
13
14
Statement Execution Order (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
14
15
Compiler/Processor Optimizations
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
15
16
Thread-Safe Routines
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
16
17
Accessing Shared Data
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
17
18
Critical Section
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
18
19
Locks
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
19
20
Spin Lock (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
20
21
Spin Lock (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
21
22
Pthread Lock Routines (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
22
23
Pthread Lock Routines (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
23
24
Deadlock (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
24
25
Deadlock (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
25
26
Pthread Lock Checking Routine
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
26
27
Semaphore
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
27
28
Mutual Exclusion of Critical Sections
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
28
29
General Semaphore (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
29
30
General Semaphore (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
30
31
Monitor
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
31
32
Condition Variables
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
32
33
Condition Variable Operations (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
33
34
Condition Variable Operations (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
34
35
Pthread Condition Variable
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
35
36
Language Constructs for Parallelism (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
36
37
Language Constructs for Parallelism (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
37
38
Dependency Analysis
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
38
39
Berstein’s Conditions
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
39
40
Example
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
40
41
Shared Data in System with Caches (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
41
42
Shared Data in System with Caches (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
42
43
Program Example (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
43
44
Program Example (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
44
45
Program Example (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
45
46
Program Example (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
46
47
Program Example (5)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
47
48
Program Example (6)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
48
49
Program Example (7)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
49
50
Program Example (8)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
50
51
Pthread Example (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
51
52
Pthread Example (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
52
53
Pthread Example (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
53
54
Pthread Example (4)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
54
55
Java Example (1)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
55
56
Java Example (2)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
56
57
Java Example (3)
National Tsing Hua University ® copyright OIA
香港中文大学（深圳）数据科学院
CUHK-SZ School of Data Science
57
/docProps/thumbnail.jpeg