ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

PHAN THỊ GIANG
NGHIÊN CỨU VÀ ỨNG DỤNG CÁC THUẬT TOÁN
GIẢI CÁC BÀI TOÁN TÍNH TOÁN TRÊN
COMPUTER CLUSTER
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Thanh Thuỷ, người đã có những định hướng, những kiến thức quý báu, những
lời động viên và chỉ bảo giúp học viên vượt qua những khó khăn để học viên
hoàn thành tốt luận văn của mình.
Học viên xin được bày tỏ lòng cảm ơn và sự kính trọng của mình đến các
thầy cô giáo Trường Đại học Công nghệ Thông tin và Truyền Thông, Đại học
Thái Nguyên, các thầy bên Viện Công nghệ thông tin, đặc biệt là các thầy cô
giáo đã giảng dạy và giúp đỡ học viên trong suốt quá trình học tập tại trường.
Học viên cũng đặc biệt cảm ơn tới bạn bè lớp Cao học K9, các đồng
nghiệp đã luôn động viên, giúp đỡ học viên trong quá trình học tập và công
tác, để học viên hoàn thành nhiệm vụ được giao.
Xin chân thành cảm ơn sự quan tâm, giúp đỡ, chia sẻ, động viên về tinh
thần và vật chất của người thân trong gia đình, bạn bè để học viên hoàn thành
luận văn.
Thái Nguyên, tháng 10 năm 2012

Học viên
Phan Thị Giang
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

iv
MỤC LỤC
LỜI CAM ĐOAN 1
LỜI CẢM ƠN iii
MỤC LỤC iv
MỞ ĐẦU 1
1. Lý do chọn đề tài 1
2. Đối tượng và phạm vi nghiên cứu 1

2.5. Cách cài đặt và cấu hình Cluster trên Linux 42
2.5.1. Khái niệm LVS 43
2.5.2. Các mô hình LVS 44
2.5.3. Mô hình Virtual Server via NAT 44
2.5.4. Mô hình Virtual Server via Tunneling 45
2.5.5. Mô hình Virtual Server via Direct Routing 46
2.5.6. Cách triển khai các mô hình 47
2.5.7. Các bước triển khai LVS via Direct Routing 47
2.6. Tính toán phân tán bằng Cluster 53
2.6.1. Lập trình trên môi trường MPI 53
2.6.2. Cài đặt MPICH2 55
2.6.3. Tính toán trên MPI 57
2.6.4. Các mô hình tương tác trong lập trình MPI 61
Chƣơng 3. CÀI ĐẶT THỬ NGHIỆM 66
3.1. Phương trình vi phân đạo hàm riêng 66
3.2. Phương trình Laplace 67
3.3. Công thức lặp Jacobi 69
3.3.1. Giá trị riêng của ma trận lặp Jacobi 70
3.3.2. Tính toán Jacobi 71
3.4. Song song hóa thuật toán 73

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

vi
3.5. Kết quả thực hiện 74
3.5.1. Thông tin chung về hệ thống 74
3.5.2. Giao diện và lệnh thực hiện 74
3.5.3. Kết quả thực hiện tuần tự 77
3.5.4. Kết quả thực hiện thực hiện xử lý song song trên nhiều máy 77
3.6. Nhận xét và đánh giá 78

Hình 2.6. Mô hình chuẩn gồm 4 server 48
Hình 2.7. 6 vi xử lý kết nối với nhau thành hình tròn 63
Hình 2.8. Các vi-xử-lý kết nối với nhau thành lưới 64
Hình 3.1. Miền Ω và đường biên ∂Ω 67
Hình 3.2. Sai phân hữu hạn (Finite difference) 68

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

viii
Hình 3.3. Phương trình Laplace/Poisson biểu diễn trên một hình lưới hình chữ
nhật với N
x
x N
y
điểm. 69
Hình 3.4. Cấu trúc dải của ma trận lặp Jacobi cho phương trình Laplace/
Poisson 70
Hình 3.5. Thực hiện tính toán Jacobi trên một đối tượng 73
Hình 3.6a. Đăng nhập vào trung tâm với tên ccs1.hnue.edu.vn 75
Hình 3.6b. Nhập thông tin tài khoản 75
Hình 3.6c. Sử dụng phần mềm winscp để đăng nhập vào hệ thống 75
Hình 3.6d. Các file trên tài khoản đăng nhập vào hệ thống 76
Hình 3.7. Thời gian thực hiện trên tính toán tuần tự > 200s 77
Hình 3.8a. Lệnh qsub –q l1 –l nodes=2:ppn=4 Laplace.script trên 2 77
Hình 3.8b. Kết quả thời gian thực hiện 77
Hình 3.8c. Kết quả lưu trữ trên tệp. dat 78 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn


4. Phƣơng pháp nghiên cứu
- Về lý thuyết:
+ Ứng dụng các kết quả của lý thuyết xử lý song song.
+ Nắm bắt cách thức xây dựng và hoạt động của Computer Cluster, từ đó
xây dựng và triển khai Computer Cluster theo yêu cầu của các bài toán.
+ Nghiên cứu triển khai các thuật toán xử lý song song trên Computer
Cluster.
- Về thực nghiệm:
+ Xây dựng và triển khai Computer Cluster.
+ Cài đặt liên quan tới bài toán thực tế.
5. Ý nghĩa khoa học của đề tài
Luận văn nghiên cứu chi tiết lý thuyết xử lý song song và xử lý phân tán,
nghiên cứu việc cài đặt hệ thống Cluster server và ứng dụng để giải phương
trình vi phân đạo hàm riêng Laplace, một phương trình có ứng dụng lớn trong
khoa học kỹ thuật và có cách giải rất phức tạp. Các kết quả khả quan thu được
sẽ minh chứng nói lên triển vọng tính toán song song của Computer Cluster.
6. Cấu trúc của luận văn
Nội dung của luận văn được chia thành 3 chương như sau:
Chương I: Lý thuyết xử lý song song và phân tán.
Chương II: Cluster và tính toán phân tán bằng Cluster.
Chương III: Cài đặt thử nghiệm. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

3

Chƣơng 1
LÝ THUYẾT XỬ LÝ SONG SONG VÀ PHÂN TÁN
Trong chương này chúng ta sẽ tìm hiểu thế nào là xử lý song song và xử

Trong tính toán song song thì nhiều BXL cùng kết hợp với nhau để giải
quyết một bài toán nên sẽ 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.

Hình 1.2. Mô hình xử lý song song
Mục đích của xử lý song song: là thực hiện tính toán nhanh trên cơ sở
sử dụng nhiều BXL đồng thời. Cùng với tốc độ xử lý nhanh hơn, việc xử lý
song song cũng giải được những bài toán lớn hơn, phức tạp hơn.
Ba yếu tố chính dẫn đến việc xây dựng các hệ thống xử lý song song:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

5

1. Hiện nay giá thành của phần cứng (CPU) giảm mạnh, tạo điều kiện để
xây dựng những hệ thống có nhiều BXL với giá thành hợp lý.
2. Sự phát triển của công nghệ mạch tích hợp (VLSI) cho phép tạo ra
những hệ thống có hàng triệu transistor trên một chip.
3. Tốc độ xử lý của các BXL theo kiểu Von Neumann đã dần tiến tới giới
hạn, không thể cải tiến thêm được do vậy dẫn tới đòi hỏi phải thực hiện
xử lý song song.
Những yếu tố trên thúc đẩy các nhà nghiên cứu phải tập trung khai thác
công nghệ xử lý song song. 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), thuật toán và ngôn
ngữ lập trình, v.v…
Một máy tính song song: là một tập các BXL (thường là cùng một loại)
kết nối với nhau theo một kiến trúc nào đó để có thể hợp tác trong hoạt động
và trao đổi dữ liệu được với nhau [5].
Các máy tính song song có thể phân thành nhiều loại dựa vào các đặc
trưng của các kiến trúc và việc tổ chức bộ nhớ. Phần lớn các hệ điều hành

tiếng được nhiều người chấp nhận. Máy tính song song được phân chia thành
các loại:
+ SISD: Single Instruction Stream, Single Data Stream: Đơn luồng lệnh,
đơn luồng dữ liệu.
+ SIMD: Single Instruction Stream, Multiple Data Stream: Đơn luồng
lệnh, đa luồng dữ liệu.
+ MISD: Multiple Instruction Stream, Single Data Stream: Đa luồng
lệnh, đơn luồng dữ liệu.
+ MIMD: Multiple Instruction Stream, Multiple Data Stream: Đa luồng
lệnh, đa luồng dữ liệu.
a) Mô hình SISD (Simple Instruction Simple Data)

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

7

Máy tính loại SISD chỉ có một CPU, ở mỗi thời điểm thực hiện một chỉ lệnh
và chỉ đọc, ghi một mục dữ liệu. Tất cả các máy tính SISD chỉ có một thanh ghi
register được gọi là bộ đếm chương trình được sử dụng để nạp địa chỉ của lệnh
tiếp theo khi xử lý tuần tự và kết quả là thực hiện theo một thứ tự xác định của các
câu lệnh. Hình 1.3 mô tả hoạt động của máy tính theo mô hình SISD.

Hình 1.3. Mô hình của kiến trúc SISD
Mô hình SISD còn được gọi là SPSD (Simple Program Simple Data),
đơn chương trình và đơn luồng dữ liệu.
b). Mô hình SIMD (Simple Instruction Multiple Data)
Máy tính loại SIMD có một đơn vị điều khiển để điều khiển nhiều đơn vị
xử lý (nhiều hơn một đơn vị) thực hiện theo một luồng các câu lệnh. CU phát
sinh tín hiệu điều khiển tới tất cả các phần tử xử lý, những BXL 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, nghĩa là mỗi BXL có

Hình 1.6. Mô hình của kiến trúc MISD
 Lớp các máy tính có các luồng dữ liệu được gửi tuần tự theo dãy các
CPU liên tiếp. Đây là loại kiến trúc hình ống, xem xét như sau:
Nguyên lý hình ống (pipelined) dựa vào phương pháp phân đoạn hoặc
chia nhỏ một tiến trình tính toán thành một số đoạn nhỏ hơn để thực hiện
trong các pha liên tiếp. Tất cả các giai đoạn của một tiến trình được thực hiện
tuần tự, khi thực hiện xong thì bắt đầu thực hiện của tiến trình tiếp theo. Mỗi
pha thực hiện xong sẽ gửi kết quả cho pha tiếp theo. Như vậy, trong cách thực
hiện theo nguyên lý hình ống, khi một giai đoạn công việc đang thực hiện thì
một giai đoạn khác có thể nạp dữ liệu vào và dữ liệu vào của giai đoạn này có
thể là kết quả của giai đoạn trước nó.
Ví dụ, hình 1.6.1 mô tả một tiến trình được phân thành 4 giai đoạn thực
hiện tuần tự, nhưng có thể thực hiện song song theo nguyên lý hình ống để
tăng tốc độ tính toán khi phải thực hiện nhiều tiến trình như thế.
Một tiến trình được chia thành 4 giai đoạn:

Thực hiện tuần tự hai tiến trình phải qua 8 giai đoạn:

Thực hiện theo hình ống hai tiến trình trên chỉ cần trải qua 5 giai đoạn:

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

10 Hình 1.6.1. Thực hiện tuần tự và hình ống của hai tiến trình gồm 4 giai
đoạn
Nếu ký hiệu S
i
là thời gian cần thiết để thực hiện giai đoạn thứ i thì:

hiện những luồng lệnh (chương trì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 (global) khi cần, do vậy giảm thiểu được sự trao đổi giữa
các BXL trong hệ thống. Đây là kiến trúc phức tạp nhất, nhưng nó là mô hình

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

11

hỗ trợ xử lý song song cao nhất và đã có nhiều máy tính được sản xuất theo
kiến trúc này, ví dụ: BBN Butterfly, Alliant FX, iSPC của Intel, v.v Hình 1.8. Mô hình của kiến trúc MIMD
1.2.4. Song song hóa trong máy tính tuần tự
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ế. Nhưng cấu trúc phần cứng thường là trong suốt đối với
những người lập trình. Sau đây chúng ta tìm hiểu về kỹ thuật song song áp
dụng trong các máy tính có một BXL.
a) Đa đơn vị chức năng
Hầu hết các máy tính truyền thống chỉ có một đơn vị số học và logic
(ALU) trong BXL. Ở mỗi thời điểm nó chỉ có thể thực hiện một chức năng.
Nhiều máy tính thực tế hiện nay có thể có nhiều đơn vị chức năng (nhất là


12

phép toán rất cơ bản như: phép cộng, nhân, chia, tăng giảm, các phép logic và
các phép dịch chuyển (shift). Với 10 đơn vị chức năng và 24 thanh ghi
(register), máy tính CDC 6600 có thể thực hiện tính toán với tốc độ tăng lên
đáng kể, đáp ứng được nhiều bài toán xử lý song song.
Vấn đề chính đối với những máy tính loại này là cần phải xây dựng bộ
lập lịch tối ưu để phân chia các câu lệnh thực hiện sao cho tận dụng được tối
đa các đơn vị chức năng cũng như các tài nguyên mà máy tính cung cấp.
b) Xử lý theo nguyên lý hình ống trong CPU
Nhiều pha thực hiện khác nhau của các câu lệnh có thể thực hiện theo
nguyên lý hình ống, ví dụ nạp cậu lệnh về từ bộ nhớ, giải mã (decode), xác
định các toán hạng, thực hiện các phép số học/logic và lưu trữ kết quả, v.v.
Những câu lệnh trong chương trình có thể thực hiện gối đầu nhau theo nguyên
lý hình ống và nó sẽ hiệu quả hơn khi dựa vào kỹ thuật tạo ra vùng đệm dữ
liệu. Bằng cách thực hiện như trên thì trong quá trình thực hiện của BXL có
thể thực hiện được nhiều câu lệnh gối đầu nhau trong cùng một thời gian.
Trước khi một câu lệnh kết thúc thực hiện thì câu lệnh tiếp theo đã có thể thực
hiện pha giải mã, câu lệnh khác lại có thể được nạp về, v.v
c) Sự gối đầu CPU và các thao tác vào/ra (I/O)
Nhiều phép vào/ra có thể thực hiện đồng thời đối với nhiều nhiệm vụ
tính toán khác nhau bằng cách sử dụng những bộ điều khiển vào/ra, các kênh
hay những BXL vào/ra khác nhau.
Nhiều máy tính hiện nay có nhiều bộ điều khiển thiết bị vào/ra, cho phép
đa xử lý vào/ra do vậy tăng được tốc độ trao đổi dữ liệu giữa các thiết bị
ngoài với CPU.
d) Các hệ thống bộ nhớ phân cấp
Tốc độ các phép toán thực hiện trong BXL nhanh hơn rất nhiều so với
việc truy cập vào bộ nhớ và tốc độ truy cập vào bộ nhớ trong (RAM) nhanh

đượ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 BXL 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ý.
Kết luận: Sự phát triển của công nghệ phần cứng dẫn tới xu thế xử lý
song song để đáp ứng các yêu cầu tính toán của nhiều bài toán trong thực tế.
Nhiều máy tính có kiến trúc song song như các loại máy tính kiểu SIMD,
MISD, MIMD ra đời tạo điều kiện cho công nghệ xử lý song song phát triển
cả về mặt công nghệ lẫn triển khai ứng dụng. Vấn đề xử lý song song cũng có
thể thực hiện được trên các máy tuần tự kiểu Von Neumann bằng cách sử dụng
nguyên lý xử lý hình ống hay chia sẻ thời gian, v.v
1.3. Lý thuyết xử lý phân tán
1.3.1. Khái niệm
Xử lý phân tán bao gồm một loạt các hệ thống máy tính, sử dụng nhiều
hơn một máy tính, hoặc bộ xử lý để chạy một ứng dụng. Bao gồm xử lý song
song, trong đó một máy tính đơn sử dụng nhiều hơn một CPU để thực hiện
chương trình. Xử lý phân tán có thể sử dụng trong mạng LAN được thiết kế để
cho một chương trình đơn có thể chạy đồng thời ở các địa điểm khác nhau.
Một hình thức xử lý phân tán bao gồm cơ sở dữ liệu phân tán, cơ sở dữ
liệu trong đó dữ liệu được lưu trữ trên hai hoặc nhiều hệ thống máy tính. Hệ
thống cơ sở dữ liệu theo dõi các dữ liệu ở đó được phân phối tới người sử dụng.

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

15

1.3.2. Tính toán phân tán
Tính toán phân tán là những tính toán được thực hiện trên cơ sở kết hợp
khả năng tính toán và truyền thông của hai hay nhiều máy tính trên mạng.

hình gửi/nhận thông báo là các tiến trình. Tuy nhiên cũng có một số điểm
khác nhau giữa hai mô hình này, trong mô hình gửi/nhận thông báo:
 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
truy cập được vào không gian bộ nhớ chia sẻ. Vì lý do này, những
chương trình trao đổi thông điệp với nhau còn được gọi là các chương
trình phân tán.
 Các chương trình phân tán trao đổi dữ liệu với nhau qua hệ thống mạng
cục bộ hoặc mạng diện rộng.
 Việc truyền thông và đồng bộ hóa hoạt động của các tiến trình được
thực hiện thông qua hai phương thức send() và receive().
 Tất cả các biến là cục bộ của các tiến trình. Vì thế, những vấn đề về
xung đột dữ liệu (cần phải khoá dữ liệu khi một tiến trình truy cập), hay
tranh chấp thông tin (bài toán loại trừ nhau) không xuất hiện trong mô
hình tính toán phân tán.
 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ế gửi/nhận thông báo. 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ự. Ở đây không có các
buffer để tạm lưu giữ các thông điệp cần trao đổi giữa các tiến trình.
1.4.2. Mô hình tổng quát

Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn

17

Trong mô hình gửi/nhận thông báo các tiến trình chia sẻ với nhau kênh
truyền thông. Kênh (channel) là khái niệm trừu tượng của đường truyền thông
vật lý giữa các tiến trình.
Các kênh được truy cập bởi hai phương thức: send() và receive(). Để bắt
đầu trao đổi được với nhau thì một tiến trình phải gửi đi (send) một thông