Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Метод Монте-Карло на графических процессорах

Покупка
Артикул: 799110.01.99
Доступ онлайн
200 ₽
В корзину
В учебном пособии изложены основные идеи метода Монте-Карло, принципы распараллеливания расчетов, организации высокоскоростных параллельных вычислений методом Монте-Карло на графических процессорах NVIDIA архитектуры CUDA. Подробно проанализирован пример моделирования методом Монте-Карло диффузии нейтронов через пластину. Пособие предназначено для проведения практических занятий по программированию графических процессоров для магистрантов по направлениям подготовки 09.04.02, 14.04.02, специалистов по направлению подготовки 141401.
Метод Монте-Карло на графических процессорах : учебное пособие / К. А. Некрасов, С. И. Поташников, А. С. Боярченков, А. Я. Купряжкин [и др.]. - Екатеринбург : Изд-во Уральского ун-та, 2016. - 60 с. - ISBN 978-5-7996-1723-3. - Текст : электронный. - URL: https://znanium.com/catalog/product/1936365 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.
Министерство образования и науки Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

К. А. Некрасов, С. И. Поташников, 
А. С. Боярченков, А. Я. Купряжкин

Метод Монте-Карло 
на графических процессорах

Учебное пособие

Рекомендовано методическим советом УрФУ
для студентов, обучающихся по направлениям подготовки
14.04.02 — Ядерная физика и технологии;
09.04.02 — Информационные системы и технологии;
14.04.01 — Ядерные реакторы и материалы

Екатеринбург
Издательство Уральского университета
2016

УДК 519.245:004(075.8)
ББК 22я73+32.97я73
          М54
Авторы:
Некрасов К. А., Поташников С. И., Боярченков А. С., Купряжкин А. Я.

Рецензенты:
Институт теплофизики УрО РАН (д‑р физ.‑мат. наук, проф. В. Г. Байдаков); 
гл. науч. сотр. лаборатории математического моделирования Ин‑
ститута промышленной экологии УрО РАН д‑р физ.‑мат. наук, проф. 
А. Н. Вадаксин

М54
    Метод Монте-Карло на графических процессорах : учебное посо‑
бие / К. А. Некрасов, С. И. Поташников, А. С. Боярченков, А. Я. Купряж‑
кин. — Екатеринбург : Изд‑во Урал. ун‑та, 2016. — 60 с.

ISBN 978‑5‑7996‑1723‑3

В учебном пособии изложены основные идеи метода Монте‑Карло, принципы 
распараллеливания расчетов, организации высокоскоростных параллельных вы‑
числений методом Монте‑Карло на графических процессорах NVIDIA архитек‑
туры CUDA. Подробно проанализирован пример моделирования методом Мон‑
те‑Карло диффузии нейтронов через пластину.
Пособие предназначено для проведения практических занятий по программи‑
рованию графических процессоров для магистрантов по направлениям подготов‑
ки 09.04.02, 14.04.02, специалистов по направлению подготовки 141401.

Библиогр.: 15 назв. Рис. 15. Прил. 1.

УДК 519.245:004(075.8)
ББК 22я73+32.97я73

ISBN 978‑5‑7996‑1723‑3 
© Уральский федеральный
 
     университет, 2016

Введение

Одним из широко используемых подходов к численному модели‑
рованию физических систем является метод Монте‑Карло [1]–[2], для 
применения которого необходим анализ большого количества случай‑
ных состояний и вариантов поведения исследуемой системы, что свя‑
зано с большими объемами вычислений.
Варианты случайного поведения системы, рассматриваемые мето‑
дом Монте‑Карло, обычно генерируются и обрабатываются по одно‑
му и тому же общему алгоритму, будучи при этом независимыми друг 
от друга. Это позволяет эффективно реализовывать метод Монте‑Кар‑
ло на поточно‑параллельных вычислительных системах.
В последние годы появилась практическая возможность проведе‑
ния поточно‑параллельного физико‑математического моделирования 
на графических процессорах (GPU) — вычислительных устройствах 
параллельной архитектуры, изначально предназначенных для отобра‑
жения графики на персональных компьютерах и рабочих станциях [3].
В настоящее время ведущие производители графических процес‑
соров сами позиционируют новые GPU как универсальные системы, 
предназначенные не только для графических вычислений, но и для рас‑
четов общего назначения. В частности, компанией NVIDIA выпуска‑
ются графические процессоры архитектуры CUDA [4] и соответству‑
ющее программное обеспечение [5], которые позволяют сравнительно 
легко программировать GPU на языке, являющемся расширением 
языка C, сохраняющем синтаксис последнего и включающем все его 
основные возможности.
Современные графические процессоры имеют в своем составе 
до нескольких сотен параллельных процессоров, каждый из которых 
по вычислительной производительности сравним с центральным про‑
цессором персонального компьютера [6]– [7].

ВВедение

Опыт показывает, что при решении хорошо распараллеливаемых 
задач реальная производительность GPU оказывается не менее чем 
на два порядка выше, чем у современных центральных процессоров 
ПК. Отметим, что затраты на приобретение и эксплуатацию одного 
вычислительного комплекса с GPU примерно совпадают с затрата‑
ми на обычный персональный компьютер, тогда как кластер эквива‑
лентной производительности занимал бы намного больше места, бу‑
дучи при этом намного сложнее в эксплуатации и на порядки дороже.
В работах [8]–[10] представлены результаты применения графи‑
ческих процессоров для моделирования кристаллов диоксида урана 
методом молекулярной динамики. Использование графических про‑
цессоров позволило ускорить решение данной задачи (по сравнению 
с центральным процессором) более чем в 600 раз. Настоящее пособие 
посвящено оценке возможностей графических процессоров архитек‑
туры CUDA (Compute Unified Device Architecture [3]–[5]) на примере ме‑
тода Монте‑Карло, в частности при моделировании одномерной диф‑
фузии нейтронов через пластину.
Архитектуры графических процессоров, выпускаемых ведущими 
производителями — компаниями NVIDIA и AMD/ATI, несколько 
различны, что особенно проявляется при неграфических вычислени‑
ях. Наиболее удобной для таких вычислений мы считаем архитектуру 
CUDA [3]–[5], предлагаемую компанией NVIDIA.
В настоящем пособии будут рассмотрены особенности параллель‑
ной реализации метода Монте‑Карло для высокопроизводительных 
вычислений на графических процессорах. При этом мы ограничимся 
программированием для CUDA, так как в настоящее время эта плат‑
форма представляется наиболее эффективной, а реализованный в ней 
подход — наиболее перспективным.

1. Применение метода Монте-Карло  
для моделирования физических систем

1.1. Содержание метода Монте-Карло

1.1.1. Метод Монте-Карло на примере вычисления площадей

Простейшей иллюстрацией метода Монте‑Карло [1] является вы‑
числение площади плоской фигуры (S) по принципу, показанному 
на рис. 1.1 [2].
Фигура заключена в квадрат, по которому 
случайным образом разбрасывается большое 
количество точек. Если число точек достаточ‑
но велико, то отношение площади S к площа‑
ди квадрата L 2 будет с заданной точностью рав‑
няться отношению количества точек 
ў
N , 
попавших внутрь фигуры, к полному количе‑
ству точек N

S
L N

N
»
ў
2
.

Точность оценки площади возрастает вме‑
сте с количеством точек N. Погрешность вы‑
числений обычно пропорциональна N ‑1/2 .
Площадь фигуры можно интерпретировать как ее объем в двух‑
мерном пространстве. Очевидно, что метод, показанный на рис. 1.1, 
может быть применен и для вычисления объема трехмерной фигуры, 
заключенной внутрь куба. Аналогично можно рассчитывать объемы 
многомерных фигур в пространствах бόльшей размерности. Этот под‑
ход может быть без модификации применен и для многомерного чис‑
ленного интегрирования, поскольку определенные интегралы могут 
быть представлены как объемы многомерных тел.

L

S

Рис. 1.1. Вычисление 
площади плоской фи‑
гуры с криволинейной 
границей методом Мон‑
те‑Карло [2]

1. Применение метода монте-Карло для моделироВания физичесКих систем 

1.1.2. Распределения случайных величин

Одним из основных этапов любой вариации метода Монте‑Кар‑
ло является генерирование случайных величин, распределенных 
по необходимому закону. При вычислении площади фигуры в пара‑
графе 1.1.1 этими случайными величинами были координаты точек, 
разбрасываемых по площади квадрата. Каждой точке соответствова‑
ли две координаты (x, y), каждая из которых должна была быть слу‑
чайной величиной, равномерно распределенной на интервале (0; L).
Пусть некоторая случайная величина x определена на интервале 
(a; b). Плотностью распределения x называют функцию w (x), та‑
кую, что

W x
w x dx
P
x

a

x
( ) =
( )
=
<
(
)
т
x
 —

вероятность того, что x окажется меньше, чем x. Сам интеграл W(x) на‑
зывается интегральной (кумулятивной) функцией распределе‑
ния величины x, значения W(x) всегда принадлежат интервалу (0; 1). 
Поскольку P
b
g Ј
(
)  = 1, для любой плотности распределения выпол‑
няется условие нормировки

 
w x dx

a

b
( )
=
т
1. 
 (1.1)

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

w x
b
a
x
a b

x
a b
( ) =
‑
О(
)

П(
)

м

нп

оп

1
, при
;

0,
при
;

;

.

Такое распределение имеет прямоуголь‑
ную форму, как это показано для интерва‑
ла (0; 1) на рис. 1.2.

Кроме равномерно распределенных, 
широко используются и часто рассматри‑
ваются нормально распределенные (рас‑
пределенные по Гауссу) случайные ве‑

w(x)

1

x
0
1
0

Рис. 1.2. Плотность вероятно‑
сти для равномерного распре‑
деления на интервале (0; 1)

1.1. содержание метода монте-Карло

личины. Нормальной (гауссовой) случайной величиной называется 
случайная величина x, определенная на всей числовой оси ‑Ґ Ґ
(
)
;
 
с плотностью распределения

 
w x
x
( ) =
‑

‑
(
)
й

л

к
к

щ

ы

ъ
ъ
1

2
2

2

2
s
p

x

s
exp
,

где s — дисперсия x , характеризующая разброс значений относи‑
тельно среднего; x  — математическое ожидание (среднее значение) x.
Среднее значение произвольной непрерывной случайной величи‑
ны x с плотностью распределения w (x) может быть вычислено по фор‑
муле

 
x =
( )
т xw x dx

0

1

,

а дисперсия определяется по выражению

 
s
x
x
2
2

0

1
2
[ ] =
( )
‑( )
т x w x dx
.

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

Стандартные генераторы случайных чисел (см. подглаву 1.2) обыч‑
но создают числовые последовательности с равномерным распреде‑
лением. В то же время для решения конкретных задач методом Мон‑
те‑Карло могут потребоваться случайные величины, распределенные 
по самым разным законам. Существуют достаточно простые способы 
перехода от равномерно распределенной случайной последователь‑
ности к последовательностям с любыми другими распределениями. 
Остановимся на одном из них.
Пусть необходимо генерировать значения случайной величины x, 
распределенной в интервале (a; b) с плотностью вероятности w(x) 
и функцией распределения W(x). Значения функции распределения 
W(x) обязательно приходятся на интервал (0; 1), что позволяет сопоста‑
вить ей случайную величину g, равномерно распределенную на этом же 
интервале.

1. Применение метода монте-Карло для моделироВания физичесКих систем 

Известно, что если g — случайная величина, равномерно распре‑
деленная на интервале (0; 1), то случайная величина x О (a; b), удов‑
летворяющая соотношению

 
W
w x dx

a

x
g

x

( ) є
( )
=
т
, 
 (1.2)

будет распределена именно с плотностью вероятности w (x) и функ‑
цией распределения W(x).
В результате аналитического либо численного решения уравнения 
можно на основании имеющейся равномерно распределенной после‑
довательности {gi} получить случайную последовательность {xi} с тре‑
буемой плотностью распределения w(x).
Изложенный метод не является единственным. Существуют и дру‑
гие методы получения как непрерывных, так и дискретных случайных 
величин с требуемыми распределениями. В любом случае для получе‑
ния разнообразных случайных последовательностей, которые могут 
потребоваться для реализации конкретных вариантов метода Монте‑
Карло, необходимо иметь качественный генератор какой‑либо стан‑
дартной случайной последовательности, например, генератор равно‑
мерно распределенных случайных чисел.

1.2. Генераторы случайных чисел

1.2.1. Требования, предъявляемые к генераторам  
случайных чисел

В задачах, решаемых методом Монте‑Карло, очень большое значе‑
ние может иметь качество используемых случайных последовательно‑
стей. Как отличие распределения случайной величины от требуемого, 
так и коррелированность (взаимозависимость) соседних значений ис‑
кажают результаты моделирования, причем не всегда очевидным об‑
разом. Случайные последовательности, подходящие для метода Мон‑
те‑Карло, должны удовлетворять следующим требованиям:
· максимально точное воспроизведение заданного случайного рас‑
пределения (в частности, равномерного распределения);

1.2. Генераторы случайных чисел

· отсутствие корреляций во взаимном расположении членов по‑
следовательности;
· достаточно большой период повторения (зацикливания) после‑
довательности (или отсутствие такого периода, как у «генерато‑
ров энтропии»);
· одинаковая случайность всех битов числа;
· необратимость последовательности.

1.2.2. Типы генераторов случайных чисел

По принципу формирования числовой последовательности приня‑
то выделять следующие типы генераторов случайных чисел:
· генераторы, основанные на естественных процессах, таких как 
шум транзисторов или сетевого напряжения (генераторы эн-
тропии). Не имеют периода. Создают заведомо случайные, по‑
этому очень качественные последовательности. Вместе с тем 
такие генераторы бывают неудобны на практике из‑за таких 
ограничений:
– как сравнительно медленная работа;
– сложность распараллеливания;
– сложность самостоятельной реализации на новых вычисли‑
тельных устройствах, таких как графические процессоры;
– невоспроизводимость случайных последовательностей;
· генераторы квазислучайных чисел. На основе простых функций 
создают числовые последовательности, члены которых заведо‑
мо коррелируют между собой. Такие генераторы могут приме‑
няться для решения задач, в которых значение имеет только рав‑
номерность распределения случайных чисел, а их корреляции 
неважны. Например, последовательность {1, 2, 3, 4, 5, 5, 4, 3, 2, 1} 
имеет вполне равномерное распределение, хотя и неслучайна;
· генераторы псевдослучайных чисел. Наиболее широко исполь‑
зуются при моделировании случайных последовательностей 
на ЭВМ. Для получения следующих членов последовательности 
обычно осуществляют более или менее сложные операции над 
предыдущими членами, формируя очередное случайное число 
как комбинацию из цифр мантиссы результата этих операций, 
либо как комбинацию битов, представляющих результат.

1. Применение метода монте-Карло для моделироВания физичесКих систем 

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

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

Как отмечено выше, при параллельной реализации метода Монте‑
Карло на графическом процессоре создается большое количество па‑
раллельных вычислительных потоков (исполняемых на параллельных 
«вычислителях»), каждый из которых обрабатывает один (или несколь‑
ко) случайных вариантов поведения или состояния модельной систе‑
мы. Поскольку эти варианты должны быть максимально независи‑
мы друг от друга, вычислительные потоки не могут использовать одну 
и ту же последовательность случайных чисел: каждому потоку нужен 
свой генератор.
В принципе последовательности псевдослучайных чисел для каж‑
дого из вычислительных потоков могли бы быть сгенерированы зара‑
нее, а при необходимости — загружаться в память, доступную графи‑
ческому процессору. Такое решение не представляется эффективным, 
поскольку доступ графического процессора к видеопамяти, где долж‑
ны будут храниться эти числа, осуществляется слишком медленно; 
количество доступных случайных чисел становится ограниченным.
Следовательно, генератор случайных чисел должен быть запрограм‑
мирован как часть вычислительного ядра, исполняемого графическим 
процессором в параллельном режиме. При этом внутри каждого вы‑

Доступ онлайн
200 ₽
В корзину