РАЗРАБОТКА СТРУКТУРЫ УНИВЕРСАЛЬНОЙ МАШИНЫ ЛОГИЧЕСКОГО ВЫВОДА

DEVELOPMENT OF UNVERSAL INFERENCE MACHINE STRUCTURE

Maria Dolgenkova

candidate of technical science, docent, Vyatka State University,

Russia, Kirov

Tatiana Prozorova

lecturer, Vyatka State University,

Russia, Kirov

Gennadiy Chistyakov

candidate of technical science, Vyatka State University,

Russia, Kirov

АННОТАЦИЯ

В работе предлагается структура универсальной машины логического вывода, способной поддерживать одновременное выполнение нескольких методов. Отличительными особенностями структуры является ориентация на логико-потоковую обработку данных с применением data-flow управления, наличие многоуровневой памяти, поддержка параллельной обработки и эвристик, заложенных в реализуемые методы. Структура может быть использована как основа для проектирования и реализации специализированного вычислительного устройства символьной и логической обработки.

ABSTRACT

The paper proposes the universal inference machine structure capable of simultaneous supporting multiple methods. The distinctive features of the structure is to focus on the logical-threading processing with data-flow operations control, the presence of the multilevel memory, support of parallel processing and of heuristics, which is inherent in methods. The structure can be used as a basis for the design and implementation of a specialized computing unit for symbolic and logical data processing.

Ключевые слова: логический вывод; структура машины логического вывода; унификация литералов; процессор команд; исполнительный процессор.

Keywords: logical inference; structure of inference machine; literals unification; instruction processor; executive processor.

Работа выполнена при финансовой поддержке РФФИ (проект № 15-01-02818а)

Введение. Математический аппарат теории логического вывода представляет собой мощный инструмент для решения целого ряда задач, имеющих важное практическое значение [1; 6]. Наиболее критическим недостатком данного аппарата, сдерживающим его применение, является узкая специализированность. Нередко для решения конкретной задачи требуется модификация известного метода, принимающая во внимание особенности предметной области и позволяющая эффективно осуществлять символьную и логическую обработку данных [4].

Как правило, на основе подобной модификации создается специализированное вычислительное устройство – машина логического вывода, физически реализуемое как программный, программно-аппаратный или же полностью аппаратный комплекс [5]. Очевидно, что архитектура машины обусловлена той модификацией метода, выполнение которого данная машина поддерживает. Таким образом, процесс решения реальных задач посредством математического аппарата теории логического вывода сопряжен со значительными временными затратами, связанными с необходимостью проектирование архитектуры.

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

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

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

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

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

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

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

Рисунок 1. Структура универсальной машины логического вывода

В состав процессора команд входят следующие блоки.

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

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

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

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

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

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

Список литературы:

1. Вагин В.Н. Достоверный и правдоподобный вывод в интеллектуальных системах / В.Н. Вагин, Е.Ю. Головина, А.А. Загорянская, М.В. Фомина // – М.: ФизМатЛит, 2008. – 712 с.
2. Долженкова М.Л. Чистяков Г.А. Метод дедуктивного вывода всех следствий // Вестник Тамбовского государственного технического университета, 2015. – Т. 21. № 3. С. 488–495.
3. Страбыкин Д.А. Логическое прогнозирование развития ситуаций в интеллектуальных системах на основе дедуктивного вывода // Киров: Изд-во Вят. гос. Ун-та, 2014. – 182 с.
4. Страбыкин Д.А. Логический вывод в системах обработки знаний // СПб.: Изд-во СПбГЭТУ, 1998. – 164 с.
5. Meltsov V.Yu. High-Perfomance Systems of Deductive Inference // Yelm, WA., USA: Science Book Publishing House, 2014. – 216 p.
6. Russell S.J. Artificial Intelligence: A Modern Approach / S.J. Russell, P. Norvig // Pearson Education, 2009. – 1104 p.