Это статья из серии Seminal Papers in ML, выпущенная MIT Machine Intelligence Community (MIC). MIT MIC стремится обучить сообщество в целом машинному обучению и снизить барьеры для входа. Чтобы узнать больше, посетите https://mitmic.io или напишите по адресу [email protected].

Глубокие нейронные сети (DNN) обеспечивают беспрецедентную точность и производительность во все более широком спектре промышленных приложений, таких как распознавание изображений, обработка естественного языка и другие сложные задачи, такие как управление автономными транспортными средствами. Несмотря на значительное улучшение результатов по сравнению со старыми алгоритмами машинного обучения, DNN очень требовательны с точки зрения вычислений и требуют обучения на больших наборах данных, что занимает много времени. Таким образом, логично, что было предпринято много усилий, чтобы ускорить как время обучения, так и время вывода (время, необходимое для фактического прогнозирования с учетом обученной модели) DNN. Это позволяет нам обучать большему количеству данных за меньшее время, а также быстрее делать выводы на менее мощных устройствах, таких как мобильные телефоны или встроенные системы. В своей статье Оптимальный выбор примитивов DNN с помощью секционированного булево-квадратичного программирования (PBQP) Эндрю Андерсон и Дэвид Грегг используют гибридный подход к оптимизации вычислений DNN. Они сосредоточены на поиске решения проблемы выбора примитивов DNN, которую можно описать как решение, какие алгоритмы и библиотеки использовать для запуска каждого уровня DNN - проблема подробно объясняется ниже. Они также сводят проблему к известной проблеме NP-жесткого графа, PBQP, и используют для ее решения стандартный решатель PBQP.

При оценке результатов особое внимание уделяется операции свертки, которая требует чрезвычайно больших вычислительных ресурсов и используется почти во всех DNN обработки изображений - такие сети называются сверточными нейронными сетями (CNN).

Примитивы DNN и их значение

DNN состоят из ориентированного графа слоев, и именно на направленных ребрах между этими уровнями возникают потоки данных. Каждый уровень обрабатывает данные и состоит из стандартных математических операторов, таких как свертка, активация, объединение или полносвязные слои. Выходные данные одного уровня передаются в следующий, что соответствует потокам данных. Эти уровни реализованы как набор примитивов подпрограмм, где каждый примитив представляет собой оптимизированную реализацию этих математических операций. Существует множество возможных алгоритмов и реализаций для уровня, что равносильно тому, что существует множество вариантов доступных для использования примитивных подпрограмм, состоящих как из реализаций с открытым исходным кодом, так и из проприетарных библиотек. Например, Winograd и FFT - это два алгоритма, которые можно использовать для реализации свертки. Важно отметить, что эти примитивы работают по-разному в разных сценариях, в зависимости от спецификаций уровня. Цель состоит в том, чтобы выбрать лучшую примитивную процедуру для каждого уровня, чтобы минимизировать общее время работы всей сети - эта проблема называется оптимальным выбором примитивов DNN.

Что такое слои свертки?

Хотя используемая методология является общей и может быть легко реализована и протестирована для любого типа слоя, оценка сосредоточена только на сверточных слоях. Обычно они доминируют во времени выполнения, а также используются во многих важных CNN для обработки изображений. Входными данными для сверточного слоя обычно является тензор, обычно трехмерное или четырехмерное представление двухмерного изображения. Например, для трехмерного представления типичного цветного двухмерного изображения первые два измерения обычно кодируют горизонтальное и вертикальное положение пикселя, а третье измерение обычно хранит количество красного, зеленого и синего цвета в изображении. пиксель. Слой свертки обрабатывает этот тензор, перемещая серию небольших фильтров или ядер по изображению для выполнения операции математической свертки. Контур показан на диаграмме ниже, где изображение размером H × W × C свернуто с ядром размера k × k × C, чтобы получить выходное изображение (называемое картой характеристик) размером H × W - и поскольку таких ядер M, результат представлен в виде тензора размера H × W × M. Здесь важно наличие нескольких ядер, поскольку они позволяют сети изучать различные функции и шаблоны. Например, одно ядро ​​может попытаться обнаружить кошку на изображении, а другое ядро ​​может научиться обнаруживать собак. Результирующий тензор - с выходными данными всех ядер - затем может быть передан в max-pooling layer, который определит, какой из этих M шаблонов является наиболее значимым, например, обнаружило ли ядро ​​cat лучшее совпадение, чем ядро ​​собаки - это обеспечивает высокую точность классификации изображений.

Выбор примитивов и согласование формата данных в слоях свертки

Существует большое количество различных примитивов для свертки. Методы прямого цикла, im2, kn2, Winograd и FFT (с использованием алгоритмов быстрого преобразования Фурье) - это все семейства алгоритмов, которые могут использоваться для реализации свертки. Как упоминалось ранее, производительность каждого алгоритма зависит от параметров и спецификаций сверточного слоя. Например, методы прямого цикла хорошо работают с последовательной сверткой, при которой ядро ​​пропускает некоторые входные пиксели, чтобы получить меньшее выходное изображение, и семейство im2 хорошо справляется и в этом случае. Однако методы прямого цикла обычно медленнее, а алгоритмы im2 очень интенсивны в памяти. Виноград очень быстр, но непредсказуем. БПФ также является вариантом с балансом преимуществ производительности, но плохо для небольших ядер; несмотря на более низкую асимптотическую сложность, он имеет большие накладные расходы, поэтому более низкая сложность полезна только при больших входных данных. Другие параметры, такие как количество каналов (то есть значение C на диаграмме выше), также влияют на оптимальный выбор примитива.

Поскольку в типичной CNN параметры для каждого уровня сильно различаются, имеет смысл иметь различный выбор примитива для каждого уровня, чтобы минимизировать общее время выполнения вычислений во всей сети. На первый взгляд, это кажется очень простой проблемой: перед запуском всей сети мы могли бы просто опробовать каждый примитив на каждом уровне и отметить время выполнения в списке (назовем этот список «вектором затрат»). . Для этого пробного запуска мы можем просто использовать случайные входные значения, поскольку время выполнения на самом деле не зависит от самих значений, а зависит только от их общего количества. Собственно, этим и занимаются авторы с самого начала.

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

Здесь слои свертки представлены в виде узлов: conv1, conv2 и conv3. И эти три примитива - это A, B и C. Показаны векторы стоимости примитивов (определенные пробными запусками) для каждого уровня, и мы можем видеть, что оптимизация всей сети - это просто выбор примитива минимальной стоимости. В этом случае он соответствует алгоритму выбора B для conv1, алгоритму C для conv2 и снова алгоритму B для conv3. Общая стоимость сети - это просто сумма затрат на каждый уровень.

Однако в этом наивном решении упускается один важный аспект. Он не принимает во внимание тот факт, что каждый из примитивов работает с данными в разных форматах данных. Например, некоторые примитивы принимают и производят выходные значения в 16-битном формате с плавающей запятой, а другие используют 32-битные числа с плавающей запятой. Некоторые примитивы также требуют определенных перестановок размеров входных изображений - CHW (канал × высота × ширина) и HWC (высота × ширина × канал) - это два разных формата данных, и определенные примитивы могут работать только с одним из форматов. Другой пример: если кто-то работает с сигналами, данные могут быть представлены в представлении частотной области или в представлении временной области (это просто разные способы представления одного и того же сигнала), и разные примитивы могут поддерживать только один из этих форматов. Это необходимо учитывать, как показано на диаграмме выше, возможно, что conv1 использует другой формат данных, чем conv2, и данные нужно будет преобразовать из этого формата conv1 в формат conv2, прежде чем он сможет пройти между ними - это преобразование требует времени. Таким образом, нам необходимо учитывать стоимость преобразования формата данных в нашей оптимизации.

PBQP

Результирующая задача оптимизации теперь учитывает не только время выполнения примитивов, но также время преобразования формата данных между примитивами, используемыми в последовательных слоях. Авторы показывают, что это эквивалентно известной NP-сложной задаче Partitioned Boolean Quadratic Programming (PBQP). В PBQP нам дается граф, и каждому узлу должна быть назначена метка из заданного набора меток, представляющих затраты. Таким образом, каждый узел имеет вектор стоимости для всех меток, и это аналогично задаче на предыдущем графике. Стоимость выбора метки для узла добавляет соответствующую стоимость к общей стоимости нашей цели, которую мы хотим минимизировать. Но помимо стоимости узлов существует еще и стоимость каждого ребра. Стоимость ребра зависит как от выбора метки для исходного узла, так и от выбора метки для целевого узла. Поскольку он зависит от меток обоих подключенных узлов, его можно рассматривать как матрицу (поскольку она индексируется двумя метками). Это показано на схеме ниже:

На диаграмме выше видно, что примитив с наименьшей стоимостью для conv1 - это примитив b со стоимостью 6, а примитив с наименьшей стоимостью для conv2 является примитивом c со стоимостью 14. Но теперь мы также должны учитывать затраты на грани, и использование этого назначения дает дополнительную стоимость ребра 5, которая определяется путем соответствующей индексации в матрицу стоимости ребер. Так что на самом деле выбор примитива c для conv1 лучше, поскольку он дает нулевую стоимость. Тогда общая стоимость - это просто сумма всех затрат на узлы и грани - теперь это цель, которую мы хотим минимизировать.

Внедрение и тестирование

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

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

После того, как векторы и матрицы затрат готовы, для получения оптимального примитивного выбора для DNN, который будет тестироваться, используется стандартный решатель PBQP. Производительность тестировалась на трех популярных нейронных сетях: AlexNet, VGG Model E и GoogleNet. Время выполнения сравнивается с производительностью при использовании только одного примитива, а также с Caffe (популярный фреймворк для глубокого обучения). Также включен тест Intel MKL-DNN library, который представляет собой оптимизированный JIT-компилятор для примитивов DNN. Эксперименты проводились на разных аппаратных архитектурах, и результаты по скорости для Intel Haswell показаны ниже (чем выше, тем лучше):

Как мы видим, в Intel Haswell примитивное назначение PBQP превосходит все другие методы в случае нескольких потоков, даже собственный компилятор нейронной сети MKL-DNN от Intel. В случае работы одного потока MKL-DNN немного лучше по производительности в сетях AlexNet и GoogleNet, но метод PBQP подходит очень близко и по-прежнему превосходит остальные методы. Для VGG метод PBQP также превосходит MKL-DNN.

Результаты производительности для ARM Cortex показаны ниже (чем выше, тем лучше):

Здесь мы также можем видеть, что назначение PBQP превосходит любую другую реализацию сетей на архитектуре ARM Cortex-A57.

Обсуждение и заключение

Из экспериментальных результатов ясно, что формулировка PBQP чрезвычайно эффективна при выборе оптимальных примитивов для реализации DNN. Существуют и другие структуры оптимизации DNN, и некоторые используют аналогичные методы для ускорения вычислений DNN. Возможно, самым быстрым примером является cuDNN от NVIDIA, которая также использует реализацию / примитив, которая, скорее всего, будет самой быстрой для данного уровня. Это отличается от решателя PBQP тем, что он не принимает во внимание затраты на границу, то есть время на преобразование форматов данных. Tensorflow XLA - еще один фреймворк, который по сути является опережающим компилятором для DNN. Он вычисляет затраты на межуровневые переходы и преобразования формата данных и пытается объединить слои, чтобы избежать этих затрат, что в некоторой степени аналогично подходу PBQP. Результаты показывают, что метод PBQP улучшает время выполнения DNN и, таким образом, возможно, хорошо подходит для использования в рамках оптимизации DNN для улучшения. Авторы представили этот документ на Международном симпозиуме по генерации и оптимизации кода (CGO) 2018, и методы, использованные в этом документе, позволяют нам быстрее обучать DNN, а также выполнять глубокое обучение и логический вывод на все большем количестве недорогих мобильных и встроенных устройств. процессоры.

об авторе

Али Зарташ - растущий выпускник Массачусетского технологического института (MIT) и член сообщества Machine Intelligence Community (MIC) Массачусетского технологического института, клуба ИИ для студентов. Этим летом он проходит стажировку в Google, работая над конвейерами данных и графиками для систем социального рейтинга / рекомендаций, а ранее он стажировался в SpaceX, где работал над распределением нагрузки на GPU. В свободное время он играет с друзьями в футбол. Узнайте больше о MIC на http://mitmic.io.