Nội dung:
Tìm hiểu tính toán song song hóa thuật toán và
ứng dụng song song bài toán sắp xếp theo giỏ
(bucket sort)

MỤC LỤC
TÀI LIỆU THAM KHẢO 15
2
Phần I: MỞ ĐẦU
Bốn thập kỷ qua chứng kiến sự phát triển bùng nổ về sức mạnh máy tính,
tạo tiền đề cho những bước tiến chưa từng thấy về phát minh, năng suất lao động
và phúc lợi cho con người. Nhưng quá trình đó giờ đây đứng trước một trở ngại
mà ít ai nghĩ đến: sự kết thúc của quá trình mở rộng sức mạnh điện toán. Ngành
tin học đã đạt đến giới hạn của những gì từng khả thi với một hay hai vi xử lý
trung tâm hoạt động theo chuỗi truyền thống (serial processing). Ngành nào vẫn
dựa vào mô hình đó để tiếp tục phát triển năng suất, tăng trưởng kinh tế và phát
triển xã hội thì cần phải bắt đầu một bước nhảy mới vào điện toán xử lý song
song (parallel processing).
Ngày nay, với các bài toán yêu cầu xử lý trên một số lượng dữ liệu lớn và
phức tạp như sự mô phỏng những hệ thống phức tạp và "những vấn đề thách
thức lớn" như: dự báo thời tiết và khí hậu, những phản ứng hoá học và hạt nhân,
hệ gen sinh học, đặt ra một nhu cầu lớn về tốc độ tính toán. Những bài toán
này thường yêu cầu một lượng lớn các phép tính lặp lại trên một khối lượng lớn
dữ liệu để đưa ra một kết quả đúng đắn, và các phép tính này cần hoàn thành
trong khoảng thời gian hợp lý. Ví dụ như bài toán dự bào thời tiết không thể xử
lý bằng các máy tính thông thường vì thời gian xử lý là khoảng 10 năm, điều
này hoàn toàn không phù hợp.
Đề giải quyết được các bài toán trên ta cần phải tăng tốc độ tính toán. Mặc

x 1mile x 1mile.
- Ước tính khoảng 5x10^8 khối (cells).
- Trên mỗi khối cần thực hiện ~ 200 phép toán -> cần thực hiện ~ 10^11
phép toán.
- Nếu cần dự báo cho 1 tuần, chu kỳ 1 phút -> cần thực hiện 10^4 lần, mỗi
lần 10^11phép toán.
- Siêu máy tính có thể thực hiện: 10^9 phép toán trên 1 giây -> cần 10^6
giây ~ 10 ngày để thực hiện.
Ví dụ 3: Mô phỏng tương tác của các protein với phân tử nước (Levin 1990):
- Thực hiện trên máy Cray X/MP (~800 triệu phép toán / 1 giây): để mô
phỏng 10^-12 giây phản ứng protein cần 1 giờ thực hiện.
- Nếu mô phỏng một phản ứng thực sự trên cùng máy Cray X/MP cần
31,688 năm.
TÓM LẠI:
Yêu cầu về thực nghiệm nghiên cứu, mô phỏng -> giải quyết những bài
toán có khối lượng tính toán lớn trong một khoảng thời gian chấp nhận được.
Phương hướng giải quyết vấn đề:
- Thực hiện trên các siêu máy tính mạnh.
- Thực hiện phân chia công việc thực hiện song song trên hệ thống các máy tính
Tính khả dụng của tính toán song song
SIÊU MÁY TÍNH: Khả năng tính toán phụ thuộc nhiều vào tốc độ xử lý
của CPU -> phụ thuộc vào cấu trúc và số lượng transistors chứa trong CPU –>
Có những giới hạn nhất định về kích thước, nhiệt độ -> không thể tăng số
transistors lên mãi được
THỰC HIỆN SONG SONG:
Nguyên tắc: thực hiện phân chia công việc chính thành các công việc con, có thể
thực hiện song song với nhau.
Xây dựng hệ thống song song từ nhiều bộ xử lý riêng biệt. Thực hiện các công
việc song song trên các bộ xử lý đó.
Vấn đề:

gian.
Thực hiện được với số lượng phép toán lớn hơn -> giải quyết được bài
toán lớn.
Hỗ trợ giải quyết nhiều công việc đồng thời.
2. Các ứng dụng trong hệ thống máy tính
Khi các hệ thống máy tính trở nên rộng khắp và sự tính toán trải rộng trên
toàn mạng, thì các vấn đề xử lý song song cũng được ứng dụng nhiều hơn. trong
việc bảo mật máy tính, việc phát hiện xâm phạm là một thử thách đáng kể.
Trong trường hợp phát hiệ xâm phạm mạng, dữ liệu được thu thập từ các trang
phân tán và phải được phân tích một cách nhanh chóng. Việc không thể thu thập
được dữ liệu này tại vị trí trung tâm để phân tích đòi hỏi các thuật giải song song
và phân tán. Trong lĩnh vực mật mã, ứng dụng đặc biệt nhất của tính toán song
song trên Internet tập trung vào việc phân tích các số nguyên cực lớn.
Các hệ thống nhúng tăng dựa trên các thuật toán điều khiển phân tán để
hoàn thành một số tác vụ. Một ô tô hiện đại gồm mười bộ xử lý liên lạc với nhau
5
để thực hiện các tác hợp trong việc tối ưu hoá quá trình tiến hành và sự thực
hiện. Trong các hệ thống này, các thuật toán phân tán và song song truyền thống
để lựa chọn vật dẫn đầu và tập độc lập lớn nhất, vv thường được sử dụng.
3. Các loại máy tính song song
3.1. Phân loại theo Flynn
Dù là máy tính tuần tự hay song song đều phải thực hiện bằng cách thực
thi các chỉ lệnh trên dữ liệu
Dựa vào số lượng dòng lệnh và số lượng dòng dữ liệu thực thi cùng tại
một thời điểm mà Micheal Flynn đã phân các máy tính thành 4 loại:
- Máy tính SISD: Đơn dòng lệnh-đơn dòng dữ liệu
- Máy tính MISD: Đa dòng lệnh – đơn dòng dữ liệu
- Máy tính SIMD: Đơn dòng lệnh – đa dòng dữ liệu
- Máy tính MIMD: Đa dòng lệnh – đa dòng dữ liệu
3.2. Kiến trúc bộ nhớ của máy tính song song

vùng nhớ đó cho tới khi việc cập nhật đó kết thúc.
6
4.3. Lập trình chia sẻ bộ nhớ dựa vào luồng
Các luồng của một tiến trình có thể chia sẻ với nhau về không gian địa chỉ
chương trình, các đoạn dữ liệu và môi trường xử lý, đồng thời cũng có những
vùng dữ liệu riêng để thao tác.
Công việc của một luồng có thể được miêu tả như là một chương trình
con của một chương trình chính. Một luồng bất kì có thể thực thi một chương
trình con bất kì cùng lúc với các luồng khác.
Các thể hiện của luồng có nhiều hệ điều hành hỗ trợ đa luồng như: SUN
Solaris, Windows NT v.v những nỗ lực tiểu chuẩn hoá không giống nhau đã
đưa tới hai thể hiện rất khác nhau của luồng đó là: POSIX Threads và OpenMP.
4.4. Mô hình truyền thông điệp
Giống như mô hình chia sẻ bộ nhớ, các đơn vị xử lý song song trong mô
hình truyền thông điệp là các tiến trình. Trong mô hình truyền thông điệp.
Các tiến trình có thể thực hiện trên những bộ xử lý khác nhau và không
được truy cập vào không gian bộ nhớ chia sẻ.
Việc truyền thông giữa các tiến trình thông qua việc gửi và nhận thông
điệp.
Việc đồng bộ hoá các tiến trình của một chương trình song song được
thực hiện theo cơ chế truyền thông điệp. Khi một tiến trình muốn gửi một thông
điệp thì nó phải chờ cho đến khi tiến trình nhận sẵn sàng nhận thông điệp đó và
ngược lại, cũng tương tự.
5. Thuật toán song song
5.1. Nguyên lý thiết kế thuật toán song song
Phát triển thuật toán là một phần cơ bản của việc giải quyết bài toán sử
dụng máy tính. Một thuật toán tuần tự về bản chất là một cách làm hay một số
tuần tự các bước để giải quyết bài toán đưa ra bằng một máy tính tuần tự. Một
các tương tự, một thuật toán song song là một cách làm chỉ cho chúng ta làm thế
nào để giải quyết bài toán đưa ra bằng các máy tính song song.

- Nhóm gom các tác vụ (agglomeration)
- Gán vào hệ thống (mapping)
II. Lập trình song song với MPI
Lập trình song song cũng giống như lập trình tuần tự, có nhiều ngôn ngữ
và công cụ lập trình song song khác nhau. Lập trình theo mô hình truyền thông
điệp trong hệ thống máy tính thực hiện theo 3 cách:
- Sử dụng ngôn ngữ lập trình song song đặc biệt, ví dụ Occam được thiết
kế sử dụng với các Transputer (Inmos 1986).
- Sử dụng ngôn ngữ lập trình bậc cao (tuần tự) truyền thông được mở rộng
bằng cách bổ sung thêm các từ khoá và mở rộng một cú phát để xử lý việc trao
đổi thông điệp, gồm có CC+ (mở rộng từ C++) và Fortram M ( mở rộng từ
Rortran)
- Sủ dụng ngôn ngữ lập trình bậc cao như là ngôn ngữ C và cung cấp một
thư viện các thủ tục bên ngoài để thực hiện truyền thông điệp.
Lập trình song song với MPI là lập trình theo mô hình truyền thông điệp
trong hệ thống máy tính sử dụng cách tiếp cận thứ ba.
III. Thuật toán sắp xếp
1. Sắp xếp theo giỏ (Bucket sort)
Các thuật toán sắp xếp đã được nghiên cứu nhiều trong lập trình tuần tự.
Hầu hết các thuật toán sắp xếp tuần tự đều dựa trên cơ sở so sánh và đổi chỗ các
cặp số. Phần này chúng ta sẽ sử dụng kỹ thuật phân hoạch và chia để trị để song
soag hoá thuật toán sắp xếp theo giỏ (bucket sort).
Thuật toán bucket sort không dựa trên cơ sở so sánh và đổi chỗ, thuật toán
là một phép phân hoạch một cách tự nhiên. Thuật toán bụcket sort chỉ có hiểu
quả khi các số ban đầu có phân bổ đều trên một khoảng cho trước, giả sử từ o
đến a - 1. Khoảng cho trước sẽ được chia thành m khoảng nhỏ, 0 tới a/m-1, a/m
tới 2a/m-1, , và mỗi giỏ được gán để chứa các số trong khoảng đó vậy cần có
m giỏ.
2. Thuật toán tuần tự
Đặt các số vào các khoảng phù hợp: để đặt một số vào khoảng cách thích

Hình 2: Thuật toán bucket sort song song
Phân tích: Thuật toán gồm 4 giai đoạn sau đây:
1. Phân các số vào p miền.
Giả sử cần n bước tính toán để phân n số vào p miền.
t
comp1
= n
Sau khi chia nhỏ, p phần nhỏ mỗi phần chứa n/p số được gửi tới các tiến
trình:
t
comp1
= t
srartup
+ t
data
n
2. Sắp xếp trong các giỏ nhỏ.
Chia mỗi phần của n/p số vào p giỏ nhỏ yêu cầu thời gian là
t
comp2
= n/p
3. Gửi tới các giỏ lớn
Các giỏ nhỏ được phân tán. Mỗi giỏ nhỏ có khoảng n/p
2
số (giả thiết là
phân bố đều). Mỗi tiến trình phải gửi (p-1) giỏ nhỏ tới các tiến trình khác. Cả p
tiến trình phải thực hiện phép truyền thông này, ta có:
t
comp3
= p(p - 1)(t

srartup
+ (n/p
2
)t
data
) + (n/p)log(n/p)
Công thức trên đạt được khi các số được phân bố đều. Nếu các số không
có phân bố đều thì các số trong mỗi giỏ sẽ khác nhau, điều này sẽ làm tăng tổng
thời gian tính toán. Trường hợp tồi nhất của bài toán là khi tất cả các số cùng
nằm trong một giỏ. Thuật toán bucket sort có thể được phát triển theo hướng
10
phương pháp chia để trị bằng cách chia liên tục các giỏ cho tới khi mỗi giỏ chỉ
chứa một phần tử của dãy. Phương pháp này tương tự như thuật toán quick sort
(sắp xếp nhanh), chỉ khác là trong quick sort sử dụng một phần từ để chia đôi
miền.
Phần III: MÃ NGUỒN
1. Mã code thực hiện song song thuật toán bucket sort bằng cách gán cho mỗi
tiến trình một giỏ.
#include<stdio.h>
#include<stdlib.h>
#include<mpi.h>
int sort(int ar[],int size)
{
int temp;
int i,j;
for(i=size-1; i>=1;i )
for(j=0;j<i;j++)
if(ar[j]>ar[j+1])
{
temp=ar[j];

// dien cac so ngau nhien vao mang
printf("Dien cac so ngau nhien vao mang :");
for(i=0; i<n; i++)
{
array[i] = rand() % a;
printf("a[%d] = %d ",i, array [i]);
}
printf("\n");
}
tstart = MPI_Wtime();
//gui cac thong so mang,a,n vao cac tien trinh
MPI_Bcast(&n,1,MPI_INT,0,MPI_COMM_WORLD);
MPI_Bcast(&a,1,MPI_INT,0,MPI_COMM_WORLD);
if (rank !=0)
array = (int*)malloc(sizeof(int)*n);
MPI_Bcast(array, n, MPI_INT,0,MPI_COMM_WORLD);
tend = MPI_Wtime();
printf("Thoi gian may chu Broadcast toi cac tien trinh %d : %lf \n",rank,tend-tstart);
tstart=MPI_Wtime();
slice=a/p;
start=rank*slice;
end=(rank==p-1)?a:start+slice;
// Tính toán thời gian xử lý trong các tiến trình con, trả về kết quả cho máy chủ
xử lý
count=0;
local=(int*)malloc(sizeof(int)*n);
//ghep mot cua mang thanh mot nhom
for(i=0; i<n; i++)
if(array[i]<end&&array[i]>=start)
local[count++]=array[i];

}
2. Kết quả thu được
Chương trình sử dụng sắp xếp nổi bọt xử lỹ chuỗi nhập thành chuỗi có giá
trị tăng dần.
Mãy chủ gửi một số đoạn dãy cho các tiến trình con.
Tiến trình con xử lý rồi gửi lại kết quả cho máy chủ.
Máy chủ tập hợp các tiến trình, tổng hợp kết quả.
Hàm sort nhằm sắp xếp dãy theo thứ tự tăng dần
3. Hình ảnh chương trình nhóm 7 chạy trên máy chủ guest@bkluster
Với số phần tử của mảng là 7 với 5 tiến trình được thực thi
Với số phần tử của mảng là 8 với 5 tiến trình được thực thi
13
14
TÀI LIỆU THAM KHẢO
Tài liệu
[1] Nguyễn Văn Ba, Phát triển hệ thống hướng đối tượng với UML và C++,
Nhà xuất bản ĐH Quốc gia Hà nội, 2007.
[2] Slide bài giảng của TS. Nguyễn Hữu Đức
Trang Web
[1] MPI Tutorial

[2] Open Source High Performance Computing
/>[3] LAM/MPI Parallel Computing
/>[4] Sàng Eratosthenes
/>15