M-Tree: A parallel abstract data type for block-irregular adaptive applications

Abstract. This paper describes an abstract data type called M-Tree | a generalization of a quadtree which captures both the data struc-ture and computational structure common to many adaptive problems in science and engineering. It is equipped with a rich set of access func-tions including higher-order operators describing commonly used com-putational patterns in parallel adaptive computations. This provides a uniform high level abstraction of a wide range of applications including adaptive mesh renement and adaptive particle simulation and thus en-ables such applications to be constructed systematically and eciently. We present examples in which an M-tree is used to solve both an adap-tive heat- ow problem and N-body particle simulation. The structured abstraction of commonly-occurring computation patterns in the applica-tion 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.