Giải pháp nâng cao hiệu quả của giản đồ lập lịch dựa trên độ tin cậy trong các hệ thống tính toán tình nguyện

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

---------------------------------------

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

GIẢI PHÁP NÂNG CAO HIỆU QUẢ CỦA GIẢN ĐỒ LẬP LỊCH DỰA TRÊN ĐỘ TIN CẬY TRONG CÁC HỆ THỐNG TÍNH TOÁN TÌNH NGUYỆN

Có thể bạn quan tâm!

Xem toàn bộ 83 trang tài liệu này.

NGÀNH: CÔNG NGHỆ THÔNG TIN

MÃ SỐ: ………………………………

Nguyễn Quang Hòa

Người hướng dẫn khoa học: TS. NGÔ HỒNG SƠN

Hà Nội – 2008

LỜI CAM ĐOAN

Tôi xin cam đoan bản Luận văn này là công trình nghiên cứu của riêng tôi. Các dữ liệu và kết quả nêu trong Luận văn là hoàn toàn trung thực và có nguồn gốc rõ ràng.

TÁC GIẢ

(Ký tên)

Chương 1. LỜI CẢM ƠN

Trước hết, tôi xin được chân thành cảm ơn TS. Ngô Hồng Sơn đã tận tình hướng dẫn, cung cấp tài liệu và kiến thức cần thiết giúp tôi hoàn thành Luận văn tốt nghiệp này.

Tôi xin bày tỏ lòng biết ơn sâu sắc tới các thầy, cô giáo trong Khoa Công nghệ thông tin cũng như các thầy, cô giáo trong trường Đại học Bách Khoa Hà Nội đã truyền đạt cho tôi những kiến thức quan trọng trong suốt thời gian tôi học tập và nghiên cứu tại trường.

Cuối cùng, tôi xin được nói lời cảm ơn đến gia đình và bạn bè, những người luôn ở bên tôi, cổ vũ và động viên tôi trong suốt thời gian học tập và làm luận văn tốt nghiệp.

Trong quá trình hoàn thành luận văn, do còn thiếu kinh nghiệm, sự ràng buộc về thời gian và sự hạn chế về kiến thức nên chắc chắn không tránh khỏi những thiếu sót. Vì vậy tôi rất mong nhận được sự đóng góp ý kiến và giúp đỡ của các thầy, các cô và các bạn.

Hà Nội, ngày 20 tháng 11 năm 2008 Người thực hiện luận văn

MỤC LỤC

LỜI CAM ĐOAN 1

LỜI CẢM ƠN 2

MỤC LỤC 3

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ 5

MỞ ĐẦU 6

Chương 1. TỔNG QUAN 8

1.1 Tính toán lưới 8

1.2 Tính toán ngang hàng 12

1.3 Tính toán tình nguyện 14

1.3.1 Khái niệm 14

1.3.2 BOINC 15

1.3.2.1 Khái niệm 15

1.3.2.2 Các đặc trưng cơ bản của BOINC [23] 16

1.3.2.3 Kiến trúc BOINC 18

1.3.3 Lập lịch trong tính toán tình nguyện 19

1.3.3.1 Lập lịch phía máy trạm 20

1.3.3.2 Lập lịch phía máy chủ 20

1.3.3.3 Lập lịch chịu lỗi dựa trên độ tin cậy 21

1.3.4 So sánh với tính toán lưới và tính toán ngang hàng 23

1.3.4.1 Tính toán lưới 23

1.3.4.2 Tính toán ngang hàng 23

Chương 2. LÝ THUYẾT CƠ BẢN VỀ LẬP LỊCH DỰA TRÊN ĐỘ TIN CẬY 25

2.1 Mô hình cơ bản và các giả định 25

2.2 Các kĩ thuật chịu lỗi truyền thống. 28

2.2.1 Biểu quyết theo số đông 29

2.2.2 Kiểm tra điểm 30

2.2.2.1 Kiểm tra điểm dùng danh sách đen 31

2.2.2.2 Kiểm tra điểm không dùng danh sách đen 32

2.3 Chịu lỗi dựa trên độ tin cậy 33

2.3.1 Tổng quan 33

2.3.2 Tính toán độ tin cậy 35

2.3.3 Ứng dụng sự tin cậy 36

2.3.3.1 Kết hợp biểu quyết và kiểm tra điểm 36

2.3.3.2 Kiểm tra điểm bằng biểu quyết 37

2.4 Khảo sát một số giản đồ lập lịch 38

2.4.1 Lập lịch Round Robin 39

2.4.2 Lập lịch Round Robin dựa trên sự ưu tiên về khả năng tính toán 41

Chương 3. GIẢN ĐỒ LẬP LỊCH ROUND ROBIN DỰA TRÊN ĐỘ TIN CẬY 44

3.1 Giản đồ lập lịch Round Robin dựa trên sự ưu tiên về độ tin cậy 44

3.2 Giản đồ lập lịch Round Robin dựa trên kiểm thử độ tin cậy 55

Chương 4. KẾT QUẢ THỰC NGHIỆM 65

4.1 Chương trình mô phỏng 65

4.2 Kịch bản mô phỏng 65

4.3 Kết quả 66

Chương 5. KẾT LUẬN 72

5.1 Những kết quả đạt được. 72

5.2 Những công việc chưa làm được 72

5.3 Hướng phát triển trong tương lai 73

TÀI LIỆU THAM KHẢO 74

DANH MỤC CÁC HÌNH VẼ VÀ ĐỒ THỊ

Hình 1-1. Minh họa về tính toán lưới. 9

Hình 1-2. Tổ chức ảo 11

Hình 1-3. Mô hình mạng ngang hàng 12

Hình 1-4. Mô hình tính toán tình nguyện 15

Hình 1-5. Mô hình cơ bản của BOINC 16

Hình 1-6. Kiến trúc BOINC 18

Hình 1-7. Sự tương tác giữa máy trạm và máy chủ 19

Hình 2-1. Mô hình chủ khách 26

Hình 2-2. Hàng đợi công việc lập lịch tham lam với biểu quyết m đầu tiên 28

Hình 2-3. Tỉ lệ lỗi của biểu quyết số đông với nhiều các giá trị m và f [8] 30

Hình 2-4. Hàng đợi công việc lập lịch tham lam nâng cao độ tin cậy [8] 33

Hình 3-1. Mô tả hệ thống tính toán tình nguyện 45

Hình 3-2. Sơ đồ hình vẽ các bước của giản đồ lập lịch Round Robin dựa trên sự ưu tiên về độ tin cậy 46

Hình 3-3. Sơ đồ hình vẽ các bước của giản đồ lập lịch kiểm thử dựa trên độ tin cậy

...................................................................................................................................57

Hình 4-1. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.25,N >P 67 Hình 4-2. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.5,N >P..68 Hình 4-3 Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.75,N >P.68 Hình 4-4. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 1,N >P 69

Hình 4-5. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.25,N< P 69 Hình 4-6. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.5,N< P..70 Hình 4-7. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 0.75,N< P 70 Hình 4-8. Biểu đồ so sánh sự chậm chễ của các giản đồ lập lịch với s= 1,N< P 71

MỞ ĐẦU

Tính toán tình nguyện là một mô hình tính toán song song hấp dẫn để xây dựng lên các hệ thống tính toán có phạm vi rộng lớn từ số lượng lớn các máy tính tình nguyện trên mạng. Trong những năm gần đây, đã có sự quan tâm tăng lên và nhanh chóng trong các hệ thống tính toán tình nguyện. Hệ thống tính toán tình nguyện cho phép người sử dụng từ bất cứ nơi nào trên mạng, đóng góp thời gian tính toán nhàn rỗi của máy tính để hướng vào giải quyết các bài toán có thời gian tính toán lớn.

Tính toán tình nguyện giúp cho có thể xây dựng các mạng tính toán toàn cầu lớn rất nhanh, điều này được chứng mình bởi sự thành công của dự án SETI@home[2], dự án này đang triển khai hàng trăm nghìn máy tính tình nguyện để tìm kiếm số lượng lớn dữ liệu đàm thoại radio cho tín hiệu của sự sống bên ngoài trái đất, Einstein@Home [6] tìm kiếm các sao neutron xoay rất nhanh dùng dữ liệu từ các nhà dò tìm sóng hấp dẫn LIGO và GEO hay Climateprediction.net@Home [7] dùng để dự đoán khí hậu trên trái đất …

Trong hệ thống tính toán tình nguyện, khả năng chịu đựng lỗi là một vấn đề quan trọng bởi vì có thể có nhiều những người dùng ác ý trên mạng phá hoại hệ thống bằng việc cố ý đệ trình các kết quả sai. Để giải quyết yêu cầu đưa ra kết quả tốt trong hệ thống tính toán tình nguyện mà có người dùng ác ý tham gia thì hệ thống lập lịch tại máy chủ phải thực thi các chính sách lập lịch chịu lỗi. Do đó trong luận văn này, tôi quan tâm đến vấn đề lập lịch nhiệm vụ phía máy chủ của hệ thống tính toán tình nguyện thực thi các kĩ thuật chịu đựng lỗi. Mặc dù một số kĩ thuật chịu lỗi đang tồn tại như là biểu quyết theo số đông, kiểm tra điểm, kết hợp biểu quyêt và kiểm tra điểm, kiêm tra điểm bằng biểu quyết [8], hay giản đồ lập lịch Round Robin dựa trên sự ưu tiên về khả năng tính toán [10] có thể đảm bảo các yêu cầu về độ tin cậy cho các kết quả tính toán, tuy nhiên, các kĩ thuật này luôn luôn là nguyên nhân làm cho hiệu năng giảm đi trong giới hạn của toàn bộ thời gian tính toán. Trong luận văn này tôi đề xuất hai kĩ thuật lập lịch hiệu quả cho máy chủ được gọi là lập lịch Round Robin dựa trên sự ưu tiên về độ tin cậy và lập lịch Round Robin dựa trên kiểm thử độ tin cậy nhằm nâng cao hiệu quả của giản đồ lập lịch dựa trên độ tin

cậy trong các hệ thống tính toán tình nguyện. Các kĩ thuật này đều đưa ra các tiêu chí để chọn một máy trạm phù hợp nhất để thực thi một nhiệm vụ. Kĩ thuật đầu tiên quan tâm đến chọn một máy trạm đang có khả năng có độ tin cậy cao nhất và khả năng thực hiện tốt nhất. Kĩ thuật thứ hai thì chọn máy trạm sao cho khi nhiệm vụ được thực hiện bởi nó thì độ tin cậy của nhiệm vụ sẽ tăng lên, Bằng việc sử dụng bộ mô phỏng VCSIM để thực hiện mô phỏng các thuật toán lập lịch, tôi đã chỉ ra rằng kĩ thuật được đưa ra có thể giúp giảm bớt thời gian thực thi của toàn bộ hệ thống so với kĩ thuật lập lịch Round Robin tương ứng.

Phần còn lại của luận văn này được tổ chức như sau:

 Chương 1. Giới thiệu tổng quan: Trình bày về các hệ thống tính toán phân tán, tính toán lưới, tính toán ngang hàng, tính toán tình nguyện, BOINC, và khảo sát qua các thuật toán lập lịch trong tính toán tình nguyện.

 Chương 2. Lý thuyết cơ bản lập lịch dựa trên độ tin: Trình bày về các mô hình cơ bản của hệ thống và các giả định, các kĩ thuật chịu lỗi chuyền thống, chịu lỗi dựa trên độ tin cậy và khảo sát một số giản đồ lập lịch chịu lỗi dựa trên độ tin cậy.

 Chương 3. Giản đồ lập lịch dựa trên độ tin cậy: Mô tả các đề xuất của chúng tôi về giản đồ lập lịch dựa trên độ tin cậy.

Chương 4. Kết quả thực nghiệm: Giới thiệu kịch bản mô phỏng và thảo luận về các kết quả mô phỏng.

Chương 5. Kết luận: Tóm tắt lại những công việc đã đạt được, những công việc chưa làm được và hướng phát triển trong tương lai.