Исслeдoвaтeли из   MIT рaзрaбoтaли библиoтeку исполнение)   C++, кoтoрaя aвтoмaтичeски гeнeрируeт код, оптимизированный для выполнения операций по-над разреженными тензорами произвольного ранга. При вычислениях с   матрицами время выполнения сего кода было сопоставимо с   оптимизированными вручную программами, а   для тензоров более высокого ранга возлюбленная работала намного быстрее (почти в   сто раз). Статья опубликована в   Proceedings of   the ACM   on Programming Languages, посмотреть держи   работу программы онлайн можно на   посвященном ей   сайте.

При работе с   данными их   только и знает удобно представлять в   виде матриц или тензоров. С   помощью подобной матрицы позволено описать связи между страничками в   Facebook или сопоставить покупателей и   их   отзывы к товарам получи   Amazon. При этом большая часть информации, записанной таким образом, может выдаться «бесполезной». Например, тензор отзывов покупателей на   Amazon содержит примерно 1019   ингредиент, однако отличны от   нуля только 109 из   них. Такие тензоры называются разреженными.

Примеры разреженных матриц. F. Kjolstad et al / Proceedings of the ACM on Programming Languages

Вычисления с   разреженными тензорами (бог) велел значительно ускорить, если учесть тот факт, что при умножении любого числа получи и распишись   ноль всегда получается ноль. Кроме того, хранить результаты промежуточных вычислений неэффективно при больших объемах данных, в крыша с чем нужно провести некоторую дополнительную оптимизацию. Например, вычисление выражения Σi,j AijkBij + Ck   кажется выполняться за   один шаг, а   не   разбиваться на   отдельные операции умножения и   сложения. Обычно такая оптимизация выполняется вручную, и угоду кому) каждого типа операций разрабатывается собственный шаблон (так называемое ядро, kernel).  

Упрощенчество вычислений при работе с разреженными векторами. F. Kjolstad et al / Proceedings of the ACM on Programming Languages

В   этой статье ученые предлагают новоизобретённый инструмент оптимизации произвольных выражений с тензорами, генерирующий программный код автоматически нате   основе анализа структуры данных. Пользователю нужно указать только формат хранения данных и   последовательность операций, которую что в порядке вещей оптимизировать. Чтобы продемонстрировать их   подход, ученые разработали библиотеку   C++, которую они назвали taco (Tensor Algebra COmpiler, Программа Тензорной Алгебры).

Для этого ученые разработали удобный формат хранения данных, основанный держи   представлении тензора в   виде дерева, у   которого число уровней равно рангу тензора (неравно не   считать корень дерева за   отдельный уровень). Затем они определили, (как) будто операции над тензорами (умножение и   сложение) реализуются в   виде операций над такими деревьями. Этак, умножение двух тензоров выполняется с   помощью графов, указывающих направления обхода деревьев, а   суммирование реализуется слиянием двух деревьев. Напоследках, ученые описали рекурсивный алгоритм, который использует эти идеи для генерации шаблонов   заключение.

Пример представления разреженной матрицы с помощью дерева. F. Kjolstad et al / Proceedings of the ACM on Programming Languages

Кроме исследователи сравнили работу разработанной ими библиотеки с   существующими программами. Оказалось, ась? с   вычислениями над разреженными матрицами она справляется так   же хорошо, в качестве кого и   все оптимизированные вручную алгоритмы, а   в   некоторых случаях время вычислений с   помощью taco оказывалось ажно меньше. При работе   же с   тензорами более высокого ранга taco превосходил существующие аналоги во   отбою) раз. Например, тензоры   третьего ранга, сформированные на   основе анализа постов в   локальной шатер Facebook Нового Орлеана, новый алгоритм перемножал в   114 раз быстрее, нежели MATLAB Tensor Toolbox.

Ранее мы   писали о   том, как исследователи из   MIT разработали программу, которая автоматически ищет и   исправляет ошибки в   исходном коде других программ. А   ученые из   Кембриджа научили искусственный интеллект воровать адрес и   собирать из   него собственные проекты.

Автор: Дмитрий Трунин