Модификация системы адресации микрокоманд в устройстве управления с разделением кодов
Запропоновано дві модифікації системи адресації мікрокоманд у композиційному мікропрограмному пристрої керування з розділенням кодів. Модифікації базуються на використанні псевдоеквівалентних станів автомата для зменшення кількості рядків таблиці переходів автомата і, як наслідок, складності комбіна...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2013 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2013
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/86175 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов / А.А. Баркалов, Л.А. Титаренко, А.Н. Мирошкин // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 161-171. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859517371714109440 |
|---|---|
| author | Баркалов, А.А. Титаренко, Л.А. Мирошкин, А.Н. |
| author_facet | Баркалов, А.А. Титаренко, Л.А. Мирошкин, А.Н. |
| citation_txt | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов / А.А. Баркалов, Л.А. Титаренко, А.Н. Мирошкин // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 161-171. — Бібліогр.: 17 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано дві модифікації системи адресації мікрокоманд у композиційному мікропрограмному пристрої керування з розділенням кодів. Модифікації базуються на використанні псевдоеквівалентних станів автомата для зменшення кількості рядків таблиці переходів автомата і, як наслідок, складності комбінаційної частини схеми пристрою. Запропоновано методики синтезу композиційних пристроїв з модифікованою системою мікрокоманд. Наведено результати досліджень. Визначено області доцільного застосування запропонованих методик.
Two modifications of microcommand addressing system in compositional microprogram control unit with code sharing are proposed in the paper. The modifications are based on using the automaton pseudoequivalent states to reduce the row number in the automaton transition table and thus to reduce the complexity of the combinational part of the device. The methods are proposed to synthesize compositional control units with mo dified microcommand addressing system. The research results are given and the appropriate fields of application of the proposed methods are identified.
|
| first_indexed | 2025-11-25T20:47:31Z |
| format | Article |
| fulltext |
À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ, À.Í. ÌÈÐÎØÊÈÍ
ÓÄÊ 004.3 ÌÎÄÈÔÈÊÀÖÈß ÑÈÑÒÅÌÛ ÀÄÐÅÑÀÖÈÈ
ÌÈÊÐÎÊÎÌÀÍÄ Â ÓÑÒÐÎÉÑÒÂÅ ÓÏÐÀÂËÅÍÈß
Ñ ÐÀÇÄÅËÅÍÈÅÌ ÊÎÄÎÂ
Êëþ÷åâûå ñëîâà: ãðàô-ñõåìà àëãîðèòìà, óïðàâëÿþùåå óñòðîéñòâî, êîìïîçè-
öèîííîå ìèêðîïðîãðàììíîå óñòðîéñòâî óïðàâëåíèÿ, ðàçäåëåíèå êîäîâ, ïðîãðàì-
ìèðóåìûå ëîãè÷åñêèå èíòåãðàëüíûå ñõåìû òèïà FPGA, àäðåñàöèÿ ìèêðîêîìàíä.
ÂÂÅÄÅÍÈÅ
Ëþáàÿ öèôðîâàÿ ñèñòåìà ñîñòîèò èç óñòðîéñòâà óïðàâëåíèÿ (ÓÓ) è îïåðàöèîí-
íîãî àâòîìàòà. Ïåðâîå âûðàáàòûâàåò ïîñëåäîâàòåëüíîñòü óïðàâëÿþùèõ ñèãíà-
ëîâ, ïîä âîçäåéñòâèåì êîòîðûõ îïåðàöèîííûé àâòîìàò âûïîëíÿåò îïðåäåëåííûå
ìèêðîîïåðàöèè [1]. Äëÿ çàäàíèÿ ïîñëåäîâàòåëüíîñòè äåéñòâèé èñïîëüçóåòñÿ
ÿçûê ãðàô-ñõåì àëãîðèòìà (ÃÑÀ). Ôóíêöèîíèðîâàíèå ÓÓ, ðåàëèçóþùåãî ÃÑÀ,
îïèñûâàåòñÿ ìîäåëüþ öèôðîâîãî àâòîìàòà [2]. Ïðàêòè÷åñêàÿ ðåàëèçàöèÿ ðàç-
ëè÷íûõ òèïîâ ÓÓ õàðàêòåðèçóåòñÿ òàêèìè ïîêàçàòåëÿìè, êàê àïïàðàòóðíûå çà-
òðàòû è âðåìåííûå õàðàêòåðèñòèêè (äëèòåëüíîñòü òàêòà ñèíõðîíèçàöèè, íàðà-
áîòêà äî îòêàçà). Íà ïðàêòèêå, êàê ïðàâèëî, àêòóàëüíà ïðîáëåìà ìèíèìèçàöèè
àïïàðàòóðíûõ çàòðàò [3], ðåøåíèå êîòîðîé çàâèñèò îò îñîáåííîñòåé àëãîðèòìà
óïðàâëåíèÿ è èñïîëüçóåìîãî ïðè ðåàëèçàöèè óñòðîéñòâà ýëåìåíòíîãî áàçèñà.
 ñëó÷àå åñëè àëãîðèòì íîñèò ëèíåéíûé õàðàêòåð, öåëåñîîáðàçíî èñïîëüçî-
âàòü ìîäåëü êîìïîçèöèîííîãî ìèêðîïðîãðàììíîãî óñòðîéñòâà óïðàâëåíèÿ
(ÊÌÓÓ) [4, 5].
Íàñòîÿùàÿ ðàáîòà ïîñâÿùåíà èññëåäîâàíèþ ïðîöåññà ðåàëèçàöèè ñõåìû
ÊÌÓÓ â áàçèñå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì òèïà FPGA
(field-programmable gate array) [6, 7]. Ôóíêöèîíàëüíûì ýëåìåíòîì FPGA ñëóæèò
òàáëèöà ïðåîáðàçîâàíèÿ (Look-Up Table — LUT). Êàæäûé LUT-ýëåìåíò ìîæíî
èñïîëüçîâàòü íå òîëüêî â êà÷åñòâå ôóíêöèîíàëüíûõ ãåíåðàòîðîâ, íî è êàê ñèí-
õðîííóþ ïàìÿòü íåáîëüøîé åìêîñòè. Êðîìå LUT-ýëåìåíòîâ áîëüøèíñòâî ñîâðå-
ìåííûõ ìèêðîñõåì FPGA ñîäåðæàò ñïåöèàëüíûå ïðîãðàììèðóåìûå áëîêè ïàìÿ-
òè, êàæäûé èç êîòîðûõ ïðåäñòàâëÿåò ñîáîé ñèíõðîííîå îïåðàòèâíîå çàïîìèíàþ-
ùåå óñòðîéñòâî (ÎÇÓ) åìêîñòüþ 18 Êáèò [8]. Áëî÷íîå ÎÇÓ ýôôåêòèâíåå
ïðèìåíÿåòñÿ â ñõåìàõ äëÿ õðàíåíèÿ îòíîñèòåëüíî áîëüøîãî êîëè÷åñòâà äàííûõ,
÷åì óïîìÿíóòàÿ ðàñïðåäåëåííàÿ ïàìÿòü íà áàçå LUT-ýëåìåíòîâ. Ðåàëèçàöèÿ êî-
íå÷íûõ àâòîìàòîâ ñ ïàìÿòüþ â áàçèñå FPGA îïèñàíà â [9–13].
Äàëåå ðàññìîòðåíû íåêîòîðûå ïîäõîäû ê ìîäèôèêàöèÿì ñèñòåìû àäðåñàöèè
ìèêðîêîìàíä, êîòîðûå îñíîâàíû íà ìîäåëè ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ [4],
îäíàêî ïðåäëîæåííóþ èäåþ ìîæíî ðåàëèçîâàòü è äëÿ äðóãèõ ñòðóêòóð óïðàâëÿ-
þùèõ óñòðîéñòâ ñ ïàìÿòüþ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 161
© À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, À.Í. Ìèðîøêèí, 2013
162 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
ÌÎÄÅËÜ ÊÌÓÓ Ñ ÐÀÇÄÅËÅÍÈÅÌ ÊÎÄÎÂ
Èñõîäíûìè äàííûìè äëÿ ñèíòåçà ÓÓ ÿâëÿåòñÿ ãðàô-ñõåìà óïðàâëÿþùåãî àë-
ãîðèòìà. Ïóñòü ïðîèçâîëüíàÿ ÃÑÀ � ñîñòîèò èç ìíîæåñòâà âåðøèí B è äóã E,
ñîåäèíÿþùèõ ýòè âåðøèíû. Ïðè ýòîì B b b B BE� � �{ }0 1 2, , ãäå b0 , bE —
íà÷àëüíàÿ è êîíå÷íàÿ âåðøèíû ÃÑÀ à, B1, B2 — ìíîæåñòâà îïåðàòîðíûõ è
óñëîâíûõ âåðøèí ñîîòâåòñòâåííî. Âåðøèíû b Bm � 1 ñîäåðæàò íàáîðû ìèêðî-
îïåðàöèé Y b Ym( ) � , ãäå m M�1, , M B� | |1 — îáùåå êîëè÷åñòâî îïåðàòîð-
íûõ âåðøèí ÃÑÀ, Y y yN� � �{ }1 � — ìíîæåñòâî ìèêðîîïåðàöèé (âûõîäíûõ
ôóíêöèé àâòîìàòà). Âåðøèíû b Bq � 2 ñîäåðæàò ýëåìåíòû ìíîæåñòâà ëîãè÷å-
ñêèõ óñëîâèé X x xL� { }1, ..., . Ââåäåì îïðåäåëåíèÿ, íåîáõîäèìûå äëÿ äàëüíåé-
øåãî èçëîæåíèÿ.
Îïðåäåëåíèå 1. Îïåðàòîðíîé ëèíåéíîé öåïüþ � g ÃÑÀ � íàçûâàåòñÿ êîíå÷-
íàÿ ïîñëåäîâàòåëüíîñòü îïåðàòîðíûõ âåðøèí � b bg gFg1
, ..., , äëÿ ëþáîé ïàðû ñî-
ñåäíèõ êîìïîíåíòîâ êîòîðîé ñóùåñòâóåò äóãà � �
b b Eg gi i
,
1
, ãäå i Fg� �1 1, ,
Fg — ÷èñëî êîìïîíåíòîâ â îïåðàòîðíûõ ëèíåéíûõ öåïÿõ (ÎËÖ) � g .
Îïðåäåëåíèå 2. Îïåðàòîðíàÿ âåðøèíà b Bm
g� , ãäå m Fg�1, , B Bg � 1 —
ìíîæåñòâî îïåðàòîðíûõ âåðøèí, âõîäÿùèõ â ÎËÖ � g , íàçûâàåòñÿ åå âõîäîì,
åñëè ñóùåñòâóåò äóãà � �b b Et m, , ãäå b Bt
g� . Êàæäàÿ ÎËÖ � g èìååò ïðîèç-
âîëüíîå ÷èñëî âõîäîâ, îáðàçóþùèõ ìíîæåñòâî I I Ig g g( ) , , ...� � { }1 2 .
Îïðåäåëåíèå 3. Îïåðàòîðíàÿ âåðøèíà b Bm
g� íàçûâàåòñÿ âûõîäîì ÎËÖ � g ,
åñëè ñóùåñòâóåò äóãà � �b b Em t, , ãäå b Bt
g� . Ïðîèçâîëüíàÿ ÎËÖ � g èìååò
òîëüêî îäèí âûõîä, îáîçíà÷àåìûé Og .
Îïðåäåëåíèå 4. Öåïè � i è � j íàçûâàþòñÿ ïñåâäîýêâèâàëåíòíûìè ÎËÖ
(ÏÎËÖ), åñëè ñóùåñòâóþò äóãè � �b b Ei t, è � �b b Ej t, , ãäå bi , b j — âûõîäû
ÎËÖ � i , � j ñîîòâåòñòâåííî.
Îïðåäåëåíèå 5. Ãðàô ñõåìà àëãîðèòìà � íàçûâàåòñÿ ëèíåéíîé, åñëè âûïîë-
íÿåòñÿ óñëîâèå
M
G
2, (1)
ãäå G — ÷èñëî îïåðàòîðíûõ ëèíåéíûõ öåïåé ÃÑÀ, ò.å ÃÑÀ ÿâëÿåòñÿ ëèíåéíîé,
åñëè ÷èñëî îïåðàòîðíûõ âåðøèí àëãîðèòìà ïðåâûøàåò ìèíèìàëüíîå êîëè÷åñòâî
öåïåé íå ìåíåå ÷åì â äâà ðàçà. Ïðè âûïîëíåíèè óñëîâèÿ (1) äëÿ ðåàëèçàöèè àë-
ãîðèòìà óïðàâëåíèÿ öåëåñîîáðàçíî èñïîëüçîâàòü ìîäåëü ÊÌÓÓ [4].
Äëÿ íàõîæäåíèÿ ðàçáèåíèÿ ìíîæåñòâà B1 îïåðàòîðíûõ âåðøèí íà ìèíè-
ìàëüíîå êîëè÷åñòâî ÎËÖ èñïîëüçóåòñÿ ìåòîäèêà, îïèñàííàÿ â [4]. Ïîñëå ôîðìè-
ðîâàíèÿ ìíîæåñòâà C G� � �{ }� �1 � êàæäàÿ ÎËÖ � g ñîäåðæèò Fg êîìïîíåíòîâ
è åé ïðèñâàèâàåòñÿ äâîè÷íûé êîä K g( )� ðàçðÿäíîñòè
� �R G1 2� log , (2)
à êàæäîìó êîìïîíåíòó bgi
— êîä K bgi
( ) ðàçðÿäíîñòè
� �R F2 2� log ( )max , (3)
ãäå F F FGmax max ( , ..., )� 1 — êîëè÷åñòâî êîìïîíåíòîâ â ÎËÖ ìàêñèìàëüíîé
äëèíû. Äëÿ êîäèðîâàíèÿ ÎËÖ èñïîëüçóþòñÿ ýëåìåíòû ìíîæåñòâà �, à äëÿ êî-
äèðîâàíèÿ êîìïîíåíòîâ ÎËÖ — ýëåìåíòû ìíîæåñòâà T , ãäå | |� � R1, | |T R� 2 .
Êîäèðîâàíèå êîìïîíåíòîâ âûïîëíÿåòñÿ â åñòåñòâåííîì ïîðÿäêå, ò.å.
K b K bg gi i
( ) ( )
�
1
1, ( , ; , )g G i Fg� �1 1 . (4)
Îïåðàòîðíàÿ âåðøèíà bm ñîîòâåòñòâóåò ìèêðîêîìàíäå MI m , àäðåñ A MI m( )
êîòîðîé îïðåäåëÿåòñÿ êàê
A MI K K bm g gi
( ) ( )* ( )� � , (5)
ãäå * — çíàê êîíêàòåíàöèè, à âåðøèíà bm ñîîòâåòñòâóåò êîìïîíåíòó bgi
ÎËÖ � g .
Ïðèìåíåíèå ïðèíöèïà ðàçäåëåíèÿ êîäîâ ïðèâîäèò ê òîìó, ÷òî ñõåìà ôîðìè-
ðîâàíèÿ àäðåñà (ÑÔÀ) ðåàëèçóåò ñèñòåìó ôóíêöèé âîçáóæäåíèÿ ñ÷åò÷èêà CT
è ðåãèñòðà RG:
� �
� �
�
�
( , ) ;
( , ).
�
�
X
X
(6)
Ìîäåëü ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ (Code Sharing, CS-ñòðóêòóðà) ïðèâåäåíà
íà ðèñ. 1 è ôóíêöèîíèðóåò ñëåäóþùèì îáðàçîì.  íà÷àëå ðàáîòû ïî ñèãíàëó
Start òðèããåð TB ðàçðåøåíèÿ ÷òå-
íèÿ èç óïðàâëÿþùåé ïàìÿòè (ÓÏ)
ïåðåêëþ÷àåòñÿ â ñîñòîÿíèå ëîãè-
÷åñêîé åäèíèöû. Ñõåìà ôîðìèðî-
âàíèÿ àäðåñà îáåñïå÷èâàåò ïåðå-
õîä íà âõîäíóþ âåðøèíó îäíîé
èç ÎËÖ � g . Ñôîðìèðîâàííûé
äëÿ íåå àäðåñ, ïîïàâ â ñ÷åò÷èê,
ó÷àñòâóåò â âûáîðêå îïðåäåëåí-
íîé ìèêðîêîìàíäû èç ïàìÿòè.
Åñëè òåêóùàÿ âåðøèíà íå ÿâëÿåò-
ñÿ âûõîäîì ÎËÖ, ôîðìèðóåòñÿ
ñèãíàë y0 , êîòîðûé ïîçâîëÿåò
ñ÷åò÷èêó óâåëè÷èòü ñâîå ñîäåð-
æèìîå, òåì ñàìûì àäðåñóÿ ñëåäó-
þùèé êîìïîíåíò ÎËÖ � g ñî-
ãëàñíî ïðàâèëó åñòåñòâåííîé àä-
ðåñàöèè ìèêðîêîìàíä (4). Ïî
äîñòèæåíèþ âûõîäà Og ÎËÖ � g
ñèãíàë y0 íå ôîðìèðóåòñÿ, ÷òî
ïðèâîäèò ê çàïèñè â ñ÷åò÷èê àä-
ðåñà ïåðåõîäà íà âõîäíóþ âåðøè-
íó î÷åðåäíîé ÎËÖ. Ýòîò àäðåñ ôîðìèðóåòñÿ ÑÔÀ ïî êîäó òåêóùåé ÎËÖ, êîòî-
ðûé íàõîäèòñÿ â ðåãèñòðå RG. Ôóíêöèîíèðîâàíèå óñòðîéñòâà çàâåðøàåòñÿ, êîãäà
ñôîðìèðîâàí ñèãíàë yE , çàïðåùàþùèé äàëüíåéøåå ñ÷èòûâàíèå ìèêðîêîìàíä.
Ýòîò ñèãíàë äîáàâëÿåòñÿ âî âñå âåðøèíû, âûõîäû êîòîðûõ ñâÿçàíû ñ êîíå÷íîé
âåðøèíîé ÃÑÀ.
Ïðè ðåàëèçàöèè ñõåìû ÊÌÓÓ â áàçèñå FPGA äëÿ áëîêîâ, êðîìå ÓÏ, ïðèìå-
íÿþòñÿ LUT-ýëåìåíòû è ðàñïðåäåëåííûå ýëåìåíòû ïàìÿòè (òðèããåðû-çàùåëêè),
à äëÿ ðåàëèçàöèè ïàìÿòè — âñòðîåííûå áëîêè ïàìÿòè. Åñëè ïðè ñèíòåçå ÊÌÓÓ
÷àñòü ðåñóðñîâ âñòðîåííûõ áëîêîâ ïàìÿòè íå èñïîëüçóåòñÿ, èõ ìîæíî çàäåéñòâî-
âàòü äëÿ óìåíüøåíèÿ ÷èñëà LUT-ýëåìåíòîâ â ñõåìå àäðåñàöèè, ÷òî ñíèçèò àïïà-
ðàòóðíûå çàòðàòû ïðè ðåàëèçàöèè óñòðîéñòâà è óëó÷øèò âðåìåííûå õàðàêòåðèñ-
òèêè ïîëó÷åííîé ñõåìû.
ÎÑÍÎÂÍÀß ÈÄÅß ÏÐÅÄËÀÃÀÅÌÎÃÎ ÌÅÒÎÄÀ
Ïåðåõîäû èç ïñåâäîýêâèâàëåíòíûõ öåïåé ïðåäñòàâëåíû â òàáëèöå ïåðåõîäîâ
ÊÌÓÓ ñòðîêàìè, îòëè÷àþùèìèñÿ ëèøü èñòî÷íèêîì êîäà äëÿ ÑÔÀ. Òàêèì îá-
ðàçîì, èõ ìîæíî çàìåíèòü îäíîé ñòðîêîé ñ êîäîì êëàññà ÏÎËÖ â êà÷åñòâå
èñòî÷íèêà, âñëåäñòâèå ÷åãî óìåíüøèòñÿ êîëè÷åñòâî ñòðîê òàáëèöû, à òàêæå
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 163
Ñõåìà
ôîðìèðîâàíèÿ
àäðåñà
CT
R
S TB E
Óïðàâëÿþùàÿ
ïàìÿòü
X
Y
y0yE
Fetch
Start
Start
Clock
RG + 1
T
Ðèñ. 1. Ñòðóêòóðíàÿ ñõåìà ÊÌÓÓ ñ ðàçäåëåíèåì
êîäîâ
�
�
�
�
÷èñëî àðãóìåíòîâ è òåðìîâ â ôóíêöèÿõ ñèñòåìû (6). Êîäû êëàññîâ ÏÎËÖ
ìîæíî õðàíèòü â ñâîáîäíûõ ðåñóðñàõ âñòðîåííûõ áëîêîâ ïàìÿòè ìèêðîñõåìû
FPGA. Â íàñòîÿùåé ñòàòüå ïðåäëîæåíû äâà ïîäõîäà ê ìîäèôèêàöèè ñèñòåìû
àäðåñàöèè ìèêðîêîìàíä: ðàñøèðåíèå ôîðìàòà ìèêðîêîìàíä, ò.å. âêëþ÷åíèå
â ôîðìàò äîïîëíèòåëüíîãî ïîëÿ, êîòîðîå áóäåò ñîäåðæàòü êîä êëàññà ÏÎËÖ;
ìîäèôèêàöèÿ öåïåé, ò.å. âêëþ÷åíèå â èñõîäíóþ ÃÑÀ äîïîëíèòåëüíîé âåðøè-
íû ñ êîäîì êëàññà ÏÎËÖ â êîíöå êàæäîé îïåðàòîðíîé ëèíåéíîé öåïè, íå
ñâÿçàííîé ñ êîíå÷íîé âåðøèíîé.
Ïóñòü ÎËÖ � g C� 1, åñëè åå âûõîä Og íå ñâÿçàí ñ êîíå÷íîé âåðøèíîé bE .
Íàéäåì ðàçáèåíèå �C IB B� { }1, ..., ìíîæåñòâà C1 íà êëàññû ÏÎËÖ è çàêîäèðó-
åì êàæäûé èç íèõ äâîè÷íûì êîäîì ðàçðÿäíîñòè � �R I3 2� log . Äëÿ êîäèðîâà-
íèÿ êëàññîâ ÏÎËÖ èñïîëüçóåì ïåðåìåííûå ìíîæåñòâà Z z zR� { }1 3
, ..., . Òîãäà
ñèñòåìà (6) ïðåîáðàçóåòñÿ ê âèäó
� �
� �
�
�
( , ) ;
( , ).
Z X
Z X
(7)
Ïðè ðàñøèðåíèè ôîðìàòà ìèêðîêîìàíä èõ êîëè÷åñòâî â ïàìÿòè ðàâíî ñîîò-
âåòñòâóþùåìó çíà÷åíèþ äëÿ ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ
� �M G1 1 2 2� � �
( ) | |
log | |
min
max�
� ,
ãäå � max , � min — öåïè ñ ìàêñèìàëüíûì è ìèíèìàëüíûì êîëè÷åñòâîì êîìïî-
íåíòîâ ñîîòâåòñòâåííî. Äëÿ îáåñïå÷åíèÿ ìèíèìàëüíîãî ÷èñëà ñëîâ ìèêðîïðîã-
ðàììû íåîáõîäèìî ÎËÖ � min ïðèñâîèòü ìàêñèìàëüíûé èç èñïîëüçóåìûõ êî-
äîâ ÎËÖ, â ðåçóëüòàòå ñîîòâåòñòâóþùåå ñîäåðæèìîå ïàìÿòè ïîñòóïèò â îá-
ëàñòü ñ ìàêñèìàëüíûìè àäðåñàìè.
Ðàçðÿäíîñòü êàæäîãî ñëîâà ïîñëå âêëþ÷åíèÿ äîïîëíèòåëüíîãî ïîëÿ áóäåò
ðàâíà N N RY1 32�
, ãäå NY — êîëè÷åñòâî ðàçðÿäîâ, íåîáõîäèìûõ äëÿ êîäè-
ðîâàíèÿ ìíîæåñòâà ìèêðîêîìàíä y Yi � (ïðè óíèòàðíîì êîäèðîâàíèè ìèêðîîïå-
ðàöèé N YY � | | ), à êîíñòàíòà 2 ðåçåðâèðóåò äâà ðàçðÿäà äëÿ õðàíåíèÿ âíóòðåí-
íèõ ïåðåìåííûõ: y0 è yE . Ðàçðÿäíîñòè ðåãèñòðà è ñ÷åò÷èêà ðàâíû ñîîòâåòñòâóþ-
ùèì çíà÷åíèÿì (2) è (3).
Ìîäèôèêàöèÿ ÎËÖ ìîæåò óâåëè÷èòü êîëè÷åñòâî ñëîâ ìèêðîïðîãðàììû äî
âåëè÷èíû � �M G2
1
1 2 12� � �
( ) | |
log (| | )
min
max�
� .
Ðàçðÿäíîñòü ñëîâà ïðè òðèâèàëüíîé ðåàëèçàöèè ïðåäëîæåííîãî ïîäõîäà
îïðåäåëÿåòñÿ êàê N N RY2 3 2�
max ( ; ) .
Ðàçðÿäíîñòü ðåãèñòðà è ñ÷åò÷èêà ïîñëå ìîäèôèêàöèè öåïåé îïðåäåëÿåòñÿ
ôîðìóëàìè (2) è (3). Îäíàêî ïàðàìåòð Fmax ìîæåò óâåëè÷èòüñÿ, ÷òî ïðèâåäåò
ê óâåëè÷åíèþ êîëè÷åñòâà ðàçðÿäîâ ðåãèñòðà. Îòìåòèì, ÷òî ïðè óâåëè÷åíèè ðàç-
ðÿäíîñòè ñ÷åò÷èêà ÑÔÀ áóäåò ïî-ïðåæíåìó ôîðìèðîâàòü R2 ïåðåìåííûõ. Ýòî
ñâÿçàíî ñ òåì, ÷òî íåïîñðåäñòâåííûé ïåðåõîä ê ìèêðîêîìàíäå, êîòîðàÿ ñîäåðæèò
ëèøü êîä êëàññà ÏÎËÖ, íèêîãäà íå âûïîëíèòñÿ. Ïðè ýòîì ñòàðøèé ðàçðÿä äàí-
íûõ äëÿ ñ÷åò÷èêà âñåãäà áóäåò ðàâåí íóëþ.
Óñëîâèìñÿ, ÷òî ñ ïàðàìåòðàìè M i è N i ìèêðîïðîãðàììó ìîæíî ðåàëèçî-
âàòü ñ èñïîëüçîâàíèåì îäíîãî áëîêà âñòðîåííîé ïàìÿòè.
Îáîçíà÷èì FCS è MCS ïðåäñòàâëåííûå íà ðèñ. 2, à, á ìîäåëè ÊÌÓÓ ñîîò-
âåòñòâåííî.
Ïðèíöèïû ôóíêöèîíèðîâàíèÿ áàçîâîé ìîäåëè ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ
(ñì. ðèñ. 1) è ìîäåëåé FCS è MCS àíàëîãè÷íû. Ìåòîä ñèíòåçà ðàññìîòðåííûõ
ñòðóêòóð âêëþ÷àåò ñëåäóþùèå ýòàïû:
— ôîðìèðîâàíèå äëÿ ÃÑÀ � ìíîæåñòâ C, C1 è �C ;
— îïòèìàëüíîå êîäèðîâàíèå öåïåé � g C� 1 è èõ êîìïîíåíòîâ;
164 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
— êîäèðîâàíèå êëàññîâ ïñåâ-
äîýêâèâàëåíòíûõ öåïåé Bi C�� ;
— ôîðìèðîâàíèå ñîäåðæè-
ìîãî ÓÏ;
— ôîðìèðîâàíèå òàáëèöû
ïåðåõîäîâ ÊÌÓÓ è ñèñòåìû ôóíê-
öèé ïåðåõîäîâ (7);
— ñèíòåç ñõåìû ÓÓ â çà-
äàííîì áàçèñå.
Ïåðâûé ýòàï âûïîëíÿåòñÿ ïî
îïèñàííîé â [4] ìåòîäèêå, ïðè
ýòîì êîëè÷åñòâî G ÎËÖ � g C�
ÿâëÿåòñÿ ìèíèìàëüíî âîçìîæ-
íûì. Ðàçáèåíèå �C ôîðìèðóåòñÿ
íà îñíîâå îïðåäåëåíèÿ 4 òðèâè-
àëüíûì îáðàçîì.
Îïòèìàëüíîå êîäèðîâàíèå
ÎËÖ � g C� 1 âûïîëíÿåòñÿ ïî ìå-
òîäèêå, àíàëîãè÷íîé îïòèìàëü-
íîìó êîäèðîâàíèþ ñîñòîÿíèé àâ-
òîìàòà Ìóðà [15]. Äëÿ ðåøåíèÿ
ýòîé çàäà÷è èñïîëüçóþòñÿ èç-
âåñòíûå ìåòîäû ñèìâîëüíîé ìè-
íèìèçàöèè [3]. Êîìïîíåíòû âñåõ
ÎËÖ êîäèðóþòñÿ òðèâèàëüíûì
ñïîñîáîì: ïåðâîìó êîìïîíåíòó
ïðèñâàèâàåòñÿ êîä, äåñÿòè÷íûé
ýêâèâàëåíò êîòîðîãî ðàâåí íóëþ,
âòîðîìó — åäèíèöå, äàëåå —
äâóì è ò.ä. Òàêîå êîäèðîâàíèå
óäîâëåòâîðÿåò ðàâåíñòâó (4).
Ñïîñîá êîäèðîâàíèÿ êëàññîâ
Bi C�� äîëæåí ìèíèìèçèðîâàòü
êîëè÷åñòâî òåðìîâ â ôóíêöèè
z Zr � . Àäàïòèðîâàâ èçâåñòíûé
äëÿ D-òðèããåðîâ ìåòîä êîäèðîâà-
íèÿ ñîñòîÿíèé [15], ïîëó÷èì, ÷òî
÷åì áîëüøå îáîáùåííûõ èíòåðâà-
ëîâ íåîáõîäèìî äëÿ ïðåäñòàâëå-
íèÿ êëàññà Bi C�� , òåì ìåíüøå
åäèíèö äîëæåí ñîäåðæàòü åãî êîä.
Ñîäåðæèìîå ÓÏ ôîðìèðóåòñÿ
â âèäå òàáëèöû ñ ïîëÿìè A MI m( ), Y bm( ), y0 , yE , C Bi( ). Ïðè÷åì äëÿ FCS-ñòðóêòó-
ðû ÊÌÓÓ ïîëÿ Y bm( ) è C Bi( ) ÿâëÿþòñÿ îòäåëüíûìè ñòîëáöàìè íàðàâíå ñ îñòàëü-
íûìè ïîëÿìè.  ñëó÷àå MCS-ñòðóêòóðû ýòè ïîëÿ çàïèñûâàþòñÿ â îäèí ñòîëáåö, ñî-
äåðæèìîå êîòîðîãî òðàêòóåòñÿ â çàâèñèìîñòè îò çíà÷åíèÿ ïåðåìåííîé y0 . Ïðè ýòîì
øèðèíà ñòîëáöà âûáèðàåòñÿ êàê max ( ; )N RY 3 , à ê êîäàì â ïîëå ìåíüøåé øèðèíû
äîáàâëÿþòñÿ íåçíà÷àùèå íóëè.
Ïåðåä ïîñòðîåíèåì ñîäåðæèìîãî ïàìÿòè ïðîèñõîäèò ïðåîáðàçîâàíèå èñõîä-
íîé ÃÑÀ [4]. Åñëè âåðøèíà bgi
ÎËÖ � g C� 1 íå ÿâëÿåòñÿ âûõîäîì ÎËÖ, â íåå
ââîäèòñÿ ïåðåìåííàÿ y0 1� , êîòîðàÿ îïðåäåëÿåò åñòåñòâåííóþ àäðåñàöèþ äëÿ
ñëåäóþùåãî êîìïîíåíòà ÎËÖ. Åñëè � g C� 1, òî â âåðøèíó Og ââîäèòñÿ ïåðå-
ìåííàÿ yE �1, êîòîðàÿ çàâåðøèò ðàáîòó àâòîìàòà.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 165
Ñõåìà
ôîðìèðîâàíèÿ
àäðåñà
CT
R
S TB E
Óïðàâëÿþùàÿ
ïàìÿòü
X
Y
y0
yE
Fetch
Start
Start
Clock
RG +1
Z
Z
Ñõåìà
ôîðìèðîâàíèÿ
àäðåñà
CT
R
S
E
Óïðàâëÿþùàÿ
ïàìÿòü
X
Y
y0yE
Fetch
Start
Start
Clock
RG +1
Z
Z
TB
T
Ðèñ. 2. Ñòðóêòóðíûå ñõåìû ÊÌÓÓ ñ ìîäèôèêàöèÿìè
ñèñòåìû àäðåñàöèè ìèêðîêîìàíä: ñ ðàñøèðåíèåì
ôîðìàòà ìèêðîêîìàíä (à); ñ ìîäèôèêàöèåé ÃÑÀ (á)
à
á
� �
� �
�
� T
Òàáëèöà ïåðåõîäîâ äëÿ ðàññìàòðèâàåìûõ ÊÌÓÓ ñîäåðæèò ñëåäóþùèå ñòîëá-
öû: Bi — êëàññ ÏÎËÖ, èç êîòîðîãî âûïîëíÿåòñÿ ïåðåõîä; k Bi( ) — êîä êëàññà
ÏÎËÖ; bm — âåðøèíà, íà êîòîðóþ âûïîëíÿåòñÿ ïåðåõîä; A MI m( ) — àäðåñ ìèê-
ðîêîìàíäû, ñîîòâåòñòâóþùåé âåðøèíå bm ; X h — êîíúþíêöèÿ ëîãè÷åñêèõ ïåðå-
ìåííûõ, îïðåäåëÿþùèõ ïåðåõîä èç âûõîäà Og ÎËÖ � g iB� â âåðøèíó bm â h-é
ñòðîêå òàáëèöû ïåðåõîäîâ; �h , �h — ôóíêöèè âîçáóæäåíèÿ ðåãèñòðà è ñ÷åò÷èêà
ñîîòâåòñòâåííî; h — íîìåð òåðìà (ñòðîêè òàáëèöû ïåðåõîäîâ).
Êàæäàÿ ôóíêöèÿ ñèñòåìû (7) ïðåäñòàâëÿåòñÿ â âèäå
d P B C x ii
h
H
i
h
h
l
L
l
h
l
h� � �
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�� �
� �1 1
, ( 1, )R , (8)
ãäå di — ôóíêöèÿ âîçáóæäåíèÿ i-ãî ðàçðÿäà ðåãèñòðà ñîñòîÿíèÿ àâòîìàòà
(di i� � ïðè i R�1 2, è d Ti R i
�
2
ïðè i R�1 1, ); Pi
h — ïåðåìåííàÿ, îïðåäåëÿþ-
ùàÿ íàëè÷èå ôóíêöèè di â ñòðîêå h òàáëèöû ïåðåõîäîâ (Pi
h �1, åñëè ôóíêöèÿ
di èìååòñÿ â ñòðîêå h è Pi
h � 0 â ïðîòèâíîì ñëó÷àå); Bh — êîíúþíêöèÿ ðàçðÿ-
äîâ qr
h êîäà êëàññà ÏÎËÖ (qr
h — çíà÷åíèå r-ãî ðàçðÿäà ( , )r R�1 3 êîäà k Bi( )
êëàññà Bi C�� ÏÎËÖ â ñòðîêå h òàáëèöû ïåðåõîäîâ, q qr
h
r� , åñëè r-é ðàçðÿä
êîäà ðàâåí ëîãè÷åñêîé åäèíèöå è q qr
h
r� â ïðîòèâíîì ñëó÷àå); x
l
h — ïåðå-
ìåííàÿ, îïðåäåëÿþùàÿ çíà÷åíèå ëîãè÷åñêîãî óñëîâèÿ xl â ñòðîêå h òàáëèöû
ïåðåõîäîâ (x x
l
h
l� â ñëó÷àå, åñëè ïåðåõîä â ñòðîêå h ïðîèñõîäèò ïðè âûïîë-
íåíèè óñëîâèÿ, è x x
l
h
l� — ïðè íåâûïîëíåíèè); C
l
h — ïåðåìåííàÿ, îïðåäå-
ëÿþùàÿ íàëè÷èå ëîãè÷åñêîãî óñëîâèÿ xl â ñòðîêå h òàáëèöû ïåðåõîäîâ
(C
l
h �1 ïðè íàëè÷èè ñèãíàëà xl è C
l
h � 0 ïðè åãî îòñóòñòâèè); H — êîëè÷å-
ñòâî ñòðîê òàáëèöû ïåðåõîäîâ; R3 — ðàçðÿäíîñòü êîäà êëàññà ÏÎËÖ; L —
êîëè÷åñòâî ëîãè÷åñêèõ óñëîâèé.
Ñèíòåç ñõåìû ÊÌÓÓ ñâîäèòñÿ ê ðåàëèçàöèè ìîäåëè óïðàâëÿþùåãî àâòîìàòà
â áàçèñå FPGA ñ ïîìîùüþ îäíîãî èç ñòàíäàðòíûõ ïðèêëàäíûõ ïàêåòîâ [16, 17]
è âûõîäèò çà ðàìêè íàøåé ñòàòüè.
ÏÐÈÌÅÐ ÏÐÈÌÅÍÅÍÈß ÏÐÅÄËÀÃÀÅÌÎÃÎ ÌÅÒÎÄÀ
Ïóñòü íåêîòîðàÿ ÃÑÀ �1 ñîäåðæèò M �17 îïåðàòîðíûõ âåðøèí, êîòîðûå îáðà-
çóþò ìíîæåñòâî C � � �{ }� �0 7� ÎËÖ, ãäå � 0 0 1 2� � b b b, , , �1 3 4 5� � b b b, , ,
�2 6 7� � b b, , �3 8 9 10� � b b b, , , �4 11 12� � b b, , �5 13 14� � b b, , � 6 15 16� � b b, ,
� 7 17� � b bE, . Ïîëó÷åíî G � 8 ÎËÖ èç M �17 îïåðàòîðíûõ âåðøèí. Óñëî-
âèå (1) âûïîëíÿåòñÿ, ñëåäîâàòåëüíî, ïðèìåíåíèå ìîäåëè ÊÌÓÓ öåëåñîîáðàçíî.
Öåïü � 7 1�C , ïîñêîëüêó îíà ñîäåðæèò êîíå÷íóþ âåðøèíó ÃÑÀ. Ìíîæåñòâî
ëîãè÷åñêèõ óñëîâèé âêëþ÷àåò L � 4 ýëåìåíòîâ, àâòîìàò âûðàáàòûâàåò N � 6
óïðàâëÿþùèõ ñèãíàëîâ. Èç ìíîæåñòâà C1 ïîëó÷åíî ðàçáèåíèå �C B B� { }0 3, ...,
íà êëàññû ÏÎËÖ, ãäå B0 0 5� { }� �, , B1 1 2 4� { }� � �, , , B2 3� { }� , B3 6� { }� .
Äëÿ êîäèðîâàíèÿ âåðøèí ÃÑÀ ñîãëàñíî (2) è (3) äîñòàòî÷íî R1 3� ýëåìåí-
òîâ ìíîæåñòâà � � � �� { }1 2 3, , è R2 2� ýëåìåíòîâ ìíîæåñòâà T T T� { }1 2, . Êîäû
âåðøèí ÃÑÀ �1 ïðèâåäåíû â òàáë. 1, â ñêîáêàõ äàíû äîáàâëåííûå âåðøèíû äëÿ
ÊÌÓÓ ñ ìîäèôèêàöèåé ÎËÖ. Ñîãëàñíî âûðàæåíèþ (5) êîä âåðøèíû îïðåäåëÿ-
åòñÿ êàê êîíêàòåíàöèÿ êîäà ÎËÖ è êîäà ñàìîãî êîìïîíåíòà, ò.å. k b( )0 00000� ,
k b( )3 00100� , k b( )16 11001� è ò.ä. Çàêîäèðóåì êëàññû Bi C�� ñëåäóþùèì îá-
166 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
ðàçîì: k B( )0 00� , k B( )1 01� , k B( )2 10� , k B( )3 11� . Ïðè ñèíòåçå ÊÌÓÓ ñ ìî-
äèôèêàöèåé öåïåé àëãîðèòìà óïðàâëåíèÿ â êîíåö êàæäîé ÎËÖ � g C� 1 ââîäèòñÿ
âåðøèíà, ñîäåðæàùàÿ êîä k Bi( ), ãäå � g iB� .
Íàïîìíèì, ÷òî ïåðå-
ìåííàÿ y0 çàïèñàíà â âåð-
øèíàõ, êîòîðûå íå ÿâëÿþò-
ñÿ âûõîäàìè ÎËÖ � g C� 1.
Ïåðåìåííàÿ yE çàïèñàíà
â âåðøèíàõ, ñâÿçàííûõ ñ êî-
íå÷íîé âåðøèíîé àëãîðèò-
ìà. Îñòàëüíûå ïîëÿ ìíî-
æåñòâà Y ôîðìèðóþòñÿ ñî-
ãëàñíî ñîäåðæèìîìó ÃÑÀ.
Ôðàãìåíòû ñîäåðæèìîãî
ïàìÿòè äëÿ èññëåäóåìûõ
ñòðóêòóð ÊÌÓÓ ïðèâåäåíû
íà ðèñ. 3, ãäå æèðíûì
øðèôòîì âûäåëåíû êîäû
ÏÎËÖ, êîòîðûå ó÷àñòâóþò
â ôîðìèðîâàíèè àäðåñà ïå-
ðåõîäà, à ñâåòëûì — íåçà-
äåéñòâîâàííûå îáëàñòè ïà-
ìÿòè. Àíàëîãè÷íî ïîëó÷àåò-
ñÿ ñîäåðèìîå è äëÿ âñåõ
îñòàëüíûõ öåïåé � g C� .
Ïî èñõîäíîé ãðàô-ñõå-
ìå ñòðîèòñÿ òàáëèöà ïåðå-
õîäîâ, íà îñíîâå êîòîðîé
ïîëó÷àþò ôóíêöèè (7). Ðàñ-
ñìîòðèì òàáëèöó ïåðåõîäîâ
äëÿ ÃÑÀ �1.
Ïðåäñòàâèì êàæäóþ ôóíêöèþ ñèñòåìû (7) â âèäå ôóíêöèé (8):
B z z B z z B z z B z z0 1 0 1 1 0 2 1 0 3 1 0� � � �; ; ; ;
� �3 1 2 2 0 1 1� � � �B B B x B; ;
�1 0 1 0 1 2 1 4 2 3 3� � � � �B x B x x B x B x B ; T B T2 3 1 0� �; .
Êàê óæå îòìå÷àëîñü, ýòàï ðåàëèçàöèè ñõåìû ÊÌÓÓ â äàííîé ñòàòüå íå ðàñ-
ñìàòðèâàåòñÿ. Îäíàêî àâòîðàìè ðåàëèçîâàíà ÑÀÏÐ, ïîçâîëÿþùàÿ ñîâìåñòíî
ñ ïàêåòîì Xilinx ISE Webpack ñèíòåçèðîâàòü ïðåäëîæåííûå ñõåìû ÊÌÓÓ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 167
Ò à á ë è ö à 1
T T1 2
Êîäû âåðøèí äëÿ ÎËÖ (� � �3 2 1)
�0
(000)
�1
(001)
�2
(010)
�3
(011)
�4
(100)
�5
(101)
�6
(110)
�7
(111)
00 b0 b3 b6 b8 b11 b13 b15 b17
01 b1 b4 b7 b9 b12 b14 b16 —
10 b2 b5 ( )b20 b10 ( )b22 ( )b23 ( )b24 —
11 ( )b18 ( )b19 — ( )b21 — — — —
Ðèñ. 3. Ôðàãìåíòû ñîäåðæèìîãî óïðàâëÿþùåé ïàìÿòè äëÿ
ÊÌÓÓ: ñ ðàñøèðåíèåì ôîðìàòà ìèêðîêîìàíä (à); ñ ìîäè-
ôèêàöèåé ÎËÖ àëãîðèòìà óïðàâëåíèÿ (á)
1
0 1 0
0
1
—
—
Àäðåñ Ìèêðîêîìàíäà
�1
bm
ÎËÖ
0 0 1
�2
�i
—
b3
b4
b5
b6
b7
�1 �2 �3 T2 T1
0
0
01
11
0
1
0
0
01
11
yE y1 y2 y3 y4 y5 y6 y0 z2 z1
00
00
0 001010
0 000 000000
0 000 000000
0 000 000000
10 010000
1001 000000
1 00
10
0 000100
00 101000
1
0 1 0
0
1
—
Àäðåñ Ìèêðîêîìàíäà
�1
bm
ÎËÖ
0 0 1
�2
�i
b3
b4
b5
b6
b7
�1 �2 �3 T2 T1
0
0
01
11
0
1
0
0
01
11
yE
y1 y2
y3 y4 y5 y6 y0
0 001010
b19
b20
(z2) (z1)
10 010000
11 000000
00 000100
10 000100
10 101000
00 000100
00 000000
à
á
ÐÅÇÓËÜÒÀÒÛ ÈÑÑËÅÄÎÂÀÍÈÉ
Àíàëèç ïðîâåäåí ñ ïîìîùüþ ðàçðàáîòàííîé ÑÀÏÐ óïðàâëÿþùèõ àâòîìàòîâ,
êîòîðàÿ ïî îïèñàíèþ ãðàô-ñõåìû àëãîðèòìà óïðàâëåíèÿ â ôîðìàòå XML ñèí-
òåçèðóåò ìîäåëè ñòðóêòóð óïðàâëÿþùåãî àâòîìàòà. Ïîä ìîäåëüþ ïîíèìàåòñÿ
VHDL-îïèñàíèå ñõåìû óñòðîéñòâà è ôàéëû ïðîøèâêè ÏÇÓ (äëÿ óñòðîéñòâ
ñ ïàìÿòüþ). Ýòè ìîäåëè ïåðåäàþòñÿ â ñèñòåìó Xilinx ISE Webpack, ãäå ïðîèñ-
õîäèò èõ èìïëåìåíòàöèÿ â îäíó èç äîñòóïíûõ ìèêðîñõåì. Ôàéëû ïðîåêòà èì-
ïëåìåíòàöèè óñòðîéñòâà ñîäåðæàò èíôîðìàöèþ î çàäåéñòâîâàííûõ àïïàðàòóð-
íûõ ðåñóðñàõ ìèêðîñõåìû, î êðèòè÷åñêèõ ïóòÿõ ñëåäîâàíèÿ ñèãíàëà, âðåìåí-
íûõ ïîêàçàòåëÿõ óñòðîéñòâà, ïîòðåáëÿåìîé óñòðîéñòâîì ìîùíîñòè è äð.
Äëÿ ýêñïåðèìåíòà âûáðàíû ÃÑÀ ñî ñëåäóþùèìè ïàðàìåòðàìè: îò 10 äî 500
âåðøèí ñ øàãîì 10; îò 50 % äî 90 % îïåðàòîðíûõ âåðøèí ñ øàãîì 10 %; 15 ìèê-
ðîîïåðàöèé; ïÿòü ëîãè÷åñêèõ óñëîâèé.
Äëÿ êàæäîé ÃÑÀ ñèíòåçèðîâàíà ñòðóêòóðà ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ (CS),
à òàêæå èññëåäóåìûå FCS- è MCS-ñòðóêòóðû. Äëÿ ñðàâíåíèÿ ñ êëàññîì àâòîìà-
òîâ ñ æåñòêîé ëîãèêîé òàêæå ñèíòåçèðîâàíû àâòîìàòû Ìèëè. Êàæäîå èçìåðåíèå,
ïðåäñòàâëåííîå íà ãðàôèêàõ, ÿâëÿåòñÿ ñðåäíèì çíà÷åíèåì ðåçóëüòàòîâ ñèíòåçà
ïÿòè ðàçëè÷íûõ ÃÑÀ ñ îäèíàêîâûìè ïàðàìåòðàìè.
Àíàëèç àïïàðàòóðíûõ çàòðàò ïîêàçàë ýôôåêòèâíîñòü ïðèìåíåíèÿ ïðåäëàãàå-
ìûõ ìåòîäèê äëÿ âñåõ èññëåäóåìûõ ÃÑÀ (ðèñ. 4).
Ïðåäëîæåííûå ñòðóêòóðû ÊÌÓÓ (ñì. ðèñ. 4) òðåáóþò ìåíüøå àïïàðàòóðíûõ
çàòðàò, ÷åì áàçîâàÿ ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ è àâòîìàò Ìèëè. Îòìåòèì, ÷òî ñ
ðîñòîì äîëè îïåðàòîðíûõ âåðøèí â ÃÑÀ àïïàðàòóðíûå çàòðàòû äëÿ ðåàëèçàöèè
àâòîìàòà Ìèëè óâåëè÷èâàþòñÿ, à äëÿ ðåàëèçàöèè óñòðîéñòâà êëàññà ÊÌÓÓ —
óìåíüøàþòñÿ. Ðàñõîæäåíèÿ â çíà÷åíèÿõ àïïàðàòóðíûõ çàòðàò äëÿ FCS- è MCS-
ñòðóêòóð ÊÌÓÓ ìèíèìàëüíû è èìåþò õàðàêòåð ñòàòèñòè÷åñêèõ îòêëîíåíèé. Äëÿ
äàëüíåéøåãî ñðàâíåíèÿ äàííûõ ñòðóêòóð èññëåäóåì âðåìåííûå õàðàêòåðèñòèêè
ïîëó÷åííûõ ñõåì.
 êà÷åñòâå âðåìåííûõ õàðàêòåðèñòèê âûáðàíû ïåðèîä ñèíõðîñèãíàëà è äëè-
òåëüíîñòü ôîðìèðîâàíèÿ âûõîäíûõ ôóíêöèé. Ïåðâûé ïàðàìåòð èìååò ñìûñë,
êîãäà ëîãè÷åñêèå óñëîâèÿ çàäàíû â çàâèñèìîñòè îò ðåæèìà ðàáîòû. Åñëè âûáîð
âåòâè àëãîðèòìà îáóñëîâëåí ðåçóëüòàòîì ïðåäûäóùåé îïåðàöèè, òî èìååò ñìûñë
âòîðîé âðåìåííîé ïàðàìåòð, îïðåäåëÿþùèé ìàêñèìàëüíîå âðåìÿ ïîñëå ôîðìè-
ðîâàíèÿ ïîñëåäíåãî èç ëîãè÷åñêèõ óñëîâèé, ÷åðåç êîòîðîå óñòðîéñòâî ñãåíåðèðó-
åò âûõîäíûå ôóíêöèè.
168 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
Ò à á ë è ö à 2
Bi k Bi( ) bm A MIm( ) Xh �h �h h
B0 00
b3 00100 x1 �1 — 1
b8 01100 x x1 2 � 2 �1 — 2
b6 01000 x x1 2 � 2 — 3
B1 01
b15 11000 x4 � 3 � 2 — 4
b17 11100 x4 � 3 � 2 �1 — 5
B2 10
b11 10000 x3 � 3 — 6
b13 10100 x3 � 3 �1 — 7
B3 11 b5 00110 1 �1 T2 8
Àíàëèç ãðàôèêîâ íà ðèñ. 5 ïîçâîëÿåò ñäåëàòü âûâîä î òîì, ÷òî ïðåäëîæåí-
íûå ñòðóêòóðû ÊÌÓÓ íå òîëüêî çàíèìàþò ìåíüøóþ ïëîùàäü, íî è ìîãóò èìåòü
ìåíüøåå âðåìÿ öèêëà, ÷åì ÊÌÓÓ ñ ðàçäåëåíèåì êîäîâ è àâòîìàò Ìèëè. Îäíàêî
ñðàâíåíèå ïåðèîäà ñèãíàëà ñèíõðîíèçàöèè ïî-ïðåæíåìó íå ïîçâîëÿåò ñäåëàòü
âûâîä î ïðåäïî÷òèòåëüíîé ñòðóêòóðå óïðàâëÿþùåãî óñòðîéñòâà.
Ïðîâåäåííûå èññëåäîâàíèÿ äëèòåëüíîñòè ôîðìèðîâàíèÿ âûõîäíûõ ôóíêöèé
(ðèñ. 6) ïîêàçàëè, ÷òî ñòðóêòóðà ÊÌÓÓ ñ ðàñøèðåíèåì ôîðìàòà ìèêðîêîìàíä
ôîðìèðóåò âûõîäíûå ôóíêöèè áûñòðåå ÊÌÓÓ ñ ìîäèôèêàöèåé ÎËÖ àëãîðèòìà
óïðàâëåíèÿ äëÿ âñåõ ðàññìîòðåííûõ ÃÑÀ. Ýòî îáóñëîâëåíî äîïîëíèòåëüíîé ñõå-
ìîé íà âûõîäå óñòðîéñòâà, êîòîðàÿ â ìîìåíòû ïåðåõîäà àâòîìàòà îò îäíîé ÎËÖ ê
äðóãîé íå ïîçâîëÿåò òðàêòîâàòü êîä êëàññà ÏÎËÖ êàê âûõîäíûå ñèãíàëû.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 169
Ðèñ. 4. Ãðàôèêè àïïàðàòóðíûõ çàòðàò ïðè ðåàëèçàöèè ðàçëè÷íûõ ñòðóêòóð ÊÌÓÓ, êîãäà ÃÑÀ
ñîäåðæèò 70 % îïåðàòîðíûõ âåðøèí (à) è 90 % îïåðàòîðíûõ âåðøèí (á)
0
100
200
300
400
500
600
100 200 300 400 500
×èñëî âåðøèí ÃÑÀ
CS
FCS
MCS
Mealy
×
è
ñ
ë
î
L
U
T
-ý
ë
å
ì
å
í
òî
â
à
0
50
100
150
100 200 300 400 500
CS
FCS
MCS
Mealy
×èñëî âåðøèí ÃÑÀ
×
è
ñë
î
L
U
T
-ý
ë
åì
å
í
ò
î
â
á
Ðèñ. 5. Ãðàôèêè ïåðèîäà ñèíõðîñèãíàëà ñõåì ðàçëè÷íûõ óïðàâëÿþùèõ óñòðîéñòâ, êîãäà ÃÑÀ
ñîäåðæèò 70 % îïåðàòîðíûõ âåðøèí (à) è 90 % îïåðàòîðíûõ âåðøèí (á)
0
2
4
6
8
100 200 300 400 500
CS
FCS
MCS
Mealy
×èñëî âåðøèí ÃÑÀ
Ï
åð
è
î
ä
ñ
è
ã
í
àë
à
ñè
í
õ
ð
î
í
è
ç
àö
è
è
,
í
ñ
à
0
2
4
6
8
10
100 200 300 400 500
CS
FCS
MCS
Mealy
×èñëî âåðøèí ÃÑÀ
Ï
åð
è
î
ä
ñ
è
ã
í
àë
à
ñè
í
õ
ð
î
í
è
ç
àö
è
è
,
í
ñ
á
Îòìåòèì, ÷òî âñå ïîëó÷åííûå ñõåìû óïðàâëÿþùèõ óñòðîéñòâ ñ ïàìÿòüþ èñ-
ïîëüçîâàëè íå áîëåå îäíîãî áëîêà âñòðîåííîé ïàìÿòè ìèêðîñõåìû FPGA.
ÇÀÊËÞ×ÅÍÈÅ
Ðàñøèðåíèå ôîðìàòà ìèêðîêîìàíä è ìîäèôèêàöèÿ ÎËÖ èñõîäíûõ ÃÑÀ ïîêà-
çàëè ñíèæåíèå àïïàðàòóðíûõ çàòðàò â ñðåäíåì íà 40 % ïî ñðàâíåíèþ ñ áàçî-
âîé ñòðóêòóðîé ÊÌÓÓ ïðè ðåàëèçàöèè ñõåì ÓÓ â áàçèñå ñîâðåìåííûõ ìèê-
ðîñõåì FPGA.
Äëÿ ðåàëèçàöèè ïðåäëîæåííûõ ñòðóêòóð ÊÌÓÓ â áàçèñå ìèêðîñõåìû Spartan-3
ôèðìû Xilinx àâòîðàìè ïîëó÷åíà àíàëèòè÷åñêàÿ çàâèñèìîñòü ìåæäó ïàðàìåòðàìè
âõîäíîé ÃÑÀ è íåîáõîäèìûìè ïðè ðåàëèçàöèè óñòðîéñòâà àïïàðàòóðíûìè çàòðàòà-
ìè. Çàâèñèìîñòü èìååò âèä Q N N p� �
�( , , , )0 026 2 56 10112 , ãäå N — îáùåå êîëè-
÷åñòâî âåðøèí ÃÑÀ, p — ÷àñòü îïåðàòîðíûõ âåðøèí â íåé, p �[ , ; , ]0 5 0 9 . Äàííóþ
çàâèñèìîñòü ìîæíî èñïîëüçîâàòü äëÿ äðóãèõ FPGA-ìèêðîñõåì ôèðìû Xilinx ñ ÷å-
òûðåõâõîäîâûìè LUT-ýëåìåíòàìè. Ïîãðåøíîñòü ôîðìóëû äëÿ ÃÑÀ ñ êîëè÷å-
170 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1
Ðèñ. 6. Ãðàôèêè äëèòåëüíîñòè ôîðìèðîâàíèÿ âûõîäíûõ ôóíêöèé ÓÓ, êîãäà ÃÑÀ ñîäåðæèò 70 %
îïåðàòîðíûõ âåðøèí (à) è 90 % îïåðàòîðíûõ âåðøèí (á), à òàêæå ãðàôèêè îòíîñèòåëüíîé äëè-
òåëüíîñòè ôîðìèðîâàíèÿ âûõîäíûõ ôóíêöèé, â ñëó÷àå, åñëè ÃÑÀ ñîäåðæèò 90 % îïåðàòîðíûõ
âåðøèí (çíà÷åíèÿ äëÿ MCS-ñòðóêòóðû íîðìèðîâàíû îòíîñèòåëüíî çíà÷åíèé äëÿ FCS-
ñòðóêòóðû) (â)
0
5
10
15
20
100 200 300 400 500
Â
ð
åì
ÿ
,
í
ñ CS
FCS
MCS
Mealy
×èñëî âåðøèí ÃÑÀ
à
0
5
10
15
20
100 200 300 400 500
CS
FCS
MCS
MealyÂ
ð
å
ì
ÿ
,
í
ñ
×èñëî âåðøèí ÃÑÀ
á
80
90
100
110
120
0 50 100 150 200 250 300 350 400 450 500
Î
òí
î
ñè
òå
ë
ü
í
î
å
â
ð
åì
ÿ,
%
MCS/FCS
Norm
×èñëî âåðøèí ÃÑÀ
â
ñòâîì âåðøèí áîëåå 70 íå ïðåâûøàåò 20%, â òî âðåìÿ êàê äëÿ ìàëûõ ÃÑÀ ñòàòè-
ñòè÷åñêàÿ ïîãðåøíîñòü ìîæåò äîñòèãàòü âåëè÷èíû àïïàðàòóðíûõ çàòðàò.
Äëèòåëüíîñòü ïåðèîäà ñèíõðîñèãíàëà è âðåìÿ ôîðìèðîâàíèÿ âûõîäíûõ ñèã-
íàëîâ äëÿ ïðåäëîæåííûõ ñòðóêòóð ÊÌÓÓ ñîñòàâëÿþò ïðèáëèçèòåëüíî 1,7–2,5 íñ
ïî ñðàâíåíèþ ñ 5–6 íñ äëÿ àâòîìàòà Ìèëè, ïðè÷åì äëÿ ÊÌÓÓ ýòè çíà÷åíèÿ ïî-
ñòîÿííû è çàâèñÿò îò òèïà ìèêðîñõåìû, à â àâòîìàòå Ìèëè çàäåðæêè ðàñòóò ïðè
óâåëè÷åíèè ñëîæíîñòè ñõåìû. Èñïîëüçîâàíèå ñïåöèàëèçèðîâàííîé ÑÀÏÐ óïðàâ-
ëÿþùèõ óñòðîéñòâ ìíîãîêðàòíî ñîêðàùàåò âðåìÿ ðàçðàáîòêè öèôðîâîãî óñòðîé-
ñòâà (ñ íåñêîëüêèõ ÷àñîâ äî íåñêîëüêèõ ìèíóò äëÿ ÃÑÀ íåáîëüøîé ñëîæíîñòè).
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. B a r a n o v S . Logic and system design of digital systems. — Tallinn: TUT press, 2008. — 266 p.
2. Ã ë ó ø ê î â Â . Ì . Ñèíòåç öèôðîâûõ àâòîìàòîâ. — Ì.: Ôèçìàòãèç, 1962. — 476 ñ.
3. D e M i c h e l i G . Synthesis and optimization of digital circuits. — N.Y.: McGraw-Hill, 1994. —
541 p.
4. 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. — 272 p.
5. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . , Å ô è ì å í ê î Ê . Í . Îïòèìèçàöèÿ ñõåì êîìïî-
çèöèîííûõ ìèêðîïðîãðàììíûõ óñòðîéñòâ óïðàâëåíèÿ, ðåàëèçóåìûõ íà ÏËÈÑ // Êèáåðíåòèêà
è ñèñòåìíûé àíàëèç. — 2011. — ¹ 1. — Ñ. 179–188.
6. Ã ð ó ø â è ö ê è é Ð . , Ì ó ð ñ à å â À . , Ó ã ð þ ì î â Å . Ïðîåêòèðîâàíèå ñèñòåì íà ìèêðî-
ñõåìàõ ïðîãðàììèðóåìîé ëîãèêè. — ÑÏá: ÁÕÂ-Ïåòåðáóðã, 2002. — 636 ñ.
7. Ñ î ë î â ü å â  .  . , Ê ë è ì î â è ÷ À . Ñ . Ëîãè÷åñêîå ïðîåêòèðîâàíèå öèôðîâûõ ñèñòåì íà
îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì. — Ì.: Ãîðÿ÷àÿ Ëèíèÿ – Òåëåêîì,
2008 ã. — 376 ñ.
8. Ê ó ç å ë è í Ì . ÏËÈÑ ôèðìû Xilinx: ñåìåéñòâî SpartanTM-3. — http://chip-news.ru/ar-
chive/chipnews/200305/2.html
9. R O M - b a s e d FSM implementation using input multiplexing in FPGA devices / R. Senha-
dji-Navarro, I. Garcia-Vargas, G. Jim�nez-Moreno, A. Civit-Ballcels // Electronics Letters. — 2004.
— 40, N 20. — P. 1249–1251.
10. R a w s k i M . , S e l v a r a j H . , L u b a T . An application of functional decomposition in
ROM-based FSM implementation in FPGA devices // J. of Syst. Archit. — 2005. — 51, N 6-7. —
P. 424–434.
11. S k l y a r o v V . Synthesis and implementation of RAM-based finite state machines in FPGAs //
10th Intern. Conf. «Field-Programmable Logic and Applications: The Roadmap to Reconfigurable
Computing», Proc., FPL 2000 Villach, Austria, Aug. 27–30, 2000. — P. 718–727.
12. T i w a r i A . , T o m k o K . A . Saving power by mapping finite-state machines into embedded
memory blocks in FPGAs // Proc. — Des., Automation and Test in Europe Conf. and Exhib. —
2004. — 2. — P. 916–921.
13. G a r c i a E . Creating finite state machines using true dual-port fully synchronous selectRAM blocks
// Xcell J. — 2000. — N 38. — P. 36–38.
14. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . , Ö î ë î ë î Ñ . À . Îïòèìèçàöèÿ ñõåìû àâòîìàòà
Ìóðà, ðåàëèçóåìîé â áàçèñå ÏËÈÑ // Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. — 2009. — ¹ 5. —
Ñ. 180–186.
15. B a r k a l o v A . , T i t a r e n k o L . Logic synthesis for FSM-based control units. — Berlin:
Springer, 2009. — 233 p.
16. Ô ð å í ê å ë ü Á . Ñ . , Ê ó ç ü ì è ÷ Ì . Ñ . Xilinx WebPACK ISE. — http://ru.wikibooks.org/wiki/
Xilinx_WebPACK_ISE.
17. Ñ ð å ä ñ ò â à ïðîåêòèðîâàíèÿ è ïðîãðàììèðîâàíèÿ ôèðìû Altera. — http://www.altera.ru/
cgi-bin/go?19.
Ïîñòóïèëà 13.10.2011
Ïîñëå äîðàáîòêè 12.03.2012
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2013, ¹ 1 171
|
| id | nasplib_isofts_kiev_ua-123456789-86175 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0023-1274 |
| language | Russian |
| last_indexed | 2025-11-25T20:47:31Z |
| publishDate | 2013 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Титаренко, Л.А. Мирошкин, А.Н. 2015-09-08T18:26:35Z 2015-09-08T18:26:35Z 2013 Модификация системы адресации микрокоманд в устройстве управления с разделением кодов / А.А. Баркалов, Л.А. Титаренко, А.Н. Мирошкин // Кибернетика и системный анализ. — 2013. — Т. 49, № 1. — С. 161-171. — Бібліогр.: 17 назв. — рос. 0023-1274 https://nasplib.isofts.kiev.ua/handle/123456789/86175 004.3 Запропоновано дві модифікації системи адресації мікрокоманд у композиційному мікропрограмному пристрої керування з розділенням кодів. Модифікації базуються на використанні псевдоеквівалентних станів автомата для зменшення кількості рядків таблиці переходів автомата і, як наслідок, складності комбінаційної частини схеми пристрою. Запропоновано методики синтезу композиційних пристроїв з модифікованою системою мікрокоманд. Наведено результати досліджень. Визначено області доцільного застосування запропонованих методик. Two modifications of microcommand addressing system in compositional microprogram control unit with code sharing are proposed in the paper. The modifications are based on using the automaton pseudoequivalent states to reduce the row number in the automaton transition table and thus to reduce the complexity of the combinational part of the device. The methods are proposed to synthesize compositional control units with mo dified microcommand addressing system. The research results are given and the appropriate fields of application of the proposed methods are identified. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Модификация системы адресации микрокоманд в устройстве управления с разделением кодов Модифікація системи адресації мікрокоманд у пристрої керування з розділенням кодів Modification of microcommand addressing system in control unit with code sharing Article published earlier |
| spellingShingle | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов Баркалов, А.А. Титаренко, Л.А. Мирошкин, А.Н. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов |
| title_alt | Модифікація системи адресації мікрокоманд у пристрої керування з розділенням кодів Modification of microcommand addressing system in control unit with code sharing |
| title_full | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов |
| title_fullStr | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов |
| title_full_unstemmed | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов |
| title_short | Модификация системы адресации микрокоманд в устройстве управления с разделением кодов |
| title_sort | модификация системы адресации микрокоманд в устройстве управления с разделением кодов |
| topic | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/86175 |
| work_keys_str_mv | AT barkalovaa modifikaciâsistemyadresaciimikrokomandvustroistveupravleniâsrazdeleniemkodov AT titarenkola modifikaciâsistemyadresaciimikrokomandvustroistveupravleniâsrazdeleniemkodov AT miroškinan modifikaciâsistemyadresaciimikrokomandvustroistveupravleniâsrazdeleniemkodov AT barkalovaa modifíkacíâsistemiadresacíímíkrokomandupristroíkeruvannâzrozdílennâmkodív AT titarenkola modifíkacíâsistemiadresacíímíkrokomandupristroíkeruvannâzrozdílennâmkodív AT miroškinan modifíkacíâsistemiadresacíímíkrokomandupristroíkeruvannâzrozdílennâmkodív AT barkalovaa modificationofmicrocommandaddressingsystemincontrolunitwithcodesharing AT titarenkola modificationofmicrocommandaddressingsystemincontrolunitwithcodesharing AT miroškinan modificationofmicrocommandaddressingsystemincontrolunitwithcodesharing |