Assignment Problems in Parallel and Distributed Computing

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.