Module memory 

Memory planning — buffer allocation via live-interval graph colouring.

The memory planner assigns device memory “slots” to logical buffers so that two buffers whose live intervals do not overlap can share the same physical memory region (offset within a pool allocation).

Algorithm

This is an instance of the interval graph colouring problem, which on an interval graph is solvable optimally in O(n log n) time using a greedy “earliest deadline first” scan:

1. Sort buffers by live-interval start position.
2. Maintain a priority queue of “free slots” keyed by their end position.
3. For each buffer (in order): reuse a free slot whose end position is ≤ the buffer’s start position (best-fit by size); or allocate a new slot if no free slot is large enough.

The result is a MemoryPlan that tells each buffer which slot and byte offset to use within the device memory pool.

Structs

MemoryPlan

The complete memory allocation plan for a graph.

SlotAssignment

The memory slot assigned to a single buffer.

Functions

analyse

Runs the memory planning pass on graph.