автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Управление преобразованиями программ с переменным набором трансформаций

На правах рукописи

Князева Маргарита Александровна 2 7 АВГ 2009

УПРАВЛЕНИЕ ПРЕОБРАЗОВАНИЯМИ ПРОГРАММ С ПЕРЕМЕННЫМ НАБОРОМ ТРАНСФОРМАЦИЙ

Специальность 05.13.01 - Системный анализ, управление и обработка

информации

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени доктора технических наук

Владивосток - 2009

003475734

003475734

Работа выполнена в лаборатории интеллектуальных систем Института автоматики и процессов управления Дальневосточного отделения РАН и в ГОУ высшего профессионального образования «Дальневосточный государственный университет» (ДВГУ).

Защита состоится « 25 » сентября 2009 г. в 10 часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.

С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН.

Научный консультант: доктор физико-математических наук, профессор

Клещев Александр Сергеевич Официальные оппоненты: член-корреспондент РАН,

доктор физико-математических наук

Смагин Сергей Иванович

доктор физико-математических наук, профессор

Касьянов Виктор Николаевич

доктор технических наук, профессор

Вагин Вадим Николаевич

Ведущая организация: Вычислительный центр

имени А.А. Дородницына РАН (г. Москва)

Автореферат разослан

Ученый секретарь

диссертационного совета Д 005.007.01, к.т.н.

Лебедев А.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Большой вклад в разработку и исследование программ внесли российские и зарубежные учёные: С.М. Абрамов, В.В. Воеводин, Вл.В. Воеводин, В.Ю. Волконский, В.М. Глушков, Б.А. Головкин, В.А. Евстигнеев, А.П. Ершов, В.П. Иванников, В.Э. Иткин, В.Н. Касьянов, В.Е. Котов, СЛ. Кривой, В.П. Кутепов, A.A. Ляпунов, С.С. Лавров, A.A. Летичевский, Э.З. Любимский, В.В. Мартынюк, A.C. Нариньяни, В.А. Непомнящий, И.В. Поттосин, Р.И. Подловченко, В.К. Сабельфельд, В.А. Серебряков, A.A. Терехов, Э.А. Трахтенгерц, Г.С. Цейтин, Ю.И.Янов, Ф.Э. Аллен, Д.Ф. Бэкон, М. Вольф, Дж. Кок, Г. Килделл, П. Кузо, М. Лэм, Д. Падуа, К-В. Ценг, Дж. Т. Шварц и многие другие.

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

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

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

Большой вклад в разработку и исследование онтологического подхода внесли российские и зарубежные ученые: В.Н. Вагин, Т.А. Гаврилова, A.C. Клещев, Г.С. Поспелов, Д.А. Поспелов, В.Ф. Хорошевский, T.R. Gruber, N. Guarino, J.F. Sowa и др. Онтологический подход успешно использовался в объектно-ориентированном проектировании и программировании, для проектирования интерфейса пользователя, реинжениринга бизнес-процессов, в концептуальном проектировании, при проектировании и разработке систем на основе моделей предметных областей, позволяющих в полной мере использовать знания экспертов и пополнять их в процессе работы.

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

Достижение цели работы предполагает решение следующих задач.

1. Разработка концепции преобразователя программ с переменным набором трансформаций на основе онтологического подхода.

2. Разработка онтологии единого представления программ и онтологии и его расширения.

3. Разработка онтологии методов потокового анализа программ и базы знаний о методах потокового анализа программ.

4. Разработка онтологии знаний о трансформациях программ и базы знаний о трансформациях программ.

5. Разработка методов интерпретации знаний о преобразованиях программ.

6. Разработка и реализация специализированного банка знаний о преобразованиях программ.

7. Разработка технологии использования методов и средств преобразования программ с переменным набором трансформаций и ее экспериментальное исследование.

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

Научная новизна работы. На основе проведенных научных исследований разработаны методы и средства создания нового класса программных средств -

системы управления преобразованиями программ с переменным набором трансформаций.

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

Впервые разработана концепция системы для управления преобразованиями программ с переменным набором трансформаций.

Впервые разработаны онтологии модели структурных программ и онтологии расширенной модели структурных программ.

Впервые разработаны онтологии методов потокового анализа программ и онтологии знаний о трансформациях программ, а также база знаний о методах потокового анализа программ и база знаний о трансформациях программ.

Впервые поставлена задача интерпретации декларативного представления базы знаний о трансформациях программ и разработан метод ее решения.

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

Предложена технология использования методов и средств управления преобразованиями программ с переменным набором трансформаций.

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

Практическая ценность и реализация результатов работы.

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

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

Разработанные методы интерпретации базы знаний о методах потокового анализа программ и базы знаний о трансформациях программ позволяют проводить исследования с преобразованиями программ с переменным набором трансформаций.

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

Программное средство для исследования преобразований программ с переменным набором трансформаций использовалось:

- при разработке почтового клиента для сотовых телефонов, основной целью которого является доступ с мобильного телефона к почтовым серверам по протоколам SMTP, РОРЗ, IMAP4;

- при разработке программного комплекса автоматизации работы туристических операторов на базе технологий ContourWEB;

- при разработке программного комплекса управления и учета услуг, предоставляемых посетителям интернет - ресурсов компании;

- при разработке программного комплекса для системы контроля сотрудников FrontLine.

Полученные в диссертации результаты внедрены (использованы): в научный процесс Института автоматики и процессов управления ДВО РАН, г. Владивосток; в учебный процесс Дальневосточного государственного университета, г. Владивосток.

Полученные результаты нашли применение при разработке Учебно-методических комплексов по дисциплинам «Теория вычислительных процессов и структур II. Теория и методы трансляции» и «Оптимизация программ» для студентов, обучающихся по специальности 351500 - математическое обеспечение и администрирование информационных систем и которые используются в процессе обучения.

Результаты диссертационной работы использовались в учебном процессе Дальневосточного государственного университета при чтении курсов лекций «Теория вычислительных процессов и структур И. Теория и методы трансляции», «Оптимизация программ», «Параллельное программирование», при выполнении курсовых работ (всего 30) и дипломных работ (всего 15) специальности 351500 - математическое обеспечение и администрирование информационных систем, а также при выполнении кандидатских диссертаций по специальности 051311-математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

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

Результаты диссертационной работы нашли применение при выполнении научно-исследовательских работ:

- проект РФФИ 06-07-89071-а «Исследование возможностей коллективного управления в семантическом вебе информационными ресурсами различных уровней общности» 2006-2008 гг.

- программа №14 Президиума РАН «Фундаментальные проблемы информатики и информационных технологий», проект 06-1-П14-052 «Параллельные вычисления в создании инструментальных и проблемно -ориентированных средств для решения вычислительно-сложных задач моделирования динамики океана и атмосферы с использованием спутниковой информации, оптимизации в условиях неопределенности и построения интеллектуальных систем», раздел 2 «Разработка средств поддержки построения интеллектуальных систем и корректного программного

обеспечения для многопроцессорных вычислительных комплексов» 2006-2008 гг.

- программа №15 фундаментальных исследований ОЭММПУ РАН «Проблемы анализа и синтеза интегрированных систем управления для сложных объектов, функционирующих в условиях неопределённости», проект 06-1-П15-055 «Синтез интеллектуальных систем управления базами знаний и базами данных при управлении сложными объектами в условиях неопределённости» 2006-2008 гг.

- инициативный научный проект ДВО РАН 06-Ш-А-01-007 «Интернет-система управления информацией о преобразованиях программ» 2006-2008 гг.

Апробация работы. Научные положения и результаты диссертационной работы докладывались и получили одобрение на Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (г. Новосибирск, 1997 г.), на Н-ой и Ш-ей Международной научно-технической конференции «Интерактивные системы: проблемы человеко - компьютерного взаимодействия» (г. Ульяновск, 1997 и 1999 г.), на третьем сибирском конгрессе по прикладной и индустриальной математике посвященный памяти С.Л. Соболева (г. Новосибирск, 1998г.), на Международной конференции по математической логике, посвященной 90-летию со дня рождения академика А.И. Мальцева (г. Новосибирск, 1999 г.), на четвертом сибирском конгрессе по прикладной и индустриальной математике, посвященном памяти М.А. Лаврентьева (г. Новосибирск, 2000 г.), на Международной конференции «Искусственный интеллект 2000» (Кацивели, Крым, 2000, 2006, 2007, 2008 г.), на Дальневосточной математической школе-семинаре им. Акад. Е.В. Золотова (г. Владивосток, в 2001, 2002, 2006, 2007 и 2008 г., г. Хабаровск в 2005г.), на Международной конференции по искусственному интеллекту КИИ (г. Коломна, 2002 г., г. Обнинск, 2006 г., г. Дубна 2008 г.), на Международной конференции К08-2003, КВ8-2005, КОЗ-2007 и КБ8-2008 (г. Варна, Болгария), на Международной конференции им. В.А. Трапезникова РАН «Параллельные вычисления и задачи управления» РАСО'2004, РАСО'2006 и РАСО'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 г. (г. Москва).

Публикация результатов работы.

Результаты диссертационной работы представлены в монографии, в 48 научных публикациях в отечественных и международных изданиях, в том числе 32 статьи, из них 7 статей в международных изданиях, 16 статей в российских реферируемых журналах, в свидетельстве об официальной регистрации программ для ЭВМ, в свидетельстве об отраслевой регистрации разработки.

Личный вклад автора. Автором осуществлена постановка задачи, получение всех экспериментальных исследований и самостоятельно получены все теоретические результаты. Автор принимал личное участие в разработке программных систем и ей принадлежит интерпретация всех основных экспериментальных и теоретических результатов, представленных в диссертации. В работах [2-4, 18-19, 22, 34,38-39] выделены основные компоненты онтологии предметной области. В работах [9,24-25] определены язык модели структурных программ и расширение языка модели структурных программ терминами потокового анализа. В работах [5-6, 10, 12,14-17,35,40,4143] выполнены постановки задач, разработаны основные теоретические положения. В работах [8, 13, 23, 26-28, 30-32, 36,44] описаны архитектура и основные задачи преобразователя программ. В работах [11,47] разработана архитектура преобразователя программ, управляемого знаниями.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

Обычно преобразование программ рассматривается как суперпозиция элементарных преобразований - трансформаций. Трансформация состоит из

формулы трансформации и формулы контекстного условия (условия применимости этой трансформации).

Определение 1. Под преобразованием программ с переменным набором трансформаций будем понимать отображение TV: (PxN) -» Р, где Р -множество программ на языке L, N - множество наборов элементарных трансформаций программ.

Определение 2. Назовём стратегией s(n) на заданном наборе элементарных трансформаций п конечную последовательность этих трансформаций, составленную из фиксированного их набора п.

Определение 3. Преобразователь с переменным набором п трансформаций TVS(n) = (TV, S (n)) - это абстрактное устройство, которое предназначено для преобразования заданной программы путем интерпретации заданной стратегии s (п) из множества стратегий S (п).

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

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

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

На вход преобразователю подается набор, стратегия преобразования программ и программа на языке программирования высокого уровня (ЯВУ). На выходе преобразователя формируются истории преобразований программ и программа на языке программирования высокого уровня, которая получена из входной программы в результате применения к ней трансформаций из входного набора в соответствии с заданной стратегией.

Преобразователь программ состоит из (1) средств декомпозиции программ на языке высокого уровня и их преобразования в единое представление, (2) средств преобразования программ в едином представлении, (3) средств визуализации историй преобразований программ и (4) средств генерации программ из единого представления на языки программирования высокого уровня.

Средства декомпозиции программ на языке высокого уровня и их преобразования в единое представление осуществляют преобразование входной программы на ЯВУ в единое представление. Программа в едином представлении может быть сохранена в базе программ для повторного исследования в эксперименте.

Средства преобразования программ в едином представлении включают: (1) интерпретатор стратегии преобразования; (2) анализатор потока управления и потока данных программ; (3) проверку контекстных условий трансформаций и выполнение трансформаций.

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

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

Средства генерации программ из единого представления на язык программирования высокого уровня осуществляют преобразование программы из единого представления на ЯВУ.

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

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

В третьей главе решается вторая задача диссертационной работы. В ней разработана онтология моделей структурных программ (МСП); онтология МСП, расширенная терминами потокового анализа. Дано описание проекций языков программирования высокого уровня на единое представление программ и единого представления программ на языки высокого уровня.

Набор преобразования и стратегия преобразования

_ п^рограмлл^ _ __>

Входная программа на язы ке программирования высокого уровня

Средства декомпозиции программ на языке высокого Ш' уровня и их преобразования в й-

единое представление

I

" Г5'ГГ;'ГГ1'Т!ТТ1ТГ:ТТ'Г:' ТПТТ'ТТТТГ-Т? 'ТТЛ П1ГГ" П"'Т'ГП'.~. '''

База программ в терминах онтологии «зыка программирования высокого ^ уровня

Средства преобразования программ в едином представлении Интерпретатор стратегии преобразования

^ПьГ-.Т

т тт.-тол

Анализатор потока управления и потока данных программ

Проверка контекстных условий трансформаций и вы полнение ТР§ н с форм_а_иий_____ ^

База знаний о методах потокового Цналиаа поограм|уи

База знаний о трансформациях программ _

Сродства ¡|

визуализации г

историй !|

преобразований |

программ ц

-------- .-ГV - - гг. -, -Л

Средства генерации программ из единого представления на языки программирования высокого уровня

Истории преобразований V программ

Выходная программа на языке программирования высокого уровня

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

Описание терминологии некоторой предметной области вместе с определением смысла терминов в современном мире получило название модели онтологии.

Онтология МСП (термины, с использованием которых описывается модель онтологии структурных программ). Полное описание модели приведено в диссертации.

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

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

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

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

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

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

Будем считать, что все фрагменты могут быть разбиты на три группы: операторы описания, исполнимые операторы и элементы операторов. Каждый фрагмент характеризуется своим классом, например, фрагмент может иметь класс оператор присваивания, оператор цикла, оператор описания функций и т.д. Функция ^га^С/аи возвращает для указанного адреса фрагмента класс этого фрагмента. Множество названий классов фрагментов (каждой группы) в программе задают значения параметров Операторы описания, Исполнимые операторы, Элементы операторов.

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

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

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

На множестве фрагментов и идентификаторов программы определены функции и отношения, которые позволяют определить структуру программы и некоторые ее свойства.

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

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

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

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

Значение параметра Элементарные типы задает для языка множество идентификаторов типов данных, являющимися базовыми для всех остальных типов данных этого языка.

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

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

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

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

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

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

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

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

Любая переменная может иметь либо простой тип, либо сложный. К простым типам относятся такие типы, как целый, вещественный и логический. Все эти типы являются неявно приводимыми друг к другу. К операндам простого типа применимы следующие операции: +, -, *, /, взятие адреса, обращение по указателю, And, Or, Not. Разрешены динамические переменные, операции New и Dispose, а также адресная арифметика.

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

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

Онтология расширенной МСП.

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

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

Расширенная МСП для преобразований программ является обобщением схем программ. Так, например, если из описания МСП Имена дуг исключить Дуги управления, используемые при потоковом анализе, то можно получить схему Мартынюка. Если из описания расширенной МСП исключить описание всех атрибутов, и оставить вычисление атрибутов А и Я только для Исполнимых операторов, то можно получить схему Лаврова.

Большинство векторизующих и распараллеливающих компиляторов используют граф зависимости по данным (ГПЗ). ГПЗ можно получить путем введения в расширенную МСП классических преобразований программ специальный атрибут Раг ОО и отношение - итерационная зависимость.

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

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

В четвертой главе решается третья задача диссертационной работы.

В ней разработана онтология методов потокового анализа программ (абстрактный синтаксис языка для представления методов потокового анализа программ и его операционная семантика), приведены методы потокового анализа программ, представленные в базе знаний о методах потокового анализа программ.

Онтология знаний о методах потокового анализа программ. Полное описание онтологии знаний о методах потокового анализа программ приведено в диссертации.

Преобразования программ проводятся на основе информации, собранной в результате потокового анализа программ.

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

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

База методов потокового анализа формируется экспертом предметной области. В нее могут входить как методы взятые из различных источников (описанные в литературе, в сети Интернет и т.д.), так и методы разработанные непосредственно экспертом.

База знаний о методах потокового анализа программ в терминах онтологии. В базе знаний о методах потокового анализа программ методы потокового анализа представлены на языке МПА.

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

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

В пятой главе решается четвертая задача диссертационной работы. В ней разработаны онтология знаний о трансформациях программ (абстрактный синтаксис языка описания трансформаций программ - ЯОТ), а также база знаний о трансформациях программ.

Термины, для описания знаний о трансформациях программ. Полное описание онтологии знаний о трансформациях программ приведено в диссертации.

Обычно преобразование проводится не над всей программой, а над каким-то ее участком, не обязательно непрерывным. Множество фрагментов программы, необходимых для принятия решения о преобразовании, называется Кандидатом в участки экономии, а то множество фрагментов, на котором истинно контекстное условие преобразования, называется Участком экономии. Таким образом, участок экономии - это кандидат, для которого истинно контекстное условие преобразования.

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

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

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

Каждое преобразование имеет простые и множественные параметры. Каждый фрагмент простой части участка экономии будем называть значением соответствующего ему простого параметра участка экономии.

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

Контекстное условие преобразования описывает свойства участка экономии, к которому применимо это преобразование. В данной модели онтологии контекстное условие представляется в виде предиката, аргументами которого являются номер шага истории преобразования программ, а также некоторый кандидат в участки экономии.

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

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

экономии с выбранной характеристикой и подвергается преобразованию на этом шаге истории.

Параметры с одинаковым контекстом - это множество пар номеров параметров участка экономии до и после преобразования, у которых контексты должны совпадать.

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

Полное описание базы знаний о трансформациях программ приведено в приложениях диссертационной работы.

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

Шнсслврвнтюостчисра ю цкгв етеред

Ошхаяр^упгтаосвго мгиагвдам

Вмфпэров+ьк

Харжгерои«сгарфт+я

Сгщтпсппаиэди

здмкчдкмеа»

МуМ'.ШЯ»!

(г х в о у п уг)

Отсос Омзх

Фср^л

"/Г.

\

Рис. 2. Пример описания трансформации программы в базе знаний о трансформациях программ

В шестой главе диссертации поставлена и решена пятая задача диссертационной работы - разработка методов интерпретации базы знаний о трансформациях программ.

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

фрагментов, своим множеством идентификаторов, и т.д. Каждое преобразование обладает следующими свойствами: участком экономии (УЭ), контекстным условием (КУ), характеристической функцией (ХФ), стратегией применения.

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

Метод ИНТЕРПРЕТАЦИЯ, СТРАТЕГИИ, ПРЕОБРАЗОВАНИЯ_ПРОГРАММ

Входные данные: модель структурной программы (МСП); стратегия

преобразования; набор преобразования.

Выходные данные: модель программы, расширенная терминами потокового анализа программ; история преобразований модели структурной программы.

Примененные функции в методе: Проанализировать МСП, Найти участки экономии, Построить характеристики УЭ, Реализовать стратегию, Построить новую МСП с преобразованным УЭ рассмотрены как отдельные методы.

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

Метод Проанализировать МСП.

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

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

Метод Найти участки экономии. Обобщённое контекстное условие преобразования в базе знаний задается следующим образом: 3<а1,..,ап> (Р1(а1,...,ап),

3{<Ы,..,Ьт>}(Р2(а1,..,ап,Ы,..,Ьт),

Э{<с1,..,ск>}(РЗ(а1,..,ап,Ы,..Ьт, с1,..,ск),)) &

Э{<е1,..,е1>}(Р4(а1,..,ап,е1,..,еО,

У<<!1 ,..,су>(Р5(а1 ,..,ап,е 1 ,..е1, с11,..,ф),))) Здесь а, Ь, с, б, е - имена переменных, Р1-Р5 - обобщенные формулы.

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

Находится подстановка значений фрагментов для вектора переменных а1..ап такая, что предикат Р1 истинен. Этот вектор значений образует простую часть участка экономии. Затем, при найденных значениях переменных а1..ап происходит поиск всех подстановок значений переменных Ы..Ьт, удовлетворяющих условию Р2. Для каждой такой подстановки Ь1..Ьш, в свою очередь, ищется множество векторов с1..ск, удовлетворяющих условию РЗ. Затем, для этих же найденных значений переменных а1..ап происходит поиск всех подстановок значений переменных е1..е1, удовлетворяющих условию Р4. Однако, так как для вектора е1..е1 в качестве дополнительного условия определена отрицательная множественная формула Р5, то каждая подстановка е1..е1 попадает в участок экономии только в том случае, если для нее не существует ни одной подстановки фрагментов <31.при которых Р5 стала бы истинной.

Метод Построить характеристики УЭ.

Характеристическая функция в модели онтологии представляет функцию, которая при подстановке в неё участка экономии вернет рациональное число -его характеристику.

Обобщенная характеристическая функция в базе знаний задается следующим образом: <а1,..,ап> (Р1(а1,...,ап).

В методе Построить характеристики УЭ вычисляется характеристика участка экономии как значение терма Р. Аргументами терма Р являются переменные а1,..,ап из простой части участка экономии.

Метод Реализовать стратегию.

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

В методе Реализовать стратегию задание стратегии осуществляется путем выбора одного из следующих вариантов: Мах, Мт, Яп<1

Метод Построить новую МСП с преобразованным УЭ.

Обобщенное правило трансформации в базе знаний задается следующим образом:

В<а1,..,ап>(Р,(а1,...,аа,Ьь...,Ьь)&р2(а1,...,аь,Ьь...,Ьь, С1,...,сс)&...&Рп(...)

а1=>Ь.....аь=>Ьь, а^Сь—а^Сс,...);

Здесь: аь...аа - вектор подстановок исходных фрагментов в программе;

Ь[.....Ьь, С1...,СС и т.д. - вектора подстановок новых фрагментов. РЬ...,Р„ -

формулы, определяющий свойства создаваемых фрагментов; а|=>Ьь...аь=>Ьь, а^сь.-.а^с,; и т.д. - правила, определяющие, какой фрагмент заменять и как производить эту замену.

В методе Построить новую МСП с преобразованным УЭ происходит интерпретация трансформации следующим образом.

Для вектора подстановок аь...,ап создать новый вектор подстановок Ьь...,Ьь, причем свойства создаваемых фрагментов определяются формулой Рь Для формул Рг-.-Р,, - аналогично. Фрагменты, созданные формулой Р„ могут использоваться в формуле Рп+1 в качестве аргументов. Последовательно перебрать все пары подстановок а^Ь],..., аь=>Ьь, а1=>сь...ас=>сс, для каждой пары. Для пары подстановок а=>Ь, заменить фрагмент а на фрагмент Ь. Все дуги, ведущие к фрагменту а, заменить соответствующими дугами к фрагменту Ь. Последовательно перебрать все фрагменты, проверив, что фрагмент имеет все необходимые атрибуты и дуги согласно спецификации МСП.

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

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

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

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

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

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

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

Архитектура банка знаний. Банк знаний (рис.3) состоит из (1) информационной системы администрирования (ИСА), (2) информационного наполнения (ИН), (3) оболочки ИН и (4) программного наполнения (ПН).

Информационная система_администрирования банка знаний

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

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

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

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

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

Специализированный банк знаний о преобразованиях компьютерных программ

Администратор

Сопровождающий банка знаний

1. Информационная система администрирования банка знаний

Административная база данных

2.Информационное наполнение

7Т

3. Оболочка информационного наполнения

V

-(.Программное наполнение

Рис. 3. Компоненты специализированного банка знаний о преобразованиях

компьютерных программ Обозначения на рисунке три и далее:

* передача управления, | передача данных.

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

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

Подсистема преобразования программ состоит из следующих подсистем: поиска участков экономии и проверки контекстных условий; подсистема

замены участка экономии на преобразованный участок экономии; подсистема измерения эффективности преобразований.

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

Методы реализации банка знаний. На рис. 4 представлена клиент -серверная архитектура банка знаний о преобразованиях компьютерных программ, разработанной по технологии «клиент-сервер».

На клиентской части архитектуры банка знаний находятся: (1) интерфейс средств редактирования банка знаний; (2) интерфейс системы преобразования программ; (3) интерфейс системы построения макетов оптимизирующих компиляторов.

На серверной части архитектуры банка знаний находятся: (1) WEB- сайт многоцелевого банка знаний (МБкЗ); (2) средства редактирования банка знаний и редактор МБкЗ ИРУО; (3) оболочка информационного наполнения; (4) информационное наполнение банка знаний.

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

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

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

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

модификация ее в базе программ в терминах онтологии языков программирования.

Рис. 4. Клиент - серверная архитектура банка знаний о преобразованиях компьютерных программ

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

модификация этих знаний в базе знаний о методах потокового анализа программ.

При разработке редакторов использовалась оригинальная технология разработки структурных веб-редакторов средствами метаредактора.

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

Разработаны веб-ресурсы: база знаний программ в терминах онтологии языка программирования высокого уровня, представленная в форме графа; база знаний о методах потокового анализа программ, представленная в форме графа; база знаний о трансформациях программ, представленная в форме графа. Базы знаний доступны для обработки веб-сервисами через оболочку системы управления информационными ресурсами. Для создания веб-ресурсов были использованы веб-редакторы базы программ в терминах онтологии языка программирования высокого уровня, базы знаний о методах потокового анализа программ, базы знаний о трансформациях программ.

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

Термин разметки "ПОСЛЕДОВАТЕЛЬНОСТЬ" говорит о том, что для описания предка должны быть описаны все потомки, в то время как термин "АЛЬТЕРНАТИВА" говорит о том, что для описания предка достаточно описания одного из потомков. Спецификаторы на дугах определяют способ описания того понятия, в которое входит соответствующая размеченная дуга.

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

программ на языке Паскаль, а модель онтологии в данном контексте используется Редактором ИРУО в качестве метаинформации.

нетерминал

$имя: Описание типа

$имя'. 1гЛевег $тип: символ

$имя: Элементарный и

.АЛЬТЕРНАТИВА

$имя: геа1 $тип: символ

$имя: Ьоо1вал I $тип: символ

АЛЬТЕРНАТИВА

АЛЬТЕРНАТИВА

$имя: Указатель

; АЛЬТЕРНАТИВА'

$имя: Элементарных тмгтов

е

\5

$имя: Массивов

$имя: Указателей

^ПОдлЕДбвАТЕЛЬНОСТьПОСЛЕДОВАТЕЛЬНОСТЬ

гЧ /

Й! 1/!

$имя: Нижняя граница

$тип: сорт $значение: Целое число

$имя: Верхняя граница

$тип: сорт $эначение: Целое число

Рис. 5. Фрагмент модели онтологии языка Паскаль на языке ИРУО

Разработаны модели и методы взаимодействия веб-сервисов с обрабатываемыми ими информационными ресурсами.

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

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

В восьмой главе решается седьмая задача диссертационной работы -разработка технологии использования методов и средств преобразования

программ с переменным набором трансформаций и ее экспериментальное исследование.

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

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

Специализированный банк знаний можно использовать для разработки макетов блоков оптимизации в компиляторах. Разработка макетов блоков оптимизации в компиляторах открывает возможность для проведения исследований стратегий и наборов преобразований программ в таких компиляторах.

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

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

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

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

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

4. Разработана онтология знаний о трансформациях программ (абстрактный синтаксис языка описания трансформаций программ - ЯОТ) и база знаний о трансформациях программ. Описание трансформации программ включает формулу трансформации и формулу контекстного условия, характеристическую функцию и стратегию преобразования. Контекстное условие в базе знаний представляет формулу (предикат), которая при подстановке в нее участка экономии станет истинным. Формула трансформации в модели онтологии представляет предикат, который при подстановке в него участка экономии и преобразованного участка экономии должен стать истинным.

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

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

информационной системы администрирования, информационного наполнения, оболочки информационного наполнения и программного наполнения.

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

ОПУБЛИКОВАННЫЕ РАБОТЫ ПО ТЕМЕ ДИССЕРТАЦИИ

Монография:

1. Князева М.А. Преобразования программ с переменным набором трансформаций. Монография. - Владивосток: Изд-во Дальневост. ун-та, 2008.208 с. ISBN 978-5-7944-2141-0

Статьи, опубликованные в реферируемых журналах из Перечня ВАК:

2. Артемьева И.Л., Князева М.А., Купневич O.A. Модель онтологии предметной области "Оптимизация последовательных программ". 4.1. Термины для описания объекта оптимизации // НТИ. Сер. 2.-2002.-№ 12.-С. 23-28.

3. Артемьева И.Л., Князева М.А., Купневич O.A. Модель онтологии предметной области "Оптимизация последовательных программ". 4.2. Термины для описания процесса оптимизации // НТИ. Сер. 2.-2003 .-№ 1.-С. 22-29.

4. Артемьева И.Л., Князева М.А., Купневич O.A. Модель онтологии предметной области "Оптимизация последовательных программ". Ч.З. Примеры описания некоторых оптимизирующих преобразований // НТИ.Сер.2.-2003 .-№ 2.-С.27-34.

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

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

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

8. Князева М.А., В.А. Тимченко. Структурные редакторы программ на языках программирования высокого уровня и генератор моделей структурных программ в Банке знаний о преобразованиях программ // Вестник Компьютерных и информационных технологий.-2006.-№ 6.-С.43-49.

9. Князева М.А., Матецкий C.B. Модель онтологии предметной области «Оптимизация коммуникаций для машин с распределенной памятью».

Определение расширения языка модели структурных программ // Вестник Компьютерных и информационных технологий.-2006.-№ 5.-С.49-55.

10. Артемьева И.Л., Гаврилова Т.Л., В.В. Грибова, Клещев A.C., Князева М.А., Никифорова Н.Ю., Орлов В.А., Черняховская М.Ю., Шалфеева Е.А. Мультидисциплинарная система управления информационными ресурсами различных уровней общности И Проблемы управления.-2006.-№4.-С.64-68.

11. Князева М.А., Бердник А.Н., Волков Д.А., Жеравин М.В., Зотов И.Ю., Маевский М.С., Плохих С.А., Тимченко В.А. Система, моделирующая процесс преобразования программ, управляемый знаниями // Программы для ЭВМ базы данных топологии интегральных микросхем. Официальный бюллетень Федеральной службы по интеллектуальной собственности, патентам и товарным знакам.-2006.-№4. -С.157.

12. Клещев A.C., Князева М.А. Интернет-система управления информацией о преобразованиях программ // Информационные технологии.-2007.-№1.-С. 42-46.

13. Князева М.А., Волков Д.А. Потоковый анализ программ, управляемый знаниями // Программные продукты и системы.-2007.-№1.-С.49-52. (ISSN 0236-235Х)

14. Князева М.А., Жеравин М.В. Генерация низкоуровневого кода, управляемая знаниями // Информационные технологии.-2007.-№ 10.-С. 7-12.

15. Князева М.А., Маевский М.С. Проверка контекстных условий и поиск участков экономии в системе преобразований программ // Информационные технологии .- 2007.-№ 12.-С. 70-73.

16. Князева М.А., Тимченко В.А. Подсистема генерации единого внутреннего представления в системе преобразований программ. // Программные продукты и системы. -2008.-№1.-С.58-62. (ISSN 0236-235Х)

17. Князева М.А., Плохих С. А. Концепция системы управления специализированного банка знаний о преобразованиях программ // Информационные технологии.-2009.- №5.-С. 36-40.

Статьи, опубликованные в материалах конференций и других журналах:

18. Артемьева И.Л., Князева М.А., Купневич O.A. Моделирование процесса оптимизации последовательных программ с использованием модели онтологий // Искусственный интеллект- Т. 3.- 2002.-С. 467-473.

19. Князева М.А., Матецкий C.B. Модель онтологии предметной области «Оптимизация коммуникаций для машин с распределенной памятью» // Искусственный интеллект. Т. 3.- 2003.- С. 102-108.

20. Князева М.А. Банк знаний о преобразованиях компьютерных программ // Искусственный интеллект.- Т. 3,- 2004.- С. 179-186.

21. Князева М.А., Максимов C.B. Каталог реструктурирующих оптимизирующих преобразований в специализированном банке знаний по оптимизации программ // Научная сессия МИФИ-2004: Сборник научных трудов.-Т.З.- М.: МИФИ,- 2004,- С.190-191.

22. Князева М.А., Максимов C.B. Модель онтологии реструктурирующих оптимизирующих преобразований // II Международная конференция

«Параллельные вычисления и задачи управления» [Электронный ресурс].-Труды конференции.-2004- (CD ROM).-ISBN 5-201-14974-Х.

23. Князева М.А. Преобразователь программ специализированного банка знаний о преобразованиях компьютерных программ. Искусственный интеллект. Интеллектуальные и многопроцессорные системы-2004 // Материалы Международной научной конференции Интеллектуальные и многопроцессорные системы. - 2004.- Т. 1.-Таганрог: Изд-во ТРТУ.- 2004.-С.186-189.

24. Князева М.А., Купневич O.A. Модель онтологии предметной области «Оптимизация последовательных программ». Определение языка модели структурных программ // НТИ. Сер. 2.-2005.-№ 2.-С. 17-21.

25. Князева М.А., Купневич O.A. Модель онтологии предметной области «Оптимизация последовательных программ». Определение расширения языка модели структурных программ терминами потокового анализа // НТИ. Сер. 2,-2005.-№ 4.-С. 14-22.

26. Князева М.А., Зотов И.Ю. Подсистема потокового анализа для распараллеливаемых программ в банке знаний о преобразованиях программ // Искусственный интеллект.-Т.4.- 2005.- С. 192-199.

27. Князева М.А., Тимченко В.А. Структурные редакторы программ на языках программирования высокого уровня и генератор моделей структурных программ в банке знаний о преобразованиях программ И Искусственный интеллект,- Т.4.- 2005.- С. 200-208.

28. Князева М.А..С.А. Плохих. Измерительная подсистема для преобразователя программ // Научная Сессия МИФИ -2005: Сборник научных трудов,- Т.З.- М.: МИФИ.-2005.-С. 130-131.

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

30. Князева М.А., Бердник А.Н. Интерпретация знаний о трансформации программ в специализированном банке знаний о преобразованиях программ // Искусственный интеллект. Украина, Донецк: Институт проблем искусственного интеллекта.- 2006.- Т. 4.- С.191-200.

31. Князева М.А., Зотов И.Ю. Поиск участков программ для распараллеливания в системе потокового анализа в специализированном банке знаний о преобразованиях программ // Научная сессия МИФИ-2006: Сборник научных трудов,- Т. 3,- М: МИФИ,- 2006,- С. 136-137.

32. Князева М.А., Зотов И.Ю. Решение задачи распараллеливания программ в специализированном банке знаний о преобразованиях программ // III Международная конференция "Параллельные вычисления и задачи управления" [Электронный ресурс]. -Труды конференции.- 2006.-(CD ROM).

33. Князева М.А. Интеллектуальная система управления знаниями об оптимизации программ // X национальная конференция по искусственному интеллекту с международным участием: Труды конференции.- В З-т.-T.l.- М: Физматлит, 2006,- С. 61-68.

34. Князева М.А., Волков Д.А. Онтология потокового анализа программ для классических оптимизирующих преобразований // Вторая международная конференция по когнитивной науке: тезисы докладов. Санкт-Петербург: Филологический факультет СПбГУ, 2006.-Т. 2. - С. 579-580.

35. Князева М.А., Пронина Е.А. Методы потокового анализа распараллеливаемых программ в специализированном банке знаний о преобразованиях программ // Искусственный интеллект. - Украина, Донецк: Институт проблем искусственного интеллекта. - 2007. - Т.З. - С. 79-85. - ISSN 1561-5359.

36. Клещев А.С., Князева М.А., Тимченко В.А. Интеллектуальная система генерации единого внутреннего представления в системе преобразований программ // Труды Второй международной конференции "Системный анализ и информационные технологии" САИТ-2007, 10-14 сентября, 2007, Обнинск, Россия. М.: Издательство ЛКИ, 2007. В 2 т., Т.1.-С.130-133. - ISBN 978-5-38200437-2.

37. Князева М.А. Маевский М.С. Модель представления знаний о преобразованиях программ на основе онтологии // Материалы Всероссийской конференции с международным участием «Знания-Онтологии-Теории» (ЗОНТ-07), 14-16 сентября 2007, Новосибирск, Россия. Новосибирск: Институт математики, 2007. В 2 т., т.1- С. 159-165. - ISSN 0568-661Х.

38. Knyazeva М.А., Kupnevich О.А. Expert system for simulation of program optimization // Joint NCC&IIS Bull., Сотр. Science, 1999, №.12. P. 24-28.

39. Artemjeva I.L., Knyazeva M. A., Kupnevich O. A. Processing of knowledge about optimization of classical optimizing transformations // International Journal Information Theories & Applications, 2003.V. 10, № 2. P. 126-132.

40. Kleshchev A.S., Knyazeva M.A. Controlling Information on Program Transformations: I. Analysis of Problems and Ways of Their Solution with methods of Artificial Intelligence // Journal of Computer and Systems Sciences International, 2005, V.44, № 5.- P. 784-792.

41. Kleshchev A.S., Knyazeva M.A. Controlling Information on Program Transformations: II. The Internal Structure of a Special-Purpose Knowledge Bank on Program Transformations // Journal of Computer and Systems Sciences International, 2005. V.44, № 6,-P. 932-941.

42. Knyazeva M.A., Kleschev A.S. A concept of the knowledge bank on computer program transformations // In proceedings of Xl-th International conference "Kowledge-diaIog-soIution"(KDS-2005). 2005.Varna, Bulgaria. V. 1. P. 147-152.

43. Knyazeva M.A, Kleshchev A.S. A Web-system for Computer Experiments in the Field of Program Transformations // International Journal Information Theories & Applications. - Bulgaria, Sofía: FOI-COMMERCE. - 2006. - Vol. 13. -№ 4 - PP. 331-336 - ISSN: 1310-0513 (printed), 1313-0463 (online), 1313-0498 (CD/DVD).

44. Knyazeva M.A, Volkov D.A. Management of information on program flow analysis // Proceedings of XIII-th Conference "Knowledge-Dialogue-Solutions", June

18-24, 2007. - Varna (Bulgaria). - Vol. 2. - PP. 411-417. - ITHEA, Sofia, 2007. -Printed in Sofia (Bulgaria) by Institute of Information Theories and Applications FOI ITHEA. - Текст англ. - ISSN: 1313-0087 (paperback); 1313-1176 (CD); 1313-1206 (online). FSBN Vol2: 978-954-16-2010-6 (paperback); 978-954-16-2011-3 (CD); 978-954-16-2012-0 (online).

45. Knyazeva M.A., Volkov D.A. Management of information on program flow analysis // International Journal Information Technologies & Knowledge. - Bulgaria, Sofia: FOI-COMMERCE. - 2008. - Vol. 2. - № 1 - PP. 11-16 - ISSN: 1313-0455 (printed), 1313-048X (online), 1313-0501 (CD/DVD).

46. Knyazeva M.A., Timchenko V.A. Ontology-based model of representation of knowledge about language mappings // International Book Series "INFORMATION SCIENCE & COMPUTING", Number 5. Supplement to the International Journal "INFORMATION TECHNOLOGIES & KNOWLEDGE" -Bulgaria, Sofia: FOI ITHEA. - 2008. - Vol. 2. - PP. 111-118 - ISSN: 1313-0455 (printed), 1313-048X (online), 1313-0501 (CD/DVD).

Свидетельства о регистрации программ:

47. Князева М.А., Бердник А.Н., Волков Д.А., Жеравин М.В., Зотов И.Ю., Маевскнй М.С., Плохих С.А., Тимченко В.А. Система, моделирующая процесс преобразования программ, управляемый знаниями. Свидетельство РОСПАТЕНТА об официальной регистрации программы для ЭВМ № 2006612928., 15 августа 2006г.

48. Князева М.А. Учебно-методический комплекс «Оптимизация программ». Свидетельство об отраслевой регистрации разработки № 5861, 17 марта 2006 г.

Князева Маргарита Александровна

Управление преобразованиями программ с переменным набором трансформаций

Автореферат

Подписано к печати 29.04.09 Усл. печ. л. 1,8 Уч.-изд. л. 1,5

Формат 60x84/16 Тираж 100 Заказ 22

Издано ИАПУ ДВО РАН. Владивосток, ул. Радио, 5 Отпечатано участком оперативной печати ИАПУ ДВО РАН Владивосток, ул. Радио, 5

ВВЕДЕНИЕ.

ГЛАВА 1. ПРЕОБРАЗОВАНИЯ ПРОГРАММ. ОБЗОР ЛИТЕРАТУРЫ.

1.1. Основные понятия и постановка проблемы преобразований программ

1.2. Современное состояние теоретических исследований в области преобразований программ.

1.2.1. Модели программ, ориентированные на трансформации программ.

1.2.2. Классификация трансформаций.

1.3. Современное состояние разработки блоков оптимизации в компиляторах.

1.3.1. Представления программ.

1.3.2. Представление трансформаций в реализациях трансформационных машин.

1.3.3. Потоковый анализ программ.

1.4. Средства автоматизации построения оптимизирующих компиляторов

1.5. Компьютерные эксперименты в области преобразований программ.

1.6. Выводы к первой главе.

ГЛАВА 2. КОНЦЕПЦИЯ ПРЕОБРАЗОВАТЕЛЯ ПРОГРАММ С ПЕРЕМЕННЫМ НАБОРОМ ТРАНСФОРМАЦИЙ.

2.1. Требования к преобразователю программ с переменным набором трансформаций.

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

2.3. Выводы ко второй главе и постановки задач исследования.

ГЛАВА 3. ОНТОЛОГИЯ МОДЕЛИ ОБЪЕКТА ПРЕОБРАЗОВАНИЙ.

3.1. Постановка задачи моделирования объекта преобразований.

3.2. Онтология МСП.

3.2.1. Определение МСП.

3.2.2. Вспомогательные термины.

3.2.3. Классы фрагментов программы, идентификаторы программы.

3.2.4. Типы данных.

3.2.5. Дуги управления.

3.2.6. Атрибуты.

3.3. Проекции языков программирования высокого уровня на единое представление программ и единого представления программ на языки высокого уровня.

3.4. Онтология расширенной МСП.

3.4.1. Онтология расширенной МСП для классических оптимизирующих преобразований.

3.4.2. Онтология расширенной МСП для реструктурирующих преобразований

3.4.3. Онтология расширенной МСП для коммуникационных преобразований

3.5. Онтологические соглашения онтологии МСП и онтологии расширенной МСП.

3.6. Выводы к третьей главе.

ГЛАВА 4. ПРЕДСТАВЛЕНИЕ МЕТОДОВ ПОТОКОВОГО АНАЛИЗА ПРОГРАММ

4.1. Постановка задачи представления методов потокового анализа программ.

4.2. Абстрактный синтаксис языка описания методов потокового анализа программ и его операционная семантика.

4.3. База знаний о методах потокового анализа программ.

4.4. Выводы к четвертой главе.

ГЛАВА 5. ПРЕДСТАВЛЕНИЕ ТРАНСФОРМАЦИЙ.

5.1. Постановка задачи представления трансформаций.

5.2. Абстрактный синтаксис языка описания трансформаций.

5.3. База знаний о трансформациях программ.

5.4. Выводы к пятой главе.

ГЛАВА 6. МЕТОДЫ ИНТЕРПРЕТАЦИИ БАЗЫ ЗНАНИЙ О ТРАНСФОРМАЦИЯХ ПРОГРАММ.

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

6.2. Метод интерпретации стратегии преобразования.

6.3. Метод поиска участка экономии.

6.4. Метод выполнения преобразования.

6.5. Выводы к шестой главе.

ГЛАВА 7. СПЕЦИАЛИЗИРОВАННЫЙ БАНК ЗНАНИЙ О ПРЕОБРАЗОВАНИЯХ ПРОГРАММ.

7.1. Постановка задачи разработки средств преобразования программ с переменным набором трансформаций.

7.2. Требования к СБкЗПП.

7.3. Архитектура СБкЗПП.

7.4. Методы реализации СБкЗПП.

7.5. Выводы к седьмой главе.

ГЛАВА 8. ТЕХНОЛОГИЯ ИСПОЛЬЗОВАНИЯ МЕТОДОВ И СРЕДСТВ ПРЕОБРАЗОВАНИЯ ПРОГРАММ С ПЕРЕМЕННЫМ НАБОРОМ ТРАНСФОРМАЦИЙ И ЕЕ ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ.

8.1. Технология использования методов и средств преобразования программ с переменным набором трансформаций.

8.2. Экспериментальное исследование технологии использования методов и средств преобразования программ с переменным набором трансформаций.

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

8.2.1.1. Модель измерения временных характеристик МСП.

8.2.1.2. Модель измерения характеристик объема МСП.

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

8.3. Использование технологии для экспериментального исследования переменных наборов трансформаций.

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

8.5. Использование технологии для обучения студентов.

8.5.1. Организация лабораторного практикума.

8.5.2. Проведение деловых игр на лабораторном практикуме.

8.6. Выводы к восьмой главе.

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ.

ГЛОССАРИЙ.

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

Большой вклад в разработку и исследование программ внесли российские и зарубежные учёные: С.М. Абрамов, В.В. Воеводин, Вл.В. Воеводин, В.Ю. Волконский, В.М. Глушков, Б.А. Головкин, В.А. Евстигнеев, А.П. Ершов, В.П. Иванников, В.Э. Иткин, В.Н. Касьянов, В.Е. Котов, C.JI. Кривой, В.П. Кутепов, A.A. Ляпунов, С.С. Лавров, A.A. Летичевский, Э.З. Любимский, В.В. Мартынюк, A.C. Нариньяни, В.А. Непомнящий, И.В. Поттосин, Р.И. Подловченко, В.К. Сабельфельд, В.А. Серебряков, A.A. Терехов, Э.А. Трахтенгерц, Г.С. Цейтин, Ю.И.Янов, Ф.Э. Аллен, Д.Ф. Бэкон, М. Вольф, Дж. Кок, Г. Килделл, П. Кузо, М. Лэм, Д. Падуа, К-В. Ценг, Дж. Т. Шварц и многие другие.

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

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

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

Большой вклад в разработку и исследование онтологического подхода внесли российские и зарубежные ученые: В.Н. Вагин, Т.А. Гаврилова, A.C. Клещев, Г.С. Поспелов, Д.А. Поспелов, В.Ф. Хорошевский, T.R. Gruber, N. Guarino, J.F. Sowa и др. Онтологический подход успешно использовался в объектно-ориентированном проектировании и программировании, для проектирования интерфейса пользователя, ре-инжиниринга бизнес-процессов, в концептуальном проектировании. Онтологии обеспечили проектирование и разработку более интеллектуальных и интегрированных информационных систем.

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

Достижение цели работы предполагает решение следующих задач.

1. Разработка концепции преобразователя программ с переменным набором трансформаций на основе онтологического подхода.

2. Разработка онтологии единого представления программ и онтологии и его расширения.

3. Разработка онтологии методов потокового анализа программ и базы знаний о методах потокового анализа программ.

4. Разработка онтологии знаний о трансформациях программ и базы знаний о трансформациях программ.

5. Разработка методов интерпретации знаний о преобразованиях программ.

6. Разработка и реализация специализированного банка знаний о преобразованиях программ.

7. Разработка технологии использования методов и средств преобразования программ с переменным набором трансформаций и ее экспериментальное исследование.

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

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

Впервые разработана концепция системы для управления преобразованиями программ с переменным набором трансформаций.

Впервые разработаны онтологии модели структурных программ и онтологии расширенной модели структурных программ.

Впервые разработаны онтологии методов потокового анализа программ и онтологии знаний о трансформациях программ, а также база знаний о методах потокового анализа программ и база знаний о трансформациях программ.

Впервые поставлена задача интерпретации декларативного представления базы знаний о трансформациях программ и разработан метод ее решения.

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

Предложена технология использования методов и средств управления преобразованиями программ с переменным набором трансформаций.

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

Практическая ценность работы.

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

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

Разработанные методы интерпретации базы знаний о методах потокового анализа программ и базы знаний о трансформациях программ позволяют проводить исследования с преобразованиями программ с переменным набором трансформаций.

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

Программное средство для исследования преобразований программ с переменным набором трансформаций использовалось:

- при разработке почтового клиента для сотовых телефонов, основной целью которого является доступ с мобильного телефона к почтовым серверам по протоколам SMTP, РОРЗ, IMAP4;

- при разработке программного комплекса автоматизации работы туристических операторов на базе технологий Contour WEB;

- при разработке программного комплекса управления и учета услуг, предоставляемых посетителям интернет - ресурсов компании;

- при разработке программного комплекса для системы контроля сотрудников FrontLine.

Полученные в диссертации результаты внедрены (использованы): в научный процесс Института автоматики и процессов управления ДВО РАН, г. Владивосток; в учебный процесс Дальневосточного государственного университета, г. Владивосток.

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

Результаты диссертационной работы использовались в учебном процессе Дальневосточного государственного университета при чтении курсов лекций «Теория вычислительных процессов и структур II. Теория и методы трансляции», «Оптимизация программ», «Параллельное программирование», при выполнении курсовых работ (всего 30) и дипломных работ (всего 15) специальности 351500 - математическое обеспечение и администрирование информационных систем, а также при выполнении кандидатских диссертаций по специальности 051311-математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей.

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

Реализация работы. Результаты диссертационной работы нашли применение при выполнении научно-исследовательских работ:

- проект РФФИ 06-07-89071-а "Исследование возможностей коллективного управления в семантическом вебе информационными ресурсами различных уровней общности" 2006-2008 гг.

- программа №14 Президиума РАН «Фундаментальные проблемы информатики и информационных технологий», проект 06-1-П14-052 «Параллельные вычисления в создании инструментальных и проблемно -ориентированных средств для решения вычислительно-сложных задач моделирования динамики океана и атмосферы с использованием спутниковой информации, оптимизации в условиях неопределенности и построения интеллектуальных систем», раздел 2 «Разработка средств поддержки построения интеллектуальных систем и корректного программного обеспечения для многопроцессорных вычислительных комплексов» 2006-2008 гг.

- программа №15 фундаментальных исследований ОЭММПУ РАН «Проблемы анализа и синтеза интегрированных систем управления для сложных объектов, функционирующих в условиях неопределённости», проект 06-1-П15-055"Синтез интеллектуальных систем управления базами знаний и базами данных при управлении сложными объектами в условиях неопределённости" 2006-2008 гг.

- инициативный научный проект ДВО РАН 06-III-A-01-007 «Интернет-система управления информацией о преобразованиях программ» 2006-2008 гг.

Апробация работы. Научные положения и результаты диссертационной работы докладывались и получили одобрение на Международной научно-методической конференции «Новые информационные технологии в университетском образовании» (г. Новосибирск, 1997 г.), на П-ой и Ш-ей Международной научно-технической конференции «Интерактивные системы: проблемы человеко - компьютерного взаимодействия» (г. Ульяновск, 1997 и 1999 г.), на третьем сибирском конгрессе по прикладной и индустриальной математике посвященный памяти C.JI. Соболева (г. Новосибирск, 1998г.), на Международной конференции по математической логике, посвященной 90-летию со дня рождения академика А.И. Мальцева (г. Новосибирск, 1999 г.), на четвертом сибирском конгрессе по прикладной и индустриальной математике, посвященном памяти М.А. Лаврентьева (г. Новосибирск, 2000 г.), на Международной конференции «Искусственный интеллект 2000» (Кацивели, Крым, 2000, 2006, 2007 г.), на Дальневосточной математической школе-семинаре им. Акад. Е.В. Золотова (г. Владивосток, в 2001, 2002, 2006 и 2007 г., г. Хабаровск в 2005г.), на Международной конференции по искусственному интеллекту КИИ (г. Коломна, 2002 г., г. Обнинск, 2006 г.), на Международной конференции KDS-2003, KDS-2005, KDS-2007 и KDS-2008 (г. Варна, Болгария), на Международной конференции им. В.А. Трапезникова РАН «Параллельные вычисления и задачи управления»

РАСО'2004 и РАСО'2006 (г. Москва, 2004 г., 2006 г.), на Международной конференции «Системный анализ и информационные технологии» САИТ-2005 и САИТ-2007 (г. Переславль-Залесский, 2005 г., г. Обнинск, 2007 г.), на Всероссийской конференции «Знания-онтологии-теории» с международным участием (г. Новосибирск, 2007г.), на научных сессиях МИФИ (г. Москва, 2001, 2002, 2004-2008г.г.), Интеллектуальные и многопроцессорные системы (г. Таганрог, 2003-2007 г.г.), на второй Международной конференции по когнитивной науке (г. Санкт-Петербург, 2006 г.), на IX Международной конференции «Интеллектуальные системы и компьютерные науки» (г. Москва, 2006 г.); на семинарах Отдела экспертных систем Института автоматики и процессов управления ДВО РАН и Института математики и компьютерных наук ДВГУ (1991-2007г., г. Владивосток), в лаборатории Системного программирования Института Систем Информатики СО РАН им. А.П. Ершова в 1998 г. (г. Новосибирск), на семинаре в НИВЦ МГУ в лаборатории параллельных Информационных Технологий в 2003 г., 2006 г. (г. Москва), на семинаре ВЦ РАН в 2003 г., 2006 г. (г. Москва).

Личный вклад автора. Автором осуществлена постановка задачи, получение всех экспериментальных исследований и самостоятельно получены все теоретические результаты. Автор принимал личное участие в разработке программных систем и ей принадлежит интерпретация всех основных экспериментальных и теоретических результатов, представленных в диссертации. В работах [1-4] [75] [79] [95] [101] [195] [144] выделены основные компоненты онтологии предметной области. В работах [82-83] [88] определены язык модели структурных программ и расширение языка модели структурных программ терминами потокового анализа. В работах [5] [70-72] [76] [98-100][104] [193-194] [196-197] выполнены постановки задач, разработаны основные теоретические положения. В работах [73] [80] [84-87] [90-91] [94] [97] [198] описаны архитектура и основные задачи преобразователя программ. В работах [93] [96] разработана архитектура преобразователя программ, управляемого знаниями.

Публикация результатов работы.

Результаты диссертационной работы представлены в монографии, в 47 научных публикациях в отечественных и международных изданиях, в том числе 31 статья, из них 7 статей в международных изданиях, 15 статей в российских реферируемых журналах, в свидетельстве об официальной регистрации программ для ЭВМ, в свидетельстве об отраслевой регистрации разработки.

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

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

4. Разработана онтология знаний о трансформациях программ (абстрактный синтаксис языка описания трансформаций программ - ЯОТ) и база знаний о трансформациях программ. Описание трансформации программ включает формулу трансформации и формулу контекстного условия, характеристическую функцию и стратегию преобразования. Контекстное условие в базе знаний представляет формулу (предикат), которая при подстановке в нее участка экономии станет истинным. Формула трансформации в модели онтологии представляет предикат, который при подстановке в него участка экономии и преобразованного участка экономии должен стать истинным.

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

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

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

259

ГЛОССАРИЙ

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

Перечень обозначений и сокращений.

СБкЗ 1Ш - специализированный банк знаний о преобразованиях программ ИН - информационное наполнение ПН - программное наполнение

МСП Генератор - генератор моделей структурных программ

ДАС - дерево абстрактного синтаксиса

ИРУО - информация различных уровней общности

МСП - модель структурных программ

ЯМСП - язык моделей структурных программ

МБкЗ - многоцелевой банк знаний

СПТ - система построения трансляторов

МСТП - многоцелевая система трансформаций программ

СТП - система трансформаций программ

ГА - генетический алгоритм

ЯВУ - язык программирования высокого уровня

ПО — программное обеспечение

ЛОТ - язык описания трансформаций

СУ СБкЗПП - система упроавления СБкЗПП

ИАС - информационно-административная система МБкЗ

Определения терминов.

Преобразованием программ называется функция Т: Р—» Р, где Р — множество программ.

Трансформация - элементарное преобразование, которое может менять обрабатываемую программу.

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

Преобразование - суперпозиция элементарных преобразований (трансформаций).

Трансформация состоит из формулы трансформации и формулы контекстного условия (условия применимости этой трансформации).

261

1. Артемьева И.Л., Князева М.А., Купневич O.A. Модель онтологии предметной области "Оптимизация последовательных программ". 4.1. Термины для описания объекта оптимизации // НТИ. Сер. 2. 2002. -№ 12. - С. 23-28.

2. Артемьева И.Л., Князева М.А., Купневич O.A. Моделирование процесса оптимизации последовательных программ с использованием модели онтологий // Искусственный интеллект. Т. 3.- 2002.- С. 467473.

3. Артемьева И.Л., Князева М.А., Купневич O.A. Модель онтологии предметной области "Оптимизация последовательных программ". 4.2. Термины для описания процесса оптимизации // НТИ. Сер. 2. 2003. -№ 1. - С. 22-29.

4. Артемьева И.Л., Князева М.А., Купневич O.A. Модель онтологии предметной области "Оптимизация последовательных программ". Ч.З. Примеры описания некоторых оптимизирующих преобразований // НТИ. Сер. 2. 2003. - № 2 .- С. 27-34.

5. Аллен Р., Кеннеди К. Автоматическая трансляция Фортран-программ векторную форму // Векторизация программ: теория, методы, реализация : сб. науч. тр. М.: Мир, 1991. - С. 77-140.

6. Архангельский Б. В. Системы оптимизации программ / Б. В. Архангельский, А. И. Никитин. Киев: Техника, 1983. - 167 с.

7. АЛЬФА система автоматизации программирования / Наука: Новосибирск, 1967.

8. Ахо А. Теория синтаксического анализа, перевода и компиляции / А . Ахо, Д. Ульман Т 2. - Москва: Мир, 1978.-486 с.

9. Ахо Альфред. Компиляторы: принципы, технологии и инструменты / Альфред Ахо, Рави Сети, Джеффри Ульман. Компиляторы: принципы, технологии и инструменты. Пер. с англ. - М.: Издательский дом «Вильяме», 2001. - 768 с.

10. Баяковский Ю.М., Штаркман Вик. С. Об одном методе оценки эффективности оптимизирующих преобразований // Оптимизация и преобразование программ : сб. науч. тр. Новосибирск, 1983.

11. Болтаев Т.Б. Анализ информационных влияний в модула-программах // Конструирование и оптимизация программ : сб. науч. тр. -Новосибирск : ИСИ СО РАН, 1993.- С 39-51.

12. Н.Букатов A.A., Коваль В.В. Методы реализации трансформационной машины в многоцелевой системе трансформации программ // Информационные технологии. 2004. - № 3. - С. 24-30.

13. Вагин В.Н. Дедукция и обобщение в системах принятия решений / В.Н. Вагин.- М.: Наука. Гл. ред. Физ.-мат. Лит, 1988.- 384 с.

14. Воеводин В.В. Математические модели и методы в параллельных процессах//В.В. Воеводин. М.: наука, Гл. ред. физ.- мат. лит., 1986.

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

16. Волконский В.Ю., Окунев С.К. Предикатное представление как основа оптимизации программы для архитектур с явно выраженной параллельностью программ // Информационные технологии. 2003.-№ 4.- С. 36-45.

17. Волков Д. А. Язык описания методов потокового анализа // Информатика и системы управления.- № 1(13).- 2007.- С.118-129.

18. Гаврилова Т.А. Базы знаний интеллектуальных систем / Т.А. Гаврилова, В.Ф. Хорошевский. СПб.Питер, 2000.

19. Гаврилова Т.Л. Использование моделирующей ЭС оптимизации программ для подготовки разработчиков программного обеспечения ЭВМ / Т.Л. Гаврилова, М.А. Князева Владивосток: ИАПУ ДВО РАН, 1992.-21 с.

20. Гаврилова Т.Л. Лабораторный практикум по спецдисциплине «Методы трансляции и оптимизации программ» : методические указания 4.1 / Т.Л. Гаврилова, М.А. Князева ДВГУ, 1993. - 28 с.

21. Гаврилова Т.Л. Лабораторный практикум по спецдисциплине «Методы трансляции и оптимизации программ» : методические указания 4.2 / Т.Л. Гаврилова, М.А. Князева. ДВГУ, 1993. - 19 с.

22. Глушков В.М., Капитонова Ю.В., Летичевский A.A. Теория структур данных и синхронные параллельные вычисления // Кибернетика.-1976.- № 6.

23. Головкин Б.А. Построение вероятностной модели и анализ параллельных вычислительных процессов // Изв. АН СССР.-Техническая кибернетика. 1973. - № 3.

24. Головкин Б.А. Статистические методы формализации и диспетчирования параллельных вычислительных процессов // Автоматика и телемеханика.- 1974.- № 2.

25. Головкин Б.А. Параллельная обработка информации, программирование, вычислительные методы, вычислительные системы // Изв. АН СССР. Техническая кибернетика.- 1979. № 2.

26. Городняя Л.В., Касьянов В.Н. Проблемы и перспективы исследования преобразований программ на современных технических средствах // Проблемы конструирования эффективных и надежных программ : сб. науч. тр. Новосибирск, 1995. - С. 7-17.

27. Городняя JI.В. Информационно инструментальная система анализа и преобразования программ // Оптимизирующая трансляция и конструирование программ : сб.науч. тр. - Новосибирск, 1997. - С. 3442.

28. О.Грабарь А.В. Алгоритм потокового анализа с учетом точек доопределения переменных // Конструирование и оптимизация программ. Новосибирск: ИСИ СО РАН, 1993. - С 52-59.

29. Грис Д. Конструирование компиляторов для цифровых вычислительных машин / Д. Грис. М.: Мир, 1975. - 544 с.

30. Деннис Дж. Б. Схемы потока данных. Теория программирования. Ч. 2. // Дж. Б. Денис, Дж. Б. Фоссин, Дж. П. Линдерман Тр. симпоз. Новосибирск. - ВЦ СО АН СССР. - 1972.

31. Дроздов А.Ю., Степаненков A.M. Управляемые пакеты оптимизаций // Информационные технологии и вычислительные системы. 2004. - № 3.- С. 93-101.

32. Евстигнеев В.А. Применение теории графов в программировании / Евстигнеев В.А., Касьянов В.Н. М.: Наука, 1985.

33. Евстигнеев В.А. О некоторых формах промежуточного представления программ // Конструирование и оптимизация программ: сб. науч. тр. -Новосибирск : ИСИ СО РАН, 1993. С. 60-68.

34. Евстигнеев В.А. Теория графов: алгоритмы обработки деревьев / В.А. Евстигнеев, В.Н. Касьянов. Новосибирск: Наука, 1994.

35. Евстигнеев В.А. Касьянов В.Н. Инструментальная система для изучения преобразований программ // Интеллектуализация и качество программного обеспечения: сб. науч. тр. Новосибирск: ИСИ СО РАН, 1994. -С. 90-99.

36. Евстигнеев В.А. Основы параллельной обработки. Анализ программных зависимостей / В.А. Евстигнеев.- Новосибирск: НГУ, 1996.

37. Евстигнеев В.А., Касьянов В.Н. Оптимизирующие преобразования в распараллеливающих компиляторах // Программирование,- 1996.- № 6.- С. 12-26.

38. Евстигнеев В.А., Мирзуитова И.Л. Анализ циклов: выбор кандидатов на распараллеливание / Препринт № 58. Сибирское отделение Институт систем информатики им. А.П. Ершова. - Новосибирск, 1999.

39. Ершов А.П., Ляпунов A.A. О формализации понятия программы // Кибернетика. 1967.- №5.

40. Система БЕТА- сравнение постановки задачи с пробной реализацией // Тр. Всесоюз. Симпоз. По методам реализации новых алгоритмических языков. 4.1. Новосибирск, 1975. - С. 73-81.

41. Ершов А.П. Введение в теоретическое программирование (беседы о методе) / А.П. Ершов.- М.: Наука, 1977.

42. Ершов А.П., В.В. Грушецкий. Метод описания алгоритмических языков, ориентированный на реализацию. / Препринт. Новосибирск: ВЦ Сибирское отделение АН СССР, 1977.

43. Ершов А.П. Трансформационная машина: тема и вариации // Проблемы теоретического и системного программирования. Новосибирск: НГУ, 1982. - С. 5-24.

44. Ершов А.П., Касьянов В.Н., Покровский С.Б. и др. Методика разработки многоязыковых трансляторов на примере системы БЕТА // Математическая теория и практика систем программного обеспечения. Новосибирск: ВЦ СО АН СССР, 1982. - С.64-80.

45. Ершов А.П. Современное состояние теории схем программ / А.П. Ершов. Избранные труды. - Новосибирск: ВО "Наука". Сибирская издательская фирма, 1994.- 416 с.

46. Касперски К. Техника оптимизации программ. Эффективное использование памяти / К. Касперски. СПб.: БХВ-Петербург, 2003.464 с.

47. Касьянов В.Н. Методы построения трансляторов / В.Н. Касьянов, И.В. Поттосин.- Новосибирск: Наука, 1986.- 345 с.

48. Касьянов В.Н. Оптимизирующие преобразования программ / В.Н. Касьянов. М.: Наука. Гл. ред. Физ. - мат. лит., 1988.- 336 с.

49. Касьянов В.Н. 8ЫСШХЗ:Срезы программ и их использование / В.Н. Касьянов, И.Л. Мирзуитова. Новосибирск: Институт систем информатики, 2002. - 116 с.

50. Касьянов В.Н. Графы в программировании: обработка, визуализации и применение / В.Н. Касьянов, В.А. Евстигнеев,- СПб.: БХВ -Петербург, 2003. 1104 с.

51. Клещев A.C., Артемьева И.Л. Необогащенные системы логических соотношений. 4.1. // НТИ. Сер.2. 2000. - № 7. - С. 18-28.

52. Клещев A.C., Артемьева И.Л. Математические модели онтологий предметных областей. 4.2. Компоненты модели // НТИ. Сер.2. -2001. -№2.- С. 19-29.

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

54. Клещев A.C., Князева М.А. Управление информацией о преобразованиях программ. II. Внутреннее устройство специализированного банка знаний о преобразованиях программ // Изв. РАН. ТиСУ. 2005.- № 6. - С. 101-110.

55. Клещев A.C., Князева М.А. Интернет-система управления информацией о преобразованиях программ // Информационные технологии. 2007.- № 1.-С. 42-46.

56. Князева M.А., Матецкий C.B. Модель онтологии предметной области «Оптимизация коммуникаций для машин с распределенной памятью» //Искусственный интеллект.- Т. 3.- 2003.- С. 102-108.

57. Князева М.А., Клещев A.C. Концепция банка знаний в области оптимизации программ для поддержки научных исследований, образования и профессиональной деятельности // Владивосток: ИАПУ ДВО РАН, 2003.-28 с.

58. Князева М.А. Банк знаний о преобразованиях компьютерных программ //Искусственный интеллект.- Т. 3.- 2004.- С. 179-186.

59. Князева М.А. Учебно-методический комплекс по дисциплине «Оптимизация программ» / М.А. Князева. — Владивосток: Изд-во ДВГУ, 2004.

60. Князева М.А., Максимов C.B. Модель онтологии реструктурирующих оптимизирующих преобразований // II Международная конференция «Параллельные вычисления и задачи управления» Электронный ресурс. Труды конференции.-2004- (CD ROM).

61. Князева М.А. Оптимизирующие компиляторы, управляемые базами знаний // Информационные технологии. 2005.- № 12.- С. 42-48.

62. Князева М.А., Купневич O.A. Модель онтологии предметной области «Оптимизация последовательных программ». Определение языка модели структурных программ //НТИ. Сер. 2.- 2005. -№ 2.-С. 17-21.

63. Князева М.А., Купневич O.A. Модель онтологии предметной области «Оптимизация последовательных программ». Определение расширения языка модели структурных программ терминами потокового анализа // НТИ. Сер. 2.- 2005.- № 4.-С. 14-22.

64. Князева М:А;, Зотов И.Ю. Подсистема потокового анализа для распараллеливаемых программ в банке знаний: о преобразованиях программ//Искусственный интеллект.- Т.4.- 2005.-С^ 192-199;

65. Князева М.А., Тимченко В.А. Структурные редакторы программ на языках программирования высокого уровня: и генератор моделей структурных программ в банке знаний- о преобразованиях программ // Искусственный интеллект.- Т.4.- 2005.- С. 200-208.

66. Князева М.А., Плохих С. А. Измерительная- подсистема для преобразователя программ // Научная Сессия МИФИ -2005: сб. научн.тр. в;14 томах, т.З. М.: МИФИ; 2005 -С. 130-131.

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

68. Князева М.А., Бердник А.Н. Интерпретация знаний о трансформации. программ в специализированном банке знаний о преобразованиях программ // Искусственный? интеллект/Украина, Донецк: Институт проблем искусственного интеллекта. -2006; Т. С.191-200

69. Князева М.А. Интеллектуальная система управления знаниями об оптимизации программ // X национальная конференция по искусственному интеллекту с международным участием: Труды конференции.- В З-т.Т.1. М: Физматлит, 2006. - С. 61-68.

70. Князева М.А., Зотов И.Ю. Поиск участков программ для распараллеливания в системе потокового анализа в специализированном банке знаний о преобразованиях программ // Научная сессия МИФИ-2006. Сб. научн. тр. в 16 томах.- Т. 3. М: МИФИ, 2006.-С. 136-137.

71. Князева М.А., Волков Д.А. Потоковый анализ программ, управляемый знаниями //Программные продукты и системы. -2007.-№1.-С.49-52.

72. Князева М.А., Жеравин M.B. Генерация низкоуровневого кода, управляемая знаниями // Информационные технологии. 2007. - № 10.-С. 7-12.

73. Князева М.А., Маевский М.С. Проверка контекстных условий и поиск участков экономии в системе преобразований программ // Информационные технологии . 2007.-№ 12. - С. 70-73.

74. Князева М.А., Пронина Е.А. Методы потокового анализа распараллеливаемых программ в специализированном банке знаний о преобразованиях программ // Искусственный интеллект, Донецк: Институт проблем искусственного интеллекта. — 2007. Т.З. - С. 79-85.

75. Князева М.А., Тимченко В.А. Подсистема генерации единого внутреннего представления в системе преобразований программ. // Программные продукты и системы. -2008. -№ 1.- С.58-62.

76. Князева М.А. Преобразования программ с переменным набором трансформаций. Монография. Владивосток: Изд-во Дальневост. ун-та,2008.-210 с.

77. Князева М.А., Плохих С.А. Концепция системы управления специализированного банка знаний о преобразованиях программ // Информационные технологии.- 2009. № 5.-С. 36-40.

78. Кривой C.JI. Обобщение алгоритмов поиска инвариантных соотношений в программах над алгеброй термов // Кибернетика и системный анализ. 1996 .-№ 1.- С.24-36.

79. Купневич O.A. Князева М.А. Экспертная система, моделирующая процесс оптимизации программ. Модель оптимизации программ / Препринт. Владивосток : ИАПУ ДВО РАН, 1997. 40 с.

80. Котляров Д.В., Кутепов В.П., Осипов М.А. Граф-схемное потоковое параллельное программирование и его реализация на кластерных системах. // Изв. РАН. ТиСУ. 2005.- № 1.- С. 75-96.

81. Котов В.Е., Нариньяни A.C. Асинхронные вычислительные процессы над памятью // Кибернетика 1966.- № 3.

82. Котов В.Е. Теория параллельного программирования. Прикладные аспекты// Кибернетика.- 1974.- №1,2.

83. Котов В.Е. Введение в теорию схем программ / В.Е. Котов. -Новосибирск: Наука, 1978.

84. Лавров С.С. Об экономии памяти в замкнутых операторных схемах// ЖВМиМФ.- I.- 1961.- №4.

85. Любимский Э.З. О формальной постановке задачи реализации циклов// Программирование.- 1979.- №5.

86. Любимский Э.З., Миташюнас А.Ю. О задаче реализации составных циклов// Программирование 1981 - №1.

87. Ляпунов A.A. О логических схемах программ // Сб. «Проблемы кибернетики».- вып. I.- М.: Физматгиз, 1958.

88. Льюис Ф. Теоретические основы проектирования компиляторов / Ф. Льюис, Д. Розенкранц, Р. Стирнз. Москва: Мир, 1979.- 645 с.

89. Малинина Ю.В. Информационная система ТРАНСФОРМ по преобразованиям программ. // Проблемы конструирования эффективных и надежных программ. Новосибирск, 1995. - С. 128136.

90. Малинина Ю.В. ИС ТРАНСФОРМ: описание инфологической схемы базы данных. // Оптимизирующая трансляция и конструирование программ. Новосибирск, 1997. - С. 60-79.

91. Меткалф М. Оптимизация в Фортране / М. Меткалф.- Пер. с англ. М.: Мир, 1985.- 264 с.

92. Нариньяни A.C. Теория параллельного программирования. Формальные модели // Кибернетика.- 1974.- № № 3, 5.

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

94. Орлов В. А., Клещев А. С. Компьютерные банки знаний. Требования к Многоцелевому банку знаний // Информационные технологии. 2006.-№ 4.-С. 21-28.

95. Орлов В. А., Клещев А. С. Компьютерные банки знаний. Универсальный подход к решению проблемы редактирования информации // Информационные технологии. 2006.-№ 5.- С. 25-31.

96. Орлов В. А., Клещев А. С. Компьютерные банки знаний. Модель процесса редактирования информационного наполнения // Информационные технологии. 2006.-№ 7.- С. 11-16.

97. Падуа Д., Вольф М. Оптимизация в компиляторах для суперкомпьютеров // Русский перевод в книге "Векторизация программ: теория, методы, реализация". М.: Мир, 1991.- С. 7-47.

98. Поттосин И.В. К обоснованию алгоритмов оптимизации программ //Программирование.- 1979.- №2.- С. 3-13.

99. Поттосин И.В. О контекстных условиях для корректности преобразования расчленения и объединения циклов // Языки и системы программирования: сб.научн. тр.- Новосибирск: ВЦ СО АН СССР, 1979.-С. 139-149.

100. Поттосин И.В., Югринова О.В. Обоснование преобразования чистки циклов // Программирование.- 1980.- №5.

101. Поттосин И.В. О математических моделях программ, ориентированных на оптимизацию программ // Mathematical methods in informatic. Varna, 1981.-P. 1-24.

102. Поттосин И.В. Анализ возможностей и путей развития оптимизации программ //Программирование.-1991.- № 6.-С.64-80.

103. Поттосин И.В. Система Сократ: окружение программирования для встроенных ЭВМ // Новосибирск, 1992. (Препр./ РАН. Сиб. отд-е. ИСИ; N11).

104. Пратт Т. Языки программирования: разработка и реализация / Т. Пратт. М.: Мир, 1979. - 575 с.

105. Сабельфельд В.К. Метод разметки для глобального анализа свойств // Препринт ВЦ СО АН СССР № 699.- 20 с.

106. Серебряков В.А. Основы конструирования компиляторов / В.А. Серебряков, М.П. Галочкин. М.: Эдиториал УРСС, 2001.- 224 с.

107. СОКРАТ: Окружение надежного и эффективного программирования /Л.А. Захаров, В.Н. Касьянов, Т.В. Кузьминов и др. // Актуальные проблемы информатики, прикладной математики и механики. Часть III: Информатика.- Новосибирск-Красноярск, 1996.- С. 51-64.

108. Андрей А.Терехов, Наталья Вояковская, Дмитрий Булычев, Антон Москаль. Разработка компиляторов на платформе NET. 2001.-Режим доступа: http://se.math.spbu.ru

109. Уваров Д.Л. Оптимальный алгоритм чистки регулярных гамаков //Программирование.- 1998.- №2.-С. 68-80.

110. Уваров Д.Л. Оптимальный алгоритм чистки регулярных схем // Программирование.- 2000.- №6.- С. 20-44.

111. Фахрутдинов К.И. Языки программирования / К.И. Фахрутдинов.- Владивосток: Изд-во Дальневост. ун-та, 1991. 188 с.

112. Хантер Р. Проектирование и конструирование компиляторов /Р. Хантер .- пер. с англ.- М: Финансы и статистика, 1984.-232 с.

113. Хислей Ф.Н. Генерация высококачественного кода для программ, написанных на СИ. Режим доступа: http://rtfm.vn.Ua/prog/c/hicode.html

114. Шелехов В.И. Нахождение заместителей объектных переменных // Среда программирования: методы и инструменты.- Новосибирск, 1992.- С. 80-90.

115. Шелухина А. А. Оптимизирующие и реструктурирующие преобразования программ: к проблеме создания каталога // Интеллектуализация и качество программного обеспечения : сб. науч.тр.- Новосибирск: ИСИ СО РАН, 1994.- С. 129-138.

116. Штейнберг Б.Я. Математические методы распараллеливания рекуррентных циклов для суперкомпьютеров с параллельной памятью / Б.Я. Штейнберг.- Ростов н/Д: Изд-во Рост, ун-та, 2004.-192 с.

117. Artemjeva I.L., Knyazeva М. A., Kupnevich О. A. Processing of knowledge about optimization of classical optimizing transformations // International Journal Information Theories & Applications.- 2003.-V. 10.-№2. -P. 126-132.

118. Aho A. V. Compilers: Principles, Techniques, and Tools / A. V. Aho, R. Sethi, J.D. Ullman. Reading, Mass.: Addison- Wesley, 1986.

119. Allen F.E. Program optimization // Annual Review in Automatic Programming .-V. 5,- Pergamon Press, 1969. PP.239-307.

120. Allen F.E. Cock J. A catalogue of optimizing transformations // IBM Watson Research Center.- Yorktown Heights.- New York.

121. Allen J.R. Dependence analysis for subscribed variables and its application to program transformations // PhD thesis.- Rice Univ., 1983.

122. Alpern В., Wegman .N., Zadek F.K. Detecting equality of values in programs// Conf. Rec. Fifteenth ACM Symp. On Principles of Progr. Lang., Jan. 1988 .-New York.: ACM.- P. 1-11.

123. Babayan B.A. E2k Technology and Implementation.// Proceedings of the Euro-Par 2000. parallel Processing: 6th International.- V. 1900/2000. -January, 2000.-P. 18-21.

124. Bacon D.F., Graham S.L., Sharp O.J. Compiler transformations for high-performance computing // ACM Computing Surveys.- 1994.- V.26.- № 4.- PP.345-420.

125. Baer J.L. A survey of multiprocessing // Comp. Sci. Group.- Univ. Washington.- TR-72-05-01, 1972.

126. Baer J.L. Large scale systems // Ch.5. In " Computer Science", A.F. cardenor, L. Presser and M. A. Marin (Eds). N. Y., Wiley-Interscience, 1972.

127. Banerjee U. Speedup of ordinary programs // PhD thesis, Univ. of Illinois at Urbana-Champaign, (Oct.). -Tech. Rep., 1979, P. 79-989.

128. Banerjee. U. An introduction to a formal theory of dependence analysis // The J of Supercomputing.- 1988.- Vol. 2, № 2.- P. 133-149.

129. Bernstein P.A. Description problems in the modeling of asynchrous computer systems // Toronto, Univ. Of Toronto, Dep. Of Comput. Sci., Techn. Rep.-№48.- 1973.

130. Blum W., Doallo R., Eigenmann R. A.o. Parallel programming with Polaris // Computer.- 1992.-Vol. 29, N 12.- P. 78-82.

131. Bowie W.S. Applications of graph theory in computer systems // Intern. J. Comput. Inform. Sci.- 1976.- 5, No. 1.

132. Method of Programming // Selected Papers on the CIP project /Ed. by M. Broy and M. Wirsing.- Berlin a.o.: Springer- Verlag, 1991.- (Lect. Notes Comput. Sci.; Vol.544).

133. Burgess C.J., Saidi M. The automatic generation of test cases for optimizing Fortran compilers // Information and Software Technology. -1996.- V. 38. -P.lll-119.

134. Clifford N. Click. Combining Analyses, Combining Optimization // A thesis submitted in fulfillment of requirements for the degree Doctor of Philosophy.- Houston.- Texas.- February 1995.

135. Cocke J. Markstein P. Measurement of program improvement algorithms //In: Proc. IFIP Cong. 80.- 1980.- h. 221-228.

136. Coffman E.G. Denning PJ. Operating systems theory // Englewood Cliffs.- Prentic Hall.- 1973.

137. Cooper K., Kennedy K., Torszon L. The impact of interprocedual analysis and optimization in the R n environment // ACM Trans. On Prog. Lang, and syst. №8 (4).- 1986.- P. 491-523.

138. Cousot P., Cousot R. Abstract interpretation frameworks // Rapport de Recherche.- Ecole Polytechnique.- Laboratoire dTnformatique, 1992.

139. Choi, J.-D., Burke, M., and Carini, P. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects // 20th ACM Symposium on Principles of Programming Languages.- ACM Press.- 1993. New York.-P.232-245.

140. Dieffendorf K. The Russians Are Coming. Supercomputer Maker Elbrus Seeks to Join x86/IA-64 Melee // Microprocessor Report, V. 13, #2. February 15.- 1999.-P.1-7.

141. Ershov A.P. Alpha an automatic programming system of high efficietcy// J. ACM 131.- 1966.- P. 17-24.

142. Foo S. Y., Musgrave G.Comparison of graph models for parallel computation and their extension. // Intern. Symp. Comput. Hardware Descript. Lang. And Appl.- Proc.- N. Y., 1975.

143. Fenton N.E., Pfleeger S.L. Software metrics: A rigorous & practical approach // Second edition. International Tompson Computer Press, 1996.-P.638.

144. Ferrante J., Ottenstein K.J., Warren J.D. The program dependence graph and its use in optimization // ACM TOPLAS. 1987.- V. 9. -№ 3.- PP 319-349.

145. Gerhard Goos, William Waite. Compiler Construction.Springer / Jan, 1984.

146. Girkar M., Polychronopoulos C.D. The HTG: an intermediate representation for program based on control and data dependences //-Univ. Of Illinois at Urbana-Champaign. CSRD Rep.- 1046.- May 1991.

147. Hobbs L. C. Parallel processor systems, technologies, and applications / Hobbs L. C., D.J. Theis, J. Trimble,H. Titus, I. Highberg (Esd). N.Y. -Spartan Books, 1970.

148. Holt A. W., commoner F. Events and conditions // Record of the Project MAC Conf. On Concurrent Systems and Computation.-1970.-N.Y.ACM, 1970.

149. Hunter R. The essence of compilers. / Hunter R. Prentice Hall Europe, 1999.-P. 237.

150. Haghighat M.R. Symbolic analysis: a basis for parallelization, optimization and cheduling of programs // 1314.-ps.

151. M. Haghighat and C. Polychronopoulos. Symbolic analysis: A basis for parallelization, optimization, and scheduling of programs // In Proceedings of the Sixth Workshop on Languages and Compilers for Parallel Computing.- Portland.- OR.- August 1993.

152. Hect M. S. Flow Analysis of Computer Programs // Programming Languages Series. -North-Holland.- NewYork, 1977.-P. 232.

153. Irene L. Artemjeva, Margarita A. Knyazeva, Oleg A. Kupnevich Processing of knowledge about optimization of classical optimizingtransformations // International Journal Information Theories & Applications.- Vol. 10.-No 2.-2003.-P. 126-132.

154. Intel C-H- Compiler 7.0 and GNU Compiler 3.2 Performance on IA-32 and Itanium Architecture.-Режим доступа: http: // www.intel.com /software /products /compilers/techtopics/compilergnuperf.pdf

155. Intel С++ Compiler 8.0 for Windows, Intel Corporation.-Режим доступа: ftp: //download.intel.com/ software/products/compilers/docs/cwin/ ccug.chm

156. Karp R.M., Miller R. E. Parallel program schemata // J. Comput. Syst. Sei.- 1969.-3.-No 2.

157. Kam J.B., Ullman J.D. Monotone data flow analysis frameworks // Acta Informatica.-1977. 7:3. -P. 305-318.

158. Kam J.B., Ullman J.D. Global Data Flow Analysis and Iterative Algorithms// JACM.-1976.- №23.-P. 158-171.

159. Karsai Gabor, Agrawal Aditya, Shi Feng, Sprinkle Jonathan. On The Use of Graph Transformation in the Formal Specifications of Model Interpreters.- Ржим доступа: http://www.isis.vanderbilt.edu/ publications/ archive/Karsai GOO 2003 On the Use.pdf

160. Kennedy K., Uen A. Compilers: a dependence-based approach. 2002.

161. A unified approachto global program optimization // ACM Symposium on Principles of Programming Languages.- 1973.-P. 194-206.

162. Kleschev A.S. Artemjeva I.L. Mathematical models of domain ontologies //Technical report 18-2000.-Vladivostok.- IACP ofFEBRAS.-431. P

163. Kleschev A.S., Artemjeva I.L. Unenriched logical relationship systems // Technical report 1-2000. Vladivostok.- IACP of FEBRAS.- 431. P

164. Knyazeva M.A., Kupnevich O.A. Expert system for simulation of program optimization. Joint NCC&IIS Bull.,Comp. Science,12 (1999),24-28.

165. Knyazeva M.A., Kleschev A.S. A concept of the knowledge bank on computer program transformations // Proceedings of Xl-th International conference "Kowledge-dialog-solution"-Varna, 2005.- V. 1.- P.147-152.

166. Knyazeva M., Keshchev A. A Web-system for Computer Experiments in the Field of Program Transformations // International Journal Information Theories & Applications. Bulgaria, Sofia: FOI-COMMERCE. - 2006. -Vol. 13. -№ 4 — PP. 331-336

167. Knyazeva M.A., Timchenko V.A. Ontology-based model of representation of knowledge about language mappings // International Book Series "INFORMATION SCIENCE & COMPUTING", Number 5. Supplement to the International Journal "INFORMATION

168. TECHNOLOGIES & KNOWLEDGE" Bulgaria, Sofia: FOI ITHEA. -2008. - Vol. 2. - PP. 111-118-IS SN: 1313-0455 (printed), 1313-048X(online),1313-0501 (CD/DVD).

169. Kuck DJ.,Kuhn R.H., Leasure В., Wolfe M. The structure of advanced retargetable vectorizer. Tutorial on Supercomputers:Designs and Applications // K.Hwang, Ed. IEEE Press, New York, 1984.- P. 163-178.

170. Lattner Ch. LLVM: An Infrastructure For Multi-Stage Optimization, B.S., University of Portland, 2000.- Режим доступа: http://llvm.cs.uiuc.edu/ pubs/ 2002-12-LattnerMSThesis.pdf

171. Miller R.E. Some theoretical of parallel computation // Intern. Comput. Symp.- Venice, 1972.- Proc. ACM.- S. 1.

172. Miller R.E. A comparison of some theoretical models of parallel computation // IEEEE Trans. Comput., 1977.- C-26, No 2. Special Issue on Parallel Proccessors and Processing.

173. Muchnick S.S. Advanced compiler design&implementation.l997.

174. Padua D.A., Wolf M.J. Advanced compiler optimization for supercomputers // Communs. ACM.- 1986.-Vol.29.- № 12.- P. 1184-1201.

175. Rodriguez J.E. A graph model for parallel computation // Cambridge.- MIT Project MAC report.- MAC-TR-64.- 1967.

176. Ripken K. A formal method for describing machine code generation with local optimization // In "Le point sur la compilation".- INRIA.- 1978.

177. Scott R. Ladd. An Evolutionary Analysis of GNU С Optimizations.-Режим доступа: http://www.coyotegulch.com/acovea/

178. Slutz D.R. The flow graph model of parallel computation // Cambridge. MIT Project MAC report. MAC-TR-53.- 1968.

179. Slutz D.R. Flow graph schemata. Record of the Project MAC Conf. On Concurrent Systems and Parallel Computation, 1970. N.Y. ACM, 1970.

180. Schneck P. B. A Survey of Compiler Optimization Techniques.

181. Stallman R. Using and Porting the GNU Compiler Collection / R. Stallman.- Addison-Vesley Publishing.- New York.- 2000 556 p.

182. Taentzer Gabriele. Towards Common Exchange Formats for Graphs and Graphs Transformation Systems.-Режим доступа: http://www.elsevier.n1/gej-ng/31/29/23/73/28/58/44.4.004.pdf

183. Tseng C-W. An Optimizing Fortran D Compiler for MIMD Distributed- Memory Machines / C-W. Tseng.- Rice University.- Houston, Texas, 1993.

184. Wilhelm R. Computation and use of data flow information in optimizing compilers // Acta info. №12 (3) 1979.

185. Wilson R.P., FrenchR.S., Wilson C.S. a.o. SUIF: An infrastructure for research on parallelizing and optimizing compilers // SIGPLAN Not.-1994.-Vol. 29, N12.-P. 31-37.

186. Wulf W.A. Trends in the design and implementation of programming languages //Computer. #3 (1), 1980. P. 14-24.