Совершенствование программного обеспечения

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

Учитывая, что задача ускорения вычислений в приложениях искусственного интеллекта приводит даже к созданию специальных параллельных процессоров, было бы неразумно отказаться от прямой трансляции языков в рамках таких процессоров. Здесь пригодится большой объем накопленных знаний о трансляции, открывающих новые возможности для повышения эффективности вычислений. (Отметим, например, более чем 100-кратное различие в скоростях большинства интерпретаторов языка Пролог, написанных на Лиспе, и транслятора с Пролога, созданного Уорреном для машины DEC-20)

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

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

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

Неоднократно отмечалось, что наборы команд типичных компьютеров мало пригодны для создания программного обеспечения систем искусственного интеллекта, однако практически не предпринималось попыток объяснить, почему это так. Что касается машин предыдущих поколений, то отмечались характерные для них жесткие ограничения на адресное пространство и отсутствие достаточной свободы в манипулировании указателям. Но как соотносятся с Лисп-машинами компьютеры, такие, как DEC VAX, Motorola 68000, National Semiconductor 16000 и различные машины с упрощенным множеством команд (RISC)? Стремясь разобраться в проблемах разработки систем команд, я исследовал ряд версий Лиспа и отдельные детали их реализации. В частности, я выяснил, что чрезвычайно важно знать, насколько мощные программные средства желательно иметь в каждом конкретном случае.

Так, вопреки ожиданиям, при выполнении одной большой прикладной программы на компьютере DEC VAX-11/780 диалект Лиспа Franz LISP оказался не на много медленнее, чем Zetalisp, используемый на машине Simbolics 3600 (Первая машина— это так называемая супер-мини общего назначения, а вторая — специально ориентированная на Лисп система). При этом, правда, в Franz LISP были отключены «универсальные» функциональные средства (речь идет, например, об арифметических «универсальных» функциях, в качестве аргумента которых одинаково годятся целые, дробные, действительные и комплексные числа) и почти все проверки типов данных, которые в диалекзе Franz LISP—более бедном программными средствами— отсутствовали. Считая эти возможности важными, я исследовал затраты на их реализацию при различных архитектурах машин.

Гибкая работа Лиспа обеспечивается динамической проверкой типов данных и использованием «универсальных» функций. Хранение в памяти типа объекта вместе с самим объектом ведет к тому, что в процессе работы тип всегда находится под рукой, поэтому при разработке на языке Лисп особенно удобным становится использование меток-признаков. Использование признаков означает, что скорость работы процессора при выполнении «универсальной» задачи на Лиспе зависит от того, насколько эффективно процессор способен имитировать (эмулировать) память с метками.

Таблица 1.Время (в микросекундах) выполнения функции foo на грех диалектах Лиспа шестью различными процессорами
(defun foo(x) (-car х) (cdr х)))

Я провел серию экспериментов по сравнению версий Лиспа, работающих на машинах с различными наборами команд. Для примера в табл. 1 показано время выполнения простой лисповской программы, содержащей ряд стандартных функций, таких, как CAR, CDR, « + », а также операция обращения к функции и возврата.

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

Для трансляции функции foo были использованы существующие трансляторы с диалектов Franz LISP и PSL для компьютеров DEC VAX и Motorola 68000. В целях повышения быстродействия проверка типов была отключена. (Ни Franz LISP, ии PSL не проверяли, являются ли аргументы функции « + » малыми целыми; Franz LISP осуществлял контроль за переполнением, a PSL — нет.) Приведенные в таблице значения продолжительности счета получены путем анализа созданных трансляторами кодов на языке ассемблера с учетом реального времени выполнения их элементов на машине. Значения времени для диалекта Zetalisp на машинах 3600 и CADR установлены из наблюдений за реальными системами.

Операции, подобные тем, что использовались в диалекте Zetalisp на машинах DEC VAX и Motorola 68000, кодировались вручную, а время определялось так же, как для PSL и Franz LISP. Процессоры 68000 и 68010 работали с тактовой частотой 10 МГц в безостановочном режиме. В процессоре 68000 использовалось 24-разрядное адресное пространство, причем 8 старших разрядов в слове отводилось под метки-признаки. В процессоре 68010 использовался 32-разрядный адрес, и, прежде чем использовать слово в качестве адреса, с помощью некоторой команды AND ликвидировались метки. Значения времени для процессора 68020 рассчитывались в предположении об использовании кэшпамяти в соответствии с данными инструкции по этой машине, и они не столь точны, как аналогичные данные для остальных машин. Предполагалось, что процессор 68020 работает с 1 актовой частотой 16 МГц при использовании внешней кэшпамяти объемом в 16 килобайт и специального устройства управления памятью, что обеспечивало время обращения к памяти, равное 185 нс. (Этот процессор имел также небольшую внутреннюю кэш-память.)

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

Говоря точнее, чтобы сделать существующие процессоры более пригодными для Лиспа (так же, как и для языков Пролог, Kripton, MRS, PEARL н т. д.), необходимо осуществление следующих команд и возможностей.

1. «Переход по группе разрядов»: команда выделяет ряд последовательно расположенных разрядов операнда, добавляет эту последовательность к базовому адресу таблицы переходов и осуществляет косвенную передачу управления. Это необходимо для ускорения операций над метками при проверке типов использования «универсальных» функций и при создании унификатора.
2. «Переход по объединению двух групп разрядов»: тс же действия по отношению к двум операндам (необходимость этого вызвана теми же причинами, что и в случае с одним аргументом).
3. Система адресации, используемая процессором, должна исключать старшие разряды адреса. Это позволит использовать старшие разряды 32-разрядного слова для хранения меток.

В программе, подобной той, которую выдает транслятор с диалекта Zetalisp, более 30% времени работы процессора 68000 уходит на эмуляцию команд, подобных описанным выше. Для отделения разрядов, хранящих признаки, требуется примерно 10% времени. Таким образом, согласно оценкам, аппаратная реализация этих возможностей в существующих процессорах  позволила  бы ускоризъ почти вдвое работу диалектов Лиспа (таких, как Zetalisp), осуществляющих проверки типов. Эти оценки получены путем реализации вручную стандартных функций диалекта Zetalisp на существующих микропроцессорах. Например, в распечатке 1 представлена программа на языке ассемблера, реализующая функцию CAR.

Распечатка 1. Лисповская функция CAR диалекта Zetalisp, реализованная на ассемблере для процессора МС68010. Фрагменты программы, заключенные в рамку, могут быть заменены одной командой из расширенного множества команд, что сократит время выполнения программы.

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

На распечатке 2 показана программа, реализующая функцию CAR на процессоре 68010 с днумя усовершенствованиями. Первое состоит в том, что 7 старших разрядов адреса игнорируются системой виртуальной памяти. Второе заключается в том, что добавлена команда «переход по группе разрядов». Эта команда выделяет последовательность битов из второго аргумента так, как указано в первом аргументе (формат: <#первый-разряд, ширина-поля>), суммирует эту последовательность с третьим аргументом (базовый адрес таблицы переходов) и осуществляет косвенную передачу управления по этому адресу. [Процессор 68020 имеет быстродействующую команду выделения битов. Это обеспечивает его большое превосходство в скорости (по сравнению со старым процессором 68000) при выполнении лисповской программы, что видно из табл. 1.]

Распечатка 2. Распечатка, сделанная в предположении, что в систему команд процессора внесены изменения.

В новых компьютерах, разрабатываемых специально для систем искусственного интеллекта, все эти возможности могут быть реализованы аппаратно. При использовании архитектуры, связанной с метками, многие  "универсальные" операции, например сложение, не требуют обращения к подпрограмме. Вместо этого процессор может проверить метки аргументов операции сложения и, если они являются простыми целыми числами, просто выполнить сложение. Если же аргументы выражаются числами более сложного вида, то процессор организует программное прерывание, передавая управление определенной подпрограмме. Кроме того, в новых типах машин было бы полезно иметь возможность быстро прослеживать косвенные ссылки, как это сделано в машине DEC PDP-10 и в специальных Лисп-машинах.

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

Изучение «заказной» системы команд компьютера FAIM-1 показало, что работа одного процессора может тормозиться памятью DRAM (dynamic random-access read/write memory — динамическая память произвольного доступа); более того, это имеет место даже при использовании большой кэш-памяти, что весьма существенно. Он говорит о том, что создание параллельно работающих машин, использующих одну большую общую память,— неверный путь, ибо доступ к памяти будет сдерживать их работу.