著者

河野洋一 西松 研 福盛 秀雄 村岡 洋一

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ハイパフォーマンスコンピューティング(HPC)

巻号頁・発行日

vol.1996, no.22, pp.43-48, 1996-03-04

参考文献数

5

被引用文献数

1

---

有限要素法の要素分割には、有限要素法の解に信頼性が増すため、ボロノイ分割と双対なdelaunay三角形(elaunayy四面体)が非常に有効である。しかしボロノイ分割の処理は非常に重いため、ボロノイ分割の高速化が望まれている。そこで、本論文ではボロノイ分割の高速化のため、並列計算機を用いたアルゴリズムを提案する。さらに、要素数の多い時に有効な要素分割の並列化手法の提案を行なう。本手法を富士通の分散メモリ型並列計算機AP1000に実装した結果、母点数6000個の2次元ボロノイ分割を、PE数32台で約11倍の高速化を達成することができた。This paper presents two parallel algorithms for constructing Voronoi diagram and Delaunay triangulation. One algorithm using both a incremental method for inside PEs, and a divide-and-conquer method for merging Voronoi Diagrams between neighboring PEs is proposed. And the other algorithm for many generators which needs only one step of communication for merging Voronoi Diagrams is proposed. With 32 PEs configuration, the second method achieved speed-up ratio of 11 for 6000 generators.