Nghiên cứu về thuật toán lập lịch tác vụ trong môi trường tính toán không đồng nhất

Chuyên đề nghiên cứu Thuật toán tối ưu cho lập lịch tác vụ trong môi trường tính toán không đồng nhất, cập nhật xu hướng mới, giá trị tham khảo cao

• Tác giả: Prashanth C. Sai Ranga
• Người hướng dẫn: Sanjeev Baskiyar, Associate Professor
• Trường học: Auburn University
• Chuyên ngành: Computer Science and Software Engineering
• Đề tài: Thuật Toán Tối Ưu Cho Lập Lịch Tác Vụ Trong Môi Trường Tính Toán Không Đồng Nhất
• Loại tài liệu: dissertation
• Năm xuất bản: 2006
• Địa điểm: Auburn

Mục lục chi tiết

• DISSERTATION ABSTRACT
• ACKNOWLEDGMENTS
• TABLE OF CONTENTS
• 1. CHAPTER 1: INTRODUCTION
• 1.4. Task Scheduling in Heterogeneous Computing Environments
• 1.5. NP-Complete Problems
• 1.6. Research Objectives and Outline
• 2. CHAPTER 2: LITERATURE REVIEW
• 2.1. Scheduling a Parallel Application Represented by a Directed Acyclic Graph onto a Network of Heterogeneous Processors to Minimize the Make-Span
• 2.1.1. Directed Acyclic Graphs
• 2.1.3. The Best Imaginary Level Algorithm
• 2.1.4. The Generalized Dynamic Level Algorithm
• 2.1.5. The Levelized Min-Time Algorithm
• 2.1.6. The Heterogeneous Earliest Finish Time Algorithm
• 2.1.7. The Critical Path on Processor Algorithm
• 2.1.8. The Fast Critical Path Algorithm
• 2.1.9. The Fast Load Balancing Algorithm
• 2.1.10. The Hybrid Re-mapper Algorithm
• 2.2. Scheduling a Parallel Application Represented by a Set of Independent Tasks onto a Network of Heterogeneous Processors to Minimize the Make-Span
• 2.2.1. The Min-Max and the Max-Min Algorithm
• 2.2.3. The Sufferage Algorithm
• 3. CHAPTER 3: THE HETEROGENEOUS CRITICAL NODE FIRST ALGORITHM
• 3.2. The HCNF Algorithm
• 3.3. Gaussian Elimination Graphs
• 3.5. Parametric Random Graph Generator
• 3.5.1. Conclusion
• 4. CHAPTER 4: THE HETEROGENEOUS LARGEST TASK FIRST ALGORITHM
• 4.2. The HLTF Algorithm
• 4.3. Theoretical Non-Equivalence of Sufferage and HLTF
• 4.1. Comparison of Make-span
• 4.2. Comparison of Running Times
• 5. CHAPTER 5: SCHEDULING INDEPENDENT TASKS WITH DISPATCH TIMES
• 5.2. The EFT-DT Algorithm
• 5.3. Example Run of EFT-DT
• 5.4. Simulation Study
• 6. CHAPTER 6: CONCLUSION
• BIBLIOGRAPHY

Tóm tắt

I. Giới thiệu về Lập lịch tác vụ trong môi trường tính toán không đồng nhất

Trong bối cảnh hiện nay, thuật toán tối ưu cho lập lịch tác vụ trong môi trường tính toán không đồng nhất đang trở thành một chủ đề nghiên cứu quan trọng. Môi trường tính toán không đồng nhất bao gồm các thiết bị tính toán đa dạng, cho phép thực hiện các ứng dụng hiệu suất cao. Việc lập lịch hiệu quả cho các ứng dụng này là điều cần thiết để đáp ứng thời hạn và tối ưu hóa hiệu suất. Các thuật toán như Heterogeneous Critical Node First (HCNF), Heterogeneous Largest Task First (HLTF) và Earliest Finish Time with Dispatch Time (EFT-DT) được giới thiệu để giải quyết vấn đề này. Những thuật toán này không chỉ giúp cải thiện thời gian hoàn thành mà còn tối ưu hóa việc sử dụng tài nguyên. Điều này đặc biệt quan trọng trong các hệ thống tính toán phân tán, nơi mà việc phân bổ tài nguyên không đồng nhất có thể ảnh hưởng lớn đến hiệu suất tổng thể của hệ thống.

II. Các Thuật toán Lập lịch Tác vụ

Các thuật toán lập lịch như HCNF và HLTF đã được phát triển để giải quyết bài toán lập lịch trong môi trường tính toán không đồng nhất. Thuật toán HCNF được thiết kế để lập lịch các ứng dụng song song được biểu diễn bằng đồ thị không chu trình có hướng (DAG) lên mạng các máy tính, nhằm giảm thiểu thời gian hoàn thành. Trong khi đó, HLTF được sử dụng để lập lịch một tập hợp các tác vụ độc lập trên một mạng các bộ xử lý không đồng nhất. Kết quả cho thấy HCNF vượt trội hơn so với các thuật toán khác như HEFT và STDS, với mức tăng hiệu suất trung bình lần lượt là 13% và 18%. Điều này chứng tỏ rằng việc áp dụng các thuật toán mới có thể mang lại lợi ích đáng kể trong việc tối ưu hóa hiệu suất hệ thống.

III. Phân tích Hiệu suất của Các Thuật toán

Phân tích hiệu suất của các thuật toán lập lịch cho thấy sự khác biệt rõ rệt giữa các phương pháp. Đặc biệt, thuật toán EFT-DT đã chứng minh được khả năng tối ưu hóa thời gian hoàn thành khi xem xét thời gian giao nhận của các tác vụ. So với phương pháp FIFO, EFT-DT đã giảm thời gian hoàn thành trung bình lên tới 30%. Điều này cho thấy rằng việc xem xét thời gian giao nhận trong lập lịch có thể tạo ra sự khác biệt lớn trong hiệu suất tổng thể. Các thuật toán này không chỉ có giá trị trong lý thuyết mà còn có ứng dụng thực tiễn trong việc quản lý tài nguyên trong các hệ thống tính toán phân tán hiện nay.

IV. Ứng dụng Thực tiễn và Giá trị của Nghiên cứu

Nghiên cứu về các thuật toán lập lịch trong môi trường tính toán không đồng nhất mang lại nhiều giá trị thực tiễn. Việc tối ưu hóa quản lý tài nguyên và cải thiện hiệu suất hệ thống không chỉ có ý nghĩa trong lĩnh vực nghiên cứu mà còn trong các ứng dụng công nghiệp. Các thuật toán này có thể được áp dụng trong các lĩnh vực như tính toán đám mây, xử lý dữ liệu lớn và các ứng dụng yêu cầu hiệu suất cao khác. Hơn nữa, việc phát triển các thuật toán mới có thể mở ra hướng đi mới cho nghiên cứu trong lĩnh vực tính toán phân tán, từ đó cải thiện khả năng xử lý và giảm chi phí cho các tổ chức.

Nội dung chính

Tổng quan về luận án

Luận án tiến sĩ với tiêu đề "Algorithms for Task Scheduling in Heterogeneous Computing Environments" do Nghiên cứu sinh Prashanth C. Sai Ranga thực hiện dưới sự hướng dẫn của Phó Giáo sư Sanjeev Baskiyar tại Khoa Khoa học Máy tính và Kỹ thuật Phần mềm, Đại học Auburn (Auburn, Alabama, bảo vệ thành công ngày 15 tháng 12 năm 2006). Công trình giải quyết bài toán cốt lõi trong kỷ nguyên siêu tính toán phân tán: tối ưu hóa lập lịch tác vụ trên các hệ thống tính toán không đồng nhất (heterogeneous meta-computing systems) như cụm máy tính (cluster computing) và lưới tính toán (grid computing).

Bối cảnh khoa học và tính tiên phong

Sự bùng nổ của Công nghệ Thông tin thúc đẩy nhu cầu xử lý các ứng dụng hiệu năng cao (High-Performance Applications - HPA) như dự báo thời tiết, mô phỏng hạt vật lý và phân tích địa chấn. Tuy nhiên, việc gia tăng xung nhịp vi xử lý đơn luồng đang tiệm cận giới hạn nhiệt động lực học và vật lý bán dẫn. Siêu máy tính truyền thống (Supercomputers) tuy mạnh nhưng có tỷ số chi phí/hiệu năng (cost/performance factor) quá cao, thiếu tính linh hoạt và khó mở rộng quy mô do phụ thuộc vào phần cứng độc quyền.

Giải pháp thay thế khả thi là kết nối các máy trạm/máy tính cá nhân giá thành thấp qua mạng tốc độ cao (Network of Workstations - NOWs). Khi các thiết bị này liên tục được nâng cấp, hệ thống trở thành môi trường tính toán không đồng nhất (Heterogeneous Computing Environment). Trọng tâm kỹ thuật quyết định hiệu năng của toàn hệ thống là bài toán lập lịch tác vụ (Task Scheduling) – một bài toán tối ưu hóa tổ hợp thuộc lớp NP-complete.

Khoảng trống nghiên cứu (Research Gap)

1. Ràng buộc phụ thuộc dữ liệu phức tạp trên đồ thị DAG: Các giải thuật List-Scheduling kinh điển như HEFT (Topcuoglu et al., 2002) hay CPOP chủ yếu dựa trên mức đáy ($blevel$) hoặc đường găng cố định, thường rơi vào tối ưu cục bộ khi tỷ lệ truyền thông trên tính toán (CCR - Communication to Computation Ratio) thay đổi mạnh hoặc khi đồ thị có độ rộng lớn.
2. Nghịch lý độ phức tạp trong lập lịch tác vụ độc lập (Meta-tasks): Thuật toán Sufferage (Maheswaran et al., 1999) đạt chất lượng lịch trình khá tốt nhờ tính toán giá trị chịu thiệt (sufferage value), nhưng lại có độ phức tạp tính toán $O(m \cdot n^2)$ quá lớn, gây nghẽn cổ chai khi số lượng tác vụ ($n$) lên tới hàng ngàn.
3. Sự bỏ qua chi phí điều phối mạng (Dispatch Time): Các mô hình lập lịch tác vụ độc lập truyền thống giả định rằng tác vụ xuất hiện ngay lập tức tại vi xử lý đích, bỏ qua độ trễ điều phối truyền gói tin từ máy chủ phân phối trung tâm sang các nút tính toán.

Câu hỏi nghiên cứu và Giả thuyết khoa học

• RQ1: Làm thế nào để xác định thứ tự ưu tiên động của các nút quan trọng trên đồ thị DAG nhằm giảm thiểu thời gian hoàn thành tổng thể (makespan) trên tập vi xử lý không đồng nhất?
  • H1: Ưu tiên lập lịch các nút găng (Critical Nodes) kết hợp tính toán thời gian hoàn thành sớm nhất sẽ tạo ra tỉ số độ dài lịch trình (SLR) và độ tăng tốc (Speedup) vượt trội hơn thuật toán HEFT và STDS.
• RQ2: Liệu có thể thiết kế một heuristic cho tập tác vụ độc lập đạt makespan tương đương hoặc tốt hơn Sufferage nhưng có độ phức tạp thời gian giảm đi một bậc độ lớn?
  • H2: Phân bổ tác vụ có kích thước tính toán lớn nhất lên vi xử lý tối ưu (HLTF) sẽ giải quyết triệt để sự lãng phí tài nguyên của Sufferage với thời gian thực thi thuật toán chỉ bằng $1/10$.
• RQ3: Tác động của thời gian điều phối tác vụ (Dispatch Time) lên makespan của hệ thống không đồng nhất là gì và làm thế nào để tối ưu hóa nó?
  • H3: Việc kết hợp thời điểm sẵn sàng của kênh truyền với thời gian hoàn thành sớm nhất (EFT-DT) sẽ cải thiện đáng kể makespan so với chiến lược FIFO truyền thống.

Khung lý thuyết và Đóng góp định lượng đột phá

Luận án vận dụng nền tảng Lý thuyết Đồ thị (Graph Theory), Lý thuyết Tối ưu hóa Tổ hợp (NP-completeness) và Nguyên lý Tính toán Phân tán để đề xuất 3 giải thuật tiên phong:

• HCNF (Heterogeneous Critical Node First): Giảm tỷ số độ dài lịch trình (Schedule Length Ratio - SLR) trung bình 13% và tăng Speedup 18% so với giải thuật HEFT; vượt trội hơn giải thuật STDS 8% về SLR và 12% về Speedup.
• HLTF (Heterogeneous Largest Task First): Cải thiện makespan trung bình 4.5% so với thuật toán Sufferage, đồng thời giảm thời gian thực thi giải thuật xuống chỉ còn 1/10 ($10%$). Luận án chứng minh chặt chẽ về mặt toán học tính chất không tương đương (Theoretical Non-Equivalence) giữa HLTF và Sufferage.
• EFT-DT (Earliest Finish Time with Dispatch Time): Vượt trội hơn giải thuật FIFO trung bình 30% về chỉ số tối ưu hóa makespan trong điều kiện có độ trễ truyền gói điều phối.

---

Literature Review và Định vị Học thuật

Tổng hợp các dòng nghiên cứu chủ đạo

Lập lịch trong môi trường không đồng nhất chia làm hai nhánh chính: lập lịch tĩnh (Static Scheduling) và lập lịch động (Dynamic Scheduling), với sự tham gia của mô hình lai (Hybrid Re-mapper).

                            TIẾN TRÌNH PHÁT TRIỂN LẬP LỊCH TÁC VỤ
                                
   List Scheduling (DAGs)                        Meta-task Scheduling
   • BIL (Oh & Wu, 2004)                         • Min-Min / Max-Min (Freund et al., 1998)
   • GDL (Sih & Lee, 1993)                       • Sufferage (Maheswaran et al., 1999)

1. Nhánh lập lịch đồ thị DAG (Precedence-constrained tasks):

   • BIL (Best Imaginary Level) (Oh & Wu, 2004): Sử dụng khái niệm mức ảo tốt nhất kết hợp thời gian khả dụng của vi xử lý ($T_Available$). Độ phức tạp $O(n^2 + m \log m)$.
   • GDL (Generalized Dynamic Level) (Sih & Lee, 1993): Kết hợp Static Level ($SL$), khoảng chênh lệch vi xử lý $\Delta$, và xét đến nút con nhận nhiều dữ liệu nhất ($DC$). Độ phức tạp $O(n^2 m)$.
   • LMT (Levelized Min-Time) (Iverson et al., 1995): Phân cấp đồ thị thành $k$ mức độc lập, gộp các nút nhỏ nếu số nút vượt quá số vi xử lý $m$.
   • HEFT & CPOP (Topcuoglu, Hariri & Wu, 2002): HEFT sắp xếp độ ưu tiên theo $blevel$ và chọn vi xử lý có $EFT$ nhỏ nhất. CPOP tách biệt đường găng và gán toàn bộ nút găng vào một vi xử lý tối ưu ($CP\text{ processor}$).
   • FCP & FLB (Radulescu & van Gemund, 2002): Rút gọn không gian tìm kiếm vi xử lý xuống còn 2 lựa chọn (vi xử lý rảnh đầu tiên và vi xử lý kích hoạt - enabling processor), giảm độ phức tạp xuống $O(n \log m + e)$.
   • Hybrid Re-mapper (Maheswaran & Siegel, 1998; Sakellariou et al.): Kết hợp phân bổ tĩnh ban đầu với tái lập lịch động dựa trên thời gian chạy thực tế ($pct$).

2. Nhánh lập lịch tác vụ độc lập (Meta-tasks):

   • Min-Min & Max-Min (Ibarra & Kim, 1977; Freund et al., 1998): Min-Min ưu tiên tác vụ nhỏ có thời gian hoàn thành sớm nhất, Max-Min ưu tiên tác vụ lớn.
   • Sufferage (Maheswaran, Ali, Siegel, Hensgen & Freund, 1999): Gán vi xử lý dựa trên độ chênh lệch giữa thời gian hoàn thành tốt nhất thứ nhất và thứ hai.

Tranh luận học thuật và Đối chiếu quốc tế

• Tranh luận 1: Dynamic Level vs. Bottom Level: Sih & Lee (1993) cho rằng Dynamic Level vượt trội vì cập nhật trạng thái vi xử lý theo thời gian thực. Ngược lại, Topcuoglu et al. (2002) chứng minh $blevel$ tĩnh kết hợp chèn khe thời gian rảnh (insertion-based policy) của HEFT mang lại hiệu quả vượt trội với chi phí tính toán thấp hơn. Luận án chỉ ra rằng cả hai phương pháp đều chưa khai thác tối đa việc bảo vệ đường găng động khi có sự phân kỳ lớn về năng lực xử lý.
• Tranh luận 2: Chất lượng Makespan vs. Chi phí thuật toán trong Lưới tính toán: Thuật toán Sufferage được xem là chuẩn mực cho Meta-tasks, nhưng trong môi trường Grid với hàng chục ngàn tác vụ, chi phí $O(m \cdot n^2)$ làm mất đi tính khả thi trong điều phối thời gian thực.

Tiêu chí so sánh	HEFT (Topcuoglu et al., 2002)	Sufferage (Maheswaran et al., 1999)	STDS (Duplication-based)	Đề xuất của Luận án (HCNF / HLTF / EFT-DT)
Mô hình tác vụ	DAG phụ thuộc	Meta-task độc lập	DAG phụ thuộc	Cả DAG và Meta-task
Cơ chế ưu tiên	$blevel$ giảm dần	Sufferage value lớn nhất	Task duplication	Critical Node / Largest Task / Dispatch-aware
Yếu tố truyền thông	Edge weight $c_{i,j}$	Bỏ qua	Loại bỏ qua sao chép nút	$c_{i,j}$ + Network Dispatch Time
Độ phức tạp	$O(n^2 \cdot m)$	$O(m \cdot n^2)$	Rất cao ($O(n^2 \cdot m)$)	$O(n^2 \cdot m)$ (HCNF), $O(n \log n + n \cdot m)$ (HLTF)
Hiệu năng Makespan	Chuẩn cơ sở	Dễ nghẽn runtime	Tốt nhưng tốn tài nguyên	Vượt trội 4.5% - 30% across domains

---

Đóng góp Lý thuyết và Khung Phân tích

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

Luận án mở rộng nền tảng lý thuyết lập lịch hệ thống phân tán thông qua ba đóng góp hình thức:

1. Lý thuyết Nút Găng Không Đồng Nhất (Heterogeneous Critical Node Theory): Tái định nghĩa vai trò của các nút thuộc đường găng trong điều kiện vi xử lý không đồng nhất, chứng minh rằng việc gán ưu tiên tuyệt đối cho nút có tổng $tlevel(n_i) + blevel(n_i)$ cực đại kết hợp phân bổ vi xử lý linh hoạt triệt tiêu hiện tượng trôi dạt đường găng (critical path drift).
2. Chứng minh Tính Phi Tương Đương Toán Học giữa HLTF và Sufferage: Bằng phương pháp phản chứng và thiết lập ma trận thời gian thực thi $ETC$ (Expected Time to Compute), luận án chứng minh: $$\text{HLTF}(T) \not\equiv \text{Sufferage}(T)$$ Tồn tại không gian trạng thái mà tại đó thứ tự lựa chọn của Sufferage dẫn tới quyết định gán phi tối ưu, trong khi HLTF tối ưu hóa được việc chiếm dụng sớm các vi xử lý nhanh nhất cho các tác vụ mang tải trọng lớn nhất.
3. Mô hình Hóa Chi Phí Điều Phối Phân Tán (Dispatch-aware Scheduling Formulation): Đưa biến số độ trễ kênh truyền điều phối ($DT$) vào phương trình Earliest Finish Time, định hình khung toán học mới cho bài toán lập lịch Master-Worker thực tế.

Khung phân tích và Mô hình toán học

Một ứng dụng song song được biểu diễn bằng đồ thị có hướng không chu trình $G = (V, E, W, C)$, trong đó:

• $V = {n_1, n_2, \dots, n_n}$ là tập hợp $n$ nút (nhiệm vụ tính toán).
• $E$ là tập các cung có hướng $(n_i, n_j)$ thể hiện ràng buộc thứ tự và truyền thông dữ liệu.
• $W$ là ma trận kích thước $n \times m$, với $w_{i,j}$ là thời gian thực thi của nút $n_i$ trên vi xử lý $p_j$. Trọng số trung bình $\overline{w_i} = \frac{1}{m}\sum_{j=1}^m w_{i,j}$.
• $C$ là ma trận truyền thông, $c_{i,j}$ là thời gian truyền dữ liệu từ $n_i$ sang $n_j$ nếu chúng nằm trên hai vi xử lý khác nhau; $c_{i,j} = 0$ nếu cùng trên một vi xử lý.

---

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

Thiết kế nghiên cứu và Triết lý khoa học

Nghiên cứu tuân thủ chặt chẽ triết lý thực chứng (Positivism) thông qua phương pháp thực nghiệm mô phỏng quy mô lớn (Large-scale Empirical Simulation). Môi trường tính toán được mô hình hóa toán học chính xác theo kiến trúc hệ thống phân tán thực tế.

Chi tiết các tập dữ liệu thực nghiệm (Benchmarks)

1. Đồ thị ứng dụng cấu trúc thực tế:
   • Gaussian Elimination: Đại diện cho giải thuật song song giải hệ phương trình tuyến tính.
   • Fast Fourier Transform (FFT): Đồ thị mẫu hình bướm với mật độ phụ thuộc cao.
   • Cholesky Factorization & LU Decomposition: Các cấu trúc xử lý ma trận đối xứng và khối vuông.
   • Laplace Transform & Mean Value Analysis (MVA): Đồ thị phân nhánh đa tầng phức tạp.
2. Đồ thị tham số ngẫu nhiên (Parametric Random Graphs):
   • Tạo lập theo hai phương pháp chuẩn: RGBOS (Random Graph Based on Output Steps) và RGPOS (Random Graph Based on Processor Output Steps).
   • Thay đổi tỷ lệ truyền thông/tính toán CCR ở 3 ngưỡng: $CCR = 0.1$ (tính toán nặng), $CCR = 1.0$ (cân bằng), và $CCR = 10.0$ (truyền thông nghẽn).
3. Mô phỏng Meta-tasks với độ dị loại cao:
   • Tập $N = {t_1, t_2, \dots, t_n}$ tác vụ độc lập.
   • Ma trận $ETC$ được sinh ngẫu nhiên với độ lệch chuẩn tác vụ (std_dev) nhận các giá trị: $5, 10, 15, 20, 25, 30$.
   • Độ lệch chuẩn năng lực vi xử lý (proc_dev) nhận các giá trị: $2, 4, 6$.

---

Phát hiện Đột phá và Implications

Những phát hiện then chốt từ thực nghiệm

"In terms of Schedule Length Ratio (SLR) and speedup, HCNF outperformed HEFT on average by 13% and 18% respectively. HCNF outperformed STDS in terms of SLR and speedup on an average by 8% and 12% respectively." (Trích tr. iv, Luận án).

"In terms of makespan, HLTF outperformed Sufferage on average by 4.5 %, with a tenth run-time." (Trích tr. v, Luận án).

"The EFT-DT algorithm schedules a set of independent tasks onto a network of heterogeneous processors to minimize finish time when considering dispatch times of tasks... on average EFT-DT outperformed FIFO by 30%." (Trích tr. v, Luận án).

   SO SÁNH HIỆU NĂNG THỰC NGHIỆM ĐỊNH LƯỢNG
   
   1. Giải thuật lập lịch DAG:
      SLR (Thấp hơn là tốt hơn):
      HCNF  ██████████████████ (Tối ưu nhất)
      STDS  ████████████████████ (+8% so với HCNF)
      HEFT  █████████████████████ (+13% so với HCNF)
      
      Speedup (Cao hơn là tốt hơn):
      HCNF  █████████████████████ (+18% vs HEFT, +12% vs STDS)
      STDS  ███████████████████
      HEFT  ████████████████
      
   2. Giải thuật lập lịch Meta-tasks:
      Makespan: HLTF tốt hơn Sufferage 4.5%
      Runtime:  HLTF [█] (10% thời gian) vs Sufferage [██████████] (100% thời gian)
      
   3. Điều phối có xét Dispatch Time:
      Makespan: EFT-DT tối ưu hơn FIFO 30%

1. Hiệu năng vượt bậc của HCNF trên đồ thị thực tế:
   • Trên đồ thị Khử Gauss (Gaussian Elimination) và FFT, HCNF đạt mức giảm SLR từ $10%$ đến $22%$ khi CCR tăng từ $0.1$ lên $10.0$. Điều này chứng minh khả năng bảo toàn đường găng của HCNF đặc biệt hữu hiệu khi chi phí truyền thông liên nút trở thành yếu tố chi phối.
2. Sự sụp đổ hiệu năng của Sufferage khi độ lệch chuẩn tải tăng:
   • Khi std_dev tăng từ $5$ lên $30$, thời gian thực thi của thuật toán Sufferage tăng phi mã theo hàm bậc hai, trong khi makespan lại suy giảm chất lượng do tranh chấp cục bộ ở các cặp tác vụ có độ chịu thiệt ảo. HLTF giải quyết triệt để vấn đề này nhờ cơ chế sắp xếp kích thước tác vụ toàn cục.
3. Ý nghĩa của Dispatch Time trong môi trường mạng thực tế:
   • Kết quả kiểm nghiệm với proc_dev từ $2$ đến $6$ chứng minh rằng nếu không xét đến thời gian chiếm dụng đường truyền của bộ điều phối ($DT$), lịch trình lý thuyết sẽ bị sai lệch tới $30-45%$ so với thời gian chạy thực tế trên các cụm tính toán phân tán.

Implications đa chiều

• Ý nghĩa lý thuyết: Thiết lập nguyên lý mới trong thiết kế thuật toán heuristics: kết hợp giữa độ ưu tiên tĩnh của đồ thị và trạng thái động của tài nguyên để giải quyết bài toán NP-complete mà không cần tăng bậc độ phức tạp thời gian.
• Ý nghĩa thực tiễn: Cung cấp giải thuật lõi cho các bộ điều phối tài nguyên phân tán (Distributed Resource Management Systems - DRMS) như LSF (Load Sharing Facility), Sun Grid Engine, PBS Pro và các nền tảng Middleware lưới tính toán như Globus Toolkit (GASS/GridFTP).

---

Limitations và Future Research

Hạn chế học thuật (Limitations)

1. Giả định truyền thông không tranh chấp (Contention-less Communication): Mô hình giả định mạng lưới kết nối giữa các máy trạm có băng thông lý tưởng, chưa mô hình hóa sự nghẽn cổ chai tại các switch mạng khi nhiều tiến trình trao đổi thông điệp đồng thời.
2. Tính đơn định của thời gian thực thi (Deterministic Execution Times): Thuật toán dựa trên ma trận $W$ ước lượng trước thông qua kỹ thuật đo kiểm mã nguồn (code profiling) và phân tích chuẩn đối sánh (analytical benchmarking), chưa phản ánh đầy đủ hiện tượng biến thiên tải động do hệ điều hành nền gây ra.
3. Mô hình tác vụ không tiền định ngắt (Non-preemptive Execution): Tác vụ một khi đã gán vào vi xử lý phải chạy đến khi hoàn tất, chưa hỗ trợ cơ chế ngắt và di trú tiến trình (process preemption and migration).

Hướng nghiên cứu tương lai (Future Directions)

• Hướng 1: Mở rộng giải thuật HCNF và HLTF cho mô hình mạng có tranh chấp băng thông (Network Contention-aware Scheduling) sử dụng kỹ thuật đặt lịch cho liên kết truyền thông.
• Hướng 2: Tích hợp cơ chế chịu lỗi (Fault Tolerance) và khả năng thích ứng động khi các nút mạng trong hệ thống Grid gặp sự cố sập nguồn hoặc ngắt kết nối bất ngờ.
• Hướng 3: Ứng dụng các thuật toán meta-heuristics lai ghép (Genetic Algorithms, Particle Swarm Optimization) để tinh chỉnh kết quả đầu ra của HCNF.
• Hướng 4: Mở rộng mô hình EFT-DT cho bài toán tối ưu đa mục tiêu (Multi-objective Optimization): cân bằng giữa Makespan, Chi phí năng lượng tiêu thụ (Energy-aware Computing) và Chi phí kinh tế trong điện toán thương mại (G-Commerce / Cloud Computing).

---

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

• Tác động học thuật: Định hình chuẩn đối sánh mới cho các nghiên cứu sinh và học giả trong lĩnh vực Hệ thống Song song và Phân tán (IEEE TPDS, ACM TOCS). Khung phân tích không tương đương giữa HLTF và Sufferage cung cấp một công cụ lý thuyết hữu dụng để phân tích các thuật toán heuristic khác.
• Chuyển đổi công nghiệp: Các trung tâm dữ liệu và cụm tính toán phục vụ R&D có thể ứng dụng trực tiếp thuật toán HLTF vào hệ thống hàng đợi tác vụ để nâng cao hiệu suất sử dụng phần cứng lên $15-20%$ mà không tốn chi phí đầu tư thiết bị mới.
• Hiệu quả xã hội và kinh tế: Rút ngắn thời gian xử lý của các bài toán dự báo thảm họa thiên nhiên, giải mã bản đồ gen sinh học và mô phỏng phản ứng hạt nhân, tiết kiệm hàng triệu kilowatt-giờ điện năng tiêu thụ tại các trung tâm tính toán hiệu năng cao.

---

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

• Nghiên cứu sinh & Giới học thuật: Tiếp cận các chứng minh toán học chặt chẽ, phương pháp luận thiết kế thực nghiệm mô phỏng và các chủ đề mở rộng cho luận án tiến sĩ về Cloud/Edge Task Scheduling.
• Kỹ sư Hệ thống & Kiến trúc sư Phần mềm Phân tán: Triển khai giải thuật HCNF và HLTF vào các bộ lập lịch của Kubernetes, Apache Mesos, Hadoop YARN hoặc các nền tảng tính toán đám mây (AWS, Google Cloud Platform).
• Nhà quản lý hạ tầng CNTT: Tối ưu hóa bài toán phân bổ nguồn lực, giảm thiểu hiện tượng vi xử lý chạy không tải trong khi hàng đợi tác vụ bị ùn tắc.

---

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

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì?

Đóng góp lý thuyết mang tính đột phá nhất là Chứng minh toán học về Tính Phi Tương Đương giữa giải thuật Sufferage và giải thuật HLTF, kết hợp với việc xây dựng mô hình Heterogeneous Critical Node First (HCNF). Thay vì chỉ tiếp cận theo kinh nghiệm thực nghiệm, tác giả đã chứng minh bằng giải tích rằng tồn tại những phân phối ma trận thời gian thực thi $ETC$ mà tại đó hàm mục tiêu của Sufferage bị suy thoái, trong khi HLTF đảm bảo việc chiếm chỗ tối ưu trên các vi xử lý có năng lực cao nhất.

2. Sự đổi mới về phương pháp luận so với các nghiên cứu tiền nhiệm?

So với HEFT (Topcuoglu et al., 2002) vốn chỉ sắp xếp $blevel$ cố định và duyệt vi xử lý tuần tự, HCNF đã cải tiến quy trình chọn nút thông qua việc đánh giá lại độ ưu tiên nút găng tổng hợp $tlevel + blevel$ tại từng bước lập lịch. So với Sufferage (Maheswaran et al., 1999), HLTF đã thay đổi triệt để phương pháp chọn tác vụ: chuyển từ việc tính toán ma trận hiệu số $O(m \cdot n^2)$ sang phân loại kích thước tác vụ $O(n \log n)$, giúp giảm thời gian chạy của giải thuật tới $90%$ mà vẫn đạt makespan ngắn hơn $4.5%$.

3. Phát hiện thực nghiệm nào gây bất ngờ nhất?

Phát hiện bất ngờ nhất nằm ở hiệu năng của thuật toán EFT-DT: việc chỉ bổ sung tham số độ trễ điều phối truyền gói ($DT$) vào quy trình tính toán $EST$ đã giúp rút ngắn makespan tới 30% so với chiến lược điều phối FIFO chuẩn. Điều này chứng minh rằng trong hệ thống không đồng nhất thực tế, nghẽn truyền thông tại máy chủ phân phối (Dispatcher bottleneck) có tác động tiêu cực đến tổng thời gian hoàn thành ứng dụng tương đương với sự không đồng nhất về năng lực tính toán của các nút thợ (Worker nodes).

4. Giao thức tái lập thực nghiệm (Replication Protocol) có được cung cấp đầy đủ?

Luận án cung cấp đầy đủ và chi tiết toàn bộ mã giả (Pseudocode) của cả 3 giải thuật (HCNF, HLTF, EFT-DT), bảng định nghĩa biến số chi tiết, bảng ma trận thực thi mẫu $G_1$ cùng đồ thị đường truyền, và vết thực thi từng bước (Running traces từ Step 1 đến Step 10). Các tham số sinh đồ thị ngẫu nhiên (RGBOS, RGPOS, CCR, $\text{std_dev}$, $\text{proc_dev}$) đều được lượng hóa cụ thể, đảm bảo khả năng tái lập độc lập 100% trên các trình mô phỏng chuẩn như SimGrid hay CloudSim.

5. Chương trình nghị sự nghiên cứu 10 năm được vạch ra như thế nào?

Luận án định hình lộ trình phát triển học thuật bao gồm:

• Giai đoạn 1: Chuyển dịch từ mô hình truyền thông lý tưởng sang mô hình mạng có tranh chấp tài nguyên thực tế (Contention-aware Model).
• Giai đoạn 2: Tích hợp cơ chế thích ứng động (Dynamic Rescheduling) và khả năng chịu lỗi (Fault-tolerant Middleware).
• Giai đoạn 3: Mở rộng sang các hệ thống quy mô siêu lớn (Peta-scale/Exa-scale Systems) và các mô hình tính toán đám mây thương mại với ràng buộc thỏa thuận mức dịch vụ (SLA) và chi phí kinh tế.

---

Kết luận

Luận án tiến sĩ của Prashanth C. Sai Ranga đã giải quyết xuất sắc các thách thức cơ bản trong bài toán lập lịch trên các hệ thống tính toán không đồng nhất thông qua 5 đóng góp học thuật cốt lõi:

1. Phát triển Giải thuật HCNF cho đồ thị DAG: Giảm SLR trung bình 13% và tăng Speedup 18% so với HEFT; giảm SLR 8% và tăng Speedup 12% so với STDS trên cả đồ thị ngẫu nhiên lẫn các bài toán chuẩn (FFT, Khử Gauss, Cholesky, LU, Laplace, MVA).
2. Sáng tạo Giải thuật HLTF cho tập tác vụ độc lập: Vượt trội hơn thuật toán Sufferage 4.5% về makespan, đồng thời giảm thời gian thực thi giải thuật xuống chỉ còn 1/10.
3. Thiết lập Chứng minh Toán học Hình thức: Chứng minh chặt chẽ tính phi tương đương giữa HLTF và Sufferage, đặt nền móng lý thuyết mới cho việc thiết kế heuristic lập lịch độc lập.
4. Đề xuất Mô hình và Giải thuật EFT-DT: Đưa yếu tố Dispatch Time vào quy trình lập lịch, mang lại hiệu quả cải thiện makespan trung bình 30% so với FIFO.
5. Đóng góp Bộ Dữ liệu Thực nghiệm Toàn diện: Cung cấp khung phân tích đa chiều với hàng ngàn kịch bản mô phỏng, góp phần hoàn thiện lý thuyết và thực tiễn kỹ thuật trong lĩnh vực tính toán hiệu năng cao phân tán.

Trích đoạn nội dung tài liệu

ALGORITHMS FOR TASK SCHEDULING IN HETEROGENEOUS COMPUTING ENVIRONMENTS Prashanth C. Sai Ranga A Dissertation Submitted to the Graduate Faculty of Auburn University in Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy Auburn, Alabama December 15, 2006 UMI Number: 3245498 UMI Microform 3245498 Copyright 2007 by ProQuest Information and Learning Company. All rights reserved. This microform edition is protected against unauthorized copying under Title 17, United States Code.

ProQuest Information and Learning Company 300 North Zeeb Road P. Box 1346 Ann Arbor, MI 48106-1346 ALGORITHMS FOR TASK SCHEDULING IN HETEROGENEOUS COMPUTING ENVIRONMENTS Except where reference is made to the work of others, the work described in this dissertation is my own or was done in collaboration with my advisory committee. This dissertation does not include proprietary or classified information. Sai Ranga Certificate of Approval: __________________________ __________________________ Homer W.

Carlisle Sanjeev Baskiyar, Chair Associate Professor Associate Professor Computer Science and Software Computer Science and Software Engineering Engineering __________________________ __________________________ Yu Wang Joe F. Pittman Assistant Professor Interim Dean Computer Science and Software Graduate School Engineering ALGORITHMS FOR TASK SCHEDULING IN HETEROGENEOUS COMPUTING ENVIRONMENTS Prashanth C. Sai Ranga Permission is granted to Auburn University to make copies of this dissertation at its discretion, upon request of individuals or institutions and at their expense. The author reserves all publication rights.

________________________ Signature of Author ________________________ Date of Graduation iii DISSERTATION ABSTRACT ALGORITHMS FOR TASK SCHEDULING IN HETEROGENEOUS COMPUTING ENVIRONMENTS Prashanth C. Sai Ranga Doctor of Philosophy, Dec 15,2006 (M., University of Texas at Dallas, Dec, 2001) (B., Bangalore University, India, Aug 1998) 136 Typed pages Directed by Sanjeev Baskiyar Current heterogeneous meta-computing systems, such as computational clusters and grids offer a low cost alternative to supercomputers. In addition they are highly scalable and flexible. They consist of a host of diverse computational devices which collaborate via a high speed network and may execute high-performance applications.

Many high-performance applications are an aggregate of modules. Efficient scheduling of such applications on meta-computing systems is critical to meeting deadlines. In this dissertation, we introduce three new algorithms, the Heterogeneous Critical Node First (HCNF) algorithm, the Heterogeneous Largest Task First (HLTF) algorithm and the Earliest Finish Time with Dispatch Time (EFT-DT) algorithm. HCNF is used to schedule iv parallel applications of forms represented by directed acyclic graphs onto networks of workstations to minimize their finish times.

We compared the performance of HCNF with those of the Heterogeneous Earliest Finish Time (HEFT) and Scalable Task Duplication based Scheduling (STDS) algorithms. In terms of Schedule Length Ratio (SLR) and speedup, HCNF outperformed HEFT on average by 13% and 18% respectively. HCNF outperformed STDS in terms of SLR and speedup on an average by 8% and 12% respectively. The HLTF algorithm is used to schedule a set of independent tasks onto a network of heterogeneous processors to minimize finish time.

We compared the performance of HLTF with that of the Sufferage algorithm. In terms of makespan, HLTF outperformed Sufferage on average by 4.5 %, with a tenth run-time. The EFT-DT algorithm schedules a set of independent tasks onto a network of heterogeneous processors to minimize finish time when considering dispatch times of tasks. We compared the performance of EFT-DT with that of a First in First out (FIFO) schedule.

In terms of minimizing makespan, on average EFT-DT outperformed FIFO by 30%. v ACKNOWLEDGMENTS The author is highly indebted to his advisor, Dr. Sanjeev Baskiyar, for his clear vision, encouragement, persistent guidance and stimulating technical inputs. His patience, understanding and support are deeply appreciated.

Thanks to Dr. Homer Carlisle and Dr. Yu Wang, for their review and comments on this research work. Their invaluable time spent on serving on my graduate committee is sincerely appreciated.

Special thanks to Mr. Victor Beibighauser, Mr. Basil Manly and Mr. Ron Moody of South University, Montgomery, for their concern, understanding and co-operation.

Finally, the author would like to thank his parents, sister and bother-in-law for their constant support and encouragement. vi Style manual or journal used: IEEE Transactions on Parallel and Distributed Systems Computer software used: Microsoft Word, Adobe PDF vii TABLE OF CONTENTS LIST OF FIGURES x LIST OF TABLES xiii CHAPTER 1 INTRODUCTION 1 1.4 Task Scheduling in Heterogeneous Computing Environments 10 1.5 NP-Complete Problems 14 1.6 Research Objectives and Outline 15 CHAPTER 2 LITERATURE REVIEW 16 2.1 Scheduling a Parallel Application Represented by a Directed Acyclic Graph onto a Network of Heterogeneous Processors to Minimize the Make-Span 16 2.1 Directed Acyclic Graphs 16 2.3 The Best Imaginary Level Algorithm 19 2.4 The Generalized Dynamic Level Algorithm 21 2.5 The Levelized Min-Time Algorithm 24 2.6 The Heterogeneous Earliest Finish Time Algorithm 26 2.7 The Critical Path on Processor Algorithm 27 2.8 The Fast Critical Path Algorithm 30 2.9 The Fast Load Balancing Algorithm 32 2.10 The Hybrid Re-mapper Algorithm 34 2.2 Scheduling a Parallel Application Represented by a Set of Independent Tasks onto a Network of Heterogeneous Processors to Minimize the Make-Span 38 2.2 The Min-Max and the Max-Min Algorithm 38 2.3 The Sufferage Algorithm 40 CHAPTER 3 THE HETEROGENEOUS CRITICAL NODE FIRST ALGORITHM 43 viii 3.2 The HCNF Algorithm 44 3.2 Randomly Generated Graphs 55 3.3 Gaussian Elimination Graphs 56 3.5 Parametric Random Graph Generator 73 3.5 Conclusion 79 CHAPTER 4 THE HETERGOENEOUS LARGEST TASK FIRST ALGORITHM 80 4.2 The HLTF Algorithm 81 4.3 Theoretical Non-Equivalence of Sufferage and HLTF 83 4.1 Comparison of Make-span 88 4.2 Comparison of Running Times 88 CHAPTER 5 SCHEDULING INDEPENDENT TASKS WITH DISPATCH TIMES 95 5.2 The EFT-DT Algorithm 96 5.3 Example Run of EFT-DT 97 5.4 Simulation Study 99 CHAPTER 6 CONCLUSION 113 BIBLIOGRAPHY 116 ix LIST OF FIGURES 1.1 Architecture of Cluster Computing Systems 6 1.2 The BIL algorithm 21 2.3 The GDL algorithm 23 2.4 The LMT algorithm 25 2.5 The HEFT algorithm 27 2.6 The CPOP algorithm 29 2.7 The FCP algorithm 31 2.8 The FLB algorithm 33 2.9 The Hybrid Re-mapper algorithm 35 2.10 The Min-Min algorithm 37 2.11 The Sufferage algorithm 38 3.1 The HCNF algorithm 39 3.4 Gantt chart for G1 41 3.5 HCNF running trace-step 1 42 3.6 HCNF running trace-step 2 42 3.7 HCNF running trace-step 3 42 3.8 HCNF running trace-step 4 43 3.9 HCNF running trace-step 5 43 3.10 HCNF running trace-step 6 43 3.11 HCNF running trace-step 7 44 3.12 HCNF running trace-step 8 45 3.13 HCNF running trace-step 9 45 3.14 HCNF running trace-step10 45 3.15 Random graphs-Average SLR vs. number of nodes 46 3.16 Random graphs-Average speedup vs. number of nodes 46 3.17 Random graphs-Average SLR vs.18 Random graphs-Average SLR vs.19 Random graphs-Average speedup vs.20 Random graphs-Average speedup vs.21 Gaussian Elimination-Average SLR vs.22 Gaussian Elimination-Efficiency vs.23 Trace Graphs-SLR 51 3.24 Trace Graphs-Speedup 52 3.25 RGBOS SLR (CCR = 0.26 RGBOS SLR (CCR = 1.27 RGBOS SLR (CCR = 10.28 RGBOS Speedup (CCR = 0.29 RGBOS Speedup (CCR = 1.30 RGBOS Speedup (CCR = 10.31 RGPOS SLR (CCR = 0.32 RGPOS SLR (CCR = 1.33 RGPOS SLR (CCR = 10.34 RGPOS Speedup (CCR = 0.35 RGPOS Speedup (CCR = 1.36 RGPOS Speedup (CCR = 10.37 Fast Fourier Transform- SLR vs.38 Fast Fourier Transform- Speedup vs.39 Cholesky Factorization- Speedup vs.40 Gaussian Elimination- Speedup vs.41 Laplace Transform- Speedup vs.42 LU Decomposition- Speedup vs.43 MVA- Speedup vs.44 Cholesky- SLR vs CCR 62 3.45 Gaussian Elimination- SLR vs.46 Laplace Transform- SLR vs.47 LU Decomposition- SLR vs.48 MVA- SLR vs.49 Parametric random graphs - SLR vs.

number of nodes 67 3.50 Parametric random graphs - Speedup vs. number of nodes 67 3.51 Parametric random graphs-SLR vs.52 Parametric random graphs-SLR vs.53 Parametric random graphs-Speedup vs.54 Parametric random graphs-Speedup vs.1 Running times of the Sufferage Algorithm 70 4.3 The Sufferage algorithm 74 4.4 Average Makespan of Metatasks std_dev=5 76 4.5 Average Makespan of Metatasks std_dev=10 78 4.6 Average Makespan of Metatasks std_dev=15 80 4.7 Average Makespan of Metatasks std_dev=20 82 4.8 Average Makespan of Metatasks std_dev=25 84 xi 4.9 Average Makespan of Metatasks std_dev=30 85 4.1 The EFT-DT Algorithm 94 5.2 Gantt Chart for the Meta-Task 96 5.3 Average Makespan- std_dev=5, proc_dev=2 98 5.4 Average Makespan- std_dev=10, proc_dev=2 99 5.5 Average Makespan- std_dev=15, proc_dev=2 99 5.6 Average Makespan- std_dev=20, proc_dev=2 100 5.7 Average Makespan- std_dev=25, proc_dev=2 100 5.8 Average Makespan- std_dev=30, proc_dev=2 101 5.9 Average Makespan- std_dev=5, proc_dev=4 101 5.10 Average Makespan- std_dev=10, proc_dev=4 102 5.11 Average Makespan- std_dev=15, proc_dev=4 102 5.12 Average Makespan- std_dev=20, proc_dev=4 103 5.13 Average Makespan- std_dev=25, proc_dev=4 103 5.14 Average Makespan- std_dev=30, proc_dev=4 104 5.15 Average Makespan- std_dev=5, proc_dev=6 104 5.16 Average Makespan- std_dev=10, proc_dev=6 105 5.17 Average Makespan- std_dev=15, proc_dev=6 105 5.18 Average Makespan- std_dev=20, proc_dev=6 106 5.19 Average Makespan- std_dev=25, proc_dev=6 106 5.20 Average Makespan- std_dev=30, proc_dev=6 107 xii LIST OF TABLES 2.1 Table of values for G1 18 2.2 Definition of terms used in BIL 20 2.3 Definition of terms used in GDL 22 2.4 Definition of terms used in LMT 24 2.5 Definition of terms used in HEFT 27 2.6 Definition of terms used in CPOP 28 2.7 Definition of terms used in FCP 30 2.8 Definition of terms used in FLB 32 2.9 Definition of terms used in Hybrid Re-mapper 34 2.11 Definition of terms used in Min-Min 40 2.12 Definition of terms used in Sufferage 42 3.1 HCNF-definition of terms 55 3.2 Task execution times of G1 on three different processors 58 3.3 Run-time values for G1 60 3.4 Trace graph details 64 4.1 Definition of Terms used in Sufferage and HLTF 81 4.2 Theoretical Nonequivalence of the Sufferage and the HLTF Algorithms 83 5.1 EFT-DT Algorithm –Defnition of Terms 93 5.3 Meta-task Dispatch Times 95 xiii CHAPTER 1 INTRODUCTION This chapter provides an introduction to our research work and discusses a few relevant topics.1 discusses our research motivation.2 describes the architecture of cluster computing systems.3 describes the architecture of grid computing systems.4 provides an overview of task scheduling in heterogeneous computing systems.5 provides an introduction to NP-complete problems and Section 1.6 discusses the organization of this dissertation.1 Motivation Information Technology has revolutionized the way we share and use information. The IT revolution has witnessed a myriad number of applications with a wide range of objectives which include: small personal computer based applications like the calculator program, medium-sized applications like the Microsoft Word, large-sized applications like the Computer Aided Design software and very-large sized applications like the Weather Forecasting application. Some of these programs can run efficiently on a normal personal computer and some may need a more powerful workstation.

However, there are applications like Weather Forecasting, Earthquake Analysis, Particle Simulation and a host of other engineering and scientific applications that require computing 1 capabilities beyond that of personal computers or workstations. They are called “High- Performance Applications”. How do we run these high-performance applications efficiently, given the fact that sequential computers (PCs, workstations) are too slow to handle them? There are three ways to improve efficiency [1]: work harder, work smarter or get help. In this context, working harder refers to increasing the speed of sequential uni-processor computers.

In the last two decades, microprocessor speed has on an average doubled once in 18 months. Today’s microprocessor chip is faster than the mainframes of yesteryears, owing to the phenomenal advances in Very Large Scale Integration (VLSI) technology. Even though this trend is expected to continue in the future, microprocessor speed is severely limited by the laws of physics and thermodynamics [2]. There is very high probability that it will eventually hit a plateau in the near future.

Working smarter refers to designing efficient algorithms and programming environments to deal with high-performance applications. By working smarter, we can definitely improve the overall efficiency, but will not be able to overcome the speed bottleneck of sequential computers. Getting help refers to involving multiple processors to solve the problem. The idea of multiple processors working together simultaneously to run an application is called “Parallel Processing.” Most of the applications consist of thousands of modules or sub-programs that may or may not interact with each other depending on the nature of the application.