Участник:Jhuighuy/Уравнение Пуассона, решение методом Галеркина - История изменений

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

2017-11-29T16:06:52Z

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

← Предыдущая версия		Версия от 16:06, 29 ноября 2017
Строка 140:		Строка 140:
	[[Файл:GalerkinMPI_Perf.png\|thumb\|center\|500px\|Рисунок 2. Оценка сильной масштабируемости метода Галеркина.]]		[[Файл:GalerkinMPI_Perf.png\|thumb\|center\|500px\|Рисунок 2. Оценка сильной масштабируемости метода Галеркина.]]

	Анализируя график, видно, что производительность растет линейно с увеличением количества вычислительных узлов. Шкала на данном графике логарифмическая. Это можно объяснить отсутствием накладных расходов на обмен данными между процессами при вычислении коэффициентов приближенного решения и значений функции.		Анализируя график, видно, что производительность растет линейно с увеличением количества вычислительных узлов. Шкала на данном графике логарифмическая. Это можно объяснить отсутствием накладных расходов на обмен данными между процессами (то есть все данные, необходимые для соответствующего вычисления, локальны относительно процесса) при вычислении коэффициентов приближенного решения и значений функции, а также лишь двумя обменами данными между этапами вычислений.

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

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

2017-11-29T15:38:33Z

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

← Предыдущая версия		Версия от 15:38, 29 ноября 2017
Строка 149:		Строка 149:

	* [https://github.com/asaks/Galerkin-Method-Integral-Equation-MPI] Реализация метода Галеркина для интегрального уравнения с использованием MPI.		* [https://github.com/asaks/Galerkin-Method-Integral-Equation-MPI] Реализация метода Галеркина для интегрального уравнения с использованием MPI.
	* [https://github.com/chanchikwan/sg2] Реализация метода Галеркина для задач CFD с ~~использование~~ CUDA.		* [https://github.com/chanchikwan/sg2] Реализация метода Галеркина для задач CFD с использованием CUDA.

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

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

2017-11-29T15:36:50Z

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

← Предыдущая версия		Версия от 15:36, 29 ноября 2017
Строка 140:		Строка 140:
	[[Файл:GalerkinMPI_Perf.png\|thumb\|center\|500px\|Рисунок 2. Оценка сильной масштабируемости метода Галеркина.]]		[[Файл:GalerkinMPI_Perf.png\|thumb\|center\|500px\|Рисунок 2. Оценка сильной масштабируемости метода Галеркина.]]

	Анализируя график, видно, что производительность растет линейно с увеличением количества вычислительных узлов. Шкала на данном графике логарифмическая. Это можно объяснить отсутствием ~~расходом~~ на обмен данными между процессами при вычислении коэффициентов приближенного решения и значений функции.		Анализируя график, видно, что производительность растет линейно с увеличением количества вычислительных узлов. Шкала на данном графике логарифмическая. Это можно объяснить отсутствием накладных расходов на обмен данными между процессами при вычислении коэффициентов приближенного решения и значений функции.

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

Jhuighuy: /* Входные и выходные данные алгоритма */

2017-11-29T15:35:17Z

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

← Предыдущая версия		Версия от 15:35, 29 ноября 2017
Строка 122:		Строка 122:
	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

	В качестве входных данных выступает трехмерный массив <math>M_x \times M_y \times M_z</math> правой части уравнения. ~~Выходной массив -~~ трехмерный массив решения той же размерности.		В качестве входных данных выступает трехмерный массив <math>M_x \times M_y \times M_z</math> правой части уравнения. Выходные данные — трехмерный массив решения той же размерности.

	=== Свойства алгоритма ===		=== Свойства алгоритма ===

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

2017-11-29T15:33:16Z

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

← Предыдущая версия		Версия от 15:33, 29 ноября 2017
Строка 117:		Строка 117:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Информационный граф показывает, что коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из этих значений вычисляется в виде сумм, дополнительного увеличения производительности можно достичь за счет параллельного суммирования. Таким образом, ~~при количестве~~ <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>		Информационный граф показывает, что коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из этих значений вычисляется в виде сумм, дополнительного увеличения производительности можно достичь за счет параллельного суммирования. Таким образом, если <math>P</math> — количество вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math>, можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>
	При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.		При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.

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

2017-11-29T15:32:13Z

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

← Предыдущая версия		Версия от 15:32, 29 ноября 2017
Строка 117:		Строка 117:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	Информационный граф показывает, что коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из ~~этий значение~~ вычисляется в виде сумм, дополнительного увеличения производительности можно достичь за счет параллельного суммирования. Таким образом, при количестве <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>		Информационный граф показывает, что коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из этих значений вычисляется в виде сумм, дополнительного увеличения производительности можно достичь за счет параллельного суммирования. Таким образом, при количестве <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>
	При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.		При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.

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

2017-11-29T15:31:13Z

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

← Предыдущая версия		Версия от 15:31, 29 ноября 2017
Строка 117:		Строка 117:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	~~Информационного~~ граф показывает, что ~~можно~~ коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из ~~этих~~ значение вычисляется в виде сумм, ~~дополнительный параллелизм~~ можно достичь за счет параллельного суммирования. Таким образом, при количестве <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>		Информационный граф показывает, что коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из этий значение вычисляется в виде сумм, дополнительного увеличения производительности можно достичь за счет параллельного суммирования. Таким образом, при количестве <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>
	При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.		При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.

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

2017-11-29T15:28:20Z

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

← Предыдущая версия		Версия от 15:28, 29 ноября 2017
Строка 117:		Строка 117:
	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===

	~~Из информационного графа видно~~, что можно коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из этих значение вычисляется в виде сумм, дополнительный параллелизм можно достичь за счет параллельного суммирования. Таким образом, при количестве <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>		Информационного граф показывает, что можно коэффициенты <math>C_{m,n,l}</math> и <math>\hat{u}_{h,i,j,k}</math> можно вычислять параллельно. Так как каждое из этих значение вычисляется в виде сумм, дополнительный параллелизм можно достичь за счет параллельного суммирования. Таким образом, при количестве <math>P</math> вычислительных узлов, при <math>P \le min(N_x N_y N_z, M_x M_y M_z)</math> можно достичь производительности в <math>O(\frac{N_x N_y N_z M_x M_y M_z}{P})</math> операций. <br/>
	При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.		При <math>P \gt min(N_x N_y N_z, M_x M_y M_z)</math>, положив <math>Q = mod(P, min(N_x N_y N_z, M_x M_y M_z))</math>, за счет параллельного суммирования, эта величина равна <math>O(\frac{N_x N_y N_z + M_x M_y M_z}{Q})</math>.

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

2017-11-29T15:26:56Z

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

← Предыдущая версия		Версия от 15:26, 29 ноября 2017
Строка 71:		Строка 71:
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

	~~С сначала~~ вычислим все коэффициенты, а потом восстановим функцию. Алгоритм:		Сначала вычислим все коэффициенты, а потом восстановим функцию. Алгоритм:
	# Для всех <math>i=1..N_x, j=1..N_y, k=1..N_z</math> вычислить <math>C_{m,n,l}</math>.		# Для всех <math>i=1..N_x, j=1..N_y, k=1..N_z</math> вычислить <math>C_{m,n,l}</math>.
	# Для всех <math>i=0..M_x, j=0..M_y, k=0..M_z</math> вычислить <math>\hat{u}_{h,i,j,k}</math>.		# Для всех <math>i=0..M_x, j=0..M_y, k=0..M_z</math> вычислить <math>\hat{u}_{h,i,j,k}</math>.

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

2017-11-29T15:26:48Z

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

← Предыдущая версия		Версия от 15:26, 29 ноября 2017
Строка 71:		Строка 71:
	=== Макроструктура алгоритма ===		=== Макроструктура алгоритма ===

	~~Рассмотрим две возможные структуры алгоритма, в одной~~ сначала вычислим все коэффициенты, а потом восстановим функцию. Алгоритм:		С сначала вычислим все коэффициенты, а потом восстановим функцию. Алгоритм:
	# Для всех <math>i=1..N_x, j=1..N_y, k=1..N_z</math> вычислить <math>C_{m,n,l}</math>.		# Для всех <math>i=1..N_x, j=1..N_y, k=1..N_z</math> вычислить <math>C_{m,n,l}</math>.
	# Для всех <math>i=0..M_x, j=0..M_y, k=0..M_z</math> вычислить <math>\hat{u}_{h,i,j,k}</math>.		# Для всех <math>i=0..M_x, j=0..M_y, k=0..M_z</math> вычислить <math>\hat{u}_{h,i,j,k}</math>.