GPU Computing Gems: Emerald Edition

Front Cover......Page 1
GPU Computing Gems......Page 4
Copyright......Page 5
Table of Contents......Page 6
Editors, Reviewers, and Authors......Page 12
Introduction......Page 20
Section 1: Scientific Simulation......Page 22
1.1.
Introduction, Problem Statement, and Context......Page 26
1.2.
Core Method......Page 27
1.3.
Algorithms, Implementations, and Evaluations......Page 29
1.4.
Final Evaluation......Page 37
References......Page 39
2.1.
Introduction, Problem Statement, and Context......Page 40
2.3.
Gaussian Shape Overlay: Parallelization and Arithmetic Optimization......Page 43
2.4.
LINGO: Algorithmic Transformation and Memory Optimization......Page 48
2.5.
Final Evaluation......Page 51
Acknowledgments......Page 54
References......Page 55
3.1.
Introduction......Page 56
3.2.
Core Method......Page 57
3.3.
Implementation......Page 58
3.4.
Performance Improvement......Page 60
3.5.
Future Work......Page 62
References......Page 63
4.1.
Introduction, Problem Statement, and Context......Page 64
4.3.
Algorithms, Implementations, and Evaluations......Page 66
4.4.
Final Evaluation......Page 75
References......Page 79
5.1.
Problem Statement......Page 80
5.2.
Core Technology and Algorithm......Page 82
5.3.
The Key Insight on the Implementation—the Choice of Building Blocks......Page 86
5.4.
Final Evaluation and Benefits......Page 90
Acknowledgments......Page 93
References......Page 94
6.1.
Introduction, Problem Statement, and Context......Page 96
6.2.
Core Methods......Page 97
6.3.
Algorithms and Implementations......Page 99
6.4.
Evaluation and Validation of Results, Total Benefits, and Limitations......Page 109
References......Page 113
7.1.
Background and Problem Statement......Page 114
7.2.
Flux Calculation and Aggregation......Page 116
7.3.
The GRASSY Platform......Page 118
7.4.
Initial Testing......Page 121
Acknowledgments......Page 122
References......Page 123
8.1.
Introduction......Page 124
8.2.
The Post-Newtonian Approximation......Page 125
8.3.
Numerical Algorithm......Page 126
8.4.
GPU Implementation......Page 127
8.6.
GPU Supercomputing Clusters......Page 128
8.8.
Conclusion......Page 130
References......Page 131
9.1.
Introduction......Page 134
9.2.
Fast N-Body Simulation......Page 135
9.3.
CUDA Implementation of the Fast N-Body Algorithms......Page 137
9.4.
Improvements of Performance......Page 141
9.5.
Detailed Description of the GPU Kernels......Page 143
9.6.
Overview of Advanced Techniques......Page 150
References......Page 152
10.1.
Introduction, Problem Statement, and Context......Page 154
10.2.
Core Method......Page 156
10.3.
Algorithms, Implementations, and Evaluations......Page 159
10.4.
Final Evaluation and Validation of Results, Total Benefits, and Limitations......Page 165
10.5.
Conclusions and Future Directions......Page 168
References......Page 172
Section 2: Life Sciences......Page 174
11.1.
Introduction, Problem Statement, and Context......Page 176
11.3.
CUDA Implementation of the SW Algorithm for Identification of Homologous Proteins......Page 177
11.4.
Discussion......Page 190
References......Page 191
12.1.
Introduction, Problem Statement, and Context......Page 194
12.2.
Core Methods......Page 195
12.3.
Algorithms, Implementations, and Evaluations......Page 197
12.5.
Future Directions......Page 204
References......Page 205
13.1.
Introduction, Problem Statement, and Context......Page 206
13.2.
Core Method......Page 207
13.3.
Algorithms, Implementations, and Evaluations......Page 208
13.4.
Final Evaluation......Page 214
Appendix......Page 217
References......Page 219
14.1.
Problem Statement......Page 220
14.2.
Core Method......Page 221
14.3.
Algorithms, Implementations, and Evaluations......Page 222
14.4.
Final Evaluation......Page 228
References......Page 230
15.1.
Introduction......Page 232
15.2.
Core Methodology......Page 233
15.3.
GPU Parallelization: Algorithms and Implementations......Page 235
15.4.
Experimental Results......Page 243
15.5.
Discussion......Page 247
References......Page 248
Section 3: Statistical Modeling......Page 250
16.1.
Introduction......Page 252
16.2. L'Ecuyer's Multiple Recursive Generator MRG32k3a......Page 253
16.3.
Sobol Generator......Page 256
16.4.
Mersenne Twister MT19937......Page 258
16.5.
Performance Benchmarks......Page 263
Acknowledgments......Page 265
References......Page 266
17.1.
Physics of Photon Transport......Page 268
17.2.
Photon Transport on the GPU......Page 270
17.3.
The Complete System......Page 277
17.4.
Results and Evaluation......Page 279
17.5.
Future Directions......Page 280
References......Page 282
18.1.
Problem Statement and Mathematical Background......Page 284
18.3.
Implementation......Page 287
18.4.
Final Evaluation......Page 291
References......Page 293
Section 4: Emerging Data-Intensive Applications......Page 296
19.1.
Introduction......Page 298
19.2.
Core Technology......Page 299
19.3.
GPU Algorithm and Implementation......Page 301
19.4.
Improvements of Performance......Page 308
19.5.
Conclusions and Future Work......Page 311
References......Page 312
20.1.
Introduction, Problem Statement, and Context......Page 314
20.2.
Core Method......Page 315
20.3.
Algorithms, Implementations, and Evaluations......Page 317
20.4.
Final Evaluation......Page 327
References......Page 331
21.1.
Introduction, Problem Statement, and Context......Page 334
21.2.
Final Evaluation and Validation of Results......Page 341
21.3.
Conclusions, Benefits and Limitations, and Future Work......Page 344
References......Page 345
22.1.
Introduction, Problem Statement, and Context......Page 346
22.2.
Core Method......Page 347
22.3.
Algorithms, Implementations, and Evaluations......Page 348
22.4.
Final Evaluation......Page 358
22.5.
Future Direction......Page 360
References......Page 361
Section 5: Electronic Design Automation......Page 362
23.1.
Introduction......Page 364
23.2.
Simulator Overview......Page 366
23.3.
Compilation and Simulation......Page 368
23.4.
Experimental Results......Page 376
23.5.
Future Directions......Page 383
References......Page 384
24.1.
Introduction, Problem Statement, and Context......Page 386
24.2.
Core Method......Page 388
24.3.
Algorithms, Implementations, and Evaluations......Page 390
24.4.
Final Evaluation......Page 394
24.5.
Future Direction......Page 397
References......Page 399
Section 6: Ray Tracing and Rendering......Page 400
25.1.
Introduction, Problem Statement, and Context......Page 402
25.2.
Core Methods......Page 403
25.3.
Algorithms, Implementation, and Evaluation......Page 404
25.4.
Final Evaluation......Page 414
25.6.
Derivation of the Diffusion Equation......Page 416
References......Page 419
26.1.
Introduction......Page 422
26.3.
Random Walks in Path Tracing......Page 423
26.4.
Implementation Details......Page 427
26.5.
Results......Page 429
Acknowledgments......Page 432
References......Page 433
27.1.
System Overview......Page 434
27.3.
Core Technology and Algorithms......Page 435
27.4.
Future Directions......Page 446
References......Page 447
28.1.
Introduction, Problem Statement, and Context......Page 448
28.3.
Algorithms, Implementations, and Evaluations......Page 449
28.4.
Final Evaluation......Page 454
References......Page 456
Section 7: Computer Vision......Page 458
29.2.
Core Method......Page 460
29.3.
Algorithms, Implementations, and Evaluations......Page 461
29.4.
Final evaluation and validation of results......Page 468
29.5.
Multilabel Graph Cuts......Page 469
References......Page 471
30.1.
Introduction......Page 472
30.2.
Visual Saliency Model......Page 473
30.3.
GPU Implementation......Page 475
30.4.
Results......Page 487
References......Page 492
31.1.
Introduction, Problem Statement, and Context......Page 494
31.2.
Core Method......Page 496
References......Page 515
32.1.
Introduction......Page 518
32.2.
Methods......Page 520
32.3.
Implementation......Page 526
32.4.
Results and Discussion......Page 528
32.5.
Conclusion and Future Work......Page 534
References......Page 535
33.2.
Viola-Jones Object Detection Retrospective......Page 538
33.3.
Object Detection Pipeline with NVIDIA CUDA......Page 547
33.4.
Benchmarking and Implementation Details......Page 562
References......Page 564
Section 8: Video and Image Processing......Page 566
34.1.
Introduction, Problem Statement, and Background......Page 568
34.2.
Core Technology or Algorithm......Page 569
34.3.
Key Insights from Implementation and Evaluation......Page 572
34.4.
Final Evaluation......Page 586
References......Page 588
35.1.
Introduction......Page 590
35.2.
Core Algorithm......Page 591
35.3.
CUDA Algorithm and Implementation......Page 593
35.4.
Final Evaluation and Results......Page 598
References......Page 602
36.1.
Introduction, Problem Statement, and Context......Page 604
36.3.
Algorithms, Implementations, and Evaluations......Page 606
36.4.
Final Evaluation......Page 618
References......Page 619
Section 9: Signal and Audio Processing......Page 620
37.1.
Introduction, Problem Statement, and Context......Page 622
37.2.
Core Methods......Page 624
37.3.
Algorithms, Implementations, and Evaluations......Page 625
37.4.
Conclusion and Future Directions......Page 636
References......Page 638
38.1.
Introduction, Problem Statement, and Context......Page 640
38.2.
Core Technology......Page 641
38.3.
Algorithms, Implementations, and Evaluations......Page 643
38.4.
Final Evaluation......Page 647
References......Page 648
39.1.
Introduction......Page 650
39.2.
Memory Hierarchy of GPU Clusters......Page 652
39.3.
Large-Scale Fast Fourier Transform......Page 654
39.4.
Algebraic Manipulation of Array Dimensions......Page 656
39.6.
Conclusion and Future Work......Page 660
References......Page 663
Section 10: Medical Imaging......Page 664
40.1.
Introduction......Page 668
40.2.
Digital Breast Tomosynthesis......Page 670
40.3.
Accelerating Iterative DBT using GPUs......Page 671
Acknowledgments......Page 677
References......Page 678
41.2.
Core Methods......Page 680
41.3.
Algorithms, Implementations, and Evaluations......Page 682
41.4.
Final Evaluation and Validation of Results, Total Benefits, and Limitations......Page 693
41.5.
Related Work......Page 696
References......Page 697
42.1.
Introduction......Page 700
42.2.
Core Methods......Page 703
42.3.
Implementation......Page 705
42.4.
Evaluation and Validation of Results, Total Benefits, and Limitations......Page 707
42.5.
Future Directions......Page 711
References......Page 712
43.1.
Introduction, Problem Statement, and Context......Page 714
43.2.
Core Method(s)......Page 715
43.3.
Algorithms, Implementations, and Evaluations......Page 716
43.4.
Final Evaluation and Validation of Results, Total Benefits, and Limitations......Page 721
43.5.
Future Directions......Page 727
References......Page 728
44.1.
Introduction......Page 730
44.2.
Core Method: Advanced Image Reconstruction Toolbox for MRI......Page 731
44.3.
MRI Reconstruction Algorithms and Implementation on GPUs......Page 734
44.4.
Final Results and Evaluation......Page 740
44.5.
Conclusion and Future Directions......Page 741
References......Page 742
45.1.
Introduction, Problem Statement, and Context......Page 744
45.2.
Core Methods (High Level Description)......Page 747
45.3.
Algorithms, Implementations, and Evaluations (Detailed Description)......Page 748
45.4.
Final Evaluation and Validation of Results, Total Benefits, and Limitations......Page 754
References......Page 756
46.2.
Core Methods......Page 758
46.3.
Implementation......Page 761
46.4.
Results......Page 767
46.6. Acknowledgments......Page 769
References......Page 770
47.1.
Introduction......Page 772
47.2.
An Overview of B-Spline Registration......Page 773
47.3.
Implementation Details......Page 777
47.4.
Results......Page 788
References......Page 790
48.1.
Introduction, Problem Statement, and Context......Page 792
48.2.
Core Methods......Page 795
48.3.
Algorithms, Implementations, and Evaluations......Page 796
48.4.
Final Evaluation and Validation of Results, Total Benefits, and Limitations......Page 807
48.5.
Future Directions......Page 810
Acknowledgments......Page 811
References......Page 812
49.2.
Core Methods......Page 814
49.3.
Implementation......Page 818
49.4.
Results......Page 830
49.5.
Future Directions......Page 832
References......Page 833
50.1.
Introduction, Problem Statement, and Context......Page 834
50.2.
Core Methods......Page 835
50.3.
Algorithms, Implementations, and Evaluations......Page 836
50.4.
Final Evaluation and Validation of Results, Total Benefits, and Limitations......Page 843
50.5.
Future Directions......Page 848
References......Page 849
Index......Page 852