Advanced Computer Architecture and Parallel Processing

1. Introduction to Advanced Computer Architecture and Parallel Processing 1

1.1 Four Decades of Computing 2

1.2 Flynn’s 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