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

О физических моделях многогранников см. Модель многогранника.

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

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

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

  const int п = 100;  int я, j, а[п][п];  за (я = 1; я < п; я++) {    за (j = 1; j < (я + 2) && j < п; j++) {      а[я][j] = а[я - 1][j] + а[я][j - 1];    }  }

Основная проблема этого кода заключается в том, что каждая итерация внутреннего цикла на a [i] [j] требует, чтобы результат предыдущей итерации, a [i] [j - 1], уже доступны. Следовательно, этот код нельзя распараллелить или конвейерный как сейчас написано.

Применение модели многогранника с аффинным преобразованием и соответствующее изменение границ преобразует вложенные циклы выше в:

      а[я - j][j] = а[я - j - 1][j] + а[я - j][j - 1];

В этом случае итерация внутреннего цикла не зависит от результатов предыдущей итерации; весь внутренний цикл может выполняться параллельно. (Однако каждая итерация внешнего цикла зависит от предыдущих итераций.)

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

Зависимости src, перед перекос петли. Красная точка соответствует src [1] [0]; розовая точка соответствует SRC [2] [2].

Следующее C код реализует форму распределения ошибок дизеринг похожий на Дизеринг Флойда – Стейнберга, но модифицированный по педагогическим причинам. Двумерный массив src содержит час ряды ш пикселей, каждый пиксель имеет оттенки серого значение от 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])пустота дрожать(беззнаковый char** src, беззнаковый char** dst, int ш, int час){    int я, j;    за (j = 0; j < час; ++j) {        за (я = 0; я < ш; ++я) {            int v = src[я][j];            если (я > 0)                v -= ERR(я - 1, j) / 2;            если (j > 0) {                v -= ERR(я, j - 1) / 4;                если (я < ш - 1)                    v -= ERR(я + 1, j - 1) / 4;            }            dst[я][j] = (v < 128) ? 0 : 255;            src[я][j] = (v < 0) ? 0 : (v < 255) ? v : 255;        }    }}
Зависимости src, после перекоса петли. Элементы массива будут обрабатываться в порядке серый, красный, зеленый, синий, желтый ...

Выполнение аффинного преобразования на исходной диаграмме зависимостей дает нам новую диаграмму, которая показана на следующем изображении. Затем мы можем переписать код для выполнения цикла п и т вместо я и j, получив следующую "искаженную" процедуру.

 пустота dither_skewed(беззнаковый char **src, беззнаковый char **dst, int ш, int час)   {     int т, п;     за (т = 0; т < (ш + (2 * час)); ++т) {         int pmin = Максимум(т % 2, т - (2 * час) + 2);         int pmax = мин(т, ш - 1);         за (п = pmin; п <= pmax; п += 2) {             int я = п;             int j = (т - п) / 2;             int v = src[я][j];             если (я > 0)               v -= ERR(я - 1, j) / 2;             если (j > 0)               v -= ERR(я, j - 1) / 4;             если (j > 0 && я < ш - 1)               v -= ERR(я + 1, j - 1) / 4;             dst[я][j] = (v < 128) ? 0 : 255;             src[я][j] = (v < 0) ? 0 : (v < 255) ? v : 255;         }     } }

Смотрите также

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