Posted on 2008-02-09 13:14
ZelluX 阅读(336)
评论(0) 编辑 收藏 所属分类:
Laboratory
4. GPGPU Techniques
4.1. Stream Operations
4.1.1. Map
Given a stream of data elements and a function, map will apply the function to every element in the stream.
4.1.2. Reduce
Sometimes a computation requires computing a smaller stream from a larger input stream, possibly to a single element stream. This type of computation is called a reduction. For example, computing the sum or maximum of all the elements in a stream.
On GPUs, reductions can be performed by alternately rendering to and reading from a pair of textures.
也就是用分治法，不断切换输入和输出数据，每次都能减少一定比例的数据规模。
4.1.3. Scatter and Gather
If the write and read operations access memory indirectly, they are called scatter and gather respectively.
4.1.4. Stream Filtering
This stream fitering operation is essentially a nonuniform reduction.
4.1.5. Sort
Classic sorting algorithms are data-dependent and generally require scatter operations.
主要的几个算法都和Sorting Network有关，还有一种adaptive sort，和原来序列的有序度相关。
4.1.6. Search
4.2. Data Structures