banner image
No data available.
Please log in to see this content.
You have no subscription access to this content.
No metrics data to plot.
The attempt to load metrics for this article has failed.
The attempt to plot a graph for these metrics has failed.
The midpoint method for parallelization of particle simulations
Rent this article for
Access full text Article
1.M. Karplus and J. A. McCammon, Nat. Struct. Biol. 9, 646 (2002);
1.C. L. Brooks and D. A. Case, Chem. Rev. (Washington, D.C.) 93, 2487 (1993);
1.D. Frenkel and B. Smit, Understanding Molecular Simulation: From Algorithms to Applications, 2nd ed. (Academic, London, 2001);
1.W. Wang, O. Donini, C. M. Reyes, and P. A. Kollman, Annu. Rev. Biophys. Biomol. Struct. 30, 211 (2001);
1.T. Schlick, R. D. Skeel, A. T. Brunger, L. V. Kalé, J. A. Board, J. Hermans, and K. Schulten, J. Comput. Phys. 151, 9 (1999).
2.G. S. Almasi, C. Cascaval, J. G. Castanos et al., Int. J. Parallel Prog. 30, 317 (2002).
3.D. van der Spoel, E. Lindahl, B. Hess, G. Groenhof, A. E. Mark, and H. J. C. Berendsen, J. Comput. Chem. 26, 1701 (2005).
4.R. W. Hockney and J. W. Eastwood, Computer Simulation Using Particles (Adam Hilger, Bristol, 1988).
5.J. J. Monaghan, Annu. Rev. Astron. Astrophys. 30, 543 (1992).
6.G. S. Heffelfinger, Comput. Phys. Commun. 128, 219 (2000);
6.S. Plimpton, J. Comput. Phys. 117, 1 (1995).
7.K. J. Bowers, R. O. Dror, and D. E. Shaw, J. Phys.: Conf. Ser.16, 300 (2005).
8.K. J. Bowers, R. O. Dror, and D. E. Shaw, J. Comput. Phys. (in press).
9.D. E. Shaw, J. Comput. Chem. 26, 1318 (2005).
10.B. G. Fitch, A. Rayshubskiy, M. Eleftheriou et al., Blue Matter: Strong Scaling of Molecular Dynamics on Blue Gene/L, IBM Report RC23688, IBM (2005).
11.B. G. Fitch, A. Rayshubskiy, M. Eleftheriou et al., Blue Matter: Strong Scaling of Molecular Dynamics on Blue Gene/L, IBM Report RC23888, IBM (2006).
12.One can only guarantee that an interaction between two particles residing in the same processor will be computed on that processor if the region assigned to that processor is convex.
13.We have discovered novel neutral territory methods whose import volume is slightly smaller than that of the midpoint and ES methods for small . These methods will be described in a subsequent paper.
14.M. Snir, Theory Comput. Syst. 37, 295 (2004).
15.These figures are approximate because we have ignored the constraints on box aspect ratios due to the finite number of processors. In order for the boxes to be exactly cubic when the global cell is cubic, for example, the number of processors must be the cube of some integer. In practice, one might choose not to use a few of the available processors in order to obtain more convenient aspect ratios.
16.Red Storm System Raises Bar on Supercomputer Scalability (Cray, Seattle, 2003);
16.N. R. Adiga, G. Almasi, G. S. Almasi et al., in Proceedings of the 3rd IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, Jersey City, NJ, 207 (2005);
16.R. E. Kessler and J. L. Schwarzmeier, in 38th IEEE Comput. Soc. Intl. Conf., 176 (1993);
16.S. Scott and G. Thomas, in Proceedings of Hot Interconnects IV, 147 (1996).
17.J. MacKerell, D. Bashford, M. Bellott et al., J. Phys. Chem. B 102, 3586 (1998).
18.P. A. Kollman, R. W. Dixon, W. D. Cornell, T. Fox, C. Chipot, and A. Pohorille, in Computer Simulations of Biological Systems, edited by W. F. van Gunsteren (Kluwer, Dordrecht, Netherlands ESCOM, Leiden, 1997), Vol. 3, 83.
19.W. L. Jorgensen, D. S. Maxwell, and J. Tirado-Rives, J. Am. Chem. Soc. 118, 11225 (1996).
20.W. R. P. Scott, P. H. Hünenberger, I. G. Tironi, A. E. Marks, S. R. Billeter, J. Fennen, A. E. Torda, T. Huber, P. Krüger, and W. F. van Gunsteren, J. Phys. Chem. A 103, 3596 (1999).
21.T. A. Halgren, J. Comput. Chem. 20, 730 (1999).
22.C. L. Brooks, B. M. Pettit, and M. Karplus, J. Chem. Phys. 83, 5897 (1985);
22.P. Mark and L. Nilsson, J. Comput. Chem. 23, 1211 (2002);
22.J. Norberg and L. Nilsson, Biophys. J. 79, 1537 (2000);
22.M. Patra, M. Karttunen, T. Hyvönen, E. Falck, P. Lindqvist, and I. Vattulainen, Biophys. J. 84, 3636 (2003).
23.T. Darden, D. York, and L. Pedersen, J. Chem. Phys. 98, 10089 (1993);
23.U. Essmann, L. Perera, M. L. Berkowitz, T. Darden, H. Lee, and L. G. Pedersen, J. Chem. Phys. 103, 8577 (1995).
24.C. Sagui and T. Darden, J. Chem. Phys. 114, 6578 (2001).
25.Y. Shan, J. L. Klepeis, M. P. Eastwood, R. O. Dror, and D. E. Shaw, J. Chem. Phys. 122, 054101 (2005).
26.J. Vidgren, L. A. Svensson, and A. Liljas, Nature (London) 368, 354 (1994).
27.H. J. C. Berendsen, J. P. M. Postma, W. F. van Gunsteren, and J. Hermans, in Intermolecular Forces, edited by B. Pullman (Reidel, Dordrecht, 1981), 331.
View: Figures


Image of FIG. 1.

Click to view

FIG. 1.

Assignment of particle pairs to interaction boxes in the midpoint method. In this figure, the boxes are square with side length and . Each pair of particles separated by a distance less than is connected by a dashed line segment, with the “x” at its center lying in the box which will compute the interaction of that pair.

Image of FIG. 2.

Click to view

FIG. 2.

Import regions of (a) the two-dimensional midpoint method and (b) the two-dimensional analog of the HS method. The boxes are square with side length and . In each case, the interaction box is shown in light gray and the import region in dark gray.

Image of FIG. 3.

Click to view

FIG. 3.

Import regions of (a) the three-dimensional midpoint method, (b) the HS method, (c) the NT method, and (d) the ES method. In each case, the interaction box is shown in light gray and the import region in dark gray. The diagrams of the midpoint method, the HS method, and the ES method assume that the boxes are cubic with side length and that . The diagram of the NT method assumes the same values for and for box volume, but box aspect ratios have been optimized to minimize import volume.

Image of FIG. 4.

Click to view

FIG. 4.

A formulation of the two-dimensional midpoint method as a zonal method. (a) The interaction box (I) represents a single zone, and the import region is partitioned into eight zones. (b) An interaction schedule indicating which pairs of zones interact. An entry of 0 indicates that the zones in the corresponding row and column do not interact, while an entry of 1 indicates that they do.

Image of FIG. 5.

Click to view

FIG. 5.

Import volumes of several parallelization methods for pairwise interactions as a function of the number of processors , assuming a cubic global cell with a side length of and an interaction radius . Import volumes are represented relative to that of the HS method for any number of processors. The box aspect ratios of the NT method were optimized at each value of to minimize import volume, while the boxes are assumed to be cubic for the other methods. The midpoint and ES methods have the same import volume for all .

Image of FIG. 6.

Click to view

FIG. 6.

Number of interactions assigned to each processor for a biomolecular system by (a) the midpoint method and (b) a midpoint-ensured method. The system contained 50 846 atoms in a cubic global cell measuring per side, parallelized on 64 processors with .


Article metrics loading...



The evaluation of interactions between nearby particles constitutes the majority of the computational workload involved in classical molecular dynamics (MD) simulations. In this paper, we introduce a new method for the parallelization of range-limited particle interactions that proves particularly suitable to MD applications. Because it applies not only to pairwise interactions but also to interactions involving three or more particles, the method can be used for evaluation of both nonbonded and bonded forces in a MD simulation. It requires less interprocessor data transfer than traditional spatial decomposition methods at all but the lowest levels of parallelism. It gains an additional practical advantage in certain commonly used interprocessor communication networks by distributing the communication burden more evenly across network links and by decreasing the associated latency. When used to parallelize MD, it further reduces communication requirements by allowing the computations associated with short-range nonbonded interactions, long-range electrostatics, bonded interactions, and particle migration to use much of the same communicated data. We also introduce certain variants of this method that can significantly improve the balance of computational load across processors.


Full text loading...

This is a required field
Please enter a valid email address
752b84549af89a08dbdd7fdb8b9568b5 journal.articlezxybnytfddd
Scitation: The midpoint method for parallelization of particle simulations