Новый алгоритм перемножил разреженные тензоры в сто раз быстрее

Примеры разреженных матриц
F. Kjolstad et al / Proceedings of the ACM on Programming Languages
Исследователи из MIT разработали библиотеку для C++, которая автоматически генерирует код, оптимизированный для выполнения операций над разреженными тензорами произвольного ранга. При вычислениях с матрицами время выполнения этого кода было сопоставимо с оптимизированными вручную программами, а для тензоров более высокого ранга она работала намного быстрее (почти в сто раз). Статья опубликована в Proceedings of the ACM on Programming Languages, посмотреть на работу программы онлайн можно на посвященном ей сайте.
При работе с данными их часто удобно представлять в виде матриц или тензоров. С помощью подобной матрицы можно описать связи между страничками в Facebook или сопоставить покупателей и их отзывы к товарам на Amazon. При этом большая часть информации, записанной таким образом, может оказаться «бесполезной». Например, тензор отзывов покупателей на Amazon содержит примерно 1019 компонент, однако отличны от нуля только 109 из них. Такие тензоры называются разреженными.
Вычисления с разреженными тензорами можно значительно ускорить, если учесть тот факт, что при умножении любого числа на ноль всегда получается ноль. Кроме того, хранить результаты промежуточных вычислений неэффективно при больших объемах данных, в связи с чем нужно провести некоторую дополнительную оптимизацию. Например, вычисление выражения Σi,j AijkBij + Ck должно выполняться за один шаг, а не разбиваться на отдельные операции умножения и сложения. Обычно такая оптимизация выполняется вручную, и для каждого типа операций разрабатывается собственный шаблон (так называемое ядро, kernel).
Для этого ученые разработали удобный формат хранения данных, основанный на представлении тензора в виде дерева, у которого число уровней равно рангу тензора (если не считать корень дерева за отдельный уровень). Затем они определили, как операции над тензорами (умножение и сложение) реализуются в виде операций над такими деревьями. Так, умножение двух тензоров выполняется с помощью графов, указывающих направления обхода деревьев, а суммирование реализуется слиянием двух деревьев. Наконец, ученые описали рекурсивный алгоритм, который использует эти идеи для генерации шаблонов кода.
Ранее мы писали о том, как исследователи из MIT разработали программу, которая автоматически ищет и исправляет ошибки в исходном коде других программ. А ученые из Кембриджа научили искусственный интеллект воровать код и собирать из него собственные проекты.
Дмитрий Трунин