This project implements a parallel Ball Tree construction algorithm in a Distributed-Memory environment. The implementation focuses on problem decomposition, synchronization concerns, and load balancing to improve performance.
- Clara Gil, Grade: 17/20
- José Brás, Grade: 17/20
- Miguel Barros, Grade: 19/20
The project aims to efficiently construct a Ball Tree data structure in a distributed memory setting. The algorithm splits the point set among available processes, enabling the handling of larger problem instances that do not fit on a single machine.
- Problem decomposition for distributing workload among processes
- Synchronization mechanisms for efficient parallel computation
- Load balancing strategies to optimize performance
The parallel implementation shows significant speedup compared to the sequential version, with a 36% improvement for larger inputs. The speedup scales with the number of processes up to a certain point, after which communication overhead limits further gains.
-
Clone the repository to your local machine.
-
Compile the project using the provided Makefile. make
-
Run the executable with the desired input parameters. mpirun -np <num_processes> ./ball_tree_construction <input_file>
Example: mpirun -np 4 ./ball_tree_construction input_data.txt
- View the output results and performance metrics.
ball_tree_construction.cpp
: Main source code file for the Ball Tree construction algorithm.Makefile
: Makefile for compiling the project.input_data.txt
: Sample input data file.
- OpenMPI
- C/C++ compiler
For more details on the project implementation, performance analysis, and algorithm insights, refer to the full report g29report.pdf.