SPMD Execution in the Presence of Dynamic Data Structures

Introduction A wide range of applications make use of regular dynamic data structures. Dynamic data structures are typically required because either the size of the data structure cannot be determined at compile-time or the form of the data structure depends upon the data that it contains which is not known until runtime. Some commonly used regular data structures include link lists, trees, and two dimensional meshes. Lists and trees are used by applications such as the N-body problem [10] and sparse Cholesky factorization [8, 11], dynamic meshes are used for solving partial differential equations and quad-trees are used by applications such as solid modeling, geographic information systems, and robotics [9]. Recently researchers have focussed on the translation of programs written using the shared-memory paradigm for parallel SPMD (single-program, multiple-data) execution on distributed-memory machines [1, 6]. In this approach the distribution of shared data arrays among th