Algorithms and Parallel Computing [Hardcover]

There is a software gap between the hardware potential and the performance that can be attained using today's software parallel program development tools. The tools need manual intervention by the programmer to parallelize the code. Programming a parallel computer requires closely studying the target algorithm or application, more so than in the traditional sequential programming we have all learned. The programmer must be aware of the communication and data dependencies of the algorithm or application. This book provides the techniques to explore the possible ways to program a parallel computer for a given application.

Preface xiii

List of Acronyms xix

1 Introduction 1

1.1 Introduction 1

1.2 Toward Automating Parallel Programming 2

1.3 Algorithms 4

1.4 Parallel Computing Design Considerations 12

1.5 Parallel Algorithms and Parallel Architectures 13

1.6 Relating Parallel Algorithm and Parallel Architecture 14

1.7 Implementation of Algorithms: A Two-Sided Problem 14

1.8 Measuring Benefi ts of Parallel Computing 15

1.9 Amdahls Law for Multiprocessor Systems 19

1.10 GustafsonBarsiss Law 21

1.11 Applications of Parallel Computing 22

2 Enhancing Uniprocessor Performance 29

2.1 Introduction 29

2.2 Increasing Processor Clock Frequency 30

2.3 Parallelizing ALU Structure 30

2.4 Using Memory Hierarchy 33

2.5 Pipelining 39

2.6 Very Long Instruction Word (VLIW) Processors 44

2.7 Instruction-Level Parallelism (ILP) and Superscalar Processors 45

2.8 Multithreaded Processor 49

3 Parallel ComputelCí