Метод коррекции для параллелизации численных моделей гидродинамики водоемов со свободной поверхностью

В роботi запропоновано метод перетворення послiдовних алгоритмiв моделей гiдродинамiки резервуарiв з вiльною поверхнею в паралельнi, використовуючи MPI та розбивку розрахункової областi на пiдобластi, перевагою якого є відносна простота реалізації, обумовлена потребою тільки у додаткових процедурах...

Full description

Saved in:
Bibliographic Details
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