WEKO3
アイテム
分割統治法を用いたタスク並列Tree-based AMRアルゴリズム
http://hdl.handle.net/2261/54203
http://hdl.handle.net/2261/5420384ace62e-a341-44c0-8a6b-e580c4f5e6a3
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
48116422.pdf (2.7 MB)
|
|
| Item type | 学位論文 / Thesis or Dissertation(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2013-05-07 | |||||
| タイトル | ||||||
| タイトル | 分割統治法を用いたタスク並列Tree-based AMRアルゴリズム | |||||
| 言語 | ||||||
| 言語 | jpn | |||||
| 資源タイプ | ||||||
| 資源 | http://purl.org/coar/resource_type/c_46ec | |||||
| タイプ | thesis | |||||
| その他のタイトル | ||||||
| その他のタイトル | A Task Parallel Tree-based AMR Using Divide-and-Conquer Method | |||||
| 著者 |
河野, 瑛
× 河野, 瑛 |
|||||
| 著者別名 | ||||||
| 識別子Scheme | WEKO | |||||
| 識別子 | 10556 | |||||
| 姓名 | Kono, Akira | |||||
| 著者所属 | ||||||
| 著者所属 | 東京大学大学院情報理工学系研究科電子情報学専攻 | |||||
| 著者所属 | ||||||
| 著者所属 | Department of Information and Communication Engineering, Graduate School of Information Science and Technology, The University of Tokyo | |||||
| Abstract | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | 微分方程式の数値シミュレーションは工学・自然科学等様々な分野で重要な問題であり，特に近年並列計算環境を用いた大規模計算によって大きな成果が挙げられている．これらのシミュレーションは一般に計算対象空間を格子を用いて離散化することで行われる．計算の精度は格子のサイズに依存し，より高精度な計算にはより大きな計算量，データサイズが必要となる．しかしながら多くの場合，高精度が必要となるのはシミュレーション領域のごく限られた部分であることが多く，こういった場合には本来必要の無い部分にまで細粒度な格子が用いられることになる．このように領域中の場所によって求められる精度が異なるようないわゆるマルチスケール問題に対して効果を発揮するのがAdaptive Mesh Refinement(AMR) 法である．AMR 法では高精度が必要な部分に局所的に細かい格子を用いて離散化を行い，全体は粗い格子で離散化を行うことにより，計算量やメモリ量を節約しつつ高解像度の計算を実現する．特に高精度が必要な部分に対して再帰的に空間を均等に分割することによって得られる格子を用いるTree-based AMR 法に対して，近年大規模な並列計算を行う研究が盛んに行われている．Tree-based AMR 法は空間的に不均一なデータ分布を持ち，また計算が進むに連れて格子が変化していくために，従来用いられてきたようなデータを分轄することによって並列化を行うSPMD モデルを用いて効率的な並列プログラムを記述することは難しい問題である．一方でこのような並列化の難しいアプリケーションや階層化・複雑化の進む計算機環境を背景に，高生産に並列計算を行うことができる並列プログラミングモデルやプログラミング言語への要請が高まっている．中でもタスク並列モデルは，プログラム中の任意の場所で生成できる並列実行可能な『タスク』を用いた柔軟な並列性の記述が可能であり，特に再帰を用いる分割統治法のようなアルゴリズムも直感的かつ効率的に並列化することができる．また，処理系によって自動的に計算プロセス間の負荷分散がおこなわれるため，動的なアプリケーションに対しても効率的な並列化が可能である．本研究ではこのような背景から，タスク並列モデルを用いたTree-based AMR アルゴリズムを提案している．提案手法では，タスク並列処理系による自動的な負荷分散や見通しの良い並列化を実現しているだけでなく，分割統治法に基づいたアルゴリズムにより効率的な処理を可能にしている．特に格子中の隣接セルへのアクセスを伴うような操作に対しては，従来全体でO(n log(n)) の計算コストを要するか，もしくは高速化のためのデータ構造を別に用意する必要があったのに対して，木構造のデータ分散が偏りすぎていないという前提のもとでシンプルなデータ構造を保ちながらO(n) の計算コストを実現している．実際に，移流方程式と拡散方程式の差分解法に基づいたTree-based AMR シミュレーションの実装を行い共有メモリ環境で良好な並列性能を確認した． | |||||
| 書誌情報 | 発行日 2013-03-25 | |||||
| 学位名 | ||||||
| 学位名 | 修士(情報理工学) | |||||
| 学位 | ||||||
| 値 | master | |||||
| 研究科・専攻 | ||||||
| 情報理工学系研究科・電子情報学専攻 | ||||||
| 学位授与年月日 | ||||||
| 学位授与年月日 | 2013-03-25 | |||||
