Оценка эффективности реализации алгоритма метода Монте-Карло на современных графических ускорителях

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Ларкин Евгений Васильевич, д-р техн. наук, проф., зав. кафедрой, elar-kin@, mail. ru, Россия, Тула, Тульский государственный университет
SYSTEMS OF SOFTWARE CONTROL AND DIAGNOSTICS A.N. Ivutin, E.V. Larkin
The systems of software control and diagnostics are considered. The classifications of software errors are offered. The symptoms and aftereffects of errors are showed.
Key words: failures, software, reliability, running time.
Ivutin Alexey Nicolaevich, candidate of technical science, docent, alex-ey. ivutin@, gmail. com, Russia, Tula, Tula State University,
Larkin Evgeniy Vasilevich, doctor of technical science, professor, manager of department, elarkin@, mail. ru, Russia, Tula, Tula State University
УДК 004. 042
ОЦЕНКА ЭФФЕКТИВНОСТИ РЕАЛИЗАЦИИ АЛГОРИТМА МЕТОДА МОНТЕ-КАРЛО НА СОВРЕМЕННЫХ ГРАФИЧЕСКИХ
УСКОРИТЕЛЯХ
А. Н. Ивутин, И.А. Страхов
Произведена экспериментальная проверка зависимости времени выполнения алгоритма Монте-Карло для различных конфигураций вычислительного ядра графического процессора. Проанализировано влияние потоковых и скалярных процессоров на время выполнения алгоритма.
Ключевые слова: GPGPU, GPU, CUDA, NVidia, метод Монте-Карло, вычислительное ядро, GRID, конфигурация.
Увеличение производительности вычислительной техники в последние десятилетия осуществлялось в основном за счет повышения тактовой частоты центрального процессора. Данный способ всегда был и остается наиболее надежным из всех возможных. Однако ввиду технических ограничений при изготовлении интегральных схем уже невозможно рассчитывать на рост частоты работы процессора. Применение многопроцессорных систем также не получило широкого распространения, так как требует сложных и дорогостоящих многопроцессорных материнских плат. Поэтому эволюция вычислительной техники пошла по другому пути — развитию идеи многоядерности процессоров. Принцип увеличения
производительности процессора за счёт нескольких ядер заключается в разбиении выполнения потоков (различных задач). Можно сказать, что практически каждый процесс, запущенный в системе, имеет несколько потоков. Однако одним из самых важных недостатков является внушительное энергопотребление, а значит, сильное тепловыделение и высокие температуры чипа при работе под нагрузкой. Также существенным минусом является высокая себестоимость процессора, возникшая из-за увеличения количества «железа». Поэтому процесс наращивания числа ядер замедлился. Графические процессоры (GPU) шагнули далеко вперед в плане наращивания вычислительной мощности и общего количества вычислителей. Однако такая высокая плотность достигается за счет максимального упрощения дизайна самого чипа [1]. На рис. 1 приведены примеры CPU-и GPU-архитектур.
Рис. 1. Пример CPU-и GPU-архитектур
General-purpose graphics processing units (GPGPU) — техника использования графического процессора видеокарты для вычислений общего назначения, которые обычно проводит центральный процессор. Вычисление на GPU не предполагает переноса нагрузки с центрального процессора на графический. Как правило, центральный процессор при этом остается загруженным, а использование графического процессора наряду с центральным позволяет повысить производительность, т. е. сократить время выполнения задачи. Причем сам GPU здесь выступает в роли своеобразного сопроцессора для CPU, но ни в коем случае не заменяет его полностью.
CUDA — программно-аппаратная архитектура, разработанная компанией Nvidia для видеокарт серии GeForce 8000 и старше. Платформа обеспечивает набор расширений для языков С/С++^оЛгап, позволяющих выражать как параллелизм данных, так и параллелизм задач на уровне мелких и крупных структурных единиц. Существует поддержка фреймворка OpenCL [2].
CUDA использует большое число отдельных нитей для вычислений. Часто каждому вычисляемому элементу соответствует одна нить. Все они группируются в иерархию — grid/block/thread (рис. 2).
Верхний уровень — grid, — соответствует ядру, которое является функцией вычисления данных в GPU, и объединяет все нити, выполняющие данное ядро. Grid представляет собой одномерный или двухмерный массив блоков (block). Каждый блок (block) является одно-, двух-, трехмерным массивом нитей (threads). При этом каждый блок представляет собой полностью независимый набор взаимодействующих между собой в пределах одного блока нитей.
Grid
ЫосЦ0,0) Ыоск (0,1) Ыоск (0,п-1)
Ыоск (1,0) Ыоск (1,1) Ыоск (1,п-1)

Ыоек (т-1,0), Ыаск (т-1,1) — - Ыоск (т-1, п-1)

Block
thread (0,0) threna (0,l-l)

dtreadfk-1,0) dtreadfk-1,1−1)
Рис. 2. Иерархия нитей в CUDA
Для контроля исполнения работы нитей GPU используется так называемый warp. С программной точки зрения он является пулом нитей, в пределах которого происходит параллельная работа потоков, запрошенных при вызове ядра. Размер warp^ для всех GPU составляет 32, т. е. параллельно исполняются только 32 нити. Одновременно на GPU можно запустить несколько warp^.
Метод Монте-Карло — общее название группы численных методов, основанных на получении большого числа реализаций стохастического (случайного) процесса, который формируется таким образом, чтобы его вероятностные характеристики совпадали с аналогичными величинами решаемой задачи. В частности, метод Монте-Карло используется при
приближенном определении площади фигуры [3]. Его суть заключается в том, что вокруг выпуклой фигуры F, площадь которой требуется вычислить, описывается другая фигура R, площадь которой S® легко рассчитывается по формулам геометрии. Обычно в качестве R выбирается прямоугольник, причем его стороны не обязательно должны касаться вершин исследуемой фигуры F. Дальше случайным образом генерируются точки, попадающие внутрь фигуры R, причем они должны равномерно покрывать всю фигуру R. Если точка попала внутрь исследуемой фигуры F, счетчик C увеличивается на 1. В итоге, если из N точек M = C попало внутрь F, то площадь исследуемой фигуры рассчитается через площадь S® следующим образом:
S (F) = S® * M / N. (1)
Актуальность работы заключается в определении оптимальной конфигурации вычислительного ядра для заданного кода (рис. 3), что в дальнейшем позволит создать динамическую модель изменения параметров графического процессора для более эффективного использования ресурсов системы.
_global_ void MonteKarlo2(f loat* kl^ float* k2, float* total count Poi nt, float* dx, float* maxx, float* maxY, float* courrtPoint){
Рис. 3. Код вычислительного ядра
В ходе работы была произведена оценка времени нахождения площади треугольника методом Монте-Карло на GPU при различном сочетании блоков в сетке и нитей в блоке. Итерации проводились с количеством
3 10
точек от 10 до 10 с возрастанием по геометрической прогрессии (q = 10). С целью уменьшения погрешности полученных данных вычисление для каждой конфигурации проводилось 4 раза [4]. Расчеты осуществлялись на графическом процессоре GeForce GT 240M с характеристиками, приведенными в табл. 1. Количество блоков изменялось от 32 до 32 768 по геометрической прогрессии (q = 2). Данная особенность связана
с методом используемого алгоритма решения задачи Монте-Карло -редукцией массива положительных попаданий точек в фигуру, позволяющей более эффективно использовать ресурсы GPU [2]. Количество нитей в блоке варьировалось в интервале от 32 до 512 с изменением количества по геометрической прогрессии со знаменателем 2.
Таблица 1
Характеристики графического процессора
Количество Частота Частота Частота Объем Интерфейс Количество
потоковых ядра процессора, памяти, памяти, памяти скалярных
процессоров (МГц) МГц МГц Гб (bit) процессоров
48 174 1210 790 1 128 8
В результате анализа полученных в результате эксперимента данных была составлена динамика изменения времени и выбраны наиболее эффективные настройки вычислительного ядра (табл. 2).
Таблица 2
Оптимальные конфигурации вычислителя
Количество точек 103 104 105 106 107 108 109 10
Оптимальная конфигурация (блоковни-тей) 6432 3232 3232 3232 3264 3264 32256 512128
Время вычисления, мс 125 16 23 24 35 140 990,5 8311
На рис. 4 представлена зависимость времени вычисления площади для всех конфигураций.
Для малого количества точек время вычисления велико для каждой из конфигураций. Это связано с невозможностью полностью заполнить все ресурсы графического процессора, что, в свою очередь, приводит к «холостой» работе отдельных скалярных процессоров. При увеличении количества точек «включаются» потоковые возможности мультипроцессоров, что приводит к росту скорости вычисления. Однако для конфигураций с малым числом нитей в блоке с увеличением числа точек время вычисления начинает линейно увеличиваться. Это связано с необходимостью скалярного процессора переключаться множество раз между нитями блока. Заметим, что на время вычисления также влияет количество блоков в сетке. Данный параметр «отодвигает» начало линейного роста времени и уменьшает наклон прямой. Однако для большого количества блоков появляется необходимость переключаться уже не скалярным процессорам, а потоковым. Данная особенность сказывается на начальном времени вычисления.
В конечном итоге при количестве блоков больше 2048 зависимость сводится к прямой, что при увеличении количества точек позволяет получить существенный выигрыш в скорости вычисления.
Время вычисления, мс

-128512




^?00-

: -----

-'-

00 10 000 1000М ЮООООО «олт"С1""ч,» 10 000 000 100. 0 1 000 000 000 10 000,
Рис. 4. Зависимость времени вычисления от конфигурации
Следующим шагом исследования станет нахождения математической зависимости оптимальных параметров блоков и нитей в зависимости от количества генерируемых точек.
Список литературы
1. Суперкомпьютер из видеокарты: задействуем возможности GPU для ускорения софта // Режим доступа: http: //xakep. ru/56 966, свободный. Загл. с экрана.
2. Сандерс Дж., Кэндрот Э. Технология CUDA в примерах: введение в программирование графических процессоров: пер. с англ. А. А. Слинкина / науч. ред. А. В. Боресков. М.: ДМК Пресс, 2011. 232 с.: ил.
3. Metropolis N., Ulam S. The Monte Carlo Method. J. Amer. statistical assoc. 1949. № 247. P. 335 — 341.
4. Шишкин И. Ф. Метрология, стандартизация и управление качеством: учеб. для вузов / под ред. Н. С. Соломенко. М.: Изд-во стандартов, 1990. 342 с.
Ивутин Алексей Николаевич, канд. техн. наук, доц., alexey. ivutin@, gmail. com, Россия, Тула, Тульский государственный университет,
Страхов Илья Андреевич, магистрант, iastrahov@gmail. com, Россия, Тула, Тульский государственный университет
EVALUATION OF THE ALGORITHM THE MONTE CARLO ON PRESENT GRAPHICS
ACCELERATORS
A.N. Ivutin, I.A. Strahov
The experimental verification of the dependence the performance Monte Carlo algorithm for different configurations of the computational kernel graphics processor. Analyzed the influence offlow and scalar processors for the duration the algorithm.
Key words: GPGPU, GPU, CUDA, NVidia, method Monte-Carlo, calculation core, GRID, configuration.
Ivutin Alexey Nicolaevich, candidate of technical science, docent, alexey. ivutin@, gmail. com, Russia, Tula, Tula State University,
Strahov Ilia Andreevich, undergraduate, iastrahov@, gmail. com, Russia, Tula, Tula State University
УДК 004. 04
ДИНАМИЧЕСКАЯ УНИФИКАЦИЯ КАК СПОСОБ ПОВЫШЕНИЯ
КАЧЕСТВА И ЭФФЕКТИВНОСТИ СОПРОВОЖДЕНИЯ ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ В КОРПОРАТИВНОЙ СЕТИ ТРАНСПОРТНО-ПРОИЗВОДСТВЕННОЙ СИСТЕМЫ
В.Н. Изотов
Рассмотрена постановка задачи динамической унификации программного обеспечения. Приведена технологическая схема решения двухуровневой задачи унификации. Сформулирована математическая модель двухуровневой динамической задачи унификации. Разработан алгоритм решения двухуровневой динамической задачи унификации.
Ключевые слова: программное обеспечение, технология унификации, динамическая унификация.
В транспортно-производственных системах (ТПС) [1] необходимость решения динамической задачи унификации как системного, так и прикладного программного обеспечения (ПО) корпоративной компьютерной сети ТПС обусловлено периодическим появлением новых прикладных задач и технологий их решения. В свою очередь, связанное с этим увеличение числа разнотипных программных средств и систем приводит к снижению качества функционирования ПО в целом (надёжности, быстродействия), а также к снижению эффективности его сопровождения в составе ТПС (увеличению суммарных затрат на внедрение, сопровождение, эксплуатацию).

ПоказатьСвернуть
Заполнить форму текущей работой