Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС
Запропоновано два методи адресації мікрокоманд у разі інтерпретації алгоритму керування композиційними мікропрограмними пристроями керування (КМПК). Метод уточненої адресації дозволяє однозначно ідентифікувати виходи операторних лінійних ланцюгів (ОЛЛ) мінімальним числом адресних розрядів. Метод опт...
Gespeichert in:
| Veröffentlicht in: | Кибернетика и системный анализ |
|---|---|
| Datum: | 2011 |
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2011
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/72212 |
| 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: | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС / А.А. Баркалов, Л.А. Титаренко, К.Н. Ефименко // Кибернетика и системный анализ. — 2011. — № 1. — С. 179-188. — Бібліогр.: 14 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859709478935461888 |
|---|---|
| author | Баркалов, А.А. Титаренко, Л.А. Ефименко, К.Н. |
| author_facet | Баркалов, А.А. Титаренко, Л.А. Ефименко, К.Н. |
| citation_txt | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС / А.А. Баркалов, Л.А. Титаренко, К.Н. Ефименко // Кибернетика и системный анализ. — 2011. — № 1. — С. 179-188. — Бібліогр.: 14 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | Запропоновано два методи адресації мікрокоманд у разі інтерпретації алгоритму керування композиційними мікропрограмними пристроями керування (КМПК). Метод уточненої адресації дозволяє однозначно ідентифікувати виходи операторних лінійних ланцюгів (ОЛЛ) мінімальним числом адресних розрядів. Метод оптимальної адресації орієнтований на поданні класів псевдоеквівалентних ОЛЛ мінімальним числом узагальнених інтервалів простору, що кодує. Наведено приклади для кожного із запропонованих методів. Обидва методи дозволяють зменшити число елементів табличного типу в схемі КМПК у порівнянні зі схемою для базової структури. В основному зменшення апаратурних витрат супроводжується зменшенням часу такту КМПК.
|
| first_indexed | 2025-12-01T04:29:21Z |
| format | Article |
| fulltext |
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 179
ÓÄÊ 004.383.3
À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ, Ê.Í. ÅÔÈÌÅÍÊÎ
ÎÏÒÈÌÈÇÀÖÈß ÑÕÅÌ ÊÎÌÏÎÇÈÖÈÎÍÍÛÕ
ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÛÕ ÓÑÒÐÎÉÑÒÂ ÓÏÐÀÂËÅÍÈß,
ÐÅÀËÈÇÓÅÌÛÕ ÍÀ ÏËÈÑ
Êëþ÷åâûå ñëîâà: êîìïîçèöèîííîå ìèêðîïðîãðàììíîå óñòðîéñòâî óïðàâëåíèÿ,
ÏËÈÑ, îïòèìèçàöèÿ, àäðåñàöèÿ ìèêðîêîìàíä.
ÂÂÅÄÅÍÈÅ
Óñòðîéñòâî óïðàâëåíèÿ (ÓÓ) — âàæíûé áëîê ëþáîé öèôðîâîé ñèñòåìû [1]. Äëÿ
çàäàíèÿ çàêîíà ôóíêöèîíèðîâàíèÿ ÓÓ ÷àñòî èñïîëüçóåòñÿ ìîäåëü öèôðîâîãî àâ-
òîìàòà [2]. Îäíà èç àêòóàëüíûõ çàäà÷, âîçíèêàþùèõ ïðè ñèíòåçå ëîãè÷åñêèõ
ñõåì ÓÓ, — çàäà÷à óìåíüøåíèÿ àïïàðàòóðíûõ çàòðàò ïðè ñîõðàíåíèè çàäàííîãî
áûñòðîäåéñòâèÿ [3]. Ìåòîäû ðåøåíèÿ ýòîé çàäà÷è çàâèñÿò êàê îò èñïîëüçóåìîé
ìîäåëè ÓÓ, òàê è îò õàðàêòåðèñòèê àëãîðèòìà óïðàâëåíèÿ è ýëåìåíòîâ, èç êîòî-
ðûõ ðåàëèçóåòñÿ ñõåìà. Â íàñòîÿùåå âðåìÿ äëÿ ðåàëèçàöèè ñõåì ÓÓ øèðîêî èñ-
ïîëüçóþòñÿ ïðîãðàììèðóåìûå ëîãè÷åñêèå ñõåìû (ÏËÈÑ) òèïà FPGA (field-
programmable gate array) [4, 5]. Ïîäîáíûå ÏËÈÑ âêëþ÷àþò ëîãè÷åñêèå ýëåìåíòû
òàáëè÷íîãî òèïà (LUT, look-up tables) è âñòðîåííûå áëîêè ïàìÿòè ÅÌÂ
(embedded memory block). Äàëåå óñëîâèìñÿ èñïîëüçîâàòü îáîçíà÷åíèå ÏËÈÑ äëÿ
FPGA, ËÝ (ëîãè÷åñêèé ýëåìåíò) äëÿ LUT è ÂÁÏ (âñòðîåííûé áëîê ïàìÿòè) äëÿ
ÅÌÂ. Äëÿ ËÝ ñâîéñòâåííî îãðàíè÷åííîå ÷èñëî âõîäîâ (4–6), ÷òî ïðèâîäèò ê íå-
îáõîäèìîñòè ôóíêöèîíàëüíîé äåêîìïîçèöèè [6] ðåàëèçóåìûõ ñèñòåì áóëåâûõ
ôóíêöèé.  ðåçóëüòàòå óâåëè÷èâàåòñÿ ÷èñëî óðîâíåé â ñõåìå ÓÓ è óìåíüøàåòñÿ
áûñòðîäåéñòâèå öèôðîâîé ñèñòåìû â öåëîì. Â íàñòîÿùåé ðàáîòå ïðåäëàãàþòñÿ
ìåòîäû óìåíüøåíèÿ àïïàðàòóðíûõ çàòðàò ïðè ðåàëèçàöèè íà ÏËÈÑ ñõåì, èíòåð-
ïðåòèðóþùèõ ëèíåéíûå ãðàô-ñõåìû àëãîðèòìà (ÃÑÀ) [7]. Äëÿ ëèíåéíûõ ÃÑÀ
õàðàêòåðíî íàëè÷èå öåïî÷åê áåçóñëîâíî âûïîëíÿåìûõ ìèêðîêîìàíä, ÷òî ïîçâî-
ëÿåò èñïîëüçîâàòü äëÿ èõ èíòåðïðåòàöèè àâòîìàò Ìóðà, íàçâàííûé â [8] êîìïî-
çèöèîííûì ìèêðîïðîãðàììíûì óñòðîéñòâîì óïðàâëåíèÿ (ÊÌÓÓ).
ÎÑÍÎÂÛ ÊÎÌÏÎÇÈÖÈÎÍÍÛÕ ÌÈÊÐÎÏÐÎÃÐÀÌÌÍÛÕ ÓÑÒÐÎÉÑÒÂ ÓÏÐÀÂËÅÍÈß
Ïóñòü àëãîðèòì óïðàâëåíèÿ ïðåäñòàâëåí ÃÑÀ Ã, õàðàêòåðèçóåìîé ìíîæåñòâàìè
âåðøèí B E E b bE� � �1 2 0{ }, è äóã Å, ñîåäèíÿþùèõ ýòè âåðøèíû. Çäåñü E1 —
ìíîæåñòâî îïåðàòîðíûõ âåðøèí, ñîäåðæàùèõ íàáîðû ìèêðîîïåðàöèé èç ìíî-
æåñòâà Y y yN� { }1, ,� ; E
2
— ìíîæåñòâî óñëîâíûõ âåðøèí, ñîäåðæàùèõ ýëå-
ìåíòû ìíîæåñòâà ëîãè÷åñêèõ óñëîâèé X x x L� { }1, ,� ; b bE0 , — ñîîòâåòñòâåííî
íà÷àëüíàÿ è êîíå÷íàÿ âåðøèíû ÃÑÀ. Ââåäåì ðÿä îïðåäåëåíèé, âçÿòûõ èç [8] è
íåîáõîäèìûõ äëÿ äàëüíåéøåãî èçëîæåíèÿ.
Îïðåäåëåíèå 1. Îïåðàòîðíîé ëèíåéíîé öåïüþ (ÎËÖ) ÃÑÀ Ã íàçûâàåòñÿ êî-
íå÷íàÿ ïîñëåäîâàòåëüíîñòü îïåðàòîðíûõ âåðøèí � g g gFb b
g
� � �1, ,� òàêàÿ, ÷òî
äëÿ ëþáîé ïàðû åå ñîñåäíèõ êîìïîíåíò ñóùåñòâóåò äóãà � � ��b b Egi gi, 1 , ãäå
i Fg� �1 1, ,� .
© À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, Ê.Í. Åôèìåíêî, 2011
Îïðåäåëåíèå 2. Îïåðàòîðíàÿ âåðøèíà b Dq
g� , ãäå D g — ìíîæåñòâî âåðøèí,
âõîäÿùèõ â ÎËÖ � g , íàçûâàåòñÿ âõîäîì ÎËÖ � g , åñëè ñóùåñòâóåò äóãà
� � �b b Et q, , ãäå b Dt
g .
Îïðåäåëåíèå 3. Îïåðàòîðíàÿ âåðøèíà b Dq
g� íàçûâàåòñÿ âûõîäîì ÎËÖ � g ,
åñëè ñóùåñòâóåò äóãà � � �b b Eq t, , ãäå b Dt
g .
Ïóñòü äëÿ ÃÑÀ à ïîëó÷åíû ìíîæåñòâî ÎËÖ C G� { }� �1, ,� , ñîîòâåòñòâóþ-
ùåå ðàçáèåíèþ ìèíèìàëüíîé ìîùíîñòè ìíîæåñòâà E1 íà G êëàññîâ, êàæäûé èç êî-
òîðûõ îòâå÷àåò îïðåäåëåíèþ 1. Ïóñòü I Î( ), ( )
— ñîîòâåòñòâåííî ìíîæåñòâî
âõîäîâ è âûõîäîâ ÎËÖ � g C� . Êàæäàÿ âåðøèíà b Eq � 1 ñîîòâåòñòâóåò ìèêðîêî-
ìàíäå, èìåþùåé àäðåñ A bq( ) . Âûïîëíèì àäðåñàöèþ ìèêðîêîìàíä òàê, ÷òîáû
âûïîëíÿëîñü óñëîâèå
A b A bgi gi( ) ( )� � �1 1 , (1)
ãäå g G i Fg� � �{ } { }1 1 1, ... , , ,� .  ýòîì ñëó÷àå ÃÑÀ à ìîæåò áûòü èíòåðïðåòè-
ðîâàíà ÊÌÓÓ U 1 [7], ñòðóêòóðíàÿ ñõåìà êîòîðîãî ïðèâåäåíà íà ðèñ. 1. Ýòî
óñòðîéñòâî âêëþ÷àåò áëîê àäðåñàöèè ìèêðîêîìàíä (ÁÀÌ), ñ÷åò÷èê (ÑÒ), áëîê
ìèêðîîïåðàöèé (ÁÌÎ) è òðèããåð âûáîðêè (ÒÂ). ÊÌÓÓ U 1 ôóíêöèîíèðóåò ñëå-
äóþùèì îáðàçîì.
Ïî ñèãíàëó Start â ÑÒ çàïèñûâàåòñÿ íóëåâîé àäðåñ, ñîîòâåòñòâóþùèé íà÷àëó
ìèêðîïðîãðàììû, èíòåðïðåòèðóþùåé ÃÑÀ Ã. Îäíîâðåìåííî òðèããåð ÒÂ óñòàíàâ-
ëèâàåòñÿ â åäèíè÷íîå ñîñòîÿíèå (Fetch=1) è ìèêðîêîìàíäû ìîãóò âûáèðàòüñÿ èç
áëîêà ïàìÿòè ÁÌÎ. Åñëè ÑÒ ñîäåðæèò àäðåñ A bq( ) è b Oq ( )
, òî îäíîâðåìåííî
ñ íàáîðîì ìèêðîîïåðàöèé Y bq( ) , çàïèñàííûõ â âåðøèíå b Eq � 1, ÁÌÎ ôîðìèðóåò
ñèãíàë y
0
. Åñëè y0 1� , òî ñîäåðæèìîå ÑÒ óâåëè÷èâàåòñÿ íà åäèíèöó ïî ñèãíàëó
Clock. Ïðè ýòîì ïðîèñõîäèò áåçóñëîâíûé ïåðåõîä, ñîîòâåòñòâóþùèé (1). Åñëè
b Oq � ( )
, òî ñèãíàë y0 íå ôîðìèðóåòñÿ, à ÁÀÌ âûðàáàòûâàåò ôóíêöèè
âîçáóæäåíèÿ ÑÒ:
� �� ( , )T X . (2)
180 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
CT
ÁÌÎ
Ô T
Start
TÂR
SStart
FetchClock
+1
Ðèñ. 1. Ñòðóêòóðíàÿ ñõåìà ÊÌÓÓ U1
X
yE
y0
YÁÀÌ
 ýòîì ñëó÷àå ïî ñèãíàëó Clock â ÑÒ ôîðìèðóåòñÿ àäðåñ ïåðåõîäà èç âûõîäà
íåêîòîðîé ÎËÖ � g C� . Åñëè � � �b b Eq E, , òî ÁÌÎ ôîðìèðóåò ñèãíàë yE , âûçû-
âàþùèé óñòàíîâêó ÒÂ â íóëåâîå ñîñòîÿíèå. Ïðè ýòîì Fetch = 0, ïðåêðàùàåòñÿ
âûáîðêà ìèêðîêîìàíä è ôóíêöèîíèðîâàíèå ÊÌÓÓ U 1.
Ïðè ðåàëèçàöèè ñõåìû ÊÌÓÓ U
1
íà ÏËÈÑ ñõåìà ÁÀÌ, ÑÒ è ÒÂ ñòðîèòñÿ íà
ËÝ, à ñõåìà ÁÌÎ ðåàëèçóåòñÿ íà ÂÁÏ. Òàêèì îáðàçîì, ìîäåëü ïîçâîëÿåò ñáàëàíñè-
ðîâàíî èñïîëüçîâàòü âîçìîæíîñòè ñîâðåìåííûõ ÏËÈÑ. Íåäîñòàòîê ìîäåëè — íà-
ëè÷èå ìíîæåñòâà ôóíêöèé îáðàòíîé ñâÿçè T , ñîâïàäàþùåãî ñ ðàçðÿäíîñòüþ àäðåñà
ìèêðîêîìàíäû
R MA � �
log 2 , (3)
ãäå M E� | |1 . Â íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ äâà ìåòîäà àäðåñàöèè ìèêðîêî-
ìàíä, ïîçâîëÿþùèõ óìåíüøèòü ÷èñëî ñèãíàëîâ îáðàòíîé ñâÿçè â áëîêå ÁÀÌ.
ÏÐÅÄËÀÃÀÅÌÛÅ ÌÅÒÎÄÛ ÀÄÐÅÑÀÖÈÈ ÌÈÊÐÎÊÎÌÀÍÄ
Âûõîäíûå ñèãíàëû Y ÊÌÓÓ çàâèñÿò îò ñîäåðæèìîãî ÑÒ, ò.å.
Y Y T� ( ) , y y T0 0� ( ) , y y TE E� ( ) . (4)
Òàêèì îáðàçîì, ÊÌÓÓ ÿâëÿåòñÿ àâòîìàòîì Ìóðà, à àäðåñà ìèêðîêîìàíä ñîîò-
âåòñòâóþò êîäàì åãî ñîñòîÿíèé. Õàðàêòåðíàÿ îñîáåííîñòü ÊÌÓÓ çàêëþ÷àåòñÿ â
òîì, ÷òî â êà÷åñòâå êîäîâ, ó÷àñòâóþùèõ â ôîðìèðîâàíèè ôóíêöèé (2), èñïîëüçóþò-
ñÿ òîëüêî àäðåñà âûõîäîâ ÎËÖ. Î÷åâèäíî, ÷òî äëÿ îäíîçíà÷íîé èäåíòèôèêàöèè G
ÎËÖ äîñòàòî÷íî
R GG � �
log 2 (5)
ïåðåìåííûõ.
Åñëè íà÷àëüíûå àäðåñà ìèêðîêîìàíä èçìåíèòü òàê, ÷òîáû äëÿ èäåíòèôèêàöèè
âûõîäîâ èñïîëüçîâàòü R R A0 � ïåðåìåííûõ, òî ñëîæíîñòü ôóíêöèé (2) óìåíüøèòü-
ñÿ. Î÷åâèäíî, ÷òî â ïðåäåëå R RG0 � . Èòàê, ïåðâàÿ âîçìîæíîñòü îïòèìèçàöèè ñõå-
ìû ÁÀÌ çàêëþ÷àåòñÿ â îäíîçíà÷íîé èäåíòèôèêàöèè âûõîäîâ ÎËÖ � g C� ñ èñ-
ïîëüçîâàíèåì R R A0 � ïåðåìåííûõ.
Õàðàêòåðíàÿ îñîáåííîñòü àâòîìàòà Ìóðà — íàëè÷èå êëàññîâ ïñåâäîýêâèâà-
ëåíòíûõ ñîñòîÿíèé [8], ñîîòâåòñòâóþùèõ ñîñòîÿíèÿì ýêâèâàëåíòíîãî àâòîìàòà
Ìèëè. Äëÿ îïòèìèçàöèè ñõåìû àâòîìàòà Ìóðà ñîñòîÿíèÿ äîëæíû áûòü çàêîäèðîâà-
íû òàê, ÷òîáû áîëüøèíñòâî êëàññîâ ïñåâäîýêâèâàëåíòíûõ ñîñòîÿíèé (â ïðåäåëå —
âñå êëàññû) ïðåäñòàâëÿëèñü îáîáùåííûìè èíòåðâàëàìè êîäèðóþùåãî ïðîñòðà-
íñòâà. Ýòà èäåÿ ìîæåò èñïîëüçîâàòüñÿ è äëÿ îïòèìèçàöèè ñõåìû ÊÌÓÓ U
1
.
Íàçîâåì ÎËÖ � �g i C, � ïñåâäîýêâèâàëåíòíûìè ÎËÖ , åñëè èõ âûõîäû ñîåäèíå-
íû ñ âõîäîì îäíîé è òîé æå âåðøèíû ÃÑÀ Ã. Íàéäåì ðàçáèåíèå �C IB B� { }1, ,�
ìíîæåñòâà ÎËÖ Ñ íà êëàññû ïñåâäîýêâèâàëåíòíûõ ÎËÖ. Âûïîëíèì àäðåñàöèþ ìèê-
ðîêîìàíä òàê, ÷òîáû êàæäûé êëàññ Bi C�� ïðåäñòàâëÿëñÿ îäíèì îáîáùåííûì èí-
òåðâàëîì R
A
-ìåðíîãî áóëåâà ïðîñòðàíñòâà. Òàêîé èíòåðâàë èñïîëüçóåòñÿ â êà÷åñòâå
êîäà K Bi( ) êëàññà Bi C�� è ó÷àñòâóåò â ôîðìèðîâàíèè ôóíêöèé (2).
Íàçîâåì ïåðâûé ïîäõîä óòî÷íåííîé àäðåñàöèåé ìèêðîêîìàíä, à âòîðîé —
áëî÷íîé àäðåñàöèåé ìèêðîêîìàíä. Ðàññìîòðèì ìåòîäû ñèíòåçà ÊÌÓÓ U
2
è U 3,
îñíîâàííûõ íà ýòèõ ïîäõîäàõ. Ïðè ýòîì ñòðóêòóðíûå ñõåìû ÊÌÓÓ U 1 – U 3 ñîâïà-
äàþò, à ðàçíèöà â àïïàðàòóðíûõ çàòðàòàõ ñâÿçàíà òîëüêî ñ ðàçíûìè àäðåñàìè âûõî-
äîâ ÎËÖ � g C� . Ðàññìîòðèì îáà ïðåäëàãàåìûõ ìåòîäà îïòèìèçàöèè íà ïðèìåðå
ÃÑÀ
1 (ðèñ. 2).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 181
Ïåðâûé ýòàï ñèíòåçà äëÿ U 2 è U 3 ñâÿçàí ñ ôîðìèðîâàíèåì ìíîæåñòâà ÎËÖ Ñ,
óäîâëåòâîðÿþùåãî ñëåäóþùèì óñëîâèÿì [8]:
D D i j i j Gi j� �� � �( , , , , ){ }1 � , D D D EG1 2
1� � � �� , G� min. (6)
Ìåòîäû ðåøåíèÿ ýòîé çàäà÷è äîñòàòî÷íî èçâåñòíû [7] è â ñëó÷àå ÊÌÓÓ, ðåà-
ëèçóåìîãî ïî ÃÑÀ
1, äàþò ñëåäóþùåå ðåøåíèå: C � { }� �1 4, ,� , ãäå
�1 1 2 3� � �b b b, , , � 2 4 5 6� � �b b b, , , � 3 7 8� � �b b, , � 4 9 10 11� � �b b b, , . Èòàê, äëÿ
ÃÑÀ
� G M� �4 11, , R A � 4, RG � 2 . Äëÿ àäðåñàöèè ìèêðîêîìàíä èñïîëüçóþò-
ñÿ ýëåìåíòû ìíîæåñòâà T T T� { }1 4, ,� . Êàê ïðàâèëî, ñ÷åò÷èê ÑÒ èìååò âõîäû
òèïà D [6], ïîýòîìó ìíîæåñòâî � � { }D D1 4, ,� . Óñëîâèìñÿ â äàëüíåéøåì îáîçíà-
÷àòü U i j( )
òîò ôàêò, ÷òî ÃÑÀ
j èíòåðïðåòèðóåòñÿ ÊÌÓÓ U i ( , , )i �1 2 3 .
ÑÈÍÒÅÇ ÊÌÓÓ Ñ ÓÒÎ×ÍÅÍÍÎÉ ÀÄÐÅÑÀÖÈÅÉ ÌÈÊÐÎÊÎÌÀÍÄ
Äëÿ àäðåñàöèè ìèêðîêîìàíä ÊÌÓÓ U
1
èñïîëüçóåòñÿ ìåòîäèêà èç [8]. Ïðè ýòîì
àëãîðèòì ñîñòîèò èç G øàãîâ. Íà ïåðâîì øàãå àäðåñóþòñÿ ìèêðîêîìàíäû, ñîîò-
âåòñòâóþùèå âåðøèíàì ÎËÖ, âõîä êîòîðîé ñâÿçàí ñ âûõîäîì íà÷àëüíîé âåðøè-
íû b
0
.  ñëó÷àå ÊÌÓÓ U 1 1( )
àäðåñàöèÿ íà÷èíàåòñÿ ñ ÎËÖ �1. Íà g-ì øàãå
âûïîëíÿåòñÿ àäðåñàöèÿ ìèêðîêîìàíä, ñîîòâåòñòâóþùèõ âåðøèíàì ÎËÖ � g
( , , )g G� �1 . Ïðè ýòîì â êà÷åñòâå ïåðâîãî àäðåñà äëÿ ÎËÖ � g áåðåòñÿ óâåëè-
÷åííûé íà åäèíèöó àäðåñ âûõîäà ÎËÖ � g�1.  ñëó÷àå ÊÌÓÓ U 1 1( )
àäðåñà
ìèêðîêîìàíä ïîêàçàíû â òàáë. 1.
182 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
Start
y1, y2
b0
b1
y3 b2
y2, y5 b7
x1
1
0
x3
y1, y2 b9
y2, y5 b10
y4 b11
y1, y3 b4
y5 b5
End bÅ
1
0
x2
1
0
y3, y4 b3
y3 b8
y3, y4 b6
b12
b13
b14
Ðèñ. 2. Èñõîäíàÿ ãðàô-ñõåìà àëãîðèòìà
1
Íàçîâåì ðàññìîòðåííûé ðàíåå ïðîöåññ ñòàíäàðòíîé àäðåñàöèåé ìèêðîêîìàíä,
à ïîëó÷åííûå àäðåñà — ñòàíäàðòíûìè àäðåñàìè ìèêðîêîìàíä. Ïóñòü O A Og g, ( )
îçíà÷àþò ñîîòâåòñòâåííî âûõîä ÎËÖ � g C� è àäðåñ ýòîãî âûõîäà.
Èç òàáë. 1 ñëåäóåò, ÷òî A O( )
1
0010� , A O( )2 0101� , A O( )3 0111� ,
A O( )4 1010� . Î÷åâèäíî, àäðåñ A O( )
4
íå èìååò çíà÷åíèÿ, òàê êàê íå ó÷àñòâóåò
â ôîðìèðîâàíèè ôóíêöèé (2). Ýòî ñâÿçàíî ñ òåì, ÷òî ïðè äîñòèæåíèè âûõîäà
O b4 11� ÊÌÓÓ ôîðìèðóåò ñèãíàë yE è ôóíêöèîíèðîâàíèå ïðåêðàùàåòñÿ. Àíàëèç
àäðåñîâ A O( )1 –A O( )
3
ïîêàçûâàåò, ÷òî äëÿ îäíîçíà÷íîé èäåíòèôèêàöèè âûõîäîâ
O1– O3 äîñòàòî÷íî òðåõ ïåðåìåííûõ: T T T1 2 3, , . Ïðè ýòîì O1 õàðàêòåðèçóåòñÿ êîäîì
K O( )1 001� , O2 — K O( )2 010� è O3 — K O( )3 011� . Òàê êàê R
G
� 2 , òî íåîáõîäè-
ìî ñäåëàòü ïîïûòêó òàêîé àäðåñàöèè ìèêðîêîìàíä, ÷òîáû âûõîäû ÎËÖ � �1 3� õà-
ðàêòåðèçîâàëèñü äâóìÿ ïåðåìåííûìè T Tr � . Ïóñòü C C
1
� — ìíîæåñòâî ÎËÖ , âû-
õîäû êîòîðûõ íå ñâÿçàíû ñ âõîäîì âåðøèíû bE . Êàê áûëî ïîêàçàíî ðàíåå, òîëüêî âû-
õîäû ÎËÖ � g C�
1
äîëæíû èäåíòèôèöèðîâàòüñÿ ñ ïîìîùüþ RG ïåðåìåííûõ.
 íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ ìåòîä óòî÷íåííîé àäðåñàöèè, ìèíèìèçèðóþ-
ùèé âåëè÷èíó R0.
1. Ïîëîæèòü R R
G0 � è âûïîëíèòü ñòàíäàðòíóþ àäðåñàöèþ ìèêðîêîìàíä.
2. Ïîñòðîèòü òàáëèöó àäðåñàöèè, èìåþùóþ 2 0R
ñòîëáöîâ, îòìå÷åííûõ ïåðå-
ìåííûìè T TR1 0
, ,� , è 2 0R RA � ñòðîê, îòìå÷åííûõ ïåðåìåííûìè T TR RA0 1� , ,� .
3. Îñóùåñòâèòü ñäâèã èíôîðìàöèè, íà÷èíàÿ ñ ïåðâîé êîìïîíåíòû ÎËÖ
� j C�
1
, åñëè âûõîäû ÎËÖ � �i j C, � 1, ãäå j i� , íàõîäÿòñÿ â îäíîì ñòîëáöå òàá-
ëèöû àäðåñàöèè. Îñâîáîæäàþùèåñÿ êëåòêè òàáëèöû àäðåñàöèè çàïîëíèì çíàêîì *.
Ñäâèã ïðîäîëæàåì äî òåõ ïîð, ïîêà âûõîäû Oi è O j íå îêàæóòñÿ â ðàçíûõ ñòîëá-
öàõ òàáëèöû àäðåñàöèè.
4. Åñëè â ïðîöåññå ñäâèãà ïðîèñõîäèò âûõîä çà ïðåäåëû àäðåñíîãî ïðîñòðà-
íñòâà ðàçìåðíîñòè R A , òî R R0 0 1:� � .
5. Åñëè R R A0 � , òî ïåðåéòè ê ï. 2.
6. Êîíåö.
Ðàññìîòðèì ïðèìåíåíèå ýòîé ïðîöåäóðû ê ÊÌÓÓ U 1 1( )
. Ïîëîæèì R0 2� è ïî-
ñòðîèì íà÷àëüíóþ òàáëèöó àäðåñàöèè, èñïîëüçóÿ ñòàíäàðòíûå àäðåñà èç òàáë. 1 (ðèñ. 3).
Âûõîäû ÎËÖ �1 è � 2 íàõîäÿòñÿ â ðàçíûõ ñòîëáöàõ òàáëèöû àäðåñàöèè, à âû-
õîäû ÎËÖ � 2 è � 3 — â îäíîì. Ñäâèíåì èíôîðìàöèþ íà îäèí ðàçðÿä âíèç, íà÷è-
íàÿ ñ âåðøèíû b7 (ðèñ. 4).
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 183
Ò à á ë è ö à 1 . Àäðåñàöèÿ ìèêðîêîìàíä ÊÌÓÓ U 1 1( )
T T1 4� bq T T1 4� bq T T1 4� bq T T1 4� bq
0000 b1 0011 b4 0110 b7 1001 b10
0001 b2 0100 b5 0111 b8 1010 b11
0010 b3 0101 b6 1000 b9 1011 *
Êàê âèäíî èç ðèñ. 4, âûõîäû ÎËÖ � g C� �
1
= { }� � �1 2 3, , íàõîäÿòñÿ â ðàçíûõ ñòîëáöàõ òàá-
ëèöû êîäèðîâàíèÿ. Ñëåäîâàòåëüíî, íà ðèñ. 4 ïðè-
âåäåíû óòî÷íåííûå àäðåñà ìèêðîêîìàíä. Î÷å-
âèäíî, ÷òî êîä âûõîäà Og ñîâïàäàåò ñ èíôîðìà-
öèåé, èäåíòèôèöèðóþùåé ñîîòâåòñòâóþùèé
ñòîëáåö. Èòàê, äëÿ ÊÌÓÓ U 2 1( )
èìååì
K O( )1 00� , K O( )2 01� è K O( )3 10� . Çíà÷èò,
â ðàññìàòðèâàåìîì ïðèìåðå âûõîäû ÎËÖ
� g C� 1 îäíîçíà÷íî èäåíòèôèöèðóþòñÿ ñ ïî-
ìîùüþ RG � 2 ðàçðÿäîâ.
Äëÿ ñèíòåçà ñõåìû ÊÌÓÓ U 2 1( )
íåîáõîäè-
ìî âûïîëíèòü ñëåäóþùèå ýòàïû [7]:
1) ñôîðìèðîâàòü ñèñòåìó ôîðìóë ïåðåõîäà
ÊÌÓÓ;
2) ñôîðìèðîâàòü òàáëèöó ïåðåõîäîâ ÊÌÓÓ;
3) ñôîðìèðîâàòü ôóíêöèþ âîçáóæäåíèÿ
ñ÷åò÷èêà ÑÒ;
4) ñôîðìèðîâàòü ñîäåðæèìîå áëîêà ÁÌÎ;
5) ðåàëèçîâàòü ñõåìó ÊÌÓÓ â çàäàííîì ýëåìåíòíîì áàçèñå.
Ñèñòåìà ôîðìóë ïåðåõîäà [1] ôîðìèðóåòñÿ òîëüêî äëÿ âûõîäîâ ÎËÖ � g C�
1
.
 äàííîì ïðèìåðå ýòà ñèñòåìà èìååò ñëåäóþùèé âèä:
O x b x b1 1 7 1 4� � ,
O x x b x x b x b2 2 3 2 2 3 9 2 4� � � , (7)
O x x b x x b x b3 2 3 2 2 3 9 2 4� � � .
Òàáëèöà ïåðåõîäîâ ÊÌÓÓ ñòðîèòñÿ ïî ñèñòåìå ôîðìóë ïåðåõîäà. Çäåñü X h —
âõîäíîé ñèãíàë, îïðåäåëÿþùèé ïåðåõîä èç Og â bq è ðàâíûé êîíúþíêöèè íåêîòî-
ðûõ ýëåìåíòîâ ìíîæåñòâà X (èëè èõ îòðèöàíèé); � �h � — íàáîð ôóíêöèé âîç-
áóæäåíèÿ ïàìÿòè, ïðèíèìàþùèõ åäèíè÷íîå çíà÷åíèå äëÿ ôîðìèðîâàíèÿ â ÑÒ àä-
ðåñà A bq( ) . Äëÿ äàííîãî ïðèìåðà òàáëèöà ïåðåõîäîâ èìååò H 2 1 8( )
� ñòðîê
(òàáë. 2), ãäå H i j( )
îçíà÷àåò ÷èñëî ñòðîê òàáëèöû ïåðåõîäîâ ÊÌÓÓ U i j( )
.
Àäðåñà ìèêðîêîìàíä A bq( ) áåðóòñÿ èç ðèñ. 4. Ñâÿçü òàáë. 2 ñ ñèñòåìîé (7) î÷å-
âèäíà.
184 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
00 01 10 11
00 b1 b5 b9 *
01 b2 b6 b10 *
10 b3 b7 b11 *
11 b4 b8 * *
Ðèñ. 3. Ñòàíäàðòíûå àäðåñà ìèêðî-
êîìàíä ÊÌÓÓ U2 1( )
T T1 2
T T3 4
00 01 10 11
00 b1 b5 b8 *
01 b2 b6 b9 *
10 b3 * b10 *
11 b4 b7 b11 *
Ðèñ. 4. Óòî÷íåííûå àäðåñà ìèêðîêî-
ìàíä ÊÌÓÓ U2 1( )
T T1 2
T T3 4
Ò à á ë è ö à 2 . Ïîñëåäîâàòåëüíîñòü ïåðåõîäîâ ÊÌÓÓ U 2 1( )
Og K Og( ) bq A bq( ) X h �h h
O1 00 b7 0111 x1 D D D2 3 4 1
b4 0011 x1 D D3 4 2
O2 01 b2 0001 x x2 3 D4 3
b9 1001 x x2 3 D D1 4 4
b4 0011 x2 D D3 4 5
O3 10 b2 0001 x x2 3 D4 6
b9 1001 x x2 3 D D1 4 7
b4 0011 x2 D D3 4 8
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 185
Òàáëèöà ïåðåõîäîâ ÊÌÓÓ ñëóæèò îñíîâîé äëÿ ôîðìèðîâàíèÿ ñèñòåìû (2), çà-
âèñÿùåé îò òåðìîâ Fh , ãäå
F T Xh
r
R
r
lrh
h�
�
�
�
��
�
�
�
��
�
�1
0
. (8)
 ôîðìóëå (8) ïåðâàÿ êîíúþíêöèÿ ñîîòâåòñòâóåò êîäó K Og( ) èç h-é ñòðîêè
òàáëèöû (h � �1, , H j2
( )
); lrh�{ }0 1, — çíà÷åíèå r-ãî ðàçðÿäà êîäà K Og( ) èç h-é
ñòðîêè òàáëèöû, T T T T r Rr r r r
0 1
01� � �, ( , , )� . Íàïðèìåð, èç òàáë. 2 èìååì
D F F1 4 7� � � T T x x T T x x1 2 2 3 1 2 2 3� .
Îòìåòèì, ÷òî â ôîðìóëó Dr �� äëÿ ÊÌÓÓ U 1 1( )
âõîäÿò âñå ïåðåìåííûå
T Tr � , ÷òî ïîâûøàåò âåðîÿòíîñòü íåîáõîäèìîñòè ôóíêöèîíàëüíîé äåêîìïîçèöèè
äëÿ ñèñòåìû (2).
Áëîê ÁÌÎ ðåàëèçóåòñÿ íà ÂÁÏ è çàäàåòñÿ òàáëèöåé èñòèííîñòè ñ âõîäàìè
T Tr � è âûõîäàìè Y y yE�{ }0, . Ñîäåðæèìîå ýòîé òàáëèöû ñòðîèòñÿ òðèâèàëüíûì
îáðàçîì:
1) íàáîð ìèêðîîïåðàöèé Y bq( ) çàïèñûâàåòñÿ â ñòðîêó òàáëèöû, ñîîòâåòñòâóþ-
ùóþ àäðåñó A bq( ) ;
2) ïåðåìåííàÿ y0 çàïèñûâàåòñÿ ïî àäðåñó A bq( ) , åñëè b Oq g� ;
3) ïåðåìåííàÿ yE çàïèñûâàåòñÿ ïî àäðåñó A bq( ) , åñëè � � �b b Et E, .
Ïðèìåíåíèå ýòîé ïðîöåäóðû ê ÃÑÀ
1 ïðèâîäèò ê ñîäåðæèìîìó áëîêà ÁÌÎ,
ñèìâîëüíîå ïðåäñòàâëåíèå êîòîðîãî ïîêàçàíî â òàáë. 3.
Àäðåñà ìèêðîêîìàíä äëÿ òàáë. 3 âçÿòû èç ðèñ. 4, à ñîäåðæèìîå ñëîâ ïàìÿòè —
èç âåðøèí ÃÑÀ
1. Â òàáë. 3 çíàê «–» ñîîòâåòñòâóåò íåîïðåäåëåííîìó ñîäåðæàíèþ
ñëîâà, êîãäà àäðåñ äëÿ ìèêðîêîìàíä ÊÌÓÓ U 2 1( )
íå èñïîëüçóåòñÿ.
Ðåàëèçàöèÿ ñõåìû ÊÌÓÓ U j2( )
ñâîäèòñÿ ê ðåàëèçàöèè ñèñòåìû (2) íà ËÝ
òàáëè÷íîãî òèïà, à ñèñòåìû (4) — íà âñòðîåííûõ áëîêàõ ïàìÿòè. Äëÿ ýòîé öåëè èñ-
ïîëüçóþòñÿ ñòàíäàðòíûå ïðîìûøëåííûå ïàêåòû [9, 10]. Â íàñòîÿùåé ñòàòüå ýòîò
ýòàï íå ðàññìàòðèâàåòñÿ.
ÑÈÍÒÅÇ ÊÌÓÓ Ñ ÎÏÒÈÌÀËÜÍÎÉ ÀÄÐÅÑÀÖÈÅÉ ÌÈÊÐÎÊÎÌÀÍÄ
Àíàëèç òàáë. 2 ïîêàçûâàåò, ÷òî ïåðåõîäû èç âûõîäîâ O2 è O3 èäåíòè÷íû äëÿ
îäèíàêîâûõ âõîäíûõ íàáîðîâ X h . Ýòî ñâÿçàíî ñ òåì, ÷òî âåðøèíû b O6 2� è
b O8 3� ñâÿçàíû ñ âõîäîì óñëîâíîé âåðøèíû b13 ÃÑÀ
1 (ðèñ. 2). Òàêèì îáðà-
çîì, ÎËÖ � �2 3 1, �C ïñåâäîýêâèâàëåíòíû. Åñëè âûõîäû O2 è O3 âõîäÿò
â îäèí îáîáùåííûé èíòåðâàë ÷åòûðåõìåðíîãî áóëåâà ïðîñòðàíñòâà, òî ÷èñëî
ñòðîê òàáëèöû ïåðåõîäîâ óìåíüøàåòñÿ ïî ñðàâíåíèþ ñ H 2( )�� .  îáùåì ñëó-
÷àå ïàðàìåòð H 2( )
îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì:
Ò à á ë è ö à 3 . Ñîäåðæèìîå áëîêà ïàìÿòè
Àäðåñ Ñëîâî Àäðåñ Ñëîâî Àäðåñ Ñëîâî Àäðåñ Ñëîâî
0000 y y y0 1 2 0100 y y0 5 1000 y3 1100 –
0001 y y0 3 0101 y y3 4 1001 y y y0 1 2 1101 –
0010 y y3 4 0110 – 1010 y y y0 2 5 1110 –
0011 y y y0 1 2 0111 y y y0 2 5 1011 y yE4 1111 –
H H Cg g
g
G
2
1
( ) ,
�
�
(9)
ãäå C g — áóëåâà ïåðåìåííàÿ, ðàâíàÿ åäèíèöå, åñëè � g C� 1, H g — ÷èñëî ïåðå-
õîäîâ èç âûõîäà ÎËÖ � g C�
1
.
Åñëè êàæäûé êëàññ Bi C�� ïðåäñòàâëÿåòñÿ îäíèì îáîáùåííûì èíòåðâàëîì
R A -ìåðíîãî áóëåâà ïðîñòðàíñòâà, òî òàáëèöà ïåðåõîäîâ ÊÌÓÓ âêëþ÷àåò H 3( )
ñòðîê, ãäå
H H gi
i
I
3
1
( )
�
�
. (10)
 âûðàæåíèè (10) ïàðàìåòð Hgi ðàâåí ÷èñëó ïåðåõîäîâ H g äëÿ ëþáîé èç ÎËÖ
� g iB� . Ïðè ýòîì ðàçáèåíèå �C íàõîäèòñÿ äëÿ ìíîæåñòâà C1. Êàê îòìå÷àëîñü ðà-
íåå, îïòèìàëüíàÿ àäðåñàöèÿ ìèêðîêîìàíä ïîðîæäàåò ÊÌÓÓ U 3. Ñòðóêòóðû ÊÌÓÓ
U 1 è U 3 ñîâïàäàþò. Ìåòîä ñèíòåçà ÊÌÓÓ U 3 âêëþ÷àåò ñëåäóþùèå ýòàïû:
1) ôîðìèðîâàíèå ìíîæåñòâ Ñ è C1 äëÿ ÃÑÀ Ã;
2) ôîðìèðîâàíèå ðàçáèåíèÿ �C ìíîæåñòâà C1 íà êëàññû ïñåâäîýêâèâàëåí-
òíûõ ÎËÖ;
3) îïòèìàëüíàÿ àäðåñàöèÿ ìèêðîêîìàíä.
Äàëåå ñëåäóåò ïÿòü ýòàïîâ, ðàññìîòðåííûõ äëÿ ÊÌÓÓ U
2
. Íàèáîëåå òðóäíûé
èç íèõ — àäðåñàöèÿ ìèêðîêîìàíä. Äëÿ åå âûïîëíåíèÿ ìîæíî èñïîëüçîâàòü ìîäè-
ôèöèðîâàííûå àëãîðèòìû èç ðàáîò [11,12] ëèáî àëãîðèòì ESPRESSO [6]. Ðàññìîò-
ðèì óñëîâèÿ, ïðè êîòîðûõ îïòèìàëüíàÿ àäðåñàöèÿ ìèêðîêîìàíä ñ | |Bi �1 äëÿ i I�1,
âîçìîæíà.
Ïóñòü R Bi i� �
log 2| | , òîãäà äëÿ ðàçìåùåíèÿ âûõîäîâ ÎËÖ � g iB� òðåáóåòñÿ
êóá áóëåâà ïðîñòðàíñòâà, ðàçìåðíîñòü êîòîðîãî îïðåäåëÿåòñÿ êàê
V i Ii
Ri� �2 1( , ) . (11)
Ïóñòü d i — ìàêñèìàëüíîå ÷èñëî êîìïîíåíò â ÎËÖ � g iB� , Q di i� �
log 2 .
 ýòîì ñëó÷àå äëÿ ðàçìåùåíèÿ êîìïîíåíò ÎËÖ � g C�
1
òðåáóåòñÿ êóá
ðàçìåðíîñòè
W i Ii
Qi� �2 1( , ) . (12)
Òàêèì îáðàçîì, äëÿ ðàçìåùåíèÿ âñåõ êîìïîíåíò ÎËÖ � g iB� òðåáóåòñÿ êóá
ðàçìåðà
! i i iV W i I� " �( , )1 . (13)
Äëÿ àäðåñàöèè ìèêðîêîìàíä èñïîëüçóåòñÿ êàðòà Êàðíî, â êîòîðîé äëÿ àäðåñîâ
ìèêðîêîìàíä, ñîîòâåòñòâóþùèõ êîìïîíåíòàì ÎËÖ � g C� 1, îòâîäèòñÿ ! êëåòîê,
ãäå
! � �2 1
RA M . (14)
Ïàðàìåòð M1 îïðåäåëÿåò ÷èñëî êîìïîíåíò äëÿ ÎËÖ � g C 1. Åñëè âûïîëíÿåò-
ñÿ óñëîâèå
! !#
�
i
i
I
1
, (15)
òî àäðåñà êîìïîíåíò ëþáîé ÎËÖ � g C�
1
ìîãóò áûòü ðàñïîëîæåíû â ñîñåäíèõ
êëåòêàõ êàðòû Êàðíî, ïðè÷åì êîìïîíåíòû âñåõ ÎËÖ � g iB� ðàñïîëîæåíû â
186 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
îäíîì êóáå ðàçìåðíîñòè ! i .
Äëÿ ðàññìàòðèâàåìîãî ïðèìåðà C
1 1� {� ,
� �2 3, } , �C B B� { }1 2, , B1 1� { }� , B2 2 3� { }� �,
è îäèí èç âàðèàíòîâ îïòèìàëüíîé àäðåñàöèè
ìèêðîêîìàíä ïðåäñòàâëåí íà ðèñ. 5.
Ìîäèôèêàöèÿ êàðòû çàêëþ÷àåòñÿ â òîì, ÷òî
ïî âåðòèêàëè çàïèñûâàþòñÿ äâîè÷íûå íàáîðû,
ñëåäóþùèå â åñòåñòâåííîì ïîðÿäêå. Êóáû, ñîîò-
âåòñòâóþùèå êëàññàì B B C1 2, �� è ÎËÖ � 3,
äàþò ñëåäóþùèå êîäû, îäíîçíà÷íî èäåíòèôèöè-
ðóþùèå êëàññû: Bi C�� : K B( ) * *1 00� , K B( ) * * *2 1� . Êàê âèäíî èç ýòèõ êîäîâ
êëàññîâ, èñïîëüçóåòñÿ RG � 2 ïåðåìåííûõ, êàê è â ñëó÷àå ÊÌÓÓ U 2 1( )
.
Ñèñòåìà ôîðìóë ïåðåõîäà äëÿ ÊÌÓÓ U 3 1( )
ïðåäñòàâëåíà ñèñòåìîé (7).
Ñ ó÷åòîì îïòèìàëüíîé àäðåñàöèè ìèêðîêîìàíä âûõîä O1 ïðåäñòàâëÿåòñÿ êëàññîì
B1, à âûõîäû O2 è O3 — êëàññîì B2. Ïîñòðîèì ìîäèôèöèðîâàííóþ ñèñòåìó ôîð-
ìóë ïåðåõîäà, çàìåíèâ âûõîäû ÎËÖ � g iB� êëàññàìè Bi C�� :
B x b x b1 1 7 1 4� � ;
B x x b x x b x b2 2 3 2 2 3 9 2 4� � � . (16)
Òàáëèöà ïåðåõîäîâ ÊÌÓÓ U3 ñòðîèòñÿ ïî ìîäèôèöèðîâàííîé ñèñòåìå ôîð-
ìóë ïåðåõîäà è âêëþ÷àåò ñòîëáöû: Bi , K Bi( ) , bq , A bq( ) , X h , �h h, .  ñëó÷àå
ÊÌÓÓ U 3 1( )
àäðåñà ìèêðîêîìàíä áåðóòñÿ èç ðèñ. 5, à òàáëèöà ïåðåõîäîâ èìååò
H
3 1 5( )
� ñòðîê (òàáë. 3).
Ýòà òàáëèöà ñëóæèò îñíîâîé äëÿ ôîðìèðîâàíèÿ ñèñòåìû (2), òåðìû êîòîðîé
òàêæå îïðåäåëÿþòñÿ âûðàæåíèåì (8). Îäíàêî â äàííîì ñëó÷àå ïåðâàÿ êîíúþíêöèÿ
ñîîòâåòñòâóåò êîäó K Bi( ) èç h-é ñòðîêè òàáëèöû, à lrh h H� �{ }0 1 1
3
, , * ( , , ( ))�
.
Ëèòåðàëû ýòîé êîíúþíêöèè îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì: T T Tr r r
0 1� �,
� � �T T r Rr r A, ( , , )* 1 1 � . Íàïðèìåð, èç òàáë. 4 èìååì
D F F F T T x T x x T x T T x T x T x1 2 4 5 1 2 1 2 2 3 2 2 1 2 1 2 2 2 3� � � � � � � � � .
Ñîäåðæèìîå ÁÌÎ äëÿ ÊÌÓÓ U 3 ïðîâîäèòñÿ àíàëîãè÷íî âûïîëíåíèþ ýòîãî
ýòàïà äëÿ ÊÌÓÓ U
2
. Ðåàëèçàöèÿ ñõåìû ÊÌÓÓ U 3 ñâîäèòñÿ ê ðåàëèçàöèè ñõåìû
ÁÀÌ íà ËÝ òàáëè÷íîãî òèïà, à ñõåìû ÁÌÎ — íà ÂÁÏ. Ýòè ýòàïû â íàñòîÿùåé
ñòàòüå íå ðàññìàòðèâàþòñÿ.
ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1 187
00 01 10 11
00 b1 * * *
01 b2 * b4 b9
10 b3 b7 b5 b10
11 * b8 b6 b11
Ðèñ. 5. Ìîäèôèöèðîâàííàÿ êàðòà
Êàðíî äëÿ îïòèìàëüíîé àäðåñàöèè
ìèêðîêîìàíä ÊÌÓÓ U3 1( )
T T1 2
T T3 4
Ò à á ë è ö à 4 . Ïîñëåäîâàòåëüíîñòü ïåðåõîäîâ ÊÌÓÓ U 3 1( )
Bi K Bi( ) bq A bq( ) X h �h h
B1 00** b7 0110 x1 D D2 3 1
b4 1101 x1 D D D1 2 4 2
B2 *1** b2 0001 x x2 3 D4 3
b9 1001 x x2 3 D D1 4 4
b4 1101 x2 D D D1 2 4 5
ÇÀÊËÞ×ÅÍÈÅ
Ïðåäëîæåííûå ìåòîäû àäðåñàöèè ìèêðîêîìàíä ïîçâîëÿþò óìåíüøèòü ÷èñëî àðãó-
ìåíòîâ â ôóíêöèÿõ âîçáóæäåíèÿ ñ÷åò÷èêà â ïðåäåëå äî RG . Ïðè ýòîì óïðîùàþòñÿ
óðàâíåíèÿ äëÿ âûõîäíûõ ôóíêöèé áëîêà àäðåñàöèè ìèêðîêîìàíä, ÷òî ïðèâîäèò
ê óìåíüøåíèþ àïïàðàòóðíûõ çàòðàò ïî ñðàâíåíèþ ñ èñõîäíîé ìîäåëüþ ÊÌÓÓ U 1.
Òåîðåòè÷åñêè âñå ìîäåëè U 1–U 3 èìåþò îäèíàêîâóþ äëèòåëüíîñòü òàêòà, íî íà
ïðàêòèêå óïðîùåíèå ðåàëèçóåìûõ óðàâíåíèé ÷àñòî ïðèâîäèò ê óìåíüøåíèþ ÷èñëà
óðîâíåé â êîìáèíàöèîííîé ñõåìå. Òàêèì îáðàçîì, ïðèìåíåíèå ïðåäëîæåííûõ ìå-
òîäîâ àäðåñàöèè ìîæåò ïðèâåñòè ê óìåíüøåíèþ êàê ÷èñëà ËÝ òàáëè÷íîãî òèïà, òàê
è âðåìåíè òàêòà óñòðîéñòâà óïðàâëåíèÿ. Ïðè ýòîì îïòèìàëüíàÿ àäðåñàöèÿ ìèêðî-
êîìàíä áîëåå ýôôåêòèâíà, ÷åì óòî÷íåííàÿ, åñëè âûïîëíÿåòñÿ óñëîâèå (15).
Äëÿ èññëåäîâàíèÿ ýôôåêòèâíîñòè ðàçðàáîòàííûõ ìåòîäîâ áûëè ïîñòðîåíû
VHDL-ìîäåëè ÊÌÓÓ U 1 – U 3. Ïîëó÷åííûå ñèñòåìû óðàâíåíèé ââîäèëèñü â ïàêåò
WebPack ôèðìû Xilinx [10] äëÿ ðåàëèçàöèè ñõåìû ÊÌÓÓ. Ñòàíäàðòíûå òåñòîâûå
ïðèìåðû äëÿ êîíå÷íûõ àâòîìàòîâ [13] íå ñîäåðæàò ëèíåéíûõ ÃÑÀ, ïîýòîìó äëÿ èõ
ãåíåðàöèè ðàçðàáîòàíà ñïåöèàëüíàÿ ïðîãðàììà. Â ðåçóëüòàòå èññëåäîâàíèé îêàçà-
ëîñü, ÷òî ñõåìû ÊÌÓÓ U 2, U 3 âñåãäà èìåëè ìåíüøå àïïàðàòóðíûõ çàòðàò (â ñðåä-
íåì íà 22 %), ÷åì ñõåìû ýêâèâàëåíòíûõ ÊÌÓÓ U 1. Åñëè óñëîâèå (15) âûïîëíÿåòñÿ,
òî ÊÌÓÓ U 3 îáëàäàåò íàèëó÷øèìè õàðàêòåðèñòèêàìè ïî áûñòðîäåéñòâèþ è àïïà-
ðàòóðíûì çàòðàòàì ïî ñðàâíåíèþ ñ ÊÌÓÓ U 1 è U 2. Îòìåòèì òàêæå, ÷òî ìåòîä
îïòèìàëüíîé àäðåñàöèè ìîæåò èñïîëüçîâàòüñÿ è ïðè ðåàëèçàöèè ñõåì ÊÌÓÓ íà
ÏËÈÑ, îñíîâàííûõ íà ìàêðîÿ÷åéêàõ ïðîãðàììèðóåìîé ìàòðè÷íîé ëîãèêè
(ÏÌË) [14]. Ýòî ñâÿçàíî ñ òåì, ÷òî ïðè îïòèìàëüíîé àäðåñàöèè ìèíèìèçèðóåòñÿ
÷èñëî òåðìîâ â ôóíêöèÿõ ñèñòåìû (2), à ìàêðîÿ÷åéêè ÏÌË èìåþò îãðàíè÷åííîå
÷èñëî òåðìîâ. Òàêæå îòìåòèì, ÷òî îáà ìåòîäà àäðåñàöèè íå òðåáóþò óâåëè÷åíèÿ
åìêîñòè ïàìÿòè ÁÌÎ ïî ñðàâíåíèþ ñ áàçîâîé ñõåìîé ÊÌÓÓ U 1.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
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. M i n k s P . , E l i o t I . FSM — based Digital Design using Verilog. — John Wiley & Sons, 2008. —
351 p.
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. D e M i c h e l i G . Synthesis and Optimization of Digital Circuits. — NY: McGraw Hill, 1994. — 626 p.
7. Á à ð ê à ë î â À . À . , Ò è ò à ð å í ê î Ë . À . Ñèíòåç êîìïîçèöèîííûõ ìèêðîïðîãðàììíûõ óñòðîéñòâ
óïðàâëåíèÿ. — Õàðüêîâ: Êîëëåãèóì, 2007. — 302 ñ.
8. Á à ð ê à ë î â À . À . Ìèêðîïðîãðàììíîå óñòðîéñòâî óïðàâëåíèÿ êàê êîìïîçèöèÿ àâòîìàòîâ ñ ïðî-
ãðàììèðóåìîé è æåñòêîé ëîãèêîé // Àâòîìàòèêà è âû÷èñë. òåõíèêà. — 1983. — ¹ 4. — C. 36–41.
9. www.xilinx.com.
10. www.altera.com.
11. À ÷ à ñ î â à Ñ . Í . Àëãîðèòìû ñèíòåçà àâòîìàòîâ íà ïðîãðàììèðóåìûõ ìàòðèöàõ. — Ì.: Ðàäèî è
ñâÿçü, 1987. — 136 ñ.
12. Ç à ê ð å â ñ ê è é À . Ä . , Ï î ò ò î ñ è í Þ . Â . , × å ð å ì è ñ è í î â à Ë . Ä . Îïòèìèçàöèÿ â áóëåâîì
ïðîñòðàíñòâå. — Ìèíñê: Îáúåä. èí-ò ïðîáëåì èíôîðìàòèêè, 2004. — 240 ñ.
13. Y a n g S . Logic Synthesis and Optimization Benchmarks User Guide: (Techn. Rep.) — IWLS — UG —
Sqeyang. / Microelectronics Center of North Carifornia. — 1991. — 43 p.
14. Ñ î ë î â ü å â  .  . , Ê ë è ì î â è ÷ À . Ñ . Ëîãè÷åñêîå ïðîåêòèðîâàíèå öèôðîâûõ ñèñòåì íà îñíîâå
ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èíòåãðàëüíûõ ñõåì. — Ì.: Ãîðÿ÷àÿ ëèíèÿ — Òåëåêîì, 2008. — 376 ñ.
Ïîñòóïèëà 17.04.2009
188 ISSN 0023-1274. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2011, ¹ 1
|
| id | nasplib_isofts_kiev_ua-123456789-72212 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-12-01T04:29:21Z |
| publishDate | 2011 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Баркалов, А.А. Титаренко, Л.А. Ефименко, К.Н. 2014-12-19T22:13:33Z 2014-12-19T22:13:33Z 2011 Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС / А.А. Баркалов, Л.А. Титаренко, К.Н. Ефименко // Кибернетика и системный анализ. — 2011. — № 1. — С. 179-188. — Бібліогр.: 14 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/72212 004.383.3 Запропоновано два методи адресації мікрокоманд у разі інтерпретації алгоритму керування композиційними мікропрограмними пристроями керування (КМПК). Метод уточненої адресації дозволяє однозначно ідентифікувати виходи операторних лінійних ланцюгів (ОЛЛ) мінімальним числом адресних розрядів. Метод оптимальної адресації орієнтований на поданні класів псевдоеквівалентних ОЛЛ мінімальним числом узагальнених інтервалів простору, що кодує. Наведено приклади для кожного із запропонованих методів. Обидва методи дозволяють зменшити число елементів табличного типу в схемі КМПК у порівнянні зі схемою для базової структури. В основному зменшення апаратурних витрат супроводжується зменшенням часу такту КМПК. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Новые средства кибернетики, информатики, вычислительной техники и системного анализа Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС Article published earlier |
| spellingShingle | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС Баркалов, А.А. Титаренко, Л.А. Ефименко, К.Н. Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| title | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС |
| title_full | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС |
| title_fullStr | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС |
| title_full_unstemmed | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС |
| title_short | Оптимизация схем композиционных микропрограммных устройств управления, реализуемых на ПЛИС |
| title_sort | оптимизация схем композиционных микропрограммных устройств управления, реализуемых на плис |
| topic | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| topic_facet | Новые средства кибернетики, информатики, вычислительной техники и системного анализа |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/72212 |
| work_keys_str_mv | AT barkalovaa optimizaciâshemkompozicionnyhmikroprogrammnyhustroistvupravleniârealizuemyhnaplis AT titarenkola optimizaciâshemkompozicionnyhmikroprogrammnyhustroistvupravleniârealizuemyhnaplis AT efimenkokn optimizaciâshemkompozicionnyhmikroprogrammnyhustroistvupravleniârealizuemyhnaplis |