(57)【要約】【課題】並列計算機やクラスタ計算機を構成するマトリックススイッチの通過時間を、経路履歴によって調停する調停回路をクロスポイントのネットワーク回路に備えるマトリックススイッチをもつ処理システムにある。【解決手段】情報処理システム１は、マトリックススイッチ５で接続され、マトリックススイッチ５内の経路情報及び経路履歴と、を含む通信情報を発行先に送出する処理部２１と、４方向の入力端子及び出力端子を有するネットワーク回路５ｋｌをマトリックスに接続して構成するマトリックススイッチ５と、を備え、ネットワーク回路５ｋｌに通信情報の競合を調停する調停回路５０３１を備える。【選択図】　　　図１
2004086304.tif 000002
【特許請求の範囲】
【請求項１】
演算装置，メモリ装置，周辺装置，通信装置を表す処理部をマトリックススイッチに接続し、前記処理部間で通信情報を前記マトリックススイッチを介して送受する情報処理システムにおいて、
前記マトリックススイッチに接続し、前記マトリックススイッチ内の経路情報及び経路履歴並びに命令及びデータを記載する通信情報を、発行先の処理部に送出する、あるいは発行元の処理部から受け付ける処理部と、
４方向の入力端子及び出力端子を有するネットワーク回路をマトリックスに接続し、前記処理部を前記マトリックスの周辺に接続してなるマトリックススイッチと、を備え、
前記ネットワーク回路は、
４方向から入力する通信情報をそれぞれに受け付け、前記通信情報を一時記憶し、前記通信情報の発行先への最短経路の出力方向を前記経路情報によって選択する４つの受付回路と、
選択された出力方向に対する１つ以上の競合する通信情報の前記経路履歴を参照する履歴参照回路と、
前記経路履歴の参照結果に基づいて、前記通信情報の競合を調停する調停回路と、
前記通信情報の経路情報及び経路履歴を更新する履歴更新回路と、
前記通信情報を発行先への前記最短経路の出力端子に送出する送出回路と、
を有することを特徴とする調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項２】
前記マトリックススイッチは、
Ｘ方向に１以上のＭ個のネットワーク回路を接続し、Ｙ方向に１以上のＮ個のネットワーク回路を接続して、マトリックススイッチを形成することを特徴とする請求項１記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項３】
前記受付回路は、
入力する通信情報を一時記憶する手段を備えることを特徴とする請求項１記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項４】
前記受付回路は、
前記マトリックススイッチ内を経由するネットワーク回路の数が最小になる最短経路の出力端子を前記経路情報によって選択する手段を備えることを特徴とする請求項１記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項５】
前記履歴更新回路は、
前記ネットワーク回路の通過数をカウントして経路履歴に、前記ネットワーク回路の通過を示す識別を経路情報に、それぞれ更新する手段を備えることを特徴とする請求項１記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項６】
前記調停回路は、
前記経路履歴のカウント値が大きい順に優先させ、前記カウント値が同一である通信情報が複数あるとき、所定の基準によって優先順位を判定する調停手段を備えることを特徴とする請求項１記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項７】
前記経路情報は、
通信情報を発行する処理部が記述する、発行先に至る最短経路を経路のネットワーク回路から出力する左右のＸ方向と上下のＹ方向のデータと、通過したことを示す通過識別と、で表すデータ列であることを特徴とする請求項１及び請求項４及び請求項５及び請求項６記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【請求項８】
前記経路履歴は、
前記通信情報が通過したネットワーク回路数を表すカウント値であることを特徴とする請求項１及び請求項５記載の調停回路付きマトリックススイッチをもつ情報処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、演算装置，メモリ装置，周辺装置，通信装置をマトリックススイッチで接続する並列計算機あるいはクラスタプロセッサの処理システムに関し、特に、マトリックススイッチを構成するネットワーク回路に、経路履歴に基づいて競合を制御する調停回路を付加した調停回路付きマトリックススイッチをもつ情報処理システムに関する。
【０００２】
【従来の技術】
複数の演算装置，メモリ装置，周辺装置，通信装置、を表す処理部をクロスバースイッチやマトリックススイッチやバス等で接続して処理システムを構成する形態を並列計算機あるいはクラスタプロセッサと呼び、最近、この構成を採る処理システムが増えている。処理部が協同するため、処理部間の通信がマトリックススイッチを通じて実行されるとき、マトリックススイッチのクロスポイントで通信が競合することがある。この競合を調停する手段をマトリックススイッチのクロスポイントに設ける方式と、予め競合が生じないような経路をマトリックススイッチ上に選択する方式と、がある。
【０００３】
特開２０００−２９３４９５号公報によれば、多段接続のクロスバースイッチを配置してなるネットワーク装置で、ノードに生じる通過データの競合を調停する調停回路をクロスバースイッチに設けている。調停回路は、データのヘッダ部と、ルーティングコントロール部をみて、経路指定で指定された出力ポートに該データを転送する。出力ポートの競合に対して、優先判定がなされる。判定基準は、固定方式，サイクリック方式などによってなされ、この判定で通過データを選択する切り替え信号を出力する発明である。この発明におけるクロスバースイッチを通過するたびにカウントアップされる経路カウントは、競合情報の数を記録して経路の選択に用いるもので、競合に対する優先順を決定するためのものではない。
【０００４】
更に、特開２００１−２４６４１号公報によれば、クロスバースイッチのアービタにおける接続許可システムを開示している。この開示によれば、アービタが入力回線ごとのＦＩＦＯを優先順位で選択し、候補のＦＩＦＯを比較して、調停する発明である。したがって、クロスバースイッチの経路途中における競合を調停するものではない。
【０００５】
更に、特開平１１−１５０５３３号公報によれば、ネットワークスイッチ装置の複数の送信側ノードと複数の受信側との間を相互接続するとき、リクエストを予め与えられている優先順位によって選択し、経路を確定する発明を開示している。したがって、経路途上に生じるクロスポイントの競合を解消するものではない。
【０００６】
更に、特開平１０−２６２０６７号公報によれば、通信装置がネットワークにパケットを送信するとき、該パケットに送信カウントを付加し、通信装置が送信カウント数で定まる優先順に基づく時間をウエイトして、ネットワークの空きを待つ発明を開示している。これによれば、通信装置の優先順位に従った待ち時間でネットワークの空きを監視して、パケットを送信するのであるから、競合を減らすことを行うのであって、調停するものではない。
【０００７】
【発明が解決しようとする課題】
従来の、マトリックススイッチにおける調停方式では、経路上のクロスポイントにける調停の優先順位を適応的に制御することではない。したがって、通過するクロスポイントで、固定的な優先順による制御を受けると、多くのクロスポイントを通過する通信情報である程、途中における競合の影響を受けて待たされる、あるいは迂回させられて、経路の通過時間が長くなる傾向が生じる。
【０００８】
そこで、通信情報に通過したクロスポイントの数を記憶させる経路履歴を保持させる。その数で優先順を適応的に制御する。つまり、長い経路を伝播する通信情報ほど、高い優先順位を持たせて、競合時に優先して通過させることにより、通信情報のマトリクススイッチの通過時間を全体として平準化し、短縮する。
【０００９】
更に、マトリックススイッチ上の経路は、発行元と発行先とによって、通過しなければならないクロスポイントの最小数が決定されるので、それが最短経路における通過クロスポイント数になる。最短経路は、複数あり得るので、通過するクロスポイントの出力端子を左右のＸ方向と、上下のＹ方向と、で表して経路情報とし、発行元の処理部でプログラムし、特定経路に集中することを回避できる。
【００１０】
更に、同一の出力端子に同一順位の通信情報が競合したとき、所定の基準で判定する。例えば、残る経路が長い方を優先させる。更に、同一順位で、残る経路長が同じ場合は、クロスポイントに入力する方向に与えられている優先順位で、出力端子の出力順を決定する。上述の調停の結果、通過待ちになる通信情報は、クロスポイントに設ける一時記憶にホールドされ、優先する通信情報の通過後に出力端子に出力する。
【００１１】
この発明の目的は、通過するネットワーク回路の数に比例して調停での優先度を上げることにより、多数のネットワーク回路を渡る通信情報のマトリックススイッチの通過時間を短縮して平準化することにある。
【００１２】
更に、他の目的は、通信情報の経路情報によって、最短経路をプログラムすることにより、通過する途中経路を複数化して特定経路の集中を回避する。
【００１３】
【課題を解決するための手段】
そのため、この発明の、演算装置，メモリ装置，周辺装置，通信装置を表す処理部をマトリックススイッチに接続し、前記処理部間で通信情報を前記マトリックススイッチを介して送受する情報処理システムにおいて、前記マトリックススイッチに接続し、前記マトリックススイッチ内の経路情報及び経路履歴並びに命令及びデータを記載する通信情報を、発行先の処理部に送出する、あるいは発行元の処理部から受け付ける処理部と、４方向の入力端子及び出力端子を有するネットワーク回路をマトリックスに接続し、前記処理部を前記マトリックスの周辺に接続してなるマトリックススイッチと、を備え、前記ネットワーク回路は、４方向から入力する通信情報をそれぞれに受け付け、前記通信情報を一時記憶し、前記通信情報の発行先への最短経路の出力方向を前記経路情報によって選択する４つの受付回路と、選択された出力方向に対する１つ以上の競合する通信情報の前記経路履歴を参照する履歴参照回路と、前記経路履歴の参照結果に基づいて、前記通信情報の競合を調停する調停回路と、前記通信情報の経路情報及び経路履歴を更新する履歴更新回路と、前記通信情報を発行先への前記最短経路の出力端子に送出する送出回路と、を有することを特徴とする。
【００１４】
更に、前記マトリックススイッチは、Ｘ方向に１以上のＭ個のネットワーク回路を接続し、Ｙ方向に１以上のＮ個のネットワーク回路を接続して、マトリックススイッチを形成することを特徴とする。
【００１５】
更に、前記受付回路は、入力する通信情報を一時記憶する手段を備えることを特徴とする。
【００１６】
更に、前記受付回路は、前記マトリックススイッチ内を経由するネットワーク回路の数が最小になる最短経路の出力端子を前記経路情報によって選択する手段を備えることを特徴とする。
【００１７】
更に、前記履歴更新回路は、前記ネットワーク回路の通過数をカウントして経路履歴に、前記ネットワーク回路の通過を示す識別を経路情報に、それぞれ更新する手段を備えることを特徴とする。
【００１８】
更に、前記調停回路は、前記経路履歴のカウント値が大きい順に優先させ、前記カウント値が同一である通信情報が複数あるとき、所定の基準によって優先順位を判定する調停手段を備えることを特徴とする。
【００１９】
更に、前記経路情報は、通信情報を発行する処理部が記述する、発行先に至る最短経路を経路のネットワーク回路から出力する左右のＸ方向と上下のＹ方向のデータと、通過したことを示す通過識別と、で表すデータ列であることを特徴とする。
【００２０】
更に、前記経路履歴は、前記通信情報が通過したネットワーク回路数を表すカウント値であることを特徴とする。
【００２１】
【発明の実施の形態】
この発明の実施の形態について図面を参照して説明する。調停回路付きマトリックススイッチをもつ処理システム１の一実施例を示す図１を参照すると、マトリックススイッチ５の周辺に、演算部，メモリ装置，周辺装置，通信装置等を表す構成要素である処理部１１乃至処理部１ｎ，処理部２１乃至処理部２ｍ，処理部３１乃至処理部３ｎ，処理部４１乃至処理部４ｍを配置して接続する。マトリックススイッチ５は、ネットワークを構成する回路要素をＮ行Ｍ列に接続する。この回路要素をネットワーク回路５１１乃至ネットワーク回路５ｎｍで示す。
【００２２】
ネットワーク回路５ｋｌの接続を示す図２を参照すると、ネットワーク回路５ｋｌは、左右のＸ方向及び上下のＹ方向の４組の入力端子及び出力端子によって、ネットワーク回路５ｋｌ−１，ネットワーク回路５ｋ＋１ｌ，ネットワーク回路５ｋｌ＋１，ネットワーク回路５ｋ−１ｌのそれぞれの入力端子及び出力端子に接続して、マトリックススイッチ５を形成する。
【００２３】
ネットワーク回路５ｋｌの構成の構成を示す図３を参照すると、ネットワーク回路５ｋｌは、４つの入力端子からの通信情報受け付ける４つの受付回路５０１１乃至受付回路５０１４を備え、経路情報５０を解析して得られる出力方向の履歴参照回路５０２１乃至履歴参照回路５０２４に接続し、調停によって通信情報が保留される場合の一時記憶手段を備える。
【００２４】
４つの履歴参照回路５０２１乃至履歴参照回路５０２４は、４つの入力端子から入力する通信情報が同一の出力方向で競合する場合、競合を調停するために競合する通信情報の経路履歴を参照する。
【００２５】
同一出力方向の競合を調停する４つの調停回路５０３１乃至調停回路５０３４は、所定の基準によって競合を調停する。該基準は、経路履歴のカウント値の大きい順に優先を判定する。更に、同一カウント値で競合するときは、例えば、発行先の遠さの順と、同一の遠さに対しては所定の入力方向と、を組み合わせて調停する。調停回路５０４１乃至調停回路５０４４の出力は、それぞれ出力方向の４つの送出回路５０５１乃至送出回路５０５４に送付する。
【００２６】
処理部が発行する通信情報に記載される経路情報を示す図４（ａ）を参照すると、発行元の処理部が接続するネットワーク回路番号５０１と、発行先の処理部が接続するネットワーク回路番号５０２と、選択した最短経路の進行方向をネットワーク回路の出力端子で示す上下方向の＋Ｙ，−Ｙ，左右方向の＋Ｘ，−Ｘの識別５０３と、該ネットワーク回路を通過したことを示す通過識別５０４と、を通過する経路のネットワーク回路に渡って記述したデータ列である。
【００２７】
通信情報が発行元の処理部からマトリックススイッチ５上を通過したネットワーク回路数をカウントして記録する経路履歴６０を示す図４（ｂ）を参照すると、通信情報の識別子６０１と、通過したネットワーク回路毎にカウントされるカウント値６０２と、を含む。
【００２８】
次に、ネットワーク回路５ｋｌにおける入出力及び調停の動作を説明する。図５を参照すると、ネットワーク回路５ｋｌの受付回路５０１１乃至５０１４が入力した通信情報の経路情報５０を参照して、出力方向を示すＸＹの記号と通過識別とに基づいて、出力方向の出力端子を選択する（ステップ７０１）。同一の出力端子に複数の通信情報があるか否かを判定し、競合がない、つまり、出力する通信情報が１つであるとき（ステップ７０２のＮ）、該出力端子に、経路情報の通過識別及び経路履歴のカウント値を更新して、出力する（ステップ７０６）。同一の出力端子に競合があるとき（ステップ７０２のＹ）、通信情報の経路履歴６０を参照して、カウント値の大きい順に優先順位を付ける（ステップ７０３）。該カウント値に、同一の値があるか否かを判定し、同一のカウント値がないとき（ステップ７０４のＮ）、優先順に出力端子に出力する（ステップ７０６）。同一のカウント値があるとき（ステップ７０４のＹ）、所定の優先規準によって判定する（ステップ７０５）。所定の優先規準は、例えば、経路情報５０を参照して、発行先のネットワーク回路番号と通過中のネットワーク回路番号とによって、発行先が遠方になる通信情報を優先させる、あるいは、通信情報の入力方向に優先順位を与える、ことを組み合わせて判定し（ステップ７０５）、選択した出力端子に出力す（ステップ７０６）。
【００２９】
次に、この実施例の動作の具体例を図６を参照して説明する。処理部２２が発行した通信情報Ａは、ネットワーク回路５１２，５１３，５２３，５２４，５３４、５３５，５４５，５４６を、経路情報５０で指定された方向に従って、マトリックススイッチ５上を通過する。一方、処理部２５が発行した通信情報Ｂは、経路情報５０で指定する出力方向に従って、ネットワーク回路５１５，５２５，５３５、５４５とマトリックススイッチ５上を通過する。この２つの通信情報Ａ，Ｂは、ネットワーク回路５３５の下向きのＹ方向の出力端子で競合する。
【００３０】
ネットワーク回路５３５の調停回路は、２つの通信情報Ａ，Ｂの経路履歴を判定する。該判定では、処理部２２が発行した通信情報Ａの経路履歴のカウント値が５であり、処理部２５が発行した通信情報Ｂの経路履歴のカウント値が２であるから、処理部２２の通信情報Ａが優先して、ネットワーク回路５４５に出力する。処理部２５の通信情報Ｂは、ネットワーク回路５３５で一記憶で保留された後、ネットワーク回路５４５に出力する。ネットワーク回路５４５においては、通信情報Ａと通信情報Ｂとではタイミングがずれるため、競合が回避される。
【００３１】
マトリックススイッチ５上の一連の動作を、タイミングチャートに示した図７を参照すると、通信情報Ａと通信情報Ｂとは、タイミングＴ７で、ネットワーク回路５３５で同一方向に出力するため競合する。両者の経路履歴の大きさで、通信情報Ａが優先し、通信情報Ｂが一時記憶されて、タイミングがずらされるので、ネットワーク回路５４５では、通信情報Ａと通信情報Ｂとは、タイミングＴ８とＴ９にずれるので、競合が回避されている。
【００３２】
【発明の効果】
この発明の効果は、マトリクススイッチ上を渡る通信情報の通過時間を平準化し、かつ短縮できることである。その理由は、通信情報がネットワーク回路を通過する毎に更新する経路履歴でカウント値が大きい、つまり経路履歴が長い方を優先して次段のネットワーク回路に出力するため、経路履歴が長いほど、優先順位が上がり、途中で待たされることがなくなり、時間を短縮できるからである。
【００３３】
更に、他の効果は、マトリックススイッチ上のネットワーク回路を平準して使用できるため、特定の経路に通信情報が集中して競合することを回避できることである。その理由は、複数ある最短経路の経路情報を発行元の処理部がプログラムできるからである。
【図面の簡単な説明】
【図１】この発明の調停回路付きマトリックススイッチをもつ処理システムの一実施例の構成を示す図である。
【図２】マトリックススイッチの構成要素であるネットワーク回路の接続関係を示す図である。
【図３】ネットワーク回路の構成を示す図である。
【図４】分図（ａ）は経路情報の構成を、分図（ｂ）は経路履歴の構成を、それぞれ示す図である。
【図５】ネットワーク回路の調停で選択される優先順位の決定する処理を示すフローチャートである。
【図６】マトリックススイッチ上を渡る通信情報の例示である。
【図７】図６の例示をタイムチャートで示す図である。
【符号の説明】
１　　調停回路付きマトリックススイッチをもつ処理システム
５　　マトリックススイッチ
１１乃至１ｎ　　処理部
２１乃至２ｍ　　処理部
３１乃至３ｎ　　処理部
４１乃至４ｍ　　処理部
５０　　経路情報
６０　　経路履歴
５０１１乃至５０１４　　受付回路
５０２１乃至５０２４　　履歴参照回路
５０３１乃至５０３４　　調停回路
５０４１乃至５０４４　　履歴更新回路
５０５１乃至５０５４　　送出回路
【図１】
2004086304.tif 000003
【図２】
2004086304.tif 000004
【図３】
2004086304.tif 000005
【図４】
2004086304.tif 000006
【図５】
2004086304.tif 000007
【図６】
2004086304.tif 000008
【図７】
2004086304.tif 000009