Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.

Розглядається один із можливих підходів до вирішення на базі принципу мікропрограмного керування проблеми комплексної – від постановки задачі до отримання ескізу друкованої плати – автоматизації процесу розробки операційних пристроїв. Підхід демонструється на прикладі синтезу в діалоговій трансформа...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Control systems & computers
Datum:	2020
1. Verfasser:	Петрушенко, А.М.
Format:	Artikel
Sprache:	Ukrainisch
Veröffentlicht:	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України 2020
Schlagworte:	Fundamental Problems in Computer Science
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/181114
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:	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв. І / А. М. Петрушенко // Control systems & computers. — 2020. — № 1. — С. 3-22. — Бібліогр.: 26 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859681801098756096
author	Петрушенко, А.М.
author_facet	Петрушенко, А.М.
citation_txt	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв. І / А. М. Петрушенко // Control systems & computers. — 2020. — № 1. — С. 3-22. — Бібліогр.: 26 назв. — укр.
collection	DSpace DC
container_title	Control systems & computers
description	Розглядається один із можливих підходів до вирішення на базі принципу мікропрограмного керування проблеми комплексної – від постановки задачі до отримання ескізу друкованої плати – автоматизації процесу розробки операційних пристроїв. Підхід демонструється на прикладі синтезу в діалоговій трансформаційній машині – інструментарію алгебро-граматичних методів подання знань у різноманітних предметних областях – керуючого автомату операційного пристрою, що реалізує операцію додавання. Цель данной статьи — демонстрация одного из возможных подходов к реализации инструментария, воплощающего модель математизации В.М. Глушкова и возможностей данного инструментария на примере синтеза операционных устройств. Методы. При реализации инструментария и алгоритма синтеза операционных устройств использовался алгебро-грамматический метод представления знаний, метод построения операционных устройств на базе принципа микропрограммного управления, методы абстрактной и структурной теории автоматов, методы алгебры алгоритмов и т.д. Результат. Разработан инструментарий, воплощающий модель математизации В.М. Глушкова, позволяющий осуществить комплексную автоматизацию проектирования операционных устройств. The purpose is to demonstrate the inextricable link between the fundamental concepts of the general theory of computer systems design and practical methods of designing software and hardware of computer technology, as well as new technological capabilities that arise when using the apparatus of algebra of algorithms in the process of designing programmes and equipment using an interactive transformational machine. Methods. When implementing the tools (conversational transformation machine) and the synthesis algorithm of operating devices, we used the algebraic-grammatical method of representing knowledge, the method of constructing operating devices based on the principle of microprogram control, the methods of abstract and structural theory of automata, the methods of algebra of algorithms, etc. Results. Synthesis methods for operating devices developed for the language of graph diagrams of algorithms and the language of logical diagrams of algorithms are extended to the language CAA\D – the input language of the dialogue transformation machine. Based on the dialogue transformational machine, a toolkit has been developed that embodies the V.M.Glushkov mathematical model and allows the complex automation of the operating devices: from setting the task to obtaining a sketch of the printed circuit board
first_indexed	2025-11-30T17:51:41Z
format	Article
fulltext	Fundamental Problems in Computer Science ISSN 2706-8145, Control systems and computers, 2020, № 1 3 DOI https://doi.org/10.15407/usim.2020.01.003 УДК 681.3.006 А.М. ПЕТРУШЕНКО, канд. фіз.-мат. наук, доцент, Київський національний університет імені Тараса Шевченка, 03022, м. Київ, просп. Академіка Глушкова, 4Д, факультет комп’ютерних наук та кібернетики, anatoly@mytaskhelper.com ПРИНЦИП МІКРОПРОГРАМНОГО КЕРУВАННЯ ТА АВТОМАТИЗАЦІЯ ПРОЕКТУВАННЯ ОПЕРАЦІЙНИХ ПРИСТРОЇВ. I Розглядається один із можливих підходів до вирішення на базі принципу мікропрограмного керування проблеми комплекс- ної – від постановки задачі до отримання ескізу друкованої плати – автоматизації процесу розробки операційних пристроїв. Підхід демонструється на прикладі синтезу в діалоговій трансформаційній машині – інструментаріїю алгебро-граматичних методів подання знань у різноманітних предметних областях – керуючого автомату операцій- ного пристрою, що реалізує операцію додавання. Ключові слова: принцип мікропрограмного керування, дискретний перетворювач інформації, операційний пристрій, алгебра алгоритмів, алгебро-граматичний метод подання знань, діалогова трансформаційна машина. Вступ Робота виконана в рамках досліджень зі ство- рення так званих трансформаційних методів синтезу знань у довільних предметних областях, що займають проміжне становище між кла- сичними індуктивними і дедуктивними мето- дами синтезу [1–9]. Загальна ідея трансфор- маційного синтезу [5] може бути формалізо- вана, зокрема, в алгебро-граматичній моделі, що отримала назву граматик структурного проектування [6]. В основі цієї моделі лежать запропоновані В.М. Глушковим поняття дис- кретного перетворювача інформації та систе- ми мікропрограмних (алгоритмічних) алгебр [1–7] — ефективного математичного апара- ту для моделювання систем будь-якої приро- ди, поведінка яких може бути описана алго- ритмічно; проте, до основних застосувань цього апарату належать теорія проектування комп’ютерів і теоретичне програмування. Діалогова трансформаційна машина (ДТМ) [10–15] може розглядатися як інструментальна підтримка проектування алгоритмів й асоційо- ваних з ними програм і апаратури у названій моделі. Початок робіт зі створення ДТМ покла- дено в [10, 11], де було запропоновано архітек- туру і програмно реалізовану компоненту ДТМ, призначену для автоматизації аналітичних пе- ретворень алгоритмів і асоційованих з ними програм. В [12–15] описується реалізація ряду нових функцій ДТМ, орієнтованих, головним чином, на динамічне (діалогове) конструюван- ня алгоритмів обробки знань в довільних пред- метних областях. У роботі основна увага при- діляється використанню цього інструментарію для автоматизації процесу проектування на- більш інтелектуальної частини комп’ютерів — операційних пристроїв (ОП), до класу яких відносяться процесори, пристроїв керування зовнішніми пристроями, канали введення/ви- ведення тощо. А.М. Петрушенко 4 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 Основна задача проектування операційних пристроїв, проблеми та методи їх подолання Основна задача проектування операційних прис- троїв. В процесі системного проектування комп’ютера (який спочатку розглядається як одне ціле) на певному етапі здійснюється його декомпозиція на підсистеми, внаслідок чього виокремлюються: номенклатура пристроїв, зокрема ОП, з яких складається комп’ютер; спосіб сполучення пристроїв (інтерфейси); вимоги до швидкодії пристроїв. При цьому для кожного ОП стає відомим: перелік входів D = {d 1 , ..., d H } і виходів R = ={r 1 , ..., r Q }, зумовлений складом інтерфейсів; набір операцій F = {f 1 , ..., f G }, реаліза- ція яких покладається на ОП; вимога до швидкодії ОП. З урахуванням сказаного основна задача проектування ОП формулюється так [16–19]: задано головну функцію ОП, яка визначається множинами D, R, F і полягає у виконанні зада- ної множини F операцій над вхідними словами із D з метою обчислення результатів операцій — слів із R, а також вимоги до швидкодії ОП. По- трібно синтезувати схему ОП, яка забезпечу- вала б реалізацію заданої головної функції із заданою швидкодією і була б мінімальною за кількістю використаного устаткування (як правило, остання вимога спричиняє також зменшення вартості виробу, збільшення його надійності тощо.). Очевидно, основна задача проектування ОП потребує подальшого уточнення. Принцип мікропрограмного керування. У будь- якому (алгоритмічно універсальному) ком- п’ютері всі операції реалізуються за допомо- гою апаратних і програмних засобів. Апаратні засоби можна умовно розділити на три основ- ні частини: процесор, пам’ять і периферія. У процесорі також виділяються дві складові частини: пристрій керування і арифметично- логічний пристрій (АЛП). Пристрій керуван- ня розшифровує команди формування послі- довності керуючих сигналів, які включають у роботу окремі вузли процесора з метою вико- нання дій, вказаних у команді. АЛП призначе- ний для виконання операцій над інформа- цією (даними), що розглядається як складне просторово-часове перетворення машинних слів. Таке перетворення може бути описано як мікроалгоритм, що являє собою деяку послі- довність елементарних машинних дій — їх називають мікроопераціями (МО) — над сло- вами інформації і логічних умов (ЛУ), які ке- рують порядком слідування цих МО. Процедура визначення структури (архітек- тури) ОП і порядку його функціонування, що реалізує головну функцію ОП, базується на принципі мікропрограмного керування, який, з урахуванням сказаного вище, можна описати в такий спосіб [16–19]: будь-яка операція f g ∈F розглядається як складна дія, розділена на ряд МО; порядок виконання МО визначається ЛУ, які, в залежності від значень слів інформації, приймають значення "істина" або "хибність" (1 чи 0); процедура виконання будь-якої операцій f g ∈F в ОП описується у формі мікроалгоритму, який називають мікропрограмою (МПР); МПР є, крім усього іншого, формою подан- ня функції ОП. Ця функція слугує для визна- чення структури ОП і порядку його функціону- вання в часі (див. далі). Концепція керуючого та операційного блоків. За аналогією з процесором, у структурі ОП зручно виділяти — як у структурному, так і у функціональному відношенні — дві складові частини: операційний блок (ОБ) і керуючий блок (КБ), які взаємодіють між собою згідно з принципом зворотного зв’язку. Структура ОБ служить для збереження слів інформації, вико- нання набору МО та обчислення значень ЛУ. МО, що реалізуються ОБ, збуджуються керую- чими сигналами із деякої множини Y, що над- ходять із КБ. На станах ОБ, які виникають в ОБ після виконання МО, обчислюються значен- ня ЛУ, які відображаються інформаційними сигналами із деякої множини X. Ці сигнали (значення ЛУ) поступають на вхід КБ, який під їхнім впливом генерує нові керуючі сигна- ISSN 2706-8145, Control systems and computers, 2020, № 1 5 Принцип мікропрограмного керування та автоматизація проектування ли, що знову надходять на вхід ОБ і так далі до завершення виконання тієї чи іншої операції. Найменування операції, яку реалізує ОП, визна- чається кодом операції. Як і сигнали із Х, коди операцій зараховують до класу інформаційних сигналів. Отже, КБ задає порядок виконання дій в ОБ і, тим самим, керує роботою ОП, у той час як ОБ є, по суті, виконавчою частиною ОП. Функціонування та структуру КБ можна визначити й на базі поняття мікрокоманди – керуючого слова, що має операційно-адресну структуру та визначає порядок функціонуван- ня ОП протягом одного такту машинного часу. Послідовність мікрокоманд, що відповідає мі- кроалгоритму, який реалізує ту чи іншу опера- цію, також називають мікропрограмою цієї операції. МПР може бути записана в (постій- ний) запам’ятовуючий пристрій. ОП, в яких КБ реалізуються подібним чином, називають ОП з програмованою, або "м’якою", логікою. ОП, схеми яких будуються з дискретних (логіч- них) елементів, називають пристроями з "твер- дою" логікою. Існує також змішане керування операціями, при якому частина операцій реа- лізується на "твердій", а частина — на "м’якій" логіці. Кожен із перерахованих способів має свої переваги і недоліки. Причому останнім часом частіше використовується м’яка логіка. Проте, при вирішенні багатьох важливих прак- тичних задач при побудові КБ зручніше вико- ристовувати "тверду" логіку керування вико- нанням операцій [16–19]. Зазначимо, що часто при проектуван- ні обчислювальної системи буває доціль- ним багаторівневе подання ОП. Так, в од- них випадках, наприклад, при проектуванні центрального пристрою керування комп’юте- ром, виникає потреба розглядати АЛП як час- тину ОП, тоді як при проектуванні вже самого АЛП у ньому виділяються свої КБ і ОБ. Функції операційного та керуючого блоків. На даному рівні абстракції функція ОБ задається шляхом визначення множин D, R, S, Y, X, де D= = {d 1 , ..., dH} — множина вхідних слів, що вводяться в ОБ як операнди; R = {r 1 , ..., r Q } — множина вихідних слів, що містять результати операцій; S={s 1 , ..., s N } — множина внутрішніх слів, що слугують для представлення інформа- ції в процесі виконання операцій із множини F ={f 1 , ..., f G }. Припускається, що D⊆S і R⊆S; Y={y 1 , ..., у M } — множина МО, що реалізують перетворення S = ϕ m (S) над словами інформа- ції, де ϕ m — обчислювана функція; X = {x 1 , ... ..., х L } — множина ЛУ, де x i = ψ i (S), а ψ i — буле- ва функція (БФ). Зазначимо, що час не є аргументом функції ОБ, оскільки ОБ характеризує лише засоби, які можуть бути використані для обчислень, і ніяк не впливає на порядок протікання обчис- лювального процесу у часі — цю функцію бере на себе КБ. Оскільки МО і ЛУ стосовно до КБ розгля- даються як елементарні символи із множин Y і X відповідно, то його функція може задаватися операторною схемою МПР, у якій символи із Y відіграють роль операторів, а символи із X – роль ЛУ. На сьогодні задавання операторних схем алгоритмів відбувається переважно у фор- мі граф-схем алгоритмів (ГСА) Л.А. Калужніна [20]. ГСА є графічним аналогом логічних схем алгоритмів (ЛСА) А.А. Ляпунова [21–24]. Кож- на з цих форм визначає обчислювальний про- цес у послідовному аспекті — встановлює по- рядок перевірки ЛУ і порядок виконання МО. Зазначимо, при описі ГСА слова "оператор" і "мікрокоманда" будемо розглядати як сино- німи, тобто під оператором будемо розуміти множину МО, що записані в одній оператор- ній вершині і виконуються в ОП одночасно. Надалі, виходячи з функцій КБ і ОБ, визнача- ються структури цих блоків. Основні характеристики операційного блоку. На базі введених понять уточнимо характе- ристики ОП, що входять до формулювання основної задачі проектування ОП. До ос- новних характеристик ОП належать швидко- дія і витрати устаткування [16–19]. Швидкодія ОП визначається середнім часом виконання операцій 1 ω= τ G g g g p = ∑ , де p g — ймовірність вико- нання операцій f g ; τ g — середній час виконання операції f g . Ймовірності р 1 , ..., р G визначаються класом задач, для вирішення яких призначе- 6 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко ний ОП і які вважаються відомими. ОП функ- ціонує в дискретному часі t = 0, 1, 2, ... Про- міжок між двома сусідніми моментами часу t і t+1 називається тактом. Протягом такту фор- мується набір керуючих сигналів, виконуються відповідні МО й обчислюються значення ЛУ. Тривалість такту Т залежить від складності МО й ЛУ та від швидкодії елементів, з яких побу- довані КБ і ОБ. З урахуванням сказаного, се- редній час виконання однієї операції τγ = T∗Θ, де T — тривалість такту; Θ — середня кількість тактів, за яке ОП реалізує операцію f g . Витрати устаткування в ОП: С = С КБ +С ОБ , де С КБ і С ОБ — вартість елементів у КБ і ОБ відпо- відно. При структурній реалізації в ОБ ви- окремлюють три частини: пам’ять S; комбіна- ційну схему (КС) Ф, що реалізує МО; КС Ψ, що обчислює значення ЛУ. Тоді С = С S + С Ф +Сψ+С КБ , де С S , С Ф , СΨ, С КБ – витрати устатку- вання, відповідно, на пам’ять S, КС Ф, КС Ψ та КБ. Вплив систем мікрооперацій і логічних умов на характеристики операційних пристроїв. Най- більш істотний вплив на характеристики ОП мають множини МО Y = {y 1 , ..., у M } і ЛУ X= ={x 1 , ..., х L } і, насамперед, системи функцій, на основі яких вони будуються. Дійсно, згідно з визначенням, МО у m ∈Y і ЛУ x l ∈X синтаксично записуються як sα := φ m (sβ1 , ..., sβk ) і x l := ψ l (sγ1 ,... ..., sγh ) відповідно. Отже, у множинах Y і Х еле- менти розрізняються як функціями Ф = {ϕ m } і Ψ = {ψ l }, на основі яких утворюються МО і ЛУ, так і наборами слів sα, sβ1 , ..., sβk ∈S і sγ1 , ... ..., sγh ∈S, які є операндами цих функцій. Сис- тему Z = <Ф, Ψ> називають системою утворю- ючих алгоритму[16–19]. Виявляється [18], що кількість тактів, необ- хідних для виконання операції, яку реалізує ОП, залежить як від самої операції, так і скла- ду системи Z: чим "елементарніші", простіші функції з Ф та Ψ, тим більша кількість тактів потрібна для виконання операції. Але це озна- чає, що середній час τ g виконання операції збільшується, а швидкодія ОП зменшується. Крім цього, зміна системи Z шляхом роз- кладання операцій із F на усе більш прості операції (МО і ЛУ) приводить до зменшення витрат устаткування С ОБ в ОБ, але, водночас збільшуються витрати устаткування С КБ в КБ. Виходить, що змінюючи склад МО і ЛУ, у тер- мінах яких описується МПР виконання опера- цій, можна "перекачувати" устаткування з ОБ у КБ і навпаки. При цьому можна знайти де- яку систему утворюючих Z m , яка забезпечить мінімум витрат устаткування в ОП. Однак, від- повідний системі Z m час виконання операцій ω досить великий. Щоб зменшити значення ω, тобто збільшити швидкодію ОП, необхідно додаткове устаткування, що використовується для реалізації більш складних МО і ЛУ. Отже, система утворюючих Z = <Ф, Ψ> суттєво впливає на характеристики ОП. Тому визначення набору функцій Z є першочер- говою задачею мікропрограмування. Однак, задача породження систем утворюючих, що мінімізують витрати устаткування та забез- печують заданий час виконання операцій у пристрої, досить складна, що ускладнює роз- робку формальних методів оптимізації харак- теристик ОП. В.М. Глушков запропонував під- хід до рішення цієї проблеми, який базується на апараті алгоритмічних (мікропрограмних) алгебр. У [3] наведено приклад перетворення мікропрограми множення двійкових чисел, який став уже класичним. Зазначимо, що апа- рат САА втілено у мові САА\Д (див. далі). Концепція функціонального мікропрограму- вання. Щоб синтезувати структуру ОП, необ- хідно прийняти деякий спосіб виконання операцій в ОП й описати його у формі МПР. МПР, що представляє функцію ОП безвіднос- но до засобів (структури ОП), які можуть бути використані для реалізації заданої функції, називається функціональною МПР [16–19]. Функціональна МПР фіксує в собі алгоритм виконання операції, який рекомендується роз- робником, і, крім цього, використовується як вихідна форма подання функції ОП, на основі якої синтезується структура КБ і ОБ, достатня для реалізації цієї функції. Зазначимо, процедура вибору розробни- ком алгоритму реалізації тієї чи іншої операції формалізована недостатньо, й тому розробник, у загальному випадку, рекомендує алгоритм, ISSN 2706-8145, Control systems and computers, 2020, № 1 7 Принцип мікропрограмного керування та автоматизація проектування який, як правило, погано (не повно) враховує витрати часу й устаткування на його реалі- зацію, роль окремих алгоритмів у процеду- рі "оптимального" об’єднання відповідних їм закодованих граф-схем МПР в один граф (див. далі) тощо. Для запису функціональних МПР необхідно мати ту чи іншу мову функціонального мікро- програмування (ФМ-мову). ФМ-мова роз- глядається, зазвичай, як інженерна, тобто не машинна, мова. З цієї причини для зручності в ФМ-мові використовують, зазвичай, загально- прийняту математичну символіку та графічне представлення схем алгоритмів. Функціональні МПР містять у собі дві час- тини: опис слів і масивів, що встановлює типи та формати слів, з якими оперує МПР; змістовний граф МПР, який визначає алго- ритм виконання операцій в ОП не в термінах елементів множин Y і X, а у вигляді описів МО і ЛУ в змістовній формі — така форма застосо- вується, як правило, на початкових (поперед- ніх) етапах проектування ОП. Розрізняють такі основні типи слів: – вхідні — значення приписуються поза МПР, а використовуються всередині МПР; – внутрішні (локальні) — значення припи- суються та використовуються лише всередині МПР; – допоміжні — значення приписуються та використовуються лише всередині МПР, але існують не постійно, а лише протягом обмеже- них інтервалів часу (в межах такту); – вихідні — значення приписуються в МПР і використовуються поза нею. Типи слів позначаються буквами: I — вхід- ні, L — внутрішні, А — допоміжні, О — вихідні. Деякі слова можуть використовуватися як еле- менти інформації декількох типів, тобто мо- жуть мати, наприклад, такі типи: IL, LO, ILO тощо. Деякі з МО із даної МПР можуть виконува- тися паралельно в часі, тоді як інші — лише по- слідовно. Кажуть, що сукупність МО володіє властивістю сумісності, якщо ця властивість гарантує можливість паралельного виконання МО із цієї сукупності. МО, що не володіють за- значеною властивістю, називаються несуміс- ними. Сумісність МО буває двох типів: функці- ональна і структурна. МО є функціонально сумісними, якщо вони присвоюють значен- ня різним словам, тобто якщо S 1 := ϕ 1 (S 2 ) і S 3 := ϕ 2 (S 4 ), де S 1 , S 2 , S 3 , S 4 ⊆S, то МО ϕ 1 і ϕ 2 — функціонально сумісні, якщо S 1 ∩S 3 = ∅. Структурна сумісність зумовлена структурою ОП, яка допускає чи виключає можливість па- ралельного виконання декількох МО. Якщо структуру ОП не визначено, то сумісними вважаються функціонально сумісні МО, інак- ше — структурно сумісні МО. Очевидно, що сумісні МО можуть записуватися в одній опе- раторній вершині й розглядатися як один опе- ратор (як одна мікрокоманда)Y t , t = 1, ..., Т, де Т — кількість операторних вершин МПР. Далі ми покажемо, що існують структури ОП, які забезпечують сумісність усіх функціонально сумісних МО, але більшість структур вносить обмеження на сумісність окремих груп чи всіх без винятку МО. Отже, засоби ФМ-мови мають, перш за все, забезпечувати опис алгоритмів виконан- ня операцій з таким ступенем деталізації, що уможливлює синтез адекватної структури ОП. Однак, це ще не все. Бажано також, щоб такі мови містили у собі засоби для перевірки коректності алгоритмів шляхом їхнього моде- лювання на комп’ютері та, крім цього, якісь засоби для оптимізації цих алгоритмів і асоці- йованих з ними ОП за тими чи іншими крите- ріям. На жаль, сучасні ФМ-мови недостатньо підтримують зазначені вимоги, особливо у комплексі. Уточнення функцій операційного та керуючого блоків. Легко бачити, що функціональні МПР M 1 , ..., M G , які описують алгоритми виконання в ОП операцій f 1 , ..., f G із F, несуть у собі всю інформацію про функції ОБ і КБ. Отож, визна- чимо спочатку функцію ОБ. Нехай S g ,Y g і X g — множини слів, МО і ЛУ відповідно, які вводить функціональна МПР М g , що реалізує алгоритм виконання операції f g ∈F, g = 1, ..., G. Тоді множини S, Y, X (вони за- дають функцію ОБ) достатні для реалізації всіх 8 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко операцій з множини F = {f 1 , ..., f G }, визначають- ся як об’єднання, відповідно, множин S g , Y g , X g для всіх М g , g = 1, ..., G. Деякі проблеми виникають лише при знаход- женні множини S. Дійсно, можна очікувати, що витрати устаткування в ОБ будуть тим мен- ше, чим менше сумарне число розрядів міс- титься в словах із S. Отже, при об’єднанні слів із S 1 , ..., S G необхідно вміти, якщо це можливо, ототожнювати їх між собою. Коли функціо- нальні МПР створюються незалежно одна від одної, то для ототожнення слів потрібна спеці- альна процедура. Однак у роботі ми лише при- пускаємо, що функціональні МПР будуються з урахуванням їх об’єднання й, у зв’язку з цим, тотожні слова, що використовуються в різ- них МПР, ідентифікуються однаковими іме- нами. Таке припущення дозволяє процедуру об’єднання множин S 1 , ..., S G звести до пере- рахування в множині S слів з попарно різними ідентифікаторами, а якщо слова з однаковими ідентифікаторами мають різну довжину, то в множину S включати лише слово з максималь- ною довжиною (якщо слово меншої довжини можна подати в більшому форматі). Множина Y визначається перерахуванням усіх попарно різних МО (операторів присвою- вання) з множин Y 1 , ..., Y G , що "витягуються" зі змістовних МПР M 1 , ..., M G відповідно. Лег- ко бачити, що число МО у множині Y можна зменшити, якщо при розробці функціональ- них МПР M 1 , ..., M G використовувати, по мож- ливості, одні й ті самі МО. Аналогічно визначається достатня для реалі- зації операцій із F множина ЛУ X. Функція КБ, як ми вже знаємо, задається: множиною Х вхідних (інформаційних) сиг- налів, що відбивають стан ОБ; множиною Y вихідних (керуючих) сигна- лів, що ініціюють реалізацію МО в ОБ; операторною граф-схемою МПР, яка задає порядок проходження керуючих сигналів із Y залежно від значень інформаційних сигналів X. Однією з форм операторних схем є так звана закодована граф-схема МПР, яку можна отри- мати зі змістовної граф-схеми МПР шляхом заміни МО (ЛУ), що знаходяться в оператор- них (умовних) вершинах, на відповідні їм сим- воли із множини Y = {y 1 , ..., у M } (X = {x 1 , ..., х L }). При цьому однакові МО і ЛУ, що знаходяться у різних операторних і умовних вершинах МПР, замінюються на однакові символи із множин Y і Х відповідно. Якщо функція КБ визначається сукупністю закодованих ГСА Г 1 , ..., Г G , що відповідають змістовним ГСА M 1 , ..., M G , то, в принципі, на основі ГСА Г 1 , ..., Г G можна синтезувати G КБ, що забезпечать керування ОБ. Однак таке рі- шення не є оптимальним з наступних причин [16–19]. ГСА різних МПР, як правило, містять однакові операторні й умовні вершини. Якщо процедуру об’єднання ГСА Г 1 , ..., Г G в одну ГСАГ побудувати таким чином, що однакові операторні й однакові умовні вершини ГСА Г 1 , ..., Г G будуть "зливатися" в одну операторну й одну умовну вершину ГСА Г, то можна очі- кувати, що число операторних й умовних вер- шин у ГСА Г — у порівнянні з аналогічними числом у граф-схемах Г 1 , ..., Г G — зменшиться, що, у свою чергу, спричинить зменшення вит- рат устаткування в КБ. У зв’язку з цим слід очі- кувати, що витрати устаткування в ОП, побу- дованому по об’єднаній ГСА Г, у загальному випадку, будуть менші, ніж сумарні витрати устаткування в G ОП, кожен з яких реалізує відповідну закодовану ГСА Г 1 , ..., Г G . Таким чином, функцію КБ доцільно представляти у вигляді закодованої ГСА, що є об’єднанням закодованих ГСА МПР, які описують алгорит- ми виконання окремих операцій. Метод об’єднання ГСА Г 1 , ..., Г G у єдину граф-схему Г, що містить мінімальу кількість операторних і умовних вершин, наведено в [19]. В об’єднаній МПР шляхи розвитку процесу обчислень, що відповідають різним операціям f 1 , ..., f G , задаються h-розрядним набором двій- кових змінних p 1 , ..., p h , де h ≥ log 2 G, за допомо- гою яких кодуються операції. При цьому змін- ні p 1 , ..., p h відіграють роль ЛУ, які визначають переходи в об’єднаній МПР. Зрозуміло, чим більшою є кількість МПР, що беруть участь в об’єднанні, тим більше можливостей створю- ється для злиття фрагментів різних МПР і, як наслідок, кількість вершин в об’єднаній МПР ISSN 2706-8145, Control systems and computers, 2020, № 1 9 Принцип мікропрограмного керування та автоматизація проектування часто виявляється значно меншою сумарної кількості вершин в об’єднуваних МПР. Характеристики операційного блоку. Основ- ними характеристиками ОБ є продуктивність, швидкодія, витрати устаткування (вартість), регулярність та універсальність [16–19]. ОБ можна розглядати як самостійний об’єкт. У цьому разі такт τ ОБ — це проміжок часу від мо- менту надходження на вхід ОБ керуючих сиг- налів до моменту вироблення значень інфор- маційних сигналів, що відповідають стану пам’яті ОБ. Тривалість T такту визначається максимальним значеням, необхідним для ви- конання будь-якої МО й обчислення значення будь-якої ЛУ. При цьому тактуючі (синхроні- зуючі) сигнали, які виробляються в комп’ютері генератором тактуючих імпульсів, слідують один за одним з періодом Т. Продуктивність ОБ — це кількість МО, що виконується в ОБ протягом такту. В одному такті можуть виконуватися лише сумісні МО, що знаходяться в одній операторній вершині МПР, і їхнє число може змінюватися від такту до такту. Тому кількість МО, що виконуються в ОБ за один такт, є дискретною випадковою величиною. Фактор випадковості вноситься вхідними даними D, у залежності від значень яких про- цес виконання МПР може розвиватися різни- ми шляхами алгоритму. З урахуванням цього продуктивність оцінюють або максимальною кількістю МО, які може виконати ОБ протя- гом такту, або середнім значенням. Якщо при- пустити, що МПР складається з К операторів, кожен із яких містить m k сумісних МО, і що в одній реалізації МПР кожен оператор викону- ється у середньому q k раз (k=1, …, K), то серед- ня кількість МО, що виконуються ОБ в одно- му такті, визначається як 1 1 K k k k K k k q mV q = = ∑= ∑ . Швидкодія ОБ характеризується тривалістю такту τ ОБ — чим менше тривалість такту, тим вище швидкодія ОБ. Швидкодія залежить як від структури KC Ф і Ψ, так і від швидкісних характеристик логічних і запам’ятовуючих еле- ментів, з яких побудовано КС і пам’ять S ОБ. Витрати устаткування С ОБ в OБ, як і раніше, визначаються сумою: С ОБ = С S + С Ф + СΨ. Регулярна структура складається з однотип- них частин, які однаково пов’язані між собою. Очевидно, регуляризація структури спрощує процес її виробництва, що, у кінцевому ра- хунку, призводить до зменшення її вартості та збільшення надійності. Універсальність (багатофункціональність) cтруктури ОБ проявляється в можливості реа- лізації однією структурою досить широкого класу функцій (алгоритмів). Якщо структура універсальна, то реалізація будь-якого алго- ритму зводиться до перенастроювання струк- тури зовнішніми засобами, наприклад шля- хом програмування. Якщо система МО і ЛУ повна, то максимальний ступінь універсаль- ності досягається, якщо будь-які MO і ЛУ можуть бути поширені на кожен з регістрів ОБ. Легко бачити, що чим більш універсальна структура, тим ширше область її застосуван- ня. Збільшення ступеню універсальності доз- воляє скоротити номенклатуру виробів, збіль- шити об’єм їх випуску та знизити вартість ви- робництва. Виявляється [18], що регулярність і універ- сальність — взаємозалежні властивості. Регу- лярні структури, як правило, більш універ- сальні, ніж нерегулярні, а збільшення ступеня універсальності можна досягнути шляхом регу- ляризації структури. Формальні методи проектування обчислювальних систем Дискретні перетворювачі інформації (ДПІ) мо- жуть розглядатися, зокрема, як базова матема- тична модель комп’ютерів і використовуватися як відправна точка для розв’язання задач авто- матизації проектування обчислювальних сис- тем. Цей підхід, запропонований В.М. Глуш- ковим [1–7], узагальнює ідеї А. Тьюринга і ґрунтується на припущенні, що узагальненою моделлю будь-якого ОП служить композиція зі зворотним зв’язком двох автоматів — керую- чого (КА) та операційного (ОА), причому вибирають, як правило, автомати Мілі та Мура 10 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко відповідно. Такий підхід має загальний харак- тер і використовується не лише в моделях од- нопроцесорних обчислювальних систем, але й у тих випадках, коли ОП є багатопроцесорним комплексом [5, 6]. Уведемо необхідні поняття. Розглянемо ініціальний, у загальному ви- падку — частковий, детермінований автомат � = <А, Q, В, δ, γ>, де А — вхідний алфавіт, Q — алфавіт станів, у якому виділено початковий q 0 і заключний q* стани, В — вихідний алфавіт, δ — функція переходів і γ — функція виходів. Нехай М — непорожня множина, яку назива- ють інформаційною, і припустимо, що зада- ні два (часткових) відображення π: M →A та ξ: B →F, де F = F М : M→M — сукупність частко- вих відображень із M в M. Дискретним перетворювачем інформації, що діє на інформаційній множині М, нази- вають четвірку T = < , π, ξ; М0>, де М0⊆М, відображення з F називають елементарними операторами, π — функцією відміток, M0 — множиною початкових станів множини М, а відображення π і ξ — інтерпретацією вхідних і вихідних сигналів ДПІ T [1–5]. Припускається, що функціонування ДПІ Т розпочинається у початковий момент часу, коли встановлено в стан q 0 , а інформаційну множину М — у стан х∈M0. Якщо π(х)=а, то , під впливом а, переходить у стан δ(q 0 , а), а на його виході з’являється символ γ(q 0 ,а)=b, якому ставиться у відповідність відображення ξ(b) = f. Отже, один цикл роботи ДПІ пере- творює початковий стан х на стан у = f(х). Далі знов обчислюється π(у) і т. д. Процес триває доти, доки не відбудеться одна з подій: автомат потрапить у заключний стан q∈Q; відобра- ження f∈F або одна з функції π, ξ, δ, γ будуть невизначені у якийсь момент часу. Як тільки одна з цих подій відбувається, ДПІ припиняє роботу. Описаний процес часто подають як спільне функціонування двох автоматів: КА (див. ра- ніше) і ОА , який визначається так: = <B, ℳ, A, σ, π>, де В — вхідний алфавіт, А — вихідний алфавіт, ℳ — множина станів, елементами якої є елементи інформаційної множини М, σ — функція переходів така, що σ(х, b) = f b (х), де f b = = ξ(b), і π — функція виходів, що співпадає з раніше визначеним відображенням π: M →A. Спільне функціонування автоматів і поля- гає у наступному. Задаються початкові стани КА та ОА і значення виходу ОА на його по- чатковому стані. Спочатку спрацьовує КА , значення його виходу подається на вхід ОА , який змінює свій стан і подає на вхід символ із B і так само далі. Зазначимо, на відміну від КА, який, зазви- чай, є скінченним, ОА, у загальному випадку, має нескінченну множину станів, оскільки на потужність інформаційної множини, елемен- ти якої моделюють оброблювану інформацію, ніяких обмежень не накладається. Легко бачити, що ДПІ Т задає часткове відображення r T : М0→М, причому r T (х) співпа- дає зі значенням оператора f b = ξ(b), обчисле- ним у заключному стані КА. Якщо автомат не потрапляє в цей стан, значення r T (х) не визна- чено. Значення r T не визначено також у точках з М\М0, проте ці точки можуть бути проміж- ними і заключними станами при обчисленнях. Часткове відображення r T називають операто- ром, поданим у ДПІ Т. Алгебра В.М. Глушкова. Нехай M — непорож- ня множина, яку, як і раніше, будемо називати інформаційною, а її елементи — станами інфор- маційної множини M; F M : М →М — сукупність різноманітних часткових відображень із М в М; е — тотожне на М відображення; η — ніде не визначений на М оператор; Р M : М→Е 3 — множина всіх одномісних предикатів на М, що набувають значення в Е 3 ={0, μ, 1}, де μ — неви- значене значення. Уведемо операції: диз’юнкції ϕ 1 : Р M ×Р M →Р M , ϕ 1 (α, β) = α ∨ β (тут і далі α, β∈Р M ); кон’юнкції ϕ 2 : Р M ×Р M → Р M , ϕ 2 (α, β) = α∧β= = αβ; заперечення ϕ 3 : Р M → Р M , ϕ 3 (α) = ¬α; лівого множення умови на оператор (прог- нозування):ϕ 4 : F M ×Р M →Р M , ϕ 4 (f, α)(х) = =α(f(х)) для всякого х∈M; ϕ 4 (f, α) =fα; композиції відображень ψ 1 : F M ×F M → F M , ψ 1 (f, g) = fg; ISSN 2706-8145, Control systems and computers, 2020, № 1 11 Принцип мікропрограмного керування та автоматизація проектування α-диз’юнкції ψ 2 : Р M ×F M ×F M →F M : Зазвичай, α-диз’юнкцію ψ 2 (α, f, g) операто- рів f і g позначають як α(f∨g) або [α](f∨g); α-ітерації ψ 3 : Р M ×F M →F M задається так. Нехай α∈Р M , f∈F M , х∈М, тоді k(α, f, x) = ={n∈N: α(f i (x)) = 0, i = 0, 1, ..., n}, де f 0(x) = =х. Через m позначимо max k(α, f, x), якщо цей максимум існує, і α(f m+1(х)) = 1. Тоді α-ітерація оператора f позначається, зазви- чай, як α{f} або [α]{f}. Нехай Ω={ϕ 1 , ϕ 2 , ϕ 3 , ϕ 4 , ψ 1 , ψ 2 , ψ 3 } і зада- на множина сортів S = {1, 2}, А = {A 1 , А 2 }, де А 1 =Ф⊆F M , A 2 =П⊆Р M . Системою алгоритміч- них (мікропрограмних) алгебр (САА) назива- ють скінченно породжену двохосновну алгебру = =<A, Ω> (або = <Ф, П, Ω>) з фіксованою скінченною системою твірних (Ф 0 , П 0 ), де Ф 0 ⊆Ф, П 0 ⊆П. При цьому Ф називають прос- тором операторів, П — простором умов, опера- тори з Ф 0 — елементарними операторами, а предикати з П 0 — елементарними умовами алгебри . . Операції сигнатури Ω цієї алгебри мають наступні типи: ϕ 1 (22, 2), ϕ 2 (22, 2), ϕ 3 (2, 2), ϕ 4 (12, 2),ψ 1 (11, 1), ψ 2 (211, 1), ψ 1 (21, 1). Нехай тепер X (Y) — скінченна множина змінних, кожній з яких у взаємнооднознач- ну відповідність поставлено функціональний (предикатний) символ, що відповідає опера- тору з Ф 0 (умовi з П 0 ). Розглянемо множину R термів сигнатури Ω, що складаються з цих змінних. Терми з R називаються регулярними схемами. Задана відповідність, зазвичай, являє собою інтерпретацію змінних, які входять до регулярних схем. Разом з тим визначені і зна- чення кожного з термів R . При цьому терм на- буває значення в Ф (в П) лише тоді, коли він має сорт 1 (сорт 2). Якщо t — терм сорту 1 (сор- ту 2), що набуває значення f∈Ф (α∈П), то регу- лярну схему t називають регулярною схемою оператора f (умови α) і кажуть, що оператор f∈Ф (умова α∈П) подано регулярною схемою t. САА ще називають алгоритмічною алгеброю, алгеброю алгоритмів або алгеброю Глушкова. Надалі відповідно до класу задач, на вирі- шення яких був спрямований апарат САА, сигнатура Ω змінювалася: деякі операції вилу- чались, інші – вводились у сигнатуру; іноді до імені САА, що утворюється при цьому, дода- ється слово "модифікована". Апарат САА є еквівалентним за своїми мож- ливостями обчислювати функції класичним алгоритмічним системам – таким, як машини Тьюринга, алгорифми Маркова, схеми Янова тощо. Проте, у порівнянні з цими формаліз- мами, САА більш зручна в практичному від- ношенні, оскільки за допомогою операцій її сигнатури Ω можуть бути описані "програми" обчислення значень операторів із Ф (або умов із П), зображених за допомогою інших, елемен- тарних, операторів і умов. Якщо "елементарні" оператори та умови вибираються з деякої фік- сованої системи твірних С, то конструкції про- грам можна описати елементами алгебри R(Ω, С), тобто термами сигнатури Ω, в яких змін- ними є елементи системи твірних алгебри . У зв’язку з цим регулярна схема оператора може розглядатися як математична модель при проектуванні ОП та реальних алгоритмів і про- грам, а також при розробці відповідних інстру- ментальних засобів (див. далі). Перевагою алгебр Глушкова є також можли- вість проведення на основі тотожностей даної алгебри (справедливих як для операторів і умов будь-якої алгебри, так і для конкретних опера- торів і умов конкретної алгебри) різноманітних перетворень (з метою, наприклад, оптимізації за тим чи іншим критерієм) регулярних схем як алгоритмів і програм, так і операторів (мікро- програм) даної алгебри [6]. При вирішенні задач автоматизації проек- тування обчислювальних систем з’являється проблема відповідності формальних засо- 12 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко бів, які використовуються для моделювання роботи комп’ютерів, і засобів, що описують "програми" обробки даних на них. До пер- ших належить, зокрема, формальне подання комп’ютерів у вигляді ДПІ, других — апарат САА. У зв’язку з цим особливе значення має наступний результат, отриманий В.М. Глушко- вим [4–6]. Теорема Глушкова. Будь-який оператор, по- даний у скінченному ДПІ, може бути заданий і регулярною схемою САА, асоційованою із цим ДПІ. Зазначимо, що вивчення різних форм по- дання алгоритмів і розв’язання проблем їх від- повідності один одному має давню історію і становить не лише теоретичний, а й глибокий практичний інтерес (див. далі). Алгоритм синтезу операційних пристроїв З урахуванням проблематики, що виникає у результаті аналізу основної задачі проекту- вання ОП, і зроблених при цьому застережень, сформулюємо алгоритм синтезу ОП. Цей алго- ритм включає алгоритми синтезу КА та ОА, з яких складається ОП [16—19]. Алгоритм синтезу керуючого автомата умов- но розбивається на наступні етапи. Етап 1. Для кожної з операцій f 1 , ..., f G , реалі- зація яких покладається на ОП, обирається відповідний цій операції алгоритм, який реалі- зовуватиме її. Етап 2. Фіксуються мова і форма опису алгоритмів. У термінах обраних засобів — не- хай це будуть граф-схеми — створюють зміс- товні МПР М 1 , ..., М G . Етап 3. Для кожної змістовної МО склада- ється список керуючих сигналів із множини Y, який забезпечує її (МО) виконання; визнача- ються тривалості кожного керуючого сигналу (у числі тактів) і періоди тактуючих сигналів автомата. Етап 4. Кожній змістовній ЛУ ставиться у від- повідність інформаційний сигнал із набору Х. Етап 5. З функціональних МПР М 1 , ... ..., М G визначаються множини слів S = {s 1 , ... ..., s N }, МО Y = {y 1 , ..., у M } і ЛУ X= {x 1 , ..., х L }, необхідні для реалізації операцій із набору F = = {f 1 , ..., f G }. Множини S,Y,X визначаються як об’єднання, відповідно, множин слів S g , МО Y g , ЛУ X g , що вводяться однією М g , g = 1, ..., G. Етап 6. Будуються закодовані ГСА Г 1 , ..., Г G , що відповідають змістовним МПР М 1 , ..., М G . Етап 7. Закодовані ГСА Г 1 , ..., Г G об’єднують- ся в одну ГСА Г. Задача об’єднання ГСА фор- мулюється так. Припустимо, що у кожній з ГСА оператори не повторюються, але в різних ГСА можуть зустрічатися однакові оператори. Потрібно побудувати об’єднану ГСА Г, яка за умови, що повинна виконуватися операція f g є рівносильною ГСА Г g (g = 1, ..., G). Процедуру об’єднання ГСА можна умовно розбити на такі етапи. Для кожної граф-схеми Г g будується відпо- відна їй матрична схема алгоритму (МСА) C g (g = 1, ..., G). Нехай ГСА Г g має початкову Y g0 і кінцеву Y gk вершини, а також Т g інших опера- торних вершин з записаними у них різними операторами Y g1 , ..., Y Тg . Тоді МСА C g , що відпо- відає ГСА Г g , являє собою квадратну матрицю, рядки якої позначено символами Y g0 , Y g1 ,... ..., Y Тg , а стовпці — символами Y g1 , ..., Y Тg , Y gk . У цій матриці на перетині рядка Y gi і стовпця Y gj стоїть функція переходу α ij від оператора Y gi до оператора Y gj . Перехід від ГСА Г g до МСА C g (g = = 1, ..., G) наступний: по ГСА Г g необхідно знай- ти усі функції переходу і занести їх у відпо- відні клітини матриці. Перехід від МСА C g до ГСА Г g полягає у послідовному отриманні сис- теми формул переходу, системи факторних (дужкових) формул переходу і після цього — ГСА Г g (g = 1, ..., G). Кожна МСА C g кодується вектором (е g1 , ... ..., е gh ) значень змінних p 1 ,..., p h , де p i ∉∪ Х g , а X g — множина ЛУ граф-схеми Г g ; е gі ∈{0, 1}; і = 1, ... ..., h; 2h ≥ G. Кожній MCA C g ставиться у відповідність кон’юнкція P g = p 1 #...p h #, де p i # = p i , якщо е gi =1, і p i # = p i , якщо е gi = 0; і = 1, ..., h; (е g1 , ..., е gh ) — код МСА С g . Будується об’єднана МСА C, рядки і стовп- ці якої позначено усіма операторами, що вхо- дять в об’єднання множин операторів МСА G g=1 ISSN 2706-8145, Control systems and computers, 2020, № 1 13 Принцип мікропрограмного керування та автоматизація проектування С1, ..., С G . Серед рядків, як і раніше, немає Y k , а серед стовпців — Y 0 . Елемент α ij МСА С дорів- нює α ij 1 P 1 ∨...∨α ij G P G , де α ij G — елемент МСА С g , що стоїть на перетині рядка Y gi і стовпця Y gj . Оскільки кон’юнкція Р g (g = 1, ..., G) дорів- нює одиниці весь час, поки МСА С "працює" як МСА С g , жоден оператор не змінює значень змінних р 1 , ..., р h (щодо цих змінних маємо порожній розподіл зсувів [19]), у зв’язку з чим МСА С можна мінімізувати з урахуванням роз- поділу зсувів. Для переходу від мінімізованої МСА С min до об’єднаної ГСА необхідно розбити МСА С min на підматриці і скористатися методом побудо- ви мінімальної ГСА або ж спробувати знайти близьку до мінімальної систему факторних формул переходу для кожної із підматриць. При цьому в обох випадках слід враховувати невизначеності двох типів, які виникають при об’єднанні часткових МПР [19]: Якщо число G МПР, що об’єднуються, строго менше 2h, тобто не всі набори значень змінних р1, ..., рh використовуються для коду- вання МСА С 1 , ..., С G , усі формули переходу (або відмічені покриття формул переходу) є не- визначеними на тих наборах значень змінних р 1 , ..., р h , x 1 , ..., x L , які покриваються кубами (е g1 ...е gh х...х), де (е g1 ... е gh ) — невикористаний набір значень змінних р 1 , ..., р h . Якщо оператор Y t не зустрічається в яки- хось МСА С g (g = 1, ..., G), то формула переходу для Y t (зазначене покриття Y t ) не визначена на тих наборах значень змінних, які покриваються кубом (е g1 ...е gh х...), де (е g1 ...е gh ) — код МСА С g . Якщо тепер для підматриць побудувати від- повідні ГСА, то після об’єднання однакових вихідних і вхідних операторних вершин в одну вершину прийдемо до необхідної об’єднаної ГСА Г. Алгоритм синтезу керуючого автомата як автомата Мілі. В основі процедури синте- зу КА лежить так званий канонічний метод структурного синтезу автоматів з пам’яттю, теоретичним фундаментом якого є теорема В.М. Глушкова про структурну повноту [1]. Вхідними даними для початку роботи методу служить абстрактний (цифровий) автомат з пам’яттю, заданий своїми таблицями перехо- дів і виходів, а результатом роботи — рівняння булевих функцій переходів, виходів і функ- цій збудження елементів пам’яті в канонічній (операторній) формі подання. Якщо етапи 1–7 алгоритму синтезу КА є спільними для будь- яких типів КА, то надалі алгоритм синтезу розгалужується в залежності від типу КА, що синтезується. Етап 8. Обирається тип КА. КА може бути синтезовано або як автомат Мілі, або як авто- мат Мура. Припустимо, що ми обрали автомат Мілі. Етап 9. Здійснюється позначення станів у закодованій (об’єднаній) ГСА Г: символом a 1 позначається вхід вершини (логічної чи опера- торної), що слідує за початковою, а також вхід кінцевої вершини; входи усіх вершин, що слі- дують за операторними, позначаються різни- ми символами а j . Крім визначених станів може виникнути необхідність уведення додаткових станів, зокрема, для забезпечення стійкості роботи ОП (див. далі); Етап 10. Закодована ГСА з позначками ста- нів інтерпретується як автомат Мілі. З цією метою за даною ГСА будується граф перехо- дів і виходів автомата Мілі. Число вершин у цьому графі дорівнює числу позначок станів а j на ГСА. Кожному переходу автомата Мілі з одного стану в інший відповідає дуга графа. Дузі приписується набір ЛУ, що викликає цей перехід, а також набір керуючих сигналів, що відповідає даному переходу. Етап 11. Здійснюється кодування станів КА. Довжина m двійкового кортежу, яка дозво- ляє однозначно закодувати стани КА, визна- чається з умови 2m ≥ M, де М — число станів КА (бажано, щоб m було мінімальним). Число m визначає кількість тригерів, необхідних для організації пам’яті КА. У результаті кожному стану а j відповідає одна визначена комбінація значень Q 1 , ..., Q m виходів тригерів. Зазначимо, що спосіб кодування впливає на правильність формування керуючих сиг- налів і складність КА. Зокрема, неоптимальне кодування станів зумовлює появу негативних явищ —"гонок" сигналів та "проскоків" станів в КА. 14 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко Для усунення цього недоліку потрібно, зокре- ма, використовувати "сусіднє" кодування станів (код Грея). В КА, що не допускають сусіднього кодування, необхідно вводити додаткові стани. Етап 12. Будується структурна таблиця пере- ходів і виходів КА, а також функцій збуд- ження елементів пам’яті (припускається, що нам відомі типи логічних елементів і типи три- герів, які будуть використовуватися у процесі синтезу ОП). Структурна таблиця КА будуєть- ся за його графом переходів і виходів. У кожен рядок таблиці записують код поточного стану (у момент часу S), код стану переходу (у мо- мент часу S+1), значення ЛУ, що забезпечують перехід, відповідні значення керуючих сигна- лів і функцій збудження тригерів. Етап 13. Структурна таблиця інтерпрету- ється як таблиця істинності для функцій збуд- ження елементів пам’яті та функцій виходів (керуючих сигналів) як функцій кодів станів КА в момент часу S і ЛУ, що спричиняють перехід у стан КА у момент часу S+1. На під- ставі такої інтерпретації знаходяться аналітич- ні представлення названих функцій у вигляді МДНФ. Етап 14. Знаходиться операторна форма представлення знайдених функцій збудження тригерів і керуючих сигналів. Етап 15. Операторні форми розглядаються як форми для побудови структурної схеми КА і ескіза друкованої плати. На цьому процедура синтезу КА як автомата Мілі завершується. Алгоритм синтезу керуючого автомата як автомата Мура. Етап 8. Обирається тип КА. Припустимо, що ми обрали автомат Мура. Етап 9. Здійснюється позначення станів закодованої ГСА для автомата Мура: симво- лом a 1 позначаються початкова і кінцева вер- шини, а всі інші операторні вершини познача- ються різними символами а j (може виникнути необхідність уведення додаткових станів). Етап 10. На графі переходів і виходів авто- мата Мура у вершинах графа, число яких до- рівнює кількості позначок у закодованій ГСА, записують стани КА і відповідні їм керуючі сигнали, а дугам, що з’єднують вершини гра- фа, приписують лише набори ЛУ, що спричи- няють відповідні (вершинам графа) переходи КА зі стану в стан. Етап 11. Кодування станів автомата Мура можна виконувати так само, як і для автомата Мілі. Однак при відповідному кодуванні керу- ючі сигнали можна знімати і безпосередньо з виходів тригерів автомата Мура, тобто КС для формування функцій y j не потрібні. Етапи 12–15 синтезу автоматів Мура май- же повністю (з урахуванням особливостей цих автоматів) повторюють відповідні етапи син- тезу автоматів Мілі. Основні структури операційних автоматів. До основних структур ОА відносяться ОА з канонічною структурою, І-автомати, М-авто- мати, ІМ-автомати з паралельними та послі- довними комбінаційними частинами (КЧ). Для синтезу структури ОА не підходять методи, що використовуються при синтезі КА, оскіль- ки в основі цих методів лежать результати абстрактної теорії автоматів, а число різних станів, в яких може перебувати ОА, дуже ве- лике. Структури ОА в заданому структурному базисі, який утворюють шини, регістри та КС, можна синтезувати безпосередньо за функці- єю, реалізація якої покладається на ОА. Як ві- домо, функція ОА задається множинами: слів S = {s 1 , ..., s N }, які можуть бути вхідни- ми, вихідними і внутрішніми; МО Y = {y m } = {sα:= ϕ m (sβ1 , ..., sβk )}, m = 1, ..., M і sα, sβ1 ,..., sβk ∈S; ЛУ X = {x l = ψ l (sγ1 , ..., sγt )}, де l = 1, ..., L i sγ1 , ..., sγt ∈S. При цьому функцію ОА можна "витягти" безпосередньо зі змістовної (об’єднаної) граф- схеми МПР, яку реалізує ОП. Канонічна структура операційного автома- та та її синтез. Алгоритм синтезу ОА з такою структурою: Словам s 1 ,...,s N , які мають в МПР тип L, ставляться у відповідність регістри s 1 , ..., s N з довжинами n 1 ,...,n N , що дорівнюють довжинам слів. Словам s d1 ,...,s dH , які мають тип I, став- ляться у відповідність вхідні полюси (входи) d 1 ,...,d H структурної схеми. Кожен вхід d 1 , ..., d H ISSN 2706-8145, Control systems and computers, 2020, № 1 15 Принцип мікропрограмного керування та автоматизація проектування з’єднується з відповідним регістром s d1 ,..., s dH шиною, що виходить із входу. Словам s r1 ,...,s rQ , які мають тип O, став- ляться у відповідність вихідні полюси (виходи) r 1 , ..., r Q структурної схеми. Кожен регістр s r1 ,...,s rQ з’єднується з відповідним виходом r 1 , ,...,r Q шиною, що виходить із регістра. Кожній MO y m ∈Y, що описується операто- ром присвоювання sα := ϕ m (sβ1 ,...,sβk ), ставиться у відповідність KC ϕ m , входи якої підключають- ся до регістрів sβ1 ,...,sβk , а вихід з’єднується ке- рованою шиною з регістром sα. Керована шина позначається сигналом y m , який ініціює MO присвоювання слову sα значення ϕ m (sβ1 ,...,sβk ). Для виконання MO передачі sα:=sβ й установ- ки sα := const не потрібні KC, що обчислюють значення двійкового виразу. Кожній ЛУ x l = ψ l (sγ1 ,....,sγt ), x l ∈X, ставиться у відповідність KC ψ l , входи якої з’єднуються з регістрами sγ1 ,...,sγt , а вихід позначається сигна- лом x l . Якщо ψ l — тривіальна БФ, то ЛУ інтер- претується ланцюгом, що виходить з певного розряду регістра sβ. Структуру ОА, яку отримують шляхом замі- ни кожного елемента функції ОА (слова, MO, ЛУ) відповідними елементами структурного базису, називають канонічною структурою. Як вже зазначалося, в структурі ОА можна виділити три частини: пам’ять S, KC Ф і Ψ. Множину МО Y можна розділити на N під- множин Y 1 = {s 1 :=ϕ mi (S)},....,YN = {sN := ϕ mq (S)}, кожна з яких складається із сукупності МО, що обчислюють значення лише одного слова із сукупності S = {s 1 ,...,s N }. Різні множини Y i та Y j не містять спільних МО і тому KC Ф можна розділити на незалежні підсхеми Φ 1 ,...,Ф N , які реалізують підмножини МО Y 1 ,...,Y N . Підсхе- ми Ф 1 ,...,Ф N обслуговують відповідні регістри s 1 ,...,s N й у кожному такті можуть реалізувати по одній МО y mi ∈Y 1 ,...,y mq ∈Y N . Аналогічно, КС Ψ, що обчислює значення ЛУ із множини X, може бути розділена на підсхеми Ψ 1 ,...,Ψ N , що об- числюють значення із підмножин ЛУ Х 1 ,...,Х N . Схему, що складається з регістра s n і КС Ф n і Ψ n (n=1,...,N), можна розглядати як елементарний ОА, який називають операційним елементом. Отже, у загальному випадку ОА можна роз- глядати як сукупність операційних елементів Е 1 ,...,Е N , число яких дорівнює кількості внут- рішніх слів, що оброблюються МПР. Властивості канонічних структур операцій- ного автомата. Оскільки канонічна структура не вносить обмежень на сумісність МО (тобто усі функціонально сумісні МО можуть викону- ватися паралельно в одному такті), то каноніч- на структура має максимальну продуктивність, яка може досягати N МО за такт, де N — кількість в МПР слів типу L. А тому витрати часу на виконання фіксованої МПР в ОА з канонічною структурою мінімальні у порів- нянні з іншими варіантами структур. Менших витрат часу можна досягти, якщо змінити ал- горитм виконання операцій в ОП, зокрема, шляхом аналітичних перетворень (див. далі). Можна стверджувати, що канонічна струк- тура має найвищу швидкодію (найменшу три- валість такту τ ОА ) у порівнянні з іншими варіан- тами структур (хоча швидкодія різних структур OA, що побудовані на одній і тій же елементній базі, розрізняється незначно). У більшості випадків канонічна структура не є мінімальною за кількістю устаткування ("заліза"), що може використовуватись при реалізації фіксованого набору операцій. Це викликано рядом причин, для усунення яких розроблено різні формальні методи. Одна з причин — пам’ять ОА може бути надлишко- вою по відношенню до певного алгоритму. Як ми вже знаємо, для мінімізації пам’яті ОА існу- ють методи, які дозволяють перетворити алго- ритм таким чином, щоб мінімізувати в ньому кількість слів для подання даних. Крім цього, надмірність устаткування в KC із Z = {ϕ 1 ,...,ϕ M , ψ 0 ,...,ψ L } часто спричинена тим, що декілька KC, наприклад ϕ a ,...,ϕω, можуть реалізовува- ти одну й ту саму функцію. Для зменшення кількості устаткування в ОА у цьому випадку можна, зокрема, замінити KC ϕ a ,...,ϕω однією схемою. На цій ідеї засновано, зокрема, клас I-автоматів (див. далі). Нарешті, набору КС Z може відповідати ін- ший, еквівалентний за своїми функціями, набір КС, який породжує менші витрати устаткуван- ня. І в цьому випадку можна шляхом глибоких 16 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко перетворень алгоритму, що приводять до змі- ни набору МО і ЛУ, створити новий набір, для реалізації якого будуть потрібні KC Z із менши- ми витратами устаткування порівняно з КС Z. Але, як зазначалося в [3–6], техніка формаль- них перетворень алгоритмів з метою зміни часу їх реалізації й зменшення витрат устаткування носить достатньо складний і громіздкий харак- тер, який, до того ж, важко формалізувати, і тому не дивно, що сьогодні такі перетворення виробляються, в основному, "вручну" і, до того ж, евристичними методами. Отже, канонічна структура, що реалізує зада- ну функціональну МПР, має максимально можливу для даної МПР продуктивність і максимальну швидкодію. Оскільки каноніч- на структура синтезується безпосередньо за функціональною МПР без використання жод- них процедур мінімізації витрат на "залізо", то така структура, в загальному випадку, є над- лишковою за кількістю устаткування, що вико- ристовується в ній. I-автомати та їх синтез. До класу I-автома- тів належать ОА зі структурою, у якій мінімаль- но можлива кількість KC забезпечує можли- вість одночасного виконання усіх функціо- нально сумісних МО. Уведемо необхідні по- няття. Двійкові вирази Cα1 Cα2 ...Cαp і Cβ1 Cβ2 ...Cβq (тут Сα, Сβ — аргументи оператора, що являють собою слова, їхні інверсії і констан- ти; — знаки двійкових операцій), що стоять у правій частині МО (оператора присвою- вання), називаються еквівалентними, якщо один з двійкових виразів може бути отриманий з іншого шляхом [18]: заміні слова Сα словом Сβ або ¬Сβ; заміні слова Сα константою (зокрема, ну- лем) і навпаки; заміні одних констант іншими, у тому чис- лі і нульовими; рівносильними перетвореннями виразу Cα1 Cα2 ...Cαp . Еквівалентними МО називаються МО із еквівалентними двійковими виразами. З цього визначення, зокрема, випливає, що МО будуть еквівалентними, якщо функції в їх операторах мають однакові імена. Так, sα1 := ϕ m (sα2 , ..., sαp ) і sβ1 := ϕ m (sβ2 , ..., sβq ) — еквівалентні МО. При цьому, у загальному випадку, р≠q, тобто кіль- кість аргументів р і q у функціях ϕ m може бути різною. Зазначимо, еквівалентність МО означає, що для обчислення двійкових виразів, які від- повідають цим MO, може використовуватися одна KC. Але це виключає сумісність цих МО через структурні обмеження, що виникають при цьому, і, у загальному випадку, призводить до збільшення часу виконання операцій. Для побудови структури, що реалізує сукуп- ність еквівалентних МО у а , …,y w , уводить- ся спеціальна форма подання таких МО — узагальнений оператор, який має вигляд: sγ:=Aα1 Aα2 ...Aαr , де Aα1 , Aα2 , ..., Aαr — допоміжні змінні, що приймають певні значення при ви- конанні МО у a , …, y w . Оскільки МО у а , …, y w не- сумісні, то довільна допоміжна змінна визна- чається завжди однозначно. Алгоритм синтезу І-автомата, по суті, зводиться до перетворен- ня заданого набору МО Y в сукупність узагаль- нених операторів, які виступають як форми для побудови структурної схеми I-автомата. Алгоритм полягає в наступному : Множина MO Y розбивається на підмно- жини Y 1 , ..., Y N , що відповідають внутрішнім словам (регістрам) s 1 , ..., s N . При цьому МО sα := ϕ m (sβ1 , ..., sβk ) приписується множині Yα. На підмножинах Y n , n = 1, ..., N виділяють- ся класи еквівалентних МО K nj , j = 1, ..., J n . Для класу K nj , що містить не менше двох MO, будується узагальнений оператор. Якщо клас K nj містить лише одну МО, то узагальне- ним оператором для нього є сама МО. Виходячи з опису слів, списку узагальне- них операторів і ЛУ будується структурна схе- ма I-автомата. Властивості І-автоматів. Легко бачити, що алгоритм синтезу І-автоматів базується на можливості подання структури ОА у вигляді композиції операційних елементів Е 1 , ..., Е N , де N — число слів типу L в МПР. Оскільки в структурі І-автомата, що виникає у результаті застосування даного алгоритму синтезу, кожен операційний елемент Е n використовується для обчисленням значень лише одного слова s n ISSN 2706-8145, Control systems and computers, 2020, № 1 17 Принцип мікропрограмного керування та автоматизація проектування (n = 1, ..., N), то така структура і не вносить об- межень на сумісність МО, і мінімізує витрати устаткування в ОА. Наслідок цього — макси- мальна продуктивність, яка при наявності N операційних елементів може, потенційно, досягати N МО за такт, і мінімальне число KC, які використовуються в OA для виконання МО. Отже, у порівнянні з ОА з канонічною струк- турою продуктивність І-автоматів не нижче, а витрати устаткування — менше. М-автомати та їх синтез. У структурі I-автомата можуть міститися еквівалентні за своїми функціями КС, які використовуються для обслуговування різних регістрів. При зада- ній МПР витрати устаткування в ОА можна мінімізувати, якщо кожну КС ϕ m використо- вувати для виконання всіх еквівалентних MO з множини Y. OA, синтезовані на основі даного принципу, називають M-автоматами. Для обчислення будь-якого двійкового ви- разу ϕ k (sβ1 , ..., sβk ) у структурі M-автомата ство- рюється одна KC Ф, рівнодоступна по відно- шенню до всіх регістрів s 1 , ..., s N , що оперують зі словами типу L. Для вибірки слів із регістрів s 1 , ..., s N на шини А1 і A2, по яким операнди, що беруть участь в MO, надходять на вхід КС Ф, використовуються керуючі сигнали a 1 , ..., а N та b 1 , ..., b N відповідно: сигнал а i ініціює передачу А 1 := s i , а сигнал b j — передачу A2 := s j . КС Ф налаштовується на виконання перетворення ϕ k (A 1 , A 2 ) = R керуючим сигналом ϕ k (k = 1, ... ..., К). Завантаження обчисленого значення R в будь-який регістр s n ініціюється керуючим сиг- налом d n (n = 1, ..., N). Отже, у процесі роботи М-автомат генерує специфічний набір керуючих сигналів {а i }, {b j }, {ϕ k }, {d n }, які ініціюють виконання MO s n := ϕk(s i , s j ). У результаті виникає новий на- бір MO {А 1 := s i } ∪{A 2 := s j }∪{R := ϕ k (A 1 , A 2 )} ∪ ∪{s n := R}, достатній для реалізації будь-якої MO функціональної МПР (зазначимо, існу- ють МО, наприклад унарні чи установки типу s n :=const, при виконанні яких деякі із сигналів а i , b j , ϕ k , d n не виробляються). Алгоритм синтезу М-автоматів зводиться до породження на основі списку MO Y су- купності операторів, притаманних структурі М-автомата (вибірки слів на шини, перетво- рення слів і завантаження результату в регі- стри), і складається з наступних етапів. Етап 1. Здійснюється розподіл регістрів на шини А 1 і А 2 з мінімізацією числа керованих шин, що використовуються для передачі опе- рандів на входи КС Ф. Етап 2. Визначаються формати і значення слів А 1 , А 2 . Як правило, приймається наступ- на угода про порядок подання внутрішніх слів s 1 , ..., s N допоміжними словами А 1 , А 2 : молодші розряди слів sα1 , ..., sαp , що складають множину А i (і = 1, 2), співставляються з молодшим роз- рядом слова A i . Кількість розрядів у слові А i визначається максимальним числом розрядів в словах sα1 , ..., sαp , включених в множину А i . Етап 3. Визначаються оператори, що реалі- зуються М-автоматом (тут, на відміну від мно- жини МО Y із МПР, під операторами розумі- ються МО, притаманні структурі М-автомата), і здійснюється кодування МО наборами керу- ючих сигналів. Етап 4. Визначаються класи еквівалентних МО, будуються узагальнені оператори і струк- турна схема М-автомата. Етап 5. Оскільки у кожному такті М-автомат реалізує лише одну МО, яка ініціюється набо- ром сигналів (а i , b j , ϕ k , d n ), то закодована ГСА, яка визначає функцію КА, повинна бути пере- творена наступним чином: кожна операторна вершина, яка містить q функціонально суміс- них МО y k1 , ..., y kq , замінюється послідовністю q операторних вершин, що містять по одній MO y k1 , ..., y kq ; кожен символ y k ∈Y замінюється відповідним набором (а i , b j , ϕ k , d n ). Властивості І-автоматів. Продуктивність М-автомата має мінімальне значення, яке до- рівнює одній МО за такт. У М-автоматі, у по- рівнянні з I-автоматом, швидкодія відрізня- ється вкрай незначно, а витрати устаткування менші, оскільки кожна КС ϕ k ∈Ф використо- вується для виконання всіх еквівалентних MO з множини Y. IМ-автомати та їх синтез. Класи I- та М-автоматів володіють діаметрально проти- лежними властивостями. Слід очікувати, що між цими двома класами ОА існують ОА з про- 18 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко міжними властивостями. Один з варіантів та- ких ОА утворює клас IM-автоматів, які мають досить високу продуктивність при помірних витратах устаткування. Для виконання МО в IM-автоматах можуть використовуватись пара- лельні й послідовні КС, що породжують струк- тури, які називають, відповідно, IM-автоматами з паралельною і послідовною КЧ. IM-автомат з паралельною КЧ можна розгля- дати як композицію з В (1<В<N) М-автоматів, що мають спільну пам’ять s 1 , ..., s N . Тому син- тез IM-автоматів з паралельною КЧ зводиться до розбиття множини MO Y на В підмножин Y 1 , ... ..., Y B і синтезу ВМ-автоматів, які реалізу- ють зазначені підмножини MO. В одному такті автомат може виконувати до В МО включно, що ініціюються набором керуючих сигналів, кількість яких залежить як від величини В, так і характеру МО, і тому може змінюватись у до- сить широких межах. Величина В визначається вимогами до швидкодії ОП, насамперед, обме- женням на час виконання операцій і затратами устаткування. Принцип послідовної організації КЧ OA призводить до структур ОА, у яких, для при- кладу, КЧ складається з трьох КС Ф 1 , Ф 2 , Ф 3 , що реалізують операції з множин {f k }, {g l }, {h m } відповідно (при використанні таких ОА як ОА процесорів КС Ф 1 , Ф 2 , Ф 3 , зазвичай, реа- лізують функції формувача, суматора та зсу- вача кодів відповідно [18]). Для нашого при- кладу ОА за один такт реалізує перетворення s n := h m (g l (s i , f k (s j ))), еквівалентне трьом послі- довно виконуваним MO f k , g l , h m над словами s i , s j з метою обчислення слова s n . Це перетворен- ня ініціюється набором сигналів (a i , b j , f k , g l , h m , d n ). При цьому під впливом сигналів a i і b j , які ініціюють передачі A 1 :=s i і A 2 : = s j , слова s i і s j "вибираються" на входи A 1 і A 2 ; сигнали f k , g l , h m , які ініціюють перетворення: A 3 := f k (A 2 ), A 4 := g l (A 1 , A 3 ), R := h m (A 4 ), де A 3 , A 4 , R — допоміж- ні змінні, "налаштовують" КC Ф 1 , Ф 2 , Ф 3 на ви- конання необхідних MO; сигнал d n ініціює за- пис s n := R результату R в пам’ять ОА. За ра- хунок цього максимальна продуктивність IM- автомата з даною структурою в три рази пере- вищує продуктивність М-автомата. Синтез IM-автомата з послідовною КЧ здій- снюється на основі МПР шляхом подання послідовностей МО yα1 , …, yαr ∈Y у формі вира- зів s n := h m (g l (s i ,f k (s j ))). Для цього МПР ділиться на лінійні ділянки (ЛД), що складаються з по- слідовності операторів О 1 , ..., О r . ЛД класифіку- ються за рангами r = 1, ..., Т. До рангу r відно- ситься ЛД, що складається з r операторів О 1 , ..., О r . В результаті функція ОА подається множинами L 1 , ..., L R ЛД. Потім визначається множина виразів, по- роджуваних цими ЛД. ЛД першого рангу L 1 відповідають МО y а1 , …, y аr ∈Y. Вирази, що на- лежать до ЛД Оγ1 , ..., Оγr рангу r = 2, ..., Т, зна- ходяться в такий спосіб. Серед MO, що вхо- дять до складу операторів ЛД, виділяються MO y b1 , ..., y bt , пов’язані з обчисленням одного і того ж слова s n . Шляхом послідовних підста- новок виразів y b1 →y b2 →...→y bt формується MO s n := ϕ m (s in ,...,s im ), яка еквівалентна послідовнос- ті MO y b1 , y b2 , ..., y bt . MO y b1 , y b2 , ..., y bt виключа- ються з ЛД, і процес породження виразів виду s n := h m (g l (s i , f k (s j ))) повторюється для решти MO лінійної дільники. Множина виразів M r , що породжуються ЛД L r рангу r, визначається шляхом об’єднання виразів M ir (i=1, ..., r), що породжуються окре- мими ЛД. Множина виразів M, що породжу- ються МПР, визначається шляхом об’єднання виразів M r (r=1, ..., Т). Множину М можна розглядати як множину MO, реалізація яких покладається на OA. Застосуванням алгорит- му синтезу М-автоматів до множини MO М визначається набір операторів A 1 := s i , A 2 := s j , A3 := f k (A 2 ), A 4 :=g l (A 1 ,A 3 ), R := h m (A 4 ), s n := R, що реалізуються схемами вибірки операндів A 1 , A 2 , КЧ і схемою запису результату R в регістри s1, ..., s N . За набором операторів будується структурна схема IM-автомата. Кількість рів- нів в КЧ ОА визначається максимальним числом дій в двійкових виразах М. Властивості ІМ-автоматів. Структурна організація IM-автоматів з паралельною КЧ добре пристосована для реалізації МПР, у яких велике число операторів містять декілька сумісних МО, а лінійні ділянки не містять МО, пов’язані з обчисленням одного слова. Така ISSN 2706-8145, Control systems and computers, 2020, № 1 19 Принцип мікропрограмного керування та автоматизація проектування структура вносить деякі обмеження на суміс- ність МО і, разом з цим, забезпечує виконання за такт більше однієї МО функціональної МПР. Максимальна продуктивність IM-автомата з В паралельними KC (1<В<N), дорівнює В MO за такт і зростає зі збільшенням числа KC. IM-автомати з послідовною КЧ доцільно застосовувати для реалізації МПР, у яких при- сутні багаторазово виконувані послідовнос- ті МО, що забезпечують обчислення одного слова s n ∈S. Такі послідовності найбільш легко виявляються на лінійних ділянках МПР. Висновки У першій частині роботи здійснюється ана- ліз задачі проектування ОП, деяких основних методів її вирішення, проблем, що виникають при цьому, і підходів до їх подолання. Аналіз стосується, насамперед, функцій, реалізація яких покладається на ОП, і лише частково, на змістовному рівні (неформально), торкається як форми, у якій ці функції задаються, так і техніки виконання їх (цих функцій) оптимізу- ючих перетворень. З урахуванням застережень, здійснених на етапі аналізу, формулюється процедура визна- чення структури (архітектури) ОП і порядку його функціонування, яка базується на прин- ципі мікропрограмного керування. Виявля- ється, точка зору на процес функціонування ОП як процес реалізації принципу мікропро- грамного керування є ефективною (резуль- тативною) не лише з практичної точки зору, але й теоретичної, бо дозволяє формалізувати процес проектування ОП. Цю формалізацію здійснив В.М.Глушков, який як узагальнену модель ОП запропонував використовувати поняття дискретного пере- творювача інформації (композиції зі зворотним зв’язком двох автоматів – керуючого і опера- ційного, яким відповідають, як правило, авто- мати Мілі і Мура), а як формальні засоби, що описують “програми” обробки даних в ОП, – апарат систем алгоритмічних алгебр. Зазна- чимо, даний підхід носить загальний характер і може бути використаний не лише в моделях однопроцесорних обчислювальних систем, але й у тих випадках, коли ОП є багатопроце- сорним комплексом. У другій частині роботи буде показано, що цей підхід дозволяє не ли- ше з єдиних позицій підійти до вирішення ба- гатоаспектних проблем, виявлених у процесі аналізу задачі проектування ОП, але й авто- матизувати процедуру синтезу ОП потрібної якості на базі запропонованого варіанту (одно- го із можливих) інструментального засобу. ЛІТЕРАТУРА 1. Глушков В.М. Синтез цифровых автоматов. М.: Физматгиз., 1962. 476 с. 2. Глушков В.М. Теория автоматов и вопросы проектирования структур цифровых машин. Кибернетика. 1965. № 1. С. 3–11. 3. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. Кибернетика. 1965. №5. С. 1–10. 4. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей. Избранные вопросы алгебры и логики. Новосибирск: Наука, 1973. С. 5–40. 5. Капитонова Ю.В., Летичевский А.А. Математическая теория проектирования вычислительных систем. М.: Наука, 1988. 295 с. 6. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л. Алгебра. Языки. Программирование. 3-е изд., пераб. и доп. Киев: Наук. думка, 1989. 376 с. 7. Анисимов А.В. Рекурсивные преобразователи информации. Киев: Вища шк., 1987. 231 с. 8. Bauer F.L., Wossner H. Algorithmische sprache und programmentwicklung. Berlin ets.: Springer Verlag, 1981. 513 p. 9. Ершов А.П. Трансформационная машина: тема и вариации Проблемы теоретического и системного программирования. Но- восибирск. НГУ, 1979. С. 5–45. 10. Петрушенко А.Н. О диалоговых вычислениях в алгоритмических алгебрах. Кибернетика. 1990. №1. С. 13–20. 11. Петрушенко А.Н. Об одном подходе к проблеме автоматизации оптимизирующих преобразований алгоритмов и программ. Кибернетика и системный анализ. 1991. №5. С. 127–136. 12. Петрушенко А.Н. Об одном подходе к решению проблемы общения человека с вычислительной системой на естественном языке. Проблемы программирования: Сб. науч. трудов. вып. 3. 1998. С. 65–72. 20 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.М. Петрушенко 13. Петрушенко А.Н., Хохлов В.А. Об использовании естественного языка для представления абстрактных типов данных и по- лиморфизма. Проблемы программирования. 1999. №1. С. 76–83. 14. Петрушенко А.Н., Хохлов В.А., Ткачев В.А., Шепетухин Е.С. Диалоговая трансформационная машина: некоторые функциональные возможности. Проблемы программирования. 2000. № 1–2 (Спец. выпуск). С. 323–334. 15. Петрушенко А.М., Хохлов В.А. Концепція діалогових обчислень та деякі проблеми автоматизації програмування. Проблемы программирования. 2004. № 2–3 (Спец. выпуск). С. 37–47. 16. Самофалов К.Г., Корнейчук В.Н., Тарасенко В.П. Цифровые ЭВМ. К.: Вища шк., 1989. 423 с. 17. Самофалов К.Г., Корнейчук В.Н., Тарасенко В.П., Жабин В.Н. Цифровые ЭВМ. Практикум. К.: Вища шк., 1990. 215с. 18. Майоров С.А., Новиков Г.И. Структура электронных вычислительных машин. Л.: Машиностроение, 1979. 384 с 19. Баранов С.И. Синтез микропрограммных автоматов. Л.: Энергия, 1979. 232с. 20. Калужнин Л.А. Об алгоритмизиции математических задач. Проблемы кибернетики. Выл. 2. М.: Физматгиз, 1959. С. 51–67. 21. Ляпунов А. А. О логических схемах программ. Проблемы кибернетики. Вып. 1, М.: Физматгиз, 1958. С. 46–74. 22. Янов Ю.И. О логических схемах алгоритмов. Проблемы кибернетики. Вып. 1. М.: Физматгиз, 1958. С. 75–127. 23. Яблонский С.В. Основные понятия кибернетики. Проблемы кибернетики. Вып. 2. М.: Физматгиз, 1959. С. 7–38. 24. Ершов А.П. Операторные алгоритмы. 3 (об операторных схемах Янова). Проблемы кибернетики. Вып. 20. М.: Физматгиз, 1968. С. 181–200. 25. Системы компьютерной алгебры семейства АНАЛИТИК. Теория. Реализация. Применение. К., 2010. 762 с. 26. Разевиг В.Д. Применение программ PCAD и PSpise для схемотехнического моделирования на ПЭВМ: В 4 выпусках. Вып. 1: Общие сведения. Графический ввод схем. М.: Радио и связь, 1992. 72 с. Надійшла 16.10.2019 REFERENCES 1. Glushkov, V.M., 1962. Sintez tsifrovykh avtomatov. M.: Fizmatgiz. 476 p. (In Russian). 2. Glushkov, V.M., 1965. "Teoriya avtomatov i voprosy proyektirovaniya struktur tsifrovykh mashin", Kibernetika, 1, pp. 3–11. (In Russian). 3. Glushkov, V.M., 1965. "Teoriya avtomatov i formalnyye preobrazovaniya mikroprogramm". Kibernetika, 5, pp. 1–10. (In Russian). 4. Glushkov, V.M., Letichevskiy, A.A., 1973. "Teoriya diskretnykh preobrazovateley". Izbrannyye voprosy algebry i logiki. Novosibirsk: Nauka, pp. 5–40. (In Russian). 5. Kapitonova, Yu.V., Letichevskiy, A.A., 1988. Matematicheskaya teoriya proyektirovaniya vychislitelnykh sistem. M.: Nauka, 295 p. (In Russian). 6. Glushkov, V.M., Tseytlin, G.Ye., Yushchenko, Ye.L., 1989. Yazyki. Programmirovaniye. 3-ye izd., perab. i dop. Kyiv: Nauk. dumka, 376 p. (In Russian). 7. Anisimov, A.V., 1987. Rekursivnyye preobrazovateli informatsii. Kyiv: Vishcha shk., 231 p. (In Russian). 8. Bauer, F.L., Wossner, H., 1981. Algorithmische sprache und programmentwicklung. Berlin: Springer Verlag, 513 p. 9. Yershov, A.P., 1979. "Transformatsionnaya mashina: tema i variatsii". Problemy teoreticheskogo i sistemnogo programmirovaniya. Novosibirsk, NGU, pp. 5–45. (In Russian). 10. Petrushenko, A.N., 1990. "O dialogovykh vychisleniyakh v algoritmicheskikh algebrakh". Kibernetika, 1, pp. 13–20. (In Russian). 11. Petrushenko, A.N., 1991. "Ob odnom podkhode k probleme avtomatizatsii optimiziruyushchikh preobrazovaniy algoritmov i programm". Kibernetika i sistemnyy analiz, 5, pp. 127–136. (In Russian). 12. Petrushenko, A.N., 1998. "Ob odnom podkhode k resheniyu problemy obshcheniya cheloveka s vychislitelnoy sistemoy na yestestvennom yazyke". Problemy programmirovaniya: Sb. nauch. trudov, 3, pp. 65–72. (In Russian). 13. Petrushenko, A.N., Khokhlov, V.A., 1999. "Ob ispolzovanii yestestvennogo yazyka dlya predstavleniya abstraktnykh tipov dannykh i polimorfizma". Problemy programmirovaniya, 1, pp. 76–83. (In Russian). 14. Petrushenko, A.N., Khokhlov, V.A., Tkachev, V.A., Shepetukhin, Ye.S., 2000. "Dialogovaya transformatsionnaya mashina: nekotoryye funktsionalnyye vozmozhnosti". Problemy programmirovaniya, 1–2 (Spets. vypusk), pp. 323–334. (In Russian). 15. Petrushenko A.M., Khokhlov V.A., 2004. Kontseptsiya dialohovykh obchyslen ta deyaki problemy avtomatyzatsiyi prohramuvannya. Problemy prohrammyrovanyya, 2–3 (Spets. vypusk), pp. 37–47. (In Ukrainian). 16. Samofalov, K.G., Korneychuk, V.N., Tarasenko, V.P., 1989. Tsifrovyye EVM. K.: Vishcha shk., 423 p. (In Russian). 17. Samofalov, K.G., Korneychuk, V.N., Tarasenko, V.P., Zhabin, V.N., 1990. Tsifrovyye EVM. Praktikum. K.: Vish. shk., 215 p. (In Russian). 18. Mayorov, A., Novikov, G.I., 1979. Struktura elektronnykh vychislitelnykh mashin. L.: Mashinostroyeniye. 384 p. (In Russian). 19. Baranov, S.I., 1979. Sintez mikroprogrammnykh avtomatov. L.: Energiya. 232 p. (In Russian). ISSN 2706-8145, Control systems and computers, 2020, № 1 21 Принцип мікропрограмного керування та автоматизація проектування 20. Kaluzhnin, L.A., 1959. "Ob algoritmizitsii matematicheskikh zadach". Problemy kibernetiki., 2, M.: Fizmatgiz, pp. 51–67. (In Russian). 21. Lyapunov, A.A., 1958. "O logicheskikh skhemakh programm". Problemy kibernetiki., 1, M.: Fizmatgiz, pp. 46–74. (In Russian). 22. Yanov, Yu.I., 1958. "O logicheskikh skhemakh algoritmov". Problemy kibernetiki. M.: Fizmatgiz, 1, pp. 75–127. (In Russian). 23. Yablonski,y S.V., 1959. "Osnovnyye ponyatiya kibernetiki". Problemy kibernetiki. M.: Fizmatgiz, 1, pp. 7–38. (In Russian). 24. Yershov, A.P., 1968. "Operatornyye algoritmy". 3 (ob operatornykh skhemakh Yanova). Problemy kibernetiki. M.: Fizmatgiz, 2, pp. 181–200. (In Russian). 25. Sistemy kompyuternoy algebry semeystva ANALITIK. Teoriya. Primeneniye. K., 2010. 762 p. (In Russian). 26. Razevig, V.D., 1992. Primeneniye programm PCAD i PSpise dlya skhemotekhnicheskogo modelirovaniya na PEVM: V 4 vyp. 1: Obshchiye svedeniya. Graficheskiy vvod skhem. M.: Radio i svyaz. 72 p. (In Russian). Received 16.10.2019 A.M. Petruchenko, PhD in Phys.-Math Sciences, Associate Professor, Taras Shevchenko National University of Kyiv, 03022, Kyiv, Glushkov ave., 4D, Ukraine, anatoly@mytaskhelper.com THE PRINCIPLE OF FIRMWARE CONTROL AND DESIGN AUTOMATION OF OPERATING DEVICES. I Introduction. Promising areas of research that are developing both in Ukraine and abroad include the so-called transformational synthesis methods. According to these methods, a computing system is obtained by phasing the initial description of the system (setting the task) according to the rules,which is knowledge about the problem being solved. In this area of research, two interrelated directions can be distinguished – the theoretical and applied. The theoretical direction requires, in particular, the presentation of various computational models that describe particular parts of computing systems, and the study of basic transformations in these models. The applied direction is associated with the creation of a transformation machine, the commands for which are basic transformations, and the data are expres- sions in the language over which these transformations are given. The Ukrainian Algebra-Cybernetic School researches the computational model, which is based on the concept of a discrete information converter. Representation of the computing process in this form allowed V.M. Glushkov and his students to create a new theoretical direction in the applied theory of algorithms – the algebra of algorithms. A characteristic feature of this direction is the commonality of mathematical models and methods for designing programmes and equipment. The apparatus of algebra of algorithms is the basis of the dialogue transformation machine – the main object of this article. The purpose is to demonstrate the inextricable link between the fundamental concepts of the general theory of computer systems design and practical methods of designing software and hardware of computer technology, as well as new technological capabilities that arise when using the apparatus of algebra of algorithms in the process of designing programmes and equipment using an interactive transformational machine. Methods. When implementing the tools (conversational transformation machine) and the synthesis algorithm of operating devices, we used the algebraic-grammatical method of representing knowledge, the method of constructing operating devices based on the principle of microprogram control, the methods of abstract and structural theory of automata, the methods of algebra of algorithms, etc. Results. Synthesis methods for operating devices developed for the language of graph diagrams of algorithms and the language of logi- cal diagrams of algorithms are extended to the language CAA\D – the input language of the dialogue transformation machine. Based on the dialogue transformational machine, a toolkit has been developed that embodies the V.M.Glushkov mathematical model and allows the complex automation of the operating devices: from setting the task to obtaining a sketch of the printed circuit board. Conclusions. The integral algebraic-grammatical apparatus underlying the dialogue transformational machine combines algebraic, logi- cal, and grammatical formalisms and is focused on the multi-level structural design of classes of algorithms and associated programmes (serial and parallel) and hardware. It is characterized by the analytical style of the specifications of programmes and equipment, focused on their optimizing transformations in order to achieve the necessary quality indicators. At the same time, using the CAA\Dv language as the input language of the dialog transformational machine allows you to increase the "intelligence" of the computer to a level that provides direct communication with it, in particular, inexperienced in programming users who are specialists in specific areas. Keywords: a principle of microprogram control, discrete information converter, operating device, algebra of algorithms, algebraic-grammatical method of knowledge representation, interactive transformation machine. А.М. Петрушенко 22 ISSN 2706-8145, Системи керування та комп'ютери, 2020, № 1 А.Н. Петрушенко, кандидат физ.-мат. наук, доцент, Киевский национальный университет имени Тараса Шевченко, 03022, г. Киев, просп. Академика Глушкова, 4Д, факультет компьютерных наук и кибернетики, anatoly@mytaskhelper.com ПРИНЦИП МИКРОПРОГРАММНОГО УПРАВЛЕНИЯ И АВТОМАТИЗАЦИЯ ПРОЕКТИРОВАНИЯ ОПЕРАЦИОННЫХ УСТРОЙСТВ. I Введение. Одной из определяющих тенденций развития науки в целом является ее математизация. Не являются исключением и науки, которые исследуют компьютеры, принципы их строения и функционирования. Создание компьютеров и универсальных алгоритмических языков приводит к изменению акцентов при оценке значения математизации — ее уровень является теперь не только одним из главных показателей уровня научности, систем- ности представлений о тех или иных предметных областях, но и определяет возможности автоматизации процес- сов, протекающих в этих областях. Цель статьи. Компьютеры изменяют не только отношение к математизации, но и ее характер, ее сущность. В частности, возник метод научных исследований – имитационное моделирование, который соединил в себе черты классических дедуктивных и экспериментальных методов, присущих математике и физике соответственно. Но такой метод проведения эксперимента еще не есть настоящая математизация — для ее достижения необходимы алгебры алгоритмов. Именно в существовании такой алгебры и состоит разница между настоящей математиза- цией и простой формализацией знаний. Разработка такого аппарата связана с работами В.М.Глушкова, который ввел понятие дискретного преобразователя информации и системы алгоритмических (их сначала называли микропрограммными) алгебр. По Глушкову, каждая модель математизации должна состоять: из области объекта, которая должна быть изучена формальными математическими методами; из формального языка, подходящего для более или менее адекватного описания этого объекта; формальной модели вывода, включающей как общие средства логического вывода, так и средства вывода, специально разработанные для этого языка (алгебру данного языка). Формальный язык вместе с формальной моделью вывода образуют формальную теорию. Чтобы эта теория стала настоящим дедуктивным аппаратом, она должна быть воплощена в инструменте вывода, который состав- ляет четвертую часть модели математизации. В настоящее время известны два типа таких инструментов: челове- ческий мозг и компьютер. Формальная теория, усвоенная мозгом или компьютером, названа системой познания. Легко видеть, что реализация идей В.М.Глушкова в полном объеме сопряжена с корректировкой целей матема- тизации – одной из главных целей которой является повышение интеллекта компьютера до уровня, который обеспечивает непосредственное общение с компьютером даже несведущих в программировании пользовате- лей – специалистов в конкретных предметных областях. Цель данной статьи — демонстрация одного из возможных подходов к реализации инструментария, воплощающего модель математизации В.М. Глушкова и возможностей данного инструментария на примере синтеза операционных устройств. Методы. При реализации инструментария и алгоритма синтеза операционных устройств использовался алгебро-грамматический метод представления знаний, метод построения операционных устройств на базе прин- ципа микропрограммного управления, методы абстрактной и структурной теории автоматов, методы алгебры алгоритмов и т.д. Результат. Разработан инструментарий, воплощающий модель математизации В.М. Глушкова, позволяющий осуществить комплексную автоматизацию проектирования операционных устройств. Выводы. Необходима работа по приведению инструментария к товарному виду. Ключевые слова: принцип микропрограммного управления, дискретный преобразователь информации, операционное устройство, алгебра алгоритмов, алгебро-грамматический метод представления знаний, диалоговая трансформаци- онная машина.
id	nasplib_isofts_kiev_ua-123456789-181114
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	2706-8145
language	Ukrainian
last_indexed	2025-11-30T17:51:41Z
publishDate	2020
publisher	Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
record_format	dspace
spelling	Петрушенко, А.М. 2021-11-02T16:04:43Z 2021-11-02T16:04:43Z 2020 Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв. І / А. М. Петрушенко // Control systems & computers. — 2020. — № 1. — С. 3-22. — Бібліогр.: 26 назв. — укр. 2706-8145 DOI https://doi.org/10.15407/usim.2020.01.003 https://nasplib.isofts.kiev.ua/handle/123456789/181114 681.3.006 Розглядається один із можливих підходів до вирішення на базі принципу мікропрограмного керування проблеми комплексної – від постановки задачі до отримання ескізу друкованої плати – автоматизації процесу розробки операційних пристроїв. Підхід демонструється на прикладі синтезу в діалоговій трансформаційній машині – інструментарію алгебро-граматичних методів подання знань у різноманітних предметних областях – керуючого автомату операційного пристрою, що реалізує операцію додавання. Цель данной статьи — демонстрация одного из возможных подходов к реализации инструментария, воплощающего модель математизации В.М. Глушкова и возможностей данного инструментария на примере синтеза операционных устройств. Методы. При реализации инструментария и алгоритма синтеза операционных устройств использовался алгебро-грамматический метод представления знаний, метод построения операционных устройств на базе принципа микропрограммного управления, методы абстрактной и структурной теории автоматов, методы алгебры алгоритмов и т.д. Результат. Разработан инструментарий, воплощающий модель математизации В.М. Глушкова, позволяющий осуществить комплексную автоматизацию проектирования операционных устройств. The purpose is to demonstrate the inextricable link between the fundamental concepts of the general theory of computer systems design and practical methods of designing software and hardware of computer technology, as well as new technological capabilities that arise when using the apparatus of algebra of algorithms in the process of designing programmes and equipment using an interactive transformational machine. Methods. When implementing the tools (conversational transformation machine) and the synthesis algorithm of operating devices, we used the algebraic-grammatical method of representing knowledge, the method of constructing operating devices based on the principle of microprogram control, the methods of abstract and structural theory of automata, the methods of algebra of algorithms, etc. Results. Synthesis methods for operating devices developed for the language of graph diagrams of algorithms and the language of logical diagrams of algorithms are extended to the language CAA\D – the input language of the dialogue transformation machine. Based on the dialogue transformational machine, a toolkit has been developed that embodies the V.M.Glushkov mathematical model and allows the complex automation of the operating devices: from setting the task to obtaining a sketch of the printed circuit board uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Control systems & computers Fundamental Problems in Computer Science Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв. Принцип микропрограммного управления и автоматизация проектирования операционных устройств. I The Principle of Firmware Control and Design Automation of Operating Devices. I Article published earlier
spellingShingle	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв. Петрушенко, А.М. Fundamental Problems in Computer Science
title	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.
title_alt	Принцип микропрограммного управления и автоматизация проектирования операционных устройств. I The Principle of Firmware Control and Design Automation of Operating Devices. I
title_full	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.
title_fullStr	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.
title_full_unstemmed	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.
title_short	Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.
title_sort	принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.
topic	Fundamental Problems in Computer Science
topic_facet	Fundamental Problems in Computer Science
url	https://nasplib.isofts.kiev.ua/handle/123456789/181114
work_keys_str_mv	AT petrušenkoam principmíkroprogramnogokeruvannâtaavtomatizacíâproektuvannâoperacíinihpristroív AT petrušenkoam principmikroprogrammnogoupravleniâiavtomatizaciâproektirovaniâoperacionnyhustroistvi AT petrušenkoam theprincipleoffirmwarecontrolanddesignautomationofoperatingdevicesi

Принцип мікропрограмного керування та автоматизація проектування операційних пристроїв.

Institution

Ähnliche Einträge