JPS63501663A - マルチプロセッサ通信装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 本発明は、コンピュータシステム内で使用するための特殊目的の処理ユニットの 分野、特にマルチコンピュータ・データ処理システム内の個々のコンピュータ間 の通信のための通信プロセッサに関するものである。

７オン・ノイマンの基本的コンピュータ・アーキテクチャの改良について数多く の試みがなされてきた。７オン・ノイマンの設計は、メモリに結合された中央処 理ユニットから成るものである。この中央処理ユニットは、メモリに記憶された プログラムにより指定される種々の計算を実行する役目をもっている。これらの 計算に使われるデータもまたそのメモリに記憶されている。このメモリは複数個 の記憶スロットから成立っており、これらはワードと呼ばれる。中央処理ユニッ ト自体の記憶容量は極めて小さい。一般的には、中央処理ユニットはメモリから 次の実行する命令を取出し、次に中央処理ユニットにまだ入っていない必要なデ ータを取出し、その問題の命令を実行し、そしてその結果をメモリに記憶し戻す 。

基本的なフォン・ノイマンのシステムは、中央処理ユニットのスピードで、シス テムのスピードが制限されている。

基本的な７オン・ノイマン設計のスピード限界に対する従来の一つの解決法は、 多数の処理ユニットを同じメモリ・ユニットに接続することである。その夫々の 処理ユニットは、メモリにそれら処理ユニツ、トをリンクする共通バスに対し接 続されている。夫々の処理ユニットは他のユニットから独立してランをする。メ モリをアクセスするために同時にバスをコントロールしようとする二つの処理ユ ニットの間の衝突を解決するために、ある形の調停が用いられる。システムによ って実行されるべきプログラムは、多数の副プログラムに分解され、その各々が 処理ユニットの一つにより実行される。この同時処理の形式によるシステムのス ピード改善能力は、メモリを夫々の処理ユニットにリンクする共通バスの使用が 必要なことで制限される。もし、ある一つの処理ユニットがこれを１０クロツク ・サイクルの間ビジーに保持するのに必要な命令及びデータを得るためにメモリ へのアクセスを１クロツク・サイクルの間必要だとすれば、１０個の処理ユニッ トしかバスに生産的に接続させられない。

それら個々の処理ユニットの内部記憶容量は極めて小さいので、メモリ・アクセ ス・サイクルの計算サイクルに対する比率は、このタイプのシステムでは極めて 大きい。

上述のバス共用システムのスピード限界を解決する従来の一つの方法は、夫々そ れ自身のメモリを持った処理ユニットを使うことである。この設計では、各種の 処理し、そしてそれらの個々のメモリと一つの内部バスを通して通信をする。再 び、そのプログラムは個々のプロセッサによって実行される多数の副プログラム に分けられる。

個々の処理ユニットはかなりの量のメモリを含んでいるので、その通信リンクで の通信に要する時間と、そのような通信のない計算にかかる時間との比率は、上 述のバス共用システムにおけるのと比べて極めて小さい。これは、次の例からも 分ることである。

メモリに記憶された単一のデータワードの使用を要求する９８の命令を持つ簡単 なプログラムについて考え、ばならない第２データワードとする。そのようなデ ータワードの１０００個がこのプログラムで処理されるべきであるという典型的 な状況においては、一つのワードを処理する度毎にメモリは１００回アクセスさ れなければならない。このデータワードは、メモリから取出されねばならない。

次に、プログラムの９８の命令を取出さなければならないが、それにはメモリの 更に９８回のアクセスが必要となる。最後に、結果を記憶させなけれなばらない 。

あるバス共用システムでは、このプログラムをｌｏ。

０個のデータワードに適用するためにメモリがアクセスされねばならない回数は 、１００，０００となる。もし、処理ユニットがそれ自身のメモリを持っていれ ば、通信リンクは、１０００個のデータワードに加えて９８の命令を一度だけ処 理ユニットに送り、そして１０００個の結果のデータワードを処理ユニットから 送り戻すのに使用されることが必要なだけである。このように、この通信リンク は、共用バス・システムで１００，０００のアクセスを必要とした計算動作に対 して僅かに２０９８のアクセスで足りるのである。このことは、より多数の処理 ユニットが同じ通信リンクを共用できることになる。

しかしながら、遅かれ早かれその全ての処理ユニットをサービスする通信リンク の能力に限界がくるので、その数は勝手に多くはできない。

通信リンクが限界にきたときには、もう一つのレベルの通信リンクを設置してピ ラミッド状アーキテクチャを形成しなけれなばらない。諸処理ユニットの二つ以 上のシステムは夫々“クラスタ“と呼ばれるが、これらは“スーパー通信リンク ・プロセッサ”を設けることによって組合わせられ、このスーパー通信リンク・ プロセッサは各クラスタの間でタスクを通信するのに使用され、その各クラスタ は、内部通信リンクを通して個々の処理ユニットにそれらタスクを通信する。こ の通信リンクのオーバロードに対する解決法にはいくつかの問題点がある。

第１に、スーパー通信リンク・プロセッサは、少しのクラスタしか処理できない 。これは、次のことで分る。即ち、スーパー通信リンクは、クラスタ内の個々の バスの一つよりも大きな容量を有していない。この理由は、もし、より大きな容 量を持つスーパー通信リンクを作ることが可能だとしたら、その設計を夫々のク ラスタにも用いることができたはずであるからである。ここで、一つのクラスタ 内の各プロセッサが、その作業をスーパー通信リンクからだけ受取る場合を考え てみる。クラスタ内のプロセッサの数はクラスタ・バスが全容量で動作するよう に選ばれる、即ち、このバスの容量は、スーパー通信リンクから夫々のプロセッ サ用の作業を受取りそしてそれらタスクの結果をスーパー通信リンクを通してリ ターンするのに必要な通信タスクによって飽和させられるのである。しかし、こ のデータの夫々の部分はスーパー通信リンクから来なければならなかったのであ るから、スーパー通信リンクもまた、この一つのクラスタをサービスするのに要 する負荷によって飽和させられるのに違いない。このように、この場合はスーパ ー通信リンクは、ただ一つのクラスタにしかサービスできないことになる。

これは、クラスタ内の夫々のプロセッサがその作業をスーパー通信リンクからだ け受取ると仮定した結果である。

従って、スーパー通信リンクが一つ以上のクラスタにサービスするためには、各 クラスタは、その内部バス上の殆んどの通信トラフィックを発生及び“消費“し なければならない。これは、そのようなピラミッド・アーキテクチャの使用を制 限する。夫々の処理ユニットにメモリを含ませたことによる大きな改良は、スー パー通信リンク・プロセッサ・レベルでの類似の改良を有していない。

この始めに述べた改良は、プログラムを夫々の処理ユニットに対し他の処理ユニ ットと共用の共通メモリ・バスを通して反復転送する必要を除いた結果であった 。一旦、個々の処理ユニットの夫々が、プログラム及び反復転送される任意のデ ータの記憶に充分なだけのメモリを持つならば、このタイプのピラミッド・アー キテクチャを使って通信リンク上の通信密度をさらに大きく改良することは不可 能である。

ピラミッド・クラスタ法に固有の第２の問題は、そのシステムを拡張するとき、 新しいタイプのプロセッサ、スーパー通信リンク・プロセッサの導入が必要な事 である。ＶＬＳＩの製造技術は、クラスタ内の個々の処理ユニットやメモリの構 成に使われるような高反復機能素子のコストを大幅に下げた。しかしながら、ス ーパー通信リンク・プロセッサに使用する少数のパーツのコストは極めて高くな る。追加のレベルの複雑さがまたシステム駆動に必要なソフトウェアにおいて追 加のレベルの複雑さをもたらす。このソフトウェアは、解決する問題を各クラス タに送るべき大きな部分へ分割するのを管理するだけでなく、クラスタ内の夫々 の処理ユニットに割当てられるべき小さな部分への分割をも管理しなければなら ない。

第３に、各スーパー通信リンクは通信の潜在的隘路であることである。同じスー パー通信リンク・プロセッサに取付けられた二つのクラスタが大量の情報（メツ セージと呼ぶ）を交換しなければならない状況を考えてみる。

この交換は、スーパー通信リンク・プロセッサの時間を多く占有し、それにより そのスーパー通信リンク・プロセッサに取付けられた他のクラスタ間でのメツセ ージ伝送のために時間が残らないという可能性がある。この結果、それら他のク ラスタが作業出来ずアイドルとなり、システムのスループットを低下させるとい うことが起こり得る。この種の問題を避けるため、飽和していない交替のスーパ ー通信リンク・プロセッサを介してメツセージを別ルートで送る手段が必要であ る。このような別ルートを与える便利な構成を組立てるのは、このタイプのピラ ミッド・アーキテクチャでは難しい。

最後に、このタイプのピラミッド・アーキテクチャは耐故障性が充分ではない。

システム中の処理ユニットの数を増加したとき、誤動作増発により一つの処理ユ ニットをラインから外さなければならないことがある。もし、問題のその処理ユ ニットがスーパー通信リンク・プロセッサであれば、それがサービスしていたク ラスタの全部をサービスから外さなければならない。

それ故に、本発明の目的は、マルチプロセッサ・システム内の処理ユニット間の 通信のための改良された通信プロセッサ及びアーキテクチャを提供することであ る。

本発明の別の目的は、新たな通信部品を追加することなしに、任意の大形のマル チプロセッサ・システムを構築するのに使われる通信プロセッサ及び通信アーキ テクチャを提供することである。

本発明のさらに別の目的は、メツセージを隘路の回りのルートで自動的に送る通 信ネットワ「りを提供することである。

本発明のさらに別の目的は、耐故障性のある通信プロセッサを提供することであ る。

本発明のこれらの目的及びその他の目的については、以下の本発明の詳細な説明 、及び付随する図面によって明らかとなろう。

発明の概要 本発明は、複数個の通信プロセッサで形成される通信ネットワークから成り、こ れら通信プロセッサは、マルチプロセッサ・データ処理システム内のいずれの二 つのプロセッサ間でもメツセージが効率的に送ることができるように互いに接続 されている。このデータ処理システムは複数個のデータプロセッサから成り、そ れらは好ましくは同一のものである。各データプロセッサは通信プロセッサに結 合され、この通信プロセッサは、それ自身と他のデータプロセッサに結合した他 の通信プロセッサとの間のメツセージの送受に責任がある。これら通信プロセッ サは、二次元六辺形アレイに組織化されている。

夫々の通信プロセッサは、それに隣接した６個の通信プロセッサと６個のポート を通して通信する。それらポートの夫々は、該当の通信プロセッサをこれに隣接 する６個の通信プロセッサの内の一つの対応したポートに結合する。

所与のデータプロセッサがマルチプロセッサ・システム中の他のデータプロセッ サにメツセージを送りたいときは、そのメツセージをそれ自身のメモリに入れ、 それから自身に結合している通信プロセッサに信号を送る。

この通信プロセッサは、そのデータプロセッサのメモリをアクセスする。メツセ ージの送出準備完了を示す信号は、通信プロセッサがデータプロセッサのメモリ 中の該当するメツセージを捜すのに必要な情報を含んでいる。

一度この信号が与えられると、データプロセッサはフリーとなり、その他の計算 を続けることができる。このように、通信プロセッサは、マルチプロセッサ・シ ステム内の他のデータプロセッサとの通信に関する実質止金てのオーバヘッドを データプロセッサから取り除くのである。

この通信プロセッサは、適当なポートを通って隣接する一つの通信プロセッサに メツセージを送る。もし、このメツセージの最終宛先がその隣接通信プロセッサ に結合されたデータプロセッサであれば、その通信プロセッサは、メツセージを 前記データプロセッサのメモリに記憶させる。もし宛先が、そのメツセージを送 った隣接通信プロセッサに結合したデータプロセッサでないときは、その隣接通 信プロセッサは、そのメツセージを隣接する第３の通信プロセッサに中継する。

このように、メツセージは、その最終宛先であるデータプロセッサに結合したプ ロセッサに到達するまで中継される。

夫々の通信プロセッサが使うメツセージ・ルーティング・アルゴリズムは、通信 プロセッサの誤動作または局部的な通信のオーバロードによって作られた通信隘 路の周囲の別ルートで自動的にメツセージを送る。もしも、メツセージがある通 信プロセッサに送られるべきで、し自動的に別ルートで送られる。

六辺形アレイのエツジにある諸通信プロセッサは、それらのポートの夫々に結合 した、“隣接”通信プロセッサのポートを持っていない。そのような結合を欠い た諸ボートはルーティングスイッチに接続され、このルーティングスイッチは、 それらポートを、外部シグナルパスによって六辺形アレイの反対側のエツジにあ る通信プロセラもしくはプロセッサに結合させる。この六辺形アレイの反対側エ ツジへの結合は、メツセージの生じたデータプロセッサから遠い宛先を持ったメ ツセージについて、その伝送時間を短縮する。この外部シグナルパス・システム が、六辺形アレイにおいて最短のバス長を与えることが示される。これらのエツ ジボートはまた、マルチプロセッサ・システムの外側の世界と通信するための手 段を提供し、これは在来コンピュータにおける入力−出力ポートに類似したもの である。

図面の簡単な説明 第１図は、本発明による通信ネットワークを示す。

第２図は、隣接した諸通信プロセッサの対応するボート間の結合の詳細図である 。

第３（ａ）図は、７個の小形の六辺形通信ネットワークから構成された、より大 形の通信ネットワークを示す。

第３（ｂ）図は、第３（ａ）図に示した大形の通信ネットワークの代替構成を示 す。

第４図（ａ）は、六辺形アレイに基づく通信ネットワーク内の非隣接通信プロセ ッサ間のメツセージのルーティングを示す。

第４図（ｂ）は、方形アレイに基づく通信ネットワーク内の非隣接通信プロセッ サ間のメツセージのルーティングを示す。

第５図は、六辺形アレイの反対側エツジにあるポートを結合するのに使われるシ グナルパス接続を示す。

第６（ａ）図は、六辺形アレイのエツジ上のいずれのポートを互いに結合すべき かを決める方法を示す。

第６（ｂ）図は、各通信プロセッサ上の諸ボートの番号付けを示す。

第７（ａ）図及び第７（ｂ）図は、夫々、各辺に３個の通信プロセッサを持つ六 辺形アレイにおいてその中の通信プロセッサに対するルーティング・ダイヤグラ ムを示す。

第８図は、無限の六辺形アレイの中の所与の通信プロセッサを捜すための座標系 を示す。

第９図は、第８図に示した座標系の、各辺に３個の通信プロセッサを持つ六辺形 アレイ、に対する適合を示す。

第１０図は本発明の好適実施例に使われる通信プロセッサのブロック図である。

第１１図は、パケットが送信されるときポート・コントローラによて実行される 動作のフローチャートである。

第１２図は、パケットが送信されるべきときポートにより実行される動作のフロ ーチャートである。

第１３図は、パケットが受信されるときポートにより実行される動作のフローチ ャートである。

発明の詳細な説明 本発明は、マルチプロセッサ・データ処理システム内の諸データプロセッサ間で メツセージを伝送するための通信ネットワークから成るものである。各データプ ロセッサは、そのネットワーク内の他の通信プロセッサと交信する一つの通信プ ロセッサに接続されている。当業者には明らかなように、諸データプロセッサの 夫々は、一つのメモリに結合した二つまたはそれ以上の処理ユニットから成るデ ータプロセッサのクラスタ（１群）で置換えることができる。本発明による、１ ９個の通信プロセッサを持つ通信ネットワークを第１図に示す。分りやすくする ために、各通信プロセッサに接続された一つ又は複数のデータプロセッサは示し ていない。通信ネットワークは、通信プロセッサ２２が代表的な諸通信プロセッ サの一つの六辺形アレイ２０から成っている。より大きな通信ネットワークは、 より多くの通信プロセッサを各辺に持つ諸六辺形アレイを使って構築することが できる。

各通信プロセッサは六角形で表わされている。何故ならば、それは隣の通信プロ セッサとの通信のため６個のポートを持っているからである。メツセージはこれ らポートのどれからでも送信又は受信ができる。このことは、第２図に詳しく示 しである。各通信プロセッサの諸ポート２４には、１から６の番号を付けである 。各ポート２４は、隣接通信プロセッサの対応するポート２４に接続されている 。ポート１は隣接の通信プロセッサのポート４に接続されている。ポート２は隣 接する他の通信プロセッサのポート５に接続されている。ポート３は隣接する更 に他の通信プロセッサのポート６に接続されている。以下同様である。六辺形ア レイのエツジ上の諸通信プロセッサに対し使用されるボート接続は、以下に詳し く述べる。

以下にさらに詳述するように、通信プロセッサそれ自体は、いくつかのタスクを 同時に処理する能力をもつコンカレント・プロセッサである。ポートの夫々は、 他のポートとは独立して動作する。この故に、数個のメツセージを一時に送信又 は受信できる。加えて、諸ポートによって他のメツセージが送信及び受信されて いる間に、メツセージをプロセッサメモリにまｔ；はそれから転送させることが できる。

メツセージは、そのルートが通信プロセッサ間で決められ、それは、そのメツセ ージを隣接通信プロセッサに転送し、このプロセッサが更にそれを隣接する通信 プロセッサの一つにパスし、そしてメツセージが最終宛先であるデータプロセッ サに接続された通信プロセッサに達するまで統けることによって行われる。好適 実施例においては、このプロセスに使われるルーティング・アルゴリズムは、こ れがメツセージのルートを決めることができるようにするためには、全通信ネッ トワークのマツプのような大域情報を要求しないことに注目すべきである。

そのような情報は、通信ネットワーク中の通信プロセッサの数によって指図され るサイズのテーブルに記憶しなければならないであろう。もし、ネットワーク中 の通信プロセッサ数が増加した場合には、これらのテーブルのサイズも増加させ なけれなばらない。これは、すべての通信プロセッサのハードウェアの変更修正 を必要とすることになり、明らかに望ましくないことである。以下に述べるよう に、本発明はそのようなテーブルの使用を避けている。

本発明によれば、１個のデータプロセッサが六辺形アレイ中の他のデータプロセ ッサにメツセージを送りたいときは、送りたいデータプロセッサがそのメツセー ジをその宛先と共に自己のメモリに転送する。次に、自己に接続された通信プロ セッサに信号を送る。そのデータプロセッサに接続された通信プロセッサが、そ のデータプロセッサのメモリをアクセスする。前記通信プロセッサはそのデータ プロセッサのメモリからメツセージを読出ず。その後はデータプロセッサはメツ セージ伝送に影響するそれ以上のアクションを取ることは不必要である。

その送信する通信プロセッサは、送信用にメツセージをコード化し、そしてそれ を自己のポートの一つに割当てる。もし、メツセージの最終宛先が隣接する通信 プロセッサの一つに接続されたデータプロセッサであれば、それら二つの通信プ ロセッサを結ぶポートがそのメツセージに割当てられる。もし、メツセージの最 終宛先がさらに遠くのデータプロセッサであれば、以下に詳細に述べる方法によ って、伝送時間を最小にするポートが選ばれる。

通信プロセッサが自己のポートの一つにメツセージを受ケた時、通信プロセッサ は、メツセージの最終宛先を指定するメツセージヘッダに含まれた情報をチェッ クし、それによってメツセージが前記通信プロセッサに接続されたデータプロセ ッサへ送られるべきかどうかを決定する。このヘッダ情報は、最初にメツセージ を送った通信プロセッサによってメツセージ中に置かれる。

もし、前記データプロセッサが最終宛先であれば、通信プロセッサはそのデータ プロセッサのメモリにメツセージを記憶し、そしてデータプロセッサにメツセー ジが到来したことを知らせる。もし前記データプロセッサがメツセージの最終宛 先でない場合は、通信プロセッサはそのメツセージを自己に接続されたデータプ ロセッサで生起したメツセージのように再送信する。

このタイプの六辺形アレイ通信トポロジーは、以前の技法よりもいくつかの有利 な点をもっている。自由なサイズの通信ネットワークが、単一の六辺形アレイを 使うか、または、数個の六辺形アレイを組合わせることによって構成できる。第 ３（ａ）図は、７個の小形の六辺形アレイ３２−３８を組合わせて構成できる、 実現可能な大形のネットワークを示したものである。この例では、夫々の小形ア レイは１９個の通信プロセッサを含んでいる。

各アレイの中心の通信プロセッサにはアレイの番号が付けである。明瞭にするた めに、夫々のアレイの境界は点線で輪郭をつけである。任意の数のそのようなア レイの組合わせが、通信ネットワークの中にいかなる接続要素の導入の必要も無 しで可能である。この故に、本発明では、従来のシステムにおいて諸グループの データプロセッサを組合わせるのに使用されている特別目的の通信プロセッサは 、排除されている。

第３（ａ）図に示したものに類似した第２のネットワークを第３（ｂ）図に示す 。これは、３２’　−３８″の７個のアレイから成るものである。第３（ｂ）図 に示すネットワークから、アレイ３３′がアレイ３４′　よりも高くなっている 点で、第３（ａ）図のアレイ３４がアレイ３３よりも高いのと異なっている。こ れらのタイプのアレイの組合わせの重要性については、以下でさらに詳しく説明 する。

共用バス、またはメツセージが特定の通信プロセッサに届くまでに通らなければ ならない通信“ハブがないので、従来の設計手法に付随して起こった通信の隘路 は回避されている。もし、所与の通信プロセッサが、誤動作または伝送しなけれ ばならないメツセージが残っているためにメツセージの受信が不可能のときは、 以下に詳シく述べるように、メツセージは自動的にその周囲のルートで送ること ができる。データ処理システムのサイズが、諸六辺形アレイを組合わせるかまた は１つの六辺形アレイのサイズを大きくすることで増大させられるにつれ、所与 のメツセージに対して可能な通信パスの数もまた増加することに注目すべきであ る。このために、メツセージを自動的に別ルートで伝送するシステムの容量は、 システム中のデータプロセッサの数に関係したメツセージの量の増加とともに、 自動的に増加する。

他の二次元アレイに対抗して六辺形アレイのこの選択は、二つの考慮によって指 図される。それらは、マルチプロセッサ・データ処理システム製造の能率と、通 信隘路周辺へのメツセージ・ルーティングの能率である。データプロセッサの好 適実施例は、シングルチップまたはシングルウェハ上での製造を意図している。

前記チップまたはウェハの表面積の利用効率は、一つの重要な要素である。何故 ならば、それがデータ処理システムに組込まれるプロセッサの数を決定するから である。六辺形は最高位の正多角形で、多角形間に隙間なく表面を覆うのに使う ことができる。従って、六辺形はチップの表面積を有効に利用するのに最高の多 辺形である。さらに、もしそれより辺の多い多辺形を使ったとしたら、アレイ中 の種々の通信プロセッサ間の接続が交差することが必要となり、製造工程が複雑 になってしまう。故に、アレイは六辺形、三辺形、四辺形、または三辺形でなく てはなので、プロセッサ・アレイは特定の方向を持つべきではない。このことは 、チップの全表面を覆うのに加えて、プロセッサ・アレイが通信プロセッサ・ア レイを含む平面内の二つの直交軸に関して対称でなければならないこと、を要求 するのと等価である。三辺形及び三辺形のアレイはこの対称性に欠けるので、こ の通信ネットワークには不適当である。

これで、可能な選択は六辺形と四辺形のアレイに減る。

四辺形アレイよりも六辺形アレイを選ぶのは、局部的隘路の周辺の通信効率によ るためである。このことは第４図に示されている。第４図（ａ）において、本発 明による六辺形アレイの一部分が４０で示されている。通信プロセッサ４２で発 し、その最終宛先が通信プロセッサ４４であるメツセージについて考えてみる。

このメツセージの最適ルートは通信プロセッサ４８を通るルートである。このル ートはメツセージが二度の伝送、即ち一度は通信プロセッサ４２によって、もう 一度は通信プロセッサ４８によって、伝送されることを要する。もし通信プロセ ッサ４８が、オーバロードあるいは誤動作のためにメツセージを受けることがで きない場合は、メツセージは代わりの二つのパスのいずれかで送られる。そのパ スの第１は通信プロセッサ４３及び４５を通るものであり、第２は通信プロセッ サ４６及び４７を通るものである。

これら代替バスの夫々は、メツセージに三度の伝送、即ち最適バスを通るよりも 一度余計な伝送を必要とする。

第４図（ｂ）には、通信プロセッサの四辺形アレイの類似部分が５０で示されて いる。ここで、通信プロセッサ５２で発しその最終宛先が通信プロセッサ５４で あるメツセージについて考えてみる。唯一のパス、即ち二度の伝送に必要な時間 と等しい遅延で伝送できるパスは、通信プロセッサ５６を通るパスである。もし 通信プロセッサ５６がオーバロードあるいは誤動作のためにメツセージを受けら れない場合は、メツセージは通信プロセッサ５ｇ、６０及び６２のルートで送ら ねばならない。その結果、４回伝送するのに必要な時間と同じ伝送時間となる。

この故に、オーバロードと誤動作の状態下において、非隣接通信プロセッサへの 代替バスが短くてすむ六辺形アレイは四辺形アレイに比べて優れている。

六辺形アレイのエツジの上にある諸通信プロセッサは、それらのポートの各々に 結合すべき隣接通信プロセッサの数を充分にもっていない。例えば３個の通信プ ロセッサを一辺にもつ六辺形アレイの場合、エツジ上の諸通信プロセッサは、そ れらが結合できる隣接通信プロセッサの数は僅か３個か４個である。このことは 第５図に示されており、これは、１９個の通信プロセッサ（−辺に３個の通信プ ロセッサ）を持つ一つの六辺形アレイ７０を示している。アレイ７０のエツジ上 の諸通信プロセッサ７４の各々は、隣接した通信プロセッサに結合されない２個 あるいは３個のポートを持っている。そのような代表的なポートを７２で示しで ある。これらのポートを以下では周辺ボートと呼ぶことにする。各周辺ポートは ルーティングスイッチ７６に接続されている。各ルーティングスイッチは２個の ルーティングポート７８と８０を持っている。

ルーティングボート８０の夫々は、この六辺形アレイの反対側エツジ上のルーテ ィングスイッチ７６のルーティングボート８０に対し、８２で代表されるシグナ ルバスにより接続されている。諸エツジ通信プロセッサ７４の夫々の他の１個ま たは２個のポートに接続しているシグナルパス及びルーティングスイッチ７６は 、図を分りやすくするために第５図から省略しである。このようにして、あるエ ツジ通信プロセッサ７４の周辺ポートの一つを去るメツセージは、六辺形アレイ の反対側エツジにラップアラウンドされる。これは六辺形アレイ内の互いに遠く 離れた通信プロセッサ間でのメツセージ伝送に必要な時間を短縮する。いずれの 周辺ポートが所与のシグナルパスによって結合されるかの選択は、以下に詳しく 述べる。

各ルーティングスイッチ７６の第２ルーテイングポート７８は、六辺形アレイを “外の世界”に結合するのに使われる。それは、従来のデータ処理システムの普 通の入力−出力ポートの機能を果す。外部デバイスがこの六辺形アレイにメツセ ージを送りたいときは、前記メツセージをそのアレイに接続されたルーティング スイッチ７６に送る。次に、このルーティングスイッチ７６は、そのメツセージ をこれに接続する通信プロセッサ７４に中継する。

これらルーティングスイッチ７６は、各メツセージのヘッダ情報内のデータでコ ントロールされる。“外の世界”に伝送されるべきメツセージは、所定のヘッダ と共にコード化され、この所定のヘッダは、隣接通信プロセッサ７４からのメツ セージを受けるルーティングスイッチ７６が認識する内部宛先を指定する。同様 に、六辺形アレイに接続されているデータプロセッサに対し向けられた外部デバ イスからのメツセージは、その問題のデータプロセッサを識別するヘッダと共に コード化される。スイッチ７６がそのようなメツセージを受けたとき、自己に接 続された通信プロセッサにそれを送る。

シグナルパス８２によって接続される周辺ポートの選択は二つの考慮によって決 められる。第１は、これらの接続がしばしば通信プロセッサ間でのメツセージの 伝送に必要な時間を決めることである。この時間を最小にすることは重要である 。第２は、以下に詳しく述べるように、周辺ポート接続の適正な選択によりその 結果生じる通信ネットワークでは、アレイのエツジ上の通信プロセッサ７４がそ の六辺形アレイの中心にあるものと見分けがつかなくなる。これは、個々の通信 プロセッサの製造の効率を増大する。加えて、この結果、通信プロセッサは、い かなるサイズの六辺形アレイにも使えることになる。

どの周辺ポートが相互接続されるべきかの選択は、１９個の通信プロセッサを持 っている（その内３個の通信プロセッサは各エツジにある）通信ネットワークに 関して、第５図に良く説明されている。接続の決定方法は、第６（ａ）図に示さ れたダイヤグラムを参照すればさらに容易に理解できる。このダイヤグラムは、 ６個のファントム通信ネットワーク８６−９１に接続された１９通通信プロセッ サ通信ネットワーク８４を示している。夫々のファントム通信ネットワークは、 通信ネットワーク８４のコピーである。通信ネットワーク８４中の夫々の通信プ ロセッサは、通信ネットワーク中でそれが現われる位置を識別するＯａから１８ ａのラベルが付されている。ファントム・ネットワーク８６−９１も同様にラベ ルが付されている。上で分るように、各通信プロセッサは、第６（ｂ）図に示す ように１から６までのラベルが付された６個のポートを持っている。どの二つの 通信プロセッサ間の接続も、互いに接続されたポートの各々のラベルを与えるこ と、及びそれら当該ポートの各々を含む通信プロセッサのラベルを与えることに より指定できる。例えば、通信ネットワーク８４において、通信プロセッサ３ａ のポート６は通信プロセッサ２ａのポート３に接続している。同様に、ネットワ ーク８４中の二つのエツジ・プロセッサ間の相互接続については、例えば、次の ようになる。通信ネットワーク８４中の通信プロセッサ９ａのポート６は、ファ ントム通信ネットワーク８６中の通信プロセッサ１４ａのポート３に接続してい る。

以下に述べるように、これは第５図に示したシグナルパス８２に相当するもので ある。

通信ネットワーク８４中の各周辺ボートについて、シグナルパスで接続されるべ き通信ネットワーク８４中の対応する周辺ポートは、次のようにして決定される 。通信ネットワーク８４中から問題の周辺ポートを見付は出し、そしてそれが接 続される適当なファントム通信ネットワーク８６．８７．８８，８９．９０ある いは９１中の通信プロセッサ及び周辺ポートを決定する。前記周辺ポートを、通 信ネットワーク８４中の同じ通信プロセッサ・ラベルとポート・ラベルを持つ周 辺ポートに接続する。例えば、通信ネットワーク８４中の通信プロセッサ９ａの ポート６は、ファントム通信ネットワーク８６中の通信プロセッサ１４ａのポー ト３に接続される。従って、シグナルパスは、ルーティングスイッチ７６を使い 、通信ネットワーク８４中の通信プロセッサ９ａのポート６を通信ネットワーク ８４中の通信プロセッサ１４ａのポート３に接続することによって作られる。上 に詠べたように、これが第５図に８２で示したシグナルパスである。

このシグナルパス接続設計は、夫々の通信プロセッサに、それが一つの大形アレ イの中にシグナルパス接続なしで置かれているかの“想像”をさせるものである 。ある特定の通信プロセッサに送られるべきメツセージのルーティングを決定す るのには、第６（ａ）図の大形アレイ図の中で、その通信プロセッサの周囲の諸 通信プロセッサを調べて、それが当該メツセージを送られるべき通信プロセッサ のラベルにマツチしたラベルを持つ通信プロセッサを見付は出すまで行うだけで よい。第６（ａ）図を調べると、通信プロセッサがどの所与のラベルを見付は出 すのにも、ネットワーク８４中の離れた２個の通信プロセッサを見る以上のこと は必要のないことが明白である。従って、このシグナルパス接続設計は、ネット ワーク８４中のどの２個のデータプロセッサ間で伝送すべきメツセージであって も、せいぜい通信ネットワークがメツセージを２度伝送するのに要する遅れです むようにする。これは、明らかに、３個の通信プロセッサを一辺に持つ六辺形ア レイに対しては可能な最小の遅れである。

従って、所与の通信プロセッサは、第６（ａ）図に示したダイヤグラムの中で、 多くて当該通信プロセッサから２通信プロセッサ内の部分を記憶していればよい ことになる。前記ダイヤグラムのこの部分は、ルーティング・ダイヤグラムと呼 ばれるが、それ自体当該通信プロセッサを中心とした六辺形アレイである。通信 プロセッサ５ａ及び９ａに対するルーティング・ダイヤグラムは、夫々第７（ａ ）図及び第７（ｂ）図に示しである。各通信プロセッサはその情報をこれに記憶 した関連のルーティング情報に含んでいる。通信ネットワーク８４において一つ の通信プロセッサを他から識別するただ一つのものは、各通信プロセッサに記憶 された特定のルーティング・ダイヤグラムである。従って、夫々の通信プロセッ サに対するハードウェアとソフトウェアは同じものである。

このことは、本発明の通信ネットワークの構成を大いに単純化している。以下に 詳しく説明されるように、ルーティング・ダイヤグラムは、記憶要件が六辺形ア レイのサイズに無関係なアルゴリズムに縮小できる。

上の分析は第６（ａ）図に示したファントム六辺形アレイ・ダイヤグラムを使っ て行ったもので、これは第３（ａ）図に示したものから作ったものである。上で 指摘したように、この形には第３（ｂ）図に示したような第２の可能なダイヤグ ラムがある。トポロジーの分野の当業者には明らかなように、もし六辺形アレイ ８４へのシグナルパス接続が第３（ｂ）図に示したのと類似のファントム六辺形 アレイ・ダイヤグラムに関して決められた場合に、同様な結果が得られる。この 場合に接続される実際の周辺ポートは異なる。しかし、本発明の変更される面は 、各通信プロセッサに記憶されるルーティング・ダイヤグラムの特定のラベルだ けである。

最後に、上の分析は３個の通信プロセッサを夫々のエツジに持つ六辺形アレイを 使って行ったものである。同様な技法が、Ｅ個の通信プロセッサを一辺に持った 任意の大きさの大形六辺形アレイにも適用できる。第６（ａ）図に示したのと類 似のダイヤグラムを構成でき、これは問題の通信ネットワークをこれの６個のフ ァントム・コピーと共に示す。それらの周辺ポートはシグナルバスにより接続さ れ、これらシグナルパスは、各周辺ポートを、関連しＩ；７アントム・コピー中 の接続されるポート及び通信プロセッサのラベルと同じラベルを持つ六辺形アレ イの反対側エツジ上の通信プロセッサのポートに、接続する。その結果のルーテ ィング・ダイヤグラムは、各辺にＥ個のエントリをもつ六辺形アレイとなる。各 通信プロセッサは、六辺形アレイ中の他の各通信プロセッサからＥ−１通信プロ セッサ内にあることになる。これが、通信プロセッサ間の最小距離であることが 示されている（Ｓｃｂｌｕｍｂｅｒｇｅｒ　Ｐｓｌｏ　Ａｌｔｏ　Ｒｅ５ｅ＊ｒ ｃｂ　Ｒｅｐｏｒｔ　＃４７参照）０この故に、本発明は、メツセージがその最 終宛先に到達するのに再伝送されねばならない回数に関しては、最高の能率を持 った通信ネットワークである。

単一六辺形アレイ中のいずれの二つの通信プロセッサ間の距離をも最小にするの に加えて、シグナルパスとルーティングスイッチとは、第３（ａ）図及び第３（ ｂ）図に示すようないくつかの六辺形アレイを組み合わせた大形ネットワークに おいて向上した性能を提供する。このようなネットワークでは、ルーティングス イッチは、個々の六辺形アレイ間の接続に使われる。一つまたはそれ以上の追加 の六辺形アレイによって分離された異なった六辺形アレイに位置する通信プロセ ッサの間でメツセージを送らなければならない場合、シグナルパスは、介在する 六辺形アレイの周囲でメツセージを“ジャンプ”させるのに使用できる。

例えば、第３（ａ）図のラベル３７の通信プロセッサからラベル３５の通信プロ セッサに送られるべきメツセージについて考えてみる。外部シグナルパス無しで は、このメツセージは、通信プロセッサ３７が位置する六辺形アレイのエツジに 到達するまで、通信プロセッサから通信プロセッサを通過しなくてはならない。

このメツセージは、次に通信プロセッサ３２を含んだ六辺形アレイを横切って、 その六辺形アレイのエツジに到達するまで同様な方法で通過しなければならない 。最後にメツセージは、通信プロセッサ３５が位置している六辺形アレイ中の適 当な通信プロセッサを通過してその通信プロセッサ３５に到達することになる。

諸六辺形アレイのエツジ上のルーティングスイッチは、メツセージを通信プロセ ッサ３２を含む六辺形アレイのエツジ上の通信プロセッサからこの六辺形アレイ の反対側エツジにある通信プロセッサへの中継を可能にし、従って通信プロセッ サ３２を含んだその六辺形アレイ中の全ての通信プロセッサをバイパスする。こ れは、発信地から遠い宛先のメツセージについてその伝送時間を大幅に短縮する 。

上で指摘したように、重要なことは、通信プロセッサが、六辺形アレイのサイズ に依存するサイズのテーブルに記憶せねばならないような大域情報を含んでいな いことである。これは、もしそのようなテーブルが要求されると、構成できる最 大サイズの六辺形アレイは、そのテーブル中の利用可能なスペースに依存するこ とになるからである。上に述べたルーティング・ダイヤグラムはそのようなテー ブルである。本発明はまた、この問題にも解決を与えている。

そのようなテーブルに対する過剰スペースの配分を回避するために、本発明は、 諸通信プロセッサに対するラベリング設計を使用し、これは、前記ルーティング ・ダイヤグラムに含まれた情報を、記憶要件が六辺形アレイのサイズに無関係と なるアルゴリズムに縮小させる。この故に、本発明の通信プロセッサは、それが 六辺形アレイとして接続されておれば、いかなるサイズの通信ネットワークにも 使用できるのである。

本発明で使用されるラベリング設計を第８（ａ）図に示しである。“無限大”の 六辺形アレイの一部分を９１′で示している。各通信プロセッサは２つの数字（ ｘ、ｙ）から成るラベルを割当てられており、これは、直交座標系の座標に類似 の座標系において、各通信プロセッサの位置を指定するものである。これら２つ の数字は各六辺形の中でコンマで分けて示されている。この座標系の軸は９２で 示されている。この座標系は、軸が直交していないこと、及びＤとラベル付けさ れた第３の軸が定義されている点で、直交座標系と異なっている。Ｘ軸に平行な 方向で通信プロセッサから通信プロセッサに移動するとき、第１の座標は移動方 向によって増分または減分される。同様に、ｙ軸に平行な方向で移動するときは 、第２の座標が増分または減分される。最後に、Ｄ軸に平行に移動するときは、 第１と第２の座標が共に増分又は減分される。各軸は２つのポートに対応してい ることに注目すべきである。例えば、ポートｌまたはポート４から送られるメツ セージはＤ軸に平行な方向に伝播する。ポート番号は第８（ｂ）図の９３に示さ れている。

このラベリング設計を使って、通信プロセッサは、ルーティング・ダイヤグラム の必要なしに他のどの通信プロセッサに対しても最適バスを計算できる。この説 明の目的のために、メツセージを送りつつある通信プロセッサを送信者、そして そのメツセージの最終宛先である通信プロセッサを受信者と呼ぶことにする。送 信者はまず、送信者を受信者に結ぶ線のＸ軸に対する角度を計算する。

この角度を受信者角と呼ぶ。各ポートは“ポート”角を割当てられるが、これは 、そのポートに接続された送信者に隣接の通信プロセッサへ送信者を結ぶ線の角 度に等しい。ポート角もまたＸ軸に対して計算される。この故に、ポート１のポ ート角は６０°、ポート２のボート角角は１２０’、以下同様である。次に、優 先順のポー１、のりストは、受信者角と各ボート角との差の絶対値を使ってポー トを順序づけることによって計算される。

例えば（０，０）の通信プロセッサから（１，２）の通信プロセッサに送られる メツセージに５いて考えてみる。受信者角（（０，０）の通信プロセッサの中心 を（１，２）の通信プロセッサの中心と結ぶ線の角度）は９０°である。従って 、ポートｌと２が望ましい。何故なら、それらは各々受信者角からの差角が３０ ″のボート角を有しているからである。ポート６及び３は、夫々が受信者角から の差角が９００のボート角であるから、次に最も望ましいポートである。以下同 様である。

上の例で、もし受信者が（０，２）であったとすると、受信者角は１２０°であ る、ただ一つのポート、即ちポート２だけが望ましいものとなる。次の最も望ま しいポートはこの場合、ポート１と３になる。以下同様である。

上述のルーティング・アルゴリズムは、本発明に従う有限六辺形アレイ通信ネッ トワークに適用できる。本発明による、３個の通信プロセッサを各辺に持った六 辺形アレイを基にする通信ネットワークは、第９図の９４で示されている。この 六辺形アレイ”の境界は太線で輪郭をとっである。この六辺形アレイの６個の７ アントム・コピーの関連する部分は、この太線の外側に示しである。

上の第６図に関して指摘したように、これらのファントム・コピーは、六辺形ア レイ９４の反対側エツジ間を結ぶシグナルバスがメツセージのルーティングに使 われるとき、最適ルーティングの計算を笥単にするのに使われる。これらのファ ントム・コピーは、各通信プロセッサが六辺形アレイの中にある他のいずれの通 信プロセッサの座標をも計算するのを可能にするものである。

これらのシグナルバスは、上述の座標系に不連続を導入する。例えば、（０，０ ）から正のｙ軸に沿って進行すると、次の通信プロセッサが（０，２）の通信プ ロセッサの後に出会う次の通信プロセッサは、（−２，−２）の通信プロセッサ であって、“無限”六辺形アレイの場合の（０，３）の通信プロセッサではない 。従って、各通信プロセッサは、六辺形アレイのサイズを指定する数を記憶しな ければならず、それによってこの不連続の位置及びその不連続を越えた次の通信 プロセッサの座標が計算できるようにしなければならない。

有限の六辺形アレイと無限の六辺形アレイの違いの第２は、所与の通信プロセッ サに対し多くの異なった方向に沿って進むことにより到達できることである。例 えば（−２，−２）の通信プロセッサに（０，０）の通信プロセッサから到達す るには、正のｙ軸に沿って進行することにより、または負のＤ軸を進行すること により、もしくは（１，ｌ）の通信プロセッサへ正のＤ軸を進行しそして次に正 のＸ軸に沿って進行することにより可能である。正しいバスは次のようにして選 ばれる。送信者は、送信者のＥ−１通信プロセッサの範囲内にある受信者の座標 を計算する。ここで、Ｅは六辺形アレイ９４の一辺にある通信プロセッサの数で ある。上記のように六辺形アレイ９４のエツジ上の通信プロセッサを接続するシ グナルバスは、どの通信プロセッサも他のどの通信プロセッサのＥ−１通信プロ セッサ範囲内にくるように選ばれる。

この受信者の座標は、送信者からＥ−１通信プロセッサの距離の範囲内に一度だ け現れることになる。

上記修正により、送信者は、無限の六辺形アレイに関して述べたアルゴリズムを 使って、六辺形アレイ中の任意の受信者にメツセージを送るのに使用するポート のリストを、優先順に割当てることができる。送信者は、送信者のＥ−１通信プ ロセッサ範囲にある受信者の座標を持った通信プロセッサの位置を計算する。こ れを行うために、送信者は、六辺形アレイ内又はその仮想コピー内の受信者の座 標と同じものを持った各通信プロセッサの位置を計算する。次に、送信者のＥ− １通信プロセッサ範囲内に位置する通信プロセッサを選択する。送信者は、次に この通信プロセッサを送信者に結ぶ線の角度を計算し、そしてメツセージ送信に 使われる優先順のポートのリストを計算する。メツセージは次に最高優先順位の ポートに接続された隣接通信プロセッサに送られる。もし、そのようなポートが ２個あるときは、メツセージは、その第１のフリーのポートで送られる。もしこ の隣接通信プロセッサが利用できないときは（例えば、他のタスクでビジーとか 、動作しないとかの理由）、メツセージの隣接通信プロセッサへの伝送が成功す るまで、次に高い優先順位のポートが使われる。

本発明による通信プロセッサの好適実施例が第１０図の１００に示されている。

それは、４つの基本要素を持っている。第１の要素はバッファ１０２で、これは 通信プロセッサを通過するメツセージを記憶するのに使用される。第２の要素は ポートコントローラ１０４で、これは第３の要素であるポート１０６を通るメツ セージの伝送を管理する。第４の基本要素は直接記憶アクセス・コントローラ１ ０Ｂで、これは、バッファ１０２と当該通信プロセッサに接続されたデータプロ セッサ１１１のメモリ１１０との間のメツセージの転送を管理する。

バッファ１０２内のスペースのより有効な利用のために、長いメツセージは、パ ケットと呼ばれる複数の小メツセージに分けられる。一連のパケットへの長いメ ツセージの分割は、以下に詳しく述べるように直接記憶アクセス・コントローラ １０８によって行われる。各パケットは、これが属するメツセージと、及びその パケットの最終宛先とを識別するヘッダを含んでいる。また、このヘッダは、そ のメツセージ中のパケットの数、及びこのメッセージ中の当該パケットの位置と を含んでいる。最後に、ヘッダはまた、メツセージが正しく送信及び受信された ことを検証するためポート１０６により使用されるエラー検査情報を含んでいる 。

バッファ１０２は複数個の記憶スロットに分けられている。夫々の記憶スロット は１個のパケットの記憶に使われる。好適実施例においては、パケットのサイズ はデータ処理システムにおいて送られる平均メツセージの長さに選ばれている。

バッファ１０２に記憶されるパケットは、６個のポート１０６が共用するバス１ １２及び直接記憶アクセス・コントローラ１０８を通して１つのポート１０６に 転送される。パス１１２の使用に関する衝突は、バッファ１０２の一部であるバ ッファ・コントローラで解決される。通信プロセッサによって実行される種々の 動作の優先順位については、以下で更に詳しく論説する。

パス１１２は６個のボート１０６全てと直接記憶アクセス・コントローラとをサ ービスしなくてはならないので、パケットをバッファ１０２から所与のポート１ ０６あるいは直接記憶アクセス・コントローラに転送するのに必要な時間は、パ ケットを所与のポート１０６に出力する時間に比べて小さくなくてはならない。

そうでない場合は、パケットは、これが向けられるポート１０６がフリーである ときでも、バッファ１０２の中で待っていなければならなくなる。好適実施例に おいては、バス１１２の幅は、パケットを２バス・サイクルで転送するに充分の 大きさである。これは、ポート１０６を通してパケットを出力するのに必要な時 間の約１／１０である。

ポート１０６の夫々は、１個のパケットを記憶するのに充分な内部バッファを持 っている。従って、各ポート１０６は、バッファ１０２及び他のポート１０６か ら独立して作動できるのである。ポート１０６がバッファ１０２から一つの隣接 通信プロセッサにパケットを転送するために使われる場合、それはパケットをバ ッファ１０２から転送してこのパケットを自己の内部バッファに記憶する。この ポートｌＯ６は次に通信プロセッサ中の他の動作に無関係にパケットを伝送する 。同様に、ポート１０６が一つの隣接通信プロセッサからパケットを受信する場 合は、前記ポートはその自己の内部バッファにパケットを累算する。

上に述べたように、バッファ１０２は、このバッファ中の記憶スペースの割当て に責任のあるコントローラを含んでいる。ポート１０６がバッファ１０２に記憶 すべきパケットを受けｔ；とき、これはバッファ・スペースをバッファ・コント ローラから要求する。同様に、パケットが首尾よく隣接通信プロセッサに伝送さ れたとき、ポート・コントローラ１０４がバッファ・コントローラに信号を送り 、このバッファ・コントローラは利用できる該当パケットによって占有されるス ペースを作る。

ポート・コントローラ１０４によって実行される動作のフローチャートを第１１ 図に示しである。ポート・コントローラ１０４は、バッファ１０２中の諸パケッ トを通してサイクルし、それが送る用意のできたパケットを見付けるまで続く。

このポート・コントローラは次に、そのパケットを送るための望ましい一つまた は複数のポートを決定する。上に指摘したように、もしこのパケットの最終宛先 がデータプロセッサで、その通信プロセッサが軸の一つに平行な線上にない場合 は、その通信プロセッサへの最適ルートは二つ以上ある。即ち、パケットは二つ 以上のポートから遅れを導入せずに送ることができるのである。もし、二つ以上 の最適ボートがある場合は、ポート・コントローラはそれらポートの内のフリー な第１番目のものにパケットを割当てる。もし、望ましいポート１０６の一つの ポートがフリーである場合、それは当該ボートにパケットを取るよう信号を出す 。もし、望ましいポートのいずれもフリーでない場合、カウンタが増分されそし て臨界値に対するテストがなされる。もし、前記カウンタのカウントが臨界値よ りも大きいときは、ポート・コントローラは、当該パケットに代替ボートを選ぶ 。このカウンタは、パケットが伝送を断られた回数を計るので、そのカウントは ８該パケットの“腐敗“の尺度である。ポート・コントローラ１０４は、次に、 送るべき次のパケットを見付けるまで、バッファ１０２中のパケットを通しての サイクル動作に戻る。

もし、パケットが割当てられＩ；ポート１０６が首尾よくパケットの伝送を完了 したときは、ポート１０６はポート・コントローラ１０４に信号を送る。ポート ・コントローラ１０４は、次にバッファ・コントローラに信号を送り、このコン トローラは、前記パケットによって先に占められていたスペースを７リーにする 。もし、当該ポート１０６からパケット伝送失敗のレポートがあれば、当該パケ ットに関係したカウンタが増分されて、上に述べたようなテストを受ける。

代替ポートを選ばなければならないときは、これらポートのいずれを使うべきか の選択に３つのファクタが影響する。第１は、もしパケットが他の通信プロセッ サで生起したものである場合（即ち、当該通信プロセッサが単にパケットをその 最終宛先に中継している場合）、このパケットはそれを受信したのと同じポート に送られてはならない。もしこのルールに従わなかった場合は、パケットは、よ り適当なルーティングが利用可能になるまで同じそれら二つの通信プロセッサの 間を往復する。これは、“スラッシングと呼ばれる。このスラッシングは、パケ ットがその宛先へ移動するのを遅らせるばかりでなく、パケットが通過するそれ ら二つの通信プロセッサの通信負荷を増大させる。パケットが受信されたボート １０６を指定する情報は、そのパケットと共にバッファ１０２に記憶される。こ の情報は当該パケットを受信したポート１０６によって提供される。このように して、ポート・コントローラはこの問題を回避するのに必要な情報を持つのであ る。

第２に、大形の六辺形アレイ（−辺に３°個の通信プロセッサを持つものより大 きい）においては、長距離通信向けのパケットを送ることができる非常に多くの ルートがあることである。パケットを送るのに選択されたポート１０６は、後の 伝送に対して利用できるルーティング決定の数に影響を与える。これは次の例に よって説明できる。

第８（ａ）図を参照して、通信プロセッサ（１，−２）を離れそして最終宛先が 通信プロセッサ（２，２）に接続されたデータプロセッサであるパケットについ て考えてみる。（２，２）への最適ルートは４つあり、夫々はパケットの４回の 伝送を必要とする。その第１のルートは通信プロセッサ（１，−１）、（１，Ｏ ）及び（１゜ｌ）を通るもの、第２のルートは通信プロセッサ（１゜−１）、（ １，０）及び（２，１）を通るもの、第３のルートは通信プロセッサ（１，−１ ）、（２，０）及び（２，１）を通るもの、そして第４のルートは通信プロセッ サ（２，−１）、（２，Ｏ）及び（２，１）を通るものである。もしもパケット が通信プロセッサ（１，−１）を経由して送られるとすれば、３つの最適ルート が可能であるから、当該通信プロセッサと通信プロセッサ（１，−１）を結ぶポ ート２の方が当該通信プロセッサと通信プロセッサ（２，−１）を結ぶポート１ よりも望ましい。ポート２は、その後のルーティング決定により大きな柔軟性を 与える。

本発明の好適実施例において、この“柔軟性”情報は、パケットが送られるべき 最適ポートの決定と、その最適ボートが利用できない場合の代替ボートの決定の 両方に使われる。上に述べた角度計算アルゴリズムは、自動的にこの情報を考慮 に入れている。上の例において、通信プロセッサ（１，−２）を通信プロセッサ （２，２）に結ぶ線と、ポート２を通るｙ軸に平行の線との角度の差は、前記線 の角度とポート１を通るＤ軸に平行な線の角度との差より小さい。従って。ポー ト２が自動的に選ばれることになる。

最後に、代替ポートの利用可能性について考慮しなければならない。ここで、二 つの代替ポートがあり、それらは同じ長さのパスを持っているが、“柔軟性”が 異なる場合を考えてみる。もし、より大きな柔軟性を持つポートがビジーのとき は、他のポートが選ばれる。パケットの“腐敗度”　（即ち、そのパケットが伝 送を断られた回数）を測るカウンタの臨界値は、そのパケットを平均して一回再 伝送するに要する時間より長い一つの時間を表している。従って、パケットを送 るのには、少しばかり良いルートを待機するよりは、少し劣ったルートを経由し た方が良い。

当業者には明らかなように、複雑さのより少ない他のルーティング・アルゴリズ ムが可能である。例えば、ポート・コントローラは単に、パケットを受信したも のでない無作為に選んだ代替ポートに割当てることができる。

このポートは、パケットをその最終宛先からより遠くに出す方向に送らないよう なポートの中から選ぶことができる。このような無作為な割当てアルゴリズムは 能率は良くないが、これを実施するためのハードウェアが少なくてすむので、経 済的な理由からは好ましい。

ポート・コントローラがポート１０６にパケット伝送を行うよう要求した場合に 、ポート１０６が実行する動作についてのチャートを第１２図に示しである。ポ ート１０６がパケット伝送の要求を受けたが、それがビジーの場合、パケットを 送る試みが不首尾である場合に送られる信号と同じ信号を、ポート・コントロー ラ１０４に送る。もしも当該ボート１０６がフリーであれば、このポートは、パ ケットを当該ポート１０６のバッファに伝送するバッファ・コントローラに信号 を送る。ポート１０６は次に、これが接続される隣接通信プロセッサ中の対応す るポート１０６との通信リンクを確立すべく試みる。もし、それに失敗したら、 ポートはポート・コントローラ１０４に信号を送る。もし、それに成功したら、 ポートは当該パケットを送信し、そして受信側ボート１０６からの、パケットが 正しく受信された旨の信号を待つ。もしもそれが正しく受信されなかつｊ；なら ば、当該ポート１０６はカウンタを増分する。もし、このカウンタのカウントが 所定の臨界値より小さければ、ポートは当該パケットをもう一度送る。もし、そ のカウントが前記臨界値より大きければ、ポートはポート・コントローラ１０４ に対し伝送完了に失敗した旨の信号を送る。もし、受信側ポート１０６が伝送成 功をアクノリッジすると、当該ポート１０６はポート・コントローラ１０４にパ ケットが首尾よく送られた旨の信号を送る。その後に待機状態に入る。

隣接通信プロセッサがポート１０６にパケットを送りたい場合の、ポート１０６ が実行する動作についてのフローチャー小を第１３図に示す。もし、当該ポート １０６がその要求を受けたときにビジーであれば、それは送信側ボートに信号を 送る。この状態は、当該ポートが、そのバッファから先に受けたパケットをバッ ファ１０２に未だ伝送していない場合に起り得る。もし、当該ポート１０６がフ リーであれば、それは当該パケットを取入れる。これと同時に、ポートはバッフ ァ・コントローラからバッファ１０２中のバッファ・スペースを要求する。

伝送完了時に、当該ポートは、通常のサイクリック冗長検査（ＣＲＣ）によって パケットの正しい伝送を検査する。もし、パケットが正しく伝送されなかったと きは、当該ポートは送信側ポートに信号を送る。もし、パケットが首尾よく伝送 されかつバッファ１０２内のスペースが利用可能であっｔ；ときは、当該ポート は、パケットをバッファに送ってこれをバッファ・コントローラによって割当て られた位置に記憶させる。スペースが利用できないときは、送信側ポートに伝送 失敗の信号を送る。

直接記憶アクセス・コントローラ１０８は、バッファ１０２中に記憶されたパケ ットを通してサイクルし、続く処理を最も長く待機していてしかも最終宛先が当 該通信プロセッサであるパケットを捜し出すまで続く。直接記憶アクセス・コン トローラ１０Ｂは、パケット中のヘッダ情報を検査して、このパケットが引出さ れた元のメツセージが一つより多いパケットを必要としたかどうかを決定する。

もし、ただ一つのパケットが使われたのならば、直接記憶アクセス・コントロー ラはそのパケットのメツセージ部分をデータプロセッサのメモリに記憶し、そし てメツセージの到着をそのデータプロセッサに通知する。

直接記憶アクセス・コントローラ１０ｇは、一つより多いパケットに分割された メツセージの再組立てに使うテーブルを含んでいる。もし、当該メツセージが一 つより多いパケットを持っていたら、直接記憶アクセス・コントローラ１０８は このテーブルを調べて、それがメツセージから受けた最初のパケットかどうかを 決定する。

もし、それが最初のパケットであれば、直接記憶アクセス・コントローラ１０８ は、テーブルへのこのメツセージのｌ；めのエントリをスタートし、そして全メ ツセージを記憶するためにデータプロセッサのメモリ中の充分なスペースを割当 てる。直接記憶アクセス・コントローラ１０８は次に、この当該パケットを、デ ータプロセッサのメモリのこのメツセージのために用意されたメモリブロック内 の適当な位置に記憶する。そして次にバッファ１０２中の他のパケットを探索す る。もし、当該パケットがメツセージの最初のパケットでない場合は、直接記憶 アクセス・コントローラ１０８は、このパケットを受取ったことを示すエントリ をテーブルに行い、そしてそのパケットをデータプロセッサのメモリ中の適当な 位置に記憶する。もし、当該パケットがメツセージを完了するのに最後に残った パッケージである場合は、直接記憶アクセス・コントローラ１０ｇは、そのテー ブルを消去し、そしてデータプロセッサにメツセージを受取った旨の信号を送る 。

データプロセッサが送るべきメツセージを持っているときは、それは直接記憶ア クセス・コントローラ１０ｇに、データプロセッサ・メモリ１１０中のメツセー ジの位置を与える信号を送る。直接記憶アクセス・コントローラ１０８は次にそ のメツセージを取出し、適当なヘッダ情報をそのメツセージに割当て、そしてそ れをパケットに分割する。次にこれらパケットはバッファ１０２に記憶される。

受信側通信プロセッサにこのメツセージの諸パケットを他のメツセージのパケッ トから識別させるため、独特なメツセージ・ラベルがヘッダ情報の中に含まれて いる。例えば、このラベルは、メツセージを送る通信プロセッサの識別と、この 通信プロセッサによりメツセージが送られる度に増分されるシーケンス番号と、 から成っている。

通信プロセッサが実行する各種タスクの優先順位とバッファ１０２中のスペース の割当てとは、通信隘路の可能性を最小にするように選ばれる。６個のポート１ ０６及び直接記憶アクセス・コントローラ１０８は全て同じバッファ１０２を共 用しており、それからパケットが伝送のため検索されそして到着時に記憶される 。この共用バッファは、内部バスと配線の数を最小にし、各通信プロセッサに必 要とするバッファ・スペース量を減らしている。

しかしながら、このアーキテクチャはまた、共用資源としてのバッファに対する 潜在的な競争の問題をもたらす。

通信プロセッサ中のパケット伝送には、三つの一般的なトラフィック・パターン と、二つの可能なデッドロック・シナリオがある。デッドロックが生ずるのは、 全てのバッファ・スペースが、隣接通信プロセッサ全てがパケットを受入れるに はビジー過ぎるため送ることができないでいるメツセージで一杯になった場合で ある。トラフィック・パターンは、当該通信プロセッサに接続されたローカル・ データプロセッサからリモート通信プロセッサへのアウトバウンド・パケット、 宛先が当該通信プロセッサに接続されたデータプロセッサであるリモート通信プ ロセッサからのインバウンド・パケットから成り、そして相互通信プロセッサ・ トラフィックは、当該通信プロセッサによって最終宛先に向けて中継されている リモート通信プロセッサで生起したパケットから成っている。

アウトバウンド・パケット及び相互通信プロセッサ・パケットは共にポート１０ ６を通るルートを取る。インバウンド・パケットもまた、直接記憶アクセス・コ ントローラ１０８を通って流れねばならない。

好適実施例において使われたバッファ割当てアルゴリズムは、デッドロックを作 らないことが保証されている。

これは、パケットがデッドロックのない通信ネットワークを横切って循環するの に充分なフリー・バッファ・スペースを保有しているために達成できたのであり 、同時に、このバッファ・スペースを、六辺形アレイを横切る効率的なパケ！ノ ドの流れをもたらすような方法で割当てる。もっと悪い場合には、パケット伝送 の遅れを生じる。

好適実施例において、バッファ１０２は少なくとも４個のパケット分のスペース を持っている。異なった数のパケットに対するバッファ・スペースを持ったシス テムのシミュレーションでは、３個の通信グロセッサを一辺に持った六辺形アレ イにおける最適バッファ記憶容量は、１９パケツトである。このバッファ・スペ ースは、バラ”　フチ１０２中に残りが３パケット分のフリー・スペースクセス ・コントローラ１０８によりどの方向のトラフィックに対しても使用できる。こ の３個分のフリー・スペースきなった時点で、ポート１０６から入ってくるパケ ットは、それらがデッドロック発生の原因にならないという保証のためテストさ れなければならない。１個のインバウンド・パケットに対するスペースは、デッ ドロックが発生しないよう、常にフリーにしておかなければならない。ポート１ ０６から入ってくる、デッドロックを起こすようなどのパケットも拒否される。

デッドロックを防ぐのには、もう一つのパケット分のスペースがあれば足りるの であるが、好適実施例では能率を上げるために、さらに３パケット分のスペース を準備している。追加３個のパケットに対するスペースしかない場合は、直接記 憶アクセス・コントローラ１０８は、それ以上はバッファにパケットの追加をし ない。この場合、直接記憶アクセス・フントｃ７−２は、ただ、インバウンド− パケットをそのバッファから取去るだけである。

もし、一つのボート１０６上の１個のインバウンド・パケットが当該通信プロセ ッサに接続されたデータプロセッサに向けられており、しかもそのようＩこ向け られた他の一つのパケットが直接記憶アクセス・コントローラ１０８のデータプ ロセッサへの伝送のため待ち行列に既にある場合は、そのインバウンド・パケッ トはポート１０６によって拒否される。相互通信プロセッサ・パケットは、前記 パケットの受け入れが、当該通信プロセッサに接続されたデータプロセッサへの １個のインバウンド・パケットのためのスペースをバッファ１０２中に残すもの となる限り、受は入れられる。この用法は、通信ネットワークが局部的にオーバ ロードになったときに、パケット“製造者”の優先順位を下げそしてパケット“ 消費者”の優先順位を上げるという効果をもっている。

諸パケットが、隣接通信プロセッサへの伝達のためバッファ１０２の待ち行列に あるときは、ポート・コントローラ１０４は、バッファ１０２中のそれらパケッ トをそれらの宛先のポート１０６に送ることで、その数を減らそうとする試みを 続ける。このことは、各パケットの宛先ボート１０６を利用できるボートリスト と突合せることで行われる。上に説明したように、もし希望するポート１０６が ビジーのときは、当該パケットに対するカウントが増分される。このカウントが 所定の値を越えたききは、そのパケットに割当てられたポート１０６は、もし可 能であれば、他の代替ボート１０６に変更される。

待ち行列のパケットの数を減らすことは、バッファ１０２への新しいパケットの 記憶よりも優先する。従って、ポート・コントローラ１０４は、バス１１２より も、パケットを隣接通信プロセッサに伝送する用意のできているポート１０６に 優先権を与える。直接記憶アクセス・コントローラ１０８は、それがバッファか ら当該通信プロセッサに接続されたデータプロセッサにパケット伝送していると きに最高の優先順位を持っている。

ここには二つの起こり得るオーバロード状態がある。

その第１は、通信プロセッサに対する全ロードは比較的少ないが、しかし、ポー ト１０６のいくつかが１個のポートから全て再伝送されるべき到来パケットを持 っている場合について考えてみる。この場合、通信プロセッサに対する全ロード は少なくても、多くのパケットが１個のポート１０６を通って配送されるのを待 っている（只一つのポート１０６が苛酷に使われている）。この通信プロセッサ を他の隣接通信プロセッサとリンクしているフリーのポート１０６は多くあるの で、この場合は、パケットを代替ポート１０６を通す別ルートにするのが有利で ある。上に述べたアルゴリズムが自動的にこのルート変更を行う。何故なら、パ ケットがポート・コントローラ１０４により検査され、そしてそれが、割当てら れたポート１０６がビジーのため配送できないことを見出す度毎に、カウンタが 増分されるからである。そのカウントが所定の値を越えたときは、もしできれば 、そのパケットは別ルートに回され、そのワークロードを使用の少ないポート１ ０６に移す。

次に、多くの隣接通信プロセッサで混雑している場合について考える。バッファ １０２は６個のポート１０６全部に向けられたパケットで直ぐに一杯になる。苛 酷に使われていないポート１０６にルート変更できるパケットは、そのようにル ート変更される。これはまた、少ないロードの状態においてより平等なパケット ロード配分をもたらすことになる。しかしながら、これは、パケット伝送の一層 の後れを加えることにもなる。最後に、デッドロック防止に関して上述したよう に、混雑した所での新しいパケットの生成は、その混雑を救うために、減らされ る。

当業者には、本発明の請求の範囲から外れることなく、種々の変更ができること は明らかであろう。

２ｇ ＦＩＧＵＲＥ　１ ＦＩＧＵＲＥ　３（ｅ） ＦＩＧｔＪＲＥ　３Ｔｏｌ ＼す ＦＩＧＵＲＥ　Ｈ５ ＦＩＧＵＲＥ　１１ 国際調査報告 Ｉｎ瞳＋ＩＩ＋ｌ自ａｎｍｌＡａｐｌｉ＋＋＋：ｏｎＮｏ、ＰＣＴ１０５８６１ ０２０３９

Claims (12)

【特許請求の範囲】
1. １．複数個のデータプロセッサを含むデータ処理システムであって、各前記デー タプロセッサが、前記データ処理システム中の他のデータプロセッサに送るまた はそれから受取るメッセージを記憶するためのメモリ手段を含む、前記データ処 理システムにおいて、前記データ処理システム中の任意の二つのデータプロセッ サの間でメッセージを送るための通信ネットワークが、六辺形アレイの通信プロ セッサであって、該六辺形アレイの各辺にＥ通信プロセッサを持ち、各前記通信 プロセッサが一つの前記データプロセッサに作用上接続されている、六辺形アレ イの通信プロセッサを含み、各前記通信プロセッサが、前記通信プロセッサに結 合されたデータプロセッサとメッセージを交換するための手段と、前記六辺形ア レイ中の前記通信プロセッサに隣接する通信プロセッサにメッセージを送りまた はそれからメッセージを受けるためのポート手段と、を含み、該ポート手段は６ 個の個々のポートを持ち、前記ポート手段中の各前記ポートは前記通信プロセッ サに隣接する複数個の通信プロセッサの中の異なった一つの応対するポートに作 用上接続されていること、 から成る通信ネットワーク。
2. ２．請求の範囲第１項記載の通信ネットワークにおいて、さらに、一つの隣接通 信プロセッサの対応ポートに結合されていない前記六辺形アレイのエッジ上の各 通信プロセッサの前記ポートを、前記六辺形アレイの反対側エッジ上の通信プロ セッサの対応ポートに結合するためのシグナルパス手段を含み、これによってメ ッセージが前記六辺形アレイ中の任意の通信プロセッサから前記六辺形アレイ中 の他のＥ−２通信プロセッサより多くを通過せずに前記六辺形アレイ中の任意の 他の通信プロセッサに送ることができるようにする、通信ネットワーク。
3. ３．請求の範囲第２項記載の通信ネットワークにおいて、各前記シグナルパス手 段は、さらに、少なくとも一つの前記エッジ・ポートに作用上接続されたスイッ チ手段を含んでおり、該スイッチ手段は、前記エッジ・ポートを前記六辺形アレ イの外部のデータプロセッサに選択的に結合する手段を含む、通信ネットワーク 。
4. ４．請求の範囲第１項記載の通信ネットワークにおいて、各前記ポートは、さら に、 それが結合されるべき前記対応ポートがメッセージを受けることができるかどう かを決定する手段、前記対応ポートに送られたメッセージが正しく伝送されたか どうかを決定する手段、 前記メッセージが正しく伝送されなかった場合に前記メッセージを繰返す手段、 前記ポートがメッセージを受けることができる旨を前記対応ポートに通知する手 段、 前記ポートが前記対応ポートから受けたメッセージが正しく伝送されたかどうか を決定する手段、及び前記対応ポートが送った最後のメッセージを前記対応ポー トに繰返させる手段、 を含んでいる通信ネットワーク。
5. ５．請求の範囲第１項記載の通信ネットワークにおいて、前記通信プロセッサは 、さらに、 メッセージを記憶するためのパッファ手段、該パッファ手段に記憶された各メッ セージのための宛先ポートを指定する手段であって、前記宛先ポートは、前記通 信プロセッサが作用上接続されたデータプロセッサであるか、または送られるべ き前記メッセージが通過するポートであること、 前記通信プロセッサに作用上接続された前記メモリ手段と前記バッアァ手段との 間でメッセージを転送するための直接記憶アクセス・コントロール手段、及び前 記バッファ手段中に記憶されたメッセージを前記宛先ポート指定手段が指定する 前記ポートに結合させ、かつ前記ポートの一つが受けたメッセージを前記バッフ ァ手段に記憶させるためのコントロール手段、から成る通信ネットワーク。
6. ６．請求の範囲第５項記載の通信ネットワークにおいて、前記バッアァ手段は榎 数個の記憶スロットを含み、前記メッセージは一つの記憶スロットに記憶するに は長すぎるメッセージを含み、また、前記直接記憶アクセスコントロール手段は 、さらに、 長いメッセージを分割によって、複数個の夫々のサイズが対応する記憶スロット に記憶されるような短いメッセージを作る手段であって、各前記短いメッセージ は、これが作られた元の前記長いメッセージと及び前記長いメッセージから作ら れた他の短いメッセージとの関係とを指定する情報を含むこと、及び 長いメッセージの分割によって発生した前記短いメッセージを再結合して前記長 いメッセージを再構成するための手段、 を含むこと、を特徴とする通信ネットワーク。
7. ７．請求の範囲第５項記載の通信ネットワークにおいて、前記コントロール手段 は、さらに、前記バッファ手段に記憶されたところの宛先ポートがポートである 各メッセージを逐次的に検査する手段、前記ポートに結合した前記通信プロセッ サが前記メッセージを受けることができるかどうかを確認する手段、前記ポート に結合する前記通信プロセッサが前記メッセージを受けることができる場合、前 記メッセージを前記バッファ手段から前記ポートに結合させる手段、前記ポート に結合した前記通信プロセッサがメッセージを受けることができなかったために 前記メッセージを送れなかった回数をカウントする手段、前記カウント手段が所 定の回数より多くは送れないことを示す場合、前記宛先ポート指定手段に、前記 メッセージのための別の宛先ポートを指定させる手段、を含む二と、を特徴とす る通信ネットワーク。
8. ８．複数個のデータプロセッサを持つデータ処理システムであって、各前記デー タプロセッサは、前記データ処理システム中の他のデータプロセッサに送るまた はそれから受けるメッセージを記憶するためのメモリ手段を含んでいて、このメ モリ手段は通信プロセッサの六辺形アレイ中に含まれている一つの通信プロセッ サに作用上接続されている、前記データ処理システムにおいて、通信プロセッサ は、 前記通信プロセッサに結合したデータプロセッサとメッセージを交換する手段、 及び 前記六辺形アレイ中の前記通信プロセッサに隣接する通信プロセッサにメッセー ジを送るまたはそれからメッセージを受けるためのポート手段であって、該ポー ト手段は、６個の個々のポートを含み、前記ポート手段中の各前記ポートは前記 通信プロセッサに隣接している複数個の通信プロセッサの内の異なった一つの通 信プロセッサの対応ポートに作用上接続されていること、から成るデータ処理シ ステム。
9. ９．請求の範囲第８項記載の通信プロセッサにおいて、前記ポートは、さらに、 前記ポートが結合されるべき前記対応ポートがメッセージを受けることができる かどうかを決定する手段、前記対応ポートに送られたメッセージが正しく伝送さ れたかどうかを決定する手段、 前記メッセージが正しく伝送されなかった場合に前記メッセージを繰返す手段、 前記ポートがメッセージを受けることができる旨を前記対応ポートに通知する手 段、 前記ポートが前記対応ポートから受けたメッセージが正しく伝送されたかどうか を決定する手段、及び前記対応ポートが送った最後のメッセージを前記対応ポー トに繰返させる手段、 を含んでいる通信プロセッサ。
10. １０．請求の範囲第９項記載の通信プロセッサにおいて、さらに、 メッセージを記憶するためのバッファ手段、該バッファ手段に記憶された各メッ セージのための宛先ポートを指定する手段であって、前記宛先ポートは、前記通 信プロセッサが作用上接続されたデータプロセッサであるか、または送られるべ き前記メッセージが通過するポートであること、 前記通信プロセッサに作用上接続された前記メモリ手段と前記バッファ手段との 間でメッセージを転送するための直接記憶アクセス・コントロール手段、及び前 記バッファ手段中に記憶されたメッセージを前記宛先ポート指定手段が指定する 前記ポートに結合させ、かつ前記ポートの一つが受けたメッセージを前記バッフ ァ手段に記憶させるためのコントロール手段、から成る通信プロセッサ。
11. １１．請求の範囲第１０項記載の通信プロセッサにおいて、前記バッファ手段は 複数個の記憶スロットを含み、前記メッセージは一つの記憶スロットに記憶する には長すぎるメッセージを含み、また、前記直接記憶アクセス・コントロール手 段は、さらに、 長いメッセージを分割によって、複数個の夫々のサイズが対応する記憶スロット に記憶されるような短いメッセージを作る手段であって、各前記短いメッセージ は、これが作られた元の前記長いメッセージと及び前記長いメッセージから作ら れた他の短いメッセージとの関係とを指定する情報を含むこと、及び 長いメッセージの分割によって発生した前記短いメッセージを再結合して前記長 いメッセージを再構成するための手段、 を含むこと、を特徴とする通信プロセッサ。
12. １２．請求の範囲第１０項記載の通信プロセッサにおいて、前記コントロール手 段は、さらに、前記バッファ手段に記憶されたところの宛先ポートがポートであ る各メッセージを逐次的に検査する手段、前記ポートに結合した前記通信プロセ ッサが前記メッセージを受けることができるかどうかを確認する手段、前記ポー トに結合する前記通信プロセッサが前記メッセージを受けることができる場合、 前記メッセージを前記バッファ手段から前記ポートに結合させる手段、前記ポー トに結合した前記通信プロセッサがメッセージを受けることができなかったため に前記メッセージを送れなかった回数をカウントする手段、前記カウント手段が 所定の回数より多くは送れないことを示す場合、前記宛先ポート指定手段に、前 記メッセージのための別の宛先ポートを指定させる手段、を含むこと、を特徴と する通信プロセッサ。