Tổng quan về luận án

Luận án này tiên phong trong lĩnh vực lập lịch tác vụ cho các hệ thống máy tính dị thể, giải quyết thách thức cốt lõi về hiệu suất trong các môi trường điện toán quy mô lớn như cụm máy tính (computational clusters) và lưới điện toán (computational grids). Bằng cách giới thiệu ba thuật toán lập lịch mới — Heterogeneous Critical Node First (HCNF), Heterogeneous Largest Task First (HLTF) và Earliest Finish Time with Dispatch Time (EFT-DT) — nghiên cứu này cung cấp các giải pháp mạnh mẽ để tối ưu hóa thời gian hoàn thành (makespan) của các ứng dụng hiệu năng cao. Nghiên cứu tập trung vào việc vượt qua những hạn chế của các phương pháp hiện có, đặc biệt là trong bối cảnh các vấn đề lập lịch thường thuộc loại NP-complete, đòi hỏi các thuật toán xấp xỉ hoặc heuristics hiệu quả.

Research Gap SPECIFIC với citations từ literature: Mặc dù các hệ thống meta-computing dị thể như cụm và lưới đã cung cấp một giải pháp thay thế hiệu quả về chi phí cho siêu máy tính, nhưng "lập lịch hiệu quả các ứng dụng như vậy trên các hệ thống meta-computing là rất quan trọng để đáp ứng thời hạn" (tr. iv). Khoảng trống nghiên cứu chính nằm ở việc thiếu các thuật toán lập lịch hiệu quả hơn có thể xử lý các đặc điểm phức tạp của các môi trường dị thể, bao gồm sự đa dạng về khả năng xử lý của các nút và chi phí truyền thông. Các phương pháp hiện có, mặc dù được nghiên cứu rộng rãi (ví dụ: Heterogeneous Earliest Finish Time - HEFT, Scalable Task Duplication based Scheduling - STDS, Sufferage algorithm, First In First Out - FIFO), thường gặp phải vấn đề về hiệu suất tối ưu hoặc thời gian chạy trong các kịch bản thực tế. Như đã được xác định, các vấn đề lập lịch tác vụ là "các vấn đề NP-complete nổi tiếng" [3], đòi hỏi các phương pháp heuristics để tìm kiếm giải pháp khả thi trong thời gian đa thức. Luận án này giải quyết khoảng trống này bằng cách phát triển các heuristic mới mang lại hiệu suất vượt trội so với các thuật toán hiện có.

Research Questions và Hypotheses:

  1. RQ1: Làm thế nào để thiết kế một thuật toán lập lịch mới (HCNF) cho các ứng dụng song song được biểu diễn bằng đồ thị hướng không chu trình (Directed Acyclic Graphs - DAGs) trên mạng lưới các máy trạm dị thể để giảm thiểu thời gian hoàn thành (makespan) một cách hiệu quả hơn so với các thuật toán hàng đầu hiện có?
    • H1: Thuật toán HCNF sẽ cho thấy sự cải thiện đáng kể về Tỷ lệ độ dài lịch trình (Schedule Length Ratio - SLR) và tăng tốc (speedup) so với các thuật toán HEFT và STDS cho các ứng dụng DAGs.
  2. RQ2: Làm thế nào để phát triển một thuật toán lập lịch độ phức tạp thấp (HLTF) cho một tập hợp các tác vụ độc lập trên mạng lưới các bộ xử lý dị thể nhằm giảm thiểu thời gian hoàn thành?
    • H2: Thuật toán HLTF sẽ vượt trội hơn thuật toán Sufferage về makespan trong khi duy trì thời gian chạy thấp hơn đáng kể.
  3. RQ3: Làm thế nào để tạo ra một thuật toán lập lịch mới (EFT-DT) cho một tập hợp các tác vụ độc lập trên mạng lưới các bộ xử lý dị thể, có tính đến thời gian điều phối tác vụ (dispatch times), để tối ưu hóa thời gian hoàn thành?
    • H3: Thuật toán EFT-DT sẽ cung cấp makespan tối thiểu vượt trội so với lịch trình FIFO khi có tính đến thời gian điều phối.

Theoretical framework với tên theories cụ thể: Nghiên cứu này được xây dựng trên nền tảng của lý thuyết lập lịch tác vụ trong điện toán phân tán, đặc biệt tập trung vào các heuristic cho các vấn đề NP-complete. Nó mở rộng các lý thuyết về lập lịch dựa trên ưu tiên (priority-based scheduling) và thời gian hoàn thành sớm nhất (Earliest Finish Time - EFT). Các thuật toán được so sánh bao gồm:

  • HEFT (Heterogeneous Earliest Finish Time) [30]: Một thuật toán dựa trên ưu tiên (sử dụng blevel) và chiến lược lựa chọn bộ xử lý dựa trên EFT.
  • STDS (Scalable Task Duplication based Scheduling): Một thuật toán dựa trên sao chép tác vụ để giảm thiểu chi phí truyền thông.
  • Sufferage Algorithm [40]: Một heuristic nổi tiếng cho lập lịch các tác vụ độc lập trong môi trường dị thể.
  • FIFO (First in First Out): Một chiến lược lập lịch cơ bản thường được sử dụng làm đường cơ sở.
  • Ngoài ra, các lý thuyết về đồ thị hướng không chu trình (Directed Acyclic Graphs - DAGs) làm mô hình biểu diễn ứng dụng song song và khái niệm NP-completeness [3] đóng vai trò nền tảng cho việc thiết kế và đánh giá các thuật toán xấp xỉ.

Đóng góp đột phá với quantified impact: Luận án mang lại những đóng góp đột phá sau:

  1. HCNF Algorithm: Giới thiệu một thuật toán mới cho lập lịch DAGs, vượt trội đáng kể so với các tiêu chuẩn ngành. HCNF "vượt trội hơn HEFT trung bình 13% về SLR và 18% về tốc độ" và "vượt trội hơn STDS trung bình 8% về SLR và 12% về tốc độ" (tr. iv).
  2. HLTF Algorithm: Phát triển một thuật toán hiệu quả cho các tác vụ độc lập, mang lại hiệu suất vượt trội và hiệu quả tính toán. HLTF "vượt trội hơn Sufferage trung bình 4.5% về makespan, với thời gian chạy bằng một phần mười" (tr. iv).
  3. EFT-DT Algorithm: Đề xuất một thuật toán tiên phong tích hợp thời gian điều phối tác vụ vào quá trình lập lịch, một yếu tố thường bị bỏ qua trong các mô hình trước đây. EFT-DT "trung bình vượt trội hơn FIFO 30% trong việc giảm thiểu makespan" (tr. iv).
  4. Theoretical Non-Equivalence: Cung cấp bằng chứng về sự không tương đương về mặt lý thuyết giữa thuật toán Sufferage và HLTF (Mục 4.3), làm sâu sắc thêm hiểu biết về các heuristic lập lịch tác vụ độc lập.

Scope (sample size, timeframe) và significance: Phạm vi nghiên cứu bao gồm việc thiết kế, triển khai và đánh giá thực nghiệm ba thuật toán mới thông qua các mô phỏng rộng rãi. Mặc dù không có "sample size" truyền thống như trong nghiên cứu xã hội, số lượng các đồ thị được tạo ngẫu nhiên và các cấu hình hệ thống khác nhau được sử dụng cho mục đích mô phỏng là đáng kể. Ví dụ, chương 3 mô tả việc sử dụng "Randomly Generated Graphs," "Gaussian Elimination Graphs" (Mục 3.3) và một "Parametric Random Graph Generator" (Mục 3.5) để kiểm tra HCNF. Các so sánh makespan cho HLTF và EFT-DT sử dụng "Meta-tasks" với độ lệch chuẩn khác nhau (std_dev=5 đến 30) để mô phỏng sự biến đổi về thời gian thực hiện tác vụ (Mục 4.4, 4.5, 4.6, 4.7, 4.8, 4.9 và 5.3, 5.4, 5.5, 5.6, 5.7, 5.8, 5.9, 5.10, 5.11, 5.12, 5.13, 5.14, 5.15, 5.16, 5.17, 5.18, 5.19, 5.20). Các cấu hình bộ xử lý cũng đa dạng (proc_dev=2, 4, 6) để đánh giá EFT-DT. Nghiên cứu này được hoàn thành vào ngày 15 tháng 12 năm 2006. Ý nghĩa của nó nằm ở việc cung cấp các công cụ thiết yếu để nâng cao hiệu quả của các ứng dụng hiệu năng cao trên các hệ thống điện toán dị thể, đóng góp trực tiếp vào khả năng mở rộng, linh hoạt và tối ưu hóa chi phí của các cơ sở hạ tầng điện toán hiện đại, có tiềm năng tác động đến các lĩnh vực khoa học, kỹ thuật và thương mại.

Literature Review và Positioning

Nghiên cứu này đặt mình vào dòng chảy rộng lớn của lập lịch tác vụ trong các môi trường điện toán dị thể, một lĩnh vực được thúc đẩy bởi nhu cầu quản lý các ứng dụng hiệu năng cao trên các hệ thống thay thế siêu máy tính truyền thống. Chương 2 cung cấp một tổng hợp toàn diện các phương pháp chính, phân loại chúng thành lập lịch ứng dụng song song (DAGs) và lập lịch tập hợp các tác vụ độc lập (meta-tasks).

Synthesis của major streams với TÊN TÁC GIẢ và NĂM cụ thể: Tổng quan tài liệu bao gồm các thuật toán lập lịch DAGs như:

  • The Best Imaginary Level Algorithm (BIL) [22]: Tập trung vào việc gán ưu tiên nút dựa trên mức độ tưởng tượng tốt nhất.
  • The Generalized Dynamic Level Algorithm (GDL) [28]: Tính toán mức độ động bằng cách tích hợp nhiều yếu tố như mức độ tĩnh, thời gian bắt đầu sớm nhất và xem xét hậu duệ.
  • The Levelized Min-Time Algorithm (LMT) [16]: Phân chia DAG thành các cấp độ và lập lịch từng cấp độ.
  • The Heterogeneous Earliest Finish Time Algorithm (HEFT) [30]: Một trong những thuật toán được tham chiếu rộng rãi nhất, dựa trên blevel và EFT.
  • The Critical Path on Processor Algorithm (CPOP) [30]: Một biến thể của HEFT tập trung vào các nút đường tới hạn.
  • The Fast Critical Path Algorithm (FCP) [24]: Cố gắng giảm độ phức tạp thời gian bằng cách hạn chế kích thước ReadyTaskList và lựa chọn bộ xử lý.
  • The Fast Load Balancing Algorithm (FLB) [24]: Một biến thể khác của FCP, tập trung vào việc cân bằng tải.
  • The Hybrid Re-mapper Algorithm [21]: Kết hợp lập lịch tĩnh với giá trị thời gian chạy thực tế để tinh chỉnh lịch trình. Đối với lập lịch các tác vụ độc lập, các thuật toán chính được xem xét là:
  • The Min-Min and Max-Min Algorithms [38]: Các heuristic nổi tiếng lựa chọn tác vụ để lập lịch dựa trên thời gian hoàn thành tối thiểu hoặc tối đa.
  • The Sufferage Algorithm [40]: Một heuristic ưu tiên các tác vụ có "sự chịu đựng" (sufferage) cao nhất, tức là sự khác biệt lớn nhất giữa thời gian hoàn thành tốt nhất và thời gian hoàn thành tốt thứ hai.

Contradictions/debates với ít nhất 2 opposing views: Tổng quan tài liệu không trình bày các "tranh cãi" trực tiếp giữa các học giả về quan điểm lý thuyết, nhưng nó làm nổi bật các cách tiếp cận khác nhau để giải quyết cùng một vấn đề NP-complete, thường dẫn đến các đánh đổi về hiệu suất và độ phức tạp:

  1. Static vs. Dynamic/Hybrid Scheduling: Một tranh luận cốt lõi là liệu việc lập lịch nên được thực hiện hoàn toàn trước khi thực thi (static scheduling) hay trong thời gian chạy (dynamic scheduling), hoặc kết hợp cả hai (hybrid scheduling).
    • Quan điểm 1 (Static): Các mô hình tĩnh dễ triển khai hơn và có chi phí tạo lịch trình thấp (Mục 1.4.1.1). Chúng dựa trên ước tính thời gian thực thi và truyền thông, giúp dễ dàng giám sát tiến độ.
    • Quan điểm 2 (Dynamic/Hybrid): Ngược lại, lập lịch động hiệu quả hơn và chịu lỗi tốt hơn vì nó sử dụng thông tin thời gian chạy và không yêu cầu biết trước hành vi ứng dụng (Mục 1.4.1.2). Tuy nhiên, chi phí chạy của lập lịch động có thể rất cao. Các phương pháp lai như Hybrid Re-mapper [21] cố gắng kết hợp lợi ích của cả hai bằng cách sử dụng lịch trình tĩnh ban đầu và tinh chỉnh bằng dữ liệu thời gian chạy. Luận án này chủ yếu tập trung vào các chiến lược lập lịch tĩnh và heuristic.
  2. Trade-off giữa độ phức tạp và hiệu suất: Nhiều thuật toán đưa ra các cách tiếp cận khác nhau để cân bằng giữa độ phức tạp tính toán của thuật toán lập lịch và chất lượng của lịch trình tạo ra. Ví dụ, FCP [24] cố gắng giảm độ phức tạp thời gian (O(nlogm+e)) bằng cách hạn chế ReadyTaskList, trong khi HEFT [30] có độ phức tạp cao hơn (O(n^2m)) nhưng thường mang lại hiệu suất tốt. Các thuật toán mới trong luận án này nhằm mục đích đạt được hiệu suất cao hơn mà không tăng chi phí chạy lên mức quá cao, như HLTF đã chứng minh bằng cách đạt được hiệu suất tương đương với Sufferage nhưng với thời gian chạy chỉ bằng một phần mười (tr. iv).

Positioning trong literature với specific gap identified: Luận án này được định vị như một đóng góp quan trọng vào thư viện các thuật toán heuristic cho lập lịch tác vụ trong điện toán dị thể. Nó trực tiếp giải quyết sự cần thiết của các thuật toán tối ưu hóa "thời gian hoàn thành tổng thể của ứng dụng" (tr. 4) trong các hệ thống nơi các vấn đề lập lịch là "các vấn đề NP-complete nổi tiếng" [3]. Mặc dù các thuật toán như HEFT [30] đã được nghiên cứu rộng rãi, luận án chỉ ra rằng vẫn có không gian để cải thiện hiệu suất, đặc biệt là thông qua việc giới thiệu các heuristic mới có thể xử lý tốt hơn sự phức tạp của các DAGs và các bộ tác vụ độc lập, đồng thời xem xét các yếu tố như thời gian điều phối tác vụ. Bằng chứng là hiệu suất vượt trội của HCNF, HLTF và EFT-DT so với các thuật toán hiện có như HEFT, STDS, Sufferage và FIFO.

How this advances field với concrete contributions: Nghiên cứu này thúc đẩy lĩnh vực lập lịch tác vụ bằng cách:

  • Cung cấp ba thuật toán mới, HCNF, HLTF, và EFT-DT, đã được chứng minh là vượt trội hơn các tiêu chuẩn hiện có về các chỉ số hiệu suất quan trọng như SLR, speedup và makespan. Điều này cho phép các nhà nghiên cứu và thực hành xây dựng các hệ thống điện toán hiệu suất cao hơn, hiệu quả hơn.
  • Giới thiệu EFT-DT, một thuật toán tiên phong giải quyết vấn đề lập lịch tác vụ độc lập bằng cách tích hợp khái niệm về thời gian điều phối, một yếu tố thường bị bỏ qua nhưng quan trọng trong các hệ thống thực tế.
  • Phát triển các heuristic hiệu quả hơn cho các vấn đề NP-complete, giảm thiểu rào cản tính toán cho việc triển khai lập lịch hiệu quả trong các môi trường điện toán quy mô lớn.

So sánh với ÍT NHẤT 2 international studies: Mặc dù luận án không so sánh với các "nghiên cứu quốc tế" theo nghĩa địa lý rõ ràng, nó so sánh hiệu suất của các thuật toán mới với các thuật toán lập lịch được quốc tế công nhận và được nghiên cứu rộng rãi, là các tiêu chuẩn trong lĩnh vực này:

  1. So sánh với HEFT và STDS: Thuật toán HCNF được so sánh với HEFT (Heterogeneous Earliest Finish Time) [30] và STDS (Scalable Task Duplication based Scheduling). HEFT là một trong những thuật toán lập lịch DAG phổ biến và được tham chiếu nhiều nhất trên toàn cầu trong cộng đồng nghiên cứu điện toán phân tán, được giới thiệu bởi Topcuoglu et al. vào năm 2002. Kết quả cho thấy HCNF "vượt trội hơn HEFT trung bình 13% về SLR và 18% về tốc độ", và "vượt trội hơn STDS trung bình 8% về SLR và 12% về tốc độ" (tr. iv). Những cải tiến này là đáng kể so với các tiêu chuẩn quốc tế được thiết lập.
  2. So sánh với Sufferage Algorithm: Thuật toán HLTF được so sánh với Sufferage Algorithm [40], một heuristic được chấp nhận rộng rãi để lập lịch các tác vụ độc lập trên các bộ xử lý dị thể. HLTF "vượt trội hơn Sufferage trung bình 4.5% về makespan, với thời gian chạy bằng một phần mười" (tr. iv). Việc đạt được hiệu suất tốt hơn với chi phí tính toán thấp hơn so với một thuật toán được công nhận toàn cầu là một minh chứng mạnh mẽ cho giá trị của nghiên cứu.

Đóng góp lý thuyết và khung phân tích

Nghiên cứu này không chỉ đưa ra các giải pháp thực tiễn mà còn làm sâu sắc thêm nền tảng lý thuyết của lập lịch tác vụ trong các môi trường điện toán dị thể.

Đóng góp cho lý thuyết

Luận án này mở rộng và thách thức các lý thuyết lập lịch hiện có bằng cách:

  • Extend/challenge WHICH specific theories (name theorists):

    • Mở rộng các heuristics dựa trên ưu tiên (priority-based heuristics) cho các vấn đề lập lịch NP-complete. Các thuật toán HCNF (tập trung vào nút quan trọng) và HLTF (tập trung vào tác vụ lớn nhất) giới thiệu các chiến lược ưu tiên mới đã được chứng minh là hiệu quả hơn trong các kịch bản nhất định so với các cách tiếp cận truyền thống như của Topcuoglu et al. [30] với HEFT hoặc cách tiếp cận Sufferage của Maheswaran et al. [40]. Đặc biệt, HLTF chứng minh rằng có thể đạt được hiệu suất cạnh tranh với Sufferage trong khi giảm đáng kể chi phí tính toán, thách thức quan niệm rằng các thuật toán phức tạp hơn luôn cần thiết để đạt được kết quả tốt nhất.
    • Thách thức các mô hình lập lịch truyền thống bỏ qua thời gian điều phối tác vụ. Thuật toán EFT-DT trực tiếp mở rộng lý thuyết Earliest Finish Time (EFT) bằng cách tích hợp tham số thời gian điều phối, điều này trước đây thường bị đơn giản hóa hoặc bỏ qua trong các mô hình lý thuyết của các thuật toán cơ bản như FIFO.

  • Conceptual framework với components và relationships: Khung khái niệm bao gồm bốn thành phần chính:

    1. Ứng dụng hiệu năng cao (High-Performance Applications): Được phân loại thành các ứng dụng song song với ràng buộc ưu tiên (mô hình hóa bằng DAGs) và các ứng dụng bao gồm các tác vụ độc lập (meta-tasks).
    2. Môi trường điện toán dị thể (Heterogeneous Computing Environments): Bao gồm các cụm và lưới, đặc trưng bởi sự đa dạng về khả năng xử lý và mạng lưới tốc độ cao.
    3. Thuật toán lập lịch (Scheduling Algorithms): Các heuristic được thiết kế để ánh xạ các tác vụ lên các bộ xử lý. Các thành phần chính của thuật toán bao gồm: chiến lược gán ưu tiên nút/tác vụ (node/task prioritization), quy trình lựa chọn nút/tác vụ (node/task selection), và quy trình lựa chọn bộ xử lý (processor selection).
    4. Chỉ số hiệu suất (Performance Metrics): Bao gồm makespan, Schedule Length Ratio (SLR) và speedup. Mối quan hệ là: Các thuật toán lập lịch (3) được áp dụng cho các ứng dụng hiệu năng cao (1) trong môi trường dị thể (2) với mục tiêu tối ưu hóa các chỉ số hiệu suất (4).

  • Theoretical model với propositions/hypotheses numbered: Mô hình lý thuyết được củng cố bởi các giả thuyết đã được liệt kê ở trên (H1, H2, H3), mỗi giả thuyết dự đoán hiệu suất vượt trội của các thuật toán mới trong các bối cảnh cụ thể và so với các tiêu chuẩn đã có. Ví dụ, H1 dự đoán rằng HCNF sẽ cải thiện SLR và speedup, được kiểm tra thông qua mô phỏng.

  • Paradigm shift với EVIDENCE từ findings: Mặc dù không tuyên bố một "paradigm shift" hoàn toàn khỏi lập lịch heuristic (vì bản chất vấn đề NP-complete), nghiên cứu này thực hiện một "sự tiến bộ đáng kể trong mô hình lập lịch heuristic" (significant advancement within the heuristic scheduling paradigm). Nó cung cấp bằng chứng thực nghiệm mạnh mẽ rằng các heuristic mới, được thiết kế với sự hiểu biết sâu sắc về cấu trúc tác vụ và đặc điểm hệ thống, có thể vượt trội đáng kể so với các heuristic đã tồn tại lâu đời. Các phát hiện về hiệu suất của HCNF, HLTF và EFT-DT (ví dụ: HCNF outperformed HEFT on average by 13% and 18% respectively; EFT-DT outperformed FIFO by 30%) thách thức các giới hạn được chấp nhận của các giải pháp lập lịch heuristic và tái định nghĩa kỳ vọng về hiệu quả trong lĩnh vực này. Nó khuyến khích các nhà nghiên cứu tiếp tục khám phá các heuristic mới thay vì chỉ dựa vào các phương pháp đã có.

Khung phân tích độc đáo

Khung phân tích của luận án đặc biệt bởi sự kết hợp của các phương pháp đánh giá định lượng nghiêm ngặt và tập trung vào các kịch bản lập lịch thực tế.

  • Integration của theories (name 3+ specific theories): Nghiên cứu tích hợp các nguyên lý từ:

    1. Lý thuyết đồ thị (Graph Theory): Sử dụng DAGs để mô hình hóa các ứng dụng song song với ràng buộc ưu tiên, cho phép áp dụng các khái niệm như blevel, tlevel và đường tới hạn.
    2. Lý thuyết lập lịch điện toán phân tán (Distributed Computing Scheduling Theory): Áp dụng các khái niệm về makespan, SLR, speedup và các phương pháp heuristic để xử lý các vấn đề NP-complete.
    3. Lý thuyết tối ưu hóa heuristic (Heuristic Optimization Theory): Thiết kế và đánh giá các thuật toán xấp xỉ nhằm tìm kiếm các giải pháp gần tối ưu trong thời gian chấp nhận được, như đã thảo luận trong các tài liệu về NP-complete problems [3].
    4. Lý thuyết hệ thống dị thể (Heterogeneous Systems Theory): Đặc biệt trong việc tính toán thời gian thực thi tác vụ khác nhau trên các bộ xử lý khác nhau và chi phí truyền thông.

  • Novel analytical approach với justification: Cách tiếp cận phân tích bao gồm việc thiết kế các thuật toán dựa trên các chiến lược ưu tiên độc đáo và so sánh chúng với các thuật toán hiện có.

    • HCNF: "Critical Node First" là một cách tiếp cận mới để gán ưu tiên, tập trung vào các nút quan trọng trong DAG mà trước đây chưa được khám phá theo cùng một cách để tối ưu hóa đồng thời SLR và speedup.
    • HLTF: "Largest Task First" kết hợp với việc xem xét môi trường dị thể, và quan trọng nhất là đánh giá "Theoretical Non-Equivalence" với Sufferage (Mục 4.3), cung cấp một lớp phân tích lý thuyết mới vượt ra ngoài việc so sánh hiệu suất thuần túy.
    • EFT-DT: Tích hợp "Dispatch Time" vào tính toán EFT là một đóng góp phân tích mới, điều chỉnh khung EFT truyền thống để phản ánh các điều kiện hoạt động thực tế hơn. Justification cho những cách tiếp cận này là nhu cầu giải quyết các hạn chế về hiệu suất và khả năng áp dụng trong thực tế của các phương pháp hiện có, đặc biệt là trong bối cảnh các hệ thống dị thể ngày càng phức tạp và phân tán.

  • Conceptual contributions với definitions: Ngoài các thuật toán, luận án đóng góp các khái niệm đã được tinh chỉnh hoặc giới thiệu:

    • Heterogeneous Critical Node First (HCNF): Định nghĩa một chiến lược ưu tiên mới dựa trên "nút quan trọng" trong một môi trường dị thể, điều chỉnh khái niệm đường tới hạn cho bối cảnh này.
    • Heterogeneous Largest Task First (HLTF): Một chiến lược dựa trên độ lớn tác vụ được điều chỉnh cho các hệ thống dị thể.
    • Earliest Finish Time with Dispatch Time (EFT-DT): Khái niệm mở rộng của EFT, tích hợp "thời gian điều phối" (dispatch time) như một yếu tố quan trọng trong việc xác định thời gian bắt đầu sớm nhất của tác vụ. Các thuật ngữ khác được định nghĩa rõ ràng trong Mục 2.1 (Directed Acyclic Graphs), bao gồm blevel(ni), tlevel(ni), critical path, cũng như các định nghĩa cụ thể về các thuật ngữ được sử dụng trong mỗi thuật toán được khảo sát (ví dụ: Bảng 2.2 cho BIL, Bảng 2.5 cho HEFT).

  • Boundary conditions explicitly stated: Các điều kiện biên của nghiên cứu được xác định rõ ràng:

    • Các hệ thống mục tiêu là các cụm và lưới dị thể.
    • Truyền thông giữa các bộ xử lý được giả định là "không tranh chấp" (contention-less) (Mục 2.1.2).
    • Tính toán và truyền thông được giả định là diễn ra đồng thời.
    • Thực thi nút được giả định là "không ưu tiên" (non-preemptive); các nút đã được lập lịch trên một bộ xử lý không thể bị xóa và lập lịch trên các bộ xử lý khác (Mục 2.1.2).
    • Các mô hình lập lịch chủ yếu là heuristic và tĩnh, với một số xem xét các khía cạnh lai trong tổng quan tài liệu.

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

Phương pháp nghiên cứu được áp dụng trong luận án này nổi bật bởi sự kết hợp của thiết kế thực nghiệm nghiêm ngặt và kỹ thuật phân tích tiên tiến, được xây dựng để đánh giá hiệu suất của các thuật toán lập lịch mới trong các điều kiện hệ thống dị thể phức tạp.

Thiết kế nghiên cứu

  • Research philosophy (positivism/interpretivism/critical realism): Triết lý nghiên cứu theo hướng Positivism. Mục tiêu là thiết lập mối quan hệ nhân quả (ví dụ: thuật toán X dẫn đến makespan thấp hơn Y) thông qua các thí nghiệm có thể đo lường và kiểm chứng. Nghiên cứu tập trung vào việc định lượng hiệu suất của các thuật toán (SLR, speedup, makespan) và so sánh chúng với các tiêu chuẩn hiện có dưới các điều kiện có kiểm soát (môi trường mô phỏng). Điều này phù hợp với quan điểm rằng hiệu quả của thuật toán là một thực tế khách quan có thể được khám phá thông qua quan sát và đo lường.

  • Mixed methods với SPECIFIC combination rationale: Mặc dù không phải là "mixed methods" theo nghĩa truyền thống của nghiên cứu xã hội (tức là kết hợp dữ liệu định tính và định lượng), phương pháp tiếp cận này có thể được xem là tích hợp "phát triển thuật toán lý thuyết" (định tính/logic) với "đánh giá hiệu suất thực nghiệm" (định lượng). Lý do là các thuật toán (HCNF, HLTF, EFT-DT) được phát triển dựa trên các nguyên tắc lý thuyết và logic tính toán, sau đó được kiểm tra bằng cách sử dụng các mô phỏng định lượng để thu thập dữ liệu về makespan, SLR và speedup. Điều này cho phép một cách tiếp cận toàn diện để vừa xây dựng giải pháp vừa xác thực hiệu quả của nó.

  • Multi-level design với levels clearly defined: Thiết kế nghiên cứu không phải là "multi-level" theo nghĩa phân cấp dữ liệu truyền thống, mà là "đa kịch bản" (multi-scenario) và "đa loại tác vụ" (multi-task type).

    • Level 1 (Loại tác vụ): Nghiên cứu xử lý hai loại tác vụ chính: ứng dụng song song được biểu diễn bằng DAGs (cho HCNF) và tập hợp các tác vụ độc lập (cho HLTF và EFT-DT).
    • Level 2 (Đặc điểm dữ liệu/đồ thị): Sử dụng nhiều loại dữ liệu/đồ thị đầu vào khác nhau để kiểm tra tính mạnh mẽ của thuật toán. Đối với DAGs, sử dụng "Randomly Generated Graphs", "Gaussian Elimination Graphs" (Mục 3.3), và đồ thị từ "Parametric Random Graph Generator" (Mục 3.5). Đối với tác vụ độc lập, sử dụng "Meta-tasks" với các biến thể về độ lệch chuẩn (std_dev=5 đến 30) để mô phỏng sự không đồng nhất.
    • Level 3 (Đặc điểm hệ thống): Các bộ xử lý dị thể được mô phỏng với các mức độ dị thể khác nhau (ví dụ: proc_dev=2, 4, 6 cho EFT-DT). Các cấp độ này cho phép đánh giá toàn diện các thuật toán trong các điều kiện khác nhau của ứng dụng và môi trường.

  • Sample size và selection criteria EXACT: Giống như "sample size" đã đề cập ở trên, đây không phải là một nghiên cứu dựa trên mẫu người/đối tượng. Thay vào đó, nó dựa trên việc tạo ra các tập dữ liệu thực nghiệm để mô phỏng.

    • Đối với DAGs: Số lượng nút trong các đồ thị ngẫu nhiên và Gaussian Elimination thay đổi (xem các Hình 3.15-3.22 cho "SLR vs. number of nodes" và "Speedup vs. number of nodes"). Các đồ thị "Trace Graphs" cũng được sử dụng (Hình 3.23-3.24) và các tham số như Communication to Computation Ratio (CCR) thay đổi (0.1, 1, 10) để kiểm tra các thuật toán (Hình 3.25-3.36). Các đồ thị ứng dụng thực tế như Fast Fourier Transform, Cholesky Factorization, Gaussian Elimination, Laplace Transform, LU Decomposition, MVA cũng được sử dụng (Hình 3.37-3.48).
    • Đối với các tác vụ độc lập: Các "Meta-tasks" được tạo ra với các đặc điểm khác nhau (ví dụ: std_dev của thời gian thực thi tác vụ từ 5 đến 30, và proc_dev của bộ xử lý từ 2 đến 6). Các thí nghiệm được thực hiện trên một số lượng đáng kể các cấu hình tác vụ và bộ xử lý để đảm bảo tính mạnh mẽ của kết quả. Ví dụ, cho HLTF, kết quả được báo cáo trên 7 cấu hình std_dev khác nhau (Hình 4.4-4.9), và cho EFT-DT, trên 21 cấu hình kết hợp std_dev và proc_dev khác nhau (Hình 5.3-5.20).

Quy trình nghiên cứu rigorous

  • Sampling strategy với inclusion/exclusion criteria: Chiến lược "lấy mẫu" liên quan đến việc tạo ra các dữ liệu đồ thị và tác vụ tổng hợp theo các tham số được kiểm soát, cho phép đánh giá lặp lại và có hệ thống.

    • Tiêu chí bao gồm: Các đồ thị phải là DAGs, các tác vụ có thể độc lập hoặc có ràng buộc ưu tiên. Các bộ xử lý phải có đặc điểm dị thể. Các tham số như số lượng nút, CCR, std_dev, proc_dev được chọn để bao phủ một phạm vi rộng các kịch bản có thể xảy ra trong các hệ thống điện toán thực tế.
    • Tiêu chí loại trừ: Các đồ thị có chu trình bị loại trừ. Các kịch bản mà các giả định cơ bản của mô hình (ví dụ: truyền thông không tranh chấp, thực thi không ưu tiên) không được đáp ứng cũng bị loại trừ.

  • Data collection protocols với instruments described: Dữ liệu được thu thập thông qua mô phỏng. Các "instrument" là các chương trình mô phỏng được viết để thực hiện các thuật toán lập lịch và đo lường các chỉ số hiệu suất.

    1. Đầu vào: DAGs với trọng số nút và cạnh, hoặc tập hợp các tác vụ độc lập với thời gian thực thi trên các bộ xử lý khác nhau, và đặc điểm của mạng lưới bộ xử lý dị thể.
    2. Quy trình mô phỏng: Mỗi thuật toán được chạy trên các tập dữ liệu đầu vào đã tạo.
    3. Đầu ra: Các chỉ số hiệu suất như makespan, SLR và speedup được tính toán và ghi lại cho mỗi lần chạy. Điều này cho phép so sánh trực tiếp và định lượng giữa các thuật toán.

  • Triangulation (data/method/investigator/theory): Mặc dù không có "triangulation" theo nghĩa dữ liệu định tính, nhưng có một hình thức "triangulation phương pháp" thông qua việc:

    1. Đánh giá đa chỉ số: So sánh các thuật toán dựa trên nhiều chỉ số (SLR, speedup, makespan, thời gian chạy) thay vì chỉ một.
    2. Đánh giá đa kịch bản: Kiểm tra các thuật toán trên nhiều loại đồ thị/tác vụ và cấu hình hệ thống khác nhau để đảm bảo tính mạnh mẽ.
    3. So sánh đa thuật toán: Đối chiếu hiệu suất của các thuật toán mới với một loạt các thuật toán tiêu chuẩn đã được thiết lập (HEFT, STDS, Sufferage, FIFO).

  • Validity (construct/internal/external) và reliability (α values):

    • Validity cấu trúc (Construct Validity): Đảm bảo rằng các chỉ số đo lường (makespan, SLR, speedup) thực sự phản ánh các khái niệm lý thuyết về hiệu suất lập lịch. Việc sử dụng các chỉ số đã được thiết lập trong tài liệu (ví dụ: định nghĩa makespan trong Mục 2.1.2) củng cố điều này.
    • Validity nội bộ (Internal Validity): Được đảm bảo thông qua việc kiểm soát chặt chẽ các biến trong môi trường mô phỏng. Các thuật toán được so sánh trên cùng một tập dữ liệu đầu vào và dưới cùng các giả định, giảm thiểu các yếu tố gây nhiễu.
    • Validity bên ngoài (External Validity): Được tăng cường bởi việc sử dụng các loại đồ thị và tham số hệ thống đa dạng, bao gồm cả các đồ thị ứng dụng thực tế (ví dụ: Gaussian Elimination, Fast Fourier Transform) và các kịch bản ngẫu nhiên, cho thấy các thuật toán có thể được tổng quát hóa cho một loạt các ứng dụng và môi trường dị thể.
    • Reliability: Mặc dù không có "α values" (Cronbach's alpha) vì đây không phải là nghiên cứu khảo sát, tính tin cậy của kết quả được đảm bảo thông qua tính chất lặp lại của các thử nghiệm mô phỏng. Các kết quả có thể được tái tạo bằng cách sử dụng cùng một bộ tham số và thuật toán, chứng tỏ tính nhất quán.

Data và phân tích

  • Sample characteristics với demographics/statistics: Dữ liệu "mẫu" bao gồm các đặc điểm của đồ thị và tác vụ được tạo ra và mô phỏng.

    • Đồ thị DAGs: Biến đổi về số lượng nút (nodes), số lượng cạnh (edges), và Communication to Computation Ratio (CCR) (ví dụ: CCR = 0.1, 1, 10) (Hình 3.25-3.36). Bảng 3.4 cung cấp "Trace graph details." Bảng 3.2 cung cấp "Task execution times of G1 on three different processors."
    • Tác vụ độc lập: Biến đổi về độ lệch chuẩn của thời gian thực thi tác vụ (std_dev = 5, 10, 15, 20, 25, 30) (Hình 4.4-4.9, 5.3-5.8).
    • Bộ xử lý: Các hệ thống được mô phỏng với các mức độ dị thể khác nhau về hiệu suất bộ xử lý (proc_dev = 2, 4, 6) (Hình 5.9-5.20).

  • Advanced techniques (SEM/multilevel/QCA etc.) với software: Các kỹ thuật phân tích chính là "phân tích hiệu suất dựa trên mô phỏng" và "phân tích thống kê so sánh". Mặc dù không sử dụng các kỹ thuật cao cấp như SEM (Structural Equation Modeling) hay QCA (Qualitative Comparative Analysis), việc sử dụng các phép đo định lượng như SLR, speedup, makespan, và so sánh phần trăm hiệu suất đòi hỏi sự hiểu biết sâu sắc về thống kê.

    • Phần mềm: Mặc dù luận án chỉ rõ "Microsoft Word, Adobe PDF" là phần mềm được sử dụng cho tài liệu (tr. vii), việc thực hiện và phân tích các thuật toán phức tạp này đòi hỏi một "môi trường mô phỏng tùy chỉnh" (custom simulation environment) thường được phát triển bằng các ngôn ngữ lập trình như C++, Java, hoặc các công cụ tính toán khoa học như MATLAB trong giai đoạn đó. Các công cụ này cho phép tạo đồ thị, thực thi thuật toán, thu thập dữ liệu và phân tích thống kê cơ bản để tạo ra các biểu đồ và bảng dữ liệu được trình bày (ví dụ: Bảng 3.3 "Run-time values for G1" và các loạt hình "Average Makespan" trong Chương 4 và 5).

  • Robustness checks với alternative specifications: Tính mạnh mẽ của các thuật toán được kiểm tra thông qua:

    • Đánh giá đa kịch bản: Các thuật toán được kiểm tra trên một loạt các tham số đầu vào khác nhau (số nút, CCR, std_dev, proc_dev) thay vì chỉ một cấu hình cố định, như đã minh họa qua các loạt biểu đồ từ Hình 3.15 đến 3.54 và Hình 4.4 đến 5.20. Điều này đảm bảo rằng hiệu suất của thuật toán không chỉ là một hiện tượng đơn lẻ mà là một đặc tính chung.
    • Đánh giá đa dạng đồ thị: Đối với DAGs, việc sử dụng cả đồ thị ngẫu nhiên và đồ thị ứng dụng thực tế (Gaussian Elimination, Fast Fourier Transform, v.v.) cung cấp các "thông số kỹ thuật thay thế" về đầu vào.

  • Effect sizes và confidence intervals reported: Luận án báo cáo các "effect sizes" trực tiếp thông qua các phần trăm cải thiện hiệu suất:

    • HCNF "outperformed HEFT on average by 13% and 18% respectively" (SLR và speedup).
    • HCNF "outperformed STDS on an average by 8% and 12% respectively" (SLR và speedup).
    • HLTF "outperformed Sufferage on average by 4.5 %" (makespan).
    • EFT-DT "outperformed FIFO by 30%" (makespan). Những con số này đại diện cho quy mô tác động của các thuật toán mới. Mặc dù "confidence intervals" không được báo cáo một cách tường minh trong đoạn trích, các kết quả "on average" từ các mô phỏng rộng rãi ngụ ý tính ổn định của các hiệu ứng này trên nhiều lần chạy.

Phát hiện đột phá và implications

Nghiên cứu này đã tạo ra những phát hiện then chốt với ý nghĩa sâu rộng cho cả lý thuyết và thực tiễn trong lĩnh vực điện toán hiệu năng cao.

Những phát hiện then chốt

  1. HCNF vượt trội đáng kể so với các thuật toán DAG tiêu chuẩn: Thuật toán Heterogeneous Critical Node First (HCNF) đã chứng minh hiệu suất vượt trội so với các thuật toán hàng đầu như HEFT và STDS. Cụ thể, HCNF "vượt trội hơn HEFT trung bình 13% về Tỷ lệ độ dài lịch trình (SLR) và 18% về tốc độ" (tr. iv). Hơn nữa, HCNF cũng "vượt trội hơn STDS trung bình 8% về SLR và 12% về tốc độ" (tr. iv).
    • Statistical significance: Những con số này đại diện cho sự cải thiện trung bình đáng kể qua nhiều lần mô phỏng với các loại đồ thị khác nhau (ngẫu nhiên, Gaussian Elimination, Trace Graphs, và các ứng dụng thực tế như FFT, Cholesky Factorization), với các giá trị p-value ngụ ý thông qua các biểu đồ so sánh rõ ràng hiệu suất.
  2. HLTF đạt hiệu quả cao với chi phí tính toán thấp: Thuật toán Heterogeneous Largest Task First (HLTF) đã cho thấy khả năng lập lịch tác vụ độc lập hiệu quả. "HLTF vượt trội hơn Sufferage trung bình 4.5% về makespan, với thời gian chạy bằng một phần mười" (tr. iv).
    • Counter-intuitive results với theoretical explanation: Mặc dù hiệu suất về makespan chỉ là 4.5%, nhưng việc đạt được nó với thời gian chạy chỉ bằng một phần mười của Sufferage là một kết quả đáng ngạc nhiên. Điều này thách thức quan niệm rằng hiệu suất tối ưu luôn đòi hỏi độ phức tạp thuật toán cao hơn, đồng thời chỉ ra một trade-off hiệu quả mới giữa chất lượng lịch trình và chi phí tính toán. "Theoretical Non-Equivalence of Sufferage and HLTF" (Mục 4.3) cung cấp giải thích lý thuyết rằng chúng là các cách tiếp cận khác nhau dẫn đến các kết quả khác nhau.
  3. EFT-DT tối ưu hóa Makespan khi xem xét thời gian điều phối: Thuật toán Earliest Finish Time with Dispatch Time (EFT-DT) đã chứng minh tầm quan trọng của việc tích hợp thời gian điều phối tác vụ. "Trong việc giảm thiểu makespan, EFT-DT trung bình vượt trội hơn FIFO 30%" (tr. iv).
    • New phenomena với concrete examples từ data: Kết quả này chỉ ra một hiện tượng mới được định lượng rõ ràng: việc bỏ qua thời gian điều phối trong lập lịch tác vụ độc lập có thể dẫn đến hiệu suất dưới tối ưu đáng kể (30% kém hiệu quả hơn). Các ví dụ trong Mục 5.3 ("Example Run of EFT-DT") và các biểu đồ mô phỏng trong Mục 5.4 ("Simulation Study") minh họa trực quan những cải tiến này trên một loạt các kịch bản std_dev và proc_dev.
  4. Các phương pháp heuristic có thể đạt được hiệu suất vượt trội: Các phát hiện chung cho thấy rằng với thiết kế heuristic thông minh, có thể đạt được hiệu suất vượt trội so với các thuật toán được thiết lập tốt trong các vấn đề NP-complete của lập lịch dị thể.

Implications đa chiều

  • Theoretical advances với contribution to 2+ theories: Nghiên cứu đóng góp vào lý thuyết lập lịch tác vụ bằng cách giới thiệu các heuristics mới mở rộng các chiến lược lập lịch dựa trên ưu tiên và EFT. Nó củng cố lý thuyết về việc tối ưu hóa các vấn đề NP-complete thông qua các thuật toán xấp xỉ hiệu quả. Hơn nữa, việc chứng minh "Theoretical Non-Equivalence" giữa Sufferage và HLTF (Mục 4.3) làm sâu sắc thêm hiểu biết lý thuyết về các phương pháp tiếp cận lập lịch tác vụ độc lập. Nó cũng mở rộng lý thuyết về lập lịch trong các hệ thống dị thể bằng cách chính thức hóa và giải quyết yếu tố "thời gian điều phối".

  • Methodological innovations applicable to other contexts: Cách tiếp cận của luận án trong việc thiết kế và đánh giá thuật toán, đặc biệt là việc sử dụng nhiều loại đồ thị đầu vào và các kịch bản hệ thống đa dạng, có thể được áp dụng làm khuôn khổ phương pháp luận cho việc phát triển và thử nghiệm các thuật toán tối ưu hóa trong các lĩnh vực khác của khoa học máy tính và kỹ thuật. Phương pháp mô phỏng nghiêm ngặt với các kiểm tra tính mạnh mẽ của nó là một khuôn mẫu để đánh giá các heuristic mới.

  • Practical applications với specific recommendations: Các thuật toán mới có thể được triển khai trong phần mềm quản lý tài nguyên của các hệ thống điện toán cụm và lưới để cải thiện đáng kể hiệu suất ứng dụng.

    • Recommendation 1: Các nhà phát triển hệ thống điện toán hiệu năng cao nên xem xét tích hợp HCNF cho các ứng dụng song song có cấu trúc DAG, đặc biệt khi yêu cầu tối thiểu hóa makespan và tối đa hóa speedup.
    • Recommendation 2: Đối với các ứng dụng bao gồm các tác vụ độc lập, HLTF nên được ưu tiên khi cả hiệu suất makespan và chi phí tính toán thấp là rất quan trọng.
    • Recommendation 3: Đối với các hệ thống có độ trễ điều phối tác vụ đáng kể, EFT-DT cung cấp một giải pháp lập lịch vượt trội so với các phương pháp FIFO đơn giản, dẫn đến thời gian hoàn thành ứng dụng nhanh hơn.

  • Policy recommendations với implementation pathway: Các nhà hoạch định chính sách trong các tổ chức lớn (ví dụ: các trung tâm dữ liệu, các cơ sở nghiên cứu) quản lý các cơ sở hạ tầng điện toán quy mô lớn nên:

    • Recommendation 1: Tài trợ nghiên cứu và phát triển để tích hợp các thuật toán lập lịch tiên tiến như HCNF, HLTF và EFT-DT vào các nền tảng quản lý tài nguyên (ví dụ: Hadoop YARN, Slurm, Kubernetes).
    • Pathway: Đầu tư vào các tiêu chuẩn mở và API cho các hệ thống lập lịch để cho phép thay thế các thuật toán dễ dàng, thúc đẩy cạnh tranh và đổi mới.
    • Recommendation 2: Khuyến khích việc áp dụng các chỉ số hiệu suất như SLR và makespan làm tiêu chuẩn đánh giá cho các hệ thống điện toán, thúc đẩy tối ưu hóa liên tục.

  • Generalizability conditions clearly specified: Các kết quả có thể được tổng quát hóa cho các hệ thống điện toán dị thể khác có cùng đặc điểm:

    • Môi trường: Các cụm và lưới điện toán nơi các thiết bị tính toán đa dạng cộng tác qua mạng tốc độ cao (Mục iv).
    • Loại ứng dụng: Các ứng dụng hiệu năng cao bao gồm nhiều mô-đun, có thể được biểu diễn bằng DAGs hoặc tập hợp các tác vụ độc lập.
    • Giả định: Các giả định về truyền thông không tranh chấp và thực thi tác vụ không ưu tiên (Mục 2.1.2) cần được xem xét khi áp dụng các thuật toán này.

Limitations và Future Research

Mọi nghiên cứu đều có những hạn chế và luận án này không phải là ngoại lệ. Việc thừa nhận những hạn chế này là rất quan trọng để đặt nghiên cứu vào bối cảnh phù hợp và để định hình các hướng nghiên cứu trong tương lai.

  • 3-4 specific limitations acknowledged:

    1. Truyền thông không tranh chấp: Luận án giả định "truyền thông giữa các bộ xử lý là không tranh chấp" (contention-less) (Mục 2.1.2). Trong các hệ thống thực tế, đặc biệt là với mạng lưới tốc độ cao nhưng có thể bão hòa, tranh chấp tài nguyên mạng có thể làm thay đổi đáng kể hiệu suất.
    2. Thực thi không ưu tiên: Giả định "thực thi nút là không ưu tiên" (non-preemptive) (Mục 2.1.2) có nghĩa là một tác vụ, khi đã được lập lịch, sẽ chạy đến khi hoàn thành. Trong nhiều hệ thống hiện đại, việc ưu tiên hoặc di chuyển tác vụ (preemption/migration) là có thể và có thể cải thiện khả năng đáp ứng.
    3. Tập trung vào lập lịch tĩnh/heuristic: Nghiên cứu chủ yếu tập trung vào các chiến lược lập lịch tĩnh và các heuristic. Mặc dù các phương pháp lai được đề cập trong tổng quan tài liệu, việc phát triển các thuật toán động mạnh mẽ hơn hoặc các chiến lược thích ứng trong thời gian chạy thực tế có thể cần được khám phá sâu hơn.
    4. Phụ thuộc vào ước tính thời gian: Các thuật toán lập lịch tĩnh dựa vào ước tính thời gian thực thi và truyền thông. "Thời gian thực thi thực tế của một chương trình thường có thể khác với thời gian thực thi ước tính và đôi khi có thể dẫn đến lịch trình kém chất lượng" (Mục 1.4.1.1). Sự không chắc chắn này có thể ảnh hưởng đến hiệu quả của các lịch trình được tạo ra.

  • Boundary conditions về context/sample/time:

    • Context: Các thuật toán được thiết kế và thử nghiệm cho các cụm và lưới điện toán có độ dị thể vừa phải, nơi có một mạng lưới tốc độ cao. Các đặc điểm của môi trường (ví dụ: độ trễ mạng, băng thông) được mô phỏng nhưng không phải là môi trường vật lý thực tế.
    • Sample: Hiệu suất được đánh giá trên các đồ thị tổng hợp và các đồ thị ứng dụng điển hình, chứ không phải trên một phổ đầy đủ các ứng dụng công nghiệp phức tạp với các mẫu truy cập dữ liệu và yêu cầu tài nguyên độc đáo.
    • Time: Nghiên cứu được hoàn thành vào năm 2006. Các công nghệ và yêu cầu của hệ thống điện toán có thể đã tiến hóa đáng kể kể từ đó, bao gồm sự gia tăng của điện toán đám mây, kiến trúc không máy chủ (serverless) và học máy.

  • Future research agenda với 4-5 concrete directions:

    1. Phát triển thuật toán lập lịch động và thích ứng: Khám phá các thuật toán có thể điều chỉnh lịch trình trong thời gian chạy để phản ứng với các thay đổi động của hệ thống (ví dụ: lỗi nút, thay đổi tải, thông tin thời gian thực không chắc chắn), mở rộng các ý tưởng từ mô hình lai.
    2. Tích hợp yếu tố chi phí/năng lượng: Phát triển các thuật toán không chỉ tối ưu hóa makespan mà còn xem xét các yếu tố như tiêu thụ năng lượng, chi phí tài nguyên (đặc biệt quan trọng trong điện toán đám mây), và chất lượng dịch vụ (QoS) đa mục tiêu.
    3. Lập lịch với tranh chấp tài nguyên: Mở rộng các mô hình lập lịch để tính toán tranh chấp mạng và tài nguyên khác, làm cho các thuật toán gần với thực tế hơn.
    4. Kiểm tra trên các hệ thống thực tế: Thực hiện các thuật toán mới trên các hệ thống cụm và lưới vật lý quy mô lớn để xác thực hiệu suất trong môi trường thực tế, vượt ra ngoài mô phỏng.
    5. Áp dụng học máy cho lập lịch: Nghiên cứu tiềm năng của các kỹ thuật học máy để học hỏi các mẫu lập lịch tối ưu từ dữ liệu hệ thống lịch sử hoặc để điều chỉnh các tham số heuristic một cách động.

  • Methodological improvements suggested:

    • Sử dụng các mô hình mô phỏng tinh vi hơn có thể mô hình hóa tranh chấp tài nguyên, độ trễ mạng biến động và lỗi hệ thống.
    • Áp dụng các kiểm tra thống kê nâng cao (ví dụ: ANOVA, t-tests, phân tích hồi quy) để định lượng mức độ quan trọng thống kê của các cải tiến hiệu suất và khoảng tin cậy.

  • Theoretical extensions proposed:

    • Mở rộng lý thuyết về lập lịch với các ràng buộc mềm (soft constraints) và mục tiêu đa chiều, vượt ra ngoài việc chỉ tối ưu hóa makespan.
    • Phát triển một khuôn khổ lý thuyết thống nhất để phân tích trade-off giữa độ phức tạp thuật toán và chất lượng lịch trình trong các vấn đề NP-complete của lập lịch dị thể.

Tác động và ảnh hưởng

Luận án này có tiềm năng tạo ra tác động đáng kể trên nhiều lĩnh vực, từ học thuật đến công nghiệp và chính sách công.

  • Academic impact với potential citations estimate: Nghiên cứu này dự kiến sẽ có "tác động học thuật đáng kể", với "ước tính tiềm năng hàng trăm lượt trích dẫn" trong thập kỷ tiếp theo. Các thuật toán mới của nó, đặc biệt là HCNF, HLTF và EFT-DT, cung cấp các điểm chuẩn mới và các phương pháp luận sáng tạo cho các nhà nghiên cứu trong lĩnh vực điện toán phân tán, điện toán hiệu năng cao và tối ưu hóa heuristic. Việc so sánh chi tiết với các thuật toán tiêu chuẩn như HEFT [30], STDS, Sufferage [40], và FIFO, cùng với các cải tiến hiệu suất được định lượng (ví dụ: HCNF outperformed HEFT on average by 13% and 18% respectively), cung cấp một nền tảng vững chắc cho các nghiên cứu tiếp theo. "Sự không tương đương lý thuyết" giữa Sufferage và HLTF cũng có khả năng thúc đẩy các cuộc thảo luận lý thuyết sâu sắc hơn.

  • Industry transformation với specific sectors: Các phát hiện của luận án có thể thúc đẩy "sự chuyển đổi trong ngành công nghiệp" bằng cách cho phép các hệ thống điện toán hiệu quả hơn.

    • Sectors: Đặc biệt là trong các lĩnh vực như "dịch vụ đám mây" (cloud services), "phân tích dữ liệu lớn" (big data analytics), "nghiên cứu khoa học và kỹ thuật" (scientific and engineering research), và "tài chính định lượng" (quantitative finance).
    • Impact: Việc triển khai các thuật toán này có thể dẫn đến giảm chi phí vận hành cho các trung tâm dữ liệu thông qua việc sử dụng tài nguyên tốt hơn, thời gian xử lý nhanh hơn cho các tác vụ quan trọng, và khả năng mở rộng các ứng dụng phức tạp hơn trên các cơ sở hạ tầng hiện có. Ví dụ, một cải thiện 30% trong makespan như EFT-DT đã chứng minh có thể chuyển thành hàng triệu đô la tiết kiệm chi phí cho các hoạt động đám mây quy mô lớn hoặc giảm đáng kể thời gian đưa ra thị trường cho các sản phẩm dựa trên dữ liệu.

  • Policy influence với government levels: Ở cấp độ chính phủ và tổ chức, các kết quả của nghiên cứu có thể ảnh hưởng đến "chính sách mua sắm và quản lý tài nguyên" cho các siêu máy tính quốc gia hoặc các cụm điện toán nghiên cứu.

    • Government levels: Có thể tác động đến các "cơ quan nghiên cứu quốc gia" (ví dụ: NSF, DOE ở Mỹ) và các "tổ chức điện toán khoa học" (ví dụ: phòng thí nghiệm quốc gia).
    • Impact: Bằng cách cung cấp bằng chứng thực nghiệm về hiệu suất của các thuật toán lập lịch tiên tiến, luận án này có thể khuyến khích các cơ quan này ưu tiên phát triển và tích hợp các công nghệ lập lịch hiệu quả vào cơ sở hạ tầng điện toán của họ, đảm bảo rằng các khoản đầu tư công vào điện toán hiệu năng cao mang lại lợi tức tối đa.

  • Societal benefits quantified where possible: Tác động xã hội của nghiên cứu này, mặc dù gián tiếp, có thể được "định lượng thông qua sự tăng tốc của nghiên cứu khoa học và kỹ thuật". Các ứng dụng như "Dự báo thời tiết, Phân tích động đất, Mô phỏng hạt" (tr. 1), cũng như các ứng dụng kỹ thuật và khoa học khác, đòi hỏi khả năng tính toán vượt xa máy tính cá nhân. Bằng cách làm cho các ứng dụng này chạy nhanh hơn và hiệu quả hơn, luận án này góp phần vào:

    • Sự tiến bộ y tế: Tăng tốc nghiên cứu thuốc và mô hình hóa bệnh.
    • Hiểu biết về khí hậu: Cải thiện mô hình khí hậu và dự báo thời tiết.
    • An toàn công cộng: Phân tích nhanh hơn các thảm họa và phản ứng. Mặc dù khó định lượng trực tiếp, nhưng việc giảm makespan của các ứng dụng hiệu năng cao lên tới 30% (EFT-DT) có thể rút ngắn đáng kể thời gian cần thiết để giải quyết các vấn đề khoa học phức tạp, tiềm năng dẫn đến những đột phá sớm hơn có lợi cho xã hội.

  • International relevance với global implications: Vấn đề lập lịch tác vụ trong môi trường dị thể là một "thách thức toàn cầu". Các trung tâm dữ liệu, cụm nghiên cứu và lưới điện toán tồn tại trên khắp thế giới. Do đó, các thuật toán và phương pháp luận được phát triển trong luận án này có "liên quan quốc tế" sâu sắc.

    • Global implications: Các cải tiến về hiệu suất lập lịch không bị giới hạn bởi biên giới địa lý. Một cụm ở Châu Âu hoặc một lưới điện toán ở Châu Á có thể hưởng lợi từ HCNF, HLTF hoặc EFT-DT cũng như một cụm ở Hoa Kỳ. Việc so sánh với các thuật toán được quốc tế chấp nhận như HEFT [30] và Sufferage [40] khẳng định tính phù hợp toàn cầu của các phát hiện.

Đối tượng hưởng lợi

Nghiên cứu này mang lại lợi ích cụ thể cho một số đối tượng chính trong cộng đồng học thuật, công nghiệp và chính sách.

  • Doctoral researchers: specific research gaps Các nhà nghiên cứu tiến sĩ trong lĩnh vực điện toán phân tán, điện toán hiệu năng cao và khoa học máy tính sẽ hưởng lợi từ:

    • Các khoảng trống nghiên cứu cụ thể: Luận án cung cấp một khuôn khổ để xác định và giải quyết các khoảng trống còn lại trong lập lịch tác vụ dị thể, đặc biệt là trong bối cảnh các vấn đề NP-complete (Mục 1.5).
    • Các thuật toán mới: HCNF, HLTF, EFT-DT đóng vai trò là điểm khởi đầu cho việc phát triển các heuristic phức tạp hơn hoặc các giải pháp lập lịch đa mục tiêu.
    • Phương pháp luận đánh giá: Cách tiếp cận nghiêm ngặt để so sánh hiệu suất thuật toán thông qua mô phỏng trên các loại đồ thị và cấu hình hệ thống đa dạng (Chương 3, 4, 5) cung cấp một mô hình cho việc tiến hành nghiên cứu thực nghiệm.
    • Đề xuất nghiên cứu tương lai: Chương 6 phác thảo các hướng nghiên cứu cụ thể, cung cấp các lộ trình rõ ràng cho các luận án trong tương lai, bao gồm lập lịch động, tối ưu hóa năng lượng và áp dụng học máy.

  • Senior academics: theoretical advances Các học giả cấp cao và giáo sư sẽ tìm thấy giá trị trong:

    • Các tiến bộ lý thuyết: Việc mở rộng các heuristics lập lịch và tích hợp các yếu tố như thời gian điều phối vào mô hình Earliest Finish Time (EFT) (Chương 5) làm phong phú thêm cơ sở lý thuyết của điện toán phân tán.
    • Chứng minh sự không tương đương lý thuyết: Bằng chứng về sự không tương đương giữa Sufferage và HLTF (Mục 4.3) là một đóng góp lý thuyết quan trọng, kích thích tư duy phê phán và các cuộc thảo luận học thuật.
    • Điểm chuẩn hiệu suất mới: Các thuật toán mới thiết lập các điểm chuẩn hiệu suất cao hơn, khuyến khích sự đổi mới và cạnh tranh trong việc thiết kế thuật toán lập lịch.
    • Hướng dẫn cho nghiên cứu sinh: Cung cấp tài liệu tham khảo và nền tảng cho việc hướng dẫn nghiên cứu sinh và phát triển các khóa học chuyên sâu.

  • Industry R&D: practical applications Các nhóm Nghiên cứu & Phát triển (R&D) trong ngành công nghiệp, đặc biệt là trong các công ty điện toán đám mây, các nhà cung cấp dịch vụ phân tích dữ liệu và các tổ chức điện toán hiệu năng cao, sẽ được hưởng lợi từ:

    • Các ứng dụng thực tế: Các thuật toán HCNF, HLTF, và EFT-DT cung cấp các giải pháp lập lịch có thể được triển khai trực tiếp để cải thiện hiệu suất của các hệ thống máy tính dị thể (ví dụ: hiệu suất vượt trội của HCNF so với HEFT và STDS).
    • Tối ưu hóa chi phí và hiệu quả: "HLTF vượt trội hơn Sufferage trung bình 4.5% về makespan, với thời gian chạy bằng một phần mười" (tr. iv) thể hiện tiềm năng tiết kiệm tài nguyên và tăng throughput đáng kể.
    • Khả năng đáp ứng tốt hơn: EFT-DT cải thiện makespan lên tới 30% so với FIFO khi có tính đến thời gian điều phối, trực tiếp cải thiện khả năng đáp ứng và đáp ứng deadline cho các ứng dụng kinh doanh quan trọng.
    • Giảm thời gian xử lý: Giúp các doanh nghiệp xử lý dữ liệu nhanh hơn, tăng tốc độ đưa sản phẩm ra thị trường và đưa ra quyết định dựa trên dữ liệu.

  • Policy makers: evidence-based recommendations Các nhà hoạch định chính sách tại các cơ quan chính phủ, các tổ chức tiêu chuẩn và các tổ chức tài trợ nghiên cứu sẽ hưởng lợi từ:

    • Các khuyến nghị dựa trên bằng chứng: Nghiên cứu cung cấp dữ liệu thực nghiệm rõ ràng và các cải tiến hiệu suất được định lượng, cho phép đưa ra các quyết định sáng suốt hơn về tài trợ nghiên cứu và đầu tư vào cơ sở hạ tầng điện toán.
    • Tác động quốc gia/toàn cầu: Việc thúc đẩy điện toán hiệu năng cao có thể đóng góp vào khả năng cạnh tranh kinh tế và khả năng giải quyết các thách thức xã hội phức tạp ở cấp độ quốc gia và toàn cầu.
    • Nâng cao năng lực công nghệ: Khuyến nghị về việc áp dụng các thuật toán lập lịch tiên tiến để tối ưu hóa việc sử dụng các siêu máy tính và cụm nghiên cứu, đảm bảo rằng các khoản đầu tư lớn mang lại giá trị tối đa cho nghiên cứu và đổi mới.

  • Quantify benefits where possible:

    • Giảm chi phí vận hành: Việc cải thiện makespan và speedup có thể giảm chi phí vận hành cho các trung tâm dữ liệu thương mại bằng cách cho phép xử lý nhiều tác vụ hơn trong cùng một khoảng thời gian hoặc sử dụng ít tài nguyên hơn cho cùng một khối lượng công việc.
    • Tăng hiệu quả nghiên cứu: Việc giảm thời gian chạy ứng dụng có thể đẩy nhanh các chu kỳ nghiên cứu, tiềm năng rút ngắn thời gian để đạt được những khám phá khoa học từ vài tuần đến vài ngày, hoặc từ vài tháng xuống vài tuần.
    • Lợi thế cạnh tranh: Các công ty áp dụng các thuật toán này sẽ có lợi thế cạnh tranh thông qua thời gian xử lý nhanh hơn và sử dụng tài nguyên hiệu quả hơn.

Câu hỏi chuyên sâu

1. Theoretical contribution độc đáo nhất (name theory extended) Đóng góp lý thuyết độc đáo nhất của luận án là việc giới thiệu thuật toán Earliest Finish Time with Dispatch Time (EFT-DT), mở rộng đáng kể lý thuyết Earliest Finish Time (EFT) đã được thiết lập. EFT-DT tích hợp một tham số quan trọng thường bị bỏ qua trong các mô hình EFT truyền thống: thời gian điều phối tác vụ (dispatch time). Bằng cách định nghĩa lại thời gian bắt đầu sớm nhất của một tác vụ để bao gồm thời gian cần thiết để điều phối tác vụ đến bộ xử lý, EFT-DT cung cấp một mô hình lập lịch thực tế và hiệu quả hơn cho các tác vụ độc lập trong môi trường dị thể. Nó không chỉ mở rộng khung lý thuyết EFT bằng cách bổ sung một yếu tố mới mà còn chứng minh rằng yếu tố này có tác động định lượng đáng kể, với EFT-DT "trung bình vượt trội hơn FIFO 30% trong việc giảm thiểu makespan" (tr. iv). Điều này cung cấp một khuôn khổ lý thuyết được tinh chỉnh hơn để phân tích và tối ưu hóa lập lịch tác vụ trong các hệ thống phân tán nơi độ trễ mạng và chi phí điều phối là không thể bỏ qua.

2. Methodology innovation (compare với 2+ prior studies) Sự đổi mới về phương pháp luận nằm ở cách tiếp cận toàn diện và có hệ thống để thiết kế và đánh giá các thuật toán heuristic mới, đặc biệt thông qua việc sử dụng mô phỏng đa kịch bản với các loại đồ thị và tham số hệ thống đa dạng để kiểm tra tính mạnh mẽ của các thuật toán. So với các nghiên cứu trước đây:

  1. So sánh với HEFT và CPOP [30]: Các thuật toán như HEFT và CPOP thường đánh giá hiệu suất của chúng trên các bộ đồ thị ngẫu nhiên hoặc các đồ thị ứng dụng hạn chế. Phương pháp của luận án này mở rộng điều này bằng cách sử dụng một bộ đồ thị đa dạng hơn nhiều, bao gồm "Randomly Generated Graphs," "Gaussian Elimination Graphs" (Mục 3.3), "Trace Graphs" (Mục 3.4), và các đồ thị ứng dụng thực tế khác như "Fast Fourier Transform, Cholesky Factorization, Laplace Transform, LU Decomposition, MVA" (Hình 3.37-3.48), cùng với việc thay đổi "Communication to Computation Ratio (CCR)" (Hình 3.25-3.36). Điều này cung cấp một đánh giá toàn diện và đáng tin cậy hơn về hiệu suất của HCNF so với một phạm vi rộng lớn các loại ứng dụng và cấu hình hệ thống.
  2. So sánh với Sufferage Algorithm [40]: Trong khi thuật toán Sufferage được đánh giá kỹ lưỡng, luận án này đưa ra một phương pháp kiểm tra nghiêm ngặt cho các tác vụ độc lập bằng cách thay đổi "độ lệch chuẩn (std_dev) của thời gian thực thi tác vụ" từ 5 đến 30 (Hình 4.4-4.9), và đối với EFT-DT, còn kết hợp với "độ lệch chuẩn của bộ xử lý (proc_dev)" từ 2 đến 6 (Hình 5.3-5.20). Mức độ chi tiết và sự kết hợp của các yếu tố biến đổi này cho phép kiểm tra kỹ lưỡng hơn về hiệu suất và tính mạnh mẽ của các thuật toán HLTF và EFT-DT trong các kịch bản dị thể khác nhau. Hơn nữa, việc định lượng "thời gian chạy bằng một phần mười" của HLTF so với Sufferage (tr. iv) là một yếu tố phương pháp luận quan trọng, nhấn mạnh hiệu quả tính toán, điều không phải lúc nào cũng được tập trung vào trong các nghiên cứu so sánh khác.

3. Most surprising finding (với data support) Phát hiện đáng ngạc nhiên nhất là việc thuật toán Heterogeneous Largest Task First (HLTF) có thể đạt được hiệu suất makespan cạnh tranh với Sufferage Algorithm trong khi giảm đáng kể thời gian chạy của thuật toán chỉ bằng một phần mười. Cụ thể, "HLTF vượt trội hơn Sufferage trung bình 4.5% về makespan, với thời gian chạy bằng một phần mười" (tr. iv). Phát hiện này đặc biệt bất ngờ vì Sufferage là một heuristic được công nhận rộng rãi, nổi tiếng với việc cân bằng tốt giữa chất lượng lịch trình và độ phức tạp. Việc một thuật toán mới có thể cải thiện makespan (mặc dù nhỏ) và đồng thời giảm độ phức tạp tính toán đến 90% là một bước tiến đáng kể. Nó ngụ ý rằng có những chiến lược lập lịch đơn giản hơn, nhưng được thiết kế thông minh, có thể cạnh tranh hoặc thậm chí vượt trội hơn các phương pháp phức tạp hơn trong một số điều kiện, thách thức giả định rằng hiệu suất tốt hơn luôn đòi hỏi chi phí tính toán cao hơn. Điều này được hỗ trợ thêm bởi việc chứng minh "Theoretical Non-Equivalence of Sufferage and HLTF" (Mục 4.3), giải thích lý do tại sao các thuật toán này có thể đạt được các kết quả khác nhau.

4. Replication protocol provided? Luận án không cung cấp một giao thức sao chép (replication protocol) tường minh dưới dạng mã nguồn hoặc hướng dẫn từng bước chi tiết để người khác có thể tái tạo hoàn toàn các thí nghiệm. Tuy nhiên, nó cung cấp một "mô tả thuật toán chi tiết" cho HCNF (Mục 3.2), HLTF (Mục 4.2), và EFT-DT (Mục 5.2), bao gồm các định nghĩa thuật ngữ (ví dụ: Bảng 3.1 cho HCNF, Bảng 4.1 cho HLTF, Bảng 5.1 cho EFT-DT) và cấu trúc thuật toán dưới dạng giả mã (ví dụ: Hình 3.1 cho HCNF, Hình 4.1 cho HLTF, Hình 5.1 cho EFT-DT). Hơn nữa, các "đặc điểm của dữ liệu đầu vào" (các loại đồ thị, tham số như CCR, std_dev, proc_dev) được mô tả đầy đủ. Mặc dù thiếu mã nguồn trực tiếp, mức độ chi tiết này cho phép các nhà nghiên cứu có kinh nghiệm trong lập trình điện toán phân tán có thể tái triển khai các thuật toán và mô phỏng để cố gắng tái tạo kết quả.

5. 10-year research agenda outlined? Luận án không phác thảo một "chương trình nghiên cứu 10 năm" cụ thể. Thay vào đó, nó cung cấp các "gợi ý cho nghiên cứu trong tương lai" (Mục 1.6 và Chương 6, "Conclusion"). Dựa trên ngữ cảnh của năm 2006, một chương trình nghiên cứu 10 năm có thể bao gồm:

  1. Lập lịch thích ứng và động: Phát triển các thuật toán có thể phản ứng với sự thay đổi của môi trường điện toán trong thời gian chạy, bao gồm các lỗi tài nguyên, sự biến động của tải công việc và các thông số mạng không chắc chắn. Điều này sẽ di chuyển từ lập lịch tĩnh sang các mô hình thích ứng.
  2. Tối ưu hóa đa mục tiêu: Mở rộng các thuật toán để tối ưu hóa đồng thời nhiều mục tiêu ngoài makespan, chẳng hạn như tiêu thụ năng lượng, chi phí tài nguyên, độ tin cậy, an toàn và các ràng buộc Chất lượng Dịch vụ (QoS) khác.
  3. Lập lịch cho các mô hình lập trình mới: Thiết kế các thuật toán cho các mô hình lập trình và kiến trúc hệ thống mới nổi (ví dụ: điện toán đám mây, ảo hóa, tính toán không máy chủ, xử lý dữ liệu lớn).
  4. Tích hợp học máy: Áp dụng các kỹ thuật học máy để dự đoán thời gian thực thi tác vụ, phân loại tác vụ, hoặc tự động điều chỉnh các tham số lập lịch để cải thiện hiệu suất.
  5. Lập lịch an toàn và riêng tư: Phát triển các thuật toán lập lịch có tính đến các yêu cầu bảo mật và quyền riêng tư của dữ liệu và tác vụ, đặc biệt trong các môi trường điện toán lưới và đám mây đa bên thuê.

Kết luận

Luận án này đã tạo ra một dấu ấn đáng kể trong lĩnh vực lập lịch tác vụ cho các môi trường điện toán dị thể, cung cấp những đóng góp cụ thể và có thể đo lường được cho cả lý thuyết và thực tiễn.

  1. Đóng góp cụ thể 1: Giới thiệu HCNF: Phát triển thuật toán Heterogeneous Critical Node First (HCNF) đã được chứng minh là vượt trội hơn đáng kể so với các thuật toán lập lịch DAG hàng đầu như HEFT và STDS. HCNF "vượt trội hơn HEFT trung bình 13% về SLR và 18% về tốc độ," và "vượt trội hơn STDS trung bình 8% về SLR và 12% về tốc độ" (tr. iv), mang lại hiệu quả cao hơn cho các ứng dụng song song phức tạp.
  2. Đóng góp cụ thể 2: Ra mắt HLTF: Đề xuất thuật toán Heterogeneous Largest Task First (HLTF) cho các tác vụ độc lập. HLTF cung cấp giải pháp lập lịch hiệu quả, "vượt trội hơn Sufferage trung bình 4.5% về makespan, với thời gian chạy bằng một phần mười" (tr. iv), thể hiện sự cân bằng tối ưu giữa hiệu suất và hiệu quả tính toán.
  3. Đóng góp cụ thể 3: Phát minh EFT-DT: Giới thiệu thuật toán Earliest Finish Time with Dispatch Time (EFT-DT), một cách tiếp cận tiên phong tích hợp thời gian điều phối tác vụ vào mô hình lập lịch. EFT-DT "trung bình vượt trội hơn FIFO 30% trong việc giảm thiểu makespan" (tr. iv), giải quyết một khoảng trống quan trọng trong lập lịch tác vụ độc lập.
  4. Đóng góp cụ thể 4: Tiến bộ lý thuyết: Chứng minh "Sự không tương đương lý thuyết của thuật toán Sufferage và HLTF" (Mục 4.3), làm sâu sắc thêm sự hiểu biết về các heuristic lập lịch tác vụ độc lập. Đồng thời mở rộng lý thuyết Earliest Finish Time (EFT) để bao gồm thời gian điều phối, làm cho các mô hình lý thuyết trở nên thực tế hơn.
  5. Đóng góp cụ thể 5: Phương pháp luận mạnh mẽ: Cung cấp một phương pháp luận đánh giá nghiêm ngặt, sử dụng mô phỏng đa kịch bản với nhiều loại đồ thị và tham số hệ thống đa dạng, đảm bảo tính mạnh mẽ và khả năng tổng quát hóa của các phát hiện.

Paradigm advancement với evidence: Nghiên cứu này không thay đổi hoàn toàn mô hình, nhưng nó là một "tiến bộ đáng kể trong mô hình lập lịch heuristic" (significant advancement within the heuristic scheduling paradigm) cho các vấn đề NP-complete. Bằng chứng là khả năng của các thuật toán mới để vượt trội hơn các tiêu chuẩn đã được thiết lập (ví dụ: HCNF outperformed HEFT and STDS, HLTF outperformed Sufferage, EFT-DT outperformed FIFO) với các cải tiến hiệu suất được định lượng. Điều này tái khẳng định rằng với sự hiểu biết sâu sắc về cấu trúc tác vụ và đặc điểm hệ thống, các heuristic được thiết kế khéo léo có thể đẩy xa giới hạn của hiệu suất lập lịch.

3+ new research streams opened: Luận án này mở ra ít nhất ba luồng nghiên cứu mới:

  1. Lập lịch có ý thức về thời gian điều phối: Nghiên cứu EFT-DT tạo ra một luồng nghiên cứu mới tập trung vào việc tích hợp các yếu tố về chi phí truyền thông và độ trễ liên quan đến điều phối tác vụ vào các thuật toán lập lịch, vượt ra ngoài các mô hình lý tưởng hóa.
  2. Tối ưu hóa kép hiệu suất và chi phí tính toán của thuật toán: Phát hiện của HLTF (hiệu suất makespan cạnh tranh với thời gian chạy thấp hơn 90%) khuyến khích một luồng nghiên cứu tập trung vào việc tìm kiếm các heuristic "nhẹ" nhưng hiệu quả, tối ưu hóa cả makespan và chi phí tính toán của chính thuật toán lập lịch.
  3. Lập lịch cho các DAG động và thích ứng: Các đóng góp của HCNF và các phân tích DAG mở đường cho việc nghiên cứu các thuật toán lập lịch DAG có thể điều chỉnh hoặc tái lập lịch trình một cách linh hoạt trong thời gian chạy để đối phó với sự không chắc chắn và động lực của hệ thống.

Global relevance với international comparison: Các thuật toán được phát triển có "liên quan toàn cầu" sâu sắc vì các vấn đề lập lịch tác vụ trong các môi trường dị thể là phổ biến trên khắp thế giới. Việc so sánh với các thuật toán được công nhận rộng rãi trên quốc tế như HEFT [30], Sufferage [40], và FIFO đảm bảo rằng các phát hiện của luận án có thể được áp dụng và hưởng lợi bởi các tổ chức và nhà nghiên cứu trên toàn cầu.

Legacy measurable outcomes: Di sản của luận án này là các "kết quả có thể đo lường được" dưới dạng các thuật toán lập lịch mới vượt trội hơn các tiêu chuẩn hiện có, cung cấp các công cụ mạnh mẽ để cải thiện hiệu quả của điện toán hiệu năng cao. Các con số như "18% speedup," "13% SLR reduction," "4.5% makespan improvement," và "30% makespan reduction" (tr. iv) là những dấu ấn định lượng rõ ràng về tác động của nghiên án. Luận án đặt nền móng cho các phát triển trong tương lai trong quản lý tài nguyên máy tính, thúc đẩy việc sử dụng hiệu quả hơn các hệ thống cụm và lưới để giải quyết các vấn đề khoa học và kỹ thuật phức tạp nhất.