Дослідники з MIT розробили бібліотеку для C++, яка автоматично генерує код, оптимізований для виконання операцій над розрідженими тензорами довільного рангу. При обчисленнях з матрицями час виконання цього коду був порівнянний з оптимізованими вручну програмами, а для тензорів більш високого рангу вона працювала набагато швидше (майже в сто разів). Стаття опублікована в, подивитися на роботу програми онлайн можна на присвяченому їй сайті.
При роботі з даними їх часто зручно представляти у вигляді матриць або тензорів. За допомогою подібної матриці можна описати зв'язки між сторінками в Facebook або зіставити покупців і їх відгуки до товарів на Amazon. При цьому велика частина інформації, записаної таким чином, може виявитися «марною». Наприклад, тензор відгуків покупців на Amazon містить приблизно 1019 компонент, проте відмінні від нуля тільки 109 з них. Такі тензори називаються розрідженими.
Обчислення з розрідженими тензорами можна значно прискорити, якщо врахувати той факт, що при множенні будь-якого числа на нуль завжди виходить нуль. Крім того, зберігати результати проміжних обчислень неефективно при великих обсягах даних, у зв'язку з чим потрібно провести деяку додаткову оптимізацію. Наприклад, обчислення виразу I, j AijkBij + Ck має виконуватися за один крок, а не розбиватися на окремі операції множення і додавання. Зазвичай така оптимізація виконується вручну, і для кожного типу операцій розробляється власний шаблон (так зване ядро, kernel).
У цій статті вчені пропонують новий інструмент оптимізації довільних виразів з тензорами, що генерує програмний код автоматично на основі аналізу структури даних. Користувачеві потрібно вказати тільки формат зберігання даних і послідовність операцій, яку треба оптимізувати. Щоб продемонструвати їхній підхід, вчені розробили бібліотеку C++, яку вони назвали taco (Tensor Algebra COmpiler, компілятор Тензорної Алгебри).
Для цього вчені розробили зручний формат зберігання даних, заснований на представленні тензора у вигляді дерева, у якого число рівнів дорівнює рангу тензору (якщо не рахувати корінь дерева за окремий рівень). Потім вони визначили, як операції над тензорами (множення і додавання) реалізуються у вигляді операцій над такими деревами. Так, множення двох тензорів виконується за допомогою графів, що вказують напрямки обходу дерев, а підсумовування реалізується злиттям двох дерев. Нарешті, вчені описали рекурсивний алгоритм, який використовує ці ідеї для генерації шаблонів коду.
Потім дослідники порівняли роботу розробленої ними бібліотеки з існуючими програмами. Виявилося, що з обчисленнями над розрідженими матрицями вона справляється так само добре, як і всі оптимізовані вручну алгоритми, а в деяких випадках час обчислень за допомогою taco виявлялося навіть менше. При роботі ж з тензорами більш високого рангу taco перевершував існуючі аналоги у багато разів. Наприклад, тензори третього рангу, сформовані на основі аналізу постів у локальній мережі Facebook Нового Орлеана, новий алгоритм перемножував у 114 разів швидше, ніж MATLAB Tensor Toolbox.
Раніше ми писали про те, як дослідники з MIT розробили програму, яка автоматично шукає і виправляє помилки у вихідному коді інших програм. А вчені з Кембриджу навчили штучний інтелект красти код і збирати з нього власні проекти.