Advanced Computer Architecture and Parallel Processing

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.

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

• 1. Introduction to Advanced Computer Architecture and Parallel Processing 11.1 Four Decades of Computing 21.2 Flynn’s Taxonomy of Computer Architecture 41.3 SIMD Architecture 51.4 MIMD Architecture 61.5 Interconnection Networks 111.6 Chapter Summary 15Problems 16References 172. Multiprocessors Interconnection Networks 192.1 Interconnection Networks Taxonomy 192.2 Bus-Based Dynamic Interconnection Networks 202.3 Switch-Based Interconnection Networks 242.4 Static Interconnection Networks 332.5 Analysis and Performance Metrics 412.6 Chapter Summary 45Problems 46References 483. Performance Analysis of Multiprocessor Architecture 513.1 Computational Models 513.2 An Argument for Parallel Architectures 553.3 Interconnection Networks Performance Issues 583.4 Scalability of Parallel Architectures 633.5 Benchmark Performance 673.6 Chapter Summary 72Problems 73References 744. Shared Memory Architecture 774.1 Classification of Shared Memory Systems 784.2 Bus-Based Symmetric Multiprocessors 804.3 Basic Cache Coherency Methods 814.4 Snooping Protocols 834.5 Directory Based Protocols 894.6 Shared Memory Programming 964.7 Chapter Summary 99Problems 100References 1015. Message Passing Architecture 1035.1 Introduction to Message Passing 1035.2 Routing in Message Passing Networks 1055.3 Switching Mechanisms in Message Passing 1095.4 Message Passing Programming Models 1145.5 Processor Support for Message Passing 1175.6 Example Message Passing Architectures 1185.7 Message Passing Versus Shared Memory Architectures 1225.8 Chapter Summary 123Problems 123References 1246. Abstract Models 1276.1 The PRAM Model and Its Variations 1276.2 Simulating Multiple Accesses on an EREW PRAM 1296.3 Analysis of Parallel Algorithms 1316.4 Computing Sum and All Sums 1336.5 Matrix Multiplication 1366.6 Sorting 1396.7 Message Passing Model 1406.8 Leader Election Problem 1466.9 Leader Election in Synchronous Rings 1476.10 Chapter Summary 154Problems 154References 1557. Network Computing 1577.1 Computer Networks Basics 1587.2 Client/Server Systems 1617.3 Clusters 1667.4 Interconnection Networks 1707.5 Cluster Examples 1757.6 Grid Computing 1777.7 Chapter Summary 178Problems 178References 1808. Parallel Programming in the Parallel Virtual Machine 1818.1 PVM Environment and Application Structure 1818.2 Task Creation 1858.3 Task Groups 1888.4 Communication Among Tasks 1908.5 Task Synchronization 1968.6 Reduction Operations 1988.7 Work Assignment 2008.8 Chapter Summary 201Problems 202References 2039. Message Passing Interface (MPI) 2059.1 Communicators 2059.2 Virtual Topologies 2099.3 Task Communication 2139.4 Synchronization 2179.5 Collective Operations 2209.6 Task Creation 2259.7 One-Sided Communication 2289.8 Chapter Summary 231Problems 231References 23310 Scheduling and Task Allocation 23510.1 The Scheduling Problem 23510.2 Scheduling DAGs without Considering Communication 23810.3 Communication Models 24210.4 Scheduling DAGs with Communication 24410.5 The NP-Completeness of the Scheduling Problem 24810.6 Heuristic Algorithms 25010.7 Task Allocation 25610.8 Scheduling in Heterogeneous Environments 262Problems 263References 264Index 267