Optimizing layout of an application on a massively parallel supercomputer
US8117288B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Oct 12, 2004 |
| Grant date | Feb 14, 2012 |
| Priority date | — |
| Expiry date | Oct 1, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F9/5066
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
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 …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.