Patent Document ID: 8117288
Application ID: 10963101
Patent Flag: 1

Claim One:
1. A computer-implemented method to optimize an allocation of a software application across two or more parallel computational nodes on a parallel-processing system, the computer-implemented method comprising: receiving a communications profile of a software application comprising a plurality of software computations i for execution across two or more parallel computational nodes j on a parallel-processing system coupled together by a communications fabric, wherein at least a first software computation of the plurality of software computations communicates application data from at least a second software application of the plurality of software computations i, and wherein the communications profile includes an amount of software application data communicated between each of the software computations given by C(i, j); implementing, from the communications profile of the software application which has been received, an initial heuristic map defined by mapping each of the software computations i, in a domain D of all the software computation i on a given computational node, for i=1 to D by iteratively performing until i=D the following: mapping one of the software computations i=1 to one of the computational nodes j at a first arbitrary location of a node (x, y, z); mapping all domains with which domain i communicates either to the one of the computational nodes j at the initial location of the node (x, y, z) or to one of the computational nodes j in a neighboring location on the parallel processing system while satisfying the constraint of Int(p)≦n(x, y, z)≦Int (p+1), wherein n(x, y, z) is a number of domains mapped to the node (x, y, z), wherein D domains, which are to be mapped to a supercomputer computer with a number of nodes L×M×N, where p=D/(L×M×N)) be the number of domains mapped to each supercomputer node on average, and wherein Int(p) is the integer part of p; mapping domain i=2, in response to domain i=2 is not yet mapped, to one of the computational nodes i at a second arbitrary location of a node (x′, y′, z′) and the domains with which it communicates either to a same computational node at the second arbitrary location of a node (x′, y′, z′) or one of the computational nodes j in a neighboring location a neighboring computational node on the parallel processing system while satisfying the constraint of Int(p)≦n(x, y, z)≦Int(p+1); generating a Markov chain of maps from the initial heuristic map using Monte Carlo simulation with Free Energy given by F=Σ i,j C(i, j)H(i, j) where H(i, j) is an inter-node cost communication function; and mathematically minimizing H(i, j) using only the inter-node communication cost function for a total amount of software application data transferred between the parallel computational nodes j, wherein minimizing the inter-node communication cost minimizes inter-node communication time using simulated annealing, and wherein computation costs are uniform across the two or more parallel computational nodes j, wherein the total amount of software application data transferred between the parallel computational nodes i is minimized by at least one of a global time and a discrete time interval so as to reduce the inter-node communication cost of the software application, and the simulated annealing is performed by selecting a new candidate map M N i from M N i-1 , of a set of candidate maps M i =M N i when R<exp[−β{F(M N i −F(M i-1 )}/F min ], where R is a random number uniformly distributed in (0, 1) and where i is a non-negative integer and M o is the heuristic map and M i is derived from M i-1 by applying a Metropolis Algorithm and β is the inverse temperature β=1/T, F min is a minimum calculated Free Energy, and new candidate mappings M N i are generated using a same β value until the Free Energy decreases to a stable equilibrium.