К автоматическому порождению программ трафаретных вычислений с улучшенной временной локальностью

Трафаретные (stencil) алгоритмы широко используются в задачах математического моделирования на регулярных сетках, эволюции клеточных автоматов (типа игры «жизнь»), обработки изображений, анализа последовательностей и т.п. Такие алгоритмы хорошо параллелятся, но обычные подходы к распараллеливанию имеют низкую временную локальность, что ограничивает их масштабируемость. Избавление от этого недостатка возможно при использовании различных схем переупорядочения обработки точек, когда пространство разбивается на небольшие области, помещающиеся в кэш, в которых удается продвинутся сразу на несколько итераций. Однако, такие схемы трудно программируются и отлаживаются. Есть несложный метод пирамид, но он плохо масштабируется, поскольку влечет дублирование вычислений.
Наш подход состоит в использовании более сложных схем переупорядочения без дублирования, для которых код может генерироваться автоматически из относительно несложной спецификации схемы. При этом сами схемы задаются путем назначения функций распределения вычислительных узлов по пространству и времени. В этой статье излагается подход, и рассматриваются на простом примере различные варианты кода, порождаемые по различным функциям распределения.