Parallel and Cache-Aware Algorithms
Parallel divide-and-conquer, work versus span, parallel reductions, race conditions in shared structures, cache locality, cache-oblivious algorithm concepts, external-memory model, and when asymptotically efficient code may be slow in practice.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
The timing ratio is real but machine-dependent — it was measured once on the build machine and will differ on yours. Row order walks memory sequentially, so each cache line fetched serves 16 consecutive ints; column order jumps N elements per step and wastes most of every line. Asymptotic analysis counts operations; real performance also depends on memory movement.
Work and span: work W is the total operations, span S the longest dependency chain; with p processors the time is at least max(W/p, S). A tree-shaped reduction has span O(log n).
Races: two threads updating one variable without synchronisation is undefined behaviour in C++ (a data race). The program avoids it by giving each thread its own slot and by using std::atomic for the shared counter — it deliberately does *not* run the racy version, because a sanitizer build would (rightly) report it.
External-memory model: cost counts block transfers of size B between memory of size M and disk; sorting costs Θ((n/B) log_(M/B)(n/B)) transfers, which B-trees (Module 13) and external merge sort (Module 18) achieve. Cache-oblivious algorithms (recursive matrix transpose, van Emde Boas layout) achieve good locality without knowing B.
#include <bits/stdc++.h>
using namespace std;
int main() {
const int N = 2048;
vector<int> m(N * N, 1);
auto time = [](auto f) { auto t0 = chrono::steady_clock::now(); long long r = f(); auto t1 = chrono::steady_clock::now(); return make_pair(r, chrono::duration<double, milli>(t1 - t0).count()); };
auto [rowSum, rowMs] = time([&] { long long s = 0; for (int r = 0; r < N; ++r) for (int c = 0; c < N; ++c) s += m[r * N + c]; return s; });
auto [colSum, colMs] = time([&] { long long s = 0; for (int c = 0; c < N; ++c) for (int r = 0; r < N; ++r) s += m[r * N + c]; return s; });
cout << "sum of a 2048 x 2048 matrix: row order " << rowSum << ", column order " << colSum << '\n';
cout << "column-order / row-order time ratio on this run: " << fixed << setprecision(1) << colMs / rowMs << "x (identical O(N^2) work)\n";
// parallel reduction: work O(n), span O(n / threads + threads)
vector<long long> v(10'000'000); iota(v.begin(), v.end(), 1);
unsigned T = 4; vector<long long> partial(T, 0); vector<thread> pool;
for (unsigned t = 0; t < T; ++t) pool.emplace_back([&, t] {
size_t lo = v.size() * t / T, hi = v.size() * (t + 1) / T; long long s
…sum of a 2048 x 2048 matrix: row order 4194304, column order 4194304
column-order / row-order time ratio on this run: 6.1x (identical O(N^2) work)
parallel sum of 1..10^7 with 4 threads: 50000005000000 (formula 50000005000000)
4 threads x 1e6 atomic increments: 4000000Quiz
? Row-order and column-order summation do identical O(N²) work. Why was column order slower?
+ It jumps N elements per access, so most of each fetched cache line is wasted :: Memory movement, not operation count.
- It adds more numbers :: Same numbers.
- The compiler skipped row order :: The sums are equal.
- Column order is O(N³) :: No.
? Why does each thread write to its own `partial[t]` slot?
+ Separate memory locations avoid a data race, which is undefined behaviour in C++ :: Combine after join.
- To use less memory :: Not the reason.
- Threads cannot share vectors :: They can, with care.
- It is faster to allocate :: No.
? With work W = n and span S = log n, what limits the speed-up on p processors?
+ Time ≥ max(W/p, S), so speed-up is at most min(p, W/S) :: Work and span bounds.
- Only p :: Span also limits.
- Only S :: Work also limits.
- Nothing :: Bounds exist.