nchong / scan Goto Github PK
View Code? Open in Web Editor NEWScan (prefix-sum) on OpenCL
Scan (prefix-sum) on OpenCL
Scan implementations using OpenCL ================================= This project contains some simple exclusive scan (re)implementations for arbitrary length arrays: - harris[0] is a vanilla scan - sengupta[1] is a segmented scan. SCAN IN A NUTSHELL ------------------ Suppose you have a bunch of threads that each produce an arbitrary number of outputs. For example, thread 0 outputs 3 values (a,b,c) thread 1 outputs 0 values () thread 2 outputs 2 values (i,j) thread 3 outputs 1 values (x). It is not known statically now many values a thread will produce (but you do know how many will be produced in total, in this case 6). You want to store these outputs in a contiguous array: 0 1 2 3 4 5 +---+---+---+---+---+---+ | a | b | c | i | j | x | +---+---+---+---+---+---+ How can you do this? You need an exclusive scan operation! Taking the array containing the number of outputs for each thread: t0 t1 t2 t3 +---+---+---+---+ | 3 | 0 | 2 | 1 | +---+---+---+---+ An exclusive scan operation calculates, for each index i, the sum of the elements preceding it. That is, for our example: t0 t1 t2 t3 +---+---+---+---+ | 0 | 3 | 3 | 5 | +---+---+---+---+ Which is exactly the offset into our contiguous array that each thread needs to write. It turns out this is a very useful operation (see Blelloch[2]) and can be put to good use for all sorts of goodness. Fortunately, there are work-efficient algorithms for computing scans in parallel. READMORE -------- http://en.wikipedia.org/wiki/Prefix_sum [0] HARRIS [Parallel Prefix Sum (Scan) with CUDA](http://developer.download.nvidia.com/compute/cuda/1_1/Website/projects/scan/doc/scan.pdf) [1] SENGUPTA ET AL [Scan Primitives for GPU Computing](http://www.google.co.uk/url?sa=t&source=web&cd=1&ved=0CCgQFjAA&url=http%3A%2F%2Fciteseer.ist.psu.edu%2Fviewdoc%2Fdownload%3Bjsessionid%3D1190FF7DA52704424448D3AFDDF1AE40%3Fdoi%3D10.1.1.131.3326%26rep%3Drep1%26type%3Dpdf&ei=CpOMTqa4HoWWhQfRoIHgAw&usg=AFQjCNHqpkKwQMHosfwVNEmWm1dFI9CM0g) [2] BLELLOCH [Prefix Sums and Their Applications](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.128.6230&rep=rep1&type=pdf)
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.