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.
Live Links
The three main places to open this project. After these files are pushed, GitHub Pages serves this site from the repository root.
| What | Link |
|---|---|
| Repository | https://github.com/rohaan2802/Multithreading |
| Website (GitHub Pages) | https://rohaan2802.github.io/Multithreading/ |
| Releases page | https://github.com/rohaan2802/Multithreading/releases |
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).
Serial baseline
A single-threaded implementation of each kernel. This is the correctness reference and the T1 in every speedup figure.
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.
Affinity and static chunks
Each thread is pinned with pthread_setaffinity_np and walks a static set of chunks (tid, tid+T, tid+2T, …).
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 scoring
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 multiply
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 graph
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
| Version | Threads | Avg (ms) | Min (ms) | Speedup | Efficiency |
|---|---|---|---|---|---|
| V1 | 1 | 69.93 | 10.16 | 1.00 | 1.00 |
| V2 | 1 | 67.17 | 11.56 | 1.04 | 1.04 |
| V2 | 2 | 47.22 | 11.28 | 1.48 | 0.74 |
| V2 | 3 | 38.79 | 11.12 | 1.80 | 0.60 |
| V2 | 4 | 43.58 | 10.98 | 1.60 | 0.40 |
| V3 | 1 | 68.95 | 10.65 | 1.01 | 1.01 |
| V3 | 2 | 47.18 | 10.75 | 1.48 | 0.74 |
| V3 | 3 | 39.45 | 11.23 | 1.77 | 0.59 |
| V3 | 4 | 40.72 | 11.18 | 1.72 | 0.43 |
Task 2 — SpMV
| Version | Threads | Avg (ms) | Min (ms) | Speedup | Efficiency |
|---|---|---|---|---|---|
| V1 | 1 | 26.21 | 8.11 | 1.00 | 1.00 |
| V2 | 1 | 26.00 | 8.17 | 1.01 | 1.01 |
| V2 | 2 | 16.08 | 5.15 | 1.63 | 0.81 |
| V2 | 3 | 12.51 | 4.38 | 2.09 | 0.70 |
| V2 | 4 | 16.85 | 4.11 | 1.56 | 0.39 |
| V3 | 1 | 25.75 | 8.52 | 1.02 | 1.02 |
| V3 | 2 | 19.48 | 7.66 | 1.35 | 0.67 |
| V3 | 3 | 14.62 | 5.62 | 1.79 | 0.60 |
| V3 | 4 | 14.25 | 5.00 | 1.84 | 0.46 |
Task 3 — BFS
| Version | Threads | Avg (ms) | Min (ms) | Speedup | Efficiency |
|---|---|---|---|---|---|
| V1 | 1 | 82.09 | 14.17 | 1.00 | 1.00 |
| V2 | 1 | 105.05 | 14.02 | 0.78 | 0.78 |
| V2 | 2 | 69.57 | 14.76 | 1.18 | 0.59 |
| V2 | 3 | 64.80 | 22.25 | 1.27 | 0.42 |
| V2 | 4 | 56.10 | 19.50 | 1.46 | 0.37 |
| V3 | 1 | 101.49 | 15.34 | 0.81 | 0.81 |
| V3 | 2 | 102.06 | 25.02 | 0.80 | 0.40 |
| V3 | 3 | 61.10 | 19.13 | 1.34 | 0.45 |
| V3 | 4 | 67.48 | 21.94 | 1.22 | 0.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.
Datasets and Large Files
Two compressed archives sit in the repository. The SUSY zip is about 799 MB, which is over GitHub’s 100 MB limit, so it lives in release/ and is meant to be attached to a GitHub Release.
Task 2 and Task 3 archives
webbase-1M.tar.gz (~11 MB) and web-Google.txt.gz (~21 MB), with unpack instructions.
datasets/README.mdSUSY.zip (release asset)
The Task 1 dataset, kept locally in release/ and published from the Releases page.
UCI SUSY
The original source of the Task 1 CSV, if you would rather download it there.
archive.ics.uci.eduReleases page
Where SUSY.zip is published as a release asset.
Screenshots
Eighteen snapshots of the programs, the measurements and the source. Click any image to enlarge it, and use the arrow keys to move between images.
No screenshots match that filter.
Folder Structure
Source, datasets, the assignment brief and the website, with names that match what is in each folder.
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
git clone https://github.com/rohaan2802/Multithreading.git
cd Multithreading
bash scripts/extract_datasets.sh
make
Run a program
./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.