Abstract
This thesis presents an out-of-core parallel formulation of the Barnes-Hut method. When the data of an application is too large to fit in the main memory, the conven-tional method is to use virtual memory to support out of core computation. However, we will show in our experimental results that virtual memory is not an effective scheme to support the out-of-core computation of dynamically-linked quadtree structures. The underlying architecture of this work is based on a shared nothing workstation cluster connected via high-speed network. The experiment is conducted on a 16-node IBM SP-2 and an 8-node DEC Farms located at National High-Performance Com-puting Center. We demonstrate a novel scheme to carry out out-of-core computation with Barnes-Hut N-body method. The data structure used in our study is Quadtree structure, the programming model is SPMD model, and the communication is done via MPI (Message Passing Interface) library. Our results show that virtual memory will have thrashing behaviors in supporting out-of-core quadtree computation for N-Body problems, while the out-of-core model and mechanism proposed in this thesis can support the out-of-core computation efficiently. The time taken by out-of-core version grows smoothly as the number of bodies increases. We report experimental evaluation of this scheme on IBM SP2 up to 16 processors and 8-node DEC Alpha Farms. In addition, we also compare the performance of two file systems, NFS and PIOFS, on IBM SP2, and model the performance behavior of our scheme.