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

33 Chương 5. THỬ NGHIỆM VÀ ĐÁNH GIÁ Khả năng của thuật giải mới được chứng minh bằng cách triển khai thử nghiệm với một bộ thông tin tài nguyên và ứng dụng được sinh ra liên tục và hỗn tạp đúng như tính chất của dữ liệu trên môi trường lưới. Các thuật giải đã có như Min-Min, Max-Min, Sufferage,… cũng được triển khai và thử nghiệm với bộ dữ liệu này nhằm có được một nhìn nhận rõ ràng hơn về khả năng của các thuật giải đề xuất. Đề tài đã thực hiện các mô phỏng để so sánh thời gian hoàn thành các ứng dụng khi sử dụng bảy giải thuật định thời: SufMin, DMin-Min, DMax-Min, DSufferage, Min-Min, Max-Min và Sufferage. Để thực hiện các mô phỏng này, đề tài xây dựng một bộ giả lập các thông tin về ứng dụng cần hoàn thành và giả lập các thông tin về tài nguyên lưới (luôn thay đổi theo thời gian). Dữ liệu đầu vào là một tập gồm n ứng dụng ban đầu, sau đó n thay đổi theo thời gian. Mỗi ứng dụng có một số lượng (tối đa là m_lNumTaskMax) các tác vụ và mỗi tác vụ có độ lớn cực đại là m_lMaxTaskSize. Tương tự, dữ liệu đầu vào còn có m bộ tài nguyên ban đầu, sau đó m tài nguyên này thay đổi theo thời gian. Việc này mô phỏng sự thay đổi liên tục của môi trường lưới. Mỗi tài nguyên có một số lượng (tối đa là m_lNumHostMax) các host với khả năng xử lý cực đại của mỗi host là m_lMaxHostsCapability. Ngoài ra, mỗi ứng dụng còn có thông tin về thời điểm đệ trình (submit), thông tin này là cần thiết khi giả lập, còn trong hệ thống thực ta không cần thông tin này vì ta đã có thời gian thực làm thông tin. Như đã đề cập ở phần 3.3, makespan là thời gian để hoàn thành tất cả các ứng dụng, nhưng các giải thuật đề nghị không tập trung định thời cho một nhóm ứng dụng cố định mà số lượng các ứng dụng này luôn thay đổi theo thời gian. Chính vì vậy nên đề tài không sử dụng makespan làm tiêu chuẩn cho mức độ hiệu quả của giải thuật. Thay vào đó, đề tài sử dụng thời gian hoàn thành trung bình của các ứng dụng làm thước đo tiêu chuẩn. Các dữ liệu đầu vào và đầu ra được ghi trên tập tin Excel với mục đích dễ dàng so sánh kết quả giữa các thuật giải khác nhau. ứng dụ cho th không ể (đ h ) Biểu đồ Trong thử ng có nhiề ấy trường h đáng kể kh 0 10 20 30 40 50 60 70 80 DMaxMin DMinMin DSufferage SufMin Max‐Min Min‐Min Sufferage T hờ i đ iể m h oà n th àn h (đ ơn  v ịt h ời  g ia n ) 1: Số cụm tà nghiệm 1, u tác vụ c ợp này thờ i áp dụng c Ud 1 41 41 41 41 36 70.75 36 i nguyên 3, tổ số lần thự on độc lập i gian hoàn ác giải thu 3 Thử 34 ng số host 8, c thi lặp lại và chỉ thực thành trun ật khác nha Ud 2 58.6 61 57.8 58.6 62.3 5.55 62.3 nghiệ số ứng dụng 3 của mỗi ứ thi một lư g bình của u. Ud 3 22 14.55 22 22 52.8 14.55 22 m 1 , tổng số tác v ng dụng là ợt là hoàn các ứng d ụ 11 1, đây là d thành. Kết ụng chênh Tb 40.53 38.85 40.27 40.53 50.37 40.28 40.1 ạng quả lệch nhưng thấy th tiến đề khác c SufMi toàn h ứng d không của m Suffer Biểu đồ Trong thử số lần thự ời gian ho u nhỏ hơn ho thấy kh n cho kết q ợp lý do đị ụng đó ph quan tâm ột ứng dụn age (ứng dụ Sau đây là 0 20 40 60 80 100 120 140 160 180 200 DMaxMin DMinMin DSufferage SufMin Max‐Min Min‐Min Sufferage T hờ i đ iể m h oà n th àn h (đ ơn v ị t hờ i g ia n) 2: Số cụm tà nghiệm 2, c thi lặp lạ àn thành tr so với các i N càng l uả càng tố nh nghĩa b ải kết thúc đến điểm y g trong giải ng 2) khá một số kết Ud 1 114.87 81 81 81 71 181.84 71 i nguyên 3, tổ cũng với i của mỗi ung bình c giải thuật M ớn, các giả t so với M ài toán là m . Các giải ếu này nên thuật Min lớn do ứng quả thử ng U 1 1 1 1 10 16 Th 35 ng số host 8, các ứng dụ ứng dụng l ủa các ứng ax-Min, M i thuật DM ax-Min, M ột ứng dụ thuật định trong một -Min (ứng d dụng phải hiệm khác d 2 117 44.2 45.8 44.2 68.3 4.64 5.49 ử nghiệ số ứng dụng 3 ng và tài n à N (N>1) dụng khi in-Min, S ax-Min, D in-Min, Su ng kết thúc thời Min-M số trường ụng 1), M đợi vài côn : Ud 3 106 82.29 82.29 82.29 171.8 82.29 127 m 2 , tổng số tác v guyên như . Kết quả t áp dụng cá ufferage. C Min-Min, fferage. Đi nếu mọi c in, Max-M hợp thời g ax-Min (ứn g việc đượ 1 1 1 1 1 ụ 11 thử nghiệ hử nghiệm c giải thuậ ác thử ngh DSufferag ều này là h ông việc tr in, Suffe ian hoàn th g dụng 3) h c định thời Tb 12.62 102.5 03.03 102.5 37.03 22.92 21.16 m 1 cho t cải iệm e và oàn ong rage ành oặc trễ. tổng s như tr các gi với trư do số nhau n D D D S M M S Biểu đồ 3 Thử nghiệ ố tác vụ nh ong thử ngh ải thuật kh ờng hợp tổ lượng host hiều. 0 5 10 15 20 25 MaxMin MinMin Sufferage ufMin ax‐Min in‐Min ufferage Th ời đ iể m h oà n th àn h (đ ơn  v ịt h ời  g ia n ) : Số cụm tài n m 3 được ỏ so với tổ iệm 1, thờ ác nhau ch ng số tác v nhiều dẫn Ud 1 9.87 9.87 9.87 9.87 8.86 10.13 8.86 guyên 13, tổn thực hiện v ng số host i gian hoàn ênh lệch kh ụ nhỏ so v đến các tá Ud 2 U 6.57 9 6.57 8 6.57 9 6.57 8 5.77 8 6.8 8 8.1 9 Thử 36 g số host 308 ới các ứng (147 so vớ thành trun ông đáng ới tổng số h c vụ trong d 3 Ud .01 16. .44 18 .01 16. .27 18 .91 13. .71 18. .23 12. nghiệm , số ứng dụng dụng khô i 308), kết g bình của kể. Một số ost cũng c cùng ứng  4 Ud 5 24 6.85 .3 5.98 24 6.85 .3 6.85 33 6.93 17 6.52 74 8.11 3 6, tổng số tác ng thực thi quả cho th các ứng dụ kết quả th ho kết quả dụng khôn Ud 6 16.59 15.63 16.59 15.63 17.75 23.23 14.12 vụ 147 lặp lại (N ấy cũng g ng khi áp d ử nghiệm k tương tự, đ g phải chờ Tb 10.86 10.8 10.86 10.91 10.26 12.26 10.19 =1), iống ụng hác ó là lẫn Suf DM DM DSu Ma Min Suf T h ờ i g i a n h o à n t h à n h ( đ ơ n v ị t h ờ i g i a n ) 0 200 400 600 800 1000 1200 1400 1600 Ud 1 Min 671 ax‐Min 188 in‐Min 125 fferage 671 x‐Min 1093 ‐Min 1523 ferage 1093 Biểu đồ 4: Số Ud 2 Ud 3 97 93 132 146 23 278 97 100 847 290 271 153 258 143 cụm tài nguyên 2 Ud 4 Ud 5 24 175 93 108 242 63 402 70 976 1165 1207 566 1064 664 T 37 1, tổng số host 95 Ud 6 Ud 7 181 73 550 93 264 93 161 183 658 675 122 820 173 722 hử nghiệ 1, số ứng dụng 14 Ud 8 Ud 9 198 93 456 262 94 305 316 332 287 851 458 256 398 396 m 4 , tổng số tác vụ 77 Ud 10 Ud 11 70 305 118 140 391 122 92 133 589 290 577 423 720 400 8 Ud 12 Ud 13 429 341 290 689 145 277 605 32 407 147 444 105 531 171 Ud 14 TB 248 214.14 32 235.5 872 235.29 575 269.21 733 643.43 714 545.64 905 545.57 0 10000 20000 30000 40000 50000 60000 DMaxMi DMinMin DSuffera SufMin Max‐Min Min‐Min Sufferag T h ờ i đ i ể m h o à n t h à n h ( đ ơ n v ị t h ờ i g i a n ) Ud 1 Ud 2 n 496.7 859.2 185.3 1144. ge 228.3 658.2 572.2 859.2 40555 750.3 912.1 29046 e 225.6 1393. Biểu đồ 5: Số Ud 3 Ud 4 U 372.1 859.9 6 289.2 203.7 9 572.2 366.1 5 324.5 1320 6 38155 36264 1 761 595.9 58 1322 1586. 8 cụm tài nguyên 1 d 5 Ud 6 Ud 7 10.5 322.5 234. 45.0 434.4 115. 61.1 293.2 457. 10.5 408.4 884. 023. 1402 109. 107 3458. 140. 375. 15593 1581 T 38 0, tổng số host 144 Ud 8 Ud 9 7 88 884.9 3 16.77 353.4 2 82.85 1026. 4 116.5 579.4 2 1418. 39734 5 11231 6054. 2 1407. 33179 hử nghi , số ứng dụng 18 Ud 10 Ud 11 Ud 671.0 1375. 69 341.4 1329 65 262.1 1551. 48 716.4 1375. 49 38581 16804 38 7047. 15413 80 32204 30321 33 ệm 5 , tổng số tác vụ 37  12 Ud 13 Ud 14 5.6 1156. 926.4 8.6 1206. 289.0 8.8 1093. 475.7 6.7 1158. 634.6 348 4823. 35596 19 25080 6766 000 3208. 32638 0 Ud 15 Ud 16 1190. 597.0 862.9 564.3 633.2 1228. 1125 1079 38396 7909 . 17597 18694 45359 13631 Ud 17 Ud 18 T 1142. 1100. 75 628.1 1092. 59 511.0 858.4 63 1143. 1136. 80 21728 35260 220 18226 11208 132 31839 38133 188 b 4.6 2.2 0.4 7.8 48 42 46 Th ờ i đ i ể m h o à n t h à n h ( đ ơ n v ị t h ờ i g i a n ) 1 10 100 1000 10000 100000 1000000 10000000 DMaxMin DMinMin DSufferage 1 SufMin Max‐Min 1 Min‐Min 1 Sufferage 1 T h ờ i đ i ể m h o à n t h à n h ( đ ơ n v ị t h ờ i g i a n ) Ud 1 Ud 2 171 1832.99 171 26.26 55.37 162.24 171 570.4 22.76 57.61 74.21 30.5 56.34 44 Biểu đồ 6: Số c Ud 3 U 53.58 55 83.23 11 53.58 13 53.58 47 45.08 55 132.43 50 68.86 284 ụm tài nguyên 13 d 30 Ud 31 2.07 1808.45 98.23 137.35 50.68 1525.39 5.26 1075.1 2092 710734.5 1983 35063 428.8 301786.8 39 , tổng số host 116 Ud 32 Ud 1687 134 120.64 44 1507.59 95 1140.11 140 727088.6 40 92013 38 414350.0 266 Thử n , số ứng dụng 100  68 Ud 69 9.29 1322.58 5.01 97.37 1.82 846.22 4.93 190.74 3413 313183 7193 1155476. 714.2 264956.8 ghiệm 6 , tổng số tác vụ 11 Ud 70 Ud 1678.21 174 741.73 157 889.36 174 1857.6 178 590582 186 825502 1184 355845.1 2617 32  98 Ud 99 8.2 1799.04 1.69 257.14 2.13 618 4.42 522 043 422783 015. 67313 71.5 96923.2 Ud 100 Tb 1904.61 1335 2203.08 761 1644.3 992 1706.51 963 370153 46679 1184969. 5423 273024.6 2683 .44 .65 .44 .57 5.5 50.0 30.4 40 Các thử nghiệm 4, 5, 6 cho thấy trong trường hợp tổng số host càng nhỏ so với tổng số tác vụ thì các giải thuật do đề tài đề xuất càng cho kết quả tốt so với các giải thuật Max-Min, Min-Min và Sufferage. Các giải thuật Max-Min, Min-Min và Sufferage không hoàn toàn hướng đến giải quyết bài toán mà luận văn đặt ra vì quan hệ giữa các tác vụ trong từng ứng dụng chưa được khai thác nên khi số ứng dụng tăng lên, các tác vụ của các ứng dụng khác nhau được định thời đồng thời, dẫn đến các ứng dụng không thể hoàn thành sớm do phải chờ lẫn nhau, dẫn đến thời gian hoàn thành ứng dụng lớn (thử nghiệm 6). Các giải thuật đề xuất giải quyết được vấn đề này khi nó ưu tiên định thời dứt điểm từng ứng dụng một. Từ các biểu đồ trên ta thấy trong từng trường hợp cụ thể, thuật giải này có thể tốt hơn thuật giải kia (do ứng dụng A có thể được ưu tiên định thời trước ứng dụng B trong giải thuật này nhưng B lại được ưu tiên định thời trước trong giải thuật khác) nhưng trong trường hợp trung bình, các thuật giải do đề tài đề xuất thường cho kết quả tốt hơn các thuật giải đã có.