Loading...
Please wait, while we are loading the content...
Similar Documents
A sound and complete abstraction for reasoning about parallel prefix sums ∗.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chong, Nathan Donaldson, Alastair F. Ketema, Jeroen |
| Abstract | Prefix sums are key building blocks in the implementation of many concurrent software applications, and recently much work has gone into efficiently implementing prefix sums to run on massively par-allel graphics processing units (GPUs). Because they lie at the heart of many GPU-accelerated applications, the correctness of prefix sum implementations is of prime importance. We introduce a novel abstraction, the interval of summations, that allows scalable reasoning about implementations of prefix sums. We present this abstraction as a monoid, and prove a sound-ness and completeness result showing that a generic sequential pre-fix sum implementation is correct for an array of length n if and only if it computes the correct result for a specific test case when instantiated with the interval of summations monoid. This allows correctness to be established by running a single test where the in- |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Prefix Sum Parallel Prefix Sum Complete Abstraction Many Gpu-accelerated Application Prefix Sum Implementation Completeness Result Single Test Many Concurrent Software Application Novel Abstraction Par-allel Graphic Much Work Specific Test Case Generic Sequential Pre-fix Sum Implementation Prime Importance Correct Result |
| Content Type | Text |
