Bài giảng Giới thiệu về tính toán song song

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

ộ

N i dung

ệ

ớ

i thi u ậ

ệ

 Gi  Mô hình l p trình song song  Giao di n MPI



ớ

ệ

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)

ướ 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

ấ



ớ

ệ

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

ả ộ ỏ ỏ



ớ

ệ

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ọ ắ ắ ự ự ươ

ệ

ự  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

ự

ứ ư ự ổ ị ệ ạ ị  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

ờ ề ầ ầ



ớ

ệ

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 ố ờ ự ồ ệ

ấ ậ 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ý



ớ

ệ

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,

ứ ạ 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

ồ ọ ủ

ộ ử ặ ư 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

ươ ng trình con)



ớ

ệ

Gi

i thi u

ậ

 Mô hình l p trình song song



ệ Giao di n MPI

PC cluster



ớ

ệ

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

ỗ ượ ượ ơ

ấ

ư ử ụ ạ ả ầ

ộ ị

ớ ệ

ề ệ ả ư  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)



ớ

ệ

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

ề ệ ả



ớ

ệ

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ậ ệ ố ạ ả ệ

ứ ự ẵ 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 ằ

ộ ự ỏ ậ ị

ễ ả ả ả ử ụ  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



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song

ả

ậ

Thi t k gi i thu t song song

ồ

ụ

ị

ướ

 Mô hình tác v /kênh: đ th có h



ớ

ệ

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ạ

ợ



ớ

ệ

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

ụ ề ư ằ ầ c g n b ng nhau ấ ướ c v n đ



ớ

ệ

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

ồ ụ ể ụ ồ ờ d li u đ ng th i ể ụ ờ đ ng th i



ớ

ệ

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

ệ ầ ự ổ

ữ ươ ự ệ ợ ầ ng trình tu n t hi n có ổ thay đ i mã ch



ớ

ệ

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ý ử ụ ầ ậ ị ạ

ổ ằ ả 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? ụ



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song



ệ Giao di n MPI

Tính s PIố

arctan(

)1

4 



2 dx

4  x 1



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song



ệ Giao di n MPI

Tính s PIố



ệ 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

ố ượ



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song



ệ Giao di n MPI

ệ

Hi u năng tính toán

ộ

N i dung

ệ

ớ

i thi u

ệ

 Gi  Mô hình tính toán song song  Giao di n MPI



ớ

ệ

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ầ



ớ

ệ

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



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song

ng trình

ử

ể

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

tính song song



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song



ệ 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

ệ ề



ớ

ệ

i thi u

ậ

 Mô hình l p trình song song



ệ 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 đầ

ư ệ ợ

ế ế ắ ả ầ

ư ệ ư ệ ả ơ  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