Assignment Problems in Parallel and Distributed Computing

Front Cover
Springer Science & Business Media, Sep 30, 1987 - Computers - 156 pages
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.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

CHAPTER 1 Introduction
1
11 The Motivations for Distributed Processing
2
112 Parallel Processing
4
12 Environments for Distributed Processing
5
13 Distinction between Distributed and Parallel Processing
6
14 The Central Problem Addressed in this book
7
16 Overview
8
CHAPTER 2 GraphTheoretic Concepts
11
Varying Load Conditions
71
51 Varying Load on one Processor
72
512 Critical Load Factors
73
513 Applications
75
52 Varying Load on Two Processors
77
522 The Load Plane
81
523 Finding the Load Plane
84
524 Critical Load Lines
85

21 Directed Graphs
12
212 Paths in Directed Graphs
13
222 Paths in Undirected Graphs
14
23 Graphs in General
15
233 Connected Components of a Graph
16
235 st cuts
17
241 Shortest Paths
20
25 Trees
23
251 Directed Trees
24
26 Multigraphs
25
Network Flow Techniques
27
31 The Basic DualProcessor Assignment Problem
28
311 Stones Solution to the Assignment Problem
29
312 Applications
32
32 Memory Constraints
33
331 Solution to the Dynamic Assignment Problem
36
332 Zero Residence Cost Graphs
37
334 Bounds on the costs of the Dynamic Assignment
39
335 An Alternative Problem Formulation
41
34 Resource Partitioning with Replication
42
35 Summary
45
Shortest Path Techniques
47
41 Introduction
48
42 Assigning Trees across Space
49
422 The Assignment Graph
51
423 The Shortest Tree Algorithm
54
43 Assigning SeriesParallel Graphs
57
431 Definitions
58
432 The Assignment Graph
61
433 Finding the Optimal Assignment
64
44 Optimal Assignments across Space and Time
66
442 Formulation of the Problem
67
443 Solution
69
53 Varying Communication Costs
88
54 Summary
92
The SumBottleneck Path Algorithm
95
61 Motivations
96
63 Partitioning Chains over Chains
98
631 Signal Processing
99
632 Image Analysis
100
633 Partial Differential Equations
101
635 Construction of Assignment Graph
102
636 Finding the Optimal Assignment
104
641 Construction of the Assignment Graph
106
642 Solution
107
65 Global Assignments in MultipleSatellite System
108
651 Transformation into Chains
110
652 Construction of the Assignment Graph
111
66 Partitioning Trees in a HostSatellite System
113
67 Summary
116
Mapping for Parallel Processing
117
71 The Parallel Processing Environment
118
72 The Mapping Problem
122
722 Applications
123
723 Relation to Graph Isomorphism
124
724 A Heuristic algorithm
126
73 Binary Dissections of Nonuniform domains
127
732 Natural mappings
130
742 Other Interconnection Structures
132
75 Summary
134
Conclusions
135
81 Alternative Approaches
136
83 Sources of Information
137
BIBLIOGRAPHY
139
INDEX
149
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information