Luận văn Thạc sĩ Khoa học máy tính: 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

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

Thái Nguyên - 2012

LỜI CAM ĐOAN

Học viên xin khẳng định tất cả các kết quả được trình bày trong luận văn

là của riêng học viên, không sao chép từ bất kỳ một công trình nào khác. Nếu

có điều gì không trung thực, học viên xin hoàn toàn chịu trách nhiệm.

Học viê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

Phan Thị Giang

iii

LỜI CẢM ƠN

Luận văn được thực hiện tại trường Đại học Công nghệ Thông tin và

Truyền Thông – Đại học Thái Nguyên dưới sự hướng dẫn của GS.TS Nguyễn

Thanh Thuỷ.

Trước hết học viên xin bày tỏ lòng biết ơn sâu sắc tới thầy Nguyễn

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

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

Phan Thị Giang

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

3. Hướng nghiên cứu của đề tài ...................................................................... 1

4. Phương pháp nghiên cứu ............................................................................ 2

5. Ý nghĩa khoa học của đề tài ........................................................................ 2

6. Cấu trúc của luận văn ................................................................................. 2

Chƣơng 1. LÝ THUYẾT XỬ LÝ SONG SONG VÀ PHÂN TÁN .............. 3

1.1. Giới thiệu chung ...................................................................................... 3

1.2. Lý thuyết xử lý song song ....................................................................... 3

1.2.1. Khái niệm .......................................................................................... 3

1.2.2. Phân biệt xử lý song song với tuần tự ............................................... 3

1.2.3. Phân loại máy tính song song ............................................................ 6

1.2.4. Song song hóa trong máy tính tuần tự ............................................ 11

1.3. Lý thuyết xử lý phân tán ........................................................................ 14

1.3.1. Khái niệm ........................................................................................ 14

1.3.2. Tính toán phân tán ........................................................................... 15

1.4. Các phương pháp giải bài toán bằng xử lý song song và phân tán ....... 15

1.4.1. Mô hình gửi/nhận thông báo ........................................................... 16

1.4.3. Mô hình lập trình ............................................................................. 19

1.4.4. Lập trình trên cụm máy tính ............................................................ 23

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

Chƣơng 2. CLUSTER VÀ TÍNH TOÁN PHÂN TÁN BẰNG CLUSTER26

2.1. Mô hình chung của hệ thống Cluster ..................................................... 26

2.1.1. Mô hình ........................................................................................... 26

2.1.2. Chế độ hoạt động của Cluster ......................................................... 27

2.1.3. Một số ứng dụng trong Cluster ....................................................... 29

2.2. Các ưu điểm của hệ thống Cluster ......................................................... 30

2.3. Các thành phần của Cluster Service ...................................................... 32

2.4. Nguyên tắc hoạt động của Server Cluster ............................................. 37

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

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.4. Song song hóa thuật toán ....................................................................... 73

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

KẾT LUẬN VÀ KIẾN NGHỊ ....................................................................... 79

1. Kết luận ..................................................................................................... 79

2. Kiến nghị ................................................................................................... 79

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

TÀI LIỆU THAM KHẢO ............................................................................. 80

vii

DANH MỤC HÌNH VẼ

Hình 1.1. Mô hình xử lý tuần tự ........................................................................ 4

Hình 1.2. Mô hình xử lý song song ................................................................... 4

Hình 1.3. Mô hình của kiến trúc SISD .............................................................. 7

Hình 1.4. Mô hình của kiến trúc SIMD ............................................................ 8

Hình 1.5. Mô hình MISD .................................................................................. 8

Hình 1.6. Mô hình của kiến trúc MISD ............................................................ 9

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 10

Hình 1.7. (a) Xử lý hình ống theo ALU, (b) Xử lý hình ống theo CU ........... 10

Hình 1.8. Mô hình của kiến trúc MIMD ......................................................... 11

Hình 1.9. Hệ thống bộ nhớ phân cấp .............................................................. 13

Hình 1.10. Dịch đơn chương trình, đa thao tác dữ liệu .................................. 20

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

Hình 1.12. Sự trao đổi thông điệp của các máy tính trong hệ PVM ............... 24

Hình 1.13. Gọi hàm pvm_psend() và pvm_precv() ........................................ 25

Hình 2.1. Nguyên lý hoạt động của một Cluster ............................................. 28

Hình 2.2. Linux Virtual Server ....................................................................... 43

Hình 2.3. Mô hình Virtual Server via NAT ..................................................... 45

Hình 2.4. Mô hình Virtual Server via Tunneling ............................................ 46

Hình 2.5. Mô hình Virtual Server via Direct Routing ................................... 47

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

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

Hình 3.2. Sai phân hữu hạn (Finite difference) .............................................. 68

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 Nx x Ny đ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

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

Hình 3.8c. Kết quả lưu trữ trên tệp. dat .......................................................... 78

MỞ ĐẦU

1. Lý do chọn đề tài

Ngày nay có rất nhiều bài toán phức tạp và các ứng dụng thực tế cần

phải tính toán, giải trên một số lượng lớn các dữ liệu, nếu chúng ta sử dụng

máy tính thông thường để thực thi thì sẽ mất rất nhiều thời gian và công sức.

Để giải quyết được những khó khăn trên chúng ta có thể sử dụng một hệ

thống máy tính được kết nối với nhau gọi là Computer Cluster.

Trong cuốn luận văn này học viên đã thực hiện tìm hiểu cách thức xây

dựng một Computer Cluster cho việc giải quyết bài toán lớn (Phương trình

Laplace với công thức lặp Jacobi) bằng cách song song hóa để đưa ra sự so

sánh về thời gian thực hiện khi xử lý tuần tự.

2. Đối tƣợng và phạm vi nghiên cứu

- Lý thuyết xử lý song song, xử lý phân tán.

- Hệ thống Computer Cluster.

- Một số bài toán thực tế trong Khoa học kỹ thuật.

- Ngôn ngữ xử lý song song MPI (Message Passing Interface).

3. Hƣớng nghiên cứu của đề tài

- Nghiên cứu các lý thuyết xử lý song song, xử lý phân tán.

- Nghiên cứu cách xây dựng và vận hành Computer Cluster, tìm hiểu

các khả năng của Computer Cluster. Nghiên cứu cách cài đặt các thuật toán

xử lý song song trên Computer Cluster.

- Giải quyết một số bài toán thực tế trong khoa học kỹ thuậ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

- Tìm hiểu thêm về ngôn ngữ xử lý song song MPI.

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.

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

Chương III: Cài đặt thử nghiệm.

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ử

lý phân tán. Đồng thời đưa ra các mô hình diễn tả cách thức hoạt động trong

việc xử lý dữ liệu.

1.1. Giới thiệu chung

Hiện nay lý thuyết xử lý song song và xử lý phân tán đang được quan

tâm và nghiên cứu để giải quyết những bài toán lớn và cần tốc độ tính toán

cao mà trước đó một máy tính không thể làm được. Nó là một vấn đề quan

tâm đối với các nhà nghiên cứu ngày nay để sử dụng chiến thuật hợp tác

tương tự trong việc xây dựng các siêu máy tính có thể thực hiện hàng nghìn tỉ

tính toán trong một giây. Hầu hết các siêu máy tính đều sử dụng phương pháp

xử lý song song, chứa một giàn các bộ vi xử lý cực nhanh, làm việc đồng loạt

để giải quyết những bài toán phức tạp, dữ liệu lớn như dự báo thời tiết hoặc

mô phỏng vụ nổ hạt nhân, vv…

1.2. Lý thuyết xử lý song song

1.2.1. Khái niệm

Xử lý song song là quá trình xử lý gồm nhiều tiến trình được kích hoạt

đồng thời và cùng tham gia giải quyết một bài toán, nói chung xử lý song

song được thực hiện trên những hệ thống đa bộ xử lý [7].

1.2.2. Phân biệt xử lý song song với tuần tự

Trong tính toán tuần tự với một bộ xử lý (BXL) thì tại mỗi thời điểm chỉ

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

thực hiện được một phép toán.

Hình 1.1: Mô hình xử lý tuần tự

- Bài toán được tách thành một chuỗi các câu lệnh rời rạc

- Các câu lệnh được thực hiện một cách tuần tự

- Tại mỗi thời điểm chỉ thực hiện được một câu lệnh

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.

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

Ba yếu tố chính dẫn đến việc xây dựng các hệ thống xử lý song song:

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

ngày nay đều hỗ trợ đa xử lý/đa nhiệm và cho phép thực hiện việc xử lý song

song. Như vậy, để xử lý song song chúng ta phải có nhiều BXL (các đơn vị

tính toán độc lập) cùng hoạt động và quan trọng hơn là chúng ta phải thiết kế

các thuật toán để chúng cùng tham gia "giải quyết một bài toán". Nói cách

khác, những tiến trình thực hiện trên mỗi BXL phải trao đổi dữ liệu với nhau

để giải quyết một bài toán cho trước. Trường hợp ngược lại thì đó không phải

là xử lý song song. Chúng ta dễ nhận thấy là độ phức tạp của xử lý song song

sẽ lớn hơn xử lý tuần tự rất nhiều, tập trung chủ yếu ở phương diện truyền

thông và sự đồng bộ các tiến trình.

Một trong các mục đích chính của xử lý song song là nghiên cứu và xây

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

dựng những thuật toán thích hợp để cài đặt trên các máy tính song song, nghĩa

là phát triển các thuật toán song song. Câu hỏi tự nhiên là đánh giá một thuật

toán song song như thế nào được gọi là thích hợp cho xử lý song song? Đối

với thuật toán tuần tự thì chúng ta có thể thống nhất cách đánh giá dựa vào

thời gian thực hiện thuật toán, không gian bộ nhớ và khả năng lập trình, v.v...

Đánh giá thuật toán song song thì phức tạp hơn nhiều, ngoài những tiêu chuẩn

trên còn phải bổ sung thêm những tham số về số BXL, khả năng của các bộ

nhớ cục bộ, sơ đồ truyền thông và các giao thức đồng bộ hoá, v.v...

Để cài đặt các thuật toán song song trên các máy tính song song chúng ta

phải sử dụng những ngôn ngữ lập trình song song. Nhiều ngôn ngữ lập trình

song song đang được sử dụng như: Fortran 90, nCUBE C, Occam, C-Linda,

PVM với C/C++, CDC 6600, v.v...

1.2.3. Phân loại máy tính song song

Dựa vào các đặc tính về số lượng BXL, số chương trình thực hiện, cấu

trúc bộ nhớ, v.v..., Michael Flynn (1966) [8] đã đưa ra cách phân loại nổi

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.

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

a) Mô hình SISD (Simple Instruction Simple Data)

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

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ó

luồng dữ liệu riêng.

Mô hình SIMD còn được gọi là SPMD, đơn chương trình và đa luồng dữ

liệu. Đây chính là mô hình máy tính phổ biến có trên thị trường như: DAP và

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

Connection Machine CM-2.

Hình 1.4. Mô hình của kiến trúc SIMD

c) Mô hình MISD (Multiple Instruction Simple Data)

Máy tính loại MISD là ngược lại với SIMD. Máy tính MISD có thể thực

hiện nhiều chương trình (nhiều lệnh) trên cùng một mục dữ liệu, nên còn

được gọi là MPSD (đa chương trình, đơn luồng dữ liệu).

Hình 1.5. Mô hình MISD

Kiến trúc kiểu này có thể chia thành hai nhóm:

 Lớp các máy tính yêu cầu những đơn vị xử lý (PU) khác nhau có thể

nhận được những chỉ lệnh khác nhau để thực hiện trên cùng một mục

dữ liệu. Đây là kiến trúc khó và hiện nay chưa có loại máy tính nào

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

được sản xuất theo loại này.

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:

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

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:

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 Si là thời gian cần thiết để thực hiện giai đoạn thứ i thì:

Tổng thời gian tính toán tuần tự là: 2*(S1 + S2 + S3+ S4)

Tổng thời gian tính toán hình ống là: S1 + S2 + S3+ S4 + S4

Nguyên lý hình ống có thể áp dụng theo hai mức:

 Hình ống theo đơn vị số học: Các đơn vị số học và logic ALU được tổ

chức thành mảng, các phép toán bên trong được thực hiện theo nguyên

lý hình ống (hình 1.7.(a)).

 Hình ống theo đơn vị câu lệnh: Các đơn vị điều khiển CU được phân

đoạn và tổ chức theo hình ống (hình 1.7.(b)).

Hình 1.7.(a) Xử lý hình ống theo ALU (b) Xử lý hình ống theo CU

d) Mô hình MIMD (Multiple Instruction Multiple Data)

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

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

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

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

hỗ trợ xử lý song song cao nhất và đã có nhiều máy tính được sản xuất theo

Luồng dữ liệu 1

Luồng lệnh 1

CU 1

Phần tử xử lý 1

Luồng dữ liệu 2

Luồng lệnh 2

CU 2

Phần tử xử lý 2

. . .

Luồng dữ liệu n

Luồng lệnh n

CU n

Phần tử xử lý n

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à

những chức năng chuyên biệt) và những đơn vị này có thể thực hiện song

song được. Ví dụ máy CDC 6600 (thiết kế năm 1964) có 10 đơn vị chức năng

được tổ chức trong một BXL. Những đơn vị chức năng này độc lập với nhau

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

và do vậy có thể thực hiện đồng thời. Thường đó là các đơn vị thực hiện các

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

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ệc truy cập vào bộ nhớ và tốc độ truy cập vào bộ nhớ trong (RAM) nhanh

hơn rất nhiều so với việc truy cập vào bộ nhớ ngoài. Hệ thống bộ nhớ phân

cấp như thế có thể mô tả như hình 1.9.

Hình 1.9. Hệ thống bộ nhớ phân cấp

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 BXL và bộ nhớ 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ệ thống. Ví dụ, trong khi dữ liệu được lấy từ bộ nhớ ngoài vào bộ nhớ

chính thì đồng thời có thể gửi dữ liệu từ cache vào cho CPU.

e) Đa chương trình và chia sẻ thời gian

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ữ liệu từ những thiết bị vào/ra chung (VD:

Cổng giao tiếp, Đĩa cứng, CD, …). Chúng ta biết rằng 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ĐH sử dụng Bộ lập lịch chia sẻ thời gian là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

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 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ệ

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

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.

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.

Mô hình tính toán phân tán có những ưu điểm sau:

 Cho phép chia sẻ dữ liệu được lưu trữu ở nhiều máy tính khác nhau.

 Chia sẻ với nhau về một số chức năng chính của máy tính.

 Độ tin cậy cao hơn. Trong trường hợp có một máy tính bị trục trặc thì

những máy tính khác có thể thay thế để hoàn thành nhiệm vụ của hệ

thống.

 Tính kinh tế: thường đầu tư vào hệ phân tán sẽ thấp hơn đầu tư cho hệ

tập trung.

Tuy nhiên, hệ tính toán phân tán cũng đứng trước nhiều thách thức:

+ Những vấn đề liên quan đến việc quản trị hệ thống, vấn đề đảm bảo an

toàn hệ thống, bảo mật thông tin, v.v...

+ Xử lý trong các hệ thống phân tán không có bộ nhớ chia sẻ để trao đổi

dữ liệu với nhau. Sự trao đổi được thực hiện bằng cách gửi/nhận thông báo.

Hiện nay có nhiều công cụ lập trình được sử dụng cho tính toán phân tán

ở nhiều mức độ trừu tượng khác nhau, như PVM, MPI, vv...

1.4. Các phƣơng pháp giải bài toán bằng xử lý song song và phân tán

Những buổi đầu của tính toán với máy tính, tất cả các dữ liệu và mọi sự

tính toán đều thực hiện tập trung ở những máy tính lớn. Sau đó, với sự phát

triển của các máy tính PC, ngày càng nhiều dữ liệu được lưu trữ và được xử

lý ở những máy tính cá nhân. Những dữ liệu này cần phải được chia sẻ và các

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

tính toán ở nhiều nơi này cũng cần phải được kết hợp lại để giải quyết hiệu

quả hơn những bài toán đặt ra trong thực tế. Từ đó xuất hiện mô hình tính

toán phân tán [7].

1.4.1. Mô hình gửi/nhận thông báo

Giống như mô hình chia sẻ bộ nhớ, các đơn vị xử lý song song trong mô

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.

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

1.4.2. Mô hình tổng quát

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

điệp vào kênh truyền thông và có một tiến trình khác yêu cầu nhận (receive)

thông điệp đó. Sự trao đổi được hoàn tất khi dữ liệu đã được gửi từ địa chỉ

nguồn tới đích.

Có hai mô hình gửi/nhận thông báo:

- Gửi/nhận thông báo theo cơ chế dị bộ: Trong mô hình này, một kênh

truyền thông được giả thiết là có khả năng tiếp nhận không bị giới hạn. Khả

năng không giới hạn được cài đặt trong thực tế bằng cách sử dụng bộ đệm

(buffer) để tiếp nhận các thông điệp gửi đến cho mỗi tiến trình. Do vậy, tiến

trình gửi sẽ không phải chờ để tiến trình nhận sẵn sàng nhận mà cứ gửi khi có

dữ liệu. Ở đây, hai tiến trình gửi và nhận có thể hoạt động gần như độc lập với

nhau và thông điệp có thể nhận được sau một khoảng thời gian nào đó (lâu bất

kỳ) kể từ khi nó được gửi đi. Tuy nhiên, tiến trình nhận muốn nhận dữ liệu thì

phải chờ cho đến khi có thông điệp của một tiến trình khác gửi cho nó. Từ đó

dẫn đến một số yêu cầu sau:

o Khi tiến trình A gửi đi một thông điệp cho tiến trình B thì sau đó nó

cần phải được biết xem B có nhận được hay không, nghĩa là A phải

chờ để nhận được câu trả lời khẳng định của B.

o Việc phân phát thông điệp cũng không thể đảm bảo rằng không bị

thất bại. Nếu A gửi đi một thông điệp cho B và A không nhận được

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

câu trả lời từ B thì nó sẽ không biết là thông điệp đó đã được gửi đến

đích B hay chưa? (có thể là tiến trình B không nhận được hoặc câu trả

lời của B không đến được A).

o Tất cả các thông điệp đều phải đưa vào bộ đệm (hàng đợi), nhưng

trong thực tế không gian hàng đợi là hữu hạn. Khi có quá nhiều thông

điệp được gửi đi thì phương thức gửi sẽ bị chặn lại. Điều này vi phạm

ngữ nghĩa của mô hình gửi/nhận thông báo dị bộ.

- Gửi/nhận thông báo theo cơ chế đồng bộ: Trong mô hình này, tiến trình

gửi bị chặn lại cho đến khi tiến trình nhận sẵn sàng nhận. Ở đây, sự truyền

thông và đồng bộ hoá luôn gắn chặt với nhau. Mô hình này có thể tìm thấy ở

những hệ thống đa bộ xử lý được cài đặt dựa trên các Transputer. Mô hình

đầu tiên cho hệ thống trao đổi thông tin đồng bộ là CSP của Hoare [4].

Ưu điểm:

+ Làm cho nhiều vấn đề trong đồng bộ hoá và việc cấp phát bộ nhớ động

trở lên đơn giản hơn.

Nhược điểm:

+ Việc gắn chặt các tiến trình với thời gian phân phát thông điệp cũng

được xem như là điều kiện ràng buộc bổ sung đòi hỏi trong thiết kế và thực

thi chương trình.

+ Việc bắt tiến trình gửi phải chờ dẫn đến việc làm giảm tính đồng thời

của hệ thống.

+ Ngoài ra, để cài đặt hiệu quả các hệ thống truyền thông đồng bộ đòi

hỏi phải có những phần cứng đặc biệt để đảm bảo rằng sự truyền thông phải

cực nhanh và sự trao đổi dữ liệu không ảnh hưởng tới sự tính toán của hệ

thống. Mà các mạng truyền thông nhanh có nhiều nút mạng trao đổi dữ liệu

với nhau là rất đắt tiền. Vì những lý do trên, nên hệ gửi/nhận thông báo dị bộ

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

làm việc trên mạng cục bộ đã được phát triển mạnh mẽ hơn.

1.4.3. Mô hình lập trình

Trong phần này chúng ta định nghĩa mô hình lập trình cho hệ thống

gửi/nhận thông báo dị bộ.

Ở đây chúng ta xét các chức năng chính ở mức khái niệm như: tạo lập

nhiều tiến trình trong chương trình song song, định nghĩa các kênh truyền

thông, cơ chế ghi địa chỉ cho các tiến trình, và các chức năng đồng bộ, v.v...

Những hệ thống cụ thể, như PVM được đề cập đến ở phần sau.

Lập trình theo mô hình gửi/nhận thông báo trong hệ thống nhiều máy

tính có thể thực hiện theo ba cách:

1. 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).

2. Sử dụng ngôn ngữ lập trình bậc cao (tuần tự) được mở rộng bằng cách

bổ sung thêm các từ khoá và cú pháp mở rộng để xử lý việc trao đổi

thông điệp, ví dụ C, C++.

3. Sử dụng những ngôn ngữ lập trình bậc cao và các thư viện gồm những

thủ tục xử lý việc trao đổi thông điệp, ví dụ ngôn ngữ C/C++ và hệ

chương trình thư viện để chạy với PVM, MPI, PTHREAD, …

Chúng ta tập trung vào cách thứ ba. Trong hệ thống trao đổi thông điệp

thì vấn đề tạo lập các tiến trình để thực hiện trên những bộ xử lý khác nhau và

việc gửi, nhận thông điệp là quan trọng nhất.

Phát sinh các tiến trình con:

Một chức năng quan trọng trong lập trình song song là tạo lập ra nhiều

tiến trình để thực hiện những công việc con của một chương trình song song.

Nói chung, một chương trình bắt đầu thực hiện như một tiến trình và sau đó

phát sinh ra nhiều tiến trình con để khai thác khả năng song song của bài toá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

Có hai cách tạo lập tiến trình: tạo lập tĩnh và tạo lập động.

 Tạo lập tiến trình tĩnh: tất cả các tiến trình được xác định trước khi thực

hiện và hệ thống có một số tiến trình xác định trước. Trong các hệ

thống này thường có một tiến trình điều khiển còn được gọi là tiến trình

“chủ” (master), những tiến trình khác được gọi là tiến trình tớ (slave).

Đây là mô hình SPMD. Sau khi chương trình nguồn được viết với các

lệnh phân chia công việc cho từng tiến trình, nó sẽ được dịch sang mã

thực thi được cho những tiến trình đó. Quá trình này được mô tả như

Chương trình nguồn

Đoạn chương trình thực thi

Biên dịch theo các bộ xử lý

BXL n-1

BXL 0

hình sau:

Hình 1.10. Dịch đơn chương trình, đa thao tác dữ liệu

Ví dụ điển hình là hệ thư viện MPI được xây dựng theo cách tạo lập tĩnh

như trên.

 Tạo lập tiến trình động: các tiến trình được tạo lập sau đó chúng có thể

thực hiện trong các tiến trình khác. Các tiến trình có thể được tạo lập

mới hoặc bị huỷ bỏ có điều kiện và một số tiến trình có thể thay đổi

trong quá trình thực hiện. Mô hình cho phép thực hiện tạo lập động là

MPMD (MIMD), trong đó những chương trình khác nhau có thể thực

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

hiện trên những bộ xử lý khác nhau.

 Tất cả các hệ thư viện gửi/nhận thông báo đều có hàm phát sinh các

tiến trình con với cấu trúc tổng quát như sau:

spawn(prog:string, host:int, count:int, id[]:int)

 prog: tên chương trình được nạp xuống như là chương trình con. Kết

quả khi thực hiện thành công sẽ trả lại mảng id là địa chỉ của các tiến

trình được tạo ra để gửi/nhận thông báo. Mảng id có chỉ số từ 1, tiến

trình đầu tiên của chương trình song song có chỉ số là 0.

 host: tên của tiến trình mà ở đó các tiến trình con được tạo ra.

 count: số các đại diện của chương trình được tạo ra.

Các hàm send() và receive():

Việc gửi một thông điệp được thực hiện bằng cách xác định địa chỉ của

một hay tất cả các tiến trình nhận theo một kênh truyền thông. Để lựa chọn

thông điệp, tiến trình nhận có thể dựa vào tiến trình gửi, kênh truyền thông,

hay thẻ bài (tag) của thông điệp, v.v...

Lời gọi send() là không bị chặn, không phải chờ câu trả lời của nơi nhận.

Nhưng việc gọi receive() sẽ bị chặn lại, chỉ có thể tiếp tục khi có một thông

điệp tương ứng đã được gửi đến.

1. Gửi thông điệp cho một tiến trình id:

send(id:int, message:message_type);

send(id:int,tag:int,message:message_type);

2. Gửi thông điệp tới một kênh truyền thông: một thông điệp có thể gửi

cho tất cả các tiến trình trên cùng một kênh mych (my channel).

send(mych:channel, message:message_type);

3. Nhận thông điệp từ một kênh: để nhận một thông điệp đang chờ đợi 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

một kênh thì có thể sử dụng lời gọi hàm sau:

receive(mych:channel,message:message_type);

Nếu thông điệp được ghi thẻ thì tiến trình nhận có thể phân loại thông

điệp trong hộp nhận và chọn thông điệp theo thẻ xác định.

receive(id:int,tag:int,msg:message_type);

Ví dụ: send(destination_id,&x);

trong tiến trình nguồn và gọi:

receive(source_id,&y);

ở tiến trình đích để gửi giá trị dữ liệu x từ tiến trình nguồn (source-id) sang

biến y cho tiến trình đích. Tất nhiên là x, y phải có cùng kiểu (kiểu tương

Tiến trình 1

Tiến trình 2

x . . .send(2, &x); . . .

y . . .receive(1, &y); . . .

thích với nhau) và cùng kích cỡ.

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

Như đã phân tích, việc gửi và nhận thông điệp có thể thực hiện một cách

đồng bộ hoặc dị bộ. Trong trao đổi thông điệp đồng bộ, tiến trình gửi trước

tiên phải gửi đi yêu cầu gửi và nó phải chờ đến khi nhận được câu trả lời sẵn

sàng nhận của tiến trình đích thì mới tiến hành gửi. Ngược lại, khi có một tiến

trình muốn nhận một thông điệp thì nó phải chờ để có một tiến trình khác gửi

cho nó thì sau đó mới có thể thực hiên các công việc tiếp theo. Trong mô hình

dị bộ thì các thông điệp được gửi đi và được đưa vào bộ đệm để sau đó gửi

dần tới cho các tiến trình đích. Để linh hoạt cho việc trao đổi, người ta thườ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

gán cho mỗi thông điệp một thẻ bài (tag) và nó được sử dụng để phân biệt các

thông điệp trong quá trình trao đổi. Ví dụ: để gửi thông điệp x từ tiến trình số

1 tới tiến trình số 2 và gán cho y, ta viết:

send(&x,2,5);

ở tiến trình số 1 và ở tiến trình số 2 gọi:

receive(&y,1,5);

1.4.4. Lập trình trên cụm máy tính

Mô hình gửi/ nhận thông báo nêu trên được sử dụng rất hiệu quả để lập

trình song song theo cụm máy tính. Một môi trường cho hệ thống nhiều máy

tính, nhất là các cụm máy tính đã được phát triển và được sử dụng phổ biến

hiện nay là PVM (Oak Ridge National Laboratories). PVM cung cấp môi

trường phần mềm để gửi/nhận thông báo cho các hệ máy tính thuần nhất và cả

không thuần nhất. PVM có một tập hợp các hàm thư viện được viết bằng

C/C++ hoặc Fortran.

Mỗi chương trình được viết bằng C/C++, được biên dịch để chạy trên

những kiểu máy tính xác định trên mạng. Nếu mạng gồm những máy tính

cùng kiểu thì chương trình chỉ cần dịch 1 lần. Mỗi nút trong mạng(LAN) phải

truy cập đến hệ thống tệp chứa các chương trình đã được dịch để thực hiện.

Tập các máy tính được sử dụng trong mạng phải được định nghĩa theo

các mức ưu tiên để chạy các chương trình. Điều này được thực hiện trên tập

máy ảo song song PVM [1]. PVM là hệ thống cho phép một tuyển tập các

trạm máy tính không thuần nhất và các máy tính kết nối với nhau để xử lý

song song [8]. Cách thực hiện tốt nhất là tạo ra một danh sách tên gọi của các

máy tính và đặt ở hostfile. Tệp này được PVM đọc để thực hiện các chương

trình. Mỗi máy tính có thể chạy một hay nhiều tiến trình. Các chương trình

ứng dụng chạy trong các máy tính thông qua các tiến trình của PVM để trao

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

đổi với nhau trên mạng.

Máy tính trạm

`PVM

Chương trình ứng dụng

Máy tính trạm

PVM

Trao đổi thông điệp trên mạng

PVM

Chương trình ứng dụng

Hình 1.12. Sự trao đổi thông điệp của các máy tính trong hệ PVM

Các chương trình của PVM thường được tổ chức theo mô hình chủ-tớ

(master-slave), trong đó tiến trình chủ được thực hiện trước tiên, sau đó các

tiến trình tớ sẽ được tạo ra trong tiến trình chủ đó. Hàm phát sinh tiến trình

mới trong PVM là: pvm_spawn(). Một tiến trình muốn tham gia vào hệ PVM

thì nó phải ghi danh bằng cách gọi hàm pvm_mytid(). Các tiến trình muốn

được huỷ bỏ thì gọi hàm pvm_exit().

Các chương trình trao đổi thông điệp với nhau thông qua các hàm

pvm_send() và pvm_recv(). Tất cả các thủ tục gửi đều không bị chặn (dị bộ)

còn các thủ tục nhận thì hoặc bị chặn (được đồng bộ) hoặc không bị chặn. Các

thao tác chính của việc gửi và nhận dữ liệu được thực hiện ở các bộ đệm

buffer.

Nếu dữ liệu được gửi đi là một danh sách các mục có cùng kiểu thì trong

PVM sử dụng pvm_psend() và pvm_precv(). Hình 1.13 mô tả hoạt động của

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

hai tiến trình trao đổi một mảng dữ liệu với nhau.

Tiến trình 1

send buffer

Tiến trình 2

Chờ thông điệp

Tiếp tục xử lý

. . . pvm_psend(); . . .

. . . pvm_precv(); . . .

Hình 1.13. Gọi hàm pvm_psend() và pvm_precv()

Khi dữ liệu gửi đi là phức tạp, gồm nhiều kiểu khác nhau thì chúng

phải được đóng gói lại (pack) để gửi đến buffer, sau đó tiến trình nhận lại mở

gói (unpack) để nhận về dữ liệu tương ứng. Đó là các hàm:

pvm_pkint() và pvm_upkint(): cho dữ liệu kiểu int

pvm_pkfloat() và pvm_upkfloat(): cho dữ liệu kiểu float

pvm_pkstr() và pvm_upkstr(): cho dữ liệu kiểu string, v.v.

Lưu ý: thứ tự mở gói để lấy dữ liệu ra phải đúng theo thứ tự mà chúng

được đóng gói ở tiến trình gửi. Bộ đệm buffer để gửi dữ liệu là mặc định và

nó phải được khởi tạo ở tiến trình gửi bằng lệnh pvm_inistend().

Tương tự, các lệnh khác về trao đổi thông điệp theo nhóm 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

pvm_bcast(), pvm_scatter(), pvm_gather(), pvm_reduce(), v.v...

Chƣơng 2

Trong chương I chúng ta đã nghiên cứu lý thuyết xử lý song song và xử

CLUSTER VÀ TÍNH TOÁN PHÂN TÁN BẰNG CLUSTER

lý phân tán, trong chương này chúng ta sẽ tìm hiểu một mô hình hiện thực hóa

các kiến trúc xử lý song song - Computer Server Cluster. Cụ thể chúng ta sẽ

tìm hiểu cách thức hoạt động của một Cluster, các bước xây dựng một Cluster

cũng như cách lập trình với thư viện xử lý song song MPI trên Cluster.

2.1. Mô hình chung của hệ thống Cluster

2.1.1. Mô hình

Server Cluster là một mô hình được đưa ra nhằm đáp ứng các nhu cầu

ngày càng gia tăng trong việc truy xuất các ứng dụng có tính chất quan trọng

như trí tuệ tính toán, thương mại điện tử, database … Các ứng dụng này phải

có khả năng chịu được lỗi cao, luôn đáp ứng được tính sẵn sàng và khả năng

có thể mở rộng hệ thống khi cần thiết. Các khả năng của Server Cluster giúp

cho hệ thống có thể tiếp tục hoạt động và cung cấp dịch vụ luôn sẵn sàng

ngay cả khi hệ thống có thể xảy ra lỗi như hỏng ổ đĩa hay server bị down.

Mô hình Server Cluster bao gồm nhiều server riêng lẻ được liên kết và

hoạt động cùng với nhau trong một hệ thống. Các Server này giao tiếp với

nhau để trao đổi thông tin lẫn nhau và giao tiếp với bên ngoài để thực hiện các

yêu cầu. Khi có lỗi xảy ra, các service trong Cluster hoạt động tương tác với

nhau để duy trì tính ổn định và tính sẵn sàng cao cho Cluster.

Cluster được tổ chức thành các nhóm gọi là các farm hay pack. Trong

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

hầu hết các trường hợp, các dịch vụ ở tầng trước và giữa được tổ chức thành

các farm sử dụng các clone, trong khi đó các dịch vụ tầng sau (back-end

services) được tổ chức thành các pack.

Cluster Farm là một nhóm các máy chủ chạy các dịch vụ giống nhau,

nhưng không dùng chung cơ sở dữ liệu. Được gọi là farm (trang trại) bởi vì

chúng xử lý bất cứ yêu cầu nào gửi đến cho chúng bằng các bản sao cơ sở dữ

liệu (tài nguyên) giống hệt nhau được lưu giữ cục bộ, chứ không dùng chung

một bản cơ sở dữ liệu. Cũng bởi tính chất này nên các máy chủ thành viên của

farm làm việc độc lập và chúng được gọi là clone (clone là máy tính được

thiết kế để mô phỏng chức năng của máy tính khác).

Cluster Pack là một nhóm các máy chủ hoạt động cùng với nhau và chia

sẻ với nhau các phần của cơ sở dữ liệu. Được gọi là pack (khối) vì sự hoạt

động của các máy chủ thành viên của pack có liên hệ chặt chẽ với nhau và

chúng làm việc theo một phương thức thống nhất để quản lý và duy trì các

dịch vụ.

2.1.2. Chế độ hoạt động của Cluster

Mỗi máy chủ trong Cluster được gọi là một nút (Cluster node), và có thể

được thiết lập ở chế độ chủ động (active) hay thụ động (passive). Khi một nút

ở chế độ chủ động, nó sẽ chủ động xử lý các yêu cầu. Khi một nút là thụ

động, nó sẽ nằm ở chế độ dự phòng nóng (stanby) chờ để sẵn sàng thay thế

cho một nút khác nếu bị hỏng. Nguyên lý hoạt động của Cluster có thể biểu

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

diễn như hình:

Hình 2.1. Nguyên lý hoạt động của một Cluster

Trong một Cluster có nhiều nút có thể kết hợp cả nút chủ động và nút

thụ động. Trong những mô hình loại này việc quyết định một nút được cấu

hình là chủ động hay thụ động rất quan trọng. Để hiểu lý do tại sao, hãy xem

xét các tình huống sau:

- Nếu một nút chủ động bị sự cố và có một nút thụ động đang sẵn sàng,

các ứng dụng và dịch vụ đang chạy trên nút hỏng có thể lập tức được chuyển

sang nút thụ động. Vì máy chủ đóng vai trò nút thụ động hiện tại chưa chạy

ứng dụng hay dịch vụ gì cả nên nó có thể gánh toàn bộ công việc của máy chủ

hỏng mà không ảnh hưởng gì đến các ứng dụng và dịch vụ cung cấp cho

người dùng cuối.

- Nếu tất cả các máy chủ trong Cluster là chủ động và có một nút bị sự

cố, các ứng dụng và dịch vụ đang chạy trên máy chủ hỏng sẽ phải chuyển

sang một máy chủ khác cũng đóng vai trò nút chủ động. Vì là nút chủ động

nên bình thường máy chủ này cũng phải đảm nhận một số ứng dụng hay dịch

vụ gì đó, khi có sự cố xảy ra thì nó sẽ phải gánh thêm công việc của máy chủ

hỏng. Do vậy để đảm bảo hệ thống hoạt động bình thường kể cả khi có sự cố

thì máy chủ trong Cluster cần phải có cấu hình dư ra đủ để có thể gánh thê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

khối lượng công việc của máy chủ khác khi cần. Trong cấu trúc Cluster mà

mỗi nút chủ động được dự phòng bởi một nút thụ động, các máy chủ cần có

cấu hình sao cho với khối lượng công việc trung bình chúng sử dụng hết

khoảng 50% CPU và dung lượng bộ nhớ. Trong cấu trúc Cluster mà số nút

chủ động nhiều hơn số nút bị động, các máy chủ cần có cấu hình tài nguyên

CPU và bộ nhớ mạnh hơn nữa để có thể xử lý được khối lượng công việc cần

thiết khi một nút nào đó bị hỏng.

Các nút trong một Cluster thường là một bộ phận của cùng một vùng

(domain) và có thể được cấu hình là máy điều khiển vùng (domain

controllers) hay máy chủ thành viên. Lý tưởng nhất là mỗi Cluster nhiều nút

có ít nhất hai nút làm máy điều khiển vùng và đảm nhiệm việc failover đối

với những dịch vụ vùng thiết yếu. Nếu không như vậy thì khả năng sẵn sàng

của các tài nguyên trên Cluster sẽ bị phụ thuộc vào khả năng sẵn sàng của các

máy điều khiển trong domain.

2.1.3. Một số ứng dụng trong Cluster

- Ứng dụng khoa học: Một ví dụ khá nổi bật về ứng dụng Cluster là công

ty Compagnie Générale de Géophysique (CGG) tại Pháp. CGG thực hiện việc

thăm dò địa chất và cung cấp các hình ảnh 3 chiều dưới lòng đất để giúp các

công ty khai thác dầu khí xác định trữ lượng các mỏ dầu. Giải pháp Cluster

của CGG bao gồm 512 máy chủ IBM xSeries 330 hai CPU Pentium III 1GHz

tại văn phòng ở Luân-đôn của công ty và 128 máy chủ như vậy ở Pari. Các

máy chủ chạy RedHat Linux và hai cụm Cluster được nối mạng với nhau, cho

phép CGG giải quyết các bài toán ở cả hai nơi. Cluster Linux của CGG có

khả năng tính toán 1,25 teraflop và đã giúp công ty tiết kiệm tới 50% chi phí

máy chủ.

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

- Ứng dụng Internet: Các ISP lớn và các công ty thương mại điện tử với

cơ sở dữ liệu lớn cần tới hệ thống máy chủ với tính sẵn sàng cao, khả năng

cân bằng tải và nâng cấp dễ dàng.

- Xử lý đồ hoạ ba chiều và tạo hình ảnh chuyển động: Trường hợp của

nhóm tạo hiệu ứng đặc biệt cho phim Titanic nêu trên là một ví dụ.

Có thể phân loại Cluster theo chức năng như sau:

- Cluster xử lý phân tán: Các tác vụ (các đoạn code nhỏ) được thực hiện

trên nhiều máy nhỏ thay vì tập trung trong một máy siêu tính. Loại Cluster

này rất thích hợp cho các phân tích khoa học hay tài chính. Cluster xử lý lỗi

(Fail-over): Các Cluster được dùng để nâng độ sẵn sàng và khả năng phục vụ

của các mạng dịch vụ. Khi một ứng dụng hay máy chủ ngừng hoạt động, các

dịch vụ của nó được chuyển sang máy khác. Định danh của máy ngừng hoạt

động cũng được chuyển sang. Các failover Cluster được dùng làm máy chủ cơ

sở dữ liệu, mail server hay file server.

- Cluster xử lý lỗi (Fail-over): Các cluster được dùng để nâng độ sẵn

sàng và khả năng phục vụ của các mạng dịch vụ.

- Cluster cân bằng tải có độ sẵn sàng cao: Một ứng dụng nhất định có thể

chạy trên tất cả các máy tính và một máy tính trong nhóm có thể chứa nhiều

ứng dụng. Bên ngoài chỉ giao tiếp với Cluster, mỗi máy tính trong nhóm là ẩn

với người dùng. Loại này không yêu cầu chỉnh sửa ứng dụng, làm việc tốt

nhất với các ứng dụng không cần lưu trạng thái và có thể chạy đồng thời.

2.2. Các ƣu điểm của hệ thống Cluster

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

 Cung cấp tính sẵn sàng cao:

o Hệ thống Server Cluster cung cấp tính luôn sẵng sàng cho các ứng

dụng và các service ngay cả khi các thành phần hardware hay

software bị lỗi.

o Khi một server trong Cluster bị fail, quyền sở hữu tài nguyên của nó

như là các ổ đĩa và IP address tự động chuyển tới một server khác

còn hoạt động.

 Cung cấp khả năng dễ mở rộng:

o Khi các ứng dụng trong Cluster sử dụng tài nguyên hệ thống vượt

quá khả năng của nó, ta có thể dễ dàng add thêm node vào Cluster

để đáp ứng nhu cầu truy cập hay dễ dàng thêm vào nhiều bộ xử lý (

8 CPU cho Windows Server 2003 Enterprise Edition và 32 CPU cho

Windows Server Datacenter Edition) hoặc thêm bộ nhớ RAM (8GB

cho Windows Server 2003 Enterprise Edition và 64GB cho

Datacenter Edititon).

 Cung cấp sự dễ dàng trong quản lý:

o Ta có thể dùng Cluster Administrator tools để quản lý một Cluster

như là một hệ thống đơn và quản lý một ứng dụng khi chúng chạy

trên một server đơn.

o Có thể di chuyển các ứng dụng giữa các server khác nhau bên trong

một Cluster.

o Có thể chuyển đổi lượng công việc giữa các server hay đặt server ở

trạng thái không hoạt động cho kế hoạch bảo trì.

o Có thể giám sát trạng thái của Cluster, tất cả các node và tài nguyê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

từ bất kỳ nơi nào trong mạng.

2.3. Các thành phần của Cluster Service

Cluster service chạy trên mỗi node trong server Cluster và điều khiển

mọi hoạt động của server Cluster. Cluster service bao gồm nhiều thành phần

software làm việc cùng với nhau. Các thành phần này thực hiện việc theo dõi,

duy trì tính ổn định và vận chuyển các resource từ một node qua một node

khác:

 Resource DLLs: Mỗi ứng dụng chịu trách nhiệm theo dõi và điều

khiển ứng dụng đó. Ví dụ: Resource DLL sao lưu và phục hồi các

thuộc tính của ứng dụng trong Cluster database, mang resource online,

offline và kiểm tra trạng thái của resource đó. Khi cần thiết phải thực

hiện failover, Resource DLL làm việc cùng với Resource Monitor và

Failover Manager để đảm bảo quá trình failover được thực hiện dễ

dàng.

 Checkpoint Manage: Để đảm bảo cho việc Cluster service có thể phục

hồi từ một resource bị lỗi, Checkpoint Manager kiểm tra các khóa

registry khi một resource được mang online và ghi dữ liệu checkpoint

lên quorum resource khi resource này offline. Một vài ứng dụng chứa

thông tin cấu hình tại cục bộ thay cho việc chứa thông tin trong cơ sở

dữ liệu cấu hình Cluster. Nếu một ứng dụng yêu cầu chứa đựng cục bộ

thông tin có thể failover, Checkpoint Manager cung cấp cho yêu cầu

này bằng cách duy trì một bản sao của thông tin cục bộ hiện hành này

trên Quorum resource. Đối với các ứng dụng chứa thông tin cấu hình

trong registry trên server, Checkpoint Manager theo dõi dữ liệu này khi

ứng dụng đang online. Khi có sự thay đổi xảy ra, Checkpoint Manager

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

cập nhật quorum resource với dữ liệu cấu hình hiện hành.

 Database Manager: Chạy trên mỗi node và duy trì một bản sao lưu cục

bộ của cơ sở dữ liệu cấu hình Cluster - chứa những thông tin về những

thực thể vật lý và logic trong một Cluster. Những thực thể này bao gồm

bản thân Cluster, các node thành viên, các resource group, các loại

resource và những mô tả của các loại resource đặc biệt như là các ổ đĩa

và địa chỉ IP. Database Manager dùng Global Update Manager cho việc

cập nhật lẫn nhau (replicate) tất cả những thay đổi tới các node khác

trong Cluster. Theo cách này, những thông tin cấu hình được duy trì

qua Cluster nay cả khi một node bị hỏng và khi Administrator thay đổi

cấu hình Cluster trước khi node đó quay trở lại phục vụ. Database

Manager cũng cung cấp một interface chứa những thay đổi trong cơ sở

dữ liệu cấu hình Cluster thông qua các thành phần Cluster service khác

như là Failover Manager và Node Manager. Interface này dùng để tạo

ra những thay đổi tương tự như interface dùng để tạo ra những thay đổi

tới registry qua Windows Programming Interface (API). Những thay

đổi khác này được Database Manager tiếp nhận để cập nhật cho các

node khác trong Cluster qua Global Update Manager.

 Event Log Replication Manager: Là một phần của Cluster service làm

việc cùng với Event Log Service để sao chép các event log tới tất cả

các node trong Cluster. Các sự kiện này được đánh dấu để cho thấy

node nào mà sự kiện xảy ra trên đó. Các sự kiện được ghi lại trên một

node được sắp xếp, củng cố và gửi qua Event Log Replication Manager

để broadcast tới các node đang hoạt động khác. Nếu một vài sự kiện

được ghi lại trong một khoảng thời gian, mỗi sự kiện có thể broadcast

một cách riêng lẻ, nhưng nếu nhiều sự kiện được ghi lại trong mộ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

khoảng thời gian ngắn, chúng được kết hợp với nhau trước khi

broadcast. Các sự kiện được dán nhãn để cho biết node nào chúng được

xảy ra. Các node khác tiếp nhận các sự kiện và ghi chúng lên local log.

 Failover Manager: Quản lý các resource và các resource group. Nó

chịu trách nhiệm tắt hay khởi động các resource, quản lý các resource

liên quan và chuẩn bị cho một quá trình failover các resource group. Để

thực hiện các hoạt động này, nó tiếp nhận resource và thông tin trạng

thái hệ thống từ các thành phần Cluster trên một node và từ Resource

Monitors. Resource Monitors cung cấp môi trường thực hiện cho

resource DLLs và cung cấp sự giao tiếp giữa resource DLLs và

Failover Manager. Failover Manager xác định node nào trong Cluster

nên sở hữu resource group. Khi cần thiết phải failover một resource

group, Failover Manager trên mỗi node trong Cluster làm việc cùng

nhau để tái chỉ định quyền sở hữu cho resource group đó. Dựa trên cách

mà resource group được cấu hình, Failover Manager có thể cục bộ khởi

động lại resource bị hỏng hay có thể làm cho resource đó offline đối

với các resource liên quan với nó và sau đó chuẩn bị cho một quá trình

failover.

 Global Update Manager: Được dùng bởi các thành phần bên trong

Cluster như là Failover Manager hay Database Manager để mang

những cập nhật thay đổi tới mỗi node trong Cluster. Khi quá trình cập

nhật xảy ra, nó bắt đầu tại một node client và một node khác được bổ

nhiệm theo dõi việc cập nhật để đảm bảo việc cập nhật được xảy ra trên

tất cả các node. Node client yêu cầu node này gửi tới một global lock

để thực hiện cập nhật. Nếu lock này chưa sẵn sàng, nó sẽ chờ. Khi lock

này sẵn sàng node giám sát sẽ gán cho node client và chỉ định cập nhật

tại cục bộ. Nếu node này cập nhật thành công mà quá trình update bị lỗi

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

trên một node khác thì node này sẽ bị loại bỏ khỏi danh sách các node

đang hoạt động và sự cập nhật tiến hành trên các node còn hoạt động

khác. Nếu việc này xảy ra, quorum log sẽ được ghi lại để đảm bảo rằng

node bị lỗi có thể nhận được tất cả các thông tin cấu hình cần thiết khi

nó quay trở lại hoạt động.

 Log Manager: Cùng với Checkpoint Manager tương tác với nhau đảm

bảo rằng recover log trên quorum resource chứa đựng dữ liệu cấu hình

mới nhất và các checkpoint thay đổi. Nếu một hay nhiều node trong

Cluster bị hỏng, các node còn hoạt động khác vẫn có thể thực hiện thay

đổi cấu hình. Khi những node này bị hỏng, Database Manager sử dụng

Log Manager để ghi lại sự thay đổi cấu hình lên Quorum resource. Khi

các node bị lỗi quay trở lại phục vụ, chúng đọc vị trí của quorum

resource trong local Cluster. Các cơ chế được xây dựng bên trong sẽ dò

tìm trong cơ sở dữ liệu cũ những quorum resource nào không đúng. Sau

đó Database Manager sẽ yêu cầu Log Manager cập nhật bản sao cục bộ

của Cluster sử dụng file checkpoint trong Quorum resource và sau đó

đối chiếu với file log trong Quorum disk. Kết quả là hoàn thành việc

cập nhật Cluster.

 Membership Manager: Chịu trách nhiệm duy trì một một cái nhìn nhất

quán về các node trong Cluster hiện đang hoạt động hay bị hỏng tại

một thời điểm nhất định. Trọng tâm của thành phần này là thuật toán

regroup được yêu cầu thực hiện bất cứ khi nào có dấu hiệu của một hay

nhiều node bị lỗi.

 Node Manager: Chạy trên mỗi node và duy trì một danh sách cục bộ

các node, các network, các network interface trong Cluster. Qua sự giao

tiếp giữa các node, Node Manager đảm bảo cho tất cả các node có cùng

một danh sách các node đang hoạt động. Node Manager dùng nhữ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

thông tin trong cơ sở dữ liệu cấu hình Cluster để xác định các node nào

được thêm vào hay bị loại bỏ khỏi Cluster. Node Manager trên mỗi

node cũng theo dõi các node khác để tìm ra node bị lỗi. Để thực hiện

việc theo dõi, nó gửi và nhận những message gọi là các heartbeat tới

mỗi node trong Cluster. Nếu một node có một sự giao tiếp bị lỗi với

một node khác, nó gửi broadcast một message tới các node khác sao

cho tất cả các node nhận message này để xác nhận lại danh sách các

node đang hoạt động trong Cluster. Quá trình này gọi là một regroup

event. Node Manager cũng tham gia vào quá trình một node tham gia

vào Cluster. Tại thời điểm một node được thêm vào Cluster, Node

Manager trên node đó thành lập một quá trình giao tiếp với các Node

Manager trên các node khác để thực hiện quá trình chứng thực.

 Resource Monitor: Cung cấp một interface giao tiếp giữa resource

DLLs và Cluster service. Khi Cluster cần lấy dữ liệu từ một resource,

Resource Monitor tiếp nhận yêu cầu và đẩy yêu cầu đó tới resource

DLL thích hợp. Ngược lại, khi một resource DLL cần báo cáo trạng

thái của nó hoặc thông báo cho Cluster service một sự kiện, resource

đẩy thông tin này từ resource tới Cluster service.

 Backup/Restore Manager: Cluster service đưa ra một API dùng để

backup cơ sở dữ liệu Cluster, BackupClusterDatabase. Backup Cluster

Database trước tiên tương tác với Failover Manager, sau đó đẩy yêu

cầu tới node sở hữu quorum resource. Database Manager trên node đó

sẽ được yêu cầu và sau đó tạo một bản backup cho quorum log file và

các file checkpoint.

Cluster service cũng đưa ra một API khác, Restore Cluster Database để

restore cơ sở dữ liệu Cluster từ một backup path. API này có thể chỉ được yêu

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

cầu tại cục bộ từ một trong các node của Cluster. Khi API được yêu cầu,

trước tiên nó tắt Cluster service, restore cơ sở dử liệu Cluster từ bản backup,

tạo một giá trị registry chứa backup path và sau đó khởi động lại Cluster

service. Cluster service khi khởi động sẽ dò tìm yêu cầu restore và tiến hành

restore cơ sở dữ liệu Cluster từ backup path tới Quorum resource.

2.4. Nguyên tắc hoạt động của Server Cluster

Khi một node hay một application trong Cluster bị fail, Server Cluster có

thể phản ứng bằng cách khởi động lại application bị lỗi hay phân tán công

việc từ node bị fail tới các node khác còn hoạt động trong Cluster đó.

Cluster service kiểm tra tình trạng không hoạt động của các resource

riêng biệt hay một node, và tự động di chuyển hay khởi động lại các ứng

dụng, dữ liệu và file resource tới một node còn hoạt động trong Cluster. Quá

trình này cho phép các resource như là database, file share và application duy

trì tính sẵn sàng cao cho các ứng dụng của user và client.

 Detect Node Failure: Một cách định kỳ, mỗi node trao đổi các gói

message với những node khác trong Cluster sử dụng private Cluster

network. Những message này được gọi là Heartbeat. Sự trao đổi

Heartbeat cho phép mỗi node kiểm tra tính sẵng sàng của các node

khác và các ứng dụng của chúng. Nếu một server bị fail trong việc phản

hồi 1 Heartbeat, các server còn hoạt động bắt đầu một quá trình

Failover để đàm phán quyền sở hữu đối với các tài nguyên và ứng dụng

của node bị fail. Việc đàm phán này sử dụng Challenge và Defense

protocol.

Việc bị fail trong quá trình phản hồi Heartbeat có thể xảy ra trong nhiều

sự kiện như là computer failure, network interface failure, network

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

failure, hay trong lúc hoạt động cao bất thường nào đó. Thông thường,

khi tất cả các node giao tiếp với nhau, Configuration Database Manager

gửi Global Configuration Database update tới mỗi node. Tuy nhiên, khi

fail trong quá trình trao đổi heartbeat xảy ra, Log Manager cũng lưu lại

cấu hình database thay đổi tới Quorum Resource. Nó đảm bảo các node

còn hoạt động có thể truy cập thông tin cấu hình Cluster mới nhất và dữ

liệu registry cục bộ trên node trong quá trình phục hồi.

 Detect Resource Failure: Failover Manager và Resource Monitors làm

việc cùng với nhau để dò tìm và khôi phục resource bị fail. Resource

Monitors theo dõi trạng thái của resource bằng cách kiểm tra định kỳ

các resource sử dụng Resource DLLs. Việc kiểm tra vòng gồm hai

bước, một query LookAlive lướt qua và một query lâu hơn, cuối cùng -

IsAlive. Khi Resource Monitor dò tìm một resource bị fail, nó thông

báo cho Failover Manager và tiếp tục giám sát resource này.

Failover Manager duy trì trạng thái của các resource và resource group.

Nó cũng chịu trách nhiệm thực hiện việc phục hồi khi một resource bị fail và

sẽ yêu cầu Resource Monitor phản hồi tới user tình trạng hoạt động hay

không hoạt động của resource.

Sau khi resource bị fail được tìm thấy, Failover Manager có thể thực

hiện việc phục hồi bằng cách khởi động lại một resource và các resource hay

di chuyển toàn bộ resource group tới một node khác. Công việc phục hồi xác

định đã được thực hiện bởi resource và resource group properties và node

availability.

Trong quá trình failover, một resource group được coi như là một

failover unit, để đảm bảo resource được phục hồi đúng. Khi một resource

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

được phục hồi từ trạng thái fail, Resource Monitor thông báo tới Failover

Manager để tự động thực hiện quá trình failback các resource group dựa trên

cấu hình của resource group failback properties.

 Heartbeat: Là một UDP packet chuyển đổi giữa các node mỗi 1.2 giây

một lần để xác định mỗi node trong Cluster vẫn hoạt động. Nếu một

node thiếu hụt liên tiếp 5 heartbeat, node đó sẽ chuẩn bị một quá trình

regroup event để đảm bảo rằng tất cả các node đi tới một sự nhất quán

danh sách các node còn đang hoạt động.Server Cluster network có thể

là private (chỉ có sự giao tiếp giữa các node với nhau), public (giao tiếp

giữa client với node), hay mixed (cả sự giao tiếp giữa các node và sự

giao tiếp giữa client với node). Heartbeat được giao tiếp qua tất cả các

loại network, tuy nhiên việc theo dõi heartbeat và cách mà Cluster thể

hiện các heartbeat bị lỗi dựa trên các kiểu network sau:

- Trên private hay mixed network, cả hai đều có sự giao tiếp giữa

các node, heartbeat được theo dõi để xác định node có hoạt động trong

Cluster hay không.

- Trên public network, chỉ có sự giao tiếp giữa client với node,

heartbeat được theo dõi chỉ để xác định network adapter của node có

hoạt động hay không.

 Regroup event: Nếu một node thiếu hụt liên tiếp 5 heartbeat, một quá

trình regroup event được xảy ra. Nếu node vẫn duy trì tính trạng không

thể phản hồi, node đó sẽ được loại bỏ khỏi danh sách các node hoạt

động. Nếu node không phản hổi này đang sở hữu một quorum resource,

các node còn lại cũng bắt đầu một quá trình đàm phán quorum. Sau đó,

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

quá trình failover được bắt đầu.

 Quá trình đàm phán quorum: Quá trình đàm phán quorum xảy ra khi

một node đang sở hữu một quorum resource bị lỗi hay không hoạt

động, và các node còn lại sẽ xác định node nào sẽ giữ quyền sở hữu

quorum resource. Mục đích của quá trình đàm phán quorum là tại một

thời điểm đảm bảo rằng chỉ một node duy nhất được sở hữu quorum

resource. Việc chỉ cho một node sở hữu quorum resource là rất quan

trọng bởi vì nếu tất cả các giao tiếp giữa 2 hay nhiều node bị lỗi, nó có

khả năng chia Cluster thành 2 hay nhiều phần riêng biệt để giữ cho nó

vần tiếp tục hoạt động (split brain). Server Cluster ngăn ngừa nó bằng

cách chỉ cho phép duy nhất một Cluster tách ra này có chứa node đang

sở hữu quorum resource tiếp tục hoạt động như một Cluster. Bất kỳ

node nào không thể giao tiếp với node đang sở hữu quorum resource,

thì node đó sẽ không còn là node thành viên trong Cluster.

 Cách Cluster giữ cho các resource group luôn sẵn sàng: Cluster giữ

cho các resource group luôn sẵn sàng bằng cách theo dõi trạng thái của

các resource, mang các resource online, và tiến hành failover.

 Theo dõi trạng thái các resource: Resource Monitor đưa ra 2 cách theo

dõi trạng thái các resource trên node mà nó giám sát: Look Alive

(resource xuất hiện là online) và IsAlive (kiểm tra chi tiết trạng thái

online và hoạt động của resource là đúng chức năng).

 Cách Failover xảy ra: Quá trình failover xảy ra khi một group hay một

node đang sở hữu resource bị lỗi. Một resource bị lỗi có thể là lý do cho

một group fail nếu ta cấu hình Affect the group cho resource đó.

Failover có hai dạng: Resource failure hay Group failure và Node

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

failure hay mất sự giao tiếp giữa các node.

o Resource failure và Group failure:Khi một resource bị hỏng quá

 Resource Monitor dò tìm lỗi qua Looks Alive hay Is Alive

trình sau sẽ xảy ra:

hoặc qua một sự kiện được ghi bởi resource đó. Resource

Monitor gọi điểm vào Is Alive của resource DLL để xác

 Nếu Is Alive bị lỗi, trạng thái resource chuyển thành fail

 Nếu ta cấu hình cho resource khởi động lại khi bị lỗi,

định resource đó bị hỏng

Failover Manager cố gắn khởi động lại resource để mang

nó online trở lại. Nếu sự cố gắng mang resource online

không đạt được hay vượt qua ngưỡng hay thời gian cho

 Thông qua Resource Monitor, Failover Manager gọi

phép khởi động lại, Resource Monitor stop resource này.

 Nếu resource này được cấu hình là Affect the group, quá

Terminal entry point của resource DLL

trình làm việc được tiếp tục, ngược lại, nó sẽ kết thúc mà

không có hoạt động nào khác. Khi cấu hình là Affect the

group, Failover Manager trên các node trong Cluster làm

việc cùng với nhau để tái chỉ định quyền sở hữu cho group

 Trên node mà resource bị hỏng, Failover Manager kết thúc

đó.

 Failover Manager trên node mà resource bị hỏng thông

resource đó và các resource liên quan với nó

báo cho Failover Manager trên node sẽ sở hữu resoure đó

và cũng thông báo với Failover Manager trên tất cả các

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

node khác cho sự thay đổi này

 Nếu bất kỳ resource nào được cấu hình lưu thông tin cấu

hình trên cục bộ registry, Checkpoint Manager sẽ restore

 Node mà Failover Manager sẽ chuyển resource tới là duy

bản sao registry cho resource đó từ quorum resource

 Node mới sở hữu group sẽ điều khiển các resource của

nhất, sử dụng danh sách phụ thuộc để xác định thứ tự đúng

o Node failure và mất sự giao tiếp giữa các node: Failover xảy ra

group đó thông qua Resource Monitor tương ứng

khi một node bị hỏng khác với Failover xảy ra khi một resource

bị hỏng. Trong Clustering, một node được coi là bị hỏng nếu nó

mất sự giao tiếp với các node khác. Nếu một node mất liên tiếp 5

heartbeat, nó được coi là bị hỏng và một quá trình regroup event

được xảy ra. Sau khi một node bị hỏng, các node còn lại tiến

hành đàm phán cho việc sở hữu các resource group. Failover

Manager trên các node còn sử dụng được xác định quyền sở hữu

 Các node mà ta chỉ định có khả năng sở hữu các resouce

các resource group dựa trên:

 Thứ tự được chỉ định trong danh sách các node ưu tiên

group đó.

 Cách Failback xảy ra: Failback là quá trình Cluster service chuyển các

resource group trả về node thích hợp hơn sau khi node này online trở

lại. Node mà một group được trả về chuẩn bị một quá trình failback.

Failover Manager trên node đó tương tác với Failover Manager trên

node đang sở hữu group và tiến hành đàm phán sau đó chuyển quyền

sở hữu resource group trở về node thích hợp hơ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

2.5. Cách cài đặt và cấu hình Cluster trên Linux

2.5.1. Khái niệm LVS

LVS (Linux Virtual Server) là một server ảo được xây dựng dựa trên

một Cluster của các server thật. Với người sử dụng thì họ chỉ nhìn thấy một

User

Internet

Load Balancing

LAN/WAN

Real Sever 1

Real Sever 2

Real Sever n

server ảo đầy quyền năng, không hề biết đến kiến trúc bên trong.

Hình 2.2. Linux Virtual Server

Như mô tả của hình trên, khi sử dụng Virtual Server, người sử dụng

bên ngoài Internet chỉ nhìn thấy một địa chỉ IP, đó là địa chỉ IP của Load

balancer. Load balancer là máy tính duy nhất liên lạc, nhận request từ các

máy ngoài Internet. Sau đó, load balancer sẽ có cơ chế tự động phân chia

request đến các real server bên trong. Load balancer và các real server có thể

liên lạc qua một đường truyền mạng LAN tốc độ cao, hoặc cũng có thể liên

lạc qua mạng WAN. Để đảm bảo hệ thống hoạt động trong suốt với người sử

dụng cần đảm bảo các vấn đề sau:

 Khi load balancer bị lỗi, phải có cơ chế back up tốt để hoạt động của hệ

thống vẫn tiếp diễn.

 LVS phải có cơ chế để tự động cập nhật khi có một real server tham gia

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

hoặc tách khỏi hệ thống.

 Khi một real server bị lỗi, hệ thống phải phát hiện được để đảm bảo

hoạt động không bị gián đoạn.

 Mặt khác để hệ thống có thể hoạt động hiệu quả cần giải quyết vấn đề

phân chia request hợp lí, tránh tình trạng một real server xử lí quá tải,

trong khi các real server khác lại ở tình trạng “idle”.

2.5.2. Các mô hình LVS

Để triển khai ý tưởng của LVS, người ta có 3 mô hình chính:

 Virtual server via NAT.

 Virtual server via IP Tunneling.

 Virtual server via Direct Routing.

Mỗi mô hình có một số ưu, khuyết điểm khác nhau. Tùy theo cách triển

khai, tùy theo thực trạng và yêu cầu của hệ thống mà ta có thể lựa chọn một

mô hình thích hợp.

2.5.3. Mô hình Virtual Server via NAT

Với mô hình NAT, dòng chuyển dữ liệu được thực hiện như sau:

 Client gởi request cho load balancer.

 Load balancer phân chia request đến cho những real server.

 Real server gởi reponse cho load balancer.

 Load balancer chuyển reponse cho client.

Load balancer có 2 địa chỉ: một để liên lạc với client, một để liên lạc với

các real server bên trong. Địa chỉ để liên lạc với real server cũng như địa chỉ

của các real server có thể là địa chỉ private. Địa chỉ mà load balancer 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

để liên lạc với client là địa chỉ public (địa chỉ thật).

Hình 2.3. Mô hình Virtual Server via NAT

Điểm bất lợi lớn nhất của mô hình NAT là Load balancer có thể sẽ trở

thành một “bottle neck” bởi vì tất cả request và reponse đều sẽ phải đi qua

điểm này. Mô hình NAT chỉ có thể phục vụ khoảng 10-20 real server.Để khắc

phục nhược điểm của mô hình NAT, ta có thể sử dụng mô hình Tunnel hoặc

mô hình Direct Routing tùy theo yêu cầu triển khai cụ thể.

2.5.4. Mô hình Virtual Server via Tunneling

Với mô hình Tunneling, dòng dữ liệu lưu chuyển như sau:

 Client gởi request cho Load balancer.

 Load balancer phân chia request cho các real server.

 Các real server sau khi được phân chia sẽ tự động liên lạc với các client

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

bằng con đường riêng, không thông qua Load balancer.

Mô hình Tunneling sẽ giảm được tình trạng “bottle neck” cho load

balance. Load balancer chỉ đảm nhận nhiệm vụ lập lịch, phân chia request đến

các real server. Với mô hình này, một load balancer có thể phục vụ cho

khoảng 100 real server.

Hình 2.4. Mô hình Virtual Server via Tunneling

2.5.5. Mô hình Virtual Server via Direct Routing

Giống mô hình Tunneling, mô hình Direct Routing chỉ nhận request và

lập lịch xử lí. Các real server sẽ gởi reponse cho client theo một con đường

riêng, không thông qua load balancer. Mô hình Direct Routing đòi hỏi load

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

balancer và real server phải thuộc cùng một segment vật lý.

Hình 2.5. Mô hình Virtual Server via Direct Routing

2.5.6. Cách triển khai các mô hình

Trước hết để Linux hỗ trợ LVS, cần thực hiện những việc sau:

 Cài đặt gói các gói heartbeat.

 Thực hiện các thao tác chặn ARP

 Tùy theo mô hình chọn sử dụng (NAT, Tunneling, Direct Routing), ta

sẽ chọn các cấu hình thích hợp.

2.5.7. Các bước triển khai LVS via Direct Routing

a. Mô hình

Ở đây, giới thiệu một mô hình chuẩn gồm 4 server: Load balancer

Master (Master), Load balancer (Backup), Real1, Real2. Ta test thử với dịch

vụ HTTP. Khi client ở ngoài, gởi request http vào, request sẽ được tiếp nhậ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

bởi Master, sau đó, Master sẽ tiến hành phân chia request cho Real1, và

Real2. Master và Backup sẽ dùng tín hiệu heartbeat để trao đổi với nhau, nếu

Master có sự cố, thì Backup sẽ thay thế vai trò của Master, và Master trở

thành Backup. Khi Master khắc phục xong sự cố, Backup sẽ nhường lại vai

trò cho Master. Master sẽ dùng ldirectord để monitor Real1 và Real2. Nếu

Real1 có sự cố, Master sẽ chỉ chia request cho Real2 và ngược lại. Khi Real1

khắc phục xong sự cố, Master lại tiếp tục chia request cho Real1.

Giả sử hostname của các máy lần lượt là: Master, Backup, Real1, Real2.

 Master: eth0: 192.168.1.2, eth1: 172.16.1.2

 Backup: eth0: 192.168.1.3, eth1: 172.16.1.3

 Real1: 192.168.1.4

 Real2: 192.168.1.5

 VIP: 192.168.1.1 (IP ảo, Client gởi request đến IP này).

 Master & Backup bắt buộc phải có 2 card mạng: eth0 để lắng

(Cần dùng lệnh uname –n để xác định chính xác hostname của các máy).

nghe request từ bên ngoài, và eth1 để nhận tín hiệu heartbeat với nhau.

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

Hình 2.6. Mô hình chuẩn gồm 4 server

Đầu tiên, các bạn làm quen với mô hình chuẩn, gồm đủ các thành phần:

Master, Backup, Real1, Real2. Khi đã hiểu nguyên tắc hoạt động, với các bài

lab sau, mình sẽ hướng dẫn các bạn cách tinh chỉnh để giảm số server, mà vẫn

đảm bảo được ý nghĩ logic của mô hình.

b. Cài đặt

Cài đặt các gói heartbeat trên Master và Backup bằng lệnh:

# yum install heartbeat*

Hoặc cụ thể hơn, có thể cài đặt tất cả các gói rpm cho Master và Backup

theo trình tự sau:

# rpm –ivh heartbeat-pils-1.2.3.cvs.20050927-1.rh.el.um.1.i386.rpm

# rpm –ivh libnet-1.1.2.1-1.rh.el.um.1.i386.rpm

# rpm –ivh perl-Authen-SASL-2.08-1.rh.el.um.1.noarch.rpm

# rpm –ivh perl-Convert-ASN1-0.18-1.rh.el.um.1.noarch.rpm

# rpm –ivh perl-Net-SSLeay-1.25-1.rh.el.um.1.i386.rpm

# rpm –ivh perl-IO-Socket-SSL-0.96-1.rh.el.um.1.noarch.rpm

# rpm –ivh perl-Parse-RecDescent-1.94-1.rh.el.um.1.noarch.rpm

# rpm –ivh perl-Mail-IMAPClient-2.2.9-1.rh.el.um.1.noarch.rpm

# rpm -ivh heartbeat-stonith-1.2.3.cvs.20050927-1.rh.el.um.1.i386.rpm

# rpm –ivh perl-XML-NamespaceSupport-1.08-

1.rh.el.um.1.noarch.rpm

# rpm –ivh perl-XML-SAX-0.12-1.rh.el.um.1.noarch.rpm

# rpm –ivh perl-ldap-0.3202-1.rh.el.um.1.noarch.rpm

# rpm –ivh heartbeat-1.2.3.cvs.20050927-1.rh.el.um.1.i386.rpm

# rpm –ivh heartbeat-ldirectord-1.2.3.cvs.20050927-

1.rh.el.um.1.i386.rpm

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

# rpm –ivh ipvsadm-1.21-1.rh.el.1.um.1.i386.rpm

Cài đặt các gói sau trên Real1 và Real2:

# rpm –ivh arptables-noarp-addr-0.99.2-1.rh.el.um.1.noarch.rpm

# rpm –ivh arptables_jf-0.0.7-0.3E.i386.rpm

Ghi chú: tùy theo cách cài đặt perl kèm theo hệ điều hành ban đầu, các

gói perl trên đây có thể thiếu, hoặc có thể thừa. Có thể bổ sung cho đúng với

cách cài đặt hệ điều hành. RPM download tại: http://www.ultramonkey.org.

c. Các bước cấu hình

 Cấu hình hearbeat để Master và Backup lắng nghe nhau.

 Cấu hình ldirectord để Master monitor Real1 và Real2.

Như đã trình bày, phần cấu hình cho Master sẽ gồm các bước sau:

d. Cấu hình heartbeat

- Phần này cấu hình cho cả Master và Backup.

- Các file cần cấu hình cho dịch vụ heartbeat là: file ha.cf, haresources,

authkeys. - Chép các file này vào thư mục /etc/ha.d.

cp /usr/share/doc/heartbeat-1.2.3.cvs.20050927/ha.cf /etc/ha.d/

cp /usr/share/doc/heartbeat-1.2.3.cvs.20050927/authkeys /etc/ha.d/

cp /usr/share/doc/heartbeat-1.2.3.cvs.20050927/haresources /etc/ha.d

- Sửa các tham số sau trong file ha.cf:

udpport 694 # Port để gởi tín hiệu heartbeat

bcast eth1 # Card mạng để gởi tín hiệu heartbeat

keepalive 2

deadtime 30

initdead 120

node Real1 Real2 ( Sử dụng lệnh uname –n để xác định chính xác tên

server real).

- Sửa các tham số sau trong file authkeys:

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

auth 1

1 sha1 lvsvtdns11

- Chuẩn bị các script để đặt vào file haresources: ldirectord.cf.

- Thêm dòng sau vào file haresources.

Master 192.168.1.1 \

ldirectord::ldirectord.cf \

LVSSyncDaemonSwap::master \

e. Cấu hình ldirectord

Phần này cấu hình cho cả Master và Backup.

ldirectord cần có file ldirectord.cf. File này có nội dung như sau:

checktimeout=3

checkinterval=5

autoreload=yes

logfile=”/var/log/ldirectord.log”

virtual=192.168.1.1:80

real=192.168.1.4:53 gate 5

real=192.168.1.5:53 gate 5

request=”/.testpage”

receive=”test page”

scheduler=rr

service=http

checkcount=3

f. Cấu hình cho Real1, Real2

 Trên Real1 và Real2 cần cấu hình dịch vụ http.

 Tạo một trang web test cho dịch vụ http, đặt trong Document Root.

protocol=tcp

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

echo “test page” >. testpage

 Tạo IP ảo cho các Real1 và Real2:

 Chặn ARP trên IP ảo của các Real1 và Real2:

ifconfig eth0:0 192.168.1.1 netmask 255.255.255.0

/usr/sbin/arptables-noarp-addr 192.168.1.1 start

/etc/init.d/arptables_jf save

/etc/init.d/arptables_jf restart

 Sau khi thực hiện xong các bước cấu hình trên, thực hiện test như sau:

 Trên Master, thực hiện:

g. Test thử cấu hình

 Trên Backup, thực hiện:

# service heartbeat start

 Trên Master, xem kết quả:

# service heartbeat start

# ipvsadm

Nếu hiển thị kết quả bảng phân chia request có IP của Real1,

 Trên Backup, xem kết quả:

Real2 là đúng.

# ipvsadm

Vì backup, lúc này chỉ đang đứng lắng nghe, trên không có bả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

phân chia request.

 Từ Client kết nối dịch vụ http, hoạt động bình thường, dùng lại lệnh

ipvsadm trên Master, sẽ thấy request được phân chia cho Real1 hoặc

Real2.

2.6. Tính toán phân tán bằng Cluster

2.6.1. Lập trình trên môi trường MPI

MPI là một công nghệ lập trình song song rất phổ biến với việc sử dụng

bộ nhớ phân tán. MPI cho phép tạo ra nhiều tiến trình có thể thực hiện song

song. Phiên bản mới nhất là MPI 2.0, để lập trình MPI trên Win32 với ngôn

ngữ C++ chúng ta sử dụng thư viện các hàm của MPI trong MPICH2.

Ta sử dụng một mạng gồm các máy tính vào mục đích tính toán, mỗi

máy hoạt động theo nhịp đồng hồ riêng của mình và chỉ có thể đọc dữ liệu ở

trên máy của mình (distributed memory system & asynchronous operation

mode).

Đối với một mạng như vậy, thì về nguyên tắc, trên mỗi máy ta có thể cho

chạy một trình riêng và dữ liệu mỗi trình xử lý là riêng (MPMD). Các trình

này có thể khác nhau, tức là chúng giải quyết các bài toán khác nhau, hoạt

động độc lập và chỉ đến một lúc nào đó thì chúng mới trao đổi dữ liệu cho

nhau.

Sự việc xảy ra là: nếu thời điểm khởi động các trình trên các máy khác

nhau mà không xác định, thì thời điểm cho việc chúng trao đổi dữ liệu cho

nhau cũng không thể xác định được. Vậy chúng ta vẫn cần phải có một “trọng

tài” để xác định thời điểm bắt đầu hoạt động cho chúng. Với quan niệm này

người ta coi như tất cả chúng chỉ là một trình chung thôi, có nghĩa là:

- Trên mỗi máy tính vẫn chạy một trình, nhưng chúng hoàn toàn giống

nhau.

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

- Tất cả các trình ấy được khởi động để chạy cùng một lúc.

Tuy chỉ sử dụng một chương trình, nhưng các máy tính khác nhau vẫn sẽ

làm những “phần việc” khác nhau, bởi trong trình chung ấy, mỗi “phần việc”

chỉ là những đoạn lệnh riêng và mỗi máy phải tự xác định và thực hiện đoạn

lệnh của mình (thường là thông qua tên máy và process).

Các chương trình, tức là các đoạn lệnh “riêng” ấy, chỉ có thể truy cập

trực tiếp vào bộ nhớ RAM trong máy của mình – SPMD. Nếu ở trong chương

trình chung có một biến được khai báo thì tức là nó sẽ có mặt ở tất cả các máy

tính.

Các máy tính muốn trao đổi dữ liệu với nhau thì phải thông qua các lệnh

gửi – nhận mà MPI cung cấp. Đó là một môi trường đảm nhận nhiệm vụ trao

đổi dữ liệu qua mạng. Mỗi máy tính muốn tham gia vào hệ thống MPI phải

được cài thêm một trình thường trú, gọi là Driver – MPI.

Mục đích của MPI là tạo ra một môi trường gửi – nhận dữ liệu thân

thiện, cho phép chúng ta soạn thảo và thử trình MPI chỉ trên một máy, để sau

đó chạy nó trên một mạng máy tính – có thể có cấu trúc rất phức tạp.

Để làm việc này MPI cho phép mô phỏng một mạng ảo chỉ trên một máy

tính. Mỗi một máy tính ảo như vậy được gợi là một tiến trình. MPI bảo đảm

để về mặt hình thức mỗi tiến trình hoàn toàn tương đương với máy tính tuần

tự, tức là gồm có một vi xử lý trung tâm và RAM. Điểm khác biệt chỉ là

chúng có chung ổ đĩa cứng. RAM của các máy ảo này chiếm giữ các vùng

nhớ khác nhau, chính vì vậy mà các tiến trình không thể trực tiếp trao đổi dữ

liệu cho nhau. Giống như các máy tính độc lập trong mạng, các tiến trình chỉ

có thể trao đổi dữ liệu với nhau thông qua môi trường MPI. Tuy nhiên, không

phải cứ mỗi tiến trình, tức là mỗi máy ảo, thì cần một trình thường trú Driver-

MPI riêng mà trên mỗi máy tính chỉ cần cài một trình thường chú Driver-

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

MPI. Nó sẽ phục vụ tất cả các tiến trình trên máy tính ấy.

Thông thường người ta viết và thử trình trên một máy tính, khi ấy sẽ có

sự phân biệt giữa rõ ràng giữa tiến trình và máy tính. Tuy nhiên khi sử dụng

chương trình ấy trên một mạng nhiều máy tính thì, thường là, trên mỗi máy

tính chỉ chạy có một tiến trình. Chính vì vậy mà sẽ có một sự “chồng chéo”

khi sử dụng từ “tiến trình” và người đọc sẽ phải tự phân biệt được khi nào thì

nó hàm ý là máy tính “ảo” và khi nào thì là máy tính “thật”, hoặc là ngược lại,

khi nào thì máy tính “thật” lại hàm ý là “tiến trình”. Tất cả những điều rắc rối

này xảy ra chỉ là vì chúng ta soạn trình thì trên một máy, mà chạy trình thì

trên một mạng gồm nhiều máy tính và trên mỗi máy tính thật ấy lại có thể có

nhiều tiến trình.

2.6.2. Cài đặt MPICH2

Cài đặt MPICH2 trên Linux

Chúng ta thực hiện cài đặt thư viện MPI trên hệ điều hành Linux như

- Download MPICH2 tại:

http://wwwunix.mcs.anl.gov/mpi/mpich2/

- Giải nén $ tar zxf mpich2-1.0.6.tar.gz

- Dịch và cài đặt

$ cd mpich2-1.0.6.tar.gz

$ mkdir /opt/mpich2

$. /configure --prefix=/opt/mpich2

$ make

$ make install

Chú ý, nếu không có quyền ghi vào thư mục /opt thì phải chuyển qua

dùng account root (hoặc dùng sudo) để cài đặ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

Sau khi cài đặt xong, thêm dòng sau vào file ~/.bashrc:

export PATH=/opt/mpich2/bin/:$PATH

Bây giờ, ta cần phải cấu hình mpd. Nếu muốn cấu hình cho account của

riêng bạn, cần thêm file. mpd.conf vào thư mục nhà. File này chứa một dòng

với nội dung MPD_SECRETWORD= với tùy

chọn của bạn. Ví dụ là "conloncon". ta tạo file như sau:

$ echo "MPD_SECRETWORD=conloncon" > ~/.mpd.conf

Sau đó thiết lập lại quyền truy cập vào file này:

$ chmod 600 ~/.mpd.conf

Muốn chạy các chương trình MPI, trước hết ta phải khởi động tiến trình

mpd:

$ mpd &

Ta chạy mpd như một tiến trình ngầm (background), do đó nếu cần có

thể kiểm tra lại:

$ mpdtrace -l

cheva_49376 (127.0.0.3)

Kết quả trên cho thấy mpd đang chạy trên host cheva (127.0.0.3) và cổng

49376.

Để khởi động tiến trình mpd trên nhiều máy, ta có thể tạo một file

mpd.hosts, lưu địa chỉ của các máy cần chạy mpd vào file này rồi dùng lệnh:

$ mpdboot -n -f mpd.hosts

Cài đặt MPICH2 trên windows

- Download và cài đặt MPICH2 32bit hoặc 64bit tùy theo hệ điều 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

trên máy tính.

- Thêm C:\Program Files\MPICH2\bin vào vị trí MyComputer/

Properties / Advanced System Settings/Advanced/Environment Variables

- Bổ xung các file đường dẫn file sau tới tường lửa của bạn:

C:\Program Files\MPICH2\bin\mpiexec.exe

C:\Program Files\MPICH2\bin\smpd.exe

- Đăng kí tài khoản bằng cách nhập tên và pass tuân theo đường dẫn:

C:\ProgramFiles\MPICH2\bin\wmpiregister

- Lựa chọn Port để mở cổng 8676 tuân theo đường dẫn:

C:\Program Files\MPICH2\bin\wmpiconfig

Cài đặt trên môi trường Visual Studio:

- Khởi động Visual Studio.

- Đi tới Tools/Options/Projects and Solutions/Visual C++ Directories

trong phần Combo Box lựa chọn win 32.

- Trong Combo Box Directories, lựa chọn "Include files" và bổ xung

đường dẫn sau:

C:\Program Files\MPICH2\include (hoặc Program Files (x86) với

windows 64 bit)

- Lựa chọn "Library files" và thêm đường dẫn sau C:\Program

Files\MPICH2\lib\ (hoặc Program Files (x86) với windows 64 bit).

2.6.3. Tính toán trên MPI

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

Các hàm MPI thông dụng:

Tên hàm Ý nghĩa

MPI_Init() Khởi tạo bộ môi trường thực thi

MPI, hàm này phải được gọi trước tất cả

các hàm MPI khác, và chỉ được gọi một

lần. Hàm này có thể được dùng để

truyền tham số dòng lệnh tới tất cả các

tiến trình, cách dùng như sau: MPI_Init

(&argc, &argv).

MPI_Finalize() Dùng để kết thúc môi trường thực

thi MPI. Hàm này phải được gọi cuối

cùng trong tất cả các hàm MPI.

MPI_Comm_size(MPI_CO Xác định số lượng tiến trình tham

gia vào một bộ giao tiếp, thông thường, MM_WORLD, &size)

nó được dùng trong bộ giao tiếp

MPI_COMM_WORLD bộ giao tiếp

được xây dựng sẵn, bao gồm tất cả các

tiến trình tham gia vào chương trình.

MPI_Comm_rank(MPI_CO Xác định thứ tự của tiến trình này

MM_WORLD, &rank) trong bộ giao tiếp. Lúc ban đầu mỗi tiến

trình được gán cho một số thứ tự từ 0 tới

n-1 trong bộ giao tiếp

MPI_COMM_WORLD.

MPI_Finalized(&flag) Kiểm tra xem hàm MPI_Init() đã

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

được gọi hay chưa.

MPI_Barrier() Đồng bộ tất cả các tiến trình trong

hệ thống, khi hàm này được gọi, tất cả

các tiến trình sẽ cùng chờ cho tới khi

tiến trình cuối cùng thực hiện đến bước

này và tất cả cùng thực hiện câu lệnh

tiếp theo vào cùng một thời điểm.

MPI_Wtime() Xác định thời gian của hệ thống.

MPI_Wtick() Xác định độ chính xác của thời gian

hệ thống.

MPI_Reduce(void *local, Hàm tính gộp, dùng để gộp các kết

void *global, int count, quả của từng tiến trình vào kết quả

MPI_Datatype type, MPI_Op chung. Trong đó, local là kết quả cục bộ,

operator, int root, MPI_Comm global là kết quả nhận được sau khi tính

comm) gộp các kết quả cục bộ, type là kiểu dữ

liệu tính gộp, operator là thao tác tính

gộp, root là thứ tự của tiến trình sẽ nhận

được kết quả global, comm là bộ giao

tiếp.

int MPI_Send(void *buf, int + buf: địa chỉ bắt đầu của thông báo

count, MPI_Datatype datatype, + count: độ dài của thông báo

int dest,int msgtag, MPI_Comm + datatype: kiểu dữ liệu

+ dest: số hiệu của tiến trình nhận comm)

+ msgtag: số hiệu của thông báo

+ comm: số hiệu của kênh làm việc

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

int MPI_Recv(void *buf, + OUT buf: địa chỉ đầu của thông

int count, MPI_Datatype báo

datatype, int source,int msgtag, + count

MPI_Comm comm, MPI_Status + datatype

*status) + source: số hiệu của tiến trình gửi

+ msgtag: số hiệu của thông báo

+ comm: số hiệu kênh

+ OUT: status – trạng thái

Các kiểu dữ liệu được dùng với MPI:

MPI_CHAR

Tên Kiểu dữ liệu C tƣơng đƣơng

MPI_DOUBLE

signed char

MPI_FLOAT

double

MPI_INT

Float

MPI_LONG

Int

MPI_LONG_DOUBLE

Long

MPI_SHORT

long double

MPI_UNISIGNED_CHAR

Short

MPI_UNISIGNED

unsigned char

MPI_UNSIGNED_LONG

unsigned int

MPI_UNSIGNED_SHORT

unsigned long

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

unsigned shorrt

2.6.4. Các mô hình tương tác trong lập trình MPI

Việc quan niệm vật chất được tạo ra từ các “phần tử” nhỏ và rằng mọi sự

tác động đều phải được lan truyền đi với vận tốc không vượt quá vận tốc ánh

sáng dẫn chúng ta đến mô hình tương tác gần.

Theo quan niệm này nếu có một sự thay đổi nào đó ở một “phần tử” thì

sự thay đổi này chỉ làm ảnh hưởng tới các thành viên ở ngay cạnh nó mà thôi.

Nếu chúng ta giao cho mỗi máy tính phụ trách một “phần tử” – máy tính này

tính toán ra trạng thái của “phần tử” dựa vào các định luật vật lý – thì chúng

ta đã thực hiện việc mô hình hóa một bài toán thực tế.

Quá trình mô hình hóa này tạo ra các kết nối ảo – theo đó các máy tính

kết nối và gửi dữ liệu cho nhau. Các kết nối ảo này phải được “nhúng” vào

các kết nối thực (tức là phân việc cho từng máy tính trên mạng) để tiến hành

tính toán.

Như vậy quá trình tính toán trên hệ thống mạng máy tính là sự mô phỏng

lại thực tế. Trong thực tế các đối tượng tương tác với nhau thông qua trao đổi

chất. Các đối tượng này được khái quát hóa và được hình dung như các máy

tính; quá trình trao đổi chất giữa chúng với nhau được mô phỏng lại thông

qua việc trao đổi dữ liệu giữa các máy tính. Trong thực tế, quá trình trao đổi

chất diễn ra song song vì vậy quá trình mô phỏng cũng cần phải được thực

hiện song song. Việc làm này được thực hiện trên mạng máy tính và sự

“tương tác” được thực hiện thông qua việc truyền dữ liệu.

Một trong số các lợi điểm của phương pháp mô phỏng nằm ở chỗ: cho

dù trong thế giới thực có rất nhiều kiểu tương tác giữa các vật thể với các qui

luật vật lý khác nhau, nhưng chúng có cùng chung một mô hình gửi nhận dữ

liệu khi mô phỏng chúng trên mạng.

Một trong số các điểm bất lợi của phương pháp mô phỏng nằm ở chỗ:

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

trong thực tế, các quá trình trao đổi chất diễn ra song song và cho dù vật chất

vận động thế nào thì đấy cũng là “thực tế”. Ngược lại, khi mô phỏng, việc

trao đổi này được thực hiện thông qua các lệnh gửi - nhận dữ liệu và chúng có

thể tự gây ra tắc nghẽn khiến cho toàn bộ quá trình trao đổi chất “mô - phỏng”

bị ngừng trệ.

Để tận dụng các lợi điểm và hạn chế các điểm bất lợi, MPI cung cấp một

số khả năng gửi nhận dữ liệu “tập thể”. Ở đấy các quá trình tương tác có trong

thực tế được mô hình hóa thông qua các kết nối cụ thể, được gọi là “kết nối

ảo” (virtual topology).

Kết nối thực:

Các bài toán thực tế thường cần tới những máy tính có cấu trúc đặc biệt

– mà chế tạo đơn chiếc thì tốn kém. Một trong số các phương hướng để giải

quyết vấn đề là tạo ra các “modul” đơn giản rồi ghép lại với nhau theo các cấu

trúc cần thiết, tạo ra các máy tính lớn hơn. Mỗi modul như vậy bao gồm một

số vi-xử-lý dùng chung một bộ nhớ. Chúng có khả năng kết nối với nhau –

“kết nối thực” (real topology) – để tạo ra một máy tính có nhiều thành phần

mà mỗi phần có nhiều vi-xử-lý.

Cấu tạo và khả năng kết nối của mỗi modul được tính toán dựa trên khả

năng công nghệ và tính tối ưu. Mặt khác các kết nối này phải hỗ trợ cho các

kết nối ảo. Như vậy có hai vấn đề xuất hiện: (1) Chúng ta có thể và chỉ có thể

tạo ra các kết nối thực nào? (2) Làm thế nào để các kết nối thực này hỗ trợ

cho các kết nối ảo?

Một trong số các sản phẩm có trên thị trường là modul Origin2000. Mỗi

modul gồm 2 vi-xử-lý cùng sử dụng chung một bộ nhớ RAM và có cổng kết

nối. Các modul này có thể kết nối với nhau thông qua cổng để tạo thành các

máy tính với nhiều vi-xử-lý có cấu trúc mong muốn để giải từng loại bài toá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

thực tế.

Không giống như việc gửi nhận dữ liệu trên mạng, quá trình gửi - nhận

dữ liệu giữa các modul là trực tiếp (không thông qua server) và có thể đi theo

nhiều đường kết nối khác nhau. Tất nhiên là có sự phân biệt giữa các máy liền

kề nhau và các máy ở xa. Trong sơ đồ trên, dữ liệu trao đổi giữa các máy nằm

ở cùng đỉnh liền kề nhau diễn ra rất nhanh – vì chỉ cần qua một “R” (Router),

giữa các máy trên cùng cạnh diễn ra chậm hơn – vì nó phải đi qua 2 “R”, giữa

các máy nằm ở các đỉnh đối diện với nhau sẽ là chậm nhất – vì chúng phải đi

qua 3 “R”.

Người ta cần phân cho nhiệm vụ cho từng vi-xử-lý một cách hợp lý – tốt

nhất là làm sao cho tất cả dữ liệu đều chỉ cần đi một khoảng cánh ngắn nhất

có thể. Điều này đòi hỏi không chỉ nghệ thuật phân việc cho các vi-xử-lý mà

còn ở cấu trúc mạng máy tính.

Người ta thấy rằng phần lớn các bài toán có thể được triển khai trên

mạng vi-xử-lý có dạng kết nối như sau:

Cấu trúc “hướng tâm”: Các vi-xử-lý trao đổi dữ liệu với nhau thông qua

một vi-xử-lý “trung tâm”.

Cấu trúc thẳng: Các vi-xử-lý kết nối với nhau thẳng hàng, các vi-xử-lý

đều có thể gửi nhận dữ liệu đến các vi-xử-lý ở cạnh mình.

Cấu trúc tròn: Các vi-xử-lý kết nối với nhau thành một vòng tròn, các

vi-xử-lý đều có thể gửi nhận dữ liệu đến hai vi-xử-lý ở cạnh mì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

Hình 2.7. 6 vi xử lý kết nối với nhau thành hình tròn

Cấu trúc lưới: Các vi-xử-lý kết nối với nhau thành lưới ô vuông, hai

chiều hoặc ba chiều. Các vi-xử-lý có thể gửi dữ liệu tới 4 vi-xử-lý cạnh nhau

(trong trường hợp lưới ô vuông 2 chiều, hoặc là 8 vi-xử-lý cạnh nhau (trong

trường hợp lưới ô vuông 3 chiều).

Hình 2.8. Các vi-xử-lý kết nối với nhau thành lưới

Ánh xạ nhúng:

Khả năng kết nối các modul lại với nhau để được một máy tính mạnh

hơn cho phép tạo ra nhiều máy tính với các cấu trúc khác nhau. Các vi xử lý

trong các máy trên là các máy tính riêng biệt có bộ nhớ riêng. Tuy có sự khác

nhau trong cấu tạo nhưng việc gửi nhận dữ liệu giữa chúng được thực hiện

thông qua các lệnh gửi - nhận cơ bản. Điều này hàm ý là người lập trình sẽ

không phải lưu tâm quá mức đến cấu trúc vật lý của máy tính. Họ sẽ chỉ cần

biết cách sử dụng các lệnh gửi - nhận cơ bản là đủ để sử dụng hệ thống máy

tính phục vụ cho việc tính toán của mình.

“Kết nối ảo” trong chương trình phải được nhúng vào “kết nối thực”

trong máy tính. Kết nối ảo là được tạo ra từ các tiến trình, kết nối thực là từ

các vi xử lý – chúng nối với nhau bằng các dây dẫn điện. Chính vì thế để làm

giảm thời gian gửi - nhận dữ liệu, những tiến trình hay gửi dữ liệu cho nhau

phải được thực hiện trên các vi xử lý ở cạnh nhau. Quá trình phân bổ cô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

việc cho các vi xử lý được gọi là “nhúng” cấu trúc ảo vào cấu trúc thực.

Do tính “tương đương” của các thành phần mà các tiến trình trong một

kết nối ảo của một bài toán thực tế thường là tương đương với nhau. Chính vì

vậy các kết nối ảo thông dụng không nhiều, chúng chủ yếu thuộc hai loại:

Loại thứ nhất (các bài toán vật lý) là các lưới: một chiều, hai chiều, ba

chiều…, loại thứ hai (các bài toán quản lý) là các đồ thị cây, kiểu như cây nhị

phân.

Topology – Kết nối ảo:

Kết nối ảo là kết nối của một số nào đó của tiến trình – máy ảo. Mỗi

tiến trình hay máy ảo cần phải biết được số hiệu của các máy tính liền kề với

nó. Dựa vào các thông tin này chúng gửi dữ liệu cho nhau.

Các kết nối mạng ảo thường gặp thuộc vào một trong số các dạng sau:

- Kết nối nhóm: với kiểu kết nối này dữ liệu có thể trao đổi trong nhóm

mà các thành viên khác không thuộc trong nhóm này sẽ không thể nhận được.

- Dạng kết nối đồ thị cây.

- Và dạng kết nối tuyến tính bao gồm các kết nối thẳng và kết nối vòng,

kết nối lưới ô vuông (2 hoặc 3 chiều).

Kết nối nhóm “Group”:

Kết nối nhóm thường được sử dụng để phân chia công việc cho từng

nhóm khác nhau. Mỗi máy tính ảo luôn có một số hiệu, số hiệu này có được

ngay từ khi bắt đầu chạy trình. Và nếu nó thuộc thêm vào một nhóm nào đó

thì nó có thêm số hiệu riêng theo nhóm ấy. Như vậy MPI_COM_WORLD là

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

nhóm ban đầu, bao gồm tất cả các máy tính.

Chƣơng 3

CÀI ĐẶT THỬ NGHIỆM

Trong chương này chúng ta sẽ xem xét cách giải một bài toán tính toán

trên Computer Cluster. Cụ thể, ta sẽ cách giải phương trình vi phân đạo hàm

riêng Laplace và đánh giá kết quả nhận được.

3.1. Phƣơng trình vi phân đạo hàm riêng

Phương trình đạo hàm riêng là một lĩnh vực quan trọng của toán học.

Có rất nhiều sự vật, hiện tượng, hoạt động trong tự nhiên được mô tả bởi một

phương trình hoặc một hệ phương trình vi phân nói chung và phương trình vi

phân đạo hàm riêng nói riêng. Một phương trình liên hệ giữa ẩn hàm

u(x1,…,xn), các biến độc lập xi và các đạo hàm riêng của nó được gọi là một

phương trình vi phân đạo hàm riêng (hay phương trình đạo hàm riêng cho

gọn). Nó có dạng:

Trong đó F là một hàm nào đó của các đối số của nó, với ký hiệu x = Rn, u(x) = u(x1,…,xn). Cấp cao nhất của đạo hàm riêng của u có (x1,…,xn)

mặt trong phương trình. Phương trình được gọi là tuyến tính nếu nó tuyến tính

đối với ẩn hàm và các đạo hàm riêng của ẩn hàm.

Lý thuyết phương trình đạo hàm riêng có hai nét đặc thù cơ bản. Thứ

nhất là mối liên hệ trực tiếp với các bài toán vật lý, vì quá trình nghiên cứu

các bài toán vật lý và cơ học dẫn đến các bài toán phương trình đạo hàm

riêng, vì vậy người ta còn gọi là phương trình đạo hàm riêng là phương trình

vật lý toán. Những nhà tiên phong trong lĩnh vực này là J.D’Alembert (1717-

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

1783), L.Euler (1707-1783), D.Bernoulli (1700-1782), J.Lagrange (1736-

1813), P.Laplace (1749-1827), S.Poisson (1781-1840), J.Fourier (1768-1830).

Thứ hai là mối liên hệ mật thiết của phương trình đạo hàm riêng với các

ngành toán học khác như giải tích hàm, lý thuyết hàm, tô pô, đại số....

3.2. Phƣơng trình Laplace

(1)

Phương trình Laplace 2 chiều có dạng như sau:

Cùng với:

u(x,y)=g(x,y) (x,y) ∂Ω (2)

Gồm có 2 phần: một là phương trình vi phân ứng với mọi giá trị x,y nằm

trong miền Ω và hai là giá trị U dọc theo đường biên ∂Ω được biểu diễn thông

qua hình sau:

Hình 3.1. Miền Ω và đường biên ∂Ω

Ở đây Ω ≡ [ax,bx]x[ay,by] và f(x,y), g(x,y) là các hàm được đưa ra, giả sử

nằm trong vùng C(Ω) hoặc C(∂Ω).

Cũng giống như các phương trình vi phân khác, để giải phương trì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

Laplace (1) bằng máy tính cần phải sử dụng phương pháp xấp xỉ rời rạc. Ta

chia nhỏ miền Ω thành lưới gồm Nx×Ny ô kích thước hx×hy như Hình 3.2. Giả

sử điểm (x,y) nằm tại vị trí (i,j) trên lưới ô, khi đó ta ký hiệu:

ui,j = u(x,y); ui-1,j = u(x-hx,y); ui+1,j = u(x+hx,y)

(3) ui,j+1 = u(x,y+hy); ui,j-1 = u(x,y-hy) ;

fi,j=f(x,y), gi,j=g(x,y).

Biến đổi phương trình (1) về dạng sai phân rời rạc bằng cách xấp xỉ đạo

hàm bậc hai:

(4) = fi,j

với i =2,3,…, Nx-1; j = 2,3,…, Ny-1.

Điều kiện (2) có thể được viết dưới dạng sau:

(5) ui,j = gi,j

với i=1 hoặc Nx, (j=2,…, Ny - 1); hoặc với j=1 hoặc Ny, (i=2,…,Nx-1).

Trong đó giá trị i, j là các giá trị được biểu diễn như hình sau:

Hình 3.2. Sai phân hữu hạn (Finite difference)

Để đơn giản, ta giả sử rằng khoảng cách giữa các lưới là đồng bộ trong

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

các hướng khác nhau. Việc thiết lập vấn đề này được miêu tả trong hình 3.2,

một sự thay đổi trong hình 3.3 cho trường hợp đặc biệt của Laplacian được

xét tại đây.

Chúng ta tính toán hx và hy:

Và có sự thiết lập đặc biệt ở đó hx = hy = h thì công thức (4) được biến

đổi thành:

ui-1,j+ui,j-1 - 4ui,j+ui,j+1+ui+1,j = h2 fi,j, với i =2,3,…,Nx-1; j = 2,3,…,Ny-1 (6)

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 Nx x Ny điểm.

3.3. Công thức lặp Jacobi

Nếu chúng ta phân tích (6) với Ui,j và đưa vào các biến đếm lặp, thì

chúng ta được công thức lặp Jacobi sau:

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

= [ + + + – h2fi,j], với n=1,2,… (7)

Công thức (7) được gọi là công thức lặp Jacobi, quá trình lặp sẽ dừng

khi:

(8)

Với mọi i, j trong tập chỉ số của phương trình (6), tập các phương trình

này được được rút gọn có thể được miêu tả như sau:

u(n+1)=Bu(n) + k, (9)

ở đó B là ma trận lặp Jacobi.

3.3.1. Giá trị riêng của ma trận lặp Jacobi

Để kiểm tra sự hội tụ của các vòng lặp lại (9) chúng ta cần tìm ρ(B), bán

kính quang phổ của ma trận lặp Jacobi B. Trong trường hợp hiện tại, chúng ta

sẽ làm phép phân tích này. Chúng ta bắt đầu thể hiện vấn đề giá trị riêng cho

ma trận này như: Bv=μv, (10)

ở đó v là vecto riêng tương ứng với giá trị riêng μ. Phương trình (7) và cấu

trúc dải trong hình 3.4 ngụ ý rằng chúng ta có thể viết một phương trình bất kì

từ hệ thống (10) như: = (11)

Chúng ta cũng viết trong phương trình sai phân được phân tích như sau:

[ (x-h,y) + (x,y-h) + (x,y+h) + (x+h,y)] = (x,y) (12)

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

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

Bây giờ từ tính đồng nhất của các vấn đề giá trị riêng, và từ nhân tố đó

mà vấn đề giá trị đường biên của phương trình sai phân là Dirichlet. Chúng ta

kết luận rằng:

(x,y) = sin (13)

Ở đó chúng ta phải nắm bắt miền Ω là (0,a) x (0,b). Đó là (a,y) = 0 trên

∂Ω. Thay thế (13) thành (12) tuân theo một số tiêu chuyển, nhưng các thao tác

kết quả của công thức lượng giác thể hiện như sau:

cos ) (14)

Với giá trị riêng của ma trận lặp Jacobi B. Trong (13) và (14) p và q có

thể là số nguyên, nhưng nhớ rằng B chỉ là một ma trận kiểu [(Nx -2)(Ny -

2)]x[(Nx -2)(Ny -2)], vậy p và q có thể là các giá trị nằm giữa 1 tới Nx - 2 và 1

được tính toán trong tới Ny – 2, trước đó sự lặp lại xuất hiện trong các giá trị

(14).

Nhiệm vụ của chúng ta bây giờ là tìm , để tìm giá trị lớn nhất của

cho p và q trong các mảng trên. Nó dễ dàng kiểm tra mà giá trị cực đại xuất

hiện với p=q=1, đưa ra được kết quả:

cos ) (15)

Đây chính xác là bán kính quang phổ của ma trận lặp Jacobi tới vấn đề

Dirichlet của phương trình Laplace trên một lưới Nx x Ny trong miền chữ nhật

Ω =(0,a)x(0,b), như vậy hx=hy=h từ đây ta có:

(16)

3.3.2. Tính toán Jacobi

Tính toán Jacobi là một tập dữ liệu (1D, 2D, 3D,...), là một mảng giá trị

ở đó được cập nhật trong một quy trình lặp tới một số điều kiện được thỏa

mãn. Chúng ta sẽ tính một giá trị mới cho mỗi phần tử trong ma trận 2 chiều.

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

Giá trị mới của phần tử này sẽ là giá trị trung bình của các phần tử hiện tại và

giá trị hiện tại nằm trong bốn điểm lân cận của nó. Chúng ta sẽ làm điều này

cho mỗi phần tử trong ma trận (một phương pháp lặp). Kết thúc mỗi vòng lặp

thay đổi giá trị cực đại được xác định. Đó là mỗi phần tử trong ma trận thì giá

trị thay đổi là khác nhau giữa giá trị cũ và giá trị mới, mà giá trị cực đại được

tính toán qua toàn bộ ma trận 2D.

Hình dưới minh họa trên một đối tượng thực hiện việc tính toán với các

vòng bao quanh. Và 5 sự kiện xuất hiện trong mỗi bước để thi hành việc tính

toán.

A: Đối tượng trung tâm hướng tới đông East(x+1, y) gửi cột dữ liệu

phía tây gần nhất với nó tới đối tượng (x, y). Dữ liệu được copy tới vị trí

hướng đông.

B: Đối tượng trung tâm hướng tới nam South(x, y+1) gửi dòng dữ liệu

phía bắc gần nhất với nó tới đối tượng (x, y). Dữ liệu được copy tới vị trí

hướng nam.

C: Đối tượng trung tâm hướng tới tây west(x-1, y) gửi cột dữ liệu phía

đông gần nhất với nó tới đối tượng (x, y). Dữ liệu được copy tới vị trí hướng

tây.

D: Đối tượng trung tâm hướng tới bắc north(x, y-1) gửi dòng dữ liệu

phía nam gần nhất với nó tới đối tượng (x, y). Dữ liệu được copy tới vị trí

hướng bắc.

E: Đối tượng (x, y) tương tự như vậy gửi dữ liệu tới 4 vị trí lân cận.

Điều này được thực hiện theo cách thức tương tự như cách từng truyền đạt dữ

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

liệu được gửi.

Hình 3.5. Thực hiện tính toán Jacobi trên một đối tượng

3.4. Song song hóa thuật toán

xx + Uyy = 0, đưa ra một vùng không gian và các giá

Với phương trình: U

trị cho các điểm trên đường biên của vùng, kết quả là để xấp xỉ cho các điểm

trong vòng lặp.

Thuật toán song song thực hiện các bước sau:

Ta sẽ song song hóa công thức (7) bằng cách phân mỗi bộ xử lý một

miền có kích thước giống nhau xử lý theo thuật toán sau:

Lựa chọn giá trị khởi tạo diff = 10

While diff > (hoặc lặp với số lần đủ lớn)

1. Tính toán lặp cho mỗi điểm thuộc vùng

2. Gửi giá trị lặp được tính toán trên đường biên của vùng tới bộ xử lý

vùng bên cạ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

3. Nhận giá trị lặp cho các điểm cần thay đổi

4. Tính toán giá trị diff = |u_new[ij]- u_old[ij]| với ij là chỉ số điểm

nằm trong vùng

End While

3.5. Kết quả thực hiện

3.5.1. Thông tin chung về hệ thống

Học viên đã sử dụng Cluster Server tại Trung tâm Khoa học tính toán

của trường Đại học Sư Phạm Hà Nội để thực hiện thuật toán trên. Hệ thống

Cluster này bao gồm:

+ 09 máy tính (node1,.., node9), mỗi máy có 4 processors. Các máy từ

node1 đến node7 có 4GB bộ nhớ trong, node8 có 16 GB bộ nhớ trong, node9

có 32 GB bộ nhớ trong.

+Tất cả 9 nodes của hệ thống được cài đặt hệ điều hành linux debian và

cấu hình thành một PC Cluster với thư viện xử lý song song MPITCH2 và Bộ

quản lý chương trình PBS Torque.

Người sử dụng có thể truy cập và khai thác các tài nguyên hệ thống

thông qua máy Master (node7) với tên internet toàn cầu là: ccs1.hnue.edu.vn

thông qua giao thức ssh. Hệ thống đã cài đặt các trình biên dịch cho các ngôn

ngữ lập trình thông dụng như C, C++, java, Fortran, matlab, v.v.

3.5.2. Giao diện và lệnh thực hiện

3.5.2.1. Giao diện thực hiệ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

- Sử dụng phần mềm putty.exe để đăng nhập vào hệ thống:

Hình 3.6a. Đăng nhập vào trung tâm với tên ccs1.hnue.edu.vn

Hình 3.6b. Nhập thông tin tài khoản

- Sử dụng phần mềm winscp để tải lên hoặc lấy về chương trình và dữ

liệu trên Hệ thống của Trung tâ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

Hình 3.6c. Sử dụng phần mềm winscp để đăng nhập vào hệ thống

Hình 3.6d. Các file trên tài khoản đăng nhập vào hệ thống

3.5.2.2. Lệnh thực hiện

a) File sử dụng MPI

Học viên đã đẩy lên với file có tên Laplace.cpp chứa các lệnh chương

trình để thực hiện chạy song song trên hệ thống bao gồm các bước sau:

- Biên dịch bằng trình biên dịch: mpic++ Laplace.cpp –o Laplace

- Tạo file PBS script Laplace.script có nội dung đơn giản như sau:

#!/bin/sh

/usr/local/bin/mpiexec /home/tuanha/Laplace

- Sau đó đẩy file lên hệ thống

b)File thực hiện tuần tự

Đối với file Cpp thực hiện tuần tự để thực hiện ta thao tác như sau:

- Đẩy file lên hệ thống

- Biên dịch file bằng lệnh: c++ Laplace_TT.cpp –o Laplace_TT

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

- Chạy file bằng lệnh: . /Laplace_TT

3.5.3. Kết quả thực hiện tuần tự

Hình 3.7. Thời gian thực hiện trên tính toán tuần tự > 200s

3.5.4. Kết quả thực hiện thực hiện xử lý song song trên nhiều máy

Hình 3.8a. Lệnh qsub –q l1 –l nodes=2:ppn=4 Laplace.script trên 2

node, mỗi node gồm 4 vi xử lý. Cho ra kết quả nằm trong tệp 24035

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

Hình 3.8b. Kết quả thời gian thực hiện

Hình 3.8c. Kết quả lưu trữ trên tệp. dat

Như vậy, kết quả nhận được về mặt thời gian như sau:

Chạy chương trình thực hiện thuật toán song song với 2 nodes, mỗi node

gồm 4 vi xử lý bằng lệnh qsub (Hình 3.8a) thời gian giải là 32 giây (Hình

3.8b). Chạy chương trình thực hiện thuật toán giải tuần tự trên 1 node, thời

gian giải là hơn 200 giây (Hình 3.7). Như vậy việc giải song song phương

trình Laplace trên Computer Cluster đem lại hiệu quả cao hơn rất nhiều so với

giải tuần tự.

3.6. Nhận xét và đánh giá

Từ kết quả trên với việc thực hiện tuần tự trên một máy ta thấy kết quả

khác nhiều so với việc thực hiện trên nhiều máy với nhiều vi xử lý. Với

phương trình Laplace 2D thì quá trình xử lý được thực hiện lặp trên mỗi phần

tử, nếu ta tăng số lượng phần ở mức lớn hơn thì thời gian thực hiện tính toán

trên một máy sẽ tốn nhiều thời gian khi thực hiện trên nhiều máy. Phương

trình Laplace là một phương trình đạo hàm riêng được áp dụng nhiều trong

trong ngành vật lý như tính giao động của dây, truyền nhiệt trong môi trường

đẳng hướng,…. Do vậy đối với các chương trình có độ phức tạp trong tính

toán hoặc những bài toán lớn thì xử lý song song trên nhiều máy sẽ được kế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

quả như mong muốn và giảm thiểu được thời gian thực hiện.

KẾT LUẬN VÀ KIẾN NGHỊ

1. Kết luận

Trong cuốn luận văn này học viê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 mô hình, cách xây dựng, lập trình

trên Cluster cũng như 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 là minh chứng nói lên triển vọng của tính toán song song, của

Computer Cluster.

Trong bài toán trên học viên đã áp dụng việc xử lý song song đối với

2. Kiến nghị

phương trình Laplace trên 2 chiều, kết hợp với công thức lặp Jacobi để giải

quyết số lượng phần tử tương đối nhỏ. Nhưng đối với số lượng phần tử lớn và

do tính chất yêu cầu của bài toán thì thuật toán cần phải được cải tiến thêm và

song song hóa trên nhiều chiều khác nhau. Trong thời gian tiếp theo học viên

sẽ từng bước nghiên cứu xây dựng một phương pháp mới có thể giải bài toá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

một cách nhanh gọn.

TÀI LIỆU THAM KHẢO

Tiếng Việt

[1] TS. Nguyễn Mạnh Hùng, Bài giảng xử lý song song, Trường Học viện kỹ

thuật Quân sự.

[2] GS. Tạ Văn Đĩnh, 2002, Phương pháp sai phân và Phương pháp phần tử

hữu hạn, NXB Khoa học Kỹ thuật.

[3] Nguyễn Văn Chương, 2002, Phương trình đạo hàm riêng, NXBGD.

Tiếng Anh

[4] C. A. R. Hoare, Communicating Sequencatial Processes, Prentice Hall,

1985 (new version 2003, Jim.Davies@comlab.ox.ac.uk).

[5] Joseph JáJá, An Introduction to Parallel Algrithms, Addison - Wesley,

1992.

[6] Bitola, Parallel Numerical Simulation, October 2-8, 2005.

[7] M. Sasikumar, Dinesh Shikhare, P. Ravi Prakash, Introduction to Parallel

Processing, Prentice - Hall, 2000.

[8] Seyed H. Roosta, Parallel Processing and Parallel Algorithms, Theory

and Computation, Springer 1999.

[9] Roy Culver, Numerical Solution of the Poisson Equation, MAE 237

Computational Fluid Dynamics, (January 24, 2005).

[10] Eric Dow, A Parallel Iterative Poisson Solver for a Distributed Memory

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

Architecture, May 11, 2010.

Luận văn Thạc sĩ Khoa học máy tính: 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

Nội dung của luận văn "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" trình bày về lý thuyết xử lý song song và phân tán, Cluster và tính toán phân tán bằng Cluster, cài đặt thử nghiệm.

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

Thái Nguyên - 2012

Có thể bạn quan tâm

Tài liêu mới

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok

Luận văn Thạc sĩ Khoa học máy tính: 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

Nội dung của luận văn "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" trình bày về lý thuyết xử lý song song và phân tán, Cluster và tính toán phân tán bằng Cluster, cài đặt thử nghiệm.

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

Thái Nguyên - 2012

Có thể bạn quan tâm

Tài liêu mới

AI tóm tắt

Giới thiệu tài liệu

Đối tượng sử dụng

Từ khoá chính

Nội dung tóm tắt

Giới thiệu

Về chúng tôi

Việc làm

Quảng cáo

Liên hệ

Chính sách

Thoả thuận sử dụng

Chính sách bảo mật

Chính sách hoàn tiền

DMCA

Hỗ trợ

Hướng dẫn sử dụng

Đăng ký tài khoản VIP

093 303 0098

support@tailieu.vn

Phương thức thanh toán

Theo dõi chúng tôi

Facebook

Youtube

TikTok