NÂNG CAO TỐC ĐỘ SẮP XẾP DỮ
LIỆU VỚI THUẬT TOÁN PSRS
TRÊN HỆ THỐNG XỬ LÝ SONG SONG
ThS. Bùi Thanh Tuyền
Giảng viên Khoa Cảnh sát phòng, chống tội phạm sử dụng cơng nghệ cao
Học viện Cảnh sát nhân dân
Ngày tịa soạn nhận được bài báo: 06/03/2020
Ngày phản biện đánh giá:16/03/2020
Ngày bài báo được duyệt: 26/03/2020
Tóm tắt: Nhu cầu khai thác, tìm kiếm thơng tin của con người ngày càng cao thì việc
nâng cao tốc độ sắp xếp dữ liệu, phục vụ cho q trình tìm kiếm thơng tin lại càng trở
nên quan trọng hơn bao giờ hết. Có rất nhiều thuật tốn có thể giải quyết bài tốn nâng
cao tốc độ sắp xếp dữ liệu, bài báo này tập trung nghiên cứu và ứng dụng lập trình song
song cài đặt thuật toán PSRS (Parallel Sorting by Regular Sampling- Sắp xếp song song
dựa trên mẫu chuẩn). Tác giả sử dụng hệ thống IBM Linux Cluster 2350 để mơ phỏng,
thuật tốn PSRS đã cho kết quả tốc độ sắp xếp dữ liệu tốt hơn khi chạy trên hệ thống xử
lý tuần tự.
Từ Khóa: PSRS, Xử lý song song, Sắp xếp dữ liệu lớn…
1. Giới thiệu thuật toán sắp xếp song
song dựa trên các mẫu chuẩn PSRS
So với các thuật tốn sắp xếp thơng
thường, PSRS là một thuật toán sắp xếp song
song với nhiều ưu điểm. Nó giữ ngun được
kích thước của mảng, giữ được sự cân bằng
tải trong các tác vụ, tránh được việc truyền
thơng lặp lại các khóa.
PSRS là sự kết hợp của một thuật tốn
sắp xếp tuần tự, một q trình trao đổi dữ liệu
và một bước trộn song song. Mặc dù bất kỳ
một thuật toán sắp xếp và trộn tuần tự nào
đều có thể sử dụng được, nhưng PSRS sử

dụng thuật toán sắp xếp Quicksort và liên
tiếp 2 cách trộn. Thuật tốn này phù hợp với

hầu hết các mơ hình song song hiện tại đang
được sử dụng với số bộ xử lí là tùy ý. Tác giả
sẽ mơ tả, tính tốn độ phức tạp, mơ phỏng về
giải thuật PSRS tại các phần tiếp theo.[2]
2. Giải thuật PSRS
Thuật toán PSRS bao gồm có 6 pha phân
biệt. PSRS sử dụng mơ hình truyền thông
điệp để gửi, nhận, truyền thông, phân chia và
tập hợp các dữ liệu. Trên hệ thống sử dụng
p bộ xử lí và sắp xếp mảng có kích cỡ n, khi
đó, thuật tốn trải qua 6 bước thực hiện như
sau [2]:
Bước 1. Khởi tạo ban đầu
Với p bộ xử lí, lựa chọn một bộ xử lí làm
TẠP CHÍ KHOA HỌC 3
QUẢN LÝ VÀ CÔNG NGHỆ


cách lấy ra các phần tử có chỉ số 𝑝𝑝 +
h
cỡ
𝑛𝑛.
h
chọn có khoảng cách đều nhau. Cụ thể,
𝑓𝑓, 2𝑝𝑝 + 𝑓𝑓, … , (𝑝𝑝 − 1)𝑝𝑝 + 𝑓𝑓 với 𝑓𝑓 =
gốc
(bộ

xử
lí
0),
khởi
tạo
liệu
với+kích
Bước 6. Tập hợp dữ liệu cuối cùng
i chia các
phẩn
tử
ở
vị
trí
1,bộ𝑤𝑤dữ
+ 1,
2𝑤𝑤
dữ liệu, sắp xếp
𝑝𝑝
cỡ n.
⌊2⌋. Tiếp
Bộ sẽ
xử truyền
lí gốc sẽ tập hợp tất cả dữ liệu và
𝑛𝑛 theo, bộ xử lí gốc
chọn các
mẫu
chuẩn.
]
được

1, . .Bước
. , (𝑝𝑝 −
1)𝑤𝑤
+
1
với
𝑤𝑤
=
[
2
2. Phân chia dữ liệu, 𝑝𝑝sắp
xếp cục
lắp ráp các danh sách được sắp xếp trên mỗi
các phần tử chốtbộnày
𝑝𝑝 −danh
1 sách được sắp xếp gồm n
bộ và lựa chọn các mẫuthơng
chuẩn.
xử đến
lí thành
chọnban
để làm
a dữ liệu
đầu mẫu.
cho 𝑝𝑝
phần tử ban đầu. Thuật toán kết thúc.
Phân chia dữ liệu banbộđầu
p bộ
xử cho
lí cịn

lại.xử lí.
lí sẽ
cụcxếp
Mỗi
bộsắp
xử Tập
líxếp
sẽ sắp
bộ các
tập dữ
liệu với
3. Tính tốn độ phức tạp thuật toán
3.
hợp
vàcục
trộn
mẫu,
6bộ xửBước
PSRS
𝑛𝑛
4. Phân
bằng
thước
bằng
cáchBước
sử dụng
thuậtchia
toándữ liệu cục bộ tại các
kích chọn
thướcphần

lựa
tử
chốt.
h với kích
𝑝𝑝
Độ phức tạp của giải thuật được xem xét
bộ
xử
lí
dựa
trên
các
phần
tử
chốt.
tuần tự. Sau đó, mỗi bộ xử lí sẽ lựa
dưới ba yếu tố: Độ phức tạp về thời gian, độ
n thuậtQuickSort
tốnBộQuickSort
xử
lítửgốc
sẽ dữ
tập
hợp
tấtCụ
cảthể,
ra pcóphần
từcách
tập
của

mình
để
phức tạp về khơng gian sử dụng, độ độ phức
ính chọn
chọn
khoảng
đềuliệu
nhau.
ữó, mỗi
Mỗi
bộ
xử
lí
sẽ
phân
chia
làm
mẫu.
Các
mẫu
được
lựa
chọn
có
khoảng
bộ
xử
lí
sẽ
lựa

khi
truyền
thơng
phần
thành
việc dữ
tính
tốn.
Thờitử.
gianTrong
truyềnđó, độ
thành
𝑝𝑝 chọn
phân ra
lớplàm
dựa mẫu
vào 𝑝𝑝ở− 1 phầntạp
phầnphẩn
tử đãtử
được
giải các
các
ở
vị
trí
1,
𝑤𝑤
+
1,
2𝑤𝑤

+
cách đều nhau. Cụ thể, các phẩn tử ở vị trí
phức tạp về khơng gian sử dụng là tổng số
thông
yêu cầu cho các bộ
tửcủa
chốt đã chọn.
liệu cục bộ đã được sắplượng
xếp
củalànóthời
ra gian
ní tử từ
tập
dữ
liệu
khơng
gian
u
cầu chuyển qua tất các
𝑝𝑝
bộ
xử
lí.
Điều
quan
trọng
cần
để
ý
đó

𝑛𝑛
]
xử
lí
để
di
chuyển
tất
cả các
điệp Thời
1,mẫu
. . . , (𝑝𝑝
− 1)𝑤𝑤
+ 1 với
= [𝑝𝑝2 ] được
được
1,w+1,2w+1,...,(p-1)w+1
với 𝑤𝑤w=
các bộ xử lí để hồn thành
việcthơng
tính tốn.
,
mẫu.
Các
được
lựa
Bước
5.
Tập
hợp

và
trộn
các
phân
là mỗi tập hợp các phần tử mẫu tại mỗi
chọn để làm mẫu.
gian trong
truyền
thơng
thời
gian u cầu cho các
q
trình là
tính
tốn.[1]
tại các bộ xử lí.
chọn để làmlớpmẫu.
bộ xử lí để di chuyển tất cả các thơng điệp
Bước
Tập hợp
và trộn
các
bộ xử
lí đã3.được
sắp xếp.
Có 𝑝𝑝
tậpmẫu,
hợp lựa
trong q trình tính tốn.[1]
chọn phần tử chốt.Bộ xử lí thứ 𝑖𝑖 sẽ tập hợp dữ liệu


n

sắp 3.xếp
và hợp
sử dụng
thuậtcáctốn
Bước
Tập
và trộn
mẫu,
ó 6 được

Bộ xử lí gốctrong
sẽ tập
hợp
các
phân
lớptất
thứcả𝑖𝑖(1
≤ phần
𝑖𝑖 ≤ 𝑝𝑝)tử
từ các

tử
chốt.
đểchọn
trộn
chúng
lạimẫu

vớiởnhau.
𝑝𝑝2Điều
ình trộn
p bộ Từ
đã lựa
được
chọnphần
ra làm
xử lí.

bộ xử lí khác. Mỗi phân lớp này sẽ
quan trọng cần để ý đó là mỗi tập hợp các

phần tử đã sắp
xếp này,
lựa
chọn
ra
được
trộn
lại với
phần tử mẫu
mỗi
bộ
xửsẽ
lívàđã
được
sắp
xếp.
Bộ tại

xử
lí sắp
gốcxếp
tập
hợp
tấtnhau.
cả
Có
p
tập
hợp
được
sắp
xếp
và
sử
dụng
thuật
𝑝𝑝 − 1 giá trị để làm phần tử chốt bằng
Bước
6. Tập
hợp
dữnhau.
liệu mẫu
cuối
cáctrộn
phần
đã chúng
được
chọn

ra
làm
ởp2
toán
để tử
trộn
lại
với
Từ cùng
cách
ra sắp
các xếp
phần
tử lựa
có chỉ
phần lấy
tử đã
này,
chọnsốra𝑝𝑝p+
-1 giá
𝑝𝑝
bộ
xử
lí.
Điều
quan
trọng
cần
để
ý đó

Bộ
xử
lí
gốc
sẽ
tập
hợp
trị để làm phần tử chốt bằng cách lấy ra tất
cáccả dữ
đó, 𝑓𝑓,
𝑓𝑓
=
2𝑝𝑝
+
𝑓𝑓,
…
,
(𝑝𝑝
−
1)𝑝𝑝
+
𝑓𝑓
với
phần
tử cótập
chỉhợp
số và
p+f,2p+f,…,(p-1)p+f
f= sắp
liệu

lắpphần
ráp các
danh sách
được
là mỗi
các
tử mẫu
tạivới
mỗi
p
hiện
𝑝𝑝
trên mỗi bộ xử lí thành danh sách
xử lítheo,
đã xếp
được
sắp
xếp.
𝑝𝑝truyền
tập thơng
hợp
⌊ ⌋bộ
Tiếp
theo,
bộxử
xử
gốcsẽCó
sẽtruyền
.. Tiếp
bộ

lí lígốc

yền
ộ
dữ
ộ
ử lí

𝑝𝑝

c

g

bộ

2
được sắp xếp gồm n phần tử ban đầu.
xếpnày
và đến
sử dụng
tốn
cácđược
phần sắp
tử chốt
p-1 bộ thuật
xử lí cịn
lại.
thơng các phần
tử tốn

chốtkết
này
đến 𝑝𝑝 − 1
Thuật
thúc.
2
Bước
Phân
chialạidữ
cụcTừ
bộ𝑝𝑝tại
trộn
để 4.trộn
chúng
vớiliệu
nhau.
bộ
xử
lí
cịn
lại.
các bộ xử lí dựa trên các phần tử chốt.

phần tử đã sắp xếp này, lựa chọn ra
Mỗi bộ xử lí sẽ phân chia dữ liệu cục bộ
Bước
chia
cụctử
bộchốt
tại các

𝑝𝑝 −4.1Phân
giá trị
để dữ
làmliệu
phần
bằng

đã được sắp xếp của nó ra thành p phân lớp

bộ dựa vào p-1 phần
3. Tính
tốnđã
độ
phức
tạp thuật tốn
tử chốt
bộ cách
xử lí dựa
trên
các
phần
tửchọn.
chốt.
lấy
ra
các
phần
tử
có
chỉ

số 𝑝𝑝 +
PSRS
t
Bước 5. Tập hợp và trộn các phân lớp

phức
giảidữ
𝑓𝑓thuật
= được
2𝑝𝑝
+xử
𝑓𝑓,bộ…
, (𝑝𝑝 Độ
1)𝑝𝑝
+tạp𝑓𝑓 của
với
Mỗi
lí− sẽ
phân
chia
tại 𝑓𝑓,
các
bộ
lí.xử

a
xem xét dưới ba yếu tố: Độ phức tạp
xếp liệuBộ
𝑝𝑝cục
đã iđược

củatrong
nó raphân
xửbộ
lí thứ
sẽ tậpsắp
hợpxếp
dữ liệu
a
⌊thứ
⌋
. i(1≤i≤p)
Tiếp theo,
bộbộ
xửxửlíđộ
gốc
sẽMỗi
truyền
về
thời
gian,
phức
tạp
về khơng
lớp
từ
các
lí
khác.
phân
2

n.
a
lớp này sẽ được
sắpsửxếp
và trộn
nhau.
gian
dụng,
độ lại
độ với
phức
tạp khi
thông các phần tử chốt này đến 𝑝𝑝 − 1
truyền thông phần tử. Trong đó, độ
o 𝑝𝑝
bộ4xửTẠP
lí CHÍ
cịnKHOA
lại. HỌC
phức
tạp về
khơng gian sử dụng là
QUẢN
LÝ
VÀ
CƠNG
NGHỆ
cục

ằng


tổng số lượng không gian yêu cầu

Bước 4. Phân chia dữ liệu cục bộ tại các

3.1 Độ phức tạp về thời gian
Trong pha thứ 2 của giải thuật,
mỗi bộ xử lí thực hiện sắp xếp dữ liệu


dụng+thuật
có kích cỡ 𝑂𝑂 .(Sửlog
𝑝𝑝 + tốn
+ trộn
log 𝑝𝑝 )
ầu tính
trong
phađãnày
𝑝𝑝
trộn tốn
𝑝𝑝 kích
danh
sách
đượcmột
sắpdanh
xếp với
cỡ
là
𝑝𝑝
thành

sách
được
𝑝𝑝
𝑝𝑝
𝑝𝑝
𝑝𝑝
𝑛𝑛
𝑛𝑛
𝑛𝑛
𝑛𝑛
trong
trường
hợp
này
u
cầu
thời
gian
gian u cầu tính tốn trong pha này
𝑂𝑂 ( log + 𝑝𝑝 + 𝑛𝑛+ log 𝑝𝑝 )
bằngkích
QuickSort.
Kích
thước
của
dữ
trong
trường
hợpthước
này u

cầu
thờikhi
gian
2được
𝑛𝑛
cỡsắp
là 𝑝𝑝xếp
thành
một
danh
sách
𝑝𝑝có kích
𝑝𝑝
𝑝𝑝 2 mà
𝑝𝑝 𝑛𝑛sau
danh
sách
𝑛𝑛 và sau
với
kích
cỡ
là
𝑝𝑝
,
đó
𝑝𝑝= 𝑂𝑂( (log ) + log 𝑝𝑝
là:
là
𝑂𝑂(
log

𝑝𝑝)
𝑛𝑛 thời
𝑛𝑛
3.1 Độ
tạp
về
gian
𝑝𝑝 đó
𝑝𝑝
𝑛𝑛𝑝𝑝
𝑛𝑛
với
kích
cỡ
𝑝𝑝2 ,sau
và
sau
𝑛𝑛
iệu 𝑛𝑛sắp
trên xếp
mỗi
bộ phức
xử
là 1là
và
đó
là
𝑂𝑂(
log
𝑝𝑝)

chọn
ra
𝑝𝑝lí −
phần
tử
làm
chốt.
Sử
(log
)
+
log
=
𝑂𝑂(
𝑝𝑝
trộn mỗi𝑝𝑝 danh sách trên mỗi
bộ𝑝𝑝xử lí sẽ 𝑝𝑝
𝑂𝑂 ( log Trong
+ 𝑝𝑝)pha
𝑝𝑝 + 𝑝𝑝
𝑛𝑛 thứ𝑛𝑛2 của
giải thuật, mỗi bộ xử
𝑛𝑛
+1
𝑝𝑝chọn 𝑝𝑝ra 𝑂𝑂
bằng
QuickSort.
Kích
của 𝑛𝑛
dữlí song

𝑝𝑝 −
1thuật
phần
tử
làm bằng
chốt.
Sử thước
( sắp
log
+
𝑝𝑝) liệu
mà sau k
danh
sách
có
kích
thước
dụng
tốn
trộn,
q
trình
xử
lí
Tổng
thời
gian
xử
song
lí

thực
hiện
xếp
dữ
QuickSort.
chọn ra 𝑝𝑝 phần tử𝑝𝑝làm 𝑝𝑝mẫu. Do đó thời
𝑝𝑝2
.
Sử
dụng
thuật
tốn
trộn
có kích
cỡ
+
𝑝𝑝
+
1
𝑛𝑛
Tổng
𝑝𝑝 thời gian xử
dụng
thuật
tốn
trộn,
q
trình
xử
lí2lí là

𝑛𝑛 lí song song
liệu
trên
mỗi
bộ
xử
lí
và
sau
đó
Kích
thước
của
dữ
liệu
trên
mỗi
bộ
xử
là
trộn
này
thực
hiện
hết
𝑂𝑂(𝑝𝑝
log
𝑝𝑝).
sẽ
là:

g
pha
thứ
3,
bộ
xử
lí
gốc
gian u cầu tính tốn trong pha này
=
𝑂𝑂(mỗi
𝑙𝑙𝑙𝑙𝑙𝑙danh
𝑛𝑛 +sách
𝑝𝑝 + 1)
𝑝𝑝
trộn
trên mỗi bộ xử lí
2 gốc
sẽ
là:
𝑝𝑝
Trong
pha
thứ
3,
bộ
xử
lí
𝑛𝑛
trong

trường
hợp
này
u
cầu
thời
gian
trộn
này
hiện
hết
𝑂𝑂(𝑝𝑝
𝑝𝑝).Do đó
và
đóthực
chọn
ra
pvới
phần
tử làm
mẫu.
Tổng
thờixếp
gian
u cầu
là:log
hà:sách
đãsau
được
sắp

=
𝑛𝑛 + 𝑝𝑝 +𝑛𝑛1)
𝑛𝑛
𝑛𝑛 là: Do
𝑛𝑛 thời
𝑛𝑛 𝑂𝑂(𝑝𝑝 𝑙𝑙𝑙𝑙𝑙𝑙
chọn
ra
𝑝𝑝
phần
tử
làm
mẫu.
đó
có
kích
𝑛𝑛
thời
gian
u
cầu
tính
tốn
trong
pha
này
trộn
𝑝𝑝 danh
sách
đã được

sắp xếp
𝑂𝑂 (vớilog là +
𝑝𝑝 +𝑛𝑛log+𝑝𝑝)
𝑝𝑝 )𝑛𝑛 𝑛𝑛 cỡ 𝑝𝑝. Sử dụng thuật tốn trộ
Tổng
thời
giansách
u
cầu là:
𝑂𝑂(
𝑛𝑛𝑝𝑝 logDo
ta có hệ số tăng tốc
𝑝𝑝 thành
một
danh
được
𝑝𝑝
𝑝𝑝
𝑝𝑝
gian2 log
yêu𝑝𝑝cầu
𝑂𝑂 𝑝𝑝( pha
lognày+ 𝑝𝑝 + đó
+ log 𝑝𝑝 )
)) trong
+ (𝑝𝑝tính
− 1tốn
𝑂𝑂(𝑝𝑝
𝑛𝑛
𝑛𝑛

kích cỡ là𝑂𝑂𝑝𝑝(thành
một
danh sách được
𝑝𝑝 𝑛𝑛 Do
𝑝𝑝 đó
𝑝𝑝 có
Do
đó tatatrong
có
hệ𝑝𝑝trường
số
tốc
Speedup
đượcthời gi
nàytốcu cầu
2 log
+ 𝑝𝑝)
𝑛𝑛
hệ tăng
số hợp
tăng
Speedup
được
tính
bằng:
2 và sau
i kích cỡ là
𝑝𝑝
,
đó

(
)
𝑝𝑝
𝑝𝑝
𝑂𝑂(𝑝𝑝 log
là:𝑝𝑝 + 𝑝𝑝2 − 1 )
= 𝑂𝑂(tính
(log
) + log
bằng:
𝑛𝑛xử𝑝𝑝lí𝑛𝑛 song
𝑛𝑛
Tổng
song
sắp xếp với kích
cỡ làpha
𝑝𝑝 4,
, và
sau
đó
𝑝𝑝 thời
𝑝𝑝=gian
Trong
mỗi
bộ
xử
lí
phân
Speedup
được

tính
bằng:
𝑂𝑂(
(log
) +𝑝𝑝)log 𝑝𝑝
là 𝑂𝑂(
log
− 1 phần tử làm chốt. Sử
𝑝𝑝 𝑝𝑝
𝑛𝑛 log 𝑛𝑛
thứ
3,
bộ
xửxử
lílígốc
trộn
danh
𝑛𝑛 phân
𝑛𝑛 p sẽ
𝑛𝑛 pha
là:+ 𝑝𝑝 + 1 𝑆𝑆(𝑛𝑛, 𝑝𝑝) =𝑝𝑝
pha
thứ
bộ
xử
Trong
4,3,tử
mỗi
bộ
lígốc

chọnTrong
raTrong
𝑝𝑝chia
−
1pha
phần
tử
làm
chốt.
Sử
phần
được
sắp
xếp.
Thời
𝑂𝑂 ( cỡ
log p+thành
𝑝𝑝)
𝑛𝑛 𝑛𝑛 log𝑛𝑛𝑛𝑛
t tốnsách
trộn,đãq
được
sắpxử
xếplívới kích
𝑝𝑝 trình
𝑝𝑝 làbộ
𝑝𝑝 xử lí2 yêu cầu một
+ 𝑝𝑝cặp
+ 1bộ(log
+ log 𝑝𝑝 + 𝑝𝑝 + 1)

𝑛𝑛
nhớ𝑝𝑝 đệm
rộn
𝑝𝑝 một
danh
sách
được
sắp
xếpvới
với
danh
sách
được
sắp
xếp
kích
dụng
thuật
tốn
trộn,
q
trình
xử
lí cỡ là 𝑛𝑛p 𝑛𝑛𝑆𝑆(𝑛𝑛, 𝑛𝑛𝑝𝑝) = 𝑛𝑛 𝑛𝑛 𝑛𝑛𝑝𝑝𝑛𝑛 Tổng
thời gian xử líQ
songtrình
son
phần
tửđãđược
sắp

xếp.
Thời
chia
2
𝑛𝑛
𝑝𝑝
bộ xử lí u
hực hiện
hếtđó𝑂𝑂(𝑝𝑝
log
𝑝𝑝).
(log
+
log
𝑝𝑝
+
𝑝𝑝
+
1)
, và sau
chọn
ra
p-1
phần
tử
làm
chốt.
Sử
𝑂𝑂
(

log
+
𝑝𝑝
+
+
log
𝑝𝑝
)
= kích
𝑂𝑂( cỡ
𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛 +[2]
𝑝𝑝 + 1)
cầnmột
thiết
là: 𝑂𝑂
( 2).
có
𝑝𝑝 log 𝑛𝑛 hành trên hệ thố
kích
là 𝑝𝑝gian
thành
danh
sách
𝑝𝑝gốc 𝑛𝑛𝑝𝑝 𝑝𝑝sẽ 𝑝𝑝là:
𝑝𝑝
trộncỡdụng
này
thực
hiệntrộn,
hết

𝑂𝑂(𝑝𝑝
logxử𝑝𝑝).
𝑝𝑝 được
Trong
pha
thứ
3, này
bộ
𝑝𝑝 𝑝𝑝xửlàlí𝑝𝑝.
thuật
tốn
q
trình
lí
trộn
𝑛𝑛
=
𝑂𝑂(
𝑙𝑙𝑙𝑙𝑙𝑙
𝑛𝑛
+
𝑝𝑝
+
1)
=
 có kích cỡ là
gian gian
u cầu
là:
cần

thiết
là:O(𝑂𝑂p2(logp).
). Tổng thời gian u
𝑝𝑝
log
𝑛𝑛
+
𝑝𝑝
+
1
thực
hiện
hết
𝑝𝑝
log
𝑛𝑛
2
2350:
𝑛𝑛
𝑛𝑛
𝑝𝑝
ắpTổng
xếpthời
với gian
kíchu
cỡtrộn
là 𝑝𝑝𝑝𝑝
và sau
cầu
là:,danh

sáchđóđã3.3
được
sắp xếptạp
với= 𝑂𝑂(= (log
Độ
thơng
𝑛𝑛 ) +𝑛𝑛log 𝑝𝑝 𝑛𝑛 𝑛𝑛
cầu là:
Do líđó
ta𝑖𝑖 có 3.2
hệ truyền
số phức
tăng
tốc
Trong
pha
thứ
5, bộ xử
thứphức
log
𝑛𝑛
𝑝𝑝 +không
1 𝑝𝑝 +gian
2
𝑝𝑝
𝑝𝑝+
𝑂𝑂
(
log
+

+ 3.3
logĐộ
𝑝𝑝 )
Độ
tạp
về
(
)
1 ) kích
𝑝𝑝 logra𝑝𝑝 +
3.2
Độ
phức
tạp
về𝑝𝑝khơng
gian
chọn
𝑝𝑝 −𝑝𝑝1−
phần
tử
làm
chốt.
Sử
- 8 phức
node
cỡ
là
𝑝𝑝
thành
một

danh
sách
được
𝑝𝑝
𝑝𝑝
𝑝𝑝
Do
đó
ta
có
hệ
số
tăng
tốc
2
Trong
bộ
xử
lísắp
thứxếp.
𝑖𝑖 Mỗi
Trong
pha
2,
tất
cả
𝑛𝑛
phần
tử
(sách

)
Speedup
được
tính
bằng:
𝑝𝑝bằng
+thứ
𝑝𝑝 5,
−
1
)
𝑂𝑂(𝑝𝑝
trộn log
𝑝𝑝pha
danh
được
𝑛𝑛
3.2
Độ
phức
tạp
về
khơng
gian
𝑝𝑝 +
1 (0)
QuickSort. Kích thước
của Bộ
dữ+xử
lí danh

gốc
chứa
mảng
kích
2
màTrong
sau
sách
cóđược
kích
thước
𝑛𝑛gồmcó
dụng
thuật
tốn
trộn,
q
trình
xử
lícỡQuickSort.
2𝑛𝑛
Intek
2 chip
sắp
xếp
với
kích
là
𝑝𝑝
,

và
sau
đó
Speedup
được
tính
bằng:
Bộ
xử
lídữlại
gốc
(0)
chứa
được
bằng
Kích
thước
của
𝑝𝑝
g pha
4,
mỗi
bộ
xử
lí
phân
trộn 𝑝𝑝 danh
danh sách
sách này
được

sắp
xếp.
Mỗi
=
𝑂𝑂(
(log
)
+
log
𝑝𝑝
danh
sách
có
kích
thướ
cỡ
n,
mỗi
bộ
xử
lí
cịn
cần
chứa
được
mảng
được
chia
cắt.
được tạo ra bằng các𝑛𝑛sử

𝑝𝑝
𝑝𝑝
2xử
𝑛𝑛
log
𝑛𝑛
Trong
pha
4,
mỗi
bộ
lí
phân
chia
Trong
pha
4,
mỗi
bộ
xử
lí
phân
𝑛𝑛
liệu
trên
mỗi
bộ
xử
lí
là

và
sau
đó
chia
Bộ
xử𝑛𝑛cólítrộn
gốcmỗi
(0)danh
được
rộn này thực hiệnchọn
hết ra
𝑂𝑂(𝑝𝑝𝑝𝑝 −log
𝑝𝑝).
GHz,
2 bộ
GB cắt
RA
1𝑆𝑆liệu
làm
Sử
mảng
kích
𝑛𝑛,líchứa
mỗi
bộ
xử được
lícặp
cịn
𝑝𝑝 bộchốt.
sách

trên
mỗi
(phần
)sửtử
𝑛𝑛, trên
𝑝𝑝chọn
=mỗi
=
𝑂𝑂(
𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛
+𝑛𝑛
𝑝𝑝bộ
+cỡ
1)
tử được
sắp
xếp.
Thời
.và
Mỗi
xử
u
cầu
một
bộ xử lí
kích
cỡ
danh
sách
này

được
tạo
ra
bằng
các
xử
lí
là
sau
đó
log
𝑛𝑛
𝑛𝑛
𝑛𝑛
dụng
các
phần
tử
chốt
được
trong
𝑛𝑛
2+
𝑝𝑝3,
𝑝𝑝 xử
trộn
mỗi
sách trê
𝑝𝑝lí +
1 𝑛𝑛danh

(log
𝑝𝑝bộ
+
𝑝𝑝 +𝑛𝑛,
Trong
pha
lí 1)
gốc
(𝑛𝑛,𝑝𝑝𝑝𝑝)+
𝑆𝑆mảng
=log
phần
được
sắp
xếp.
Thời
chiathời
phần
tử tử
được
sắp
xếp.
Thời
gian cần
thiết
là:
có
kích
cỡ
mỗiđọc

bộ𝑛𝑛𝑝𝑝xử
cịn
DVD
ROM. Tổ
Tổng
gian
u
cầu
là:
𝑝𝑝
dụng
thuật
tốn
trộn,
q
trình
xử
lí
𝑛𝑛
𝑛𝑛
lại
cần
chứa
được
mảng
kích
cỡ
.
Mỗi
chọn

ra
𝑝𝑝
phần
tử
làm
mẫu.
Do
đó
thời
𝑝𝑝
dụng các
tử chốt
đượchợp
chọnlýtrong
Trong
. Sử1)dụng 𝑝𝑝thuật
trộ
kích
cỡp. [2]
đệm
có có
kích
cỡ 𝑝𝑝
là
𝑛𝑛phaphần
3, trong
trường
mỗi tử nhớ
𝑛𝑛 tốn
chọntưởng,

ra
𝑝𝑝trị.
phần
làm mẫu.
đólog
thời +𝑝𝑝𝑝𝑝𝑛𝑛+
𝑝𝑝 (logDo
𝑝𝑝 +
𝑛𝑛 kích cỡ . Sử dụng
giá
ết là: 𝑂𝑂 ( )..
có
2
của 8 𝑝𝑝
node là kh
𝑝𝑝đó
log
𝑛𝑛
. Mỗi
lạiDo
cần
chứa
được
mảng
taĐộ
cóphức
hệ
số kích
tăngcỡtốc
𝑛𝑛 hợp

trộn
này lý
thực
hiện
hếttrong
𝑂𝑂(𝑝𝑝
log
𝑝𝑝).
𝑝𝑝 trong
gian
u
cầu
tính
tốn
pha
này
2
pha
3,
trường
tưởng,
mỗi
3.3
tạp
truyền
thơng
𝑝𝑝 𝑛𝑛 + 𝑝𝑝
giá
trị.
𝑛𝑛

=
𝑂𝑂(
𝑙𝑙𝑙𝑙𝑙𝑙
+
1)
(
)
log
𝑝𝑝
+
𝑝𝑝
−
1
)
𝑂𝑂(𝑝𝑝
=

gian
cần
thiết
là:
𝑂𝑂
(
).
dữ
𝑝𝑝 logtrường
𝑛𝑛
gian
u
cầu

tính
tốn
trong
pha
này
trong
hợp
này
u
cầu
thời gi
mà
sau
khi
danh
sách
có
kích
thước
𝑝𝑝
𝑝𝑝
log
𝑛𝑛
+
𝑝𝑝
+
1
2u
Trong pha thứ
xửgian

lí 𝑝𝑝
thứ
i trộn
danh
Speedup
bằng:
=

Tổng
thời
cầup là:
là: 5, bộ
trong
trường
hợp
Trongđược
phaTrong
4tính
bộlog
xử
lí
gốc
truyền
2 này
nody
pha𝑛𝑛2,+tất
cả n phần tử được -chia
𝑛𝑛𝑝𝑝 + 1
gđóphaTrong
thứ được

5,pha
bộ sắp
xử
lí
thứ
𝑖𝑖
sách
xếp.
Mỗi
danh
sách
này
được
là:
Trong
4,
mỗisách
bộ xử
lí 𝑛𝑛phân
3.2 Độ
phức
vềcắt.
khơng gianlà 𝑂𝑂( log 𝑝𝑝)
ữ
𝑛𝑛
trộn
mỗi
danh
mỗi
bộ

xử
lí chốt
sẽtạp
mà
sau
khi
danh
có
kích
Do
đó
ta
có
hệ
số
tăng
tạo
rasách
bằng
các
sử
dụng
các
phần
tử
(Storage1
Trong
pha
thứ
5,thước

bộtrên
xử
lí
thứ
𝑖𝑖
thơng
𝑝𝑝
−
1
giá
trị.
𝑝𝑝
2
2
log 𝑛𝑛 gian là 𝑂𝑂(𝑝𝑝2log 𝑝𝑝) và Stot
𝑛𝑛 𝑝𝑝 +𝑛𝑛 (𝑝𝑝 −3.2
𝑝𝑝 log
Độ
phức tạp về𝑛𝑛không
)
1
)
𝑛𝑛 được
h sách
đượcchọn
sắptrong
xếp. pha
Mỗi3,𝑂𝑂(𝑝𝑝
thông
trong

hợp
trị. 𝑝𝑝 − 1 g
𝑆𝑆(lý𝑛𝑛, 𝑛𝑛𝑝𝑝) = 𝑛𝑛𝑛𝑛Trong 𝑛𝑛pha 3, bộ xử lí gốc đọc p giá
𝑛𝑛 xếp. Thời
𝑂𝑂 ( trường
log +
𝑝𝑝)
phần tử được sắp
chia
óhời
Speedup
được
tính
bằng:
𝑝𝑝 𝑝𝑝có
2
chip
Xeo
Bộ
xử
lí
gốc
(0)
chứa
được
trộn
danh
sách
được
sắp

xếp.
Mỗi
𝑛𝑛
.
Sử
dụng
thuật
tốn
trộn
kích
cỡ
𝑝𝑝
𝑝𝑝
𝑂𝑂Trong
(saulog
+
𝑝𝑝)mỗi
(log
+ log
𝑝𝑝
+lí𝑝𝑝 gửi
+
1) gian xử lí Intel
ước được
của
dữ
trộntạo
mỗi
trên
xử lí sẽ mà

này
radanh
bằng
các
sửcómỗi
𝑝𝑝sách
pha
5,
bộ
xử
khi
kích
thước
tưởng,
mỗi
danh
sách
kíchbộ
thước
Tổng
thời
song
son
𝑝𝑝
𝑝𝑝
Trong
pha
4
bộ
xử

lí
gốc
truyền
thơng
p-1
𝑝𝑝
𝑝𝑝
2
(0) chứa được Tổng thời gian
Trong pha 4, mỗi𝑝𝑝 bộ xử lí Bộ
phânxử lí gốc
𝑛𝑛
𝑛𝑛
này
Trong
3 GB RAM, 4x7
mảng
kích
𝑛𝑛,giá
mỗi
bộ xử lí mà
cịnsau khi
sách
này
được
racủa
bằng
các sửcó
𝑛𝑛 danh
Kích

dữ
𝑛𝑛(thước
trị.thước
𝑛𝑛trộn
𝑛𝑛 cỡcó
danh
sách
kích
gian
cần
thiết
là:
).tạo
i QuickSort.
𝑛𝑛 log 𝑛𝑛
hần
chốt
được
trong
trong
trường
hợp
u
cầu
thời
gian
vàtử
sau
đó
2là:số

𝑝𝑝
log
𝑛𝑛
sẽ
. 𝑝𝑝Sử
dụng
thuật
tốn
có
kích
cỡ𝑂𝑂chọn
sau
khi
trộn
mỗi
danh
sách
trên
mỗi
bộ
xử
Trong
pha
thứ
3,
bộ
xử
lí
gốc
𝑛𝑛này

𝑝𝑝
−
phần
tử,
do
đó,
tổng
phần
tử
mảng
có
kích
cỡ 𝑛𝑛,𝑛𝑛𝑆𝑆(mỗi
bộ=
xử sẽ
lí cịn
)
𝑝𝑝
𝑛𝑛,
𝑝𝑝
𝑛𝑛
trộn
mỗi
danh
sách
trên
mỗi
bộ
xử
lí

sẽ
𝑝𝑝 chia
2 pha
phần
tử
được
sắp
xếp.
Thời
𝑛𝑛
=

là:
𝑝𝑝
𝑝𝑝
Trong
thứ
3,
bộ
xử
lí
gốc
𝑛𝑛 xử lí 𝑛𝑛gửi 𝑛𝑛 −
dụng
các
phần
tửcỡ
chốt .được
chọn
trong

𝑝𝑝Sửsau
.
Mỗi
lại
cần
chứa
được
mảng
kích
cỡ
Trong
pha
5,
mỗi
bộ
phần
𝑛𝑛
lí
sẽ
có
kích
dụng
thuật
tốn
trộn
mỗi
bộ
xử
lí
là

và
đó
1
node
log
𝑛𝑛
+
𝑝𝑝
+
1
ytrên
(log
+ log
g trườnglàhợp
lýlog
tưởng,
mỗi
𝑝𝑝 bộ xử lí 𝑝𝑝
𝑛𝑛
trộn
𝑝𝑝 danh
sách đãtrộn
được
sắp
xếp
vớiđược
𝑝𝑝 𝑝𝑝 +
𝑝𝑝2𝑝𝑝 + 1)
𝑝𝑝
𝑛𝑛

mỗi
danh
sách
trên
mỗi
sẽ
𝑂𝑂(
𝑝𝑝)
𝑝𝑝
𝑛𝑛
𝑛𝑛
𝑛𝑛
𝑛𝑛
𝑛𝑛
.
Mỗi
lại
cần
chứa
mảng
kích
cỡ
. Do
đó
thời
trong
trường
này
u
cầu

thời
gian
𝑝𝑝trường
bằng
QuickSort.
thước
của
dữsố +
. líSử
dụng
tốn
trộn
cóhợp
kích
𝑛𝑛thuật
trộn
danh
sáchphức
đãKích
được
sắpkhơng
xếp
với
pha
thứ
5,hợp
bộcỡ
thứ
𝑖𝑖 𝑝𝑝cần
pha Trong

3,
trong
lýxử
tưởng,
mỗi
𝑝𝑝𝑝𝑝danh
sách
cóbao
kích
𝑂𝑂
(tổng
log
+tử𝑛𝑛(MGT)
+ 𝑛𝑛truyền
log
𝑝𝑝
) gồm
truyền
thơng
là
.đó,
trong
trường
hợp
này
u
cầu
thời
gian
là

phần
tử,−
do
phần
cần
𝑛𝑛thư
3.2
Độ
tạp
về
gian
𝑝𝑝
gian
cần
thiết
là:
𝑂𝑂
(
).
𝑛𝑛
𝑝𝑝
kích
cỡ
là
𝑝𝑝
thành
một
danh
sách
được

𝑝𝑝
𝑝𝑝
𝑝𝑝
𝑝𝑝
𝑝𝑝
log
𝑛𝑛
ra
𝑝𝑝
phần
tử
làm
mẫu.
Do
đó
thời
𝑛𝑛
𝑝𝑝 + th+
𝑝𝑝 kích cỡ . Sử dụng𝑛𝑛thuật tốn trộn 𝑂𝑂 ( logcần+truyền
có
ong
này sách
= 𝑝𝑝Core𝑝𝑝 3.2  GHz,
𝑂𝑂(
log
𝑝𝑝)
kích
cỡ
là mỗi
𝑝𝑝 thành

mộtlídanh
sách
được
𝑝𝑝
rộn pha
𝑝𝑝làdanh
được
sắp
xếp.
Mỗi
thơng
là
.
𝑝𝑝
liệu
trên
bộ
xử
là
và
sau
đó
trong
trường
hợpkích
nàycỡ
ulàsong
cầu
gian
𝑝𝑝 Tổng

thời
gian
xử
log𝑛𝑛mỗi
𝑛𝑛 + danh
𝑝𝑝 𝑛𝑛+ 1sách tr
𝑝𝑝
trộn
sắp
xếp
𝑝𝑝2 ,thời
và
sau
đó
u cầu tính
tốn trong
phavới
nàylí song
Bộ pha
xử lícuối
gốccùng,
(0) bộ
chứa
được
(log
) + log𝑛𝑛𝑝𝑝
Trong
xửbộ
lí=xử𝑂𝑂(
sắp

xếp
với
kích
cỡ
lànày
𝑝𝑝2u
,pha
vàcầu
sauthời
đó gian
danh sách này được tạo𝑛𝑛ra Trong
bằng các
sửthứ
Trong
cuối
cùng,
lí 𝑝𝑝
gốc
tập𝑝𝑝𝑛𝑛
hợp
trong
trường
hợp
pha
5,
bộ
xử
lí
thứ
𝑖𝑖

GBHDD.
=Trong
𝑂𝑂( (
sẽTổng
là: thờilàgian
3.2
Độ
phức
tạp
về
khơng
gian
gốc
xử
lí
song
song
sẽ
là:
chọn
ratửmảng
𝑝𝑝 làm
phầncó
tửkích
làm
mẫu.
thời
𝑂𝑂(
log
𝑝𝑝)

chọn
ra xử
𝑝𝑝 −
phầnsong
chốt.
Sử𝑛𝑛
dụn
có kích cỡ . Sử
𝑝𝑝
cỡ 𝑛𝑛,Do
mỗiđóbộ
xử lí cịn
Tổng thời
gian
lí 1song
𝑝𝑝
𝑛𝑛
𝑝𝑝
chọnđược
ra
𝑝𝑝
−
1
phần
tử
làm
chốt.
Sử
dụng các phần tử chốt
được

chọn sách
trong
tử.
trộn
𝑝𝑝
danh
sắp
xếp.
Mỗi
𝑛𝑛
−
phần
gốc
tập
hợp
+
𝑝𝑝
+
1
làu
𝑂𝑂(q
log
𝑝𝑝) xử
gian
tính
tốn
pha này 𝑛𝑛
Năng
lự1𝑛𝑛
)cvới sẽ là: 𝑛𝑛

trộn,
trình
lí𝑝𝑝 trong
𝑛𝑛dụng thuật
𝑛𝑛 𝑛𝑛tốn
𝑝𝑝cầu
+ 𝑝𝑝hợp
+đư
gốc- chứa
tập
Bộlícỡxử. Mỗi
lítrong
gốctrường
(0)
lại
cần
chứa
được
mảng
kích
𝑛𝑛
𝑛𝑛
hợp
này
pha 3, trong
trường
hợp
lý
tưởng,
mỗi

dụng
thuật
tốn
trộn,
q
trình
xử
𝑂𝑂
(
log
+
𝑝𝑝
+
+
log
𝑝𝑝
)
𝑝𝑝
danh
sáchthời
này gian
đượcxử
tạolírasong
bằng2song
các Do
sử đó tổng số giá trị cần
𝑂𝑂 ( log
𝑝𝑝) Tổng
:
ược

𝑛𝑛 truyềntrữthơng
𝑝𝑝 𝑝𝑝 +𝑝𝑝trộn
𝑝𝑝 thực
𝑝𝑝 là:
dùnglàchung
E
này
hiện
hết
𝑂𝑂(𝑝𝑝
log
𝑝𝑝).
𝑝𝑝
mảng
có
kích
cỡ
𝑛𝑛,
mỗi
bộ
xử
lí cị
i
𝑛𝑛
2
=
𝑂𝑂(
𝑙𝑙𝑙𝑙𝑙𝑙
𝑛𝑛
+

𝑝𝑝
+
1)
𝑛𝑛
𝑛𝑛
𝑛𝑛
𝑛𝑛
𝑛𝑛
Do
đó
tổng
số
giá
trị
cần
truyền
Tổng
thời
gian
xử
lí
song
song
trộn
này
thực
hiện
hết
𝑂𝑂(𝑝𝑝
log

𝑝𝑝).
dụng các𝑛𝑛 phần𝑛𝑛tử chốt được chọn trong
logSCSI
𝑝𝑝) 𝑙𝑙𝑙𝑙𝑙𝑙320
𝑝𝑝 là 𝑂𝑂(HDD
ộđóxử lí 𝑂𝑂gốc
( log sẽ+là:
𝑝𝑝 =
+ 𝑂𝑂(
+ (log
log 𝑝𝑝
)+ cầu
𝑝𝑝 = 𝑂𝑂(
Tổng
thời
gian
yêu
là:
Do𝑛𝑛 𝑛𝑛
đó+
)
log
𝑝𝑝
𝑛𝑛
𝑛𝑛
𝑝𝑝
c Trong pha
𝑝𝑝 thứ𝑝𝑝3, bộ xử
𝑝𝑝 𝑝𝑝lí𝑝𝑝gốc𝑝𝑝Tổngsẽthơng
.

M
lại
cần
chứa
được
mảng
kích
cỡ
TẠP CHÍ KHOA HỌC 5
:(ulog
là: gian
cầu
pha 3, trong trường thời
hợp
lýlà
tưởng,
mỗilà:
𝑝𝑝
𝑂𝑂
+
𝑝𝑝)
sắp
xếp
với
QUẢN LÝ VÀ CƠNG NGHỆ
Sử
chia
𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛
𝑝𝑝
𝑝𝑝

thơng
là : sẻt
Do đó ta cóhệTổng
hệthống
sốthời
tăng
2 + + (log 𝑝𝑝 )
ó𝑝𝑝 danh sách đã được
𝑂𝑂=( sắp
log
+
𝑝𝑝
log
𝑝𝑝
+
𝑝𝑝
−
1
)
𝑂𝑂(𝑝𝑝
𝑂𝑂(𝑝𝑝 xếp
+
+(log
1 với) + log 𝑝𝑝 𝑛𝑛 2 𝑛𝑛
Do đó ta gian
có
𝑛𝑛
𝑛𝑛
𝑝𝑝
ửh lísách được

v2.3.0.5.
𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑝𝑝
)
2log 𝑝𝑝 + (𝑝𝑝𝑛𝑛− 1𝑛𝑛
)
𝑂𝑂(𝑝𝑝
Speedup
được
tính
bằng:
𝑛𝑛
+
𝑝𝑝
+
𝑝𝑝
−
1
+
𝑛𝑛
−
+
𝑛𝑛
−
𝑂𝑂 ( log + 𝑝𝑝 + + log 𝑝𝑝 )
ử
sẽ là:


Do đó tổng số giá trị cần truyền
thơng là :


HDD SCSI 320 MBps 15KRpm, dùng
hệ thống chia sẻ file: GPFS cho Linux

𝑛𝑛 + 𝑝𝑝2 + 𝑝𝑝 − 1 + 𝑛𝑛 −

𝑛𝑛
𝑛𝑛
+ 𝑛𝑛 −
𝑝𝑝
𝑝𝑝

1
= 2𝑛𝑛 (1 − ) + 𝑝𝑝2 + 𝑝𝑝
𝑝𝑝
−1

4. Mơ phỏng thuật tốn

4. Mơ phỏng thuật tốn

4.1 Mơi trường mơ phỏng:

4.1 Mơi trường mơ phỏng:

Q trình mơ phỏng được tiến hành trên
hệ thống IBM Linux Cluster 2350:

lập trình song song MPI. Mơ phỏng


- 8 node tính tốn, mỗi node gồm 2 chip
mục đích
tra sự
songRAM,
song
Intel nhằm
Xeon Dual
Core kiểm
3.2 GHz,
2 GB
1x36 GB HDD, DVD ROM. Tổng năng lực tính
hóa của thuật tốn PSRS.
tốn của 8 node là khoảng 51.2 Gflops.

Phương
mơtrữ
phỏng
- 4.2
2 node
phụcpháp
vụ lưu
(Storage1 và
Storage2), mỗi node gồm 2 chip Intel Xeon
tắc RAM,
lấy số4x72
liệu GB
mô
Dual Core Về
3.2 nguyên
GHz, 3 GB

HDD.phỏng:
- 1 node đóng vai trị quản lí (MGT) bao
- Cố
định
sốCore
phần3.2
tửGHz,
của 3mảng
gồm chip Intel
Xeon
Dual
GB
RAM, 2x36 GBHDD.

thay đổi số bộ xử lí sử dụng (2, 4, 8)

- Năng lực lưu trữ: thiết bị lưu trữ dùng

chạy từ 5 đến 10 lần để đo thời gian và

chung EXP400 với 10x73 GB HDD SCSI 320
v2.3.0.5.
MBps 15KRpm, dùng hệ thống chia sẻ file:
GPFS cho Linux v2.3.0.5.

- Các node chạy HĐH Redhat

- Các node chạy HĐH Redhat Enterprise
Enterprise
3.0nối

vàvới
được
nốiqua
Linux
3.0 vàLinux
được kết
nhaukết
thơng
mạng
Gethernet.
với nhau
thơng qua mạng Gethernet.
- Các thuật tốn được lập trình bằng ngơn
- Các
thuậtthưtốn
lậpsong
trìnhsong
ngữ C++
sử dụng
việnđược
lập trình
MPI. Mơ phỏng nhằm mục đích kiểm tra sự
bằng ngơn ngữ C++ sử dụng thư viện
song song hóa của thuật tốn PSRS.
4.2 Phương pháp mô phỏng


- Thay đổi số phần tử của mảng

Về nguyên tắc lấy số liệu mô phỏng:


5
6
, 10
, 10số7) phần
và chạy
trênmảng
cùng thay
số bộđổi
(10
- Cố
định
tử của

sốxử
bộ lí,
xửchạy
lí sử dụng
(2, 4,10
8) lần
chạyđểtừđo
5 đến
từ 5 đến
thời10
lần để đo thời gian và lấy giá trị trung bình các
lầngian
chạy.và lấy giá trị trung bình các lần
- Thay đổi số phần tử của mảng (105, 106,
chạy.


107) và chạy trên cùng số bộ xử lí, chạy từ 5
4.310Kết
mơ
phỏng
đến
lần quả
để đo
thời
gian và lấy giá trị trung
bình các lần chạy.

4.3.1 Kết quả mơ phỏng khi chạy
4.3 thuật
Kết quả
mơPSRS
phỏng
trên
tốn

4.3.1 Kết quả mơ phỏng khi chạy trên
thuật tốn PSRS

lấy giá trị trung bình các lần chạy.
Input
Size

T.sequency
(seconds)

105


Thời gian chạy trung bình của thuật tốn
PSRS(giây)
P=2

P=3

P=4

P=8

0.0372

0.0285

0.0199

0.0183

0.0514

106

0.4186

0.3343

0.2188

0.1947


0.2146

107

4.6197

3.1352

2.5169

2.1608

2.1887

P: số bộ xử lí sử dụng, T.sequency: thời gian tuần tự (giây)
Input Size (kích thước dữ liệu đầu vào)
chạy chương trình trong trường hợp xử
Qua mơ phỏng, trước hết nhận

lí song song, với cả bốn trường hợp khi

QUẢN
LÝ VÀ
CƠNG
NGHỆPSRS hồn tồn
thấy
rằng
thuật
tốn


cố định số phần tử của mảng và thay

có thể song song hóa được và khi chạy

đổi số bộ xử lí sử dụng (2, 3, 4, 8 bộ

6 TẠP CHÍ KHOA HỌC


Qua mơ phỏng, trước hết nhận thấy rằng
thuật tốn PSRS hồn tồn có thể song song
hóa được và khi chạy chương trình có thể sử
dụng số bộ xử lí bất kì, khơng cần điều kiện
ràng buộc về số bộ xử lí sử dụng.
Về kết quả mơ phỏng, nhìn vào bảng kết
quả nhận thấy rằng, thời gian chạy chương
trình trong trường hợp xử lí song song, với cả
bốn trường hợp khi cố định số phần tử của
mảng và thay đổi số bộ xử lí sử dụng (2, 3, 4,
8 bộ xử lí) kết quả đều cho thời gian chạy tốt
hơn so với thời gian chạy tuần tự (sử dụng
trên 1 bộ xử lí).
Cụ thể, trong trường hợp sử dụng 2 bộ
xử lí so với thời gian chạy tuần tự, với số phần
tử n=100000 thì thời gian chạy song song
nhanh gấp 1.5 lần, với số phần tử n=1000000
thì thời gian chạy song song nhanh gấp 1.36
lần, với n=10000000 thì thời gian chạy song
song nhanh gấp 1.48 lần. Trong trường hợp

sử dụng 4 bộ xử lí so với thời gian chạy tuần
tự, với số phần tử n=100000 thì thời gian
chạy song
gấp đồ
3 lần,
với số
Dướisong
đây nhanh
là các biểu
thể hiện

phần tử n=1000000 thì thời gian chạy song
song nhanh gấp 2.15 lần, với n=10000000
thì thời gian chạy song song nhanh gấp 2.16
lần. Trường hợp cuối cùng, sử dụng 4 bộ xử
lí so với thời gian chạy tuần tự, với số phần
tử n=1000000 thì thời gian chạy song song
nhanh gấp 1.95 lần, với n=10000000 thì thời
gian chạy song song nhanh gấp 2.11 lần.
Rõ ràng, khi chạy trên đa bộ xử lí, thuật
tốn PSRS cho kết quả hiệu quả hơn nhiều
lần so với chạy tuần tự. Số bộ xử lí cho kết quả
tốt nhất là 4 bộ xử lí. Qua kết quả mơ phỏng,
phần nào giúp ta nhận thấy rằng, khơng phải
cứ tăng số bộ xử lí của hệ thống lên thì thuật
tốn sẽ đạt được hiệu quả tốt về thời gian.
Đến một lúc nào đó, khi tăng số bộ xử lí của
hệ thống lên nhưng độ hiệu quả khơng thể
tăng lên được nữa. Do đó ln ln cần xác
định số bộ xử lí tốt nhất mà hệ thống nên sử

dụng trong quá trình chạy chương trình.
Dưới đây là các biểu đồ thể hiện kết quả
chạy thuật toán PSRS trên hệ thống song
song:

Biểu đồ 2. Biểu đồ so sánh thời gian
Biều đồ 1. Biểu đồ so sánh thời gian chạy thuật toán PSRS

kết quả chạy thuật toán PSRS trên hệ

Biểu đồ so sánh thời gian chạy thuật toán PSRS
5
4.5
4

Thời gian(giây)

3.5
3

N=1
N=2

2.5

N=4
N=8

2
1.5

1
0.5
0
100

1000

10000

Số phần tử (nghìn)

thống song song:

chạy của các BXL với cùng số phần tử N=106

5. Kết luận

TẠP CHÍ KHOA HỌC 7
QUẢN LÝ VÀ CÔNG NGHỆ

Biều đồ 1. Biểu đồ so sánh thời gian
chạy thuật tốn PSRS

Qua kết quả mơ phỏng cũng như


Biều đồ 1. Biểu đồ so sánh thời gian
chạy thuật tốn PSRS

Qua kết quả mơ phỏng cũng như

căn cứ vào độ phức tạp tính tốn của

Biểu đồ 2. Biểu đồ so sánh thời gian chạy của
các BXL
cùng số
N=106 định
thuật
tốnvớiPSRS,
cóphần
thể tửkhẳng
Biểu đồ so sánh thời gian chạy của các bộ xử lý với cùng số phần tử
N=1000000
0.45

Thời gian (giây)

0.4

0.4186

0.35

0.3343

0.3

0.2755

0.25
0.2


0.1947

0.2146

0.15
0.1
0.05
0
N=1

N=2

N=4

N=8

N=16

Số bộ xử lý

5. Kết luận
Qua kết quả mô phỏng cũng như căn
cứ vào độ phức tạp tính tốn của thuật tốn
PSRS, có thể khẳng định rằng, PSRS là một
trong những thuật toán sắp xếp dữ liệu trên
hệ thống song song đạt hiệu quả cao vượt
trội so với hệ thống xử lý tuần tự. Thuật tốn
này có thể được áp dụng rộng rãi trong các
ứng dụng xử lý song song, là bước tiền đề để

nâng cao hiệu quả tìm kiếm dữ liệu trên các
hệ thống dữ liệu lớn (Bigdata) trong giai đoạn
hiện nay. Trong thời gian tiếp theo tác giả sẽ
cải tiến thuật tốn PSRS để cho kết quả tốt
hơn.

8 TẠP CHÍ KHOA HỌC

QUẢN LÝ VÀ CÔNG NGHỆ

TÀI LIỆU THAM KHẢO
1. Grama A., A. Gupta, G. Karypis, V.
Kumar (2003), “Introduction to Parallel
Computing”, Addison Wesley.
2. Xiaobo Li, Paul Lu, Jonathan Schaeffer,
John Shillington, Pok Sze Wong (2004), “On
the Versatility of parallel sorting by Regular
Sampling”, University of Alberta, EdmonTon,
Alberta, Canada.