超並列計算システムのモデル化と超並列アルゴリズム

大规模并行计算系统和大规模并行算法的建模

基本信息

批准号：
05219102
负责人：
深澤良彰
金额：
$ 0.64万
依托单位：
Waseda University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research on Priority Areas
财政年份：
1992
资助国家：
日本
起止时间：
1992 至 1994
项目状态：
已结题

项目摘要

ノイマン型のアーキテクチャにおいて超並列化を試みる場合,メモリなどのアクセス競合が大きな問題となる。このため,共有性のメモリを用いているノイマン型コンピュータを高速化しようとする試みには限界が存在する。これに対し,各プロセッサに分散してローカルメモリをもたせることにより,メモリアクセスの競合を避けることができる。これにより,ハードウェウ的にもより並列性の高い,プロセッサ数の多いシステムへの拡張も容易である。このような理由により,同じ形のプロセッサを多数接続し,空間並列的に計算を行なう,セルラ計算機のような分散メモリ型の並列計算システムが生まれてきた。しかし,このような分散メモリ型の並列計算システムにおいては,プロセッサメモリに必要なデータがない場合には通信を行ない,他のプロセッサに必要なデータを送ってもらう必要がある。多数のプロセッサ間では,このような通信をより効果的に行なうためのアルゴリズム,その際の通信遅れの考慮が難しいものとなる。さらに全てのプロセッサ間での自由な通信を実現するためには,通信手段の繁雑化として問題が生じる。このような問題を解決するために,問題を結合律が成立する計算に限定し,さらに,データの分散に関する制約がない場合の計算について,ステップ数が最小となるアルゴリズム(計算順序とそのタイミング)とその構成法を導き出した。ネットワークとしては,同一のクロックを各プロセッサに与えることにより同期をとるものと仮定している。さらにこのアルゴリズムを割りつけるネットワークトボロジおよびデータを割り振る際のデータの分散方法を求める手順を発見した。

当尝试在Neumann体系结构中进行大规模并行化时，访问竞争（例如内存）成为一个主要问题。因此，尝试加快使用共享内存的Neumann计算机的尝试存在局限性。相反，通过将本地内存分配给每个处理器，可以避免内存访问中的冲突。这使得可以轻松扩展到具有较高并行性和更多处理器以及硬件的系统。因此，分布式内存类型并行计算系统（例如蜂窝计算机）已经诞生，它们连接了相同类型的许多处理器并执行空间并行计算。但是，在这样的分布式内存类型并行计算系统中，如果处理器内存没有必要的数据，则需要通信，而其他处理器必须发送必要的数据。很难考虑在许多处理器之间更有效地进行此类沟通的算法以及所涉及的沟通延迟。此外，为了实现所有处理器之间的自由沟通，问题出现了，因为沟通意味着变得更加复杂。为了解决这个问题，我们将问题限制为耦合规则保持真实的计算，此外，我们得出了一种算法（计算顺序和时序），该算法将步骤数及其结构方法最小化，而其计算方法在数据方差无约束时进行计算。作为一个网络，假定通过向每个处理器提供相同的时钟来实现同步。此外，我们发现了一个程序，用于确定网络示意图，用于分配该算法以及如何在分配数据时分发数据。