PHI: Architectural Support for Synchronization- and Bandwidth-Efficient Commutative Scatter Updates
PHI: Architectural Support for Synchronization- and Bandwidth-Efficient Commutative Scatter Updates
复制标题
DOI：
10.1145/3352460.3358254
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Anurag Mukkara;Nathan Beckmann;Daniel Sánchez
中科院分区：
文献类型：
--
作者：
Anurag Mukkara;Nathan Beckmann;Daniel Sánchez
许多应用程序经常对大型数据结构进行散步。在当前系统中，散布更新的位置很高，这些弊端会导致推送式执行，当算法允许时，程序员会倾向于基于收集读数的拉力实现PHI，一种推动缓存层次结构，使散点更新同步 - phi添加了phi的支持。层次结构。暂时的和空间的局部性好处，其中一些不适用于收集读数，因此PHI不仅使推动算法有效，而且使它们始终如一地比拉算法。稀疏的应用程序处理大型输入。
Many applications perform frequent scatter update operations to large data structures. For example, in push-style graph algorithms, processing each vertex requires updating the data of all its neighbors. Neighbors are often scattered over the whole graph, so these scatter updates have poor spatial and temporal locality. In current systems, scatter updates suffer high synchronization costs and high memory traffic. These drawbacks make push-style execution unattractive, and, when algorithms allow it, programmers gravitate towards pull-style implementations based on gather reads instead. We present PHI, a push cache hierarchy that makes scatter updates synchronization- and bandwidth-efficient. PHI adds support for pushing sparse, commutative updates from cores towards main memory. PHI adds simple compute logic at each cache level to buffer and coalesce these commutative updates throughout the hierarchy. This avoids synchronization, exploits temporal locality, and produces a load-balanced execution. Moreover, PHI exploits spatial locality by selectively deferring updates with poor spatial locality, batching them to achieve sequential main memory transfers. PHI is the first system to leverage both the temporal and spatial locality benefits of commutative scatter updates, some of which do not apply to gather reads. As a result, PHI not only makes push algorithms efficient, but makes them consistently faster than pull ones. We evaluate PHI on graph algorithms and other sparse applications processing large inputs. PHI improves performance by 4.7× on average (and by up to 11×), and reduces memory traffic by 2× (and by up to 5×).