Преобразование кодов в композиционных микропрограммных устройствах управления
Запропоновано спільне використання методів структурної декомпозиції та перетворення кодів об’єктів, що орієнтоване на зменшення апаратурних витрат у схемі композиційного мікропрограмного пристрою керування. Оптимізація досягається завдяки зменшенню як кількості аргументів нерегулярних функцій, так і...
Saved in:
| Published in: | Кибернетика и системный анализ |
|---|---|
| Date: | 2011 |
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84238 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Преобразование кодов в композиционных микропрограммных устройствах управления / А.А. Баркалов, Л.А. Титаренко // Кибернетика и системный анализ. — 2011. — Т. 47, № 5. — С. 107-118. — Бібліогр.: 11 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859676995376381952 |
|---|---|
| author | Баркалов, А.А. Титаренко, Л.А. |
| author_facet | Баркалов, А.А. Титаренко, Л.А. |
| citation_txt | Преобразование кодов в композиционных микропрограммных устройствах управления / А.А. Баркалов, Л.А. Титаренко // Кибернетика и системный анализ. — 2011. — Т. 47, № 5. — С. 107-118. — Бібліогр.: 11 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано спільне використання методів структурної декомпозиції та перетворення кодів об’єктів, що орієнтоване на зменшення апаратурних витрат у схемі композиційного мікропрограмного пристрою керування. Оптимізація досягається завдяки зменшенню як кількості аргументів нерегулярних функцій, так і кількості самих функцій. Для реалізації регулярних функцій використовуються вбудовані блоки пам’яті. Розглянуто метод і приклад синтезу, а також наведено результати досліджень.
Properties of a smooth continuous spline are considered. Existence conditions are established and an algorithm for determining parameters of such a spline by the sum of a polynomial and an exponent is proposed. Estimates of approximation errors are obtained for polynomial splines and splines with sections in the form of the sum of a polynomial and an exponent.
|
| first_indexed | 2025-11-30T16:29:16Z |
| format | Article |
| fulltext |
ÓÄÊ 004.383.3
À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ
ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÊÎÄÎÂ Â ÊÎÌÏÎÇÈÖÈÎÍÍÛÕ
ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÛÕ ÓÑÒÐÎÉÑÒÂÀÕ ÓÏÐÀÂËÅÍÈß
Êëþ÷åâûå ñëîâà: êîìïîçèöèîííîå ìèêðîïðîãðàììíîå óñòðîéñòâî óïðàâëåíèÿ,
ÏËÈÑ, ñòðóêòóðíàÿ äåêîìïîçèöèÿ, îïòèìèçàöèÿ
ÂÂÅÄÅÍÈÅ
Ìåòîäû îïòèìèçàöèè àïïàðàòóðíûõ çàòðàò â ñõåìàõ óñòðîéñòâ óïðàâëåíèÿ
(ÓÓ) çàâèñÿò êàê îò õàðàêòåðèñòèê ðåàëèçóåìîãî àëãîðèòìà óïðàâëåíèÿ, òàê è
îò ïàðàìåòðîâ ýëåìåíòíîãî áàçèñà [1]. Ïðè ðåàëèçàöèè ñõåì ÓÓ íà ïðîãðàì-
ìèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåìàõ (ÏËÈÑ) òèïà FPGA (field
programmable gate arrays) îäíèì èç ìåòîäîâ îïòèìèçàöèè ÿâëÿåòñÿ ôóíêöèî-
íàëüíàÿ äåêîìïîçèöèÿ [2, 3]. Ýòî ñâÿçàíî ñ òåì, ÷òî îñíîâó òàêèõ ÏËÈÑ ñî-
ñòàâëÿþò ëîãè÷åñêèå ýëåìåíòû (ËÝ) òàáëè÷íîãî òèïà LUT (look-up table)
[4, 5]. Åñëè àëãîðèòì óïðàâëåíèÿ íîñèò ëèíåéíûé õàðàêòåð, òî äëÿ åãî èíòåð-
ïðåòàöèè öåëåñîîáðàçíî èñïîëüçîâàòü ìîäåëü êîìïîçèöèîííîãî ìèêðîïðîãðàì-
ìíîãî óñòðîéñòâà óïðàâëåíèÿ (ÊÌÓÓ) [6]. Â ÊÌÓÓ ñèñòåìà ìèêðîîïåðàöèé
ðåàëèçóåòñÿ íà ïîñòîÿííûõ çàïîìèíàþùèõ óñòðîéñòâàõ (ÏÇÓ). Äëÿ ýòîé öåëè
ìîãóò áûòü ýôôåêòèâíî èñïîëüçîâàíû âñòðîåííûå áëîêè ïàìÿòè EMB
(embedded memory blocks) ñîâðåìåííûõ ÏËÈÑ òèïà FPGA [7, 8]. Óñëîâèìñÿ
èñïîëüçîâàòü îáîçíà÷åíèå ÏËÈÑ äëÿ FPGA, îáîçíà÷åíèå ËÝ — äëÿ LUT è
îáîçíà÷åíèå ÂÁÏ (âñòðîåííûé áëîê ïàìÿòè) — äëÿ EMB. Äëÿ óìåíüøåíèÿ
÷èñëà ËÝ â ñõåìå ÓÓ íåîáõîäèìî óìåíüøàòü êàê ÷èñëî àðãóìåíòîâ â ðåàëè-
çóåìûõ ôóíêöèÿõ, òàê è ÷èñëî ôóíêöèé, çàâèñÿùèõ îò ëîãè÷åñêèõ óñëîâèé.
Äëÿ ðåøåíèÿ ïåðâîé çàäà÷è ïðåäëàãàåòñÿ ïðåîáðàçîâàíèå êîäîâ âõîäîâ îïåðà-
òîðíûõ ëèíåéíûõ öåïåé (ÎËÖ) àëãîðèòìà óïðàâëåíèÿ â êîäû êëàññîâ ïñåâäî-
ýêâèâàëåíòíûõ ÎËÖ. Äëÿ ðåøåíèÿ âòîðîé çàäà÷è ïðåäëàãàåòñÿ ïðåîáðàçîâàíèå
êîäîâ âõîäîâ ÎËÖ â àäðåñà ñîîòâåòñòâóþùèõ èì ìèêðîêîìàíä. Ïðè ýòîì àë-
ãîðèòì óïðàâëåíèÿ ïðåäñòàâëÿåòñÿ â âèäå ãðàô-ñõåìû àëãîðèòìà (ÃÑÀ) [1],
à äëÿ çàäàíèÿ ÓÓ èñïîëüçóåòñÿ ìîäåëü ÊÌÓÓ ñ îáùåé ïàìÿòüþ [6]. Îòìåòèì,
÷òî ïðåäëàãàåìûå ìåòîäû ìîãóò áûòü àäàïòèðîâàíû ê äðóãèì ôîðìàì ïðåä-
ñòàâëåíèÿ àëãîðèòìà è äðóãèì ìîäåëÿì ÊÌÓÓ.
ÌÎÄÅËÜ ÊÌÓÓ Ñ ÎÁÙÅÉ ÏÀÌßÒÜÞ
Ïóñòü àëãîðèòì óïðàâëåíèÿ öèôðîâîé ñèñòåìû ïðåäñòàâëåí â âèäå ÃÑÀ �, êî-
òîðàÿ õàðàêòåðèçóåòñÿ ìíîæåñòâàìè âåðøèí B E E b bE� � �1 2 0{ }, è äóã E,
ñîåäèíÿþùèõ ýòè âåðøèíû. Çäåñü E1 — ìíîæåñòâî îïåðàòîðíûõ âåðøèí, ñîäåð-
æàùèõ íàáîðû ìèêðîîïåðàöèé èç ìíîæåñòâà ìèêðîîïåðàöèé Y y yN� { }1, ,� ;
E2 — ìíîæåñòâî óñëîâíûõ âåðøèí, ñîäåðæàùèõ ýëåìåíòû ìíîæåñòâà ëîãè÷åñ-
êèõ óñëîâèé (ËÓ) X x xL� { }1, ,� ; b0 — íà÷àëüíàÿ âåðøèíà; bE — êîíå÷íàÿ
âåðøèíà ÃÑÀ �. Ââåäåì ðÿä îïðåäåëåíèé [6].
Îïðåäåëåíèå 1. Îïåðàòîðíîé ëèíåéíîé öåïüþ ÃÑÀ � íàçûâàåòñÿ êîíå÷íàÿ
ïîñëåäîâàòåëüíîñòü îïåðàòîðíûõ âåðøèí � g g gb b
Fg
� � �1, ,� òàêàÿ, ÷òî äëÿ ëþ-
áîé ïàðû åå ñîñåäíèõ âåðøèí ñóùåñòâóåò äóãà � ���b b Egi gi, 1 , ãäå
i Fg� 1 1, ,� .
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 107
À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, 2011
Îïðåäåëåíèå 2. Îïåðàòîðíàÿ âåðøèíà b Dq
g� , ãäå D Eg � 1 — ìíîæåñòâî
âåðøèí, âõîäÿùèõ â ÃÑÀ �, íàçûâàåòñÿ âõîäîì ÎËÖ � g , åñëè ñóùåñòâóåò äóãà
� ��b b Et q, , ãäå b Dt
g� .
Îïðåäåëåíèå 3. Îïåðàòîðíàÿ âåðøèíà b Dq
g� íàçûâàåòñÿ âûõîäîì ÎËÖ
� g , åñëè ñóùåñòâóåò äóãà � ��b b Eq t, , ãäå b Dt
g� .
Îïðåäåëåíèå 4. Öåïè � i è � j íàçûâàþòñÿ ïñåâäîýêâèâàëåíòíûìè ÎËÖ,
åñëè èõ âûõîäû ñâÿçàíû ñ âõîäîì îäíîé è òîé æå âåðøèíû ÃÑÀ �.
Ëþáàÿ ÎËÖ � g èìååò ïðîèçâîëüíîå ÷èñëî âõîäîâ, îáîçíà÷àåìûõ
I k Fg
k
g( , , )�1 � è îáðàçóþùèõ ìíîæåñòâî I g , è òî÷íî îäèí âûõîä, îáîçíà÷àå-
ìûé ñèìâîëîì Og .
Ïóñòü äëÿ ÃÑÀ � ïîëó÷åíî ìíîæåñòâî ÎËÖ C G� { }� �1, ,� , ñîîòâåòñòâóþ-
ùåå ðàçáèåíèþ ìèíèìàëüíîé ìîùíîñòè ìíîæåñòâà E1 íà G êëàññîâ, êàæäûé èç
êîòîðûõ îòâå÷àåò îïðåäåëåíèþ 1.
Îïðåäåëåíèå 5. Ãðàô-ñõåìà àëãîðèòìà � ÿâëÿåòñÿ ëèíåéíîé, åñëè ÷èñëî åå
îïåðàòîðíûõ âåðøèí íå ìåíåå ÷åì â äâà ðàçà ïðåâîñõîäèò ìèíèìàëüíî âîçìîæ-
íîå ÷èñëî G åå ÎËÖ.
Ïóñòü I ( )� , Î ( )� — ñîîòâåòñòâåííî ìíîæåñòâî âõîäîâ è âûõîäîâ ÎËÖ
� g C� . Êàæäàÿ âåðøèíà b Eq � 1 ñîîòâåòñòâóåò ìèêðîêîìàíäå, èìåþùåé àäðåñ
A bq( ). Îñóùåñòâèì àäðåñàöèþ ìèêðîêîìàíä òàê, ÷òîáû âûïîëíÿëîñü óñëîâèå
A b A bgi gi( ) ( )� � �1 1, (1)
ãäå g G�{ }1, ,� , i Fg� { }1 1, ,� .  ýòîì ñëó÷àå ÃÑÀ � ìîæåò áûòü èíòåðïðå-
òèðîâàíà ÊÌÓÓ U 1 [7], ñòðóêòóðíàÿ ñõåìà êîòîðîãî ïðèâåäåíà íà ðèñ. 1.
Ýòî óñòðîéñòâî âêëþ÷àåò áëîê àäðåñàöèè ìèêðîêîìàíä (ÁÀÌ), ñ÷åò÷èê
(Ñò), áëîê ìèêðîîïåðàöèé (ÁÌÎ) è òðèããåð âûáîðêè (ÒÂ). ÊÌÓÓU 1 ôóíêöèîíè-
ðóåò ñëåäóþùèì îáðàçîì.
Ïî ñèãíàëó Start â Ñò çàïèñûâàåòñÿ íóëåâîé àäðåñ, ñîîòâåòñòâóþùèé íà÷àëó
ìèêðîïðîãðàììû, èíòåðïðåòèðóþùåé ÃÑÀ �. Îäíîâðåìåííî ÒÂ óñòàíàâëèâàåò-
ñÿ â åäèíè÷íîå ñîñòîÿíèå (Fetch �1) è ìèêðîêîìàíäû ìîãóò âûáèðàòüñÿ èç ÁÌÎ.
Åñëè Ñò ñîäåðæèò àäðåñ A bq( ) è b Îq � ( )� , òî îäíîâðåìåííî ñ íàáîðîì ìèê-
ðîîïåðàöèé Y bq( ), çàïèñàííûõ â âåðøèíå b Eq � 1, ÁÌÎ ôîðìèðóåò ñèãíàë y0 .
Åñëè y0 1� , òî ñîäåðæèìîå Ñò óâåëè÷èâàåòñÿ ïî ñèãíàëó Clock. Ïðè ýòîì ïðîèñ-
õîäèò áåçóñëîâíûé ïåðåõîä, ñîîòâåòñòâóþùèé (1). Åñëè b Îq � ( )� , òî ñèãíàë y0 íå
108 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Ðèñ. 1
Áëîê
àäðåñàöèè
ìèêðîêîìàíä
Áëîê
ìèêðî-
îïåðàöèé
Ñò
X
T
+1
Y
R
Start
Clock
S
y
E
TB
y
0
Start
Fetch
ôîðìèðóåòñÿ, à ÁÀÌ âûðàáàòûâàåò ôóíêöèè âîçáóæäåíèÿ Ñò
� ( , )T X . (2)
 ýòîì ñëó÷àå ïî ñèãíàëó Clock â Ñò ôîðìèðóåòñÿ àäðåñ ïåðåõîäà èç âûõîäà
íåêîòîðîé ÎËÖ � g C� . Åñëè � � �b b Eq E, , òî ÁÌÎ ôîðìèðóåò ñèãíàë yE , âû-
çûâàþùèé óñòàíîâêó â íóëåâîå ñîñòîÿíèå. Ïðè ýòîì Fetch � 0, âûáîðêà ìèêðî-
êîìàíä çàïðåùàåòñÿ è ÊÌÓÓ U 1 ïðåêðàùàåò ôóíêöèîíèðîâàíèå.
Ïðè ðåàëèçàöèè ñõåìû ÊÌÓÓU 1 íà ÏËÈÑ ñõåìà ÁÀÌ, Ñò è ÒÂ ñòðîèòñÿ íà
ëîãè÷åñêèõ ýëåìåíòàõ, à ñõåìà ÁÌÎ ðåàëèçóåòñÿ íà ÂÁÏ. Òàêèì îáðàçîì, ìîäåëü
ïîçâîëÿåò ñáàëàíñèðîâàííî èñïîëüçîâàòü âîçìîæíîñòè ñîâðåìåííûõ ÏËÈÑ. Åå
íåäîñòàòêîì ÿâëÿåòñÿ çíà÷èòåëüíîå ÷èñëî ôóíêöèé îáðàòíîé ñâÿçè T ,
ñîâïàäàþùåå ñ ðàçðÿäíîñòüþ àäðåñà ìèêðîêîìàíäû
R MA � � �log 2 ,
ãäå M E� | |1 . Â íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ ñîâìåñòíîå èñïîëüçîâàíèå ìåòî-
äîâ ñòðóêòóðíîé äåêîìïîçèöèè (ïðåäñòàâëåíèå áëîêîâ ìîäåëè â âèäå êîìïîçè-
öèè ïîäáëîêîâ) è ïðåîáðàçîâàíèÿ êîäîâ áëîêîâ, îñíîâû êîòîðûõ èçëîæåíû â [9].
ÎÑÍÎÂÍÀß ÈÄÅß ÏÐÅÄËÀÃÀÅÌÛÕ ÌÅÒÎÄÎÂ
Ôóíêöèè (2) îòíîñÿòñÿ ê êëàññó íåðåãóëÿðíûõ ôóíêöèé (i-ôóíêöèé), ò.å. îíè
îïðåäåëåíû íà ìåíåå ÷åì 50% âîçìîæíûõ âõîäíûõ íàáîðîâ [9]. Ïðè ðåàëèçà-
öèè i-ôóíêöèé íà ËÝ âîçíèêàåò ïðîáëåìà, ñâÿçàííàÿ ñî çíà÷èòåëüíûì ïðåâû-
øåíèåì ÷èñëà àðãóìåíòîâ ôóíêöèé (äî 50) ÷èñëà âõîäîâ ËÝ (äî 6) ñîâðåìåí-
íûõ ÏËÈÑ [7, 8], ÷òî ïðèâîäèò ê íåîáõîäèìîñòè ôóíêöèîíàëüíîé äåêîì-
ïîçèöèè i-ôóíêöèé [2, 3]. Áëîê ìèêðîîïåðàöèé ÊÌÓÓ U 1 ðåàëèçóåò ôóíê-
öèè � � �Y Y T( ). Ýòè ôóíêöèè ÿâëÿþòñÿ ðåãóëÿðíûìè (r-ôóíêöèè), è äëÿ èõ ðå-
àëèçàöèè èñïîëüçóþòñÿ ÂÁÏ. Äëÿ óìåíüøåíèÿ ÷èñëà i-ôóíêöèé ïðåäëàãàåòñÿ
ñëåäóþùèé ïîäõîä.
Ïóñòü I ( )� — ìíîæåñòâî âõîäîâ ÎËÖ � g C� , ò.å.
I I g
g
G
( )� �
�1
� ,
è ïóñòü | ( )|I M� � 0 . Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó ýëåìåíòó I Ig
k � ( )�
äâîè÷íûé êîä K I g
k( ) ðàçðÿäíîñòè
R MI � � �log 2 0 .
Èñïîëüçóåì äëÿ êîäèðîâàíèÿ âõîäîâ ÎËÖ ïåðåìåííûå z Zr � , ãäå | |Z RI� .
Î÷åâèäíî, ÷òî ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó êîäàìè
âõîäîâ ÎËÖ è àäðåñàìè ìèêðîêîìàíä, ñîîòâåòñòâóþùèìè ýòèì âõîäàì. Òàêèì
îáðàçîì, ìîæíî íàéòè ôóíêöèþ
� ( )Z , ïîçâîëÿþùóþ ïîëó÷èòü àäðåñà ìèê-
ðîêîìàíä, ñîîòâåòñòâóþùèå âõîäàì, íà îñíîâå êîäîâ ýòèõ âõîäîâ.
Ïóñòü � �C C — ìíîæåñòâî ÎËÖ, âûõîäû êîòîðûõ íå ñâÿçàíû ñ âõîäîì êî-
íå÷íîé âåðøèíû, ò.å. � g C� �, åñëè � g C� , è � � �b b Et E, , ãäå b Ot g� . Ïóñòü
�C IB B= { }1, ,� — ðàçáèåíèå ìíîæåñòâà ÎËÖ �C íà êëàññû ïñåâäîýêâèâà-
ëåíòíûõ ÎËÖ. Ïîñòàâèì â ñîîòâåòñòâèå êàæäîìó êëàññó Bi C�� äâîè÷íûé êîä
K Bi( ) ðàçðÿäíîñòè
R IC � � �log 2 (3)
è èñïîëüçóåì äëÿ êîäèðîâàíèÿ ïåðåìåííûå � �r � , ãäå | |� � RC. Äàëåå ÊÌÓÓ
U 1 ìîæåò áûòü ïðåîáðàçîâàíî â ÊÌÓÓ U 2 (ðèñ. 2).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 109
 ÊÌÓÓ U 2 áëîê êîäèðîâàíèÿ âõîäîâ (ÁÊÂ) ôîðìèðóåò ïåðåìåííûå
Z Z X� ( , )� , êîäèðóþùèå âõîäû I Ig
k � ( )� . Áëîê äåêîäèðîâàíèÿ âõîäîâ è êëàññîâ
(ÁÄÂÊ) ôîðìèðóåò ôóíêöèè
� ( )Z , (4)
� �� ( )Z , (5)
èñïîëüçóåìûå äëÿ ôîðìèðîâàíèÿ â Ñò àäðåñà âõîäà è â Ðã êîäà êëàññà ïñåâ-
äîýêâèâàëåíòíûõ ÎËÖ ñîîòâåòñòâåííî. Îñòàëüíûå áëîêè ÊÌÓÓ U 2 (Ñò,
ÁÌÎ, ÒÂ) èìåþò òî æå íàçíà÷åíèå, ÷òî è â ÊÌÓÓ U 1.
ÓñòðîéñòâîU 2 ôóíêöèîíèðóåò ñëåäóþùèì îáðàçîì. Ïî ñèãíàëó Start â Ñò è
Ðã çàïèñûâàþòñÿ íóëåâûå êîäû, íà÷èíàåòñÿ âûáîðêà ìèêðîêîìàíä èç ÁÌÎ. Åñëè
Ñò ñîäåðæèò àäðåñ A bq( ) è b Îq � ( )� , òî ôîðìèðóåòñÿ ïåðåìåííàÿ y0 . Ïðè ýòîì
ïî ñèãíàëó Clock ñîäåðæèìîå Ñò óâåëè÷èâàåòñÿ íà åäèíèöó, à ñîäåðæèìîå Ðã íå
èçìåíÿåòñÿ. Åñëè b Îq � ( )� , òî ñèãíàë y0 íå ôîðìèðóåòñÿ. Ïî ñèãíàëó Clock ñî-
äåðæèìîå Ñò ìîäèôèöèðóåòñÿ ôóíêöèÿìè (4), à ñîäåðæèìîå Ðã — ôóíêöèÿ-
ìè (5). Åñëè � ��b b Eq E, , òî ôîðìèðóåòñÿ ïåðåìåííàÿ yE è âûáîðêà
ìèêðîêîìàíä ïðåêðàùàåòñÿ.
Ñðàâíåíèå ìîäåëåé U 1 è U 2 ïîêàçûâàåò, ÷òî ÊÌÓÓ U 2 îñíîâàíî íà ñòðóê-
òóðíîé äåêîìïîçèöèè ÁÀÌ è ïðåîáðàçîâàíèè êîäîâ âõîäîâ ÎËÖ â êîäû êëàññîâ
ïñåâäîýêâèâàëåíòíûõ ÎËÖ è àäðåñà âõîäîâ. Ïðè ýòîì ÁÄÂÊ ðåàëèçóåòñÿ íà
ÂÁÏ, ÷òî óìåíüøàåò ÷èñëî ËÝ â ñõåìå ÊÌÓÓ (ïî ñðàâíåíèþ ñ U 1). Ïðè ñèíòåçå
ñõåìû ÊÌÓÓ U 2 èñïîëüçóåòñÿ òîò ôàêò, ÷òî ÷èñëî àäðåñíûõ âõîäîâ S F è âûõî-
äîâ tF áëîêà ïàìÿòè ñîâðåìåííûõ ÏËÈÑ [7, 8] ìîæåò íàñòðàèâàòüñÿ
ïîëüçîâàòåëåì ïðè ñîõðàíåíèè ïîñòîÿííîé åìêîñòè
V tF
S
F
F� 2 . (6)
Áëîê ÁÊÂ èìååò S RI1 � âõîäîâ è t R RA C1 � � âûõîäîâ, ïðè ýòîì
t V R RF
R
A C
I
0 2� �( / ) ( ) (7)
âûõîäîâ áëîêà ÂÁÏ íå èñïîëüçóþòñÿ äëÿ ôîðìèðîâàíèÿ ôóíêöèé
è �.
Ïðè ðåàëèçàöèè ñõåìû ÁÌÎ íà áëîêàõ ÂÁÏ ìîæåò áûòü èñïîëüçîâàíî
t VF
RA
1 2� /
âûõîäîâ äëÿ ôîðìèðîâàíèÿ ìèêðîîïåðàöèé y Yn � �.  îáùåì ñëó÷àå äëÿ ðåà-
110 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Ðèñ. 2
Áëîê
êîäèðîâàíèÿ
âõîäîâ
X
Áëîê
ìèêðî-
îïåðàöèé
Ñò
T
+1
Y
R
Start
Start
S
y
E
TB
y
0
Clock
Áëîê
äåêîäèðîâàíèÿ
âõîäîâ
è êëàññîâ
Pã
Ñlock
y
0�
Start
Z
�
Fetch
�
ëèçàöèè ÁÌÎ òðåáóåòñÿ
n
N
t
1
1
2
�
��
�
�
�
�
� (8)
ÁÂÏ, èìåþùèõ åìêîñòü (6). Åñëè n1 1� , òî t0 ìèêðîîïåðàöèé ìîæíî ðåàëèçî-
âàòü íà ÁÄÂÊ. Ýòî öåëåñîîáðàçíî òîëüêî ïðè âûïîëíåíèè óñëîâèÿ
N t
t
n
� �
�
�
�
�
��
2 0
1
1. (9)
Ðàçîáüåì ìíîæåñòâî �Y íà êëàññû YI è YR , ïðè ýòîì y Yn I� , åñëè è òîëüêî
åñëè ýòà ìèêðîîïåðàöèÿ ôîðìèðóåòñÿ ëèøü ïðè ïåðåõîäå âî âõîäû ÎËÖ � g C� .
 ïðîòèâíîì ñëó÷àå ìèêðîîïåðàöèÿ y Yn R� . Ïðè âûïîëíåíèè óñëîâèé (9) è
t nI0 � , (10)
ãäå n YI I� | |, ÷èñëî ÂÁÏ â ñõåìå ÁÌÎ óìåíüøàåòñÿ íà åäèíèöó. Ýòî ïðèâîäèò
ê ÊÌÓÓ U 3 (ðèñ. 3), ïðèíöèï ôóíêöèîíèðîâàíèÿ êîòîðîãî íå òðåáóåò ïîÿñíåíèÿ.
 íàñòîÿùåå âðåìÿ ÂÁÏ ÿâëÿþòñÿ ñèíõðîííûìè, ÷òî ìîæíî ó÷åñòü ïðè
îáåñïå÷åíèè óñòîé÷èâîñòè ìèêðîîïåðàöèé y Yn I� . Îòìåòèì, ÷òî ÊÌÓÓ U 3 —
÷àñòíûé ñëó÷àé ÊÌÓÓU 2 è ñòàíîâèòñÿ ýêâèâàëåíòíûì, åñëè YI �� èëè åñëè íå
âûïîëíÿåòñÿ õîòÿ áû îäíî èç óñëîâèé — (9) èëè (10). Â íàñòîÿùåé ðàáîòå ïðåä-
ëàãàåòñÿ ìåòîä ñèíòåçà ÊÌÓÓ U 3 , êîòîðûé èëëþñòðèðóåòñÿ íà ïðèìåðå ÃÑÀ �1
(ðèñ. 4).
Äëÿ ðåàëèçàöèè r-ôóíêöèé óñëîâèìñÿ èñïîëüçîâàòü ÂÁÏ ñ êîíôèãóðàöèåé
128 1� , 64 2� , 32 4� ,16 8� , 8 16� áèò, åìêîñòü êîòîðûõVF �128 áèò ïðè tF �1.
ÌÅÒÎÄ ÑÈÍÒÅÇÀ È ÏÐÈÌÅÐ ÅÃÎ ÏÐÈÌÅÍÅÍÈß
Ïðåäëàãàåìûé ìåòîä ñèíòåçà âêëþ÷àåò ñëåäóþùèå ýòàïû:
1) ôîðìèðîâàíèå ìíîæåñòâ ÎËÖ C, âõîäîâ I ( )� , âûõîäîâ O( )� è �Ñ äëÿ
ÃÑÀ �;
2) ëèíåéíàÿ àäðåñàöèÿ ìèêðîêîìàíä;
3) ðàçáèåíèå ìíîæåñòâà �Y ;
4) êîäèðîâàíèå âõîäîâ ÎËÖ � g C� ;
5) êîäèðîâàíèå êëàññîâ Bi C� � ;
6) ñïåöèôèêàöèÿ ÁÊÂ;
7) ñïåöèôèêàöèÿ ÁÄÂÊ;
8) ñïåöèôèêàöèÿ ÁÌÎ;
9) ðåàëèçàöèÿ ñõåìû ÊÌÓÓ â çàäàííîì ýëåìåíòíîì áàçèñå.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 111
Ðèñ. 3
Áëîê
êîäèðîâàíèÿ
âõîäîâ
X
Áëîê
ìèêðî-
îïåðàöèé
Ñò
T
+1
YR
R
Start
Start
y
E
TB
y
0
Clock
Pã
Ñlock
Start
Z
�
Fetch
�
Áëîê
äåêîäèðîâàíèÿ
âõîäîâ
è êëàññîâ
YI
S
y
0�
Âûïîëíåíèå ïåðâîãî ýòàïà íå âûçûâàåò òðóäíîñòåé è âûïîëíÿåòñÿ ïî ìå-
òîäèêå [6]. Äëÿ ÃÑÀ �1 ôîðìèðóåòñÿ ìíîæåñòâî C � { }� �1 7, ,� , ãäå �1 �
�� �b b1 2, , I b
1
1
1� , O b1 2� ; � 2 3 6�� �b b, ,� , I b
2
1
3� , I b
2
2
5� , I O b
2
3
2 6� � ;
� 3 7 11�� �b b, ,� , I b
3
1
7� , O b3 11� ; � 4 12 15�� �b b, ,� , I b
4
1
12� , I b
4
2
14� ,
O b4 15� ; � 5 16 17�� �b b, , I b
5
1
16� , I O b
5
2
5 17� � ; � 6 18 19�� �b b, , I b
6
1
18� ,
112 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Start
End
1
y1 y2 b1
b0
y3 b2
x1
x3 x2
0
y1 y4
y5
y6
0
1
b4
b3
b5
y2 y7 b6
y3 y5
y4
y2 y7
b8
b7
b9
y3 b10
1
y1 y3 y4
y2
y6 y7
b13
b12
b14
y3 y7 b15
0
y2 y7 b11
1 x3
x5 x4
0
0
1
1
0
y4 b18
y3 y7 b19
y1 y5 b16
y2 y6 b17
1 x5
0
y2 y5 b20
bE
Ðèñ. 4
O b6 19� ; � 7 20�� �b , I O b
7
1
7 20� � . Àíàëèç ìíîæåñòâà C ïîêàçûâàåò, ÷òî äëÿ
ÃÑÀ �1 M � 20, RA � 5, T T T� { }1 5, ,� ,
� { }D D1 5, ,� , I b b b b( ) , , , ,�1 1 3 5 6� {
b b b b b b b7 12 14 16 17 18 20, , , , , , }, ò.å. M 0 11� , RI � 4, Z z z� { }1 4, ,� . Èñïîëüçóÿ îïðå-
äåëåíèå ïñåâäîýêâèâàëåíòíûõ ÎËÖ, ìîæíî íàéòè ðàçáèåíèå �C B B B= { }1 2 3, , , ãäå
B1 1� { }� , B2 2 3 4� { }� � �, , , B3 5 6� { }� �, . Îòìåòèì, ÷òî � 7 � �C . Àíàëèç ðàçáè-
åíèÿ �Ñ ïîêàçûâàåò, ÷òî I � 3, RC � 2, � � �� { }1 2, , � � { }D D6 7, . Êðîìå òîãî,
ïðåäïîëàãàåòñÿ èñïîëüçîâàíèå â Ñò è Ðã èíôîðìàöèîííûõ âõîäîâ òèïà D, ÷òî ñî-
îòâåòñòâóåò ñîâðåìåííûì òåíäåíöèÿì ðåàëèçàöèè ÓÓ [10]. Â âåðøèíàõ ÃÑÀ �1
çàïèñàíû N � 7 ìèêðîîïåðàöèé, ò.å. | ' |Y � 9.
Ëèíåéíàÿ àäðåñàöèÿ ìèêðîêîìàíä ñîîòâåòñòâóåò óñëîâèþ (1) è âûïîëíÿåòñÿ
òðèâèàëüíûì îáðàçîì [6]. Äëÿ ÃÑÀ �1 èìååì A b A b( ) , , ( )1 2000000 10100� �� .
Ðàññìîòðèì öåëåñîîáðàçíîñòü ðàçáèåíèÿ ìíîæåñòâà �Y äëÿ ïðèâåäåííîãî
ïðèìåðà. Òàê êàê RA � 5, íåîáõîäèìî âûáðàòü êîíôèãóðàöèþ ÂÁÏ 32 4� , ò.å.
t1 4� . Èç óñëîâèÿ (8) ñëåäóåò, ÷òî äëÿ ðåàëèçàöèè N � �2 9 âûõîäîâ ÁÌÎ òðåáó-
åòñÿ n1 3� ÂÁÏ. Ïîñêîëüêó RI � 4, äëÿ ðåàëèçàöèè ÁÄÂÊ âûáèðàåòñÿ êîíôèãóðà-
öèÿ 16 8� , ò.å. tF � 8. Èç âûðàæåíèÿ (7) ñëåäóåò, ÷òî t0 1� , ïðè ýòîì óñëîâèå (9)
âûïîëíÿåòñÿ. Òàêèì îáðàçîì, åñëè îäíà èç ìèêðîîïåðàöèé y Yn � ìîæåò áûòü
îòíåñåíà â ìíîæåñòâî YI , òî ÷èñëî ÂÁÏ â ñõåìå ÁÌÎ óìåíüøèòñÿ äî n1 2� .
Èç àíàëèçà îïåðàòîðíûõ âåðøèí ÃÑÀ �1 ñëåäóåò, ÷òî ìèêðîîïåðàöèÿ y Y1 �
åñòü â âåðøèíàõ b1, b3 , b12 è b16 . Ýòè âåðøèíû ÿâëÿþòñÿ ýëåìåíòàìè ìíîæåñòâà
I ( )�1 . Èòàê, íàéäåíî ðàçáèåíèå Y yI � { }1 , Y y yR � { }2 7, ,� .
Êîäèðîâàíèå âõîäîâ âåðøèí b Iq � ( )� ìîæåò áûòü âûïîëíåíî ïðîèçâîëü-
íûì îáðàçîì. Îäèí èç âîçìîæíûõ âàðèàíòîâ ïðèâåäåí â òàáë. 1. Â äàííîé òàáëè-
öå è äàëåå ñèìâîë U i j( )� îçíà÷àåò, ÷òî ìîäåëü ÊÌÓÓ U i èñïîëüçóåòñÿ äëÿ èí-
òåðïðåòàöèè ÃÑÀ � j .
Êîäèðîâàíèå êëàññîâ Bi Ñ�� òàêæå âûïîëíÿåòñÿ ïðîèçâîëüíûì îáðàçîì.
Ïóñòü äëÿ ÊÌÓÓ U 3 1( )� ïðèíÿòû ñëåäóþùèå êîäû: K B( )1 00� , K B( )2 01� è
K B( )3 10� .
Äëÿ ñïåöèôèêàöèè ÂÁÏ ïðåäëàãàåòñÿ ïðîöåäóðà ïîñòðîåíèÿ:
1) ñèñòåìû ôîðìóë ïåðåõîäà äëÿ âõîäîâ ÎËÖ � g C� �;
2) ñèñòåìû îáîáùåííûõ ôîðìóë ïåðåõîäà;
3) òàáëèöû ÂÁÏ;
4) ñèñòåìû (3) íà îñíîâå òàáëèöû ÂÁÏ.
Ñèñòåìà ôîðìóë ïåðåõîäà [1] äëÿ ðàññìàòðèâàåìîãî ïðèìåðà èìååò ñëåäóþ-
ùèé âèä:
b x x b x x b x x b x x b2 1 3 5 1 3 3 1 2 7 1 2 12� � � � ;
b x x b x x b x x b x x b6 3 5 6 1 5 16 3 4 18 3 4 14� � � � ;
b x x b x x b x x b x x b11 3 5 6 1 5 16 3 4 18 3 4 14� � � � ;
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 113
I g
k
bq
K I g
k( ) I g
k bq K I g
k( )
I1
1 b1 0000 I 4
2 b14 0110
I 2
1 b3 0001 I 5
1 b16 0111
I 2
2 b5 0010 I 5
2 b17 1000
I 2
3 b6 0011 I 6
1 b18 1001
I 3
1 b7 0100 I 7
1 b20 1010
I 4
1 b12 0101 – – 1011
Ò à á ë è ö à 1
b x x b x x b x x b x x b15 3 5 6 1 5 16 3 4 18 3 4 14� � � � ;
b x b x b17 5 17 5 20� � ;
b x b x b15 5 17 5 20� � . (11)
Äëÿ ïîñòðîåíèÿ ñèñòåìû îáîáùåííûõ ôîðìóë ïåðåõîäà [6] íåîáõîäèìî çà-
ìåíèòü âåðøèíû b Oq � ( )� îáîçíà÷åíèÿìè êëàññîâ Bi C� � , â êîòîðûå âõîäÿò
òàêèå ÎËÖ. Åñëè ïðè ýòîì ñèñòåìà òèïà (11) ñîäåðæèò i îäèíàêîâûõ ôîðìóë, òî
( )i 1 èç íèõ óäàëÿþòñÿ. Âåðøèíû â ëåâîé ÷àñòè ôîðìóë íåîáõîäèìî çàìåíèòü
îáîçíà÷åíèÿìè ñîîòâåòñòâóþùèõ âõîäîâ. Íàïðèìåð, èç ñèñòåìû (11) èìååì
B x x I x x I x x I x x I1 1 3 2
2
1 3 2
1
1 2 3
1
1 2 4
1� � � � ;
B x x I x x I x x I x x I2 3 5 2
3
3 5 5
1
3 4 6
1
3 4 4
2� � � � ;
B x I x I3 5 5
2
5 7
1� � . (12)
Òàáëèöà ÁÊÂ ñòðîèòñÿ ïî ñèñòåìå îáîáùåííûõ ôîðìóë ïåðåõîäà è èìååò
ñëåäóþùèå ñòîëáöû: Bi , K Bi( ), I g
k , K I g
k( ), X h , Zh , h. Ñòîëáåö Zh ñîäåðæèò ïåðå-
ìåííûå z Zr � , ðàâíûå åäèíèöå â êîäå K I g
k( ), äëÿ ñòðîêè h òàáëèöû, ãäå
h H�1 0, ,� . Äëÿ ÁÊÂ ÊÌÓÓU 3 1( )� äàííàÿ òàáëèöà èìååò H 0 10� ñòðîê (òàáë. 2).
Ñâÿçü òàáë. 2 ñ ñèñòåìîé (12) î÷åâèäíà, ïðè ýòîì êîäû K I g
k( ) âçÿòû èç
òàáë. 1. Ôóíêöèè z Zr � ôîðìèðóþòñÿ â âèäå
z C F r Rr
h
H
rh h I� � �
�1
0
1( , , )� ,
(13)
ãäå Crh — áóëåâà ïåðåìåííàÿ, ðàâíàÿ åäèíèöå, åñëè è òîëüêî åñëè ïåðåìåííàÿ
zr çàïèñàíà â ñòðîêå h òàáëèöû. Òåðìû Fh ñèñòåìû (13) îïðåäåëÿþòñÿ ñëåäó-
þùèì îáðàçîì:
F X h Hh
r
R
r
l
h
C
rh� �
�
�
!
"
#
#
�
�1
01� ( , , )� . (14)
 âûðàæåíèè (14) lrh � { }0 1, — çíà÷åíèå r-ãî ðàçðÿäà êîäà K Bi( ) èç ñòðîêè h
òàáëèöû, � �r r
0 � , � �r r Cr R1 1� �( , , )� . Òàê, èç òàáë. 2, íàïðèìåð, èìååì
114 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
Bi
K Bi( ) I g
k K I g
k( ) Ìíîæåñòâî
óñëîâèé, X h
z Zr h� Íîìåð
ñòðîêè, h
B1 00
I 2
2 0010 x x1 3 z3 1
I 2
1 0001 x x1 3 z4 2
I 3
1 0100 x x1 2 z2 3
I 4
1 0101 x x1 2 z z2 4 4
B2 01
I 2
3 0011 x x3 5 z z3 4 5
I 5
1 0111 x x3 5 z z z2 3 4 6
I 6
1 1001 x x3 4 z z1 4 7
I 4
2 0110 x x3 4 z z2 3 8
B3 10
I 5
2 1000 x5 z1 9
I 7
1 1010 x5 z z1 3 10
Ò à á ë è ö à 2
z F F F x x1 7 9 10 1 2 3 4 1 2� � � � �� � � � ;
z F F F F x x x x x2 3 4 6 8 1 2 1 1 2 3 5 1 2 3 4� � � � � � �� � � � � � .
Äëÿ ñïåöèôèêàöèè ÁÄÂÊ íåîáõîäèìî ïîñòðîèòü òàáëèöó ñî ñòîëáöàìè: I g
k ,
K I g
k( ), A I g
k( ), K Bi( ), YI , h, ãäå k
RI�1 2, ,� . Ïðè ýòîì êîä K I g
k( ) ðàññìàòðèâàåò-
ñÿ êàê àäðåñ ÂÁÏ, à îñòàëüíàÿ èíôîðìàöèÿ ÿâëÿåòñÿ âûõîäíîé. Äëÿ ÊÌÓÓ
U 3 1( )� äàííàÿ òàáëèöà èìååò 16 ñòðîê. Çäåñü ïîêàçàíû òîëüêî ïåðâûå 11, îñòàëü-
íûå ñëîâà ÂÁÏ äëÿ ÁÄÂÊ íå èñïîëüçóþòñÿ (òàáë. 3). Íàïðèìåð, âòîðàÿ ñòðîêà
òàáëèöû ñîîòâåòñòâóåò âåðøèíå b E3 1� . Ýòîé âåðøèíå ñîîòâåòñòâóåò àäðåñ
A b( )3 00010� , êîòîðûé çàíîñèòñÿ â ñòîëáåö A I g
k( ). Äàííàÿ âåðøèíà âõîäèò
â ÎËÖ � 2 2�B , ïîýòîìó â ñòîëáöå K Bi( ) çàïèñûâàåòñÿ êîä K B( )2 . Â âåðøèíå b3
çàïèñàíà ìèêðîîïåðàöèÿ y1, ïîýòîìó â ñòîëáöå YI âî âòîðîé ñòðîêå ïèøåòñÿ åäè-
íèöà. Ïîäîáíûé àíàëèç îñóùåñòâëÿåòñÿ ïðîèçâîëüíî äëÿ âñåõ âåðøèí b Iq � ( )�1 .
Äëÿ âåðøèí-âûõîäîâ ÎËÖ � g C� ' êîä K Bi( ) íå èìååò çíà÷åíèÿ, ïîýòîìó
ñòîëáåö K Bi( ) ñîäåðæèò êîä 00 äëÿ 11-é ñòðîêè òàáë. 3.
Äëÿ ñïåöèôèêàöèè áëîêà ÁÌÎ íåîáõîäèìî ïîñòðîèòü òàáëèöó ñî ñòîëáöàìè
bq , A bq( ), y0 , YR , yE , h, èìåþùóþ 2
RA ñòðîê. Çàïîëíåíèå ñòðîêè, ñîîòâåòñòâóþ-
ùåé âåðøèíå b Eq � 1, âûïîëíÿåòñÿ ñëåäóþùèì îáðàçîì:
1) åñëè b Oq g$ , òî â ñòîëáåö y0 çàíîñèòñÿ åäèíèöà;
2) åñëè b bq E� , òî â ñòîëáåö yE çàíîñèòñÿ åäèíèöà;
3) åñëè ìèêðîîïåðàöèÿ y Yn R� çàïèñàíà â âåðøèíå bq , òî â ñòîëáöå YR ñî-
îòâåòñòâóþùèé áèò ðàâåí åäèíèöå.
 òàáë. 4 ïðåäñòàâëåí ôðàãìåíò òàáëèöû ñïåöèôèêàöèè — ïåðâûå âîñåìü
ñòðîê, îïðåäåëÿþùèå ÁÌÎ ÊÌÓÓ U 3 1( )� .
Ñèíòåç ëîãè÷åñêîé ñõåìû ÊÌÓÓ U 3 ñâîäèòñÿ ê ðåàëèçàöèè ñèñòåìû (13) íà
ëîãè÷åñêèõ ýëåìåíòàõ è ðåàëèçàöèè òàáëèö âèäà òàáë. 3, 4 íà âñòðîåííûõ áëîêàõ
ïàìÿòè. Äëÿ ðåøåíèÿ ýòîé çàäà÷è íåîáõîäèìî èñïîëüçîâàòü ñòàíäàðòíûå ïàêåòû
[7, 8]. Â äàííîé ñòàòüå ýòîò ýòàï íå ðàññìàòðèâàåòñÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 115
I g
k
K I g
k( ) A I g
k( ) K Bi( ) YI
Íîìåð
ñòðîêè, h
I1
1 0000 00000 00 1 1
I 2
1 0001 00010 01 1 2
I 2
2 0010 00100 01 0 3
I 2
3 0011 00101 01 0 4
I 3
1 0100 00110 01 0 5
I 4
1 0101 01011 01 1 6
I 4
2 0110 01101 01 0 7
I 5
1 0111 01111 10 1 8
I 5
2 1000 10000 10 0 9
I 6
1 1001 10001 10 0 10
I 7
1 1010 10011 00 0 11
Ò à á ë è ö à 3
ÈÑÑËÅÄÎÂÀÍÈÅ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÏÐÅÄËÎÆÅÍÍÛÕ ÌÅÒÎÄÎÂ
Äëÿ èññëåäîâàíèÿ ñðàâíèòåëüíîé ýôôåêòèâíîñòè ÊÌÓÓ U U1 3 ðàçðàáîòàíî
ïðîãðàììíîå îáåñïå÷åíèå, ÿâëÿþùååñÿ ðàñøèðåíèåì ñèñòåìû ATOMIC [11].
Äëÿ èññëåäîâàíèé áûëà ñîçäàíà áèáëèîòåêà òåñòîâûõ ÃÑÀ, ïðåäñòàâëåííûõ
â ôîðìàòå, ïðèâåäåííîì â [1]. Ïðîãðàììíûå ìîäóëè ãåíåðèðóþò ìîäåëè
ÊÌÓÓ íà ÿçûêå Verilog. Äàëåå ýòè îïèñàíèÿ ÿâëÿþòñÿ îñíîâîé äëÿ ñèíòåçà
ñõåìû ÊÌÓÓ ñ èñïîëüçîâàíèåì ñèñòåìû XST ôèðìû Xilinx [8]. Â òàáë. 5
ïðèâåäåíû ðåçóëüòàòû èññëåäîâàíèé äëÿ ìîäåëåé êëàññè÷åñêîãî àâòîìàòà
Ìóðà, ïàìÿòü êîòîðîãî ðåàëèçîâàíà íà ðåãèñòðå, à ñèñòåìà ìèêðîîïåðàöèé —
íà ÂÁÏ, à òàêæå ÊÌÓÓ U 1 è U 2 . Ýòè äàííûå ïîëó÷åíû äëÿ ìèêðîñõåìû
XC2VP30 (Xilinx Virtex-II Pro family) [8]. Èññëåäîâàíèÿ ïðîâîäèëèñü äëÿ 150
ðàçëè÷íûõ ÃÑÀ, íî â òàáë. 5 ïðèâåäåíû ðåçóëüòàòû òîëüêî äëÿ 15 èç íèõ.
Çäåñü óêàçàíû ÷èñëî ëîãè÷åñêèõ óñëîâèé L, ÷èñëî ìèêðîîïåðàöèé N è ÷èñëî
îïåðàòîðíûõ âåðøèí M äëÿ êàæäîé òåñòîâîé ÃÑÀ. Ñèìâîëîì FSM îáîçíà÷åí
êëàññè÷åñêèé àâòîìàò Ìóðà. Äëÿ êàæäîãî èññëåäóåìîãî ÓÓ óêàçàíî èñïîëüçó-
åìîå ÷èñëî ËÝ òàáëè÷íîãî òèïà è ÷èñëî ÂÁÏ. Îòìåòèì, ÷òî ðåçóëüòàòû èñ-
ñëåäîâàíèé â çíà÷èòåëüíîé ìåðå çàâèñÿò îò ìåòîäîâ ôóíêöèîíàëüíîé äåêîì-
ïîçèöèè è êîäèðîâàíèÿ ñîñòîÿíèé àâòîìàòà. Ñóùåñòâåííî íà íèõ âëèÿåò
òàêæå ÷èñëî êëàññîâ ïñåâäîýêâèâàëåíòíûõ ÎËÖ: ÷åì ìåíüøå êëàññîâ, òåì
ëó÷øå ðåçóëüòàò. Òàêèì îáðàçîì, ðåçóëüòàòû ñèíòåçà çàâèñÿò îò ìíîãèõ ôàê-
òîðîâ (ìåòîäîâ äåêîìïîçèöèè è êîäèðîâàíèÿ, õàðàêòåðèñòèê àëãîðèòìà óïðàâ-
ëåíèÿ, ïàðàìåòðîâ ýëåìåíòíîãî áàçèñà).
Ðåçóëüòàòû èññëåäîâàíèé ïîêàçûâàþò, ÷òî äëÿ ëèíåéíûõ ÃÑÀ ïðèìåíåíèå
ìîäåëè ÊÌÓÓ öåëåñîîáðàçíî, òàê êàê ïîçâîëÿåò óìåíüøèòü ÷èñëî èñïîëüçóå-
ìûõ ËÝ. Íàïîìíèì, ÷òî ñîãëàñíî îïðåäåëåíèþ 5 ÃÑÀ � ÿâëÿåòñÿ ëèíåéíîé, åñëè
âûïîëíÿåòñÿ óñëîâèå M G � 2.
Êàê âèäíî èç òàáë. 5, ïåðåõîä îò ìîäåëè FSM ê ìîäåëè ÊÌÓÓ U 1 ìîæåò ñî-
ïðîâîæäàòüñÿ ðîñòîì ÷èñëà ËÝ. Ýòîò ôàêò îáúÿñíÿåòñÿ òåì, ÷òî ËÝ èñïîëüçóþò-
ñÿ è äëÿ ðåàëèçàöèè ñ÷åò÷èêà. Ïðè ýòîì ÷èñëî ËÝ â ñõåìå Ñò çàâèñèò êàê îò ðàç-
ðÿäíîñòè àäðåñà ìèêðîêîìàíäû, òàê è îò èñïîëüçóåìîãî òèïà ïåðåíîñà ìåæäó
ðàçðÿäàìè. Àíàëèç òàáë. 5 ïîêàçûâàåò, ÷òî ÷èñëî ËÝ â ñõåìå ÊÌÓÓ U 3 âñåãäà
ìåíüøå ÷èñëà ËÝ äëÿ ìîäåëåé FSM è U 1. Ïðè ýòîì ÷èñëî ÂÁÏ íà åäèíèöó áîëü-
øå, ÷òî îáúÿñíÿåòñÿ íåîáõîäèìîñòüþ ðåàëèçàöèè ÁÄÂÊ. Îòìåòèì, ÷òî ìîäåëü
U 3 ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì ìîäåëè U 2 , ïîýòîìó â òàáë. 5 èñïîëüçóåòñÿ òîëüêî
îäíî îáîçíà÷åíèå (U 3), õîòÿ ðåçóëüòàòû ïðèâåäåíû äëÿ òîé ìîäåëè, êîòîðàÿ
ìîæåò áûòü ðåàëèçîâàíà äëÿ äàííîé ÃÑÀ.
116 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
bq A bq( ) y
0
YR y
E h
b1 00000 1 1000000 0 1
b2 00001 0 010000 0 2
b3 00010 1 001000 0 3
b4 00011 1 000100 0 4
b5 0100 1 000010 0 5
b6 00101 0 100001 0 6
b7 00110 1 010100 0 7
b8 00111 1 001000 0 8
Ò à á ë è ö à 4
 òàáë. 6 ïðåäñòàâëåíû ðåçóëüòàòû ñðàâíåíèÿ ÷èñëà ËÝ â ñõåìàõ ÓÓ òèïà
FSM è U 1 è ÷èñëà ËÝ ÊÌÓÓ U 2 , ïîëó÷åííûå íà îñíîâå òàáë. 5. Êàê âèäèì,
â ñðåäíåì èñïîëüçîâàíèå ìîäåëè ÊÌÓÓ U 3 ïîçâîëÿåò óìåíüøèòü êîëè÷åñòâî ËÝ
íà 59% ïî ñðàâíåíèþ ñ èõ ÷èñëîì äëÿ êëàññè÷åñêîãî àâòîìàòà Ìóðà è íà 39% ïî
ñðàâíåíèþ ñ êîëè÷åñòâîì ËÝ â ÊÌÓÓU 2 . Òàêèå æå ðåçóëüòàòû áûëè ïîëó÷åíû è
äëÿ âñåõ 150 ÃÑÀ. Çàìåòèì, ÷òî ðåçóëüòàòû áóäóò èíûìè, åñëè èñïîëüçóþòñÿ äðó-
ãèå ñèñòåìû ñèíòåçà. Îäíàêî èç òàáë. 5 ñëåäóåò, ÷òî ìîäåëü U 3 ÿâëÿåòñÿ ýôôåê-
òèâíîé äëÿ ðåàëèçàöèè ñõåì ÓÓ ïî ëèíåéíûì àëãîðèòìàì óïðàâëåíèÿ.
ÇÀÊËÞ×ÅÍÈÅ
 ðàáîòå ðàññìàòðèâàåòñÿ ñîâìåñòíîå ïðèìåíåíèå ìåòîäîâ ñòðóêòóðíîé äå-
êîìïîçèöèè áëîêà àäðåñàöèè ìèêðîêîìàíä è ïðåîáðàçîâàíèÿ êîäîâ âõîäîâ
ÎËÖ â êîäû êëàññîâ ïñåâäîýêâèâàëåíòíûõ ÎËÖ è àäðåñà ìèêðîêîìàíä. Ïðåä-
ëàãàåìûé ìåòîä îðèåíòèðîâàí íà óìåíüøåíèå ÷èñëà ëîãè÷åñêèõ ýëåìåíòîâ
â ñõåìå ÊÌÓÓ, ðåàëèçóåìîé â áàçèñå ÏËÈÑ ïî ëèíåéíîé ÃÑÀ. Ýòà öåëü äîñ-
òèãàåòñÿ çà ñ÷åò óâåëè÷åíèÿ ÷èñëà ðåãóëÿðíûõ ôóíêöèé, äëÿ ðåàëèçàöèè êîòî-
ðûõ ìîæíî èñïîëüçîâàòü âñòðîåííûå áëîêè ïàìÿòè. Êðîìå òîãî, êîäèðîâàíèå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5 117
Ñîîòíîøåíèå
Ðåçóëüòàò ñîîòíîøåíèÿ äëÿ ÃÑÀ
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Ñðåäíåå
çíà÷åíèå, %
FSM U 3 58 63 67 63 60 40 41 67 67 64 65 64 65 52 59 59
U U1 3 57 61 55 62 64 46 60 26 34 17 18 16 30 32 22 39
Ò à á ë è ö à 6
Íîìåð
ÃÑÀ
Ðåçóëüòàòû ñèíòåçà
Õàðàêòåðèñòèêè ÃÑÀ FSM U 1 U 3
L M N ËÝ ÂÁÏ ËÝ ÂÁÏ ËÝ ÂÁÏ
1 10 9 85 80 1 83 1 34 2
2 10 9 89 51 1 85 1 33 2
3 13 12 92 126 1 94 1 42 2
4 11 10 71 100 1 96 1 37 2
5 9 10 72 81 1 88 1 32 2
6 8 9 53 47 1 52 1 28 2
7 8 12 68 49 1 71 1 29 2
8 65 18 153 642 1 283 1 211 2
9 35 152 100 361 5 176 5 117 6
10 52 222 151 482 7 208 7 173 8
11 52 152 151 486 5 207 5 171 6
12 52 452 151 486 13 204 13 172 14
13 11 42 154 114 2 58 2 41 3
14 11 42 188 108 2 76 2 52 3
15 14 44 207 134 2 71 2 56 3
Ò à á ë è ö à 5
êëàññîâ ïñåâäîýêâèâàëåíòíûõ ÎËÖ äàåò âîçìîæíîñòü óìåíüøèòü ÷èñëî àðãó-
ìåíòîâ â íåðåãóëÿðíûõ ôóíêöèÿõ, ðåàëèçóåìûõ íà ËÝ òàáëè÷íîãî òèïà.
Ïðîâåäåííûå èññëåäîâàíèÿ ïîêàçàëè, ÷òî ïðåäëîæåííûé ìåòîä ïîçâîëÿåò
óìåíüøèòü ÷èñëî ËÝ ïî ñðàâíåíèþ êàê ñ êëàññè÷åñêîé ìîäåëüþ àâòîìàòà Ìóðà,
òàê è ñ ÊÌÓÓ ñ îáùåé ïàìÿòüþ. Âûèãðûø çàâèñèò îò ìíîãèõ ôàêòîðîâ, íàïðè-
ìåð îò ÷èñëà âõîäîâ ÎËÖ è êëàññîâ ïñåâäîýêâèâàëåíòíûõ ÎËÖ. Âûèãðûø óâå-
ëè÷èâàåòñÿ ïî ìåðå óìåíüøåíèÿ âåëè÷èí ýòèõ ïàðàìåòðîâ äëÿ ÃÑÀ ñ îäèíàêî-
âûì ÷èñëîì îïåðàòîðíûõ âåðøèí.
Äàëüíåéøåå óìåíüøåíèå ÷èñëà ËÝ ñâÿçàíî ñ ðàçðàáîòêîé ìåòîäîâ êîäèðî-
âàíèÿ âõîäîâ ÎËÖ è êëàññîâ ïñåâäîýêâèâàëåíòíûõ ÎËÖ. Ýòî ÿâëÿåòñÿ îñíîâíûì
íàïðàâëåíèåì äàëüíåéøèõ èññëåäîâàíèé. Äðóãîå íàïðàâëåíèå — àäàïòàöèÿ ðàç-
ðàáîòàííûõ ìåòîäîâ ê îñîáåííîñòÿì ÏËÈÑ, ìàêðîÿ÷åéêè êîòîðûõ îñíîâàíû íà
ýëåìåíòàõ ïðîãðàììèðóåìîé ìàòðè÷íîé ëîãèêè [10].
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B a r a n o v S . Logic and system design of digital systems. — Tallinn: TUT Press, 2008. — 266 p.
2. S c h o l l C . Functional decomposition with application to FPGA. — Boston: Kluwer Acad. Publ.,
2001. — 288 p.
3. R a w s k i H . , J o z w i a k L . , L u b a T . Functional decomposition with an efficient input sup-
port selection for sub-functions based on information relationships measures // J. System Archit. —
2001. — 47, N 3. — P. 137–155.
4. Ã ð ó ø â è ö ê è é Ð . È . , Ì ó ð ñ à å â À . Õ . , Ó ã ð þ ì î â Å . Ï . Ïðîåêòèðîâàíèå ñèñòåì íà
ìèêðîñõåìàõ ïðîãðàììèðóåìîé ëîãèêè. — ÑÏá.: ÁÕÂ — ÑÏá., 2002. — 636 ñ.
5. M a x f i e l d S . The design warrior’s guide to FPGAs. — Amsterdam: Elsevier, 2004. — 541 p.
6. B a r k a l o v A . , T i t a r e n k o L . Logic synthesis for compositional microprogram control units.
— Berlin: Springer, 2008. — 273 p.
7. A l t e r a Corporation. FPGA, CPLID and Structured ASIC — http://www.altera.com.
8. X i l i n x Inc. FPGA, CPLD Solutions. — http://www.xilinx.com.
9. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . Ñèíòåç ìèêðîïðîãðàììíûõ àâòîìàòîâ íà çàêàçíûõ
è ïðîãðàììèðóåìûõ ÑÁÈÑ. — Äîíåöê: ÓÍÈÒÅÕ, 2009. — 336 ñ.
10. Ñ î ë î â ü å â  .  . , Ê ë è ì î â è ÷ À . Ëîãè÷åñêîå ïðîåêòèðîâàíèå öèôðîâûõ ñèñòåì íà
îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì. — Ì.: Ãîðÿ÷àÿ ëèíèÿ — Òåëåêîì,
2008. — 376 ñ.
11. W i s n i e w s l c i R . Synthesis of compositional microprogram control units for programmable de-
vices. — Zielona Gora: UZG Press, 2009. — 104 p.
Ïîñòóïèëà 28.09.2009
118 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 5
|
| id | nasplib_isofts_kiev_ua-123456789-84238 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-30T16:29:16Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Титаренко, Л.А. 2015-07-04T12:51:57Z 2015-07-04T12:51:57Z 2011 Преобразование кодов в композиционных микропрограммных устройствах управления / А.А. Баркалов, Л.А. Титаренко // Кибернетика и системный анализ. — 2011. — Т. 47, № 5. — С. 107-118. — Бібліогр.: 11 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/84238 004.383.3 Запропоновано спільне використання методів структурної декомпозиції та перетворення кодів об’єктів, що орієнтоване на зменшення апаратурних витрат у схемі композиційного мікропрограмного пристрою керування. Оптимізація досягається завдяки зменшенню як кількості аргументів нерегулярних функцій, так і кількості самих функцій. Для реалізації регулярних функцій використовуються вбудовані блоки пам’яті. Розглянуто метод і приклад синтезу, а також наведено результати досліджень. Properties of a smooth continuous spline are considered. Existence conditions are established and an algorithm for determining parameters of such a spline by the sum of a polynomial and an exponent is proposed. Estimates of approximation errors are obtained for polynomial splines and splines with sections in the form of the sum of a polynomial and an exponent. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Системный анализ Преобразование кодов в композиционных микропрограммных устройствах управления Перетворення кодів в композиційних мікропрограмних пристроях керування Code transformation in compositional microprogram control units Article published earlier |
| spellingShingle | Преобразование кодов в композиционных микропрограммных устройствах управления Баркалов, А.А. Титаренко, Л.А. Системный анализ |
| title | Преобразование кодов в композиционных микропрограммных устройствах управления |
| title_alt | Перетворення кодів в композиційних мікропрограмних пристроях керування Code transformation in compositional microprogram control units |
| title_full | Преобразование кодов в композиционных микропрограммных устройствах управления |
| title_fullStr | Преобразование кодов в композиционных микропрограммных устройствах управления |
| title_full_unstemmed | Преобразование кодов в композиционных микропрограммных устройствах управления |
| title_short | Преобразование кодов в композиционных микропрограммных устройствах управления |
| title_sort | преобразование кодов в композиционных микропрограммных устройствах управления |
| topic | Системный анализ |
| topic_facet | Системный анализ |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84238 |
| work_keys_str_mv | AT barkalovaa preobrazovaniekodovvkompozicionnyhmikroprogrammnyhustroistvahupravleniâ AT titarenkola preobrazovaniekodovvkompozicionnyhmikroprogrammnyhustroistvahupravleniâ AT barkalovaa peretvorennâkodívvkompozicíinihmíkroprogramnihpristroâhkeruvannâ AT titarenkola peretvorennâkodívvkompozicíinihmíkroprogramnihpristroâhkeruvannâ AT barkalovaa codetransformationincompositionalmicroprogramcontrolunits AT titarenkola codetransformationincompositionalmicroprogramcontrolunits |