ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------
BÙI THANH TUYỀN
NÂNG CAO HIỆU QUẢ BÀI TOÁN SẮP XẾP VỚI GIẢI THUẬT SONG SONG
LUẬN VĂN THẠC SĨ KHOA HỌC
Hà Nội – Năm 2014
1
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------
BÙI THANH TUYỀN
NÂNG CAO HIỆU QUẢ BÀI TOÁN SẮP XẾP VỚI GIẢI THUẬT SONG SONG
Chuyên ngành: Cơ sở toán cho tin học
Mã số: 60460110
LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
TS. Nguyễn Thị Hồng Minh
Hà Nội – Năm 2014
2
LỜI CẢM ƠN
Trên thực tế, không có thành công nào mà không gắn liền với những sự
hỗ trợ, giúp đỡ. Trong suốt thời gian từ khi bắt đầu học tập tại trường đến
nay, em đã nhận được rất nhiều sự quan tâm, giúp đỡ của quý Thầy Cô Khoa
Toán-Cơ-Tin học, Trường Đại học Khoa học Tự nhiên - ĐHQGHN đã cùng
với tri thức và tâm huyết của mình để truyền đạt vốn kiến thức quý báu cho
chúng em, và luôn luôn tạo mọi điều kiện tốt nhất cho chúng em trong suốt
quá trình theo học tại trường. Em xin chân thành cảm ơn quý Thầy Cô và
Ban lãnh đạo nhà trường!
Với lòng biết ơn sâu sắc nhất, em xin gửi lời cảm ơn tới TS. Nguyễn
Thị Hồng Minh, Phó chủ nhiệm Khoa Sau đại học - ĐHQGHN, là cán bộ
trực tiếp hướng dẫn và định hướng khoa học cho em. Cô đã dành nhiều thời
gian cho việc hướng dẫn em cách nghiên cứu, đọc tài liệu, cài đặt các thuật
toán và giúp đỡ em trong việc xây dựng chương trình, em xin chân thành
cảm ơn cô!
Em cũng xin được chân thành gửi lời cảm ơn đến quý thầy cô, các
anh chị em của Trung tâm Tính toán Hiệu Năng Cao Trường Ðại học Khoa
học Tự nhiên đã quan tâm giúp đỡ, tạo điều kiện về nhiều mặt, chỉ bảo tận
tình trong quá trình em thực hiện thực nghiệm tại trung tâm.
Và cuối cùng em xin bày tỏ lòng chân thành biết ơn tới lãnh đạo khoa
Công nghệ Thông tin,Trường Đại học Kinh doanh và Công nghệ Hà Nội
cùng bạn bè đồng nghiệp, ba mẹ và anh chị em đã luôn ở bên cạnh những
lúc em khó khăn và tạo điều kiện thuận lợi giúp em hoàn thành luận văn này.
Hà Nội, ngày 26 tháng 3 năm 2014
Học viên: Bùi Thanh Tuyền
1
Mục lục
LỜI CẢM ƠN ................................................................................................. 1
Danh mục viết tắt ............................................................................................ 4
Danh mục các hình .......................................................................................... 5
Danh mục các bảng ......................................................................................... 5
MỞ ĐẦU ........................................................................................................ 6
CHƯƠNG 1. TỔNG QUAN VỀ XỬ LÝ SONG SONG ................................... 8
1.1 Tổng quan về xử lí song song ....................................................... 8
1.1.1 Tính toán tuần tự và tính toán song song.............................................. 8
1.1.2 Kiến trúc máy tính song song ............................................................. 10
1.1.3 Một số mạng kết nối trên hệ thống song song .................................... 11
1.1.3.1 Mạng liên kết tuyến tính và liên kết vòng ................................... 11
1.1.3.2 Mạng liên kết lưới hai chiều ....................................................... 12
1.1.3.3 Mạng liên kết hình khối .............................................................. 12
1.1.4 Cơ sở đánh giá giải thuật song song ................................................... 13
1.1.4.1 Thời gian thực hiện ..................................................................... 13
1.1.4.2 Hệ số tăng tốc và độ hiệu quả giải thuật ..................................... 14
1.2 Tổng quan về bài toán sắp xếp .................................................... 15
1.2.1 Bài toán sắp xếp. ................................................................................. 15
1.2.2 Các cấu trúc dữ liệu cho bài toán sắp xếp. ......................................... 18
1.2.3 Phân lớp các thuật toán sắp xếp dựa trên độ phức tạp. ...................... 19
1.2.3.1 Lớp thuật toán có độ phức tạp O(n2) ........................................... 19
1.2.3.2 Lớp thuật toán có độ phức tạp O(nlogn) ..................................... 23
1.2.3.3 Thuật toán sắp xếp có độ phức tạp thấp với dữ liệu đặc biệt ...... 26
1.3 Kết luận chương ........................................................................ 28
CHƯƠNG 2. MỘT SỐ THUẬT TOÁN SONG SONG CHO BÀI TOÁN SẮP XẾP .............................................................................................................. 29
2
2.1 Chiến lược song song cho bài toán sắp xếp. ................................ 29
2.2 Thuật toán sắp xếp song song phát triển dựa trên thuật toán tuần
30
tự
2.2.1 Thuật toán sắp xếp hoán vị chẵn lẻ..................................................... 30
2.2.2 Thuật toán Shellsort. ........................................................................... 32
2.2.3 Thuật toán Parallel QuickSort. ........................................................... 36
2.2.4 Thuật toán HyperQuicksort ................................................................ 41
2.3 Thuật toán sắp xếp song song dựa trên các mẫu chuẩn PSRS ....... 47
2.3.1 Tư tưởng thuật toán ............................................................................ 47
2.3.2 Đánh giá độ phức tạp .......................................................................... 50
2.3.3 Ví dụ ................................................................................................... 50
2.4 Kết luận chương ........................................................................ 52
CHƯƠNG 3. ỨNG DỤNG LẬP TRÌNH SONG SONG CÀI ĐẶT THUẬT TOÁN SẮP XẾP PSRS VÀ PARALLELQUICKSORT ................................. 53
3.1 Môi trường và phương pháp thực nghiệm ................................... 53
3.1.1 Môi trường thực nghiệm ..................................................................... 53
3.1.2 Phương pháp thực nghiệm .................................................................. 54
3.2 Các kết quả thực nghiệm ............................................................ 54
3.2.1 Kết quả thực nghiệm khi chạy trên thuật toán PSRS ......................... 54
3.2.2 So sánh kết quả giữa thuật toán PSRS và ParallelQuicksort .............. 56
3.3 Kết luận chương ........................................................................ 57
KẾT LUẬN ................................................................................................ 588
3
TÀI LIỆU THAM KHẢO .............................................................................. 59
Danh mục viết tắt
Viết tắt
Viết đầy đủ
Ý nghĩa
ADN
Acid Deoxyribo Nucleic
Phân tử di truyền
CPU
Central Processing Unit
Đơn vị xử lí trung tâm
MIMD
Multiple Instruction Multiple
Đa lệnh Đa dữ liệu
Data
MISD
Multiple Instruction Single Data
Đa lệnh Đơn dữ liệu
PQ
Parallel QuickSort
Sắp xếp nhanh song
song
PSRS
Parallel Sorting by Regular
Sắp xếp song song dựa
Sampling
trên mẫu
SIMD
Single Instruction Multiple Data
Đơn lệnh Đa dữ liệu
SISD
Single Instruction Single Data
Đơn lệnh Đơn dữ liệu
4
Danh mục các hình ...................................................................................... 5
Hình 1.1 Minh họa quá trình xử lí tuần tự .................................................... 8
Hình 1.2 Minh họa quá trình xử lí song song ............................................... 9
Hình 1.3 Phân loại Flynn về các kiến trúc song song ................................. 10
Hình 1.4 Mạng liên kết tuyến tính và mạng vòng ....................................... 11
Hình 1.5 Mạng liên kết lưới hai chiều ........................................................ 12
Hình 1.6 Mạng liên kết khối 4 chiều với 16 bộ xử lí. ................................. 13
Hình 2.1 Ví dụ thuật toán ShellSort ............................................................ 35
Hình 2.2 Minh họa thuật toán ParallelQuickSort ........................................ 38
Hình 2.3 Ví dụ minh họa thuật toán ParallelQuickSort .............................. 40
Hình 2.4 Minh họa thuật toán HyperQuickSort .......................................... 43
Hình 2.5 Ví dụ minh họa thuật toán HyperQuickSort ................................ 45
Hình 2.6 Minh họa thuật toán PSRS ........................................................... 49
Hình 3.1 Biểu đồ so sánh thời gian chạy của thuật toán PSRS .................. 57
Hình 3.2 Biểu đồ so sánh thời gian chạy của các BXL chạy với N=106 .... 57
Hình 3.3 Biểu đồ so sánh thời gian chạy của thuật toán PSRS và PQ........ 58
Danh mục các bảng
Bảng 1. So sánh kết quả chạy thuật toán PSRS .......................................... 55
Bảng 2. So sánh thời gian chạy của PSRS và Parallel Quicksort ............... 58
5
MỞ ĐẦU
Từ thủa sơ khai của lịch sử máy tính và khoa học tính toán, việc xây dựng được
một chương trình tính toán trên một máy tính là điều hết sức kỳ diệu đối với tất cả
mọi người. Từ những chiếc máy tính khổng lồ, cồng kềnh nhưng chỉ thao tác được
những tác vụ đơn giản đến những máy nhỉnh hơn lòng bàn tay nhưng có thể tính
toán được hàng nghìn tỷ phép tính trong một giây, từ những chương trình rất nhỏ
chỉ có vài ba câu lệnh của những ngày xa xưa, đến những chương trình vô cùng
lớn có sức ảnh hưởng đến toàn cầu như ngày nay… tất cả những điều đó đã nói lên
được sự phát triển mạnh mẽ của ngành công nghệ thông tin.
Sự phát triển cả về phần cứng lẫn phần mềm đã tạo ra rất nhiều sự đổi thay
trong công nghệ tính toán của ngành khoa học máy tính cũng như ảnh hưởng của
nó đến tất cả các lĩnh vực khác nhau trong xã hội. Càng ngày yêu cầu về tốc độ
tính toán và xử lí càng lớn, đòi hỏi các máy tính, các phần mềm chương trình phải
thực thi cực nhanh. Chính vì vậy, việc sử dụng các hệ thống tính toán truyền thống
đã không thể đáp ứng kịp nhu cầu đó của con người cũng như của các ngành khoa
học liên quan. Việc xây dựng các chương trình tính toán trên các hệ thống song
song để hỗ trợ cho hệ thống tuần tự đã trở thành một điều tất yếu. Nhìn lại chúng
ta thấy rằng, hầu hết các chương trình đòi hỏi tốc độ tính toán lớn đều áp dụng
trong những lĩnh vực quan trọng ảnh hưởng lớn đến xã hội. Không đâu xa, đó là
những ứng dụng trong dự báo thời tiết, thiên tai, đó là những ứng dụng trong những
ngành thiết kế máy bay, kĩ thuật quân sự, đó là những ứng dụng trong thương mại
điện tử, trong y sinh học v.v… tất cả đều được xử lí song song với mục tiêu nâng
cao hiệu quả xử lí tính toán.
Nhận thấy đây là một trong những hướng nghiên cứu đang được phát triển và
sẽ được ứng dụng nhiều trong thực tế, vì vậy em đã lựa chọn đề tài của mình vào
việc nghiên cứu và tìm hiểu về các hệ thống xử lí song song áp dụng vào giải quyết
một bài toán cụ thể đó là bài toán sắp xếp. Khái niệm sắp xếp dường như đã gắn
liền với xã hội loài người từ thuở ban đầu của nền văn minh. Nó đơn giản thể hiện
6
trong việc sắp hàng, trong việc phân công công việc,… Ngày nay, trong một thế
giới mà khoa học công nghệ thay đổi từng ngày và 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ính hiệu quả của các giải
thuật sắp xếp cũng ngày càng trở nên quan trọng hơn.
Từ những vấn đề trên, đề tài “Nâng cao hiệu quả bài toán sắp xếp với giải
thuật song song” sẽ tập trung vào nghiên cứu việc song song hóa các thuật toán
sắp xếp nhằm giảm thiểu thời gian sắp xếp dữ liệu để đưa vào áp dụng trong các
ứng dụng thực tế. Luận văn gồm có 3 chương:
Chương 1. Tổng quan về xử lí song song và bài toán sắp xếp. Nội dung chủ
yếu của chương nhằm giới thiệu tổng quan về xử lí song song, các mô hình cơ bản
trong hệ thống song song đồng thời đưa ra sự nhìn nhận tổng quan nhất về bài toán
sắp xếp, đi đôi với việc hệ thống hóa lại hầu hết các thuật toán sắp xếp theo hướng
tính toán tuần tự.
Chương 2. Một số thuật toán song song cho bài toán sắp xếp. Nội dung của
chương tập trung vào vấn đề phát triển các thuật toán song song cho bài toán sắp
xếp. Đây là nội dung chính của luận văn, các thuật toán sắp xếp sẽ được song song
hóa dựa trên các chiến lược cụ thể.
Chương 3. Ứng dụng lập trình song song cài đặt thuật toán PSRS và
ParallelQuickSort. Nội dung của chương sẽ trình bày các kết quả thực nghiệm trên
7
thuật toán PSRS và so sánh hai thuật toán PSRS và ParallelQuicksort về thời gian xử lí khi cùng chạy trên hệ thống tính toán song song với nhiều bộ xử lí.
CHƯƠNG 1. TỔNG QUAN VỀ XỬ LÝ SONG SONG VÀ BÀI TOÁN SẮP XẾP
1.1 Tổng quan về xử lí song song
1.1.1 Tính toán tuần tự và tính toán song song
Trong những thập niên 60, nền tảng để thiết kế máy tính đều dựa trên mô
hình của John Von Neumann, với một bộ xử lí đơn được nối với một vùng lưu trữ
làm bộ nhớ và tại cùng một thời điểm chỉ có một lệnh được thực thi. Đó là hình
thức tính toán tuần tự [1].
Tuy nhiên, hiện nay khoa học kỹ thuật ngày càng phát triển, từ đó sẽ đặt ra
nhiều bài toán với khối lượng tính toán rất lớn, trong đó có những bài toán mà kết
quả chỉ có ý nghĩa nếu được hoàn thành trong thời gian cho phép. Từ đó hình thành
nên hệ thống xử lí song song. Xử lí song song là quá trình xử lí gồm nhiều tiến
trình được kích hoạt đồng thời, được thực hiện trên nhiều bộ xử lí và cùng tham
gia vào giải quyết một bài toán. Hình 1.1 và 1.2 dưới đây phần nào cho thấy cái
nhìn khái quát về sự khác nhau giữa xử lí tuần tự và xử lí song song.
Hình 1.1 Minh họa quá trình xử lí tuần tự
Trong xử lí tuần tự (hình 1.1), một CPU sẽ thực hiện lần lượt các lệnh Si để
giải quyết bài toán. Với xử lí song song (hình 1.2) các lệnh để giải quyết bài toán
được chia ra thành các cụm độc lập, được gọi là các tiến trình và mỗi tiến trình sẽ
8
được thực hiện trên một CPU khác nhau.
Hình 1.2 Minh họa quá trình xử lí song song
Mục đích xây dựng hệ thống xử lí song song là để thực hiện tính toán nhanh
hơn trên cơ sở sử dụng đồng thời nhiều bộ xử lí để giải quyết được những bài toán
phức tạp với yêu cầu khối lượng tính toán lớn. Ví dụ các bài toán tính toán lớn như
mô phỏng các hoạt động ở mức lượng tử, tính toán quỹ đạo chuyển động của vật
thể trong không gian, dự báo thời tiết, các bài toán nghiên cứu trên ADN…
Trong tính toán song song hiện nay, chúng ta có thể sử dụng hai mô hình
chính:
Thứ nhất là sử dụng các siêu máy tính với rất nhiều các bộ xử lí được tích
hợp bên trong và được thiết kế đồng bộ cả về phần cứng lẫn phần mềm. Các công
nghệ được áp dụng trong các siêu máy tính thường là các công nghệ tiên tiến làm
cho giá thành của hệ thống siêu máy tính thường rất cao.
Cách thứ hai là kết nối các đơn máy tính đồng bộ lại với nhau và cùng thực
hiện bài toán, hệ thống các máy tính kết nối này là hệ thống tính toán song song
phân cụm. Hệ thống này có ưu điểm là giá thành rẻ hơn do nó sử dụng các thiết bị
thông thường và tính linh hoạt của hệ thống (số nút, số bộ xử lí, bộ nhớ, thiết bị
mạng… đều mang tính tùy biến cao). Sự phát triển mạnh mẽ của mạng máy tính,
các công nghệ mạng hiện nay đã lấp đi sự hạn chế về truyền thông trong hệ thống
máy tính song song phân cụm làm cho nó được phát triển rộng rãi. Các lĩnh vực
sử dụng hệ thống tính toán song song phân cụm thường yêu cầu tính toán không
quá lớn như xử lí ảnh, nhận dạng vân tay, tính toán kết cấu công trình, mô phỏng
9
các thí nghiệm…
Phần dưới đây sẽ trình bày về các mô hình máy tính song song cơ bản theo
phân loại của Flynn giúp chúng ta có cái nhìn tổng quát hơn về các hệ thống song
song.
1.1.2 Kiến trúc máy tính song song
Một hệ thống máy tính song song là một máy tính với nhiều hơn một bộ xử
lí cho phép thực hiện đồng thời nhiều tiến trình. Định nghĩa này có thể bao quát
được tất cả các siêu máy tính với hàng trăm bộ xử lí, các mạng máy tính trạm hay
các hệ thống nhúng...
Dựa vào sự phân biệt ở cách kết nối giữa các bộ xử lí (hay thành phần xử
lí), giữa bộ xử lí và bộ nhớ mà có rất nhiều loại kiến trúc máy tính song song khác
nhau. Nhưng theo phân loại của Flynn dựa trên cấu trúc luồng lệnh và luồng dữ
Hình 1.3 Phân loại Flynn về các kiến trúc song song
liệu thì có bốn kiến trúc điển hình [1] đó là:
SIMD- Single Instruction Multiple Data: Đơn lệnh đa dữ liệu. Đây là một kiểu
máy tính song song mà các bộ xử lí thực hiện cùng một lệnh nhưng với các dữ liệu
khác nhau. Mô hình này có ưu điểm là đơn giản trong thiết kế phần cứng cũng như
phân mềm nhưng chỉ phù hợp để giải quyết các bài toán tương đối đặc thù có tính
cân đối cao như trong xử lí như xử lí ảnh, các bài toán với các dữ liệu dạng vecto
hoặc ma trận. Các thuật giải cho các đa máy tính thường chạy không hiệu quả trên
các máy SIMD.
MIMD- Multiple Instruction Multiple Data: Đa lệnh đa dữ liệu. Đây là một
10
mô hình kiến trúc máy tính song song thông dụng hiện nay. Với mô hình này thì
tất cả các bộ xử lí sẽ thực hiện các lệnh khác nhau với các dữ liệu riêng khác nhau.
Sự thực thi các lệnh có thể theo cơ chế đồng bộ hoặc không đồng bộ, điều này giúp
cho MIMD rất linh hoạt trong việc xử lí song song. Tuy nhiên, cùng với tính linh
hoạt của mình, mô hình MIMD cũng mang theo một sự phức tạp nhất định. Việc
lập trình được những bài toán song song theo mô hình này đòi hỏi có nhiều công
sức nghiên cứu, phân tích bài toán để tìm ra một cách phân rã tối ưu.
Ngoài ra còn có hai loại mô hình khác theo phân loại của Flynn tuy nhiên ít
thông dụng: SISD-Single Instruction Single Data: Đơn lệnh đơn dữ liệu và MISD-
Multiple Instruction Single Data: Đa lệnh đơn dữ liệu.
Với sự đa dạng của các mô hình kiến trúc máy tính song song, thì việc tổ chức
và kết nối các bộ xử lí trong các mô hình cũng được quan tâm và nghiên cứu. Hầu
hết các máy tính với đa bộ xử lí đều phải đưa ra một cách để các bộ xử lí tương tác
với nhau. Trong một số hệ thống, các bộ xử lí sử dụng kết nối mạng để truy cập
vào bộ nhớ chia sẻ, nhưng cũng có một số hệ thống khác thì lại sử dụng phương
thức gửi và nhận tin nhắn để truyền thông với nhau. Dưới đây là một số mạng kết
nối được sử dụng trong các hệ thống máy tính song song.
1.1.3 Một số mạng kết nối trên hệ thống song song
1.1.3.1 Mạng liên kết tuyến tính và liên kết vòng
Với mạng liên kết tuyến tính, các bộ xử lí được liên kết với nhau theo dãy
và được đánh số theo thứ tự tăng dần. Trong mạng liên kết này, trừ hai phần tử đầu
và cuối của mạng, tất cả các bộ xử lí đều có hai láng giềng là bộ xử lí trước và sau
nó. Đây là dạng liên kết đơn giản, nhưng dữ liệu cũng cần phải chuyển qua nhiều
bộ xử lí, do đó sự truyền thông dữ liệu giữa các bộ xử lí đặc biệt là bộ xử lí đầu và
Hình 1.4 Mạng liên kết tuyến tính và mạng vòng
11
cuối sẽ bị chậm lại khi số bộ xử lí lớn.
Mạng liên kết vòng được tổ chức tương tự như mạng liên kết tuyến tính,
tuy nhiên, với mạng liên kết vòng, bộ xử lí đầu tiên và cuối cùng được kết nối với
nhau để tạo thành một vòng. Trong mạng liên kết vòng, sự trao đổi giữa các bộ xử
lí có thể thực hiện theo một chiều gọi là mạng đơn, hoặc theo cả hai chiều gọi là
mạng kép. Sự truyền thông trong mạng liên kết vòng, nhất là các bộ xử lí ở xa nhau
vẫn bị trễ.
1.1.3.2 Mạng liên kết lưới hai chiều (Two-Dimentional mesh)
Với mạng liên kết lưới hai chiều, mỗi bộ xử lí được liên kết với các láng
giềng: Trên, dưới, trái và phải. Mạng liên kết lưới hai chiều có hai dạng đó là lưới
Hình 1.5 Mạng liên kết lưới hai chiều
quay vòng lưới không quay vòng.
1.1.3.3 Mạng liên kết hình khối (Hypercube Network)
Giả sử có 𝑛 bộ xử lí, trong đó 𝑛 là lũy thừa của 2, 𝑛 = 2𝐷(𝐷 ≥ 0). Trong
mạng này, mỗi bộ xử lí sẽ liên kết với đúng 𝐷 bộ xử lí lân cận. Trong đó, chỉ số
của các bộ xử lí được đánh dưới dạng chuỗi nhị phân, hai bộ xử lí được kết nối với
12
nhau nếu chúng sai khác nhau đúng một bit.
Hình 1.6 Mạng liên kết khối
Trên đây là một số kiểu liên kết các bộ xử lí điển hình được sử dụng trong
các mô hình song song. Việc sử dụng kiến trúc song song nào và các thức liên kết
giữa các bộ xử lí song song ra sao cũng là một yếu tố quan trọng ảnh hưởng đến
khả năng xử lí bài toán.
1.1.4 Cơ sở đánh giá giải thuật song song
Việc sử dụng mô hình song song nào phù hợp với bài toán nào là một vấn
đề khá quan trọng trong xử lí song song bởi lẽ một thuật toán có thể phù hợp với
mô hình này nhưng chưa chắc đã là tốt với mô hình kia. Để đánh giá được một giải
thuật song song, thông thường chúng ta sẽ dựa vào ba tiêu chí: Thời gian thực hiện,
khả năng tăng tốc, độ hiệu quả của thuật toán [4].
1.1.4.1 Thời gian thực hiện
Khi tốc độ tính toán được coi là mục tiêu chủ yếu khi xây dựng các máy
tính song song, thì thời gian thực hiện là một độ đo quan trọng trong việc đánh giá
giải thuật. Nó được xác định như là thời gian giải thuật yêu cầu để giải quyết một
vấn đề trên máy tính song song, đó là khoảng thời gian kể từ thời điểm ban đầu
đến thời điểm kết thúc. Nếu các bộ xử lí khác nhau, tất cả không bắt đầu và kết
thúc đồng thời, thì thời gian thực hiện bằng thời gian kéo dài giữa thời điểm bộ xử
lí đầu tiên bắt đầu tính toán đến thời điểm cuối cùng bộ xử lí kết thúc tính toán.
Trước khi thực sự cài đặt một giải thuật song song hay tuần tự đều có sự phân tích
13
về lý thuyết, giải thuật cần bao nhiêu thời gian để giải quyết vấn đề tính toán đã
cho. Điều này thường được thực hiện bằng cách tính toán các thao tác cơ bản hoặc
các bước mà giải thuật thực hiện trong trường hợp xấu nhất. Số các bước như thế
là một hàm của kích thước đầu vào (input size). Các thao tác cơ bản có thể là phép
cộng, so sánh hoặc đổi chỗ, truyền dữ liệu. Mỗi thao tác như vậy yêu cầu một số
cố định các đơn vị thời gian trên máy tính đơn bộ xử lí truyền thống.
1.1.4.2 Hệ số tăng tốc và độ hiệu quả giải thuật
Thời gian thực hiện không hẳn là thước đo thuận tiện nhất để đánh giá độ
hiệu quả của thuật giải. Khi thời gian thực hiện có xu hướng biến đổi theo kích
thước bài toán, thời gian thực hiện phải được tiêu chuẩn hóa khi so sánh hiệu năng
giải thuật với kích thước bài toán khác nhau.
Hiệu quả của giải thuật được định nghĩa là phần thời gian mà bộ xử lí dùng
để thực hiện công việc có ích, chỉ ra mức độ hiệu quả của một giải thuật khi sử
dụng các tài nguyên tính toán của một máy tính song song theo hướng độc lập với
kích thước bài toán. Được xác định bằng công thức sau:
𝐸𝑝 = 𝑇𝑠 𝑝𝑇𝑝
Trong đó:
𝑇𝑠 là thời gian thực hiện thuật toán tuần tự trên 1 bộ xử lí
𝑇𝑝 là thời gian thực hiện thuật toán song song trên 𝑝 bộ xử lí
𝐸𝑝 là hệ số hiệu quả của giải thuật
𝑝 là số bộ xử lí
Một độ đo khác đánh giá được hiệu năng của giải thuật là khả năng tăng
tốc, đây là hệ số mà thời gian thực hiện được giảm đi khi thực hiện bài toán với 𝑝
14
bộ xử lí. Được xác định theo công thức sau:
𝑆𝑝 =
𝑇𝑠 𝑇𝑝
Trong đó:
𝑇𝑠 là thời gian thực hiện thuật toán tuần tự trên 1 bộ xử lí
𝑇𝑝 là thời gian thực hiện thuật toán song song trên 𝑝 bộ xử lí
𝑆𝑝 là hệ số tăng tốc. 𝑆𝑝 càng lớn thì thuật toán song song càng tốt.
Năm 1967 Amdahl đã đưa ra luật về giới hạn khả năng tăng tốc:
Luật Amdahl [4]: Giả sử 𝑓 là tỉ lệ cần phải thực hiện tính toán tuần tự, trong
đó, 0≤ 𝑓 ≤1. Khả năng tăng tốc tối đa 𝑆𝑝 đạt được bởi một máy tính song song có
=
𝑆𝑝 ≤
1 1−𝑓
𝑝 1 + (𝑝 − 1)𝑓
𝑓 +
𝑝
p bộ xử lí thực hiện tính toán là:
1.2 Tổng quan về bài toán sắp xếp
Sắp xếp là một bài toán quan trọng và phổ biến trong lĩnh vực tin học. Đó
là bài toán cơ bản được sử dụng bởi hầu hết các chương trình ứng dụng trên máy
tính [5]. Thực tế này có phần dễ hiểu vì việc xử lí trên dữ liệu đã được sắp xếp sẽ
trở nên dễ dàng hơn nhiều so với dữ liệu ngẫu nhiên không có thứ tự. Hơn nữa, có
nhiều giải thuật thao tác trên dữ liệu yêu cầu dữ liệu phải được sắp xếp trước khi
xử lí. Vì vậy, đã có nhiều thuật toán sắp xếp đã được nghiên cứu và phát triển.
1.2.1 Bài toán sắp xếp.
Sắp xếp là quá trình xử lí một danh sách các phần tử để đặt chúng theo một
thứ tự nào đó (tăng dần, giảm dần) dựa trên nội dung lưu trữ tại mỗi phần tử. Với
15
dữ liệu là kiểu số, bài toán sắp xếp đơn giản được phát biểu như sau: Cho một
mảng S có 𝑛 phần tử thuộc kiểu số, S={a1, a2,…, an} chưa có thứ tự theo giá trị
các phần tử. Yêu cầu chuyển mảng S đã cho thành mảng S’
’, a2
’,…, an
’| ai
’ (hoặc ai
’∈S, ai
’ ≤ aj
’ ≥aj
’) với 1≤ 𝑖 ≤ 𝑗 ≤ 𝑛}.
S’={a1
Ta có mảng S’ được sắp xếp từ mảng S.
Có nhiều giải thuật thực hiện việc sắp xếp mảng, chúng ta có thể phân loại
các giải thuật sắp xếp theo các tiêu chí dưới đây:
Xét về không gian sắp xếp, giải thuật sắp xếp được phân thành sắp xếp trong
và sắp xếp ngoài [3][4]. Với sắp xếp trong, số lượng các phần tử được sắp xếp là
đủ nhỏ để vừa với bộ nhớ chính, trong khi sắp xếp ngoài được sử dụng để sắp trên
các bộ nhớ bổ trợ như trên ổ đĩa lưu trữ, thường được sử dụng để sắp xếp trong
trường hợp số phần tử là quá lớn.
Xét về cách thức thực hiện sắp xếp, có thể phân thành hai loại là sắp xếp
dựa trên sự so sánh và sắp xếp không dựa trên sự so sánh [3]. Thuật toán sắp xếp
dựa trên sự so sánh sắp xếp một chuỗi các phần tử bằng cách lặp lại phép so sánh
các cặp các phần tử, nếu chúng không theo thứ tự thì đổi chỗ chúng cho nhau. Các
phép tính cơ bản của sắp xếp dựa trên sự so sánh được gọi là “so sánh- đổi chỗ”.
Khi xây dựng thuật toán sắp xếp kiểu này, chúng ta luôn phải đặt ra mục tiêu là
giảm thiểu tối đa số phép “so sánh và đổi chỗ” để tăng hiệu quả của các thuật toán
sắp xếp. Với một tư tưởng khác, các thuật toán sắp xếp không dựa trên sự so sánh
thực hiện việc sắp xếp bằng cách sử dụng sự hiểu biết cụ thể về các thuộc tính của
các phần tử (chẳng hạn như sự biểu diễn các phần tử dưới dạng nhị phân…).
Phổ biến hơn và thường được sử dụng hơn đó là phân loại các thuật toán
sắp xếp dựa trên sự phân tích về độ phức tạp của các thuật toán. Dựa vào độ phức
tạp các thuật toán sắp xếp có thể được chia thành ba lớp sau: Lớp thuật toán có độ
phức tạp 𝑂(𝑛2) bao gồm thuật toán sắp xếp chọn (SelectSort), thuật toán sắp xếp
chèn (InsertSort), thuật toán sắp xếp nổi bọt (BubbleSort), thuật toán sắp xếp
16
Gnome, thuật toán ShellSort. Thứ hai là lớp thuật toán có độ phức tạp
𝑂(𝑛𝑙𝑜𝑔𝑛) bao gồm các thuật toán sắp xếp nhanh (QuickSort), thuật toán sắp xếp
trộn (MergeSort), thuật toán sắp xếp vun đống (HeapSort), thuật toán sắp xếp chẵn
lẻ (OddEvenSort)… và cuối cùng là lớp thuật toán có độ phức tạp thấp, sắp xếp
trên dữ liệu đặc biệt như thuật toán sắp xếp CountingSort 𝑂(𝑛 ∗ 𝑚),
RadixSort 𝑂(𝑛 + 𝑚).
Cùng với mục đích sắp xếp như nhau, nhưng có nhiều phương pháp giải
quyết khác nhau như vậy. Do đó, nếu chỉ dựa vào độ phức tạp của thuật toán để
đánh giá thuật toán này là tốt hơn thuật toán kia về mọi mặt là không nên. Việc
chọn một thuật toán sắp xếp thích hợp cho phù hợp với từng yêu cầu, từng điều
kiện cụ thể là kỹ năng của người lập trình. Những thuật toán có độ phức tạp
𝑂(𝑛2) thì chỉ nên áp dụng trong chương trình có ít lần sắp xếp và với kích thước
nhỏ. Về tốc độ, có thể nói BubbleSort luôn là tồi nhất, nhưng mã lệnh của nó thì
lại đơn giản dễ cài đặt. Trong những thuật toán có độ phức tạp O(n2), InsertionSort
tỏ ra nhanh hơn những phương pháp còn lại mã lệnh cũng tương đối đơn giản. Với
n là nhỏ, việc chọn ra m khóa nhỏ nhất bởi SelectionSort có thể thực hiện dễ dàng
chứ không cần phải sắp xếp lại toàn bộ như InsertionSort.
Các thuật toán CountingSort và RadixSort nên được tận dụng trong trường
hợp các khóa sắp xếp là số tự nhiên (hay là một kiểu dữ liệu có thể quy ra thành
các số tự nhiên) bởi những thuật toán này có tốc độ rất cao.
QuickSort, HeapSort, MergeSort và ShellSort là những thuật toán sắp xếp
tổng quát, dãy khóa thuộc kiểu dữ liệu có thứ tự nào cũng có thể áp dụng được chứ
không nhất thiết phải là các số. QuickSort gặp nhược điểm trong những trường
hợp suy biến nhưng xác suất sảy ra trường hợp này thường nhỏ. HeapSort thì mã
lệnh hơi phức tạp và khó cài đặt hơn, nhưng nếu cần chọn ra m khóa lớn nhất trong
dãy khóa thì HeapSort sẽ không phải sắp lại toàn bộ dãy. MergeSort phải đòi hỏi
thêm một không gian nhớ phụ, nên áp dụng nó trong trường hợp sắp xếp trên file.
Còn Shellsort thì hơi khó trong việc đánh giá về thời gian thực thi, nó là sửa đổi
17
của thuật toán sắp xếp chèn nhưng lại có tốc độ tốt, mã lệnh đơn giản và lượng bộ
nhớ cần huy động rất ít. Tuy nhiên, những nhược điểm của bốn phương pháp này
quá nhỏ so với ưu điểm chung của chúng là nhanh và hiệu quả cao. Hơn nữa, chúng
được đánh giá cao không chỉ vì tính tổng quát và tốc độ nhanh, mà còn là kết quả
của những các tiếp cận khoa học đối với bài toán sắp xếp [2].
1.2.2 Các cấu trúc dữ liệu cho bài toán sắp xếp
Việc tổ chức dữ liệu cho các bài toán sắp xếp cũng là một trong các vấn đề
quan trọng cần được quan tâm để hỗ trợ nâng cao hiệu quả thuật toán khi thực hiện.
Thông thường, một tập các đối tượng cần sắp xếp là tập các bản ghi, mỗi bản ghi
bao gồm một số trường khác nhau. Nhưng không phải toàn bộ các trường dữ liệu
trong các bản ghi đều được xem xét đến trong quá trình sắp xếp mà chỉ là một
trường nào đó (hay một vài trường nào đó) được chú ý tới. Trường như vậy được
gọi là trường khóa. Việc sắp xếp sẽ được tiến hành dựa vào giá trị của khóa này.
Khi sắp xếp, các bản ghi trong bảng sẽ được đặt lại vào các vị trí sao cho giá trị
khóa tương ứng với chúng có đúng thứ tự đã ấn định.
Vì kích thước của toàn bản ghi có thể rất lớn, nên nếu việc sắp xếp thực
hiện trực tiếp trên các bản ghi sẽ đòi hỏi sự chuyển đổi vị trí của các bản ghi, kéo
theo việc thường xuyên phải di chuyển, copy những vùng nhớ lớn, gây ra tổn phí
khá nhiều thời gian. Để khắc phục tình trạng này, ta xây dựng một bảng khoá, mỗi
bản ghi trong bảng ban đầu sẽ tương ứng với một bản ghi trong bảng khóa. Bảng
khóa cũng gồm các bản ghi nhưng mỗi bản ghi chỉ gồm có hai trường: trường khóa
và trường chứa liên kết tới một bản ghi ban đầu, tức là chứa một thông tin đủ để
biết bản ghi tương ứng với nó trong bảng ban đầu là bản ghi nào. Sau đó việc sắp
xếp được thực hiện trực tiếp trên bảng khóa, trong quá trình sắp xếp, bảng chính
không hề bị ảnh hưởng gì, việc truy cập vào bảng ghi nào đó của bảng chính vẫn
có thể được thực hiện bằng cách dựa vào trường liên kết của bản ghi tương ứng
thuộc bảng khóa [2]. Do khóa có vai trò đặc biệt như vậy nên sau này, khi trình
bày các giải thuật, ta sẽ coi khóa như đại diện cho các bản ghi và để cho đơn giản,
18
ta chỉ nói tới giá trị của khóa mà thôi.
Với tập hợp các bản ghi này, ta có thể sử dụng các danh sách liên kết để
liên kết các bản ghi. Với hầu hết các thuật toán sắp xếp ta thường sử dụng phương
pháp này, tuy nhiên cũng có những thuật toán sắp xếp rất hiệu quả lại sử dụng
phương pháp dùng cấu trúc của cây để liên kết các bản ghi, khi đó mỗi bản ghi sẽ
là một nút của cây. Song dù sử dụng cấu trúc nào đi nữa thì mục tiêu mà các thuật
toán hướng đến vẫn là đơn giản cho lập trình và hiệu quả về thời gian.
Mục tiếp theo đây là tổng hợp một số các thuật toán sắp xếp cơ bản đã được
nghiên cứu trong tin học, được phân loại dựa vào độ phức tạp của thuật toán.
1.2.3 Phân lớp các thuật toán sắp xếp dựa trên độ phức tạp
1.2.3.1 Lớp thuật toán có độ phức tạp O(n2)
a. Thuật toán sắp xếp chọn (SelectionSort)
Đây là thuật toán sắp xếp khá đơn giản. Tại mỗi bước lặp luôn chọn ra phần
tử nhỏ nhất trong danh sách bằng cách tìm kiếm tuyến tính và hoán đổi vị trí phần
tử đó với phần tử đầu tiên trong danh sách, sau đó tìm phần tử nhỏ nhất thứ hai
bằng cách duyệt trong phạm vi các phần tử còn lại trừ phần tử đầu đã xếp xong và
if A[j]< A[min] min=j;
cứ như vậy cho đến khi hết các phần tử để duyệt.
void Selection(A[], n) { For i=1 n { min = i; for j=i+1 n if min ≠ i Exchange A[min] cho A[i]; }
}
Có thể nói thuật toán sắp xếp chọn là thuật toán duy nhất xét về thời gian
chạy so với các thuật toán khác không bị ảnh hưởng bởi tình trạng thứ tự của dữ
liệu đầu vào, nó luôn thực hiện cùng số lượng thao tác do cấu trúc đơn giản của
mình. Thuật toán sắp xếp chọn có độ phức tạp cỡ 𝑂(𝑛2)[2].
19
b. Thuật toán sắp xếp chèn (InsertionSort)
Thuật toán sắp xếp chèn làm việc giống hệt tên gọi của nó. Nó thực hiện
việc quét danh sách, với mỗi phẩn tử, thủ tục kiểm tra và chèn phần tử đó vào vị
trí thích hợp trong danh sách đích (chứa các phần tử đứng trước nó đã được sắp
xếp), được tiến hành bằng cách dịch chuyển phần tử hiện tại đang xét tuần tự qua
những phần tử ở vùng dữ liệu phía trước đã được sắp xếp, phép hoán vị nó với
phần tử liền kề được thực hiện một cách lặp lại cho đến khi đến được vị trí thích
hợp.
Với mỗi phần tử, thuật toán sắp xếp chèn thực hiện so sánh với các phần tử
trước nó nên tối đa số lần để duyệt dữ liệu là n. Vì vậy cũng giống với thuật toán
sắp xếp chọn, độ phức tạp của thuật toán sắp xếp chèn cũng là 𝑂(𝑛2)[2].
void InsertionSort (A[],n) { for i=1 n { j=i; while (j>0 && A[j-1] > A[j])
{ exchange (A[j], A[j-1])
j--; }
}
}
c. Thuật toán Shellsort
Với InsertionSort, ta thấy sẽ rất hiệu quả nếu dữ liệu đầu vào hầu như đã
được sắp xếp (đã được sắp xếp trong từng khoảng cục bộ). Tuy nhiên, nó lại hoạt
động kém hiệu quả vì nó di chuyển các phần tử mỗi lần chỉ một vị trí. Shellsort là
sự cải tiến của InsertionSort.
Thuật toán tạo ra nhiều luồng chạy duyệt qua danh sách, mỗi lần sắp xếp
một số trong những tập dữ liệu được định kích cỡ như nhau bằng cách dùng
InsertionSort. Sau mỗi lần duyệt qua hết bộ dữ liệu thông qua các phân đoạn (có
kích thước giảm dần ≥1), kích thước của tập được sắp xếp trở nên lớn hơn cho tới
20
khi nó chứa toàn bộ danh sách.
void Shellsort(A[],n){ i,j,h, tmp: integer; h= n/2;
while h≠ 0 { for i=h+1 n {
tmp=A[i];j=i-h; while (j>0 && A[j]>tmp){
A[j+h]=A[j];
Shellsort là thuật toán có độ phức tạp 𝑂(𝑛2)và là thuật toán hiệu quả nhất
trong lớp thuật toán có độ phức tạp 𝑂(𝑛2) [2].
d. Thuật toán sắp xếp nổi bọt (BubbleSort)
Thuật toán sắp xếp nổi bọt là một phương pháp sắp xếp đơn giản. Dãy khóa
sẽ được duyệt từ cuối dãy về đến 𝐴[1], nếu gặp hai khóa kế cận bị ngược thứ tự
thì đổi chỗ của chúng cho nhau, khóa nhỏ nhất trong dãy khóa sẽ được chuyển về
vị trí đầu tiên, vấn đề trở thành sắp xếp dãy khóa từ 𝐴[2] đến 𝐴[𝑛].
void BubbleSort(A[],n) { for i=2 n {
for j=ni {
if A[j] < A[j-1]
exchange (A[j], A[j-1]);
}
}
Qua thuật toán ta nhận thấy rằng, sau lần duyệt toàn bộ dữ liệu lần thứ nhất,
chúng ta chắc chắn có phần tử nhỏ nhất nằm đầu, lần thứ hai phần tử nhỏ nhất liền
kề sẽ nằm kế đầu, cứ như vậy cho đến khi toàn bộ dữ liệu được sắp xếp. Do đó
tổng số lần lặp xử lí cho thuật toán này sẽ là 𝑛2. Vì vậy, độ phức tạp của thuật toán
nổi bọt là 𝑂(𝑛2) [2].
21
e. Thuật toán sắp xếp hoán vị chẵn lẻ (OddEvenSort)
Thuật toán sắp xếp hoán vị chẵn lẻ là một biến thể của thuật toán nổi bọt
𝑛 cho phép sắp xếp 𝑛 phần tử trong 𝑛 pha, mỗi pha yêu cầu thực hiện 2
phép so sánh-
đổi chỗ[3]. Thuật toán kết hợp thực hiện giữa hai pha là pha chẵn và pha lẻ. Trong
pha chẵn, các phần tử ở vị trí chẵn sẽ so sánh với phần tử liền kề bên phải nó, nếu
không đúng thứ tự thì chúng sẽ được đổi chỗ cho nhau. Tương tự với pha lẻ. Thuật
toán dừng nếu trong hai pha liên tiếp không có phần tử nào bị đổi chỗ. Thuật toán
có độ phức tạp là 𝑂(𝑛2)[2].
void OddEvenSort(A[],n) {
compare-exchange( A[2j], A[2j+1]);
for (j =0; j<= n/2-1; j++) if i chẵn for (j=1; j<=n/2-1; j++)
compare- exchange( A[2j], [2j+1]);}
int i,j, n; for (i=1; i<=n; i++){
if i lẻ
}
f. Thuật toán sắp xếp Gnome
Cùng với sắp xếp nổi bọt, sắp xếp chèn, Gnome là một trong những thuật
toán sắp xếp ngắn gọn và đơn giản. Sự khác biệt có thể đôi khi là đáng giá của
thuật toán Gnome so với các thuật toán khác đó là nó chỉ sử dụng vòng lặp duy
nhất, không có cặp lồng nhau. Điều này giúp Gnome nhìn rõ ràng hơn và trong
thực tế nhiều trường hợp, nó sẽ được xử lí nhanh hơn do dễ dàng áp dụng các kỹ
thuật triển khai tối ưu.
Tư tưởng của Gnome đơn giản, bắt đầu từ vị trí thứ 2 của dãy giá trị cần sắp
xếp tăng dần, so sánh giá trị phần tử ở vị trí hiện tại với phần tử trước nó, nếu nhỏ
hơn thì hoán vị rồi lùi lại một vị trí (giới hạn biên là vị trí xuất phát), nếu lớn hơn
thì tiến lên một vị trí. Cứ như vậy cho tới khi tiến tới vị trí cuối cùng của dãy giá
trị.
void Gnome(A[],n) { int i=1;
22
i++;
while (i< n) {if (A[i]>=A[i-1]) else
{
exchange (A[i], A[i-1]); if(i>1)
Gnome là thuật toán sắp xếp nằm trong lớp thuật toán có độ phức tạp 𝑂(𝑛2)[2].
1.2.3.2 Lớp thuật toán có độ phức tạp O(nlogn)
a.Thuật toán sắp xếp nhanh (QuickSort)
QuickSort là một trong những thuật toán hiệu quả ở cả hai phương diện cài
đặt và thời gian thực hiện. Thuật toán này phù hợp trong việc sắp xếp với lượng
dữ liệu lớn.
Ý tưởng của thuật toán như sau: Chọn một phần tử trong mảng làm phần
tử chốt, các phần tử trong mảng sẽ được chia thành hai phần, một phần chỉ chứa
những phần tử lớn hơn chốt, và một phần chỉ chứa những phần tử nhỏ hơn chốt.
Sau đó thực hiện việc sắp xếp hai phần này theo cách tương tự bằng thủ tục đệ quy,
chúng ta sẽ thu được mảng sắp xếp có thứ tự.
Trong lược đồ trên, phần tử chốt được chọn là phần tử nằm ở vị trí giữa
mảng. Có thể có một số cách chọn phần tử chốt khác nhau như chọn phần tử ở đầu
hoặc cuối mảng hoặc phần tử trung bình. Trong trường hợp trung bình Quicksort
có độ phức tạp là 𝑂(𝑛𝑙𝑜𝑔𝑛), tuy nhiên trong trường hợp xấu độ phức tạp của
void quickSort(int A[], int left, int right) {
int i = left, j = right; int pivot = A[(left + right) / 2]; /* phân đoạn */ while (i <= j)
{ while (A[i] < pivot) i++;
while (A[j] > pivot)j--; if (i <= j)
{
23
Exchange(A[i], A[j]); i++; j--; } }
QuickSort có thể là 𝑂(𝑛2) [2].
b. Thuật toán sắp xếp hòa nhập (MergeSort)
Merge sort chia mảng cần được sắp xếp thành hai nửa bằng nhau và đặt
chúng vào vùng chứa dữ liệu riêng biệt. Mỗi mảng dữ liệu được sắp xếp một cách
đệ quy, sau đó trộn lẫn vào nhau tạo thành danh sách dữ liệu được sắp xếp cuối
cùng.
void MergeSort (A,B,p,q);
{ If p
MergeSort (A,B1,p,t);
MergeSort (A,B2,t+1,q);
Merge(B1,B2,B,t-p+1,q-t);
}
}
void Merge (X,Y,Z,m,n);
{ i=1 ; j=1 ; k=1 ;
{ Z[k]= X[i]; i=i+1;}
while (im //Nối phần còn lại của Y vào Z
else //Nối phần còn lại của X vào Z
}
24
Giống như Quicksort, Merge sort là phương pháp dựa trên đệ quy, điều này
sẽ là lựa chọn không tốt với các ứng dụng chạy trên máy tính giới hạn về bộ nhớ.
MergeSort có độ phức tạp là 𝑂(𝑛𝑙𝑜𝑔𝑛) [2].
c. Thuật toán sắp vun đống (HeapSort)
Đống là một dạng cây nhị phân hoàn chỉnh đặc biệt mà giá trị lưu tại mọi
nút có độ ưu tiên cao hơn hay bằng giá trị lưu trong hai nút con của nó. Trong thuật
toán sắp xếp kiểu vun đống, ta coi quan hệ “ưu tiên hơn hay bằng” là quan hệ “lớn
hơn hoặc bằng”: “≥” [2].
Thuật toán sắp xếp vun đống hoạt động cũng như tên gọi của nó, bắt đầu
bằng việc xây dựng một “đống” của tập dữ liệu, sau đó loại phần tử lớn nhất và
đặt nó vào vị trí cuối cùng của mảng. Sau việc xóa phần tử lớn nhất, nó tái cấu trúc
của đống và di chuyển phần tử lớn nhất kế tiếp còn lại và đặt nó vào vị trí ở kế
cuối của mảng được sắp xếp. Thao tác này được lặp lại cho tới khi không còn phần
tử bên trái trong đống và mảng đã được sắp xếp đầy.
Thuật toán sắp xếp vun đống có độ phức tạp 𝑂(𝑛𝑙𝑜𝑔𝑛) [2]. Dưới đây là
lược đồ của thuật toán sắp xếp vun đống.
void HeapSort(int A[], int n){
int i;
ShipDown( A, i, n);
exchange (A[0],A[i]);
ShipDown(A, 0, i-1);
for i= n/2 -1 0
for i= n-1 1{
}
}
void ShipDown(int A[], int root, int bottom){
25
maxchild = root*2;
maxchild = root*2+1;
else
int done, maxchild;
done=0;
while ((root*2<= bottom) && (!done)){
if(root*2 == bottom) maxchild = root*2;
else if ( A[root*2] > A[root*2+1])
if (A[root]< A[maxchild]{
exchange(A[root], A[maxchild]);
1.2.3.2 Thuật toán sắp xếp có độ phức tạp thấp với dữ liệu đặc biệt
a. Thuật toán sắp xếp Counting
Cho một mảng 𝐴 có 𝑛 số nguyên, mỗi số đều nằm trong vùng giá trị (0 . . 𝐾).
Thuật toán sắp xếp đếm sử dụng một mảng 𝐶 chứa giá trị của các bộ đếm, kết quả
đầu ra được lưu trữ trong một mảng phụ 𝐶.
Ý tưởng của thuật toán: Với mỗi số 𝑖 trong vùng giá trị từ (0 . . 𝐾), đếm số
lần xuất hiện của 𝑖 ở trong mảng 𝐴 và sau đó lưu giá trị đó và 𝐶[𝑖]. Sau khi kết
thúc, việc sắp xếp được thực hiện bằng cách liệt kê sự xuất hiện của các giá trị từ
(0 . . 𝐾) dựa vào các giá trị 𝐶[𝑖]. Lần lượt 𝐶[0] số 0, rồi đến 𝐶[1] số 1 … và
𝐶[𝐾] số 𝐾. Thuật toán CountingSort hiệu quả cho việc sắp xếp mảng các số nguyên
khi mà độ dài 𝑛 của mảng là lớn hơn nhiều so với giá trị lớn nhất của mảng.
void CountingSort(int A[],int B[], int C[], int k)
{
for i=0k
C[i]=0;
for j=1 length[A]
C[A[j]]= C[A[j]]+1;//Đếm số lần xuất hiện A[j]
for i=2k
C[i]=C[i]+C[i-1];//C[i] bây giờ là số phần tử ≤ 𝑖
for j= length[A] 1
{B[C[A[j]]]= A[j];
C[A[j]]= C[A[j]]-1;}
26
}
Thuật toán sắp xếp đếm CountingSort có độ phức tạp là 𝑂(𝑛 + 𝑘) [2].
b. Thuật toán sắp xếp theo cơ số (RadixSort)
Kế thừa ý tưởng của Quicksort, tại bước phân đoạn thuật toán phân đoạn
đoạn đang xét thành hai đoạn thỏa mãn mỗi khóa trong đoạn đầu nhỏ hơn hoặc
bằng mọi khóa trong đoạn sau và thực hiện tương tự trên hai đoạn mới tạo ra, việc
phân đoạn được tiến hành với sự so sánh các khóa với giá trị một khóa chốt. Với
Radixsort, khi sắp xếp mảng các số nguyên mà mỗi số nguyên được biểu diễn dưới
dạng nhị phân có độ dài 𝑧 bit đánh số từ bit 0 (bit ở hàng đơn vị) tới bit 𝑧 − 1 (bit
cao nhất).
Tại bước phân đoạn, dãy khóa từ 𝐴[1] tới 𝐴[𝑛] ta có thể đưa những khóa
có bit cao nhất là 0 được đưa về vị trí đầu dãy, những khóa có bit cao nhất là 1 về
cuối dãy. Hiển nhiên, những khóa bắt đầu bằng bit 0 phải có giá trị nhỏ hơn những
khóa bắt đầu bằng bit 1. Tiếp tục quá trình phân đoạn với hai đoạn dãy khóa: Đoạn
gồm các khóa có bit cao nhất là 0 và đoạn gồm các khóa có bit cao nhất là 1. Với
những khóa thuộc cùng một đoạn thì bit cao nhất giống nhau, ta có thể áp dụng
quá trình phân đoạn tương tự trên theo bit thứ 𝑧 − 2 và cứ tiếp tục như vậy. Quá
trình phân đoạn kết thúc nếu như đoạn đang xét là rỗng hay ta đã tiến hành phân
đoạn đến tận bit đơn vị tức là tất cả các khóa thuộc một trong hai đoạn mới tạo ra
đều có bit đơn vị bằng nhau [2].
void RadixBinarySort()
partition(L,R,b: integer){
if L>=R
exit;
exchange (A[i], A[j]);
while (i
partition(L,j-1,b-1);
partition(j, R, b-1);
27
{
}
i=L; j=R;
do
while i==j;
if (Bit b của A[i]=0) j=j++;
if b>0
}
partition(1, n, z-1);//z là độ dài chuỗi nhị phân
Với 𝑛 là số phần tử cần sắp xếp và 𝑧 là chiều dài của chuỗi nhị phân biểu
diễn từng phần tử thì khi đó thuật toán có độ phức tạp là 𝑂(𝑛. 𝑧) [2].
1.3 Kết luận chương
Như vậy trong chương 1, phần đầu của chương đã trình bày một cách tổng
quan về xử lí song song và các mô hình song song cơ bản. Chúng ta hình dung
được phần nào về xử lí song song, tầm quan trọng của việc song song hóa một bài
toán và cách thức để đánh giá một giải thuật song song cho một bài toán cụ thể.
Phần tiếp theo của chương đã hệ thống hóa lại các thuật toán sắp xếp tuần
tự, đây là những thuật toán phổ biến và quen thuộc. Mỗi thuật toán đều thể hiện rõ
trên hai khía cạnh là tư tưởng thuật toán và độ phức tạp của thuật toán.
Việc cải tiến và song song hóa một số thuật toán đã được giới thiệu ở trên
28
sẽ được nghiên cứu và trình bày trong chương 2.
CHƯƠNG 2. MỘT SỐ THUẬT TOÁN SONG SONG CHO
BÀI TOÁN SẮP XẾP
2.1 Chiến lược song song cho bài toán sắp xếp
Với việc xử lý tuần tự, chương trình thực thi trên một bộ xử lí đơn, tại một
thời điểm chỉ có duy nhất một tác vụ được thực hiện, điều này phần nào làm cho
thời gian thực hiện chương trình lâu hơn so với việc thực thi đồng thời nhiều tác
vụ cùng một lúc. Do đó, việc song song hóa các thuật toán sắp xếp một cách hợp
lý sẽ giúp giảm đáng kể thời gian của việc sắp xếp. Nếu đầu vào của bài toán được
chia thành nhiều phần và phân cho các CPU và mỗi CPU thực thi trên một mảng
con và có sự phối hợp hợp lí thì khi đó, thời gian cần thiết để sắp xếp mảng sẽ có
khả năng giảm đi nhiều.
Để thực hiện song song hóa một thuật toán sắp xếp, chúng ta có thể thực
hiện theo ba phương pháp:
Phương pháp đầu tiên là phát triển các thuật toán song song từ các thuật
toán tuần tự có sẵn. Đây là cách làm tương đối đơn giản bởi vì thuật toán tuần tự
là đã có sẵn, việc phân tích thuật toán tuần tự để chuyển sang thuật toán song song
sẽ dễ dàng hơn nhiều. Tuy nhiên, không phải thuật toán tuần tự nào cũng có thể
song song hóa được, vì có một số thuật toán, vốn bản thân nó luôn luôn là tuần tự,
tức là ta không thể chia cắt bài toán ra thành các tiến trình độc lập nhau để phân
chia cho các bộ xử lí thực thi đồng thời.
Phương pháp thứ hai là phát triển một thuật toán song song từ một thuật
toán song song đã có. Thực tế, để có một chương trình đạt hiệu quả cao cần phải
trải qua các quá trình thay đổi và chỉnh sửa cho phù hợp. Do đó, ta có thể dựa vào
thuật toán sắp xếp song song đã có để có thể phát triển thành thuật toán song song
mới không những rút ngắn thời gian thực hiện mà còn để phù hợp hơn với một số
hệ thống song song mới.
Phương pháp thứ ba là xây dựng một thuật toán song song hoàn toàn mới,
điều này có nghĩa là chúng ta bắt đầu ý tưởng song song mà không phụ thuộc vào
29
thuật toán tuần tự đã có cũng như không phát triển từ những thuật toán song song
đã làm. Để làm được điều này sẽ mất nhiều thời gian và cần phải có trình độ và sự
chuyên sâu về xử lí song song.
Qua đó, để xây dựng một giải thuật song song nói chung cũng như song
song hóa cho bài toán sắp xếp nói riêng có thể dựa vào ba phương pháp trên. Nhưng
dù theo phương pháp nào, thì mục đích cuối cùng cần đạt được đó là thuật toán
song song cần phải cải thiện được thời gian thực hiện chương trình so với thuật
toán tuần tự. Phần dưới đây sẽ trình bày chi tiết về các thuật toán sắp xếp song
song phát triển dựa trên ba phương pháp nêu trên.
2.2 Thuật toán sắp xếp song song phát triển dựa trên thuật toán tuần tự
Nội dung phần này sẽ trình bày hai thuật toán sắp xếp song song được xây
dựng từ thuật toán tuần tự có khả năng song song hóa cao đó là thuật toán
OddEvenSort, thuật toán ParallelQuickSort cùng với hai thuật toán trên là thuật
toán Shellsort là sự cải thiện của thuật toán OddEvenSort và thuật toán
HyperQuickSort thuật toán song song được phát triển từ thuật toán song song
ParallelQuickSort.
2.2.1 Thuật toán sắp xếp hoán vị chẵn lẻ (OddEvenSort)
2.2.1.1 Tư tưởng thuật toán
Cho mảng 𝐴[𝑛]. Giả sử hệ thống sử dụng 𝑛 bộ xử lí, mỗi bộ xử lí mang một
chỉ số khác nhau 𝑝𝑖 (𝑖 = 0. . 𝑛 − 1), khi đó chỉ số của các bộ xử lí phân các bộ xử
lí thành hai loại đó là các bộ xử lí có chỉ số chẵn và các bộ xử lí có chỉ số lẻ [3].
Quá trình phân chia dữ liệu cho các bộ xử lí: Phân chia phần tử của mảng 𝐴
ban đầu cho các bộ xử lí. Để đơn giản, bộ xử lí 𝑝𝑖 sẽ nhận phần tử thứ 𝐴[𝑖] trong
mảng.
Quá trình thực hiện thuật toán: Thuật toán song song sẽ trải qua tối đa n pha
(0 . . 𝑛 − 1) chẵn lẻ xen kẽ nhau.
Trong pha chẵn, các bộ xử lí mang chỉ số chẵn sẽ thực hiện so sánh phần tử
30
của nó với phần tử nằm trong bộ xử lí có chỉ số lẻ nằm liền bên phải của nó (𝑝0,
𝑝1), (𝑝2, 𝑝3)…, nếu hai phần tử trong các cặp xử lí này không đúng thứ tự cần sắp
xếp, khi đó hai bộ xử lí sẽ tráo đổi hai phần tử của chúng cho nhau.
Tương tự, trong pha lẻ, các bộ xử lí mang chỉ số lẻ sẽ so sánh phần tử của nó
với phần tử nằm trong bộ xử lí có chỉ số chẵn liền kề bên phải của nó (𝑝1, 𝑝2), (𝑝3,
𝑝4)… nếu hai phần tử trong các cặp xử lí này không đúng thứ tự cần sắp xếp, khi
đó hai bộ xử lí sẽ tráo đổi hai phần tử của chúng cho nhau. Thuật toán dừng nếu
trong hai pha liên tiếp không có cặp nào được đổi chỗ cho nhau [3].
2.2.1.2 Độ phức tạp thuật toán
Trong mỗi pha của thuật toán, các bộ xử lí với nhãn chẵn hoặc lẻ thực thi một
𝑛
bước so sánh – đổi chỗ với bộ xử lí bên phải của nó. Và mỗi yêu cầu đó tốn 𝑂(1)
2
đơn vị thời gian, cần có yêu cầu so sánh. Tổng số pha cần thực hiện là 𝑛. Do đó,
thời gian xây dựng cho giải thuật song song là 𝑂(𝑛2) [3].
Thuật toán thực hiện tối đa 𝑛 pha, độ phức tạp về thời gian sẽ là 𝑂(𝑛2). Tuy
nhiên đó là độ phức tạp thời gian khi chúng ta có đủ 𝑛 bộ xử lí. Khi số phần tử của
mảng cần sắp xếp là rất lớn thì chi phí tài nguyên này khó có thể đáp ứng được.
Dưới đây, chúng ta sẽ xem xét thuật toán khi thực hiện với 𝑝 bộ xử lí 𝑝 < 𝑛.
Ban đầu, chia mảng gồm 𝑛 phần tử ra thành 𝑝 phần. Mỗi bộ xử lí được nhận
𝑛
một khối gồm
𝑝
phần tử, các bộ xử lí sẽ sắp xếp nội bộ các phần tử mà chúng được
𝑛
giao. Thời gian để sắp xếp các khối ban đầu này (sử dụng thuật toán Quicksort
𝑝
𝑝
𝑝
log ). Sau đó, quá trình xử lí thực hiện 𝑝 pha làm việc hoặc Merge sort) là 𝑂 (𝑛
𝑝
2
( pha lẻ và pha chẵn), mỗi pha sẽ tiến hành các phép so sánh-phân chia. Đến
2
pha cuối cùng, danh sách được sắp xếp [3]. Trong mỗi pha, mất 𝑂 (𝑛
𝑝
) phép so
) thời gian để gửi truyền sánh để trộn hai khối lại với nhau theo thứ tự, và mất 𝑂 (𝑛
𝑝
31
thông giữa bộ xử lí.
2.2.1.3 Ví dụ minh họa
Cho mảng A={4, 2, 7, 8, 5, 1, 3, 6} và số bộ xử lí 𝑛=8. Ban đầu, các phần
tử trong mảng A lần lượt được phân chia cho các bộ xử lí (𝑝0 … 𝑝7). Thuật toán
trải qua 7 pha làm việc dưới đây.
Pha
P0 P1 P2 P3 P4 P5 P6 P7
4 ↔ 2 7 − 8 5 ↔ 1 3 − 6 0
1 2 4 − 7 8 ↔ 1 5 ↔ 3 6
2 2 4 − 7 ↔ 1 8 ↔ 3 5 − 6
3 2 4 ↔ 1 7 ↔ 3 8 ↔ 5 6
4 2 ↔ 1 4 ↔ 3 7 ↔ 5 8 ↔ 6
5 1 2 − 3 4 − 7 ↔ 6 8 5
6 1 2 − 3 − 4 − 6 7 − 8 5
7 1 2 − 3 4 − 6 − 7 8 5
2.2.2 Thuật toán Shellsort.
Thuật toán sắp xếp song song dựa trên hoán vị chẵn lẻ ở trên tồn tại nhược
điểm đó là tại mỗi vòng lặp và tại một thời điểm các phần tử chỉ được đổi chỗ đến
một vị trí gần với nó mà thôi (từ BXL 𝑝𝑖 sang BXL 𝑝𝑖+1). Nhưng thông thường,
có một số phần tử trong mảng chúng có khoảng cách so với vị trí đúng của chúng
là khá xa (chẳng hạn như phần tử 𝑎 nằm ở bộ xử lí 𝑝0 nhưng vị trí đúng của chúng
lại là ở bộ xử lí 𝑝𝑖). Thuật toán ShellSort phần nào cải thiện được nhược điểm của
32
OddEvenSort.
Thuật toán song song Shellsort được xây dựng trên mô hình mạng
Hypercube-𝐷 chiều [4]. Gọi 𝑝 là số bộ xử lí của hệ thống với 𝑝 là lũy thừa của 2,
𝑝 = 2𝐷(𝐷 là số chiều của mạng).
2.2.2.1 Tư tưởng thuật toán
𝑛
Quá trình phân chia dữ liệu cho các bộ xử lí: Chia 𝑛 phần tử của mảng A
𝑝
cho p bộ xử lí, mỗi bộ xử lí sẽ chứa phần tử.
Quá trình thực hiện thuật toán: Ban đầu, mỗi bộ xử lí sử dụng một thuật
toán sắp xếp tuần tự hiệu quả (chẳng hạn Quicksort) để sắp xếp nội bộ các phần tử
của chúng theo thứ tự. Thuật toán tiếp tục trải qua hai giai đoạn:
Giai đoạn 1: Thực hiện 𝐷 bước lặp, tại mỗi bước lặp, tiến hành các phép so
sánh và phân chia chọn ra các bộ xử lí để ghép cặp trên mạng Hypercuber. Các bộ
xử lí được ghép cặp với nhau theo quy luật sau: Tại bước lặp thứ 𝑖 (1 ≤ 𝑖 ≤ 𝐷) các
bộ xử lí khác nhau duy nhất ở bit thứ 𝑖 được lựa chọn để so sánh và trao đổi các
phần tử với nhau (chẳng hạn với 𝑖 = 1 thì các cặp xử lí có dạng biểu diễn nhị phân
(000, 100), (001, 101), (010,110), (011, 111)).
Việc so sánh và trao đổi phần tử này có thể sử dụng một thuật toán tuần tự
hiệu quả để trộn các phần tử trong hai bộ xử lí lại với nhau, sau đó phân chia lại
các phần tử thành hai phần và chuyển về các bộ xử lí sao cho thỏa mãn điều kiện:
Các bộ xử lí có bit thứ 𝑖 =0 sẽ chứa các phần tử nhỏ, phần còn lại chứa các phần
tử lớn hơn sẽ được chuyển về các bộ xử lí mà bit thứ 𝑖 = 1. Quá trình so sánh và
trao đổi các phần tử này hoàn toàn tương tự như trong thuật toán OddEvenSort.
Giai đoạn 2: Sau khi kết thúc giai đoạn một, đa số các phần tử đã được về
đúng hoặc gần đúng với vị trí của chúng trong mảng được sắp xếp. Tuy nhiên, để
thu được mảng được sắp xếp có thứ tự, tại giai đoạn này cần tiếp tục thực hiện
thêm 𝑙 (𝑙 = 2. . 𝑝) bước lặp của thuật toán song song OddEvenSort cho các mảng
trên các bộ xử lí.
33
2.2.2.2 Đánh giá độ phức tạp thuật toán.
𝑝
so sánh-phân chia. Trong mỗi phép so sánh và phân chia, tổng số
Trong giai đoạn đầu của thuật toán, mỗi bộ xử lí sẽ thực thi 𝐷 = log 𝑝 phép
2
𝑛
cặp của các bộ
𝑝
xử lí cần được trao đổi vị trí để sắp xếp phần tử. Vì vậy, độ phức tạp của pha
log 𝑝). này là 𝑂 (𝑛
𝑝
𝑛
𝑛
Trong giai đoạn thứ 2, có l pha Odd-even được thực thi, mỗi pha yêu cầu
𝑝
𝑝
thời gian 𝑂 ( ), do đó độ phức tạp của pha này là 𝑂(𝑙 ).
2.2.2.3 Ví dụ
Cho mảng A=[12, 54, 96, 51, 37, 68, 87, 45, 36, 2,17, 82, 16, 6, 24, 45]. Số bộ xử
lý 𝑝 = 22 𝐷 = 2.
Quá trình thực hiện thuật toán như sau: Ban đầu sảy ra quá trình phân chia
các phần tử của mảng 𝐴 cho 4 bộ xử lí. Thuật toán tiếp tục trải qua hai giai đoạn.
Giai đoạn 1 sẽ thực hiện qua hai vòng lặp.
0
0
0
1
37 45 68 87
12 51 53 96
- Ban đầu các bộ xử lí sắp
xếp nội bộ phần tử của
mình
6 16 24 45
- Các BXL chỉ khác nhau ở
bit thứ 1 sẽ ghép cặp và
trao đổi dữ liệu
2 17 36 82
1
0
1
1
Vòng lặp 1:
01
00
6 16 24 37
2 12 17 36
- Kết thúc vòng lặp 1 các
phần tử được chuyển về
các BXL phù hợp
34
- Tại vòng lặp 2 các BXL
chỉ khác nhau ở bit thứ 2
sẽ ghép cặp và trao đổi dữ
51 53 82 96
45 45 68 87
Vòng lặp 2.
00
01
17 24 36 37
2 6 12 16
- Sau khi kết thúc vòng lặp
2, các phần tử đã về đúng
vị trí
45 45 51 54
68 82 87 96
10
11
- Thuật toán thực hiện tiếp
giai đoạn 2, sử dụng liên
tiếp 2 pha của thuật toán
OddEvenSort (l=2)
Hình 2.1 Ví dụ thuật toán ShellSort
Kết thúc vòng lặp 2.
Trên đây là hai thuật toán sắp xếp song song được xây dựng dựa trên nền tảng
của thuật toán tuần tự đã có và một thuật toán phát triển lên từ thuật toán song song
OddEvenSort. Với các thuật toán thuộc lớp độ phức tạp 𝑂(𝑛𝑙𝑜𝑔𝑛) vốn đã khá hiệu
quả khi thực hiện tuần tự, việc song song hóa các thuật toán thuộc lớp này cũng
mang lại hiệu quả cao hơn. Đặc biệt với Quicksort, đây là một trong những thuật
toán sắp xếp hiệu quả cao, và nó cũng rất thích hợp cho việc song song hóa. Vì
vậy, phần tiếp theo của chương này sẽ đề cập đến vấn đề song song hóa cho thuật
35
toán tuần tự Quicksort.
2.2.3 Thuật toán Parallel QuickSort.
Cũng giống như Shellsort, thuật toán ParallelQuickSort được xây dựng dựa
trên mô hình mạng Hypercube với 𝑝 bộ xử lí, trong đó 𝑝 phải thỏa mãn luôn là lũy
thừa của 2 hay 𝑝 = 2𝐷.
2.2.3.1 Tư tưởng thuật toán
𝑛
Quá trình phân chia dữ liệu: Phân chia 𝑛 phần tử của mảng A cho 𝑝 bộ xử
𝑝
lí. Mỗi bộ xử lí sẽ chứa phần tử.
Quá trình thực thi thuật toán: Việc song song hóa được thực hiện qua 𝐷
vòng lặp, tại vòng lặp thứ 𝑖 (1 ≤ 𝑖 ≤ 𝐷) sẽ trải qua các bước sau:
Bước 1. Một bộ xử lí lựa chọn ra một phần tử bất kỳ từ dãy con của nó làm
phần tử chốt và truyền phần tử chốt này đến tất cả các bộ xử lí còn lại. Việc chọn
ra phần tử chốt có thể chọn phần tử đầu tiên hoặc phần tử bất kỳ trong mảng của
bộ xử lí này.
Bước 2. Dựa vào phần tử chốt, các bộ xử lí sẽ phân hoạch các phần tử của
mình thành hai phần, phần nhỏ hơn hoặc bằng chốt và phần còn lại là các phần tử
lớn hơn chốt. Thuật toán tiến hành ghép cặp các bộ xử lí để trao đổi dữ liệu. Tại
vòng lặp thứ 𝑖 (1 ≤ 𝑖 ≤ 𝐷) những bộ xử lí mà chỉ khác nhau duy nhất một bit ở vị
trí thứ 𝑖 sẽ được ghép cặp với nhau.
Bước 3. Sau khi các bộ xử lí phân hoạch và ghép cặp, các bộ xử lí trong một
cặp sẽ xảy ra quá trình trao đổi dữ liệu. Những phần tử mà có giá trị nhỏ hơn chốt
phải được chuyển về bộ xử lí có bit thứ 𝑖 = 0 (bit thấp), những phần tử lớn hơn
chốt được chuyển về bộ xử lí có bit thứ 𝑖 = 1 (bit cao).
Sau bước này, dữ liệu ban đầu được chia thành hai phần, phần đầu tiên là
phần chứa các phần tử có giá trị nhỏ hơn chốt, những phần tử này sẽ nằm trên các
𝑝
bộ xử lí có bit thứ 𝑖 = 0 và sẽ chỉ có
2
bộ xử lí như vậy, phần còn lại sẽ chứa những
36
phần tử có giá trị lớn hơn chốt.
Khối hypercube 𝐷 chiều lúc này sẽ được chia thành 2 khối Hypercube con
với kích thước 𝐷 − 1 chiều. Tiếp tục sử dụng thủ tục đệ quy cho hai Hypercube
con 𝐷 − 1 chiều này.
Sau khi thực hiện xong 𝐷 vòng lặp, mỗi bộ xử lí sẽ sắp xếp nội bộ phần tử
của mình bằng cách sử dụng thuật toán QuickSort tuần tự, sau đó truyền các phần
này về một bộ xử lí gốc để ghép nối thành mảng được sắp xếp. Hình dưới đây minh
họa quá trình thực hiện thuật toán Parallel Quicksort trong trường hợp sử dụng 4
bộ xử lí, với khối Hypercube 2 chiều 𝐷 = 2.
Bước 1. BXL P00 lựa chọn một
phần tử chốt và truyền phần tử
chốt đến các BXL còn lại
Vòng lặp 1:
P00
<
P00
>
Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau
P01
P10
P11
>
<
>
<
<
>
P10
P11
Nửa thấp
Bước 3. Các BXL trao đổi các
phần tử, phân Hypercube ban
đầu thành 2 Hypercube con
P01
Nửa cao
P11
Vòng lặp 2:
P00
Nửa thấp
Bước 1. Lần lượt BXL P00 và
P10 lựa chọn phần tử chốt để
truyền cho P01 và P11
P01
P10
Nửa cao
P11
37
P00
P01
P10
<
P00
>
Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau
P01
>
<
>
P10
<
<
>
P11
Nửa thấp
P00
Bước 3. Các BXL trao đổi các
phần tử. Vòng lặp 2 kết thúc
P01
Nửa cao
P10
Nửa thấp
P11
Nửa cao
P00
Quicksort
thuật
P01
Quicksort
Sau khi kết thúc 2 vòng lặp, các
BXL sắp xếp tuần tự các phần tử
của mình bằng
toán
Quicksort tuần tự
P10
Quicksort
P11
Quicksort
Hình 2.2 Minh họa thuật toán ParallelQuickSort
2.2.3.2 Đánh giá độ phức tạp
Với 𝑛 là số phần tử của mảng , 𝑝 là số bộ xử lí. Khi đó độ phức tạp về thời gian
chạy của Parallel Quicksort là [7]:
𝑇(𝑛, 𝑝) = 𝑂( log ) + 𝑂( log 𝑝) + 𝑂(log 𝑝2) 𝑛
𝑝 𝑛
𝑝 𝑛
𝑝
2.2.3.3 Ví dụ
38
Mảng A={75, 91, 15, 64, 24, 25, 88, 54, 50, 12, 47, 72, 65, 54, 66, 22, 83,
66, 67, 0, 70, 98, 99, 82, 20, 40, 89, 47, 19, 61, 86, 85}. Số bộ xử lí 𝑝 =4. Quá trình
thực hiện thuật toán Parallel Quicksort như sau:
P00
Ban đầu, phân chia các phần tử cho các bộ xử lí:
P01
75 91 15 64 21 8 88 54
P10
50 12 47 72 65 54 66 22
P11
83 66 67 0 70 98 99 82
20 40 89 47 19 61 86 85
Thuật toán tiếp tục trải qua hai vòng lặp. Tại vòng lặp 1:
P00
P01
75 91 15 64 21 8 88 54
Bước 1. Bộ xử lí P00 lựa chọn
một phần tử chốt, sau đó truyền
phần tử chốt này cho 3 BXL còn
lại.
P10
50 12 47 72 65 54 66 22
P11
83 66 67 0 70 98 99 82
20 40 89 47 19 61 86 85
P00
P01
75 15 64 21 8 54 91 88
Bước 2. Các bộ xử lí phân hoạch
mảng thành hai phần lớn hơn chốt
và nhỏ hơn chốt, sau đó ghép cặp
với nhau
P10
50 12 47 72 65 54 66 22
P11
66 67 0 70 83 98 99 82
39
20 40 4719 61 89 86 85
P00
Nửa
nhỏ
P01
Bước 3. Các bộ xử lí thực hiện quá
trình trao đổi phần dữ liệu đã phân
hoạch. Chia Hypercube thành hai
Hypercube con.
7515 64 218 54 66 67 0 70
P10
50 12 47 72 65 54 66 22 20
40 47 19 61
Nửa
lớn
P11
83 98 99 82 91 88
Vòng lặp 2:
89 86 85
P00
P01
Bước 1. Bộ xử lí P00 và P10 lựa
chọn ngẫu nhiên ra một phần tử
rồi truyền cho các bộ xử lí tương
ứng.
7515 64 218 54 66 67 0 70
P10
50 12 47 72 65 54 66 22 20
40 47 19 61
P11
89 86 85
83 98 99 82 91 88
P00
Bước 2. Các bộ xử lí phân hoạch
mảng thành hai phần, sau đó
ghép cặp các BXL
P01
15 21 8 0 75 64 54 66 67 70
12 20 19 50 47 72 65 54 66
22 40 47 61
P10
P11
83 82 91 88 98 99
89 86 85
P00
Bước 3. Các bộ xử lí tiến hành
truyền dữ liệu. Vòng lặp 2 kết
thúc.
P01
15 218 0 12 20 19
50 47 72 65 54 66 22 40 47
61 75 64 54 66 67 70
P10
P11
83 82 91 8889 86 85
40
98 99
P00
Kết thúc thuật toán: Các BXL sử
dụng Quicksort tuần tự để sắp
xếp lại phần tử của mình.
P01
0 8 12 15 19 20 21
P10
22 40 47 47 50 54 54 61 64
65 66 66 67 70 72 75
P11
82 83 85 86 88 89 91
Hình 2.3 Ví dụ thuật toán ParallelQuickSort
98 99
2.2.4 Thuật toán HyperQuicksort
HyperQuicksort là thuật toán sắp xếp nhanh phát triển trên mô hình mạng
Hypercube, nó có thể được sử dụng cho bất kỳ một hệ thống truyền thông điệp nào
có số phần tử xử lí là lũy thừa của 2 [7].
2.2.4.1 Tư tưởng thuật toán
Sự khác nhau chủ yếu giữa HyperQuicksort và ParallelQuickSort là ở
phương thức lựa chọn phần tử chốt. Ngay tại bước đầu tiên, mỗi bộ xử lí sau khi
được phân chia phần tử, chúng sẽ sắp xếp nội bộ các phần tử của chúng bằng cách
sử dụng thuật toán sắp xếp tuần tự Quicksort.
Sau đó, một bộ xử lí sẽ lấy phần tử trung vị trong khối của nó làm phần tử
chốt, và thường nó được lấy ra từ bộ xử lí đầu tiên trong hệ thống. Các bước lặp
tiếp theo hoàn toàn tương tự như với thuật toán ParallelQuicksort. Tuy nhiên, khác
với ParallelQuicksort, phép chia tách và hợp nhất các phần tử trên các BXL luôn
đảm bảo quá trình phân một Hypercube thành hai Hypercube con mà mỗi bộ xử lí
chứa một danh sách đã sắp xếp và giá trị lớn nhất trong BXL chứa bit thấp là nhỏ
hơn giá trị nhỏ nhất trong BXL chứa bit cao.
Minh họa thuật toán HyperQuicksort trong trường hợp có 4 bộ xử lí. Ta
phải thực hiện thuật toán qua 2 vòng lặp. Cụ thể như sau:
Ban đầu, phân chia các phần tử cho các BXL. Các bộ xử lí sắp xếp nội bộ các phần
41
tử của mình.
P00
Quicksort
P01
Quicksort
Sau khi nhận được các phần tử, các
BXL sắp xếp nội bộ các phần tử của
mình. Thuật toán tiếp tục trả qua 2
vòng lặp
P10
Quicksort
P11
Quicksort
Vòng lặp 1
P00
Bước 1. BXL P00 truyền phần
tử trung vị đến các BXL còn lại
P01
P10
P11
<
P00
>
Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau
P01
>
<
>
P10
<
<
>
P11
P00
Nửa thấp
Bước 3. Các BXL trao đổi các
phần tử, phân Hypercube ban
đầu thành 2 Hypercube con
P01
P10
Nửa cao
P11
Vòng lặp 2
P00
Nửa thấp
Bước 1. Lần lượt BXL P00 và
P10 lựa chọn phần tử trung vị của
mình để truyền cho P01 và P11
P01
P10
Nửa cao
P11
42
<
P00
>
Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau
P01
>
<
>
P10
<
<
P11
>
Nửa thấp
P00
Bước 3. Các BXL trao đổi các
phần tử. Vòng lặp 2 kết thúc
P01
Nửa cao
P10
Nửa thấp
P11
Nửa cao
P00
Sorted
Kết thúc vòng lặp, các phần
được sắp xếp.
P01
Sorted
P10
Sorted
P11
Sorted
Hình 2.4 Minh họa thuật toán HyperQuickSort
2.2.4.2 Đánh giá độ phức tạp
Gọi 𝑛 là tổng số phần tử của mảng và gọi 𝑝 là số thành phần xử lí.[7]
43
log 𝑂( ) - Quicksort ban đầu có độ phức tạp là :
𝑛
𝑝 𝑛
𝑝
- Tổng thời gian để truyền thông cho log 𝑝 bước trao đổi là:
𝑂( log 𝑝) 𝑛
𝑝
- Tổng thời gian truyền thông giá trị phần tử chốt là
𝑂(log 𝑝)
2.2.4.3 Ví dụ
Mảng 𝐴 ={75, 91, 15, 64, 24, 8, 88, 54, 50, 12, 47, 72, 65, 54, 66, 22, 83, 66,
67, 0, 70, 98, 99, 82, 20, 40, 89, 47, 19, 61, 86, 85}.
Số bộ xử lí 𝑝 = 4. Quá trình thực hiện thuật toán HyperQuickSort được minh họa
bằng các bước dưới đây:
P00
75 91 15 64 21 8 88 54
P01
Quá trình phân chia các
phần tử: Ban đầu, phân chia
các phần tử cho các BXL.
50 12 47 72 65 54 66 22
P10
P11
83 66 67 0 70 98 99 82
8 15 21 54 64 75 88 91
P00
P01
20 40 89 47 19 61 86 85
P10
12 22 47 50 54 65 66 72
Các BXL sắp xếp nội bộ các phần
tử của mình bằng cách sử dụng
thuật toán QuickSort tuần tự. Sau
đó thuật toán tiếp tục trải qua hai
vòng lặp:
P11
0 66 67 70 82 83 98 99
44
19 20 40 47 61 85 86 89
Vòng lặp 1.
P00
8 15 21 54 64 75 88 91
P01
Bước 1. BXL đầu tiên chọn ra
phần tử ở vị trí trung vị làm phần
tử chốt, sau đó truyền phần tử
này đến các BXL còn lại
12 22 47 50 54 65 66 72
P10
0 66 67 70 82 83 98 99
P11
19 20 40 47 61 85 86 89
P00
8 15 21 54 65 75 88 91
P01
P10
Bước 2. Các BXL phân hoạch
các phần tử của mình thành hai
phần, lớn hơn chốt và nhỏ hơn
chốt. Sau đó, các BXL ghép cặp
để chuẩn bị truyền các phần tử
12 22 47 50 54 65 66 72
P11
0 66 67 70 82 83 98 99
19 20 40 47 61 85 86 89
P00
0 8 15 21 54
P01
P10
12 19 20 22 40 47 47 50 54
Bước 3. Các BXL truyền các phần
tử cho nhau theo quy tắc đã xây
dựng. Sau giai đoạn này, khối
Hypercube được phân thành 2
khối Hypercube con. Thuật toán
chuyển sang vòng lặp thứ 2
64 66 67 70 75 82 83 88 91
98 99
P11
61 65 66 72 85 86 89
Vòng lặp 2.
P00
0 8 15 21 54
P01
Bước 1. Hai BXL P00 và P10 lựa
chọn phần tử trung vị của mình
để truyền đến các BXL tương
ứng
P10
12 19 20 22 40 47 47 50 54
64 66 67 70 75 82 83 88 91
98 99
P11
45
61 65 66 72 85 86 89
P00
0 8 15 21 54
P01
Bước 2. Các BXL phân hoạch
các phần tử của mình thành hai
phần, lớn hơn chốt và nhỏ hơn
chốt. Sau đó, các BXL ghép cặp
đê chuẩn bị truyền các phần tử
P10
12 19 20 22 40 47 47 50 54
P11
64 66 67 70 75 82 83 88 91
98 99
61 65 66 72 85 86 89
P00
Bước 3. Các BXL truyền các
phần tử cho nhau theo quy tắc đã
xây dựng. Vòng lặp 2 kết thúc.
P01
0 8 12 15
19 20 21 22 40 47 47 50 54
54
P10
P11
61 64 65 66 67 70 72 75 82
Hình 2.5 Ví dụ thuật toán HyperQuickSort
83 85 86 88 89 91 98 99
Trên đây là hai thuật toán sắp xếp song song được thực hiện dựa trên những
thuật toán tuần tự đã có sẵn (OddEven sort, ParallelQuicksort) và thuật toán song
song phát triển từ thuật toán song song đã có(Shellsort, HyperQuicksort). Mỗi
thuật toán đều có những ưu và nhược điểm riêng, nếu như OddEven sort và
Shellsort là hai thuật toán đơn giản dễ cài đặt thì ParallelQuicksort và
HyperQuicksort lại là những thuật toán đem lại hiệu quả cao hơn và song song hóa
tốt hơn. Nhưng để ý một điều rằng, tuy phù hợp với song song hóa nhưng
ParallelQuickSort và HyperQuicksort lại cần phải có một điều kiện bắt buộc là số
bộ xử lí sử dụng luôn phải là lũy thừa của 2. Mặt khác, với Parallel QuickSort khi
thuật toán bị rơi vào trường hợp suy biến tức là thuật toán chọn phần tử chốt không
tốt, sẽ dẫn đến sự mất cân bằng trong quá trình phân chia các phần tử trên các bộ
xử lí khiến các bộ xử lí có thể làm việc không cân bằng nhau khi đó thời gian chạy
46
chương trình sẽ trở nên chậm.
Phần cuối của chương này xin được đề cập đến một thuật toán sắp xếp song
song mà có thể khắc phục được nhược điểm của Parallel Quicksort, thuật toán này
không dựa trên việc song song hóa thuật toán tuần tự đã có và cũng không phát
triển từ một thuật toán song song đã được đưa ra, và có thể phù hợp với hầu hết
các hệ thống song song.
2.3 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 toán sắp xếp song song đã được trình bày ở trên, PSRS là
một thuật toán sắp xếp song song với nhiều ưu điểm [9]. Nó giữ nguyên đượ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 toán sắp xếp tuần tự, một quá 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 toá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 ý.
2.3.1 Tư tưởng thuật toán
Thuật toán PSRS bao gồm có 6 pha phân biệt. Nó 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 𝑝 bộ xử lí và sắp xếp mảng có kích cỡ 𝑛, khi đó, thuật toán trải qua 6 bước
thực hiện như sau:
Bước 1. Khởi tạo ban đầu
Với 𝑝 bộ xử lí, lựa chọn một bộ xử lí làm gốc (bộ xử lí 0), khởi tạo bộ dữ
liệu với kích cỡ 𝑛.
Bước 2. Phân chia dữ liệu, sắp xếp cục bộ và lựa chọn các mẫu chuẩn.
𝑛
Phân chia dữ liệu ban đầu cho 𝑝 bộ xử lí. Mỗi bộ xử lí sẽ sắp xếp cục bộ tập
𝑝
47
dữ liệu với kích thước bằng cách sử dụng thuật toán QuickSort tuần tự. Sau đó,
mỗi bộ xử lí sẽ lựa chọn ra 𝑝 phần tử từ tập dữ liệu của mình để làm mẫu. Các mẫu
được lựa chọn có khoảng cách đều nhau. Cụ thể, các phẩn tử ở vị trí 1, 𝑤 + 1, 2𝑤 +
𝑝2]được chọn để làm mẫu.
1, . . . , (𝑝 − 1)𝑤 + 1 với 𝑤 = [ 𝑛
Bước 3. Tập hợp và trộn các mẫu, lựa chọn phần tử chốt.
Bộ xử lí gốc sẽ tập hợp tất cả các phần tử đã được chọn ra làm mẫu ở 𝑝 bộ
xử lí. Điều quan trọng cần để ý đó là mỗi tập hợp các phần tử mẫu tại mỗi bộ xử lí
đã được sắp xếp. Có 𝑝 tập hợp được sắp xếp và sử dụng thuật toán trộn để trộn
chúng lại với nhau. Từ 𝑝2 phần tử đã sắp xếp này, lựa chọn ra 𝑝 − 1 giá trị để làm
phần tử chốt bằng cách lấy ra các phần tử có chỉ số 𝑝 + 𝑓, 2𝑝 + 𝑓, … , (𝑝 − 1)𝑝 +
⌋. Tiếp theo, bộ xử lí gốc sẽ truyền thông các phần tử chốt này đến 𝑓 với 𝑓 = ⌊𝑝
2
𝑝 − 1 bộ xử lí còn lại.
Bước 4. Phân chia dữ liệu cục bộ tại các bộ xử lí dựa trên các phần tử chốt.
Mỗi bộ xử lí sẽ phân chia dữ liệu cục bộ đã được sắp xếp của nó ra thành 𝑝
phân lớp dựa vào 𝑝 − 1 phần tử chốt đã chọn.
Bước 5. Tập hợp và trộn các phân lớp tại các bộ xử lí.
Bộ xử lí thứ 𝑖 sẽ tập hợp dữ liệu trong phân lớp thứ 𝑖(1 ≤ 𝑖 ≤ 𝑝) từ các bộ
xử lí khác. Mỗi phân lớp này sẽ được sắp xếp và trộn lại với nhau.
Bước 6. Tập hợp dữ liệu cuối cùng
Bộ xử lí gốc sẽ tập hợp tất cả dữ liệu và lắp ráp các danh sách được sắp xếp
trên mỗi bộ xử lí thành danh sách được sắp xếp gồm n phần tử ban đầu. Thuật toán
kết thúc.
48
Thuật toán có thể được minh họa bằng hình dưới đây:
Dữ liệu ban đầu
Phân chia dữ liệu
P2
P0
P1
Sắp xếp cục bộ
P2
P0
P1
Lựa chọn mẫu
Trộn và sắp xếp mẫu
Chọn ra p-1 phần tử chốt
Truyền thông chốt
Phân lớp dữ liệu
Truyền và
trộn các
phân lớp
Tập hợp kết quả
Hình 2.6 Minh họa thuật toán PSRS
49
2.3.2 Đánh giá độ phức tạp
Về độ phức tạp của thời gian tính toán, trong bước thứ 2 của giải thuật, mỗi
𝑛
bộ xử lí thực hiện sắp xếp dữ liệu bằng QuickSort. Kích thước của dữ liệu trên mỗi
𝑝
bộ xử lí là và sau đó chọn ra 𝑝 phần tử làm mẫu. Do đó thời gian yêu cầu tính
toán trong bước này là:
𝑛
𝑂 ( log + 𝑝). 𝑛
𝑝 𝑛
𝑝
𝑝
𝑛
cần thiết là 𝑂 (
).
𝑝
Trong bước 4, mỗi bộ xử lí phân chia phần tử được sắp xếp. Thời gian
Trong bước thứ 5, bộ xử lí thứ 𝑖 trộn 𝑝 danh sách được sắp xếp. Mỗi danh
𝑛
sách này được tạo ra bằng cách sử dụng các phần tử chốt được chọn trong pha 3,
𝑝2 mà sau khi trộn mỗi
𝑛
trong trường hợp lý tưởng, mỗi danh sách có kích thước
𝑝
𝑛
danh sách trên mỗi bộ xử lí sẽ có kích cỡ . Sử dụng thuật toán trộn trong trường
𝑝
hợp này yêu cầu thời gian là 𝑂( log 𝑝).Tổng thời gian tính toán sẽ là:
𝑛
𝑛
𝑂 ( log + 𝑝 + + log 𝑝 ) 𝑛
𝑝 𝑛
𝑝 𝑛
𝑝 𝑛
𝑝
𝑝
𝑝2 phần
𝑛
Xét về thời gian truyền thông, trong bước 5, mỗi bộ xử lí gửi −
𝑝
𝑛
.Trong bước cuối cùng, bộ xử tử, do đó, tổng số phần tử cần truyền thông là 𝑛 −
𝑝
phần tử. Do đó độ phức tạp thời gian truyền thông là: lí gốc tập hợp 𝑛 −
𝑂(𝑛 − ) 𝑛
𝑝
50
2.3.3 Ví dụ minh họa
Thực hiện thuật toán sắp sếp PSRS trên mảng A có 36 phần tử với 3 bộ xử lí. Quá
2.3.4 Ví dụ minh họa
51
trình sắp xếp được thực hiện theo thứ tự dưới đây:
36 khóa
16 2 17 24 33 28 30 1 0 27 9 25 34 23 19 18 11 7 21 13 8 35 12 29 6 3 4 14 22 15 32 10 26 31 20 5
P1
P2
P3
16 2 17 24 33 28 30 1 0 27 9 25
34 23 19 18 11 7 21 13 8 35 12 29
6 3 4 14 22 15 32 10 26 31 20 5
Sắp xếp cục bộ
0 1 2 9 16 17 24 25 27 28 30 33
Sắp xếp cục bộ
7 8 11 12 12 18 19 21 23 29 34 35
Sắp xếp cục bộ
3 4 5 6 10 14 15 20 22 26 31 32
Lựa chọn mẫu
Lựa chọn mẫu
Lựa chọn mẫu
0 16 27
7 12 23
3 10 22
0 16 27 7 12 23 3 10 22
BXL P1 tập hợp các phần tử mẫu
0 3 7 10 13 16 22 23 27
Sắp xếp nội bộ phẩn tử mẫu
Lựa chọn ra 2 phần tử chốt
10
22
10
22
22
10
26
31
32
14
15
20
22
3
4
5
6
10
17
16
0
1
2
9
24
25
27
28
30
33
7
8
21
11
12
13
18
19
23
29
34
35
P1
P2
Kết hợp lại các vùng
P3
Kết hợp lại các vùng
Kết hợp lại các vùng
Phần 1 P1
Phần 2 P1
Phần 3 P1
0 1 2 9
24 25 27 28 30 33
Phần1 P2
Phần 2 P2
Phần 3 P2
Phần1 P3
Phần 2 P3
Phần 3 P3
7 8
3 4 5 6 10
16 17
11 12 13 18 19 21
14 15 20 22
Kết quả cuối cùng khi trộn các phân vùng tại P1
Kết quả cuối cùng khi trộn các phân vùng tại P1
23 29 34 35
26 31 32
Kết quả cuối cùng khi trộn các phân vùng tại P1
0 1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20 21 22
23 24 25 26 27 28 29 30 31 32 33 34 35
51
10 22
2.4 Kết luận chương
Chương 2, phần thứ nhất của chương đã đưa ra các chiến lược thiết kế cho bài
toán sắp xếp trên hệ thống song song, các chiến lược được áp dụng một cách linh hoạt
cho các thuật toán sắp xếp song song đã được trình bày ở trên.
Phần thứ hai của chương đã tập trung đi trình bày chi tiết về các thuật toán sắp
xếp song song về tư tưởng của thuật toán, cách thực hiện thuật toán, thuật toán và các
ví dụ chi tiết minh họa cho từng thuật toán. Ngoài ra, qua đó có thể nhận thấy được
sự khác nhau trong các thuật toán sắp xếp song song, mỗi thuật toán đều có những ưu
và nhược điểm riêng của mình. Bằng việc phân tích một cách chi tiết thuật toán song
song PSRS, nhận thấy rằng đây là một thuật toán hay với nhiều ưu điểm cả về độ
phức tạp và thủ tục cài đặt, phù hợp với nhiều mô hình song song hiện tại. Do đó
trong chương tiếp theo, phần thực nghiệm của luận văn xin lựa chọn ra thuật toán
Parallel Quicksort và thuật toán PSRS để cài đặt thử nghiệm trên hệ thống song song
52
cụ thể để đưa ra những đánh giá và so sánh độ hiệu quả của hai thuật toán này.
CHƯƠNG 3. ỨNG DỤNGLẬP TRÌNH SONG SONGCÀI ĐẶT THUẬT
TOÁN SẮP XẾP PSRS VÀ PARALLELQUICKSORT
Nội dung chính của chương trình bày thủ tục và các hàm cần thiết để cài đặt
thuật toán PSRS và ParallelQuicksort cùng với các kết quả thực nghiệm khi chạy
thuật toán này đồng thời đưa ra sự so sánh kết quả thực hiện giữa thuật toán PSRS và
thuật toán ParallelQuicksort khi cùng chạy trên một hệ thống để có thể đánh giá một
cách tổng thể tính đúng đắn cũng như hiệu quả của thuật toán.
3.1 Môi trường và phương pháp thực nghiệm
3.1.1 Môi trường thực nghiệm
Quá trình thực nghiệm được tiến hành trên hệ thống IBM Linux Cluster 1350
của trung tâm Tính toán Hiệu Năng Cao – Trường đại học Khoa học Tự nhiên –
- 8 node tính toán, mỗi node gồm 2 chip Intel Xeon Dual Core 3.2 GHz, 2 GB
ĐHQGHN với cấu hình như sau:
RAM, 1x36 GB HDD, DVD ROM. Tổng năng lực tính toán của 8 node là khoảng
- 2 node phục vụ lưu trữ (Storage1 và Storage2), mỗi node gồm 2 chip Intel
51.2 Gflops.
- 1 node đóng vai trò quản lí (MGT) bao gồm chip Intel Xeon Dual Core 3.2
Xeon Dual Core 3.2 GHz, 3 GB RAM, 4x72 GB HDD.
- Năng lực lưu trữ: thiết bị lưu trữ dùng chung EXP400 với 10x73 GB HDD
GHz, 3 GB RAM, 2x36 GBHDD.
- Các node chạy HĐH Redhat Enterprise Linux 3.0 và được kết nối với nhau
SCSI 320 MBps 15KRpm, dùng hệ thống chia sẻ file: GPFS cho Linux v2.3.0.5.
thông qua mạng Gethernet.
Các thuật toán được lập trình bằng ngôn ngữ C++ sử dụng thư viện lập trình
song song MPI. Thực nghiệm nhằm mục đích kiểm tra sự song song hóa của thuật
toán PSRS và kiểm nghiệm và so sánh thời gian thực thi của thuật toán này so với
thuật toán ParallelQuicksort (Thuật toán ParallelQuickSort được xây dựng trên mô
53
hình mạng Hypercube tuy nhiên vẫn có thể chạy thực nghiệm trêm mô hình MPI-Mô
hình truyền thông điệp, bởi lẽ quá trình truyền thông điệp chính là quá trình gửi nhận
dữ liệu giữa các nút trên mạng Hypercube).
3.1.2 Phương pháp thực nghiệm
Về nguyên tắc lấy số liệu thực nghiệm:
- Cố định số phần tử của mảng thay đổi số bộ xử lí sử dụng(2, 4, 8) 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.
- Thay đổi số phần tử của mảng (105, 106, 107) và chạy trên cùng số bộ xử lí,
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.
3.2 Các kết quả thực nghiệm
3.2.1 Kết quả thực nghiệm khi chạy trên thuật toán PSRS
Thời gian chạy trung bình của thuật toán
PSRS(giây)
Input
Size T.sequency
(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
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)
107 4.6197 3.1352 2.5169 2.1608 2.1887
Bảng 1. So sánh kết quả chạy thuật toán PSRS
Qua thực nghiệm, trước hết nhận thấy rằng thuật toán PSRS hoàn toà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ả thực nghiệm, 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ử 𝑛 = 100000 thì thời gian chạy song song nhanh gấp 1.5 lần, với số phần
54
tử 𝑛 = 1000000 thì thời gian chạy song song nhanh gấp 1.36 lần, với 𝑛 = 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ử 𝑛 = 100000 thì thời gian chạy song
song nhanh gấp 3 lần, với số phần tử 𝑛 = 1000000 thì thời gian chạy song song
nhanh gấp 2.15 lần, với 𝑛 = 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ử 𝑛 = 1000000 thì thời gian chạy song song nhanh gấp 1.95 lần, với 𝑛 =
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 toá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ả thực nghiệm, 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 toá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 đó luôn luôn 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
Hình 3.1 Biểu đồ so sánh thời gian chạy thuật toán PSRS
55
song song.
Hình 3.2 Biểu đồ so sánh thời gian chạy của các BXL với cùng số phần tử N=106
3.2.2 So sánh kết quả giữa thuật toán PSRS và ParallelQuicksort(PQ)
Thời gian chạy trung bình của thuật toán song song(giây) Input PSRS PQ PSRS PQ PSRS PQ Size P=2 P=2 P=4 P=4 P=8 P=8
105 0.0285 0.009 0.0183 0.007 0.0514 0.0466
106 0.3343 0.1043 0.1947 0.0873 0.2146 0.1204
107 3.1352 0.9525 2.1608 0.8029 2.1887 1.2908
Bảng 2. So sánh thời gian chạy của PSRS và Parallel Quicksort
56
P: Số bộ xử lí của hệ thống Input Size: Kích thước đầu vào(Số phần tử )
Hình 3.3 Biểu đồ so sánh thời gian của PSRS và PQ
Khi chạy trên cùng một hệ thống, thuật toán PSRS và Parallel Quicksort đều
cho những kết quả khả quan. Với dữ liệu đầu vào như trên thì cả hai thuật toán đều
nên sử dụng 4 bộ xử . Qua biểu đồ trên ta thấy rằng, trong trường hợp trung bình, tức
là thuật toán Parallel Quicksort không bị suy biến, thì thuật toán Parallel Quicksort
cho kết quả tốt hơn thuật toán PSRS.
3.3 Kết luận chương
Trong chương 3, em đã tập trung vào xây dựng và cài đặt chương trình thử
nghiệm tại trung tâm Tính toán Hiệu Năng Cao – Trường đại học Khoa học Tự nhiên
– ĐHQGHN. Với hai thuật toán được cài đặt, khi chạy thử nghiệm đã thu được kết
quả khá khả quan. Trước hết có thể khẳng định rằng hai thuật toán này hoàn toàn có
thể thực hiện song song hóa được, hơn thế nữa, hai thuật toán khi chạy đều cho ra
thời gian thực thi nhanh hơn nhiều so với việc chạy thuật toán tuần tự. Qua đó, em
nhận thấy được rằng việc lựa chọn số bộ xử lí để chạy chương trình có ảnh hưởng rất
lớn đến kết quả của chương trình. Cần xác định số bộ xử lí phù hợp với từng bài toán
57
để có được kết quả khả quan nhất.
KẾT LUẬN
Luận văn đã trình bày một cách khái quát nhất về cơ sở của xử lí song song,
các mô hình song song thường được sử dụng hiện nay. Nội dung chủ yếu của luận
văn tập trung vào việc hệ thống hóa các thuật toán sắp xếp đã được nghiên cứu, phân
tích được đặc điểm của các thuật toán, đưa ra được cái nhìn bao quát nhất về các thuật
toán sắp xếp cơ bản. Lấy đó là chủ đề để nghiên cứu của luận văn, luận văn đã được
đưa ra với cấu trúc gồm có 3 chương. Trong đó, chương 1 của luận văn trình bày một
cách tổng quan nhất về lý thuyết xử lí song song, các mô hình song song phổ biến và
tập trung mô tả bài toán sắp xếp, việc hệ thống hóa lại hầu hết các thuật toán sắp xếp
và đưa ra những so sánh trên các thuật toán sắp xếp là một điểm nổi bật của chương
1. Chương 2 của luận văn tập trung vào việc tìm hiểu vấn đề song song hóa các thuật
toán sắp xếp cơ bản. Đây là một trong những vấn đề trọng tâm của luận văn. Các
thuật toán sắp xếp song song đã được trình bày hết sức chi tiết từ tư tưởng đến thuật
toán và các ví dụ minh họa để làm rõ nét hơn về các thuật toán đó. Với ba thuật toán
điển hình đó là Parallel Quicksort, HyperQuicksort và PSRS, đây sẽ là ba thuật toán
giúp cải thiện tốc độ của việc sắp xếp một cách tốt nhất khi thực hiện trên hệ thống
song song. Qua quá trình tính toán và thực nghiệm, luận văn đã đưa ra được những
kết quả để có thể khẳng định rằng việc song song hóa trên các thuật toán trên là hoàn
toàn chính xác và thu được thời gian xử lí tốt hơn những giải thuật tuần tự đã có rất
nhiều.
Với kiến thức của bản thân còn chưa cao và chưa có nhiều thời gian để nghiên
cứu nhiều thuật toán song song khác, vì vậy trong tương lai, em sẽ tiếp tục tìm hiểu
những thuật toán song song khác, không chỉ áp dụng trên các bài toán sắp xếp mà còn
áp dụng được trên nhiều lĩnh vực khác nữa để từ đó có thể bổ sung thêm kiến thức
cũng như kinh nghiệm cho bản thân về khả năng phân tích cũng như xử lí bài toán
58
trên hệ thống song song để áp dụng trong các lĩnh vực mà xã hội đang cần.
TÀI LIỆU THAM KHẢO
Tiếng việt
[1]. Lê Huy Thập (2010), “ Cơ sở lý thuyết song song”, NXB Công nghệ
thông tin và truyền thông , Hà Nội.
[2]. Lê Minh Hoàng (2009), “Giải thuật và lập trình”, Đại học sư phạm Hà
Nội I.
Tiếng anh
[3]. Grama A., A. Gupta, G. Karypis, V. Kumar (2003), “Introduction to
Parallel Computing”, Addison Wesley.
[4]. M. J. Quinn(2003), “Parallel Programming in C with MPI and
OpenMP”, Tata McGraw Hill Publications .
[5]. Madhavi Desai, Viral Kapadiya, “Performance Study of Efficient Quick
Sort and Other Sorting Algorithms for Repeated Data”, National Conference
on Recent Trends in Engineering & Technology, 13-14 May 2011.
[6]. D. E. Knuth(1998), “The Art of Computer Programming”, Volume 3:
Sorting and Searching, Second ed. Boston, MA: Addison-Wesley.
[7]. I.S. Rajput, B. Kumar, TinKu Singh, “Performance comparison of
Sequential Quicksort and Parallel Quicksort Algorithms”, International
Journal of Computer Applications (0975-8887) Volume 57_No9, November
2012.
[8]. Quinn M.J (1989), “Analysis and Benchmarking of two parallel sorting
algorithms: HyperQuicksort and QuickMerge”, University of New
Hampshire, Durham, NH 03824, USA.
[9]. Xiaobo Li, Paul Lu, Jonathan Schaeffer, John Shillington, Pok Sze
Wong (2004), “On the Versatility of parallel sorting by Regular Sampling”,
59
University of Alberta, EdmonTon, Alberta, Canada.
MergeSort (A,B1,p,t); MergeSort (A,B2,t+1,q); Merge(B1,B2,B,t-p+1,q-t);
} }
void Merge (X,Y,Z,m,n); { i=1 ; j=1 ; k=1 ;
{ Z[k]= X[i]; i=i+1;}
while (i
}
24
Giống như Quicksort, Merge sort là phương pháp dựa trên đệ quy, điều này
sẽ là lựa chọn không tốt với các ứng dụng chạy trên máy tính giới hạn về bộ nhớ.
MergeSort có độ phức tạp là 𝑂(𝑛𝑙𝑜𝑔𝑛) [2].
c. Thuật toán sắp vun đống (HeapSort)
Đống là một dạng cây nhị phân hoàn chỉnh đặc biệt mà giá trị lưu tại mọi
nút có độ ưu tiên cao hơn hay bằng giá trị lưu trong hai nút con của nó. Trong thuật
toán sắp xếp kiểu vun đống, ta coi quan hệ “ưu tiên hơn hay bằng” là quan hệ “lớn
hơn hoặc bằng”: “≥” [2].
Thuật toán sắp xếp vun đống hoạt động cũng như tên gọi của nó, bắt đầu
bằng việc xây dựng một “đống” của tập dữ liệu, sau đó loại phần tử lớn nhất và
đặt nó vào vị trí cuối cùng của mảng. Sau việc xóa phần tử lớn nhất, nó tái cấu trúc
của đống và di chuyển phần tử lớn nhất kế tiếp còn lại và đặt nó vào vị trí ở kế
cuối của mảng được sắp xếp. Thao tác này được lặp lại cho tới khi không còn phần
tử bên trái trong đống và mảng đã được sắp xếp đầy.
Thuật toán sắp xếp vun đống có độ phức tạp 𝑂(𝑛𝑙𝑜𝑔𝑛) [2]. Dưới đây là
lược đồ của thuật toán sắp xếp vun đống.
void HeapSort(int A[], int n){ int i;
ShipDown( A, i, n);
exchange (A[0],A[i]); ShipDown(A, 0, i-1);
for i= n/2 -1 0 for i= n-1 1{ } }
void ShipDown(int A[], int root, int bottom){
25 maxchild = root*2;
maxchild = root*2+1;
else
int done, maxchild; done=0; while ((root*2<= bottom) && (!done)){ if(root*2 == bottom) maxchild = root*2; else if ( A[root*2] > A[root*2+1]) if (A[root]< A[maxchild]{
exchange(A[root], A[maxchild]);
1.2.3.2 Thuật toán sắp xếp có độ phức tạp thấp với dữ liệu đặc biệt
a. Thuật toán sắp xếp Counting
Cho một mảng 𝐴 có 𝑛 số nguyên, mỗi số đều nằm trong vùng giá trị (0 . . 𝐾).
Thuật toán sắp xếp đếm sử dụng một mảng 𝐶 chứa giá trị của các bộ đếm, kết quả
đầu ra được lưu trữ trong một mảng phụ 𝐶.
Ý tưởng của thuật toán: Với mỗi số 𝑖 trong vùng giá trị từ (0 . . 𝐾), đếm số
lần xuất hiện của 𝑖 ở trong mảng 𝐴 và sau đó lưu giá trị đó và 𝐶[𝑖]. Sau khi kết
thúc, việc sắp xếp được thực hiện bằng cách liệt kê sự xuất hiện của các giá trị từ
(0 . . 𝐾) dựa vào các giá trị 𝐶[𝑖]. Lần lượt 𝐶[0] số 0, rồi đến 𝐶[1] số 1 … và
𝐶[𝐾] số 𝐾. Thuật toán CountingSort hiệu quả cho việc sắp xếp mảng các số nguyên
khi mà độ dài 𝑛 của mảng là lớn hơn nhiều so với giá trị lớn nhất của mảng.
void CountingSort(int A[],int B[], int C[], int k) {
for i=0k
C[i]=0;
for j=1 length[A] C[A[j]]= C[A[j]]+1;//Đếm số lần xuất hiện A[j] for i=2k C[i]=C[i]+C[i-1];//C[i] bây giờ là số phần tử ≤ 𝑖 for j= length[A] 1
{B[C[A[j]]]= A[j]; C[A[j]]= C[A[j]]-1;}
26
}
Thuật toán sắp xếp đếm CountingSort có độ phức tạp là 𝑂(𝑛 + 𝑘) [2].
b. Thuật toán sắp xếp theo cơ số (RadixSort)
Kế thừa ý tưởng của Quicksort, tại bước phân đoạn thuật toán phân đoạn
đoạn đang xét thành hai đoạn thỏa mãn mỗi khóa trong đoạn đầu nhỏ hơn hoặc
bằng mọi khóa trong đoạn sau và thực hiện tương tự trên hai đoạn mới tạo ra, việc
phân đoạn được tiến hành với sự so sánh các khóa với giá trị một khóa chốt. Với
Radixsort, khi sắp xếp mảng các số nguyên mà mỗi số nguyên được biểu diễn dưới
dạng nhị phân có độ dài 𝑧 bit đánh số từ bit 0 (bit ở hàng đơn vị) tới bit 𝑧 − 1 (bit
cao nhất).
Tại bước phân đoạn, dãy khóa từ 𝐴[1] tới 𝐴[𝑛] ta có thể đưa những khóa
có bit cao nhất là 0 được đưa về vị trí đầu dãy, những khóa có bit cao nhất là 1 về
cuối dãy. Hiển nhiên, những khóa bắt đầu bằng bit 0 phải có giá trị nhỏ hơn những
khóa bắt đầu bằng bit 1. Tiếp tục quá trình phân đoạn với hai đoạn dãy khóa: Đoạn
gồm các khóa có bit cao nhất là 0 và đoạn gồm các khóa có bit cao nhất là 1. Với
những khóa thuộc cùng một đoạn thì bit cao nhất giống nhau, ta có thể áp dụng
quá trình phân đoạn tương tự trên theo bit thứ 𝑧 − 2 và cứ tiếp tục như vậy. Quá
trình phân đoạn kết thúc nếu như đoạn đang xét là rỗng hay ta đã tiến hành phân
đoạn đến tận bit đơn vị tức là tất cả các khóa thuộc một trong hai đoạn mới tạo ra
đều có bit đơn vị bằng nhau [2].
void RadixBinarySort() partition(L,R,b: integer){ if L>=R
exit;
exchange (A[i], A[j]);
while (i partition(L,j-1,b-1);
partition(j, R, b-1); 27 {
} i=L; j=R;
do
while i==j;
if (Bit b của A[i]=0) j=j++;
if b>0
}
partition(1, n, z-1);//z là độ dài chuỗi nhị phân Với 𝑛 là số phần tử cần sắp xếp và 𝑧 là chiều dài của chuỗi nhị phân biểu diễn từng phần tử thì khi đó thuật toán có độ phức tạp là 𝑂(𝑛. 𝑧) [2]. 1.3 Kết luận chương Như vậy trong chương 1, phần đầu của chương đã trình bày một cách tổng quan về xử lí song song và các mô hình song song cơ bản. Chúng ta hình dung được phần nào về xử lí song song, tầm quan trọng của việc song song hóa một bài toán và cách thức để đánh giá một giải thuật song song cho một bài toán cụ thể. Phần tiếp theo của chương đã hệ thống hóa lại các thuật toán sắp xếp tuần tự, đây là những thuật toán phổ biến và quen thuộc. Mỗi thuật toán đều thể hiện rõ trên hai khía cạnh là tư tưởng thuật toán và độ phức tạp của thuật toán. Việc cải tiến và song song hóa một số thuật toán đã được giới thiệu ở trên 28 sẽ được nghiên cứu và trình bày trong chương 2. Với việc xử lý tuần tự, chương trình thực thi trên một bộ xử lí đơn, tại một thời điểm chỉ có duy nhất một tác vụ được thực hiện, điều này phần nào làm cho thời gian thực hiện chương trình lâu hơn so với việc thực thi đồng thời nhiều tác vụ cùng một lúc. Do đó, việc song song hóa các thuật toán sắp xếp một cách hợp lý sẽ giúp giảm đáng kể thời gian của việc sắp xếp. Nếu đầu vào của bài toán được chia thành nhiều phần và phân cho các CPU và mỗi CPU thực thi trên một mảng con và có sự phối hợp hợp lí thì khi đó, thời gian cần thiết để sắp xếp mảng sẽ có khả năng giảm đi nhiều. Để thực hiện song song hóa một thuật toán sắp xếp, chúng ta có thể thực hiện theo ba phương pháp: Phương pháp đầu tiên là phát triển các thuật toán song song từ các thuật toán tuần tự có sẵn. Đây là cách làm tương đối đơn giản bởi vì thuật toán tuần tự là đã có sẵn, việc phân tích thuật toán tuần tự để chuyển sang thuật toán song song sẽ dễ dàng hơn nhiều. Tuy nhiên, không phải thuật toán tuần tự nào cũng có thể song song hóa được, vì có một số thuật toán, vốn bản thân nó luôn luôn là tuần tự, tức là ta không thể chia cắt bài toán ra thành các tiến trình độc lập nhau để phân chia cho các bộ xử lí thực thi đồng thời. Phương pháp thứ hai là phát triển một thuật toán song song từ một thuật toán song song đã có. Thực tế, để có một chương trình đạt hiệu quả cao cần phải trải qua các quá trình thay đổi và chỉnh sửa cho phù hợp. Do đó, ta có thể dựa vào thuật toán sắp xếp song song đã có để có thể phát triển thành thuật toán song song mới không những rút ngắn thời gian thực hiện mà còn để phù hợp hơn với một số hệ thống song song mới. Phương pháp thứ ba là xây dựng một thuật toán song song hoàn toàn mới, điều này có nghĩa là chúng ta bắt đầu ý tưởng song song mà không phụ thuộc vào 29 thuật toán tuần tự đã có cũng như không phát triển từ những thuật toán song song đã làm. Để làm được điều này sẽ mất nhiều thời gian và cần phải có trình độ và sự chuyên sâu về xử lí song song. Qua đó, để xây dựng một giải thuật song song nói chung cũng như song song hóa cho bài toán sắp xếp nói riêng có thể dựa vào ba phương pháp trên. Nhưng dù theo phương pháp nào, thì mục đích cuối cùng cần đạt được đó là thuật toán song song cần phải cải thiện được thời gian thực hiện chương trình so với thuật toán tuần tự. Phần dưới đây sẽ trình bày chi tiết về các thuật toán sắp xếp song song phát triển dựa trên ba phương pháp nêu trên. Nội dung phần này sẽ trình bày hai thuật toán sắp xếp song song được xây dựng từ thuật toán tuần tự có khả năng song song hóa cao đó là thuật toán OddEvenSort, thuật toán ParallelQuickSort cùng với hai thuật toán trên là thuật toán Shellsort là sự cải thiện của thuật toán OddEvenSort và thuật toán HyperQuickSort thuật toán song song được phát triển từ thuật toán song song ParallelQuickSort. Cho mảng 𝐴[𝑛]. Giả sử hệ thống sử dụng 𝑛 bộ xử lí, mỗi bộ xử lí mang một chỉ số khác nhau 𝑝𝑖 (𝑖 = 0. . 𝑛 − 1), khi đó chỉ số của các bộ xử lí phân các bộ xử lí thành hai loại đó là các bộ xử lí có chỉ số chẵn và các bộ xử lí có chỉ số lẻ [3]. Quá trình phân chia dữ liệu cho các bộ xử lí: Phân chia phần tử của mảng 𝐴 ban đầu cho các bộ xử lí. Để đơn giản, bộ xử lí 𝑝𝑖 sẽ nhận phần tử thứ 𝐴[𝑖] trong mảng. Quá trình thực hiện thuật toán: Thuật toán song song sẽ trải qua tối đa n pha (0 . . 𝑛 − 1) chẵn lẻ xen kẽ nhau. Trong pha chẵn, các bộ xử lí mang chỉ số chẵn sẽ thực hiện so sánh phần tử 30 của nó với phần tử nằm trong bộ xử lí có chỉ số lẻ nằm liền bên phải của nó (𝑝0, 𝑝1), (𝑝2, 𝑝3)…, nếu hai phần tử trong các cặp xử lí này không đúng thứ tự cần sắp xếp, khi đó hai bộ xử lí sẽ tráo đổi hai phần tử của chúng cho nhau. Tương tự, trong pha lẻ, các bộ xử lí mang chỉ số lẻ sẽ so sánh phần tử của nó với phần tử nằm trong bộ xử lí có chỉ số chẵn liền kề bên phải của nó (𝑝1, 𝑝2), (𝑝3, 𝑝4)… nếu hai phần tử trong các cặp xử lí này không đúng thứ tự cần sắp xếp, khi đó hai bộ xử lí sẽ tráo đổi hai phần tử của chúng cho nhau. Thuật toán dừng nếu trong hai pha liên tiếp không có cặp nào được đổi chỗ cho nhau [3]. 2.2.1.2 Độ phức tạp thuật toán Trong mỗi pha của thuật toán, các bộ xử lí với nhãn chẵn hoặc lẻ thực thi một 𝑛 bước so sánh – đổi chỗ với bộ xử lí bên phải của nó. Và mỗi yêu cầu đó tốn 𝑂(1) 2 đơn vị thời gian, cần có yêu cầu so sánh. Tổng số pha cần thực hiện là 𝑛. Do đó, thời gian xây dựng cho giải thuật song song là 𝑂(𝑛2) [3]. Thuật toán thực hiện tối đa 𝑛 pha, độ phức tạp về thời gian sẽ là 𝑂(𝑛2). Tuy nhiên đó là độ phức tạp thời gian khi chúng ta có đủ 𝑛 bộ xử lí. Khi số phần tử của mảng cần sắp xếp là rất lớn thì chi phí tài nguyên này khó có thể đáp ứng được. Dưới đây, chúng ta sẽ xem xét thuật toán khi thực hiện với 𝑝 bộ xử lí 𝑝 < 𝑛. Ban đầu, chia mảng gồm 𝑛 phần tử ra thành 𝑝 phần. Mỗi bộ xử lí được nhận 𝑛
một khối gồm
𝑝 phần tử, các bộ xử lí sẽ sắp xếp nội bộ các phần tử mà chúng được 𝑛 giao. Thời gian để sắp xếp các khối ban đầu này (sử dụng thuật toán Quicksort 𝑝 𝑝 𝑝 log ). Sau đó, quá trình xử lí thực hiện 𝑝 pha làm việc hoặc Merge sort) là 𝑂 (𝑛
𝑝 2 ( pha lẻ và pha chẵn), mỗi pha sẽ tiến hành các phép so sánh-phân chia. Đến 2
pha cuối cùng, danh sách được sắp xếp [3]. Trong mỗi pha, mất 𝑂 (𝑛
𝑝 ) phép so ) thời gian để gửi truyền sánh để trộn hai khối lại với nhau theo thứ tự, và mất 𝑂 (𝑛
𝑝 31 thông giữa bộ xử lí. 2.2.1.3 Ví dụ minh họa Cho mảng A={4, 2, 7, 8, 5, 1, 3, 6} và số bộ xử lí 𝑛=8. Ban đầu, các phần tử trong mảng A lần lượt được phân chia cho các bộ xử lí (𝑝0 … 𝑝7). Thuật toán trải qua 7 pha làm việc dưới đây. Pha P0 P1 P2 P3 P4 P5 P6 P7 4 ↔ 2 7 − 8 5 ↔ 1 3 − 6 0 1 2 4 − 7 8 ↔ 1 5 ↔ 3 6 2 2 4 − 7 ↔ 1 8 ↔ 3 5 − 6 3 2 4 ↔ 1 7 ↔ 3 8 ↔ 5 6 4 2 ↔ 1 4 ↔ 3 7 ↔ 5 8 ↔ 6 5 1 2 − 3 4 − 7 ↔ 6 8 5 6 1 2 − 3 − 4 − 6 7 − 8 5 7 1 2 − 3 4 − 6 − 7 8 5 2.2.2 Thuật toán Shellsort. Thuật toán sắp xếp song song dựa trên hoán vị chẵn lẻ ở trên tồn tại nhược điểm đó là tại mỗi vòng lặp và tại một thời điểm các phần tử chỉ được đổi chỗ đến một vị trí gần với nó mà thôi (từ BXL 𝑝𝑖 sang BXL 𝑝𝑖+1). Nhưng thông thường, có một số phần tử trong mảng chúng có khoảng cách so với vị trí đúng của chúng là khá xa (chẳng hạn như phần tử 𝑎 nằm ở bộ xử lí 𝑝0 nhưng vị trí đúng của chúng lại là ở bộ xử lí 𝑝𝑖). Thuật toán ShellSort phần nào cải thiện được nhược điểm của 32 OddEvenSort. Thuật toán song song Shellsort được xây dựng trên mô hình mạng Hypercube-𝐷 chiều [4]. Gọi 𝑝 là số bộ xử lí của hệ thống với 𝑝 là lũy thừa của 2, 𝑝 = 2𝐷(𝐷 là số chiều của mạng). 2.2.2.1 Tư tưởng thuật toán 𝑛 Quá trình phân chia dữ liệu cho các bộ xử lí: Chia 𝑛 phần tử của mảng A 𝑝 cho p bộ xử lí, mỗi bộ xử lí sẽ chứa phần tử. Quá trình thực hiện thuật toán: Ban đầu, mỗi bộ xử lí sử dụng một thuật toán sắp xếp tuần tự hiệu quả (chẳng hạn Quicksort) để sắp xếp nội bộ các phần tử của chúng theo thứ tự. Thuật toán tiếp tục trải qua hai giai đoạn: Giai đoạn 1: Thực hiện 𝐷 bước lặp, tại mỗi bước lặp, tiến hành các phép so sánh và phân chia chọn ra các bộ xử lí để ghép cặp trên mạng Hypercuber. Các bộ xử lí được ghép cặp với nhau theo quy luật sau: Tại bước lặp thứ 𝑖 (1 ≤ 𝑖 ≤ 𝐷) các bộ xử lí khác nhau duy nhất ở bit thứ 𝑖 được lựa chọn để so sánh và trao đổi các phần tử với nhau (chẳng hạn với 𝑖 = 1 thì các cặp xử lí có dạng biểu diễn nhị phân (000, 100), (001, 101), (010,110), (011, 111)). Việc so sánh và trao đổi phần tử này có thể sử dụng một thuật toán tuần tự hiệu quả để trộn các phần tử trong hai bộ xử lí lại với nhau, sau đó phân chia lại các phần tử thành hai phần và chuyển về các bộ xử lí sao cho thỏa mãn điều kiện: Các bộ xử lí có bit thứ 𝑖 =0 sẽ chứa các phần tử nhỏ, phần còn lại chứa các phần tử lớn hơn sẽ được chuyển về các bộ xử lí mà bit thứ 𝑖 = 1. Quá trình so sánh và trao đổi các phần tử này hoàn toàn tương tự như trong thuật toán OddEvenSort. Giai đoạn 2: Sau khi kết thúc giai đoạn một, đa số các phần tử đã được về đúng hoặc gần đúng với vị trí của chúng trong mảng được sắp xếp. Tuy nhiên, để thu được mảng được sắp xếp có thứ tự, tại giai đoạn này cần tiếp tục thực hiện thêm 𝑙 (𝑙 = 2. . 𝑝) bước lặp của thuật toán song song OddEvenSort cho các mảng trên các bộ xử lí. 33 2.2.2.2 Đánh giá độ phức tạp thuật toán. 𝑝
so sánh-phân chia. Trong mỗi phép so sánh và phân chia, tổng số Trong giai đoạn đầu của thuật toán, mỗi bộ xử lí sẽ thực thi 𝐷 = log 𝑝 phép 2 𝑛 cặp của các bộ 𝑝 xử lí cần được trao đổi vị trí để sắp xếp phần tử. Vì vậy, độ phức tạp của pha log 𝑝). này là 𝑂 (𝑛
𝑝 𝑛 𝑛 Trong giai đoạn thứ 2, có l pha Odd-even được thực thi, mỗi pha yêu cầu 𝑝 𝑝 thời gian 𝑂 ( ), do đó độ phức tạp của pha này là 𝑂(𝑙 ). 2.2.2.3 Ví dụ Cho mảng A=[12, 54, 96, 51, 37, 68, 87, 45, 36, 2,17, 82, 16, 6, 24, 45]. Số bộ xử lý 𝑝 = 22 𝐷 = 2. Quá trình thực hiện thuật toán như sau: Ban đầu sảy ra quá trình phân chia các phần tử của mảng 𝐴 cho 4 bộ xử lí. Thuật toán tiếp tục trải qua hai giai đoạn. Giai đoạn 1 sẽ thực hiện qua hai vòng lặp. 0
0 0
1
37 45 68 87 12 51 53 96 - Ban đầu các bộ xử lí sắp
xếp nội bộ phần tử của
mình 6 16 24 45 - Các BXL chỉ khác nhau ở
bit thứ 1 sẽ ghép cặp và
trao đổi dữ liệu 2 17 36 82 1
0 1
1 Vòng lặp 1: 01 00 6 16 24 37 2 12 17 36 - Kết thúc vòng lặp 1 các
phần tử được chuyển về
các BXL phù hợp 34 - Tại vòng lặp 2 các BXL
chỉ khác nhau ở bit thứ 2
sẽ ghép cặp và trao đổi dữ 51 53 82 96 45 45 68 87 Vòng lặp 2. 00 01 17 24 36 37 2 6 12 16 - Sau khi kết thúc vòng lặp
2, các phần tử đã về đúng
vị trí 45 45 51 54 68 82 87 96 10 11 - Thuật toán thực hiện tiếp
giai đoạn 2, sử dụng liên
tiếp 2 pha của thuật toán
OddEvenSort (l=2) Hình 2.1 Ví dụ thuật toán ShellSort Kết thúc vòng lặp 2. Trên đây là hai thuật toán sắp xếp song song được xây dựng dựa trên nền tảng của thuật toán tuần tự đã có và một thuật toán phát triển lên từ thuật toán song song OddEvenSort. Với các thuật toán thuộc lớp độ phức tạp 𝑂(𝑛𝑙𝑜𝑔𝑛) vốn đã khá hiệu quả khi thực hiện tuần tự, việc song song hóa các thuật toán thuộc lớp này cũng mang lại hiệu quả cao hơn. Đặc biệt với Quicksort, đây là một trong những thuật toán sắp xếp hiệu quả cao, và nó cũng rất thích hợp cho việc song song hóa. Vì vậy, phần tiếp theo của chương này sẽ đề cập đến vấn đề song song hóa cho thuật 35 toán tuần tự Quicksort. 2.2.3 Thuật toán Parallel QuickSort. Cũng giống như Shellsort, thuật toán ParallelQuickSort được xây dựng dựa trên mô hình mạng Hypercube với 𝑝 bộ xử lí, trong đó 𝑝 phải thỏa mãn luôn là lũy thừa của 2 hay 𝑝 = 2𝐷. 2.2.3.1 Tư tưởng thuật toán 𝑛 Quá trình phân chia dữ liệu: Phân chia 𝑛 phần tử của mảng A cho 𝑝 bộ xử 𝑝 lí. Mỗi bộ xử lí sẽ chứa phần tử. Quá trình thực thi thuật toán: Việc song song hóa được thực hiện qua 𝐷 vòng lặp, tại vòng lặp thứ 𝑖 (1 ≤ 𝑖 ≤ 𝐷) sẽ trải qua các bước sau: Bước 1. Một bộ xử lí lựa chọn ra một phần tử bất kỳ từ dãy con của nó làm phần tử chốt và truyền phần tử chốt này đến tất cả các bộ xử lí còn lại. Việc chọn ra phần tử chốt có thể chọn phần tử đầu tiên hoặc phần tử bất kỳ trong mảng của bộ xử lí này. Bước 2. Dựa vào phần tử chốt, các bộ xử lí sẽ phân hoạch các phần tử của mình thành hai phần, phần nhỏ hơn hoặc bằng chốt và phần còn lại là các phần tử lớn hơn chốt. Thuật toán tiến hành ghép cặp các bộ xử lí để trao đổi dữ liệu. Tại vòng lặp thứ 𝑖 (1 ≤ 𝑖 ≤ 𝐷) những bộ xử lí mà chỉ khác nhau duy nhất một bit ở vị trí thứ 𝑖 sẽ được ghép cặp với nhau. Bước 3. Sau khi các bộ xử lí phân hoạch và ghép cặp, các bộ xử lí trong một cặp sẽ xảy ra quá trình trao đổi dữ liệu. Những phần tử mà có giá trị nhỏ hơn chốt phải được chuyển về bộ xử lí có bit thứ 𝑖 = 0 (bit thấp), những phần tử lớn hơn chốt được chuyển về bộ xử lí có bit thứ 𝑖 = 1 (bit cao). Sau bước này, dữ liệu ban đầu được chia thành hai phần, phần đầu tiên là phần chứa các phần tử có giá trị nhỏ hơn chốt, những phần tử này sẽ nằm trên các 𝑝
bộ xử lí có bit thứ 𝑖 = 0 và sẽ chỉ có
2 bộ xử lí như vậy, phần còn lại sẽ chứa những 36 phần tử có giá trị lớn hơn chốt. Khối hypercube 𝐷 chiều lúc này sẽ được chia thành 2 khối Hypercube con với kích thước 𝐷 − 1 chiều. Tiếp tục sử dụng thủ tục đệ quy cho hai Hypercube con 𝐷 − 1 chiều này. Sau khi thực hiện xong 𝐷 vòng lặp, mỗi bộ xử lí sẽ sắp xếp nội bộ phần tử của mình bằng cách sử dụng thuật toán QuickSort tuần tự, sau đó truyền các phần này về một bộ xử lí gốc để ghép nối thành mảng được sắp xếp. Hình dưới đây minh họa quá trình thực hiện thuật toán Parallel Quicksort trong trường hợp sử dụng 4 bộ xử lí, với khối Hypercube 2 chiều 𝐷 = 2. Bước 1. BXL P00 lựa chọn một
phần tử chốt và truyền phần tử
chốt đến các BXL còn lại Vòng lặp 1:
P00 < P00 > Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau P01
P10
P11 > < > < < > P10
P11 Nửa thấp Bước 3. Các BXL trao đổi các
phần tử, phân Hypercube ban
đầu thành 2 Hypercube con P01 Nửa cao P11
Vòng lặp 2: P00 Nửa thấp Bước 1. Lần lượt BXL P00 và
P10 lựa chọn phần tử chốt để
truyền cho P01 và P11 P01 P10 Nửa cao P11 37 P00
P01
P10 < P00 > Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau P01 > < > P10 < < > P11 Nửa thấp P00 Bước 3. Các BXL trao đổi các
phần tử. Vòng lặp 2 kết thúc P01 Nửa cao P10 Nửa thấp P11 Nửa cao P00 Quicksort thuật P01 Quicksort Sau khi kết thúc 2 vòng lặp, các
BXL sắp xếp tuần tự các phần tử
của mình bằng
toán
Quicksort tuần tự P10 Quicksort P11 Quicksort Hình 2.2 Minh họa thuật toán ParallelQuickSort 2.2.3.2 Đánh giá độ phức tạp Với 𝑛 là số phần tử của mảng , 𝑝 là số bộ xử lí. Khi đó độ phức tạp về thời gian chạy của Parallel Quicksort là [7]: 𝑇(𝑛, 𝑝) = 𝑂( log ) + 𝑂( log 𝑝) + 𝑂(log 𝑝2) 𝑛
𝑝 𝑛
𝑝 𝑛
𝑝 38 Mảng A={75, 91, 15, 64, 24, 25, 88, 54, 50, 12, 47, 72, 65, 54, 66, 22, 83, 66, 67, 0, 70, 98, 99, 82, 20, 40, 89, 47, 19, 61, 86, 85}. Số bộ xử lí 𝑝 =4. Quá trình thực hiện thuật toán Parallel Quicksort như sau: P00 Ban đầu, phân chia các phần tử cho các bộ xử lí: P01 75 91 15 64 21 8 88 54 P10 50 12 47 72 65 54 66 22 P11 83 66 67 0 70 98 99 82 20 40 89 47 19 61 86 85 Thuật toán tiếp tục trải qua hai vòng lặp. Tại vòng lặp 1: P00 P01 75 91 15 64 21 8 88 54 Bước 1. Bộ xử lí P00 lựa chọn
một phần tử chốt, sau đó truyền
phần tử chốt này cho 3 BXL còn
lại. P10 50 12 47 72 65 54 66 22 P11 83 66 67 0 70 98 99 82 20 40 89 47 19 61 86 85 P00 P01 75 15 64 21 8 54 91 88 Bước 2. Các bộ xử lí phân hoạch
mảng thành hai phần lớn hơn chốt
và nhỏ hơn chốt, sau đó ghép cặp
với nhau P10 50 12 47 72 65 54 66 22 P11 66 67 0 70 83 98 99 82 39 20 40 4719 61 89 86 85 P00 Nửa
nhỏ P01 Bước 3. Các bộ xử lí thực hiện quá
trình trao đổi phần dữ liệu đã phân
hoạch. Chia Hypercube thành hai
Hypercube con. 7515 64 218 54 66 67 0 70 P10 50 12 47 72 65 54 66 22 20
40 47 19 61 Nửa
lớn P11 83 98 99 82 91 88 Vòng lặp 2: 89 86 85 P00 P01 Bước 1. Bộ xử lí P00 và P10 lựa
chọn ngẫu nhiên ra một phần tử
rồi truyền cho các bộ xử lí tương
ứng. 7515 64 218 54 66 67 0 70 P10 50 12 47 72 65 54 66 22 20
40 47 19 61 P11 89 86 85 83 98 99 82 91 88 P00 Bước 2. Các bộ xử lí phân hoạch
mảng thành hai phần, sau đó
ghép cặp các BXL P01 15 21 8 0 75 64 54 66 67 70 12 20 19 50 47 72 65 54 66
22 40 47 61 P10 P11 83 82 91 88 98 99 89 86 85 P00 Bước 3. Các bộ xử lí tiến hành
truyền dữ liệu. Vòng lặp 2 kết
thúc. P01 15 218 0 12 20 19 50 47 72 65 54 66 22 40 47
61 75 64 54 66 67 70 P10 P11 83 82 91 8889 86 85 40 98 99 P00 Kết thúc thuật toán: Các BXL sử
dụng Quicksort tuần tự để sắp
xếp lại phần tử của mình. P01 0 8 12 15 19 20 21 P10 22 40 47 47 50 54 54 61 64
65 66 66 67 70 72 75 P11 82 83 85 86 88 89 91 Hình 2.3 Ví dụ thuật toán ParallelQuickSort 98 99 HyperQuicksort là thuật toán sắp xếp nhanh phát triển trên mô hình mạng Hypercube, nó có thể được sử dụng cho bất kỳ một hệ thống truyền thông điệp nào có số phần tử xử lí là lũy thừa của 2 [7]. Sự khác nhau chủ yếu giữa HyperQuicksort và ParallelQuickSort là ở phương thức lựa chọn phần tử chốt. Ngay tại bước đầu tiên, mỗi bộ xử lí sau khi được phân chia phần tử, chúng sẽ sắp xếp nội bộ các phần tử của chúng bằng cách sử dụng thuật toán sắp xếp tuần tự Quicksort. Sau đó, một bộ xử lí sẽ lấy phần tử trung vị trong khối của nó làm phần tử chốt, và thường nó được lấy ra từ bộ xử lí đầu tiên trong hệ thống. Các bước lặp tiếp theo hoàn toàn tương tự như với thuật toán ParallelQuicksort. Tuy nhiên, khác với ParallelQuicksort, phép chia tách và hợp nhất các phần tử trên các BXL luôn đảm bảo quá trình phân một Hypercube thành hai Hypercube con mà mỗi bộ xử lí chứa một danh sách đã sắp xếp và giá trị lớn nhất trong BXL chứa bit thấp là nhỏ hơn giá trị nhỏ nhất trong BXL chứa bit cao. Minh họa thuật toán HyperQuicksort trong trường hợp có 4 bộ xử lí. Ta phải thực hiện thuật toán qua 2 vòng lặp. Cụ thể như sau: Ban đầu, phân chia các phần tử cho các BXL. Các bộ xử lí sắp xếp nội bộ các phần 41 tử của mình. P00 Quicksort P01 Quicksort Sau khi nhận được các phần tử, các
BXL sắp xếp nội bộ các phần tử của
mình. Thuật toán tiếp tục trả qua 2
vòng lặp P10 Quicksort P11 Quicksort P00 Bước 1. BXL P00 truyền phần
tử trung vị đến các BXL còn lại P01 P10 P11 < P00 > Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau P01 > < > P10 < < > P11 P00 Nửa thấp Bước 3. Các BXL trao đổi các
phần tử, phân Hypercube ban
đầu thành 2 Hypercube con P01 P10 Nửa cao P11 Vòng lặp 2 P00 Nửa thấp Bước 1. Lần lượt BXL P00 và
P10 lựa chọn phần tử trung vị của
mình để truyền cho P01 và P11 P01 P10 Nửa cao P11 42 < P00 > Bước 2. Các BXL phân hoạch
phần tử thành hai phần và tiến
hành ghép cặp với nhau P01 > < > P10 < < P11 > Nửa thấp P00 Bước 3. Các BXL trao đổi các
phần tử. Vòng lặp 2 kết thúc P01 Nửa cao P10 Nửa thấp P11 Nửa cao P00 Sorted Kết thúc vòng lặp, các phần
được sắp xếp. P01 Sorted P10 Sorted P11 Sorted Hình 2.4 Minh họa thuật toán HyperQuickSort 2.2.4.2 Đánh giá độ phức tạp Gọi 𝑛 là tổng số phần tử của mảng và gọi 𝑝 là số thành phần xử lí.[7] 43 log 𝑂( ) - Quicksort ban đầu có độ phức tạp là :
𝑛
𝑝 𝑛
𝑝 - Tổng thời gian để truyền thông cho log 𝑝 bước trao đổi là: 𝑂( log 𝑝) 𝑛
𝑝 - Tổng thời gian truyền thông giá trị phần tử chốt là 𝑂(log 𝑝) 2.2.4.3 Ví dụ Mảng 𝐴 ={75, 91, 15, 64, 24, 8, 88, 54, 50, 12, 47, 72, 65, 54, 66, 22, 83, 66, 67, 0, 70, 98, 99, 82, 20, 40, 89, 47, 19, 61, 86, 85}. Số bộ xử lí 𝑝 = 4. Quá trình thực hiện thuật toán HyperQuickSort được minh họa bằng các bước dưới đây: P00 75 91 15 64 21 8 88 54 P01 Quá trình phân chia các
phần tử: Ban đầu, phân chia
các phần tử cho các BXL. 50 12 47 72 65 54 66 22 P10 P11 83 66 67 0 70 98 99 82 8 15 21 54 64 75 88 91 P00 P01 20 40 89 47 19 61 86 85 P10 12 22 47 50 54 65 66 72 Các BXL sắp xếp nội bộ các phần
tử của mình bằng cách sử dụng
thuật toán QuickSort tuần tự. Sau
đó thuật toán tiếp tục trải qua hai
vòng lặp: P11 0 66 67 70 82 83 98 99 44 19 20 40 47 61 85 86 89 Vòng lặp 1. P00 8 15 21 54 64 75 88 91 P01 Bước 1. BXL đầu tiên chọn ra
phần tử ở vị trí trung vị làm phần
tử chốt, sau đó truyền phần tử
này đến các BXL còn lại 12 22 47 50 54 65 66 72 P10 0 66 67 70 82 83 98 99 P11 19 20 40 47 61 85 86 89 P00 8 15 21 54 65 75 88 91 P01 P10 Bước 2. Các BXL phân hoạch
các phần tử của mình thành hai
phần, lớn hơn chốt và nhỏ hơn
chốt. Sau đó, các BXL ghép cặp
để chuẩn bị truyền các phần tử 12 22 47 50 54 65 66 72 P11 0 66 67 70 82 83 98 99 19 20 40 47 61 85 86 89 P00 0 8 15 21 54 P01 P10 12 19 20 22 40 47 47 50 54 Bước 3. Các BXL truyền các phần
tử cho nhau theo quy tắc đã xây
dựng. Sau giai đoạn này, khối
Hypercube được phân thành 2
khối Hypercube con. Thuật toán
chuyển sang vòng lặp thứ 2 64 66 67 70 75 82 83 88 91
98 99 P11 61 65 66 72 85 86 89 Vòng lặp 2. P00 0 8 15 21 54 P01 Bước 1. Hai BXL P00 và P10 lựa
chọn phần tử trung vị của mình
để truyền đến các BXL tương
ứng P10 12 19 20 22 40 47 47 50 54 64 66 67 70 75 82 83 88 91
98 99 P11 45 61 65 66 72 85 86 89 P00 0 8 15 21 54 P01 Bước 2. Các BXL phân hoạch
các phần tử của mình thành hai
phần, lớn hơn chốt và nhỏ hơn
chốt. Sau đó, các BXL ghép cặp
đê chuẩn bị truyền các phần tử P10 12 19 20 22 40 47 47 50 54 P11 64 66 67 70 75 82 83 88 91
98 99 61 65 66 72 85 86 89 P00 Bước 3. Các BXL truyền các
phần tử cho nhau theo quy tắc đã
xây dựng. Vòng lặp 2 kết thúc. P01 0 8 12 15 19 20 21 22 40 47 47 50 54
54 P10 P11 61 64 65 66 67 70 72 75 82 Hình 2.5 Ví dụ thuật toán HyperQuickSort 83 85 86 88 89 91 98 99 Trên đây là hai thuật toán sắp xếp song song được thực hiện dựa trên những thuật toán tuần tự đã có sẵn (OddEven sort, ParallelQuicksort) và thuật toán song song phát triển từ thuật toán song song đã có(Shellsort, HyperQuicksort). Mỗi thuật toán đều có những ưu và nhược điểm riêng, nếu như OddEven sort và Shellsort là hai thuật toán đơn giản dễ cài đặt thì ParallelQuicksort và HyperQuicksort lại là những thuật toán đem lại hiệu quả cao hơn và song song hóa tốt hơn. Nhưng để ý một điều rằng, tuy phù hợp với song song hóa nhưng ParallelQuickSort và HyperQuicksort lại cần phải có một điều kiện bắt buộc là số bộ xử lí sử dụng luôn phải là lũy thừa của 2. Mặt khác, với Parallel QuickSort khi thuật toán bị rơi vào trường hợp suy biến tức là thuật toán chọn phần tử chốt không tốt, sẽ dẫn đến sự mất cân bằng trong quá trình phân chia các phần tử trên các bộ xử lí khiến các bộ xử lí có thể làm việc không cân bằng nhau khi đó thời gian chạy 46 chương trình sẽ trở nên chậm. Phần cuối của chương này xin được đề cập đến một thuật toán sắp xếp song song mà có thể khắc phục được nhược điểm của Parallel Quicksort, thuật toán này không dựa trên việc song song hóa thuật toán tuần tự đã có và cũng không phát triển từ một thuật toán song song đã được đưa ra, và có thể phù hợp với hầu hết các hệ thống song song. 2.3 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 toán sắp xếp song song đã được trình bày ở trên, PSRS là một thuật toán sắp xếp song song với nhiều ưu điểm [9]. Nó giữ nguyên đượ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 toán sắp xếp tuần tự, một quá 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 toá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 ý. 2.3.1 Tư tưởng thuật toán Thuật toán PSRS bao gồm có 6 pha phân biệt. Nó 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 𝑝 bộ xử lí và sắp xếp mảng có kích cỡ 𝑛, khi đó, thuật toán trải qua 6 bước thực hiện như sau: Bước 1. Khởi tạo ban đầu Với 𝑝 bộ xử lí, lựa chọn một bộ xử lí làm gốc (bộ xử lí 0), khởi tạo bộ dữ liệu với kích cỡ 𝑛. Bước 2. Phân chia dữ liệu, sắp xếp cục bộ và lựa chọn các mẫu chuẩn. 𝑛 Phân chia dữ liệu ban đầu cho 𝑝 bộ xử lí. Mỗi bộ xử lí sẽ sắp xếp cục bộ tập 𝑝 47 dữ liệu với kích thước bằng cách sử dụng thuật toán QuickSort tuần tự. Sau đó, mỗi bộ xử lí sẽ lựa chọn ra 𝑝 phần tử từ tập dữ liệu của mình để làm mẫu. Các mẫu được lựa chọn có khoảng cách đều nhau. Cụ thể, các phẩn tử ở vị trí 1, 𝑤 + 1, 2𝑤 + 𝑝2]được chọn để làm mẫu. 1, . . . , (𝑝 − 1)𝑤 + 1 với 𝑤 = [ 𝑛 Bước 3. Tập hợp và trộn các mẫu, lựa chọn phần tử chốt. Bộ xử lí gốc sẽ tập hợp tất cả các phần tử đã được chọn ra làm mẫu ở 𝑝 bộ xử lí. Điều quan trọng cần để ý đó là mỗi tập hợp các phần tử mẫu tại mỗi bộ xử lí đã được sắp xếp. Có 𝑝 tập hợp được sắp xếp và sử dụng thuật toán trộn để trộn chúng lại với nhau. Từ 𝑝2 phần tử đã sắp xếp này, lựa chọn ra 𝑝 − 1 giá trị để làm phần tử chốt bằng cách lấy ra các phần tử có chỉ số 𝑝 + 𝑓, 2𝑝 + 𝑓, … , (𝑝 − 1)𝑝 + ⌋. Tiếp theo, bộ xử lí gốc sẽ truyền thông các phần tử chốt này đến 𝑓 với 𝑓 = ⌊𝑝
2 𝑝 − 1 bộ xử lí còn lại. Bước 4. Phân chia dữ liệu cục bộ tại các bộ xử lí dựa trên các phần tử chốt. Mỗi bộ xử lí sẽ phân chia dữ liệu cục bộ đã được sắp xếp của nó ra thành 𝑝 phân lớp dựa vào 𝑝 − 1 phần tử chốt đã chọn. Bước 5. Tập hợp và trộn các phân lớp tại các bộ xử lí. Bộ xử lí thứ 𝑖 sẽ tập hợp dữ liệu trong phân lớp thứ 𝑖(1 ≤ 𝑖 ≤ 𝑝) từ các bộ xử lí khác. Mỗi phân lớp này sẽ được sắp xếp và trộn lại với nhau. Bước 6. Tập hợp dữ liệu cuối cùng Bộ xử lí gốc sẽ tập hợp tất cả dữ liệu và lắp ráp các danh sách được sắp xếp trên mỗi bộ xử lí thành danh sách được sắp xếp gồm n phần tử ban đầu. Thuật toán kết thúc. 48 Thuật toán có thể được minh họa bằng hình dưới đây: Dữ liệu ban đầu Phân chia dữ liệu P2 P0 P1 Sắp xếp cục bộ P2 P0 P1 Lựa chọn mẫu Trộn và sắp xếp mẫu Chọn ra p-1 phần tử chốt Truyền thông chốt Phân lớp dữ liệu Truyền và
trộn các
phân lớp Tập hợp kết quả Hình 2.6 Minh họa thuật toán PSRS 49 Về độ phức tạp của thời gian tính toán, trong bước thứ 2 của giải thuật, mỗi 𝑛 bộ xử lí thực hiện sắp xếp dữ liệu bằng QuickSort. Kích thước của dữ liệu trên mỗi 𝑝 bộ xử lí là và sau đó chọn ra 𝑝 phần tử làm mẫu. Do đó thời gian yêu cầu tính toán trong bước này là: 𝑛 𝑂 ( log + 𝑝). 𝑛
𝑝 𝑛
𝑝 𝑝 𝑛
cần thiết là 𝑂 ( ). 𝑝 Trong bước 4, mỗi bộ xử lí phân chia phần tử được sắp xếp. Thời gian Trong bước thứ 5, bộ xử lí thứ 𝑖 trộn 𝑝 danh sách được sắp xếp. Mỗi danh 𝑛 sách này được tạo ra bằng cách sử dụng các phần tử chốt được chọn trong pha 3, 𝑝2 mà sau khi trộn mỗi 𝑛 trong trường hợp lý tưởng, mỗi danh sách có kích thước 𝑝 𝑛 danh sách trên mỗi bộ xử lí sẽ có kích cỡ . Sử dụng thuật toán trộn trong trường 𝑝 hợp này yêu cầu thời gian là 𝑂( log 𝑝).Tổng thời gian tính toán sẽ là: 𝑛 𝑛 𝑂 ( log + 𝑝 + + log 𝑝 ) 𝑛
𝑝 𝑛
𝑝 𝑛
𝑝 𝑛
𝑝 𝑝 𝑝2 phần 𝑛 Xét về thời gian truyền thông, trong bước 5, mỗi bộ xử lí gửi − 𝑝 𝑛 .Trong bước cuối cùng, bộ xử tử, do đó, tổng số phần tử cần truyền thông là 𝑛 − 𝑝 phần tử. Do đó độ phức tạp thời gian truyền thông là: lí gốc tập hợp 𝑛 − 𝑂(𝑛 − ) 𝑛
𝑝 50 2.3.3 Ví dụ minh họa Thực hiện thuật toán sắp sếp PSRS trên mảng A có 36 phần tử với 3 bộ xử lí. Quá 2.3.4 Ví dụ minh họa 51 trình sắp xếp được thực hiện theo thứ tự dưới đây: 36 khóa 16 2 17 24 33 28 30 1 0 27 9 25 34 23 19 18 11 7 21 13 8 35 12 29 6 3 4 14 22 15 32 10 26 31 20 5 P1 P2 P3 16 2 17 24 33 28 30 1 0 27 9 25 34 23 19 18 11 7 21 13 8 35 12 29 6 3 4 14 22 15 32 10 26 31 20 5 Sắp xếp cục bộ
0 1 2 9 16 17 24 25 27 28 30 33 Sắp xếp cục bộ
7 8 11 12 12 18 19 21 23 29 34 35 Sắp xếp cục bộ
3 4 5 6 10 14 15 20 22 26 31 32 Lựa chọn mẫu Lựa chọn mẫu Lựa chọn mẫu 0 16 27 7 12 23 3 10 22 0 16 27 7 12 23 3 10 22 BXL P1 tập hợp các phần tử mẫu 0 3 7 10 13 16 22 23 27 Sắp xếp nội bộ phẩn tử mẫu Lựa chọn ra 2 phần tử chốt 10 22 10 22 22 10 26 31 32 14 15 20 22 3 4 5 6 10 17 16 0 1 2 9 24 25 27 28 30 33 7 8 21 11 12 13 18 19 23 29 34 35 P1 P2 Kết hợp lại các vùng P3 Kết hợp lại các vùng Kết hợp lại các vùng Phần 1 P1 Phần 2 P1 Phần 3 P1 0 1 2 9 24 25 27 28 30 33 Phần1 P2 Phần 2 P2 Phần 3 P2 Phần1 P3 Phần 2 P3 Phần 3 P3 7 8
3 4 5 6 10 16 17
11 12 13 18 19 21
14 15 20 22 Kết quả cuối cùng khi trộn các phân vùng tại P1 Kết quả cuối cùng khi trộn các phân vùng tại P1 23 29 34 35
26 31 32
Kết quả cuối cùng khi trộn các phân vùng tại P1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 51 10 22 2.4 Kết luận chương Chương 2, phần thứ nhất của chương đã đưa ra các chiến lược thiết kế cho bài toán sắp xếp trên hệ thống song song, các chiến lược được áp dụng một cách linh hoạt cho các thuật toán sắp xếp song song đã được trình bày ở trên. Phần thứ hai của chương đã tập trung đi trình bày chi tiết về các thuật toán sắp xếp song song về tư tưởng của thuật toán, cách thực hiện thuật toán, thuật toán và các ví dụ chi tiết minh họa cho từng thuật toán. Ngoài ra, qua đó có thể nhận thấy được sự khác nhau trong các thuật toán sắp xếp song song, mỗi thuật toán đều có những ưu và nhược điểm riêng của mình. Bằng việc phân tích một cách chi tiết thuật toán song song PSRS, nhận thấy rằng đây là một thuật toán hay với nhiều ưu điểm cả về độ phức tạp và thủ tục cài đặt, phù hợp với nhiều mô hình song song hiện tại. Do đó trong chương tiếp theo, phần thực nghiệm của luận văn xin lựa chọn ra thuật toán Parallel Quicksort và thuật toán PSRS để cài đặt thử nghiệm trên hệ thống song song 52 cụ thể để đưa ra những đánh giá và so sánh độ hiệu quả của hai thuật toán này. Nội dung chính của chương trình bày thủ tục và các hàm cần thiết để cài đặt thuật toán PSRS và ParallelQuicksort cùng với các kết quả thực nghiệm khi chạy thuật toán này đồng thời đưa ra sự so sánh kết quả thực hiện giữa thuật toán PSRS và thuật toán ParallelQuicksort khi cùng chạy trên một hệ thống để có thể đánh giá một cách tổng thể tính đúng đắn cũng như hiệu quả của thuật toán. 3.1 Môi trường và phương pháp thực nghiệm 3.1.1 Môi trường thực nghiệm Quá trình thực nghiệm được tiến hành trên hệ thống IBM Linux Cluster 1350 của trung tâm Tính toán Hiệu Năng Cao – Trường đại học Khoa học Tự nhiên – - 8 node tính toán, mỗi node gồm 2 chip Intel Xeon Dual Core 3.2 GHz, 2 GB ĐHQGHN với cấu hình như sau: RAM, 1x36 GB HDD, DVD ROM. Tổng năng lực tính toán của 8 node là khoảng - 2 node phục vụ lưu trữ (Storage1 và Storage2), mỗi node gồm 2 chip Intel 51.2 Gflops. - 1 node đóng vai trò quản lí (MGT) bao gồm chip Intel Xeon Dual Core 3.2 Xeon Dual Core 3.2 GHz, 3 GB RAM, 4x72 GB HDD. - Năng lực lưu trữ: thiết bị lưu trữ dùng chung EXP400 với 10x73 GB HDD GHz, 3 GB RAM, 2x36 GBHDD. - Các node chạy HĐH Redhat Enterprise Linux 3.0 và được kết nối với nhau SCSI 320 MBps 15KRpm, dùng hệ thống chia sẻ file: GPFS cho Linux v2.3.0.5. thông qua mạng Gethernet. Các thuật toán được lập trình bằng ngôn ngữ C++ sử dụng thư viện lập trình song song MPI. Thực nghiệm nhằm mục đích kiểm tra sự song song hóa của thuật toán PSRS và kiểm nghiệm và so sánh thời gian thực thi của thuật toán này so với thuật toán ParallelQuicksort (Thuật toán ParallelQuickSort được xây dựng trên mô 53 hình mạng Hypercube tuy nhiên vẫn có thể chạy thực nghiệm trêm mô hình MPI-Mô hình truyền thông điệp, bởi lẽ quá trình truyền thông điệp chính là quá trình gửi nhận dữ liệu giữa các nút trên mạng Hypercube). 3.1.2 Phương pháp thực nghiệm Về nguyên tắc lấy số liệu thực nghiệm: - Cố định số phần tử của mảng thay đổi số bộ xử lí sử dụng(2, 4, 8) 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. - Thay đổi số phần tử của mảng (105, 106, 107) và chạy trên cùng số bộ xử lí, 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. 3.2 Các kết quả thực nghiệm 3.2.1 Kết quả thực nghiệm khi chạy trên thuật toán PSRS Thời gian chạy trung bình của thuật toán
PSRS(giây) Input
Size T.sequency
(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 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) 107 4.6197 3.1352 2.5169 2.1608 2.1887 Bảng 1. So sánh kết quả chạy thuật toán PSRS Qua thực nghiệm, trước hết nhận thấy rằng thuật toán PSRS hoàn toà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ả thực nghiệm, 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ử 𝑛 = 100000 thì thời gian chạy song song nhanh gấp 1.5 lần, với số phần 54 tử 𝑛 = 1000000 thì thời gian chạy song song nhanh gấp 1.36 lần, với 𝑛 = 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ử 𝑛 = 100000 thì thời gian chạy song song nhanh gấp 3 lần, với số phần tử 𝑛 = 1000000 thì thời gian chạy song song nhanh gấp 2.15 lần, với 𝑛 = 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ử 𝑛 = 1000000 thì thời gian chạy song song nhanh gấp 1.95 lần, với 𝑛 = 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 toá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ả thực nghiệm, 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 toá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 đó luôn luôn 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 Hình 3.1 Biểu đồ so sánh thời gian chạy thuật toán PSRS 55 song song. Hình 3.2 Biểu đồ so sánh thời gian chạy của các BXL với cùng số phần tử N=106 Thời gian chạy trung bình của thuật toán song song(giây) Input PSRS PQ PSRS PQ PSRS PQ Size P=2 P=2 P=4 P=4 P=8 P=8 105 0.0285 0.009 0.0183 0.007 0.0514 0.0466 106 0.3343 0.1043 0.1947 0.0873 0.2146 0.1204 107 3.1352 0.9525 2.1608 0.8029 2.1887 1.2908 Bảng 2. So sánh thời gian chạy của PSRS và Parallel Quicksort 56 P: Số bộ xử lí của hệ thống Input Size: Kích thước đầu vào(Số phần tử ) Hình 3.3 Biểu đồ so sánh thời gian của PSRS và PQ Khi chạy trên cùng một hệ thống, thuật toán PSRS và Parallel Quicksort đều cho những kết quả khả quan. Với dữ liệu đầu vào như trên thì cả hai thuật toán đều nên sử dụng 4 bộ xử . Qua biểu đồ trên ta thấy rằng, trong trường hợp trung bình, tức là thuật toán Parallel Quicksort không bị suy biến, thì thuật toán Parallel Quicksort cho kết quả tốt hơn thuật toán PSRS. Trong chương 3, em đã tập trung vào xây dựng và cài đặt chương trình thử nghiệm tại trung tâm Tính toán Hiệu Năng Cao – Trường đại học Khoa học Tự nhiên – ĐHQGHN. Với hai thuật toán được cài đặt, khi chạy thử nghiệm đã thu được kết quả khá khả quan. Trước hết có thể khẳng định rằng hai thuật toán này hoàn toàn có thể thực hiện song song hóa được, hơn thế nữa, hai thuật toán khi chạy đều cho ra thời gian thực thi nhanh hơn nhiều so với việc chạy thuật toán tuần tự. Qua đó, em nhận thấy được rằng việc lựa chọn số bộ xử lí để chạy chương trình có ảnh hưởng rất lớn đến kết quả của chương trình. Cần xác định số bộ xử lí phù hợp với từng bài toán 57 để có được kết quả khả quan nhất. Luận văn đã trình bày một cách khái quát nhất về cơ sở của xử lí song song, các mô hình song song thường được sử dụng hiện nay. Nội dung chủ yếu của luận văn tập trung vào việc hệ thống hóa các thuật toán sắp xếp đã được nghiên cứu, phân tích được đặc điểm của các thuật toán, đưa ra được cái nhìn bao quát nhất về các thuật toán sắp xếp cơ bản. Lấy đó là chủ đề để nghiên cứu của luận văn, luận văn đã được đưa ra với cấu trúc gồm có 3 chương. Trong đó, chương 1 của luận văn trình bày một cách tổng quan nhất về lý thuyết xử lí song song, các mô hình song song phổ biến và tập trung mô tả bài toán sắp xếp, việc hệ thống hóa lại hầu hết các thuật toán sắp xếp và đưa ra những so sánh trên các thuật toán sắp xếp là một điểm nổi bật của chương 1. Chương 2 của luận văn tập trung vào việc tìm hiểu vấn đề song song hóa các thuật toán sắp xếp cơ bản. Đây là một trong những vấn đề trọng tâm của luận văn. Các thuật toán sắp xếp song song đã được trình bày hết sức chi tiết từ tư tưởng đến thuật toán và các ví dụ minh họa để làm rõ nét hơn về các thuật toán đó. Với ba thuật toán điển hình đó là Parallel Quicksort, HyperQuicksort và PSRS, đây sẽ là ba thuật toán giúp cải thiện tốc độ của việc sắp xếp một cách tốt nhất khi thực hiện trên hệ thống song song. Qua quá trình tính toán và thực nghiệm, luận văn đã đưa ra được những kết quả để có thể khẳng định rằng việc song song hóa trên các thuật toán trên là hoàn toàn chính xác và thu được thời gian xử lí tốt hơn những giải thuật tuần tự đã có rất nhiều. Với kiến thức của bản thân còn chưa cao và chưa có nhiều thời gian để nghiên cứu nhiều thuật toán song song khác, vì vậy trong tương lai, em sẽ tiếp tục tìm hiểu những thuật toán song song khác, không chỉ áp dụng trên các bài toán sắp xếp mà còn áp dụng được trên nhiều lĩnh vực khác nữa để từ đó có thể bổ sung thêm kiến thức cũng như kinh nghiệm cho bản thân về khả năng phân tích cũng như xử lí bài toán 58 trên hệ thống song song để áp dụng trong các lĩnh vực mà xã hội đang cần. TÀI LIỆU THAM KHẢO Tiếng việt [1]. Lê Huy Thập (2010), “ Cơ sở lý thuyết song song”, NXB Công nghệ thông tin và truyền thông , Hà Nội. [2]. Lê Minh Hoàng (2009), “Giải thuật và lập trình”, Đại học sư phạm Hà Nội I. Tiếng anh [3]. Grama A., A. Gupta, G. Karypis, V. Kumar (2003), “Introduction to Parallel Computing”, Addison Wesley. [4]. M. J. Quinn(2003), “Parallel Programming in C with MPI and OpenMP”, Tata McGraw Hill Publications . [5]. Madhavi Desai, Viral Kapadiya, “Performance Study of Efficient Quick Sort and Other Sorting Algorithms for Repeated Data”, National Conference on Recent Trends in Engineering & Technology, 13-14 May 2011. [6]. D. E. Knuth(1998), “The Art of Computer Programming”, Volume 3: Sorting and Searching, Second ed. Boston, MA: Addison-Wesley. [7]. I.S. Rajput, B. Kumar, TinKu Singh, “Performance comparison of Sequential Quicksort and Parallel Quicksort Algorithms”, International Journal of Computer Applications (0975-8887) Volume 57_No9, November 2012. [8]. Quinn M.J (1989), “Analysis and Benchmarking of two parallel sorting algorithms: HyperQuicksort and QuickMerge”, University of New Hampshire, Durham, NH 03824, USA. [9]. Xiaobo Li, Paul Lu, Jonathan Schaeffer, John Shillington, Pok Sze Wong (2004), “On the Versatility of parallel sorting by Regular Sampling”, 59 University of Alberta, EdmonTon, Alberta, Canada.CHƯƠNG 2. MỘT SỐ THUẬT TOÁN SONG SONG CHO
BÀI TOÁN SẮP XẾP
2.1 Chiến lược song song cho bài toán sắp xếp
2.2 Thuật toán sắp xếp song song phát triển dựa trên thuật toán tuần tự
2.2.1 Thuật toán sắp xếp hoán vị chẵn lẻ (OddEvenSort)
2.2.1.1 Tư tưởng thuật toán
2.2.3.3 Ví dụ
2.2.4 Thuật toán HyperQuicksort
2.2.4.1 Tư tưởng thuật toán
Vòng lặp 1
2.3.2 Đánh giá độ phức tạp
CHƯƠNG 3. ỨNG DỤNGLẬP TRÌNH SONG SONGCÀI ĐẶT THUẬT
TOÁN SẮP XẾP PSRS VÀ PARALLELQUICKSORT
3.2.2 So sánh kết quả giữa thuật toán PSRS và ParallelQuicksort(PQ)
3.3 Kết luận chương
KẾT LUẬN
