The plot below shows parallel efficiency for SPPARKS running a Potts grain growth model with a KMC algorithm on a cubic lattice with 26 neighbors per site. Four different size problems were run on varying numbers of processors on Sandia's Cray XT3 (Red Storm) machine. The four problem sizes were 1 million lattice sites, 3.375 million sites, 8 million sites, and 1 billion sites. Runs on 1 processor were considered to be 100% efficient. Thus a run on 100 processors with parallel efficiency of 120% means that it ran 120x faster on 100 processors than it did on 1 processor. Since the largest billion-site problem could not be run on 1 processor, it's efficiency on 216 processors was estimated as the baseline measurement for the blue data points. Overall, the data indicate very large on-lattice problems can be run on large numbers of processors with high parallel efficiency.
Normally, a parallel code will fall off from 100% efficiency as a problem is run on more processors. In this case, the parallel efficiency actually increases modestly across a wide range of processor counts. This is because a tree-based event selection routine is being used in the KMC solver. It's cost scales as log(N) in the number of events N to select from, at each step. Since the number of sites per processor shrinks as processors are added, and N is proportional to the number of sites per processor, the cost of event selection decreases as processor count increases.
The smallest problem (1 million lattice sites) was run in two different modes, with DeltaN = 0.125 and 1.25. DeltaN is the nstop parameter in the sector command and determines how long the KMC algorithm performs selection in one octant of a processor's sub-domain before communicating and moving to the next octant. Thus runs with a small DeltaN perform more communication and are less parallel efficient as processor count increases.
This benchmark and the various KMC solver options in SPPARKS are discussed in more detail in the technical report listed on the publications page.