Đăng ký Đăng nhập
Trang chủ Báo cáo môn học grid computing dynamic workflow management grid & cloud computin...

Tài liệu Báo cáo môn học grid computing dynamic workflow management grid & cloud computing enviroment

.PDF
22
105
120

Mô tả:

ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA KHOA KHOA HỌC KỸ THUẬT MÁY TÍNH …………..o0o………….. Báo cáo môn học GRID COMPUTING DYNAMIC WORKFLOW MANAGEMENT GRID & CLOUD COMPUTING ENVIROMENT Lecturer Dr. Phạm Trần Vũ Reporter Nguyễn Minh Thành May 2014 13070263 Lịch sử tài liệu Ngày Phiên bản Ghi chú Tác giả 04/04/2014 0.1 Khởi tạo sơ thảo yêu cầu báo cáo Thành 2/5/2014 0.4 Background workflow scheduling Thành 28/5/2014 0.8 DCP-G algorithm, heuristic for adaptive workflow management Thành 31/5/2014 1 review, finalize report Thành Mục lục Abstract ....................................................................................................................................................... 3 Keywords ..................................................................................................................................................... 3 I. Introduction .............................................................................................................................................. 3 II. BACKGROUND OF WORKFLOW SCHEDULING ........................................................................................... 4 2.1. Workflow scheduling problem........................................................................................................... 4 2.2. Existing workflow scheduling algorithms ........................................................................................... 4 2.3. Heuristics .......................................................................................................................................... 5 2.3.1. Myopic ....................................................................................................................................... 5 2.3.2. Min–min..................................................................................................................................... 5 2.3.3. Max–min .................................................................................................................................... 6 2.3.4. HEFT ........................................................................................................................................... 7 2.4. Metaheuristics .................................................................................................................................. 8 2.4.1. GRASP ........................................................................................................................................ 8 2.4.2. GA .............................................................................................................................................. 9 III. DCP-G ALGORITHM FOR WORKFLOW SCHEDULING ............................................................................... 10 3.1. Calculation of AEST and ALST in DCP-G ............................................................................................ 11 3.2. Task selection.................................................................................................................................. 11 3.3. Resource selection .......................................................................................................................... 12 3.4. Methodology .................................................................................................................................. 12 3.5. DCP-G example ............................................................................................................................... 12 V. CASE STUDY ........................................................................................................................................... 14 5.1. Testbed setup ................................................................................................................................. 14 5.2. Schedule generation........................................................................................................................ 14 5.3. Discussion ....................................................................................................................................... 15 VI. HEURISTIC FOR ADAPTIVE WORKFLOW MANAGEMENT IN HYBRID CLOUDS .......................................... 17 Dynamic Workflow Management for Grid & Cloud Computing Enviroment 1 VII. CONCLUSIONS ..................................................................................................................................... 21 References................................................................................................................................................. 21 Dynamic Workflow Management for Grid & Cloud Computing Enviroment 2 Abstract Lập kế hoạch hiệu quả là mối quan tâm chính của việc thực hiện các ứng dụng lưới trọng hiệu suất như là workflows. Trình bày cho môn học có đề tài là: “Quản lý workflow linh động trong môi trường tính toán lưới và điện toán đám mây”. Nội dung được phân bố gồm hai phần. Thứ nhất là mô tả vấn đề lập kế hoạch workflow, và các phương pháp hoạch định workflow dựa trên heuristic và mete-heristic hiện có. Phần thứ hai là đề xuất giải thuật hoạch định workflow thích nghi linh động critical-path-based, nhằm xác định tác vụ ánh xạ hiệu quả đến tài nguyên grid linh động thực tế bằng cách tính critical path. Dùng mô phỏng, ta thực hiện so sánh hiệu năng của phương pháp đề xuất với cái hiện có. Kết quả cho thấy kỹ thuật lập kế hoạch heuristic-based có thể thích nghi với tài nguyên linh động thực tế, và tránh suy giảm hiệu suất trong môi trường grid thay đổi linh động. Keywords Workflow management, adaptive scheduling, grid computing, cloud computing I. Introduction Nhiều ứng dụng khoa học qui mô lớn thực thi hiện nay được mô tả là e-Science workflow phức tạp, nó là một tập các tác vụ có thứ tự được liên kết bởi sự phụ thuộc dữ liệu. Một hệ thống quản lý workflow được sử dụng để định nghĩa, quản lý và thực thi các ứng dụng workflow này trên tài nguyên lưới. Một hệ thống quản trị workflow dùng chiến lược hoạch định đặc biệt để ánh xạ các tác vụ trong workflow đến tài nguyên lưới phù hợp nhằm thỏa mãn yêu cầu người dùng. Hình 1.b minh họa thực hiện workflow được mô tả trong hình 1.a trên môi trường tính toán phân bố truyền thống. Figure 1.a : Ví dụ workflow: ứng dụng dự báo thời tiết Figure 1.b: Hệ thống quản trị workflow Figure 1: Ngữ cảnh quản lý ứng dụng workflow thông thường trong môi trường tính toán phân bố Tuy nhiên hầu hết các chiến lược hoạch định này là tĩnh trong thực tế. Họ tạo ra một kế hoạch tốt cho thời điểm hiện tại của tài nguyên lưới mà không tính đến sự thay đổi của tính sẵn sàng của tài nguyên. Vì vậy bài viết này trình bày kỹ thuật hoạch định workflow linh động nhằm không chỉ tối Dynamic Workflow Management for Grid & Cloud Computing Enviroment 3 thiểu linh hoạt thời gian thực hiện workflow mà còn giảm the scheduling overhead, là thời gian đáng kể để tạo kế hoạch. Critical Path (CP) heuristics được dùng rộng rãi để lập lịch các tác vụ độc lập trong hệ thống đa xử lý. Các heuristics này xác định độ dài nhất của các đường thực thi từ khởi đầu đến kết thúc trong đồ họa tác vụ và hoạch định cái dễ nhất để tối thiểu thời gian thực thi cho toàn đồ thị. Giải thuật Dynamic CP (DCP, Kwok & Ahmad 1996) được giới thiệu là giải thuật CP có thể xác định linh hoạt sau mỗi tác vụ được lập lịch. Tuy nhiên giải thuật này được thiết kế để ánh xạ các tác vụ vào các bộ xử lý thuần nhất, và tĩnh, trong giả định là kế hoạch chỉ được tính một lần 1 đồ thị tác vụ. Ta mở rộng giải thuật DCP để ánh xạ và lặp kế hoạch các tác vụ trong workflow trên các tài nguyên hỗn độn trong môi trường lưới linh động. Để đánh giá hiệu suất của giải thuật này gọi là DCP for grids (DCP-G), ta so sánh nó với các phương pháp hiện tại cho nhiều kiểu và kích cỡ workflow khác nhau. Kết quả cho thấy DCP-G có thể thích nghi đến tài nguyên tạm thời, ứng phó và tránh suy giảm hiệu suất trong môi trường lưới thay đổi linh động. II. BACKGROUND OF WORKFLOW SCHEDULING 2.1. Workflow scheduling problem Tổng quát, một ứng dụng workflow được thể hiện là một đồ thị directed acyclic (DAG) trong đó các nút thể hiện tác vụ, các cạnh thể hiện dữ liệu phụ thuộc giữa các tác vụ, với trọng số trong node thể hiện độ phức tạp tính toán. Vì vậy bài toán lập lịch workflow thường được xem là trường hợp đặc biệt của bài toán xếp lịch DAG, là bài toán non-deterministic polynomial (NP). Mặc dù bài toán xếp lịch DAG có thể giải được bằng các phương pháp quét cạn, nhưng độ phức tạp để tạo ra kế hoạch scheduling là rất cao. Thời gian hoàn thành chung của ứng dụng thường được gọi là schedule length hoặc makespan. Vì vậy mục tiêu của kỹ thuật xếp lịch workflow là làm tối giảm makespan của ứng dụng song song bằng cách sắp xếp hợp lý các tác vụ đến bộ xử lý, tài nguyên, và sắp xếp trình tự thực hiện. Hãy xem workflow gồm một tập các tác vụ, , và một tập phụ thuộc giữa các tác vụ, , trong đó là cha của . là tập hợp các tài nguyên sẵn có trong lưới tính toán. Vì vậy, bài toán lập lịch workflow là ánh xạ các tác vụ workflow vào lưới tài nguyên để makespan M là nhỏ nhất. Một tác vụ workflow là một tập các lệnh có thể thực hiện trên một thành phần xử lý đơn lẻ của tài nguyên tính toán. Trong một workflow, một tác vụ gia nhập sẽ không có tác vụ cha, và một tác vụ thoát sẽ không có tác vụ con. Tác vụ con không thể thực hiện được đến khi tất cả tác vụ cha của nó được hoàn tấc. Vào bất cứ lúc nào của lập lịch, tác vụ có tất cả tác vụ cha của nó hoàn thành thì được gọi là tác vụ sẵn sàng. 2.2. Existing workflow scheduling algorithms Vì lập lịch workflow là bài toán NP-complete, nên ta dựa các chiến lược lập lịch heuristic-based và metaheuristic-based để đạt giải pháp tối ưu trong thời gian đa thức. Bảng 1 trình bày các giải thuật heuristic và metaheuristic nổi tiếng cho bài toán xếp lịch trong hệ thống lưới. Phương pháp xếp lịch Myoptic Min-min Max-min HEFT GRASP GA Kiểu xếp lịch Heuristic Heuristic Heuristic Heuristic MetaHeuristic MetaHeuristic Project Condor DAGMan vGrADS vGrADS ASKALON Pegasus ASKALON Tổ chức University of Wiscousin-Madesion, USA Rice University, USA Rice University, USA University of Innsbruck, Austria University of Southern, California University of Innsbruck, Austria HEFT, Heterogeneous Earliest Finish Time; GRASP, greedy randomized adaptive search procedure; GA, genetic algorithm Table 1: Tóm tắc các giải thuật lập lịch workflow Dynamic Workflow Management for Grid & Cloud Computing Enviroment 4 2.3. Heuristics 2.3.1. Myopic Myopic là một heuristic lập lịch tác vụ đơn thể được xem là phương pháp xếp kế hoạch đơn giản nhất cho các ứng dụng lập lịch workflow vì căn bản nó xử lý cho tác vụ đơn lẻ. Nó lập lịch một tác vụ chưa ánh xạ, thứ tự tùy ý đến tài nguyên, với mong muốn hoàn thành tác vụ này sớm nhất, cho đến khi tất cả tác vụ được xếp lịch. 2.3.2. Min–min Một danh sách tác vụ workflow lập lịch có độ ưu tiên heuristic, và việc xếp lịch dựa trên ưu tiên này. Min-min là một danh sách heuristic xếp lịch mà gán độ ưu tiên tác vụ trên cơ sở thời gian hoàn thành kỳ vọng (ECT) trên một tài nguyên. Heuristic này tổ chức tác vụ workflow vào nhiều nhóm tác vụ độc lập và xếp lịch vòng lặp các tác vụ của mỗi nhóm. Trong mỗi vòng lặp, nó lấy một tập tất cả tác vụ độc lập chưa ánh xạ, và tạo các ECT tối thiểu (MCT) cho mỗi tác vụ trong , trong đó ; là tập tài nguyên có sẵn, và là khoảng thời gian tài nguyên dùng để thực hiện tác vụ . Khi tác vụ có giá trị MCT nhỏ nhất trên tất cả tác vụ được chọn để xếp lịch đầu tiên tại vòng lặp này đến tài nguyên tương ứng phù hợp cho MCT này, vì vậy được gọi là min-min. Theo các này, min-min xếp lịch các tác vụ độc lập khác trong và chuyển đến vòng lặp kế đến khi về rỗng. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 5 2.3.3. Max–min Giải thuật Max-min heuristic rất giống với min-min. Điểm khác là max-min đạt độ ưu tiên đến tác vụ cần thời gian thực hiện dài nhất hơn là thời gian thực hiện ngắn nhất. Trong mỗi bước lặp, sau khi có được tập giá trị MCT cho tất cả tác vụ độc lập chưa ánh xạ, một tác vụ có MCT lớn nhất được chọn để xếp lịch trên tài nguyên, với kỳ vọng hoàn thành tác vụ với thời gian sớm nhất. Max-min cố gắng tối thiểu tổng thời gian thực thi bằng cách gán các tác vụ dài nhất đến tài nguyên tốt nhất. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 6 2.3.4. HEFT HEFT là giải thuật lặp lịch danh sách thiết lập tốt, gán độ ưu tiên cao hơn cho workflow có vị trí thứ hạng cao. Vị trí thứ hạng được tính bằng thời gian trung bình cho mỗi tác vụ và thời gian giao tiếp trung bình giữa các tài nguyên của hai tác vụ kế tiếp, khi các tác vụ trong CP có vị trí hạng cao hơn. Khi đó nó sắp xếp tác vụ theo thứ tự giảm dần giá trị thứ hạng, và tác vụ có thứ hạng cao hơn được gán ưu tiên cao hơn. Trong pha chọn tài nguyên, các tác vụ được xếp lịch theo thứ tự độ ưu tiên, mỗi tác vụ được gán đến tài nguyên có thể hoàn thành với thời gian sớm nhất. Ta hãy xem | | là kích thước của tác vụ và là tập các tài nguyên có sẵn với khả năng xử lý trung bình | | ∑ | | . Vì vậy thời gian xử lý trung bình của tác vụ: | | | | (1) Cho ̅̅̅̅ là kích cỡ dữ liệu giao tiếp giữa tác vụ xử lý dữ liệu trung bình ̅ ∑ ̅ và , và R là tập tài nguyên có sẵn với khả năng . Vì vậy thời gian giao tiếp dữ liệu trung bình cho tác vụ: ( và ( ) ̅̅̅̅̅ ̅ (2) ) được dùng để tính thứ hạng của một tác vụ. Đối với tác vụ thoát, giá trị thứ hạng là (3) Giá trị thứ hạng của các tác vụ khác trong workflow có thể được tính đệ qui trên cơ bản của (1), (2), (3), và được mô tả như sau: ( ) (4) Vì workflow được thể hiện như là DAG, các giá trị thứ hạng của các tác vụ được tính bằng cách duyệt đồ thị tác vụ trong breadth-first search (BFS) theo hướng ngược của phụ thuộc tác vụ (là bắt đầu từ exit task) Ưu điểm của HEFT hơn min-min và max-min là trong khi gán độ ưu tiên đến các tác vụ, nó xem xét toàn thể workflow hơn là tập trung vào chỉ các tác vụ độc lập chưa ánh xạ tại mỗi bước lặp. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 7 2.4. Metaheuristics 2.4.1. GRASP GRASP, greedy randomized adaptive search procedure, là kỹ thuật tìm kiếm ngẫu nhiên có lặp. Trong GRASP, có một số vòng lặp dùng để tìm kiếm một giải pháp tối ưu có thể cho tác vụ ánh xạ trên các tài nguyên. Một giải pháp được tạo ra tại mỗi bước lặp, và giải pháp tốt nhất được giữ làm xếp lịch cuối cùng. Thủ tục tìm kiếm này dừng khi thỏa điều kiện dừng. GRASP có thể tạo kết quả lịch tốt hơn các kỹ thuật khác đã nói phía trên vì nó tìm kiếm toàn bộ không gian workflow và tài nguyên có sẵn. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 8 2.4.2. GA Tương tự như GRASP, giải thuật genetic là kỹ thuật áp dụng nguyên lý tiến hóa cho ra giải pháp xếp lịch chất lượng tốt từ không gian tìm kiếm lớn trong thời gian đa thức. GA kết hợp khai thác giải pháp tốt nhất từ tìm kiếm quá khứ với việc khám pháp vùng mới của không gian tìm kiếm. Thay vì tạo giải pháp mới bằng tìm kiếm ngẫu nhiên như GRASP, GA tạo giải pháp mới tại mỗi bước bằng cách điều chỉnh ngẫu nhiên giải pháp tốt được tạo ra ở bước trước, kết quả là xếp lịch tốt hơn có ít thời gian hơn. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 9 III. DCP-G ALGORITHM FOR WORKFLOW SCHEDULING Cho mỗi đồ thị, cận trên và cận dưới của thời gian bắt đầu cho một tác vụ diễn tả biên độ thời gian bắt đầu sớm nhất (AEST) và biên độ thời gian bắt đầu trễ nhất (ALST). Trong giải thuật DCP, các tác vụ trên CP có cùng giá trị AEST và ALST như làm trễ các tác vụ này ảnh hưởng thời gian thực thi toàn thể cho đồ thị tác vụ. Tác vụ đầu tiên trên CP được ánh xạ đến bộ xử lý xác định cho nó. Quy trình này được lặp lại đến khi tất cả tác vụ trong đồ thị được ánh xạ. Tuy nhiên, giải thuật này được thiết kế để lập lịch tất cả các tác vụ trong một đồ thị tác vụ có thời gian tính toán và truyền thông là tùy ý, với hệ thống đa xử lý có số lượng không giới hạn bộ xử lý kết nối với nhau. Nhưng grids là môi trường hỗn tạp và linh động bao gồm tính toán, lưu trữ, tài nguyên mạng lưới với các khả năng và sẵn sàng khác nhau. Vì vậy để làm việc trên grids, giải thuật DCP cần phải mở rộng như sau: Đối với tác vụ, tính giá trị khởi động cho AEST và ALST, cung cấp thời gian thực thi tối thiểu cho tác vụ. Mục tiêu toàn cục là giảm chiều dài của CP tại mỗi pass. Ta tiếp tục nguyên lý của minmin trong đó một tác vụ được gán đến tài nguyên thực hiện nhanh nhất. Để ánh xạ nhiệm vụ trên CP, tất cả tài nguyên sẵn có được xem xét bởi DCP-G, quan tâm chỉ tài nguyên bị chiếm bởi tác vụ cha và con. Cái này vì thời gian thực thi không thay đổi cho các bộ xử lý khác nhau, và chỉ thời gian giao tiếp giữa các task có thể giảm bằng cách gán các tác vụ đến cùng tài nguyên. Tuy nhiên, thời gian tính toán và truyền thông trên lưới là có thay đổi, biến động do sự hỗn tạp tài nguyên. Khi một tác vụ được ánh xạ đến một tài nguyên, thời gian thực thi và thời gian truyền dữ liệu từ nút cha được cập nhật phù hợp. Cái này biến đổi AEST và ALST của tác vụ kế tiếp. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 10 Tiếp theo, ta sẽ thảo luận các đặc trưng căn bản của giải thuật. Phần đầu, ta mô tả kỹ thuật dùng để tính AEST và ALST cần thiết cho việc chọn tác vụ. Sau đó, ta nói về phương pháp chọn của chiến lược chọn tài nguyên. Giải thuật DCP-G được hình thức hóa và mô tả với ví dụ ở phần tiếp theo. Bảng II cung cấp các khái niệm và ý nghĩa được sử dụng trình bày trong các phần sau: Ký hiệu AET(t) ADTT(t) AEST(t,R) ALST(t,R) PC(R) BW(R) DCPL Ý nghĩa Trị tuyệt đối thời gian thực thi của tác vụ t Trị tuyệt đối thời gian truyền dữ liệu của tác vụ t Trị tuyệt đối thời gian bắt đầu sớm nhất của tác vụ t trên tài nguyên R Trị tuyệt đối thời gian bắt đầu trễ nhất của tác vụ t trên tài nguyên R Thời gian truyền dữ liệu giữa tác vụ t và mà được xếp lịch đến tài nguyên Khả năng xử lý của tài nguyên R Băng thông của liên kết mạng kết nối tài nguyên R với lưới toàn cục Độ dài của dynamic critical path trong một workflow và 3.1. Calculation of AEST and ALST in DCP-G Trong DCP-G, thời gian bắt đầu của một tác vụ chưa xác định đến khi nó được ánh xạ vào một tài nguyên. Có hai thuộc tính: trị tuyệt đối thời gian thực thi (AET) của một tác vụ, là thời gian thực thi nhỏ nhất của tác vụ; và trị tuyệt đối thời gian truyền dữ liệu (ADTT), là thời gian nhỏ nhất cần để truyền ra một tác vụ. với và là khả năng xử lý và khả năng truyền của tài nguyên Khi một task t được xếp lịch đến một tài nguyên, giá trị của AET(t) và ADTT(t) được cập nhật tương ứng. Vì vậy giá trị AEST của tác vụ t trên tài nguyên R được định nghĩa là: ( trong đó t có tác vụ cha p, ) là tác vụ cha thứ k , và nếu t là tác vụ ngõ vào. ( ) nếu ( ) nếu t và không được xếp lịch. Ở đây, thời gian truyền thông giữa hai tác vụ được xem là zero, nếu nó được ánh xạ vào cùng tài nguyên, và bằng ADTT của tác vụ cha nếu tác vụ con chưa được ánh xạ. Dùng định nghĩa này, giá trị AEST có thể được tính bằng cách duyệt đồ thị tác vụ bằng phương pháp breadth-first bắt đầu từ các tác vụ ngõ vào. Một khi AEST của tất cả tác vụ được tính, nó có thể tính chiều dài DCP, (DCPL), là chiều dài xếp lịch của workflow được ánh xạ từng phần. DCPL được định nghĩa là: ( ) trong đó n là tổng số các tác vụ trong workflow. Sau khi tính DCPL, giá trị ALST có thể được tính bằng cách duyệt đồ thị tác vụ bằng phương pháp breadth first nhưng theo chiều ngược lại. Vì vậy, ALST của một tác vụ t trong tài nguyên R được định nghĩa: ( ) trong đó t có c tác vụ con, ( ( ) ) là tác vụ con thứ k , và nếu t là một tác vụ thoát. nếu nếu và không được ánh xạ. 3.2. Task selection Trong quá trình xếp lịch, CP trong đồ thị tác vụ quyết định chiều dài lịch của workflow được xếp lịch từng phần. Vì vậy, trong khi xếp lịch, thật cần thiết để gán độ ưu tiên đến các tác vụ trong CP. Tuy nhiên, cùng sự tiến triển quá trình xếp lịch, CP có thể được thay đổi linh động, là một tác vụ trên một CP tại một bước có thể không thuộc CP tại bước kế vì hành vi thay đổi linh động tài nguyên. Đó là lý do, CP trong workflow được gọi là DCP vì nó có thể thay đổi tại mỗi bước của xếp lịch. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 11 Các tác vụ trong DCP có cùng cận trên, cận dưới của thời gian bắt đầu, nghĩa là có cùng AEST và ALST. Vì vậy tác vụ trong DCP-G được xem là trên CP và được gọi là critical task nếu AEST và ALST của nó bằng nhau. Để giảm giá trị của DCPL tại mỗi bước, tác vụ được chọn cho xếp lịch phải là trên CP và có các tác vụ cha không ánh xạ, trong đó các ràng buộc bị phá vỡ khi chọn critical task với AEST thấp nhất. 3.3. Resource selection Sau khi xác định một critical task, ta cần chọn tài nguyên phù hợp cho tài nguyên đó. Ta chọn tài nguyên mà cho thời gian thực thi nhỏ nhất cho tác vụ đó. Cái này được tìm bởi duyệt tất cả tài nguyên có sẵn để tối thiểu thời gian bắt đầu tiềm năng của critical child task trên cùng tài nguyên, trong đó critical child task là cái có sự khác nhau tối thiểu của AEST và ALST. Cuối cùng, critical task được ánh xạ đến tài nguyên mà cung cấp thời gian bắt đầu kết hợp sớm nhất. 3.4. Methodology Đầu tiên, giải thuật DCP-G tính khỏi trị: AET, ADTT, AEST, ALST của tất cả các tác vụ. Sau đó chọn tác vụ có sự khác nhau nhỏ nhất giữa AEST và ALST, trong đó ràng buộc bị phá vỡ bởi chọn cái có AEST nhỏ hơn. Theo trình bày của phần 3.2, tác vụ này là DCP và được gọi là critical task. Critical task con của critical task cũng được xác định theo cách tương tự. Giải thuật tính thời gian bắt đầu của critical task cho tất cả tài nguyên có sẵn có xem xét thời gian kết thúc của tất cả của tác vụ cha, và tìm vị trí bắt đầu có thời gian bắt đầu này với quá trình thực thi. Tài nguyên đó cho thời gian bắt đầu sớm nhất cho cả hai và critical task con của nó được chọn. Sau khi chọn tài nguyên phù hợp R, giải thuật tính thời gian bắt đầu và trong suốt cho trên tài nguyên này, và cập nhật sự bắt đầu thực sự, thời gian thực thi cho tương ứng. Giá trị AEST và ALST của các tác vụ khác được cập nhật tại cuối mỗi bước xếp lịch để xác định critical task kế tiếp. Quá trình này tiếp tục đến khi tất cả tác vụ trong workflow được xếp lịch. 3.5. DCP-G example Hình 2 minh họa giải thuật DCP-G từng bước giải thích ánh xạ các tác vụ trong workflow mẫu. Workflow mẫu gồm có 5 tác vụ là có yêu cầu truyền dữ liệu và thực thi khác nhau. Chiều dài và kích cỡ của output của mỗi tác vụ được trình bày trong hình 2.a, được đo bằng million instruction (MI), gigabytes (GB). Tác vụ được ánh xạ đến hai tài nguyên lưới và có khả năng xử lý (PC) và khả năng truyền dữ liệu (băng thông BW). Đầu tiên giá trị AET và ADTT được tính cho mỗi tác vụ được tính như hình 2.a . Sau đó dùng các giá trị này, AEST và ALST của tất cả các tác vụ được tính theo mục 3.1, (hình 2.b). Vì có cùng AEST và ALST, đang là CP với là tác vụ cao nhất. Sau đó, được chọn như là critical task và ánh xạ đến tài nguyên , cho thời gian kết hợp nhỏ nhất. Tại cuối bước này, chiều dài của workflow là 890. Tương tự, hình 2.c, được chọn như là critical task và ánh xạ đến . Vì cả hai và được ánh xạ đến , thời gian bắt đầu của trên là 700. Vì vậy, được ánh xạ đến như thời gian bắt đầu, thời gian kết thúc trên là 180 và 430. Sau cùng, được ánh xạ đến (hình 2.g), tất cả các tác vụ được ánh xạ, chiều dài tác vụ không thể cải thiện hơn, và chiều dài lịch được xác định là 750. Lịch sau cùng được tạo ra bởi DCP-G như hình 2.h Dynamic Workflow Management for Grid & Cloud Computing Enviroment 12 Figure 2. Ví dụ của xếp lịch workflow dùng dynamic critical path cho giải thuật DCP-G (a) Tính giá trị AET và ADTT cho mỗi tác vụ (b) Tính giá trị AEST và ADTT cho mỗi tác vụ (c) Tinh lại giá trị AEST, ALST, DCPL dựa trên critical tasks mới (d) Tính lại giá trị AEST, ALST, DCPL dựa trên critical tasks mới (e) Tính lại giá trị AEST, ALST, DCPL dựa trên critical tasks mới (f) Tính lại giá trị AEST, ALST, DCPL dựa trên critical tasks mới (g) Tính lại giá trị AEST, ALST, DCPL dựa trên critical tasks mới (h) Kết thúc giải thuật được tạo bởi giải thuật DCP-G Dynamic Workflow Management for Grid & Cloud Computing Enviroment 13 V. CASE STUDY Phần này cung cấp sự nghiên cứu cụ thể tình huống lập lịch thích nghi (adaptive scheduling) và thực thi ứng dụng workflow mẫu trong môi trường dynamic grid có nguồn tài nguyên linh động đa dạng. Để kết hợp sự năng động và đa dạng của môi trường, ta xem xét các kiểu tài nguyên có khả năng xử lý khác nhau được đo lường theo đơn vị triệu lệnh mỗi giây (MIPS) và khả năng kết nối mạng lưới được đo theo Mbps. Kích thước của các task và data truyền giữa các task trong workflow được đo theo MI và GB tương ứng. Ta tạo ánh xạ của workflow tasks đến tài nguyên grid dùng DCP-G heuristic và GA metaheuristic. Tính tổng thời gian thực thi cho 3 kịch bản sau: 1. Môi trường tĩnh, là trạng thái của các tài nguyên không thay đổi trong suốt lúc thực thi workflow. 2. Môi trường động, là khả năng xử lý của các tài nguyên thay đổi trong khi thực thi. 3. Môi trường động, là khi khả năng kết nối mạng đến các tài nguyên thay đổi trong khi thực thi 5.1. Testbed setup Hình 7.a giới thiệu workflow fork-join mẫu có 5 tasks được mô tả bởi mô hình workflow trong phần 4.1.1. Kích cỡ của các task trong workflow và lượng dữ liệu được truyền giữa các task cũng được mô tả tương ứng. Ta giả định rằng tài nguyên có thể thay đổi trong tự nhiên, và để tăng cường độ tin cậy, sau khi thực thi một task t, tài nguyên tương ứng di chuyển dữ liệu trung gian đã tạo đến kho lưu trữ trung tâm, và các tài nguyên được xếp lịch để thực hiện các task t, cần tải dữ liệu từ kho trước khi chúng thực hiện task. Tuy nhiên, nếu cùng tài nguyên thực thi cả t và các task phụ thuộc, khi đó nó không cần tải dữ liệu về từ kho. Trong phạm vi đề tài này, ta xem xét 3 tài nguyên grid được phân bố toàn cục. Hình 7.b mô tả khả năng kết nối giữa các tài nguyên, băng thông của các kết nối mạng của các tài nguyên này đến kho lưu trữ trung tâm. 5.2. Schedule generation Tổng thời gian thực thi của tất cả các tasks trong workflow cho kỹ thuật lập kế hoạch thích nghi và không thích nghi (adaptive and nonadaptive scheduling techniques) được minh họa trong hình 8. Hình 8.a mô tả khả năng xử lý của theo thời gian, hình 8.b mô tả băng thông của kết nối mạng đến các tài nguyên này. Nhận thấy rằng, trạng thái của các tài nguyên không thay đổi theo thời gian vì môi trường là tĩnh. Ngược lại, hình 9 mô tả lập kế hoạch trong môi trường động, khi Dynamic Workflow Management for Grid & Cloud Computing Enviroment 14 khả năng xử lý của rơi từ 1500 tới 750 MIPS trong khoảng thời gian 100-800 s. Tuy nhiên khả năng xử lý của tất cả tài nguyên vẫn giữ nguyên trong suốt thời gian thực thi. 5.3. Discussion Hình 8 cho thấy, nếu trạng thái của môi trường lưới không thay đổi, hiệu suất của cả hai kỹ thuật lập kế hoạch thích nghi và không thích nghi là không suy biến khi thực thi workflow. Vì vậy, cả hai DCP-G và GA tạo kế hoạch như nhau và tốn thời gian thực thi workflow bằng nhau. Tuy nhiên, khi khả năng xử lý bị thay đổi trong lúc thực thi, nonadaptive scheduling scheme như là GA không thể nhận diện khi tài nguyên có thay đổi (khả năng xử lý của giảm suốt 700 s) và điều chỉnh lịch kế hoạch mà giữ ánh xạ task với tài nguyên được tạo lúc đầu. Vì vậy thời gian hoàn thành thực thi bị tăng đến 1340 s (hình 9.d). Ngược lại, với lập lịch đáp ứng, adaptive scheduling scheme, như là DCP-G, điều chỉnh lịch kế hoạch linh động theo tình trạng tài nguyên hiện tại. Vì vậy, DCP-G gán task đến tài nguyên nhanh nhất tại giây thứ 100, và có thể tốn thời gian hoàn thành tất cả tasks là 1180 s (hình 9.c) Dynamic Workflow Management for Grid & Cloud Computing Enviroment 15 Nếu khả năng kết nối mạng lưới đến các tài nguyên bị thay đổi trong lúc thực thi ( trong hình 10.b), GA không thể thích ứng với các thay đổi. Trong khi đó, DCP-G gán đến thay vì khi băng thông của giảm tại giây 100, và tránh suy biến hiệu suất. Vì vậy tổng thời gian hoàn thành thực thi dùng DCP-G là 1115 s, ít hơn cho trường hợp GA trong cùng điều kiện, hình 10.c và 10.d Dynamic Workflow Management for Grid & Cloud Computing Enviroment 16 VI. HEURISTIC FOR ADAPTIVE WORKFLOW MANAGEMENT IN HYBRID CLOUDS Điện toán đám mây đã nổi lên vai trò là nền tảng thế hệ tiếp theo cho đảm trách các ứng dụng khoa học và kinh doanh. Nó cung cấp kiến trúc hạ tầng, nền tảng, phần mềm dạng dịch vụ tạo tính sẵn sàng cung cấp người dùng các dịch vụ theo yêu cầu hoặc đăng ký sử dụng theo mô hình trả phí theo mức dùng (pay as you go). Clouds được triển khai theo hai dạng: public cloud và private cloud. Public cloud, (hay external cloud) mô tả điện toán đám mây là các dịch vụ cung cấp linh động theo yêu cầu và cơ bản tự phục vụ qua internet và trả phí cho nhà cung cấp. Private cloud (hay internal cloud) nói đến dịch vụ điện toán đám mây trên mạng riêng thông qua sự ảo hóa. Hình 11 mô tả một hybrid cloud là kết hợp của public cloud và private cloud nhắm đến phục vụ yêu cầu có tính tổ chức của baseline computing thông qua private cloud và peak computing dùng public clouds. Ví dụ, hình 11, một tổ chức có thể dùng dịch vụ tính toán mây riêng để triển khai trong các cụm cục bộ cho các ứng dụng có nhiệm vụ quan trọng và quan tâm bảo mật, security, hay dùng dịch vụ public cloud như Amazon Simple Storage Service (Amazon S3) để lưu trữ dữ liệu dạng backup. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 17 Môi trường điện toán đám mây không chỉ linh động mà còn đa dạng với nhiều kiểu dịch vụ (như kiến trúc hạ tầng, nền tảng, phần mềm) được cung cấp bởi rất nhiều nhà cung cấp dịch vụ. Các ứng dụng workflow phân tích dữ liệu hoạch định (hình 12 và 13) cần xác định một số vấn đề, bao gồm tối giảm chi phí và thời gian thực thi, thỏa mãn ràng buộc QoS, chất lượng dịch vụ, xem xét biến động theo thời gian của môi trường. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 18 Kỹ thuật hoạch định chính yếu được cung cấp để giải quyết các vấn đề này là dựa trên metaheuristics, tạo ra hoạch định tốt với trạng thái hiện tại của các dịch vụ đám mây, và đăng ký giữ chỗ các dịch vụ dạng nâng cao. Tuy nhiên lại thiếu khả năng thích nghi với các thay đổi dịch vụ trong suốt quá trình thực thi. Mặt khác, kỹ thuật hoạch định dựa trên heuristic được thảo luận trong bài viết này là linh động tự nhiên và các task workflow đến các dịch vụ đang có, on-the-fly, nhưng thiếu khả năng tạo kế hoạch xem xét tối ưu mức workflow và ràng buộc QoS như là hạn thời gian, ngân sách. Vì vậy cần thiết để phát triển hybrid heuristic có thể tích hợp hiệu quả hầu hết lợi ích của cả hai cách tiếp cận metaheuristic và heuristic, nhằm tối ưu thời gian và chi phí thực thi cũng như đáp ứng các yêu cầu của người sử dụng đến kiểu cách, hình thức có tính thích nghi, nhằm quản lý hiệu quả sự linh động, đa dạng của môi trường hybrid cloud. Dynamic Workflow Management for Grid & Cloud Computing Enviroment 19
- Xem thêm -

Tài liệu liên quan

Tài liệu vừa đăng