ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN

Ngô Thị Minh Nguyệt

MỘT SỐ PHƢƠNG PHÁP THIẾT KẾ THUẬT TOÁN CƠ
BẢN TRONG TÍNH TOÁN SONG SONG VÀ ỨNG DỤNG
Chuyên ngành: Bảo đảm toán học cho máy tính và hệ thống tính toán
Mã số: 62 46 01 10

LUẬN VĂN THẠC SĨ KHOA HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

PGS.TS. NGUYỄN HỮU ĐIỂN

Hà Nội - Năm 2014


MỤC LỤC
Trang
Trang phụ bìa ................................................................................................................
Mục lục ..........................................................................................................................
Danh mục các ký hiệu ...................................................................................................
Danh mục các bảng .......................................................................................................
Danh mục các hình vẽ ...................................................................................................
Danh mục các thuật toán ...............................................................................................

MỞ ĐẦU ........................................................................................................... 3
Chƣơng 1 – TÍNH TOÁN SONG SONG ....................................................... 5
1.1.

Định nghĩa thuật toán song song ............................................. 13

1.3.2.

Các nguyên lý thiết kế thuật toán song song .......................... 14

1.3.3.

Các cách tiếp cận trong thiết kế thuật toán song song ............ 15

1.3.4.

Phân tích và đánh giá thuật toán song song. ........................... 15

Mô hình lập trình truyền thông điệp – MPI song song ....................... 19
1.4.1.

Giới thiệu mô hình truyền thông điệp ..................................... 19

1.4.2.

Lập trình truyền thông điệp - MPI .......................................... 20

1


1.4.3.

Cấu trúc chương trình MPI ..................................................... 23



Môi trường chạy .................................................................................. 44

3.3.

Kết quả chạy thực nghiệm................................................................... 45

KẾT LUẬN ..................................................................................................... 52
TÀI LIỆU THAM KHẢO ............................................................................. 53
PHỤ LỤC ............................................................ Error! Bookmark not defined.

2


MỞ ĐẦU
Nhân loại ngày nay đang chứng kiến sự phát triển mạnh mẽ của ngành Công
nghệ thông tin, một trong những ngành mũi nhọn của nhiều quốc gia trên thế giới.
Sự phát triển vượt bậc của nó là kết quả tất yếu của sự phát triển các thiết bị phần
cứng cũng như phần mềm tiện ích. Từ những máy tính đơn giản, tốc độ xử lý chậm,
và chỉ được sử dụng trong một số lĩnh vực kỹ thuật nhất định, thì ngày nay chúng đã
có khả năng tính toán và tốc độ xử lý vượt trội trở thành một công cụ không thể
thiếu trong mọi lĩnh vực của đời sống.
Những máy tính ra đời đầu tiên, do hạn chế về tốc độ xử lý và cơ chế vào ra dữ
liệu nên việc lập trình rất khó khăn. Điều này làm cho máy tính không có khả năng
sử dụng dễ dàng và phổ cập, nó chỉ được ứng dụng trong một số lĩnh vực khoa học
đặc biệt.
Ngày nay, cùng với sự phát triển mạnh mẽ của thiết bị lưu trữ, bộ nhớ, tốc độ
xử lý và các thiết bị ngoại vi,… máy tính đã trở nên thân thiện hơn với người sử
dụng, cũng như tốc độ tính toán nhanh hơn rất nhiều. Nhờ đó mà rất nhiều bài toán
lớn đã có khả năng thực thi và nhiều ứng dụng được đưa ra.

dài nhất trong tính toán song song; Chƣơng 3 trình bày một số kết quả thực nghiệm
trên dữ liệu cho chương trình song song tìm dãy con chung dài nhât. Với thời gian
tiếp cận vấn đề và lượng thông tin còn hạn chế, luận văn còn nhiều thiếu sót. Tôi rất
mong nhận được sự góp ý của các thầy, các cô và các anh/chị để có thể tiếp tục phát
triển đề tài đã nghiên cứu và đạt được kết quả.

4


Chƣơng 1 – TÍNH TOÁN SONG SONG
1.1.

Tổng quan về xử lý 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 (Hình 1.10), với một đơn vị xử lý được nối với một vùng
lưu trữ làm bộ nhớ và tại một thời điểm chỉ có một lệnh được thực thi. [14]
Bộ nhớ

Câu lệnh

Ghi dữ liệu

Đọc dữ liệu

Bộ xử lý

Hình 1.1. Mô tả kiến trúc Von Neumann

Với những bài toán yêu cầu về khả năng tính toán và lưu trữ lớn thì mô hình

giải thuật và ngôn ngữ lập trình, …
Độ phức tạp
Độ phức tạp của tính toán song song không chỉ phụ thuộc vào kích cỡ của dữ
liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số lượng các bộ
xử lý được phép sử dụng trong hệ thống.
Cài đặt giải thuật song song
Để cài đặt các giải thuật song song trên các máy tính song song, phải sử dụng
những ngôn ngữ lập trình song song như: OpenMP với C/C++, MPI với C/C++,
v.v..
1.1.2. Phân loại các kiến trúc của máy tinh song song
1.1.2.1.

Phân loại theo kiến trúc máy tính của Flynn.

Một trong những phân loại hay được nhắc tới là của Flynn – 1966 [6]. Michael
Flynn phân các kiến trúc máy tính thành bốn loại dựa vào sự phân phối luông dữ
liệu (data stream ) và phân phối các luồng lệnh (instruction stream) trên mỗi bộ
xử lý.


Mô hình SISD (đơn luồng lệnh, đơn luồng dữ liệu)

6


Đây chính là kiến trúc tuần tự Von Neuman , máy tính SISD chỉ có một CPU,
các dòng lệnh được thực hiện một cách tuần tự. Hệ thống SISD (hình 1.2: trong đó
tại mỗi thời điểm chỉ thực hiện một lệnh trên một mục dữ liệu)

Hình 1.2: Mô hình máy SISD

Máy tính loại MIMD còn gọi là đa bộ xử lý, trong đó mỗi bộ xử lý có thể thực

hiện những luồng lệnh khác nhau trên các luồng dữ liệu riêng.
Hầu hết các hệ thống MIMD đều có bộ nhớ riêng và cũng có thể truy cập vào
được bộ nhớ chung khi cần, do vậy giảm thiểu được sự trao đổi giữa các bộ xử lý
trong hệ thống.

Hình 1.4: Mô hình máy MIMD

Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình hỗ trợ xử lý song song
cao nhất, bởi chúng có thể thực thi các lệnh khác nhau trên nhiều dòng dữ liệu khác
nhau tại một thời điểm.
Theo Flynn: có hai họ kiến trúc quan trọng cho các máy tính song song: SIMD
và MIMD. Những kiến trúc khác có thể xếp theo hai mẫu đó. Mục tiêu của xử lý
song song là khai thác đến mức tối đa các khả năng sử dụng của các thiết bị phần
cứng nhằm giải quyết nhanh những bài toán đặt ra trong thực tế.
1.1.2.2.


Phân loại theo mô hình bộ nhớ

Mô hình bộ nhớ chia sẻ

8


Đặc điểm của máy tính song song loại này là các nút tính toán đều có thể truy
nhập vào bộ nhớ dùng chung như là bộ nhó toàn cục. Nhiều bộ xử lý hoạt động độc
lập nhưng cùng sử dụng chung một bộ nhớ, mỗi sự thay đổi nội dung các ngăn nhớ
đều được các bộ xử lý biết.


giữa kiến trúc chia sẻ bộ nhớ chung và bộ nhớ phân tán. Sự kết hợp đó tạo nên một
máy tính với tên gọi máy tính có bộ nhớ lai
1.1.3. Song song hóa máy tính tuần tự
Trong kiến trúc tuần tự có thể tận dụng tốc độ cực nhanh của bộ xử lý để thực
hiện xử lý song song theo nguyên lý chia sẻ thời gian và chia sẻ tài nguyên.
Các thanh ghi được sử dụng trực tiếp cho ALU. Bộ nhớ cache được xem như
vùng đệm giữa bộ xử lý chính. Sự song song hóa trong sự trao đổi dữ liệu theo cấu
trúc phân cấp là cách khai thác chung để cải tiến hiệu quả xử lý của hệ hống. Các hệ
điều hành của máy tính đơn bộ xử lý cho phép thực hiện song song dựa vào cách
tiếp cận phần mềm.
Trong cùng một khoảng thời gian, có nhiều tiến trình cùng truy cập vào dữ iệu
từ những thiết bị vào/ra chung. Phần lớn các chương trình đều có hai phần: phần
vào/ra và các thành phần tính toán trong quá trình xử lý. Các hệ điều hành đa
chương trình luân phiên thực hiện các chương trình khác nhau.
Để thực hiện việc này hệ điều hành sử dụng Bộ lập lịch chia sẻ thời gian làm
nhiệm vụ phân chia CPU cho mỗi tiến trình một khoảng thời gian cố định theo
phương pháp quay vòng tròn. Bằng cách đó, tất cả các tiến trình đều được sẵn sàng
để thực hiện trên cơ sở được phép sử dụng CPU và những tài nguyên khác của hệ
thống.
Do vậy, về nguyên tắc việc phát triển những chương trình song song trên máy
đơn bộ xử lý thực hiện được nếu có hệ điều hành cho phép nhiều tiến trình thực
hiện, nghĩa là có thể xem hệ thống như là đa bộ xử lý.

10


1.2.

Các mô hình lập trình song song

11


với việc kết nối này thì chương trình phải được xây dựng một cách đồng bộ để tránh
cùng một lúc có nhiều luồng cùng cập nhập một vị trí trong bộ nhớ toàn cục .

Hình 1.7: Mô tả chương trình trong tệp a.out, chương trình khởi động chạy
như một tiến trình đơn, sau đó các tiến trình được khởi tạo để chạy đồng thời, các
tiến trình có thể sử dụng tài nguyên của a.out và có thể kết thúc riêng rẽ.
1.2.3. Mô hình truyền thông điệp
Trong mô hình truyền thông điệp chương trình song song được chia thành các
tác nhiệm. Một tập các tác nhiệm sử dụng bộ nhớ cục bộ riêng của chúng trong quá
trình tính toán. Nhiều tác nhiệm có thể nằm trên cùng một máy cũng như nằm trên
nhiều máy.

Hình 1.8: Mô hình truyền thông điệp

Các tác nhiệm vụ trao đổi dữ liệu thông qua truyền thông bằng cách gửi và
nhận các thông điệp.
Có nhiều thư viện truyền thông điệp, nhưng chúng khác nhau đáng kể, gây
khó khăn cho các nhà lập trình trong việc phát triển các ứng dụng di động. MPI
Forum được lập ra với mục đích thiết lập một chuẩn cho việc triển khai mô hình
truyền thông điệp. Hiện nay, MPI là chuẩn cho mô hình truyền thông điệp.

12


1.2.4. Mô hình phân hoạch dữ liệu
Mô hình lập trình song song dữ liệu giúp lập trình các chương trình song song
được thực hiện trên một tập dữ liệu lớn. Tập dữ liệu ở đây thường được xắp xếp


-

Chỉ ra cách truy cập và chia sẻ dữ liệu.

-

Phân các tác vụ cho các tiến trình (bộ xử lý)

-

Các tiến trình được đồng bộ ra sao.

Khi thiết kế một thuật toán song song có thể sử dụng năm nguyên lí chính
trong thiết kế thuật toán song song:
+ Nguyên lý lập lịch: Mục đích là giảm tối thiểu các bộ xử lý dùng trong thuật
toán sao cho thời gian tính toán là không tăng.
+ Nguyên lý hình ống: Nguyên lý này được áp dụng khi bài toán xuất hiện
dãy các thao tác {T1, T2, . . ., Tn}, trong đó Ti+1 thực hiện sau khi Ti kết thúc.
+ Nguyên lý chia để trị: Chia bài toán thành những phần nhỏ hơn tương đối
độc lập với nhau và giải quyết chúng một cách song song.
+ Nguyên lý đồ thị phụ thuộc dữ liệu: Phân tích mối quan hệ dữ liệu trong tính
toán để xây dựng đồ thị phụ thuộc dữ liệu và dựa vào nó để xây dựng thuật toán
song song.
+ Nguyên lý điều kiện tương tranh: Nếu hai tiến trình cùng muốn truy cập vào
cùng một mục dữ liệu chia sẻ thì chúng phải tương tranh với nhau.
Ngoài những nguyên lý nêu trên, khi thiết kế thuật toán song song ta còn phải
chú ý đến kiến trúc của hệ thống tính toán. Khi chuyển một thuật toán tuần tự sang
thuật toán song song hoặc chuyển một thuật toán song song thích hợp với kiến trúc
đang có. Cần xác định được kiến trúc tính toán nào sẽ phù hợp với bài toán và

Thiết kế thuật toán song song hiệu quả bao gồm việc lựa chọn cấu trúc dữ liệu
phù hợp, phân bố bộ xử lý và cuối cùng là thực hiện thuật toán. Ba đại lượng này
tác động lẫn nhau như một tổ chức tính toán.
Đánh giá thuật toán song song
Độ phức tạp tính toán của thuật toán song song không chỉ phụ thuộc vào kích
cỡ của dữ liệu đầu vào mà còn phụ thuộc vào kiến trúc máy tính song song và số
lượng các bộ xử lý được phép sử dụng trong hệ thống. Độ phức tạp thời gian là
thước đo quan trọng nhất đánh giá mức độ hiệu quả của thuật toán song song.
Chúng ta giả thiết rằng mô hình tính toán có p bộ xử lý. Nghĩa là mức độ song song
là có giới hạn. Ngược lại, mức độ song song không bị giới hạn khi số các bộ xử lý
là không bị chặn. Độ phức tạp thời gian của thuật toán song song sử dụng p bộ xử
lý để giải một bài toán có kích cỡ n là hàm f n, p  xác định thời gian cực đại trôi

15


qua giữa thời điểm bắt đầu thực hiện thuật toán bởi một bộ xử lý và thời điểm kết
thúc của các bộ xử lý đối với bộ dữ liệu vào bất kỳ. Có hai loại thao tác khác nhau
trong các thuật toán song song:
1. Các phép toán cơ sở như +, -, *, /, AND, OR, v.v…
2. Các phép toán truyền dữ liệu trên các kênh truyền.
Độ phức tạp thời gian của thuật toán song song được xác định bởi số các phép
toán cơ sở và số các bước truyền tải dữ liệu giữa các bộ xử lý với nhau. Từ đó suy
ra, độ phức tạp thời gian của thuật toán song song không chỉ phụ thuộc vào mô hình
tính toán mà còn phụ thuộc vào số bộ xử lý được sử dụng.
Nói chung, chương trình tính toán song song thường bắt đầu bằng việc nhập
dữ liệu vào bộ nhớ và kích hoạt một phần tử xử lý. Mỗi bước tính toán, phần tử xử
lý này có thể đọc một số dữ liệu từ bộ nhớ, thực hiện một số phép toán cơ sở và ghi
kết quả vào bộ nhớ riêng hoặc bộ nhớ chung. Đồng thời mỗi bước tính toán, một
phần tử xử lý có thể kích hoạt một hay một số phần tử xử lý khác. Thực tế thì các


(1.2)

Trong đó, t startup 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ố.
t data là thời gian cần thiết để chuyển một mục dữ liệu (data word) từ nơi gửi tới

nơi nhận, được giả thiết là hằng số và n là số từ dữ liệu được trao đổi trong hệ
thống.
Chi phí cho một thuật toán song song được xác định bằng tích của thời gian
tính toán song song và số bộ xử lý được sử dụng. Chi phí này phản ánh tổng số thời
gian mà một bộ xử lý dùng để giải quyết bài toán.
Một thuật toán song song sử dụng p bộ vi xử lý để giải quyết bài toán đặt ra
trong OT  đơn vị thời gian, sử dụng p bộ xử lý trong t p đơn vị thời gian, khi đó
chi phí cho thuật toán song song C p :

Cp  p  t p .

(1.3)

Hệ số tăng tốc cũng là yếu tố đáng chú ý khi đánh giá thuật toán song song
được song song hóa từ một thuật toán tuần tự.
Hệ số tăng tốc là tỉ lệ giữa thời gian thực hiện của thuật toán tuần tự ts và thời
gian thực hiện của thuật toán song song t p với p bộ xử lý
Sp 

ts
tp



Ta dễ dàng thấy được,
nên S p 

1
.
1 P

1
P
(1  P) 
N

là hàm tăng theo N và lim
N 

1
(1  P) 

Ta có biểu đồ thể hiện luật Amdahl như hình 1.4.

Hình 1.10 Luật Amdahl

18

P
N




sử dụng trong các cụm máy tính và siêu máy tính và là một trong các mô hình cổ
nhất được sử dụng rộng rãi nhất trong các mô hình dùng cho lập trình trên các máy
tính song song bởi vì nó yêu cầu tối thiểu về phần cứng.
Có hai tính chất quan trọng tạo nên bản chất của mô hình truyền thông điệp:
thứ nhất là nó giả sử không gian địa chỉ được phân chia và thứ hai là nó chỉ hỗ trợ
song song hóa tường minh.

Hình 1.11: Sự trao đổi thông điệp giữa hai tiến trình

19


1.4.2. Lập trình truyền thông điệp - MPI
Giới thiệu về MPI
MPI là giao thức độc lập ngôn ngữ sử dụng cho các máy tính song song. MPI
là một giao diện lập trình ứng dụng truyền thông điệp với mục đích là đem lại hiệu
năng cao, khả năng mở rộng và linh hoạt.
MPI là một thư viện chương trình mà có thể được gọi trực tiếp từ chương trình
Fortran, C/C++ và bất cứ ngôn ngữ nào khác tương thích với thư viện hàm (như C#,
Java và Python). Lợi ích của việc sử dụng MPI là tính khả chuyển (vì MPI được cài
đặt cho hầu hết các kiến trúc bộ nhớ phân tán) và tốc độ (vì mỗi cài được được tối
ưu hoá về nguyên lý cho phần cứng mà nó thực thi trên đó).
MPI sử dụng đặc tả độc lập ngôn ngữ (LIS) cho các lời gọi hàm. Hiện nay, các
chuẩn MPI có hai phiên bản phổ biến là 1.2 (gọi tắt là MPI-1) chủ yếu là truyền
thông điệp và có môi trường hoạt động tĩnh, và phiên bản MPI-2.1 (gọi tắt là MPI2) bao gồm nhiều đặc điểm mới như vào/ra song song, quản lý tiến trình động và
truy cập bộ nhớ từ xa. MPI-2 gần như bao hàm toàn bộ MPI-1, mặc dù có một số
hàm đã bị loại bỏ. Vì thế, các chương trình viết theo MPI-1.2 vẫn có thể tương thích
với chuẩn MPI-2.
Chức năng của MPI
Chức năng của thư viện MPI bao gồm (nhưng không hạn chế) các hoạt động

xuyên gửi dữ liệu cho tiến trình kia mỗi khi có một tác vụ hoàn thành.
MPI-1 đặc tả cơ chế truyền thông điểm-điểm không khoá và có khoá.
Cơ sở cộng tác tập thể: Chức năng hoạt động tập thể trong MPI liên quan
đến truyền thông giữa mọi tiến trình trong nhóm. Một hàm, hay gặp, dạng này là
MPI_Bcast. Hàm này lấy dữ liệu từ một nút đặc biệt nào đó và gửi thông điệp tới
mọi tiến trình trong nhóm. Một hàm khác đó là MPI_Reduce, hàm này dùng để lấy
dữ liệu từ mọi tiến trình khác trong nhóm. Các loại hàm này thường hữu ích khi bắt
đầu hoặc kết thúc quá trình tính toán phân tán lớn. Còn có một số hàm phức tạp hơn
như MPI_Alltoall, hàm này tái sắp xếp n phần dữ liệu từ mỗi tiến trình để nút thứ
n lấy dữ liệu phần tử thứ n từ mỗi nút.

Các loại dữ liệu: Nhiều hàm MPI cần chúng ta đặc tả loại dữ liệu được gửi
giữa các bộ xử lý. Điều này xuất phát từ việc các tham số của hàm MPI đều là các
biến, không phải là loại được định nghĩa trước. Nếu loại dữ liệu là chuẩn như int,

21


char, double.., thì ta có thể sử dụng các loại dữ liệu định nghĩa của MPI như
MPI_INT, MPI_CHAR, MPI_DOUBLE… Giả sử ta có một mảng các số nguyên, và
mọi bộ xử lý muốn gửi các mảng dữ liệu đó tới nút gốc, thì có thể gọi hàm
MPI_Gather. Ví dụ:
int array[100];
int root, total_p, *receive_array;
MPI_Comm_size(comm, &total_p);
receive_array=(int *) malloc(total_p*100*sizeof(int));
MPI_Gather(array, 100, MPI_INT, receive_array, 100, MPI_INT, root, comm);

Truyền thông một phía (MPI-2): MPI-2 xác định ba thao tác truyền thông
một phía, bao gồm Put, Get, và Accumulate, dùng để ghi, đọc đối với bộ nhớ từ xa,

gồm tập tin .h như mpi.h mpio.h và các tập tin khác. Thông thường người lập trình
chỉ cần dùng thư viện mpi.h là đủ.
Môi trường MPI: Tất cả các kiểu dữ liệu, các thủ tục, các giá trị defined nếu
muốn dùng nó, sau khi gọi các tập tin thư viện liên kết thì phải khởi tạo môi trường
sử dụng thì mới có thể dùng được các chức năng mà MPI cung cấp. Các thủ tục,
hàm MPI: sử dụng giống như các hàm trong C và cả các ngôn ngữ khác như Fortran

Các tập tin thư viện

Khởi tạo môi trường MPI

Thực hiện các thủ tục hàm của MPI

Thoát khỏi môi trường MPI
Hình 1.12: Cấu trúc chương trình MPI

23


Chƣơng 2 – SONG SONG HÓA THUẬT TOÁN TÌM XÂU
CON CHUNG DÀI NHẤT
2.1.

Đặt vấn đề
Tin sinh học (bioinformatics) là một lĩnh vực khoa học sử dụng các công nghệ

của ngành toán học ứng dụng, tin học, thống kê, khoa học máy tính và toán sinh học
(biomathematics) để nghiên cứu thông tin về cuộc sống từ góc độ sinh học. Các ứng
dụng của tin sinh học tập trung vào nghiên cứu ở cấp độ phân tử để hiểu sâu sắc về
cấu trúc cơ bản và các quá trình ở cấp độ tế bào và phân bào. Những lĩnh vực