Giới thiệu về tính toán song song
ỗ ị
Đ Thanh Ngh dtnghi@cit.ctu.edu.vn
ộ
N i dung
ệ
ớ
i thi u ậ
ệ
Gi Mô hình l p trình song song Giao di n MPI
2
ộ
N i dung
ệ
ớ
i thi u ậ
ệ
Gi Mô hình l p trình song song Giao di n MPI
3
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ầ
ề Yêu c u v tính toán
ề
ự
ấ ầ
ộ
ử ổ ồ
ự ỏ ọ
ữ ệ ờ ề ơ ờ
ệ
ễ ề Nhi u v n đ trong th c ti n ề ố Yêu c u v t c đ tính toán X lý và tính toán d li u kh ng l ế Mô ph ng, d báo th i ti t, thiên văn, sinh h c, etc ầ Máy tính đ n: c n nhi u th i gian ề Máy tính song song (nhi u CPU), PC cluster (nhóm ự máy tính), Grid (l ờ nhi u CPU => tăng t c (th i gian tính toán ng n)
4
ướ i): th c hi n song song trên ố ề ắ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ầ
ề Nhu c u v tính toán
ầ
ờ D báo th i ti t toàn c u
ế ớ ử
ự ữ ệ
ồ ầ
ổ ư ự ầ ả
ự D li u càng l n => d báo càng chính xác ữ ệ Phân tích và x lý hàng Petabytes d li u Yêu c u tính toán kh ng l ệ ơ Máy tính đ n: g n nh không có kh năng th c hi n Máy tính song song: chi phí cao PC cluster, Grid: chi phí th p
(1): 1 Kb = 1000 bytes, 1 Mb = 10002 bytes, 1 Gb = 10003 bytes, 1 Tb = 10004 bytes, 1 Pb = 10005 bytes, 1 Eb = 10006 bytes, 1 Zb = 10007 bytes, 1 Yb = 10008 bytes
5
ấ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ầ
ề Nhu c u v tính toán
ệ Công nghi p khai thác m ị
ứ ạ ấ ậ
ỏ ữ ệ ớ Thăm dò đ a ch n: d li u l n, gi i thu t ph c t p ứ Mô ph ng m : nghiên c u tác đ ng quá trình khai thác
6
ả ộ ỏ ỏ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ầ
ề Nhu c u v tính toán
ặ ặ
Sinh tin h cọ ắ ắ ự ự ươ
ệ
7
ự B t c p trình t ấ B t c p c u trúc protein ấ D đoán c u trúc protein ể D đoán bi u hi n gen T ng tác protein - protein
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ầ
ề Nhu c u v tính toán
ữ ệ Khám phá tri th c và khai thác d li u ữ ệ
ừ ọ ổ ồ
ệ
ờ ự ự ọ ề ế ả
ứ ứ Khám phá tri th c quan tr ng t kho d li u kh ng l ọ ọ Phát hi n quan tr ng trong khoa h c D báo chính xác v th i ti t và các th m h a t nhiên ề Xác đ nh đ c nguyên nhân và ph ng pháp đi u tr các
ươ ị
ượ ể căn b nh hi m nghèo
ự
8
ứ ư ự ổ ị ệ ạ ị D báo d ch h i ạ ậ Nh n d ng ế Tìm ki m thông tin ữ T t ch c l u tr thông tin
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ự
Tính toán tu n tầ
ễ ề Nhi u v n đ trong th c ti n
ề ứ
ấ ạ
ộ
ự ề ố ầ Ph c t p, yêu c u v t c đ tính toán ự Tính toán tu n t (1 CPU): c n nhi u th i gian
9
ờ ề ầ ầ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tính toán song song
ề
Tính toán song song trên nhi u CPU ươ V n đ đ c chia thành nhi u ph n t
ộ ề ầ
ề ượ ượ ố ng đ i đ c ố ờ ự ồ ệ
10
ấ ậ l p và đ c th c hi n đ ng th i: tăng t c tính toán
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tính toán song song
ượ
ề
ế
ờ
ồ
ả
ạ
ố
ề
ề
ệ
ấ
ộ ộ ử
ồ Quá trình tính toán g m nhi u ti n trình đ c ế kích ho t đ ng th i và cùng tham gia gi i quy t m t bài toán / v n đ trên h th ng có nhi u b x lý
11
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ạ
T i sao tính toán song song?
ủ
ầ Yêu c u c a ng
ườ ộ
i dùng: ố ượ ệ C n th c hi n m t kh i l ử Th i gian x lý ph i nhanh
ệ ớ ự ầ ng công vi c l n
ễ
ờ ầ
ự ể ạ
ả Yêu c u th c ti n: ộ ớ ộ ớ Không th t o m t máy tính v i tài nguyên b nh
ạ ả
ệ ử ầ ự Hi n đang có r t nhi u bài toán mà x lý tu n t
và kh năng tính toán vô h n ấ ứ ể
ề ượ không đ đáp ng đ c ệ ẽ ề ố Vi c tính toán trên h th ng có nhi u CPU s nhanh
ố ệ ệ ơ h n trên h th ng có 1 CPU
ượ ớ ẽ ế ả Tính toán song song s gi i quy t đ c bài toán l n,
12
ứ ạ ph c t p
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tài nguyên tính toán song song
ề
ộ
ề
ộ ử ạ
ố
ế
ử
ộ
ề
ộ ầ
ứ
ơ M t máy tính đ n có nhi u b x lý ượ Nhi u máy tính đ c k t n i m ng M t siêu máy tính có nhi u b đa x lý ệ Ph n c ng chuyên bi t
Field-Programmable Gate Array (FPGA) ủ B x lý đa năng c a card đ h a (GPU) ạ ự ế
ợ
ể
ế
ị Ho c có th là s k t h p c a các lo i thi t b
ồ ọ ủ
13
ộ ử ặ ư nh trên
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ứ
Hình th c tính toán song song
ữ
Tính toán song song: ấ Song song c p bit ệ ấ Song song c p l nh (ngôn ng LT) ữ ệ Song song d li u ụ Song song tác v (ch
14
ươ ng trình con)
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
PC cluster
15
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
PC cluster
PC cluster
ạ
ẳ ủ ộ ạ ố ế
ủ Đ c tr ng c a PC cluster
ỗ ượ ượ ơ
ấ
ư ử ụ ạ ả ầ
ộ ị
ớ ệ
16
ề ệ ả ư Nhóm các nút tính toán (ch ng h n nh PC) ề ệ M i nút ch y h đi u hành c a riêng nó ộ ố ụ Đ c n i k t c c b (t c đ cao) ư ộ Đ c xem nh m t “siêu” máy tính đ n ặ S d ng các microprocessor: chi phí th p ố M ng t c đ cao ỏ ự Kh năng ch u đ ng h ng hóc Ph n m m tính toán phân tán v i hi u năng cao Giao di n MPI: qu n lý tính toán trên cluster
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ướ
L
i (Grid)
17
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ướ
L
i (Grid)
ớ
Gi
ề ướ i
ệ i thi u v l ợ ậ
ố ư ữ ạ ệ
ố ố ế
ố ệ ệ ậ ạ
ơ
ề ư ộ ự ị
ượ ả ầ ớ ệ
T p h p các tài nguyên đa d ng Siêu máy tính, PC clusters, h th ng l u tr ộ ượ Đ c n i k t t c đ cao Chia sẻ Phân tán Đa d ng: h đi u hành, h th ng t p tin Đ c xem nh m t “siêu” máy tính đ n ỏ Kh năng ch u đ ng h ng hóc Ph n m m tính toán phân tán v i hi u năng cao Giao di n MPI: qu n lý tính toán trên cluster
18
ề ệ ả
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ướ
L
i (Grid)
ệ ng d ng: nhi u công vi c th c thi song song trên
Khái ni mệ ự ề ụ Ứ ủ ướ nhi u máy tính khác nhau c a l
ề i
ề ậ ự ố ệ ử ụ Đăng ký s d ng tài nguyên ấ ườ ị L p l ch: ng i dùng đ xu t hay h th ng t tìm tài
nguyên thích h p ợ
H th ng phân công vi c đ n các tài nguyên nh l ch
H th ng qu n lý: theo dõi tài nguyên s n dùng,
ư ị ệ ế
ườ ệ ố ệ đã l pậ ệ ố ạ ả ệ
19
ứ ự ẵ i dùng ậ ạ ủ tr ng thái hi n t i c a công vi c, ng ự An ninh: ch ng th c, xác th c, đăng nh p
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ướ
L
i (Grid)
ờ
ợ L i ích ệ Ti t ki m th i gian và tài nguyên Th c thi m t ch
ế ự ộ ề ng trình song song trên nhi u
ươ máy tính khác nhau
ậ ụ ỗ ạ
T n d ng tài nguyên nhàn r i trên m ng: CPU, đĩa Tài nguyên o: t n d ng t t c tài nguyên không
ụ ậ ả ấ ả
ồ
ấ đ ng nh t ằ
ộ ự ỏ ậ ị
20
ễ ả ả ả ử ụ Cân b ng t i s d ng tài nguyên ả Đ tin c y: kh năng ch u đ ng h ng hóc Chi phí th pấ D b o trì, qu n lý
ộ
N i dung
ệ
ớ
i thi u
ệ
Gi Các mô hình tính toán song song Giao di n MPI
21
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ế
ứ
ầ
ệ Giao di n MPI
Ki n trúc ph n c ng Mô hình von Neumann
22
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ế
ầ
ệ Giao di n MPI
ứ Ki n trúc ph n c ng Symmetric Multiprocessor (SMP)
23
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ế
ầ
ệ Giao di n MPI
ứ Ki n trúc ph n c ng Massively Parallel Processors (MPP)
24
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ậ
Mô hình l p trình (SMP)
25
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ậ
Mô hình l p trình (simple MPP)
26
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ậ
Mô hình l p trình (hybrid MPP)
27
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ậ
Mô hình l p trình (hybrid MPP)
28
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ậ
Mô hình l p trình (SPMD)
29
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ậ
Mô hình l p trình (MPMD)
30
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ế
ế
ả
ậ
Thi t k gi i thu t song song
ồ
ụ
ị
ướ
Mô hình tác v /kênh: đ th có h
ng
31
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ế
ế
ậ
ả
Thi t k gi i thu t song song
Mô hình Foster Phân ho chạ Giao ti p ế ổ T ng h p Ánh xạ
32
ợ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ế
ế
ả
ậ
Thi t k gi i thu t song song
ụ
ữ ả
ộ ử ừ ủ ụ
ạ Phân ho ch ữ ệ D li u ứ Ch c năng tính toán #tác v >= #b x lý ư ể Gi m thi u d th a trong tính toán và l u tr ướ Tác v nguyên th y có kích th #tác v là hàm tăng theo kích th
33
ụ ề ư ằ ầ c g n b ng nhau ấ ướ c v n đ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ế
ế
ậ
ả
Thi t k gi i thu t song song
Giao ti p ế
ế ữ ệ ượ ậ ả
ằ
ụ ế ỗ
ề ậ ự ế ề ề Thao tác giao ti p truy n nh n d li u ph i đ c ụ ữ cân b ng gi a các tác v ớ ố M i tác v giao ti p v i s ít các tác v láng gi ng ệ Các tác v có th th c hi n giao ti p truy n nh n
ữ ệ
ứ ự ệ Các tác v có th th c hi n các ch c năng tính toán
34
ồ ụ ể ụ ồ ờ d li u đ ng th i ể ụ ờ đ ng th i
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ế
ế
ả
ậ
Thi t k gi i thu t song song
T ng h p
ữ ệ ả
ợ ổ ộ Tăng tính c c bụ Chi phí tính toán vs chi phí giao ti pế ỏ Nhân b n d li u đ nh ụ Các tác v thu đ c sau t ng h p có chi phí tính
ủ ượ ổ
ự ế ề
ư ể
ả ố ượ ụ ầ ằ ặ ợ ươ ng t toán và giao ti p truy n thông t ấ ỏ ng tác v c n gi m nh nh t có th nh ng ộ ử ng b x lý, không gây
ố ượ #S l ả ớ ấ ơ ph i l n h n ho c b ng s l ả ằ ra m t cân b ng t i
C n th a hi p gi a vi c th c hi n đ ng th i và chi
ờ ữ ự ỏ ồ ệ ệ ệ ầ
phí thông tin liên l cạ
C n dung hòa gi a s t ng h p và chi phí cho vi c
ệ ầ ự ổ
35
ữ ươ ự ệ ợ ầ ng trình tu n t hi n có ổ thay đ i mã ch
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ế
ế
ậ
ả
Thi t k gi i thu t song song
Ánh x ạ ị
ơ ượ ự
ụ ạ ộ ả ủ ỗ ỗ Xác đ nh đ c n i mà m i tác v th c thi ế Hi u qu c a 2 thi t k : ánh x m t tác v cho m i
ụ ộ ử ỗ ụ ề
ế b x lý, ánh x nhi u tác v cho m i b x lý ụ ệ ộ ử ệ ạ ấ ộ Hi u qu c a c p phát đ ng và tĩnh các tác v trên
ả
Khi s d ng mô hình cân b ng t i t p trung, chúng ẽ
ả ủ ộ ử các b x lý ử ụ ầ ậ ị ạ
36
ổ ằ ả ta c n xem xét tác v qu n lý có b tình tr ng ngh n c chai hay không? ụ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tính s PIố
1
arctan(
)1
4
2 dx
4 x 1
0
37
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tính s PIố
38
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tính s PIố
b9
b10
b5
b6
b7
b8
b1
b2
b3
b4
39
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
Tính s PIố
ậ k tác v ụ
ữ k hình ch nh t => ổ ế
ổ
Mô hình Foster Phân ho ch: ề ả Giao ti p: truy n k t qu => t ng ộ ử T ng h p: Ánh x : cân b ng t i gi a
40
ạ ế ợ k >= np b x lý ạ ằ ả ộ ử ữ np b x lý
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ệ
Hi u năng tính toán
ầ
ậ ị Đ nh lu t Gene Amdahl ự ự ỷ ệ α: t l th c thi tu n t ộ ử np: s l ng b x lý ố ố ả Kh năng tăng t c t i đa S
41
ố ượ
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ệ
Hi u năng tính toán
42
ộ
N i dung
ệ
ớ
i thi u
ệ
Gi Mô hình tính toán song song Giao di n MPI
43
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ươ
ng trình
ệ Giao di n MPI
ự
Mô hình ch tu n tầ
44
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ươ
ng trình
ệ Giao di n MPI
ệ
Mô hình ch ể chuy n thông đi p
45
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ng trình
ệ Giao di n MPI
ệ
ươ Mô hình ch ể chuy n thông đi p (SPMD)
46
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ệ
ể
Chuy n thông đi p
47
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ể
ệ
Chuy n thông đi p
48
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ệ Giao di n MPI (Message Passing Interface)
ệ
Giao di n MPI
ị
ả
ệ ể
ả Không ph i là trình biên d ch ẩ ả Không ph i là s n ph m ư ệ ẩ Đ c t chu n cho th vi n chuy n thông đi p S d ng cho các máy tính song song, PC cluster,
ả ặ ử ụ ạ ạ
ề ầ
49
ỗ m ng h n t p ể ấ ư ệ Phát tri n th vi n ph n m m song song ứ ầ Truy xu t ph n c ng song song
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ử
ể
Lich s phát tri n MPI
ệ
Giao di n MPI
Version 1.0 (06/1994): 40 t ch c, t p đoàn, công
ứ ổ ậ
ị
ư ệ ty (IBM, Intel, Cray, TMC, etc) tham gia đ nh nghĩa th vi n hàm MPI
ổ ỏ ề Version 1.1 (06/1995), 1.2 (1997): thay đ i nh v
ấ ề
Version 2.0 (07/1997): b sung thêm qu n lý ti n
tính nh t quán v tên hàm ổ ế
ộ ố ế
ợ ố ỉ ơ ả trình đ ng, k t n i, vào/ra song song, etc. Version 2.1 (06/2008): hoàn ch nh MPI 2.0 ỗ Version 3 (2012): h tr t t h n many-core, máy
50
tính song song
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ệ Giao di n MPI
ả
ế
ự ớ
ể ậ
ế
ệ Giao di n MPI qu n lý ườ Môi tr ng th c thi các ti n trình ể ố ế N i k t đi m t i đi m (point-point) ợ ố ế N i k t t p h p (communication collective) ố ế Nhóm các ti n trình, k t n i Truy n thông đi p theo topo
51
ệ ề
ớ
ệ
Gi
i thi u
ậ
Mô hình l p trình song song
ệ Giao di n MPI
ệ Giao di n MPI
ệ
Giao di n MPI ế
Trong th c t , là các hàm C/C++, các ch
ự ươ ng trình
Ba th vi n: MPICH-2, OpenMPI, LAM-MPI
con Fortran
ỉ ớ ượ ế ng trình song song đ c vi t ch v i 6
ơ ả MPI đ y đầ
ư ệ ợ
ế ế ắ ả ầ
52
ư ệ ư ệ ả ơ MPI đ n gi n ươ ề Nhi u ch hàm c b n ủ ỗ Th vi n h tr 125 hàm ể ử ụ Có th s d ng mà không c n thi t ph i n m h t ả ề ấ t t c v th vi n
ệ
ả
Tài li u tham kh o
1. Argonne National Lab. MPICH2 : High-performance and Widely
Portable MPI. 2012. http://www.mcs.anl.gov/research/projects/mpich2/.
2. P. Pacheco. An Introduction to Parallel Programming. Morgan
Kaufmann, 2011.
3. William Gropp. Tutorial on MPI: The Message-Passing
Interface. 1995.
ỗ
ỗ
ệ
ị
ậ
4. Đ Thanh Ngh , Nguy n Văn Hòa, Đ Hi p Thu n.
ậ L p trình
ơ
ầ
ễ ạ ọ song song. NXB Đ i h c C n th , 2014.
53
Cám n ơ
54