Участник:Valkyrie/Адаптивное интегрирование - История изменений

Valkyrie: /* Ресурс параллелизма алгоритма */

2017-12-11T16:09:55Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 16:09, 11 декабря 2017
Строка 65:		Строка 65:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг ~~отрезков~~ "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.		Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. Однако, в виде, описанном выше, данный алгоритм не может эффективно воспользоваться этой особенностью. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров, после чего, применить описанный алгоритм к каждому такому отрезку параллельно. Стоит отметить, что алгоритм сгущает сетку вокруг точек "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования. Таким образом, можно обеспечить равномерную нагрузку на все процессоры.

			Из написанного выше и того факта, что алгоритм адаптивно дробит определенные отрезки на 2 части, можно сделать следующий вывод - максимальная производительность может быть достигнута, если количество процессоров <math>p \approx 2k</math>, где <math>k</math> - количество точек "малой гладкости". При дальнейшем увеличении количества процессоров скорость алгоритма будет лишь падать, так как результируещее количество подотрезков интегрирования, полученных в результате адаптивного дробления исходных отрезков, зависит в основном от <math>k</math>, следовательно, сложность вычислений останется неизменной, а накладные расходы лишь увеличатся.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Valkyrie: /* Макроструктура алгоритма */

2017-12-11T15:25:49Z

Макроструктура алгоритма

← Предыдущая версия		Версия от 15:25, 11 декабря 2017
Строка 41:		Строка 41:

	Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.		Как уже записано в описании ядра алгоритма, основную часть алгоритма составляют вычисление квадратурной формулы и подсчет ошибки интегрирования на текущем отрезке интегрирования. После чего решается уточнять ли значение квадратурной формулы на данном отрезке или нет.
			Таким образом, на текущем отрезке интегрирования <math>[a,b]</math> выполняется следующая последовательность макроопераций:
			: подсчет <math>Q(a,b)</math> в качестве приближения значения интеграла на текущем отрезке интегрирования
			: подсчет <math>\tilde{Q}(a,b)</math> для последующей оценки ошибки интегрирования <math>\tau</math>
			: рекурсивное дробление текущего отрезка интегрирования на 2 подотрезка, если <math>\tau > \varepsilon </math>

	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===

Valkyrie: /* Описание схемы реализации последовательного алгоритма */

2017-12-11T15:16:12Z

Описание схемы реализации последовательного алгоритма

← Предыдущая версия		Версия от 15:16, 11 декабря 2017
Строка 44:		Строка 44:
	=== Описание схемы реализации последовательного алгоритма ===		=== Описание схемы реализации последовательного алгоритма ===

	Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{\|Q(a,c) + Q(c,b) - Q(a,b)\|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a~~,c) + Q(c~~,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.		Последовательный алгоритм представляет собой рекурсивный подсчет приближенного значения интеграла на отрезке с заданной допустимой погрешностью. Начальным отрезком является весь отрезок интегрирования. Далее, на каждом шаге рекурсии происходит подсчет трех квадратурных формул - <math>Q(a,b)</math>, <math>Q(a,c)</math> и <math>Q(c,b)</math>, после чего оценивается погрешность интегрирования <math>\tau = \frac{\|Q(a,c) + Q(c,b) - Q(a,b)\|}{15}</math>. Если <math>\tau < \varepsilon</math>, тогда приближенным значением интеграла на данном отрезке считаем величину <math>Q(a,b)</math>. Иначе рекурсивно считаем таким же образом приближенные значения интеграла на отрезках <math>[a,c]</math> и <math>[c,b]</math>, задав допустимой погрешностью на каждом отрезке величину <math>\frac{\varepsilon}{2}</math>, а их сумму примем за результат.

	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

Valkyrie: /* Общее описание алгоритма */

2017-12-11T15:12:50Z

Общее описание алгоритма

← Предыдущая версия		Версия от 15:12, 11 декабря 2017
Строка 16:		Строка 16:
	Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.		Из анализа погрешностей методов численного интегрирования следует, что точность получаемых результатов зависит как от характера изменения подынтегральной функции, так и от шага интегрирования. При этом ясно, что для достижения сравнимой точности при интегрировании слабо меняющейся функции шаг можно выбирать большим, чем при интегрировании резко меняющихся функций.

	На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции -вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.		На практике нередко встречаются случаи, когда подынтегральная функция меняется по-разному на отдельных участках отрезка интегрирования. Это обстоятельство требует такой организации численного алгоритма, при котором он автоматически приспосабливался к характеру изменения функции - вводил разные значения шага интегрирования на отдельных участках отрезка интегрирования. Это позволяет уменьшить машинное время без потери точности результатов расчета. Такой подход используется обычно при задании подынтегральной функции <math>f(x)</math> в виде формулы, а не в табличном виде.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

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

2017-12-11T15:10:14Z

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

← Предыдущая версия		Версия от 15:10, 11 декабря 2017
Строка 85:		Строка 85:
	Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.		Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
	{\| class="wikitable"		{\| class="wikitable"
	\|+ k = 16		\|+ k = 8
	! Количество процессоров		! Количество процессоров
	! 1		! 1
Строка 97:		Строка 97:
	\|-		\|-
	! Время, с		! Время, с
	\| ~~232~~.29 \|\| ~~117~~.49 \|\| 60.34 \|\| 30.23 \|\| 15.37 \|\| 7.99 \|\| 7.75 \|\| 13.57		\| 61.02 \|\| 30.79 \|\| 15.74 \|\| 7.92 \|\| 4.03 \|\| 4.03 \|\| 4.02 \|\| 7.19
	\|}		\|}
	{\| class="wikitable"		{\| class="wikitable"
Строка 114:		Строка 114:
	\| 232.29 \|\| 117.49 \|\| 60.34 \|\| 30.23 \|\| 15.37 \|\| 7.99 \|\| 7.75 \|\| 13.57		\| 232.29 \|\| 117.49 \|\| 60.34 \|\| 30.23 \|\| 15.37 \|\| 7.99 \|\| 7.75 \|\| 13.57
	\|}		\|}

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


	Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. <br>		Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. <br>

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

2017-12-11T15:03:48Z

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

← Предыдущая версия		Версия от 15:03, 11 декабря 2017
Строка 82:		Строка 82:

	[[file:ValkyrieScalability.png\|thumb\|center\|800px\|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]		[[file:ValkyrieScalability.png\|thumb\|center\|800px\|Рисунок 2. Параллельная реализация алгоритма адаптивного интегрирования]]

			Для более детального восприятия приведем некоторые из этих результатов в виде таблиц.
			{\| class="wikitable"
			\|+ k = 16
			! Количество процессоров
			! 1
			! 2
			! 4
			! 8
			! 16
			! 32
			! 64
			! 128
			\|-
			! Время, с
			\| 232.29 \|\| 117.49 \|\| 60.34 \|\| 30.23 \|\| 15.37 \|\| 7.99 \|\| 7.75 \|\| 13.57
			\|}
			{\| class="wikitable"
			\|+ k = 16
			! Количество процессоров
			! 1
			! 2
			! 4
			! 8
			! 16
			! 32
			! 64
			! 128
			\|-
			! Время, с
			\| 232.29 \|\| 117.49 \|\| 60.34 \|\| 30.23 \|\| 15.37 \|\| 7.99 \|\| 7.75 \|\| 13.57
			\|}

			Для компиляции использовались <code> gcc (GCC) 4.4.7 </code> и <code> openmpi/1.8.4-gcc </code>. <br>
			Программа компилировалась при помощи команды <code> mpicc -std=c99 Adaptive.c -o Adaptive -lm -fopenmp </code> <br>
			Запускалась: <code>./Adaptive k</code>, где <math>k</math> — количество "особых" точек. <br>

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Valkyrie: /* Информационный граф */

2017-12-01T01:48:18Z

Информационный граф

← Предыдущая версия		Версия от 01:48, 1 декабря 2017
Строка 58:		Строка 58:

	[[File:ValkyrieGraph.png\|thumb\|center\|800px\|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]		[[File:ValkyrieGraph.png\|thumb\|center\|800px\|Рисунок 1. Квадратики - задачи интегрирования <math>f(x)</math> на отрезке <math>[a,b]</math> при допустимой погрешности <math>\varepsilon</math>, разбиение задачи на 2 происходит при условии <math>\tau > \varepsilon</math>. Оранжевым выделены операции вычисления квадратурной формулы на данном отрезке интегрирования <math>Q(a,b)</math>, желтым - уточненной квадратурной формулы <math>\tilde{Q}(a,b)</math>. Зеленым отмечены операции оценки ошибки интегрирования <math>\tau</math>. Фиолетовым выделены операции сложения двух чисел. Красным отмечен результат работы алгоритма.]]


	Напомним, что уточненная квадратурная формула вычисляется следующим образом - <math>\tilde{Q}(a,b) = Q(a,\frac{a+b}{2}) + Q(\frac{a+b}{2},b)</math>

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

Valkyrie: /* Ресурс параллелизма алгоритма */

2017-12-01T01:47:55Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 01:47, 1 декабря 2017
Строка 64:		Строка 64:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся ~~еще не проинтегрированные~~ отрезки.		Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся отрезки, ожидающие дальнейшего интегрирования.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Valkyrie: /* Ресурс параллелизма алгоритма */

2017-12-01T01:46:50Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 01:46, 1 декабря 2017
Строка 64:		Строка 64:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки~~. С данной точки зрения для параллельного алгоритма стоит воспользоваться схемой "мастер - рабочий"~~.		Очевидным ресурсом параллелизма данного алгоритма является независимость интегрирования по разным отрезкам. В первую очередь, например, можно разбить исходный отрезок интегрирования на <math>p</math> частей, где <math>p</math> - количество процессоров. Стоит отметить, что алгоритм сгущает сетку вокруг отрезков "малой гладкости" интегрируемой функции, так что только разбиения начального отрезка интегрирования, вообще говоря, недостаточно для эффективной работы параллельного алгоритма. Для решения данной проблемы можно организовать, например, стек, в котором хранятся еще не проинтегрированные отрезки.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Valkyrie: /* Существующие реализации алгоритма */

2017-12-01T01:46:20Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 01:46, 1 декабря 2017
Строка 91:		Строка 91:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			Действительно широкого распространения, как, например, решение СЛАУ различными методами, данная задача не обрела. Тем не менее существует немало реализаций алгоритмов адаптивного интегрирования, например, таких как <ref>De Doncker E., Gupta A., Guo M. Adaptive multivariate integration using MPI //High-Performance Computing, 1997. Proceedings. Fourth International Conference on. – IEEE, 1997. – С. 152-158.</ref> и <ref>Walawalkar M. P. Parallelization of adaptive quadrature rule-based integration methods : дис. – Texas Tech University, 2003.</ref>.

	== Литература ==		== Литература ==