Efficient GPU Implementation of Affine Index Permutations on Arrays

on YouTube ↗42m

" summary

Presents GPU kernels that implement BMMC (bit-matrix-multiply-complement) index permutations with performance comparable to as fast as a simple array copy, using tiled shared-memory reads/writes and bitwise linear-algebra on indices. A BPC (bit-permute-complement) kernel uses one kernel for BPC, two for BMMC; BPC runs nearly at a 9.5 ms reference copy, tiled transpose gives >2× speedup over naive, and larger arrays amplify gains. Works for FFT bit-reversal, Palm combinator and sorting-network layouts; requires power-of-two sizes and an offline-known permutation.

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 4:03GPU architecture basics
3. 7:16Matrix transposition on GPUs
4. 11:57Affine index permutations
5. 16:13Bit-permute-complement permutations
6. 20:45Implementing the Palm combinator
7. 25:29Tiled kernel for BPC
8. 28:01Generalizing to BMMC
9. 32:00Performance evaluation
10. 35:15Summary and limitations
11. 36:21Q&A

" related talks

• 24mAdvanced SIMD Algorithms in PicturesDenis Yaroshevskiy · CppCon 2023
• 28mCommunication Avoiding Algorithms for Linear Algebra and BeyondJim Demmel · Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013)
• 01h 04mDesign for PerformanceFedor Pikus · CppCon 2018
• 01h 02mSqueezing the Hardware to Make Performance JuiceSasha Goldshtein · NDC London 2017
• 46m.NET Intrinsics in CoreCLR 3.0Dan Schechter · Dotnetos Conference 2019
• 48mC++ Algorithmic Complexity, Data Locality, Parallelism, Compiler Optimizations, & Some ConcurrencyAvi Lachmish · CppCon 2022
• 02h 50mFunctional Array Funhouse Intensive - Part 3 of 5Aaron W Hsu · LambdaConf 2017
• 01h 00m“Want fast C++? Know your hardware!"Timur Doumler · CppCon 2016