Document Type

Thesis

Date of Award

5-2015

School/College

College of Science, Engineering, and Technology (COSET)

Degree Name

MS in Computer Science

First Advisor

Professor L. Ghemri

Second Advisor

Professor Chirstopher J. Tymczak

Abstract

k dimensional trees are an important binary space partitioning data structure in computer science. The goal of this study is to build a parallel k dimensional tree in a distributed memory system to organize the problem domain of the renowned astrophysical simulation N Body problem. The N-Body problem states that a bounded system of N particles interact with each other under the influence of gravity and that these particles change their position continuously due to the force acting upon them. It provides an idea on how large scale structures like galaxies and other cosmological structures are formed. The goal of this work is to organize that system of particles into a data structure, a k-d tree that will enable efficient computation of the forces acting on these particles and their new positions in the system. Our program randomly generated initial conditions for N particles, that is their X, Y, Z coordinate as well as their mass. Then these particles were sorted following one axis in order to build the k-d tree. 1 2 We implemented a sequential version of k-d tree building for and performed benchmarking of this program and analyzed it using several methods that provided us with useful insight on how to improve of the running time of the program and we deemed it more efficient to incorporate parallelism. We have designed and implemented the parallel k-d tree in a distributed memory. ,- Since the construction of k-d tree requires the splitting of search space, we have applied two different methods to implement the k-d tree and decompose the problem space among participating processors: a) the parallel median method and b) the parallel sorting method. We tested our program on up to 512 processors and 64 million data points and measured the timing of the parallel program for both methods. The results are promising and show a linear speedup and efficiency for both methods; with the parallel median method showing a 450% speedup time improvement on the construction of parallel k-d tree. We also compared the two methods and the parallel median method outperforms the parallel sorting method for all test cases.

Download

Share

COinS