Модель многогранника

Многогранная модель (также называемая методом многогранника ) — это математическая основа для программ, выполняющих большое количество операций — слишком большое, чтобы их можно было явно перечислить, — поэтому требующее компактного представления. Программы с вложенными циклами являются типичным, но не единственным примером, и наиболее часто эта модель используется для оптимизации гнезда циклов при оптимизации программ . Метод многогранников рассматривает каждую итерацию цикла внутри вложенных циклов как точки решетки внутри математических объектов, называемых многогранниками , выполняет аффинные преобразования или более общие неаффинные преобразования, такие как мозаика на многогранниках, а затем преобразует преобразованные многогранники в эквивалентные, но оптимизированные (в зависимости от целевая цель оптимизации), вложение циклов посредством сканирования многогранников.

Простой пример

Рассмотрим следующий пример, написанный на C :

const int n = 100;
int i, j, a[n][n];

for (i = 1; i < n; i++) {
  for (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], уже доступен. Следовательно, этот код не может быть распараллелен или конвейеризирован в том виде, в каком он сейчас написан.

Применение модели многогранника с аффинным преобразованием $(i',\,j')=(i+j,\,j)$ и соответствующее изменение границ преобразуют приведенные выше вложенные циклы в:

a[i - j][j] = a[i - j - 1][j] + a[i - j][j - 1];

В этом случае ни одна итерация внутреннего цикла не зависит от результатов предыдущей итерации; весь внутренний цикл может выполняться параллельно. Действительно, учитывая a(i, j) = a[i-j][j] затем a(i, j) зависит только от a(i - 1, x), с $x\in \{j-1,\,j\}$ . (Однако каждая итерация внешнего цикла зависит от предыдущих итераций.)

Подробный пример

Следующий код 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] графически, как на схеме справа.

#define ERR(x, y) (dst[x][y] - src[x][y])

void dither(unsigned char** src, unsigned char** dst, int w, int h)
{
    int i, j;
    for (j = 0; j < h; ++j) {
        for (i = 0; i < w; ++i) {
            int v = src[i][j];
            if (i > 0)
                v -= ERR(i - 1, j) / 2;
            if (j > 0) {
                v -= ERR(i, j - 1) / 4;
                if (i < w - 1)
                    v -= ERR(i + 1, j - 1) / 4;
            }
            dst[i][j] = (v < 128) ? 0 : 255;
            src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255;
        }
    }
}

Выполнение аффинного преобразования $(p,\,t)=(i,\,2j+i)$ на исходной диаграмме зависимостей дает нам новую диаграмму, которая показана на следующем изображении. Затем мы можем переписать код для зацикливания p и t вместо i и j, получив следующую «перекошенную» процедуру.

 void dither_skewed(unsigned char **src, unsigned char **dst, int w, int h)  
 {
     int t, p;
     for (t = 0; t < (w + (2 * h)); ++t) {
         int pmin = max(t % 2, t - (2 * h) + 2);
         int pmax = min(t, w - 1);
         for (p = pmin; p <= pmax; p += 2) {
             int i = p;
             int j = (t - p) / 2;
             int v = src[i][j];
             if (i > 0)
               v -= ERR(i - 1, j) / 2;
             if (j > 0)
               v -= ERR(i, j - 1) / 4;
             if (j > 0 && i < w - 1)
               v -= ERR(i + 1, j - 1) / 4;
             dst[i][j] = (v < 128) ? 0 : 255;
             src[i][j] = (v < 0) ? 0 : (v < 255) ? v : 255;
         }
     }
 }

См. также

Внешние ссылки и ссылки

«Базовый метод многогранника» , учебник Мартина Грибла, содержащий диаграммы приведенного выше примера псевдокода.
«Генерация кода в модели многогранника» (1998). Мартин Грибль, Кристиан Ленгауэр и Сабина Ветцель
«Генератор многогранного кода CLooG»
«CodeGen+: сканирование Z-многогранников» ^{[ постоянная мертвая ссылка ]}
PoCC: Коллекция многогранных компиляторов
PLUTO — автоматический распараллеливатель и оптимизатор локальности для вложений аффинных циклов.
- Бондугула, Удай; Хартоно, Альберт; Рамануджам, Дж.; Садаяппан, П. (1 января 2008 г.). «Практический автоматический многогранный параллелизатор и оптимизатор локальности». Материалы 29-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . ПЛДИ '08. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 101–113. дои : 10.1145/1375581.1375595 . ISBN 9781595938602 . S2CID 7086982 .
Polyhedral.info — сайт, собирающий информацию о составлении многогранников.
Polly — LLVM Framework для высокоуровневой оптимизации циклов и локальности данных
Массачусетского технологического института Многогранная структура Тирамису .