Итерационные петли трафарета - Iterative Stencil Loops

Форма 7-точечного 3D- трафарета в стиле фон Неймана .

Итерационные циклы шаблонов (ISL) - это класс решений для обработки числовых данных, которые обновляют элементы массива в соответствии с некоторым фиксированным шаблоном, который называется шаблоном. Чаще всего они используются при компьютерном моделировании , например, для вычислительной гидродинамики в контексте научных и инженерных приложений. Другие известные примеры включают решение уравнений в частных производных , ядро Якоби , метод Гаусса – Зейделя , обработку изображений и клеточные автоматы . Регулярная структура массивов отличает методы трафарета от других методов моделирования, таких как метод конечных элементов . Большинство конечно-разностных кодов, которые работают с регулярными сетками, могут быть сформулированы как ISL.

Определение

ISL выполняют последовательность разверток (называемых временными шагами) по заданному массиву. Обычно это 2- или 3-мерная регулярная сетка. Элементы массивов часто называют ячейками. На каждом временном шаге обновляются все элементы массива. Новое значение каждой ячейки вычисляется с использованием соседних элементов массива в фиксированном шаблоне (трафарете). В большинстве случаев граничные значения остаются неизменными, но в некоторых случаях (например, коды LBM ) их также необходимо отрегулировать во время вычислений. Поскольку шаблон для каждого элемента один и тот же, шаблон доступа к данным повторяется.

Более формально мы можем определить ISL как 5-кортеж со следующим значением: ${\ displaystyle (I, S, S_ {0}, s, T)}$

• ${\ Displaystyle I = \ prod _ {я = 1} ^ {k} [0, \ ldots, n_ {i}]}$ - индексный набор. Он определяет топологию массива.
• ${\ displaystyle S}$ - это (не обязательно конечный) набор состояний, одно из которых может принимать каждая ячейка на любом заданном временном шаге.
• ${\ Displaystyle S_ {0} \ двоеточие \ mathbb {Z} ^ {k} \ to S}$ определяет начальное состояние системы в момент времени 0.
• ${\ Displaystyle s \ in \ prod _ {я = 1} ^ {l} \ mathbb {Z} ^ {k}}$ является самим трафаретом и описывает фактическую форму окрестности. В трафарете есть элементы. ${\ displaystyle l}$
• ${\ Displaystyle T \ двоеточие S ^ {l} \ to S}$ - это функция перехода, которая используется для определения нового состояния ячейки в зависимости от ее соседей.

Поскольку I является k -мерным целочисленным интервалом, массив всегда будет иметь топологию конечной регулярной сетки. Массив также называется пространством моделирования, и отдельные ячейки идентифицируются своим индексом . Шаблон представляет собой упорядоченный набор относительных координат. Теперь мы можем получить для каждой ячейки набор индексов ее соседей ${\ displaystyle c \ in I}$${\ displaystyle l}$${\ displaystyle c}$${\ displaystyle I_ {c}}$

${\ Displaystyle I_ {c} = \ {j \ mid \ exists x \ in s: j = c + x \} \,}$

Их состояния задаются отображением кортежа в соответствующий набор состояний , где определяется следующим образом: ${\ displaystyle I_ {c}}$${\ Displaystyle N_ {я} (с)}$${\ displaystyle N_ {i} \ двоеточие I \ to S ^ {l}}$

${\ displaystyle N_ {i} (c) = (s_ {1}, \ ldots, s_ {l}) {\ text {with}} s_ {j} = S_ {i} (I_ {c} (j)) \,}$

Это все, что нам нужно для определения состояния системы для следующих временных шагов с помощью : ${\ Displaystyle S_ {я + 1} \ двоеточие \ mathbb {Z} ^ {k} \ to S}$${\ Displaystyle я \ в \ mathbb {N}}$

${\ Displaystyle S_ {я + 1} (с) = {\ begin {case} T (N_ {i} (c)), & c \ in I \\ S_ {i} (c), & c \ in \ mathbb { Z} ^ {k} \ setminus I \ end {case}}}$

Обратите внимание, что это определено, а не только, поскольку также необходимо установить граничные условия. Иногда элементы могут быть определены путем сложения векторов по модулю размерности пространства моделирования для реализации тороидальных топологий: ${\ displaystyle S_ {i}}$${\ displaystyle \ mathbb {Z} ^ {k}}$${\ displaystyle I}$${\ displaystyle I_ {c}}$

${\ Displaystyle I_ {c} = \ {j \ mid \ exists x \ in s: j = ((c + x) \ mod (n_ {1}, \ ldots, n_ {k})) \}}$

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

Пример: итерация Якоби в 2D

Зависимости данных выбранной ячейки в 2D-массиве.

Чтобы проиллюстрировать формальное определение, мы посмотрим, как можно определить двумерную итерацию Якоби . Функция обновления вычисляет среднее арифметическое четырех соседей ячейки. В этом случае мы начинаем с начальным решением 0. Левая и правая границы зафиксированы на 1, а верхняя и нижняя границы установлены на 0. После достаточного количества итераций система сходится к седловидной форме.

${\ displaystyle {\ begin {align} I & = [0, \ ldots, 99] ^ {2} \\ S & = \ mathbb {R} \\ S_ {0} &: \ mathbb {Z} ^ {2} \ в \ mathbb {R} \\ S_ {0} ((x, y)) & = {\ begin {cases} 1, & x <0 \\ 0, & 0 \ leq x <100 \\ 1, & x \ geq 100 \ end {case}} \\ s & = ((0, -1), (- 1,0), (1,0), (0,1)) \\ T & \ двоеточие \ mathbb {R} ^ {4 } \ to \ mathbb {R} \\ T ((x_ {1}, x_ {2}, x_ {3}, x_ {4})) & = 0,25 \ cdot (x_ {1} + x_ {2} + х_ {3} + х_ {4}) \ конец {выровнено}}}$

${\ displaystyle S_ {0}}$

${\ displaystyle S_ {200}}$

${\ displaystyle S_ {400}}$

${\ displaystyle S_ {600}}$

${\ displaystyle S_ {800}}$

${\ displaystyle S_ {1000}}$

2D итерация Якоби на массиве ${\ displaystyle 100 ^ {2}}$

Трафареты

Форма окрестности, используемой во время обновлений, зависит от самого приложения. Наиболее распространенными трафаретами являются 2D или 3D версии окрестностей фон Неймана и Мура . В приведенном выше примере используется двухмерный шаблон фон Неймана, в то время как коды LBM обычно используют его трехмерный вариант. «Игра жизни» Конвея использует двухмерную окрестность Мура. Тем не менее, можно найти и другие шаблоны, такие как 25-точечный шаблон для распространения сейсмических волн.

9-точечный 2D-трафарет

5-точечный 2D-трафарет

7-точечный 3D-трафарет

25-точечный 3D-трафарет

Подборка трафаретов, используемых в различных научных приложениях.

Проблемы реализации

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

Библиотеки

В связи с важностью ISL для компьютерного моделирования и их высокими вычислительными требованиями, существует ряд усилий, направленных на создание повторно используемых библиотек для поддержки ученых в выполнении вычислений на основе трафаретов. Библиотеки в основном занимаются распараллеливанием, но могут также решать другие задачи, такие как ввод-вывод, управление и контрольные точки . Их можно классифицировать по их API.

Библиотеки на основе патчей

Это традиционный дизайн. Библиотека управляет набором n- мерных скалярных массивов, к которым пользовательская программа может обращаться для выполнения обновлений. Библиотека обрабатывает синхронизацию границ (дублированная зона-призрак или ореол). Преимущество этого интерфейса заключается в том, что пользовательская программа может перебирать массивы, что упрощает интеграцию унаследованного кода. Недостатком является то, что библиотека не может обрабатывать блокировку кеша (так как это должно выполняться в циклах) или обертывание API-вызовов для ускорителей (например, через CUDA или OpenCL). Реализации включают Cactus , среду решения физических задач и waLBerla .

Библиотеки на основе ячеек

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

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

• Расширенная библиотека моделирования
• Метод конечных разностей
• Компьютерное моделирование
• Пятиточечный трафарет
• Прыжки по трафарету
• Трафарет (численный анализ)

Рекомендации

внешняя ссылка

• Physis
• LibGeoDecomp
• WaLBerla