<!-- examples/mpk/README.md -->

# MPK tGraph teaching model

Run `python3 examples/mpk/tgraph.py` from the repository root. Add `--json` for
deterministic output. Python 3.10 or later is sufficient; there are no
third-party dependencies.

The canonical regions `dependencies`, `fusion`, `linearize`, and `schedule` are
synchronized into the paper page by `scripts/sync-paper-examples.mjs`. Edit this
source before regenerating excerpts or downloads.

This is an independently authored teaching model of the compiler stages in
"MPK: A Compiler and Runtime for Mega-Kernelizing Tensor Programs" (OSDI 2026).
It is not MPK's code. It runs no GPU work, generates no CUDA, and does not
model task implementations or inter-GPU communication, and it models
shared-memory pages only as a page count in the authored pipelining timeline.
Every count and duration comes from toy graphs chosen for this page, not from
the paper's models. Durations are illustrative units, not measured times.

## What it models

- **Decomposition.** Each operator's output axis is split into equal tasks.
- **Dependency analysis (Section 4.1).** An event is created for a task pair
  when the producer's output region overlaps the consumer's input region. Tasks
  with no producer wait on a start event.
- **Event fusion (Definitions 4.1 and 4.2).** Successor-set fusion runs first,
  then predecessor-set fusion, as in Figure 5(c) and 5(d). The set of producer
  and consumer task pairs is unchanged by both.
- **Normalization (Figure 6).** Every task ends with one dependent event and at
  most one triggering event.
- **Linearization (Algorithm 1).** A breadth-first order places the tasks
  launched by one event next to each other, so an event stores a first and a
  last task index.
- **Dispatch (Section 5.1).** Schedulers enqueue the tasks of an activated
  event; workers run their FIFO queues. A task finishing decrements its
  triggering event.
- **Cross-task pipelining (Section 5.3).** `pipeline_timeline` is an authored
  one-SM timeline. A task preloads once the previous task has issued all of its
  loads and enough pages are free.

## Choices this model makes where the paper is silent or inconsistent

- Fusion runs successor-set first, then predecessor-set, once each. The model
  checks that a second round changes nothing for the Figure 5 example and that
  the reverse order produces different events.
- Section 4.1 describes a fresh event and k empty tasks for every fork or join.
  Figure 5(e) draws one fewer empty task: it reuses the event whose only trigger
  is the forking task. The model reuses such an event when it exists and
  applies the general rewrite otherwise. For Figure 5 it adds two empty tasks.
- Tasks are numbered in creation order, by operator. Algorithm 1 then places the
  first eight tasks in operator order (`Q1 Q2 Q3 Q4 K1 K2 V1 V2`); Figure 5(f)
  draws a different order inside that range. Every event's first and last task
  index matches Figure 5(f).
- Figure 5(f)'s Counts row prints 2 for e4 and 1 for e5. By the figure's own
  task rows e4 is triggered only by `A2` and e5 by `D1` and `D2`, which gives 1 and 2. The model reports 1 and 2.
- Which worker receives a launched task is not specified in the sections used.
  This model gives it to the worker with the fewest queued or running tasks
  (lowest index on ties).
- Scheduling latency is zero, and empty tasks take zero time.
- Empty tasks are named `D1`, `D2`, and so on, skipping names already in use.
- Toy encoding: 4-byte indices. An explicit list stores one index per successor
  plus one length word per event; a range stores two indices. The paper reports
  110,932 and 18,928 bytes for one model; the second equals 8 bytes times 2,366
  events, which is consistent with two 4-byte indices per event, but the paper
  does not state the index width.

The self-check asserts the Figure 5 pipeline (18 pair events, 8 after
successor-set fusion, 5 after predecessor-set fusion, plus the start event), the
linearized order and each event's first and last index, preservation of the
producer-consumer pair set through fusion, normalization invariants for forks
and joins, that every simulated task starts after its producers finish, and
that invalid shapes are rejected.

## Sources

- [Paper (USENIX OSDI '26 open access)](https://www.usenix.org/conference/osdi26/presentation/cheng):
  Sections 3 to 5, Figures 4 to 8, Definitions 4.1 and 4.2, Algorithm 1.
- [Official repository](https://github.com/mirage-project/mirage/tree/d90383d009aba60b9c2a274685e3c0ef0d83e7b8),
  the default-branch head on 2026-11-10. It is not a paper-tagged release, and
  it has not been compared line by line with this model.
