Graph contraction for physical optimization methods: a quality-cost tradeoff for mapping data on parallel computers
Graph contraction for physical optimization methods: a quality-cost tradeoff for mapping data on parallel computers
复制标题
物理优化方法的图收缩：并行计算机上映射数据的质量成本权衡
DOI：
10.1145/165939.165942
复制
发表时间：
1993
影响因子：
2.9
通讯作者：
G. Fox
中科院分区：
文献类型：
--
作者：
N. Mansour;R. Ponnusamy;A. Choudhary;G. Fox
将数据映射到并行计算机的目的是最小化相关应用程序的执行时间。但是，如果问题的大小很大，则与应用程序的执行时间相比，它可能花费不可接受的时间量。在本文中，首先，我们激励的情况下，图收缩作为一种手段，减少问题的大小。我们将我们的讨论限制在可以使用图描述问题域的应用中（例如，计算流体动力学应用）。然后，我们提出了一个面向映射的并行图收缩（PGC）的启发式算法，产生一个较小的表示的映射，然后应用的问题。原问题的映射解是通过直接插值得到的。然后，我们提出的实验结果使用收缩图作为输入的两个物理优化方法，即遗传算法和模拟退火。实验结果表明，PGC算法仍然导致一个相当好的质量映射解决方案的原始问题，同时产生了大量减少映射时间。最后，我们讨论了在执行图收缩的成本质量权衡。
Mapping data to parallel computers aims at minimizing the execution time of the associated application. However, it can take an unacceptable amount of time in comparison with the execution time of the application if the size of the problem is large. In this paper, first we motivate the case for graph contraction as a means for reducing the problem size. We restrict our discussion to applications where the problem domain can be described using a graph (e.g., computational fluid dynamics applications). Then we present a mapping-oriented Parallel Graph Contraction (PGC) heuristic algorithm that yields a smaller representation of the problem to which mapping is then applied. The mapping solution for the original problem is obtained by a straight-forward interpolation. We then present experimental results on using contracted graphs as inputs to two physical optimization methods; namely, Genetic Algorithm and Simulated Annealing. The experimental results show that the PGC algorithm still leads to a reasonably good quality mapping solutions to the original problem, while producing a substantial reduction in mapping time. Finally, we discuss the cost-quality tradeoffs in performing graph contraction.