Download Luận văn Nghiên cứu giải thuật định thời cho các bài toán song song, độc lập trên môi trường tính toán lưới
Mục lục
Danh mục các hình . 4
Danh mục các bảng . 5
Danh mục thuật ngữ, từviết tắt . 6
Chương 1. Giới thiệu . 7
Chương 2. Công NghệGrid Computing – Tính toán lưới . 9
2.1 Giới thiệu công nghệGrid Computing – Tính toán lưới . 9
2.2 Những động lực thúc đẩy việc phát triển của tính toán lưới . 10
2.3 Cấu trúc một hệthống lưới . 11
2.4 Một sốdựán thực tếvềGrid Computing . 13
Chương 3. Những nghiên cứu vềlập lịch trên môi trường tính toán lưới . 14
3.1 Giới thiệu bài toán lập lịch . 14
3.2 Các ứng dụng song song, độc lập . 14
3.3 Các hướng nghiên cứu trong bài toán lập lịch . 15
3.4 Lập lịch theo hiệu năng hệthống . 16
3.4.1 OLB (Opportunistic Load Balancing). 16
3.4.2 MET (Minimum Execution Time) . 16
3.4.3 MCT (Minimum Completion Time) . 17
3.4.4 Thuật giải Min – Min . 18
3.4.5 Thuật giải Max-Min . 19
3.4.6 Thuật giải Sufferage . 21
3.4.7 Thuật giải XSufferage . 22
3.4.8 Các thuật giải điều phối cho các ứng dụng vừa và nhỏ. 23
3.5 Lập lịch theo hiệu năng kinh tế. 23
3.5.1 Time Minimization . 24
3.5.2 Cost Minimization . 24
3.5.3 DBC (Deadline and Budget constrained scheduling) . 25
3.5.4 HRED (Highest Rank Earliest Deadline) . 26
3.5.5 Các mô hình thường áp dụng trong bài toán lập lịch theo hiệu năng kinh tế. 27
3.5.6 Lập lịch mô phỏng cơchếthịtrường . 29
3.6 Một sốdựán vềlập lịch đã được triển khai thực tế. 32
Chương 4. Các thuật giải định thời cho ứng dụng song song, độc lập trên môi trường lưới . 34
4.1 Mô hình hoạt động của hệthống . 34
4.2 Mô hình ứng dụng . 36
4.3 Những điểm chưa phù hợp với hoàn cảnh Việt Nam của các thuật giải đã có . 38
4.3.1 Hiệu suất thực thi kém . 38
4.3.2 Thời gian thực thi ứng dụng cao . 40
4.4 Hướng giải quyết của luận văn . 40
4.5 Các thuật giải ởSystem Broker . 41
4.5.1 Thuật giải điều phối ADeadline . 42
4.5.2 Thuật giải điều phối ACostPI . 44
4.5.3 Thuật giải điều phối ABenefit . 45
4.6 Thuật giải điều phối công việc tại một máy tính cụm . 48
4.7 Các đềxuất cho Provider – Nhà cung cấp . 51
4.7.1 Chào giá COST_MAX . 52
4.7.2 Chào giá COST_MIN . 53
4.7.3 Adaptive Provider . 53
Chương 5. ThửNghiệm Và Đánh Giá . 58
5.1 So sánh các thuật giải đềxuất . 58
5.2 So sánh giữa các phương án chào giá của provider . 67
5.2.1 So sánh giữa chào giá MAX và chào giá MIN . 68
5.2.2 So sánh giữa chào giá MIN và ADAPTIVE . 69
Chương 6. Tổng Kết & Hướng Phát Triển . 71
Tài Liệu Tham Khảo . 73
Để tải bản DOC Đầy Đủ 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í
Chương 1. Giới thiệu
Tính toán lưới (Grid Computing [1]) là một lĩnh vực được nghiên cứu và phát
triển mạnh mẽ trong thời gian gần đây. Môi trường tính toán lưới cho phép kết hợp
các hệ thống xử lý với nhau để giải quyết một cách hiệu quả những nhu cầu ngày
càng cao của con người. Ưu điểm của công nghệ lưới so với các công nghệ ra đời
trước đó là khả năng kết hợp các tài nguyên thuộc những tổ chức khác nhau, phân
tán rộng về mặt địa lý và không đòi hỏi các nguồn tài nguyên này phải tương đồng
về cấu trúc cũng như năng lực xử lý.
Bài toán lập lịch trên môi trường tính toán lưới là một lĩnh vực đòi hỏi nhiều
công sức nghiên cứu và còn rất nhiều thử thách. Quá trình lập lịch chịu trách nhiệm
quyết định thời điểm và tài nguyên đảm nhận thực thi ứng dụng do đó ảnh hưởng
trực tiếp đến hiệu năng của hệ thống. Môi trường lưới là một môi trường biến động
về số lượng cũng như năng lực các nguồn tài nguyên; do đó những nghiên cứu về
lập lịch trên môi trường này có nhiều đặc điểm riêng so với các môi trường khác.
Lớp bài toán được nghiên cứu và triển khai nhiều trên môi trường lưới là lớp
ứng dụng gồm các tác vụ song song và độc lập với nhau (ví dụ như lớp ứng dụng
parameter sweep [11] gồm các tác vụ thực thi cùng một chức năng tính toán nhưng
trên các bộ tham số đầu vào khác nhau). Đây là một lớp ứng dụng phát huy hiệu quả
cao trên môi trường tính toán lưới; lớp ứng dụng này được thấy nhiều trong các lĩnh
vực như phân tích số liệu kinh tế, vật lý, sinh học …
Đã có nhiều nghiên cứu về lập lịch trên môi trường lưới cho lớp ứng dụng
song song độc lập, tuy nhiên các nghiên cứu này chủ yếu nhắm đến các ứng dụng
rất lớn nên có một số đặc điểm chưa phù hợp với mô hình thực tế tại Việt Nam.
Luận văn tập trung nghiên cứu lập lịch trong điều kiện môi trường lưới có một số
lượng lớn các ứng dụng vừa và nhỏ, có thể thực thi toàn bộ một ứng dụng trên một
cụm tài nguyên tính toán như máy tính cụm (clusters). Vấn đề được nghiên cứu
trong luận văn là bài toán lập lịch theo hiệu năng kinh tế, mỗi ứng dụng chịu chi
8
phối bởi hai ràng buộc chính là ngân sách thực thi (budget) và thời hạn hoàn tất
(deadline).
Ba giải thuật định thời ADeadline, ACostPI và ABenefit được phát triển trong
luận văn nhằm thỏa mãn cho các tiêu chí khác nhau của hệ thống. Mô hình lý thuyết
và các kết quả thực nghiệm cho thấy những giải thuật này phù hợp hơn với mô hình
các ứng dụng tại Việt Nam.
Luận văn cũng đề xuất mô hình nhà cung cấp - provider, quản lý phân khu các
nguồn tài nguyên tính toán. Mô hình này giúp giảm tải cho hệ thống cũng như hạ
thấp độ phức tạp của giải thuật lập lịch. Ngoài ra, các phương án hoạt động khác
nhau của provider được phân tích, kiểm nghiệm để tìm ra phương án phù hợp.
Các giải thuật được đề xuất trong luận văn hoàn toàn có thể được tích hợp để
hoạt động bên trong các bộ điều phối (broker) có sẵn của các hệ thống lưới hiện
nay.
Phần còn lại của luận văn được chia thành 5 chương: Chương 2 giới thiệu về
công nghệ Grid Computing - tính toán lưới, các dự án Grid đang được nghiên cứu
và triển khai. Chương 3 giới thiệu về đặc điểm và những hướng tiếp cận của bài
toán lập lịch cho các ứng dụng song song, độc lập trên môi trường lưới. Chương 4
trình bày mô hình hệ thống và những giải thuật định thời được luận văn đề xuất cho
các ứng dụng trên môi trường lưới. Các thử nghiệm và phân tích được trình bày ở
chương 5. Chương 6 là những đánh giá, kết luận và hướng phát triển của đề tài.
...
Download miễn phí Luận văn Nghiên cứu giải thuật định thời cho các bài toán song song, độc lập trên môi trường tính toán lưới
Mục lục
Danh mục các hình . 4
Danh mục các bảng . 5
Danh mục thuật ngữ, từviết tắt . 6
Chương 1. Giới thiệu . 7
Chương 2. Công NghệGrid Computing – Tính toán lưới . 9
2.1 Giới thiệu công nghệGrid Computing – Tính toán lưới . 9
2.2 Những động lực thúc đẩy việc phát triển của tính toán lưới . 10
2.3 Cấu trúc một hệthống lưới . 11
2.4 Một sốdựán thực tếvềGrid Computing . 13
Chương 3. Những nghiên cứu vềlập lịch trên môi trường tính toán lưới . 14
3.1 Giới thiệu bài toán lập lịch . 14
3.2 Các ứng dụng song song, độc lập . 14
3.3 Các hướng nghiên cứu trong bài toán lập lịch . 15
3.4 Lập lịch theo hiệu năng hệthống . 16
3.4.1 OLB (Opportunistic Load Balancing). 16
3.4.2 MET (Minimum Execution Time) . 16
3.4.3 MCT (Minimum Completion Time) . 17
3.4.4 Thuật giải Min – Min . 18
3.4.5 Thuật giải Max-Min . 19
3.4.6 Thuật giải Sufferage . 21
3.4.7 Thuật giải XSufferage . 22
3.4.8 Các thuật giải điều phối cho các ứng dụng vừa và nhỏ. 23
3.5 Lập lịch theo hiệu năng kinh tế. 23
3.5.1 Time Minimization . 24
3.5.2 Cost Minimization . 24
3.5.3 DBC (Deadline and Budget constrained scheduling) . 25
3.5.4 HRED (Highest Rank Earliest Deadline) . 26
3.5.5 Các mô hình thường áp dụng trong bài toán lập lịch theo hiệu năng kinh tế. 27
3.5.6 Lập lịch mô phỏng cơchếthịtrường . 29
3.6 Một sốdựán vềlập lịch đã được triển khai thực tế. 32
Chương 4. Các thuật giải định thời cho ứng dụng song song, độc lập trên môi trường lưới . 34
4.1 Mô hình hoạt động của hệthống . 34
4.2 Mô hình ứng dụng . 36
4.3 Những điểm chưa phù hợp với hoàn cảnh Việt Nam của các thuật giải đã có . 38
4.3.1 Hiệu suất thực thi kém . 38
4.3.2 Thời gian thực thi ứng dụng cao . 40
4.4 Hướng giải quyết của luận văn . 40
4.5 Các thuật giải ởSystem Broker . 41
4.5.1 Thuật giải điều phối ADeadline . 42
4.5.2 Thuật giải điều phối ACostPI . 44
4.5.3 Thuật giải điều phối ABenefit . 45
4.6 Thuật giải điều phối công việc tại một máy tính cụm . 48
4.7 Các đềxuất cho Provider – Nhà cung cấp . 51
4.7.1 Chào giá COST_MAX . 52
4.7.2 Chào giá COST_MIN . 53
4.7.3 Adaptive Provider . 53
Chương 5. ThửNghiệm Và Đánh Giá . 58
5.1 So sánh các thuật giải đềxuất . 58
5.2 So sánh giữa các phương án chào giá của provider . 67
5.2.1 So sánh giữa chào giá MAX và chào giá MIN . 68
5.2.2 So sánh giữa chào giá MIN và ADAPTIVE . 69
Chương 6. Tổng Kết & Hướng Phát Triển . 71
Tài Liệu Tham Khảo . 73
Để tải bản DOC Đầy Đủ 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:
7Chương 1. Giới thiệu
Tính toán lưới (Grid Computing [1]) là một lĩnh vực được nghiên cứu và phát
triển mạnh mẽ trong thời gian gần đây. Môi trường tính toán lưới cho phép kết hợp
các hệ thống xử lý với nhau để giải quyết một cách hiệu quả những nhu cầu ngày
càng cao của con người. Ưu điểm của công nghệ lưới so với các công nghệ ra đời
trước đó là khả năng kết hợp các tài nguyên thuộc những tổ chức khác nhau, phân
tán rộng về mặt địa lý và không đòi hỏi các nguồn tài nguyên này phải tương đồng
về cấu trúc cũng như năng lực xử lý.
Bài toán lập lịch trên môi trường tính toán lưới là một lĩnh vực đòi hỏi nhiều
công sức nghiên cứu và còn rất nhiều thử thách. Quá trình lập lịch chịu trách nhiệm
quyết định thời điểm và tài nguyên đảm nhận thực thi ứng dụng do đó ảnh hưởng
trực tiếp đến hiệu năng của hệ thống. Môi trường lưới là một môi trường biến động
về số lượng cũng như năng lực các nguồn tài nguyên; do đó những nghiên cứu về
lập lịch trên môi trường này có nhiều đặc điểm riêng so với các môi trường khác.
Lớp bài toán được nghiên cứu và triển khai nhiều trên môi trường lưới là lớp
ứng dụng gồm các tác vụ song song và độc lập với nhau (ví dụ như lớp ứng dụng
parameter sweep [11] gồm các tác vụ thực thi cùng một chức năng tính toán nhưng
trên các bộ tham số đầu vào khác nhau). Đây là một lớp ứng dụng phát huy hiệu quả
cao trên môi trường tính toán lưới; lớp ứng dụng này được thấy nhiều trong các lĩnh
vực như phân tích số liệu kinh tế, vật lý, sinh học …
Đã có nhiều nghiên cứu về lập lịch trên môi trường lưới cho lớp ứng dụng
song song độc lập, tuy nhiên các nghiên cứu này chủ yếu nhắm đến các ứng dụng
rất lớn nên có một số đặc điểm chưa phù hợp với mô hình thực tế tại Việt Nam.
Luận văn tập trung nghiên cứu lập lịch trong điều kiện môi trường lưới có một số
lượng lớn các ứng dụng vừa và nhỏ, có thể thực thi toàn bộ một ứng dụng trên một
cụm tài nguyên tính toán như máy tính cụm (clusters). Vấn đề được nghiên cứu
trong luận văn là bài toán lập lịch theo hiệu năng kinh tế, mỗi ứng dụng chịu chi
8
phối bởi hai ràng buộc chính là ngân sách thực thi (budget) và thời hạn hoàn tất
(deadline).
Ba giải thuật định thời ADeadline, ACostPI và ABenefit được phát triển trong
luận văn nhằm thỏa mãn cho các tiêu chí khác nhau của hệ thống. Mô hình lý thuyết
và các kết quả thực nghiệm cho thấy những giải thuật này phù hợp hơn với mô hình
các ứng dụng tại Việt Nam.
Luận văn cũng đề xuất mô hình nhà cung cấp - provider, quản lý phân khu các
nguồn tài nguyên tính toán. Mô hình này giúp giảm tải cho hệ thống cũng như hạ
thấp độ phức tạp của giải thuật lập lịch. Ngoài ra, các phương án hoạt động khác
nhau của provider được phân tích, kiểm nghiệm để tìm ra phương án phù hợp.
Các giải thuật được đề xuất trong luận văn hoàn toàn có thể được tích hợp để
hoạt động bên trong các bộ điều phối (broker) có sẵn của các hệ thống lưới hiện
nay.
Phần còn lại của luận văn được chia thành 5 chương: Chương 2 giới thiệu về
công nghệ Grid Computing - tính toán lưới, các dự án Grid đang được nghiên cứu
và triển khai. Chương 3 giới thiệu về đặc điểm và những hướng tiếp cận của bài
toán lập lịch cho các ứng dụng song song, độc lập trên môi trường lưới. Chương 4
trình bày mô hình hệ thống và những giải thuật định thời được luận văn đề xuất cho
các ứng dụng trên môi trường lưới. Các thử nghiệm và phân tích được trình bày ở
chương 5. Chương 6 là những đánh giá, kết luận và hướng phát triển của đề tài.
...