8.2 Multicomputers: Hardware, RPC, DSM & Scheduling

8.2.1 Multicomputer Hardware & Interconnect Topologies

A multicomputer is a tightly coupled parallel computing system composed of multiple autonomous computers (nodes). Unlike shared-memory multiprocessors, multicomputer nodes share no physical memory and cannot directly execute atomic bus transactions or hardware cache-snooping across nodes. Each node runs its own local operating system kernel with private RAM and coordinates strictly via message exchange across an interconnection network.

Direct Interconnection Topologies

The communication network topology determines scaling properties, routing latency, and contention. Four canonical topologies characterize multicomputer fabrics:

Topology	Node Degree	Network Diameter	Bisection Bandwidth	Properties
Ring	2	\lfloor n / 2 \rfloor	2 links	Simple wiring; prone to single-link bottlenecks and high hop counts.
2D Mesh / Grid	4 (interior)	2(\sqrtn - 1)	\sqrtn links	Planar mapping to silicon substrates; perimeter nodes have boundary penalties.
2D Torus	4	2 × \lfloor \sqrtn / 2 \rfloor	2\sqrtn links	Wraparound edges create symmetry; every node observes identical topology.
k-ary d-cube (Hypercube)	d = \log₂ n	d = \log₂ n	n / 2 links	Logarithmic diameter growth; excellent fault paths; high cable complexity.

Figure 8-2: Multicomputer Interconnect Topologies.

Store-and-Forward vs. Wormhole Routing

Store-and-Forward: When a message traverses a path of intermediate routers, each router buffers the complete packet in local RAM before inspecting the header and transmitting it to the next link. Latency is proportional to:
Latency = h × ≤ft( \fracPacket SizeBandwidth + Routing Delay \right)
where h is the number of hops. Long messages traveling across multiple hops incur significant queuing delay.
Cut-Through & Wormhole Routing: Packets are divided into small, fixed-size flow control units called flits. The router inspects the header flit and immediately establishes an outgoing circuit switch. Subsequent payload flits follow in a pipelined fashion behind the header across intermediate links. If the header flit blocks due to link contention, the remaining body flits stall in-place across the traversed links, forming a "worm" through the fabric. Latency is largely decoupled from distance:
Latency ≈ \fracPacket SizeBandwidth + h × (Flit Delay)

Routing Simulation: Store-and-Forward vs. Wormhole

Simulate a 4-flit packet traversing 3 router hops (Node 0 → Router 1 → Router 2 → Dest 3):

Node 0
[H][F1][F2][T]

→

Router 1
[empty]

→

Router 2
[empty]

→

Dest 3
[empty]

-- Select a routing algorithm to compare pipeline cycles --

8.2.2 & 8.2.3 Low-Level vs. User-Level Communication Software

In traditional operating systems, network communication relies on kernel mediation. A send() system call copies payload data from user space into a kernel socket buffer, attaches protocol headers, programs the network interface controller (NIC) via DMA descriptors, and awaits an interrupt on completion.

The Kernel Crossing Bottleneck

For modern 100+ Gbps interconnects, the latency of kernel traps, context switches, and CPU data buffer copies dwarfs the actual wire transmission latency. Two design models contrast:

Dimension	Traditional Kernel-Mediated I/O	User-Level Zero-Copy Interface (RDMA)
Control Path	System call trap on every transmission (Ring 3 → Ring 0).	Memory-mapped doorbells; application posts directly to NIC.
Memory Copies	User buffer → Kernel buffer → NIC DMA buffer (2–3 copies).	Zero copies; NIC DMAs directly from pinned user memory pages.
Interrupts	Interrupt Service Routine (ISR) executed per packet.	Completion queues polled in user space; interrupts avoided.
Protection	Enforced by kernel checking file descriptors.	Hardware protection keys enforced directly by NIC translation tables.

8.2.4 Remote Procedure Call (RPC)

Pioneered by Birrell and Nelson (1984), Remote Procedure Calls (RPC) bridge the programming gap between local procedural invocation and message passing. The core design goal is syntactic transparency: making a remote procedure call look identical to a standard local call in the high-level language.

Figure 8-3: The Complete Remote Procedure Call Pipeline.

RPC Mechanics: Stubs & Marshalling

The client calls a local proxy procedure called the Client Stub using standard calling conventions (parameters on stack or registers).
The Client Stub converts the parameters into a standardized network format (e.g., Big-Endian network byte order, JSON, or protocol buffers). This translation is called Parameter Marshalling.
The client OS kernel transmits the request message to the server node over the network.
The server OS receives the packet and dispatches it to the Server Stub (or skeleton).
The Server Stub unmarshalls the arguments from the message buffer, sets up a normal local procedure call frame, and calls the real worker procedure.
The worker executes, produces a result, and returns to the Server Stub.
The Server Stub marshalls the return value and transmits the response back through the client stub to unblock the original caller.

8.2.5 Distributed Shared Memory (DSM)

Pioneered by Kai Li (1986), Distributed Shared Memory (DSM) emulates a single, shared virtual address space across a collection of disjoint multicomputer nodes using standard MMU paging hardware and network message passing.

Page-Based DSM Operation

Virtual address space is divided into uniform pages (e.g., 4 KiB). When CPU 0 references a page currently mapped locally, the memory access completes at full hardware RAM speed without network latency.

Read Fault: If CPU 1 reads page P which is currently unmapped locally, the MMU triggers a page fault. The OS fault routine intercepts the trap, issues a network request to the node holding page P, maps the page as read-only on both nodes, and resumes execution.
Write Fault & Invalidation: If CPU 1 attempts to write to page P (currently mapped as read-only), the MMU raises a protection fault. The local DSM layer sends an invalidation message to all other nodes holding copies of page P, marks its own copy as read-write, and completes the write.

The False Sharing Trap: Unlike hardware cache coherence which operates at 64-byte cache line granularity, page-based DSM operates at page granularity (typically 4096 bytes). If variable A and variable B reside on the exact same 4 KiB page, and Node 0 repeatedly writes A while Node 1 repeatedly writes B, the entire 4 KiB page will continuously bounce back and forth across the network. Even though the processes touch independent variables, performance collapses due to false sharing.

Interactive Page-Based DSM Simulator

Observe virtual page replication, write invalidations, and false sharing across two independent nodes sharing Page 12 (containing Variables A and B):

Node 0 Memory State: Read-Only [Shared]

Page 12: Var A = 10, Var B = 20

Node 1 Memory State: Read-Only [Shared]

Page 12: Var A = 10, Var B = 20

-- DSM Initialized. Page 12 shared read-only across both nodes. --

8.2.6 & 8.2.7 Multicomputer Scheduling & Dynamic Load Balancing

In a multicomputer, scheduling must assign independent tasks across distinct physical nodes to minimize completion time without creating communication bottlenecks.

1. Graph-Theoretic Allocation

Tasks are modeled as nodes in a graph with edges weighted by inter-task communication volume. The scheduling objective minimizes total execution cost plus communication cost across nodes. If two tasks communicate heavily, placing them on the same node eliminates network delay entirely.

2. Dynamic Load Balancing Heuristics

When task arrival rates fluctuate dynamically, nodes exchange tasks to prevent imbalance:

Sender-Initiated Algorithms: An overloaded node actively seeks out underloaded nodes by sending probe queries to transfer tasks. Most effective when total system load is light to moderate, as finding an underloaded target is fast. Under high system load, sender probing generates heavy query storms because almost all nodes are busy.
Receiver-Initiated Algorithms: An idle or underloaded node actively probes other nodes seeking tasks to steal. Highly effective when the system operates at high utilization, because heavily loaded nodes are readily available to offload work.