Parallel computing is a powerful tool to solve a large scale problem derived from finite element method or finite difference method related to the subjects such as fluid dynamics, weather forecasting, aerodynamics, and image problem. Currently a multi-core computer is available at a low price and the parallel computing with a small number of parallel tasks is possible at home. In the subjects listed above, propagating interface occurs in a wide variety of phenomena, especially in ocean waves, combustion and flame propagation, crystal growth, image restoration, image reconstruction, and image segmentation. To handle the propagating interface the level set method has been widely used. In this thesis, we study the parallel level set method and implement it in the multi-core computing environment. We use the Godunov scheme for numerical implementation of the level set method and divide the computational domain to keep the scalability. In other words, we develop a methodology for the parallel level set method to keep the scalability. In addition, we show the numerical results keeping the scalability.
유체역학, 기상예측, 항공역학, 이미지 문제와 관련된 유한요소법이나 유한차분법 등과 같은 계산시간이 많이 걸리는 큰 문제를 푸는 데에 병렬 계산은 좋은 해결책이 될 수 있다. 과거에는 병렬 계산을 위해 클러스터와 같은 비싼 장비를 갖추어야 하기 때문에 병렬 계산을 하는 것은 어려운 일이었다. 근래에 데스크탑 시장에서 멀티코어 컴퓨터의 등장으로 가정에서조차 병렬 계산을 할 수 있는 시대가 되어 병렬 계산을 위한 환경을 갖추기가 쉬어졌다.
한편, 파랑, 연소와 불꽃의 이동, 이미지 복원, 이미지 분할 등의 문제는 경계가 진행하는 문제로 생각할 수 있다. 이런 경계의 진행을 해석하는 방법으로 등위 집합 방법이 많이 이용된다. 본 논문에서는 등위 집합 방법을 multi-core 컴퓨터 상에서 병렬 계산하기 위한 병렬 등위 집합 방법을 제시한다.
먼저 등위 집합 방법을 구현하기 위해서 Godunov scheme을 이용하여 등위 집합식을 풀고, 재초기화식을 풀어 등위 집합 함수를 부호 거리 함수로 다시 초기화 한다. 또한 CFL (Courant-Friedrichs-Levy) 조건을 고려하여, 적절한 시간간격을 정한다. 병렬 계산을 수행하기 위하여, 문제가 정의 된 영역을 분할하여 계산하고, 적절한 위치에서 동기화를 수행하여 올바른 계산을 하도록 한다.
논문의 알고리즘을 확인하기 위하여, Microsoft Visual Studio 2005 C++와 OpenMP를 이용하여 알고리즘을 구현하였고, 다양한 수치적 결과를 통해 본 논문에서 제시한 알고리즘이 정확한 결과와 코어의 수에 따른 선형적 속도 향상을 보이는 것을 알 수 있다.
