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

1 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.