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