Вычисление Разреженного Тензора С Открытым Исходным Кодом Выполняется Быстро


Тензоры-это таблицы данных в n измерениях, и когда они возникают, они часто разрежены, т. Е. Большинство записей равно нулю. В прошлом у нас был ручной код для эффективной работы с разреженными тензорами, но теперь у нас есть Taco, компилятор с открытым исходным кодом, который может автоматически генерировать код, который может работать в 100 раз быстрее. 

Тензор-это матрица в более чем двух измерениях. Куб данных-это тензор ранга 3 и так далее. Большая проблема с тензорами заключается в том, что они часто большие, и для их хранения просто недостаточно места. Однако многие тензоры разрежены – в основном пустые. Например, клиенты Amazon, сопоставленные с купленными продуктами, представляют собой очень большую таблицу с большим количеством нулей.

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

Исследователи из Массачусетского технологического института, Французской комиссии по альтернативным энергиям и атомной энергии и Adobe Research проанализировали эту проблему и внедрили компилятор для манипулирования разреженными тензорами. Система, называемая Taco – компилятором тензорной алгебры, является открытым исходным кодом и может использоваться в качестве библиотеки C++ и может генерировать ядра C, которые выполняют определенные операции. Обычно, когда вы выполняете разреженные тензорные вычисления, они, как правило, разбиваются на компоненты. Например, AB+C обычно реализуется с помощью кода, который умножает A и B, а затем код, который добавляет C к результату. За кулисами это включает в себя повторение разреженных структур более одного раза.

Чтобы быть более эффективным, Taco генерирует набор итераций через разреженные структуры, которые выполняют AB+C за один проход – это ядро операции. 

Вот пример тензора ранга 3,умноженного на одномерный вектор с использованием библиотеки Taco C++. 

Обратите внимание, что каждый тензор, объявленный в начале, может иметь отдельные плотные и разреженные измерения, и Taco учитывает это при создании итераций для каждого измерения.

Другая оптимизация заключается в том, что Taco автоматически использует схему индексации для хранения только ненулевых значений. Например, таблица Amazon, которая сопоставляет идентификационные номера клиентов с покупками и условиями из отзывов, занимает 107 экзабайт данных. Taco представляет тот же тензор всего в 13 гигабайтах. 

Для удивительно подробного взгляда на Тако смотрите официальное видео:

Вы можете получить исходный код Taco под лицензией MIT с его веб-сайта.


Добавить комментарий