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.