Краткая древовидная структура сокращает объем памяти графического процессора и унифицирует двусторонние операции с разреженными матрицами
Дерево $k^2$ представляет собой компактное представление логических матриц: оно хранит рекурсивную иерархию их непустых подматриц без значений и координат и одинаково обслуживает строки и столбцы. Однако его обход находит дочерние элементы каждого узла с помощью ранговых запросов — цепочки зависимых нерегулярных нагрузок, которая заставляет графический процессор ждать памяти. Мы реализуем разреженное матрично-векторное умножение (SpMV) на $k^2$-деревьях для графического процессора. Поскольку обход не зависит от вектора, позиции дочерних элементов статичны: мы спускаемся по дереву по одному уровню и получаем их из параллельной суммы префиксов или из выборочного каталога размером около 0,1 бита на узел. По убыванию в плитках временная память ограничивается глубиной дерева, поэтому память устройства продукта известна до его запуска. Тот же обход вычисляет правые и левые произведения для одного вектора или пакета по плюсовым, булевым и тропическим полукольцам. Мы оцениваем движок на NVIDIA GB10 и H100 с четырнадцатью графами Wikidata, Software Heritage, веб- и социальными графами с числом до 1,2 миллиарда ребер в сравнении с cuSPARSE, движком графического процессора со сжатием грамматики и логическим CSR. Наши результаты показывают, что дерево на 2,3-27x меньше, чем CSR cuSPARSE, и что при кэшировании последнего внутреннего уровня продукт занимает 0,7-2.4x времени cuSPARSE справа и 0,27-2.6x слева. На графе с 1,2 миллиарда ребер продукту требуется 1,1 ГБ на устройстве, что 9x меньше, чем cuSPARSE. Движок ограничен памятью: дерево $k^2$ является предпочтительным форматом, когда ограничением является память устройства, а не время.
## В чем суть открытия В ходе этой работы создается первый вычислительный механизм на графическом процессоре для сжатых графов с деревом k2, позволяющий помещать огромные сети с миллиардами ребер в память видеокарты, одновременно выполняя быстрые матрично-векторные операции. ## Как это устроено: принцип работы Вместо того, чтобы следовать медленным цепочкам указателей на уровнях дерева, движок выполняет синхронные по уровням параллельные обходы, при которых дочерние смещения вычисляются статически с использованием параллельных сумм префиксов или крошечных выборочных каталогов рангов. Обрабатывая смежные диапазоны узлов в плитках в глубину, временная память строго ограничивается глубиной дерева, а не размером графа, а декодирование с перестановкой координат в конечных узлах позволяет одной и той же структуре выполнять как левое, так и правое умножение матрицы на вектор. ## Что это меняет на практике Позволяет крупномасштабным графовым базам данных, графам знаний и системам реляционного мышления выполнять высокопроизводительный анализ непосредственно на графических процессорах одной рабочей станции без сбоев из-за нехватки памяти. ## Границы метода и риски Движок ограничен пропускной способностью памяти и основан на кластеризации графов; на некластеризованных графах или одновекторном умножении без кэшированных границ он работает от 1.2x до 5.6x медленнее, чем несжатые форматы CSR. ## Результаты и доказательства - **Комплексный скор значимости:** 9.5 / 10.0 - **Уровень доказательности:** программный бенчмарк и верификация - **Бенчмарки и прирост:** Memory compression ratio (2.3x-27x vs CSR), SpMV execution latency (ms), working set size (MB/GB), throughput (G nnz/s) - **Размер выборки / валидация:** N = 14 real-world graphs up to 1.2 billion edges (Wikidata, Software Heritage, LAW web and social graphs) - **Реализация в открытом доступе:** Да (верифицируемый репозиторий кода)