(57)【特許請求の範囲】
【請求項１】
多次元格子空間の各格子点のアドレスが与えられる複数のプロセッサと、前記複数のプロセッサ間のメッセージ通信のためのネットワークとを含む並列計算機であって、
前記ネットワークは、
前記多次元格子空間の第１方向の各辺ごとに、それぞれその辺に並ぶ格子点の間のメッセージ転送を受け持つ複数の第１方向クロスバスイッチと、
前記多次元格子空間の第２方向の各辺ごとに、それぞれその辺に並ぶ格子点の間のメッセージ転送を受け持つ複数の第２方向クロスバスイッチと
前記多次元格子空間の各格子点にそれぞれ設けられ、その格子点アドレスのプロセッサからその格子点を接続する第１方向クロスバスイッチもしくはその格子点を接続する第２方向クロスバスイッチへのメッセージの中継、前記第１方向クロスバスイッチから前記第２方向クロスバスイッチもしくは前記プロセッサへのメッセージの中継、及び前記第２方向クロスバスイッチから前記第１方向クロスバスイッチもしくは前記プロセッサへのメッセージの中継を選択的に行う中継スイッチとを有し、
各プロセッサは、送信するメッセージが部分放送メッセージであるとき、放送先のプロセッサの範囲によりその部分放送メッセージが第１方向クロスバスイッチ及び第２方向クロスバスイッチにそれぞれ中継されるべきか否かを示す経路指示情報を付加して対応する中継スイッチに送信する手段を備え、
各格子点の中継スイッチは、入力した部分放送メッセージに付加された経路指示情報にしたがい、かつ該経路指示情報が第１方向クロスバスイッチおよび第２方向クロスバスイッチの双方への中継を示す場合は第１方向クロスバスイッチを優先して、該入力した部分放送メッセージの中継先を、当該格子点を接続する第１方向クロスバスイッチ、当該格子点を接続する第２方向クロスバスイッチ、及び当該格子点アドレスのプロセッサの中の一つに決定する経路決定回路と、メッセージが次に別の中継スイッチに転送されたときの中継経路を示すように前記入力した部分放送メッセージの経路指示情報を変更し、変更した部分放送メッセージを決定した中継先に転送する手段を有し、
各第１方向クロスバスイッチは、転送を受け持つ格子点に対応する入力ポートの各々に対応して、その入力ポートから入力した部分放送メッセージが転送されるべきプロセッサ群の第１方向アドレスの範囲が予め設定されるレジスタ手段と、各入力ポートから入力したメッセージが部分放送メッセージであった時に該部分放送メッセージを同時送信する出力ポートを対応するレジスタ手段に設定された第１方向アドレスの範囲内にある各格子点に対応する出力ポートとする転送制御回路を有し、
各第２方向クロスバスイッチは、転送を受け持つ格子点に対応する入力ポートの各々に対応して、その入力ポートから入力した部分放送メッセージが転送されるべきプロセッサ群の第２方向アドレスの範囲が予め設定されるレジスタ手段と、各入力ポートから入力したメッセージが部分放送メッセージであった時に該部分放送メッセージを同時送信する出力ポートを対応するレジスタ手段に設定された第２方向アドレスの範囲内にある各格子点に対応する出力ポートとする転送制御回路を有することを特徴とする並列計算機。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、複数のプロセッサを用いて計算を高速に実行する並列計算機において、特に１つのプロセッサから多数のプロセッサにデータを転送する放送機能に関連する。
【０００２】
【従来の技術】
多数のプロセッサをネットワークで結合し、相互に協調させながら高速に処理を実行する並列計算機が実用化されつつある。
【０００３】
キューブ型のネットワークを持ち、あるプロセッサから他のプロセッサへの転送経路が短いためデータを高速に転送できる並列計算機において、ブロードキャスト機能を実現する方法としては、たとえば特開平１−２６７７６３に開示されている方式がある。
【０００４】
上記特開平１−２６７７６３に開示されている方式は、ｎ台のプロセッサをｎ＝ｎ1×ｎ2×ｎ3×……×ｎnと因数分解し、これらの因数の各々を一辺の格子点数とするｎ次元格子空間上にプロセッサを並べ、その各辺をクロスバスイッチからなる部分ネットワークで結合してメッセージ転送経路を構成し、１つのプロセッサから全プロセッサへデータを並列に転送するブロードキャスト機能を実現している。
【０００５】
並列計算機におけるプロセッサ間のデータ転送機能として、ブロードキャスト機能の他に、ある限定された範囲のプロセッサの集まりであるプロセッサグループ内のプロセッサにのみデータを転送する、部分ブロードキャスト機能がある。並列計算機において、プログラムを全プロセッサ内の一部のプロセッサにマッピングして並列実行する場合、部分ブロードキャスト機能が必要となる。
【０００６】
トーラス型のネットワークを持つ並列計算機において、部分ブロードキャスト機能を備える装置としては、たとえば情報処理学会研究報告Ｖｏｌ．９０，Ｎｏ．６０の第２２３頁から第２２８頁に記載の装置が挙げられる。この装置では、複数のプロセッサを２次元格子上に配置し、これらを２次元のトーラス状に接続し、送信先プロセッサの範囲を送信元プロセッサの近傍（行方向、列方向、行方向と列方向の組み合わせ）に限定し、部分ブロードキャストを実現しているがその実現方法は、具体的には開示していない。
【０００７】
また、特開昭６１−３５６４５号公報には、リング状に接続されたプロセッサの一つから、メッセージにプロセッサ群の識別子を付して、その識別子のプロセッサのみがそのメッセージを受信する技術が開示されている。前記研究報告の２２９〜２３４頁にも同様の技術が開示されている。
【０００８】
【発明が解決しようとする課題】
上記特開昭６１−３５６４５では、全てのプロセッサに放送メッセージが送付され、それぞれのプロセッサにおいてそのメッセージを取り組むため、ムダなメッセージの転送が生じている。
【０００９】
上記情報処理学会研究報告Ｖｏｌ．９０，Ｎｏ．６０の第２２３頁から第２２８頁に記載の装置では、部分放送すべきプロセッサ以外のプロセッサに至る経路にもメッセージは転送されないが、格子状のネットワークであるため、転送されるデータを順送りする必要があり、部分放送すべきプロセッサの範囲が広い場合、データ転送に時間がかかる。
【００１０】
データの高速転送の観点からは、特開平１−２６７７６３のように、複数のプロセッサに並列にデータを放送することが望ましい。しかし、並列転送ネットワークでデータを移送すると本来データ転送すべきでないプロセッサに対しても、データ転送を行なってしまう。この無駄なデータ転送がネットワークの負荷を増加させ、プログラム実行の妨げとなって性能の低下を招くことになる。
【００１１】
本発明の目的は、複数のプロセッサに並列にデータを放送しうる方式のように、ネットワークを用いて、転送不要な経路へのデータ転送がなるべく生じない部分ブロードキャストを実現するブロードキャスト方法およびそのための並列計算機を提供することにある。
【００１２】
【課題を解決するための手段】
上記目的を達成するために、部分放送すべきプロセッサ群により定まる転送制御情報をネットワーク中にあらかじめ記憶し、ネットワークの途中の複数箇所（転送制御点）に部分放送メッセージが到達した場合に、その転送制御情報に従ってそのメッセージを下流に転送するか否かを制御する。
【００１３】
本発明の望ましい態様では、ネットワークが複数の部分ネットワークにより構成されているとき、各部分ネットワーク中に上記転送制御情報を記憶する。本発明のより望ましい態様では、各転送制御点に対応して、その点の下流に部分放送メッセージを転送するか否かを示す情報からなる転送制御情報を記憶する。
【００１４】
本発明の他の態様では、メッセージの転送先を制御する転送制御情報を含む放送メッセージを放送し、ネットワーク中のあらかじめ定めた複数の点（転送制御点）のいずれかにそのメッセージが到着したとき、そのメッセージに含まれる転送制御情報に従い、そのメッセージをさらに下流側に転送するか否かを制御する。本発明の具体的一態様ではネットワークが複数の部分ネットワークにより構成されているときに、各部分ネットワークに、部分放送すべきプロセッサの装置アドレスが属するアドレス範囲（最大アドレスと最小アドレス）を示す転送制御情報を記憶する手段と、その部分ネットワーク内の出力ポートに部分放送メッセージが到着したときに、そのアドレス範囲に基づいてその出力ポートの下流側に、そのアドレス範囲に属するプロセッサが接続されているかを判別する手段と、その判別結果によりそのメッセージの、下流側への転送を制御する手段を設ける。さらに本発明の、より望ましい一態様では、複数のプロセッサ群を規定し、それぞれのプロセッサ群内でメッセージを部分放送する。
【００１５】
このためには、より具体的には各転送制御点に、それぞれ一つのプロセッサ群により定まる複数の転送制御情報をあらかじめ記憶し、そこに放送メッセージが到着したときにその下流側に、いずれかのプロセッサ群に属するプロセッサが接続されているか否かをそれらの複数の転送制御情報により判別し、その結果により、その放送メッセージを下流側に転送するか否かを制御する。
【００１６】
【作用】
各転送制御点において、転送制御情報に従ってメッセージをさらに下流に転送するか否かを制御するので所定の範囲外にはメッセージを転送しない。これによって、無駄なデータ転送を抑止した部分ブロードキャストを実現することができる。
【００１７】
【実施例】
〈第１の実施例〉
第１の実施例を図面を参照して説明する。
【００１８】
図１において１００はプロセッサ（以下ＰＥと略す）、１３２〜１３５はＸ方向のクロスバスイッチ（以下ＸＢ−Ｘと略す）である。１３６〜１３９はＹ方向のクロスバスイッチ（以下ＸＢ−Ｙと略す）である。１１６は各ＸＢ−Ｘと各ＹＢ−Ｙの交点に設けられた中継スイッチ（以下ＥＸと略す）である。以下では、これらのクロスバスイッチを区別しないで言うときは、単にＸＢと言うことがある。１４０はホスト計算機またはサ−ビスプロセッサ（ＳＶＰ）である。各ＰＥは２次元座標空間の一つの格子点のＸ座標、Ｙ座標をそのＰＥの番号として与えられている。各ＸＢ−Ｘは同一のＹ座標を有するＰＥに対して設けられ、そのＹ座標ｉをつけてＸＢ−Ｘｉと呼ぶ。各ＸＢ−Ｙは同一のＸ座標を有するＰＥに対して設けられ、そのＸ座標ｊつけてＸＢ−Ｙｊと呼ぶ。各ＥＸは一つのＰＥに対応して設けられ、以下では対応するＰＥの番号と同じ番号をつける。ここではＸ方向の４つのクロスバスイッチ、Ｙ方向の４つのクロスバスイッチを示しているが、これらの数はあくまで一例である。
【００１９】
本実施例では、各ＰＥは経路指示情報を生成するルーティングビット生成回路２０８を有し、この経路指示情報を含んだ部分放送メッセージを送信するようになっている。
【００２０】
各ＥＸは対応するＰＥ、ＸＢ−Ｘ又はＸＢ−Ｙから転送された部分放送メッセージをさらにＸＢ−Ｙ、ＸＢ−Ｘ又はＰＥに転送するもので、そこに転送された部分放送メッセージ内の経路情報により、そのメッセージの転送先を決める部分放送経路指示回路４０３〜４０５を有する。さらにこの部分放送メッセージを転送する前にそのメッセージ内の経路指示情報を変更する回路３１１を有する。
【００２１】
さらに各ＸＢは、いずれかの入力ポートから入力された部分放送メッセージを複数の出力ポートに並列に転送するもので、部分放送経路指示回路６０４を有する。この回路６０４は、複数のプロセッサ群の情報を保持する境界レジスタ群７０と、各出力ポートに部分放送メッセージが転送されたとき、その下流側に、いずれかのプロセッサ群に属するプロセッサがあるかをこのレジスタ群７０の内容から判定し、その出力ポートの下流にそのメッセージを転送するか否かを制御する転送制御回路７０８〜７１１を有し、もしそのようなプロセッサがあれば、その出力ポートの下流側にあるＥＸにそのメッセージを転送するようになっている。図１９はプロセッサ群の例を示す図である。各プロセッサ群は、その中のＰＥの間でのみメッセージが放送されるＰＥの集合である。丸印はＰＥを例示し、その中の番号はＰＥの番号を示している。各プロセッサ群は、図１９（ａ）に示すように、２次元の矩形の領域５０Ａ、５０Ｂ又は５０Ｃに含まれるＰＥからなっていてもよい。又、図１９（ｂ）、又は（ｃ）に示すように、一列のＰＥ又は一行のＰＥからなっていてもよい。
【００２２】
本実施例では、各プロセッサ群でのメッセージを部分放送するときに、他のプロセッサ群では、その部分放送と並行して他のメッセージを放送できるのが特徴である。
【００２３】
以下では、特に断らない限り図１９（ａ）の場合を例に用いる。
【００２４】
本実施例では特定のＰＥへ送るメッセージ（通常のメッセージ）と、全ＰＥに送るメッセージ（放送メッセージ）と一部のＰＥに送るメッセージ（部分放送メッセージ）を転送できるようになっている。
【００２５】
まず、メッセージフォーマットを図８に示す。いずれのメッセージも、図８（ａ）に示すように送信ＰＥ番号、受信ＰＥ番号、経路指示情報（これは２ビットのルーティングビット（Ｒ０、Ｒ１）からなる）、ＣＴＬ（コントロール）ビット、データをそれぞれ保持するフィールドにより構成される。ＣＴＬビットはメッセージの持つ属性を示すもので、部分ブロードキャストであることを示すビット（ＰＢビット）、ブロードキャストであることを示すビット（ＢＣビット）を内部に持っている。送信ＰＥ番号はメッセージを送り出すＰＥの番号である。受信ＰＥ番号はメッセージを受け取るＰＥの番号である。ルーティングビットのうち、Ｒ０はＸＢ−Ｘへの送信の要否を、Ｒ１はＸＢ−Ｙへの送信の要否を示すビットである。本発明に関連する部分放送メッセージの場合には、図８（ｂ）に示すようにＰＢ＝１、ＢＣ＝０でありＲ０、Ｒ１が適当な値をもつが、送信ＰＥ番号、受信ＰＥ番号は有意な値とならない。＊はこのことを示す。
【００２６】
なお、放送メッセージの場合には図８（ｃ）に示すようにＰＢ＝０、ＢＣ＝１となるが、Ｒ０、Ｒ１、送信ＰＥ番号、受信ＰＥ番号は有意な値とならない。
【００２７】
また、通常のメッセージの場合には図８（ｄ）に示すように送信ＰＥ番号、受信ＰＥ番号がともに有意となるがＰＢ＝ＢＣ＝０であり、Ｒ０、Ｒ１ビットは有意な値とならない。Ｒ０、Ｒ１、ＰＢ、ＢＣの各ビットの生成方法、使い方については、後述する。
【００２８】
図２は各ＰＥの構成を示している。２００はプログラムを実行するデータ処理装置、２０１はデータと命令列を格納するメモリ、２０２はそのＰＥに対応するＥＸからメッセージを受信し、メモリ２０１に転送する受信制御回路、２０３は送信制御回路である。送信制御回路２０３は、メモリ２０１から読み出されたルーティングビットＲ０、Ｒ１以外の、メッセージ内容を保持するレジスタ２０４〜２０７、メッセージに新たに付加するルーティングビットＲ０、Ｒ１を生成するルーティングビット生成回路２０８、メッセージを生成し、そのＰＥに対応するＥＸに転送するメッセージ生成回路２０９から構成される。なお、レジスタ２０４〜２０７に保持されるメッセージ内容は、送信ＰＥ番号、受信ＰＥ番号、ＣＴＬビット、データのフィールドからなるが、それらのフィールドの一部は図８（ｂ）〜（ｄ）に示したように送出するメッセージの種類により有意でない。特に部分放送メッセージで有意なのはＣＴＬビット、データのみである。
【００２９】
ルーティングビット生成回路２０８は、そのＰＥから部分放送メッセージを送信するとき動作するもので、そのＰＥから部分ブロードキャストを行なうべきプロセッサ群内にあるＰＥの座標の内の最大座標（最大のＹ座標ＹＭＡＸと最大のＸ座標ＸＭＡＸ）と最小座標（最小のＹ座標ＹＭＩＮと最小のＸ座標ＸＭＩＮ）を保持するレジスタ２１０および２１１、それぞれ最大のＸ座標ＸＭＡＸと最小のＸ座標ＸＭＩＮを比較する比較回路２１２および最大のＹ座標ＹＭＡＸと最小のＹ座標ＹＭＩＮを比較する比較回路２１３、それぞれの結果と部分ブロードキャストビット（ＰＢビット）の論理積を生成するＡＮＤ回路２１４および２１５から構成される。たとえば図１９（ａ）の場合、ＰＥ００、ＰＥ０１、ＰＥ１０、およびＰＥ１１内のレジスタ２１０にはＰＥ１１の座標１１、レジスタ２１１にはＰＥ００の座標００が保持されている。これらの値は、事前（プログラムをＰＥにローディングしたときなど）に外部（たとえばホスト計算機またはＳＶＰ１４０（図１））から設定される。
【００３０】
部分放送メッセージを送信するＰＥ（図１９（ａ）のプロセッサ群５０Ａの場合には例えばＰＥ００）では、データ処理装置２００によって必要な情報がメモリ２０１から読み出され、レジスタ２０４〜２０７にセットされた後、メッセージ生成回路２０９に送られる。なお部分ブロードキャストのときにはＣＴＬビット２０６内にＰＢビットとして１、ＢＣビットとして０がセットされている。ＭＡＸ座標２１０の内のＸＭＡＸとＭＩＮ座標２１１の内のＸＭＩＮが比較回路２１２で比較され、ＭＡＸ座標２１０の内のＹＭＡＸとＭＩＮ座標２１１の内のＹＭＩＮが比較回路２１３で比較される。これらの比較回路は、比較の結果一致が検出されないときに１を出力するようになっている。これらの比較回路２１２、２１３の出力はそれぞれＡＮＤ回路２１４、２１５によってＣＴＬビットの中のＰＢビットと論理積がとられ、メッセージ生成回路２０９に送られる。Ｒ０はそのＰＥからＸＢ−Ｘに送信するか否かを、Ｒ１はＸＢ−Ｙに送信するか否かを示すものである。すなわち、プロセッサ群の形状とＰＥで生成されるＲ０、Ｒ１の値との関係は図２０のとおりとなる。つまりＸＭＡＸとＸＭＩＮが一致するとき、すなわち、部分ブロードキャストするプロセッサ群が単一列に属するとき（図１９（ｂ））、Ｒ０は０となり、ＸＢ−Ｘ０に放送メッセージを送信しないようになっている。同様に、部分ブロードキャストすべきプロセッサ群が単一行に属するとき（図１９（ｃ））には、Ｒ１が０となりＸＢ−Ｙ０に放送メッセージを送出しないようになっている。図１９（ａ）の場合にはＲ０、Ｒ１がともに１である。つまりそのＰＥからＸＢ−Ｘの方向にもＸＢ−Ｙの方向にも放送メッセージを送信する必要があることを示している。メッセージ生成回路２０９は、２０４〜２０８より送られる情報にＲ０、Ｒ１を付加して図８（ｂ）、（ｃ）又は（ｄ）の形式のメッセージを生成し、ＥＸに送出する。
【００３１】
図３は各ＥＸの構成を示している。いずれのＥＸもハードウェアの構成は同じである。各ＥＸの３つの入力ポート３０はそれぞれＰＥ、ＸＢ−Ｘ、又はＸＢ−Ｙに接続されている。それらの入力ポート３０に入力されたメッセージはそれぞれ入力バッファ３００〜３０２に一時的に保持される。３０３〜３０５はそれぞれＸＢ−Ｘ、ＰＥ、ＸＢ−Ｙへメッセージを送り出す出力ポート、３０６は入力バッファ３００〜３０２内のメッセージの送信先を決めるための経路指示回路である。この回路３０６は後述するように、各入力ポートに対応して、部分放送用経路指示回路４０３、４０４又は４０５を有するのが本実施例の特徴である。これらの回路は、入力された部分放送メッセージ中のルーティングビットによりその転送先を決める。
【００３２】
３１０はメッセージを選択するセレクタであり、経路指示回路３０６からの信号により送信すべきメッセージが選択される。３１２は選択されたメッセージを一時的に保持しておく出力バッファである。３１１はルーティングビットＲ１の変更を行なう経路指示情報変更回路である。出力ポート３０４および３０５も３０３と同様の構成となる。
【００３３】
図４に経路指示回路３０６の内部の構成を示す。４０３〜４０５は部分ブロードキャストを行なうときにルーティングビットにより経路を決める部分放送経路指示回路である。４００〜４０２はそれぞれ入力バッファ３００〜３０２に入力されたメッセージＭ（ＰＥ）、Ｍ（Ｘ）、Ｍ（Ｙ）が通常のメッセージの場合に、その中の受信ＰＥ番号をデコードしメッセージの送信先を決めるアドレスデコーダで、そのメッセージ中のＰＢおよびＢＣが０のときに動作する。信号Ｍ（ＰＥ）、Ｍ（Ｘ）、Ｍ（Ｙ）はそれぞれそのＥＸが接続されたＰＥ、ＸＢ−Ｘ、ＸＢ−Ｙから入力されたメッセージの信号（受信ＰＥ番号、ルーティングビットＲ０、Ｒ１、部分ブロードキャストビットＰＢ、ブロードキャストビットＢＣ）を示す。また出力信号ＰＸ、ＸＸ、ＹＸはそれぞれＰＥ、ＸＢ−Ｘ、ＸＢ−Ｙから入力されたメッセージをＸＢ−Ｘへ送信することを示す。同様に、出力信号ＰＹ、ＸＹ、ＹＹはＰＥ、ＸＢ−Ｘ、ＸＢ−Ｙから入力されたメッセージをＸＢ−Ｙへ送信することを、出力信号ＰＰ、ＸＰ、ＹＰはＰＥ、ＸＢ−Ｘ、ＸＢ−Ｙから入力されたメッセージをＰＥへ送信することを示している。
【００３４】
経路指示回路４０３〜４０５は本実施例で新たに設けた回路であり、部分放送メッセージ内のルーティングビットにより図２１に従いそのメッセージの送信先を決める。たとえば、ＰＥから入力された部分放送メッセージの場合経路指示回路４０３では、ＰＢが１かつＲ０が１のとき（図２１のケース１又は２のとき）はＡＮＤ回路４２４の出力Ａが１となり、ＰＸが１となるのでＸＢ−Ｘが送信先となる。ＰＢが１、かつＲ０が０、かつＲ１が１のとき（図２１のケース３のとき）はＡＮＤ回路４２５の出力Ｂが１となり、ＰＹが１となるのでＸＢ−Ｙが送信先となる。ＰＢが１、かつＲ０が０、かつＲ１が０のとき（図２１のケース４のとき）はＡＮＤ回路４２６の出力Ｃが１となり、ＰＰが１となるのでＰＥが送信先となる。他の部分放送経路指示回路４０４、４０５の構造と動作も全く同じである。
【００３５】
このように、Ｒ０、Ｒ１により部分放送メッセージの転送先を決める理由は、後述する動作説明から分かるように、同じ部分放送メッセージが同じＥＸを複数回返るときの、転送先の決定が容易に行ないえることにある。このためには、部分放送メッセージの転送先を決定したあとに、経路指示情報変更回路３１１（図３）によりこれらのＲ０、Ｒ１を変更する必要がある。この回路は、図２１の最右欄に示すように、セレクタ３１０により選択されたメッセージのルーティングビットＲ０、Ｒ１がともに１のときだけＲ１は１に保持され、それ以外は０に変更する。Ｒ０は常に０として送出する。
【００３６】
３０７〜３０９はプライオリティ回路である。このプライオリティ回路は入力された３つのメッセージの一つを選択するもので、いずれを選んだかを示す信号ＳＸ、ＳＹ、ＳＰを出す。ここでは到着順にメッセージを選ぶことにしている。
図１９（ａ）の場合ＰＥ００から入力された部分放送メッセージに対するＥＸ００の動作は次のようになる。このメッセージは入力バッファ３００にセットされ、セレクタ３１０と経路指示回路３０６に送られる。この時ＰＢが１、ＢＣが０、Ｒ０が１、Ｒ１が１であるため、図４内の部分放送経路指示回路４０３の出力Ａが１となり、その結果ＯＲ回路の出力ＰＸが１となる。一方プライオリティ回路３０７（図４）では、ＯＲゲート群４３０からのＰＸを受け、セレクタ３１０で入力バッファ３００から送られたメッセージを選択するよう制御信号を生成し、出力ポート（１）３０３に送る。セレクタ３１０では入力バッファ３００から入力されたメッセージを選択し、経路指示情報変更回路３１１でルーティングビットＲ０、１が変更される。即ち、入力されたＲ０、Ｒ１はそれぞれ１、１であるため、Ｒ０、Ｒ１がそれぞれ０、１に変更される。Ｒ０、Ｒ１を変更された後の部分放送メッセージは、出力バッファ３１２にセットされＸＢ−Ｘ０へ送り出される。
【００３７】
なお、ＰＥから入力されたメッセージが通常メッセージ（ＰＢ＝０、ＢＣ＝０のメッセージ）の場合は受信ＰＥ番号をアドレスデコーダ４００でデコードして、送信先を決め、ＯＲゲート４１５〜４１７のいずれかに信号１を出力する。他のアドレスデコーダ４０１、４０２も同様である。
【００３８】
入力されたメッセージが放送メッセージの場合、本実施例では次のようになっている。
【００３９】
（１）ＰＥから入力された放送メッセージはＸＢ−Ｘに送る。
【００４０】
（２）ＸＢ−Ｘから入力された放送メッセージはＸＢ−Ｙに送る。
【００４１】
（３）ＸＢ−Ｙから入力された放送メッセージはＰＥに送る。
【００４２】
このために、例えばＰＥから入力されたメッセージが放送メッセージの場合、ＢＣが１であるため、そのメッセージのＢＣビットがそのままＯＲゲート４１５に送られ、信号ＰＸが１となり、メッセージはＸＢ−Ｘに送られる。同様に、ＸＢ−Ｘ又はＸＢ−Ｙから入力されたメッセージが放送メッセージのときには、そのメッセージ内のＢＣビットをＯＲゲート４１９又は４２３に送り、それぞれ信号ＸＹ、ＹＰが１となり、そのメッセージをＸＢ−Ｙ又はＰＥに送る。
【００４３】
図５にＸ方向クロスバスイッチＸＢ−Ｘ■（■＝０，１，２または３）の構成を示す。Ｙ方向クロスバスイッチも同様である。図の入出力信号ＥＸ０〜ＥＸ３はそのクロスバスイッチに接続されたＥＸ■０〜ＥＸ■３からの信号を示す。たとえばＸＢ−Ｘ０の場合、入出力信号ＥＸ０〜ＥＸ３はＥＸ００〜ＥＸ０３に置き換えられる。５００〜５０３は４つの入力ポートの１つを選択するスイッチである。ＸＢはクロスバスイッチであるため、入力ＥＸ０〜ＥＸ３のいずれもがそのままスイッチ５００〜５０３の入力につながっていて、いずれかの入力ポートから入力されたメッセージはそのままスイッチ５００〜５０３に供給される。経路指示回路５０４は、入力されたメッセージをどのスイッチから転送するかを決めるものである。５０４は４つのＥＸから入力されたメッセージの送信先を決めるための経路指示を行なう。本実施例では、経路指示回路５０４内に、部分放送経路回路６０４を設けたのが特徴である。この回路６０４は、このＸＢに入力された部分放送メッセージがある出力ポートに転送されたときに、その下流側にさらに転送するかを制御するものである。部分放送経路指示回路６０４には、部分ブロードキャストを行なうプロセッサ群に関する情報を保持する境界レジスタ群７０と、各出力ポートの下流に、それぞれのプロセッサ群に属するプロセッサが接続しているか否かを判定するための各出力ポートに対応して設けられた転送制御回路７０８〜７１１が設けられている。
【００４４】
図６に経路指示回路５０４の詳細を示す。この回路は、部分放送メッセージの転送経路を決める部分放送経路指示回路６０４と、アドレスデコーダ群５０とＯＲゲート６０９〜６２４およびプライオリティ回路５０５〜５０８からなる。
【００４５】
部分放送経路指示回路６０４の出力Ｅｉｊ（ｉ＝０〜３、ｊ＝０〜３）は、ＥＸｊから入力された部分放送メッセージを、ＥＸｉにさらに転送すべきことを示す信号である。この出力ＥｉｊはＯＲゲート６０９〜６２４を介してプライオリティ制御回路５０５〜５０８に入力される。これらのプライオリティ回路は入力された４つのメッセージの送出順序を決めるもので、ここでは到着順にメッセージを選ぶことにしている。ＯＲゲート６０９〜６１２の出力信号Ｄ００、Ｄ０１、Ｄ０２、Ｄ０３は入力されたメッセージをＥＸ０へ出力することを指示する信号であり、それぞれＥＸ０、ＥＸ１、ＥＸ２、ＥＸ３から入力されたメッセージから生成される。またＯＲゲート６１３〜６１６の出力信号Ｄ１０、Ｄ１１、Ｄ１２、Ｄ１３はＥＸ１へ、ＯＲゲート６１７〜６２０の出力信号Ｄ２０、Ｄ２１、Ｄ２２、Ｄ２３はＥＸ２へ、ＯＲゲート６２１〜６２４の出力信号Ｄ３０、Ｄ３１、Ｄ３２、Ｄ３３はＥＸ３へそれぞれメッセージを出力することを指示する信号であり、それぞれＥＸ０、ＥＸ１、ＥＸ２、ＥＸ３から入力されたメッセージから生成される。
【００４６】
なおアドレスデータ群５０は、ＸＢに入力されたメッセージが通常メッセージの場合に、その中の受信ＰＥ番号をデコードし、そのメッセージの送信先を決める、各入力ポート対応に設けたアドレスデコーダ６００〜６０３からなる。
【００４７】
たとえばＥＸ０から入力されたメッセージが通常メッセージの場合、そのメッセージ内の受信ＰＥ番号がアドレスデコーダ６００でデコードされ、ユニークに送信先が決められる。アドレスデコーダ６００は各出力ポートに対する＃０−＃３の４つの信号線からなり、受信先ＰＥ番号に応じてそれらの一つが１にされると、ＯＲゲート６０９、６１３、６１７、６２１の出力Ｄ００、Ｄ１０、Ｄ２０、Ｄ３０のいずれかが１になる。その入力されたメッセージがブロードキャストメッセージの時、即ちＢＣが１の場合は、そのＢＣがそのままＯＲゲート６０９、６１３、６１７、６２１に入力され、Ｄ００、Ｄ１０、Ｄ２０、Ｄ３０のすべてが１となり、ＥＸ０〜ＥＸ３の全てが送信先となる。以上の動作は、他の入力ポートから入力されたメッセージについても同様である。
【００４８】
図７に部分放送経路指示回路６０４の詳細を示す。境界レジスタ群７０は、複数対のレジスタからなり各対はそのクロスバスイッチの一つの入力ポートに対応して設けられている。本実施例では７００Ａと７００ＢがＥＸ０に接続された入力ポートに対するものである。同様に７０１Ａと７０１ＢはＥＸ１に接続された入力ポートに、７０２Ａと７０２ＡはＥＸ２に接続された入力ポートに、７０３Ａと７０３ＢはＥＸ３に接続された入力ポートに対応するものである。各レジスタ対は対応する入力ポートのＥＸに接続されたＰＥが、部分放送すべきいずれかのプロセッサ群に属するとき、そのプロセッサ群のアドレスの最大値と最小値を保持する。たとえば、レジスタ７００ＡはＥＸ０に接続されたＰＥがいずれかのプロセッサ群に属するとき、そのプロセッサ群のＸ座標の最大値ＸＭＡＸ０を保持する。一方レジスタ７００Ｂは、そのプロセッサ群のＸ座標の最小値ＸＭＩＮ０を保持する。他のレジスタ対についても同様にＸＭＡＸｉ、ＸＭＩＮｉ（ｉ＝１、２、又は３）を保持する。
【００４９】
たとえば図１９（ａ）のようにプロセッサ群５０Ａ〜５０Ｃが定められているとき、ＰＥ００に接続されたクロスバスイッチＸＢ−Ｘ０の、レジスタ７００Ａ、７００Ｂには、プロセッサ群５０ＡのＸ座標の最大値１と最小値０がそれぞれ保持される。一方、同じクロスバスイッチのレジスタ７０１Ａ、７０１Ｂには、対応するＰＥ０１が同じプロセッサ群に属するため、上と同じ値１、０がそれぞれセットされる。一方、同じクロスバスイッチのレジスタ７０２Ａと７０２Ｂにはプロセッサ群５０ＢのＸ座標の最大値３と最小値２がセットされる。レジスタ７０３Ａと７０３Ｂにも同じ値がセットされる。一方、図１９（ｂ）のプロセッサ群５０Ｄのように一列のプロセッサ群が定められているとき、ＰＥ００に接続されたＸＢ−Ｘ０の、レジスタ７００Ａ、７００Ｂにはプロセッサ群５０ＤのアドレスのＸ座標の最大値０と最小値０がそれぞれ保持される。また、そのレジスタ対に対応するＰＥがどのプロセッサ群に属さない場合にも、そのＰＥのＸ座標がそのレジスタ対に保持される。レジスタ群７０内の値は、部分放送を開始するより前にあらかじめ、ホストプロセッサ又はＳＶＰ１４０によりセットされる。転送制御回路７０８〜７１１は、それぞれ、一つの出力ポート（本実施例では一つのスイッチに対応する）に対応して設けられ、いずれかの入力ポートからその出力ポートに転送された部分放送メッセージを、その下流側にさらに転送するかを判断するものである。たとえば転送制御回路７０８は、ＥＸ０にメッセージを出力するスイッチ５００（図５）に対応し、レジスタ群７０内のＭＡＸ座標およびＭＩＮ座標とこのＥＸ０に対応するＰＥ０の座標を比較して、このＰＥ０が各入力ポートに対するＰＥが属する部分ブロードキャストに属するか否かを判定するための転送制御回路である。７１２は、制御するスイッチ５００の出力にＥＸを介して接続されている、ＰＥ自身の座標を保持するレジスタである。７１３〜７２０は比較回路、７２１〜７２４はＡＮＤ回路である。転送制御回路７０９〜７１１も７０８と同様の構成をとる。図面では内部の回路を省略してあるが、以後の説明では転送制御回路７０８と同じものがあるものとし、説明を行なう。
出力信号Ｅ００〜Ｅ０３は、それぞれＥＸ０〜ＥＸ３から入力されたメッセージが部分ブロードキャストである場合に、ＥＸ０にその部分放送メッセージを出力することを示す信号である。同様に、出力信号Ｅ１０〜Ｅ１３はＥＸ１へ、Ｅ２０〜Ｅ２３はＥＸ２へ、Ｅ３０〜Ｅ３３はＥＸ３へその部分放送メッセージを出力することを示す信号である。
【００５０】
たとえば転送制御回路７０８内の７１３と７１４はＥＸ０に接続された入力ポートに対応して設けられた一対の比較回路である。同様に他の一対の比較回路の対７１５と７１６はＥＸ１に接続された入力ポートに対して、７１７と７１８はＥＸ２に接続された入力ポートに対して、７１９と７２０はＥＸ３に接続された入力ポートに対して設けられている。各比較回路対は、その対応する入力ポートにＥＸを介して接続されたＰＥに対して設けられた一対の境界レジスタの値と、その転送制御回路に対応する、ＥＸ（たとえば転送制御回路７０８ではＥＸ０）を介して接続されたＰＥの座標を比較する。例えば比較回路の対７１７と７１８はＥＸ２に接続された入力ポートから部分放送メッセージがＥＸ０に接続された出力ポートに転送されたとき、このＰＥ２が属する部分放送のＸ方向範囲を示す一対の境界レジスタ７０２Ａ、７０２ＢにあるＸ方向の最大座標と最小座標をレジスタ７１２内にあるＰＥ０のＸ座標とを比較し、前者の間に後者が含まれていれば、ＡＮＤゲート７２３が１となるものである。勿論、このＡＮＤゲート７２３には、ＥＸ２に接続された入力ポートに入力された部分放送メッセージに含まれるＰＢビット（ここではＰＢ（ＥＸ２）と示す）が入力されている。ＰＥ２が属する部分放送範囲にＰＥ０が属するとき、このＡＮＤゲート７２３の出力Ｅ０２が１となる。この信号は、図６のＯＲゲート６１１を通ってプライオリティ制御回路５０５に送られ、そこでその信号Ｅ０２すなわちＤ０２が選択されたときに、そのプライオリティ制御回路５０５の出力Ｓ０により、スイッチ５００が、ＥＸ２から入力された前述の部分放送メッセージを選択し、ＥＸ０に転送する。しかし、ＥＸ２から入力された部分放送メッセージを放送する範囲内にＰＥ０が所属しないときには、ＡＮＤゲート７２３の出力Ｅ０２が０のままであり、ＰＥ０へのこの部分放送メッセージの転送はなされない。
【００５１】
次に、図５、６、７を用いて、ＸＢ−Ｘ０を例にとり、クロスバスイッチの動作を説明する。
【００５２】
図２２は、図１９（ａ）の場合において、ＰＥ００、０１、１０、１１のまわりにおける部分放送メッセージの転送経路を示したものである。図中（１、１）等は、そのメッセージに付されている（Ｒ０、Ｒ１）ビットを示す。すなわち、ＰＥ００から送出された部分放送メッセージの（Ｒ０、Ｒ１）は（１、１）であり、これがＥＸ００を経て、ＸＢ−Ｘ０に転送される。その際（Ｒ０、Ｒ１）は（０、１）に変更される。このメッセージはＸＢ−Ｘ０によりＥＸ００、ＥＸ０１に転送される。ＥＸ０２、ＥＸ０３には転送されない。
【００５３】
ＥＸ００に戻ったこのメッセージは（Ｒ０、Ｒ１）が（０、０）に変更された後、ＹＢ−Ｙ０に転送される。ＹＢ−Ｙ０はこのメッセージをＥＸ００、ＥＸ１０に再転送し、それらはＰＥ００、ＰＥ１０に送られる。一方、ＥＸ２０、ＥＸ３０には転送されない。ＹＢ−Ｙ１でも同様の動作となる。
【００５４】
こうして、図１９（ａ）の範囲５０Ａ内のプロセッサ間で部分放送を並列に行ないうる。さらに、これと並行して他の範囲５０Ｂ、５０Ｃでも別のメッセージを部分放送できるのが本実施例の他の特徴である。
【００５５】
以下ではこの動作がどのようにして実現されるかを説明する。
【００５６】
図５において、ＥＸ００から入力されたメッセージは、スイッチ５００〜５０３に送られるとともに、その一部が経路指示回路５０４に送られる。そのメッセージが部分放送メッセージのときＰＢが１、ＢＣが０となっているため、この回路５０４では、図６に示す部分放送経路指示回路６０４により、このメッセージの転送先が決められる。この回路６０４の転送制御回路７０８〜７１１（図７）の中のＰＥ座標レジスタ７１２には、それぞれ図５のスイッチ５００〜５０３の出力にＥＸを介して接続されているＰＥ座標００、０１、０２、０３のＸ座標０、１、２、３がセットされている。たとえば転送制御回路７０８では、比較回路７１３でレジスタ７００ＡのＸＭＡＸ０の値１とレジスタ７１２のＰＥ座標の値０が比較され１が出力される。比較回路７１４でレジスタ７００ＢのＸＭＩＮ０の値０とレジスタ７１２のＰＥ座標の値０が比較され１が出力される。そしてＡＮＤ回路７２１で、比較回路７１３および７１４の出力とＰＢの論理積がとられ、出力信号Ｅ００は１となる。すなわち、本実施例では、ＥＸ００から入力された部分放送メッセージは必ず、ＥＸ００に再転送されるようになっている。一方、他の転送制御回路７０９〜７１１においても同様の処理がなされるが、それらの中の対応する出力Ｅ１０、Ｅ２０、Ｅ３０の値は、ＰＥ０１、ＰＥ０２、ＰＥ０３がＰＥ００が属する部分ブロードキャスト範囲に属するか否かによりかわる。
【００５７】
例えば図１９（ａ）の例ではＰＥ０１はＰＥ００と同じ部分放送範囲に属するが、ＰＥ０２、ＰＥ０３はその範囲に属さないため、Ｅ１０は１となり、Ｅ２０、Ｅ３０は０である。
【００５８】
なお、各ＸＢ−ＹはＸＢ−Ｘと実質的に同一の回路にて構成され、それと異なるのは、境界レジスタ群７０にはＹ方向の最大座標ＹＭＡＸ０〜ＹＭＡＸ３、最小座標ＹＭＩＮ０〜ＹＭＩＮ３がセットされる点である。このことから図６における出力信号Ｄ００、Ｄ１０が１となるがＤ２０、Ｄ３０は０のままである。そして図６におけるプライオリティ回路５０５、５０６において、ＥＸ００からのメッセージが選ばれるようプライオリティがとられる。即ち、２つのスイッチ５００、５０１により、ＥＸ００から入力された部分放送メッセージが選ばれ、ＥＸ００、ＥＸ０１に送られるがＥＸ０２、ＥＸ０３には送られない。
【００５９】
ＸＢ−Ｘ０に接続されているＥＸ００、ＥＸ０１では、この部分放送メッセージに対して全て同様の動作を行なう。ここでは、ＥＸ０１を例にとる。ＥＸ０１は、図３において入出力信号のＰＥをＰＥ０１に、ＸＢ−ＸをＸＢ−Ｘ０に、ＸＢ−ＹをＸＢ−Ｙ１に置き換えたものである。図３において、ＸＢ−Ｘ０から入力された部分放送メッセージは、入力バッファ３０１にセットされ、出力ポート３０３〜３０５と経路指示回路３０６に送られる。経路指示回路３０６では、図４に示すように、部分放送経路指示回路４０４が、このメッセージの送信先を決める。すなわち、この回路４０４内のＡＮＤ回路４２４〜４２６にてメッセージ中のＰＢ、Ｒ１、Ｒ０の論理積がとられる。今の例では、ＰＢ、Ｒ１が１、Ｒ０が０であるため、出力信号Ｂだけが１となり、ＯＲゲート４１９の出力ＸＹが１となる。こうして、この部分放送メッセージはＸＢ−Ｙに転送することが決まる。この出力信号ＸＹはプライオリティ回路３０８へ入力され、そこにおいて図３の出力ポート（３）３０５にて入力バッファ３０１にセットされているＸＢ−Ｘ０から入力された部分放送メッセージを選択するよう制御信号ＳＹが生成される。出力ポート（３）では、セレクタ３１０で選択された部分放送メッセージのＲ０、Ｒ１が０、１であるため、変更回路３１１によりそれぞれ０、０に変更し出力バッファ３１２を介してＸＢ−Ｙ１へ送出する。同様に、ＥＸ００も、ＸＢ−Ｙ０にこの部分放送メッセージを送出する。
【００６０】
次に、図５、６、７を用いて、この部分放送メッセージに対するＸＢ−Ｙ１の動作を説明する。ＸＢ−Ｙ１では、図５の入出力信号ＥＸ０〜ＥＸ３はＥＸ０１〜ＥＸ３１となる。ＸＢ−Ｙ１は、ＸＢ−Ｘ０で行なった動作と同様の動作を行なう。すなわち、図５において、ＥＸ０１から入力された部分放送メッセージは、スイッチ５００〜５０３に送られるとともに、一部が経路指示回路５０４に送られる。この回路５０４では、部分放送経路指示回路６０４内の転送制御回路７０８〜７１１の中のＰＥ座標レジスタ７１２には、それぞれスイッチ５００〜５０３の出力にＥＸを介して接続されているＰＥの座標０１、１１、２１、３１のＹ座標０、１、２、３がセットされている。また、部分ブロードキャスト範囲が図１９（ａ）の５０Ａの場合、境界レジスタ群７０内のレジスタ７００ＡにはＹＭＡＸ０として１が、レジスタ７００ＢにはＹＭＩＮ０として０がセットされている。レジスタ７０１Ａ、７０１Ｂの値もそれぞれ１、０である。一方、レジスタ７０２Ａ、７０２Ｂには、それぞれ３、２がセットされている。レジスタ７０３Ａ、７０３Ｂも同様である。
【００６１】
このためにＥＸ０１に対応する転送制御回路７０８では、比較回路７１３でレジスタ７００ＡのＹＭＡＸ０の値１とＰＥ座標レジスタ７１２の値０が比較され出力が１となり、比較回路７１４でレジスタ７００ＢのＹＭＩＮ０の値０とＰＥ座標レジスタ７１２の値０が比較され出力が１となる。そしてＡＮＤ回路７２１で、比較回路７１３および７１４の結果とＰＢの論理積をとり出力信号Ｅ００は１となる。同様に、ＥＸ１１に対応する転送制御回路７０９では、同じ動作により出力信号Ｅ１０が１となる。すなわち、ＰＥ００と同じ部分放送群５０Ａに属するＰＥ０１、１１に対するＥＸ０１、ＥＸ１１にこの部分放送メッセージが転送されることが決定される。一方、ＥＸ２１に対応する転送制御回路７１０では、同様の動作がなされるがＰＥ座標レジスタ７１２の内容が２であり、ＹＭＩＮ０（＝０）とＹＭＡＸ０（＝１）の間にないので、出力信号Ｅ２０が０となる。転送制御回路７１１でも、同様に出力信号Ｅ３０が０となる。
【００６２】
これらにより、図６においてＤ００、Ｄ１０、Ｄ２０、Ｄ３０は、それぞれ１、１、０、０となる。プライオリティ回路５０５、５０６では、ＥＸ０１から入力された部分放送メッセージが選ばれるようプライオリティがとられる。即ち、図５に示す２つのスイッチ５００および５０１がＥＸ０１から入力された部分放送メッセージを選び、ＥＸ０１、ＥＸ１１へ送られる。一方ＥＸ０１から入力された部分放送メッセージはＥＸ２１、ＥＸ３１へは送り出されない。
【００６３】
ＸＢ−Ｙ１からこのメッセージを取り込んだＥＸ０１とＥＸ１１は、同じ動作を行なう。ここでは、ＥＸ１１を例にとる。ＥＸ１１では、図３において入出力信号のＰＥはＰＥ１１、ＸＢ−ＸはＸＢ−Ｘ１、ＸＢ−ＹはＸＢ−Ｙ１である。ＸＢ−Ｙ１から入力されたメッセージは、入力バッファ３０２にセットされ、出力ポート３０３〜３０５と経路指示回路３０６に送られる。この回路３０６では、部分放送経路指示回４０５内のＡＮＤ回路４２４〜４２６にてメッセージ中のＰＢ、Ｒ１、Ｒ０の論理積がとられる。ＰＢが１、Ｒ１、Ｒ０が０であるため、出力信号Ｃだけが１となり、ＹＰが１となる。この出力信号ＹＰはプライオリティ回路３０９に入力され、出力ポート（２）３０４にて入力バッファ３０２にセットされているＸＢ−Ｙ１からのメッセージを選択するよう制御信号ＳＰが生成される。出力ポート（２）では、選択された部分放送メッセージをＰＥ１１に送出する。ＥＸ１０でも同様に、ＰＥ１０にこのメッセージが送出される。
【００６４】
ＸＢ−Ｙ０も同様に動作し、結局ＰＥ００、ＰＥ１０、ＰＥ０１、ＰＥ１１にこの部分放送メッセージが送出される。以上説明した通り、１つのプロセッサグループ内に対する部分ブロードキャストが、無駄なデータ転送を生じることなく実現できる。
【００６５】
以上は図１９（ａ）の範囲５０Ａ内の部分ブロードキャストであった。以上の動作と並行して他の範囲５０Ｂ、５０Ｃ内でもメッセージを部分放送できることが以上の説明からも明らかである。
【００６６】
また、図１９（ｂ）の場合の部分放送メッセージの転送経路と、Ｒ０、Ｒ１ビットの値を図２３に示す。この場合には（Ｒ０、Ｒ１）ビットが（０、０）のときＥＸ００、ＥＸ１０がメッセージをＰＥ００、ＰＥ１０に転送するので、ＹＢ−Ｘ０、ＹＢ−Ｘ１には転送されないのが特徴である。つまり一列のＰＥの場合、他の列への無用な転送を防止している。また図１９（ｃ）の場合の転送は、図２４に示す通りである。
【００６７】
以上で部分放送メッセージの転送動作の説明は終える。
【００６８】
なお、放送メッセージの場合には、ルーティングビットＲ０、Ｒ１は使用されず、各ＥＸでは、経路指示回路３０６にてそのメッセージ中のＢＣビットにより特定の方向にこのメッセージを転送する。たとえば図４において、ＰＥから入力された放送メッセージは、ＯＲゲート４１５を介して信号ＰＸを１にし、ＸＢ−Ｘへこのメッセージを転送する。さらにＸＢ−Ｘから放送メッセージがそのＥＸに転送されたときには、図４のＯＲゲート４１９の出力信号ＸＹを１にし、このメッセージをＸＢ−Ｙに転送する。さらに、ＸＢ−Ｙから放送メッセージがそのＥＸに転送されたときには、ＯＲゲート４２３の出力ＹＰを１にし、それによりそのメッセージをＰＥに転送する。一方、各ＸＢでは図６に示すように経路指示回路５０４により、次のように転送方向を制御する。たとえばＥＸ０から入力された放送メッセージは、ＯＲゲート６０９、６１３、６１７、６２１の出力を１にし、それにより、対応するＥＸ０、ＥＸ１、ＥＸ２、ＥＸ３にそのメッセージを転送するようになっている。こうして、前述のＥＸの動作と組みあわさって、放送メッセージはＰＥ００→ＥＸ００→ＸＢ−Ｘ０→ＥＸ００、Ｅ０１、ＥＸ０２、ＥＸ０３→ＸＢ−Ｙ０〜ＸＢ−Ｙ３→ＰＥｉｊというルートで送信元を含めてすべてのＰＥへ転送される。
【００６９】
また、放送メッセージ、部分放送メッセージのいずれでもない通常のメッセージの場合、ＥＸ内のアドレスデコーダ４００〜４０２と、ＸＢ内のアドレスデコーダ群５０によりメッセージ中の送信先ＰＥ番号のＰＥへ選択的に転送される。
【００７０】
〈第２の実施例〉
図９に本実施例の並列計算機の構成を示す。第２の実施例は、第１の実施例の境界レジスタ群７０をなくし、代りに部分放送メッセージ中にそのメッセージを転送する範囲情報を付加し、この情報を用いてＸＢにおいて部分放送範囲を決める所に特徴がある。以下では、第１の実施例との相違点に絞って説明する。
【００７１】
図１２に、プロセッサ間でデータ転送する場合の、本実施例に係るメッセージのフォーマットを示す。メッセージは、図８（ａ）に示したメッセージの送信ＰＥ番号、受信ＰＥ番号、２ビットのルーティングビット（Ｒ０、Ｒ１）、ＣＴＬビット、データに対し、さらに転送制御情報としてＭＡＸ座標、ＭＩＮ座標を付加したものである。ＭＡＸ座標は、メッセージを転送するプロセッサ群の座標の最大Ｙ座標ＹＭＡＸ、最大Ｘ座標ＸＭＡＸからなる。ＭＩＮ座標も同様にＹＭＩＮ、ＸＭＩＮからなる。なお、図１２において部分放送メッセージの場合、送信ＰＥ番号等を用いないのは図８（ｂ）の場合と同様である。
【００７２】
データを転送するために、ＰＥ００では送信するためのメッセージを生成する。図１０はＰＥの構成を示している。図において、図２と同じ参照番号は同じものをさす。図１０では、メッセージ生成回路２０９Ａは、部分放送メッセージを生成するとき、その中にレジスタ２１０、２１１の内容をそのメッセージに含ませる点でのみ図２と異なる。
【００７３】
本実施例におけるＸＢは、部分放送経路指示回路が異なること以外、実施例１と同じである。
【００７４】
図１１に、本実施例による部分放送経路指示回路６０４Ａの構成を示す。この回路に入力される情報が、実施例１の回路６０４（図７）では部分放送メッセージ中のＰＢだけであったのに対し、本実施例では、このメッセージ中のＭＡＸ座標（ＹＭＡＸ、ＸＭＡＸ）、ＭＩＮ座標（ＹＭＩＮ、ＸＭＩＮ）が各転送制御回路７０８〜７１１においてＰＥ座標レジスタ７１２の内容と比較される。これに伴ない実施例１の境界レジスタ群７０は用いられない。その他の点は図７と同じである。
【００７５】
次に図１９（ａ）の場合について、ＰＥ００からの部分放送メッセージをＥＸ００からＸＢ−Ｘ０へ送信したときの部分放送経路指示回路６０４Ａの動作を説明する。この回路６０４Ａの各転送制御回路７０８、７０９、７１０又は７１１では、入力されたメッセージ中のＸＭＡＸ、ＸＭＩＮとＰＥ座標レジスタ７１２中のＰＥ座標を比較する。ＥＸ００から入力された部分放送メッセージの場合、たとえば転送制御回路７０９では比較器７１３、７１４によりＰＥ座標レジスタ７１２の内容（今の例では１）が、このメッセージ中のＸＭＡＸ（今の例では１）、ＸＭＩＮ（今の例では０）の間にあるかが判定される。このメッセージが指定する部分放送範囲に属するＰＥが、この転送制御回路７０９すなわちスイッチ５０１（図５）の下流に接続しているか否かを判定している。本実施例では、信号Ｅ１０が１となり、ＥＸ０１に転送される。その後の動作は実施例１と同じであるので省略する。このような方法によって、図１９（ａ）に示す領域５０Ｂ内のＰＥにはこのメッセージが転送されないことが分かる。
【００７６】
結局、本実施例によっても、部分放送範囲内に属するＰＥ間でメッセージの部分放送を並列に行なうことができ、かつ他の部分放送範囲における部分放送と並列に行ないえる。しかも、本実施例では、実施例１のように境界レジスタ群が不要なだけに、回路がより簡単である。
【００７７】
〈第３の実施例〉
第１の実施例では、転送制御情報として境界レジスタ群７０（図７）にプロセッサグループの範囲を示す座標データを保持した。本実施例では、各ＥＸ、各ＸＢの各出力ポートごとに全入力ポートに対応したデータ送出制御ビットからなる転送制御情報を持ち、そのビットの値によってデータを送出するか否かを制御する。以下では、第１の実施例との相違点に絞って説明する。図１３に本実施例の並列計算機の構成を示す。図において、図１と同じ参照番号は同じものをさす。図１との相違点は各ＰＥ内のルーティングビット生成回路がないことと、各ＥＸ内の部分放送経路指示回路４０３Ｂ〜４０５Ｂに経路指示ビットレジスタ６２８が設けられたことと、各ＸＢ内の境界レジスタ群７０の代りに経路指示ビットレジスタ群７００が設けられ、転送制御回路７０８Ｂ〜７１１Ｂがこのレジスタ群７００内のビットの値により部分放送メッセージの転送を制御するようになっていることである。
【００７８】
図１８に、本実施例に係るメッセージのフォーマットを示す。このメッセージには、図８の場合に比べ、ルーティングビットＲ０、Ｒ１がない。
【００７９】
図１４はＰＥの構成を示している。図において図２と同じ参照番号は同じものをさす。各ＰＥはルーティングビット生成回路２０８（図２）を有しない点で図２と異なるのみである。
【００８０】
各ＥＸは出力ポートと部分放送経路指示回路のみ図３と異なる。図１５に本実施例による出力ポート３０３Ｂの構成を示す。経路指示情報変更回路３１１（図３）を削除した以外は同じである。このことは、他の出力ポート３０４Ｂ、３０５Ｂについても同じである。図１６に、ＰＥからの部分放送メッセージに対する部分放送経路指示回路４０３Ｂの内部の構成を示す。図において、６２８は各送出先に対応する送出制御ビットＲＸ、ＲＹ、ＲＰからなる転送制御情報を保持する経路指示レジスタである。これらの送出制御ビットは、ＰＥに接続された入力ポートから入力された部分放送メッセージに対応する送出先に転送するか否かを示すビットであり、ビットＲＸはＸＢ−Ｘに、ビットＲＹはＸＢ−Ｙに、ビットＲＰはＰＥに、そのメッセージを転送するときに１にされる。これらの送出制御ビットは、事前（プログラムをＰＥにローディングしたときなど）に外部（たとえばホスト計算機またはＳＶＰ１４０）のソフトウェアで算出され設定される。他の入力ポートに対する部分放送経路指示回路４０４Ｂ、４０５Ｂ（図１３）も同様の構成である。
【００８１】
部分ブロードキャストの時、即ちＰＢが１の場合は部分放送経路指示回路４０３Ｂ〜４０５Ｂがそれぞれに設定された送出制御ビットＲＸ、ＲＹ、ＲＰの値によりそのメッセージの送信先を決める。即ち、ＰＢが１かつレジスタ６２８のビットＲＸが１のときはＡＮＤ回路６２５（図１６）の出力Ａが１となるので、ＸＢ−Ｘが送信先となる。ＰＢが１かつレジスタ６２８のビットＲＹが１のときはＡＮＤ回路６２６の出力Ｂが１となるので、ＸＢ−Ｙが送信先となる。ＰＢが１かつレジスタ６２８のビットＲＰが１のときはＡＮＤ回路６２７の出力Ｃが１となるので、ＰＥが送信先となる。たとえば図１９（ａ）の場合、ＥＸ００では、部分放送経路指示回路４０３Ｂではレジスタ６２８のビットＲＸだけが１となっており、ＰＥ００から送られてきた部分放送メッセージは第１の実施例と同様、ＸＢ−Ｘ０に送出される。
【００８２】
本実施例では各ＸＢは、部分放送経路指示回路６０４Ｂのみ実施例１と異なる。図１７にその構成を示す。７２５〜７２８は各入力ポートに対応して、それぞれ設けられ、それぞれは各出力ポートに対応した送出制御ビットを保持する経路指示ビットレジスタである。すなわち、レジスタ７２５はＥＸ０から入力された部分放送メッセージのための送出制御ビットＲ００〜Ｒ０３を持つ。同様に、レジスタ７２６、７２７、７２８はそれぞれＥＸ１、ＥＸ２、ＥＸ３から入力されたメッセージの送出制御ビット（Ｒｉｊ（ｉ＝１〜３、ｊ＝０〜３）を持つ）である。送出制御ビットＲｉｊ（ｉ＝０〜３、ｊ＝０〜３）は対応するｉ番目の入力ポートから入力された部分放送メッセージをｊ番目の出力ポートに転送するか否かを示すビットであり、Ｒ００、Ｒ１０、Ｒ２０、Ｒ３０はそれぞれＥＸ０〜３から入力された部分放送メッセージをＥＸ０に出力するときに１とされる。Ｒ０１、Ｒ１１、Ｒ２１、Ｒ３１はＥＸ０〜３からそれぞれ入力された部分放送メッセージをＥＸ１に転送するときに１にされる。同様にＲ０２、Ｒ１２、Ｒ２２、Ｒ３２はそれぞれＥＸ０〜３から入力された部分放送メッセージをＥＸ２に出力するとき１にされる。Ｒ０３、Ｒ１３、Ｒ２３、Ｒ３３は出力先がそれぞれＥＸ０〜３から入力された部分放送メッセージをＥＸ３に出力するとき１にされる。各転送制御回路７０８Ｂ〜７１１Ｂはこれらのレジスタ７２５〜７２８の内容と異なる入力ポートから入力された部分放送メッセージ内のＰＢビットとの論理積をとる４つのＡＮＤゲートからなる。これらのレジスタ７２５〜７２８は、事前（プログラムをＰＥにローディングしたときなど）に外部（たとえばホスト計算機またはＳＶＰ１４０）のソフトウェアで算出され設定される。ＡＮＤゲート７２９〜７３２の出力信号Ｅ００〜Ｅ０３は、それぞれＥＸ０〜ＥＸ３から入力されたメッセージが部分ブロードキャストである場合に、ＥＸ０にそのメッセージを出力することを示す信号である。同様に、ＡＮＤゲート７３３〜７３６の出力信号Ｅ１０〜Ｅ１３はＥＸ１へ、Ｅ２０〜Ｅ２３はＥＸ２へ、Ｅ３０〜Ｅ３３はＥＸ３へ出力することを示す信号である。
【００８３】
次に、図５、図１７を用いて、図１９（ａ）の場合についてＸＢ−Ｘ０を例としてＸＢ−Ｘの動作を説明する。図１７の部分放送経路指示回路６０４Ｂでは、ＸＢ−Ｘ０内のレジスタ７２５のＲ００〜Ｒ０３に予め１、１、０、０がセットされている。これはＰＥ００からの部分放送メッセージは図１９（ａ）の場合、ＰＥ００、ＰＥ０１には送るがＰＥ０２、ＰＥ０３には送らないようにするためである。このためＡＮＤ回路７２９、７３３、７３７、７４１でそれぞれレジスタ７２５の値とＰＢの論理積がとられ、出力信号Ｅ００、Ｅ１０がともに１となるがＥ２０、Ｅ３０は０のままである。この後は実施例１と同じ動作にしたがって２つのスイッチ５００、５０１（図５）によりＥＸ００から入力されたメッセージが選ばれ、ＥＸ００、ＥＸ０１に送られる。しかしＥＸ０２、ＥＸ０３には送られない。
【００８４】
ＸＢ−Ｘ０に接続されているＥＸ００〜ＥＸ０１では、この転送された部分放送メッセージに対して全て同様の動作を行なう。ここでは、ＥＸ０１を例にとる。ＥＸ０１は、ＥＸ０１のこのＸＢ−Ｘ０に対応する部分放送経路指示回路４０４Ｂ（図１３）ではその中の経路指示ビットレジスタ６２８にはビットＲＸ、ＲＹ、ＲＰとしてそれぞれに０、１、０が予めセットされている。これは、図２２に例示したように、図１９（ａ）の場合、ＸＢ−Ｘ０から転送された部分放送メッセージは、ＹＢ−Ｙ１に転送する必要があるからである。これらのビットはＡＮＤ回路６２５〜６２７にて入力メッセージ中のＰＢと論理積がとられる。その結果出力信号Ｂだけが１となる。このためＸＢ−Ｘ０から送られてきた部分放送メッセージは、ＥＸ０１によってＸＢ−Ｙ１に送られる。同様にＥＸ００も、ＸＢ−Ｙ０にメッセージを送り出す。
【００８５】
次に、図５、図１７を用いて、このメッセージに対するＸＢ−Ｙ１の動作を説明する。本実施例のＸＢ−Ｙ１では、経路指示ビットレジスタ７２５のＲ００〜Ｒ０３に予め１、１、０、０がセットされている。これは、ＥＸ０１からＹＢ−Ｙ１に転送されてきた部分放送メッセージをＰＥ０１、ＰＥ１１には転送するがＰＥ２１、ＰＥ３１には転送しないためである。このためＡＮＤ回路７２９、７３３、７３７、７４１でそれぞれレジスタ７２５の値とＰＢの論理積がとられ、出力信号Ｅ００、Ｅ１０に１が、Ｅ２０、Ｅ３０に０が出力される。この後は実施例１と同じ動作により、ＸＢ−Ｙ１内の２つのスイッチ５００および５０１（図５）により、ＥＸ０１から入力された部分放送メッセージが選ばれ、ＥＸ０１、ＥＸ１１へ送られる。またＥＸ２１、ＥＸ３１へはこのメッセージは送り出されない。
【００８６】
ＸＢ−Ｙ１からこのメッセージを取り込んだＥＸ０１とＥＸ１１は、同じ動作を行なう。ここではＥＸ１１を例にとる。ＥＸ１１では、このＸＢ−Ｙ１に対応する部分放送経路指示回路４０５Ｂ（図１３）では、レジスタ６２８にはビットＲＸ、ＲＹ、ＲＰそれぞれに０、０、１が予めセットされている。これは、図２２に例示したように、ＥＸ１１ではＸＢ−Ｙ１から入力された部分放送メッセージをＰＥ１１へのみ転送する必要があるからである。図１６ではＡＮＤ回路６２５〜６２７にてＰＢとこれらのビットとの論理積がとられ出力信号Ｃだけが１となる。このためＸＢ−Ｙ１から送られてきた部分放送メッセージは、ＥＸ１１によってＰＥ１１に送られる。ＥＸ０１でも同様に、ＰＥ０１にこのメッセージが送出される。ＸＢ−Ｙ０でも同様に動作し、結局ＰＥ００、ＰＥ１０、ＰＥ０１、ＰＥ１１にメッセージが送出される。
【００８７】
以上、メッセージの転送先を限定するための送出制御ビットにより１つのプロセッサグループ内のＰＥだけにメッセージを転送する部分ブロードキャストが、無駄なデータ転送を生じることなく実現できる。
【００８８】
実施例１又は２では、プロセッサグループの範囲として矩形を仮定しているが、本実施例のごとくデータの送出制御ビットを用いれば、任意の形状の範囲のプロセッサグループを指定することができる。また、実施例１あるいは２に必要な多数の比較回路をＸＢに設ける必要がなく回路の小型化を図れる。
【００８９】
〈変形例〉
（１）実施例１において、複数の部分放送範囲が固定していてもよい場合、図７の境界レジスタ群７０の内、同一の部分放送範囲に属する複数の入力ポートに対して一対の境界レジスタを用いることができる。
【００９０】
（２）さらに実施例１において、部分放送の範囲が並列計算機の中で一つに限定してもよいときには、境界レジスタ群７０はその一つの範囲を示す一対のレジスタでよい。
【００９１】
（３）実施例１においては、各出力ポートに、複数の入力ポートの一つにそれぞれ対応する複数対の境界レジスタを設けたが、次のように変形することも可能である。たとえば、図７において、境界レジスタ７０の代りにこの並列計算機システム内で持ちうる最大の部分放送範囲の数に等しい境界レジスタ対を設け、各対には、対応する部分放送範囲を表わす最大Ｙ座標とＸ座標を記憶しておくとともに、図７の転送制御回路７０８〜７１１とこのレジスタ対との間に各入力ポートが、これらのレジスタ対のいずれの一つの対により表わされるかを表わす識別ビットを保持するレジスタと、このレジスタ内の識別ビットにより上記レジスタ対の一つを選択して転送制御回路７０８〜７１１に送出する回路を設けてもよい。実施例１では、境界レジスタ群として、各クロスバスイッチの入力ポートの数の２倍の数のレジスタが各クロスバスイッチに必要であるが、この変形例によれば、部分放送の範囲数の２倍のレジスタがあればよいので、部分放送範囲が少ないときに回路が少なくてすむ。
【００９２】
（４）実施例１の境界レジスタ群７０の代りに、並列計算機で使用されうる複数の部分放送範囲をそれぞれ示す複数対の境界レジスタを出力ポートに対応して設ける。実施例１では一つの部分放送メッセージに対して各クロスバスイッチ内のスイッチ５００〜５０３（図５）を選択的にオンにしたが、これにかえ、まず、これらのスイッチをすべてこの部分放送メッセージに対してオンにしてから、それぞれのスイッチの出力側に別のゲートを設け、そのゲートを開閉するか否かを制御する部分放送経路指示回路を設けることも可能である。この方法では、この部分放送経路指示回路は、各スイッチの出力側に、この並列計算機で使用する複数の部分放送範囲のいずれかに属するＰＥがあるかを判断して、そのスイッチの出力側のゲートを制御すればよい。そのためには、そのスイッチに対応して、すなわち出力ポートに対応して、それらの複数の部分放送範囲を示す境界レジスタ群を設け、その出力ポートに接続されるＰＥの座標とそれらの境界レジスタ群とから、そのＰＥが上記複数の部分放送範囲のいずれかに属するか否かを判断する転送制御回路を設ければよい。この変形によると、境界レジスタ群は上記変形（３）の場合と同じ数でよく、実施例１より少なくてすむ。勿論この方法によれば、ＸＢの各スイッチが転送しない可能性がありながら部分放送メッセージを選択するので、その間、実施例１では選択されうる他のメッセージを選択できないという欠点があり、実施例１はその点ですぐれている。
【００９３】
（５）実施例１及び２において、各ＰＥに保持していた部分放送の範囲を示す座標を、各ＥＸに保持することもできる。すなわち、ルーティングビット生成回路２０８（図２）を各ＥＸに持つ。部分ブロードキャストの場合、実施例１では送信元ＰＥに対応するＥＸでＲ０、Ｒ１をメッセージに付加し、また実施例２では送信元ＰＥに対応するＥＸでＲ０、Ｒ１、ＭＡＸ座標、ＭＩＮ座標をメッセージに付加する。この変形により、部分ブロードキャストによる回路追加をＥＸ及びＸＢのスイッチ回路だけに行なえばよく、ＰＥの回路変更は必要ない。
【００９４】
（６）実施例１〜３とも部分放送経路指示回路内に複数の転送制御回路を設けたが、一つの転送制御回路により順次異なる境界レジスタ対を用いて判定するようにしてもよい。
【００９５】
（７）実施例１〜３とも二次元のクロスバスイッチからなるネットワークを示したが、これは三次元以上のものでもよい。
【００９６】
（８）さらにクロスバスイッチに限らず、たとえば多段スイッチからなるネットワークを用いてもよい。
【００９７】
〈応用例〉
ホスト計算機１４０またはあるプロセッサからそれが属さないプロセッサグループへ部分ブロードキャストしたいとき、たとえば図１９（ａ）の場合ＰＥ００からＰＥ２０〜ＰＥ２３およびＰＥ３０〜ＰＥ３３からなる範囲５０Ｃへ部分ブロードキャストしたいときは、ＰＥ００で実行中のプログラムによりその範囲５０Ｃの一つのＰＥたとえばＰＥ２０へそのことを要求する通常のメッセージを転送し、ＰＥ２０からＰＥ２０〜ＰＥ２３およびＰＥ３０〜ＰＥ３３へ部分ブロードキャストすることで実現する。またあるＰＥがそれが属さない２つ以上のプロセッサグループに部分放送をしたいとき、たとえばＰＥ００から図１９（ａ）の範囲５０Ｂ、５０Ｃへ部分ブロードキャストしたいときは、ＰＥ００のこのプログラムによりそれぞれの範囲内のＰＥたとえばＰＥ０２とＰＥ２０へそのことを要求する通常メッセージを転送し、ＰＥ０２とＰＥ２０から範囲５０Ｂ、５０Ｃ内で部分ブロードキャストすればよい。また、実施例１又は２を用い部分ブロードキャストを矩形でないプロセッサ範囲に行ないたい場合、この範囲を複数の矩形の領域に分け、それぞれ内の一つのＰＥに上述のごとく部分放送を依頼する方法を用いればよい。
【００９８】
【発明の効果】
本発明によれば、並列計算機において全プロセッサのうちの一部プロセッサにメッセージを選択的に、かつ、並列に転送できる。
【図面の簡単な説明】
【図１】本発明の実施例１による並列計算機の構成図である。
【図２】図１に示すプロセッサエレメント（ＰＥ）の構成図である。
【図３】図１の中の中継スイッチ（ＥＸ）の構成図である。
【図４】図３の中の経路指定回路の構成図である。
【図５】図１のクロスバスイッチ（ＸＢ）の構成図である。
【図６】図５の中の経路指示回路の構成図である。
【図７】図６の中の部分放送経路指示回路の構成図である。
【図８】第１の実施例に用いるメッセージのフォーマットの図である。
【図９】本発明の第２の実施例における並列計算機の構成図である。
【図１０】図９に示すプロセッサエレメント（ＰＥ）の構成図である。
【図１１】図９の中の部分放送経路指示回路の構成図である。
【図１２】第２の実施例に用いるメッセージのフォーマットの図である。
【図１３】本発明の第３の実施例の並列計算機の構成図である。
【図１４】図１３に示すＰＥの構成図である。
【図１５】図１３の中の中継スイッチ中の出力ポート（ＥＸ）の構成図である。
【図１６】図１３の中継スイッチ（ＥＸ）の中の部分放送経路指示回路の構成図である。
【図１７】図５の中のクロスバスイッチ（ＸＢ）の中の部分放送経路指示回路の構成図である。
【図１８】第３の実施例のメッセージのフォーマットの図である。
【図１９】複数の部分放送範囲を示す図である。
【図２０】部分放送範囲の形状と送信元（ＰＥ）で生成されるルーティングビットＲ０、Ｒ１との関係を示す図である。
【図２１】図１の中継スイッチ（ＥＸ）の動作とルーティングビットＲ０、Ｒ１との関係を示す図である。
【図２２】図１９（ａ）の部分放送範囲に対する部分放送メッセージの転送経路を示す図である。
【図２３】図１９（ｂ）の部分放送範囲に対する部分放送メッセージの転送経路を示す図である。
【図２４】図１９（ｃ）の部分放送範囲に対する部分放送メッセージの転送経路を示す図である。
【符号の説明】
１００…プロセッサ、１１６…中継スイッチ、１３２〜１３９…クロスバスイッチ、２０８…ルーティングビット生成回路、３１１…経路指示情報変更回路、４０３〜４０５…部分放送経路指示回路、６０４…部分放送経路指示回路、７０…境界レジスタ群、７０８〜７１１…転送制御回路。
【図１】
0003679813.tif 000002
【図２】
0003679813.tif 000003
【図３】
0003679813.tif 000004
【図４】
0003679813.tif 000005
【図５】
0003679813.tif 000006
【図６】
0003679813.tif 000007
【図７】
0003679813.tif 000008
【図８】
0003679813.tif 000009
【図９】
0003679813.tif 000010
【図１０】
0003679813.tif 000011
【図１１】
0003679813.tif 000012
【図１２】
0003679813.tif 000013
【図１３】
0003679813.tif 000014
【図１４】
0003679813.tif 000015
【図１５】
0003679813.tif 000016
【図１６】
0003679813.tif 000017
【図１７】
0003679813.tif 000018
【図１８】
0003679813.tif 000019
【図１９】
0003679813.tif 000020
【図２０】
0003679813.tif 000021
【図２１】
0003679813.tif 000022
【図２２】
0003679813.tif 000023
【図２３】
0003679813.tif 000024
【図２４】
0003679813.tif 000025