Отображение периодических алгоритмов в программируемые логические интегральные схемы
Рассмотрен метод отображения периодических алгоритмов, представленных графом синхронных потоков данных, в конвейерный вычислитель, реализованный в программируемой логической интегральной схеме. Метод заключается в размещении графа алгоритма в многомерном индексном пространстве и отображении его в по...
Збережено в:
| Дата: | 2007 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2007
|
| Назва видання: | Электронное моделирование |
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101668 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Отображение периодических алгоритмов в программируемые логические интегральные схемы / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 49-61. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101668 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1016682025-02-09T20:07:11Z Отображение периодических алгоритмов в программируемые логические интегральные схемы Mapping of Periodical Algorithms Into Programmed Logic Integral Circuits Сергиенко, А.М. Симоненко, В.П. Вычислительные процессы и системы Рассмотрен метод отображения периодических алгоритмов, представленных графом синхронных потоков данных, в конвейерный вычислитель, реализованный в программируемой логической интегральной схеме. Метод заключается в размещении графа алгоритма в многомерном индексном пространстве и отображении его в подпространства структур и времени. Ограничения на процесс отображения позволяют минимизировать как тактовый интервал, так и аппаратные затраты, включая мультиплексоры. Розглянуто метод відображення періодичних алгоритмів, зображених графом синхронних потоків даних, в конвейєрний обчислювач, реалізований у програмованій логічній інтегральній схемі. Метод полягає в розміщенні графа алгоритму у багатовимірному індексному просторі та його відображенні у підпростори структур і часу. Обмеження на процес відображення дають змогу мінімізувати як тактовий інтервал, так і апаратні витрати, включаючи мультиплексори. A method of mapping periodical algorithms into pipeline processor based on FPGA is considered. The algorithm is represented by the synchronous dataflow graph. The method lies in placing the algorithm graph in multidimensional index space and then in its mapping into subspaces of structures and time. The limitations to the mapping process allow to minimize both the clock cycle and hardware volume including multiplexers. 2007 Article Отображение периодических алгоритмов в программируемые логические интегральные схемы / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 49-61. — Бібліогр.: 8 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101668 681.3 ru Электронное моделирование application/pdf Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| 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 |
2007 |
| topic_facet |
Вычислительные процессы и системы |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101668 |
| citation_txt |
Отображение периодических алгоритмов в программируемые логические интегральные схемы / А.М. Сергиенко, В.П. Симоненко // Электронное моделирование. — 2007. — Т. 29, № 2. — С. 49-61. — Бібліогр.: 8 назв. — рос. |
| series |
Электронное моделирование |
| work_keys_str_mv |
AT sergienkoam otobraženieperiodičeskihalgoritmovvprogrammiruemyelogičeskieintegralʹnyeshemy AT simonenkovp otobraženieperiodičeskihalgoritmovvprogrammiruemyelogičeskieintegralʹnyeshemy AT sergienkoam mappingofperiodicalalgorithmsintoprogrammedlogicintegralcircuits AT simonenkovp mappingofperiodicalalgorithmsintoprogrammedlogicintegralcircuits |
| first_indexed |
2025-11-30T09:40:02Z |
| last_indexed |
2025-11-30T09:40:02Z |
| _version_ |
1850207740663693312 |
| fulltext |
ÓÄÊ 681.3
À. Ì. Ñåðãèåíêî, êàíä. òåõí. íàóê,
Â. Ï. Ñèìîíåíêî, ä-ð òåõí.íàóê
Íàöèîíàëüíûé òåõíè÷åñêèé óíèâåðñèòåò Óêðàèíû «ÊÏÈ»
(Óêðàèíà, 03056, Êèåâ, ïð-ò Ïîáåäû, 37,
òåë.: (044) 4549337, E-mail: aser@comsys.ntu-kpi.kiev.ua)
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
â ïðîãðàììèðóåìûå ëîãè÷åñêèå èíòåãðàëüíûå ñõåìû
Ðàññìîòðåí ìåòîä îòîáðàæåíèÿ ïåðèîäè÷åñêèõ àëãîðèòìîâ, ïðåäñòàâëåííûõ ãðàôîì ñèíõ-
ðîííûõ ïîòîêîâ äàííûõ, â êîíâåéåðíûé âû÷èñëèòåëü, ðåàëèçîâàííûé â ïðîãðàììèðóåìîé
ëîãè÷åñêîé èíòåãðàëüíîé ñõåìå. Ìåòîä çàêëþ÷àåòñÿ â ðàçìåùåíèè ãðàôà àëãîðèòìà â ìíî-
ãîìåðíîì èíäåêñíîì ïðîñòðàíñòâå è îòîáðàæåíèè åãî â ïîäïðîñòðàíñòâà ñòðóêòóð è âðåìåíè.
Îãðàíè÷åíèÿ íà ïðîöåññ îòîáðàæåíèÿ ïîçâîëÿþò ìèíèìèçèðîâàòü êàê òàêòîâûé èíòåðâàë,
òàê è àïïàðàòíûå çàòðàòû, âêëþ÷àÿ ìóëüòèïëåêñîðû.
Ðîçãëÿíóòî ìåòîä â³äîáðàæåííÿ ïåð³îäè÷íèõ àëãîðèòì³â, çîáðàæåíèõ ãðàôîì ñèíõðîííèõ
ïîòîê³â äàíèõ, â êîíâåéºðíèé îá÷èñëþâà÷, ðåàë³çîâàíèé ó ïðîãðàìîâàí³é ëîã³÷í³é ³íòå-
ãðàëüí³é ñõåì³. Ìåòîä ïîëÿãຠâ ðîçì³ùåíí³ ãðàôà àëãîðèòìó ó áàãàòîâèì³ðíîìó ³íäåêñ-
íîìó ïðîñòîð³ òà éîãî â³äîáðàæåíí³ ó ï³äïðîñòîðè ñòðóêòóð ³ ÷àñó. Îáìåæåííÿ íà ïðîöåñ
â³äîáðàæåííÿ äàþòü çìîãó ì³í³ì³çóâàòè ÿê òàêòîâèé ³íòåðâàë, òàê ³ àïàðàòí³ âèòðàòè,
âêëþ÷àþ÷è ìóëüòèïëåêñîðè.
Ê ë þ ÷ å â û å ñ ë î â à: VHDL, ÏËÈÑ, FPGA, SDF, îòîáðàæåíèå àëãîðèòìà,
ñòðóêòóðíûé ñèíòåç.
Ñîâðåìåííûå ïðîãðàììèðóåìûå ëîãè÷åñêèå èíòåãðàëüíûå ñõåìû
(ÏËÈÑ) èìåþò åìêîñòè, ñîñòàâëÿþùèå ìèëëèîíû âåíòèëåé è ñîòíè àïïà-
ðàòíûõ óìíîæèòåëåé, è ðàáîòàþò ñ ÷àñòîòàìè â ñîòíè ìåãàãåðö. Ïîýòîìó èõ
çàñëóæåííî ñ÷èòàþò ïåðñïåêòèâíîé ýëåìåíòíîé áàçîé äëÿ âûñîêîïðîèçâî-
äèòåëüíûõ ðàñ÷åòîâ, îáðàáîòêè äàííûõ è ìîäåëèðîâàíèÿ, à òàêæå öèôðîâîé
îáðàáîòêè ñèãíàëîâ (ÖÎÑ). Îäíàêî øèðîêîìó âíåäðåíèþ ÏËÈÑ ïðåïÿòñò-
âóþò òðóäíîñòè, ñâÿçàííûå ñ îòîáðàæåíèåì â íèõ àëãîðèòìîâ. Ðàçðàáîòêà
ñïåöâû÷èñëèòåëÿ íà áàçå ÏËÈÑ îñòàåòñÿ äîñòàòî÷íî òðóäîåìêîé ðàáîòîé è
òðåáóåò âûñîêîé êâàëèôèêàöèè.
Ïðè âûñîêîóðîâíåâîì (ñèñòåìíîì) ñèíòåçå âû÷èñëèòåëüíûõ óñòðîéñòâ
(ÂÓ) ïåðèîäè÷åñêèé àëãîðèòì, òàêîé êàê àëãîðèòì ÖÎÑ, îáû÷íî ïðåä-
ñòàâëÿþò ãðàôîì ñèíõðîííûõ ïîòîêîâ äàííûõ (ÃÑÏÄ). Â íåì âåðøèíû —
àêòîðû — ïðåäñòàâëÿþò ñîáîé îïåðàòîðû, à äóãè — ïåðåäà÷è ïåðåìåííûõ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 49
�������� �
��
�
�� ���������� ��
ìåæäó àêòîðàìè ñ çàäåðæêîé íà çàäàííîå ÷èñëî öèêëîâ. Ïðè÷åì êàæäûé
àêòîð â òå÷åíèå öèêëà ãåíåðèðóåò è èñïîëüçóåò ïåðåìåííûå, ÷èñëî êîòî-
ðûõ îñòàåòñÿ íåèçìåííûì îò öèêëà ê öèêëó [1,2].
Ñèíòåç ÂÓ îáû÷íî âûïîëíÿåòñÿ â òðè ýòàïà: 1) ôîðìèðîâàíèå ìíîæåñòâà
àïïàðàòíûõ ðåñóðñîâ; 2) ñîñòàâëåíèå ðàñïèñàíèÿ âûïîëíåíèÿ àêòîðîâ; 3)
íàçíà÷åíèå àêòîðîâ íà ðåñóðñû.  ìåòîäàõ ñèíòåçà èñïîëüçóåòñÿ ðàçëè÷íûé
ïîðÿäîê ïîäýòàïîâ: íàçíà÷åíèå ïåðåìåííûõ ðåãèñòðàì èëè øèíàì, íàçíà-
÷åíèå îïåðàöèé ïðîöåññîðíûì ýëåìåíòàì (ÏÝ), ñîñòàâëåíèå ðàñïèñàíèÿ âû-
ïîëíåíèÿ àêòîðîâ, ïåðåñûëîê ïåðåìåííûõ, à òàêæå ðàçëè÷íûå àëãîðèòìû
ðåàëèçàöèè ýòèõ ïîäýòàïîâ. Íàèáîëåå îòâåòñòâåííûé è ñëîæíûé ýòàï — ñîñ-
òàâëåíèå ðàñïèñàíèÿ, òàê êàê îò íåãî çàâèñèò ïðîèçâîäèòåëüíîñòü ÂÓ è
çàãðóæåííîñòü åãî ðåñóðñîâ. Ýòîò ýòàï ïðåäñòàâëÿåò ñîáîé ðåøåíèå ñëîæíîé
êîìáèíàòîðíîé çàäà÷è.
ÃÑÏÄ ÿâëÿåòñÿ ãðàôîì îäíîé èòåðàöèè (ïåðèîäà) ïåðèîäè÷åñêîãî
àëãîðèòìà. ÃÑÏÄ áûâàþò êàê öèêëè÷åñêèìè, òàê è àöèêëè÷åñêèìè. Äóãè,
çàìûêàþùèå àöèêëè÷åñêèé ãðàô â öèêëè÷åñêèé, îïèñûâàþòñÿ ìåæèòåðà-
öèîííûìè çàâèñèìîñòÿìè. Ïîëîæèòåëüíîå ÷èñëî, íàãðóæàþùåå çàìûêàþ-
ùóþ äóãó, ðàâíî äèñòàíöèè ïåðåäà÷è îïåðàíäà è èçìåðÿåòñÿ â èòåðàöèÿõ.
Ñîñòàâëåíèå ðàñïèñàíèÿ äëÿ öèêëè÷åñêèõ ÃÑÏÄ — íàèáîëåå ñëîæíàÿ çà-
äà÷à. Ðàñïðîñòðàíåííûì ïîäõîäîì ïðè ýòîì ÿâëÿåòñÿ ïîèñê ðàñïèñàíèÿ ïå-
ðèîäà àëãîðèòìà ñ ïëàíèðîâàíèåì âû÷èñëåíèé äëÿ åãî àöèêëè÷åñêîé ÷àñòè.
Îáû÷íî èñïîëüçóþò àëãîðèòìû ñïèñî÷íîãî ïëàíèðîâàíèÿ, ñèëîâîãî ïëàíè-
ðîâàíèÿ, ðàñêðàñêè ãðàôà, ìåòîä ïëàíèðîâàíèÿ ñ âûðàâíèâàíèåì àêòîðîâ ïî
ëåâîìó êðàþ ïðîñòðàíñòâà ðåñóðñû — âðåìÿ (left edge scheduling). Îäíàêî
ïðÿìîå èõ ïðèìåíåíèå ïðèâîäèò ê íèçêîé çàãðóæåííîñòè ÂÓ â íà÷àëå è â
êîíöå öèêëà. Äëÿ ó÷åòà öèêëè÷íîñòè àëãîðèòìà àíàëèçèðóþò ãðàô êîíô-
ëèêòîâ ðåñóðñîâ è îïåðàöèé, à òàêæå ãðàô èíòåðâàëîâ ñóùåñòâîâàíèÿ
ïåðåìåííûõ [2, 3].
Îïòèìàëüíîñòü ñèíòåçèðîâàííîãî ÂÓ çàâèñèò îò âñåõ ýòàïîâ ñèíòåçà,
êîòîðûå, êàê ïðàâèëî, âûïîëíÿþòñÿ íåçàâèñèìî îäèí îò äðóãîãî. Êàæäûé
èç íèõ èìååò ëîêàëüíóþ öåëü, êîòîðàÿ ÷àñòî ïðîòèâîðå÷èò öåëè äðóãèõ
ýòàïîâ. Òàê, ìèíèìèçàöèÿ ðåñóðñîâ ïðè ôîðìèðîâàíèè èõ ìíîæåñòâà íåèç-
áåæíî ïðèâîäèò ê óâåëè÷åíèþ äëèòåëüíîñòè ðàñïèñàíèÿ. Ïîýòîìó áîëü-
øèíñòâî ìåòîäîâ ñèñòåìíîãî ñèíòåçà íå îáåñïå÷èâàåò âûñîêîå êà÷åñòâî
ÂÑ, ðåàëèçóþùèõ ñëîæíûå àëãîðèòìû.
 ïîñëåäíåå âðåìÿ ïîëó÷àþò ðàñïðîñòðàíåíèå òàêèå ïðîãðàììíûå
ñðåäñòâà, êàê AccelDSP è System Generator, ïîìîãàþùèå ïåðåâåñòè â ïðî-
øèâêó ÏËÈÑ ïåðèîäè÷åñêèé àëãîðèòì, ïðåäñòàâëåííûé â âèäå ÃÑÏÄ ñ
ïîìîùüþ ñðåäû Matlab Simulink [4]. Îäíàêî ýòè ñðåäñòâà ýôôåêòèâíû
òîëüêî äëÿ àëãîðèòìîâ ñ àöèêëè÷åñêèìè ÃÑÏÄ, íàïðèìåð äëÿ ôèëüòðîâ ñ
À. Ì. Ñåðãèåíêî, Â. Ï. Ñèìîíåíêî
50 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
êîíå÷íîé èìïóëüñíîé õðàêòåðèñòèêîé èëè ïðè åäèíè÷íîì îòîáðàæåíèè
ÃÑÏÄ, èëè äëÿ àëãîðèòìîâ, îïåðàòîðû êîòîðûõ ñîîòâåòñòâóþò êðóïíûì
áèáëèîòå÷íûì êîìïîíåíòàì.
 ðàáîòàõ [5, 6] ïðåäëîæåíû ìåòîäû îòîáðàæåíèÿ àëãîðèòìîâ, ïðåä-
ñòàâëåííûõ ÃÑÏÄ, â ñòðóêòóðû ïàðàëëåëüíûõ ÂÓ. Ìåòîäû îñíîâàíû íà
ðàçìåùåíèè ãðàôà àëãîðèòìà â ìíîãîìåðíîì èíäåêñíîì ïðîñòðàíñòâå è
îòîáðàæåíèè åãî â ïîäïðîñòðàíñòâà ñòðóêòóð è âðåìåíè. Â ìåòîäàõ ñòðóê-
òóðíîãî ïðîåêòèðîâàíèÿ öèôðîâûõ ôèëüòðîâ (ÖÔ), îïèñàííûõ â [6, 7],
òàêæå èñïîëüçóåòñÿ ýòîò ïîäõîä. Ïðè òàêîì ïîäõîäå ýòàïû ñèíòåçà âûïîë-
íÿþòñÿ îäíîâðåìåííî, à ÂÓ îïòèìèçèðóåòñÿ ñ óäîâëåòâîðåíèåì ïðîòèâî-
ðå÷èâûõ òðåáîâàíèé ê íåìó.  äàííîì ñëó÷àå ýòîò ïîäõîä ïðèìåíÿåòñÿ
äëÿ ñèíòåçà ÂÓ, ðåàëèçóþùåãî ïåðèîäè÷åñêèå àëãîðèòìû â ÏËÈÑ.
Îòîáðàæåíèå ÃÑÏÄ â ïîäïðîñòðàíñòâà ñòðóêòóð è âðåìåíè. Èñõîä-
íûìè äàííûìè äëÿ ïðîåêòèðîâàíèÿ ÂÓ ÿâëÿåòñÿ ïåðèîäè÷åñêèé àëãîðèòì,
ïðåäñòàâëåííûé ÃÑÏÄ, è êðèòåðèè îïòèìèçàöèè. Ðàññìîòðèì ÃÑÏÄ, â êîòî-
ðûõ ÷èñëî ãðóïï ïåðåìåííûõ, ïîòðåáëÿåìûõ àêòîðîì, ðàâíî ÷èñëó ðåçóëü-
òàòîâ, âûäàâàåìûõ ýòèì æå àêòîðîì â òå÷åíèå îäíîãî öèêëà. Ýòî îçíà÷àåò,
÷òî ÏÝ áóäóò ðàáîòàòü â îäèíàêîâîì òåìïå, êàê, íàïðèìåð, â êîíâåéåðå. Ê
ïîäêëàññó òàêèõ àëãîðèòìîâ îòíîñÿòñÿ àëãîðèòìû ÖÔ ñ ïîñòîÿííîé ÷àñ-
òîòîé äèñêðåòèçàöèè. Ïðåäïîëîæèì, ÷òî ÂÓ ñîñòîèò èç ïðîñòûõ ÏÝ,
ñâÿçàííûõ ìåæäó ñîáîé ñîãëàñíî ãðàôó ñòðóêòóðû ÂÓ. ÏÝ âêëþ÷àåò â
ñåáÿ àðèôìåòèêî-ëîãè÷åñêîå óñòðîéñòâî (ÀËÓ) îïðåäåëåííîãî òèïà (óìíî-
æèòåëü, ñóììàòîð) ñ ðåãèñòðîì ðåçóëüòàòà íà åãî âûõîäå (èëè ñ áóôåðîì
FIFO) è ìóëüòèïëåêñîðàìè âõîäíûõ äàííûõ íà åãî âõîäå. ÏÝ âûïîëíÿåò
îïåðàöèþ íàä âõîäíûìè äàííûìè ñ çàïèñüþ ðåçóëüòàòà â ðåãèñòð íå
áîëåå, ÷åì çà îäèí òàêò. Åñëè ÏÝ íå èìååò ðåãèñòðà, òî ñ÷èòàåòñÿ, ÷òî
îïåðàöèÿ âûïîëíÿåòñÿ áåç çàäåðæêè.
 êà÷åñòâå êðèòåðèÿ îïòèìèçàöèè ïðèìåì ïåðèîä âûïîëíåíèÿ
àëãîðèòìà QT = LtC è cóììàðíóþ öåíó ÏÝ ðàçëè÷íîãî òèïà Q C qS p
p
p
� � .
Çäåñü ââåäåíû ñëåäóþùèå îáîçíà÷åíèÿ: L — ÷èñëî òàêòîâ ïåðèîäà; tC —
äëèòåëüíîñòü òàêòà; Ñp — àïïàðàòíàÿ ñëîæíîñòü ÏÝ p-ãî òèïà; q p
— ÷èñëî
ÏÝ p-ãî òèïà.
Ïðè êîíâåéåðíîé îáðàáîòêå äàííûõ â ÏËÈÑ îñîáåííî âàæíî äîñ-
òèæåíèå ìèíèìàëüíîé äëèíû êðèòè÷åñêîãî ïóòè, ïîñêîëüêó â ÏËÈÑ íà
ìàðøðóòû ïðîõîæäåíèÿ ñèãíàëà ìåæäó ëîãè÷åñêèìè ýëåìåíòàìè ïðèõî-
äèòñÿ â ñðåäíåì îò 50 äî 90 % çàäåðæêè êðèòè÷åñêîãî ïóòè. Ïîýòîìó
ÏËÈÑ ïëîõî êîíêóðèðóþò ïî áûñòðîäåéñòâèþ ñ çàêàçíûìè ìèêðîñõå-
ìàìè. Ïðè îòîáðàæåíèè ÃÑÏÄ â ÏËÈÑ ñ L > 1 ê çàäåðæêå êðèòè÷åñêîãî
ïóòè íåèçáåæíî äîáàâëÿþòñÿ çàäåðæêè ìóëüòèïëåêñîðîâ. Êðîìå òîãî, â
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 51
ÏËÈÑ àïïàðàòíûå çàòðàòû ìóëüòèïëåêñîðîâ ìîãóò ñóùåñòâåííî ïðåâîñ-
õîäèòü çàòðàòû ðåãèñòðîâ è ñóììàòîðîâ. Òàê, äâóõâõîäîâûé ìóëüòèïëåê-
ñîð â ÏËÈÑ ôèðì Altera, Xilinx çàíèìàåò ñòîëüêî æå ðåñóðñîâ, êàê ñóììà-
òîð òàêîé æå ðàçðÿäíîñòè.  ÏËÈÑ ôèðìû Xilinx êîëè÷åñòâî ðåñóðñîâ,
çàíèìàåìûõ n-âõîäîâûì ìóëüòèïëåêñîðîì, ïðè n � 8ïðèáëèçèòåëüíî ïðî-
ïîðöèîíàëüíî n. Òîëüêî ïÿòè- è ñåìèâõîäîâûé ìóëüòèïëåêñîðû ðåàëè-
çóþòñÿ ñîîòâåòñòâåííî êàê øåñòè- è âîñüìèâõîäîâûé. Òàêèì îáðàçîì, ñ
ó÷åòîì ÷àñòîòû èñïîëüçîâàíèÿ ðàçëè÷íûõ ìóëüòèïëåêñîðîâ â ðåàëüíûõ
ïðîåêòàõ ñðåäíþþ ñëîæíîñòü îäíîãî âõîäà ìóëüòèïëåêñîðà ÏËÈÑ ìîæíî
îöåíèòü â 0,57 ñëîæíîñòè ðåãèñòðà èëè ÀËÓ. Ïîýòîìó ñëåäóåò ìèíè-
ìèçèðîâàòü êàê ÷èñëî ÏÝ, òàê è ÷èñëî âõîäîâ èõ ìóëüòèïëåêñîðîâ, îòðà-
æàþùåå ñëîæíîñòü ëèíèé ñâÿçè.
ÃÑÏÄ ïðåäñòàâëÿåòñÿ â òðåõìåðíîì öåëî÷èñëåííîì ïðîñòðàíñòâå â
âèäå êîíôèãóðàöèè àëãîðèòìà (ÊÀ) KG K D A� ( , , ), ãäå K — ìàòðèöà âåê-
òîðîâ-âåðøèí Ki, ñîîòâåòñòâóþùèõ îïåðàòîðàì àëãîðèòìà; D — ìàòðèöà
âåêòîðîâ-äóã Dj, ñîîòâåòñòâóþùèõ íåïîñðåäñòâåííûì èíôîðìàöèîííûì
ñâÿçÿì ìåæäó îïåðàòîðàìè; A — ìàòðèöà èíöèäåíòíîñòè ÃÑÏÄ. Â âåêòîðå-
âåðøèíå Ki = <ki,si,ti> êîîðäèíàòû ki, si, ti ñîîòâåòñòâóþò òèïó îïåðàòîðà
(íàïðèìåð, k = 1 — óìíîæåíèå), íîìåðó ïðîöåññîðíîãî ýëåìåíòà, ãäå
âûïîëíÿåòñÿ äàííûé îïåðàòîð, è òàêòó, â êîòîðîì çàïèñûâàåòñÿ â ðåãèñòð
ðåçóëüòàò ýòîãî îïåðàòîðà.
Ðàçëè÷íûì ýêâèâàëåíòíûì ñòðóêòóðíûì ðåøåíèÿì ÂÓ ñîîòâåòñòâóþò
ýêâèâàëåíòíûå ÊÀ, êîòîðûå îòëè÷àþòñÿ ëèøü ðàçíûìè ìàòðèöàìè K è D.
Ìàòðèöà K êîäèðóåò íåêîòîðîå äîïóñòèìîå ðåøåíèå, òàê êàê ìàòðèöà D
âû÷èñëÿåòñÿ èç óðàâíåíèÿ D = KÀ. Ïîèñê îïòèìàëüíîãî ñòðóêòóðíîãî
ðåøåíèÿ çàêëþ÷àåòñÿ â íàõîæäåíèè òàêîé ìàòðèöû K, êîòîðàÿ ìèíèìè-
çèðóåò çàäàííûé êðèòåðèé êà÷åñòâà. Åñëè ïðèìåíÿåòñÿ ãåíåòè÷åñêèé ìå-
òîä îïòèìèçàöèè, òî ìàòðèöà K ìîæåò áûòü èñïîëüçîâàíà â êà÷åñòâå ãåíà
ïðåäñòàâèòåëÿ ïîïóëÿöèè. Ïðè ïîèñêå ýôôåêòèâíûõ ñòðóêòóðíûõ ðåøå-
íèé íåîáõîäèìî ðóêîâîäñòâîâàòüñÿ ñëåäóþùèìè çàêîíîìåðíîñòÿìè.
ÊÀ ÿâëÿåòñÿ êîððåêòíîé, åñëè â ìàòðèöå K íåò äâóõ îäèíàêîâûõ
âåêòîðîâ:
� � �K K K Ki j i j i j, ( , ).
Ðàñïèñàíèå âûïîëíåíèÿ àëãîðèòìà êîððåêòíî, åñëè îïåðàòîðû, îòîá-
ðàæàåìûå â îäèí è òîò æå ÏÝ, âûïîëíÿþòñÿ â ðàçëè÷íûõ òàêòàõ:
� � � � �K Ki j i j i j i jk k s s t t L, ( , ) / mod .
Îäíîòèïíûå îïåðàòîðû ñëåäóåò îòîáðàæàòü â ÏÝ òîãî æå òèïà, ò. å.
K Ki j p q i j i j p qK k k p s s q K L, ( , ),
, ,
� � � � � ,
À. Ì. Ñåðãèåíêî, Â. Ï. Ñèìîíåíêî
52 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
ãäå K p q,
— ìíîæåñòâî âåêòîðîâ-âåðøèí îïåðàòîðîâ p-ãî òèïà, îòîáðà-
æàåìûõ â q-é ÏÝ p-ãî òèïà (q =1, 2, …, q p
max) [5].
Åñëè ÃÑÏÄ — öèêëè÷åñêèé, ò. å. â íåì åñòü öèêëû ìåæèòåðàöèîííîé
çàâèñèìîñòè, òî äîëæíà áûòü ðàâíà íóëþ ñóììà âåêòîðîâ-äóã Dj, âõîäÿ-
ùèõ â ëþáîé èç öèêëîâ ãðàôà. Äëÿ i-ãî öèêëà bi j j,
D �� 0, ãäå bi j,
—
ýëåìåíò i-é ñòðîêè öèêëîìàòè÷åñêîé ìàòðèöû ÃÑÏÄ. Òàêèå öèêëû ñó-
ùåñòâóþò, íàïðèìåð, â àëãîðèòìàõ ðåêóðñèâíîé ôèëüòðàöèè. Îáðàòíûå
âåêòîðû-äóãè DÂj = <0, 0, – iL> îçíà÷àþò çàäåðæêó, ðàâíóþ i öèêëîâ
(èòåðàöèé), ãäå i — ÷èñëî, íàãðóæàþùåå ñîîòâåòñòâóþùóþ çàìûêàþùóþ
äóãó â ÃÑÏÄ. Òàêèì îáðàçîì, ÊÀ ðàâíà îáúåäèíåíèþ àöèêëè÷åñêîé êîí-
ôèãóðàöèè, âûïîëíÿþùåé âû÷èñëåíèÿ îäíîé èòåðàöèè è ìíîæåñòâà
îáðàòíûõ äóã DÂj, ïðåäñòàâëÿþùèõ ìåæèòåðàöèîííóþ çàäåðæêó ïåðåìåí-
íûõ íà iL òàêòîâ. Ýòè âåêòîðû íàïðàâëåííû â ïðîòèâîïîëîæíóþ ñòîðîíó
îòíîñèòåëüíî îñè âðåìåíè ît è íàçûâàþòñÿ çàìûêàþùèìè âåêòîðàìè.
Ýôôåêòèâíàÿ ÊÀ ïîëó÷àåòñÿ â äâà ýòàïà. Íà ïåðâîì ýòàïå âåðøèíû
ÃÑÏÄ âìåñòå ñ äóãàìè ðàçìåùàþòñÿ â òðåõìåðíîì ïðîñòðàíñòâå êàê ìíî-
æåñòâà âåêòîðîâ Ki è Dj ñ ó÷åòîì âñåõ óêàçàííûõ âûøå óñëîâèé, ò.å.
ôîðìèðóåòñÿ íà÷àëüíàÿ ÊÀ. Ìèíèìèçèðóåòñÿ ÷èñëî ÏÝ â èñêîìîé ñòðóê-
òóðå âûïîëíåíèåì òðåáîâàíèÿ K Lp q,
, ò. å. ÷èñëî âåðøèí, îòîáðàæàå-
ìûõ â îäèí ÏÝ, ñòðåìèòñÿ ê L.
Íà âòîðîì ýòàïå âûïîëíÿåòñÿ óðàâíîâåøèâàíèå ÊÀ. Äëÿ ýòîãî ðàñ-
ñìàòðèâàåòñÿ àöèêëè÷åñêèé ïîäãðàô ÃÑÏÄ áåç çàìûêàþùèõ âåêòîðîâ —
äóã DÂj. Âî âñå åãî äóãè âêëþ÷àþòñÿ ïðîìåæóòî÷íûå âåðøèíû îïåðàòîðîâ
çàäåðæêè (ðåãèñòðîâ). Â ðåçóëüòèðóþùåé óðàâíîâåøåííîé ÊÀ âñå âåêòîðû-
äóãè, êðîìå çàìûêàþùèõ, èìåþò âèä D j j ja b�� �, ,1 èëè D j j ja b�� �, ,0 .
Ïðè ýòîì âåðøèíû-îïåðàòîðû îáðàçóþò ÿðóñû, ðàññòîÿíèå ìåæäó êîòî-
ðûìè ïî êîîðäèíàòå âðåìåíè t ðàâíî îäíîìó òàêòó.
Óðàâíîâåøåííàÿ ÊÀ îïòèìèçèðóåòñÿ ïóòåì âçàèìíûõ ïåðåñòàíîâîê
âåêòîðîâ-âåðøèí èç îäíîãî ÿðóñà ñ ìèíèìèçàöèåé ÷èñëà ðåãèñòðîâ è
âõîäîâ ìóëüòèïëåêñîðîâ. Ïðèìåíÿþòñÿ è äðóãèå èçâåñòíûå ñòðàòåãèè,
íàïðèìåð ðåñèíõðîíèçàöèÿ èëè àëãîðèòì ëåâîãî êðàÿ, ìèíèìèçèðóþùèå
÷èñëî ðåãèñòðîâ.
Ñòðóêòóðó ÂÓ è ðàñïèñàíèå âûïîëíåíèÿ àëãîðèòìà ìîæíî ïîëó÷èòü,
ðàñùåïèâ ÊÀ KG íà êîíôèãóðàöèþ ñòðóêòóðû (ÊÑ) KS è êîíôèãóðàöèþ
ïðåäøåñòâîâàíèÿ (ÊÏ), êîòîðûå èìåþò òó æå ìàòðèöó À, à âåêòîðû ìàò-
ðèöû KS êîîðäèíàò ÏÝ è ìàòðèöû ìîìåíòîâ ñðàáàòûâàíèÿ KT ðàâíû
êîîðäèíàòàì âåêòîðîâ ìàòðèöû K, ò. å. <ki, si> è <ti>. ÊÑ è ÊÏ ïðåä-
ñòàâëÿþò ñîáîé îòîáðàæåíèå ÊÀ â ïîäïðîñòðàíñòâà ñòðóêòóð è âðåìåíè,
êîòîðîå âûïîëíÿåòñÿ ýëåìåíòàðíûì îáðàçîì.
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 53
Ìåòîä ìèíèìèçàöèè âõîäîâ ìóëüòèïëåêñîðîâ. Ðàññìîòðèì ìåòîä
ìèíèìèçàöèè ÷èñëà ìóëüòèïëåêñîðîâ â êîíâåéåðíûõ ÂÓ, íàèáîëåå ýô-
ôåêòèâíûé äëÿ ïðîåêòîâ ÏËÈÑ. Î÷åíü ÷àñòî ÃÑÏÄ àëãîðèòìîâ èìåþò èçî-
ìîðôíûå ïîäãðàôû. Òàê, àëãîðèòìû áîëüøèõ ðåêóðñèâíûõ ôèëüòðîâ — ýòî
öåïî÷êè èç îäèíàêîâûõ ñòóïåíåé âòîðîãî ïîðÿäêà, à â ãðàôàõ íåðåêóð-
ñèâíûõ ôèëüòðîâ ìîæíî âûäåëèòü ïåðèîäè÷åñêèå ôðàãìåíòû. Äëÿ ìèíè-
ìèçàöèè âõîäîâ ìóëüòèïëåêñîðîâ èñïîëüçóåì ñëåäóþùèå óòâåðæäåíèÿ.
Óòâåðæäåíèå 1. Äëÿ êîððåêòíîé ÊÀ ÷èñëî âõîäîâ N Mi ìóëüòèïëåê-
ñîðîâ i-é âåðøèíû ÏÝ íå áîëüøå ÷èñëà íåîäèíàêîâûõ âåêòîðîâ D i j,
,
èíöèäåíòíûõ âåðøèíàì K i k,
, êîòîðûå îòîáðàæàþòñÿ â âåðøèíó ÏÝ.
Äîêàçàòåëüñòâî óòâåðæäåíèÿ 1 î÷åâèäíî. Âûðàæåíèå «íå áîëüøå»
îçíà÷àåò, ÷òî, íå áîëåå ÷åì ñ îäíîãî âõîäà ÏÝ ïîäàåòñÿ îïåðàíä íà îäèí
âõîä ÀËÓ ýòîãî ÏÝ, è äëÿ òàêîãî âõîäà ìóëüòèïëåêñîð íå íóæåí.
Óòâåðæäåíèå 2. Ïóñòü ÃÑÏÄ êîððåêòíîé êîíôèãóðàöèè àëãîðèòìà
KG èìååò äî L èçîìîðôíûõ ïîäãðàôîâ, êîòîðûå ïðåäñòàâëåíû ýêâèâàëåíò-
íûìè ïîäêîíôèãóðàöèÿìè KGγ = (Kγ, Dγ, AO). Òîãäà, äëÿ òîãî ÷òîáû ïðè
îòîáðàæåíèè ÊÀ KG â ñòðóêòóðó ñ êîíôèãóðàöèåé KS è ïåðèîäîì âû÷èñëå-
íèé L ïîëó÷àëîñü ìèíèìàëüíîå ÷èñëî ÏÝ è âõîäîâ èõ ìóëüòèïëåêñîðîâ,
íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû âñå ïîäêîíôèãóðàöèè KGγ îòîáðàæàëèñü
â îäíó ïîäêîíôèãóðàöèþ ñòðóêòóðû KSÎ, ïðè÷åì
� �� �K Ki j Oi i j j k j l i jK c c t
, , , , ,
( , , ),
� K i j OiK
,
, (1)
(Di,l êîíöîì èíöèäåíòíûé K Di j i k l lc c c
, ,
, , , )� �� � �
1
1 0 .
Ñëåäîâàòåëüíî, ïîäãðàô ñòðóêòóðû èçîìîðôåí ïîäãðàôàì àëãîðèòìà.
Íà ðèñ. 1 ïîêàçàí ïðèìåð îòîáðàæåíèÿ ÊÀ ñ ïåðèîäîì L = 3 â ñîîòâåòñò-
âóþùóþ ÊÑ.
Ä î ê à ç à ò å ë ü ñ ò â î ä î ñ ò à ò î ÷ í î ñ ò è. Íåòðóäíî ïîêàçàòü ÷òî ïðè
óñëîâèÿõ (1) ÏÝ ñ îäíîâõîäîâûì ÀËÓ áóäåò èìåòü îäèí âõîä, à ñ äâóâõî-
À. Ì. Ñåðãèåíêî, Â. Ï. Ñèìîíåíêî
54 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
S
T
KGO1
KGO2
KGO3 KSO
Ìóëüòèïëåêñîð
Ðèñ. 1. Îòîáðàæåíèå ÊÀ ñîãëàñíî óòâåðæäåíèþ 2
äîâûì ÀËÓ — ñîîòâåòñòâåííî, äâà âõîäà, ò. å. êàæäûé ÏÝ, êðîìå ÏÝ
ââîäà-âûâîäà ýòîé ïîäñòðóêòóðû, íå èìååò ìóëüòèïëåêñîðîâ.
Ä î ê à ç à ò å ë ü ñ ò â î í å î á õ î ä è ì î ñ ò è. Ïóñòü îäíà èëè äâå
âåðøèíû-îïåðàòîðîâ ïåðåñòàâëåíû, ò. å. íå âûïîëíÿþòñÿ óñëîâèÿ (1).
Òîãäà âîçìîæíû äâà ñëó÷àÿ.  ïåðâîì — îäíà ïåðåñòàâëåííàÿ âåðøèíà
îòîáðàçèòñÿ â íîâóþ âåðøèíó ÏÝ, ò.å. óâåëè÷àòñÿ àïïàðàòíûå çàòðàòû íà
îäèí ÏÝ. Êðîìå òîãî, âåêòîð Di,l, âûõîäÿùàÿ èç ýòîé âåðøèíû, èçìåíèò
ñâîè êîîðäèíàòû è íå áóäåò ðàâåí âåêòîðó Di,k, êîòîðûé äî ýòîãî âìåñòå ñ
íèì îòîáðàæàëñÿ â îäíó äóãó ãðàôà ñòðóêòóðû. Ïîýòîìó ñëåäóåò äîáàâèòü
ìóëüòèïëåêñîð â ÏÝ, â êîòîðûé ïîñòóïàåò ðåçóëüòàò ñ íîâîãî ÏÝ.
Âî âòîðîì ñëó÷àå âåðøèíà áóäåò îòîáðàæåíà â äðóãîé, íå ïîëíîñòüþ
çàíÿòûé, ÏÝ èëè äâå âåðøèíû áóäóò âçàèìíî ïåðåñòàâëåíû. Òîãäà íà
âõîäàõ ÀËÓ ýòèõ ÏÝ ïîÿâÿòñÿ äâóâõîäîâûå ìóëüòèïëåêñîðû. Òàêèì îáðà-
çîì, ëþáûå èçìåíåíèÿ â ïîäêîíôèãóðàöèÿõ, íàðóøàþùèå òðåáîâàíèå (1),
ïðèâîäÿò ê óâåëè÷åíèþ ÷èñëà ÏÝ èëè âõîäîâ ìóëüòèïëåêñîðîâ.
Ìåòîäèêà ñèíòåçà öèôðîâûõ ôèëüòðîâ ñ êðàòíûìè çàäåðæêàìè.
Ðàññìîòðèì ïðèìåíåíèå îïèñàííîãî âûøå ìåòîäà äëÿ ïðîåêòèðîâàíèÿ
âûñîêîýôôåêòèâíûõ öèôðîâûõ ôèëüòðîâ, ðåàëèçóåìûõ â ÏËÈÑ. Öèôðî-
âûå ôèëüòðû ïðèíÿòî îïèñûâàòü ïåðåäàòî÷íîé õàðàêòåðèñòèêîé H0(Z) îò
êîìïëåêñíîé ïåðåìåííîé Z. Îíà îäíîçíà÷íî ñîîòâåòñòâóåò àëãîðèòìó
âû÷èñëåíèÿ ôèëüòðà. Ïðè ýòîì êàæäîìó ÷ëåíó Zk
â ôîðìóëå õàðàêòåðèñ-
òèêè ñîîòâåòñòâóåò çàäåðæêà íà k öèêëîâ èëè öåïî÷êà èç k ðåãèñòðîâ
çàäåðæêè. Åñëè â ôèëüòðå ÷èñëî ðåãèñòðîâ çàäåðæêè óâåëè÷èòü â n ðàç, òî
ïîëó÷èì ôèëüòð ñ õàðàêòåðèñòèêîé Hn (z) = H0 (Z n
). Òàêîé ôèëüòð ñ êðàò-
íûìè çàäåðæêàìè èìååò ñëåäóþùóþ îñîáåííîñòü: åãî àìïëèòóäî-÷àñòîòíàÿ
õàðàêòåðèñòèêà (À×Õ) ïî ôîðìå òàêàÿ æå, êàê ó ôèëüòðà-ïðîòîòèïà H0(Z), íî
â äèàïàçîíå 0 — fS îíà ïîâòîðÿåòñÿ n ðàç, ãäå fS — ÷àñòîòà äèñêðåòèçàöèè.
Ïðè ïîñëåäîâàòåëüíîì ñîåäèíåíèè ñòóïåíåé ôèëüòðîâ ðåçóëüòèðóþ-
ùàÿ À×Õ — ýòî ïåðåñå÷åíèå À×Õ ñòóïåíåé, ÷òî íàçûâàþò ìàñêèðîâàíèåì
À×Õ. Òàêæå ìàñêèðîâàíèå è èñïîëüçîâàíèå ôèëüòðîâ ñ êðàòíûìè çàäåðæ-
êàìè ïîçâîëÿåò ïîëó÷àòü âûñîêîäîáðîòíûå ôèëüòðû ñ ìèíèìàëüíûìè
àïïàðàòíûìè çàòðàòàìè [8]. Êðîìå òîãî, åñëè íå ýêîíîìèòü ðåãèñòðû
çàäåðæêè, òî ôèëüòð ñ êðàòíûìè çàäåðæêàìè — ýòî ýêâèâàëåíò ôèëüòðà ñ
íåñêîëüêèìè ÷àñòîòàìè äèñêðåòèçàöèè, íàïðèìåð ñèñòåìû èç ôèëüòðîâ-
äåöèìàòîðîâ è èíòåðïîëÿòîðîâ. Â ÏËÈÑ ôèðìû Xilinx êðàòíûå çàäåðæêè
âûïîëíÿþò íà áëîêàõ FIFO òèïà SRL16, çàíèìàþùèõ òàêîé æå îáúåì, êàê
è îòäåëüíûå ðåãèñòðû. Äëÿ ñèíòåçà òàêèõ ôèëüòðîâ íà áàçå ÏËÈÑ ïðåä-
ëàãàåòñÿ ñëåäóþùàÿ ìåòîäèêà.
Íà ïåðâîì ýòàïå âûáèðàåì àëãîðèòì, ÃÑÏÄ êîòîðîãî èìååò èçîìîðô-
íûå ïîäãðàôû. Äóãè ãðàôà íàãðóæåíû çàäåðæêàìè, êîòîðûå êðàòíû è ðàâ-
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 55
íû K. Ïóñòü ÷èñëî òàêèõ ïîäãðàôîâ ðàâíî L. Ïðè ýòîì óñëîâèè äîñòèãàåòñÿ
ìàêñèìàëüíàÿ çàãðóæåííîñòü ðåçóëüòèðóþùåé ñòðóêòóðû. Ïîäãðàô àëãîðèò-
ìà, äëÿ êîòîðîãî K = 1, ïðåäñòàâëÿåì â âèäå êîíôèãóðàöèè ïåðèîäà àëãîðèò-
ìà (ÊÏÀ).  íåé äîïîëíèòåëüíî âûäåëÿåì ïîãðàíè÷íûå âåðøèíû, â êîòîðûå
çàõîäÿò è èç êîòîðûõ âûõîäÿò çàìûêàþùèå âåêòîðû, ñîîòâåòñòâóþùèå çà-
äåðæêàì íà k öèêëîâ. Ýòè ïîãðàíè÷íûå âåðøèíû äàëåå áóäóò îòîáðàæåíû â
èòåðàöèîííûå âõîäû è âûõîäû êîíôèãóðàöèè ñòðóêòóðû. ÊÏÀ îïòèìè-
çèðóåòñÿ ïðè óñëîâèè, ÷òî îíà îòîáðàæàåòñÿ â ñòðóêóòóðó ñ ïåðèîäîì âû÷èñ-
ëåíèé, ðàâíûì îäíîìó òàêòó, ò. å. ñ ìàêñèìàëüíûì ïàðàëëåëèçìîì.
Íà âòîðîì ýòàïå îò äâóõ äî L ÊÏÀ ñîåäèíÿþòñÿ ìåæäó ñîáîé â
ñîîòâåòñòâèè ñ àëãîðèòìîì ôèëüòðàöèè. Ïðè ýòîì ñîáëþäàþòñÿ óñëîâèÿ
óòâåðæäåíèÿ 2. Ïîñêîëüêó â íåêîòîðîé ñòóïåíè èñïîëüçóþòñÿ çàäåðæêè
íà k òàêòîâ, ê åå ÊÏÀ äîáàâëÿþòñÿ ïîäêîíôèãóðàöèè çàäåðæåê íà k–1
ïåðèîäîâ, êîòîðûå ÷åðåç çàìûêàþùèå âåêòîðû äëèíîé kL ïîäñîåäèíÿþòñÿ
ê ñîîòâåòñòâóþùèì ïîãðàíè÷íûì âåðøèíàì. Òàêæå äîáàâëÿþòñÿ âåðøè-
íû îïåðàòîðîâ è äóãè, äîïîëíÿþùèåùèå ÊÏÀ, ïîäêîíôèãóðàöèè çàäåð-
æåê äî ïîëíîãî ÃÑÏÄ.
Íà òðåòüåì ýòàïå ÊÀ îòîáðàæàåòñÿ â êîíôèãóðàöèþ ñòðóêòóðû ñ ïå-
ðèîäîì âû÷èñëåíèé L. Ðåçóëüòèðóþùàÿ ñòðóêòóðà âêëþ÷àåò â ñåáÿ ñòðóê-
òóðó, ñîîòâåòñòâóþùóþ ÊÏÀ, ê èòåðàöèîííûì âõîäàì êîòîðîé ïîäêëþ-
÷åíû ìóëüòèïëåêñîðû, à ê èõ âõîäàì ÷åðåç çàäåðæêè íà k – 1 ïåðèîäîâ
ïîäàþòñÿ çàäåðæèâàåìûå äàííûå.
Àïïàðàòíûå çàòðàòû ÂÓ âêëþ÷àþò çàòðàòû íà ïîñòðîåíèå êîíâåéåð-
íîé ñòðóêòóðû, â êîòîðóþ îòîáðàæàåòñÿ ÊÏÀ, ìóëüòèïëåêñîðû íà èòåðà-
öèîííûõ âõîäàõ ñ ÷èñëîì âõîäîâ äî L è çàäåðæêè íà ðàçëè÷íîå ÷èñëî
ïåðèîäîâ (îò 0 äî k – 1). Ïðè ýòîì êîíâåéåðíàÿ ñòðóêòóðà ìóëüòèïëåêñîðîâ íå
ñîäåðæèò. Àïïàðàòíûå çàòðàòû, âûðàæåííûå â ñëîæíîñòè ñóììàòîðà, íå
ñ÷èòàÿ ÷èñëà ðåãèñòðîâ, ìîæíî îïðåäåëèòü ïî ôîðìóëå
� � ��S A Mn n10
�0 57, LnD , ãäå nA è nM — ÷èñëî ñóììàòîðîâ è áëîêîâ óìíîæåíèÿ, ðàâíîå
÷èñëó ñëîæåíèé è óìíîæåíèé â àëãîðèòìå ñòóïåíè; nD — ÷èñëî ïåðåìåí-
íûõ, ïî êîòîðûì âûïîëíÿþòñÿ ìåæèòåðàöèîííûå ñâÿçè, ò.å. ÷èñëî ëèíèé
çàäåðæåê â ñòóïåíè ôèëüòðà. Çäåñü ñëîæíîñòü óìíîæèòåëÿ ïðèíÿòà ðàâíîé
ñëîæíîñòè äåñÿòêà ñóììàòîðîâ, òàê êàê â ñîâðåìåííûõ ÏËÈÑ ïðè èõ
ìàêñèìàëüíîé çàïîëíåííîñòè íà îäèí àïïàðàòíûé óìíîæèòåëü ïðèõîäèò-
ñÿ îò øåñòè äî äâàäöàòè ñèíòåçèðóåìûõ ñóììàòîðîâ òàêîé æå ðàçðÿäíîñòè,
ò.å. â ñðåäíåì — äåñÿòü (äëÿ ñåðèè Xilinx Virtex 4) [4].
×èñëî ðåãèñòðîâ â ñòðóêòóðå çàâèñèò îò òîïîëîãèè ÃÑÏÄ ñòóïåíè
ôèëüòðà, ðàñïðåäåëåíèÿ äëèíû çàäåðæåê ïî ñòóïåíÿì è ïðîïîðöèîíàëüíî
L. Ðåçóëüòèðóþùàÿ ñòðóêòóðà ïðè ÷èñëå ñòóïåíåé ôèëüòðà, ðàâíîì L, èìå-
åò ìèíèìàëüíîå ÷èñëî ðåãèñòðîâ, ñóììàòîðîâ è áëîêîâ óìíîæåíèÿ. Ýòî
À. Ì. Ñåðãèåíêî, Â. Ï. Ñèìîíåíêî
56 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
óòâåðæäåíèå îñíîâàíî íà òîì, ÷òî ïðè óñëîâèè (1) ðîâíî L âåðøèí îïåðà-
òîðîâ çàäåðæêè, îïåðàòîðîâ ñëîæåíèÿ è óìíîæåíèÿ îòîáðàæàþòñÿ ñîîò-
âåòñòâåííî â îäíó âåðøèíó ðåãèñòðà, ñóììàòîðà è áëîêà óìíîæåíèÿ. Ñëåäî-
âàòåëüíî, âñå ðåñóðñû ñòðóêòóðû àñèìïòîòè÷åñêè çàãðóæåíû íà 100 %.
Ïðèìåð ñèíòåçà öèôðîâîãî ôèëüòðà. Ðàññìîòðèì ïðèìåð ñèíòåçà
ôèëüòðà íèæíèõ ÷àñòîò, ñîñòîÿùåãî èç ÷åòûðåõ ñòóïåíåé ñ çàäåðæêàìè
êðàòíîñòè 1, 2, 4 è 8. Ïåðâûå òðè ñòóïåíè — ýòî ôèëüòðû-ïñåâäîäåöè-
ìàòîðû, à ïîñëåäíÿÿ ñòóïåíü — ôèëüòð-ôîðìèðîâàòåëü. Ôèëüòð-ïñåâäî-
äåöèìàòîð âûïîëíÿåò ôèëüòðàöèþ íèæíèõ ÷àñòîò ñ òàêîé æå À×Õ, êàê ó
ôèëüòðà-äåöèìàòîðà, íî íå âûïîëíÿåò ñîáñòâåííî äåöèìàöèþ. Âñëåäñò-
âèå òîãî, ÷òî ôèëüòðû-ïñåâäîäåöèìàòîðû èìåþò êðàòíûå çàäåðæêè è
âûïîëíÿåòñÿ ìàñêèðîâàíèå, ðåçóëüòèðóþùàÿ À×Õ èìååò íèçêóþ ÷àñòîòó
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 57
Âõîä
Âûõîä
Ðèñ. 2. Ðåçóëüòèðóþùàÿ ÊÀ: O — ïîãðàíè÷íàÿ âåðøèíà; — çàäåðæêà íà îäèí òàêò èëè
ðåãèñòð; — ñëîæåíèå; — îáðàòíàÿ äóãà
ñðåçà (ìåíåå fS/16) è óçêóþ ïåðåõîäíóþ ïîëîñó [8]. Êàæäàÿ ñòóïåíü âûïîë-
íåíà íà îñíîâå âñåïðîïóñêàþùåãî ôèëüòðà, ÷òî îáåñïå÷èâàåò âûñîêèå è
ñòàáèëüíûå õàðàêòåðèñòèêè ôèëüòðà, à òàêæå âîçìîæíîñòü ðåãóëèðîâàíèÿ
åãî õàðàêòåðèñòèê. Ïåðåäàòî÷íàÿ ôóíêöèÿ îäíîé (ïåðâîé) ñòóïåíè ôèëüò-
ðà èìååò âèä
H z Z
Z b a Z a
b a Z aZ
( )
( )
( )
� �
� � �
� � �
�
� �
� �
1
2 1
1 2
1
1 1
,
(2)
ãäå b — êîýôôèöèåíò, ðåãóëèðóþùèé ÷àñòîòó ñðåçà; a — êîýôôèöèåíò,
ðåãóëèðóþùèé êðóòèçíó ñïàäà [8].
Íà ïåðâîì ýòàïå ñèíòåçà ôèëüòðà ôîðìèðóåòñÿ óðàâíîâåøåííàÿ ÊÏÀ
(ðèñ. 2), ñîîòâåòñòâóþùàÿ âîëíîâîìó ôèëüòðó âòîðîãî ïîðÿäêà ñ ïåðåäà-
òî÷íîé õàðàêòåðèñòèêîé (2).
Íà âòîðîì ýòàïå ÷åòûðå êîíôèãóðàöèè ïåðèîäà àëãîðèòìà ÊÏÀ ñîå-
äèíÿþòñÿ ìåæäó ñîáîé ïîñëåäîâàòåëüíî. Íà ðèñ. 3 ÊÏÀ ïðåäñòàâëåíû
çàòåìíåííûìè ìíîãîóãîëüíèêàìè. Íà òðåòüåì ýòàïå ïîëó÷àåì ñòðóêòóðó
ôèëüòðà (ðèñ. 4) è ñèíòåçèðóåì åãî óïðàâëÿþùèé àâòîìàò. Ðåàëèçàöèÿ
ôèëüòðà ñîñòîèò â åãî îïèñàíèè íà ÿçûêå VHDL è äàëüíåéøåì îòîáðàæå-
íèè â ÏËÈÑ. Ïðè ýòîì ìîæíî èñïîëüçîâàòü ìåòîäèêó îòîáðàæåíèÿ ÊÀ â
ÏËÈÑ, îïèñàííóþ â [6].
Îöåíèì àïïàðàòíûå çàòðàòû è ïðîèçâîäèòåëüíîñòü ïîëó÷åííîãî
ôèëüòðà. Ïðè ïîñòðîåíèè áàçîâîé ñòðóêòóðû ôèëüòðà òðàäèöèîííûì ñïî-
ñîáîì îíà èìååò ÷åòûðå ïîñëåäîâàòåëüíî ñîåäèíåííûå ñòóïåíè. Êàæäàÿ
ñòóïåíü èìååò ñåìü ñóììàòîðîâ, äâà áëîêà óìíîæåíèÿ è òðè ðåãèñòðà,
êîòîðûå ïðåäíàçíà÷åíû äëÿ ðåàëèçàöèè êîíâåéåðíîãî ðåæèìà âû÷èñëå-
íèé è ïðèåìà âõîäíîãî îïåðàíäà. Êðîìå òîãî, ñòóïåíè äîëæíû èìåòü ïî
òðè ðåãèñòðîâûå çàäåðæêè äëèíîé 1, 2, 4 è 8 ðåãèñòðîâ, êîòîðûå ìîæíî
ðåàëèçîâàòü êàê áëîêè SRL16. Ðåçóëüòèðóþùèå àïïàðàòíûå çàòðàòû ñîñ-
À. Ì. Ñåðãèåíêî, Â. Ï. Ñèìîíåíêî
58 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3
Âõîä Öèêë
Âûõîä
7
7
7
3
3
3
1
1
1
Ðèñ. 3. Êîíôèãóðàöèÿ ïåðèîäà àëãîðèòìà îäíîé ñòóïåíè ôèëüòðà: � —ïîãðàíè÷íàÿ âåðøè-
íà; � — çàäåðæêà íà îäèí, òðè è ñåìü òàêòîâ
òàâëÿþò �SB = 132. Äëÿ òàêîé ñòðóêòóðû â êðèòè÷åñêèé ïóòü âõîäÿò
÷åòûðå ñóììàòîðà, ò.å. ïåðèîä òàêòîâîãî èíòåðâàëà ñîñòàâëÿåò �TB ST� 4 .
Ñèíòåçèðîâàííàÿ ñòðóêòóðà èìååò äâà áëîêà óìíîæåíèÿ, ñåìü ñóììà-
òîðîâ, 26 ðåãèñòðîâ è ðåãèñòðîâûõ çàäåðæåê, à òàêæå îäèí äâóâõîäîâûé è
øåñòü ÷åòûðåõâõîäîâûõ ìóëüòèïëåêñîðîâ.  ñòðóêòóðå çàäåéñòâîâàíî 22
âõîäà ìóëüòèïëåêñîðà è ðåçóëüòèðóþùèå àïïàðàòíûå çàòðàòû ñîñòàâëÿþò
�S = 65,5. Ïåðèîä òàêòîâîãî èíòåðâàëà ñîñòàâëÿåò �T ST� , ò. å. â êðèòè-
÷åñêèé ïóòü âõîäèò ëèøü çàäåðæêà îäíîãî ñóììàòîðà èëè óìíîæèòåëÿ, à
äëèòåëüíîñòü öèêëà ñîñòàâëÿåò LT TS S� 4 . Òàêèì îáðàçîì, ïîëó÷åííàÿ
ñòðóêòóðà ôèëüòðà îáåñïå÷èâàåò âäâîå ìåíüøèå àïïàðàòíûå çàòðàòû, ÷åì
òðàäèöèîííàÿ, ïðè òàêîé æå ïðîèçâîäèòåëüíîñòè.
Öèôðîâîé ôèëüòð ñ äèíàìè÷åñêîé ïåðåñòðîéêîé ÷àñòîòû ñðåçà. Íà
îñíîâå îïèñàííûõ àëãîðèòìîâ áûë ðàçðàáîòàí ïðîåêò öèôðîâîãî ôèëüòðà ñ
äèíàìè÷åñêîé ïåðåñòðîéêîé ÷àñòîòû ñðåçà. Ïðè ýòîì äëÿ óëó÷øåíèÿ ôèëü-
òðàöèè â ïðèâåäåííîì âûøå ïðèìåðå ïîðÿäîê âñåïðîïóñêàþùåãî ôèëüòðà
ïîâûøåí äî òðåõ. ×àñòîòà ñðåçà â ôèëüòðå ïåðåñòðàèâàåòñÿ ñêà÷êàìè —
îòâîäîì ñèãíàëà îò òîé èëè èíîé ñòóïåíè, à òàêæå ïëàâíî — èçìåíåíèåì
êîýôôèöèåíòîâ ñòóïåíè, îò êîòîðîé âûïîëíÿåòñÿ îòâîä, ò. å. êîýôôèöèåíòîâ
ôèëüòðà-ôîðìèðîâàòåëÿ.  ðåçóëüòàòå ÷àñòîòà ñðåçà èçìåíÿåòñÿ ïëàâíî â
ïðåäåëàõ îò 0,015 äî 0,4 fS. Ïîñêîëüêó ñòóïåíè îáðàçóþò ïàðû îäèíàêîâûõ
ôèëüòðîâ, à ÷èñëî ñòóïåíåé óâåëè÷åíî äî L = 8, ïðè ëþáîé çàäàííîé ÷àñòîòå
ñðåçà óðîâåíü ïîäàâëåíèÿ ñîñòàâëÿåò íå ìåíåå 75—80 äá, à íàêëîí À×Õ â
ïåðåõîäíîé ïîëîñå — íå ìåíåå 100 äá/îêòàâà.
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 59
7
7
7
3
3
3
1
1
1
Âõîä
Âûõîä
Ðèñ. 4. Êîíôèãóðàöèÿ ñòðóêòóðû ôèëüòðà: O — ïîãðàíè÷íûé âõîä-âûõîä; — çàäåðæêà
íà îäèí, òðè è ñåìü òàêòîâ; — ìóëüòèïëåêñîð
Äëÿ çàäàíèÿ ÷àñòîòû ñðåçà 12-áèòíûì êîäîì ïðèìåíåí àïïàðàòíûé
êàëüêóëÿòîð, ïåðåñ÷èòûâàþùèé êîä ÷àñòîòû â çíà÷åíèå êîýôôèöèåíòîâ
ôèëüòðà-ôîðìèðîâàòåëÿ. Ïîñêîëüêó àëãîðèòì âîëíîâîãî ôèëüòðà ïðèíöè-
ïèàëüíî íå äîïóñêàåò òàêèõ ÿâëåíèé, êàê íåñòàáèëüíîñòü ðàáîòû, âîçáóæ-
äåíèå, ïðè âñåõ âîçìîæíûõ êîäàõ ÷àñòîòû è âõîäíûõ äàííûõ ôèëüòð
ðàáîòàåò ñòàáèëüíî.
Ôèëüòð áûë ðåàëèçîâàí â ÏËÈÑ Xilinx Virtex2P. Åãî àïïàðàòíûå
çàòðàòû áåç çàòðàò íà ðåàëèçàöèþ êàëüêóëÿòîðà êîýôôèöèåíòîâ ñîñòàâ-
ëÿþò 706 ýêâèâàëåíòíûõ êîíôèãóðèðóåìûõ ëîãè÷åñêèõ áëîêîâ (CLB slices)
è òðè áëîêà óìíîæåíèÿ. Âñëåäñòâèå âûñîêîé ñòåïåíè êîíâåéåðèçàöèè
ñòðóêòóðû òàêòîâàÿ ÷àñòîòà äîñòèãàåò 190 ÌÃö. Òàêèì îáðàçîì, ôèëüòð
ìîæåò îáðàáàòûâàòü â ðåàëüíîì âðåìåíè ñèãíàëû ñ ÷àñòîòîé äèñêðå-
òèçàöèè äî 24 ÌÃö.
Âûâîäû. Îïèñàííûé ìåòîä ïðîåêòèðîâàíèÿ êîíâåéåðèçîâàííûõ ÂÓ
äëÿ ðåàëèçàöèè ïåðèîäè÷åñêèõ àëãîðèòìîâ, îáåñïå÷èâàåò ìèíèìèçàöèþ
êàê ÷èñëà ÀËÓ, áëîêîâ óìíîæåíèÿ, òàê è ÷èñëà âõîäîâ ìóëüòèïëåêñîðîâ â
ðåçóëüòàòå èñïîëüçîâàíèÿ îñîáåííîñòåé àëãîðèòìîâ è ñòðóêòóðíûõ ñâîéñòâ
ñîâðåìåííûõ ÏËÈÑ. Ïðè ýòîì ñèíòåçèðîâàííîå ÂÓ èìååò ìèíèìàëüíûé
ïåðèîä òàêòîâîãî èíòåðâàëà ïðè âûïîëíåíèè àëãîðèòìà â êîíâåéåðíîì
ðåæèìå ñ çàäàííûì ïåðèîäîì âû÷èñëåíèé L.
Ðàçðàáîòàííûå ìåòîäû è ìåòîäèêà ïðîåêòèðîâàíèÿ ìíîãîñòóïåí÷à-
òûõ öèôðîâûõ ôèëüòðîâ ñ êðàòíûìè çàäåðæêàìè îáåñïå÷èâàåò ïðè çàäàííûõ
îãðàíè÷åíèÿõ (ïåðèîä L, ýëåìåíòíàÿ áàçà, ÃÑÏÄ ñ èçîìîðôíûìè ïîäãðà-
ôàìè) ìèíèìàëüíûå ïåðèîä ñèíõðîñåðèè è àïàðàòíûå çàòðàòû. Ïðîâåðêà
ìåòîäèêè ïðè ïðîåêòèðîâàíèè ìíîãîñòóïåí÷àòûõ âîëíîâûõ ôèëüòðîâ ïîêà-
çàëà, ÷òî ìîæíî óìåíüøèòü àïïàðàòíûå çàòðàòû â äâà ðàçà ïðè òàêîé æå
ïðîèçâîäèòåëüíîñòè ïî ñðàâíåíèþ ñ òðàäèöèîííîé ñòðóêòóðîé.
A method of mapping periodical algorithms into pipeline processor based on FPGA is conside-
red. The algorithm is represented by the synchronous dataflow graph. The method lies in placing
the algorithm graph in multidimensional index space and then in its mapping into subspaces of
structures and time. The limitations to the mapping process allow to minimize both the clock
cycle and hardware volume including multiplexers.
1. Bhattacharyya S. S., Leupers R., Marwedel P. Software Synthesis and Code Generation for
Signal Processing Systems // IEEE Trans. on Circuits and Systems—II: Analog and Digital
Signal Processing.— 2000. — Vol 47, ¹ 9. — P. 849—875.
2. The Synthesis Approach to Digital System Design / Ed. P. Michel, U. Lauther, P. Duzy. —
NY: Kluwer Academic Pub,1992. — 415 p.
3. Eles P., Kuchinski K., Zebo P. System Synthesis with VHDL. — NY : Kluwer Academic
Pub, 1998. — 370 p.
4. Hill T. The benefits of FPGA Coprocessing // Xcell journal: Xilinx. — 2006. — Vol. 58,
¹ 3. — Ð. 29—31.
À. Ì. Ñåðãèåíêî, Â. Ï. Ñèìîíåíêî
60 ISSN 0204–3572. Electronic Modeling. 2007. V. 29. ¹ 2
5. Êàíåâñêèé Þ. Ñ., Îâðàìåíêî Ñ. Ã., Ñåðãèåíêî À. Ì. Îòîáðàæåíèå ðåãóëÿðíûõ àëãîðèò-
ìîâ â ñòðóêòóðû ñïåöèàëèçèðîâàííûõ ïðîöåññîðîâ // Ýëåêòðîí. ìîäåëèðîâàíèå. —
2002. — 24. ¹ 2. — Ñ. 46—59.
6. Ñåðãèåíêî À. Ì. VHDL äëÿ ïðîåêòèðîâàíèÿ âû÷èñëèòåëüíûõ óñòðîéñòâ. — Êèåâ :
ÄèàÑîôò, 2003. — 208 ñ.
7. Êàíåâñêèé Þ. Ñ., Ëîãèíîâà Ë. Ì., Ñåðãèåíêî À. Ì. Ñòðóêòóðíîå ïðîåêòèðîâàíèå
ðåêóðñèâíûõ öèôðîâûõ ôèëüòðîâ // Ýëåêòðîí. ìîäåëèðîâàíèå. — 1995. —17, ¹ 3. —
Ñ. 18—22.
8. Chung J. G., Parhi K. K. Pipelined wave digital filter design for narrow-band sharp-transi-
tion digital filters // Proc. IEEE Workshop VLSI Signal Processing. CA, La Jolla. —1994. —
Ð. 501—510.
Ïîñòóïèëà 18.09.06;
ïîñëå äîðàáîòêè 07.11.06
ÑÅÐÃÈÅÍÊÎ Àíàòîëèé Ìèõàéëîâè÷, êàíä. òåõí. íàóê, ñò. íàó÷. ñîòð. Íàöèîíàëüíîãî òåõíè-
÷åñêîãî óíèâåðñèòåòà Óêðàèíû «ÊÏÈ», êîòîðûé îêîí÷èë â 1981 ã. Îáëàñòü íàó÷íûõ èññëåäî-
âàíèé — îòîáðàæåíèå àëãîðèòìîâ â ñòðóêòóðû âû÷èñëèòåëüíûõ ñðåäñòâ, öèôðîâàÿ îáðà-
áîòêà ñèãíàëîâ.
CÈÌÎÍÅÍÊÎ Âàëåðèé Ïàâëîâè÷, ä-ð òåõí. íàóê, ïðîôåññîð Íàöèîíàëüíîãî òåõíè÷åñêîãî
óíèâåðñèòåòà Óêðàèíû «ÊÏÈ», êîòîðûé îêîí÷èë â 1965 ã. Îáëàñòü íàó÷íûõ èññëåäîâàíèé —
îðãàíèçàöèÿ âû÷èñëèòåëüíûõ ïðîöåññîâ â âû÷èñëèòåëüíûõ ñèñòåìàõ.
Îòîáðàæåíèå ïåðèîäè÷åñêèõ àëãîðèòìîâ
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2007. Ò. 29. ¹ 2 61
|