JPH09190421A - 計算機のデータ通信システム - Google Patents

Abstract

(57)【要約】 【課題】 多数の要素プロセッサを接続したシステムの
構築のために、各要素プロセッサ中での演算処理とプロ
セッサ間通信処理との独立化、並びにプロセッサ間通信
のためのネットワークシステムの最適化を実現すること
が課題である。 【解決手段】 多数のプロセッサＰＥがトーラス接続さ
れる計算機のデータ通信システムに於て、各プロセッサ
ＰＥは、データ処理を行うデータ処理部と、行方向及び
列方向夫々四方の隣接プロセッサとの結合の為に４個の
双方向の入出力ポートを備えた通信制御部と、を有し、
且つ前記各入出力ポートに１パケット分の情報量のみを
持つ入力レジスタｒ並びに出力レジスタｒと、前記４個
の入力レジスタｒ及び前記データ処理部の入力側にそれ
ぞれ対応して設けられた５個の合流制御回路部と、前記
４個の出力レジスタｒ及び前記データ処理部の出力側に
それぞれ対応して設けられた５個の分岐制御回路部と、
を備える。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、計算機、特にデー
タ駆動計算機のデータ通信システムに関する。

【０００２】

【従来の技術】近年、実用的な並列処理計算機の実現に
向けて研究が進められており、本願発明者は、既にデー
タ駆動計算機とその言語処理系ソフトウェアの開発、及
びそれらの評価を終了している。

【０００３】［田中他：「データ駆動計算機ＳＰＭの試
作」、情報処理学会第３６回全国大会講演論文集７Ｂ−
５。

【０００４】西川他：「データ駆動計算機ＳＰＭのコン
パイラ」、同７Ｂ−６。

【０００５】田中他：「データ駆動計算機ＳＰＭの性能
評価（１）」情報処理学会第３７回全国大会講演論文集
１Ｎ−４。

【０００６】岡本他：「データ駆動計算機ＳＰＭの性能
評価（２）」同１Ｎ−５。］ 一般に、データ駆動計算機は、種々の命令がデータの流
れを示すアークによって接続されるデータフローグラフ
をプログラムとして実行するものであり、言い替えれ
ば、「処理可能なデータから処理を実行していく」とい
うような非ノイマン型の思想に従い簡単な実行規則によ
って演算処理が行われる。

【０００７】斯様なデータ駆動計算機は、主としてデー
タ対検出機構、演算処理機構、プログラム記憶機構の三
つの構成要素からなり、その実行処理の概略は以下のと
おりである。

【０００８】まず、データ駆動型計算機ではパケットと
呼ばれる一まとまりのデータ集合を単位として使用して
おり、該パケットは処理対象データ、データフローグラ
フの接続情報（ノード番号）並びに命令コードなどから
構成される。

【０００９】このデータ対検出機構では演算が可能なオ
ペランドパケットの組を検出して出力する。そして検出
されたオペランドパケットの組は演算処理機構で処理さ
れる。この結果、パケットはプログラム記憶機構で新た
なノード番号を付与されデータ対検出機構に送られる。
斯る処理を繰り返し続けることにより一連の処理が実行
される。

【００１０】本願発明者は、現在、上述の如きデータフ
ロー計算機に於て、特にそのプロセッサアーキテクチャ
に種々の改良を加えた高並列データ駆動計算機ＥＤＤＥ
Ｎ（Enhanced Data Driven ENgine）の開発を進めてい
る。

【００１１】このＥＤＤＥＮでは、１チップのＣＭＯＳ
−ＬＳＩによって実現する要素プロセッサを、最大１０
２４台接続した大規模データ駆動計算機の稼働を目指
し、また、ＰＥ数台の小規模システム、ＰＥ数十台の中
規模システムなど柔軟な構成がとれるようにし、信号処
理、画像処理、グラフィックス、各種シミュレーショ
ン、ＣＡＤなどの広範な分野に適応されることが目標と
なっている。

【００１２】

【発明が解決しようとする課題】上述の如く、多数の要
素プロセッサを接続したシステムの構築のためには、各
要素プロセッサ中での演算処理とプロセッサ間通信処理
との独立化、並びにプロセッサ間通信のためのネットワ
ークシステムの最適化等が要求され、これ等の実現によ
って高性能計算機が得られる。

【００１３】

【課題を解決するための手段】本発明の計算機のデータ
通信システムは、多数のプロセッサを行列配置し、各縦
方向のプロセッサ列を循環的に結合する複数の縦通信線
と各横方向のプロセッサ行を循環的に結合する複数の横
通信線とでプロセッサ間のデータ通信を行う計算機のデ
ータ通信システムに於て、各プロセッサは、データ処理
を行うデータ処理部と、行方向及び列方向夫々四方の隣
接プロセッサとの結合の為に４個の双方向の入出力ポー
トを備えた通信制御部と、を有し、且つ前記各入出力ポ
ートに１パケット分の情報量に該当する記憶容量を持つ
入力レジスタ並びに出力レジスタと、前記各入出力ポー
トの出力レジスタ及び前記データ処理部の入力側にそれ
ぞれ対応して設けられた５個の合流制御回路部と、前記
各入出力ポートの入力レジスタ及び前記データ処理部の
出力側にそれぞれ対応して設けられた５個の分岐制御回
路部と、を備え、前記通信制御部は、前記分岐制御回路
部に送られた、入力レジスタから入力された通信データ
又は前記プロセッサから得られる処理データを前記合流
制御回路部に送るように制御し、また前記通信制御部
は、前記合流制御回路部に送られた前記処理データを前
記出力レジスタに、又は前記合流制御回路部に送られた
前記通信データを前記出力レジスタ或いは前記データ処
理部に送るように制御することを特徴とする。

【００１４】特に、前記通信制御部の内部は、自己同期
式で動作することを特徴とする。

【００１５】

【発明の実施の形態】図１に本発明の一実施形態として
の高並列データ駆動計算機のシステムを示し、図２に要
素プロセッサの構成を示す。

【００１６】まず、図２の要素プロセッサ（ＰＥ）は、
基本的にはプログラム記憶（ＰＳ）、発火制御・カラー
管理部（ＦＣＣＭ）、命令実行部（ＥＸＥ）、及びキュ
ーメモリ（Ｑ）が巡回パイプライン（リング）構造に接
続された構成としている。

【００１７】プログラム記憶（ＰＳ）はノード番号の更
新、定数付与、及び結果のコピーを行う。発火制御・カ
ラー管理部（ＦＣＣＭ）は、２段階の待ち合わせ記憶方
式で発火制御及びカラーの獲得・解放の管理を行う。命
令実行部（ＥＸＥ）は、浮動小数点・整数演算、条件判
定、分岐、簡易定数発生などの命令、及びそれらの複合
命令を実行する。

【００１８】キュー（Ｑ）はリング上でのあらゆるデー
タ流変動を吸収する緩衝記憶である。緩衝記憶が必要と
なるのは、コピー、リングへの強制的入力、リン
グからの出力遅延、（ＦＣＣＭ）における待ちリスト
のサーチ、などが生じた時である。本要素プロセッサ
（ＰＥ）には、キュー（Ｑ）のデータ滞在量に応じて
〜の動作モードを動的に変更する機能を付加し、これ
によって並列度の制御を行う。

【００１９】また、キュー（Ｑ）がやむなくオーバーフ
ローした時には、外部データメモリ（ＥＤＭ）上に外部
キューを形成してこれを吸収し、プログラム実行の継続
を図る。

【００２０】ネットワーク制御部（ＮＣ）は、東西南北
４系統の通信ポートを保持し、最大１０２４台のプロセ
ッサ（ＰＥ）のトーラス結合網に基づくルーティング制
御を行う。ベクトル演算制御部（ＶＣ）は、ベクトル演
算関連命令、及び通常のメモリアクセス命令の実行制御
を行う。前記制御部（ＶＣ）と、入力制御部（ＩＣ）及
び出力制御部（ＯＣ）の間には構造体（ベクトル）通信
用のバイパス線を設ける。外部データメモリ（ＥＤＭ）
は、構造体等を格納するデータメモリであり、容量は５
１２ＫＢｙｔｅ（１２８Ｋ語×３２ｂｉｔ）程度とす
る。クロック方式は同期式であるが、上記ネットワーク
制御部（ＮＣ）内部は自己同期式で動作するものとす
る。

【００２１】斯様な要素プロセッサ（ＰＥ）を多数用い
たＥＤＤＥＮの基本的な構成は図１に示すようにｎ×ｎ
台の要素プロセッサをトーラス結合網で接続することを
基本とする。該トーラス結合網とは、多数のプロセッサ
を行列配置し、各縦方向、即ち南北方向（Ｎ ＜−＞
Ｓ）のプロセッサ列を循環的に結合する複数の縦通信線
と各横方向、即ち東西方向（Ｗ ＜−＞ Ｅ）のプロセ
ッサ行を循環的に結合する複数の横通信線とで任意のプ
ロセッサ間のデータ通信を可能としたものである。

【００２２】本実施形態システムでは、ネットワークと
のデータのやりとりは、南北方向（Ｎ ＜−＞ Ｓ）の
任意の通信リンクにネットワークインタフェース（ＮＩ
Ｆ）を挿入することによって行う。前記インタフェース
（ＮＩＦ）、及び要素プロセッサ１６〜６４台を１枚の
プロセッサボート上に実装し、トーラス接続リンクをプ
リント基板上に形成する。

【００２３】小・中規模システムの構成としては、ホス
ト計算機として汎用のＥＷＳまたはパソコンを用い、そ
れらのバスインタフェースを介してネットワークインタ
フェース（ＮＩＦ）に接続する。実装形態としては、１
〜４枚のプロセッサボードと１枚のバスインタフェース
ボードを、ＥＷＳ等のラックに直接挿入することにす
る。

【００２４】大規模システムの構成としては、応用分野
に応じて、次の２種類の構成法が考えられる。

【００２５】 クラスタ接続 前述のプロセッサボードを１つのクラスタとして、クラ
スタ間をクラスタインタフェースを介して接続する。ク
ラスタインタフェースは、各クラスタ内のデータの収集
・分配の管理を行う。

【００２６】 大型トーラス接続 １０２４台（３２台×３２台）の要素プロセッサをトー
ラス結合網で接続する。実装形態としては、１枚のプリ
ント基板に南北（Ｎ ＜−＞ Ｓ）方向の３２台の要素
プロセッサとＮＩＦとを実装し、東西（Ｗ ＜−＞
Ｅ）方向のリンクはマザーボード上に形成する。

【００２７】上述の構成のデータ駆動計算機で用いられ
るデータパケットには、大別して、プログラム実行に使
用する実行パケットとプログラム実行以外に使用される
非実行パケットがあり、図４及び図５にその実例を示し
ている。尚、パケット形式は、構造体本体を保持したパ
ケット以外は固定長とし、プロセッサ（ＰＥ）内のパイ
プラインリング上では３３ビット×２語、ネットワーク
上では１８ビット×４語構成を採用している。

【００２８】以下に、図４及び図５のパケットフォーマ
ットに於ける各フィールドの内容を示す。

【００２９】ＨＤ（１ｂｉｔ）：２語パケットの際の１
語目（ヘッダ）と２語目（テイル）の識別子。ヘッダの
時「１」。

【００３０】ＥＸ（１ｂｉｔ）：パイプラインリング上
からＰＥ外部へ出力されるパケットを識別するフラグ。

【００３１】ＭＯＤＥ（２ｂｉｔ）：実行パケット、非
実行パケット等のパケットの種類を識別する識別コー
ド。

【００３２】Ｓ−ＣＯＤＥ（３ｂｉｔ）：ＭＯＤＥと併
せてパケットに対する処理を規定する識別コード。

【００３３】ＯＰＣＯＤＥ−Ｍ（５ｂｉｔ）：メイン命
令コード。命令実行部（ＥＸＥ）における命令の種類を
規定する。また、ｎｓｙｎｃの際に同期処理を行うデー
タの数を保持する。

【００３４】ＯＰＣＯＤＥ−Ｓ（６ｂｉｔ）：サブ命令
コード。メイン命令コードで規定された命令を更に詳細
に規定する。

【００３５】ＮＯＤＥ＃（最大１１ｂｉｔ）：データフ
ローグラフのノード番号。

【００３６】ＣＯＬＯＲ（４ｂｉｔ）：カラー識別子。
サブルーチンコールによるプログラム共用、時系別デー
タに対する処理など、同一データフローグラフを多重実
行する際に環境を識別する識別番号。

【００３７】ＰＥ＃（１０ｂｉｔ）：ＰＥ番号。最大１
０２４台のＰＥを識別するための識別番号。

【００３８】ＤＡＴＡ（３２ｂｉｔ）：３２ビットの整
数あるいは浮動小数点数。

【００３９】ＨＴ（１ｂｉｔ）：語数が４語以上のパケ
ットの際に、ヘッダ及びテイルと中間の語とを識別する
フラグヘッダまたはテイルの時に「１」となる。

【００４０】ＲＱ（１ｂｉｔ）：ネットワーク上を転送
されるパケットに付加するフラグで、ネットワーク上で
１語転送される度に値が反転するため、語の存在を認識
できる。更に、値が反転することが、パケットを前方ヘ
転送するための転送要求信号となる。また、ＨＴフラグ
と合わせて、ヘッダとテイルとを識別できる。

【００４１】ＡＤＤＲＥＳＳ（１６ｂｉｔ）：各メモリ
のデータのロード／ダンプなどの際に、メモリアドレス
を格納する。

【００４２】以上の基本構成を持つ本発明実施形態の計
算機の特徴的な構成は、要素プロセッサ（ＰＥ）での本
来のデータ処理のための各機構とは独立して動作するネ
ットワーク制御部（ＮＣ）にある。

【００４３】前記ネットワーク制御部（ＮＣ）は図４
（ｃ）及び図５（ｅ）の如きパケットを当該プロセッサ
（ＰＥ）から受け取り、又は他のプロセッサ（ＰＥ）か
ら受け取って、そのパケットの第１語目にある［ＰＥ
＃］を検知する。この［ＰＥ＃］には該パケットが転送
されるべき宛先のプロセッサの行列番号形式の宛先のプ
ロセッサ番号（Ｘ，Ｙ）が書き込まれているので、この
値と当該プロセッサの番号（ｘ，ｙ）との比較を行う。

【００４４】この比較処理により、例えば、Ｘ＝ｘでな
い限り、パケットを西（Ｗ）から東（Ｅ）へ、あるいは
東（Ｅ）から西（Ｗ）へ転送する。

【００４５】Ｘ＝ｘであれば、Ｙ＝ｙでない限りパケッ
トは南（Ｓ）から北（Ｎ）へ、あるいは北（Ｎ）から南
（Ｓ）へ転送する。

【００４６】そして、Ｘ＝ｘ且つＹ＝ｙとなった時にこ
のパケットが当該プロセッサ内でのデータ処理に供せら
れるのである。

【００４７】従って、データパケットはトーラス結合さ
れた多数の行列プロセッサ間を、まず、東西方向に転送
され、その後南北方向に転送される事になり、これによ
って、最短距離転送のセルフルーティングを実現してい
る。

【００４８】図３に上述の如きトーラスネットワーク上
でのセルフルーティングを実現する為のネットワーク制
御部（ＮＣ）のデータシステムを模式的に示し、同図に
従い、そのルーティングアルゴリズムを示す。尚、図３
に於て、（ＲＮＩ）（ＲＮＯ）は北入出力ポートを構成
する入力シフトレジスタ、及び出力シフトレジスタであ
り、４段のレジスタ（ｒ）からなる。同様に（ＲＳＩ）
（ＲＳＯ）は南入出力ポート、（ＲＷＩ）（ＲＷＯ）は
西入出力ポート、（ＲＥＩ）（ＲＥＯ）は東入出力ポー
トを構成している。又、「○」は合流、「◎」は分岐を
示している。

【００４９】ルーティングアルゴリズムは以下のとお
り。 Ｉ．自分のＰＥ番号を（ｘ，ｙ）、ネットワークをｐ×
ｑ（ｐ：Ｎ −＞ Ｓ方向、ｑ：Ｗ −＞ Ｅ方向）のトー
ラス、パケットの行き先ＰＥ番号を（Ｘ，Ｙ）とし、

【００５０】

【数１】

【００５１】とする。 II．ＰＥ番号は、ＮからＳの方向に順に ｙ＝０、１、２、・・・、ｐ ＷからＥの方向に順に ｘ＝０、１、２、・・・、ｑ とする。 III．ＭＯＤＥはパケットのタグのＭＯＤＥフィールド
の値を意味する。（ＭＯＤＥ＝００はホストへのパケッ
トである。） （１）Ｒ１ Δｙ＝０のときパケットをＰへ出力 Δｙ≠０のときパケットをＳへ出力 （２）Ｒ２ Δｘ≠０のときパケットをＷへ出力 Δｘ＝０かつΔｙ＞０のときパケットをＳへ出力 Δｘ＝０かつΔｙ＝０かつＭＯＤＥ≠００のときパケッ
トをＰへ出力 Δｘ＝０かつΔｙ＝０かつＭＯＤＥ＝００のときパケッ
トをＮへ出力 Δｘ＝０かつΔｙ＜０のときパケットをＮへ出力 （３）Ｒ３ Δｘ≠０のときパケットをＥへ出力 Δｘ＝０かつΔｙ＞０のときパケットをＳへ出力 Δｘ＝０かつΔｙ＝０かつＭＯＤＥ≠００のときパケッ
トをＰへ出力 Δｘ＝０かつΔｙ＝０かつＭＯＤＥ＝００のときパケッ
トをＮへ出力 Δｘ＝０かつΔｙ＜０のときパケットをＮへ出力 （４）Ｒ４ Δｙ＝０かつＭＯＤＥ≠００のときパケットをＰへ出力 Δｙ≠０またはＭＯＤＥ＝００のときパケットをＮへ出
力 （５）Ｒ５ Δｘ＞０のときパケットをＥへ出力 Δｘ＝０かつΔｙ＞０のときパケットをＳへ出力 Δｘ＝０かつΔｙ≦０のときパケットをＮへ出力 Δｘ＜０のときパケットをＷへ出力 IV．パケットのヘッダが到着したときにルーティングを
行い、以降のデータはパケットのテイルが到着するま
で、同じ経路に出力する。 Ｖ．ＰＥ番号（ｘ，ｙ）とネットワークのサイズは、あ
らかじめ設定できるものとする。ただし、ｐ、ｑは２の
べき乗に限る。また、Δｘ、Δｙを計算するときに、モ
ジェロをとらないモード（格子状ネットワークに対応）
ことも可能とする。 VI．ＰＥをリング状に接続する場合も、Ｎ−Ｓを結線す
れば、上のルーティングアルゴリズムでルーティングで
きる。

【００５２】以上がセルフルーティングアルゴリズムの
１例であるが、これに限られるものでない。

【００５３】一方、図３のネットワーク制御部（ＮＣ）
の入出力ポートの構成は、図示の如く、４段の各１８ビ
ットのシフトレジスタ（ｒ）・・・の入力ポート、同じ
く４段のシフトレジスタ（ｒ）・・・の出力ポートを備
えているので、図４（ｃ）、図５（ｅ）の４語形式のパ
ケットがそのまま全て入力ポート、あるいは出力ポート
に格納できる事になる。この事は、トーラスネットワー
クのように双方向通信が必要な双方向通信路上で、一方
向の前にパケットがつかえている状態でこの方向のパケ
ット転送が停止していても、パケット単位がポート部で
中断して停止すると云うデッドロックの原因の一つを解
消する事になる。即ち、例えば入出力ポートの入力側あ
るいは出力側に１まとまりのパケットが完全に格納され
るので、当該プロセッサで、他のパケットの他の方向へ
の転送が可能となる。

【００５４】本実施形態では、多数のプロセッサがトー
ラス接続されるネットワークシステムを採用すると共
に、各プロセッサに主にプロセッサ間通信のための通信
制御部をデータ処理部とは独立して設けたものであるの
で、プロセッサのＬＳＩ化実現の際に、上記トーラス接
続によりピン数削減、一様構造が図れ、上記通信制御部
の独立性を保った形のＬＳＩ内蔵により、システム全体
の小型化、低価格化が望める。

【００５５】また、本実施形態では、行方向及び列方向
夫々四方の隣接プロセッサとの結合の為に４個の双方向
の入出力ポートを備え、各ポートに通信データの基本的
情報量に該当する記憶容量をもつ入力レジスタ並びに出
力レジスタを具備する。

【００５６】このように、本実施形態では、四方の隣接
プロセッサとの入出力を行う４個の入出力ポートに夫々
通信データの基本的情報量、即ち１パケット分の情報量
をもつ入力レジスタと出力レジスタとを一対にして備え
ているので、データ転送毎に必ずパケット単位でプロセ
ッサ間のデータ転送が完了できる。従って、パケット単
位の途中でデータ転送が停滞する事がないので、停滞デ
ータが他のデータの通信を妨げると云ったデッドロック
現象の回避が可能となる。

【００５７】更に、本実施形態では、行列番号と対応付
けられて行列結合された複数のデータフロー型のプロセ
ッサ間で通信データの送受信を行うデータ通信方法であ
り、上記通信データには、送信先プロセッサに対応づけ
られた行列番号が送信先行列番号として書き込まれてお
り、上記各プロセッサは、該プロセッサ自身の行列番号
と該プロセッサに転送されて来た通信データの送信先行
列番号とを比較し、両番号が一致する時の通信データを
該プロセッサでデータ処理し、不一致の時の通信データ
を隣接プロセッサに転送するものである。

【００５８】このように、本実施形態では、通信データ
中に送信先プロセッサ番号（対応行列番号）が書き込ま
れているので、各プロセッサでは内部的に発生したデー
タ、あるいは他のプロセッサから転送されて来たデータ
の送信先プロセッサ番号を検知してこのデータを四方の
隣接プロセッサの内、いずれのプロセッサに転送すべき
かがプロセッサ自身で判断できる。従って、データは各
プロセッサの転送動作により、最短ルートで宛先プロセ
ッサに通信できるセルフルーティングを実現できる。

【００５９】

【発明の効果】本発明によれば、システム全体の小型
化、低価格化のために、通信制御機構をもＰＥチップに
内蔵でき、プロセッサの基本的な結合状態により、チッ
プのピン数制限、プロセッサ間距離が小さい、一様構
造、デッドロック回避が可能、実装が容易となるデータ
通信システムを実現する事ができる。

【図面の簡単な説明】

【図１】本発明の一実施形態に係るデータ通信システム
を示すシステム図である。

【図２】本発明の一実施形態に係るプロセッサの概略構
成を示すブロック図である。

【図３】本発明の一実施形態に係るプロセッサの要部ゲ
ート構成の模式図である。

【図４】パケット構成図である。

【図５】パケット構成図である。

【符号の説明】

ＰＥ 要素プロセッサ ＥＸＥ 命令実行部 ＥＤＭ 外部データメモリ ＮＣ ネットワーク制御部

Claims (2)

【特許請求の範囲】
1. 【請求項１】 多数のプロセッサを行列配置し、各縦方
   向のプロセッサ列を循環的に結合する複数の縦通信線と
   各横方向のプロセッサ行を循環的に結合する複数の横通
   信線とでプロセッサ間のデータ通信を行う計算機のデー
   タ通信システムに於て、 各プロセッサは、データ処理を行うデータ処理部と、行
   方向及び列方向夫々四方の隣接プロセッサとの結合の為
   に４個の双方向の入出力ポートを備えた通信制御部と、
   を有し、 且つ前記各入出力ポートに１パケット分の情報量に該当
   する記憶容量を持つ入力レジスタ並びに出力レジスタ
   と、 前記各入出力ポートの出力レジスタ及び前記データ処理
   部の入力側にそれぞれ対応して設けられた５個の合流制
   御回路部と、 前記各入出力ポートの入力レジスタ及び前記データ処理
   部の出力側にそれぞれ対応して設けられた５個の分岐制
   御回路部と、を備え、 前記通信制御部は、前記分岐制御回路部に送られた、入
   力レジスタから入力された通信データ又は前記プロセッ
   サから得られる処理データを前記合流制御回路部に送る
   ように制御し、また前記通信制御部は、前記合流制御回
   路部に送られた前記処理データを前記出力レジスタに、
   又は前記合流制御回路部に送られた前記通信データを前
   記出力レジスタ或いは前記データ処理部に送るように制
   御することを特徴とする計算機のデータ通信システム。
2. 【請求項２】 前記通信制御部の内部は、自己同期式で
   動作することを特徴とする請求項１記載の計算機のデー
   タ通信システム。