Полиэдральная модель (также называемая методом политопа ) — это математическая структура для программ, которые выполняют большое количество операций — слишком большое, чтобы их можно было явно перечислить — поэтому требующее компактного представления. Программы с вложенными циклами являются типичным, но не единственным примером, и наиболее распространенное использование модели — оптимизация гнезда циклов в оптимизации программ . Полиэдральный метод рассматривает каждую итерацию цикла внутри вложенных циклов как точки решетки внутри математических объектов, называемых полиэдрами , выполняет аффинные преобразования или более общие неаффинные преобразования, такие как мозаика на политопах, а затем преобразует преобразованные политопы в эквивалентные, но оптимизированные (в зависимости от целевой цели оптимизации) гнезда циклов посредством сканирования полиэдров.
Рассмотрим следующий пример, написанный на языке C :
константа int n = 100 ; int i , j , a [ n ][ n ]; для ( i = 1 ; i < n ; i ++ ) { для ( j = 1 ; j < ( i + 2 ) && j < n ; j ++ ) { a [ i ][ j ] = a [ i - 1 ][ j ] + a [ i ][ j - 1 ]; } } Основная проблема этого кода заключается в том, что каждая итерация внутреннего цикла a[i][j]требует, чтобы результат предыдущей итерации, a[i][j - 1], был уже доступен. Поэтому этот код не может быть распараллелен или конвейеризирован в том виде, в котором он написан в настоящее время.
Применение модели многогранника с аффинным преобразованием и соответствующим изменением границ преобразует вложенные циклы, указанные выше, в:
а [ я - j ][ j ] = а [ я - j - 1 ][ j ] + а [ я - j ][ j - 1 ]; В этом случае ни одна итерация внутреннего цикла не зависит от результатов предыдущей итерации; весь внутренний цикл может быть выполнен параллельно. Действительно, если a(i, j) = a[i-j][j]то a(i, j)зависит только от a(i - 1, x), причем . (Однако каждая итерация внешнего цикла зависит от предыдущих итераций.)
src, до перекоса цикла . Красная точка соответствует src[1][0]; розовая точка соответствует src[2][2].Следующий код C реализует форму сглаживания распределения ошибок , похожую на сглаживание Флойда–Стейнберга , но измененную в педагогических целях. Двумерный массив srcсодержит hстроки wпикселей, каждый пиксель имеет значение градаций серого от 0 до 255 включительно. После завершения процедуры выходной массив dstбудет содержать только пиксели со значением 0 или 255. Во время вычисления ошибка сглаживания каждого пикселя собирается путем добавления ее обратно в массив src. (Обратите внимание, что srcи dstсчитываются и записываются во время вычисления; srcне только для чтения и dstне только для записи.)
Каждая итерация внутреннего цикла изменяет значения в src[i][j]на основе значений src[i-1][j], src[i][j-1]и src[i+1][j-1]. (Те же зависимости применяются к dst[i][j]. Для целей перекоса цикла мы можем рассматривать src[i][j]и dst[i][j]как один и тот же элемент.) Мы можем проиллюстрировать зависимости src[i][j]графически, как на диаграмме справа.
srcпосле перекоса цикла. Элементы массива будут обработаны в следующем порядке: серый, красный, зеленый, синий, желтый...Выполнение аффинного преобразования на исходной диаграмме зависимости дает нам новую диаграмму, которая показана на следующем изображении. Затем мы можем переписать код для цикла по и вместо и , получив следующую «перекошенную» процедуру.ptij
