Параллельная генерация сетки
Параллельная генерация сеток в численном анализе — это новая область исследований, находящаяся на границе двух научных вычислительных дисциплин: вычислительной геометрии и параллельных вычислений . [1] Методы параллельного создания сетки разлагают исходную задачу создания сетки на более мелкие подзадачи, которые решаются (объединяются в сетку) параллельно с использованием нескольких процессоров или потоков. Существующие методы параллельного построения сетки можно классифицировать по двум основным признакам:
- последовательный метод, используемый для объединения отдельных подзадач и
- степень связи между подзадачами.
Одной из проблем создания параллельных сеток является разработка программного обеспечения для создания параллельных сеток с использованием готовых кодов последовательного построения сеток.
Обзор
[ редактировать ]Процедуры параллельного создания сетки, как правило, разлагают исходную задачу создания двухмерной (2D) или трехмерной (3D) сетки на N меньших подзадач, которые решаются (т.е. объединяются в сетку) одновременно с использованием P процессоров или потоков. [1] Подзадачи могут быть сформулированы как тесно связанные, [2] [3] частично связанный [4] [5] или даже разъединены. [6] [7] Связь подзадач определяет интенсивность коммуникации и объем/тип синхронизации, требуемой между подзадачами.
Задачи в методах создания параллельных сеток заключаются в следующем: поддерживать стабильность параллельного создателя сетки (т. е. сохранять качество конечных элементов, генерируемых современными последовательными кодами) и в то же время достигать 100% повторного использования кода ( т.е. использовать постоянно развивающиеся и полностью функциональные готовые последовательные сетки) без существенного ухудшения масштабируемости параллельной модели.
Существует разница между созданием параллельной сетки и параллельной триангуляцией. При параллельной триангуляции заранее определенный набор точек используется для создания параллельных треугольников, покрывающих выпуклую оболочку набора точек. Очень эффективный алгоритм параллельных триангуляций Делоне представлен в работе Blelloch et al. [8] Этот алгоритм расширен Клеменсом и Уокингтоном. [9] для параллельной генерации сетки.
Программное обеспечение для параллельного создания сетки
[ редактировать ]Хотя многие решатели были перенесены на параллельные машины, генераторы сеток остались позади. Тем не менее этап предварительной обработки создания сетки остается узким местом в цикле моделирования. Поэтому необходимость разработки стабильного генератора параллельных 3D-сеток вполне оправдана.
Параллельная версия генератора сетки MeshSim от Simmetrix Inc., [10] доступен как для исследовательских, так и для коммерческих целей. Он включает в себя параллельную реализацию генерации сетки поверхности, объема и пограничного слоя, а также адаптивность параллельной сетки. Алгоритмы, которые он использует, основаны на тех, что указаны в ссылке. [4] и масштабируемы (как в параллельном смысле, так и в том смысле, что дают ускорение по сравнению с последовательной реализацией) и стабильны. Для многоядерных или многопроцессорных систем также существует многопоточная версия этих алгоритмов, доступная в базовом продукте MeshSim. [11]
Еще один генератор параллельных сеток — D3D , [12] был разработан Дэниелом Риплом [13] в Чешском техническом университете в Праге. D3D — это генератор сеток, способный разделять параллельно (или последовательно) 3D-домены на смешанные сетки.
БОКСЕРСетка [14] представляет собой неструктурированный гибридный генератор сетки [15] разработан компанией Cambridge Flow Solutions. [16] Реализованное в виде полностью распараллеленного программного обеспечения с распределенной памятью, оно специально разработано для преодоления традиционных узких мест, ограничивающих инженерное моделирование, обеспечивая расширенное создание сеток на геометриях произвольной сложности и размера. Его масштабируемость была продемонстрирована на очень больших сетках, созданных в кластерах HPC.
Проблемы параллельного создания сетки
[ редактировать ]Разработка алгоритмической и программной инфраструктуры для коммерческих библиотек последовательного создания сеток занимает значительное время. Более того, открыты улучшения по качеству, скорости и функционалу.закончилось, что усложняет задачу создания передовых кодов параллельной генерации сетки.
Областью, которая дает непосредственные преимущества параллельного создания сетки, является декомпозиция доменов. Проблема DD, как она поставлена в [17] по-прежнему открыт для трехмерной геометрии, и его решение поможет предоставить стабильные и масштабируемые методы, основанные на готовых кодах генерации сетки для Delaunay и Advancing Front Techniques.
Наконец, долгосрочные инвестиции в параллельное создание сеток призваны привлечь внимание математиков открытыми проблемами создания сеток и более широким влиянием на математику.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Никос Крисохоидес, Параллельная генерация сетки, глава численного решения уравнений в частных производных на параллельных компьютерах (под ред. Магнуса Бруасета, Аслака Твейто), Springer-Verlag, стр. 237-259, 2005.
- ^ Никос Крисохоидес и Демиан Нейв. Ядро параллельной генерации сетки Делоне . Межд. Дж. Нумер. Мет. англ., 58:161--176, 2003
- ^ Лонер, Дж. Камберос и М. Маршал. Параллельная неструктурированная сеткаПоколение. Глава « Неструктурированные научные вычисления на масштабируемых мультипроцессорах» . (Редакторы Пиюш Мехротра и Джоэл Сальц), стр. 31–64, MIT Press, 1990.
- ^ Jump up to: а б Х. де Куни и М. Шепард. Параллельное создание объемной сетки с использованием удаления граней и иерархического перераспределения. Комп. Мет. Прил. Мех. англ., 174(3-4):275-298, 1999.
- ^ Андрей Черников и Никос Хрисохоидес. Параллельное гарантированное качество. Уточнение плоской сетки Делоне. Одновременная вставка точек. SIAM Journal for Scientific Computing , Vol. 28, № 5, стр. 1907-1926, 2006.
- ^ Дж. Галтье и П.Л. Джордж. Предварительное разделение как способ параллельного объединения поддоменов. Специальный симпозиум по тенденциям в создании неструктурированных сеток, стр. 107–122. ASME/ASCE/SES, 1997.
- ^ Леонидас Линардакис и Никос Крисохоидес. Метод развязки Делоне для параллельного создания плоской сетки гарантированного качества. SIAM Journal for Scientific Computing , Vol. 27, № 4, стр. 1394-1423, 2006.
- ^ GE Blelloch, JC Hardwick, G.~L. Миллер и Д. Талмор, Разработка и реализация практического параллельного алгоритма Делоне, Algorithmica, 24 (1999), стр. 243–269.
- ^ Клеменс Кадоу и Ноэль Уокингтон. Разработка алгоритма параллельного построения и уточнения сетки Делоне на основе проекций. В материалах Четвертого симпозиума по тенденциям в создании неструктурированных сеток, 2003 г.
- ^ «Параллельный MeshSim» . Архивировано из оригинала 18 февраля 2009 г. Проверено 5 августа 2009 г.
- ^ «МешСим» . Архивировано из оригинала 27 сентября 2009 г. Проверено 5 августа 2009 г.
- ^ Веб-страница генератора сетки D3D
- ^ Веб-страница университета Дэниела Рипла, http://mech.fsv.cvut.cz/~dr/
- ^ БОКСЕРМэш
- ^ Масштабируемое параллельное создание сетки
- ^ Кембриджские решения для потоков
- ^ Крисохоидес Н., Обзор методов создания параллельных сеток , Университет Брауна, Провиденс, Род-Айленд, 2005.