БЛОК УНИФИКАЦИИ С ПОСЛЕДОВАТЕЛЬНЫМ СОПОСТАВЛЕНИЕМ ТЕРМОВ

Полезная модель относится к вычислительной технике, а именно к устройству унификации двух N-местных предикатов, и может быть использована в машине логического вывода, обрабатывающей знания в логике предикатов первого порядка, а также может быть использована как специализированный компаратор сложноструктурированных массивов тэгированных данных, а также как модель отдельного специализированного вычислительного устройства унификации для организации лабораторных работ студентов.
Используемые понятия:
N
N
1
N
1
N
Предикат - выражение вида P(t, …t), где P - N - местная предикатная константа, a(t, …t) - его термы (аргументы). Терм может быть представлен:
- предметной константой;
- свободной переменной;
- функтором.
N
N
1
N
1
N
Функтор - выражение вида f(t, …t), где F - N - местная факторная константа, a(t, …t) - его термы (аргументы).
Для разработанной модели устройства введены следующие ограничения на обрабатываемые данные: количество термов (аргументов) предиката - 8, количество уровней вложенности функторов - 3 (т.е. аргументом функтора может быть функтор, одним из аргументов которого является функтор). Анализ задач, применяемых для тестирования процессоров логического вывода [Вишняков В.А. Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - с. 93] показал, что данные ограничения позволяют провести тестирование на любом наборе указанных тестов.
В настоящее время в сфере компьютерных систем и технологий особенно актуальными становятся системы, решающие задачи обработки знаний. Представление знаний о выбранной предметной области является, как правило, достаточно трудоемкой задачей для интерпретации на ЭВМ, и поэтому для работы с такой информацией необходимы семантические способы описания. Сложность решения подобных задач определяется сложностью проблемной среды, так называемой онтологии. К таким задачам относятся: управление крупными предприятиями, транспортная логистика, бизнес-аналитика, управление боем, медицинская и техническая диагностика, логическое прогнозирование и т.д. Количество вышеуказанных задач неуклонно растет, а вычислительный аспект в них уходит на второй план. Именно поэтому были созданы специальные языки логического программирования (ЯЛП), а также появился спрос на различного рода экспертные системы (ЭС) и системы поддержки принятия решения. Главная проблема в том, что языки логического программирования реализуются на ПЭВМ неэффективно, так как ЯЛП предназначены для обработки символьной информации, основаны на переборной процедуре логического вывода, используют нетрадиционные сложные структуры данных, и в них преобладают специфические операции, не имеющие аналогов в «обычных» алгоритмических языках [Вишняков В.А. Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - с. 3]. На сегодняшний день написанные на ЯЛП программы переводятся в набор микрокоманд для выполнения на серийных универсальных процессорах, предназначенных, в первую очередь, для обработки числовых данных, при этом не учитывается специфика алгоритмов обработки логических программ.
Решением указанных проблем может стать аппаратная поддержка специализированных машин логического вывода, составляющих основу любой системы обработки знаний. А поскольку в процессе логического вывода на знаниях одной из самых частых операций над символьными данными (около 70%) является операция унификации термов [Вишняков В.А. Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - с. 137], то особое внимание необходимо уделить устройству, выполняющему именно эту процедуру.
Из источника [Вишняков В.А. Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - с. 137] известен процессор (блок) унификации, который реализует следующие этапы унификации: этап проверки равенства функторов унифицируемых структур, этап вычисления аргумента унифицируемых структур, этап перехода к следующим обрабатываемым аргументам, этап дерефернсирования переменной, этап дерефернсирования аргумента, этапы записи в стеки, этап чтения из унифицируемого стека, этап создание подстановок. Указанный процессор состоит из следующие элементов: блока регистров общего назначения REGISTERS, сумматора SM, компараторов СОМР0-СОМР3, регистра состояния RGPSW, постоянного запоминающего устройства ROM, выходных буферных регистров RGA и RGB, выходного регистра команд RGI, устройства управления CU, 32-разрядной входной шина данных LDI, 32-разрядной выходной шины данных LDO, 24-разрядной выходной шины адреса LDA, 6-разрядной входной шины команд LMI, 4-разрядной входной шины стробирования и синхронизации WR, 8-разрядной входной шины состояния STAT. Блок регистров общего назначения (РОН) включает шестнадцать регистров: регистры унифицируемых аргументов, регистры хранения максимального верхнего значения глобального, локального и трейлового стеков, регистры хранения текущих адресов в стеках, регистры хранения векторов переменных, входящих в скелетоны унифицируемых структур, регистр хранения указателя унифицируемого стека, регистр хранения указателя пары унифицируемых аргументов, регистр адреса тэгированного значения, считанного из памяти в регистры унифицируемых аргументов. Регистры унифицируемых аргументов 32-разрядные, регистр текущего номера пары аргументов 8-разрядный, остальные регистры 24-разрядные.
Данное устройство имеет следующие недостатки. Во-первых, в процессоре используется большое число типов данных - 9, что приводит к значительному усложнению устройства управления, т.к. для каждой пары сопоставляемых типов данных вызывается своя специализированная процедура обработки. Во-вторых, присутствует значительное число (20) регистров большой разрядности (24-разрядные и 32-разрядные) для хранения обрабатываемых термов и служебной информации, что существенно увеличивает аппаратурные затраты. Так, даже для хранения индекса (адреса) переменной в небольшой по объему таблице символов используется 24-разрядное поле. Как следствие, большая разрядность устройств сравнения и анализа этих данных. В-третьих, обрабатываемые данные каждый раз сохраняются во внешнюю, для блока унификации, память, что значительно увеличивает время унификации при необходимости повторного обращения к ним в процессе унификации. В-четвертых, применение сжатых форматов данных, типа молекула, хотя и несколько уменьшает объем требуемой для хранения памяти, однако вызывает необходимость каждый раз распаковывать структуру при унификации подобных термов, что усложняет конструкцию процессора. В-пятых, операция дереференсирования переменных проводится каждый раз в процессе сопоставления двух аргументов-переменных, что приводит к необходимости проводить ее неоднократно для одной и той же глобальной переменной и, соответственно, значительному увеличению времени унификации.
Техническим результатом, достигаемым при использовании предлагаемой полезной модели, является значительное сокращение времени унификации предикатов, а также снижение аппаратурных затрат. Технический результат достигается за счет сокращения сопоставляемых типов данных до четырех (предикат, функтор, константа переменная; «пустая ячейка» типом данных, по сути, не является, т.к. не подлежит сопоставлению), уменьшению числа необходимых регистров до шести, использованию для определения адреса перехода к следующему аргументу счетчика (вместо сумматора) и выполнению операции дереференсирования до операции сопоставления глобальной переменной (что позволяет иметь актуальное значение данной переменной в момент ее унификации). Данный подход позволяет значительно упростить блок управления, использовать универсальные узлы для унификации термов и значительно уменьшить число вызываемых подпрограмм сопоставления различных пар термов. Введение в состав блока унификации рабочей памяти с хранимыми в ней структурами сравниваемых предикатов не связано с увеличением аппаратурных затрат блока, т.к. в устройстве [Вишняков В.А. Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - с. 137] подобная память входит в состав исполнительного процессора, частью которого и является процессор унификации. Принятое решение позволило значительно сократить время сопоставления, за счет уменьшения длительности операций чтения/записи в данную память в ходе процедуры унификации.
Предлагаемое устройство благодаря регулярной структуре может быть легко реализовано на основе программируемой логической интегральной схемы или заказной СБИС.
Раскрытие полезной модели
Предлагаемое устройство может быть использовано в машине логического вывода, реализующей любую процедуру вывода в логике предикатов первого порядка, а также может быть использовано как специализированный компаратор сложноструктурированных массивов тегированных данных. Обобщенная структура машины логического вывода, а также форматы и структуры данных взяты из [Страбыкин Д.А. Логический вывод в системах обработки знаний [Текст] / Д.А. Страбыкин; под ред. Д.В. Пузанкова. - СПб.: Изд-во СПбГЭТУ, 1998. - с. 87]. Для осуществления указанных функции требуются следующие элементы: регистры хранения операндов; компаратор для сравнения имен термов; дешифраторы для обработки тэгов сравниваемых операндов; блок рабочей памяти для хранения обрабатываемых структур и служебной информации; счетчик управления адресами блока рабочей памяти; два мультиплексора для выбора источника загрузки операнда; память подстановок для хранения значений инициализации переменных; счетчик управления адресами памяти подстановок; регистр и компаратор для восстановления значения счетчика управления адресами памяти подстановок; устройство управления блоком последовательной унификации; девятнадцать однонаправленных линий связи для передачи данных, адресов и служебных сигналов.
На фигуре 1 представлена структурная схема блока унификации с последовательным сопоставлением термов. На схеме указаны:
1 - устройство управления блоком последовательной унификации;
2 - блок рабочей памяти (двухпортовая);
3 - мультиплексор для выбора источника загрузки операнда в регистр 5;
4 - мультиплексор для выбора источника загрузки операнда в регистр 6;
5 - регистр хранения первого операнда;
6 - регистр хранения второго операнда;
7 - счетчик управления адресом первого порта блока рабочей памяти;
8 - счетчик управления адресом второго порта блока рабочей памяти;
9 - дешифратор тэга первого операнда;
10 - дешифратор тэга второго операнда;
11 - компаратор для сравнения имен операндов;
12 - счетчик управления адресами памяти подстановок;
13 - память подстановок;
14 - однонаправленная линия связи от блока рабочей памяти к мультиплексору 3;
15 - однонаправленная линия связи от блока рабочей памяти к мультиплексору 4;
16 - однонаправленная линия связи от мультиплексора 3 к регистру хранения первого операнда 5;
17 - однонаправленная линия связи от мультиплексора 4 к регистру хранения второго операнда 6;
18 - однонаправленная линия связи для передачи адреса от счетчика управления адресом первого порта блока рабочей памяти 7 к блоку рабочей памяти 2;
19 - однонаправленная линия связи для передачи адреса от счетчика управления адресом второго порта блока рабочей памяти 8 к блоку рабочей памяти 2;
20 - однонаправленная линия связи от регистра хранения первого операнда 5 к дешифратору 9, компаратору для сравнения имен операндов 11 и памяти подстановок 13;
21 - однонаправленная линия связи от регистра хранения второго операнда 6 к дешифратору 10, компаратору для сравнения имен операндов 11 и памяти подстановок 13;
22 - однонаправленная линия связи для передачи значения счетчика управления адресами памяти подстановок 12 в память подстановок 13, регистр восстановления значения счетчика управления адресами памяти подстановок 28 и компаратор для восстановления значения счетчика управления адресами памяти подстановок 29;
23 - однонаправленная линия связи для передачи термов (операндов) из памяти подстановок на мультиплексор 4, а также для выдачи результирующих подстановок первого предиката;
24 - однонаправленная линия связи для передачи термов (операндов) из памяти подстановок на мультиплексор 5, а также для выдачи результирующих подстановок второго предиката;
25 - однонаправленная линия связи для передачи осведомительных сигналов от дешифратора 9 к устройству управления 1;
26 - однонаправленная линия связи для передачи осведомительных сигналов от дешифратора 10 к устройству управления 1;
27 - однонаправленная линия связи для передачи осведомительных сигналов от компаратора для сравнения имен операндов 11 к устройству управления 1;
28 - регистр восстановления значения счетчика управления адресами памяти подстановок 12;
29 - компаратор для восстановления значения счетчика управления адресами памяти подстановок 12;
30 - однонаправленная линия связи для передачи осведомительных сигналов от компаратора для восстановления значения счетчика управления адресами памяти подстановок 29 к устройству управления 1;
31 - однонаправленная линия связи для восстановления значения счетчика управления адресами памяти подстановок 12;
32 - однонаправленная линия связи для выдачи сигнала о завершении унификации: «0» - завершилась неуспешно, «1» - завершилась успешно;
33 - шина передачи команды в устройство управления 1 и адресов унифицируемых предикатов - в счетчики управления адресами первого и второго порта блока рабочей памяти 7 и 8.
На фигуре 1 шина для обмена данными между блоком рабочей памяти и основной памятью исполнительного процессора не показана. Операция по загрузке всех необходимых данных в блок рабочей памяти осуществляется до начала процедуры логического вывода в целом. Передача управляющих сигналов от блока управления 1 на все остальные элементы схемы не показана.
Рассмотрим пример организации таблицы имен (фигура 2) и блока рабочей памяти (фигура 3) для команды унификации двух предикатов САМОЛЕТ (СИНИЙ, ТУ-154, x) и САМОЛЕТ (у, ТУ-204, НОМЕР (SU, 1437)). Предикат САМОЛЕТ характеризует самолет и имеет три терма: цвет, модель и серийный номер. В данном примере первый предикат САМОЛЕТ (СИНИЙ, ТУ-154, x) характеризует самолет ТУ-154 синего цвета, а серийный номер задается переменной x и уточняется в дальнейшем. Для второго предиката - цвет самолета не определен. С учетом введенных тэгов (для используемых в машине логического вывода данных: константа - 0001, предикат 1110, переменная - 0010, 1xxx - тэг терма вложенного в функтор), структура первого предиката будет занимать первые четыре ячейки рабочей памяти (ячейки с 0 по 3 на фигуре 3). Второй предикат - ячейки с 4 по 9.
Устройство начинает работу после получения устройством управления 1 по однонаправленной линии связи (шине) 33 соответствующей команды унификации. Формат команды унификации двух предикатов изображен на фигуре 4 (8 бит - код команды, 8 бит - адрес первого предиката в блоке рабочей памяти 2, 8 бит - адрес второго предиката в блоке рабочей памяти 2). Команда содержит начальные адреса предикатов - сложноструктурированных массивов тэгированных данных, размещенных в рабочей памяти 2. Происходит запись этих адресов в счетчики 7 и 8, соответственно, и подача их по шинам 18 и 19 на блок рабочей памяти 2 для пошагового считывания обрабатываемых структур данных. Считанные из блока рабочей памяти 2 операнды (имена предикатов, первые аргументы, вторые аргументы и т.д., соответственно), по шинам 14 и 15 поступают на мультиплексоры 3 и 4. Через правые плечи мультиплексоров операнды по шинам данных 16 и 17 загружаются в регистры хранения операндов 5 и 6. При сопоставлении имен предикатов, о чем устройству управления 1 сигнализируют дешифраторы тэгов 9 и 10, имена по шинам 20 и 21 подаются на компаратор для сравнения имен 11. Если имена предикатов не совпадают, блок управления 3 по шине 32 выдает ответ о невозможности унификации предикатов, и операция унификации завершается.
Если имена предикатов совпадают, производится переход к последовательному сопоставлению термов обоих предикатов. Для этого значения счетчиков 7 и 8 одновременно увеличиваются и очередные аргументы из памяти 2 через правые плечи мультиплексоров 3 и 4 заносятся в регистры операндов 5 и 6. Тэги аргументов дешифрируются на блоках 9 и 10, а осведомительные сигналы о результатах этой операции поступают по шинам 25 и 26 в блок управления 1.
Если сопоставляется пара «переменная-константа» или «константа-переменная», то в память подстановок 13 по адресу, указанному в счетчике управления адресами памяти подстановок 12, записывается соответствующая подстановка (например, x=5), и унификация предикатов продолжается (необходимо сравнить следующие аргументы).
Если сопоставляется пара «переменная-переменная», то в память подстановок 13 по адресу, указанному в счетчике управления адресами памяти подстановок 12, записывается соответствующая подстановка (например, x=y), и унификация предикатов продолжается (необходимо сравнить следующие аргументы).
Если сопоставляется пара «константа-константа», то необходимо сравнить их имена на компараторе для сравнения имен 11. Если имена совпадают, унификация предикатов продолжается, без занесения информации в память подстановок. В противном случае унификация невозможна, о чем выдается сигнал «0» по линии связи 32.
Если сопоставляется пара «функтор-функтор», то необходимо сравнить их имена на компараторе для сравнения имен 11. Если имена функторов совпадают, необходимо последовательно сопоставить все термы (аргументы) этих функторов с занесением соответствующих подстановок в память подстановок 13, аналогично сопоставлению термов предикатов. В противном случае унификация невозможна, о чем выдается сигнал «0» по линии связи 32.
Если сопоставляется пара «переменная-функтор» или «функтор-переменная», то сопоставление возможно, только если переменная не входит в функтор. Чтобы это проверить, нужно оставить переменную в «своем» регистре операнда (например, 5), а в соседний регистр второго операнда (соответственно 6) последовательно заносить аргументы функтора, увеличивая значение счетчика управления адресом второго порта блока рабочей памяти 8, пока не будет найдет терм с тэгом без вложения (в старшем разряде которого 0). Сравнивая тэги и имена аргументов функтора с переменной, записанной в регистре первого операнда 5 (для этого используются блоки 9, 10 и 11), блок управления 1 сообщает либо о вхождении переменной в функтор (тогда по линии 32 выдается сигнал о невозможности унификации), либо об отсутствии данного факта - тогда в память 13 записывается соответствующая подстановка (например, x=func(y,8)) и унификация предикатов продолжается.
Сопоставление пар «константа-функтор» или «функтор-константа» невозможно. В этом случае по шине 32 выдается сигнал о неуспешном завершении операции унификации двух предикатов.
Необходимо помнить один важный момент. Если, начиная со второго аргумента, одним из сопоставляемых термов является переменная, то нужно проверить, не были ли ранее сделаны замены данной переменной. Для этого выполняется поиск среди всех подстановок, сделанных ранее. Адрес текущей подстановки из счетчика управления адресами памяти подстановок 12, который указывает на первую свободную ячейку памяти подстановок, сохраняется в регистре восстановления значения счетчика управления адресами памяти подстановок 28. Далее значение счетчика 12 обнуляется. Для примера, допустим, что проверяемая переменная находится в регистре первого операнда 5. Тогда в регистр второго операнда 6 через левое плечо мультиплексора 4 заносится левая часть первой подстановки, сделанной при унификации данной пары предикатов. С помощью блоков 9, 10 и 11 происходит сравнение операндов. Если значения в регистрах операндов 5 и 6 совпадают (т.е. обнаружена подстановка переменной, сделанная ранее), то в регистр 5 из памяти подстановок 13 по шине 24 через левое плечо мультиплексора 3 записывается значение (правая часть) сделанной подстановки. Значение счетчика управления адресами памяти подстановок 12 восстанавливается из регистра 28, а в регистр второго операнда 6 из блока рабочей памяти 2 снова заносится сопоставляемый терм (аргумент) второго предиката.
Если сопоставление всех аргументов прошло удачно, т.е. в регистр второго операнда 6 загружена «пустая ячейка» с тэгом 0000, о чем дешифратор 10 послал сигнал в блок управления 1, то по линии 32 будет выдано сообщение об успешном окончании операции унификации. Одновременно с этим значение счетчика управления адресами памяти подстановок 12 записывается в регистр 28, а затем счетчик 12 обнуляется. Это необходимо для того, чтобы выдать все полученные при унификации пары предикатов подстановки по шинам выдачи результирующих подстановок 23 и 24. Об окончании операции выдачи результатов блоку управления 1 сообщит компаратор для восстановления значения счетчика управления адресами памяти подстановок 29. Команда унификации предикатов завершена.