Перейти к основному содержимому

Бестиарий операций: справочник по UOp

При отладке IR-дампов Morok вы встретите операции, назначение которых не очевидно из названия. Эта глава документирует нетривиальные операции с сигнатурами, описанием полей и примерами.

Что покрыто: Операции, требующие пояснений — управление циклами, редукции, работа с памятью, структура ядер, векторизация, тензорные ядра.

Что НЕ покрыто: Тривиальные ALU-операции (Add, Mul, Sqrt и т.д.), которые работают ровно так, как вы ожидаете.


Управление циклами: RANGE и END

RANGE — открытие скоупа цикла

Range {
end: Arc<UOp>, // loop bound (exclusive)
axis_id: AxisId, // identifier for deduplication
axis_type: AxisType, // scheduling behavior
deps: SmallVec<[Arc<UOp>; 2]>, // range dependencies
}

Поля:

ПолеТипНазначение
endArc<UOp>Верхняя граница (исключительно), обычно CONST
axis_idAxisIdUnrenumbered(n) до разделения ядер, Renumbered(n) после
axis_typeAxisTypeОпределяет способ планирования цикла (см. ниже)
depsSmallVec<[Arc<UOp>; 2]>Другие RANGE, от которых зависит этот

Иерархия AxisType:

ТипПриоритетGPU-маппингНазначение
Placeholder-3Временный канонический range, используемый при кэшировании RESHAPE
Loop-1цикл forRange по умолчанию после rangeify; обёртки уровня schedule структурно соединены парой END(Call)
Global0blockIdxПараллелизм по гриду
Thread0пул потоковCPU-параллелизм
Warp1warp/wavefrontСубгрупповой параллелизм
Local2threadIdxПараллелизм внутри воркгруппы
GroupReduce2shared memoryДвухэтапная редукция
Upcast3SIMDВекторизация
Reduce4аккумуляторОсь редукции
Unroll5развёрнутыйРазвёртка цикла

Приоритет определяет порядок вложенности — меньшие значения соответствуют внешним циклам. Границы ядер выражаются структурно через Call/Function, без выделенного типа оси.

Пример:

RANGE(end=128, axis_id=R0, type=Global)
└── CONST(128) : Index

END — закрытие скоупа цикла

End {
computation: Arc<UOp>, // value computed inside loop
ranges: SmallVec<[Arc<UOp>; 4]>, // ranges being closed
}

END закрывает один или несколько скоупов RANGE и убирает их из активного набора. Можно закрыть несколько RANGE одновременно.

Пример:

END
├── STORE(...) — computation
├── RANGE(R0, Global) — first range closed
└── RANGE(R1, Local) — second range closed

Редукция: REDUCE vs REDUCE_AXIS

Две операции с похожими названиями, но с разным назначением.

REDUCE_AXIS — редукция по измерению тензора (высокоуровневая)

ReduceAxis {
src: Arc<UOp>, // input tensor
reduce_op: ReduceOp, // Add, Mul, Max, Min
axes: Vec<usize>, // axes to reduce
}

Используется до rangeify. Работает по измерениям тензора, как .sum(axis=0) в NumPy.

Пример:

REDUCE_AXIS(Add, axes=[1])
└── BUFFER[10, 20] : Float32

Редуцирует тензор [10, 20] до [10], суммируя по оси 1.

REDUCE — редукция по итерациям RANGE (низкоуровневая)

Reduce {
src: Arc<UOp>, // value to accumulate
ranges: SmallVec<[Arc<UOp>; 4]>, // ranges being reduced
reduce_op: ReduceOp, // Add, Mul, Max, Min
}

Используется после rangeify. Аккумулирует значения по итерациям RANGE и закрывает указанные RANGE.

Варианты ReduceOp:

OpНейтральный элементОперацияTinygrad
Add0acc + value
Mul1acc * value
Max-∞max(acc, value)
Min+∞min(acc, value)Только Morok

Совместимость: Спецификация Tinygrad ограничивает REDUCE_AXIS до {Add, Mul, Max}. Morok расширяет это добавлением Min.

Пример:

REDUCE(Add)
├── MUL — value to accumulate
│ ├── LOAD(A, ...)
│ └── LOAD(B, ...)
└── RANGE(R2, Reduce) — range being reduced
└── CONST(64)

ALLREDUCE — редукция между устройствами

AllReduce {
src: Arc<UOp>, // local partial result
device: Arc<UOp>, // device specification
reduce_op: ReduceOp, // reduction operation
}

Выполняет распределённую редукцию между несколькими устройствами. Используется для мульти-GPU обучения.


Операции с буферами

BUFFER — объявление буфера

Buffer {
unique: Arc<UOp>, // UNIQUE op for identity
device: Arc<UOp>, // DEVICE op
size: usize, // total element count
}

Объявляет буфер для хранения данных тензора. Поле unique гарантирует различимость буферов даже при одинаковых размере и устройстве.

BUFFERIZE — маркер материализации

Bufferize {
compute: Arc<UOp>, // computation to materialize
ranges: SmallVec<[Arc<UOp>; 4]>, // output dimensions
opts: BufferizeOpts, // address space, device
}

Отмечает место, где вычисление должно материализоваться в память. Триггерит разделение на ядра.

BufferizeOpts:

ПолеТипНазначение
deviceOption<DeviceSpec>Целевое устройство, None для локального
addrspaceAddrSpaceGlobal (устройство) или Local (shared)
removableboolПри false buffer_removal не имеет права инлайнить эту BUFFERIZE — используется на границах realize с несколькими потребителями, чтобы буфер сохранялся между итерациями фикспоинта мега-прохода

Пример:

BUFFERIZE(opts={addrspace=Global})
├── REDUCE(Add, ...) — computation
├── RANGE(R0, Global) — output dim 0
└── RANGE(R1, Global) — output dim 1

INDEX — многомерный доступ к буферу

Index {
buffer: Arc<UOp>, // BUFFER or PARAM
indices: SmallVec<[Arc<UOp>; 4]>, // index per dimension
gate: Option<Arc<UOp>>, // optional predicate
}

Вычисляет адрес в памяти из многомерных индексов. Возвращает DType элемента (не указатель).

Пример:

INDEX : Float32
├── PARAM(0)
├── RANGE(R0, Global) — index for dim 0
├── RANGE(R1, Loop) — index for dim 1
└── MUL(...) — index for dim 2

POINTER_INDEX — низкоуровневая арифметика указателей

PointerIndex {
ptr: Arc<UOp>, // base pointer
offset: Arc<UOp>, // byte offset
}

Прямая арифметика указателей. Используется после линеаризации, когда индексы уже свёрнуты в линейные.

Совместимость: Tinygrad использует INDEX с флагом ptr=True вместо отдельной операции.

LOAD — чтение из памяти

Load {
buffer: Arc<UOp>, // buffer or pointer
index: Arc<UOp>, // INDEX op
alt: Option<Arc<UOp>>, // alternative value for gated loads
}

Читает значение из буфера по индексу. Для gated loads поле alt задаёт значение при ложном условии INDEX-а (позволяет полностью избежать обращения к памяти).

Пример:

LOAD : Float32
├── PARAM(1)
└── INDEX
├── PARAM(1)
├── RANGE(R0)
└── RANGE(R2)

STORE — запись в память

Store {
index: Arc<UOp>, // INDEX op (buffer accessed via index.src[0])
value: Arc<UOp>, // value to write
ranges: SmallVec<[Arc<UOp>; 4]>, // ranges being closed
}

Записывает значение в буфер. Буфер доступен через INDEX-узел (через index.src[0]), а не через отдельное поле. STORE закрывает указанные RANGE, которые представляют выходные измерения итерации. Поле ranges используется для output upcasting: когда включён Range(Upcast), он становится UNROLL при расширении, а затем сжимается через CONTRACT.

Для условной записи используйте INDEX с gate (у INDEX есть опциональное поле gate).

Совместимость: У STORE в Morok нет отдельного поля buffer — источники: index=0, value=1, ranges=2+ (range_start=2). Устройство Tinygrad аналогично.

Пример:

STORE
├── INDEX[R0, R1] — write address (buffer via index.src[0])
├── REDUCE(Add, ...) — value
├── RANGE(R0, Global) — output dim 0 (closed)
└── RANGE(R1, Global) — output dim 1 (closed)

Структура ядра и вызываемый IR

Работа уровня schedule выражается через вызываемый IR, повторяющий модель CALL/FUNCTION/PROGRAM из tinygrad: Function определяет тело (обычно Sink со store-операциями), параметризованное аргументами, Call вызывает его с конкретными аргументами, а Program проводит тело через строгий конвейер компиляции SINK → LINEAR → SOURCE → BINARY.

CALL — вызов тела функции

Call {
body: Arc<UOp>, // FUNCTION (или его тело)
args: SmallVec<[Arc<UOp>; 4]>, // конкретные значения аргументов
info: CallInfo, // метаданные (name, grad_tag, ...)
}

Вызывает тело callable с аргументами. Закрывает диапазоны: любые Range из args (range_start_index = 1; body=0, args=1+).

CallInfo несёт безопасные для ключей кэша аннотации:

ПолеТипНазначение
nameOption<String>Человекочитаемое имя callable
grad_tagOption<String>Зарезервировано для идентичности градиентного коллбека
metadataVec<String>Стабильные хешируемые аннотации
precompile / precompile_backwardboolПодсказки для предкомпиляции

FUNCTION — переиспользуемое тело

Function {
body: Arc<UOp>, // вычисление
args: SmallVec<[Arc<UOp>; 4]>, // формальные параметры
info: CallInfo,
}

Переиспользуемый callable. Его dtype всегда Void; тела, возвращающие несколько значений, оборачиваются в Tuple, чтобы граница функции оставалась Void. По форме закрытия диапазонов идентичен Call.

TUPLE / GET_TUPLE — мульти-возврат

Tuple { src: SmallVec<[Arc<UOp>; 4]> }
GetTuple { src: Arc<UOp>, index: usize }

Tuple упаковывает разнородные значения; его dtype всегда Void. GetTuple извлекает элемент index из Tuple (или из Function, чьё тело — Tuple); dtype соответствует внутреннему элементу. Используется, чтобы провести несколько выходов через Void-границу функции.

PROGRAM — контейнер компиляционного конвейера

Program {
sink: Arc<UOp>, // корневой SINK
device: Arc<UOp>, // DEVICE
linear: Option<Arc<UOp>>, // LINEAR (после линеаризации)
source: Option<Arc<UOp>>, // SOURCE (после рендера)
binary: Option<Arc<UOp>>, // PROGRAM_BINARY (после компиляции)
}

Проводит ядро через стадии SINK → LINEAR → SOURCE → PROGRAM_BINARY, которые жёстко выстроены в codegen/src/program_pipeline.rs (do_linearize/do_render/do_compile/get_program). Каждая стадия заполняет следующее поле. Рендерeры C/LLVM/MLIR ожидают вход Op::Linear и сообщают Error::InvalidGraph через pending_error контекста, не падая с panic; многоиндексные INDEX должны быть приведены к одноиндексным через pm_linearize_multi_index до рендера.

LINEAR — линеаризованный поток операций

Linear { ops: SmallVec<[Arc<UOp>; 8]> }

Плоская последовательность операций, полученная при линеаризации. Потребители итерируются по ops напрямую, без обхода графа.

SOURCE / PROGRAM_BINARY — артефакты компиляции

Source { code: String } // отрендеренный исходник (C / LLVM-IR / MLIR)
ProgramBinary { bytes: Vec<u8> } // скомпилированный артефакт

Терминальные стадии конвейера. Оба — листья (без потомков).

SINK — коллектор нескольких корней

Sink {
sources: SmallVec<[Arc<UOp>; 4]>,
info: Option<KernelInfo>, // структурный маркер для AST ядер
}

Собирает несколько выходов в один корень. Тело Function — как правило, Sink из store-операций. Поле info — хеш-консолидированный структурный маркер, отличающий SINK уровня kernel-AST от обычного SINK с теми же источниками без опоры на боковой канал type-erased метаданных.

Пример:

SINK
├── STORE(output_0, ...)
├── STORE(output_1, ...)
└── STORE(output_2, ...)

AFTER — маркер зависимости

After {
passthrough: Arc<UOp>, // value that flows through
deps: SmallVec<[Arc<UOp>; 4]>, // operations that must complete
}

Выражает зависимости выполнения между ядрами без data dependency. Значение passthrough возвращается без изменений, но только после завершения всех deps.

Пример:

SINK
├── AFTER
│ ├── PARAM(0) — passthrough (buffer reference)
│ └── KERNEL(...) — must complete first
└── KERNEL(...) — can use buffer after AFTER

BARRIER — барьер синхронизации

Barrier {
src: Arc<UOp>, // value passing through
deps: SmallVec<[Arc<UOp>; 4]>, // operations to wait for
}

Синхронизация GPU-воркгруппы. Гарантирует, что все потоки в воркгруппе достигли барьера, прежде чем продолжить.


Векторные операции

VECTORIZE — создание вектора из скаляров

Vectorize {
elements: SmallVec<[Arc<UOp>; 4]>,
}

Комбинирует N скалярных значений в вектор размера N. Все элементы должны иметь одинаковый базовый DType.

Пример:

VECTORIZE : <4 x Float32>
├── CONST(1.0)
├── CONST(2.0)
├── CONST(3.0)
└── CONST(4.0)

GEP — Get Element Pointer (извлечение из вектора)

Gep {
vector: Arc<UOp>, // source vector
indices: Vec<usize>, // positions to extract
}

Извлекает элементы из вектора:

  • Один индекс — скаляр
  • Несколько индексов — вектор меньшего размера

Пример:

GEP([0, 2]) : <2 x Float32>
└── VECTORIZE : <4 x Float32>
└── ...

VConst — векторная константа

VConst {
values: Vec<ConstValue>,
}

Вектор констант, известных на этапе компиляции. Эффективнее, чем VECTORIZE из CONST-узлов.

CAT — конкатенация векторов

Cat {
sources: SmallVec<[Arc<UOp>; 4]>,
}

Конкатенирует векторы в вектор большего размера. vcount на выходе = сумма vcount входов.

Пример:

CAT : <8 x Float32>
├── VECTORIZE : <4 x Float32>
└── VECTORIZE : <4 x Float32>

PtrCat — конкатенация указателей

PtrCat {
sources: SmallVec<[Arc<UOp>; 4]>,
}

Группирует обращения к памяти для векторизованного load/store. Используется проходом devectorizer.


Расширение: UNROLL и CONTRACT

UNROLL — расширение вычисления по итерациям

Unroll {
src: Arc<UOp>, // computation to expand
unroll_axes: Vec<(usize, usize)>, // (axis_index, factor) pairs
}

Создаёт несколько версий вычисления для разных значений итерации. Используется для оптимизации развёртки циклов.

Пример: UNROLL(unroll_axes=[(0, 4)]) расширяет вычисление 4 раза с разными значениями индекса.

CONTRACT — свёртка развёрнутых значений в вектор

Contract {
src: Arc<UOp>, // unrolled computation
upcast_ranges: Vec<(usize, usize)>, // (axis_index, factor) pairs
}

Обратная операция к UNROLL — собирает расширенные скалярные значения в вектор. Размер выходного вектора = произведение множителей.

Пример:

CONTRACT(upcast_ranges=[(0, 4)]) : <4 x Float32>
└── UNROLL(unroll_axes=[(0, 4)])
└── LOAD(...)

Этот паттерн векторизует загрузку: расширить 4 итерации, затем упаковать результаты в 4-элементный вектор.


Тензорные ядра: WMMA

WMMA — Warp Matrix Multiply-Accumulate

Wmma {
a: Arc<UOp>, // matrix A fragment
b: Arc<UOp>, // matrix B fragment
c: Arc<UOp>, // accumulator C fragment
metadata: WmmaMetadata, // hardware configuration
}

Аппаратная операция тензорного ядра: D = A * B + C. Требует конкретных форм матриц и раскладок данных.

Поля WmmaMetadata:

ПолеТипНазначение
nameStringИмя инструкции (например, "__hmma...")
dims(N, M, K)Размерности матриц (например, (16, 16, 16))
dtype_inDTypeТочность входных матриц (например, Float16)
dtype_outDTypeТочность выхода (например, Float32)
deviceRendererDeviceРендерер / TC-бэкенд, породивший эту WMMA
threadsusizeПотоков на warp (обычно 32)
upcast_axesWmmaUpcastAxesВекторизация для каждого операнда (поля: a, b, c)
reduce_axesVec<(usize, usize)>Оси свёртки
tile_grid(usize, usize)Грид для мульти-FMA батчинга (по умолчанию (1,1))

Пример:

WMMA(dims=(16, 16, 16), dtype_in=Float16, dtype_out=Float32)
├── A fragment : <8 x Float16>
├── B fragment : <8 x Float16>
└── C accumulator : <8 x Float32>

Управление потоком выполнения

IF / ENDIF — условное выполнение

If {
condition: Arc<UOp>, // boolean predicate
body: SmallVec<[Arc<UOp>; 4]>, // operations to execute
}

EndIf {
if_op: Arc<UOp>, // corresponding IF op
}

Выполнить тело, только если условие истинно. Используется для проверок границ и разреженных операций.

Пример:

IF
├── LT(idx, bound) — condition (src[0])
├── STORE(...) — body[0]
└── STORE(...) — body[1]

ENDIF
└── IF(...) — references IF op

Операции определения

PARAM — параметр буфера

Param { slot: usize, size: usize, device: Option<Arc<UOp>> }

Нормализованный параметр буфера — позиционная ссылка на входной/выходной буфер. Создаётся при предварительной нормализации расписания (BUFFER->PARAM) для стирания идентичности буфера, что позволяет структурную дедупликацию идентичных вычислений на разных буферах. slot — позиция в списке аргументов ядра, size — количество элементов.

DEFINE_LOCAL — аллокация shared-памяти

DefineLocal(usize) // local memory index

Аллокация GPU shared memory (LDS). Видна внутри воркгруппы.

DEFINE_VAR — символическая рантайм-переменная

DefineVar {
name: String, // variable name
min_val: i64, // minimum bound
max_val: i64, // maximum bound
}

Рантайм-переменная с известными границами. Используется для динамических форм, когда границы известны.

Пример:

DEFINE_VAR(name="batch_size", min=1, max=128) : Index

DEFINE_REG — аллокация регистра

DefineReg {
size: usize, // register size
id: usize, // unique accumulator ID
}

Аллоцирует регистр для промежуточного хранения. Поле id различает регистры одного DType — без него два reduce с одинаковым DType разделили бы один DEFINE_REG через hash consing. Используется в кодогенерации.

BIND — привязка переменной

Bind {
var: Arc<UOp>, // DEFINE_VAR
value: Arc<UOp>, // concrete value
}

Привязывает символическую переменную к конкретному значению в рантайме.


Специальные операции

SPECIAL — аппаратные значения

Special {
end: Arc<UOp>, // upper bound for this dimension
name: String, // e.g., "blockIdx.x", "threadIdx.y"
}

Доступ к значениям, предоставляемым аппаратурой (индексы потоков/блоков). Это не цикл — значение даётся напрямую оборудованием.

Пример:

SPECIAL(name="blockIdx.x", end=128) : Index
└── CONST(128)

UNIQUE / LUNIQUE — маркеры идентичности

Unique(usize) // глобальный счётчик идентичности
LUnique(usize) // счётчик идентичности локальной области

Создаёт уникальную идентичность для различения буферов. Два буфера с разными Unique-значениями различимы, даже если в остальном идентичны. LUnique обеспечивает такое же различение в пределах локальной области (например, внутри тела Function), не пересекаясь с глобальным счётчиком, — благодаря этому тела callable можно хеш-консолидировать независимо от точек вызова.

DEVICE — спецификация устройства

Device(DeviceSpec) // device specification

Указывает целевое устройство для вычисления.


Операции перемещения (Movement)

Высокоуровневые трансформации формы тензора. Преобразуются в явные INDEX-операции во время rangeify.

ОперацияСигнатураНазначение
Reshape{ src, new_shape }Изменить форму, те же элементы
Permute{ src, axes: Vec<usize> }Транспонирование / перестановка осей
Expand{ src, new_shape }Бродкаст до большей формы
Pad{ src, begin_pads, end_pads }Добавить паддинг
Shrink{ src, begins, ends }Извлечь подобласть
Flip{ src, axes: Vec<bool> }Развернуть по осям

Пример: RESHAPE

RESHAPE(new_shape=[6, 4]) : Shape[6, 4]
├── BUFFER[2, 3, 4] : Float32
└── CONST([6, 4]) : Shape

Дополнительные операции

Следующие операции существуют в enum Op, но являются внутренними или редко встречаются при отладке:

ОперацияНазначение
CopyЯвное копирование значения
BufferView{ buffer, size, offset } — срез существующего буфера со смещением
MStackАллокация стека в памяти
MSelectВыбор в памяти (условный доступ)
MultiОперация с множественными выходами
GroupГруппировка операций для планирования
DetachОтсоединение от графа (запрет оптимизации через узел)
ContiguousХинт, что данные непрерывны
ContiguousBackwardОбратный проход для хинта contiguous
PrecastПредварительное приведение типа
Custom / CustomIИнлайновое расширение пользовательскими операциями (Custom поддерживает только C)
CustomFunctionХук пользовательской функции уровня runtime (виды: EncDec, Graph)

Краткий справочник

По категориям

КатегорияОперации
Управление цикламиRANGE, END
РедукцияREDUCE_AXIS, REDUCE, ALLREDUCE
ПамятьBUFFER, BUFFER_VIEW, BUFFERIZE, INDEX, POINTER_INDEX, LOAD, STORE
Ядро и callableSINK, CALL, FUNCTION, TUPLE, GET_TUPLE, PROGRAM, LINEAR, SOURCE, PROGRAM_BINARY, AFTER, BARRIER
ВекторныеVECTORIZE, GEP, VCONST, CAT, PTRCAT
РасширениеUNROLL, CONTRACT
АппаратныеWMMA, SPECIAL
УправлениеIF, ENDIF
ОпределениеPARAM, DEFINE_LOCAL, DEFINE_VAR, DEFINE_REG, BIND, UNIQUE, LUNIQUE, DEVICE
ПеремещениеRESHAPE, PERMUTE, EXPAND, PAD, SHRINK, FLIP
ALUUnary(...), Binary(...), Ternary(...), Cast, BitCast

Операции, закрывающие RANGE

Операции, которые закрывают скоупы RANGE (убирают RANGE из активного набора):

ОперацияНачальный индекс RANGE
BUFFERIZE1 (compute=0, ranges=1+)
REDUCE1 (src=0, ranges=1+)
STORE2 (index=0, value=1, ranges=2+)
WMMA3 (a=0, b=1, c=2)
END1 (computation=0, ranges=1+)
CALL / FUNCTION1 (body=0, args=1+)

Расширяемые операции

Операции, через которые UNROLL пропагируется по графу вычислений:

  • ALU: Unary, Binary, Ternary
  • Типы: Cast, BitCast
  • Векторные: Gep, Vectorize
  • Память: Load, Store, Index, PointerIndex
  • Управление: Reduce, End, After
  • Буферы: Bufferize
  • Аппаратные: Wmma