Assignment problems in parallel and distributed computing

by Shahid H. Bokhari

[目次]

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

「Nielsen BookData」より

この本の情報

書名 Assignment problems in parallel and distributed computing
著作者等 Bokhari, Shahid H.
Bokhari S.H.
シリーズ名 The Kluwer international series in engineering and computer science
出版元 Kluwer Academic
刊行年月 c1987
ページ数 xvii, 154 p.
大きさ 24 cm
ISBN 0898382408
NCID BA01275267
※クリックでCiNii Booksを表示
言語 英語
出版国 アメリカ合衆国
この本を: 
このエントリーをはてなブックマークに追加

Yahoo!ブックマークに登録
この記事をクリップ!
Clip to Evernote
このページを印刷

外部サイトで検索

この本と繋がる本を検索

ウィキペディアから連想