Parallel 3D Voxel Pattern Matching v1
Parallel 3D voxel processing with 64-bit pattern encoding, POSIX Threads, and MPI
A 3D voxel-pattern matching system comparing sequential, shared-memory, and distributed-memory approaches to exhaustive pattern matching.
- Role
- Software Engineer — Parallel Computing & Algorithms
- Year
- 2025
Technologies
Technical context
Matching repeated structures within large volumetric datasets requires substantial computation. Parallel execution offers different approaches to distributing this workload across shared-memory threads and independent processes, each with its own coordination and communication costs.
Problem
Process 1,048,576 voxel patterns extracted from a 3D CT volume and count every ordered pair of identical patterns. Implement the same matching task across sequential, multithreaded, and MPI execution models while managing workload partitioning and result aggregation.
Project overview
The system processes 64 slices of a 1024 × 1024 CT volume, applies a binary threshold, and divides the data into 1,048,576 non-overlapping 4 × 4 × 4 patterns. Each block is represented by a 64-bit mask, allowing pattern equality to be evaluated through integer comparison. The original algorithm counts matching ordered pairs using exhaustive comparisons.
Three implementations explore different approaches to executing this workload. The sequential version performs comparisons in a single process, the POSIX Threads version partitions outer-loop iterations across shared-memory workers, and the MPI version distributes comparison ranges across processes using broadcast and reduction operations.
Technical approach
- Partition the CT volume into non-overlapping 4 × 4 × 4 blocks and apply binary thresholding
- Encode each 64-voxel pattern as a compact uint64_t bitmask
- Implement a sequential baseline using exhaustive pairwise comparisons
- Parallelize independent comparison ranges using POSIX Threads and thread-local counters
- Distribute comparison ranges across MPI processes and aggregate partial results through collective communication
Technical focus
- Parallel algorithm design and workload decomposition
- Shared-memory multithreading and synchronization
- Distributed-memory processing and MPI communication
- Binary data representation and exhaustive pattern matching
- Execution-time measurement and computational complexity
Architecture notes
- Three implementations processing the same 64-slice CT volume and fixed-size voxel blocks
- Sequential baseline using uint64_t pattern masks and quadratic pairwise comparison
- POSIX Threads workers operating on shared bitmask data with local match counters
- Mutex-protected aggregation of thread results after independent computation
- MPI architecture broadcasting encoded patterns, partitioning comparison ranges, and reducing partial counts
Engineering highlights
- Processing of 1,048,576 voxel patterns extracted from a 64 MiB CT volume
- Compact 64-bit encoding of thresholded 4 × 4 × 4 voxel structures
- Three implementations spanning sequential, shared-memory, and distributed-memory execution
- Thread-local counting with a single synchronized update per worker
- MPI-based data distribution and collective aggregation of matching-pair counts
Outcome
Implemented three execution models for exhaustive 3D voxel matching: sequential C, shared-memory POSIX Threads, and distributed-memory MPI. The implementations establish a common computational task with explicit workload partitioning, result aggregation, and execution-time instrumentation.