Shared‐Memory Matrix Transposition

Original Repository by Matthew Maccelari, Warwick Brown & Liberty Kapungu

This repository provides in-place transposition of square matrices using shared‐memory parallelism in both C (OpenMP & PThreads) and Rust. It also includes automated build/run scripts and benchmarking infrastructure.

---

Building and Running the Code

Before running any of the shell scripts make sure they are executable using:

chmod +x build_all.sh run_all.sh

Simply run:

./build_all.sh

This will:

1. Compile all OpenMP C programs (Naïve, Diagonal, Block)
2. Compile all PThread C programs (Diagonal, Block)
3. Build the Rust binaries in src/RustBlock/, src/RustDiagonal/, (and src/RustNaive/ if present) with --release

Once everything is built, run:

./run_all.sh

This will:

• Execute each C and Rust implementation on matrix sizes 128, 1024, 2048, 4096
• Append execution times to the corresponding .csv files in Benchmarks/
• (Optionally) Dump full matrix outputs to Results/ for inspection

Testing

This script above will also run the verification tests to confirm algorithmic correctness. Each test will print the original and transposed 4×4 matrix and report whether it matches the expected result.

Building and Running Each File Independently

OpenMP Implementations

Compilation

# from the repo root
gcc -fopenmp -lgomp src/C/OpenMPNaiveThreaded.c     -o OpenMPNaiveThreaded
gcc -fopenmp -lgomp src/C/OpenMPDiagonalThreaded.c -o OpenMPDiagonalThreaded
gcc -fopenmp -lgomp src/C/OpenMPBlockOrientated.c  -o OpenMPBlockOrientated

Execution

./OpenMPNaiveThreaded
./OpenMPDiagonalThreaded
./OpenMPBlockOrientated

Each C binary will transpose matrices of sizes 128, 1024, 2048, and 4096 (with bs = 64 in the block version) and append timing data to its corresponding CSV under Benchmarks/.

PThread Implementations

Compilation

gcc -pthread src/C/PThreadDiagonalThreaded.c   -o PThreadDiagonalThreaded
gcc -pthread src/C/PThreadBlockOrientated.c   -o PThreadBlockOrientated

Execution

./PThreadDiagonalThreaded
./PThreadBlockOrientated

Each C binary will transpose matrices of sizes 128, 1024, 2048, and 4096 (with bs = 64 in the block version) and append timing data to its corresponding CSV under Benchmarks/.

Rust Implementations

Each Rust variant lives in its own crate directory under src/. You can build & run in one step.

1. Naïve‐Threaded (RustNaive)

cd src/RustNaive
cargo run --release

2. Diagonal‐Threaded (RustDiagonal)

cd src/RustDiagonal
cargo run --release

3. Block‐Oriented‐Threaded (RustBlock)

cd src/RustBlock
cargo run --release

Each Rust binary will transpose matrices of sizes 128, 1024, 2048, and 4096 (with bs = 64 in the block version) and append timing data to its corresponding CSV under Benchmarks/.

---

Overview

The lab implements multiple algorithms for in-place transposition of a square matrix:

• OpenMP Implementations:

  • Naïve-Threaded Algorithm:
    Inserts #pragma omp parallel for around the standard nested swap loops so that all element swaps above the diagonal are done in parallel.

  • Diagonal-Threaded Algorithm:
    Spawns one OpenMP task per diagonal position; each task swaps its corresponding off-diagonal element pairs (i, j) and (j, i) for j > i in parallel.

  • Block-Oriented-Threaded Algorithm:
    Chunks the N×N matrix into bs×bs blocks and uses OpenMP tasks to (1) transpose each diagonal block internally and (2) swap symmetric off-diagonal block pairs, yielding two levels of concurrency.

• PThread Implementations:

  • Diagonal-Threaded Algorithm:
    Creates one POSIX thread per diagonal index; each thread handles swapping off-diagonal element pairs in its row/column.

  • Block-Oriented-Threaded Algorithm:
    Divides the matrix into bs×bs tiles and spawns threads to (1) transpose each diagonal tile and (2) swap entire off-diagonal tile pairs using the PThread API.

• Rust Implementations:

  • Naïve-Threaded in Rust:
    Uses NUM_THREADS worker threads. Each thread takes every NUM_THREADS-th row (i = tid, tid+NUM_THREADS, …) and atomically swaps (i,j) ↔ (j,i) using Arc<Vec<AtomicI32>> with Acquire/Release ordering.

  • Diagonal-Threaded in Rust:
    Mirrors the PThread/OpenMP diagonal approach by either spawning one std::thread per diagonal index or using a small worker pool; each thread performs atomic loads/stores to swap off-diagonal element pairs.

  • Block-Oriented-Threaded in Rust:
    Divides the N×N matrix into bs×bs blocks (default bs = 64). For each block index pair (bi, bj), it spawns a std::thread that:

    1. Clones the shared Arc<Vec<AtomicI32>> buffer.
    2. If bi == bj, swaps only the upper triangle within that block; otherwise swaps corresponding elements between the two blocks.
    3. Uses atomic load(Ordering::Acquire) and store(Ordering::Release) for each element to ensure safe in-place updates.
       All thread handles are collected and joined before proceeding, mirroring the manual per-block threading of the C implementations.

For correctness validation, the Testing/ folder provides C and Rust test programs that transpose a fixed 4×4 matrix (values 1…16) and compare the result against the expected output.

---

Repository Structure

project-root/
├── Benchmarks/                   # CSV timing results & spreadsheet
│   ├── OpenMPNaiveThreaded.csv
│   ├── OpenMPDiagonalThreaded.csv
│   ├── OpenMPBlockOrientated.csv
│   ├── PThreadDiagonalThreaded.csv
│   ├── PThreadBlockOrientated.csv
│   ├── RustBlockOrientated.csv
│   ├── RustDiagonalThreaded.csv
│   ├── RustNaiveThreaded.csv
│   ├── combined_benchmarks.csv
│   └── merge_benchmarks.py
│
├── src/                          # All source code
│   ├── Results/                  # Detailed matrix dumps (optional)
│   │   └── \*.txt
│   ├── OpenMPNaiveThreaded.c
│   ├── OpenMPDiagonalThreaded.c
│   ├── OpenMPBlockOrientated.c
│   ├── PThreadDiagonalThreaded.c
│   ├── PThreadBlockOrientated.c
│   ├── RustBlock/                # Block‐oriented transpose
│   │   └── src/main.rs
│   ├── RustDiagonal/             # Diagonal‐threaded transpose
│   │   └── src/main.rs
│   └── RustNaive/                # Naïve single‐threaded baseline
│       └── src/main.rs
│
├── Testing/                      # Fixed 4×4 test matrices for correctness
│   ├── OpenMPBlockOrientatedTest.c
│   ├── OpenMPDiagonalThreadedTest.c
│   ├── OpenMPNaiveThreadedTest.c
│   ├── PThreadBlockOrientatedTest.c
│   ├── PThreadsDiagonalThreadedTest.c
│   └── RustAllTests/             # All Rust tests
│       └── src/lib.rs
│
├── build_all.sh                  # Compile ALL C & Rust implementations
├── run_all.sh                    # Execute ALL benchmarks & save results
└── README.md                     # This file

---

Benchmarks

All timing results are collected under Benchmarks/:

• CSV files (*.csv) list each run’s timings, as well as a combined file with all results.

The benchmarks compare execution times with different matrix sizes (e.g., 128, 1024, 2048, 4096) for both C OpenMP, C PThread, and Rust implementations.

---

Summary

This lab demonstrates:

• Naïve, Diagonal, and Block-oriented in-place transpose algorithms.
• Shared-memory parallelism in OpenMP, PThreads, and Rust (std::thread).
• Automated build & run workflows via build_all.sh and run_all.sh.
• Correctness validation on a fixed 4×4 test matrix.
• Performance benchmarking across multiple matrix sizes.