Оптимизация схемы совмещенного автомата в базисе ASIC

Предложен метод уменьшения площади кристалла, занимаемой схемой совмещенного автомата. Метод основан на кодировании классов псевдоэквивалентных состояний автомата Мура дополнительными переменными. Этот подход порождает четырехуровневую схему, реализуемую в виде двух нано-ПЛМ, и позволяет уменьшить п...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2020
Hauptverfasser:	Баркалов, А.А., Титаренко, Л.А., Баев, А.В., Матвиенко, А.В.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут кібернетики ім. В.М. Глушкова НАН України 2020
Schriftenreihe:	Кибернетика и системный анализ
Schlagworte:	Кібернетика
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/190483
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:	Оптимизация схемы совмещенного автомата в базисе ASIC / А.А. Баркалов, Л.А. Титаренко, А.В. Баев, А.В. Матвиенко // Кибернетика и системный анализ. — 2020. — Т. 56, № 6. — С. 3–11. — Бібліогр.: 26 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-190483
record_format	dspace
spelling	irk-123456789-1904832023-06-11T20:20:51Z Оптимизация схемы совмещенного автомата в базисе ASIC Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В. Кібернетика Предложен метод уменьшения площади кристалла, занимаемой схемой совмещенного автомата. Метод основан на кодировании классов псевдоэквивалентных состояний автомата Мура дополнительными переменными. Этот подход порождает четырехуровневую схему, реализуемую в виде двух нано-ПЛМ, и позволяет уменьшить площадь нано-ПЛМ, формирующей микрооперации автомата Мура и дополнительные переменные. Рассмотрен пример синтеза схемы с использованием предложенного метода. Приведены результаты исследований эффективности метода с использованием библиотеки стандартных тестовых автоматов. Запропоновано метод зменшення площі кристала, яку займає схема суміщеного автомата. Метод базується на кодуванні класів псевдоеквівалентних станів автомата Мура додатковими змінними. Цей підхід породжує чотирирівневу схему, яка реалізується у вигляді двох нано-ПЛМ, і дає змогу зменшити площу нано-ПЛМ, яка формує мікрооперації автомата Мура та додаткові змінні. Розглянуто приклад синтезу схеми із застосуванням запропонованого методу. Наведено результати досліджень ефективності методу з використанням бібліотеки стандартних тестових автоматів. A method is proposed for decreasing the area of the ASIC occupied by the scheme of a combined automaton. The method is based on encoding of the classes of pseudoequivalent states of Moore automaton by additional variables. This approach leads to a four-level scheme implemented as two nano-PLAs and decreases the area of nano-PLA generating microoperations of the Moore automaton and additional variables. An example of synthesis with the use of the proposed scheme is considered. The results of the efficiency analysis of the proposed method with the use of a library of benchmarks are presented. 2020 Article Оптимизация схемы совмещенного автомата в базисе ASIC / А.А. Баркалов, Л.А. Титаренко, А.В. Баев, А.В. Матвиенко // Кибернетика и системный анализ. — 2020. — Т. 56, № 6. — С. 3–11. — Бібліогр.: 26 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/190483 004.274 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Кібернетика Кібернетика
spellingShingle	Кібернетика Кібернетика Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В. Оптимизация схемы совмещенного автомата в базисе ASIC Кибернетика и системный анализ
description	Предложен метод уменьшения площади кристалла, занимаемой схемой совмещенного автомата. Метод основан на кодировании классов псевдоэквивалентных состояний автомата Мура дополнительными переменными. Этот подход порождает четырехуровневую схему, реализуемую в виде двух нано-ПЛМ, и позволяет уменьшить площадь нано-ПЛМ, формирующей микрооперации автомата Мура и дополнительные переменные. Рассмотрен пример синтеза схемы с использованием предложенного метода. Приведены результаты исследований эффективности метода с использованием библиотеки стандартных тестовых автоматов.
format	Article
author	Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В.
author_facet	Баркалов, А.А. Титаренко, Л.А. Баев, А.В. Матвиенко, А.В.
author_sort	Баркалов, А.А.
title	Оптимизация схемы совмещенного автомата в базисе ASIC
title_short	Оптимизация схемы совмещенного автомата в базисе ASIC
title_full	Оптимизация схемы совмещенного автомата в базисе ASIC
title_fullStr	Оптимизация схемы совмещенного автомата в базисе ASIC
title_full_unstemmed	Оптимизация схемы совмещенного автомата в базисе ASIC
title_sort	оптимизация схемы совмещенного автомата в базисе asic
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2020
topic_facet	Кібернетика
url	http://dspace.nbuv.gov.ua/handle/123456789/190483
citation_txt	Оптимизация схемы совмещенного автомата в базисе ASIC / А.А. Баркалов, Л.А. Титаренко, А.В. Баев, А.В. Матвиенко // Кибернетика и системный анализ. — 2020. — Т. 56, № 6. — С. 3–11. — Бібліогр.: 26 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT barkalovaa optimizaciâshemysovmeŝennogoavtomatavbaziseasic AT titarenkola optimizaciâshemysovmeŝennogoavtomatavbaziseasic AT baevav optimizaciâshemysovmeŝennogoavtomatavbaziseasic AT matvienkoav optimizaciâshemysovmeŝennogoavtomatavbaziseasic
first_indexed	2025-07-16T13:25:00Z
last_indexed	2025-07-16T13:25:00Z
_version_	1837810120001585152
fulltext	À.À. ÁÀÐÊÀËÎÂ, Ë.À. ÒÈÒÀÐÅÍÊÎ, À.Â. ÁÀÅÂ, À.Â. ÌÀÒÂÈÅÍÊÎ ÓÄÊ 004.274 ÎÏÒÈÌÈÇÀÖÈß ÑÕÅÌÛ ÑÎÂÌÅÙÅÍÍÎÃÎ ÀÂÒÎÌÀÒÀ Â ÁÀÇÈÑÅ ASIC Àííîòàöèÿ. Ïðåäëîæåí ìåòîä óìåíüøåíèÿ ïëîùàäè êðèñòàëëà, çàíèìàåìîé ñõåìîé ñîâìåùåííîãî àâòîìàòà. Ìåòîä îñíîâàí íà êîäèðîâàíèè êëàññîâ ïñåâäîýêâèâàëåíòíûõ ñîñòîÿíèé àâòîìàòà Ìóðà äîïîëíèòåëüíûìè ïåðåìåí- íûìè. Ýòîò ïîäõîä ïîðîæäàåò ÷åòûðåõóðîâíåâóþ ñõåìó, ðåàëèçóåìóþ â âèäå äâóõ íàíî-ÏËÌ, è ïîçâîëÿåò óìåíüøèòü ïëîùàäü íàíî-ÏËÌ, ôîðìèðóþùåé ìèêðîîïåðàöèè àâòîìàòà Ìóðà è äîïîëíèòåëüíûå ïåðåìåííûå. Ðàññìîòðåí ïðèìåð ñèíòåçà ñõåìû ñ èñïîëüçîâàíèåì ïðåäëîæåííîãî ìåòîäà. Ïðèâåäåíû ðåçóëüòàòû èññëåäîâàíèé ýôôåêòèâíîñòè ìåòîäà ñ èñïîëüçîâàíèåì áèáëèîòå- êè ñòàíäàðòíûõ òåñòîâûõ àâòîìàòîâ. Êëþ÷åâûå ñëîâà: ñîâìåùåííûé ìèêðîïðîãðàììíûé àâòîìàò, ñèíòåç, íàíî- ÏËÌ, ASIC, ïñåâäîýêâèâàëåíòíûå ñîñòîÿíèÿ. ÂÂÅÄÅÍÈÅ Øèðîêîå ïðèìåíåíèå âñòðîåííûõ, àâòîíîìíûõ è ìîáèëüíûõ ñèñòåì [1–3] òåñ- íî ñâÿçàíî ñ ïðîáëåìîé óìåíüøåíèÿ ïëîùàäè êðèñòàëëà, çàíèìàåìîé öèôðî- âîé ñèñòåìîé. Ðåøåíèå ýòîé ïðîáëåìû âî ìíîãîì çàâèñèò îò îñîáåííîñòåé ýëåìåíòíîãî áàçèñà [4, 5]. Ïðè ìàññîâîì ïðîèçâîäñòâå íàíîýëåêòðîííûõ èçäå- ëèé öåëåñîîáðàçíî èñïîëüçîâàíèå çàêàçíûõ ÑÁÈÑ òèïà ASIC (application specific integrated circuit) [6, 7]. Ìåòîäû îïòèìèçàöèè ïëîùàäè äëÿ îòäåëüíûõ áëîêîâ çàâèñÿò îò èõ îñîáåííîñòåé [8]. Îäíèì èç âàæíåéøèõ áëîêîâ öèôðîâûõ ñèñòåì ÿâëÿåòñÿ óñòðîéñòâî óïðàâëå- íèÿ [9], êîîðäèíèðóþùåå âçàèìîäåéñòâèå îñòàëüíûõ áëîêîâ. Äëÿ ñèíòåçà ñõåì óñòðîéñòâ óïðàâëåíèÿ èñïîëüçóþòñÿ ðàçëè÷íûå ìîäåëè. Îäíà èç íèõ — ìîäåëü ñîâ- ìåùåííîãî ìèêðîïðîãðàììíîãî àâòîìàòà (ÑÌÏÀ) [10]. Ïîäîáíàÿ ìîäåëü ïîçâîëÿåò ðåàëèçîâàòü àâòîìàòû, èìåþùèå õàðàêòåðèñòèêè, êàê ó àâòîìàòîâ Ìèëè è Ìóðà [8]. Ñõåìà ÑÌÏÀ çàäàåòñÿ ñèñòåìîé áóëåâûõ ôóíêöèé (ÑÁÔ), äëÿ ðåàëèçàöèè êîòîðîé â áàçèñå ASIC öåëåñîîáðàçíî èñïîëüçîâàòü íàíîïðîãðàììèðóåìóþ ëî- ãè÷åñêóþ ìàòðèöó (íàíî-ÏËÌ) [11–13]. Â èçâåñòíûõ ïóáëèêàöèÿõ íå ðàññìàòðè- âàëèñü ìåòîäû ñèíòåçà ñõåì ÑÌÏÀ â áàçèñå íàíî-ÏËÌ. Â íàñòîÿùåé ñòàòüå ïðåäëàãàåòñÿ ìåòîä óìåíüøåíèÿ ïëîùàäè íàíî-ÏËÌ, îñíîâàííûé íà êîäèðîâà- íèè êëàññîâ ïñåâäîýêâèâàëåíòíûõ ñîñòîÿíèé (ÏÝÑ) àâòîìàòà Ìóðà [14]. Äëÿ ñïåöèôèêàöèè ÑÌÏÀ èñïîëüçóåòñÿ ÿçûê ãðàô-ñõåì àëãîðèòìà (ÃÑÀ) [8], êîòîðûé íàãëÿäíî èëëþñòðèðóåò ìåòîäû ñèíòåçà àâòîìàòîâ. ÕÀÐÀÊÒÅÐÈÑÒÈÊÈ ÎÑÎÁÅÍÍÎÑÒÅÉ ÑÌÏÀ È ÁÀÇÈÑÀ ÍÀÍÎ-ÏËÌ Äëÿ ñèíòåçà ñõåìû ÑÌÏÀ íåîáõîäèìî îòìåòèòü èñõîäíóþ ÃÑÀ � ñîñòîÿíèÿìè àâòîìàòà Ìóðà [8]. Ýòî ñâÿçàíî ñ òåì, ÷òî ÑÌÏÀ ãåíåðèðóåò äâà òèïà âûõîä- íûõ ñèãíàëîâ (ìèêðîîïåðàöèé). Ìèêðîîïåðàöèè àâòîìàòà Ìèëè èç ìíîæåñòâà ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 3 © À.À. Áàðêàëîâ, Ë.À. Òèòàðåíêî, À.Â. Áàåâ, À.Â. Ìàòâèåíêî, 2020 Y y yN� { }1 1, ,� ôîðìèðóþòñÿ íà ïå- ðåõîäàõ ìåæäó ñîñòîÿíèÿìè àâòîìàòà, êîòîðûå îáðàçóþò ìíîæåñòâî A a a M� { }1, ,� . Ìèêðîîïåðàöèè àâ- òîìàòà Ìóðà èç ìíîæåñòâà V N� { }� �1 2, ,� ôîðìèðóþòñÿ íà ïðîòÿæåíèè âñåãî òàêòà ðàáîòû ÑÌÏÀ. Òàêèì îáðàçîì, íàáîðû ìèê- ðîîïåðàöèé (ÍÌÎ) Y Yq � àññîöèèðó- þòñÿ ñ ïåðåõîäàìè ìåæäó ñîñòîÿíèÿìè àâòîìàòà, à ÍÌÎ V a Vm( ) � — ñ ñî- ñòîÿíèÿìè àâòîìàòà. Ïåðåõîäû ìåæäó ñîñòîÿíèÿìè çàâèñÿò îò âõîäíûõ ïåðå- ìåííûõ, êîòîðûìè ÿâëÿþòñÿ ëîãè÷åñêèå óñëîâèÿ (ËÓ) x X x xl L� � { }1, ,� . Â íà÷àëüíîì òàêòå ôóíêöèîíèðîâà- íèÿ àâòîìàò íàõîäèòñÿ â èñõîäíîì ñîñòîÿíèè a A1 � . Ïóñòü íåêîòîðûé àâòîìàò çàäàí ÃÑÀ �1 (ðèñ. 1). Àíàëèç ÃÑÀ �1 ïîçâîëÿåò íàéòè ñëåäóþùèå ìíîæåñòâà: A a� { 1,� , a8 }, Y y y y� { }1 2 3, , , V � { }� �1 10, ,� , X x x� { }1 4, ,� . Ýòî äàåò M � 8, N1 3� , N 2 10� è L � 4. Êðîìå òîãî, ìîæíî îïðåäåëèòü ÷èñëî ïåðåõîäîâ ìåæäó ñîñòîÿíèÿìè H � 16. Ñîñòîÿíèÿ a Am � ÿâëÿþòñÿ àáñòðàêòíûìè îáúåêòàìè. Äëÿ ñèíòåçà ñõåìû ÑÌÏÀ èõ íåîáõîäèìî çàêîäèðîâàòü äâîè÷íûìè êîäàìè ðàçðÿäíîñòè R. Â ñëó÷àå ðåàëèçàöèè àâòîìàòîâ íà ÏËÌ [13, 15] ïàðàìåòð R îïðåäåëÿåòñÿ êàê R M� � �log 2 . (1) Ôîðìóëà (1) ïðèìåíèìà è â áàçèñå íàíî-ÏËÌ [11]. Äëÿ êîäèðîâàíèÿ ñîñòîÿíèé èñïîëüçóþòñÿ âíóòðåííèå ïåðåìåííûå èç ìíî- æåñòâà T T TR� { }1, ,� . Êîäû K am( ) õðàíÿòñÿ â ðåãèñòðå RG , ñîñòîÿùåì èç D-òðèããåðîâ. Äëÿ çàïèñè êîäà â RG èñïîëüçóþòñÿ ôóíêöèè âîçáóæäåíèÿ ïàìÿòè (ÔÂÏ), îáðàçóþùèå ìíîæåñòâî � � { }D DR1, ,� . Çàìåíà ñîäåðæèìîãî RG èíè- öèèðóåòñÿ èìïóëüñîì ñèíõðîíèçàöèè Clock. Êàê ïðàâèëî, íà÷àëüíîå ñîñòîÿíèå a A1 � èìååò íóëåâîé êîä, êîòîðûé çàíîñèòñÿ â ðåãèñòð RG ïî ñèãíàëó Start. Â íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ óìåíüøèòü ïëîùàäü íàíî-ÏËÌ, çàêîäèðî- âàâ êëàññû ÏÝÑ. Îòìåòèì, ÷òî êàæäûé êëàññ ÏÝÑ àâòîìàòà Ìóðà ñîîòâåòñòâóåò îäíîìó ñîñòîÿíèþ ýêâèâàëåíòíîãî àâòîìàòà Ìèëè [14]. Åñëè ìíîæåñòâî ñîñòîÿ- íèé A ìîæåò áûòü ðàçáèòî íà I êëàññîâ ÏÝÑ B B Bi A I� � { }1, ,� , òî äëÿ èõ êî- äèðîâàíèÿ äîñòàòî÷íî RA ïåðåìåííûõ � � � �A RA � � { }1, ,� , ãäå R IA � � �log 2 . Ñîñòîÿíèÿ a a Bm s i, � , åñëè âûõîäû îòìå÷åííûõ èìè âåðøèí ñîåäèíåíû ñ âõîäîì îäíîé è òîé æå âåðøèíû ÃÑÀ � [4]. Èñïîëüçîâàâ ýòî îïðåäåëåíèå, ìîæíî íàéòè ñëåäóþùåå ðàçáèåíèå A äëÿ ÃÑÀ �1: A B B� { }1 4, ,� , ãäå B a1 1� { }, B a2 2� { }, B a a a3 3 4 5� { }, , è B a a a4 6 7 8� { }, , . Èòàê, èìååì I � 4, ÷òî îïðåäåëÿåò RA � 2 è � � �� { }1 2, . Èñïîëüçóÿ (1), èìååì R � 3 äëÿ T T T T� { }1 2 3, , è � � { }D D D1 2 3, , äëÿ ÑÌÏÀ çàäàííîãî ÃÑÀ �1. Íàíî-ÏËÌ ïðåäñòàâëÿåò ñîáîé ïîñëåäîâàòåëüíîå ñîåäèíåíèå ìàòðèö: êîíú- þíêòèâíîé M1 è äèçúþíêòèâíîé M 2 [11]. Äëÿ êàæäîé ìàòðèöû èñïîëüçóåòñÿ èäåÿ ðàñïðåäåëåííîé ëîãèêè [7], ò.å. îíà ïðåäñòàâëÿåòñÿ â âèäå ñîâîêóïíîñòè NV âåðòèêàëüíûõ è N H ãîðèçîíòàëüíûõ øèí. Íà ïåðåñå÷åíèè øèí íàõîäÿòñÿ ýëåìåí- òû ñ îäíîñòîðîííåé ïðîâîäèìîñòüþ. 4 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 Start End 1 a1 1 1 0 0 0 1 0 a4 x1 x2 y1y2 a2 y3 y1 a3 y1 a5 x3 a6 x4 a1 a7 a8 y2 y3 �1�4 �5�7 �3�9 �1�3 �5 �2�4 �8 �2�5 �2�6 �7�8 �10 Ðèñ. 1. Èñõîäíàÿ ÃÑÀ �1 Íà ðèñ. 2 ïîêàçàíà íàíî-ÏËÌ, ðåàëèçóþùàÿ ÑÁÔ y Yn � , çàâèñÿùèõ îò L áóëåâûõ ïåðåìåííûõ x X Y Nl � �(\| \| ). Ìàòðèöà M1 ðåàëèçóåò òåðìû Fh , îáðàçóþ- ùèå ìíîæåñòâî F F FH� { }1, ,� . Òåðìû çàâèñÿò êàê îò ïðÿìûõ, òàê è îò èíâåðñíûõ çíà÷åíèé x Xl � . Ïîýòîìó äëÿ M1 èìååì N LV � 2 , à äëÿ ìàòðèöû M 2 — N HV � è N NH � . Äëÿ ñðàâíåíèÿ ðàçëè÷íûõ âàðèàíòîâ ìàòðè÷íîé ðåàëèçàöèè ÑÁÔ ïðèíÿòî èñïîëüçîâàòü ïëîùàäè ìàòðèö, âûðàæåííûå â óñëîâíûõ åäèíèöàõ ïëîùàäè (ó.å.ï.) [8, 11]. Ïëîùàäü S M i( ) îïðåäåëÿåòñÿ ïðîèçâåäåíèåì N NV H . Äëÿ ñõå- ìû, èçîáðàæåííîé íà ðèñ. 2, èìååì S M L H( )1 2� , (2) S M H N( )2 � . (3) Ïëîùàäü ýòîé ñõåìû îïðåäåëÿåòñÿ ñóììîé âûðàæåíèé (2) è (3). Êàê ñëåäóåò èç ôîðìóë (2) è (3), äëÿ óìåíüøåíèÿ ïëîùàäè íåîáõîäèìî óìåíüøàòü ïàðàìåòðû L , N èëè H . Ïîýòîìó äëÿ îïòèìèçàöèè ìàòðè÷íîé ñõåìû ñëåäóåò âûïîëíÿòü ñîâìåñòíóþ ìèíèìèçàöèþ ÑÁÔ [9]. Îïòèìèçàöèÿ ïîäîáíîãî òèïà äîëæíà âûïîëíÿòüñÿ è äëÿ ÑÌÏÀ. ÒÐÈÂÈÀËÜÍÀß ÐÅÀËÈÇÀÖÈß ÑÌÏÀ Â ÁÀÇÈÑÅ ÍÀÍÎ-ÏËÌ Ïîñòðîèì ïðÿìóþ ñòðóêòóðíóþ òàáëèöó (ÏÑÒ) ÑÌÏÀ [10]. Êàæäàÿ ñòðîêà ÏÑÒ ñîîòâåòñòâóåò îäíîìó ïåðåõîäó ìåæäó ñîñòîÿíèÿìè àâòîìàòà è èìååò H ñòðîê. Íîìåð ñòðîêè èç ñòîëáöà h ñîîòâåòñòâóåò òåðìó Fh (h H�{ }1, ,� ), âõî- äÿùåìó â ÄÍÔ ôóíêöèé y Yn � è Dr �� [8]. Ýòà òàáëèöà èìååò ñëåäóþùèå ñòîëáöû [16, 17]: am — èñõîäíîå ñîñòîÿíèå, èç êîòîðîãî îñóùåñòâëÿåòñÿ ïå- ðåõîä; K am( ) — êîä ñîñòîÿíèÿ a Am � ; V a Vm( ) � — ÍÌÎ, ôîðìèðóåìûé â ñîñòîÿíèè a Am � ; as — ñîñòîÿíèå ïåðåõîäà; K as( ) — êîä ñîñòîÿíèÿ a As � ; X h — âõîäíîé ñèãíàë, îïðåäåëÿþùèé ïåðåõîä � �a am s, è ðàâíûé êîíú- þíêöèè íåêîòîðûõ ýëåìåíòîâ ìíîæåñòâà ËÓ èëè èõ îòðèöàíèé; Y Yh � — ÍÌÎ, ôîðìèðóåìûé íà ïåðåõîäå � �a am s, ; � �h � — íàáîð ÔÂÏ, ïðèíèìàþ- ùèõ åäèíè÷íîå çíà÷åíèå äëÿ çàìåíû ñîäåðæèìîãî RG, à èìåííî êîäà K am( ) êîäîì K as( ); h — íîìåð ïåðåõîäà, h H�{ }1, ,� . Êàæäàÿ ñòðîêà ÏÑÒ ñîîòâåòñòâóåò òåðìó F T Xh r R r l h mr� �1 ( , )h H�1 , (4) ãäå ïåðâûé ÷ëåí âûðàæåíèÿ ñîîòâåòñòâóåò êîíúþíêöèè Am , îïðåäåëÿåìîé êî- äîì ñîñòîÿíèÿ a Am � ; lmr �{ }0 1, — çíà÷åíèå r-ãî ðàçðÿäà T Tr r 0 � è T Tr r 1 � , r R�{ }1, ,� . Îòìåòèì, ÷òî äèçúþíêöèÿ âñåõ òåðìîâ (4) ñ îäèíàêîâûì ïåðâûì ÷ëåíîì Am äàåò êîíúþíêöèþ Am . Òàêèì îáðàçîì, åñëè êîíúþíêöèÿ Am âõî- äèò â ÄÍÔ ôóíêöèè � n V� , òî â ýòó ÄÍÔ äîëæíû âîéòè âñå òåðìû (4), ñîäåðæàùèå êîíúþíêöèþ Am . Òåðìû (4) âõîäÿò â ÄÍÔ ôóíêöèé y Yn � è Dr �� . Èñïîëüçóÿ ÏÑÒ, ìîæíî íàéòè ìíîæåñòâî F òåðìîâ (4) è ñëåäóþùèå ôóíêöèè: Y Y F� ( ), � �� ( )F , V V F� ( ) . (5) Ýòà ñèñòåìà îïðåäåëÿåò òðèâèàëüíóþ ñõåìó ÑÌÏÀ U 1 â áàçèñå íàíî-ÏËÌ (ðèñ. 3). ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 5 Start Clock RG X Y M1 F M2 1& V T Ðèñ. 3. Ñòðóêòóðíàÿ ñõåìà ÑÌÏÀ U1 � X Y M1 F M2 1& Ðèñ. 2. Ðåàëèçàöèÿ ÑÁÔ â áàçèñå íàíî-ÏËÌ Â ñõåìå íà ðèñ. 3 ìàòðèöà M1 ðåàëèçóåò ñèñòåìó òåðìîâ F è èìååò ïëîùàäü S M L R H( ) ( )1 2� � . (6) Ìàòðèöà M 2 ðåàëèçóåò ôóíêöèè (5) è èìååò ïëîùàäü S M R N N H( ) ( )2 1 2� � � . (7) Ðåçóëüòàò ñóììèðîâàíèÿ (6) è (7) äàåò ïëîùàäü S U( )1 ñõåìû ÑÌÏÀU 1: S U L R N N H( ) ( )1 2 3 1 2� � � � . (8) Èçâåñòíî [8], ÷òî òðèâèàëüíûå ìàòðè÷íûå ñõåìû àâòîìàòîâ çíà÷èòåëüíî èç- áûòî÷íû. Äëÿ óìåíüøåíèÿ ïëîùàäè, çàíèìàåìîé ñõåìîé àâòîìàòà, èñïîëüçóþò ðàçëè÷íûå ìåòîäû ñòðóêòóðíîé ðåäóêöèè [18, 19]. Â íàñòîÿùåé ñòàòüå ïðåäëàãà- åòñÿ îïòèìèçèðîâàòü ïëîùàäü, èñïîëüçóÿ êîäèðîâàíèå êëàññîâ ÏÝÑ, â ðåçóëüòà- òå ÷åãî áóäåò ïîëó÷åí ÑÌÏÀ U 2 , ñòðóêòóðà è ìåòîä ñèíòåçà êîòîðîãî ðàññìîòðåíû äàëåå. ÎÑÍÎÂÍÀß ÈÄÅß È ÌÅÒÎÄ ÑÈÍÒÅÇÀ ÑÌÏÀ U 2 Íàéäåì ðàçáèåíèå A IB B� { }1, ,� äëÿ íåêîòîðîé ÃÑÀ � j è âûïîëíèì êîäè- ðîâàíèå ñîñòîÿíèé äëÿ àâòîìàòà U j1 ( )� . Çäåñü çàïèñü U i j( )� îçíà÷àåò, ÷òî àâòîìàò ñî ñòðóêòóðîé U i ñèíòåçèðóåòñÿ ïî ÃÑÀ � j . Èñïîëüçîâàâ ÃÑÀ � j , ïîñòðîèì ñèñòåìó îáîáùåííûõ ôîðìóë ïåðåõîäîâ (ÎÔÏ) [20]. Íàïðèìåð, äëÿ ÃÑÀ �1 ìîæíî ïîñòðîèòü ñëåäóþùóþ ñèñòåìó ÎÔÏ: B x a x x a x x a1 1 2 1 2 3 1 2 4� � � ; B a2 5� ; (9) B x a x x a x x a3 3 6 3 4 7 3 4 8� � � ; B a4 1� . Êàê ñëåäóåò èç (9), â ëåâîé ÷àñòè êàæäîé ÎÔÏ âìåñòî ñîñòîÿíèé a Am � íà- õîäÿòñÿ êëàññû Bi A� , âêëþ÷àþùèå ýòè ñîñòîÿíèÿ. Èñïîëüçîâàâ ñèñòåìó ÎÔÏ, ïîñòðîèì ÏÑÒ àâòîìàòà U 2 ñî ñòîëáöàìè Bi , K Bi( ) , as, K as( ), X h , �h , h, â êîòîðîé Bi — êëàññ ÏÝÑ èç ëåâîé ÷àñòè ÎÔÏ, à K Bi( ) — åãî êîä. Òàáëèöà èìååò H 0 ñòðîê, êàæäàÿ èç êîòîðûõ ñîîòâåòñòâóåò îä- íîìó òåðìó ñèñòåìû ÎÔÏ. Åñëè äëÿ êëàññà Bi A� âûïîëíÿþòñÿ ïåðåõîäû â ñî- ñòîÿíèå ñ íóëåâûì êîäîì è íå ôîðìèðóþòñÿ ÍÌÎ Y Yh � , òî òàêèå ïåðåõîäû â ÏÑÒ íå âêëþ÷àþòñÿ. Òàêèì îáðàçîì, ÏÑÒ àâòîìàòà U 2 îïðåäåëÿåò ìíîæåñòâî òåðìîâ F0 , \| \|F H0 0� . Êàæäûé òåðì F Fh � 0 ñîîòâåòñòâóåò êîíúþíêöèè F Xh r R r l h A ir� �1 � ( , )h H�1 0 , (10) ãäå ïåðâûé ÷ëåí îïðåäåëÿåòñÿ êîäîì K Bi( ), lir �{ }0 1, — çíà÷åíèå r-ãî ðàçðÿ- äà K Bi( ). Ýòî êîíúþíêöèÿ ïåðåìåííûõ � �r � , ãäå � �r r 0 � è � �r r 1 � ( , )r RA�1 . Èç ÏÑÒU 2 ôîðìèðóþòñÿ ñèñòåìû ôóíêöèé Dr �� è y Yn � . Ñèñòåìà ôóíê- öèé � n V� ôîðìèðóåòñÿ ïî ÃÑÀ �1. Ïðè ýòîì ôóíêöèè èç ñèñòåì � è Y çàâèñÿò îò òåðìîâ (10), à ôóíêöèè � n V� — îò òåðìîâ Am . Ýòè òåðìû îáðàçóþò ñîîòâåòñòâåí- íî ìíîæåñòâà F0 , \| \|F H0 0� , è AV , \| \|A MV V� . Ñõåìà ÑÌÏÀ U 2 çàäàåòñÿ ñèñòå- ìàìè ôóíêöèé Y Y F� ( )0 , (11) � �� ( )F0 , (12) V V AV� ( ) . (13) Òåðìû (10) çàâèñÿò îò ïåðåìåííûõ � �r � . Â ñèëó çàâèñèìîñòè êëàññîâ Bi A� îò ñîñòîÿíèé [14] òåðìû ñèñòåìû � �� ( )A , òàêæå êàê è ôóíêöèè 6 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 � �� ( )AV , (14) çàâèñÿò îò A Am V� . Â ðåçóëüòàòå ïðîâåäåííîãî àíàëèçà ìîæíî ïðåäëîæèòü ñòðóêòóðíóþ ñõåìó ÑÌÏÀ U 2 (ðèñ. 4). Ýòà ñõåìà âêëþ÷àåò äâå íàíî-ÏËÌ, îá- ðàçîâàííûå ìàòðèöàìè Ì1, Ì 2 è Ì 3 , Ì 4 . Ïðè ýòîì ìàòðèöà Ì1 ôîðìèðóåò ñèñòåìó òåð- ìîâ (10), ìàòðèöà Ì 2 — ÑÁÔ (11) è (12), ìàò- ðèöà Ì 3 — òåðìû (4), à ìàòðèöà Ì 4 — ôóíê- öèè (13) è (14). Â íàñòîÿùåé ðàáîòå ïðåäëàãàåòñÿ òàêîé ìåòîä ñèíòåçà ñõåìû ÑÌÏÀ U 2 . 1. Îòìåòèòü èñõîäíóþ ãðàô-ñõåìó ñîñòîÿ- íèÿìè àâòîìàòà Ìóðà. 2. Íàéòè ðàçáèåíèå A IB B� { }1, ,� ìíîæåñòâà A . 3. Çàêîäèðîâàòü êëàññû Bi A� . 4. Çàêîäèðîâàòü ñîñòîÿíèÿ a Am � . 5. Ïîñòðîèòü ñèñòåìó ÎÔÏ è ÏÑÒ ÑÌÏÀ U 2 . 6. Ïîñòðîèòü òåðìû äëÿ AV è (10), à òàêæå ÑÁÔ (11)–(14). 7. Ïîñòðîèòü ñõåìó ÑÌÏÀ U 2 íà íàíî-ÏËÌ. ÏÐÈÌÅÐ ÑÈÍÒÅÇÀ ÑÕÅÌÛ ÑÌÏÀ U 2 Â ðàññìàòðèâàåìîì ïðèìåðå I � 4 , RA � 2 . Çàêîäèðóåì êëàññû Bi A� ñëåäó- þùèì îáðàçîì: ÷åì áîëüøå ñîñòîÿíèé âêëþ÷àåò êëàññ, òåì áîëüøå åäèíèö ñîäåðæèò åãî êîä. Èç àíàëèçà ðàçáèåíèÿ A ìîæíî ïîëó÷èòü òàêèå êîäû: K B( )1 10� , K B( )2 11� , K B( )3 00� , K B( )4 � 01. Êîäèðîâàíèå ñîñòîÿíèé a Am � íåîáõîäèìî âûïîëíèòü òàê, ÷òîáû ìèíèìè- çèðîâàòü âåëè÷èíó M AV V� \| \| . Ïîñòðîèì ñèñòåìû ôóíêöèé �( )A è V A( ) äëÿ ðàññìàòðèâàåìîãî ïðèìåðà: �1 2 3� �A A , � 2 4 6 7� � �A A A , � 3 3 5� �A A , � 4 2 4� �A A , � 5 2 3 6� � �A A A , � 6 7� A , (15) � 7 2 7� �A A , � 8 4 7� �A A , � 9 5� A , �10 8� A ; �1 1 2� �A A , �2 2 4� �A A . (16) Äëÿ ìèíèìèçàöèè ñèñòåì (15), (16) èñïîëüçóåì àëãîðèòì èç [21]. Êîäû ñîñòîÿíèé a Am � ïðèâåäå- íû íà ðèñ. 5. Ñèñòåìà ÎÔÏ (9) è êîäû (ñì. ðèñ. 5) ïîçâîëÿþò ïîñòðîèòü ÏÑÒ ÑÌÏÀ U 2 1( )� (òàáë. 1). Òàáëèöà èìååò H 0 7� ñòðîê, òàê êàê ïåðåõîäû ïðîèñõîäÿò èç ñîñòîÿíèé a Bm � 4 â ñîñòîÿíèå a A1 � ñ êîäîì K a( )1 000� . Èç òàáë. 1 ñëåäóåò, ÷òî F F F0 1 7� { }, ,� , ãäå F x1 1 2 1� � � , F x x F x x2 1 2 1 2 7 1 2 3 4� � �� , , . Òåðìû F Fh � 0 ôîðìèðóåò ìàòðèöà M1. Èç òàáë. 1 ìîæíî íàéòè ñëåäóþùèå ÑÁÔ, ðåàëèçóåìûå ìàòðèöåé M 2 òðèâè- àëüíûì îáðàçîì: y F F F1 1 4 5� � � , y F F2 1 7� � , y F F3 2 7� � ; D F F1 3 6� � �� , D F F F F2 1 2 4 6� � � � , D F F F F3 2 4 5 7� � � � . ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 7 Start Clock RG X Y M1 F M2 1& T M3 & M4 1 AV V Ðèñ. 4. Ñòðóêòóðíàÿ ñõåìà ÑÌÏÀ U2 � T1 00 01 11 10 0 1 a1 a8 a2 a4 a3 a6 a7 a5 T2 T3 Ðèñ. 5. Êîäû ñîñòîÿíèé ÑÌÏÀ U2 1( )� � Íàéäåì òåðìû ñèñòåì (13), (14), îáðàçóþùèå ìíîæåñòâî A F FV H� { }8 1, ,� . Íà÷íåì ñ F8 , ïîñêîëüêó ìíîæåñòâî F0 âêëþ÷àåò H 0 7� ýëåìåíòîâ. Èñïîëüçîâàâ êîäû èç ðèñ. 4 è çàêîíû àëãåáðû ëîãèêè [9], ïðåîáðàçóåì ñèñòåìû (15), (16) ñëå- äóþùèì îáðàçîì: �1 1 2 8� �T T F , � 2 1 3 1 2 9 10� � � �T T T T F F , � 3 2 3 11� �T T F , � 4 2 4 12 13� � � �A A F F , � 5 1 2 6 8 14� � � �T T A F F , � 6 7 15� �A F , � 7 2 3 16� �T T F , � 8 1 3 9� �T T F , � 9 5 17� �A F , �10 8 18� �A F ; �1 1 3 15� �T T F , � �2 2 4 4� � �A A . Ýòà ñèñòåìà èìååò MV �11 òåðìîâ, ðåàëèçóåìûõ íà ìàòðèöå M 3 . Ïðè ýòîì N 0 8� ôóíêöèé ïðåäñòàâëÿþòñÿ â âèäå îäíîãî òåðìà. Òàêèì îáðàçîì, ýòè âîñåìü ôóíêöèé ôîðìèðóþòñÿ íåïîñðåäñòâåííî ìàòðèöåé M 3 è îáðàçóþò ìíîæåñòâà V V1 � è � � 1 � . Ñëåäîâàòåëüíî, ìàòðèöà M 4 ôîðìèðóåò îñòàëüíûå ôóíêöèè èç ìíîæåñòâà V V V2 1� / è � � � 2 1� / . Â ðàññìàòðèâàåìîì ñëó÷àå V 1 1 3 6 10� { }� � � �, , , ,� , � � 1 1� { }, V 2 � �{� � �2 4 5, , }, � � 2 � { }2 . Â ñèëó ðàâåíñòâà � �2 4� ìàòðèöà M 4 ôîðìèðóåò N N R NA1 02 1 3� � � � � ôóíêöèè. Ïðè ýòîì òîëüêî MV1 6� òåðìîâ èç ìíîæåñò- âà A F F F F F FV0 9 10 12 13 8 14� { }, , , , , ÿâëÿþòñÿ âõîäàìè ìàòðèöû M 4 . Ñðàâíèì âàðèàíòû ðåàëèçàöèè ôóíêöèé V T( ) è �( )T â âèäå, ïîêàçàííîì íà ðèñ. 4 è ðèñ. 6 (äëÿ ðàññìàòðèâàåìîãî ïðèìåðà). Äëÿ ñõåìû íà ðèñ. 4 ïëîùàäè S M( )3 , S M( )4 îöåíèâàþòñÿ ñëåäóþùèì îáðàçîì: S M R M( )3 2 48� � � ó.å.ï., (17) S M M N RA( ) ( )4 2 96� � � � ó.å.ï. (18) Äëÿ ñõåìû íà ðèñ. 6 èìååì äëÿ ðàññìàòðèâàå- ìîãî ïðèìåðà S M R MV( )3 2 6 11 66� � � � � ó.å.ï., (19) S M M NV( )4 11 6 3 18� � � � � ó.å.ï. (20) Ñóììèðîâàíèå (17) è (18) äàåò 144 ó.å.ï., à ñóì- ìèðîâàíèå (19) è (20) äàåò 84 ó.å.ï. Âòîðîé âàðèàíò ïî ñðàâíåíèþ ñ ïåðâûì äàåò âûèãðûø â 1.71 ðàçà. Òàêîé ýôôåêò äîñòèãíóò, áëàãîäàðÿ èñïîëüçîâàíèþ ìåòîäà [21] äëÿ êîäèðîâàíèÿ a Am � . 8 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 Ò à á ë è ö à 1. Ïðÿìàÿ ñòðóêòóðíàÿ òàáëèöà àâòîìàòà U 2 1( )� Bi K Bi( ) as K as( ) Xh Yh Ôh h B1 10 a2 010 x1 y y1 2 D2 1 a3 011 x x1 2 y3 D D2 3 2 a4 100 x x1 2 — D1 3 B2 11 a5 111 1 y1 D D D1 2 3 4 B3 00 a6 101 x3 y1 D D1 3 5 a7 110 x x3 4 — D D1 2 6 a8 001 x x3 4 y y2 3 D3 7 M3 & T M4 1 AV V 1 V 2 0 Ðèñ. 6. Ðåàëèçàöèÿ ôóíêöèé V T( ) è �( )T ñ ó÷åòîì îïòèìèçàöèè � 1 � 2 Ïîñëåäíèé ýòàï ïðåäëîæåííîãî ìåòîäà âûïîëíÿåòñÿ òðèâèàëüíûì îáðàçîì. Îòìåòèì, ÷òî ôèçè÷åñêàÿ ðåàëèçàöèÿ ñõåìû íàíî-ÏËÌ ñâÿçàíà ñ èçãîòîâëåíèåì ëèòîãðàôè÷åñêèõ ìàñîê è äðóãèìè ñëîæíûìè òåõíîëîãè÷åñêèìè ïðîöåññàìè [6]. ÀÍÀËÈÇ ÝÔÔÅÊÒÈÂÍÎÑÒÈ ÏÐÅÄËÎÆÅÍÍÎÃÎ ÌÅÒÎÄÀ Óñëîâèìñÿ ïîíèìàòü ïîä ýôôåêòèâíîñòüþ ìåòîäà îòíîøåíèå ïëîùàäè íåêîòî- ðîé áàçîâîé ñõåìû ê ïëîùàäè ñõåìû, ïîëó÷åííîé â ðåçóëüòàòå ïðèìåíåíèÿ ïðåäëîæåííîãî ìåòîäà. Ïëîùàäü S U( )1 îïðåäåëåíà â (8). Íàéäåì ïîäîáíîå âûðàæåíèå äëÿ S U( )2 . Ïëîùàäè ìàòðèöû àâòîìàòà U 2 îïðåäåëÿþòñÿ ïî ôîðìóëàì: S M L R HA( ) ( )1 02� � , (21) S M H N R( ) ( )2 0 1� � , (22) S M M R M M NV V( , )3 4 12 1 � � . (23) Ðàâåíñòâî (23) íàéäåíî êàê ñóììà ðàâåíñòâ (19) è (20). Åñëè M M MV V� � 1 è N N RA1 2� � , òî ðàâåíñòâà (19), (20) ïðåâðàùàþòñÿ â (17), (18) ñîîòâåòñòâåííî. Ðåçóëüòàò ñóììèðîâàíèÿ (21)–(23) äàåò ïëîùàäü S U( )2 . Äëÿ U 1 1( )� ÷èñëî òåðìîâ (4) H �16 . Èñïîëüçîâàâ ïàðàìåòðû L � 4 , R � 3 , N1 3� , N 2 10� , íàéäåì S U( )1 480� ó.å.ï. Äëÿ U 2 1( )� èìååì S M( )1 � � � � � �2 2 4 7 84( ) , S M( ) ( )2 7 3 3 42� � � � , S M S M( ) ( )3 4 84� � . Ýòî äàåò S U( )2 210� . Îòíîøåíèå S U S U( ) / ( )1 2 � 2.28, ò.å. ïðåäëîæåííûé ìåòîä ïîçâîëÿ- åò íà 57 % óìåíüøèòü ïëîùàäü ìàòðè÷íîé ñõåìû ÑÌÏÀ. Åñòåñòâåííî, òàêàÿ ýôôåêòèâíîñòü ïîëó÷åíà òîëüêî äëÿ ðàññìàòðèâàåìîãî ïðèìåðà. Äëÿ îáùåãî ñëó÷àÿ íåîáõîäèìî èññëåäîâàòü íåêîòîðóþ ñîâîêóïíîñòü ñòàíäàðòíûõ ïðèìåðîâ (benchmarks) ñ ïîìîùüþ áèáëèîòåêè [22], ñîáðàííîé â 90-õ ãîäàõ XX âåêà. Âî ìíîãèõ ðàáîòàõ, îïèñûâàþùèõ ñõåìû àâòîìàòîâ, èìåí- íî ýòà áèáëèîòåêà èñïîëüçóåòñÿ äëÿ ñðàâíåíèÿ ðàçëè÷íûõ ìåòîäîâ ñèíòåçà. Êàê ïîêàçàëè ïðîâåäåííûå èññëåäîâàíèÿ, ïðåäëîæåííûé ìåòîä âñåãäà äàâàë ëó÷øèå ðåçóëüòàòû, ÷åì ìåòîäU 1. Âûèãðûø îò ïðèìåíåíèÿ ìîäåëèU 2 óâåëè÷è- âàëñÿ ïî ìåðå ðîñòà oòíîøåíèÿ ÷èñëà êîäèðóþùèõ ïåðåìåííûõ R RA/ è îòíîøå- íèÿ ÷èñëà ñòðîê ÏÑÒ H H/ 0 . Ïðè ýòîì âòîðîé ôàêòîð èìåë á�ëüøåå âëèÿíèå. Êðîìå òîãî, óìåíüøåíèå ïëîùàäè S M M( , )3 4 çàâèñèò îò òîãî, êàêàÿ ÷àñòü ôóíê- öèé � n V� è � �r � ïðåäñòàâëÿåòñÿ â âèäå îäíîãî òåðìà (êîíúþíêöèè âíóòðåííèõ ïåðåìåííûõ T Tr � ). Â ïðåäåëüíîì ñëó÷àå ìàòðèöà M 3 ãåíåðèðóåò âñå ôóíêöèè èç ìíîæåñòâà V � �, à ìàòðèöà M 4 èìååò íóëåâóþ ïëîùàäü. Îòìåòèì, ÷òî äëÿ ïðèìåðîâ èç [22] òàêàÿ ñèòóàöèÿ íå âîçíèêàëà. Ïåðåõîä îòU 1 êU 2 ïîçâîëèë â ñðåäíåì óìåíüøèòü ïëîùàäü ñõåìû íà 26 %, â äàííîì ñëó÷àå ìàêñèìàëüíûé âûèãðûø äîñòèãàë 42 %, à ìèíèìàëüíûé — 11.5 %. Îòìåòèì, ÷òî òåîðåòè÷åñêè âûèãðûø íåâîçìîæåí, åñëè I M� . Ïðè ýòîì êàæäûé êëàññ Bi A� âêëþ÷àåò òîëüêî îäèí ýëåìåíò. Äëÿ ñòàíäàðòíûõ ïðèìå- ðîâ èç [22] òàêàÿ ñèòóàöèÿ òàêæå íå âîçíèêàëà. ÇÀÊËÞ×ÅÍÈÅ Óìåíüøåíèå ïëîùàäè êðèñòàëëà ASIC, çàíèìàåìîé ñõåìîé óñòðîéñòâà óïðàâëå- íèÿ, ïîçâîëÿåò ñíèçèòü ïîòðåáëÿåìóþ ìîùíîñòü, óâåëè÷èòü áûñòðîäåéñòâèå è ïîâûñèòü íàäåæíîñòü ñõåìû [9]. Ïðåäëîæåííûé â ðàáîòå ìåòîä îðèåíòèðîâàí íà ðåøåíèå ýòîé çàäà÷è äëÿ ÑÌÏÀ. Ïîñêîëüêó ñõåìà ÑÌÏÀ çàäàåòñÿ ñèñòå- ìàìè áóëåâûõ ôóíêöèé, äëÿ åå ðåàëèçàöèè âûáðàí áàçèñ íàíî-ÏËÌ. Ïðåäëàãàåìûé ìåòîä îñíîâàí íà êîäèðîâàíèè êëàññîâ ÏÝÑ àâòîìàòà Ìóðà. Èìåííî ñîñòîÿíèÿìè àâòîìàòà Ìóðà îòìå÷åíà ÃÑÀ, çàäàþùàÿ çàêîí ôóíêöèîíèðîâà- íèÿ ÑÌÏÀ. Ïðè ýòîì ïðîèñõîäèò ïåðåõîä îò äâóõóðîâíåâîé ñõåìû U 1 (ñì. ðèñ. 3) ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 9 ê ÷åòûðåõóðîâíåâîé ñõåìå U 2 (ñì. ðèñ. 4). Êîäèðîâàíèå êëàññîâ ÏÝÑ âûïîëíÿ- åòñÿ äîïîëíèòåëüíûìè ïåðåìåííûìè, êîòîðûå íåîáõîäèìî ãåíåðèðîâàòü êàê âû- õîäû îäíîé èç ìàòðèö. Äëÿ îïòèìèçàöèè ñõåìû, ôîðìèðóþùåé ìèêðîîïåðàöèè àâòîìàòà Ìóðà è äîïîëíèòåëüíûå ïåðåìåííûå, èñïîëüçóåòñÿ ìåòîä êîäèðîâàíèÿ ñîñòîÿíèé, îñíîâàííûé íà ïîäõîäå [21]. Â ïðåäåëüíîì ñëó÷àå ýòè ìèêðîîïåðàöèè è äîïîë- íèòåëüíûå ïåðåìåííûå ôîðìèðóþòñÿ íà òðåòüåì óðîâíå ñõåìû, ÷òî ïîçâîëÿåò óâåëè÷èòü áûñòðîäåéñòâèå. Èññëåäîâàíèÿ ñ èñïîëüçîâàíèåì áèáëèîòåêè [22] ïîêàçàëè âûñîêóþ ýôôåê- òèâíîñòü ïðåäëîæåííîãî ìåòîäà. Â ñðåäíåì ïëîùàäü ñõåì àâòîìàòîâ U 2 óìåíü- øàåòñÿ äî 0.76 ïëîùàäè àâòîìàòîâ U 1. Îñíîâûâàÿñü íà ðåçóëüòàòàõ [5, 7, 11], ìîæíî îæèäàòü, ÷òî ñíèçèòñÿ è ïîòðåáëÿåìàÿ ìîùíîñòü. Óâåëè÷åíèå ÷èñëà óðîâíåé â ñõåìå U 2 (îòíîñèòåëüíî U 1) ñâèäåòåëüñòâóåò, ÷òî ïðåäëîæåííûé ìåòîä îòíîñèòñÿ ê ãðóïïå ìåòîäîâ ñòðóêòóðíîé äåêîìïîçè- öèè [19], â êîòîðóþ âõîäÿò ìåòîäû çàìåíû ëîãè÷åñêèõ óñëîâèé, êîäèðîâàíèÿ ïî- ëåé ñîâìåñòèìûõ ìèêðîîïåðàöèé, êîäèðîâàíèÿ òåðìîâ ÏÑÒ è äð. [23, 24]. Â äàëüíåéøèõ èññëåäîâàíèÿõ ïëàíèðóåòñÿ ïðèìåíèòü ýòè ïîäõîäû äëÿ îïòèìè- çàöèè ñõåì ÑÌÏÀ â áàçèñå ASIC, PLD [25] è â íåéðîííûõ ñåòÿõ [26]. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Barkalov A., Titarenko L., Mazurkiewicz M. Foundations of embedded systems. Berlin: Springer, 2019. 167 p. 2. Marwedel P. Embedded system design: Embedded systems, foundations of cyber-physical systems and the Internet of Things. Berlin: Springer, 2017. 612 p. 3. Gajski D.D., Abdi S., Gerstlauer A., Schirner G. Embedded system design: Modeling, synthesis and verification. New York: Springer, 2009. 352 p. 4. Baranov S. Logic and system design of digital systems. Tallin: TUT Press, 2008. 267 p. 5. Czerwinski R., Kania D. Finite state machines logic synthesis for complex programmable logic devices. Lecture Notes in Electrical Engineering. Vol. 231. Berlin; Heidelberg: Springer-Verlag, 2013. 172 p. 6. Smith M. Application specific integrated circuits. Boston: Addison-Wesley, 1997. 632 p. 7. Nababi Z. Embedded core design with FPGAs. New York: McGraw-Hill, 2008. 418 p. 8. Baranov S. Logic synthesis for control automata. Dordrecht: Kluwer Academic Publishers, 1994. 312 p. 9. DeMicheli G. Synthesis and optimization of digital circuits. New York: McGraw-Hill, 1994. 634 p. 10. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Âèçîð ß.Å., Ìàòâèåíêî À.Â., Ãîðèíà Â.Â. Óìåíüøåíèå ÷èñëà LUT ýëåìåíòîâ â ñõåìå ñîâìåùåííîãî àâòîìàòà. Óïðàâëÿþùèå ñèñòåìû è ìàøèíû. 2016. ¹ 3. Ñ. 16–22. 11. Baranov S., Levin L., Keren O., Karpovsky M. Designing fault tolerant FSM by nano-PLA. Proc. of 15th International On-Line Testing Symposium. Lisbon, 2009. P. 216–220. 12. Naemi H., DeHon A. A greedy algorithm for toleranting crosspoints in NanoPLA design. Proc. of IEEE International Competence on Field-Programmable Technology. Piscataway, NJ, 2004. P. 49–56. 13. Áàðàíîâ Ñ.È., Ñêëÿðîâ Â.À. Öèôðîâûå óñòðîéñòâà íà ïðîãðàììèðóåìûõ ÁÈÑ ñ ìàòðè÷íîé ñòðóêòóðîé. Ìîñêâà: Ðàäèî è ñâÿçü, 1986. 272 ñ. 14. Áàðêàëîâ À.À. Ïðèíöèïû îïòèìèçàöèè ëîãè÷åñêîé ñõåìû ìèêðîïðîãðàììíîãî àâòîìàòà Ìóðà. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 1998. ¹ 1. Ñ. 65–72. 15. Ñîëîâüåâ Â.Â. Ïðîåêòèðîâàíèå öèôðîâûõ ñõåì íà îñíîâå ïðîãðàììèðóåìûõ ëîãè÷åñêèõ èí- òåãðàëüíûõ ñõåì. Ìîñêâà: Ãîðÿ÷àÿ ëèíèÿ — ÒÅËÅÊÎÌ, 2001. 636 ñ. 16. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Âèçîð ß.Å., Ìàòâèåíêî À.Â. Ñèíòåç ñîâìåùåííîãî ìèêðîïðîã- ðàììíîãî àâòîìàòà â áàçèñå FPGA. Êîìï’þòåðíi çàñîáè, ìåðåæi òà ñèñòåìè. Êè¿â: ²í-ò ê³áåð- íåòèêè ³ì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðà¿íè, 2015. Âèï. 14. Ñ. 32–39. 17. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Âèçîð ß.Å., Ìàòâèåíêî À.Â. Ðåàëèçàöèÿ ñõåìû ñîâìåùåííîãî ìèêðîïðîãðàììíîãî àâòîìàòà â áàçèñå FPGA. Ïðîáëåìè ³íôîðìàòèçàö³¿ òà óïðàâë³ííÿ. Êè¿â: Íàö³îíàëüíèé àâ³àö³éíèé óí³âåðñèòåò, 2015. Âèï. 3(51). Ñ 5–13. 18. Áàðêàëîâ À.À. Ñòðóêòóðû ìíîãîóðîâíåâûõ ñõåì ìèêðîïðîãðàììíûõ àâòîìàòîâ íà ïðîãðàì- ìèðóåìûõ ëîãè÷åñêèõ ìàòðèöàõ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 1994. ¹ 4. Ñ. 22–29. 19. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Áàðêàëîâ À.À. (ìë.). Ñòðóêòóðíàÿ äåêîìïîçèöèÿ êàê ñðåäñòâî îïòèìèçà- öèè ñõåìû àâòîìàòà Ìèëè íà ÏËÈÑ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2012. ¹ 2. Ñ. 177–187. 10 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 20. Barkalov A., Titarenko L., Kolopenczyk M., Mielcarek K., Bazydlo G. Logic synthesis for FPGA-based finite state machines. Berlin: Springer, 2016. 280 p. 21. À÷àñîâà Ñ.Ì. Àëãîðèòìû ñèíòåçà àâòîìàòîâ íà ïðîãðàììèðóåìûõ ëîãè÷åñêèõ ìàòðèöàõ. Ìîñ- êâà: Ñîâ. ðàäèî, 1987. 132 ñ. 22. Yang S. Logic synthesis and optimization benchmarks user guide. Version 3.0. Microelectronics Center of North Carolina, 1991. 43 p. 23. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Öîëîëî Ñ.À. Îïòèìèçàöèÿ ñõåìû àâòîìàòà Ìóðà, ðåàëèçóå- ìîé â áàçèñå ÏËÈÑ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2009. ¹ 5. Ñ. 180–186. 24. Áàðêàëîâ À.À., Òèòàðåíêî Ë.À., Ëàâðèê À.Ñ. Óìåíüøåíèå àïïàðàòóðíûõ çàòðàò â óñòðîéñòâå óïðàâëåíèÿ ñ ðàçäåëåíèåì êîäîâ. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2013. ¹ 3. Ñ. 113–123. 25. Palagin A.V., Opanasenko V.N. 3 Design and application of the PLD-based reconfigurable devices. In: Design of Digital Systems and Devices. Lecture Notes in Electrical Engineering. Adamski M., Barkalov A., Wegrzyn M. (Eds.). Berlin; Heidelberg: Springer, 2011. Vol 79. P. 59–91. 26. Opanasenko V.N., Kryvyi S.L. Synthesis of neural-like networks on the basis of conversion of cyclic hamming codes. Cybernetics and Systems Analysis. 2017. Vol. 53, N 4. P. 627–635. https:// doi.org/10.1007/s10559-017-9965-z. Íàä³éøëà äî ðåäàêö³¿ 17.01.2020 Î.Î. Áàðêàëîâ, Ë.Î. Ò³òàðåíêî, À.Â. Áàºâ, Î.Â. Ìàòâ³ºíêî ÎÏÒÈÌ²ÇÀÖ²ß ÑÕÅÌÈ ÑÓÌ²ÙÅÍÎÃÎ ÀÂÒÎÌÀÒÀ Â ÁÀÇÈÑ² ASIC Àíîòàö³ÿ. Çàïðîïîíîâàíî ìåòîä çìåíøåííÿ ïëîù³ êðèñòàëà, ÿêó çàéìàº ñõå- ìà ñóì³ùåíîãî àâòîìàòà. Ìåòîä áàçóºòüñÿ íà êîäóâàíí³ êëàñ³â ïñåâäîåêâ³âà- ëåíòíèõ ñòàí³â àâòîìàòà Ìóðà äîäàòêîâèìè çì³ííèìè. Öåé ï³äõ³ä ïîðîäæóº ÷îòèðèð³âíåâó ñõåìó, ÿêà ðåàë³çóºòüñÿ ó âèãëÿä³ äâîõ íàíî-ÏËÌ, ³ äàº çìî- ãó çìåíøèòè ïëîùó íàíî-ÏËÌ, ÿêà ôîðìóº ì³êðîîïåðàö³¿ àâòîìàòà Ìóðà òà äîäàòêîâ³ çì³íí³. Ðîçãëÿíóòî ïðèêëàä ñèíòåçó ñõåìè ³ç çàñòîñóâàííÿì çàïðî- ïîíîâàíîãî ìåòîäó. Íàâåäåíî ðåçóëüòàòè äîñë³äæåíü åôåêòèâíîñò³ ìåòîäó ç âèêîðèñòàííÿì á³áë³îòåêè ñòàíäàðòíèõ òåñòîâèõ àâòîìàò³â. Êëþ÷îâ³ ñëîâà: ñóì³ùåíèé ì³êðîïðîãðàìíèé àâòîìàò, ñèíòåç, íàíî-ÏËÌ, ASIC, ïñåâäîåêâ³âàëåíòí³ ñòàíè. A.A. Barkalov, L.A. Titarenko, A.V. Baiev, A.V. Matviienko OPTIMIZING THE SCHEME OF A COMBINED AUTOMATON IN THE ASIC BASIS Abstract. A method is proposed for decreasing the area of the ASIC occupied by the scheme of a combined automaton. The method is based on encoding of the classes of pseudoequivalent states of Moore automaton by additional variables. This approach leads to a four-level scheme implemented as two nano-PLAs and decreases the area of nano-PLA generating microoperations of the Moore automaton and additional variables. An example of synthesis with the use of the proposed scheme is considered. The results of the efficiency analysis of the proposed method with the use of a library of benchmarks are presented. Keywords: combined microprogrammed automaton, synthesis, nano-PLA, ASIC, pseudo-equivalent states. Áàðêàëîâ Àëåêñàíäð Àëåêñàíäðîâè÷, äîêòîð òåõí. íàóê, ïðîôåññîð Óíèâåðñèòåòà Çåëåíîãóðñêîãî (Ïîëüøà), ïðîôåññîð Äîíåöêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Âàñèëèÿ Ñòóñà, Âèííèöà, e-mail: A.Barkalov@iie.uz.zgora.pl. Òèòàðåíêî Ëàðèñà Àëåêñàíäðîâíà, äîêòîð òåõí. íàóê, ïðîôåññîð Óíèâåðñèòåòà Çåëåíîãóðñêîãî (Ïîëüøà), ïðîôåññîð Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà ðàäèîýëåêòðîíèêè, e-mail: L.Titarenko@iie.uz.zgora.pl. Áàåâ Àðòåì Âèêòîðîâè÷, êàíäèäàò ôèç.-ìàò. íàóê, äåêàí Äîíåöêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èìåíè Âàñèëèÿ Ñòóñà, Âèííèöà; ðóêîâîäèòåëü íàïðàâëåíèÿ ïî èñêóññòâåííîìó èíòåëëåêòó, ôèðìà Peoly, Âèííèöà, e-mail: a.baev@donnu.edu.ua. Ìàòâèåíêî Àëåêñàíäð Âëàäèìèðîâè÷, íàó÷íûé ñîòðóäíèê Èíñòèòóòà êèáåðíåòèêè èì. Â.Ì. Ãëóøêîâà ÍÀÍ Óêðàèíû, Êèåâ, e-mail: avmatv@ukr.net. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2020, òîì 56, ¹ 6 11

Оптимизация схемы совмещенного автомата в базисе ASIC

Institution

Ähnliche Einträge