Блок унификации с параллельным сопоставлением термов Российский патент 2018 года по МПК G06N5/04 

Изобретение относится к вычислительной технике, а именно к устройствам обработки символьной информации, и направлено на увеличение производительности и расширение функциональных возможностей процессоров логического вывода и систем, основанных на знаниях, реализующих любой метод логического вывода.

Изобретение может быть использовано при проектировании и разработке специализированных процессоров логического вывода или как самостоятельное устройство для проведения исследований по анализу эффективности различных методов параллельной унификации.

В настоящее время в сфере компьютерных систем и технологий особенно актуальными становятся системы, решающие задачи обработки знаний. Представление знаний о выбранной предметной области является, как правило, достаточно трудоемкой задачей для интерпретации на ЭВМ, поэтому для работы с такой информацией необходимы новые семантические подходы к извлечению, представлению, хранению и обработке информации. К задачам интеллектуальной обработки данных и знаний относятся: управление крупными предприятиями, транспортная логистика, бизнес-аналитика, медицинская и техническая диагностика, логическое прогнозирование и т.д. Количество вышеуказанных задач неуклонно растет, а вычислительный аспект в них уходит на второй план. Именно поэтому были созданы специальные языки логического программирования, а также появился спрос на различного рода экспертные системы и системы поддержки принятия решений. Главная проблема в том, что при реализации на ЭВМ языки логического программирования используются неэффективно, так как они предназначены для обработки символьной информации, а написанные на них программы переводятся в набор микрокоманд для выполнения на серийных универсальных процессорах, предназначенных, в первую очередь, для обработки числовых данных.

Решением перечисленных проблем может стать аппаратная поддержка специализированных машин логического вывода, составляющих основу любой интеллектуальный системы обработки знаний.

В процессе логического вывода одной из самых частых операций над символьными данными является операция унификации предикатов. Известны обобщенная структура абстрактной машины логического вывода, а также форматы и структуры данных [Meltsov V.Yu. High-performance systems of deductive i nference: Monograph. -Yelm, WA, USA: Science Book Publishing House, 2014. - 216 p., с. 101, 124-132].

Из источника [Вишняков, В.А., Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - 264 с., с. 136-139] известен процессор унификации, который реализует следующие этапы унификации: этап проверки равенства имен унифицируемых структур, этап вычисления аргумента унифицируемых структур, этап перехода к следующим обрабатываемым аргументам, этап дереференсирования переменной, этап дереференсирования аргумента, этапы записи в стеки, операции чтения из унифицируемого стека, создание подстановок. Данный процессор унификации имеет следующие элементы: блок регистров общего назначения, который включает в себя: регистры унифицируемых аргументов, регистры хранения максимального верхнего значения глобального, локального и трейлового стеков, регистры хранения текущих адресов в стеках, регистры хранения векторов переменных, входящих в скелетоны унифицируемых структур, регистр хранения указателя унифицируемого стека, регистр хранения указателя пары унифицируемых аргументов, регистр адреса тегированного значения, считанного из памяти в регистры унифицируемых аргументов. Также в указанный процессор унификации входят: компараторы, сумматор, регистр состояния, ПЗУ, входные буферные регистры, устройство управления, входная и выходная шины данных, входная шина адреса, входная шина команд, шина стробирования записи и шина состояния. Данное устройство имеет следующие недостатки. Во-первых, значительное время унификации из-за последовательного сопоставления термов. Во-вторых, обрабатываемые данные каждый раз сохраняются во внешнюю для блока унификации память, что значительно увеличивает время унификации при необходимости повторного обращения к ним в процессе унификации. В-третьих, применение сжатых форматов данных, типа молекула, хотя и несколько уменьшает объем требуемой для хранения памяти, однако вызывает необходимость каждый раз распаковывать структуру при унификации подобных термов, что усложняет конструкцию процессора. В-четвертых, операция деференсирования переменных проводится каждый раз в процессе сопоставления двух аргументов-переменных, что приводит к необходимости проводить ее неоднократно для одной и той же глобальной переменной и, соответственно, значительному увеличению времени унификации.

Из источника [RU №158945 (Ul), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] известен блок унификации с последовательным сопоставлением термов. Данный блок унификации содержит: устройство управления, рабочую память, мультиплексоры для выбора источника загрузки операнда в регистры, регистры для хранения операндов, счетчики управления адресами первого и второго портов блока рабочей памяти, дешифраторы тэгов операндов, компаратор для сравнения имен термов, счетчик управления адресом памяти подстановок, память подстановок, регистр восстановления значения счетчика, компаратор для сравнения значения адреса памяти подстановок и сохраненного адреса. Данный блок унификации имеет следующие недостатки. Во-первых, значительное время унификации из-за последовательного сопоставления термов. Во-вторых, для учета возможной замены термапеременной, выполненной при сопоставлении предыдущих аргументов, требуется наличие дополнительной аппаратуры (регистр, счетчик, дешифратор) и значительное время на поиск имеющихся подстановок и восстановление значения счетчика адреса. В-третьих, отсутствует возможность учета подстановок, сделанных до выполняемой в настоящий момент команды унификации.

Из источника [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.] известен блок унификации с параллельным сопоставлением термов. Данный блок содержит: внутреннюю рабочую память, узел управления, узел диспетчеризации, узел сопоставления имен предикатов, узлы сопоставления термов, узел формирования подстановок. Данный блок унификации имеет следующий недостаток: отсутствует возможность корректной унификации предикатов, если в одном из предикатов есть более двух пар одноименных свободных переменных, конкретизируемых в процессе сопоставления разными константами. Свободная (или неконкретизированная) переменная - это переменная, которая еще не получила значения. Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной или конкретизированной. Пример, демонстрирующий подобную ситуацию, приведен на фигуре 8 (в устройстве [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.] нет возможности выполнить несколько шагов 2 на третьем этапе). Следует отметить, что все более широкое применение методов параллельного логического вывода в таких областях, как управление крупными предприятиями, медицинская и техническая диагностика, многокритериальное логическое прогнозирование, приводит к необходимости использовать предикаты с 15-20 и более аргументами, при этом вероятность появления описанной выше ситуации заметно возрастает.

Техническим результатом, достигаемым при использовании предлагаемого изобретения, является сокращение времени унификации предикатов с большой арностью, а также добавление опции унификации пары предикатов, если в одном из них имеется более двух пар одноименных свободных переменных, конкретизируемых в процессе сопоставления разными константами. Данный результат достигается за счет разработки и включения в состав блока унификации набора отдельных, функционально законченных узлов сопоставления термов и узла согласования переменных, необходимого для согласования конкретизируемых переменных и формирования итоговых подстановок.

Введение нескольких узлов сопоставления позволяет выполнять сопоставление всех термов параллельно и снизить влияние арности предикатов на продолжительность операции унификации. Реализована функциональная возможность изменения количества узлов сопоставления с учетом особенностей данных, имеющихся в базе знаний машины логического вывода (арности предикатов, количества предикатов в исходных посылках и т.д.). Благодаря регулярной структуре устройство можно легко реализовать на основе программируемой логической интегральной схемы (ПЛИС) или заказной СБИС.

Технической задачей, на решение которой направлено изобретение, является разработка устройства, значительно сокращающего время унификации предикатов по сравнению с последовательными устройствами за счет параллельной реализации операции сопоставления всех пар термов, а также обладающего возможностью (ресурсами) унифицировать предикаты, когда в одном из предикатов есть более двух пар одноименных свободных переменных, конкретизируемых в процессе сопоставления разными константами. Представленные положения обеспечиваются применением специальных форматов унифицируемых предикатов и их аргументов, введением в состав блока унификации специализированных совместно работающих узлов сопоставления термов, а также узла согласования переменных. Особенностью представления обрабатываемых данных является использование тэгов: 1111 - предикат, 0001 - константа, 0010 - переменная исходного правила (исходной посылки-дизъюнкта), 0011 - переменная выводимого правила (целевого утверждения, запроса), а также уникальных номеров (адресов) таблицы символов для однозначной идентификации обрабатываемых термов. Поле тэгов взято размерностью 4 бита для дальнейшего расширения количества сопоставляемых типов данных, например, за счет введения функторов и списков. Таблица имен хранится во внешней общей памяти.

Структурная схема блока унификации с параллельным сопоставлением термов показана на фигуре 1. Устройство содержит:

1 - внутренняя рабочая память блока унификации (ВРП);

2 - однонаправленная линия связи для загрузки унифицируемых предикатов из внешней памяти по входной шине данных;

3 - однонаправленная линия связи с внешним устройством управления для запуска операции унификации по входной шине управления;

4 - узел управления (УУ);

5 - узел диспетчеризации (УД);

6 - однонаправленная линия связи для управления чтением из внутренней рабочей памяти;

7 - однонаправленная линия связи для передачи имен предикатов;

8 - узел сопоставления имен предикатов;

9 - однонаправленная линия связи для передачи результатов сопоставления имен предикатов;

10 - однонаправленная линия связи для передачи термов;

11 - однонаправленная линия связи для передачи термов;

12 - первый узел сопоставления термов (УСТ);

13 - последний УСТ;

14 - однонаправленная линия связи для передачи переменных;

15 - узел согласования переменных (УСП);

16 - двунаправленная линия связи для управления УСТ;

17 - двунаправленная линия связи для управления УСТ;

18 - однонаправленная линия связи для передачи результатов сопоставления термов;

19 - однонаправленная линия связи для передачи результатов сопоставления термов;

20 - однонаправленная линия связи для передачи подстановок из УСТ;

21 - однонаправленная линия связи для передачи подстановок из УСТ;

22 - однонаправленная линия связи для передачи результата операции согласования переменных в узел управления;

23 - однонаправленная линия связи для выдачи результата унификации на выходную шину управления;

24 - однонаправленная линия связи для выдачи результирующих подстановок на выходную шину данных.

В блоке унификации предусмотрена возможность изменения количества узлов сопоставления термов, что позволяет реализовать параллельное сопоставление всех термов и за счет этого значительно снизить время, затрачиваемое на унификацию предикатов по сравнению с устройством [RU №158945 (U1), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов].

Узел сопоставления имен предикатов выделен в отдельный специализированный элемент, поскольку его структура значительно проще, чем УСТ, и отсутствует необходимость формирования подстановок переменных.

Внутренняя структура узла согласования переменных (15) приведена на фигуре 2. Он содержит:

20 - однонаправленная линия связи для передачи подстановок из УСТ;

21 - однонаправленная линия связи для передачи подстановок из УСТ;

14 - однонаправленная линия связи для передачи переменных;

25 - узел проверки согласованности переменных (УПС);

26 - двунаправленная линия связи для передачи конкретизаций согласуемых переменных;

27 - двунаправленная линия связи для передачи конкретизации: согласуемых переменных;

28 - узел хранения подстановок (УХП);

29 - однонаправленная линия связи для передачи результата согласования пары переменных;

30 - однонаправленная линия связи для передачи результата согласования пары переменных;

40 - узел формирования ошибки при согласовании всех переменных (УФО);

22 - однонаправленная линия связи для передачи результата операции согласования переменных в узел управления;

24 - однонаправленная линия связи для выдачи результирующих подстановок на выходную шину данных.

Узел проверки согласованности переменных представляет собой многокаскадную комбинационную схемы сравнения констант, конкретизирующих одноименные переменные исходного и выводимого правила. Число каскадов определяется по формуле n/2-1, где n - максимально допустимая арность предикатов.

Узел хранения подстановок на основе ассоциативной памяти необходим не только для хранения подстановок, получаемых в процессе выполнения текущей команды унификации, но и для хранения подстановок, полученных ранее при обработке предыдущих команд унификации предикатов выбранного дизъюнкта-посылки (исходного правила) и целевого заключения (выводимого правила). Это позволяет проводить операцию унификации всех термов с учетом ранее принятых замен (конкретизаций) переменных, не тратя на дереференсирование и согласование переменных дополнительное время, весьма значительное, если конкретизации переменных хранятся во внешней памяти.

Узел формирования ошибки формирует сигнал о неуспешном завершении процедуры согласования переменных, если для оной и той же переменной хотя бы один раз встречаются различные значения констант, конкретизирующие эту переменную.

Описание работы блока унификаций двух предикатов В качестве аргументов (атрибутов, термов) предикатов могут выступать переменные (неконкретизированные переменные), поименованные константы (атомы) и числовые константы. Имена констант всегда начинаются с заглавной буквы, а имена переменных - с прописной. Предикатное имя - все буквы заглавные.

Рассмотрим пример организации таблицы имен (фигура 3) и внутренней рабочей памяти (фигура 4) для команды унификации двух предикатов АВТОМОБИЛЬ (Лада веста, х, у, z, z, Красный, х) и АВТОМОБИЛЬ (u, v, 43, к785не, к875не, Красный, Иванов). Предикат АВТОМОБИЛЬ имеет семь термов: модель автомобиля, фамилия владельца, код региона регистрации автомобиля, передний государственный регистрационный номер, задний государственный регистрационный номер, цвет автомобиля и фамилия водителя (за рулем в настоящий момент времени). В данном примере первый предикат характеризует автомобиль Лада Веста серебристого цвета, а владелец, код региона и государственные номера задаются переменными х, у и z соответственно, которые могут уточняться в дальнейшем. Для второго предиката известны: код региона, номера и цвет автомобиля, фамилия водителя, а владелец и модель автомобиля не определены - переменные u и v могут уточняться в дальнейшем ( - переменная выводимого правила). С учетом введенных тэгов (см. выше), структура первого предиката будет занимать первые пять ячеек рабочей памяти (фигура 4, ячейки с адреса 000 по 007), второй предикат - ячейки с 008 по 015. По правилам, введенным в теории логического программирования, предикаты с одинаковым именем, всегда должны иметь одинаковую арность (количество термов).

Рассмотрим пример организации таблицы подстановок в УСП (фигура 5). Сначала (столбцы 3 и 4) указывается тэг и номер заменяемой переменной, а в конце (столбцы 5 и 6) - новое значение переменной.

Алгоритм выполнения операции, параллельной унификации термов двух предикатов на заявляемом устройстве, состоит из следующих этапов (см. фигуру 1).

Этап 0. Во внутреннюю рабочую память 1 по линии связи 2 загружаются два предиката - сложноструктурированные группы тэгированных данных. По линии связи 3 в узел управления 4 поступает сигнал о начале выполнения операции унификации.

Этап 1. Узел диспетчеризации 5 по линии связи 6 посылает команду на чтение из внутренней рабочей памяти 1:

- имен предикатов по линии связи 7 в узел сопоставления имен предикатов 8;

- термов предикатов (первый, второй, третий, ... и т.д.) попарно по линиям связи 10 и 11 в узлы сопоставления термов 12 и 13 соответственно.

Этап 2. На узлах сопоставления 8, 12-13 производится параллельная асинхронная процедура сопоставления указанных аргументов.

Если имена предикатов не совпадают, то из узла сопоставления 8 по линии связи 9 в узел управления 4 поступает сигнал - «0». В противном случае поступает сигнал «1».

При сопоставлении термов возможны следующие ситуации:

- если унифицируется пара «константа-константа» и имена констант не совпадают, то из узла сопоставления 12 (13) по линии связи 18 (19) в узел управления 4 поступает сигнал «0». В противном случае поступает сигнал «1»;

- если унифицируется пара «переменная-константа» (или «константа-переменная»), то из узла сопоставления 12 (13) по линии связи 18 (19) в узел управления 4 поступает сигнал «1», а в узел сопоставления переменных 15 по линии связи 20 (21) - сформированная при сопоставлении термов подстановка переменной;

- если унифицируется пара «переменная-переменная», причем одна из них является переменной выводимого правила, то из узла сопоставления 12 (13) по линии связи 18 (19) в узел управления 4 поступает сигнал «1», а в узел сопоставления переменных 15 по линии связи 20 (21) - сформированная при сопоставлении термов подстановка (переменная выводимого правила является «заменяемой переменной»).

Пример организации таблицы подстановок после второго этапа унификации вышеуказанных предикатов АВТОМОБИЛЬ приведен на фигуре 5.

Если в результате сопоставления имен предикатов или какой-либо пары термов в узел управления 4 поступил хотя бы один «0», то операция унификации останавливается и по линии связи 23 выдается сигнал («0») о неуспешном завершении операции.

Этап 3. Если в результате сопоставления имен предикатов и всех пар термов в узел управления 4 поступили сигналы «1», то в узле сопоставления переменных 15 производится процедура согласования конкретизированных переменных, состоящая из следующих шагов:

- шаг 1. Сравниваются все конкретизации одноименных переменных константами (см. фигура 5, столбцы «Заменяемая переменная» и «Новое значение»). Если в столбце «Новое значение» хотя бы один раз встречаются различные значения констант для оной и той же переменной, то в узел управления 4 по линии связи 22 подается сигнал «0» о неуспешном завершении процедуры согласования переменных. Если все записи конкретизируются одной и той же константой, то в ассоциативной памяти подстановок остается только одна (первая) запись о замене этой переменной соответствующей константой, а остальные записи удаляются.

- шаг 2. Во всех парах «переменная-переменная» аргументы - переменные заменяются на имеющиеся в других записях конкретизации соответствующими константами. Причем, если в паре заменяется на константу только переменная выводимого правила (столбец «Заменяемая переменная»), а переменная исходного правила нет (столбец «Новое значение»), то ячейки (содержимое ячеек) в столбцах «Заменяемая переменная» и «Новое значение» такой записи меняются местами.

Если для какой-либо записи в столбцах «Заменяемая переменная» и «Новое значение» встречаются две константы с различными значениями (именами), то в узел управления 4 по линии связи 22 подается сигнал «0» о неуспешном завершении процедуры согласования переменных. Записи с двумя одинаковыми константами удаляются для уменьшения объема информации, хранимой в таблице подстановок.

В процессе унификации предикатов с большим числом пар одноименных переменных может потребоваться выполнить несколько подобных шагов. Худший случай, т.е. наибольшее количество шагов 2 на третьем этапе согласования двух n-местных предикатов, можно получить при наличии в одном предикате n/2 пар одноименных свободных переменных, а в другом предикате (n/2-l) пар одноименных свободных переменных. Число шагов 2 в этом случае будет равно (n/2-l).

- шаг 3. Сравниваются все конкретизации одноименных переменных константами (см. фигура 5, столбцы «Заменяемая переменная» и «Новое значение»). Если в столбце «Новое значение» хотя бы один раз встречаются различные значения констант, то в узел управления 4 по линии связи 22 подается сигнал «0» о неуспешном завершении процедуры согласования переменных. Если все записи конкретизируются одной и той же константой, то в ассоциативной памяти подстановок остается только одна (первая) запись о замене этой переменной соответствующей константой, а остальные записи удаляются, а в узел управления 4 по линии связи 22 подается сигнал «1» об успешном завершении процедуры согласования переменных.

Этап 4. Если процедура согласования конкретизированных переменных завершилась неуспешно (из узла согласования переменных 15 по линии связи 22 поступил сигнал «0»), то узел управления 4 по линии связи 23 выдает сигнал «0», означающий невозможность унификации анализируемой пары предикатов. Если процедура согласования конкретизированных переменных завершилась успешно (из узла согласования переменных 15 по линии связи 22 поступил сигнал «1»), то узел управления 4 по линии связи 23 выдает сигнал «1», означающий успешное окончание операции унификации пары предикатов. При этом из узла согласования переменных 15 по линии связи 24 выдаются замены всех переменных, полученные при унификации указанной пары предикатов.

Пример 1 (фиг. 6) демонстрирует случай успешного завершения процедуры согласования переменных - все пары отмечены (1), и унификации предикатов в целом. В узел управления 4 из узла формирования подстановок посылается сигнал «1». Конкретизации переменных (подстановки) получены на этапе 3, шаг 1.

Пример 2 (фиг. 7) демонстрирует случай неуспешного завершения процедуры согласования переменных на третьем шаге третьего этапа и унификации предикатов в целом. Шаг 2 третьего этапа достаточно выполнить однократно.

Пример 3 (фиг .8) демонстрирует случай неуспешного завершения процедуры согласования переменных на третьем шаге третьего этапа и унификации предикатов в целом. Однако второй шаг третьего этапа при этом необходимо выполнить дважды, что алгоритмом функционирования (и ресурсами) устройства [4] не предусмотрено.

Пример 4 (фиг. 9) демонстрирует случай неуспешного завершения процедуры согласования переменных на третьем шаге третьего этапа. Однако второй шаг третьего этапа при этом необходимо выполнить трижды, что алгоритмом функционирования (и ресурсами) устройства [4] также не предусмотрено.

Минимальное повышение производительности заявляемым устройством можно оценить следующим образом. Будем считать, что унифицируемые предикаты загружены во внутреннюю память заранее и отсчет времени ведется с момента поступления сигнала запуска (т.е. без учета этапа 0). Время выполнения этапов 1, 2, 4, а также каждого шага этапа 3 (потребуется только в том случае, если в сопоставляемой паре термов имеется хотя бы одна переменная) будем называть тактом работы устройства.

Для сравнения возьмем устройства [RU №158945 (Ul), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] и [4]. Этапы 1, 2 и 4 на них выполняются также за один такт каждый. В устройстве [RU №158945 (U1), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] для поиска и возможного согласования (дереференсирования) переменной в памяти подстановок потребуется 6 тактов (в случае необходимости согласования) или 4 такта (в случае отсутствия в памяти подстановок предыдущих конкретизаций анализируемой переменной). Таким образом, минимально возможное время унификации будет 3 такта - если в унифицируемой паре предикатов в качестве самых первых термов используются константы с разными именами (значениями). В устройстве [4] и заявляемом устройстве это время также равно 3 тактам.

В устройстве [RU №158945 (U1), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] унификация для примера 1 (фиг. 6) выполнится за 45 тактов: считывание имен предикатов (1 такт); сопоставление имен предикатов (1 такт); считывание первой пары аргументов (1 такт); сопоставление первой пары аргументов (1 такт); считывание второй пары аргументов (1 такт); сопоставление второй пары аргументов (1 такт); попытка согласования переменной v (4 такта); попытка согласования переменной х (4 такта); считывание третьей пары аргументов (1 такт); сопоставление третьей пары аргументов (1 такт); попытка согласования переменной у (4 такта); считывание четвертой пары аргументов (1 такт); сопоставление четвертой пары аргументов - (1 такт); попытка согласования переменной z (4 такта); считывание пятой пары аргументов (1 такт); сопоставление пятой пары аргументов (1 такт); согласование переменной z - (6 тактов); считывание шестой пары аргументов (1 такт); сопоставление шестой пары аргументов (1 такт); считывание седьмой пары аргументов (1 такт); сопоставление седьмой пары аргументов (1 такт); согласование переменной х (6 тактов); выдача результатов (1 такт).

В устройстве [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.] - за 4 такта (Этап 1; Этап 2; Этап3_шаг 1; Этап 4).

В заявляемом устройстве - также за 4 такта (Этап 1; Этап 2; Этап 3_шаг1; Этап 4).

В устройстве [RU №158945 (U1), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] унификация для примера 2 (фиг. 7) выполнится за 32 такта: считывание имен предикатов (1 такт); сопоставление имен предикатов (1 такт); считывание первой пары аргументов (1 такт); сопоставление первой пары аргументов (1 такт); считывание второй пары аргументов (1 такт); попытка согласования переменной х (4 такта); попытка согласования переменной t (4 такта); считывание третьей пары аргументов (1 такт); сопоставление третьей пары аргументов (1 такт); попытка согласования переменной х (4 такта); попытка согласования переменной s (4 такта); считывание четвертой пары аргументов (1 такт); сопоставление четвертой пары аргументов (1 такт); согласование переменной s (6 тактов); выдача результатов (1 такт).

В устройстве [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.] - за 6 тактов (Этап 1; Этап 2; Этап 3_шаг 1; Этап 3_шаг 2; Этап 3_шаг 3; Этап 4).

В заявляемом устройстве - также за 6 тактов (Этап 1; Этап 2; Этап 3_шаг 1; Этап 3_шаг 2; Этап 3_шаг 3; Этап 4).

В устройстве [RU №158945 (Ul), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] унификация для примера 3 (фиг. 8) выполнится за 52 такта: считывание имен предикатов (1 такт); сопоставление имен предикатов (1 такт); считывание первой пары аргументов (1 такт); сопоставление первой пары аргументов (1 такт); считывание второй пары аргументов (1 такт); попытка согласования переменной х (4 такта); попытка согласования переменной t (4 такта); считывание третьей пары аргументов (1 такт); сопоставление третьей пары аргументов (1 такт); попытка согласования переменной х (4 такта); попытка согласования переменной u (4 такта); считывание четвертой пары аргументов (1 такт); сопоставление четвертой пары аргументов (1 такт); попытка согласования переменной у (4 такта); попытка согласования переменной u (4 такта); считывание пятой пары аргументов (1 такт); сопоставление пятой пары аргументов (1 такт); попытка согласования переменной у (4 такта); попытка согласования переменной s (4 такта); считывание шестой пары аргументов (1 такт); сопоставление шестой пары аргументов (1 такт); согласования переменной s (6 тактов); выдача результатов (1 такт).

В устройстве [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.] - отсутствует возможность полного согласования переменных и, соответственно, корректной унификации предикатов.

В заявляемом устройстве - за 7 тактов (Этап 1; Этап 2; Этап 3_шаг 1; Этап 3_шаг 2.1; Этап 3_шаг 2.2; Этап 3_шаг 2.3; Этап 3_шаг 3; Этап 4).

В устройстве [RU №158945 (U1), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] унификация для примера 4 (фиг.9) выполнится за 72 такта: считывание имен предикатов (1 такт); сопоставление имен предикатов (1 такт); считывание первой пары аргументов (1 такт); сопоставление первой пары аргументов (1 такт); считывание второй пары аргументов (1 такт); попытка согласования переменной х (4 такта); попытка согласования переменной t (4 такта); считывание третьей пары аргументов (1 такт); сопоставление третьей пары аргументов (1 такт); попытка согласования переменной х (4 такта); попытка согласования переменной u (4 такта); считывание четвертой пары аргументов (1 такт); сопоставление четвертой пары аргументов (1 такт); попытка согласования переменной z (4 такта); попытка согласования переменной u (4 такта); считывание пятой пары аргументов (1 такт); сопоставление пятой пары аргументов (1 такт); попытка согласования переменной z (4 такта); попытка согласования переменной v (4 такта); считывание шестой пары аргументов (1 такт); сопоставление шестой пары аргументов (1 такт); по пытка согласования переменной у (4 такта); попытка согласования переменной v (4 такта); считывание седьмой пары аргументов (1 такт); сопоставление седьмой пары аргументов (1 такт); попытка согласования переменной у (4 такта); попытка согласования переменной s (4 такта); считывание восьмой пары аргументов (1 такт); сопоставление восьмой пары аргументов (1 такт); согласование переменной s (6 тактов); выдача результатов (1 такт).

В устройстве [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.] - отсутствует возможность полного согласования переменных и, соответственно, корректной унификации предикатов.

В заявляемом устройстве - за 8 тактов (Этап 1; Этап 2; Этап 3_шаг 1; Этап 3_шаг 2.1; Этап 3_шаг 2.2; Этап 3_шаг 2.3; Этап 3_шаг 3; Этап 4).

Все сравнения приведены для случая, когда предыдущие подстановки переменных находятся во внутренней памяти блока унификации. Для заявляемого устройства это условие выполняется всегда. Для устройства [RU №158945 (U1), G06N 5/04. Заявка: 2015120634/08, 29.05.2015; опубл. 20.01.2016. Блок унификации с последовательным сопоставлением термов] во внутренней памяти хранятся только подстановки, выполненные при унификации текущей пары предикатов обрабатываемых правил-дизъюнктов. Остальные конкретизации хранятся во внешней памяти.

С учетом вышесказанного можно утверждать, что заявляемое устройство многократно снижает время унификации по сравнению с последовательными устройствами, что позволит достичь значительного превосходства по производительности разрабатываемых на его основе специализированных процессоров логического вывода над существующими аналогами. Кроме того, в заявляемом устройстве возможно сопоставление пар предикатов, даже если в одном из предикатов есть более двух пар одноименных свободных переменных, конкретизируемых в процессе сопоставления разными константами, что отличает его от устройства [Заявка на изобретение №2016120823 от 26.05.2016. МПК G06N 5/04. Блок унификации с параллельным сопоставлением термов. Авторы: Мельцов В.Ю., Куваев А.С., Чистяков Г.А., Шипицына А.А.].

Предварительные оценки аппаратной реализации заявляемого устройства на бюджетной ПЛИС Altera Cyclone III свидетельствуют о свободном размещении на кристалле более 100 узлов сопоставления в одном блоке унификации, что дает возможность параллельного сопоставления всех аргументов обрабатываемых предикатов одновременно.

Изобретение относится к вычислительной технике. Технический результат заключается в сокращении времени унификации предикатов, обеспечивается блоком унификации с параллельным сопоставлением термов, содержащим внутреннюю рабочую память, входами соединеную с входной шиной данных, и выходом узла диспетчеризации, а выходы соединены с входом узла сопоставления переменных, входом узла сопоставления имен предикатов и входами узлов сопоставления термов, узел управления входами соединен с входной шиной управления, выходом узла сопоставления переменных, выходом узла сопоставления имен предикатов и выходами узлов сопоставления термов, узел диспетчеризации, входами соединенный с выходами узлов сопоставления термов, а выходы соединены с входом внутренней рабочей памяти и входами узлов сопоставления термов, узел сопоставления имен предикатов входом соединен с выходом внутренней рабочей памяти, а выход соединен с входом узла управления, узлы сопоставления термов, входы которых соединены с выходами внутренней рабочей памяти и выходами узла диспетчеризации, а выходы соединены с входами узла управления, входами узла согласования переменных и входами узла диспетчеризации, узел согласования переменных входами соединенный с выходами узлов сопоставления термов и выходом внутренней рабочей памяти. 9 ил.

Блок унификации с параллельным сопоставлением термов, содержащий внутреннюю рабочую память, входы которой соединены с входной шиной данных и выходом узла диспетчеризации, а выходы соединены с входом узла сопоставления переменных, входом узла сопоставления имен предикатов и входами узлов сопоставления термов, узел управления, входы которого соединены с входной шиной управления, выходом узла сопоставления переменных, выходом узла сопоставления имен предикатов и выходами узлов сопоставления термов, узел диспетчеризации, входы которого соединены с выходами узлов сопоставления термов, а выходы соединены с входом внутренней рабочей памяти и входами узлов сопоставления термов, узел сопоставления имен предикатов, вход которого соединен с выходом внутренней рабочей памяти, а выход соединен с входом узла управления, узлы сопоставления термов, входы которых соединены с выходами внутренней рабочей памяти и выходами узла диспетчеризации, а выходы соединены с входами узла управления, входами узла согласования переменных и входами узла диспетчеризации, отличающийся тем, что дополнительно содержит узел согласования переменных, входы которого соединены с выходами узлов сопоставления термов и выходом внутренней рабочей памяти, а выходы соединены с входом узла управления и выходной шиной данных.