Процессор команд машины логического вывода

Полезная модель относится к вычислительной технике, а именно к устройству управления процессом логического вывода, и может быть использована в машине логического вывода с data-flow архитектурой, реализующей ускоренный метод деления дизъюнктов, также в качестве сопроцессора для преобразования входных сообщений в исполняемые команды. Предлагаемая полезная модель имеет следующие отличительные признаки: в устройство введен регистр сообщений, который связан с очередью сообщений, что позволяет освободить процессор команд от выполнения функции организации доступа к ресурсам и диспетчеризации сообщений; введена ассоциативная память фреймов для ускорения идентификации состояний процессов и связей родитель-потомок; в устройстве отсутствует необходимость генерации сообщений и фреймов процессов, поскольку фреймы процессов формируются исключительно на основании содержимого сообщений, которые поступают извне, что позволяет уменьшить аппаратурные затраты и упростить структуру ПК. Устройство включает регистр сообщений (2), который хранит обрабатываемые сообщения, поступающие из очереди команд; память фреймов (4), которая хранит состояния фреймов процессов, находящихся на обработке в процессоре команд; очередь FIFO (6), которая хранит готовые пакеты команд, предназначенные для передачи в исполнительный процессор машины логического вывода; дешифратор (10); регистр-указатель свободной ячейки памяти фреймов (18); устройство управления распаковкой (12), управляющее процессом дешифрации сообщений; блок управления процессора команд (20), который обрабатывает осведомительные сигналы, генерирует управляющие сигналы и управляет памятью фреймов; устройство управления обменом с шиной (25), управляющее процессом выдачи пакетов команд из очереди FIFO на шину.

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

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

РИСУНКИ