A sound and complete abstraction for reasoning about parallel prefix sums
A sound and complete abstraction for reasoning about parallel prefix sums
复制标题
用于推理并行前缀和的合理且完整的抽象
DOI：
10.1145/2535838.2535882
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Chong N
中科院分区：
文献类型：
--
作者：
Chong N
前缀和是许多并发软件应用程序实现中的关键构建块，并且最近许多工作已经有效地实现前缀和以在大规模并行图形处理单元（GPU）上运行。因为他们躺在许多GPU加速的应用程序的心脏，前缀和实现的正确性是最重要的。我们引入了一种新的抽象，区间的总和，允许可扩展的推理实现前缀和。我们提出了这个抽象作为一个幺半群，并证明了一个健全性和完整性的结果表明，一个通用的顺序前缀和实现是正确的长度的数组，当且仅当它计算正确的结果时，一个特定的测试用例实例化的时间间隔的总和幺半群。这允许通过运行一个单一的测试来建立正确性，其中输入和结果需要O（n lg（n））空间。这改进了Shepherd的现有结果，其中输入需要O（nlg（n））空间和结果O（n2\lg（n））空间，并且比Voigtlaender的方法更可行，该方法使用O（n）空间用于输入和结果，但需要运行O（n2）测试。然后，我们将我们的抽象和结果扩展到数据并行程序的上下文中，为前缀和的GPU实现开发了一种自动验证方法。我们的方法使用静态验证来证明通用前缀和实现是无数据竞争的，之后可以通过在求和抽象间隔下运行单个测试用例来确定实现的功能正确性。我们使用四种不同的前缀和算法进行了实验评估，表明我们的方法具有高度自动化，可扩展到大线程数，并且当应用于大阵列时，显著优于Voigtlaender的方法。
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 parallel 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 soundness and completeness result showing that a generic sequential prefix sum implementation is correct for an array of lengthif 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 input and result require O(n lg(n)) space. This improves upon an existing result by Sheeran where the input requires O(n lg(n)) space and the result O(n2\lg(n)) space, and is more feasible for largenthan a method by Voigtlaender that uses O(n) space for the input and result but requires running O(n2) tests. We then extend our abstraction and results to the context of data-parallel programs, developing an automated verification method for GPU implementations of prefix sums. Our method uses static verification to prove that a generic prefix sum implementation is data race-free, after which functional correctness of the implementation can be determined by running a single test case under the interval of summations abstraction.We present an experimental evaluation using four different prefix sum algorithms, showing that our method is highly automatic, scales to large thread counts, and significantly outperforms Voigtlaender's method when applied to large arrays.
登录
查看更多内容
扫描代数
DOI：
10.1007/978-3-540-27764-4_11
发表时间：
2004
期刊：
American journal of kidney diseases : the official journal of the National Kidney Foundation
影响因子：
--
作者：
R. Hinze
通讯作者：
R. Hinze
OpenCL 代码的符号测试
DOI：
--
发表时间：
2011
期刊：
Haifa Verification Conference
影响因子：
--
作者：
Peter Collingbourne;Cristian Cadar;P. Kelly
通讯作者：
P. Kelly
MPI 并行前缀（扫描）算法
影响因子：
4.3
作者：
P. Sanders;J. Träff
通讯作者：
J. Träff
一种快速实用的高阶牛顿插值并行方法
影响因子：
1.5
作者：
Ö. Eğecioğlu;Efstratios Gallopoulos;Ç. Koç
通讯作者：
Ç. Koç
基于 SMT 的可扩展 GPU 内核功能验证
影响因子：
12.6
作者：
Guodong Li;G. Gopalakrishnan
通讯作者：
G. Gopalakrishnan