High-Performance Computing Repository

This repository contains implementations of parallel sorting algorithms and matrix multiplication optimizations using various high-performance computing techniques, including CUDA and OpenMP.

Repository Structure

.
├── sort algorithm/                # Sorting algorithm implementations
│   ├── bitonic Sort/              # Bitonic sort implementation
│   │   └── CUDA/                  # CUDA-based bitonic sort
│   ├── quicksort/                 # Quicksort implementations
│   │   └── OpenMP/               # OpenMP-based quicksort
│   ├── dataset/                   # Datasets with different sizes
│   ├── generate_data              # Executable for data generation
│   ├── generate_data.c            # Source for dataset generation
│   └── Makefile                   # Build configuration
│
└── matrix multiplication/         # Matrix multiplication implementations
    ├── CUDA/                      # CUDA-based matrix multiplication
    ├── OpenMP/                    # OpenMP-based matrix multiplication
    ├── dataset/                   # Matrix datasets
    ├── generate_matrix            # Executable for matrix generation
    ├── generate_matrix.c          # Source for matrix generation
    └── makefile                   # Build configuration

Sorting Algorithms

The repository implements two different sorting algorithms optimized for parallel execution:

Bitonic Sort (CUDA)

Bitonic sort is a comparison-based sorting algorithm that is well-suited for parallel implementation. The CUDA implementation uses GPU parallelism to achieve high performance, especially for large datasets.

Key features:

• GPU-accelerated implementation using CUDA
• Efficient for large datasets (up to hundreds of millions of elements)
• In-place sorting to minimize memory overhead
• Scales well with available GPU resources

Quicksort (OpenMP)

The repository includes a parallel implementation of the classic quicksort algorithm using OpenMP.

Key features:

• CPU-based parallelism using OpenMP tasks
• Hybrid approach with sequential sorting for small partitions
• Configurable threshold (THRESHOLD) to switch between parallel and sequential execution
• Good performance scaling with multiple CPU cores

Sorting Dataset Generation

The repository includes a data generator (generate_data.c) that creates datasets of various sizes for testing the sorting algorithms. The generated datasets consist of random floating-point numbers.

Features:

• Supports various dataset sizes (powers of 2)
• Creates directory structure for organized data management
• Generates reproducible random data

Available dataset sizes (number of elements):

• 1024 (1K)
• 32768 (32K)
• 1048576 (1M)
• 16777216 (16M)
• 67108864 (64M)
• 134217728 (128M)
• 268435456 (256M)
• 402653184 (384M)

Matrix Multiplication

The repository provides optimized implementations of matrix multiplication using parallel computing techniques:

CUDA Matrix Multiplication

The CUDA implementation leverages GPU cores to perform matrix multiplication in parallel.

Key features:

• 2D thread organization for efficient computation
• Each thread computes one element of the result matrix
• Uses 16x16 thread blocks for optimal performance
• Handles large matrix sizes (tested with 8192x8192)

OpenMP Matrix Multiplication

The OpenMP implementation uses multiple CPU cores to parallelize the matrix multiplication operation.

Key features:

• Configurable number of threads (NUM_THREADS)
• Uses OpenMP directives to parallelize the outermost loop
• Simple and effective parallelization approach
• Support for different matrix sizes

Matrix Data Generation

The repository includes a tool (generate_matrix.c) for creating random matrices for testing purposes.

Features:

• Generates two random matrices (A and B)
• Supports different matrix sizes (configurable via the N macro)
• Saves matrices in binary format for efficient loading

Building and Running

Sorting Algorithms

1. Generate the dataset:

   cd "sort algorithm"
   make generate_data
   ./generate_data [size]
   

   Where [size] is a power of 2 (e.g., 1024, 32768, etc.)

2. Build and run the CUDA bitonic sort:

   cd "sort algorithm/bitonic Sort/CUDA"
   make
   ./bitonic_sort
   

3. Build and run the OpenMP quicksort:

   cd "sort algorithm/quicksort/OpenMP"
   make
   ./quicksort
   

Matrix Multiplication

1. Generate the matrices:

   cd "matrix multiplication"
   make -f makefile
   ./generate_matrix
   

2. Build and run the CUDA matrix multiplication:

   cd "matrix multiplication/CUDA"
   make -f makefile
   ./matrix_mul
   

3. Build and run the OpenMP matrix multiplication:

   cd "matrix multiplication/OpenMP"
   make
   ./matrix_mul
   

Performance Considerations

Sorting Performance

• The CUDA bitonic sort performs best for very large datasets where the GPU parallelism can be fully utilized.
• The OpenMP quicksort performs well on multi-core CPUs and is more efficient for smaller datasets.
• The THRESHOLD parameter in the OpenMP quicksort can be tuned based on the hardware to optimize performance.

Matrix Multiplication Performance

• The CUDA implementation performs best for large matrices where the GPU parallelism can be fully utilized.
• The OpenMP implementation works well on multi-core CPUs but may not scale as well as the GPU version for very large matrices.
• The block size in the CUDA implementation (16x16) is chosen for good performance on most GPUs but can be tuned for specific hardware.

Requirements

Hardware

• For CUDA implementations: NVIDIA GPU with CUDA support
• For OpenMP implementations: Multi-core CPU

Software

• CUDA Toolkit (for CUDA implementations)
• GCC with OpenMP support (for OpenMP implementations)
• Make

Notes

• Matrix sizes and array lengths are generally defined as constants in the source files. Modify these constants to experiment with different sizes.
• Both implementations read input data from files in the dataset directory.
• The CUDA implementations require a compatible NVIDIA GPU.
• The OpenMP implementations will work on any multi-core CPU.