ПРОЦЕССОР КОМАНД МАШИНЫ ЛОГИЧЕСКОГО ВЫВОДА

Название	ПРОЦЕССОР КОМАНД МАШИНЫ ЛОГИЧЕСКОГО ВЫВОДА
Разработчик (Авторы)	Мельцов Василий Юрьевич, Тарасов Александр Викторович, Караваев Михаил Альбертович, Чистяков Геннадий Андреевич
Вид объекта патентного права	Полезная модель
Регистрационный номер	144233
Дата регистрации	10.08.2014
Правообладатель	Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Вятский государственный университет" (ФГБОУ ВПО "ВятГУ")
Область применения (класс МПК)	G06N 5/04 (2006.01)

Описание изобретения

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

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

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

Из источника [1, с. 125-127] известен процессор команд, который реализует следующие этапы обработки команд: выборку команд, буферизацию, распаковку, организацию очереди распакованных команд, формирование исполнимых команд. Данный процессор команд состоит из следующих блоков: входные регистры, кольцевой буфер, устройство управления обменом с шиной, устройство управления опережающей выборкой, дешифратор, селектор, регистр адреса данных в основной памяти, устройство управления распаковкой, очередь FIFO (FIFO - принцип технической обработки очереди или обслуживания конфликтных требований путем упорядочения процесса по принципу: «первым пришел - первым обслужен»), блок переходов, счетчик адреса, устройство управления обменом с блоком микропрограммного управления. Объектная Пролог-команда по шине поступает во входные регистры, далее - в кольцевой буфер. Код операции однозначно идентифицирует команду и определяет ее длину (число байт) и формат. Формирование длины команды, количества и размера операндов в байтах, выделение команд по коду операции выполняет дешифратор. Выборку кода операции и данных из регистров кольцевого буфера выполняет селектор. Устройство управления распаковкой управляет очередью FIFO для распаковки команд. Блок переходов предназначен для формирования значения счетчика команд, адресов безусловных переходов и загрузки счетчика адреса этими значениями. Управление процессором команд осуществляет устройство управления обменом с блоком микропрограммного управления.

Данное устройство имеет следующие недостатки. Во-первых, в процессоре команд большое число регистров общего назначения (ΡΟΗ), хранящих одну и ту же информацию. Например, код операции хранится в регистре старшей части команды RGH, одном из четырех регистров кольцевого буфера, регистре кода операции COD. Это приводит к неоправданному увеличению аппаратурных затрат, а перезапись данной информации из одного регистра в другой - к снижению быстродействия процессора.

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

Технический результат от использования заявляемой полезной модели заключается в увеличении быстродействия процессора посредством повышения скорости формирования исполняемых команд, а также в сокращении аппаратурных затрат процессора и, соответственно, упрощении конструкции устройства. Технический результат достигается за счет использования системы команд, включающей четыре типа команд (операторов) и применения нетрадиционной архитектуры с потоковым принципом управления. Данный принцип управления позволяет выполнять команды в произвольном порядке, что приводит к отказу от адресной памяти и введению ассоциативного обращения к динамической и статической области памяти ПК. Таким образом, процессор команд включает в себя следующие блоки: регистр сообщений, память фреймов, очередь FIFO, дешифратор, регистр-указатель свободной ячейки памяти фреймов, устройство управления распаковкой, блок управления процессора команд, устройство управления обменом с шиной. Кроме того, технический результат достигается за счет использования только прямой адресации при формирования адресов операндов в МЛВ, реализующей ускоренный метод дедуктивного вывода делением дизъюнктов, описанный в источнике [2, с. 28-35]. Это позволяет применить данную полезную модель в машине логического вывода в качестве сопроцессора для преобразования входных сообщений в пакеты исполняемых команд, а также исследовать эффективность функционирования сопроцессоров и спецвычислителей с data-flow архитектурой.

Описание работы процессора команд машины логического вывода

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

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

1 - однонаправленная линия связи от очереди сообщений к регистру сообщений 2;

2 - регистр сообщений;

3 - однонаправленная линия связи от регистра сообщений 2 к памяти фреймов 4;

4 - память фреймов;

5 - однонаправленная линия связи от памяти фреймов 4 к очереди FIFO 6;

6 - очередь FIFO;

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

8 - однонаправленная линия связи от устройства управления распаковкой 12 к регистру сообщений 2;

9 - однонаправленная линия связи от регистра сообщений 2 к дешифратору 10;

10 - дешифратор;

11 - однонаправленная линия связи от дешифратора 10 к устройству управления распаковкой 12;

12 - устройство управления распаковкой;

13 - однонаправленная линия связи от блока управления процессора команд 20 к устройству управления распаковкой 12;

14 - однонаправленная линия связи от устройства управления распаковкой 12 к блоку управления процессора команд 20;

15 - однонаправленная линия связи от памяти фреймов 4 к блоку управления процессора команд 20;

16 - однонаправленная линия связи от блока управления процессора команд 20 к памяти фреймов 4;

17 - однонаправленная линия связи от регистра-указателя свободной ячейки памяти фреймов 18 к памяти фреймов 4;

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

19 - однонаправленная линия связи от блока управления процессора команд 20 к регистру-указателю свободной ячейки памяти фреймов 18;

20 - блок управления процессора команд;

21 - однонаправленная линия связи от устройства управления обменом с шиной 25 к блоку управления процессора команд 20;

22 - однонаправленная линия связи от блока управления процессора команд 20 к устройству управления обменом с шиной 25;

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

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

25 - устройство управления обменом с шиной.

На начальном этапе в процессор команд последовательно посылаются два сообщения: CREATE V и CREATE ANSWER. После чего в памяти фреймов 4 создаются фреймы двух процессов: V-процесса и процесса ANSWER. V-процесс (выполняет один шаг логического вывода) находится в состоянии READY (готов к выполнению), поскольку получает в качестве готовых операндов адрес системы исходных правил и адрес выводимого правила. Процесс ANSWER (выдает положительное решение задачи логического вывода, либо сообщает о неудачном завершении процесса) находится в состоянии WAIT (ожидание), поскольку ожидает ответа (решения) от V-процесса. Универсальный формат фрейма любого процесса приведен на фиг. 2. Размещение фреймов в памяти 4 осуществляется с помощью регистра-указателя первой свободной ячейки памяти фреймов 18.

Поскольку после этапа компиляции в памяти фреймов имеется процесс готовый к выполнению (V-процесс, бит готовности "1"), то необходимо создать пакет исполняемой команды. Формат пакета команды показан на фиг. 3. Первым операндом для V-процесса является адрес системы исходных посылок в памяти операндов. Второй операнд содержит адрес выводимого правила. А третий операнд - адрес размещения ответа для данной системы правил (ответом может быть "0" - вывод завершен или "1" - вывод невозможен). Информация в поле DES указывает на фрейм обрабатываемого процесса, и она необходима для формирования адреса назначения в сообщениях CREATE и END. Пакет исполняемой команды по линии связи 5 помещается в очередь FIFO 6, из которой по линии связи 7 поступает на шину команд.

В большинстве случаев процесс логического вывода выполняется за несколько шагов. Поэтому обработка команды (V-оператора) на исполнительном процессоре скорее всего завершится порождением N-процессов потомков. В очередь сообщений поступит один (иногда несколько) пакет CREATE N (сформировать команду полного деления дизъюнктов для получения конечного остатка [2, с. 88-95]). Формат сообщения CREATE (создание и активация процесса-наследника) приведен на фиг. 4. В нем указаны тип создаваемого процесса (N), адрес операнда (базового правила), адрес размещения ответа, и номер фрейма в памяти фреймов 4, которому необходимо возвратить ответ (решение) N-процесса. Получив сообщение CREATE, блок управления процессора команд 20 увеличивает на «1» содержимое поля CT (счетчика) в фрейме процесса-родителя, пославшего данное сообщение и переводит его в состояние WAIT (ожидание). Далее блок управления создает новый фрейм для процесса, тип которого указан в контексте сообщения (значение регистра-указателя свободной ячейки памяти фреймов при этом также увеличивается на 1), заполняет поля операндов порождаемого процесса и сохраняет адрес возврата RET. Поскольку все аргументы созданного процесса известны (для N-процесса: адрес исходного правила, адрес выводимого правила и адрес размещения ответа), то бит готовности устанавливается в "1", и готовый пакет команды посылается в очередь FIFO 6 по линии связи 5.

Новая команда (N-оператор) при первом исполнении породит сообщение CREATE M - сформировать команду (процесс) частичного деления дизъюнктов [2, с. 85-88]. В памяти фреймов 4 будет создан фрейм M-процесса, операндами которого будут указаны: адрес матрицы «производных» базового дизъюнкта-посылки, адрес размещения литералов фактов, и адрес дизъюнкта-заключения, участвующего в образовании остатков. После этого будет скомпонована исполнительная команда (M-оператор). Процесс N переводится в состояние WAIT.

Если выполнение M-оператора завершится успешно, в очередь сообщений ПК поступит сообщение END (передача ответа-решения процессу-предшественнику), формат которого приведен на фиг. 5. В сообщении указывается тип процесса, завершившего вычисления, и адрес назначения, т.е. номер фрейма-родителя, которому адресовано данное сообщение. Сообщение из очереди поступает в регистр сообщений 2 по линии связи 1. Затем сообщение по линии связи 9 поступает на дешифратор 10, и уже в раскодированном виде передается по линии связи 11 в устройство управления распаковкой команды 12. Осведомительные сигналы из блока 12 по линии связи 14 поступают в блок управления процессора команд 20.

N-процесс родитель (его адрес находится в поле DES сообщения), получив результат выполнения М-процесса потомка, переводится из состояния WAIT в состояние READY. Бит повторного входа S устанавливается в единицу и формируется вновь N-команда (N-оператор).

Если выполнение N-оператора завершится успешно, в очередь сообщений ПК поступит сообщение END (передача ответа-решения V-процессу предшественнику). В фрейме соответствующего V-процесса заполнится поле OPR3 адресом размещения ответа (решения), бит S установится в 1, и будет сформирована команда (V-процесс).

После выполнения последнего V-процесса на ПК придет сообщение END с указанием адреса ячейки, где размещен результат логического вывода для системы исходных посылок и выводимого правила. Этот адрес будет помещен в поле операнда процесса ANSWER, который и выдаст его пользователю, ожидающему решение. Процесс логического вывода завершен.

Благодаря достаточно простой и регулярной структуре процессора команд имеется возможность аппаратной реализации данного устройства на ПЛИС или заказной СБИС.

Источники информации

1. Вишняков, В.А. Аппаратно-программные средства процессоров логического вывода [Текст] / В.А. Вишняков, Д.Ю. Буланже, О.В. Герман. - М.: Радио и связь, 1991. - 264 с.

2. Страбыкин, Д.А. Логический вывод в системах обработки знаний [Текст] / Д.А. Страбыкин; под ред. Д.В. Пузанкова. - СПб.: Изд-во СПбГЭТУ, 1998. - 164 с.

Формула полезной модели

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

Изобретение "ПРОЦЕССОР КОМАНД МАШИНЫ ЛОГИЧЕСКОГО ВЫВОДА" (Мельцов Василий Юрьевич, Тарасов Александр Викторович, Караваев Михаил Альбертович, Чистяков Геннадий Андреевич) отмечено юбилейной наградой (25 лет Российской Академии Естествознания)
Медаль Альфреда Нобеля

Оформление наградных документов и заказ каталога