Итерационные циклы шаблонов (ISL) - это класс решений для обработки числовых данных [1], которые обновляют элементы массива в соответствии с некоторым фиксированным шаблоном, называемым шаблоном. [2] Чаще всего они используются при компьютерном моделировании , например, для вычислительной гидродинамики в контексте научных и инженерных приложений. Другие известные примеры включают решения дифференциальных уравнений , [1] Якобите ядро, то метод Гаусса-Зейделя , [2] обработки изображений [1] и клеточные автоматы . [3]Регулярная структура массивов отличает методы трафарета от других методов моделирования, таких как метод конечных элементов . Большинство конечно-разностных кодов, которые работают с регулярными сетками, могут быть сформулированы как ISL.
Определение
ISL выполняют последовательность разверток (называемых временными шагами) по заданному массиву. [2] Обычно это 2- или 3-мерная регулярная сетка. [3] Элементы массивов часто называют ячейками. На каждом временном шаге обновляются все элементы массива. [2] Используя соседние элементы массива в фиксированном шаблоне (трафарете), вычисляется новое значение каждой ячейки. В большинстве случаев граничные значения остаются неизменными, но в некоторых случаях (например, коды LBM ) их также необходимо отрегулировать во время вычислений. Поскольку шаблон для каждого элемента одинаков, шаблон доступа к данным повторяется. [4]
Более формально мы можем определить ISL как 5-кортеж со следующим значением: [3]
- - это индексный набор. Он определяет топологию массива.
- - это (не обязательно конечный) набор состояний, одно из которых может принимать каждая ячейка на любом заданном временном шаге.
- определяет начальное состояние системы в момент времени 0.
- является самим трафаретом и описывает фактическую форму окрестности. Есть элементы в трафарете.
- - это функция перехода, которая используется для определения нового состояния ячейки в зависимости от ее соседей.
Поскольку I - k- мерный целочисленный интервал, массив всегда будет иметь топологию конечной регулярной сетки. Массив также называется пространством моделирования, и отдельные ячейки идентифицируются своим индексом.. Трафарет представляет собой упорядоченный наборотносительные координаты. Теперь мы можем получить для каждой ячейки набор индексов соседей
Их состояния задаются отображением кортежа в соответствующий набор состояний , где определяется следующим образом:
Это все, что нам нужно для определения состояния системы для следующих временных шагов. с участием :
Обратите внимание, что определяется на и не только на так как граничные условия также должны быть установлены. Иногда элементы может быть определен векторным сложением по модулю размерности пространства моделирования для реализации тороидальных топологий:
Это может быть полезно для реализации периодических граничных условий , которые упрощают определенные физические модели.
Пример: итерация Якоби в 2D
Чтобы проиллюстрировать формальное определение, мы посмотрим, как можно определить двумерную итерацию Якоби . Функция обновления вычисляет среднее арифметическое четырех соседей ячейки. В этом случае мы начинаем с начальным решением 0. Левая и правая границы зафиксированы на 1, а верхняя и нижняя границы установлены на 0. После достаточного количества итераций система сходится к седловидной форме.
Трафареты
Форма окрестности, используемой во время обновлений, зависит от самого приложения. Наиболее распространенными шаблонами являются 2D или 3D версии окрестностей фон Неймана и Мура . В приведенном выше примере используется двухмерный шаблон фон Неймана, в то время как коды LBM обычно используют его трехмерный вариант. «Игра жизни» Конвея использует двухмерную окрестность Мура. Тем не менее, можно найти и другие шаблоны, такие как 25-точечный шаблон для распространения сейсмических волн [5] .
Проблемы реализации
Многие коды моделирования могут быть естественно сформулированы как ISL. Поскольку время вычислений и потребление памяти линейно растут с количеством элементов массива, параллельные реализации ISL имеют первостепенное значение для исследований. [6] Это сложно, поскольку вычисления тесно связаны (из-за того, что обновления ячеек зависят от соседних ячеек), и большинство ISL привязаны к памяти (т. Е. Отношение обращений к памяти к вычислениям велико). [7] Практически все текущие параллельные архитектуры были исследованы для эффективного выполнения ISL; [8] на данный момент GPGPU доказали свою эффективность. [9]
Библиотеки
Из-за важности ISL для компьютерного моделирования и их высоких вычислительных требований, существует ряд усилий, направленных на создание многоразовых библиотек для поддержки ученых в выполнении вычислений на основе трафаретов. Библиотеки в основном занимаются распараллеливанием, но могут также решать другие задачи, такие как ввод-вывод, управление и контрольные точки . Их можно классифицировать по их API.
Библиотеки на основе патчей
Это традиционный дизайн. Библиотека управляет набором n- мерных скалярных массивов, к которым пользовательская программа может обращаться для выполнения обновлений. Библиотека обрабатывает синхронизацию границ (дублированная зона-призрак или ореол). Преимущество этого интерфейса состоит в том, что пользовательская программа может перебирать массивы, что упрощает интеграцию унаследованного кода [10] . Недостатком является то, что библиотека не может обрабатывать блокировку кеша (поскольку это должно выполняться в циклах [11] ) или обертывание API-вызовов для ускорителей (например, через CUDA или OpenCL). Реализации включают Cactus , среду решения физических задач и waLBerla .
Библиотеки на основе ячеек
Эти библиотеки перемещают интерфейс для обновления отдельных ячеек моделирования: отображаются только текущая ячейка и ее соседи, например, с помощью методов получения / установки. Преимущество этого подхода заключается в том, что библиотека может жестко контролировать, какие ячейки обновляются в каком порядке, что полезно не только для реализации блокировки кеша [9], но также для запуска одного и того же кода на многоядерных процессорах и графических процессорах. [12] Этот подход требует, чтобы пользователь перекомпилировал исходный код вместе с библиотекой. В противном случае потребуется вызов функции для каждого обновления ячейки, что серьезно снизит производительность. Это возможно только с такими методами, как шаблоны классов или метапрограммирование , что также является причиной того, что этот дизайн встречается только в более новых библиотеках. Примерами являются Physis и LibGeoDecomp .
Смотрите также
- Расширенная библиотека моделирования
- Метод конечных разностей
- Компьютерное моделирование
- Пятиточечный трафарет
- Прыжки по трафарету
- Трафарет (численный анализ)
Рекомендации
- ^ a b c Рот, Джеральд и др. (1997) Труды SC'97: Высокопроизводительные сети и вычисления. Компиляция трафаретов в высокопроизводительном Фортране.
- ^ a b c d Sloot, Peter MA et al. (28 мая 2002 г.) Вычислительная наука - ICCS 2002: Международная конференция, Амстердам, Нидерланды, 21–24 апреля 2002 г. Труды, часть I. Страница 843. Издатель: Springer. ISBN 3-540-43591-3 .
- ^ a b c Фей, Дитмар и др. (2010) Grid-Computing: Eine Basistechnologie für Computational Science . Стр. 439. Издательство: Springer. ISBN 3-540-79746-7
- ^ Ян, Лоуренс Т .; Го, Миньи. (12 августа 2005 г.) Высокопроизводительные вычисления: парадигма и инфраструктура. Стр. 221. Издательство: Wiley-Interscience. ISBN 0-471-65471-X
- ^ Micikevicius, Paulius et al. (2009) 3D-вычисление конечных разностей на графических процессорах с использованием материалов CUDA 2-го семинара по универсальной обработке на графических процессорах ISBN 978-1-60558-517-8
- ^ Datta, Kaushik (2009) Коды автонастройки трафаретов для многоядерных платформ на основе кэша Архивировано 8 октября 2012 г. в Wayback Machine , Ph.D. Тезис
- ^ Wellein, G et al. (2009) Эффективная временная блокировка для вычислений трафаретов с помощью многоядерного распараллеливания волнового фронта , 33-я ежегодная Международная конференция по компьютерному программному обеспечению и приложениям IEEE, COMPSAC 2009
- ^ Датта, Каушик и др. (2008) Оптимизация трафаретных вычислений и автонастройка на современных многоядерных архитектурах , SC '08 Proceedings of the 2008 ACM / IEEE Conference on Supercomputing
- ^ a b Шефер, Андреас и Фей, Дитмар (2011) Высокопроизводительные алгоритмы кода трафарета для GPGPU , Труды Международной конференции по вычислительной науке, ICCS 2011
- ^ С. Донат, Дж. Гетц, К. Файхтингер, К. Иглбергер и У. Рюде (2010) waLBerla: Оптимизация для систем на базе Itanium с тысячами процессоров , высокопроизводительные вычисления в науке и технике, Гархинг / Мюнхен, 2009 г.
- ^ Нгуен, Энтони и др. (2010) 3.5-D Blocking Optimization for Stencil Computations on Modern CPU and GPUs , SC '10 Proceedings of the 2010 ACM / IEEE International Conference for High Performance Computing, Networking, Storage and Analysis
- ^ Наоя Маруяма, Тацуо Номура, Кенто Сато и Сатоши Мацуока (2011) Physis: неявно параллельная модель программирования для трафаретных вычислений на крупномасштабных суперкомпьютерах с GPU-ускорением , Материалы SC '11 Международной конференции ACM / IEEE 2011 по высокой производительности Вычислительная техника, сеть, хранение и анализ
Внешние ссылки
- Physis
- LibGeoDecomp
- WaLBerla