Scalability

Materials Science Research Group

Monte Carlo simulations of the time evolution of very large systems with tens of thousands to millions of individual parts must be executed on massively parallel computers. However, problems with causality may occur on the boundaries between the processing elements (PEs), and any scheme to solve this problem must lead to a reduction in computing speed. In our group we have therefore studied a particular class of parallel kinetic Monte Carlo algorithms (aka parallel discrete event simulations, or PDES) called "conservative." In these algorithms, a PE is required to idle until it is guaranteed that no causality conflicts with its neighbors can arise. In our work we used concepts from the theory of surface growth in materials science to show that the simulation speed nevertheless increases proportionally with the number of PEs, i.e., the simulation is scalable [G. Korniss, Z. Toroczkai, M.A. Novotny, and P.A. Rikvold, Physical Review Letters 84, 1351 (2000)]. However, a problem still remained: the width of the time surface (shown in the accompanying figure), increases with the number of PEs. As a result, if one actually wants to perform a measurement on the simulation on the simultaion at a particular time (and why else would one do the simulation in the first place?), more and more memory is required as the number of PEs increases. Again we found the solution in a seemingly different area of science: the theory of networks. The "principle of six degrees of separation" states that any two human beings anywhere in the world can be connected by a chain of about six people who know each other. Such a network is called a "small-world network." We used this idea to have a few of the PEs check causality, not only against their nearest neighbors, but also against one randomly chosen PE anywhere else in the system. As a result, the rough time surface shown in the figure becomes smooth, and the measurment process becomes scalable as well [G. Korniss, et al., Science 299, 677 (2003)]. This exciting, multidisciplinary work is continuing.

Publications

All of these online publcations can be found for free at the Los Alamos Condensed Matter Preprint Server (cond-mat) by following the links below. All papers are also published in print. The abstract, postscript, and publication information can be found by following the links.

Papers in Reverse Chronological Order:

Note: The authors' names below are links to cond-mat publication lists, not to the authors' home pages.

6. cond-mat/0306222

: Title: Update statistics in conservative parallel discrete event simulations of asynchronous systems
Authors: A. Kolakowska, M. A. Novotny, Per Arne Rikvold

5. cond-mat/0302050

: Title: Suppressing Roughness of Virtual Times in Parallel Discrete-event Simulations
Authors: G. Korniss, M.A. Novotny, H. Guclu, Z. Toroczkai, P.A. Rikvold

4. cond-mat/0112103

: Title: Going through Rough Times: from Non-Equilibrium Surface Growth to Algorithmic Stability
Authors: G. Korniss, M.A. Novotny, P.A. Rikvold, H. Guclu, Z. Toroczkai

3. cond-mat/9812344

: Title: Parallelization of a Dynamic Monte Carlo Algorithm: a Partially Rejection-Free Conservative Approach
Authors: G. Korniss, M. A. Novotny, P. A. Rikvold (Florida State U.)

2. cond-mat/0002469

Title: Non-equilibrium Surface Growth and Scalability of Parallel Algorithms for Large Asynchronous Systems
Authors: G. Korniss, M.A. Novotny, Z. Toroczkai, P.A. Rikvold

1. cond-mat/9909114

Title: From Massively Parallel Algorithms and Fluctuating Time Horizons to Non-equilibrium Surface Growth
Authors: G. Korniss, Z. Toroczkai, M. A. Novotny, P. A. Rikvold

Back to Materials Science Group Page