加速基于 GPU 的 Top-K 计算.pdf

1、NVIDIAACCELERATING TOP-KCOMPUTATION ON GPUChristina Zhang 8 Yong Wang#page#OUTLINEAlgorithms for Top-KOptimizing WarpSelectOptimizing Radix Select#page#PROBLEM DEFINITIONTop-K:find k smallest (or largest） elements in a list of Nelements.For example，whenN=8，k=3：34615827#page#TWO USEFUL ENHANCEMENTS I

2、N PRACTICEbatch processingreturn also the index3461583OO4index01234567287S4628346#page#ALGORITHM 1: SORTINGinput3461582217sorted112134567884advantage: highly efficient sorting algorithms for GPU existdisadvantage:do more work than necessaryGPU implementatiion: cub：DeviceRadixSort from CUB library#pa

3、ge#ALGORITHM 2: PRIORITY QUEUE (PQ）maintain a PQof size k，and try to insert elements one after one:PO642PQY642介432a failed insertiona successful insertionadvantages:read data only once， can handle streaming data efficient when k is smallDisadvantage:depending on the implementation of PQ，the time com

4、plexity is usually at least proportional to log kinefficient when kis largeGPU implementation: WarpSelect from FAISS Library (https:/ PQ is commonly implemented with Heap for CPU.using parallel sorting can be more effiicient on GPU.#page#ALGORITHM 3: SELECTION + FILTERa closely related problem is K-

5、selection Problem:find the k-th smallest(or largest)element ina list of Nelementsinput 34161518217selectionl31416111518|217filter by3H2eep aepauu sululeuleu nle kq sinsal ydo uanalo paypou aq ue suuosie uoas auos aou）thus dont neeed the filter step）#page#ALGORITHM 3: SELECTION + FILTERmany sorting a

6、lgorithms have corresponding selection algorithms:sortingselectionquicksortquick selectsamplesortsample selectradix sortradix selectadvantages: selection algorithm usually has time complexity O(N），so efficient when kand Nare largedisadvantages: may need to read input multiple timesGPU implementation