並列化困難問題の並列性に関する研究

难并行问题的并行研究

基本信息

批准号：
14780229
负责人：
藤原暁宏
金额：
$ 2.3万
依托单位：
Kyushu Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2002
资助国家：
日本
起止时间：
2002 至 2004
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14780229/
关键词：
並列化困難性計算量理論並列アルゴリズム並列分散処理 P完全性

项目摘要

本研究では,並列化困難とされている問題群に対して,実用的な並列アルゴリズムの提案を目指し研究に取り組んでいる.平成16年度に関しては,以下のような成果を得た.1 一般問題の並列性の評価を行なうシステムの実現平成15年度までの研究において,いくつかの並列化困難問題に適した並列アルゴリズムの提案を行ない,また,そのアルゴリズムを実際の計算機クラスタ上で実装することにより,効果的な並列処理が可能であることを示した.この結果を元に,一般的な問題に対する並列性の評価尺度を提案した.提案した評価尺度は有効性,評価容易性等の条件を満たしており,並列化困難な問題に対するアルゴリズム制作の指標として活用することが可能であった.また,自動的に問題の並列性を評価するシステムを作成し,多くの並列化困難問題に対して,問題の持つ並列性の評価を行った.2 グリッド環境における並列化困難問題に対する並列アルゴリズムの実装と評価平成15年度までに提案した並列アルゴリズムを拡張し,地理的に離れた複数のクラスタを用いたグリッド環境に実装することにより,大規模なグリッド環境におけるアルゴリズムの実用性を示した.これまでの計算機クラスタ環境とは異なり,グリッド環境では様々な計算資源(通信遅延,通信路帯域制限,CPUの性能等)の差異が大きい.したがって,実際のグリッド環境に実装を行う時点で,実際の並列化のコストを正確に見積もった上で開発を行うことが必要であった.本研究については,グリッド上での基本操作である完全交換について一般的には効率的に実行できない"致命的な通信行列"というものが存在することを示し,この通信行列に対してタスク分割を行なうことにより効率よく処理を実行するアルゴリズムを提案した.

在这项研究中，我们正在研究一种被认为难以并行化的问题的实用并行算法。在2004财年，我们获得了以下结果：1实施用于评估一般问题并行性的系统。在2003财年之前的研究中，我们提出了一种适用于几个困难并行化问题的并行算法，还表明可以通过在实际的计算机群集上实现算法来执行有效的并行性。基于此结果，我们提出了有关一般问题的并行性量表。提出的评估量表满足了诸如有效性和易于评估等条件，并且可以将其用作为难以并行化的问题创建算法的指标。此外，将自动创建一个系统来评估问题的并行性，并评估了许多困难并行问题的问题的并行性。2实施和评估网格环境中困难的并行问题的并行算法的实现和评估。通过扩展2003年提出的并行算法并使用多个地理分离的多个群集在网格环境中实施，我们证明了该算法在大规模的网格环境中的实用性。与以前的计算机集群环境不同，在网格环境中，各种计算资源（通信延迟，通信频道限制，CPU性能等）很大。因此，在实际的网格环境中实施它时，有必要在开发开发之前准确估计实际并行化的成本。在这项研究中，我们表明存在一个“致命的通信矩阵”，该矩阵无法有效地对网格的基本操作进行有效执行，这在完全交换方面通常不有效，并提出了一种算法，该算法在此通信矩阵上执行任务部门。