Управление преобразованиями программ с переменным набором трансформаций
На правах рукописи
КНЯЗЕВА МАРГАРИТА АЛЕКСАНДРОВНА УПРАВЛЕНИЕ ПРЕОБРАЗОВАНИЯМИ ПРОГРАММ С ПЕРЕМЕННЫМ НАБОРОМ ТРАНСФОРМАЦИЙ Специальность 05.13.01 – Системный анализ, управление и обработка информации Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей
Автореферат диссертации на соискание ученой степени доктора технических наук
Владивосток - 2009 г.
2
Работа выполнена в Лаборатории интеллектуальных систем Института автоматики и процессов управления Дальневосточного отделения РАН и в ГОУ высшего профессионального образования «Дальневосточный государственный университет» (ДВГУ)
Научный консультант: доктор физико-математических наук, профессор Клещев Александр Сергеевич
Официальные оппоненты: член-корреспондента РАН, доктор физико-математических наук, Смагин Сергей Иванович доктор физико-математических наук, профессор Касьянов Виктор Николаевич доктор технических наук, профессор Вагин Вадим Николаевич
Ведущая организация: Вычислительный центр имени А.А. Дородницына РАН (г. Москва)
Защита состоится « 25 » сентября 2009 г. в 10 часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.
С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН.
Автореферат разослан « » 200 г.
Ученый секретарь диссертационного совета Д 005.007.01, к.т.н.
Лебедев А.В.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы. При решении различных задач управления техническими объектами исследователям часто приходится решать проблему оптимального сочетания их аппаратных возможностей с соответствующим программным обеспечением. Эта проблема особенно актуальна для обеспечения эффективности управления суперкомпьютерами, поскольку для ее решения необходимо учитывать как многообразие архитектур суперкомпьютеров, так и анализировать особенности представления и обработки больших объемов информации. Поэтому актуальными являются исследования, направленные на разработку качественных компьютерных программ, как одного из важнейших факторов, обеспечивающих управление современных компьютерных систем.
Большой вклад в разработку и исследование программ внесли российские и зарубежные учёные: С.М. Абрамов, В.В. Воеводин, Вл.В. Воеводин, В.Ю.
Волконский, В.М. Глушков, Б.А. Головкин, В.А. Евстигнеев, А.П. Ершов, В.П.
Иванников, В.Э. Иткин, В.Н. Касьянов, В.Е. Котов, С.Л. Кривой, В.П. Кутепов, А.А.
Ляпунов, С.С. Лавров, А.А. Летичевский, Э.З. Любимский, В.В. Мартынюк, А.С.
Нариньяни, В.А. Непомнящий, И.В. Поттосин, Р.И. Подловченко, В.К. Сабельфельд, В.А. Серебряков, А.А. Терехов, Э.А. Трахтенгерц, Г.С. Цейтин, Ю.И.Янов, Ф.Э.
Аллен, Д.Ф. Бэкон, М. Вольф, Дж. Кок, Г. Килделл, П. Кузо, М. Лэм, Д. Падуа, К–В.
Ценг, Дж. Т. Шварц и многие другие.
На основе теоретических моделей программ сформулировано и обосновано большое число их преобразований. Одним из подходов к преобразованиям программ является трансформационный подход, при котором разрабатываемая программа создаётся путём преобразования из других программ за счет применения набора трансформаций, к которым относятся трансляция программ, их оптимизация и распараллеливание, реинжениринг программ при их переносе в новое операционное окружение, модификация программ при их сопровождении и др.
Основная цель использования таких преобразований – это повышение качества программ.
Однако, общий метод построения набора трансформаций отсутствует, поэтому наборы строятся на эвристической основе. Исследования эффективности применения одного фиксированного набора трансформаций при заданной стратегии их применения проводились неоднократно. Проведение исследований эффективности переменных наборов преобразований программ связано с рядом проблем. Одна из проблем заключается в том, что системы, разработанные и/или разрабатываемые для изучения порядков преобразований, позволяют проводить исследования программ только на тех языках, которые в них поддерживаются, и только с такими наборами трансформаций, которые хранятся в библиотеке трансформаций во внутреннем представлении, а их модификация является трудоемким процессом.
Другой проблемой для исследования набора трансформаций является включение новых трансформаций в набор. Единой инструментальной среды, обеспечивающей все шаги процесса интеграции знаний о преобразованиях программ, не существует, а имеющиеся системы обладают рядом ограничений, уменьшающих эффективность их практического использования. Это связано с отсутствием единого подхода к представлению знаний в этой области. Общей идеей, гарантирующей подход к такому представлению, является онтологический подход.
Большой вклад в разработку и исследование онтологического подхода внесли российские и зарубежные ученые: В.Н. Вагин, Т.А. Гаврилова, А.С. Клещев, Г.С.
Поспелов, Д.А. Поспелов, В.Ф. Хорошевский, T.R. Gruber, N. Guarino, J.F. Sowa и др. Онтологический подход успешно использовался в объектно-ориентированном проектировании и программировании, для проектирования интерфейса пользователя, реинжениринга бизнес-процессов, в концептуальном проектировании, при проектировании и разработке систем на основе моделей предметных областей, позволяющих в полной мере использовать знания экспертов и пополнять их в процессе работы.
Целью диссертационной работы является разработка онтологических моделей и методов реализации преобразований программ с переменным набором трансформаций и изменяемой стратегией управления трансформациями.
Достижение цели работы предполагает решение следующих задач.
1. Разработка концепции преобразователя программ с переменным набором трансформаций на основе онтологического подхода.
2. Разработка онтологии единого представления программ и онтологии и его расширения.
3. Разработка онтологии методов потокового анализа программ и базы знаний о методах потокового анализа программ.
4. Разработка онтологии знаний о трансформациях программ и базы знаний о трансформациях программ.
5. Разработка методов интерпретации знаний о преобразованиях программ.
6. Разработка и реализация специализированного банка знаний о преобразованиях программ.
7. Разработка технологии использования методов и средств преобразования программ с переменным набором трансформаций и ее экспериментальное исследование.
Научная новизна работы. На основе проведенных научных исследований разработаны методы и средства создания нового класса программных средств – системы управления преобразованиями программ с переменным набором трансформаций.
Научная новизна разработанных методов и средств управления преобразованиями программ с переменным набором трансформаций заключается в использовании онтологического подхода и в представлении информации в базах знаний в декларативном представлении.
Впервые разработана концепция системы для управления преобразованиями программ с переменным набором трансформаций.
Впервые разработаны онтологии модели структурных программ и онтологии расширенной модели структурных программ.
Впервые разработаны онтологии методов потокового анализа программ и онтологии знаний о трансформациях программ, а также база знаний о методах потокового анализа программ и база знаний о трансформациях программ.
Впервые поставлена задача интерпретации декларативного представления базы знаний о трансформациях программ и разработан метод ее решения.
Впервые разработан и реализован специализированный банк знаний о преобразованиях программ.
Предложена технология использования методов и средств управления преобразованиями программ с переменным набором трансформаций.
Достоверность результатов. Обоснованность и достоверность научных положений, методов и выводов подтверждается использованием методов математического моделирования онтологий предметных областей, прикладной логики, теории графов, теории вычислительных процессов и структур, теории трансляции и оптимизации программ, а также результатами вычислительных экспериментов с помощью разработанных программных средств.
Практическая ценность работы.
Полученные в диссертации научные результаты имеют практическую направленность и предназначаются для автоматизации научных исследований в области преобразований программ.
Разработанные онтология модели структурных программ, онтология расширенной модели структурных программ, онтология методов потокового анализа программ позволяют создавать базы знаний о методах потокового анализа программ и базы знаний о трансформациях программ в единой унифицированной терминологии.
Разработанные методы интерпретации базы знаний о методах потокового анализа программ и базы знаний о трансформациях программ позволяют проводить исследования с преобразованиями программ с переменным набором трансформаций.
Разработанный специализированный банк знаний о преобразованиях программ позволяет коллективно развивать информационные ресурсы в области преобразований программ и распространять знания специализированного банка среди его пользователей.
Программное средство для исследования преобразований программ с переменным набором трансформаций использовалось:
- при разработке почтового клиента для сотовых телефонов, основной целью которого является доступ с мобильного телефона к почтовым серверам по протоколам SMTP, POP3, IMAP4;
- при разработке программного комплекса автоматизации работы туристических операторов на базе технологий ContourWEB;
- при разработке программного комплекса управления и учета услуг, предоставляемых посетителям интернет - ресурсов компании;
- при разработке программного комплекса для системы контроля сотрудников FrontLine.
Полученные в диссертации результаты внедрены (использованы): в научный процесс Института автоматики и процессов управления ДВО РАН, г.
Владивосток;
в учебный процесс Дальневосточного государственного университета, г. Владивосток.
Полученные результаты нашли применение при разработке Учебно методических комплексов по дисциплинам «Теория вычислительных процессов и структур II. Теория и методы трансляции» и «Оптимизация программ» для студентов, обучающихся по специальности 351500 – математическое обеспечение и администрирование информационных систем и которые используются в процессе обучения.
Результаты диссертационной работы использовались в учебном процессе Дальневосточного государственного университета при чтении курсов лекций «Теория вычислительных процессов и структур II. Теория и методы трансляции», «Оптимизация программ», «Параллельное программирование», при выполнении курсовых работ (всего 30) и дипломных работ (всего 15) специальности 351500 – математическое обеспечение и администрирование информационных систем, а также при выполнении кандидатских диссертаций по специальности 051311 математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.
В диссертации разработаны теоретические положения и научно обоснованные технические решения, обеспечивающие разработку системы для экспериментов в области преобразований программ.
Реализация работы. Результаты диссертационной работы нашли применение при выполнении научно-исследовательских работ:
- проект РФФИ 06-07-89071-а «Исследование возможностей коллективного управления в семантическом вебе информационными ресурсами различных уровней общности» 2006-2008 гг.
- программа №14 Президиума РАН «Фундаментальные проблемы информатики и информационных технологий», проект 06-I-П14-052 «Параллельные вычисления в создании инструментальных и проблемно - ориентированных средств для решения вычислительно-сложных задач моделирования динамики океана и атмосферы с использованием спутниковой информации, оптимизации в условиях неопределенности и построения интеллектуальных систем», раздел 2 «Разработка средств поддержки построения интеллектуальных систем и корректного программного обеспечения для многопроцессорных вычислительных комплексов» 2006-2008 гг.
- программа №15 фундаментальных исследований ОЭММПУ РАН «Проблемы анализа и синтеза интегрированных систем управления для сложных объектов, функционирующих в условиях неопределённости», проект 06-I-П15- «Синтез интеллектуальных систем управления базами знаний и базами данных при управлении сложными объектами в условиях неопределённости» 2006-2008 гг.
- инициативный научный проект ДВО РАН 06-III-A-01-007 «Интернет система управления информацией о преобразованиях программ» 2006-2008 гг.
Апробация работы. Научные положения и результаты диссертационной работы докладывались и получили одобрение на Международной научно методической конференции «Новые информационные технологии в университетском образовании» (г. Новосибирск, 1997 г.), на II-ой и III-ей Международной научно-технической конференции «Интерактивные системы:
проблемы человеко - компьютерного взаимодействия» (г. Ульяновск, 1997 и г.), на третьем сибирском конгрессе по прикладной и индустриальной математике посвященный памяти С.Л. Соболева (г. Новосибирск, 1998г.), на Международной конференции по математической логике, посвященной 90-летию со дня рождения академика А.И. Мальцева (г. Новосибирск, 1999 г.), на четвертом сибирском конгрессе по прикладной и индустриальной математике, посвященном памяти М.А.
Лаврентьева (г. Новосибирск, 2000 г.), на Международной конференции «Искусственный интеллект 2000» (Кацивели, Крым, 2000, 2006, 2007, 2008 г.), на Дальневосточной математической школе-семинаре им. Акад. Е.В. Золотова (г.
Владивосток, в 2001, 2002, 2006, 2007 и 2008 г., г. Хабаровск в 2005г.), на Международной конференции по искусственному интеллекту КИИ (г. Коломна, 2002 г., г. Обнинск, 2006 г., г. Дубна 2008 г.), на Международной конференции KDS-2003, KDS-2005, KDS-2007 и KDS-2008 (г. Варна, Болгария), на Международной конференции им. В.А. Трапезникова РАН «Параллельные вычисления и задачи управления» PACO’2004, PACO’2006 и PACO’2008 (г.
Москва, 2004 г., 2006 г., 2008 г.), на Международной конференции «Системный анализ и информационные технологии» САИТ-2005 и САИТ-2007 (г. Переславль Залесский, 2005 г.. г. Обнинск, 2007 г.), на Всероссийской конференции «Знания онтологии-теории» с международным участием (г. Новосибирск, 2007г.), на научных сессиях МИФИ (г. Москва, 2001, 2002, 2004-2008 г.г.), Интеллектуальные и многопроцессорные системы (г. Таганрог, 2003-2007 г.г.), на второй Международной конференции по когнитивной науке (г. Санкт-Петербург, 2006 г.), на IX Международной конференции «Интеллектуальные системы и компьютерные науки» (г. Москва, 2006 г.);
на семинарах Отдела экспертных систем Института автоматики и процессов управления ДВО РАН и Института математики и компьютерных наук ДВГУ (1991-2008г., г. Владивосток), в лаборатории Системного программирования Института Систем Информатики СО РАН им. А.П. Ершова в 1998 г. (г. Новосибирск), на семинаре в НИВЦ МГУ в лаборатории параллельных Информационных Технологий в 2003 г., 2006 г. (г. Москва), на семинаре ВЦ РАН в 2003 г., 2006 г. (г. Москва).
Личный вклад автора. Автором осуществлена постановка задачи, получение всех экспериментальных исследований и самостоятельно получены все теоретические результаты. Автор принимал личное участие в разработке программных систем и ей принадлежит интерпретация всех основных экспериментальных и теоретических результатов, представленных в диссертации. В работах [2-4, 18-19, 22, 34,38,38-39] выделены основные компоненты онтологии предметной области. В работах [9,24-25] определены язык модели структурных программ и расширение языка модели структурных программ терминами потокового анализа. В работах [5-6, 10, 12,14-15,35,40,41-43] выполнены постановки задач, разработаны основные теоретические положения. В работах [8, 13, 23, 26-28, 30-32, 36,44] описаны архитектура и основные задачи преобразователя программ. В работах [11,47] разработана архитектура преобразователя программ, управляемого знаниями.
Публикация результатов работы.
Результаты диссертационной работы представлены в монографии, в научных публикациях в отечественных и международных изданиях, в том числе статьи, из них 7 статей в международных изданиях, 16 статей в российских реферируемых журналах, в свидетельстве об официальной регистрации программ для ЭВМ, в свидетельстве об отраслевой регистрации разработки.
Структура и объем работы. Диссертация состоит из введения, восьми глав, заключения, списка литературы, включающего 220 наименований, 6 приложений.
Основное содержание работы
изложено на 282 страницах машинописного текста, содержит 23 рисунка.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность работы, дана общая характеристика научной проблемы, сформулирована цель и поставлены задачи, показана научная новизна, практическая ценность результатов работы, приведен перечень основных результатов диссертационной работы, приведены сведения об апробации работы и публикациях.
В первой главе дан анализ современного состояния проблемы преобразований программ, как с помощью традиционных методов, так и с помощью методов искусственного интеллекта. На основе проведенного обзора определена цель и основные задачи диссертационной работы.
Во второй главе диссертационной работы решается задача разработки концепции преобразователя программ с переменным набором трансформаций.
Сформулированы требования к преобразователю программ с переменным набором трансформаций и предложена его архитектура.
Обычно преобразование программ рассматривается как суперпозиция элементарных преобразований – трансформаций. Трансформация состоит из формулы трансформации и формулы контекстного условия (условия применимости этой трансформации).
Определение 1. Под преобразованием программ с переменным набором трансформаций будем понимать отображение TV: (PN) P, где P – множество программ на языке L, N - множество наборов элементарных трансформаций программ.
Определение 2. Назовём стратегией s(n) на заданном наборе элементарных трансформаций n конечную последовательность этих трансформаций, составленную из фиксированного их набора n.
Определение 3. Преобразователь с переменным набором n трансформаций TVS(n) = (TV, S (n)) – это абстрактное устройство, которое предназначено для преобразования заданной программы путем интерпретации заданной стратегии s (n) из множества стратегий S (n).
На основе проведенного анализа в области преобразования программ определены требования к преобразователю программ с переменным набором трансформаций: должен быть разработан преобразователь, позволяющий проводить исследования с переменным набором трансформаций;
должен быть разработан преобразователь, позволяющий задавать произвольные стратегии трансформаций;
чтобы обеспечить возможность для исследования стратегий применения преобразований программ и свойств самих преобразований, должен быть разработан преобразователь, позволяющий визуализировать истории применения преобразований программ;
чтобы использовать в исследованиях вновь создаваемые преобразования программ, должен быть разработан преобразователь, позволяющий задавать описания преобразований программ;
чтобы использовать в исследованиях новые методы потокового анализа программ, должен быть разработан преобразователь, позволяющий пользователям задавать методы потокового анализа программ.
С целью повышения эффективности работы преобразователя в диссертации предлагается в явном виде использовать семантику и специфику предметной области преобразований программ. Для этого вся информация для работы преобразователя представляется в виде онтологии на языке прикладной логики (ЯПЛ) и находится в базе знаний программ на языках высокого уровня, в базе знаний о методах потокового анализа программ, в базе знаний о трансформациях программ в декларативном представлении. В диссертации предложена модель преобразователя программ с переменным набором трансформаций, удовлетворяющая перечисленным выше требованиям (см. рис.1).
На вход преобразователю подается набор, стратегия преобразования программ и программа на языке программирования высокого уровня (ЯВУ). На выходе преобразователя формируются истории преобразований программ и программа на языке программирования высокого уровня, которая получена из входной программы в результате применения к ней трансформаций из входного набора в соответствии с заданной стратегией.
Преобразователь программ состоит из (1) средств декомпозиции программ на языке высокого уровня и их преобразования в единое представление, (2) средств преобразования программ в едином представлении, (3) средств визуализации историй преобразований программ и (4) средств генерации программ из единого представления на языки программирования высокого уровня.
Средства декомпозиции программ на языке высокого уровня и их преобразования в единое представление осуществляют преобразование входной программы на ЯВУ в единое представление. Программа в едином представлении может быть сохранена в базе программ для повторного исследования в эксперименте.
Средства преобразования программ в едином представлении включают: (1) интерпретатор стратегии преобразования;
(2) анализатор потока управления и потока данных программ;
(3) проверку контекстных условий трансформаций и выполнение трансформаций.
Интерпретатор стратегии преобразования задает порядок выполнения трансформаций в соответствии со стратегией. Анализатор потока управления и потока данных программ управляется стратегией применения преобразований и базой знаний о методах потокового анализа программ: он расширяет единое представление программы значениями терминов потокового анализа программ.
Преобразователь программ управляется стратегией применения преобразований и базой знаний о трансформациях программ: он формирует единое представление программы после выполнения над ней очередной трансформации.
Рис. 1. Архитектура преобразователя программ с переменным набором трансформаций Средства визуализации позволяют отображать информацию об историях преобразований программ и создавать графические представления единого представления программ.
Средства генерации программ из единого представления на язык программирования высокого уровня осуществляют преобразование программы из единого представления на ЯВУ.
Преобразователь позволяет выполнять преобразования на одном языковом уровне, что дает следующие преимущества: становится возможным повторение выполнения трансформаций, так как вход и выход этапа преобразований совпадают по языку;
упрощается процесс пополнения или модификации трансформаций и методов потокового анализа программ и изменения алгоритмов преобразования за счет отсутствия перевода с одного языкового уровня на другой;
предоставляет возможности для экспериментальной оценки влияния различных наборов на результирующую программу за счет более простой модификации набора трансформаций и возможностей отключения трансформаций.
Декларативное описание знаний в базах знаний преобразователя с переменным набором трансформаций позволяет задавать трансформации в наглядной непроцедурной форме вместо того, чтобы реализовывать необходимые алгоритмы.
В третьей главе решается вторая задача диссертационной работы. В ней разработана онтология моделей структурных программ (МСП);
онтология МСП, расширенная терминами потокового анализа. Дано описание проекций языков программирования высокого уровня на единое представление программ и единого представления программ на языки высокого уровня.
Описание терминологии некоторой предметной области вместе с определением смысла терминов в современном мире получило название модели онтологии.
Онтология МСП (термины, с использованием которых описывается модель онтологии структурных программ). Полное описание модели приведено в диссертации.
Объектом преобразований является некоторая программа. Свойства программы всегда формулируются в терминах математической модели этой программы.
Характеристикой любой программы является язык (множество программ), которому эта программа принадлежит. Свойства языка также формулируются в терминах математической модели этого языка. Тем самым, множество терминов для описания объекта преобразований может быть разбито на две группы: термины для описания модели языка и термины для описания модели конкретной программы. Прежде чем будет преобразовываться конкретная программа, должен быть определен язык, которому эта программа принадлежит. Следовательно, термины для описания модели языка являются параметрами модели онтологии, а термины для описания модели программы – неизвестными модели онтологии. Тогда модель языка задается указанием значений параметров, а модель конкретной программы – указанием значений неизвестных.
Очевидно, что модель программы описывает не одну программу, а множество программ, обладающих одинаковыми свойствами, а модель языка – множество языков, обладающих одинаковыми свойствами. Поэтому к модели языка предъявлены следующие требования: она должна позволять представлять основные конструкции императивных языков программирования, существенные для описания последовательных трансформаций;
быть гибкой и расширяемой с тем, чтобы при необходимости класс моделируемых программ мог быть легко расширен;
форма представления моделей программ должна быть удобна для анализа, как информационных потоков, так и потоков управления в программе.
Модель онтологии представляет собой необогащенную систему логических соотношений с параметрами, записанную с использованием предложений многосортного языка прикладной логики.
Любая программа состоит из фрагментов, причем каждый фрагмент, в свою очередь, также состоит из фрагментов, т.е. любая программа имеет синтаксическую структуру, которую отражает математическая модель этой программы.
Каждый фрагмент, как элемент программы, обладает рядом свойств. Прежде всего, у него есть адрес фрагмента – некоторая уникальная характеристика, однозначно определяющая каждый фрагмент в программе.
Будем считать, что все фрагменты могут быть разбиты на три группы:
операторы описания, исполнимые операторы и элементы операторов. Каждый фрагмент характеризуется своим классом, например, фрагмент может иметь класс оператор присваивания, оператор цикла, оператор описания функций и т.д. Функция FragClass возвращает для указанного адреса фрагмента класс этого фрагмента.
Множество названий классов фрагментов (каждой группы) в программе задают значения параметров Операторы описания, Исполнимые операторы, Элементы операторов.
Синтаксическую структуру программы задают дуги управления. Каждая дуга управления связывает два фрагмента программы. Каждая дуга управления имеет метку, которая определяет тип связи между фрагментами. Для задания дуги управления используется функция, имя которой совпадает с меткой дуги. Значение параметра Имена дуг управления задает, какие метки могут иметь дуги управления в программе. Для каждой дуги управления определена область действия дуги управления. Эту область задает значение функционального параметра Область действия дуг управления –функция, которая сопоставляет каждой метке дуги пару, состоящую из двух множеств имен классов фрагментов: первое множество определяет, фрагменты каких классов могут быть аргументами, а второе – результатами дуги управления с данной меткой.
В программе всегда присутствует множество различных Идентификаторов.
Идентификаторы могут быть разных видов, например, идентификаторы переменных, функций, констант и типов данных. Идентификаторы каждого вида образуют в программе множество, название которого совпадает с названием вида.
Значение параметра Виды идентификаторов задает, идентификаторы каких видов могут быть в программе.
На множестве фрагментов и идентификаторов программы определены функции и отношения, которые позволяют определить структуру программы и некоторые ее свойства.
Функции, имеющие один аргумент (фрагмент или идентификатор) называются атрибутами. Каждый атрибут имеет имя. Значение параметра Имена атрибутов задает, какие атрибуты могут использоваться для описания свойств идентификаторов или фрагментов в программе. Для каждого атрибута определяются область определения и область значений атрибута. Эти области задаются значениями функциональных параметров Область определения атрибута и Область значения атрибута.
Значение параметра Имена функций задает, какие функции, имеющие два и более аргументов, могут использоваться при описании свойств фрагментов или идентификаторов программы. Для каждой функции определяется область определения и область значений. Эти области задаются значениями параметров Область определения функции и Область значений функции.
Значение параметра Имена отношений задает, какие отношения могут быть определены на множестве фрагментов и идентификаторов программы. Значения параметров Определение отношения для каждого имени отношения задают формулу определения истинности отношения между фрагментами и идентификаторами программы.
Еще одним свойством фрагмента является его корректность. Значение корректности задает предикат Корректность, который сопоставляет адресу фрагмента истину, если у него имеются все дуги управления и атрибуты, необходимые для этого фрагмента. Значение параметра Определение корректности задает для каждого класса фрагмента, какие дуги управления и атрибуты должны быть определены для фрагмента этого класса.
Значение параметра Элементарные типы задает для языка множество идентификаторов типов данных, являющимися базовыми для всех остальных типов данных этого языка.
Значение параметра Способы порождения задает множество названий конструкторов типов данных в языке. Для каждого идентификатора типа данных в программе определены значения таких свойств, как базовый тип и метод конструирования типа из базового. Значение первого свойства задает функция BaseType, которая сопоставляет каждому идентификатору типа последовательность идентификаторов типов, которые использованы при конструировании этого типа данных. Значение второго свойства задает функция ConstructMethod, которая сопоставляет каждому идентификатору типа название конструктора. Значением параметра Совместимость типов является предикат, определяющий возможность неявного преобразования одного типа к другому.
Значение параметра Зарезервированные имена задает множество имен ролей, которые могут играть фрагменты или идентификаторы программы. Значение параметра Область значения зарезервированного имени сопоставляет каждому имени роли предикат, определяющий, какими свойствами должен обладать фрагмент или идентификатор, играющий в программе эту роль.
Значение параметра Знаки операций задает множество символов, использующихся в программе для обозначения каких-либо операций в выражениях (арифметических, логических, преобразования и т.д.) программы. Функциональные параметры Число аргументов и Приоритет, сопоставляют каждому символу операции количество аргументов и приоритет.
Для реализации концепции преобразователя программ с переменным набором трансформаций, разработано единое представление программ, ориентированное на преобразование программ и позволяющее более точно проводить потоковый анализ программ и реализовывать преобразования программ, а также определить способ построения единого представления. Такое единое представление удовлетворяет следующим требованиям: представление должно быть единым для программ, написанных на различных процедурных языках;
единое представление должно быть расширяемым, т.е. позволяло бы добавлять новые конструкции языков программирования;
должно позволять реализовывать алгоритмы потокового анализа программ.
В качестве единого представления программ в диссертации предложена Модель структурной программы (МСП), которая в линейной форме представляет текст на некотором формальном языке и ее расширение. Также определены проекции языков программирования высокого уровня на единое представление программ и единого представления программ на языки высокого уровня.
Формальный Язык Модели Структурных Программ (ЯМСП) определяется заданием значений параметров модели онтологии объекта преобразований программ. К языку предъявлены следующие требования: он должен содержать средства для представления конструкций языков высокого уровня.
Язык ЯМСП разработан на основе таких языков программирования, как Паскаль и Си и является структурным языком программирования, где в качестве первичных примитивов выбраны последовательность, цикл с предусловием и постусловием и ветвление. В нем принято обычное понятие статической блочной среды;
все переменные (идентификаторы) должны быть описаны до их использования в каком-либо операторе описания функции либо вне любой функции в начале программы;
допускаются вложенные процедуры и функции;
если функция не возвращает результат, то она считается процедурой. Функция с именем Main считается главной, все остальные функции должны быть вложены в нее.
Любая переменная может иметь либо простой тип, либо сложный. К простым типам относятся такие типы, как целый, вещественный и логический. Все эти типы являются неявно приводимыми друг к другу. К операндам простого типа применимы следующие операции: +, -, *, /, взятие адреса, обращение по указателю, And, Or, Not. Разрешены динамические переменные, операции New и Dispose, а также адресная арифметика.
Сложные типы данных конструируются на основе ранее определенных типов путем объединения их в массивы и создания ссылочных типов. Элементы массивов могут иметь как простой, так и сложный тип. Массивы могут быть только одномерными. Индексы массивов - только целые переменные. К массивам может применяться только одна операция - обращение к элементу массива по индексу. В отношении переменных применяется принцип именной эквивалентности, т.е. две переменные эквивалентны, если они имеют один и тот же тип. Исключения из этого правила - все простые типы эквивалентны между собой.
Функции могут возвращать результат только скалярного типа, т.е. целого, вещественного, логического и произвольного ссылочного (например, указатель на трех мерный массив, компонентами которого являются указатели на указатель).
Параметры функций могут иметь любой тип и передаваться по ссылке либо по значению. Все имена функций, переменных, констант, типов уникальны в пределах программы.
Онтология расширенной МСП.
Полное описание онтологии МСП, расширенной терминами потокового анализа, приведено в диссертации. Все термины онтологии знаний о методах потокового анализа программ делятся на три группы: термины для описания знаний о потоковом анализе для классических оптимизирующих преобразований, реструктурирующих преобразований программ и коммуникационных преобразований программ для машин с распределенной памятью.
Потоковый анализ является средством получения достоверной информации в поведении программы без ее реального исполнения. Извлекаемые из текста программы свойства – это глобальная информация о программе, которая не может быть получена ни пробными запусками программы, ни изучением ее отдельных фрагментов. В диссертации определено расширение модели структурной программы терминами, используемыми при потоковом анализе программ для трех классов преобразований.
Расширенная МСП для преобразований программ является обобщением схем программ. Так, например, если из описания МСП Имена дуг исключить Дуги управления, используемые при потоковом анализе, то можно получить схему Мартынюка. Если из описания расширенной МСП исключить описание всех атрибутов, и оставить вычисление атрибутов А и R только для Исполнимых операторов, то можно получить схему Лаврова.
Большинство векторизующих и распараллеливающих компиляторов используют граф зависимости по данным (ГПЗ). ГПЗ можно получить путем введения в расширенную МСП классических преобразований программ специальный атрибут Par_DO и отношение – итерационная зависимость.
Для решения проблемы автоматического выявления параллелизма на уровне заданий в последовательных программах силами распараллеливающего компилятора с использованием понятия иерархии циклов и зависимостей по данным и по управлению был введен иерархический граф заданий (ИГЗ). Так, например, ИГЗ можно получить из расширенной МСП для коммуникационных преобразований путем введения в расширенную МСП для классических преобразований Оператора_Посылки, Оператора_Приема.
Единое представление позволяет реализовывать всевозможные алгоритмы потокового анализа программ. В разработанном в диссертации подходе необходимая информация для проверки контекстных условий трансформаций собирается до выполнения преобразований, но в отличии от существующих подходов, графовая модель может быть получена путем интерпретации соответствующего метода потокового анализа программ из соответствующей базы знаний о методах потокового анализа программ.
В четвертой главе решается третья задача диссертационной работы.
В ней разработана онтология методов потокового анализа программ (абстрактный синтаксис языка для представления методов потокового анализа программ и его операционная семантика), приведены методы потокового анализа программ, представленные в базе знаний о методах потокового анализа программ.
Онтология знаний о методах потокового анализа программ. Полное описание онтологии знаний о методах потокового анализа программ приведено в диссертации.
Преобразования программ проводятся на основе информации, собранной в результате потокового анализа программ.
В диссертации предложен специальный язык для записи методов потокового анализа программ (язык МПА). Язык разработан с целью формализации процесса расширения МСП. При разработке языка были проанализированы основные формы записи методов потокового анализа, описанные в литературе. Язык позволяет описывать конструкции, которые являются результатом потокового анализа программы: атрибуты вершин графа;
отношения и функции над вершинами графа;
вершины и дуги графа. Язык содержит переменные, которые в качестве значений могут принимать ссылки на различные элементы модели программы;
основные конструкции алгоритмических языков программирования (такие как цикл, выбор, присваивание);
операции с множествами, поскольку в процессе накопления информации о программе часто оперируют с множествами переменных и идентификаторов;
операции обходов деревьев.
База методов потокового анализа формируется экспертом предметной области.
В нее могут входить как методы взятые из различных источников (описанные в литературе, в сети Интернет и т.д.), так и методы разработанные непосредственно экспертом.
База знаний о методах потокового анализа программ в терминах онтологии. В базе знаний о методах потокового анализа программ методы потокового анализа представлены на языке МПА.
В приложении диссертационной работы приведены три каталога преобразований программ, в которых знания о преобразованиях программ представлены в декларативном виде. Для интерпретации формул, приведенных в каталогах необходимо предварительно выполнить потоковый анализ программ, т.е.
вычислить все фрагменты, дуги и атрибуты расширенной МСП.
В диссертации предложен подход, в котором возможно представлять в виде онтологии методов потокового анализа программ различные информационные модели, записывать их на специально разработанном языке в базу знаний методов потокового анализа программ. В отличие от существующих подходов в системах, знания о методах потокового анализа в предложенной концепции представляются в явном виде в декларативной форме.
В пятой главе решается четвертая задача диссертационной работы. В ней разработаны онтология знаний о трансформациях программ (абстрактный синтаксис языка описания трансформаций программ - ЯОТ), а также база знаний о трансформациях программ.
Термины, для описания знаний о трансформациях программ. Полное описание онтологии знаний о трансформациях программ приведено в диссертации.
Обычно преобразование проводится не над всей программой, а над каким-то ее участком, не обязательно непрерывным. Множество фрагментов программы, необходимых для принятия решения о преобразовании, называется Кандидатом в участки экономии, а то множество фрагментов, на котором истинно контекстное условие преобразования, называется Участком экономии. Таким образом, участок экономии - это кандидат, для которого истинно контекстное условие преобразования.
Участок экономии - набор фрагментов программы, для которого известно число фрагментов, их типы и их взаимное расположение в программе. Однако достаточно часто участок экономии состоит из двух частей. Первая часть представляет собой кортеж фрагментов, для каждого элемента которого известен его тип и положение в участке экономии. Вторая часть представляет собой множество кортежей фрагментов. Число кортежей, принадлежащих второй части участка экономии, является переменным для разных участков экономии одной программы, но число элементов каждого кортежа, типы и взаимное расположение фрагментов, входящих в последовательность, фиксированы, т.е. эти кортежи фрагментов обладают некоторыми одинаковыми свойствами. При применении преобразования все кортежи фрагментов второй части участка экономии меняются одинаковым образом. Например, для некоторых преобразований процедур (функций) участок экономии содержит как оператор описания процедуры, так и все ее вызовы. При этом оператор описания процедуры (функции) всегда один, а операторов вызова может быть много. Все элементы множества вызовов однозначно определяются оператором описания процедуры (функции). В результате применения преобразования все операторы вызова процедуры (функции) изменяются одинаковым образом.
Поэтому участок экономии в модели представляется парой, первый элемент которой называется простой частью участка экономии, а второй – множественной частью участка экономии. Первый элемент пары – это кортеж адресов фрагментов.
Второй элемент пары – это множество кортежей адресов фрагментов.
Каждое преобразование имеет простые и множественные параметры. Каждый фрагмент простой части участка экономии будем называть значением соответствующего ему простого параметра участка экономии.
Множество фрагментов, входящее во множество кортежей фрагментов множественной части участка экономии, называются значением множественного параметра участка экономии. Термин Число простых параметров преобразования задает число элементов кортежа простой части участка экономии, а термин Число множественных параметров преобразования задает число элементов каждой последовательности множественной части участка экономии. Термины Классы простых параметров преобразования и Классы множественных параметров преобразования задают последовательности классов фрагментов, образующих простую часть участка экономии, и последовательности классов фрагментов, образующих каждый кортеж множественной части участка экономии.
Контекстное условие преобразования описывает свойства участка экономии, к которому применимо это преобразование. В данной модели онтологии контекстное условие представляется в виде предиката, аргументами которого являются номер шага истории преобразования программ, а также некоторый кандидат в участки экономии.
Участков экономии на каждом шаге процесса преобразования может быть несколько. Поэтому необходим критерий для выбора одного участка из многих.
Характеристическая функция (ХФ) - это формула, аргументами которой являются фрагменты из участка экономии. Она сопоставляет каждому участку экономии его оценку - рациональное число.
Стратегия преобразования – это формула, при помощи которой из множества рациональных чисел - результатов характеристической функции для разных участков экономии, можно выбирать одно. Соответственно, участок экономии с выбранной характеристикой и подвергается преобразованию на этом шаге истории.
Параметры с одинаковым контекстом - это множество пар номеров параметров участка экономии до и после преобразования, у которых контексты должны совпадать.
Последовательность применения трансформаций задает порядок, в котором будут применяться трансформации. При этом каждая трансформация исполняется до тех пор, пока для ее не останется допустимых участков экономии. На рис. приведен пример описания трансформации программы в базе знаний о трансформациях программ.
Полное описание базы знаний о трансформациях программ приведено в приложениях диссертационной работы.
В рассмотренных каталогах и системах контекстные условия и формулы трансформации, как правило, описываются неформально. В приложении к диссертационной работе приведено три каталога, в которых знания о контекстных условиях и трансформациях формализованы и представлены на ЯОТ в явном виде в декларативном представлении. В отличие от существующих систем, знания о преобразованиях программ не надо описывать на языках программирования высокого уровня, для такого представления предложен язык спецификаций. Эта форма удобна для интерпретации знаний в преобразователе программ.
В шестой главе диссертации поставлена и решена пятая задача диссертационной работы – разработка методов интерпретации базы знаний о трансформациях программ.
Преобразование программ выполняется последовательно по шагам, на каждом из которых происходит применение к преобразуемой модели программы одной трансформации. Каждый такой шаг называется шагом истории преобразования. В качестве объекта преобразования выступает модель программы. На каждом шаге процесса преобразования модель программы изменяется: к ней применяется формула трансформации, определяемая трансформацией, применяемой на текущем шаге преобразования программы. Таким образом, на каждом шаге преобразования существует своя версия модели программы со своим множеством адресов фрагментов, своим множеством идентификаторов, и т.д. Каждое преобразование обладает следующими свойствами: участком экономии (УЭ), контекстным условием (КУ), характеристической функцией (ХФ), стратегией применения.
В диссертации разработаны следующие методы интерпретации базы знаний о трансформациях программ.
Вынос инвариантного оператора из цикла вперед Список атрибутов потокового Вектор переменных Условие Трансформация Характеристическая функция Стратегия оптимизации анализа программ Max Level X Последовательность_операторов Z X B D Y Y1 Y2 Список Список Дуга_последовательность_операторов Сравнения формул формул Первый_элемент_последовательности...
Последний_элемент_последовательности...
......
Предшествование Принадлежность Является_частью фрагмента классу Аргументное_множество Равенство Функциональная Функциональная Результатное_множество Сравнение Сравнение множеств формула формула Сильно_результатное_множество Z Последовательность_операторов Отнош ение над V D Z Z V Класс_фрагмента фрагментами Последовательность_операторов Операция над Y D Является частью фрагментами Concatination Z Дуга_последовательность_операторов Null Y Пересечение {} множеств Y X Y Результатное_множество Y Аргументное_множество Рис. 2. Пример описания трансформации программы в базе знаний о трансформациях программ Метод ИНТЕРПРЕТАЦИЯ_ СТРАТЕГИИ_ ПРЕОБРАЗОВАНИЯ_ПРОГРАММ Входные данные: модель структурной программы (МСП);
стратегия преобразования;
набор преобразования.
Выходные данные: модель программы, расширенная терминами потокового анализа программ;
история преобразований модели структурной программы.
Примененные функции в методе: Проанализировать МСП, Найти участки экономии, Построить характеристики УЭ, Реализовать стратегию, Построить новую МСП с преобразованным УЭ рассмотрены как отдельные методы.
Все методы связаны с тем, что надо интерпретировать знания, представленные в базе знаний в виде формул и на основании этой интерпретации осуществлять анализ МСП, поиск участков экономии, построение характеристик УЭ, реализацию стратегии и построение новой МСП с преобразованным УЭ.
Метод Проанализировать МСП.
В базе знаний о потоковом анализе программ содержатся атрибуты для потокового анализа МСП и метод вычисления этих атрибутов.
Метод Проанализировать МСП дополняет модель структурной программы атрибутами путем интерпретации методов вычисления атрибутов, находящихся в базе знаний о методах потокового анализа программ.
Метод Найти участки экономии.
Обобщённое контекстное условие преобразования в базе знаний задается следующим образом:
$a1,..,an (F1(a1,…,an), ${b1,..,bm}(F2(a1,..,an,b1,..,bm), ${c1,..,ck}(F3(a1,..,an,b1,..bm, c1,..,ck),)) & ${e1,..,ei}(F4(a1,..,an,e1,..,ei), "d1,..,dj(F5(a1,..,an,e1,..ei, d1,..,dj),))) Здесь a, b, c, d, e – имена переменных, F1-F5 – обобщенные формулы.
В методе Найти участки экономии происходит интерпретация приведенного выше контекстного условия следующим образом.
Находится подстановка значений фрагментов для вектора переменных a1..an такая, что предикат F1 истинен. Этот вектор значений образует простую часть участка экономии. Затем, при найденных значениях переменных a1..an происходит поиск всех подстановок значений переменных b1..bm, удовлетворяющих условию F2. Для каждой такой подстановки b1..bm, в свою очередь, ищется множество векторов c1..ck, удовлетворяющих условию F3. Затем, для этих же найденных значений переменных a1..an происходит поиск всех подстановок значений переменных e1..ei, удовлетворяющих условию F4. Однако, так как для вектора e1..ei в качестве дополнительного условия определена отрицательная множественная формула F5, то каждая подстановка e1..ei попадает в участок экономии только в том случае, если для нее не существует ни одной подстановки фрагментов d1..dj, при которых F5 стала бы истинной.
Метод Построить характеристики УЭ.
Характеристическая функция в модели онтологии представляет функцию, которая при подстановке в неё участка экономии вернет рациональное число – его характеристику.
Обобщенная характеристическая функция в базе знаний задается следующим образом: a1,..,an (F1(a1,…,an).
В методе Построить характеристики УЭ вычисляется характеристика участка экономии как значение терма F. Аргументами терма F являются переменные a1,..,an из простой части участка экономии.
Метод Реализовать стратегию.
В базе знаний стратегия представляет функцию, аргументом которой является множество характеристик участков экономии, а результатом – один из элементов этого множества.
В методе Реализовать стратегию задание стратегии осуществляется путем выбора одного из следующих вариантов: Max, Min, Rnd.
Метод Построить новую МСП с преобразованным УЭ.
Обобщенное правило трансформации в базе знаний задается следующим образом:
$a1,..,an (F1(a1,…,aa, b1,…,bb)&F2;(a1,…,ab, b1,…,bb, c1,…,cc)&…&Fn; (…) a1b1,…abbb, a1c1,…accc,…);
Здесь: a1,…aa – вектор подстановок исходных фрагментов в программе;
b1,…,bb, c1,…,cc и т.д. – вектора подстановок новых фрагментов. F1,…,Fn – формулы, определяющий свойства создаваемых фрагментов;
a1b1,…abbb, a1c1,…accc и т.д. – правила, определяющие, какой фрагмент заменять и как производить эту замену.
В методе Построить новую МСП с преобразованным УЭ происходит интерпретация трансформации следующим образом.
Для вектора подстановок a1,…,an создать новый вектор подстановок b1,…,bb, причем свойства создаваемых фрагментов определяются формулой F1. Для формул F2…Fn – аналогично. Фрагменты, созданные формулой Fn могут использоваться в формуле Fn+1 в качестве аргументов. Последовательно перебрать все пары подстановок a1b1,…, abbb, a1c1,…accc, для каждой пары. Для пары подстановок ab, заменить фрагмент a на фрагмент b. Все дуги, ведущие к фрагменту a, заменить соответствующими дугами к фрагменту b. Последовательно перебрать все фрагменты, проверив, что фрагмент имеет все необходимые атрибуты и дуги согласно спецификации МСП.
В существующих оптимизирующих и распараллеливающих компиляторах и системах, предназначенных для преобразования программ, набор трансформаций встроен жестко, поэтому метод потокового анализа не изменяется. По предложенной схеме метод потокового анализа изменяется в зависимости от стратегии преобразования программ.
В седьмой главе диссертационной работы поставлена и решена шестая задача диссертационной работы - разработка и реализация специализированного банка знаний о преобразованиях программ. Сформулированы требования к специализированному банку знаний о преобразованиях программ (СБкЗ_ПП – далее банк знаний), предложены его архитектура и методы реализации.
Для решения научных и образовательных проблем в области преобразования программ в диссертационной работе во второй главе предложена концепция преобразователя программ с переменным набором трансформаций.
Для того, чтобы обеспечить информационное наполнение и доступ к преобразователю программ, необходимы соответствующие программные средства.
В диссертации предложен подход, в рамках которого доступ к информационному наполнению и программным средствам осуществляется через специализированный банк знаний о преобразованиях компьютерных программ.
СБкЗ_ПП для поддержки научных исследований и образовательной деятельности в области преобразования программ есть информационный ресурс, объединяющий всю информацию, используемую в этих научных исследованиях, образовательной деятельности, обеспечивающий доступ к этой информации специалистам и компьютерным программам и содержащий средства, предназначенные для выполнения тех задач обработки информации, для решения которых уже разработаны эффективные методы.
Общая задача СБкЗ_ПП – централизация знаний о преобразованиях программ, координация процесса их обработки и коллективное развитие с целью получения наиболее качественных и современных знаний в этой области, а также облегчения их использования в науке и образовании.
Для того, чтобы СБкЗ_ПП можно было использовать для проведения компьютерных экспериментов и для макетирования блоков оптимизации в компиляторах, он должен удовлетворять следующим требованиям: предоставлять средства для проведения экспериментов с любыми наборами преобразований, для задания разных стратегий применения преобразований программ, визуализации истории применения преобразований программ;
поддерживать единое представлении программ;
предоставлять средства задания проекций языков программирования на это единое представление программ, для описания преобразований программ, для задания методов потокового анализа программ.
Архитектура банка знаний. Банк знаний (рис.3) состоит из (1) информационной системы администрирования (ИСА), (2) информационного наполнения (ИН), (3) оболочки ИН и (4) программного наполнения (ПН).
Информационная система администрирования банка знаний предназначена для администрирования информационных ресурсов банка, его пользователей и их полномочий. Функции по управлению информационными ресурсами, пользователями и их полномочиями выполняет администратор банка знаний.
Информационное наполнение состоит из: онтологии (описания абстрактного синтаксиса) языков программирования;
онтологии знаний о методах потокового анализа программ;
онтологии знаний о трансформациях программ. Также в информационном наполнении банка знаний хранятся: база программ в терминах онтологии языка программирования высокого уровня;
база знаний о методах потокового анализа программ;
база знаний о трансформациях программ.
Оболочка ИН предоставляет доступ к хранимой информации и компьютерным программам. Оболочка информационного наполнения банка знаний может надстраиваться, а для программного наполнения банка знаний могут разрабатываться новые программные средства. Функции по надстраиванию оболочки информационного наполнения банка знаний и встраиванию новых программных средств банка знаний выполняет специальный пользователь, называемый сопровождающим.
Программное наполнение (т.е. сервисы, реализованные через оболочку) включают: средства редактирования;
средства декомпозиции программ на языке высокого уровня и их преобразования в единое представление;
средства преобразования программ;
средства генерации программ из единого представления на язык программирования высокого уровня, а также средства визуализации историй преобразований программ. Также в программное наполнение входит система управления банка знаний.
Средства редактирования включают: редактор базы программ в терминах онтологии языка программирования высокого уровня;
редактор базы знаний о методах потокового анализа программ;
редактор базы знаний о трансформациях программ, которые создаются с использованием редактора информации различных уровней общности (ИРУО).
Специализированный банк знаний о преобразованиях компьютерных программ 1. Информационная система Административная Администр администрирования банка база данных атор знаний 2. Информационное наполнение 3. Оболочка информационного наполнения Сопровожд 4. Программное наполнение ающий банка знаний Рис. 3. Компоненты специализированного банка знаний о преобразованиях компьютерных программ Обозначения на рисунке три и далее:
передача данных.
передача управления, Средства декомпозиции программ на языке высокого уровня и их преобразования в универсальное представление включают следующие компоненты:
Редактор программ на языке программирования высокого уровня, Редактор проекций языков программирования высокого уровня на единое представление и Генератор единого представления программ. Подсистема управления, являющаяся частью системы управления банка знаний, связывает эти компоненты друг с другом, осуществляя передачу информации и управления между ними.
Средства преобразования программ в универсальном представлении состоят из следующих подсистем: подсистема интерпретации стратегии преобразований;
подсистема потокового анализа программ;
подсистема преобразования программ.
Подсистема преобразования программ состоит из следующих подсистем:
поиска участков экономии и проверки контекстных условий;
подсистема замены участка экономии на преобразованный участок экономии;
подсистема измерения эффективности преобразований.
Средства визуализации историй преобразований программ и отчетов по качеству процесса оптимизации программ позволяют просмотреть историю применения преобразований программ.
Методы реализации банка знаний. На рис. 4 представлена клиент - серверная архитектура банка знаний о преобразованиях компьютерных программ, разработанной по технологии «клиент-сервер».
На клиентской части архитектуры банка знаний находятся: (1) интерфейс средств редактирования банка знаний;
(2) интерфейс системы преобразования программ;
(3) интерфейс системы построения макетов оптимизирующих компиляторов.
На серверной части архитектуры банка знаний находятся: (1) WEB- сайт многоцелевого банка знаний (МБкЗ);
(2) средства редактирования банка знаний и редактор МБкЗ ИРУО;
(3) оболочка информационного наполнения;
(4) информационное наполнение банка знаний.
WEB-сайт МБкЗ. Сайт многоцелевого банка знаний предназначен для регистрации пользователей на сайте МБкЗ. После регистрации пользователь получает доступ к просмотру или редактированию ресурсов МБкЗ, а также получает возможность загрузить клиентскую часть банка знаний о преобразованиях компьютерных программ и установить ее на свой компьютер.
Средства редактирования банка знаний используются для редактирования информационного наполнения банка знаний, имеют графический пользовательский интерфейс и представляют собой распределенное приложение. Пользователь взаимодействует с клиентской частью средств редактирования, которая предоставляет единый интерфейс для редактирования каждого вида информации.
Логика средств редактирования разработана на основе соответствующей модели онтологии и взаимодействует с соответствующей компонентой информационного наполнения банка знаний.
Редактор базы знаний о трансформациях программ. Редактор управляется онтологией знаний о трансформациях программ и используется для редактирования знаний о трансформациях программ. Входной информацией для редактора являются знания о трансформациях программ. Выходом редактора является представление знаний о трансформациях программ в виде дерева понятий и модификация этих знаний в Базе знаний о трансформациях программ.
Редактор базы программ в терминах онтологии языка программирования высокого уровня. Каждый редактор базы программ управляется онтологией соответствующего языка программирования и используется для редактирования программ в терминах онтологии этого языка программирования. Входной информацией для редактора является программа на соответствующем языке программирования высокого уровня. Выходом редактора является представление программы в виде дерева понятий и модификация ее в базе программ в терминах онтологий языков программирования.
Рис. 4. Клиент - серверная архитектура банка знаний о преобразованиях компьютерных программ Редактор знаний о методах потокового анализа программ. Редактор управляется онтологией знаний о методах потокового анализа программ и используется для редактирования знаний о методах потокового анализа программ. Входной информацией для редактора являются знания о методах потокового анализа программ. Выходом редактора является представление знаний о методах потокового анализа программ в виде дерева понятий и модификация этих знаний в базе знаний о методах потокового анализа программ.
При разработке редакторов использовалась оригинальная технология разработки структурных веб-редакторов средствами метаредактора.
Разработаны информационные веб-ресурсы: онтология языков программирования высокого уровня, представленная в форме графа;
онтология знаний о методах потокового анализа программ, представленная в форме графа;
онтология знаний о трансформациях программ, представленная в форме графа.
Основу онтологии составляет абстрактный синтаксис этого языка;
абстрактный синтаксис языка описания знаний о методах потокового анализа программ;
абстрактный синтаксис языка описания знаний о трансформациях программ.
Показана возможность формального представления онтологии расширяемого языка для описания онтологий. Онтологии доступна для обработки веб-сервисами через оболочку системы управления информационными ресурсами. Для создании веб ресурсов был использован метаредактор.
Разработаны веб-ресурсы: база знаний программ в терминах онтологии языка программирования высокого уровня, представленная в форме графа;
база знаний о методах потокового анализа программ, представленная в форме графа;
база знаний о трансформациях программ, представленная в форме графа. Базы знаний доступны для обработки веб-сервисами через оболочку системы управления информационными ресурсами. Для создания веб-ресурсов были использованы веб редакторы базы программ в терминах онтологии языка программирования высокого уровня, базы знаний о методах потокового анализа программ, базы знаний о трансформациях программ.
В базе знаний программ модель онтологии языков программирования Си и Паскаль представлены на языке ИРУО (см. рис.5). Модель онтологии языков программирования представляет собой семантическую сеть понятий – набор понятий и направленных отношений между ними, снабженных специальной разметкой. Понятия (или вершины) сети представляют термины онтологии языка Паскаль, а направленные дуги описывают, каким образом одни термины онтологии определены через другие.
Термин разметки “ПОСЛЕДОВАТЕЛЬНОСТЬ” говорит о том, что для описания предка должны быть описаны все потомки, в то время как термин “АЛЬТЕРНАТИВА” говорит о том, что для описания предка достаточно описания одного из потомков. Спецификаторы на дугах определяют способ описания того понятия, в которое входит соответствующая размеченная дуга.
Разработанные модели онтологий языков программирования с помощью Редактора ИРУО заносятся в информационное наполнение банка знаний, чтобы на их основе создать специализированные редакторы программ на языках Си и Паскаль. Модели на языке ИРУО служат для Редактора ИРУО своего рода программами, а сам Редактор ИРУО является интерпретатором этих программ. Так, в процессе интерпретации модели онтологии языка Паскаль Редактор ИРУО становится по существу специализированным структурным редактором программ на языке Паскаль, а модель онтологии в данном контексте используется Редактором ИРУО в качестве метаинформации.
Рис. 5. Фрагмент модели онтологии языка Паскаль на языке ИРУО Разработаны модели и методы взаимодействия веб-сервисов с обрабатываемыми ими информационными ресурсами.
Разработана модель веб-сервиса для вычисления (построения) графа преобразованной программы из базы программ в терминах онтологии языка программирования высокого уровня. Веб-сервис взаимодействует с базами знаний о методах потокового анализа программ и базой знаний о трансформациях программ средствами оболочки системы управления информационными ресурсами. Показана возможность построения графа преобразованной программы автоматически на основе декларативного представления знаний о трансформациях программ и методах потокового анализа программ. В литературе нет описаний аналогичных средств.
Достоинством специализированного банка знаний о преобразованиях программ является высокая модифицируемость системы вследствие использования декларативного представления знаний о преобразованиях программ. Во всех существующих системах используется процедурное представление знаний.
В восьмой главе решается седьмая задача диссертационной работы разработка технологии использования методов и средств преобразования программ с переменным набором трансформаций и ее экспериментальное исследование.
Технология использования методов и средств преобразования программ с переменным набором трансформаций состоит из следующих основных этапов:
определения принадлежности языка программирования высокого уровня (ЯПВУ) к классу допустимых языков (если ЯПВУ не принадлежит к классу допустимых языков, то средство не использовать);
формирования набора трансформаций (если необходимая трансформация в каталоге отсутствует, то добавить ее в базу знаний путем формализации);
задания стратегии;
запуска программного средства на заданной стратегии и заданной программе на ЯПВУ и получении результата (исходная программа на ЯПВУ, если ни одна из стратегий не привела к преобразованию;
преобразованная программа и стратегия, на которой была получена эта программа).
Специализированный банк знаний можно использовать для поддержки научных исследований. Банк предоставляет следующие возможности: построения классификаций преобразований, в том числе новых;
позволяет формировать и развивать системы понятий в этой области;
включать новые преобразования в систему знаний, оперативно знакомить специалистов с новыми результатами;
проводить компьютерные эксперименты;
представлять научные результаты в виде, удобном для использования в профессиональной деятельности;
сопоставлять новые результаты с ранее полученными результатами;
минимизировать трудозатраты при написании научных обзоров.
Специализированный банк знаний можно использовать для разработки макетов блоков оптимизации в компиляторах. Разработка макетов блоков оптимизации в компиляторах открывает возможность для проведения исследований стратегий и наборов преобразований программ в таких компиляторах.
Специализированный банк знаний возможно использовать и для создания саморазвивающихся оптимизирующих компиляторов. Такой компилятор получается путем макетирования компилятора по схеме, предложенной выше, когда набор оптимизирующих преобразований программ содержит все преобразования, содержащиеся в базе знаний – как в текущем ее состоянии, так и во всех будущих.
Поскольку база знаний постоянно модифицируется – в нее добавляются новые преобразованиями и из нее исключаются морально устаревшие преобразования, то свойства макета компилятора будут автоматически изменяться по мере изменения базы знаний банка.
Специализированный банк знаний о преобразованиях программ, можно использовать для поддержки процесса обучения студентов.
Для лучшего усвоения знаний разработан учебно-методический комплекс по дисциплине «Теория вычислительных процессов и структур II. Теория и методы трансляции» и «Оптимизация программ» для студентов, обучающихся по специальности 351500 – математическое обеспечение и администрирование информационных систем.
Предложенная технология открывает возможности построения классификаций преобразований программ, в том числе новых, позволяет формировать и развивать системы понятий в этой области, включать новые преобразования в систему знаний, оперативно знакомить специалистов с новыми результатами. Технология обеспечивает проведение компьютерных экспериментов, открывает возможность сопоставления новых результатов с ранее полученными результатами.
ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ В диссертационной работе на основе проведенных автором исследований сделано теоретическое обобщение и получено решение важной научно-технической проблемы, состоящей в разработке моделей и методов реализации преобразований программ с переменным набором трансформаций и изменяемой стратегией управления трансформациями. В рамках указанной проблемы получены следующие основные теоретические и практические результаты.
1. Предложена концепция преобразователя программ с переменным набором трансформаций. Основными положениями концепции являются: выделение систем понятий, в терминах которых производится декомпозиция программ на языке высокого уровня и их преобразование в единое представление, построение модели онтологии для каждой системы понятий, анализ потока управления и потока данных программ, проверка контекстных условий трансформаций и выполнение трансформаций программ;
формирование баз программ, баз знаний о методах потокового анализа программ и базы знаний о трансформациях программ в терминах модели онтологий;
разработка алгоритма интерпретации стратегии преобразования, алгоритма генерации программ из единого представления на языки программирования высокого уровня и алгоритма визуализации историй преобразований программ.
2. Разработана онтология модели структурных программ и онтология расширенной модели структурных программ (МСП). Модель онтологии структурных программ представляет собой необогащенную систему логических соотношений с параметрами, записанную с использованием предложений многосортного языка прикладной логики. МСП является универсальным представлением программ. Язык ЯМСП определяется заданием значений параметров модели онтологии объекта преобразований программ. В работе определено расширение модели структурных программ терминами, используемыми при потоковом анализе программ для трех классов преобразований: классические, реструктурирующие и коммуникационные преобразования программ для машин с распределенной памятью. Расширенная МСП является обобщением некоторых схем программ. Единое представление позволяет реализовывать всевозможные алгоритмы потокового анализа программ. Информация для проверки контекстных условий трансформаций собирается до выполнения преобразований, а расширенная модель может быть получена путем интерпретации соответствующего метода потокового анализа программ из базы знаний.
3. Разработана онтология методов потокового анализа программ (абстрактный синтаксис языка для представления методов потового анализа программ и его операционная семантика), сформирована база знаний методов потокового анализа программ. Методы потокового анализа в базе знаний представлены на специальном языке описания методов потокового анализа программ (язык МПА). Разработаны каталоги классических, реструктурирующих и коммуникационных преобразований программ для машин с распределенной памятью, в которых знания о преобразованиях программ представлены в декларативном виде. Для интерпретации формул, приведенных в каталогах необходимо предварительно выполнить потоковый анализ программ, т.е. вычислить все фрагменты, дуги и атрибуты расширенной МСП.
4. Разработана онтология знаний о трансформациях программ (абстрактный синтаксис языка описания трансформаций программ - ЯОТ) и база знаний о трансформациях программ. Описание трансформации программ включает формулу трансформации и формулу контекстного условия, характеристическую функцию и стратегию преобразования. Контекстное условие в базе знаний представляет формулу (предикат), которая при подстановке в нее участка экономии станет истинным. Формула трансформации в модели онтологии представляет предикат, который при подстановке в него участка экономии и преобразованного участка экономии должен стать истинным.
5. Разработаны методы интерпретации базы знаний о трансформациях программ. Процесс интерпретации базы знаний о трансформациях программ рассматривается как последовательность шагов, на каждом из которых происходит применение к оптимизируемой программе одной трансформации. В качестве объекта оптимизации выступает модель программы. На каждом шаге процесса интерпретации базы знаний о трансформациях программ модель программы изменяется: к ней применятся правило трансформации, определяемое оптимизирующим преобразованием, применяемым на текущем шаге процесса оптимизации. Все подзадачи метода интерпретации связаны с интерпретацией знаний, представленных в базах знаний в виде формул и на основании этой интерпретации осуществляется анализ МСП, поиск участков экономии, построение характеристики участка экономии, реализация стратегии и построение новой МСП с преобразованным участком экономии.
6. Разработан и реализован специализированный банк знаний о преобразованиях программ, предложена архитектура банка знаний и метод его реализации, а также технология его использования для проведения компьютерных экспериментов, для моделирования блоков оптимизации в компиляторах и для поддержки обучения. Банк знаний состоит из информационной системы администрирования, информационного наполнения, оболочки информационного наполнения и программного наполнения.
7. Разработана технология использования методов и средств преобразования программ с переменным набором трансформаций и проведено ее экспериментальное исследование. Основные преимущества предложенной технологии заключаются в следующем: технология открывает возможности построения классификаций преобразований программ, в том числе новых;
позволяет формировать и развивать системы понятий в этой области;
включать новые преобразования в систему знаний, оперативно знакомить специалистов с новыми результатами;
проводить компьютерные эксперименты;
открывает возможности сопоставления новых результатов с ранее полученными результатами.
ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ Монография:
1.Князева М.А. Преобразования программ с переменным набором трансформаций.
Монография. - Владивосток: Изд-во Дальневост. ун-та, 2008.-208 с. ISBN 978-5 7944-2141- Статьи, опубликованные в реферируемых журналах из Перечня ВАК:
2.Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". Ч.1. Термины для описания объекта оптимизации // НТИ. Сер. 2.-2002.-№ 12.-С. 23-28.
3.Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". Ч.2. Термины для описания процесса оптимизации // НТИ. Сер. 2.-2003.-№ 1.-С. 22-29.
4.Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". Ч.3. Примеры описания некоторых оптимизирующих преобразований // НТИ. Сер. 2.-2003.-№ 2.-С. 27-34.
5.Клещев А.С., Князева М.А. Управление информацией о преобразованиях программ. I. Анализ проблем и пути их решения на основе методов искусственного интеллекта //Изв. РАН. ТиСУ. 2005. № 5, с. 120-129.
6.Клещев А.С., Князева М.А. Управление информацией о преобразованиях программ. II. Внутреннее устройство специализированного банка знаний о преобразованиях программ // Изв. РАН. ТиСУ. 2005. № 6, с. 101-110.
7.Князева М.А. Оптимизирующие компиляторы, управляемые базами знаний // Информационные технологии. - 2005.-№ 12.- с. 42-48.
8.Князева М.А., В.А. Тимченко. Структурные редакторы программ на языках программирования высокого уровня и генератор моделей структурных программ в Банке знаний о преобразованиях программ // Вестник Компьютерных и информационных технологий.-2006-№ 6-с.43-49.
9.Князева М.А., Матецкий С.В. Модель онтологии предметной области «Оптимизация коммуникаций для машин с распределенной памятью». Определение расширения языка модели структурных программ // Вестник Компьютерных и информационных технологий.-2006-№ 5-с.49-55.
10.Артемьева И.Л., Гаврилова Т.Л., В.В. Грибова, Клещев А.С., Князева М.А., Никифорова Н.Ю., Орлов В.А., Черняховская М.Ю., Шалфеева Е.А.
Мультидисциплинарная система управления информационными ресурсами различных уровней общности // Проблемы управления.-2006-№4-с.64-68.
11.Князева М.А., Бердник А.Н., Волков Д.А., Жеравин М.В., Зотов И.Ю., Маевский М.С., Плохих С.А., Тимченко В.А. Система, моделирующая процесс преобразования программ, управляемый знаниями // Программы для ЭВМ базы данных топологии интегральных микросхем. Официальный бюллетень Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.-2006. №4 -с.157.
12.Клещев А.С., Князева М.А. Интернет-система управления информацией о преобразованиях программ // Информационные технологии.- 2007.-№ 1.-с. 42-46.
13.Князева М.А., Волков Д.А. Потоковый анализ программ, управляемый знаниями // Программные продукты и системы. -2007.-№1.-с.49-52. (ISSN 0236-235X) 14.Князева М.А., Жеравин М.В. Генерация низкоуровневого кода, управляемая знаниями // Информационные технологии.-2007.-№10.-с. 7-12.
15.Князева М.А., Маевский М.С. Проверка контекстных условий и поиск участков экономии в системе преобразований программ // Информационные технологии. 2007.-№ 12.-с. 70-73.
16.Князева М.А., Тимченко В.А. Подсистема генерации единого внутреннего представления в системе преобразований программ. // Программные продукты и системы. -2008.-№1.-с.58-62. (ISSN 0236-235X) 17.Князева М.А., Плохих С.А. Концепция системы управления специализированного банка знаний о преобразованиях программ // Информационные технологии.-2009.- №5.-с. 36-40.
Статьи, опубликованные в материалах конференций и других журналах:
18.Артемьева И.Л., Князева М.А., Купневич О.А. Моделирование процесса оптимизации последовательных программ с использованием модели онтологий // Искусственный интеллект, т. 3, 2002, с. 467-473.