Abstract
This paper describes an abstract data type called M-Tree — a generalization of a quadtree which captures both the data structure and computational structure common to many adaptive problems in science and engineering. It is equipped with a rich set of access functions including higher-order operators describing commonly used computational patterns in parallel adaptive computations. This provides a uniform high level abstraction of a wide range of applications including adaptive mesh refinement and adaptive particle simulation and thus enables such applications to be constructed systematically and efficiently. We present examples in which an M-tree is used to solve both an adaptive heat-flow problem and N-body particle simulation. The structured abstraction of commonly-occurring computation patterns in the application provides us with the opportunity to investigate various approaches to load balancing and communication minimization using caching and other techniques. These optimizations are applicable to other problems with a similar structure.
Qian Wu is now with CRAM, 40 High Street, Wimbledon Village, London, UK.
Chapter PDF
Similar content being viewed by others
References
J. Barnes and P. Hut. A hierarchical O(N log N) force-calculation algorithm. Nature, 324(4), December 1986.
Andrew J. Bennett and Paul H. J. Kelly. Efficient shared-memory support for parallel graph reduction. Future Generation Computer Systems, 1997. To appear.
Simon Boothroyd. Galaxy simulation on the AP1000, 1996. MEng Dissertation, Department of Computing, Imperial College.
G. H. Botorog and H. Kuchen. Algorithmic skeletons for adaptive multigrid algorithms. In Proceedings of IRREGULAR'95, LNCS 980. Springer-Verlag, 1995.
G.F. Carey, M.Shaama, and K.C.Wang. A class of data structures for 2-d and 3-d adaptive mesh refinement. International Journal for numerical methods in Engineering, 26, 1988.
K.M. Chandy and C. Kesselman. Compositional C++: Compositional parallel programming. Technical report, California Institute of Technology, 1992. Technical Report Caltech CS-TR-92-13.
K.M. Chandy, R. Manohar, B.L. Massingill, and D.I. Meiron. Integrating task and data parallelism with the collective communication archetype. Technical report, California Institute of Technology, 1994. Technical Report Caltech CS-TR-94-08.
J. Darlington, A.J. Field, P.G. Harrison, P.H.J. Kelly, D.W.N. Sharp, Q. Wu, and R.L. While. Parallel programming using skeleton functions. In Parallel Architectures And Languages, Europe: PARLE 93. Springer-Verlag, 1993.
Department of Computer Science, Computer Sciences Laboratory, The Australian National University. MPI: User's Guide, 1994.
D.J. Edelsohn. Hierarchical tree-structures as adaptive meshes. Technical Report SCCS-193, Syracuse Center for Computational Science, NY, 1991.
Ian Foster, Robert Olson, and Steven Tuecke. Productive parallel programming: The PCN approach. Scientific Programming, 1(1), 1992.
Paul H.J. Kelly. Functional Programming for Loosely-coupled Multiprocessors. Pitman/MIT Press, 1989.
S. R. Kohn. A Parallel Software Infrastructure for Dynamic Block-Irregular Scientific Calculations. PhD thesis, Dept. of Computer Science and Engineering, Univ. of California, San Diego, 1995.
J. K. Salmon M. S. Warren. A parallel hashed oct-tree n-body algorithm. In Proceedings of SuperComputing 93, 1993.
M. Parashar and J. C. Browne. Dagh: A data management infrastructure for parallel adaptive mesh refinement techniques. Technical report, Dept. of Computer Science, Univ. of Texas at Austin, 1995. Premiminary Users Guide.
W. H. Press, B. P. Flannery, S. A. Teukolsky, and W. T. Vetterling. Numerical Recipes in C. Cambridge University Press, Cambridge, second edition, 1992.
H. Samet. The design and analysis of spatial data structures. MIT Press, 1990.
Mario Südholt. Data distribution algebras — a formal basis for programming using skeletons. In E.-R. Olderog, editor, Programming Concepts, Methods and Calculi, pages 19–38. North-Holland, June 1994.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wu, Q., Field, A.J., Kelly, P.H.J. (1997). M-Tree: A parallel abstract data type for block-irregular adaptive applications. In: Lengauer, C., Griebl, M., Gorlatch, S. (eds) Euro-Par'97 Parallel Processing. Euro-Par 1997. Lecture Notes in Computer Science, vol 1300. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0002795
Download citation
DOI: https://doi.org/10.1007/BFb0002795
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-63440-9
Online ISBN: 978-3-540-69549-3
eBook Packages: Springer Book Archive
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.