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

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

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

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

Распараллеливание циклов
Межитерационная цикловая зависимость
for (i=0;i<10;i++)
{
a[i+1]=a[i]+5;
}
for(i=0;i<10;i++)
{
a[i]=a[i]+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; }

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

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

Представление индекса массива
Внутреннее представление
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
Граф потока данных

Формирование уравнений для анализа зависимостей
Линейная форма представления 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

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

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

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

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