Posted on 2008-02-09 13:14
ZelluX 閱讀(354)
評論(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