РЕАЛИЗАЦИЯ АЛГОРИТМА ОБУЧЕНИЯ САМООРГАНИЗУЮЩИХСЯ КАРТ КОХОНЕНА НА ГРАФИЧЕСКИХ ПРОЦЕССОРАХ

Чанкин Антон Александрович

ведущий специалист по информационным технологиям, ООО «ЭПП «Пойма», г. Москва

E-mail: chankin.anton@gmail.com

В настоящее время нейросетевые технологии являются популярным инструментом при проведении научных исследованиях. С их помощью производится обработка результатов экспериментов, распознавание изображений, нейросетевые методы data-mining, позволяют находить закономерности в больших объемах данных.

Одной из моделей подобных сетей являются самоорганизующиеся карты Кохонена. Наиболее успешно с их помощью решаются задачи кластеризации массивов данных и построения контекстных карт признаков [5].

Принцип работы самоорганизующихся карт Кохонена в некотором смысле повторяет один из способов обработки информации головным мозгом – модель отображения признаков. Такие сенсорные входы, как нервные окончания зрения, слуха, тактильной системы топологически упорядоченно отображаются на соответствующие области коры головного мозга. Модель Кохонена не концентрируется на нейробиологических особенностях и является более общей в том смысле, что осуществляет отображение многомерного входного пространства на двумерное (реже одномерное) выходное пространство, т. е. проводит сжатие данных.

Рисунок 1. Модель работы самоорганизующихся карт.

Модель самоорганизующихся карт (Рис. 1) принадлежит к классу нейронных сетей с обучением без учителя. В этом алгоритме не существует примеров, по которым проводится обучение, присутствует лишь некая мера качества, согласно которой настраиваются параметры сети.

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

Самоорганизующиеся карты реализуют правило конкурентного обучения – нейрон, наиболее «близкий» к входящему вектору, назначается победителем и переходит в активное состояние. Победитель определяет топологическую окрестность, в которой производится корректировка соответствующих возбуждаемых нейронов. Таким образом, происходит упорядочивание нейронов в виде значимой системы координат [8].

Классический алгоритм обучения самоорганизующихся карт [5] выглядит следующим образом:

1.  Инициализация. Вначале случайными значениями инициализируются исходные вектора синаптических весов   где s – размерность входящего вектора.

2.  Подвыборка. Выбор вектора  из входного пространства с определенной вероятностью. Вектор представляет собой возбуждение, которое применяется к решетке нейронов.

3.  Поиск максимального подобия. Производится поиск наиболее подходящего (победившего) нейрона с(x), используя критерий минимума Евклидова расстояния

4. Коррекция. Корректировка весов нейронов, входящих в окрестность h(d,t) вектора-победителя, производится по следующей формуле (для j-го веса i-го нейрона)

где  – коэффициент скорости обучения, зависящий от времени. Он принимает значения в области от 0 до 1. Значение α должно уменьшаться со временем, однако нет определенного закона, по которому должно происходить это уменьшение. В нашем случае коэффициент скорости обучения рассчитывался как:

где i – номер итерации, t – общее количество итерации обучаюшего алгоритма.

В качестве функции окрестности нами использовалась гауссовская функция окрестности,

где d – расстояние на координатной сетке между текущим нейроном и нейроном-победителем,

 σ₀- константа,

  где n – максимальное количество итераций.

5. Продолжение. Происходит возврат к шагу 2, вычисления продолжаются до тех пор, пока в карте признаков не перестанут происходить заметные изменения.

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

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

Возможные способы параллелизации.

Согласно Нордстрёму [9] существует 5 методов параллелизации фазы обучения ИНС. В равной степени это относится и к модели саморганизующихся карт, однако эффективность применения того или иного метода для СОК может значительно отличаться. Приведем список этих методов с кратким описанием принципов параллелизации.

1.  Параллелизация фазы обучения

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

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

2.  Параллелизация обучающей выборки

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

3.  Параллелизация на уровне слоя.

В таких моделях ИНС как сеть с обратным распространением ошибки и неокогнитрон, обучающие вектора проходят через сеть по принципу конвейера. Таким образом, несколько обучающих векторов могут находиться в сети одновременно.

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

4.  Параллелизация на уровне нейрона

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

5.  Параллелизация на уровне весов.

Вычисления в пределах нейрона также могут быть разделены между несколькими процессорами. Это очень мелкомодульный параллелизм и он в первую очередь представлен в аппаратных реализациях.

Технологии реализации параллельных алгоритмов ИНС.

Почти все вышеописанные методы параллелизации успешно используются для ускорения работы алгоритмов нейронных сетей. Для реализаций используются как постоянно наращивающие мощность высокопроизводительные суперкомпьютеры, так и нейрокомпьютеры, функционирующие на отличных от фон-неймановского вычислительных принципах.

Суперкомпьютеры являются наиболее распространенным решением для реализаций различных моделей нейронных сетей. С различной эффективностью для высокопроизводительных вычислений используются массивно-параллельные машины, вычислительные кластеры с производительностью в несколько тысяч Gflops [10].

Реализации на нейрочипах являются куда менее распространенным решением, в первую очередь за счет своей высокой стоимости. В настоящее время на рынке отсутствуют массово доступные нейрочипы, большинство их разработок производится на заказ, для выполнения специфических задач, что делает их малодоступными для рядового пользователя [1]. 

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

Однако существует технология, позволяющая осуществлять высокопроизводительные вычисления с помощью средств, находящихся практически в каждом современном ПК. Речь идет о технологии GPGPU, в перевод c англ. General-purpose graphics processing units — графические процессоры общего назначения. Первоначально графические процессоры использовались только для обработки компьютерной графики, и для того, чтобы осуществить сторонние вычисления, были необходимы специфические знания и навыки программирования трехмерной графики. 

Технология CUDA является программно-аппаратной архитектурой, позволяющей программисту писать полнофункциональные приложения с использованием дополнительной библиотеки CUDA C, без дополнительного изучения принципов и алгоритмов обработки компьютерной графики.

К настоящему времени продано более 128 миллионов графических процессоров, поддерживающих технологию CUDA. NVIDIA предлагает широкий выбор устройств, от мощных графических процессоров Tesla, стоимостью в несколько тысяч долларов и сконструированных специально для высокопроизводительных вычислений, до дискретных видеокарт ION для портативных компьютеров, на которых также возможно достичь небольшого прироста скорости по сравнению с вычислениями на CPU [2]. Для наших целей была выбрана оптимальная по соотношению цены и производительности видеокарта GeForce GTX 680 с памятью 2048 MB, 256-bit GDDR5 [3].

Основные принципы технологии CUDA

Архитектура CUDA спроектирована в виде масштабируемого массива многопоточных мультипроцессоров (Streaming Multiprocessors). Используемая в нашем эксперименте видеокарта GTX680 содержит 1526 CUDA ядер, объединенных в 8 мультипроцессоров. Определяющий принцип архитектуры CUDA состоит в том, что GPU (обозначаемое как device) выступает в роли массивно-параллельного сопроцессора к CPU (используется термин host). При этом последовательный код выполняется на CPU, а для параллельных вычислений соответствующий код выполняется на GPU N раз на N параллельных нитях. Функции, выполняемые параллельно на всех нитях GPU носят название ядер (kernel), и представляют собой расширенные функции языка C.  

В основе идеи библиотеки расширений языка C для CUDA лежат три абстрактных понятия – иерархия групп нитей, разделение памяти и барьерная синхронизация. API интерфейс CUDA скрывает все сложности создания нитей и генерирует легковесные нити для обработки на ядрах CUDA, всего лишь основываясь на вызове функции. Однако общее количество нитей и их загруженность в мультипроцессорах целиком зависят от вызова API. Здесь кроется основная сложность, требующая значительных усилий, чтобы использовать GPU на пике возможностей и достичь наилучшей производительности [12].

CPU взаимодействует с GPU для создания, выполнения и прекращения работы ядра. В нашем случае GPU и CPU работают в блокирующем режим. В этом режиме CPU запускает одно ядро и ждет до полного окончания его выполнения.

Верхний уровень организации соответствует всем нитям, выполняющим данное ядро. Для его обозначения используется термин «сетка» - grid. Сетка представляет собой одномерный или двумерный массив блоков. Каждый блок – это одномерный, двумерный или трехмерный массив нитей, в блоке их может содержаться до 512. Все блоки, образующие сетку, имеют одинаковую размерность (максимальная поддерживаемая размерность для GTX680 составляет 1024 x 1024 x 64). Каждый блок в сетке имеет свой адрес, индекс блока в сети, также как и нить имеет свой индекс внутри блока.

Когда мультипроцессор получает один или несколько блоков нитей для выполнения (в GTX680 на каждом мультипроцессоре может выполняться одновременно до 2048 нитей), он разделяет их на группы по 32 нити - warp’ы, каждый warp с помощью warp-планировщика получает свою очередь на выполнение. При этом только нити в пределах одного warp’а выполняются физически одновременно. Нити из разных warp’ов могут находиться на разных стадиях выполнения программы, что нужно учитывать при написании программы, вызываемые нити не должны зависеть от результатов работы друг друга.  

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

Каждая нить имеет собственный, доступный только ей небольшой участок памяти, называемый локальной памятью (local memory). Также все нити внутри одного блока могут сообщаться друг с другом с помощью так называемой разделяемой памяти (shared memory) с низкой задержкой.  Более объемная общая память (global memory) имеет высокую задержку и является доступной из CPU, таким образом, являясь единственным каналом сообщения между CPU и GPU.

Кроме того, существует ещё два дополнительных вида памяти, открытых только для чтения и доступных для всех нитей. Это так называемые константная и текстурная память, оптимизированные для некоторых специфических форматов данных.

Механизм взаимодействия нитей друг с другом, барьерная синхронизация в CUDA реализован при помощи встроенной функции _syncthreads() [7]. Ей обозначаются точки синхронизации в ядре. Она запрещает нитям выполнение дальнейших команд до тех пор, пока все нити не войдут в эту функцию.

Описание реализации параллельного алгоритма.

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

1.  Расчет расстояния между входящим вектором и нейронами сети;

2.  Расчет расстояния на сетке между нейроном-победителем и остальными нейронами сети, для определения области корректировки;

3.  Корректировка отдельных весов нейронов, входящих в окрестность.

На блок-схеме алгоритма на рисунке 2 можно увидеть, как такое разделение отображается в архитектуре программы как принцип организации ядер CUDA.

Рисунок 2. Блок-схема алгоритма.

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

Работа ядер fv_distance_kernel, xy_distance_kernel и nodes_update_kernel осуществляется по единому принципу. Каждой нити выделяется элемент нейронной сети, или, в случае ядра fv_distance_kernel, отдельные веса нейронов. Затем по заданной формуле на каждой нити вычисляется результат для выделенного элемента, полученное значение записывается в соответствующий массив данных для последующей обработки.

Этап корректировки весов является потенциально параллелизуемым на уровне весов, поскольку для каждого веса корректировка рассчитывается независимо. Теоретически это должно ускорить работу алгоритма. Однако в нашем случае каждой нити выделяется не вес, а весь нейрон целиком, с последовательной коррекцией весов каждого нейрона на одной нити. Это сделано во избежание дивергенции потока управления — простоя большого количества нитей, созданных перед условным выбором [4].

Четвертое ядро bmu_search_kernel отличается от других ядер тем, что оно представляет собой не параллелизацию подэтапа алгоритма, а отдельную функцию.

Редукция массива реализуется следующим образом – для массива , проводится попарное сравнение элементов , для . Если  , i-ый заменяется элементом . Далее процедура повторяется для подмассива . В случае, если n нечетно, элемент  добавляется в . Этот процесс повторяется до тех пор, пока подмассив не уменьшится до единичной длины.

На рисунке 3 представлена схема работы алгоритма редукции массива

Рисунок 3. Схематичное изображение редукции массива.

Тестовые результаты.

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

В экспериментах использовался ПК со следующими техническими характеристиками: процессор Intel Core i7 920 (4 ядра по 2.67GHz), на операционной системе Windows 7 64-bit. В качестве графического процессора использовалась вышеописанная видеокарта NVIDIA GeForce GTX 680. Компиляция параллельной и последовательной версий осуществлялась в Microsoft Visual Studio 2010, для параллельной версии использовалась надстройка NVIDIA Parallel Nsight v.2.1 и программный пакет NVIDIA CUDA Toolkit v4.2.

Для проведения тестов были выбраны три конфигурации сети: размерности карт составляли 25х25, 50х50 и 100х100 нейронов. Тестовый массив входных обучающих векторов для каждой карты состоял из 60000 векторов размерности 100. Обучающая выборка генерировалась случайным образом по нормальному распределению со значениями в интервале от нуля до единицы не включительно. Для каждой конфигурации производилось 50 последовательных запусков CPU и CUDA алгоритмов. Результаты тестов отображены на рисунке 4.

Рисунок 4. Результаты работы алгоритмов на различных конфигурациях сети.

Средний прирост скорости обучения относительно последовательной версии алгоритма для карты размера 25х25 нейронов составил 12.39 раз, для карты размера 50х50 нейронов 24.27 раз, а для карты размера 100х100 нейронов 55.78 раз.

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

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

Технология CUDA применима не только для модели самоорганизующихся карт, но и для других ИНС, в которых имеются потенциально параллелизуемые структуры [6]. Таким образом, при условии, что будет соблюдена технология работы с памятью, архитектура CUDA является перспективным методом распараллеливания времязатратных алгоритмов работы нейронных сетей. 

Кроме того, поскольку основной код алгоритма написан на языке C с добавлением некоторых функций из библиотеки CUDA. Это позволяет адаптировать его для работы с недавно анонсированной компанией Microsoft технологией параллельного программирования C++ AMP [11], что даёт новые возможности для дальнейших исследований в этой области.

Список литературы:

1.Калитин Д. Использование технологии CUDA фирмы NVIDIA для САПР нейронных сетей // Электронное научное издание «Устойчивое инновационное развитие: проектирование и управление», том 4, 1999. URL: www.rypravlenie.ru (Дата обращения 21.05.2012)

2.Официальный сайт компании NVIDIA. Раздел Продукты с поддержкой NVIDIA CUDA// http://www.nvidia.ru/object/cuda_gpus_ru.html (Дата обращения 21.05.2012)

3.Официальный сайт компании NVIDIA. Технические характеристики графической карты NVIDIA GeForce GTX 680 // http://www.nvidia.ru/object/geforce-gtx-680-ru.html#pdpContent=2

4.Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров: Пер. с англ. — М.: ДМК Пресс, 2011.

5.Хайкин С. Нейронные сети: полный курс, 2-е издание. : Пер. с англ. — М.: Издательский дом «Вильямс», 2008

6.Чанкин А.А. Реализация алгоритма прогнозирования временных рядов при помощи интервальной нейронной сети. Сб. трудов XIV Всероссийской научно- технической конференции «Новые информационные технологии». 2011 – М.: МГУПИ. 2011, С. 64-73.

7.CUDA API Reference Manual v.4.2 // http://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_Toolkit_Reference_Manual.pdf

8.Kohonen T. “The self-organizing map”, Proceedings of the Institute of Electrical and Electronics, 1990, vol. 78, p. 1464 — 1480

9.Nordstrom T. Designing parallel computers for self-organizing maps. Forth Swedish Workshop on Computer System Architecture, Linkoping, 1992. [Труды конференции]

10.D. Valencia, A. Plaza, P. Martinez and J. Plaza. Parallel Processing of High-Dimensional Remote Sensing Images Using Cluster Computer Architectures // International Journal of Computers and their Applications, USA, NC, Cary, March 2007,  vol. 14, no. 1, pp. 23 — 34

11.Анонс о выходе С++ AMP в официальном блоге компании Microsoft // http://blogs.msdn.com/b/vcblog/archive/2011/06/15/introducing-amp.aspx

12.Руководство по программированию на CUDA C вер. 4.1 // CUDA C Programming Guide v.4.1. // http://developer.download.nvidia.com/compute/DevZone/docs/html/C/doc/CUDA_C_Programming_Guide.pdf