`ĐẠ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
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


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........................................................................................................9
Chương 1 – TÍNH TOÁN SONG SONG ...................................................11
1.1.

Tổng quan về xử lý song song .......................................................... 11

1.2.

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

1.3.

1.4.

1.2.1.

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

1.2.2.

Mô hình luồng ...................................................................... 17


1.4.2.

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

3


1.4.3.

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

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

Đặt vấn đề ........................................................................................ 30

2.2.

Bài toán tìm xâu con chung dài nhất ................................................. 31

2.3. Thuật toán quy hoạch động giải bài toán tìm xâu con chung dài nhất
của hai xâu. .................................................................................................. 32
2.4.

Phương pháp phần tử trội trong bài toán xâu con chung dài nhất...... 36

2.5.

Phương pháp song song trong bài toán xâu con chung dài nhất. ....... 41

Nghĩa tiếng Việt

CPU

Central Processing Unit

Bộ xử lý trung tâm

DNA

Deoxyribo nucleic acid

Axít deoxyribosenucleic

HPC

High Performance Computing

Tính toán/máy tính hiệu năng cao

LCS

Longest Common Subsequence

Dãy con chung dài nhất.

MIMD

Multiple Instruction multiple Data


Đơn luồng lệnh đa luồng dữ liệu

SISD

Simple Instruction simpleData

Đơn luồng lệnh đơn luồng dữ liệu

TCP

Transmission Control Protocol

Giao thức điều khiển truyền thông

UDP

User Datagram Protocol

Giao thức gói người dùng

UMA

Uniform Memory Access

Truy cập bộ nhớ đồng thời

5


DANH MỤC CÁC BẢNG

Hình 1.2: Mô hình máy MIMD..............................................................................13
Hình 1.3: Mô hình máy tính SIMD ........................................................................13
Hình 1.4: Mô hình máy MIMD..............................................................................14
Hình 1.5: Máy tính chia sẻ bộ nhớ .........................................................................15
Hình 1.6: Máy tính bộ nhớ phân tán ......................................................................15
Hình 1.7: Mô hình luồng .......................................................................................18
Hình 1.8: Mô hình truyền thông điệp .....................................................................18
Hình 1.9: Mô hình lập trình song song dữ liệu.......................................................19
Hình 1.10 Luật Amdahl .........................................................................................24
Hình 1.11: Sự trao đổi thông điệp giữa hai tiến trình .............................................25
Hình 1.12: Cấu trúc chương trình MPI ..................................................................29
Hình 3.1. Thời gian chạy của thuật toán với 8 xâu độ dài 64 trên bảng chữ cái 4 và
20 ký tự...................................................................................................55
Hình 3.2. Thời gian chạy của thuật toán với 2 xâu độ dài 4096 trên bảng chữ cái 20
ký tự. ......................................................................................................55
Hình 3.3. Hệ số tăng tốc của thuật toán với 2 xâu độ dài 4096 trên bảng chữ cái 20
ký tự. ......................................................................................................56
Hình 3.4. Hệ số tăng tốc của thuật toán với 8 xâu độ dài 64 trên bảng chữ cái 4 và
20 ký tự...................................................................................................56
Hình 3.5. Hệ số hiệu quả của thuật toán với 8 xâu độ dài 64 trên bảng chữ cái 4 và
20 ký tự...................................................................................................57

7


DANH MỤC CÁC THUẬT TOÁN

Trang

Thuật toán 2.1. Thuật toán tuần tự tìm dãy con chung dài nhất..................... 34

làm được điều đó.
Hiện nay trên thế giới đã có những máy tính song song chứa đến hàng nghìn
bộ xử lý. Để khai thác tiềm năng và sức mạnh của máy tính song song, cùng với
việc thiết kế kiến trúc song song ta còn phải nghiên cứu những vấn đề quan trọng
khác như hệ điều hành hỗ trợ xử lý song song, các ngôn ngữ lập trình và thuật toán
song song.

9


Việc nghiên cứu thiết kế các máy tính song song, và các thuật toán song song
cũng như các ngôn ngữ lập trình hỗ trợ lập trình song song bắt đầu được quan tâm
từ những năm 70, cho đến nay các ứng dụng của chúng đã lan rộng khắp các lĩnh
vực của đời sống như đánh giá khả năng rủi ro về tài chính: dùng để mô hình hoá
các xu hướng trên thị trường… Hỗ trợ quyết định như phân tích thị trường, dự báo
thời tiết… Trí tuệ nhân tạo như thiết kế robot… Xử lý ảnh ứng dụng trong công
nghệ nhận dạng… Điều khiển tự động… Trong đó bài toán có liên quan tới sắp xếp
đóng một vai trò quan trọng, hay gặp trong các lời giải các bài toán tìm kiếm, tra
cứu, … Do vậy việc nghiên cứu các thuật toán sắp xếp cơ bản, đặc biệt là các thuật
toán song song trên bài toán sắp xếp là rất cần thiết.
Trong phạm vi luận văn này trình bày ba phần chính, Chương 1 trình bày tổng
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ả.

10

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
Định nghĩa về xử lý song song
Tính toán song song hay xử lý song song: là quá trình xử lý thông tin trong đó
nhiều đơn vị dữ liệu được xử lý đồng thời bởi một hay nhiều bộ xử lý để giải quyết
một bài toán. [1]
Máy tính song song là tập hợp các bộ xử lý kết nối với nhau theo một kiến trúc
xác định để cùng hợp tác hoạt động và trao đổi dữ liệu. [1]

11


Phân biệt xử lý song song và xử lý tuần tự
Trong tính toán tuần tự với một bộ xử lý thì tại mỗi thời điểm chỉ được thực
hiện một phép toán. Trong tính toán song song thì nhiều bộ xử lý cùng kết hợp với
nhau để giải quyết cùng một bài toán cho nên giảm được thời gian xử lý vì mỗi thời
điểm có thể thực hiện đồng thời nhiều phép toán.
Mục đích của xử lý song song
Thực hiện tính toán nhanh trên cơ sở sử dụng nhiều bộ xử lý đồng thời. Cùng
với tốc độ xử lý nhanh, việc xử lý song song cũng sẽ giải được những bài toán phức
tạp yêu cầu khối lượng tính toán lớn.
Vấn đề xử lý song song
Liên quan trực tiếp đến kiến trúc máy tính, phần mềm hệ thống (hệ điều 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

các phần tử xử lý, những bộ xử lý này cùng thực hiện một phép toán trên các mục
dữ liệu khác nhau.

Hình 1.3: Mô hình máy tính SIMD

•

Mô hình MISD (Đa luồng lệnh, đơn dữ liệu)
Máy tính MISD có thể thực hiện nhiều nhiều lệnh trên cùng một mục dữ liệu,
- Các máy tính yêu cầu mỗi đơn vị xử lý (PU) nhận những lệnh khác nhau để

thực hiện trên cùng một mục dữ liệu.

13


- Các máy tính có các luồng dữ liệu được chuyển tuần tự theo dãy các CPU
liên tiếp gọi là kiến trúc hình ống xử lýtheo vector thông qua một dãy các bước,
trong đó mỗi bước thực hiện một chức năng và sau đó chuyển kết quảcho PU thực
hiện bước tiếp theo
•

Mô hình MIMD (đa luồng lệnh, đa luồng dữ liệu)
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.


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

15


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
này đôi khi là rất khó khăn.
•

Mô hình bộ nhớ lai.
Hầu hết các máy tính nhanh và lớn ngày nay đều xây dựng dựa trên sự kết hợp

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ư

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

17


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

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.

19


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.

-


-

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 p ( p > 1) 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ố
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à

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à t p gồm hai phần t comp và t comm

t p = tcomp + tcomm .

(1.1)

Trong đó, t comp là thời gian tính toán và t comm là thời gian truyền thông dữ liệu.
Thời gian tính toán t comp được xác định giống như thuật toán tuần tự. Khi có
nhiều tiến trình thực hiện đồng thời thì chỉ cần tính thời gian thực hiện của tiến trình

22


phức tạp nhất. Trong phân tích độ phức tạp tính toán, chúng ta luôn giả thiết rằng,
tất cả các bộ xử lý là giống nhau và cùng một tốc độ xử lý như nhau. Đối với những
cụm máy tính không thuần nhất thì điều này không đảm bảo nên việc đánh giá thời
tính toán của những hệ như thế là rất phức tạp.
Thời gian truyền thông t comm lại phụ thuộc vào kích cỡ của các thông điệp, vào
cấu hình kết nối mạng đường truyền và cả cách thức truyền tải thông điệp. Công
thức ước lượng thời gian truyền thông được xác định như sau:

tcomm = tstartup + n × tdata .

(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



Giả sử các bộ xử lý trong hệ thống song song hoàn toàn giống với bộ xử lý sử
dụng trong tính toán tuần tự và ts là thời gian thực hiện bài toán bằng tính toán tuần
tự tối ưu nhất. Hệ số tăng tốc lí tưởng đạt được khi S p = p .
Rõ ràng khả năng tăng tốc càng lớn thì giải thuật song song càng tốt.
Tuy nhiên, năm 1967 Amdahl đã đưa ra luật về giới hạn khả năng tăng tốc như
sau:
Khi tăng số lượng bộ xử lý trong máy tính song song, khối lượng công việc
được phân phối cho nhiều bộ xử lý thực hiện. Mục tiêu chính là tìm được kết quả
bài toán nhanh nhất có thể hay nói cách khác là giảm đến mức tối đa thời gian tính
toán.

Luật Amdahl: luật này phát biểu rằng nếu P là tỉ lệ có thể song song hóa của
thuật toán tuần tự thì hệ số tăng tốc lớn nhất có thể đạt được khi sử dụng N bộ xử
1

lý là

(1 − P ) +

P
N

.

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