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

点击翻译按钮获取中文摘要

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