Xem mẫu
- 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 quá 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 toán có thể giải quyết bài toá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 toá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 hầu hết các mô hình song song hiện tại đang
song dựa trên các mẫu chuẩn PSRS được sử dụng với số bộ xử lí là tùy ý. Tác giả
sẽ mô tả, tính toán độ phức tạp, mô phỏng về
So với các thuật toán sắp xếp thông giải thuật PSRS tại các phần tiếp theo.[2]
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ữ nguyên được 2. Giải thuật PSRS
kích thước của mảng, giữ được sự cân bằng Thuật toán PSRS bao gồm có 6 pha phân
tải trong các tác vụ, tránh được việc truyền biệt. PSRS sử dụng mô hình truyền thông
thông lặp lại các khóa. điệp để gửi, nhận, truyền thông, phân chia và
PSRS là sự kết hợp của một thuật toán tập hợp các dữ liệu. Trên hệ thống sử dụng
sắp xếp tuần tự, một quá trình trao đổi dữ liệu p bộ xử lí và sắp xếp mảng có kích cỡ n, khi
và một bước trộn song song. Mặc dù bất kỳ đó, thuật toán trải qua 6 bước thực hiện như
một thuật toán sắp xếp và trộn tuần tự nào sau [2]:
đều có thể sử dụng được, nhưng PSRS sử Bước 1. Khởi tạo ban đầu
dụng thuật toán sắp xếp Quicksort và liên
tiếp 2 cách trộn. Thuật toán này phù hợp với 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
h cỡ 𝑛𝑛.
chọn có khoảng cách đều nhau. Cụ thể,
𝑓𝑓, 2𝑝𝑝 + 𝑓𝑓, … , (𝑝𝑝 − 1)𝑝𝑝 + 𝑓𝑓 với 𝑓𝑓 =
i chia các
gốc (bộ
phẩn xử
dữ liệu, sắp xếp lí
tử 0),
ở khởi
vị tạo
trí 1,bộ𝑤𝑤dữ liệu
+ 1, 2𝑤𝑤 với+kích Bước 6. Tập hợp dữ liệu cuối cùng
cỡ n. 𝑝𝑝
⌊2⌋. Tiếp 𝑛𝑛 theo, bộ xử lí gốc Bộ sẽxử truyền
lí gốc sẽ tập hợp tất cả dữ liệu và
chọn các mẫu
1, . .Bước
. , (𝑝𝑝 − chuẩn.
1)𝑤𝑤 + 1 với 𝑤𝑤 = [ ] được
2. Phân chia dữ liệu, 𝑝𝑝sắp 2 xếp cục lắp ráp các danh sách được sắp xếp trên mỗi
bộ và lựa chọn các mẫuthông chuẩn. các phần tử chốtbộnày xử đến 𝑝𝑝 −danh
lí thành 1 sách được sắp xếp gồm n
chọnban
a dữ liệu để làmđầ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 xử cho
lí cònp bộ lại.xử lí.
6bộ xửBước lí sẽ
Mỗi bộsắp xử Tập
3. líxếp cụcxếp
sẽ sắp
hợp vàcục trộn bộ các
tập dữ mẫu,liệu với 3. Tính toán độ phức tạp thuật toán
PSRS
cáchBước 4. Phânthuậtchia toándữ liệu cục bộ tại các
𝑛𝑛
h với kích
lựa thước
kích chọn
thướcphần
𝑝𝑝
bằng
tử
bằng chốt. sử dụng
Độ 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.
n thuậtQuickSort
toánBộQuickSorttuầ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, độ
ính chọn chọnra pcóphần xử lítửgốc
khoảng từcáchsẽ dữ
tập tập hợp
đềuliệu của
nhau. tấtCụ cảthể,
mình để phức tạp về không gian sử dụng, độ độ phức
ữó, mỗi làm bộmẫu. xử lí
Các sẽ lựa
mẫu
thành được lựa
phân ra
𝑝𝑝 chọn Mỗi
chọn
lớplàm có
dựa mẫu bộ xử
khoảng lí
vào 𝑝𝑝ở− 1 phầntạpsẽ phân
khi
thành chia
việc dữ
truyền thông
tính phần
toán. Thờitử.
gianTrong
truyềnđó, độ
giải các phầnphẩn
các tử đãtử được
ở vị trí
cách đều nhau. Cụ thể, các phẩn tử ở vị trí 1, 𝑤𝑤 + 1, 2𝑤𝑤 + phức tạp về không gian sử dụng là tổng số
ní tử từ𝑝𝑝 tập
bộ xử dữ lí. liệu
Điều
tửcủa
quan
liệu cục bộ đã được sắplượng
chốt đã chọn.
trọng cần để ý đó
xếp củalànóthời
thông
không ra gian
gian yêu
yêu cầu cho các bộ
cầu chuyển qua tất các
] 1,mẫu
. . . , (𝑝𝑝
1,w+1,2w+1,...,(p-1)w+1− 1)𝑤𝑤 + 1 với với 𝑤𝑤w=
𝑛𝑛
= [𝑝𝑝2 ] được được xử lí để di chuyển
các bộ xử lí để hoàn thành tất cả các
việcthông điệp Thời
tính toá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
quá trình là thời
tính gian yêu cầu cho các
toán.[1]
n chọn để làmlớpmẫu.
tại các bộ xử lí. bộ xử lí để di chuyển tất cả các thông điệp
bộ xử lí đã3.được
Bước sắp xếp.
Tập hợp Có 𝑝𝑝
và trộn cáctậpmẫu,
hợp lựa trong quá trình tính toán.[1]
chọn phần tử chốt.Bộ xử lí thứ 𝑖𝑖 sẽ tập hợp dữ liệu
ó 6 được sắp 3.xếp
Bước và hợp
Tập sử dụng thuậtcáctoán
và trộn mẫu,
Bộ xử lí gốctrong
sẽ tập hợp
phân lớptất
thứcả𝑖𝑖(1
các
≤ phần
𝑖𝑖 ≤ 𝑝𝑝)tử
từ các
đã lựa
ình trộn đểchọn
được chọnphần
trộn chúng tử
ra làm chốt.
lạimẫu
vớiởnhau.
p bộ Từ 𝑝𝑝2Điều
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
yền phần tử đã sắp đượcxếp này, lựa chọn ra
ộ phần tử mẫu Bộ tại xử lí sắp
mỗi gốcxếp
bộ xửsẽ lívàđãtrộn
tập đượclại với
hợp tấtnhau.
sắp xếp.
cả
dữ Có p tập hợp được sắp xếp
𝑝𝑝 − 1 giá trị để làm phần tử chốt bằng và sử dụng thuật
ộ toán cáctrộnphần
để tử đã chúng
Bước
trộn được
6. Tập chọnhợp
lại vớira làm
liệu mẫu
dữnhau. cuối ởp2
Từ cùng
ử lí cách
phần lấy tử đãra sắp
các xếpphần tử lựa
này, có chỉchọnsốra𝑝𝑝p+ -1 giá
𝑝𝑝 bộ xử lí. Điều quan trọng
trị để làm phần tử chốt bằng cách lấy ra tất
Bộ xử lí gốc cần
sẽ tậpđểhợpý đó
cáccả dữ
đó, 𝑓𝑓,
phần 2𝑝𝑝 + 𝑓𝑓, …
tử cótập , (𝑝𝑝
chỉhợp −
số và 1)𝑝𝑝 + 𝑓𝑓 với 𝑓𝑓 =
là mỗi liệu p+f,2p+f,…,(p-1)p+f
các lắpphần
ráp các tử mẫu
danh sáchtạivới
mỗi f= sắp
được
p
hiện 𝑝𝑝
⌊ ⌋bộ .. Tiếp
Tiếp đã xếp
xử lítheo,
theo, đượctrên mỗi bộ xử lí thành danh sách
bộxử
bộ sắp
xử xếp.
lí lígốcgốcsẽCó tập thông
𝑝𝑝truyền
sẽtruyền hợp
2 được sắp xếp gồm n phần tử ban đầu.
cácđược
phần sắp xếpnày
tử chốt và đến
sử dụng
p-1 bộ thuật toán
xử lí còn lại.
thông các phần tử toán
Thuật chốtkếtnày đến 𝑝𝑝 − 1
thúc.
𝑝𝑝 trộn
Bước để 4.trộn
Phânchúng
chialạidữ
vớiliệu
nhau.
cụcTừ 2
bộ𝑝𝑝tại
bộ xử lí còn lại.
các bộ xử lí dựa trên các phần tử chốt.
c phần tử đã sắp xếp này, lựa chọn ra
bộ Mỗi bộ xử lí sẽ phân chia dữ liệu cục bộ
g Bước
𝑝𝑝 −4.1Phân chia
giá trị để dữ
làmliệu cụctử
phần bộchốt
tại các
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 toánđã
độ phức tạp thuật toán
bộ cách
xử lí dựa
lấy trên
ra các
các phần
tử chốt
phần tửchọn.
tử chốt.
có chỉ số 𝑝𝑝 +
t PSRS
Bước 5. Tập hợp và trộn các phân lớp
a tại 𝑓𝑓,
các Mỗi
2𝑝𝑝
bộ 𝑓𝑓,bộ…
+xử , (𝑝𝑝 Độ
lí.xử phức
lí− sẽ
1)𝑝𝑝 +tạp𝑓𝑓 của
phân với giảidữ
chia 𝑓𝑓thuật
= được
xếp liệuBộ𝑝𝑝cục xửbộ
xem xét dưới ba yếu tố: Độ phức tạp
đã iđược
sẽ tậpsắp
hợpxếp củatrong
nó raphân
a ⌊thứ⌋ lí thứ
. i(1≤i≤p)
Tiếp theo, bộbộ
dữ liệu
xửxửlíđộ gốc sẽMỗi
truyền
lớp vềtừ thời
các gian, lí phức
khác. tạp về không
phân
n. 2
a lớp này sẽ được giansắpsửxếp và trộn
dụng, độ lại
độ với
phứcnhau.
tạp khi
thông các phần tử chốt này đến 𝑝𝑝 − 1
o 𝑝𝑝 truyền thông phần tử. Trong đó, độ
3.1 Độ phức tạp về thời gian
bộ4xửTẠP lí CHÍ
cònKHOA
lại. HỌC
cục QUẢN phức
LÝ VÀ tạp về
CÔNG NGHỆkhông gian sử dụng là
Trong pha thứ 2 của giải thuật,
tổng số lượng không gian yêu cầu
ằng Bước 4. Phân chia dữ liệu cục bộ tại các mỗi bộ xử lí thực hiện sắp xếp dữ liệu
- ầu tính có kích cỡ 𝑂𝑂 .(Sửlog dụng+thuật 𝑝𝑝 + toán + trộn
trộn toán danh
𝑝𝑝 kích trong
cỡ sách là
phađãnày
𝑝𝑝 thànhđượcmột sắpdanh xếp với sách được 𝑛𝑛 𝑝𝑝
𝑛𝑛 𝑝𝑝 𝑝𝑝 𝑛𝑛 𝑛𝑛 𝑝𝑝 𝑝𝑝
log 𝑝𝑝 )
gian yêu cầu tính toán trong pha này trong trường hợp này yêu cầu thời gian
bằngkích QuickSort. Kích thước của dữ 𝑂𝑂 ( log + 𝑝𝑝 + 𝑛𝑛+ log 𝑝𝑝 )
cỡsắp là 𝑝𝑝xếp thành với mộtkích danh cỡ sách
là 𝑝𝑝 2được
,𝑛𝑛 và sau danh trong đó sách trường
𝑝𝑝có kích hợpthước
𝑝𝑝 này yêu 𝑝𝑝 2 mà cầu
𝑝𝑝 𝑛𝑛sau thờikhi gian
𝑛𝑛
là: 𝑛𝑛 thời là 𝑂𝑂( log 𝑝𝑝) 𝑝𝑝= 𝑂𝑂( (log ) + log 𝑝𝑝
iệu 𝑛𝑛sắp
trên xếp 3.1 Độ
mỗi bộ phức
với kích
xử tạp
cỡlà 1là về 𝑝𝑝2 ,sau gian
và sau 𝑝𝑝 đó 𝑛𝑛 𝑛𝑛 𝑛𝑛𝑝𝑝 𝑝𝑝
𝑛𝑛 chọn ra 𝑝𝑝lí − phầnvà tử đó
làm chốt. là Sử𝑂𝑂( log
trộn mỗi𝑝𝑝 danh sách trên mỗi
𝑝𝑝) = 𝑂𝑂( (log bộ𝑝𝑝xử lí sẽ 𝑝𝑝
) + log
𝑂𝑂 ( log Trong + 𝑝𝑝)pha 𝑛𝑛 thứ𝑛𝑛2 của 𝑝𝑝
giải thuật, mỗi bộ xử 𝑝𝑝 + 𝑝𝑝
𝑝𝑝chọn 𝑝𝑝ra 𝑂𝑂 𝑝𝑝 − bằng
1thuậtphần QuickSort.
tử làm bằng chốt. Kích Sử thước của 𝑛𝑛 dữlí song +1 𝑛𝑛
lí thực dụnghiện ( sắp log xếp +
toán 𝑝𝑝) liệu
dữ trộn, quá trình
Tổng
QuickSort. xử
thời lí gian xử danh song sách có kích thước mà sau k
chọn ra 𝑝𝑝 phần tử𝑝𝑝làm 𝑝𝑝mẫu. Do đó thời có kích cỡ . Sử dụng
+ 𝑝𝑝 +thuật1 toán trộn 𝑝𝑝2
dụng thuật toán trộn, quá trình xử lí2lí là 𝑛𝑛 Tổng 𝑝𝑝 thời gian xử 𝑛𝑛 lí song song
g pha thứ
Kích trộn
3,
thước bộ
gian yêu cầu tính toán trong pha này này
củaxử liệu thực
dữlí trên
gốc
liệu hiện
trênmỗi mỗi bộ
hết
sẽ là:
bộ xử
𝑂𝑂(𝑝𝑝
xử lí log
là 𝑝𝑝). và sau đó
𝑝𝑝 = trộn 𝑂𝑂(mỗi 𝑙𝑙𝑙𝑙𝑙𝑙danh𝑛𝑛 +sách 𝑝𝑝 + 1) trên mỗi bộ xử lí
trộn Trong
này pha thứ 3, bộ xử lí
2 gốc trongsẽ là: trường hợp này
𝑛𝑛 yêu 𝑝𝑝cầu thời gian
hà:sách và đãsau Tổng
được đóthực thờixếp
chọn
sắp hiệngian
ra pvới hết
yêu cầu
phần 𝑂𝑂(𝑝𝑝
tử làm là:log mẫu. 𝑝𝑝).Do đó
=
chọn ra 𝑝𝑝 phần tử làm
𝑛𝑛 mẫu.
𝑛𝑛 là: Do đó
𝑛𝑛 thời 𝑛𝑛 𝑂𝑂(𝑝𝑝 𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛 + 𝑝𝑝 +𝑛𝑛1)
trộnTổng
thời
𝑝𝑝 danh gian
thời
yêu
sách
giansách
cầu
đã được
yêu
tính
cầu là:
toán sắp xếptrong pha
𝑂𝑂 (vớilog là + này
𝑂𝑂(
𝑛𝑛
𝑝𝑝 +𝑛𝑛log+𝑝𝑝) 𝑛𝑛𝑝𝑝 logDo 𝑝𝑝 )𝑛𝑛 𝑛𝑛 cỡ 𝑝𝑝. Sử dụng thuật toán trộ
có kích
𝑝𝑝 thành một danh
𝑛𝑛 gian2 log
𝑂𝑂(𝑝𝑝
𝑛𝑛
được yêu𝑝𝑝cầu + (𝑝𝑝tính
𝑝𝑝
− 1toán )) trong
𝑝𝑝 𝑂𝑂 𝑝𝑝( pha lognày+ 𝑝𝑝 + đó
𝑝𝑝 ta có hệ số tăng tốc
+ log 𝑝𝑝 )
kích cỡ là𝑂𝑂𝑝𝑝(thành 2 log một + 𝑝𝑝) danh sách được 𝑝𝑝 𝑛𝑛 Do 𝑝𝑝 đó
Do đó tatatrong
𝑛𝑛 𝑝𝑝 có
có hệ𝑝𝑝trường
số
hệ tăng số hợp tốc
tăng nàytốcyêu cầu
Speedup đượcthời gi
i kích cỡ là 𝑝𝑝𝑝𝑝
𝑂𝑂(𝑝𝑝 log,2 và sau
𝑝𝑝 đó
là:𝑝𝑝 + 𝑝𝑝2 − 1 )( ) Speedup được tính bằng:
= 𝑂𝑂(tính (logbằng: ) + log 𝑛𝑛xử𝑝𝑝lí𝑛𝑛 song 𝑛𝑛
sắp xếp với kích Trong cỡ làpha 𝑝𝑝 4, , và mỗi sau bộ đó
xử lí phân Tổng
Speedup 𝑝𝑝 thời được 𝑝𝑝=gian tính bằng: song
− 1 phần tử làm chốt. Sử 𝑂𝑂( là 𝑂𝑂( (log log ) +𝑝𝑝)log 𝑝𝑝
là:+ 𝑝𝑝 + 1 𝑆𝑆(𝑛𝑛, 𝑝𝑝) =𝑝𝑝
𝑝𝑝 𝑝𝑝 𝑛𝑛 log 𝑛𝑛
chọnTrong raTrong
Trong
𝑝𝑝chia
−pha 1pha thứ
𝑛𝑛 pha
phần
phần
thứ 4,3,tử 3,
mỗi
tử bộbộlàm
được
xửxử
xử
bộ lílígốc
chốt.
sắp
𝑂𝑂 ( cỡ
𝑛𝑛 phân
lígốc
xếp.
trộn
Sử 𝑛𝑛 p sẽ
log p+thànhThời
danh
𝑝𝑝)
t toánsách trộn,đãquá được𝑝𝑝 trình sắpxử xếplívới kích
𝑝𝑝 làbộ 𝑝𝑝 xử lí2 yêu cầu một + 𝑝𝑝cặp
𝑛𝑛 𝑛𝑛 log𝑛𝑛𝑛𝑛
+ 1bộ(log nhớ𝑝𝑝 đệm + log 𝑝𝑝 + 𝑝𝑝 + 1)
thời gian xử líQuá songtrình
𝑛𝑛
rộndụngchia danh
𝑝𝑝 một thuật
phần
danh sách tửđãđược
toán
sách đượcđược
trộn, sắpquá
sắpsắp xếp. xếpvới
trình
xếp Thờivới
xử kích lí cỡ là 𝑛𝑛p 𝑛𝑛𝑆𝑆(𝑛𝑛, 𝑛𝑛𝑝𝑝) = 𝑛𝑛 𝑛𝑛 𝑛𝑛𝑝𝑝𝑛𝑛 Tổng son
hực hiện 𝑝𝑝
, và sau hếtđó𝑂𝑂(𝑝𝑝 chọn
2
logra 𝑝𝑝).
p-1 phần 𝑛𝑛 tử làm chốt. 𝑂𝑂Sử ( log + 𝑝𝑝 + (log + +log log 𝑝𝑝 𝑝𝑝
) + 𝑝𝑝 + 1) bộ xử lí yêu
là 𝑝𝑝gian cầnmột thiết là: 𝑂𝑂 ( 2). có = kích 𝑂𝑂( cỡ 𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛 +[2] 𝑝𝑝 + 1) 𝑝𝑝 log 𝑛𝑛 hành trên hệ thố
kích trộncỡdụng này thành
thực
thuật hiệntrộn,
toán danh
hết𝑛𝑛 Trong
quásách
𝑂𝑂(𝑝𝑝 𝑝𝑝 được
trình pha
logxử𝑝𝑝). thứ
lí trộn 3, này bộ𝑝𝑝 𝑝𝑝xửlàlí𝑝𝑝. 𝑝𝑝gốc 𝑛𝑛𝑝𝑝 𝑝𝑝sẽ 𝑝𝑝là:
= 𝑂𝑂( 𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛 +
𝑝𝑝
𝑝𝑝
= + 1) có kích cỡ là
gian gianyêu cầu cần là:
thiết là:O(𝑂𝑂p2(logp). ). Tổng thời gian yêu
ắpTổng thực
xếpthời hiện
với gian hết
kíchyêu cỡtrộn là 𝑝𝑝𝑝𝑝 2 𝑝𝑝 𝑛𝑛 𝑝𝑝 log
𝑛𝑛 log 𝑛𝑛 𝑛𝑛 + 𝑝𝑝 + 1
2350:
cầu là:,danh
𝑝𝑝 và sau sáchđóđã3.3 được Độ sắp xếptạp với= 𝑂𝑂(= (log
cầu là: Trong pha thứ 5, bộ xử Do líđó thứphức ta𝑖𝑖 có 3.2 hệ truyền Độsố phức tăng
𝑝𝑝
thông
log
𝑛𝑛 ) +𝑛𝑛log 𝑝𝑝 𝑛𝑛 𝑛𝑛
tốc
𝑛𝑛
tạp 𝑝𝑝+ 𝑝𝑝 +không
về 1 𝑝𝑝 +gian
𝑂𝑂 ( log về𝑝𝑝không + + 3.3 logĐộ 𝑝𝑝 )
- 8 phức
2 ( )
𝑝𝑝 logra𝑝𝑝 +
chọn 𝑝𝑝 −𝑝𝑝1− 1 ) kích
phần tử làm
cỡ là chốt.
𝑝𝑝 thành Sử một danh sách Do được 3.2
đó Độta phức
có hệ tạp
𝑝𝑝 số tăng gian
tốc 𝑝𝑝 𝑝𝑝 node
Trong
𝑂𝑂(𝑝𝑝 2
trộn log 𝑝𝑝phadanh
𝑝𝑝bằng+thứ 𝑝𝑝 5,
(sách − bộ
1 được
) ) xửSpeeduplísắp thứxếp. 𝑖𝑖 Mỗi
được Trong
tính
3.2 bằng:
Độ phaphức 2, tất
tạp cả
về 𝑛𝑛
không phần gian tử 𝑛𝑛
QuickSort. Kích thước của Bộ dữ+xử 𝑝𝑝 + 1 (0)
lí danh sách cóđược kích thước màTrong sau
dụng
g pha thuật
4, mỗi toán
bộ xử trộn,sắp
lí phân quáxếp trình
với xử
kích
bằng lícỡQuickSort. là 𝑝𝑝 2
,
Speedup và sau
Kíchđượcđó tính
thước Bộ
gốc
bằng:
xử
của
chứa
lídữlạigốc (0)
mảng
𝑛𝑛gồmcó
chứa 2𝑛𝑛
được
kích
2 chip Intek
trộn 𝑝𝑝 danh danh sách sách này được sắp xếp.
được tạo ra bằng các𝑛𝑛sử Mỗi được chia cắt. cỡ n, mỗi bộ xử lí còn cần danh
=chứa 𝑂𝑂( sách(log
được 𝑝𝑝
cómảngkích
) + logthướ 𝑝𝑝
Trong
Trong pha
pha 4, liệu
4, mỗi mỗi trênbộ bộ xửmỗi
2xử lí phân
bộ
lí phânxử líchia là và sau 𝑛𝑛 log
đó𝑛𝑛 𝑛𝑛 𝑝𝑝 𝑝𝑝
rộn này thực hiệnchọn
tử được
danh sắp
sách xếp.
này Thời
được
hết ra
tạo
𝑂𝑂(𝑝𝑝𝑝𝑝 −log
ra bằng
𝑝𝑝).
(phần
1𝑆𝑆liệu 𝑛𝑛, trên
các )sửtử
𝑝𝑝chọn =mỗi làm𝑝𝑝 bộchốt. =
xửkích
Bộ
𝑂𝑂( Sử
mảng
lí cỡlà
xử𝑛𝑛cólítrộn
𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛 .và +𝑛𝑛
Mỗi
gốcmỗi
kích 𝑝𝑝bộ
sau +cỡ
(0)danh
đó1)
xử 𝑛𝑛,líchứa
mỗi
yêu sách bộ
cầu
được xử được
GHz,
trên
một lícặp
mỗi 2 bộ
còn chia
GB cắt
bộ xử lí
RA
𝑛𝑛 dụng các phần tử chốt được trong
𝑛𝑛 𝑛𝑛 𝑝𝑝3, log 𝑛𝑛 trộn
2+ 𝑝𝑝lí +mỗi 1 𝑛𝑛danh sách trê
Tổng chiathời phần phần tử tử
gian yêu
được được cầu
sắp
dụng sắplà:
xếp. xếp. Thời
thuật Thời gian cần
toán trộn, thiết quá
𝑝𝑝 Trong
(log
là: (𝑛𝑛,𝑝𝑝𝑝𝑝)+
𝑆𝑆mảng
trình pha
xử=log
có kích
lí
𝑛𝑛
𝑝𝑝bộ 𝑝𝑝 xử
+ cỡ𝑝𝑝 +𝑛𝑛,
𝑛𝑛 lí 1)gốc
mỗiđọc bộ𝑛𝑛𝑝𝑝xử còn
DVD ROM. Tổ
dụng các 𝑛𝑛phaphần chọn
tử chốt ra 𝑝𝑝
đượchợp phần tử
chọnlýtrong làm mẫu. Do đó lại
thời cần chứa
có có được
kích mảng
cỡp. [2] kích
. Sử1)dụng 𝑝𝑝thuậtcỡ . Mỗi Trong
𝑛𝑛 toán trộ
𝑝𝑝
3, trong trường chọntưởng, ra phần
𝑝𝑝trị. mỗi tử nhớ làm mẫu.
đệm
𝑝𝑝 (logDo
kích
𝑝𝑝 + đólog
cỡ 𝑝𝑝 là
thời +𝑝𝑝𝑝𝑝𝑛𝑛+
ết là: 𝑂𝑂 ( ).. trộn này lý thực hiện giá hếttrong lạiDo
𝑂𝑂(𝑝𝑝 2cần 𝑝𝑝đó
log chứa
log𝑝𝑝). 𝑛𝑛
taĐộ được
cóphức hệmảng số kích tăngcỡtốc có 𝑛𝑛 kích cỡ . Sử dụng
. Mỗicủa 8 𝑝𝑝 node là kh
gianpha cần 3,
𝑂𝑂(𝑝𝑝𝑝𝑝 trong
2
thiết log là: trường
𝑝𝑝 𝑂𝑂
+ gian((
𝑛𝑛 hợp
𝑝𝑝 ).− yêu 1 ) ) cầu tưởng,
𝑛𝑛tính toán
mỗi = pha này
3.3 tạp =truyền
𝑂𝑂( thông
𝑙𝑙𝑙𝑙𝑙𝑙
𝑝𝑝 𝑛𝑛 + 𝑝𝑝 giá + trị.
1)
dữ danh sách có kích
𝑝𝑝 thước gian mà yêu
sau cầu
khi tính
log toán
𝑛𝑛 + 𝑝𝑝 trong
+ 1 pha
trong này
𝑝𝑝 logtrường 𝑛𝑛 hợp
𝑝𝑝 này yêu cầu thời gi
Trong pha thứ là: 5, bộ
Tổng thời xửgian lí 𝑝𝑝
thứ2yêu i trộn cầup là: Speedup
danh Trongđược phaTrong 4tính =
bộlog bằng:
xử
pha𝑛𝑛2,+tấtlí gốc truyền trong
cả n phần tử được -chia trường hợp 2 này nody
gđóphaTrong thứ được
sách 5,pha bộ sắp xử lí
xếp. thứ Mỗi 𝑖𝑖 danh sách
là: này được 𝑛𝑛𝑝𝑝 + 1
3.2 Độ phức Trong
ữ danh trộnrasách mỗi 4,
códanhmỗisách
kích
bộ xử
5,thướcbộtrên
lí 𝑛𝑛phân
mỗi mà bộ sau xử khi sẽtạp
lí chốt vềcắt. không gianlà 𝑂𝑂( log 𝑝𝑝) 𝑛𝑛
h sách
tạo Trong
đượcchọn
bằng pha
sắptrong
cácthứ
xếp. pha
sử dụng
Mỗi3,𝑂𝑂(𝑝𝑝
xử các
22lí
𝑝𝑝 log
thứ
phần 𝑖𝑖thông
𝑛𝑛 𝑝𝑝 +𝑛𝑛 (𝑝𝑝 −3.2 tử 𝑝𝑝
1
−) Độ
)
1 giá trị.
phức tạp về𝑛𝑛không log 𝑛𝑛 gian là 𝑂𝑂(𝑝𝑝2log 𝑝𝑝) và Stot
𝑝𝑝Do đó ta có hệ
(Storage1 số tăng
chia
𝑛𝑛 được
phần tử được sắp 𝑛𝑛 xếp. Thời trong𝑂𝑂 ( trường log + hợp 𝑆𝑆(lý𝑛𝑛, 𝑛𝑛𝑝𝑝) = 𝑛𝑛𝑛𝑛Trong 𝑛𝑛pha 3, bộ xử lí gốc đọc p giá
𝑝𝑝) thôngtrị. 𝑝𝑝 − 1 g
óhờitrộn 𝑝𝑝 𝑝𝑝có danh kích sách cỡ được
. Sử sắp
dụng xếp.
thuật 𝑝𝑝 Mỗi Bộ
toán 𝑝𝑝 xử
trộn
𝑛𝑛 lí
𝑂𝑂Trong
(sauloggốc (0)
+ chứa
𝑝𝑝)mỗi Speedupđược được tính bằng:
1) gian xử lí Intel
2 chip Xeo
ước được
này của
trộntạo
tưởng, dữmỗi radanh
mỗi bằngdanh 𝑝𝑝sách
các sách trên
sửcómỗi kíchbộ
kích xử lí sẽ mà
thước
thước pha
khi 𝑝𝑝
(log5, 𝑝𝑝
+ log bộ 𝑝𝑝
xử
Tổng+lí𝑝𝑝 gửi +thời song son
Trong pha 4, mỗi𝑝𝑝 bộ xử lí Bộ 2 𝑝𝑝 𝑝𝑝 Trong
phânxử lí gốc pha 4 bộ xử lí gốc
(0) chứa được Tổng thời gian truyền thông p-1
này 𝑛𝑛 mảng
các sửcó kích 𝑛𝑛 3 GB RAM, 4x7 Trong
𝑛𝑛 danh
i QuickSort.
gian
hần vàtử cần sách
thiết
chốt
trong
này
được
Kích được
cỡ𝑂𝑂chọn
là:
trường
𝑛𝑛(thước ).tạo
hợp trong
racủa bằng dữ danh𝑛𝑛trộn 𝑛𝑛 cỡcó
sách 𝑛𝑛,giá mỗi
kích trị.thướcbộ xử lí mà cònsau khi
𝑛𝑛 log 𝑛𝑛
sau
có
sau đó
kích
khi trộn . 𝑝𝑝Sử
mỗi danh 𝑛𝑛này
dụng Trong yêu
thuật
sách cầu
pha
trên toán thời
thứ
mỗi −gian
3,
bộ bộ
xử
mảng phầnxử có lí
tử, gốc
kíchdo đó, 𝑝𝑝sẽ
tổng 2là:số
log
cỡ 𝑛𝑛,𝑛𝑛𝑆𝑆(mỗi
𝑝𝑝 𝑛𝑛 phần
bộ= xử sẽ tử lí còn
𝑝𝑝
dụng các phần trộn
𝑝𝑝 chia
tửcỡ mỗi
𝑛𝑛
chốt .được danh
phần chọn sách
tử được trên
trong sắp
𝑝𝑝 mỗi
Trong xếp.
𝑝𝑝bộ2 pha xửThời lí
thứ sẽ =
3, bộ xử 𝑛𝑛,
lí 𝑝𝑝
gốc ) 𝑛𝑛 xử lí 𝑛𝑛gửi 𝑛𝑛 −
là: 𝑛𝑛
ytrên mỗi
lí sẽ bộ có xử kích
𝑛𝑛 lí là và
𝑝𝑝Sửsau dụng đó lạithuậtcần chứa
toán được
trộn mảng kích
Trong log cỡ
pha𝑛𝑛 + .5,Mỗi
𝑝𝑝 mỗi
+ 1 bộ (log + log - 1 phần
node
g trườnglàhợp 𝑂𝑂( lýlog tưởng, trộn
𝑝𝑝) 𝑝𝑝 mỗi
𝑝𝑝 danh 𝑛𝑛 sách đãtrộn được mỗi sắp danh xếp sáchvớiđược trên mỗi 𝑝𝑝 bộ xử lí 𝑝𝑝
𝑛𝑛 𝑛𝑛 sẽ 𝑛𝑛 𝑝𝑝𝑛𝑛 𝑝𝑝 𝑝𝑝 +
𝑛𝑛 𝑝𝑝2𝑝𝑝 + 1)
. Do đó
pha Trongtrong
3, thời
trong trường
pha
𝑝𝑝trường cóhợp
thứ kích
5,hợp này
bộcỡ yêu
lýxử cầu
. líSử
tưởng, thứ thời
bằng
dụng
trộn mỗi
𝑖𝑖 𝑝𝑝cần gian
QuickSort.
𝑛𝑛thuật
danh lại toáncần
sáchphức chứa
đãKích
trộn được thước 𝑛𝑛 mảng
sắpkhông xếp của kích
với dữsố + cỡ . Mỗi
trong trường hợp
gian này
cần yêu
thiết
𝑝𝑝 cầu
là: thời
𝑂𝑂 ( gian
). truyền
3.2 là
Độ thông
phần là
tạp tử,− vềdo .đó,
𝑂𝑂 (tổng log
gian 𝑝𝑝𝑝𝑝danh
phần +tử𝑛𝑛(MGT)sách
+ 𝑛𝑛truyền
cần cóbao
log kích
𝑝𝑝 ) gồm𝑛𝑛thư
ong ra 𝑝𝑝 phần tử
𝑛𝑛 làm mẫu.kích Do cỡ đólà 𝑝𝑝
thời thành một
có danh sách 𝑛𝑛 được
𝑝𝑝 kích cỡ . Sử dụng𝑛𝑛thuật toán trộn 𝑂𝑂 ( logcần+truyền 𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑝𝑝𝑝𝑝 log𝑝𝑝 𝑛𝑛 𝑝𝑝 + th+
rộn pha 𝑝𝑝làdanhnày sách
𝑂𝑂( log 𝑝𝑝)
được
trong sắp
trường xếp.hợpkích
kích
Mỗiliệu
nàycỡ
cỡtrên
yêulàsong
là mỗi
cầu
𝑝𝑝 thành bộ 𝑝𝑝 mộtlídanh
xử
thông là
là - sách
. và được
sau đó = 𝑝𝑝Core𝑝𝑝 3.2 GHz, 𝑝𝑝
yêu cầu tính 𝑝𝑝 Tổng
toán trong thời
sắp gian
xếp phavới xử
nàylí song 𝑝𝑝2 ,thời và gian
Bộ phasau đó
xử lícuối 𝑝𝑝
gốccùng, (0) bộ chứa được
log𝑛𝑛mỗi
trộn 𝑛𝑛 + danh𝑝𝑝 𝑛𝑛+ 1sách tr
danh sách này được tạo𝑛𝑛ra Trong bằng các sắp
pha sửthứ xếp
trong 5, với Trong
trường
bộ kích
xử lí cỡ
hợp thứ lànày
Trong 𝑖𝑖 𝑝𝑝2yêu,phavàcầu sauthời
cuối đó gian
cùng, xửbộ lí=xử𝑂𝑂( lí 𝑝𝑝
gốc (log tập𝑝𝑝𝑛𝑛 ) + log𝑛𝑛𝑝𝑝
hợp
gốc sẽTổnglà: thờilàgian 𝑂𝑂( log 𝑝𝑝) chọn ratửmảng phầncó tửkích làm mẫu. 3.2 Độ phức tạp về GBHDD.
không =Trong
gian 𝑂𝑂( (
Tổng thời chọn xử
gian
𝑝𝑝
lí
ra xử song
𝑝𝑝 − song
lí 1song phầnsongsẽ là: 𝑝𝑝 làm chốt. Sử𝑛𝑛 cỡ 𝑛𝑛,Do mỗiđóbộ thời xử lí còn có kích cỡ . Sử dụn
𝑝𝑝
dụng các phần tử chốt trộn được 𝑝𝑝 chọn sách
danh chọnđược
trong ra
gốc
làyêu 𝑂𝑂(quá 𝑝𝑝 𝑛𝑛−
sắp
tập log 1
hợp phần
xếp. 𝑛𝑛
𝑝𝑝) xử −
Mỗi tử làm
phần chốt.
tử. Sử + 𝑝𝑝 + 1 𝑝𝑝
)cvới sẽ là: 𝑛𝑛 𝑛𝑛dụng thuật 𝑛𝑛 𝑛𝑛toán gian trộn, 𝑝𝑝cầu trìnhtính toán lí𝑝𝑝 trong pha này 𝑛𝑛
Bộlícỡxử. Mỗi lítrong gốctrường gốc- chứa
(0)
Năng
tập
+ 𝑝𝑝hợp +đư lự1𝑛𝑛
pha 3, trong 𝑛𝑛
𝑂𝑂 ( trường𝑛𝑛
log hợp+ 𝑝𝑝 lý
+ tưởng,
+ mỗi
dụng
log 𝑝𝑝 ) thuật lại cần
toán chứa trộn, được quá mảng
trình kích
xử hợp này
𝑂𝑂 ( log danh
𝑝𝑝) Tổng sáchthời này gian đượcxử tạolírasong bằng2song các Do sử đó tổng số giá trị cần 𝑝𝑝
ược 𝑝𝑝 𝑝𝑝 𝑝𝑝 +𝑝𝑝trộn này 𝑝𝑝 thực 𝑝𝑝 là: hiện hết 𝑂𝑂(𝑝𝑝 log 𝑝𝑝). 𝑛𝑛 truyềntrữthông dùnglàchung : E
i 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 trộn này Do
Tổng
thực đó thời
hiện tổng gian
hết số giá
xử
𝑂𝑂(𝑝𝑝 mảng
lí
2trị song
log cầncó
𝑝𝑝).= kích
𝑂𝑂(
truyền
song cỡ
𝑙𝑙𝑙𝑙𝑙𝑙 𝑛𝑛,
𝑛𝑛 mỗi
+
𝑛𝑛 𝑝𝑝 bộ
+ 1)
𝑛𝑛 xử lí cò
dụng các𝑛𝑛 phần𝑛𝑛tử chốt được chọn trong 𝑝𝑝 là 𝑂𝑂(HDD logSCSI 𝑝𝑝) 𝑙𝑙𝑙𝑙𝑙𝑙320
ộđóxử lí 𝑂𝑂gốc ( log sẽ+là: Tổng𝑝𝑝 = + 𝑂𝑂( thời+ (log log 𝑝𝑝
gian yêu
) )+ cầu log là:
𝑝𝑝 𝑝𝑝 = 𝑂𝑂( Do𝑛𝑛 𝑛𝑛 đó+
c Trong pha 𝑝𝑝 thứ𝑝𝑝3, bộ xử 𝑝𝑝 𝑝𝑝lí𝑝𝑝gốc𝑝𝑝Tổngsẽthông 𝑛𝑛 𝑛𝑛 lại cần chứa được mảng kích 𝑝𝑝 cỡ . M
sắp xếp với pha 3, trong trường thời hợp là: gian lýlà 𝑂𝑂 :(yêulog
tưởng, cầumỗilà: + 𝑝𝑝) TẠP CHÍ KHOA HỌC 5
𝑝𝑝
Sử 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑛𝑛 𝑝𝑝 𝑝𝑝 Do đó ta cóhệTổng
QUẢN LÝ VÀ CÔNG NGHỆ
hệthống
thông
sốthời chia
là : sẻt
tăng
ó𝑝𝑝 danh sách đã được 𝑂𝑂=( sắp log + 𝑝𝑝 Do đó ta gian
2 + + (log 𝑝𝑝 )
+ 𝑂𝑂(𝑝𝑝 xếp 𝑂𝑂(𝑝𝑝
+(log log 𝑝𝑝
1 với) + log 𝑝𝑝 𝑛𝑛 2 𝑛𝑛 + 𝑝𝑝 − 1 ) có
ửh lísách được 𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑝𝑝 𝑛𝑛 𝑂𝑂(𝑝𝑝
+ 𝑝𝑝 2log 𝑝𝑝 + (𝑝𝑝𝑛𝑛− 1𝑛𝑛
+ 𝑝𝑝 − 1 + 𝑛𝑛 − ) )𝑛𝑛
Speedup
+ 𝑛𝑛 −
𝑛𝑛
được tính v2.3.0.5.
bằng:
ử 𝑂𝑂 ( log + 𝑝𝑝 + + log 𝑝𝑝 ) sẽ là:
- Do đó tổng số giá trị cần truyền
HDD SCSI 320 MBps 15KRpm, dùng
thông là :
hệ thống chia sẻ file: GPFS cho Linux
𝑛𝑛 𝑛𝑛 chung EXP400 với 10x73 GB HDD SCSI 320
𝑛𝑛 + 𝑝𝑝2 + 𝑝𝑝 − 1 + 𝑛𝑛 − + 𝑛𝑛 − 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
1
= 2𝑛𝑛 (1 − ) + 𝑝𝑝2 + 𝑝𝑝 - Các node chạy HĐH Redhat Enterprise
𝑝𝑝 Enterprise
Linux 3.0 vàLinux 3.0nối
được kết vàvới
được
nhaukết nốiqua
thông
mạng Gethernet.
với nhau thông qua mạng Gethernet.
−1
- Các thuật toán được lập trình bằng ngôn
4. Mô phỏng thuật toán - Các
ngữ C++ thuậtthưtoán
sử dụng việnđược lậpsong
lập trình trìnhsong
4. Mô phỏng thuật toán
MPI. Mô phỏng nhằm mục đích kiểm tra sự
4.1 Môi trường mô phỏng: bằng ngôn ngữ C++ sử dụng thư viện
4.1 Môi trường mô phỏng: song song hóa của thuật toán PSRS.
Quá trình mô phỏng được tiến hành trên
4.2 Phương pháp mô phỏng
hệ thống IBM Linux Cluster 2350:
lập trình song song MPI. 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:
- 8 node tính toán, mỗi node gồm 2 chip
Intel nhằm mục đích
Core kiểm tra sự songRAM,
song (10 , 10 , 10số7) phần
và chạy trênmảng
cùng thay
số bộđổi
5 6
Xeon Dual 3.2 GHz, 2 GB - Cố định tử của
1x36 GB HDD, DVD ROM. Tổng năng lực tính sốxửbộ lí,
xửchạy
lí sử dụng (2, 4,10
8) lần
chạyđểtừđo
5 đến
hóa của thuật toán PSRS. từ 5 đến thời10
toán của 8 node là khoảng 51.2 Gflops. 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
- 4.2 Phương
2 node phụcpháp môtrữ
vụ lưu phỏng
(Storage1 và
Storage2), mỗi node gồm 2 chip Intel Xeon chạy.
- Thay đổi số phần tử của mảng (105, 106,
Dual Core Về
3.2 nguyên tắc RAM,
GHz, 3 GB lấy số4x72
liệu GB
mô 107) và chạy trên cùng số bộ xử lí, chạy từ 5
HDD.phỏng: 4.310Kết
đến lần quả mô
để đo phỏng
thời gian và lấy giá trị trung
bình các lần chạy.
- 1 node đóng vai trò quản lí (MGT) bao 4.3.1 Kết quả mô phỏng khi chạy
- Cố
gồm chip Intel định
Xeon sốCore
Dual phần3.2
tửGHz,
của 3mảng
GB trên
4.3 thuật toán
Kết quả môPSRS
phỏng
RAM, 2x36 GBHDD.
thay đổi số bộ xử lí sử dụng (2, 4, 8) 4.3.1 Kết quả mô phỏng khi chạy trên
- Năng lực lưu trữ: thiết bị lưu trữ dùng thuật toán PSRS
chạy từ 5 đến 10 lần để đo thời gian và
lấy giá trị trung bình các lần chạy.
Thời gian chạy trung bình của thuật toán
Input T.sequency PSRS(giây)
Size (seconds)
P=2 P=3 P=4 P=8
105 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
6 TẠP CHÍ KHOA HỌC
thấy rằng
QUẢN thuật
LÝ VÀ toán
CÔNG NGHỆPSRS hoàn toà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ộ
- Qua mô phỏng, trước hết nhận thấy rằng phần tử n=1000000 thì thời gian chạy song
thuật toán PSRS hoàn toàn có thể song song song nhanh gấp 2.15 lần, với n=10000000
hóa được và khi chạy chương trình có thể sử thì thời gian chạy song song nhanh gấp 2.16
dụng số bộ xử lí bất kì, không cần điều kiện lần. Trường hợp cuối cùng, sử dụng 4 bộ xử
ràng buộc về số bộ xử lí sử dụng. 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
Về kết quả mô phỏng, nhìn vào bảng kết nhanh gấp 1.95 lần, với n=10000000 thì thời
quả nhận thấy rằng, thời gian chạy chương gian chạy song song nhanh gấp 2.11 lần.
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 Rõ ràng, khi chạy trên đa bộ xử lí, thuật
mảng và thay đổi số bộ xử lí sử dụng (2, 3, 4, toán PSRS cho kết quả hiệu quả hơn nhiều
8 bộ xử lí) kết quả đều cho thời gian chạy tốt lần so với chạy tuần tự. Số bộ xử lí cho kết quả
hơn so với thời gian chạy tuần tự (sử dụng tốt nhất là 4 bộ xử lí. Qua kết quả mô phỏng,
trên 1 bộ xử lí). 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
Cụ thể, trong trường hợp sử dụng 2 bộ toán sẽ đạt được hiệu quả tốt về thời gian.
xử lí so với thời gian chạy tuần tự, với số phần Đến một lúc nào đó, khi tăng số bộ xử lí của
tử n=100000 thì thời gian chạy song song hệ thống lên nhưng độ hiệu quả không thể
nhanh gấp 1.5 lần, với số phần tử n=1000000 tăng lên được nữa. Do đó luôn luôn cần xác
thì thời gian chạy song song nhanh gấp 1.36 định số bộ xử lí tốt nhất mà hệ thống nên sử
lần, với n=10000000 thì thời gian chạy song dụng trong quá trình chạy chương trình.
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 Dưới đây là các biểu đồ thể hiện kết quả
tự, với số phần tử n=100000 thì thời gian chạy thuật toán PSRS trên hệ thống song
chạy songDướisong
đây nhanh gấp đồ
là các biểu 3 lần, với số
thể hiện song:
kết quả chạy thuật toán PSRS trên hệ 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
Biểu đồ so sánh thời gian chạy thuật toán PSRS
5
4.5
4
3.5
Thời gian(giây)
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 Qua kết quả mô phỏng cũng như
chạy thuật toán PSRS
- Biều đồ 1. Biểu đồ so sánh thời gian Qua kết quả mô phỏng cũng như
chạy thuật toán PSRS
căn cứ vào độ phức tạp tính toán của
Biểu đồ 2. Biểu đồ so sánh thời gian chạy của các BXL
thuật toánvớiPSRS,
cùng số
cóphần
thể tửkhẳng
N=106 định
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
0.4186
0.4
0.35
0.3343
Thời gian (giây)
0.3
0.2755
0.25
0.2 0.2146
0.1947
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 TÀI LIỆU THAM KHẢO
Qua kết quả mô phỏng cũng như căn 1. Grama A., A. Gupta, G. Karypis, V.
cứ vào độ phức tạp tính toán của thuật toán Kumar (2003), “Introduction to Parallel
PSRS, có thể khẳng định rằng, PSRS là một Computing”, Addison Wesley.
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 2. Xiaobo Li, Paul Lu, Jonathan Schaeffer,
trội so với hệ thống xử lý tuần tự. Thuật toán John Shillington, Pok Sze Wong (2004), “On
này có thể được áp dụng rộng rãi trong các the Versatility of parallel sorting by Regular
ứng dụng xử lý song song, là bước tiền đề để Sampling”, University of Alberta, EdmonTon,
nâng cao hiệu quả tìm kiếm dữ liệu trên các Alberta, Canada.
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 toán PSRS để cho kết quả tốt
hơn.
8 TẠP CHÍ KHOA HỌC
QUẢN LÝ VÀ CÔNG NGHỆ
nguon tai.lieu . vn
