1. Introduction to Advanced Computer Architecture and Parallel Processing 1
1.1 Four Decades of Computing 2
1.2 Flynns Taxonomy of Computer Architecture 4
1.3 SIMD Architecture 5
1.4 MIMD Architecture 6
1.5 Interconnection Networks 11
1.6 Chapter Summary 15
Problems 16
References 17
2. Multiprocessors Interconnection Networks 19
2.1 Interconnection Networks Taxonomy 19
2.2 Bus-Based Dynamic Interconnection Networks 20
2.3 Switch-Based Interconnection Networks 24
2.4 Static Interconnection Networks 33
2.5 Analysis and Performance Metrics 41
2.6 Chapter Summary 45
Problems 46
References 48
3. Performance Analysis of Multiprocessor Architecture 51
3.1 Computational Models 51
3.2 An Argument for Parallel Architectures 55
3.3 Interconnection Networks Performance Issues 58
3.4 Scalability of Parallel Architectures 63
3.5 Benchmark Performance 67
3.6 Chapter Summary 72
Problems 73
References 74
4. Shared Memory Architecture 77
4.1 Classification of Shared Memory Systems 78
4.2 Bus-Based Symmetric Multiprocessors 80
4.3 Basic Cache Coherency Methods 81
4.4 Snooping Protocols 83
4.5 Directory Based Protocols 89
4.6 Shared Memory Programming 96
4.7 Chapter Summary 99
Problems 100
References 101
5. Message Passing Architecture 103
5.1 Introduction to Message Passing 103
5.2 Routing in Message Passing Networks 105
5.3 Switching Mechanisms in Message Passing 109
5.4 Message Passing Programming Models 114
5.5 Processor Support for Message Passing 117
5.6 Example Message Passing Architectures 118
5.7 Message Passing Versus Shared Memory Architectures 122
5.8 Chapter Summary 123
Problems 123
References 124
6. Abstract Models 127
6.1 The PRAM Model and Its Variations 127
6.2 Simulating Multiple Accesses on an EREW PRAM 129
6.3 Analysis of Parallel Algorithms 131
6.4 Computing Sum and All Sums 133
6.5 Matrix Multiplication 136
6.6 Sorting 139
6.7 Message Passing Model 140
6.8 Leader Election Problem 146
6.9 Leader Election in Synchronous Rings 147
6.10 Chapter Summary 154
Problems 154
References 155
7. Network Computing 157
7.1 Computer Networks Basics 158
7.2 Client/Server Systems 161
7.3 Clusters 166
7.4 Interconnection Networks 170
7.5 Cluster Examples 175
7.6 Grid Computing 177
7.7 Chapter Summary 178
Problems 178
References 180
8. Parallel Programming in the Parallel Virtual Machine 181
8.1 PVM Environment and Application Structure 181
8.2 Task Creation 185
8.3 Task Groups 188
8.4 Communication Among Tasks 190
8.5 Task Synchronization 196
8.6 Reduction Operations 198
8.7 Work Assignment 200
8.8 Chapter Summary 201
Problems 202
References 203
9. Message Passing Interface (MPI) 205
9.1 Communicators 205
9.2 Virtual Topologies 209
9.3 Task Communication 213
9.4 Synchronization 217
9.5 Collective Operations 220
9.6 Task Creation 225
9.7 One-Sided Communication 228
9.8 Chapter Summary 231
Problems 231
References 233
10 Scheduling and Task Allocation 235
10.1 The Scheduling Problem 235
10.2 Scheduling DAGs without Considering Communication 238
10.3 Communication Models 242
10.4 Scheduling DAGs with Communication 244
10.5 The NP-Completeness of the Scheduling Problem 248
10.6 Heuristic Algorithms 250
10.7 Task Allocation 256
10.8 Scheduling in Heterogeneous Environments 262
Problems 263
References 264
Index 267
