## Assignment Problems in Parallel and Distributed ComputingThis 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 |

149 | |

### Other editions - View all

Assignment Problems in Parallel and Distributed Computing Shahid H. Bokhari No preview available - 2012 |

Assignment Problems in Parallel and Distributed Computing Shahid H Bokhari No preview available - 1987 |

### Common terms and phrases

allocation graph applications assigned to processor assignment of modules assignment problem assignment tree binary dissection cessor chain limb Chapter communication costs communication link complete binary tree convex polygonal cost edges cost of executing critical load factors critical load line cutset described directed graph distributed computing distributed processing distributed program dynamic assignment graph edge joining executing module execution costs find the optimal floating point unit Fortran graph of Figure graph theory host hypercube interconnection structure interprocessor communication invocation tree isomorphism layer layered graph load plane load point loading chain machine mapping problem ment minimize minimum weight modular program network flow number of edges number of nodes optimal assignment optimal SB path Parallel Processing partitioning phase pipelined problem graph program graph regions relocation cost s-t cut satellite Section serial program series-parallel graph shortest path shown in Figure single-host solution sors subgraph task techniques terminal nodes tion undirected weighted graph