Algorithms and Parallel Computing

Informationen zum Autor Fayez Gebali , PhD, has taught at the University of Victoria since 1984 and has served as the Associate Dean of Engineering for undergraduate programs since 2002. He has contributed to dozens of journals and technical reports and has completed four books. Dr. Gebali's primary research interests include VLSI design, processor array design, algorithms for computer arithmetic, and communication system modeling. Klappentext A balanced overview of the techniques used to design and program parallel computers There is a software gap between parallel computers and programmers' abilities to program such computers. Programming a parallel computer requires closely studying the target algorithm or application, more so than in traditional sequential programming. Today's programmer must be aware of the communication and data dependencies of the algorithm or application; yet, programmers do not have the tools to help them implement an algorithm on a parallel computer platform. This book provides the techniques necessary to explore parallelism in algorithms, serial as well as iterative. It shows how to systematically design special-purpose parallel processing structures to implement algorithms. The book begins by explaining how to classify an algorithm, and then identifying which technique would be appropriate to implement the application on a parallel platform. It provides techniques for studying and analyzing several types of algorithms-parallel, serial-parallel, non-serial-parallel, and regular iterative algorithms. New techniques for extracting parallelism and controlling thread workload are shown for the first time, such as z-transform, graphic, algebraic, and nonlinear workload specification for the threads. Also featured in the book: A review of algorithms and how to parallelize each algorithm category Ten case studies, detailed in separate chapters, that address implementing parallel algorithms on multithreaded parallel computers and developing special-purpose parallel machines A chapter dedicated to enhancing single processor performance End-of-chapter problems (solutions and lecture notes are available) Algorithms and Parallel Computing is intended for application developers, researchers, and graduate students and seniors in computer engineering, electrical engineering, and computer science. Software developers and major computer manufacturers will also find the material highly beneficial. Zusammenfassung New techniques (z-transform, graphic, algebraic) for studying and analyzing parallel algorithms and how to use them Case studies throughout th book Problems at the end of each chapter and available solutions manual A companion website to include lecture notes . Inhaltsverzeichnis 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 Amdahl's Law for Multiprocessor Systems 19 1.10 Gustafson-Barsis's 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 Computers 53 3.1 Introduction 53 3.2 Paral...

List of contents

Preface.
 
List of Acronyms.
 
1 Introduction.
 
1.1 Introduction.
 
1.2 Toward Automating Parallel Programming.
 
1.3 Algorithms.
 
1.4 Parallel Computing Design Considerations.
 
1.5 Parallel Algorithms and Parallel Architectures.
 
1.6 Relating Parallel Algorithm and Parallel Architecture.
 
1.7 Implementation of Algorithms: A Two-Sided Problem.
 
1.8 Measuring Benefi ts of Parallel Computing.
 
1.9 Amdahl's Law for Multiprocessor Systems.
 
1.10 Gustafson-Barsis's Law.
 
1.11 Applications of Parallel Computing.
 
2 Enhancing Uniprocessor Performance.
 
2.1 Introduction.
 
2.2 Increasing Processor Clock Frequency.
 
2.3 Parallelizing ALU Structure.
 
2.4 Using Memory Hierarchy.
 
2.5 Pipelining.
 
2.6 Very Long Instruction Word (VLIW) Processors.
 
2.7 Instruction-Level Parallelism (ILP) and Superscalar Processors.
 
2.8 Multithreaded Processor.
 
3 Parallel Computers.
 
3.1 Introduction.
 
3.2 Parallel Computing.
 
3.3 Shared-Memory Multiprocessors (Uniform Memory Access [UMA]).
 
3.4 Distributed-Memory Multiprocessor (Nonuniform Memory Access [NUMA]).
 
3.5 SIMD Processors.
 
3.6 Systolic Processors.
 
3.7 Cluster Computing.
 
3.8 Grid (Cloud) Computing.
 
3.9 Multicore Systems.
 
3.10 SM.
 
3.11 Communication Between Parallel Processors.
 
3.12 Summary of Parallel Architectures.
 
4 Shared-Memory Multiprocessors.
 
4.1 Introduction.
 
4.2 Cache Coherence and Memory Consistency.
 
4.3 Synchronization and Mutual Exclusion.
 
5 Interconnection Networks.
 
5.1 Introduction.
 
5.2 Classification of Interconnection Networks by Logical Topologies.
 
5.3 Interconnection Network Switch Architecture.
 
6 Concurrency Platforms.
 
6.1 Introduction.
 
6.2 Concurrency Platforms.
 
6.3 Cilk++.
 
6.4 OpenMP.
 
6.5 Compute Unifi ed Device Architecture (CUDA).
 
7 Ad Hoc Techniques for Parallel Algorithms.
 
7.1 Introduction.
 
7.2 Defining Algorithm Variables.
 
7.3 Independent Loop Scheduling.
 
7.4 Dependent Loops.
 
7.5 Loop Spreading for Simple Dependent Loops.
 
7.6 Loop Unrolling.
 
7.7 Problem Partitioning.
 
7.8 Divide-and-Conquer (Recursive Partitioning) Strategies.
 
7.9 Pipelining.
 
8 Nonserial-Parallel Algorithms.
 
8.1 Introduction.
 
8.2 Comparing DAG and DCG Algorithms.
 
8.3 Parallelizing NSPA Algorithms Represented by a DAG.
 
8.4 Formal Technique for Analyzing NSPAs.
 
8.5 Detecting Cycles in the Algorithm.
 
8.6 Extracting Serial and Parallel Algorithm Performance Parameters.
 
8.7 Useful Theorems.
 
8.8 Performance of Serial and Parallel Algorithms on Parallel Computers.
 
9 z-Transform Analysis.
 
9.1 Introduction.
 
9.2 Definition of z-Transform.
 
9.3 The 1-D FIR Digital Filter Algorithm.
 
9.4 Software and Hardware Implementations of the z-Transform.
 
9.5 Design 1: Using Horner's Rule for Broadcast Input and Pipelined Output.
 
9.6 Design 2: Pipelined Input and Broadcast Output.
 
9.7 Design 3: Pipelined Input and Output.
 
10 Dependence Graph Analysis.
 
10.1 Introduction.
 
10.2 The 1-D FIR Digital Filter Algorithm.
 
10.3 The Dependence Graph of an Algorithm.
 
10.4 Deriving the Dependence Graph for an Algorithm.
 
10.5 The

Product details

• Authors: Gebali, F Gebali, Fayez Gebali, Gebali Fayez
• Publisher: Wiley, John and Sons Ltd
• Languages: English
• Product format: Hardback
• Released: 18.03.2011
• EAN: 9780470902103
• ISBN: 978-0-470-90210-3
• No. of pages: 364
• Series: Wiley Series on Parallel and Distributed Computing; Wiley Series on Parallel and D; Wiley Series on Parallel and Distributed Computing
• Subjects: Natural sciences, medicine, IT, technology > IT, data processing > Data communication, networks; Informatik, Netzwerke, Networking, Algorithmus, computer science, Kommunikationsnetze, Electrical & Electronics Engineering, Elektrotechnik u. Elektronik, Communication Technology - Networks, Numerische Methoden u. Algorithmen, Numerical Methods & Algorithms, Parallelverarbeitung (EDV)