Case Study · Parallel Computing
Parallel 3D Voxel Pattern Matching v1
Sequential, multithreaded and distributed 3D voxel search across volumetric CT datasets.
A parallel computing prototype for matching 4 × 4 × 4 voxel patterns within 3D CT datasets. The project compares sequential C, POSIX Threads and MPI implementations to evaluate correctness, scalability and performance across shared-memory and distributed-memory execution models.
- ROLE
- Lead Developer · Parallel Computing Engineer
- YEAR
- 2025
TECH_STACK
Technologies
CONTEXT
Technical context
Volumetric CT datasets contain large amounts of voxel data, making exhaustive 3D pattern matching computationally demanding. Searching every possible subvolume sequentially can become inefficient as dataset dimensions increase, particularly when the same matching operation must be repeated across multiple scans or target patterns. This project examines how shared-memory and distributed-memory parallelism can accelerate the search for fixed-size voxel patterns while maintaining consistent results. It compares sequential C, POSIX Threads and MPI implementations of the same 3D matching problem to evaluate workload distribution, synchronization overhead and scalability.
PROBLEM
Problem
Exhaustive 3D voxel pattern matching requires evaluating a large number of candidate subvolumes, which can lead to long execution times on larger CT datasets. A sequential implementation is straightforward and reliable, but it does not take advantage of modern multicore processors or distributed computing resources. The challenge was to preserve identical matching behavior across three execution models while dividing the workload efficiently and avoiding missed or duplicated regions. The solution also needed to handle thread and process coordination, volume partitioning, boundary conditions, result aggregation and performance measurement in a way that allowed fair comparison between sequential C, POSIX Threads and MPI.
OVERVIEW
Project overview
The project evaluates three implementations of the same 3D voxel pattern-matching problem: a sequential C baseline, a shared-memory POSIX Threads version and a distributed-memory MPI version.
Each implementation searches volumetric CT data for occurrences of a fixed 4 × 4 × 4 voxel pattern by moving a three-dimensional comparison window through every valid position in the dataset.
The sequential implementation provides the reference behavior used to validate correctness and measure baseline execution time before introducing parallel processing.
The POSIX Threads implementation divides the search space among multiple worker threads that operate on the same shared volume, allowing independent regions to be processed concurrently with limited synchronization.
The MPI implementation partitions the workload across separate processes, distributes the required data and combines partial match results after all assigned regions have been evaluated.
Boundary regions are handled carefully to prevent candidate patterns located near partition edges from being skipped or counted incorrectly.
All versions use equivalent comparison logic so their results can be validated directly and their execution times compared fairly.
The resulting structure supports analysis of speedup, scalability, workload balance and the overhead introduced by thread coordination and inter-process communication.
The project provides a practical comparison of sequential, shared-memory and distributed-memory computing applied to a real three-dimensional data-processing task.
APPROACH
Technical approach
- Implemented a sequential C version to establish a correctness and performance baseline.
- Designed a 3D sliding-window search that evaluates every valid 4 × 4 × 4 candidate region within the CT volume.
- Kept the voxel comparison logic identical across all implementations to ensure fair result validation.
- Developed a POSIX Threads version that partitions the search space across multiple CPU threads in shared memory.
- Assigned independent voxel ranges to worker threads to minimize synchronization overhead during matching.
- Implemented thread-safe aggregation of detected pattern locations and total match counts.
- Developed an MPI version that distributes sections of the 3D dataset across multiple processes.
- Handled partition boundaries so patterns spanning adjacent process regions are not missed.
- Collected and merged partial results from MPI processes into a unified final output.
- Measured execution time across sequential, multithreaded and distributed implementations.
- Compared scalability, speedup and overhead at different thread and process counts.
- Validated that all three implementations produce consistent matching results.
FOCUS
Technical focus
- Parallel Algorithm Design
- 3D Voxel Pattern Matching
- Sequential Performance Baseline
- Shared-Memory Parallelism
- POSIX Threads
- Distributed-Memory Processing
- MPI Workload Distribution
- Search-Space Partitioning
- Boundary Handling
- Thread and Process Coordination
- Result Aggregation
- Load Balancing
- Performance Benchmarking
- Speedup and Scalability Analysis
- Parallel Overhead Evaluation
- Correctness Validation
ARCHITECTURE
Architecture notes
- The project is organized into three independent implementations that share the same voxel-matching logic and input data format.
- The sequential C implementation acts as the reference architecture for validating correctness and measuring baseline execution time.
- The search operates as a three-dimensional sliding window over every valid position in the CT volume.
- Each candidate region is compared against a fixed 4 × 4 × 4 voxel pattern using identical comparison rules across all versions.
- The POSIX Threads implementation uses a shared-memory architecture in which worker threads access the same voxel dataset.
- The 3D search space is partitioned into independent ranges and assigned to threads for concurrent processing.
- Thread-local partial results are combined after execution to reduce synchronization during the main search loop.
- The MPI implementation uses a distributed-memory architecture with separate processes and independent address spaces.
- The global workload is divided among MPI ranks, with each process evaluating its assigned portion of the search space.
- Partition overlap or boundary-aware indexing is used to preserve candidate regions that extend across process boundaries.
- Partial match counts and detected positions are returned to the root process and merged into the final result.
- Execution timing is measured separately for each implementation to support direct performance comparison.
- The architecture keeps input handling, pattern comparison and output semantics consistent so differences primarily reflect the execution model.
- The modular structure supports future extensions such as larger patterns, additional datasets, alternative partitioning strategies and further low-level optimization.
HIGHLIGHTS
Engineering highlights
- Three Consistent Implementations of the Same 3D Search Algorithm
- Sequential C Baseline for Correctness and Performance Comparison
- Parallel 4 × 4 × 4 Voxel Pattern Matching
- Shared-Memory Acceleration with POSIX Threads
- Distributed-Memory Processing with MPI
- Workload Partitioning Across Threads and Processes
- Boundary-Aware Search-Space Decomposition
- Consistent Matching Logic Across All Execution Models
- Thread-Local and Process-Local Result Aggregation
- Performance Benchmarking Across Different Levels of Parallelism
- Speedup and Scalability Evaluation
- Practical Comparison of Sequential, Multithreaded and Distributed Computing
- Architecture Prepared for Larger CT Datasets and Further Optimization
OUTCOME
Outcome
The project resulted in three functionally consistent implementations of the same 3D voxel pattern-matching algorithm: sequential C, POSIX Threads and MPI. Each version detects identical 4 × 4 × 4 patterns within volumetric CT datasets while using a different execution model. The comparison demonstrates how shared-memory multithreading and distributed-memory processing can reduce execution time compared with the sequential baseline, while also revealing the effects of workload partitioning, communication and coordination overhead. The project provides a practical foundation for further benchmarking, larger datasets and more advanced parallel optimization.