Thạc Sĩ 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ì

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.
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 nganghà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