Parallel 3D Voxel Pattern Matching v2
High-performance voxel processing with 64-bit pattern encoding, radix sorting, and parallel computation
An optimized 3D voxel-pattern matching system combining efficient data representation, radix-based algorithms, and shared- and distributed-memory parallelism.
- Role
- Software Engineer — Algorithms & Parallel Computing
- Year
- 2026
Technologies
Project media
Technical context
Processing large volumetric datasets presents significant computational challenges when identifying repeated spatial patterns. Direct pairwise comparison becomes increasingly expensive as the number of patterns grows, making data representation and algorithm selection critical to performance.
Problem
Count every ordered pair of matching 4 × 4 × 4 voxel patterns across 1,048,576 blocks without relying on approximately 1.1 trillion pairwise comparisons, while preserving identical results across sequential, multithreaded, and MPI implementations.
Project overview
The system processes 64 slices of a 1024 × 1024 CT volume, converting each non-overlapping 4 × 4 × 4 block into a compact 64-bit pattern. An eight-pass LSD radix sort groups identical masks, allowing ordered matches to be counted in a linear scan using the frequency of each pattern instead of comparing every pair.
Three implementations explore different execution models. The sequential version establishes the optimized reference algorithm, POSIX Threads parallelizes mask generation and radix sorting through synchronized workers, and MPI distributes computation across processes using local compression, hash-based ownership, and collective communication.
Technical approach
- Encode thresholded 4 × 4 × 4 voxel blocks directly as 64-bit bitmasks
- Replace quadratic comparisons with eight-pass LSD radix sorting and linear run aggregation
- Implement an optimized sequential baseline and parallel shared-memory processing with POSIX Threads
- Distribute pattern generation, sorting, and compressed-count aggregation across MPI processes
- Benchmark multiple execution configurations and validate matching results across repeated runs
Technical focus
- Algorithmic complexity reduction and compact data representation
- Shared-memory parallelism and synchronization
- Distributed-memory computation and MPI communication
- Memory layout, radix sorting, and workload partitioning
- Performance benchmarking and parallel scalability analysis
Architecture notes
- Contiguous 64 MiB working volume with direct 64-bit voxel-pattern encoding
- Eight stable radix passes followed by linear aggregation of equal-mask runs
- Pthreads workers using local histograms, coordinated bucket offsets, and barriers
- MPI processing with local sorting, compressed mask counts, and hash-based ownership redistribution
- MPI_Alltoallv exchanges and MPI_Reduce aggregation with computation timing separated from disk loading
Engineering highlights
- Replaced approximately 1.1 trillion pairwise comparisons with a radix-based processing pipeline
- Processed 1,048,576 voxel patterns with identical results across all 300 recorded benchmark runs
- Achieved a 12.105 ms median and 3.95× speedup using 16 POSIX threads
- Achieved a 29.341 ms median and 1.63× speedup using eight MPI processes
- Identified synchronization and communication overhead as key limits to further parallel scaling
Outcome
All 300 recorded benchmark runs produced the same result of 970,777,711,592 ordered matching pairs. The 16-thread POSIX Threads implementation achieved a median computation time of 12.105 ms, delivering a 3.95× speedup over the optimized sequential baseline. The best MPI configuration reached 29.341 ms with eight processes, achieving a 1.63× speedup.