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

• Автор: Арапбаев, Русланбек Нурмаматович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Новосибирск
• Количество страниц: 116 с. : ил.

ВВЕДЕНИЕ

1. АНАЛИЗ ЗАВИСИМОСТЕЙ: ТЕСТЫ НА ЗАВИСИМОСТЬ ПО

ДАННЫМ

1Л. Основные понятия и определения

1Л Л. Модель программы

1Л .2. Определение зависимостей по данным

1Л .3. Граф зависимостей по данным

1 Л.4. Анализ зависимостей по данным

1.2. Основные методы

1.2.1. НОД-тест

1.2.2. Тест Банержи

1.2.3. Метод исключения переменных Фурье-Моцкина
1.3. Расширенные методы
1.3.1 Приближенные тесты
Обобщенный НОД-тест
/Отест
1-тест (Интервальный тест)
1.3.2. Точные тесты
Роуег-тест
Омега-тест

1.4. Другие тесты на зависимость по данным
1.5. Анализ зависимостей по данным для многомерных массивов
1.5.1. Постановка проблемы
1.5.2. Модифицированный Я
1.5.3. Алгоритм
1.5.4. Сравнение результатов
1.5.5. Временная сложность
Выводы по главе

2. АНАЛИЗ ЗАВИСИМОСТЕЙ ПО ДАННЫМ: СТРАТЕГИИ
ТЕСТИРОВАНИЯ
2.1. Существующие алгоритмы анализа зависимостей по данным
2.1.1. Дельта-тест
ZIV-тест
SIV-тест
MIV-тест
2.1.2. Эпсилон-тест
Эпсилон-Омега тест
2.1.3. Алгоритм Майдана
SVPC-тест (“single variable per constraint”)
Acyclic-тест
LR-тест (“ loop residue”)
2.1.4. К-тест
Организация интеллектуального подхода
2.2. Новая стратегия применений тестов на зависимость
2.2.1. Библиотека тестов на зависимость по данным
Одномерные тесты
Многомерные тесты
2.2.2 Основные результаты существующих исследований
2.2.3. Случаи, повышающие точность тестов на зависимость
2.2.4. Алгоритм стратегии
2.2.5. Временная сложность
Выводы по главе
3. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ
3.1. Программный комплекс для анализа зависимостей по данным
3.1.1. Реализация библиотеки тестов на зависимость и алгоритма
новой стратегии
3.1.2. Система SUIF

3.1.3. Прототип распараллеливающего компилятора на основе новой стратегии тестирования на зависимость и библиотек системы SUIF
3.2. Экспериментальное сравнение результатов
3.2.1. Системная среда
3.2.2. Сравнение результатов
3.2.3. Сравнение результатов на экспериментальных примерах
3.2.4. Время выполнения
3.2.5. Статистические данные Новой стратегии
3.3. Индексный анализ зависимостей по данным в Sisal -программах
3.3.1. Язык функционального программирования SISAL
3.3.2. Промежуточное представление IR1
3.3.3. Построение алгоритма индексного анализа зависимостей по
данным
Поиск гнезд циклов, для которых возможен индексный анализ.97 Поиск индексных переменных и подготовка данных гнезда
циклов
Подготовка данных для анализа существования зависимости
двух операций обращения к массиву в цикле
Особенности используемого алгоритма анализа зависимостей..99 Интерпретация и использование результатов анализа в целях
оптимизации
Выводы по главе
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА

Известно много результатов, относящихся к анализу зависимостей по данным и оставшихся- за пределами настоящей диссертационной работы. Сюда относятся, например, оценки числа решений уравнения зависимости [60], вычисление УВ-зависимостей [40; 62; 96], а также обширная область межпроцедурного анализа в контексте анализа зависимостей по данным [4; 28; 51; 102]. Сюда же примыкают исследования,, по зависимостям по управлению [3; 41; 42] и теоретико-графовым промежуточным
представлениям программ, где совместно выступают зависимости-по данным, и по управлению.
1.5. Анализ зависимостей по данным, для многомерных
массивов
1.5.1. Постановка проблемы
Общий' подход состоит в индивидуальном' тестировании уравнений (тестирование “индекс-за-индексом”) из (3) вместо проверки, существования решения системы в целом. Однако система уравнений зависимости может не иметь решения даже- в том случае, когда имеются- решения в каждом из отдельных уравнений.
Если потенциальная зависимость включает сцепленные индексы, то для её разрушения, необходимо одновременное рассмотрение индексов .многомерного массива. Заметим; что среди всего множества тестов лишь некоторые из них пригодны для работы со-сцепленными индексами, например, обобщенный НОД-тест и тесты на основе линейного и целочисленного программирования; целочисленной- тест, Ро"уег-тест, Омега-тест,, и др. В- первом даётся ответ на вопрос о существовании целочисленного решения, но не учитываются ограничения- на область изменения переменных. Поэтому обобщенный НОД-тест не может доказать существование зависимости, но. полезен для- ее опровержении. Тесты, использующие дорогостоящие методы, не эффективны