평행 메시 생성

Parallel mesh generation

수치해석에서의 병렬 메시 생성은 두 과학적인 계산 분야인 계산 기하학과 병렬 컴퓨팅 사이의 새로운 연구 영역이다.[1]병렬 메시 생성 방법은 원래 메시 생성 문제를 여러 프로세서 또는 스레드를 사용하여 병렬로 해결(메시드)하는 더 작은 하위 문제로 분해한다.기존의 병렬 메시 생성 방법은 두 가지 기본 속성으로 분류할 수 있다.

  1. 개별 하위 문제를 메싱하는 데 사용되는 순차적 기법
  2. 하위 문제 사이의 결합 정도

병렬 메시 생성의 과제 중 하나는 기성품 순차 메싱 코드를 사용하여 병렬 메싱 소프트웨어를 개발하는 것이다.

개요

일반적으로 병렬 메시 생성 절차는 원래의 2차원(2D) 또는 3차원(3D) 메시 생성 문제를 P 프로세서나 스레드를 사용하여 동시에 해결(즉, 메쉬드)되는 N개의 작은 하위 문제로 분해한다.[1]하위 문제는 긴밀하게 결합되거나 부분적으로[4][5] 결합되거나 분리되도록 공식화될 수 있다.[2][3][6][7]하위 문제의 결합은 통신의 강도 및 하위 문제들 사이에 필요한 동기화 양/유형을 결정한다.

병렬 메시 생성 방법의 과제는 병렬 메셔의 안정성을 유지하는 것(즉, 최첨단 순차 코드에 의해 생성된 유한 요소의 품질을 유지하는 것)과 동시에 100% 코드 재사용을 달성하는 것(즉, 연속적으로 진화하고 완전히 기능하는 기성 순차 메서드를 활용하는 것)이다.병렬 메셔의 확장성이 실질적으로 저하됨

병렬 메시 생성과 병렬 삼각 측량 사이에는 차이가 있다.병렬 삼각측량에서는 미리 정의된 점 집합을 사용하여 점 집합의 볼록한 선체를 덮는 병렬 삼각형을 생성한다.병렬 Delaunay 삼각측량을 위한 매우 효율적인 알고리즘이 Blelloch 등지에 나타난다.[8]이 알고리즘은 병렬 메시 생성을 위해 클레멘스와 워킹턴에서[9] 확장된다.

병렬 메시 생성 소프트웨어

많은 솔버들이 평행 기계에 포팅되어 있는 반면, 그리드 발전기는 뒤에 남겨졌다.여전히 메쉬 생성의 사전 처리 단계는 시뮬레이션 사이클에서 순차적인 병목현상으로 남아 있다.안정적인 3D 병렬 그리드 발전기 개발의 필요성이 충분히 정당화된 이유다.

Simmetrix Inc.에 의한 MeshSim 메쉬 생성기의 병렬 버전은 연구용과 상업용으로 모두 사용할 수 있다.[10]그것은 표면, 부피 및 경계층 메시 생성의 병렬 구현과 병렬 메시 적응성을 포함한다.이 알고리즘이 사용하는 알고리즘은 참조 알고리즘을 기반으로 하며 확장성이 있으며(연속 구현에 비해 병렬적 의미와 속도 향상을 제공한다는 의미에서 모두) 안정적이다.멀티코어 또는 멀티프로세서 시스템의 경우, 기본 MeshSim 제품에서 사용할 수 있는 이러한 알고리즘의 멀티스레드 버전도 있다.

또 다른 병렬 메시 발전기는 프라하에 있는 체코 기술 대학의 다니엘 라이플에[13] 의해 개발된 [12]D3D이다.D3D는 3D 도메인을 병렬(또는 순차적으로) 혼합 메쉬로 분해할 수 있는 메쉬 생성기다.

BOXMesh는 캠브리지 플로우 솔루션에서 개발한 구조화되지 않은 하이브리드 메쉬 생성기다.[16]분산 메모리 완전 병렬 소프트웨어로 구현된 이 소프트웨어는 엔지니어링 시뮬레이션을 제약하는 기존의 병목 현상을 극복하기 위해 특별히 설계되었으며, 임의의 복잡성과 크기의 기하학적 구조에 대한 고급 메싱을 제공한다.HPC 클러스터에서 생성된 매우 큰 메쉬에서 확장성이 입증되었다.

병렬 메시 생성의 과제

상용 순차 메시 생성 라이브러리를 위한 알고리즘과 소프트웨어 인프라를 개발하려면 상당한 시간이 걸린다.더욱이 품질, 속도, 기능성의 측면에서 개선은 오픈 엔드로 되어 있어 선행 에지 병렬 메시 생성 코드를 만드는 작업이 난항을 겪고 있다.

병렬 메쉬 생성에 대한 즉각적인 이점이 높은 영역은 영역 분해다.DD 문제는 3D 기하학에도 여전히 열려 있으며, DD의 솔루션은 Delaunay 및 Advanced Front Technologies의 기성 메쉬 생성 코드에 의존하는 안정적이고 확장 가능한 방법을 제공하는 데 도움이 될 것이다.

마지막으로 병렬 메쉬 생성에 대한 장기적인 투자는 메쉬 생성에 있어 개방적인 문제와 수학에 있어 광범위한 영향을 가진 수학자들의 관심을 끄는 것이다.

참고 항목

참조

  1. ^ a b Nikos Chrisochoides, Parallel Mesh Generation, Parallel Mesh Generation, Parallel Computers의 부분 미분 방정식 수치해결 챕터, (Eds)Are Magnus Bruaset, Aslak Tveito), Springer-Verlag, pp 237-259, 2005.
  2. ^ 니코스 크리스초이데스, 데미안 네이브.병렬 Delaunay 메쉬 생성 커널.숫자 J. 숫자.필로폰, 58:161-176, 2003
  3. ^ 로너, J. 캠버로스, M.보안관님병렬 구조화되지 않은 그리드 생성.확장 가능한 멀티프로세서에 대한 비정형 과학 연산 장(Eds).Piyush Mehrotra and Joel Saltz), 페이지 31-64, MIT Press, 1990.
  4. ^ a b H. de Cougny와 M.셰퍼드얼굴 제거 및 계층적 재배치를 사용한 병렬 볼륨 메싱.메스 중독자app. 메흐.영어, 174(3-4):275--298, 1999.
  5. ^ 안드레이 체르니코프와 니코스 크리스초이데스.병렬 보증 품질 평면라 델로나이 메쉬 정제 동시 포인트 삽입.SIAM 과학 컴퓨팅 저널, 제28권, 제5권 1907-1926, 2006.
  6. ^ J. Galtier와 P. L. George.하위 도메인을 병렬로 메쉬하는 방법으로 사전 파티셔닝.비정형 메쉬 생성 동향 특별 심포지엄, 페이지 107-122.ASME/ASCE/SES, 1997.
  7. ^ 레오니다스 리나르다키스와 니코스 크리스초이데스.병렬 보증 품질 평면의 메쉬 생성을 위한 Delaunay 디커플링 방법.SIAM 과학 컴퓨팅 저널, 제27권, 제4권 1394-1423호, 2006.
  8. ^ G. E. Blelloch, J.C. Hardwick, G.~L.밀러, 그리고 D.Talmor, 실제 병렬 Delaunay 알고리즘의 설계 및 구현, Algorithmica, 24 (1999), 페이지 243–269.
  9. ^ 클레멘스 카도, 노엘 워킹턴.투영 기반 병렬 Delaunay 메쉬 생성 및 미세화 알고리즘 설계2003년 제4차 비정형 메쉬 세대 동향 심포지엄의 진행과정.
  10. ^ 평행 메시심
  11. ^ 메쉬심
  12. ^ D3D Mesh Generator 웹 페이지
  13. ^ 다니엘 라이플의 대학 웹페이지 http://mech.fsv.cvut.cz/~dr/
  14. ^ 복서메시
  15. ^ 확장 가능한 병렬 메시 생성
  16. ^ 케임브리지 플로우 솔루션
  17. ^ Chrisochoides N, Brown University, Providence RI - 2005의 병렬 메시 생성 방법 조사.