When talking about work and depth, we assume each loop iteration on a single PE is unit-cost (may contain multiple instructions!) Given: $n$ values in linked list, looking for sum of all values ...

Primer for Parallel Algorithms The execution of programs can be described with Execution DAGs (EDAG) Each vertex is a basic calculation, and each edge is a dependency (value flowing) Work $W...

Bandwidth vs. Latency Transfer time [T(s) = \alpha + \beta s] $\alpha $ = startup time (latency) $\beta $ = cost per byte (bandwidth = $1/\beta $) Effective bandwidth of a transfer: ...

Little’s law Given a stable system (i.e., input rate = output rate), the long-term average number of items in the system, $𝑁$, is equal to the average throughput, $\beta$, multiplied by the averag...

Amdahl’s law Formally: Amdahl’s law: A program runs in time $T_1$ on one processor. A fraction 𝑓, $0 ≤ 𝑓 ≤ 1$, of it is sequential. Let $T_p$ be the runtime on p processors, ...

Network Architecture Topologies HPC uses a lot of components (caches, processors, servers, …) which need to communicate This is done using networks In this lecture we want to look at fundame...

Large-scale Locking and Remote Direct Memory Access How to lock thousands or processes? Question: is that useful given that locks provide mutual exclusivity? Mutual exclusivity means serializa...

Explanation from Harvard CS Course Control access to a critical region Memory accesses of all processes happen in program order (a partial order, many interleavings) An execution hi...

Memory Models We need to define what it means to “read a location” and “to write a location” and the respective ordering! What values should be seen by a processor? First thought: extend the...

Cache coherence is a fundamental concept in computer architecture, particularly in systems with multiple processors or cores that share access to a common memory. In a multi-processor system,...