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Ứ Ụ Ậ Ả Ế
S P X P B NG PH NG PHÁP TR N (MERGE SORT)Ắ Ế Ằ ƯƠ Ộ
Phú Th , tháng 05-2011ọ
LỜI M Đ UỞ Ầ
Trong nh ng năm g n đây, m c dù n n Công ngh thông tinữ ầ ặ ề ệ
c a th gi i ngày m t phát tri n. T c đ x lí máy tính ngày càngủ ế ớ ộ ể ố ộ ử
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 t, d báoữ ệ ầ ớ ự ờ ế ự
đ ng đ t, …). V i d li u đ u vào là m t con s r t l n, dù máyộ ấ ớ ữ ệ ầ ộ ố ấ ớ
tính có t c đ l n, b nh nhi u v n v p ph i yêu c u ph i gi iố ộ ớ ộ ớ ề ẫ ấ ả ầ ả ả
quy t bài toán trong th i gian ch p nh n đ c.ế ờ ấ ậ ượ
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ả ế ệ ả ỏ ề
toán. Vi c gi i quy t các bài toán nh đ c ti n hành đ ng th iệ ả ế ỏ ượ ế ồ ờ
v i nhi u máy tính. K t qu c a bài toán l n s đ c gi i quy tớ ề ế ả ủ ớ ẽ ượ ả ế
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.ụ ố ộ
3
N I DUNGỘ
I.MÔ T GI I THU TẢ Ả Ậ SONG SONG
1. Gi i thi uớ ệ
Hi n nay, đ gi i quy t các bài toán l n ng i ta th 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 ng pháp l p trình c đi n thì không th nào phátớ ươ ậ ổ ể ể
tri n đ c ch ng trình có th t n d ng đ c s c m nh c a các h th ngể ượ ươ ể ậ ụ ượ ứ ạ ủ ệ ố
đó. Đó 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ậ ộ ệ ấ ứ ạ ớ ậ ầ
t thông th ng, ng i phát tri n ph i th c hi n m t quá trình “song songự ườ ườ ể ả ự ệ ộ
hóa”, bi n đ i các ch ng trình tu n t thành ch ng trình song song có khế ổ ươ ầ ự ươ ả
nănG t n d ng t i đa s c m nh c a h th ng.ậ ụ ố ứ ạ ủ ệ ố
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 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 ng pháp gi iề ử ụ ộ ậ ộ ươ ả
quy t v n đ d a trên vi c s d ng nhi u b x lý . Tuy nhiên đ ch raế ấ ề ự ệ ử ụ ề ộ ử ể ỉ
đ c m t thu t toán song song không đ n gi n ch ra t ng b c c th , mà làượ ộ ậ ơ ả ỉ ừ ướ ụ ể
m t m c đ nào đó thu t toán song song ph i đ c them vào tính đ ng th iở ộ ứ ộ ậ ả ượ ồ ờ
và ng i thi t k ra thu t toán cũng ph i ch ra t p h p nh ng b c x lýườ ế ế ậ ả ỉ ậ ợ ữ ướ ử
đ ng th i , đi u này s t n d ng đ c kh năng tính toán c a các máy tínhồ ờ ề ẽ ậ ụ ượ ả ủ
song song. Trên th c t vi c thi t k ra m t thu t toán song song là kháự ế ệ ế ế ộ ậ
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ạ ầ ủ ệ ề ộ ử ạ
-Phân tán d li u nh p, xu t và trung gian cùng v i ch ng trìnhữ ệ ậ ấ ớ ươ
-Qu n lý truy c p vào d li u chung gi a các b x lýả ậ ữ ệ ữ ộ ử
-Đ ng b hóa các b x lý khi th c thi các ch ng trình song songồ ộ ộ ử ự ươ
2.2. Thi t k thu t toán song songế ế ậ
4
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 i m t bài toán đ t ra.ợ ả ộ ặ
Thi t k gi 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 là quá trình song song hóa bài toán tu n t .ế ế ả ậ ầ ự
Nguyên lý c b n trong thi t k gi i thu t song song bao g m:ơ ả ế ế ả ậ ồ
2.2.1. Nguyên lý l p l ch:ậ ị
Gi m t i thi u các b x lý s d ng trong thu t toán sao cho th i gianả ố ể ộ ử ử ụ ậ ờ
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 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ă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ứ ữ ầ ỏ ơ ươ ố ộ ậ ớ
nhau và gi i quy t chúng m t cách song song. T o ra m t mô hình cây phânả ế ộ ạ ộ
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ế ế ố ậ ộ ụ ữ ệ
s thì chúng ph i t ng tranh v i nhau, nghĩa là chúng có th c n tr l nẻ ả ươ ớ ể ả ở ẫ
nhau.
II. MÔ HÌNH L P TRÌNH TRUY N THÔNG ĐI P- CHU N MPIẬ Ề Ệ Ẩ
1. Gi i thi uớ ệ
5
