Distributed Systems
Assignment
P . JAG A D E E P VA R M A - S E 2 2 U C S E 204
V . R I S H I VA R M A - S E 2 2 U C S E 2 21
P OT L A A N I S H - S E 2 2 U C S E 21 1
S AT W I K C H OW D H A RY - S E 2 2 U C S E 28 7
Question 1
Objective:
Parallel Min / Max / Mean Computation using OpenMP
Build an OpenMP program that calculates the Minimum, Maximum, and Mean of a very large numeric dataset.
Study how performance changes with different numbers of threads.
Problem Setup
Total elements: 2²⁴ ≈ 16 million values
Value range: Uniformly distributed between 0 and 10⁹
Threads tested: 1, 2, 4, 6, 8, 10, 12, 14, 16
Each configuration run 5 times and averaged
Metrics collected:
Execution Time vs Number of Threads
Speedup vs Number of Threads
Goal: Identify the “sweet spot” number of threads for best performance
Q1: Methodology
Process
[Link] Partitioning
The full dataset is split so each thread works on a disjoint block of elements.
[Link] Computation
Each thread computes its own local minimum, local maximum, and partial sum.
[Link] Phase
Local results are combined into global min, max, and sum using OpenMP reduction.
[Link] Calculation
Mean is computed as:
Mean=Global SumN\text{Mean} = \frac{\text{Global Sum}}{N}Mean=NGlobal Sum
[Link]
gettimeofday() is used to record start and end timestamps around the parallel region.
[Link]
Each test (for each thread count) is repeated 5 times to smooth out noise from scheduling, cache warmup,
etc.
Key Point
The use of OpenMP reduction drastically reduces the need for manual synchronization, which helps
performance and correctness at higher thread counts.
Q1: Implementation Details
Language / Setup
C program using:
stdio.h, stdlib.h for I/O and memory
omp.h for OpenMP
sys/time.h for wall-clock timing
Dataset storage sized for ~16 million elements
Mean is computed in double to avoid precision loss
Data Generation
Each thread generates its own random values with a thread-safe generator like rand_r() so that there is no race on the RNG state.
Values are uniformly generated in [0, 10⁹] as required.
Parallel Aggregation
Core loop uses OpenMP with reductions, for example:
#pragma omp parallel for reduction(+:sum) reduction(max:max_val) reduction(min:min_val) schedule(static)
Each thread handles its chunk, producing partial stats that OpenMP then merges safely.
Thread Scaling & Measurement
The number of threads is varied from 1 up to 16.
Runtime per configuration is written to a CSV file, along with the computed min, max, and mean.
A helper Python script (plot_speedup.py) is used to generate plots of Runtime vs Threads and Speedup vs Threads.
Q1: Performance Analysis
Runtime vs Threads
Execution time drops sharply when moving from 1 thread to 2, 4, and 8 threads.
After ~8 threads, further decrease in runtime becomes very minor and sometimes noisy.
Reason: memory bandwidth starts becoming the bottleneck; the CPU is spending more time waiting for
memory than actually computing.
Speedup vs Threads
Speedup is close to proportional (almost linear) up to about 8 threads.
After that, the curve flattens and can even dip slightly due to overheads such as synchronization and
cache/memory contention.
This is typical once you reach or exceed the number of physical cores.
Observation
The design scales well initially but hits limits caused by shared resources (like RAM bandwidth).
Q1: Conclusion
Summary
Strong parallel scaling up to around 8 threads.
Synchronization and memory bus contention limit further gains beyond that point.
Achieved roughly ~3.8× speedup at 8 threads (parallel efficiency of ~47%).
Improvement Opportunities
Ensure min / max / sum are combined with OpenMP reduction instead of manually doing #pragma omp
critical.
Merge thread-local statistics after the parallel region to reduce time spent in synchronized sections.
Try different OpenMP schedules (static, dynamic) if data distribution is not uniform.
Overall Result
OpenMP is effective for bulk statistical aggregation (min / max / mean) on very large arrays.
Understanding when scaling stops being useful helps decide the optimal number of threads to use in
practice.
Q2: Parallel Dot Product Using OpenMP
Objective
Implement a highly parallel dot product of two extremely large vectors using OpenMP.
Evaluate scaling of runtime and speedup as we increase the number of threads from 1 to 16.
Problem Definition
Two large vectors A and B
Elements generated from the discrete set {−1, 0, 1}
Effective vector length tested: very large (on the order of 10⁸ elements per run; scalable to the conceptual
target of 10⁹).
Each experiment is repeated 5 times and averaged.
What We’re Measuring
How fast the dot product completes as threads increase
At what point adding more threads stops helping
Q2: Approach and Execution Model
Steps
Initialization
Define N (vector length).
Set thread count using omp_set_num_threads(...).
Data Creation
Instead of pre-allocating two full billion-element arrays in memory, each thread generates the portions of A and B it needs on the fly using its own seed.
Values are randomly chosen from {−1, 0, 1}.
This avoids global contention for random number generation and keeps memory pressure under control.
Parallel Dot Product
Use:
#pragma omp parallel for reduction(+:dot) schedule(static)
Each thread accumulates a local partial sum dot_local = A[i] * B[i].
OpenMP reduction safely combines these partial sums into a single global dot product at the end.
Timing
High-resolution timers record elapsed time for each run.
Repetition
Perform 5 runs for each thread count and average the runtime to get a stable measurement.
Q2: Results and Observations
Runtime Behavior
Runtime Behavior
Time to compute the dot product drops significantly as we go from 1 → 2 → 4 → 8 threads.
After 8 threads, the benefit of adding more threads becomes smaller.
Speedup Behavior
Speedup grows close to linearly up to ~8 threads.
At 16 threads, the total speedup is around ~2.4× relative to single-thread execution.
Why It Plateaus
The reduction step at the end introduces synchronization overhead.
Memory bandwidth becomes a limiting factor: multiple cores try to read operands at the same time.
Interpretation
The workload is “embarrassingly parallel” in theory, but real systems are limited by shared memory bandwidth and reduction
cost.
Q2: Conclusion
Key Points
OpenMP parallelization provides a clear runtime advantage for large-scale dot product calculations.
Most of the gain shows up by ~8 threads. Beyond that, scaling becomes sub-linear.
Parallel efficiency in the 8-thread range is acceptable; by 16 threads the marginal benefit drops.
Optimizations to Explore
Use #pragma omp simd inside the loop to exploit vector units (SIMD) within each core.
Try guided or dynamic scheduling if data generation cost per index is not uniform.
Apply cache blocking / tiling if vectors are split into chunks that better fit cache, particularly on NUMA systems.
Bottom Line
Parallel dot product is fast and clean to implement using OpenMP reductions, but hardware limits (not algorithmic limits) cap
the achievable speedup.
Q3: Parallel Sorting and Multi-Stage Merge
Objective
Sort and merge a large volume of data in parallel using OpenMP, and analyze how the merge strategy scales.
Problem Setup
We consider K independent subsequences.
Typical parameters discussed:
K = 1000 subsequences
Each subsequence contains ~1,000,000 uniformly distributed random numbers
⇒ Total data volume on the order of 10⁹ elements across all subsequences conceptually.
(In code samples, smaller working values like 10 million total elements are also used for timing practicality.)
Each subsequence is sorted independently, and then all subsequences are merged into one global sorted sequence.
Goals
Measure runtime with thread counts from 1 to 16.
Compute speedup relative to the single-thread version.
Average each configuration across 5 runs for fairness.
Q3: Methodology
Step-by-Step
1. Data Generation
Each thread creates one or more of the subsequences using its own random seed.
Values drawn from Uniform[0,1).
2. Parallel Sort
#pragma omp parallel for schedule(dynamic)
Each subsequence is sorted via qsort() (or similar).
Dynamic scheduling helps balance the load because different runs might take slightly different times to sort.
3. Hierarchical Merge
After sorting, subsequences are merged pairwise.
Merging is done in “rounds”:
Round 1 merges (run0 with run1), (run2 with run3), … in parallel.
Round 2 merges the outputs of Round 1, and so on.
Each merge round also uses OpenMP parallel loops to assign merge pairs to threads.
4. Timing and Averaging
Total sort+merge time is recorded with a timer like gettimeofday() / now_sec().
Each setting of thread count is repeated 5 times and averaged.
Q3: Results and Analysis
Runtime vs Threads
Runtime vs Threads
Runtime improves when going from 1 → 2 → 4 threads, e.g. a drop from about 0.223s (single-thread
baseline) to ~0.175s (4 threads) in representative measurements.
After ~4 threads, runtime reductions slow down and, in some cases, total time slightly increases.
Speedup vs Threads
Maximum speedup observed is roughly ~1.26× around 4 threads.
For higher thread counts (8, 12, 16), speedup plateaus and can even regress slightly.
Why Scaling Is Limited
Sorting individual chunks is highly parallel.
But the merge phase becomes less parallel over time:
Each round halves the number of sorted runs, so the number of parallel merge tasks shrinks.
Late rounds become closer to sequential.
Memory movement and allocation during merges add overhead.
Q3: Conclusion
Key Takeaways
The approach shows only modest scalability, with best results around 4 threads.
Beyond that, overhead from allocation, memory copies, and reduced parallelism during final merge
stages limits gains.
Possible Enhancements
Reuse buffers across merge rounds to avoid repeated malloc/free.
Use OpenMP tasks (#pragma omp task) to dynamically assign merge jobs instead of relying only on
parallel-for.
Consider multiway merge (merging more than two runs at a time using a min-heap or loser tree), which
can exploit more concurrency in earlier rounds.
Summary
Parallel sorting scales well.
Parallel merging is the true bottleneck because it naturally “funnels down” to fewer active tasks.
That funnel is what caps the achievable speedup.
Q4: Blocked Matrix Multiplication with OpenMP
Objective
Multiply two square matrices of size 4096 × 4096 in parallel.
Use cache-friendly block (tile) multiplication to improve locality and reduce cache misses.
Evaluate performance across:
Different block sizes: 2, 4, 8, 16, 32
Different thread counts: 1, 2, 4, 6, 8, 10, 12, 14, 16
Average results over 5 runs for each configuration.
Why Blocking?
Naive matrix multiplication is O(n³) and suffers from poor cache reuse for large matrices.
Blocking splits matrices into smaller tiles that fit better in cache, so data gets reused more efficiently.
This reduces memory access cost and improves throughput.
Q4: Parallel Strategy
Process
1. Matrix Setup
A and B are initialized with random floating-point values in [0, 1).
Result matrix C is initialized to zeros.
All matrices are dimension n = 4096.
2. Blocked Multiplication
We iterate over A and B in tiles of size b × b, where b ∈ {2, 4, 8, 16, 32}.
For each tile triple (ii, jj, kk), we multiply the block of A at (ii, kk) with the block of B at (kk, jj) and accumulate into the block of C at (ii, jj).
3. OpenMP Parallelism
Outer loops over ii and jj are parallelized:
#pragma omp parallel for collapse(2) schedule(static)
collapse(2) allows OpenMP to treat the nested loops (ii, jj) as a single large iteration space and split it among threads.
Each thread writes to distinct regions of C to avoid false sharing.
4. Timing
For each (block size, thread count) combination, we measure total runtime using gettimeofday().
We repeat 5 times and average to reduce noise.
5. Results Logged
For plotting: runtime vs thread count and speedup vs thread count, for each block size.
Q4: Observations and Performance
Runtime vs Threads
Runtime vs Threads
1. Runtime consistently decreases as we increase threads from 1 up to about 8 threads.
2. After ~8 threads, adding more threads gives only marginal benefit because memory bandwidth and cache pressure
become limiting.
Effect of Block Size
1. Very small block sizes (2, 4) cause overhead due to too many tiny loops and too much loop control relative to useful
work.
2. Very large block sizes (32) reduce loop overhead but can worsen cache locality since each tile may no longer fit well in
cache.
3. Block size = 16 typically gives the best overall balance between locality and overhead.
Speedup vs Threads
1. For a good block size (like 16), speedup climbs rapidly and reaches roughly 5×–6× at around 8 threads.
2. Beyond 8 threads, the speedup curve flattens because the computation becomes limited by memory transfers rather
than raw multiply-add throughput.
Q4: Conclusion
Key Points
Blocking plus OpenMP parallelization produces large performance gains for dense matrix multiplication.
Strong scaling is seen up to ~8 threads.
Block size around 16 is generally optimal across tests, giving a good trade-off between cache reuse and parallel load
distribution.
After core saturation, the main bottleneck is memory subsystem bandwidth, not arithmetic.
Further Optimization Ideas
Loop unrolling and #pragma omp simd inside the innermost multiply-accumulate loop can further accelerate per-thread
work.
NUMA-aware allocation (placing memory closer to the core that uses it) can reduce cross-socket traffic on multi-socket
systems.
Using OpenMP tasks for tiles can allow more flexible scheduling on heterogeneous cores.
Q5: Large-Scale Statistical Analysis with OpenMP
Overview
Q5 consists of two related experiments:
Part (A):
Compute minimum, maximum, and mean for a dataset of 100 million randomly generated values.
Evaluate scaling with thread counts from 1 to 16.
Part (B):
Model a continuous data stream scenario:
60 million random values per simulated minute
Over 60 minutes → total ~3.6 billion generated values in the range [0, 10¹⁸]
Compute summary statistics such as mean, median, quartiles (Q25, Q75), min, max, and approximate mode.
Again, evaluate thread scaling from 1 to 16.
Both parts measure runtime with gettimeofday(), repeat each configuration 5 times, and average results.
Both parts record Runtime vs Threads and Speedup vs Threads.
Box-plots are used to confirm data distribution characteristics (uniformity / spread / outliers).
Q5: Methodology and Computation Flow
Common Elements
3. Parallel Statistics
1. Initialization
Mean / Min / Max:
Fix total data volume (100 million for Part A; 3.6 billion total simulated stream values #pragma omp parallel for reduction(+:sum) reduction(min:min_val)
for Part B). reduction(max:max_val)
Assign thread counts among {1, 2, 4, 6, 8, 10, 12, 14, 16}. so each thread contributes safely to global aggregates.
Use deterministic seeding for reproducibility. Quartiles & Median (Part B):
Threads locally sort or partially order their own segments.
2. Parallel Data Generation These partial results are then combined to extract global median and
Each thread independently generates its assigned portion of values with a uniform percentile cut positions (Q25, Q75).
distribution (for Part B: 0 to 10¹⁸). Mode (Part B):
Work is divided using #pragma omp parallel for schedule(static) to ensure balanced Each thread maintains its own frequency map / counts for observed values
load. or binned ranges.
These local frequency summaries are merged to identify the most frequent
value/range.
(Because the numeric range is huge up to 10¹⁸, “approximate mode”
techniques or bucketing make sense.)
4. Timing and Logging
gettimeofday() records total computation time per configuration.
Each configuration is run 5 times; runtimes are averaged.
Results are output in CSV for plotting and further analysis.
Q5: Results and Interpretation
Part (A) – Basic Aggregates (Min / Max / Mean on 100M values) Speedup Curves
Runtime improves from about 0.104 seconds with 1 thread to ~0.027 seconds Speedup rises quickly at low thread counts and begins to flatten at
with 8–16 threads. high thread counts (10, 12, 16).
That’s roughly a 3.8× speedup. The flattening is caused by synchronization, shared memory
After ~8 threads, performance plateaus because memory bandwidth and contention, and overhead of merging statistical summaries
reduction overhead dominate. (especially for median/percentiles).
Part (B) – Full Statistical Summary (3.6B simulated values) Box Plot Analysis
Runtime drops dramatically when scaling threads. Box plots of per-thread data show that generated values are
Example reference trend: from the order of hundreds of seconds (single-thread
uniformly distributed (for example, across [0, 10¹⁸] in Part B).
baseline ≈ 300s) down to under 30 seconds at higher thread counts. The medians are centered and the interquartile ranges are tight and
Speedup approaches ~8.8× at 16 threads.
consistent across threads.
The improvement is larger than Part (A) because the workload is extremely large,
This confirms that load is well-balanced and no subset of threads is
so parallelism has more to exploit.
disproportionately “heavier,” which supports fair scalability.
Q5: Conclusion
Summary of Findings
Both Part (A) and Part (B) confirm that OpenMP delivers substantial runtime reduction by parallelizing statistical analysis over extremely
large datasets.
Part (A): ~3.8× speedup for core aggregates (min / max / mean).
Part (B): up to ~8.8× speedup for a richer statistical profile (mean, median, quartiles, mode, etc.).
In both, the benefit of adding threads past ~8–10 tapers off due to memory bandwidth saturation and synchronization overhead.
Optimizations Going Forward
Add SIMD (#pragma omp simd) inside tight loops to accelerate arithmetic within each core.
Use dynamic or guided scheduling for more irregular workloads (useful in Part B, where computing median / quartiles needs extra work).
Improve data locality and reuse cache-friendly buffers to reduce memory traffic.
Migrate some phases (like percentile extraction and merging of modes) to task-based parallelism for finer-grained load distribution.
Overall Conclusion
OpenMP provides a clean, scalable framework for high-volume numerical analytics, streaming analysis, and statistical summarization.
The experiments demonstrate real limits: scaling stops being ideal once we hit cache hierarchy and memory bandwidth constraints.
Understanding these saturation points is critical for designing production-grade high-performance systems.