This book has been written for practitioners, researchers and stu­ dents in the fields of parallel and distributed computing. Its objective is to provide detailed coverage of the applications of graph theoretic tech­ niques to the problems of matching resources and requirements in multi­ ple computer systems. There has been considerable research in this area over the last decade and intense work continues even as this is being written. For the practitioner, this book serves as a rich source of solution techniques for problems that are routinely encountered in the real world. Algorithms are presented in sufficient detail to permit easy implementa­ tion; background material and fundamental concepts are covered in full. The researcher will find a clear exposition of graph theoretic tech­ niques applied to parallel and distributed computing. Research results are covered and many hitherto unpublished spanning the last decade results by the author are included. There are many unsolved problems in this field-it is hoped that this book will stimulate further research.

Inhalt

1. Introduction.- 1.1. The Motivations for Distributed Processing.- 1.1.1. Distributed Processing of Serial Programs.- 1.1.2. Parallel Processing.- 1.2. Environments for Distributed Processing.- 1.3. Distinction between Distributed and Parallel Processing.- 1.4. The Central Problem Addressed in this book.- 1.5. Graph-Theoretic Solution Techniques.- 1.6. Overview.- 2. Graph Theoretic Concepts.- 2.1. Directed Graphs.- 2.1.1. Basic Definitions.- 2.1.2. Paths in Directed Graphs.- 2.2. Undirected Graphs.- 2.2.1. Basic Definitions.- 2.2.2. Paths in Undirected Graphs.- 2.3. Graphs in General.- 2.3.1. Subgraphs.- 2.3.2. The Underlying Graph of a Directed Graph.- 2.3.3. Connected Components of a Graph.- 2.3.4. Cutsets.- 2.3.5. s-t cuts.- 2.4. Weighted Graphs.- 2.4.1. Shortest Paths.- 2.4.2. Mincuts.- 2.5. Trees.- 2.5.1. Directed Trees.- 2.5.2. Binary Trees.- 2.6. Multigraphs.- 2.7. Further Reading.- 3. Network Flow Techniques.- 3.1. The Basic Dual-Processor Assignment Problem.- 3.1.1. Stone's Solution to the Assignment Problem.- 3.1.2. Applications.- 3.2. Memory Constraints.- 3.3. Dynamic Assignments.- 3.3.1. Solution to the Dynamic Assignment Problem.- 3.3.2. Zero Residence Cost Graphs.- 3.3.3. Relationship between Dynamic and Static Graphs.- 3.3.4. Bounds on the costs of the Dynamic Assignment.- 3.3.5. An Alternative Problem Formulation.- 3.4. Resource Partitioning with Replication.- 3.5. Summary.- 4. The Shortest Tree Algorithm.- 4.1. Introduction.- 4.2. Assigning Trees across Space.- 4.2.1. Formulation of the Problem.- 4.2.2. The Assignment Graph.- 4.2.3. The Shortest Tree Algorithm.- 4.3. Assigning Series-Parallel Graphs.- 4.3.1. Definitions.- 4.3.2. The Assignment Graph.- 4.3.3. Finding the Optimal Assignment.- 4.4. Optimal Assignments across Space and Time.- 4.4.1. Motivations.- 4.4.2. Formulation of the Problem.- 4.4.3. Solution.- 4.5. Summary.- 5. Varying Load Conditions.- 5.1. Varying Load on one Processor.- 5.1.1. Formulation.- 5.1.2. Critical Load Factors.- 5.1.3. Applications.- 5.2. Varying Load on Two Processors.- 5.2.1. Formulation.- 5.2.2. The Load Plane.- 5.2.3. Finding the Load Plane.- 5.2.4. Critical Load Lines.- 5.3. Varying Communication Costs.- 5.4. Summary.- 6. Sum-Bottleneck Algorithm.- 6.1. Motivations.- 6.2. Definitions.- 6.3. Partitioning Chains over Chains.- 6.3.1. Signal Processing.- 6.3.2. Image Analysis.- 6.3.3. Partial Differential Equations.- 6.3.4. Execution and Communication Costs.- 6.3.5. Construction of Assignment Graph.- 6.3.6. Finding the Optimal Assignment.- 6.4. Partitioning Multiple Chains in a Host-Satellite System.- 6.4.1. Construction of the Assignment Graph.- 6.4.2. Solution.- 6.5. Global Assignments in Multiple-Satellite System.- 6.5.1. Transformation into Chains.- 6.5.2. Construction of the Assignment Graph.- 6.6. Partitioning Trees in a Host-Satellite System.- 6.6.1. Construction of the Assignment Graph.- 6.7. Summary.- 7. Mapping for Parallel Processing.- 7.1. The Parallel Processing Environment.- 7.2. The Mapping Problem.- 7.2.1. Definitions.- 7.2.2. Applications.- 7.2.3. Relation to Graph Isomorphism.- 7.2.4. A Heuristic algorithm.- 7.3. Binary Dissections of Non-uniform domains.- 7.3.1. The Binary Dissection Strategy.- 7.3.2. Natural mappings.- 7.4. Related Research.- 7.4.1. Extensions of the Mapping Problem.- 7.4.2. Other Interconnection Structures.- 7.5. Summary.- 8. Conclusions.- 8.1. Alternative Approaches.- 8.2. Open Problems.- 8.3. Sources of Information.