Parallelisation of ConTree
Parallelized ConTree, an optimal decision tree algorithm, utilizing OpenMP and CUDA for CPU and GPU acceleration.
TL;DR: Analyzed the performance bottlenecks of the ConTree optimal decision tree builder and engineered a hybrid CPU/GPU parallelization strategy using OpenMP and CUDA to accelerate its processing of continuous numeric data.
Technologies & Methodology
- Software & Frameworks: C++, OpenMP, NVIDIA CUDA, CMake.
- Algorithms: Optimal Decision Trees (ODT), Dynamic Programming, Branch-and-Bound (BnB).
- Profiling Tools:
perf, CLion Profiler (WSL Environment).
Key Contributions & Results
- Profiled the original ConTree implementation to identify that the specialized solver, specifically the depth-one linear data scan, consumed up to 97% of CPU time.
- Engineered a hybrid parallelization architecture leveraging OpenMP for multi-core task parallelism across search tree features and CUDA for high-throughput GPU data parallelism.
- Re-architected the host dataset memory layout into a flattened, contiguous Structure of Arrays (SoA) format and managed a CUDA stream queue (FIFO) to eliminate redundant
cudaMemcpyoverheads. - Developed a 4-stage CUDA kernel (Local Histograms, Global Scan, Split Evaluation, Global Reduction) to rapidly evaluate optimal split thresholds directly on the GPU.
- Implemented dynamic thread allocation logic to optimize inner and outer threading configurations based on dataset instance size and available hardware resources.
- Successfully scaled execution across large datasets, demonstrating a significant reduction in computational latency for depth-two node searches.
Reference
This project is an optimization and parallelization of the original ConTree algorithm introduced in:
Briţa, Cătălin E., Jacobus G. M. van der Linden, and Emir Demirović. “Optimal Classification Trees for Continuous Feature Data Using Dynamic Programming with Branch-and-Bound.” In Proceedings of AAAI-25 (2025). [View PDF on arXiv]