FAST-NUCES · Spring 2026 · Parallel and Distributed Computing

Multithreading – POSIX Threads and Performance

My first PDC assignment: three C workloads with different shapes — dense scoring, sparse multiply, and graph search — each written as a serial baseline, a pthreads version, and a version that pins threads to cores.

Language: C Parallelism: Pthreads FAST-NUCES Spring 2026 Course: PDC License: MIT
3Workloads
9C programs
3Versions each
4Logical CPUs
2.1×Best average speedup
PthreadsOnly parallel library

Overview

The brief is a revision of POSIX threads and performance, for Parallel and Distributed Computing at FAST-NUCES, Spring 2026 (roll 22I-2327, section F).

V1

Serial baseline

A single-threaded implementation of each kernel. This is the correctness reference and the T1 in every speedup figure.

V2

Pthreads, OS scheduling

Work is split into chunks and picked up by a pool of threads. The operating system places those threads on cores; there is no manual affinity.

V3

Affinity and static chunks

Each thread is pinned with pthread_setaffinity_np and walks a static set of chunks (tid, tid+T, tid+2T, …).

Report

Measurement

Runtime, speedup and efficiency at 1–4 threads, on 10%, 50% and 100% of each dataset, five trials each. V3 is also profiled with gprof.

The Three Workloads

Three problems with different memory behaviour, each in three versions. Only C and Pthreads are used — no OpenMP, TBB or std::thread.

Task 1SUSY logistic scoringDense, compute-bound · 18 features + a fixed bias

Each row of the SUSY CSV is a label followed by 18 numeric features. A fixed logistic model (bias −0.35 and a given weight vector) produces a probability; records with p ≥ 0.5 are predicted positive. The program prints N, PRED_POS, TP, FP, TN and FN.

Task 2Sparse matrix–vector multiplyCOO → CSR, then y = Ax on webbase-1M

The SuiteSparse webbase-1M matrix is a 1,000,005 × 1,000,005 web graph with 3,105,536 non-zeros. After a CSR build (outside the timer), the programs compute y = Ax with x[j] = (j mod 1000) / 1000 and print a checksum. A correct full run gives CHECKSUM 499500.015000. Parallel versions split work on row chunks.

Task 3BFS on a web graphSNAP web-Google, source 0

SNAP’s web-Google graph has 875,713 nodes and 5,105,039 directed edges. BFS from node 0 reaches 600,493 of them; the farthest sits at hop-distance 32. The programs print the reachable count, the maximum distance, and a per-level histogram. This kernel is the hardest of the three to scale, because of frontier synchronisation and irregular neighbour walks.

Performance Results

Taken on an Intel Core i5-5300U (2 cores, 4 logical processors), Linux/WSL, GCC -O2. Averages pool the 10%, 50% and 100% dataset sizes, five trials each. Speedup is T1 / Tp against the V1 baseline; efficiency is speedup divided by the thread count.

Task 1 — SUSY scoring

VersionThreadsAvg (ms)Min (ms)SpeedupEfficiency
V1169.9310.161.001.00
V2167.1711.561.041.04
V2247.2211.281.480.74
V2338.7911.121.800.60
V2443.5810.981.600.40
V3168.9510.651.011.01
V3247.1810.751.480.74
V3339.4511.231.770.59
V3440.7211.181.720.43

Task 2 — SpMV

VersionThreadsAvg (ms)Min (ms)SpeedupEfficiency
V1126.218.111.001.00
V2126.008.171.011.01
V2216.085.151.630.81
V2312.514.382.090.70
V2416.854.111.560.39
V3125.758.521.021.02
V3219.487.661.350.67
V3314.625.621.790.60
V3414.255.001.840.46

Task 3 — BFS

VersionThreadsAvg (ms)Min (ms)SpeedupEfficiency
V1182.0914.171.001.00
V21105.0514.020.780.78
V2269.5714.761.180.59
V2364.8022.251.270.42
V2456.1019.501.460.37
V31101.4915.340.810.81
V32102.0625.020.800.40
V3361.1019.131.340.45
V3467.4821.941.220.30

The best average speedup is about 2.1×, on Task 2 with three V2 threads. Four threads share two physical cores, and efficiency falls off. BFS is the awkward case: a second thread can be slower than the serial code, and even the best figure is only about 1.5×. gprof puts 98% of Task 1 inside worker_v3, and most of Task 3 inside bfs_worker_v3; Task 2 shares time between the worker, the driver and the matrix reader.

Folder Structure

Source, datasets, the assignment brief and the website, with names that match what is in each folder.

repository
Multithreading/
├── assignment/
│   ├── Assignment_1_PDC_Spring_2026.pdf
│   ├── Assignment_1_Instructions.txt
│   └── Report_22I-2327_Section_F.pdf
├── assets/css  assets/js  assets/screenshots  assets/thumbs
├── datasets/
│   ├── README.md
│   ├── webbase-1M.tar.gz
│   └── web-Google.txt.gz
├── release/README.md          (SUSY.zip sits here locally; not committed)
├── scripts/compile.sh  scripts/extract_datasets.sh
├── src/
│   ├── task1_susy_logistic/
│   ├── task2_spmv/
│   └── task3_bfs/
├── Makefile
├── LICENSE
├── README.md
├── index.html
└── .nojekyll

How to Compile and Run

Linux or WSL, with GCC. Version 3 uses pthread_setaffinity_np, which is a GNU/Linux extension.

Clone the repository

bash
git clone https://github.com/rohaan2802/Multithreading.git
cd Multithreading
bash scripts/extract_datasets.sh
make

Run a program

bash
./bin/task2_v1_serial datasets/webbase-1M.mtx
./bin/task2_v2_pthreads datasets/webbase-1M.mtx 4 1024
./bin/task2_v3_affinity datasets/webbase-1M.mtx 4 1024

./bin/task3_v1_serial datasets/web-Google.txt
./bin/task3_v2_pthreads datasets/web-Google.txt 4 2048
./bin/task3_v3_affinity datasets/web-Google.txt 4 2048

./bin/task1_v1_serial path/to/supersymmetry_dataset.csv
./bin/task1_v2_pthreads path/to/supersymmetry_dataset.csv 4 200000
./bin/task1_v3_affinity path/to/supersymmetry_dataset.csv 4 200000

Task 1 needs the SUSY CSV, which comes from release/SUSY.zip or from the UCI SUSY page. A longer walkthrough, including a gprof example, is in the README.

License

The C programs I wrote are under the MIT License. The assignment brief belongs to the course instructors at FAST-NUCES, and the datasets belong to UCI, the SuiteSparse Matrix Collection and SNAP. They are here so the programs can be run and the work can be checked. If you are an owner and want something removed, please open an issue.