Рис. 7. Архитектурно-контекстная диаграмма подсистемы потокового анализа, управляемого знаниями

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

3.4 Требования к программному средству

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

3.4.1 Общие функциональные требования

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

1. Взаимодействие с банком знаний, в котором хранится МСП.

2. Взаимодействие с базой методов потокового анализа.

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

3.4.2 Конкретные функциональные требования

Для соответствия функциональным требованиям, программное средство должно содержать:

1. Функции взаимодействия с МБкЗ:

· подключение и открытие МБкЗ;

· закрытие соединения с МБкЗ.

2. Служебные функции:

· обход дерева метода потокового анализа;

· обход дерева МСП.

3. Функции интерпретации методов потокового анализа:.

· Изменение МСП в соответствии с указанными в методе изменениями.

3.4.3 Требования к программному обеспечению

На компьютере должен быть установлен JDK версии 1.4 или выше.

3.4.4 Требования к надежности

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

3.4.5 Профиль пользователя

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

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

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

3.4.7 Требования к интерфейсу

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



3.5 Проектная документация

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

3.5.1 Архитектура программного средства

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

Класс имеет следующие функции:

LoadMethod(String method)

Функция, загружающая метод потокового анализа с именем method

changeMSP()

Функция, загружающая необходимое дерево МСП и запускающая обход дерева методов

Mtd_tree(AST.Node cur)

Функция, вызывающая необходимое для заданной вершины дерева методов cur действие:

fragOnLink(cur)

Действия, выполняемые, если вершина cur - "Фрагмент по дуге"

FragAttr(cur)

Действия, выполняемые, если вершина cur - "Атрибут фрагмента"

GetClass(cur)

Действия, выполняемые, если вершина cur - "Получить класс"

GetPhraseVar(cur)

Действия, выполняемые, если вершина cur - "Получить переменную выражения"

FirstElem(cur)

Действия, выполняемые, если вершина cur - "Первый фрагмент по дуге из последовательности"

NextElem(cur)

Действия, выполняемые, если вершина cur - "Следующий фрагмент по дуге из последовательности"

PeresMnoz(cur)

Действия, выполняемые, если вершина cur - "Пересечение множеств"

ObyedMnoz(cur)

Действия, выполняемые, если вершина cur - "Объединение множеств"

RavMnoz(cur)

Действия, выполняемые, если вершина cur - "Равенство множеств"

LogicFormula(cur)

Действия, выполняемые, если вершина cur - "Логическая формула"

ComplexLogicFormula (cur)

Действия, выполняемые, если вершина cur - "Составная логическая формула"

CreateFrag(cur)

Действия, выполняемые, если вершина cur - "Создание фрагмента"

CreateLink(cur)

Действия, выполняемые, если вершина cur - "Создание дуги"

CreateRel(cur)

Действия, выполняемые, если вершина cur - "Создание отношения"

ProgramTree(cur)

Действия, выполняемые, если вершина cur - "Обход дерева программы"

PartTree(cur)

Действия, выполняемые, если вершина cur - "Обход дерева выражения"

Choice(cur)

Действия, выполняемые, если вершина cur - "Выбор"

Cycle(cur)

Действия, выполняемые, если вершина cur - "Цикл"

CreateAttr(cur)

Действия, выполняемые, если вершина cur - "Создание атрибута"

ChangeAttr(cur)

Действия, выполняемые, если вершина cur - "Изменение атрибута"

CreateVar(cur)

Действия, выполняемые, если вершина cur - "Создание переменной"

Prisv(cur)

Действия, выполняемые, если вершина cur - "Присваивание"

Virazh(cur)

Действия, выполняемые, если вершина cur - "Выражение"

3.5.2 Спецификации функций

LoadMethod(String method)

Входные параметры: строка method - имя загружаемого метода

Выходные параметры: целое vertex - количество вершин дерева

Функция, загружающая метод потокового анализа с именем method:

Подключиться к банку.

Загрузить теорию «Методы потокового анализа программ» из банка "Банк знаний о преобразованиях программ" в виде дерева типа AST.

Отключиться от банка.

changeMSP()

Входные параметры: нет

Выходные параметры: нет

Функция, загружающая необходимое дерево МСП и запускающая обход дерева методов:

Mtd_tree(AST.Node cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Функция, вызывающая необходимое для заданной вершины дерева методов cur действие:

См. п.2.4. «Метод потокового анализа»

Более подробно о принципе работы следующих функций написано в п.2.4. «Алгоритм решения задачи потокового анализа МСП».

fragOnLink(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Фрагмент по дуге"

FragAttr(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Атрибут фрагмента"

GetClass(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Получить класс"

GetPhraseVar(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Получить переменную выражения"

FirstElem(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Первый фрагмент по дуге из последовательности"

NextElem(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Следующий фрагмент по дуге из последовательности"

PeresMnoz(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата-множества

Действия, выполняемые, если вершина cur - "Пересечение множеств"

ObyedMnoz(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата-множества

Действия, выполняемые, если вершина cur - "Объединение множеств"

RavMnoz(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата: «T» или «F»

Действия, выполняемые, если вершина cur - "Равенство множеств"

LogicFormula(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата: «T» или «F»

Действия, выполняемые, если вершина cur - "Логическая формула"

ComplexLogicFormula (cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата: «T» или «F»

Действия, выполняемые, если вершина cur - "Составная логическая формула"

CreateFrag(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Создание фрагмента"

CreateLink(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата-атрибута

Действия, выполняемые, если вершина cur - "Создание дуги"

CreateRel(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Создание отношения"

ProgramTree(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение «T» или «F», если обнаружена ошибка

Действия, выполняемые, если вершина cur - "Обход дерева программы"

PartTree(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение значение «T» или «F», если обнаружена ошибка

Действия, выполняемые, если вершина cur - "Обход дерева выражения"

Choice(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Выбор"

Cycle(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение значение «T» или «F», если обнаружена ошибка

Действия, выполняемые, если вершина cur - "Цикл"

CreateAttr(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата-атрибута

Действия, выполняемые, если вершина cur - "Создание атрибута"

ChangeAttr(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение результата- атрибута

Действия, выполняемые, если вершина cur - "Изменение атрибута"

CreateVar(cur)

Входные параметры: AST.Node cur - вершина дерева методов

Выходные параметры: строка - значение переменной

Действия, выполняемые, если вершина cur - "Создание переменной"

Prisv(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Присваивание"

Virazh(cur)

Входные параметры: AST.Node cur - вершина дерева методов

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

Действия, выполняемые, если вершина cur - "Выражение"

3.5.3 Описание реализации программного средства

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

Среда реализации. Аппаратная часть среды: Intel Pentium-3 500 МГц, 256 Мб ОЗУ. Программная составляющая: необходима установленная JDK версии 1.4 или выше.

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



3.5.4 Описание использования программного средства

Для того, чтобы запустить интерпретацию метода потокового анализа на выполнение, необходимо импортировать библиотеку Interpretator и запустить процедуру LoadMethod(имя), где имя - название необходимого метода потового анализа. Результатом работы интерпретатора методов потокового анализа является измененная МСП.

4. Тестирование

В данной главе описывается тестирование программного средства.

4.1 Тестовые ситуации

1. Указанного метода не найдено

2. Указанный метод найден

2.1 Метод использует "Фрагмент по дуге"

2.2 Метод использует "Атрибут фрагмента"

2.3 Метод использует "Получить класс"

2.4 Метод использует "Получить переменную выражения"

2.4.1 Аргумент-фрагмент - терминальная вершина

2.4.2 Аргумент-фрагмент - нетерминальная вершина

2.5 Метод использует "Первый фрагмент по дуге"

2.6 Метод использует "Следующий фрагмент по дуге"

2.7 Метод использует "Пересечение множеств"

2.7.1 одно из множеств - пустое

2.7.2 множества не пусты

2.8 Метод использует "Объединение множеств"

2.8.1 одно из множеств - пустое

2.8.2 множества не пусты

2.9 Метод использует "Равенство множеств"

2.9.1множества равны

2.9.2 множества не равны

2.10 Метод использует "Логическая формула"

2.11 Метод использует "Создание фрагмента"

2.12 Метод использует "Создание дуги"

2.13 Метод использует "Создание атрибута"

2.14 Метод использует "Изменение атрибута"

2.15 Метод использует "Создание переменной"

2.16 Метод использует "Присваивание"

2.16.1 типы левой и правой частей присваивания совместимы

2.16.2 типы левой и правой частей присваивания несовместимы

2.17 Метод использует "Выражение"

2.18 Метод использует "Составная логическая формула"

4.2 Тесты

По плану тестирование будет представлять собой тестирование всего программного средства по методу «черного ящика».

№	№ тс	Вход	Ожидаемый результат	Выход	Успешность
1	1	Load method(“A”)	“”	“”	+
2	2	Load method(“ParDo”)	“T”	“T”	+
3	2.1	Арг = Фрагмент МСП (тип DIf) Имя_дуги =Если Результат -фрагмент = рез	рез= фрагмент (тип DExpr, являющийся потомком Арг)	рез= фрагмент (тип DExpr, являющийся потомком Арг)	+
4	2.2	Арг = Фрагмент МСП (тип DAss) Имя_атрибута = Аргументное_множество Результат -атрибут = рез	Рез={a, b, c}	Рез={a, b, c}	+
5	2.3	Арг = Фрагмент МСП (тип Dexpr) Результат-класс фрагмента = рез	Рез= «Выражение»	Рез= «Выражение»	+
6	2.4.1	Арг = Фрагмент МСП (тип Dexpr) Результат-переменная = рез	Рез= a	Рез= а	+
7	2.4.2	Арг = Фрагмент МСП (тип Dexpr) Результат-переменная = рез	Рез=	Рез=	+
8	2.5	Арг = Фрагмент МСП (тип Dbody) Результат -фрагмент = рез	рез= фрагмент (тип DIf, являющийся потомком Арг)	рез= фрагмент (тип DIf, являющийся потомком Арг)	+
9	2.6	Арг = Фрагмент МСП (тип Dbody) Результат -фрагмент = рез	рез= фрагмент (тип DExpr, являющийся потомком Арг)	рез= фрагмент (тип DExpr, являющийся потомком Арг)	+
10	2.7.1	Аргумент-множество1={a, b, c} Аргумент-множество2={} Результат- множество=рез	Рез={ }	Рез={ }	+
10	2.7.2	Аргумент-множество1={a, b, c} Аргумент-множество2={a, c} Результат- множество=рез	Рез={a, c}	Рез={a, c}	+
11	2.8.1	Аргумент-множество1={a, b, c} Аргумент-множество2={} Результат- множество=рез	Рез={a, b, c}	Рез={a, b, c}	+
12	2.8.2	Аргумент-множество1={a, b, c} Аргумент-множество2={a, c} Результат- множество=рез	Рез={a, b, c, a, c}	Рез={a, b, c, a, c }	+
13	2.9.1	Аргумент-множество1={a, b, c} Аргумент-множество2={} булево =рез	Рез= "False"	Рез= "False"	+
14	2.9.2	Аргумент-множество1={a, b, c} Аргумент-множество2={a, b, c} булево=рез	Рез= "True"	Рез= "True"	+
15	2.10	Логическая формула= составная логическая формула Аргумент1=переменная арг1 Аргумент2= переменная арг2 Знак= «==»	"True"	"True"	+
16	2.11	Аргумент1=переменная арг1 Аргумент2= переменная переем_1 Знак= «==»	" False "	" False "	+
17	2.12	Арг = Фрагмент МСП (тип Dbody) класс =Условный Результат -фрагмент = рез	рез= фрагмент (тип DIf, являющийся потомком Арг)	рез= фрагмент (тип DIf, являющийся потомком Арг)	+
18	2.13	Арг = Фрагмент МСП (тип Dexpr) имя = Аргументное_множество значение = { a, b, c}	Создан аргумент от фрагмента арг Имя= Аргументное_множество значение = { a, b, c}	Создан аргумент от фрагмента арг Имя= Аргументное_множество значение = { a, b, c}	+
19	2.14	Арг = Фрагмент МСП (тип Dexpr) имя = Аргументное_множество значение = { b, c}	аргумент от фрагмента арг Имя= Аргументное_множество значение = {b, c}	аргумент от фрагмента арг Имя= Аргументное_множество значение = {b, c}	+
20	2.15	Имя переменной = пер1 Тип = вещественный	Создана переменная	Создана переменная	+
21	2.16.1	Левая часть = фрагм1 Правая часть = фрагм2	Фрагм1=фрагм2	Фрагм1=фрагм2	+
22	2.16.2	Левая часть = фрагм1 Правая часть = 34	F	F	+
23	2.17	Аргумент1=3 Аргумент2=5 Знак = "+"	8	8	+
24	2.18	(2+4)*5	30	30	+



5. Экспериментальное изучение свойств программного средства

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

5.1 Цель экспериментов

1. Проверить совместимость с уже существующими компонентами новой версии СБкЗ_ПП.

2. Оценить время работы программного средства в зависимости от сложности исходных данных.

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

5.2 Описание среды

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

Рис. 8. Схема применения компонентов СБкЗ_ПП для экспериментов

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

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

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

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

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

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



Таблица 1

Сложность операторов и операций

Операция	Сложность
Унарная арифметическая или логическая операция	1
Бинарная арифметическая или логическая операция	2
Операция взятия элемента массива	2
Оператор присваивания	4
Оператор объявления переменной	4
Условный оператор	5
Оператор цикла For	7

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

Аппаратное обеспечение, используемое при проведении экспериментов: Intel Mobile 2.13 GHz, 1024 Мб ОЗУ. Программное обеспечение, используемое при проведении экспериментов: ОС MS Windows XP. Данные для проведения экспериментов описаны в приложении 1, набор тестовых данных №1.

5.3 План экспериментов

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

По схеме применения компонентов СБкЗ_ПП для экспериментов (рис. 9) выполняется запуск соответствующих программных средств.

Для эксперимента использовались: дерево методов потокового анализа (694 вершины) и мсп:

Эксперимент №1

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

1. Запущена зарузка дерева методов потокового анализа.

2. Запущен МСП-генератор.

3. На выходе МСП-генератора получена МСП, находящаяся в СБкЗ_ПП.

4. Запущена программа, которая осуществляет интерпретирование метода потокового анализа на дерево МСП.

5. На выходе получена МСП, расширенная термином потокового анализа и находящаяся в СБкЗ_ПП.

Рис 9. МСП для эксперимента



Результат: Все реализованные части системы СБкЗ_ПП отработали совместно без возникновения ошибок. Время, за которое выполнились функции загрузки равно 144813 мсек. Время, за которое выполнились функции интерпретирования методов равно 84 мсек.

Эксперимент №2

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

1. Запущена зарузка дерева методов потокового анализа (542 вершины).

2. МСП-генератор сгенерировал МСП, находящуюся в СБкЗ_ПП.

3. Запущена программа, которая осуществляет интерпретирование метода потокового анализа на дерево МСП.

4. На выходе получена МСП, расширенная термином потокового анализа и находящаяся в СБкЗ_ПП..

Результат: Время, за которое выполнились функции загрузки равно 65216 мсек. Время, за которое выполнились функции интерпретирования методов равно 52 мсек.

Эксперимент №3

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

1. Запущена зарузка дерева методов потокового анализа (128 вершин).

2. МСП-генератор сгенерировал МСП, находящуюся в СБкЗ_ПП.

3. Запущена программа, которая осуществляет интерпретирование метода потокового анализа на дерево МСП.

4. На выходе получена МСП, расширенная термином потокового анализа и находящаяся в СБкЗ_ПП.

Результат: Время, за которое выполнились функции загрузки равно 22217 мсек. Время, за которое выполнились функции интерпретирования методов равно 13 мсек.



5.4 Результаты экспериментов

Сводная таблица времени выполнения приведена в таблице 2.

Таблица 2. Время выполнения экспериментов в мс (ось Y) и сложность входных данных (ось X)

Из вышеприведенных результатов экспериментов можно сделать следующие выводы:

· Со всеми реализованными компонентами СБкЗ_ПП, программное средство работало без сбоев, это позволяет сделать вывод, что оно совместимо с остальной системой;

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



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

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

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

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

Было реализовано программное средство, интерпретирующее методы потокового анализа, управляемого знаниями, для распараллеливаемых программ в МСП как части СБкЗ_ПП. Программное средство было реализовано в среде IntelliJ Idea 6 на языке Java.

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

На основании этого можно считать, что цель дипломной работы достигнута.

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



Заключение

В ходе выполнения дипломной работы были получены следующие результаты:

· написан обзор литературы, по теме «потоковый анализ программ в распараллеливающих и оптимизирующих компиляторах»;

· сформулированы требования к программному средству, реализующему интерпретацию методов потокового анализа;

· создана техническая документация для программного средства;

· реализовано программное средство.

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

1. Абрамов С.М., Адамович А.И., Инюхин А.В., Московский А.А., Роганов А.В., Шевчук Ю.А., Шевчук Е.В. // Т-система с открытой архитектурой. ИПС РАН, г. Переславль-Залесский. http://skif.pereslavl.ru/skif/index.cgi?module=chap&action=getpage&data=publications%5Cpubl2004%5Ct-system-ssa_2004.doc.

2. Артемьева И.Л., Князева М.А., Купневич О.А. Модель онтологии предметной области "Оптимизация последовательных программ". Термины для описания объекта оптимизации. Препринт 29-2000 - 44с.

3. Артемьева И.Л., Князева М.А., Купневич О.А. модель онтологии предметной области "Оптимизация последовательных программ". Термины для описания потокового анализа программ. Владивосток: ИАПУ ДВО РАН, 2004.28 с.

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

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

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

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

8. Касьянов В.Н., Трахтенброт М.Б. Анализ структур программ в глобальной оптимизации // Сборник научных трудов. - Новосибирск, 1975.-С.143-161.

9. Компилятор Fortran-DVM. Детальный дизайн http://www.keldysh.ru/dvm/dvmhtm1107/rus/sys/fdvm/fdvmDDr.html

10. Компиляторы Intel C++ и Fortran и библиотека MKL. http://parallel.ru/cluster/intel_compilers.html

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

12. Нис З.Я. Автоматизация проверок семантической корректности распараллеливающих преобразований // PACO' 2006 (Тр. международной конференции «Параллельные вычисления и задачи управления» 2-4 октября 2006г. Москва, М.: ИПУ РАН, 2006. С.565-577.)

13. Петренко В.В. Новое внутреннее представление открытой распараллеливающей системы. Дипломная работа. - Ростовский РГУ, 2005.- 40 с.

14. Рагозин Д.В., Митин Р.О., Галкин С.В., Лялин С.С. Оптимизирующие компиляторы (на примере GCC). http://compiler.itlab.unn.ru/uploads/compiler_practice.update19.doc

15. Система V-Ray. http://www.parallel.ru/v-ray

16. Терехов А.А. Анализ потоков данных http://www.intuit.ru/department/sa/compilersdev/13/

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

18. Acovea Overview. http://www.coyotegulch.com/products/acovea/index.html

19. Adve S., Rawsthorne A., Kandemir M., Fang J., Burger D., Smith M.D., Lilja D.J., Yew P-C., R. Eigenmann, C. Gebotys, A. Choudhary The Interaction of Architecture and Compilation Technology for High-Performance Processor Design, 1997

20. Interactive Parallel Programming Using the ParaScope Editor. http://www.cs.utexas.edu/users/mckinley/papers/ped.pdf

21. Kleshev A.S. Artemjeva I.L. Mathematical models of domain ontologies. Technical report 18-2000. Vladivostok, IACP of FEBRAS, 43 p.

22. Kleshev A.S. Artemjeva I.L. Unenriched logical relationship systems. Technical report 1-2000. Vladivostok, IACP of FEBRAS, 43 p.

23. Red Hat Enterprise Linux 4: Using the GNU Compiler Collection (GCC). GCC Command Options http://www.redhat.com/docs/manuals/enterprise/RHEL-4-Manual/gcc/optimize-options.html

24. S-J. Min, A. Basumallik, R. Eigenmann Optimizing OpenMP Programs on Software Distributed Shared Memory Systems http://www.ece.purdue.edu/ParaMount

25. Suif Optimization Programming Interface. http://www.eecs.harvard.edu/machsuif/software/nci/opi-users.html

Приложение 1. Каталог реструктурирующих преобразований программ

Вариант 1

1. обмен циклов

Бэкон 6.2.1 (16), Никитин _

0.115 октября 2006

Описание

Преобразование состоит в перестановке местами каких-либо двух циклов в тесно вложенном гнезде циклов. В частности, всегда можно переставлять рядом стоящие циклы, имеющие по всем зависимостям тип ParDo. После перестановки свойство РаrDo сохраняется у обоих циклов. Если возможна перестановка 1-го цикла с k-ым и 1-ый цикл имеет тип РаrDо, то после перестановки тип РаrDо будет иметь k-ый цикл. Пусть самый внешний цикл имеет тип РаrDо по всем зависимостям. Его всегда можно переставить со вторым циклом. Новый второй цикл будет также иметь тип РаrDо по всем зависимостям. Поэтому его можно переставить с третьим циклом и т. д. Это означает, что любой цикл РаrDо всегда можно поставить в тесно вложенном гнезде на любое более глубокое место. При этом свойство РаrDо сохраняется. В противоположность этому, в общем случае переставлять внутренний цикл РаrDо "наружу" нельзя.

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



Пример

было

Do i=1,n

do j=1,n

total[i]=total[i]+a[i,j]

end do

end do

стало

Do j=1,n

do i=1,n

total[i]=total[i]+a[i,j]

end do

end do

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из другого цикла For, тело которого, в свою очередь, состоит из двух операторов.

Здесь Y1 - первый (внешний) цикл For, Y2 - второй (внутренний) цикл For. У каждого цикла есть свои начальные границы - E1 и T1, свои конечные границы - E3 и T3, свои шаги цикла E2 и T2 и свои тела циклов - B1 и B2. Причём Y2 является телом цикла Y1. D - представление тела внутреннего цикла Y2 в виде последовательности операторов, X1 и X2 - две части этой последовательности.

Информационные условия:

Любой цикл РаrDо всегда можно поставить в тесно вложенном гнезде на любое более глубокое место.

Формальное контекстное условие

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2, D, X1, X2>(

FragClass(Y1)=Dfor & FragClass(Y2)=Dfor &

FragClass(B1)=Dbody & FragClass(B2)=Dbody & FragClass(D)=Dsch &

FragClass(E1)=Dexpr & FragClass(E2)=Dexpr & FragClass(E3)=Dexpr &

FragClass(T1)=Dexpr & FragClass(T2)=Dexpr & FragClass(T3)=Dexpr &

FragClass(X1)=DASS & FragClass(X2)=DASS &

B1=Body(Y1) & Begin(B1)=Y2 & End(B1)=Y2 &

B2=Body(Y2) & Begin(D)=Begin(X1) & End(D)=End(X2) & D=Sch(B2)

&

Left(E1){Const} & Left(E2){Const} & Left(E3){Const} &

Left(T1){Const} & Left(T2){Const} & Left(T3){Const} &

R( Expr(X1)) A(LvalueExpr(X2)) = &

R(LvalueExpr(X1)) A(Expr(X1)) = &

ParDO(Y1)=True &

(X1, X2, Y1) = false & (X2, X1, Y1) = false &

v1: Dexpr & v1 < LValueExpr (X1) & OP(v1) = NULL & IsArray (Type(Left(v1))) = true & A(LvalueExpr(X1)) \ Par(Y1) \ Par(Y2) \ R(v1) =

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

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

v3: Dexpr & v3 < Expr (X2) & OP(v3) = NULL & IsArray (Type(Left(v3))) = true & isleft(v3)=isleft(v1) & A(Expr(X1)) \ Par(Y1) \ Par(Y2) \ R(v3) =

Неформальное описание трансформации

Меняем все нижние и верхние границы циклов, а также их шаги местами. Также меняем местами счетчики циклов.

Формальное описание трансформации

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2> ( (E1Z,T1) & (E2Z,T2) & (E3Z,T3) & (T1Z,E1) & (T2Z,E2) & (T3Z,E3), i1=Par(Y1) & i2=Par(Y2), E1E1Z, E2E2Z, E3E3Z, T1T1Z, T2T2Z, T3T3Z, Par(Y1)=i2, Par(Y2)=i1)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец / Обмен циклов /

2. Распределение цикла

Бэкон 6.2.7 (23)

Воеводин 417

0.127 августа 2006



Описание

Распределение циклов (также называемое расщеплением циклов или разделением циклов) разбивает гнездо циклов на несколько отдельных циклов. Каждый из новых циклов имеет тоже итерационное пространство, что и исходный цикл, но содержит подмножество операторов исходного цикла.

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

Пример

было

do i = 1, n

do j = 1, m

a[i] = a[i] + c

x[j] = x[j] + x[j]*10

end do

end do

стало

do all i = 1, n

a[i] = a[i] + c

end do

do j = 1, m

x[j] = x[j] + x[j]*10

end do

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

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

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из другого цикла For, тело которого, в свою очередь, состоит из двух операторов.

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

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



Здесь Y1 - первый (внешний) цикл For, Y2 - второй (внутренний) цикл For. У каждого цикла есть свои начальные границы - E1 и T1, свои конечные границы - E3 и T3, свои шаги цикла E2 и T2 и свои тела циклов - B1 и B2. Причём Y2 является телом цикла Y1. D - представление тела внутреннего цикла Y2 в виде последовательности двух операторов, X1 и X2 - первый и второй оператор.

Информационные условия:

результаты X2 не влияют на X1

результаты X1 не влияют на X2

X1 и X2 не имеют общих результатов

Аргументное множество X2 не содержит переменную цикла Y1

Аргументное множество X1 не содержит переменную цикла Y2

Оба цикла имеют тип ParDO

Формальное контекстное условие

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2, D, X1, X2>( FragClass(Y1)=Dfor & FragClass(Y2)=Dfor & FragClass(B1)=Dbody & FragClass(B2)=Dbody & FragClass(D)=Dsch & & FragClass(E1)=Dexpr & FragClass(E2)=Dexpr & FragClass(E3)=Dexpr & FragClass(T1)=Dexpr & FragClass(T2)=Dexpr & FragClass(T3)=Dexpr &FragClass(X1)=DASS & FragClass(X2)=DASS & B1=Body(Y1) & Begin(B1)=Y2 & End(B1)=Y2 & B2=Body(Y2) & D=Sch(B2) & Begin(D)=Begin(X1) & End(D)=End(X2) & Left(E1){Const} & Left(E2){Const} & Left(E3){Const} & Left(T1){Const} & Left(T2){Const} & Left(T3){Const} &

R( X1) R(X2) = &

A( X1) Par(Y2) = &

A( X2) Par(Y1) = &



ParDO(Y1)=True & ParDO(Y2)=True &

(X1, X2, Y1) = false & (X2, X1, Y1) = false.

Неформальное описание трансформации

Гнездо из двух циклов разбиваем на два отдельных цикла

Формальное описание трансформации

< Y1, Y2, E1, E2, E3, T1, T2, T3, B1, B2, X1, X2>

(FragClass(V1)={Dfor} & For(V1)=(For(Y1)) & Until(V1)= (Until(Y1)) & Step(V1)= (Step(Y1)) & Par(V1)=Par(Y1) & Sch(Body(V1))=(X1)) & & FragClass(V2)={Dfor} & For(V2)= (For(Y2)) & Until(V2)= (Until(Y2)) & Step(V2)= (Step(Y2)) & Par(V2)=Par(Y2) & Sch(Body(V2))=(X2) &FragClass(Z1)={Dsch} & Z1=V1||V2, Y1Z1)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец / Распределение цикла /

3. Объединение циклов

Бэкон 6.3.3 (27)

Воеводин 416

0.127 августа 2006

Описание

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

Объединение позволяет свернуть гнездо циклов в один цикл с оригинальными индексными переменными, которые вычисляются с помощью другой индексной переменной. Объединение может улучшить распределение цикла при параллельных вычислениях и уменьшить итерационные переходы. Например, если n и m немного больше, чем количество процессоров P (см. пример №6), то ни одна итерация, равно как и внешний цикл не займет столько времени, с момента выполнения последних n-P итераций, как первые P. Объединение двух циклов гарантирует, что P итераций могут выполняться каждый раз за исключением последних (nm mod P) итераций, как показано в примере

Пример

было

do all i=1, n

do all j=1, m

a[i,j] = a[i,j] +c

end do all

end do all

стало

do all T=1, n*m

i = ((T-1) / m)*m + 1

j = MOD(T-1, m) + 1

a[i,j] = a[i,j] + c

end do all



Неформальное контекстное условие

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

Схема

здесь D - последовательность операторов, Y1 и Y2 - два цикла For, являющиеся ее началом и концом соответственно, Y - последовательность операторов, возможно пустая, лежащая между ними. У каждого цикла есть свои начальные границы - E1 и T1, свои конечные границы - E3 и T3, свои шаги цикла E2 и Е2 и свои тела циклов - B1 и B2. Образы выражений E1 и Е1, E2 и T2, E3 и T3 соответственно должны совпадать.

Информационные условия:

Результаты E1, E2, E3, B1, Y не должны влиять на T1, T2, T3 или B2

Результаты B2 не должны влиять на B1 и Y

Формальное контекстное условие

<D, Y, Y1, Y2, E1, E2, E3, T1,T2,T3, B1,B2> (

FragClass(D)=Dsch & FragClass(Y1)=Dfor &

FragClass(Y)=Dsch & FragClass(Y2)=Dfor &

FragClass(E1)=Dexpr & FragClass(E2)=Dexpr & FragClass(E3)=Dexpr & FragClass(T1)=Dexpr & FragClass(T2)=Dexpr & FragClass(T3)=Dexpr & FragClass(B1)=DBody & FragClass(B2)=DBody &

Begin(D)=Y1 & End(D)= Y2 & Y2<>Y1 & <(Y1, Y) & <(Y, Y2) & IsLine(D) & IsLine(Y) & B1=Body(Y1) & B2=Body(Y2)& Image(E1)= Image(T1) & Image(E2)= Image(T2) & Image(E3)= Image(T3) & ((R(E1) R(E2) R(E3) R(B1) R(Y)) (A(T1) A(T2) A(T3) A(B2)))= & R(B2) (A(B1) A(Y))= , ParDO(Y1)=True & ParDo(Y2)=True)

Неформальное описание трансформации

Тело цикла B1 заменяется на конкатенацию B1 и B2 c заменой в B2 всех вхождений параметра цикла Y2 на параметр цикла B1

цикл Y2 заменяется на Null

Гнездо из двух циклов разбиваем на два отдельных цикла

Формальное описание трансформации

<D, Y, Y1, Y2, E1, E2, E3, T1,T2,T3, B1,B2>(FragClass(B3)=Dsch & B3=(B1) || Zam(B2, Par(Y2), Par(Y1)), B1B3, Y2 NULL)

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец / Объединение циклов /

4. Распределение цикла

Бэкон 6.2.3 (20)

Воеводин 418

0.127 августа 2006

Описание

Распределение циклов (также называемое расщеплением циклов или разделением циклов) разбивает гнездо циклов на несколько отдельных циклов. Каждый из новых циклов имеет тоже итерационное пространство, что и исходный цикл, но содержит подмножество операторов исходного цикла.

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

Пример

было

do i = 1, n

do j = 1, n

a[i,j] = a[i-1,j+1] + 1

end do

end do

стало

do i = 1, n

do j = n, 1, -1

a[i,j] = a[i-1,j+1] + 1

end do

end do

исходное гнездо циклов: дистанционный вектор (1, -1) - перестановка недопустима

внутренний цикл инвертирован: вектор направлений (1, 1) - перестановка допустима

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из последовательности операторов.

Y - цикл. У цикла есть свои границы: Е1 - начальная граница, Е2 - конечная граница, Е3 - шаг цикла. B - тело цикла. E3 = 1. E1>0.

Формальное контекстное условие

<Y,E1,E2,E3,B>(FragClass(Y)=Dfor & FragClass(B)=Dbody & FragClass(E1)=Dexpr & FragClass(E1)=Dexpr & FragClass(E2)=Dexpr & FragClass(E3)=Dexpr & ParDO(Y)=True & E1 = For(Y) & E2 = Until(Y) & E3 = Step(Y) & B = Body(Y) & Eval(E1, null, null) > 0 & Eval(E3, null, null) = 1 ).

Неформальное описание трансформации

Создаём Y'. Y' - это цикл For такой, что значения его начальной границы совпадают со значениями конечной границы цикла Y, значение конечной границы со значением начальной границы Y, а шаг цикла = -1.

Цикл Y переходит в цикл Y'.

Формальное описание трансформации

<Y,E1,E2,E3,B,D> ( (c: Новые идентификаторы (Var, Int)) &

FragClass(Y')=Dfor & Par(Y')=Par(Y) & Sch(Body(Y))=?Sch(Body(Y'))& For(Y')=NewExp(C)& For(Y') =? (Until(Y))& Until(Y')=NewExp(C) & Until(Y') =? (For(Y)) & Eval(Step(Y')=1),Y=>Y')

Характеристическая функция

Формула стратегии

Элементы потокового анализа

Конец /Распределение цикла /

5. Разбиение цикла

Бэкон 6.2.6 (22)

0.127 августа 2006

Описание

Разбиение цикла является многомерным обобщением послойного разбора. Разбиение цикла (также называемое блочным разбиением) в основном используется для улучшения повторного использования кэша (Qc) и представляет собой деление итерационного пространства на блоки и преобразования гнезда циклов для проведения итераций над этими блоками. Однако оно может использоваться для улучшения использования процессоров (на многопроцессорных машинах), регистров, TLB (Translation Lookaside Buffer - используется для преобразования линейных адресов в физические адреса), или размещения страниц памяти.

Ниже приведен пример №8 гнезда массивов, в котором матрице a присваивается транспонированная матрица b. Во внутреннем цикле (с итерационной переменной j) доступ к элементам массива b осуществляется максимальным шагом 1, в то время, как доступ к элементам массива a - с максимальным шагом n. Перестановка циклов в данном случае не поможет, т.к. после перестановки доступ к элементу массива b будет осуществляться с максимальным шагом n. Осуществляя дополнительные итерации над прямоугольными подпространствами итерационного пространства, как показано в примере №8, достигается полное использование кэша.

Пример

было

do i = 1, n

do j = 1, n

a[i,j] = b[j,i]

end do

end do

стало

do TI = 1, n, 64

do TJ = 1, n, 64

do i = TI, min(TI+63,n)

do j = TJ, min(TJ+63,n)

a[i,j] = b[j,i]

end do

end do

end do

end do

Неформальное контекстное условие

Участком экономии в данном случае является цикл For, тело которого состоит из другого цикла For, тело которого, в свою очередь, состоит из последовательности операторов. Здесь Y1 - первый (внешний) цикл For, Y2 - второй (внутренний) цикл For. У каждого цикла есть свои начальные границы - O1 и O2, свои конечные границы - E1 и E2, свои шаги цикла S1 и S2 и свои тела циклов - B1 и B2. Причём Y2 является телом цикла Y1. D - представление тела внутреннего цикла Y2 в виде последовательности операторов



Формальное контекстное условие

< Y1, Y2, B1, B2, O1, O2, E1, E2, S1, S2, D > ( FragClass(Y1)=Dfor & FragClass(Y2)=Dfor &

FragClass(B1)=Dbody & FragClass(B2)=Dbody & FragClass(D)=Dsch &

FragClass(O1)=Dexpr & FragClass(E1)=Dexpr & FragClass(S1)=Dexpr &

FragClass(O2)=Dexpr & FragClass(E2)=Dexpr & FragClass(S2)=Dexpr &

B1=Body(Y1) & Begin(B1)=Y2 & End(B1)=Y2 &

B2=Body(Y2) & D=Sch(B2) &

ParDO(Y1)=True

Неформальное описание трансформации

Создаём Y1'. Y1' - это цикл For такой, что значения его начальной и конечной границы совпадают со значениями начальной и конечной границы цикла Y1 соответственно, а шаг цикла - увеличенный шаг цикла Y1. Создаём целочисленную переменную - счётчик цикла Y1 - V1. Телом цикла Y1' является цикл Y2'. Y2' - это цикл For такой, что значения его начальной и конечной границы совпадают со значениями начальной и конечной границы цикла Y2 соответственно, а шаг цикла - увеличенный шаг цикла Y2. Для него так же создаем целочисленную переменную, которая будет являться счётчиком цикла - V2. Внутри цикла Y2 создаём цикл Y3 c шагом 1, начальная граница которого совпадает с текущим значением V1, а конечная - min(V1 + (значение(S1) - 1), E1). Y3 - является телом цикла Y2'. Затем, уже внутри цикла Y3, создаём цикл Y4 так же c шагом 1. Начальная граница Y4 совпадает с текущим значением V2, а конечная - min(V2 + (значение(S2) - 1), E2). Y4 - является телом цикла Y3. Телом цикла Y4 - является последовательность операторов - D

Формальное описание трансформации

< Y1, Y2, B1, B2, O1, O2, E1, E2, S1, S2, D > ( (c: Новые идентификаторы (Var, Int)) &

FragClass(Y1')=Dfor & For(Y1')=?(For(Y1)) & Until(Y1')=?(Until(Y1)) &

Step(Y1')=Eval(Step(Y1),+,NewExpr(c)) & V1=NewExpr(c) &

FragClass(Y2')=Dfor &For(Y2')=?(For(Y2)) & Until(Y2')=?(Until(Y2)) &

Step(Y2')=Eval(Step(Y2),+,NewExpr(c)) & V2=NewExpr(c) &

FragClass(Y3)=Dfor & Par(Y3)=?(V1) & For (Y3)=Eval(V1) & Step (Y3)=Eval(1) &

Until(Y3)=MakeExpr(MakeExpr(MakeExpr(Step(Y1),-,1),+,V1),min,E1) &

FragClass(Y4)=Dfor & Par(Y4)=?(V2) & For (Y4)=Eval(V2) & Step (Y4)=Eval(1) &

Until(Y4)=MakeExpr(MakeExpr(MakeExpr(Step(Y2),-,1),+,V2),min,E2) &

Sch(Body(Y1'))=?(Y2') & Sch(Body(Y2'))=?(Y3) & Sch(Body(Y3))=?(Y4) &

Sch(Body(Y4))=?(Y4) || =?(Sch(Body(Y2))), Y1 => Y1', Y2 => Y2' || Y3 | Y4 )

Характеристическая функция

Формула стратегии

Элементы потокового анализа Конец /Разбиение цикла/

6. Развертка цикла

Бекон 6.3.1 (24)

0.127 августа 2006

Описание

Развёртка в точности копирует тело цикла некоторое количество раз, называемое фактором разворачивания (unrolling factor) u. Каждая итерация после этого будет состоять не из одного, а из u шагов. Выгода использования разворачивания циклов была изучена на нескольких различных архитектурах.

Развёртка может улучшить производительность посредством:

· уменьшения количества итераций и соответственно количество условных переходов;

· увеличения параллелизма инструкций;

улучшения использования регистров, кэша данных