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

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 （イン　産業上の利用分野 本発明は、計算機、特にデータ駆動計算機のデータ通信
システム、該システムに用いるプロセッサ、並びにデー
タ通信方法に関する。

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

［田中他：　「データ駆動計算機ＳＰＭの試作」、情報
処理学会第３６口金国大会講演論文集７　Ｂ　−５゜ 西用他＝　「データ駆動計算機ＳＰＭのコンパイラ」、
同７Ｂ−６゜ 田中他：　「データ駆動計算機ＳＰＭの性能評価（１）
」情報処理学会第３７口金国大会講演論文集ｌＮ−４゜ 岡本他：　「データ駆動計算機ＳＰＭの性能評価（２）
」同ｌＮ−５゜〕 一般に、データ駆動計算機は、種々の命令がデータの流
れを示すアークによって接続されるデータ７０−グラフ
をプログラムとして実行する６のであり、言い替えれば
、「処理可能なデータから処理を実行していく」という
ような非ノイマン型の思想に従い簡単な実行規則によっ
て演算処理が行なノ）れる。

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

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

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

本願発明者は、現在、上述の如きデータフロー計算機に
於て、特にそのプロセッサアーキテクチャに種々の改良
を加えた高並列データ駆動計算機Ｅ　Ｄ　Ｄ　Ｅ　Ｎ　
（Ｅｎｈａｎｃｅｄ　Ｄａｔａ　Ｄｒｉｖｅｎ　ＥＮｇ
ｉｎｅ）の開発を進めている。このＥＤＤＥＮでは、ｌ
チップのＣ＼１０５−ＬＳＩによって実現する要素プロ
セッサを、最大ｌＴ１２４台接続した大規模データ駆動
計算機の稼働を目指し、また、ＰＥ数台の小規模システ
ム、ＰＥ数十台の中規模システムなど柔軟な構成がとれ
るようにし、信号処理、画像処理、グラフィックス、各
種シミュレーション、ＣＡＤなどの広範な分野に適応さ
れることが目標となっている。

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

（ニ）課題を解決するための手段 本発明のデータ通信システムは、多数のプロセッサを行
列配置し、各縦方向のプロセッサ列を循環的に結合する
複数の縦通信線と各横方向のプロセッサ行を循環的に結
合する複数の横通信線とでプロセッサ間のデータ通信を
行う計算機のデータ通信システムであり、各プロセッサ
は少なくともデータ処理部と通信制御部とからなり、該
通信制御部が該データ処理部から得られる処理データを
縦方向線、或は横方向線のいずれかの方向のプロセッサ
に選択的に転送する通信制御、並びに、該通信制御部が
隣接プロセッサから縦方向線あるいは横方向線を介して
得られるデータを該プロセッサのデータ処理部に供給す
るか、又は縦方向線あるいは横方向線のいずれかの方向
のプロセッサに選択的に転送する通信制御を司るもので
ある。

本発明のデータ通信シテスムのプロセッサは、行方向及
び列方向夫々四方の隣接プロセッサとの結合の為に４個
の双方向の入出力ポートを備え、各ポートに通信データ
の基本的情報量に該当する記憶容量を持つ入力レジスタ
、並びに出力レジスタを具備したものである。

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

（ホ）作用 本発明のデータ通信シテスムによれば、多数のプロセッ
サがトーラス接続さノＬるネットワークシステムを採用
すると共に、各プロセッサに主にプロセッサ間通信のた
めの通信制御部をデータ処理部とは独立して設けたもの
であるので、プロセッサのＬＳＩ化実現の際に、上下ト
ーラス接続によりビン数削限、−様構造が図れ、上記通
信制御部の独立性を保った型のＬＳＩ内蔵により、シス
テム全体の小型化、低価格化が望める。

また、本発明システムのプロセッサは、四方の隣接プロ
セッサとの入出力を行う４個の入出力ポートに夫々通信
データの基本的情報量、即ち１パケット分の情報量を持
つ入力レジスタと出力レジスタとを１対にして備えてい
るので、データ転送毎に必ずパケ・ｌト単位でプロセッ
サ間のデータ転送が完ｒできる。従って、パケット単位
の途中でデータ転送が停帯する事がないので、停帯デー
タが他のデータの通信を妨げると云ったデッドロック現
象を回避が可能となる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以下に、第４図のパケットフォーマットに於ける各フィ
ールドの内容を示す。

ＨＤ（ｌｂｉｔ月２８５パケツトの際の１語目（ヘッダ
）と２語目（テイル）の識別子。ヘッダの時　１“ＥＸ
（ｌｂｉｔ戸パイプラインリング上からＰＥ外部へ出力
されるパケットを識別するフラグ ５ＩＯＤＥ（２ｂｉｔ戸実行パケット、非実行パケット
等のパケットの種類を識別する識別コード ５−ＣＯＤＥ（３ｂｉｔ）：〜ｌ０ＤＥと合わせてパケ
ットに対する処理を規定する識別コード ＯＰＣＯＤＥ−Ｍ（５ｂｉｔ）：メイン命令コード。命
令実行部（ＥＸＥ）における命令の種類を規定する。ま
た、ｎ５ｙｎｃの際に同期処理を行うデータの数を保持
する。

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

聞ＯＤＥ＊（最大１１ｂｉｔ）：データフローグラフの
ノード番号 Ｃ０ＬＯＲ（４ｂｉ　ｔ）：カラー識別子。サブルーチ
ンコールによるプログラム共用、時系別データに対する
処理なと、同一データフローグラフを多重実行する際に
環境を識別する職別番号。

ＰＨ１（ＬＯｂｉｔ）：ＰＥ番号。最大１０２４台のＰ
Ｅを識別するための識別番号。

ＤＡＴＡ（３２ｂｉ　ｔ）：　３２ビツトの整数あるい
は浮動少数点数。

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

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

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

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

該ネットワーク制御部（ＮＣ）は第４図（ｃ）及び同図
（ｅ）の如きパケットを当該プロセッサ（ＰＥ）から受
けとり、又は他のプロセッサ（ＰＥ）から受けとって、
そのパケットの第１語口にある（ＰＥ＠Ｉを検知する。

この［ＰＥ番］には該パケットが転送されるべき宛先の
プロセッサの行列番号形式の宛先のプロセッサ番号（ｘ
、ｙ）が書き込まれているので、この値と当該プロセッ
サの番号（ｘ、　　ｙ）との比較を行われる。

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

Ｘ＝ｘであれば、ｙ＝ｙでない限りパケットは市（Ｓ）
から北（Ｎ）へ、あるいは北（Ｎ）がら南（Ｓ）・＼転
送する。

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

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

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

ルーティングアルゴリズムは以下のとおり。

■、自分のＰＥ番号を（ｘ、ｙ）、ネットワークをｐＸ
ｑ（ｑ：Ｎ−＊Ｓ方向、ｑ：Ｗ−４Ｅ方向）のトーラス
、パケットの行き先ＰＥ番号を（ｘ、ｙ）とし、 △Ｘミ（Ｘ　−ｘ　）ｍｏｄ　ｑ　　ｌ△ｘ１≦ｑ／２
△ｙミ（Ｙ−１）ｍｏｄｐ　　ｌ△ｙ１≦ｐ／２とする
。

１１、ＰＥ番号は、ＮからＳの方向に順にｙ＝ｏ、１．
２、・・・　ｐ ＷからＥの方向に順に ｘ＝Ｏ１ｌ、２、・・・、ｑ　　　　とする。

１１■、＼ｌ０ＤＥはパケットのタグの＼ｌ０ＤＥフィ
ールドの値を意味する。（〜ｌ０ＤＥ−（１０はホスト
へのパケットである。） （１）Ｒ１ △ｙ＝ＱのときパケットをＰへ出力 Δｙ≠０．のときパケットをＳへ出力 （２）Ｒ２ △Ｘ≠０のときパケットをＷへ出力 △ｘ＝Ｏかつ△ｙ〉０のときパケットをＳへ出力 △ｘ＝０かつ△ｙ＝ＱかつＭＯＤＥ≠、００のときパケ
ットをＰへ出力 Δｘ　＝　ＯかつΔｙ＝０がッＭＯＤＥ＝００のときパ
ケットをＮへ出力 Δｘ＝０かつ△ｙくＯのときパケットをＮへ出力 （３）Ｒ３ Δｘ＋ＱのときパケットをＥへ出力 Δｘ＝０かつ△ｙ〉０のときパケットをＳへ出力 Δｘ＝ＯかツＬ　ｙ　＝　ＯかつＭ　ＯＤ　Ｅ≠００の
ときパケットをＰへ出力 △Ｘ＝Ｏかつ△ｙ＝Ｑかつ！＋ｌ０ＤＥ＝００のときパ
ケットをＮ・入出力 △ｘ＝Ｏかつ△ｙ〈０のときパケットをＮへ出力 （４）Ｒ４ Δ〜＝＝０かつＭＯＤＥ≠００のときパケットをＰへ出
力 ニ−・≠０またはＭＯＤＥ＝　００のときパケットをＮ
へ出力 （５）Ｒ５ △ｘ＞ＯのときパケットをＥへ出力 △ｘ＝Ｏかつ△ｙ〉０のときパケットをＳへ出力 △ｘ＝ＯかつΔ）ｒ≦ＯのときパケットをＮへ出力 △ｘ＜０のときパケットをＷへ出力 ■、パケットのヘッダが到着したときにルーティングを
行い、以降のデータはパケットのテイルが到着するまで
、同じ経路に出力する。

Ｖ、Ｐ　Ｅ番号（Ｘ、Ｙ）とネットワークのサイズは、
あらかじめ設定できるものとする。ただし、ｐ、（１は
２のべき乗に限る。また、△Ｘ、△ｙを計算するときに
、モジユロをとらないモード（格子状ネットワークに対
応）ことら可能とする。

Ｖｌ　、　Ｉ’　Ｅをリング状に接続する場合ら、Ｎ　
−Ｓを結線すれば、上のルーティングアルゴリズムでル
ーティングできる。

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

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

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

【図面の簡単な説明】

第１図は本発明のデータ通信システムを示すシステム図
、第２図は本発明のプロセッサの蜆略構成を示すブロッ
ク図、第３図は本発明プロセッサの要部ゲート構成の模
式図、第４図（ａ）乃至（ｅ）はパケット構成図である
。 （ＰＥ）・・・要素プロセッサ、（ＥＸＥ）・・・命令
実行部、（ＥＤ〜１）・・・外部データメモリ、（ＮＣ
）・・・ネットワーク制９１１部。

Claims (3)

【特許請求の範囲】
1. （１）多数のプロセッサを行列配置し、各縦方向のプロ
   セッサ列を循環的に結合する複数の縦通信線と各横方向
   のプロセッサ行を循環的に結合する複数の横通信線とで
   プロセッサ間のデータ通信を行う計算機のデータ通信シ
   ステムに於て、各プロセッサは少なくともデータ処理部
   と通信制御部とからなり、 該通信制御部が該データ処理部から得られる処理データ
   を縦方向線、或は横方向線のいずれかの方向のプロセッ
   サに選択的に転送する通信制御、並びに、該通信制御部
   が隣接プロセッサから縦方向線あるいは横方向線を介し
   て得られるデータを該プロセッサのデータ処理部に供給
   するか、又は縦方向線あるいは横方向線のいずれかの方
   向のプロセッサに選択的に転送する通信制御を司る事を
   特徴とする計算機のデータ通信システム。
2. （２）請求項１記載の計算機のデータ通信システムのプ
   ロセッサに於て、 行方向及び列方向夫々四方の隣接プロセッサとの結合の
   為に４個の双方向の入出力ポートを備え、各ポートに通
   信データの基本的情報量に該当する記憶容量を持つ入力
   レジスタ、並びに出力レジスタを具備したことを特徴と
   するプロセッサ。
3. （３）行列番号と対応付けられて行列結合された複数の
   データフロー型のプロセッサ間で通信データの送受信を
   行うデータ通信方法に於て、上記通信データには、送信
   先プロセッサに対応付けられた行列番号が送信先行列番
   号として書き込まれており、 上記各プロセッサは、該プロセッサ自身の行列番号と該
   プロセッサに転送されて来た通信データの送信先行列番
   号とを比較し、両番号が一致する時の通信データを該プ
   ロセッサでデータ処理し、不一致の時の通信データを隣
   接プロセッサに転送するデータ通信方法。