KILOBOOKS.COM
1

MC LC

LI NểI U2
Chng 1: TNG QUAN V X L SONG SONG4
1.1 X lý song song4
1.2 Phõn loi kin trỳc mỏy tớnh4
1.3 Cỏc thnh phn chớnh ca mỏy tớnh song song7
1.4 Thit k v ỏnh giỏ thut toỏn song song
1.5 Kin trỳc cm mỏy tớnh
Chng 2: GIAO DIN TRUYN THễNG IP MPI
2.1 Gii thiu v MPI
2.2 Mụ hỡnh lp trỡnh MPI
2.3 Nhng hm MPI c bn
2.4 Nhng hm truyn thng tp th
Chng 3: MT S PHNG PHP LP GII H I S TUYN TNH
3.1 Gii thiu
3.2 Mt s phng phỏp lp tun t gii h phng trỡnh i s tuyn tớnh
3.3 Mt s thut toỏn lp song song gii h phng trỡnh i s tuyn tớnh
3.4 Chng trỡnh th nghim
KT LUN
TI LIU THAM KHO
PH LC


THệ VIEN ẹIEN Tệ TRệẽC TUYEN

KILOBOOKS.COM
3
Khóa luận này chắc chắn khơng tránh khỏi thiếu sót do hạn chế về thời gian
cũng như kiến thức. Em rất mong nhận được sự đóng góp ý kiến của thầy cụ và cỏc
bạn để có thể phát triển đề tài đạt được kết quả tốt hơn.
Em xin gửi lời cảm ơn chân thành tới thầy giáo về sự tận tâm hướng dẫn, giúp
đỡ em hồn thành khóa luận này. Em xin cảm ơn tất cả các các thầy cơ khoa Tốn
Cơ Tin học, các thầy cơ trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà
Nội về sự dạy dỗ ân cần trong thời gian em học tại trường. Em xin cảm ơn các thầy
cơ, các anh chị của Trung Tâm Tính Tốn Hiệu Năng Cao đó tạo điều kiện và giúp
đỡ em rất nhiều trong việc hồn thành khóa luận. Xin cảm ơn gia đỡnh, người thân
và bạn bè đó luụn ủng hộ và là nguồn cổ vũ lớn lao cho tơi.


THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN


Hỡnh 1.1. Mụ hỡnh của kiến trỳc SISD
1.2.2 Kiến trúc SIMD (đơn dũng lệnh, đa luồng dữ liệu)
Những máy tính SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị xử
lí thực hiện một dũng cỏc cõu lệnh. Đơn vị điều khiển phát sinh tín hiệu điều khiển
tới tất cả cỏc bộ xử lớ thực hiờn cựng một phộp toỏn trờn cỏc mục dữ liệu khỏc
nhau.

Hỡnh 1.2. Mụ hỡnh của kiến trỳc SIMD
1.2.3 Kiến trúc MISD (đa dũng lệnh, đơn luồng dữ liệu)
Mỏy tớnh loại MISD cú thể thực hiện nhiều chương trỡnh trờn cựng một mục
dữ liệu. Kiến trỳc kiểu này chia thành hai nhúm như sau:
• Lớp các máy tính yêu cầu các đơn vị xử lí khác nhau có thể nhận những
lệnh khác nhau và thực hiện trên cùng một mục dữ liệu.
Đơn vị điều
khiển
Bộ xử lớ
số học
Bộ nhớ
Luồng
kết quả
Dũng
lệnh
Luồng
dữ liệu
Đơn vị điều khiển
Phần tử
xử lớ 1
Phần tử
xử lớ 2

.
.
.
.
.
Luồng dữ liệu 1
Luồng dữ liệu 2
Đơn vị điều khiển1
Đơn vị điều khiển 2
Đơn vị điều khiển n
Phần tử xử lớ 1
Phần tử xử lớ 2
Phần tử xử lớ n
Dũng lệnh 1
Dũng lệnh 2
Dũng lệnh n
.
.
.
.
.
.
Luồng
dữ liệu
Luồng dữ liệu 2

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM
7
Hỡnh 1.4. Mụ hỡnh của kiến trỳc MIMD

• Ghi độc quyền EW (Exclusive Write): mỗi bộ xử lí chỉ ghi được vào một
ô nhớ và mỗi ô nhớ chỉ được ghi bởi một bộ xử lí.
Dễ nhận thấy rằng ER và EW là những trường hợp riêng của CR và CW. Trong
đó CW có những đặc tính sau:
• Ghi đồng thời có ưu tiên (Priority CW): mỗi bộ xử lí được gắn với một
mức ưu tiên, bộ nhớ có mức ưu tiên cao nhất sẽ được quyền ghi vào một
ô nhớ cho trước. Các mức ưu tiên có thể tĩnh hoặc động theo qui tắc xác
định.
• Ghi đồng thời chung (Common CW): tất cả các bộ xử lí được phép ghi
vào cụng một ô nhớ nếu chúng ghi cùng một giá trị. Khi đó một bộ xử lí
sẽ được chọn để thực hiện việc ghi dữ liệu đó.
• Ghi đồng thời tự do (Arbitracy CW): một số bộ xử lí muốn ghi dữ liệu
vào một ô nhớ nhưng chỉ một bộ xử lí được phép. Trong trường hợp này
ta phải chỉ ra cách xác định bộ xử lí được chọn.
• Ghi đồng thời ngẫu nhiên (Random CW): bộ xử lí được chọn để ghi dữ
liệu là ngẫu nhiên.

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM
9
Ghi ng thi kt hp (Combining CW): tt c cỏc giỏ tr m cỏc b x lớ
mun ghi ng thi lờn mt ụ nh s c kt hp li thnh mt giỏ tr
v giỏ tr ny s c ghi vo ụ nh ú.
Mt s m hnh b nh cho my truy cp ngu nhin song song PRAM:
1. M hnh truy cp b nh ng b UMA (Uniform Memory Access) ca
b nh chia s: tt c cỏc b x lớ lm vic nh c ch chuyn mch tp
trung truy cp ti b nh chia s. Thi gian truy cp vo b nh l
nh nhau vi tt c cỏc b x lớ.
2. M hnh truy cp b nh khng ng b NUMA ca b nh chia s:
trong m hnh ny, b nh c phõn tỏn v c chia thnh mt s

Hỡnh 1.6. Mạng liờn kết tuyến tớnh của n bộ xử lớ
2. Mạng liờn kết vũng
Mạng liờn kết vũng cú thể được tổ chức như mạng tuyến tính bằng cách nối hai
bộ xử lí đầu và cuối. Sự trao đổi giữa các bộ xử lí có thể theo một chiều hoặc hai
chiều tuy nhiên việc truyền thông giữa các bộ xử lí đặc biệt là các bộ xử lí ở xa
nhau vẫn bị trễ.

Hỡnh 1.7. Mạng liờn kết vũng của n bộ xử lớ
3. Mạng liờn kết xỏo trộn
P
0
P
1
P
n-1
P
0
P
1
P
n-1

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM
11
Gi s cỳ N b x l P
0
, P
1
,, P

N-1
t liờn kt vi chớnh
nú, b x lớ i c liờn kt vi b x lớ 2i mod (N-1).
4. Mng liờn kt li hai chiu
Trong mng liờn kt li hai chiu, cỏc b x lớ c sp xp thnh mt ma
trn hai chiu, mi b x lớ c liờn kt vi bn lỏng ging: trờn, di, trỏi, phi.
Khụng cú qui lut chung cho nhng b x lớ biờn. Cú hai bin th ca mng li
hai chiu: li hai chiu khng cỳ kt ni vng v li hai chiu cú kt ni vng.

P
0
P
1
P
2
P
3
P
4
P
5
P
6
P
7
vi
vi

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM


THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM
13

Hnh 1.11: Mng lin kt hnh sao vi 24 b x l
1.4 Thit k v ỏnh giỏ thut toỏn song song
1.4.1 Nguyn l thit k thut ton song song
Thut toỏn song song c nh ngha l mt tp cỏc tin trnh hoc cc tc v
cỳ th thc hin ng thi v cú th trao i d liu vi nhau kt hp cựng gii
mt bi toỏn. Cú th cú nhiu thut ton song song cng gii mt bi ton ty
thuc vo cch phừn chia d liu cho cc tc v, cch truy xut d liu, cch phừn
rú cc tc v v cch ng b cỏc tin trnh. thit k mt thut toỏn song song
tt ta cú th s dng nm nguyờn lớ chớnh trong thit k thut ton song song:
P
1234
P
3214
P
2314
P
2134
P
1324
P
3124
P
4231
P
3241

P
4132

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM
14
- Ngun lí lập lịch: Giảm tối thiểu các bộ xử lí trong thuật tốn mà khơng
làm tăng thời gian tính tốn. Nói chung, khi số bộ xử lí giảm thời gian thực
hiện của chương trỡnh cú thể tăng và có thể tăng lên một hằng số nào đó
nhưng xét theo độ phức tạp của thuật tốn thỡ vẫn khụng thay đổi.
- Ngun lí đường ống: Ngun lí này được áp dụng trong trường hợp ta
muốn thực hiện một dóy cỏc thao tỏc theo trỡnh tự {P
1
, P
2
,…, P
n
} trong đó
một số bước của P
i+1
có thể thực hiên trước khi P
i
kết thỳc.
- Ngun lí chia để trị: Chia bài tốn thành các phần nhỏ tương đối độc lập và
giải quyết chúng đồng thời.
- Ngun lí đồ thị phụ thuộc dữ liệu: Chúng ta xây dựng một đồ thị có hướng
trong đó các nút biểu diễn các khối câu lệnh độc lập cũn cỏc cạnh biểu diễn
tỡnh huống khối này phụ thuộc kết quả từ việc thực hiện của khối kia. Từ đó
ta tỡm cỏch loại bỏ cỏc phụ thuộc để xây dựng thuật tốn song song.
- Nguyờn lớ cạnh tranh: Nếu hai tiến trỡnh cựng truy cập vào một mục dữ

1. Thi gian thc hin
Thi gian thc hin ca mt thut ton bao gm: thi gian tnh ton, thi gian
truyn thng v thi gian ri.
Thi gian tnh ton
Thi gian tnh ton ca mt thut ton (T
comp
) l thi gian s dng
tớnh toỏn (bao gm cỏc phộp toỏn logic v s hc). Nu chỳng ta cú mt
chng trnh tun t m thc hin tnh ton ging nh thut toỏn song song
chỳng ta cú th xỏc nh T
comp
bng vic tớnh thi gian chng trnh ú. Nu
khụng chỳng ta cú th phi thc thi nhng nhõn then cht. Thi gian tớnh
toỏn s thng ph thuc vo kớch thc bi toỏn dự nú c biu din bi
mt tham s N hay bi mt tp cỏc tham s N
1
, N
2
, , N
m
.Thi gian tnh

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM
16
ton cn ph thuc vo s cc tc v hoc s b x l. Trong mng my
tnh song song khng ng nht ( nh mng cỏc mỏy trm), thi gian tớnh
toỏn cú th bin thiờn theo b x lớ m ti ú tớnh toỏn c thc hin. Thi
gian tớnh toỏn cng ph thuc vo c im ca nhng b x lớ v phng
thc nh ca chỳng.

s
+ T
w
L

THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM
17
Thi gian ri
Thi gian tớnh toỏn v thi gian truyn thụng u c ch ra mt cỏch
r rng trong thut ton song song v th khng khỳ khn tớnh tng ca
chỳng trong thi gian thc hin. Thi gian ri (T
idle
) cú th khú xỏc nh hn,
tuy nhiờn chỳng thng ph thuc vo th t cỏc thao tỏc c thc hin.
Mt b x l cỳ th ri v khng cỳ tnh ton hoc thiu d liu. Trong
trng hp u tiờn, thi gian ri cú th trỏnh bng vic s dng nhng k
thut ti cõn bng. Trong trng hp th hai b x lớ ri trong khi tớnh toỏn
v truyn thụng i d liu xa c thc hin. Thi gian ri ny ụi khi cú
th trỏnh bng vic xõy dng mt chng trnh m nhng b x l thc hin
nhng tớnh toỏn hoc truyn thụng khỏc trong khi i d liu xa.
2. Hiu sut v h s gia tc
Thi gian thc hin khụng phi lỳc no cng l thc o tt nht ỏnh giỏ
hiu nng thut toỏn. V thi gian thc hin cỳ khuynh hng bin thiờn theo kớch
thc bi toỏn, thi gian thc hin phi c chun húa khi so sỏnh hiu nng thut
toỏn vi nhng kớch thc khỏc nhau ca bi toỏn. Hiu sut - phn thi gian m
b x lớ s dng lm cụng vic cú ớch- cung cp mt thc o tt cho cht lng
ca mt thut toỏn song song. Nú c trng húa s hiu qu ca mt thut toỏn s
dng ti nguyờn tớnh toỏn ca mt mỏy tớnh song song mt cỏch c lp vi kớch
thc bi toỏn. Chỳng ta nh ngha hiu sut tng i nh sau:

) cho thuật
tốn tốt nhất. Trong nhiều trường hợp, thuật tốn tốt nhất này sẽ là thuật toỏn (tuần
tự) tốt nhất.
1.5 Kiến trỳc cụm mỏy tớnh
Trước đây, thuật ngữ “máy tính hiệu năng cao” (High- Performance Computing
- HPC) thường được dùng để chỉ những máy tính song song hoặc máy tính véc tơ
với giá trị lên tới hàng triệu đơla. Nhưng với sự phát triển nhanh chóng của cơng
nghệ phần cứng đặc biệt là những tiến bộ trong việc cải tiến hiệu năng của bộ xử lí
và băng thơng mạng đó làm thay đổi một cách tồn diện kiến trúc của các máy tính
hiệu năng cao. Và khi các máy tính hiệu năng cao được tạo ra bằng cỏch kết nối
cỏc mỏy trạm (Workstation – WS) với nhau thỡ thuật ngữ “cụm mỏy tớnh”
(Computer Cluster) được sử dụng để mơ tả dạng máy tính này.
Cụm máy trạm (Workstation Cluster -WSC) là một nhóm các máy trạm được
kết nối với nhau thơng qua một mạng tốc độ cao. Các máy tính trong một WSC
truyền thơng qua một trong hai giao thức truyền thơng phổ biến đó là: truyền thơng
dựa trên kết nối và truyền thơng khơng kết nối. Mơ hỡnh kết nối dựa trờn giao thức
TCP (Tranmission Control Protocol) với độ tin cậy cho việc truyền thơng điệp
được bảo đảm. Mơ hỡnh khụng kết nối dựa trờn giao thức UDP (User Datagram

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
KILOBOOKS.COM
19
Protocol), với giao thức này độ tin cậy cho việc truyền thơng điệp được bảo đảm.
Hiện nay có rất nhiều phần mềm hỗ trợ việc tính tốn song song trên WSC tiêu
biểu như MPICH.
WSC có rất nhiều ưu điểm đó là:
o Kĩ thuật tính tốn trên các cụm máy tính có thể mở rộng từ một hệ thống
nhỏ đến các hệ thống rất lớn. Điều này thể hiện tính mềm dẻo và linh
hoạt của hệ thống. Hệ thống có thể chỉ gồm một máy tính hoặc nhiều
máy tính ghép nối mạng với nhau. Những máy tính nối mạng Internet

8 node tớnh toỏn, mi node gm 2 chip Intel Xeon Dual Core 3.2 GHz, 2
GB RAM, 1x36 GB HDD, DVD ROM. Tng nng lc tớnh toỏn ca 8
node l khong 51.2 Gflops.
2 node phc v lu tr, mi node gm 2 chip Intel Xeon Dual Core 3.2
GHz, 3 GB RAM, 4x72 GB HDD.
1 node úng vai tr qun l bao gm chip Intel Xeon Dual Core 3.2
GHz, 3 GB RAM, 2x36 GBHDD.
Nng lc lu tr: thit b lu tr dựng chung EXP400 vi 10x73 GB
HDD SCSI 320 MBps 15KRpm, dựng h thng chia s file: GPFS cho
Linux v2.3.0.5
Cỏc node chy HH Redhat Enterprise Linux 3.0 v c kt ni vi
nhau thụng qua mng Gethernet.


THệ VIEN ẹIEN Tệ TRệẽC TUYEN
KILOBOOKS.COM
21


truyền thơng cục bộ và khơng có cấu trúc. Một nhóm các tiến trỡnh cú thể gọi cỏc
thao tỏc truyền thụng tập thể để thực hiện những thao tác tồn cục như tổng hợp và
quảng bá. MPI hỗ trợ truyền thơng khơng đồng bộ (dị bộ). Có lẽ tính năng quan
trọng nhất của MPI từ quan điểm của cơng nghệ phần mềm là nó hỗ trợ lập trỡnh
module. Một cơ chế được gọi là bộ truyền thơng (communicator) cho phộp lập
trỡnh viờn MPI định nghĩa module trong đó đóng gói các cấu trúc truyền thơng bên
trong.
Những thuật toỏn mà tạo ra chỉ một tỏc vụ trờn một bộ xử lý cú thể thực hiện
trực tiếp sử dụng những hàm truyền thụng tập thể hay điểm tới điểm. Những thuật
tốn mà tạo ra nhiều tác vụ theo một cách động hoặc phụ thuộc vào sự thực hiện
đồng thời của một vài tác vụ trên 1 bộ xử lý phải được biến đổi để có thể thực thi
MPI.

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
KILOBOOKS.COM
23
2.3 Nhng hm MPI c bn
Mc d MPI l mt h thng phc tp chng ta cỳ th gii nhng bi toỏn
thuc mt phm vi rng m ch s dng 6 hm c bn. Nhng hm ny khi to v
kt thỳc mt chng trnh MPI, xc nh nhn dng cỏc tin trnh, gi v nhn
thng ip.
MPI_Init khi to mụi trng MPI
MPI_Finalize úng mụi trng MPI
MPI_Comm_size xỏc nh s cỏc tin trnh
MPI_Comm_rank xỏc nh s hng tin trnh
MPI-Send gi mt thụng ip
MPI-Recv nhn mt thụng ip
Nhng hm ny c mụ t chi tit sau õy,trong ú nhún IN, OUT, v INOUT
ng trc tham s ch ra rng:
IN: hm s dng nhng khụng lm thay i tham s.

nhầm lẫn. Nó cung cấp giá trị mặc định MPI_COMM_WORLD, xác định tất
cả các tiến trỡnh trong chương trỡnh. Mỗi tiến trỡnh được gán một số hạng là
số nguyên liên tiếp bắt đầu từ 0. Số hạng này cũn được gọi là id của tiến
trỡnh.
Bốn hàm trờn thuộc nhúm những hàm quản lý mụi trường. Một ví dụ nhỏ sử
dụng các hàm này viết bằng ngôn ngữ C.

#include <mpi.h>
#include <stdio.h>

THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
KILOBOOKS.COM
25

int main(int argc, char **argv)
{
int rank, size;
MPI_Init( &argc, &argv );
MPI_Comm_rank(MPI_COMM_WORLD, &rank );
MPI_Comm_size(MPI_COMM_WORLD, &size );
printf("Hello! I am %d of %d \n", rank, size);
MPI_Finalize();
return 0;
}

Nếu chương trỡnh trờn được chạy bởi 4 tiến trỡnh thỡ ta sẽ thu được kết quả có
dạng như sau:
Hello! I am 1 of 4
Hello! I am 3 of 4
Hello! I am 0 of 4