Parallel 2D DCT Image Processing

A comprehensive performance analysis and implementation of 2D Discrete Cosine Transform (DCT) for image processing, featuring three variants: Sequential, OpenMP Parallel, and CUDA GPU implementations.

📋 Overview

This project implements block-based 2D DCT processing for grayscale images, comparing performance across CPU (sequential and OpenMP parallel) and GPU (CUDA) implementations. The study demonstrates dramatic performance improvements through parallelization and GPU acceleration, achieving up to 146× speedup for large images.

Documentation

For a detailed technical analysis including:

• In-depth discussion of optimization strategies
• Comprehensive performance analysis with statistical metrics

Please refer to DCT_Parallel_Report.pdf which contains the full academic report of this work.

Key Features

• ✅ Three implementation variants with different parallelization strategies
• ✅ Highly optimized CUDA implementation with shared/constant memory
• ✅ OpenMP parallel implementation with dynamic scheduling
• ✅ Comprehensive benchmarking across multiple block sizes (1, 2, 4, 8, 16, 32)
• ✅ Automated benchmark script with CSV output and visualization
• ✅ Detailed performance analysis and recommendations

🚀 Performance Highlights

Image Size	Implementation	Block Size	Execution Time	Speedup
8000×8000	Sequential	32	361.7s	1.0×
8000×8000	OpenMP	32	53.9s	6.7×
8000×8000	CUDA	32	2.5s	146×
1000×1000	OpenMP	4	17ms	12.2×
1000×1000	CUDA	32	108ms	56×

🛠️ Requirements

Hardware

• CPU: Intel Core i9-13900H (14 cores, 20 threads, up to 5.4 GHz)
• GPU: NVIDIA GeForce RTX 4060 Laptop (3,072 CUDA cores, Compute Capability 8.9, 8 GB GDDR6)
• RAM: 32 GB DDR5-5200

Software

• Compiler: g++ with C++11 support and OpenMP
• CUDA: CUDA Toolkit 11.0 or higher
• OpenCV: Version 4.x for image I/O
• CMake: Version 3.10 or higher
• Python 3: For benchmark visualization (with pandas, matplotlib)

📦 Installation

1. Clone the repository

git clone https://github.com/lapemaya/DCT-parallel.git
cd DCT-parallel

2. Install dependencies

Ubuntu/Debian

sudo apt-get update
sudo apt-get install build-essential cmake
sudo apt-get install libopencv-dev
sudo apt-get install nvidia-cuda-toolkit

Python dependencies (for visualization)

pip install pandas matplotlib numpy

3. Build the project

mkdir -p cmake-build-debug
cd cmake-build-debug
cmake ..
make

This will generate three executables:

• DCTSeq - Sequential implementation
• DCTPar - OpenMP parallel implementation
• DCTCuda - CUDA GPU implementation

🎯 Usage

Basic Execution

Run each implementation with an input image and block size:

# Sequential
./cmake-build-debug/DCTSeq <image.png> <blocksize>

# OpenMP Parallel
./cmake-build-debug/DCTPar <image.png> <blocksize>

# CUDA GPU
./cmake-build-debug/DCTCuda <image.png> <blocksize>

Example:

./cmake-build-debug/DCTCuda place.png 16

Automated Benchmarking

Run comprehensive benchmarks across all block sizes:

./benchmark.sh <image.png> <output_directory>

Example:

./benchmark.sh place.png place/

This will:

1. Run all three implementations with block sizes: 1, 2, 4, 8, 16, 32
2. Generate benchmark_results.csv and benchmark_results.txt
3. Create visualization plots using plot_results.py
4. Output:
   • benchmark_times.png - Execution time comparison
   • benchmark_speedup.png - Speedup comparison

Visualization Only

If you already have benchmark results, generate plots:

python3 plot_results.py <benchmark_results.csv>

📊 Implementation Details

Sequential Implementation (DCTSeq.cpp)

Features:

• Single-threaded baseline
• Precomputed lookup tables for alpha and cosine values
• Direct pointer access for cache efficiency
• Zero-padding for boundary blocks

Best Use Cases:

• Educational purposes and debugging
• Embedded systems without OpenMP/CUDA support

OpenMP Parallel Implementation (DCTPar.cpp)

Features:

• #pragma omp parallel with collapse(2) for nested loop parallelization
• Dynamic scheduling (schedule(dynamic)) for load balancing
• nowait clause to eliminate implicit barriers
• Thread-local block buffers to avoid allocation overhead
• Atomic progress tracking

Optimizations:

• Precomputed lookup tables (shared read-only)
• Cache-friendly data layout (row-major order)
• Thread-local buffers to reduce false sharing

Best Use Cases:

• Small images (<1 megapixel) with any block size
• Medium images (1-4 megapixels) with block sizes 1-8
• CPU-only systems or real-time low-latency scenarios (<10ms)

CUDA GPU Implementation (DCTCuda.cu)

Features:

• Highly optimized GPU kernels
• Grid configuration: 1D grid with one block per image block
• Thread configuration: 2D threads (N×N) per block

Memory Hierarchy Optimizations:

• Constant Memory: Read-only alpha and cosine tables (broadcast to all threads)
• Shared Memory: Each thread block loads its image block + lookup tables into shared memory
• Coalesced Access: Threads with consecutive IDs access consecutive memory addresses
• Cooperative Loading: All threads cooperatively load shared data in parallel
• Float Precision: Uses float (32-bit) for 2× throughput

Best Use Cases:

• Large images (>4 megapixels) with any block size ≥4
• Medium images (1-4 megapixels) with block sizes ≥16
• Batch processing (amortize initialization overhead)
• Maximum throughput requirements (100-146× speedup possible)

📈 Performance Analysis

Scaling Patterns

Large Images (>4 megapixels)

• CUDA dominates across all block sizes ≥4
• Maintains nearly constant execution time (~1-2.5s)
• GPU's 3,072 cores effectively mask O(N⁴) complexity
• Recommendation: Use CUDA exclusively

Medium Images (1-4 megapixels)

• OpenMP superior for block sizes 1-8 (lower overhead)
• CUDA dominant for block sizes ≥16 (computational intensity overcomes overhead)
• Crossover point around block size 8-16
• Recommendation: Choose based on block size

Small Images (<1 megapixel)

• OpenMP optimal for nearly all scenarios
• CUDA's fixed overhead (~70-100ms) cannot be amortized
• GPU underutilization (<1% of SMs active)
• Recommendation: Use OpenMP unless block size = 32 and GPU already initialized

Key Findings

• Sequential: Optimal block size is always 2 (balance between block count and per-block complexity)
• OpenMP: Consistent 7-12× speedups, bounded by memory bandwidth and cache coherence
• CUDA: Exponential speedup scaling with block size for large images (0.64× to 146×)

📁 Project Structure

.
├── CMakeLists.txt           # CMake build configuration
├── DCTSeq.cpp              # Sequential implementation
├── DCTPar.cpp              # OpenMP parallel implementation
├── DCTCuda.cu              # CUDA GPU implementation
├── benchmark.sh            # Automated benchmarking script
├── plot_results.py         # Python visualization script
├── dct_report.tex          # Comprehensive LaTeX report (updated Jan 2026)
├── README.md               # This file
├── bear.png                # Test image (500×500)
├── banana.png              # Test image (1000×1000)
├── place.png               # Test image (8000×8000)
├── bear/                   # Benchmark results for bear.png
│   ├── benchmark_results.csv
│   ├── benchmark_results.txt
│   ├── benchmark_times.png
│   └── benchmark_speedup.png
├── banana/                 # Benchmark results for banana.png
│   ├── benchmark_results.csv
│   ├── benchmark_results.txt
│   ├── benchmark_times.png
│   └── benchmark_speedup.png
└── place/                  # Benchmark results for place.png
    ├── benchmark_results.csv
    ├── benchmark_results.txt
    ├── benchmark_times.png
    └── benchmark_speedup.png

🔬 Optimization Techniques

CPU Optimizations

1. Precomputed Lookup Tables: Eliminate expensive trigonometric function calls
2. Direct Pointer Access: Reduce bounds checking overhead
3. Cache-Friendly Layout: Row-major storage matching access pattern
4. Thread-Local Buffers: Avoid allocator contention and false sharing
5. Dynamic Scheduling + Nowait: Better load balancing, reduced synchronization

GPU Optimizations

1. Constant Memory: Broadcast-optimized access for lookup tables (near L1-cache performance)
2. Shared Memory Blocking: Reduce global memory latency from ~400 to ~20 cycles
3. Coalesced Memory Access: Full memory burst utilization (128 bytes per transaction)
4. Cooperative Loading: Maximize bandwidth during data transfer phase
5. Float Precision: 2× throughput on CUDA cores
6. Occupancy Optimization: Validate shared memory limits before launch

🎓 Academic Report

A comprehensive LaTeX report (dct_report.tex) is included with detailed analysis:

• Methodology: Algorithm design and block-based processing approach
• Hardware/Software Configuration: Complete system specifications and test environment
• Implementation Details: Line-by-line code explanation for all three variants
• Optimization Techniques: CPU and GPU-specific optimizations with justifications
• Performance Analysis: Comprehensive results with tables, graphs, and visualizations
• Per-Image Analysis: Detailed comparison across different image sizes (500×500, 1000×1000, 8000×8000)
• Recommendations: Decision guide for choosing the right implementation
• Conclusions: Key findings, limitations, and future work

Compile the report with:

pdflatex dct_report.tex
bibtex dct_report
pdflatex dct_report.tex
pdflatex dct_report.tex

📊 Example Benchmark Results

Place.png (8000×8000)

Block Size	Sequential (ms)	OpenMP (ms)	CUDA (ms)	Speedup OpenMP	Speedup CUDA
1	28,174	3,627	1,493	7.77×	18.87×
2	12,790	1,728	1,261	7.40×	10.14×
4	13,365	1,200	1,282	11.14×	10.43×
8	33,658	3,439	1,288	9.79×	26.13×
16	100,465	11,466	1,297	8.76×	77.46×
32	361,744	53,936	2,476	6.71×	146.10×

Banana.png (1000×1000)

Block Size	Sequential (ms)	OpenMP (ms)	CUDA (ms)	Speedup OpenMP	Speedup CUDA
1	444	57	84	7.79×	5.29×
4	207	17	93	12.18×	2.23×
16	1,602	174	93	9.21×	17.23×
32	6,046	699	108	8.65×	55.98×

Bear.png (500×500)

Block Size	Sequential (ms)	OpenMP (ms)	CUDA (ms)	Speedup OpenMP	Speedup CUDA
2	49	5	66	9.80×	0.74×
4	50	4	78	12.50×	0.64×
16	415	43	78	9.65×	5.32×
32	1,546	175	78	8.83×	19.82×

🚦 Quick Decision Guide

Choose Sequential if:

• Educational/debugging purposes only
• No OpenMP or CUDA support available

Choose OpenMP if:

• Image size < 1 megapixel (any block size)
• Block size 1-8 for medium images (1-4 MP)
• CPU-only system or GPU unavailable
• Low latency required (<10ms)
• Processing many small images in pipeline

Choose CUDA if:

• Image size > 4 megapixels (any block size ≥4)
• Block size ≥16 for medium images (1-4 MP)
• Batch processing multiple images
• Maximum throughput critical
• Sequential execution time > 200ms

🐛 Troubleshooting

CUDA Compilation Issues

# Check CUDA installation
nvcc --version

# Verify GPU is detected
nvidia-smi

# Check compute capability
nvidia-smi --query-gpu=compute_cap --format=csv

OpenCV Not Found

# Find OpenCV installation
pkg-config --modversion opencv4

# Set OpenCV_DIR if needed
export OpenCV_DIR=/usr/local/lib/cmake/opencv4

Runtime Errors

"CUDA kernel launch failed": Block size may be too large for GPU's shared memory. Try smaller block sizes (≤16).

"Out of memory": Image too large for available RAM/VRAM. Process smaller images or use smaller block sizes.

Segmentation fault: Check image file exists and is valid. Verify block size is a power of 2.

🤝 Contributing

Contributions are welcome! Areas for improvement:

• Fast DCT algorithms (Chen-Wang, Lee's algorithm)
• Hybrid CPU-GPU pipeline with CUDA streams
• Multi-GPU support
• Mixed-precision computation (FP16/FP32)
• Additional image formats support

📄 License

This project is licensed under the MIT License - see the LICENSE file for details.

👨‍💻 Author

Lapo Chiostrini
University of Florence

Developed as part of a High Performance Computing course project (January 2026).

GitHub: lapemaya
Repository: DCT-parallel

📚 References

1. JPEG Standard: ITU-T T.81 | ISO/IEC 10918-1 (1992) - Information technology - Digital compression and coding of continuous-tone still images - Requirements and guidelines
2. OpenMP: OpenMP Architecture Review Board. OpenMP Application Programming Interface Version 5.0, November 2018. Available at: https://www.openmp.org/specifications/
3. CUDA Programming: NVIDIA Corporation. CUDA C++ Programming Guide, Version 12.3, 2023. Available at: https://docs.nvidia.com/cuda/cuda-c-programming-guide/
4. OpenCV: Bradski, G., and Kaehler, A. Learning OpenCV: Computer Vision with the OpenCV Library. O'Reilly Media, 2008
5. DCT Theory: Rao, K. R., and Yip, P. Discrete Cosine Transform: Algorithms, Advantages, Applications. Academic Press, 1990
6. Parallel Computing: Pacheco, P. An Introduction to Parallel Programming. Morgan Kaufmann, 2011
7. GPU Computing: Kirk, D. B., and Hwu, W. W. Programming Massively Parallel Processors: A Hands-on Approach, 3rd Edition. Morgan Kaufmann, 2016

For the complete bibliography and citations, see dct_report.tex.

📞 Support

For questions or issues:

1. Check the troubleshooting section above
2. Review the comprehensive report in dct_report.tex
3. Open an issue on GitHub

---

Project Repository: https://github.com/lapemaya/DCT-parallel