fdvmLDr (1158337), страница 14

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 14)

A x = b

где A – матрица коэффициентов,

b – вектор свободных членов,

x – вектор неизвестных.

Для решения этой системы используются следующие основные методы.

Прямые методы. Хорошо известный метод исключения Гаусса является наиболее широко используемым алгоритмом этого класса. Основная идея алгоритма заключается в преобразовании матрицы А в верхнетреугольную матрицу и использовании затем обратной подстановки, чтобы привести ее к диагональной форме.

Явные итерационные методы. Наиболее известным алгоритмом этого класса является метод релаксации Якоби. Алгоритм выполняет следующие итерационные вычисления

x_i,j^new = (x_i-1,j^old + x_i,j-1^old + x_i+1,j^old + x_i,j+1^old ) / 4

Неявные итерационные методы. К этому классу относится метод последовательной верхней релаксации. Итерационное приближение вычисляется по формуле

x_i,j^new = ( w / 4 ) * (x_i-1,j^new + x_i,j-1^new + x_i+1,j^old + x_i,j+1^old ) + (1-w) * x_i,j^old

При использовании "красно-черного" упорядочивания переменных каждый итерационный шаг разделяется на два полушага Якоби. На одном полушаге вычисляются значения "красных" переменных, на другом – "черных" переменных. "Красно-черное" упорядочивание позволяет совместить вычисления и обмены данными.

Пример 1. Алгоритм метода исключения Гаусса

PROGRAM GAUSS

C решение системы линейных уравнений A x = b

PARAMETER ( N = 100 )

REAL A( N, N+1 ), X( N )

C A : матрица коэффициентов (N,N+1).

C вектор правых частей линейных уравнений хранится

C в (N+1)-ом столбце матрицы A

C X : вектор неизвестных

C N : число линейных уравнений

CDVM$ DISTRIBUTE A ( BLOCK, *)

CDVM$ ALIGN X(I) WITH A(I, N+1)

C

C Инициализация

C

*DVM$ PARALLEL ( I ) ON A( I , * )

DO 100 I = 1, N

DO 100 J = 1, N+1

IF (( I .EQ. J ) THEN

A( I, J ) = 2.0

ELSE

IF ( J .EQ. N+1) THEN

A( I, J ) = 0.0

ENDIF

ENDIF

100 CONTINUE

C

C Исключение

C

DO 1 I = 1, N

C I-ая строка матрицы A буферизуется перед

C обработкой I-ого уравнения, и ссылки A(I,K), A(I, I)

C заменяются соответствующими ссылками на буфер

*DVM$ PARALLEL ( J ) ON A( J, * ) , REMOTE_ACCESS (A ( I, : ))

DO 5 J = I+1, N

DO 5 K = I+1, N+1

A( J, K ) = A( J, K ) - A( J, I ) * A( I, K ) / A( I, I )

5 CONTINUE

1 CONTINUE

C сначала вычисляется X(N)

X( N ) = A( N, N+1 ) / A( N, N )

C

C Нахождение X(N-1), X(N-2), ...,X(1) обратной подстановкой

C

DO 6 J = N-1, 1, -1

C (J+1)-ый элемент массива X буферизуется перед

C обработкой J-ого уравнения, и ссылка X(J+1)

C заменяется соответствующей ссылкой на буфер

*DVM$ PARALLEL ( I ) ON A( I , * ) , REMOTE_ACCESS ( X( J+1 ))

DO 7 I = 1, J

A( I, N+1 ) = A( I, N+1 ) - A( I, J+1 ) * X( J+1 )

7 CONTINUE

X( J ) = A( J, N+1 ) / A( J, J)

6 CONTINUE

PRINT *, X

END

Пример 2. Алгоритм Якоби

PROGRAM JACOB

PARAMETER (K=8, ITMAX=20)

REAL A(K,K), B(K,K), EPS, MAXEPS

CDVM$ DISTRIBUTE A ( BLOCK, BLOCK)

CDVM$ ALIGN B( I, J ) WITH A( I, J )

C массивы A и B распределяются блоками

PRINT *, '********** TEST_JACOBI **********'

MAXEPS = 0.5E - 7

CDVM$ PARALLEL (J,I) ON A(I, J)

C гнездо из двух параллельных циклов, итерация (i,j) выполняется,

C на том процессоре, где размещен элемент A(i,j)

DO 1 J = 1, K

DO 1 I = 1, K

A(I, J) = 0.

IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.K .OR. J.EQ.K) THEN

B(I, J) = 0.

ELSE

B(I, J) = ( 1. + I + J )

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

CDVM$ PARALLEL (J, I) ON A(I, J), REDUCTION ( MAX( EPS ))

C переменная EPS используется для вычисления максимального значения

DO 21 J = 2, K-1

DO 21 I = 2, K-1

EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))

A(I, J) = B(I, J)

21 CONTINUE

CDVM$ PARALLEL (J, I) ON B(I, J), SHADOW_RENEW (A)

C копирование теневых элементов массива A

C с соседних процессоров перед выполнением цикла

DO 22 J = 2, K-1

DO 22 I = 2, K-1

B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J) + A( I, J+1 )) / 4

22 CONTINUE

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF ( EPS . LT . MAXEPS ) GO TO 3

2 CONTINUE

3 OPEN (3, FILE='JACOBI.DAT', FORM='FORMATTED')

WRITE (3,*) B

CLOSE (3)

END

Пример 3. Алгоритм Якоби (асинхронный вариант)

PROGRAM JACOB1

PARAMETER (K=8, ITMAX=20)

REAL A(K,K), B(K,K), EPS, MAXEPS

CDVM$ DISTRIBUTE A ( BLOCK, BLOCK)

CDVM$ ALIGN B( I, J ) WITH A( I, J )

C массивы A и B распределяются блоками

CDVM$ REDUCTION_GROUP REPS

PRINT *, '********** TEST_JACOBI_ASYNCHR **********'

CDVM$ SHADOW_GROUP SA ( A )

C создание группы теневых граней

MAXEPS = 0.5E - 7

CDVM$ PARALLEL (J,I) ON A(I, J)

C параллельный цикл для инициализации массивов А и В

DO 1 J = 1, K

DO 1 I = 1, K

A(I, J) = 0.

IF(I.EQ.1 .OR. J.EQ.1 .OR. I.EQ.K .OR. J.EQ.K) THEN

B(I, J) = 0.

ELSE

B(I, J) = ( 1. + I + J )

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

C создается группа редукционных операций

C и начальные значения редукционных переменных запоминаются

CDVM$ PARALLEL (J, I) ON A(I, J), SHADOW_START SA ,

CDVM$* REDUCTION_GROUP ( REPS : MAX( EPS ))

C изменяется порядок выполнения витков цикла:

C сначала вычисляются и посылаются граничные элементы массива A,

C затем вычисляются внутренние элементы массива A

DO 21 J = 2, K-1

DO 21 I = 2, K-1

EPS = MAX ( EPS, ABS( B( I, J) - A( I, J)))

A(I, J) = B(I, J)

21 CONTINUE

CDVM$ REDUCTION_START REPS

C начало редукционной операции над частичными результатами,

C вычисленными в копиях переменной EPS на каждом процессоре

CDVM$ PARALLEL (J, I) ON B(I, J), SHADOW_WAIT SA

C изменяется порядок выполнения витков цикла:

C сначала вычисляются внутренние элементы массива B , затем принимаются

C от соседних процессоров теневые элементы массиваA,

C а потом вычисляются граничные элементы массива B

DO 22 J = 2, K-1

DO 22 I = 2, K-1

B(I, J) = (A( I-1, J ) + A( I, J-1 ) + A( I+1, J) + A( I, J+1 )) / 4

22 CONTINUE

CDVM$ REDUCTION_WAIT REPS

C ожидается результат выполнения редукционной операции

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF ( EPS . LT . MAXEPS ) GO TO 3

2 CONTINUE

3 OPEN (3, FILE='JACOBI.DAT', FORM='FORMATTED')

WRITE (3,*) B

CLOSE (3)

END

Пример 4. Последовательная верхняя релаксация

PROGRAM SOR

PARAMETER ( N = 100 )

REAL A( N, N ), EPS, MAXEPS, W

INTEGER ITMAX

*DVM$ DISTRIBUTE A ( BLOCK, BLOCK )

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

*DVM$ PARALLEL ( I, J ) ON A( I, J )

DO 1 I = 1, N

DO 1 J = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

*DVM$ PARALLEL ( I, J) ON A( I, J), NEW (S),

*DVM$* REDUCTION ( MAX( EPS )), ACROSS (A(1:1,1:1))

C переменная S – приватная переменная

С (ее использование локализовано в пределах одного витка)

C переменная EPS используется для вычисления максимума

DO 21 I = 2, N-1

DO 21 J = 2, N-1

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

* A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

21 CONTINUE

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF (EPS .LT. MAXEPS ) GO TO 4

2 CONTINUE

4 PRINT *, A

END

Пример 5. "Красно-черная" последовательная верхняя релаксация

PROGRAM REDBLACK

PARAMETER ( N = 100 )

REAL A( N, N ), EPS, MAXEPS, W

INTEGER ITMAX

*DVM$ DISTRIBUTE A ( BLOCK, BLOCK )

ITMAX=20

MAXEPS = 0.5E - 5

W = 0.5

*DVM$ PARALLEL ( I, J ) ON A( I, J )

DO 1 I = 1, N

DO 1 J = 1, N

IF ( I .EQ.J) THEN

A( I, J ) = N + 2

ELSE

A( I, J ) = -1.0

ENDIF

1 CONTINUE

DO 2 IT = 1, ITMAX

EPS = 0.

C цикл для красных и черных переменных

DO 3 IRB = 1,2

*DVM$ PARALLEL ( I, J) ON A( I, J), NEW (S),

*DVM$* REDUCTION ( MAX( EPS )), SHADOW_RENEW (A)

C переменная S – приватная переменная

С (ее использование локализовано в пределах одного витка)

C переменная EPS используется для вычисления максимума

C Исключение : непрямоугольное итерационное пространство

DO 21 I = 2, N-1

DO 21 J = 2 + MOD ( I+ IRB, 2 ), N-1, 2

S = A( I, J )

A( I, J ) = (W / 4) * (A( I-1, J ) + A( I+1, J ) + A( I, J-1 ) +

* A( I, J+1 )) + ( 1-W ) * A( I, J)

EPS = MAX ( EPS, ABS( S - A( I, J )))

21 CONTINUE

3 CONTINUE

PRINT *, 'IT = ', IT, ' EPS = ', EPS

IF (EPS .LT. MAXEPS ) GO TO 4

2 CONTINUE

4 PRINT *, A

END

Пример 6. Статические задачи (параллельные секции)

PROGRAM TASKS

C прямоугольная сетка разделена на две области

C

C

PARAMETER (K=100, N1 = 50, ITMAX=10, N2 = K – N1 )

CDVM$ PROCESSORS P(NUMBER_OF_PROCESSORS( ))

REAL A1(N1+1,K), A2(N2+1,K), B1(N1+1,K), B2(N2+1,K)

INTEGER LP(2), HP(2)

CDVM$ TASK MB( 2 )

CDVM$ ALIGN B1( I, J ) WITH A1( I, J )

CDVM$ ALIGN B2( I, J ) WITH A2( I, J )

CDVM$ DISTRIBUTE :: A1, A2

CDVM$ REMOTE_GROUP BOUND

CALL DPT(LP, HP, 2)

C Распределение задач (областей) по процессорам.

C Распределение массивов по задачам

CDVM$ MAP MB( 1 ) ONTO P( LP(1) : HP(1) )

CDVM$ REDISTRIBUTE A1( *, BLOCK ) ONTO MB( 1 )

CDVM$ MAP MB( 2 ) ONTO P( LP(2) : HP(2) )

CDVM$ REDISTRIBUTE A2( *, BLOCK ) ONTO MB( 2 )

C Инициализация

CDVM$ PARALLEL ( J, I ) ON A1(I, J)

DO 10 J = 1, K

DO 10 I = 1, N1

IF(I.EQ.1 .OR. J.EQ.1 .OR. J.EQ.K) THEN

A1(I, J) = 0.

B1(I, J) = 0.

ELSE

B1(I, J) = 1. + I + J

A1(I, J) = B1(I, J)

ENDIF

10 CONTINUE

CDVM$ PARALLEL ( J, I ) ON A2(I, J)

Характеристики

Список файлов учебной работы