Luận án tiến sĩ một số thuật toán lập lịch để phân phối tài nguyên trong hệ thống tính toán lưới 62 46 35 01

Luận án tiến sĩ toán học nghiên cứu một số thuật toán lập lịch để phân phối tài nguyên trong hệ thống tính toán lưới 62 46 35 01, phân tích chuyên sâu, xây dựng mô hình lý thuyết,

Trường đại học

Đại học Quốc gia Hà Nội

Người đăng

Ẩn danh

Thể loại

luận án tiến sĩ

2011

128
0
0

Phí lưu trữ

35 Point

Mục lục chi tiết

LỜI CAM ĐOAN

DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT

DANH MỤC CÁC BẢNG

DANH MỤC CÁC HÌNH VẼ

1. CHƯƠNG 1: TỔNG QUAN VỀ HỆ THỐNG TÍNH TOÁN LƯỚI

1.1. Giới thiệu chung

1.2. Hệ thống tính toán lưới là gì

1.3. Các mô hình tính toán lưới

1.4. Các thành phần chính của hệ thống tính toán lưới

1.5. So sánh mô hình tính toán lưới với một số mô hình tính toán khác

1.6. Những ứng dụng cơ bản của hệ thống tính toán lưới

1.7. Các công cụ hỗ trợ xây dựng hệ thống tính toán lưới

1.8. Một số hệ thống tính toán lưới

1.9. Các thách thức đối với mô hình tính toán lưới và một số vấn đề nghiên cứu

1.9.1. Các xu hướng trong tính toán

1.9.2. Một số hướng nghiên cứu

1.10. Mục tiêu của luận án

1.11. Các kết quả đã đạt được của luận án

2. CHƯƠNG 2: BÀI TOÁN LẬP LỊCH TRONG TÍNH TOÁN LƯỚI

2.1. Một số bài toán lập lịch truyền thống

2.1.1. Bài toán lập lịch trên hai máy và giải thuật gia công Johnson

2.1.2. Giải thuật xếp lịch heuristic

2.1.3. Phương pháp duyệt nhánh cận

2.1.4. Phương pháp qui hoạch động

2.1.5. Phương pháp làm mịn kết quả

2.1.6. Phương pháp Hung-ga-ri

2.2. Bài toán lập lịch trong hệ thống tính toán lưới

2.2.1. Phát biểu bài toán

2.2.2. Một số khó khăn trong lập lịch đối với hệ thống tính toán lưới

2.2.3. Một số cách tiếp cận

2.2.4. Độ khó của bài toán

2.3. Mô hình lập lịch trong hệ thống tính toán lưới

2.3.1. Các mô hình lập lịch trong hệ thống tính toán lưới

2.3.2. Mô hình Buyya lập lịch trong hệ thống tính toán lưới

2.3.3. Thực hiện công việc lập lịch trong hệ thống tính toán lưới

2.4. Kết luận chương 2

3. CHƯƠNG 3: MỘT SỐ GIẢI THUẬT CHO BÀI TOÁN LẬP LỊCH TRONG TÍNH TOÁN LƯỚI

3.1. Các giải thuật lập lịch tối ưu theo thời gian, chi phí

3.1.1. Giải thuật lập lịch tối ưu về thời gian

3.1.2. Giải thuật tối ưu về chi phí

3.1.3. Giải thuật tối ưu về thời gian - chi phí

3.2. Giải thuật tham lam

3.2.1. Các kết quả thử nghiệm

3.3. Giải thuật di truyền

3.3.1. Giới thiệu về giải thuật di truyền

3.3.2. Giải thuật di truyền trong lập lịch

3.3.3. Các kết quả thử nghiệm

3.4. Giải thuật tối ưu hóa theo nhóm bầy (PSO)

3.4.1. Giải thuật PSO

3.4.2. Giải thuật PSO cho bài toán lập lịch trong hệ thống tính toán lưới

3.4.3. Các kết quả thực nghiệm

3.5. Kết luận chương 3

4. CHƯƠNG 4: MÔ HÌNH HỆ THỐNG THỬ NGHIỆM

4.1. Giới thiệu về hệ thống thử nghiệm TestGrid

4.1.1. Kiến trúc chung của TestGrid

4.1.2. Mô tả chức năng bộ lập lịch

4.1.3. Thiết kế bộ lập lịch

4.1.4. Cơ chế lập lịch của TestGrid

4.1.5. Xử lý và chống lỗi

4.2. Bộ lập lịch của TestGrid với các giải thuật đề xuất

4.2.1. Mô hình triển khai thực nghiệm bộ lập lịch trên lưới

4.2.2. Yêu cầu tương thích giữa giải thuật lập lịch với khung phần mềm thực nghiệm

4.3. Kết luận chương 4

KẾT LUẬN CHUNG

DANH MỤC CÔNG TRÌNH KHOA HỌC CỦA TÁC GIẢ LIÊN QUAN ĐẾN LUẬN ÁN

TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng quan về thuật toán lập lịch phân phối tài nguyên trong tính toán lưới

Thuật toán lập lịch phân phối tài nguyên trong tính toán lưới là một lĩnh vực nghiên cứu quan trọng, nhằm tối ưu hóa việc sử dụng tài nguyên tính toán. Hệ thống tính toán lưới cho phép chia sẻ tài nguyên từ nhiều nguồn khác nhau, tạo ra một môi trường tính toán mạnh mẽ và linh hoạt. Việc áp dụng các thuật toán lập lịch hiệu quả giúp cải thiện hiệu suất và giảm thiểu thời gian xử lý công việc.

1.1. Khái niệm về hệ thống tính toán lưới

Hệ thống tính toán lưới là một mạng lưới các máy tính kết nối với nhau, cho phép chia sẻ tài nguyên và thực hiện các tác vụ tính toán phức tạp. Các tài nguyên này có thể bao gồm CPU, bộ nhớ, và dung lượng lưu trữ. Mục tiêu chính của hệ thống này là tối ưu hóa việc sử dụng tài nguyên và giảm thiểu chi phí.

1.2. Vai trò của thuật toán lập lịch trong tính toán lưới

Thuật toán lập lịch đóng vai trò quan trọng trong việc phân phối tài nguyên trong hệ thống tính toán lưới. Chúng giúp xác định cách thức và thời điểm tài nguyên được phân bổ cho các công việc khác nhau, từ đó nâng cao hiệu suất và giảm thiểu thời gian chờ đợi.

II. Các thách thức trong việc lập lịch tài nguyên trong tính toán lưới

Việc lập lịch tài nguyên trong tính toán lưới đối mặt với nhiều thách thức, bao gồm tính không đồng nhất của tài nguyên, sự thay đổi liên tục của môi trường, và yêu cầu về thời gian thực. Những thách thức này đòi hỏi các thuật toán lập lịch phải linh hoạt và hiệu quả.

2.1. Tính không đồng nhất của tài nguyên

Tài nguyên trong hệ thống tính toán lưới thường không đồng nhất, với các máy tính có cấu hình và hiệu suất khác nhau. Điều này tạo ra khó khăn trong việc phân bổ công việc một cách công bằng và hiệu quả.

2.2. Môi trường động và thay đổi liên tục

Môi trường tính toán lưới thường thay đổi liên tục, với các tài nguyên có thể được thêm vào hoặc loại bỏ bất cứ lúc nào. Điều này yêu cầu các thuật toán lập lịch phải có khả năng thích ứng nhanh chóng với các thay đổi này.

III. Phương pháp lập lịch tài nguyên trong tính toán lưới

Có nhiều phương pháp khác nhau để lập lịch tài nguyên trong tính toán lưới, bao gồm các thuật toán tối ưu hóa, thuật toán di truyền, và các phương pháp heuristic. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, phù hợp với các tình huống khác nhau.

3.1. Thuật toán tối ưu hóa

Thuật toán tối ưu hóa thường được sử dụng để tìm ra giải pháp tốt nhất cho bài toán lập lịch. Chúng có thể giúp giảm thiểu thời gian xử lý và chi phí, nhưng thường yêu cầu thời gian tính toán dài.

3.2. Thuật toán di truyền

Thuật toán di truyền là một phương pháp mạnh mẽ trong việc tìm kiếm giải pháp cho các bài toán phức tạp. Chúng sử dụng các nguyên tắc của di truyền học để tìm ra các giải pháp tối ưu cho bài toán lập lịch.

IV. Ứng dụng thực tiễn của thuật toán lập lịch trong tính toán lưới

Các thuật toán lập lịch phân phối tài nguyên đã được áp dụng rộng rãi trong nhiều lĩnh vực, từ nghiên cứu khoa học đến công nghiệp. Chúng giúp tối ưu hóa quy trình làm việc và nâng cao hiệu suất của các hệ thống tính toán.

4.1. Ứng dụng trong nghiên cứu khoa học

Trong nghiên cứu khoa học, các thuật toán lập lịch giúp xử lý các bài toán tính toán lớn, như mô phỏng động đất hay dự báo thời tiết. Chúng cho phép các nhà khoa học tận dụng tối đa tài nguyên tính toán có sẵn.

4.2. Ứng dụng trong công nghiệp

Trong công nghiệp, các thuật toán lập lịch giúp tối ưu hóa quy trình sản xuất, giảm thiểu thời gian chờ đợi và chi phí. Chúng cũng hỗ trợ trong việc quản lý tài nguyên hiệu quả hơn.

V. Kết luận và tương lai của thuật toán lập lịch trong tính toán lưới

Thuật toán lập lịch phân phối tài nguyên trong tính toán lưới đang ngày càng trở nên quan trọng trong bối cảnh công nghệ phát triển nhanh chóng. Tương lai của lĩnh vực này hứa hẹn sẽ có nhiều cải tiến và ứng dụng mới, giúp nâng cao hiệu suất và giảm thiểu chi phí.

5.1. Xu hướng phát triển trong tương lai

Trong tương lai, các thuật toán lập lịch sẽ tiếp tục được cải tiến để đáp ứng nhu cầu ngày càng cao về hiệu suất và tính linh hoạt trong các hệ thống tính toán lưới.

5.2. Tác động của công nghệ mới

Sự phát triển của công nghệ mới, như trí tuệ nhân tạo và học máy, sẽ có tác động lớn đến cách thức lập lịch tài nguyên trong tính toán lưới, mở ra nhiều cơ hội mới cho nghiên cứu và ứng dụng.

16/08/2025

Trích đoạn nội dung tài liệu

Chương 1. TỔNG QUAN VỀ HỆ THỐNG TÍNH TOÁN LƯỚI 1.1 Giới thiệu chung 1.1 Hệ thống tính toán lưới là gì Ngày nay, cùng với sự phát triển vượt bậc của khoa học kỹ thuật và công nghệ ñã xuất hiện các bài toán yêu cầu khối lượng tính toán lớn với ñộ chính xác cao, ví dụ như: dự báo thời tiết, chẩn ñoán trong y học sử dụng thông tin hình ảnh, khoa học sự sống, hoá học tính toán, khoa học trái ñất, vật lý năng lượng cao, y sinh, khoa học trái ñất, vật lý học thiên thể, dược phẩm học, thủy lực học, vũ trụ học, mô hình hoá tài chính, mô phỏng ñộng ñất… Với những bài toán này, các máy tính riêng lẻ không thể ñảm trách ñược. Do vậy, các kỹ thuật tính toán song song, tính toán phân tán ñược ñề xuất và phần nào ñáp ứng ñược yêu cầu này. Để có ñược các hệ thống tính toán song song với khả năng tính toán mạnh, các tổ chức phải ñầu tư thêm trang thiết bị, cơ sở hạ tầng tính toán (máy chủ, máy trạm, siêu máy tính, cụm máy tính,.

Cách làm này hết sức tốn kém. Mặt khác, thực tế cho thấy có một phần lớn các nguồn tài nguyên ñang ñược sử dụng lãng phí: các máy ñể bàn thường chỉ hoạt ñộng khoảng 5% công suất, các máy chủ cũng chỉ hoạt ñộng với 20% công suất. Do vậy, việc tận dụng hiệu quả các nguồn tài nguyên này mang lại một sức mạnh tính toán khổng lồ. Hơn nữa, thay vì việc ñầu tư vào cơ sở hạ tầng, chúng ta cũng có thể "thuê" các nguồn tài nguyên từ bên ngoài với chi phí rẻ hơn.

Cùng với việc phân bố hợp lý các tài nguyên sẵn có và các tài nguyên thuê ngoài, chúng ta sẽ thu ñược một hệ thống có khả năng tính toán lớn với chi phí thấp. Đây là mục tiêu chính của hệ thống tính toán lưới [27]. Hệ thống tính toán lưới hướng ñến việc chia sẻ và sử dụng hiệu quả các nguồn tài nguyên thuộc về nhiều tổ chức trên một quy mô rộng lớn (thậm chí là quy mô toàn cầu) [12,23,40]. Như vậy, hệ thống tính toán lưới, hiểu một cách ñơn giản, là sự phát triển tiếp theo của tính toán phân tán [71].

Mục ñích của hệ thống tính toán lưới là tạo ra một "máy tính" ảo lớn từ một tập các hệ thống không ñồng nhất nhằm nâng cao khả 11 TIEU LUAN MOI download : skknchat@gmail.com năng tính toán, chia sẻ các tài nguyên khác nhau [13]. Các nhà khoa học tại Argone National Labs thuộc Đại học Chicago (Mỹ) là những người ñầu tiên ñề xuất ý tưởng về hệ thống tính toán lưới. Thuật ngữ "lưới" ở ñây xuất phát từ lưới ñiện (electricity grid), ngụ ý rằng bất cứ một thiết bị tương thích nào ñều có thể gắn vào trong lưới và ñược xếp ở một mức tài nguyên nào ñó mà không cần quan tâm ñến nguồn gốc của tài nguyên ấy. Trong tương lai, hệ thống tính toán lưới có thể cung cấp cho người sử dụng các dịch vụ, như là dịch vụ cơ sở hạ tầng ñược sử dụng hàng ngày như ñiện, nước, giao thông [22,29,56].

Để ñáp ứng ñược mục tiêu to lớn này, hệ thống tính toán lưới cần có những gì? Phần tiếp theo luận án sẽ trình bày các mô hình tính toán lưới.2 Các mô hình tính toán lưới Trong thực tế, hệ thống tính toán lưới ñược cài ñặt theo nhiều mô hình khác nhau, phù hợp với từng ứng dụng cụ thể. Có thể phân loại các dạng lưới tính toán này dựa vào cấu trúc của tổ chức ảo tham gia vào mạng lưới hoặc ñịnh nghĩa hệ thống tính toán lưới theo tính chất của tài nguyên ñược chia sẻ [22,23]. Lưới tính toán có thể ñược xây dựng với các kích thước khác nhau. Có thể là chỉ một vài máy trong một phòng hoặc có thể là cả một hệ thống phân cấp các máy tính trải rộng trên toàn cầu.

Sau ñây chúng ta sẽ xem xét một số cấu trúc hệ thống lưới tính toán cơ bản. a) Lưới nội tuyến (Intragrid) Là một hệ thống tính toán lưới bao gồm các tài nguyên nằm rải rác trong một tổ chức (công ty, xí nghiệp) và cung cấp dịch vụ cho tất cả người dùng. Tài nguyên chia sẻ trong các nhóm khác nhau của một tổ chức tạo thành một lưới nội tuyến. Lưới nội tuyến có thể chỉ hạn chế trong một mạng cục bộ hoặc các mạng riêng ảo.

Thông thường lưới nội tuyến ñược bảo vệ bởi hệ thống tường lửa. 12 TIEU LUAN MOI download : skknchat@gmail.com Lưới nội tuyến có thể bao gồm các máy trạm, máy chủ, cũng như các tài nguyên tập trung ñược quản lý cục bộ, nằm tại các bộ phận khác nhau trong một tổ chức. Mô hình tính toán lưới phức tạp hơn có thể gồm các máy tính không ñồng nhất. Trong hệ thống này tồn tại nhiều kiểu tài nguyên khác nhau.

Để quản lý ñiều phối tài nguyên, hệ thống tính toán lưới phải gồm thành phần ñiều phối và lập lịch. Ngoài ra, việc chia sẻ các tệp ñược thực thi bởi hệ thống quản lý tệp. Các máy tính tham gia vào lưới tính toán loại này thường không nhất thiết phải nằm trong cùng một phòng, nhưng nhất thiết phải nằm trong cùng một tổ chức. Mô hình lưới nội tuyến b) Lưới liên tuyến (Intergrid) Là những lưới tính toán ñược phát triển dựa vào mạng Internet công cộng.

Lưới loại này có thể ñược thiết lập bởi các công ty nhằm hỗ trợ việc kinh doanh mua bán, cung cấp các dịch vụ giá trị gia tăng và cho phép người dùng khai thác các tài nguyên bên ngoài [37]. 13 TIEU LUAN MOI download : skknchat@gmail.com Lưới liên tuyến cho phép truy cập và khai thác các tài nguyên phân tán trên khắp thế giới nhằm phục vụ các công việc tính toán và cộng tác của người dùng. Lưới liên tuyến cung cấp khả năng chia sẻ tài nguyên tính toán và lưu trữ thông qua Web. Lưới tính toán ñược sử dụng và xuất hiện ở rất nhiều nơi trên thế giới.

Điều này dẫn ñến việc cần thiết phải có các khuyến nghị cụ thể về việc lưới tính toán ñược sử dụng như thế nào. Ví dụ như, khuyến nghị xác ñịnh loại công việc nào ñược thực hiện trên hệ thống và vào khoảng thời gian nào. Bên cạnh ñó, việc bảo mật cũng trở thành một vấn ñề quan trọng của các tổ chức liên quan. Ngày nay, hệ thống tính toán lưới trải rộng trên khắp toàn cầu, vượt qua biên giới của từng tổ chức riêng lẻ, của các nước và trở thành một lưới tính toán giải quyết các dự án mang tính chất toàn cầu.

Hệ thống tính toán lưới này ñược gọi là: Lưới liên tuyến - “Intergrid”.2 dưới ñây minh họa một hệ thống lưới liên tuyến. Mô hình lưới liên tuyến 14 TIEU LUAN MOI download : skknchat@gmail.3 Các thành phần chính của hệ thống tính toán lưới Khi nói ñến các thành phần của lưới, ta có nhiều cách tiếp cận khác nhau [3]. Nếu nhìn một cách tổng thể, một hệ thống lưới bao gồm nhiều nút lưới mà mỗi nút ñó có thể là một lưới nhỏ hay một cluster. Ở góc ñộ này, một hệ thống lưới bao gồm các thành phần: a) Thành phần quản lý Bất kì một lưới nào cũng cần có một thành phần quản lý.

Trước hết, thành phần này theo dõi các tài nguyên ñang sẵn dùng và các thành viên ñang có mặt trong hệ thống. Các thông tin này rất quan trọng trong việc gán công việc cho máy trong lưới. Tiếp ñó là thành phần ño lường, xác ñịnh dung lượng tài nguyên của từng nút mạng và tỉ lệ tài nguyên ñược sử dụng tại một thời ñiểm bất kì. Điều này là cơ sở cho việc lập lịch cho các tiến trình lưới.

Thành phần ño lường cũng cho thấy tình trạng của lưới, cảnh báo người sử dụng về khả năng có thể xảy ra thất bại do thiếu tài nguyên, ñụng ñộ hay các nguyên nhân khác. Một thủ tục khác cần ñến các thông tin này là các thống kê về sử dụng hệ thống, việc chi trả cho hệ thống khi chạy các phần mềm trên lưới. b) Phần mềm quản lý donor Mỗi máy tính thành viên ñóng góp tài nguyên vào hệ thống ñều cần có quá trình ñăng nhập trước khi ñược xem như một thành viên chính thức. Thông thường sẽ có các thủ tục ñịnh danh và thẩm quyền ñể thực hiện, các thủ tục này sẽ giúp tạo lập một tài khoản cho máy thành viên cũng như người chủ của máy ñó.

Một số hệ thống lưới tự ñộng ñăng nhập, trong khi một số hệ thống khác lại sử dụng việc ñăng nhập vào hệ ñiều hành trên máy ñịa phương. Trong kiểu quản lý thứ hai, hệ thống sẽ ñối chiếu ñịnh danh người dùng, ñể quyết ñịnh quyền của người sử dụng ñối với các máy khác nhau trong hệ thống lưới. Những quyền hạn này ñược 15 TIEU LUAN MOI download : skknchat@gmail.com quyết ñịnh bởi người quản trị hệ thống, sử dụng các thông tin trong cơ sở dữ liệu người dùng. Hệ thống tính toán lưới còn thông báo tới tất cả các máy thành viên khi có một tài nguyên mới ñược kết nối vào hệ thống.

Máy ñệ trình phải tiến hành các hoạt ñộng theo dõi, ño lường tỉ lệ tài nguyên ñược sử dụng trên máy, máy nào ở trạng thái nghỉ, … Các thông tin này ñược truyền ñến hệ thống quản lý lưới phục vụ cho công việc lập lịch sau này. Vấn ñề quan trọng nhất vẫn là khả năng tiếp nhận công việc và thực hiện công việc của một phần mềm ñược cài ñặt trên một máy nào ñó khi ñược gán nhiệm vụ. Quá trình ñược mô tả như sau: tại một trạm nào ñó trên lưới, người sử dụng ñệ trình một công việc và yêu cầu thực hiện trên lưới. Phần mềm quản lý phải chọn ra máy thực hiện, liên lạc với máy ñó ñể gửi công việc cần thực hiện.

Phần mềm ñệ trình phải nhận ñược tệp chạy hoặc chọn bản sao trên máy ñã sẵn sàng, tiếp ñó tệp chạy ñược thực hiện trên máy ñệ trình và kết quả ñược trả về cho người yêu cầu. c) Phần mềm ñệ trình Về nguyên tắc, người ta có thể dùng bất cứ máy thành phần nào trong lưới ñể ñệ trình một công việc. Tuy vậy, trong một số hệ thống, việc ñệ trình các công việc ñược thực hiện bởi một số thành phần cài ñặt trên máy, gọi là nút ñệ trình hay máy khách ñệ trình. Khi lưới tính toán ñược xây dựng dựa trên các tài nguyên chuyên dụng, các thành phần ñệ trình thường ñược cài ñặt trên máy của người dùng hay các trạm làm việc.

d) Quản lý phân tán Các lưới tính toán ñược cài ñặt trên phạm vi rộng lớn thường có cấu trúc hình cây hay các cấu trúc ñặc thù khác phù hợp với dạng kết nối.

Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ