TRNG 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  TH
KHÓA LUN C NHÂN TIN HC
GIÁO VIÊN HNG DN
TS. TRN AN TH
Th.S NGUYN THANH SN



NHN XÉT CA GIÁO VIÊN PHN BIN


Chúng em xin bày t lòng bit n chân thành nht đn thy Trn an
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 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



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


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


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. ánh giá chung 134

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

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.
Trang 14
Trong khi đó Cluster li là các máy tính đn hay đa b x lý đc kt
hp tng đi vi nhau thông qua đng mng, vì th nó chm hn t 1 đn 2
ln so vi kt ni MP. Ví d nh cluster Beowulf chy Linux, hay TCF
(Technical Compute Farm) ca Sun chy h điu hành Solaris/TM, chúng đc
s dng cho các tính toán s lng ln, phân phi các tác v tính toán (thng
là không song song) cho các b x lý, ri thu thp li các kt qu tính toán vào
kt qu toàn cc. Các tính toán này có th là vic hin th hàng ngàn khung
hình đ làm phim hay là gi lp vic kim tra và thit k đ xây dng th h
tip theo ca chip VLSI, hay nh trong công ngh sinh hc, đó là vic ct lp
hàng trm ngàn chui gen.
Trong khi MPs và Cluster ch là các h thng đn, thng là trong mt
domain đn. Grid đin toán bao gm các cluster ca mng các MPs hay/và
cluster, nm trên nhiu domain khác nhau, phân b  nhiu phòng ban, xí
nghip hay thm chí là trên mng Internet. V bn cht, nhng grid có mt đ
phc tp cao hn, đc bit là  tng trung gian, trong vic thc thi, qun lý, và
s dng các tài nguyên tính toán phân tán, và  tng ng dng là vic thit k,
phát trin, chy các phn mm đ trin khai grid mt cách hiu qu.

Ngày nay chúng ta đang thy nhng n lc đu tiên nhm khai thác mt
cách có h thng các ngun tài nguyên tính toán li trên mng Internet.
Nhng d án này đc gi là peer-to-peer computing, nh SETI@home,
Distributed.Net và Folderol, cho phép ngi dùng Internet ti v các d liu
khoa hc, chy trên các máy cá nhân theo chu trình x lý chia s, và gi li kt
qu cho c s d liu trung tâm. Gn đây có mt d án  mt trng đi hc,
đc gi là Compute Power Market, đc xây dng nên nhm phát trin các k
thut phn mm cho phép to lp nhng Grid, mà  đó bt c ai cng có th
mua hay bán kh nng kh nng tính toán ging nh cách mà ngi ta s dng
đin hin nay.
Trang 16
1.2. Nhng thách thc đi vi tính toán li
Hu ht các k thut phc tp bên di dành cho Grid hin nay đang
đc tip tc phát trin. Các môi trng Grid mu tn ti ging nh các d án
Globus và Legion.  án EcoGrid thì đang nghiên cu cách thc qun lý tài
nguyên, và các khi xây dng nh vy đang tn ti trong trình qun lý tài
nguyên mang tính thng mi ca phn mm Sun Grid Engine.
Din đàn Grid (GGF – Global Grid Forum), đc thành lp vào nm
1998, đã tp hp đc hàng trm các nhà khoa hc đ cùng nhau nghiên cu và
tho lun v mt kin trúc Grid chung. Trong đó vn còn tn ti mt s thách
thc sau:

Trang 17
Chng 2. Tính toán song song và phân b
2.1. Khái nim
Ngày nay trong khi công ngh ngày mt phát trin thì nhu cu v tc đ
tính toán ca các h thng máy tính cng ngày mt tng cao. Các lnh vc đòi
hi tính tóan hiu nng cao nh là mô hình s và gi lp các vn đ ca khoa
hc và công ngh.
Ngoài ra nó còn nhm gii quyt các lai vn đ cn tc đ x lý cao
nh:
• Mô hình hóa và gi lp
Mô hình các mu DNA
Mô hình hóa chuyn đng ca các phi hành gia
…
• X lý/Thao tác trên các d liu rt ln
X lý nh và tín hiu
Khai thác d liu và c s d liu
Xác đnh đa chn
…
• Các vn đ “grand challenge” (là nhng vn đ không th gii quyt
trong thi gian “hp lý”, nh cn 100, 1000,…nm đ có đáp án)
Mô hình khí hu
S chuyn đng ca cht lng
B gene con ngi
Mô hình cht bán dn
…
Xut phát t nhu cu đó đã dn đn s cn thit phi có nhng h thng
song song và phân b nhm tn dng ti đa kh nng thc thi ca các b x lý,
và đ gii quyt các vn đ nan gii trên.
• SIMD (
Single Instruction stream, Multiple Data streams)
• MISD (
Multiple Instruction streams, a Single Data stream)
• MIMD (
Multiple Instruction streams, Multiple Data streams)
Phân theo mc đ hay đc s dng:
MIMD > SIMD > MISD
Trang 19
Instruction Stream(s)
SISD
(Uniprocessors)
SIMD
(Array Processors)
MISD
GMSV GMMP
DMSV
Data Stream(s)

Trang 20
t. Theo quan đim ca ngi dùng thì các ng dng s dng kin trúc SIMD
thì d dàng đc lp trình hn và tn dng hiu qu hn các thit b phn cng.

Hình 2-3 : Kin trúc SIMD
Bên trong SIMD, tn ti hai la chn thit k c bn sau:
1. SIMD đng b và bt đng b. Trong mt máy SIMD, tng b x
lý có th thc thi hay b qua các ch th đc qung bá da vào trng
thái cc b ca nó hay nhng điu kin ph thuc vào d liu. Tuy
nhiên điu này có th dn đn x lý mt vài tính toán điu kin
không hiu qu. Mt cách gii quyt kh thi là s dng phiên bn bt
đng b ca S1IMD, đc bit đn là SPMD (Single Program
Multiple Data), trong đó tng b x lý s chy mt bn sao ca
Trang 21
chng trình chung. im thun li ca SPMD là trong lúc tính toán
biu thc điu kin “if-then-else”, tng b x lý s ch thc hin 
nhánh thích hp mà không mt thi gian cho các chi phí tính toán
khác.

Hình 2-4 : Kin trúc MISD
Trong hình trên là ví d v mt b x lý song song vi kin trúc MISD.
Mt dòng d liu đn đi vào mt máy tính gm 5 b x lý. Nhiu phép bin
đi đc thc hin trên tng đn v d liu trc khi nó đc chuyn sang mt
(hay nhiu) b x lý khác. Các đn v d liu k tip có th đi qua các phép
bin đi khác do điu kin đc lp d liu ca các dòng ch th hay do các th
điu khin đc bit đc truyn cùng vi d liu. Chính vì vy mà cách t chc
theo kin trúc MISD có th đc xem nh là mt h thng ng lnh cp đ cao
và phc tp vi nhiu đng dn và trong đó tng giai đan có th đc lp
trình riêng bit.
2.2.1.4. MIMD
c tiên đoán bi các doanh nghip vào thp niên 90, mô hình MIMD
gn đây đã tr nên khá ph bin. Lý do cho s thay đi này là vì tính uyn
chuyn cao ca kin trúc MIMD và bi kh nng tn dng đc nhng u
đim ca các b vi x lý đc sn xut hàng lat (commodity
microprocessors), vì th tránh đc nhng vòng phát trin dài dòng và qua đó
có th đc phát trin cùng vi s ci thin ca các b x lý. Các máy tính
MIMD đc áp dng rt hiu qu cho các ng dng song song mà vn đ ca
nó đc phân rã t trung bình cho đn tt (medium- to coarse-grain parallel
applications).u đim ca các máy tính MIMD bao gm kh nng uyn
Trang 23

vic tính toán hiu nng cao, bng cách s dng đa b x lý đc
thit k đc bit trên nhiu máy tính hay là tp hp ca nhng máy
trm bình thng đc kt ni vi nhau bi các h thng mng “tin
nghi” (nh là Ethernet hay ATM) và nhng tng tác nào s đc
kt ni vi nhau bng h thng phn mm đc bit và các h thng
tp tin phân tán? Cách tip cn th hai đôi khi đc bit đn là mng
ca các máy trm (network of workstations hay là NOW) hay là tính
toán cluster, đã đc s dng rng rãi trong nhng nm gn đây. Tuy
nhiên vn còn nhiu vn đ m còn tn ti nhm phát huy ti đa kh
nng ca nhng kin trúc có nn tng là mng. Thit b phn cng,
h thng phn mm, và nhng khía cnh ng dng ca NOW đang
đc đu t tìm hiu bi mt s lng ln các nhóm ngiên cu. Mt
cách tip cn trung gian là kt hp các cluster nhng b x lý thông
qua môi trng mng. iu này v c bn là mt phng pháp phân
nhánh, đc bit thích hp khi có mt s truy cp rt ln đn d liu
cc b.
3. Truyn thông đip tng minh hay chia s b nh o. Lai nào
s tt hn, cho phép ngi dùng ch ra tt c các loi thông đip s
đc truyn gia các b x lý hay là cho phép h lp trình  mt cp
đ tru tng cao hn, cùng vi các thông đip cn thit t đng
đc phát sinh bi h thng phn mm? Câu hi này v c bn là
tng t vi câu đc hi trong nhng ngày đu ca nhng ngôn
ERCW. Cho phép nhiu thao tác ghi cùng lúc trên cùng mt vùng
nh, tuy nhiên nhiu thao tác đc ch thc hin theo tun t.

Trích đoạn Cách th c xây d n gm tch ng trình song song và phâ nb Các mơ hình th ut tốn song song Dung li Giao tip non-blocking

---