Tổng quan nghiên cứu

Trong bối cảnh phát triển nhanh chóng của các ứng dụng khoa học quy mô lớn, nhu cầu về sức mạnh tính toán vượt quá khả năng của một máy tính đơn lẻ ngày càng tăng cao. Theo ước tính, các bộ dữ liệu khoa học có thể lên đến hàng terabytes hoặc petabytes, đòi hỏi môi trường tính toán hiệu năng cao như cluster, grid hoặc điện toán đám mây (cloud computing) để xử lý trong thời gian hợp lý. Workflow được sử dụng như một mô hình phổ biến để mô tả các ứng dụng khoa học này, trong đó các công việc tính toán có sự phụ thuộc dữ liệu lẫn nhau được biểu diễn dưới dạng đồ thị có hướng không chu trình (DAG).

Vấn đề nghiên cứu trọng tâm của luận văn là bài toán lập lịch workflow trên nền tảng điện toán đám mây nhằm giảm thiểu tổng thời gian thực thi (makespan) của các ứng dụng workflow. Mục tiêu cụ thể bao gồm xây dựng các mô hình quy hoạch tuyến tính nguyên (ILP) để làm rõ bản chất toán học của bài toán, đồng thời đề xuất giải thuật heuristic MM-HEFT để giải quyết bài toán lập lịch đa workflow trên các cụm tài nguyên phân tán trong môi trường cloud. Phạm vi nghiên cứu tập trung vào các workflow khoa học thực thi trên các cụm tài nguyên ảo (VM) trong môi trường cloud, với dữ liệu thực nghiệm dựa trên bộ dữ liệu Pegasus, mô phỏng năm loại workflow khoa học phổ biến như Montage, Cybershake, Epigenomics, LIGO và SIPHT.

Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao hiệu quả sử dụng tài nguyên tính toán phân tán, giảm thiểu thời gian hoàn thành các workflow khoa học, từ đó góp phần thúc đẩy tiến trình nghiên cứu khoa học và ứng dụng công nghệ điện toán đám mây trong quản lý và thực thi các tác vụ phức tạp.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

  • Lập lịch công việc độc lập và workflow: Bao gồm các giải thuật lập lịch như MET (Minimum Execution Time), MCT (Minimum Completion Time), Min-Min, Max-Min cho các tác vụ độc lập, và HEFT (Heterogeneous Earliest Finish Time), Hybrid heuristic cho các workflow có phụ thuộc dữ liệu.
  • Mô hình quy hoạch tuyến tính nguyên (ILP): Hai mô hình ILP được xây dựng để biểu diễn bài toán lập lịch workflow, với các biến quyết định nhị phân thể hiện việc phân bổ task đến VM và thời điểm thực thi, cùng các ràng buộc về thứ tự thực thi, không trùng lặp và liên tục.
  • Thuật ngữ chuyên ngành: Workflow DAG, makespan, VM (Virtual Machine), bandwidth, precedence constraint, heuristic algorithm, integer linear programming.

Ba khái niệm chính được sử dụng là:

  1. Workflow DAG: Đồ thị có hướng không chu trình biểu diễn các task và sự phụ thuộc dữ liệu.
  2. Makespan: Tổng thời gian hoàn thành thực thi toàn bộ workflow.
  3. Heuristic scheduling: Giải thuật gần đúng nhằm tối ưu thời gian thực thi trong môi trường phân tán.

Phương pháp nghiên cứu

Nguồn dữ liệu sử dụng là bộ sinh workflow Pegasus, tạo ra các workflow khoa học với kích thước và cấu trúc tương tự thực tế. Nghiên cứu sử dụng phương pháp kết hợp:

  • Phân tích lý thuyết và xây dựng mô hình toán học: Phát triển hai mô hình ILP cho bài toán lập lịch workflow, xác định hàm mục tiêu và các ràng buộc.
  • Phát triển giải thuật heuristic MM-HEFT: Kết hợp giải thuật Min-Min và HEFT để lập lịch đồng thời nhiều workflow trên các cụm tài nguyên phân tán, có xét đến giới hạn băng thông và thời gian sẵn sàng của VM.
  • Thực nghiệm mô phỏng: Sử dụng Gurobi solver để giải các mô hình ILP, chạy mô phỏng với các workflow có số lượng task từ 20 đến hơn 3400, trên môi trường giả lập gồm 11 cụm tài nguyên với số lượng VM và băng thông ngẫu nhiên.
  • Phân tích kết quả: Đánh giá dựa trên các chỉ số thời gian tính toán, makespan, speedup và so sánh với các giải thuật HEFT và Hybrid.BMCT.

Timeline nghiên cứu kéo dài từ tháng 1 đến tháng 11 năm 2013, với các bước từ xây dựng mô hình, phát triển giải thuật đến thực nghiệm và đánh giá.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

  1. Hiệu quả của mô hình ILP: Mô hình 1 cho thấy hiệu quả tính toán vượt trội hơn mô hình 2 với thời gian tính toán tối ưu trung bình giảm khoảng 20-30%, số vòng lặp solver giảm đáng kể, và lower bound gần với lời giải tối ưu hơn. Ví dụ, với workflow Montage và SIPHT, mô hình 1 đạt thời gian tính toán nhanh hơn mô hình 2 tới 25%.

  2. Hiệu quả giải thuật MM-HEFT: Khi lập lịch đồng thời nhiều workflow trên các cụm tài nguyên phân tán, MM-HEFT giảm makespan trung bình từ 10-30% so với các giải thuật HEFT và Hybrid.BMCT, đặc biệt khi số lượng workflow lớn (từ 60 đến 100 workflow). Ví dụ, với 100 workflow, makespan của MM-HEFT là khoảng 683 đơn vị thời gian, trong khi HEFT và Hybrid.BMCT lần lượt là 49596 và 26183.

  3. Tăng tốc độ thực thi (speedup): MM-HEFT đạt speedup trung bình khoảng 7.6 lần so với thực thi tuần tự trên một cụm tài nguyên, trong khi HEFT và Hybrid.BMCT không có speedup đáng kể (bằng 1) do tập trung thực thi trên một cụm duy nhất.

  4. Thời gian chạy giải thuật: MM-HEFT có thời gian chạy trung bình thấp hơn đáng kể so với các giải thuật so sánh, phù hợp với yêu cầu thực thi thường xuyên trong môi trường cloud.

Thảo luận kết quả

Nguyên nhân chính của hiệu quả vượt trội của MM-HEFT là do chiến lược phân bổ mỗi workflow vào một cụm tài nguyên riêng biệt, giảm thiểu chi phí truyền dẫn dữ liệu lớn giữa các cụm, đồng thời tận dụng tối đa khả năng tính toán phân tán. Trong khi đó, các giải thuật HEFT và Hybrid.BMCT khi áp dụng cho bài toán đa workflow thường gộp các workflow thành một workflow hợp nhất và ép thực thi trên một cụm tài nguyên, dẫn đến tắc nghẽn tài nguyên và tăng makespan.

Kết quả mô phỏng được minh họa qua biểu đồ Gantt thể hiện sự phân bổ task hợp lý trên các VM và cụm tài nguyên, cũng như các biểu đồ so sánh thời gian hoàn thành và speedup. So sánh với các nghiên cứu trước đây cho thấy MM-HEFT phù hợp hơn với môi trường cloud phân tán có giới hạn băng thông và thời gian sẵn sàng tài nguyên.

Đề xuất và khuyến nghị

  1. Áp dụng giải thuật MM-HEFT trong hệ thống quản lý workflow trên cloud: Động từ hành động là "triển khai", mục tiêu là giảm makespan trung bình ít nhất 20%, thời gian thực hiện trong vòng 6 tháng, chủ thể thực hiện là các nhà phát triển phần mềm quản lý tài nguyên cloud.

  2. Tối ưu hóa băng thông và phân bổ tài nguyên dựa trên đặc tính workflow: Đề xuất "xây dựng" module phân tích đặc tính workflow để phân bổ cụm tài nguyên phù hợp, nhằm giảm chi phí truyền dẫn dữ liệu, thực hiện trong 3 tháng, chủ thể là nhóm nghiên cứu và kỹ sư mạng.

  3. Phát triển công cụ mô phỏng và đánh giá hiệu quả lập lịch: "Phát triển" phần mềm mô phỏng dựa trên bộ dữ liệu Pegasus để đánh giá các giải thuật lập lịch mới, mục tiêu nâng cao độ chính xác mô phỏng, thời gian 4 tháng, chủ thể là nhóm nghiên cứu khoa học máy tính.

  4. Nâng cao khả năng mở rộng của giải thuật MM-HEFT: "Cải tiến" thuật toán để xử lý số lượng workflow lớn hơn 1000, giảm độ phức tạp tính toán, thời gian thực hiện 1 năm, chủ thể là các nhà nghiên cứu và kỹ sư phần mềm.

Đối tượng nên tham khảo luận văn

  1. Nhà nghiên cứu và sinh viên ngành Khoa học Máy tính: Có thể sử dụng luận văn làm tài liệu tham khảo về lập lịch workflow, mô hình toán học và giải thuật heuristic trong điện toán đám mây.

  2. Kỹ sư phát triển hệ thống điện toán đám mây: Áp dụng các giải thuật lập lịch hiệu quả để tối ưu hóa việc phân bổ tài nguyên và giảm thời gian thực thi ứng dụng.

  3. Quản lý dự án công nghệ thông tin: Hiểu rõ các yếu tố ảnh hưởng đến hiệu năng hệ thống phân tán, từ đó đưa ra quyết định đầu tư và triển khai phù hợp.

  4. Nhà phát triển phần mềm quản lý workflow khoa học: Tận dụng các mô hình và giải thuật đề xuất để xây dựng các công cụ lập lịch workflow hiệu quả, đáp ứng nhu cầu thực tế.

Câu hỏi thường gặp

  1. Workflow là gì và tại sao cần lập lịch?
    Workflow là chuỗi các công việc có sự phụ thuộc dữ liệu lẫn nhau, được biểu diễn dưới dạng đồ thị DAG. Lập lịch giúp phân bổ các công việc này lên tài nguyên tính toán phân tán sao cho tối ưu thời gian và chi phí thực thi.

  2. Tại sao điện toán đám mây phù hợp cho thực thi workflow khoa học?
    Điện toán đám mây cung cấp tài nguyên tính toán hiệu năng cao, khả năng mở rộng linh hoạt và chi phí thuê tài nguyên theo nhu cầu, đáp ứng tốt các yêu cầu tính toán lớn và dữ liệu khổng lồ của workflow khoa học.

  3. Mô hình quy hoạch tuyến tính nguyên (ILP) giúp gì cho bài toán lập lịch?
    ILP cung cấp cách biểu diễn toán học chính xác bài toán lập lịch, giúp tìm lời giải tối ưu bằng các solver chuyên dụng, từ đó đánh giá hiệu quả các giải thuật heuristic.

  4. Giải thuật MM-HEFT khác gì so với HEFT truyền thống?
    MM-HEFT kết hợp Min-Min và HEFT, tập trung lập lịch đồng thời nhiều workflow trên nhiều cụm tài nguyên phân tán, giảm thiểu chi phí truyền dẫn dữ liệu và tận dụng tối đa tài nguyên, trong khi HEFT chỉ áp dụng cho một workflow trên một cụm tài nguyên.

  5. Làm thế nào để đánh giá hiệu quả của giải thuật lập lịch?
    Hiệu quả được đánh giá qua các chỉ số như thời gian hoàn thành thực thi (makespan), tốc độ tăng tốc (speedup), thời gian chạy giải thuật và khả năng mở rộng khi số lượng workflow tăng lên.

Kết luận

  • Luận văn đã xây dựng thành công hai mô hình quy hoạch tuyến tính nguyên cho bài toán lập lịch workflow trên điện toán đám mây, trong đó mô hình 1 cho hiệu quả tính toán vượt trội hơn.
  • Đã đề xuất giải thuật heuristic MM-HEFT, kết hợp Min-Min và HEFT, giải quyết hiệu quả bài toán lập lịch đồng thời nhiều workflow trên các cụm tài nguyên phân tán với giới hạn băng thông.
  • Kết quả thực nghiệm cho thấy MM-HEFT giảm đáng kể thời gian hoàn thành thực thi và tăng tốc độ xử lý so với các giải thuật hiện có như HEFT và Hybrid.BMCT.
  • Nghiên cứu góp phần nâng cao hiệu quả sử dụng tài nguyên điện toán đám mây trong thực thi các ứng dụng khoa học quy mô lớn.
  • Các bước tiếp theo bao gồm mở rộng giải thuật cho số lượng workflow lớn hơn, phát triển công cụ mô phỏng và ứng dụng thực tế trong các hệ thống quản lý workflow trên cloud.

Độc giả và các nhà nghiên cứu được khuyến khích áp dụng và phát triển tiếp các kết quả này nhằm nâng cao hiệu quả quản lý và thực thi workflow trong môi trường điện toán đám mây hiện đại.