Efficient Resource Oblivious Algorithms for Multicores with False Sharing
Efficient Resource Oblivious Algorithms for Multicores with False Sharing
复制标题
具有错误共享的多核高效资源忽略算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
V. Ramachandran
中科院分区：
文献类型：
--
作者：
R. Cole;V. Ramachandran
我们考虑用于多核环境的算法，在该环境中，每个核都有自己的私有缓存，并且可能发生虚假共享。当两个或多个处理器并行访问同一块(即高速缓存线)，并且至少有一个处理器写入块中的某个位置时，就会发生虚假共享。错误共享会导致不同的处理器对块中的数据具有不一致的视图，而当前用于解决这些不一致的许多方法可能会导致较大的延迟。我们分析了存储在并行任务的执行堆栈上的变量和输出变量的虚假共享的代价。我们的主要技术贡献是为多线程的块弹性HBP(分层平衡并行)计算建立了这种开销的低成本。利用这一技术和其他技术，我们开发了块弹性HBP算法，用于几个基本问题，包括扫描、矩阵乘法、FFT、排序，以及用于列表排名和图连通分量的混合块弹性HBP算法，并且具有较低的错误共享成本。这些算法中的大多数都是从已知的多核算法派生出来的，但经过进一步改进以实现较低的虚假共享开销。我们的算法没有提到机器参数，我们对错误共享开销的分析主要是根据计算过程中并行生成的任务数量来进行的，因此适用于各种调度器。
We consider algorithms for a multicore environment in which each core has its own private cache and false sharing can occur. False sharing happens when two or more processors access the same block (i.e., cache-line) in parallel, and at least one processor writes into a location in the block. False sharing causes different processors to have inconsistent views of the data in the block, and many of the methods currently used to resolve these inconsistencies can cause large delays. We analyze the cost of false sharing both for variables stored on the execution stacks of the parallel tasks and for output variables. Our main technical contribution is to establish a low cost for this overhead for the class of multithreaded block-resilient HBP (Hierarchical Balanced Parallel) computations. Using this and other techniques, we develop block-resilient HBP algorithms with low false sharing costs for several fundamental problems including scans, matrix multiplication, FFT, sorting, and hybrid block-resilient HBP algorithms for list ranking and graph connected components. Most of these algorithms are derived from known multicore algorithms, but are further refined to achieve a low false sharing overhead. Our algorithms make no mention of machine parameters, and our analysis of the false sharing overhead is mostly in terms of the the number of tasks generated in parallel during the computation, and thus applies to a variety of schedulers.