多重バスを有する並列計算機モデル上の並列計算に関する研究

多总线并行计算机模型并行计算研究

基本信息

批准号：
05780255
负责人：
藤田聡
金额：
$ 0.51万
依托单位：
Hiroshima University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Encouragement of Young Scientists (A)
财政年份：
1993
资助国家：
日本
起止时间：
1993 至无数据
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-05780255/
关键词：
並列計算マルチプロセッサ共有バス放送ゴシップ問題

项目摘要

共有バス結合は、並列計算機のための最も実用的な結合方式のひとつである。従来共有バス結合は、安価であることの代償として、通信のバンド幅が非常に狭いという制約をもつものと認識されてきたが、近年のハードウェア技術の進歩は、共有バスの多重化・階層化という手法によってこの問題点を克服しつつある。今年度の研究では特に、二次元状に配置されたプロセッサを複数のバスで結合するモデルに着目し、そのような計算機上で効率的に情報交換をおこなうための新しい方式を提案した。この通信モデルに基づく並列プロセッサシステムはすでに多くの研究機関で稼働しており、それらのシステムをより効率的に運用する上でも、本研究の意義は大きいものと期待される。主な結果は以下の通りである:1.プロセッサ間で情報交換をおこなう問題(この問題は一般に、ゴシップ問題と呼ばれている)を上記モデル上で考察し、その実行時間の厳密な解析を行った。この結果は同時に、このモデル上でのゴシップに関する非常に効率の良いアルゴリズムも与えている。2.1回の通信あたりの転送情報量をパラメータとして、上の結果をより現実的なモデル上で拡張した。通信1回あたりの転送情報量が大きくなるにしたがって、効率の良いアルゴリズムの性質が、集中的なものから分散的なものへと徐々に変化することが新たな知見として得られた。今後の課題として、この関係を系の持つエントロピーの増大などの観点からより詳しく評価することがあげられる。3.バスモデルのひとつの変形としてワ-ムホール転送モデルに着目し、同様の処理を対象として考察をおこなった。ワ-ムホール転送モデルは動的に経路の変化する一種のバスと見なすこともでき、この考察を通して、多重バスのひとつの発展の方向を示すことができるのではないかと期待している。

共享总线耦合是并行计算机最实用的耦合方法之一。传统上，共享总线耦合被认为具有极窄通信带宽的限制，作为低成本的权衡，但硬件技术的最新进展已经实现了共享总线复用和层次结构，这一问题正在通过一种称为“共享总线”的方法得到解决。今年的研究特别关注二维排列的处理器通过多个总线连接的模型，并提出了一种在此类计算机上有效交换信息的新方法。基于这种通信模型的并行处理器系统已经在许多研究机构中运行，这项研究预计对于更有效地运行这些系统具有重要意义。主要结果如下： 1.我们利用上述模型考虑处理器之间交换信息的问题（该问题一般称为gossip问题），并对其执行时间进行了严格的分析。这个结果也为该模型上的八卦提供了一种非常有效的算法。 2. 我们使用每次通信传输的信息量作为参数，将上述结果扩展到更现实的模型。一个新的发现是，随着每次通信传输的信息量的增加，高效算法的特征逐渐从集中式转变为分散式。未来的挑战是从增加系统熵的角度更详细地评估这种关系。 3.我们重点关注虫洞传输模型作为总线模型的修改，并考虑类似的处理。虫洞传输模型可以看作是一种路线动态变化的总线，我们希望这种考虑能够指明复用总线的发展方向。