Workflow Scheduling on Computing Systems

✍ Scribed by Kenli Li, Xiaoyong Tang, Jing Mei, Longxin Zhang, Wangdong Yang, Keqin Li

• Publisher: CRC Press
• Year: 2022
• Tongue: English
• Leaves: 252
• Category: Library

✦ Synopsis

This book will serve as a guide in understanding workflow scheduling techniques on computing systems such as Cluster, Supercomputers, Grid computing, Cloud computing, Edge computing, Fog computing, and the practical realization of such methods.

It offers a whole new perspective and holistic approach in understanding computing systems’ workflow scheduling. Expressing and exposing approaches for various process-centric cloud-based applications give a full coverage of most systems’ energy consumption, reliability, resource utilization, cost, and application stochastic computation. By combining theory with application and connecting mathematical concepts and models with their resource management targets, this book will be equally accessible to readers with both Computer Science and Engineering backgrounds.

It will be of great interest to students and professionals alike in the field of computing system design, management, and application. This book will also be beneficial to the general audience and technology enthusiasts who want to expand their knowledge on computer structure.

✦ Table of Contents

Cover
Half Title
Title Page
Copyright Page
Contents
List of Figures
List of Tables
Foreword
Author Bios
Preface
CHAPTER 1: Computing Systems
1.1. COMPUTING SYSTEMS RESOURCE MANAGEMENT
1.2. THE WELL KNOWN SYSTEMS
1.2.1. SLURM
1.2.2. PBS
1.2.3. YARN
1.3. PARALLEL APPLICATIONS
1.3.1. Workflow Applications
1.3.2. Classical Tasks DAG Model
1.4. SOME REAL-WORLD WORKFLOW APPLICATIONS
1.4.1. Montage
1.4.2. Broadband
1.4.3. Epigenomics
1.4.4. LIGO Inspiral Analysis
1.5. OUTLINE OF THE BOOK
CHAPTER 2: Classical Workflow Scheduling
2.1. TASK SCHEDULING
2.2. SCHEDULING CHALLENGES
2.2.1. Energy-Efficient Scheduling
2.2.2. Reliability-Aware Scheduling
2.2.3. High Performance Real-Time Scheduling
2.3. SCHEDULING ALGORITHMS CLASSIFICATION
2.3.1. Local versus Global
2.3.2. Static versus Dynamic
2.3.3. Optimal versus Suboptimal
2.3.4. Approximate versus Heuristic
2.3.5. Centralized versus Distributed
2.4. SEVERAL HEURISTIC WORKFLOW SCHEDULING ALGORITHMS
2.4.1. DLS
2.4.2. MCP
2.4.3. HEFT
2.5. SUMMARY
CHAPTER 3: Stochastic Task Scheduling on Grid Computing Systems
3.1. INTRODUCTION
3.2. THE GRID SCHEDULING ARCHITECTURE
3.3. STOCHASTIC SCHEDULING PROBLEM
3.3.1. The Random Variable Approximate Weight
3.3.2. Stochastic Scheduling Attributes
3.4. THE STOCHASTIC SCHEDULING STRATEGY
3.4.1. Stochastic Task Priorities Phase
3.4.2. Machine Selection Phase
3.4.3. SHEFT Scheduling Algorithm Complexity Analysis
3.5. ALGORITHM PERFORMANCE EVALUATION
3.5.1. Experiments Setting and Evaluation Metrics
3.5.2. Randomly Generated Workflow DAG Graphs
3.5.3. The Sensitivity of Machine Number
3.5.4. The Sensitivity of DAG Size
3.6. SUMMARY
CHAPTER 4: Scheduling Stochastic Tasks on Heterogeneous Cluster Systems
4.1. INTRODUCTION
4.2. A STOCHASTIC SCHEDULING MODEL
4.2.1. Stochastic Workflow Applications
4.2.2. Heterogeneous Cluster Systems
4.2.3. The Motivational Example
4.3. THE PRELIMINARY CONCEPTS
4.3.1. Scheduling Attributes
4.3.2. Manipulation of Normal Random Variables
4.4. A STOCHASTIC SCHEDULING ALGORITHM
4.4.1. Stochastic Bottom Level
4.4.2. Stochastic Dynamic Level Scheduling Algorithm
4.4.3. An Illustration Example
4.5. WORKFLOW APPLICATION PERFORMANCE EVALUATION
4.5.1. Special Application DAG
4.5.2. Experimental Results
4.6. SUMMARY
CHAPTER 5: Reliability-Energy-Aware Scheduling algorithm
5.1. INTRODUCTION
5.2. SYSTEM MODELS
5.2.1. Task Scheduling Architecture
5.2.2. Heterogeneous Computing Systems
5.2.3. Parallel Application Workflow DAG
5.2.4. Energy Consumption Model
5.3. SYSTEM RELIABILITY ANALYSIS
5.3.1. Single Processor Failure Rate
5.3.2. Application Reliability Analysis
5.4. THE RELIABILITY-ENERGY AWARE SCHEDULING ALGORITHM
5.4.1. Task Priorities Phase
5.4.2. Task Assignment Phase
5.4.3. Slack Reclamation
5.5. EXPERIMENTAL RESULTS AND DISCUSSION
5.5.1. Simulation Environment
5.5.2. Randomly Generated Application
5.5.3. Various Weight θ of REAS Algorithm
5.5.4. The Real-World Applications Results
5.6. SUMMARY
CHAPTER 6: Energy Consumption and Reliability Bi-objective Workflow Scheduling
6.1. INTRODUCTION
6.2. MODELS AND PRELIMINARIES
6.2.1. Workflow Model
6.2.2. System Model
6.2.3. Energy Model
6.2.4. Reliability Model
6.2.5. Problem Definition
6.3. MULTI-OBJECTIVE OPTIMIZATION AND A MOTIVATIONAL EXAMPLE
6.3.1. Multi-Objective Optimization Problem Overview
6.3.2. A Motivational Example
6.4. ALGORITHMS
6.4.1. Encoding
6.4.2. Initial Population
6.4.3. Fitness Measure
6.4.4. Selection
6.4.5. Two-Point Crossover
6.4.6. Mutation
6.4.7. The Main Algorithm
6.5. PERFORMANCES EVALUATION
6.5.1. Performance Metrics
6.5.2. Experimental Setting
6.5.3. Real World Application Graphs
6.5.3.1. Three Kinds of Classic DAG Graphs
6.5.3.2. Molecular Dynamic Code
6.5.4. Randomly Generated Application Graphs
6.6. SUMMARY
CHAPTER 7: Interconnection Network Energy-Aware Scheduling Algorithm
7.1. INTRODUCTION
7.2. HETEROGENEOUS SYSTEMS
7.2.1. Computing Nodes and Fat-Tree Networks
7.2.2. Scientific Application Workflow
7.2.3. Energy Consumption Model
7.3. INTERCONNECTION ENERGY AWARE SCHEDULING PROBLEM
7.4. NETWORK ENERGY-EFFICIENT WORKFLOW SCHEDULING STRATEGY
7.4.1. Task Level Computing
7.4.2. Subdeadline Initialization
7.4.3. Dynamic Adjustment
7.4.4. Data Communication Optimization Algorithm
7.4.5. The Heuristic Network Energy-Efficient Workflow Scheduling Algorithm
7.5. REAL-WORLLD APPLICATION PERFORMANCE EVALUATION
7.5.1. Experimental Setting
7.5.2. Real-World Scientific Workflow
7.5.3. The First Experimental Results
7.5.4. The Second Experimental Results
7.6. SUMMARY
CHAPTER 8: Resource-Aware Duplication-Minimization Scheduling Algorithm
8.1. INTRODUCTION
8.1.1. Definition of Task Scheduling
8.1.2. Introduction of Duplication-based Algorithms
8.2. MODELS AND PRELIMINARIES
8.2.1. Computing System Model
8.2.2. Application Model
8.2.3. Performance Measures
8.3. RESOURCE-AWARE SCHEDULING ALGORITHM WITH DUPLICATION MINIMIZATION (RADMS)
8.3.1. Task Prioritization Stage
8.3.2. Task Mapping Stage
8.3.3. Redundancy Deletion Stage
8.3.4. A Scheduling Example
8.4. DUPLICATION OPTIMIZING SCHEME
8.4.1. Analysis on Generation of Redundancy
8.4.2. Strategies of Redundancy Exploitation
8.4.2.1. Move Tasks to the LFT
8.4.2.2. Move Tasks to the EST
8.4.2.3. Migrate Tasks among Processors
8.5. EXPERIMENTAL RESULTS AND ANALYSIS
8.5.1. Experimental Metrics
8.5.2. Parameter Settings
8.5.3. Experimental Results and Analysis
8.5.3.1. Effect of Task Number
8.5.3.2. Effect of Processor Number
8.5.3.3. Effect of Parallelism Factor
8.5.3.4. Effect of CCR
8.5.3.5. Makespan Improvement
8.6. SUMMARY
CHAPTER 9: Contention-Aware Reliability Efficient Scheduling
9.1. INTRODUCTION
9.2. MODELS AND PRELIMINARIES
9.2.1. Application Model
9.2.2. Communication Contention Model
9.2.3. Energy Model
9.2.4. Reliability Model
9.3. PRELIMINARIES
9.3.1. Task Priority
9.3.2. Problem Description
9.3.3. Motivational Example
9.4. CONTENTION-AWARE RELIABILITY MANAGEMENT SCHEME
9.5. EXPERIMENTS
9.5.1. Performance Metrics
9.5.1.1. Scheduling Length Ratio (SLR)
9.5.1.2. Energy Consumption Ratio (ECR)
9.5.1.3. POF
9.5.2. Randomly Generated DAG
9.5.3. Effect of Random Applications
9.5.4. Real-World Application DAG
9.5.4.1. LU Decomposition
9.5.4.2. Fast Fourier Transform
9.5.4.3. Molecular Dynamic Code
9.6. SUMMARY
Bibliography