JPH0877127A - プロセッサ間データ転送方法及び並列計算機 - Google Patents

Abstract

(57)【要約】 【目的】 ネットワークにおける故障の有無にかかわら
ず、１対１転送、ブロードキャスト等のメッセージの転
送におけるデッドロックを回避することにある。 【構成】 プロセッサと中継スイッチ及びクロスバスイ
ッチ、ホスト計算機またはＳＶＰで構成され、中継スイ
ッチ及びクロスバスイッチは、経路指示回路と経路情報
変更回路と、迂回指示回路及び一致判定回路（中継スイ
ッチ）を有し、例えば、ＰＥ０１からメッセージをブロ
ードキャストする場合、メッセージ中の転送制御情報
と、ホスト計算機またはＳＶＰにより中継スイッチ及び
クロスバスイッチに設定された経路情報により、ブロー
ドキャストメッセージをまず特定のクロスバスイッチ
（例えば、１３５）に転送し、そこからブロードキャス
トする。また、１対１転送メッセージの転送経路中の部
分ネットワークに故障がある場合には、まず、特定のク
ロスバスイッチに迂回転送し、そこから１対１転送す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、複数のプロセッサ間で
ネットワークを介してメッセージ転送を行なうプロセッ
サ間データ転送方法及び並列計算機に係り、特に一つの
プロセッサから多数のプロセッサにデータを転送する放
送機能を有するプロセッサ間データ転送方法及び並列計
算機に関する。

【０００２】

【従来の技術】複数のプロセッサ間でネットワークを介
してメッセージ転送を行なう並列計算機において、重要
なデータ転送機能にブロ−ドキャストがある。キューブ
型のネットワークを持ち、あるプロセッサから他のプロ
セッサへの転送経路が短かくデータを高速に転送できる
並列計算機において、ブロードキャスト機能を実現する
方法としては、例えば特開平１−２６７７６３に開示さ
れている方式がある。上記特開平１−２６７７６３に開
示されている方式は、ｎ台のプロセッサをｎ＝ｎ₁×ｎ₂
×ｎ₃×……×ｎ_nと因数分解し、これらの因数の各々を
１辺の格子点数とするｎ次元格子空間上にプロセッサを
並べ、その各辺をクロスバスイッチからなる部分ネット
ワークで結合してメッセージ転送経路を構成し、１つの
プロセッサから全プロセッサへデータを並列に転送する
ブロードキャスト機能を実現している。

【０００３】並列計算機におけるデータ転送機能とし
て、ブロードキャストの他に、ある限定された範囲のプ
ロセッサの集まりであるプロセッサグループ内のプロセ
ッサにのみデータを転送する、部分ブロードキャスト機
能がある。部分ブロードキャスト機能を実現する方法と
しては、例えば、特開平５−２８１２２に開示されてい
る方式がある。上記特開平５−２８１２２に開示されて
いる方式は、部分ブロードキャストすべきプロセッサ群
により定まる転送制御情報（ｔｒａｎｓｍｉｔ ｃｏｎ
ｔｒｏｌ ｉｎｆｏｒｍａｔｉｏｎ）をネットワークに
あらかじめ記憶し、ネットワーク途中の複数箇所（転送
制御点）に部分ブロードキャストメッセージが到達した
場合に、その転送制御情報に従ってそのメッセージを下
流に転送するか否かを制御して、転送不要な経路へのデ
ータ転送がなるべく生じないように部分ブロードキャス
トを実現している。

【０００４】並列計算機では一般に、データ転送方式と
してワ−ムホ−ルルーティングを用いている。このルー
ティングは、先だってすべての経路を確保しない。ある
経路では、データの先頭からデータの終わりが通りぬけ
る間のみ経路を確保する。ある経路を確保できない場
合、先に確保した経路を確保したまま待たされることに
なる。ところが、上記に示したブロードキャストおよび
部分ブロードキャスト方式の実施例で用いられている、
クロスバスイッチからなる複数の部分ネットワークから
なるネットワークを介して複数のプロセッサ間でメッセ
ージ転送を行なう並列計算機では、複数のプロセッサか
ら同時にブロードキャストメッセージが転送されると、
転送経路をとりあうことにより、デッドロックが発生す
る。上記の実施例は、システム中の唯１つのプロセッサ
から全プロセッサへデータを並列に転送する方法である
ため、複数のプロセッサからブロードキャストが発生し
た場合にデッドロックが発生してしまう。これを解決す
る方法として、電子情報通信学会技術研究報告Ｖｏｌ．
９３，Ｎｏ．３２０では、ブロードキャストを実行する
プロセッサをシステム中で唯１つに制限する方法が紹介
されている。

【０００５】さらに、上記に示したブロードキャストお
よび部分ブロードキャスト方式の実施例は、障害が発生
した場合には対処できない。クロスバスイッチからなる
複数の部分ネットワークからなるネットワークにおい
て、故障が発生した場合にデータを転送する方法として
は、例えば特開平３−２０９５５０に開示されている方
式がある。上記特開平３−２０９５５０に開示されてい
る方式では、各部分ネットワークがそれぞれ接続する部
分ネットワークの故障情報を持つことにより、故障した
部分ネットワークにメッセージが送られるのを防止す
る。また、各部分ネットワークの選択アルゴリズムにお
いて、（前段の）部分ネットワークに接続した入力ポー
トからのメッセージを同じ部分ネットワークを接続した
出力ポートに送ることがないため、ネットワーク上でメ
ッセージが無限ループに陥ることなく、メッセージを正
しく受信プロセッサに転送することができる。

【０００６】

【発明が解決しようとする課題】上記電子情報通信学会
技術研究報告Ｖｏｌ．９３，Ｎｏ．３２０では、ブロー
ドキャストを実行するプロセッサをシステム中で唯１つ
に制限することで、デッドロックを回避している。この
場合、他のブロードキャストを実行したいプロセッサ
は、一旦ブロードキャストを実行するプロセッサにメッ
セージを送り、ブロードキャストの代行をしてもらう。
しかしながら、一旦プロセッサにブロードキャストメッ
セージを取り込むと転送オーバーヘッドが大きくなる。
また、唯１つのプロセッサにブロードキャストメッセー
ジを集めるために、そのプロセッサへメッセージが集中
し、性能が低下する恐れがある。また、ブロードキャス
ト用のプロセッサから最も離れたプロセッサからのブロ
ードキャストメッセージであってもブロードキャスト用
のプロセッサを経由して転送しなければならないために
転送距離が通常の倍になり、性能が低下してしまう。

【０００７】また、上記特開平３−２０９５５０では、
各部分ネットワークがそれぞれ接続する部分ネットワー
クの故障情報を持つことにより、故障した部分ネットワ
ークにメッセージが送られるのを防止する。しかしなが
ら、部分ネットワーク故障時に、ブロードキャストと１
対１転送、ブロードキャストと部分ブロードキャスト、
複数のブロードキャストがほぼ同時に発生した場合には
故障経路を迂回することによりデッドロックが発生して
しまう。

【０００８】本発明の目的は、複数のプロセッサからブ
ロードキャストメッセージ及び部分ブロードキャストメ
ッセージを転送する場合に、デッドロックを回避し、特
定プロセッサへのメッセージの集中を緩和するプロセッ
サ間データ転送方法及び並列計算機を提供することにあ
る。本発明の別の目的は、故障部分ネットワークを有す
るシステムにおいて、複数のプロセッサから１対１転送
メッセージ、ブロードキャストメッセージ及び部分ブロ
ードキャストメッセージを転送する場合に、特定プロセ
ッサへのメッセージの集中を緩和し、デッドロックを回
避するプロセッサ間データ転送方法及び並列計算機を提
供することにある。

【０００９】

【課題を解決するための手段】上記目的を達成するた
め、本発明は、ｎ次元（ｎ≧２）の各次元毎に複数の部
分ネットワークを設け、各次元の部分ネットワークの交
点に該各次元の部分ネットワークに接続される中継スイ
ッチを配置し、該中継スイッチにプロセッサを接続し、
複数のメッセージを複数のプロセッサ間で並列に転送可
能にしたネットワークにおけるメッセージを転送先プロ
セッサに転送するプロセッサ間データ転送方法であっ
て、ブロードキャストメッセージを逐次化するための部
分ネットワークであるシリアライズネットワークの経路
情報を各部分ネットワーク及び各中継スイッチ中に予め
記憶し、送信元プロセッサから転送されるブロードキャ
ストメッセージを前記経路情報に従って部分ネットワー
ク及び中継スイッチを介してシリアライズネットワーク
に転送し、該シリアライズネットワークは該シリアライ
ズネットワークに接続された各中継スイッチを介して次
元の異なる各部分ネットワークにメッセージを転送し、
該各部分ネットワークに接続された中継スイッチを介し
て各プロセッサにメッセージをブロードキャストするよ
うにしている。また、前記部分ネットワークの故障情報
を関連する前記中継スイッチに予め記憶し、該関連する
中継スイッチに接続されたプロセッサが送信元プロセッ
サとして１対１メッセージを転送するとき、該中継スイ
ッチは前記故障情報に基づき該メッセージを前記シリア
ライズネットワークに転送するようにしている。また、
前記中継スイッチの故障情報を関連する前記部分ネット
ワークに予め記憶し、前記部分ネットワークは送信元プ
ロセッサから転送される１対１メッセージを前記故障情
報に基づき故障中継スイッチを介することなく転送する
ようにしている。また、前記経路情報は前記部分ネット
ワークに付された番号を含む情報であるようにしてい
る。また、前記部分ネットワークはクロスバスイッチで
あるようにしている。また、前記部分ネットワークは、
前記経路情報により転送先を決定する手段を有するよう
にしている。また、前記中継スイッチは、前記故障情報
により転送先を決定する手段を有するようにしている。
また、前記部分ネットワークは、前記故障情報により転
送先を決定する手段を有するようにしている。また、前
記中継スイッチは、該中継スイッチに接続されたプロセ
ッサの装置番号と前記経路情報を比較する手段を有する
ようにしている。また、前記転送先を決定する手段は、
該転送先としてシリアライズネットワークあるいはメッ
セージ中の転送先プロセッサのいずれかを選択する選択
手段を有するようにしている。また、前記シリアライズ
ネットワークに接続され、該シリアライズネットワーク
にメッセージを転送する中継スイッチは、該メッセージ
を同時に、該中継スイッチに接続された他の部分ネット
ワーク及び該中継スイッチに接続されたプロセッサに転
送し、該シリアライズネットワークは該中継スイッチか
ら転送されたメッセージを該中継スイッチには転送しな
いようにしている。また、ブロードキャストメッセージ
をシリアライズネットワークからブロードキャストする
場合には、該シリアライズネットワークに接続された全
ての中継スイッチにメッセージを転送し、ブロードキャ
ストメッセージをシリアライズネットワーク以外の部分
ネットワークからブロードキャストする場合には、該部
分ネットワークへブロードキャストメッセージを転送し
た中継スイッチ以外の全ての中継スイッチにメッセージ
を転送するようにしている。またさらに、ｎ次元（ｎ≧
２）の各次元毎に複数の部分ネットワークを設け、各次
元の部分ネットワークの交点に該各次元の部分ネットワ
ークに接続される中継スイッチを配置し、該中継スイッ
チにプロセッサを接続し、複数のメッセージを複数のプ
ロセッサ間で並列に転送可能にしたネットワークにおい
て、該複数のプロセッサから選択された一群のプロセッ
サに選択的に部分ブロードキャストメッセージを転送す
るプロセッサ間データ転送方法であって、前記部分ブロ
ードキャストメッセージ内に前記一群のプロセッサを指
定する範囲情報を設定し、部分ブロードキャストメッセ
ージを逐次化するための部分ネットワークであるシリア
ライズネットワークの経路情報を各部分ネットワーク及
び各中継スイッチ中に予め記憶し、送信元プロセッサか
ら転送される部分ブロードキャストメッセージを前記経
路情報に従って部分ネットワーク及び中継スイッチを介
してシリアライズネットワークに転送し、該シリアライ
ズネットワークは、該シリアライズネットワークに接続
され、前記範囲情報の条件を満たす中継スイッチを介し
て次元の異なる部分ネットワークにメッセージを転送
し、該部分ネットワークは前記範囲情報の条件を満たす
中継スイッチを介してプロセッサにメッセージを転送す
るようにしている。また、前記経路情報は前記部分ネッ
トワークに付された番号を含む情報であるようにしてい
る。また、前記部分ネットワークはクロスバスイッチで
あるようにしている。

【００１０】

【作用】本発明は、上述した構成により、次のような作
用を有している。送信元プロセッサにおいてブロードキ
ャストメッセージおよび部分ブロードキャストメッセー
ジが発生すると、部分ネットワークは、あらかじめ記憶
された転送制御情報に従ってシリアライズネットワーク
にそのメッセージを転送する。また、送信元プロセッサ
において１対１転送が発生した場合に、その転送経路中
に故障部分ネットワークがあると、部分ネットワークは
あらかじめ記憶された故障情報に従ってシリアライズネ
ットワークにそのメッセージを転送する。そして、シリ
アライズネットワークはメッセージ中の転送制御情報に
よりメッセージを該当するプロセッサに転送する。これ
によって、デッドロックを回避し、かつ特定プロセッサ
の転送オーバーヘッドを削減し、かつ特定プロセッサへ
のメッセージの集中を緩和するブロードキャストおよび
部分ブロードキャストを実現することができる。さら
に、部分ネットワーク中に故障がある場合にも、デッド
ロックを回避し、かつ特定プロセッサへのメッセージの
集中を緩和するプロセッサ間データ転送を実現すること
ができる。

【００１１】

【実施例】

＜第１の実施例＞第１の実施例を図面を参照して説明す
る。本実施例では、複数ブロードキャストが発生した場
合に、ブロードキャストのシリアライズを特定の部分ネ
ットワークで行うこと、さらに部分ネットワークのうち
のいずれか１箇所が故障している場合に、複数ブロード
キャストのシリアライズおよび、１対１転送の迂回を特
定の部分ネットワークで行うことを考える。複数の故障
にも対処できる場合もあるが、ここでは、故障を１箇所
に限定することにより、動作を保証する。また本実施例
では、特定ＰＥへのメッセージ転送（１対１転送）と、
全ＰＥへのメッセージ転送（ブロードキャスト）が可能
になっている。

【００１２】図１は本実施例における並列計算機の構成
を示したものである。図１において１００〜１１５は並
列計算機を構成するプロセッサ（以下ＰＥと略する）で
ある。１３２〜１３５はＸ方向のクロスバスイッチ（以
下Ｘ−ＸＢと略する）、１３６〜１３９はＹ方向のクロ
スバスイッチ（以下Ｙ−ＸＢと略する）であり、それぞ
れ上記部分ネットワークに対応するものである。以下で
は、これらのクロスバスイッチを区別しない場合は、単
にＸＢと呼ぶことがある。１１６〜１３１は各Ｘ−ＸＢ
と各Ｙ−ＸＢの交点に設けられた中継スイッチ（以下Ｅ
Ｘと略する）である。ＸＢ、ＥＸをまとめてハイパクロ
スバネットワークと呼ぶ。１４０はホスト計算機または
サービスプロセッサ（ＳＶＰ）である。

【００１３】上記各ＰＥは、図１中には示されていない
が、内部にデータおよびプログラムを格納するメモリ
と、データを用いてプログラムを実行するＣＰＵで構成
され、それぞれ独立に動作可能である。各ＰＥは２次元
座標空間の１つの格子点のＸ座標、Ｙ座標をそのＰＥ番
号として与えられている。各Ｘ−ＸＢは同一のＹ座標を
有するＰＥに対して設けられ、そのＹ座標ｉをつけてＸ
ｉ−ＸＢと呼ぶ。各Ｙ−ＸＢは同一のＸ座標を有するＰ
Ｅに対して設けられ、そのＸ座標ｊをつけてＹｊ−ＸＢ
と呼ぶ。各ＥＸは１つのＰＥに対応して設けられ、以下
では対応するＰＥと同じ番号をつける。ここでは、Ｘ方
向の４本のＸＢ、Ｙ方向の４本のＸＢを持つ並列計算機
を例にとったが、実際はＸ方向ｍ本のＸＢ、Ｙ方向ｎ本
のＸＢでもよい。また、２次元構成の並列計算機を例に
とったが、ｎ次元構成でもよい。ホスト計算機またはＳ
ＶＰ１４０は、各プロセッサ１００〜１１５へプログラ
ムとデータをロードし、また、プログラムの終了後、各
プロセッサで得られた結果のデータを読み出す。また、
ブロードキャストを逐次化し、また故障時の１対１転送
を迂回するための部分ネットワーク（以下、シリアライ
ズネットワークと呼ぶ）の経路情報（以下、シリアライ
ズネットワーク番号と呼ぶ）をあらかじめセットする。

【００１４】複数のブロードキャストをシリアライズす
るシリアライズネットワークはいずれのクロスバスイッ
チでもよい。いずれかのＸ系クロスバスイッチ（Ｘｉ−
ＸＢ）が故障している場合、シリアライズネットワーク
は、Ｘｉ−ＸＢと同次元かつ異なるクロスバスイッチ
（Ｘｊ−ＸＢ（ｉ≠ｊ））であればいずれでもよい。例
えば、クロスバスイッチ１３４（Ｘ２−ＸＢ）が故障し
ている場合、シリアライズネットワークは、クロスバス
イッチ１３５（Ｘ３−ＸＢ）とする。逆に、Ｙ系クロス
バスイッチが故障している場合は、Ｙ系クロスバスイッ
チの一つをシリアライズネットワークとする。中継スイ
ッチが故障している場合、シリアライズネットワーク
は、その故障中継スイッチが接続していないクロスバス
イッチであればいずれでもよい。また、本実施例では、
メッセージの転送には、固定ルーティングを用い、すべ
てのメッセージに対して故障ＸＢ（シリアライズネット
ワーク）のある次元方向にまず転送したのち、他次元に
転送する。例えば、Ｘ系ＸＢが故障している場合、通常
ルーティングのメッセージを、まずＸ方向に転送し、次
にＹ方向に転送する。反対に、Ｙ系ＸＢが故障している
場合は、メッセージをまずＹ方向に転送し、次にＸ方向
に転送する。本実施例では、例として２次元構成の場合
について述べるが、Ｎ次元構成の場合についても同様で
ある。例えば、ｉ次元のクロスバスイッチが故障した場
合、シリアライズネットワークは故障ＸＢ以外のｉ次元
クロスバスイッチとし、メッセージの転送順序は、ｉ次
元方向→ｉ＋１次元方向→ｉ＋２次元方向→…→ｉ−１
次元方向とすればよい。

【００１５】各ＥＸは対応するＰＥ、Ｘ−ＸＢまたはＹ
−ＸＢから転送されたメッセージをＹ−ＸＢ、Ｘ−ＸＢ
またはＰＥに転送する回路である。ＥＸは、ＥＸに接続
するＸＢの故障情報により、到着したメッセージの転送
制御情報を付けかえる迂回指示回路６１０と、ホスト計
算機またはＳＶＰ１４０によりあらかじめ記憶されたシ
リアライズネットワークの番号と各ＥＸが接続するＰＥ
の番号を比較する一致判定回路６１１と、一致判定回路
６１１の出力信号により、シリアライズネットワークに
到着したメッセージの転送制御情報を付けかえる経路情
報変更回路６０１〜６０３と、転送されたメッセージ内
の経路情報とホスト計算機およびＳＶＰによりあらかじ
め記憶されたシリアライズネットワークまでの経路情報
と一致判定回路６１１の出力により、そのメッセージの
転送先を決定する経路指示回路６００を有する。本発明
では、ＥＸ内に迂回指示回路、一致判定回路、経路情報
変更回路および経路指示回路を有することが特徴である
各ＸＢは、いずれかの入力ポートから入力された放送メ
ッセージを複数の出力ポートに並列に転送する回路であ
る。ＸＢは、ＸＢに接続するＥＸの故障情報により、転
送されたメッセージの出力ポートを変更する迂回指示回
路９０５と、メッセージの転送情報を付け変える経路情
報変更回路９０６〜９０９と、経路指示回路９００を有
する。経路指示回路９００は、シリアライズネットワー
クの情報を保持するレジスタ群１１００と、そのＸＢが
シリアライズネットワークである場合に、複数のＰＥか
ら互いに並列に送出された複数のブロードキャストメッ
セージを順次送出するためのブロードキャスト逐次回路
１１８０を有する。本発明では、ＸＢ内に迂回指示回
路、経路情報変更回路および経路指示回路を有し、経路
指示回路中にブロードキャスト逐次回路を持つことが特
徴である。

【００１６】図２、図３、図４Ａおよび図４Ｂに本発明
の簡単な動作を示す。図２はネットワークが正常である
場合にＰＥ０１からブロードキャストを行なう様子を示
す。ここでは、シリアライズネットワークをＸＢ１３５
とする。ＰＥ０１から出力されたブロードキャストメッ
セージは各ＥＸの一致判定回路の出力が０であるうち
は、経路指示回路中の選択回路においてシリアライズネ
ットワークへの経路が選択され、出力が１になると、す
なわちそのメッセージがシリアライズネットワークを通
過する場合、経路情報変更回路によりメッセージ中の経
路情報が変更され、ブロードキャストされる。ここで
は、ブロードキャストについてのみ説明したが、１対１
転送は従来の手順で行なえるため省略する。

【００１７】図３および図４Ａ、図４ＢはいずれかのＸ
ＢあるいはＥＸが故障した場合に、ブロードキャストを
行なう場合と１対１転送を行なう場合の経路を示す。こ
こでは、故障ＸＢをＸＢ１３４とし、ブロードキャスト
のシリアライズと１対１転送の迂回をＸＢ１３５で行な
うことを考える。図３（ａ）のようにＸＢ故障時にブロ
ードキャストする場合、シリアライズネットワークを故
障ＸＢと同次元のＸＢ１３５にすることで、故障がない
場合と同様にメッセージを転送できる。図３（ｂ）のよ
うにＸＢ故障時にＰＥ２１からＰＥ２３へ１対１転送を
行なう場合、ＰＥ２１から出力された１対１転送メッセ
ージはＥＸ２１の迂回指示回路により迂回動作を指示さ
れ、各ＥＸの一致指示回路の出力が０のうちは、経路指
示回路中の選択回路においてシリアライズネットワーク
への経路が選択され、出力が１になると、すなわちその
メッセージがシリアライズネットワークを通過すると、
経路情報変更回路によりメッセージ中の経路情報が変更
され、ＰＥ２３へ転送される。

【００１８】図４ＡのようにＥＸ故障時にブロードキャ
ストする場合、シリアライズネットワークを故障ＥＸに
接続しないＸＢ１３５にすることで、故障がない場合と
同様にメッセージを転送できる。図４ＢのようにＥＸ故
障時にＰＥ２１からＰＥ１２へ１対１転送を行なう場
合、ＰＥ２１から出力された１対１転送メッセージはＸ
Ｂ１３４中の迂回指示回路により迂回動作を指示され、
各ＥＸ内の一致指示回路の出力が０のうちは、経路指示
回路中の選択回路においてシリアライズネットワークへ
の経路が選択され、出力が１になると、すなわちそのメ
ッセージがシリアライズネットワークを通過すると、経
路情報変更回路によりメッセージ中の経路情報が変更さ
れ、ＰＥ１２へ転送される。

【００１９】本実施例では、複数のブロードキャストの
シリアライズを、特定のクロスバスイッチが行うことが
特徴である。本実施例のもう一つの特徴は、いずれかの
ＸＢが故障した場合に、ブロードキャストのシリアライ
ズと、故障により迂回が必要な１対１転送の迂回を、故
障ＸＢと同次元にあるクロスバスイッチのうちの一つが
行うことである。また、いずれかのＥＸが故障した場合
には、ブロードキャストのシリアライズと、故障により
迂回が必要な１対１転送の迂回を故障ＥＸに接続しない
ＸＢが行うことも特徴である。

【００２０】図５にメッセージフォーマットを示す。メ
ッセージは、図５（ａ）に示すように送信ＰＥ番号、受
信ＰＥ番号、コントロール（ＣＴＬ）ビット、データを
それぞれ保持するフィールドにより構成される。送信Ｐ
Ｅ番号はメッセージを送り出すＰＥの番号である。受信
ＰＥ番号はメッセージを受け取るＰＥの番号である。Ｃ
ＴＬビットは、メッセージの持つ属性を示し、ブロード
キャストであることを示すビット（ＢＣビット）、シリ
アライズネットワークに転送中であることを示すビット
（ＳＢビット）を内部に持っている。ブロードキャスト
メッセージをシリアライズネットワークに転送中である
場合、図５（ｂ）に示すようにＢＣ＝ＳＢ＝１となる
が、受信ＰＥ番号は有意な値とならない。＊はこのこと
を示す。ブロードキャストメッセージがシリアライズネ
ットワークから放送されている場合、図５（ｃ）に示す
ようにＢＣ＝１、ＳＢ＝０となるが、受信ＰＥ番号は有
意な値とならない。また、１対１転送で、転送経路途中
に故障ＸＢがある場合、シリアライズネットワーク上で
迂回するため、図５（ｅ）に示すようにＢＣ＝０、ＳＢ
＝１となる。通常の１対１メッセージ、あるいは迂回に
より、シリアライズネットワークからメッセージが転送
されている場合、図５（ｄ）に示すように送信ＰＥ番
号、受信ＰＥ番号は有意な値となるが、ＢＣ＝０、ＳＢ
＝０となる。

【００２１】次に図６を用いて、ＥＸにおけるメッセー
ジの制御について説明する。いずれのＥＸもハードウェ
ア構成は同じである。ＥＸは、経路情報変更回路６０１
〜６０３と、入力バッファ６０４〜６０６と、経路指示
回路６００と、出力ポート６０７〜６０９と、迂回指示
回路６１０と、一致判定回路６１１で構成される。一致
判定回路６１１は、レジスタ６１２およびレジスタ６１
３と比較器６１４で構成される。レジスタ６１２および
６１３には、ホスト計算機またはＳＶＰ１４０によりそ
のＥＸが直接接続するＰＥ番号とシリアライズネットワ
ーク番号があらかじめセットされる。比較器６１４は、
レジスタ６１２とレジスタ６１３の値を比較し、比較結
果を出力する。迂回指示回路６１０は、レジスタ６１５
とＯＲゲート６１６で構成され、レジスタ６１５に設定
されたＥＸに接続するＸＢの故障情報により、そのメッ
セージの転送制御情報ＳＢビットを０から１につけかえ
る。故障がない場合はメッセージ中の転送制御情報ＳＢ
ビットを変更しない。経路情報変更回路６０１〜６０３
は、ブロードキャストメッセージあるいは迂回すべきメ
ッセージが転送された場合、一致判定回路６１４の出力
信号６１４Ｓにより、そのメッセージの転送制御情報Ｓ
Ｂビットをつけかえる。入力バッファ６０４〜６０６
は、入力メッセージを一時的に保持する。経路指示回路
６００は、入力バッファ内のブロードキャストメッセー
ジ中のＣＴＬビットとあらかじめ設定されたシリアライ
ズネットワ−クの経路情報６１３Ｓにより、その送信先
を決定する。出力ポート６０７は、セレクタ６１７と出
力バッファ６２０で構成され、Ｘ−ＸＢ、Ｙ−ＸＢおよ
びＰＥへメッセージを送り出す。セレクタ６１７では、
経路指示回路６００からの信号により送信すべきメッセ
ージが選択される。出力バッファ６２０は、選択された
メッセージを一時的に保持する。出力ポート６０８およ
び６０９も同様な構成である。

【００２２】図７に経路指示回路６００の内部の構成を
示す。経路指示回路６００は、選択回路７０１〜７０３
と、アドレスデコーダ７０４〜７０６と、プライオリテ
ィ回路７０７〜７０９と、ＡＮＤゲート群７１０と、Ｏ
Ｒゲート群７１１で構成される。本発明では、従来技術
で実現できるアドレスデコーダ、プライオリティ回路お
よびＯＲゲート群のほかに、選択回路７０１〜７０３と
ＡＮＤゲート群７１０を有するところが新規である。信
号Ｍ（ＰＥ）、Ｍ（Ｘ）、Ｍ（Ｙ）はそれぞれのＥＸが
接続されたＰＥ、Ｘ−ＸＢ、Ｙ−ＹＢから入力されたメ
ッセージの信号（受信ＰＥ番号、シリアライズビットＳ
Ｂ、ブロードキャストビットＢＣ）を示す。また、出力
信号ＰＸ、ＸＸ、ＹＸはそれぞれＰＥ、Ｘ−ＸＢ、Ｙ−
ＸＢから入力されたメッセージをＸ−ＸＢへ送信するこ
とを示す。同時に、出力信号ＰＹ、ＸＹ、ＹＹはそれぞ
れＰＥ、Ｘ−ＸＢ、Ｙ−ＸＢから入力されたメッセージ
をＹ−ＸＢへ送信することを、出力信号ＰＰ、ＸＰ、Ｙ
ＰはそれぞれＰＥ、Ｘ−ＸＢ、Ｙ−ＸＢから入力された
メッセージをＰＥへ送信することを示す。

【００２３】選択回路７０１は、入力バッファ６０４
（図６参照）に入力されたメッセージＭ（ＰＥ）がシリ
アライズネットワークに向かうブロードキャストメッセ
ージ（ＢＣ＝１、ＳＢ＝１）、あるいは接続ＸＢが故障
（ＢＣ＝０、ＳＢ＝１）している場合には、信号６１３
Ｓの出力であるシリアライズネットワーク番号を選択
し、通常の１対１転送（ＳＢ＝０、ＢＣ＝０）である場
合にはメッセージ中の受信ＰＥ番号を選択する。選択回
路７０２および７０３も選択回路７０１と同様である。
アドレスデコータ７０４〜７０６は選択回路７０１〜７
０３により選択されたメッセージの経路情報をデコード
し、それぞれメッセージの送信先を決定し、ＯＲゲート
群７１１に信号を出力する。プライオリティ回路７０７
〜７０９は、入力された３つのメッセージのうちのいず
れか１つを選択し、信号ＳＸ、ＳＹ、ＳＰを出力する。
ここでは、到着順にメッセージを選ぶ。ＯＲゲート群７
１１は、ＯＲゲート７１５〜７２３で構成され、ＡＮＤ
ゲート群７１０の出力信号と、アドレスデコーダ７０４
〜７０６の出力信号の論理和をとる。

【００２４】ＡＮＤゲート群７１０は入力された信号の
論理積をとる。図８にＡＮＤゲート群７１０の内部構成
を示す。ＡＮＤゲート群７１０はＡＮＤゲート８０１〜
８０３と、ＡＮＤゲート８０４〜８１６と、あらかじめ
ホスト計算機またはＳＶＰ１４０によりルーティング順
序を示すビットを設定するレジスタ８００で構成され
る。レジスタ８００には、ルーティング順序がＸ→Ｙの
場合は１を、逆にＹ→Ｘの場合は０をセットする。

【００２５】ＡＮＤゲート８０１〜８０３は、ブロード
キャストメッセージ中の転送制御情報ＢＣビットが１、
ＳＢビットが０であるとき、即ちブロードキャストメッ
セージをシリアライズネットワークから放送する場合に
１となる。ＡＮＤゲート８０４〜８１６は、レジスタ８
００と、信号６１４Ｓにより、どの出力信号を１にする
かを決定する。

【００２６】ＰＥ及びＸＢからメッセージが転送された
場合、本実施例の経路指示回路６００は次のように動作
する。 （１）故障がない場合 ・１対１転送 ＰＥでは、転送制御情報ＢＣおよびＳＢはいずれも０に
なっている。選択回路７０１により、メッセージ中の受
信ＰＥ番号をアドレスデコーダ７０４でデコードして送
信先を決定し、ＯＲゲート群７１１中のＯＲゲート７１
５、７１８、７２１のいずれかに信号１を出力する。他
のアドレスデコーダ７０５、７０６も同様に動作する。 ・ブロードキャスト ＰＥでは、転送制御情報ＢＣおよびＳＢが１になってい
る。各ＥＸ内の経路指示回路において ａ）ＳＢ＝１の場合：選択回路７０１により、レジスタ
６１３（図６参照）に保持されているシリアライズネッ
トワーク番号をアドレスデコーダ７０４でデコードして
送信先を決定し、ＯＲゲート群７１１中のＯＲゲート７
１５、７１８、７２１のいずれかに信号１を出力する。
他のアドレスデコーダ７０５、７０６も同様に動作す
る。 ｂ）ＳＢ＝０の場合：ＰＥからメッセージが転送された
場合、選択回路７０１によりメッセージ中の受信ＰＥ番
号をアドレスデコーダ７０４でデコードして送信先を決
定し、ＯＲゲート群７１１中のＯＲゲート７１５に信号
１を出力する。Ｘ系ＸＢからメッセージが転送された場
合、ＯＲゲート群７１１中のＯＲゲート７１９および７
２２に信号１を出力する。Ｙ系ＸＢからメッセージが転
送された場合、ＯＲゲート群７１１中のＯＲゲート７２
３に信号１を出力する。

【００２７】（２）故障がある場合 ・１対１転送 ＰＥでは、転送制御情報ＢＣビットおよびＳＢビットは
いずれも０になっている。そのメッセージを転送するＥ
ＸにＸＢの故障情報が設定されている場合には、レジス
タ６１５の値により、迂回指示回路６１６（図６参照）
において、ＳＢビットを０から１に付けかえる。 ａ）ＳＢ＝１の場合：選択回路７０１により、レジスタ
６１３（図６）に保持されているシリアライズネットワ
ーク番号をアドレスデコーダ７０４でデコードして送信
先を決定し、ＯＲゲート群７１１中のＯＲゲート７１
５、７１８、７２１のいずれかに信号１を出力する。他
のアドレスデコーダ７０５、７０６も同様に動作する。 ｂ）ＳＢ＝０の場合：選択回路７０１により、メッセー
ジ中の受信ＰＥ番号をアドレスデコーダ７０４でデコー
ドして送信先を決定し、ＯＲゲート群７１１中のＯＲゲ
ート７１５、７１８、７２１のいずれかに信号１を出力
する。他のアドレスデコーダ７０５、７０６も同様に動
作する。 ・ブロードキャスト 故障がない場合と同様に動作する。

【００２８】図９にＸ方向クロスバスイッチＸｉ―ＸＢ
（ｉ＝０、１、２または３）の構成を示す。Ｙ方向クロ
スバスイッチも同様である。クロスバスイッチＸｉ―Ｘ
Ｂは、経路指示回路９００と、迂回指示回路９０５と、
経路情報変更回路９０６〜９０９と、スイッチ９０１〜
９０４で構成される。本実施例では、迂回指示回路と経
路情報変更回路を有することが新規である。経路指示回
路９００は、入力されたメッセージをどのスイッチから
転送するかを決定する。スイッチ９０１〜９０４は、４
つの入力ポートのうちの１つを選択する。図の入出力信
号ＥＸ０〜ＥＸ３は、そのＸＢに接続されたＥＸｉ０〜
ＥＸｉ３からの信号を示す。例えば、Ｘ０―ＸＢの場
合、入出力信号ＥＸ０〜ＥＸ３はＥＸ００〜ＥＸ０３に
置き換えられる。また、Ｙ０―ＸＢの場合、入出力信号
ＥＸ０〜ＥＸ３はＥＸ００〜ＥＸ３０に置き換えられ
る。ＸＢはクロスバスイッチであるため、入力ＥＸ０〜
ＥＸ３のいずれもが、そのままスイッチ９０１〜９０４
に接続され、いずれかの入力ポートから入力されたメッ
セージはそのままスイッチ９０１〜９０４に転送され
る。

【００２９】迂回指示回路９０５は、経路指示回路９０
０からの信号Ｓ０、Ｓ１、Ｓ２、Ｓ３と、ホスト計算機
およびＳＶＰ１４０からの信号により、故障したＥＸに
は信号を出力せずに、となりのＥＸに接続するポートに
信号を出力する。経路情報変更回路９０６は、迂回指示
回路９０５からの信号により、メッセージ中の転送制御
情報ＳＢビットを付けかえる。経路情報変更回路９０７
〜９０９も経路情報変更回路９０６と同様な構成であ
る。図１０に迂回指示回路９０５の構成を示す。迂回指
示回路９０５は、レジスタ１０００と、ＡＮＤゲート１
００１〜１００４、１００９〜１０１２と、ＯＲゲート
１００５〜１００８で構成される。レジスタ１０００に
は、ホスト計算機およびＳＶＰ１４０により、そのＸＢ
に接続しているＥＸの故障情報があらかじめセットされ
る。例えば、そのＸＢの０番目の出力ポートに接続する
ＥＸが故障している場合、レジスタ１０００には１００
０がセットされる。ＡＮＤゲート１００１〜１００４は
レジスタ１０００内の出力したいポートに該当するビッ
トが１になっている場合（故障ＥＸがある）に出力が１
になり、となりのポートに出力する。例えば、Ｓ０から
の出力信号が１である場合に、ポート０に接続するＥＸ
が故障していると、レジスタ１０００の１ビット目に１
がたっているため、ＡＮＤゲート１００１の出力が１に
なり、その結果、ＯＲゲート１００６の出力が１とな
り、Ｓ１の出力が１になる。本実施例では、迂回先をと
なりのポートとしたが、故障箇所を１箇所に制限すれ
ば、いずれのポートを迂回先としてもよい。

【００３０】図１１に経路指示回路９００の詳細を示
す。経路指示回路９００はレジスタ群１１００と選択回
路１１０１〜１１０４と、アドレスデコーダ１１０５〜
１１０８と、ブロードキャスト逐次回路１１８０と、ア
ンドゲート１１２１〜１１２８と、プライオリティ回路
１１０９〜１１１２と、ＯＲゲート群１１１４で構成さ
れる。レジスタ群１１００は、レジスタ１１１５と、レ
ジスタ１１１６〜１１１９で構成される。レジスタ１１
１５には、そのＸＢがシリアライズネットワークである
場合に、ホスト計算機およびＳＶＰの信号１４１によ
り、あらかじめ１がセットされる。また、レジスタ１１
１６〜１１１９には、ホスト計算機およびＳＶＰ１４０
により、あらかじめポート対応にシリアライズネットワ
ーク番号ｉｊがセットされる。例えば、本実施例では、
シリアライズネットワークがＸｉ−ＸＢ（ｉ＝３）であ
る場合、レジスタ１１１６には３０、レジスタ１１１７
には３１、レジスタ１１１８には３２、レジスタ１１１
９には３３がセットされる。選択回路１１０１〜１１０
４は、メッセージ中の転送制御情報ＳＢビットが１（入
力メッセージがシリアライズネットワークに向かうブロ
ードキャスト、あるいは１対１転送の迂回動作）である
場合には、シリアライズネットワークの経路情報を選択
し、通常の１対１転送である場合にはメッセージ中の受
信ＰＥ番号を選択する。アドレスデコータ１１０５〜１
１０８は選択回路１１０１〜１１０４により選択された
メッセージの経路情報をデコードし、メッセージの送信
先を決定する。

【００３１】ブロードキャスト逐次回路１１８０は入力
された４つの信号２１ｉ、２２ｉ、２３ｉ、２４ｉのう
ちいずれか一つを選択し、信号２１ｏ、２２ｏ、２３
ｏ、２４ｏのいずれかに出力する。図２０にブロードキ
ャスト逐次回路１１８０の構成を示す。１１８０は、プ
ライオリティ回路２００１と、セレクタ２００２〜２０
０５で構成される。プライオリティ回路２０００１は、
入力された４つの信号のうちのいずれか１つを選択し、
信号Ｓ０、Ｓ１、Ｓ２、Ｓ３のいずれか一つに出力す
る。ここでは到着順にメッセージを選択する。複数のブ
ロードキャストメッセージが同時に転送された場合に
は、ブロードキャスト逐次回路１１８０により、メッセ
ージを逐次にして転送する。プライオリティ回路１１０
９〜１１１２は、入力された４つのメッセージのうちの
いずれか１つを選択し、信号Ｓ０、Ｓ１、Ｓ２、Ｓ３を
出力する。ここでは、到着順にメッセージを選ぶ。ＡＮ
Ｄゲート１１２１〜１１２４では、ブロードキャストメ
ッセージ中の転送制御情報ＢＣビットが１、ＳＢビット
が０であるとき、即ち、ブロードキャストメッセージを
シリアライズネットワークからブロードキャストする場
合のみ出力が１となる。また、ＡＮＤゲート１１２５〜
１１２８では、レジスタ１１１５の値が１の場合のみ、
出力が１となる。ＯＲゲート群１１１４は、ＯＲゲート
１１２９〜１１４４で構成される。ＯＲゲート群１１１
４は、アドレスデコーダの出力と、ＡＮＤゲート群の出
力によりいずれかのＯＲゲートの出力を１にする。出力
信号Ｄ００、Ｄ１０、Ｄ２０、Ｄ３０はそれぞれＥＸ
０、ＥＸ１、ＥＸ２、ＥＸ３から入力されたメッセージ
をＥＸ０へ送信することを示す。同時に、出力信号Ｄ０
１、Ｄ１１、Ｄ２１、Ｄ３１はそれぞれＥＸ０、ＥＸ
１、ＥＸ２、ＥＸ３から入力されたメッセージをＥＸ１
へ送信することを、出力信号Ｄ０２、Ｄ１２、Ｄ２２、
Ｄ３２はそれぞれＥＸ０、ＥＸ１、ＥＸ２、ＥＸ３から
入力されたメッセージをＥＸ２へ送信することを、出力
信号Ｄ０３、Ｄ１３、Ｄ２３、Ｄ３３はそれぞれＥＸ
０、ＥＸ１、ＥＸ２、ＥＸ３から入力されたメッセージ
をＥＸ３へ送信することを示す。

【００３２】メッセージがＥＸから入力された場合、経
路指示回路９００は次のように動作をする。 （１）故障がない場合 ・１対１転送 ＰＥでは、転送制御情報ＢＣビットおよびＳＢビットは
いずれも０になっている。選択回路１１０１により、メ
ッセージ中の受信ＰＥ番号をアドレスデコーダ１１０４
でデコードして送信先を決定し、ＯＲゲート群１１１４
中のＯＲゲート１１２９、１１３３、１１３７、１１４
１のいずれかに信号１を出力する。他のアドレスデコー
ダ１１０６〜１１０８も同様に動作する。

【００３３】・ブロードキャスト ａ）ＳＢ＝１の場合：選択回路１１０１により、シリア
ライズネットワーク番号を選択し、それをアドレスデコ
ーダ１１０５でデコードして送信先を決定し、ＯＲゲー
ト１１２９、１１３３、１１３７、１１４１のいずれか
に信号１を出力する。このとき、ＡＮＤゲート群の出力
は０である。また、他のアドレスデコーダ１１０６〜１
１０８も同様に動作する。 ｂ）ＳＢ＝０かつレジスタ１１１５の値が１の場合：Ｅ
Ｘ０からメッセージが転送された場合、ＡＮＤゲート１
１２１の出力２１ｉが１になり、ブロードキャスト逐次
回路１１８０に転送される。ブロードキャスト逐次回路
１１８０では、プライオリティ回路２００１において信
号Ｓ０の出力が１になり、セレクタ２００２から２１ｏ
に１を出力する。ＡＮＤゲート１１２５の出力が１であ
るため、ＯＲゲート１１２９、１１３３、１１３７、１
１４１のすべてに信号１を出力する。つまり、ＥＸ０か
ら転送されたブロードキャストメッセージはＥＸ０、Ｅ
Ｘ１、ＥＸ２、ＥＸ３に転送する。ＥＸ０以外からメッ
セージが転送された場合も同様に動作する。 ｃ）ＳＢ＝０かつレジスタ１１１５の値が０の場合：Ｅ
Ｘ０からメッセージが転送された場合、ＡＮＤゲート１
１２１の出力２１ｉが１になり、ブロードキャスト逐次
回路１１８０に転送される。ブロードキャスト逐次回路
１１８０では、プライオリティ回路２００１において信
号Ｓ０の出力が１になり、セレクタ２００２から２１ｏ
に１を出力する。ＡＮＤゲート１１２５の出力は０であ
る。ＯＲゲート１１３３、１１３７、１１４１に信号１
を出力する。ＯＲゲート１１２９には出力されない。

【００３４】（２）故障がある場合 ・１対１転送 ａ）ＳＢ＝１の場合：選択回路１１０１により、レジス
タ１１１６に保持されているシリアライズネットワーク
番号をアドレスデコーダ１１０５でデコードして送信先
を決定し、ＯＲゲート群１１１４中のＯＲゲート１１２
９、１１３３、１１３７、１１４１のいずれかに信号１
を出力する。このとき、ＡＮＤゲート１１２１〜１１２
８の出力は０である。また、他のアドレスデコーダ１１
０６〜１１０８も同様に動作する。

【００３５】ｂ）ＳＢ＝０の場合：選択回路１１０１に
より、メッセージ中の受信ＰＥ番号をアドレスデコーダ
１１０５でデコードして送信先を決定し、ＯＲゲート群
１１１４中のＯＲゲート１１２９、１１３３、１１３
７、１１４１のいずれかに信号１を出力する。このと
き、ＡＮＤゲート１１２１〜１１２８の出力は０であ
る。また、他のアドレスデコーダ１１０６〜１１０８も
同様に動作する。 ・ブロードキャスト 故障のない場合のブロードキャストと同様に動作する。

【００３６】次に、本発明における並列計算機のメッセ
ージ転送について説明する。まず、ネットワークが正常
に動作している場合について説明する。 （１）ブロードキャストメッセージの転送 図１２は、ＰＥ０１からブロードキャストが発生した場
合のメッセージの流れを示す。ここで、シリアライズネ
ットワークをＸＢ１３５（Ｘ３−ＸＢ）とし、ＸＢ１３
５内のレジスタ１１１５に１をセットする。ここでは、
シリアライズネットワークがＸＢ１３５であるため、Ｅ
Ｘ内のシリアライズネットワーク番号を保持するレジス
タ６１３にはＰＥ番号のＸ座標を３にした値をセットす
る。例えば、ＥＸ００内のレジスタには３０を、ＥＸ２
０内のレジスタには３０を、ＥＸ０１内のレジスタには
３１をセットする。シリアライズネットワーク内の各ポ
−ト対応にあるシリアライズネットワーク番号を保持す
るレジスタ１１１６〜１１１９には、あらかじめそのポ
−トに接続するＥＸ番号（３０、３１、３２、３３）を
セットする。また、シリアライズネットワーク以外のＸ
Ｂ内の各ポ−ト対応にあるレジスタ１１１６〜１１１９
にはＸＢに接続するＥＸ内のレジスタ６１３に保持した
値をセットする。また、ネットワークは正常であるた
め、故障情報レジスタ６１５、および故障情報レジスタ
１０００の値は０である。

【００３７】同じジョブ内の処理を分割して割り当てら
れた各プロセッサは、ＥＸおよびＸＢを介して、実行に
必要なメッセージを相互に転送しあい、それぞれ独立に
プログラムを実行する。メッセージは送信元プロセッサ
ＰＥ０１によって、図５に示すフォーマットに従って組
み立てられる。メッセージの組み立ては、プログラムに
よって行なわれても良いし、専用に設けられたハードウ
ェアにより行なわれても構わない。このとき、ブロード
キャストメッセージであるため、メッセージの転送制御
情報ＢＣビットは１、ＳＢも１である。

【００３８】図１２において、送信元プロセッサＰＥ０
１で構成されたブロードキャストメッセージは、まずＥ
Ｘ０１に転送される。ＥＸ０１内部の動作を図６、図７
および図８を用いて説明する。一致判定回路６１１で
は、ホスト計算機およびＳＶＰ１４０によりあらかじめ
セットしてある自ＰＥ番号０１とシリアライズネットワ
ーク番号３１を比較して、比較結果が一致しないため、
信号６１４Ｓの出力が０になっている。まず、メッセー
ジの転送制御情報ＳＢビットが迂回指示回路６１０に転
送される。迂回指示回路６１０では、ネットワークが正
常であるため、ＳＢビットは変更されない。次にメッセ
ージは経路情報変更回路６０３に転送される。経路情報
変更回路６０３では、信号６１４Ｓの出力が０、ＳＢビ
ットが１であるためＡＮＤゲート６２３の出力が１にな
り、ＳＢビットは変更されずに入力バッファ６０６に保
持される。このとき、ＢＣ＝１、ＳＢ＝１のままであ
る。次に、経路指示回路６００内部の動作を説明する。
まず、選択回路７０１では、メッセージの転送制御情報
ＢＣ＝１、ＳＢ＝１であるため、信号６１３Ｓが選択さ
れ、シリアライズネットワーク番号３１がアドレスデコ
ーダ７０４でデコードされ、ＯＲゲート群７１１に１が
出力される。ＡＮＤゲート群７１０では、ＢＣ＝ＳＢ＝
１であるため、図８に示すようにＡＮＤゲート８０１の
出力は０である。よって、アドレスデコーダの出力結果
がＯＲゲート群７１１に反映される。デコーダの出力信
号によりＯＲゲート７１８の出力が１になり、プライオ
リティ回路７０８でＳＹに１が出力される。図６では信
号ＳＹが１になったのをうけて、セレクタ６１８でブロ
ードキャストメッセージが選択され、ＸＢ１３７に転送
される。以上のようにして、ＥＸ０１から出力されたメ
ッセージはＸＢ１３７（Ｙ１−ＸＢ）に転送される（図
１２参照）。

【００３９】次にＸＢ１３７内の動作を図９、図１０お
よび図１１を用いて説明する。経路指示回路９００で
は、ＢＣ＝ＳＢ＝１であるため、選択回路１１０１によ
りシリアライズネットワーク番号が選択され、アドレス
デコーダ１１０５でデコードされ、ＯＲゲート群１１１
４のうちのＯＲゲート１１４１の出力が１になり、プラ
イオリティ回路１１１２から信号線Ｓ３に出力される。
ＡＮＤゲート１１２１〜１１２８の出力は０のままであ
る。Ｓ３から出力された信号は迂回指示回路９０５に転
送される。迂回指示回路９０５では図１０に示すように
レジスタ１０００には故障情報がセットされていないた
め、ＡＮＤゲート１０１２の出力が１になり、迂回は行
なわない。ブロードキャストメッセージは、迂回指示回
路９０５から出力された信号Ｓ３によりスイッチ９０４
でＥＸ３１に転送される。経路情報変更回路９０３では
故障がないため、ＳＢビットの変更はない。

【００４０】次にＥＸ３１内部の動作を図６、図７およ
び図８を用いて説明する。一致判定回路６１１では、自
ＰＥ番号３１とシリアライズネットワーク番号３１が一
致しているため、信号６１４Ｓの出力が１になってい
る。まず、メッセージの転送制御情報が経路情報変更回
路６０２に転送される。経路情報変更回路６０２では、
信号６１４Ｓの出力が１、転送制御情報ＳＢビットが１
であるためＡＮＤゲート６２３の出力が０になり、ＳＢ
ビットは１から０に変更されメッセージが入力バッファ
６０５に保持される。このとき、ＢＣ＝１、ＳＢ＝０で
ある。次に、経路指示回路６００内部の動作を説明す
る。メッセージの転送制御情報ＢＣ＝１、ＳＢ＝０であ
るため、図８に示すＡＮＤゲート群７１０のうちのＡＮ
Ｄゲート８０３およびＡＮＤゲート８０７の出力が１に
なり、ＯＲゲート７１７の出力が１になる。その結果、
プライオリティ回路７０７からＳＸに１が出力される。
図６では信号ＳＸが１になったのをうけて、セレクタ６
１７でブロードキャストメッセージが選択され、ＸＢ１
３５に転送される。

【００４１】図１２に示すように、ＥＸ３１から出力さ
れたメッセージはＸＢ１３５に転送される。ＸＢ１３５
はシリアライズネットワークである。ＸＢ１３５内部の
動作を図９、図１０及び図１１を用いて説明する。図１
１の経路指示回路９００では、ＢＣ＝１、ＳＢ＝０であ
るため、ＡＮＤゲート１１２２の出力が１になる。ま
た、ＸＢ１３５はシリアライズネットワークであるた
め、レジスタ１１１５には１がセットされており、ＡＮ
Ｄゲート１１２６の出力も１になる。その結果、ＯＲゲ
ート１１３０、１１３４、１１３８、１１４２の出力が
１になり、Ｓ０、Ｓ１、Ｓ２、Ｓ３の出力が１となる。
経路指示回路９００からの信号は迂回指示回路９０５に
入力するが、故障情報が設定されていないため、変更な
くスイッチ９０１〜９０４に出力される。経路情報変更
回路では、転送制御情報の変更はない。このようにし
て、ＥＸ３１から転送されたメッセージはすべてのスイ
ッチからＥＸＸ３０、ＥＸ３１、ＥＸ３２、ＥＸ３３に
転送され、ブロードキャストメッセージのシリアライズ
が可能になる。

【００４２】ＥＸ３０、ＥＸ３１、ＥＸ３２、ＥＸ３３
に入力されたメッセージの動作はすべて同じであるた
め、以降ＥＸ３１に入力されたメッセージについて説明
する。ＥＸ３１内部の動作を図６、図７および図８を用
いて説明する。ＥＸ３１に転送されたメッセージは経路
情報変更回路６０１に転送される。経路情報変更回路６
０１では、ＳＢビットが０であるため、ＳＢビットを変
更せずに入力バッファ６０４に保持する。図７に示す経
路指示回路６００では、ＢＣ＝１、ＳＢ＝０であるた
め、ＡＮＤゲート群７１０のうちのＡＮＤゲート８０
２、８０９および８１３の出力が１になり（図８参
照）、ＯＲゲート７１９およびＯＲ７２２の出力が１に
なる。その結果、ＳＹおよびＳＰに１が出力される。図
６のセレクタ６１８および６１９でブロードキャストメ
ッセージが選択され、ＸＢ１３７およびＰＥ３１に転送
される。

【００４３】図１２に示すように、ＥＸ３１から転送さ
れたメッセージはＸＢ１３７に転送される。ＸＢ１３７
内の動作を図９、図１０及び図１１を用いて説明する。
メッセージはまず経路指示回路９００に転送される。経
路指示回路９００（図１１参照）では、ＢＣ＝１、ＳＢ
＝０であるため、ＡＮＤゲート１１２４の出力が１にな
る。ブロードキャスト逐次回路１１８０（図２０）では
２４ｏへの経路が選択される。ＸＢ１３７はシリアライ
ズネットワークではないため、レジスタ１１１５には０
がセットされており、ＡＮＤゲート１１２８からは信号
が出力されない。その結果、ＯＲゲート１１３２、１１
３６、１１４０の出力が１になり、Ｓ０、Ｓ１、Ｓ２の
出力が１となる。Ｓ３には出力しない。ネットワークは
正常であるため、迂回指示回路９０５において信号の変
更はない。ＥＸ３１からのメッセージは図９のスイッチ
９０１〜９０３からＥＸ０１、ＥＸ１１、ＥＸ２１に転
送される。ＥＸ３１には転送しないことで、デッドロッ
クを回避する。

【００４４】ＥＸ０１、ＥＸ１１、ＥＸ２１の動作は同
じであるため、ここではＥＸ０１内部の動作を図６、図
７および図８を用いて説明する。図６において、一致判
定回路６１１の出力６１４Ｓは０になっている。Ｙ−Ｘ
Ｂから入力されたメッセージは経路情報変更回路６０２
に転送される。ＳＢビットは０であるから、ＳＢビット
の変更はなく、入力バッファ６０５に保持される。図７
に示す経路指示回路６００では、ＢＣ＝１、ＳＢ＝０で
あるため、図８中のＡＮＤゲート７１０内のＡＮＤゲー
ト８０３および８１６の出力が１になり、図７のＯＲゲ
ート７２３の出力が１になる。その結果、ＳＰに１が出
力される。図６では、セレクタ６１９においてブロード
キャストメッセージが選択され、ＰＥ０１に転送され
る。

【００４５】以上をまとめると、ＰＥ０１からのブロー
ドキャストは、ＰＥ０１→ＥＸ０１→Ｙ１−ＸＢ→ＥＸ
３１→Ｘ３−ＸＢ→ＥＸ３ｉ（ｉ＝０、１、２および
３）→Ｙｉ−ＸＢ、ＰＥ３ｉ（ｉ＝０、１、２および
３）→ＥＸｉ０（ｉ＝０、１および２）→ＰＥｉｊ（ｉ
＝０、１および２、ｊ＝０、１、２および３）のように
転送される。

【００４６】（２）１対１転送メッセージの場合 図７に示すＥＸ内のアドレスデコーダ７０４〜７０６
と、図１１に示すＸＢ内のアドレスデコーダ１１０５〜
１１０８により、メッセージ中の受信ＰＥ番号のＰＥへ
選択的に転送される。ネットワーク中に故障がなく、か
つブロードキャストメッセージでない場合にはメッセー
ジの転送制御情報ＢＣビット、ＳＢビットとも０であ
り、経路情報変更回路、迂回指示回路および一致判定回
路は動作しない。そのため、公知例と同等の方法でメッ
セージを転送でき、ここでは説明を省略する。

【００４７】次にＸＢが故障している場合について説明
する。

【００４８】（１）ブロードキャストメッセージの転送 図１３は、ＰＥ２１からブロードキャストが発生した場
合のメッセージの流れを示している。ここで、故障ＸＢ
はクロスバスイッチ１３４（Ｘ２−ＸＢ）であり、各Ｅ
Ｘ内の故障ＸＢ情報保持レジスタ６１５に故障ＸＢ情報
をセットする。例えば、故障ＸＢに接続するＥＸ２０〜
ＥＸ２３の故障ＸＢ情報保持レジスタには０１をセット
し、その他のＥＸ内の故障ＸＢ情報保持レジスタには、
００をセットする。また、故障ＸＢはＸ系ＸＢであるた
め、ルーティング順序はＸ→Ｙとし、図８中のレジスタ
８００にはあらかじめ１をセットする。本実施例では、
システム中の部分ネットワークの故障を１箇所に限定し
ているため、ＥＸに故障はなく、各ＸＢ内の故障ＥＸ情
報保持レジスタ１０００の値は０である。シリアライズ
ネットワークは故障ＸＢと同次元方向のＸＢであればい
ずれでもよいが、ここでは、ＸＢ１３５（Ｘ３−ＸＢ）
とし、ＸＢ１３５内部のレジスタ１１１５に１をセット
する。ＥＸ内部のレジスタ６１３、ＸＢ内部のレジスタ
１１１５〜１１１９にセットする値は図１２と同じであ
る。本発明では、ＸＢが故障している場合にはシリアラ
イズネットワークを故障ＸＢと同次元にあるＸＢのうち
の一つに設定することが特徴である。図１３において、
プロセッサの動作は故障のない場合のブロードキャスト
の場合と同様である。メッセージは送信元プロセッサＰ
Ｅ２１によって、図５に示すフォーマットに従って組み
立てられる。このとき、ブロードキャストメッセージで
あるため、転送制御情報ＢＣビットおよびＳＢビットは
１である。図１３において、送信元プロセッサＰＥ２１
で構成されたブロードキャストメッセージは、以下のよ
うに転送される。 ＰＥ２１→ＥＸ２１→Ｙ１−ＸＢ→ＥＸ３１→Ｘ３−Ｘ
Ｂ→ＥＸ３ｉ（ｉ＝０、１、２および３）→Ｙｉ−Ｘ
Ｂ、ＰＥ３ｉ（ｉ＝０、１、２および３）→ＥＸｉ０
（ｉ＝０、１、２）→ＰＥｉｊ（ｉ＝０、１および２、
ｊ＝０、１、２および３） シリアライズネットワークを故障ＸＢと同次元にあるＸ
Ｂのうちの一つに設定することで、ブロードキャストメ
ッセージを転送する場合の各ＥＸ及びＸＢの動作は、故
障のない場合のブロードキャストと同じになる。よっ
て、ここでは説明を省略する。

【００４９】（２）１対１メッセージ転送 図１４は、ＰＥ２１からＰＥ２３に１対１転送が発生し
た場合のメッセージの流れを示している。ここで、故障
ＸＢはＸＢ１３４（Ｘ２−ＸＢ）であり、シリアライズ
ネットワークをＸＢ１３５（Ｘ３−ＸＢ）とする。Ｘ
Ｂ、ＥＸ内の各レジスタにあらかじめセットする値は図
１３と同様である。図１４において、プロセッサの動作
はブロードキャストの場合と同様である。メッセージは
送信元プロセッサＰＥ２１によって、図５に示すフォー
マットに従って組み立てられる。このとき、１対１転送
のメッセージであるため、転送制御情報ＢＣビットおよ
びＳＢビットはそれぞれ０である。図１４において、送
信元プロセッサＰＥ２１で構成された１対１転送のメッ
セージは、まず、ＥＸ２１に転送される。ＥＸ２１内部
の動作を図６、図７および図８を用いて説明する。ＥＸ
２１では、シリアライズネットワーク番号が一致しない
ため、一致判定回路６１１の出力６１４Ｓは０になって
いる。ＥＸ２１に転送されたメッセージは迂回指示回路
６１０に転送される。迂回指示回路６１０では、レジス
タ６１５の値が０１であるため、ＯＲゲート６１６の出
力が１になり、メッセージ中のＳＢビットが０から１に
変更される。この時、ＢＣ＝０、ＳＢ＝１になる。本発
明では、迂回指示回路のレジスタに１が設定されている
場合に１対１転送メッセージ中の転送制御情報ＳＢビッ
トを付け換えることが特徴である。次に、メッセージは
経路情報変更回路６０３に転送される。経路情報変更回
路６０３では、信号６１４Ｓの出力が０であるためＳＢ
ビットの変更はなく、メッセージは入力バッファ６０６
に保持される。この時、ＢＣ＝０、ＳＢ＝１である。経
路指示回路６００（図７参照）では、ＢＣ＝０、ＳＢ＝
１であるため、信号６１３Ｓが選択され、シリアライズ
ネットワーク番号３１がアドレスデコーダ７０４でデコ
ードされ、ＳＹに１が出力される。１対１転送メッセー
ジの場合、ＢＣ＝０であるため、ＡＮＤゲート群７１０
からの出力はない。そして、図６のセレクタ６１９でメ
ッセージが選択され、ＸＢ１３７（Ｙ１−ＸＢ）に転送
される。つまり、ＥＸ２１に接続するＸＢ１３４が故障
しているため、メッセージをＸＢ１３４（Ｘ２−ＸＢ）
には転送せず、シリアライズネットワーク１３５に転送
して迂回動作する。

【００５０】図１４に示すように、ＥＸ２１から出力さ
れたメッセージはＸＢ１３７（Ｙ１−ＸＢ）に転送され
る。ＸＢ１３７内の動作を図９、図１０および図１１を
用いて説明する。図９に示す経路指示回路９００では、
ＢＣ＝０、ＳＢ＝１であるため、シリアライズネットワ
ーク番号３１がアドレスデコーダでデコードされ、Ｓ３
に１が出力される。図１０の迂回指示回路９０５では、
接続するＥＸの故障情報であるレジスタ１０００の値が
０であるため、出力信号の変更はなくスイッチ９０４で
ＥＸ３１に転送される。経路情報変更回路９０９では、
迂回指示回路９０５からの出力信号Ｕ３は０であるた
め、メッセージの転送制御情報ＳＢビットの変更はな
い。

【００５１】次にＥＸ３１内部の動作を図６を用いて説
明する。一致判定回路６１１では比較器６１４が一致を
示しているためその出力６１４Ｓは１になっている。メ
ッセージはまず経路情報変更回路６０２に転送される。
経路情報変更回路６０２では、信号６１４Ｓの出力が
１、ＳＢ＝１であるためＡＮＤゲート６２３の出力が１
になり、ＳＢビットを１から０に置き換えたメッセージ
が選択され、入力バッファ６０５に保持される。このと
き、ＢＣ＝０、ＳＢ＝０となる。本発明では、メッセー
ジがシリアライズネットワークを通過する場合にメッセ
ージ中の転送制御情報ＳＢビットを付け換えることも特
徴である。経路指示回路６００（図７参照）では、ＢＣ
＝０、ＳＢ＝０であるため、選択回路７０３において受
信ＰＥ番号が選択され、アドレスデコーダ７０６でデコ
ードされ、ＳＸに１が出力される。ＢＣ＝０であるた
め、ＡＮＤゲート群７１０からの出力はない。そして、
図６のセレクタ６１８でメッセージが選択され、ＸＢ１
３５（Ｘ３−ＸＢ）に転送される。このようにしてＥＸ
３１から出力されたメッセージはＸＢ１３５に転送され
る。

【００５２】ＸＢ１３５は、シリアライズネットワーク
である。ＸＢ１３５内の動作を図９、図１０および図１
１を用いて説明する。図９においてメッセージはまず経
路指示回路９００に転送される。経路指示回路（図１１
参照）では、ＢＣ＝０、ＳＢ＝０であるため、選択回路
１１０２において受信ＰＥ番号がアドレスデコーダ１１
０６でデコードされ、Ｓ３に１が出力される。出力信号
は迂回指示回路９０５に転送される。迂回指示回路９０
５（図１０参照）では、レジスタ１０００の値が０であ
るため、出力信号の変更はなく、スイッチ９０４により
ＥＸ３３に転送される。経路情報変更回路９０９におい
て、迂回指示回路９０５からの出力信号Ｕ３が０である
ため、メッセージの転送制御情報の変更はない。

【００５３】次に、ＥＸ３３に入力されたメッセージに
ついて図６を用いて説明する。一致判定回路６１１で
は、比較結果が一致するため、信号６１４Ｓの出力は１
になっている。メッセージはまず、経路情報変更回路６
０１に転送される。経路情報変更回路６０１では、ＳＢ
＝０であるため、転送制御情報が変更されずに、入力バ
ッファ６０４に保持される。経路指示回路６００（図７
参照）では、ＢＣ＝０、ＳＢ＝０であるため、受信ＰＥ
番号がアドレスデコーダ７０５によりデコードされ、Ｓ
Ｙに１が出力される。そして、セレクタ６１８でメッセ
ージが選択され、ＸＢ１３９（Ｙ３−ＸＢ）に転送され
る。

【００５４】図１４に示すように、ＥＸ３３から出力さ
れたメッセージはＸＢ１３９に転送される。ＸＢ１３９
内の動作を図９、図１０および図１１を用いて説明す
る。図９に示すようにメッセージはまず経路指示回路９
００に転送される。経路指示回路９００（図１１参照）
では、ＢＣ＝０、ＳＢ＝０であるため、受信ＰＥ番号が
アドレスデコーダ１１０８でデコードされ、Ｓ２に１が
出力される。迂回指示回路９０５（図１０参照）では、
レジスタ１０００の値が０であるため、出力信号の変更
はなく、スイッチ９０３でＥＸ２３に転送される。経路
情報変更回路９０９では、迂回指示回路９０５からの出
力信号Ｕ３が０であるため、メッセージの転送制御情報
の変更はない。

【００５５】次に、ＥＸ２３に入力されたメッセージに
ついて図６を用いて説明する。一致判定回路６１１で
は、比較結果が一致しないため、信号６１４Ｓの出力は
０になっている。メッセージは、まず経路情報変更回路
６０２に転送される。経路情報変更回路６０２ではＳＢ
＝０であるため、転送制御情報は変更されることなく、
入力バッファ６０５に保持される。経路指示回路６００
（図７参照）では、ＢＣ＝０、ＳＢ＝０であるため、受
信ＰＥ番号がアドレスデコーダ７０６でデコードされ、
ＳＰに１が出力される。メッセージは、セレクタ６１９
で選択され、ＰＥ２３に転送される。

【００５６】以上をまとめると、ＰＥ２１からＰＥ２３
への１対１転送は、 ＰＥ２１→ＥＸ２１→Ｙ１−ＸＢ→ＥＸ３１→Ｘ３−Ｘ
Ｂ→ＥＸ３３→Ｙ３−ＸＢ→ＥＸ２３→ＰＥ２３ のように転送される。また、通常の１対１転送メッセー
ジの場合、ＥＸ内のアドレスデコーダ７０４〜７０６
と、ＸＢ内のアドレスデコーダ１１０５〜１１０８にに
より、メッセージ中の経路情報である受信ＰＥ番号のＰ
Ｅへ選択的に転送される。本実施例では、ＸＢが故障し
ている場合に、故障ＸＢに接続するＰＥ間の１対１通信
をシリアライズネットワークを経由して実現できる。さ
らに、シリアライズネットワークでのみ迂回を許可する
ことにより、ブロードキャストが同時に発生してもデッ
ドロックが発生しない。

【００５７】次に、ＥＸが故障している場合について説
明する。 （１）ブロードキャストメッセージの転送 図１５は、ＰＥ２１からブロードキャストが発生した場
合のメッセージの流れを示している。ここで、故障ＥＸ
をＥＸ０１のみに限定し、各ＸＢ内の故障情報保持レジ
スタ１０００に故障ＥＸ情報をセットする。例えば、故
障ＥＸに接続するＸＢ１３２の故障情報保持レジスタに
は０１００を、ＸＢ１３７の故障ＥＸ情報保持レジスタ
には、１０００をセットし、他のＸＢ内の故障情報保持
レジスタの値は、すべて０にセットする。本実施例で
は、システム中の部分ネットワークの故障を１箇所に限
定するため、ＸＢには故障がなく、各ＥＸ内の故障情報
保持レジスタ８００には、００をセットする。シリアラ
イズネットワークは故障ＥＸに接続しないＸＢであれば
いずれでもよいが、ここでは、ＸＢ１３５（Ｘ３−Ｘ
Ｂ）とし、シリアライズネットワークを示すレジスタ１
１１５に１をセットする。ＥＸ、ＸＢ内のシリアライズ
ネットワーク番号保持レジスタにセットする値は図１２
の場合と同様である。また、ルーティングの順序はＥＸ
故障であるため変更する必要はなく、ここではＸ→Ｙと
し、図５のレジスタ８００にあらかじめ１をセットす
る。ブロードキャストの場合、メッセージは、ＸＢが故
障している場合と同様に転送される。但し、図１５に示
す例では、故障ＥＸに接続しているＰＥへはメッセージ
を転送しない構成になっている。以上から、ＥＸが故障
している場合には、故障ＥＸの接続しないＸＢをシリア
ライズネットワークとするため、故障を気にすることな
くブロードキャストを実現できる。

【００５８】（２）１対１メッセージ転送 図１６は、ＰＥ２１からＰＥ１２に１対１転送が発生し
た場合のメッセージの流れを示している。ここで、故障
部分ネットワークは、ＥＸ２２であり、シリアライズネ
ットワークは、ＥＸ２２に接続するＸＢ１３４、ＸＢ１
３８以外のＸＢであればいずれでもよく、ここでは、Ｘ
Ｂ１３５（Ｘ３−ＸＢ）とする。故障情報を設定するレ
ジスタを除いて、ＸＢおよびＥＸ内の各レジスタにあら
かじめセットする値は図１２と同様である。図１６にお
いて、プロセッサの動作はブロードキャストの場合と同
様である。メッセージは送信元プロセッサＰＥ２１によ
って、図５に示すフォーマットに従って組み立てられ
る。このとき、１対１転送のメッセージであるため、Ｂ
Ｃ＝０、ＳＢ＝０である。図１６において、送信元プロ
セッサＰＥ２１で構成された１対１転送のメッセージ
は、ＥＸ２１に転送される。ＥＸ２１内部の動作を図６
を用いて説明する。一致判定回路６１１では、自ＰＥ番
号２１とシリアライズネットワーク番号３１を比較し、
比較結果が一致しないため、信号６１４Ｓの出力は０に
なっている。まず、メッセージは迂回指示回路６１０に
転送される。迂回指示回路６１０では、レジスタ６１５
の値が００であるため、メッセージの転送制御情報の変
更はない。この時、ＢＣ＝０、ＳＢ＝０である。次に、
メッセージは経路情報変更回路６０３に転送される。経
路情報変更回路６０３では、信号６１４Ｓの出力が０で
あるためＳＢビットの変更はなく、メッセージは入力バ
ッファ６０６に保持される。経路指示回路６００（図７
参照）では、ＢＣ＝０、ＳＢ＝０であるため、受信ＰＥ
番号が選択され、受信ＰＥ番号１２がアドレスデコーダ
７０４でデコードされ、ＯＲゲート群７１１のうちのＯ
Ｒゲート７１５に入力される。ＢＣ＝０であるため、Ａ
ＮＤゲート群７１０（図８参照）からは出力されない。
そして、ＳＸに１が出力される。出力された信号によ
り、セレクタ６１７でメッセージが選択されＸ−ＸＢに
転送される。

【００５９】図１６に示すように、ＥＸ２１から出力さ
れたメッセージはＸＢ１３４（Ｘ２−ＸＢ）に転送され
る。ＸＢ１３４内の動作を図９、図１０および図１１を
用いて説明する。図９に示すようにメッセージはまず経
路指示回路９００に転送される。経路指示回路９００
（図１１参照）では、ＢＣ＝０、ＳＢ＝０であるため、
受信ＰＥ番号１２がアドレスデコーダ１１０６でデコー
ドされ、ＯＲゲート群１１１４に転送され、Ｓ２に１が
出力される。ＸＢ１３４はシリアライズネットワークで
はないため、レジスタ１１１５には０が設定されてい
る。ＢＣ＝０およびレジスタ１１１５の値からＡＮＤゲ
ート群１１１３からの出力はない。迂回指示回路９０５
（図１０参照）では、レジスタ１０００の値が００１０
であるため、ＡＮＤゲート１００３の出力が１になり、
Ｓ２の出力信号がＳ３に変更される。また、信号Ｕ３も
１になる。スイッチ９０４において出力信号Ｓ３により
メッセージが選択される。経路指示変更回路９０９で
は、Ｕ３が１であるため、メッセージの転送制御情報Ｓ
Ｂビットは０から１に変更される。このとき、ＢＣ＝
０、ＳＢ＝１になる。本発明では、ＥＸ故障時に、故障
ＥＸに接続するＸＢの中の故障情報により、迂回指示回
路では故障ＥＸの隣のＥＸにメッセージを転送し、かつ
経路情報変更回路ではメッセージの転送制御情報を付け
かえることが特徴である。本実施例では、ＥＸ故障時は
迂回指示回路において故障ＥＸの隣のＥＸにメッセージ
を転送するが、隣接するＥＸでなくともよい。

【００６０】次にＥＸ２３内部の動作を図６、図７およ
び図８を用いて説明する。一致判定回路６１１では、比
較結果が一致しないため、信号６１４Ｓの出力は０にな
っている。メッセージは、まず経路情報変更回路６０１
に転送される。経路情報変更回路６０１では、信号６１
４Ｓの出力が０であるため転送制御情報の変更はなく、
入力バッファ６０４に保持される。経路指示回路６００
（図７参照）では、ＳＢ＝１であるため、シリアライズ
ネットワーク番号３３がアドレスデコーダ７０５でデコ
ードされ、ＯＲゲート群７１１に入力される。ＯＲゲー
ト群７１１では、ＯＲゲート７１９の出力が１になり、
ＳＹに１が出力される。そして、セレクタ６１８でメッ
セージが選択され、ＸＢ１３９（Ｙ３−ＸＢ）に転送さ
れる。

【００６１】図１６に示すように、ＥＸ２３から出力さ
れたメッセージはＸＢ１３９（Ｙ３−ＸＢ）に転送され
る。ＸＢ１３９内の動作を図９、図１０および図１１を
用いて説明する。図９に示すようにメッセージはまず経
路指示回路９００に転送される。経路指示回路９００
（図１１参照）では、ＳＢ＝１であるためシリアライズ
ネットワーク番号３３がアドレスデコーダ１１０７でデ
コードされ、Ｓ３に１が出力される。迂回指示回路９０
５（図１０参照）では、レジスタ１０００の値が０００
０であるため、出力信号の変更はなく、スイッチ９０４
では信号Ｓ３によりＥＸ３３へのメッセージが選択され
る。経路指示変更回路９０９におけるメッセージの転送
制御情報ＳＢビットの変更はない。このとき、ＢＣ＝
０、ＳＢ＝１である。

【００６２】次にＥＸ３３内部の動作を図６、図７およ
び図８を用いて説明する。一致判定回路６１１では、比
較結果が一致するため、信号６１４Ｓの出力は１になっ
ている。メッセージはまず経路情報変更回路６０２に転
送される。経路情報変更回路６０２では、信号６１４Ｓ
の出力が１、ＳＢ＝１であるためＡＮＤゲート６２３の
出力が０になり、ＳＢビットを０に置き換えたメッセー
ジが選択され、入力バッファ６０５に保持される。この
とき、ＢＣ＝０、ＳＢ＝０となる。経路指示回路６００
（図７参照）では、ＢＣ＝０、ＳＢ＝０であるため、受
信ＰＥ番号１２がアドレスデコーダ７０６でデコードさ
れ、ＳＸに１が出力される。セレク６１７でメッセージ
が選択され、ＸＢ１３５（Ｘ３−ＸＢ）に転送される。
シリアライズネットワークに転送された後は、ＸＢ故障
時の１対１転送メッセージの動作と同じであるため、こ
こでは説明を省略する。

【００６３】以上をまとめると、ＰＥ２１からＰＥ１２
への１対１転送は、 ＰＥ２１→ＥＸ２１→Ｘ２−ＸＢ→ＥＸ２３→Ｙ３−Ｘ
Ｂ→ＥＸ３３→Ｘ３−ＸＢ→ＥＸ３２→Ｙ２−ＸＢ→Ｅ
Ｘ１２→ＰＥ１２ のように転送される。また、通常の１対１転送メッセー
ジの場合、ＥＸ内のアドレスデコーダ７０４〜７０６
と、ＸＢ内のアドレスデコーダ１１０５〜１１０８によ
りメッセージ中の経路情報である受信ＰＥ番号のＰＥへ
選択的に転送される。

【００６４】以上から、ネットワークが正常である場合
にも、故障している場合にも、ブロードキャストメッセ
ージの転送を行なう場合には特定のクロスバスイッチを
経由させることで、デッドロックを回避し、転送オーバ
ーヘッドを従来に比べて削減することができる。さら
に、ＸＢが故障している場合には、故障ＸＢと同次元に
あるＸＢの一つをシリアライズネットワークとし、故障
による１対１転送メッセージの迂回をシリアライズネッ
トワークにおいてのみ許可するため、逆順転送は１箇所
に限定され、複数データ転送発生時のデッドロックを回
避できる。さらに、ＥＸが故障している場合も、故障Ｅ
Ｘの接続していないＸＢをシリアライズネットワークと
し、故障による１対１転送メッセージの迂回をシリアラ
イズネットワークにおいてのみ許可するため、逆順転送
は１箇所に限定され、複数データ転送発生時のデッドロ
ックを回避できる。ここでは、２次元構成の例を示した
が、ｎ次元構成でも良い。この場合、転送順序を例えば
Ｘ次元→Ｙ次元→Ｚ次元→…→Ｎ次元のように固定し、
最初にメッセージを転送する次元のクロスバスイッチの
内の１つをシリアライズネットワークにすればよい。

【００６５】＜第２の実施例＞第２の実施例は、ブロー
ドキャストと部分ブロードキャストが混在する場合に、
これらのメッセージをクロスバスイッチでシリアライズ
し、デッドロックを回避することに特徴がある。ここで
は、従来例として、特開平５−２８１２２に開示されて
いるブロードキャスト方法を考える。以下では、第１の
実施例と従来例との相違点にしぼって説明する。

【００６６】図１７に本実施例におけるメッセージのフ
ォーマットを示す。本実施例の実施例１と異なるところ
は、送信ＰＥ番号、ＣＴＬ（コントロール）ビットの他
に、範囲情報として、ＭＡＸ座標、ＭＩＮ座標をもつこ
とである。ＭＡＸ座標は、メッセージを転送するプロセ
ッサ群の座標の最大Ｘ座標ＸＭＡＸ、最大Ｙ座標ＹＭＡ
Ｘからなる。ＭＩＮ座標も同様にＸＭＩＮ、ＹＭＩＮか
らなる。また、ＣＴＬ（コントロ−ル）ビットにＢＣビ
ットとＳＢビットの他に部分ブロードキャストであるこ
とを示すビット（ＰＢビット）を持つところも実施例１
とは異なる。部分ブロードキャストメッセージをシリア
ライズネットワークに転送中である場合、図１７（ｃ）
に示すようにＰＢ＝ＳＢ＝１、ＢＣ＝０となるが、受信
ＰＥ番号は有意な値とはならない。＊はそのことを示
す。部分ブロードキャストメッセージがシリアライズネ
ットワークから部分放送されている場合、図１７（ｅ）
に示すようにＰＢ＝１、ＢＣ＝ＳＢ＝０となるが、受信
ＰＥ番号は有意な値とならない。

【００６７】図１８に、本実施例におけるＥＸ内部の経
路指示回路の構成を示す。実施例１と異なるところは、
経路指示回路内に、ＯＲゲート１８０１〜１８０３が付
加されたことである。ＯＲゲート１８０１〜１８０３
は、メッセージ中のＰＢビットあるいはＢＣビットが１
の場合に１を出力する。

【００６８】図１９に、本実施例におけるＸＢ内部の経
路指示回路の構成を示す。第１の実施例と異なるところ
は、部分放送経路指示回路１９０１〜１９０４が付加さ
れたことである。部分放送経路指示回路１９０１〜１９
０４は、メッセージ中のＰＢビット、ＭＡＸ座標、ＭＩ
Ｎ座標に従い、ｘｉ-０、ｘｉ-１、ｘｉ-２、ｘｉ-３
（ｘ＝２１、２２、２３、２４）に１を出力する。部分
放送経路指示回路１９０１の構成を図２６に示す。部分
放送経路指示回路１９０１は、レジスタ２６５０〜２６
５３と、比較器２６０５〜２６１２と、ＡＮＤゲート２
６０１〜２６０４で構成される。ＥＸ０から入力された
メッセージは、ホスト計算機またはＳＶＰによりセット
されるポート番号がＸＭＡＸ座標とＸＭＩＮ座標の範囲
内にある場合に、比較器２６０５〜２６１２の出力が１
になる。ＡＮＤゲート２６０１はメッセージ中のＰＢビ
ットが１であり、かつ比較器のペアの出力（例えば、２
６０５と２６０６）が１である場合のみ、出力が１にな
り、結果として２１ｉ-０〜２１ｉ-３の出力が１にな
る。他の部分放送指示回路の動作も同様である。例え
ば、ＰＢが１、ＸＭＡＸが２、ＸＭＩＮが０の場合、比
較結果より、ＡＮＤゲート２６０１〜２６０３の出力が
１になり、２１ｉ-０〜２１ｉ-２の出力が１になる。ま
た、ブロードキャスト逐次回路１１８０は、信号２１ｉ
〜２４ｉおよび２１ｏ〜２４ｏのそれぞれが１ビット幅
から４ビット幅に変更されている。プライオリティ回路
２００１では４つの信号のうちいくつかを選択する。選
択方法は、まず到着順に行ない、かつブロードキャスト
メッセージの場合はｓ０〜ｓ３のうちのいずれか１つの
みを選択し、部分ブロードキャストメッセージの場合、
出力ポートが重複しないかぎりいくつでも選択可能であ
る。

【００６９】次に本実施例におけるメッセージ転送につ
いて図２１、図２２、図２３および図２４を用いて説明
する。図２１は、部分ブロードキャストを行うプロセッ
サ群の例を示す図である。各プロセッサ群は、その中の
ＰＥ間でのみ、メッセージが放送されるＰＥの集合であ
る。丸印はＰＥを例示し、その中の番号はＰＥ番号を示
している。各プロセッサ群は、図２１（ａ）に示すよう
に、２次元の矩形の領域Ａ、Ｂ、Ｃに含まれるＰＥから
なってもよい。また、図２１（ｂ）、または図２１
（ｃ）に示すように一列のＰＥまたは一行のＰＥからな
っていてもよい。

【００７０】（１）ネットワークが正常である場合 図２２は、ＰＥ０１から図２１に示す領域Ａに対して部
分ブロードキャストが発生した場合のメッセージの流れ
を示している。シリアライズネットワークはいずれのク
ロスバスイッチでも構わないが、ここではＸＢ１３５と
する。ホスト計算機およびＳＶＰによりあらかじめＥＸ
およびＸＢ内のシリアライズネットワーク番号を保持す
るレジスタは実施例１の図１２と同じ値をセットする。
プロセッサの動作は実施例１と同じであり、メッセージ
のフォーマットは図１７（ｃ）になる。すなわち、部分
ブロードキャストの場合、ＢＣ＝０、ＰＢ＝１、ＳＢ＝
１である。図２２において、送信元プロセッサＰＥ０１
からの部分ブロードキャストメッセージは、ＥＸ０１に
転送され、ＥＸ０１→Ｙ０−ＸＢ→ＥＸ３１のように、
シリアライズネットワークＸＢ１３５に向かって実施例
１と同じように転送される。

【００７１】次にＥＸ３１内部の動作を図６および図１
８を用いて説明する。一致判定回路６１１では、比較結
果が一致するため、信号６１４Ｓの出力は１になってい
る。メッセージは経路情報変更回路６０２に転送され
る。経路情報変更回路６０２では、信号６１４Ｓの出力
が１、転送制御情報ＳＢビットが１であるため、ＳＢビ
ットを１から０に置き換えたメッセージが入力バッファ
に保持される。このとき、ＢＣ＝０、ＰＢ＝１、ＳＢ＝
０となる。図１８に示す経路指示回路６００では、ＢＣ
＝０、ＰＢ＝１、ＳＢ＝０であるため、ＯＲゲート１８
０３の出力が１となり、ＡＮＤゲート群７１０に出力さ
れる。ＡＮＤゲート群７１０では、ＡＮＤゲートにより
信号８０７Ｓに１が出力され、ＯＲゲート群７１１の一
つから１が出力され、その結果ＳＸに１が出力される。
図６のセレクタ６１７により部分ブロードキャストメッ
セージが選択され、ＸＢ１３５に転送される。

【００７２】図２２に示すように、ＥＸ３１から出力さ
れたメッセージはＸＢ１３５（Ｘ３−ＸＢ）に転送され
る。ＸＢ１３５内の動作を図９および図１９を用いて説
明する。図１９の経路指示回路９００では、ＰＢ＝１で
あるため、部分放送経路指示回路１９０２から２１ｉ-
０、２１ｉ-１に１が出力される。ブロードキャスト逐
次回路１１８０では、セレクタ２００２からの出力が選
択され２１ｏ-０、２１ｏ-１に１が出力される。さら
に、レジスタ１１１５の値は１であり、その結果、ＡＮ
Ｄゲート１１２５の出力が１になり、Ｓ０、Ｓ１の出力
が１になる。Ｓ２およびＳ３には出力しない。ＥＸ３１
からのメッセージは、図９のスイッチ９０１および９０
２からＥＸ３０およびＥＸ３１に転送される。ＥＸ３２
およびＥＸ３３には転送されない。ＥＸ３０およびＥＸ
３１に転送されたメッセージの動作は実施例１と同じで
あり、Ｙ−ＸＢおよびＰＥに同時に転送される。

【００７３】図２２に示すように、ＥＸ３０およびＥＸ
３１から出力されたメッセージはＸＢ１３６（Ｙ０−Ｘ
Ｂ）とＸＢ１３７（Ｙ１−ＸＢ）に転送される。ＸＢ１
３６とＸＢ１３７の動作は同じであるため、ここではＸ
Ｂ１３７について説明する。経路指示回路９００では、
ＰＢ＝１であるため、部分放送経路指示回路１９０４か
らｓ０およびｓ１に１が出力される。そして、ＥＸ３１
からのメッセージは、図９のスイッチ９０１および９０
２からＥＸ０１およびＥＸ０２に転送される。ＥＸ２１
およびＥＸ３１には転送されない。

【００７４】以上をまとめると、ＰＥ０１からの部分ブ
ロードキャストは、 ＰＥ０１⇒Ｙ０−ＸＢ⇒ＥＸ３１⇒Ｘ３−ＸＢ⇒ＥＸ３
ｉ（ｉ＝０および１）⇒Ｙｉ−ＸＢ（ｉ＝０および
１）、ＰＥｉ０（ｉ＝０および１）⇒ＥＸｉｊ（ｉ＝０
および１、ｊ＝０および１）⇒ＰＥｉｊ（ｉ＝０および
１、ｊ＝０および１）のように転送される。また、１対
１転送メッセージの場合、ＥＸ内のアドレスデコーダ７
０４〜７０６と、ＸＢ内のアドレスデコーダ１１０５〜
１１０８によりメッセージ中の受信ＰＥ番号のＰＥへと
選択的に転送される。

【００７５】（２）ＸＢの一つが故障している場合 図２３は、ＰＥ１１から領域Ａに対して部分ブロードキ
ャストが発生した場合のメッセージの流れを示してい
る。ここでは、システム中の１つのＸＢが故障した場合
を考え、ＸＢ１３３（Ｘ１−ＸＢ）が故障しているとす
る。シリアライズネットワークはいずれのＸＢでもかま
わないが、ここでは、ＸＢ１３５（Ｘ３−ＸＢ）とす
る。ＥＸおよびＸＢ内のシリアライズネットワーク番号
を保持するのレジスタには実施例１と同じ値をセットす
る。プロセッサの動作は実施例１と同じであり、メッセ
ージのフォーマットは図１７（ｃ）になる。すなわち、
部分ブロードキャストの場合、ＢＣ＝０、ＰＢ＝１、Ｓ
Ｂ＝１である。故障ＸＢとは異なるＸＢをシリアライズ
ネットワークとし、メッセージを転送するための構成お
よび動作は実施例１と同じであり、部分ブロードキャス
トを実現する場合に新たに必要な構成および動作は実施
例２（１）に示したものと同じであるため、部分ブロー
ドキャストは実施例１と実施例２の（１）との組合せに
より実現でき、ここでは詳細の説明の省略する。以上を
まとめると、ＰＥ１１から領域Ａ（図２１（ａ））への
部分ブロードキャストは、 ＰＥ１１→Ｙ０−ＸＢ→ＥＸ３１→Ｘ３−ＸＢ→ＥＸ３
ｉ（ｉ＝０および１）→Ｙｉ−ＸＢ（ｉ＝０および
１）、ＰＥｉ０（ｉ＝０および１）→ＥＸｉｊ（ｉ＝０
および１、ｊ＝０および１）→ＰＥｉｊ（ｉ＝０および
１、ｊ＝０および１）のように転送される。ここでは、
ＸＢが故障している場合の部分ブロードキャストメッセ
ージについてのみ説明したが、故障ＸＢに接続するＥＸ
間のメッセージ転送も、実施例１とまったく同じように
実現できる。また、ブロードキャストメッセージの場
合、実施例１とまったく同じように転送される。また、
通常の１対１転送メッセージの場合、ＥＸ内のアドレス
デコーダ７０４〜７０６と、ＸＢ内のアドレスデコーダ
１１０５〜１１０８によりメッセージ中の受信ＰＥ番号
のＰＥへ選択的に転送される。

【００７６】（３）ＥＸの一つが故障してる場合 図２４は、ＥＸ０１が故障している場合に、ＰＥ１１か
ら領域Ａに対して部分ブロードキャストを行なう時のメ
ッセージの流れを示している。シリアライズネットワー
クは故障ＥＸの接続するクロスバスイッチ以外であれば
いずれのクロスバスイッチでもかまわないが、ここで
は、クロスバスイッチ１３５（Ｘ３−ＸＢ）とする。Ｅ
ＸおよびＸＢ内のシリアライズネットワーク番号と故障
情報を保持するレジスタには実施例１と同じ値をセット
する。ＥＸ故障の場合、プロセッサ、各ＥＸおよび各Ｘ
Ｂの動作は実施例１と同じであり、メッセージのフォー
マットは図１７（ｃ）になる。すなわち、部分ブロード
キャストの場合、ＢＣ＝０、ＰＢ＝１、ＳＢ＝１であ
る。また、部分ブロードキャストを実現するために必要
な機構と動作は実施例２の（１）と同じである。ＥＸ故
障の場合も実施例１と実施例２の（１）との組合せで実
現できるため、ここでは説明を省略する。以上をまとめ
ると、ＰＥ１１からの部分ブロードキャストは、 ＰＥ１１→Ｙ０−ＸＢ→ＥＸ３１→Ｘ３−ＸＢ→ＥＸ３
ｉ（ｉ＝０および１）→Ｙｉ−ＸＢ（ｉ＝０および
１）、ＰＥｉ０（ｉ＝０および１）→ＥＸ０１、ＥＸ１
０、ＥＸ００→ＰＥ０１、ＰＥ１０、ＰＥ００ のように転送される。ここでは、部分ブロードキャスト
メッセージの転送について説明したが、ブロードキャス
トメッセージの場合も、実施例１とまったく同じように
転送される。また、故障ＥＸを経由するメッセージ転送
は、実施例１とまったく同じようにクロスバスイッチを
迂回することにより実現できる。また、通常の１対１転
送メッセージの場合、ＥＸ内のアドレスデコーダ７０４
〜７０６と、ＸＢ内のアドレスデコーダ１１０５〜１１
０８によりメッセージ中の受信ＰＥ番号のＰＥへ選択的
に転送される。ここでは、２次元構成の例を示したが、
ｎ次元構成でも良い。以上のように本実施例では、故障
のない場合はもちろん、部分ネットワークの１つ、つま
りＸＢおよびＥＸが故障した場合に、ブロードキャス
ト、部分ブロードキャスト、迂回すべき１対１メッセー
ジ転送および通常の１対１転送おこなっても、デッドロ
ックを発生させない。また、ネットワークをシリアライ
ズネットワークに垂直（列方向）に分割した場合には、
各列ごとに独立に部分ブロードキャストメッセージを転
送できる。また、メッセージ中にプロセッサ群の範囲情
報を設定するため動的にプロセッサ群の範囲を変更でき
る。

【００７７】＜第３の実施例＞第３の実施例は、ブロー
ドキャストメッセージを中継スイッチ（ＥＸ）でシリア
ライズし、デッドロックを回避することに特徴がある。
以下では、第１の実施例との相違に絞って説明する。

【００７８】本実施例において、第１の実施例と異なる
ところは、図７に示す経路指示回路内部にある、Ｍ（Ｐ
Ｅ）、Ｍ（Ｘ）、Ｍ（Ｙ）に転送されたメッセージをど
の経路に転送するかを決定するＡＮＤゲート群７１０で
ある。また、本実施例では信号線８１４Ｓおよび８１６
Ｓがない。図２５にＡＮＤゲート群７１０の詳細を示
す。図８と比べてもわかるように、ＥＸでブロードキャ
ストメッセージをシリアライズする方がＡＮＤゲート群
を簡単に構成できる。ブロードキャストメッセージがシ
リアライズネットワークに到着し、転送制御情報ＳＢビ
ットを０に置き換えるところまでは、実施例１と同様で
ある。シリアライズネットワークからブロードキャスト
メッセージが放送される場合、Ｘ−ＸＢ、Ｙ−ＸＢ、Ｐ
Ｅに同時に転送されるところが、実施例１とは異なる。
本実施例におけるＸＢは、実施例１と同じ動作をする
が、実施例１の図１１において、各ポート対応にセット
しなければならなかったシリアライズネットワーク番号
保持レジスタをＸＢに１つにしてよい。また、シリアラ
イズネットワークがＸＢでないため、レジスタ１１１５
はなくてもよい。このように、レジスタ群１１１０の数
を削減し、簡単にすることができる。各プロセッサ、Ｅ
Ｘ、ＸＢの動作は第１の実施例と同じであるため、ここ
では説明を省略する。ここでは、２次元構成の例を示し
たが、ｎ次元構成でも良い。以上のように本実施例で
は、部分ネットワークの一つであるＥＸを用いて、ブロ
ードキャストを行なう場合にデッドロックを発生させな
い。また、ＸＢを用いてブロードキャストの逐次化を行
なう場合に比べ、回路を簡単にできる。

【００７９】＜第４の実施例＞第４の実施例は、ブロー
ドキャストメッセージおよび部分ブロードキャストメッ
セージを中継スイッチ（ＥＸ）でシリアライズし、デッ
ドロックを回避することに特徴がある。以下では、第２
の実施例との相違に絞って説明する。本実施例におい
て、第２の実施例と異なるところは、図１８に示す経路
指示回路内部にある、Ｍ（ＰＥ）、Ｍ（Ｘ）、Ｍ（Ｙ）
に転送されたメッセージをどの経路に転送するかを決定
するＡＮＤゲート群７１０である。また、本実施例では
信号線８１４Ｓおよび８１６Ｓがない。ＡＮＤゲート群
７１０の構成と動作は第３の実施例と同じであるため、
ここでは説明を省略する。図８と比べてもわかるよう
に、ＥＸでブロードキャストメッセージをシリアライズ
する方がＡＮＤゲート群を簡単に構成できる。ブロード
キャストメッセージおよび部分ブロードキャストメッセ
ージがシリアライズネットワークに到着し、転送制御情
報ＳＢビットを０に置き換えるところまでは、実施例２
と同様である。シリアライズネットワークからブロード
キャストメッセージが放送される場合、Ｘ−ＸＢ、Ｙ−
ＸＢ、ＰＥに同時に転送されるところが、実施例２とは
異なる。本実施例におけるＸＢは、実施例２と同じ動作
をするが、実施例２の図１９において、各ポート対応に
セットしなければならなかったシリアライズネットワー
ク番号保持レジスタをＸＢに１つにしてよい。また、シ
リアライズネットワークがＸＢでないため、レジスタ１
１１５はなくてもよい。このように、レジスタ群１１１
０の数を削減し、簡単にすることができる。各プロセッ
サ、ＥＸ、ＸＢの動作は実施例と同じであるため、ここ
では説明を省略する。ここでは、２次元構成の例を示し
たが、ｎ次元構成でも良い。以上のように本実施例で
は、ブロードキャスト、部分ブロードキャストをおこな
っても、デッドロックを発生させない。また、実施例２
に比べ、回路を簡単にできる。

【００８０】＜その他の実施例＞その他の実施例とし
て、メッセージ中にシリアライズネットワークの番号を
ソフトウェアもしくはハードウェアで書き込み、シリア
ライズネットワークに到着した後、その番号を書き変え
ることによりブロードキャストの逐次化および故障時の
１対１転送の迂回を実現可能である。また、実施例２で
は部分ブロードキャストを行なう範囲をメッセージ中に
記述したが、クロスバスイッチ内のレジスタ群に設定す
ることにより、メッセージのフォーマットを図５のよう
に簡単にすることができる。また、本実施例ではハイパ
クロスバネットワークを例にとって説明したが、多数の
部分ネットワークで構成される、多段結合ネットワーク
やハイパキューブネットワークおよび格子結合ネットワ
ークにおいても実施例３と同様に実現可能である。これ
らのネットワークは、複数の中継スイッチ（ＥＸ）間を
結合して構成される。よって、実施例の３および４のよ
うな、ハイパクロスバネットワークの中継スイッチにお
いてブロードキャストメッセージを逐次化を行なう場合
と同様に実現でき、ここでは中継スイッチ内部の構成お
よび動作の説明は省略する。

【００８１】

【発明の効果】本発明によれば、複数の部分ネットワー
クで構成されるシステムにおいて、特定の部分ネットワ
ーク（シリアライスライズネットワーク）によって、複
数のプロセッサからのブロードキャストおよび部分ブロ
ードキャストを逐次化することによってデッドロックを
回避し、特定プロセッサへのメッセージの集中を緩和す
ることができる。さらに、本発明によれば、故障部分ネ
ットワークを有するシステムにおいて、故障部分ネット
ワーク以外の部分ネットワークの一つを特定用途として
用い、複数のプロセッサからブロードキャストおよび部
分ブロードキャストは発生した場合には、シリアライス
ライズネットワークでそれらを逐次化し、かつ１対１転
送の転送経路中に故障部分ネットワークがある場合に、
シリアライスライズネットワークで迂回できるため、デ
ッドロックを回避し、特定プロセッサへのメッセージの
集中を緩和できる。

【図面の簡単な説明】

【図１】本発明の実施例における並列計算機の構成を示
す図である。

【図２】本発明の第１の実施例におけるブロードキャス
トメッセージの流れの概略を示す図である。

【図３】本発明の第１の実施例におけるクロスバスイッ
チ故障時のメッセージの流れの概略を示すである。

【図４Ａ】本発明の第１の実施例における中継スイッチ
故障時のブロードキャストメッセージの流れの概略を示
す図である。

【図４Ｂ】本発明の第１の実施例における中継スイッチ
故障時の１対１転送のメッセージの流れの概略を示す図
である。

【図５】本発明の第１の実施例におけるメッセージのフ
ォーマットを示す図である。

【図６】本発明の第１の実施例における中継スイッチの
構成を示す図である。

【図７】図６における経路指示回路の内部構成を示す図
である。

【図８】図７におけるＡＮＤゲート群の内部構成を示す
図である。

【図９】本発明の実施例におけるクロスバスイッチの構
成を示す図である。

【図１０】図９における迂回指示回路の内部構成を示す
図である。

【図１１】図９における経路指示回路の内部構成を示す
図である。

【図１２】本発明の第１の実施例におけるブロードキャ
ストメッセージの流れを示す図である。

【図１３】本発明の第１の実施例におけるクロスバスイ
ッチ故障時のブロードキャストメッセージの流れを示す
図である。

【図１４】本発明の第１の実施例におけるクロスバスイ
ッチ故障時の１対１転送メッセージの流れを示す図であ
る。

【図１５】本発明の第１の実施例における中継スイッチ
故障時のブロードキャストメッセージの流れを示す図で
ある。

【図１６】本発明の第１の実施例における中継スイッチ
故障時の１対１転送メッセージの流れを示す図である。

【図１７】本発明の第２の実施例におけるメッセージの
フォーマットを示す図である。

【図１８】本発明の第２の実施例における中継スイッチ
内の経路指示回路の内部構成を示す図である。

【図１９】本発明の第２の実施例におけるクロスバスイ
ッチ内の経路指示回路の内部構成を示す図である。

【図２０】ブロードキャスト逐次回路の構成を示す図で
ある。

【図２１】本発明の第２の実施例における複数の部分放
送範囲を示す図である。

【図２２】本発明の第２の実施例における部分ブロード
キャストメッセージの流れを示す図である。

【図２３】本発明の第２の実施例におけるクロスバスイ
ッチ故障時の部分ブロードキャストメッセージの流れを
示す図である。

【図２４】本発明の第２の実施例における中継スイッチ
故障時の部分ブロードキャストメッセージの流れを示す
図である。

【図２５】本発明の第３の実施例における中継スイッチ
内部のＡＮＤゲート群の内部構成を示す図である。

【図２６】図１９の中の部分放送経路指示回路の内部構
成を示す図である。

【符号の説明】

１００〜１１５ プロセッサ １１６〜１３１ 中継スイッチ １３２〜１３９ クロスバスイッチ １４０ ホスト計算機またはＳＶＰ ６００ 経路指示回路 ６０１〜６０３ 経路情報変更回路 ６１０ 迂回指示回路 ６１１ 一致判定回路 ７０１〜７０３ 選択回路 ７１０ ＡＮＤゲート群 ９００ 経路指示回路 ９０５ 迂回指示回路 ９０６〜９０９ 経路情報変更回路 １１００ レジスタ群 １１０１〜１１０４ 選択回路 １１８０ ブロードキャスト逐次回路

フロントページの続き (51)Int.Cl.⁶ 識別記号 庁内整理番号 ＦＩ 技術表示箇所 Ｇ０６Ｆ 15/16 ４７０ Ａ Ｇ０６Ｆ 15/16 ４００ Ｗ (72)発明者 中川 貴之 神奈川県秦野市堀山下１番地 株式会社日 立製作所汎用コンピュータ事業部内 (72)発明者 佐伯 裕治 神奈川県秦野市堀山下１番地 株式会社日 立製作所汎用コンピュータ事業部内

Claims (30)

【特許請求の範囲】
1. 【請求項１】 ｎ次元（ｎ≧２）の各次元毎に複数の部
   分ネットワークを設け、各次元の部分ネットワークの交
   点に該各次元の部分ネットワークに接続される中継スイ
   ッチを配置し、該中継スイッチにプロセッサを接続し、
   複数のメッセージを複数のプロセッサ間で並列に転送可
   能にしたネットワークにおけるメッセージを転送先プロ
   セッサに転送するプロセッサ間データ転送方法であっ
   て、 ブロードキャストメッセージを逐次化するための部分ネ
   ットワークであるシリアライズネットワークの経路情報
   を各部分ネットワーク及び各中継スイッチ中に予め記憶
   し、 送信元プロセッサから転送されるブロードキャストメッ
   セージを前記経路情報に従って部分ネットワーク及び中
   継スイッチを介してシリアライズネットワークに転送
   し、 該シリアライズネットワークは該シリアライズネットワ
   ークに接続された各中継スイッチを介して次元の異なる
   各部分ネットワークにメッセージを転送し、 該各部分ネットワークに接続された中継スイッチを介し
   て各プロセッサにメッセージをブロードキャストするこ
   とを特徴とするプロセッサ間データ転送方法。
2. 【請求項２】 請求項１記載のプロセッサ間データ転送
   方法において、 前記部分ネットワークの故障情報を関連する前記中継ス
   イッチに予め記憶し、 該関連する中継スイッチに接続されたプロセッサが送信
   元プロセッサとして１対１メッセージを転送するとき、
   該中継スイッチは前記故障情報に基づき該メッセージを
   前記シリアライズネットワークに転送することを特徴と
   するプロセッサ間データ転送方法。
3. 【請求項３】 請求項１記載のプロセッサ間データ転送
   方法において、 前記中継スイッチの故障情報を関連する前記部分ネット
   ワークに予め記憶し、 前記部分ネットワークは送信元プロセッサから転送され
   る１対１メッセージを前記故障情報に基づき故障中継ス
   イッチを介することなく転送することを特徴とするプロ
   セッサ間データ転送方法。
4. 【請求項４】 請求項１記載のプロセッサ間データ転送
   方法において、 前記経路情報は前記部分ネットワークに付された番号を
   含む情報であることを特徴とするプロセッサ間データ転
   送方法。
5. 【請求項５】 請求項１記載のプロセッサ間データ転送
   方法において、 前記部分ネットワークはクロスバスイッチであることを
   特徴とするプロセッサ間データ転送方法。
6. 【請求項６】 請求項１記載のプロセッサ間データ転送
   方法において、 前記部分ネットワークは、前記経路情報により転送先を
   決定する手段を有することを特徴とするプロセッサ間デ
   ータ転送方法。
7. 【請求項７】 請求項２記載のプロセッサ間データ転送
   方法において、 前記中継スイッチは、前記故障情報により転送先を決定
   する手段を有することを特徴とするプロセッサ間データ
   転送方法。
8. 【請求項８】 請求項３記載のプロセッサ間データ転送
   方法において、 前記部分ネットワークは、前記故障情報により転送先を
   決定する手段を有することを特徴とするプロセッサ間デ
   ータ転送方法。
9. 【請求項９】 請求項１記載のプロセッサ間データ転送
   方法において、 前記中継スイッチは、該中継スイッチに接続されたプロ
   セッサの装置番号と前記経路情報を比較する手段を有す
   ることを特徴とするプロセッサ間データ転送方法。
10. 【請求項１０】 請求項６記載のプロセッサ間データ転
    送方法において、 前記転送先を決定する手段は、該転送先としてシリアラ
    イズネットワークあるいはメッセージ中の転送先プロセ
    ッサのいずれかを選択する選択手段を有することを特徴
    とするプロセッサ間データ転送方法。
11. 【請求項１１】 請求項１記載のプロセッサ間データ転
    送方法において、 前記シリアライズネットワークに接続され、該シリアラ
    イズネットワークにメッセージを転送する中継スイッチ
    は、該メッセージを同時に、該中継スイッチに接続され
    た他の部分ネットワーク及び該中継スイッチに接続され
    たプロセッサに転送し、該シリアライズネットワークは
    該中継スイッチから転送されたメッセージを該中継スイ
    ッチには転送しないようにすることを特徴とするプロセ
    ッサ間データ転送方法。
12. 【請求項１２】 請求項１記載のプロセッサ間データ転
    送方法において、 ブロードキャストメッセージをシリアライズネットワー
    クからブロードキャストする場合には、該シリアライズ
    ネットワークに接続された全ての中継スイッチにメッセ
    ージを転送し、ブロードキャストメッセージをシリアラ
    イズネットワーク以外の部分ネットワークからブロード
    キャストする場合には、該部分ネットワークへブロード
    キャストメッセージを転送した中継スイッチ以外の全て
    の中継スイッチにメッセージを転送することを特徴とす
    るプロセッサ間データ転送方法。
13. 【請求項１３】 ｎ次元（ｎ≧２）の各次元毎に複数の
    部分ネットワークを設け、各次元の部分ネットワークの
    交点に該各次元の部分ネットワークに接続される中継ス
    イッチを配置し、該中継スイッチにプロセッサを接続
    し、複数のメッセージを複数のプロセッサ間で並列に転
    送可能にしたネットワークにおいて、該複数のプロセッ
    サから選択された一群のプロセッサに選択的に部分ブロ
    ードキャストメッセージを転送するプロセッサ間データ
    転送方法であって、 前記部分ブロードキャストメッセージ内に前記一群のプ
    ロセッサを指定する範囲情報を設定し、 部分ブロードキャストメッセージを逐次化するための部
    分ネットワークであるシリアライズネットワークの経路
    情報を各部分ネットワーク及び各中継スイッチ中に予め
    記憶し、送信元プロセッサから転送される部分ブロード
    キャストメッセージを前記経路情報に従って部分ネット
    ワーク及び中継スイッチを介してシリアライズネットワ
    ークに転送し、 該シリアライズネットワークは、該シリアライズネット
    ワークに接続され、前記範囲情報の条件を満たす中継ス
    イッチを介して次元の異なる部分ネットワークにメッセ
    ージを転送し、該部分ネットワークは前記範囲情報の条
    件を満たす中継スイッチを介してプロセッサにメッセー
    ジを転送することを特徴とするプロセッサ間データ転送
    方法。
14. 【請求項１４】 請求項１３記載のプロセッサ間データ
    転送方法において、 前記経路情報は前記部分ネットワークに付された番号を
    含む情報であることを特徴とするプロセッサ間データ転
    送方法。
15. 【請求項１５】 請求項１３記載のプロセッサ間データ
    転送方法において、 前記部分ネットワークはクロスバスイッチであることを
    特徴とするプロセッサ間データ転送方法。
16. 【請求項１６】 ｎ次元（ｎ≧２）の各次元毎に複数の
    部分ネットワークを設け、各次元の部分ネットワークの
    交点に該各次元の部分ネットワークに接続される中継ス
    イッチを配置し、該中継スイッチにプロセッサを接続
    し、複数のメッセージを複数のプロセッサ間で並列に転
    送可能にしたネットワークを備える並列計算機であっ
    て、 前記各部分ネットワーク及び各中継スイッチは、ブロー
    ドキャストメッセージを逐次化するための部分ネットワ
    ークであるシリアライズネットワークの経路情報を予め
    記憶し、 前記部分ネットワーク及び中継スイッチは、関連する送
    信元プロセッサから転送されるブロードキャストメッセ
    ージを前記経路情報に従って前記シリアライズネットワ
    ークに転送し、 該シリアライズネットワークは該シリアライズネットワ
    ークに接続された各中継スイッチを介して次元の異なる
    各部分ネットワークにメッセージを転送し、 該各部分ネットワークは接続された中継スイッチを介し
    て各プロセッサにメッセージをブロードキャストするこ
    とを特徴とする並列計算機。
17. 【請求項１７】 請求項１６記載の並列計算機におい
    て、 故障した前記部分ネットワークに関連する前記中継スイ
    ッチは前記部分ネットワークの故障情報を予め記憶し、
    該関連する中継スイッチに接続されたプロセッサが送信
    元プロセッサとして１対１メッセージを転送するとき、
    該中継スイッチは前記故障情報に基づき該メッセージを
    前記シリアライズネットワークに転送することを特徴と
    する並列計算機。
18. 【請求項１８】 請求項１６記載の並列計算機におい
    て、 故障した前記中継スイッチに関連する前記部分ネットワ
    ークは前記中継スイッチの故障情報を予め記憶し、 前記部分ネットワークは送信元プロセッサから転送され
    る１対１メッセージを前記故障情報に基づき故障中継ス
    イッチを介することなく転送することを特徴とする並列
    計算機。
19. 【請求項１９】 請求項１６記載の並列計算機におい
    て、 前記経路情報は前記部分ネットワークに付された番号を
    含む情報であることを特徴とする並列計算機。
20. 【請求項２０】 請求項１６記載の並列計算機におい
    て、 前記部分ネットワークはクロスバスイッチであることを
    特徴とする並列計算機。
21. 【請求項２１】 請求項１６記載の並列計算機におい
    て、 前記部分ネットワークは、前記経路情報により転送先を
    決定する手段を有することを特徴とする並列計算機。
22. 【請求項２２】 請求項１７記載の並列計算機におい
    て、 前記中継スイッチは、前記故障情報により転送先を決定
    する手段を有することを特徴とする並列計算機。
23. 【請求項２３】 請求項１８記載の並列計算機におい
    て、 前記部分ネットワークは、前記故障情報により転送先を
    決定する手段を有することを特徴とする並列計算機。
24. 【請求項２４】 請求項１６記載の並列計算機におい
    て、 前記中継スイッチは、該中継スイッチに接続されたプロ
    セッサの装置番号と前記経路情報を比較する手段を有す
    ることを特徴とする並列計算機。
25. 【請求項２５】 請求項２１記載の並列計算機におい
    て、 前記転送先を決定する手段は、該転送先としてシリアラ
    イズネットワークあるいはメッセージ中の転送先プロセ
    ッサのいずれかを選択する選択手段を有することを特徴
    とする並列計算機。
26. 【請求項２６】 請求項１６記載の並列計算機におい
    て、 前記シリアライズネットワークに接続され、該シリアラ
    イズネットワークにメッセージを転送する中継スイッチ
    は、該メッセージを同時に、該中継スイッチに接続され
    た他の部分ネットワーク及び該中継スイッチに接続され
    たプロセッサに転送し、該シリアライズネットワークは
    該中継スイッチから転送されたメッセージを該中継スイ
    ッチには転送しないようにすることを特徴とする並列計
    算機。
27. 【請求項２７】 請求項１６記載の並列計算機におい
    て、 ブロードキャストメッセージをシリアライズネットワー
    クからブロードキャストする場合には、該シリアライズ
    ネットワークに接続された全ての中継スイッチにメッセ
    ージを転送し、ブロードキャストメッセージをシリアラ
    イズネットワーク以外の部分ネットワークからブロード
    キャストする場合には、該部分ネットワークへブロード
    キャストメッセージを転送した中継スイッチ以外の全て
    の中継スイッチにメッセージを転送することを特徴とす
    る並列計算機。
28. 【請求項２８】 ｎ次元（ｎ≧２）の各次元毎に複数の
    部分ネットワークを設け、各次元の部分ネットワークの
    交点に該各次元の部分ネットワークに接続される中継ス
    イッチを配置し、該中継スイッチにプロセッサを接続
    し、複数のメッセージを複数のプロセッサ間で並列に転
    送可能にしたネットワークにおいて、該複数のプロセッ
    サから選択された一群のプロセッサに選択的に部分ブロ
    ードキャストメッセージを転送する並列計算機であっ
    て、 前記部分ブロードキャストメッセージ内に前記一群のプ
    ロセッサを指定する範囲情報を設定し、 前記各部分ネットワーク及び各中継スイッチは、部分ブ
    ロードキャストメッセージを逐次化するための部分ネッ
    トワークであるシリアライズネットワークの経路情報を
    予め記憶し、 前記部分ネットワーク及び中継スイッチは、関連する送
    信元プロセッサから転送される部分ブロードキャストメ
    ッセージを前記経路情報に従って前記シリアライズネッ
    トワークに転送し、 該シリアライズネットワークは、該シリアライズネット
    ワークに接続され、前記範囲情報の条件を満たす中継ス
    イッチを介して次元の異なる部分ネットワークにメッセ
    ージを転送し、該部分ネットワークは前記範囲情報の条
    件を満たす中継スイッチを介してプロセッサにメッセー
    ジを転送することを特徴とする特徴とする並列計算機。
29. 【請求項２９】 請求項２８記載の並列計算機におい
    て、 前記経路情報は前記部分ネットワークに付された番号を
    含む情報であることを特徴とする並列計算機。
30. 【請求項３０】 請求項２８記載の並列計算機におい
    て、 前記部分ネットワークはクロスバスイッチであることを
    特徴とする並列計算機。