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

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

· она должна позволять представлять основные конструкции императивных языков программирования, существенные для описания последовательных ОП.

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

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

Определение терминологии для описания объекта оптимизации

Онтология моделей программ описывается при помощи формализма, предложенного в [21, 22]. Модель онтологии предметной области "Оптимизация последовательных программ" состоит из двух модулей. Первый модуль содержит определение терминов для описания объекта оптимизации, а второй - терминов для описания процесса оптимизации. Первый модуль представляет собой необогащенную систему логических соотношений с параметрами, записанную с использованием предложений многосортного языка прикладной логики: при помощи предложений - описаний значений имен в п.1.1 работы [3] определяются вспомогательные термины, при помощи предложений - описаний сортов имен в п. 1.2. и 1.3. работы [3] определяются параметры и неизвестные, при помощи предложений - ограничений на интерпретацию имен в п.1.4 работы [3] определяются онтологические соглашения, определяющие ограничения целостности модели языка, ограничения целостности модели программы, а также взаимосвязь между моделью программы и моделью языка. Для большей ясности изложения вначале описываются неизвестные и параметры неформально.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.2.2 Описание терминов потокового анализа МСП

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

Введём новое отношение: - итерационная зависимость.

Сопоставляет двум операторам и циклу ложь, если между двумя операторами отсутствует итерационная зависимость, и истину, если зависимость присутствует.

Введём новый атрибут ParDo

Имена атрибутов {Id, Def, Par, Left, LeftExpr, Right, RightExpr, Image, IsArray, IsPointer, IsRec, IsFunc, IsEffects, IsLValue, IsVar, Level, Op, Priority, Type, ByValue, FormRefParam, FormValParam, RefParam, ChangeRefParam, ValParam, A, R, RR, RP, OwnerFunc, Length, IsLine, Name, Result, TypeSet, LowBound, HighBound, ParentLevel, ParDo}

- ParDo - сопоставляет фрагменту типа DFor истину если он имеет тип ParDo, и ложь в обратном случае.

Область определения атрибута ( (v: Имена атрибутов)

/ (v = ParDo => ((v₁: Адреса фрагментов Идентификаторы) v₁ Адреса фрагментов & FragClass(v₁) = {DFor})

Областью определения атрибута ParDo является множество фрагментов типа DFor.

Область значения атрибута = ( (v: Имена атрибутов)

/ (v = ParDo => ((v1:Значения атрибутов) v1 L))

Область значения атрибута ParDo есть множество логических значений.

2.3 Постановка задач и методы их решения

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

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

Решение задачи интерпретации: Описать алгоритмы действий синтаксиса методов потокового анализа.

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

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

Также необходимо описать и добавить в базу методов потокового анализа метод «ParDo».

2.3.1 Алгоритм добавления атрибутов ParDo

Смыслом метода потокового анализа «ParDo» является добавление атрибутов ParDo.

Алгоритм записан на естественном языке и заключается в следующем:

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

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

1.1 Если пересечение аргументного (а) и результатного (р) множеств цикла (внут) - пустое множество, тогда (внеш) присваивается атрибут ParDo

1.2 Иначе

1.2.1 Для всех операторов присваивания Dass (присв) тела цикла (внут), начиная с первого

1.2.1.1 Если пересечение множеств (а), (р) и левой части оператора присваивания (внут) не совпадает с пересечением (а), (р) и правой части оператора присваивания (внут), то переход к 2.Иначе

1.2.1.1.1 Если элементы пересечения - индексные переменные, иесли в индексе (л) присутствуют переменные из условия цикла1, ииндекс (л) <> (п), то переход к 2.

1.2.2 (внеш) присваивается атрибут ParDo.

2. Конец алгоритма.

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

Пример работы алгоритма потокового анализа МСП

Поиск участка экономии «Гнездо циклов»

Нахождение участка экономии заключается в обходе МСП в ширину, начиная с корня. Производится поиск участков вида (рисунок 2.1):

Рисунок 2.1 участок экономии



Для гнезд циклов вложенности n, где n - количество Dfor.

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

Пусть найден участок экономии

DO i = 1, n

DO j = 1, n

DO k = 1, n

a_ij = a_ij + b_ik c_kj

END DO

End DO

End DO

МСП которого выглядит так (рисунок 2.2):

Рисунок 2.2 МСП участка экономии

Из этого фрагмента мы выделяем счетчики циклов:

i: (1, n)

j: (1, n)

k: (1,n)

проверяется, что счетчик цикла DFor (внут), не пересекается с объединением аргументных множеств начальной границы цикла, конечной границы цикла и шага DFor (внеш)

j не зависит от цикла i

проверяется, что аргументное и результатное множества не пересекаются

{a} {a, b, c} ?

проверяется, что элементы пересечения - индексные переменные, ив индексе (л) присутствуют переменные из условия цикла1, ииндекс (л) <> (п),

a - индексная переменная

в индексе (л) присутствуют переменные из условия циклов

i=i, j=j (рисунок 2.3)

Рисунок 2.3

Циклу i присваивается атрибут ParDo

Аналогично оценивается цикл j. В результате ему тоже присваивается атрибут ParDo.

У цикла K нет вложенных циклов, поэтому он не рассматривается.

Расширение МСП терминами потокового анализа

Рисунок 2.4 МСП, расширенная терминами потокового анализа

2.4 Представление методов потокового анализа программ

Для представления методов потокового анализа программ в базе знаний СБкЗ_ПП был разработан язык методов потокового анализа программ.



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

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

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

Метод потокового анализа = (метод потокового анализа: Последовательность конструкций)

проц Метод_потокового_анализа(вершина: Вершина)

если вершина=«Фрагмент по дуге» то вызов Фрагмент_по_дуге()

если вершина=«Атрибут фрагмента» то вызов Атрибут_фрагмента()

если вершина=«Получить класс» то вызов Получить_класс()

если вершина=«Получить переменную выражения» то вызов Получить_переменную_выражения()

если вершина=«Первый фрагмент по дуге из последовательности» то вызов Первый_фрагмент_по_дуге_из_последовательности()

если вершина=«Следующий фрагмент по дуге из последовательности» то вызов Следующий фрагмент по дуге из последовательности()

если вершина=«Пересечение множеств» то вызов Пересечение множеств()

если вершина=«Объединение множеств» то вызов Объединение множеств()

если вершина=«Равенство множеств» то вызов Равенство_множеств()

если вершина=«Логическая формула» то вызов Логическая_формула()

если вершина=«Составная логическая формула» то вызов Составная_логическая_формула()

если вершина=«Терм логической формулы» то вызов Терм_логической_формулы()

если вершина=«Обход дерева программы» то вызов Обход_дерева_программ()

если вершина=«Обход дерева выражения» то вызов Обход_дерева_выражения()

если вершина=«Выбор» то вызов Выбор()

если вершина=«Цикл» то вызов Цикл()

если вершина=«Создание фрагмента» то вызов Создание_фрагмента()

если вершина=«Создание атрибута» то вызов Создание_атрибута()

если вершина=«Изменение атрибута» то вызов Изменение_атрибута()

если вершина=«Создание дуги» то вызов Создание_дуги()

если вершина=«Создание отношения» то вызов Создание_отношения()

если вершина=«Создание переменной» то вызов Создание_переменной()

если вершина=«Присваивание» то вызов Присваивание()

если вершина=«Выражение» то вызов Выражение()

если вершина=«Выражение в скобках» то вызов Выражение_в_скобках()

иначе вершина= Метод_потокового_анализа(вершина.дочерн[0])

Фрагмент по дуге = (аргумент-фрагмент, имя, результат-фрагмент)

Описание: Фрагмент по дуге представляет собой функцию, которая сопоставляет фрагменту Аргумент-фрагмент, фрагмент Результат-фрагмент, который соединен с первым дугой с именем Имя дуги.

Семантика: Присвоить переменной Результат-фрагмент фрагмент, к которому от Аргумент-фрагмента ведет дуга Имя дуги.

проц Фрагм_по_дуге (А_ф, имя_дуги, р_ф)

р_ф = а_ф.перейти_по_дуге(имя_дуги)

потоковый анализ распараллеливаемый программа



Атрибут фрагмента = (Аргумент-фрагмент, Имя атрибута,

Результат-атрибут)

Описание: Атрибут фрагмента есть функция, которая для фрагмента Аргумент-фрагмент возвращает атрибут Результат-атрибут с именем Имя атрибута.

Семантика: Присвоить переменной Результат-атрибут атрибут фрагмента Аргумент-фрагмент с именем Имя атрибута.

проц атрибут_фрагмента (А_ф, имя_атр, р_а)

р_а = а_ф.получить_атрибут(имя_атр)

Получить класс = (аргумент1 : переменная-фрагмент, результат :

класс фрагмента)

Описание: Получить класс есть функция, которая для заданного фрагмента Аргумент-фрагмент возвращает его класс.

Семантика: Присвоить Результату-классу фрагмента класс фрагмента Аргумент-фрагмент.

проц Получить_класс (арг: вершина, рез: класс)

рез = арг.класс

Получить переменную выражения = ( Аргумент-фрагмент,

Результат-переменная)

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

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

Первый фрагмент по дуге из последовательности? = (Аргумент-

фрагмент, Результат-фрагмент )

Описание: Функция Первый фрагмент по дуге из последовательности для фрагмента Аргумент-фрагмент возвращает фрагмент Результат-фрагмент к которому ведет первая дуга Оператор.

Семантика: Присвоить Результат-фрагменту фрагмент к которому от фрагмента Аргумент-фрагмент ведет первая дуга Оператор.

проц Первый_фрагмент_по_дуге_из_последовательности (арг: вершина, рез: вершина)

цикл i=1 по арг.количество_дочерн шаг 1

если арг.дочерн[i].тип == оператор то

рез= арг.дочерн[i]

выход_из_цикла

Следующий фрагмент по дуге из последовательности? =

(Аргумент-фрагмент, Аргумент-фрагмент2, Результат-фрагмент )

Описание: Функция Первый фрагмент по дуге из последовательности для фрагмента Аргумент-фрагмент возвращает фрагмент Результат-фрагмент к которому ведет дуга Оператор следующая за дугой, которая ведет к Аргумент-фрагменту2.

Семантика: Присвоить Результат-фрагменту фрагмент к которому от фрагмента Аргумент-фрагмент ведет дуга Оператор следующая за дугой, которая ведет к Аргумент-фрагменту2.

проц Следующий_фрагмент_по_дуге_из_последовательности (арг1:

вершина, арг2: вершина, рез: вершина)

i=1

пока арг1.дочерн[i] ? арг2 выполнять i=i+1

цикл j=i по арг.количество_дочерн шаг 1

если арг1.дочерн[i].тип == оператор то

рез= арг1.дочерн[i]

выход_из_цикла

Пересечение множеств = (Аргумент-множество, Аргумент-

множество2, Результат-множество)

Описание: Пересечение множеств есть функция, которая для заданных множеств Аргумент-множество и Аргумент-множество2 вычисляет Результат-множество, равное их пересечению.

Семантика: Пересечь множества Аргумент-множество и Аргумент-множество2 и присвоить полученное множество переменной Результат-множество.

проц Пересечение_множеств(арг1: множество, арг2: множество, рез:

множество)

объявить рез тип множество

цикл i=1 по арг1.количество шаг 1

цикл j=1 по арг2.количество шаг 1

если арг1[i] == арг2[j] то

объявить т тип двоичный

т=0

цикл k=1 по рез.количество шаг 1

если рез[k] == арг2[j] то т=1

если т ? 1 то рез.добавить(арг2[j])

выход_из_цикла

Объединение множеств = (Аргумент-множество, Аргумент-

множество2, Результат-множество)

Описание: Объединение множеств есть функция, которая для заданных множеств Аргумент-множество и Аргумент-множество2 вычисляет Результат-множество, равное их объединению.

Семантика: Объединить множества Аргумент-множество и Аргумент-множество2 и присвоить полученное множество переменной Результат-множество.

проц Объединение_множеств(арг1: множество, арг2: множество, рез: множество)

объявить рез тип множество

объявить т тип двоичный

т=0

цикл i=1 по арг1.количество шаг 1

рез.добавить(арг1[i])

цикл j=1 по арг2.количество шаг 1

цикл k=1 по рез.количество шаг 1

если рез[k] == арг2[j] то т=1

если т ? 1 то рез.добавить(арг2[j])

выход_из_цикла

Равенство множеств = (Аргумент-множество, Аргумент-

множество2, Результат равенства)



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

Семантика: Если множества Аргумент-множество и Аргумент-множество2 пусты, либо содержат одинаковые элементы присвоить Результату равенства значение истина, в противном случае присвоить Результату равенства значение ложь.

проц Равенство_множеств(арг1: множество, арг2: множество, рез:

двоичный)

если арг1.количество == арг2.количество то

цикл i=1 по арг1.количество шаг 1

если арг1[i] ? арг2[i] то

рез=ложь

выход_из_цикла

иначе

рез=ложь

Логическая формула = (Терм логической формулы)

Описание: Логическая формула есть функция, область значения которой Булево множество.

Семантика: Присвоить аргументу Булево множество истину или ложь в зависимости от результата вычисления логической формулы, которая задается Термом логической формулы

проц Логическая_формула(терм :

терм_логической_формулы):двоичный

если терм_логической_формулы(терм)==истина то

Логическая_формула= истина

иначе Логическая_формула=ложь

Составная логическая формула = объед (Терм логической

формулы, Знак логической операции, Терм логической формулы)

Описание: Терм логической формулы есть особого вида логическая формула.

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

проц Составная_логическая_формула (терм1:терм_логической_формулы, зн:знак_логической_операции, терм2: терм_логической_формулы):двоичный

объявить т1 тип двоичный

т1=0

объявить т2 тип двоичный

т2=0

т1= терм_логической_формулы(терм1)

т2= терм_логической_формулы(терм2)

если зн == “<” и т1<т2 то Составная_логическая_формула = истина

если зн == “>” и т1>т2 то Составная_логическая_формула = истина

если зн == “=>” и т1=>т2 то Составная_логическая_формула = истина

если зн == “=<” и т1=<т2 то Составная_логическая_формула = истина

если зн == “<>” и т1<>т2 то Составная_логическая_формула = истина

если зн == “==” и т1==т2 то Составная_логическая_формула = истина

если зн == “И” и т1 И т2 то Составная_логическая_формула = истина

если зн == “ИЛИ” и т1 ИЛИ т2 то Составная_логическая_формула = истина

если зн == “НЕ” и НЕ т1 то Составная_логическая_формула = истина

иначе Составная_логическая_формула = ложь

Обход дерева программы = (Начальный фрагмент, Текущий

фрагмент, Условие обхода, Тело обхода)

Описание: Обход дерева программы обозначает обход фрагментов дерева МСП (кроме фрагментов класса Выражение) «сверху-вниз», «слева-направо» начиная с фрагмента Начальный фрагмент, включая сам Начальный фрагмент. На каждой итерации Текущий фрагмент является фрагментом МСП в соответствии с правилами обхода. На каждой итерации проверяется Логическая формула, и если ее результат истина, то выполняется последовательность Конструкций из Тела обхода. Обход продолжается до тех пор, пока не будут пройдены все фрагменты поддерева МСП, вершиной которого является Начальный фрагмент.

Семантика:

Выполнение Обход дерева программы представляет собой рекурсию:

Шаг 1 (база рекурсии):

Вызвать рекурсивную функцию Шаг2 Текущий фрагмент равен Начальный фрагмент.

Шаг 2 (рекурсивная функция с параметром Текущий фрагмент):

Если класс переменной-фрагмента Текущий фрагмент равен Описание_одной_функции, то:

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Блок_описаний_функций, к которому от текущего фрагмента ведет дуга Описание_функций);

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Блок_описаний_параметров, к которому от текущего фрагмента ведет дуга Описание_параметров);

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Блок_описаний_типов, к которому от текущего фрагмента ведет дуга Описание_типов);

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Блок_описаний_переменных, к которому от текущего фрагмента ведет дуга Описание_переменных);

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Программный_блок, к которому от текущего фрагмента ведет дуга Тело).

Если класс текущего фрагмента Блок_описаний_функций, то последовательно для каждого фрагмента Описание_одной_функции, к которому от текущего фрагмента ведет дуга Оператор выполнить Шаг 2 (Текущий фрагмент равен фрагменту Описание_одной_функции).

Если класс текущего фрагмента Блок_описаний_параметров, то последовательно для каждого фрагмента Описание_одного_параметра, к которому от текущего фрагмента ведет дуга Оператор выполнить Шаг2 (Текущий фрагмент равен фрагменту Описание_одного_параметра).

Если класс текущего фрагмента Блок_описаний_типов, то последовательно для каждого фрагмента Описание_одного_типа, к которому от текущего фрагмента ведет дуга Оператор выполнить Шаг 2 (Текущий фрагмент равен фрагменту Описание_одного_типа).

Если класс текущего фрагмента Блок_описаний_переменных, то последовательно для каждого фрагмента Описание_одной_переменной, к которому от текущего фрагмента ведет дуга Оператор выполнить Шаг 2 (Текущий фрагмент равен фрагменту Описание_одной_переменной).

Если класс текущего фрагмента Программный_блок, то последовательно для каждого фрагмента, к которому от Текущего фрагмента ведет дуга Оператор выполнить Шаг 2 (Текущий фрагмент равен фрагменту к которому ведет дуга Оператор).

Если класс текущего фрагмента Условный_оператор, то:

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Программный_блок, к которому от текущего фрагмента ведет дуга То);

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Программный_блок, к которому от текущего фрагмента ведет дуга Иначе).

Если класс текущего фрагмента Цикл_for, то:

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Программный_блок, к которому от текущего фрагмента ведет дуга Тело).

Если класс текущего фрагмента Цикл_while, то:

выполнить Шаг2 (Текущий фрагмент равен фрагменту Программный_блок, к которому от текущего фрагмента ведет дуга Тело).

Если класс текущего фрагмента Цикл_repeat, то:

выполнить Шаг 2 (Текущий фрагмент равен фрагменту Программный_блок, к которому от текущего фрагмента ведет дуга Тело).

Если Условие обхода истинно, то поочередно выполнить Конструкции из Тела обхода.

проц рекурсия(тек: вершина, усл: логическая_формула, тело: конструкция)

Если тек. Дуга (Выражение_справа).класс== Описание_одной_функции то

Рекурсия(тек.перейти_по_дуге(Описание_функций усл,тело)

Рекурсия(тек.перейти_по_дуге(Описание_параметров усл,тело)

Рекурсия(тек.перейти_по_дуге(Описание_типов усл,тело)

Рекурсия(тек.перейти_по_дуге(Описание_переменных усл,тело)

Рекурсия(тек.перейти_по_дуге(Тело усл,тело)

Если тек.дуга(Выражение_справа).класс== Блок_описаний_функций то

Для и=0 по тек.количество_дочерн

Рекурсия(тек.перейти_по_дуге(Описание_одной_функции и],усл,тело)

Если тек.дуга(Выражение_справа).класс== Блок_описаний_параметров то

Для и=0 по тек.количество_дочерн

Рекурсия(тек.перейти_по_дуге(Оператор [и] ,усл,тело)

Если тек.дуга(Выражение_справа).класс== Блок_описаний_типов то

Для и=0 по тек.количество_дочерн

Рекурсия(тек.перейти_по_дуге(Оператор [и] ,усл,тело)

Если тек. Дуга (Выражение_справа). класс== Блок_описаний_переменных то

Рекурсия (тек.перейти_по_дуге (Оператор [и] ,усл,тело)

Если тек. дуга (Выражение_справа).класс== Программный_блок то

Рекурсия (тек. перейти_по_дуге(Оператор усл,тело)

Если тек. дуга (Выражение_справа).класс== Условный_оператор то

Рекурсия (тек.перейти_по_дуге(То усл,тело)

Рекурсия(тек.перейти_по_дуге(Иначе усл,тело)

Если тек.дуга(Выражение_справа).класс== Цикл_for то

Рекурсия(тек.перейти_по_дуге(Тело усл,тело)

Если тек.дуга(Выражение_справа).класс== Цикл_while то

Рекурсия(тек.перейти_по_дуге(Тело усл,тело)

Если тек.дуга(Выражение_справа).класс== Цикл_repeat то

Рекурсия(тек.перейти_по_дуге(Тело усл,тело)

Если Условие обхода == Истина то

метод_потокового_анализа (Тело_обхода)

проц обход_дерева_программы(нач: вершина, тек: вершина,усл: логическая_формула, тело: конструкция)

тек=нач

рекурсия(тек, усл, тело)

Обход дерева выражения = (Начальный фрагмент, Текущий

фрагмент, Тело обхода)

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

Семантика:

Выполнение Обход дерева выражения представляет собой рекурсию:

Шаг 1 (база рекурсии): Вызвать рекурсивную функцию

Шаг 2 Текущий фрагмент равен Начальный фрагмент.

Шаг 2 (рекурсивная функция с параметром Текущий фрагмент):

Если у фрагмента Текущий фрагмент по дуге Выражение_справа находится фрагмент класса Выражение, то

выполнить Шаг 2 (Текущий фрагмент равен фрагменту, к которому от текущего фрагмента ведет дуга Выражение_справа).

Если у фрагмента Текущий фрагмент по дуге Выражение_слева находится фрагмент класса “Выражение”, то

выполнить Шаг 2 (Текущий фрагмент равен фрагменту, к которому от текущего фрагмента ведет дуга Выражение_слева).

Поочередно выполнить Конструкции из Тела обхода.

проц рек(тек: вершина, тело: конструкция)

Если тек.дуга(Выражение_справа).класс==выражение то

рек(тек.дуга(Выражение_справа), тело)

Если тек.дуга(Выражение_слева).класс==выражение то

Рек(тек.дуга(Выражение_слева), тело)

метод_потокового_анализа (тело)

проц обход_дерева_выражения(нач: вершина, тек: вершина, тело: конструкция)

тек=нач

рек(нач, тело)

Выбор = (условие: Логическая формула, если истина: Последовательность конструкций, [если ложь : Последовательность конструкций])

Описание: Выбор состоит из Условия, и двух последовательностей Конструкций: Если истина и Если ложь.

Семантика: Если значение Условия есть истина, то выполнить последовательность Конструкций Если истина, в противном случае выполнить последовательность Конструкций Если ложь.

проц выбор(усл: Логическая_формула, ист: конструкция, ложь: конструкция)

объявить т тип булево

вызов логическая_формула(условие,т)

Если т==Истина то

метод_потокового_анализа (ист)

Иначе

метод_потокового_анализа (ложь)

Цикл = (Условие, Конструкция)

Описание: Цикл состоит из Условия, и последовательности Конструкций.

Семантика:

Выполнение Цикла есть выполнение следующих шагов:

Шаг1: Проверить Условие. Если значение Условия есть истина, выполнить Шаг2.

Шаг2: Выполнить последовательность Конструкций, вернуться к Шаг1.

проц цикл(усл: условие, конст: вершина)

объявить т тип булево

пока логическая_формула(условие,т)== Истина

цикл и=1 по конст.количество шаг 1

метод_потокового_анализа(конст.дочерн[и])

Создание фрагмента = (Аргумент-фрагмент, Класс фрагмента, Результат-фрагмент)

Описание: Создание фрагмента есть добавление к МСП нового фрагмента.

Семантика: Добавить к МСП новый фрагмент Результат-фрагмент. Класс нового фрагмента - Класс фрагмента, а предок - Аргумент-фрагмент.

проц Создание_фрагмента(арг: вершина, класс: класс, рез: вершина)

рез = арг.создать_дочерн

рез.класс = класс

Создание атрибута = (Аргумент-фрагмент, Имя атрибута, Значение атрибута)

Описание: Создание атрибута есть добавление к фрагменту МСП нового атрибута.

Семантика: Добавить к фрагменту Аргумент-фрагмент новый атрибут с именем Имя атрибута и значением Значение атрибута.

проц Создание_атрибута(арг: вершина, имя: строка, зн: переменная)

арг.создать_аттриб(имя, зн)

Изменение атрибута = (Переменная-атрибут, Значение атрибута)

Описание: Изменение атрибута есть изменение значения атрибута МСП.

Семантика: Изменить значение атрибута Переменная-атрибут на Значение атрибута.

проц Изменение_атрибута(пер_атр:атрибут, знач: тип)

пер_атр.значение = знач

Создание дуги = (Аргумент-фрагмент, Имя дуги, Аргумент-фрагмент2, Переменная-дуга)

Описание: Создание дуги есть добавление к МСП новой дуги.

Семантика: Добавить к МСП новую дугу Переменная-дуга от фрагмента Аргумент-фрагмент к фрагменту Аргумент-фрагмент2 с именем Имя дуги.

проц Создание_дуги(арг: выражение, имя: строка, арг2: выражение, п_дуга: переменная)

арг.создать_дугу(арг2, имя)

п_дуга = арг.дуга(имя)

Создание отношения = (Имя отношения, Аргумент-фрагмент, Аргумент-фрагмент2, Аргумент-фрагмент3, Аргумент-фрагмент4, Переменная-отношение)

Описание: Создание отношения есть добавление к МСП нового отношения.

Семантика: Добавить к МСП новое отношение Переменная-отношение с именем Имя отношения, которое бы связывало фрагменты Аргумент-фрагмент, Аргумент-фрагмент2, Аргумент-фрагмент3, Аргумент-фрагмент4.

проц Создание_отношения(имя_отн, а-ф, а--ф2, а-ф3, а-ф4, пер-отн)

объявить пер-отн тип отношение

пер-отн = создать_отношение(имя_отн, а-ф, а-ф2, а-ф3, а-ф4)

Создание переменной = (Значение переменной, тип переменной, имя переменной)

Описание: Создание переменной есть добавление к МСП новой переменой.

Семантика: Добавить к МСП новую переменную с именем Имя переменной, типом Тип переменной и значением Значение переменной.

проц Создание_переменной(зн_п, тип_п, имя_п)

объявить имя_п тип тип_п

имя_п = зн_п

Присваивание = (Левая часть присваивания, Правая часть присваивания)

Семантика: Вычислить значение Правой части присваивания и присвоить его Левой части присваивания.

Проц присваивание(л_ч: вершина, п_ч: вершина)

Если п_ч.тип == «Арифметическое выражение» то л_ч.значение = арифметическое_выражение (п_ч.дочерн[1], п_ч.дочерн[2], п_ч.дочерн[3])

Если п_ч.тип ==л_ч.тип то л_ч.зачение = п_ч.значение

Арифметическое выражение = (Терм выражения, Знак операции, Терм выражения)

Описание: Выражение есть последовательность арифметических операций.

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

проц Арифметическое_выражение(терм1: терм_выражения, зн: Знак_операции, терм2: терм_выражения): тип

терм1 = (терм1.дочерн[0])

терм2 = (терм2.дочерн[0])

Если зн == «+» то Арифметическое_выражение = терм1.значение + терм2.значение

Если зн == «-» то Арифметическое_выражение = терм1.значение - терм2.значение

Если зн == «*» то Арифметическое_выражение = терм1.значение * терм2.значение

Если зн == «/» то Арифметическое_выражение = терм1.значение / терм2.значение

Если зн == «^» то Арифметическое_выражение = терм1.значение ^ терм2.значение

2.4.3 Расширение базы методов потокового анализа программ

При помощи редактора методов потокового анализа программ в базу методов потокового анализа был занесен метод «ParDo». Представление этого метода в базе представлено ниже.

Метод потокового анализа

Название метода

ParDo

Конструкция -> Обход

Обход дерева программы

Начальный фрагмент -> Переменная-фрагмент «Функция_главная»

Текущий фрагмент -> Переменная-фрагмент «Цикл1»

Условие обхода

Переменная-фрагмент«Цикл1» == Класс_фрагмента «Цикл_Dfor»

Тело обхода

Обход дерева програмы

Начальный фрагмент -> Переменная-фрагмент «Цикл2»

Текущий фрагмент -> Переменная-фрагмент «Цикл1»

Условие обхода

Переменная-фрагмент «Цикл1» == Класс_фрагмента «Цикл_Dfor»

Тело обхода

Переменная-атрибут «Счетчик_Цикла1»

Переменная-фрагмент «Нач_гран_цикла2»

Атрибут_фрагмента( //Получили Сч_ц для внш «Цикл2»

«Цикл2»,

«Счетчик_цикла»,

«Счетчик_цикла1»)

Атрибут_фрагмента(//арг_множ от Нач_гр_ц (дуга For) «Цикл1»

Фрагмент_по_дуге(

«Цикл1»,

«Начальная_граница_цикла»,

«Нач_гран_цикла2»),

«Аргументное_множество»,

«Аргум_множ_1»)

Переменная-фрагмент «Кон_гран_цикла2»

Атрибут_фрагмента(//арг множ от Кон_гр_ц (дуга For) «Цикл1»

Фрагмент_по_дуге(

«Цикл1»,

«Конечная_граница_цикла»,

«Кон_гран_цикла2»),

«Аргументное_множество»,

«Арг_множ_2»)

Переменная-фрагмент «шаг»

Атрибут_фрагмента(//арг множ от шаг (дуга For) от «Цикл1»

Фрагмент_по_дуге(

«Цикл1»,

«шаг»,

«шаг1»),

«Аргументное_множество»,

«Арг_множ_3»)

Объединение_множеств(

Арг_множ_1,

Арг_множ_2,

«рез_об1»)

Объединение_множеств(

рез_об1,

Арг_множ_3,

«объед_множ2»)

Пересечение_множеств(

объед_множ2,

Счетчик_Цикла1,

«перес_множ1»)

Конструкция Выбор{//пункт 1

Условие -> равенство можеств

терм логической формулы -> перес_множ1

терм логической формулы -> пустое множество

Булево множество -> Истина

если истина// выполняем

Атрибут_фрагмента(//арг_множ от тело_ц (дуга For) «Цикл1»

Фрагмент_по_дуге(

«Цикл1»,

«тело_цикла»,

«тело_1»),

«Аргументное_множество»,

«Аргументное_1»)

Атрибут_фрагмента(//рез_множ от тело_ц (дуга For) «Цикл1»

Фрагмент_по_дуге( «Цикл1», «тело_цикла», «тело_1»),

«Результатное_множество»,

«Результатное_2»)

Пересечение_множеств(

Аргументное_1,

Результатное_2,

«перес_множ2») //

Конструкция Выбор//пункт 1

Условие -> равенство можеств

терм логической формулы -> перес_множ2

терм логической формулы -> пустое множество

Булево множество -> Истина

если истина// выполняем 1.1

Модификация программы

Создание атрибута(цикл2, «ParDo», «1»)

если ложь// выполняем 1.2

обход_дерева_программы («тело_1»,«текущий_DASS»,

«Класс_фрагмента(текущий_DASS)==

Оператор_присваивания» )// выполняем 1.2.1

{

аргумент-фрагмент «Левая_часть_DASS»

Атрибут_фрагмента(//для левой части выражения

Фрагмент_по_дуге(

«текущий_DASS»,

«левая часть»,

«л_ч»),

«Аргументное_множество»,

«левая_часть»)

аргумент-фрагмент «Правая_часть_DASS»

Атрибут_фрагмента(//для правой части выражения

Фрагмент_по_дуге(

«текущий_DASS»,

«правая часть»,

«п_ч»),

«результатное_множество»,

«правая_часть»)

пересечение множеств (

перес_множ2,

Левая_часть_DASS,

Перес_множ_л)

пересечение множеств (

перес_множ2,

Правая_часть_DASS,

Перес_множ_п)

Условие -> равенство множеств

терм логической формулы -> Перес_множ_п

терм логической формулы -> Перес_множ_л

Булево множество -> ложь

если истина// выполняем 2

«ошибка»=1

выход_из конструкции

если ложь// выполняем 1.2.1.1.1.

если

класс_фрагмента (

Фрагмент_по_дуге(

«текущий_DASS»,

«левая часть»,

«л_ч_2»)

==

«индекс»

значение_по_дуге(элем, индекс, «инд_л»)

Фрагмент_по_дуге(

«текущий_DASS»,

«правая часть»,

«п_ч_2»)

значение_по_дуге(элем, индекс, «инд_п»)

пересечение множеств(

Нач_гран_цикла2,

Инд_л,

«присут_л»)

пересечение множеств(

Нач_гран_цикла2,

Инд_п,

«присут_п»)

условие -> логическая формула

терм логической формулы -> инд_л

Знак логической операции -> <>

терм логической формулы -> инд_п

И

терм логической формулы -> присут_л

Булево множество -> истина

терм логической формулы -> пустое множество

И

терм логической формулы -> присут_п

Булево множество -> истина

терм логической формулы -> пустое множество

если истина// выполняем 2

«ошибка»=1

выход_из конструкции

)

Условие -> логическая формула

терм логической формулы -> ошибка

Знак логической операции -> =

терм логической формулы -> 0

если истина// выполняем 1.2.2

Модификация программы

Создание атрибута(цикл2, «ParDo», «1»)



3. Техническая часть

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

3.1 Назначение программного средства (ПС)

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

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

3.2 Архитектурно-контекстная диаграмма СБкЗ_ПП

Рассмотрим архитектурно контекстную диаграмму системы управления СБкЗ_ПП.

Диаграмма отображает внешнее окружение Системы Управления (СУ) СБкЗ_ПП. Здесь показано, что, работая с СБкЗ_ПП, пользователь может решать три основные задачи: Задача 1 - работа со знаниями и данными, Задача 2 - проведение экспериментов над преобразованием программ, Задача 3 - построение макета оптимизирующего компилятора. Для решения задач в СБкЗ_ПП на компьютере пользователя устанавливается интерфейсная часть (тонкий клиент), который взаимодействует с СУ на стороне сервера.

Рисунок 5. АКД СБкЗ_ПП

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

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

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

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

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

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

3.2.1 Подсистема потокового анализа

На рисунке представлена структура управления, с точки зрения последовательности применения подсистем на ключевую внутреннюю структуру данных МСП.

Рис. 6. Диаграмма потока данных

Выделенные красным цветом элементы - интересующие нас участки.

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

3.3 Архитектурно-контекстная диаграмма ПС

Рассмотрим архитектуру и контекст подсистемы потокового анализа, управляемого знаниями в рамках системы преобразований программ СБкЗ_ПП (рис. 7).