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

# Welder tile-graph teaching model

Run `python3 examples/welder/tile_graph.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 `propagate`, `traffic`, `connect`, 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. It is not Welder's code, it
does not run on a GPU, and it predicts no latency.

What it models:

- Back-to-front tile propagation through a chain of operators: a matrix
  multiplication followed by a row softmax, and a 3 by 3 convolution, a ReLU and
  a 2 by 2 max pool. Window extents follow `(out - 1) * stride + kernel` and
  ignore padding.
- The traffic calculation of the paper's Section 2: global bytes for one
  tile-graph are its input tiles plus its output tile, multiplied by the number
  of tile-graphs that cover the output. Reuse tiles stay on chip and are not
  counted. The B tile is reloaded for every output tile, and "MB" in the
  paper's 840 MB and 264 MB means 2^20 bytes.
- A footprint that sums every tile of the tile-graph. The paper allocates with
  a best-fit allocator over tile liveness, so this sum is an upper bound.
- Grouping of operators at each memory layer from the reuse layer of each edge.
- A miniature of the SubGraphTiling step in the paper's Figure 7: propagate each
  candidate output tile, drop those whose footprint exceeds a capacity, rank the
  rest by traffic, and keep the top K. Candidates are power-of-two row counts,
  a stand-in for the Roller-style tile expansion that the paper uses.

What it does not model: the penalties of Section 4.1 (uncoalesced access,
insufficient parallelism), TensorCore shape constraints, partitioning of
reduction axes, profiling-based selection of a reuse layer, code generation, or
any measured behavior. The memory capacity passed to the search is an argument,
not a hardware specification.

The self-check reproduces the paper's worked numbers exactly: 35,840 bytes per
tile and 24,576 tiles for a `[4 x 128]` output tile (840 MiB in total), and
45,056 bytes per tile and 6,144 tiles for `[16 x 128]` (264 MiB in total). It
also checks monotonic traffic and footprint, rejection of tiles that split a
softmax row or do not divide the tensor, and the Figure 5 tile shapes.

Source: Yining Shi et al., "Welder: Scheduling Deep Learning Memory Access via
Tile-graph", OSDI 2023,
<https://www.usenix.org/conference/osdi23/presentation/shi>, Sections 2, 3.1
and 3.2. Official code is in the
[NNFusion repository](https://github.com/microsoft/nnfusion/tree/7d1e71ea2b5acedd7e87be572523a8cbf1fc4e82)
(`osdi2023welder` artifact branch, revision
`7d1e71ea2b5acedd7e87be572523a8cbf1fc4e82`). No paper measurement is
reproduced by this CPU model.
