公开(公告)号：US08117288B2

公开(公告)日：2012-02-14

申请号：US10963101

申请日：2004-10-12

申请人： Gyan V. Bhanot ,  Alan Gara ,  Philip Heidelberger ,  Eoin M. Lawless ,  James C. Sexton ,  Robert E. Walkup

发明人： Gyan V. Bhanot ,  Alan Gara ,  Philip Heidelberger ,  Eoin M. Lawless ,  James C. Sexton ,  Robert E. Walkup

IPC分类号： G06F15/177

CPC分类号： G06F9/5066

摘要： A general computer-implement method and apparatus to optimize problem layout on a massively parallel supercomputer is described. The method takes as input the communication matrix of an arbitrary problem in the form of an array whose entries C(i, j) are the amount to data communicated from domain i to domain j. Given C(i, j), first implement a heuristic map is implemented which attempts sequentially to map a domain and its communications neighbors either to the same supercomputer node or to near-neighbor nodes on the supercomputer torus while keeping the number of domains mapped to a supercomputer node constant (as much as possible). Next a Markov Chain of maps is generated from the initial map using Monte Carlo simulation with Free Energy (cost function) F=Σi,jC(i,j)H(i,j)− where H(i,j) is the smallest number of hops on the supercomputer torus between domain i and domain j. On the cases tested, found was that the method produces good mappings and has the potential to be used as a general layout optimization tool for parallel codes. At the moment, the serial code implemented to test the method is un-optimized so that computation time to find the optimum map can be several hours on a typical PC. For production implementation, good parallel code for our algorithm would be required which could itself be implemented on supercomputer.

摘要翻译： 描述了在大型并行超级计算机上优化问题布局的通用计算机实现方法和装置。 该方法采用数组形式的任意问题的通信矩阵作为输入，其条目C（i，j）是从域i到域j传送的数据量。 给定C（i，j），首先实现启发式映射，其尝试顺序地将域及其通信邻居映射到超级计算机节点或超级计算机环面上的近邻节点，同时保持域的数量映射到 超级计算机节点常数（尽可能多）。 接下来，使用具有自由能的蒙特卡罗模拟（成本函数）F =＆Sgr; i，jC（i，j）H（i，j），从初始映射生成马尔科夫链映射。其中H（i，j） 域i和域j之间的超级计算机环面上的最小跳数。 在测试的情况下，发现该方法产生良好的映射，并且有可能被用作并行代码的通用布局优化工具。 此时，实现测试方法的序列号未优化，以便在典型的PC上找到最佳映射的计算时间可以为几个小时。 对于生产实现，将需要我们的算法的良好的并行代码，这本身可以在超级计算机上实现。