Multiprocessor Systems

A multiprocessor interconnects two or more CPUs with memory and I/O under one cooperating system. It is normally MIMD: processors execute different instruction streams on different data. Multiple autonomous computers linked only as a general network are not automatically one multiprocessor; the distinction is coordinated resource management and cooperation on system work.

Why Multiple Processors?

• Throughput: run independent jobs concurrently.
• Speedup: partition one job into parallel tasks whose dependencies permit overlap.
• Specialization: assign computation, I/O, signal processing, or control to suitable processors.
• Reliability: continue with reduced performance when one processor fails.
• Growth: add processing resources when the organization and software can scale.

Parallelizing software must identify data dependencies. Tasks that consume another task’s results must wait; independent tasks can be scheduled on different processors. More processors do not automatically yield proportional speedup because sequential work, communication, synchronization, and memory contention remain.

Amdahl’s law makes the limit numerical. If fraction $f$ of a program can use $p$ processors, ideal speedup is

$S=\frac{1}{(1-f)+f/p}.$

With $f=0.80$ and $p=4$, $S=1/(0.20+0.20)=2.5$, not four. The untouched 20% sets a hard ceiling of $1/(1-f)=5$ even with unlimited processors.

Shared and Distributed Memory

A processor element in a distributed system contains CPU, local memory, and I/O. A packet names a destination or service and carries content plus error-detection information.

Time-Shared Common Bus

A bus master places an address and command on the bus; the addressed unit responds and data transfer follows. With several potential masters, arbitration chooses one requester. The common path is inexpensive and easy to broadcast/snoop, but its bandwidth limits scale.

A dual-bus organization attaches each CPU/IOP and local memory to a local bus, then uses a system-bus controller to reach common memory and shared I/O. Address decoding distinguishes local from global references. Adding fully independent buses allows simultaneous transfers but increases wiring and control cost.

Multiport Memory and Crossbar

In multiport memory, each CPU has a bus to a dedicated port on every module. A module resolves simultaneous requests to itself, often by fixed port priority. Different CPUs can access different modules concurrently. Transfer rate is high, but multiported modules, cables, and connectors are expensive.

An $p\times m$ crossbar contains $pm$ crosspoints. Each addressed module selects one requesting processor through data, address, and control multiplexers plus arbitration. For four CPUs and four modules, 16 crosspoints allow up to four concurrent transfers when every CPU selects a different module. Requests for the same module still conflict.

Multistage Networks

A 2×2 interchange switch can pass inputs straight, cross them, or connect one requester while blocking a conflict. Networks of these switches provide many paths with less hardware than a crossbar.

An $N\times N$ omega network for $N=2^n$ has $\log_2N=n$ stages and $N/2$ switches per stage, so total switches are

$\frac N2\log_2N.$

An 8×8 omega network has three stages of four switches, or 12 switches, far fewer than a 64-crosspoint crossbar. It offers exactly one path from a source to a destination, so some otherwise independent pairs block when they require the same internal link.

A binary $n$-cube has $N=2^n$ nodes, each with $n$ direct neighbors. Neighbor addresses differ in one bit. Routing from source $s$ to destination $d$ can use $s\oplus d$: each 1 identifies a dimension that must be traversed. In a three-cube, 010 to 001 gives 011; one shortest route is 010 → 000 → 001.

Bus Arbitration

Arbitration must provide mutual exclusion of bus ownership and a priority/fairness policy.

Static priority

• Serial/daisy chain: priority-in/out passes through arbiters in fixed order. The first requester with priority and an idle bus captures it.
• Parallel: request lines feed a priority encoder; a decoder enables the winning acknowledge. It is faster but requires centralized logic and more wires.

Common signals include bus priority in/out, common bus request, bus busy, individual bus request/acknowledge, and a bus clock.

Dynamic priority

Static priority gives predictable latency to favored devices but can starve low-priority ones. Dynamic schemes improve fairness with additional state.

Communication and Operating-System Organization

In shared memory, processors can exchange messages through a mailbox: data plus status bits indicating valid content and destination. Polling finds messages eventually; a software-generated interprocessor interrupt alerts the receiver immediately. Other paths can link IOPs so each CPU treats the other side like an I/O device.

Operating-system responsibilities may be organized as:

• Master–slave: one processor executes OS services; slaves request them.
• Separate OS: every processor has its own OS copy, suitable for loosely coupled nodes.
• Distributed/floating OS: functions are distributed and may migrate, but one processor owns a particular function at a time.

Distributed-memory communication names source and destination, establishes or selects a route, and sends a message header plus objects. Efficiency depends on topology, routing protocol, processor speed, and link bandwidth.

Synchronization and Mutual Exclusion

Communication exchanges data; synchronization exchanges control information to order events. A critical section accesses shared writable state and must execute with mutual exclusion.

A binary semaphore SEM uses 0 for available and 1 for held. Merely reading and later writing it is unsafe: two CPUs could both read zero. A test-and-set-while-locked instruction performs atomically:

If returned $R=0$, this processor acquired the resource; if $R=1$, another owns it. The hardware lock needs to cover only the indivisible read-modify-write. The semaphore remains one until the owner completes the critical section and stores zero.

repeat:
    old ← test_and_set(SEM)
until old == 0
critical section
SEM ← 0

This spin lock is suitable only for short waits. Longer waits should block and let the scheduler run another task.

Cache Coherence

Private caches may hold copies of the same shared address. If core 1 writes X=9 while core 2 keeps cached X=4, core 2 can compute with stale data unless the coherence mechanism acts.

Every cache controller snoops shared-bus transactions for blocks it holds. Coherence has two obligations: propagate a processor’s write and determine which copy may supply the current value.

• Write-invalidate: a writer obtains ownership and broadcasts invalidation; other caches mark their copies invalid. Later readers miss and fetch the new value.
• Write-update: a writer broadcasts the new data so other cached copies update. This generates traffic on every write, similar in spirit to write-through.

Coherence concerns one memory location’s copies. Consistency is the broader rule for when writes to different locations become visible and in what order.

Bus Multiprocessors, Networks, and Clusters

A shared bus has low cost, simple protocols, and efficient broadcast, but one path and one memory module impose bandwidth limits. Caches reduce average latency and bus traffic, yet misses and coherence transactions still consume the bus. Networks provide aggregate bandwidth and many simultaneous routes for larger systems.

A cluster is a group of complete computers connected by a fast local network and configured to work as one service or computational resource.

A shared-address multiprocessor can let one program use almost all installed memory, while a cluster has independent node memories. Conversely, cluster failure isolation and incremental growth can be stronger.

Memory interleaving complements either design: consecutive shared addresses distributed over modules raise bandwidth, but it does not by itself solve cache coherence or synchronization.

Check Your Understanding

1. How many crosspoints connect 8 CPUs to 16 memory modules?
2. How many stages and total 2×2 switches does a 16×16 omega network need?
3. Which nodes neighbor 101 in a three-cube?
4. Why must test-and-set be indivisible?
5. What happens to core 2’s copy after core 1 writes under write-invalidate?