BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ
PHAN THANH TOÀN CÁC PHƯƠNG PHÁP GẦN ĐÚNG DỰA TRÊN TỐI ƯU BÀY ĐÀN VÀ TIẾN HÓA VI PHÂN GIẢI BÀI TOÁN LẬP LỊCH LUỒNG CÔNG VIỆC TRONG MÔI TRƯỜNG ĐIỆN TOÁN ĐÁM MÂY
Chuyên ngành : Cơ sở toán học cho tin học Mã số
: 62 46 01 10
TÓM TẮT LUẬN ÁN TIẾN SĨ TOÁN HỌC HÀ NỘI - 2018
Công trình được hoàn thành tại: VIỆN KH&CN QUÂN SỰ - BỘ QUỐC PHÒNG
Người hướng dẫn khoa học:
1. TS Nguyễn Thế Lộc
2. TS Nguyễn Doãn Cường
Phản biện 1:PGS.TS. Nguyễn Đức Nghĩa
Trường Đại học Bách khoa Hà Nội
Phản biện 2: PGS.TS. Lê Trọng Vĩnh
Trường Đại học Khoa học tự nhiên
Đại học Quốc gia Hà Nội
Phản biện 3: PGS.TS. Nguyễn Xuân Hoài
Trường Đại học Hà Nội
Luận án tiến sĩ được bảo vệ trước Hội đồng chấm luận án cấp Viện, họp tại Viện KH&CNQS Vào hồi giờ ngày tháng năm 2018
Có thể tìm hiểu luận án tại thư viện: - Thư viện Viện Khoa học và Công nghệ quân sự - Thư viện Quốc gia Việt Nam
1
MỞ ĐẦU
Tính cấp thiết của đề tài luận án
Điện toán đám mây hoạt động dựa trên nền tảng công nghệ ảo hóa và mạng internet. Trong môi trường điện toán đám mây mọi tài nguyên phần cứng, phần mềm đều được cung cấp cho khách hàng dưới dạng dịch vụ và khách hàng sẽ phải trả chi phí cho các tài nguyên thực dùng. Điện toán đám mây [1] là môi trường phân tán không đồng nhất với sự kết hợp của nhiều máy chủ vật lý tạo nên các máy chủ ảo để phục vụ khách hàng. Bên cạnh các lợi ích mang lại như tài nguyên luôn sẵn dùng, giảm thiểu chi phí đầu tư hạ tầng và đội ngũ nhân viên công nghệ thông tin, điện toán đám mây cũng phải đối mặt với những thách thức như an toàn và bảo mật dữ liệu, điều phối tài nguyên hiệu quả tại các trung tâm dữ liệu, lập lịch luồng công việc,…
Bài toán Lập lịch luồng công việc được ứng dụng trong nhiều lĩnh vực của khoa học và cuộc sống như lập lịch điều phối tài nguyên trong hệ điều hành, các hệ thống phân tán, lập lịch biểu cho các dây chuyền sản xuất. Các nhà khoa học đã sử dụng dữ liệu dạng luồng công việc trong nhiều lĩnh vực khoa học như nghiên cứu vũ trụ, động đất, tin sinh, vật lý….Đặc trưng của các loại ứng dụng này là cần phải xử lý một số lượng lớn tác vụ , khối lượng dữ liệu trao đổi giữa các tác vụ cũng rất lớn do vậy các ứng dụng này thường được triển khai trên các hệ thống tính toán phân tán như điện toán lưới hay điện toán đám mây. Thời gian hoàn thành và chi phí thực thi luồng công việc phụ thuộc vào nhiều yếu tố đầu vào như:
• Số lượng tác vụ của luồng công việc.
• Số tài nguyên của môi trường tính toán.
• Quan hệ thứ tự giữa các tác vụ trong luồng công việc.
• Độ trù mật của đồ thị luồng công việc.
2
Rất nhiều trường hợp riêng của bài toán lập lịch đã được chứng minh là thuộc lớp NP-Khó [2], do vậy để tìm ra lời giải tối ưu cho các bài toán với kích thước dữ liệu vào lớn nếu dùng phương pháp vét cạn sẽ mất rất nhiều thời gian. Một số cách tiếp cận theo Heuristic truyền thống như Min- min, Max-min,… thường cho chất lượng lời giải không tốt. Những giải pháp khác, chẳng hạn GA hay PSO, được các nhà nghiên cứu đề xuất cho tới nay đều không hướng tới mục tiêu là tối thiểu hóa thời gian thực hiện (makespan) như luận án này đặt ra. Do vậy việc nghiên cứu và đề xuất các thuật toán lập lịch tìm được lời giải gần tối ưu trong thời gian ngắn sẽ giúp nâng cao hiệu năng của trung tâm điều phối đám mây trong việc cung cấp dịch vụ tới khách hàng.
Cấu trúc luận án
Luận án gồm phần mở đầu, phụ lục, 03 chương, phần kết luận và hướng phát triển, danh mục các công trình khoa học đã công bố và tài liệu tham khảo.
Phần mở đầu: trình bày tính cấp thiết của đề tài, những khái quát chung về mục tiêu, đối tượng, nội dung, phương pháp nghiên cứu, ý nghĩa khoa học và thực tiễn của luận án.
Chương 1: Giới thiệu bài toán và các nghiên cứu liên quan
Chương này trình bày các khái niệm cơ bản về luồng công việc, cấu trúc và một số luồng công việc trong các ứng dụng khoa học thực tiễn. Mục
1.4 trình bày mô hình bài toán lập lịch luồng công việc trong môi trường điện toán đám mây (từ đây gọi là CLOS - Cloud Scheduling), biểu diễn bài toán dưới dạng kí hiệu Graham và chứng minh độ phức tạp của bài toán. Mục 1.6 trình bày một số nghiên cứu liên quan đến bài toán lập lịch và đánh giá ưu nhược điểm của các cách tiếp cận giải bài toán lập lịch.
Chương 2: Giải bài toán CLOS theo phương pháp Tối ưu bày đàn
3
Dựa theo phương pháp Tối ưu bày đàn, chương 2 trình bày hai thuật toán mới để giải bài toán CLOS là thuật toán PSOi_H và LPSO_H. Mục 2.2 trình bày thuật toán đề xuất PSOi_H với các nội dung về phương pháp mã hóa cá thể, cách thức cập nhật vector vị trí của các cá thể, phương pháp thoát khỏi cực trị địa phương, chi tiết thuật toán PSOi_H. Phần này cũng đã trình bày các kết quả thực nghiệm và đánh giá chất lượng lời giải thuật toán PSOi_H. Mục 2.3 trình bày chi tiết về thuật toán đề xuất LPSO_H và các kết quả thực nghiệm cùng với đánh giá chất lượng lời giải của thuật toán LPSO_H.
Chương 3: Giải bài toán CLOS theo phương pháp Tiến hóa vi phân
Chương này trình bày tổng quan về phương pháp tiến hóa vi phân, phương pháp đối xứng, phương pháp lựa chọn theo vòng dựa trên xếp hạng của cá thể. Mục 3.2 trình bày thuật toán đề xuất MODE để giải bài toán CLOS dựa theo phương pháp tiến hóa vi phân. Phần cuối chương này đã trình bày các kết quả thực nghiệm và đánh giá chất lượng lời giải của thuật toán đề xuất MODE.
Ý nghĩa khoa học và thực tiễn
Về mặt lý thuyết khoa học, trong số nhiều công trình nghiên cứu những dạng khác nhau của bài toán Lập lịch, theo hiểu biết của tác giả, luận án là công trình đầu tiên giải quyết bài toán Lập lịch cho dạng dữ liệu luồng công việc DAG với mục tiêu duy nhất là tối thiểu hóa makespan. Luận án đã đề xuất mô hình toán học chặt chẽ và tường minh cho bài toán - lấy bối cảnh thực hiện là trung tâm điện toán đám mây - trên cơ sở đó đưa ra cách phân loại bài toán theo phương pháp Graham và chỉ ra bài toán thuộc lớp NP-Khó. Luận án đã đề xuất ba thuật toán lập lịch mới dựa trên hướng tiếp cận metaheuristic bao gồm Tối ưu bày đàn, và Tiến hóa vi phân.
Về thực tiễn, kết quả nghiên cứu của luận án là cơ sở khoa học để thực thi các thuật toán lập lịch luồng công việc trong môi trường điện toán đám
4
mây phù hợp cho từng loại đồ thị luồng công việc và các tham số của môi trường như tốc độ tính toán các máy chủ, băng thông giữa các máy chủ.
Chương 1: Giới thiệu bài toán và các nghiên cứu liên quan
Chương này trình bày mô hình bài toán lập lịch luồng công việc trong môi trường điện toán đám mây, phân lớp các phương pháp giải bài toán lập lịch và chứng minh bài toán đề xuất CLOS thuộc lớp NP-Khó.
Mô hình bài toán lập lịch luồng công việc trong môi trường điện toán đám mây
Hệ thống tính toán Giả thiết cho trước hệ thống tính toán bao gồm:
• Tập hợp N máy chủ trong môi trường điện toán đám mây S = {S1, S2,
... SN}.
• Luồng công việc cần thực hiện biểu diễn bởi đồ thị có hướng, không có chu trình G=(V,E), mỗi đỉnh biểu thị một tác vụ, mỗi cạnh biểu diễn mối quan hệ cha-con giữa một cặp tác vụ.
• Tập các tác vụ T={T1, T2, ... TM} với M là số lượng tác vụ.
• Khối lượng tính toán của tác vụ Ti ký hiệu là Wi , đo bằng đơn vị flop (floating point operations: phép tính trên số thực dấu phảy động).
• Tốc độ tính toán của máy tính, đo bằng đơn vị flop/s (số phép tính thực hiện được trên giây), ký hiệu P(), là hàm số được định nghĩa như sau:
P: S R+
Si P(Si)
• Mọi cặp máy chủ (Si, Sk) bất kỳ đều có đường truyền để trao đổi dữ
liệu với nhau (1≤i, k≤N).
5
• Băng thông của đường truyền, ký hiệu B(), là tốc độ truyền dữ liệu giữa các máy chủ, đo bằng đơn vị bit trên giây (bps), là hàm số được định nghĩa như sau:
B: SS R+
(Si, Sk) B(Si, Sk)
• Hàm băng thông B() tuân theo các ràng buộc sau:
- B(Si,Si) =: thời gian truyền từ một máy chủ tới chính nó bằng 0,
nghĩa là nếu tác vụ cha và tác vụ con được bố trí trên cùng một máy chủ thì không mất thời gian để truyền dữ liệu giữa chúng vì dữ liệu đó được lưu trữ và sử dụng ngay tại chỗ.
- B(Si,Sk ) = B(Sk,Si): kênh truyền hoạt động từ hai đầu với tốc độ tương
đương nhau.
Khối lượng dữ liệu cần truyền giữa hai tác vụ Ti và Tk, ký hiệu là Dik, là
các giá trị cho trước, Dik 0 khi và chỉ khi Ti là tác vụ cha của Tk, ngược lại
Dik =0.
Khái niệm lịch biểu
Một phương án xếp lịch F, còn gọi là lịch biểu F, được xác định bởi hai hàm (ts , proc) trong đó
• ts: T R+; ts(Ti) là thời điểm mà tác vụ Ti T bắt đầu được thực hiện
• proc: T S; proc(Ti) là máy tính được phân công thực hiện tác vụ Ti
T
Từ các giả thiết trên suy ra:
Thời gian tính toán của tác vụ Ti:
Thời gian truyền dữ liệu giữa tác vụ Ti và tác vụ Tk là:
Makespan của lịch biểu F được biểu diễn theo công thức sau:
6
với tf(Ti) là thời điểm kết thúc và ts(Ti) là thời điểm bắt đầu thực hiện của tác vụ Ti
Mục tiêu của bài toán
Mục tiêu của bài toán là tìm lịch biểu F sao cho
Xếp loại bài toán CLOS thông qua phân loại Graham
• Bài toán CLOS có thể được biểu diễn theo ký pháp Graham như sau:
Q|outtree, cij |Cmax
Độ phức tạp của bài toán CLOS
Dựa theo bài toán SCHED đã được O. Sinnen chứng minh thuộc lớp NP-khó, tác giả đã chứng minh bài toán CLOS cũng thuộc lớp NP-khó bằng cách qui dẫn bài toán SCHED về bài toán CLOS.
Các nghiên cứu liên quan
Phân loại các phương pháp giải bài toán lập lịch
Cấu trúc
Cơ chế
Căn cứ ra quyết định
Tập trung
Tĩnh
Cục bộ
Phân tán
Động
Toàn
cục
Phân bậc
Phân loại các phương pháp giải bài toán lập lịch
Hình 1.12: Phân loại các phương pháp lập lịch
Các giải thuật lập lịch tĩnh
Các giải thuật dựa trên heuristics
Các giải thuật dựa trên Metaheuristics
Lập lịch dựa trên phân cụm
Lập lịch dựa trên bản sao các tác vụ
Lập lịch dựa trên quyền ưu tiên các tác vụ
…
Thuật toán di truyền
Thuật toán đàn kiến
Thuật toán luyện thép
Phương pháp tiến hóa vi phân
Phương pháp tối ưu bày đàn
7
Hình 1.13: Phân lớp các giải thuật lập lịch tĩnh
Các phương pháp giải bài toán lập lịch Các thuật toán Heuristic giải bài toán lập lịch
Có nhiều thuật toán Heuristic giải bài toán lập lịch, điển hình trong họ này là các thuật toán Myopic, Min-min, Max-min, HEFT, TANH, Random, RRTSM.
Các thuật toán Metaheuristic giải bài toán lập lịch
Đã có nhiều công trình nghiên cứu giải bài toán lập lịch dựa trên cách tiếp cận metaheuristic như thuật toán EGA, GATSM, GAPSO, PSO_H, MPSO, …
So sánh các thuật toán
Các thuật toán heuristic và metaheuristic thường cho chất lượng lời giải chấp nhận được trong thời gian đa thức, tuy nhiên các thuật toán heuristic thường hoạt động dựa vào các tính chất của từng tác vụ rời rạc trong qua trình xếp lịch do vậy chỉ hiệu quả trong một số luồng công việc
8
cụ thể như luồng công việc có cấu trúc đơn giản dạng tiến trình, đường ống (pipeline), và dữ liệu truyền qua lại giữa các tác vụ là nhỏ. Các thuật toán metaheustic hoạt động dựa trên tri thức của cả quần thể do vậy có thường có hiệu quả đối với nhiều dạng bài toán lập lịch và các cấu trúc luồng công việc phức tạp.
Chương 2: Giải bài toán CLOS theo phương pháp tối ưu bày đàn
Chương này gồm hai nội dung chính:
(i) Đề xuất thuật toán PSOi_H giải bài toán CLOS
(ii) Đề xuất thuật toán LPSO_H giải bài toán CLOS
2.1. Thuật toán đề xuất PSOi_H
Thuật toán đề xuất hoạt động theo phương pháp tối ưu bày đàn, tuy
nhiên thuật toán được cải tiến ở các điểm sau:
(i) Thay đổi phương pháp cập nhật vị trí cho các cá thể nhằm tăng tính
đa dạng cho quần thể.
(ii) Đề xuất thủ tục Inverse nhằm giúp quần thể thoát khỏi cực trị địa
phương.
Mã hóa cá thể
Vector vị trí và vector dịch chuyển đều được biểu diễn bằng cấu trúc
dữ liệu bảng băm trong ngôn ngữ lập trình java.
T1 S1 T2 S2 T3 S1 T4 S3 T5 S2
Phương thức cập nhật vị trí của cá thể
Định nghĩa 1: điểm năng lực tính toán cơ bản của máy chủ (base score) là một đại lượng được sử dụng để đánh giá hiệu suất của máy chủ, được tính toán dựa trên điểm của các thành phần khác trong máy tính như tốc độ bộ vi xử lý, dung lượng và tốc độ bộ nhớ RAM, tốc độ ổ đĩa cứng. Trong luận
9
án này điểm năng lực tính toán được ưu tiên theo tốc độ tính toán của bộ vi xử lý trên máy chủ. Công thức cập nhật các thành phần của vector vị trí và vector dịch chuyển như sau :
Biện pháp thoát khỏi cực trị địa phương
Phương pháp tối ưu bày đàn nói riêng và các phương pháp tìm kiếm dựa trên heuristic và metaheuristic nói chung đôi khi bị mắc kẹt tại các lời giải cực trị địa phương mà không thể thoát ra để đi tới lời giải tốt hơn.Phần này đề xuất thủ tục Inverse như một biện pháp được áp dụng mỗi khi vòng lặp chương trình sa vào một cực trị địa phương và các cá thể bị hút vào gần lời giải cực trị đó mà không thể thoát ra.
S1 S2 S3
3.1 5.2 4.1
Sπ(1) Sπ(2) Sπ(3)
3.1 4.1 5.2
Sπ(1) Sπ(3) S1 S2
Hình 2.2:Thủ tục Inverse
Thuật toán PSOi_H hoạt động theo phương pháp tối ưu bày đàn theo đó tại mỗi bước lặp các cá thể cập nhật vị trí của mình hướng tới vị trí tốt nhất của cả quần thể (gbest) đồng thời có dựa trên kinh nghiệm cá nhân
10
(pbesti). Nếu sau K thế hệ liên tiếp không cải thiện được một cách đáng kể
giá trị gbest (mức chênh không vượt quá ) thì chứng tỏ quần thể đang hội
tụ tại một cực trị địa phương. Khi đó thủ tục Inverse được áp dụng cho một nửa cá thể tồi nhất trong quần thể, và di cư chúng tới một vùng không gian mới, tại đó quá trình tìm kiếm được tái khởi động.
Thực nghiệm
Để kiểm chứng thuật toán PSOi_H tác giả đã sử dụng các bộ dữ liệu thực nghiệm được xây dựng trong phụ lục PL1, PL2 và công cụ mô phỏng môi trường điện toán đám mây CloudSim [64], các hàm của gói thư viện Jswarm. Kết quả của thuật toán được so sánh với các giá trị tối ưu tìm được bằng phương pháp vét cạn và các thuật toán heuristic và metaheuristic là Random [38], RRTSM [39], PSO_H [28], EGA [40]. Chi tiết về kết quả thực nghiệm được trình bày trong các bảng 2-3, 2-4 và 2-5 của luận án.
So sánh thuật toán PSOi_H với các thuật toán khác
Hình 2.4: So sánh thuật toán PSOi_H và các thuật toán khác với bộ dữ liệu T1052
11
Hình 2.5: So sánh thuật toán PSOi_H và các thuật toán khác với bộ dữ liệu T2032
Đánh giá chất lượng lời giải thuật toán PSOi_H
Với mỗi bộ dữ liệu chuẩn chúng tôi đã tiến hành thực nghiệm các thuật toán một cách độc lập với 30 lần thử, các tham số về băng thông giữa các máy chủ, tốc độ tính toán của các máy chủ được thiết lập trong môi trường mô phỏng CloudSim một cách nhất quán cho tất cả các thuật toán trong các lần thử nghiệm. Với hai thuật toán PSOi_H và PSO_H các tham
số về hệ số quán tính: ; hệ số gia tốc c1, c2; số cá thể trong quần thể và số
thế hệ được thiết lập như nhau. Kết quả thực nghiệm đã chỉ ra chất lượng lời giải của thuật toán PSOi_H luôn tốt hơn các thuật toán Random, RRTSM ở cả 3 tham số là độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất trong tất cả các bộ dữ liệu thực nghiệm. Kết quả thực nghiệm với các bộ dữ liệu ngẫu nhiên trong bảng 2-3 đã chỉ ra thuật toán PSOi_H luôn cho chất lượng lời giải tốt hơn thuật toán PSO_H ở cả 3 tham số độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất trong hầu hết các bộ dữ liệu thực nghiệm. Một số bộ dữ liệu như T1035, T2051, T2053 thì thuật toán
12
PSOi_H có giá trị trung bình và độ lệch chuẩn nhỏ hơn so với kết quả tìm được bởi thuật toán PSO_H. Kết quả thực nghiệm với các bộ dữ liệu trong ứng dụng thực tiễn Montage, Epigenomics (xem bảng 2-4, 2-5) đã chỉ ra chất lượng lời giải của thuật toán PSOi_H tốt hơn thuật toán PSO_H ở cả 3 tham số độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất. So với thuật toán EGA thì thuật toán PSOi_H tốt hơn ở 2 tham số giá trị trung bình và giá trị tốt nhất.
Độ lệch chuẩn tìm được bởi thuật toán PSOi_H nhỏ hơn độ lệch chuẩn tìm được bởi các thuật toán PSO_H từ 2% - 11% cho các bộ dữ liệu thực nghiệm có các tham số môi trường đám mây đồng đều về băng thông và tốc
độ tính toán, và nhỏ hơn từ 16% - 51% cho các bộ dữ liệu thực nghiệm có tham số môi trường đám mây không đồng đều về băng thông và tốc độ tính toán giữa các máy chủ.
Giá trị trung bình tìm được bởi thuật toán PSOi_H nhỏ hơn giá trị trung bình tìm được bởi thuật toán PSO_H từ 1% - 7%, đặc biệt với các bộ
dữ liệu thực nghiệm có hệ số nhỏ (đồ thị luồng công việc có số cạnh ít,
hay sự phụ thuộc dữ liệu giữa các tác vụ không nhiều) thì thuật toán PSOi_H có giá trị trung bình nhỏ hơn so với thuật toán PSO_H từ 8% - 16%. So với thuật toán EGA giá trị trung bình tìm được bởi thuật toán PSOi_H nhỏ hơn từ 2% - 9%.
Giá trị tốt nhất tìm được bởi thuật toán PSOi_H nhỏ hơn giá trị tốt nhất tìm được bởi các thuật toán Random và RRTSM với tất cả các bộ dữ liệu thực nghiệm. So với thuật toán PSO_H thì giá trị tốt nhất tìm được bởi PSOi_H nhỏ hơn 2% - 7% , đặc biệt với các bộ dữ liệu thực nghiệm từ ứng dụng thực tiễn Epinogenmic thì giá trị tốt nhất tìm được bởi PSOi_H nhỏ hơn PSO_H từ 8% - 15%. Giá trị tốt nhất tìm được bởi thuật toán PSOi_H nhỏ hơn giá trị tốt nhất tìm được bởi thuật toán EGA từ 2.3% - 8%.
13
Với một số bộ dữ liệu thực nghiệm thì giá trị tốt nhất tìm được bởi thuật toán PSOi_H bằng giá trị tối ưu tìm được theo phương pháp vét cạn; như các bộ dữ liệu chuẩn T531, T532, T533. Với các bộ dữ liệu thực nghiệm khác giá trị tốt nhất tìm được bởi thuật toán PSOi_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 0.8% đến 4% (theo công thức 1-10). Với các bộ dữ liệu thực nghiệm có băng thông giữa các máy chủ trong môi trường đám mây thấp thì giá trị tốt nhất tìm được bởi thuật toán PSOi_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 11.5% - 20.7%. Kết quả được trình bày chi tiết trong bảng 2-6 của luận án.
2.2. Thuật toán LPSO_H
Thuật toán LPSO_H là một thuật toán tối ưu bày đàn lai, trong đó sử dụng kết hợp phương pháp tối ưu bày đàn và phương pháp tìm kiếm lân cận.
Thuật toán LPSO gồm các điểm cải tiến cơ bản sau:
(i) Thay đổi phương pháp cập nhật vị trí của các cá thể nhằm tăng tính
đa dạng trong quần thể.
(ii) Kết hợp với thủ tục tìm kiếm lân cận nhằm giúp quần thể thoát khỏi
các điểm cực trị địa phương.
Phương pháp tìm kiếm lân cận
Tìm kiếm lân cận là một phương pháp tìm kiếm heuristic. Phương pháp này thường bắt đầu từ một giải pháp khởi tạo của bài toán, sau đó sẽ áp dụng một dãy các toán tử biến đổi trên lời giải ban đầu để thu được lời giải mới với giá trị hàm mục tiêu tốt hơn [70].
Tác giả đã đề xuất hai toán tử Exchange và RotateRight sử dụng cho
quá trình tìm kiếm lân cận như hình sau:
14
3
1
2
3
1
3
1
2
3
1
a) Toán tử RotateRight
3
3
2
1
1
b) Toán tử Exchange
Hình 2.14: Toán tử RotateRight và Exchange
Thực nghiệm
Tham số môi trường điện toán đám mây và luồng dữ liệu thực nghiệm được trình bày chi tiết trong các bảng PL1-1 đến PL1-39 và PL2-1 đến PL2-3. Kết quả thực nghiệm thuật toán LPSO_H được trình bày chi tiết trong các bảng 2-9, 2-10 và 2-11 của luận án.
Đánh giá chất lượng lời giải thuật toán LPSO_H
Với mỗi bộ dữ liệu chuẩn tác giả đã tiến hành thực nghiệm các thuật toán một cách độc lập với 30 lần thử, các tham số về băng thông giữa các máy chủ, tốc độ tính toán của các máy chủ được thiết lập trong môi trường mô phỏng CloudSim một cách nhất quán cho tất cả các thuật toán trong các lần thử nghiệm. Với hai thuật toán LPSO_H và PSO_H các tham số về hệ
số quán tính: ; hệ số gia tốc c1, c2; số cá thể trong quần thể và số thế hệ
được thiết lập như nhau. Kết quả thực nghiệm trong các bảng 2-9, 2-10 và 2-11 đã chỉ ra chất lượng lời giải của thuật toán LPSO_H luôn tốt hơn các thuật toán Random, RRTSM, PSO_H ở cả 3 tham số là độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất. So sánh với thuật toán EGA, thuật toán LPSO_H luôn cho lời giải tốt hơn thuật toán EGA ở cả 3 tham số độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất trong hầu hết các bộ dữ liệu thực nghiệm. Với một số bộ dữ liệu như T2054, T2055, M2531, M5081,
15
E10081 thuật toán LPSO_H luôn cho chất lượng lời giải tốt hơn thuật toán EGA ở 2 tham số là giá trị trung bình và giá trị tốt nhất.
Độ lệch chuẩn tìm được bởi thuật toán LPSO_H nhỏ hơn độ lệch chuẩn tìm được bởi thuật toán PSO_H từ 7% - 14% trong hầu hết các bộ dữ liệu thực nghiệm, đặc biệt trong các bộ dữ liệu thực nghiệm từ ứng dụng thực tế Montage và Epigenomics thì độ lệch chuẩn tìm được bởi thuật toán LPSO_H nhỏ hơn so với thuật toán PSO_H từ 16% - 31%.
Giá trị trung bình tìm được bởi thuật toán LPSO_H nhỏ hơn giá trị trung bình tìm được bởi thuật toán PSO_H từ 2.7% - 9.8%, đặc biệt với các bộ dữ liệu thực nghiệm có khối lượng dữ liệu cần truyền giữa các tác vụ nhỏ thì giá trị trung bình tìm được bởi thuật toán LPSO_H nhỏ hơn so với thuật toán PSO_H từ 21% - 33%. So với thuật toán EGA giá trị trung bình tìm được bởi LPSO_H nhỏ hơn từ 2.4% - 11.8%.
Giá trị tốt nhất tìm được bởi thuật toán LPSO_H nhỏ hơn giá trị tốt nhất tìm được bởi PSO_H từ 2.1% - 11% và nhỏ hơn so với thuật toán EGA từ 1.2% - 15.4%.
Với một số bộ dữ liệu thực nghiệm thì giá trị tốt nhất tìm được bởi thuật toán LPSO_H bằng giá trị tối ưu tìm được theo phương pháp vét cạn; như các bộ dữ liệu chuẩn T531, T532, T533. Với các bộ dữ liệu thực nghiệm khác giá trị tốt nhất tìm được bởi thuật toán LPSO_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 0.1% đến 5.4% (theo công thức 1-10). Với các dữ liệu thực nghiệm có tham số môi trường đám mây không đồng đều về băng thông và tốc độ tính toán giữa các máy chủ thì giá trị tốt nhất tìm được bởi thuật toán LPSO_H có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 8.5% - 20.7%. Kết quả được trình bày chi tiết trong bảng 2-12 của luận án.
So sánh thuật toán LPSO_H với các thuật toán khác
16
Hình 2.18: So sánh thuật toán LPSO_H và các thuật toán khác với bộ dữ liệu M5081
Chương 3: Giải bài toán CLOS theo phương pháp tiến hóa vi phân
Chương này trình bày các nội dung chính sau:
(i) Phương pháp tiến hóa vi phân dựa trên thông tin định hướng
(ii) Đề xuất thuật toán mới lập lịch luồng công việc trong môi trường điện
toán đám mây MODE dựa trên phương pháp tiến hóa vi phân.
Phương pháp tiến hóa vi phân dựa trên thông tin đối xứng
Định nghĩa 1 (Tính đối xứng): cho x là một số thực, x [a,b]. Khi đó phần
tử đối xứng của x, ký hiệu là được tính như sau:
-1)
Nếu a =0, b=1 thì ta có:
17
Định nghĩa 2 ( Tính đối xứng trong không gian n chiều): xét điểm p(x1,
x2,..,xn) trong không gian n chiều, với xi R và xi [ai, bi]. Khi đó điểm đối
xứng của p kí hiệu là và được tính như sau:
2)
Phương pháp OBL: trong mỗi bước lặp của phương pháp OBL với mỗi
của p, nếu điểm p(x1, x2,…,xn) ta sẽ tính điểm đối xứng
thì điểm sẽ thay thế điểm p (với f là hàm mục tiêu của bài
toán) và quá trình tìm kiếm sẽ được tiếp tục với tập các điểm mới tìm được.
Thuật toán đề xuất MODE
Thuật toán MODE (Modified Opposition-Based Differential Evolution) là thuật toán lập lịch luồng công việc trong môi trường điện toán đám mây nhằm cực tiểu hóa makespan, thuật toán làm việc theo nguyên tắc của thuật toán tiến hóa vi phân dựa trên thông tin đối xứng, tuy nhiên thuật toán được cải tiến ở các điểm sau:
(i) Định nghĩa phương pháp lấy đối xứng cho các cá thể trong quần thể.
(ii)
Sử dụng phương pháp lựa chọn theo vòng dựa trên xếp hạng của cá thể để chọn các cá thể cho quá trình đột biến nhằm sinh ra được cá thể tốt cho thế hệ kế tiếp.
(iii) Sử dụng thông tin đối xứng của các cá thể dựa theo đặc trưng của
bài toán CLOS trong quá trình tìm kiếm.
Phương pháp tìm cá thể đối xứng
Theo phương pháp tiến hóa vi phân dựa trên thông tin đối xứng, trong bước khởi tạo và các bước lặp của thuật toán cần phải tìm ra quần thể đối xứng với quần thể hiện tại. Dựa trên đặc trưng của bài toán CLOS, phần này đề xuất phương pháp tìm các cá thể đối xứng như sau:
18
Kí hiệu:
a = Max{P(Si )}; i=1,2,…,N; P(Si) là năng lực tính toán của máy chủ Si
b = Min{P(Si)}; i=1,2,…,N.
k = (Si(1), Si(2),..,Si(M)) với Si(j) {S1, S2,…,SN} j=1,2,…,M.
k được định nghĩa là cá thể
Cá thể xi
Định nghĩa 1: cá thể đối xứng của cá thể xi
với các thành phần được tính như sau:
(Error! No text of specified style in document..3)
Với là năng lực tính toán của máy chủ
Cách thức gán định danh máy chủ cho các thành phần của vector vị j của vector trí: để gán định danh cho thành phần thứ
ta sẽ tìm máy chủ có năng lực tính toán gần
nhất với giá trị của thành phần j là và gán định danh của máy chủ đó
cho thành phần thứ j trong vector . Công thức gán như sau:
(Error!
No text of specified style in document..4)
Phương lựa chọn theo vòng dựa trên xếp hạng của cá thể
Trong phương pháp DE và ODE toán tử đột biến được tính toán dựa trên việc lựa chọn một cách ngẫu nhiên hai cá thể cha mẹ, sau đó sẽ tính
vector đột biến vi theo công thức: vi(t) pbest + F(p1- p2). Sử dụng chiến
lược đột biến best/1 thường cho chất lượng lời giải tốt và tốc độ hội tụ nhanh hơn các chiến lược rand/1, rand/2.
Thuật toán cải tiến MODE tác giả đã sử dụng phương pháp lựa chọn theo vòng dựa trên xếp hạng của cá thể (RBRWS) để chọn ra các cá thể cho
19
quá trình đột biến, phương pháp RBRWS đã được sử dụng trong nhiều thuật toán tiến hóa và đã được kiểm chứng là giảm sự hội tụ sớm tới các vùng cực trị địa phương, và tránh được sự phụ thuộc vào tính chất đồng đều của giá trị hàm mục tiêu trong quá trình lựa chọn [76].
Phương lựa chọn theo vòng dựa trên xếp hạng của cá thể (Rank-based Roulette Wheel Selection – RBRWS) [76] là phương pháp lựa chọn cá thể trong đó xác suất lựa chọn mỗi cá thể được quyết định dựa trên hạng của cá thể đó trong quần thể, với hạng của cá thể được tính toán theo giá trị hàm mục tiêu đạt được của cá thể. Phương pháp này đầu tiên sẽ tính giá trị hàm mục tiêu cho tất cả các cá thể trong quần thể và sắp xếp chúng theo chiều tăng dần của giá trị hàm mục tiêu tính được, sau đó mỗi cá thể được gán một giá trị vị trí từ 1 đến NP (NP là số cá thể trong quần thể) theo nguyên tắc cá thể có giá trị hàm mục tiêu nhỏ nhất ứng với vị trí là NP, cá thể tiếp theo là NP -1,…, và cá thể có giá trị hàm mục tiêu lớn nhất có vị trí là 1. Hạng của mỗi cá thể trong quần thể được tính theo công thức sau:
(Error! No text of
specified style in document..5)
trong đó: + pos là giá trị vị trí của cá thể i
+ SP là một hằng số trong đoạn [1.0, 2.0]
Thực nghiệm
Tham số môi trường điện toán đám mây và luồng dữ liệu thực nghiệm được trình bày chi tiết trong các bảng PL1-1 đến PL1-39 và PL2-1 đến PL2-3. Kết quả thực nghiệm thuật toán MODE được trình bày chi tiết trong các bảng 3-2, 3-3 và 3-4 của luận án.
20
Đánh giá chất lượng lời giải thuật toán MODE
Với mỗi bộ dữ liệu chuẩn tác giả tiến hành thực nghiệm các thuật toán một cách độc lập với 30 lần thử, các tham số về băng thông giữa các máy chủ, tốc độ tính toán của các máy chủ được thiết lập trong môi trường mô phỏng CloudSim một cách nhất quán cho tất cả các thuật toán trong các lần thử nghiệm. Kết quả thực nghiệm trong các bảng 3-2, 3-3 và 3-4 đã chỉ ra chất lượng lời giải của thuật toán MODE luôn tốt hơn các thuật toán Random, RRTSM, PSO_H và EGA ở cả 3 tham số là độ lệch chuẩn, giá trị trung bình và giá trị tốt nhất.
Giá trị trung bình tìm được bởi thuật toán MODE nhỏ hơn giá trị trung bình
tìm được bởi thuật toán PSO_H từ 2% - 9%, với các bộ dữ liệu thực nghiệm có khối lượng dữ liệu truyền giữa các tác vụ nhỏ thì giá trị trung bình tìm được bởi thuật toán MODE nhỏ hơn thuật toán PSO_H từ 13% - 29%. So với thuật toán EGA giá trị trung bình tìm được bởi MODE nhỏ hơn từ 1.1% - 11%.
Giá trị tốt nhất tìm được bởi thuật toán MODE nhỏ hơn giá trị tốt nhất tìm được bởi thuật toán PSO_H từ 2.1% - 12.5%, với các bộ dữ liệu thực nghiệm có khối lượng dữ liệu truyền qua lại giữa các tác vụ trong luồng công việc nhỏ thì giá trị tốt nhất tìm được bởi thuật toán MODE nhỏ hơn giá trị tốt nhất tìm được bởi thuật toán PSO_H từ 14.5% - 24.6%. Giá trị tốt nhất tìm được bởi MODE nhỏ hơn so với giá trị tốt nhất tìm được bởi thuật
toán EGA từ 1.2% - 9.4%.
Với một số bộ dữ liệu chuẩn thì lời giải tốt nhất tìm được bởi thuật toán MODE bằng với giá trị tối ưu tìm được bởi thuật toán vét cạn như các bộ dữ liệu chuẩn T1032, T1031, T1034, T1035,…, với các bộ dữ liệu khác lời giải tốt nhất tìm được bởi thuật toán MODE có tỷ lệ sai lệch so với giá trị tối ưu tìm được bằng vét cạn từ 0.2% đến 4.3%. Kết quả chi tiết được trình bày trong bảng 3-5, thuật toán MODE có độ lệch chuẩn nhỏ trong hầu
21
hết các bộ dữ liệu đã thử nghiệm, giá trị lệch chuẩn của thuật toán MODE nằm trong đoạn [0, 4.2], đồng thời sự chênh lệch giữa giá trị trung bình và giá trị tốt nhất trong các bộ dữ liệu thực nghiệm cũng khá nhỏ, điều đó chứng tỏ chất lượng lời giải của thuật toán MODE tốt và ổn định trong hầu hết các bộ dữ liệu thực nghiệm
So sánh thuật toán MODE với các thuật toán khác
Định hướng các trường hợp sử dụng các thuật toán đề xuất PSOi_H,
LPSO_H và MODE
Trên cơ sở những khảo sát thực nghiệm các thuật toán theo các tham số về độ lệch chuẩn, giá trị trung bình, giá trị tốt nhất và thời gian chiếm dụng CPU, luận án đề xuất về hướng áp dụng các thuật toán PSOi_H, LPSO_H và MODE cho các loại dữ liệu cụ thể như sau:
• Các đồ thị luồng công việc phức tạp có nhiều tác vụ phân chia và tập hợp dữ liệu, với số tác vụ lớn và khối lượng dữ liệu cần truyền giữa các tác vụ trong luồng công việc lớn thì thuật toán MODE cho chất lượng lời giải tốt nhất, tuy nhiên thời gian sử dụng CPU của các máy chủ trong thuật toán MODE là lớn nhất (xem bảng 3-6). Do vậy khi cần thực hiện việc lập lịch cho các luồng công việc phức tạp với khối
22
lượng dữ liệu cần truyền giữa các tác vụ lớn thì nên sử dụng thuật toán MODE.
• Các đồ thị luồng công việc có cấu trúc đơn giản với hệ số nhỏ hoặc
các đồ thị luồng công việc có cấu trúc dạng đường ống song song, và dữ liệu truyền qua lại giữa các tác vụ trong luồng công việc ít thì thuật toán PSOi_H cho chất lượng lời giải tốt tương đương với hai thuật toán LPSO_H và MODE, tuy nhiên thời gian chiếm dụng CPU ít hơn so với hai thuật toán LPSO_H và MODE (xem bảng 3-7). Do vậy với
các đồ thị luồng công việc có cấu trúc đơn giản, hệ số nhỏ và khối
lượng dữ liệu cần truyền giữa các tác vụ nhỏ thì nên chọn thuật toán PSOi_H.
• Các đồ thị luồng công việc có cấu trúc phức tạp với hệ số lớn, có nhiều tác vụ tập hợp và phân phối dữ liệu trong luồng công việc, khối lượng dữ liệu cần truyền giữa các tác vụ nhỏ thì thuật toán LPSO_H cho chất lượng lời giải tốt hơn so với thuật toán PSOi_H, và tương đương chất lượng lời giải thuật toán MODE. Tuy nhiên thời gian chiếm dụng CPU của thuật toán LPSO_H nhỏ hơn so với thuật toán MODE (xem bảng 3-8). Do vậy trong trường hợp này nên sử dụng thuật toán LPSO_H.
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Từ các nội dung nghiên cứu của luận án rút ra các kết luận sau:
a. Các kết quả chính của luận án
• Phát biểu tường minh bài toán CLOS dưới dạng công thức toán học, xếp loại nó theo phương pháp phân loại Gramham và chứng minh bài toán CLOS thuộc lớp NP-Khó. Theo những tài liệu đã công bố cho
23
tới này mà chúng tôi tìm được, đây là lần đầu tiên bài toán này được phát biểu chính thức và đặt tên.
• Trình bày tổng quan về các phương pháp giải bài toán lập lịch luồng công việc theo hai hướng tiếp cận heuristic và metaheuristic, đồng thời đánh giá ưu nhược điểm của các phương pháp tiếp cận.
• Trình bày về một số luồng công việc trong các ứng dụng khoa học thực tiễn và một số luồng công việc ngẫu nhiên làm dữ liệu mẫu cho thực nghiệm các thuật toán.
• Đề xuất ba thuật toán mới dựa trên phương pháp tối ưu bày đàn và
tiến hóa vi phân để giải bài toán CLOS.
b. Những đóng góp mới của luận án
• Thứ nhất: mô tả bài toán Lập lịch luồng công việc trong môi trường điện toán đám mây dưới dạng ngôn ngữ tự nhiên và dạng ký pháp Graham, đề xuất mô hình toán học cho bài toán, phát biểu bài toán dưới dạng các ràng buộc toán học và chỉ ra nó thuộc lớp NP-Khó.
• Thứ hai: Đề xuất hai thuật toán mới giải bài toán CLOS theo phương pháp tối ưu bày đàn là PSOi_H, LPSO_H và một thuật toán mới giải bài toán CLOS theo phương pháp tiến hóa vi phân là MODE.
• Thứ 3: Kết quả thực nghiệm trên các bộ dữ liệu thực nghiệm với tính đa dạng về các tham số của môi trường điện toán đám mây như băng thông, tốc độ tính toán các máy chủ và nhiều dạng đồ thị luồng công việc khác nhau đã chỉ ra rằng: Các thuật toán đề xuất cho chất lượng lời giải tốt hơn các thuật toán đối chứng là Random, RRTSM, PSO_H và EGA.
24
c. Hướng phát triển của luận án
Luận án đã đề xuất ba thuật toán gần đúng cho bài toán CLOS, để kiểm chứng các thuật toán đó phải so sánh lời giải của chúng với lời giải tối ưu. Chúng tôi đã tìm lời giải tối ưu thông qua phương pháp vét cạn, tuy nhiên phương pháp này chỉ khả thi đối với những bộ dữ liệu kích thước nhỏ. Trong thời gian tới chúng tôi sẽ sử dụng công cụ lập trình song song kết hợp với phương pháp nhánh cận để tìm lời giải tối ưu cho những bộ dữ liệu kích thước vừa và lớn, qua đó kiểm chứng rõ hơn các thuật toán đề xuất đồng thời làm phong phú thêm bộ dữ liệu thực nghiệm mà chúng tôi đã công bố.
Một hướng nghiên cứu khác mà chúng tôi sẽ theo đuổi là áp dụng các phương pháp dự báo nhu cầu tiêu thụ tài nguyên đám mây của khách hàng trong tương lai gần, từ đó lập lịch hiệu quả hơn cho việc phân bổ tài nguyên đám mây.
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ [1]. Phan Thanh Toàn, Kiều Tuấn Dũng, Nguyễn Thế Lộc, Nguyễn Doãn Cường, “Sắp xếp lịch biểu thực thi luồng công việc tại đám mây điện toán”, Hội thảo quốc gia lần thứ XVI, một số vấn đề chọn lọc của công nghệ thông tin và truyền thông (@ 2013), pp. 285-290, 2013.
[2]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Đỗ Như Long, “Thuật toán lập lịch luồng công việc theo phương pháp tối ưu bày đàn trong môi trường điện toán đám mây”, tạp chí Nghiên cứu khoa học và Công nghệ quân sự, pp. 132-138, 2015.
[3]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Đỗ Như Long, “Giải thuật tối thiểu hóa chi phí thực thi luồng công việc trong môi trường điện toán đám mây”, Tạp chí khoa học trường đại học Sư Phạm Hà Nội, pp. 47-55, 2015.
[4]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường , “Thuật toán lập lịch luồng công việc trong môi trường điện toán đám mây”, Proc. Of the 8th National Conference on Foundamental and Applied Information Techonoly Research (FAIR’8), pp. 687-693, 2015.
[5]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, “Thuật toán lập lịch luồng công việc trong môi trường điện toán đám mây dựa trên chiến lược tối ưu bày đàn”, tạp chí Công nghệ thông tin và Truyền thông, pp. 15-20, 2015.
[6]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, “A Novel Workflow Scheduling Algorithm in Cloud Environment”, Proc. Of 2015 2nd National Foundation for Science and Technology Development Conference on Information and Computer Science (NICS’2015), pp. 125-129, 2015.
[7]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, Trần Đăng Hưng, “MODE: Hướng tiếp cận mới cho việc thực thi luồng công việc”, tạp chí khoa học Công nghệ thông tin và Truyền thông, tập 1, số 1, pp. 63-70, 2016. [8]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường , “Thuật toán LPSO lập lịch cho các ứng dụng khoa học trong môi trường điện toán đám mây”, tạp chí Khoa học và Công nghệ, Viện hàn lâm khoa học Việt Nam, pp. 287-299, 2016.
for Workflow Scheduling
[9]. Phan Thanh Toàn, Nguyễn Thế Lộc, Nguyễn Doãn Cường, “A Robus and in Cloud Effective MODE Algorithm Enveronment”, Proc. Of The 7th International Symposium on Information and Communication Technology (SoICT’2016), pp. 259-264, 2016.
[10]. Toan Phan Thanh, Loc Nguyen The, Said Elnaffar and Cuong Nguyen Doan, "LPSO: Another Algorithm for Workflow Scheduling in the Cloud", Journal of Computer Science, ISSN: 1549-3636, DOI: 10.3844/jcssp.2016, pp.611- 617, Volume 12, Issue 12, 2016.
