Assignment Problems in Parallel and Distributed Computing

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.

1. Introduction.- 1.1. The Motivations for Distributed 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.2. Undirected Graphs.- 2.3. Graphs in General.- 2.4. Weighted Graphs.- 2.5. Trees.- 2.6. Multigraphs.- 2.7. Further Reading.- 3. Network Flow Techniques.- 3.1. The Basic Dual-Processor Assignment Problem.- 3.2. Memory Constraints.- 3.3. Dynamic Assignments.- 3.4. Resource Partitioning with Replication.- 3.5. Summary.- 4. The Shortest Tree Algorithm.- 4.1. Introduction.- 4.2. Assigning Trees across Space.- 4.3. Assigning Series-Parallel Graphs.- 4.4. Optimal Assignments across Space and Time.- 4.5. Summary.- 5. Varying Load Conditions.- 5.1. Varying Load on one Processor.- 5.2. Varying Load on Two Processors.- 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.4. Partitioning Multiple Chains in a Host-Satellite System.- 6.5. Global Assignments in Multiple-Satellite System.- 6.6. Partitioning Trees in a Host-Satellite System.- 6.7. Summary.- 7. Mapping for Parallel Processing.- 7.1. The Parallel Processing Environment.- 7.2. The Mapping Problem.- 7.3. Binary Dissections of Non-uniform domains.- 7.4. Related Research.- 7.5. Summary.- 8. Conclusions.- 8.1. Alternative Approaches.- 8.2. Open Problems.- 8.3. Sources of Information.