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

• Карпушин, Андрей Александрович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Карпушин, Андрей Александрович

Введение.

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

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

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

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

Публикации.

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

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

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

Глава 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е: • на основе библиотеки ОоепСЬ:

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

Список литературы диссертационного исследования кандидат технических наук Карпушин, Андрей Александрович, 2011 год

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.