Siêu thị PDFTải ngay đi em, trời tối mất

Thư viện tri thức trực tuyến

Kho tài liệu với 50,000+ tài liệu học thuật

Trang chủ

Đăng nhập

Đăng ký

Mới

Đăng ký tài khoản mới

AI Tư vấn

Mới

Trợ lý thông minh tìm tài liệu

Liên hệ fanpage

Hỗ trợ tìm tài liệu

Lưu trang

Liên hệ fanpage

Luận văn: Nghiên cứu tính toán lưới và thử nghiệm một số thuật toán lý thuyết đồ thị pdf

PREMIUM

Số trang

138

Kích thước

23.6 MB

Định dạng

PDF

Lượt xem

1128

Luận văn: Nghiên cứu tính toán lưới và thử nghiệm một số thuật toán lý thuyết đồ thị pdf

Nội dung xem thử

Mô tả chi tiết

TR姶云NG A萎I H窺C KHOA H窺C T衛 NHIÊN

KHOA CÔNG NGH烏 THÔNG TIN

B浦 MÔN CÔNG NGH烏 PH井N M陰M

HU┺NH BÁ THANH TÙNG - 0112079

TR井N VI烏T C姶云NG - 0112339

NGHIÊN C永U TÍNH TOÁN L姶閏I VÀ

TH盈 NGHI烏M M浦T S渦 THU一T TOÁN

LÝ THUY蔭T A唄 TH卯

KHÓA LU一N C盈 NHÂN TIN H窺C

GIÁO VIÊN H姶閏NG D郁N

TS. TR井N AAN TH姶

Th.S NGUY右N THANH S愛N

NI ÊN KHÓA 2001-2005

NH一N XÉT C曳A GIÁO VIÊN H姶閏NG D郁N

..........................................................................................................................................

NH一N XÉT C曳A GIÁO VIÊN PH謂N BI烏N

..........................................................................................................................................

L云I C謂M 愛N

Chúng em xin bày t臼 lòng bi院t 挨n chân thành nh医t đ院n th亥y Tr亥n Aan

Th逢 và th亥y Nguy宇n Thanh S挨n, hai th亥y đã t壱n tâm h逢噂ng d磯n, giúp đ叡 chúng

em trong su嘘t th運i gian th詠c hi羽n lu壱n v<n này.

Chúng con xin g穎i t医t c違 lòng bi院t 挨n sâu s逸c và s詠 kính tr丑ng đ院n ông

bà, cha m姻, cùng toàn th吋 gia đình, nh英ng ng逢運i đã nuôi d衣y chúng con tr逢荏ng

thành đ院n ngày hôm nay.

Chúng em c┡ng xin chân thành cám 挨n quý Th亥y cô trong Khoa Công

ngh羽 thông tin, tr逢運ng A衣i h丑c Khoa h丑c T詠 nhiên Tp.H欝 Chí Minh đã t壱n tình

gi違ng d衣y, h逢噂ng d磯n, giúp đ叡 và t衣o đi隠u ki羽n cho chúng em th詠c hi羽n t嘘t

lu壱n v<n này.

Xin chân thành cám 挨n s詠 giúp đ叡, đ瓜ng viên và ch雨 b違o r医t nhi羽t tình

c栄a các anh ch鵜 và t医t c違 các b衣n, nh英ng ng逢運i đã giúp chúng tôi có đ栄 ngh鵜 l詠c

và ý chí đ吋 hoàn thành lu壱n v<n này.

M員c dù đã c嘘 g逸ng h院t s泳c, song ch逸c ch逸n lu壱n v<n không kh臼i nh英ng

thi院u sót. Chúng em r医t mong nh壱n đ逢嬰c s詠 thông c違m và ch雨 b違o t壱n tình c栄a

quý Th亥y Cô và các b衣n.

TP.HCM, 7/2005

Nhóm sinh viên th詠c hi羽n

Hu┻nh Bá Thanh Tùng - Tr亥n Vi羽t C逢運ng

L云I NÓI A井U

Nhân l丑ai ngày nay đang ch泳ng ki院n s詠 phát tri吋n m衣nh m胤 c栄a ngành

Công ngh羽 Thông tin, m瓜t trong nh英ng ngành m┡i nh丑n c栄a nhi隠u qu嘘c gia

trên th院 gi噂i. S詠 phát tri吋n v逢嬰t b壱c c栄a nó là k院t qu違 t医t y院u c栄a s詠 phát tri吋n

kèm theo các thi院t b鵜 ph亥n c泳ng c┡ng nh逢 ph亥n m隠m ti羽n ích.

S詠 phát tri吋n đó đã kéo theo r医t nhi隠u các ngành khác phát tri隠n theo,

trong đó có l┄nh v詠c nghiên c泳u khoa h丑c. Tuy công ngh羽 ngày càng phát tri吋n,

t嘘c đ瓜 x穎 lý c栄a các thi院t b鵜 c┡ng không ng瑛ng t<ng cao, nh逢ng nhu c亥u tính

toán c栄a con ng逢運i v磯n còn r医t l噂n. Cho đ院n hi羽n nay v磯n còn r医t nhi隠u v医n đ隠

mà các nhà khoa h丑c cùng v噂i kh違 n<ng tính toán c栄a các máy tính hi羽n nay

v磯n ch逢a gi違i quy院t đ逢嬰c hay gi違i quy院t đ逢嬰c nh逢ng v噂i th運i gian r医t l噂n.

Các v医n đ隠 đó có th吋 là :

• Mô hình hóa và gi違 l壱p

• X穎 lý thao tác trên các d英 li羽u r医t l噂n

• Các v医n đ隠 “grand challenge” (là các v医n đ隠 không th吋 gi違i quy院t

trong th運i gian h嬰p lý)

L運i gi違i cho nh英ng v医n đ隠 này đã d磯n đ院n s詠 ra đ運i c栄a các th院 h羽 siêu

máy tính. Tuy nhiên vi羽c đ亥u t逢 phát tri吋n cho các thi院t b鵜 này g亥n nh逢 là đi隠u

quá khó kh<n đ嘘i v噂i nhi隠u ng逢運i, t鰻 ch泳c, tr逢運ng h丑c…. Chính vì l胤 đó mà

ngày nay ng逢運i ta đang t壱p trung nghiên c泳u cách cách s穎 d映ng các tài nguyên

phân b嘘 m瓜t cách h嬰p lý đ吋 t壱n d映ng đ逢嬰c kh違 n<ng tính toán c栄a các máy tính

đ挨n. Nh英ng gi違i pháp này đ逢嬰c bi院t đ院n v噂i nhi隠u tên g丑i khác nhau nh逢 metacomputing, salable-computing, global- computing, internet computing và g亥n

nh医t hi羽n nay là peer to peer computing hay Grid computing.

Aây là ph逢挨ng pháp nh茨m t壱n d映ng kh違 n<ng c栄a các máy tính trên toàn

m衣ng thành m瓜t máy tính “違o” duy nh医t, nh茨m h嬰p nh医t tài nguyên tính toán 荏

nhi隠u n挨i trên th院 gi噂i đ吋 t衣o ra m瓜t kh違 n<ng tính toán kh鰻ng l欝, góp ph亥n gi違i

quy院t các v医n đ隠 khó kh<n trong khoa h丑c và công ngh羽. Ngày nay nó đang

càng đ逢嬰c s詠 h厩 tr嬰 m衣nh h挨n c栄a các thi院t b鵜 ph亥n c泳ng, b<ng thông…

Grid Computing có kh違 n<ng chia s飲, ch丑n l詠a, và thu gom m瓜t s嘘 l逢嬰ng

l噂n nh英ng tài nguyên khác nhau bao g欝m nh英ng siêu máy tính, các h羽 th嘘ng

l逢u tr英, cùng v噂i nh英ng ngu欝n d英 li羽u, các thi院t b鵜 đ員t bi羽t… Nh英ng tài nguyên

này đ逢嬰c phân b嘘荏 các vùng đ鵜a lý khác nhau và thu瓜c v隠 các t鰻 ch泳c khác

nhau.

Nh壱n th医y đ逢嬰c nhu c亥u phát tri吋n 医y, nhóm chúng em đã quy院t đ鵜nh

ch丑n th詠c hi羽n đ隠 tài “Nghiên c泳u tính toán l逢噂i và th詠c nghi羽m trên m瓜t

s嘘 thu壱t toán lý thuy院t đ欝 th鵜”

M映c tiêu c栄a đ隠 tài đ隠 ra là tìm hi吋u v隠 tính toán l逢噂i, và qua đó t壱n

d映ng các ki院n th泳c có đ逢嬰c đ吋 có th吋 cài đ員t m瓜t s嘘 thu壱t toán lý thuy院t đ欝 th鵜,

nh茨m có th吋 gi違i quy院t các v医n đ隠 tìm đ逢運ng đi khi s嘘 đ雨nh t逢挨ng đ嘘i l噂n…

Các n瓜i dung chính:

• Nghiên c泳u tính toán l逢噂i

• Tìm hi吋u các môi tr逢運ng h厩 tr嬰

• Tìm hi吋u l壱p trinh song song và phân tán

• Cài đ員t m瓜t s嘘 thu壱t toán v噂i ki院n th泳c có đ逢嬰c

N瓜i dung c栄a lu壱n v<n đ逢嬰c chia làm 6 ch逢挨ng :

Ch逢挨ng 1. Gi噂i thi羽u : Gi噂i thi羽u t鰻ng quan v隠 tính toán l逢噂i, khái

ni羽m l鵜ch s穎 phát tri吋n.

Ch逢挨ng 2. Tính toán song song và phân b嘘 : Trình bày v隠 các ki院n

trúc, mô hình x穎 lý song song và phân b嘘, cách th泳c xây d詠ng ch逢挨ng trình,

thi院t k院 thu壱t toán…

Ch逢挨ng 3. Các môi tr逢運ng h厩 tr嬰 tính toán l逢噂i : Tìm hi吋u v隠 các

môi tr逢運ng đang đ逢嬰c s穎 d映ng và nghiên c泳u hi羽n nay trên th院 gi噂i.

Ch逢挨ng 4. Mô hình l壱p trình truy隠n thông đi羽p - MPI : Mô hình c映

th吋 đ逢嬰c dùng đ吋 phát tri吋n 泳ng d映ng MPI.

Ch逢挨ng 5. Th穎 nghi羽m các thu壱t toán lý thuy院t đ欝 th鵜 : Cách th泳c

xây d詠ng ch逢挨ng trình , các khái ni羽m lý thuy院t, th詠c nghi羽m th詠c t院 …

Ch逢挨ng 6. T鰻ng k院t : Nêu các k院t qu違 đã đ衣t đ逢嬰c, m瓜t s嘘 v医n đ隠 còn

t欝n t衣i, đ鵜nh h逢噂ng m映c tiêu m荏 r瓜ng phát tri吋n đ隠 tài trong t逢挨ng lai.

M映c l映c

Danh sách hình..................................................................................................... 11

Ch逢挨ng 1. Gi噂i thi羽u ........................................................................................... 13

1.1. Các khái ni羽m.......................................................................................... 13

1.2. Nh英ng thách th泳c đ嘘i v噂i tính toán l逢噂i................................................. 16

Ch逢挨ng 2. Tính toán song song và phân b嘘...................................................... 17

2.1. Khái ni羽m ................................................................................................ 17

2.2. N隠n t違ng tính toán song song và phân b嘘 ............................................... 18

2.2.1. Ki院n trúc x穎 lý song song và phân b嘘 ..............................................18

2.2.2. T鰻 ch泳c v壱t lý c栄a các n隠n t違ng song song và phân b嘘....................25

2.3. M瓜t s嘘 mô hình l壱p trình song song thông d映ng..................................... 26

2.3.1. Mô hình chia s胤 không gian b瓜 nh噂..................................................26

2.3.2. Mô hình truy隠n thông đi羽p ...............................................................27

2.4. Cách th泳c xây d詠ng m瓜t ch逢挨ng trình song song và phân b嘘................ 29

2.4.1. Các thu壱t ng英 c<n b違n.......................................................................29

2.4.2. Thi院t k院 thu壱t toán song song ...........................................................31

2.4.3. M瓜t s嘘 ph逢挨ng pháp t嘘i 逢u...............................................................43

2.4.4. Các mô hình thu壱t toán song song....................................................48

Ch逢挨ng 3. Các môi tr逢運ng h厩 tr嬰 tính toán l逢噂i ............................................. 52

3.1. Gi噂i thi羽u................................................................................................. 52

3.2. Các v医n đ隠 khi l壱p trình lu噂i ................................................................... 53

3.2.1. Tính mang chuy吋n, tính kh違 thi và kh違 n<ng thích 泳ng....................53

3.2.2. Kh違 n<ng phát hi羽n tài nguyên .........................................................54

3.2.3. Hi羽u n<ng..........................................................................................54

3.2.4. Dung l厩i ............................................................................................55

3.2.5. B違o m壱t .............................................................................................55

3.2.6. Các siêu mô hình...............................................................................55

3.3. T鰻ng quát v隠 các môi tr逢運ng h厩 tr嬰........................................................ 56

3.3.1. M瓜t s嘘 môi tr逢運ng Grid....................................................................56

3.3.2. Nh英ng mô hình l壱p trình và công c映 h厩 tr嬰......................................59

3.3.3. Môi tr逢運ng cài đ員t ............................................................................64

3.4. Nh英ng k悦 thu壱t nâng cao h厩 tr嬰 l壱p trình ............................................... 75

3.4.1. Các k悦 thu壱t truy隠n th嘘ng.................................................................76

3.4.2. Các k悦 thu壱t h逢噂ng d英 li羽u...............................................................76

3.4.3. Các k悦 thu壱t suy đoán và t嘘i 逢u........................................................77

3.4.4. Các k悦 thu壱t phân tán........................................................................77

3.4.5. Nh壱p xu医t h逢噂ng Grid ......................................................................78

3.4.6. Các d鵜ch v映 giao ti院p c医p cao ...........................................................78

3.4.7. B違o m壱t .............................................................................................80

3.4.8. Dung l厩i ............................................................................................80

3.4.9. Các siêu mô hình và h羽 th嘘ng th運i gian th詠c h逢噂ng Grid................82

3.5. Tóm t逸t .................................................................................................... 83

Ch逢挨ng 4. Mô hình l壱p trình truy隠n thông đi羽p - MPI................................... 85

4.1. Các khái ni羽m c挨 b違n .............................................................................. 86

4.2. C医u trúc ch逢挨ng trình MPI ..................................................................... 89

4.3. Trao đ鰻i thông tin đi吋m-đi吋m ................................................................. 90

4.3.1. Các thông tin c栄a thông đi羽p ............................................................90

4.3.2. Các hình th泳c truy隠n thông...............................................................91

4.3.3. Giao ti院p blocking.............................................................................92

4.3.4. Giao ti院p non-blocking .....................................................................96

4.4. Trao đ鰻i thông tin t壱p h嬰p..................................................................... 101

4.4.1. A欝ng b瓜 hóa....................................................................................101

4.4.2. Di d運i d英 li羽u trong nhóm ..............................................................101

4.4.3. Tính toán g瓜p..................................................................................105

4.5. Các ki吋u d英 li羽u..................................................................................... 109

4.5.1. Nh英ng ki吋u d英 li羽u đã đ逢嬰c đ鵜nh ngh┄a .........................................109

4.5.2. Các ki吋u d英 li羽u b鰻 sung.................................................................110

4.5.3. Pack và UnPack ..............................................................................113

Ch逢挨ng 5. Th穎 nghi羽m các thu壱t toán lý thuy院t đ欝 th鵜................................. 114

5.1. Các khái ni羽m c挨 b違n ............................................................................ 114

5.2. Dijkstra.................................................................................................. 115

5.2.1. Tu亥n t詠............................................................................................115

5.2.2. Song song........................................................................................119

5.2.3. Th詠c nghi羽m ch逢挨ng trình .............................................................120

5.3. Prim ....................................................................................................... 122

5.3.1. Tu亥n t詠............................................................................................122

5.3.2. Song song........................................................................................124

5.3.3. Th詠c nghi羽m ch逢挨ng trình .............................................................126

5.4. Bellman – Ford...................................................................................... 128

5.4.1. Tu亥n t詠............................................................................................128

5.4.2. Song song........................................................................................130

5.4.3. Th詠c nghi羽m ch逢挨ng trình .............................................................132

5.5. Aánh giá chung...................................................................................... 134

Ch逢挨ng 6. T鰻ng k院t........................................................................................... 136

6.1. K院t lu壱n ................................................................................................. 136

6.2. H逢噂ng phát tri吋n ................................................................................... 136

Tài li羽u tham kh違o ............................................................................................. 138

Danh sách hình

Hình 1-1 : 3 t亥ng c栄a Grid ................................................................................ 15

Hình 2-1 : Phân l丑ai h羽 th嘘ng máy tính theo Flynn-Johnson ........................... 19

Hình 2-2 : Ki院n trúc SISD ................................................................................ 19

Hình 2-3 : Ki院n trúc SIMD ............................................................................... 20

Hình 2-4 : Ki院n trúc MISD ............................................................................... 22

Hình 2-5 : Ki院n trúc MIMD.............................................................................. 23

Hình 2-6 : Mô hình chía s胤 không gian b瓜 nh噂 ................................................ 27

Hình 2-7 : Mô hình truy隠n thông đi羽p .............................................................. 28

Hình 3-1 : Mô hình NetSolve............................................................................ 56

Hình 3-2 : Các thành ph亥n c栄a Globus ............................................................. 59

Hình 4-1 : Các ti院n trình t衣o l壱p trên mô hình l壱p trình MPI ........................... 86

Hình 4-2 : Cách th泳c truy隠n thông c栄a các process.......................................... 87

Hình 4-3 : Blocking và non-blocking ............................................................... 88

Hình 4-4 : Group, communicator và rank......................................................... 88

Hình 4-5 : C医u trúc c栄a ch逢挨ng trình MPI ....................................................... 89

Hình 4-6 : Giao ti院p blocking ........................................................................... 92

Hình 4-7 : Th泳 t詠 các x穎 lý............................................................................... 95

Hình 4-8 : Cách th泳c x穎 lý ti院n trình................................................................ 95

Hình 4-9 : Giao ti院p non-blocking.................................................................... 96

Hình 4-10 : Broadcast d英 li羽u......................................................................... 102

Hình 4-11 : Ví d映 hàm Scatter ........................................................................ 103

Hình 4-12 : Hàm MPI_Gather ........................................................................ 103

Hình 4-13 : Hàm MPI_Allgather .................................................................... 104

Hình 4-14 : Hàm MPI_Alltoall ....................................................................... 104

Hình 4-15 : Hàm MPI_Reduce ....................................................................... 105

Hình 4-16 : S穎 d映ng 8 x穎 lý đ吋 tính giá tr鵜 tuy羽t đ嘘i...................................... 107

Hình 4-17 Hàm Mpi-Allreduce....................................................................... 108

Hình 4-18 : Hàm MPI_Reduce_scatter........................................................... 108

Hình 4-19 : Hàm MPI_Scan ........................................................................... 109

Hình 4-20 : MPI_Type_contiguous ................................................................ 110

Trang 12

Hình 4-21 : MPI_Type_vetor.......................................................................... 111

Hình 4-22 : MPI_Type_indexed ..................................................................... 112

Hình 4-23 : MPI_Type_struct......................................................................... 112

Hình 5-1. Thu壱t toán Dijkstra tu亥n t詠............................................................. 118

Hình 5-2 : Thu壱t toán Dijkstra song song....................................................... 119

Hình 5-3. Thu壱t toán Prim tu亥n t詠 .................................................................. 124

Hình 5-3 : Thu壱t toán Prim song song............................................................ 125

Hình 5-4: Thu壱t toán Bellman-Ford tu亥n t詠 ................................................... 130

Hình 5-5 : Thu壱t toán Bellman-Ford song song ............................................. 132

Trang 13

Ch逢挨ng 1. Gi噂i thi羽u

1.1. Các khái ni羽m

Trong nh英ng n<m đ亥u th壱p niên 90, nhi隠u nhóm nghiên c泳u đã b逸t đ亥u

khai thác các ngu欝n tài nguyên tính toán phân tán trên Internet. Các nhà khoa

h丑c đã t壱p trung và s穎 d映ng hàng tr<m các máy tr衣m đ吋 th詠c hi羽n các ch逢挨ng

trình song song nh逢 thi院t k院 phân t穎 và hi吋n th鵜 đ欝 h丑a máy tính. Trong khi đó

các nhóm nghiên c泳u khác đã k院t h嬰p các siêu máy tính l噂n l衣i v噂i nhau thành

m瓜t siêu máy tính 違o duy nh医t, r欝i phân ph嘘i các ph亥n c栄a m瓜t 泳ng d映ng r医t

l噂n cho các máy tính trên m瓜t m衣ng di羽n r瓜ng, ví d映 nh逢 máy tính gi違 l壱p các

泳ng d映ng t逢挨ng tác gi英a ch医t l臼ng và cánh qu衣t c栄a chân v鵜t tàu…Thêm vào đó

ph衣m vi c栄a các d詠 án nghiên c泳u này đã nêu ra ti隠m n<ng th詠c s詠 c栄a m衣ng

máy tính, cùng v噂i c挨 s荏 ph亥n m隠m và tin h丑c đ吋 phát tri吋n nó xa h挨n.

H羽 th嘘ng đa b瓜 x穎 lý (Multiprocessor Systems - MPs), Cluster, Grids là

các ví d映 c栄a ki院n trúc tính toán phân tán. Trong MPs, các b瓜 x穎 lý đ逢嬰c k院t

h挨p ch員t ch胤 v噂i nhau, thông qua b瓜 nh噂 chia s胤 chung và đ逢運ng truy隠n k院t n嘘i

r医t cao. Ví d映 nh逢 là PVPs (Parallel Vector Processors), chúng h亥u nh逢 r医t

thích h嬰p cho tính toán hi羽u n<ng cao, nh逢 là các 泳ng d映ng song song d詠a vào

trao đ鰻i thông đi羽p t嘘c đ瓜 cao gi英a các ti院n trình song song.

Tài liệu tương tự (6)

Xem tất cả

PREMIUM

4662 lượt xem

Tài liệu Luận văn - Nghiên cứu tình hình tiêu thụ sản phẩm gà giống thương phẩm pptx

Xem chi tiết

PREMIUM

3108 lượt xem

Tài liệu Luận văn: Nghiên cứu ngôn ngữ UML và ứng dụng doc

Xem chi tiết

PREMIUM

5439 lượt xem

Luận văn Nghiên cứu xây dựng chuẩn đầu ra ngành công nghệ thông tin trường Cao đẳng Nghề Kỹ thuật

Xem chi tiết

PREMIUM

3108 lượt xem

Luận văn Nghiên cứu và đánh giá tác động của biến đổi khí hậu đến hoạt động nuôi trồng thủy sản tại

Xem chi tiết

PREMIUM

6216 lượt xem

Tài liệu LUẬN VĂN: Nghiên cứu, phân tích, nắm bắt những quy luật khách quan và thực tiễn để đề ra

Xem chi tiết

PREMIUM

7770 lượt xem

Luận văn: Nghiên cứu sự ảnh hưởng của thức ăn đến sự tăng trưởng và tỷ lệ sống của tôm thẻ chân

Xem chi tiết

Tải ngay đi em, còn do dự, trời tối mất!