Постановка задачи
Постановка задачи
В прямоугольной области требуется найти решение задачи Дирихле для уравнения Пуассона
То есть найти такую функцию U = U(x,y), принимающую значения g(x,y) на границе области и удовлетворяющей в области уравнению. (В качестве области задания функции будет использоваться единичный квадрат)
Необходимо реализовать метод Гаусса-Зейделя для поставленной задачи и сравнить время работы алгоритмов.
Метод решения
Метод решения
Явная разностная схема решения этого уравнения имеет вид:
Где u значение функции в точке разностной сетки. Ниже представлен главный фрагмент программы итерационного решения задачи.
double A[n+2][m+2], B[n][m];
...
while(…)
{
/*выполнение схемы крест*/
for(j=1;j<=m;j++)
for(i=1;i<=n;i++)
B[i-1][j-1] = 0.25*(A[i-1}[j]+A[i+1][j]+A[i][j-1]+A[i][j+1])
Этот фрагмент программы описывает главный цикл итерационного процесса решения, где на каждой итерации значение в окрестности точки заменяется средним значение сумм значений ее четырех соседних точек на предыдущем временном шаге итерации.
Параллельная схема
Параллельная схема
Алгоритм этой задачи имеет простую структуру, идентичную для всех точек пространства вычисления, поэтому здесь при построении параллельной программы целесообразно использовать метод распараллеливания по данным. Массив «разрезается» на части, затем в каждый процессор загружается программа, аналогичная последовательной программе, но с модифицированными значениями индексов циклов и соответствующая часть массива данных, т.е. каждый процессор обрабатывает только часть данных. Будем использовать одномерное разрезание исходной матрицы.
Анализ эффективности
Анализ эффективности
Для анализа будем использовать следующие показатели:
n - количество узлов по каждой из координат области D.
m - число операций, выполняемых методом для одного узла сетки.
k - количество итераций метода до выполнения условия остановки.
T1 - время решения задачи на одном процессоре.
Tp - время решения задачи на p процессорах.
S - ускорение (speedup). Ускорение определяется из отношения: S=T1/Tp .
Вычислительная трудоёмкость последовательного алгоритма T1 = k*m*n*n.
Для p потоков:
Tp=k*m*n*n/p.
S = О(n)/O(n/p)->p
Результаты экспериментов
Результаты экспериментов
Характеристика оборудования:
OS: Windows 7 x86
CPU: Intel Core 2 Duo T9300 2.50GHz
RAM: 4GB
Латентность: 0.00678с
Пропускная способность: 38.2 мб/с
Автор
Автор
Работы выполнил студент 3 курса Лебедев Сергей.
| 
