January 27th, 2010

glider

Апдейт по поводу полиэдральной модели

Походу, state of the art работы насчет полиэдральной модели сводятся к тому, что:
  1. Зависимости между стейтментами гнезда циклов проверяем PipLib-ом.
  2. Строим множество всех планов обхода индексного пространства, которые представляют собой линейное преобразование плана из программы. Из них валидными являются только те, которые сохраняют зависимости. Для установления последнего факта юзаем лемму Фаркаша в аффинной форме и PipLib.
  3. ???
  4. PROFIT Генерим код из найденного плана обхода алгоритмом аля Cloog. Ну или представляем публике свой алгоритм, который в 0.001% случаев генерит на один if меньше, чем Cloog.

Я прямо долго не мог понять, почему все это не складывается в целостную картину. Догнал только, когда все написал на бумажке. Пункт #3 - задание метрики на множестве планов обхода и поиск плана по этой метрике, он же самая суть всего происходящего, обычно стыдливо прячет свою тривиальность за кучей формул в пунктах 1, 2 и 4. У кого-то индексное пространство тупо тайлится блоками размером с объем кэша, у кого-то метрика суть количество данных, которые нужно передать между тайлами, у кого-то вообще какие-то эвристики. Никакой магии. Но и совершенно никакой пользы для GPGPU в моделировании таких важных вещей как аллокация регистров и коалесцирование. Блин...

Upd. Похоже, все обстоит именно так, как я понял. Вот выдержка из диссера одного из исследователей университета Огайо (в этом универе вообще весьма неслабая школа по ресерчу полиэдральной модели циклов). Диссер написан в 2008м году и, по моим знаниям, является самой свежей работой на ниве автоматической параллелизации гнезд циклов. Итак:

The three major phases of an optimizer for parallelism and locality are:
1. Static analysis: Computing affine dependences for an input source program
2. Automatic transformation: Computing the transformations automatically
3. Code generation: Generating the new nested loop code under the computed transformations

As explained in Chapter 1, the first and last steps are currently quite stable, while no scalable and practical approach exists for the middle step that works for all polyhedral input or for input that the first and last steps are known to be quite advanced for. This chapter deals with the theory for the key middle step: automatic transformation, which is often considered synonymous with automatic parallelization.