М. А. КНЯЗЕВА, П. Н. ГРИШИН
Институт автоматики и процессов управления ДВО РАН, Владивосток
МЕТОДЫ ПОИСКА УЧАСТКОВ ЭКОНОМИИ И ПРОВЕРКИ КОНТЕКСТНЫХ УСЛОВИЙ РЕСТРУКТУРИРУЮЩИХ ПРЕОБРАЗОВАНИЙ В ПРЕОБРАЗОВАТЕЛЕ ПРОГРАММ
В работе описаны методы поиска фрагментов исходной программы (участков экономии), удовлетворяющих условиям применимости (контекстные условия) реструктуризирующего преобразования над найденными фрагментами программы, в специализированном банке знаний о преобразованиях программ.
Одним из способов создания параллельных программ является реструктуризация последовательных программ [1]. Формально реструктуризация сводится к математически эквивалентным заменам в записях всех или части формульных выражений с целью явно указать обнаруженные в алгоритмах скрытый параллелизм. Следовательно, необходимо иметь эффективные технологии как для выявления требуемых свойств алгоритмов, так и для выполнения преобразований самих записей к виду, в котором все эти свойства можно описать с помощью специальных комментариев.
Для решения данной проблемы, ведется разработка специализированного банка знаний о преобразованиях программ (СБкЗ_ПП) [2].
Все подсистемы СБкЗ_ПП работают с программами, представленными в виде модели структурной программы (МСП) [3], содержащаяся в реляционной БД. МСП описывается в терминах модуля, который представляет собой необогащенную систему логических соотношений с параметрами. Язык грамматики КУ для реструктурирующих преобразований основан на языке грамматики КУ для классических преобразований [3], но дополнен терминами, необходимыми для описания зависимостей в циклах.
При реструктурирующих преобразованиях одной из основных проверок является проверка итерационной зависимости операторов присваивания в теле цикла. Для описания данного отношения между операторами в грамматику КУ введено новое отношение: g - итерационная зависимость. Данное отношение сопоставляет истину двум операторам и циклу, если первый оператор зависит итерационно от второго в теле данного цикла, и ложь в противном случае. Алгоритм проверки данного отношения:
1. Если оператор X1 является частью последовательности операторов из тела цикла Y, то перейти к 2, иначе к 4.
2. Если пересечение аргументного множества X1 с результатом X2 есть пустое множество, то переход к 4, иначе к 2.1.
2.1. Если пересечение аргументного множества X1 с результатом X2 содержит индексные переменные, тогда перейти к 2.1.1, иначе к 2.2.
2.1.1. Если в индексных переменных пересечения присутствуют переменные из условия цикла Y, то перейти к 3, иначе к 2.2.
2.2. Если оператор X1 предшествует оператору X2, то перейти к 4, иначе к 3.
3. Формула истинна. Конец алгоритма.
4. Формула ложна. Конец алгоритма.
Для выполнения алгоритма поиска УЭ и проверки КУ, описанного в работе [4], необходимо построить карту раскраски МСП: рМСП = {Ci}, i=1,…,n – набор цветов. Каждый цвет Ci это четвёрка <НО, ИП, Ф, нФ>, где НОi – индивидуальный номер оператора описания переменной (FragClass), ИПi – имя переменной, Фi – множество фрагментов МСП i-го цвета, нФi – «негатив» Фi, т. е. множество фрагментов МСП i-го цвета, временно исключёнными из Фi в процессе работы алгоритма.
Работа выполнена при финансовой поддержке ДВО РАН, инициативный научный проект «Интернет-система управления информацией о преобразованиях программ».
Список литературы
1. , Воеводин Вл. В. Параллельные вычисления. - СПб.: БХВ_Петербург, 20с.
2. , Князева -система управления информацией о преобразованиях программ // Информационные технологии, 2007. №1. С. 42-46. ISSN .
3. , , Купневич онтологии предметной области "Оптимизация последовательных программ". Ч.1. Термины для описания объекта оптимизации // НТИ. Сер. 2, 2002. № 12. С. 23-28.
4. , Маевский контекстных условий преобразований программ и поиск участков экономии в системе преобразований программ // Информационные технологии, 2007.
