Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров
Досліджено задачу оптимізації тайлінга при розв’язанні першої краєвої задачі для багатомірного рівняння теплопровідності на обчислювальних системах з розподіленою пам’яттю. Наведено оцінки об’єма комунікацій і обчислень. Задачу оптимізації тайлінга зведено до задачі мінімізації функції, що явно вира...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2010 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/45136 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров / П.И. Соболевский, С.В. Баханович, А.Н. Горбач // Кибернетика и системный анализ. — 2010. — № 1. — С. 163-171. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859954328958140416 |
|---|---|
| author | Соболевский, П.И. Баханович, С.В. Горбач, А.Н. |
| author_facet | Соболевский, П.И. Баханович, С.В. Горбач, А.Н. |
| citation_txt | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров / П.И. Соболевский, С.В. Баханович, А.Н. Горбач // Кибернетика и системный анализ. — 2010. — № 1. — С. 163-171. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Досліджено задачу оптимізації тайлінга при розв’язанні першої краєвої задачі для багатомірного рівняння теплопровідності на обчислювальних системах з розподіленою пам’яттю. Наведено оцінки об’єма комунікацій і обчислень. Задачу оптимізації тайлінга зведено до задачі мінімізації функції, що явно виражає залежність часу реалізації алгоритму від розмірів тайла і параметрів цільового суперкомп’ютера.
The problem of tiling optimization in solving the heat equation on supercomputers with distributed memory is investigated. Estimates of amounts of computation and communication are obtained. The tiling optimization is reduced to the minimization of the algorithm execution time as a function of the tile size, size of computing environment, processor performance, and latency and bandwidth of communication channels.
|
| first_indexed | 2025-12-07T16:18:27Z |
| format | Article |
| fulltext |
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 163
Ï.È. ÑÎÁÎËÅÂÑÊÈÉ, Ñ.Â. ÁÀÕÀÍÎÂÈ×, À.Í. ÃÎÐÁÀ×
ÓÄÊ 681.3.012+519.6 ÎÏÒÈÌÈÇÀÖÈß ÒÀÉËÈÍÃÀ ÏÐÈ ×ÈÑËÅÍÍÎÌ
ÐÅØÅÍÈÈ ÌÍÎÃÎÌÅÐÍÎÃÎ ÓÐÀÂÍÅÍÈß
ÒÅÏËÎÏÐÎÂÎÄÍÎÑÒÈ
ÍÀ ÊÎËÜÖÅ ÏÐÎÖÅÑÑÎÐÎÂ 1
Êëþ÷åâûå ñëîâà: òàéëèíã, òàéë, âû÷èñëèòåëüíàÿ ñèñòåìà ñ ðàñïðåäåëåííîé
ïàìÿòüþ, îïòèìèçàöèÿ, óðàâíåíèå òåïëîïðîâîäíîñòè.
Îäèí èç âàæíåéøèõ àñïåêòîâ ïðè ðàçðàáîòêå è îïòèìèçàöèè ïàðàëëåëüíûõ ïðèëî-
æåíèé äëÿ âû÷èñëèòåëüíûõ ñèñòåì ñ ðàñïðåäåëåííîé ïàìÿòüþ — ýôôåêòèâíàÿ
îðãàíèçàöèÿ êîììóíèêàöèè. Íà ïðàêòèêå êîììóíèêàöèè ÷àñòî ÿâëÿþòñÿ óçêèì ìåñ-
òîì ïàðàëëåëüíûõ ïðèëîæåíèé âñëåäñòâèå âûñîêîé ëàòåíòíîñòè êàíàëîâ ñâÿçè ïî
ñðàâíåíèþ ñ ïðîèçâîäèòåëüíîñòüþ óçëîâ. Îäíî èç ýôôåêòèâíûõ ñðåäñòâ îïòèìèçà-
öèè êîììóíèêàöèé — òåõíèêà òàéëèíãà, ïîçâîëÿþùàÿ óìåíüøèòü äîëþ êîììóíè-
êàöèé ïî ñðàâíåíèþ ñ äîëåé âû÷èñëåíèé ïàðàëëåëüíîãî àëãîðèòìà è äîïîëíèòåëü-
íî ïîâûñèòü ýôôåêòèâíîñòü èñïîëüçîâàíèÿ ïàìÿòè âû÷èñëèòåëüíûõ óçëîâ.
 äàííîé ðàáîòå èññëåäóåòñÿ çàäà÷à îïòèìèçàöèè òàéëèíãà ïðè ðåøåíèè ïåð-
âîé êðàåâîé çàäà÷è äëÿ ìíîãîìåðíîãî óðàâíåíèÿ òåïëîïðîâîäíîñòè
�
�
�
�
��
�
u
x
u
xmm
n
1
2
2
2
, 0 1� �xm , 2 � �m n, 0 1� �x T, (1)
íà âû÷èñëèòåëüíûõ ñèñòåìàõ ñ ðàñïðåäåëåííîé ïàìÿòüþ, ïîñòðîåíû îöåíêè îáúå-
ìà êîììóíèêàöèé è âû÷èñëåíèé ïðè çàäàííûõ âàðèàíòàõ òàéëèíãà. Íà èõ îñíîâå
äëÿ ñëó÷àåâ n � 2 è n � 3 ïîëó÷åíû îöåíêè ïîëíîãî âðåìåíè ðåàëèçàöèè àëãîðèòìà,
ïðåäñòàâëÿþùèå ñîáîé ôóíêöèþ îò ïàðàìåòðîâ òàéëèíãà è ïàðàìåòðîâ öåëåâîãî
ñóïåðêîìïüþòåðà: ðàçìåðíîñòè è ðàçìåðîâ âû÷èñëèòåëüíîé ñðåäû, ïðîèçâîäèòåëü-
íîñòè ïðîöåññîðîâ, âðåìåíè èíèöèàëèçàöèè è ïðîïóñêíîé ñïîñîáíîñòè êàíàëîâ
ñâÿçè. Ìèíèìèçàöèÿ ýòîé ôóíêöèè ïîçâîëÿåò îïòèìèçèðîâàòü òàéëèíã.
1. ÒÀÉËÈÍÃ
Ïðåäïîëîæèì, ÷òî ïàðàëëåëüíûé àëãîðèòì, êàê ýòî ÷àñòî áûâàåò íà ïðàêòèêå,
ñòðîèòñÿ íà îñíîâå ñîîòâåòñòâóþùåãî ïîñëåäîâàòåëüíîãî àëãîðèòìà. Ðàññìàòðèì
n-ìåðíûå àëãîðèòìû ñ îäíîðîäíûìè çàâèñèìîñòÿìè, çàïèñàííûå â âèäå ãíåçäà
òåñíîâëîæåííûõ öèêëîâ:
for to doi I1 11�
��������
for to doi In n�1
begin (2)
S i i in1 1 2( , , , );�
�������
S i i ik n( , , , )1 2 �
end
1
Ðàáîòà âûïîëíåíà ïðè ôèíàíñîâîé ïîääåðæêå Áåëîðóññêîãî ðåñïóáëèêàíñêîãî ôîíäà
ôóíäàìåíòàëüíûõ èññëåäîâàíèé (ïðîåêò ¹ Ô08-016).
� Ï.È. Ñîáîëåâñêèé, Ñ.Â. Áàõàíîâè÷, À.Í. Ãîðáà÷, 2010
Àëãîðèòìû òàêîãî âèäà õàðàêòåðèçóþòñÿ îáëàñòüþ âû÷èñëåíèé V è ìíîæåñò-
âîì âåêòîðîâ çàâèñèìîñòåé �. Îáëàñòü âû÷èñëåíèé åñòü ïîäìíîæåñòâî òî÷åê öå-
ëî÷èñëåííîãî ïðîñòðàíñòâà Zn , êîòîðîå îïðåäåëÿåòñÿ êàê V v i i in� { ( , , , )1 2 �
� � � �Zn
m mi I m n| ,1 1 }. Êàæäîé òî÷êå v i i i Vn( , , , )1 2 � â ñîîòâåòñòâèè ñ àëãî-
ðèòìîì ïðèïèñàíî k îïåðàöèé S v S i i ii i n( ) ( , , , )� 1 2 � , 1� �i k. Ìíîæåñòâî âåêòîðîâ
çàâèñèìîñòåé îòðàæàåò èíôîðìàöèîííûå çàâèñèìîñòè ìåæäó îïåðàöèÿìè àëãîðèòìà:
íàëè÷èå âåêòîðà �( , )i j ìíîæåñòâà � îçíà÷àåò, ÷òî ñóùåñòâóþò òàêèå v V è i j N, ,
1� �i j k, , ÷òî îïåðàöèÿ S vj
i j( )( , )
� èíôîðìàöèîííî çàâèñèò îò îïåðàöèè S vi ( ) .
Òåõíèêà òàéëèíãà ñîñòîèò â ðàçáèåíèè îáëàñòè âû÷èñëåíèé àëãîðèòìà (è ñîîò-
âåòñòâåííî ìíîæåñòâà åãî îïåðàöèé) n ñåìåéñòâàìè ïàðàëëåëüíûõ ãèïåðïëîñêîñòåé
íà ìíîæåñòâî n-ìåðíûõ ïàðàëëåëåïèïåäîâ-òàéëîâ. Ìíîæåñòâî îïåðàöèé, ïðèíàä-
ëåæàùèõ îäíîìó òàéëó, ñîñòàâëÿþò íîâîå (óêðóïíåííîå) çåðíî âû÷èñëåíèé. Ñå-
ìåéñòâà ãèïåðïëîñêîñòåé çàäàþòñÿ ìíîæåñòâîì èç n ëèíåéíî íåçàâèñèìûõ âåêòî-
ðîâ { }h h hn1 2, , ,� . Êàæäîìó ñåìåéñòâó ñîîòâåòñòâóåò ñâîé âåêòîð hm , íîðìàëüíûé
äëÿ ãèïåðïëîñêîñòåé ýòîãî ñåìåéñòâà. Ïîëó÷àåìîå ðàçáèåíèå îáëàñòè V íà òàéëû
äîëæíî óäîâëåòâîðÿòü ñëåäóþùèì óñëîâèÿì:
1) òàéëû äîëæíû áûòü îäíîòèïíûìè, ò.å. îäèíàêîâûìè ïî ôîðìå è ðàçìåðó (çà
èñêëþ÷åíèåì âîçìîæíî ãðàíè÷íûõ);
2) ìåæäó òàéëàìè íå äîëæíî ñóùåñòâîâàòü îáðàòíûõ ñâÿçåé.
Ââåäåì ðÿä ôîðìàëüíûõ îïðåäåëåíèé è îáîçíà÷åíèé.
�H h h hn� ( , , , )1 2 �
T — êâàäðàòíàÿ ìàòðèöà ïîðÿäêà n, ñòðîêàìè êîòîðîé âû-
ñòóïàþò êîîðäèíàòû ëèíåéíî íåçàâèñèìûõ öåëî÷èñëåííûõ âåêòîðîâ h m nm , 1� � ,
— íîðìàëüíûõ âåêòîðîâ ãèïåðïëîñêîñòåé, îñóùåñòâëÿþùèõ ðàçáèåíèå îáëàñòè
âû÷èñëåíèé íà òàéëû. Áóäåì ñ÷èòàòü, ÷òî íàèáîëüøèé îáùèé äåëèòåëü ìîäóëåé
êîîðäèíàò êàæäîãî èç ýòèõ âåêòîðîâ ðàâåí åäèíèöå.
� R r r rn�diag ( , , , )1 2 � — äèàãîíàëüíàÿ ìàòðèöà. Íàòóðàëüíîå ÷èñëî rm îáîçíà-
÷àåò êîëè÷åñòâî ãèïåðïëîñêîñòåé ñ íîðìàëüíûì âåêòîðîì hm , 1� �m n, ïðîõîäÿ-
ùèõ ÷åðåç êàæäûé òàéë.
� v v v vn
min min min min( , , , )�
1 2
�
T — âåêòîð, îïðåäåëÿåìûé óñëîâèÿìè h vm m� �min
� �
min
v V
mh v, 1� �m n.
� 1 1 1 1n � ( , , , )�
T — âåêòîð ðàçìåðíîñòè n, ñîñòàâëåííûé èç åäèíèö.
� I I I I n� ( , , , )1 2 �
T — âåêòîð, ïîñòðîåííûé èç çíà÷åíèé I m nm , 1� � .
�
�a — âåêòîð, ñîñòàâëåííûé èç öåëûõ ÷àñòåé êîîðäèíàò âåêòîðà a.
{ }a — âåêòîð, ïîñòðîåííûé èç äðîáíûõ ÷àñòåé êîîðäèíàò âåêòîðà a.
Ôîðìàëüíî òàéëèíã ìîæíî ðàññìàòðèâàòü êàê íåëèíåéíîå îòîáðàæåíèå ìíî-
æåñòâà V íà ìíîæåñòâî � �V nZ2 : v j� ( , )� , v V n � Z , ( , )j V n� � � Z2 , ãäå
j j j j R H v vn n� �
� �
�( , , , ) ( )min
1 2
11�
T ,
� � � �� � � ��( , , , ) ( ( ) )min
1 2
11� n nR R H v vT { } . (3)
Âåêòîð j j j jn� ( , , , )1 2 �
T , j Jm m�12, , , ,� J
r
h Im
m
m k
k
n
k� �
�
�
�
�
�
�
�
�
1
1 1
1
| |( ), ,
1� �m n, îïðåäåëÿåò ãëîáàëüíûå êîîðäèíàòû òàéëà, âåêòîð � � � �� ( , , , )1 2 � n
T ,
�m mr�12, , ,� , 1� �m n, — ëîêàëüíûå (â êàæäîì òàéëå) êîîðäèíàòû òî÷êè
v i i i Vn� ( , , , )1 2 � . Êîîðäèíàòà �m îáîçíà÷àåò ïîðÿäêîâûé íîìåð ãèïåðïëîñêîñ-
òè, ïðîõîäÿùåé ÷åðåç òàéë ñ íîðìàëüíûì âåêòîðîì hm .
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Âåêòîðû çàâèñèìîñòåé äëÿ àëãîðèòìà âèäà (2) îáëàäàþò òàêèì ñâîéñòâîì: ïåð-
âàÿ íåíóëåâàÿ êîîðäèíàòà âåêòîðà áîëüøå íóëÿ. Îòñþäà, à òàêæå èç îïðåäåëåíèÿ
òàéëèíãà è îáîçíà÷åíèé, ïðèâåäåííûõ âûøå, ñëåäóåò, ÷òî òî÷êà vmin ïðèíàäëåæèò
òàéëó ñ åäèíè÷íûìè êîîðäèíàòàìè è ÿâëÿåòñÿ òî÷êîé ïåðåñå÷åíèÿ ãèïåðïëîñêîñ-
òåé ñ íîìåðàìè, îïðåäåëÿåìûìè âåêòîðîì � � �R n1 ( , , , )r r rn1 2 �
T .
Ïóñòü H
è H� — ìàòðèöû, ïîëó÷åííûå èç ìàòðèöû H çàìåíîé ñîîòâåòñòâåí-
íî îòðèöàòåëüíûõ è ïîëîæèòåëüíûõ ýëåìåíòîâ íóëÿìè. Òîãäà èìååò ìåñòî ðàâåíñòâî
Hv H H In
min �
�1 .
Î÷åâèäíî ñîîòíîøåíèå
H v v Rj( )min� � ��, (4)
èç êîòîðîãî ïðè óñëîâèè öåëî÷èñëåííîñòè âåêòîðà v H Rjmin ( )
��1 � ñëåäóåò
v v H R j V�
� �min ( )1 � èëè ñ ó÷åòîì ïðèâåäåííûõ îïðåäåëåíèé
v v
H
r j
r j
r j
m m m m
m
n
m m m m
m
n
m
�
�
�
�
�
�
�min
| |
( )
( )
(
1
1
1
2
1
�
�
A
A
�
m m mn
m
n
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
��
� � )A
1
, (5)
ãäå Amk — àëãåáðàè÷åñêîå äîïîëíåíèå ýëåìåíòà hmk ìàòðèöû H, | |H — îïðåäå-
ëèòåëü ìàòðèöû H.
Îïðåäåëåíèå 1. Òàéëû j j� ��, íàçûâàþòñÿ îäíîòèïíûìè, åñëè ñóùåñòâóåò òà-
êîé âåêòîð b n Z , ÷òî òàéë j�� ìîæåò áûòü ïîëó÷åí ïóòåì ïàðàëëåëüíîãî ïåðåíîñà
òàéëà j� íà âåêòîð b.
Óòâåðæäåíèå 1. Ïóñòü I m ��, 1� �m n. Äëÿ òîãî ÷òîáû âñå òàéëû áûëè îä-
íîòèïíûìè, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû ìàòðèöà H R�1 áûëà öåëî÷èñëåííîé,
ò.å. ÷òîáû âñå äèàãîíàëüíûå ýëåìåíòû rm ìàòðèöû r äåëèëèñü ñîîòâåòñòâåííî íà
�m
m m mn
H
H A A A
�
| |
(| | , , , , )ÍÎÄ 1 2 �
, 1� �m n.
Äåéñòâèòåëüíî, ïóñòü j j� ��, — äâà òàéëà, v v H Rj� �
���min ( )1 � , v v�� �
min
����H Rj1 ( )� — äâå òî÷êè, ÿâëÿþùèåñÿ òî÷êàìè ïåðåñå÷åíèÿ ãèïåðïëîñêîñòåé ñ
îäèíàêîâûìè íîìåðàìè, îïðåäåëÿåìûìè îäíèì è òåì æå âåêòîðîì �. Èç ðàâåíñòâà
v v H R j j�� � � �� ��– ( – )1 ñëåäóåò, ÷òî òàéë j�� ìîæíî ïîëó÷èòü èç òàéëà j� ïàðàëëåëü-
íûì ïåðåíîñîì òàéëà j�íà âåêòîð H R j j� ��� �1 ( ). Ñëåäîâàòåëüíî, êîîðäèíàòû âåêòî-
ðà H R j j� ��� �1 ( ) äîëæíû ïðèíèìàòü öåëî÷èñëåííûå çíà÷åíèÿ.  ñâîþ î÷åðåäü öåëî-
÷èñëåííîñòü êîîðäèíàò âåêòîðà H R j j� ��� �1 ( ) ïðè óñëîâèè íåîãðàíè÷åííîñòè îáëàñ-
òè âû÷èñëåíèé ýêâèâàëåíòíà öåëî÷èñëåííîñòè ýëåìåíòîâ ìàòðèöû H R�1 .
Óòâåðæäåíèå 2[1]. Äëÿ òîãî ÷òîáû ìåæäó òàéëàìè îòñóòñòâîâàëè îáðàòíûå
ñâÿçè, íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèÿ óñëîâèÿ
H� � 0, �. (6)
Óñëîâèå (6) ýêâèâàëåíòíî òîìó, ÷òî ïðîåêöèè âåêòîðîâ çàâèñèìîñòåé íà ïðÿ-
ìûå ñ íàïðàâëÿþùèìè âåêòîðàìè hm , 1� �m n, ëèáî íóëåâûå, ëèáî îäèíàêîâî
íàïðàâëåíû.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 165
Ñïîñîá ðàçáèåíèÿ íà ñóïåðâåðøèíû (èõ ôîðìà, ðàçìåðû) è ñïîñîá îòîáðàæå-
íèÿ ìíîæåñòâà ñóïåðâåðøèí íà ïàðàëëåëüíóþ àðõèòåêòóðó îïðåäåëÿþò ýôôåêòèâ-
íîñòü ðåàëèçàöèè àëãîðèòìà. Êðîìå òîãî, íà ýôôåêòèâíîñòü ðåàëèçàöèè âëèÿåò è
òî, â êàêîì îáúåìå ïðè ðàçáèåíèè ó÷èòûâàþòñÿ õàðàêòåðèñòèêè ñóïåðêîìïüþòåðà,
òàêèå êàê ïðîèçâîäèòåëüíîñòü ïðîöåññîðîâ, âðåìÿ èíèöèàëèçàöèè êàíàëîâ ñâÿçè è
èõ ïðîïóñêíàÿ ñïîñîáíîñòü.
Ïåðñïåêòèâíîñòü òàéëèíãà ïîâëåêëà çà ñîáîé ðÿä èññëåäîâàíèé â öåëÿõ ðàçðà-
áîòêè ìåòîäîâ ïîñòðîåíèÿ îïòèìàëüíûõ ðàçáèåíèé. Ðåçóëüòàòîì ýòèõ èññëåäîâà-
íèé ñòàë ðÿä ìåòîäîâ îïòèìèçàöèè òàéëèíãà [1–9]. Îòëè÷èÿ ýòèõ ìåòîäîâ ñîñòîÿò
â îïðåäåëåíèè êðèòåðèåâ îïòèìàëüíîñòè: â êàêîé ñòåïåíè ïðè ðàçáèåíèè ó÷èòûâà-
þòñÿ îñîáåííîñòè àëãîðèòìà, õàðàêòåðèñòèêè âû÷èñëèòåëüíîé ñèñòåìû, à òàêæå,
êàê ðåøàåòñÿ çàäà÷à îòîáðàæåíèÿ òàéëîâ íà ìíîæåñòâî âû÷èñëèòåëüíûõ óçëîâ ïà-
ðàëëåëüíîãî êîìïüþòåðà. Íåäîñòàòîê ìåòîäîâ çàêëþ÷àåòñÿ â òîì, ÷òî îíè íå â ïîë-
íîé ìåðå, à íåêîòîðûå èç íèõ âîîáùå íå ó÷èòûâàþò õàðàêòåðèñòèêè öåëåâîé âû-
÷èñëèòåëüíîé ñèñòåìû. Èñêëþ÷åíèå ñîñòàâëÿþò ìåòîäû, ïðåäñòàâëåííûå â [8, 9].
Îäíàêî îíè ïðèãîäíû òîëüêî òîãäà, êîãäà ìíîæåñòâî âåêòîðîâ çàâèñèìîñòåé àëãî-
ðèòìà è ìíîæåñòâî íîðìàëüíûõ âåêòîðîâ ãèïåðïëîñêîñòåé, îñóùåñòâëÿþùèõ ðàç-
áèåíèå íà òàéëû, ñîñòîèò òîëüêî èç êîîðäèíàòíûõ âåêòîðîâ em , 1� �m n (n-ìåðíûå
âåêòîðû, ó êîòîðûõ m-ÿ êîîðäèíàòà ðàâíà åäèíèöå, à îñòàëüíûå íóëåâûå).
2. ÀËÃÎÐÈÒÌ ÐÅØÅÍÈß ÏÅÐÂÎÉ ÊÐÀÅÂÎÉ ÇÀÄÀ×È
ÄËß ÌÍÎÃÎÌÅÐÍÎÃÎ ÓÐÀÂÍÅÍÈß ÒÅÏËÎÏÐÎÂÎÄÍÎÑÒÈ
Ïîñëåäîâàòåëüíûé àëãîðèòì âèäà (2) ðåøåíèÿ çàäà÷è (1), îñíîâàííûé íà èñïîëü-
çîâàíèè ÿâíîé ðàçíîñòíîé ñõåìû, ìîæíî çàïèñàòü â ñëåäóþùåì âèäå:
for to doi I
1 11�
for to doi I2 21�
��������
for to doi In n�1
y i i i y i i in
mm
n
n( , , , ) ( , , , )1 2
1
2
2
1 21 2 1� �� �
!
"
#
#
$
%
&
&
�
�
�
�
�
(7)
� �
�
�
�
�
�
1
2
2
1 2 1 11 1
mk
n
k k k ny i i i i i i( ( , , , , , , )� �
�
�
y i i i i i ik k k n( , , , , , , ))1 2 1 11 1� � .
Îáëàñòüþ âû÷èñëåíèéV äëÿ äàííîãî àëãîðèòìà åñòü ïîäìíîæåñòâî òî÷åê ïðî-
ñòðàíñòâà Zn , îïðåäåëÿåìîå êàê V v i i i i I m nn
n
m m� � � � �{ }( , , , ) | ,1 2 1 1� Z .
Ìíîæåñòâî � � � �
� � � �
�
�{ }� � � � � �1 1 1 1 1 2, , | , , ,
k k k k k ke e e e e k n îòðàæà-
åò èíôîðìàöèîííûå çàâèñèìîñòè ìåæäó îïåðàöèÿìè àëãîðèòìà.
3. ÎÖÅÍÊÀ ÂÛ×ÈÑËÈÒÅËÜÍÎÃÎ È ÊÎÌÌÓÍÈÊÀÖÈÎÍÍÎÃÎ ÎÁÚÅÌΠÏÐÈ n � 2
Ðàññìîòðèì âàðèàíò ðàçáèåíèÿ íà òàéëû, îïðåäåëÿåìûé ìàòðèöåé H1
1 0
1 1
�
!
"
#
$
%
& .
Î÷åâèäíî, ÷òî äëÿ ýòîãî âàðèàíòà òàéëèíãà óñëîâèå (6) âûïîëíÿåòñÿ è èìåþò
ìåñòî ñëåäóþùèå ðàâåíñòâà:
vmin ( , )� 1 1 T , J
I
r
I I
r
�
�
�
�
�
�
�
��
�
�
�
�
�
!
"
#
#
$
%
&
&
1
1
1 2
2
1
,
T
,
j
i
r
i i
r
�
��
�
�
�
�
��
�
�
�
�
!
"
#
#
$
%
&
&1
1
1
21
1
1 2
2
,
T
, � � �
��
�
�
�
�
�
�
��
�
�
�
�
�
!
"
#
#
$
%
&
&r r
i
r
r r
i i
r
1 1
1
1
2 2
1 2
2
1 2
,
T
.
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Ìíîæåñòâî âåêòîðîâ � � �� ( , )1 2
T , �m mr�12, , ,� , m �1 2, , îáîçíà÷èì '( )R ,
à êîëè÷åñòâî ðàçëè÷íûõ âåêòîðîâ âî ìíîæåñòâå '( )R çàïèøåì | ( )|' R .
Òðåáîâàíèå îäíîòèïíîñòè íå íàêëàäûâàåò íèêàêèõ îãðàíè÷åíèé íà ïàðàìåòðû
r r1 2, , êðîìå èõ öåëî÷èñëåííîñòè, òàê êàê �1 1� è �2 1� .
Òàéëû ìîæíî ðàññìàòðèâàòü êàê íîâûå óêðóïíåííûå çåðíà âû÷èñëåíèé (ìàê-
ðîîïåðàöèè), à ìíîæåñòâî âñåõ òàéëîâ, îáîçíà÷èì åãî U, — êàê îáëàñòü âû÷èñëå-
íèé àëãîðèòìà (7) íà óðîâíå ìàêðîîïåðàöèé.
Èíôîðìàöèîííàÿ çàâèñèìîñòü ìåæäó òàéëàìè j j U,
� îïðåäåëÿåòñÿ íàëè-
÷èåì òî÷åê v V è v V
� , âåêòîðà çàâèñèìîñòè � �, òàêèõ ÷òî v j , v j
� �.
Ìíîæåñòâî âñåõ âåêòîðîâ � � � �� ( , , , )1 2 � n — ýòî ìíîæåñòâî âåêòîðîâ çàâèñè-
ìîñòåé àëãîðèòìà íà óðîâíå òàéëîâ, îáîçíà÷èì åãî B.
Ìíîæåñòâî âñåõ òî÷åê v j , äëÿ êàæäîé èç êîòîðûõ ñóùåñòâóþò òî÷êè
v j
� �, îáîçíà÷èì V j ,� . Ìíîæåñòâî âåêòîðîâ � �, îïðåäåëÿþùèõ èíôîðìà-
öèîííóþ çàâèñèìîñòü ìåæäó òàéëàìè j è j
�, çàïèøåì � � .
Ïóñòü v v H Rj�
��min ( )1 1� , v v H R j
�
��� � �min ( ( ) )1 2 , � �1 2, ( ) ' R .
Òîãäà � � '� � � � � � � �� �
� { }| , , ( )H R R1 2 1 2 . Äðóãèìè ñëîâàìè, âåêòîð
� � ïðèíàäëåæèò ìíîæåñòâó � � , åñëè ñóùåñòâóþò âåêòîðû � �1 2, ( ) ' R , óäîâ-
ëåòâîðÿþùèå ðàâåíñòâó H R� � � ��
�1 2 . Åñëè äëÿ âñåõ � � ïðè ôèêñèðîâàí-
íîì � òàêèõ âåêòîðîâ � �1 2, ( ) ' R íå ñóùåñòâóåò, òî ìíîæåñòâî � � ïóñòî è òàéëû
j è j
� èíôîðìàöèîííî íåçàâèñèìû. Çàìåòèì, ÷òî ìíîæåñòâî � � áóäåò ïóñòûì,
åñëè âåêòîð � èìååò õîòÿ áû îäíó îòðèöàòåëüíóþ êîîðäèíàòó. Äåéñòâèòåëüíî, ïóñòü m-ÿ êî-
îðäèíàòà �m âåêòîðà � îòðèöàòåëüíà. Òîãäà èç îïðåäåëåíèÿ ìíîæåñòâà � � ñëåäóåò
h r r rm m m m m m m m� � �
� �
�� � � � �1 2 1 0, ÷òî ïðîòèâîðå÷èò óñëîâèþ (6).
Îïðåäåëåíèå 2. Äâà òàéëà: j j,
� áóäåì íàçûâàòü ñîñåäíèìè ïî íàïðàâ-
ëåíèþ íåíóëåâîãî âåêòîðà � Zn , åñëè êîîðäèíàòû âåêòîðà � ðàâíû 0 ëèáî 1,
à max
� �
�
� � �
�
h rm m 1, 1� �m n.
Îïðåäåëèì êîììóíèêàöèîííûé îáúåì äàííûõ, ïåðåäàâàåìûõ îò òàéëà j ê ñî-
ñåäíåìó òàéëó j
�, êàê T a b V jcomm
�
��
| |, . Çäåñü a — âðåìÿ èíèöèàëèçàöèè êàíà-
ëà ñâÿçè, b — âðåìÿ, íåîáõîäèìîå íà íåïîñðåäñòâåííóþ ïåðåäà÷ó åäèíèöû äàííûõ,
| |,V j � — êîëè÷åñòâî òî÷åê v j â ìíîæåñòâå V j , � , èëè, ÷òî òî æå ñàìîå, êîëè÷åñòâî
ðàçëè÷íûõ âåêòîðîâ �1 '( )R , äëÿ êîòîðûõ ñóùåñòâóþò ñîîòâåòñòâóþùèå âåêòî-
ðû �2 '( )R , óäîâëåòâîðÿþùèå âñåì ðàâåíñòâàì
H R� � � ��
�1 2 , � � � . (8)
Óòâåðæäåíèå 3. Ïóñòü n � 2, H H� 1 è r1 2 , r2 3 . Òîãäà âû÷èñëèòåëüíûé îáúåì
òàéëà ðàâåí T t R t r rcomp � �0 0 1 2| ( )|' , ìíîæåñòâî B èìååò âèä B � �{�1 0 1( , ) ,
� �2 310 11� �( , ), ( , )}, à êîììóíèêàöèîííûå îáúåìû òàéëà ðàâíû ñîîòâåòñòâåííî
T a b rcomm
�1
2 11�
�( ), T a brcomm
�2
2�
, T a bcomm
�3
2�
, ãäå ìíîæåñòâà âåêòîðîâ, îïðå-
äåëÿþùèõ èíôîðìàöèîííóþ çàâèñèìîñòü ìåæäó ñîñåäíèìè òàéëàìè j è j k
� ,
k �1 2 3, , , èìåþò âèä �
�
� �1 1 2
�
{ }, , �
�
� � �2 1 2 2
� �
{ }, , , �
�
� �3 1 2
�
{ }, .
Ïîêîîðäèíàòíî ðàâåíñòâà (8) çàïèøåì h rm m m m
k
m� � �
� � � �1 2 , �
�
� k ,
k �1 2 3, , , ïðè÷åì hm � � { }0 1 2, , , m �1 2, . Íî ðàâåíñòâî rm m m
� �� �1 2 0 íåâîçìîæíî
íè ïðè êàêîì âûáîðå âåêòîðîâ � �1 2, ( ) ' R , ðàâåíñòâî rm m m
� �� �1 2 1 èìååò
ìåñòî, òîëüêî åñëè � �m m mr
1 21� �, , à ðàâåíñòâî rm m m
� �� �1 2 2 âîçìîæíî, òîëüêî
åñëè � �m m mr
1 21 1� � �, , ëèáî � �m m mr
1 22� �, , m �1 2, . Ýòî ïîçâîëÿåò îïðåäåëèòü
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 167
ìíîæåñòâî ðàçëè÷íûõ ïàð âåêòîðîâ � �1 2, ( ) ' R , óäîâëåòâîðÿþùèõ (ïîêîîðäè-
íàòíî) âñåì ðàâåíñòâàì (8), è, ñëåäîâàòåëüíî, îïðåäåëèòü çíà÷åíèå | |,V j � .
Ïîñêîëüêó ìíîæåñòâî âåêòîðîâ '( )R èìååò âèä '( ) |R rm m� � �{� �Z2 1 ,
m �1 2, }, òî | ( )|' R r r� 1 2 . Âåêòîð �1 ïðèíàäëåæèò ìíîæåñòâó �
�1 , òàê êàê èìååòñÿ
r1 1� ïàð âåêòîðîâ � �1 2, ( ) ' R , �1 1� ( , )k , �2
21� �( , ),k r k r� 2 3 1, , ,� , óäîâëåò-
âîðÿþùèõ ðàâåíñòâàì � �
1
1
1
2 1� � , r2 2
1
2
2 1
� �� � . Àíàëîãè÷íî �
�1 2 � , òàê êàê
èìååòñÿ r2 1� ïàð âåêòîðîâ � �1 2, ( ) ' R , �1 1� ( , ),k �2
1 1� �( , )r k , k r� 2 3 2, , ,� ,
óäîâëåòâîðÿþùèõ ðàâåíñòâàì � �
2
1
2
2 1� � , r1 1
1
1
2 1
� �� � . Âåêòîð �1 ïðèíàäëåæèò
òàêæå ìíîæåñòâó �
�3 , ïîñêîëüêó èìååòñÿ îäíà ïàðà âåêòîðîâ � �1 2, ( ) ' R , �1 1 1� ( , ) ,
�2
1 2� ( , )r r , óäîâëåòâîðÿþùèõ ðàâåíñòâàì r1 1
1
1
2 1
� �� � , r2 2
1
2
2 1
� �� � .
Àíàëîãè÷íî îïðåäåëÿåòñÿ, ÷òî âåêòîð �2
� ïðèíàäëåæèò ìíîæåñòâó �
�2 , à âåê-
òîð �
2
— âñåì ìíîæåñòâàì �
�k k, , ,�1 2 3 .
 ïðèâåäåííîì óòâåðæäåíèè íå ó÷òåíà îñîáåííîñòü ãðàíè÷íûõ òàéëîâ. Ýòî
îïðàâäàíî, åñëè ðàçìåðû îáëàñòè V äîñòàòî÷íî âåëèêè è âëèÿíèåì ãðàíè÷íûõ
òàéëîâ ìîæíî ïðåíåáðå÷ü.
4. ÎÖÅÍÊÀ ÂÛ×ÈÑËÈÒÅËÜÍÎÃÎ È ÊÎÌÌÓÍÈÊÀÖÈÎÍÍÎÃÎ ÎÁÚÅÌΠÏÐÈ n 3
Ïóñòü n � 3 .  êà÷åñòâå ìàòðèöû H ðàññìîòðèì ìàòðèöó H2
1 1 1
1 1 1
1 1 1
� �
� �
!
"
#
#
#
$
%
&
&
&
.
Óñëîâèå îäíîòèïíîñòè òàéëîâ ýêâèâàëåíòíî òðåáîâàíèþ ÷åòíîñòè âñåõ äèàãî-
íàëüíûõ ýëåìåíòîâ ìàòðèöû R, òàê êàê | |H3 4� , �m � 2 , 1 3� �m .
Óòâåðæäåíèå 4. Ïóñòü I 2 — ÷åòíîå ÷èñëî, à I 3 — íå÷åòíîå. Òîãäà âû÷èñëè-
òåëüíûé îáúåì òàéëà ðàâåí T t
r r r
comp � 0
1 2 3
4
; ìíîæåñòâî B ñîñòîèò èç âåêòîðîâ
�1 0 0 1� ( , , ) , �2 0 1 0� ( , , ) , �3 0 1 1� ( , , ), �4 1 0 0� ( , , ) , �5 1 1 0� ( , , ) ; êîììóíèêàöèîííûé
îáúåì òàéëà ðàâåí T a b V jcomm
�
��
| |, , ãäå � �� � �k k, ,1 5 | | /
,
V r r
j �1 1 2 2� , | |
,
V
j �2 �
� �r r1 3
2 2/ , | |
,
V r
j �3 1� , | | /
,
V r r
j �4 2 3 2� , | |
,
V r
j �5 3� .
Äîêàçàòåëüñòâî ïðîâîäèòñÿ àíàëîãè÷íî ïðåäûäóùåìó ñ ó÷åòîì òîãî, ÷òî åñëè
I 2 — ÷åòíîå ÷èñëî, à I 3 — íå÷åòíîå, òî ñòðóêòóðà ìíîæåñòâà âåêòîðîâ '( )R èìååò
âèä '( ) {( , , ), ( , , ), / ,R k k k k k k k rm m� � � � � �2 2 1 2 1 2 1 2 2 1 21 2 3 1 2 3 m �1 2 3, , }, à èí-
ôîðìàöèîííàÿ çàâèñèìîñòü ñîñåäíèõ ïî íàïðàâëåíèÿì �k k, ,1 5� � òàéëîâ îïðåäåëÿ-
åòñÿ ñîîòâåòñòâóþùèìè ìíîæåñòâàìè âåêòîðîâ �
�
� � �1 1 2 3� � �{ }, , , �
�
� � �2 1 2 3
� �
{ }, , ,
�
�
� �3 1 2� �{ }, , �
�
� � �4 1 2 3
�
{ }, , , �
�
�5 3
�
{ }.
Ïóñòü n 3.  êà÷åñòâå ìàòðèöû H ðàññìîòðèì ìàòðèöó
H3
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
�
�
�
�
!
"
#
#
#
#
#
#
$
%
&
&
&
&
&
&
�
�
�
� � � � �
�
.
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
Òîãäà | | ( )
( )
H
n n
n
3
1
2 11 2� �
�
� . Óñëîâèå îäíîòèïíîñòè òàéëîâ ýêâèâàëåíòíî òðåáîâà-
íèþ ÷åòíîñòè âñåõ äèàãîíàëüíûõ ýëåìåíòîâ ìàòðèöû R. Âû÷èñëèòåëüíûé îáúåì
òàéëà ðàâåí T t r
n m
m
n
comp �
�
�
(0 1
1
1
2
. Ïðè îïðåäåëåíèè êîììóíèêàöèîííûõ îáúåìîâ
òàéëà ó÷èòûâàåòñÿ ñòðóêòóðà ìíîæåñòâà '( )R , êîòîðàÿ çàâèñèò òàêæå îò ÷åòíîñ-
òè ïàðàìåòðîâ I m nm , 2 � � .  ÷àñòíîñòè, åñëè â àëãîðèòìå (2) âñå ïàðàìåòðû
I m nm , 2 � � , — íå÷åòíûå ÷èñëà, òî
'( ) ( , , , ), ( , , , ),R k k k k k k k rn n m� � � � � �{ 2 2 2 2 1 2 1 2 1 11 2 1 2� � m / 2 , 1� �m n},
åñëè âñå ïàðàìåòðû I m nm , ,2 � � — ÷åòíûå ÷èñëà, òî
'( ) {( , , , ), ( , , , ),R k k k k k k k rn n m� � � � � �2 1 2 2 2 2 1 2 1 11 2 1 2� � m m n/ , }2 1� � .
Àíàëîãè÷íî îïðåäåëÿþòñÿ âñå äîïóñòèìûå âåêòîðû, óäîâëåòâîðÿþùèå ðà-
âåíñòâàì (8), òàê êàê âñå ðàâåíñòâà (8) èìåþò âèä h rm m m m
k
m� � �
� � � �1 2 ,
�
�
� k , �k B , ïðè÷åì hm � � { }0 1 2, , , 1� �m n.
5. ÀÏÏÐÎÊÑÈÌÀÖÈß ÌÍÎÆÅÑÒÂÀ ÒÀÉËÎÂ
Äëÿ ïîñòðîåíèÿ îöåíêè ïîëíîãî âðåìåíè ðåàëèçàöèè àëãîðèòìà íåîáõîäèìî
ÿâíî îïðåäåëèòü ìíîæåñòâî òàéëîâ.
Ïóñòü D
H
d d dn�
1
1 2
| |
( , , , )diag � , d A r A r A rk k k nk n� ÍÎÄ( , , , )1 1 2 2 � , 1� �k n.
Ââåäåì â ðàññìîòðåíèå âåêòîðû
C D H R D H H I Hn n n
�
� � �
�
��
�
�1 1 1 1 11 1 1( ( ) )
è
C D H R D H H I Hn n n
� �
�
� � �
�
�� �
� � �1 1 1 1 11 1 1( ( ) ) .
Óòâåðæäåíèå 5. Ïóñòü ðàçáèåíèå íà òàéëû îïðåäåëÿåòñÿ ìàòðèöåé H. Òîãäà
ìíîæåñòâî òàéëîâ îãðàíè÷åíî n-ìåðíûì ìíîãîãðàííèêîì
U j Z C D H Rj C j Jn
n� � � � �� � �
{ }| ,1 1 1 . (9)
Äîêàçàòåëüñòâî ñëåäóåò èç îöåíîê
H Rj H Rj H Rj H R R H v H v In n
�
�
�
�
� �
��
�
�
�1 1 1 1 11 1( ( ( ) ( )) )�
� �
�
� ��
� �
�H R R H v H v In n
1 1 1 1( ( ( ) ( ) ) )
�
�
�
� �
�H R R H v H v In n
1 11 1( ( ( ) ( )))
�
�
��
� �
�H R R H v H v In n
1 1 1 1( ( ( ) ( ) ))
�
� � �
�
�
� �
�
�H R H v H H H H In n n
1 1 1 11 1 1
�
�
�
�
� �
H R H H H In n n
1 1 11 1 1( ) ,
H Rj H Rj H Rj H R R H v H v In n
�
�
�
�
� �
��
� � �
�
1 1 1 1 1 1 1( ( ) ( ) )�
�
� � �
� �
�H R R H v H v In n
1 11 1( ( ( ) ( )) )
�
�
�
�
� �
�
�
�
H H v H v I H R H H v Hn n n n
1 1 11 1 1 1( ( ) ( ) ) ( ( ) � � �( ))v I
�
� � �
�
� �
�
�H R H v H H H H In n n
1 1 1 11 1 1
� ��
� �
�H R H H H In n n1
1 1 11 1 1( ) .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 169
6. ÎÒÎÁÐÀÆÅÍÈÅ ÍÀ ÊÎËÜÖÎ ÏÐÎÖÅÑÑÎÐÎÂ
Ïðèìåíèì LPGS-ñòðàòåãèþ ïðîñòðàíñòâåííî-âðåìåííîãî îòîáðàæåíèÿ ïîëó÷åííî-
ãî àëãîðèòìà íà êîëüöî ïðîöåññîðîâ, ñîñòîÿùåå èç çàäàííîãî ÷èñëà P âû÷èñëè-
òåëüíûõ óçëîâ (ïðîöåññîðíûõ ýëåìåíòîâ) [8]. Îöåíèì âðåìÿ ðåøåíèÿ çàäà÷è
ñâåðõó ôóíêöèåé, çàâèñÿùåé ÿâíûì îáðàçîì îò ïàðàìåòðîâ êîìïüþòåðà, ðàçìåðîâ
ñåòêè óçëîâ â àëãîðèòìå è îò ÷èñåë r m nm , ,1� � õàðàêòåðèçóþùèõ ðàçìåðû òàéëà.
Ïóñòü n � 2 , J 2 êðàòíî P è r2 êðàòíî r1. Ïðèìåíÿÿ LPGS-ñòðàòåãèþ îòîáðàæå-
íèÿ â ñîîòâåòñòâèè ñ ìåòîäèêîé, îïèñàííîé â [8], ïîëó÷àåì, ÷òî ïîëíîå âðåìÿ ðå-
øåíèÿ çàäà÷è íå ïðåâîñõîäèò çíà÷åíèÿ T:
T P t a b I I r r( , , , , , , , )0 1 2 1 2 �
� � �
�
�
!
"
##
$
%
&&
�t j J
r
r
J l( ) ( ) ( ) ( )mamax � �2 2 1
2
1
21 1 1 1) x ,0 1
2
1
2� �l
r
r
P P�
!
"
##
$
%
&& �
�
�
�
�
�
�
,
ãäå � �
(max( , ), )T T T Tcomp comm comp comm , l
r
r
I
r
�
��
�
�
�
�1
22
1
2
1
, ) � J P2 / , Tcomm �
�
T Tcomm comm
� �1 3
.
Ïðè ïîñòðîåíèè îöåíêè T P t a b I I r r( , , , , , , , )0 1 2 1 2 ó÷òåíà âîçìîæíîñòü ñîâìåùå-
íèÿ ïðîöåññà ïåðåäà÷è ñ ïðîöåññîì âûïîëíåíèÿ îïåðàöèé òàéëîâ, îòîáðàæåííûõ
íà îäèí è òîò æå âû÷èñëèòåëüíûé óçåë. Âðåìÿ ïåðåäà÷è äàííûõ ìåæäó òàéëàìè,
îòîáðàæåííûìè íà îäèí óçåë, ïðèíÿòî ðàâíûì 0, òàê êàê ôèçè÷åñêè äàííûå
îñòàþòñÿ â ïàìÿòè ïðîöåññîðíîãî ýëåìåíòà.
Ìèíèìèçàöèÿ ôóíêöèè
T P t a b I I r r( , , , , , , , )0 1 2 1 2 ïîçâî-
ëÿåò ïîëó÷èòü àëãîðèòì ñ íàè-
ëó÷øèì âðåìåíåì ðåàëèçàöèè íà
çàäàííîì êîëüöå ïðîöåññîðîâ.
 ÷àñòíîñòè åñëè ïðèíÿòü çíà÷å-
íèÿ ïàðàìåòðîâ P �10,
t0
910� � ñ, a � �10 6 ñ, b � �10 8 ñ,
I1
62 10� � è I 2
310� , òî îïòè-
ìàëüíîå çíà÷åíèÿ ôóíêöèè T
äîñòèãàþòñÿ ïðè r r1 2 56� � è
ðàâíî 0,207 ñ. Íà ðèñ. 1 èçî-
áðàæåíà ïîâåðõíîñòü çíà÷åíèé
ôóíêöèè T â çàâèñèìîñòè îò
ïàðàìåòðîâ òàéëà r1 è r2 .
 ñëó÷àå n � 3 ïðèìåíåíèå LPGS-ñòðàòåãèè îòîáðàæåíèÿ ïî ìåòîäèêå [8] ïî-
çâîëÿåò îöåíèòü âðåìÿ ðåøåíèÿ çàäà÷è ôóíêöèåé
T P t a b I I I r r r( , , , , , , , , , )0 1 2 3 1 2 3 �
� �
�
�
�
!
"
##
$
� � �2 2 3 3 1 3
2
1
21 1 1 0 1( ) ( ) ( ) max , ( )J J lJ
r
r
J)
%
&&�
�
�
�
�
�
�
�2 P ,
ãäå
�1 0
1 2 3 1 2
4 2
2�
�
!
"
#
$
%
&
!
"
##
$
%
&&max ,t
r r r
a b
r r
, �2 0
1 2 3 1 2
4 2
2�
�
!
"
#
$
%
&t
r r r
a b
r r
, � �3 1� l ,
J I I I r J I I I r J P2 1 2 3 2 3 1 2 3 3 22 2� �
� � � �
� � �( ) / , ( ) / , /) ,
l
r
r
I
r
�
��
�
�
�
�2 2
22
1
2
1
.
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1
500
1000
1500
r1 20
40
60
80
100
r2
0
2
4
6
T
2000
Ðèñ. 1
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. R a m a n u j a m J . , S a d a y a p p a a n P . Tiling of iteration spaces for multicomputers // Proc. of Int.
Conf. on Parallel Proces. — 1990. — 2. — P. 179–186.
2. B o u l e t P . , D a r t e A . , R i s s e t T . , R o b e r t Y . (Pen)-ultimate tiling? // Integration, The VLSI J.
— 1994. — 17. — P. 33–51.
3. X u e J . Communication-minimal tiling of uniform dependence loops // J. of Parallel and Distributed
Comput. — 1997. — 1, N 42. — P. 42–59.
4. S c h r e i b e r R . , D o n g a r r a J . Automatic blocking of nested loops // Tech. rep. 90.38, RIACS. 1997.
5. O h t a H . , S a i t o Y . , K a i n a g a M . , O n o H . Optimal tile size adjustment in compiling general
DOACROSS loop nests // Proc. of Int. Conf. on Supercomput. ACM Press, 1995. — P. 270–279.
6. H o d z i c E . , S h a n g W . On supernode transformation with minimized total running time // IEEE Trans.
Parallel and Distributed Systems. — 1998. — 9, N 5. — P. 417–428.
7. H o d z i c E . , S h a n g W . On-time optimal supernode shape // IEEE Trans. Parallel and Distributed Sys-
tems. — 2002. — 13, N 10. — P. 1220–1223.
8. Á à õ à í î â è ÷ Ñ .  . , Ñ î á î ë å â ñ ê è é Ï . È . Îòîáðàæåíèå àëãîðèòìîâ íà âû÷èñëèòåëüíûå
ñèñòåìû ñ ðàñïðåäåëåííîé ïàìÿòüþ: îïòèìèçàöèÿ òàéëèíãà äëÿ îäíî- è äâóìåðíûõ òîïîëîãèé //
Âåñöi ÍÀÍ Áåëàðóñi. Ñåð. ôiç.-ìàò. íàâóê. — 2006. — ¹ 2. — Ñ. 106–112.
9. Á à õ à í î â è ÷ Ñ . Â . , Ñ î á î ë å â ñ ê è é Ï . È . Îïòèìèçàöèÿ òàéëèíãà ïðè LSGP ñòðàòåãèè
îòîáðàæåíèÿ àëãîðèòìîâ íà ñóïåðêîìïüþòåðû ñ ðàñïðåäåëåííîé ïàìÿòüþ // Òàì æå — 2007. — ¹ 3.
— Ñ. 113–118.
Ïîñòóïèëà 24.07.2008
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2010, ¹ 1 171
|
| id | nasplib_isofts_kiev_ua-123456789-45136 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-12-07T16:18:27Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Соболевский, П.И. Баханович, С.В. Горбач, А.Н. 2013-06-07T19:55:00Z 2013-06-07T19:55:00Z 2010 Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров / П.И. Соболевский, С.В. Баханович, А.Н. Горбач // Кибернетика и системный анализ. — 2010. — № 1. — С. 163-171. — Бібліогр.: 9 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/45136 681.3.012 + 519.6 Досліджено задачу оптимізації тайлінга при розв’язанні першої краєвої задачі для багатомірного рівняння теплопровідності на обчислювальних системах з розподіленою пам’яттю. Наведено оцінки об’єма комунікацій і обчислень. Задачу оптимізації тайлінга зведено до задачі мінімізації функції, що явно виражає залежність часу реалізації алгоритму від розмірів тайла і параметрів цільового суперкомп’ютера. The problem of tiling optimization in solving the heat equation on supercomputers with distributed memory is investigated. Estimates of amounts of computation and communication are obtained. The tiling optimization is reduced to the minimization of the algorithm execution time as a function of the tile size, size of computing environment, processor performance, and latency and bandwidth of communication channels. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Программно-технические комплексы Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров Оптимізація тайлінга при числовому розв’язанні багатомірного рівняння теплопровідності на кільці процесорів Tiling optimization in solving the heat equation on a ring of processors Article published earlier |
| spellingShingle | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров Соболевский, П.И. Баханович, С.В. Горбач, А.Н. Программно-технические комплексы |
| title | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров |
| title_alt | Оптимізація тайлінга при числовому розв’язанні багатомірного рівняння теплопровідності на кільці процесорів Tiling optimization in solving the heat equation on a ring of processors |
| title_full | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров |
| title_fullStr | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров |
| title_full_unstemmed | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров |
| title_short | Оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров |
| title_sort | оптимизация тайлинга при численном решении многомерного уравнения теплопроводности на кольце процессоров |
| topic | Программно-технические комплексы |
| topic_facet | Программно-технические комплексы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/45136 |
| work_keys_str_mv | AT sobolevskiipi optimizaciâtailingapričislennomrešeniimnogomernogouravneniâteploprovodnostinakolʹceprocessorov AT bahanovičsv optimizaciâtailingapričislennomrešeniimnogomernogouravneniâteploprovodnostinakolʹceprocessorov AT gorbačan optimizaciâtailingapričislennomrešeniimnogomernogouravneniâteploprovodnostinakolʹceprocessorov AT sobolevskiipi optimízacíâtailíngapričislovomurozvâzanníbagatomírnogorívnânnâteploprovídnostínakílʹcíprocesorív AT bahanovičsv optimízacíâtailíngapričislovomurozvâzanníbagatomírnogorívnânnâteploprovídnostínakílʹcíprocesorív AT gorbačan optimízacíâtailíngapričislovomurozvâzanníbagatomírnogorívnânnâteploprovídnostínakílʹcíprocesorív AT sobolevskiipi tilingoptimizationinsolvingtheheatequationonaringofprocessors AT bahanovičsv tilingoptimizationinsolvingtheheatequationonaringofprocessors AT gorbačan tilingoptimizationinsolvingtheheatequationonaringofprocessors |