Assignment Problems in Parallel and Distributed Computing

Name: Assignment Problems in Parallel and Distributed Computing
Rating: 0 (0 reviews)
ISBN: 9780898382402

The Springer International Engineering and Computer Science

By: Shahid H. Bokhari

Be the first to write a review

Hardcover Published: 30th September 1987
ISBN: 9780898382402
Number Of Pages: 156

Hardcover

$213.24

or 4 easy payments of $53.31 with

Learn more

BUY NOW

Add to Wishlist

Ships in 15 business days

Earn 426 Qantas Points
on this Book

Other Available Editions (Hide)

Paperback View Product Published: 24th February 2012

Ships in 15 business days
$213.24

Description
Table of Contents
Product Details

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.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.

ISBN: 9780898382402
ISBN-10: 0898382408
Series: The Springer International Engineering and Computer Science
Audience: General
Format: Hardcover
Language: English
Number Of Pages: 156
Published: 30th September 1987
Publisher: SPRINGER VERLAG GMBH
Country of Publication: US
Dimensions (cm): 24.28 x 16.46 x 1.68
Weight (kg): 0.45