GADES: GPU-ускорение расстояний Кендалла для больших данных

Рис. 5 из оригинальной статьи. Для тёмной темы адаптирована только палитра изображения, данные не изменены.

GADES (GPU-Assisted Distance Estimation Software) помогает быстрее вычислять попарные расстояния Кендалла в больших и разреженных данных. Пакет использует параллельные вычисления на GPU, делит входные данные на пакеты и отдельно оптимизирует работу с матрицами, в которых много нулей.

Работа опубликована в журнале GigaScience в 2024 году под названием GPU-accelerated Kendall distance computation for large or sparse data. Павел Ахтямов указан первым автором.

Какую задачу решает GADES

Коэффициент Кендалла сравнивает порядок элементов в двух наблюдениях. Если пары признаков расположены в разном порядке, они вносят вклад в несогласованность. Расстояние Кендалла показывает долю таких несогласованных пар и позволяет сравнивать объекты между собой.

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

В биоинформатике добавляется ещё одна трудность: матрицы scRNA-seq и scATAC-seq часто содержат много нулей. Обычный плотный расчёт выполняет лишнюю работу, а простое использование GPU не решает автоматически ни алгоритмическую сложность, ни ограничение видеопамяти.

Что предложила оригинальная работа

Массовый параллелизм на GPU

Независимые элементы матрицы расстояний вычисляются параллельно через CUDA. В статье также предусмотрен CPU-режим: на небольших данных он помогает избежать накладных расходов на передачу данных и инициализацию GPU.

Пакетная обработка

Входная матрица делится на пакеты, которые помещаются в доступную память GPU. Промежуточные результаты объединяются в итоговую матрицу. Такой подход уменьшает ограничение со стороны видеопамяти при вычислениях, но не отменяет квадратичный размер самой матрицы попарных расстояний.

Разреженный режим

Для данных с большим числом нулей алгоритм учитывает только нужные ненулевые элементы и диапазоны между ними. В статье использованы представления COO и CSR, а также метод сканирующей линии. За счёт этого число операций зависит сильнее от структуры ненулевых значений, а не только от полного размера матрицы.

Вклад Павла Ахтямова

Раздел Author Contributions в полном тексте статьи приписывает Павлу ведущую роль в Data curation, Formal Analysis и Software. Он также внёс вклад в исследование, валидацию, визуализацию, подготовку первоначального текста и редактирование статьи. Работа выполнена в соавторстве с Ausaaf Nabi, Vladislav Gafurov, Alexey Sizykh, Alexander Favorov, Yulia Medvedeva и Alexey Stupnikov.

Формулировка «первый автор и участник разработки» точнее, чем присваивание всего проекта одному человеку: программная реализация, научный замысел, ресурсы и текст статьи являются результатом совместной работы.

Что показали эксперименты

Авторы сравнивали GADES с amap, factoextra, scipy и pandas на синтетических и реальных наборах scRNA-seq и scATAC-seq. Для GPU-экспериментов использовалась NVIDIA RTX 3090, а повторные запуски позволяли учитывать вариативность времени вычисления.

На синтетических плотных данных авторы сообщают, что GPU-режим GADES оказался в 75 раз быстрее ближайшего сравниваемого пакета pandas в принятой экспериментальной конфигурации.
На успешно обработанных реальных наборах ближайший сравниваемый пакет pandas оказался в 7,8 раза медленнее разреженного GPU-режима GADES. Авторы отдельно отмечают, что на реальных данных эффект меньше, чем на синтетических разреженных матрицах.
Некоторые наборы не были обработаны методами в пределах суточного лимита. Поэтому выводы статьи относятся к описанным данным и настройкам, а не означают одинаковое ускорение на любой задаче.

Условия сравнения и ограничения приведены в статье, а код для воспроизведения связан с публикацией через раздел Data Availability.

Код и отличие текущего репозитория от статьи

Открытый код находится в репозитории lab-medvedeva/GADES-main. Именно этот адрес указан в опубликованной статье. Адрес https://github.com/lab-medvedeva/GADES при проверке 24 октября 2026 года возвращал 404, поэтому здесь используется фактический репозиторий.

Оригинальная статья описывает R/CUDA-пакет для расстояний Кендалла. Текущее описание репозитория уже включает общее C++/CUDA-ядро, интерфейсы для R и Python и дополнительные метрики. Новые возможности репозитория не нужно задним числом приписывать статье 2024 года: публикация и развивающийся код фиксируют разные состояния проекта.