Đ I H C ĐÀ NẴNG
TR
NG ĐẠI H C S PHẠM
-------------------------------------

NGUY N ĐĔNG KHOA

NÂNG CAO HI U NĔNG TệNH TOÁN
CHO CÁC BÀI TỐN TÌM Đ
NG ĐI NGẮN NHẤT
VÀ CÂY KHUNG NH NHẤT

Chuyên ngành: H th ng thông tin
Mã s : 848.01.04

TÓM TẮT LU N VĔN THẠC SĨ H TH NG THÔNG TIN

Đà Nẵng - Nĕm 2019


Cơng trình được hồn thành tại
TR

Ng

ih

NG ĐẠI H C S

PHẠM

ng d n khoa học: TS. Nguy n Đình Lầu

Phản biện 1: PGS. TSKH. Trần Quốc Chiến
Phản biện 2: TS. Nguyễn Quang Thanh

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt
nghiệp thạc sĩ ngành Hệ thống thông tin họp tại trường Đại học
Sư phạm vào ngày 06 tháng 4 năm 2019.

Có thể tìm hiểu luận văn tại:
- Thư viện Trường Đại học Sư phạm – ĐHĐN
- Khoa Công nghệ thông tin, trường Đại học Sư phạm - ĐHĐN


1
M

Đ U

1. Lý do chọn đ tài
Công nghệ thông tin đang phát triển với một tốc độ chóng
mặt, đi cùng đó là lượng dữ liệu khổng lồ. Để xử lý lượng dữ liệu
khổng lồ đó địi hỏi khối lượng tính toán rất lớn và thời gian là yếu tố
quyết định tính thực tiễn c a bài tốn đó.Để tăng tốc độ tính tốn,
các nhà khoa học đã đưa ra hai giải pháp:
Th nhất là cải tiến công nghệ, tăng tốc độ xử lý c a máy
tính. Cơng việc này đỏi hỏi nhiều thời gian, công s c và tiền bạc
nhưng tốc độ thì chỉ đạt đến một giới hạn nhất định.
Th hai là chia bài toán ra thành những bài toán nhỏ để chạy
song song trên nhiều bộ xử lý.

Các nhà khoa học đã tập trung nghiên c u ở giải pháp th
hai, từ đó ra đời thuật tốn song song. Đó là việc sử dụng đồng thời
nhiều tài nguyên tính tốn để giải quyết một bài tốn. Các tài ngun
tính tốn có thể bao gồm một máy tính với nhiều bộ vi xử lý hay một
tập các máy tính kết nối mạng hay là một sự kết hợp c a hai dạng
trên. Cơng nghệ tính tốn song song cho phép giảm thời gian thực thi
bài toán tùy thuộc cách phân chia và số bộ xử lý thực thi chương
trình. Ngun tắc quan trọng nhất c a tính tốn song song chính là
tính đồng thời hay xử lý nhiều tác vụ cùng một lúc.
Với mục đích tìm hiểu và nghiên c u về thuật toán song
song để giải quyết bài toán đồ thị một cách hiệu quả hơn, thời gian
xử lý ngắn hơn do đó tơi chọn đề tài: “Nâng cao hiệu năng tính tốn
cho các bài tốn tìm đường đi ngắn nhất và cây khung nhỏ nhất “
2. M c tiêu và nhi m v
2.1. Mục tiêu
Nghiên c u thuật toán song song, ng dụng một thư viện cụ


2
thể nâng cao hiệu năng tính tốn cho hai thuật tốn Dijkstra và Prim
nhằm giảm thời gian thực hiện, góp phần nâng cao hiệu năng hoạt
động c a hệ thống.
2.2. Nhiệm vụ
⁻

Tìm hiểu về lý thuyết đồ thị.

⁻

Nghiên c u về xử lý song song và lập trình song

song.

⁻

Xây dựng và giải quyết một số bài toán đồ thị dự
theo mơ hình thư viện MPI.

⁻
3. Đ i t

Cài đặt và đánh giá kết quả bài toán.
ng và phạm vi nghiên c u:

3.1. Đối tượng nghiên cứu của đề tài
⁻

XLSS và thuật tốn song song.

⁻

Các bài tốn đồ thị.

⁻

Lập trình song song với MPI.

3.2. Phạm vi nghiên cứu của đề tài
⁻

Tổng quan về XLSS và phân tán.


⁻

Tổng quan về lý thuyết đồ thị.

4. Ph

ng pháp nghiên c u

4.1. Nghiên cứu lý thuyết
⁻

XLSS và thuật toán song song.

⁻

Đồ thị và các bài tốn trên đồ thị.

⁻

Tìm hiểu lập trình song song với MPI.

4.2. Nghiên cứu thực nghiệm
⁻

Xây dựng sơ đồ, thuật toán song song.

⁻

Lập trình song song với MPI bằng Visual Studio.


5. B c c đ tài
Ngoài phần mở đầu và kết thúc, nội dung chính c a luận văn


3
có 3 chương.
Chương 1: Xử lý song song và lập trình với MPI .
Chương 2: Các thuật tốn trên đồ thị.
Chương 3: Nghiên cứu ứng dụng thuật toán song song
trên thư viện MPI.
6. ụ nghĩa khoa học và thực ti n c a đ tài
Nghiên c u và nâng cao hiệu năng c a hệ thống bằng XLSS.
Tối ưu hơn về thời gian và chi phí so với phương pháp thơng
thường.
Có thể áp dụng cho một số lĩnh vực cụ thể và một số bài tốn
có độ ph c tạp về thời gian lớn, những bào toán thời gian thực.
Làm giảm chi phí giá thành, thời gian cho các cơ quan,
doanh nghiệp khi ng dụng, triển khai thực tế.
CH

NG 1. X

LÝ SONG SONG VÀ L P TRÌNH
V I MPI

1.1. Gi i thi u v x lý song song
Ngày nay, rất nhiều bài tốn u cầu khả năng tính tốn và
lưu trữ rất lớn thì mơ hình kiến trúc này cịn hạn chế. Do đó để giải
quyết các bài tốn này cần có những hệ thống máy tính đ mạnh để

thực hiện một cách nhanh chóng và hiệu quả. Vì vậy, hướng xử lý
song song với việc kết hợp nhiều bộ xử lý vào trong một máy tính
được lựa chọn để giải quyết các bài toán đặt ra.
Xử lý song song hay tính tốn song song là q trình xử lý
gồm nhiều tiến trình được kích hoạt đồng thời và cùng tham gia giải
quyết một vấn đề, nói chung là thực hiện tính tốn trên những hệ
thống đa bộ xử lý [1].
Máy tính song song là tập hợp các bộ xử lý kết nối với nhau


4
theo một kiến trúc xác định cùng hợp tác hoạt động và trao đổi song
song.
1.2. Ki n trúc máy tính song song
1.2.1. Mơ hình SISD
1.2.2. Kiến trúc song song SIMD
1.2.3. Kiến trúc song song MISD
1.2.4. Mơ hình máy tính MIMD
1.3. Thu t tốn song song
1.3.1. Quy trình thiết kế thuật toán song song
1.3.2. Nguyên lý thiết kế thuật toán song song
1.3.3. Các cách tiếp cận trong thiết kế
1.3.4. Phân tích đánh giá thuật toán song song
Trong thuật toán tuần tự chúng ta chỉ quan tâm đến độ ph c tạp
về thời gian và khơng gian, nhưng trong thuật tốn song song thường có
thêm một số đại lượng đo lường khác. Độ ph c tạp thời gian c a thuật
toán song song không chỉ đơn giản là việc đếm số câu lệnh cơ bản như
trong thuật toán tuần tự mà thay vào đó nó phụ thuộc vào các phép tốn
cơ bản này có thể được thực hiện trên p bộ xử lý như thế nào. Bên cạnh
độ ph c tạp thời gian độ ph c tạp về số bộ xử lý cũng là một đại lượng

quan trọng trong phân tích thiết kế thuật toán song song.
Thiết kế thuật toán song song hiệu quả bao gồm việc lựa chọn
cấu trúc dữ liệu phù hợp, phân bố bộ xử lý và cuối cùng là thực hiện
thuật toán. Ba đại lượng này tác động lẫn nhau như một tổ ch c tính
tốn.
1.4. Các mơ hình l p trình song song
1.4.1. Mơ hình chia sẽ bộ nhớ
1.4.2. Mơ hình luồng
1.4.3. Mơ hình truyền thơng điệp


5
1.4.4. Mơ hình phân hoạch dữ liệu
1.5. L p trình song song trong môi tr

ng MPI

1.5.1. Giới thiệu
Giao th c truyền thông điệp MPI là một thư viện các hàm và
macro có thể được gọi từ các chương trình sử dụng ngôn ngữ C,
Fortran, và C++. Như tên gọi c a nó MPI được xây dựng nhằm sử
dụng trong các chương trình để khai thác hệ thống các bộ xử lý bằng
cách truyền thông điệp.
1.5.1. Một số đặc điểm của lập trình MPI
1.5.2. Một số vấn đề hiệu năng
1.5.2.1. Năng lực tính tốn
1.5.2.2. Cân bằng tải
1.5.2.3. Sự bế tắc
1.6. Tìm hi u t p l nh c a th vi n MPI
1.6.1. Các lệnh quản lý môi trường MPI

Các lệnh này có nhiệm vụ thiết lập mơi trường cho các lệnh
thực thi MPI, truy vấn chỉ số c a tác vụ, các thư viện MPI, ...
- MPI Init khởi động môi trường MPI
MPI_Init (&argc, &argv)
Init ((argc, argv)
- MPI Comm size trả về tổng số tác vụ MPI đang được thực hiện
trong communicator (chẳng hạn như trong MPI_COMM_WORLD)
MPI_Comm_size (comm,&size)
Comm::Get_size()
- MPI Comm rank trả về chỉ số c a tác vụ (rank). Ban đầu mỗi tác vụ
sẽ được gán cho một số nguyên từ 0 đến (N-1) với N là tổng số tác
vụ trong communicator
MPI_COMM_WORLD.


6
MPI_Comm_rank (comm, &rank)
Comm::Get_rank()
- MPI Abort kết thúc tất cả các tiến trình MPI
MPI_Abort (comm, errorcode)
Comm::Abort(errorcode)
- MPI Get processor name trả về tên c a bộ xử lý
MPI_Get_processor_name(&name, &resultl)
Get_processor_name(&name, resultlen)
- MPI Initialized trả về giá trị 1 nếu MPI_Init() đã được gọi, 0 trong
trường hợp ngược lại
MPI_Initialized (&flag)
Initialized (&flag)
- MPI Wtime trả về thời gian chạy (tính theo giây) c a bộ xử lý
MPI_Wtime ()

Wtime ()
- MPI Wtick trả về độ phân giải thời gian (tính theo giây) c a
MPI_Wtime()
MPI_Wtick ()
Wtick ()
- MPI _ Finalize kết thúc môi trường MPI
MPI_Finalize ()
Finalize ()
1.6.2. Các kiểu dữ liệu
1.6.3. Cơ chế truyền thông điệp
1.6.4. Các lệnh truyền thông điệp blocking
Một số lệnh thông dụng cho chế độ truyền thơng điệp
blocking gồm có:
- MPI Send gửi các thông tin cơ bản


7
MPI_Send(&buf,count,datatype,dest,tag,comm)
Comm::Send(&buf,count,datatype,dest,tag)
- MPI Recv nhận các thông tin cơ bản
MPI_Recv(&buf,count,datatype,source,tag,comm,&status)
Comm::Recv(&buf,count,datatype,source,tag,status)
- MPI Ssend gửi đồng bộ thông tin, lệnh này sẽ chờ cho đến khi
thông tin đã được nhận (thông tin được gửi sẽ bị giữ lại cho đến khi
bộ đệm c a tác vụ gửi được giải phóng để có thể sử dụng lại và tác
vụ đích (destination pr ocess) bắt đầu nhận thông tin)
MPI_Ssend (&buf,count,datatype,dest,tag,comm)
Comm::Ssend(&buf,count,datatype,dest,tag)
- MPI Bsend tạo một bộ nhớ đệm (buffer ) mà dữ liệu được lưu vào
cho đến khi được gửi đi, lệnh này sẽ kết thúc khi hoàn tất việc lưu dữ

liệu vào bộ nhớ đệm.
MPI_Bsend (&buf,count,datatype,dest,tag,comm)
Comm::Bsend(&buf,count,datatype,dest,tag)
- MPI Buffer attach cấp phát dung lượng bộ nhớ đệm cho thông tin
được sử dụng bởi lệnh MPI_Bsend()
MPI_Buffer_attach (&buffer,size)
Attach_buffer(&buffer,size)
- MPI Buffer detach bỏ cấp phát dung lượng bộ nhớ đệm cho thông
tin được sử dụng bởi lệnh MPI_Bsend()
MPI_Buffer_detach (&buffer,size)
Detach_buffer(&buffer,size)
- MPI Rsend gửi thông tin theo chế độ r eady, chỉ nên sử dụng khi
người lập trình chắc chắn rằng q trình nhận thơng tin đã sẵn sàng.
MPI_Rsend (&buf,count,datatype,dest,tag,comm)
Comm::Rsend(&buf,count,datatype,dest,tag)


8
- MPI Sendrecv gửi thông tin đi và sẵn sàng cho việc nhận thông tin
từ tác vụ khác
MPI_Sendrecv (&sendbuf,sendcount,sendtype,dest,sendtag,
&recvbuf,recvcount,recvtype,source,recvtag,comm,&status)
Comm::Sendrecv(&sendbuf,sendcount,sendtype,dest,sendtag,
&recvbuf,recvcount,recvtype,source,recvtag,status)
- MPI Wait chờ cho đến khi các tác vụ gửi và nhận thơng tin đã hồn
thành
MPI_Wait (&request,&status)
Request::Wait(status)
- MPI Probe kiểm tra tính blocking c a thơng tin
MPI_Probe(source,tag,comm,&status)Comm::Probe(source,ta

g,status)
1.6.5. Các lệnh truyền thơng điệp non-blocking
Một số lệnh thông dụng cho chế độ truyền thơng điệp nonblocking gồm có:
MPI Isend gửi thơng điệp non-blocking, xác định một khu vực c a
bộ nhớ thực hiện nhiệm vụ như là một bộ đệm gửi thông tin.
MPI_Isend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Isend(&buf,count,datatype,dest,tag)
- MPI Irecv nhận thông điệp non-blocking, xác định một khu vực c a
bộ nhớ thực hiện nhiệm vụ như là một bộ đệm nhận thông tin.
MPI_Irecv (&buf,count,datatype,source,tag,comm,&request)
Request Comm::Irecv(&buf,count,datatype,source,tag)
- MPI Issend gửi thông điệp non-blocking đồng bộ (synchr onous).
MPI_Issend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Issend(&buf,count,datatype,dest,tag)
- MPI Ibsend gửi thông điệp non-blocking theo cơ chế buffer .


9
MPI_Ibsend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Ibsend(&buf,count,datatype,dest,tag)
- MPI Irsend gửi thông điệp non-blocking theo cơ chế r eady.
MPI_Irsend (&buf,count,datatype,dest,tag,comm,&request)
Request Comm::Irsend(&buf,count,datatype,dest,tag)
- MPI Test kiểm tra trạng thái kết thúc c a các lệnh gửi và nhận
thông điệp non-blocking Isend(), Irecv(). Tham số request là tên biến
yêu cầu đã được dùng trong các lệnh gửi và nhận thông điệp, tham số
flag sẽ trả về giá trị 1 nếu thao tác hoàn thành và giá trị 0 trong
trường hợp ngược lại.
MPI_Test (&request,&flag,&status)
Request::Test(status)

- MPI Iprobe kiểm tra tính non-blocking c a thông điệp
MPI_Iprobe(source,tag,comm,&flag,&status)
Comm::Iprobe(source,tag,status)
1.6.6. Các lệnh truyền thông tập thể
Một số lệnh thông dụng cho cơ chế truyền thông tập thể gồm
có:
- MPI Barrier lệnh đồng bộ hóa (rào chắn), tác vụ tại rào chắn
(bar r ier ) phải chờ cho đến khi tất cả các tác vụ khác trên cùng một
communicator đều hoàn thành.
MPI_Barrier (comm)
Intracomm::Barrier()
- MPI Bcast gửi bản sao c a bộ đệm có kích thước count từ tác vụ
root đến tất cả các tiến trình khác trong cùng một communicator.
MPI_Bcast (&buffer,count,datatype,root,comm)
Intracomm::Bcast(&buffer,count,datatype,root)
- MPI Scatter phân phát giá trị bộ đệm lên tất cả các tác vụ khác, bộ


10
đệm được chia thành sendcnt phần.
MPI_Scatter(&sendbuf,sendcnt,sendtype,&recvbuf,recvcnt,r
ecvtype,root,comm)
Intracomm::Scatter(&sendbuf,sendcnt,sendtype,&recvbuf,re
cvcnt,recvtype,root)
- MPI Gather tạo mới một giá trị bộ đệm riêng cho mình từ các mảnh
dữ liệu gộp lại.
MPI_Gather(&sendbuf,sendcnt,sendtype,&recvbuf,recvcnt,rec
vtype,root,comm)
Intracomm::Gather(&sendbuf,sendcnt,sendtype,&recvbuf,recv
cnt,recvtype,root)

- MPI Allgather tương tự như MPI_GATHER nhưng sao chép bộ
đệm mới cho tất cả các tác vụ.
MPI_Allgather(&sendbuf,sendcnt,sendtype,&recvbuf,recvcou
nt,recvtype,comm)
Intracomm::Allgather(&sendbuf,sendcnt,sendtype,&recvbuf,re
cvcnt,recvtype)
- MPI _ Reduce áp dụng các toán tử rút gọn (tham số op) cho tất cả
các tác vụ và lưu kết quả vào một tác vụ duy nhất.
MPI_Reduce
(&sendbuf,&recvbuf,count,datatype,op,root,comm)
Intracomm::Reduce(
&sendbuf,&recvbuf,count,datatype,op,root)
- Các tốn tử rút gọn gồm có: MPI_MAX (cực đại), MPI_MIN (cực
tiểu), MPI_SUM (tổng), MPI_PROD (tích), MPI_LAND (tốn tử
AND logic), MPI_BAND (toán tử AND bitwise), MPI_LOR (toán
tử OR logic), MPI_BOR (toán tử OR bitwise), MPI_LXOR (toán tử
XOR logic), MPI_BXOR (toán tử XOR bitwise), MPI_MAXLOC


11
(giá tri cực đại và vi trí), MPI_MINLOC (giá tri cực tiểu và vi trí).
- MPI Allreduce tương tự như MPI_Reduce nhưng lưu kết quả vào
tất cả các tác vụ.
MPI_Allreduce(&sendbuf,&recvbuf,count,
datatype,op,comm)
Intracomm::Allreduce(&sendbuf,&recvbuf,count, datatype,op)
- MPI Reduce scatter tương đương với việc áp dụng lệnh
MPI_Reduce rồi tới lệnh MPI_Scatter.
MPI_Reduce_scatter(&sendbuf,&recvbuf,recvcount,datatype,
op,comm)

Intracomm::Reduce_scatter(&sendbuf,&recvbuf,recvcount[],
datatype,op)
- MPI Alltoall tương đương với việc áp dụng lệnh MPI_Scatter rồi
tới lệnh MPI_Gather.
MPI_Alltoall(&sendbuf,sendcount,sendtype,&recvbuf,recvcnt,
recvtype,comm)
Intracomm::Alltoall(&sendbuf,sendcount,sendtype,&recvbuf,r
ecvcnt,recvtype)
- MPI Scan kiểm tra việc thực hiện toán tử rút gọn c a các tác vụ.
MPI_Scan(&sendbuf,&recvbuf,count,datatype,op,comm)
Intracomm::Scan(&sendbuf,&recvbuf,count, datatype,op)

1.7. K t lu n ch

ng

Để giải những bài toán đặt ra một cách hiệu quả trên những
máy tính mà chúng ta có, vấn đề chính là làm thế nào để xây dựng
được những thuật toán song song. Cách làm khá thông dụng là biến
đổi các thuật toán tuần tự về song song, hay chuyển từ một dạng


12
song song về dạng song song phù hợp hơn nhưng vẫn bảo tồn được
tính tương đương trong tính tốn.
Dựa vào bốn cơng đoạn và những ngun lý thiết kế chính:
ngun lý lập lịch, nguyên lý hình ống, nguyên lý chia để trị, nguyên
lý đồ thị phụ thuộc dữ liệu, nguyên lý điều kiện tranh đua để xây
dựng một số thuật tốn song song.
Để đánh giá được tính hiệu quả c a thuật toán song song

thường phải dựa vào độ ph c tạp thời gian c a thuật toán. Độ ph c
tạp thời gian c a thuật tốn song song khơng chỉ phụ thuộc vào kích
cỡ c a dữ liệu đầu vào mà cịn phụ thuộc vào kiến trúc máy tính song
song và số lượng các bộ xử lý được phép sử dụng trong hệ thống.
CH

NG 2. CÁC THU T TOÁN TRểN Đ

2.1. Thu t tốn Dijkstra tìm đ

TH

ng đi ngắn nh t

2.1.1. Mơ tả thuật tốn
+ Đầu vào: Đồ thị liên thông G(V,E,w), w(i,j) > 0

(i,j)

E, đỉnh nguồn a.
+ Đầu ra : Chiều dài đường đi ngắn nhất và đường đi ngắn
nhất từ đỉnh a đến các đỉnh c a đồ thị.
+ Phương pháp :
B

c 1: Gán L(a):= 0. Với mọi đỉnh x

a gán L(x) =

.


Đặt T:=V.
B

c 2: Chọn v

T, v chưa xét sao cho L(v) có giá trị nhỏ

nhất. Đặt T := T - {v}, đánh dấu đỉnh v đã xét.
B

c 3: Nếu T= , kết thúc. L(z),

z

V, z

a là chiều

dài đường đi ngắn nhất từ a đến z. Từ z lần ngược theo đỉnh được ghi


13
nhớ ta có đường đi ngắn nhất. (L(z) khơng thay đổi, nếu L(z) =
thì khơng tồn tại đường đi.
Ngược lại sang b
B

c 4.


c 4: Với mỗi x

T kề v gán L(x) := min {L(x), L(v) +

w(v,x)}. Nếu L(x) thay đổi thì ghi nhớ đỉnh v cạnh đỉnh x bằng mảng
truoc[] (với truoc[] c a đỉnh 1 = 0) để sau này xây dựng đường đi
ngắn nhất.
Quay về b

c 2.

Độ ph c tạp c a thuật toán Dijkstra: Thuật toán dùng không
quá n-1 bước lặp. Trong mỗi bước lặp, dùng không hơn 2(n-1) phép
cộng và phép so sánh để sửa đỗi nhãn c a các đỉnh. Ngoài ra, một
đỉnh thuộc Sk có nhãn nhỏ nhất nhờ khơng q n – 1 phép so sánh.
Do đó thuật tốn có độ ph c tạp O(n2).
2.1.2. Ví dụ minh họa
2.2. Thu t tốn tuần tự Prim tìm cây khung cực ti u
2.2.1. Mơ tả thuật toán
Đầu vào: Đồ thị G=(V,E) với trọng số. Các đỉnh ký hiệu là
1,2,3,…,n

Trọng số c a cạnh (i,j), (i,j)  E , ký hiệu là cij, đỉnh nguồn a,

1 bộ xử lý chính và m-1 bộ xử lý phụ.
Đầu ra: Cây ph nhỏ nhất T, Hoặc kết luận đồ thị không liên
thông.
Các bước:
(1) Khởi tạo: T là đồ thị gồm một đỉnh 1 và khơng có cạnh
(2) Kiểm tra điều kiện kết thúc:

Nếu T có n-1 cạnh, kết thúc, kết luận: T là cây ph
nhỏ nhất. Ngược lại sang bước (3)


14
(3) Thêm cạnh:

Ký hiệu M là tập M ={ (i,j)  E | i  T &j  T }

Tìm cạnh (k,h)  M sao cho :

ckh=min{cij|(i,j)  M }

Nếu ckh<∞, thêm cạnh (k,h) và đỉnh h vào T, sang bước (2).

Ngược lại t c M=  , kết thúc. Kết luận đồ thị G khơng liên thơng
2.2.2. Ví dụ minh họa

CH

NG 3. NGHIÊN C U

TOÁN SONG SONG TRểN TH

NG D NG THU T
VI N MPI

3.1. Thu t toán song song Prim tìm cây khung cực ti u:
3.1.1. Cách thực hiện thuật toán:
Đầu vào: Đồ thị G=(V,E) với trọng số. Các đỉnh ký hiệu là

1,2,3,…,n

Trọng số c a cạnh (i,j), (i,j)  E , ký hiệu là cij, đỉnh nguồn a,

1 bộ xử lý chính và m-1 bộ xử lý phụ.
Đầu ra: Cây ph nhỏ nhất T, hoặc kết luận đồ thị không liên
thông
Các b
B

c thực hi n:

c 1: Chia số đỉnh n và ma trận trọng số tương ng c a

đồ thị cho m BXL (mỗi BXL nhận n/m đỉnh). BXL 1 đặt tên P1 có
tập cạnh là E1, BXL 2 là P2 có tập cạnh là E2, …, BXL m là Pm có
tập cạnh là Em
B

c 2: Bộ xử lý P1 gửi một đỉnh ban đầu lên cho các BXL

P1,P2,…,Pm
B
đây:

c 3: Trên mỗi BXL (P1,P2,…,Pm) thực hiện các bước sau


15
Khởi tạo T= (1 đỉnh mà P1 đã phát ra ở bước 2, không cạnh)

B

c 4: Kiểm tra điều kiện kết thúc:Nếu T có n-1 cạnh thì

kết thúc, ngược lại sang bước 5
B

c 5: Thêm cạnh: Trên mỗi BXL Ký hiệu Mk là tập trên

BXL k

Mk={(i,j)  E k i  T &j  T (k=1,…,m)}

Trên mỗi BXL tìm cạnh (xk,yk)  M k (k=1,…,m)
sao cho

c( xk yk )

=min{cij|(i,j)  M k (k=1,…,m)}

Nếu tất cả các Mk trên tất cả m BXL là rổng thì kết thúc, kết
luận đồ thị không liên thông, ngược lại sang bước 6
B

c 6: BXL P1 thực hiện tìm

c( xy) nhỏ nhất trên tất cả m

BXL .
BXL P1 thêm cạnh (x,y) và đỉnh y vào T

BXL P1 chuyển số cạnh c a T và đỉnh y lên tất cả các
BXL để lặp lại b

c4

3.1.2. Ví dụ thực hiện thuật toán song song Prim
3.2. Thu t tốn song song Dijkstra tìm đ

ng đi ngắn

nh t t m t đ nh đ n t t cả các đ nh
3.2.1. Cách thực hiện thuật toán

Đầu vào: Đồ thị liên thông G(V,E,w), w(i,j) ≥ 0  (i,j)  E,

đỉnh nguồn a, 1 bộ xử lý chính và m-1 bộ xử lý phụ.
Đầu ra: Chiều dài đường đi ngắn nhất là đường đi ngắn nhất
từ đỉnh a đến tất cả các đỉnh trên đồ thị.
ụt
1),

ng: Chia đồ thị ban đầu cho m bộ xử lý (P0, P1,…,Pm-

cùng tính tốn đồng thời, mỗi bộ BXL đảm nhận n/m đỉnh c a đồ

thị (n là số đỉnh c a đồ thị, m là số BXL ) và ma trận trọng số n/m


16
cột và n dịng

+Phương pháp:
B

c 1. B x lý chính thực hi n
- Gán L(a):=0. Với mọi đỉnh x ≠ a, x thuộc bộ xử lý

chính gán L(x)= ∞.
- Chia đều số đỉnh và ma trận trọng số để gửi cho m BXL.
Cách chia đều như sau: giả sử ta có n đỉnh và m bộ xử lý
P 0,P 1,…,Pm-1.
Gọi ni là số đỉnh của bộ xử lý P i (i=0,…,m-1).
- Nếu n chia hết cho m thì
For i=0 to m-1 do

ni  n / m

- Nếu n không chia hết cho m thì
For i=0 to m-2 do

n
ni   
 m

n
nm1  n  (m  1). 
 m

- Ta xây dựng Ti (i=0,…,m-1) là tập đỉnh mà bộ xử lý Pi sẽ
nhận như sau:
BN=0; kt là số phần tử mà các bộ xử lý nhận

for (k=0; k{

T k=  ;

n
BN  k. 
 m

for (j=0; j
Tk=Tk+{j+ BN+1}

}

- Ta xây dựng Ai (i=0,…,m-1) là ma trận trọng số mà bộ xử
lý Pi sẽ nhận như sau:


17
Gọi A là ma trận trọng số c a đồ thị đầu vào thì A=(wij)nxn.

 w11 w12 ... w1n 
 w w ... w 
2n 
A   21 22
...................... 


 wn1 wn2 ... w nn 

Ai  wkj k1,n; jT

HÌNH 3.1 Ma trận trọng số c a đồ thị
Suy ra:

(i=0,…,m-1) nhận.

sẽ được bộ xử lý Pi

i

- Gửi Ti (i=1,..,m-1), Ai (i=1,..,m-1), L(x), x  Ti (i=1,..,m-1),
cho m-1 BXL phụ P1,P2,…,Pm-1.
B

c 2. m b x lý thực hi n

Trong m bộ xử lý (trừ bộ xử lý chính), gán L(xi)= ∞, sao cho
xi thuộc
Ti (i=1,…,m-1).

Trên m bộ xử lý tìm Li(xi)= min{L(xi), xi  Ti (i=0,…,m-1),

xi chưa xét}.
Các bộ xử lý phụ gửi Li(xi) về bộ xử lý chính.
B

c 3. B x lý chính thực hi n

Bộ xử lý chính tìm l(v)= min{Li(xi), i=0,..,m-1}trên m bộ xử
lý.
- Chuyển đỉnh v lên m bộ xử lý để thực hiện các bước tiếp
theo.
B

c 4. m b x lý thực hi n

- Trên m BXL kiểm tra nếu v  Ti , Ti=Ti\{v} (i=0,…,m-1),

đánh đấu đỉnh v đã xét.


18
- Kiểm tra nếu Ti (i=0,..,m-1) =  , thì bộ xử lý th i kết
thúc, sang bước 6.
- Ngược lại, sang bước 5.
B

c 5. m b x lý thực hi n

for x  Ti (i=0,…,m-1) kề với v
if L(x)> L(v)+ w(v,x)
{ L(x) := L[v] + w(v,x)
Truoc[x]=v // ghi nhớ đỉnh v vào x
}
quay lại bước 2.
B

c 6. B x lý chính thực hi n

Nếu tất cả m-1 bộ xử lý phụ kết thúc thì bộ xử lý chính thực
hiện: nhận kết quả từ các bộ xử lý phụ và kết luận chiều dài đường đi
ngắn nhất từ a đến tất cả các đỉnh và đường đi ngắn nhất qua các
đỉnh đã ghi nhớ. Đỉnh nào có nhãn khơng thay đổi (bằng ∞) thì
khơng tồn tại đường đi_(Not Path). Hệ thống kết thúc.
3.2.2. Ví dụ thực hiện thuật tốn song song Dijkstra
3.3. Thực nghi m ch

ng trình

Chương trình được thực nghiệm trên hệ thống cụm máy tính
song song (Parallel computer cluster) c a trường Đại Học Sư phạm
Hà Nội với hệ thống tồn cầu ccsl.hnue.edu.vn
Hệ thống máy tính c a Trung tâm thường dùng để chạy các
chương trình lớn, yêu cầu nhiều bộ xử lý và bộ nhớ. Sau khi truy cập
hệ thống, người sử dụng có thể viết (hoặc gửi chương trình từ máy
tính cá nhân c a mình lên), biên dịch và chạy chương trình trên hệ
thống c a Trung tâm. Có 2 loại chương trình: single-node program
(chương trình đơn, chạy trên 1 bộ xử lý) và multi-node program
(chương trình song song); và có 2 cách thực hiện chương trình trên


19
hệ thống PC cluster c a CCS: chạy trực tiếp trên nền hệ điều hành và
chạy thông qua Bộ quản lý chương trình Torque.
3.3.1. Đăng nhập hệ thống
3.3.2. Cách chạy chương trình trên hệ thống ccs1
3.3.3. Kết quả thu được
Dưới đây là kết quả bài toán Dijkstra với 02 BXL P0 và P1

với thời gian chạy là 0.002539 sescond


20

Bộ xử lý chính (P0) ghi
nhớ các đỉnh để tìm

Bộ xử lý phụ (P1) ghi
nhớ các đỉnh để tìm
đường đi

Bộ xử lý chính (P0) tìm chiều
dài từ đỉnh 1 đến các đỉnh 1, 2,
3, 4, 5, 6

Bộ xử lý phụ (P1) tìm chiều dài từ
đỉnh 1 đến các đỉnh 7, 8, 9, 10,
11, 12

Hình 3.13. Kết quả thu được chạy bài toán Dijkstra trên hệ thống


21
3.3.4. Đánh giá thuật toán
Trong thuật toán song song người ta sử dụng tốc độ (Speedup)
Để đánh giá thời gian thực hiện c a thuật toán song song so
với thuật tốn tuần tự.
Bài tốn Dijkstra
Chúng tơi tiếp tục tạo thêm đồ thị gồm 2500 đỉnh và cho

thực hiện trên 1 bộ xử lý (tuần tự), 2, 4, 6, 8 bộ xử lý thì kết quả
được cho ở bảng sau:
Bảng 3.2. Bảng đánh giá thời gian thực hiện thuật toán song song
so với thuật toán tuần tự bài toán Dijkstra 2500 đỉnh

S b x lý
T cđ
(Speedup)

2

4

6

8

1.5

1.78

1.99

2.09

Trong đó Speedup (tốc độ)= Ts/ Tp
Ts: Sequential time (Thời gian chạy tuần tự)
Tp: Parallel time (Thời gian chạy song song)

22
Bảng đánh giá trên được biểu diễn bằng đồ thị sau:

Speedup (t c đ )

Number of processors (số bộ xử lý)
2.5
1.78

2

1.99

2.09

6

8

1.5

1.5
1
0.5
0
2

4
Dijkstra

Number of processors (s b x lý)
hình 3.16. Đồ thị biểu diễn sự đánh giá thuật toán song song so với
tuần tự bài tốn Dijkstra 2500 đỉnh
Bài tốn Prim
Chúng tơi tiếp tục tạo thêm đồ thị gồm 2100 đỉnh và cho
thực hiện trên 1 bộ xử lý (tuần tự), 2, 4, 6, 8 bộ xử lý thì kết quả
được cho ở bảng sau:
Bảng 3.3. Bảng đánh thời gian thực hiện thuật toán song song so
với thuật toán tuần tự bài toán Prim 2100 đỉnh

S b x lý
T cđ
(Speedup)

2

4

6

8

1.45

1.73

1.91

2.05

23
Bảng đánh giá trên được biểu diễn bằng đồ thị sau:

Number of processors (s b x lý)
Speedup (t c đ )

2.5
2

1.73

1.91

2.05

6

8

1.45

1.5
1
0.5

0
2

4

Prim
Num er of pro essors số ộ xử lý

Hình 3.17. Đồ thị biểu diễn sự đánh giá thuật toán song song so
với tuần tự bài toán Prim 2100 đỉnh
Nh n xét: từ đồ thị và bảng kết quả trên, chúng ta nhận thấy
rằng tốc độ xử lý được tăng lên đáng kể khi xử lý trên 2 bộ xử lý thì
thời gian giảm hơn 1,6 lần so với xử lý tuần tự.
K T LU N VÀ H

NG PHÁT TRI N

K T LU N
Luận văn đã nghiên c u tổng quát về thuật toán song song và
áp dụng cho một số bài toán về đồ thị. Luận văn cũng đã khái quát
các khái niệm về thuật toán song song và các vấn đề liên quan đến
thuật tốn song song, các mơ hình song song, mơi trường lập trình
song song, lý thuyết đồ thị, cách biểu diễn đồ thị trên máy tính, các
vấn đề về đường đi, cây bao trùm trên bảng đồ.
Từ các hiểu biết trên luận văn đã nghiên c u để song song