Быстрый клеточный метод умножения матриц
Запропоновано клітинний метод множення матриць, який дозволяє мінімізувати на 12,5 % мультиплікативну й адитивну складності відомих алгоритмів матричного множення. Надано оцінки обчислювальної складності клітинних аналогів зазначених алгоритмів, одержаних на базі запропонованого методу. Представлено...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2008 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/72064 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Быстрый клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2008. — № 3. — С. 55-59. — Бібліогр.: 13 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859709470816337920 |
|---|---|
| author | Елфимова, Л.Д. |
| author_facet | Елфимова, Л.Д. |
| citation_txt | Быстрый клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2008. — № 3. — С. 55-59. — Бібліогр.: 13 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано клітинний метод множення матриць, який дозволяє мінімізувати на 12,5 % мультиплікативну й адитивну складності відомих алгоритмів матричного множення. Надано оцінки обчислювальної складності клітинних аналогів зазначених алгоритмів, одержаних на базі запропонованого методу. Представлено швидкий клітинний аналог, що має мультиплікативну й адитивну складності, які дорівнюють відповідно ≈ 0,382n³ операціям множення та ≈ 1,147n³ операціям додавання, де n - порядок матриць.
|
| first_indexed | 2025-12-01T05:01:17Z |
| format | Article |
| fulltext |
ÓÄÊ 681.322.012
Ë.Ä. ÅËÔÈÌÎÂÀ
ÁÛÑÒÐÛÉ ÊËÅÒÎ×ÍÛÉ ÌÅÒÎÄ ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ
Êëþ÷åâûå ñëîâà: êëåòî÷íûå ìåòîäû ëèíåéíîé àëãåáðû, àëãîðèòìû ìàòðè÷íî-
ãî óìíîæåíèÿ, ïàðàëëåëüíûå âû÷èñëåíèÿ.
Ðåøåíèå ïðîáëåìû ïîãðóæåíèÿ àëãîðèòìîâ ïðîèçâîëüíûõ ðàçìåðîâ â àðõèòåêòó-
ðó êîíêðåòíûõ âû÷èñëèòåëüíûõ ñèñòåì îñíîâàíî íà äåêîìïîçèöèè âû÷èñëèòåëü-
íîãî ïðîöåññà áîëüøèõ ðàçìåðîâ íà ìíîæåñòâî âçàèìîñâÿçàííûõ ïîäïðîöåññîâ
ìåíüøèõ ðàçìåðîâ íà ðàçëè÷íûõ óðîâíÿõ ïðåäñòàâëåíèÿ âû÷èñëåíèé. Ïîòåí-
öèàëüíî íàèáîëåå ïåðñïåêòèâíà äåêîìïîçèöèÿ âû÷èñëèòåëüíîãî ïðîöåññà íà óðîâ-
íå èñõîäíûõ àëãîðèòìîâ, â ðåçóëüòàòå ïðèìåíåíèÿ êîòîðîé îáðàçóþòñÿ êëåòî÷íûå
àëãîðèòìû, ãäå áàçîâûìè îïåðàöèÿìè ÿâëÿþòñÿ îïåðàöèè íàä êëåòêàìè ìàòðèö.
Èçâåñòíû êëåòî÷íûå àëãîðèòìû [1, 2], êîòîðûå òðåáóþò âûïîëíåíèÿ òîëüêî
äâóõ òèïîâ îïåðàöèé: áàçîâîé îïåðàöèè ìàòðè÷íîãî óìíîæåíèÿ ñî ñëîæåíèåì
AB D C� � (ãäå A , B, C, D — êâàäðàòíûå ìàòðèöû ðàçìåðà êëåòêè) è íåñòàíäàðòíûõ
îïåðàöèé, ñîñòàâëÿþùèõ ìàëûé ïðîöåíò îáùåãî ÷èñëà îïåðàöèé àëãîðèòìà. Òàêèå
êëåòî÷íûå àëãîðèòìû äëÿ ðåøåíèÿ ïðàêòè÷åñêè âñåõ çàäà÷ ëèíåéíîé àëãåáðû è ìíî-
ãèõ çàäà÷ âû÷èñëèòåëüíîé ìàòåìàòèêè ðåàëèçóþòñÿ íà ðàçëè÷íûõ âû÷èñëèòåëüíûõ
ñèñòåìàõ, à òàêæå â ñïåöïðîöåññîðàõ, âêëþ÷àþùèõ áûñòðûé âû÷èñëèòåëü äëÿ âû-
ïîëíåíèÿ êëåòî÷íîé îïåðàöèè AB D C� � , êîòîðàÿ ìîæåò áûòü ðåàëèçîâàíà ñ èñ-
ïîëüçîâàíèåì èçâåñòíûõ áûñòðûõ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ [3–5].
Íàèáîëåå ýôôåêòèâíà ðåàëèçàöèÿ áàçîâîé îïåðàöèè íà ÑÁÈÑ-âû÷èñëèòåëÿõ,
â ÷àñòíîñòè ïðîöåññîðíûõ ìàññèâàõ ñ ñèñòîëè÷åñêîé îðãàíèçàöèåé âû÷èñëåíèé.
 íàñòîÿùåå âðåìÿ íà îñíîâå èíòåãðèðîâàííîãî ïîäõîäà ê ïðîåêòèðîâàíèþ óêàçàí-
íûõ ìàññèâîâ [6] ðàçðàáîòàíû ÑÁÈÑ-îðèåíòèðîâàííûå âåðñèè áûñòðûõ àëãîðèò-
ìîâ Âèíîãðàäà [3], Øòðàññåíà [4], íîâîãî áûñòðîãî àëãîðèòìà [5], à òàêæå ñèíòåçè-
ðîâàíû áûñòðûå ñèñòîëè÷åñêèå ìàññèâû ðàçëè÷íîé àðõèòåêòóðû [6–8], ýôôåêòèâ-
íî ðåàëèçóþùèå ïåðå÷èñëåííûå ÑÁÈÑ-àëãîðèòìû ìàòðè÷íîãî óìíîæåíèÿ.
Èçâåñòíû òàêæå êëåòî÷íûå àëãîðèòìû [9–12], ïîëó÷åííûå çàìåíîé ñêàëÿðíûõ
îïåðàöèé íàä ÷èñëàìè îïåðàöèÿìè íàä êëåòêàìè ìàòðèö, ëèáî òàêèì ïåðåóïîðÿäî-
÷èâàíèåì ìíîæåñòâà ñêàëÿðíûõ îïåðàöèé, êîòîðîå ïîçâîëÿåò âûäåëèòü ìàêðîîïå-
ðàöèè íàä êëåòêàìè ìàòðèö. Åñëè àëãîðèòì äîïóñêàåò ñâîáîäó â âûáîðå ìàñøòàáà
ïàðàëëåëèçìà, òî ïåðåõîä ê êðóïíîìàñøòàáíîìó ïàðàëëåëèçìó íà óðîâíå êëåòî÷íûõ
îïåðàöèé ïîçâîëÿåò äîñòè÷ü áîëåå âûñîêîé ñòåïåíè ðàñïàðàëëåëèâàíèÿ âû÷èñëåíèé,
çàãðóæåííîñòè îáîðóäîâàíèÿ, ñîêðàùåíèÿ èçäåðæåê íà îáìåíû. Òàê, íàïðèìåð, äëÿ
ðåàëèçàöèè íà ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è ïðåîäîëåíèÿ ðåêóðñèâíîé
ïðèðîäû áûñòðîãî àëãîðèòìà Øòðàññåíà [4] èñïîëüçóþòñÿ âîñõîäÿùàÿ è íèñõîäÿùàÿ
ñõåìû âû÷èñëåíèé, ãäå èñõîäíûå ìàòðèöû ðàçáèâàþòñÿ íà êëåòêè [12].  âîñõîäÿùåé
ñõåìå âû÷èñëåíèé â êà÷åñòâå âíåøíåãî àëãîðèòìà, îïåðèðóþùåãî êëåòêàìè, èñïîëüçó-
åòñÿ òðàäèöèîííûé àëãîðèòì ìàòðè÷íîãî óìíîæåíèÿ [13], à â êà÷åñòâå âíóòðåííåãî
àëãîðèòìà, îïåðèðóþùåãî ÷èñëàìè, — àëãîðèòì Øòðàññåíà. Íèñõîäÿùàÿ ñõåìà âû-
÷èñëåíèé âûïîëíÿåòñÿ â îáðàòíîì ïîðÿäêå: îíà èñïîëüçóåò àëãîðèòì Øòðàññåíà êàê
âíåøíèé àëãîðèòì, à â êà÷åñòâå âíóòðåííåãî ïðèìåíÿåòñÿ òðàäèöèîííûé àëãîðèòì.
 íàñòîÿùåé ñòàòüå ðàññìàòðèâàåòñÿ êëåòî÷íûé ìåòîä óìíîæåíèÿ ìàòðèö, íà áàçå
êîòîðîãî ïîëó÷åíû êëåòî÷íûå àíàëîãè èçâåñòíûõ àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ
ñ ìèíèìèçèðîâàííîé íà 12,5 % ìóëüòèïëèêàòèâíîé è àääèòèâíîé ñëîæíîñòüþ.
Èñõîäíûå ìàòðèöû A è B ïîðÿäêà n � 2� ( )� � 2 , êîòîðûå äåêîìïîçèðóþòñÿ íà
êëåòêè ïîðÿäêà 2 2q q( )� �� , ïðåäñòàâëåíû íà ðèñ. 1, ãäå m n q q� � �/ 2 2� .
Âíåøíèé (êëåòî÷íûé) àëãîðèòì îïåðèðóåò ìàòðèöàìè ïîðÿäêà 2q .  êà÷åñòâå
âíóòðåííèõ àëãîðèòìîâ, îïåðèðóþùèõ ÷èñëàìè, ìîãóò áûòü èñïîëüçîâàíû èçâåñò-
íûå àëãîðèòìû ìàòðè÷íîãî óìíîæåíèÿ è ñëîæåíèÿ [3–5, 13].
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 55
© Ë.Ä. Åëôèìîâà, 2008
Íà ïåðâîì ýòàïå âûïîëíåíèÿ êëåòî÷íîãî ìåòîäà âû÷èñëÿþòñÿ ìàòðè÷íûå êî-
ýôôèöèåíòû:
R A A F B B
ik i k i k kj k j k j
1
2 1 2 1 2 2
1
2 1 2 1 2 2� � � �� � � �( ), ( ),, , , ,
R A A F B B
ik i k i k kj k j k j
2
2 2 1 2 2
2
2 1 2 2 2� � � �� �( ), ( ),, , , ,
R A A F B B
ik i k i k kj k j k j
3
2 1 2 1 2 1 2
3
2 2 1 2 1 2� � � �� � � � �( ), (, , , , �1 ), (1)
R A A F B B
ik i k i k kj k j k
4
2 2 1 2 1 2 1
4
2 1 2 1 2 1� � � �� � � � � �( ), (, , , , 2 j ),
R A A F B B
ik i k i k kj k j k j
5
2 1 2 2 2
5
2 2 1 2 2� � � �� �( ), ( ),, , , ,
ãäå i j k p p n q q, , , , , ; /� � �� � �1 2 2 21 1� � .
Íà âòîðîì ýòàïå âûïîëíÿþòñÿ ðåãóëÿðíûå âû÷èñëåíèÿ ìàòðèö Qij :
Q R Fij
k
p
ik kj
1
1
1 1�
�
� , Q R Bij
k
p
ik k j
2
1
2
2 1 2 1�
�
� �� , ,
Q A Fij
k
p
i k kj
3
1
2 1 2 1
2�
�
� �� , , Q A Fij
k
p
i k kj
4
1
2 2
3�
�
� , , Q R Bij
k
p
ik k j
5
1
3
2 2�
�
� , ,
(2)
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 � .
Íà òðåòüåì (ïîñëåäíåì) ýòàïå âû÷èñëÿþòñÿ ðåçóëüòèðóþùèå ìàòðèöû Cij :
C Q Q Q Qi j ij ij ij ij2 1 2 1
1 4 5 7
� � � � � �, ,
C Q Q
C Q Q
i j ij ij
i j ij ij
2 1 2
3 5
2 2 1
2 4
�
�
� �
� �
,
,
,
,
(3)
C Q Q Q Qi j ij ij ij ij2 2
1 2 3 6
, � � � � , ãäå i j p, , , ,� 1 2 � .
Îñîáåííîñòü ïðåäëàãàåìîãî êëåòî÷íîãî ìåòîäà çàêëþ÷àåòñÿ â òîì, ÷òî ìàò-
ðè÷íûå êîýôôèöèåíòû Rik (ñîîòâåòñòâåííî Fkj ) âû÷èñëÿþòñÿ òîëüêî îäèí ðàç è èñ-
ïîëüçóþòñÿ äëÿ âñåé ìàòðè÷íîé ñòðîêè i (ñîîòâåòñòâåííî ìàòðè÷íîãî ñòîëáöà j ),
ñîñòîÿùåé èç êëåòîê ïîðÿäêà 2 1q� . Ïîýòîìó ïðè âû÷èñëåíèè ìàòðè÷íûõ êîýôôè-
öèåíòîâ (1) âíåøíèé àëãîðèòì òðåáóåò 10 2p ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ. Äëÿ
êàæäîé ìàòðè÷íîé îïåðàöèè ñëîæåíèÿ âíóòðåííèé àëãîðèòì òðåáóåò 22q ñêàëÿð-
íûõ îïåðàöèé ñëîæåíèÿ, òàê êàê ïîðÿäîê îïåðèðóåìûõ ìàòðèö ðàâåí 2q . Ñëåäîâà-
òåëüíî, àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (1), îïðåäåëÿåìàÿ êîëè÷åñòâîì ñêàëÿð-
íûõ îïåðàöèé ñëîæåíèÿ, ñîñòàâëÿåò
W p
n
nq
q
q
a
( ) ,1 2 2
1
2
2 210 2 10
2
2 2 5� � �
�
�
� � �
�
(îïåðàöèé ñëîæåíèÿ).
56 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
mmmm
m
mq
mmmm
m
m
q
mmmm
m
mq
CCC
CCC
CCC
BBB
BBB
BBB
AAA
AAA
AAA
CBA
qqq
�
����
�
�
�
����
�
�
�
����
�
�
���������
21
22221
11211
21
22221
11211
1
21
22221
11211
222
2
2
2
Ðèñ. 1
Ïðè âû÷èñëåíèè ìàòðè÷íûõ âûðàæåíèé (2) âíåøíèé àëãîðèòì òðåáóåò 7 3p
ìàòðè÷íûõ îïåðàöèé óìíîæåíèÿ è 7 3 2( )p p� ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ. Êàê
áûëî îòìå÷åíî âûøå, êàæäîå ÷àñòè÷íîå ïðîèçâåäåíèå 2 2q q� ìàòðèö (âíóòðåííèé
àëãîðèòì) ìîæåò âû÷èñëÿòüñÿ ñ èñïîëüçîâàíèåì èçâåñòíûõ àëãîðèòìîâ ìàòðè÷íî-
ãî óìíîæåíèÿ [3–5, 13]. Èñïîëüçóÿ òðàäèöèîííûé àëãîðèòì ìàòðè÷íîãî óìíîæå-
íèÿ [13], êîòîðûé òðåáóåò 23q ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ è ( )2 23 2q q� ñêà-
ëÿðíûõ îïåðàöèé ñëîæåíèÿ, ïîëó÷èì äëÿ ìóëüòèïëèêàòèâíîé ñëîæíîñòè, îïðåäå-
ëÿåìîé êîëè÷åñòâîì ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ, è àääèòèâíîé ñëîæíîñòè
âû÷èñëåíèé (2) ñëåäóþùèå âûðàæåíèÿ:
W p
n
nq
q
q
ì
( ) ,2 3 3
1
3
3 37 2 7
2
2 0 875� � �
�
�
� � �
�
(îïåðàöèé óìíîæåíèÿ),
W p p pq q q
a
( ) [( ) ( )]2 3 2 2 3 3 27 2 2 2� � � � � �
� � � � � �7 2 2 0 875 1753 3 2 2 3 2( ) , ,p p n nq q (îïåðàöèé ñëîæåíèÿ).
Ïðè âû÷èñëåíèè ðåçóëüòèðóþùåé ìàòðèöû (3) âíåøíèé àëãîðèòì òðåáóåò 8 2p
ìàòðè÷íûõ îïåðàöèé ñëîæåíèÿ, à âíóòðåííèé — 22q ñêàëÿðíûõ îïåðàöèé ñëîæå-
íèÿ. Ñëåäîâàòåëüíî, àääèòèâíàÿ ñëîæíîñòü âû÷èñëåíèé (3) ñîñòàâèò
W p
n
nq
q
q
a
( )3 2 2
1
2
2 28 2 8
2
2 2� � �
�
�
� � �
�
(îïåðàöèé ñëîæåíèÿ).
Òàêèì îáðàçîì, íà îñíîâå ïðåäëîæåííîãî ìåòîäà (1)–(3) ïîëó÷àåì êëåòî÷íûé
àíàëîã òðàäèöèîííîãî àëãîðèòìà ñî ñëåäóþùèìè çíà÷åíèÿìè ìóëüòèïëèêàòèâíîé
è àääèòèâíîé ñëîæíîñòè:
W nì � 0 875 3, (îïåðàöèé óìíîæåíèÿ),
W W W W n na a a a� � � � �( ) ( ) ( ) , ,1 2 3 3 20 875 2 75 (îïåðàöèé ñëîæåíèÿ).
Îöåíèì îïåðàöèîííóþ ñëîæíîñòü âû÷èñëåíèé (2) ïðè óñëîâèè, ÷òî â êà÷åñòâå
âíóòðåííåãî àëãîðèòìà áóäåò èñïîëüçîâàí ñàìûé áûñòðûé àëãîðèòì [5], òðåáóþ-
ùèé � 0 437 3, n îïåðàöèé óìíîæåíèÿ è � 1311 3, n îïåðàöèé ñëîæåíèÿ.  ýòîì ñëó÷àå
ìóëüòèïëèêàòèâíàÿ è àääèòèâíàÿ ñëîæíîñòè âû÷èñëåíèé (2) ñîñòàâÿò
W
n
n
q
q
ì
( ) , ,2
1
3
3 37
2
0 437 2 0 382�
�
�
� � � �
�
(îïåðàöèé óìíîæåíèÿ),
W
n n
q
q
q
q
a
( ) ,2
1
3
3
1
2
27
2
1311 2 7
2
2�
�
�
� � � �
�
�
� � �
� �
� �1147 1753 2, ,n n (îïåðàöèé ñëîæåíèÿ).
Ñëåäîâàòåëüíî, ïðåäëîæåííûé ìåòîä (1)–(3) ìèíèìèçèðóåò âû÷èñëèòåëüíóþ
ñëîæíîñòü áûñòðîãî àëãîðèòìà [5] äî ñëåäóþùèõ çíà÷åíèé:
W nì � 0 382 3, (îïåðàöèé óìíîæåíèÿ),
W W W W n na a a a� � � � �( ) ( ) ( ) , ,1 2 3 3 21147 2 75 (îïåðàöèé ñëîæåíèÿ).
Ïîäîáíûì îáðàçîì ïîëó÷àåì êëåòî÷íûé àíàëîã àëãîðèòìà Âèíîãðàäà [3] ñî
ñëåäóþùèìè çíà÷åíèÿìè âû÷èñëèòåëüíîé ñëîæíîñòè:
W nì � 0 437 3, (îïåðàöèé óìíîæåíèÿ),
W n na � �1311 2 753 2, , (îïåðàöèé ñëîæåíèÿ).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 57
Ïðè èñïîëüçîâàíèè àëãîðèòìà Øòðàññåíà [4] â êà÷åñòâå âíóòðåííåãî àëãîðèò-
ìà òðåáóåòñÿ 7q ñêàëÿðíûõ îïåðàöèé óìíîæåíèÿ è 6 7 22( )q q� ñêàëÿðíûõ îïåðàöèé
ñëîæåíèÿ äëÿ êàæäîé ìàòðè÷íîé îïåðàöèè óìíîæåíèÿ. Òîãäà êëåòî÷íûé àíàëîã àë-
ãîðèòìà Øòðàññåíà èìååò ñëåäóþùèå çíà÷åíèÿ âû÷èñëèòåëüíîé ñëîæíîñòè:
W p
n
nq
q
q
q
qì � � �
�
�
� � �
�
�
�
�
��
7 7 7
2
7 0 875
7
2
3
1
3
3
3, (îïåðàöèé óìíîæåíèÿ),
W p p p pq q q q
a � � � � � � � � �7 6 7 2 7 2 18 23 2 3 2 2 2 2( ) ( )
�
� � �
�
�
�
�
�
�0 875
6 7 5 2
2
2 75
2
3
3 2, ,
q q
q
n n (îïåðàöèé ñëîæåíèÿ),
W n n
q q
qîáù. �
� �
�
�
�
�
�
�
�
0 875
7 5 2
2
2 75
1 2
3
3 2, , .
Íà ðèñ. 2 ïðåäñòàâëåí ãðàôèê
ôóíêöèè a q( ) � 0 875
7
23
,
q
q
�
�
�
�
�
(ïî-
ñòðîåííûé íà îñíîâàíèè òàáë. 1),
äëÿ ìóëüòèïëèêàòèâíîé ñëîæíîñòè
ïîëó÷åííîãî êëåòî÷íîãî àíàëîãà
ïðè q � 1 2 10, , ,� . Èç ãðàôèêà è
òàáë. 1 ñëåäóåò, ÷òî ÷èñëî îïåðàöèé
óìíîæåíèÿ íåëèíåéíî ñíèæàåòñÿ ñ
ðîñòîì q.
Íà ðèñ. 3 ïðåäñòàâëåí ãðàôèê
ôóíêöèè a q
q q
q
( ) ,�
� �
�
�
�
�
�
�
0 875
7 5 2
2
1 2
3
äëÿ îáùèõ âû÷èñëèòåëüíûõ çàòðàò
ðàññìàòðèâàåìîãî êëåòî÷íîãî àíàëîãà
àëãîðèòìà Øòðàññåíà ïðè q � 1,
2 7, ,� , ïîñòðîåííûé íà îñíîâàíèè
òàáë. 2. Èç ãðàôèêà ñëåäóåò, ÷òî ïðåä-
ëîæåííûé êëåòî÷íûé ìåòîä óìíîæå-
íèÿ ìàòðèö óìåíüøàåò çíà÷åíèå
ôóíêöèè a q( ) âî âñåì äèàïàçîíå èç-
ìåíåíèÿ q â 1,143 ðàçà ïî ñðàâíåíèþ
ñ âîñõîäÿùåé ñõåìîé âû÷èñëåíèé
[12], ãäå â êà÷åñòâå âíåøíåãî àëãîðèò-
ìà èñïîëüçóåòñÿ òðàäèöèîííûé àëãî-
ðèòì ìàòðè÷íîãî óìíîæåíèÿ, à â êà-
÷åñòâå âíóòðåííåãî — àëãîðèòì
Øòðàññåíà.
Âûáîð îïòèìàëüíîãî çíà÷åíèÿ
âåëè÷èíû q îïðåäåëÿåòñÿ àðõèòåêòó-
ðîé êîíêðåòíîé ïàðàëëåëüíîé âû÷èñëèòåëüíîé ñèñòåìû, ðåàëèçóþùåé àëãîðèòì, è çàâè-
ñèò îò îáúåìà èñïîëüçóåìîé ïàìÿòè, à òàêæå òðåáóåìîãî âðåìåíè ðåàëèçàöèè. Òàêèì îá-
ðàçîì, ïðåäëîæåííûé â ñòàòüå ìåòîä óìíîæåíèÿ ìàòðèö (1)–(3) ïðèâîäèò ê îáðàçîâàíèþ
êëåòî÷íûõ àíàëîãîâ ðàññìîòðåííûõ âûøå àëãîðèòìîâ ñ ìèíèìèçèðîâàííîé íà 12,5 % âû-
÷èñëèòåëüíîé ñëîæíîñòüþ.
 òàáë. 3 ïðèâåäåíà âû÷èñëèòåëüíàÿ ñëîæíîñòü èçâåñòíûõ áûñòðûõ àëãîðèò-
ìîâ ìàòðè÷íîãî óìíîæåíèÿ è ïîëó÷åííîãî íà îñíîâå ïðåäëîæåííîãî ìåòîäà êëå-
58 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3
a
0,8
0,7
0,6
0,5
0,4
0,3
0,2
0,1
0
1 2 3 4 5 6 7 8 9 q
Ðèñ. 2
a
4
3
2
1
0
1 2 3 4 5 6 7 q
Ðèñ. 3
Ò à á ë è ö à 1
q 1 2 3 4 6 7 10
a q( ) 0,77 0,67 0,59 0,51 0,39 0,34 0,23
Ò à á ë è ö à 2
q 1 2 3 4 5 6 7
a q( ) 3,06 3,60 3,56 3,32 3,00 2,56 2,37
òî÷íîãî àíàëîãà áûñòðîãî àëãîðèòìà, îïèñàííîãî â [5]. Ïðåäñòàâëåííûé â òàáëèöå
êëåòî÷íûé àíàëîã õàðàêòåðèçóåòñÿ íàèìåíüøåé îïåðàöèîííîé ñëîæíîñòüþ ïî
ñðàâíåíèþ ñ óïîìÿíóòûìè àëãîðèòìàìè.
Êëåòî÷íûå àíàëîãè àëãîðèòìîâ ìàòðè÷íîãî óìíîæåíèÿ ìîãóò áûòü ýôôåêòèâ-
íî ðåàëèçîâàíû â ìàòðè÷íûõ ìàøèíàõ, ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è
ÑÁÈÑ-îðèåíòèðîâàííûõ ïðîöåññîðíûõ ìàññèâàõ ðàçìåðà êëåòêè.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1.  î å â î ä è í À .  . Î êëàññå êëåòî÷íûõ àëãîðèòìîâ è åãî ñâîéñòâàõ // Âîïð. êèáåðíåòèêè. — 1988.
— ¹ 135. — Ñ. 50–64.
2. Ë û ñ à í î â Ñ . Þ . Êëåòî÷íûå ìåòîäû ðåøåíèÿ çàäà÷ ëèíåéíîé àëãåáðû // Òàì æå. — Ñ. 64–73.
3. W i n o g r a d S . A . A new algorithm for inner product // IEEE Trans. Comp. — 1968. — C-18. —
P. 693–694.
4. S t r a s s e n V . Gaussian elimination is not optimal // Numer. Math. — 1969. — 13. — P. 354–356.
5. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ . Â . Áûñòðûé àëãîðèòì äëÿ óìíîæåíèÿ ìàòðèö è åãî ýô-
ôåêòèâíàÿ ðåàëèçàöèÿ íà ñèñòîëè÷åñêèõ ìàññèâàõ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2001. —
¹ 1. — C. 135–150.
6. Å ë ô è ì î â à Ë . Ä . , Ê à ï è ò î í î â à Þ . Â . Èíòåãðèðîâàííûé ïîäõîä ê ïðîåêòèðîâàíèþ ïðîöåñ-
ñîðíûõ ìàññèâîâ ñ ñèñòîëè÷åñêîé îðãàíèçàöèåé âû÷èñëåíèé // Òàì æå. — 2002. — ¹ 6. — Ñ. 3–15.
7. J e l f i m o v a L . A new fast systolic array for modified Winograd algorithm // Proc. Sevens Int. Workshop
on Parallel Processing by Cellular Automata and Array, PARCELLA-96 (Berlin, Germany, Sept. 1996). —
Berlin: Akad. Verlag. — 1996. — 96. — P. 157–164.
8. Ä å ê ë à ð à ö ³ é í è é ïàòåíò íà êîðèñíó ìîäåëü ¹ 14282, Óêðà¿íà, ÌÏÊ G06F 15/00. Ïðèñòð³é äëÿ
ìíîæåííÿ ìàòðèöü / ªëô³ìîâà Ë.Ä., Êàï³òîíîâà Þ.Â. (Óêðà¿íà); Çàÿâë. 24.10.2005; Îïóáë.
15.05.2006. Áþë. ¹ 5.
9. Â û ø è í ñ ê è é Â . À . , Ð à á è í î â è ÷ Ç . Ë . Î ñîçäàíèè âûñîêîïðîèçâîäèòåëüíûõ ÝÂÌ, ðàáîòà-
þùèõ â àëãåáðå ìàòðèö // Àâòîìàòèêà. — 1983. — ¹ 5. — Ñ. 80–84.
10. S c h r e i b e r R . Block algorithms for parallel machines // SIAM J. Sci. Stat. Comput. — 1987. — 8, N 2.
— P. 197–207.
11. M o d i J . J . Parallel algorithms and matrix computation. — Oxford: Clarendon Press, 1988. — 260 p.
12. F r a n c o m a n o E . , T o r t o r i c i - M a c a l u s o A . , V a j t e r s i c M . Implementation analysis of fast
matrix multiplication algorithms on shared memory computers // Comp. & Artif. Intel. — 1995. — 14, N 3.
— P. 299–313.
13. Ô à ä ä å å â Ä . Ê . , Ô à ä ä å å â à  . Í . Âû÷èñëèòåëüíûå ìåòîäû ëèíåéíîé àëãåáðû. — Ì.; Ë.:
Ôèçìàòãèç, 1963. — 734 ñ.
Ïîñòóïèëà 05.10.2007
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 3 59
Ò à á ë è ö à 3
Áûñòðûå àëãîðèòìû
äëÿ óìíîæåíèÿ ìàòðèö
Âû÷èñëèòåëüíàÿ ñëîæíîñòü (÷èñëî îïåðàöèé)
Ìóëüòèïëèêàòèâíàÿ Wì Àääèòèâíàÿ Wa
Àëãîðèòì Âèíîãðàäà [3] � 0 5 3, n �1 5 3, n
Àëãîðèòì Øòðàññåíà [4] n2 807, 6 7 22 22( )log logn n�
Àëãîðèòì Åëôèìîâîé–Êàïèòîíîâîé [5] � 0 437 3, n �1 311 3, n
Êëåòî÷íûé àíàëîã àëãîðèòìà [5]
(íàñòîÿùàÿ ñòàòüÿ)
� 0 382 3, n �1147 3, n
|
| id | nasplib_isofts_kiev_ua-123456789-72064 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-01T05:01:17Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Елфимова, Л.Д. 2014-12-16T19:19:22Z 2014-12-16T19:19:22Z 2008 Быстрый клеточный метод умножения матриц / Л.Д. Елфимова // Кибернетика и системный анализ. — 2008. — № 3. — С. 55-59. — Бібліогр.: 13 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72064 681.322.012 Запропоновано клітинний метод множення матриць, який дозволяє мінімізувати на 12,5 % мультиплікативну й адитивну складності відомих алгоритмів матричного множення. Надано оцінки обчислювальної складності клітинних аналогів зазначених алгоритмів, одержаних на базі запропонованого методу. Представлено швидкий клітинний аналог, що має мультиплікативну й адитивну складності, які дорівнюють відповідно ≈ 0,382n³ операціям множення та ≈ 1,147n³ операціям додавання, де n - порядок матриць. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Быстрый клеточный метод умножения матриц Article published earlier |
| spellingShingle | Быстрый клеточный метод умножения матриц Елфимова, Л.Д. Кибернетика |
| title | Быстрый клеточный метод умножения матриц |
| title_full | Быстрый клеточный метод умножения матриц |
| title_fullStr | Быстрый клеточный метод умножения матриц |
| title_full_unstemmed | Быстрый клеточный метод умножения матриц |
| title_short | Быстрый клеточный метод умножения матриц |
| title_sort | быстрый клеточный метод умножения матриц |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/72064 |
| work_keys_str_mv | AT elfimovald bystryikletočnyimetodumnoženiâmatric |