Assignment Problems in Parallel and Distributed Computing

by Shahid H. Bokhari

Overview

This book has been written for practitioners, researchers and students in the fields of parallel and distributed computing. Its objective is to provide detailed coverage of the applications of graph theoretic techniques to the problems of matching resources and requirements in multiple 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 implementation; background material and fundamental concepts are covered in full. The researcher will find a clear exposition of graph theoretic techniques 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.

Product Details

ISBN-13:	9780898382402
Publisher:	Springer US
Publication date:	09/30/1987
Series:	The Springer International Series in Engineering and Computer Science , #32
Edition description:	1987
Pages:	156
Product dimensions:	6.14(w) x 9.21(h) x 0.24(d)

Table of Contents

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.