Oliver Sinnen, PhD, is a senior lecturer in the Department of Electrical and Computer Engineering at the University of Auckland, New Zealand.

• 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

"The theoretical framework presented and the realistic parallel computing issues make reading this book worthwhile." (Computing Reviews.com, October 1, 2007)

Oliver Sinnen, PhD, is a senior lecturer in the Department of Electrical and Computer Engineering at the University of Auckland, New Zealand.

• 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

"The theoretical framework presented and the realistic parallel computing issues make reading this book worthwhile." (Computing Reviews.com, October 1, 2007)

Oliver Sinnen, PhD, is a senior lecturer in the Department of Electrical and Computer Engineering at the University of Auckland, New Zealand.

• 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

"The theoretical framework presented and the realistic parallel computing issues make reading this book worthwhile." (Computing Reviews.com, October 1, 2007)