'

Реализация индексного анализа для деревьев циклов любого вида сложности

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

Распараллеливание циклов Межитерационная цикловая зависимость for (i=0;i<10;i++) { a[i+1]=a[i]+5; } for(i=0;i<10;i++) { a[i]=a[i]+5; } Цикловой индексный анализ позволяет определить отсутствие зависимостей существует зависимость отсутствует зависимость


Слайд 5

Проблематика Невозможность анализировать операции, принадлежащие разным гнездам for(i=0;i<1000;i++) { for(k=0;k<1000;k++) a[i][k]+=1; for(j=0;j<1000;j++) a[i][j]+=1; }


Слайд 6

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


Слайд 7

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


Слайд 8

Представление индекса массива Внутреннее представление mov 10 => Vs3 mov 4 => Vs0 mul Vs0, Vs1 => Vs2 add Vs2, Vs3 => Vs4 load a[Vs4] PS- форма: 4*(Vs1+10) 10 4 Vs1 mul add ld Граф потока данных


Слайд 9

Формирование уравнений для анализа зависимостей Линейная форма представления PS-формы: Формирование неравенств: for(i=0;i<10;i++) { a[i]=a[i+10]+5; } 0? i <10 0? j <10 i=j+10 c0 + c1*x1 + c2*x2 + … + cn*xn


Слайд 10

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


Слайд 11

Цикловой индексный анализ (используемый в МЦСТ алгоритм) нет нет нет нет нет да да да да да вход


Слайд 12

Цикловой индексный анализ (улучшенный алгоритм) нет нет нет нет да да да да - Улучшенные стадии вход


Слайд 13

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


Слайд 14

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


×

HTML:





Ссылка: