Построение оптимальных алгоритмов массовых вычислений в задачах цифровой фильтрации
В работе предложен квазисистолический метод (КСМ) организации вычислений при решении задачи цифровой фильтрации произвольной размерности. Данный метод развит для решения одно-, дву-и трехмерной задачи многоразовой каскадцифровой фильтрации. На основании КСМ построены оптимальные по быстродействию па...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2008 |
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2008
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/44192 |
| 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. — № 4. — С. 3-14. — Бібліогр.: 34 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859488271634006016 |
|---|---|
| author | Анисимов, А.В. Яджак, М.С. |
| author_facet | Анисимов, А.В. Яджак, М.С. |
| citation_txt | Построение оптимальных алгоритмов массовых вычислений в задачах цифровой фильтрации / А.В. Анисимов, М.С. Яджак // Кибернетика и системный анализ. — 2008. — № 4. — С. 3-14. — Бібліогр.: 34 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | В работе предложен квазисистолический метод (КСМ) организации вычислений при решении задачи цифровой фильтрации произвольной размерности. Данный метод развит для решения одно-, дву-и трехмерной задачи многоразовой каскадцифровой фильтрации. На основании КСМ построены оптимальные по быстродействию параллельно-конвейерные алгоритмы, ориентированные на реализацию на специализированных вычислительных системах.
|
| first_indexed | 2025-11-24T16:13:03Z |
| format | Article |
| fulltext |
À.Â. ÀÍÈÑÈÌÎÂ, Ì.Ñ. ßÄÆÀÊ
ÓÄÊ 519.681.5 ÏÎÑÒÐÎÅÍÈÅ ÎÏÒÈÌÀËÜÍÛÕ ÀËÃÎÐÈÒÌÎÂ
ÌÀÑÑÎÂÛÕ ÂÛ×ÈÑËÅÍÈÉ Â ÇÀÄÀ×ÀÕ
ÖÈÔÐÎÂÎÉ ÔÈËÜÒÐÀÖÈÈ
Êëþ÷åâûå ñëîâà: îïòèìàëüíûé ïàðàëëåëüíî-êîíâåéåðíûé àëãîðèòì, çàäà÷à öèô-
ðîâîé ôèëüòðàöèè, ìíîãîðàçîâàÿ êàñêàäíàÿ öèôðîâàÿ ôèëüòðàöèÿ, êâàçèñèñòî-
ëè÷åñêàÿ ñòðóêòóðà, îãðàíè÷åííûé ïàðàëëåëèçì, óñêîðåíèå àëãîðèòìà.
ÂÂÅÄÅÍÈÅ
Ïðîáëåìà îïòèìèçàöèè âû÷èñëåíèé ïðè ðåøåíèè çàäà÷ ôèëüòðàöèè ðàññìàòðèâà-
ëàñü âî ìíîãèõ ðàáîòàõ [1–4].  áîëüøèíñòâå ñëó÷àåâ òàêèå çàäà÷è íåîáõîäèìî
ðåøàòü â ðåæèìå ðåàëüíîãî âðåìåíè ïðè ìèíèìàëüíûõ çàòðàòàõ îáîðóäîâàíèÿ.
Ñ ýòîé öåëüþ ïðåäëîæåíî ðÿä ïàðàëëåëüíûõ àëãîðèòìîâ [5–8], îðèåíòèðîâàííûõ
íà ðàçëè÷íûå òèïû àðõèòåêòóð âû÷èñëèòåëüíûõ ñèñòåì [9], è ñêîíñòðóèðîâàíî
ñèñòîëè÷åñêèå ñòðóêòóðû [10–14]. Èçâåñòíû òàêæå ðåçóëüòàòû, êàñàþùèåñÿ ðåøå-
íèÿ çàäà÷ ôèëüòðàöèè íà îñíîâå èñïîëüçîâàíèÿ îäíîðîäíûõ âû÷èñëèòåëüíûõ ñðåä
[4, 15], ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì [16] è íåéðîííûõ ñå-
òåé [17]. Ðàçðàáîòàííûå àëãîðèòìû è âû÷èñëèòåëüíûå ñðåäñòâà îáëàäàëè ðÿäîì
íåäîñòàòêîâ: ëèáî èç-çà «íåýêîíîìíîãî» èñïîëüçîâàíèÿ ïåðåñ÷èòàííûõ çíà÷åíèé
óìåíüøàëàñü ñêîðîñòü ñõîäèìîñòè âû÷èñëèòåëüíîãî ïðîöåññà, ëèáî èñïîëüçîâà-
ëèñü íå âñå ðåçåðâû ðàñïàðàëëåëèâàíèÿ, â ÷àñòíîñòè, îñòàâàëèñü íåâîñòðåáîâàí-
íûìè åñòåñòâåííûå ñîîòíîøåíèÿ àññîöèàòèâíîñòè è êîììóòàòèâíîñòè äëÿ îïåðà-
öèé, ëèáî èìåëè ìåñòî çàäåðæêè ïîòîêîâ äàííûõ.
Ïîñòîÿííîå óâåëè÷åíèå îáúåìà îáðàáàòûâàåìîé â ðåæèìå ðåàëüíîãî âðåìåíè
èíôîðìàöèè ïðèâîäèò ê ãëóáîêîìó àíàëèçó è îïòèìèçàöèè ïî áûñòðîäåéñòâèþ
óæå ñóùåñòâóþùèõ è ïîèñêó íîâûõ ìåòîäîâ è àëãîðèòìîâ ÷èñëåííîãî ðåøåíèÿ
çàäà÷ ôèëüòðàöèè. Ñ ó÷åòîì ñîâðåìåííûõ òåíäåíöèé â ìèêðîýëåêòðîíèêå [18] àâ-
òîðàìè íàñòîÿùåé ñòàòüè áûëè ðàçâèòû ìåòîäû Êóíãà–Ëåéçåðçîíà [10] äëÿ ðåàëèçà-
öèè ôèëüòðîâ íåðåêóðñèâíîãî òèïà è ìåòîä [11] ðåàëèçàöèè ôèëüòðà ðåêóðñèâíîãî
òèïà ñ öåëüþ îðãàíèçàöèè ñèñòîëè÷åñêèõ âû÷èñëåíèé äëÿ ðåøåíèÿ îäíîìåðíîãî
âàðèàíòà çàäà÷è öèôðîâîé ôèëüòðàöèè (ÇÖÔ) [19] è çàäà÷è ìíîãîðàçîâîé êàñêàä-
íîé öèôðîâîé ôèëüòðàöèè (ÇÌÊÖÔ) [20, 21].  ðåçóëüòàòå ïîëó÷åíû ñèñòîëè÷åñ-
êèå àëãîðèòìû è îïòèìàëüíûå ïî çàãðóçêå ðåàëèçóþùèå èõ âû÷èñëèòåëüíûå
ñòðóêòóðû. Ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ îñîáûé èíòåðåñ ïðåäñòàâëÿåò ïðîáëåìà
ïîèñêà â çàäàííûõ êëàññàõ îïòèìàëüíûõ ïî áûñòðîäåéñòâèþ àëãîðèòìîâ è ðàçðà-
áîòêè ñðåäñòâ èõ íåïîñðåäñòâåííîé ðåàëèçàöèè. Îäèí èç âåñîìûõ øàãîâ â ýòîì íà-
ïðàâëåíèè ñäåëàí â [22], ãäå ïðåäëîæåí ïàðàëëåëüíî-êîíâåéåðíûé àëãîðèòì (ÏÊÀ)
ðåøåíèÿ îäíîìåðíîé ÇÖÔ, îïòèìàëüíûé ïî áûñòðîäåéñòâèþ è èñïîëüçîâàíèþ ïà-
ìÿòè â êëàññå ýêâèâàëåíòíûõ åìó ïî èíôîðìàöèîííîìó ãðàôó (ÈÃ) àëãîðèòìîâ ñ
òî÷íîñòüþ äî âûïîëíåíèÿ çàêîíîâ àññîöèàòèâíîñòè è êîììóòàòèâíîñòè äëÿ îïåðàöèè
ñëîæåíèÿ. Äàííûé àëãîðèòì ïîçâîëÿåò â äîñòàòî÷íî îáùåé ïîñòàíîâêå ðåàëèçîâàòü
öèôðîâóþ ôèëüòðàöèþ è ìîæåò áûòü ïðèìåíåí íå òîëüêî äëÿ îáðàáîòêè èíôîðìà-
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 3
© À.Â. Àíèñèìîâ, Ì.Ñ. ßäæàê, 2008
öèè â ðàçëè÷íûõ ïðåäìåòíûõ îáëàñòÿõ (àíàëèç è îáðàáîòêà ñèãíàëîâ, ýêñïåðèìåí-
òàëüíûõ äàííûõ, âûñêàçûâàíèé è ò.ä.), íî è äëÿ èññëåäîâàíèÿ ôóíêöèîíèðîâàíèÿ
íåêîòîðûõ âû÷èñëèòåëüíûõ ñèñòåì, â ÷àñòíîñòè êâàçèñèñòîëè÷åñêèõ ñòðóêòóð
(ÊÑÑ) èëè íåéðîííûõ ñåòåé [23].
 íàñòîÿùåé ðàáîòå ïðåäñòàâëåíû ðåçóëüòàòû, êàñàþùèåñÿ ïîñòðîåíèÿ è ðåà-
ëèçàöèè îïòèìàëüíûõ ïî áûñòðîäåéñòâèþ ÏÊÀ ðåøåíèé ÇÖÔ è ÇÌÊÖÔ áîëåå
âûñîêèõ ðàçìåðíîñòåé.
ÔÎÐÌÓËÈÐÎÂÊÀ ÏÐÎÁËÅÌÛ
Ðàññìàòðèâàåìàÿ ÇÖÔ ñîñòîèò â âûïîëíåíèè Ñ ïåðåñ÷åòîâ ñãëàæèâàíèÿ ìàññèâà N
çíà÷åíèé ïåðåìåííûõ ÷åðåç ïëàâàþùåå îêíî ðàçìåðà M.
 äâóìåðíîì ñëó÷àå ïåðåñ÷åò îñóùåñòâëÿåòñÿ ïî ôîðìóëå
x x f i li i
s m
m
i s i s
s m
m
s s1 2
2 2
2
1 1 2 2
1 1
1
1 2 1 1, , , ; ,� �
��
� �
��
�� 1 2 21; ,i l� . (1)
Çäåñü M m m� � �( )( )2 1 2 11 2 , N l l� 1 2 , à âåñîâûå êîýôôèöèåíòû f s m ms s1 2 1 1 1, ( , ;� �
s m m2 2 2� � , ) è «çàãðàíè÷íûå» çíà÷åíèÿ x x x
m j m j j1 2 01 1� �� � �, , ,
, , ... , ; x
l j1 1� , * ,
x
l j1 2� , * ,� ,
,
x
l m j1 1� � ( , )j m l m� � � �1 2 2 2 ; x x xi m i m i1 2 1 2 11 2 0, , ,, , ... , ;� � xi l1 2 1, ,�
xi l1 2 2, ,� � , ,xi l m1 2 2� ( , )i l1 11� — èçâåñòíûå êîíñòàíòû.
 n-ìåðíîì ñëó÷àå (1) èìååò âèä
x xi i i
s m
m
s m
m
i s i sn
n n
n
1 2
2 2
2
1 1 2 2, ,..., , ,...,�
�� ��
� �� �� i s
s m
m
s s sn n n
f�
��
�
1 1
1
1 2, ,..., ;
i l i l i ln n1 1 2 21 1 1� � �, ; , ; ; ,� .
Çäåñü M m m mn� � � � � �( )( ) ( )2 1 2 1 2 11 2 � , N l l ln� � �1 2 � . Àíàëîãè÷íî ôîðìóëèðó-
åòñÿ îäíî- è òðåõìåðíàÿ ÇÖÔ.
Êàê èçâåñòíî [1], ìíîãîðàçîâàÿ êàñêàäíàÿ ôèëüòðàöèÿ îñóùåñòâëÿåòñÿ ïîñëå-
äîâàòåëüíî íàáîðîì äåéñòâóþùèõ îäèí çà äðóãèì ïðîñòûõ ôèëüòðîâ. Ñëåäîâàòåëü-
íî, ðàññìàòðèâàåìàÿ ÇÌÊÖÔ ñîñòîèò â âûïîëíåíèè r àêòîâ ôèëüòðàöèè; ïðè
êàæäîì r�-ì àêòå ðåàëèçóåòñÿ C r1 ( )� êàñêàäîâ, â êàæäîì èç êîòîðûõ îñóùåñòâëÿåòñÿ
ïåðåñ÷åò N1 çíà÷åíèé ïåðåìåííûõ ÷åðåç ïëàâàþùåå îêíî ðàçìåðà M r1 ( , )�� � , ãäå
�� — íîìåð êàñêàäà ïðè r�-ì àêòå ôèëüòðàöèè.
Îäíîìåðíàÿ çàäà÷à ïðåäïîëàãàåò äëÿ ïðîèçâîëüíîãî r�-ãî àêòà ôèëüòðàöèè âû-
ïîëíåíèå âû÷èñëåíèé â çàäàííîì ��-ì êàñêàäå ïî ôîðìóëå
x x f r i Ni
s m r
m r
i s s1
1 1
1
1 1 1 1 1� � � �
�� � �
� �
��
( , )
( , )
( , ); ,
�
�
� 1 . (2)
 äàííîì ñëó÷àå M r m r1 12 1( , ) ( , )� �� � � � � � , à çíà÷åíèÿ x m r1 1� � �( , )� , x m r2 1� � �( , ) ,...�
... , x0 ; x x xl l l m r1 1 1 11 2� � � � �, ,... , ( , )� è âåñîâûå êîýôôèöèåíòû f r
s1
( , )�� �
( ( , ), ( , ))s m r m r1 1 1� � � � � �� � — çàäàííûå êîíñòàíòû.
Äëÿ òðåõìåðíîé ÇÌÊÖÔ ôîðìóëà (2) ïðèíèìàåò âèä
xi i i
s m r
m r
s m r
m
1 2 3
1 1
1
2 2
2
, ,
( , )
( , )
( , )
(
�
�� � �
� �
�� � �
�
�
�
�
�� �
�� � �
� �
� � �� �
, )
( , )
( , )
, ,
r
s m r
m r
i s i s i s sx f
3 3
3
1 1 2 2 3 3 1
�
�
, , ( , )s s r
2 3
�� � ;
i l i l i l1 1 2 2 3 31 1 1� � �, ; , ; , .
4 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Çäåñü N l l l1 1 2 3� , M r m r m r m r1 1 2 32 1 2 1 2( , ) ( ( , ) )( ( , ) )( ( , )� � � �� � � � � � � � � � � � 1). Àíà-
ëîãè÷íî ôîðìóëèðóåòñÿ è äâóìåðíàÿ ÇÌÊÖÔ.
Ðåøàåìàÿ ïðîáëåìà ñîñòîèò â ðàçðàáîòêå îïòèìàëüíûõ ïî áûñòðîäåéñòâèþ è
èñïîëüçîâàíèþ ïàìÿòè ÏÊÀ ÷èñëåííîãî ðåøåíèÿ ÇÖÔ ðàçìåðíîñòè n 1 è îäíî-,
äâó- è òðåõìåðíîé ÇÌÊÖÔ ñ ïîñëåäóþùåé îðèåíòàöèåé ýòèõ àëãîðèòìîâ äëÿ ýô-
ôåêòèâíîé ðåàëèçàöèè íà âû÷èñëèòåëüíûõ ñèñòåìàõ ñïåöèàëüíîãî (êâàçèñèñòîëè-
÷åñêèõ) è îáùåãî íàçíà÷åíèÿ.
Îòìåòèì, ÷òî â äàííîì ñëó÷àå áîëåå ñëàáîå òðåáîâàíèå êâàçèñèñòîëè÷íîñòè
îòëè÷àåòñÿ îò òðåáîâàíèÿ ñèñòîëè÷íîñòè òåì, ÷òî èç îäíîé «èíñòàíöèè» äîïóñêàåò-
ñÿ îäíîâðåìåííàÿ ðàññûëêà äàííûõ ñðàçó â íåñêîëüêî «òî÷åê ïðèåìà».  ñîîòâåò-
ñòâóþùèõ ÊÑÑ ýòî ìîæíî ðåàëèçîâàòü, èñïîëüçóÿ, íàïðèìåð, îïòîýëåêòðîííûå
ýëåìåíòû.
Áóäåì ñ÷èòàòü, ÷òî âðåìÿ âûïîëíåíèÿ îïåðàöèé ñëîæåíèÿ è óìíîæåíèÿ îäèíà-
êîâî è ðàâíî îäíîìó òàêòó, à åäèíñòâåííûì óñëîâèåì, òðåáóåìûì äëÿ îïåðàöèé,
ÿâëÿåòñÿ âûïîëíåíèå çàêîíîâ àññîöèàòèâíîñòè è êîììóòàòèâíîñòè äëÿ îïåðàöèè
ñëîæåíèÿ. Ïîýòîìó ïîëó÷åííûå â íàñòîÿùåé ðàáîòå ðåçóëüòàòû âåðíû è â ñëó÷àå,
êîãäà � è � — ëþáûå äðóãèå îïåðàöèè, óäîâëåòâîðÿþùèå ýòîìó òðåáîâàíèþ: ëîãè-
÷åñêèå
è � , òåîðåòèêî-ìíîæåñòâåííûå � è � èëè, íàïðèìåð, max è min.
ÎÏÒÈÌÀËÜÍÛÅ ÀËÃÎÐÈÒÌÛ ×ÈÑËÅÍÍÎÃÎ ÐÅØÅÍÈß ÇÖÔ
Ñòàíäàðòíûé ïîñëåäîâàòåëüíûé àëãîðèòì âûïîëíåíèÿ C ïåðåñ÷åòîâ ñãëàæèâàíèÿ
ïî ôîðìóëå (1) èìååò âèä
FOR t C� 1, DO
FOR i l1 11� , DO
FOR i l2 21� , DO
p1 0� ;
FOR s m m1 1 1� � , DO (3)
FOR s m m2 2 2� � , DO
p p x fi s i s s s1 1 1 1 2 2 1 2
� � �� �, , ;
x pi i1 2 1, � .
Ñîãëàñíî àëãîðèòìó äëÿ ïåðåñ÷åòà ïåðåìåííîé xi i1 2, íà t-ì øàãå áåðóòñÿ
çíà÷åíèÿ xi m i m1 1 2 2� �, , x xi m i m i m i1 1 2 2 1 1 21� � � �, ,, ... , , xi m i1 1 2 1� �, , ... , xi m i m1 1 2 2� �, ;
xi m i m1 1 2 21� � �, , xi m i m1 1 2 21 1� � � � � �, � x x xi m i i m i i m i m1 1 2 1 1 2 1 1 2 2
1 1 1 1� � � � � � � �, , ,
, , ... , ; ...;
x x x xi i m i i m i i i i1 2 2 1 2 2 1 2 1 21 1 1 1 1 1� � � � � � � �, , , ,, , ... , , , ... , ; , ,..., , ,x x xi i m i i m i i m1 2 2 1 2 2 1 2 21 1� � � � �
... ,
,
x
i i1 2 1�
, êîòîðûå ÿâëÿþòñÿ óæå ïåðåñ÷èòàííûìè íà ýòîì øàãå.
Ïåðåõîä ê ïàðàëëåëüíîé âåðñèè àëãîðèòìà (3) îñóùåñòâëÿåì, èñïîëüçóÿ êâàçèñèñ-
òîëè÷åñêèé ìåòîä (ÊÑÌ) [24] îðãàíèçàöèè âû÷èñëåíèé, ñîãëàñíî êîòîðîìó: 1) ïåðå-
ìåííûå ïåðåñ÷èòûâàþòñÿ â îòäåëüíûõ, ñäâèíóòûõ ìåæäó ñîáîé, âåòâÿõ; ñëåäîâàòåëü-
íî, ãëàâíûì ïðèåìîì ïîâûøåíèÿ ñòåïåíè ïàðàëëåëèçìà, êðîìå ñîáñòâåííî ðàñïàðàë-
ëåëèâàíèÿ, ÿâëÿåòñÿ êîíâåéåðèçàöèÿ; 2) äîïóñêàåòñÿ îäíîâðåìåííàÿ ïåðåäà÷à äàííûõ
èç îäíîé «èíñòàíöèè» ñðàçó â M «òî÷åê ïðèåìà»; 3) äëÿ ïåðåñ÷åòà çíà÷åíèÿ ïðîèç-
âîëüíîé ïåðåìåííîé íà íåêîòîðîì øàãå èñïîëüçóåòñÿ ìàêñèìàëüíîå êîëè÷åñòâî óæå
ïåðåñ÷èòàííûõ íà ýòîì øàãå çíà÷åíèé; 4) ôóíêöèîíàëüíàÿ ýêâèâàëåíòíîñòü ñ ïîñëåäî-
âàòåëüíûì ñïîñîáîì âû÷èñëåíèé îáåñïå÷èâàåòñÿ âûïîëíåíèåì ñóììèðîâàíèÿ â îïðå-
äåëåííîì ïîðÿäêå, íàïðèìåð, äëÿ ïåðåñ÷åòà xi i1 2, ïðè m1 2� , m2 1� îí áóäåò òàêèì:
x x f x f x f xi i i i i i i i i1 2 1 2 1 2 1 20 0 1 0 1 2 1 2 1, , , , , , ,� � � �� � � � � 1 2 1 21 1 1 1 2 2 0� � � � �� �, , , ,i i if x f
� � � �
� � � � � � �x f x f x f x
i i i i i i i
1 2 1 2 1 2 11 1 0 2 1 2 1 1 1 1 1 1, , , , , , , , , ,i i if x f
2 1 21 1 1 2 1 2 1� � � � � �� �
� � � �� � � � � � �x f x f x f xi i i i i i i1 2 1 2 1 2 11 1 0 2 2 0 1 1 1 1 2, , , , , , ,i i if x f
2 1 21 2 1 1 0 1� � ��, , , ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 5
5) êàæäîå èç ïåðåñ÷èòàííûõ çíà÷åíèé èñïîëüçóåòñÿ M �1 âåòâüþ, ãäå îíî ÿâëÿ-
åòñÿ àðãóìåíòîì, íà ñëåäóþùåì æå òàêòå.
 ñëó÷àå, êîãäà âåñîâûå êîýôôèöèåíòû ðàâíû ìåæäó ñîáîé, ò.å. f m m� � �
1 2, �
� �� � � �f f fm m0 0 1 2, , , íà îñíîâàíèè ÊÑÌ ïðåäëàãàåòñÿ ÏÊÀ ðåøåíèÿ äâóìåð-
íîé ÇÖÔ:
FOR i l1 11� , DO SYNCH
DELAY (( )( ))4 2 12 1m i� �
FOR i l2 21� , DO SYNCH
DELAY ( )2 22i �
FOR t C� 1, DO
BEGIN FOR u m m� � � �1 2 1 2 1 11 2, ( )( ) DO (4)
x x u ui i i i1 2 1 2
2 2, , (( / ) [ / ])� � �IF THEN
xi m u m i m u m u1 1 2 2 2 21 4 2 2 1 2 1 1� � � � � � � � � �[( )/ ( )], / ( )[( )/ (4 22m � )]
ELSE xi u m m i u m u m1 2 2 2 2 22 2 4 2 2 1 2 2 1 2� � � � � � � � � �[( )/ ( )], / / ( )[( 2 4 22)/( )]m �
x x fi i i i1 2 1 2, ,� � ;
DELAY(2); END.
Ïåðâûå äâà öèêëà â êîíñòðóêöèè (4) îáîçíà÷àþò îäíîâðåìåííûé çàïóñê l l1 2 ïà-
ðàëëåëüíûõ âåòâåé ñ ñèíõðîíèçàöèåé èõ ÷åðåç êàæäóþ îïåðàöèþ. Îïåðàòîð DELAY
( )p� îñóùåñòâëÿåò çàäåðæêó íà p� òàêòîâ. Öèêë ïî ïåðåìåííîé t ñîîòâåòñòâóåò âûïîë-
íåíèþ C ïåðåñ÷åòîâ ñãëàæèâàíèÿ. Âíóòðåííèé öèêë îïðåäåëÿåò ñóììèðîâàíèå àðãó-
ìåíòîâ â íóæíîì ïîðÿäêå. Äàëåå ðåçóëüòàòû ñóììèðîâàíèÿ óìíîæàþòñÿ íà f è ïðî-
ïóñêàåòñÿ äâà òàêòà. Ïîñëå ýòîãî âû÷èñëÿåòñÿ ñëåäóþùàÿ èòåðàöèÿ.  ïðèâåäåííîé
êîíñòðóêöèè è äàëåå çàïèñü [ ]a îáîçíà÷àåò öåëóþ ÷àñòü ÷èñëà a.
Òåîðåìà 1. Àëãîðèòì (4):
à) ýêâèâàëåíòåí àëãîðèòìó (3) ñ òî÷íîñòüþ äî ñîîòíîøåíèé àññîöèàòèâíîñòè è
êîììóòàòèâíîñòè;
á) èñïîëüçóåò ïåðåìåííûå x x x x xm m m m l m l1 1 1 2 1 1 1 21 2 1 2 1 1 2� � � � � �, , , , ,, ,... , , ,... , m2
è òîëüêî èõ;
â) èìååò ìèíèìàëüíîå âðåìÿ ðåàëèçàöèè ñðåäè âñåõ àëãîðèòìîâ, óäîâëåòâîðÿ-
þùèõ ïï. à) è á).
Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ äåòàëüíî èçëîæåíî â [24] è îñíîâàíî íà
äîêàçàòåëüñòâå äâóõ âñïîìîãàòåëüíûõ óòâåðæäåíèé. Ïåðâîå èç íèõ ãîâîðèò îá îòñóò-
ñòâèè êîíêóðåíöèè íàä ïàìÿòüþ ïðè ðåàëèçàöèè àëãîðèòìà (4), âòîðîå — î ìèíè-
ìàëüíîñòè âûñîòû äåðåâà ýòîãî àëãîðèòìà â êëàññå âñåõ ýêâèâàëåíòíûõ äåðåâüåâ.
Èç òåîðåìû 1 ñëåäóåò, ÷òî àëãîðèòì (4) ÿâëÿåòñÿ îïòèìàëüíûì ïî áûñòðîäåé-
ñòâèþ è èñïîëüçîâàíèþ ïàìÿòè (èñïîëüçóåò îáúåì ïàìÿòè, íåîáõîäèìûé äëÿ ââîäà
íà÷àëüíûõ äàííûõ) â êëàññå ýêâèâàëåíòíûõ ïî Èà àëãîðèòìîâ ñ òî÷íîñòüþ äî âû-
ïîëíåíèÿ ñîîòíîøåíèé àññîöèàòèâíîñòè è êîììóòàòèâíîñòè.
 ñëó÷àå, êîãäà âåñîâûå êîýôôèöèåíòû — ðàçíûå ìåæäó ñîáîé, ÏÊÀ (4) íå-
ñêîëüêî èçìåíèòñÿ, ïîñêîëüêó â êàæäîé èç ïàðàëëåëüíûõ âåòâåé îäíîâðåìåííî
ñ ñóììèðîâàíèåì ïðîèñõîäèò ïîäãîòîâêà îäíîãî èç ïîñëåäóþùèõ ñëàãàåìûõ, ò.å.
óìíîæåíèå íà ñîîòâåòñòâóþùèé âåñîâîé êîýôôèöèåíò. Äëÿ ñîõðàíåíèÿ ñóììèðóå-
ìûõ âåëè÷èí äëÿ êàæäîé âåòâè íåîáõîäèìà, êàê ìèíèìóì, îäíà äîïîëíèòåëüíàÿ
ïåðåìåííàÿ. Ñîîòâåòñòâóþùóþ àëãîðèòìè÷åñêóþ êîíñòðóêöèþ ïîëó÷àåì èç (4), çà-
ìåíèâ ôðàãìåíò ìåæäó îïåðàòîðàìè BEGIN è END ôðàãìåíòîì
FOR u m m� � �1 2 1 2 11 2, ( )( ) DO
BEGIN x u f xi i i i1 2 1 2
1 0 0, , ,( )� � �IF THEN ELSE x yi i i i1 2 1 2, ,� , (5)
y f xi i h u m m h u m i h u m m i h1 2 1 1 2 2 2 1 1 1 2 2 2, ( , , ), ( , ) ( , , ),� � � � ( , )u m2
END;
DELAY (2).
6 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
Çäåñü ïðåäïîëàãàåòñÿ, ÷òî îïåðàòîðû xi i1 2, � � è yi i1 2, �� , ðàçäåëåííûå çàïÿòîé,
âûïîëíÿþòñÿ ñèíõðîííî. Öåëî÷èñëåííûå ôóíêöèè h u m m
1 1 2( , , ), h u m2 2( , ) — ñî-
îòâåòñòâåííî ñëåäóþùèå óñëîâíûå îïåðàòîðû:
IF (( / ) [ / ])u u2 2� THEN [( ) / ( )]u m m� � �1 4 22 1 ELSE [( ) / ( )]u m m� � �2 2 4 22 2 ,
IF (( / ) [ / ])u u2 2� THEN u m m u m/ ( )[( ) / ( )]2 1 2 1 1 4 22 2 2� � � � � �
ELSE u m u m m/ / ( )[( ) / ( )]2 1 2 2 1 2 2 4 22 2 2� � � � � � .
 ðàáîòå [25] íà îñíîâàíèè ïðåäëîæåííîãî ÊÑÌ ïîñòðîåíû îïòèìàëüíûå ïî
áûñòðîäåéñòâèþ ÏÊÀ ðåøåíèÿ òðåõìåðíîé ÇÖÔ. Îïòèìàëüíîñòü äîêàçàíà â ñîîò-
âåòñòâóþùèõ êëàññàõ àëãîðèòìîâ, ýêâèâàëåíòíûõ ïî ÈÃ.
Ïîñëåäîâàòåëüíûé àëãîðèòì ðåøåíèÿ n-ìåðíîé ÇÖÔ èìååò âèä
FOR t C� 1, DO
FOR i l1 11� , DO
FOR i l2 21� , DO
...............................
FOR i ln n� 1, DO (6)
p1 0� ;
FOR ALL ( , , , ) {( , , , ) : , ;s s s r r r r m mn n1 2 1 2 1 1 1� �
� �
r m m r m mn n n2 2 2� � � �, ; ; , }� DO
p p x fi s i s i s s s sn n n1 1 1 1 2 2 1 2
� � �� � �, , , , , ,� � ;
x pi i in1 2 1, , ,� � .
Ñîãëàñíî (6) t-å ïðèáëèæåíèå èñïîëüçóåò ÷àñòü óæå ïåðåñ÷èòàííûõ äëÿ ýòîãî
ïðèáëèæåíèÿ çíà÷åíèé. Åñëè áîëåå òî÷ío, òî íîâîå ïðèáëèæåíèå èñïîëüçóåòñÿ ïðè
( ) ( )s s s1 1 20 0 0�
� � �
� � � � �
� � � � � � � ��( ) ( )s s s s s s sn n1 2 3 1 2 10 0 0 0 0 0 0� � .
Íà îñíîâàíèè ÊÑÌ [26] ïîëó÷àåì ÏÊÀ ðåøåíèÿ n-ìåðíîé ÇÖÔ:
t m t m t mn n1 1 2 22 1 2 1 2 1� � � � � �; ; ... ; ;
FOR ALL ( , , , ) {( , , , ):i i i i i in n1 2 1 2� �
i l i l i ln n1 1 2 21 1 1� � �, ; , ; ; , }� DO SYNCH
DELAY ( ( ( ) ( ) ( )2 1 1 12 3 1 3 4 2 1t t t i t t t i t i in n n n n� � � � � � � � � � ��� � � �1))
FOR t C� 1, DO
BEGIN FOR u t t t n� � �1 1 2, � DO (7)
BEGIN xi i in1 2, , ,� � IF ( )u � 1 THEN f xi i in0 0 0 1 2, , , , , ,� ��
ELSE x yi i i i i in n1 2 1 2, , , , , ,� �� ,
y f xi i i
h h h i h i h i hn
n n n1 2
1
0
2
0 0
1 1
0
2 2
0 0, , ,
, , , , , ,�
� �
� �
� � �
END;
DELAY (2); END.
 àëãîðèòìå (7) îïåðàòîðû xi i in1 2, , ,� �� è yi i in1 2, , ,� �� , ðàçäåëåííûå
çàïÿòîé, âûïîëíÿþòñÿ â ñèíõðîííîì ðåæèìå. Öåëî÷èñëåííûå ôóíêöèè
h u m m mn1
0
1 2( , , , , )� , h u m m m h u mn n n2
0
2 3
0( , , , , ) , , ( , )� � — ñîîòâåòñòâåííî ñëåäó-
þùèå óñëîâíûå îïåðàòîðû:
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 7
IF (( / ) [ / ])u u2 2� THEN [( ) / ( )]u t t t mn� � � �1 2 2 3 1�
ELSE [( ) / ( ) / ]u t t t n� � � �1 2 1 22 3 � ,
IF (( / ) [ / ])u u2 2� THEN
[( ) / ( )] [( ) / ( )]u t t t m t u t t tn n� � � � � � � �1 2 1 23 4 2 2 2 3� �
ELSE [( ) / ( ) / ] [( ) / ( ) /u t t t t u t t tn n� � � � � � � � �1 2 1 2 1 2 1 23 4 2 2 3� � ] ,
���������������������������.
IF (( / ) [ / ])u u2 2� THEN u m t u tn n n/ [( ) / ( )]2 1 1 2� � � �
ELSE u t u tn n/ / [( ) / ( ) / ]2 1 2 1 2 1 2� � � � .
Òåîðåìà 2. Àëãîðèòì (7):
à) ýêâèâàëåíòåí àëãîðèòìó (6) ñ òî÷íîñòüþ äî ñîîòíîøåíèé àññîöèàòèâíîñòè è
êîììóòàòèâíîñòè;
á) èñïîëüçóåò ïåðåìåííûå òîëüêî èç íàáîðà
x x xm m m l m l m l mn n1 1 1 1 1 11 2 1 1 2 2� � � � � �, , , , , , , , ,, , , ,� � �� �
n n
y yl l l; , ,, , , , , ,1 1 1 1 2� �� ;
â) èìååò ìèíèìàëüíîå âðåìÿ ðåàëèçàöèè ñðåäè âñåõ àëãîðèòìîâ, óäîâëåòâîðÿ-
þùèõ ïï. à) è á).
Äîêàçàòåëüñòâî ýòîãî óòâåðæäåíèÿ ïîäðîáíî èçëîæåíî â [26].
Íà îñíîâàíèè òåîðåìû 2 ìîæíî óòâåðæäàòü, ÷òî àëãîðèòì (7) ÿâëÿåòñÿ îïòè-
ìàëüíûì ïî áûñòðîäåéñòâèþ â êëàññå àëãîðèòìîâ, ýêâèâàëåíòíûõ ïî Èà ñ òî÷íîñ-
òüþ äî âûïîëíåíèÿ ñîîòíîøåíèé àññîöèàòèâíîñòè è êîììóòàòèâíîñòè.
Ïðåäëîæåííûå ÏÊÀ ðåøåíèÿ ÇÖÔ îðèåíòèðîâàíû íà ðåàëèçàöèþ â ñîîòâåò-
ñòâóþùèõ êâàçèñèñòîëè÷åñêèõ âû÷èñëèòåëüíûõ ñòðóêòóðàõ [20].
ÎÏÒÈÌÀËÜÍÛÅ ÀËÃÎÐÈÒÌÛ ÂÛÏÎËÍÅÍÈß
ÌÍÎÃÎÐÀÇÎÂÎÉ ÊÀÑÊÀÄÍÎÉ ÔÈËÜÒÐÀÖÈÈ
Ïîñëåäîâàòåëüíûé àëãîðèòì ðåøåíèÿ îäíîìåðíîé ÇÌÊÖÔ èìååò âèä
FOR u r1 1� , DO
FOR p C u� 1 1 1, ( ) DO
FOR i N1 11� , DO
t � 0; (8)
FOR s m p u m p u1 1 1 1 1� � ( , ), ( , ) DO
t t f p u xs i s� � � �1 1 11( , ) ;
x ti1
� .
Ïðèìåíÿÿ ÊÑÌ îðãàíèçàöèè âû÷èñëåíèé äëÿ êàæäîãî àêòà ôèëüòðàöèè, ïîëó-
÷àåì ÏÊÀ ðåøåíèÿ îäíîìåðíîé ÇÌÊÖÔ:
FOR i N1 11� , DO SYNCH
DELAY ( )2 21i �
FOR u r1 1� , DO
FOR p C u� 1 1 1, ( ) DO
BEGIN FOR s m p u1 1 11 2 1� �, ( , ) DO (9)
BEGIN xi1
� IF ( )s1 1� THEN f p u xi0 1 1
( , )� ELSE x zi i1 1
� ,
z f p u x
i h s m p u i h s m p u
1 1 1 1 1 1 1 11� � �( , ( , )) ( , ( , ))( , ) END;
DELAY (2); END.
 êîíñòðóêöèè (9) îïåðàòîðû xi1
�� è zi1
� � , ðàçäåëåííûå çàïÿòîé, âû-
ïîëíÿþòñÿ ñèíõðîííî, à ôóíêöèÿ h s m p u( , ( , ))1 1 1 — óñëîâíûé îïåðàòîð
IF(( / ) [ / ])s s1 12 2� THEN s m p u1 1 12 1/ ( , )� � ELSE ( ) /s1 1 2� .
Ïóñòü � — êëàññ àëãîðèòìîâ, êàæäûé èç êîòîðûõ ýêâèâàëåíòåí ïîñëåäîâà-
8 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
òåëüíîìó àëãîðèòìó (8) ñ òî÷íîñòüþ äî âûïîëíåíèÿ ñîîòíîøåíèé àññîöèàòèâíîñ-
òè è êîììóòàòèâíîñòè è èñïîëüçóåò ïåðåìåííûå òîëüêî èç íàáîðà z z z N1 2 1
, , ,� ;
x
m1 10�
, x x x xm N2 1 210 1� , , , ,... ,� , x xN N m1 1 101� �, ,� . Çäåñü m m p u10 1 1� max{ ( , ):
p C u u r� �1 11 1 1, ( ); , }.
Òåîðåìà 3. Àëãîðèòì (9) ïðèíàäëåæèò êëàññó � è èìååò ìèíèìàëüíîå âðåìÿ
ðåàëèçàöèè ñðåäè âñåõ àëãîðèòìîâ ýòîãî êëàññà.
Äîêàçàòåëüñòâî äàííîãî óòâåðæäåíèÿ îñóùåñòâëÿåòñÿ àíàëîãè÷íî äîêàçàòåëü-
ñòâó òåîðåìû â [22], ê òîìó æå íåîáõîäèìî ó÷åñòü, ÷òî: à) ðåçóëüòàò ïåðåñ÷åòà ïåðå-
ìåííîé x
i1
ïðè q-ì àêòå ôèëüòðàöèè â p-ì êàñêàäå ãåíåðèðóåòñÿ íà òàêòå ñ íîìå-
ðîì 2 1 1 2 1 1 1 1 2 2 21 1 1 1 1 1( ( , ) ( , ) ( ( ), ) ( , ) ( , )m m m C m m� � � � � � �� � m C1 1 2 2( ( ), ) ��
� �� � � � � � � � � �m q m q m C q q m q m
1 1 1 1 1 11 1 2 1 1 1 1( , ) ( , ) ( ( ), ) ( , ) ( , ) ( , ))2 1q m p q� � ��
� � � � � � � �3 1 2 1 2 41 1 1 1( ( ) ( ) ( ) )C C C q p i� ; á) ñ÷èòûâàíèå çíà÷åíèÿ ýòîé ïåðå-
ìåííîé êàê àðãóìåíòà îñóùåñòâëÿåòñÿ äëÿ âñåõ u m p q� � �1 1( , ) , � � �m p q1 1 1( , ) ,�
� , , ,... , ( , ) , ( , )0 1 11 1m p q m p q� , åñëè p C q� 1 ( ), èëè æå äëÿ âñåõ u m q� � �1 1 1( , ) ,
� � � �m q m C q q m C q q1 1 1 1 11 1 1 0 1 1( , ) , , , ,... , ( ( ), ) , ( ( ), )� , åñëè p C q� 1 ( ), â âåòâÿõ
i u1 � .
Òàêèì îáðàçîì, ÏÊÀ (9) ÿâëÿåòñÿ îïòèìàëüíûì ïî áûñòðîäåéñòâèþ â êëàññå
àëãîðèòìîâ, ýêâèâàëåíòíûõ ïî Èà ñ òî÷íîñòüþ äî âûïîëíåíèÿ ñîîòíîøåíèé àññî-
öèàòèâíîñòè è êîììóòàòèâíîñòè. Ýòîò àëãîðèòì ïðåäïîëàãàåò èçìåíåíèå êîëè÷åñ-
òâà ôèëüòðîâ è èõ õàðàêòåðèñòèê äëÿ êàæäîãî àêòà ðåàëèçàöèè êàñêàäíîé ôèëüòðà-
öèè, ÷òî ñ ïðàêòè÷åñêîé òî÷êè çðåíèÿ âåñüìà âàæíî.
Îïòèìàëüíûé ïî áûñòðîäåéñòâèþ ÏÊÀ ÷èñëåííîãî ðåøåíèÿ äâóìåðíîé
ÇÌÊÖÔ ïðåäëîæåí â ðàáîòå [27].
Ïîñëåäîâàòåëüíûé àëãîðèòì ðåøåíèÿ òðåõìåðíîé ÇÌÊÖÔ çàäàåòñÿ ãíåçäîì
öèêëîâ
FOR u r1 1� , DO
FOR p C u� 1 1 1, ( ) DO
FOR i l1 11� , DO
FOR i l2 21� , DO
FOR i l3 31� , DO (10)
t � 0;
FOR ( , , ) {( , , ): ( , ), ( , );s s s r r r r m p u m p u1 2 3 1 2 3 1 1 1 1 1
� �
r m p u m p u r m p u m p u2 2 1 2 1 3 3 1 3 1� � � �( , ), ( , ); ( , ), ( , )} DO
t t f p u xs s s i s i s i s� � � � � �1 2 3 1 1 2 2 3 31, , , ,( , ) ;
x ti i i1 2 3, , � .
Ïåðåõîä ê ôóíêöèîíàëüíî ýêâèâàëåíòíîé ïàðàëëåëüíîé âåðñèè àëãîðèòìà (10)
îñóùåñòâëÿåì ñ èñïîëüçîâàíèåì ÊÑÌ [28].  ðåçóëüòàòå ïîëó÷àåì ÏÊÀ ðåøåíèÿ
òðåõìåðíîé ÇÌÊÖÔ:
FOR i l1 11� , DO SYNCH
DELAY (( ( , ) )( ( , ) )( ))4 1 1 2 2 1 1 1 12 3 1m m i� � �
FOR i l2 21� , DO SYNCH
DELAY (( ( , ) )( ))4 1 1 2 13 2m i� �
FOR i l3 31� , DO SYNCH
DELAY ( ( ))2 13i �
FOR u r1 1� , DO (11)
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 9
FOR p C u� 1 1 1, ( ) DO
BEGIN FOR s m p u m p u m p u� � � �1 2 1 2 1 2 11 1 2 1 3 1, ( ( , ) )( ( , ) )( ( , ) ) DO
BEGIN xi i i1 2 3, , � IF ( )s � 1 THEN f p u xi i i0 0 0 1 1 2 3, , , ,( , )�
ELSE x y yi i i i i i i i i1 2 3 1 2 3 1 2 3, , , , , ,,� �
� f
h s m p u m p u m p u h s m p u1 1 1 2 1 3 1 2 2 1
* *( , ( , ), ( , ), ( , )), ( , ( , ), ( , )), ( , ( , ))* ( , )
m p u h s m p u
p u
3 1 3 3 1
1 �
�
� �
x
i h s m p u m p u m p u i h s m1 1 1 1 2 1 3 1 2 2 2
* *( , ( , ), ( , ), ( , )), ( , ( , ), ( , )), ( , ( , ))*p u m p u i h s m p u1 3 1 3 3 3 1�
END;
DELAY ( ( , ))L p u
1
; END.
Èñïîëüçóåìûå â (11) öåëî÷èñëåííûå ôóíêöèè h s m p u m p u1 1 1 2 1
*( , ( , ), ( , ),
m p u3 1( , )) , h s m p u m p u h s m p u2 2 1 3 1 3 3 1
* *( , ( , ), ( , )), ( , ( , )) è L p u( , )1 îïðåäåëåíû â [28].
Ïóñòü âûïîëíÿþòñÿ ñëåäóþùèå ðàâåíñòâà:
m m m C m m md d d d d d( , ) ( , ) ( ( ), ) ( , ) ( , )1 1 2 1 1 1 1 2 2 21� � � � � � �� � ( ( ), )C1 2 2 ��
�� �m rd ( , )1 m r m C r r M dd d d( , ) ( ( ), ) ; ,2 2 31� � � �� . (12)
Ðàññìîòðèì � — êëàññ àëãîðèòìîâ, ýêâèâàëåíòíûõ àëãîðèòìó (10) ñ òî÷íîñ-
òüþ äî âûïîëíåíèÿ çàêîíîâ àññîöèàòèâíîñòè è êîììóòàòèâíîñòè è òàêèõ, ÷òî èñ-
ïîëüçóþò ïåðåìåííûå òîëüêî èç íàáîðà x m M M1 1 10 2 3� � �, , , x m M M1 1 20 2 3� � �, , ,�
� �, , ,
, , , ,x xl m l M l M1 1 1 1 0 2 2 3 3� � � ; y y yl l l1 1 1 1 1 2 1 2 3, , , , , ,, � �� . Çäåñü m m0 1 1 1� max{ ( , ),
m m C m r m r m1 1 1 1 1 12 1 1 1 1 2( , ),... , ( ( ), ),... , ( , ), ( , ),... , ( ( ), )}C r r1 .
Òåîðåìà 4. Åñëè âûïîëíÿåòñÿ óñëîâèå (12), òî àëãîðèòì (11) ïðèíàäëåæèò êëàñ-
ñó � è èìååò ìèíèìàëüíîå âðåìÿ ðåàëèçàöèè ñðåäè âñåõ àëãîðèòìîâ ýòîãî êëàññà.
Äîêàçàòåëüñòâî äàííîãî óòâåðæäåíèÿ ïðèâåäåíî â [28].
Ïðåäëîæåííûå ÏÊÀ ðåøåíèÿ ÇÌÊÖÔ îðèåíòèðîâàíû íà ðåàëèçàöèþ íà
ÊÑÑ [20, 28].
ÎÏÒÈÌÈÇÀÖÈß ÊÂÀÇÈÑÈÑÒÎËÈ×ÅÑÊÈÕ ÂÛ×ÈÑËÅÍÈÉ ÏÐÈ ÐÅØÅÍÈÈ ÇÖÔ
Êâàçèñèñòîëè÷åñêèå âû÷èñëèòåëüíûå ñòðóêòóðû äëÿ ðåàëèçàöèè ðàçðàáîòàííûõ
â ïðåäûäóùèõ ðàçäåëàõ îïòèìàëüíûõ ïî áûñòðîäåéñòâèþ ÏÊÀ ñîñòîÿò èç ýëå-
ìåíòàðíûõ ôóíêöèîíàëüíûõ ýëåìåíòîâ, ðåàëèçóþùèõ îäíó èç äâóõ îïåðàöèé: � ,
�;
�, ; ,� � èëè min, max. Ïðè ýòîì â ñëó÷àå ðåøåíèÿ ÇÖÔ ìàêñèìàëüíîå êîëè-
÷åñòâî èñïîëüçóåìûõ â ýòèõ ýëåìåíòàõ âûõîäíûõ êàíàëîâ ñâÿçè ðàâíî ðàçìåðó
ïëàâàþùåãî îêíà. Ñëåäîâàòåëüíî, äëÿ êàæäîãî çíà÷åíèÿ M íåîáõîäèìî ïðîåêòè-
ðîâàòü îòäåëüíóþ âû÷èñëèòåëüíóþ ñòðóêòóðó, ÷òî íåâîçìîæíî ñäåëàòü â òè-
ïè÷íûõ ñèòóàöèÿõ. Áîëåå ðåàëüíûì âûãëÿäèò ñëó÷àé, êîãäà ðàçðàáîòàííûé äëÿ
ïðîèçâîëüíîãî M ÏÊÀ íåîáõîäèìî âëîæèòü â àïïàðàòíî ðåàëèçîâàííóþ ñõåìó
ñ ôèêñèðîâàííûì êîëè÷åñòâîì âõîäíûõ è âûõîäíûõ êàíàëîâ êàæäîãî åå èñïîë-
íÿþùåãî ýëåìåíòà. Òàêèì îáðàçîì, ñ òî÷êè çðåíèÿ ïðàêòè÷åñêîé ðåàëèçàöèè
âàæíîé îêàçûâàåòñÿ ïðîáëåìà óìåíüøåíèÿ êîëè÷åñòâà âûõîäíûõ êàíàëîâ ñâÿçè
è îöåíêè â ýòîì ñëó÷àå áûñòðîäåéñòâèÿ ñîîòâåòñòâóþùèõ ÏÊÀ. Ñëåäîâàòåëüíî,
ìîæíî ãîâîðèòü î ñâîåîáðàçíîé çàäà÷å îïòèìèçàöèè ÷èñëà êîììóòàöèîííûõ ýëå-
ìåíòîâ, ðåøåíèå êîòîðîé çíà÷èòåëüíî óâåëè÷èò âîçìîæíîñòè ðåàëèçàöèè ýòèõ
àëãîðèòìîâ íà ñïåöèàëèçèðîâàííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ.
Èòàê, îðãàíèçàöèþ êâàçèñèñòîëè÷åñêèõ âû÷èñëåíèé â ÇÖÔ îñóùåñòâëÿåì
ïðè óñëîâèè, ÷òî êîëè÷åñòâî âûõîäíûõ êàíàëîâ ñâÿçè K ÿâëÿåòñÿ ïðåäâàðèòåëüíî
çàäàííûì, ïðè÷åì 1� �K M. Òðåáóåì, ÷òîáû èíôîðìàöèîííûå ãðàôû ñîîòâåò-
ñòâóþùèõ ÏÊÀ áåç îãðàíè÷åíèé ( )K M� è ñ îãðàíè÷åíèÿìè íà ÷èñëî êàíàëîâ ñî-
âïàäàëè.
 ðåçóëüòàòå àíàëèçà ïîòàêòîâûõ ñõåì îïòèìàëüíûõ ïî áûñòðîäåéñòâèþ àëãî-
ðèòìîâ ðåøåíèÿ îäíî-, äâó- è òðåõìåðíîé ÇÖÔ, ó÷èòûâàÿ ðåãóëÿðíóþ ñòðóêòóðó
çàäàâàåìûõ èìè âû÷èñëåíèé, ïðåäëîæåíà òåõíèêà [29, 30] îïðåäåëåíèÿ âîçìîæíûõ
10 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
çíà÷åíèé K äëÿ êàæäîé çàäà÷è. Ðàçðàáîòàíû àëãîðèòìè÷åñêèå êîíñòðóêöèè äëÿ
îïòèìàëüíîé îðãàíèçàöèè êâàçèñèñòîëè÷åñêèõ âû÷èñëåíèé, îòëè÷àþùèåñÿ îò ïðè-
âåäåííûõ â [22, 24, 25] âèäîì îïåðàòîðîâ çàäåðæêè. Òàê, â ñëó÷àå ðåøåíèÿ îäíî-
ìåðíîé ÇÖÔ ïåðâûé è âòîðîé èç ýòèõ îïåðàòîðîâ
èìåþò ñîîòâåòñòâåííî ñëåäóþùèé âèä: DELAY
( ( ))D i1 1� , DELAY ( )L0 . Â òàáë. 1 äëÿ êàæäîãî èç
âîçìîæíûõ çíà÷åíèé K îïðåäåëåíû öåëî÷èñëåííûå
âåëè÷èíû D è L0 , à â òàáë. 2 ïðèâåäåíû ÷èñëåííûå
îöåíêè óñêîðåíèÿ S K( ) [29] ñîîòâåòñòâóþùèõ ÏÊÀ
ðåøåíèÿ îäíîìåðíîé çàäà÷è äëÿ ðàçíûõ çíà÷åíèé m1
â ñëó÷àå, êîãäà âåñîâûå êîýôôèöèåíòû ÿâëÿþòñÿ
ðàâíûìè è C � 5, N � 1000. Âèäíî, ÷òî ïðè óìåíüøåíèè ÷èñëà âûõîäíûõ êàíàëîâ
ñâÿçè îò ( )2 11m � äî 2 óñêîðåíèå óìåíüøàåòñÿ ïðèáëèçèòåëüíî â 1,5 ðàçà. Çäåñü
M m� �2 11 .
Ïðè ðåøåíèè äâóìåðíîé ÇÖÔ òðè îïåðàòîðà çàäåðæêè èìåþò ñîîòâåòñòâåííî
âèä: DELAY ( ( ))D i1 1 1� , DELAY ( ( ))D i2 2 1� , DELAY ( )L� . Âûðàæåíèÿ äëÿ öåëî-
÷èñëåííûõ âåëè÷èí D D L1 2, , � â çàâèñèìîñòè îò çíà÷åíèÿ K ïðèâåäåíû â òàáë. 3.
 ðàáîòå [30] îïðåäåëå-
íû äâà îïåðàòîðà çàäåð-
æêè äëÿ òðåõìåðíîé çà-
äà÷è è óñòàíîâëåíî, ÷òî
â ñëó÷àå, êîãäà âåñîâûå
êîýôôèöèåíòû ÿâëÿþòñÿ
ðàâíûìè, óìåíüøåíèå K
îò M äî 2 ïðèâîäèò ê
óìåíüøåíèþ óñêîðåíèÿ
êâàçèñèñòîëè÷åñêèõ âû-
÷èñëåíèé ïðèáëèçèòåëü-
íî â 1,53 ðàçà ïðè ðåøå-
íèè äâóìåðíîé è â 1,85
ðàçà ïðè ðåøåíèè òðåõ-
ìåðíîé ÇÖÔ. Òàêèì îá-
ðàçîì, ïîëó÷åííûå ÷èñ-
ëåííûå îöåíêè óñêîðå-
íèÿ ïðåäëîæåííûõ ÏÊÀ ðåøåíèÿ ÇÖÔ ïðè óñëîâèè 1� �K M ïîäòâåðæäàþò öåëå-
ñîîáðàçíîñòü èñïîëüçîâàíèÿ ýòèõ àëãîðèòìîâ íà ïðàêòèêå.
ÏÅÐÅÕÎÄ Ê ÎÃÐÀÍÈ×ÅÍÍÎÌÓ ÏÀÐÀËËÅËÈÇÌÓ
Êàê áûëî îòìå÷åíî, îïèñàííûå ÏÊÀ ðåøåíèÿ ÇÖÔ îðèåíòèðîâàíû, êàê ïðàâèëî,
íà ðåàëèçàöèþ íà ñïåöèàëèçèðîâàííûõ âû÷èñëèòåëüíûõ ñèñòåìàõ — ÊÑÑ. Ïðè
ïîñòðîåíèè ýòèõ àëãîðèòìîâ íå íàêëàäûâàëèñü íèêàêèå îãðàíè÷åíèÿ íà êîëè÷åñ-
òâî ïàðàëëåëüíî âûïîëíÿåìûõ âåòâåé, êîòîðîå ðàâíÿëîñü ÷èñëó ïåðåñ÷èòûâàåìûõ
çíà÷åíèé ïåðåìåííûõ. Îäíàêî, ÷òîáû ýôôåêòèâíî èñïîëüçîâàòü ïðåäëîæåííûå àë-
ãîðèòìè÷åñêèå êîíñòðóêöèè äëÿ ðåøåíèÿ ñîîòâåòñòâóþùåé çàäà÷è ôèëüòðàöèè íà
íåêîòîðîé óíèâåðñàëüíîé ÝÂÌ ïàðàëëåëüíîãî äåéñòâèÿ ñ çàäàííûì ÷èñëîì ïàðàë-
ëåëüíî ðàáîòàþùèõ ïðîöåññîðîâ, íåîáõîäèìî ðåøàòü ïðîáëåìó ïåðåõîäà îò íå-
îãðàíè÷åííîãî ïàðàëëåëèçìà ê îãðàíè÷åííîìó.  ñâÿçè ñî ñëîæíîñòüþ ýòîé ïðîá-
ëåìû åå ðåøåíèå ïðèâåäåíî äëÿ îòäåëüíûõ ñëó÷àåâ çàäàíèÿ ÷èñëà ïàðàëëåëüíî
âûïîëíÿåìûõ âåòâåé P ïðè óñëîâèè, ÷òî [ / ] /N P N P� , ê òîìó æå 1� �P N .
Åñëè âåñîâûå êîýôôèöèåíòû ðàçíûå, òî ñîîòâåòñòâóþùèå àëãîðèòìû ñ îãðàíè-
÷åííûì ïàðàëëåëèçìîì (ÀÎÏ) ñòðîÿòñÿ ñ ó÷åòîì ðàâåíñòâà [ / ] /P P2 2� .
Òàê, ÀÎÏ ðåøåíèÿ îäíîìåðíîé ÇÖÔ ïðåäëàãàþòñÿ äëÿ ñëåäóþùèõ ñëó÷àåâ [31]:
1) 1 1 11 1� � � P m m, ; 3) P lm m l�
1 1 1 1, , \ { }� ;
2) 1 1 31� � � �P N m N P, , ( / ) ; 4) P l m m l� �
( ), ,1 11 1 �.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 11
Ò à á ë è ö à 1
K D L0
2 3 2 31m �
3 3 m1 2�
m
1
1� 2 3
Ò à á ë è ö à 2
m1 S m( )2 11 � S m( )1 1� S( )3 S( )2
3 17,14 17,11 11,46 11,40
6 31,38 31,32 21,00 20,81
9 45,21 45,13 30,29 29,91
15 71,72 71,59 48,13 47,19
Ò à á ë è ö à 3
K D1 D2 L�
2 6 32m � 3 ( )( )2 1 2 1 21 2m m� � �
3 6 32m � 3 2 21 2 1 2m m m m� � �
2 22m � 4 32m � 2 2 31m �
2 11 2 1 2m m m m� � � 4 22m � 2 3
Ñòðóêòóðà äàííûõ àëãîðèòìîâ ïîõîæà íà ñòðóêòóðó ñîîòâåòñòâóþùèõ îïòè-
ìàëüíûõ ïî áûñòðîäåéñòâèþ àëãîðèòìîâ èç [22]. Îñíîâíûå îòëè÷èÿ çàêëþ÷àþòñÿ
â ñëåäóþùåì:
à) ïåðâûé öèêë ÀÎÏ çàäàåò ñèíõðîííîå âûïîëíåíèå P (åñëè âåñîâûå êîýôôè-
öèåíòû îäèíàêîâû) èëè P / 2 (åñëè âåñîâûå êîýôôèöèåíòû ðàçíûå), à íå N ïàðàë-
ëåëüíûõ âåòâåé;
á) â çàâèñèìîñòè îò ðàññìàòðèâàåìîãî ñëó÷àÿ ïåðâûé îïåðàòîð DELAY ñîäåð-
æèò ñîîòâåòñòâóþùåå âûðàæåíèå äëÿ îïðåäåëåíèÿ êîëè÷åñòâà òàêòîâ çàäåðæêè;
â) ïîñëå öèêëà, çàäàþùåãî ïîñëåäîâàòåëüíîå âûïîëíåíèå C ïåðåñ÷åòîâ ñãëà-
æèâàíèÿ, ââîäèòñÿ íîâûé öèêë, îïðåäåëÿþùèé ïåðåìåííûå, çíà÷åíèÿ êîòîðûõ ïå-
ðåñ÷èòûâàþòñÿ â äàííîé ïàðàëëåëüíîé âåòâè;
ã) âòîðîé îïåðàòîð çàäåðæêè îòñóòñòâóåò.
Íàïðèìåð, â òðåòüåì ñëó÷àå ïðè óñëîâèè ðàâåíñòâà âåñîâûõ êîýôôèöèåíòîâ
ÀÎÏ èìååò âèä
FOR � � 1, P DO SYNCH
DELAY ( ( )( ))2 2 2 11� �� � �w mP
FOR t C� 1, DO
FOR i w m w g m mP P P1 1 1 1� � � �� � � �( ) , ( ( ) ) , DO (13)
BEGIN FOR s m� 1 2 1, DO
x xi i1 1
� � IF (( / ) [ / ])s s2 2� THEN xi s m1 12 1� � �/ ELSE xi s1 1 2� �( )/
x x fi i1 1
� � ; END.
 ïðèâåäåííîé êîíñòðóêöèè g N P w m gP P P� � � �/ , ( ) [( ) / ]1 1 1� � .
Äëÿ ðåøåíèÿ äâóìåðíîé ÇÖÔ ðàçðàáîòàíû ÀÎÏ äëÿ òàêèõ ñëó÷àåâ:
1) P l� 2 ; 7) 1 1 1 2� � �P m P, �;
2) P l� � �� 1 2 ; 8) P l P j1 1 2 0� �, �;
3) P j P l� �0 2�, ; 9) P j m P l m1 0 1 2 2 1 2� � �, , ;
4) P j P l� � �0 21( ),� ; 10) P j m P k m1 0 1 2 0 1 2� � �, ,� ;
5) P P P P m P l� � � �1 2 1 1 2 21, , ; 11) P j m P m1 0 1 2 1 2� � �, ,� .
6) P l P1 1 2� �, �;
Çäåñü � � � �2 1 2 1 2m m m m ; j k0 0 1, \ { }
� .
Ñòðóêòóðà ÀÎÏ äëÿ ðåøåíèÿ äâóìåðíîé ÇÖÔ îïðåäåëÿåòñÿ ñëåäóþùåé êîíñò-
ðóêöèåé [32]:
FOR � � 1 1, A DO SYNCH
DELAY ( ( ))D10 �
FOR w A� 1 2, DO SYNCH
DELAY ( ( ))D w12 (14)
FOR t C� 1, DO
FOR i I I I1 1 2 3� ( ), ( ),� � DO
FOR i J w J w J2 1 2 3� ( ), ( ), DO
T i i( , )1 2 .
Åñëè âåñîâûå êîýôôèöèåíòû îäèíàêîâû, òî A P A P1 1 2 2� �, , à T i i( , )1 2 — ôðàã-
ìåíò, ñîñòîÿùèé èç ïÿòè ïîñëåäíèõ ñòðîê êîíñòðóêöèè (4), â êîòîðîì îïåðàòîð
DELAY (2) çàìåíåí DELAY ( )D13 .  ñëó÷àÿõ 1–4 ïîëàãàåì: P P1 � , P2 1� . Öåëî-
÷èñëåííûå âåëè÷èíû D10 ( )� , D w12 ( ), I1 ( )� , I 2 ( )� , I 3 , J w1 ( ), J w2 ( ), J 3 , D13 îïðåäå-
ëåíû äëÿ êàæäîãî èç ðàññìîòðåííûõ âûøå ñëó÷àåâ çàäàíèÿ P. Íàïðèìåð, â ïÿòîì
ñëó÷àå îíè âû÷èñëÿþòñÿ ïî ôîðìóëàì [32]: D m10 24 2 1( ) ( )( )� �� � � , D w12 ( ) �
� �2 2w , I1 ( )� �� , I l P2 1 1( )� �� � � , I P3 1� , J w J w w1 2( ) ( )� � , J 3 1� , D13 0� .
12 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
 ñëó÷àå, åñëè âåñîâûå êîýôôèöèåíòû ðàçíûå, T i i( , )1 2 â (14) ïðåäñòàâëÿåòñÿ
ôðàãìåíòîì, ñîñòîÿùèì èç çàêëþ÷åííîãî ìåæäó îïåðàòîðàìè BEGIN è END ôðàã-
ìåíòà (5), â êîòîðîì îïåðàòîð DELAY (2) çàìåíåí DELAY ( ) .D13 Ïðè çàäàíèè öèê-
ëîâ ïî ïåðåìåííûì � è w, à òàêæå âû÷èñëåíèè D10 ( )� , D w12 ( ), I1 ( )� , I 2 ( )� , I 3 ,
J w1 ( ), J w2 ( ), J 3 ó÷èòûâàåòñÿ, ÷òî P P P� 1 2 2/ . Êðîìå òîãî, òðåáóåòñÿ âûïîëíåíèå
ñëåäóþùèõ ðàâåíñòâ: [ / ] /l P l P1 1 1 1� , [ / ] /l P l P2 2 2 2� .
 ðàáîòå [32] ïðåäëîæåíû ÀÎÏ äëÿ ðåøåíèÿ òðåõìåðíîé ÇÖÔ â îòäåëüíûõ
ñëó÷àÿõ çàäàíèÿ êîëè÷åñòâà ïàðàëëåëüíî âûïîëíÿåìûõ âåòâåé.
Ïîëó÷åíû óñëîâèÿ, ïðè êîòîðûõ óñêîðåíèå S P ïðåäëîæåííûõ ÀÎÏ [31, 32]
ðàâíî îïòèìàëüíîìó (èëè áëèçêîìó ê íåìó) çíà÷åíèþ. Íàïðèìåð, äëÿ àëãîðèòìà
(13) ïðè óñëîâèè C P ïîëó÷àåì, ÷òî S PP � . Åñëè ïðåäïîëîæèòü, ÷òî
P C m� �( )2 11 , ò.å. C i m� 0 1, i0
�, òî ïðè C N�� óñêîðåíèå ýòîãî àëãîðèòìà âû-
÷èñëÿåòñÿ ïî ôîðìóëå S i m m i m iP � � � �( ( )) / ( )
0
2
1
2
1 0 1 02 1 3 1 .
 ñëó÷àå, êîãäà âåñîâûå êîýôôèöèåíòû îäèíàêîâû, äëÿ ÀÎÏ ðåøåíèÿ äâó-
ìåðíîé ÇÖÔ, ïîñòðîåííîãî äëÿ ïÿòîãî ñëó÷àÿ, ïîëó÷àåì, ÷òî ïðè l l1 2� åãî óñêîðå-
íèå âûðàæàåòñÿ ôîðìóëîé S l P m CP � � �2 1 11 2 2 1/ ( / ( ( )))� . Ïðè m1 2� , C m� �2 1
ïîëó÷àåì, ÷òî S l PP � 15 192 1 / . Ñ óâåëè÷åíèåì çíà÷åíèé C , m1, m2 óñêîðåíèå àëãî-
ðèòìà áóäåò ïðèáëèæàòüñÿ ê ñâîåìó îïòèìàëüíîìó çíà÷åíèþ.
Èññëåäîâàíû [33] òàêæå âîçìîæíîñòè ðåàëèçàöèè íåêîòîðûõ ÀÎÏ íà óíè-
âåðñàëüíûõ ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ ñ îáùåé è ðàñïðåäåëåííîé
ïàìÿòüþ.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ïðåäëîæåí ÊÑÌ îðãàíèçàöèè âû÷èñëåíèé ïðè ðåøåíèè ÇÖÔ ïðîèç-
âîëüíîé ðàçìåðíîñòè. Äàííûé ìåòîä ðàçâèò äëÿ ðåøåíèÿ îäíî-, äâó- è òðåõìåð-
íîé ÇÌÊÖÔ. Íà îñíîâàíèè ÊÑÌ ïîñòðîåíû îïòèìàëüíûå ïî áûñòðîäåéñòâèþ
ÏÊÀ, îðèåíòèðîâàííûå íà ðåàëèçàöèþ íà ñïåöèàëèçèðîâàííûõ âû÷èñëèòåëüíûõ
ñèñòåìàõ — ÊÑÑ. Âîçìîæíîñòè òàêîé ðåàëèçàöèè çíà÷èòåëüíî ðàñøèðåíû çà
ñ÷åò ðåøåíèÿ ïðîáëåìû îïòèìèçàöèè êâàçèñèñòîëè÷åñêèõ âû÷èñëåíèé ïðè íàëî-
æåíèè îãðàíè÷åíèé íà êîëè÷åñòâî âûõîäíûõ êàíàëîâ ñâÿçè. Ðàçðàáîòàíû ÀÎÏ
äëÿ ðåøåíèÿ ÇÖÔ íà óíèâåðñàëüíûõ ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ñèñòåìàõ è
óñòàíîâëåíû óñëîâèÿ, ïðè êîòîðûõ óñêîðåíèå ýòèõ àëãîðèòìîâ ðàâíî ñâîåìó
îïòèìàëüíîìó (èëè áëèçêîìó ê íåìó) çíà÷åíèþ.
Ïðåäëîæåííûå â ðàáîòå àëãîðèòìû ìîãóò áûòü ïðèìåíåíû íå òîëüêî äëÿ ðåøå-
íèÿ øèðîêîãî ñïåêòðà âû÷èñëèòåëüíûõ çàäà÷ (àíàëèç è îáðàáîòêà ïëîñêèõ è ïðî-
ñòðàíñòâåííûõ èçîáðàæåíèé, èññëåäîâàíèå n-ìåðíûõ îáúåêòîâ â íåêîòîðîì ôàçîâîì
ïðîñòðàíñòâå, îáðàáîòêà áîëüøèõ ìàññèâîâ ýêñïåðèìåíòàëüíûõ äàííûõ è ò.ä.), íî è
äëÿ èññëåäîâàíèÿ, ðàçðàáîòêè è ðåàëèçàöèè âû÷èñëèòåëüíûõ ñèñòåì, íàïðèìåð ñèñ-
òîëè÷åñêèõ, êâàçèñèñòîëè÷åñêèõ ñòðóêòóð è íåéðîííûõ ñåòåé [23]. Êîððåêòíîñòü
ïîñòðîåííûõ àëãîðèòìè÷åñêèõ êîíñòðóêöèé ïîäòâåðæäåíà ðåçóëüòàòàìè ìîäåëèðî-
âàíèÿ èõ ðàáîòû íà ÏÝÂÌ [34].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. ß ð î ñ ë à â ñ ê è é Ë . Ï . Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ â îïòèêå è ãîëîãðàôèè. Ââåäåíèå â öèô-
ðîâóþ îïòèêó. — Ì.: Ðàäèî è ñâÿçü, 1987. — 296 c.
2. Ç à ä è ð à ê à Â . Ê . , Ì å ë ü í è ê î â à Ñ . Ñ . Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ. — Ê.: Íàóê. äóìêà,
1993. — 294 ñ.
3. ß ö è ì ³ ð ñ ü ê è é Ì . Ì . Øâèäê³ àëãîðèòìè îðòîãîíàëüíèõ òðèãîíîìåòðè÷íèõ ïåðåòâîðåíü. —
Ëüâ³â: Àêàäåì³÷íèé Åêñïðåñ, 1997. — 219 ñ.
4. Ò è ì ÷ å í ê î Î .  . гçíèöåâ³ ìåòîäè öèôðîâî¿ ô³ëüòðàö³¿. — Ëüâ³â: Ôåí³êñ, 1999. — 388 ñ.
5. L a m p o r t L . The parallel execution of DO loops // Comm. ACM. — 1974. — 17, N 2. — P. 83–93.
6. Ï à ð à ë ë å ë ü í à ÿ îáðàáîòêà èíôîðìàöèè. Ïàðàëëåëüíûå ìåòîäû è ñðåäñòâà ðàñïîçíàâàíèÿ
îáðàçîâ / Ïîä ðåä. À.Í. Ñâåíñîíà. — Ê.: Íàóê. äóìêà, 1985. — Ò. 2. — 280 ñ.
7. Ë þ ë ÿ ê î â À .  . Ïîñòðîåíèå ïëîòíîãî ðàñïèñàíèÿ äëÿ êîíâåéåðíîé âû÷èñëèòåëüíîé ñèñòåìû ïðè
öèôðîâîé ôèëüòðàöèè ñèãíàëà // Òåîðåòè÷åñêèå ïðîáëåìû ñèñòåì îáðàáîòêè èíôîðìàöèè. —
Íîâîñèáèðñê: ÂÖ ÑÎ ÀÍ ÑÑÑÐ, 1986. — Ñ. 72–85.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4 13
8. Ì à ð õ ³ â ê à Â . Ñ . , ß ö è ì ³ ð ñ ü ê è é Ì . Ì . Ðîçïàðàëåëþâàííÿ ïðîãðàì øâèäêèõ îðòîãîíàëüíèõ
ïåðåòâîðåíü ó ìóëüòèïðîöåñîðíèõ ñèñòåìàõ // ³ñí. äåðæ. óí-òó «Ëüâ³âñüêà ïîë³òåõí³êà».
Êîìï’þòåðíà ³íæåíåð³ÿ òà ³íôîðìàö³éí³ òåõíîëî㳿. — 1998. — ¹ 349. — Ñ. 21–26.
9. À ë ã î ð è ò ì û , ìàòåìàòè÷åñêîå îáåñïå÷åíèå è àðõèòåêòóðà ìíîãîïðîöåññîðíûõ âû÷èñëèòåëüíûõ
ñèñòåì / Ïîä ðåä. À.Ï. Åðøîâà. — Ì.: Íàóêà, 1982. — 336 ñ.
10. K u n g H . T . , L e i s e r s o n C . E . Systolic arrays (for VLSI) // Proc. of the Symp. On Sparse Matrix
Comput., Knoxville, 1978. — Philadelphia: SIAM, 1979. — P. 256–282.
11. Ò è ù å í ê î Ò . Ï . Î öèôðîâîé ôèëüòðàöèè íà ñèñòîëè÷åñêèõ ñòðóêòóðàõ // Òåîðèÿ ïðîãðàììèðîâà-
íèÿ è ñðåäñòâà îïèñàíèÿ ïàðàëëåëèçìà äèñêðåòíûõ ñèñòåì. — Íîâîñèáèðñê: ÂÖ ÑÎ ÀÍ ÑÑÑÐ,
1985. — Ñ. 90–103.
12. Ê ó õ à ð å â à . À . , Ò ð î ï ÷ å í ê î À . Þ . , Ø ì å ð ê î  . Ï . Ñèñòîëè÷åñêèå ïðîöåññîðû äëÿ îáðà-
áîòêè ñèãíàëîâ. — Ìèíñê: Áåëàðóñü, 1988. — 127 ñ.
13. Ê à í å â ñ ê è é Þ . Ñ . Ñèñòîëè÷åñêèå ïðîöåññîðû. — Êèåâ: Òåõíèêà, 1991. — 173 ñ.
14. Ê î ñ ò þ í è í À . Í . Ïðèìåíåíèå ñèñòîëè÷åñêèõ ïðîöåññîðîâ äëÿ àäàïòèâíîé ôèëüòðàöèè ñèãíàëîâ
// ÓÑèÌ. — 1991. — ¹ 6. — Ñ. 32–35.
15. Ñ è ñ ò î ë è ÷ å ñ ê è é ïðîöåññîð ñâåðòêè / Ïîä ðåä. ß.À. Äóáðîâà. — Ëüâîâ, 1991. — 73 ñ. — (Ïðåïð.
/ ÍÒÖ «Èíòåãðàë»; ¹ 5-91).
16. È â à í î â Ñ . Ì . , Ò ð î ï ÷ å í ê î À . Þ . Êîíâåéåðíûå ðàçðÿäíî-ñðåçîâûå àëãîðèòìû ðàíãîâîé
ôèëüòðàöèè è èõ ðåàëèçàöèÿ íà ÏËÈÑ // Proc. of Fifth Intern. Conf. «Pattern Recognition and Informa-
tion Processing». — Minsk, 1999. — 2. — P. 239–243.
17. Ë ³ ñ ê å â è ÷ Î . ² . , Ë ³ ñ ê å â è ÷ Ð . ² . , ß ö è ì ³ ð ñ ü ê è é Ì . Ì . Àëãîðèòì³÷íèé ï³äõ³ä äî
ïîáóäîâè íåéðîííèõ ìåðåæ ë³í³éíî¿ ô³ëüòðàö³¿ ñèãíàë³â // Ïðàö³ ì³æíàð. êîíô. ç óïðàâë³ííÿ
ÀÂÒÎÌÀÒÈÊÀ–2000, Ëüâ³â, 11–15 âåðåñíÿ 2000 ð., ñåêö³ÿ 7. — 2000. — ×. 1. — Ñ. 318–323.
18. Ë è Ò . Òðåõìåðíàÿ ìèêðîýëåêòðîíèêà // Îòêðûòûå ñèñòåìû. — 2002. — ¹ 2 (http://
www.osp.ru/os/2002/02/022.htm).
19. ß ä æ à ê Ì . Ñ . Îïòèì³çàö³ÿ ñèñòîë³÷íèõ îá÷èñëåíü ïðè ðîçâ’ÿçàíí³ çàäà÷³ öèôðîâî¿ ô³ëüòðàö³¿ //
Òåîð³ÿ îá÷èñëåíü: Çá. íàóê. ïðàöü ²í-òó ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè. — Ê., 1999.
— Ñ. 386–390.
20. ß ä æ à ê Ì . Ñ . Äåÿê³ îá÷èñëþâàëüí³ çàñîáè ðåàë³çàö³¿ àëãîðèòì³â öèôðîâî¿ ô³ëüòðàö³¿ // Âîëèí. ìàò.
â³ñí. — 2002. — Âèï. 9. — Ñ. 90–99.
21. ß ä æ à ê Ì . Ñ . Äî ïèòàííÿ îðãàí³çàö³¿ ñèñòîë³÷íèõ îá÷èñëåíü ï³ä ÷àñ âèêîíàííÿ êàñêàäíî¿
öèôðîâî¿ ô³ëüòðàö³¿ // Òàì æå. Ñåð. ïðèêë. ìàòåìàòèêè. — 2003. — Âèï. 1(10). — Ñ. 153–160.
22. V a l ’ k o v s k i i V . A . An optimal algorithm for solving the problem of digital filtering // Pattern Recog-
nition and Image Analysis. — 1994. — 4, N 3. — P. 241–247.
23. Â à ë ü ê î â ñ ê è é Â . À . , ß ä æ à ê Ì . Ñ . Ìîäåëèðîâàíèå è ðåàëèçàöèÿ íåéðîííûõ ñåòåé íà
ìîäåëÿõ ïàðàëëåëüíîé îáðàáîòêè èíôîðìàöèè // Òð. ìåæäóíàð. êîíô. «Ìåòîäû è ñðåäñòâà
ïðåîáðàçîâàíèÿ è îáðàáîòêè àíàëîãîâîé èíôîðìàöèè», Óëüÿíîâñê (Ðîññèÿ), 8–10 èþíÿ 1999 ã. —
Óëüÿíîâñê: ÓëÃÒÓ, 1999. — 1. — Ñ. 53–55.
24.  à ë ü ê î â ñ ê è é  . À . , ß ä æ à ê Ì . Ñ . Îïòèìàëüíûé àëãîðèòì ðåøåíèÿ äâóìåðíîé çàäà÷è
öèôðîâîé ôèëüòðàöèè // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 1999. — ¹ 6. — Ñ. 92–102.
25. ß ä æ à ê Ì . Ñ . Îá îïòèìàëüíîì â îäíîì êëàññå àëãîðèòìå ðåøåíèÿ òð¸õìåðíîé çàäà÷è öèôðîâîé
ôèëüòðàöèè // Òàì æå. — 2000. — ¹ 6. — Ñ. 66–81.
26. ß ä æ à ê Ì . Ñ . Ïðî îïòèìàëüí³ñòü àëãîðèòìó ÷èñåëüíîãî ðîçâ’ÿçàííÿ óçàãàëüíåíî¿ çàäà÷³ öèôðîâî¿
ô³ëüòðàö³¿ // Âîëèí. ìàò. â³ñí. — 2000. — Âèï. 7. — Ñ. 181–192.
27. ß ä æ à ê Ì . Ñ . Ïðî ÷èñåëüíó ðåàë³çàö³þ êàñêàäíî¿ öèôðîâî¿ ô³ëüòðàö³¿ // ³ñí. Ëüâ³â. óí-òó. Ñåð.
ïðèêë. ìàòåìàòèêè òà ³íôîðìàòèêè. — 2000. — Âèï. 3. — Ñ. 75–79.
28. ß ä æ à ê Ì . Ñ . Î ÷èñëåííîì àëãîðèòìå ðåøåíèÿ ïðîñòðàíñòâåííîé çàäà÷è êàñêàäíîé öèôðîâîé
ôèëüòðàöèè // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2004. — ¹ 3. — Ñ. 107–120.
29. Âà ë ü ê î â ñ ü ê è é  . Î . , ß ä æ à ê Ì . Ñ . , Ï î ë º ò à º â Ñ . Ì . Äî ïèòàííÿ îïòèì³çàö³¿ êâà-
ç³ñèñòîë³÷íèõ îá÷èñëåíü ïðè ðîçâ’ÿçàíí³ çàäà÷³ öèôðîâî¿ ô³ëüòðàö³¿ // Êîìï’þòåðíà ìàòåìàòèêà.
Îïòèì³çàö³ÿ îá÷èñëåíü: Çá. íàóê. ïðàöü ²í-òó ê³áåðíåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè. — Ê.,
2001. — 1. — Ñ. 77–82.
30. ß ä æ à ê Ì . Ñ . Îðãàí³çàö³ÿ êâàç³ñèñòîë³÷íèõ îá÷èñëåíü ï³ä ÷àñ ðîçâ’ÿçóâàííÿ çàäà÷ öèôðîâî¿
ô³ëüòðàö³¿ // ³ñí. Ëüâ³â. óí-òó. Ñåð. ïðèêë. ìàòåìàòèêè òà ³íôîðìàòèêè. — 2002. — Âèï. 5. —
Ñ. 178–183.
31. ß ä æ à ê Ì . Ñ . Àëãîðèòìû ñ îãðàíè÷åííûì ïàðàëëåëèçìîì äëÿ ðåøåíèÿ îäíîé çàäà÷è öèôðîâîé
ôèëüòðàöèè // Ïðîáëåìû óïðàâëåíèÿ è èíôîðìàòèêè. — 2001. — ¹ 6. — Ñ. 109–118.
32. ß ä æ à ê Ì . Ñ . Î ïîñòðîåíèè àëãîðèòìîâ ñ îãðàíè÷åííûì ïàðàëëåëèçìîì äëÿ ðåøåíèÿ çàäà÷ öèô-
ðîâîé ôèëüòðàöèè // Òàì æå. — 2002. — ¹ 6. — Ñ. 92–103.
33. ßä æ à ê Ì . Ñ . Ðåàë³çàö³ÿ àëãîðèòì³â ç îáìåæåíèì ïàðàëåë³çìîì äëÿ ðîçâ’ÿçàííÿ çàäà÷³ öèôðîâî¿
ô³ëüòðàö³¿ // ³äá³ð ³ îáðîáêà ³íôîðìàö³¿. — 2006. — Âèï. 25(101). — Ñ. 103–108.
34. ß ä æ à ê Ì . Ñ . Ïðî ìîäåëþâàííÿ àëãîðèòì³â ç îáìåæåíèì ïàðàëåë³çìîì äëÿ ðîçâ’ÿçàííÿ çàäà÷
öèôðîâî¿ ô³ëüòðàö³¿ // Âîëèí. ìàò. â³ñí. — 2001. — Âèï. 8. — Ñ. 105–109.
Ïîñòóïèëà 10.01.2008
14 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2008, ¹ 4
|
| id | nasplib_isofts_kiev_ua-123456789-44192 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-24T16:13:03Z |
| publishDate | 2008 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Анисимов, А.В. Яджак, М.С. 2013-05-26T18:49:03Z 2013-05-26T18:49:03Z 2008 Построение оптимальных алгоритмов массовых вычислений в задачах цифровой фильтрации / А.В. Анисимов, М.С. Яджак // Кибернетика и системный анализ. — 2008. — № 4. — С. 3-14. — Бібліогр.: 34 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/44192 519.681.5 В работе предложен квазисистолический метод (КСМ) организации вычислений при решении задачи цифровой фильтрации произвольной размерности. Данный метод развит для решения одно-, дву-и трехмерной задачи многоразовой каскадцифровой фильтрации. На основании КСМ построены оптимальные по быстродействию параллельно-конвейерные алгоритмы, ориентированные на реализацию на специализированных вычислительных системах. 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/44192 |
| work_keys_str_mv | AT anisimovav postroenieoptimalʹnyhalgoritmovmassovyhvyčisleniivzadačahcifrovoifilʹtracii AT âdžakms postroenieoptimalʹnyhalgoritmovmassovyhvyčisleniivzadačahcifrovoifilʹtracii |