Enhancing data locality by using terminal propagation
Enhancing data locality by using terminal propagation
复制标题
使用终端传播增强数据局部性
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
R. V. Driessche
中科院分区：
文献类型：
--
作者：
B. Hendrickson;R. Leland;R. V. Driessche
终端传播是电路布置界为图划分问题添加约束而开发的一种方法。本文采用并扩展了这一思想，并将其应用于并行计算机处理器之间的数据结构划分问题。我们将展示如何使用终端传播中的约束来鼓励仅在架构上靠近处理器的处理器之间通信消息的分区。然后，我们展示了如何在两种重要的划分算法中处理这些约束，谱平分和多层kl。我们将这些算法生成的分区的质量相互比较，并与更熟悉的技术生成的分区进行比较。
Terminal propagation is a method developed in the circuit placement community for adding constraints to graph partitioning problems. This paper adapts and expands this idea, and applies it to the problem of partitioning data structures among the processors of a parallel computer. We show how the constraints in terminal propagation can be used to encourage partitions in which messages are communicated only between architecturally near processors. We then show how these constraints can be handled in two important partitioning algorithms, spectral bisection and multilevel-KL. We compare the quality of partitions generated by these algorithms to each other and to partitions generated by more familiar techniques.