Algorithms and parallel computing

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.Content: Chapter 1 Introduction (pages 1–27): Chapter 2 Enhancing Uniprocessor Performance (pages 29–51): Chapter 3 Parallel Computers (pages 53–68): Chapter 4 Shared?Memory Multiprocessors (pages 69–82): Chapter 5 Interconnection Networks (pages 83–103): Chapter 6 Concurrency Platforms (pages 105–130): Chapter 7 Ad Hoc Techniques for Parallel Algorithms (pages 131–142): Chapter 8 Nonserial–Parallel Algorithms (pages 143–157): Chapter 9 z?Transform Analysis (pages 159–165): Chapter 10 Dependence Graph Analysis (pages 167–183): Chapter 11 Computational Geometry Analysis (pages 185–208): Chapter 12 Case Study: One?Dimensional IIR Digital Filters (pages 209–218): Chapter 13 Case Study: Two? and Three?Dimensional Digital Filters (pages 219–226): Chapter 14 Case Study: Multirate Decimators and Interpolators (pages 227–244): Chapter 15 Case Study: Pattern Matching (pages 245–254): Chapter 16 Case Study: Motion Estimation for Video Compression (pages 255–266): Chapter 17 Case Study: Multiplication over GF(2m) (pages 267–277): Chapter 18 Case Study: Polynomial Division over GF(2) (pages 279–291): Chapter 19 The Fast Fourier Transform (pages 293–303): Chapter 20 Solving Systems of Linear Equations (pages 305–321): Chapter 21 Solving Partial Differential Equations Using Finite Difference Method (pages 323–329): Algorithms and Parallel Computing 5 Contents 9 Preface 15 List of Acronyms 21 Chapter 1: Introduction 25 1.1 INTRODUCTION 25 1.2 TOWARD AUTOMATING PARALLEL PROGRAMMING 26 1.3 ALGORITHMS 28 1.4 PARALLEL COMPUTING DESIGN CONSIDERATIONS 36 1.5 PARALLEL ALGORITHMS AND PARALLEL ARCHITECTURES 37 1.6 RELATING PARALLEL ALGORITHM AND PARALLEL ARCHITECTURE 38 1.7 IMPLEMENTATION OF ALGORITHMS: A TWO-SIDED PROBLEM 38 1.8 MEASURING BENEFITS OF PARALLEL COMPUTING 39 1.9 AMDAHL’S LAW FOR MULTIPROCESSOR SYSTEMS 43 1.10 GUSTAFSON–BARSIS’S LAW 45 1.11 APPLICATIONS OF PARALLEL COMPUTING 46 Chapter 2: Enhancing Uniprocessor Performance 53 2.1 INTRODUCTION 53 2.2 INCREASING PROCESSOR CLOCK FREQUENCY 54 2.3 PARALLELIZING ALU STRUCTURE 54 2.4 USING MEMORY HIERARCHY 57 2.5 PIPELINING 63 2.6 VERY LONG INSTRUCTION WORD (VLIW) PROCESSORS 68 2.7 INSTRUCTION-LEVEL PARALLELISM (ILP) AND SUPERSCALAR PROCESSORS 69 2.8 MULTITHREADED PROCESSOR 73 Chapter 3: Parallel Computers 77 3.1 INTRODUCTION 77 3.2 PARALLEL COMPUTING 77 3.3 SHARED-MEMORY MULTIPROCESSORS (UNIFORM MEMORY ACCESS [UMA]) 78 3.4 DISTRIBUTED-MEMORY MULTIPROCESSOR (NONUNIFORM MEMORY ACCESS [NUMA]) 80 3.5 SIMD PROCESSORS 81 3.6 SYSTOLIC PROCESSORS 81 3.7 CLUSTER COMPUTING 84 3.8 GRID (CLOUD) COMPUTING 84 3.9 MULTICORE SYSTEMS 85 3.10 SM 86 3.11 COMMUNICATION BETWEEN PARALLEL PROCESSORS 88 3.12 SUMMARY OF PARALLEL ARCHITECTURES 91 Chapter 4: Shared-Memory Multiprocessors 93 4.1 INTRODUCTION 93 4.2 CACHE COHERENCE AND MEMORY CONSISTENCY 94 4.3 SYNCHRONIZATION AND MUTUAL EXCLUSION 100 Chapter 5: Interconnection Networks 107 5.1 INTRODUCTION 107 5.2 CLASSIFICATION OF INTERCONNECTION NETWORKS BY LOGICAL TOPOLOGIES 108 5.3 INTERCONNECTION NETWORK SWITCH ARCHITECTURE 115 Chapter 6: Concurrency Platforms 129 6.1 INTRODUCTION 129 6.2 CONCURRENCY PLATFORMS 129 6.3 CILK++ 130 6.4 OpenMP 136 6.5 COMPUTE UNIFIED DEVICE ARCHITECTURE (CUDA) 146 Chapter 7: Ad Hoc Techniques for Parallel Algorithms 155 7.1 INTRODUCTION 155 7.2 DEFINING ALGORITHM VARIABLES 157 7.3 INDEPENDENT LOOP SCHEDULING 157 7.4 DEPENDENT LOOPS 158 7.5 LOOP SPREADING FOR SIMPLE DEPENDENT LOOPS 159 7.6 LOOP UNROLLING 159 7.7 PROBLEM PARTITIONING 160 7.8 DIVIDE-AND-CONQUER (RECURSIVE PARTITIONING) STRATEGIES 161 7.9 PIPELINING 163 Chapter 8: Nonserial–Parallel Algorithms 167 8.1 INTRODUCTION 167 8.2 COMPARING DAG AND DCG ALGORITHMS 167 8.3 PARALLELIZING NSPA ALGORITHMS REPRESENTED BY A DAG 169 8.4 FORMAL TECHNIQUE FOR ANALYZING NSPAs 171 8.5 DETECTING CYCLES IN THE ALGORITHM 174 8.6 EXTRACTING SERIAL AND PARALLEL ALGORITHM PERFORMANCE PARAMETERS 175 8.7 USEFUL THEOREMS 177 8.8 PERFORMANCE OF SERIAL AND PARALLEL ALGORITHMS ON PARALLEL COMPUTERS 180 Chapter 9: z-Transform Analysis 183 9.1 INTRODUCTION 183 9.2 DEFINITION OF z-TRANSFORM 183 9.3 THE 1-D FIR DIGITAL FILTER ALGORITHM 184 9.4 SOFTWARE AND HARDWARE IMPLEMENTATIONS OF THE z-TRANSFORM 185 9.5 DESIGN 1: USING HORNER’S RULE FOR BROADCAST INPUT AND PIPELINED OUTPUT 186 9.6 DESIGN 2: PIPELINED INPUT AND BROADCAST OUTPUT 187 9.7 DESIGN 3: PIPELINED INPUT AND OUTPUT 188 Chapter 10: Dependence Graph Analysis 191 10.1 INTRODUCTION 191 10.2 THE 1-D FIR DIGITAL FILTER ALGORITHM 191 10.3 THE DEPENDENCE GRAPH OF AN ALGORITHM 192 10.4 DERIVING THE DEPENDENCE GRAPH FOR AN ALGORITHM 193 10.5 THE SCHEDULING FUNCTION FOR THE 1-D FIR FILTER 195 10.6 NODE PROJECTION OPERATION 201 10.7 NONLINEAR PROJECTION OPERATION 203 10.8 SOFTWARE AND HARDWARE IMPLEMENTATIONS OF THE DAG TECHNIQUE 204 Chapter 11: Computational Geometry Analysis 209 11.1 INTRODUCTION 209 11.2 MATRIX MULTIPLICATION ALGORITHM 209 11.3 THE 3-D DEPENDENCE GRAPH AND COMPUTATION DOMAIN D 210 11.4 THE FACETS AND VERTICES OF D 212 11.5 THE DEPENDENCE MATRICES OF THE ALGORITHM VARIABLES 212 11.6 NULLSPACE OF DEPENDENCE MATRIX: THE BROADCAST SUBDOMAIN B 213 11.7 DESIGN SPACE EXPLORATION: CHOICE OF BROADCASTING VERSUS PIPELINING VARIABLES 216 11.8 DATA SCHEDULING 219 11.9 PROJECTION OPERATION USING THE LINEAR PROJECTION OPERATOR 224 11.10 EFFECT OF PROJECTION OPERATION ON DATA 229 11.11 THE RESULTING MULTITHREADED/MULTIPROCESSOR ARCHITECTURE 230 11.12 SUMMARY OF WORK DONE IN THIS CHAPTER 231 Chapter 12: Case Study: One-Dimensional IIR Digital Filters 233 12.1 INTRODUCTION 233 12.2 THE 1-D IIR DIGITAL FILTER ALGORITHM 233 12.3 THE IIR FILTER DEPENDENCE GRAPH 233 12.4 z-DOMAIN ANALYSIS OF 1-D IIR DIGITAL FILTER ALGORITHM 240 Chapter 13: Case Study: Two- and Three-Dimensional Digital Filters 243 13.1 INTRODUCTION 243 13.2 LINE AND FRAME WRAPAROUND PROBLEMS 243 13.3 2-D RECURSIVE FILTERS 245 13.4 3-D DIGITAL FILTERS 247 Chapter 14: Case Study: Multirate Decimators and Interpolators 251 14.1 INTRODUCTION 251 14.2 DECIMATOR STRUCTURES 251 14.3 DECIMATOR DEPENDENCE GRAPH 252 14.4 DECIMATOR SCHEDULING 254 14.5 DECIMATOR DAG FOR s1 = [1 0] 255 14.6 DECIMATOR DAG FOR s2 = [1 −1] 257 14.7 DECIMATOR DAG FOR s3 = [1 1] 259 14.8 POLYPHASE DECIMATOR IMPLEMENTATIONS 259 14.9 INTERPOLATOR STRUCTURES 260 14.10 INTERPOLATOR DEPENDENCE GRAPH 261 14.11 INTERPOLATOR SCHEDULING 262 14.12 INTERPOLATOR DAG FOR s1 = [1 0] 263 14.13 INTERPOLATOR DAG FOR s2 = [1 −1] 265 14.14 INTERPOLATOR DAG FOR s3 = [1 1] 267 14.15 POLYPHASE INTERPOLATOR IMPLEMENTATIONS 267 Chapter 15: Case Study: Pattern Matching 269 15.1 INTRODUCTION 269 15.2 EXPRESSING THE ALGORITHM AS A REGULAR ITERATIVE ALGORITHM (RIA) 269 15.3 OBTAINING THE ALGORITHM DEPENDENCE GRAPH 270 15.4 DATA SCHEDULING 271 15.5 DAG NODE PROJECTION 272 15.6 DESIGN 1: DESIGN SPACE EXPLORATION WHEN s = [1 1]t 273 15.7 DESIGN 2: DESIGN SPACE EXPLORATION WHEN s = [1 −1]t 276 15.8 DESIGN 3: DESIGN SPACE EXPLORATION WHEN s = [1 0]t 277 Chapter 16: Case Study: Motion Estimation for Video Compression 279 16.1 INTRODUCTION 279 16.2 FBMAS 280 16.3 DATA BUFFERING REQUIREMENTS 281 16.4 FORMULATION OF THE FBMA 282 16.5 HIERARCHICAL FORMULATION OF MOTION ESTIMATION 283 16.6 HARDWARE DESIGN OF THE HIERARCHY BLOCKS 285 Chapter 17: Case Study: Multiplication over GF (2m) 291 17.1 INTRODUCTION 291 17.2 THE MULTIPLICATION ALGORITHM IN GF (2m) 292 17.3 EXPRESSING FIELD MULTIPLICATION AS AN RIA 294 17.4 FIELD MULTIPLICATION DEPENDENCE GRAPH 294 17.5 DATA SCHEDULING 295 17.6 DAG NODE PROJECTION 297 17.7 DESIGN 1: USING d1 = [1 0]t 299 17.8 DESIGN 2: USING d2 = [1 1]t 299 17.9 DESIGN 3: USING d3 = [1 −1]t 301 17.10 APPLICATIONS OF FINITE FIELD MULTIPLIERS 301 Chapter 18: Case Study: Polynomial Division over GF(2) 303 18.1 INTRODUCTION 303 18.2 THE POLYNOMIAL DIVISION ALGORITHM 303 18.3 THE LFSR DEPENDENCE GRAPH 305 18.4 DATA SCHEDULING 306 18.5 DAG NODE PROJECTION 307 18.6 DESIGN 1: DESIGN SPACE EXPLORATION WHEN s1 = [1 −1] 308 18.7 DESIGN 2: DESIGN SPACE EXPLORATION WHEN s2 = [1 0] 310 18.8 DESIGN 3: DESIGN SPACE EXPLORATION WHEN s3 = [1 −0.5] 313 18.9 COMPARING THE THREE DESIGNS 315 Chapter 19: The Fast Fourier Transform 317 19.1 INTRODUCTION 317 19.2 DECIMATION-IN-TIME FFT 319 19.3 PIPELINE RADIX-2 DECIMATION-IN-TIME FFT PROCESSOR 322 19.4 DECIMATION-IN-FREQUENCY FFT 323 19.5 PIPELINE RADIX-2 DECIMATION-IN-FREQUENCY FFT PROCESSOR 327 Chapter 20: Solving Systems of Linear Equations 329 20.1 INTRODUCTION 329 20.2 SPECIAL MATRIX STRUCTURES 329 20.3 FORWARD SUBSTITUTION (DIRECT TECHNIQUE) 333 20.4 BACK SUBSTITUTION 336 20.5 MATRIX TRIANGULARIZATION ALGORITHM 336 20.6 SUCCESSIVE OVER RELAXATION (SOR) (ITERATIVE TECHNIQUE) 341 20.7 PROBLEMS 345 Chapter 21: Solving Partial Differential Equations Using Finite Difference Method 347 21.1 INTRODUCTION 347 21.2 FDM FOR 1-D SYSTEMS 348 References 355 Index 361 V413HAV Content: Frontmatter -- Introduction -- Enhancing Uniprocessor Performance -- Parallel Computers -- Shared-Memory Multiprocessors -- Interconnection Networks -- Concurrency Platforms -- Ad Hoc Techniques for Parallel Algorithms -- Nonserial6Parallel Algorithms -- -Transform Analysis -- Dependence Graph Analysis -- Computational Geometry Analysis -- Case Study: One-Dimensional IIR Digital Filters -- Case Study: Two- and Three-Dimensional Digital Filters -- Case Study: Multirate Decimators and Interpolators -- Case Study: Pattern Matching -- Case Study: Motion Estimation for Video Compression -- Case Study: Multiplication over GF(2) -- Case Study: Polynomial Division over GF(2) -- The Fast Fourier Transform -- Solving Systems of Linear Equations -- Solving Partial Differential Equations Using Finite Difference Method -- References -- Index. Abstract: 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. Read more... "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"--Provided by publisher. "This book provides the techniques to explore the possible ways to program a parallel computer for a given application"--Provided by publisher. "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"-- Résumé de l'éd