Многогранная модель
Многогранная модель (также называемая методом многогранников ) — это математическая основа для программ, которые выполняют большое количество операций — слишком большое, чтобы их можно было явно перечислить — поэтому требуется компактное представление. Программы с вложенными циклами являются типичным, но не единственным примером, и наиболее часто эта модель используется для оптимизации вложенных циклов в оптимизации программ . Многогранный метод рассматривает каждую итерацию цикла во вложенных циклах как точки решетки внутри математических объектов, называемых многогранниками , выполняет аффинные преобразования или более общие неаффинные преобразования, такие как мозаика.на многогранниках, а затем преобразует преобразованные многогранники в эквивалентные, но оптимизированные (в зависимости от целевой цели оптимизации) вложения циклов посредством сканирования многогранников.
Существенная проблема с этим кодом заключается в том, что каждая итерация внутреннего цикла on a[i][j]требует, чтобы результат предыдущей итерации a[i][j - 1]уже был доступен. Поэтому этот код не может быть распараллелен или конвейеризирован в том виде, в котором он написан в настоящее время.
Применение многогранной модели с аффинным преобразованием и соответствующим изменением границ преобразует вложенные циклы выше в:
В этом случае никакая итерация внутреннего цикла не зависит от результатов предыдущей итерации; весь внутренний цикл может выполняться параллельно. (Однако каждая итерация внешнего цикла зависит от предыдущих итераций.)
Следующий код 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до перекоса цикла . Красная точка соответствует src[1][0]; розовая точка соответствует src[2][2].