Acceleration of tensor computations using the residual class system

Full Text

Интенсивное развитие вычислительной техники и методов хранения больших объемов информации в облачных средах привело к серьезному прогрессу в области разработки методов машинного обучения. Одним из наиболее перспективных подходов в области искусственного интеллекта являются глубокие нейронные сети, которые уже показывают впечатляющие результаты в распознавании речи [1], изображений [2] и настольных играх типа шахмат [3]. Базовым элементом глубоких нейронных сетей является искусственный нейрон, математическая модель которого состоит в вычислении нелинейной функции от скалярного произведения входного сигнала на вектор весовых коэффициентов, что является простейшим примером тензорной операции. Искусственные нейроны объединяются в слои, которые, в свою очередь, организуются в последовательную структуру таким образом, что выходной сигнал предыдущего слоя подается на вход последующего слоя. Размерность пространства сигнала, передаваемого между слоями глубокой нейронной сети, может варьироваться в зависимости от решаемой задачи. Основным научно-практическим барьером для широкого распространения глубоких нейронных сетей является высокая вычислительная сложность тензорных операций, используемых в них. Например, сеть AlexNet, разработанная для распознавания цветных изображений размером 224 224 × пикселя, содержит 650 тысяч нейронов, 60 миллионов настраиваемых параметров, 630 миллионов связей для передачи данных между нейронами и обучалась в течение недели с использованием двух GPU Nvidia [4]. Другая сеть, разработанная для решения той же задачи, GoogLeNet, требует выполнения около 1,5 млрд арифметических действий при обработке одного изображения [5]. Реализация таких нейронных сетей на современных CPU и GPU является малоэффективной с точки зрения аппаратных, временных и энергетических затрат. Это делает задачу поиска альтернативных путей решения данной проблемы весьма актуальной. Одним из возможных решений задачи оптимизации тензорных вычислений для глубоких нейронных сетей является реализация вычислительных алгоритмов на современных сверхбольших интегральных схемах FPGA [6] и ASIC [7]. Базовым блоком при реализации тензорных алгоритмов типа скалярного произведения или свертки является умножитель с накоплением. Одним из примеров универсальной реализации такого устройства является сигнальный процессор DSP48A1, разработанный компанией Xilinx, одним из ведущих производителей FPGA на сегодняшний день [8]. Другим примером специализированной разработки, оптимизированной под тензорные вычисления в глубоких нейронных сетях, является тензорный процессор TPU Google, объединяющий в одном устройстве 3 64 10 ⋅ умножителей с накоплением [9]. При этом практически все усилия исследователей в области оптимизации тензорных вычислений направлены на разработку новых устройств, функционирующих в традиционной двоичной арифметике. Авторы статьи предлагают альтернативный подход к решению данной проблемы, основанный на арифметике системы остаточных классов (СОК). Идея использования СОК состоит в преобразовании вычислительного диапазона системы в прямую сумму конечных колец по модулям малой величины. Такой подход позволяет выполнять арифметические операции сложения, вычитания и умножения параллельно и без взаимодействия между вычислительными каналами, при этом малый размер модулей СОК позволяет существенно уменьшить аппаратные и временные затраты на реализацию арифметико-логических устройств. Известные на сегодняшний день архитектуры устройств, оптимизирующих вычисления в глубоких нейронных сетях и использующих СОК, построены в виде комбинационных схем [10-12]. В данной работе мы продемонстрируем эффективность использования табличной памяти в СОК для ускорения тензорных вычислений на FPGA. Тензорные вычисления в системе остаточных классов Рассмотрим тензор как полилинейную форму от n векторных аргументов ( ) 1 2 1 2 12 12 ... , ,..., ... ... . ϕ=ϕ = =∑∑ ∑ nn n n ii i i i i i i i x x x a x x x (1) Основными тензорными операциями, используемыми в глубоких нейронных сетях, являются скалярное произведение, являющееся тензором валентности 2, и свертка 1 , , , 0 (,,) ( , , ) - ++ =- =- = = = ++ ∑∑∑ f t t D i t j t z k i t j t z I x y k W I x i y j z (2) трехмерных данных, например, цветного изображения ( ) ,, Ixyz с маской W тензора, описывающего слой нейронов. Тензорные операции, определяемые (1), (2), требуют выполнения только арифметических операций сложения и умножения, которые могут быть эффективно реализованы в СОК. Математической основой СОК является представление кольца вычетов по модулю M в виде прямой суммы колец вычетов по попарно взаимно простым модулям 12 , ,..., , n m m m ( ) , 1, =ÍÎÄ ij mm ≠ij : 12... , = ⊕ ⊕ ⊕ n M m m m Z Z Z Z (3) причем 12 ... = n mm m M принято называть динамическим диапазоном СОК. Такое представление обосновывается китайской теоремой об остатках, устанавливающей взаимно однозначное соответствие между числами ∈ M XZ и векторами ( ) 12 1 , ,..., ( mod , =n x x x X m 2mod ,..., mod ) n XmXm (4) по формуле 1 1 ,- = = ∑ i n i i i m i M X M M x (5) где = i i MM m и 1 - i i mM означает мультипликативный обратный элемент для i M по модулю , im 1,2, , .=  in Практический смысл представления, описываемого (3), (4), состоит в гомоморфизме арифметических операций: числам ( )+∈ M X Y Z и ( )∈ M XY Z соответствуют векторы ( ) ( ) ( 1 1 1 2 2 2 mod , mod ,... ++ x y m x y m ( ) ) ..., mod += n n n x y m ( ) ( ) ( 12 mod , mod ,... = + + X Y m X Y m ( ) ) ..., mod + n X Y m (6) и ( ) ( ) ( 1 1 1 2 2 2 mod , mod ,... x y m x y m ( ) ) ..., mod = n n n x y m ( ) ( ) ( 12 mod , mod ,...= XY m XY m ( ) ) ..., mod n XY m . (7) При выборе модулей i m достаточно малыми можно реализовать операции ( )mod + n n n x y m ( )mod n n n x y m в табличной форме. Пример. Пусть 5. =m Двоичное представление элементов кольца вычетов 5 Z требует 3 бит информации. Таблицы сложения и умножения в кольце 5 Z чисел, представленных в двоичной форме, имеют следующий вид: X+Y mod 5 Y 000 001 010 011 100 X 000 000 001 010 011 100 001 001 010 011 100 000 010 010 011 100 000 001 011 011 100 000 001 010 100 100 000 001 010 011 XY mod 5 Y 000 001 010 011 100 X 000 000 000 000 000 000 001 000 001 010 011 100 010 000 010 100 001 011 011 000 011 001 100 010 100 000 100 011 010 001 Вычислим в кольце 5 Z выражение 2 3 4, ⋅+ которое представляет собой операцию умножения с накоплением. Из таблицы умножения по модулю 5 находим: 22 2 3 010 011 ⋅ = ⋅ = 2001 1. = Из таблицы сложения по модулю 5 находим: 221 4 001 100 + = + = 2000 0. = Проверка показывает, что 2 3 4 ⋅+≡( ) 0 mod 5 . Приведенный пример демонстрирует быстроту и удобство выполнения арифметических операций со сложностью ( ) 1O ценой экстенсивного использования памяти. Для хранения таблицы умножения по модулю m с разрядностью 2log=   bm бит требуется 2 mb бит памяти. С учетом того, что для сложения требуется таблица такого же размера, полные затраты памяти на реализацию арифметики по модулю m составят 22 mb бит памяти. Например, затраты памяти для реализации табличных вычислений по 6-битным модулям составят от 13 068 до 49 152 бит памяти, а для реализации табличных вычислений по 8-битным модулям составят от 266 256 до 1 048 576 бит памяти. Дальнейшее увеличение разрядности модулей приведет к резкому росту затрат памяти и может оказаться нецелесообразным. Рассмотрим множество попарно взаимно простых 6-битных модулей {64, 63, 61, 59, 55, 53, 47, 43, 41, 37}, из которых можно составить СОК с диапазоном 129 685 918 863 695 040≈ 56,8 2 для представления 56-битных чисел. Такой диапазон достаточен для реализации большинства современных глубоких нейронных сетей [13], при этом попытка составить таблицы сложения и умножения по модулю такого диапазона потребует использовать 120 2≈ бит памяти, что на нынешнем уровне развития технологий вычислительной техники представляется невозможным. Поэтому для реализации арифметических действий в таком диапазоне необходимо использовать комбинационные устройства сложения и умножения, имеющие сложности времени вычисления порядка ( ) Ob и ( ) 2 Ob соответственно. Применение же предложенного подхода на основе СОК позволяет уменьшить каждую из этих сложностей до ( ) 1O за счет примерно 500 Кбит памяти, что окажется особенно ощутимым при выполнении большого количества операций умножения с накоплением в тензорных вычислениях. Экспериментальное моделирование тензорных вычислений в СОК Экспериментальная проверка предложенного метода проводилась на основе моделирования устройств, реализующих тензорные вычисления, с использованием FPGA Xilinx Spartan6 xc6slx9, установленной в FPGA Development board ALINX AX309. Данное устройство обладает ресурсами, представленными в таблице. Было разработано устройство для проверки возможности размещения и эффективной работы 20 BRAM-блоков ПЗУ объемом 4096 6-битных ячеек каждая. Испытания показали, что ресурсов FPGA-микросхемы Spartan6 xc6slx9 достаточно для хранения 20 BRAM-блоков емкостью 4096 6-битовых ячеек, работающих в режиме ПЗУ. Для моделирования вычислений по формуле (7) были выбраны задача выполнения умножения целых неотрицательных чисел в СОК по модулю 31 и умножение 6-битных чисел в двоичной системе счисления без использования методов акселерации на основе блоков DSP48A1 с вычислением результата по модулю 64 простым взятием 6 младших бит результата вычислений. Экспериментальное моделирование показало двухкратное превосходство умножения в СОК над результатом в двоичной системе счисления. Время минимального прохождения электрического импульса через схему составило 6,119 нс, что соответствует максимальной частоте работы устройства 163 МГц. Внешний вид разработанного устройства показан на рисунке. Моделирование операции свертки по формуле (2) проводилось методом замера скорости выполнения операции, содержащей от 900 до 3100 слагаемых, каждое из которых представляет собой произведение двух 56-битных двоичных чисел. Каждое двоичное 56-битное число было представлено в виде 10 остатков от деления на набор взаимно простых оснований СОК {64, 63, 61, 59, 55, 53, 47, 43, 41, 37} по формуле (4). Генерация входных аргументов для операции свертки производилась 10-ю аппаратными 16-битными LFSR-генераторами псевдослучайных чисел. Время минимального прохождения электрического импульса через схему составило 6,384 нс, что соответствует максимальной частоте работы устройства 156 МГц. Обобщая результаты моделирования, можно сделать вывод о двукратном превосходстве скорости тензорных вычислений в СОК по сравнению с вычислениями в двоичной системе счисления. Данный факт может быть использован при разработке аппаратных ускорителей на основе FPGA для глубоких нейронных сетей. Заключение Мы предложили метод реализации тензорных вычислений в системе остаточных классов с использованием табличной арифметики для модульных операций шириной до 8 бит включительно. Экспериментальное моделирование предложенного метода на FPGA Xilinx Spartan6 xc6slx9 показало, что он может быть использован для быстрой организации вычислений при реализации таблиц на блоках памяти BRAM. Моделирование показало, что предложенный подход позволяет ускорить вычисления в два раза по сравнению с вычислениями в двоичной системе счисления, что может быть использовано для создания аппаратных ускорителей тензорных вычислений на практике. Интересным направлением дальнейших исследований, на наш взгляд, является разработка методов оптимизации расходования памяти при реализации табличных вычислений в СОК, что может способствовать снижению ресурсных затрат при их реализации.

About the authors

N. I Chervyakov

North-Caucasus Federal University

Email: ljahov@mail.ru
Stavropol, Russian Federation

P. A Lyakhov

North-Caucasus Federal University

Email: ljahov@mail.ru
Stavropol, Russian Federation

A. S Ionisyan

North-Caucasus Federal University

Email: ljahov@mail.ru
Stavropol, Russian Federation

A. R Orazaev

North-Caucasus Federal University

Email: ljahov@mail.ru
Stavropol, Russian Federation

References

Supplementary files