Создание параллельной сетки - Parallel mesh generation

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

  1. последовательный метод, используемый для объединения отдельных подзадач и
  2. степень связи между подзадачами.

Одной из проблем при создании параллельных сеток является разработка программного обеспечения для построения параллельных сеток с использованием готовых кодов последовательного построения сеток.

Обзор

Процедуры создания параллельной сетки в общем случае разбивают исходную задачу создания 2-мерной (2D) или 3-мерной (3D) сетки на N меньших подзадач, которые решаются (то есть объединяются в сетку) одновременно с использованием P-процессоров или потоков.[1] Подзадачи могут быть сформулированы как тесно связанные,[2][3] частично связанный[4][5] или даже развязаны.[6][7] Связь подзадач определяет интенсивность коммуникации и количество / тип синхронизации, необходимой между подзадачами.

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

Есть разница между генерацией параллельной сетки и параллельной триангуляцией. В параллельной триангуляции заранее определенный набор точек используется для создания параллельных треугольников, которые покрывают выпуклую оболочку набора точек. Очень эффективный алгоритм параллельных триангуляций Делоне появился в Blelloch et al.[8] Этот алгоритм расширен в Клеменсе и Уокингтоне.[9] для создания параллельной сетки.

Программное обеспечение для создания параллельной сетки

Хотя многие решатели были перенесены на параллельные машины, генераторы сеток остались позади. Тем не менее этап предварительной обработки сетки остается узким местом в цикле моделирования. Поэтому вполне оправдана необходимость разработки стабильного генератора трехмерных параллельных сеток.

Параллельная версия генератора сетки MeshSim от Simmetrix Inc.,[10] доступен как для исследований, так и для коммерческого использования. Он включает параллельные реализации создания поверхностных, объемных и пограничных сеток, а также адаптивность параллельных сеток. Используемые им алгоритмы основаны на приведенных [4] и являются масштабируемыми (как в параллельном смысле, так и в том смысле, что они дают ускорение по сравнению с последовательной реализацией) и стабильны. Для многоядерных или многопроцессорных систем также существует многопоточная версия этих алгоритмов, которые доступны в базовом продукте MeshSim. [11]

Другой генератор параллельной сетки D3D,[12] был разработан Daniel Rypl[13] в Чешском техническом университете в Праге. D3D - генератор сеток, способный преобразовывать параллельные (или последовательно) трехмерные области в смешанные сетки.

BOXERMesh [14] генератор неструктурированной гибридной сетки [15] разработан Cambridge Flow Solutions.[16] Реализованный в виде полностью распараллеленного программного обеспечения с распределенной памятью, он специально разработан для преодоления традиционных узких мест, ограничивающих инженерное моделирование, обеспечивая расширенное построение сетки на геометриях произвольной сложности и размера. Его масштабируемость была продемонстрирована на очень больших сетках, созданных на кластерах HPC.

Проблемы при создании параллельной сетки

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

Область, которая дает непосредственные преимущества для создания параллельной сетки, - это декомпозиция доменов. Проблема DD, как она поставлена ​​в [17] по-прежнему открыт для 3D-геометрий, и его решение поможет предоставить стабильные и масштабируемые методы, основанные на готовых кодах создания сетки для Delaunay и Advancing Front Techniques.

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

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

использованная литература

  1. ^ а б Никос Крисохоидес, Parallel Mesh Generation, глава в Численное решение уравнений с частными производными на параллельных компьютерах(Ред. Аре Магнус Брузет, Аслак Твейто), Springer-Verlag, стр. 237-259, 2005.
  2. ^ Никос Хрисохоидес и Демиан Нейв. Параллельный Делоне Ядро генерации сетки. Int. J. Numer. Meth. Англ., 58: 161--176, 2003
  3. ^ Лонер, Дж. Камберос и М. Маршал. Параллельное создание неструктурированных сетей. Глава в Неструктурированные научные вычисления на масштабируемых мультипроцессорах. (Ред. Пиюш Мехротра и Джоэл Сальц), стр 31-64, MIT Press, 1990.
  4. ^ а б Х. де Куни и М. Шепард. Создание параллельной объемной сетки с использованием удаления граней и иерархического разделения. Комп. Meth. Appl. Мех. Engng., 174 (3-4): 275-298, 1999.
  5. ^ Андрей Черников и Никос Хрисохоидес. Параллельное гарантированное качество Плоское уточнение сетки Делоне Одновременная вставка точек. SIAM Journal для научных вычислений, Vol. 28, No. 5, pp 1907-1926, 2006.
  6. ^ Дж. Галтье и П. Л. Джордж. Предварительное разбиение как способ параллельной сетки подобластей. Специальный симпозиум по тенденциям в создании неструктурированных сеток, стр 107-122. ASME / ASCE / SES, 1997.
  7. ^ Леонидас Линардакис и Никос Хрисохоидес. Метод развязки Делоне для параллельного создания плоской сетки гарантированного качества. SIAM Journal для научных вычислений, Vol. 27, No. 4, pp. 1394-1423, 2006.
  8. ^ Дж. Э. Блеллох, Дж. К. Хардвик, Г. ~ Л. Миллер, Д. Талмор, Разработка и реализация практического параллельного алгоритма Делоне, Algorithmica, 24 (1999), стр. 243--269.
  9. ^ Клеменс Кадоу и Ноэль Уокингтон. Разработка алгоритма построения и уточнения параллельной сетки Делоне на основе проекции. В трудах Четвертого симпозиума по тенденциям в создании неструктурированных сеток, 2003 г.
  10. ^ Параллельный MeshSim
  11. ^ MeshSim
  12. ^ Веб-страница D3D Mesh Generator
  13. ^ Веб-страница университета Дэниела Рипла, http://mech.fsv.cvut.cz/~dr/
  14. ^ BOXERMesh
  15. ^ Масштабируемое создание параллельной сетки
  16. ^ Решения Cambridge Flow
  17. ^ Chrisochoides N., Обзор методов создания параллельных сеток, Университет Брауна, Провиденс, Род-Айленд - 2005.