Revisiting his SISD / SIMD / MIMD classification, Michael Flynn already warned that MIMD "multiprocessors are subjected to a saturation syndrome based on general communications lockout": past some size, processors wait for the shared path instead of computing.
One machine, many brains: multiprocessors, buses and topologies
After this lesson you will say what makes a machine a multiprocessor and why it is built, explain why a single bus stops scaling at a few tens of processors, and compute the total and bisection bandwidth, the diameter and the degree of the classic networks by counting their links and cutting them in half.
The notes report that commercial single-bus multiprocessors "maxed out at ≈36 processors before the bus saturated" (p. 420). Take such a machine, 36 processors on one bus, and plug in a 37th. The machine barely gets faster. Worse, every memory access of the other 36 now waits a little longer: the 37th processor has made the bus slower for everyone.
Architects answered with networks of many links. A 64-node ring has 64 links where a bus has one. Yet when half of the machine sends data to the other half, the ring is "only 2× bus" — the notes' own verdict (p. 423). Sixty-four times the wires, twice the speed.
Both puzzles have the same answer. It is a single number, and by the end of the lesson you will compute it for any network.
What makes a machine a multiprocessor
Open the task manager of a laptop under load: several cores are busy at once, each running its own program or thread. One operating system schedules them all, and each core can load any address of the one memory. That chip is a multiprocessor. A rack of a hundred web servers is not: a hundred operating systems, a hundred separate memories, messages over a network — a cluster (lesson 34).
Multiprocessor — "a computer system with tightly coupled processors, coordinated by a single operating system, and typically offering a shared memory abstraction (shared address space)" (p. 417): processors that "remain part of one coherent machine, not a loose cluster".
Its execution paradigm is MIMD (multiple instruction, multiple data): every processor runs its own instruction stream on its own data (Flynn's taxonomy, lesson 30). What it harvests is thread-level parallelism (TLP), many independent streams at once — where instruction-level parallelism overlaps the instructions of one stream (lessons 7–21) and data-level parallelism applies one instruction to many elements (lessons 30–32). Multithreading (lesson 29) shares one core among threads; a multiprocessor gives each thread a core of its own.
Why build one? The notes give four goals (p. 417). Performance: very high throughput from TLP. Scalability: performance that grows, ideally linearly, as processors are added. Reliability: redundancy lets the machine tolerate some faults. Versatility: the same idea from embedded systems to high-end servers. Behind all four is history: "the shift from single-core → multicore → manycore reflects the industry response to ILP and frequency walls" — the walls of lesson 8.
The notes sort multiprocessors by integration and scale; from left to right the machines grow and the memory spreads out.
| Multicore | SMP | Large-scale multiprocessor | |
|---|---|---|---|
| what | several cores on the same chip; a manycore beyond 32 cores | symmetric multiprocessor: all processors share one centralized memory | distributed shared memory (DSM): the memory is physically spread over the nodes |
| size, examples | Intel i7, AMD Ryzen, ARM big.LITTLE | typically ≤ 32 processors | beyond 32 processors |
| memory access | uniform: one chip is a small SMP | uniform: UMA, Uniform Memory Access | non-uniform: NUMA, local fast and remote slow |
| coherence | snooping on small chips (p. 432) | snooping protocols | directory-based protocols |
In one sentence of the notes: "centralized memory works up to a point, beyond which distribution is necessary" (p. 417). SMP or NUMA is a scalability decision, and the coherence protocol comes with it — snooping, every cache listening to one shared medium, for small machines; directories, a table next to each memory recording who holds a copy, for large ones (lessons 35–38).
"A multicore is a SIMD machine." No: every core has its own program counter and fetches its own instructions — MIMD. SIMD lives inside a core, in its vector or packed units (lessons 30–32).
Multiprocessors are not just "more cores": they are about how processors, memory and communication are organised and coordinated (p. 417).
Ten questions every multiprocessor answers
Every machine with more than one processor answers ten questions, whether its designers meant to or not. The notes list them (pp. 418–419) under one frame: architects balance scalability — network, memory placement, coherence protocol — against programmability — shared memory or message passing — and design hardware and software together "to extract parallelism and hide communication latency".
| # | Question | The options | Where |
|---|---|---|---|
| 1 | How many processors? | small: 2–8 cores (single bus, snooping, UMA); medium: 8–32; large: hundreds to thousands (NUMA, DSM or message passing) — chosen by the workload: servers, embedded, HPC | this lesson |
| 2 | How powerful are they? | a few complex out-of-order cores or many simple in-order ones, as in IBM Blue Gene: single-thread speed against throughput; performance per watt rules at large scale | lesson 8 |
| 3 | How are they connected? | a bus: cheap, simple, saturates at ≈ 36 processors; or an interconnection network: rings, meshes, crossbars, hypercubes — it sets bandwidth, latency and scalability | sections 3–5 |
| 4 | How do they share data? | shared memory: implicit, through loads and stores, coherence needed; message passing: explicit send and receive, simpler hardware, harder programming | below; lesson 34 |
| 5 | Where is the physical memory? | centralized (UMA): uniform access, easy, a bottleneck; distributed (NUMA): scalable, non-uniform latency | lesson 34 |
| 6 | How do they coordinate? | locks, barriers, atomic operations; their cost can limit scalability | lesson 34 |
| 7 | How are they programmed? | multiprogramming (independent jobs), threads on shared memory, MPI processes, data-parallel / SPMD in bulk-synchronous phases | lesson 34 |
| 8 | How do the caches stay coherent? | snooping protocols on small SMPs, directory protocols on large NUMA machines | lessons 35–38 |
| 9 | In which order do writes become visible? | memory consistency: sequential consistency (simple, slow) or relaxed models (complex, efficient) | lesson 35 |
| 10 | How is performance evaluated? | speedup against the number of processors (Amdahl, Gustafson), local against remote latency, network and memory bandwidth, performance per watt and per cost | section 6 |
Shared memory or message passing: same power, different price
Question 4 hides a surprise. With shared memory a processor communicates by storing to an address that another one later loads from; nobody sends anything. With message passing it calls send and the other calls receive. Different worlds — yet each can be built out of the other:
The sender writes the message into a buffer in shared memory, then sets a flag. The receiver waits until the flag is set and reads the buffer. A send is a few stores, a receive a few loads.
One process owns the data. A load becomes a request message to the owner, who replies with the value; a store becomes a message carrying the new value. A load is one send and one receive.
So neither model is more powerful than the other: both are Turing complete (footnote 11, p. 418) — each can compute anything a Turing machine (an endless tape, a read/write head and a table of rules) can compute. "Choosing shared memory vs. message passing does not limit what can be computed, only how" (p. 419). The difference is practicality: performance, programmability, ease of reasoning. Shared memory is natural to program but needs coherence hardware; message passing needs simpler hardware but makes the programmer move every byte (lesson 34).
One bus for everyone — until it is full
Start with the simplest wiring, the one the notes draw first (Fig. 31, p. 422): every processor, with its cache, hangs on a single bus, and so do the main memory and the I/O system. Every cache miss of every processor becomes a transaction on it, and it carries one transaction at a time.
Before: one bus, one transfer at a time
After: a network, several transfers at once
Count what that means. Suppose a processor running alone keeps the bus busy a fraction \(d\) of the time — say one miss every 100 ns, each holding the bus for 2.8 ns, so \(d = 2.8\%\), a value picked here to land on the notes' number. Two such processors keep it busy 5.6% of the time, ten 28%. A bus cannot be busier than 100%, so it carries the traffic of at most
\[ P_{\max} \approx \frac{1}{d} = \frac{1}{0.028} \approx 36 \]processors. That is how a bus ends at the notes' "≈36 processors" (p. 420): not a law of nature, but the capacity of the bus divided by the demand of one processor.
Below the ceiling most requests find the bus free, so throughput grows almost linearly. Near it requests queue; past it each new processor brings a customer and no capacity, so throughput flattens and every access waits longer. The hardware adds a second reason (background, not in the notes): every device loads the wires electrically, so a bus built for more slots runs a slower clock.
The notes' cost/performance trade-off (p. 420) puts prices on the picture. Past its sweet spot the bus "plateaus regardless of added CPUs"; a network is "initially costlier (switches, links)" but keeps the performance per processor roughly constant, so it will "always win once the bus reaches its plateau". Hence small SMPs of 4–16 cores ruled desktops and servers, while large HPC systems adopted meshes, tori and fat trees.
The bus is not dead, though. Its weakness is also its strength: because everyone shares it, everyone hears every transaction — exactly what a snooping coherence protocol needs (lesson 35).
Network-connected multiprocessors
The alternative is an interconnection network: many point-to-point links joined by switches, so that transfers on different links proceed at once (Fig. 1, right). It takes the bus off the critical path and "can scale to many more processors" (p. 420). The notes' description of it needs a correction:
Which number tells the truth: total and bisection bandwidth
To compare networks you need numbers. Take the notes' 8-node ring (p. 423) with \(b = 1\) GB/s per link. If every node talks to a neighbour, all 8 links work at once: 8 GB/s. Now run a fire drill: the four nodes on the left each send to a partner on the right, at the same moment. Whatever routes they take, all that traffic must squeeze through the links that join the two halves — 2 of them. The network moves 2 GB/s.
Total bandwidth: count every link
Bisection bandwidth: count the links the cut crosses
Those two numbers are the canonical metrics of the notes (p. 421):
Total network bandwidth (best case) — the sum of the bandwidths of all links: "the maximum aggregate throughput that the network could deliver if all links were used simultaneously and were perfectly balanced".
Bisection bandwidth (worst case) — "the minimum total bandwidth of links that must be cut to split the network into two equal halves (each with half the nodes)".
\[ \text{Total BW} = M \times b \]
\[ \text{Bisection BW} = \min_{\text{cuts}} \sum_{\text{crossing links}} b \]
- \(M\)
- number of links in the network
- \(b\)
- bandwidth of one link (GB/s)
- cuts
- every way of splitting the \(P\) nodes into two halves of \(P/2\)
Why the minimum? Because different splits cross different numbers of links: split the 8-node ring into its odd and its even nodes and all 8 links cross; split it into two arcs and only 2 do. The narrowest passage decides, so "we have to try all possible cuts and select the smallest one" (p. 421) — the notes' "any cut crosses 2 links" means a cut through the ring as drawn. The minimum is a hard limit: if each of the \(P/2\) nodes on one side sends \(m\) bytes across, the transfer takes at least
\[ t \ge \frac{(P/2)\, m}{\text{Bisection BW}} , \]however fast the rest of the network is. Apply both definitions to the bus: it is one link, so its total bandwidth is \(b\); a cut through it severs that link, so its bisection is \(b\) as well. On a bus the best case is the worst case.
"The bisection bandwidth is half the total." No: the 64-node ring has a total of \(64b\) and a bisection of \(2b\).
Two more numbers, which the notes use ("logarithmic diameter", p. 424) but never define, complete every comparison of networks (Hennessy & Patterson, Appendix F). The diameter is the largest, over all pairs of nodes, of the number of links on the shortest path between them; every link is a hop through a switch, so the diameter measures the worst-case latency. The degree is the number of links per node, the ports of its router, so it measures cost. The 8-node ring has diameter 4 and degree 2.
Total bandwidth is the best case, neighbours talking; bisection bandwidth is the worst case, half the machine talking to the other half — and the worst case is the one that bounds global traffic.
The classic topologies, by counting and cutting
A topology is "the way processors and memories are interconnected" (p. 422): it sets how processors communicate (direct neighbours or global links), how far the system scales and what it costs in wires and switches. The notes give five classic ones, studied since the 70s–90s and still behind today's networks-on-chip and HPC interconnects. Their formulas need no memorising: each follows from two moves, count the links and cut the network in half.
Try both on the notes' Figure 32 (p. 424), a 4 × 4 mesh: four rows of 3 horizontal links and four columns of 3 vertical ones make 24 links, and a cut between the two middle columns crosses one link per row, 4 links — exactly the notes' numbers. The stepper repeats the two moves for every topology.
Ring, count. Each of the \(P\) nodes has 2 links and each link has 2 ends, so counting ends counts every link twice:
\[ M = \frac{2P}{2} = P \] \[ \text{BW}_{\text{total}} = P\,b \]Ring, cut. Split the loop into two arcs of \(P/2\) nodes. Walking round a closed loop you pass from one half to the other an even number of times, at least twice — and two arcs need exactly two cuts, wherever they fall:
\[ \text{BW}_{\text{bisect}} = 2b \]Mesh, count. \(N = \sqrt{P}\) rows, each with \(N - 1\) horizontal links, and \(N\) columns, each with \(N - 1\) vertical links:
\[ M = 2N(N-1) \]Mesh, cut. Cut between the two middle columns (\(N\) even): one horizontal link per row crosses, and no balanced cut crosses fewer.
\[ \text{BW}_{\text{bisect}} = N\,b = \sqrt{P}\,b \]Hypercube, count. \(P = 2^N\) nodes, each with \(N\) links, every link counted from both ends:
\[ M = \frac{N P}{2} \]Hypercube, cut. Cut along the top address bit: the two \((N-1)\)-cubes of the doubling (Fig. 3) fall apart, and each node loses exactly one link, the one to its twin. \(P\) nodes, two ends per link:
\[ \text{BW}_{\text{bisect}} = \frac{P}{2}\, b = 2^{N-1}\, b \]Fully connected, count and cut. One link for every pair of nodes; and each of the \(P/2\) nodes of one half has its own link to each of the \(P/2\) nodes of the other:
\[ M = \frac{P(P-1)}{2} \] \[ \text{BW}_{\text{bisect}} = \Big(\frac{P}{2}\Big)^2 b \]
| Topology | Total BW | Bisection BW | Diameter | Ports per node | \(P = 16\) |
|---|---|---|---|---|---|
| single bus | \(b\) (89) | \(b\) (90) | 1, shared | 1 | 1 / 1 |
| ring | \(P\,b\) (91) | \(2b\) (92) | \(P/2\) | 2 | 16 / 2 |
| 2-D mesh, \(N = \sqrt{P}\) | \(2N(N-1)\,b\) (95) | \(N\,b\) (96) | \(2(N-1)\) | 2 to 4 | 24 / 4 |
| hypercube, \(P = 2^N\) | \((NP/2)\,b\) (97) | \((P/2)\,b = 2^{N-1} b\) (98, corrected) | \(N = \log_2 P\) | \(N\) | 32 / 8 |
| fully connected | \(P(P-1)/2 \cdot b\) (93) | \((P/2)^2\, b\) (94) | 1 | \(P - 1\) | 120 / 64 |
| 2-D torus (extra), \(N\) even | \(2P\,b\) | \(2N\,b\) | \(N\) | 4 | 32 / 8 |
| crossbar switch (extra) | \(P\,b\) | \((P/2)\,b\) | 1 switch | 1 | 16 / 8 |
| Topology | Pro | Con |
|---|---|---|
| single bus | cheap, simple | very low scalability; saturates quickly |
| ring | good best-case parallelism | worst case only 2× bus |
| 2-D mesh | good scalability; cost-effective | multiple hops increase latency |
| hypercube | very good connectivity; logarithmic diameter | wiring complexity grows |
| fully connected | non-blocking; high performance | very high cost, growing as \(P^2\) |
The hypercube deserves a picture: its formula is the one the notes get wrong. An \(N\)-dimensional hypercube is built by doubling: take two copies of the \((N-1)\)-cube and join every node to its twin in the other copy — the node whose \(N\)-bit address differs only in the top bit.
Before: two 2-cubes, 4 + 4 links
After: join every node to its twin, 4 new links
The fully connected network wins every bandwidth contest: diameter 1 and a bisection that grows as \(P^2\). Its price grows as \(P^2\) too — \(P(P-1)/2\) cables and \(P - 1\) ports on every node, "very high cost" (p. 423). The notes file it under another name.
Fully connected: a cable for every pair
Crossbar: one switch with \(P^2\) crosspoints
Beyond the five
Three more shapes complete the map; the notes only name two of them. The 2-D torus is the mesh plus wrap-around links joining the ends of every row and column: \(2P\) links, a bisection of \(2N\) links — twice the mesh's — and about half its diameter; three-dimensional tori connected the nodes of Cray XT and IBM Blue Gene supercomputers. A tree connects \(P\) nodes cheaply, with \(P - 1\) small switches, but has a bisection of one link, at the root; the fat tree thickens the links towards the root and recovers \(P/2\), which made it the standard fabric of HPC clusters.
Tree: everything crosses at the root
Fat tree: thicker links towards the root
Why, then, do real chips use rings and meshes rather than hypercubes? A chip is flat. A ring or a mesh lies on it with short wires of equal length, and its degree stays 2 or 4 however many cores you add, while a hypercube needs ever longer wires and more router ports. So Intel's client processors link their cores with a ring, and its Xeon Scalable server chips, like Tilera's, with a 2-D mesh.
What the extra processors are worth — and the two puzzles solved
Design question 10 asked how to evaluate a multiprocessor. Two examples from Hennessy & Patterson (§5.1, not in the notes; the numbers vary between editions) show what eats the speedup even with a perfect network: the serial part of the program, and the time to reach remote data.
The serial part: Amdahl with \(P\) processors
Amdahl's law (lesson 3) with the enhancement "run on \(P\) processors" has \(S = P\). Hennessy and Patterson ask: to reach a speedup of 80 with 100 processors, what fraction of the original computation may be sequential?
Amdahl's law with \(S = P\): the fraction \(F\) runs \(P\) times faster, the rest, \(1 - F\), does not.
\[ \text{Speedup}(P) = \frac{1}{(1-F) + \dfrac{F}{P}} \]Put in the target, 80, and \(P = 100\); then turn both sides upside down:
\[ (1-F) + \frac{F}{100} = \frac{1}{80} = 0.0125 \]Collect the terms in \(F\), since \(1 - F + 0.01F = 1 - 0.99F\):
\[ 1 - 0.99\,F = 0.0125 \]Solve, and read the sequential fraction as what is left:
\[ F = \frac{0.9875}{0.99} = 0.99747 \] \[ 1 - F = 0.0025 = 0.25\% \]
A quarter of a percent: one part in four hundred of the original time may stay serial, and even then the 100 processors deliver only 80. Gustafson's law, which the notes name on p. 419, looks at it the other way round: let the problem grow with the machine, and the scaled speedup is \((1 - F) + F \cdot P\), with \(F\) measured on the parallel machine.
The remote access: 0.2% of the instructions, 160% more time
The second example is a 32-processor machine with distributed memory, a 4 GHz clock and a base CPI of 0.5 when every reference hits locally. A reference to remote memory takes 100 ns and stalls the processor, and 0.2% of the instructions make one. How much faster would the machine be without remote references? With \(T_{CLK} = 1/f_{CLK} = 0.25\) ns:
\[ \frac{t_{\text{remote}}}{T_{CLK}} = \frac{100\ \text{ns}}{0.25\ \text{ns}} = 400 \]
\[ CPI = 0.5 + 0.002 \times 400 = 1.3 \]
- \(t_{\text{remote}}\)
- time of one remote access; divided by \(T_{CLK}\) it is the stall in clock cycles
- \(0.5\)
- base CPI, every reference local
- \(0.002\)
- remote references per instruction (0.2%)
Without them the CPI would be 0.5: the machine would run \(1.3 / 0.5 = 2.6\) times faster. Two remote references in a thousand instructions add 160% to the execution time — where the data lives matters as much as the wiring, the subject of the next lesson.
The two puzzles, solved
The 37th processor. Every miss crosses the bus, and the bus is a single link: its total bandwidth and its bisection are the same \(b\). At 2.8% per processor, 36 processors nearly fill it; in the widget the 37th adds half a processor's throughput and makes every bus access slower for all 37. A faster bus only moves the wall; a network moves the limit to its bisection, which can grow with \(P\).
The ring. Its 64 links give a total of \(64b\), but the cheapest balanced cut crosses only 2 of them: a bisection of \(2b\), twice the bus's — the notes' "only 2× bus". The other 62 links help neighbours, not halves.
When half of a machine talks to the other half, only the links across the narrowest cut count: bisection bandwidth is the honest number, and a bus is simply a network whose bisection is one link.
Exam-style questions
Explain the main concepts and benefits of each one of the following:
- Multiprocessor (tightly coupled, MIMD)
- Multicore and manycore processors
- Symmetric multiprocessors (SMP)
- Large-scale distributed shared-memory multiprocessors
- Shared-memory and message-passing communication
- Single-bus interconnection
- Interconnection networks
- Bisection bandwidth
Show model answer
1. A multiprocessor is a computer system with tightly coupled processors coordinated by a single operating system, typically offering a shared address space. Each processor runs its own instruction stream on its own data (MIMD), so the machine exploits thread-level parallelism. Benefits: high throughput on many threads or processes, performance that grows with the number of processors, tolerance of some faults through redundancy, one design from embedded systems to servers. Unlike a cluster, it has one OS and one address space.
2. A multicore puts several cores on the same chip; beyond about 32 cores it is called a manycore. A multicore chip is a small SMP on a chip: private L1/L2 caches, usually a shared last-level cache, uniform access to memory, snooping coherence. Benefit: it turns the transistor budget into throughput through TLP — the industry's answer to the ILP and frequency (power) walls — instead of a wider or faster single core.
3. In an SMP (centralized shared memory) all processors share one physical memory with the same access time for everyone (UMA), usually through a bus; cache coherence is kept by snooping. Benefits: simple, symmetric view for the programmer and the OS, cheap for a few processors. Limit: the shared bus and memory saturate, so SMPs typically stay at or below about 32 processors.
4. In a distributed shared-memory (DSM) multiprocessor the memory is physically distributed among the nodes (processor + caches + local memory module) connected by an interconnection network, but forms one shared address space. Access time is non-uniform (NUMA): local is fast, remote is slower. Benefits: it scales beyond about 32 processors because memory bandwidth grows with the nodes and there is no single memory bottleneck, and it is still programmed with loads and stores. Costs: data placement matters, coherence needs directories, the network is complex.
5. With shared memory, processors communicate implicitly by loads and stores to a common address space: natural to program, but it needs coherence hardware and explicit synchronization (locks, barriers). With message passing, each processor has a private address space and communicates explicitly with send and receive: simpler hardware, explicit control of data movement, harder programming. Both models are Turing complete and each can implement the other, so the choice affects performance, programmability and cost, not what can be computed.
6. All processors, the memory and the I/O share one bus; every memory access (cache miss) is a bus transaction, one at a time. Benefits: cheap, simple, and a broadcast medium — every cache sees every transaction, which snooping coherence needs. Drawback: saturation. If each processor alone uses a fraction d of the bus, throughput grows linearly and then flattens near 1/d processors (commercial systems maxed out at about 36); beyond that, adding a processor only lengthens the queue and slows every access.
7. An interconnection network connects the nodes with many point-to-point links and switches (ring, 2-D mesh, torus, hypercube, crossbar, fat tree), so many transfers proceed in parallel and the bandwidth grows with the system. Benefits: it removes the shared bus from the critical path and scales to hundreds or thousands of processors. Costs: switches and links are expensive, and multiple hops add latency. Networks are compared by total and bisection bandwidth, diameter and node degree.
8. Bisection bandwidth is the minimum, over all cuts that split the network into two halves with equal numbers of nodes, of the total bandwidth of the links crossing the cut. It is the worst case, when half of the nodes communicate with the other half, and it bounds global traffic, while the total bandwidth (M × b, the sum of all links) is the best case for local traffic. Examples: bus b, ring 2b whatever P, 2-D mesh √P·b, hypercube (P/2)·b.
The 2026 paper asks its 8-point question in this form, "Explain the main concepts and benefits of each one of the following …", with five lines for each sub-point; multiprocessors and multicores are an item of the course's topic list. What earns the points: the defining words (tightly coupled, single OS, shared address space, MIMD; UMA and NUMA; implicit versus explicit communication; one transaction at a time; best case versus worst case) and a cost next to every benefit. Sub-point 6 is stronger with the 1/d argument than with the bare number 36.
Consider a multiprocessor with P = 16 nodes whose interconnection links each have a bandwidth b = 1 GB/s. Complete the following table, then explain which topology you would choose if the 16 processors communicate all-to-all, and why.
| Topology | Links | Total BW | Bisection BW | Diameter | Ports per node |
|---|---|---|---|---|---|
| Single bus | |||||
| Ring | |||||
| 2-D mesh (4 × 4) | |||||
| Hypercube (N = 4) | |||||
| Fully connected |
Show model answer
| Topology | Number of links | Total bandwidth | Bisection bandwidth | Diameter | Ports per node |
|---|---|---|---|---|---|
| Single bus | 1 | b = 1 GB/s | b = 1 GB/s | 1 (shared) | 1 |
| Ring | P = 16 | P·b = 16 GB/s | 2b = 2 GB/s | P/2 = 8 | 2 |
| 2-D mesh (4 × 4) | 2N(N − 1) = 24 | 24 GB/s | N·b = 4 GB/s | 2(N − 1) = 6 | 2 to 4 |
| Hypercube (N = 4) | NP/2 = 32 | 32 GB/s | (P/2)·b = 8 GB/s | N = 4 | 4 |
| Fully connected | P(P − 1)/2 = 120 | 120 GB/s | (P/2)²·b = 64 GB/s | 1 | 15 |
All-to-all traffic crosses the machine, so it is bounded by the bisection bandwidth, not by the total. The fully connected network has the largest bisection (64 GB/s) and diameter 1, but needs 120 links and 15 ports per node. The hypercube gives 8 GB/s of bisection, so every node can send across the cut at its full link speed (8 GB/s for 8 senders), with only 32 links, 4 ports per node and a diameter of 4: the usual engineering choice at this size. The mesh is cheaper but has half the bisection and diameter 6; the ring and the bus would be throttled to 2 and 1 GB/s.
An exercise in the style of the papers' tables. The two traps: the hypercube bisection (8, not the 6 of the notes' eq. 98) and confusing the total with the bisection when the question is about global traffic. Write the formula before the number in each cell — a correct formula with a slip in the arithmetic is still worth most of the cell.
A 32-processor distributed shared-memory multiprocessor runs at a clock frequency of 4 GHz. Its base CPI, when every memory reference is satisfied locally, is 0.5. A reference to remote memory takes 100 ns and stalls the processor. If 0.2% of the instructions make a remote reference, what is the CPI of the machine?
Show model answer
\[ T_{CLK} = \frac{1}{4\ \text{GHz}} = 0.25\ \text{ns} \]
\[ \text{remote cost} = \frac{100}{0.25} = 400 \text{ cycles} \]
\[ CPI = 0.5 + 0.002 \times 400 = 1.3 \]
Without remote references the machine would be 1.3 / 0.5 = 2.6 times faster.
The example comes from Hennessy & Patterson. The marks are in converting the 100 ns into clock cycles (400, not 100 or 0.4) and in weighting the stall by the fraction of instructions that pay it: 0.2% is 0.002, not 0.2.
You want a speedup of 80 on a multiprocessor with 100 processors. According to Amdahl's law, what is the largest fraction of the original execution time that may remain sequential? Give the answer in percent.
Show model answer
\[ 80 = \frac{1}{(1-F) + F/100} \]
\[ 1 - 0.99\,F = 0.0125 \]
\[ F = 0.99747, \quad 1 - F \approx 0.25\% \]
The formula sheet's Amdahl's law with S = P. The answer asked for is the sequential fraction 1 − F, not F: answering 99.75% is the classic lost point. The form F = (1 − 1/Speedup)/(1 − 1/S) from lesson 3 gives the same number in one line: 0.9875 / 0.99.
Which of the following statements about the bisection bandwidth of an interconnection network are true? (Multiple answers)
Show model answer
Answers 2, 3 and 4. Answer 1 describes the total bandwidth; the mesh bisection is N·b = √P·b, which grows as the square root of P.
The family of statements mixes the two metrics on purpose. Check each against the ring and the bus, the two cases you can draw in a second.
A hypercube interconnects P = 64 nodes with links of bandwidth b = 1 GB/s. What is its bisection bandwidth? (Single answer)
Show model answer
Answer 3: N = log₂64 = 6, bisection = 2^(N−1)·b = (P/2)·b = 32 GB/s; the total is N·P/2·b = 192 GB/s.
The distractors are the notes' wrong formula (10), the total (192) and a double count (64). The quickest route is the doubling picture: a 6-cube is two 5-cubes joined by 32 links.
In a single-bus multiprocessor, each processor running alone keeps the bus busy 4% of the time. True or false: however many processors are attached, the machine cannot deliver more than the throughput of 25 such processors running alone.
Show model answer
True. Throughput ≤ bus capacity / demand per processor = 1 / 0.04 = 25 processors' worth; near that point the bus is saturated and every further processor only lengthens the queue for the bus.
The ceiling is capacity divided by demand, the same argument that gives the notes' ≈ 36. Halve the traffic per processor (bigger caches) and the ceiling doubles.
Check yourself
A 16-node 2-D mesh (4 × 4) is replaced by a 64-node one (8 × 8) with the same links. What happens to the bisection bandwidth?
Which of these machines are multiprocessors in the sense of the notes?
The test is the definition: tightly coupled processors, a single OS, typically one shared address space.
Why does the bisection bandwidth of a ring stay \(2b\) however many nodes it has?
Each processor of a bus-based SMP keeps the bus busy 5% of the time when it runs alone. Larger L2 caches halve its misses. What happens to the number of processors the bus can feed?
For \(P = 64\) nodes, which network has the larger bisection bandwidth: a crossbar switch or a 6-dimensional hypercube?
Which statement about shared memory and message passing is right?
In the remote-access example (4 GHz, base CPI 0.5, 0.2% remote references), a better network cuts the remote access time from 100 ns to 50 ns. What is the CPI now?
Key take-aways
- A multiprocessor is a set of tightly coupled processors under a single operating system, usually with one shared address space; it is MIMD and exploits thread-level parallelism for throughput, scalability, reliability and versatility.
- The three scales are the multicore chip, the SMP (centralized memory, UMA, snooping, up to about 32 processors) and the large-scale DSM (distributed memory, NUMA, directories).
- Ten design questions shape every multiprocessor; shared memory and message passing are both Turing complete, so choosing between them changes cost, latency and programming effort, not what can be computed.
- A single bus serves one miss at a time: throughput grows linearly up to about \(1/d\) processors and then flattens, and past the knee each new processor slows every access; networks cost more per node but keep scaling.
- Total bandwidth (\(M \times b\)) is the best case for local traffic; bisection bandwidth (the narrowest balanced cut) is the worst case and bounds global traffic; diameter measures latency and degree measures cost.
- Count and cut (total / bisection): bus \(b\) / \(b\), ring \(Pb\) / \(2b\), mesh \(2N(N-1)b\) / \(Nb\), hypercube \((NP/2)\,b\) / \((P/2)\,b\) (not \(2(N-1)b\)), fully connected \(P(P-1)/2 \cdot b\) / \((P/2)^2 b\); a crossbar is a switch with \(P^2\) crosspoints and a bisection of \((P/2)\,b\).
- Even with a perfect network, a speedup of 80 on 100 processors allows only 0.25% serial work, and 0.2% of instructions going to 100 ns remote memory raise the CPI from 0.5 to 1.3.
What to watch and read
-
Lecture 27: Multiprocessors (Computer Architecture, Carnegie Mellon, 2015)
Onur Mutlu
Why multiprocessors, the MIMD design space, shared memory against message passing, tightly against loosely coupled — the frame of this lesson and the next, drawn on the board.
-
Appendix F: Interconnection Networks (Computer Architecture: A Quantitative Approach, 6th ed.)
T. M. Pinkston and J. Duato, in Hennessy & Patterson
Section F.4, Network Topology: bus, ring, mesh, torus, hypercube and fat tree with degree, diameter and bisection bandwidth — the source of every metric of this lesson, including the two the notes leave out.
-
Lecture 22: Interconnects II (ETH Zürich, Fall 2017)
Onur Mutlu
Topologies compared on cost, latency and bisection bandwidth, then routing and flow control: what happens inside the links you counted.
-
Some Computer Organizations and Their Effectiveness
Michael J. Flynn, IEEE Transactions on Computers, 1972
Flynn's classification (first proposed in 1966) in its refined form, and the source of the "saturation syndrome" quoted in section 3 — the bus problem, seen in 1972.