Parallel Synchronization-Free Approximate Data Structure Construction
Parallel Synchronization-Free Approximate Data Structure Construction
复制标题
并行无同步近似数据结构构建
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
M. Rinard
中科院分区：
文献类型：
--
作者：
M. Rinard
我们提出了近似的数据结构与构造算法，执行不同步。这些算法中存在的数据竞争可能导致它们删除插入或追加的元素。尽管如此，算法1)不会崩溃，2)可以生成足够精确的数据结构，使其客户端能够成功使用。我们提倡一种近似数据结构的方法，该方法由基本的树和数组构建块以及相关的无同步构建算法组成。这种方法使开发人员能够重用构造算法，这些算法被设计成在并行上下文中成功执行，尽管存在数据竞争，而不必了解它们成功执行的原因。我们通过为Barnes-Hut n体模拟构建一个空间细分树来评估我们方法的端到端准确性和性能后果。由此产生的近似数据结构构造算法消除了同步开销和异常，例如过度序列化和死锁。该算法表现出良好的性能（在16核上运行速度比顺序版本快14倍）和良好的精度（精度损失比将Barnes-Hut质心近似精度提高20%所带来的精度增益小4个数量级）。
We present approximate data structures with construction algorithms that execute without synchronization. The data races present in these algorithms may cause them to drop inserted or appended elements. Nevertheless, the algorithms 1) do not crash and 2) may produce a data structure that is accurate enough for its clients to use successfully. We advocate an approach in which the approximate data structures are composed of basic tree and array building blocks with associated synchronization-free construction algorithms. This approach enables developers to reuse the construction algorithms, which have been engineered to execute successfully in parallel contexts despite the presence of data races, without having to understand the details of why they execute successfully. We evaluate the end-to-end accuracy and performance consequences of our approach by building a space-subdivision tree for the Barnes-Hut N-body simulation out of our presented tree and array building blocks. The resulting approximate data structure construction algorithm eliminates synchronization overhead and anomalies such as excessive serialization and deadlock. The algorithm exhibits good performance (running 14 times faster on 16 cores than the sequential version) and good accuracy (the accuracy loss is four orders of magnitude less than the accuracy gain associated with increasing the accuracy of the Barnes-Hut center of mass approximation by 20%).