12. Parallel Storage Allocation

What this lecture covers

This lecture continues directly from the previous one on serial storage allocation, extending the picture to parallel programs. It first reviews malloc, mmap, address translation and the TLB, then asks what happens to the stack discipline when multiple function-call branches run at once, and finally works through several strategies for parallel heap allocation, ending with a detailed look at the Hoard allocator.

By the end you should be able to explain why a parallel program needs a cactus stack rather than a single linear stack, describe the tradeoffs between a global heap, per-thread local heaps, and the local-ownership and Hoard designs, and reason about blow-up, fragmentation and false sharing as consequences of these design choices. This material is examined further in project 3 and homework 6, where students implement and evaluate their own allocators.

Key ideas

• mmap vs. malloc: mmap is a lazy, page-granularity system call that reserves virtual address space without allocating physical memory until it's first touched; malloc is a fast library call that reuses memory it already obtained from mmap, falling back to the OS only when needed.
• Cactus stack: in a parallel program, sibling function calls that run concurrently need to see independent, non-overwriting views of the call stack, unlike the single linear stack of serial execution.
• Heap-based cactus stack: allocating each call's stack frame from the heap, linked to its parent frame, supports a strong space bound (SP <= P * S1, using the busy-leaves property of Cilk's work-stealing scheduler) but breaks interoperability with legacy serial binaries.
• Blow-up: for a parallel allocator, the ratio of the space it uses to what a serial allocator would use for the same program; a central metric for comparing allocator designs.
• Global heap: a single heap protected by a lock has blow-up 1 but suffers badly from lock contention, which is worse for many small allocations than for a few large ones.
• Local heaps: giving each thread its own heap removes locking but can cause unbounded blow-up through memory drift, where one thread frees objects allocated by another and the freeing thread's heap never sees that freed space.
• Local ownership: each object remembers which heap allocated it and is returned there on free, bounding blow-up by P while keeping local allocation and freeing fast, since only cross-thread frees need synchronization.
• False sharing: when independent variables from different threads land on the same cache line, causing it to bounce between caches even though there's no true data conflict; local-ownership allocators are naturally more resilient to it.
• Hoard allocator: combines per-thread local heaps with a shared global heap, moving whole superblocks between them under an invariant that bounds blow-up to 1 + O(SP/U), where S is the superblock size, P the number of threads and U the user footprint.

Walkthrough

Reviewing malloc, mmap and address translation (0:01)

The lecture reviews malloc and memalign (for cache- and vector-aligned allocations), then explains mmap as a lazy, page-granularity system call: it reserves address space and updates the page table with entries pointing to a read-only zero page, only allocating real physical memory on the first write, which is why a terabyte can be mapped on a machine with a gigabyte of DRAM. It contrasts this with malloc, a library call that reuses memory obtained via mmap and only calls into the OS when it runs out, and reviews page tables and the TLB as the hardware mechanism behind address translation.

Serial stacks and why parallelism breaks them (15:23)

Working through an example invocation tree, the lecture shows how a traditional linear stack reuses the same memory for sibling calls once each returns, and why a parent can safely pass pointers to its own stack variables down to children, but not the reverse, since a later sibling call can overwrite that memory.

The cactus stack for parallel programs (20:26)

When functions like B and C, or D and E, can run in parallel, each needs to see its own consistent view of the ancestor stack frames without copying. The lecture presents a heap-based cactus stack, where each call frame is heap-allocated with a pointer to its parent, and proves a space bound of SP <= P * S1 using the "busy leaves" property of Cilk's work-stealing scheduler, where every current leaf of the active call tree has a worker on it. This bound is applied to the divide-and-conquer matrix multiplication example, first giving O(P * N^2) and then, by analyzing where the recursion tree branches most, a tighter O(P^(1/3) * N^2) bound.

Interoperability and a linear-stack pool (38:40)

Because heap-based cactus stacks are incompatible with legacy code written to assume a traditional linear stack, the lecture explains that the actual Cilk implementation instead maintains a pool of linear stacks that workers borrow and return, preserving the space bound (given enough stacks) while sacrificing some of the work-stealing algorithm's time guarantees, as an idle worker may find no stack available to steal.

Metrics for heap allocators (41:40)

The lecture defines allocator speed, user footprint (peak bytes in use), allocator footprint (peak bytes obtained from the OS), and fragmentation as their ratio, explaining that small allocations matter more for speed because their overhead isn't amortized the way it is for large blocks whose bytes the program will write anyway. It also revisits the earlier proof that bin free list fragmentation is O(log U), and distinguishes internal fragmentation (block larger than requested), external fragmentation (unusable non-contiguous free space) and space overhead (bookkeeping).

Global heap vs. local heaps (49:54)

A single global heap protected by a lock is simple and has blow-up 1, but lock contention degrades performance sharply as thread count grows, especially for small, frequent allocations. Giving each thread its own local heap removes contention entirely but introduces memory drift: if one thread only allocates and another only frees, the freeing thread's heap accumulates unusable free space while the allocating thread keeps requesting more from the OS, producing unbounded blow-up.

Local ownership and the Hoard allocator (1:00:15)

Local ownership fixes memory drift by returning every freed object to its original owning heap, bounding blow-up by P while keeping local operations fast and reducing false sharing, since objects don't stay permanently split across heaps. The Hoard allocator builds on this by organizing memory into fixed-size superblocks that move between per-thread local heaps and a shared global heap, using an invariant that keeps each local heap's utilization above half, which the lecture uses to prove a blow-up bound of 1 + O(SP/U). The lecture closes with a comparison of speeds across the global-heap default allocator, Hoard, jemalloc and SuperMalloc on a benchmark, showing SuperMalloc as both the fastest and the simplest in lines of code.

Before you watch

• Review the previous lecture on storage allocation (stacks, free lists, bin free lists) since this lecture builds directly on those definitions and reuses its fragmentation proof.
• Recall the multithreaded algorithms lecture's work, span and master-theorem analysis, used here to derive the space bound for the matrix multiplication example.
• Familiarity with the Cilk work-stealing scheduler and its busy-leaves property is assumed when deriving the cactus stack's space bound.

Check your understanding

1. Why can't a parallel program use a single traditional linear stack the way a serial program does?
2. Walk through why the heap-based cactus stack gives a space bound of P times the serial stack space.
3. What causes memory drift in a local-heaps allocator, and how does local ownership prevent it?
4. Why does lock contention hurt small allocations more than large ones in a global-heap allocator?
5. In the Hoard allocator, what invariant bounds the amount of unused space in each local heap, and how does that lead to the overall blow-up bound?