Luận Án Tiến 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

Luận án tiến sĩ trình bày các thuật toán lập lịch hiệu quả nhằm phân phối tài nguyên trong hệ thống tính toán lưới, nâng cao hiệu suất và tối ưu hóa.

Chuyên ngành

Bảo ñảm toán học cho máy tính và hệ thống tính toán

Người đăng

Ẩn danh

Thể loại

Luận án tiến sĩ

2011

128
3
0

Phí lưu trữ

35 Point

Mục lục chi tiết

LỜI CAM ĐOAN

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

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 Tối Ưu Phân Phối Tài Nguyên

Thuật toán lập lịch tối ưu phân phối tài nguyên trong hệ thống tính toán lưới là một lĩnh vực nghiên cứu quan trọng. Hệ thống tính toán lưới cho phép chia sẻ tài nguyên giữa nhiều máy tính, giúp tối ưu hóa hiệu suất và giảm thiểu chi phí. Việc áp dụng các thuật toán lập lịch hiệu quả sẽ giúp cải thiện khả năng sử dụng tài nguyên và tăng cường hiệu suất tính toán.

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à băng thông mạng. Hệ thống này giúp tối ưu hóa việc sử dụng tài nguyên và giảm thiểu chi phí cho người dùng.

1.2. Vai Trò Của Thuật Toán Trong Lập Lịch Tài Nguyên

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 tác vụ khác nhau, từ đó tối ưu hóa hiệu suất và giảm thiểu thời gian chờ đợi.

II. Các Thách Thức Trong Lập Lịch Tài Nguyên Hệ Thống Tính Toán Lưới

Lập lịch tài nguyên trong hệ thống tính toán lưới đối mặt với nhiều thách thức. Những thách thức này 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 trạng thái tài nguyên, và yêu cầu về thời gian thực. Việc giải quyết những vấn đề này là rất cần thiết để đảm bảo hiệu suất tối ưu.

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ề hiệu suất và khả năng. Điều này tạo ra khó khăn trong việc lập lịch, vì các thuật toán cần phải xem xét khả năng của từng tài nguyên để phân bổ công việc một cách hợp lý.

2.2. Sự Thay Đổi Liên Tục Của Trạng Thái Tài Nguyên

Trạng thái của tài nguyên trong hệ thống tính toán lưới có thể thay đổi liên tục do nhiều yếu tố như tải công việc, sự cố kỹ thuật, hoặc bảo trì. Điều này yêu cầu các thuật toán lập lịch phải linh hoạt và có khả năng thích ứng nhanh chóng với các thay đổi.

III. Phương Pháp Lập Lịch Tối Ưu Trong Hệ Thống Tính Toán Lưới

Có nhiều phương pháp lập lịch tối ưu được áp dụng trong hệ thống tính toán lưới. Những phương pháp này bao gồm lập lịch dựa trên thời gian, chi phí, và hiệu suất. Mỗi phương pháp có những ưu điểm và nhược điểm riêng, và việc lựa chọn phương pháp phù hợp là rất quan trọng.

3.1. Lập Lịch Dựa Trên Thời Gian

Phương pháp lập lịch dựa trên thời gian tập trung vào việc tối ưu hóa thời gian thực hiện công việc. Các thuật toán này thường sử dụng các kỹ thuật như lập lịch động để điều chỉnh thời gian thực hiện dựa trên trạng thái hiện tại của tài nguyên.

3.2. Lập Lịch Dựa Trên Chi Phí

Lập lịch dựa trên chi phí nhằm tối ưu hóa chi phí sử dụng tài nguyên. Các thuật toán này thường xem xét chi phí của từng tài nguyên và lựa chọn tài nguyên có chi phí thấp nhất cho từng tác vụ.

IV. Ứng Dụng Thực Tiễn Của Thuật Toán Lập Lịch Tối Ưu

Các thuật toán lập lịch tối ưu đã được áp dụng rộng rãi trong nhiều lĩnh vực khác nhau, từ khoa học máy tính đến y tế và tài chính. Việc áp dụng các thuật toán này không chỉ giúp tối ưu hóa hiệu suất mà còn giảm thiểu chi phí cho các tổ chức.

4.1. Ứng Dụng Trong Khoa Học Máy Tính

Trong lĩnh vực khoa học máy tính, các thuật toán lập lịch tối ưu giúp cải thiện hiệu suất của các hệ thống máy chủ và trung tâm dữ liệu. Chúng cho phép phân bổ tài nguyên một cách hiệu quả, từ đó nâng cao khả năng xử lý và giảm thiểu thời gian chờ đợi.

4.2. Ứng Dụng Trong Y Tế

Trong y tế, các thuật toán lập lịch tối ưu được sử dụng để phân bổ tài nguyên cho các quy trình chẩn đoán và điều trị. Việc tối ưu hóa tài nguyên giúp cải thiện chất lượng dịch vụ y tế và giảm thiểu thời gian chờ đợi cho bệnh nhân.

V. Kết Luận Về Thuật Toán Lập Lịch Tối Ưu Phân Phối Tài Nguyên

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

5.1. Tương Lai Của Nghiên Cứu Về Lập Lịch Tài Nguyên

Nghiên cứu về lập lịch tài nguyên trong hệ thống tính toán lưới sẽ tiếp tục phát triển với sự xuất hiện của các công nghệ mới. Các thuật toán mới sẽ được phát triển để đáp ứng nhu cầu ngày càng cao về hiệu suất và chi phí.

5.2. Tầm Quan Trọng Của Việc Tối Ưu Hóa Tài Nguyên

Tối ưu hóa tài nguyên trong hệ thống tính toán lưới không chỉ giúp cải thiện hiệu suất mà còn góp phần vào việc phát triển bền vững. Việc sử dụng hiệu quả tài nguyên sẽ giúp giảm thiểu tác động đến môi trường và tiết kiệm chi phí cho các tổ chức.

19/07/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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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.

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