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

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

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

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

константное   число   n   =   100  ;  int   i  ,   j  ,   a  [  n  ][  n  ];  для   (  я   знак равно   1  ;   я   <   п  ;   я  ++  )   {    для   (  j   знак равно   1  ;   j   <   (  я   +   2  )   &&   j   <   n  ;   j  ++  )   {      а  [  я  ][  j  ]   =   а  [  я   -   1  ][  j  ]   +   а  [  я  ][  j   -   1  ];    }  }

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

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

а  [  я   -   j  ][  j  ]   =   а  [  я   -   j   -   1  ] [  j  ]   +   а  [  я   -   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   знак равно   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  ;              источник  [  я  ][  j  ]   знак равно   (  v   <   0  )   ?   0   :   (  v   <   255  )   ?   в   :   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  );           для   (  п   знак равно   pmin  ;   п   <=   pmax  ;   п   +=   2  )   {               int   я   знак равно   п  ;               интервал   j   знак равно   (  т   -   п  )   /   2  ;               int   v   =   источник  [  i  ][  j  ];               если   (  я   >   0  )                 v   -=   ERR  (  я   -   1  ,   j  )   /   2  ;               если   (  j   >   0  )                 v   -=   ERR  (  i  ,   j   -   1  )   /   4  ;               если   (  j   >   0   &&   я   <   w   -   1  )                 v   -=   ERR  (  я   +   1  ,   j   -   1  )   /   4  ;               dst  [  я  ][  j  ]   знак равно   (  v   <   128  )   ?   0   :   255  ;               источник  [  я  ][  j  ]   знак равно   (  v   <   0  )   ?   0   :   (  v   <   255  )   ?   в   :   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 для высокоуровневой оптимизации циклов и локальности данных
Массачусетского технологического института Многогранная структура Тирамису .