book

GPU Computing Gems Jade Edition

Name: GPU Computing Gems Jade Edition
Author: Wen-mei W. Hwu
ISBN: 9780123859648

by Wen-mei W. Hwu

November 2011

Intermediate to advanced

560 pages

17h 46m

English

Morgan Kaufmann

Read now

Unlock full access

Cover image
Title page
Table of Contents
Front Matter
Copyright
Editors, Reviewers, and Authors
Editor-In-ChiefManaging EditorNVIDIA EditorArea EditorsReviewersAuthors
Introduction
State of GPU Computing
Section 1: Parallel Algorithms and Data Structures
Introduction
In this Section
Chapter 1. Large-Scale GPU Search
1.1 Introduction1.2 Memory Performance1.3 Searching Large Data Sets1.4 Experimental Evaluation1.5 ConclusionReferences

Chapter 2. Edge v. Node Parallelism for Graph Centrality Metrics
2.1 Introduction2.2 Background2.3 Node v. Edge Parallelism2.4 Data Structure2.5 Implementation2.6 Analysis2.7 Results2.8 ConclusionsReferences
Chapter 3. Optimizing Parallel Prefix Operations for the Fermi Architecture
3.1 Introduction to Parallel Prefix Operations3.2 Efficient Binary Prefix Operations on Fermi3.3 ConclusionReferences
Chapter 4. Building an Efficient Hash Table on the GPU
4.1 Introduction4.2 Overview4.3 Building and Querying a Basic Hash Table4.4 Specializing the Hash Table4.5 Analysis4.6 ConclusionAcknowledgmentsReferences
Chapter 5. Efficient CUDA Algorithms for the Maximum Network Flow Problem
5.1 Introduction, Problem Statement, and Context5.2 Core Method5.3 Algorithms, Implementations, and Evaluations5.4 Final Evaluation5.5 Future DirectionsReferences
Chapter 6. Optimizing Memory Access Patterns for Cellular Automata on GPUs
6.1 Introduction, Problem Statement, and Context6.2 Core Methods6.3 Algorithms, Implementations, and Evaluations6.4 Final Results6.5 Future DirectionsReferences
Chapter 7. Fast Minimum Spanning Tree Computation
7.1 Introduction, Problem Statement, and Context7.2 The MST Algorithm: Overview7.3 CUDA Implementation of MST7.4 Evaluation7.5 ConclusionsReferences
Chapter 8. Comparison-Based In-Place Sorting with CUDA
8.1 Introduction8.2 Bitonic Sort8.3 Implementation8.4 Evaluation8.5 ConclusionReferences
Section 2: Numerical Algorithms
Introduction
State of GPU-Based Numerical AlgorithmsIn this Section
Chapter 9. Interval Arithmetic in CUDA
9.1 Interval Arithmetic9.2 Importance of Rounding Modes9.3 Interval Operators in CUDA9.4 Some Evaluations: Synthetic Benchmark9.5 Application-Level Benchmark9.6 ConclusionReferences
Chapter 10. Approximating the erfinv Function
10.1 Introduction10.2 New erfinv Approximations10.3 Performance and Accuracy10.4 ConclusionsReferences
Chapter 11. A Hybrid Method for Solving Tridiagonal Systems on the GPU
11.1 Introduction11.3 Algorithms11.4 Implementation11.5 Results and Evaluation11.6 Future DirectionsSource codeReferences
Chapter 12. Accelerating CULA Linear Algebra Routines with Hybrid GPU and Multicore Computing
12.1 Introduction, Problem Statement, and Context12.2 Core Methods12.3 Algorithms, Implementations, and Evaluations12.4 Final Evaluation and Validation]{Final Evaluation and Validation of Results, Total Benefits, and Limitations12.5 Future DirectionsReferences
Chapter 13. GPU Accelerated Derivative-Free Mesh Optimization
13.1 Introduction, Problem Statement, and Context13.2 Core Method13.3 Algorithms, Implementations, and Evaluations13.4 Final Evaluation13.5 Future DirectionReferences
Section 3: Engineering Simulation
Introduction
State of GPU Computing in Engineering SimulationsIn this Section
Chapter 14. Large-Scale Gas Turbine Simulations on GPU Clusters
14.1 Introduction, Problem Statement, and Context14.2 Core Method14.3 Algorithms, Implementations, and Evaluations14.4 Final Evaluation14.5 Test Case and Parallel Performance14.6 Future DirectionsReferences
Chapter 15. GPU Acceleration of Rarefied Gas Dynamic Simulations
15.1 Introduction, Problem Statement, and Context15.2 Core Methods15.3 Algorithms, Implementations, and Evaluations15.4 Final Evaluation15.5 Future DirectionsReferences
Chapter 16. Application of Assembly of Finite Element Methods on Graphics Processors for Real-Time Elastodynamics
16.1 Introduction, Problem Statement, and Context16.2 Core Method16.3 Algorithms, Implementations, and Evaluations16.4 Evaluation and Validation of Results, Total Benefits, Limitations16.5 Future DirectionsAcknowledgmentsReferences
Chapter 17. CUDA Implementation of Vertex-Centered, Finite Volume CFD Methods on Unstructured Grids with Flow Control Applications
17.1 Introduction, Problem Statement, and Context17.2 Core (CFD and Optimization) Methods17.3 Implementations and Evaluation17.4 Applications to Flow Control — OptimizationReferences
Chapter 18. Solving Wave Equations on Unstructured Geometries
18.1 Introduction, Problem Statement, and Context18.2 Core Method18.3 Algorithms, Implementations, and Evaluations18.4 Final Evaluation18.5 Future DirectionsAcknowledgmentsReferences
Chapter 19. Fast Electromagnetic Integral Equation Solvers on Graphics Processing Units
19.1 Problem Statement and Background19.2 Algorithms Introduction19.3 Algorithm Description19.4 GPU Implementations19.5 Results19.6 Integrating the GPU NGIM Algorithms with Iterative IE Solvers19.7 Future directionsReferences
Section 4: Interactive Physics and AI for Games and Engineering Simulation
Introduction
State of GPU Computing in Interactive Physics and AIIn this Section
Chapter 20. Solving Large Multibody Dynamics Problems on the GPU
20.1 Introduction, Problem Statement, and Context20.2 Core Method20.3 The Time-Stepping Scheme20.4 Algorithms, Implementations, and Evaluations20.5 Final Evaluation20.6 Future DirectionsAcknowledgmentsReferences
Chapter 21. Implicit FEM Solver on GPU for Interactive Deformation Simulation
21.1 Problem Statement and Context21.2 Core Method21.3 Algorithms and Implementations21.4 Results and Evaluation21.5 Future DirectionsAcknowledgementsReferences
Chapter 22. Real-Time Adaptive GPU Multiagent Path Planning
22.1 Introduction22.2 Core Method22.3 Implementation22.4 ResultsReferences
Section 5: Computational Finance
Introduction
State of GPU Computing in Computational FinanceIn this Section
Chapter 23. Pricing Financial Derivatives with High Performance Finite Difference Solvers on GPUs
23.1 Introduction, Problem Statement, and Context23.2 Core Method23.3 Algorithms, Implementations, and Evaluations23.4 Final Evaluation23.5 Future DirectionsReferences
Chapter 24. Large-Scale Credit Risk Loss Simulation
24.1 Introduction, Problem Statement, and Context24.2 Core Methods24.3 Algorithms, Implementations, Evaluations24.4 Results and Conclusions24.5 Future DevelopmentsAcknowledgementsReferences
Chapter 25. Monte Carlo–Based Financial Market Value-at-Risk Estimation on GPUs
25.1 Introduction, Problem Statement, and Context25.2 Core Methods25.3 Algorithms, Implementations, and Evaluations25.4 Final Results25.5 ConclusionReferences
Section 6: Programming Tools and Techniques
Introduction
Programming Tools and Techniques for GPU ComputingIn this Section
Chapter 26. Thrust: A Productivity-Oriented Library for CUDA
26.1 Motivation26.2 Diving In26.3 Generic Programming26.4 Benefits of Abstraction26.5 Best PracticesReferences
Chapter 27. GPU Scripting and Code Generation with PyCUDA
27.1 Introduction, Problem Statement, and Context27.2 Core Method27.3 Algorithms, Implementations, and Evaluations27.4 Evaluation27.5 Availability27.6 Future DirectionsAcknowledgmentReferences
Chapter 28. Jacket: GPU Powered MATLAB Acceleration
28.1 Introduction28.2 Jacket28.3 Benchmarking Procedures28.4 Experimental Results28.5 Future DirectionsReferences
Chapter 29. Accelerating Development and Execution Speed with Just-in-Time GPU Code Generation
29.1 Introduction, Problem Statement, and Context29.2 Core Methods29.3 Algorithms, Implementations, and Evaluations29.4 Final Evaluation29.5 Future DirectionsReferences
Chapter 30. GPU Application Development, Debugging, and Performance Tuning with GPU Ocelot
30.1 Introduction30.2 Core Technology30.3 Algorithm, Implementation, and Benefits30.4 Future DirectionsAcknowledgementsReferences
Chapter 31. Abstraction for AoS and SoA Layout in C++
31.1 Introduction, Problem Statement, and Context31.2 Core Method31.3 Implementation31.4 ASA in Practice31.5 Final EvaluationAcknowledgmentsReferences
Chapter 32. Processing Device Arrays with C++ Metaprogramming
32.1 Introduction, Problem Statement, and Context32.2 Core Method32.3 Implementation32.4 Evaluation32.5 Future DirectionsReferences
Chapter 33. GPU Metaprogramming: A Case Study in Biologically Inspired Machine Vision
33.1 Introduction, Problem Statement, and Context33.2 Core Method33.3 Algorithms, Implementations, and Evaluations33.4 Final Evaluation33.5 Future DirectionsReferences
Chapter 34. A Hybridization Methodology for High-Performance Linear Algebra Software for GPUs
34.1 Introduction, Problem Statement, and Context34.2 Core Method34.3 Algorithms, Implementations, and Evaluations34.4 Final Evaluation34.5 Future DirectionsReferences
Chapter 35. Dynamic Load Balancing Using Work-Stealing
35.1 Introduction35.2 Core Method35.3 Algorithms and Implementations35.4 Case Studies and Evaluation35.5 Future DirectionsAcknowledgmentsReferences
Chapter 36. Applying Software-Managed Caching and CPU/GPU Task Scheduling for Accelerating Dynamic Workloads
36.1 Introduction, Problem Statement, and Context36.2 Core Method36.3 Algorithms, Implementations, and Evaluations36.4 Final EvaluationReferences
Index

Content preview from GPU Computing Gems Jade Edition

Chapter 7

Fast Minimum Spanning Tree Computation

Pawan Harish, P.J. Narayanan, Vibhav Vineet and Suryakant Patidar

In this chapter we present a GPU implementation of the minimum spanning tree (MST) algorithm for undirected graphs. Our application follows Boruvka’s approach to MST computation in a recursive manner and lays irregular data-dependent steps in terms of primitive operations using parallel scan, segmented scan, and split to achieve the reported high performance. The adaptation also provides an outlook on exploiting data-parallel primitives for nontrivial data-dependent algorithms.

7.1 Introduction, Problem Statement, and Context

Minimum spanning tree (MST) algorithms are useful as they find many tasks such as finding a minimum connected ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.

Julian F.

Head of Cybersecurity

I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.

Addison B.

Field Engineer

I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.

Amir M.

Data Platform Tech Lead

I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.

Mark W.

Embedded Software Engineer

Publisher Resources

ISBN: 9780123859631

Cloud Computing

Data Engineering

Data Science

AI & ML

Programming Languages

Software Architecture

IT/Ops

Security

Design

Business

Soft Skills

GPU Computing Gems Jade Edition

by Wen-mei W. Hwu

7.1 Introduction, Problem Statement, and Context

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.