Download Luận văn Nghiên cứu và phát triển giải thuật định thời cho lớp bài toán Parameter Sweep trên môi trường tính toán lưới
Mục lục
Chương 1. GIỚI THIỆU . 1
Chương 2. NHU CẦU TÍNH TOÁN VÀ CÔNG NGHỆLƯỚI . 3
2.1. Nhu cầu tính toán và giải pháp . 3
2.2. Công nghệlưới . 4
2.3. Ứng dụng parameter sweep . 6
Chương 3. ĐỊNH THỜI TRÊN MÔI TRƯỜNG TÍNH TOÁN LƯỚI . 8
3.1. Định thời trên lưới . 8
3.2. Một sốdựán và sản phẩm . 9
3.3. Các giải thuật định thời liên quan . 11
3.3.1. MET (Minimum Excecution Time) . 12
3.3.2. MCT (Minimum Completion Time) . 13
3.3.3. RR (Round-robin) . 13
3.3.4. DFPLTF (Dynamic Fastest Processor to Largest Task First) . 14
3.3.5. Min-Min . 14
3.3.6. Max-Min . 16
3.3.7. Duplex . 17
3.3.8. Partitioning . 17
3.3.9. Sufferage . 17
3.3.10. XSufferage . 19
Chương 4. GIẢI THUẬT ĐỊNH THỜI CHO ỨNG DỤNG PARAMETER SWEEP . 22
4.1. Mô hình bài toán . 22
4.2. Thuật giải SufMin . 24
4.3. Thuật giải DMin-Min . 27
4.4. Thuật giải DMax-Min . 28
4.5. Thuật giải DSufferage . 29
Chương 5. THỬNGHIỆM VÀ ĐÁNH GIÁ . 33
Chương 6. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN . 41
TÀI LIỆU THAM KHẢO . 43
Để 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í
Chương 1. GIỚI THIỆU
Máy tính ngày nay được ứng dụng rộng rãi vào nhiều lĩnh vực với nhiều
chức năng khác nhau, trong đó có việc phục vụ nhu cầu tính toán. Các bài toán
có độ phức tạp cao ngày càng nhiều và đòi hỏi khả năng tính toán mạnh của máy
tính.
Nhằm đáp ứng nhu cầu tính toán này, kỹ thuật xử lý song song ra đời với
ý tưởng chính là sử dụng nhiều bộ xử lý để cùng giải quyết một vấn đề. Các máy
tính đa xử lý (multiprocessor) cùng với các hệ thống máy tính cụm (cluster) và
cả lưới tính toán (grid) đều được phát triển theo hướng này.
Lưới tính toán cho phép chia sẻ, thu thập và chọn lọc các tài nguyên phân
tán nhằm giải quyết các bài toán lớn. Tuy nhiên, việc tổng hợp, quản lý tài
nguyên và phân phối tài nguyên cho các dịch vụ và các ứng dụng là một thử
thách lớn vì các nguồn tài nguyên rất hỗn tạp, phân tán và các tác vụ thường chia
sẻ các tập tin (file) dữ liệu dùng chung.
Đề tài này quan tâm đến lớp bài toán parameter sweep, đây là dạng bài
toán thực hiện cùng một đoạn mã chương trình nhiều lần và sử dụng tập duy
nhất các giá trị tham số đầu vào [15]. Việc định thời cho lớp bài toán này đã
được nghiên cứu nhiều (xem [8] [9] [15] [18]). Xuất phát từ thực tế là phần lớn
các bài toán có kích thước không lớn, đề tài tập trung vào các ứng dụng
parameter sweep có kích thước trung bình và nhỏ để có thể xếp lịch chạy một
ứng dụng trên một nút lưới (một cụm máy tính). Việc này có ưu điểm về mặt
truy xuất, đồng bộ dữ liệu và dễ trong việc quản lý.
Đề tài này đề xuất bốn giải thuật định thời SufMin, DMin-Min, DMax-
Min và DSufferage hướng đến các tiêu chí sau:
(1) Giảm thiểu thời gian thực hiện công việc tính toán để phân bổ các tài
nguyên cho các ứng dụng parameter sweep (được đánh giá thông qua độ
phức tạp của giải thuật).
(2) Thời gian hoàn thành của ứng dụng là nhỏ.
2
(3) Phân toàn bộ một ứng dụng chạy trên một nút lưới để tối ưu thời gian
truy xuất dữ liệu của ứng dụng và dễ quản lý.
Các giải thuật SufMin, DMin-Min, DMax-Min và DSufferage đều có ưu
điểm là có độ phức tạp của giải thuật nhỏ so với một số giải thuật tương tự hiện
có như Min-Min, Max-Min, Sufferage, XSufferage… Kết quả thử nghiệm còn
cho thấy thời gian hoàn thành trung bình của các ứng dụng khi áp dụng các giải
thuật cải tiến đều nhỏ hơn so với các giải thuật Max-Min, Min-Min, Sufferage.
Các giải thuật đề xuất trong luận văn có thể áp dụng trong các bộ định
thời (lập lịch) cho các lưới tính toán chuyên phục vụ các bài toán parameter
sweep. Đối với lưới tính toán phục vụ cho các ứng dụng thuộc cả lớp bài toán
parameter sweep và không thuộc lớp bài toán này thì giải thuật định thời cần
được đánh giá và nghiên cứu thêm.
Phần còn lại của luận văn được tổ chức thành 5 chương. Chương 2 nói về
nhu cầu tính toán và công nghệ lưới. Chương 3 trình bày vấn đề định thời trên
môi trường tính toán lưới. Chương 4 trình bày các giải thuật định thời SufMin,
DMin-Min, DMax-Min, DSufferage cho ứng dụng parameter sweep. Phần thử
nghiệm và đánh giá được trình bày ở chương 5 và cuối cùng là kết luận và
hướng phát triển được trình bày ở chương 6.
...
Download miễn phí Luận văn Nghiên cứu và phát triển giải thuật định thời cho lớp bài toán Parameter Sweep trên môi trường tính toán lưới
Mục lục
Chương 1. GIỚI THIỆU . 1
Chương 2. NHU CẦU TÍNH TOÁN VÀ CÔNG NGHỆLƯỚI . 3
2.1. Nhu cầu tính toán và giải pháp . 3
2.2. Công nghệlưới . 4
2.3. Ứng dụng parameter sweep . 6
Chương 3. ĐỊNH THỜI TRÊN MÔI TRƯỜNG TÍNH TOÁN LƯỚI . 8
3.1. Định thời trên lưới . 8
3.2. Một sốdựán và sản phẩm . 9
3.3. Các giải thuật định thời liên quan . 11
3.3.1. MET (Minimum Excecution Time) . 12
3.3.2. MCT (Minimum Completion Time) . 13
3.3.3. RR (Round-robin) . 13
3.3.4. DFPLTF (Dynamic Fastest Processor to Largest Task First) . 14
3.3.5. Min-Min . 14
3.3.6. Max-Min . 16
3.3.7. Duplex . 17
3.3.8. Partitioning . 17
3.3.9. Sufferage . 17
3.3.10. XSufferage . 19
Chương 4. GIẢI THUẬT ĐỊNH THỜI CHO ỨNG DỤNG PARAMETER SWEEP . 22
4.1. Mô hình bài toán . 22
4.2. Thuật giải SufMin . 24
4.3. Thuật giải DMin-Min . 27
4.4. Thuật giải DMax-Min . 28
4.5. Thuật giải DSufferage . 29
Chương 5. THỬNGHIỆM VÀ ĐÁNH GIÁ . 33
Chương 6. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN . 41
TÀI LIỆU THAM KHẢO . 43
Để 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:
1Chương 1. GIỚI THIỆU
Máy tính ngày nay được ứng dụng rộng rãi vào nhiều lĩnh vực với nhiều
chức năng khác nhau, trong đó có việc phục vụ nhu cầu tính toán. Các bài toán
có độ phức tạp cao ngày càng nhiều và đòi hỏi khả năng tính toán mạnh của máy
tính.
Nhằm đáp ứng nhu cầu tính toán này, kỹ thuật xử lý song song ra đời với
ý tưởng chính là sử dụng nhiều bộ xử lý để cùng giải quyết một vấn đề. Các máy
tính đa xử lý (multiprocessor) cùng với các hệ thống máy tính cụm (cluster) và
cả lưới tính toán (grid) đều được phát triển theo hướng này.
Lưới tính toán cho phép chia sẻ, thu thập và chọn lọc các tài nguyên phân
tán nhằm giải quyết các bài toán lớn. Tuy nhiên, việc tổng hợp, quản lý tài
nguyên và phân phối tài nguyên cho các dịch vụ và các ứng dụng là một thử
thách lớn vì các nguồn tài nguyên rất hỗn tạp, phân tán và các tác vụ thường chia
sẻ các tập tin (file) dữ liệu dùng chung.
Đề tài này quan tâm đến lớp bài toán parameter sweep, đây là dạng bài
toán thực hiện cùng một đoạn mã chương trình nhiều lần và sử dụng tập duy
nhất các giá trị tham số đầu vào [15]. Việc định thời cho lớp bài toán này đã
được nghiên cứu nhiều (xem [8] [9] [15] [18]). Xuất phát từ thực tế là phần lớn
các bài toán có kích thước không lớn, đề tài tập trung vào các ứng dụng
parameter sweep có kích thước trung bình và nhỏ để có thể xếp lịch chạy một
ứng dụng trên một nút lưới (một cụm máy tính). Việc này có ưu điểm về mặt
truy xuất, đồng bộ dữ liệu và dễ trong việc quản lý.
Đề tài này đề xuất bốn giải thuật định thời SufMin, DMin-Min, DMax-
Min và DSufferage hướng đến các tiêu chí sau:
(1) Giảm thiểu thời gian thực hiện công việc tính toán để phân bổ các tài
nguyên cho các ứng dụng parameter sweep (được đánh giá thông qua độ
phức tạp của giải thuật).
(2) Thời gian hoàn thành của ứng dụng là nhỏ.
2
(3) Phân toàn bộ một ứng dụng chạy trên một nút lưới để tối ưu thời gian
truy xuất dữ liệu của ứng dụng và dễ quản lý.
Các giải thuật SufMin, DMin-Min, DMax-Min và DSufferage đều có ưu
điểm là có độ phức tạp của giải thuật nhỏ so với một số giải thuật tương tự hiện
có như Min-Min, Max-Min, Sufferage, XSufferage… Kết quả thử nghiệm còn
cho thấy thời gian hoàn thành trung bình của các ứng dụng khi áp dụng các giải
thuật cải tiến đều nhỏ hơn so với các giải thuật Max-Min, Min-Min, Sufferage.
Các giải thuật đề xuất trong luận văn có thể áp dụng trong các bộ định
thời (lập lịch) cho các lưới tính toán chuyên phục vụ các bài toán parameter
sweep. Đối với lưới tính toán phục vụ cho các ứng dụng thuộc cả lớp bài toán
parameter sweep và không thuộc lớp bài toán này thì giải thuật định thời cần
được đánh giá và nghiên cứu thêm.
Phần còn lại của luận văn được tổ chức thành 5 chương. Chương 2 nói về
nhu cầu tính toán và công nghệ lưới. Chương 3 trình bày vấn đề định thời trên
môi trường tính toán lưới. Chương 4 trình bày các giải thuật định thời SufMin,
DMin-Min, DMax-Min, DSufferage cho ứng dụng parameter sweep. Phần thử
nghiệm và đánh giá được trình bày ở chương 5 và cuối cùng là kết luận và
hướng phát triển được trình bày ở chương 6.
...