Интеллектуальная система управления знаниями об оптимизации программ

Размещено на http://www.allbest.ru/

Интеллектуальная система управления знаниями об оптимизации программ

М.А. Князева

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

Введение

В настоящее время задача увеличения производительности компьютеров по-прежнему остаётся актуальной [Воеводин и др., 2002], [Касьянов, 1988]. С усложнением архитектуры компьютеров усложняются и языки программирования, что влечет за собой снижение качества как исходных, так и объектных программ. Поэтому, чтобы не потерять выигрыш, полученный за счет возможностей новых архитектур компьютеров, необходимо улучшать исходные программы и совершенствовать компиляторы языков программирования.

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

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

Указанные недостатки заставляют искать новые подходы к построению модифицируемых оптимизирующих компиляторов, в которых наборы преобразований, а также наборы языков представления программ и целевые платформы не являлись бы фиксированными. Таким подходом является интеллектуальная система, моделирующая процесс преобразования программ, управляемый знаниями. Информационное обеспечение и доступ к системе осуществляется специализированным банком знаний о преобразованиях компьютерных программ (СБкЗ_ПП - далее банк знаний) [Клещев и др., 2005a, 2005b], [Князева, 2004a], [Knyazeva et al., 2006].

1. Архитектура интеллектуальной системы управления знаниями об оптимизации программ

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

Банк знаний состоит из блока администрирования (БА), информационного наполнения (ИН), оболочки ИН и программного наполнения (ПН).

Блок администрирования банка знаний предназначен для администрирования. Функции по управлению пользователями и информационными ресурсами выполняет администратор банка знаний.

Информационное наполнение состоит из: онтологии знаний о преобразованиях программ, онтологии (описания абстрактного синтаксиса) языков программирования; онтологии моделей структурных программ (МСП); онтологии знаний о потоковом анализе; онтологии знаний о целевых платформах. Также в информационном наполнении банка знаний хранятся: база знаний о преобразованиях программ; база программ в терминах онтологий языков программирования, предназначенная для хранения исходных программ; база программ в терминах онтологии МСП; база знаний о потоковом анализе программ; база знаний о целевых платформах, а также архив историй преобразований программ и отчетов по качеству процесса оптимизации программ.

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

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

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

Средства редактирования включают: редактор знаний о преобразованиях программ, редакторы программ на языках программирования, редактор МСП, редактор знаний о потоковом анализе программ, редактор знаний о целевых платформах, которые создаются с использованием редактора информации различных уровней общности (ИРУО) [Орлов и др., 2006].

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

Создание, редактирование, а также сохранение программ на различных языках программирования в базе программ осуществляется соответствующими редакторами программ, каждый из которых ориентирован на определенный язык программирования. Каждый редактор является структурным, а процесс редактирования программ с помощью соответствующего редактора осуществляется в рамках модели онтологии языка программирования, на который ориентирован редактор [Князева и др., 2005b].

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

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

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

Исходными данными для преобразователя является МСП и набор преобразований, выбранных пользователем через подсистему управления. Каждое преобразование состоит из формулы контекстного условия и формулы трансформации. Результатом работы преобразователя является исходная МСП и преобразованная согласно указанным преобразованиям.

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

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

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

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

Средства визуализации историй преобразований программ и отчетов по качеству процесса оптимизации программ позволяют просмотреть историю применения преобразований программ.

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

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

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

Специализированный банк знаний можно использовать для разработки макетов оптимизирующих компиляторов управляемых знаниями об оптимизации программ [Князева, 2005c]. Создатель макета выбирает язык программирования из множества языков, редакторы которых существуют в банке, генератор кода на нужную ему платформу из множества генераторов, которые существуют в банке, набор оптимизирующих преобразований программ из базы знаний и задает стратегию применения этих преобразований. Если задан пустой набор оптимизирующих преобразований программ из базы знаний, то макет компилятора будет неоптимизирующим. Разработка макетов оптимизирующих компиляторов открывает возможность для проведения исследований стратегий и наборов преобразований программ в таких компиляторах.

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

Специализированный банк знаний о преобразованиях программ, можно использовать для поддержки процесса обучения студентов. Через такие действия, как решение задач и исследование, обучаемые могут подойти к пониманию предмета - преобразований программ. Задача банка заключается в обеспечении всесторонней обратной связи в процессе обучения и предоставлении возможности получить практические навыки формализации и использования знаний, а роль преподавателя заключается в оценке окончательного результата. Для лучшего усвоения знаний разработан учебно-методический комплекс по дисциплине “Теория вычислительных процессов и структур II. Теория и методы трансляции” и “Оптимизация программ” для студентов, обучающихся по специальности 351500 - математическое обеспечение и администрирование информационных систем [Князева, 2006d]. Учебно-методический комплекс включает: указания по работе с комплексом; нормативное обеспечение: рабочую учебную программу, методические указания по самостоятельному освоению дисциплины; информационно-методическое обеспечение: основное учебное издание, глоссарий, лабораторные работы и рекомендации по их выполнению, список основной и дополнительной литературы, информационных и справочных источников, каталог образовательных ресурсов в сети Интернет; средства педагогического контроля: списков вопросов к коллоквиумам, зачетам и экзаменам; тестовые задания.

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

1. [Воеводин и др., 2002] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ_Петербург, 2002.

2. [Касьянов, 1988] Касьянов В.Н. Оптимизирующие преобразования программ.- Москва: Наука, 1988.

3. [Клещев и др., 2005a] Клещев А.С., Князева М.А. Управление информацией о преобразованиях программ. I. Анализ проблем и пути их решения на основе методов искусственного интеллекта // Изв. РАН. ТиСУ. 2005. № 5.

4. [Клещев и др., 2005b] Клещев А.С., Князева М.А. Управление информацией о преобразованиях программ. II. Внутреннее устройство специализированного банка знаний о преобразованиях программ // Изв. РАН. ТиСУ. 2005. № 6.

5. [Князева, 2004a] Князева М.А. Банк знаний о преобразованиях компьютерных программ // Искусственный интеллект. 2004. Т. 3.

6. [Князева и др., 2005b] Князева М.А., Тимченко В.А. Структурные редакторы программ на языках программирования высокого уровня и генератор моделей структурных программ в банке знаний о преобразованиях программ // Искусственный интеллект. 2005. Т.4.

7. [Князева, 2005c] Князева М.А. Оптимизирующие компиляторы, управляемые базами знаний // Информационные технологии. 2005. № 12.

8. [Князева, 2006d] Князева М.А. Учебно-методический комплекс «Оптимизация программ» // Компьютерные учебные программы и инновации. 2006. № 4. http://www.ofap.ru.

9. [Орлов и др., 2006] Орлов В.А., Клещев А.С. Компьютерные банки знаний. Многоцелевой банк знаний // Информационные технологии. 2006. №2.

10. [Knyazeva et al., 2006] Knyazeva M., Kleshchev A. A Web-system for Computer Experiments in the Field of Program Transformations // IJ ITA. 2006. Vol.13.Nо. 4.

Размещено на Allbest.ru