Блок унификации с параллельным сопоставлением термов

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

 

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

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

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

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

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

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

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

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

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

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

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

Устройство содержит следующее:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15 - узел формирования подстановок (УФП)

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

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

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

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

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

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

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

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

В структуру блока унификации введены узлы сопоставления термов (12-13) и предусмотрена возможность изменения их количества, что позволяет реализовать параллельное сопоставлением термов и за счет этого значительно снизить время, затрачиваемое на унификацию в целом. Наличие узла диспетчеризации (5) позволяет балансировать загрузку узлов сопоставления термов в ходе выполнения процедуры унификации, уменьшая время их простоя. Кроме того, возможность вариации количества УСТ позволяет подобрать конфигурацию блока унификации, наиболее эффективно реализующую обработку структур входных данных для конкретной пользовательской задачи.

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

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

Описание работы блока унификаций двух предикатов

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

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

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

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

Этап 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) - сформированная при сопоставлении термов подстановка (переменная выводимого правила является «заменяемой переменной»).

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

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

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

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

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

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

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

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

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

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

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

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

Следует отметить, что традиционные тестовые (искусственные) задачи, используемые для проверки корректности и эффективности различных модификаций классического принципа резолюций (в том числе многочисленных реализаций параллельного Пролога), содержат предикаты с арностью не более 6-7. Однако все более широкое применение методов параллельного логического вывода в таких областях, как управление крупными предприятиями, медицинская и техническая диагностика многокритериальное логическое прогнозирование, приводит к необходимости использовать предикаты с 15-20 и более аргументами. Предварительные оценки аппаратной реализации заявляемого устройства на бюджетной ПЛИС Altera Cyclone III свидетельствуют о свободном размещении на кристалле более 100 узлов сопоставления в одном блоке унификации, что дает возможность параллельного сопоставления всех аргументов обрабатываемых предикатов одновременно.

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

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

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

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

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

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

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

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

узел сопоставления имен предикатов, вход которого соединен с одним из выходов внутренней рабочей памяти, а выход соединен с одним из входов узла управления,

узлы сопоставления термов, входы которых соединены с выходами внутренней рабочей памяти и выходами узла диспетчеризации, а выходы соединены с входами узла управления, входами узла формирования подстановок и входами узла диспетчеризации,

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

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