ĐẠ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
LUẬN VĂN THẠC SĨ KHOA HỌC
Hà Nội- Năm 2014

ĐẠI HỌC QUỐC GIA HÀ NỘI

thầy giáo, PGS. TS. Nguyễn Hữu Điển. Thầy đã tận tình hướng dẫn, định hướng
cho tôi trong phương pháp nghiên cứu khoa học cũng như hỗ trợ tôi trong việc tìm
tài liệu.
Để có được những kết quả trong luận văn này, tôi xin gửi lời cảm ơn sâu sắc
đến thầy giáo, PGS. TS. Nguyễn Hữu Điển, Trung Tâm Tính Toán Hiệu Năng Cao
trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội.
Tôi cũng xin gửi lời cảm ơn đến các thầy cô của tôi về sự dạy dỗ ân cần trong
thời gian tôi học cao học tại trường Đại học KHTN - ĐHQGHN. Tôi xin cảm ơn
các thầy cô, các anh chị của Trung Tâm Tính Toán Hiệu Năng Cao đã tạo điều kiện
và giúp đỡ tôi rất nhiều trong việc hoàn thành luận văn.
Cuối cùng tôi xin cảm ơn gia đình, người thân và các bạn của tôi những người
đã luôn bên cạnh, động viên và khích lệ tôi để có được kết quả như ngày hôm nay.
Hà Nội, ngày 29 tháng 9 năm 2014
Người thực hiện, học viên Ngô Thị Minh Nguyệt
Lớp Cao học BĐT 2008 – 2010.

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ẽ


Thiết kế và đánh giá thuật toán song song 11

1.3.1.

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

1.3.2.

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

1.3.3.

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

1.3.4.

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

1.4.

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

1.4.1.

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

1.4.2.

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


Kết luận chương. 40

Chương 3 – KẾT QUẢ THỰC NGHIỆM 41

3.1.

Bộ dữ liệu 41

3.2.

Môi trường chạy 42

3.3.

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

KẾT LUẬN 50

TÀI LIỆU THAM KHẢO 51

BẢNG THUẬT NGỮ VIẾT TẮT
Thuật ngữ


31

Bảng 2.4. Ví dụ về việc tìm các phần tử trội độc lập trên hai vùng khác nhau.
33

Bảng 2.4. Chia ô vùng tìm kiếm và xác định các vùng tìm kiếm đồng thời. . 34

Bảng 3.1. Dữ liệu thực nghiệm thuật toán 41

Bảng 3.2. Bảng thống kê các loại amino axit [28] 42

Bảng 3.3. Số phần tử trội trung bình đối với số xâu khác nhau trên bảng chữ
cái 4 ký tự và độ dài xâu bằng 64: 43

Bảng 3.4. Số phần tử trội trung bình đối với số xâu khác nhau trên bảng chữ
cái 20 ký tự và độ dài xâu bằng 64: 44

Bảng 3.5. Thời gian chạy thuật toán với độ dài xâu là 64 trên bảng chữ cái 4
ký tự (giây) 44

Bảng 3.6. Thời gian chạy thuật toán với độ dài xâu là 64 trên bảng chữ cái 20
ký tự (giây): 45

Bảng 3.7. Thời gian chạy thuật toán với độ dài xâu là 128 trên bảng chữ cái 4
ký tự (giây): 46

Bảng 3.8. Thời gian chạy thuật toán với độ dài xâu là 128 trên bảng chữ cái
20 ký tự (giây): 46
Trang
Thuật toán 2.1. Thuật toán tuần tự tìm dãy con chung dài nhất 26

Thuật toán 2.2. Thuật toán tuần tự in ra dãy con chung dài nhất 27

Thuật toán 2.3. Thuật toán tìm phần tử trội 32

Thuật toán 2.4. Thuật toán song song tìm xâu con chung dài nhất 38

1
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.
Tuy nhiên, một thực tế là còn rất nhiều vấn đề lớn với số lượng cần tính toán

quan về xử lý song song, thuật toán song song và giới thiệu lập trình song song với
MPI , Chương 2 trình bày về phương pháp thiết kế thuật toán tìm dãy con chung
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ả. 3
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]

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
kiến trúc này còn hạn chế. Để tăng cường sức mạnh tính toán giải quyết các bài toán
lớn có độ tính toán cao, người ta đưa ra kiến trúc mới, với ý tưởng kết hợp nhiều bộ
xử lý vào trong một máy tính, hay gọi là xử lý song song hoặc kết hợp sức mạnh
tính toán của nhiều máy tính dựa trên kết nối mạng (máy tính song song).
Kể từ lúc này, để khai thác được sức mạnh tiềm tàng trong mô hình máy tính
nhiều bộ xử lý song song, cũng như trong mô hình mạng máy tính xử lý song song
thì việc xây dựng thiết kế giải thuật song song là điều quan trọng. Giải thuật song
song có thể phân rã công việc trên các phần tử xử lý khác nhau
1.1.1. Một số khái niệm về xử lý song song

đặ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ý.

5
 Mô hình SISD (
đơn luồng lệnh, đơn luồng dữ liệu
)
Đâ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ô
hình SIMD (
Đơn luồng lệnh, đa dữ liệu
)

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ế.

7
1.1.2.2. Phân loại theo mô hình bộ nhớ
 Mô hình bộ nhớ chia sẻ
Đặ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.

Ưu điểm chính của mô hình này là cung cấp một vúng nhớ toàn cục do đó dễ
dàng cho việc lập trình về mặt sử dụng bộ nhớ đồng thời việc trao đổi thông tin
giữa các modul tính toán là tương đối nhanh chóng và dễ dàng.

Hình 1.5: Máy tính chia sẻ bộ nhớ
Nhược điểm của mô hình này chính là sự mất cân đối giữa CPU và bộ nhớ.
Việc tăng CPU làm tăng thêm lưu lượng trên đường dẫn từ bộ nhớ tới CPU.
 Mô hình bộ nhớ phân tán
Mô hình này yêu cầu một mạng truyền thông để kết nối các bộ nhớ của các bộ
vi xử lý. Mỗi CPU đều gắn với một bộ nhớ riêng và các thao tác của mỗi CPU trên
bộ nhớ của mình thì không được các CPU khác biết tới.
Ưu điểm của mô hình này là kích thước bộ nhớ cân bằng với số lượng các bộ
xử lý.

Hình 1.6: Máy tính bộ nhớ phân tán

8
Nhược điểm chính của mô hình này chính là người lập trình phải tự thiết lập
lấy phương thức trao đổi thông tin giữa các CPU trong quá trình tính toán mà việc

kế giải thuật giải thuật trở nên đơn giản hơn. Lập trình song song đưa thêm những
khó khăn mới vào mô hình lập trình tuần tự. Nếu chương trình được thực hiện ở
mức thấp nhất thì không những số lệnh thực hiện là rất lớn mà nó còn phải quản lý
trực tiếp quá trình thực hiện song song của hàng nghìn bộ xử lý và kết hợp hàng
triệu tương tác liên bộ xử lý. Bởi vậy khả năng trừu tượng và tính toán module là
các đặc tính rất quan trọng trong lập trình song song. Các mô hình thông dụng bao
gồm:
- Mô hình chia sẻ bộ nhớ.
- Mô hình luồng.
- Mô hình truyền thông điệp.
- Mô hình song song dữ liệu.
1.2.1. Mô hình chia sẻ bộ nhớ
Trong mô hình này, nhiệm vụ cùng chia sẻ một không gian địa chỉ chung có
thể được truy cập đọc ghi theo phương thức không đồng bộ.Các cơ chế khác nhau
như khóa (locks) và semaphore được điều khiển để truy cập đến bộ nhớ toàn cục.
Nhược điểm của mô hình này là khó giữ lại được tính nguyên thủy của dữ liệu
khi mà nhiều bộ xử lý dùng cùng dữ liệu này.
Lợi thế của mô hình là người lập trình không cần chỉ định việc truyền sữ liệu
giữa các task; chương trình được phát triển thường được đơn giản hóa.
1.2.2. Mô hình luồng
Trong mô hình luồng chương trình chính được chia thành các nhiệm vụ. Mỗi
nhiệm vụ được thực hiện bởi các luồng một cách đồng thời. Mỗi một luồng có dữ
liệu riêng của nó và chia sẻ dữ liệu toàn cục của chương trình chính. Các nhiệm vụ
đưa cho mỗi luồng là các thủ tục con của chương trình chính. Và bất kì luồng nào
cũng có thể thực hiện bất kì thủ tục con nào tại cùng thời điểm với các luồng
khác.Trong mô hình luồng các luồng kết nối với nhau thông qua bộ nhớ toàn cục

10
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 .

đượ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
theo một cấu trúc nhất định như là mảng hoặc theo khối. Với mô hình này thì các
nhiệm vụ của chương trình làm việc với cùng một cấu trúc dữ liệu. Tuy nhiên mỗi
nhiệm vụ sẽ làm việc trên từng phân vùng khác nhau của dữ liệu và các nhiệm vụ
phải thưc hiện các thao tác giống nhau.

Hình 1.9:
Mô
hình lập trình phân hoạch dữ liệu
Trong kiến trúc chia sẻ bộ nhớ chung, tất cả các nhiệm vụ truy cập vào cấu
trúc dữ liệu thông qua bộ nhớ toàn cục. Còn đối với kiến trúc bộ nhớ phân tán thì dữ
liệu được chia ra và lưu trữ trên các bộ nhớ cục bộ của các bộ xử lý.
1.3. Thiết kế và đánh giá thuật toán song song
1.3.1. Định nghĩa thuật toán song song
Thuật toán song song là một tập hợp các tiến trình (process) hay các tác vụ (task)
có thể thực thi đồng thời và có thể trao đổi dữ liệu với nhau để kết hợp giải quyết vấn
đề đặt ra. [6]
Những thuật toán, trong đó có một số thao tác có thể thực hiện đồng thời được
gọi là thuật toán song song.
12
1.3.2. Các nguyên lý thiết kế thuật toán song song
Khi muốn thực hiện việc xử lý song song ta phải xét cả kiến trúc máy tính và
các thuật toán song song. Để thiết kế được các thuật toán song song cần phải thực
hiện.
- Phân chia dữ liệu cho các tác vụ.
- 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ý)
13
1.3.3. Các cách tiếp cận trong thiết kế thuật toán song song
Có ba phương pháp tiếp cận để thiết kế thuật toán song song:
- Song song hoá những thuật toán tuần tự, biến đổi những cấu trúc tuần tự để
tận dụng khả năng song song tự nhiên của tất cả các thành phần trong hệ
thống xử lý.
- Thiết kế thuật toán song song mới trên cơ sở thuật toán song song đã có
- Thiết kế thuật toán song song hoàn toàn mới thích ứng với những cấu trúc
song song.
1.3.4. Phân tích và đánh giá thuật toán song song.
Trong thuật toán tuần tự chúng ta chỉ quan tâm tới độ phức tạp về thời gian và
không gian, nhưng trong thuật toán song song thường có thêm một số đại lượng đo
lường khác. Độ phức tạp thời gian của thuật toán song song không chỉ đơn giản là
việc đếm số câu lệnh cơ bản như trong thuật toán tuần tự mà thay vào đó nó phụ
thuộc vào các phép toán cơ bản này có thể được thực hiện trên
 
1

pp
bộ xử lý
như thế nào. Bên cạnh độ phức tạp thời gian độ phức tạp về số bộ xử lý cũng là một
đại lượng quan trọng trong phân tích thuật toán song song.
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ố

giới hạn chỉ có nghĩa sử dụng khi chúng có thể chuyển đổi về thuật toán song song
bị giới hạn.
Thời gian tính toán song song
Để đánh giá được độ phức tạp tính toán của các thuật toán song song, ngoài số
bước tính toán chúng ta còn cần đánh giá thời gian truyền thông của các tiến trình.
Trong một hệ thống truyền thông điệp, thời gian truyền thông điệp cũng phải được
xem xét trong thời gian thực hiện của thuật toán.
Thời gian thực hiện song song: ký hiệu là
p
t
gồm hai phần
comp
t
và
comm
t

p comp comm
t t t 
. (1.1)
Trong đó,
comp
t
là thời gian tính toán và
comm
t
là thời gian truyền thông dữ liệu.
Thời gian tính toán
comp
t

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
 
TO
đơn vị thời gian, sử dụng
p
bộ xử lý trong
p
t
đơn vị thời gian, khi đó
chi phí cho thuật toán song song
p
C
:

p p
C p t 
. (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ự t