3.6Naive SC Implementations

Two implementations you could build this afternoon

SC permits two naive implementations whose value is clarity, not speed — they make it easy to see exactly which executions SC permits.

The multitasking uniprocessor

Implement SC for multithreaded user-level software by executing all threads on a single sequential core, time-multiplexed: thread T1 runs on the core until a context switch to T2, and so on. On a context switch, any pending memory operations must complete before the next thread starts. Because each thread’s instructions within a quantum execute as one atomic block — and because the uniprocessor honors memory dependencies — every SC rule is enforced. The execution literally is an interleaving of sequential thread executions.

The switch

Second: a set of cores, a single switch, and memory. Each core presents its memory operations to the switch one at a time, in its program order (internally, a core may use any optimization that doesn’t change the order of presentation — a simple five-stage in-order pipeline with branch prediction is fine). The switch picks one core, lets memory fully satisfy that access, and repeats. Try being the switch:

The switch may pick cores by any method that does not starve a core with a ready request — random is fine. The result implements SC by construction: the grant sequence is the memory order memory order The total order (<m) on all cores' memory operations that an execution appears to perform. defined in Chapter 3 — open in glossary , and it respects every core’s program order program order The per-core total order (<p) of a core's memory operations as specified by its program. defined in Chapter 3 — open in glossary because that’s the only order cores offer operations in.

Assessment

The good news: these designs are operational models — machines whose step-by-step behavior defines (1) the allowed SC executions and (2) “gold standards” for SC implementations. (Chapter 11 shows how operational models formally specify consistency models.) The switch is also an existence proof that SC can be implemented without caches or coherence — no cache appears anywhere in it.

The bad news: performance does not scale with core count. The multitasking uniprocessor uses one core, and the switch/memory pair is a sequential bottleneck serving one access at a time. These bottlenecks led some people to conclude — incorrectly — that SC precludes true parallel execution. It does not, as the next section shows: with coherence as a black box, non-conflicting accesses can proceed completely in parallel under SC.