N i dung:ộ
Tìm hi u tính toán song song hóa thu t toán vàể ậ
ng d ng song song bài toán s p x p theo giứ ụ ắ ế ỏ
(bucket sort)
M C L CỤ Ụ
TÀI LI U THAM KH OỆ Ả ........................................................................................ 15
2
Ph n I: M Đ Uầ Ở Ầ
B n th p k qua ch ng ki n s phát tri n bùng n v s c m nh máyố ậ ỷ ứ ế ự ể ổ ề ứ ạ
tính, t o ti n đ cho nh ng b c ti n ch a t ng th y v phát minh, năng su tạ ề ề ữ ướ ế ư ừ ấ ề ấ
lao đ ng và phúc l i cho con ng i. Nh ng quá trình đó gi đây đ ng tr cộ ợ ườ ư ờ ứ ướ
m t tr ng i mà ít ai nghĩ đ n: s k t thúc c a quá trình m r ng s c m nhộ ở ạ ế ự ế ủ ở ộ ứ ạ
đi n toán. Ngành tin h c đã đ t đ n gi i h n c a nh ng gì t ng kh thi v iệ ọ ạ ế ớ ạ ủ ữ ừ ả ớ
m t hay hai vi x lý trung tâm ho t đ ng theo chu i truy n th ng (serialộ ử ạ ộ ỗ ề ố
processing). Ngành nào v n d a vào mô hình đó đ ti p t c phát tri n năngẫ ự ể ế ụ ể
su t, tăng tr ng kinh t và phát tri n xã h i thì c n ph i b t đ u m t b cấ ưở ế ể ộ ầ ả ắ ầ ộ ướ
nh y m i vào đi n toán x lý song song (parallel processing).ả ớ ệ ử
Ngày nay, v i các bài toán yêu c u x lý trên m t s l ng d li u l nớ ầ ử ộ ố ượ ữ ệ ớ
và ph c t p nh s mô ph ng nh ng h th ng ph c t p và "nh ng v n đứ ạ ư ự ỏ ữ ệ ố ứ ạ ữ ấ ề
thách th c l n" nh : d báo th i ti t và khí h u, nh ng ph n ng hoá h c vàứ ớ ư ự ờ ế ậ ữ ả ứ ọ
h t nhân, h gen sinh h c, ... đ t ra m t nhu c u l n v t c đ tính toán.ạ ệ ọ ặ ộ ầ ớ ề ố ộ
Nh ng bài toán này th ng yêu c u m t l ng l n các phép tính l p l i trênữ ườ ầ ộ ượ ớ ặ ạ
m t kh i l ng l n d li u đ đ a ra m t k t qu đúng đ n, và các phép tínhộ ố ượ ớ ữ ệ ể ư ộ ế ả ắ
này c n hoàn thành trong kho ng th i gian h p lý. Ví d nh bài toán d bàoầ ả ờ ợ ụ ư ự
th i ti t không th x lý b ng các máy tính thông th ng vì th i gian x lý làờ ế ể ử ằ ườ ờ ử
kho ng 10 năm, đi u này hoàn toàn không phù h p.ả ề ợ
Đ gi i quy t đ c các bài toán trên ta c n ph i tăng t c đ tính toán.ề ả ế ượ ầ ả ố ộ
M c dù trong nh ng th p k v a qua chúng ta đã đ c ch ng ki n nh ngặ ữ ậ ỷ ừ ượ ứ ế ữ
thành t u to l n v công ngh vi x lý. T c đ đ ng h c a các b x lý đãự ớ ề ệ ử ố ộ ồ ồ ủ ộ ử
tăng t kho ng 40MHz (MIPS R3000, circa 1988) t i trên 2,0 GHz (Pentium 4,ừ ả ớ
circa 2002); cùng m t lúc các b x lý có kh năng th c hi n đa ch l nhộ ộ ử ả ự ệ ỉ ệ
trong cùng m t chu kỳ ... nh ng do gi i h n v v t lý nên kh năng tính toánộ ư ớ ạ ề ậ ả
c a các b x lý không th tăng mãi đ c.ủ ộ ử ể ượ
Minh h a m t cách đ n gi n, tính toán truy n th ng gi ng nh vi cọ ộ ơ ả ề ố ố ư ệ
m t ng i đ c bài văn theo ki u tu n t t đ u đ n cu i, còn tính toán songộ ườ ọ ể ầ ự ừ ầ ế ố
song thì gi ng nh tách bài văn đó thành các ph n và cho nhi u ng i khácố ư ầ ề ườ
nhau cùng đ c m t lúc đ có k t qu nhanh h n. Tính toán song song mangọ ộ ể ế ả ơ
l i m t n n t ng m i cho s phát tri n c a công ngh x lý. Đây là m tạ ộ ề ả ớ ự ể ủ ệ ử ộ
h ng đi m i, đúng đ n và hi u qu cho công ngh đi n toán trong t ng lai.ướ ớ ắ ệ ả ệ ệ ươ
Bài vi t sau đây v đ tài “Tìm hi u v tính toán song song , áp d ng gi iế ề ề ể ề ụ ả
quy t m t s bài toán” ph n nào th hi n đ c nh ng ki n th c c b n đ uế ộ ố ầ ể ệ ượ ữ ế ứ ơ ả ầ
tiên v tính toán song song, tính đúng đ n và ng d ng c a nó.ề ắ ứ ụ ủ
Ph n II: N I DUNGầ Ộ
I. Nh ng khái ni m c b n v tính toán song songữ ệ ơ ả ề
1. Nhu c u tính toán hi u năng cao và tính kh d ng c a tính toán song song.ầ ệ ả ụ ủ
a. Nhu c u tính toán song songầ
Ví d 1:ụ Oregon State University: Mô ph ng các dòng ch y l u thông c a đ iỏ ả ư ủ ạ
d ng --> xác đ nh nguyên nhân gây trái đ t đang nóng d n lên.ươ ị ấ ầ
- Phân chia đ i d ng thành:ạ ươ
• 4096 vùng t đông sang tây.ừ
• 1024 vùng t b c sang nam.ừ ắ
• 12 t ng bi n.ầ ể
• X p s 50 tri u kh i trong không gian 3 chi u.ấ ỉ ệ ố ề
- Mô ph ng l u thông th c hi n ~ 30 t phép tính trong 10 phút. Côngỏ ư ự ệ ỷ
vi c này th c hi n liên t c trong năm.ệ ự ệ ụ
Ví d 2:ụ D báo th i ti t (weather forecasting): ự ờ ế
- Chia b u khí quy n theo không gian 3 chi u, m i kh i kích th cầ ể ề ỗ ố ướ
1mile x 1mile x 1mile.
- c tính kho ng 5x10^8 kh i (cells).Ướ ả ố
- Trên m i kh i c n th c hi n ~ 200 phép toán -> c n th c hi n ~ỗ ố ầ ự ệ ầ ự ệ
10^11 phép toán.
- N u c n d báo cho 1 tu n, chu kỳ 1 phút -> c n th c hi n 10^4 l n,ế ầ ự ầ ầ ự ệ ầ
m i l n 10^11phép toán.ỗ ầ
- Siêu máy tính có th th c hi n: 10^9 phép toán trên 1 giây -> c n 10^6ể ự ệ ầ
giây ~ 10 ngày đ th c hi n.ể ự ệ
Ví d 3:ụ Mô ph ng t ng tác c a các protein v i phân t n c (Levin 1990):ỏ ươ ủ ớ ử ướ
- Th c hi n trên máy Cray X/MP (~800 tri u phép toán / 1 giây): đ môự ệ ệ ể
ph ng 10^-12 giây ph n ng protein c n 1 gi th c hi n.ỏ ả ứ ầ ờ ự ệ
- N u mô ph ng m t ph n ng th c s trên cùng máy Cray X/MP c nế ỏ ộ ả ứ ự ự ầ
31,688 năm.
TÓM L I: Ạ
Yêu c u v th c nghi m nghiên c u, mô ph ng -> gi i quy t nh ngầ ề ự ệ ứ ỏ ả ế ữ
bài toán có kh i l ng tính toán l n trong m t kho ng th i gian ch p nh nố ượ ớ ộ ả ờ ấ ậ
đ c.ượ
Ph ng h ng gi i quy t v n đ :ươ ướ ả ế ấ ề
- Th c hi n trên các siêu máy tính m nh.ự ệ ạ
- Th c hi n phân chia công vi c th c hi n song song trên h th ng các máyự ệ ệ ự ệ ệ ố
tính
Tính kh d ng c a tính toán song songả ụ ủ
SIÊU MÁY TÍNH: Kh năng tính toán ph thu c nhi u vào t c đ xả ụ ộ ề ố ộ ử
lý c a CPU -> ph thu c vào c u trúc và s l ng transistors ch a trong CPUủ ụ ộ ấ ố ượ ứ
–> Có nh ng gi i h n nh t đ nh v kích th c, nhi t đ -> không th tăng sữ ớ ạ ấ ị ề ướ ệ ộ ể ố
transistors lên mãi đ cượ
TH C HI N SONG SONG: Ự Ệ
Nguyên t c: th c hi n phân chia công vi c chính thành các công vi c con, cóắ ự ệ ệ ệ
th th c hi n song song v i nhau.ể ự ệ ớ
Xây d ng h th ng song song t nhi u b x lý riêng bi t. Th c hi n cácự ệ ố ừ ề ộ ử ệ ự ệ
công vi c song song trên các b x lý đó.ệ ộ ử
V n đ :ấ ề
- Ph ng pháp phân chia công vi c.ươ ệ
- Môi tr ng h tr th c hi n song song.ườ ỗ ợ ự ệ
Ví d :ụ X p sách trong th vi nế ư ệ
Sách trong th vi n đ c phân lo i theo ch cái đ u tiên và s p x pư ệ ượ ạ ữ ầ ắ ế
theo th t .ứ ự
Sách cùng nhóm đ c x p trên cùng m t giá. Các giá đ t trong các tượ ế ộ ặ ủ
sách.
Th vi n nh p m t s l ng sách l n -> yêu c u th th ph i s p x pư ệ ậ ộ ố ượ ớ ầ ủ ư ả ắ ế
sách theo đúng nguyên t c.ắ
Cách gi i quy t hi u qu nh t?ả ế ệ ả ấ
+ N u ch có 1 th thế ỉ ủ ư
- Cách th nh t: L y t ng cu n sách r i s p x p vào v trí thích h p ->ứ ấ ấ ừ ố ồ ắ ế ị ợ
không hi u qu .ệ ả
- Cách th hai: S p x p các cu n sách theo th t tr c r i mang t ngứ ắ ế ố ứ ự ướ ồ ừ
ch ng sách cùng v trí đi s p x p.ồ ị ắ ế
Rõ ràng cách th 2 hi u qu h n.ứ ệ ả ơ
Mu n hi u qu h n n a thì c n có nhi u ng i làm h n.ố ệ ả ơ ữ ầ ề ườ ơ
+ Nhi u th th h nề ủ ư ơ
Cách th nh t: M i ng i l y 1 cu n r i đi s p đ t v trí -> không hi uứ ấ ỗ ườ ấ ố ồ ắ ặ ị ệ
qu .ả
Cách th hai: Phân chia m i ng i m t nhóm ký t , khi đó m i ng iứ ỗ ườ ộ ự ỗ ườ
ch mang sách thu c nhóm mình đi s p x p.ỉ ộ ắ ế
Cách th ba: S p x p sách tr c khi mang đi đ t v trí. M i ng i đ mứ ắ ế ướ ặ ị ỗ ườ ả
nh n m t s ký t :ậ ộ ố ự
N u cu n sách đang c m c a mình thì đ t vào ch ng sách c a mình.ế ố ầ ủ ặ ồ ủ
N u c a ng i khác thì chuy n cho ng i đ y.ế ủ ườ ể ườ ấ
Sau đó mang sách đi s p x p.ắ ế
-> cách th ba hi u qu nh t.ứ ệ ả ấ
Ý nghĩa c a tính toán song songủ
Th c hi n công vi c trong kho ng th i gian ng n h n -> ti t ki m th iự ệ ệ ả ờ ắ ơ ế ệ ờ
gian.
Th c hi n đ c v i s l ng phép toán l n h n -> gi i quy t đ c bàiự ệ ượ ớ ố ượ ớ ơ ả ế ượ
toán l n.ớ
H tr gi i quy t nhi u công vi c đ ng th i.ỗ ợ ả ế ề ệ ồ ờ
2. Các ng d ng trong h th ng máy tínhứ ụ ệ ố
Khi các h th ng máy tính tr nên r ng kh p và s tính toán tr i r ngệ ố ở ộ ắ ự ả ộ
trên toàn m ng, thì các v n đ x lý song song cũng đ c ng d ng nhi uạ ấ ề ử ượ ứ ụ ề
h n. trong vi c b o m t máy tính, vi c phát hi n xâm ph m là m t th tháchơ ệ ả ậ ệ ệ ạ ộ ử
đáng k . Trong tr ng h p phát hi xâm ph m m ng, d li u đ c thu th pể ườ ợ ệ ạ ạ ữ ệ ượ ậ
t các trang phân tán và ph i đ c phân tích m t cách nhanh chóng. Vi cừ ả ượ ộ ệ
5