Đề tài: ỨNG DỤNG LẬP TRÌNH SONG SONG GIẢI QUYẾT BÀI TOÁN SẮP XẾP BẰNG PHƯƠNG PHÁP TRỘN (MERGE SORT)

TI U LU N MÔN H C

Ọ

Ậ

Ể

CÁC K THU T HI N Đ I TRONG CNTT Ệ

Ậ

Ạ

Ỹ

N i dung: ộ

NG D NG L P TRÌNH SONG SONG GI I QUY T BÀI TOÁN

Ứ

Ụ

Ậ

Ả

Ế

NG PHÁP TR N (MERGE SORT)

S P X P B NG PH Ế Ằ

Ắ

ƯƠ

Ộ

Phú Th , tháng 05-2011 ọ

M C L C

Ụ

Ọ

TI U LU N MÔN H C 1 .................................................................................. Ể 1 ............................................. CÁC K THU T HI N Đ I TRONG CNTT Ệ Ậ Ỹ Ạ Ậ

LỜI M Đ U

Ở Ầ

ầ ữ ệ

ộ ớ ế ể ủ

ề ộ ử ả

ự

r ế ờ ố ấ ớ ớ ầ ấ ộ

Trong nh ng năm g n đây, m c dù n n Công ngh thông tin ặ i ngày m t phát tri n. T c đ x lí máy tính ngày càng ố ố ộ ặ t, d báo ự t l n, dù máy ả i ữ ệ ớ ộ ớ ẫ ầ ả ố ớ

c a th gi tăng lên. Tuy nhiên, chúng ta cũng g p ph i khó khăn trong m t s bài toán có d li u đ u vào l n (bài toán d báo th i ti ầ đ ng đ t, …). V i d li u đ u vào là m t con s ộ ữ ệ tính có t c đ l n, b nh nhi u v n v p ph i yêu c u ph i gi ấ ề ộ quy t bài toán trong th i gian ch p nh n đ ả c. ượ ế ấ ậ ờ

ệ ọ

ả ề ỏ

ề ệ i quy t các bài toán nh đ ả ả ế

ỏ ượ ớ ế đ ẽ ượ ế ệ ề ả ủ ồ ả

Trong nhi u năm qua, các nhà khoa h c đã nghĩ ra bi n pháp gi n quy t hi u qu đó là chia nh bài toán ra thành nhi u bài c ti n hành đ ng th i toán. Vi c gi ờ ế v i nhi u máy tính. K t qu c a bài toán l n s i quy t c gi ế ớ khi t t c các bài toán nh đã đ c làm. ượ ả ấ ỏ

Các máy tính ti n hành x lí song song đ c k t n i v i nhau ế ượ ế ố ớ

thành các c m tính toán t c đ cao. ụ ố ử ộ

N I DUNG Ộ

I.MÔ T GI I THU T Ả Ả Ậ SONG SONG

1. Gi ớ ệ

i ta th i quy t các bài toán l n ng i thi u Hi n nay, đ gi ệ ớ ế ườ ể ả

ớ ế ặ

ươ ể

ớ ng trình có th t n d ng đ ươ ể ượ ườ ể ề ng pháp l p trình c đi n thì không th nào phát ổ ể ượ ứ ệ ố c s c m nh c a các h th ng ủ ể ậ ụ ạ

ớ ậ ậ

thông th ờ ệ ấ ự

ệ thành ch ươ ả

ng nghĩ đ n vi c ệ s d ng các siêu máy tính ho c vi c k t h p nhi u máy tính v i nhau đ tính ệ ế ợ ử ụ toán. Tuy nhiên, v i ph ậ tri n đ c ch đó. Đó chính là lý do l p trình song song ra đ i. ậ ầ L p trình song song là m t công vi c r t ph c t p so v i l p trình tu n ứ ạ ộ i phát tri n ph i th c hi n m t quá trình “song song t ng, ng ả ự ộ ể ườ ng trình song song có kh ng trình tu n t hóa”, bi n đ i các ch ầ ự ổ ế i đa s c m nh c a h th ng. nănG t n d ng t ủ ệ ố ậ ụ ườ ươ ứ ạ ố

2. Nguyên lý thi t k thu t toán song song ế ế ậ

2.1. Cách th c xây d ng m t ch ng trình song song và phân b ứ ự ộ ươ ố

Phát tri n thu t toán là m t ph n quan tr ng trong vi c gi ọ ộ ầ ậ ể ệ

ộ ộ ử ụ

ề ỉ

ừ ả ơ

ậ ề ự ệ ử ụ ế ấ c m t thu t toán song song không đ n gi n ch ra t ng b ộ ậ ứ ộ i thi t k ra thu t toán cũng ph i ch ra t p h p nh ng b ả ộ ử ỉ ả ượ ậ ỉ ợ

ế ế ề ườ ờ ữ ủ ụ ả

ế ấ i quy t v n ả ả đ khi s d ng máy tính . M t thu t toán song song là m t ph i ng pháp gi ươ ề quy t v n đ d a trên vi c s d ng nhi u b x lý . Tuy nhiên đ ch ra ể c c th , mà là đ ướ ụ ể c them vào tính đ ng th i ờ ồ ử c x lý ướ c kh năng tính toán c a các máy tính ượ t k ra m t thu t toán song song là khá ế ế ự ế ậ ộ

ượ m t m c đ nào đó thu t toán song song ph i đ ậ ở ộ và ng ậ đ ng th i , đi u này s t n d ng đ ẽ ậ ồ vi c thi song song. Trên th c t ệ ph c t p,g m các công vi c: ứ ạ ệ ồ

ầ ủ ể ự ồ ỉ Ch ra ph n c a công vi c có th th c thi đ ng th i ờ ệ

ầ ủ ộ ử ệ ề ạ ạ Ánh x các ph n c a công vi c vào nhi u b x lý ch y song song

ng trình ữ ệ ậ ấ ớ ươ Phân tán d li u nh p, xu t và trung gian cùng v i ch

ộ ử ữ ả ậ Qu n lý truy c p vào d li u chung gi a các b x lý ữ ệ

ng trình song song ự ồ ộ ươ Đ ng b hóa các b x lý khi th c thi các ch ộ ử

2.2. Thi t k thu t toán song song ế ế ậ

ộ ậ ế ặ ụ

ổ ữ ệ ể ệ ồ ờ ớ

i m t bài toán đ t ra. Thu t toán song song là m t t p các ti n trình (process) ho c các tác v (task) có th th c hi n đ ng th i và có th trao đ i d li u v i nhau đ k t ể ế h p cùng gi ợ ậ ể ự ả ặ ộ

Thi ậ

ể ự ử ệ ộ

t k gi ế ế ả ỏ i thu t song song là quá trình song song hóa bài toán tu n t ỏ ơ i thu t song song là chia bài toán thành các bài toán nh h n và gán bài toán nh cho các b vi x lý khác nhau đ th c hi n song song.Quá . trình thi ầ ự t k gi ế ế ả ậ

i thu t song song bao g m: Nguyên lý c b n trong thi ơ ả t k gi ế ế ả ậ ồ

2.2.1. Nguyên lý l p l ch: ậ ị

i thi u các b x lý s d ng trong thu t toán sao cho th i gian ố ể ộ ử Gi m t ả

ử ụ ạ ộ

ậ ộ ứ ạ ờ ự ủ ậ

ng trình có th tăng khi s b x lý gi m, và th i gian tính toán t ng th ứ ạ ươ ể ả ờ ể

ờ tính toán là không tăng (xét theo khía c nh đ ph c t p). Nghĩa là, n u đ ế ệ ủ ph c t p tính toán c a thu t toán là O(f(n)) thì th i gian th c hi n c a ch ổ tăng lên m t h ng s nào đó - nh ng v n là O(f(n)). ố ộ ử ư ộ ằ ẫ ố

2.2.2. Nguyên lý hình ng:ố

Nguyên lý này đ c áp d ng khi bài toán xu t hi n m t dãy các thao tác ấ ượ

ộ ụ {T1, T2, . . ., Tn },trong đó Ti+1 th c hi n sau khi Ti k t thúc. ệ ế ự ệ

2.2.3. Nguyên lý chia đ tr :ể ị

T c là chia bài toán thành nh ng ph n nh h n t ữ

ng đ i đ c l p v i ớ ố ộ ậ ầ i quy t chúng m t cách song song. T o ra m t mô hình cây phân ỏ ơ ươ ộ ạ ế ả ộ

ứ nhau và gi c p đ phân c p quá trình truy n thông và tính toán. ấ ề ể ấ

- Tăng tính song song so v i mô hình tr ớ c ướ

- Th i gian ch y gi m t O(n) xu ng O(logn) ạ ả ờ ừ ố

2.2.4. Nguyên lý đ th ph thu c d li u: ồ ị ụ ộ ữ ệ

Phân tích m i quan h d li u trong tính toán đ xây d ng đ th ph ồ ị ụ ể

ự ệ ữ ệ thu c d li u và d a vào đó đ xây d ng thu t toán song song. ể ộ ữ ệ ố ự ự ậ

2.2.5. Nguyên lý đi u ki n t ng tranh: ệ ươ ề

N u hai ti n trình cùng mu n truy c p vào cùng m t m c d li u chia ụ ữ ệ ậ ố ộ

ở ẫ ng tranh v i nhau, nghĩa là chúng có th c n tr l n ể ả ớ

ế ế s thì chúng ph i t ả ươ ẻ nhau.

II. MÔ HÌNH L P TRÌNH TRUY N THÔNG ĐI P- CHU N MPI Ậ Ẩ Ề Ệ

1. Gi i thi u ớ ệ

Có r t nhi u ngôn ng l p trình và các th vi n đ ể ư ệ ượ ữ ậ ề ấ

c xây d ng nên đ ự ệ ậ ộ

ổ ấ ữ ượ ử ụ ề ấ ộ

ấ

c phân chia và nó ch h tr song song hóa t nó gi s không gian đ a ch đ ườ ng ỉ ỗ ọ ỉ ượ ả ử ị

dành cho l p trình song song. Mô hình l p trình truy n thông đi p là m t trong ậ nh ng mô hình c nh t và đ c s d ng r ng rãi nh t trong các mô hình dùng cho l p trình trên các máy tính song song. Mô hình này có hai tính ch t quan ậ tr ng đó là: ọ minh.

Môi tr ả ệ ề ườ ở ồ

ớ ễ

ẩ ả

ả 40 t ồ ố ữ

ạ ọ ữ ế ệ

ườ ồ ố ể ư ệ

ng truy n thông đi p LAM/MPI là phiên b n ngu n m , cung ế c p mi n phí v i chu n MPI. Chu n MPI (Message Passing Interface) là k t ẩ ấ ườ qu sau h n 2 năm th o lu n c a MPI Forum, 1 nhóm g m kho ng 60 ng i ơ ả ậ ủ ch c khác nhau đ i di n cho nh ng nhà phân ph i các h th ng song t ổ ứ ệ ố ệ ạ ừ ng đ i h c danh ti ng. song, nh ng phòng thí nghi m qu c gia và nh ng tr ữ MPI là m t th vi n các hàm có th chèn vào mã ngu n đ ề ữ ệ ữ ể truy n d li u gi a ộ các ti n trình. ế

2. Các khái ni m c b n ơ ả ệ

ể ề ộ ố ớ Communicator: M t nhóm các ti n trình có th truy n th ng v i nhau. ế

M t ti n trình có th thu c nhi u Communicator. ộ ộ ế ể ề

ỗ ế ọ ị

Rank: M i ti n trình trong 1 communicator có 1 đ nh danh, g i là Rank, ộ 0.M t ti n trình có th các rank khác nhau khi thu c ố ắ ầ ừ ộ ế ể

đánh s b t đ u t v các communicator khác nhau. ề

Group: là các nhóm x lýử

ử ế ộ v i ki u l p trình trên m t máy có m t ể ậ ớ ộ Process(ti n trình hay x lý):

c coi nh là m t ti n trình trong m t ch ộ ế ư ộ ươ ng

b x lý thì process đ ộ ử trình có không gian đ a ch riêng do h đi u hành cung c p. ượ ỉ ệ ề ấ ị

ng trình s d ng ph ng pháp l p trình ươ ử ụ ươ ạ Send/receive: Vì các ch

ẻ ế ụ ộ ớ

ề ế ả ị

ề ệ ữ ơ ế ử ậ ử

ấ Message passing không chia s vùng nh chung, hay bi n c c b mà t t c d li u đ u ph i giao ti p thông qua truy n thông. Do đó MPI đ nh ả ữ ệ nghĩa Send/receive là 2 c ch g i nh n thông đi p gi a các x lý trên máy khác nhau.

3. C u trúc ch ng trình MPI ấ ươ

Các t p tin t ậ ế

ủ ụ li u.Bao g m t p tin.h nh mpi.h, mpio.h,…C u trúc ch ể ư vi n: liên quan đ n các hàm và th t c , các ki u d a ng trình MPI: ư ệ ậ ươ ư ệ ấ ồ

Các t p tin th vi n ư ệ

ậ

Kh i t o môi tr

ng MPI

ở ạ

ườ

ệ

ủ ụ

Th c hi n các th t c hàm ự MPI

ườ

Thoát kh i môi tr ỏ III.BÀI TOÁN S P X P Ắ Ế

ọ ế ắ

c thành 1 dãy s tăng ho c gi m đ c gi ư ố ọ ặ ướ ả ọ

ượ ệ ề ế ấ

ộ Trong toán h c, cũng nh khoa h c máy tính thì bài toán s p x p m t ắ dãy s cho tr i là các bài toán s p ố x p. Vi c s p x p giúp ích r t nhi u trong công vi c tìm ki m thông tin cũng ệ ắ ế ế ộ ố . nh trong cu c s ng ư

M t s thu t toán s p x p t ộ ố ế ươ ậ ắ ng đ i đ n gi n nh : ư ố ơ ả

1. S p x p n i b t ắ ế ổ ọ

S p x p n i b t (bubble sort) là ph ươ ơ

ế ng đ ả

đ u, n u ph n t ế ầ ử ứ ầ ử ầ ướ ớ

ế ụ ư ậ ỗ

i v i hai ổ ế ạ ớ ố ậ

ễ ng pháp s p x p đ n gi n, d ế ả ắ đ u i thu t b t đ u t ậ ắ ầ ừ ầ c l n h n ơ đ ng tr ớ ặ đ ng sau thì đ i ch chúng cho nhau. Ti p t c làm nh v y v i c p ti p theo cho đ n cu i t p h p d li u. Sau đó nó quay l đ u cho đ n khi không còn c n ph i đ i ch n a. ổ ọ ắ hi u th c d y trong khoa h c máy tính. Gi ể ọ ượ ạ ườ c a t p d li u. Nó so sánh hai ph n t ủ ậ ữ ệ ph n t ầ ử ứ ph n t ầ ử ế ph n t ầ ử ầ ợ ữ ệ ầ ả ổ ỗ ữ ế

2. S p x p chèn ắ ế

S p x p chèn (insertion sort) là m t thu t toán s p x p r t hi u qu ộ ế ấ ệ ế ắ ả

c a danh sách chèn vào v ị

ắ ậ t l y các ph n t ầ ử ủ c s p. v i các danh sách nh . Nó l n l ỏ ớ trí thích h p trong m t danh sách m i đã đ ộ ầ ượ ấ ớ ợ ượ ắ

3. S p x p ch n ắ ế ọ

S p x p ch n (select sort) là ph ế ế

ng t ọ ấ ế ị ọ ng pháp s p x p b ng cách ch n ằ ắ nh th hai, v i các ph n t ầ ử ỏ ứ ự ớ

ắ ươ ph n t bé nh t x p vào v trí th nh t, t ứ ấ ươ ầ ử th ba,... ứ

4. S p x p tr n ắ ế ộ

ắ ậ

ộ t ư ưở ủ ụ ơ ả

ế ng "chia đ tr " (divide and conquer). Th t c c b n là c s p x p vào m t danh sách m i theo th t ế x p d a vào t ế ự vi c tr n hai danh sách đã đ ộ ệ ắ S p x p tr n (merge sort) cùng v i s p x p nhanh là hai thu t toán s p ớ ắ ứ ự . ể ị ượ ắ ế ộ ớ

ẳ ạ

ộ ể ắ ầ th nh t v i ph n t ầ ử ứ ầ m t (ch ng h n ph n ế ...) và sau khi k t

c 1 nó chuy n sang b c 2. ầ ử ộ ứ ư ớ ộ ể

thành các danh sách b n ph n t ầ c 2 nó tr n các danh sách hai ph n ố . C nh v y cho đ n khi hai danh sách ế

Nó có th b t đ u tr n b ng cách so sánh hai ph n t ằ th hai, sau đó th ba v i th t t ử ứ ấ ớ thúc b b ướ t ử cu i cùng đ c tr n thành m t. ứ ướ Ở ướ ầ ử ứ ư ậ ộ ượ ố ộ

5. S p x p vun đ ng ắ ế ố

S p x p vun đ ng (heapsort) là m t trong các ph ộ ố

ắ ế m i b ọ ấ ế ắ ặ

ố ặ ọ Ở ỗ ướ ủ ắ ấ ầ

ế ế ụ ớ ờ ạ

ả c g i là đ ng (heap). Đ ng là cây nh phân mà tr ng s t đ ử ụ ị ệ ượ ọ

ộ ấ ọ ộ ọ ỉ

ủ ơ c vun thành đ ng, g c c a nó là ph n t ượ ậ ố

ầ ử ớ ắ ấ ế ỏ ố ể ặ ố

ng pháp s p x p ế ươ c c a s p x p ch n ta ch n ph n t l n nh t (ho c nh ch n. ỏ ầ ử ớ ọ ạ ủ nh t) đ t vào cu i (ho c đ u) danh sách, sau đó ti p t c v i ph n còn l i c a ặ ầ danh sách. Thông th ư ng s p x p ch n ch y trong th i gian O(n2). Nh ng ọ ườ ắ ữ ệ heapsort đã gi m đ ph c t p này b ng cách s d ng m t c u trúc d li u ằ ộ ứ ạ đ c bi ố ở ỗ m i ố ặ ố đ nh cha l n h n ho c b ng tr ng s các đ nh con c a nó. M t khi danh sách ố ặ ằ ớ ỉ l n nh t, thu t toán d li u đã đ ữ ệ ố ủ ố i phóng nó kh i đ ng đ đ t vào cu i danh sách. S p x p vun đ ng s gi ẽ ả ch y trong th i gian O(nlogn). ờ ạ

6. S p x p nhanh ắ ế

S p x p nhanh (quicksort) là m t thu t toán theo t ậ ắ ế

nh h n ch t v tr t c các ph n t t ư ưở ộ ọ ầ ử ỏ ơ

ủ ụ ố t c các ph n t ầ ử ớ ố ề ủ ụ

ể ị ng chia đ tr , ầ ử ộ ố ề ướ c ể ư ể ấ ả ờ ệ ế

ộ nó d a trên th t c phân chia nh sau: đ chia m t dãy ta ch n m t ph n t ư ể ự c g i là "ch t" (pivot), chuy n t đ ể ấ ả ượ ọ ch t, chuy n t l n h n ch t v sau nó. Th t c này có th ố th c hi n trong th i gian tuy n tính. Ti p t c phân chia các dãy con đó nh ự trên cho đ n khi các dãy con ch còn m t ph n t ơ ế ụ ộ . ầ ử ế ỉ

Đi m khác bi ể ế ộ

ệ ữ ắ đ ứ ự ượ ế t gi a s p x p nhanh và s p x p tr n là trong s p x p ắ ộ ắ ổ ị

ệ i sau khi các bài toán con đã đ c gi ị ượ ế ả

ế ợ c xác đ nh khi "tr n", t c là trong khâu t ng h p ứ i, còn s p x p nhanh đã quan tâm ắ khi phân chia m t danh sách thành hai danh sách con. các ph n t tr n vi c xác đ nh th t ộ l i gi ờ đ n th t ế ả ứ ự ầ ử ộ

Ngoài ra còn nhi u gi ế

ề c c i ti n t ả các gi ả

ng coi các gi ổ ọ ậ ả ọ

ậ ắ i thu t trên. Trong sau gi ậ i thu t chèn, ch n, n i b t là các gi ả ng h p trung bình c a chúng là O(n2). Ba gi ườ ả

i thu t i thu t s p x p khác, trong đó nhi u gi ậ ề ả t kê trên, i thu t li ậ ệ ả ộ i thu t c b n, đ ậ ơ ả i thu t còn ậ i thu t cao c p, đ ph c t p tính toán trung bình ế ượ ả ế ừ ườ ứ ạ i th ườ ợ c coi là gi ả ượ ộ ứ ạ ủ ấ ậ

s p x p đ ắ ta th ph c t p trong tr ng đ l ạ c a chúng là n.ln(n). ủ

Ắ Ậ

Ế IV. NG D NG L P TRÌNH SONG SONG VÀO BÀI TOÁN S P X P Ứ B NG PH NG PHÁP TR N(MERGESORT) Ụ ƯƠ Ộ Ằ

1. Phát bi u bài toán ể

Gi s có hai danh sách đã đ ả ử ượ ắ ế

c s p x p a[1..m] và b[1..n.] (trong đó m ớ i thành m t danh sách m i ạ ộ

và n là các s r t l n) Ta có th tr n chúng l c[1..m + n] đ ể ộ c s p x p theo cách sau: ố ấ ớ ượ ắ ế

So sánh hai ph n t đ ng đ u c a hai danh sách, l y ph n t ấ ầ ử

ỏ ơ nh h n i khi m t trong hai danh sách ầ ử ứ ớ ầ ủ ư ậ ộ ớ ế ụ

cho vào danh sách m i. Ti p t c nh v y cho t là r ng.ỗ

Khi m t trong hai danh sách là r ng ta l y ph n còn l i c a danh sách ầ ấ ộ ỗ ạ ủ

kia cho vào cu i danh sách m i. ố ớ

ễ ậ ư

Ví d :ụ Cho hai danh sách a = (1,3,7,9),b = (2,6), quá trình hòa nh p di n ra nh sau:

Danh sách a Danh sách b So sánh Danh sách c

1,3,7,9 2,6 1<2 1

3,7,9 2,6 2<3 1,2

3,7,9 6 3<6 1,2,3

7,9 6 6<7 1,2,3,6

7,9 1,2,3,6,7,9

Nh v y, vi c áp d ng tính toán song song ệ ế

ư ậ ả ụ ả ở ắ ế

bài toán s p x p chính là ta chia m ng c thành 2 m ng a và b. Ta ti n hành s p x p 2 m ng a, b sau đó tr n m ng a và m ng b vào v i nhau, ta có m ng c là k t qu c a bài toán. ắ ả ả ủ ế ế ả ả ả ộ ớ

Bài toán đ c ti n hành theo các b c sau: ượ ế ướ

Ti n trình chính có nhi n v kh i t o (đ c) d li u, chia các thành c 1: ữ ệ ọ ướ

B các block d li u liên t c cho các task làm vi c. ụ ệ ụ ở ạ ệ ế ữ ệ

c2 : ệ ế ắ ộ

ậ ả ề ả ế ể ể

B Các task làm vi c nh n d li u s a d ng thu t toán s p x p tr n đ ậ ữ ệ ử ụ ti n hành s p x p trên phân đo n c a mình, tr k t qu v cho MASTER đ ắ ạ ủ ế ti n hành tr n l n cu i. ộ ầ ướ ế ế ố

2. Mã ngu nồ

ng ươ ủ

trình trên, mã ngu nồ D i đây là mã ngu n C dùng MPI c a ch ồ ượ trình bày trong cu n "Parallel Programming in C with MPI and ố

ướ này đ c OpenMP" c a tác gi Quinn. ủ ả

#include #include #include #include #define N 10000000 #define MASTER 0

int * merge(int *A, int asize, int *B, int bsize); void m_sort(int *A, int min, int max); double startT, stopT; double startTime;

int * merge(int *A, int asize, int *B, int bsize) { int ai, bi, ci, i; int * C; int csize = asize+bsize; ai = 0; bi = 0; ci = 0; C = (int *)malloc(csize*sizeof(int)); while((ai= asize) for(i=ci;i= bsize) for(i=ci;i < csize; i++, ai++) C[i] = A[ai]; for(i=0; i < asize;i++) A[i] = C[i]; for(i=0; i < bsize; i++) B[i] = C[asize + i]; return C; } void m_sort(int *A, int min, int max) { int * C; int mid = (min + max )/2;

int left = mid - min + 1; int right = max - mid; if(max != min) { m_sort(A, min, mid); m_sort(A, mid+1, max); C = merge(A + min, left, A + mid + 1, right); } }

int main(int argc, char* argv[]) { int * data; int * blk; int * temp; int m, n = N; int id, p; int s = 0; int i; int step; MPI_Status status; MPI_Init(&argc,&argv); MPI_Comm_rank(MPI_COMM_WORLD,&id); MPI_Comm_size(MPI_COMM_WORLD,&p); startT = MPI_Wtime(); if(id == MASTER) { int r; srandom(MPI_Wtime()); s = n/p; r = n%p; data = (int *)malloc((n+s-r)*sizeof(int)); for(i=0;i

m_sort(blk, 0, s-1); } step = 1; while(step < p) { if(id%(2*step)==0) { if(id + step < p) { MPI_Recv(&m,1,MPI_INT,id+step,0,MPI_COMM_WORLD, &status); temp = (int *)malloc(m*sizeof(int)); MPI_Recv(temp,m,MPI_INT,id+step,0,MPI_COMM_WORL D,&status); blk = merge(blk,s,temp,m); s += m; } } else { int near = id-step; MPI_Send(&s,1,MPI_INT,near,0,MPI_COMM_WORLD); MPI_Send(blk,s,MPI_INT,near,0,MPI_COMM_WORLD); break; } step *= 2; } stopT = MPI_Wtime(); printf(" %d; %d processors; %f secs\n", s, p, (stopT- startT)); MPI_Finalize(); return 0; }

3. Đánh giá th i gian ch y v i s CPU khác nhau ạ ớ ố ờ

ế ộ ố

ắ ệ ự ả ả K t qu m t s test th c hi n trên bkluster@hut.edu.vn ệ ế

ự ế ả ắ

ự S p x p 1 m ng có 400.000 th c hi n trên 4 processors [guest@bkluster ~]$ mpirun -np 4 MergeSort 100000; 4 processors; 0.081254 secs 100000; 4 processors; 0.083078 secs 200000; 4 processors; 0.096949 secs 400000; 4 processors; 0.105866 secs S p x p 1 m ng có 400.000 th c hi n trên 40 processors ệ [guest@bkluster ~]$ mpirun -np 40 MergeSort 10000; 40 processors; 0.013951 secs 10000; 40 processors; 0.019274 secs 10000; 40 processors; 0.022400 secs 10000; 40 processors; 0.022348 secs 20000; 40 processors; 0.026182 secs 20000; 40 processors; 0.026826 secs

20000; 40 processors; 0.031455 secs 10000; 40 processors; 0.019963 secs 10000; 40 processors; 0.019862 secs 10000; 40 processors; 0.020511 secs 10000; 40 processors; 0.024505 secs 10000; 40 processors; 0.022193 secs 20000; 40 processors; 0.032605 secs 10000; 40 processors; 0.024016 secs 20000; 40 processors; 0.034100 secs 10000; 40 processors; 0.029445 secs 20000; 40 processors; 0.034308 secs 10000; 40 processors; 0.030610 secs 10000; 40 processors; 0.030799 secs 10000; 40 processors; 0.031756 secs 10000; 40 processors; 0.033447 secs 10000; 40 processors; 0.027346 secs 10000; 40 processors; 0.028244 secs 20000; 40 processors; 0.035594 secs 20000; 40 processors; 0.035773 secs 10000; 40 processors; 0.030917 secs 10000; 40 processors; 0.037861 secs 20000; 40 processors; 0.039877 secs 10000; 40 processors; 0.033726 secs 40000; 40 processors; 0.042259 secs 20000; 40 processors; 0.044526 secs 40000; 40 processors; 0.044677 secs 40000; 40 processors; 0.044937 secs 40000; 40 processors; 0.040305 secs 80000; 40 processors; 0.051000 secs 40000; 40 processors; 0.054588 secs 80000; 40 processors; 0.056556 secs 160000; 40 processors; 0.060220 secs 80000; 40 processors; 0.066859 secs 400000; 40 processors; 0.074034 secs S p x p 1 m ng có 1.000.000 th c hi n trên 20 processors ệ

[guest@bkluster ~]$ mpirun -np 20 MergeSort 50000; 20 processors; 0.057896 secs 50000; 20 processors; 0.063329 secs 50000; 20 processors; 0.062425 secs 50000; 20 processors; 0.075495 secs 100000; 20 processors; 0.084388 secs 50000; 20 processors; 0.096323 secs 50000; 20 processors; 0.099152 secs 100000; 20 processors; 0.106208 secs 50000; 20 processors; 0.106753 secs 50000; 20 processors; 0.112207 secs 50000; 20 processors; 0.114848 secs 100000; 20 processors; 0.117695 secs 50000; 20 processors; 0.119958 secs 200000; 20 processors; 0.101777 secs 100000; 20 processors; 0.126893 secs 100000; 20 processors; 0.324322 secs

ự ế ả ắ

ắ ả ế ự

i u c a gi ự ế

200000; 20 processors; 0.329881 secs 400000; 20 processors; 0.341076 secs 200000; 20 processors; 0.358863 secs 1000000; 20 processors; 0.378503 secs S p x p 1 m ng có 10.000.000 th c hi n trên 20 processors ệ [guest@bkluster ~]$ mpirun -np 20 MergeSort 500000; 20 processors; 0.651765 secs 500000; 20 processors; 0.652185 secs 500000; 20 processors; 0.659507 secs 500000; 20 processors; 0.767964 secs 1000000; 20 processors; 0.793689 secs 500000; 20 processors; 0.899705 secs 500000; 20 processors; 0.937705 secs 1000000; 20 processors; 1.002965 secs 500000; 20 processors; 1.039666 secs 500000; 20 processors; 1.092781 secs 1000000; 20 processors; 1.110230 secs 1000000; 20 processors; 1.206062 secs 2000000; 20 processors; 1.170763 secs 1000000; 20 processors; 1.635967 secs 2000000; 20 processors; 1.686629 secs 4000000; 20 processors; 1.735968 secs 2000000; 20 processors; 1.968635 secs 500000; 20 processors; 1.050071 secs 500000; 20 processors; 1.143645 secs 10000000; 20 processors; 2.155330 secs i thu t song song D a vào k t qu trên, ta có th th y s t ậ ể ấ ự ố ư ủ ả ế ợ i quy t các bài toán l n. V i s tham gia c a nhi u b vi x lí, k t h p ử ề i hi u qu tính toán cao i thu t tính toán xong xong t

ớ ự ả ộ ủ ớ

i u x mang l ẽ ế ậ ố ư ệ ạ ả

đ gi ể ả v i gi ả ớ nh t.ấ

K T LU N Ậ Ế

B môn gi ộ ả

ộ ự ệ ề ẽ ể ằ ầ

i thu t và tính toán song song trong CNTT là m t chuyên ả i quy t m t cách thành công ế ả ộ

ậ ngành đang phát tri n m nh m trong nhi u năm g n đây. B ng s hi u qu ạ c a tính toán song song đã giúp cho chúng ta gi ủ các bài toán khó (v i s l ng tính toán r t l n) trong nhi u ngành khoa h c. ớ ố ượ ấ ớ ề ọ

Trong nh ng năm g n đây, b ng vi c các nhà s n xu t b vi x lí c ằ ầ ệ ấ ộ ử ả

ộ ệ ự ộ

ự ế ố ộ ị

ố ữ g ng tăng t c đ tính toán cho b vi x lí c a mình. Trong vòng 30 năm qua, ủ ử ộ ố ắ t k CPU đã th c hi n gia tăng t c đ trong 3 lĩnh v c chính, hai các nhà thi ố ế ế trong s đó t p trung vào ti n trình th c thi l nh: T c đ xung nh p, T i u ố ư ệ ự ậ vi c th c thi, B nh đ m (cache). ộ ớ ệ ố ự ệ

ị ơ ộ ề

ớ ầ ệ ơ

ả

ậ ệ ượ ơ ệ ề ự

ế ạ ế ư ệ ứ ạ ệ ệ ơ ệ ẽ

ậ ắ ể

ỹ

ế ạ . Các k thu t này đ u đ ậ ề t h n và nhanh h n, t n d ng t ậ ụ ơ ế ế ừ ự ố ơ ế

ượ ố ố ộ ẽ ừ ạ ị ị

i và có th ệ ố ệ ộ ồ ẽ ạ ế ố

ể ế ụ ậ ạ ậ ộ ậ ậ ụ ạ

ươ ấ

ữ ự ậ

Vi c gia tăng t c đ xung nh p cho nhi u chu kỳ xung h n. Ch y CPU ạ ố ệ nhanh h n g n nh đ ng nghĩa v i vi c th c hi n công vi c nhanh h n. Vi c ơ ư ồ ự ệ t c nhi u vi c h n trong m i chu kỳ. i u kh năng th c thi cho phép làm đ ỗ ự ố ư c Các CPU hi n nay có t p l nh m nh h n và th c hi n đ lo i t ủ ạ ố ư ừ ơ i u t ề b n đ n ph c t p nh t o tuy n u tiên, tiên đoán r nhánh, th c thi nhi u ự ả ư ạ i chu i l nh đ cho phép l nh trong cùng xung nh p; th m chí còn s p x p l ệ ị ỗ ệ c thi th c thi không theo trình t t k nh m làm ằ ự i đa t ng chu kỳ xung cho ti n trình th c thi t ự ậ nh p. Và câu h i đ t ra khi nào thì vi c gia tăng t c đ s d ng l i? Đ nh lu t ỏ ặ Moore tiên đoán s gia tăng theo s mũ rõ ràng không th ti p t c mãi khi ự ể chúng ta đ t đ n gi i h n v t lý. Vi c tăng t c đ r i s ch m l ớ ạ i. (Chú thích: đ nh lu t Moore ch y u áp d ng cho m t đ transistor, d ng l ủ ế ị ừ ự cũng x y ra trong các lĩnh v c ng t tuy nhiên vi c tăng theo c p s mũ t ả ự ố ệ liên quan nh t c đ xung nh p. ị Th m chí trong nh ng lĩnh v c khác còn gia tăng nhanh ư ố ộ h n, ch ng h n nh l u tr d li u). ơ ư ư ữ ữ ệ ạ ẳ

ệ

ố i th : T n d ng đ ề ợ ệ ụ ậ

ụ ế ừ

ượ ố ộ ắ ể ự ố ộ ự ế ằ ự

ệ ề ứ ế ấ ồ

Khi vi c tăng t c đ cho CPU càng ngày càng khó khăn, thì vi c x lí ử ộ ờ c t c đ c a CPU, t n d ng th i ế ậ ộ ủ i quy t cùng m t lúc các bài toán). T đó làm ra ả (b ng cách rút ng n th i gian th c hi n bài toán). ờ ộ i th : Th nh t, b n ch t các lu ng đi u khi n đ c ả ệ t nhau v m t lí lu n. Th hai, song hành đem đ n s c i thi n song song có nhi u l gian đ th c hi n bài toán (gi ệ tăng t c đ tính toán th c t X lí song song có các l ử l p tách bi ậ ể ế ự ả ợ ề ặ ấ ứ ệ ậ

ấ ệ ờ ậ ủ ụ ề ế ặ ặ ờ

ế hi u su t, ho c nh t n d ng nhi u CPU ho c th i gian “ch t” c a các ti n trình trong ng d ng. ứ ụ

Bên c nh nh ng thu n l i trên, thì x lí song song còn có nh ng nh ử ữ ậ ợ

c h t, không ph i t ể ệ ề ụ

ở ấ ề

quen thu c tr ứ

ể ế ừ

ể ự ơ ậ ử ụ ế cho l p trình viên tu n t ự ặ

ầ ự ế ả

ứ ươ ự ế ồ ữ ệ ặ

ể

ng đ i t ậ ẽ ể ự ậ ỹ ậ ướ ỹ ể

c. ượ c ữ ạ t c ng d ng đ u có th th c hi n song đi m sau: Tr ả ấ ả ứ ế ướ song. Và tr ng i l n nh t là vi c l p trình song song khó h n nhi u so v i ớ ệ ậ ạ ớ ấ l p trình theo trình t c đây. Thách th c mà l p trình viên c u ướ ộ ự ậ ng là gì? làm th nào s d ng k th a?...) trúc khi chuy n sang OO (đ i t ố ượ ể t ng g p cũng là thách th c t khi chuy n ng t ừ i quy t sang song hành (lu ng th c thi là gì? t c ngh n là gì? làm th nào gi ế ắ ố ậ ho c tránh nó? nh ng ti n trình nào có th th c hi n song song...). Đa s l p trình viên hi n nay không am hi u k thu t song song, cũng nh cách đây 15 ư năm đa s l p trình viên không am hi u k thu t h ng (OO). Tuy ố ượ nhiên, m i th đ u có th h c đ ứ ề ệ ố ậ ọ ể ọ ượ

TÀI LI U THAM KH O Ả Ệ

1. Ananth Gramma, Anshul Gupta, George Karypis, Vipin Kumar:

Introduction to Parallel Computing 2 n d, Add Wesley, USA, 2003

2. Parallel Programming in C with MPI and OpenMP" c a tác gi Quinn. ủ ả

3. http://www.lam-mpi.org/

4. http://www.mpi.org/

5.http://www.cs.uncc.edu/~abw/parallel/par_prog/resources.htm

6. Slide bài gi ng môn “Các k thu t hi n đ i trong công ngh ỹ ệ ả ậ ạ ệ

thông tin và tính toán song song ” c a ủ T.S Nguy n H u Đ c ứ ữ ễ