Тераграф

Ядро из двух частей

Тераграф считает графы на ядрах GPC, и каждое ядро состоит из двух половин. Процессор CPE на RISC-V исполняет программу, а рядом с ним работает блок дерева SPE: он хранит пары «ключ и значение» и сам выполняет над ними команды.

Внутри блока дерева

Пары в блоке SPE лежат в дереве T4. Заглянем внутрь: дальше речь пойдёт о словаре, о дереве, о командах и о том, как из всего этого получается граф.

Упорядоченный словарь

По сути блок хранит упорядоченный словарь, похожий на std::map из C++. Пары в нём всегда выстроены по возрастанию ключа, и новая пара сразу занимает своё место в ряду.

Порядок даёт соседей

Из порядка сразу следует соседство: рядом с ключом 25 стоят 20 и 31. Ключа 30 в словаре нет, но ближайший больший, 31, находится без всякого перебора.

Начало ключа даёт группу

Ключ может состоять из двух чисел, например «откуда» и «куда». Тогда все пары, которые начинаются с 03, выстраиваются подряд, и вместе они описывают дороги, ведущие из точки 3.

Словарь в дереве

Внутри словарь устроен как дерево T4. Дерево читает ключ байт за байтом: первый байт выбирает ветку первого уровня, второй ведёт глубже, на второй уровень.

Группа стала веткой

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

Пустые уровни сжаты

Номера точек невелики, поэтому ключ начинается с длинной цепочки нулей. Дерево не тратит на них уровни: всё общее начало умещается в одной записи.

Короткие ветки не делятся

Если в ветке набирается не больше семи записей, дерево не дробит её дальше: записи просто лежат одним списком.

Найти и изменить

Блок дерева понимает 21 команду. SRCH спускается по дереву к нужному ключу, INS вставляет пару, DEL удаляет её и оставляет пустое место, а CNT считает ключи.

В математике: принадлежность элемента множеству, добавление, исключение, мощность множества.

Соседи по порядку

NEXT и PREV возвращают соседний ключ. NSM и NGR находят ближайший меньший и больший, даже когда самого ключа в дереве нет. MIN и MAX отвечают, где у дерева края.

В математике: функция отношения элементов множества.

Деревья целиком

AND, OR и NOT работают сразу с целыми деревьями: пересекают, объединяют и вычитают A и B, а ответ складывают в новое дерево R.

В математике: пересечение, объединение и разность множеств.

Срезы

LS, LSEQ, GR, GREQ и GRLS отсекают часть дерева по заданной границе и собирают из неё дерево R.

В математике: включение подмножества в кортеж и отношение эквивалентности множеств.

Служебные

SQ убирает пустые места, которые оставил DEL, DELS стирает дерево целиком, а JT отдаёт программе ядра код ветвления.

В математике: DELS исключает подмножество из кортежа.

Дороги в дереве

Пусть ключ задаёт пару городов с номерами от 1 до 5, а значение хранит длину дороги между ними. Пары, как и положено в дереве T4, стоят по порядку ключей.

Города стали точками

Одинаковые номера сходятся в одну точку. Такие точки графа называют вершинами.

Пары стали дорогами

Пары складываются в карту дорог. Такая карта и есть граф, а дороги в нём называют рёбрами. Каждая ветка дерева хранит все рёбра одной вершины.

Путь по дереву

Кратчайший путь из 1 в 5 равен 9. Ядро находит его одними командами дерева: MIN достаёт ближайшую точку, а NGR и NEXT перебирают дороги, которые из неё выходят.

Деньги по кругу

Мошенники дробят деньги и гоняют их по кругу через цепочки переводов. Переводы каждого счёта лежат в порядке времени, поэтому ядро просто идёт по цепочке вперёд.

ключ (счёт, время, номер) → кому, сумма

Перевод под проверкой

За каждым переводом тянутся место клиента, IP-адрес, карта и счёт. Все эти свойства лежат отдельными парами в одной ветке, и банк успевает прочитать её, прежде чем пропустить деньги.

ключ (перевод, свойство) → значение

Подставные фирмы

Налоговая выслеживает цепочки подставных фирм, через которые деньги уходят по кругу и возвращаются к первой из них.

ключ (фирма, партнёр) → сумма платежей

Энергосеть и заводы

Авария одного узла тянет за собой соседей. Граф помнит поставки, сроки службы и цену замены и подсказывает, что чинить в первую очередь.

ключ (узел, зависимый узел) → срок службы, цена

Медицина

Граф организма пациента сравнивают с графами похожих случаев. Так AstraZeneca подбирала терапию по аналогии.

ключ (случай, показатель, связанный показатель) → сила связи

Обмен веществ

Учёным известно больше 10 тысяч реакций в организме человека. По графу этих реакций ищут новые лекарства.

ключ (вещество, реакция) → коэффициент

Граф внутри вершины

Значение может хранить номер другого дерева, и тогда внутри вершины прячется целый граф: так устроен метаграф. А гиперграф соединяет одним ребром сразу несколько вершин.

ключ (вершина, поле) → номер дерева

Снова целое ядро

Блок дерева работает не сам по себе, а рядом с процессором и памятью карты. Скорость ему дают кэш, чтение наперёд и очередь команд.

Верх дерева в кэше

Два верхних уровня дерева живут в кэше ядра на 256 КБ, и слово оттуда приходит за 3 такта. В кэш попадает только верх, поэтому глубокие строки никогда не вытесняют корень.

Ядро не ждёт память

Обычный процессор на каждом шаге по дереву ждёт память. Ядро T4 читает из DDR сразу две строки по 64 байта, а очередь на 16 команд позволяет программе поставить команду и, не дожидаясь ответа, идти дальше.

64 ядра на карте

На карте U250 помещаются 64 ядра с частотой 200 МГц, и каждое держит до 4096 деревьев. Память ядра берут страницами из общего пула, а хост задаёт каждому свою квоту.

Карта в сервере

Карты стоят в узле комплекса Тераграф. У узла два процессора по 26 ядер, 1 ТБ памяти и хранилище графов на 30 ТБ.

Сервер в стойке

Комплекс Тераграф собран из трёх таких узлов, консоли и двух источников питания, а узлы связывает сеть на 100 Гбит/с. Ядро с T4 понимает ту же библиотеку lnh64, что и ядро Леонарда.

Демо

Девять программ для ядра, от кратчайшего пути до музыкальных гармоний.

Что ускоряет T4

Возьмём задачу из главы про деньги по кругу: обход переводов FinBench на 4 шага сразу от 1000 крупных счетов по 4,7 млн рёбер. Обычный компьютер решает её графовой базой Memgraph на сервере.

в 32 разабыстрее одного запроса Memgraph

  • в 6,3 разабыстрее 96 клиентов Memgraph
  • в 15 разбыстрее на одном тяжёлом запросе: 100 крупных счетов по одному

Откуда числа

Числа ядер дала такт-точная симуляция RTL 80 ядер T4: каждое ядро исполняло свою программу на своём дереве, память DDR отвечала через 150 нс. Memgraph и слияние ответов замерены на сервере Kraftway.

Где компьютер не отстаёт

Простой цикл C++ по массивам на одном потоке Apple M5 проходит ту же пачку за 115 мс, вровень с картой. Сами ядра тратят от 22 до 28 мс, а 81 % времени карты уходит на слияние ответов на хосте. Следующий шаг: слияние на самой карте.

Настоящая карта сейчас

Настоящая карта на 60 ядрах прошла пачку за 1,87 с. Хост читает её ответы через BAR по 32 бита, зеркало ответов в памяти хоста снимет этот предел.

TeraCloud

Каждый получает свой JupyterLab в браузере и ядра GPC рядом с ним.

1Войдите через SSO МГТУ или по паролю.
2Выберите число ядер GPC ползунком.
3Откройте JupyterLab и загрузите sw_kernel на ядро из Python.
4Следите за ядрами и отлаживайте программу командой gpc в терминале.
Страница рабочего пространства TeraCloud: вход по SSH, ключи S3, профиль ресурсов, квота проекта и кнопка «Открыть JupyterLab»
Рабочее пространство: вход по SSH, ключи S3, профиль ресурсов и квота проекта. JupyterLab открывается кнопкой в шапке.
Список рабочих пространств TeraCloud с квотами проекта по CPU, памяти, GPC и GPU
Список пространств: квоты проекта по процессорам, памяти и ускорителям и запущенная сессия.