Алгоритмические модели обработки потоков данных
Рассмотрены свойства различных вычислительных моделей в виде графов потоков данных и предложены рекомендации по выбору модели, наиболее пригодной для проектирования конвейерных вычислителей....
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2008
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | http://dspace.nbuv.gov.ua/handle/123456789/101607 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Алгоритмические модели обработки потоков данных / В.П. Симоненко, А.М. Сергиенко // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 71-88. — Бібліогр.: 37 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-101607 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-1016072016-06-06T03:02:21Z Алгоритмические модели обработки потоков данных Симоненко, В.П. Сергиенко, А.М. Информационные технологии, защита информации Рассмотрены свойства различных вычислительных моделей в виде графов потоков данных и предложены рекомендации по выбору модели, наиболее пригодной для проектирования конвейерных вычислителей. Розглянуто властивості різних обчислювальних моделей у вигляді графів потоків даних і запропоновано рекомендації щодо вибору моделі, найбільш придатної для проектування конвейерних обчислювачів. Properties of various computational models and recommendations are proposed for the selection of such a model which is fitted for the pipeline computer designing. 2008 Article Алгоритмические модели обработки потоков данных / В.П. Симоненко, А.М. Сергиенко // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 71-88. — Бібліогр.: 37 назв. — рос. 0204-3572 http://dspace.nbuv.gov.ua/handle/123456789/101607 681.3 ru Электронное моделирование Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Информационные технологии, защита информации Информационные технологии, защита информации |
| spellingShingle |
Информационные технологии, защита информации Информационные технологии, защита информации Симоненко, В.П. Сергиенко, А.М. Алгоритмические модели обработки потоков данных Электронное моделирование |
| description |
Рассмотрены свойства различных вычислительных моделей в виде графов потоков данных и предложены рекомендации по выбору модели, наиболее пригодной для проектирования конвейерных вычислителей. |
| format |
Article |
| author |
Симоненко, В.П. Сергиенко, А.М. |
| author_facet |
Симоненко, В.П. Сергиенко, А.М. |
| author_sort |
Симоненко, В.П. |
| title |
Алгоритмические модели обработки потоков данных |
| title_short |
Алгоритмические модели обработки потоков данных |
| title_full |
Алгоритмические модели обработки потоков данных |
| title_fullStr |
Алгоритмические модели обработки потоков данных |
| title_full_unstemmed |
Алгоритмические модели обработки потоков данных |
| title_sort |
алгоритмические модели обработки потоков данных |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| publishDate |
2008 |
| topic_facet |
Информационные технологии, защита информации |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/101607 |
| citation_txt |
Алгоритмические модели обработки потоков данных / В.П. Симоненко, А.М. Сергиенко // Электронное моделирование. — 2008. — Т. 30, № 6. — С. 71-88. — Бібліогр.: 37 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT simonenkovp algoritmičeskiemodeliobrabotkipotokovdannyh AT sergienkoam algoritmičeskiemodeliobrabotkipotokovdannyh |
| first_indexed |
2025-07-07T11:09:19Z |
| last_indexed |
2025-07-07T11:09:19Z |
| _version_ |
1836986202054459392 |
| fulltext |
ÓÄÊ 681.3
Â. Ï. Ñèìîíåíêî, ä-ð òåõí. íàóê,
À. Ì. Ñåðãèåíêî, êàíä. òåõí. íàóê
Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò Óêðàèíû «ÊÏÈ»
(Óêðàèíà, 03056, Êèåâ, ïð. Ïîáåäû, 37,
òåë.: 4549337, E-mail: aser@comsys.ntu-kpi.kiev.ua)
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
Ðàññìîòðåíû ñâîéñòâà ðàçëè÷íûõ âû÷èñëèòåëüíûõ ìîäåëåé â âèäå ãðàôîâ ïîòîêîâ äàí-
íûõ è ïðåäëîæåíû ðåêîìåíäàöèè ïî âûáîðó ìîäåëè, íàèáîëåå ïðèãîäíîé äëÿ ïðîåêòè-
ðîâàíèÿ êîíâåéåðíûõ âû÷èñëèòåëåé.
Ðîçãëÿíóòî âëàñòèâîñò³ ð³çíèõ îá÷èñëþâàëüíèõ ìîäåëåé ó âèãëÿä³ ãðàô³â ïîòîê³â äàíèõ ³
çàïðîïîíîâàíî ðåêîìåíäàö³¿ ùîäî âèáîðó ìîäåë³, íàéá³ëüø ïðèäàòíî¿ äëÿ ïðîåêòóâàííÿ
êîíâåéåðíèõ îá÷èñëþâà÷³â.
Ê ë þ ÷ å â û å ñ ë î â à: ãðàô ïîòîêîâ äàííûõ, îòîáðàæåíèå àëãîðèòìà, âû÷èñëèòåëüíàÿ
ñèñòåìà.
Ïî îáùåïðèíÿòîìó îïðåäåëåíèþ, àëãîðèòì — ýòî âû÷èñëèòåëüíûé ïðîöåññ,
èìåþùèé íà÷àëî, äåòåðìèíèðîâàííóþ ïîñëåäîâàòåëüíîñòü äåéñòâèé è êîíåö
è äàþùèé îæèäàåìûå ðåçóëüòàòû ïðè ðàçëè÷íûõ èñõîäíûõ äàííûõ [1]. Ýòî
îïðåäåëåíèå îòíîñèòñÿ ê òðàíñôîðìèðóþùèì âû÷èñëèòåëüíûì ñèñòåìàì
(ÂÑ), íå èìåþùèì îãðàíè÷åíèÿ íà áûñòðîäåéñòâèå. ÂÑ ðåàëüíîãî âðåìå-
íè îòëè÷àþòñÿ òåì, ÷òî ïåðèîäû âûïîëíåíèÿ àëãîðèòìîâ â íèõ íå
ïðåâîñõîäÿò çàäàííûõ âðåìåííûõ îãðàíè÷åíèé. Òàêèå ÂÑ ðàçäåëÿþò íà
èíòåðàêòèâíûå, åñëè îíè ðåàãèðóþò íà âõîäíûå äàííûå ñ ñîòâåòñòâóþùåé
èì ñêîðîñòüþ, è ðåàêòèâíûå, êîòîðûå íå äîïóñêàþò ïîòåðè ýòèõ äàííûõ
âñëåäñòâèå íåäîñòàòî÷íîãî áûñòðîäåéñòâèÿ [2,3]. Ïåðñîíàëüíûå êîìïüþ-
òåðû, óñòðîéñòâà ìîáèëüíîé ñâÿçè è ñðåäñòâà öèôðîâîé îáðàáîòêè ñèã-
íàëîâ (ÖÎÑ) îòíîñÿòñÿ ê ÂÑ ðåàëüíîãî âðåìåíè. Îíè è ìíîãèå äðóãèå ÂÑ
âûïîëíÿþò ïåðèîäè÷åñêèå àëãîðèòìû, îáðàáàòûâàþùèå ïîòîêè äàííûõ è
(èëè) êîìàíä.
Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ îñíîâàíà íà òîì, ñèãíàëû îáðàáàòû-
âàþòñÿ êàê ïîòîêè äàííûõ. Ïîýòîìó îáëàñòü ÖÎÑ íàèáîëåå äîñòîâåðíî
îòîáðàæàåò çàäà÷è, àëãîðèòìû è ÂÑ, â êîòîðûõ íàáëþäàþòñÿ òàêèå ïîòî-
êè. Íà ñîâðåìåííîì ýòàïå ðàçâèòèÿ ÖÎÑ àëãîðèòìû, îáåñïå÷èâàþùèå áåñ-
ïðîâîäíóþ ñâÿçü, êîìïðåññèþ èçîáðàæåíèé, ìîäåëèðîâàíèå òðåõìåðíûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 71
������� ����
��
����������
����
��������� ��
ñöåí, íå ìîãóò áûòü ðåàëèçîâàíû íà ïðîöåññîðå ïåðñîíàëüíîãî êîìïüþòåðà â
ðåàëüíîì âðåìåíè. Äëÿ èõ ðåàëèçàöèè íåîáõîäèìî èñïîëüçîâàòü ñïåöèàëü-
íûå ÂÑ íà îñíîâå çàêàçíûõ ñâåðõáîëüøèõ èíòåãðàëüíûõ ñõåì (ÑÁÈÑ),
ìíîãîïðîöåññîðíûõ ñèãíàëüíûõ ìèêðîïðîöåññîðîâ, à òàêæå ïðîãðàìèðóå-
ìûå ëîãè÷åñêèå èíòåãðàëüíûå ñõåìû (ÏËÈÑ). Íà ñîâðåìåííîì ýòàïå ðàçâè-
òèÿ ÖÎÑ ïðîãðàììèñò, ðàçðàáîòàâøèé íîâûé àëãîðèòì ÖÎÑ, èìååò âîçìîæ-
íîñòü íåìåäëåííî âíåäðèòü åãî, íî ýòîãî íå ïðîèçîéäåò, åñëè îí íå âëàäååò â
ñîâåðøåíñòâå ïàðàëëåëüíûì ïðîãðàììèðîâàíèåì [4].
Äëÿ äîñòèæåíèÿ âûñîêîé ïðîèçâîäèòåëüíîñòè ÂÑ íåîáõîäèìî ïðî-
ãðàììèðîâàíèå ìíîãîïðîöåññîðíûõ ïàðàëëåëüíûõ ñèñòåì. Îäíàêî ïðè
íàëè÷èè áîëåå ÷åòûðåõ ïðîöåññîðîâ èõ ïðîãðàììèðîâàíèå (ó÷èòûâàÿ ñîâ-
ðåìåííîå ñîñòîÿíèå òåõíîëîãèè ðàçðàáîòêè ïðîãðàìì) ïðåäñòàâëÿåò ñîáîé
âåñüìà òðóäîåìêóþ ðàáîòó. Â íàñòîÿùåå âðåìÿ øèðîêî ïðèìåíÿåòñÿ ïàðà-
äèãìà ìíîãîïîòîêîâîé îáðàáîòêè, ïîääåðæèâàåìàÿ êàê íà óðîâíå ìàòîáåñïå-
÷åíèÿ, òàê è íà àïïàðàòíîì óðîâíå ñîâðåìåííûõ êîìïüþòåðîâ. Íî, êàê ïîêà-
çàíî, íàïðèìåð, â [5], ìíîãîïîòîêîâàÿ âû÷èñëèòåëüíàÿ ìîäåëü íå ãàðàíòè-
ðîâàíà îò áëîêèðîâîê, è ïðè ïåðåõîäå ê ìíîãîÿäåðíûì ìèêðîïðîöåññîðàì
âåðîÿòíîñòü áëîêèðîâîê âîçðàñòàåò. Ïîýòîìó íåîáõîäèìî èñïîëüçîâàíèå
äðóãèõ ïàðàäèãì ðåøåíèÿ çàäà÷ îáðàáîòêè ïîòîêîâ äàííûõ.
Íîâûå çàäà÷è, âîçíèêàþùèå â îáëàñòè ðàçâèòèÿ ÖÎÑ, íå ìîãóò áûòü
ðåøåíû áåç ðàçðàáîòêè ìåòîäîâ è ñðåäñòâ îòîáðàæåíèÿ àëãîðèòìîâ â
ÑÁÈÑ è ÏËÈÑ, ïðîãðàììèðîâàíèÿ ìíîãîïðîöåññîðíûõ ÂÑ. Òàêàÿ ðàçðà-
áîòêà âîçìîæíà, ïðåæäå âñåãî, ïðè óñëîâèè íîâîãî âèäåíèÿ ïðèðîäû
àëãîðèòìîâ îáðàáîòêè ïîòîêîâ äàííûõ. Ê ñîæàëåíèþ, â îòå÷åñòâåííîé
ëèòåðàòóðå íå îïóáëèêîâàíî ñèñòåìàòè÷åñêîé èíôîðìàöèè îá àëãîðèòìè-
÷åñêèõ ìîäåëÿõ îáðàáîòêè ïîòîêîâ äàííûõ è îá èõ ïðèìåíåíèè â ïðàêòèêå
ïðîãðàììèðîâàíèÿ è ñèíòåçà ïàðàëëåëüíûõ ÂÑ. Ïðåäëàãàåìûé îáçîð ñó-
ùåñòâóþùèõ ìîäåëåé ïîñòðîåíèÿ ïåðèîäè÷åñêèõ àëãîðèòìîâ îáðàáîòêè ïî-
òîêîâ äàííûõ îòîáðàæàåò ñîñòîÿíèå íàó÷íîé ìûñëè â ýòîé îáëàñòè.
Àëãîðèòì è âû÷èñëèòåëüíàÿ ìîäåëü. Ïî îïðåäåëåíèþ Ïîñòà è
Òüþðèíãà, àëãîðèòì — ýòî âû÷èñëèòåëüíûé ïðîöåññ, âûïîëíÿåìûé íåêî-
òîðîé ìîäåëüþ âû÷èñëèòåëÿ, êîòîðàÿ ñêîíñòðóèðîâàíà â ðàìêàõ òî÷íûõ
ìàòåìàòè÷åñêèõ ïîíÿòèé [6]. Òàêîå îïðåäåëåíèå àëãîðèòìà äàåò âîçìîæ-
íîñòü, âî-ïåðâûõ, êëàññèôèöèðîâàòü àëãîðèòìû ïî òèïó ìîäåëè âû÷èñëè-
òåëÿ, âî-âòîðûõ, ñðàâíèâàòü ìåæäó ñîáîé ðàçëè÷íûå àëãîðèòìû ïóòåì èõ
ýêâèâàëåíòíîãî ïðåîáðàçîâàíèÿ â àëãîðèòìû, çàäàííûå íà ñòàíäàðòíîé
ìîäåëè âû÷èñëèòåëÿ, òàêîé êàê ìàøèíà Òüþðèíãà, â-òðåòüèõ, êîíñòðóèðî-
âàòü ìîäåëè âû÷èñëèòåëåé, íàèáîëåå ïðèãîäíûå äëÿ ýôôåêòèâíîãî çàäà-
íèÿ òîãî èëè èíîãî êëàññà àëãîðèòìîâ.
Îïðåäåëåíèå àëãîðèòìà, ïðèâåäåííîå â íà÷àëå ñòàòüè îòíîñèòñÿ,
ïðåæäå âñåãî, ê íåéìàíîâñêîé ìîäåëè âû÷èñëèòåëÿ, êîòîðàÿ ïîñëåäîâà-
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
72 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
òåëüíî âûïîëíÿåò â ñòðîãîì ïîðÿäêå êîìàíäû, èçìåíÿþùèå ñîñòîÿíèå
ïàìÿòè âû÷èñëèòåëÿ îò íà÷àëüíîãî äî êîíå÷íîãî. Íà òàêîé ìîäåëè âûïîë-
íÿþòñÿ îïåðàòîðíûå, èìïåðàòèâíûå àëãîðèòìû.
 ôóíêöèîíàëüíûõ àëãîðèòìàõ âû÷èñëåíèÿ ïðåäñòàâëÿþò ñîáîé ìíî-
æåñòâî òîæäåñòâ ôóíêöèé. Ïðè ýòîì ðåçóëüòàòû ôóíêöèé âû÷èñëÿþòñÿ
òîëüêî òîãäà, êîãäà äëÿ íèõ ñóùåñòâóþò ñîòâåòñòâóþùèå âõîäíûå äàí-
íûå.  ôóíêöèîíàëüíîì àëãîðèòìå íåò îãðàíè÷åíèé íà ïîðÿäîê âû÷èñ-
ëåíèÿ ôóíêöèé êðîìå ïîðÿäêà, çàäàííîãî çàâèñèìîñòÿìè ïî äàííûì èëè
óïðàâëåíèþ.
Ìîäåëü âû÷èñëèòåëÿ, ðåàëèçóþùóþ ôóíêöèîíàëüíûé àëãîðèòì, ïðè-
íÿòî ïðåäñòàâëÿòü â âèäå ãðàôà.  òàêîé ìîäåëè âåðøèíû ãðàôà îçíà÷àþò
ôóíêöèè èëè îïåðàòîðû, èëè ëîêàëüíûå ïðîöåññû àëãîðèòìà, à äóãè —
êàíàëû ïåðåäà÷è äàííûõ, çàâèñèìîñòè ïî äàííûì è óïðàâëåíèþ. Ðåàëèçàöèÿ
àëãîðèòìà íà òàêîé ìîäåëè ïðåäñòàâëÿåò ñîáîé ïåðåäà÷ó äàííûõ â íàïðàâ-
ëåíèè äóã è îáõîä âåðøèí â ñîòâåòñòâèè ñ èõ èíöèäåíòíîñòüþ, íàëè÷èåì
äàííûõ íà èõ âõîäàõ èëè ïî äðóãèì ïðàâèëàì.  îòëè÷èå îò èìïåðàòèâíûõ
àëãîðèòìîâ çäåñü ïîðÿäîê âûïîëíåíèÿ îïåðàòîðîâ íåñòðîãèé, à ïàðàëëåëèçì
àëãîðèòìà çàäàí ÿâíûì îáðàçîì.
Ðàññìîòðèì íåñêîëüêî èçâåñòíûõ ãðàôîâûõ ìîäåëåé ôóíêöèîíàëüíûõ
àëãîðèòìîâ è èõ îñíîâíûå ñâîéñòâà.
Ñåòü Ïåòðè — íàèáîëåå èçâåñòíàÿ ãðàôîâàÿ ìîäåëü âû÷èñëåíèé.
Ãðàô ýòîé ñåòè ñîñòîèò èç âåðøèí-ïîçèöèé è âåðøèí-ïåðåõîäîâ, ïîïàðíî
ñâÿçàííûõ äóãàìè. Âûïîëíåíèå àëãîðèòìà â ýòîé ìîäåëè îñóùåñòâëÿåòñÿ
ñ ïîìîùüþ ìåòîê â âåðøèíàõ-ïîçèöèÿõ, êîòîðûå àñîöèèðóþòñÿ ñ äàíûìè.
Åñëè ìåòîê íà âõîäàõ âåðøèíû-ïåðåõîäà äîñòàòî÷íî, òî îíà ñðàáàòûâàåò è
ñîòâåòñòâóþùàÿ ìåòêà ïîÿâëÿåòñÿ íà åå âûõîäàõ. Âûïîëíåíèå àëãîðèòìà
ñîñòîèò èç ñåðèè ñðàáàòûâàíèé ïåðåõîäîâ â ïðîèçâîëüíîì ïîðÿäêå, ïîêà
íå îñòàíåòñÿ óñëîâèé äëÿ òàêèõ ñîáûòèé [7].
Ñåòè Ïåòðè èñïîëüçóþòñÿ, ïðåæäå âñåãî, äëÿ ìîäåëèðîâàíèÿ ðàáîòû
àñèíõðîííûõ ñèñòåì, íàïðèìåð ïðîòîêîëîâ îáìåíà äàííûìè [8]. Ñóùåñò-
âóåò äîñòàòî÷íîå ÷èñëî ðàáîò [9—12], ïîñâÿùåííûõ ïðèìåíåíèþ ýòèõ
ñåòåé â ïðîåêòèðîâàíèè âû÷èñëèòåëüíîé àïïàðàòóðû, íî îíè íå ïîëó÷èëè
øèðîêîãî ðàñïðîñòðàíåíèÿ. Îñíîâíîé ïðè÷èíîé ýòîãî ÿâëÿåòñÿ ñëîæíîñòü
àíàëèçà ñåòè Ïåòðè, îïðåäåëåíèÿ åå áåçîïàñíîñòè, îòñóòñòâèÿ áëîêèðîâîê.
Ãðàô ïîòîêîâ äàííûõ (ÃÏÄ) — íàïðàâëåííûé ãðàô, âåðøèíû êîòî-
ðîãî — àêòîðû — ïðåäñòàâëÿþò îïåðàöèè, à äóãè — êàíàëû ïåðåäà÷è
äàííûõ. Àêòîðû èñïîëüçóþò äàííûå ñî ñâîèõ âõîäîâ, íàçûâàåìûå ìåòêà-
ìè èëè òîêåíàìè, è âûäàþò ìåòêè íà ñâîè âûõîäû. ÃÏÄ, ïðåäëîæåííûé
Äåííèñîì, ïðåäñòàâëÿåò ñîáîé ìîäåëü, â êîòîðîé âû÷èñëåíèÿ îïðåäå-
ëÿþòñÿ íàëè÷èåì äàííûõ íà èíôîðìàöèîííûõ è óïðàâëÿþùèõ äóãàõ [13].
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 73
 îòëè÷èå îò íåéìàíîâñêîãî ïðîöåññîðà, â êîòîðîì âû÷èñëåíèÿ óïðàâ-
ëÿþòñÿ ïîòîêîì êîìàíä, çàäàâàåìûì ñ÷åò÷èêîì êîìàíä, â êîìïüþòåðå
ïîòîêîâ äàííûõ, ïðåäëîæåííîì Äåííèñîì, óïðàâëåíèå ñâîäèòñÿ ê ñëåæå-
íèþ çà íàëè÷èåì ãîòîâûõ äàííûõ è íàïðàâëåíèþ èõ íà âõîäû àêòîðîâ.
Ãðàô Êàðïà è Ìèëëåðà (ãðàô âû÷èñëåíèé) — îäèí èç ïåðâûõ ÃÏÄ äëÿ
çàäàíèÿ àëãîðèòìîâ îáðàáîòêè ïîòîêîâ äàííûõ [13]. Â íåì k-é äóãå,
ïðåäñòàâëÿþùåé î÷åðåäü, ïðèñâîåíî ÷èñëî ìåòîê â íà÷àëå âû÷èñëåíèé,
÷èñëî ìåòîê, âõîäÿùèõ â î÷åðåäü ïðè âûïîëíåíèè îïåðàòîðà, ÷èñëî ìåòîê
Wk, âûõîäÿùèõ èç î÷åðåäè ïðè âûïîëíåíèè àêòîðà, è ìèíèìàëüíàÿ äëèíà
î÷åðåäè Òk, íåîáõîäèìàÿ äëÿ çàïóñêà àêòîðà. Ïðè âûïîëíåíèè âû÷èñëè-
òåëüíîãî ïðîöåññà àêòîðû çàïóñêàþòñÿ, åñëè Wk � Òk, è èç ïîòîêîâ ÷è-
òàþòñÿ Wk ìåòîê. Ìåæäó ãðàôîì Êàðïà è Ìèëëåðà è ñåòüþ Ïåòðè ìîæåò
áûòü âçàèìíî-îäíîçíà÷íàÿ ñâÿçü — î÷åðåäè äàííûõ ñîîòâåòñòâóþò âåð-
øèíàì-ïîçèöèÿì, à àêòîðû — âåðøèíàì-ïåðåõîäàì [14].
Ñåòü ïðîöåññîâ Êàíà — âû÷èñëèòåëüíàÿ ìîäåëü, â êîòîðîé àñèíõðîí-
íûå ïðîöåññû âçàèìîäåéñòâóþò ìåæäó ñîáîé ÷åðåç ïîñëåäîâàòåëüíûå
áóôåðû äàííûõ, íàçûâàåìûå ïîòîêàìè. Ýòè ïîòîêè ïîä÷èíÿþòñÿ äèñ-
öèïëèíå: ïåðâûé âîøåë â áóôåð —ïåðâûé âûøåë, ò.å. FIFO [13, 15]. Â ýòîé
ìîäåëè âåðøèíà ïðîöåññà ìîæåò âûïîëíÿòü ââîä äàííûõ â ïðîèçâîëüíîì
ïîðÿäêå. Íî ïîñëå ñ÷èòûâàíèÿ äàííîãî ïðîöåññ áëîêèðóåòñÿ, ïîêà íå
ïîñòóïèò íîâîå äàííîå, ò.å. ïðîöåññ çàïóñêàåòñÿ ïî îïåðàòîðó wait on data,
à ñàìî äàííîå óäàëÿåòñÿ èç áóôåðà.  îáùåì ñëó÷àå, åñëè ãëóáèíà áóôåðîâ
FIFO îãðàíè÷åíà, ýòà ñåòü ìîæåò áûòü çàáëîêèðîâàíà, ïðè÷åì íåâîçìîæíî
îïðåäåëèòü çàðàíåå, ñîâåðøèòñÿ ëè òàêàÿ áëîêèðîâêà. Ïîýòîìó êîððåêò-
íîå âûïîëíåíèå àëãîðèòìà ìîæåò áûòü ãàðàíòèðîâàíî ëèøü ïðè äèíàìè-
÷åñêîì ñîñòàâëåíèè ðàñïèñàíèÿ è ïîòåíöèàëüíî íåîãðàíè÷åííîé ãëóáèíå
áóôåðà FIFO.
 îòëè÷èå îò ñåòè Ïåòðè â ñåòè ïðîöåññîâ Êàíà ñîñòîÿíèå äàííûõ â
ïîòîêàõ íå çàâèñèò îò ðàñïèñàíèÿ âûïîëíåíèÿ ïðîöåññîâ, ò.å. ïîòîêè
äàííûõ â ìîäåëè äåòåðìèíèðîâàííûå [13]. Ýòà ñåòü ÿâèëàñü ñòèìóëîì äëÿ
ïîÿâëåíèÿ ìíîãèõ äðóãèõ ìîäåëåé îáðàáîòêè ïîòîêîâ äàííûõ. Ïîäðîá-
íûé îáçîð ìîäåëåé ïîòîêîâ äàííûõ è áèáëèîãðàôè÷åñêèå èñòî÷íèêè,
ïîñâÿùåííûå èçó÷åíèþ ñâîéñòâ ýòèõ ìîäåëåé, ïðèâåäåíû â [13, 15]. Äëÿ
êëàññèôèêàöèè ìîäåëåé ïîòîêîâ äàííûõ ðàññìîòðèì îïðåäåëåíèå ïîòîêà
äàííûõ è åãî ïàðàìåòðû.
Êëàññèôèêàöèÿ ìîäåëåé îáðàáîòêè ïîòîêîâ äàííûõ ïî òèïó ïîòî-
êà äàííûõ. Âñå ìîäåëè âû÷èñëèòåëåé ïîòîêîâ äàííûõ èìåþò îáùóþ
îñîáåííîñòü, ñîñòîÿùóþ â òîì, ÷òî èõ êîìïîíåíòû — óçëû, îïåðàòîðû,
àêòîðû èëè ïðîöåññû — ñîåäèíåíû ìåæäó ñîáîé ïîòîêàìè äàííûõ. Ïîòîê
äàííûõ — ýòî ñðåäñòâî ïåðåäà÷è êîíå÷íîãî èëè, â ïðåäåëüíîì ñëó÷àå,
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
74 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
áåñêîíå÷íîãî êîëè÷åñòâà óïîðÿäî÷åííûõ äàííûõ ìåæäó êîìïîíåíòàìè
âû÷èñëèòåëüíîé ìîäåëè. Äàííûå â ïîòîêå, óïîðÿäî÷åííûå ïî íîìåðàì
àññîöèèðîâàííûõ ñ íèìè òåãîâ, íàïðèìåð âðåìåííûõ ìåòîê, ïðèíÿòî íà-
çûâàòü ñèãíàëîì.
Âû÷èñëèòåëüíûå ìîäåëè ðàçëè÷àþòñÿ ìåæäó ñîáîé ñïîñîáîì âûïîë-
íåíèÿ ïîòîêîâ äàííûõ, êîòîðûé çàâèñèò îò îïðåäåëåííûõ ñâîéñòâ èëè
ïðèçíàêîâ ïîòîêà, ò.å. îò ñëåäóþùèõ àëüòåðíàòèâ:
ïîòîê îäíîíàïðàâëåííûé èëè äâóíàïðàâëåííûé;
ó ïîòîêà îäèí èñòî÷íèê äàííûõ èëè èõ íåñêîëüêî;
ñ ïîòîêà ñ÷èòûâàåò äàííûå îäèí ïðîöåññ èëè íåñêîëüêî ïðîöåññîâ;
êàê â ïîòîêå äàííûå ðàçëè÷àþòñÿ ïî âðåìåíè âîçíèêíîâåíèÿ, èñïîëü-
çîâàíèÿ;
êàê â ïîòîêå äàííûå ðàçëè÷àþòñÿ ìåæäó ñîáîé ïîðÿäêîì (íàïðèìåð, â
áóôåðå FIFO);
ðàçðåøåíî ëè â ïîòîêå äàííûå äóáëèðîâàòü èëè ïåðåçàïèñûâàòü;
ðàçðåøåíà ëè ïðîâåðêà íàëè÷èÿ äàííûõ â ïîòîêå;
ðàññìàòðèâàåòñÿ â ìîäåëè âðåìÿ êàê áåñïðåðûâíàÿ ñóùíîñòü, êîãäà
ñèãíàë åñòü ôóíêöèÿ îò âðåìåíè, èëè êàê äèñêðåòíûå ñîáûòèÿ, êîãäà
îòñ÷åò ñèãíàëà ïðåäñòàâëåí ïàðîé ìîìåíò âðåìåíè (íîìåð òàêòà) —
çíà÷åíèå, èëè ïðîöåññû âîîáùå ðàçâèâàþòñÿ áåçîòíîñèòåëüíî âðåìåíè,
êîãäà ñèãíàë — ýòî óïîðÿäî÷åííîå ìíîæåñòâî îòñ÷åòîâ;
ðàâíî ëè êîëè÷åñòâî ïåðåäàííûõ äàííûõ â ïîòîê çà îïðåäåëåííûé
ïðîìåæóòîê âðåìåíè êîëè÷åñòâó èñïîëüçîâàííûõ äàííûõ èëè ýòî êîëè-
÷åñòâî èçìåíÿåòñÿ äèíàìè÷åñêè;
îáðàùàþòñÿ ëè îäíîâðåìåííî ê ïîòîêó èñòî÷íèê è ïðèåìíèê äàí-
íîãî [15].
Ñèíõðîííûå è àñèíõðîííûå ìîäåëè. Òðè ïîñëåäíèõ ñâîéñòâà ïîòî-
êà äàííûõ, ïðèâåäåííûõ âûøå, õàðàêòåðèçóþò åãî ñóùåñòâîâàíèå âî âðå-
ìåíè. Ðàçëè÷àþò ñèíõðîííûå è àñèíõðîííûå ïîòîêè è ñîòâåòñòâåííî ñèí-
õðîííûå è àñèíõðîííûå ìîäåëè âû÷èñëåíèé.  àñèíõðîííîì ïîòîêå
ìîìåíò ïåðåäà÷è äàííîãî ïðîèçâîëüíûé è ïîòîê äîïóñêàåò ïðîèçâîëüíóþ
çàäåðæêó ìåæäó çàãðóçêîé äàííîãî â íåãî è åãî èñïîëüçîâàíèåì. Ýòî äàåò
âîçìîæíîñòü ëþáûì ñïîñîáîì âûáèðàòü ìîìåíòû çàãðóçêè è èñïîëüçî-
âàíèÿ äàííûõ èëè ñðàáàòûâàíèÿ ñîòâåòñòâóþùèõ àêòîðîâ ïðè ñîñòàâëå-
íèè ðàñïèñàíèÿ âûïîëíåíèÿ àëãîðèòìà. Ïðè ýòîì êîëè÷åñòâî äàííûõ â
ïîòîêå â êàæäûé ìîìåíò âðåìåíè ìîæåò áûòü ïðîèçâîëüíûì.
 ñèíõðîííîì ïîòîêå ìîìåíò ïåðåäà÷è äàííîãî èëè ãðóïïû äàííûõ
ñâÿçàí ñ íåêîòîðûì ñîáûòèåì, íàïðèìåð ñèãíàëîì ñèíõðîñåðèè, ò.å. ýòîò
ìîìåíò ìîæåò îïðåäåëÿòüñÿ äèñêðåòíî. Åñëè òàêîé ïîòîê íå èìååò áóôåð-
íîé ïàìÿòè, òî çàãðóæåííîå â íåãî äàííîå äîëæíî áûòü èñïîëüçîâàíî
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 75
ñðàçó èëè ñ çàäåðæêîé, íå ïðåâîñõîäÿùåé ïàðàìåòð ñèíõðîñèãíàëà. Ìåòêè
ïîòîêîâ äàííûõ ìîãóò èìåòü âðåìåííûå òåãè èõ âîçíèêíîâåíèÿ, â ñîò-
âåòñòâèè ñ êîòîðûìè îíè ÿâëÿþòñÿ ãëîáàëüíî èëè ëîêàëüíî óïîðÿäî-
÷åííûìè. Ìåòêè èëè ñèãíàëû ñ÷èòàþòñÿ ñèíõðîííûìè, åñëè îíè èìåþò
òåãè ñî âçàèìíî-îäíîçíà÷íûì ñîîòâåòñòâèåì. Ìîäåëü ñ÷èòàåòñÿ ñèíõðîí-
íîé, åñëè âñå ñèãíàëû â íåé — ñèíõðîííûå. Äàæå áåç íàëè÷èÿ ÿâíîé
ñèíõðîíèçàöèè â ñèíõðîííîé ìîäåëè àêòîðû ìîãóò èñïîëüçîâàòü ìåòêè â
ñîòâåòñòâèè ñ âîçðàñòàþùèì ïîðÿäêîì èõ âðåìåííûõ òåãîâ [15].
Ñèíõðîíèçì ïîòîêà ìîæåò îñóùåñòâëÿòüñÿ ñ ïîìîùüþ ëîãè÷åñêèõ
óñëîâèé, íàïðèìåð óñëîâèÿ ôðîíòà ñèãíàëà ñèíõðîñåðèè (ýòî îñîáåííûé
ñëó÷àé àñèíõðîííîãî ïîòîêà). Àíàëèç ìîäåëåé ñ ñèíõðîííûìè ïîòîêàìè è
ñîñòàâëåíèå äëÿ íèõ ðàñïèñàíèÿ ñóùåñòâåííî óïðîùàþòñÿ ïî ñðàâíåíèþ ñ
äðóãèìè ìîäåëÿìè.
Ìîäåëè ñ ñèíõðîíèçàöèåé îáðàùåíèé ê ïîòîêó ðàçäåëÿþòñÿ íà ìî-
äåëè ñ ñèíõðîíèçàöèåé ïî ñèíõðîñåðèè è ìîäåëè ñ ðàíäåâó. Â ïîñëåäíèõ
èñòî÷íèê è ïðèåìíèê îáðàùàþòñÿ ê ïîòîêó îäíîâðåìåííî ÷åðåç ìåõàíèçì
ñèíõðîíèçàöèè ñ êâèòèðîâàíèåì. ßçûêè ñèíõðîííîãî ïðîãðàìèðîâàíèÿ,
òàêèå êàê Esterel, Lustre, Signal, îñíîâàíû íà ñèíõðîíèçàöèè ïî ñèíõðî-
ñåðèè, à ÿçûê Communicating Sequential Processes (CSP) è ïðîèçâîäíûé îò
íåãî ÿçûê Occam — íà ñèíõðîíèçàöèè ñ êâèòèðîâàíèåì.
 ìîäåëÿõ ñ íåñêîëüêèìè èñòî÷íèêàìè è ïðèåìíèêàìè äàííûõ äëÿ ñîã-
ëàñîâàííîñòè äîñòóïà ê ðàçäåëÿåìîé ïåðåìåííîé ÷àùå âñåãî èñïîëüçóåòñÿ
ñòðàòåãèÿ ÷òåíèÿ — ìîäèôèêàöèè — çàïèñè, â ñîòâåòñòâèè ñ êîòîðîé çàïðå-
ùàåòñÿ äîñòóï ê ïåðåìåííîé îò äðóãèõ àêòîðîâ, åñëè îäèí èç àêòîðîâ âûïîë-
íÿåò ÷òåíèå ïåðåìåííîé èç ïîòîêà ñ ïîñëåäóþùåé çàïèñüþ â ïîòîê. Åñëè ýòà
èëè àíàëîãè÷íàÿ ñòðàòåãèÿ íå èñïîëüçóåòñÿ, òî ïðîèñõîäèò íåñèíõðîíèçè-
ðîâàííàÿ ïåðåäà÷à äàííûõ. Òàêàÿ ïåðåäà÷à íå ãàðàíòèðóåò, ÷òî ïðèåìíèê
áóäåò ÷èòàòü êîððåêòíîå äàííîå, çàïèñàííîå èñòî÷íèêîì.
Ìîäåëü ñåòè ïðîöåññîâ Êàíà àáñòðàãèðîâàíà îò âðåìåíè è ïîýòîìó
ÿâëÿåòñÿ ïîòåíöèàëüíî àñèíõðîííîé. Âñëåäñòâèå ýòîãî îíà ìîæåò çàäàâàòü
àëãîðèòìû íà áîëåå âûñîêîì óðîâíå àáñòðàêöèè è áûòü òðàíñôîðìèðî-
âàííîé â àñèíõðîííóþ èëè ñèíõðîííóþ ìîäåëü. Êðîìå òîãî, ýòà ìîäåëü
èìååò ïîòîêè â âèäå î÷åðåäåé. Ïîýòîìó îíà ìîæåò çàäàâàòü àëãîðèòìû, â
êîòîðûõ êîëè÷åñòâî äàííûõ â î÷åðåäè èçìåíÿåòñÿ äèíàìè÷åñêè. Íàïðèìåð,
ñåòü ïðîöåññîâ Êàíà ïîçâîëÿåò äèíàìè÷åñêè èçìåíÿòü êîëè÷åñòâî äàííûõ,
ïåðåäàííûõ â ïîòîê, âñëåäñòâèå ÷åãî ãëóáèíà áóôåðà ïîòîêà ìîæåò áûòü
íåîãðàíè÷åííîé.
Òàêèì îáðàçîì, ðàçëè÷íûå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ ìîæíî
êëàññèôèöèðîâàòü, ïðåæäå âñåãî, ïî ïðèçíàêàì èõ ïîòîêîâ, à òàêæå ïî
ñòðîåíèþ èõ ïðîöåññîâ, àêòîðîâ, îïåðàòîðîâ, òèïó ðàñïèñàíèÿ.
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
76 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
Êëàññèôèêàöèÿ ìîäåëåé îáðàáîòêè ïîòîêîâ äàííûõ ïî òèïó ðàñ-
ïèñàíèÿ. Êîððåêòíîñòü çàäàíèÿ àëãîðèòìà íà ìîäåëè âû÷èñëèòåëÿ ìîæåò
áûòü ïðîâåðåíà àíàëèòè÷åñêè (åñëè ýòî âîçìîæíî) èëè ñîñòàâëåíèåì
ðàñïèñàíèÿ âûïîëíåíèÿ âû÷èñëèòåëüíîãî ïðîöåññà íà äàííîé ìîäåëè.
Ðàñïèñàíèå ñîñòàâëÿåòñÿ ïðè íåïîñðåäñòâåííîì âûïîëíåíèè çàäàííîãî
àëãîðèòìà â îïðåäåëåííîé ÂÑ. Åñëè ñòðóêòóðà ÂÑ ñîîòâåòñòâóåò ãðàôó
ìîäåëè, òî ñîñòàâëåíèå ðàñïèñàíèÿ ñîñòîèò â îïðåäåëåíèè ïîðÿäêà âûïîë-
íåíèÿ îïåðàòîðîâ (àêòîðîâ, ïðîöåññîâ) è â âû÷èñëåíèè ìîìåíòà âûïîëíå-
íèÿ êàæäîãî îïåðàòîðà. Åñëè ñòðóêòóðà ÂÑ ïðîèçâîëüíàÿ, òî ïðåäâàðè-
òåëüíî âûïîëíÿþò ýòàï íàçíà÷åíèÿ îïåðàòîðîâ íà ïðîöåññîðû ýòîé ÂÑ.
Ðàçðàçëè÷àþò ïîëíîñòüþ ñòàòè÷åñêîå, ÷àñòè÷íî ñòàòè÷åñêîå, ïîë-
íîñòüþ äèíàìè÷åñêîå ðàñïèñàíèå, à òàêæå ðàñïèñàíèå ñî ñòàòè÷åñêèì
íàçíà÷åíèåì [15].  ïåðâîì ñëó÷àå âñå ýòàïû ñîñòàâëåíèÿ ðàñïèñàíèÿ
âûïîëíÿþò äî âûïîëíåíèÿ àëãîðèòìà â ÂÑ, ò.å. âî âðåìÿ êîìïèëÿöèè. Âî
âòîðîì ñëó÷àå íàçíà÷åíèå îïåðàòîðîâ íà ðåñóðñû è íàõîæäåíèå ïîðÿäêà
èõ âûïîëíåíèÿ ðåàëèçóþòñÿ âî âðåìÿ êîìïèëÿöèè, à ñîáñòâåííî ìîìåíò
âûïîëíåíèÿ îïðåäåëÿåòñÿ äèíàìè÷åñêè.  òðåòüåì ñëó÷àå âñå ýòàïû ñîñ-
òàâëåíèÿ ðàñïèñàíèÿ âûïîëíÿþòñÿ äèíàìè÷åñêè. ×åòâåðòûé ñëó÷àé îòëè-
÷àåòñÿ îò òðåòüåãî ëèøü òåì, ÷òî íàçíà÷åíèå íà ðåñóðñû âûïîëíÿåòñÿ âî
âðåìÿ êîìïèëÿöèè è íå êàñàåòñÿ âû÷èñëèòåëüíûõ ìîäåëåé, â êîòîðûõ ýòè
ðåñóðñû óæå íàçíà÷åíû.
 ñîîòâåòñòâèè ñ ïåðâûìè òðåìÿ ñëó÷àÿìè ìîæíî êëàññèôèöèðîâàòü
àëãîðèòìû è âû÷èñëèòåëüíûå ìîäåëè êàê òàêèå, êîòîðûå èìåþò ïîë-
íîñòüþ ñòàòè÷åñêîå, ÷àñòè÷íî ñòàòè÷åñêîå è ïîëíîñòüþ äèíàìè÷åñêîå
ðàñïèñàíèå.
Ïðè ñèíòåçå âû÷èñëèòåëåé íà îñíîâå ÑÁÈÑ è ÏËÈÑ ñîîòâåòñòâóþ-
ùèå ñèñòåìû àâòîìàòè÷åñêîãî ïðîåêòèðîâàíèÿ ïðèìåíÿþò äëÿ àëãîðèò-
ìîâ òîëüêî ïîëíîñòüþ ñòàòè÷åñêîå ðàñïèñàíèå è î÷åíü ðåäêî ÷àñòè÷íî
ñòàòè÷åñêîå, êàê, íàïðèìåð, ïðè ñèíòåçå ñàìîñèíõðîíèçèðóþùèõñÿ ÂÑ.
Ýòî ñâÿçàíî ñ òåì, ÷òî ðåçóëüòèðóþùàÿ ÂÑ íà óðîâíå ëîãè÷åñêèõ ñõåì
äîëæíà áûòü ïîëíîñòüþ äåòåðìèíèðîâàíà ñ òî÷íîñòüþ äî ëîãè÷åñêîãî
ýëåìåíòà è, êàê ïðàâèëî, íå äîïóñêàåò ñâîåãî äèíàìè÷åñêîãî ïåðåíàñòðàè-
âàíèÿ âî âðåìÿ âûïîëíåíèÿ çàäàííîãî àëãîðèòìà [10, 15]. Ïîýòîìó äàëåå
áóäåì îòäåëüíî ðàññìàòðèâàòü òàêèå ìîäåëè, êîòîðûå ïîääåðæèâàþò ñòà-
òè÷åñêîå ðàñïèñàíèå, èëè òàêèå, ïîâåäåíèå êîòîðûõ ìîæíî ïðåäâèäåòü íà
ñòàäèè êîìïèëÿöèè. Ïîñëåäíèå ÷àñòî íàçûâàþò ìîäåëÿìè ñ êâàçèñòàòè-
÷åñêèì ðàñïèñàíèåì.
Êëàññèôèêàöèÿ ìîäåëåé îáðàáîòêè ïîòîêîâ äàííûõ ïî òèïàì
àêòîðîâ. Àêòîð, èëè ïðîöåññ, èëè ïðîñòî îïåðàòîð, îáîçíà÷åííûé âåðøè-
íîé ãðàôà, âûïîëíÿåò íåêîòîðóþ ôóíêöèþ ïðè ñðàáàòûâàíèè. Àêòîðû
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 77
ðàçëè÷àþò ïî óñëîâèÿì ñðàáàòûâàíèÿ, ò.å. ïî ôóíêöèÿì çàïóñêà, êîëè-
÷åñòâó ìåòîê, èñïîëüçóåìûõ è ãåíåðèðóåìûõ èìè, è ïî èõ âíóòðåííåìó
ñòðîåíèþ.
Åñëè àêòîð èñïîëüçóåò è âîñïðîèçâîäèò íåêîòîðîå êà÷åñòâî ìåòîê, ýòî
êîëè÷åñòâî ñòàáèëüíî ïðè âûïîëíåíèè àëãîðèòìà è ìîæåò áûòü îïðåäå-
ëåíî âî âðåìÿ êîìïèëÿöèè, òî òàêîé àêòîð ÿâëÿåòñÿ ðåãóëÿðíûì. Åñëè ýòî
êîëè÷åñòâî íå ðàâíî êîíñòàíòå è ìîæåò èçìåíÿòüñÿ âî âðåìÿ âûïîëíåíèÿ
àëãîðèòìà â çàâèñèìîñòè îò äàííûõ â ïîòîêàõ, òî ýòî äèíàìè÷åñêèé àêòîð.
Ïðèìåðîì äèíàìè÷åñêîãî àêòîðà ÿâëÿåòñÿ âåðøèíà ïåðåêëþ÷àòåëÿ, êîòî-
ðàÿ â çàâèñèìîñòè îò íàëè÷èÿ ìåòêè íà åãî ëîãè÷åñêîì âõîäå ïðèíèìàåò
ìåòêó íà òîì èëè èíîì âõîäå äàííûõ. Ìîäåëè ñ äèíàìè÷åñêèìè àêòîðàìè
ìîãóò èìåòü äèíàìè÷åñêîå èëè êâàçèñòàòè÷åñêîå ðàñïèñàíèå.
Ó áîëüøèíñòâà ìîäåëåé àêòîð èìååò îäíó ôóíêöèþ çàïóñêà, íàïðèìåð
ôóíêöèþ, êîòîðàÿ çàïóñêàåò åãî ïðè íàëè÷èè îïðåäåëåííîãî êîëè÷åñòâà
ìåòîê íà âñåõ åãî âõîäàõ.  îáùåì ñëó÷àå àêòîð ìîæåò èìåòü íåñêîëüêî
ôóíêöèé çàïóñêà, ðàçëè÷àþùèõñÿ øàáëîíîì ñîñòîÿíèÿ âõîäîâ. Åñëè ïðè
íåêîòîðîì ñîñòîÿíèè âõîäîâ íàøåëñÿ ñîîòâåòñòâóþùèé øàáëîí, òî àêòîð
ñðàáàòûâàåò. Ñåòü ñ àêòîðàìè, âûïîëíÿþùèìè íåêîòîðûå ìîíîòîííûå
ôóíêöèè è èìåþùèìè ôóíêöèè çàïóñêà îáùåãî âèäà, ïîëó÷èëà íàçâàíèå
ñåòè îáðàáîòêè ïîòîêîâ äàííûõ (Dataflow Process Network) [21]. Â çàâèñè-
ìîñòè îò íàáîðà øàáëîíîâ ýòè àêòîðû ìîãóò áûòü êàê ðåãóëÿðíûìè, òàê è
äèíàìè÷åñêèìè.
Ãðàô Êàðïà è Ìèëëåðà, â êîòîðîì âñå àêòîðû — ðåãóëÿðíûå, ò.å. Wk =
= Òk, ïîëó÷èë íàçâàíèå ãðàôà ñèíõðîííûõ ïîòîêîâ äàííûõ (ÃÑÏÄ) èëè
ðåãóëÿðíîãî ãðàôà ïîòîêîâ äàííûõ [15]. Âòîðîå íàçâàíèå ïåðåêëèêàåòñÿ ñ
íàçâàíèåì ñîîòâåòñòâóþùåãî ïîäâèäà ðåøåò÷àòîãî ãðàôà àëãîðèòìà [16,
17] è ïîýòîìó èñïîëüçóåòñÿ ðåæå. Â ÃÑÏÄ ê ìåòêàì â ïîòîêàõ ìîæíî ïðè-
âÿçàòü òåãè, ñîîòâåòñòâóþùèå íîìåðàì öèêëîâ, ò.å. â íåì ïîòîêè ÿâëÿþòñÿ
ñèíõðîííûìè. Çäåñü ñëîâî «ñèíõðîííûé» íå îçíà÷àåò ñèíõðîííîñòü ïðèåìà
èëè âûäà÷è äàííûõ àêòîðàìè, à îçíà÷àåò ëèøü òî, ÷òî ìîäåëü âûïîëíÿåò
àëãîðèòì öèêëè÷íî. Ïðè÷åì ïîâåäåíèå ìîäåëè â êàæäîì öèêëå îäèíàêîâî:
÷èñëî èñïîëüçîâàíûõ è ñãåíåðèðîâàííûõ ìåòîê ðàâíî êîíñòàíòå.
Åñëè ÷èñëî ìåòîê, èñïîëüçîâàííûõ êàæäûì âõîäîì è ñãåíåðèðîâàííûõ
êàæäîé âåðøèíîé â îäíîì öèêëå, ðàâíî êîíñòàíòå, òî òàêîé ãðàô íàçûâàþò
îäíîðîäíûì ÃÑÏÄ. Ñèíîíèìîì îäíîðîäíîãî ÃÑÏÄ ÿâëÿåòñÿ ðåäóöèðîâàí-
íûé ãðàô àëãîðèòìà (ÐÃÀ), íàçâàíèå êîòîðîãî ïðîèñõîäèò îò ñïîñîáà åãî
ïîñòðîåíèÿ èç ðåãóëÿðíîãî ãðàôà çàâèñèìîñòåé ïî äàííûì [16].
Åñëè ÷èñëî ìåòîê, èñïîëüçîâàííûõ è ñãåíåðèðîâàííûõ âåðøèíàìè,
ðàçëè÷íî, òî ÃÑÏÄ ñëåäóåò íàçâàòü íåîäíîðîäíûì ÃÑÏÄ [17]. Íåîäíî-
ðîäíûå ÃÑÏÄ óïîìèíàþòñÿ â ðóññêîÿçû÷íîé ëèòåðàòóðå êàê «ìíîãîêðàò-
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
78 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
íûå» [18] èëè «ìíîãîñêîðîñòíûå» [19, 20] äëÿ ñèñòåì öèôðîâîé ôèëüòðàöèè,
ò.å. êàê ïåðåâîä ñëîâà multirate. Ñ ïîìîùüþ ÃÑÏÄ îïèñûâàþòñÿ ñèñòåìû, â
êîòîðûõ èñïîëüçîâàíî íåñêîëüêî âçàèìíîêðàòíûõ ÷àñòîò äèñêðåòèçàöèè.
Íåîäíîðîäíûé ÃÑÏÄ — ýòî êîìïàêòíàÿ ìîäåëü äëÿ çàäàíèÿ ïåðèîäè-
÷åñêîãî àëãîðèòìà, îäíàêî àíàëèçèðîâàòü åãî ñëîæíåå, ÷åì îäíîðîäíûé
ÃÑÏÄ. Êðîìå òîãî, åãî ìîäåëèðîâàíèå óñëîæíÿåòñÿ âîçìîæíîñòüþ áëîêè-
ðîâîê. Ïîýòîìó äëÿ àíàëèçà è ñèíòåçà ÂÑ íà åãî îñíîâå íåîäíîðîäíûé
ÃÑÏÄ ÷àñòî ïðåîáðàçóþò â ýêâèâàëåíòíûé îäíîðîäíûé ÃÑÏÄ [15]. Ìî-
äåëü íåîäíîðîäíîãî ÃÑÏÄ ïîëó÷èëà øèðîêîå ðàñïðîñòðàíåíèå. Íàïðè-
ìåð, îíà ÿâëÿåòñÿ îñíîâîé èçâåñòíîãî ïàêåòà Matlab-Simulink [21].
ÃÑÏÄ âñåãäà àññîöèèðîâàëèñü ñ àëãîðèòìàìè ÖÎÑ. Îäíîðîäíûé ÃÑÏÄ
âçàèìíî îäíîçíà÷íî ñîîòâåòñòâóåò ñèãíàëüíîìó ãðàôó àëãîðèòìà ÖÎÑ èëè
âû÷èñëèòåëüíîé ñõåìå ñ ïåðèîäîì âû÷èñëåíèé îäèí òàêò [19, 22, 23].
Ðàçðàáîòàíà òàêàÿ ðàçíîâèäíîñòü ÃÑÏÄ, â êîòîðîé âìåñòî îäèíî÷íûõ
ìåòîê ðàññìàòðèâàþòñÿ ãðóïïû ïî N ìåòîê, ñîîòâåòñòâóþùèå ìàññèâàì
îòñ÷åòîâ. Òàêîé ÃÑÏÄ ïîëó÷èë íàçâàíèå ìàñøòàáèðîâàííîãî [15]. Äëÿ
òîãî ÷òîáû çàäàòü àëãîðèòì îáðàáîòêè ìíîãîìåðíîãî ñèãíàëà, ìàñøòàáè-
ðîâàííûé ÃÑÏÄ áûë îáîáùåí äî ìíîãîìåðíîãî. Â òàêîì ÃÑÏÄ ìåòêè
ðàññìàòðèâàþòñÿ êàê ìíîãîìåðíûå ìàññèâû ñ êðàòíûìè ðàçìåðàìè, à
ðàçìåòêà äóã âûïîëíåíà ñ ïîìîùüþ âåêòîðîâ, ðàçìåðíîñòü êîòîðûõ ñîâïà-
äàåò ñ ÷èñëîì ðàçìåðíîñòåé ìàññèâîâ [15].
Ñóùåñòâóþò ìîäåëè, èìåþùèå èåðàðõèþ öèêëîâ âûïîëíåíèÿ àêòîðîâ âî
âðåìåíè, ïðè÷åì âî âíóòðåííèõ öèêëàõ ÷èñëî èñïîëüçîâàííûõ è ñãåíåðè-
ðîâàííûõ ìåòîê ìîæåò áûòü ïåðåìåííûì, íî ïðè ïîäñ÷åòå âî âíåøíåì öèêëå
ñóììàðíîå ÷èñëî ìåòîê ñòàáèëüíî. Òàêèå ìîäåëè ïîëó÷èëè íàçâàíèå öèêëî-
ñòàòè÷åñêèõ ÃÑÏÄ, è â íèõ óñòðàíåíû ìíîãèå íåäîñòàòêè, ïðèñóùèå ìîäå-
ëÿì ïðåäñòàâëåíèÿ àëãîðèòìîâ íåîäíîðîäíûìè ÃÑÏÄ [24].
Ãðàô, â êîòîðîì èñïîëüçóþòñÿ äèíàìè÷åñêèå àêòîðû, íàçûâàåòñÿ äèíà-
ìè÷åñêèì ãðàôîì ïîòîêîâ äàííûõ (ÄÃÏÄ).  ñâÿçè ñ îãðàíè÷åíèåì íà çàïóñê
àêòîðîâ âîçìîæíîñòè ñòàòè÷åñêîãî ÃÏÄ îãðàíè÷åíû ïî ñðàâíåíèþ ñ ñåòüþ
Ïåòðè. Ïî ñâîèì îñîáåííîñòÿì ÄÃÏÄ ýêâèâàëåíòåí ìàøèíå Òüþðèíãà, êîòî-
ðàÿ, â ñâîþ î÷åðåäü, ÿâëÿåòñÿ áîëåå óíèâåðñàëüíîé ìîäåëüþ, ÷åì ñåòü Ïåòðè.
Âñëåäñòâèå ýòîé óíèâåðñàëüíîñòè ÄÃÏÄ äîñòàòî÷íî ñëîæíî àíàëèçèðîâàòü,
òàê êàê åãî ïîâåäåíèå â çàâèñèìîñòè îò ïîòîêîâ äàííûõ íåîïðåäåëåííî.
Ïîýòîìó íåêîòîðûå çàäà÷è àíàëèçà ÄÃÏÄ îñòàþòñÿ íåðàçðåøèìûìè [15].
Òàêàÿ ìîäåëü îáðàáîòêè ïîòîêîâ äàííûõ ïî ìíîãèì ñâîéñòâàì ñïîâïàäàåò ñ
ìîäåëüþ äëÿ ðåàëèçàöèè ÿçûêà VHDL, èñïîëüçóåìîé êàê äëÿ ìîäåëèðî-
âàíèÿ, òàê è äëÿ ñèíòåçà ÂÑ [21, 25].
Åñëè ÄÃÏÄ ñîñòîèò èç àêòîðîâ, èñïîëüçóþùèõ óïðàâëÿþùèå ìåòêè
äâîè÷íîãî òèïà, è ðåãóëÿðíûõ àêòîðîâ, òî òàêîé ÄÃÏÄ íàçûâàåòñÿ áó-
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 79
ëåâñêèì ÃÏÄ. Áîëåå øèðîêóþ îáëàñòü àëãîðèòìîâ ïðåäñòàâëÿåò öåëî÷è-
ñëåííûé ÃÏÄ, àêòîðû êîòîðîãî óïðàâëÿþòñÿ öåëûìè ÷èñëàìè [15]. Àêòî-
ðû ýòèõ ãðàôîâ ìîæíî îïèñàòü ÿçûêîì ñ ïðèìåíåíèåì îïåðàòîðîâ ñîîò-
âåòñòâåííî if-then-else èëè case.  îòëè÷èå îò ÄÃÏÄ îáùåãî âèäà ïîâåäå-
íèå áóëåâñêîãî èëè öåëî÷èñëåííîãî ÃÏÄ íå çàâèñèò îò ñïîñîáà ñîñòàâ-
ëåíèÿ ðàñïèñàíèÿ äëÿ íåãî, òàê êàê ýòè ìîäåëè ÿâëÿþòñÿ ðàçíîâèäíîñòÿìè
ñåòè Êàíà. Áóëåâñêèé ÃÏÄ îòëè÷àåòñÿ îò ÃÏÄ Äåííèñà òåì, ÷òî åãî ïîòîêè
ïðåäñòàâëåíû íå ðåãèñòðàìè, à áóôåðàìè FIFO.
ÄÃÏÄ ìîæåò èìåòü íåáîëüøîå ÷èñëî äèíàìè÷åñêèõ âåðøèí, ïîâåäå-
íèå êîòîðûõ ìîæíî ñïðîãíîçèðîâàòü, íàïðèìåð, îïðåäåëåíèåì âåðîÿò-
íîñòè èõ ñðàáàòûâàíèÿ. Òàêèå ÄÃÏÄ ïîçâîëÿþò ðàññ÷èòàòü ñòàòè÷åñêîå
ðàñïèñàíèå äëÿ âñåõ âåðøèí, êðîìå äèíàìè÷åñêèõ. Ýòè ÄÃÏÄ ïîëó÷èëè
íàçâàíèå êâàçèñòàòè÷åñêèõ [15]. Åñëè âîçìîæíî âåðøèíû ïîäãðàôà êâàçè-
ñòàòè÷åñêîãî ÄÃÏÄ ñ äèíàìè÷åñêèìè âåðøèíàìè ñêëåèòü â âåðøèíó,
êîòîðàÿ áóäåò âåñòè ñåáÿ, êàê ñòàòè÷åñêàÿ, òî, âûïîëíèâ òàêóþ ïðîöåäó-
ðó, ÄÃÏÄ ìîæíî ïðåîáðàçîâàòü â ÃÑÏÄ.  ýòîì ñëó÷àå ÄÃÏÄ íàçûâàþò
ÄÃÏÄ ñ ýôôåêòèâíûì ïîâåäåíèåì [15].
 ïàðàìåòðè÷åñêîì ÃÑÏÄ àêòîðû ìîãóò èìåòü íåêîòîðûå íàáîðû
ôóíêöèé, à äóãè — ñîòâåòñòâóþùèå íàáîðû ðàçìåòîê, êîòîðûå ìîæíî
äèíàìè÷åñêè èçìåíÿòü íåçàâèñèìî îò ïîòîêîâ äàííûõ íà ïåðèîä íå ìåíü-
øå îäíîãî öèêëà. Äëÿ òàêîãî ÃÑÏÄ ìîæíî ñîñòàâèòü êâàçèñòàòè÷åñêîå
ðàñïèñàíèå. Ïî ñâîéñòâàì òàêîé ãðàô ïîõîæ íà öèêëî-ñòàòè÷åñêèé ÃÑÏÄ
[26].  ìîäåëèðóþùåé ñèñòåìå PtolemyII ïàðàìåòðè÷åñêèé ÃÑÏÄ, êàê è
öèêëîñòàòè÷åñêèé öåëî÷èñëåííûé, âíåäðåí â ïîëíîì îáúåìå. Ýòà ñèñòåìà
ýôôåêòèâíà ïðè ðàçðàáîòêå ìàòîáåñïå÷åíèÿ äëÿ ÂÑ îáðàáîòêè ìóëüòè-
ìåäèéíûõ äàííûõ [21].
Áëîêîâûé ÃÏÄ ÿâëÿåòñÿ ðàçâèòèåì ïàðàìåòðè÷åñêîãî è ìàñøòàáèðî-
âàííîãî ÃÑÏÄ. Â íåì ïîä ìåòêîé ïîíèìàåòñÿ ïàêåò èëè áëîê äàííûõ ñ
îïðåäåëåííûìè ñòðóêòóðîé è ñâîéñòâàìè. Ïðè÷åì àêòîðû è äóãè ÃÏÄ
âûïîëíÿþò ñâîè ôóíêöèè â ñîòâåòñòâèè ñ òåãàìè, êîòîðûå ïðèïèñàíû
ìåòêàì. Òàêîé ÃÏÄ ÿâëÿåòñÿ äèíàìè÷åñêèì è èìååò êâàçèñòàòè÷åñêîå
ðàñïèñàíèå. Áëîêîâûé ÃÏÄ ÿâëÿåòñÿ óäà÷íîé ìîäåëüþ äëÿ ñîçäàíèÿ àëãî-
ðèòìîâ îáðàáîòêè öèôðîâûõ ñèãíàëîâ ñ ïåðåìåííîé ñòðóêòóðîé, íàïðè-
ìåð ñæàòûõ âèäåîäàííûõ [27].
Èåðàðõè÷åñêèå ÃÏÄ. Ìîäåëè ïîòîêîâ äàííûõ êëàññèôèöèðóþò òàê-
æå ïî ïðèçíàêó, ÿâëÿåòñÿ ëè ìîäåëü èåðàðõè÷åñêîé.  èåðàðõè÷åñêîé
ìîäåëè âåðøèíà àêòîðà ñàìà ìîæåò áûòü ïðåäñòàâëåíà ìîäåëüþ îïðåäå-
ëåííîãî òèïà. Ïðè èñïîëüçîâàíèè ÿçûêà ïðîãðàììèðîâàíèÿ ïîñòðîåíèå
èåðàðõèè ýêâèâàëåíòíî âûçîâàì ñîîòâåòñòâóþùèõ ïðîöåäóð, âûïîëíÿþ-
ùèõ âû÷èñëåíèÿ ìîäåëåé íèæíåãî óðîâíÿ. Åñëè ìîäåëü íèæíåãî óðîâíÿ íå
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
80 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
âûðîæäåíà, òî îíà ìîæåò áûòü ïðåäñòàâëåíà íåêîòîðûì àâòîìàòîì ñ ïà-
ìÿòüþ èëè ôóíêöèåé ïðåîáðàçîâàíèÿ. Ïîýòîìó ÷àñòî âû÷èñëèòåëüíûå ìîäå-
ëè êëàññèôèöèðóþò êàê ìîäåëè, èìåþùèå àêòîðû ñ ïàìÿòüþ èëè áåç íåå.
Ìîæíî ïîëó÷èòü ïàðàìåòðè÷åñêèé öèêëî-ñòàòè÷åñêèé ÃÑÏÄ ñêëåè-
âàíèåì ìíîæåñòâ âåðøèí îäíîðîäíîãî ÃÑÏÄ. Ïðè ýòîì íîâàÿ âåðøèíà
àêòîðà âêëþ÷àåò â ñåáÿ íåñêîëüêî âåðøèí èñõîäíîãî ãðàôà è ïîýòîìó
ÿâëÿåòñÿ èåðàðõè÷åñêîé.  òî æå âðåìÿ, íîâàÿ âåðøèíà èìååò ñëîæíóþ
ôóíêöèþ, êîòîðàÿ ïîêðûâàåò ôóíêöèè ñêëååííûõ âåðøèí èñõîäíîãî ãðà-
ôà, è çà îäèí öèêë ïîñëåäîâàòåëüíî âûïîëíÿåò âû÷èñëåíèÿ ýòèõ âåðøèí,
ò.å. îíà óæå íå ðàññìàòðèâàåòñÿ êàê èåðàðõè÷åñêàÿ. Òàêàÿ âåðøèíà íå
ñîäåðæèò ïàìÿòè, òàê êàê ïîòîêè ñ áóôåðàìè îñòàþòñÿ ñíàðóæè âåðøèíû.
Ïðîöåäóðà òàêîãî ïðåîáðàçîâàíèÿ ÃÑÏÄ ïîëó÷èëà íàçâàíèå ñâîðà÷èâà-
íèÿ, à ïîëó÷åííûé ãðàô — ñâåðíóòîãî ÃÑÏÄ. Òàêàÿ îïåðàöèÿ çàèìñòâî-
âàíà èç îïòèìèçàöèè öèêëè÷åñêèõ ïðîãðàìì è ýêâèâàëåíòíà ñïîñîáó ñâî-
ðà÷èâàíèÿ öèêëîâ. Ïî ñâîåé ñóòè ñâåðíóòûé ÃÑÏÄ èçîìîðôåí ãðàôó
ñòðóêòóðû íåêîòîðîãî êîíâåéåðíîãî âû÷èñëèòåëÿ, à ñâîðà÷èâàíèå ÃÑÏÄ
èñïîëüçóåòñÿ êàê ìåòîä ñèíòåçà òàêèõ âû÷èñëèòåëåé [28].
Äëÿ àíàëèçà èåðàðõè÷åñêîé ìîäåëè åå æåëàòåëüíî ïðåîáðàçîâàòü â
îäíîóðîâíåâóþ ìîäåëü áåç èåðàðõèè. Ñóùåñòâóþò ìîäåëè ïîòîêîâ äàí-
íûõ ñ äèíàìè÷åñêîé èåðàðõèåé, íàïðèìåð åñëè âû÷èñëèòåëüíûé ïðîöåññ
àêòîðà âûçûâàåò äðóãèå ïðîèçâîëüíûå ïðîöåññû, êàê ïîäïðîãðàììû. Õîòÿ
òàêàÿ ìîäåëü èìååò áîëüøèå êðåàòèâíûå âîçìîæíîñòè äëÿ ïðîãðàììèñ-
òîâ, îíà ÿâëÿåòñÿ íåäåòåðìèíèðîâàííîé, íå äàåò âîçìîæíîñòè ñòðîèòü
îäíîóðîâíåâóþ ìîäåëü è åå àíàëèç çàòðóäíèòåëåí.
Ãðàô çàâèñèìîñòåé ïî äàííûì (ÃÇÄ) è(èëè) óïðàâëåíèþ áûë ââåäåí
êàê åñòåñòâåííàÿ ìîäåëü âû÷èñëåíèé, êîòîðàÿ óäîâëåòâîðÿåò ïîòðåáíîñòè
êîìïèëÿöèè è ðàñïàðàëëåëèâàíèÿ ïðîãðàìì, íàïèñàííûõ íà èìïåðàòèâ-
íûõ ÿçûêàõ [5,29]. Â ýòîì ãðàôå âåðøèíû-îïåðàòîðû ñâÿçàíû äóãàìè,
êîòîðûå ñîîòâåòñòâóþò íåïîñðåäñòâåííûì çàâèñèìîñòÿì ïî äàííûì ìåæäó
îïåðàòîðàìè â àëãîðèòìå èëè ïðîãðàììå. Åñëè â àëãîðèòìå èñïîëüçóåòñÿ
ïðèíöèï îäíîêðàòíîãî ïðèñâàèâàíèÿ, òî äóãàì ñîîòâåòñòâóþò îïåðàíäû
àëãîðèòìà [30]. Âî âðåìÿ êîìïèëÿöèè ïðîãðàìì àëãîðèòì äåêîìïîíèðóåòñÿ
íà ãðàô óïðàâëåíèÿ è íàïðàâëåííûå àöèêëè÷åñêèå ãðàôû íåïîñðåäñòâåííûõ
çàâèñèìîñòåé (èçâåñòíûå êàê DAG), êîòîðûå ïðåäñòàâëÿþò ñîáîé ÃÇÄ [31].
Âûïîëíåíèå àëãîðèòìà, çàäàííîãî ÃÇÄ, ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëü-
íûé îáõîä âåðøèí â ñîîòâåòñòâèè ñ èõ òîïîëîãè÷åñêîé ñîðòèðîâêîé [32].
Ïðè èñïîëüçîâàíèè ÿðóñíî-ïàðàëëåëüíîé ôîðìû ÃÇÄ ðàçðåøàåòñÿ
îäíîâðåìåííîå âûïîëíåíèå îïåðàòîðîâ, ñîîòâåòñòâóþùèõ îäíîìó ÿðóñó
ãðàôà. Ïîýòîìó ïîñòðîåíèå ÿðóñíî-ïàðàëëåëüíîé ôîðìû ÃÇÄ èñïîëüçóåò-
ñÿ êàê ïðîñòåéøèé è ïîíÿòíûé ñïîñîá ðàñïàðàëëåëèâàíèÿ àëãîðèòìîâ
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 81
[29]. Íî ÃÇÄ íå ïðèñïîñîáëåí äëÿ çàäàíèÿ àëãîðèòìîâ îáðàáîòêè ïîòîêîâ
äàííûõ. Òàêóþ îáðàáîòêó ìîæíî âûïîëíÿòü òîëüêî ïðè ïîñëåäîâàòåëüíîì
âûïîëíåíèè àëãîðèòìà: êàê òîëüêî çàâåðøàòñÿ âû÷èñëåíèÿ äëÿ n-é ãðóïïû
âõîäíûõ äàííûõ, ìîæíî íà÷àòü âû÷èñëåíèÿ äëÿ n +1-é ãðóïïû.
ÃÇÄ, â êîòîðîì çàäàíû çàäåðæêè âûïîëíåíèÿ îïåðàòîðîâ èëè ÷èñëî
ñòóïåíåé êîíâåéåðíîãî âû÷èñëèòåëÿ, ñîîòâåòñòâóþùåãî âåðøèíå, ïîëó-
÷èë íàçâàíèå áàçîâîé ÂÑ. Åñëè äóãè ÃÇÄ âûïîëíÿþò ôóíêöèþ áóôåðà
FIFO, òî ìîæíî ïîëó÷èòü óðàâíîâåøåííóþ áàçîâóþ ÂÑ, â êîòîðîé çà-
äåðæêà ìåæäó äâóìÿ ïðîèçâîëüíûìè âåðøèíàìè, çàâèñèìûìè ïî äàííûì,
îäèíàêîâà äëÿ ëþáûõ ìàðøðóòîâ ðàñïðîñòðàíåíèÿ îïåðàíäîâ ìåæäó íè-
ìè. Îñîáåííîñòü óðàâíîâåøåííîé áàçîâîé ÂÑ ñîñòîèò â òîì, ÷òî îíà
ñîîòâåòñòâóåò àöèêëè÷åñêîìó àëãîðèòìó îáðàáîòêè ïîòîêîâ äàííûõ, ò.å.
ýêâèâàëåíòíà îäíîðîäíîìó àöèêëè÷åñêîìó ÃÑÏÄ, â êîòîðîì ðàçìåòêà
äóãè ðàâíà ÷èñëó ñòóïåíåé êîíâåéåðà ñîîòâåòñòâóþùåé âåðøèíû áàçîâîé
ÂÑ [17, 23].
Âî âðåìÿ ñîñòàâëåíèÿ ðàñïèñàíèÿ âûïîëíåíèÿ àëãîðèòìà íà ÃÏÄ
ñòðîèòñÿ ðàçâåðòêà âû÷èñëåíèé, ÿâëÿþùàÿñÿ ÃÇÄ. Ñîîòâåòñòâåííî, åñëè
ÃÇÄ — ïåðèîäè÷åñêèé, òî îí ìîæåò áûòü îòîáðàæåí â ÃÑÏÄ, êîòîðûé
ìîæíî ïîñòðîèòü ïî ïåðèîäó ÃÇÄ. Òàêèì ñïîñîáîì ñòðîèòñÿ ÐÃÀ, ÿâëÿþ-
ùèéñÿ ñèíîíèìîì îäíîðîäíîãî ÃÑÏÄ [16].
ÃÇÄ ðåãóëÿðíîãî àëãîðèòìà, íàïðèìåð ãíåçäà öèêëîâ, ïðåäñòàâëÿåò
ñîáîé ïåðèîäè÷åñêèé èëè ðåøåò÷àòûé ãðàô, ïåðèîä êîòîðîãî ïðåäñòàâ-
ëÿåò DAG òåëà ãíåçäà öèêëîâ [17]. Ñóùåñòâóåò ìåòîäèêà îòîáðàæåíèÿ
òàêîãî ÃÇÄ â ãðàô ñèñòîëè÷åñêîãî ïðîöåññîðà [17, 33, 34]. Îíà ÿâëÿåòñÿ
îäíîé èç íåìíîãèõ ìåòîäèê, ïîçâîëèâøèõ ôîðìàëüíûì îáðàçîì ïðåîáðà-
çîâàòü âû÷èñëèòåëüíûé àëãîðèòì â ïàðàëëåëüíóþ ñòðóêòóðó ñïåöèàëè-
çèðîâàííîãî âû÷èñëèòåëÿ. Ñëåäóåò çàìåòèòü, ÷òî ãðàô ñèñòîëè÷åñêîãî
ïðîöåññîðà, ïî ñóòè, ÿâëÿåòñÿ îäíîðîäíûì ÃÑÏÄ è, ñëåäîâàòåëüíî, ÃÑÏÄ
ìîæíî ñòðîèòü, èñïîëüçóÿ ýôôåêòèâíûå è ôîðìàëüíûå ìåòîäû ñèíòåçà
ñèñòîëè÷åñêèõ ïðîöåññîðîâ [16].
Ïðîâåðêà íà îòñóòñòâèå áëîêèðîâîê. Äëÿ òîãî ÷òîáû çàðàíåå îïðå-
äåëèòü, áóäåò ëè ñîñòàâëåíèå ðàñïèñàíèÿ óñïåøíûì, íåîáõîäèìî ïðîâå-
ðèòü ìîäåëü íà îòñóòñòâèå áëîêèðîâîê. Òàêóþ ïðîâåðêó ìîæíî âûïîëíèòü
àíàëèòè÷åñêè, åñëè àêòîðû ïðåäñòàâëÿþò ôóíêöèè, îòîáðàæàþùèå âõîä-
íûå ïîòîêè äàííûõ â âûõîäíûå. Áëîêèðîâêà ìîäåëè íàñòóïàåò òîãäà,
êîãäà âñëåäñòâèå áëîêèðîâêè îòäåëüíûõ àêòîðîâ ñ íåêîòîðîãî ìîìåíòà
ìîäåëü íå â ñîñòîÿíèè ïîâòîðÿòü ïåðèîä àëãîðèòìà è ãåíåðàöèþ ñèãíàëîâ
ïðîèçâîëüíîé äëèíû.
Íàèáîëåå êîíñòðóêòèâíûì è îáùèì ÿâëÿåòñÿ ìåòîä ïðîâåðêè, îñíî-
âàííûé íà òåîðèè ðåøåòîê. Öåïî÷êè (ñèãíàëû) Ñ âîçìîæíûõ ïîòîêîâ
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
82 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
äàííûõ à³ â ÃÏÄ ôîðìèðóþò ÷àñòè÷íûé ïîðÿäîê, êîòîðûé äëÿ ìíîãèõ
ÃÏÄ ÿâëÿåòñÿ çàâåðøåííûì. Ñîãëàñíî ýòîìó ìåòîäó ñîñòàâëÿþò óðàâ-
íåíèå a F ai i�
�
( )
1
, êîòîðîå ñâÿçûâàåò ïîòîê äàííûõ à³ íà ³-é èòåðàöèè ñ
ïîòîêîì äàííûõ ai�1
íà ³–1-é èòåðàöèè íà îñíîâå êîìïîçèöèè ôóíêöèé
âñåõ àêòîðîâ, âõîäÿùèõ â çàìêíóòûå öèêëû ÃÏÄ. Åñëè ôóíêöèÿ F —
ìîíîòîííà, òî ìîäåëü ÃÏÄ íå èìååò áëîêèðîâîê è âû÷èñëåíèÿ â ìîäåëè
ìîãóò âûïîëíÿòüñÿ ñêîëü óãîäíî äîëãî. Ýòî ýêâèâàëåíòíî òîìó, ÷òî ìîæ-
íî íàéòè ðåøåíèå óðàâíåíèÿ îòîáðàæåíèÿ F (à) = à, ò. å. êðàéíþþ íåïîä-
âèæíóþ òî÷êó îòîáðàæåíèÿ, êîòîðàÿ ðàâíà åäèíñòâåííîìó êðàéíåìó âåðõ-
íåìó ïðåäåëó öåïî÷êè Ñ.
Ñóòü ìåòîäà ìîæíî ðàñêðûòü íà ïðîñòîì ïðèìåðå èòåðàòèâíîãî ïðî-
öåññà âû÷èñëåíèÿ àïïðîêñèìàöèè ôóíêöèè f (õ) ðÿäîì Òåéëîðà, â êîòîðîì
â êàæäîé ñëåäóþùåé èòåðàöèè ïîëó÷àåòñÿ óòî÷íåííûé ðåçóëüòàò. Òîãäà
à³ — ýòî ïðèáëèæåíèå íà ³-é ³òåðàöèè, Ñ = (à0, à1, à2 ...), à f (à) — êðàéíèé
âåðõíèé ïðåäåë, ðàâíûé òî÷íîìó çíà÷åíèþ ôóíêöèè f (õ). Ýòîò ìåòîä
ìîæíî èñïîëüçîâàòü äëÿ ìíîãèõ ìîäåëåé, âêëþ÷àÿ ñåòü îáðàáîòêè ïîòî-
êîâ äàííûõ è ñåòü Êàíà [21].
Äëÿ ÃÏÄ Êàðïà è Ìèëëåðà îòñóòñòâèå áëîêèðîâîê ýêâèâàëåíòíî íàëè-
÷èþ öåëî÷èñëåííîãî ðåøåíèÿ çàäà÷è ëèíåéíîãî ïðîãðàììèðîâàíèÿ ñ íå-
ðàâåíñòâàìè îãðàíè÷åíèÿ ÷èñëà ìåòîê â äóãàõ [13].
Äëÿ ìîäåëè íåîäíîðîäíîãî ÃÑÏÄ îòñóòñòâèå áëîêèðîâîê îïðåäåëÿþò
ïðè ðåøåíèè ñèñòåìû óðàâíåíèé áàëàíñà Ãr = 0. Çäåñü Ã — òîïîëî-
ãè÷åñêàÿ ìàòðèöà, èìåþùàÿ ñâîéñòâà ìàòðèöû èíöèäåíòíîñòè ãðàôà è
ó÷èòûâàþùàÿ ÷èñëî èñïîëüçîâàííûõ è âûäàâàåìûõ ìåòîê êàæäîé âåð-
øèíîé; r — âåêòîð ïîâòîðåíèé, óêàçûâàþùèé, ñêîëüêî ðàç êàæäàÿ âåðøè-
íà äîëæíà ñðàáàòûâàòü ïðè âûïîëíåíèè îäíîãî öèêëà àëãîðèòìà. Îäíàêî
â ýòîé ìîäåëè, êàê è â ÃÏÄ Êàðïà è Ìèëëåðà, áëîêèðîâêà âîçìîæíà, åñëè
÷èñëî ìåòîê â äóãàõ ìîäåëè â åå íà÷àëüíîì ñîñòîÿíèè íåäîñòàòî÷íî. Òàêàÿ
æå ïðîâåðêà âîçìîæíà äëÿ áóëåâñêîãî ÃÑÏÄ, åñëè â ìàòðèöó Ã âñòàâëåíû
âåðîÿòíîñòè âûäà÷è è èñïîëüçîâàíèÿ ìåòîê äèíàìè÷åñêèìè àêòîðàìè.
Îäíîðîäíûé ÃÑÏÄ íèêîãäà íå áëîêèðóåòñÿ ïðè íàëè÷èè ìåòîê íà-
÷àëüíîãî ñîñòîÿíèÿ â áóôåðàõ, âõîäÿùèõ â öèêëû ãðàôà, è ïîýòîìó áëîêè-
ðîâêè â íåì ìîæíî íå ïðîâåðÿòü.
Òàêèì îáðàçîì, àíàëèòè÷åñêàÿ ïðîâåðêà ïîòîêîâîé ìîäåëè íà îòñóòñòâèå
áëîêèðîâîê íåñëîæíà äëÿ ÃÑÏÄ è óñëîæíÿåòñÿ ñ ïåðåõîäîì ê áîëåå îáîá-
ùåííûì ìîäåëÿì ÃÏÄ. Òàê, äëÿ ñåòè ïîòîêîâ äàííûõ äîêàçàòåëüñòâî îò-
ñóòñòâèÿ áëîêèðîâîê ñâîäèòñÿ ê ïðîöåññó ïîèñêà íåïîäâèæíîé òî÷êè îòîáðà-
æåíèÿ ïðîñòðàíñòâà ñèãíàëîâ, êîòîðûé ÿâëÿåòñÿ âåñüìà ñëîæíûì è ñâÿçàí ñ
íåîáõîäèìîñòüþ ó÷èòûâàòü âñå âîçìîæíûå ïåðåêëþ÷åíèÿ äèíàìè÷åñêèõ
àêòîðîâ [21]. Íàèáîëåå ÷àñòî èñïîëüçóåìûé ñïîñîá ïðîâåðêè áëîêèðîâîê —
äèíàìè÷åñêîå ñîñòàâëåíèå ðàñïèñàíèÿ è ìîäåëèðîâàíèå ñåòè.
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 83
Âûáîð àëãîðèòìà îáðàáîòêè ïîòîêîâ äàííûõ. Îñíîâíûå ñâîéñòâà
ìîäåëåé îáðàáîòêè ïîòîêîâ äàííûõ ïðèâåäåíû â òàáëèöå. Âçàèìîîòíî-
øåíèå ãðàôîâûõ ìîäåëåé îáðàáîòêè ïîòîêîâ äàííûõ ïðåäñòàâëåíî íà
ðèñóíêå â âèäå ãðàôà. Èç ïðèâåäåííûõ äàííûõ ìîæíî ñäåëàòü ñëåäóþùèå
âûâîäû.
Ãðàô ïîòîêîâ äàííûõ, èñïîëüçóåìûé äëÿ çàäàíèÿ ðàçëè÷íûõ àëãîðèò-
ìîâ îáðàáîòêè ïîòîêîâ äàííûõ, èìååò ìíîãî ðàçíîâèäíîñòåé, ñîçäàííûõ
äëÿ óïðîùåíèÿ åãî àíàëèçà, àäàïòàöèè ê îòäåëüíûì êëàññàì àëãîðèòìîâ,
áîëüøåé âûðàçèòåëüíîñòè èõ ïðåäñòàâëåíèÿ. Àëãîðèòì, çàäàííûé ÃÏÄ,
ïîêàçûâàåò, êàê ïîëó÷àåòñÿ ðåçóëüòèðóþùèé ïîòîê äàííûõ è íå îïðå-
äåëÿåò òî÷íûé ïîðÿäîê âû÷èñëåíèé. Îòîáðàæåíèå òàêîãî àëãîðèòìà â ÂÑ
ñîñòîèò â íàõîæäåíèè îïòèìàëüíîãî ðàñïèñàíèÿ è íàçíà÷åíèè âåðøèí
ãðàôà â ïðîöåññîðíûå ýëåìåíòû ÂÑ. Ïîèñê îïòèìàëüíîãî îòîáðàæåíèÿ
ÿâëÿåòñÿ NP-ïîëíîé çàäà÷åé. Âûáîð ðàçíîâèäíîñòè ÃÏÄ çàâèñèò îò ïðåä-
ìåòíîé îáëàñòè ïðèìåíåíèÿ àëãîðèòìà (ìîäåëèðîâàíèå èëè îáðàáîòêà
äàííûõ (ñèãíàëîâ), õàðàêòåð ñèãíàëîâ) è ñïîñîáà åãî èñïîëíåíèÿ (àïïà-
ðàòíîãî èëè ïðîãðàììíîãî).
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
84 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
ÄÃÏÄ
Áëîêîâûé ÃÏÄ
Ñåòü ïðîöåññîâ Êàíà
Ïàðàìåòðè÷åñêèé ÃÑÏÄ
ÃÑÏÄ
Íåîäíîðîäíûé ÃÑÏÄ
Ñåòü Ïåòðè
Êâàçèñòàòè÷åñêèé ÃÏÄ
ÃÏÄ ñ ýôôåêòèâíûì ïîâåäåíèåì
Ñåòü îáðàáîòêè ïîòîêîâ äàííûõ
Ãðàô Êàðïà è Ìèëëåðà
Ñòàòè÷åñêèé ÃÏÄ
Ñâåðíóòûé ÃÑÏÄÌàñøòàáèðîâàííûé ÃÑÏÄ
Öåëî÷èñëåííûé ÃÏÄ
Áóëåâñêèé ÃÏÄ
Ñèñòîëè÷åñêèé ïðöåññîð
Îäíîðîäíûé ÃÑÏÄ
Öèêëîñòàòè÷åñêèé ÃÑÏÄ
Ìíîãîìåðíûé ÃÑÏÄ
Äëÿ èñïîëüçîâàíèÿ â ñèñòåìíîì ñèíòåçå àïïàðàòíûõ óñòðîéñòâ îáðà-
áîòêè ïîòîêîâ äàííûõ íàèáîëåå ïðèñïîñîáëåíà ìîäåëü ÃÑÏÄ è åå óñîâåð-
øåíñòâîâàíèÿ — ïàðàìåòðè÷åñêèé, öèêëî-ñòàòè÷åñêèé è ìíîãîìåðíûé
ÃÑÏÄ. Ìîãóò áûòü òàêæå èñïîëüçîâàíû ìîäåëè êâàçèñòàòè÷åñêîãî ÄÃÏÄ
è ÄÃÏÄ ñ ýôôåêòèâíûì ïîâåäåíèåì, äëÿ êîòîðûõ ìîæíî ñîñòàâèòü ðàñïè-
ñàíèå ñî ñâîéñòâàìè ñòàòè÷åñêîãî ðàñïèñàíèÿ. Èåðàðõè÷åñêèå ìîäåëè,
ñîñòîÿùèå èç óïîìÿíóòûõ ãðàôîâ, òàêæå ìîãóò áûòü èñïîëüçîâàíû, ïî-
ñêîëüêó îíè äîïóñêàþò ðàçâåðòûâàíèå äî îäíîóðîâíåâîé ìîäåëè.
Ñëåäóåò áîëüøå âíèìàíèÿ óäåëÿòü îäíîðîäíîìó ÃÑÏÄ, äëÿ êîòîðîãî
õàðàêòåðíû ïðîñòîé àíàëèç, âîçìîæíîñòü ýêâèâàëåíòíîãî ïðåîáðàçîâàíèÿ
â íåãî äðóãèõ òèïîâ ÃÑÏÄ. Èçâåñòíûé ïîäõîä îòîáðàæåíèÿ ðåãóëÿðíûõ
ÃÇÄ, â òîì ÷èñëå ÃÇÄ ñèñòîëè÷åñêèõ àëãîðèòìîâ, ìîæíî çàìåíèòü îòîáðà-
æåíèåì ÃÑÏÄ, êîòîðûé ÿâëÿåòñÿ ýôôåêòèâíîé ôîðìîé ïðåäñòàâëåíèÿ
òàêèõ ÃÇÄ. Äèíàìè÷åñêèå ãðàôû ïîòîêîâ äàííûõ, êàê è ñåòè Ïåòðè, ìîãóò
ýôôåêòèâíî âíåäðÿòüñÿ òîëüêî â ÂÑ ñ ïðîãðàììíîé ðåàëèçàöèåé àëãîðèòìîâ,
òàê êàê äëÿ íèõ òðåáóåòñÿ äèíàìè÷åñêîå ñîñòàâëåíèå ðàñïèñàíèÿ, êîòîðîå
ìîæåò îêàçàòüñÿ áåçóñïåøíûì âñëåäñòâèå âîçìîæíûõ áëîêèðîâîê.
Ïðèìåíåíèå ÃÑÏÄ äëÿ ñèíòåçà êîíâåéåðíûõ ÂÑ. Êîíâåéåðíàÿ ÂÑ
ïðåäñòàâëÿåò ñîáîé ìíîãîñòóïåí÷àòûé àïïàðàòíûé âû÷èñëèòåëü, îáðàáà-
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 85
Ìîäåëü Ðàñïèñàíèå
Ñèíõðîííîñòü
ìîäåëè
Ôóíêöèÿ çàïóñêà
àêòîðà
Àíàëèòè÷åñêàÿ
ïðîâåðêà
áëîêèðîâîê
Ñåòü îáðàáîòêè
ïîòîêîâ äàííûõ
Äèíàìè÷åñêîå Àñèíõðîííàÿ Íàáîð ïðàâèë Ïîèñê íåïîä-
âèæíîé òî÷êè
îòîáðàæåíèÿ
Ñåòü Êàíà " " Áëîêèðîâêà ÷òåíèÿ Òî æå
Ãðàô Êàðïà è Ìèëëåðà " " Wk � Òk
Ðåøåíèå çàäà-
÷è ëèíåéíîãî
ïðîãðàììèðî-
âàíèÿ
Öåëî÷èñëåííûé ÃÏÄ " "
Wk = Òk äëÿ ñòà-
òè÷åñêèõ àêòîðîâ,
case — äëÿ äèíà-
ìè÷åñêèõ
Ðåøåíèå Ãr = 0
Êâàçèñòàòè÷åñêèé ÃÏÄ Êâàçèñòàòè÷åñêîå " Òî æå Òî æå
Íåîäíîðîäíûé ÃÑÏÄ Ñòàòè÷åñêîå
Àêòîðû —
àñèíõðîííûå,
ïîòîêè —
ñèíõðîííûå
Wk = Òk "
Îäíîðîäíûé ÃÑÏÄ " Òî æå Òî æå Íå òðåáóåòñÿ
Ñèñòîëè÷åñêèé
ïðîöåññîð
" Ñèíõðîííàÿ Ïî ñèíõðîñèãíàëó Íå òðåáóåòñÿ
òûâàþùèé ïîòîêè äàííûõ. Åãî ñòðóêòóðà ìîæåò áûòü ïîëó÷åíà îòîáðà-
æåíèåì ÃÑÏÄ. Âûøå áûëî óïîìÿíóòî, êàê êîíâåéåðíàÿ ÂÑ ïîëó÷àåòñÿ
åäèíè÷íûì îòîáðàæåíèåì ñâåðíóòîãî ÃÑÏÄ.  [35] ïðåäëîæåíî ïðåä-
ñòàâëÿòü îäíîðîäíûé ÃÑÏÄ â ìíîãîìåðíîì ïðîñòðàíñòâå. Ýòî äàëî âîç-
ìîæíîñòü öåëåíàïðàâëåííî èñêàòü êàê ñòðóêòóðó ÂÑ, òàê è ðàñïèñàíèå
âûïîëíåíèÿ àëãîðèòìà â íåé. Â [36, 37] ýòîò ïîäõîä óñîâåðøåíñòâîâàí ñ
öåëüþ ìèíèìèçàöèè àïïàðàòíûõ çàòðàò ÏËÈÑ, â êîòîðîé ðåàëèçóåòñÿ
êîíâåéåðíàÿ ÂÑ.
Äèíàìè÷åñêèé ãðàô ïîòîêîâ äàííûõ ñ ýôôåêòèâíûì ïîâåäåíèåì îòîá-
ðàæàåòñÿ â êîíâåéåðíóþ ÂÑ ìåòîäîì, ïðåäëîæåííûì â [37]. Ýòîò ìåòîä
äàåò âîçìîæíîñòü ôîðìàëüíî îòîáðàæàòü àëãîðèòìû ñ îïåðàòîðàìè óïðàâ-
ëåíèÿ â ñòðóêòóðó êîíâåéåðíûõ ÂÑ ñ çàäàííûì ïåðèîäîì âû÷èñëåíèé,
èìåþùèõ ìèíèìèçèðîâàííûå àïïàðàòíûå çàòðàòû è âûñîêóþ òàêòîâóþ
÷àñòîòó. Ïîñêîëüêó ðåçóëüòàòîì îòîáðàæåíèÿ ÿâëÿåòñÿ îïèñàíèå ÂÑ íà
ÿçûêå VHDL, ìåòîä äàåò âîçìîæíîñòü íå ñòðîèòü ñîáñòâåííî ñòðóêòóðó ÂÑ
è ðàñïèñàíèå âûïîëíåíèÿ àëãîðèòìà, à ïåðåàäðåñîâàòü ýòî çàäàíèå êîì-
ïèëÿòîðó-ñèíòåçàòîðó ïðîåêòà äëÿ ÏËÈÑ.
Âûâîäû. Ãðàô ïîòîêîâ äàííûõ ïðåäñòàâëÿåò ñîáîé åñòåñòâåííóþ ìî-
äåëü äëÿ çàäàíèÿ àëãîðèòìîâ îáðàáîòêè òàêèõ ïîòîêîâ. Äèíàìè÷åñêèå
ÃÏÄ èìåþò øèðîêèå âîçìîæíîñòè äëÿ çàäàíèÿ àëãîðèòìîâ, íî èõ àíàëèç
óñëîæíåí è â íèõ ìîãóò ïðîèñõîäèòü áëîêèðîâêè. Ïîýòîìó îíè èñïîëü-
çóþòñÿ â îñíîâíîì â ñèñòåìàõ ñ äèíàìè÷åñêèì ðàñïèñàíèåì è íå ïðèñïî-
ñîáëåíû äëÿ ñèíòåçà êîíâåéåðíûõ ÂÑ.
Êîíâåéåðíûå ÂÑ ñëåäóåò ïðîåêòèðîâàòü îòîáðàæåíèåì ÃÑÏÄ èëè
ÃÏÄ ñ ýôôåêòèâíûì ïîâåäåíèåì è êâàçèñòàòè÷åñêèõ ÃÏÄ, èìåþùèõ ðÿä
ñâîéñòâ, òàêèõ æå, êàê ó ÃÑÏÄ. Ìåíüøàÿ âûðàçèòåëüíîñòü è áîëüøàÿ
òðóäîåìêîñòü ïðåäñòàâëåíèÿ àëãîðèòìà íà ìîäåëè îäíîðîäíîãî ÃÑÏÄ
êîìïåíñèðóåòñÿ òåì, ÷òî ïðè ïðåäñòàâëåíèè òàêîãî ÃÑÏÄ â ìíîãîìåðíîì
ïðîñòðàíñòâå åãî îòîáðàæåíèå â êîíâåéåðíóþ ñòðóêòóðó âûïîëíÿåòñÿ
ôîðìàëüíî ñ ïîëó÷åíèåì ìèíèìèçèðîâàííûõ àïïàðàòíûõ çàòðàò.
Properties of various computational models and recommendations are proposed for the selection
of such a model which is fitted for the pipeline computer designing.
1. Ìèíñêèé Ì. Âû÷èñëåíèÿ è àâòîìàòû. — Ì. : Ìèð. — 1971. — 264 ñ.
2. Berry G. Real Time Programming: Special Purpose or General Purpose Languages // Infor-
mation Processing / G. Ritter, Ed. Elsevier Science Publishers B. V. (North Holland) — 1989. —
89. — Ð. 11—17.
3. Lee E. A. Embedded Software //Advances in Computers / M. Zelkowitz. Åd. — London :
Academic Press, 2002. — 56. — 29 p.
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
86 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
4. Ñåðãèåíêî À. Ì. 5,5 äåñÿòèëåòèé öèôðîâîé îáðàáîòêè ñèãíàëîâ // Argñ&Argv. —2006. —
¹ 1. — Ñ. 19—25.
5. Lee E. A. The Problem with Threads // IEEE Computer. — 2006. — 39, ¹ 5. — Ð. 33—42.
6. Êîòîâ Â. Å. Ââåäåíèå â òåîðèþ ñõåì ïðîãðàìì. — Íîâîñèáèðñê : Íàóêà, 1978. — 258 ñ.
7. Ïåòåðñîí Äæ. Òåîðèÿ ñåòåé Ïåòðè è ìîäåëèðîâàíèå ñèñòåì. — Ì. : Ìèð,1984. — 264 ñ.
8. Êîòîâ Â.Å. Ñåòè Ïåòðè. — Ì. : Íàóêà, 1984. — 160 ñ.
9. Maciel P., Barros E., Rosenstiel W. A Petri Net Model for Hardware/Software Codesign //
Design Automation for Embedded Systems. — 1999. — ¹ 4. — P. 243—310.
10. Eles p., Kuchinski K., Peng Z. System Synthesis with VHDL. — Kluwer Academic Pub. —
1998. — 370 p.
11. À÷àñîâà Ñ. Ì., Áàíäìàí Î. Ë. Êîððåêòíîñòü ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ ïðîöåññîâ /
Îòâ. ðåä. Í.Í. Ìèðåíêîâ. — Íîâîñèáèðñê : Íàóêà, Ñèá. îòä-íèå, ÂÖ. — 1990. — 252 ñ.
12. Lin B. Efficient Compilation of Process-based Concurrent Programs without Run-time
Scheduling // Proc. of Design, Automation, and Test in Europe (DATE). — Paris. —
1998. — Ð. 211 — 217.
13. Âàëüêîâñêèé Â. À., Êîòîâ Â. Å., Ìèêëîøêî É. è äð. Àëãîðèòìû, ìàòåìàòè÷åñêîå
îáåñïå÷åíèå è àðõèòåêòóðà ìíîãîïðîöåññîðíûõ âû÷èñëèòåëüíûõ ñèñòåì. — Ì. :
Íàóêà, — 1982. — 340 ñ.
14. Ñèñòåìû ïàðàëëåëüíîé îáðàáîòêè /ïîä ðåä. Ä. Èâåíñà, — Ì. : Ìèð. — 1985. — 413 ñ.
15. Edwards S., Lavagno L., Lee E. A., Sangiovanny-Vincentelli A. Design of Embedded Sys-
tems: Formal Models, Validation and Synthesis //Proc. îf the IEEE. —1997. — 85, ¹ 3. —
Ð. 366—390.
16. Ðàî Ñ. K., Kàéëàò T. Ðåãóëÿðíûå èòåðàòèâíûå àëãîðèòìû è èõ ðåàëèçàöèÿ â ïðîöåñ-
ñîðíûõ ìàòðèöàõ // ÒÈÈÝÐ. — 1988. — 76, ¹ 3. — C. 58—69.
17. Âîåâîäèí Â. Â. Ìàòåìàòè÷åñêèå ìîäåëè è ìåòîäû â ïàðàëëåëüíûõ ïðîöåññàõ. — Ì :
Íàóêà, 1986. — 296 ñ.
18. Ãîëüäåíáåðã Ë. Ì. è äð. Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ: Ñïðàâî÷íèê. — Ì. : Ðàäèî è
ñâÿçü, 1985. — 312 ñ.
19. Ñåðãèåíêî À. Á. Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ (2-å èçä.). — ÑÏá. : Ïèòåð, 2006. — 751 ñ.
20. Âàéäüíàòõàí Ï. Ï. Öèôðîâûå ôèëüòðû, áëîêè ôèëüòðîâ è ïîëèôàçíûå öåïè ñ ìíîãî-
÷àñòîòíîé äèñêðåòèçàöèåé. Ìåòîäè÷åñêèé îáçîð // ÒÈÈÝÐ, — 1990. — 78, ¹ 3. —
Ñ. 77—120.
21. Leå E. A., Neuendorffer S. Concurrent Models of Computation for Embedded Software //IEE
Proc. Comput. Digit. Tech. — 2005. — 152, ¹ 2. — Ð. 239—250.
22. Îïïåíãåéì À. Â. Øàôåð Ð. Â. Öèôðîâàÿ îáðàáîòêà ñèãíàëîâ. — Ì. : Ñâÿçü, 1979. —
416 ñ.
23. Ñåðãèåíêî À. Ì. VHDL äëÿ ïðîåêòèðîâàíèÿ âû÷èñëèòåëüíûõ óñòðîéñòâ. — Êèåâ :
Äèàñîôò, 2003. — 200 ñ.
24. Bilsen G., Engels M., Lauwereins R., Peperstraete J. Cyclo-static Dataflow //IEEE Trans. on
Signal Processing. — 1996. — 44, ¹ 2. — Ð. 397—408.
25. Ñåðãèåíêî À. Ì. Îñîáåííîñòè VHDL êàê ÿçûêà ïàðàëëåëüíîãî ïðîãðàììèðîâàíèÿ //
Ýëåêòðîí. ìîäåëèðîâàíèå. — 2003. — 25, ¹ 3. — Ñ. 115—123.
26. Bhattacharya B., Bhattacharyya S. S. Parameterized Dataflow Modeling for DSP Systems//
IEEE Trans. on Signal Processing. — 2001. — 49, ¹ 10. — Ð. 2408—2421.
27. Ko D., Bhattacharyya S. S. Modeling of Block-based DSP Systems. // Proc. of the IEEE
Workshop on Signal Proc. Systems. Seoul, Korea. —2003. —August. —Ð. 381—386.
28. Parhi K. K., Wang C. Y., Brown A. P. Synthesis of Control Circuits in Folded Pipelined DSP
Architectures // IEEE J. Solid-St. Circ. — 1992. — 27. — Ð. 29 —43.
Àëãîðèòìè÷åñêèå ìîäåëè îáðàáîòêè ïîòîêîâ äàííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2008. Ò. 30. ¹ 6 87
29. Ïîñïåëîâ Ä. À. Ââåäåíèå â òåîðèþ âû÷èñëèòåëüíûõ ñèñòåì. — Ì. : Ñîâ.ðàäèî, 1972. —
280 ñ.
30. Ñèð Æ. -Ê. Ìåòîä ïîòîêà îïåðàíäîâ â ìîíîãîïðîöåññîðíûõ ñèñòåìàõ òèïà ̲ÌD //
Ñèñòåìû ïàðàëëåëüíîé îáðàáîòêè / Ïîä ðåä. Ä.Èâåíñà. — Ì. : Ìèð, 1985. — 413 ñ.
31. Àõî À., Ñåòè Ð., Óëüìàí Äæ. Êîìïèëÿòîðû: ïðèíöèïû, òåõíîëîãèè, èíñòðóìåíòû. —
Ì.: Èçä. äîì «Âèëüÿìñ», 2003. — 768ñ.
32. Åâñòèãíååâ Â. À. Ïðèìåíåíèå òåîðèè ãðàôîâ â ïðîãðàììèðîâàíèè. — Ì. : Íàóêà,
1985. — 350 ñ.
33. Êóí Ñ. Ìàòðè÷íûå ïðîöåññîðû íà ÑÁÈÑ. — Ì. : Ìèð, 1991. — 672 ñ.
34. Êàíåâñêèé Þ. Ñ. Ñèñòîëè÷åñêèå ïðîöåññîðû. — Êèåâ : Òåõí³êà, 1991. — 172 ñ.
35. Êàíåâñêèé Þ. Ñ., Îâðàìåíêî Ñ. Ã., Ñåðãèåíêî À. Ì. Îòîáðàæåíèå ðåãóëÿðíûõ àëãîðèò-
ìîâ â ñòðóêòóðû ñïåöèàëèçèðîâàííûõ ïðîöåññîðîâ // Ýëåêòðîí. ìîäåëèðîâàíèå. —
2002. — 24, ¹ 2. — Ñ. 46—59.
36. Ñèìîíåíêî Â.Ï., Ñåðãèåíêî À.Ì. Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ â ïðî-
ãðàììèðóåìûå ëîãè÷åñêèå èíòåãðàëüíûå ñõåìû // Òàì æå. — 2007. — 29, ¹ 2. —
Ñ. 49—61.
37. Ñåðãèåíêî À.Ì. Ñèíòåç ñòðóêòóð äëÿ âûïîëíåíèÿ ïåðèîäè÷åñêèõ àëãîðèòìîâ ñ îïåðà-
òîðàìè óïðàâëåíèÿ // ³ñòí. Íàö³îíàëüíîãî òåõíè÷íîãî óí³âåðñèòåòó Óêðà¿íè «Êϲ». Ñåð.
²íôîðìàòèêà, óïðàâë³ííÿ ³ îá÷èñëþâàëüíà òåõí³êà. — 2008. — ¹ 47. — Ñ. 62— 68.
Ïîñòóïèëà 15.07.08
CÈÌÎÍÅÍÊÎ Âàëåðèé Ïàâëîâè÷, ä-ð òåõí. íàóê, ïðîô. Íàöèîíàëüíîãî òåõíè÷åñêîãî óíèâåð-
ñèòåòà Óêðàèíû «ÊÏÈ», êîòîðûé îêîí÷èë â 1965 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé —
îðãàíèçàöèÿ âû÷èñëèòåëüíûõ ïðîöåññîâ â âû÷èñëèòåëüíûõ ñèñòåìàõ.
ÑÅÐÃÈÅÍÊÎ Àíàòîëèé Ìèõàéëîâè÷, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð. Íàöèîíàëüíîãî òåõíè-
÷åñêîãî óíèâåðñèòåòà Óêðàèíû «ÊÏÈ», êîòîðûé îêîí÷èë â 1981 ã. Îáëàñòü íàó÷íûõ èññëåäî-
âàíèé — îòîáðàæåíèå àëãîðèòìîâ â ñòðóêòóðû âû÷èñëèòåëüíûõ ñðåäñòâ, öèôðîâàÿ îáðà-
áîòêà ñèãíàëîâ.
Â. Ï. Ñèìîíåíêî, À. Ì. Ñåðãèåíêî
88 ISSN 0204–3572. Electronic Modeling. 2008. V. 30. ¹ 6
|