領域分割法を用いた直接法の超並列計算アルゴリズムについての研究

基于域分解法的直接法大规模并行计算算法研究

• 批准号: 07780226
• 负责人: 茂木 和弘
• 金额: $ 0.58万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07780226/
• 关键词: 並列計算手法; 並列スケジュール; デバイスシミュレーション; 遺伝的アルゴリズム

半導体などの開発に必要なデバイスシミュレーション等では、大規模線形連立方程式の高速・高精度な解法が求められている。高速解法の一つとして並列計算手法が有効であることが近年報告されている。スーパーコンピュータなどの計算機を用いた場合にも内部処理的には並列化されているが、並列粒度が小さく逐次処理部に大きな影響を受けてしまい十分な効果を得ることは困難である。これに対して、本研究で用いる物理モデルを考慮に入れた領域分割法を用いた並列計算手法は、大きな並列粒度を得ることが可能であり、実際の並列計算機を用いた数値実験においても効果が得られている。従来は、半導体などの物理モデルを規則的に空間分割を行いこれに対する並列スケジュールを提案したが、任意形状のモデルに対しては対応できなかった。本年度の研究目的は、(1)任意形状の空間分割に対する並列スケジュールの拡張、(2)このときの計算精度の検討である。任意形状の分割スケジュールは、従来の分割スケジュールを拡張することで可能になると考え、分割数を変えずに分割する箇所を変更するスケジュールを提案した。分割箇所を変更することで各部分領域ごとに精度を変更することが可能になった。しかし、従来のスケジュールと同様に解析領域の精度を上げるために分割数を増加させた領域は他の領域に対して多くの時間を必要としている。しかし、実際の高並列計算機AP1000を使用して評価を行った結果は、従来の並列スケジュールと同様に有効であった。しかし、プロセッサと部分領域間のマッピングが十分でなく、計算を行わないプロセッサが生じて効率の問題が残っている。また超並列計算機の計算精度を検討するために、この並列計算機に適したアルゴリズムが必要になる。このアルゴリズムとして、巡回セールスマン問題に対する並列遺伝的アルゴリズムを提案した。

半导体开发所需的器件模拟需要快速且高精度地解决大规模联立线性方程。近年来，据报道并行计算方法作为快速求解方法是有效的。使用超级计算机等计算机时，内部处理是并行的，但并行的粒度较小，受顺序处理部分的影响较大，难以获得足够的效果。另一方面，本研究中使用的考虑到物理模型的域划分方法的并行计算方法可以获得较大的并行粒度，并且在使用实际并行计算机的数值实验中也获得了有效的结果。以前，诸如半导体之类的物理模型是有规律地进行空间划分的，并为此提出了并行时间表，但这对于任意形状的模型来说是不可能的。今年的研究目标是（1）扩展任意形状空间划分的并行调度，以及（2）检查这种情况下的计算精度。我们认为，通过扩展传统的分割时间表可以使任意形状的分割时间表成为可能，并提出了一种在不改变分割数量的情况下改变分割位置的时间表。通过改变分割点，现在可以改变每个部分区域的精度。然而，与传统的调度类似，为了提高分析区域的精度而增加划分数量的区域比其他区域需要更多的时间。然而，使用实际的高度并行计算机AP1000的评估结果表明，它与传统的并行调度一样有效。但处理器与子区域之间的映射不够充分，部分处理器不进行计算，导致效率问题。另外，为了研究大规模并行计算机的计算精度，我们需要一种适合这种并行计算机的算法。作为该算法，我们提出了一种用于旅行商问题的并行遗传算法。