权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

难并行问题的并行研究

基本信息

批准号：
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の性能等)の差異が大きい.したがって,実際のグリッド環境に実装を行う時点で,実際の並列化のコストを正確に見積もった上で開発を行うことが必要であった.本研究については,グリッド上での基本操作である完全交換について一般的には効率的に実行できない"致命的な通信行列"というものが存在することを示し,この通信行列に対してタスク分割を行なうことにより効率よく処理を実行するアルゴリズムを提案した.

In this study, the problem group of parallelism difficulty and application of parallelism proposal is pointed out. 1. The evaluation of parallelism of general problems and the implementation of parallel problems in the research of Heisei 15. The proposal of parallel problems and the implementation of parallel problems in the computer installation of general problems and the implementation of parallel problems in the computer installation of general problems. The result is a general problem, and the evaluation criteria are proposed. The evaluation criteria of the proposal are effective, the evaluation is easy, etc., and the problem is difficult to solve. The automatic parallel problem evaluation system is composed of a plurality of parallel difficult problems, and a plurality of parallel difficult problems. Geographical separation of multiple types of applications in the field of environmental protection, large-scale environmental protection, large-scale environmental protection and practical applications. The computing resources (communication delay, communication bandwidth constraints,CPU performance, etc.) vary greatly from one computer environment to another. When the time comes, when the environment is ready to move, when it is necessary to move forward, when it is necessary to move forward. In this study, the basic operation of the communication array is completely switched, and the general efficiency of the communication array is implemented.