Advanced Computer Architecture and Parallel Processing

ISBN-13: 9780471467403 / Angielski / Twarda / 2005 / 288 str.

Hesham El-Rewini

Opis

Computer architecture deals with the physical configuration, logical structure, formats, protocols, and operational sequences for processing data, controlling the configuration, and controlling the operations over a computer.

Recenzje

"This outstanding treatise...allows students and professionals to become familiar with the inner workings of an inherently complex architecture." ( CHOICE, July 2005)

Spis treści

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

O autorze

HESHAM EL–REWINI, PHD, PE, is a full professor and chairman of the Department of Computer Sciences and Engineering at Southern Methodist University (SMU). He has co–authored several books, published numerous research papers in journals and conference proceedings, and chaired many international conferences.

MOSTAFA ABD–EL–BARR, PHD, PEnG, is a professor and chairman of the Department of Information Science at Kuwait University. He has co–authored two other books, published more than 120 research papers in journals and conference proceedings, and served as chair for a number of international conferences and symposia.

Blurb

An Outstanding Resource for Mastering Computer Architecture and Parallel Processing

This text enables students and practitioners to quickly master the complexities of advanced computer architecture and parallel processing. The authors have drawn from their own experience to present outstanding coverage of the complexities of advanced computer architecture and parallel processing. Using real–world examples and case studies, students and practitioners will understand the interaction between the hardware and software parts of the system. Focussing on practical solutions from architectural to software issues the book discusses key topics including:

• Multiprocessors interconnection networks
• Performance analysis of multiprocessor architecture
• Shared memory architecture
• Message passing architecture
• Abstract models
• Network computing
• Parallel programming in PVM
• Message passing interface (MPI)
• Scheduling and task allocation

The logical organization of the text is designed to help readers build on their knowledge as they progress from one chapter to the next: from problem sets based on actual issues in the workplace that test readers′ knowledge, to end–of–chapter references directing readers to additional sources for in–depth research, and chapter summaries offering a concise overview of the key points.

With its comprehensive coverage, Advanced Computer Architecture and Parallel Processing simplifies course material development for instructors and helps readers learn faster, thanks to its logical organization, clear style, and practical examples. It is an excellent learning aid for both graduate and undergraduate students in electrical engineering, computer engineering, and computer science. Moreover, engineers and programmers will find it to be an outstanding on–the–job reference.