Del 60 i serien Wiley Series on Parallel and Distributed Computing

Task Scheduling for Parallel Systems

Inbunden, Engelska, 2007

1 879 kr

Beställningsvara. Skickas inom 5-8 vardagar. Fri frakt för medlemmar vid köp för minst 249 kr.

A new model for task scheduling that dramatically improves the efficiency of parallel systems Task scheduling for parallel systems can become a quagmire of heuristics, models, and methods that have been developed over the past decades. The author of this innovative text cuts through the confusion and complexity by presenting a consistent and comprehensive theoretical framework along with realistic parallel system models. These new models, based on an investigation of the concepts and principles underlying task scheduling, take into account heterogeneity, contention for communication resources, and the involvement of the processor in communications.For readers who may be new to task scheduling, the first chapters are essential. They serve as an excellent introduction to programming parallel systems, and they place task scheduling within the context of the program parallelization process. The author then reviews the basics of graph theory, discussing the major graph models used to represent parallel programs. Next, the author introduces his task scheduling framework. He carefully explains the theoretical background of this framework and provides several examples to enable readers to fully understand how it greatly simplifies and, at the same time, enhances the ability to schedule.The second half of the text examines both basic and advanced scheduling techniques, offering readers a thorough understanding of the principles underlying scheduling algorithms. The final two chapters address communication contention in scheduling and processor involvement in communications.Each chapter features exercises that help readers put their new skills into practice. An extensive bibliography leads to additional information for further research. Finally, the use of figures and examples helps readers better visualize and understand complex concepts and processes.Researchers and students in distributed and parallel computer systems will find that this text dramatically improves their ability to schedule tasks accurately and efficiently.

Produktinformation

Utgivningsdatum2007-05-25
Mått165 x 243 x 21 mm
Vikt562 g
FormatInbunden
SpråkEngelska
SerieWiley Series on Parallel and Distributed Computing
Antal sidor320
FörlagJohn Wiley & Sons Inc
ISBN9780471735762

Tillhör följande kategorier

Elektronik och kommunikationer inom Naturvetenskap och teknik

Preface xiAcknowledgments xii1. Introduction 11.1 Overview 11.2 Organization 52. Parallel Systems and Programming 72.1 Parallel Architectures 72.1.1 Flynn’s Taxonomy 72.1.2 Memory Architectures 92.1.3 Programming Paradigms and Models 112.2 Communication Networks 132.2.1 Static Networks 132.2.2 Dynamic Networks 182.3 Parallelization 222.4 Subtask Decomposition 242.4.1 Concurrency and Granularity 242.4.2 Decomposition Techniques 252.4.3 Computation Type and Program Formulation 272.4.4 Parallelization Techniques 282.4.5 Target Parallel System 282.5 Dependence Analysis 292.5.1 Data Dependence 292.5.2 Data Dependence in Loops 322.5.3 Control Dependence 352.6 Concluding Remarks 362.7 Exercises 373. Graph Representations 403.1 Basic Graph Concepts 403.1.1 Computer Representation of Graphs 433.1.2 Elementary Graph Algorithms 463.2 Graph as a Program Model 493.2.1 Computation and Communication Costs 503.2.2 Comparison Criteria 503.3 Dependence Graph (DG) 513.3.1 Iteration Dependence Graph 533.3.2 Summary 553.4 Flow Graph (FG) 563.4.1 Data-Driven Execution Model 603.4.2 Summary 613.5 Task Graph (DAG) 623.5.1 Graph Transformations and Conversions 643.5.2 Motivations and Limitations 683.5.3 Summary 693.6 Concluding Remarks 693.7 Exercises 704. Task Scheduling 744.1 Fundamentals 744.2 With Communication Costs 764.2.1 Schedule Example 814.2.2 Scheduling Complexity 824.3 Without Communication Costs 864.3.1 Schedule Example 874.3.2 Scheduling Complexity 884.4 Task Graph Properties 924.4.1 Critical Path 934.4.2 Node Levels 954.4.3 Granularity 1014.5 Concluding Remarks 1054.6 Exercises 1055. Fundamental Heuristics 1085.1 List Scheduling 1085.1.1 Start Time Minimization 1115.1.2 With Dynamic Priorities 1145.1.3 Node Priorities 1155.2 Scheduling with Given Processor Allocation 1185.2.1 Phase Two 1195.3 Clustering 1195.3.1 Clustering Algorithms 1215.3.2 Linear Clustering 1245.3.3 Single Edge Clustering 1285.3.4 List Scheduling as Clustering 1355.3.5 Other Algorithms 1385.4 From Clustering to Scheduling 1395.4.1 Assigning Clusters to Processors 1395.4.2 Scheduling on Processors 1415.5 Concluding Remarks 1415.6 Exercises 1426. Advanced Task Scheduling 1456.1 Insertion Technique 1456.1.1 List Scheduling with Node Insertion 1486.2 Node Duplication 1506.2.1 Node Duplication Heuristics 1536.3 Heterogeneous Processors 1546.3.1 Scheduling 1576.4 Complexity Results 1586.4.1 α|β|γ Classification 1586.4.2 Without Communication Costs 1656.4.3 With Communication Costs 1656.4.4 With Node Duplication 1686.4.5 Heterogeneous Processors 1706.5 Genetic Algorithms 1706.5.1 Basics 1716.5.2 Chromosomes 1726.5.3 Reproduction 1776.5.4 Selection, Complexity, and Flexibility 1806.6 Concluding Remarks 1826.7 Exercises 1837. Communication Contention in Scheduling 1877.1 Contention Awareness 1887.1.1 End-Point Contention 1897.1.2 Network Contention 1907.1.3 Integrating End-Point and Network Contention 1927.2 Network Model 1927.2.1 Topology Graph 1927.2.2 Routing 1987.2.3 Scheduling Network Model 2027.3 Edge Scheduling 2037.3.1 Scheduling Edge on Route 2047.3.2 The Edge Scheduling 2087.4 Contention Aware Scheduling 2097.4.1 Basics 2097.4.2 NP-Completeness 2117.5 Heuristics 2167.5.1 List Scheduling 2167.5.2 Priority Schemes—Task Graph Properties 2197.5.3 Clustering 2207.5.4 Experimental Results 2217.6 Concluding Remarks 2237.7 Exercises 2248. Processor Involvement in Communication 2288.1 Processor Involvement—Types and Characteristics 2298.1.1 Involvement Types 2298.1.2 Involvement Characteristics 2328.1.3 Relation to LogP and Its Variants 2368.2 Involvement Scheduling 2388.2.1 Scheduling Edges on the Processors 2408.2.2 Node and Edge Scheduling 2468.2.3 Task Graph 2478.2.4 NP-Completeness 2488.3 Algorithmic Approaches 2508.3.1 Direct Scheduling 2518.3.2 Scheduling with Given Processor Allocation 2548.4 Heuristics 2578.4.1 List Scheduling 2578.4.2 Two-Phase Heuristics 2618.4.3 Experimental Results 2638.5 Concluding Remarks 2648.6 Exercises 265Bibliography 269Author Index 281Subject Index 285