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

На правах рукописи

Карпушин Андрей Александрович

II

РАЗРАБОТКА ЭФФЕКТИВНЫХ АЛГОРИТМОВ ДЛЯ АНАЛИЗА ДАННЫХ С ИСПОЛЬЗОВАНИЕМ ГРАФИЧЕСКОГО ПРОЦЕССОРА

05.13.17. - Теоретические основы информатики

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 2 ЯН В 1Ш

"0500731О

Воронеж - 2011

005007310

Работа выполнена в Воронежском государственном университете.

Научный руководитель: доктор физико-математических наук,

профессор Запрягаев Сергей Александрович

Официальные оппоненты:

доктор технических наук,

профессор Сирота Александр Анатольевич

доктор физико-математических наук, профессор Горбунов Вячеслав Алексеевич

Ведущая организация:

К

Воронежский государственный технический университет

2012 г. в Л?" часов на заседании диссер-

Защита состоится

тационного совета Д 212.038/24 при Воронежском государственном университете по адресу: 394006, Воронеж, Университетская пл., д. 1, ВГУ, ауд. 226.

С диссертацией можно ознакомиться в библиотеке Воронежского государственного университета.

Автореферат разослан

«Л»

2011 г.

Ученый секретарь '^^лС Чеботарев А.С.

диссертационного совета "

Д 212.038.24

Общая характеристика работы

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

В последние годы помимо роста числа ядер в многоядерных процессорах появилась возможность ускорять вычисления не только на центральных, но и на графических процессорах, встроенных в видеокарты. Так как потребности трехмерной графики привели к созданию видеокарт с уникальной многоядерной архитектурой графических процессоров, естественным образом появилась возможность использовать большое число ядер графического процессора в качестве устройств, аналогичных многоядерным системам. При этом возникли специфические проблемы использования различных типов памяти, организации алгоритмов и т.п. По этой причине, разработка и реализация вычислительных алгоритмов, ориентированных на использование как центральных, так и графических процессоров, имеет ярко выраженный научный и практический интерес. Исследованиями по применению графического процессора в различных областях, таких как видеообработка, вычислительная химия, обработка сигналов, занимались Colic A., Stone J.E., Hongsheng L., Clemente С., Anderson J.A. и др. Однако, комбинированное использование графического и центрального процессоров в вычислительных задачах исследовано не в полной мере. Комплексное использование всего набора процессоров вычислительного устройства позволяет надеяться на экономию вычислительных ресурсов и возможность использования недорогостоящего оборудования даже для ресурсоемких задач. Совокупность проблем, связанных с применением как чисто графических процессоров, так и сочетаний графических процессоров с центральными, в различных вычислительных задачах -предмет настоящего исследования.

1 Zhirnov, V. V., Cavin, R. К., Hutchby, J. A., Bourianoff, G. I. Limits to binary logic switch scaling - a gedanken model / V. V. Zhirnov, R. K. Cavin, J. A. Hutchby, G. I. Bourianoff // Proceedings of the lEEE.-2003.-vol. 91.-no. 11. [Электронный ресурс]. http://news.cnet.com/2100-1008-5112061 .html

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

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

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

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

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

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

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

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

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

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

В работе разработаны следующие новые алгоритмы:

1. Алгоритмы визуализации пространственно определенной функции на основе выборки данных по заданной плоскости, сфере, цилиндру.

2. Алгоритм одновременного построения группы эквипотенциальных поверхностей.

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

4. Алгоритм Фурье-преобразования пространственно определенной функции.

5. Алгоритм расчета полного и дифференциального сечения рассеяния электронов на произвольном молекулярном кластере.

6. Алгоритм обучения нейронной сети на графическом процессоре.

На основе совокупности алгоритмов, включая алгоритмы 1-5, разработанных автором, спроектирована и реализована база данных физико-химических свойств молекулярных объектов.

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

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

Диссертационное исследование выполнено в рамках Федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009 - 2013 годы, государственный контракт № П846 от 25.05.2010, и НИР №01200956642 аналитической вневедомственной целевой программы развития научного потенциала высшей школы 2009-2014 по теме «Разработка новых методов обработки, хранения, передачи и защиты информации в информационно-коммуникационных системах».

По результатам работы получены свидетельства об официальной регистрации программ: «Система расширенных квантово-механических вычислений на базе результатов расчета программы ОАШЗГАМОЗ», «Система оптимизации квантово-механических вычислений на графическом процессоре», «Программная библиотека для работы с искусственными нейронными сетями на графическом процессоре».

Соответствие диссертации паспорту научной специальности. Работа соответствует специальности 05.13.17 - «Теоретические основы информатики» (технические науки), а именно:

пункту 5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений»;

пункту 7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания»;

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

Структура и объем диссертации. Основное содержание работы изложено в четырех главах. Работа содержит 138 страницы машинописного текста, 50 рисунков, две таблицы. Список цитируемой литературы включает 73 наименования.

Публикации. По результатам проведенных исследований и практических разработок опубликовано 18 работ. Из них: 5 в журналах списка ВАК, 10 в трудах международных конференций, 3 свидетельства о государственной регистрации программы для ЭВМ.

Апробация работы. Результаты исследований докладывались на: международной конференции «Математика. Компьютер. Образование.» (XVI-я -г. Пущино, 19-24 января 2009г., XVII-я - г. Дубна, 25-30 января 2010г., XVIII-я - г. Пущино, 24-29 января 2011г.), международной научно-методической конференции «Информатика: проблемы, методология, технологии.» (IX-й - г. Воронеж, 12-13 февраля 2009г., Х-я - г. Воронеж, 11-12 февраля 2010г., XI-й - г. Воронеж, 10-11 февраля 2011г.), 41st EGAS Conference (Gdansk, 8-11 July 2009), 10th European Conference on Atoms, Molecules and Photons (Salamanca, 4-9 July 2010).

Основные положения, выносимые на защиту.

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

2. Алгоритм построения группы эквипотенциальных поверхностей.

3. Алгоритмы кратного численного интегрирования на графическом процессоре.

4. Алгоритм обучения нейронной сети прямого распространения на графическом процессоре.

5. Программный комплекс и база данных для анализа сложных молекулярных структур.

Содержание диссертации

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

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

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

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

Как правило, расчеты молекулярных кластеров выполняются на сложных программных комплексах, таких как Gaussian2, GAMESS-US3 и т.п. Важным набором выходных данных таких комплексов являются значения ряда скалярных функций, таких как плотность заряда, скалярный потенциал, молекулярные орбитали и т.п., которые представляются в виде массива значений в пространственных точках (x,y,z), < х< хт!1Х , утш < у< утш , znua <z< zmax, образующих «куб» данных. Использование этих данных позволяет проводить расчеты многих стандартных задач квантовой теории - теории рассеяния, теории взаимодействия молекул с внешним полем, процессов фотоионизации и т.д., однако реализация этих расчетов не включена в набор процедур известных оболочек.

В настоящей главе разработаны алгоритмы визуализации данных «куба» путем построения трехмерного объекта на основе выборки данных по одному из трех типов поверхности: плоскости, сфере, цилиндру. Трехмерный объект, отображающий проекцию функции z) на выбранную поверх-

ность аппроксимируется сеткой из треугольников4.

В общем случае, построение сетки из треугольников осуществляется следующим образом. Базовая поверхность (плоскость, сфера, цилиндр) на основе ее аналитического описания аппроксимируется сеткой из треугольников. Вершины треугольников полученной поверхности «вытягиваются» вдоль нормали пропорционально значению функции «куба» /. Предложенная в настоящей работе схема построения сетки из треугольников в случае выборки данных по плоскости представлена на рис. 1.

2Frisch, M. J., Trucks, G. W. et. al. Gaussian 03, Revision A.l / M. J. Frisch, G. W. Trucks.-2003.

3 GAMESS-US Homepage. [Электронный ресурс]. http://www.rnsg.chem.iastate.cjn/gamess/

4 Gouraud, H. Continuous Shading of Curved Surfaces / H. Gouraud // IEEE Transactions on Computers.-1971.-vol. 20.-no. 6.-pp. 623-629.

Рис. 1. Вычисление координат вершины для построения сетки из треугольников при выборке данных из «куба» на основе плоскости. р0 - радиус-вектор «начальной» точки плоскости, Л - нормаль плоскости, и и V - произвольные ортогональные с П векторы, I, j - счетчики вершины сетки из треугольников, р - радиус-вектор искомой точки трехмерного объекта.

Для анализа функции г), в ряде практических случаев, имеет

важное значение построение эквипотенциальных поверхностей вида Г(х,у,г) = сп 1 = \,...,п.

В настоящей работе разработан алгоритм построения двух эквипотенциальных поверхностей разного по знаку значения. Визуализация эквипотенциальных поверхностей осуществляется на основе эмпирической модели освещения Фонга5 при помощи пиксельной программы графического процессора6. Модель Фонга определяет интенсивность отраженного света как суперпозицию фонового освещения, рассеянного света и зеркально отраженного света по формуле:

т

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

5 Phong, В. Т. Illumination for computer generated pictures / В. Т. Phong // Commun. ACM.-1975.-vol. 18.-no. 6.-pp. 311-317.

6 Pixel shader - Wikipedia. [Электронный ресурс]. htlp://en.wikipedia.org/wiki/Pixel shader

в котором будет виден блик; Ьт - единичный вектор направления из точки

поверхности на источник света; N - нормаль в данной точке поверхности;

т ~ единичный вектор идеально отраженного луча света в данной точке

поверхности; V - единичный вектор направления из точки поверхности до наблюдателя.

Расположение векторов Ьт, N, и V представлено на рис.2.

Рис. 2. Расположение векторов, используемых в модели отражения Фонга.

В результате итоговое изображение, полученное на основе модели Фонга (формула (I)), определяется, как результат суперпозиций интенсивно-стеи, рассмотренных выше: фонового, диффузного и зеркального освещения.

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

4т2 е2"2" 1 2

а = -IT-/ J-41/P(r)exp(ig ■ г)drf sinвё<рёв, (2)

" о о Ч 1

где m - масса электрона, е - его заряд, h - постоянная Планка, q = k-f,

кик- волновые^векторы электрона в начальном и конечном состояниях соответственно, р(г) - плотность заряда молекулярного кластера.

Как видно из формулы (2), центральным ее элементом является вычисление пространственного Фурье-преобразования.

Расчет полного сечения упругого рассеяния по формуле (2) для разных величин начальной энергии на центральном процессоре занимает несколько часов. Разработанный в настоящей работе алгоритм расчета сечения упругого рассеяния на графическом процессоре уменьшает общее время вычислений в 30-40 раз.

Структура алгоритма определяется следующей последовательностью операций:

1. Для заданной начальной энергии Е электрона определяется список

7 Давыдов, А. С. Квантовая механика, 2nd ed. / Л. С. Давыдов.-М.: БХВ-Петербург,

всевозможных векторов д, определяемых двумя углами в и ф. Углы в и ф определяют положение конечного вектора электрона^' относительно начального вектора к . Формирование списка векторов ц осуществляется

полностью на графическом процессоре. _

2 Каждый из вычисленных векторов Ц участвует в Фурье-

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

3 Определяется вклад зарядов ядер молекулярного кластера в значение сечения упругого рассеяния. Вычисления выполняются параллельно для

каждого атома на графическом процессоре.

4 Центральный процессор ожидает получения результатов вычислении на этапах 2 и 3, осуществляет операцию редукции над полученными массивами данных и вычисляет значение сечения упругого рассеяния.

5 Полученные значения сечения упругого рассеяния для списка векторов Я интегрируются по углу ф для определения зависимости сечения

упругого рассеяния от угла рассеяния в (рис. 3).

6. Полученный результат интегрируется по углу в для нахождения

ш»ттачины полного сечения рассеяния.

Рис. 3. Зависимость дифференциального сечения рассеяния от угла рассеяния в

Центральным элементом расчета сечения рассеяния является п.2 алгоритма, который сводится к задаче численного кратного интегрирования.

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

ситуации.

Установлено, что если требуется максимально быстро осуществить интегрирование большого массива данных, следует использовать алгоритм, ис-

пользующий как ресурсы графического, так и центрального процессоров -алгоритм 1 (рис. 4).

Рис. 4. Зависимость времени выполнения алгоритма 1 от количества элементов исходного массива. Общее время выполнения для ЛГ=106 равно 6.085мс, время работы графического процессора 1.653мс, время работы центрального процессора 4.432мс.

Если же требуется осуществлять интегрирование в «фоновом» режиме, позволяя пользователю взаимодействовать с другими приложениями, эффективнее использовать алгоритм численного интегрирования исключительно на графическом процессоре, не использующий ресурсы центрального процессора - алгоритм 3 (рис. 5).

Рис. 5. Зависимость времени выполнения алгоритма 3 от количества элементов исходного

массива. Общее время выполнения для Л" =106 равно 13.815мс, время работы графического процессора 12.202мс, время работы центрального процессора 1.613мс. Центральный процессор используется в меньшей степени по сравнения с алгоритмом 1.

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

Алгоритм 1 (йРи)

Алгоритм 3 ^РЦ)

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

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

. модуль построения графиков - обеспечивает интерактивное отображение графиков инфракрасного (ИК) спектра и спектра ядерного магнитного

резонанса (ЯМР) молекулярных объектов.

Для проведения научных исследований с совокупностью данных сложных молекулярных объектов в работе была спроектирована, реализована и интегрирована совместно с основной программной оболочкой база данных молекулярных объектов, содержащая их физико-химические свойства. К основным физико-химическим свойствам, содержащимся в базе данных, относятся: структура, дипольные моменты молекулярного кластера, поляризуемость, ИК и ЯМР спектры, молекулярные орбитали.

Для удобства использования база данных размещена в сети Интернет. При разработке базы данных использовались современные интернет технологии а именно: платформа Google Арр Engine, веб-интерфейс Django, система аутентификации пользователей Google Friend Connect. Схема взаимодеиствия базы данных с программной оболочкой представлена на рис. 6.

еС-интерфейс

Google Арр Engine

О

■фЛк Лети '——' „3 hkuyr* мторм«

: OpanSo aal

ш-

Модуль овбэть I

«ЬД .

огр^мь.»

□

Модул» орем и я Медгп»".~ —

чнсганмыя расчетов rp^tw-cceiUatciotl'b. FW«"") (OpeiCL Pfthor)

Рис. 6. Схема взаимодействия пользователей с программной оболочкой и базой данных молекулярных объектов.

В четвертой главе описано применение графического процессора при вычислении и обучении искусственных нейронных сетей прямого распространения. Рассмотрены различные методы обучения нейронных сетей пря-

мого распространения: метод наискорейшего спуска, метод сопряженных градиентов, эвристические методы обучения С>шскргор8 и ИРКОР9.

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

Проведен сравнительный анализ скорости обучения нейронной сети по алгоритму, разработанному автором, с популярными библиотеками для работы с неиронными сетями. В сравнении библиотекой для работы с нейронными сетями РАШ , обучение нейронной сети по алгоритму, разработанному

в настоящей работе, выполняется значительно быстрее для нейронных сетей большого размера (рис. 7).

Зависимость среднего времени модификации веса сети от общего количества в

— Настоящая работа •- FANN

100ш0 15°?0<> 200000 250000 ЗООМО 35ÖOOO—адоооо Количество весов сети

Рис. 7. Зависимость среднего времени модификации одного веса нейронной сети от общего количества весов.

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

lQS»r8Fahl!ПaП, Faster-learning variations on back-propagation: an empirical study // 1 m Connections Models Summer School.- San Mateo, CA, 1988 38-51

, • ' BraUn> H" A Direet AdaPtive Mcthod for Faster Backpropagation

Learning: The RPROP algorithm // ICNN 93, Piscataway, NJ 1993 586-591 "

hun^J^S^^"" №Ural NetW°rk '[Элект Р°нный Р-^Ь

" Запрягаев, С. А., Сорокин, А. И. Распознавание рукописных символов на основе анализа дескрипторов функций длины хорды / С. А. Запрягаев, А. И. Сорокин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии,2009,vol. 2,рр. 49-58.

длины хорды и их эллиптические дескрипторы Фурье. На основе теоремы Колмогорова12 сделан вывод об оптимальной архитектуре нейронной сети -нейронная сеть содержит два скрытых слоя в силу дискретного характера соотнесения признаков символа определенному классу символа.

В ходе тестирования нейронной сети были получены следующие результаты. Количество обучающих выборок, на которых обучалась нейронная сеть, составило 157 элементов, которые распределялись в 33 класса, по одному символу русского языка в каждом классе. По прошествии 40000 эпох обучения уровень относительной погрешности обучения составил 1,5%. Однако, погрешность распознавания рукописных символов, не участвующих в процессе обучения составила 6%. ,

Полученные данные по нескольким символам тестовой выборки, а

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

Таблица 1. Результаты распознавания символов рукописного текста.

Символ

Результат распознавания

Класс

Вес

0.73

0.76

0.94

0.58

0.89

Класс

Вес

0.46

0.22

0.29

0.46

0.15

Класс

Щ

Ф

Вес

0.42

0.18

0.20

0.43

0.15

Основные результаты работы.

1 Разработаны эффективные алгоритмы визуализации пространственно определенной функции на заданной поверхности: плоскости, сфере,

цилиндру.

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

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

4. Создан пакет программных оболочек для анализа структуры и расчета

" Колмогоров, А. Н. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного и сложения. / А Н. Колмогоров II Доклад Академии HayK.-1957.-vol. 114,по. 5.-рр. 953-956.

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

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

Основные результаты диссертации опубликованы в следующих работах

Публикации в изданиях, рекомендованных ВАК РФ

1. Влияние растворителя на электрические и спектральные характеристики эидоэд-ральных металлофуллеренов ШС60 и Na2C60 / E.B. Бутырская, С.А. Запрягаев, А А Карпушин // Вестник Воронежского государственного университета. Сер. Химия Биология. Фармация .— Воронеж, 2010 .— № 2. - С. 7-11 .— ISSN 1609-0675 — ISSN 0234-5439,—0,3 п.л.

2. Применение графического процессора в ресурсоемких вычислениях на базе библиотеки OPENCL / С.А. Запрягаев, A.A. Карпушин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии .— Воронеж 2010 .— № 2. - С. 79-87 ISSN 0234-5439 .— ISSN 1995-5499 .- 0,6 п.л.

3. Сканирование полной энергии, зарядов на атомах по Малликену и дипольных моментов систем С60Н и С60Н2 / A.A. Карпушин, С.А. Запрягаев, Е.В. Бутырская // Вестник Воронежского государственного университета. Сер.: Химия. Биология. Фармация — Воронеж, 2011.— № 1. - С. 27-31 .— ISSN 0234-5439 .— ISSN 1609-0675 .- 0,3 п.л.

4. Применение графического процессора в задаче многократного численного интегрирования на основе обобщенной формулы Симпсона / С.А. Запрягаев, A.A. Карпушин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии .— Воронеж, 2011 .— № 1. - С 150-156 — ISSN 199S S4QQ _

ISSN 0234-5439.— 0,4 п.л. ' •

5. Вычисление и обучение искусственных нейронных сетей прямого распространения на графическом процессоре / С.А. Запрягаев, A.A. Карпушин // Вестник Воронежского государственного университета. Сер. Системный анализ и информационные технологии .— Воронеж, 2011 .— № 1. - С. 157-164 .— ISSN 1995-5499 .— ISSN 0234-5439 — 0 5

п.л.

Статьи и материалы конференций

6. Система расширенных квантово-механических вычислений на базе результатов расчета программы GAUSSIAN03 / С.А. Запрягаев, А.А. Карпушин // Математика. Компьютер. Образование : тез., Пущино, 19-24 янв. 2009 г. — М.-Ижевск, 2009 .— Вып. 16, ч. 1. -С. 105.— 0,1 п.л.

7. Система визуализации результатов расчета программы GAUSSIAN03 / С.А. Запрягаев, А.А. Карпушин // Информатика : проблемы, методология, технологии : материалы 9-ой международ, науч.-метод. конф., Воронеж, 12-13 февр. 2009 г. — Вопонеж 2009 — Т 1.-С. 309-312 .— 0,3 п.л.

8. Above Threshold Two Photon Transition in H-like Ions / С.А. Запрягаев, А. Карпушин // 41th EGAS Conference, Gdansk, 8-11 July 2009 : Abstracts .— Gdansk, 2009 P. 103.

9. Elastic Electron Scattering by Fullerenes and Carbon Tubes / С.А. Запрягаев, А Карпушин //41th EGAS Conference, Gdansk, 8-11 July 2009: Abstracts .— Gdansk, 2009.— P. 104.

10. Сечение упругого рассеяния электронов на фуллеренах и углеродных нанотрубках / С.А. Запрягаев, А.А. Карпушин // Математика. Компьютер. Образование : 17 Междунар.

конф. : тез., Дубна, 25-30 янв. 2010 г. — М.-Ижевск, 2010 .— Вып. 17. - С. 117-118 .— 0,1

п.л.

11. Использование OpenCL дая параллельных вычислений на графическом процессоре / С А Запрягаев A.A. Карпушин // Информатика : проблемы, методология, технологии : материалы X междунар. науч.-метод. конф., 11-12 февр. 2010 г., г. Воронеж Воронеж,

2010,— Т. 1,- С. 272-279 .— 0,5 п.л.

12 Ab Initio Quantum Calculation of C60-nH / E.B. Бутырская, A.A. Карпушин, C.A. Запрягаев // ECAMPIO : 10th European Conf. on Atoms, Molecules and Photons : Scientific Program .— Salamanca (Spain), 2010 .- 1 p. - (http://www.ecampl0.com).- 0,1 п.л. — Биб-

™3rPElastic Electron Scattering on C60-nH / A.A. Карпушин, C.A. Запрягаев // ECAMPIO : 10th European Conf. on Atoms, Molecules and Photons : Scientific Program .- Salamanca (Spain) 2010 — 1 p. — (http://www.ecampl0.com).— 0,1 п.л. — Библиогр.: с.

14 Программная библиотека для работы с искусственными нейронными сетями на графическом процессоре : Св-во о государственной регистрации программы для ЭВМ № 2011611468 / С.А. Запрягаев, A.A. Карпушин .- М., 2011 .- 40 с. - (Заявка № 2010618286; Заявлено 27.12.10; Зарегистрировано 14.02.11).— 2,5 п.л.

15 Система расширенных квантово-механических вьиислений на базе результатов расчета программы GAUSSIAN03 : Свидетельство № 2009611277 / С.А. Запрягаев, A.A. Карпушин .— 3 с. — (Заявка № 2009610020, 11.01.09. Зарегистрировано в Реестре программ

для ЭВМ 2.03.09)0,1 п.л.

16. Система оптимизации квантово-механических вычислений на графическом процессоре • Св-во о государственной регистрации программы для ЭВМ № 2011612979 / С.А. Запрягаев, A.A. Карпушин .- М„ 2011 40 с. - (Заявка № 2010618287; Заявлено 27.12.10; Зарегистрировано 14.04.11).— 2,5 п.л.

17. Алгоритм численного интегрирования на графическом процессоре с использованием OpenCl на основе обобщения квадратурной формулы Симпсона / С.А. Запрягаев, A.A. Карпушин // Информатика : проблемы, методология, технологии : материалы XI междунар. науч.-метод. конф., 10-И февр. 2011 г., г. Воронеж .— Воронеж, 2011 .— Т. 1. - С. 306-309,—0,3 п.л.

18 Вычисление искусственных нейронных сетей прямого распространения на графическом процессоре / С.А. Запрягаев, A.A. Карпушин II Информатика : проблемы, методология, технологии : материалы XI междунар. науч.-метод. конф., 10-11 февр. 2011 г., г. Воронеж .— Воронеж, 2011 .—Т. 1. - С. 309-311 .— 0,3 п.л.

Подписано в печать 06.12.11. Формат 60*84 '/,<,. Усл. пен. л. 0,93. Тираж 100 экз. Заказ 1547.

Отпечатано с готового оригинал-макета 5 типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Введение.

Актуальность исследования.

Цели и задачи диссертации.

Научная новизна и значимость работы.

Практическая ценность работы.

Публикации.

Личный вклад автора.

Основные положения, выносимые на защиту.

Классификация вычислительных систем.

Глава 1. Технологии программирования графического процессора.

1.1. Программирование графического процессора на основе вершинных и пиксельных программ.

1.2. Программирование графического процессора на основе библиотеки CUD А.

1.3. Программирование графического процессора на основе библиотеки DirectCompute.

1.4. Программирование графического процессора на основе библиотеки OpenCL.

1.5. Архитектура OpenCL.

Выводы.

Глава 2. Алгоритмы для анализа структуры и свойств сложных молекулярных кластеров с использованием графического процессора.

2.1. Алгоритмы визуализации сложных кластерных структур и их физико-химических характеристик.:.

2.1.1. Алгоритм построения сетки из треугольников на основе выборки данных по плоскости.

2.1.2. Алгоритм построения сетки из треугольников на основе выборки данных по сфере.

2.1.3. Алгоритм построения сетки из треугольников на основе выборки данных по цилиндру.

2.2. Алгоритм выборки данных из «куба» на основе отрезка.

2.3. Алгоритм построения группы эквипотенциальных поверхностей.

2.4. Алгоритм расчета сечения рассеяния частиц на молекулярном кластере.

2.5. Оценка эффективности алгоритма Фурье-преобразования на графическом процессоре.

2.6. Алгоритм кратного численного интегрирования на графическом процессоре.

Результаты.'.

Выводы.

Глава 3. База данных и программная оболочка.

3.1. Программная оболочка для анализа структуры и свойств сложных молекулярных кластеров.

3.2. Проектирование и разработка базы данных молекулярных объектов.

3.3. Интерфейс программной оболочки.

3.4. Администрирование базы данных.

Результаты.

Выводы.

Глава 4. Разработка библиотеки для работы с нейронными сетями на графическом процессоре.

4.1. Нейронные сети прямого распространения.

4.2. Алгоритм обучения нейронных сетей прямого распространения на графическом процессоре.;.

4.3. Анализ эффективности обучения нейронной сети с использованием графического процессора.

4.4. Распознавание рукописных символов с использованием нейронной сети.

4.4.1. Подбор архитектуры сети.

4.4.2. Алгоритм обучения нейронной сети.

4.4.3. Тестирование нейронной сети.

Выводы.

Актуальность исследования.

Со времени изобретения интегральных схем рост производительность вычислительных устройств приближенно описывается эмпирическим «законом Мура» [1]. Согласно наблюдению Гордона Мура в 1965 году, число транзисторов на кристалле удваивалось через каждые 24 месяца. На протяжении нескольких десятков лет закон Мура соблюдался благодаря совершенствованию технологического процесса производства интегральных схем и уменьшению размеров транзисторов на кристалле. На сегодняшний день совершенствование технологического процесса вплотную приблизилось к ограничениям, накладываемым фундаментальными физическими законами. По предварительным оценкам [2], к 2018 году дальнейшее уменьшение размера транзистора на кристалле до нескольких нанометров приведет к возникновению эффекта туннелирования и других квантово-механических эффектов, что принципиально повлияет как на технологии изготовления микросхем, так и на системы программирования.

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

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

Согласно правилу Амдала [3], ускорение выполнения программы за счет распараллеливания ее инструкций на множестве вычислительных устройств ограничено временем, необходимым для выполнения ее последовательных инструкций, и определяется следующей формулой:

-(1Л) а +Р где а — доля от общего объема вычислений, выполняемая последовательно и недоступная для распараллеливания, р — количество вычислительных узлов,

Зр{а) ~ коэффициент ускорения, который может быть получен при распараллеливании вычислений на р устройствах. Как следует из формулы (1.1), при больших значениях р, коэффициент ускорения в большей степени определяется значением коэффициента а (рис. 1). р

Рис. 1. Зависимость 5 от параметров ОС и р.

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

Цели и задачи диссертации.

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

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

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

Научная новизна и значимость работы.

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

В работе разработаны,следующие новые алгоритмы:

1. Алгоритм визуализации.пространственно определенной функции на основе построения сетки из треугольников по заданной плоскости.

2. Алгоритм-визуализации пространственно определенной функции'на основе построения сетки из треугольников по заданной сфере.

3. Алгоритм визуализации пространственно определенной функции на основе построения сетки из треугольников по заданному цилиндру.

4. Алгоритм построения двух эквипотенциальных поверхностей различного по знаку значения.

5. Алгоритм кратного численного интегрирования на графическом процессоре.

6. Алгоритм Фурье-преобразования пространственно определенной функции на графическом процессоре.

7. Алгоритм расчета полного и дифференциального сечения рассеяния электронов на произвольном молекулярном кластере с использованием графического процессора:

8. Алгоритм обучения нейронной сети на графическом процессоре.

На основе совокупности разработанных и существующих алгоритмов создана база данных физико-химических свойств молекулярных объектов.

Для разработанных алгоритмов приведены теоретические обоснования: Разработанные алгоритмы1 объединены в пакет программ для анализа структуры и свойств сложных молекулярных кластеров, нашедшем, свое применение в научных исследованиях, проводимых в ВГУ.

Все алгоритмы разработаны? с возможностью реализации на графическом и центральном процессорах.

Практическая ценность работы.

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

Диссертационные исследования; выполнены в рамках Федеральной целевой программы "Научные и научно-педагогические кадры инновационной России" на 2009 - 2013 годы, государственный контракт №

П846 от 25.05.2010, и НИР №01200956642 аналитической вневедомственной 1 целевой программе о развитии- научного потенциала высшей школы 2009

2014 по теме «Разработка новых методов обработки, хранения, передачи и защиты информации в информационно-коммуникационныхсистемах».

Получены свидетельства об официальной регистрации программ: «Система расширенных квантово-механических вычислений на базе результатов расчета программы; САи881АМ)3>> [4], «Система оптимизации; квантово-механических вычислений на графическом процессоре» [5], «Программная библиотека для работы с искусственными нейронными сетями па графическом процессоре» [6].

Публикации.

По результатам проведенных исследований и практических разработок опубликовано 18 работ. Из них: 5 в журналах списка ВАК, 10 в трудах международных конференций, 3 свидетельства о государственной регистрации программы для ЭВМ.

Личный вклад автора.

Все; основные результаты, выносимые на защиту, получены автором самостоятельно.

Основные положения, выносимые на защиту.

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

2. Алгоритм построения группы эквипотенциальных поверхностей.

3. Алгоритмы кратного численного интегрирования на графическом процессоре. , V

4. Алгоритм обучения нейронной сети прямого распространения на графическом процессоре.

5. Программный комплекс и база данных для анализа сложных молекулярных структур.

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

Классификация вычислительных систем.

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

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

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

• Многопроцессорные системы — вычислительные узлы являются самостоятельными процессорами и работают под управлением одной операционной системы. Операционная система распределяет задачи между разными процессорами, гарантируя, что« одна и та же задача не будет одновременно выполняться более чем одним процессором. Все процессоры системы имеют доступ к общей оперативной памяти. Такой тип архитектуры применялся до недавнего времени в основном в серверах и суперкомпьютерах. Примером ' использования многопроцессорных систем на сегодняшний день является персональный компьютер с несколькими видеокартами, так называемая технология SLI (Scan Line Interleave). В этом случае изображение разбивается на несколько частей, количество которых соответствует количеству видеокарт в связке. Каждая часть изображения обрабатывается полностью одной видеокартой.

Кластеры — группа компьютеров, объединенная' высокоскоростными каналами связи и представляющая- с точки зрения пользователя единый ресурс. Компьютеры в рамках кластера могут в свою очередь использовать многоядерные ■ процессоры для выполнения вычислений.

Грид-системы — объединение огромного числа слабосвязанных компьютеров для одновременного выполнения большого количества крупных и масштабных задач. В отличие от кластеров,' грид-системы, могут использовать медленный канал связи. Ерид-система является географически, распределенной инфраструктурой, объединяющей множество, ресурсов разных типов (процессоры, долговременная и* оперативная1 память, хранилища и базы данных, каналы связи и т.п.), доступ к которым пользователь может получить из любой точки, независимо от места их расположения. Грид-системьг получили широкое распространение за счет распространения сети Интернет, а также технологий пакетной передачи данных по оптоволоконным каналам. Примером современного использования грид-система может служить система по

I ' обработке данных, получаемых с Большого адронного коллайдера [7].

Каждая из перечисленных систем служит для решения определенного класса задач. Многоядерные процессоры и многопроцессорные системы используются для ускорения решения повседневных задач у широких, масс пользователей, а также задач, которые должны быть решены за фиксированное время. Кластерные системы в. силу своей дороговизны обычно применяются' в» крупных НИИ, ВУЗах и- других научных организациях. Грид-системы служат для* решения, масштабных задач, как например расшифровка генома, человека, поиск внеземных цивилизаций (проект SETT [8]) и т.п. Перечисленные выше системы^ обеспечивают параллельность вычислительных процессов.

При этоМ'* по» типу обеспечения параллельности* вычислений обычно выделяют следующие уровни параллелизма:

• Параллелизм» nai уровне битов. Суть параллелизма, на уровне битов заключается в том, что расширение размера машинного слова, которым оперирует процессор, ведет к уменьшению действий над операндами. Например, при сложении двух 64-битных чисел на 32-битном процессоре осуществляется в два1 действия: сложения младших 32 бит, а затем сложения' старших 32 бит. На> 64-битном.процессоре эта операция будет выполнена1 в одно действие.

• Параллелизм на уровне инструкций. Этот тип параллелизма использует особенности исполнения команд процессором. Различные по типу команды в современных процессорах могут выполняться параллельно. Например, за счет рациональной группировки командt чтения данных из области« памяти, выполнения арифметической инструкции,, записи в регистр процессора.

• Параллелизм ^ на уровне данных. Основная идея подхода, основанного на параллелизме данных, заключается в том, что одна операция выполняется сразу над всеми элементами массива данных. Такой подход, помимо классических алгоритмов, реализуется в разрабатываемых квантовых алгоритмах.

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

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

Параллелизм на уровне данных частично находится под контролем программиста. Современный центральный процессор имеет ряд технологий, позволяющих использовать параллелизм« на уровне данных на уровне выполнения машинных команд: Технологии; ММХ (Multimedia Extensions), SSE (Streaming SMD Extensions), SSE2, SSE3, SSE4 используют дополнительные инструкции центрального процессора для параллельного выполнения простых арифметических операций над массивами данных.

Процесс перевода программного кода от последовательной обработки данных к их параллельной обработке (векторизация), осуществляется обычно за счет «разворачивания циклов» в программе [9]. Циклы, тело которых состоит из арифметических операций над одним элементом массива, переписываются таким образом, чтобы в теле цикла обрабатывалось несколько последовательных элементов массива. Современные компиляторы в большинстве своем могут выполнять автоматическую векторизацию с применением перечисленных выше технологий.

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

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

К процессорам нового поколения относятся проектируемые процессоры по технологии Intel Larabee [10] и AMD Fusion [11]. Суть технологии заключается в объединении центрального многозадачного универсального процессора с графическим параллельным многоядерным процессором на одном кристалле.

Широкая потребность реализации высококачественной, интерактивной трехмерной графики привела в последние годы к существенному технологическому развитию графических процессоров (GPU — Grannies Processing Unit), являющихся неотъемлемой частью любого персонального компьютера. Пои этом графический процессор приобрел качество высокопроизводительного устройства. основанного на применении параллельных технологий. Современный графический процессор предоставляет возможность осуществлять программирование обработки исходных данных на уровне прямых команд графического процессора.

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

ИЯП ТСЯЖЛГ.Ш тпементпм ПЛНИЫХ — С 1ЧЫСПКЧ1М отпгииенир.м чис.пл арифметических операций к числу операций с памятью.

Технологическая модернизация графических процессоров привела к тому, что вычислительная мощность GPU стала значительно опережать вычислительную мощность центрального процессора (CPU — Central Processins Unit). Для примера, современная видеокарта NVIDIA GTX 280 содержит 240 ядер с пиковой производительность 933 ГигаФлопс. что обеспечивает выполнение миллиардов операций в секунду с вещественными

14 числами. В то время как современный центральный процессор Intel Core 2 Ouad 09550 имеет пиковую производительность только в 45.28 Гигафлопс. что почти в двадцать раз меньше производительности GPU.

Сравнение изменения производительности графического процессора по годам по отношению к производительности центрального процессора приведено на рис. 2.

Рис. 2. Сравнение производительности графического и нейтрального процессоров.

Реализация систем программирования GPU привела к его использованию не только для графических приложений, но и для решения широкого класса иных задач. Такое применение графического процессора получило название GPGPU (General Purpose computations on Graphics Processing Unit). Пои этом типичными областями применения GPGPU стали такие направления 1Т технологий как: видеообоаботка П21. вычислительная химия Г131. визуализация в медицине Г14 и обоаботка сигналов Г151 и др. Отдельные вычислительные задачи в области моделирования молекулярной динамики, перенесенные на GPU. позволили достигнуть вычислительной мощности, соответствующей кластеру из 30 CPU П61.

Использование графического процессора нашло свое применение и в задачах реализации сложных нейронных сетей. Так. в работе [17] продемонстрировано, что время обучения нейронной сети с использованием GPU сократилось в 150 раз. Еще одним перспективным направлением использования графического процессора является его применение в системах управления базами данных [18. 19. 20. 21]. Графический процессор в этом случае может выполнять вспомогательные задачи, такие как сортировка данных при добавлении новой записи в базу данных Г18]. выборка записей [20.21]. сжатие данных для их быстрой передачи Г221.

Помимо этого, графические процессоры активно используются и в высокопроизводительных научных исследованиях. Самый высокопроизводительный кластер на сегодняшний день установлен в Китае, имеет пиковую производительность в 2.5 петафлопс и оснащен 14336 центральными процессорами и 7168 графическими процессорами. Для сравнения, чтобы получить такую же производительность без использования графических процессоров, понадобилось бы оснастить кластер более чем 50000 центральных процессоров [231.

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

I лава I. вехнологни программирования графического процессора.

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

Архитектура графического процессора в сравнении с центральным процессором приведена на шс. 3.

Графический процессор

Мультиядро7\ /*Мультиядро"п\ ^

Локальная память ~ 16КВ

П I п 1

Г» Т р> Р п р г'|. р г

I " * » I =! г 1

Локальная I память ~ 16КВ \\ | I

Центральный процессор г л

Яя.ро1 • г л

Ядро л

- 32кБ

-У

1И кеш ~ 32КВ

12 кеш - 8МВ Ф

Оперативная память ~ 4вВ

Рис. 3. Дпхнтектупа гпа(Ьического пооиессопа.

Графический процессор состоит из большого числа SIMD (Single Instruction. Multiple Data) ядер (также называемых thread). каждое из которых выполняет одну и ту же микропрограмму над разными данными. В терминологии программирования графического процессора такую микропрограмму называют ядерной функцией (kernel function"). На рис. 3 S1MD ядра имеют обозначение Р,.

Графический процессор иерархически объединяет несколько S1MD ядер в так называемые рабочие группы (workgroups), между которыми осуществляется распределение данных. Рабочие группы могут обмениваться дополнительными данными посредством локальной памяти внутри группы и позволяют использовать синхронизирующие примитивы для синхронизации между отдельными SIMD ядрами. В то же время, графический процессор не предоставляет средств для синхронизации работы отдельных рабочих групп между собой. На рис. 3 рабочие группы обозначены как «Мультиядро i».

Графический процессор также имеет иерархическую структуру памяти, с которой может работать разработчик. На самом высоком уровне иерархии каждая из рабочих групп может оперировать с общей видеопамятью (рис. 3). также называемой глобальной памятью, которая имеет высокую пропускную способность и высокую задержку при обращении к ней. Внутри рабочей группы также доступна локальная память (рис. 3). общая для SIMD ядер, входящих в мультиядро. Как правило, объем локальной памяти в современных графических процессорах не превышает 16 Кбайт. Каждое SIMD ядро имеет также свою собственную память небольшого объема, используемую для хранения промежуточных результатов в процессе выполнения kernel функции (рис. 3, заштрихованная область внутри Р.).

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

Для примера, видеокарта NVIDIA GTX 280 имеет 1GB видеопамяти, пропускную способность 141 GB/s и задержку на доступ в 400-600 тактов. Если отдельные S1MD ядра внутри рабочей группы обращаются к видеопамяти последовательно, эти обращения группируются в одно фактическое обращение. Правильно используя эту особенность можно в разы сократить количество фактических обращений к видеопамяти, что может существенно повысить производительность алгоритма и повысить общую пропускную способность данных для алгоритма [241.

Например, в случае простого последовательного доступа к памяти, когда SIMD ядро Р; обращается к ячейке памяти с номером /, несколько обращений к памяти группируются в одно фактическое обращение (рис. 4а). Другими словами, чтение из видеопамяти осуществляется блоками определенного размера (для современных видеокарт 128 байтУ и если несколько ядер Р; обращаются к памяти в пределах блока, никаких дополнительных обращений к видеопамяти не осуществляется. Если доступ к памяти осуществляется с некоторым смещением (рис. 46). то количество Фактических обращений к памяти незначительно возрастает за счет того, что последние SIMD ядра обращаются к памяти соседнего блока. Если же доступ к памяти осуществляется не последовательно, то количество фактических обращений к памяти многократно возрастает.

Ячейки памяти

Ячейки пямятм

ТТТТТ гтг " иши III!

1™Ш / / / / / / / 1111111 виид

81 МО ядра а)

81М0 ядра б^

Рис. 4. Схема доступа к видеопамяти: а) операции доступа без смешения группируются в одно Фактическое обпашение к памяти: 61 операции доступа со смешением группируются в несколько фактических обращений тс памяти.

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

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

Существуют следующие методы и технологии программирования графического процессора: на основе вершинных и пиксельных программ: ® на основе библиотеки СиОА: ® на основе библиотеки 01гес1:Сотри1е: • на основе библиотеки ОоепСЬ:

Ниже приведено краткое описание данных методов.

1. Moore. G. Е. Cramming more components onto integrated circuits / G. E. Moore-2006,

2. Amdahl. G. Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities / G. Amdahl.-1967.-pp. 483-485.

3. Карпушин. А. А. Запрягаев. С. А. Система оптимизации квантово-механических вычислений на графическом процессоре : Свидетельство № 2011612979 / А. А. Карпушин. С. А. Запрягаев.-2011.

4. Карпушин. А. А. Запрягаев. С. А. Система оптимизации квантово-механических вычислений на графическом процессоре : Свидетельство № 2011612979 / А. А. Карпушин. С. А. Запрягаев.-2011.

5. Карпушин. А. А. Запрягаев. С. А. Программная библиотека для работы с искусственными нейронными сетями на графическом процессоре. Свидетельство № 2011611468 / А. А. Карпушин. С. А. Запрягаев.-2010.

6. Worldwide LHC Computing Grid. Электронный ресурс. http://lcg.web.cern.ch/LCG/

7. SETI(a)Home. Электронный ресурс., http://setiathome.berkelev.edu/info.php

8. Samuel. L. Saman. A. Exploiting superword level parallelism with multimedia instruction sets / L. Samuel. A. Saman // SIGPLAN Not.-2000.-vol. 35.-no. 5.-pp. 145-156.

9. AMD Fusion Familv official website. Электронный pecvpc., http:// fusion.amd.com/

10. Colic. A. Kalva. H. Furht. B. Exploring NV1DIA-CUDA for video coding // Proceedings of the first annual ACM SIGMM conference on Multimedia systems.- New York. NY. USA. 2010.

11. Anderson. J. A. Lorenz. С. D. Travesset. A. General purpose molecular dynamics simulations fully implemented on graphics processing units / J. A. Anderson. C. D. Lorenz. A. Travesset // J. Comput. Phvs.-2008.-vol. 227.-no. 10.-pp. 5342-5359.

12. Dolenko. A. Persiantsev. S. Multifold Acceleration of Neural NetworkComputations Using GPU // Proceedings of the 19th International Conference on Artificial Neural Networks: Part I.- Limassol. Cvprus. 2009.373-380.

13. Manocha. Govindaraiu. N. K. Lloyd. В. Wang. W. Lin. M. Dinesh GPUTeraSort: High Performance Graphics Coprocessor Sorting for Large Database Management //Proc. of ACM SIGMOD. 2006. 325-336.

14. Manocha. Govindaraiu. N. K. Lloyd. В. Wang. W. Lin. M. Dinesh Fast Computation of Database Operations Using Graphics Processors // Proc. of ACM SIGMOD. 2004. 215-226.

15. Bingsheng. H. Ke. Y. Rui. F. Mian. L. Naga. G. Oiong. L. Pedro. S. Relational query coprocessing on graphics processors / H. Bingsheng. Y. Ke. F. Rui. L. Mian. G. Naga. L. Oiong. S. Pedro.-2009.-vol. 34.-no. 4.-pp. 21:1« 21:39.

16. Bingsheng. H". Ke. Y. Rui. F. Mian. L. Naga. G. Oiong. L. Pedro. S. Relational joins on graphics processors // Proceedings of the 2008 ACM SIGMOD international conference on Management of data.- Vancouver. Canada. 2008. 511-524.

17. Fang. W. He. В. Luo. O. Database compression on graphics processors / W. Fang. В. He. O. Luo // Proc. VLDB Endow.-2010.-vol. З.-no. l-2.-pp. 670680.

18. NVIDIA Tesla GPUs Power World's Fastest Supercomputer. Электронный ресурс.http://pressroom.nvidia.com/easvir/customrel.do?easvirid=A0D622CE9F579F 09&version=live&prid=678988&releaseisp:=release 157

19. NVIDIA. (2009) NVIDIA OpenCL Best Practices Guide. Электронный ресурс!.http://www.nvidia.eom/content/cudazone/CUDABrowser/downioads/papers/NVmiAOpenCLBestPracticesGuide.pdf

20. OpenGL Overview. Электронный ресурс!. htto://www.khronos.orç/ppencl/

21. DirectX SDK (June 2010Y ГЭлектронный ресурс. http://msdn.microsoft.com/librarv/ee663275(VS.85>).aspx

22. Phong. В. T. Illumination for computer generated pictures / В. T. Phong // Commun. ACM.-1975.-vol. 18.-no. 6.-pp. 311-317.

23. Blinn. J. F. Models of light reflection for computer synthesized pictures / J. F. Blinn// SIGGRAPH Comput. Graph.-1977.-vol. ll.-no. 2.-pp. 192-198.

24. Harris. M. Fast fluid dynamics simulation on the GPU // ACM SIGGRAPH 2005 Courses.- Los Angeles. California. 2005. doi=10.1145/1198555.1198790.

25. CUDA Zone Ru. Электронный pecvpcl. http://www.nvidia.ru/obiect/cuda homenewru.html

26. Compute Shader Overview. Электронный pecvpcl. http://msdn.microsoft.com/en-us/librarv/ff476331 .aspx

27. OpenCL Overview. ГЭлектронный pecvpcl. http://www.khronos.org/opencl/

28. MOSIX Cluster and Multi-Cluster Management. ГЭлектронный ресурс. http://www.mosix.org/

29. The MOSIX Virtual OpenCL ÎVCL) Cluster Platform. Электронный ресурс., http://www.mosix.org/txtvcl.htmi

30. Python Programming Language Official Website. Электронный pecvpcl. http://pvthon.org/

31. NumPv Official Website. Электронный pecvpcl. http : //numpv.orii/

32. SciPv Home Page. Электронный ресурс., http://www.scipv.org/

33. PvOpenCL I Andreas Klockner's web page. Электронный pecvpcl. http://mathema.tician.de/software/pvopencl

34. CLvther dev documentation. ГЭлектронный ресурс. http://clvther.sourceforge.net/

35. Theano vO.3.1 documentation. Электронный ресурс. http://deeplearning.net/software/theano/

36. Frisch. M. J. Trucks. Ст. W. et. al. Gaussian 03. Revision A.l / M. J. Frisch. G. w Triicks -200?

37. Lorensen. W. E. Cline. H. E. Marching cubes: A high resolution 3D surface construction algorithm / W. E. Lorensen. H. E. Cline // SIGGRAPH Comput. Graph.-1987.-vol. 21.-no. 4.-pp. 163-169.

38. Бахвалов. H. С. Жилкой. H. П. Кобельков. Г. M. Численные метольт. 4th ed. / Н. С. Бахвалов. Н. П. Жилков. Г. М. Кобельков: БИНОМ.-Москва : БИНОМ. 2006.- с. 636

39. Давыдов. А. С. Квантовая механика. 2nd ed. / А. С. Давыдов.-М: : БХВ-Петербург. 1973.

40. Запрягаев. С. А. Карпушин. А. А. Сечение упругого рассеяния электронов на фуллеренах и углеродных нанотрубках // Математика. Компьютер. Образование : 17 Междунар. конф. vol. 17.- Дубна. 2010. 117-118.

41. Самарский. А. А. Гулин. А. В. Численные методы: Учеб. пособие для вузов. / А. А. Самарский. А. В. Гулин.-М.: Наука. 1989.- с. 432

42. Sunpvo. Н. Hvesoon. К. An analytical model for a GPU architecture with memory-level and thread-level parallelism awareness / H. Sunpvo. K. Hvesoon // SIGARCH Comput. Archit. News.-2009.-vol. 37.-no. 3.-pp. 152-163.

43. NVIDIA OpenCL Programming Overview. Электронный ресурс. httD://ww\v.nvidia.com/content/cudazone/download/OpenCL/NVIDIAOpenC L ProgrammingOverview.pdf

44. OpenCL Optimization Case Study. Электронный ресурс. http://developer.amd.com/documentation/articles/Pages/OpenCL-Optimization-Case-Study-Simple-Reductions.aspx

45. Карпушин. А. А. Запрягаев. С. А. Система расширенных квантово-механических вычислений на базе результатов расчета программы GAUSSIAN03 : Свидетельство № 2009611277 / А. А. Карпушин. С. А. Запрягаев.-2009.

46. Google Friend Connect. Электронный ресурс., http ://www. google, com/friendconnect/

47. OpenSocial. Электронный ресурс. htto://www,opensocial.org/,

48. Google Add Engine. Электронный ресурс., http://code.google.com/intl/ru-RU/appengine/

49. Chang. F. Dean. J. Ghemawat. S. Hsieh. W. C. A. W. Burrows. M. Chandra. T. et al. Bigtable: A Distributed Storage System for Structured Data // OSDI'06: Seventh Symposium on Operating System Design and Implementation.- Seattle. WA. 2006.

50. Diango. Электронный ресурс., http://www.djangoproiect.com/57. http://www.ison.org/. Электронный ресурс., http://www.ison.org/

51. Matplotlib vl.0.1 documentation. Электронный ресурс. http://matplotlib.sourceforge.net/

52. Maplesoft official website. Электронный ресурс. http://www.maplesoft.com/products/maple/

53. Microsoft Office 2010. Электронный ресурс., http://office.microsoft.com/ru-ru/excel/

54. Noel. L. Bernardete. R. An efficient gradient-based learning algorithm applied to neural networks with selective actuation neurons / 1Noel. R. Bernardete // Neural. Parallel Sci. Comput.-2003.-vol. 11.-no. 3.-pp. 253-272.

55. Герасименко. M. С. Вычисление искусственных нейронных сетей на вычислительных кластерах или ЛВС. / М. С. Герасименко // Вестник ВГУ. Серия «Системный анализ и информационные технологии».-2010.-по. 1

56. Noel. L. Bernardete. R. GPU implementation of the multiple "back-propagation algorithm. // 10th international conference on Intelligent data engineering and automated learning (IDEAL'09V Springer-Verlag. Berlin. Heidelberg. 2009. 449.4515

57. Осовский. С. Нейронные сети для обработки информации / С. Осовский.-М.: Финансы и статистика. 2004.- с. 344

58. NVIDIA OpenCL SDK Code Samples. Электронный ресурс!. http://developer.download.nvidia.com/compute/opencl/sdk/website/samples.ht m l#ocl MatVecMu 1

59. Fahlman. S. E. Faster-learning variations on back-propagation: an empirical studv // 1988 Connectionist Models Summer School.- San Mateo. CA. 1988. 38-51.

60. Riedmiller. M. Braun. H. A Direct Adaptive Method for Faster Backpropagation Learning: The RPROP algorithm // ICNN 93.- Piscataway. N.T. 1993. 586-591.

61. Gill. P. Murray. W. Wright. M. Practical Optimization / P. Gill. W. Murray. M. Wright: Academic Press.-New York : Academic Press. 1981.

62. Hestenes. M. R. Stiefel. E. Methods of Conjugate Gradients for Solving Linear Systems / M. R. Hestenes. E. Stiefel // Journal of Research of the National Bureau of Standards 49 (6).

63. Fast Artificial Neural Network Library. Электронный ресурс. http://leenissen.dk/fann/

64. Nixon. М. Aguado Feature Extraction by Shape Matching / M. Nixon. Aguado // Feature Extraction and Image Processing.-2002.-pp. 247-277.

65. Колмогоров. A. H. О представлении непрерывных функций нескольких переменных в виде суперпозиции непрерывных функций одного переменного и сложения. / А. Н. Колмогоров // Доклад Академии Наук.-1957,-vol. 114.-ПО. 5.-pp. 953-956.