Участник:Grachovamc/Интегрирование методом Монте - Карло - История изменений

Grachovamc: /* Масштабируемость алгоритма и его реализации */

2017-12-05T12:22:12Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 12:22, 5 декабря 2017
Строка 313:		Строка 313:
	Для этого были созданы реализации описанных методов. В качестве тестового примера рассматривалось интегрирование функции трех переменных <math>\sqrt{x_1} + \sqrt{x_2} - \sqrt{x_3}</math>. Использование метода Монте - Карло в данном случае нерационально, поскольку оптимальные выбрать другой детерминированный метод, но так как в данной задаче вычисление подынтегральной функции рассматривается как "черный ящик", следовательно сложность вычисления функции не имеет значения.		Для этого были созданы реализации описанных методов. В качестве тестового примера рассматривалось интегрирование функции трех переменных <math>\sqrt{x_1} + \sqrt{x_2} - \sqrt{x_3}</math>. Использование метода Монте - Карло в данном случае нерационально, поскольку оптимальные выбрать другой детерминированный метод, но так как в данной задаче вычисление подынтегральной функции рассматривается как "черный ящик", следовательно сложность вычисления функции не имеет значения.

	Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Для проведения экспериментов использовалась программа, написанная на языке C с использованием библиотеки Intel MPI 5.0.1. Тесты проводились на суперкомпьютере Ломоносов<ref>http://users.parallel.ru/wiki/pages/22-config</ref> в узле test. Для компиляции программы использовалась команда mpicc, которая является надстройкой над имеющимися компиляторами и автоматически подключает заголовочные файлы и библиотеки MPI. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 с масштабированием по степени числа 2. Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.		Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Для проведения экспериментов использовалась программа, написанная на языке C, с использованием библиотеки Intel MPI 5.0.1. Тесты проводились на суперкомпьютере Ломоносов<ref>http://users.parallel.ru/wiki/pages/22-config</ref> в узле test. Для компиляции программы использовалась команда mpicc, которая является надстройкой над имеющимися компиляторами и автоматически подключает заголовочные файлы и библиотеки MPI. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 с масштабированием по степени числа 2. Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.

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

Grachovamc: /* Масштабируемость алгоритма и его реализации */

2017-12-05T12:21:49Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 12:21, 5 декабря 2017
Строка 313:		Строка 313:
	Для этого были созданы реализации описанных методов. В качестве тестового примера рассматривалось интегрирование функции трех переменных <math>\sqrt{x_1} + \sqrt{x_2} - \sqrt{x_3}</math>. Использование метода Монте - Карло в данном случае нерационально, поскольку оптимальные выбрать другой детерминированный метод, но так как в данной задаче вычисление подынтегральной функции рассматривается как "черный ящик", следовательно сложность вычисления функции не имеет значения.		Для этого были созданы реализации описанных методов. В качестве тестового примера рассматривалось интегрирование функции трех переменных <math>\sqrt{x_1} + \sqrt{x_2} - \sqrt{x_3}</math>. Использование метода Монте - Карло в данном случае нерационально, поскольку оптимальные выбрать другой детерминированный метод, но так как в данной задаче вычисление подынтегральной функции рассматривается как "черный ящик", следовательно сложность вычисления функции не имеет значения.

	Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Для проведения экспериментов использовалась программа, написанная на языке C. Тесты проводились на суперкомпьютере Ломоносов<ref>http://users.parallel.ru/wiki/pages/22-config</ref> в узле test. Для компиляции программы использовалась команда mpicc, которая является надстройкой над имеющимися компиляторами и автоматически подключает заголовочные файлы и библиотеки MPI~~. Запуск (точнее, постановка в очередь) осуществляется командой sbatch модуля slurm с использованием Intel MPI 5.0.1~~. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 ~~(рассматривались~~ степени ~~двойки)~~. Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.		Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Для проведения экспериментов использовалась программа, написанная на языке C с использованием библиотеки Intel MPI 5.0.1. Тесты проводились на суперкомпьютере Ломоносов<ref>http://users.parallel.ru/wiki/pages/22-config</ref> в узле test. Для компиляции программы использовалась команда mpicc, которая является надстройкой над имеющимися компиляторами и автоматически подключает заголовочные файлы и библиотеки MPI. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 с масштабированием по степени числа 2. Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.

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

Grachovamc: /* Масштабируемость алгоритма и его реализации */

2017-12-05T12:12:31Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 12:12, 5 декабря 2017
Строка 313:		Строка 313:
	Для этого были созданы реализации описанных методов. В качестве тестового примера рассматривалось интегрирование функции трех переменных <math>\sqrt{x_1} + \sqrt{x_2} - \sqrt{x_3}</math>. Использование метода Монте - Карло в данном случае нерационально, поскольку оптимальные выбрать другой детерминированный метод, но так как в данной задаче вычисление подынтегральной функции рассматривается как "черный ящик", следовательно сложность вычисления функции не имеет значения.		Для этого были созданы реализации описанных методов. В качестве тестового примера рассматривалось интегрирование функции трех переменных <math>\sqrt{x_1} + \sqrt{x_2} - \sqrt{x_3}</math>. Использование метода Монте - Карло в данном случае нерационально, поскольку оптимальные выбрать другой детерминированный метод, но так как в данной задаче вычисление подынтегральной функции рассматривается как "черный ящик", следовательно сложность вычисления функции не имеет значения.

	Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Тесты проводились на суперкомпьютере Ломоносов. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 (рассматривались степени двойки). Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.		Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Для проведения экспериментов использовалась программа, написанная на языке C. Тесты проводились на суперкомпьютере Ломоносов<ref>http://users.parallel.ru/wiki/pages/22-config</ref> в узле test. Для компиляции программы использовалась команда mpicc, которая является надстройкой над имеющимися компиляторами и автоматически подключает заголовочные файлы и библиотеки MPI. Запуск (точнее, постановка в очередь) осуществляется командой sbatch модуля slurm с использованием Intel MPI 5.0.1. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 (рассматривались степени двойки). Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.

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

Grachovamc в 18:06, 3 декабря 2017

2017-12-03T18:06:05Z

← Предыдущая версия		Версия от 18:06, 3 декабря 2017
Строка 94:		Строка 94:
	Таким образом, вычислительным ядром последовательной реализации любого из представленных вариантов метода Монте - Карло интегрирования является многократное вычисление значения функции в случайной точке.		Таким образом, вычислительным ядром последовательной реализации любого из представленных вариантов метода Монте - Карло интегрирования является многократное вычисление значения функции в случайной точке.
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===
	~~Согласно~~ описанию вычислительного ядра алгоритма в качестве макровершины можно взять вычисление подынтегральной функции ~~в случайной точке~~.		В случае использования метода усреднения подынтегральной функции начальным этапом работы алгоритма является генерация случайных точек, соответствующих начальным условиям, то есть подынтегральной функции, пределам интегрирования и количеству генерируемых точек. Время на выполнение первого шага оценивается константой. Затем производится вычисление подынтегральной функции в полученных точках, которое согласно описанию вычислительного ядра алгоритма можно принять в качестве макровершины и не задумываться далее о виде и особенностях этой функции, которые будут определять время выполнения этого этапа. Далее производится суммирование результатов предыдущего шага и умножение полученной суммы на соответствующую константу. Также в качестве макровершины можно взять в целом суммирование значений функции в случайных точках и умножение этой суммы на константу, но так как в большинстве случаев время, которое уходит на вычисление подынтегральной функции гораздо больше, чем время, требуемое на осуществление операций суммирования и умножения, то основное время работы все равно приходится на вычисление подынтегральной функции.

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

Grachovamc: /* Масштабируемость алгоритма и его реализации */

2017-12-02T07:55:31Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 07:55, 2 декабря 2017
Строка 314:		Строка 314:
	Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Тесты проводились на суперкомпьютере Ломоносов. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 (рассматривались степени двойки). Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.		Выбранный алгоритм использует в качестве метода распараллеливания технологию MPI. Тесты проводились на суперкомпьютере Ломоносов. Для демонстрации оказалось достаточным провести тесты с количеством процессоров до 128 (рассматривались степени двойки). Для количества точек, в которых вычислялась функция, была введена логарифмическая шкала: от 1000 до 1000000000 с шагом умножения на 10. Такая шкала была выбрана для того, чтобы полностью продемонстрировать постепенный рост производительности при увеличении числа процессоров и падение эффективности при небольших количествах точек интегрирования.

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

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

Grachovamc: /* Метод усреднения подынтегральной функции */

2017-12-01T17:05:31Z

Метод усреднения подынтегральной функции

← Предыдущая версия		Версия от 17:05, 1 декабря 2017
Строка 248:		Строка 248:
	==== Метод усреднения подынтегральной функции ====		==== Метод усреднения подынтегральной функции ====

	Код последовательной реализации для случая использования метода усреднения подынтегральной функции в предположении, что предел интегрирования по каждой из переменных расположен внутри отрезка [0,1], на языке C может выглядеть так:		Код последовательной реализации для случая использования метода усреднения подынтегральной функции при простейшем предположении, что предел интегрирования по каждой из переменных расположен внутри отрезка [0,1], на языке C может выглядеть так:

	<pre>		<pre>

Grachovamc: /* Геометрический метод */

2017-12-01T17:04:18Z

Геометрический метод

← Предыдущая версия		Версия от 17:04, 1 декабря 2017
Строка 275:		Строка 275:
	==== Геометрический метод ====		==== Геометрический метод ====

	Код последовательной реализации для случая использования геометрического метода в предположении, что ~~пределом интегрирования по каждой~~ из ~~переменных~~ является ~~отрезок~~ [0,1], на языке C может выглядеть так:		Код последовательной реализации для случая использования геометрического метода при простейшем предположении, что функцию можно ограничить параллелепипедом, каждая из сторон которого является отрезком [0,1], на языке C может выглядеть так:

	<pre>		<pre>

Grachovamc: /* Метод усреднения подынтегральной функции */

2017-12-01T17:02:08Z

Метод усреднения подынтегральной функции

← Предыдущая версия		Версия от 17:02, 1 декабря 2017
Строка 248:		Строка 248:
	==== Метод усреднения подынтегральной функции ====		==== Метод усреднения подынтегральной функции ====

	Код последовательной реализации для случая использования метода усреднения подынтегральной функции в предположении, что ~~пределом~~ интегрирования по каждой из переменных ~~является отрезок~~ [0,1], на языке C может выглядеть так:		Код последовательной реализации для случая использования метода усреднения подынтегральной функции в предположении, что предел интегрирования по каждой из переменных расположен внутри отрезка [0,1], на языке C может выглядеть так:

	<pre>		<pre>

Grachovamc: /* Геометрический метод */

2017-12-01T17:00:36Z

Геометрический метод

← Предыдущая версия		Версия от 17:00, 1 декабря 2017
Строка 275:		Строка 275:
	==== Геометрический метод ====		==== Геометрический метод ====

	Код последовательной реализации для случая использования геометрического метода на языке C может выглядеть так:		Код последовательной реализации для случая использования геометрического метода в предположении, что пределом интегрирования по каждой из переменных является отрезок [0,1], на языке C может выглядеть так:

	<pre>		<pre>
	double geometric_method(long int number, int order~~, double *limits~~)		double geometric_method(long int number, int order)
	{		{
	double coord[order + 1];		double coord[order + 1];

Grachovamc: /* Метод усреднения подынтегральной функции */

2017-12-01T16:59:10Z

Метод усреднения подынтегральной функции

← Предыдущая версия		Версия от 16:59, 1 декабря 2017
Строка 248:		Строка 248:
	==== Метод усреднения подынтегральной функции ====		==== Метод усреднения подынтегральной функции ====

	Код последовательной реализации для случая использования метода усреднения подынтегральной функции на языке C может выглядеть так:		Код последовательной реализации для случая использования метода усреднения подынтегральной функции в предположении, что пределом интегрирования по каждой из переменных является отрезок [0,1], на языке C может выглядеть так:

	<pre>		<pre>