luuviethung.hung
New Member
Download Luận văn 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
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ẬY25
2.1 Mô hình cơbản và các giả định.25 4
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ẬY44
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
1.3.4.1 Tính toán lưới
Tính toán lưới và Tính toán tình nguyện giống nhau ở chỗ cùng sử dụng nhiều máy
tính kết nối với nhau để thực hiện một công việc chung. Tuy nhiên, tính toán lưới
không có một máy chủ tập trung mà được phân thành các cụm nhỏ, mỗi cụm nhỏ ấy
có thể lại được phân chia nhỏ hơn và đơn vị nhỏ nhất là các PC thông thường, với
nhiệm vụ là tính toán và trả về kết quả. Liên tưởng tính toán lưới với sự tham chiếu
tới việc chia sẻ những tài nguyên tính toán bên trong và giữa các tổ chức.
- Mỗi tổ chức có thể đóng vai trò là người sản xuất hay khách hàng của tài
nguyên (giống như trong lưới điện, các công ty điện năng có thể mua hay bán
năng lượng từ các công ty khác, phù hợp với yêu cầu biến đổi).
- Các tổ chức chịu trách nhiệm qua lại, nếu 1 tổ chức cư xử không đúng, những tổ
chức khác có thể từ chối hợp tác, chia sẻ tài nguyên với họ và ngược lại.
Như vậy, tính toán lưới có tính đến trách nhiệm và không có tính che giấu. Những
người tham gia phải chịu trách nhiệm về các kết quả, các xung đột, sai sót… (điểm
khác nhau cơ bản với tính toán tình nguyện).
1.3.4.2 Tính toán ngang hàng
Điểm khác nhau cơ bản nhất là tính toán ngang hàng không hề có server. Nó chỉ
đơn thuần gồm các PC kết nối với nhau và không có cái nào làm chủ. Trong đó, các
file và dữ liệu khác được trao đổi giữa các “máy ngang hàng” (ví dụ như các PCs)
mà không liên can gì tới máy chủ trung tâm. Nó khác với tính toán tình nguyện:
24
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
- Tính toán tình nguyện có những máy chủ trung tâm. Điển hình là không có
truyền thông ngang hàng.
- Tính toán ngang hàng mang lại lợi ích cho những người tham gia. Ở đó không
có khái niệm 1 dự án mà tài nguyên được cung cấp miễn phí.
- Tính toán ngang hàng thật sự bao gồm sự tích trữ và lấy lại, không phải tính
toán.
25
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Chương 2. LÝ THUYẾT CƠ BẢN VỀ LẬP LỊCH DỰA TRÊN
ĐỘ TIN CẬY
Trong phần này, tui tóm tắt lại mô hình cơ bản và các giả định, các kĩ thuật chịu lỗi
truyền thống, các kĩ thuật chịu lỗi dựa trên độ tin cậy cho tính toán tình nguyên 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.
2.1 Mô hình cơ bản và các giả định
Mô hình tính toán. Trong luận văn này, tui giả sử một mô hình chủ khách dựa trên
hàng đợi công việc, mô hình này được dùng trong tất cả các hệ thống tính toán tình
nguyện thực tế hiện nay, thêm vào đó là trong nhiều các hệ thống lưới, các hệ thống
metacomputing, và toàn bộ các hệ thống tính toán song song dựa trên mạng diện
rộng khác. Trong mô hình này một tính toán được chia vào thành vào một dãy các
lô, mỗi lô bao gồm nhiều các đối tượng công việc độc lập nhau [1]. Tại thời điểm
bắt đầu của mỗi lô, những đối tượng công việc này được đặt vào trong một hàng đợi
công việc bởi nút chủ, và sau đó được phân phối đến các nút máy trạm đã đăng kí
gia nhập vào máy tính tình nguyện để thực thi chúng song song và rồi trả về kết quả
của chúng đến máy chủ khi chúng kết thúc nhiệm vụ tính toán. Khi máy chủ đã tập
hợp được các kết quả cho tất cả các đối tượng công việc, nó sẽ tạo ra một lô các đối
tượng công việc tiếp (có thể dùng dữ liệu từ các kết quả của lô hiện tại), đặt chúng
vào trong hàng đợi công việc, và lập lại điều này cho toàn bộ xử lý. Trong mô hình
này, tui cũng giả sử rằng mọi nhiệm vụ có kích cỡ giống nhau.
Một giải thích cho mô hình này được chỉ đinh trong hình 2-1.
26
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hình 2-1. Mô hình chủ khách
Tỉ lệ lỗi. Chúng ta định nghĩa tỉ lệ lỗi, , là tỉ số của các kết quả lỗi hay các lỗi so
với các kết quả cuối cùng được chấp nhận tại cuối của nhóm. Cách thứ hai, chúng ta
cũng có thể định nghĩa nó là xác suất của từng kết quả cuối cùng riêng biệt là lỗi,
như vậy về trung bình, số lượng các lỗi được mong đợi trong một nhóm N các kết
quả được cho bởi . Để đơn giản, tui giả sử rằng các nhóm công việc là độc lập
lẫn nhau, do đó các lỗi trong một nhóm không ảnh hưởng lẫn nhau. Xa hơn, trong
thiết kế các kĩ thuật của tôi, tui giả sử rằng có một tỉ lệ lỗi chấp nhận được là khác
không, , và nhằm làm cho tỉ lệ lỗi thấp hơn nó. Một vài thuật toán “chịu lỗi tự
nhiên” như là các thuật toán di truyền, xuất video, và một vài các ứng dụng thống
kê có thể cho phép có một phân số lớn liên quan (1% hay nhiều hơn) các kết quả
cuối cùng là lỗi, và vì vậy có tỉ lệ lỗi chấp nhận cao. Trong các ứng dụng khác
không cho phép bất cứ lỗi nào tại tất cả các kết quả, phải được thiết lập để làm
cho xác suất lấy được bất cứ nỗi nào tại tất cả các kết quả cuối cùng là tương đối
nhỏ. Cho ví dụ, Giả sử rằng một tính toán có 10 lô mỗi lô có 100 đối tượng công
việc riêng biệt và mỗi lô này phụ thuộc vào nhau do đó một kết quả lỗi trong bất cứ
nhóm nào trong 10 lô sẽ là nguyên nhân của toàn bộ tính toán sai. Trong trường hợp
này, để làm cho xác suất của toàn bộ tính toán là lỗi, P (lỗi), kém hơn 1%, tỉ lệ lỗi ,
tỉ lệ xác suất của một kết quả riêng biệt bị lỗi, phải không lớn hơn:
27
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Kẻ phá hoại. Chúng ta giả sử rằng một phân số mắc lỗi, f, của toàn bộ máy trạm, P,
là các kẻ phá hoại. Nút chủ (nút mà chúng ta giả sử là tin cậy) có thể không biết giá
trị thực sự của f, nhưng được cho phép giả định một cận trên của nó, do đó không có
sự đảm bảo cần được làm nếu phân số mắc lỗi thực lớn hơn cận trên giả định.
Để đơn giản, chúng ta giả định rằng tất cả các máy trạm, bao gồm cả các máy phá
hoại, chạy chính xác với tốc độ giống nhau, để mà các đối tượng công việc là giống
nhau và được phân bố ngẫu nhiên giữa các máy trạm và các máy phá hoại. Vì vậy,
mỗi kết quả chúng ta nhận được là bằng giống như là đến từ bất cứ máy trạm nào, tỉ
lệ lỗi gốc - nghĩa là tỉ lệ lỗi được mong đợi mà không phải chịu đựng lỗi đơn giản là
f.
Tỉ lệ phá hoại và sự cấu kết. Cho đơn giản, chúng ta làm mỗi máy phá hoại theo
cách Bernoulli với một xác suất s cho một kết quả lỗi, và chúng ta giả sử
rằng s, được gọi là tỷ lệ phá hoại, là một hằng số theo thời gian và giống nhau cho
tất cả các máy phá hoại.
Chú ý rằng trong giả sử này, các máy trạm và phá hoại là độc lập lẫn nhau và không
giao tiếp với nhau. Đặc biệt, trong trường hợp ở đó các máy phá hoại không luôn
cho kết quả sai, chúng ta giả sử rằng các máy phá hoại không tán thành cho kết quả
sai, nhưng quyết định làm là độc lập.
Tuy nhiên, nếu hai hay nhiều máy phá hoại xuất hiện quyết định cho kết quả sai
cho một thực thể công việc đặc biệt, chúng ta sẽ giả sử rằng các trả lời sai của
chúng phù hợp, trừ trường hợp đã định khác. Điều này cho phép các máy phá hoại
biểu quyết cùng ...
Download miễn phí Luận văn 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
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ẬY25
2.1 Mô hình cơbản và các giả định.25 4
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ẬY44
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
sánh với tính toán lưới và tính toán ngang hàng1.3.4.1 Tính toán lưới
Tính toán lưới và Tính toán tình nguyện giống nhau ở chỗ cùng sử dụng nhiều máy
tính kết nối với nhau để thực hiện một công việc chung. Tuy nhiên, tính toán lưới
không có một máy chủ tập trung mà được phân thành các cụm nhỏ, mỗi cụm nhỏ ấy
có thể lại được phân chia nhỏ hơn và đơn vị nhỏ nhất là các PC thông thường, với
nhiệm vụ là tính toán và trả về kết quả. Liên tưởng tính toán lưới với sự tham chiếu
tới việc chia sẻ những tài nguyên tính toán bên trong và giữa các tổ chức.
- Mỗi tổ chức có thể đóng vai trò là người sản xuất hay khách hàng của tài
nguyên (giống như trong lưới điện, các công ty điện năng có thể mua hay bán
năng lượng từ các công ty khác, phù hợp với yêu cầu biến đổi).
- Các tổ chức chịu trách nhiệm qua lại, nếu 1 tổ chức cư xử không đúng, những tổ
chức khác có thể từ chối hợp tác, chia sẻ tài nguyên với họ và ngược lại.
Như vậy, tính toán lưới có tính đến trách nhiệm và không có tính che giấu. Những
người tham gia phải chịu trách nhiệm về các kết quả, các xung đột, sai sót… (điểm
khác nhau cơ bản với tính toán tình nguyện).
1.3.4.2 Tính toán ngang hàng
Điểm khác nhau cơ bản nhất là tính toán ngang hàng không hề có server. Nó chỉ
đơn thuần gồm các PC kết nối với nhau và không có cái nào làm chủ. Trong đó, các
file và dữ liệu khác được trao đổi giữa các “máy ngang hàng” (ví dụ như các PCs)
mà không liên can gì tới máy chủ trung tâm. Nó khác với tính toán tình nguyện:
24
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
- Tính toán tình nguyện có những máy chủ trung tâm. Điển hình là không có
truyền thông ngang hàng.
- Tính toán ngang hàng mang lại lợi ích cho những người tham gia. Ở đó không
có khái niệm 1 dự án mà tài nguyên được cung cấp miễn phí.
- Tính toán ngang hàng thật sự bao gồm sự tích trữ và lấy lại, không phải tính
toán.
25
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Chương 2. LÝ THUYẾT CƠ BẢN VỀ LẬP LỊCH DỰA TRÊN
ĐỘ TIN CẬY
Trong phần này, tui tóm tắt lại mô hình cơ bản và các giả định, các kĩ thuật chịu lỗi
truyền thống, các kĩ thuật chịu lỗi dựa trên độ tin cậy cho tính toán tình nguyên 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.
2.1 Mô hình cơ bản và các giả định
Mô hình tính toán. Trong luận văn này, tui giả sử một mô hình chủ khách dựa trên
hàng đợi công việc, mô hình này được dùng trong tất cả các hệ thống tính toán tình
nguyện thực tế hiện nay, thêm vào đó là trong nhiều các hệ thống lưới, các hệ thống
metacomputing, và toàn bộ các hệ thống tính toán song song dựa trên mạng diện
rộng khác. Trong mô hình này một tính toán được chia vào thành vào một dãy các
lô, mỗi lô bao gồm nhiều các đối tượng công việc độc lập nhau [1]. Tại thời điểm
bắt đầu của mỗi lô, những đối tượng công việc này được đặt vào trong một hàng đợi
công việc bởi nút chủ, và sau đó được phân phối đến các nút máy trạm đã đăng kí
gia nhập vào máy tính tình nguyện để thực thi chúng song song và rồi trả về kết quả
của chúng đến máy chủ khi chúng kết thúc nhiệm vụ tính toán. Khi máy chủ đã tập
hợp được các kết quả cho tất cả các đối tượng công việc, nó sẽ tạo ra một lô các đối
tượng công việc tiếp (có thể dùng dữ liệu từ các kết quả của lô hiện tại), đặt chúng
vào trong hàng đợi công việc, và lập lại điều này cho toàn bộ xử lý. Trong mô hình
này, tui cũng giả sử rằng mọi nhiệm vụ có kích cỡ giống nhau.
Một giải thích cho mô hình này được chỉ đinh trong hình 2-1.
26
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Hình 2-1. Mô hình chủ khách
Tỉ lệ lỗi. Chúng ta định nghĩa tỉ lệ lỗi, , là tỉ số của các kết quả lỗi hay các lỗi so
với các kết quả cuối cùng được chấp nhận tại cuối của nhóm. Cách thứ hai, chúng ta
cũng có thể định nghĩa nó là xác suất của từng kết quả cuối cùng riêng biệt là lỗi,
như vậy về trung bình, số lượng các lỗi được mong đợi trong một nhóm N các kết
quả được cho bởi . Để đơn giản, tui giả sử rằng các nhóm công việc là độc lập
lẫn nhau, do đó các lỗi trong một nhóm không ảnh hưởng lẫn nhau. Xa hơn, trong
thiết kế các kĩ thuật của tôi, tui giả sử rằng có một tỉ lệ lỗi chấp nhận được là khác
không, , và nhằm làm cho tỉ lệ lỗi thấp hơn nó. Một vài thuật toán “chịu lỗi tự
nhiên” như là các thuật toán di truyền, xuất video, và một vài các ứng dụng thống
kê có thể cho phép có một phân số lớn liên quan (1% hay nhiều hơn) các kết quả
cuối cùng là lỗi, và vì vậy có tỉ lệ lỗi chấp nhận cao. Trong các ứng dụng khác
không cho phép bất cứ lỗi nào tại tất cả các kết quả, phải được thiết lập để làm
cho xác suất lấy được bất cứ nỗi nào tại tất cả các kết quả cuối cùng là tương đối
nhỏ. Cho ví dụ, Giả sử rằng một tính toán có 10 lô mỗi lô có 100 đối tượng công
việc riêng biệt và mỗi lô này phụ thuộc vào nhau do đó một kết quả lỗi trong bất cứ
nhóm nào trong 10 lô sẽ là nguyên nhân của toàn bộ tính toán sai. Trong trường hợp
này, để làm cho xác suất của toàn bộ tính toán là lỗi, P (lỗi), kém hơn 1%, tỉ lệ lỗi ,
tỉ lệ xác suất của một kết quả riêng biệt bị lỗi, phải không lớn hơn:
27
Nguyễn Quang Hòa - Lớp CH CNTT 2006 – 2008
Kẻ phá hoại. Chúng ta giả sử rằng một phân số mắc lỗi, f, của toàn bộ máy trạm, P,
là các kẻ phá hoại. Nút chủ (nút mà chúng ta giả sử là tin cậy) có thể không biết giá
trị thực sự của f, nhưng được cho phép giả định một cận trên của nó, do đó không có
sự đảm bảo cần được làm nếu phân số mắc lỗi thực lớn hơn cận trên giả định.
Để đơn giản, chúng ta giả định rằng tất cả các máy trạm, bao gồm cả các máy phá
hoại, chạy chính xác với tốc độ giống nhau, để mà các đối tượng công việc là giống
nhau và được phân bố ngẫu nhiên giữa các máy trạm và các máy phá hoại. Vì vậy,
mỗi kết quả chúng ta nhận được là bằng giống như là đến từ bất cứ máy trạm nào, tỉ
lệ lỗi gốc - nghĩa là tỉ lệ lỗi được mong đợi mà không phải chịu đựng lỗi đơn giản là
f.
Tỉ lệ phá hoại và sự cấu kết. Cho đơn giản, chúng ta làm mỗi máy phá hoại theo
cách Bernoulli với một xác suất s cho một kết quả lỗi, và chúng ta giả sử
rằng s, được gọi là tỷ lệ phá hoại, là một hằng số theo thời gian và giống nhau cho
tất cả các máy phá hoại.
Chú ý rằng trong giả sử này, các máy trạm và phá hoại là độc lập lẫn nhau và không
giao tiếp với nhau. Đặc biệt, trong trường hợp ở đó các máy phá hoại không luôn
cho kết quả sai, chúng ta giả sử rằng các máy phá hoại không tán thành cho kết quả
sai, nhưng quyết định làm là độc lập.
Tuy nhiên, nếu hai hay nhiều máy phá hoại xuất hiện quyết định cho kết quả sai
cho một thực thể công việc đặc biệt, chúng ta sẽ giả sử rằng các trả lời sai của
chúng phù hợp, trừ trường hợp đã định khác. Điều này cho phép các máy phá hoại
biểu quyết cùng ...