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

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