English | Italiano

Parallel and Distributed Computing Labs

Hands-on labs in C from the Parallel and Distributed Computing course, exploring memory optimization and parallelization on MIMD architectures: shared memory with OpenMP and distributed memory with MPI.

The path goes from data parallelism to hybrid MPI+OpenMP matrix multiplication on an HPC cluster, with speedup/efficiency analysis and PBS job scripts.

Labs at a Glance

#	Topic	Parallel model	Key techniques
1	Max row-sum on a matrix	Shared memory	OpenMP, critical, speedup/efficiency
2	Laplace equation on a grid	Distributed memory	MPI, row decomposition, halo exchange, blocking vs non-blocking
3	Matrix–matrix multiplication	Single-core + shared	Loop reordering, cache blocking, OpenMP
4	Distributed matrix multiplication	Hybrid MPI + OpenMP	2D Cartesian grid, SUMMA, hybrid parallelism

1. Data Parallelism on Shared Memory (OpenMP)

Files: maxsum.c, mainmaxsum.c, e1.c

• Goal: compute $R = \max_{i=1..N} \sum_{j=1}^{N} \sqrt{A(i,j)}$.
• Implementation:
  • OpenMP parallel region with row-wise work distribution among threads;
  • race condition on the global maximum handled with #pragma omp critical;
  • measurement of Speed-up $S_p = T_1/T_p$ and Efficiency $E_p = S_p/p$ for N = 800 and NT = 1, 2, 4, 8.

2. Laplace Equation (MPI)

Files: laplace.c, mainlaplace.c, mainlaplace_win.c

• Goal: iterative solution of a partial differential equation on a discretized grid.
• Algorithm:
  • 4-neighbor stencil update: $B_{i,j} = 0.25 \times (A_{i-1,j} + A_{i+1,j} + A_{i,j-1} + A_{i,j+1})$;
  • row-wise domain decomposition among MPI processes with halo exchange (prev and next neighbors).
• Variants:
  • Blocking: MPI_Send and MPI_Recv;
  • Non-blocking: MPI_Isend, MPI_Irecv and MPI_Wait to overlap communication and computation.
• mainlaplace_win.c is a Windows-friendly driver for local testing.

3. Matrix Multiplication: Single-Core and OpenMP

Files: matmatthread.c, main.c

• Goal: optimize $C = A \times B$ by reducing the memory-to-flop ratio $q = N_{mem}/N_{flop}$ to exploit the memory hierarchy.
• Techniques:
  • Loop reordering: all six loop permutations (ijk, ikj, kij, kji, jik, jki) with GFlops measurement for N = 256..2048;
  • Cache blocking: matmatblock keeps working sets in L1/L2 caches (block size 256);
  • Multithreading: OpenMP blocked kernel (matmatthread) with a 2D thread grid (1×1, 1×2, 2×2, 2×4);
  • results verified against the ikj reference implementation.

4. Hybrid Distributed Matrix Multiplication (MPI + OpenMP)

Files: matmatdist.c, mainmatmatdist.c, mymain.c

• Goal: matrix multiplication on a distributed cluster.
• Architecture:
  • MPI level: 2D Cartesian process grid (MPI_Cart_create) with row/column sub-communicators (MPI_Cart_sub) and block distribution of matrices A, B, C;
  • OpenMP level: each process computes its local block with the blocked kernel matmatthread (hybrid approach);
  • Algorithm: SUMMA, broadcasting A and B blocks along process rows/columns at each step.
• Tests: correctness with global dimensions 2×4×4 on process grids (1,1) and (2,2); performance test code provided for N up to 6144.

Shared utility: c_timer.c — portable wall-clock timer used by every lab.

Repository Structure

.
├── Esercitazione_1/
│   ├── maxsum.c             # OpenMP kernel: max over row sums
│   ├── mainmaxsum.c         # Driver: speedup/efficiency sweep
│   ├── e1.c                 # Alternative self-contained driver
│   └── c_timer.c            # Wall-clock timer
├── Esercitazione_2/
│   ├── laplace.c            # MPI halo exchange (blocking + non-blocking)
│   ├── mainlaplace.c        # Linux/MPI driver
│   ├── mainlaplace_win.c    # Windows driver
│   └── laplace.pbs          # PBS job script
├── Esercitazione_3/
│   ├── matmatthread.c       # Loop orderings, cache blocking, OpenMP kernel
│   ├── main.c               # Benchmark driver
│   └── matmat.pbs           # PBS job script
├── Esercitazione_4/
│   ├── matmatdist.c         # SUMMA over a Cartesian MPI grid
│   ├── mainmatmatdist.c     # Correctness driver
│   ├── mymain.c             # Alternative test driver
│   └── matmatdist.pbs       # PBS job script
├── templateMPI.pbs          # MPI job template
└── templateOpenMP.pbs       # OpenMP job template

Build and Run

Lab 1 — OpenMP

gcc -O3 -fopenmp Esercitazione_1/e1.c -o maxsum -lm
./maxsum

Lab 2 — MPI

mpicc -O3 Esercitazione_2/mainlaplace.c Esercitazione_2/laplace.c -o laplace
mpirun -np 8 ./laplace

Lab 3 — OpenMP

gcc -O3 -fopenmp Esercitazione_3/main.c -o matmat -lm
./matmat

Lab 4 — MPI + OpenMP

mpicc -O3 -fopenmp Esercitazione_4/mainmatmatdist.c -o matmatdist -lm
mpirun -np 4 ./matmatdist

HPC Cluster (PBS)

The lab cluster uses PBS/Torque with 8 nodes × 8 cores. Ready-to-use scripts are included in each lab (*.pbs), plus templateMPI.pbs and templateOpenMP.pbs as starting points. Typical workflow:

qsub Esercitazione_2/laplace.pbs    # submit
qstat                               # check status

The scripts build with mpicc or cc -fopenmp and run on the nodes listed in $PBS_NODEFILE.

Notes

• c_timer.c is duplicated in each lab folder so that every exercise is self-contained and compilable on its own.