A parallel hashed Oct-Tree N-body algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parallel hashed Oct-Tree N-body algorithm

Full text

Pdf (1.13 MB)

Source

Conference on High Performance Networking and Computing archive
Proceedings of the 1993 ACM/IEEE conference on Supercomputing table of contents

Portland, Oregon, United States

Pages: 12 - 21

Year of Publication: 1993

ISBN:0-8186-4340-4

Authors

M. S. Warren	Theoretical Astrophysics, Mail Stop B288, Los Alamos National Laboratory, Los Alamos, NM
J. K. Salmon	Physics Department, 206-49, California Institute of Technology, Pasadena, CA

Sponsor

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 24, Downloads (12 Months): 137, Citation Count: 56

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/169627.169640 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A.W. Appel, "An efficient program for many-body simulation," SlAM J. Computing, vot. 6, p. 85, 1985.
	2	Klaas Esselink, The order of Appel's algorithm, Information Processing Letters, v.41 n.3, p.141-147, March 6, 1992 [doi>10.1016/0020-0190(92)90043-U]
	3	J. Barnes and P. Hut, "A hierarchical O(Nlog~ forcecalculation algorithm," Nature, vol. 324, p. 446, 1986.
	4	L. Greengard , V. Rokhlin, A fast algorithm for particle simulations, Journal of Computational Physics, v.73 n.2, p.325-348, December 1, 1987 [doi>10.1016/0021-9991(87)90140-9]
	5	L. Greengard and W. D. Gropp, "A parallel version of the fast muttipole method," Computers Math. Applic, vol. 20, no. 7, pp. 63-7t, 1990.
	6	Feng Zhao , S. Lennart Johnsson, The parallel multipole method on the connection machine, SIAM Journal on Scientific and Statistical Computing, v.12 n.6, p.1420-1437, Nov. 1991 [doi>10.1137/0912077]
	7	K. E. Schmidt and M. A. Lee, "Implementing the fast multipole method in three dimensions," J. Stat. Phys., vol. 63, no. 5/6, pp. 1223-1235, 1991.
	8	I.A. Board, J. W. Causey, J. E Leathrum, A. Windemuth, and K. Schulten, "Accelerated molecular dynamics simulation with the parallel fast multipole algorithm," Chem. Phys. Let., vol. 198, p. 89, 1992.
	9	H.-Q. Ding, N. Karasawa, and W. Goddard, "Atomic level simulations of a million particles: The cell multipole method for coulomb and london interactions,"J, of Chemical Physics, vol. 97, pp. 4309-4315, 1992.
	10	John K. Salmon , Michael S. Warren, Skeletons from the treecode closet, Journal of Computational Physics, v.111 n.1, p.136-155, March 1994 [doi>10.1006/jcph.1994.1050]
	11	John K. Salmon, Parallel hierarchical N-body methods, California Institute of Technology, Pasadena, CA, 1992
	12	M. S. Warren , J. K. Salmon, Astrophysical N-body simulations using hierarchical tree data structures, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.570-576, November 16-20, 1992, Minneapolis, Minnesota, United States
	13	M. S. Warren, P. J. Quinn, J. K. Salmon, and W. H. Zurek, "Dark halos formed via dissipationless collapse: I. Shapes and alignment of angular momentum," Ap. J., vol. 399, pp. 405-425, 1992.
	14	W. H. Zurek, P. J. Quinn, j. K. Salmon, and M. S. Warren, "Large Scale Structure after COBE: Peculiar Velocities and Correlations of Dark Matter Halos in a CDM Universe,"Nature, 1993. (submitted)
	15	J. P. Singh, J. L. Hennessy, and A. Gupta, "Implications of hierarchical N-body techniques for multiprocessor architectures," Tech. Rep. CSL-TR-92-506, Stanford University, 1992.
	16	Jaswinder Pal Singh , Chris Holt , Takashi Totsuka , Anoop Gupta , John Hennessy, Load balancing and data locality in adaptive hierarchical N-body methods: Barnes-Hut, fast multipole, and radiosity, Journal of Parallel and Distributed Computing, v.27 n.2, p.118-141, June 1995 [doi>10.1006/jpdc.1995.1077]
	17	S. Bhatt, M. Chen, C. Y. Lin, and P. Liu, "Abstractions for parallel N-body simulations," Tech. Rep. DCS/TR-895, Yale University, 1992.
	18	Hanan Samet, The design and analysis of spatial data structures, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
	19	J. E. Barnes, "An efficient N-body algorithm for a finegrain parallel computer," in The Use of Supercomputers in Stellar Dynamics (P. Hut and S. McMillan, eds.), (New York), pp. 175-180, Springer-Verlag, 1986.
	20	N. Engheta, W. D. Murphy, V. Rokhlin, and M. S. Vassiliou, "The fast multipole method (FMM) for electromagnetic scattering problems," IEEE Transactions on Antennas and Propagation, vol. 40, no. 6, pp. 634-642, 1992.
	21	J. K. Salmon, M. S. Warren, and G. S. Winckelmans, "Fast parallel tree codes for gravitational and fluid dynamical N- body problems," International Journal of Supercomputing Applications, 1993. (submitted)

CITED BY 56

	M. Vikram , B. Shanker, Fast evaluation of time domain fields in sub-wavelength source/observer distributions using accelerated Cartesian expansions (ACE), Journal of Computational Physics, v.227 n.2, p.1007-1023, December, 2007
	John Mellor-Crummey , David Whalley , Ken Kennedy, Improving Memory Hierarchy Performance for Irregular Applications Using Data and Computation Reorderings, International Journal of Parallel Programming, v.29 n.3, p.217-247, June 2001
	Simon Peyton Jones , Alastair Reid , Fergus Henderson , Tony Hoare , Simon Marlow, A semantics for imprecise exceptions, ACM SIGPLAN Notices, v.34 n.5, p.25-36, May 1999
	Ananth Grama , Vipin Kumar , Ahmed Sameh, Parallel matrix-vector product using approximate hierarchical methods, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.75-es, December 04-08, 1995, San Diego, California, United States
	J. Waltz , G. L. Page , S. D. Milder , J. Wallin , A. Antunes, A performance comparison of tree data structures for N-body simulation, Journal of Computational Physics, v.178 n.1, p.1-14, May 1, 2002
	Y. Charlie Hu , S. Lennart Johnsson , Shang-Hua Teng, High performance Fortran for highly irregular problems, ACM SIGPLAN Notices, v.32 n.7, p.13-24, July 1997
	Ananth Y. Grama , Vipin Kumar , Ahmed Sameh, Scalable parallel formulations of the Barnes-Hut method for n-body simulations, Proceedings of the 1994 conference on Supercomputing, p.439-448, December 1994, Washington, D.C., United States
	A. C. Calder , B. C. Curtis , L. J. Dursi , B. Fryxell , P. MacNeice , K. Olson , P. Ricker , R. Rosner , F. X. Timmes , H. M. Tufo , J. W. Turan , M. Zingale , G. Henry, High performance reactive fluid flow simulations using adaptive mesh refinement on thousands of processors, Proceedings of the 2000 ACM/IEEE conference on Supercomputing (CDROM), p.56-es, November 04-10, 2000, Dallas, Texas, United States
	Srinivas Aluru , G. M. Prabhu , John Gustafson, Truly distribution-independent algorithms for the N-body problem, Proceedings of the 1994 conference on Supercomputing, p.420-428, December 1994, Washington, D.C., United States
	Kenjiro Taura , Akinori Yonezawa, An effective garbage collection strategy for parallel programming languages on large scale distributed-memory machines, ACM SIGPLAN Notices, v.32 n.7, p.264-275, July 1997
	Dow-Yung Yang , Ananth Grama , Vivek Sarin , Naren Ramakrishnan, Compression of particle data from hierarchical approximate methods, ACM Transactions on Mathematical Software (TOMS), v.27 n.3, p.317-339, September 2001
	Collin McCurdy , John Mellor-Crummey, An evaluation of computing paradigms for N-body simulations on distributed memory architectures, ACM SIGPLAN Notices, v.34 n.8, p.25-36, Aug. 1999
	Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive array layouts and fast parallel matrix multiplication, Proceedings of the eleventh annual ACM symposium on Parallel algorithms and architectures, p.222-231, June 27-30, 1999, Saint Malo, France
	Jaswinder Pal Singh , John L. Hennessy , Anoop Gupta, Implications of hierarchical N-body methods for multiprocessor architectures, ACM Transactions on Computer Systems (TOCS), v.13 n.2, p.141-202, May 1995
	Karen Devine , Bruce Hendrickson , Erik Boman , Matthew St. John , Courtenay Vaughan, Design of dynamic load-balancing tools for parallel applications, Proceedings of the 14th international conference on Supercomputing, p.110-118, May 08-11, 2000, Santa Fe, New Mexico, United States
	Faith E. Sevilgen , Srinivas Aluru, A unifying data structure for hierarchical methods, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.24-es, November 14-19, 1999, Portland, Oregon, United States
	Xingbin Zhang , Andrew A. Chien, Dynamic pointer alignment: tiling and communication optimizations for parallel pointer-based computations, ACM SIGPLAN Notices, v.32 n.7, p.37-47, July 1997
	John Mellor-Crummey , David Whalley , Ken Kennedy, Improving memory hierarchy performance for irregular applications, Proceedings of the 13th international conference on Supercomputing, p.425-433, June 20-25, 1999, Rhodes, Greece
	Siddhartha Chatterjee , Vibhor V. Jain , Alvin R. Lebeck , Shyam Mundhra , Mithuna Thottethodi, Nonlinear array layouts for hierarchical memory systems, Proceedings of the 13th international conference on Supercomputing, p.444-453, June 20-25, 1999, Rhodes, Greece
	Ioana Banicescu , Susan Flynn Hummel, Balancing processor loads and exploiting data locality in N-body simulations, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.43-es, December 04-08, 1995, San Diego, California, United States
	Vivek Sarin , Ananth Grama , Ahmed Sameh, Analyzing the error bounds of multipole-based treecodes, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
	Srinivas Aluru , G. M. Prabhu , John Gustafson, Truly distribution-independent algorithms for the N-body problem, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Pangfeng Liu , Sandeep N. Bhatt, Experiences with Parallel N-Body Simulation, IEEE Transactions on Parallel and Distributed Systems, v.11 n.12, p.1306-1323, December 2000
	Yu Hu , S. Lennart Johnsson, A data-parallel implementation of O(N) hierarchical N-body methods, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.2-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	J. M. Malard , R. D. Stewart, Distributed dynamic hash tables using IBM LAPI, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-11, November 16, 2002, Baltimore, Maryland
	Bhanu Hariharan , Srinivas Aluru , Balasubramaniam Shanker, A scalable parallel fast multipole method for analysis of scattering from perfect electrically conducting surfaces, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-17, November 16, 2002, Baltimore, Maryland
	Sreekanth R. Sambavaram , Vivek Sarin , Ahmed Sameh , Ananth Grama, Multipole-based preconditioners for large sparse linear systems, Parallel Computing, v.29 n.9, p.1261-1273, September 2003
	Michael S. Warren , Eric H. Weigle , Wu-Chun Feng, High-density computing: a 240-processor Beowulf in one cubic meter, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-11, November 16, 2002, Baltimore, Maryland
	David Blackston , Torsten Suel, Highly portable and efficient implementations of parallel adaptive N-body methods, Proceedings of the 1997 ACM/IEEE conference on Supercomputing (CDROM), p.1-20, November 15-21, 1997, San Jose, CA
	Yudong Sun , Cho-Li Wang, Solving irregularly structured problems based on distributed object model, Parallel Computing, v.29 n.11-12, p.1539-1562, November/December 2003
	Siddhartha Chatterjee , Alvin R. Lebeck , Praveen K. Patnala , Mithuna Thottethodi, Recursive Array Layouts and Fast Matrix Multiplication, IEEE Transactions on Parallel and Distributed Systems, v.13 n.11, p.1105-1123, November 2002
	David S. Wise , Jeremy D. Frens , Yuhong Gu , Gregory A. Alexander, Language support for Morton-order matrices, ACM SIGPLAN Notices, v.36 n.7, p.24-33, July 2001
	Vijay Karamcheti , Andrew A. Chien, A hierarchical load-balancing framework for dynamic multithreaded computations, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-17, November 07-13, 1998, San Jose, CA
	Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
	John R. Pilkington , Scott B. Baden, Dynamic Partitioning of Non-Uniform Structured Workloads with Spacefilling Curves, IEEE Transactions on Parallel and Distributed Systems, v.7 n.3, p.288-300, March 1996
	Thomas Sterling , Daniel Savarese , Phillip Merkey , Kevin Olson, An empirical evaluation of the Convex SPP-1000 hierarchical shared memory system, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.214-223, June 27-29, 1995, Limassol, Cyprus
	Johan Steensland , Sumir Chandra , Manish Parashar, An Application-Centric Characterization of Domain-Based SFC Partitioners for Parallel SAMR, IEEE Transactions on Parallel and Distributed Systems, v.13 n.12, p.1275-1289, December 2002
	Srinivas Aluru , John Gustafson , G. M. Prabhu , Fatih E. Sevilgen, Distribution-Independent Hierarchical Algorithmsfor the N-body Problem, The Journal of Supercomputing, v.12 n.4, p.303-323, October 1998
	Ananth Y. Grama , Vipin Kumar , Ahmed Sameh, Scalable parallel formulations of the barnes-hut method for n-body simulations, Proceedings of the 1994 ACM/IEEE conference on Supercomputing, November 14-18, 1994, Washington, D.C.
	Ananth Grama , Vipin Kumar , Ahmed Sameh, Parallel hierarchical solvers and preconditioners for boundary element methods, Proceedings of the 1996 ACM/IEEE conference on Supercomputing (CDROM), p.34-es, January 01-01, 1996, Pittsburgh, Pennsylvania, United States
	Youssef M. Marzouk , Ahmed F. Ghoniem, K-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical N-body simulations, Journal of Computational Physics, v.207 n.2, p.493-528, 10 August 2005
	Karen D. Devine , Erik G. Boman , Robert T. Heaphy , Bruce A. Hendrickson , James D. Teresco , Jamal Faik , Joseph E. Flaherty , Luis G. Gervasio, New challanges in dynamic load balancing, Applied Numerical Mathematics, v.52 n.2-3, p.133-152, February 2005
	Ananth Y. Grama , Vivek Sarin, Impact of far-field interactions on performance of multipole-based preconditioners for sparse linear systems, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France
	Ioana Banicescu , Ricolindo L. Cariño , Jaderick P. Pabico , Mahadevan Balasubramaniam, Design and implementation of a novel dynamic load balancing library for cluster computing, Parallel Computing, v.31 n.7, p.736-756, July 2005
	Michael S. Warren , Timothy C. Germann , Peter S. Lomdahl , David M. Beazley , John K. Salmon, Avalon: an Alpha/Linux cluster achieves 10 Gflops for $15k, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-11, November 07-13, 1998, San Jose, CA
	Bhanu Hariharan , Srinivas Aluru, Efficient parallel algorithms and software for compressed octrees with applications to hierarchical methods, Parallel Computing, v.31 n.3+4, p.311-331, March/April 2005
	Jan F. Prins , Siddhartha Chatterjee , Martin Simons, Irregular computations in Fortran - expression and implementation strategies, Scientific Programming, v.7 n.3-4, p.313-326, August 1999
	Judith Hartmann , Andreas Krahnke , Christoph Zenger, Cache efficient data structures and algorithms for adaptive multidimensional multilevel finite element solvers, Applied Numerical Mathematics, v.58 n.4, p.435-448, April, 2008
	H. Carter Edwards, An HPC component for parallel, heterogeneous, and dynamic unstructured meshes, Proceedings of the 2007 symposium on Component and framework technology in high-performance and scientific computing, October 21-22, 2007, Montreal, Quebec, Canada
	William F. Mitchell, A refinement-tree based partitioning method for dynamic load balancing with adaptively refined grids, Journal of Parallel and Distributed Computing, v.67 n.4, p.417-429, April, 2007
	TIANKAI TU , DAVID R. O'HALLARON , OMAR GHATTAS, Scalable Parallel Octree Meshing for TeraScale Applications, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.4, November 12-18, 2005
	Ricolindo L. Cariño , Ioana Banicescu, A Load Balancing Tool for Distributed Parallel Loops, Cluster Computing, v.8 n.4, p.313-321, October 2005
	Michael S. Warren , Chris L. Fryer , M. Patrick Goda, The Space Simulator: Modeling the Universe from Supernovae to Cosmology, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.30, November 15-21, 2003
	Lexing Ying , George Biros , Denis Zorin , Harper Langston, A New Parallel Kernel-Independent Fast Multipole Method, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.14, November 15-21, 2003
	Ioana Banicescu , Ricolindo L. Carino , Jaderick P. Pabico , Mahadevan Balasubramaniam, Performance evaluation of a dynamic load-balancing library for cluster computing, International Journal of Computational Science and Engineering, v.1 n.2-4, p.118-133, May 2005
	Umit V. Catalyurek , Erik G. Boman , Karen D. Devine , Doruk Bozdağ , Robert T. Heaphy , Lee Ann Riesen, A repartitioning hypergraph model for dynamic load balancing, Journal of Parallel and Distributed Computing, v.69 n.8, p.711-724, August, 2009