Bài giảng Xử lý song song

N GiẢI ĐƢỢC TRÊN MÔ HÌNH PRAM 
7/17/2010
51
301
1. Khối các lệnh song song:
Parbegin và Parend (Cobegin và Coend): Giả sử các lệnh S1,
S2, … Sn được thực hiện trên n tiến trình riêng biệt
5.5 CÁC CẤU TRÚC LỆNH SONG SONG 
Parbegin
S1;
S2;
...
Sn;
Parend
Cobegin
S1;
S2;
...
Sn;
Coend
302
2. Cấu trúc forall (parfor)
Nhiều khi một số tiến trình (câu lệnh) tương tự nhau cần phải 
bắt đầu thực hiện và cùng lặp lại một số lần. Điều này có thể
thực hiện được bằng cấu trúc forall
5.5 CÁC CẤU TRÚC LỆNH SONG SONG 
Forall(i=0;i<n; i++){
S1;
S2;
...
Sn;
}
Parend
For(i=0;i<n;i++){
S1;
S2;
...
Sn;
} 
In parallel
Hoặc 
303
1. Thuật toán sắp xếp theo hạng
Bài toán: cho mảng a[n] các số nguyên. Hãy sắp xếp tăng
dần các phần tử của mảng.
Ý tƣởng thuật toán: Trong cách sắp xếp này, số những số
nhỏ hơn một số đã chọn sẽ được đếm. Số đếm được sẽ
xác định vị trí của phần tử đã được chọn trong danh sách
cần sắp xếp. Giả sử có n số được lưu giữ trong mảng a[n]
và kết quả sau khi sắp xếp là b[n].
Thuật toán tuần tự:
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
for(i = 0; i < n; i++){
x = o;
for(j = 0; i < n; j++)
if(a[i] > a[j]) x++;
b[x] = a[i];
}
Độ phức tạp O(n2)
304
Thuật toán song song-Sử dụng n bộ xử lý 
Giả sử ta có n bộ xử lý. Mỗi bộ xử lý được cấp một số trong
dãy số cho trước và nó phải tìm vị trí của số đó trong dãy
được sắp xếp.
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
for(i=0; i<n; i++){ // n bộ xử lý thực hiện song song 
x = o; 
for(j=0; i<n; j++)
if(a[i]>a[j]) x++; // đếm số phần tử nhỏ hơn
b[x] = a[i]; // Sao sang bảng được sắp xếp
}
Nhận xét: Tất cả n bộ xử lý thực hiện song song nên thuật
toán có độ phức tạp là O(n) (tuyến tính).
(Xem tài liệu Thuật toán song song-Sử dụng n2 bộ xử lý)
305
2. Thuật toán sắp xếp so sánh và đổi chổ
Bài toán: cho mảng a[n] các số nguyên. Hãy sắp xếp tăng 
dần các phần tử của mảng.
Ý tƣởng thuật toán: so sánh hai phần tử liền kề nhau. Nếu 
chưa theo thứ tự thì đổi chổ nhau. Quá trình lặp lại cho đến 
khi nào không còn cặp nào không thỏa mãn thì dừng. 
Thuật toán tuần tự:
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
for(i=n-1; i > 0; i--){
for(j=0; j < i; i++){
k = j + 1;
if(a[j] > a[k]){
temp = a[j];
a[j] = a[k];
a[k] = temp;
}
}
}
306
2. Thuật toán sắp xếp so sánh và đổi chổ
Thuật toán song song:
Ý tƣởng thuật toán 
• Dùng n tiến trình kết hợp theo nguyên lý hình ống để sắp 
xếp mảng a[n]
• Hệ thống được chia thành 2 pha: pha chẵn và pha lẻ
- Pha chẵn: gồm các tiến trình được đánh số chẵn so sánh 
với những tiến trình tiếp theo (số lẻ), nếu nó giữ phần tử 
lớp hơn thì trao đổi dữ liệu với tiến trình đó.
- Pha lẻ: các tiến trình được đánh số lẻ hoạt động tương tự 
như trên
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
7/17/2010
52
307
Ví dụ: n=8 và a = (4 , 2 , 7 , 8 , 5 , 1 , 3 , 6) 
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
Pha/TT P0 P1 P2 P3 P4 P5 P6 P7
0 4 2 7 8 5 1 3 6
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 5 7 6 8
6 1 2 3 4 5 6 7 8
7 1 2 3 4 5 6 7 8
Sắp xếp theo nguyên lý hình ống Đổi chổ
Không đổi chổ
308
Thuật toán song song:
Giả sử A lưu dữ liệu ở tiến trình lẻ và B lưu dữ liệu ở tiến trình chẵn
Thuật toán song song theo hình ống được mô tả theo MPI như sau:
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
Pha chẵn
Pi , i = 0, 2, ..., n-2 Pi , i = 1, 3, ..., n-3
recv(&A, Pi+1); send(&A, Pi-1);
send(&B, Pi+1); recv(&B, Pi-1); 
if (A>B) B=A ; if (A>B) A=B ;
Pha lẻ
Pi , i = 1, 3, ..., n-3 Pi , i = 0, 2, ..., n-2
send (&A, Pi+1); recv (&A, Pi-1); 
recv (&B, Pi+1); send(&B, Pi-1); 
if (A>B) A=B ; if (A>B) B=A ;
309
Kết hợp 2 pha ta đƣợc thuật toán song song:
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
Pi , i = 1, 3, ..., n-3 Pi , i = 0, 2, ..., n-2
send(&A,Pi-1); recv(&A,Pi+1);
recv(&B,Pi-1); send(&B,Pi-1); 
if (A>B) A=B ; if (A>B) B=A ;
if (i2){
send(&A,Pi+1); recv(&A,Pi-1);
recv(&B,Pi+1); send(&B,Pi-1);
if (A>B) A=B; if (A>B) B=A;
} }
Nhận xét: thuật toán có độ phức tạp là O(n).
310
3. Thuật toán sắp xếp MergeSort
Bài toán: cho mảng a[n] các số nguyên. Hãy sắp xếp tăng 
dần các phần tử của mảng. 
Ý tƣởng thuật toán (dùng nguyên tắc chia để trị)
• Chia mảng a thành 2 phần
• Mỗi phần lại chia đôi tiếp cho đến khi mỗi phần nhỏ chỉ có 1 
phần tử 
• Từng cặp được ghép lại theo thứ tự sắp xếp
Ví dụ
Mảng a = (4, 2, 7, 8, 5, 1, 3, 6)
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
311
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
63158724
8724 6315
24 87 15 63
4 2 7 8 5 1 3 6
42 87 51 63
8742 6531
87654321
Chia 
đôi 
danh 
sach
Ghép 
kết 
hợp
312
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
Chia danh sách thành từng cặp và phân công cho các BXL
(4, 2, 7, 8, 5, 1, 3, 6) P0
P0 P4
P0 P2 P4 P6
P0 P1 P3 P5P2 P4 P6 P7
P0 P2 P4 P6
P0 P4
P0
Nhận xét:
thuật toán có ĐPT O(nlogn)
7/17/2010
53
313
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
Xác định thời gian truyền thông: tcomm
a. Trong giai đoạn phân chia dữ liệu
Truyền dữ liệu Truyền thông của BXL
• tstartup + (n/2)tdata P0  P4
• tstartup + (n/4)tdata P0  P2; P4 P6
• tstartup + (n/8)tdata P0  P1; P2  P3; P4  P5; P6  P7
b. Trong giai đoạn ghép kết hợp có những sự trao đổi dữ liệu:
• tstartup + (n/8)tdata P0  P1; P2  P3; P4 P5; P6  P7
• tstartup + (n/4)tdata P0  P2; P4  P6
Giả sử có p BXL thì cả hai giai đoạn sẽ thực hiện đƣợc log p bƣớc.
Vậy chi phí truyền thông của cả hai giai đoạn là:
tcomm = 2(tstartup+ (n/2)tdata + tstartup + (n/4)tdata +tstartup + (n/8)tdata …)
= 2(log p)tstartup + 2ntdata
Nhắc lại:
+ tstartup là thời gian cần thiết để gửi những thông điệp
không phải là dữ liệu. Nó bao gồm cả thời gian để đóng gói
thông điệp ở nơi gửi và thời gian mở gói ở nơi nhận. Để
đơn giản chúng ta giả thiết thời gian này là hằng số.
+ tdata là thời gian cần thiết để chuyển một mục dữ liệu
(data item) từ nơi gửi tới nơi nhận, được giả thiết là hàng
số và n là số mục dữ liệu được trao đổi tro g hệ thống.
314
• Việc tính toán chỉ thực hiện việc ghép các danh sách con 
để tạo danh sách lớn hơn.
• Việc ghép 2 danh sách con được thực hiện bằng cách 
duyệt lần lượt từ đầu hai danh sách để tìm phần tử nhỏ 
hơn đưa vào danh sách mới.
• Để ghép 2 danh sách con có n phần tử thì cần nhiều nhất 
2n-1 bước so sánh.
c. Xác định thời gian 
tính toán: tcomp
Nhận xét 
315
Xác định thời gian tính toán
Tcomp=1 P0, P2, P4, P6
Tcomp=3 P0, P2
Tcomp=7 P0
Tổng quát,
Tcomp= 1 + 3 + ... + (2i - 1), i = 1, ..., logn
Vậy độ phức tạp thời gian tính toán của TTSS sử dụng n
BXL là O(n)
316
3. Thuật toán sắp xếp QuickSort
a. Bài toán: Giả sử cần sắp xếp một dãy con kể từ vị trí start
đến end trong danh sách list[ ] với pilot là vị trí của phần tử 
trong danh sách được chọn làm hoa tiêu.
b. Ý tƣởng thuật toán
• Chia dãy sắp xếp thành 2 danh sách con sao cho danh sách 
1 gồm các phần tử nhỏ hơn các phần tử của danh sách 2
• Chọn một phần tử hoa tiêu (pivot) để thực hiện việc phân chia
• Lặp lại việc phân chia trên cho từng danh sách đến khi nào 
những danh sách cuối cùng chỉ có 1 phần tử 
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
317
c. Thuật toán QuickSort tuần tự đƣợc viết đệ qui 
QuickSort(list, start, end){
if (start < end){
Partition (list, start, end, pilot);
QuickSort (list, start, pilot);
QuickSort (list, pilot+1, end);
}
} 
Trong đó, Partition() là hàm chuyển tất cả các phần tử nhỏ 
hơn hoặc bằng phần tử pilot về trước phần tử pilot, những 
phần tử lớn hơn sẽ được đặt sau pilot. Thực hiện phân tách 
xong thì pilot là vị trí của phần tử hoa tiêu ở danh sách mới
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
318
d. Ví dụ 
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
63158724
4123 6875
312 4 5 687
21 3 76 8
Danh sách cần sắp xếp
pilot
Thuật toán QuickSort tuần tự có ĐPT O(nlogn)
Reference: Parallel Programming by Barry Wilkinson
7/17/2010
54
319
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
e. Song song hóa QuickSort
Phát biểu lại QuickSort
• Chọn phần tử pilot để chia dãy thành hai phần: bên trái là
những phần tử nhỏ hơn hoặc bằng pilot và bên phải là
những phần tử lớn hơn pilot .
• Phần tử pilot được chèn vào giữa hai dãy con được tách và
nó là vị trí đã được sắp xếp sau khi thực hiện bước 1.
• Bước 1 lặp lại một cách đệ qui cho đến khi các dãy con chỉ
còn lại một phần tử.
320
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
Song song hóa QuickSort
Ý tƣởng: bắt đầu thực hiện ở một BXL và chuyển các lời gọi
đệ quy cho các BXL khác.
• Tạo ra tập các tiến trình và đặt dãy cần sắp xếp vào stack.
• Tiến trình đầu tiên (tiến trình chủ) thực hiện tách dãy cho
trước thành hai dãy con và đặt vào stack.
• Những tiến trình khác (tiến trình tớ) xử lý những dãy con đã
được tách ra và thực hiện những công việc tương tự như
thuật toán đã nêu.
321
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
P4
P0
P0 P4
P0 P2 P4 P6
P0 P1 P6
63158724
4723 6875
312 4 5 687
21 3 76 8
Danh sách sắp xếp Phân công việc cho các BXL
322
5.6 CÁC THUẬT TOÁN SẮP XẾP SONG SONG 
f. Đánh giá thuật toán QuickSort song song
• Giả thiết rằng pilot được chọn một cách lý tưởng để mỗi lần
đều tách thành hai phần có kích cỡ bằng nhau.
1. Thời gian tính toán.
• Đầu tiên một bộ xử lý phải thao tác với n số. Sau đó hai
bộ xử lý thao tác trên n/2 số, rồi bốn bộ xử lý thao tác
trên n/4 số, v.v.
• Thời gian để thực hiện thuật toán sẽ là:
tcomp = n + n/2 + n/4 + …  2n
2. Thời gian truyền thông.
• Sự trao đổi dữ liệu giữa các bộ xử lý chỉ xảy ra khi thực
hiện ghép kết hợp giống như MergeSort.
• tcomm = 2(tstartup + (n/2)tdata + tstartup + (n/4)tdata + tstartup +
(n/8)tdata …)
= 2(log p)tstartup + 2ntdata
323
5.7 CÁC THUẬT TOÁN SONG SONG THÔNG DỤNG
1. Nhân ma trận
• Mô hình lưới 2 chiều
• Mô hình mảng tâm thu
2. Giải hệ phương trình tuyến tính
3. Tính biểu đồ của ảnh
4. Tô màu đồ thị
5. Thuật toán Kruskal tìm cây khung cực tiểu
6. Thuật toán tính tổng tiền tố
7. Phương trình nhiệt một chiều
Bài tập (tham khảo tài liệu)