Машина обробки знань

Реферат: Машина обробки знань належить до області обчислювальної техніки та може бути використана при побудові систем, заснованих на знаннях (knowledge-based systems). Машина обробки знань містить: головний комп'ютер, першу та другу оперативні пам'яті, процесор термінальних програм у складі першого регістра даних, арифметико-логічного блока, робочої пам'яті, регістра-лічильника координат вхідного масиву, регістра-лічильника координат вихідного масиву, мультиплексора, першого блока керування та першого блока вводу-виводу, другий блок вводу-виводу та процесор обробки знань у складі третього блока вводу-виводу, другого блока керування, дешифратора команд, другого регістра даних, буферного регістра, блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина та блока ознак інтерпретації, регістра адреси та другого регістра даних. За допомогою запропонованої машини досягається: знання зберігаються у вигляді множини визначень термінів та відокремлено від алгоритму їхньої обробки; алгоритм роботи пристрою апаратно "зашитий" у блок керування; знання, що містяться у базі знань, зберігаються у вигляді ієрархічної структури, яка значно підвищує ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; зберігається структура логічного виводу, яка в подальшому може бути використана для пояснення ходу логічного виводу або породження нової структури даних; надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури даних, які містять визначення з використанням відношень альтернативи, послідовності та ітерації. UA 109712 C2 (12) UA 109712 C2 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Даний винахід належить до області обчислювальної техніки та може бути використаний при побудові систем, основаних на знаннях (knowledge-based systems). Відомий пристрій [SU1455345, 30.01.1989, Устройство для реализации нормальных алгорифмов Маркова// Довгань В.М, Кореневский Н.А., Бойко Ю.Л., Плотников В.В.], який призначено для обробки інформаційних потоків та масивів даних текстового та числового характерів згідно із заданими нормальними алгорифмами та складається із: блока організації підставлення, комутатора, блока пам'яті слова, блока регістрів слова, дешифратора межі слова, блока пошуку входження, блока керування. Більш швидкодіючим є пристрій [SU1635192, 15.03.91, Устройство для реализации подстановок слов// Довгаль В.М., Корольков О.Ф., Керекеша В.В., Старков Ф.А., Шевелев С.С], який дозволяє оброблювати дані символьного та числового типів за допомогою нормальних алгорифмів, які складаються виключно із формул підставлення з двобуквеними лівими та правими частинами, при цьому всі ліві частини (антецеденти) формул паралельно порівнюються із двобуквеним початковим словом (ситуацією) за допомогою асоціативного вузла порівняння. Відомий пристрій складається із: блока пам'яті слів, блока пам'яті входжень, блока пам'яті підстановок, вузла зсуву, комутатора, першого вузла контролю оброблюваного слова, вузла порівняння, блока організації підстановки елементів логіки, лічильника та блока керування. Більш досконалим щодо функціональних можливостей є пристрій [RU2039375, 22.06.1992, Устройство для реализации продукций// Довгаль В.М., Старков Ф.А., Керекеша В.В., Шевелев С.С, Леонов Е.И.], який складається із: блока пам'яті слів, вузла порівняння, блока керування, регістра символу ситуації, регістра маркера ситуації, блока тегів, блока ідентифікації активної продукції та регістра зсуву показника зчитування. Блоки сполучені між собою за допомогою окремих шин та працюють під керуванням блока керування. Серед головних особливостей відомого пристрою (RU2039375, 22.06.1992) слід відмітити те, що він допускає обробку продукцій нефіксованої довжини. Головним недоліком даного пристрою є те, що продукції у блоці пам'яті слів зберігаються у вигляді символьного масиву нефіксованої довжини. Це призводить до неефективного використання пам'яті слів та до необхідності посимвольної перевірки в процесі співставлення антецедентів. Найближчим до запропонованого є пристрій [US Patent, number 5218669 June 8, 1993, VLSI hardware implemented rule-based expert system apparatus and method (апаратно реалізована система обробки продукційних правил)// Hideaki Kobayashi, Masahiro Shindo], вибраний за прототип. Пристрій являє собою співпроцесор та містить: блок керування, блок вводу-виводу, робочу пам'ять, арифметико-логічний блок та оперативну пам'ять. Блок вводу-виводу призначений для забезпечення обміну даними та командами між процесором продукційних правил та головним комп'ютером. Процесор продукційних правил у складі блока керування, арифметико-логічного блока, робочої пам'яті, регістра даних та регістра-лічильника координат вхідного масиву призначений для ефективної обробки продукційних правил та реалізований у формі інтегральної мікросхеми. Арифметико-логічний блок призначений для виконання команд: порівняння над даними (=, , , =, NOT, AND, OR); переміщення даних; логічного зсуву та переходу. Блок керування керує роботою всіх модулів процесора продукційних правил, а також процесом обміну даними між оперативною пам'яттю правил та блоком вводу-виводу. Оперативна пам'ять містить базу знань із набору продукційних правил у формі команд фіксованої довжини. Кожна команда містить такі поля: "тип команди", "прапор" (умова (соndition)/дія (action)) та два операнди. Якщо поточна команда у полі "прапор" містить умову, то відбувається порівняння операндів у залежності від коду поля "тип команди". Якщо команда характеризується як дія, то над поточними операндами виконується дія, зазначена у полі "тип команди". Серед недоліків прототипу можна вказати наступні. 1) Необхідність виконання великої кількості обчислень у процесі пошуку активної продукції при співставленні антецедентів. Це пов'язано із тим, що між продукційними правилами, які містяться в оперативній пам'яті у вигляді команд спеціального формату, відсутній ієрархічний зв'язок. 2) Відсутність механізму пояснення логічного виводу. 3) Відсутність ефективного представлення у пам'яті ітераційних та рекурсивних структур. Спільними ознаками прототипу та пропонованої моделі є головний комп'ютер, оперативна пам'ять, перший блок керування, арифметико-логічний блок, робоча пам'ять, перший регістр даних, регістр-лічильник координат вхідного масиву та перший блок вводу-виводу. В основу моделі поставлена задача побудови спеціалізованої машини обробки знань. Будьяка задача, поставлена у вигляді імені функції та значення її аргументу, вирішується виводом рішення у процесі інтерпретації бази знань. 1 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 База знань складається із структури взаємозв'язаних визначень термінів, кожне з яких представляється у формі одного з п'яти фреймів: альтернативи, послідовності, ітерації, текстової константи або терміналу. Усякий фрейм - послідовність слів фіксованої довжини (наприклад, трибайтових), серед яких розрізняється перше слово, а в кожному зі слів - перший байт і наступні. Фрейми текстової константи й термінала - однослівні, ітерації - двослівні, альтернативи й послідовності - багатослівні. Фрейми визначень всіх термінів всякої бази знань розміщено у пам'яті бази знань у вигляді ієрархічної структури, що усуває проблему множини конфліктних правил. Такий принцип організації бази знань дозволяє ефективно зберігати та інтерпретувати ітераційні й рекурсивні структури визначень. Ще однією важливою відмінністю машини обробки знань є те, що структура процесу інтерпретації, процесу виводу рішення зберігається спеціальними засобами ведення сліду. З метою розширення функціональних можливостей інтерпретації рекурсивних, ітераційних та вкладених структур і формування структури виводу рішення задачі у пристрій, що містить головний комп'ютер, першу оперативну пам'ять, перший блок вводу-виводу, перший блок керування, арифметико-логічний блок, робочу пам'ять, перший регістр даних та регістрлічильник координат вхідного масиву, у якому перший вхід-вихід першого блока вводу-виводу підключений до системної шини пристрою, другий вхід-вихід першого блока вводу-виводу підключений до входів-виходів регістра-лічильника координат вхідного масиву, третій вхід-вихід першого блока вводу-виводу разом із входами-виходами арифметико-логічного блока, входомвиходом першого блока керування та першими входами-виходами першого регістра даних, з'єднаного другими входами-виходами з входами-виходами робочої пам'яті, підключений до шини даних, введено регістр-лічильник координат вихідного масиву, мультиплексор, другу оперативну пам'ять, другий блок керування, другий та третій блоки вводу-виводу, дешифратор команд, блоки імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина та ознак інтерпретації, буферний регістр, другий регістр даних та регістр адреси, при цьому четвертий вхід-вихід першого блока вводу-виводу підключено до входіввиходів регістра-лічильника координат вихідного масиву, вихід якого разом із виходом регістралічильника координат вхідного масиву через мультиплексор підключений до адресних входів робочої пам'яті, головний комп'ютер через другий блок вводу-виводу, друга оперативна пам'ять та перший вхід-вихід третього блока вводу-виводу підключені до системної шини пристрою, перший вихід третього блока вводу виводу підключено до першого входу другого блока керування, перший вихід якого підключено до третього входу третього блока вводу-виводу, другий вихід другого блока керування підключено до входу дешифратора команд, вихід якого підключено до перших входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина та ознак інтерпретації, третій вихід другого блока керування підключено до перших входів регістра адреси та другого регістра даних, четвертий вихід другого блока керування підключено до входу керування першої оперативної пам'яті, вихід якої підключено до другого входу третього блока вводу-виводу, до першого входу другого блока керування, до других входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, лічильника магазина та ознак інтерпретації, другий вихід третього блока вводу-виводу підключено до третіх входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина, ознак інтерпретації та до других входів другого регістра даних та регістра адреси, вихід блока імені структури підключено до третього входу другого регістра даних, до четвертого входу блока номера слова фрейму та до четвертого входу блока адреси бази знань, вихід блока номера слова фрейму підключено до четвертих входів другого регістра даних та блока адреси бази знань, чий вихід підключено до четвертого входу блока імені структури, вихід блока координати сліду підключено до третього входу регістра адреси та до четвертого входу блока вершини сліду, вихід якого підключено до п'ятого входу другого регістра даних та до четвертого входу блока координати сліду, вихід блока адреси у вхідному масиві підключено до шостого входу другого регістра даних, вихід блока адреси у вихідному масиві підключено до сьомого входу другого регістра даних, вихід блока ітерації підключено до восьмого входу другого регістра даних та до третього входу буферного регістра, чий другий вхід разом із четвертим входом блока ознак інтерпретації підключено до виходу блока істинності, вихід блока лічильника магазина підключено до четвертого входу регістра адреси, вихід блока ознак інтерпретації підключено до другого входу блока істинності, до першого входу буферного регістра та до дев'ятого входу другого регістра даних, вихід регістра адреси підключено до 2 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 адресного входу першої оперативної пам'яті, вхід даних якої підключено до виходу другого регістра даних, вихід буферного регістра підключено до третього входу третього блока вводувиводу та до другого входу другого блока керування. Відмітними ознаками запропонованої машини обробки знань від відомого прототипу є: 1) модуль розширення функціональності системи реалізовано на базі програмованої логічної інтегральної схеми; 2) знання зберігаються у вигляді множини визначень термінів та відокремлено від алгоритму їх обробки; 3) алгоритм роботи машини обробки знань оптимізовано у відповідності зі встановленими обмеженнями та апаратно "зашитий" у автомат керування по типу Мура; 4) знання, що містяться у базі знань, зберігаються у вигляді ієрархічної структури, яка значно підвищує ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; 5) зберігається структура логічного виводу, яка в подальшому може бути використана для пояснення ходу логічного виводу або породження нової структури даних; 6) надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури даних, які містять визначення з використанням відношень кон'юнкції, диз'юнкції та інверсії. На Фіг. 1 наведено структуру машини обробки знань; на Фіг. 2 наведено структуру блока керування; на Фіг. 3 наведено структуру блоків RDT1 10, Б01 19, Б03 21, Б06 24, Б07 25, БЛМ 28, RAD 30 та RDT2 31; на Фіг. 4 наведено структуру блоків Б 02 20, Б04 22, Б05 23, Б08 26 та Б09 27; на Фіг. 5 наведено структуру блока БOI 29; на Фіг. 6 наведено структуру запису пам'яті магазина та сліду; на Фіг. 7 наведено структуру слова бази знань; на Фіг. 8 наведено структуру байта ознак слова фрейму, на Фіг. 9 наведено структуру шаблонів фреймів; на Фіг. 10 наведено граф алгоритму роботи машини обробки знань. У табл. 1 наведено характеристики блоків, у табл. 2 наведено опис команд другого блока керування 8, у табл. 3 наведено реалізацію базових процедур алгоритму роботи машини. Машина обробки знань (Фіг. 1) складається із головного комп'ютера 1, модуля розширення функціональності 2, процесора обробки знань 3, другого блока вводу-виводу 4, процесора обробки термінальних програм 5, другої оперативної пам'яті 6, що включає системні програми, термінальні програми та словник термінів, третього блока вводу-виводу 7, другого блока керування 8, дешифратора команд 9, першого регістра даних RDT1 10, робочої пам'яті 11, першого блока ввода-виводу 12, регістра-лічильника координат вхідного масиву RCm 13, мультиплексора MX 14, регістра-лічильника координат вихідного масиву RC n 15, першого блока керування 16, арифметико-логічного блока 17, буферного регістра R Б 18, блоків імені структури Б01 19, номера слова фрейму Б02 20, адреси бази знань Б03 21, координати сліду Б04 22, вершини сліду Б05 23, адреси у вхідному масиві Б06 24, адреси у вихідному масиві Б07 25, ітерації Б08 26, істинності Б09 27, лічильника магазина БЛМ 28 та блока ознак інтерпретації БОІ 29, регістра адреси RAD 30, другого регістра даних RDT2 31 та першої оперативної пам'яті 32, що включає пам'яті бази знань, магазина та сліду. Головний комп'ютер 1 призначений для постановки завдання, зчитування результатів роботи модуля розширення функціональності 2 та конфігурації роботи модуля 2. Процесор обробки термінальних програм 5 призначений для взаємодії із головним комп’ютером 1 та виконання термінальних програм на замовлення процесора обробки знань 3. Робота процесора 5 здійснюється згідно з програмою, що міститься у другій оперативній пам'яті 6. Процесор обробки знань 3 розширює набір команд процесора обробки термінальних програм 5 та призначений для швидкої апаратної обробки завдання, що надійшло від головного комп'ютера 1. Головний комп'ютер 1 через другий блок вводу-виводу 4 підключений разом із входамивиходами другої оперативної пам'яті 6 та першими входами-виходами першого 12 і третього 7 блоків вводу-виводу до системної шини пристрою. Другий та четвертий входи-виходи першого блока вводу-виводу 12 підключені до входів-виходів відповідно регістра-лічильника RCm 13 координат вхідного масиву та регістра-лічильника RCn 15 координат вихідного масиву, чиї виходи через мультиплексор MX 14 підключені до адресних входів робочої пам'яті 11. Третій вхід-вихід першого блока вводу-виводу 12 разом із входами-виходами арифметико-логічного блока АЛБ 17, першого блока керування 16 та першими входами-виходами першого регістра даних RDT1 10, з'єднаного другими входами-виходами з входами-виходами робочої пам'яті 11, підключений до шини даних. Перший вихід третього блока вводу-виводу 7 підключено до першого входу другого блока керування 8, перший вихід якого підключено до третього входу третього блока вводу-виводу 7. Другий вихід другого блока керування 8 підключено до входу дешифратора команд 9, вихід якого підключено до перших входів блоків імені структури 19, номера слова фрейму 20, адреси бази знань 21, координати сліду 22, вершини сліду 23, адреси 3 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 у вхідному масиві 24, адреси у вихідному масиві 25, ітерації 26, істинності 27, лічильника магазина 28 та ознак інтерпретації 29. Третій вихід другого блока керування 8 підключено до перших входів регістра адреси 30 та другого регістра даних 31. Четвертий вихід другого блока керування 8 підключено до входу керування першої оперативної пам'яті 32, вихід якої підключено до другого входу третього блока вводу-виводу 7, до першого входу другого блока керування 8, до других входів блоків імені структури 19, номера слова фрейму 20, адреси бази знань 21, координати сліду 22, вершини сліду 23, адреси у вхідному масиві 24, адреси у вихідному масиві 25, ітерації 26, лічильника магазина 28 та ознак інтерпретації 29. Другий вихід третього блока вводу-виводу 7 підключено до третіх входів блоків імені структури 19, номера слова фрейму 20, адреси бази знань 21, координати сліду 22, вершини сліду 23, адреси у вхідному масиві 24, адреси у вихідному масиві 25, ітерації 26, істинності 27, лічильника магазина 28, ознак інтерпретації 29 та до других входів другогорегістра даних 31 та регістра адреси 30. Вихід блока імені структури 19 підключено до третього входу другого регістра даних 31, до четвертого входу блока номера слова фрейму 20 та до четвертого входу блока адреси бази знань 21. Вихід блока номера слова фрейму 20 підключено до четвертих входів другого регістра даних З1 та блока адреси бази знань 21. Вихід блока адреси бази знань 21 підключено до четвертого входу блока імені структури 19. Вихід блока координати сліду 22 підключено до третього входу регістра адреси 30 та до четвертого входу блока вершини сліду 23. Вихід блока вершини сліду 23 підключено до п'ятого входу другого регістра даних 31 та до четвертого входу блока координати сліду 22. Вихід блока адреси у вхідному масиві 24 підключено до шостого входу другого регістра даних 31. Вихід блока адреси у вихідному масиві 25 підключено до сьомого входу другого регістра даних 31. Вихід блока ітерації 26 підключено до восьмого входу другого регістра даних 31 та до третього входу буферного регістра 18, чий другий вхід разом із четвертим входом блока ознак інтерпретації 29 підключено до виходу блока істинності 27. Вихід блока лічильника магазина 28 підключено до четвертого входу регістра адреси 30. Вихід блока ознак інтерпретації 29 підключено до другого входу блока істинності 27, до першого входу буферного регістра 18 та до дев'ятого входу другого регістра даних 31. Вихід регістра адреси 30 підключено до адресного входу першої оперативної пам'яті 32, вхід даних якої підключено до виходу другого регістра даних 31. Вихід буферного регістра 18 підключено до третього входу третього блока вводу-виводу 7 та до другого входу другого блока керування 8. Детальний опис регістрів блоків, що входять до складу процесора обробки знань 3, наведено у табл. 1. Зовнішні вхідні дані, що надходять від головного комп′ютера 1 через другий блок вводувиводу 4 на входи вузлів та блоків процесора 3, призначені для ініціалізації або модифікації вмісту його регістрів та пам'ятей. Операційна частина процесора 3 виконує команди, набір яких наведено у табл. 2. Множину команд, наведених у табл. 2, можна розділити на 8 груп: а) завантаження даних із Rі до Rj; б) завантаження константи до Ri; в) інкремент даних у Ri та запис їх у Rj; г) декремент даних у Ri та запис їх у Rj; д) завантаження зовнішніх даних у Ri; e) завантаження даних із першої оперативної пам'яті 32 до Ri; ж) команди для роботи із першою оперативною пам'яттю 32; з) команди запиту на обробку термінальних програм. Розглянемо принцип роботи пристрою: 1. Ініціалізація процесора обробки знань 3. Відбувається ззовні за допомогою процесора обробки термінальних програм 5 та третього блока вводу-виводу 7. Залежно від зовнішніх команд, що надійшли від процесора обробки термінальних програм 5, у регістри процесора 3 відбувається завантаження початкових даних. Після завантаження регістрів відбувається ініціалізація першої оперативної пам'яті 32. 2. Передача керування роботи. Після завершення етапу ініціалізації виконується передача керування процесор 3, який неперервно працює згідно з закладеним у нього алгоритму. 3. Обробка поставленого завдання. Виконується в процесі зміни станів блока керування 8. Залежно від поточного стану блока керування 8 на його виходи надходять команди, які керують операційною частиною процесора 3, до якого належать дешифратор 9 та регістри й блоки 1831. 3.1. Команда з другого виходу другого блока керування 8 надходить на вхід дешифратора команд 9, який декодує її. Залежно від типу поточної команди виконується модифікація даних, що містяться у регістрах та блоках процесора 3 або передача даних із них до регістрів 30, 31. 4 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Як видно із фіг. 1, із кожним з регістрів та блоків 18-31 з'єднано декілька вхідних шин. Залежно від команди, яка надходить на його вхід керування, може відбуватися або ні запис даних із однієї із цих шин до відповідного регістра чи блока. 3.2. Команда з третього виходу другого блока керування 8 управляє модифікацією даних регістрів адреси і даних 30, 31 першої оперативної пам'яті 32. 3.3. Команда з четвертого виходу блока 8 керування управляє записом та зчитуванням даних першої оперативної пам'яті 32. 3.4. Для виконання термінальних програм процесор 3 за допомогою блока 7 видає завдання процесору 5. Після завершення виконання термінальної програми процесор 5 надсилає процесору 3 по системній шині через третій блок вводу-виводу 7 відповідну команду та результати термінальної програми. 4. Передача результатів роботи. Після завершення обробки поставленого завдання виконується зчитування даних із оперативної пам'яті 32 та передача їх процесору 5 по системній шині через перший 12 та третій 7 блоки вводу-виводу. Блок 8 керування (Фіг. 2) складається із трьох модулів: логіка переходів 33, пам'ять станів 34 та вихідна логіка 35. Блок 8 керування за результатами аналізу кодів на першому, другому та третьому входах формує на своїх першому та другому виходах команди керування блоком вводу-виводу 7 та дешифратором команд 9 відповідно. Логіка переходів 33 визначає наступний стан блока керування 8, що є функцією від поточного стану пам'яті станів 34 та кодів на входах блока керування 8. Пам'ять станів 34 складається із набору елементів пам'яті та призначена для збереження поточного стану блока 8 керування. Команди на виходах блока керування 8 визначаються вихідною логікою 35 та є функцією від поточного стану пам'яті станів 34. Структуру багатовхідних блоків RБ, Б01 Б03, RDT, Б06, Б07, БЛМ зображено на Фіг. 3 у складі відповідних мультиплексора MXі та регістра Rі. Вхід мультиплексора MXі з'єднаний із n шинами вхідних даних та шиною команд. На входи регістра R i надходять дані з виходу MXi та відповідна команда. Під керуванням відповідної команди відбувається комутація входів мультиплексора і запис даних у регістр Ri. Структуру блоків Б02, Б04, Б05, Б08 та Б09 зображено на Фіг. 4 у складі мультиплексора МХ i арифметико-логічного пристрою, інвертора та регістра Ri. Інформаційні входи мультиплексора MXi з'єднано із шинами вхідних даних, інверсії вхідних даних та виходами арифметико-логічного пристрою, а виходи підключено до входів регістра R i. Команди управляють комутацією інформаційних входів мультиплексора MXi та записом даних з його виходів у регістр Ri. Структуру блока ознак інтерпретації БOI зображено на Фіг. 5, який складається із мультиплексора MXi, регістра ознак сліду (R10), регістра ознак породження (R11), регістра Інв_1 (R12), регістра Інв_2 (R13), регістра типу фрейму (R14), регістра ознаки останнього елемента (R15). Входи мультиплексора MXi з'єднані із двома шинами вхідних даних та шиною команд. Входи регістрів Ri (R10-R15) з'єднані із виходами MXi та шиною команд. При надходженні відповідної команди виконується комутація вхідних даних мультиплексора MX i та їх запис у відповідний регістр Ri. В першій оперативній пам'яті 32 розрізняються: пам'ять бази знань (ПБЗ), пам'ять сліду (ПС) та пам'ять магазина (ПМ), які розташовані в ній послідовно. База знань (БЗ) представляється у формі інформаційної структури множини визначень понять (термінальні - константи чи іменовані процедури, або не термінальні), зв'язаних відношеннями альтернативи, послідовності чи ітерації. Пам'ять бази знань зберігає знання у машинній формі, що складається із множини фреймів, кожний із яких має структуру масиву слів фіксованої довжини (наприклад, 3 байти). Довжина фрейму залежить від типу відношення, яке він описує, та від числа понять у визначальній частині і може складати від одного до деякого скінченного числа слів. Пам'яті сліду та магазина зберігають (у формі Фіг. 6) оперативну інформацію процесу інтерпретації бази знань. Пам'ять сліду зберігає структуру виводу рішення задачі. Вона може бути використана для пояснення процесу рішення задачі або при породженні наслідку. Пам'ять магазина тимчасово зберігає проміжні дані процесу виводу рішення. Якщо на деякому рівні процесу інтерпретації вибраний шлях виявився хибним, то відбувається відновлення необхідного вмісту регістрів зчитуванням даних із пам'яті магазина. На Фіг. 7 наведено структуру слів бази знань, із яких складаються фрейми. Кожне слово бази знань містить 24 біти: байт ознак інтерпретації та інформаційне поле. Інформаційне поле залежно від типу поточного фрейму містить: фізичну адресу, що посилається на інший фрейм; фізичну адресу, що посилається на текстову константу; номер (ім'я) термінальної програми. На Фіг. 8 наведено структуру байта ознак, який містить інформацію про тип фрейму та ознаки його інтерпретації. 5 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Розглянемо побудову фреймів детальніше (Фіг. 9). Кожен фрейм містить голову та елементи, пов'язані одним відношенням: альтернативи, послідовності чи ітерації. Голова та будь-який з елементів займають декілька послідовно розташованих комірок пам'яті, елементи одного фрейму також розташовуються послідовно, причому голова фрейму розташована першою в даній послідовності. Розмір фреймів (число елементів в одному фреймі) альтернативи чи послідовності може бути довільним, але скінченним. Фрейм ітерації складається із двох компонент: голови та посилання на ітерований елемент, яким є фрейм деякого довільного поняття, за виключенням визначеного у формі ітерації. Цим забезпечується зв'язність різних фреймів у єдину багаторазово вкладену структуру, що може містити рекурсивні конструкції. Складність опису (потужність множини понять, структура їхнього взаємозв'язку) може бути довільною та обмежується ресурсами конкретної реалізації (об'ємом оперативної пам'яті, об'ємом зовнішньої пам'яті, розрядністю вузлів та шин). Ті поняття бази знань, які не визначені через поняття бази знань, є термінальними та містять посилання на константи або термінальні програми, що у подальшому виконуються процесором 5 обробки термінальних програм. Описана таким чином інформаційна структура є базою знань прикладної області. На Фіг. 10 у формі орієнтованого циклічного графу наведено алгоритм роботи машини обробки знань. При виконанні цього алгоритму процесор 3 виконує набір процедур, зміст яких визначено у табл. 3, де в якості змінних R x та Ry можуть бути застосовані регістри R01-R09, ROI, RЛМ. Процесор обробки знань 3 безперервно виконує алгоритм Фіг. 10 від початкової команди "старт" аж до зупинки тактового сигналу. В опису алгоритму використано наступні позначення: ПОЗ - процесор обробки знань 3, ПОД - процесор обробки термінальних програм 5, БЗ - база знань, ПМ - пам'ять магазина, ПС - пам'ять сліду, INP - пам'ять вхідного масиву, OUT - пам'ять вихідного масиву, ПП - пам'ять програм. 1. Початкова установка: Завантаження БЗ; Завантаження бібліотек термінальних програм в ПП ПОД або формування (конфігурування) структури ПОД; Завантаження даних (аргументу обчислювальної функції) в масиви INP і OUT пам'яті даних ПОД; Установка регістрів у початковий стан, зокрема регістр R14=00. Перехід в стан 2. 2. Прийом завдання процесором ПОЗ: Якщо отримано завдання, то: прийом від ПОД адрес даних в R06, R07 та ознак інтерпретації (режиму інтерпретації в R10, R11, значення інверсії 2 в R13 та в R15:=X); R01:= адреса БЗ; запис значень регістрів [R06], [R07] в ПМ; запис ознак інтерпретації (R14 - тип фрейму=00, режим інтерпретації - R10=0/1, R11=0/1, R12 Інв_1=Х, R13 - Інв_2=0/1, R15=Х) в ПМ; перехід в стан 3. Якщо отримано значення істинності, то зберегти його в R09 та перейти в стан 21; Інакше, очікування завдання поверненням до пункту 2. 3. Аналіз завдання і режиму його інтерпретації (R14+R10+R11) процесором ПОЗ: = R02: [R01] (вміст R01 записати в R02); R03:=[R01] (вміст R01 [записати в R03); Читання першого слова фрейму, R10:=[поле ОС], R14:=[поле "тип фрейму"], R12:=[поле 1]. Аналіз R14, R10 та R11: Якщо R14=:(00)&(R10=0/1)&(R11=0/1), то переходимо до п. 4 (термінали), Якщо (R14=01/10)&R10=0&R11=0, то перехід до п. 5 (розпізнавання альтернативи), Якщо R14=01&R10=0&R11=1, то перехід до п. 6 (породження альтернативи), Якщо R14=01&R10=1&R11=0, то перехід до п. 8 (розпізнавання альтернативи із слідом), Якщо R14=01&R10=1&R11=1, то перехід до п. 9 (породження альтернативи по сліду), Якщо R14=10&R10=0&R11=1, то перехід до п. 10 (породження послідовності), Якщо R14=10&R10=1&R11=1, то перехід до п. 12 (породження послідовності по сліду), Якщо R14=10&R10=1&R11=0, то перехід до п. 13 (розпізнавання послідовності із слідом), Якщо R14=11&R10=0&R11=0, то перехід до п. 15 (розпізнавання ітерації), Якщо R14=11&R10=0&R11=1, то перехід до п. 17 (породження ітерації), Якщо R14=11&R10=1&R11=0, то перехід до п. 18 (розпізнавання ітерації із слідом), 6 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Якщо R14=11&R10=1&R11=1, то перехід до п. 20 (породження ітерації по сліду). 4. Передача термінального завдання процесору ПОД: R01:=[перший та другий байти першого слова фрейму]; Запис R06, R07 та ознак інтерпретації (тип фрейму - термінал; поточний режим інтерпретації R10, R11; інверсія із завдання - 1) в ПМ; Передача R01, R06, R07 та ознак інтерпретації процесору ПОД; Перехід в стан 2. 5. Розпізнавання альтернативи: R02:=[R02]+1; R03:=[R02]; Читання другого слова фрейму. R13:=[поле 2], R15:=[поле ОЕ], R10:=[значення (0/1) ознаки розпізнавання із слідом] або R11:= [значення (0/1) ознаки породження], R01:=[перший та другий байти другого слова фрейму]. Запис значень регістрів [R06], [R07], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму; R 13 - Iнв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0, R11=0) в ПМ; R10:=R10; R11:=R11; Перехід в стан 3. 6. Породження альтернативи: R10:=R10; Аналіз R10 (біта "ознака сліду", взятого з першого слова фрейму): якщо 0, то перехід в стан 21, інакше - в 7. 7. Встати на слід: RC04:= [перший та другий байти першого слова фрейму]; RC08:=[ПС за адресою RC04]; R03:=[R02]+[RC08]; Читання обраного слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. Запис [R06], [R07] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 Інв_1 з першого слова фрейму; R 13 - Інв_2, R15 - ОЕ з обраного слова фрейму та поточний режим інтерпретації - R10=0/1, R11=1) в ПМ; Перехід в стан 3. 8. Розпізнавання альтернативи із слідом: RC08:=1; RC04:=[R05]+1; Запис [RC08] в ПС за адресою [RC04]; R03:=[R02]+[RC08]; Читання другого слова фрейму. R13:= [поле 12], R15:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. Запис [R06], [R07], [R05], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації – R10=1, R11=0) в ПМ; R05:= [RC04]; Перехід в стан 3. 9. Породження альтернативи по сліду: RC04:= [RC04]+1', RC08:= [ПС] за адресою [RC04]; R03:= [R02]+[RC08]; Читання вибраного слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. Запис [R06], [R07] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 Інв_1 з першого слова фрейму; R11 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R10=1, R10=1) в ПМ; Перехід в стан 3. 10. Породження послідовності: R10:=R10; Аналіз R10 (біта "ознака сліду", взятого з першого слова фрейму): якщо 1, то переходимо в стан 11, інакше - в 12. 11. Встати на слід: RC04:= [перший та другий байти першого слова фрейму]; 7 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Перехід в стан 12. 12. Породження послідовності по сліду або без сліду: R02:=[R02]+1; R03:=[R02]; Читання другого слова фрейму. R13:= [поле] 2], R15:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. Запис значень регістрів [R06], [R07], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; Перехід в стан 3. 13. Розпізнавання послідовності із слідом: RC08:=1; RC04:= [R05]; R03:=[R02]+[RC08]; Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. Запис [R06], [R07], [R05], [R02], [RC08] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0/1, R11=1) в ПМ; Перехід в стан 3. 14. Завершити породження ітерації по сліду: RC08:=[RC08]-1; R03:=[Ro2]+1; Читання другого слова фрейму. R13:= [поле  2], R01:= [перший та другий байти другого слова фрейму]. Запис [RC08], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації R10=0/1, R11=1) в ПМ; Перехід в стан 3. 15. Розпізнавання ітерації: Ro3:=[R02]+1; Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R10:= [значення (0/1) ознаки розпізнавання із слідом] або R11:= [значення (0/1) ознаки породження], R 11:= [перший та другий байти другого слова фрейму]. Запис значень регістру [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0, R11=0) в ПМ; R10:=R10; R11:= R11; Перехід в стан 3. 16. Встати на слід: RC04:= [другий та третій байти першого слова фрейму]; RC08:= [ПС] по адресу RC04; Якщо лічильник [RC08]  0, то перехід в стан 14, інакше - в стан 19. 17. Породження ітерації: R10:=R10; Аналіз R10 (біта "ознака сліду", взятого з першого слова фрейму): якщо 1, то переходимо в стан 16, інакше - в 19. 18. Розпізнавання ітерації із слідом: RC04:=[R05]+1; RC08:=0; Запис [RC08] в ПС по адресу RC04; R03:=[R02]+1; Читання другого слова фрейму. R13:= [поле  2], R10:= [перший та другий байти другого слова фрейму]. Запис [R05], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації R10=1, R11:=0) в ПМ; R05:=[RC04]; Перехід в стан 3. 19. Завершити породження ітерації без сліду: 8 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 R09:=R12; Перехід в стан 21. 20. Породження ітерації по сліду: RC04:=[RC04]+1; RC08:=[ПС] по адресу RC04; Якщо [RC08]  0, то перехід в стан 14, інакше - в стан 19. 21. Прийом і аналіз прапорів: Ознаки інтерпретації з магазина R10, R11, R12, R13, R14, R15:= [Верхній запис ПМ]; R09:=[R09][R13]; Аналіз R14, R09, R10 та R11; Якщо R14=(00)&R09=1&(R10=0/1)&(R11=0/1), то переходимо до п. 22 (прапор лож на термінал), Якщо R14=(00)&R09=0&(R10=0/1)&(R11=0/1), то переходимо до п. 23 (прапор істина на термінал), Якщо R14=01&R09=0&R10=0&R11=0, то перехід до п. 24 (розпізнавання альтернативи після прапору істина), Якщо R14=01&R09=0&R10=1&R11=0, то перехід до п. 25 (розпізнавання альтернативи із слідом після прапору істина), Якщо R14=01&R09=0&R10=0/1&R11=1, то перехід до п. 27 (породження альтернативи після прапору істина), : Якщо R14=01&R09=1&R10 =0&R11=0, то перехід до п. 28 (розпізнавання альтернативи після прапору лож), Якщо R14=01&R09=1&R10=1&R11=0, то перехід до п. 30 (розпізнавання альтернативи із слідом після прапору лож), Якщо R14=01&R09=1&R10=0/1&R11=1, то перехід до п. 32 (породження альтернативи після прапору лож), Якщо R14=10&R09=0&R10=0&R11=0, то перехід до п. 34 (розпізнавання послідовності після прапору істина), Якщо R14=10&R09=0&R10=1&R11=0, то перехід до п. 35 (розпізнавання послідовності із слідом після прапору істина), Якщо R14=10&R09=0&R10=0/1&R11=1, то перехід до п. 37 (породження послідовності після прапору істина), Якщо R14=10&R09=1&R10=0&R11=0, то перехід до п. 38 (розпізнавання послідовності після прапору лож), Якщо R14=10&R09=1&R10=1&R11=0, то перехід до п. 40 (розпізнавання послідовності із слідом після прапору лож), Якщо R14=10&R09=1&R10=0/1&R11=1, то перехід до п. 41 (породження послідовності після прапору лож), Якщо R14=11&R09=0&R10=0&R11=0, то перехід до п. 42 (розпізнавання ітерації після прапору істина), Якщо R14=11&R09=0&R10=1&R11=0, то перехід до п. 43 (розпізнавання ітерації із слідом після прапору істина), Якщо R14=11&R09=0&R10=0/1&R11=1, то перехід до п. 44 (породження ітерації після прапору істина), Якщо R14=11&R09=1&R10=0&R11=0, то перехід до п. 46 (розпізнавання ітерації після прапору лож), Якщо R14=11&R09=1&R10=1&R11=0, то перехід до п. 47 (розпізнавання ітерації із слідом після прапору лож), Якщо R14=11&R09=1&R10=0/1&R11=1, то перехід до п. 48 (породження ітерації після прапору лож). 22. Відновлення покажчиків INP, OUT: R06:=[R06 iз ПM]; R07:=[R07 із ПM]; Перехід в стан 2. 23. Набуття нових значень покажчиків INP, OUT: Виштовхнути [R06], [R07] із ПМ; Перехід в стан 2. 24. Розпізнавання альтернативи після прапору істина: Виштовхнути [R02 з ПМ]; Виштовхнути [R06 та R07] із ПМ. R09:=[R09][R12]; 9 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Перехід в стан 21. 25. Розпізнавання альтернативи із слідом після прапору істина: R02:=[R02 із ПM]; R03:=[R02]; RC04:=[R05 із ПM]; ОС першого слова фрейму:= 1; поля  1 та тип фрейму - відновити; [перший та другий байти першого слова фрейму]:=[RC04]; Виштовхнути [R06 та R07] із ПМ. R09:=[R09][R12]; Перехід в стан 21. 26. Вихід з розпізнавання альтернативи: Виштовхнути [R02 із ПМ]; R09:=[R09][R12]; Перехід в стан 21. 27. Породження альтернативи по сліду після прапору істина: Виштовхнути [R06 та R07] із ПМ. R09:=[R09][R12]; Перехід в стан 21. 28. Розпізнавання альтернативи після прапору лож: Відновлення покажчиків INP, OUT: R06:=[R06 з ПМ], R07:=[R07 з ПМ]; Аналіз значення R15: якщо 1, перехід в стан 26, інакше - в стан 29. 29. Розпізнавання нового варіанта альтернативи: R02:=[R02 iз ПM]+1; R03:=[R02]; Читання чергового слова фрейму альтернативи. R13:= [поле  2], R15:= [поле ОЕ], R10:= [значення (0/1) ознаки розпізнавання із слідом] або R10:= [значення (0/1) ознаки породження], R11:= [перший та другий байти вибраного слова фрейму]. Запис значень регістрів [R06], [R07], [R02] в ПМ Запис ознак інтерпретації (R 14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму - тобто відновлення їхніх значень у магазині; R13 - Інв_2, R15 - ОЕ з чергового слова фрейму та відновити записаний у магазині вхідний режим інтерпретації - R10=O, Rn=0) в ПМ; R10:=R10; R11:=R11; Перехід в стан 3. 30. Розпізнавання альтернативи із слідом після прапору лож: Відновлення покажчиків INP, OUT: R06:=[R06 з ПМ], R07:=[R07 з ПМ]; Аналіз значення R15: якщо 1, перехід в стан 31, інакше - в стан 33. 31. Вихід із розпізнавання альтернативи із слідом: Виштовхнути [R02 із ПМ]; R05:=[R05 із ПM]; R09:=[R09][R12]; Перехід в стан 21. 32. Породження альтернативи по сліду після прапору лож: Відновлення покажчиків R06:=[R06 із ПМ], R07:=[R07 із ПМ]; R09:=[R09][R12]; Перехід в стан 21. 33. Розпізнавання із слідом нового варіанта альтернативи: RC04:=[R05 із ПМ]+1; RC08:=[RC08 із ПC]+1; Запис [RC08] в ПС по адресу RC04; R02:=[R02 із ПM]; R03:=[R02]+[RC08]; Читання чергового слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. Запис [R06], [R07], [R05], [R02] в ПМ - ця запис відновлюється; Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму, відновлених з магазина; R13 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R10=1, R11=0) в ПМ; R05:=[RC04]; Перехід в стан 3. 34. Розпізнавання послідовності після прапору істина: 10 UA 109712 C2 5 10 15 20 25 30 35 40 45 50 55 60 Аналіз значення R15: якщо 1, перехід в стан 24, інакше - в стан 29. 35. Розпізнавання послідовності із слідом після прапору істина: Аналіз значення R15: якщо 1, перехід в стан 25, інакше - в стан 36. 36. Продовжити розпізнавання послідовності із слідом: RC08:=[RC08 із ПM]+1; R03:=[R02]+[RC08]; Читання чергового слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. Запис [R06], [R07], [R05], [R02], [RC08] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 -ОЕ з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; Перехід в стан 3. 37. Породження послідовності після прапору істина: Аналіз значення R15: якщо 1, перехід в стан 24, інакше - в стан 39. 38. Розпізнавання послідовності після прапору лож: Відновлення покажчиків INP, OUT: R06:= [R06 з ПМ], R07:=[R07 з ПМ]; Перехід в стан 26. 39. Продовжити породження послідовності: R02:=[R02 із ПM]+l; R03:=[R02]; Читання чергового слова фрейму послідовності. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. Запис [R06], [R-07], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; Перехід в стан 3. 40. Розпізнавання послідовності із слідом після прапору лож: Відновлення покажчиків: R05:=[R05 із ПМ], R06:=[R06 із ПМ], R07:=[R07 із ПМ]; R10:=R10'; R11:=R11; Перехід в стан 26. 41. Породження послідовності після прапору лож: Відновлення покажчиків INP, OUT: R06:=[R06 із ПМ], R07:=[R07 із ПМ]; R10:=R10; R11:=R11; Виштовхнути [R02 із ПМ]; R09:=[R09][R12]; Перехід в стан 21. 42. Розпізнавання ітерації після прапору істина: R03:=[R02 із ПM]+1; Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R10:= [значення (0/1) ознаки розпізнавання із слідом] або R10:= [значення (0/1) ознаки породження], R 01:= [перший та другий байти другого слова фрейму]. Запис значення регістру [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0, R11=0) в ПМ; - тобто тут просто збільшення лічильника магазина без фактичного запису (запис зберігається) R10:=R10; R11:=R11’; Перехід в стан 3. 43. Розпізнавання ітерації із слідом після прапору істина: RC04:=[R05 із ПМ]+1; RC08:=[RC08 із ПС по адресу RC04]+1; Запис [RC08] в ПС по адресу RC04; Ro3:=[R02 із ПM]+1; Читання другого слова фрейму. R13:= [поле  2], R01:= [другий та третій байти другого слова фрейму]. Запис [R05], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації R10=1, R11=0) в ПМ; - тобто тут просто збільшення лічильника магазина без фактичного запису (запис зберігається) Перехід в стан 3. 44. Породження ітерації після прапору істина: 11 UA 109712 C2 5 10 15 20 25 RC08:=[RC08 із ПM]; Аналіз [RC08]: якщо [RC08]0, то перехід в стан 45, інакше - в стан 46. 45. Продовжити породження ітерації після прапору істина: RC08:=[RC08]-1; R03:=[R02 із ПM]+1; Читання другого слова фрейму. R13:= [поле  2], R01:= [перший та другий байти другого слова фрейму]. Запис [RC08], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації R10=0/1, R11=1) в ПМ; Перехід в стан 3. 46. Завершити породження ітерації та розпізнавання ітерації після прапору лож: Виштовхнути [R02 із ПМ]; R09:=[R12]; Перехід в стан 21. 47. Розпізнавання ітерації із слідом після прапору лож: R03:=[R02 із ПM]; RC04:=[R05 із ПM]; ОС першого слова фрейму:=1; поля  1 та тип фрейма - відновити; [перший та другий байти першого слова фрейму]:= [RC04]; R09:=[R12]; Перехід в стан 21. 48. Породження ітерації після прапору лож: Виштовхнути [R02 із ПМ]; Виштовхнути [RC08 із ПМ]; R09:=[R12]; Перехід в стан 21. Таблиця 1 Блок Б01 Б02 Б03 Б04 Б05 Б06 Б07 Б08 Б09 БОІ БЛМ RAD RDT Регістр, який входить у блок R01 R02 R03 RC04 R05 R06 R07 RC08 R09 R10 R11 R12 ROI R13 R14 R15 RЛМ RAD RDT Розрядність регістра, біт 16 16 16 16 16 16 16 16 16 1 1 1 1 3 1 16 16 16 30 12 Опис блока Блок імені структури Блок номера слова фрейму Блок адреси бази знань Блок координати сліду Блок вершини сліду Блок адреси у вхідному масиві Блок адреси у вихідному масиві Блок лічильника ітерації Блок істинності Регістр ознаки сліду Регістр ознаки породження Регістр Інв_1 Регістр Інв_2 Регістр типу фрейму Регістр ознаки останнього елемента Блок лічильника пам'яті магазина Регістр адреси даних Регістр даних UA 109712 C2 Таблиця 2 № 1 Ім'я команди 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 LD R12 , R09 LD 0, R08 LD 1, R11 LD 1, R10 LD R01, R02 LD R01, R03 LD R01, RDT LDR01+1, R02 LD R02, R03 LD R02, RDT LDR02+1, R02 LD R04, R05 LD R04, RRA LD R04, RWA LD R04+1, R04 LD R05, R04 LD R05, RDT LDR05+1, R04 LD R06, RDT LD R07, RDT LD Ro8, RDT LD R08-1, R08 LD R09  R12, R09 LDR09  R13, R09 LD ROI, RDT LD RЛМ, RWA LD RЛМ+1, RЛМ LD RЛМ-1, RЛМ LDDATAEXT, R01 LD DATAEXT, R02 LD DATAEXT, R03 LD DATAEXT, R04 LD DATAEXT, R05 LD DATAEXT, R06 LD DATAEXT, R07 LD DATAEXT, R08 LD DATAEXT, R09 LD DATAEXT, RDT LD DATAEXT, RRA LD DATAEXT, RWA LD DATAEXT, ROI LD DATAEXT, RЛМ LD DATARAM, R01 LD DATARAM, R02 LD DATARAM, R04 LD DATARAM, R05 LD DATARAM, R06 LD DATARAM, R07 LD DATARAM, R08 LD DATARAM, ROI RD RAM 52 REQ_TER_PROGR 53 54 55 56 WR RAM LD R08, RБ LD R09, RБ LD RОІ, RБ Опис команди Завантаження R12 у R09 Завантаження "0" у R08 Завантаження "1" у R11 Завантаження "1" у R10 Завантаження даних із R01 у R02 Завантаження даних із R01 у R03 Завантаження даних із R01 у RDT Інкремент даних у R01 та запис їх у R02 Завантаження даних із R02 у R03 Завантаження даних із R02 у RDT Інкремент даних у R02 та запис їх у R02 Завантаження даних із R04 У R05 Завантаження даних із R04 у RRA Завантаження даних із R04 у RWA Інкремент даних у R04 та запис їх у R04 Завантаження даних із R05 у R04 Завантаження даних із R05 у RDT Інкремент даних у R05 та запис їх у R04 Завантаження даних із R06 у RDT2 Завантаження даних із R07 y RDT2 Завантаження даних із R05 у RDT2 Декремент даних у R08 та запис їх у R08 Завантаження R09  R12 у R09 Завантаження R09  R13 у R09 Завантаження даних із ROI у RDT2 Завантаження даних із RЛМ у RWA Інкремент даних у RЛМ та запис їх у RЛМ Декремент даних у RЛМ та запис їх у RЛМ Завантаження зовнішніх даних у R01 Завантаження зовнішніх даних у R02 Завантаження зовнішніх даних у R03 Завантаження зовнішніх даних у R04 Завантаження зовнішніх даних у R05 Завантаження зовнішніх даних у R06 Завантаження зовнішніх даних у R07 Завантаження зовнішніх даних у R08 Завантаження зовнішніх даних у R09 Завантаження зовнішніх даних у RDT Завантаження зовнішніх даних у RRA Завантаження зовнішніх даних у RWA Завантаження зовнішніх даних у ROI Завантаження зовнішніх даних у RЛМ Завантаження даних у R01 із першої оперативної пам'яті Завантаження даних у R02 із першої оперативної пам'яті Завантаження даних у R04 із першої оперативної пам'яті Завантаження даних у R05 із першої оперативної пам'яті Завантаження даних у R06 із першої оперативної пам'яті Завантаження даних у R07 із першої оперативної пам'яті Завантаження даних у R08 із першої оперативної пам'яті Завантаження даних у ROI із першої оперативної пам'яті Зчитування даних із першої оперативної пам'яті Запит ресурсів універсального процесора на термінальної програми Запис даних у першу оперативну пам'ять Завантаження даних із R08 у RБ Завантаження даних із R09 у RБ Завантаження даних із RОІ у RБ 13 опрацювання UA 109712 C2 Таблиця 3 № 1 4 5 6 7 Реалізація базових процедур LD Rx, Rу LD Ry, RRA Зчитування слова із першої оперативної пам'яті по RD RAM адресу, який міститься в Ry, та запис в Rx LD DATARAM, Rx LD Ry, RWA Запис даних, що знаходяться в регістрі Rx, в першу LD Rx, RDT оперативну пам'ять по адресу, що знаходиться в Rv WR RAM Інкремент даних у Rx та їх запис у Rv LDRх+1, Rу Декремент даних у Rx та їх запис у Rу LDRх-1, Rу Запис «0» у Rx LD 0, Rx Запис "1" у Rx LD 1, Rх 8 Інвертування Rх та запис отриманих даних y Rу 9 Завантаження зовнішніх даних у Rx 10 Зчитування першого слова фрейму 11 Аналіз Rx Передача Rx до універсального процесора (процесора LD Rx, RE REQ TER PROGR обробки термінальних програм) 2 3 12 Базова процедура Вміст Rx записати в Rv LD R x , Ry LD DATAEXT, Rx LD R02, RRA RD RAM LD Rx, RБ ФОРМУЛА ВИНАХОДУ 5 10 15 20 25 30 35 Машина обробки знань, що містить головний комп'ютер, першу оперативну пам'ять, перший блок вводу-виводу, перший блок керування, арифметико-логічний блок, робочу пам'ять, перший регістр даних та регістр-лічильник координат вхідного масиву, у якій перший вхід-вихід першого блока вводу-виводу підключений до системної шини машини, другий вхід-вихід першого блока вводу-виводу підключений до входів-виходів регістра-лічильника координат вхідного масиву, третій вхід-вихід першого блока вводу-виводу разом із входами-виходами арифметикологічного блока, входом-виходом першого блока керування та першими входами-виходами першого регістра даних, з'єднаного другими входами-виходами з входами-виходами робочої пам'яті, підключений до шини даних, яка відрізняється тим, що в неї введено регістр-лічильник координат вихідного масиву, мультиплексор, другу оперативну пам'ять, другий блок керування, другий та третій блоки вводу-виводу, дешифратор команд, блоки імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина та ознак інтерпретації, буферний регістр, другий регістр даних та регістр адреси, при цьому четвертий вхід-вихід першого блока вводу-виводу підключено до входів-виходів регістра-лічильника координат вихідного масиву, вихід якого разом із виходом регістра-лічильника координат вхідного масиву через мультиплексор підключений до адресних входів робочої пам'яті, головний комп'ютер через другий блок вводу-виводу, друга оперативна пам'ять та перший вхід-вихід третього блока вводу-виводу підключені до системної шини пристрою, перший вихід третього блока вводу виводу підключено до першого входу другого блока керування, перший вихід якого підключено до третього входу третього блока вводу-виводу, другий вихід другого блока керування підключено до входу дешифратора команд, вихід якого підключено до перших входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина та ознак інтерпретації, третій вихід другого блока керування підключено до перших входів регістра адреси та другого регістра даних, четвертий вихід другого блока керування підключено до входу керування першої оперативної пам'яті, вихід якої підключено до другого входу третього блока вводу-виводу, до першого входу другого блока керування, до других входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, лічильника магазина та ознак інтерпретації, другий вихід третього блока вводу-виводу підключено до третіх входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, ітерації, істинності, 14 UA 109712 C2 5 10 15 лічильника магазина, ознак інтерпретації та до других входів другого регістра даних та регістра адреси, вихід блока імені структури підключено до третього входу другого регістра даних, до четвертого входу блока номера слова фрейму та до четвертого входу блока адреси бази знань, вихід блока номера слова фрейму підключено до четвертих входів другого регістра даних та блока адреси бази знань, чий вихід підключено до четвертого входу блока імені структури, вихід блока координати сліду підключено до третього входу регістра адреси та до четвертого входу блока вершини сліду, вихід якого підключено до п'ятого входу другого регістра даних та до четвертого входу блока координати сліду, вихід блока адреси у вхідному масиві підключено до шостого входу другого регістра даних, вихід блока адреси у вихідному масиві підключено до сьомого входу другого регістра даних, вихід блока ітерації підключено до восьмого входу другого регістра даних та до третього входу буферного регістра, чий другий вхід разом із четвертим входом блока ознак інтерпретації підключено до виходу блока істинності, вихід блока лічильника магазина підключено до четвертого входу регістра адреси, вихід блока ознак інтерпретації підключено до другого входу блока істинності, до першого входу буферного регістра та до дев'ятого входу другого регістра даних, вихід регістра адреси підключено до адресного входу першої оперативної пам'яті, вхід даних якої підключено до виходу другого регістра даних, вихід буферного регістра підключено до третього входу третього блока вводувиводу та до другого входу другого блока керування. 15 UA 109712 C2 16 UA 109712 C2 17 UA 109712 C2 18 UA 109712 C2 19 UA 109712 C2 Комп’ютерна верстка А. Крулевський Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 20