Смешанный клеточный метод умножения матриц
Запропоновано змішаний клітинний метод множення матриць, який сполучає метод Штрассена зі швидким клітинним методом множення матриць, взаємодія яких мінімізує на 25 % мультиплікативну та адитивну складності відомих алгоритмів матричного множення. Наведено оцінки обчислювальної складності клітинних...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2009 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2009
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/44302 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Смешанный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2009. — № 1. — С. 22-27. — Бібліогр.: 12 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-44302 |
|---|---|
| record_format |
dspace |
| spelling |
Елфимова, Л.Д. 2013-05-28T19:03:26Z 2013-05-28T19:03:26Z 2009 Смешанный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2009. — № 1. — С. 22-27. — Бібліогр.: 12 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44302 681.322.012 Запропоновано змішаний клітинний метод множення матриць, який сполучає метод Штрассена зі швидким клітинним методом множення матриць, взаємодія яких мінімізує на 25 % мультиплікативну та адитивну складності відомих алгоритмів матричного множення. Наведено оцінки обчислювальної складності клітинних аналогів зазначених алгоритмів, отриманих на основі змішаного методу. A mixed cellular method of matrix multiplication is proposed that combines the Strassen method with a fast cellular method of matrix multiplication. The interaction of these methods makes it possible to decrease the multiplicative and additive complexities of well-known matrix multiplication algorithms by 25%. Estimates of computational complexity of cellular analogues of the mentioned algorithms are given. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Смешанный клеточный метод умножения матриц Змішаний клітинний метод множення матриць A mixed cellular method of matrix multiplication Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Смешанный клеточный метод умножения матриц |
| spellingShingle |
Смешанный клеточный метод умножения матриц Елфимова, Л.Д. Кибернетика |
| title_short |
Смешанный клеточный метод умножения матриц |
| title_full |
Смешанный клеточный метод умножения матриц |
| title_fullStr |
Смешанный клеточный метод умножения матриц |
| title_full_unstemmed |
Смешанный клеточный метод умножения матриц |
| title_sort |
смешанный клеточный метод умножения матриц |
| author |
Елфимова, Л.Д. |
| author_facet |
Елфимова, Л.Д. |
| topic |
Кибернетика |
| topic_facet |
Кибернетика |
| publishDate |
2009 |
| language |
Russian |
| container_title |
Кибернетика и системный анализ |
| publisher |
Інститут кібернетики ім. В.М. Глушкова НАН України |
| format |
Article |
| title_alt |
Змішаний клітинний метод множення матриць A mixed cellular method of matrix multiplication |
| description |
Запропоновано змішаний клітинний метод множення матриць, який сполучає метод Штрассена зі швидким клітинним методом множення матриць, взаємодія яких мінімізує на 25 % мультиплікативну та адитивну складності відомих алгоритмів матричного множення. Наведено оцінки обчислювальної складності клітинних аналогів зазначених алгоритмів, отриманих на основі змішаного методу.
A mixed cellular method of matrix multiplication is proposed that combines the Strassen method with a fast cellular method of matrix multiplication. The interaction of these methods makes it possible to decrease the multiplicative and additive complexities of well-known matrix multiplication algorithms by 25%. Estimates of computational complexity of cellular analogues of the mentioned algorithms are given.
|
| issn |
0023-1274 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/44302 |
| citation_txt |
Смешанный клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2009. — № 1. — С. 22-27. — Бібліогр.: 12 назв. — рос. |
| work_keys_str_mv |
AT elfimovald smešannyikletočnyimetodumnoženiâmatric AT elfimovald zmíšaniiklítinniimetodmnožennâmatricʹ AT elfimovald amixedcellularmethodofmatrixmultiplication |
| first_indexed |
2025-11-26T00:05:06Z |
| last_indexed |
2025-11-26T00:05:06Z |
| _version_ |
1850591274366664704 |
| fulltext |
ÓÄÊ 681.322.012
Ë.Ä. ÅËÔÈÌÎÂÀ
ÑÌÅØÀÍÍÛÉ ÊËÅÒÎ×ÍÛÉ ÌÅÒÎÄ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ
Êëþ÷åâûå ñëîâà: ìåòîä Øòðàññåíà, áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ
ìàòðèö, ìàòðè÷íûå âû÷èñëèòåëüíûå ñèñòåìû.
Îðãàíèçàöèÿ ìàòðè÷íûõ âû÷èñëåíèé ÿâëÿåòñÿ ïðåäìåòîì èíòåíñèâíûõ òåîðåòè-
÷åñêèõ è ýêñïåðèìåíòàëüíûõ èññëåäîâàíèé. Ïåðåõîä ê âåðõíåìó óðîâíþ îðãàíè-
çàöèè âû÷èñëåíèé, îáðàçîâàííîìó îïåðàöèÿìè íàä êëåòêàìè ìàòðèö, ïðèâîäèò
ê äàëüíåéøåìó óâåëè÷åíèþ ñòåïåíè âíóòðåííåãî ïàðàëëåëèçìà ðåàëèçóåìûõ àë-
ãîðèòìîâ, äîñòèæåíèþ áîëåå âûãîäíîãî ñîîòíîøåíèÿ ìåæäó îáúåìîì âû÷èñëå-
íèé è íàêëàäíûìè ðàñõîäàìè íà îðãàíèçàöèþ âû÷èñëåíèé, îñîáåííî íà îáìåí
äàííûìè.  ñâÿçè ñ ýòèì äèíàìè÷íî ðàçðàáàòûâàþòñÿ ìàòðè÷íûå âû÷èñëèòåëü-
íûå ñèñòåìû, îðèåíòèðîâàííûå íà ðåàëèçàöèþ êëåòî÷íûõ àëãîðèòìîâ, à òàêæå
ìóëüòèïðîöåññîðíûå ñèñòåìû, â êîòîðûõ îäíîâðåìåííî èñïîëüçóåòñÿ ïàðàëëå-
ëèçì ðàçëè÷íûõ óðîâíåé: îò âåêòîðíèõ îïåðàöèé, ðåàëèçóåìûõ â âåêòîðíûõ ïðî-
öåññîðíûõ ýëåìåíòàõ (ÏÝ), äî êëåòî÷íûõ îïåðàöèé, ïîä êîòîðûå âûäåëÿþòñÿ
îòäåëüíûå êëàñòåðû ÏÝ [1–3]. Êðîìå òîãî, ïðîöåññîðíûå ìàññèâû ñ ñèñòîëè÷åñ-
êîé îðãàíèçàöèåé âû÷èñëåíèé [4] òàêæå ïîçâîëÿþò èñïîëüçîâàòü êàê ñðåäíå-,
òàê è êðóïíîìàñøòàáíûå óðîâíè ïàðàëëåëèçìà çà ñ÷åò ââåäåíèÿ â ñîñòàâ ÏÝ ðå-
øàþùåãî ïîëÿ äîïîëíèòåëüíîé ëîêàëüíîé ïàìÿòè, ÷òî äàåò âîçìîæíîñòü ðåøàòü
çàäà÷è ïðîèçâîëüíûõ ðàçìåðîâ íà óêàçàííûõ ïðîöåññîðíûõ ìàññèâàõ ñ ôèêñèðî-
âàííûì ÷èñëîì ÏÝ, íåçàâèñèìûì îò ðàçìåðîâ ìàññèâîâ âõîäíûõ äàííûõ [5].
Êëåòî÷íûå ìåòîäû ðåøåíèÿ çàäà÷ áîëüøèõ ðàçìåðîâ íàèáîëåå øèðîêî èñïîëü-
çóþòñÿ â ëèíåéíîé àëãåáðå [6], îäíîé èç áàçîâûõ îïåðàöèé êîòîðîé ÿâëÿåòñÿ îïåðà-
öèÿ ìàòðè÷íîãî óìíîæåíèÿ.  ðàáîòå [7] âïåðâûå ïðåäñòàâëåí áûñòðûé êëåòî÷íûé
ìåòîä óìíîæåíèÿ ìàòðèö, ïîçâîëÿþùèé âàðüèðîâàòü ðàçìåð êëåòîê, íà êîòîðûå äå-
êîìïîçèðóþòñÿ èñõîäíûå ìàòðèöû, è ïîëó÷àòü êëåòî÷íûå àíàëîãè èçâåñòíûõ àëãî-
ðèòìîâ óìíîæåíèÿ ìàòðèö ñ ìèíèìèçèðîâàííûìè íà 12,5 % ìóëüòèïëèêàòèâíîé
è àääèòèâíîé ñëîæíîñòÿìè.
Öåëü íàñòîÿùåé ðàáîòû — óìåíüøåíèå âû÷èñëèòåëüíîé ñëîæíîñòè êëåòî÷íûõ
àíàëîãîâ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ.  äàííîé ñòàòüå ðàññìàòðèâàåòñÿ ñìå-
øàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö, ñî÷åòàþùèé ìåòîä Øòðàññåíà [8]
ñ áûñòðûì êëåòî÷íûì ìåòîäîì óìíîæåíèÿ ìàòðèö [7], âçàèìîäåéñòâèå êîòîðûõ ïðè-
âîäèò ê ïîëó÷åíèþ êëåòî÷íûõ àíàëîãîâ èçâåñòíûõ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ
ñ ìèíèìèçèðîâàííûìè íà 25 % ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòÿìè.
Èñõîäíûå ìàòðèöû A è B ïîðÿäêà n � 2� ( )� � 3 , êîòîðûå äåêîìïîçèðóþòñÿ íà
êëåòêè Aij è Bij ïîðÿäêà 2q ( )q � �� 3 , ïðåäñòàâëåíû íà ðèñ. 1, ãäå m
n
q
q� � �
2
2� ,
� �� � � �m q
2
2 1, i j m, , ,� 1� .
Êàæäàÿ èç ïîëó÷åííûõ êëåòî÷íûõ ìàòðèö A è B ïîðÿäêà m ðàçáèâàåòñÿ, â ñâîþ
î÷åðåäü, íà ÷åòûðå êëåòî÷íûå ïîäìàòðèöû Aij
rs è Bij
rs ïîðÿäêà �, ãäå íèæíèå èíäåê-
ñû i j, ,� 1 2 ïîêàçûâàþò ìåñòî ýòèõ ïîäìàòðèö â ïîëíîé ( )m m� -ìàòðèöå, à âåðõíèå
èíäåêñû r, s m� �� � � �� — ñîîòâåòñòâåííî ÷èñëî ìàòðè÷íûõ ñòðîê è ÷èñëî ìàòðè÷-
íûõ ñòîëáöîâ ïîäìàòðèö. Ðåçóëüòàòîì óìíîæåíèÿ êëåòî÷íûõ ìàòðèö A è B ÿâëÿåò-
ñÿ ìàòðèöà C , êîòîðàÿ èìååò àíàëîãè÷íóþ êàæäîìó èç ñîìíîæèòåëåé êëåòî÷íóþ
ñòðóêòóðó (ñì. ðèñ. 1).
Ñî÷åòàíèå äâóõ ìåòîäîâ îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðàçîì. Êàê èçâåñòíî,
ìåòîä Øòðàññåíà óìíîæåíèÿ ìàòðèö ïîðÿäêà n, ìóëüòèïëèêàòèâíàÿ ñëîæíîñòü êî-
22 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
© Ë.Ä. Åëôèìîâà, 2009
òîðîãî ðàâíà O n( ),2 807 , òðåáóåò log 2n ðåêóðñèâíûõ øàãîâ [8]. Ðàññìîòðèì ïåðâûé
øàã ðåêóðñèè ýòîãî ìåòîäà, êîòîðûé õîðîøî àäàïòèðîâàí ê ïàðàëëåëüíîé îáðàáîò-
êå è ÷àñòî èñïîëüçóåòñÿ äëÿ ðàñïàðàëëåëèâàíèÿ âû÷èñëåíèé [9].  ýòîì ñëó÷àå ìå-
òîä Øòðàññåíà â ìàòðè÷íîì âèäå ïðèìåíèòåëüíî ê êëåòî÷íûì ïîäìàòðèöàì ïîðÿä-
êà � çàïèøåì cëåäóþùèì îáðàçîì:
Z A A B B
m m m m1
11 22 11 22
� � �� � � �
( ) ( )
( , ) ( , ) ( , ) ( , )� � � � � � � �
,
Z A A B
m m m2
21 22 11
� �� � �
( )
( , ) ( , ) ( , )� � � � � �
,
Z A B B
m m m3
11 12 22
� �� � �( , ) ( , ) ( , )
( )
� � � � � �
,
Z A B B
m m m4
22 21 11
� �� � �( , ) ( , ) ( , )
( )
� � � � � �
, (1)
Z A A B
m m m5
11 12 22
� � � � �
( )
( , ) ( , ) ( , )� � � � � �
,
Z A A B B
m m6
21 11 11 12
� � �� �
( ) ( )
( , ) ( , ) ( , ) ( , )� � � � � � � �
,
Z A A B B
m m m m m m7
12 22 21 22
� � �� � � � � �
( ) (
( , ) ( , ) ( , ) ( ,� � � � � � � �)
);
C Z Z Z Z
11
1 4 5 7( , )� � � � � � , C Z Z
m
12
3 5( , )� �� � � ,
C Z Zm
21
2 4( , )� � �� � , C Z Z Z Zm m
22
1 2 3 6( , )� � � � � �� � .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 23
(2)
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
���
�
�
�
���
�
�
�
���
�
�
�
mmmmm
mmm
m
m
m
m
mmmmm
mmm
m
m
m
m
mmmmm
mmm
m
m
m
m
CCCC
CC
CCCC
CCCCC
CC
CCCCC
BBBB
BB
BBBB
BBBBB
BB
BBBBB
AAAA
AA
AAAA
AAAAA
AA
AAAAA
��
����
��
�
����
�
��
����
��
�
����
�
��
����
��
�
����
�
�
�
�
�
�
�
1,1
)(
22
)(
21
,11,1,11,1
121
),(
12
),(
11
11,111211
1,1
)(
22
)(
21
,11,1,11,1
121
),(
12
),(
11
11,111211
1,1
)(
22
)(
21
,11,1,11,1
121
),(
12
),(
11
11,111211
���
������
�����������
��������
����
��
���
������
�����������
��������
����
��
���
������
�����������
��������
����
��
A B
2
q
2
q
2
q
2
q
2
q
2
q
C
Ðèñ. 1
 îòëè÷èå îò ìåòîäà Øòðàññåíà, êîòîðûé îïåðèðóåò ÷èñëîâûìè ïîäìàòðèöàìè
ïîðÿäêà n /2, â âû÷èñëèòåëüíîì ïðîöåññå ñîãëàñíî ôîðìóëàì (1) è (2) ó÷àñòâó-
þò êëåòî÷íûå ïîäìàòðèöû ïîðÿäêà �, äåêîìïîçèðîâàííûå íà êëåòêè çàäàííîãî
ïîðÿäêà 2q , è âû÷èñëåíèå ìàòðè÷íûõ ïðîèçâåäåíèé îñóùåñòâëÿåòñÿ ñ èñïîëüçî-
âàíèåì áûñòðîãî êëåòî÷íîãî ìåòîäà óìíîæåíèÿ ìàòðèö [7]. Òàêîå ñî÷åòàíèå
äâóõ ìåòîäîâ îáðàçóåò ñìåøàííûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö, êîòî-
ðûé ôîðìàëèçóåì ñëåäóþùèì îáðàçîì.
Îáîçíà÷èì ñóììû êëåòî÷íûõ ( )� �� -ïîäìàòðèö, âõîäÿùèå â (1), X i è Y i
( , , , )i � 1 2 5� :
X A A
m m1
11 22
� � � �
( )
( , ) ( , )� � � �
, Y B B
m m1
11 22
� � � �
( )
( , ) ( , )� � � �
,
X A A
m m m2
21 22
� �� � �
( )
( , ) ( , )� � � �
, Y B B
m m m2
12 22
� �� � �
( )
( , ) ( , )� � � �
,
X A A
m3
11 12
� � �
( )
( , ) ( , )� � � �
, Y B B
m3
21 11
� ��
( )
( , ) ( , )� � � �
, (3)
X A A
m4
21 11
� ��
( )
( , ) ( , )� � � �
, Y B B
m4
11 12
� � �
( )
( , ) ( , )� � � �
,
X A A
m m m5
12 22
� �� � �
( )
( , ) ( , )� � � �
, Y B B
m m m5
21 22
� �� � �
( )
( , ) ( , )� � � �
.
Òîãäà âûðàæåíèå (1) ïðèìåò ñëåäóþùèé âèä:
Z X Y Z X B Z A Y
Z A
m m
1 1 1 2 2
11
3
11
2
4
22
� � �
� � �
, , ,
( , ) ( , )
( ,
� � � �
� �) ( , )
, , , .Y Z X B Z X Y Z X Y
m m3 5 3
22
6 4 4 7 5 5� � �� �� �
(4)
Íà ïåðâîì ýòàïå ñìåøàííîãî êëåòî÷íîãî ìåòîäà, ïðèìåíÿÿ èçâåñòíóþ îïåðà-
öèþ ìàòðè÷íîãî ñëîæåíèÿ [10] è îïåðèðóÿ êëåòêàìè ìàòðèö ïîðÿäêà 2q , âû÷èñëÿ-
åì ìàòðè÷íûå ñóììû ñîãëàñíî (3) ïî ñëåäóþùèì ôîðìóëàì:
X A Aij ij i j
1 � � � �( ),� � , Y B Bij ij i j
1 � � � �( ),� � ,
X A Aij i j i j
2 � �� � �( ), ,� � � , Y B Bij i j i j
2 � �� � �( ), ,� � � ,
X A Aij ij i j
3 � � �( ), � , Y B Bij i j ij
3 � ��( ),� , (5)
X A Aij i j ij
4 � ��( ),� , Y B Bij ij i j
4 � � �( ), � ,
X A Aij i j i j
5 � �� � �( ), ,� � � , Y B Bij i j i j
5 � �� � �( ), ,� � � ,
ãäå i j, , ,� 1� �.
Íà âòîðîì ýòàïå âû÷èñëÿåì ñåìü ìàòðè÷íûõ ïðîèçâåäåíèé Z Z Z1 2 7, , ,� ñî-
ãëàñíî ôîðìóëå (4), äëÿ ðåàëèçàöèè êàæäîãî èç êîòîðûõ ïðèìåíÿåì êëåòî÷íûé ìå-
òîä ìàòðè÷íîãî óìíîæåíèÿ [7]. Äëÿ íàõîæäåíèÿ ïåðâîãî ìàòðè÷íîãî ïðîèçâåäåíèÿ
Z1 èñïîëüçóþòñÿ êëåòî÷íûå ïîäìàòðèöû-îïåðàíäû X 1 è Y 1 ïîðÿäêà �, êîòîðûå
èçîáðàæåíû íà ðèñ. 2.
24 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
11
2
1
1
1
2
1
22
1
21
1
1
1
12
1
11
11
2
1
1
1
2
1
22
1
21
1
1
1
12
1
11
11
2
1
1
1
2
1
22
1
21
1
1
1
12
1
11
����
�
�
����
�
�
����
�
�
ZZZ
ZZZ
ZZZ
YYY
YYY
YYY
XXX
XXX
XXX
�
����
�
�
�
����
�
�
�
����
�
�
X
1
2
q
Y
1
Z
1
2
q
2
q � 1 2
q
2
q 2
q
Ðèñ. 2
Ñîãëàñíî êëåòî÷íîìó ìåòîäó [7] âíà÷àëå îïðåäåëÿþòñÿ ìàòðè÷íûå êîýôôèöè-
åíòû Rik è Fkj :
R X X
ik i k i k
1
2 1 2 1
1
2 2
1� �
� �
( )
, ,
, F Y Y
kj k j k j
1
2 1 2 1
1
2 2
1� �
� �
( )
, ,
,
R X X
ik i k i k
2
2 2 1
1
2 2
1� �
�
( )
, ,
, F Y Y
kj k j k j
2
2 1 2
1
2 2
1� �
�
( )
, ,
,
R X X
ik i k i k
3
2 1 2 1
1
2 1 2
1� �
� � �
( )
, ,
, F Y Y
kj k j k j
3
2 2 1
1
2 1 2 1
1� �
� � �
( )
, ,
, (6)
R X X
ik i k i k
4
2 2 1
1
2 1 2 1
1� �
� � �
( )
, ,
, F Y Y
kj k j k j
4
2 1 2 1
1
2 1 2
1� �
� � �
( )
, ,
,
R X X
ik i k i k
5
2 1 2
1
2 2
1� �
�
( )
, ,
, F Y Y
kj k j k j
5
2 2 1
1
2 2
1� �
�
( )
, ,
,
ãäå i j k p, , , , ,� 1 2 � ; p
n n
q q
q� � �
� �
� �/
.
2
2 2
2
1 2
2�
Çàòåì âûïîëíÿþòñÿ ðåãóëÿðíûå âû÷èñëåíèÿ ìàòðèö Qij :
Q R Fij
k
p
ik kj
1
1
1 1�
�
� , Q R Yij
k
p
ik k j
2
1
2
2 1 2 1
1�
�
� �� ,
,
Q X Fij
k
p
i k kj
3
1
2 1 2 1
1 2�
�
� �� ,
, Q X Fij
k
p
i k kj
4
1
2 2
1 3�
�
� ,
, Q R Yij
k
p
ik k j
5
1
3
2 2
1�
�
� ,
, (7)
Q R Fij
k
p
ik kj
6
1
4 4�
�
� , Q R Fij
k
p
ik kj
7
1
5 5�
�
� ,
ãäå i j k p, , , , ,� 1 2 � .
 çàêëþ÷åíèå âû÷èñëÿþòñÿ ìàòðèöû Zij
1 :
Z Q Q Q Q
i j ij ij ij ij2 1 2 1
1 1 4 5 7
� �
� � � �
,
, Z Q Q Z Q Q
i j ij ij i j ij ij2 1 2
1 3 5
2 2 1
1 2 4
� �
� � � �
, ,
, ,
(8)
Z Q Q Q Q
i j ij ij ij ij2 2
1 1 2 3 6
,
� � � � ,
ãäå i j p, , , ,� 1 2 � .
Àíàëîãè÷íûì îáðàçîì îïðåäåëÿåì îñòàëüíûå ìàòðè÷íûå ïðîèçâåäåíèÿ Z 2 ,
Z Z3 7, ,� ñîãëàñíî (4).
Ïîñëå âû÷èñëåíèÿ óêàçàííûõ ïðîèçâåäåíèé, íà òðåòüåì, îêîí÷àòåëüíîì, ýòàïå
ñìåøàííîãî êëåòî÷íîãî ìåòîäà âû÷èñëÿåì ðåçóëüòèðóþùèå ìàòðèöû Cij ïîðÿäêà
2q ïî ñëåäóþùèì ôîðìóëàì:
C Z Z Z Zij ij ij ij ij� � � �1 4 5 7 , C Z Zi j ij ij, ,�� � �3 5
(9)
C Z Zi j ij ij�� � �, ,2 4 C Z Z Z Zi j ij ij ij ij� �� � � � � �,
1 2 3 6 ,
ãäå i j, , , ,� 1 2 � �.
Ïåðåéäåì ê îöåíêå âû÷èñëèòåëüíîé ñëîæíîñòè êëåòî÷íûõ àíàëîãîâ èçâåñòíûõ
àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ, êîòîðûå ìîãóò áûòü ïîëó÷åíû íà îñíîâå ìåòî-
äà (4)–(9). Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (5) è (9) ýòîò ìåòîä òðåáóåò ñî-
îòâåòñòâåííî 10 2� è 8 2� ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ. Äëÿ êàæäîé ìàòðè÷íîé
îïåðàöèè ñëîæåíèÿ âíóòðåííèé àëãîðèòì òðåáóåò 22q ñêàëÿðíûõ îïåðàöèé ñëîæå-
íèÿ. Òàêèì îáðàçîì, ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (5) è (9), îïðå-
äåëÿåìàÿ êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, ñîñòàâëÿåò
W W W
mq q
a a a
( , ) ( ) ( )5 9 5 9 2 2 2 2
2
10 2 8 2 18
2
2� � � � � � �
�
�
�
�
�
� �� � 2q �
�
�
�
��
�
�
�� � �
�
18
2
2 4 5
1
2
2 2n
n
q
q , (îïåðàöèé ñëîæåíèÿ).
Îöåíèì ñëîæíîñòü âû÷èñëåíèÿ îäíîãî èç ñåìè ìàòðè÷íûõ ïðîèçâåäåíèé Z1,
ò.å. âû÷èñëåíèé (6), (7) è (8). Ïðè îïðåäåëåíèè ìàòðè÷íûõ êîýôôèöèåíòîâ (6) è
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1 25
ìàòðèö Zij
1 (8) âíåøíèå àëãîðèòìû òðåáóþò ñîîòâåòñòâåííî 10 2p è 8 2p ìàòðè÷íûõ
îïåðàöèé ñëîæåíèÿ, äëÿ êàæäîé èç êîòîðûõ âíóòðåííèé àëãîðèòì òðåáóåò 22q ñêà-
ëÿðíûõ îïåðàöèé ñëîæåíèÿ. Ñëåäîâàòåëüíî, ñóììàðíàÿ àääèòèâíàÿ ñëîæíîñòü âû-
÷èñëåíèé (6) è (8) ñîñòàâèò
W p p
n nq q
q
q
qa
( , )6 8 2 2 2 2
2
2
210 2 8 2 10
2
2 8
2
� � � � �
�
�
��
�
�
�� � �
� �
�
�
��
�
�
�� � �
2
2
22 q
� � �0 625 0 5 11252 2 2, , ,n n n (îïåðàöèé ñëîæåíèÿ).
Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (7) âíåøíèé àëãîðèòì òðåáóåò 7 3p ìàò-
ðè÷íûõ îïåðàöèé óìíîæåíèÿ è 7 3 2( )p p� ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ.
Èñïîëüçóÿ â êà÷åñòâå âíóòðåííåãî àëãîðèòìà òðàäèöèîííûé àëãîðèòì ìàòðè÷-
íîãî óìíîæåíèÿ [10], êîòîðûé òðåáóåò 23q ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ è
( )2 23 2q q� ñêàëÿðíûõ îïåðàöèé ñëîæåíèÿ, ïîëó÷àåì äëÿ ìóëüòèïëèêàòèâíîé ñëîæ-
íîñòè, îïðåäåëÿåìîé êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ, è àääèòèâíîé
ñëîæíîñòè âû÷èñëåíèé (7) ñëåäóþùèå çíà÷åíèÿ:
W p
n
nq
q
q
ì
(7) � � �
�
�
��
�
�
�� � �
�
7 2 7
2
2 01093 3
2
3
3 3, (îïåðàöèé óìíîæåíèÿ),
W p p
n nq q
q
q
qà
(7) � � � � �
�
�
��
�
�
�� � �
�
�� �
7 2 2 7
2
2
2
3 3 2 2
2
3
3
2
( ) ��
�
�
�� �
�
�
�
�
�
�
2
22 q
� �0109 0 4373 2, ,n n (îïåðàöèé ñëîæåíèÿ).
Òàêèì îáðàçîì, íà îñíîâå ïðåäëîæåííîãî ñìåøàííîãî êëåòî÷íîãî ìåòîäà (4)–(9)
ïîëó÷àåì êëåòî÷íûé àíàëîã òðàäèöèîííîãî àëãîðèòìà ñî ñëåäóþùèìè çíà÷åíèÿìè
ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòåé:
W W n nì ì
(7)� � � �7 7 0109 0 7633 3, , (îïåðàöèé óìíîæåíèÿ),
W W W W n nà à
(6,8)
à
(7)
à
(5,9)� � � � � �7 7 1125 0109 0 432 3( ) ( , , , 7 4 52 2n n) ,� �
� �0 763 9 3163 2, ,n n (îïåðàöèé ñëîæåíèÿ).
Àíàëîãè÷íûì îáðàçîì ðàññ÷èòûâàþòñÿ ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæ-
íîñòè êëåòî÷íûõ àíàëîãîâ äðóãèõ èçâåñòíûõ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ,
çíà÷åíèÿ êîòîðûõ ïðèâåäåíû â òàáë. 1.
Ïðåäëîæåííûé ìåòîä íàèáîëåå ýôôåêòèâåí ïðè áîëüøîì ïîðÿäêå èñõîäíûõ ìàòðèö
( )n � 103 , êîãäà ñëîæíîñòü O n O n( ) ( )3 2�� . Ïðèíèìàÿ âî âíèìàíèå ýòîò ôàêò, â òàáë. 1
äàíû ïðèáëèæåííûå çíà÷åíèÿ îïåðàöèîííîé ñëîæíîñòè áåç ó÷åòà ñëîæíîñòè O n( )2 , ïî-
ñêîëüêó óæå ïðè n � 104 ñëîæíîñòü O n( )2 ñîñòàâëÿåò 0,12 % ñëîæíîñòè O n( )3 .
Òàêèì îáðàçîì, ðàññìîòðåííûé ñìåøàííûé êëåòî÷íûé ìåòîä ìèíèìèçèðóåò
çíà÷åíèÿ ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòåé îòìå÷åííûõ àëãîðèòìîâ
ìàòðè÷íîãî óìíîæåíèÿ íà 25 %.
26 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2009, ¹ 1
Òàáëèöà 1
Êëåòî÷íûå àíàëîãè àëãîðèòìîâ
ìàòðè÷íîãî óìíîæåíèÿ, ïîëó÷åííûå
íà îñíîâå ñìåøàííîãî êëåòî÷íîãî
ìåòîäà (íàñòîÿùàÿ ñòàòüÿ)
Âû÷èñëèòåëüíàÿ ñëîæíîñòü (÷èñëî îïåðàöèé)
Ìóëüòèïëèêàòèâíàÿ,
Wì
Àääèòèâíàÿ,
Wà
Òðàäèöèîííîãî àëãîðèòìà [10] 0 763 3, n � 0 763 3, n
Àëãîðèòìà Âèíîãðàäà [11] � 0 382 3, n �1147 3, n
Àëãîðèòìà Øòðàññåíà [8] �
�
�
�
�
�
�
�
�
0 763
7
23
3,
q
q
n �
� � ��
�
�
�
�
�
�
�
0 763
6 7 5 2
2
2
3
3,
q q
q
n
Àëãîðèòìà Åëôèìîâîé–Êàïèòîíîâîé [12] � 0 334 3, n �1 004 3, n
Óâåëè÷åíèå ãëóáèíû ðåêóðñèè (÷èñëà ðåêóðñèâíûõ øàãîâ) ïðèâîäèò ê äàëü-
íåéøåìó óìåíüøåíèþ âû÷èñëèòåëüíîé ñëîæíîñòè ïðèâåäåííûõ êëåòî÷íûõ àíàëî-
ãîâ íà êàæäîì øàãå ðåêóðñèè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ:
1. G i l o i W . K . Parallel supercomputer architectures and their programming models // Parallel Computing.
— 1994. — 20. — P. 1443–1470.
2. G i l o i W . K . The SUPRENUM supercomputer: Goals, achievements and lessons learned // Ibid. —
1994. — 20. — Ð. 1407–1425.
3. K r e k e l D . , B o n n i g e r T . , E s s e r R . A comparative description of massively parallel computers //
Ibid. — 1995. — 21. — P. 199–232.
4. K u n g H . T . , L e i s e r s o n C . E . Systolic arrays (for VLSI) // Sparse Matrix Proc. — 1978. — Jan. —
P. 32–63.
5. N a v a r r o J . J . , L i a b e r i a J . M . , V a l o r o M . Partitioning: An essential step in mapping algo-
rithms into array processors // Computer. — 1987. — 21, N 7. — P. 77–89.
6. Ë û ñ à í î â Ñ . Þ . Êëåòî÷íûå ìåòîäû ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû // Âîïð. êèáåðíåòèêè. —
1988. — ¹ 135. — Ñ. 64–73.
7. Å ë ô è ì î â à Ë . Ä . Áûñòðûé êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö // Êèáåðíåòèêà è ñèñòåìíûé àíà-
ëèç. — 2008. — ¹ 3. — Ñ. 55–59.
8. S t r a s s e n V . Gaussian elimination is not optimal // Numer. Math. — 1969. — 13. — Ð. 354–356.
9. G r a y s o n B . , V a n d e G e i j n R . A high performance parallel Strassen implementation // Paral.
Proces. Letters. — 1996. — 6. — P. 3–12.
10. Ô à ä ä å å â Ä . Ê . , Ô à ä ä å å â à  . Í . Âû÷èñëèòåëüíûå ìåòîäû ëèíåéíîé àëãåáðû. — Ì.; Ë.:
Ôèçìàòãèç, 1963. — 734 ñ.
11. W i n o g r a d S . A . A new algorithm for inner product // IEEE Trans. Comp. — 1968. — C-18. —
Ð. 693–694.
12. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ . Â . Áûñòðûé àëãîðèòì äëÿ óìíîæåíèÿ ìàòðèö è åãî ýô-
ôåêòèâíàÿ ðåàëèçàöèÿ íà ñèñòîëè÷åñêèõ ìàññèâàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2001. —
¹ 1. — Ñ. 135–150.
Ïîñòóïèëà 02.06.2008
|