close

Вход

Забыли?

вход по аккаунту

?

Анализ эффективности параллельных алгоритмов решения ленточных систем линейных уравнений.

код для вставкиСкачать
???????? ????
???????????? ??????
?.?. ?????????
?????? ????????????? ???????????? ??????????
??????? ????????? ?????? ???????? ?????????
??????? ???????? ?????????????? ????????? (????) ????????? ?????????:
(1)
Ax = B ,
??? A ? ????????? ??????? ???????? n´ n ? ?????? ?????????? ??????? r ?
??????? ?????????? ??????? s ,
aij = 0 ??? i - j > r ??? j - i > s .
????????????? ????????? ????????? ???? ?????????????, ?????? ???? ?????? ????? r + s << n .
??????? ????? ??????? ????? ???? ???????? ????? ?? ????????????????
???????. LU ?????????? ? ??????? ???????? ????????, ??? ????? ?????????
????????? ????? ???? ????????? ??
4 3 2 2 1
(2)
N - N + N
3
3
6
???????? ? ????????? ??????. ????? ? ????? ????????, ?????????, ?????????,
???????, ?????? ?????, ?????????? ????? ??????? ?? ???? ???????? ? ?????????
??????. ?????????? ?????? ?? ???????? ???? ?????? ???
5 2 1
N + N -2
(3)
2
2
????????, ??? ???? ????? ????????? ?????? ???????
4 3
2
N + 2N 2 + N -1 .
(4)
3
3
??? ????????????? ??????? ????? ?????? ????? ???? ???????? ???? ?? ????????: ????? ?????????, ????? ?????????? ???????????, ????? ???????? ??????????? [1].
?????? ?? ???? ???????? ??????? ? ????????? ???????? ??????? ?? ?????,
?????????????? ?? ?????? ???????????. ??????? ????????? ???? ????????? ??
??? ????:
1) ???????????? ? ??????????? ?????????????? ????;
2) ??????? ?????????????? ???? ?????? ?????????? ????????;
3) ???????? ???, ?????????? ???? ?????? ????????? ????.
?????? ? ?????? ??? ??????????? ?????????? ?? ???? ??????????? ? ?? ??????? ??????????????? ???????, ?????? ??????? ?????????????? ???? ?????
??????????? ??? ????????????????? ????????, ??? ? ?????????????; ??? ??????? ????????, ??? ? ?????????????, ?? ? ????? ?????? ??????? ??????????????
???? ??????? ??????????????? ???????.
????? ????????? ??? ??????? ????????? ????
?????????? ?????????? ????????? ??????? ??????? ?????????????? ????
? ?????? ?????????. ????? ????????? ???????????? ? [2] ??? ??????????????
????????? ???? ? ???????????? ?????????????.
? ?????? ?????? ??????? A ? ??????? x ? b ??????????? ? ???? (5).
????????? ????????? ????????? ??????? ???? ???????????? ?? ???. 1. ????????? ??????????? ??????????????? ???????? ?? N p ????????? ? ??????, ???
p - ????? ???????????.
35
???????? ????
???????????? ??????
B1
צז x1 צ ז b1 צ
ז A1
ק
ק ח
קח
ח
C
A
B
קח x 2 ק ח b2 ק
ח 2
2
2
קח ... ק ח ... ק
ח
...
...
...
ק
ק=ח
קח
ח
(5)
קח ... ק ח ... ק
ח
...
...
...
ק
ק ח
קח
ח
C p -1 A p -1 B p -1 קח x p -1 ק ח b p -1 ק
ח
ח
Cp
A p קרחט x p קר חט b p קר
ט
?????????? ???????? ? ????????? ?????? ? ???????????? ??????????
47 3
5
(6)
N + 2N 2 - N .
6
6
? ?????????? ???????????? ???????? ??????? ? ????????? ??????????, ?????????????? ?? ???. 2.
???. 1. ????????? ????????? ????????? ??????? ????
???. 2. ????????? ???????????? ????
?????????? ???????????????? ??????? ??????? ?????????????? ????
??? ??????? ?????????????? ???? ????????? ????????? ??????:
·
???????????????? ????? LU ??????????;
·
???????????? ????? ??????? ??????????? ????????;
·
???????????? ????? ??????? ????????.
???????????????? ????? LU ?????????? ??????? ??????? ? ?????? ?????????? ?????????????? ??????? ???????. ??? ?????????? ????? ??????? ????? ????????? ??? ???????:
·
???? ??????? ??????? ?? ????? ?? ???????????, ??????? ??????? ???????????????? ???????, ???????? ??????? ?? ??? ??????????;
·
???? ??????? ??????? ?? ?????? ?? ???????????, ??????? ??????? ???????????????? ???????.
?????????? ??????? ??????? ??????????? ? ??????? ???? ???????????, ?????
??????, ???????? ???????????????? ???????? ?????????????? ????, ? ????? ?
????????????? ???????? ??????????? ??? ??????????? ?????? ?????????.
?????????? ??????? ??????? ??????????? ? ????????????? ?????? ???????
N
?????? ???????? N ´
?? ????? «?????? ? ??????».
p
????? ??????????? ???? ???????? ? ????????????? ??????? LU ???????????
???????? ????????????? ????????? ?????? ??? ?????????????? ??????? ???????.
????????????? ?????????? ????? ???? ??????????????? ?????? ?????????
??????? ?????????????? ????, ??????? ????? ????? ????? ??? ????????? ???????? ?????????????? ???????.
36
???????? ????
???????????? ??????
????????? ??????? ?????????????? ??????? ???????????????? ???????
LU-?????????? ????????
4
2
TLU (r , s, p ) = p � (Tsnd ( p � (r + s ))) + (r + s )3 + 2(r + s )2 + (r + s ) - 1 ,
(7)
3
3
??? Tsnd ( x ) ? ??????? ??????? ???????? x ????????? ??????.
???????????? ????? ??????? ??????????? ????????
???????????? ????? ??????? ??????????? ???????? ?????? ? [1]. ????? ??????????? ???????? ??????? ?? ????????????? ?????????? ?????????? ?? ?????????
??????? ? ????? ?????????? ??????? ? ????????????? ?????????, ??????? ????????
???????????? ???????????, ??????? ????? ?????????. ?????? ??????? ??????????
?????? ?????. ?? ???????? ???? ??????????? ?????????? ???????????.
?????? ??? ????????????? ??? ???????
= bi
+
C i x i -1 + Ai x i
Bi x i +1
= bi +1
C i +1 xi + Ai +1 xi +1 +
Bi +1 x i + 2
(8)
Ci + 2 x i +1 + Ai + 2 xi + 2 + Bi + 2 xi +3 = bi + 2
??????????? ?? ????????
BC
B C
CC
B B
C i*/ 2 = - i i +1 ; Ai*/ 2 = Ai +1 - i i +1 - i +1 i + 2 ; Bi*/ 2 = - i +1 i + 2 ;
(9)
Ai
Ai + 2
Ai
Ai + 2
Bi +1
C
bi*/ 2 =
bi + 2 + i +1 bi ;
Ai + 2
Ai
C i*/ 2 x i -1 + Ai*/ 2 x i +1 + Bi*/ 2 x i +3 = bi*/ 2 .
??????????? ?????????? ?????? ????????? ????????? ?????? ????????, ??????????? ?? ???. 3, ??? ?? ????????? ?????? ????????????? ?????????? ???????????? ????????? 1.8 ? ????
0 +
A*p / 2 x p / 2 + 0 = b *p / 2 ,
(10)
?????? ????? ??????????? x p / 2 .
?? ???????? ???? ????????? ???????? ???????????? ??? ?????????? ????????? ??????????? ????? ?? ?????? ????????.
???????? ?? ??, ??? ?????? ????? ????? ??????????? ???????????, ??? ?????????? ??? ??????? ?????????????? ??????? ? ?????? ????????? ????? ???????? ?
??????????????? ???????:
·
????????? ?????????? ?????? ????? ????????? ???????????? ? ???????? ?????????? ???????? ?????? ??? ??????? ??????????? ????????;
·
???????? ??????? ?? ???????? ??????????;
·
?????? ??????? ? ???????? ??????? ???????, ??? ?? ??????, ??? ? ??
???????? ???? ???????.
?????????? ?????? ?? ???? ???????????? ????????. ?? ???. 3 ????????? ????????? ????????? ?????????????? ??????? ?????? ?????????, ??????? ?????????? ?????? ??????? ??????? ??????????? ????????. ?? ???. 4 ???????? ???????
????????? ???????. ?????? ???? ??????????? ???????? ???????????? (r + s ) ,
?????????? ?????? p - 1 .
?? ???. 5 ???????? ????????????? ??????? ????? ????????????. ????????,
??? ??? ?????????? ?????? ??????? ??????????? ???????? ?? ????? ???????????
?????? ???? ???????????? ?????? ????? ?????? ? ???? (8).
37
???????? ????
???????????? ??????
?????????? ???????? ?????? ????????? ????????? ???? i ® i + 1 , i ® i - 1 ,
i ®i-2.
??? ??? ?? ?????? ?????????? ???????? ? ??????? ???? ????? ???????????
??? ??????, ?? ? ??????? ??????? ??????? ??????? ??????????? ???????? ?????
????????? ?????? p / 2 ???????????.
???. 3. ????????? ?????????? ??????????????
???????
???. 4. ??????? ????????? ??????????????
???????
???. 5. ????????? ????????????? ???????
????? ????????????
????????? ??????? ??????? ??????? ??????? ??????????? ???????? ???????????
????????????? ?????????? ??????? ? ?????? ???????? ? ????????? ?????????????:
(
)
T?. ???. (r , s, p ) = 2Tsnd + Tsnd (log 2 (1 + p ) - 1) 37(r + s )3 + 18(r + s )2 + 5(r + s ) - 1 . (11)
?????????? ?????? ??????????, ??? ?????????? ???????? ???????????? ?
?????? ????????? ?? ???? ??????????? ?????????? ??????????? ???????? ? ?????
?????????????? ??????? ? ??? ????????? ? ? ?????????? ?? ???????.
?????????? ?????????? ??????????? ????????? ???????????? ? ?????????
??????? ?????????????? ??????? ??? ????????? ????? (??. ???. 6, 7):
N = 1024, p = 16, r + s = 5;
N = 1536, p = 32, r + s = 5;
N = 2048, p = 64, r + s = 5;
???. 6. ?????????? ???? ???????????? ? ??????????? ????? ???????????
???. 7. ??????????? ??????? ??????? ?? ????? ???????????
38
???????? ????
???????????? ??????
???????????? ?????? ??????? ??????? ?????? ???????? ???? ???????????
?????? ???????????? ????? ??????????? ??? ??????? ????????????? ?????? ?????.
??????? ???????????? ????? ??????????? ??????? ? ?????? ????????????????
???????????? ?????????. ????? ?????? ???????? ??????? ?????????????? ????.
??????
?????? ????????????? ????????? ??????? ????????? ???? ?????? ????
??????? ??? ?????? ??????????????? ? ????? ????? ? ??????? ??????????????
????. ??????????? ??????????? ? ?????????? ?????????? ????????? ??????????
??? ??????? ?????????????? ???? ? ???????? ?????????? ???????? ???????
??????????? ???????? ? ?????????? ? ??????? ?????????????? ????.
????????????????? ??????
1.
2.
3.
Peter Arbenz, Walter Gander. A Survey of Direct Parallel Algorithms for Banded Linear
Systems.
J.J. Dongarra, A.H. Sameh. On some parallel banded linear system solvers. Parallel Computing, 1:223-235, 1984.
S. Bondeli. Divide and Conquer: A parallel algorithm for the solution of a tridiagonal linear
systems. Parallel Computing, 17:419, 1991.
?.?. ????????
?????????????? ????????????? ???? ????????????
??????? ? ???????? ????????? WINDOWS NT
? ????????? ????? ???????????? ?????? ????? ??????? ?????????? ??????????? ???????????? ???? ???????? ?????? ???????? ????????? ?????????????
?????????. ??????? ????? ?????? ?????? ???????? ????????? ??????????? ????????? ??????? ?????????????? ????????? ? ???????? ??????? ????? ????????? ?
???????. ??????????? ????????? ?????? ?????????? ? ??????? ???????????, ????????????? ? ?????? ????????? ???????, ? ?????? ????? ??????? ? ????? ????
??????????? ?? ????????, ??? ??????? ??????????? ?????????? ? ???????????
????????? ?? ????? ???????????.
???????? ???????? ??????? ???????? ?? ?????????? ? ???????? ????????
????????? ?????? ???????????? ????????? ? ????????????? ??????? ? ??????
?????? ???????. ????????? ???????? ????????????? ??????????, ????????? ??
???? ???????? ???? ? ??????????? ?????? ?? ????? ???????????? ???????????? ??
?????????????. ? ????? ?????? ????????????? ???????????? ???? ???????? ?????????? ? ???????????? ????????? ? ??????? ???????? ???? ?? ?? ???????????? ??????? ??????? ?? ??????? ???????????, ??? ??? ?????? ??????? ?????????
??? ????????????? ??????? ?????? ??????????.
???????????? ????????? ????????? ??????? ????????? ? ??????? ???????? ??
?????? ????????, ??????? ???????????? ??? ????????? ???? ??????????. ????????????, ??? ??? ????? ????? ??????? ????????? ???????, ??? ?????? ??????????
????? ??? ???????? ???????????? ??? ???????????. ???? ???? ?????? ????????????
?????????????? ???????????? ???? ? ??? ????? ?????? ??????? ???????? ?????????? ? ????????? ? ??????? ????????????, ??? ??????? ?????????? ???????? ???????
????? ?????????? ??? ?????????? ??????????, ??????? ???????????? ?????? ??????????? ???????????? ???? ????? ????????? ???????????? ??? ????? ????? ?????????????? ?????? ????????? ?????????? ?? ???????????? ???????? ????. ???
39
Документ
Категория
Без категории
Просмотров
3
Размер файла
667 Кб
Теги
анализа, эффективность, решение, уравнения, алгоритм, система, линейный, параллельное, ленточные
1/--страниц
Пожаловаться на содержимое документа