В MIT создали алгоритм, ускоряющий обработку больших данных в 100 раз

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

Разрежённые тензоры

Представьте объём данных, которые являются отображением множества абсолютно всех клиентов Amazon во множество всех товаров, представленных на площадке. Подобные многомерные тензорные матрицы будут иметь 1 на месте, обозначающем, что клиент уже приобрёл товар, а 0 — во всех остальных. Эти матричные кубы будут, в основном, состоять из нулей. Они же, в свою очередь, при математических операциях над таблицами вхолостую тратят ресурсы процессора и требуют слишком много места для хранения в памяти.

Большинство программистов, чтобы обойти существующую проблему разрежённости матриц, писали громоздкий код, который в результате применим лишь к узкой области возникающих проблем. Сотрудники MIT на прошедшей конференции SPLASH представили систему, которая автоматически создаёт код, оптимизированный для разрежённых данных.

Система Тасо

Система под названием Taco является компилятором для программ тензорной алгебры. Результат работы в 100 раз превосходит в производительности существующие неоптимизированные пакеты ПО. Он также сопоставим с характеристиками вручную написанного и оптимизированного под определённые задачи кода, требуя при этом гораздо меньшее участие со стороны программиста.

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

Существующие подходы решения проблемы

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

Ядра вычислений

Однако, в эпоху больших данных подобный подход потребляет очень много времени. Сейчас же Taco совершает множественные расчёты в рамках одного цикла, или так называемого ядра. Один из авторов предложенной системы, Фредрик Кьолстад, добавляет:

Если все операции происходят в одном ядре, все вычисления производятся быстрее, без дополнительного помещения промежуточных результатов в память с последующим чтением из неё. Подход Тасо всё делает в одну итерацию.

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

Отметим, что для работы c Taco программисту необходимо указать лишь размерность используемого тензора, является ли он полностью разрежённым и, разумеется, директорию, где находится файл с данными.

Результаты работы

Результаты работы впечатляют. Весь объём данных Amazon при использовании разрежённых тензорных таблиц составляет порядка 107 эксабайт, что примерно в 10 раз больше ёмкости всех серверов Google. При использовании же схемы сжатия Taco большие данные Amazon займут всего 13 гигабайт, что с лёгкостью вместит любой современный смартфон.

Садай Садаяппан, профессор компьютерных наук университета Огайо, восторгается предложенной системой:

Их компилятор позволяет разработчикам использовать очень сложные разрежённые матрицы без заботы о производительности их вычисления. Он автоматически сгенерирует самый эффективный код. Их система меняет ход игры в сфере компьютерных вычислений и анализа больших данных. Это одно из самых захватывающих достижений в области оптимизации компиляторов.