гр. Юдин Павел
Научный руководитель: к.т.н. Муханов Л.Е.
- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Реализация индексного анализа для деревьев циклов любого вида сложности презентация
Содержание
- 1. Реализация индексного анализа для деревьев циклов любого вида сложности
- 2. Актуальность Увеличение производительности вычислительных комплексов. Многоядерные архитектуры
- 3. Актуальность В большинстве вычислительных задач основное время
- 4. Основные понятия Индексный анализ – анализ, проводящийся
- 5. Распараллеливание циклов Межитерационная цикловая зависимость for (i=0;i
- 6. Проблематика Невозможность анализировать операции, принадлежащие разным гнездам for(i=0;i
- 7. Постановка задачи Разбор существующих методов анализа межитерационных
- 8. Математическая постановка Доказать независимость при
- 9. Представление индекса массива
- 10. Формирование уравнений для анализа зависимостей Линейная форма представления PS-формы: Формирование неравенств: for(i=0;i
- 11. Методы решения 1. «одно ограничение на переменную»
- 12. Цикловой индексный анализ (используемый
- 13. Цикловой индексный анализ (улучшенный
- 14. Экспериментальные результаты Задача wupwise168 из пакета тестов
- 15. Результаты Разобраны существующие методы анализа межитерационных цикловых
Актуальность Увеличение производительности вычислительных комплексов. Многоядерные архитектуры Значительное количество существующих приложений реализовано для последовательного исполнения Автоматическое распараллеливание позволяет повышать производительность приложений без изменений в исходном коде
Слайд 1Реализация индексного анализа
для деревьев циклов
любого вида сложности
Выполнил: студент 818
Слайд 2Актуальность
Увеличение производительности вычислительных комплексов. Многоядерные архитектуры
Значительное количество существующих приложений реализовано
для последовательного исполнения
Автоматическое распараллеливание позволяет повышать производительность приложений без изменений в исходном коде
Автоматическое распараллеливание позволяет повышать производительность приложений без изменений в исходном коде
Слайд 3Актуальность
В большинстве вычислительных задач основное время тратится на вычисления, которые содержатся
внутри циклов
Автоматическое распараллеливание нацелено на работу с циклами
Автоматическое распараллеливание нацелено на работу с циклами
Слайд 4Основные понятия
Индексный анализ – анализ, проводящийся над индексами массивов в определенном
цикле, для выявления зависимостей между конкретными операциями на разных итерациях
Дерево циклов – структура, выражающая отношения вложенности циклов
Гнездо циклов – структура, содержащая информацию об одной ветви в дереве циклов
Дерево циклов – структура, выражающая отношения вложенности циклов
Гнездо циклов – структура, содержащая информацию об одной ветви в дереве циклов
Слайд 5Распараллеливание циклов
Межитерационная цикловая зависимость
for (i=0;i
{
a[i+1]=a[i]+5;
}
for(i=0;i<10;i++)
{
a[i]=a[i]+5;
}
Цикловой индексный анализ позволяет определить отсутствие зависимостей
a[i+1]=a[i]+5;
}
for(i=0;i<10;i++)
{
a[i]=a[i]+5;
}
Цикловой индексный анализ позволяет определить отсутствие зависимостей
существует зависимость
отсутствует зависимость
Слайд 6Проблематика
Невозможность анализировать операции, принадлежащие разным гнездам
for(i=0;i
for(k=0;k<1000;k++)
a[i][k]+=1;
for(j=0;j<1000;j++)
a[i][j]+=1;
}
a[i][k]+=1;
for(j=0;j<1000;j++)
a[i][j]+=1;
}
Слайд 7Постановка задачи
Разбор существующих методов анализа межитерационных цикловых зависимостей
Разбор программной реализации существующих
методов
Реализация анализа для деревьев циклов любого вида сложности
Реализация анализа для деревьев циклов любого вида сложности
Слайд 8Математическая постановка
Доказать независимость при эквивалентности множеств A и В
Доказать независимость вне
зависимости от A == В
Новая версия:
Исходная версия:
Слайд 9
Представление индекса массива
Внутреннее представление
mov 10
=> Vs3
mov 4 => Vs0
mul Vs0, Vs1 => Vs2
add Vs2, Vs3 => Vs4
load a[Vs4]
mov 4 => Vs0
mul Vs0, Vs1 => Vs2
add Vs2, Vs3 => Vs4
load a[Vs4]
PS- форма:
4*(Vs1+10)
10
4
Vs1
mul
add
ld
Граф потока данных
Слайд 10Формирование уравнений для анализа зависимостей
Линейная форма представления PS-формы:
Формирование неравенств:
for(i=0;i
a[i]=a[i+10]+5;
}
}
0≤ i <10
0≤ j <10
i=j+10
c0 + c1*x1 + c2*x2 + … + cn*xn
Слайд 11Методы решения
1. «одно ограничение на переменную»
-не охватывает все случаи
2. Ациклический
-не охватывает
все случаи
3. Простая проверка остатка цикла
-не охватывает все случаи
4. Фурье-Моцкина
-двойная экспоненциальная сложность
5. Симплекс метод
-охватывает все случаи, экспоненциальная сложность
3. Простая проверка остатка цикла
-не охватывает все случаи
4. Фурье-Моцкина
-двойная экспоненциальная сложность
5. Симплекс метод
-охватывает все случаи, экспоненциальная сложность
Слайд 14Экспериментальные результаты
Задача wupwise168
из пакета тестов Spec2000
Время параллельного
выполнения задачи
сократилось на 14%
Слайд 15Результаты
Разобраны существующие методы анализа межитерационных цикловых зависимостей
Разобрана программная реализация существующих методов
Реализован
анализ для деревьев циклов любого вида сложности
Получены экспериментальные результаты на задаче wupwise168, пакета Spec2000
Улучшения внедрены в компилятор
Получены экспериментальные результаты на задаче wupwise168, пакета Spec2000
Улучшения внедрены в компилятор
