Реализация индексного анализа для деревьев циклов любого вида сложности Выполнил : студент 818 гр. Юдин Павел Научный руководитель : к. т. н. Муханов Л. Е.

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

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

Основные понятия Индексный анализ – анализ, проводящийся над индексами массивов в определенном цикле, для выявления зависимостей между конкретными операциями на разных итерациях Дерево циклов – структура, выражающая отношения вложенности циклов Гнездо циклов – структура, содержащая информацию об одной ветви в дереве циклов

Распараллеливание циклов Межитерационная цикловая зависимость for (i=0;i

Проблематика Невозможность анализировать операции, принадлежащие разным гнездам for(i=0;i

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

Математическая постановка Доказать независимость при эквивалентности множеств A и В Доказать независимость вне зависимости от A == ВНовая версия: Исходная версия:

Представление индекса массива Внутреннее представление mov 10 => Vs 3 mov 4 => Vs 0 mul Vs 0, Vs 1 => Vs 2 add Vs 2, Vs 3 => Vs 4 load a[Vs 4 ] PS- форма : 4*(Vs 1 +10) 104Vs 1 mul add ld Граф потока данных

Формирование уравнений для анализа зависимостей Линейная форма представления PS- формы : Формирование неравенств : for(i=0;i

Методы решения 1. « одно ограничение на переменную » - не охватывает все случаи 2. Ациклический - не охватывает все случаи 3. Простая проверка остатка цикла - не охватывает все случаи 4. Фурье - Моцкина - двойная экспоненциальная сложность 5. Симплекс метод - охватывает все случаи, экспоненциальная сложность

Цикловой индексный анализ ( используемый в МЦСТ алгоритм ) Создание пар операций запись / запись и чтение / запись Операции нужной формы ? Пара зависит от индуктивности ? Вызов решателя, Симплекс метод Задаем матрицы уравнений Операции одного гнезда ? Независимы ? Есть еще пары ? Нельзя определить независимость Отсутствие зависимости нет да вход

Цикловой индексный анализ ( улучшенный алгоритм ) Создание пар операций запись / запись и чтение / запись Операции нужной формы ? Пара зависит от индуктивности ? Вызов решателя, Симплекс метод Задаем матрицы уравнений Независимы ? Есть еще пары ? Нельзя определить независимость Отсутствие зависимости нет да - Улучшенные стадии вход

Экспериментальные результаты Задача wupwise168 из пакета тестов Spec2000 Время параллельного выполнения задачи сократилось на 14%

Результаты Разобраны существующие методы анализа межитерационных цикловых зависимостей Разобрана программная реализация существующих методов Реализован анализ для деревьев циклов любого вида сложности Получены экспериментальные результаты на задаче wupwise168, пакета Spec2000 Улучшения внедрены в компилятор