Anki Deck Changes

exec.submit(callable) returns a Future<V>. exec.execute(runnable) is fire-and-forget (no return value).

Split the bottleneck (slowest) stage into two or more sub-stages of equal duration. Caveat: too much splitting is impractical — it introduces enormous switching/management overhead.

Designing parallel algorithms means decreasing span without increasing work too much — directly equivalent to reducing f in Amdahl's Law.

"Latency" by default means the first element. For a balanced pipeline this equals num_stages × max(stage_time).

A data race is a low-level memory event: a shared variable is accessed by two threads, at least one access is a write, and there is no synchronization. A race condition is a higher-level correctness issue: the program's observable behavior depends on execution order. A data race usually causes a race condition, but a race condition can exist even without a data race (e.g. check-then-act with synchronized operations). In Java, data races invoke undefined behavior per the JMM.

Too small → overhead dominates. Too large → poor load balancing and under-utilization. The exact threshold is empirical.

Implemented via hardware CAS (compare-and-swap). Faster than synchronized for simple counters. Part of java.util.concurrent.atomic.

A good scheduler can always achieve time within a constant factor of the ideal. The two terms represent two different sources of time: \(T_1/p\) is the work-limited regime, and \(O(T_\infty)\) is the unavoidable sequential overhead from dependencies (span-limited regime). Their sum is an upper bound — a scheduler can't be much worse than their sum.

Example: for a finite run, effective throughput was 0.7 while the infinite-stream bound was 1. As N → ∞, effective throughput approaches 1/max(stage_time).