Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью
В роботi запропоновано метод перетворення послiдовних алгоритмiв моделей гiдродинамiки резервуарiв з вiльною поверхнею в паралельнi, використовуючи MPI та розбивку розрахункової областi на пiдобластi, перевагою якого є відносна простота реалізації, обумовлена потребою тільки у додаткових процедурах...
Saved in:
| Published in: | Математичні машини і системи |
|---|---|
| Date: | 2008 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем математичних машин і систем НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/46833 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью / А.А. Нестеров // Мат. машини і системи. — 2008. — № 4. — С. 154–170. — Бібліогр.: 21 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859474840651563008 |
|---|---|
| author | Нестеров, А.А. |
| author_facet | Нестеров, А.А. |
| citation_txt | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью / А.А. Нестеров // Мат. машини і системи. — 2008. — № 4. — С. 154–170. — Бібліогр.: 21 назв. — рос. |
| collection | DSpace DC |
| container_title | Математичні машини і системи |
| description | В роботi запропоновано метод перетворення послiдовних алгоритмiв моделей гiдродинамiки резервуарiв з вiльною поверхнею в паралельнi, використовуючи MPI та розбивку розрахункової областi на пiдобластi, перевагою якого є відносна простота реалізації, обумовлена потребою тільки у додаткових процедурах корекції замість значних перетворень існуючих програм послідовного розрахунку. Дослiджується вплив рiзноманiтних факторiв на ефективнiсть методу в термінах зменшення тривалості розрахунків зі збільшенням числа застосованих процесорів.
В работе предложен метод преобразования последовательных алгоритмов моделей гидродинамики резервуаров со свободной поверхностью в параллельные, используя MPI и разбивку расчётной области на подобласти, преимуществом метода является относительная простота реализации, обусловленная потребностью только в дополнительных процедурах коррекции вместо значительных преобразований существующих программ последовательного расчёта. Исследуется влияние различных факторов на эффективность метода в терминах уменьшения длительности параллельных расчётов с увеличением числа используемых процессоров.
This paper proposes a technique using MPI and domain decomposition to transform serial algorithms of numerical models for hydrodynamics simulations in the water reservoirs with free surface into parallel algorithms. The advantage of the proposed technique is a comparatively simple realization due to the necessity of only additional correction procedures instead of significant transformations of existing serial program code. The impacts of various factors on the method of efficiency are studied in terms of the speedup of computations with the increase of number of utilized processors.
|
| first_indexed | 2025-11-24T11:37:16Z |
| format | Article |
| fulltext |
154 © �������� � .� ., 2008
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
��� 004.9:504:519.6
� .� . ��������
���
�������
�� ��������
���
�
������� �
����
�
��
��
�
��
�� �� �� �����
��� ������������
Abstract: This paper proposes a technique using MPI and domain decomposition to transform serial algorithms of
numerical models for hydrodynamics simulations in the water reservoirs with free surface into parallel algorithms. The
advantage of the proposed technique is a comparatively simple realization due to the necessity of only additional
correction procedures instead of significant transformations of existing serial program code. The impacts of various
factors on the method of efficiency are studied in terms of the speedup of computations with the increase of number of
utilized processors.
Key words: hydrodynamics models of water reservoirs with free surface, parallel computations, MPI, domain
decomposition, POM, THREETOX.
�������� : � ����� i ������� �
� � ����
�����
��� � ���� i
�
�� �������� i
��
���� � i
��
� �� i��
�����
��� i
�
i�� �� ��
��� ��
�������� i,
��������
���� MPI �� �����
�� ������� ��
�� ������ i �
� i
������ i, ����
���� ����� �
�
�� � �������� ���������� , �����
�� � �������� ������ �
�
����
��
�����
���� �������� ������� � �� �� �����
��� � �� ����� ������� �����
�
��� ������� �� . ���� i
�������
���
� i� ��� i� �� ����� i
� � ����
i��� ����
�
����� �� ��� !� � ���
������ ������� ��
��
�����!� �� ����� �������
� �� ���������
.
���
� �
�
� : ��
��� ��
��
� �����
�
����" ��
��� �� ��
��� �� , �������� � �������
� � , MPI,
�������� ������� ��
�� ������� , POM, THREETOX.
��������� : � ������ ���
���� ����
���������
� �� �����
�
����� #� ���������
��
����
��
��
� ����� �����
����
�� �
���
�� ��
��� �����
��������� #� , ��������� MPI � �����
��
����$� �� ������� � ��
������� , ������"���
�� ����
� �
������ �� ������� �� ��������
���������� , ������
�� �� ������ ����� ������
���� ����� #� �����
���� ���������
�����
� ������� #� ���������
� �� ��"���
��"�� �������� �����
�
����� ��� ����$�� . %����
�����
��� �� ������ #� ������
� & ����
���� ����
�
����� �� ��� �!� ��
������ ����
��������� #� ����$��
� �
����� ��� ����� ����������#� ����������
.
���
�� �
�
� : ��
��� ��
��
� �����
�
�$��
�� �
���
�� ��
��� ����� , ��������� #�
#����� �� ,
MPI, �����
�� ����$� �� ������� , POM, THREETOX.
1. ��������
���������
������� ����� �
�������� �����
�����
� �
����
���
�
��������
�������� ���� ,
���
����
� �� �
� ����� ���!
�
�����" �
����
���
�
[1], ����#��� �� ���$�� «�������� »
%��������� �
����
���
�
, ���
� ��� %�������$ , ������
�
�������$ , �
«��%���
���$��� »:
���%���� �� , ��������$ , ���&�����&
���������� ����
& , ��������#'
� ��'����
�� �
�
�
�
�� -(
����
����
� %��������� , �%
�������� ������
��� -�
!! �
�����
������
��
�
�����
���
. )� ����
� �� ���� ������
� ����#��� ���
�����������
, � �����
� �
����� ��
��*�� (��$ ���(
�� �� %�����������$��� �����
� �����
�
��� ������
"
�
� %���
���� . �
%�
��� , ����
���� %�������
, �( ���������� ���%���� ��"
��������$# , %�
����� �
����
������
# (�����
���� �
� , %���*��#'
� &
�� ��&
# , ������� � ���# ������$ ��
��� ��
%������ ��%��
��������
. +����� (��$��� �
��� ���
�
��� �� � �� �� �� %���������
�������
�
������� ��������
� , ���(���
��� ��� �
�����
��&
������
" � ����� , ��� � '���� #�
(��$�
� ����
���� %��������� , %�
����� � %��
*��
# �������
�������� , ��� � ���(������
��%�
������ ��� %�������
����
� ������" .
��������
��&
� ���
����
" �������� ,!!���
���� ��������� ���$���
�
�
��
���$����
. -���� ���� , %������
� ����
*��
� � ����
�
���
��
���$��" ����
�
%�������#� ,
��� ��� %������
� %��
����
���$����
�%��$� ����
����� %�������
��&
� �� ����
����
������ ������ ���
���
� �������" ������� %��&������� : �� ��%�����
�
���� �&
" ����
����
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 155
�%���
���$���
(�����
������
���� *� %��&������ ��
�%��$�����
� ����" [2]. ������$�
����
� �����
�������� �� ���(����" %���������$# , ���
� ��� POM [3]
THREETOX [4], (��
������� � %�
�����
�� %�����������$��� �����
���� ������� , �� ��� ���$���
� ��
���$����
��������
���
���
� �
�������� ��������
� ����� ���(���
��
� ���%�������
���
� .
) ������'�� %�
�������� ������$�� «��������
" » %�������
��&
� ���(
��&
" ,
�
������� ��*�� �����
�$ ������
��&
# , OpenMP, MPI (Message Passing Interface)
PVM (Parallel
Virtual Machine). )�����
��&
� [2, 5] �����
��� � ��%�����
# ����"
��" *� �%���&
���
������$�
�
�%�������
������������ , ������ �� %�
�����
� �( �����
������ �%�&
!
����
�
�����*������
%��&������ , ��� � [5]. OpenMP [2]
�%��$� #��� ��� ������,!!���
���"
%�������
��&
�������� �� �
������ � �('�" %����$# , ����������� ������� �������� �������
���
����$ ���� � (���� ��� �� �� %��&�������
. .���#���
� ��������#� ������������
%��&������ , ��
� %��
����
���$����$ � '�������� �����
���� %��% ����" �%���(����$# �
��
������ . ) �� *� ����� MPI [6] ��*�� (��$ %�
����� ��� ��� �������� �� �
������ � ������$��"
%����$# , ���
��� �������� �� �����%��&��������
������������ �
������ , � ��(��$��"
���
��
���$��" ������� ��*�� (��$ ��(��� �� ������ �
�������� %��� %��&������� Intel
�
AMD, ����
������ ������� ���� �
������� . ��,��� MPI (�� ��(��� ������" ���
%�������
��&
�����
���� � �����" ��(��� .
+��
�
� ��
(���� �
������$��� ������� ���%�������
���
� �
������� �����
����
�����
� ������
" �
����
���
�
�������� ���(
���
������" ��������" �(����
�� %���(����
(Domain Decomposition). /���������$ �
������" ����
%� ���
������
� ������� ���!
�
�����"
�
����
���
�
�(���� ����
���$�� %�������� �
��� ����
���$��� ����� , � ���(���
����$
%�
�����
� ������� ���� ��� �
������" �%%����
��&
, ��%�
��� , �
!! �
����� ��������� �
����
���$��� ��%������
, %�
��(��$��� �
��� ����� %�
���
� � ���
������ ��% '��
# �
���(���
����
������
� ���� %��������� , �%
����#'
� ���
� *� ������ , ��
���
��
���$��� ��� � �('�" %����$# [7]. �� ,��" %�
�
�� ,!!���
���" �������� ���$��
���(
��� � ���
������$��� ��%������
�� . +�� %�
�������� �� ����
� �
������� �������
���!
�
�����" �
����
���
�
, ���
� ��� GESIMA [7], POLCOMS [8, 9], POP [10], TRISULA [11], �
���*� � %�������$��� ����
�� POM [12].
+��
�
� %�����"�
� �%���(�� ����
��&
������ ���(
��
��������" �(����
��
%���(����
�������� %�������
� %���(�����" � �(����� ���(���
��"
�!����&
�" �� ��*���
����
�����
�����
� %���� ��%�������������
���
����
��
, ��� �� '�������� � [10, 12].
.�%��$�����
� ������� �����
���� ������� %�
���
� � ���(���
����
�����
� �
���� �
��"���
������
" , ��%�
��� , ��� ����� [13, 14], � (��$��" �����*����" ����
&�" . ) ,��� �� ���
���(
��� �� %���(����
%�
���
� � ���������� #'�" ���(
��� ����
&� . ��
,��� %�
����#���
������
�����
������� 0���&� [11] ��� �
�������" %�������
��&
���
����"���
�
%���(�����" , � %�������$��" �����
�� ����� ����
��� ���
� �(����� , ���(� �� ����
��� �
�����
# %�����������$���� ������� � ��� �$����
����&
" . +����� �����������
%���� ���
������� �������� �� , ��� ��
%���%�����#� ����
���$� # ����� �� �
��&
# %�������� ������� ,
�������
� �%�&
��$��� ����
���� ����
" .
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
156
) �����" ��(��� %����������� ����� ������&
, %����� ����#'
"
�%��$�����
� ���$��
��%���
���$��� %��%������� , (�� ����
���$���
������
" � � '���� #'
� �����
����
%�����������$���� ������� .
���� %�
����� ��� %�������
��&
������� -���������" �����
,
�%��$� #'�" ����������� ����
[15] ��� � %�� ������� �����
���� ������� ����� %���������
[13, 14], ���
� ����� �����
���� [3]. ��� ������ � ��� �$���� %�������$���� ������� �����
�
��������
����
���� (� ����
��� ������
" %��������� � ���������� #'
� ���"��� ����
)
%�����������$��� ������ . ���
� '������ %�����*������ ������ �������� �� , ���
%�������
��&
� �����
� %�����������$��� �������� ��*�� (��$ ��%������ �����
���$��
(����� %� �������
# � �����(����" ����" �����
, � �%���� %�
������" ,!!���
�����$# ��
��������� , ������'
�
� ~10-20 %��&������� , � ���*� �� ���� � �('�" %����$#
������������
%��&������� .
2. !"�����# $%��&�
���� ������&
��� %�������
��&
�����
���� ������� ��������
������ ����� ��� �����
�
������
" , �%
����#'
� �
����
���
� ������ ���� �� ���(����" %���������$# �
�
�������
������ %�
(�
*��
- ��
����� , ��%�������� ������
��
%������� ��� ���%���� ��
��������
[3]. �������
� ��%
���� � ���������" �
����� �����
��� ),( yx %� ���
������
s -
�
����� �����
��� %� ����
���
( 0=s �� %���������
1-=s �� ��� ) [3]. �������
�
������������
���� �
�
0
=+++
ty
VD
x
UD
¶
h¶
s¶
w¶
¶
¶
¶
¶
, (1)
��� ),,( tyxhh = – ��������
� %���������
�� ������ '������ ����� , ( )yxHH ,= –
�� (
�� %�
������ '����" %���������
, h+= HD – %����� �� (
�� , w – %���(����������
”����
���$��� “ ���%������ ������� �������
[3], ��������� � &��$# ���������
���" !��� �
����
������
" . +����
���$�� ����� ��������
� 0rrr -=¢ ���$��" %�������
),,( PSTrr = (���
T – ���%���� �� , S – ��������$
P – ������
� ) �� ”����������" “ %�������
const=0r
�
����#��� � ������
�� ���
������ ��
*��
� % ��� ���'�%���
� �
�������
������� ������
�
� ¢¢=
0
)(
s
ssr dgDP �� (������%� #
(�����
�� # ��������#'
� [3]:
VisXBrcX F
U
D
fDVF
x
gD
U
y
DUV
x
DU
t
DU
+�
�
�
�
�
�+++-=+++
s¶
¶u
s¶
¶
¶
h¶
s¶
w¶
¶
¶
¶
¶
¶
¶
2
, (2)
VisYBrcY F
V
D
fDUF
y
gD
V
y
DV
x
DUV
t
DV
+�
�
�
�
�
�+-+-=+++
s¶
¶u
s¶
¶
¶
h¶
s¶
w¶
¶
¶
¶
¶
¶
¶
2
. (3)
-�����
���� ���%������ ������
� �����
����#��� ���
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 157
02
0
BrcX
gD D
F d
x D xs
¶ r r ¶ ¶ r
s
r ¶ ¶ ¶ s
¢ ¢ ¢� ¢= - -
�¢�
� ,
02
0
BrcY
gD D
F d
y D ys
¶ r r ¶ ¶ r
s
r ¶ ¶ ¶ s
¢ ¢ ¢�
¢= - -
�¢�
� , (4)
��� fV , fU – ���
��
���� ��������� , VisXF , VisYF – %����&
�
� �������
�
���
������$��� ��%������
, ������� ��%
����#��� � %�
(�
*����" ���������
���" !���� ,
�(���������" � [3]:
��
�
�
��
�
�
��
�
�
��
�
�
++�
�
�
�
�
�=
x
V
y
UHA
xx
U
HA
x
F h
hVisX
2
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
,
��
�
�
��
�
�
��
�
�
��
�
�
++��
�
�
��
�
�
=
x
V
y
UHA
yy
V
HA
y
F h
hVisY
2
¶
¶
¶
¶
¶
¶
¶
¶
¶
¶
. (5)
��,!!
&
��� �������
hA �%���������� %� !��� �� 1�����
������ :
222
2
1
��
�
�
��
�
�
+��
�
�
��
�
�
++�
�
�
�
�
�DD=
y
V
x
V
y
U
x
U
yxAh ¶
¶
¶
¶
¶
¶
¶
¶
a , (6)
��� a �������� %��������" ~0,2. 1
����� ������
" ��%�������� ������
��
%�������
��� ���%���� ��
��������
C :
.
��
�
�
��
�
�
¢+�
�
�
�
�
� ¢+�
�
�
�
�
� ¢
+=
=+++
y
C
HA
yx
C
HA
x
C
D
DS
C
y
DVC
x
DUC
t
DC
hhC ¶
¶
¶
¶
¶
¶
¶
¶
s¶
¶u
s¶
¶
s¶
w¶
¶
¶
¶
¶
¶
¶
(7)
��,!!
&
��� ����
���$��" �������
u
��,!!
&
��� �
!! �
u¢ � ����
���$���
��%������
�����
����#��� �������� e/k �����
� �( ��������
[16], � ������" %������
� �( ������" �
���
�����" ,����
k
�
��
%�&
e �%
�������� ������
��
, %���(���
(7).
�� ������� ����
&�� ����#��� ����
� %�
�
%��
� ��� ����
����
� ��%���
&������
��� ���%���� ��
��������
. �� �������� ����
&�� ����#��� �
(� ����
, �
(� ������� , � ���*�
������
� ���%���� ��
��������
. �����
��%��
�% �$�� ����� %���������$ �����
����#���
�����
� ����������
����
� ����
" ��� ��*��" %�
%�����������" ���"�
����
[4].
2�
���#���
�� (������%��� ��������#'
� ������
�
���������� ��������� �
����
���$��� ��%������
s , ��������� � ������
�� (2), (3) �%%����
�
�����
�$ � �����"
�����
�����
������
. 3���� �%%����
��&
� (������%��� ��������#'
� ������
�
�( �����
���� � '��������� �����
���
� �� ���
�����
�����
� %� ������
, � %�� ������� , ��� ,
��%�
��� , � [13, 14], %�
���
� � (��$��" �
����� �
��"��� ������
" . ��,��� � ��(���
����������� %�������
� %�������$��� �����
���� ��� ��� ������ ������ � ���(
��
�� �� ���
���������� ���� [3], ���
��� %�� �������� ������ [13]. 4�� ��� ���(
��� ��������" �(����
��
%���(����
�� '���������� � ���
������$��� ��%������
, �� %�������� ���$��"����
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
158
����������
� ( � � ��������� , �����*�'
� %��������������� %��
������� %� �����
����� x
y . �%%����
��&
�
�����
��� ������� � ��%������
s ����#��� ���
�
*� , ��� %�
%�����������$��� ������� . ����� ���*� %��������� , ��� �
�����
��&
� ����
���� ����
"
����
%������ �%%����
��&
�� ���� , ��� ���
� ������
" .
3. �"!"&&�&�'"(�# "&)%!�*$%� !"+,-*" #��./ +&")"�$./
1 �$ ������ ������&
����#������ � ��� , ��� �� %����� ,��%� ��*���� ����
�����
�����
�
%���%��������� ���
�
� !
��
���" ������" ����
&� ��*� %���(������
, ��� %��������
�%��$�����$ ����
���� ����
� , ���"�������� ��� �����
, � %����� #'�" ������&
�" �� ������
,��%� . /�������
� %�����"�
" %�
��� ���������" ������
���" ����� 1-�� %������ ����� %�
%���� [15] � �
���� � ����� , ������ ��
�
&� . ) ,��� �� ��� %�����������$��" �����
��
%��'����� :
n
i
n
i CC 1
1
-
+ = , mi ,...,1 = , )(*
1
1 tCCn =+ ,
��� )(* tC – ����
���� ����
� , �������� �� ����" ����
&� , m– �
��� ���� ����
.
/�����
� ��%��$ ��# ������� # �(����$ �� ��� %���(����
. � ��$ iC ,1 ),...,1 ( 1mi =
iC ,2 ),...,1( 2mi = – ������
� ������� � ���� ����"
%����" %���(�����" , �������������� ,
mmm =+ 21 . �� %����� ,��%� �����
��� ��� %����" %���(����
( ��� %���%������$ !
��
����
����
���� ����
� , ��%�
��� , 01 ,2 =C , ��� ���� �����*����$ ���(
�$ �����
�� �� ���
�����
�
��� :
��
�
�
�
=
==
+
-
+
)(
,...,1 ,
*
1
1,1
11,1
1
,1
tCC
miCC
n
n
i
n
i
,
��
�
�
�
=
==
+
-
+
0
,...,1 ,
1
1,2
21,2
1
,2
n
n
i
n
i
C
miCC
.
����� %������ ,��%� ������
� 1 ,2C �������� ��%���
�$��� . +�� ���������� ������
��
�
����" %���(����
�� ������ ,��%� (,��%� ������&
) %�������$���� �����
��� , ������" ��*��
(��$ ����
����� � %�
�����
�� %��&�� � %�������
������ MPI, ����� ��� MPI_SEND, MPI_
RECV [6]:
1 ,11 ,2 mCC = .
����� ������&
%�����������$��"
%�������$��" �����
��� ��#�
����
���� �����
�
�� ��*��� ���� %� ������
. ���
� '������ ������ %������ �������� �� , ��� �� %����� ,��%�
������� ��� ��*��" %���(����
%�
�������� ��� *� %�����������$��" �����
�� , ���
���
������" �(����
.
������� �
������" �%%����
��&
%� %���������� ���
�
� �� �
��� ���� , ����� #'
� �
��(���� ����� . 1������������� , �
��� ���� , � ������� ������
� ���*�� (��$ ���������
������
%���� %������ ,��%� , ���
�
� �� %������ �%%����
��&
. /�������
� TVD-����� �����&
[17, 18],
��#'
� !�����$�� 2-" %������ �%%����
��&
%� %���������� , ��� ����������� �� ���
������
� %������� (7), �%
�������� �����
����
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 159
RRRLLL
n
i
n
i
n
i
n
i C
x
t
DUC
x
t
DUDCDC
D
D
-
D
D
+=++ 11 , (8)
��� LU , RU – �������$ �� ����"
%����" ������ �
������" ���"�
, LD , LC , RD , RC –
�� (
��
������
� ������� �� ����"
%����" ������ �������������� , n – ��� %� ������
(
������ n
i ��� D
C % '��� � &��$# �����'��
� �������� ). /���
���� �����
���
��#��� ����
���� �%�������
�� LC , RC . ��%�
��� , � ����� &������$��� ��������"
( )n
i
n
iR CCC 12
1
++= [15]. TVD-����� ��� � (��$ %����������� , ��� � [18]:
( )
( )
1
1 1
1
, 0, ��� ( )(1 ) ,
2
1
, 0, ��� ( )(1 ) .
2
n n n
R R R i i i i
R
n n n
R R R i i i i
C U C C r c C C
C
C U C C r c C C
y
y
+ + +
+
- - -
+ +
� ³ = + - -��
= �
� < = - + -
��
(9)
2���$ c – �����$��� �
��� � ����� �� ������ , ir – �������
� ����
���� ������� ����� %�
%���� � �����$��� ����
��� :
x
t
Uc R
D
D
= ,
n
i
n
i
n
i
n
i
i CC
CC
r
-
-
=
+
-+
1
1 ,
n
i
n
i
n
i
n
i
i CC
CC
r
-
-
=
+
++-
1
12 . (10)
.� (8)–(10) ���� �� , ��� �� ������
� 1+n
iC ��� � ��������$ ��
��
�
n
iC 2- , n
iC 1- , n
iC , n
iC 1+ , n
iC 2+ , � ���
�
����
�� ��%������
� %�����
! ��&
y , �������
TVD-�����
���
��#��� �� � �� �� �� [18].
�� �
� . 1 %������� ���(
���
������" ��������" �(����
, ����
���
� (%�������
� )
%���(�����"
%��&�� �� ������&
��� ���� 2-�� %������ �%%����
��&
. /���
���
�
%���(�����" � �(� ������� ���(���
��
� -�� ���� , ��� %���� ��*��
���$ ����
���� ��%������
� .
�� ,��" *� %�
�
�� %��&�� �� ������&
�������� �
�����
���" �������� �� �� , ���
��������
������ TVD-�����
�%��$� #�
�!����&
# ���$�� � ������ ��� ��
� %� %���� ,
���
����
���� ������&
� (��� (� (���� ,!!���
���" . ) %���
���� �� ��� , ���
�������$ %�����
(�
��� � � �# , �� �
������" � � , ��������" ��
(���
��� ����
� �� �� � ����
����
%��&������� , ��� (� %�
���
�$ � �� ���"�
����
����� �(���� . 1
�����
���" *� �(���
�!����&
�" %�������� �� ��*��� ���� ��� ���
�
����
�� ��%������
� �������
. 4�� ���
�(� *������ �����$
�%��$� �� ����������� ����
[15], �� ��� ���� , ���(�
�%��$�����$ ���
�� *� %��%�������� �(���� ��� ���%����� �������
��� ������� , ��(��� �������� �����
%�������
� %���(�����" �� ��
� ��%���
���$��" ���" . ��� %������ �
������" ,��%��
���� ,
%����� %��
����
���$����
%�
,��� ��� '�������� .
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
160
/
� . 1. /��(
��� ��������" �(����
%��&�� �� ������&
/�������
� ��%��$ ���� �
!! �
������� ��� (7), ������� � 1-�� �� ��� %�
�
���� �
�
��
�
�
��
�
�
D
-
-
D
-
D
»�
�
�
�
�
� -
--
+
++ x
CC
HA
x
CC
HA
xx
C
HA
x
n
i
n
i
i
n
ih
n
i
n
i
i
n
ihh
1
2/1 2/1
1
2/1 2/1
1
¶
¶
¶
¶
. (11)
4�� ��� (11)
�%��$� �� ����� ��
� ��� ����� %� %����
��
� ��
� %� %���� , �� �����
������&
, %������������� �� �
� . 1, �������� ����������" , ���(� �����
�$ ��
(����� ������
� ,
�( ���������� !
��
����
����
����
����
��
��*� %���(������
�� %����� ,��%� .
/����� hA %��
����
��� %� !��� �� (6), ������� ���#���� ���
����
� %��
������� �
���
������$��� ��%������
. ��,��� %�
�����
� %��&�� �� ������&
� ������
# (7) (����
,!!���
��� %���� ���� , ��� ��� ������
����
�
!! �
����� ��������� ���
�����
���*��� ,
��� %�-�����$����
.
�%%����
��&
� %�������
�% �$�� � (2), (3) ��*�� (��$ ��%������ �
�%��$�����
��
����� &������$��� ��������" [15]
�
TVD-���� [19], � ���������� ��������� (5) – ������
���
�
!! �
������� . �������
� (2), (3) ���*� �����*�� ��������� BrcXF , BrcYF , ���
�������
�������� (4). 5��
%������
� �%%����
��&
�� ���� 2-�� , �� %��&�� �� ������&
��*�� (��$
%�
������ � (2)
(3) %���� ���� , ��� ��� %���� ��� ��������� ���
�����
���*��� .
1���� ������&
��� �� �������
���������� ������
" ������
��� . �� �
� . 2 %�������
%�
��� ��������
� ��������" �(����
�� 4 %���(����
� %�������
� . ) ���������� �� ���
�
� . 2 �������� ”�
��� ����� “ �� %�������
� ���������� %���(�����" ; ��*��� %��������� ���"��
���������� �� ����
���$��� ����( ���� . 4� ���"�
1-" %���(����
, ������
� � ������� ���*��
(��$ �������� %���� %������ ,��%� , ���%���*��� ��*� ����
&�" %���(����
%���� ����
���
�
(�������� �����" *
���" �
�
�" )
����
&�" %���(����
�� �� ����
���
� (�������� (���� ).
6�� ����$ 1-" %���(����
%������������ � ”�� �����
�
“ ������
�����$��� %���(�����" , ���
������
� %��������� �� ”
�%������ “ %���� %������ ,��%� . +�
�%��$� #��� ��� ������&
������
" 1-" %���(����
�� ������ ,��%� ������� . 4�� ��� ������&
� ���*�� �� '�������$�� ���
���� %���(�����" , �� %�
�����
� %��&�� � %�������� MPI_ISEND
MPI_IRECV [6] (���� ��(�� ,
��� %�
�����
� MPI_SEND
MPI_RECV, ������� %����� ������ ����� # %�����������$����$
%�����
%�
��� ������ , � �� ����� ��� MPI_ISEND
MPI_IRECV ��� � %������$
%�
�
���$
������ � %��
����$��� %������ , �� ��*
����$ ��������
� %�������� . +*
���
� ��������
�
�(���� ������
�(��(���� �����*��� ��
(�� �� '������#��� %��*� , ��%�
��� , � %���'$#
%��&�� �� MPI_WAITALL.
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 161
/
� . 2. /��(
���
������" �� ������" (���������" ) �(����
�� 4 %���(����
+%�
�
��&
� ���(
��
� �� �������
���������� �� ���� �� �������� ��
�
��$��"
������" . ���
�
� «� �
� » ����� %�
���
� � ������ � ����
�
��&
��������� %���(�����" %�
�
�
�
��&
��
��
� ����
& , ������� ��*�� �����$�� , ��� � [8, 9]. ) �����" ��(���
«%�
(�
*��
� » �%�
���$��" ���(
��
�%���������$ ���
� �(����� , ���(� �
��� �����
%���(����
(��� %��%��&
����$��� %��
����
���$����
���������� #'��� %��&������ , ��
������� %��
����
��� ������ ,��" %���(����
. +����� ��� ���(�������" �������� ��*��
%���
��$ �� �%�
���$� # ���(
�� . ����� ���� , %��&�� �� ���
����
�
�����
��� , %������
�% �$��
��%�� ����� %���������$ [4] ��� �
���$ ����
�� # ��
���$����$ ��*� ���
%���(�����" ,
��#'
� ��
������� �
��� ����� .
4. �"+,-* 0"!%*!%1�./ +&")"�$./ � 2!%��#
����� ����������� ���� #'
� ������ ������� (������%��� ���������
����� :
1) ����" ����� : ���'�%���
� ������� �� �� �����## (�������� # )
�����##
(�� ����� # ) ���� � %����� #'
�
� ��%��*��
�� [3]
2) %�� ������" ����� : ������
� �
����� ������
" � ����" �
����� �
��"��� ������
"
��� ����� %���������
1
,
+n
jih , ��� �%
���� ��� 2-�� �� ��� � [13],
��� 3-�� – � [14].
) %�����
� ,�
� ������� %���%��������� , ���
xx
n
ji
n
ji
D
-
»
¶
¶ - ,1, hhh
,
yy
n
ji
n
ji
D
-
»
¶
¶ - 1,, hhh
–
����� �%%����
��&
� 2-�� %������ � ����������� ������ ��� ���
����
� (������%��� ��������� .
����
���
� %��
����
���$����
���������" �����
����
������ ��� , ��� �����
���
� �� ���
�����
�����
� %� ������
, ��������� � �������� �
���� � ����� , %�
�������� ���$�� �
�� ������" ���� . ��
,��� �����
��
�����
�����
� �� ������" ���� �������� ������
����
�� ������" �����
�
����
���
�
� �������� (������%��� �
� %� ����" ����� . ���
%�������
��&
�����
��� ������� ��*��" ���
�����
�����
� ��� ���������" , ���
�� ������"
���� , �����
�
� �� � ,��%�� : �� %����� %��
����
��� ������ �
�%��$�����
�� !
��
����
����
���� ����
" ; �� ������ %�
�������� %��&�� �� ������&
. ������&
� ���������" ����
�� '���������� %���� %��&�� �� ”����"�
“ ��� .
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
162
���� %�� �������� ������� �����
(������%��� ��������� �������� �
(� (�� ������
���"�
��� , �
(� � (���� ���(�� �����
���
�� �� ���
�����
�����
� . ��%�
��� , ���
%�������
�$
xxx
n
ji
n
ji
n
ji
n
ji
D
-
-+
D
-
»
¶
¶ -
+
-
+
,1,
1
,1
1
, )1(
hh
q
hh
q
h
� %��������� ]1,0(Îq . +����� �� %�
���
�
� ���(���
����
�����
� (��$��" �
����� �
��"��� ������
" � %���*
���$�� �%���������"
����
&�" , ��� ���� ����� %�
����#��� ������
�����
������� ��%��*����� ����
�����
��
�����"���� �% ��� [20]. /�������
� �� ����� # �����$ [13] � 1=q . �������
�
������������
(1) �
�����
�
� ���� ���
0,
1
,
1
2/1,
1
,
1
2/1,
1
1,
1
,2/1
1
,
1
,2/1
1
,1 =
D
-
+
D
-
+
D
- ++
-
++
+
+
+
+
-
++
+
+
+
ty
DUDV
x
DUDU n
ji
n
ji
n
ji
n
ji
n
ji
n
ji
n
ji
n
ji
n
ji
n
ji hh
, (12)
���
2
1
,
1
,11
,2/1
++
-+
-
+
=
n
ji
n
jin
ji
DD
D
� .� .
�
�����
��&
� ������
� (2), ������������ %� �� (
�� ,
���� �
�
1 1 1 1
, 1/ 2, , 1/ 2, , 1, 1 1
1/ 2, 1/ 2, 1/ 2, ,
����� �
�
����
. . .
n n n n n n
i j i j i j i j i j i jn n n n
i j i j i j i j
U D U D
gD D U
t x
h h
l
+ + + +
- - - + +
- - -
- -
= - - +
D D ������� .
1
�� ����
� ��� (� ��,!!
&
����� n
ji ,2/1-l , [13]) ���*� �
�����
�
� #��� %�� ������ .
+����$��� % '����� ��������� �����
����#��� %� ����� ������ . ������
���� �
��������
������
� ������������ ��� (3). )���*��
� ,�
� ������
" ��������� �
�� 1
,2/1
1
,
+
-
+ n
ji
n
ji DU ���
�
��"��� ! ��&
��
�������� 1
,
+n
jih , 1
,1
+
-
n
jih , 1
,1
+
+
n
jih , 1
1,
+
-
n
jih , 1
1,
+
+
n
jih
%��������� � (12), %�� ����
������
� ��� h :
n 1 n 1 n 1 n 1 n 1
0 , , 1 , 1, 2 , 1, 3 , , 1 4 , , 1 ,
����� �
�
����
. . .n n n n n n
i j i j i j i j i j i j i j i j i j i j i ja a a a ah h h h h h+ + + + +
- + - +- - - - = + ������� , (13)
n
, 4
n
, 3
n
, 2
n
, 1
n
, 0 1 jijijijiji aaaaa ++++= , n
ji
n
ji
ji
D
x
t
ga
,2/1
,2/1
2
2
n
, ,21 1 ±
±
+D
D
=
l
,
n
ji
n
ji
ji
D
x
t
ga
2/1,
2/1,
2
2
n
, ,43 1 ±
±
+D
D
=
l
. (14)
��(�� ,�
� ������
" ��� ��*��" ���"�
),( ji ������ � ����
����
����
��
�(��� ��
�
���� �
��"��� ������
" � 5-�
������$��" ����
&�" A. ) ���������� �� ��� ����� �
�����
�
��"��� ������
" ��� h %����(�� �%
��� � [14]. ��
���(
��� ��������" �(����
��
%���(����
����
����
&� A �� %����� ,��%� ���
���#��� �����
�
�� %�������$���
%��&�����
�������� (14)
�������� � %����
���������� #'
� ���
��
���$��� ���� ��� 5
%���������� . 4� ,������� ����
&� A , ������� ���
��� �� !
��
���� ����
���� ����
" ,
����#��� ��
(�����
%���� %������ ,��%� , ���
�����$
�������
�� (��
���������
������
%������
���$�� . ) ,��� �� ��� ���(���
�� %�
�����
� %��&�� �� ������&
, %���(��"
%��&�� �� ������&
��� ������
" (2), (3).
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 163
/�������
� %�������
� %�������$���� �����
��� ��� �����
� �
����� �
��"���
������
"
bxA
��
= (15)
�� ������ ������ ��
�����"���� �% ��� [20], %���%������ , ��� ����
����
&� A
�������� x
�
,
b
�
���
���#��� ����
����
%��&�������
. /����
� (15) �����
��� � ��� �$����
����&
"
bxA nn
���
-=w ,
( )
( )nn
nn
n A ww
ww
��
��
,
,
=D , n
n
nn xx w
���
D-=+1 . (16)
�����$��� %�
(�
*��
� �����
� 0x
�
��*�� (��$ ����� � %����� '��� ����
�����
�����
� . �����
�� (16) ���( �� ���
����
� �� � ��������� %��
������
" ��������
������ %��
������
� ����
&� �� ������ �� ��*��"
����&
. 4�� ��� %��������� �������� �
%����
����
���� ���
��
���$��� ���� , �� �%���&
� ���
����
� ���������� %��
������
�
�������� x
�
y
�
��*�� (��$ %����������� ��� � ��� ��������� %��
������
" %���������� ,
���
������� �����
�
�� :
),(),(),(),( 2211 mm yxyxyxyxp
��
�
������
+++== ,
��� m – �
��� %���(�����" , 1x
�
1y
�
– ���������� #'
� %��������� . )��
����
� %����"
� ��� p � �����" ��(��� �� '���������$ %�
%���'
MPI ! ��&
" MPI_REDUCE
MPI_BROADCAST [6]. ��������� ���(���
�� ��� %������
p ���� %��&����� . ��
�%��$�����
�������� ���� �
������ 1 7(
� , ����
��#'��� ��� ��� � %��&�������
Intel P4
377&, ��� %�����
%�
��� ������ �
��� ���( ���� ~130 ��� , ��� ,��
�������� ��%�����
# ~500
�%���&
" ���*��
� ���
� *� %��&������� , � .� .
�%��$�����
� MPI ��,!!���
��� ��� �������� ,
������'
� ����� ���
� 1000 ,�������� .
��*��" ��� ����
&� A �����*
� ��
�
%���*
���$��" ,������ �� ������" �
������
4
���
&����$��� ,������� , ���%���*����� �� ����
����
�
�������� � ���
�
����
�� ��������" �(����
, � �� �����
��� �����$��� ,������� ����� � �# . ��
%������*��
k -
�� ���� ����
&� �� ������ ,�
5 ,�������� %������*�#��� �
,��������
������� , ���������� #'
� ���"��� ),( ji ,
),1( ji - , ),1( ji + , )1,( -ji , )1,( +ji . ��� �%���&
���*��
� ����
&� �� ������ ��(�� �����
������&
# ���������� #'
� ,�������� )(0 kP , )(1 kP , )(2 kP , )(3 kP , )(4 kP , ��� %������� ��
�
� . 3.
4���� �%���&
� ���*��
� xAx
��
=* %�,�������� %�
�
���� �
�
)( 4)( 3)( 2)( 1 0
*
4321 kPkkPkkPkkPkkkk xaxaxaxaxax ++++= , (17)
/
� . 3. .������&
� ����� ����
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
164
��� *
kx
kx – ,������� �������� *x
�
x
�
�������������� . ��
,��� kkP =)(0 ,
kkPP =))(( 21 , kkPP =))(( 12 , kkPP =))(( 43 , kkPP =))(( 34 , ��� ��*��
�%��$�����$�� ���
%������
�����
��� .
8��(� � ��� �$���� %�������$����
%�����������$���� �������� %�� �
�$ ��
�������
�����
� , ���(���
�� �(��%��
�$
����
�����$ �������� , %�� ������ � ��� �$���� %�������$����
%�����������$���� �������� �� ��*��� ����
����&
" (16). 5��
,������ kx ���������� ��
���"�� ����
, %�
����#'�" � %���������
��������
� ��������" �(����
, �� �� %����� ,��%�
��*��"
����&
*
kx ���
������� �������� (17),
�%��$� � !
��
���� ������
� . 5��
�(�����
�$
W – %�����*����� ,�������� ),( ji � ����� ������&
��� �����&
������� 1-�� %������
),( jiMk = – ��������� # �����!����&
# %��� ),( ji � ��������"
����� k , �� %�����*�����
,�������� )),(( jiMk W= ������� *x
�
���*�� (��$ ����'��� �� ,��%� ������&
. ������$� W
�������� %�����*������ ,�������� , ������� �������
� #��� %�
�%��$�����
���� %������� 2-
��
(���� �������� %������� , �� *� ����� %��&�� �� ������&
��� � (��$
�%��$������ , ���
��� ������� . ��� %������ �
������" ,��%��
���� , %����� %��
����
���$����
�� ����
”(��%������� “ ���*��
" ������
���$�� , ���
%���(����
���������� ���
�
.
/
� . 4. ����*��
� ����
&� �� ������ ��� %���� ���$��" %���(����
/
� . 4 %������� �%���&
# ���*��
� ����
&� �� ������ ��� %���� ���$��" ��������"
�(����
. )��������� %���(����$ �����
�
� ������&��
,�������� , ������
� ������� (1, 2, 3, 4)
��������� ����" ����
&�
������ (9, 10, 11, 12) – %����" . ����� %������ ,��%� ���*��
�
����
����
&� (��������� ) �� ����$ ������� , ������� ���������� #� ��������
�����"
%���(����
, ,������� ( *
1x , *
2x , *
3x , *
4x )
( *
9x , *
10x , *
11x , *
12x ) ����#��� ��
(�����
. �� ������ ,��%�
,�
,������� ������#��� ,��������
� �� �����
� �����" ���������� #'
� ������
�
%���(�����" .
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 165
1
�����
��&
� %�������$��� %��&�����
�(��� ������
, ������� �� '������#��� ��
��*��"
����&
(16), ���*� %�
����� � %����� %��
����
���$����
. 8
���
����&
" , ���
��'�� ��
�������
����
����
, *������" �������
�����$���� %�
(�
*��
� , ��*�� (��$ � '��������
���$���� %�
�����
�� %����( �����
������ – ����" ���
�� �����" ����
&� C, �������
%���(��� ��
����� # �
���� ������
" (15) � ,��
������� # �
���� � � ������"
����
����$# :
*** bxA
��
= , (18)
��� 11* --= ACCA , xCx
��
=* , bCb
��
1* -= . 4���� %���(�������
� ���( �� ���
����
� *b
�
*A , ��� ����������� �%���������� �����
���
� �� ���"���� C : �����
� ������
� bbC
��
=* ��
���*�� (��$ �� �����
� ; ����
&� *A �� ���*�� �����*��$ (��$���� �
��� ��� �����
,�������� ; ���
����
� ���*�� %��� �����
���$ %�������
��&
# . ������"�
" �
������$��"
%����( �����
�����$ [21], ,������� �������� �����
����#��� ���
��
�
�
�
¹
=
=
, ,0
, ,
ji
jia
c ji
ji (19)
������������ ,�
� ���(����
�� . ��
,��� i
ii
i b
a
b
* 1
= , *
1
i
ii
i x
a
x = ��� � ���
����$��
�����
�
���
%�������$���
%��&�����
. ��
�
��� �� ��
���
� �� , ��� ��*��" ��� k ����
&�
A
���� 5 ��� ����� ,�������� , ���%���*����� � �������� kkP =)(0 , )(1 kP , )(2 kP ,
)(3 kP , )(4 kP , ����� �
���$ , ��� *A
���� ��� ����� ,������� �� ��� *� ����� ������ , ���
����
&� A :
)( )(
)(*
)(
kPkPkk
kkP
kkP
ii
i
i cc
a
a = , 4,3,2,1,0=i )1( *
º� kka . (20)
5��
��� k ����
&� *A ���������� �� ,������ ����
, %�
����#'�� � %���������
��������
� %���(�����" , �� �� ,������� ,���� ���� , ������� ���
��� �� !
��
���� ,)( )( kPkP ii
c
���*�� (��$ �������� % ��� %�
�����
� ��� *� ����� %��&�� � ������&
, ��� %�
���
����
����
&� A . �
������$��" %����( �����
�����$
���� ���� #'
� %��
� '����� : ����
&� *A
���� � *� ��� �� � , ���
A ; ��� � %�
�����$�� �� *� %��&�� �� ���*��
� ����
&� ��
������ , ���
��� A ; C �� ���( �� ����� %����
; %��&�� �� ������&
��� ������
� %�������
������� ��*�� (��$
�%��$������ ��� ������&
C , *b
�
, *A ; �
��� ���(���
��� ���*��
"
���$������ �� 20%, ��� ��� 1*
ºkka ; �����*�� %�
�����
� SIMD (Single Instruction Multiple Data)
���� �&
" %��&������ [2].
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
166
5. �!%��!3" $�*%�"
���� ������&
%��������� % ��� �������
� ��� �$����� �����
(�� ���(
��
� ���(
���" ��
%���(����
. ) �������� %�
���� ����� %������� �(�������
� �
�����" ����*�
������� %����
%��%�����
� � %����� : �� -%����� , �����
���$�� ���*��� ��� �� �� %����� ����
� ���� %�
%�����"
�������
������� ����
& , � ��� �$���� ���� %���� ��*�� %��������$ ����
&� %���(�����" �
����
���� ��%������
�� ; �� -������ , %���� �������� �� ���"�
��� , ��� %�
���
� � � '���������
���
�
�� � �
����
���
����
� %���� ��*� %�
����� ���� '��
�� �� ������ %���(�����" .
4����
� � ������ %��������" �� (
�� 10� � %��%�����
�� , ���%���*����� � &�����
������ %��%���
� ����� ��� ��
, �����
�������$ %�
%���'
�� ������" �����
. ����� (��
%����� �����" 520� 33 ����� � ��������
�� 10� . 1 &��$# ���$���
� �
��
%�&
,����
��,!!
&
��� ���
������$��" �������
�����
������� �������� (6) � 0,02a = , � ������������$
��� %��������$ 5
0 103 -´=z � . �� �� � �������� ����
&�� �������
�$ ����
12,5± �� .
�����$��� ����
� %������
�$ � �����
��� ��� �������
, ���
��� ����� . C &��$#
�(�*��
�
�(�������
� ” �����" “ ����� �����$ %�����
�������� �� ����
&�� � �����
� 0,5 ��� %����
������ ������� , %���� ���� ��������� %��������� . ��������$��" ������ %�����
��� � ���(
���"
�� 4 %���(����
, �������
���
�(' # �(����$ %�������
� %����
%��%�����
� – ���� , � ������"
�����$ ��
(���� � ����
���$�� � ��������*��� ���� '��
�� .
/
� . 5. +(�������
� �
�����" ����*�
������� %����
%��%�����
� . �� �
*��� �
� ��� %������
������ �������
��� ��*��" ���"�
�
������" ����
�� �
� . 5 %������� %��� �������
�� ������ ������
5,1=t ��� %���� ������ ��������
%���� «����"�
» 4-� %���(�����" . �� ������� �
� ��� %������� �('�� ����
�� �����
� , �� �
*���
– %��� �������
�(�
�
%��%�����
� � �������� �������
��� ��*��" ���"�
����
. ��� %�������
�������
� , %�
���
����
�� � ���"��" �������$# ��� �$��� ��������
����
���� %�� ������
(�� ��������
� �� %���(����
� ����
��� ������
" %��������� � ���������� #'
� ���"���
�
������� ����� ���
������" �(����
%���(�����" .
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 167
6. �!%�'�%��*�&4�%+*4
9
�
������ ����� realT , ����������� �� ��%�����
� ������� , ���
�
� �� ��
���$����
�����
� �����
�������� ������
simT , �� ����
�����
�����
� %� ������
tD (������" ��*��
������$�� �� %����*��
��������
���
�
� �� ���������� �
������� ���� )
�� �
��� �%���&
" ,
%��
����
��� %��&������� �� ��
�
& !
�
������� ������
. ��,��� � ������ �����" ��(���
%�� ����
��� %��
����
���$����
P ( ��� %����� �����$ �������
� �
��� �����
�����
�����
� Tn (���
constt =D , �� tTn simT D= ), ���(���
���� ���
�����
�����
�
�
����� ������
" �� 0=t �� simTt = , � !
�
������ ������
realT , ����������� �� ������ :
realT TnP = .
���
� ���
� %��
����
���$����
%�������$��� ���
����
" � %�
�����
�� ������
������&
��� �� ������" �����
(��� %�������� 4 �������� ������� � �
�������
������
����
���� �������� : 520x50, 1040x50, 520x100, 1040x100 ���� , %������#'
� %��'��
52 �� x
5 �� , 104 �� x 5 �� , 52 �� x 10 �� , 104 �� x 10 �� �������������� . -��
����
������ �� (
�� �� ����
�� ���� (��� 10� . �� ����" �������" ����
&� ���������$ �
� ��
���$��� ��������
� �����
%���������
�� ������ '������ � ��%�
� ��" 2�
%��
���� 0,5 ��� . ��� ������� �����
%���������
�%��$�������$ %�� ������� ����� . 4��� %�����
��� �� �������� , ������'��
�
�� �%��&�������� ���� AMD Opteron 248 2,2 77&. -��� %������
�
������ ��� �%���(� ���(
��
������" ��������" �(����
�� ����� ,����� %���(����
, �(���������� ��� ”� “
”- “ �� �
� . 6.
/
� . 6. 1%���(� ���(
��
�� ����� ,����� %���(����
� %���������� ,��%��
������
) �� ��� ���(
��
”- “ ��� ������
� %���(����
� (���� ��
���" �('�" ����
&�"
�����
�����
�$ �� �����
��� *� ��� �������� � �('�" %����$# . 4���� %�����
�
�$ %��
%������
�� �%���&
����" �
����� ”Windows XP“. ��%���
���$�� (��
%������
�
������ ���
�%���(� ��%�����
� %��&����� �
�����" : � %�
�����" %��&���� � !
��
�������� %��&�����
(”9 “)
� �����*����$# %��
����$���� ��(��� %��&������ �%���&
����" �
�����" (”� “).
4�(�
&� 1. ����
���
� %��
����
���$����
, ���
��� !
� . 520x50 1040x50 520x100 1040x100
9 � 9 � 9 � 9 �
1(1)A 1 0,93 1 0,94 1 0,93 1 0,95
2(1)A 2,16 1,46 1,92 1,42 2,02 1,47 2,02 1,54
2(1)- 1,85 1,19 1,73 1,3 1,92 1,37 1,95 1,54
2(2)A 1,95 1,95 1,87 1,82 1,91 1,87 1,96 2,03
2(2)- 1,62 1,59 1,62 1,58 1,78 1,73 1,89 1,91
3(2)A 2,86 2,06 2,86 2,38 2,86 2,32 3,11 2,63
3(3)A 2,86 2,75 2,85 2,83 2,84 2,78 3,13 3,12
4(2)A 3,48 2,4 3,86 2,71 3,87 2,79 4,13 3,29
4(2)- 3,29 1,98 3,38 2,4 3,7 2,58 3,93 3,13
4(4)A 2,83 3,19 3,18 3,77 3,43 3,78 3,76 3,95
5(3)A 4,21 2,86 4,8 3,51 4,84 3,24 5,11 3,88
6(3)A 4,59 3,03 5,47 3,66 5,31 3,56 6,14 4,44
6(3)- 3,99 2,48 4,84 3,11 5,31 3,54 5,68 4,25
7(4)A 4,97 3,29 6,23 3,83 6,21 3,83 6,93 5,01
8(4)A 5,05 3,44 6,17 4,03 5,98 3,87 6,61 5,42
8(4)- 4,46 2,89 5,47 3,49 5,22 3,62 5,68 4,92
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
168
) ��(� .1 %������� %��
����
���$����$ , ���������� � %��
����
���$����
%�����������$���� ������� . ������ ������� �%
������ ���!
� ��&
# ���(
��
�
,��%��
����� :
�
��� ����"���������� %��&������� ; �
��� ����"���������� ���� �������� (� ���(��� ); ”� “
”- “ –
�%���(� ���(
��
. )� ���� �� ���� ��
� ���� %��
����
���$����$ (�������� *
���� ��
!��� )
����
�����$ , ���
��*��" ���
��
���$��" %��&��� (�� %�
����� � �%���������� %��&����� ,
%�
����
, ��� (��
����"�������� �(� %��&������ ������
���� *� ��� . 5��
(��
����"������� ���$�� ��
�
� �� � %��&������� ��� , �� %��
����
���$����$ ����� (��$ ���� (��
%�
����
(��� � �� ��� ”4(4)� “). �� -�
�
��� , ,�� ������� �� �� ��"��� ��(���� �%���&
����"
�
�����" %��&������ ��� ��%�����
� �����
:
��
���� ��%
�����
�
�!����&
� �,� -%����
������ %��&������ � �,� -%����$ �� ���� %�
���
� � ����
���$��" %����� %��
����
���$����
.
���(���
�� ���*� �����
�$ ��*����$
�%��$�����
� %����( �����
������ � ������� � �������
�������� ����� . -�� %����( �����
������ ������� �
���
����&
" �� ��*��� ����
�����
�����
� , ���(���
��� ��� �����
� (15) � �(���#���" %���������$# 10-6� , (���
%�
(�
�
���$�� 13,2, 12,1, 13,1, 12,0 ��� ��*��"
� %���� ��� ����� �������������� , � �� �����
��� � %����( �����
������� ���(������$ � ������� 7,3, 6,2, 7,7
6,5
����&
" ��� �����
� (18) �
,��
��������" �������$# .
�� �������
# � �� ������" �����$# , %��
����
���$����$ ���������" �����
���
�
� ��
����
� �� �
� !������� , ���
� ��� �
��� ����
���$��� ����� ; %�
�����
� ������� ���� %�
����
���
; ���
����
� ����������
�����
��� , ���#��#'
� �� �����
� �%���&
, ��� , ��%�
��� ,
� e/k �����
� �( ��������
[16]. 4�� ��� ���(
��� �� %���(����
�� '���������� �
���
������$��� ��%������
�� , �� %����
������� !������ %�
����� ���$�� � ���
���
# ����
������
, ������������ �� ��%�����
� �����
�
��� �%���&
"
, ��� �������
� , � ���
���
#
,!!���
�����
%�������
��&
.
���
����
���$����$ ���������" �����
� �����$ �� %�
���� �����
�����
� �����
� �
������ %���� ���$��" !���� , %�������� �����" 520x50x30 ����� . /������ ������
����
����
����
� (��
���
�
*� , ��� � %�����
� �%
������ ,��%��
������ ��� �� ������" �����
.
7
����
���
�� �%
�������$ ������
��
(1)–(6), ��%��������
e/k �����$# ��� ���
����
�
��,!!
&
����� ����
���$��" �������
. -��
%������
������ ��� ������ ������� �����
%���������
: %�� ������"
� ���'�%���
�� �� ���� .
/
� . 7. ���
����
���$����$ ���������" �����
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4 169
�� �
� . 7 %������� ���
���
� %��
����
���$����
� ���
�
����
�� �
��� %��&������� .
+(� �����
(� %�� �������
����� �������� ����� ) %������
���* # %��
����
���$����$ :
%��
�� ���� , ��� � ���������" �����
(��$��� ����$ ������
����
��� �� ������ ����
���$����
���%�������
� , �
�����
��&
� %��&�����
�(��� ������ �� ��*��� ����
����&
" %�
�����
�
����� ������
" ����#��� %���(��� �
�����
��&
%��&�����
�(��� ������ �� ��*���
����
�����
�����
� �� ������" ���� . 1%���( ���(
��
”- “ �� 14 %���(�����" ��������
%���%���
���$��� ��������
� ���$���
� %��'��
%���(�����" %�
��
������" ��
�� ����
&
��*� %���(������
���(
��
”A“. ��
� ���� ,!!���
�����$ , �%���������� ���
%100)/( 1 ×= NPPE N , ��� 1P – %��
����
���$����$ %�����������$��" �����
, NP –
%��
����
���$����$ �
�%��$�����
�� N %��&������� , � �������" ������ (��� ~69% � �� ���
���(
��
”A“
~75% � �� ��� ���(
��
”- “ �� 14 %���(�����" . 4�� �� ����� %��
����
���$����$
%�
,��� (��� ��
(��$��" . ��������� ���
���
� ,!!���
�����
, ����� (��� ����"�������� 9
%��&������� %� �������
# � 8, %�-�
�
��� , �( �������� (���� ,!!���
����
�%��$�����
��
�,� -%����
.
���� ������&
� %�
�����
�� MPI ���*� ��*�� (��$
�%��$����� ��� �������� ��
�� �:������� %��&������� . )����%
�����" ,��%��
���� ����������� �����
�����
� �����
� �
������ %������ ,!!���
�����$ ~85% (����" ����� )
~88% (%�� ������" ����� ) %�
�%��$�����
%��&������ Intel Dual Core 2,4 77&
���(
��� ���" ��������" �(����
�� ���
%���(����
.
7. �.�%�.
������*�� ����� %�������
��&
�����
���� ������� ,
�%��$� ���� � �
�������
�
�������
����
� ������� �������� , ���������" �� ���(
��� ��������" �(����
�� %���(����
.
���
� '������ ��� �������� �� , ��� �� %����� ,��%� ��*���� ����
�����
�����
�
�
����&
�����
�� ������� ��� ��*��" %���(����
�� ���
������ �� %�����������$���� . ������&
�
��� �$����� %��
����
��� �� ������ ,��%� � %���'$# ��%���
���$��� %��&�� � � %�
�����
��
MPI. ��� ������ �����
� �������� ����� ���
� *� , ��� %�
%�����������$��� ������� , �
,!!���
�����$ %�������
��&
�%���� %�
������ %�
�������� �� ��������� , ������'
�
� ~10-
20 %��&������� , � ���*� �� ���� � �('�" %����$#
������������ %��&������� .
4������� �����
%������
, ��� ,!!���
�����$ %�������
��&
� (��$��" ���%��
���
���� ��
��
�
� ��$��" %��
����
���$����
%��&�������
�������� %���(�����" , ��� ��
%��% ����" �%���(����
������� ���� �
������� . ) ���������" �����
���� %��
����
���$����
� ���
���
�� �
��� %��&������� �������� ���*
� %�
�%��$�����
������
%�� ��������
������� ������� ����� %���������
��(�#����� �� ���� %���������� ,��%��
������ �
�%��$�����
�� �� 14-�
%��&������� . )�*���
!�������
���
���
� %��
����
���$����
,!!���
�����
�������$
�%��$�����
� �
������$���� %����( �����
������ ��� ������" �
%�� ������� ������� ������� ����� , � ���(������
�� ������� , � ���*� %�
����� ��*����
%��&���� � �%���������� %��&����� %�
�������� �� �����%��&�������� �
������ .
���$��"��� ��(��� ���#���� �%�
�
��&
# ���(
��
��������" �(����
; %�������
��&
#
���
�������
����
� ������" , %�
����'
� � ���(���
����
�����
� �
����� �
��"��� ������
"
SSN 1028-9763.
������
��� ���
�
� �
����
, 2008, � 4
170
��� ������
� (
�
��� ��������#'�" ) � (���� ��� %��
�
������$��" ����
&�" ;
���������
�
,!!���
�����
%�����*������ ������ %�������
��&
%�
(��$��� �
��� %��&������� .
����� ����*���
������## (�����������$ ������ !
�
�� -�������
����
� �� � ,
%��!����� ) .1 .
����
� �� �������
�
������ . ����� %�
�������� TMSI, National University of
Singapore �� ������� # %�����*� � ��(��� .
��
��� �
����� ��
1. �������
�* . 7��!
�
������ �
����
���
�� . –
����� :
� , 1984. – 4. 1. – 398 � .
2. Intel. Intel 64 and IA-32 Architectures Optimization Manual � 248966-015. – Intel Corporation: Denver, 2007. –
488 p.
3. Blumberg A.F., Mellor G.L. A description of a three-dimensional coastal ocean circulation // Three-Dimensional
Coastal Ocean Models / N. Heaps (ed). – Washington, D.C.: Am. Geoph. Union, 1987. – P. 1 – 16.
4.
����
�����
� ���%���������
� ��%�� �� �� �����
� �����
%�
(��*��� �(������ ����" /
) . ����( &�
" , ) .
����
� , � . ��������
�� . // ��
������� �
��������
�� . – 2004. – � 6 (78). – 1 . 34 – 44.
5. Ashworth M., Davies A.M. Performance of a three dimensional hydrodynamic model on a range of parallel
computers // Proc. � f Euromicro Workshop on Parallel and Distributed Processing. – Gran Canaria, Spain, 1993. – P.
383 – 390.
6. Gropp W. et al. Portable Parallel Programming with the Message Passing Interface, 2nd Ed. / W. Gropp, 5 . Lusk, � .
Skjellum. – Cambridge, Mass.: MIT Press, 1999. – 395 p.
7. Parallelization of the GESIMA mesoscale atmospheric model /
. Ashworth, � . Foelkel, V. Gulzov et al. // Parallel
Computing. – 1997. – N 23. – P. 2201 – 2213.
8. Towards modeling flow and water structure in the Rockall Slope / A.J. Souza, S. Walkelin, J.T. Holt et al. // Proc. Of
the PECS’02. – Hamburg, 2002. – P. 409 – 412.
9. Ashworth M. Optimization of the POLCOMS Hydrodynamic Code for Terascale High Performance Computers / M.
Ashworth, J.T. Holt, R. Proctor // Proc. � f 18th Int. Parallel & Distributed Proc. Symp. – New Mexico, 2004. – P. 383 –
390.
10. Kerbyson D.J., Jones P.W. A performance model for Parallel Ocean Program // Int. J. of High Performance
Computing Applications. – 2005. – Vol.19. – P. 261 – 276.
11. A domain decomposition method for three-dimentional shallow water equations / E.D. Goede, J. Groeneweg, K.H.
Tan et al. // Simulation Practice and Theory. – 1995. – N 3. – P. 307 – 325.
12. The parallelization of the Princeton Ocean Model / L.A. Boukas, N.Th. Mimikou, N.M. Missirlis et al. // Springer,
Lect. Notes In Comp. Sci.; Proc. Of Euro-Par’99. – 1999. – / . 1395 – 1402.
13. Casulli V. Semi-Implicit Finite Difference Methods for the Two-Dimensional Shallow Water Equations // J. of
Computational Physics. – 1990. – N 86. – P. 56 – 74.
14. Casulli V., Cheng R.T. Semi-Implicit Finite Difference Methods for Three-Dimensional Shallow Water Flow // Int. J.
for Numer. Meth. In Fluids. – 1992.– N 15. – P. 629 – 648.
15. 9������ � . )��
��
���$��� ������ � �
���
�� *
������" . –
����� :
� , 1991. – 4. 1: +�������
%���*��
�
�('
� ������ . – 502 � .
16. Burchard H., Peterson O. Models of turbulence in the marine environment – a comparative study of two-equation
turbulence models // Journal of Marine Systems. – 1999. – N 21. – P. 29 – 53.
17. Tannehill J.C. et al. Computational Fluid Mechanics and Heat Transfer, 2nd Ed. / J.C. Tannehill, D.A. Anderson,
R.H. Pletcher. – Washington: Taylor and Francis, 1997. – 792 p.
18. Fringer O-B. et al. Reducing numerical diffusion in interfacial gravity wave simulations / O-B. Fringer, S.W.
Armfield, R.L. Street // Int. J. Numer. Meth. Fluids. – 2005. – N 49. – P. 301 – 329.
19. Stelling G.S., Duinmeijer S.P.A. A staggered conservative scheme for every Froude Number in rapidly varied
shallow water flows // Int. J. for Num. Meth. In Fluids. – 2003. – N 43. – P. 1329 – 1354.
20. -������� � .1 . 8
������� ������ . ����
� , ����(��
�(���������� �
!!����&
��$��� ������
� . –
����� : �� �� , 1975. – 631 � .
21. Templates for the solution of linear systems: building blocks for iterative methods / R. Barrett, M. Berry, T.F. Chan
et al. – 2nd Ed. – Phil.: SIAM, 1994. – 112 p.
'����� �
��!��
� ��
����� 04.02.2008
|
| id | nasplib_isofts_kiev_ua-123456789-46833 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1028-9763 |
| language | Russian |
| last_indexed | 2025-11-24T11:37:16Z |
| publishDate | 2008 |
| publisher | Інститут проблем математичних машин і систем НАН України |
| record_format | dspace |
| spelling | Нестеров, А.А. 2013-07-07T12:57:46Z 2013-07-07T12:57:46Z 2008 Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью / А.А. Нестеров // Мат. машини і системи. — 2008. — № 4. — С. 154–170. — Бібліогр.: 21 назв. — рос. 1028-9763 https://nasplib.isofts.kiev.ua/handle/123456789/46833 004.9:504:519.6 В роботi запропоновано метод перетворення послiдовних алгоритмiв моделей гiдродинамiки резервуарiв з вiльною поверхнею в паралельнi, використовуючи MPI та розбивку розрахункової областi на пiдобластi, перевагою якого є відносна простота реалізації, обумовлена потребою тільки у додаткових процедурах корекції замість значних перетворень існуючих програм послідовного розрахунку. Дослiджується вплив рiзноманiтних факторiв на ефективнiсть методу в термінах зменшення тривалості розрахунків зі збільшенням числа застосованих процесорів. В работе предложен метод преобразования последовательных алгоритмов моделей гидродинамики резервуаров со свободной поверхностью в параллельные, используя MPI и разбивку расчётной области на подобласти, преимуществом метода является относительная простота реализации, обусловленная потребностью только в дополнительных процедурах коррекции вместо значительных преобразований существующих программ последовательного расчёта. Исследуется влияние различных факторов на эффективность метода в терминах уменьшения длительности параллельных расчётов с увеличением числа используемых процессоров. This paper proposes a technique using MPI and domain decomposition to transform serial algorithms of numerical models for hydrodynamics simulations in the water reservoirs with free surface into parallel algorithms. The advantage of the proposed technique is a comparatively simple realization due to the necessity of only additional correction procedures instead of significant transformations of existing serial program code. The impacts of various factors on the method of efficiency are studied in terms of the speedup of computations with the increase of number of utilized processors. ru Інститут проблем математичних машин і систем НАН України Математичні машини і системи Моделювання і управління великими системами Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью Метод корекції для паралелізації чисельних моделей гідродинаміки водоймищ із вільною поверхнею The method of correction for parallelization of numerical models for hydrodynamics simulations in water reservoirs with free surface Article published earlier |
| spellingShingle | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью Нестеров, А.А. Моделювання і управління великими системами |
| title | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью |
| title_alt | Метод корекції для паралелізації чисельних моделей гідродинаміки водоймищ із вільною поверхнею The method of correction for parallelization of numerical models for hydrodynamics simulations in water reservoirs with free surface |
| title_full | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью |
| title_fullStr | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью |
| title_full_unstemmed | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью |
| title_short | Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью |
| title_sort | метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью |
| topic | Моделювання і управління великими системами |
| topic_facet | Моделювання і управління великими системами |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/46833 |
| work_keys_str_mv | AT nesterovaa metodkorrekciidlâparallelizaciičislennyhmodeleigidrodinamikivodoemovsosvobodnoipoverhnostʹû AT nesterovaa metodkorekcíídlâparalelízacííčiselʹnihmodeleigídrodinamíkivodoimiŝízvílʹnoûpoverhneû AT nesterovaa themethodofcorrectionforparallelizationofnumericalmodelsforhydrodynamicssimulationsinwaterreservoirswithfreesurface |