Thuật toán lập lịch tác vụ - Môi trường tính toán không đồng nhất
Luận án tiến sĩ 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. Đề xuất ba thuật toán mới cải tiến hiệu suất 4-30% so với phương pháp hiện có.
auburn university
Computer Science and Software Engineering
Luan An
Luận án
Năm xuất bản
Số trang
136
Thời gian đọc
21 phút
Lượt xem
0
Lượt tải
0
Phí lưu trữ
40 Point
Mục lục chi tiết
Tóm tắt nội dung
I. Thuật Toán Lập Lịch Tác Vụ Trong Hệ Thống Phân Tán
Task scheduling algorithm đóng vai trò then chốt trong heterogeneous computing environments. Các hệ thống meta-computing hiện đại như computational clusters và grid computing cung cấp giải pháp thay thế supercomputers với chi phí thấp hơn. Những hệ thống này bao gồm nhiều thiết bị tính toán đa dạng, kết nối qua mạng tốc độ cao. Chúng có khả năng mở rộng và linh hoạt cao. Việc lập lịch hiệu quả các ứng dụng hiệu năng cao trên meta-computing systems là yếu tố quyết định để đáp ứng deadline. Nhiều ứng dụng high-performance là tập hợp của các modules. Distributed computing yêu cầu thuật toán tối ưu để phân bổ tài nguyên. Load balancing đảm bảo sử dụng tài nguyên đồng đều. Resource allocation ảnh hưởng trực tiếp đến hiệu suất tổng thể. Makespan optimization là mục tiêu chính của các thuật toán scheduling. DAG scheduling xử lý các tác vụ có phụ thuộc. Parallel processing tận dụng tối đa khả năng của hệ thống không đồng nhất.
1.1. Đặc Điểm Môi Trường Tính Toán Không Đồng Nhất
Heterogeneous computing environments bao gồm processors với khả năng xử lý khác nhau. Mỗi processor có tốc độ và năng lực tính toán riêng biệt. Network bandwidth giữa các nodes không đồng nhất. Communication cost phụ thuộc vào khoảng cách và băng thông. Cloud computing và grid computing là hai ví dụ điển hình. Hệ thống này cung cấp tính linh hoạt cao trong resource allocation. Task scheduling phải xem xét sự không đồng nhất này.
1.2. Thách Thức Trong Lập Lịch Tác Vụ
Task scheduling trong heterogeneous computing là bài toán NP-Complete. Không tồn tại thuật toán polynomial-time để tìm giải pháp tối ưu. Số lượng cấu hình scheduling tăng theo hàm mũ với số tác vụ. Load balancing trở nên phức tạp khi processors không đồng nhất. Communication overhead ảnh hưởng đến makespan. Distributed computing yêu cầu đồng bộ giữa các nodes. Parallel processing cần xử lý dependencies giữa tasks.
1.3. Mục Tiêu Tối Ưu Hóa Chính
Makespan optimization là mục tiêu hàng đầu trong task scheduling algorithm. Minimize finish time đảm bảo ứng dụng hoàn thành sớm nhất. Resource allocation hiệu quả tăng throughput hệ thống. Load balancing giảm idle time của processors. DAG scheduling phải đảm bảo thứ tự thực thi đúng. Communication cost cần được tối thiểu hóa. Parallel processing tối đa hóa utilization của hệ thống.
II. Thuật Toán HCNF Cho Lập Lịch DAG Scheduling
Heterogeneous Critical Node First (HCNF) algorithm được thiết kế cho parallel applications dạng directed acyclic graphs. Thuật toán này schedule tasks lên networks of workstations để minimize finish times. HCNF xác định critical nodes dựa trên upward rank. Critical path được ưu tiên trong quá trình scheduling. Algorithm phân tích dependencies giữa các tasks. DAG scheduling đảm bảo precedence constraints được thỏa mãn. HCNF so sánh với Heterogeneous Earliest Finish Time (HEFT) và Scalable Task Duplication based Scheduling (STDS). Kết quả cho thấy HCNF vượt trội về Schedule Length Ratio (SLR) và speedup. HCNF outperformed HEFT trung bình 13% về SLR và 18% về speedup. So với STDS, HCNF tốt hơn 8% về SLR và 12% về speedup. Makespan optimization đạt được thông qua việc ưu tiên critical tasks. Resource allocation được tối ưu hóa dựa trên task priorities.
2.1. Nguyên Lý Hoạt Động HCNF
HCNF tính upward rank cho mỗi node trong DAG. Upward rank phản ánh độ dài critical path từ node đến exit node. Algorithm sắp xếp tasks theo thứ tự giảm dần của upward rank. Critical nodes được schedule trước để minimize makespan. Parallel processing được tối ưu bằng cách xem xét processor availability. Load balancing đạt được thông qua earliest finish time criterion. Communication cost được tính vào earliest finish time.
2.2. So Sánh Hiệu Suất Với HEFT
HEFT algorithm sử dụng earliest finish time để chọn processor. HCNF cải tiến bằng cách ưu tiên critical nodes. Experiments cho thấy HCNF giảm average schedule length 13%. Speedup improvement đạt 18% so với HEFT. DAG scheduling với HCNF xử lý dependencies hiệu quả hơn. Resource allocation trong HCNF tối ưu hơn HEFT. Makespan reduction đạt được nhờ critical path analysis.
2.3. Ưu Điểm So Với STDS Algorithm
STDS sử dụng task duplication để giảm communication overhead. HCNF không cần duplication nhưng vẫn đạt hiệu suất tốt. Schedule Length Ratio của HCNF thấp hơn STDS 8%. Speedup improvement đạt 12% trung bình. Parallel processing efficiency cao hơn với HCNF. Load balancing được cải thiện nhờ critical node prioritization. Resource utilization tối ưu hơn mà không cần task duplication.
III. Thuật Toán HLTF Cho Independent Tasks Scheduling
Heterogeneous Largest Task First (HLTF) algorithm được thiết kế để schedule independent tasks lên heterogeneous processors network. Algorithm này minimize finish time cho tập tasks không có dependencies. HLTF sắp xếp tasks theo thứ tự giảm dần của execution time. Largest tasks được assign trước để cân bằng load. Load balancing đạt được thông qua greedy assignment strategy. Resource allocation dựa trên minimum completion time criterion. HLTF được so sánh với Sufferage algorithm về hiệu suất. Makespan của HLTF tốt hơn Sufferage trung bình 4.5%. Runtime của HLTF chỉ bằng một phần mười Sufferage. Parallel processing được tối ưu hóa thông qua task ordering. Heterogeneous computing environments được khai thác hiệu quả. Cloud computing applications hưởng lợi từ HLTF scheduling. Grid computing systems cải thiện throughput với HLTF. Distributed computing đạt makespan optimization tốt hơn.
3.1. Chiến Lược Largest Task First
HLTF sắp xếp independent tasks theo execution time giảm dần. Largest tasks được schedule trước để tránh bottleneck cuối cùng. Load balancing được cải thiện khi large tasks phân bố sớm. Resource allocation cho small tasks linh hoạt hơn. Makespan optimization đạt được thông qua early placement. Parallel processing tối đa hóa processor utilization. Heterogeneous computing environments được khai thác tối ưu.
3.2. So Sánh Với Sufferage Algorithm
Sufferage algorithm tính sufferage value cho mỗi task. Sufferage value là chênh lệch giữa best và second-best processor. HLTF đơn giản hơn với complexity thấp hơn. Makespan của HLTF tốt hơn 4.5% trung bình. Runtime của HLTF nhanh hơn 10 lần Sufferage. Task scheduling algorithm HLTF scalable hơn cho large problem sizes. Resource allocation efficiency tương đương nhưng faster execution.
3.3. Ứng Dụng Trong Cloud Computing
Cloud computing environments có nhiều independent tasks. HLTF phù hợp cho batch processing trong cloud. Load balancing giữa cloud instances được cải thiện. Resource allocation tối ưu hóa cost trong pay-per-use model. Makespan reduction giảm thời gian xử lý jobs. Distributed computing trong cloud hưởng lợi từ HLTF. Grid computing applications cũng áp dụng HLTF hiệu quả.
IV. Thuật Toán EFT DT Xem Xét Dispatch Time
Earliest Finish Time with Dispatch Time (EFT-DT) algorithm schedule independent tasks với dispatch times consideration. Dispatch time là thời gian cần thiết để transfer task đến processor. Task scheduling algorithm truyền thống thường bỏ qua dispatch overhead. EFT-DT tính cả dispatch time vào earliest finish time calculation. Algorithm này realistic hơn cho distributed computing environments. Network latency và bandwidth limitations được xem xét. Resource allocation phải account cho communication delays. EFT-DT được so sánh với First In First Out (FIFO) scheduling. Makespan của EFT-DT tốt hơn FIFO trung bình 30%. Load balancing được cải thiện đáng kể. Parallel processing efficiency tăng khi xem xét dispatch times. Heterogeneous computing với varying network speeds hưởng lợi. Cloud computing và grid computing với geographic distribution cần EFT-DT. Communication cost trở thành factor quan trọng trong scheduling decision.
4.1. Tầm Quan Trọng Của Dispatch Time
Dispatch time bao gồm network transfer time và setup overhead. Distributed computing systems có dispatch times đáng kể. Ignoring dispatch time dẫn đến suboptimal schedules. Resource allocation không chính xác khi bỏ qua dispatch cost. Makespan thực tế cao hơn predicted makespan. EFT-DT algorithm addresses gap này hiệu quả. Cloud computing với data transfer costs cần consider dispatch times.
4.2. Cơ Chế Hoạt Động EFT DT
EFT-DT tính earliest finish time bao gồm cả dispatch time. Algorithm chọn processor minimizing total completion time. Dispatch time được estimate dựa trên task size và bandwidth. Load balancing xem xét cả computation và communication. Resource allocation tối ưu cho heterogeneous computing environments. Parallel processing được schedule với realistic time estimates. Makespan optimization đạt được thông qua accurate modeling.
4.3. Hiệu Suất Vượt Trội So Với FIFO
FIFO scheduling không xem xét processor heterogeneity. FIFO assign tasks theo thứ tự arrival mà không optimize. EFT-DT outperformed FIFO 30% về makespan reduction. Task scheduling algorithm EFT-DT thích nghi với system conditions. Load balancing của EFT-DT superior hơn nhiều. Resource allocation intelligent hơn với dispatch time consideration. Grid computing và distributed computing đạt efficiency cao hơn.
V. Phân Tích Độ Phức Tạp NP Complete Problems
Task scheduling trong heterogeneous computing environments là NP-Complete problem. Không tồn tại polynomial-time algorithm cho optimal solution. Search space tăng exponentially với số lượng tasks và processors. Brute force approach không khả thi cho large-scale problems. Heuristic algorithms cung cấp near-optimal solutions trong reasonable time. HCNF, HLTF, và EFT-DT là heuristic approaches hiệu quả. Complexity analysis cho thấy polynomial time complexity của các algorithms. HCNF có complexity O(v² × p) với v tasks và p processors. HLTF có complexity O(n log n + n × m) với n tasks và m processors. EFT-DT có complexity tương tự HLTF nhưng thêm dispatch time calculation. Makespan optimization đạt được trong acceptable time. Resource allocation decisions được thực hiện efficiently. Load balancing achieved mà không cần exhaustive search. Parallel processing scheduling scalable cho large systems.
5.1. Bản Chất NP Complete Của Task Scheduling
Task scheduling problem thuộc class NP-Complete. Optimal solution requires checking all possible schedules. Number of schedules grows factorially với task count. Heterogeneous computing thêm dimension của processor selection. Distributed computing có thêm communication cost considerations. Polynomial-time optimal algorithm không tồn tại unless P=NP. Heuristic approaches necessary cho practical applications.
5.2. Time Complexity Của Các Thuật Toán
HCNF algorithm có time complexity O(v² × p). DAG scheduling complexity phụ thuộc vào graph structure. HLTF complexity O(n log n + n × m) dominated bởi sorting. EFT-DT có similar complexity với HLTF. Dispatch time calculation thêm constant factor overhead. All algorithms polynomial time và practical cho large inputs. Makespan optimization achieved efficiently.
5.3. Trade off Giữa Optimality Và Efficiency
Optimal scheduling requires exponential time exploration. Heuristic algorithms trade optimality cho polynomial time. HCNF, HLTF, EFT-DT provide near-optimal solutions. Experimental results show small optimality gap. Resource allocation quality cao với fast execution. Load balancing effectiveness validated through comparisons. Parallel processing benefits outweigh small optimality loss.
VI. Ứng Dụng Trong Grid Computing Và Cloud Computing
Grid computing và cloud computing là application domains chính cho task scheduling algorithms. Grid computing kết nối geographically distributed resources. Cloud computing cung cấp on-demand scalable resources. Heterogeneous computing environments là đặc điểm của cả hai. Resource allocation trong grid phức tạp do administrative domains khác nhau. Cloud computing có dynamic resource availability. HCNF algorithm phù hợp cho workflow scheduling trong grids. DAG scheduling của scientific workflows benefits từ HCNF. HLTF ideal cho batch job scheduling trong cloud. Independent tasks trong cloud được schedule efficiently. EFT-DT critical cho wide-area distributed computing. Network latency trong grid computing được EFT-DT address. Makespan optimization quan trọng cho cost reduction trong cloud. Load balancing ensures efficient resource utilization. Parallel processing maximizes throughput trong cả grid và cloud. Task scheduling algorithm impact trực tiếp đến performance và cost.
6.1. Grid Computing Workflow Scheduling
Scientific workflows trong grid computing là DAGs phức tạp. HCNF algorithm optimal cho workflow scheduling. Distributed computing resources across organizations cần coordination. Resource allocation phải respect site policies. Makespan optimization critical cho scientific deadlines. Communication cost significant trong wide-area networks. EFT-DT addresses dispatch times trong grid environments.
6.2. Cloud Computing Batch Processing
Cloud computing batch jobs thường là independent tasks. HLTF algorithm ideal cho cloud batch scheduling. Resource allocation dynamic dựa trên availability. Load balancing across cloud instances improves utilization. Makespan reduction translates to cost savings. Pay-per-use model incentivizes efficient scheduling. Parallel processing maximizes cloud resource value.
6.3. Hybrid Cloud Grid Environments
Hybrid environments combine grid và cloud resources. Heterogeneous computing extreme trong hybrid systems. Task scheduling algorithms phải adapt to diversity. Resource allocation spans multiple administrative domains. Load balancing challenging với different pricing models. Makespan optimization balances performance và cost. Distributed computing complexity highest trong hybrid scenarios.
Tải xuống file đầy đủ để xem toàn bộ nội dung
Tải đầy đủ (136 trang)Trích đoạn nội dung luận án
Tải xuống để đọc toàn bộ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.
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ
Từ khóa và chủ đề nghiên cứu
Câu hỏi thường gặp
Luận án "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" nghiên cứu về vấn đề gì?
Luận án tiến sĩ 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. Đề xuất ba thuật toán mới cải tiến hiệu suất 4-30% so với phương pháp hiện có.
Luận án "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" được bảo vệ tại trường nào?
Luận án này được bảo vệ tại auburn university. Năm bảo vệ: 2006.
Luận án "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" thuộc chuyên ngành gì?
Luận án "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" thuộc chuyên ngành Computer Science and Software Engineering. Danh mục: Khoa Học Máy Tính.
Luận án "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" có bao nhiêu trang?
Luận án "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" có 136 trang. Bạn có thể xem trước một phần tài liệu ngay trên trang web trước khi tải về.
Cách tải luận án "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" về máy như thế nào?
Để tải luận án về máy, bạn nhấn nút "Tải xuống ngay" trên trang này, sau đó hoàn tất thanh toán phí lưu trữ. File sẽ được tải xuống ngay sau khi thanh toán thành công. Hỗ trợ qua Zalo: 0559 297 239.