離散最適化手法を用いた並列処理の高速化に関する研究

利用离散优化技术加速并行处理的研究

• 批准号: 11780211
• 负责人: 市川 周一
• 金额: $ 1.47万
• 依托单位: Toyohashi University of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1999
• 资助国家: 日本
• 起止时间: 1999 至 2000
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-11780211/
• 关键词: 並列処理; 分散処理; 静的負荷分散; データ自動分割; 通信遅延; 計算困難問題

多くの静的負荷分散問題は組合せ最適化としてモデル化できることが知られている。通信時間を考慮した静的負荷分散問題は計算困難なので実用的には単純化されたモデルや近似アルゴリズムを用いる場合が多いが、並列計算機が大規模化し、または分散処理環境の利用により通信遅延時間が支配的になってくると、このような単純化では誤差が大きくなり実行効率が低下する。より一般的な場合に適用できる手法の研究が必要である。筆者は偏微分方程式の並列求解システムNSLを例にとって計算時間と通信時間を考慮した静的負荷分散問題をモデル化し、可能な範囲において分枝限定法を用いて最適解を求め、考案した近似解法の誤差を絶対評価した。特に通信時間が支配的な環境化において、複数プロセッサを利用することにより逆に実行時間が増える状況(過剰な負荷分散)を自動的に検出し回避する手法を検討し評価した。本手法では、計算能力や通信遅延が不均一な分散処理環境において、利用可能な複数のプロセッサの中から適切なプロセッサを適切な数だけ選択し、データと計算を自動的に分割して負荷を分散し、実行時間を短縮することが可能になった。研究の過程で、計算困難問題を実用時間で求解することが必要になったため、計算困難問題の求解を高速化する手法についても検討を進めた。代表的な問題の一つとして部分グラフ同型判定問題(NP完全)を取り上げ、専用計算回路で求解を高速化する研究を行って、現状の計算機に比べ最大20倍程度の高速化が得られることを実証した。専用計算回路を大規模化することにより、更なる高速化も容易であると期待される。

Multi-static load dispersion problem optimization The load dispersion problem of communication time is difficult to calculate, and the purification error is large, and the efficiency is low when the parallel computer is used on a large scale, and when the distributed processing environment is used. It is necessary to study the method of general application. In this paper, the author discusses the parallel solution of partial differential equations, the calculation time and communication time, the static load distribution problem, the optimization of the solution, the evaluation of the error of the approximate solution. In particular, the communication time is dominated by environmental factors, such as the use of multiple servers, the increase in travel time (excessive load dispersion), and the automatic detection and avoidance of methods. This method is based on the fact that computing power and communication delay are not uniform, and it is possible to utilize multiple possible servers, select appropriate servers, and compute automatically, distribute loads, and shorten travel times. The process of research, computationally difficult problem solving, necessary, computationally difficult problem solving, fast, and advanced The representative problem is partially solved and the similarity determination problem (NP complete) is solved at a higher speed by using a computational loop. The research is carried out at a speed of up to 20 times higher than that of the current computer. It is expected that large-scale and high-speed computing circuits will be easier.

项目成果

S.Ichikawa: "Hardware Accelerator for Subgraph Isomorphism Problems"Proc.Eighth IEEE Symp.Field-Programmable Custom Computing Machines(FCCM'00). 183-184 (2000)

S.Ichikawa：“子图同构问题的硬件加速器”Proc.Eighth IEEE Symp.Field-Programmable Custom Computers(FCCM00)。

市川周一: "部分グラフ同型判定アルゴリズムのFPGAによる実装と評価"情報処理学会論文誌ハイパフォーマンスコンピューティングシステム. 41・SIG5. 39-49 (2000)

Shuichi Ichikawa：“使用 FPGA 的子图同构确定算法的实现和评估”日本信息处理协会高性能计算系统交易 41・SIG5（2000）。

藤村佳克: "並列数値シミュレーションの静的負荷分散法の拡張について"並列処理シンポジウムJSPP'99. 203-203 (1999)

Yoshikatsu Fujimura：“并行数值模拟的静态负载平衡方法的扩展”并行处理研讨会 JSPP99 (1999)。

山下真史: "分散処理環境における数値シミュレーションの静的負荷分散手法"並列処理シンポジウムJSPP'99. 204 (1999)

Masashi Yamashita：“分布式处理环境中数值模拟的静态负载平衡方法”并行处理研讨会 JSPP99（1999）。

T.Kawai: "NSL : High-Level Language for Parallel Numerical Simulation"Proc.IASTED Int'l Conf.Modeling and Simulation (MS '99). 208-213 (1999)

T.Kawai：“NSL：并行数值模拟高级语言”Proc.IASTED Intl Conf.建模与模拟（MS 99）。