ECE408@UIUC CUDA C++实现并行计算的Reduction Tree Addition ECE408@UIUC CUDA C++实现并行计算的Reduction Tree Addition 如何理解Reduction Tree: 一句话概括 :用树形结构实现 多线程的并行化 从而降低 时间复杂度。 Reduction Tree的性质:我们知道 求和一个长度为N的数列怎么的也得进行N-1次加法 , 怎么优化都是进行基于加法的交换/结合定律进行优化。 并行计算设备上实现Reduction Tree的优势: 我们可以同时计算很多路,所以我们可以结合足够多的简单的加法计算实现 很多个相邻元素的相加结合,归并地进行计算 在实际效果上形成了低时间复杂度的一个 树形结构:Reduction Tree,总的时间上从O(N)降低到了O(log(N))。 CUDA C++实现 x int main (){ /* Some launch code..... */ //@@ Initialize the grid and block dimensions here dim3 DimGrid ( numOutputElements , 1 , 1 ); dim3 DimBlock ( BLOCK_SIZE , 1 , 1 ); //@@ Launch the GPU Kernel here total <<< DimGrid , DimBlock >>> ( deviceInput , deviceOutput , numInputElements ); cudaDeviceSynchronize (); cudaMemcpy ( hostOutput , deviceOutput , numOutputElements * sizeof ( float ), cudaMemcpyDeviceToHost ); /********************************************************...
留言
張貼留言