データ転送システム、スイッチ及びデータ転送方法プロセッサ間ネットワーク
【課題】プロセッサ間で転送するパケットの転送時間の偏りを低減することができるデータ転送システム、スイッチ及びデータ転送方法を提供すること。
【解決手段】本発明にかかるデータ転送システムは、複数のプロセッサと、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部２０を備える。データ転送部２０は、次の転送先が同じ競合データについて調停を実行する調停手段２５９と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段２６０を有する。調停手段２５９は、調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する。
【解決手段】本発明にかかるデータ転送システムは、複数のプロセッサと、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部２０を備える。データ転送部２０は、次の転送先が同じ競合データについて調停を実行する調停手段２５９と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段２６０を有する。調停手段２５９は、調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ転送システム、スイッチ及びデータ転送方法に関し、特に、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を実行する技術に関する。
【背景技術】
【０００２】
並列コンピュータのプロセッサ間ネットワークとして、Ｆａｔ Ｔｒｅｅが非特許文献１に開示されている。Ｆａｔ Ｔｒｅｅの例として、４入力４出力のスイッチ１５０１で構成された１６入力１６出力のＦａｔ Ｔｒｅｅネットワークを図１９に示す。スイッチ１５０１間の信号線１５０２は双方向リンクを意味している。Ｆａｔ Ｔｒｅｅにプロセッサ０〜プロセッサ１５までの１６個のプロセッサ１５０３が接続されている。なお、図１９では、スイッチ、プロセッサ及び信号線のそれぞれは、１つを除き符号の図示を省略している。
【０００３】
次にＦａｔ Ｔｒｅｅでのルーティングの例を図２０に示す。スイッチ１５０１は、パケットが上方向へＦａｔ Ｔｒｅｅを上る時は入力ポートの対向の出力ポートを使うルーティングを行う。Ｆａｔ Ｔｒｅｅでは、パケットは、送り元プロセッサと宛先プロセッサの共通のスイッチまでＦａｔ Ｔｒｅｅを上り、共通のスイッチまで上がって折り返して下に降りる。たとえば、プロセッサ４(１６０１)からプロセッサ１５(１６０２)への通信は、スイッチＡ(１６０３)が共通のスイッチになる。そのため、パケットは、スイッチＡ(１６０３)まで上がって折り返す。プロセッサ０(１６０４)からプロセッサ３(１６０５)への通信は、スイッチＢ(１６０６)が共通のスイッチになる。そのため、パケットは、スイッチＢ(１６０６)まで上がって折り返す。共通のスイッチは、パケットがＦａｔ Ｔｒｅｅを上がっていく時に各スイッチによって行われるルーティングによって変わる。しかし、どこまで（何段目まで）上がるかは、送り元プロセッサと送り先プロセッサによって決まり、ルーティングによって変わらない。
【０００４】
従って、ある送り先プロセッサへ通信する場合、何個のスイッチを経由するかは送り元プロセッサによって異なってくる。たとえば、パケットをプロセッサ１５(１６０２)へ送る場合、プロセッサ１４(１６０７)から送ったパケットはスイッチＣ(１６０５)１個を経由するだけでプロセッサ１５(１６０２)に到着する。プロセッサ１２(１６０９)とプロセッサ１３(１６１０)から送ったパケットは、スイッチを３個経由してプロセッサ１５(１６０２)に到着する。パケットをプロセッサ０〜プロセッサ１１から送った場合は、パケットがスイッチ５個を経由してプロセッサ１５(１６０２)に到着する。ここで、Ｆａｔ Ｔｒｅｅを上がっていくパケットのルーティングは入力ポートの対向の出力ポートを使用することにしている。そのため、パケットがＦａｔ Ｔｒｅｅを上がっていく時には、スイッチでパケットの競合は発生しない。パケットがＦａｔ Ｔｒｅｅを下っていく時にスイッチでパケットの競合が発生する。
【０００５】
図２１にスイッチの構成の一例を示す。スイッチは、各入力ポート１７０２〜１７０５と各出力ポート１７０６〜１７０９にはＦＩＦＯ(First In First Out)メモリ１７１０〜１７１７がある。ＦＩＦＯメモリ１７１０〜１７１７は、クロスバスイッチ１７１８によって相互に接続されている。同じ出力ポート行きのパケットが複数の入力ポートから来た場合には、パケットが競合することになる。パケットが競合した場合、クロスバスイッチ１７１８において調停回路１７１９によって１つの入力ポートから入力されたパケットが選ばれる。選ばれたパケットは、クロスバスイッチ１７１８を抜けて、出力ポート１７０６〜１７０９のＦＩＦＯメモリ１７１４〜１７１７に書き込まれる。選ばれなかった入力ポートのパケットは入力ポートのＦＩＦＯメモリ１７１０〜１７１３で選ばれるまで待たされる。一般に調停回路１７１９での調停アルゴリズムは、競合したパケットのそれぞれが公平に選択されるように作られる。すなわち、あるパケットが競合調停で負け続けて飢餓状態が発生しないように作られる。Ｎ個のパケットが競合する場合は、その競合調停でそれぞれのパケットが選ばれる確率はＮ分の１と見ることができる（Ｎは、２以上の正整数）。
【０００６】
Ｆａｔ Ｔｒｅｅを下っていく時に１個スイッチを経由するということは、競合調停によってパケットが待たされる可能性があるということである。スイッチは４入力４出力なので、パケットがある出力ポートに行く場合には、３個の入力ポートから入力されたパケット間で競合が発生する可能性がある。従って、パケットがＦａｔ Ｔｒｅｅを下っていく時に経由するスイッチの個数が多いほど、パケットが競合調停で待たされる可能性が高くなる。
【０００７】
たとえば、図２２に示すプロセッサ０(１８０１)からプロセッサ１５(１８０２)への通信の場合は、スイッチＤ(１８０３)、スイッチＥ(１８０４)、スイッチＦ(１８０５)のそれぞれで競合が発生する。各スイッチでは３個のパケットが競合するので、各スイッチにおける競合調停でそれぞれのパケットが選ばれる確立は３分の１となる。従って、プロセッサ０(１８０１)からプロセッサ１５(１８０２)へ送られるパケットは、そのパケットが経由する３つのスイッチの全てで、そのパケットを含む３つのパケットの競合が発生した場合、２７分の１の確率で到着することになる。
【０００８】
一方、図２３に示すプロセッサ１２(１９０１)からプロセッサ１５(１９０２)への通信の場合は、スイッチＥ(１９０３)とスイッチＦ(１９０４)でパケットの競合が発生する。各スイッチでは３個のパケットが競合するので、各スイッチにおける競合調停でそれぞれのパケットが選ばれる確率は３分の１となる。従って、プロセッサ１２(１９０１)からプロセッサ１５(１９０２)へ送られるパケットは、そのパケットが経由する２つのスイッチの全てで、そのパケットを含む３つのパケット間の競合が発生した場合、９分の１の確率で到着することになる。
【０００９】
図２４に示すプロセッサ１４(２００１)からプロセッサ１５(２００２)への通信の場合は、スイッチＦ(２００３)でパケットの競合が発生する。各スイッチでは３個のパケットが競合するので、各スイッチにおける競合調停でそれぞれのパケットが選ばれる確率は３分の１となる。従って、プロセッサ１４(２００１)からプロセッサ１５(２００２)へ送られるパケットは、そのパケットが経由する１つのスイッチで、そのパケットを含む３つのパケット間の競合が発生した場合、３分の１の確率で到着することになる。
【００１０】
このように、Ｆａｔ Ｔｒｅｅでのルーティングでは、あるプロセッサへパケットを送信する場合に、送り元のプロセッサの位置が異なると、パケットが到着するまでに経由するスイッチ数が異なる。そのために、パケットが到着するまでにパケットに対して行われる競合調停の回数が異なり、パケットが到着する確率が異なることになる。つまり、パケットを送信するプロセッサの位置によって、パケットが到着するまでの時間に偏りができてしまうという問題がある。
【００１１】
このようにパケットが転送先に到着するまでの時間に偏りができてしまうと、転送先に到着するまでに時間のかかるパケットによる処理がボトルネックとなってしまい、並列コンピュータシステム全体として処理遅延が発生してしまうという問題がある。
【００１２】
なお、特許文献１には、長経路のパケットや経路上の競合により待たされたパケットによるレイテンシの低下を抑制する優先調停システムが開示されている。この優先調停システムは、複数のＣＰＵ、複数の共有資源、ルーティングテーブル及び複数のクロスバ、を備える。ＣＰＵは、リクエストパケットを共有資源に送信するときに、自ＣＰＵに対応するルーティングテーブルから、送信先の共有資源に対応するレイテンシ値を取り出して、リクエストパケットのパケットヘッダに設定する。クロスバは、複数のパケットを受信したときに、受信した複数のパケットのレイテンシ値を比較して、レイテンシ値が大きなパケットを優先的に通過させる。
【００１３】
しかし、特許文献１に開示の技術は、調停を実行する場合に、各入力ポートから競合するデータを入力する選択割合を、各入力ポートに対応する強度情報に基づいて決定する技術を開示したものではない。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００９−１９４５１０号公報
【非特許文献】
【００１５】
【非特許文献１】"Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing", C. E. Leiserson, IEEE Transactions on Computers, Vol.C-34, No.10, Oct 1985.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
背景技術として説明したように、非特許文献１に開示されている技術では、プロセッサ間で転送するパケットの転送時間に偏りができてしまうという問題がある。
【００１７】
本発明の目的は、上述した課題を解決するために、プロセッサ間で転送するパケットの転送時間の偏りを低減することができるデータ転送システム、スイッチ及びデータ転送方法を提供することにある。
【課題を解決するための手段】
【００１８】
本発明の第１の態様にかかるデータ転送システムは、複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記データ転送部は、次の転送先が同じ競合データについて調停を実行する調停手段と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するものである。
【００１９】
本発明の第２の態様にかかるデータ転送システムは、複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記プロセッサは、初期値を示す強度情報を次の転送先に送信し、前記データ転送部は、次の転送先が同じ競合データについて調停を実行する調停手段と、複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成して、複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定するものである。
【００２０】
本発明の第３の態様にかかるデータ転送システムは、複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記データ転送部は、複数のデータ転送部からデータが入力される複数の入力ポートのそれぞれについて、入力ポートに対して前記複数のプロセッサからデータが転送される転送経路数を示す転送経路数情報を格納する記憶手段と、次に転送する先が同じ競合データについて調停を実行する調停手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定するものである。
【００２１】
本発明の第４の態様にかかるスイッチは、それぞれが複数接続され、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行するスイッチであって、次の転送先が同じ競合データについて調停を実行する調停手段と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するものである。
【００２２】
本発明の第５の態様にかかるデータ転送方法は、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部のそれぞれにおけるデータ転送方法であって、次の転送先が同じ競合データについて調停を実行する調停ステップと、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知ステップと、を備え、前記調停ステップでは、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するものである。
【発明の効果】
【００２３】
上述した本発明の各態様により、プロセッサ間で転送するパケットの転送時間の偏りを低減することができるデータ転送システム、スイッチ及びデータ転送方法を提供することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の第１の実施の形態の並列コンピュータの概要となるデータ転送システムの構成を示す図である。
【図２】本発明の第１の実施の形態の並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。
【図３】本発明の第１の実施の形態の並列コンピュータのプロセッサ間ネットワークを示す図である。
【図４】本発明の第１の実施の形態の並列コンピュータのプロセッサ間ネットワークのスイッチの構成を示す図である。
【図５】本発明の第１の実施の形態の並列コンピュータのプロセッサ間ネットワークのスイッチの調停回路の構成を示す図である。
【図６】本発明の第１の実施の形態の並列コンピュータのパケットヘッダを示す図である。
【図７】本発明の第１の実施の形態の並列コンピュータの調停回路での処理を説明するフローチャートである。
【図８Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図８Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図９Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図９Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１０Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１０Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１１Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１１Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１２Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１２Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１３Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１３Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１４Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１４Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１５】本発明の第２の実施の形態の並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。
【図１６】本発明の第２の実施の形態の並列コンピュータの調停回路の構成を示す図である。
【図１７】本発明の第３の実施の形態の並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。
【図１８】本発明の第３の実施の形態の並列コンピュータのスイッチの構成を示す図である。
【図１９】Ｆａｔ Ｔｒｅｅネットワークの構成を示す図である。
【図２０】Ｆａｔ Ｔｒｅｅネットワークのルーティングを説明する図である。
【図２１】スイッチの構成の一例を示す図である。
【図２２】Ｆａｔ Ｔｒｅｅネットワークでの問題点を説明する図である。
【図２３】Ｆａｔ Ｔｒｅｅネットワークでの問題点を説明する図である。
【図２４】Ｆａｔ Ｔｒｅｅネットワークでの問題点を説明する図である。
【発明を実施するための形態】
【００２５】
発明の第１の実施の形態．
まず、図１を参照して、本発明の第１の実施の形態にかかる並列コンピュータの概要となるデータ転送システムについて説明する。図１は、本発明の第１の実施の形態にかかる並列コンピュータの概要となるデータ転送システムの構成を示す図である。
【００２６】
データ転送システム５は、複数のプロセッサ５０１〜５１６及び複数のデータ転送部５１７〜５３６を有する。データ転送部５１７〜５３６は、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する。
【００２７】
続いて、図２を参照して、本発明の第１の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部５１７〜５３６について説明する。図２は、本発明の第１の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部５１７〜５３６の構成を示す図である。
【００２８】
データ転送部２０は、入力ポート２５１〜２５４、出力ポート２５５〜２５８、調停手段２５９及び強度情報通知手段２６０を有する。
入力ポート２５１〜２５４のそれぞれは、複数のデータ転送部５１７〜５３６のうち、いずれかから送信されたデータを入力する。
出力ポート２５５〜２５６のそれぞれは、複数のプロセッサ５０１〜５１６及び複数のデータ転送部５１７〜５３６のうち、いずれかに送信されるデータを出力する。
調停手段２５９は、次の転送先が同じ競合データについて調停を実行する。また、調停手段２５９は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する。
強度情報通知手段２６０は、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する。
【００２９】
続いて、本発明の第１の実施の形態にかかるデータ転送部２０の処理について説明する。
調停手段２５９は、複数のデータ転送部から入力ポートのそれぞれを介して、次の転送先が同じ競合データを受信した場合、受信した競合データの調停を実行する。調停手段２５９は、調停において、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する。調停手段２５９は、決定した選択割合で、競合データの調停を実行する。
強度情報通知手段２６０は、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する。
【００３０】
次に、本発明の実施の形態について図面を参照して、本発明の第１の実施の形態にかかる並列コンピュータについて詳細に説明する。図３を参照すると、本発明の第１の実施の形態としての並列コンピュータが示されている。
並列コンピュータ１は、プロセッサ１０１〜１１６、及び、プロセス間ネットワーク１０を有する。プロセス間ネットワーク１０２は、スイッチ１１６〜１３６を有する。
【００３１】
図３において、複数のプロセッサ１０１〜１１６がプロセッサ間ネットワーク１０によって接続されている。ここでは、１６個のプロセッサ１０１〜１１６がプロセッサ間ネットワーク１０に接続された並列コンピュータを示しているが、プロセッサ間ネットワーク１０に接続されるプロセッサ１０１〜１１６の数は任意である。プロセッサ間ネットワーク１０は、４入力４出力のスイッチ１１７〜１３６によって構成される。つまり、スイッチ１１７〜１３６は、４つの入力ポートと４つの出力ポートとを有する。プロセス間ネットワーク１０は、Ｆａｔ Ｔｒｅｅのトポロジとなっている。
【００３２】
ここでは、プロセッサ間ネットワークＦａｔ Ｔｒｅｅは４入力４出力のスイッチ１１７〜１３６によって構成されているが、Ｎ入力Ｎ出力（Ｎは任意の数）のスイッチで構成されていてもよい。ここで、最上段スイッチ１３３〜１３６でのポート番号は、左から順に０、１、２、３と付けることにする。また、中段のスイッチ１２５〜１３２と、最下段のスイッチ１１１７〜１２４のポート番号は、下側の左から０、１、上側の左から２、３と付けることにする。
【００３３】
つまり、スイッチ１１６〜１３５は、ポート番号が０〜３の４つの入力ポートと、ポート番号が０〜３の４つの出力ポートとを有する。そして、図２に示すように、ポート番号０〜３の入力ポート及び出力ポートのそれぞれは、いずれか１つのプロセッサ又はスイッチと接続される。例えば、スイッチ１３１のポート番号０の入力ポートは、スイッチ１２３のポート番号２の出力ポートから出力されたパケットが入力される。また、スイッチ１３１のポート番号０の出力ポートは、スイッチ１２３のポート番号２の入力ポートにパケットを出力する。
【００３４】
図４を参照すると、図３に示す４入力４出力のスイッチ１１６〜１３５の１つの実施例が示されている。スイッチ２０１は、４つの入力ポート２０２〜２０５と４つの出力ポート２０６〜２０９をもつ。スイッチ２０１は、各入力ポート２０２〜２０５のそれぞれに対応するように、入力ＦＩＦＯメモリ２１０〜２１３と、調停での強度を格納する強度レジスタ２２３〜２２６とを有する。入力ＦＩＦＯメモリ２１０〜２１３は、自身に対応する入力ポート２０２〜２０５に入力されたパケットがＦＩＦＯ方式で格納される。入力ＦＩＦＯメモリ２１０〜２１３のそれぞれは、ＦＩＦＯの先頭のパケットのパケットヘッダ含まれる調停での強度を、自身に対応する強度レジスタ２２３〜２２６のそれぞれに出力する。入力ＦＩＦＯメモリ２１０〜２１３は、例えば、ＦＩＦＯにパケットが格納されていない場合、０を強度レジスタ２２３〜２２６に格納する。なお、パケットのパケットヘッダに含まれる調停での強度については、後に詳述する。調停回路２１９〜２２２は、調停手段２５９及び強度通知手段２６０として機能する。
【００３５】
強度レジスタ２２３〜２２６には入力ＦＩＦＯメモリ２１０〜２１３から出力された調停での強度が格納される。強度レジスタ２２３〜２２６は、自身に格納された調停での強度を示す信号を調停回路２１９〜２２２に出力する。また、入力ＦＩＦＯメモリ２１０〜２１３は、自身に格納された先頭のパケットを、マルチプレクサ(ＭＵＸ)２２７〜２３０に出力する。また、入力ＦＩＦＯメモリ２１０〜２１３は、パケットを出力しているときに、そのパケットを出力する出力ポートに対応する調停回路に、調停参加信号(図示せず)を出力する。
【００３６】
入力ＦＩＦＯメモリ２１０〜２１３は、例えば、パケットのパケットヘッダに含まれる送り先プロセッサ番号に基づいて、パケットを出力する出力ポートを判定する。例えば、入力ＦＩＦＯメモリ２１０〜２１３は、送り先プロセッサ番号からパケットを出力すべき出力ポートを求めることができるルーティングテーブルが格納される。そして、入力ＦＩＦＯメモリ２１０〜２１３は、自身に格納されるルーティングテーブルに基づいて、パケットを出力する出力ポートを判定する。なお、パケットのパケットヘッダに含まれる送り先プロセッサ番号については、後に詳述する。
【００３７】
スイッチ２０１は、各出力ポート２０６〜２０９のそれぞれに対応するように、調停回路２１９〜２２２と出力ＦＩＦＯメモリ２１５〜２１８とを有する。また、スイッチ２０１は、クロスバスイッチ２１４を有する。クロスバスイッチ２１４は、出力ポート２０６〜２０９のそれぞれに対応するように、マルチプレクサ(ＭＵＸ)２２７〜２３０を有する。クロスバスイッチ２１４が、入力ＦＩＦＯメモリ２１０〜２１３と出力ＦＩＦＯメモリ２１５〜２１８を接続している。
【００３８】
調停回路２１９〜２２２は、各強度レジスタ２２３〜２２６から出力された調停での強度と、各入力ＦＩＦＯメモリ２１０〜２１３から出力された調停参加信号をもとに、クロスバスイッチ２１４内の対応するマルチプレクサ(ＭＵＸ)２２７〜２３０を制御してパケットをルーティングする。マルチプレクサ２２７〜２３０は、自身に対応する調停回路からの制御に応じて、入力ＦＩＦＯメモリ２１０〜２１３のそれぞれから出力されたパケットのいずれかを選択して、自身に対応する出力ＦＩＦＯメモリ２１５〜２１８に出力する。
【００３９】
次に図５を使って、調停回路２１９〜２２２の詳細な構成を説明する。調停回路３０１は、強度カウンタ３０２〜３０５、選択回路３０６、１減算器３０７〜３１０、マルチプレクサ(ＭＵＸ)３１１〜３１４、強度計算回路３１５及び強度合計レジスタ３１６を有する。
【００４０】
調停回路３０１には、４つの入力ポート２０２〜２０５のそれぞれに対応する強度３１７〜３２０と調停参加信号３２１〜３２４が入力される。また、調停回路３０１は、各入力ポートに対応して、４つの強度カウンタ３０２〜３０５と、４つの１減算器３０７〜３１０と、４つのマルチプレクサ(ＭＵＸ)３１１〜３１４とを有する。調停回路３０１に入力された強度３１７〜３２０は、自身に対応するマルチプレクサ(ＭＵＸ)と、強度計算回路３１５とに入力される。調停回路３０１に入力された調停参加信号３２１〜３２４は、選択回路３０６及び強度計算回路３１５に入力される。
【００４１】
マルチプレクサ(ＭＵＸ)３１１〜３１４は、自身に入力された強度３１７〜３２０、又は、１減算器３０７〜３１０から出力された強度カウンタ値のいずれかを選択して強度カウンタ３０２〜３０５に出力する。強度カウンタ３０２〜３０５には、マルチプレクサ(ＭＵＸ)３１１〜３１４から出力された強度３１７〜３２０又は強度カウンタ値が、強度カウンタ値として格納される。つまり、強度カウンタ３０２〜３０５に格納される強度カウンタ値をカウントダウンする場合、マルチプレクサ(ＭＵＸ)３１１〜３１４は、１減算器３０７〜３１０から出力された強度カウンタ値を選択して強度カウンタ３０２〜３０５に出力する。強度カウンタ３０２〜３０５は、強度カウンタ値を選択回路３０６に出力する。
【００４２】
選択回路３０６は、強度カウンタ３０２〜３０５から出力された強度カウンタ値と、調停参加信号３２１〜３２４とに基づいて、１つの入力ポートのパケットを選択する。選択回路３０６は、選択した入力ポートのパケットを選択して出力するように制御する選択信号を、マルチプレクサ(ＭＵＸ)２２７〜２３０に出力する。選択処理については、後で図７を使って説明する。
【００４３】
強度計算回路３１５は、強度３１７〜３２０と調停参加信号３２１〜３２４を使って、調停参加している入力ポートの強度の合計値を算出する。強度計算回路３１５は、算出した強度の合計値を強度合計レジスタ３１６に書き込む。そして、調停回路３０１は、クロスバスイッチ２１４から出ていくパケットのパケットヘッダに強度合計レジスタ３１６内の強度の合計値を書き込む。
【００４４】
次に本実施の形態でのパケットのパケットヘッダについて、図６に示す。パケットヘッダには、送り先プロセッサ番号４０１と、送り元プロセッサ番号４０２と、調停での強度４０３、書き込みアドレス４０４、データ長４０５が格納される。パケットヘッダの後には、データ長４０５で示されたバイト数のデータ(図示せず)が続く。プロセッサ１０１〜１１５は、パケットを送る時に、調停での強度４０３を１に初期化する。調停での強度４０３は、各スイッチ１１７〜１３６通過時にスイッチ１１７〜１３６で更新される。書き込みアドレス４０４は、パケットが送り先のプロセッサに到着した場合に、データが書き込まれるメモリ上のアドレスである。
【００４５】
次に、図５の調停回路３０１での処理について、図７使って説明する。
まず、調停回路３０１は、すべての強度カウンタ３０２〜３０５を対応する強度レジスタ２２３〜２２６から出力された強度３１７〜３２０で初期化する（ステップＳ１０１）。これは、マルチプレクサ(ＭＵＸ)３１１〜３１４で強度３１７〜３２０を選択することにより行う。また、この時に、調停回路３０１は、強度合計レジスタ３１６に０を格納して、強度合計レジスタ３１６を初期化する。
【００４６】
次に、選択回路３０６は、入力ＦＩＦＯメモリ２１０〜２１３から出力された調停参加信号３２１〜３２４を参照し、新たな調停参加者を受け付ける（ステップＳ１０２）。具体的には、選択回路３０６は、入力ＦＩＦＯメモリ２１０〜２１３のいずれかから調停参加信号が入力された場合、入力された調停参加信号に対応する入力ポートを調停参加者として決定する。また、この時に、強度計算回路３１５は、強度３１７〜３２０のうち、調停参加している入力ポートに対応する強度の合計値を強度合計レジスタ３１６に格納する。以降、選択回路３０６は、再びステップＳ１０１になるまで、一度参加した調停参加者を、調停参加者として認識し続ける。
【００４７】
次に、調停回路３０１は、すべての調停参加者の強度カウンタの値が１かどうかを調べる（ステップＳ１０３）。すべての調停参加者の強度カウンタの値が１でない場合（ステップＳ１０３：いいえ）は、選択回路３０６は、強度カウンタの値が最も大きい調停参加者を選択する（ステップＳ１０４）。具体的には、選択回路３０６は、最も大きい強度カウンタ値を出力する強度カウンタに対応する入力ポートの入力ＦＩＦＯメモリから出力されたパケットを選択する選択信号をクロスバスイッチ２１４のマルチプレクサ(ＭＵＸ)に出力する。なお、選択回路３０６は、選択する入力ＦＩＦＯメモリから、調停参加信号が出力されていない場合は、調停参加信号が出力されるのを待ってから、その入力ＦＩＦＯメモリから出力されたパケットを選択する。これによって、選択回路３０６が含まれる調停回路に対応する出力ポートに、その出力ポート以外へのパケットを誤って出力しないようにする。選択回路３０６は、調停回路３０１は、そのパケットがクロスバスイッチ２１４を抜けてきた時点で強度合計レジスタ３１６の強度の合計値をパケットヘッダの調停での強度のフィールドに書き込む（ステップＳ１０５）。
【００４８】
そして、選択回路３０６は、強度カウンタ値が最も大きい調停参加者として選択した入力ポートに対応する強度カウンタの値をデクリメントする（ステップＳ１０６）。強度カウンタ３０２〜３０５の値のデクリメントは、マルチプレクサ(ＭＵＸ)３１１〜３１４で１減算器３０７〜３１０の方を選択することにより行う。この選択は、例えば、選択回路３０６が、マルチプレクサ(ＭＵＸ)３１１〜３１４に、１減算器３０７〜３１０からの出力を選択する選択信号を出力することにより行う。
【００４９】
その後、選択回路３０６は、ステップＳ１０２にすすみ、入力ポートからの調停参加信号３２１〜３２４を参照し、新たな調停参加者を受け付ける（ステップＳ１０２）。このときに、入力ＦＩＦＯメモリ２１０〜２１３は、選択されたパケットの次にＦＩＦＯに含まれるパケットを、ＦＩＦＯの先頭のパケットにする。そして、入力ＦＩＦＯメモリ２１０〜２１３は、先頭のパケットを、マルチプレクサ(ＭＵＸ)２２７〜２３０に出力する。また、選択回路３０６は、この時点で、新たに調停参加者として選択していない入力ポートに対応する調停参加信号が入力されている場合、その入力ポートを新たな調停参加者として受け入れる。その場合、選択回路３０６は、その入力ポートに対応する強度カウンタを初期化する。また、強度計算回路３１５は、新たに調停参加者として参加した入力ポートに対応する強度と、強度合計レジスタ３１６に格納された強度の合計値との合計値を、強度合計レジスタ３１６に格納する。
【００５０】
次にステップＳ１０３で、すべての調停参加者の強度カウンタの値が１であった場合について説明する（ステップＳ１０３：はい）。調停回路３０１は、まず、強度カウンタの値が１の調停参加者を１人選択する（ステップＳ１０７）。選択の仕方は、予め決められた優先順位でもラウンドロビンでもよい。そして、選択回路３０６は、選択した入力ポートに対応する入力ＦＩＦＯメモリから出力されたパケットを選択する選択信号をクロスバスイッチ２１４のマルチプレクサ(ＭＵＸ)に出力する。調停回路３０１は、そのパケットがクロスバスイッチ２１４を抜けてきた時点で強度合計レジスタ３１６の強度の合計値をパケットヘッダの調停での強度のフィールドに書き込む（ステップＳ１０８）。そして、選択した入力ポートに対応する強度カウンタの値をデクリメントする（ステップＳ１０９）。次に、調停回路３０１は、強度カウンタの値が１となった調停参加者のうちで選ばれていない調停参加者がいるかどうかを調べる（ステップＳ１１０）。つまり、調停回路３０１は、値が０になっていない強度カウンタに対応する調停参加者がいるかどうかを調べる。選ばれていない調停参加者がいる場合（ステップＳ１１０：はい）は、ステップＳ１０７に戻る。そうでない場合（ステップＳ１１０：いいえ）は、ステップＳ１０１へ戻り、強度カウンタ３０２〜３０５を初期化する。
【００５１】
以上に説明したように、調停回路３０１は、調停参加した入力ポートのそれぞれに入力されたパケットに含まれる強度を、入力ポートのそれぞれから選択して次段に出力するパケットの数としている。言い換えると、調停回路３０１は、調停参加した入力ポートのそれぞれに入力されたパケットに含まれる強度を、入力ポートのそれぞれから調停対象として取り込むパケット数としている。よって、調停参加した入力ポートのそれぞれからの強度の合計値は、調停回路３０１が調停対象としたパケット数となる。言い換えると、強度の合計値は、それぞれの出力先が競合することによって、調停回路３０１によって調停が行われたパケットの競合数である。そして、調停回路３０１は、強度の合計値を、強度としてパケットに含めて、そのパケットを次段に出力するようにしている。つまり、これによって、各スイッチは、複数の次段のスイッチのそれぞれについて、次段のスイッチに転送するパケットが自身に集中する度合いを、強度として次段のスイッチに伝えることができる。
【００５２】
そのため、調停回路３０１は、入力ポートのそれぞれに入力されたパケットに含まれる強度が示す競合数分のパケットを、それぞれの入力ポートから選択して次段に出力するようにしている。つまり、これにより、調停回路３０１は、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができる。
【００５３】
次に、図８〜図１４を使って、プロセッサ０(１０１)〜プロセッサ１４(１１５)がプロセッサ１５(１１６)に通信する場合の、本発明での動作と効果を説明する。
【００５４】
図８Ｂは、スイッチ８０４においてパケットが競合した状態を示す図である。図８Ｂは、スイッチ ８０４において、プロセッサ０(８０１)、プロセッサ４(８０２)、プロセッサ８(８０３)からプロセッサ１５(８０５)へ送信されたパケットが競合した場合について例示している。スイッチ８０４での出力ポート３の調停回路の状態を図８Ａに図示している。入力ポート０〜２の強度カウンタ８０６〜８０９には、初期値として、プロセッサ８０１、８０２、８０３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加８１０〜８１２に１が、調停参加８１３に０が格納されている。
【００５５】
ここで、調停参加８１０〜８１３は、例えば、調停回路が有する調停参加レジスタである。調停回路は、入力ポート０〜３のそれぞれに対応する調停参加レジスタを有する。調停回路は、ステップＳ１０２において、調停参加信号が入力された場合、その調停参加信号に対応する入力ポートの調停参加レジスタに１を格納する。調停回路は、ステップＳ１０１において、調停参加レジスタに０を格納して初期化する。
【００５６】
そして、強度合計レジスタ８１４には、調停での強度の合計である３が格納される。調停回路３０１は、スイッチ８０４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度に３を格納する。図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度カウンタ８０６〜８０８の値はすべて１なので、調停回路３０１は、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００５７】
図９Ｂは、スイッチ９０４においてパケットが競合した状態を示す図である。図９Ｂは、スイッチ９０４において、プロセッサ２(９０１)、プロセッサ６(９０２)、プロセッサ１０(９０３)からプロセッサ１５(９０５)へ送信されたパケットが競合した場合について例示している。スイッチ９０４での出力ポート３の調停回路の状態を図９Ａに図示している。入力ポート０〜２の強度カウンタ９０６〜９０８には、初期値として、プロセッサ９０１、９０２、９０３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加９１０〜９１２に１が、調停参加９１３に０が格納されている。そして、強度合計レジスタ９１４には、調停での強度の合計である３が格納される。スイッチ９０４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度には３が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度カウンタ９０６〜９０８の値はすべて１なので、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００５８】
図１０Ｂは、スイッチ１００４においてパケットが競合した状態を示す図である。図１０Ｂは、スイッチ １００４において、プロセッサ１(１００１)、プロセッサ５(１００２)、プロセッサ９(１００３)からプロセッサ１５(１００５)へ送信されたパケットが競合した場合について例示している。スイッチ１００４での出力ポート３の調停回路の状態を図１０Ａに図示している。入力ポート０〜２の強度カウンタ１００６〜１００８には、初期値として、プロセッサ１００１、１００２、１００３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加１０１０〜１０１２に１が、調停参加１０１３に０が格納されている。そして、強度合計レジスタ１０１４には、調停での強度の合計である３が格納される。スイッチ１００４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度には３が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度カウンタ１００６〜１００８の値はすべて１なので、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００５９】
図１１Ｂは、スイッチ１１０４においてパケットが競合した状態を示す図である。図１１Ｂは、スイッチ１１０４において、プロセッサ３(１１０１)、プロセッサ７(１１０２)、プロセッサ１１(１１０３)からプロセッサ１５(１１０５)へ送信されたパケットが競合した場合について例示している。スイッチ１１０４での出力ポート３の調停回路の状態を図１１Ａに図示している。入力ポート０〜２の強度カウンタ１１０６〜１１０８には、初期値として、プロセッサ１１０１、１１０２、１１０３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加 １１１０〜１１１２に１が、調停参加１１１３に０が格納されている。そして、強度合計レジスタ１１１４には、調停での強度の合計である３が格納される。スイッチ １１０４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度には３が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度レジスタ１１０６〜１１０８の値はすべて１なので、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００６０】
図１２Ｂは、スイッチ１２０４においてパケットが競合した状態を示す図である。図１２Ｂは、スイッチ１２０４において、プロセッサ１２(１２０３)とスイッチ１２０１とスイッチ１２０２とから送信されたパケットが競合した場合について例示している。スイッチ１２０４での出力ポート１の調停回路を図１２Ａに図示している。入力ポート０の強度カウンタ１２０６には、初期値として、プロセッサ１２(１２０３)からのパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート２と入力ポート３の強度カウンタ１２０８、１２０９には、初期値として、スイッチ１２０１とスイッチ１２０２からのパケットのパケットヘッダの調停での強度３が格納される。つまり、ここでは、スイッチ１２０１とスイッチ１２０２のそれぞれおいて、パケットが競合して、パケットヘッダの調停での強度が３に更新された場合について例示している。
【００６１】
また、入力ポート０、入力ポート２、入力ポート３が調停参加しているので、調停参加１２１０、１２１２、１２１３に１が、調停参加１２１１に０が格納されている。そして、強度合計レジスタ１２１４には、調停での強度の合計である７が格納される。スイッチ １２０４を通過し出力ポート１に出力されるパケットのパケットヘッダの調停での強度には７が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、参加者の強度カウンタの値は１、３、３となっているので、ステップＳ１０３の後に、強度カウンタの値が１、１、１になるまでは、ステップＳ１０４の処理を実行する。このときに実行されるステップＳ１０４の処理では、入力ポート２と入力ポート３からのパケットが選択される。調停回路３０１は、強度カウンタの値が１、１、１になれば、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。そして、ステップＳ１０７〜Ｓ１１０の処理において、入力ポート０、入力ポート２、入力ポート３からパケットが１つずつ選択される。
【００６２】
図１３Ｂは、スイッチ１３０４においてパケットが競合した状態を示す図である。スイッチ１３０４では、プロセッサ１３(１３０３)とスイッチ１３０１とスイッチ１３０２とから送信されたパケットが競合した場合について例示している。スイッチ１３０４での出力ポート１の調停回路を図１３Ａに図示している。入力ポート０の強度カウンタ１３０６には、初期値として、プロセッサ１３(１３０３)からのパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート２と入力ポート３の強度レジスタ１３０８、１３０９には、初期値として、スイッチ１３０１とスイッチ１３０２からのパケットのパケットヘッダの調停での強度３が格納される。つまり、ここでは、スイッチ１３０１とスイッチ１３０２のそれぞれおいて、パケットが競合して、パケットヘッダの調停での強度が３に更新された場合について例示している。
【００６３】
また、入力ポート０、入力ポート２、入力ポート３が調停参加しているので、調停参加 １３１０、１３１２、１３１３に１が、調停参加 １３１１に０が格納されている。そして、強度合計レジスタ１３１４には、調停での強度の合計である７が格納される。スイッチ １３０４を通過し出力ポート１に出力されるパケットのパケットヘッダの調停での強度には７が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、参加者の強度カウンタの値は１、３、３となっているので、ステップＳ１０３の後に、強度カウンタの値が１、１、１になるまでは、ステップＳ１０４の処理を実行する。このときに実行されるステップＳ１０４の処理では、入力ポート２と入力ポート３からのパケットが選択される。調停回路３０１は、強度カウンタの値が１、１、１になれば、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。そして、ステップＳ１０７〜Ｓ１１０の処理において、入力ポート０、入力ポート２、入力ポート３からパケットが１つずつ選択される。
【００６４】
図１４Ｂは、スイッチ１４０４においてパケットが競合した状態を示す図である。スイッチ１４０４では、プロセッサ１４(１４０３)とスイッチ１４０１とスイッチ１４０２とから送信されたパケットが競合した場合について例示している。スイッチ１４０４での出力ポート１の調停回路を図１４Ａに図示している。入力ポート０の強度カウンタ１４０６には、初期値として、プロセッサ１４(１４０３)からのパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート２と入力ポート３の強度レジスタ１４０８、１４０９には、初期値として、スイッチ１４０１とスイッチ１４０２からのパケットのパケットヘッダの調停での強度７が格納される。つまり、ここでは、スイッチ１４０１とスイッチ１４０２のそれぞれと、それぞれのスイッチの前段のスイッチにおいて、パケットが競合して、パケットヘッダの調停での強度が７に更新された場合について例示している。
【００６５】
また、入力ポート０、入力ポート２、入力ポート３が調停参加しているので、調停参加 １４１０、１４１２、１４１３に１が、調停参加１４１１に０が格納されている。そして、強度合計レジスタ１４１４には、調停での強度の合計である１５が格納される。スイッチ １４０４を通過し出力ポート１に出力されるパケットのパケットヘッダの調停での強度には１５が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、参加者の強度カウンタの値は１、７、７となっているので、ステップＳ１０３の後に、強度カウンタの値が１、１、１になるまでは、ステップＳ１０４の処理を実行する。このときに実行されるステップＳ１０４の処理では、入力ポート２と入力ポート３からのパケットが選択される。調停回路３０１は、強度カウンタの値が１、１、１になれば、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。そして、ステップＳ１０７〜Ｓ１１０の処理において、入力ポート０、入力ポート２、入力ポート３からパケットが１つずつ選択される。
【００６６】
次に、この場合の各プロセッサからプロセッサ１５への到着確率を計算する。それぞれの経由するスイッチ数が異なる、プロセッサ０、プロセッサ１２、プロセッサ１４からのパケットの到着確率を計算する。まず、プロセッサ０からのパケットは、３つのスイッチを経由する。それぞれのスイッチにおいて３つのパケットが競合した場合に、それぞれのスイッチにおいて、プロセッサ０から送信したパケットが選択される確率は、３分の１、７分の３、１５分の７になる。よって、これらの確率の積は、１５分の１になる。次にプロセッサ１２からのパケットは、２つのスイッチを経由する。それぞれのスイッチにおいて３つのパケットが競合した場合に、それぞれのスイッチにおいて、プロセッサ１２から送信したパケットが選択される確率は、７分の１、１５分の７になるよって、これらの確率の積は１５分の１になる。最後にプロセッサ１４からのパケットは、１つのスイッチを経由して１５分の１となる。
【００６７】
このように、本実施の形態では、プロセッサ０〜１４のそれぞれからプロセッサ１５に出力されるパケットのように、それぞれのパケットが経由するスイッチ数が異なってもプロセッサ１５への到着確率が１５分の１となる。したがって、どのプロセッサから出力されるパケットも転送先のプロセッサに到着する確率が同じになることがわかる。つまり、どのプロセッサから出力されるパケットも転送先のプロセッサに到着するまでにかかる時間を一定化することができる。つまり、本発明の第１の実施の形態によれば、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。
【００６８】
発明の第２の実施の形態．
続いて、図１５を参照して、本発明の第２の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部について説明する。図１５は、本発明の第２の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。なお、本発明の第２の実施の形態にかかる並列コンピュータの概要となるデータ転送システムの構成は、発明の第１の実施の形態にかかるデータ転送システムの構成と同様であるため、説明を省略する。
【００６９】
データ転送部６０は、入力ポート６５１〜６５４、出力ポート６５５〜６５８、調停手段６５９及び強度情報通知手段６６０を有する。
入力ポート６５１〜６５４のそれぞれは、複数のデータ転送部５１７〜５３６のうち、いずれかから送信されたデータを入力する。
出力ポート６５５〜６５６のそれぞれは、複数のプロセッサ５０１〜５１６及び複数のデータ転送部５１７〜５３６のうち、いずれかに送信されるデータを出力する。
調停手段６５９は、次の転送先が同じ競合データについて調停を実行する。また、調停手段６５９は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定する。
強度情報通知手段６６０は、複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成する。強度情報通知手段６６０は、生成した強度情報を複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する。
【００７０】
続いて、本発明の第２の実施の形態にかかるデータ転送部６０の処理について説明する。
複数のプロセッサ５０１〜５１６は、初期値を示す強度情報を転送先のデータ転送部に出力する。強度情報通知手段６６０は、複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成する。強度情報通知手段６６０は、生成した強度情報を複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する。
調停手段６５９は、複数のデータ転送部から入力ポートのそれぞれを介して、次の転送先が同じ競合データを受信した場合、受信した競合データの調停を実行する。調停手段６５９は、調停において、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定する。調停手段６５９は、決定した選択割合で、競合データの調停を実行する。
【００７１】
続いて、本発明の第２の実施の形態にかかる並列コンピュータについて詳細に説明する。図１６を参照して、本発明の第２の実施の形態にかかる調停回路６０１について説明する。なお、本発明の第２の実施の形態にかかる並列コンピュータ及びスイッチの構成は、発明の第１の実施の形態にかかる並列コンピュータ及びスイッチの構成と同様であるため、説明を省略する。また、本発明の第２の実施の形態にかかる調停回路６０１の処理についても、図７に示す処理と同様であるため、説明を省略する。
【００７２】
図１６を参照すると、本発明の第２の実施の形態としての並列コンピュータのプロセッサ間ネットワークを構成するスイッチの中の調停回路 ６０１が示されている。第２の実施の形態が第１の実施の形態と異なるのは、調停回路６０１の部分である。本実施の形態の調停回路６０１は、強度計算回路６１５に調停参加信号６２１〜６２４が入力されない点が、第１の実施の形態の調停回路３０１と異なる。
【００７３】
第２の実施の形態の調停回路６０１の強度計算回路６１５は、調停参加の状態を考慮せずに、強度の合計値を計算する。そして、強度計算回路６１５は、算出した強度の合計値を強度合計レジスタ６１６に格納する。調停回路６０１は、次段のスイッチに送出するパケットのパケットヘッダの調停での強度に、強度合計レジスタ６１６に格納された強度の合計値を設定する。調停回路６０１は、例えば、ステップＳ１０２のタイミングで、強度６１７〜６２０の合計値を強度合計レジスタ６１６に格納するようにしてもよい。また、調停回路６０１は、ステップＳ１０２のタイミングで、強度６１７〜６２０のうち、強度が０から０以外の値に変化した強度と、強度合計レジスタ６１６に格納される値との合計値を強度合計レジスタ６１６に格納するようにしてもよい。
【００７４】
以上に説明したように、まず、プロセッサ１０１〜１１６は、パケットの強度に初期値１を設定して出力する。調停回路６０１は、所定の期間内に、入力ポートのそれぞれに入力されたパケットに含まれる強度の合計値を、強度としてパケットに含めて、そのパケットを次段のスイッチのそれぞれに出力するようにしている。つまり、これによって、各スイッチは、パケットが自身に集中する度合いを、強度として次段のスイッチに伝えることができる。
【００７５】
そして、調停回路６０１は、入力ポートのそれぞれに入力されたパケットに含まれる強度が示す値分のパケットを、それぞれの入力ポートから選択して次段に出力するようにしている。つまり、これにより、調停回路６０１は、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができる。
【００７６】
つまり、本発明の第２の実施の形態によれば、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。また、本発明の第２の実施の形態では、入力ＦＩＦＯバッファ２２３〜２２６から強度計算回路６１５に調停参加信号を伝送する信号線が不要となるため、回路規模を抑えることができる。
【００７７】
発明の第３の実施の形態．
続いて、図１７を参照して、本発明の第３の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部について説明する。図１７は、本発明の第３の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。なお、本発明の第３の実施の形態にかかる並列コンピュータの概要となるデータ転送システムの構成は、発明の第１の実施の形態にかかるデータ転送システムの構成と同様であるため、説明を省略する。
【００７８】
データ転送部７０は、入力ポート７５１〜７５４、出力ポート７５５〜７５８、調停手段７５９及び記憶手段７６０を有する。
入力ポート７５１〜７５４のそれぞれは、複数のデータ転送部のうち、いずれかから送信されたデータを入力する。
出力ポート７５５〜７５６のそれぞれは、複数のプロセッサ及び複数のデータ転送部のうち、いずれかに送信されるデータを出力する。
調停手段７５９は、次の転送先が同じ競合データについて調停を実行する。また、調停手段７５９は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定する。
記憶手段７６０は、複数のデータ転送部から自データ転送部にデータが入力される複数の入力ポートのそれぞれについて、前記複数のプロセッサから入力ポートにデータが転送される転送経路数を示す転送経路数情報を格納する。
【００７９】
続いて、本発明の第３の実施の形態にかかるデータ転送部７０の処理について説明する。
調停手段７５９は、複数のデータ転送部から入力ポートのそれぞれを介して、次の転送先が同じ競合データを受信した場合、受信した競合データの調停を実行する。調停手段７５９は、調停において、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定する。調停手段７５９は、決定した選択割合で、競合データの調停を実行する。
【００８０】
続いて、本発明の第３の実施の形態にかかる並列コンピュータについて詳細に説明する。図１８を参照して、本発明の第２の実施の形態にかかるスイッチ７０１について説明する。なお、本発明の第３の実施の形態にかかる並列コンピュータの構成は、発明の第１の実施の形態にかかる並列コンピュータの構成と同様であるため、説明を省略する。本発明の第３の実施の形態にかかる調停回路の構成は、強度計算回路３１５及び強度合計レジスタ３１６を有しない点を除き、発明の第１の実施の形態にかかる並列コンピュータの構成と同様であるため、説明を省略する。また、本発明の第３の実施の形態にかかる調停回路の処理についても、図７に示す処理と同様であるため、説明を省略する。
【００８１】
図１８を参照すると、本発明の第３の実施の形態としての並列コンピュータのプロセッサ間ネットワークを構成するスイッチ７０１が示されている。第３の実施の形態が第１の実施の形態と異なるのは、スイッチ７０１で、強度レジスタ７２３〜７２６に設定する調停での強度をパケットヘッダから読み出して設定するのではなく、スイッチの接続形態からあらかじめ設定しておくことである。
【００８２】
具体的には、それぞれの強度レジスタ７２３〜７２６に、それぞれの強度レジスタ７２３〜７２６に対応する入力ポートに対してプロセッサ１０１〜１１６からパケットが転送される転送経路数を格納する。ここで、図１２Ｂに例示するスイッチ１２０４を例に挙げて説明する。スイッチ１２０４の入力ポート０には、１つのプロセッサ１２からパケットが転送される。したがって、入力ポート０に対応する入力強度レジスタ０(７２３)には１が格納される。スイッチ１２０４の入力ポート１には、１つのプロセッサ１４からパケットが転送される。よって、入力ポート１に対応する入力強度レジスタ１(７２４)には１が格納される。スイッチ１２０４の入力ポート２には、３つのプロセッサ０、４、８からパケットが転送される。よって、入力ポート２に対応する入力強度レジスタ２(７２５)には３が格納される。スイッチ１２０４の入力ポート３には、３つのプロセッサ１、５、９からパケットが転送される。よって、入力ポート３に対応する入力強度レジスタ３(７２６)には３が格納される。
【００８３】
以上に説明したように、強度レジスタ７２３〜７２６には、強度レジスタ７２３〜７２６に対応する入力ポートに入力されるパケットがプロセッサ１０１〜１１６から転送される転送経路数が強度として格納されている。ここで、入力ポートに対してプロセッサ１０１〜１１６からデータが転送される転送経路数が多い場合、その入力ポートに入力されるパケット数も多くなる。つまり、スイッチは、強度レジスタ７２３〜７２６のそれぞれに格納される強度は、入力ポート７０２〜７０５のそれぞれにパケットが集中する度合いとなる。
【００８４】
そして、調停回路７１９〜７２２は、入力ポートのそれぞれに対応する強度レジスタ７２３〜７２６から出力される強度が示す転送経路数分のパケットを、それぞれの入力ポートから選択して次段に出力するようにしている。つまり、これにより、調停回路６０１は、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができる。
【００８５】
つまり、本発明の第３の実施の形態によれば、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。また、本発明の第３の実施の形態では、強度計算回路及び強度合計レジスタと、調停回路７１９〜７２２にいてパケットに強度を設定する処理と、入力ＦＩＦＯメモリ７１０〜７１３において強度レジスタに強度を設定する処理とが不要となるため、回路規模を抑えることができる。また、パケットに調停での強度を格納する領域も不要となるため、プロセス間ネットワークにおいて転送されるデータ量を低減することもできる。
【００８６】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００８７】
プロセッサの数及びプロセス間ネットワークを構成するスイッチの数は、本実施の形態において例示した数に限られない。また、プロセス間ネットワークの構成は、本実施の形態において例示した構成に限られない。つまり、本発明は、本実施の形態において例示したように、スイッチが多段に接続されていないプロセス間ネットワークにも適用することができる。
【００８８】
本発明の第１及び第２の実施の形態では、調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する数を、各入力ポートから受信した強度が示す値として決定しているが、これに限られない。調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度の多さに関する入力ポート間の割合に応じて決定するようにしてもよい。このようにしても、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができるため、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。
【００８９】
本発明の第１及び第２の実施の形態では、スイッチは、調停での強度をパケットに含めて出力するようにしているが、これに限られない。例えば、スイッチは、パケットとは、別にそのパケットと対応付けて調停での強度を示す強度情報を出力するようにしてもよい。
【００９０】
本発明の第３の実施の形態では、調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する数を、各入力ポートについての転送経路数情報が示す転送経路数として決定しているが、これに限られない。調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定するようにしてもよい。このようにしても、より多くのパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができるため、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。
【００９１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００９２】
（付記１）複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記データ転送部は、次の転送先が同じ競合データについて調停を実行する調停手段と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するデータ転送システム。
【００９３】
（付記２）前記強度情報通知手段は、前記調停を行った競合データのそれぞれに対応付けて、当該調停を行った競合データの競合数を示す強度情報を次の転送先に送信し、前記調停手段は、それぞれが複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して次の転送先に送信される競合データについて、前記調停を実行する複数の調停回路を含み、前記調停回路は、前記各入力ポートから受信した強度情報のうち、当該調停回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記選択割合を決定する付記１に記載のデータ転送システム。
【００９４】
（付記３）前記強度情報通知手段は、それぞれが前記複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して送信される競合データのそれぞれに前記強度情報を対応付けて、当該出力ポートを介して次の転送先に送信する複数の強度情報通知回路を含み、前記強度情報通知回路は、当該強度情報通知回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記競合データの競合数を算出する付記２に記載のデータ転送システム。
【００９５】
（付記４）前記調整回路は、前記調停を実行する場合には、それぞれが前記複数の入力ポートのそれぞれに対応し、対応する入力ポートを選択し、その入力ポートから競合データを入力した数をカウントする複数のカウンタを含み、当該複数のカウンタのカウント数のそれぞれが、当該複数のカウンタに対応する入力ポートから受信した強度情報が示す競合数のそれぞれと一致まで、前記複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する付記２又は３に記載のデータ転送システム。
【００９６】
（付記５）前記調停手段は、より多い競合数を示す強度情報を受信した入力ポートからの競合データを優先して、次の転送先に送信する付記１乃至４に記載のデータ転送システム。
【００９７】
（付記６）前記競合データは、データ転送先のプロセッサを示す転送先プロセッサ情報を含むパケットであり、前記データ転送部は、前記パケットに含まれる出力先プロセッサ情報に基づいて、前記パケットをルーティングするスイッチである付記１乃至５のいずれか１項に記載のデータ転送システム。
【００９８】
（付記７）前記強度情報通知手段は、前記調停を行った競合データのそれぞれに、当該調停を行った競合データの競合数を示す強度情報を含めて送信する付記２乃至４のいずれか１項に記載のデータ転送システム。
【００９９】
（付記８）前記データ転送システムは、前記複数のデータ転送部が多段に接続されたプロセス間ネットワークをさらに備えた付記１乃至７のいずれか１項に記載のデータ転送システム。
【符号の説明】
【０１００】
１ 並列コンピュータ
５ データ転送システム
１０ プロセッサ間ネットワーク
２０、６０、７０ データ転送部
１０１、１０２、１０３、１０４、１０５、１０６、１０７、１０８、１０９、１１０、１１１、１１２、１１３、１１４、１１５、１１６、５０１、５０２、５０３、５０４、５０５、５０６、５０７、５０８、５０９、５１０、５１１、５１２、５１３、５１４、５１５、５１６、８０１、８０２，８０３、８０５、９０１、９０２、９０３、９０５、１００１、１００２、１００３、１００５、１１０１、１１０２、１１０３、１１０５、１２０３、１３０３、１４０３、１５０３、１６０１、１６０２、１６０４、１６０５、１６０７、１６０９、１６１０、１８０１、１８０２、１９０１、１９０２、２００１、２００２ プロセッサ
１１７、１１８、１１９、１２０、１２１、１２２、１２３、１２４、１２５、１２６、１２７、１２８、１２９、１３０、１３１、１３２、１３２、１３３、１３４、１３５、１３６、２０１、５１７、５１８、５１９、５２０、５２１、５２２、５２３、５２４、５２５、５２６、５２７、５２８、５２９、５３０、５３１、５３２、５３３、５３４、５３５、５３６、７０１、８０４、９０４、１００４、１１０４、１２０１、１２０２、１２０４、１３０１、１３０２、１３０４、１４０１、１４０２、１４０４、１５０１、１６０４、１６０３、１６０６、１６０８、１７０１、１８０３、１８０４、１８０５、１９０３、１９０４、２００３ スイッチ
２０２、２０３、２０４、２０５、２５１、２５２、２５３、２５４、６５１、６５２、６５３、６５４、７０２、７０３、７０４、７０５、７５１、７５２、７５３、７５４、１７０２、１７０３、１７０４、１７０５ 入力ポート
２０６、２０７、２０８、２０９、２５５、２５６、２５７、２５８、６５５、６５６、６５７、６５８、７０６、７０７、７０８、７０９、７５５、７５６、７５７、７５８、１７０６、１７０７、１７０８、１７０９ 出力ポート
２１０、２１１、２１２、２１３、７１０、７１１、７１２、７１３ 入力ＦＩＦＯメモリ
２１４、７１４、１７１８ クロスバスイッチ
２１５、２１６、２１７、２１８、７１５、７１６、７１７、７１８ 出力ＦＩＦＯメモリ
２１９、２２０、２２１、２２２、３０１、６０１、７１９、７２０、７２１、７２２、１７１９ 調停回路
２２３、２２４、２２５、２２６、７２３、７２４、７２５、７２６ 強度レジスタ
２２７、２２８、２２９、２３０、３１１、３１２、３１３、３１４、６１１、６１２、６１３、６１４、７２７、７２８、７２９、７３０ マルチプレクサ(ＭＵＸ)
２５９、６５９、７５９ 調停手段
２６０、６６０、７６０ 強度情報通知手段
３０２、３０３、３０４、３０５、６０２、６０３、６０４、６０５ 強度カウンタ
３０６、６０６ 選択回路
３０７、３０８、３０９、３１０、６０７、６０８、６０９、６１０ １減算器
３１５、６１５ 強度計算回路
３１６、６１６ 強度合計レジスタ
３１７、３１８、３１９、３２０、６１７、６１８、６１９、６２０ 強度
３２１、３２２、３２３、３２４、６２１、６２２、６２３、６２４ 調停参加信号
４０１ 送り先プロセッサ番号
４０２ 送り元プロセッサ番号
４０３ 調停での強度
４０４ 書き込みアドレス
４０５ データ長
８０６、８０７、８０８、８０９、９０６、９０７、９０８、９０９、１００６、１００７、１００８、１００９、１１０６、１１０７、１１０８、１１０９、１２０６、１２０７、１２０８、１２０９、１３０６、１３０７、１３０８、１３０９、１４０６、１４０７、１４０８、１４０９ 強度カウンタ値
８１０、８１１、８１２、８１３、９１０、９１１、９１２、９１３、１０１０、１０１１、１０１２、１０１３、１１１０、１１１１、１１１２、１１１３、１２１０、１２１１、１２１２、１２１３、１３１０、１３１１、１３１２、１３１３、１４１０、１４１１、１４１２、１４１３ 調停参加信号値
８１４、９１４、１０１４、１１１４、１２１４、１３１４、１４１４ 強度合計レジスタ値
１５０２ 信号線
１７１０、１７１１、１７１２、１７１３、１７１４、１７１５、１７１６、１７１７ ＦＩＦＯメモリ
【技術分野】
【０００１】
本発明は、データ転送システム、スイッチ及びデータ転送方法に関し、特に、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を実行する技術に関する。
【背景技術】
【０００２】
並列コンピュータのプロセッサ間ネットワークとして、Ｆａｔ Ｔｒｅｅが非特許文献１に開示されている。Ｆａｔ Ｔｒｅｅの例として、４入力４出力のスイッチ１５０１で構成された１６入力１６出力のＦａｔ Ｔｒｅｅネットワークを図１９に示す。スイッチ１５０１間の信号線１５０２は双方向リンクを意味している。Ｆａｔ Ｔｒｅｅにプロセッサ０〜プロセッサ１５までの１６個のプロセッサ１５０３が接続されている。なお、図１９では、スイッチ、プロセッサ及び信号線のそれぞれは、１つを除き符号の図示を省略している。
【０００３】
次にＦａｔ Ｔｒｅｅでのルーティングの例を図２０に示す。スイッチ１５０１は、パケットが上方向へＦａｔ Ｔｒｅｅを上る時は入力ポートの対向の出力ポートを使うルーティングを行う。Ｆａｔ Ｔｒｅｅでは、パケットは、送り元プロセッサと宛先プロセッサの共通のスイッチまでＦａｔ Ｔｒｅｅを上り、共通のスイッチまで上がって折り返して下に降りる。たとえば、プロセッサ４(１６０１)からプロセッサ１５(１６０２)への通信は、スイッチＡ(１６０３)が共通のスイッチになる。そのため、パケットは、スイッチＡ(１６０３)まで上がって折り返す。プロセッサ０(１６０４)からプロセッサ３(１６０５)への通信は、スイッチＢ(１６０６)が共通のスイッチになる。そのため、パケットは、スイッチＢ(１６０６)まで上がって折り返す。共通のスイッチは、パケットがＦａｔ Ｔｒｅｅを上がっていく時に各スイッチによって行われるルーティングによって変わる。しかし、どこまで（何段目まで）上がるかは、送り元プロセッサと送り先プロセッサによって決まり、ルーティングによって変わらない。
【０００４】
従って、ある送り先プロセッサへ通信する場合、何個のスイッチを経由するかは送り元プロセッサによって異なってくる。たとえば、パケットをプロセッサ１５(１６０２)へ送る場合、プロセッサ１４(１６０７)から送ったパケットはスイッチＣ(１６０５)１個を経由するだけでプロセッサ１５(１６０２)に到着する。プロセッサ１２(１６０９)とプロセッサ１３(１６１０)から送ったパケットは、スイッチを３個経由してプロセッサ１５(１６０２)に到着する。パケットをプロセッサ０〜プロセッサ１１から送った場合は、パケットがスイッチ５個を経由してプロセッサ１５(１６０２)に到着する。ここで、Ｆａｔ Ｔｒｅｅを上がっていくパケットのルーティングは入力ポートの対向の出力ポートを使用することにしている。そのため、パケットがＦａｔ Ｔｒｅｅを上がっていく時には、スイッチでパケットの競合は発生しない。パケットがＦａｔ Ｔｒｅｅを下っていく時にスイッチでパケットの競合が発生する。
【０００５】
図２１にスイッチの構成の一例を示す。スイッチは、各入力ポート１７０２〜１７０５と各出力ポート１７０６〜１７０９にはＦＩＦＯ(First In First Out)メモリ１７１０〜１７１７がある。ＦＩＦＯメモリ１７１０〜１７１７は、クロスバスイッチ１７１８によって相互に接続されている。同じ出力ポート行きのパケットが複数の入力ポートから来た場合には、パケットが競合することになる。パケットが競合した場合、クロスバスイッチ１７１８において調停回路１７１９によって１つの入力ポートから入力されたパケットが選ばれる。選ばれたパケットは、クロスバスイッチ１７１８を抜けて、出力ポート１７０６〜１７０９のＦＩＦＯメモリ１７１４〜１７１７に書き込まれる。選ばれなかった入力ポートのパケットは入力ポートのＦＩＦＯメモリ１７１０〜１７１３で選ばれるまで待たされる。一般に調停回路１７１９での調停アルゴリズムは、競合したパケットのそれぞれが公平に選択されるように作られる。すなわち、あるパケットが競合調停で負け続けて飢餓状態が発生しないように作られる。Ｎ個のパケットが競合する場合は、その競合調停でそれぞれのパケットが選ばれる確率はＮ分の１と見ることができる（Ｎは、２以上の正整数）。
【０００６】
Ｆａｔ Ｔｒｅｅを下っていく時に１個スイッチを経由するということは、競合調停によってパケットが待たされる可能性があるということである。スイッチは４入力４出力なので、パケットがある出力ポートに行く場合には、３個の入力ポートから入力されたパケット間で競合が発生する可能性がある。従って、パケットがＦａｔ Ｔｒｅｅを下っていく時に経由するスイッチの個数が多いほど、パケットが競合調停で待たされる可能性が高くなる。
【０００７】
たとえば、図２２に示すプロセッサ０(１８０１)からプロセッサ１５(１８０２)への通信の場合は、スイッチＤ(１８０３)、スイッチＥ(１８０４)、スイッチＦ(１８０５)のそれぞれで競合が発生する。各スイッチでは３個のパケットが競合するので、各スイッチにおける競合調停でそれぞれのパケットが選ばれる確立は３分の１となる。従って、プロセッサ０(１８０１)からプロセッサ１５(１８０２)へ送られるパケットは、そのパケットが経由する３つのスイッチの全てで、そのパケットを含む３つのパケットの競合が発生した場合、２７分の１の確率で到着することになる。
【０００８】
一方、図２３に示すプロセッサ１２(１９０１)からプロセッサ１５(１９０２)への通信の場合は、スイッチＥ(１９０３)とスイッチＦ(１９０４)でパケットの競合が発生する。各スイッチでは３個のパケットが競合するので、各スイッチにおける競合調停でそれぞれのパケットが選ばれる確率は３分の１となる。従って、プロセッサ１２(１９０１)からプロセッサ１５(１９０２)へ送られるパケットは、そのパケットが経由する２つのスイッチの全てで、そのパケットを含む３つのパケット間の競合が発生した場合、９分の１の確率で到着することになる。
【０００９】
図２４に示すプロセッサ１４(２００１)からプロセッサ１５(２００２)への通信の場合は、スイッチＦ(２００３)でパケットの競合が発生する。各スイッチでは３個のパケットが競合するので、各スイッチにおける競合調停でそれぞれのパケットが選ばれる確率は３分の１となる。従って、プロセッサ１４(２００１)からプロセッサ１５(２００２)へ送られるパケットは、そのパケットが経由する１つのスイッチで、そのパケットを含む３つのパケット間の競合が発生した場合、３分の１の確率で到着することになる。
【００１０】
このように、Ｆａｔ Ｔｒｅｅでのルーティングでは、あるプロセッサへパケットを送信する場合に、送り元のプロセッサの位置が異なると、パケットが到着するまでに経由するスイッチ数が異なる。そのために、パケットが到着するまでにパケットに対して行われる競合調停の回数が異なり、パケットが到着する確率が異なることになる。つまり、パケットを送信するプロセッサの位置によって、パケットが到着するまでの時間に偏りができてしまうという問題がある。
【００１１】
このようにパケットが転送先に到着するまでの時間に偏りができてしまうと、転送先に到着するまでに時間のかかるパケットによる処理がボトルネックとなってしまい、並列コンピュータシステム全体として処理遅延が発生してしまうという問題がある。
【００１２】
なお、特許文献１には、長経路のパケットや経路上の競合により待たされたパケットによるレイテンシの低下を抑制する優先調停システムが開示されている。この優先調停システムは、複数のＣＰＵ、複数の共有資源、ルーティングテーブル及び複数のクロスバ、を備える。ＣＰＵは、リクエストパケットを共有資源に送信するときに、自ＣＰＵに対応するルーティングテーブルから、送信先の共有資源に対応するレイテンシ値を取り出して、リクエストパケットのパケットヘッダに設定する。クロスバは、複数のパケットを受信したときに、受信した複数のパケットのレイテンシ値を比較して、レイテンシ値が大きなパケットを優先的に通過させる。
【００１３】
しかし、特許文献１に開示の技術は、調停を実行する場合に、各入力ポートから競合するデータを入力する選択割合を、各入力ポートに対応する強度情報に基づいて決定する技術を開示したものではない。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００９−１９４５１０号公報
【非特許文献】
【００１５】
【非特許文献１】"Fat-Trees: Universal Networks for Hardware-Efficient Supercomputing", C. E. Leiserson, IEEE Transactions on Computers, Vol.C-34, No.10, Oct 1985.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
背景技術として説明したように、非特許文献１に開示されている技術では、プロセッサ間で転送するパケットの転送時間に偏りができてしまうという問題がある。
【００１７】
本発明の目的は、上述した課題を解決するために、プロセッサ間で転送するパケットの転送時間の偏りを低減することができるデータ転送システム、スイッチ及びデータ転送方法を提供することにある。
【課題を解決するための手段】
【００１８】
本発明の第１の態様にかかるデータ転送システムは、複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記データ転送部は、次の転送先が同じ競合データについて調停を実行する調停手段と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するものである。
【００１９】
本発明の第２の態様にかかるデータ転送システムは、複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記プロセッサは、初期値を示す強度情報を次の転送先に送信し、前記データ転送部は、次の転送先が同じ競合データについて調停を実行する調停手段と、複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成して、複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定するものである。
【００２０】
本発明の第３の態様にかかるデータ転送システムは、複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記データ転送部は、複数のデータ転送部からデータが入力される複数の入力ポートのそれぞれについて、入力ポートに対して前記複数のプロセッサからデータが転送される転送経路数を示す転送経路数情報を格納する記憶手段と、次に転送する先が同じ競合データについて調停を実行する調停手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定するものである。
【００２１】
本発明の第４の態様にかかるスイッチは、それぞれが複数接続され、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行するスイッチであって、次の転送先が同じ競合データについて調停を実行する調停手段と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するものである。
【００２２】
本発明の第５の態様にかかるデータ転送方法は、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部のそれぞれにおけるデータ転送方法であって、次の転送先が同じ競合データについて調停を実行する調停ステップと、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知ステップと、を備え、前記調停ステップでは、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するものである。
【発明の効果】
【００２３】
上述した本発明の各態様により、プロセッサ間で転送するパケットの転送時間の偏りを低減することができるデータ転送システム、スイッチ及びデータ転送方法を提供することができる。
【図面の簡単な説明】
【００２４】
【図１】本発明の第１の実施の形態の並列コンピュータの概要となるデータ転送システムの構成を示す図である。
【図２】本発明の第１の実施の形態の並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。
【図３】本発明の第１の実施の形態の並列コンピュータのプロセッサ間ネットワークを示す図である。
【図４】本発明の第１の実施の形態の並列コンピュータのプロセッサ間ネットワークのスイッチの構成を示す図である。
【図５】本発明の第１の実施の形態の並列コンピュータのプロセッサ間ネットワークのスイッチの調停回路の構成を示す図である。
【図６】本発明の第１の実施の形態の並列コンピュータのパケットヘッダを示す図である。
【図７】本発明の第１の実施の形態の並列コンピュータの調停回路での処理を説明するフローチャートである。
【図８Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図８Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図９Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図９Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１０Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１０Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１１Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１１Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１２Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１２Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１３Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１３Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１４Ａ】本発明の実施の形態の並列コンピュータの調停回路の状態の一例を示す図である。
【図１４Ｂ】本発明の実施の形態の並列コンピュータのスイッチにおいてパケットが競合した状態の一例を示す図である。
【図１５】本発明の第２の実施の形態の並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。
【図１６】本発明の第２の実施の形態の並列コンピュータの調停回路の構成を示す図である。
【図１７】本発明の第３の実施の形態の並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。
【図１８】本発明の第３の実施の形態の並列コンピュータのスイッチの構成を示す図である。
【図１９】Ｆａｔ Ｔｒｅｅネットワークの構成を示す図である。
【図２０】Ｆａｔ Ｔｒｅｅネットワークのルーティングを説明する図である。
【図２１】スイッチの構成の一例を示す図である。
【図２２】Ｆａｔ Ｔｒｅｅネットワークでの問題点を説明する図である。
【図２３】Ｆａｔ Ｔｒｅｅネットワークでの問題点を説明する図である。
【図２４】Ｆａｔ Ｔｒｅｅネットワークでの問題点を説明する図である。
【発明を実施するための形態】
【００２５】
発明の第１の実施の形態．
まず、図１を参照して、本発明の第１の実施の形態にかかる並列コンピュータの概要となるデータ転送システムについて説明する。図１は、本発明の第１の実施の形態にかかる並列コンピュータの概要となるデータ転送システムの構成を示す図である。
【００２６】
データ転送システム５は、複数のプロセッサ５０１〜５１６及び複数のデータ転送部５１７〜５３６を有する。データ転送部５１７〜５３６は、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する。
【００２７】
続いて、図２を参照して、本発明の第１の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部５１７〜５３６について説明する。図２は、本発明の第１の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部５１７〜５３６の構成を示す図である。
【００２８】
データ転送部２０は、入力ポート２５１〜２５４、出力ポート２５５〜２５８、調停手段２５９及び強度情報通知手段２６０を有する。
入力ポート２５１〜２５４のそれぞれは、複数のデータ転送部５１７〜５３６のうち、いずれかから送信されたデータを入力する。
出力ポート２５５〜２５６のそれぞれは、複数のプロセッサ５０１〜５１６及び複数のデータ転送部５１７〜５３６のうち、いずれかに送信されるデータを出力する。
調停手段２５９は、次の転送先が同じ競合データについて調停を実行する。また、調停手段２５９は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する。
強度情報通知手段２６０は、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する。
【００２９】
続いて、本発明の第１の実施の形態にかかるデータ転送部２０の処理について説明する。
調停手段２５９は、複数のデータ転送部から入力ポートのそれぞれを介して、次の転送先が同じ競合データを受信した場合、受信した競合データの調停を実行する。調停手段２５９は、調停において、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する。調停手段２５９は、決定した選択割合で、競合データの調停を実行する。
強度情報通知手段２６０は、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する。
【００３０】
次に、本発明の実施の形態について図面を参照して、本発明の第１の実施の形態にかかる並列コンピュータについて詳細に説明する。図３を参照すると、本発明の第１の実施の形態としての並列コンピュータが示されている。
並列コンピュータ１は、プロセッサ１０１〜１１６、及び、プロセス間ネットワーク１０を有する。プロセス間ネットワーク１０２は、スイッチ１１６〜１３６を有する。
【００３１】
図３において、複数のプロセッサ１０１〜１１６がプロセッサ間ネットワーク１０によって接続されている。ここでは、１６個のプロセッサ１０１〜１１６がプロセッサ間ネットワーク１０に接続された並列コンピュータを示しているが、プロセッサ間ネットワーク１０に接続されるプロセッサ１０１〜１１６の数は任意である。プロセッサ間ネットワーク１０は、４入力４出力のスイッチ１１７〜１３６によって構成される。つまり、スイッチ１１７〜１３６は、４つの入力ポートと４つの出力ポートとを有する。プロセス間ネットワーク１０は、Ｆａｔ Ｔｒｅｅのトポロジとなっている。
【００３２】
ここでは、プロセッサ間ネットワークＦａｔ Ｔｒｅｅは４入力４出力のスイッチ１１７〜１３６によって構成されているが、Ｎ入力Ｎ出力（Ｎは任意の数）のスイッチで構成されていてもよい。ここで、最上段スイッチ１３３〜１３６でのポート番号は、左から順に０、１、２、３と付けることにする。また、中段のスイッチ１２５〜１３２と、最下段のスイッチ１１１７〜１２４のポート番号は、下側の左から０、１、上側の左から２、３と付けることにする。
【００３３】
つまり、スイッチ１１６〜１３５は、ポート番号が０〜３の４つの入力ポートと、ポート番号が０〜３の４つの出力ポートとを有する。そして、図２に示すように、ポート番号０〜３の入力ポート及び出力ポートのそれぞれは、いずれか１つのプロセッサ又はスイッチと接続される。例えば、スイッチ１３１のポート番号０の入力ポートは、スイッチ１２３のポート番号２の出力ポートから出力されたパケットが入力される。また、スイッチ１３１のポート番号０の出力ポートは、スイッチ１２３のポート番号２の入力ポートにパケットを出力する。
【００３４】
図４を参照すると、図３に示す４入力４出力のスイッチ１１６〜１３５の１つの実施例が示されている。スイッチ２０１は、４つの入力ポート２０２〜２０５と４つの出力ポート２０６〜２０９をもつ。スイッチ２０１は、各入力ポート２０２〜２０５のそれぞれに対応するように、入力ＦＩＦＯメモリ２１０〜２１３と、調停での強度を格納する強度レジスタ２２３〜２２６とを有する。入力ＦＩＦＯメモリ２１０〜２１３は、自身に対応する入力ポート２０２〜２０５に入力されたパケットがＦＩＦＯ方式で格納される。入力ＦＩＦＯメモリ２１０〜２１３のそれぞれは、ＦＩＦＯの先頭のパケットのパケットヘッダ含まれる調停での強度を、自身に対応する強度レジスタ２２３〜２２６のそれぞれに出力する。入力ＦＩＦＯメモリ２１０〜２１３は、例えば、ＦＩＦＯにパケットが格納されていない場合、０を強度レジスタ２２３〜２２６に格納する。なお、パケットのパケットヘッダに含まれる調停での強度については、後に詳述する。調停回路２１９〜２２２は、調停手段２５９及び強度通知手段２６０として機能する。
【００３５】
強度レジスタ２２３〜２２６には入力ＦＩＦＯメモリ２１０〜２１３から出力された調停での強度が格納される。強度レジスタ２２３〜２２６は、自身に格納された調停での強度を示す信号を調停回路２１９〜２２２に出力する。また、入力ＦＩＦＯメモリ２１０〜２１３は、自身に格納された先頭のパケットを、マルチプレクサ(ＭＵＸ)２２７〜２３０に出力する。また、入力ＦＩＦＯメモリ２１０〜２１３は、パケットを出力しているときに、そのパケットを出力する出力ポートに対応する調停回路に、調停参加信号(図示せず)を出力する。
【００３６】
入力ＦＩＦＯメモリ２１０〜２１３は、例えば、パケットのパケットヘッダに含まれる送り先プロセッサ番号に基づいて、パケットを出力する出力ポートを判定する。例えば、入力ＦＩＦＯメモリ２１０〜２１３は、送り先プロセッサ番号からパケットを出力すべき出力ポートを求めることができるルーティングテーブルが格納される。そして、入力ＦＩＦＯメモリ２１０〜２１３は、自身に格納されるルーティングテーブルに基づいて、パケットを出力する出力ポートを判定する。なお、パケットのパケットヘッダに含まれる送り先プロセッサ番号については、後に詳述する。
【００３７】
スイッチ２０１は、各出力ポート２０６〜２０９のそれぞれに対応するように、調停回路２１９〜２２２と出力ＦＩＦＯメモリ２１５〜２１８とを有する。また、スイッチ２０１は、クロスバスイッチ２１４を有する。クロスバスイッチ２１４は、出力ポート２０６〜２０９のそれぞれに対応するように、マルチプレクサ(ＭＵＸ)２２７〜２３０を有する。クロスバスイッチ２１４が、入力ＦＩＦＯメモリ２１０〜２１３と出力ＦＩＦＯメモリ２１５〜２１８を接続している。
【００３８】
調停回路２１９〜２２２は、各強度レジスタ２２３〜２２６から出力された調停での強度と、各入力ＦＩＦＯメモリ２１０〜２１３から出力された調停参加信号をもとに、クロスバスイッチ２１４内の対応するマルチプレクサ(ＭＵＸ)２２７〜２３０を制御してパケットをルーティングする。マルチプレクサ２２７〜２３０は、自身に対応する調停回路からの制御に応じて、入力ＦＩＦＯメモリ２１０〜２１３のそれぞれから出力されたパケットのいずれかを選択して、自身に対応する出力ＦＩＦＯメモリ２１５〜２１８に出力する。
【００３９】
次に図５を使って、調停回路２１９〜２２２の詳細な構成を説明する。調停回路３０１は、強度カウンタ３０２〜３０５、選択回路３０６、１減算器３０７〜３１０、マルチプレクサ(ＭＵＸ)３１１〜３１４、強度計算回路３１５及び強度合計レジスタ３１６を有する。
【００４０】
調停回路３０１には、４つの入力ポート２０２〜２０５のそれぞれに対応する強度３１７〜３２０と調停参加信号３２１〜３２４が入力される。また、調停回路３０１は、各入力ポートに対応して、４つの強度カウンタ３０２〜３０５と、４つの１減算器３０７〜３１０と、４つのマルチプレクサ(ＭＵＸ)３１１〜３１４とを有する。調停回路３０１に入力された強度３１７〜３２０は、自身に対応するマルチプレクサ(ＭＵＸ)と、強度計算回路３１５とに入力される。調停回路３０１に入力された調停参加信号３２１〜３２４は、選択回路３０６及び強度計算回路３１５に入力される。
【００４１】
マルチプレクサ(ＭＵＸ)３１１〜３１４は、自身に入力された強度３１７〜３２０、又は、１減算器３０７〜３１０から出力された強度カウンタ値のいずれかを選択して強度カウンタ３０２〜３０５に出力する。強度カウンタ３０２〜３０５には、マルチプレクサ(ＭＵＸ)３１１〜３１４から出力された強度３１７〜３２０又は強度カウンタ値が、強度カウンタ値として格納される。つまり、強度カウンタ３０２〜３０５に格納される強度カウンタ値をカウントダウンする場合、マルチプレクサ(ＭＵＸ)３１１〜３１４は、１減算器３０７〜３１０から出力された強度カウンタ値を選択して強度カウンタ３０２〜３０５に出力する。強度カウンタ３０２〜３０５は、強度カウンタ値を選択回路３０６に出力する。
【００４２】
選択回路３０６は、強度カウンタ３０２〜３０５から出力された強度カウンタ値と、調停参加信号３２１〜３２４とに基づいて、１つの入力ポートのパケットを選択する。選択回路３０６は、選択した入力ポートのパケットを選択して出力するように制御する選択信号を、マルチプレクサ(ＭＵＸ)２２７〜２３０に出力する。選択処理については、後で図７を使って説明する。
【００４３】
強度計算回路３１５は、強度３１７〜３２０と調停参加信号３２１〜３２４を使って、調停参加している入力ポートの強度の合計値を算出する。強度計算回路３１５は、算出した強度の合計値を強度合計レジスタ３１６に書き込む。そして、調停回路３０１は、クロスバスイッチ２１４から出ていくパケットのパケットヘッダに強度合計レジスタ３１６内の強度の合計値を書き込む。
【００４４】
次に本実施の形態でのパケットのパケットヘッダについて、図６に示す。パケットヘッダには、送り先プロセッサ番号４０１と、送り元プロセッサ番号４０２と、調停での強度４０３、書き込みアドレス４０４、データ長４０５が格納される。パケットヘッダの後には、データ長４０５で示されたバイト数のデータ(図示せず)が続く。プロセッサ１０１〜１１５は、パケットを送る時に、調停での強度４０３を１に初期化する。調停での強度４０３は、各スイッチ１１７〜１３６通過時にスイッチ１１７〜１３６で更新される。書き込みアドレス４０４は、パケットが送り先のプロセッサに到着した場合に、データが書き込まれるメモリ上のアドレスである。
【００４５】
次に、図５の調停回路３０１での処理について、図７使って説明する。
まず、調停回路３０１は、すべての強度カウンタ３０２〜３０５を対応する強度レジスタ２２３〜２２６から出力された強度３１７〜３２０で初期化する（ステップＳ１０１）。これは、マルチプレクサ(ＭＵＸ)３１１〜３１４で強度３１７〜３２０を選択することにより行う。また、この時に、調停回路３０１は、強度合計レジスタ３１６に０を格納して、強度合計レジスタ３１６を初期化する。
【００４６】
次に、選択回路３０６は、入力ＦＩＦＯメモリ２１０〜２１３から出力された調停参加信号３２１〜３２４を参照し、新たな調停参加者を受け付ける（ステップＳ１０２）。具体的には、選択回路３０６は、入力ＦＩＦＯメモリ２１０〜２１３のいずれかから調停参加信号が入力された場合、入力された調停参加信号に対応する入力ポートを調停参加者として決定する。また、この時に、強度計算回路３１５は、強度３１７〜３２０のうち、調停参加している入力ポートに対応する強度の合計値を強度合計レジスタ３１６に格納する。以降、選択回路３０６は、再びステップＳ１０１になるまで、一度参加した調停参加者を、調停参加者として認識し続ける。
【００４７】
次に、調停回路３０１は、すべての調停参加者の強度カウンタの値が１かどうかを調べる（ステップＳ１０３）。すべての調停参加者の強度カウンタの値が１でない場合（ステップＳ１０３：いいえ）は、選択回路３０６は、強度カウンタの値が最も大きい調停参加者を選択する（ステップＳ１０４）。具体的には、選択回路３０６は、最も大きい強度カウンタ値を出力する強度カウンタに対応する入力ポートの入力ＦＩＦＯメモリから出力されたパケットを選択する選択信号をクロスバスイッチ２１４のマルチプレクサ(ＭＵＸ)に出力する。なお、選択回路３０６は、選択する入力ＦＩＦＯメモリから、調停参加信号が出力されていない場合は、調停参加信号が出力されるのを待ってから、その入力ＦＩＦＯメモリから出力されたパケットを選択する。これによって、選択回路３０６が含まれる調停回路に対応する出力ポートに、その出力ポート以外へのパケットを誤って出力しないようにする。選択回路３０６は、調停回路３０１は、そのパケットがクロスバスイッチ２１４を抜けてきた時点で強度合計レジスタ３１６の強度の合計値をパケットヘッダの調停での強度のフィールドに書き込む（ステップＳ１０５）。
【００４８】
そして、選択回路３０６は、強度カウンタ値が最も大きい調停参加者として選択した入力ポートに対応する強度カウンタの値をデクリメントする（ステップＳ１０６）。強度カウンタ３０２〜３０５の値のデクリメントは、マルチプレクサ(ＭＵＸ)３１１〜３１４で１減算器３０７〜３１０の方を選択することにより行う。この選択は、例えば、選択回路３０６が、マルチプレクサ(ＭＵＸ)３１１〜３１４に、１減算器３０７〜３１０からの出力を選択する選択信号を出力することにより行う。
【００４９】
その後、選択回路３０６は、ステップＳ１０２にすすみ、入力ポートからの調停参加信号３２１〜３２４を参照し、新たな調停参加者を受け付ける（ステップＳ１０２）。このときに、入力ＦＩＦＯメモリ２１０〜２１３は、選択されたパケットの次にＦＩＦＯに含まれるパケットを、ＦＩＦＯの先頭のパケットにする。そして、入力ＦＩＦＯメモリ２１０〜２１３は、先頭のパケットを、マルチプレクサ(ＭＵＸ)２２７〜２３０に出力する。また、選択回路３０６は、この時点で、新たに調停参加者として選択していない入力ポートに対応する調停参加信号が入力されている場合、その入力ポートを新たな調停参加者として受け入れる。その場合、選択回路３０６は、その入力ポートに対応する強度カウンタを初期化する。また、強度計算回路３１５は、新たに調停参加者として参加した入力ポートに対応する強度と、強度合計レジスタ３１６に格納された強度の合計値との合計値を、強度合計レジスタ３１６に格納する。
【００５０】
次にステップＳ１０３で、すべての調停参加者の強度カウンタの値が１であった場合について説明する（ステップＳ１０３：はい）。調停回路３０１は、まず、強度カウンタの値が１の調停参加者を１人選択する（ステップＳ１０７）。選択の仕方は、予め決められた優先順位でもラウンドロビンでもよい。そして、選択回路３０６は、選択した入力ポートに対応する入力ＦＩＦＯメモリから出力されたパケットを選択する選択信号をクロスバスイッチ２１４のマルチプレクサ(ＭＵＸ)に出力する。調停回路３０１は、そのパケットがクロスバスイッチ２１４を抜けてきた時点で強度合計レジスタ３１６の強度の合計値をパケットヘッダの調停での強度のフィールドに書き込む（ステップＳ１０８）。そして、選択した入力ポートに対応する強度カウンタの値をデクリメントする（ステップＳ１０９）。次に、調停回路３０１は、強度カウンタの値が１となった調停参加者のうちで選ばれていない調停参加者がいるかどうかを調べる（ステップＳ１１０）。つまり、調停回路３０１は、値が０になっていない強度カウンタに対応する調停参加者がいるかどうかを調べる。選ばれていない調停参加者がいる場合（ステップＳ１１０：はい）は、ステップＳ１０７に戻る。そうでない場合（ステップＳ１１０：いいえ）は、ステップＳ１０１へ戻り、強度カウンタ３０２〜３０５を初期化する。
【００５１】
以上に説明したように、調停回路３０１は、調停参加した入力ポートのそれぞれに入力されたパケットに含まれる強度を、入力ポートのそれぞれから選択して次段に出力するパケットの数としている。言い換えると、調停回路３０１は、調停参加した入力ポートのそれぞれに入力されたパケットに含まれる強度を、入力ポートのそれぞれから調停対象として取り込むパケット数としている。よって、調停参加した入力ポートのそれぞれからの強度の合計値は、調停回路３０１が調停対象としたパケット数となる。言い換えると、強度の合計値は、それぞれの出力先が競合することによって、調停回路３０１によって調停が行われたパケットの競合数である。そして、調停回路３０１は、強度の合計値を、強度としてパケットに含めて、そのパケットを次段に出力するようにしている。つまり、これによって、各スイッチは、複数の次段のスイッチのそれぞれについて、次段のスイッチに転送するパケットが自身に集中する度合いを、強度として次段のスイッチに伝えることができる。
【００５２】
そのため、調停回路３０１は、入力ポートのそれぞれに入力されたパケットに含まれる強度が示す競合数分のパケットを、それぞれの入力ポートから選択して次段に出力するようにしている。つまり、これにより、調停回路３０１は、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができる。
【００５３】
次に、図８〜図１４を使って、プロセッサ０(１０１)〜プロセッサ１４(１１５)がプロセッサ１５(１１６)に通信する場合の、本発明での動作と効果を説明する。
【００５４】
図８Ｂは、スイッチ８０４においてパケットが競合した状態を示す図である。図８Ｂは、スイッチ ８０４において、プロセッサ０(８０１)、プロセッサ４(８０２)、プロセッサ８(８０３)からプロセッサ１５(８０５)へ送信されたパケットが競合した場合について例示している。スイッチ８０４での出力ポート３の調停回路の状態を図８Ａに図示している。入力ポート０〜２の強度カウンタ８０６〜８０９には、初期値として、プロセッサ８０１、８０２、８０３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加８１０〜８１２に１が、調停参加８１３に０が格納されている。
【００５５】
ここで、調停参加８１０〜８１３は、例えば、調停回路が有する調停参加レジスタである。調停回路は、入力ポート０〜３のそれぞれに対応する調停参加レジスタを有する。調停回路は、ステップＳ１０２において、調停参加信号が入力された場合、その調停参加信号に対応する入力ポートの調停参加レジスタに１を格納する。調停回路は、ステップＳ１０１において、調停参加レジスタに０を格納して初期化する。
【００５６】
そして、強度合計レジスタ８１４には、調停での強度の合計である３が格納される。調停回路３０１は、スイッチ８０４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度に３を格納する。図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度カウンタ８０６〜８０８の値はすべて１なので、調停回路３０１は、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００５７】
図９Ｂは、スイッチ９０４においてパケットが競合した状態を示す図である。図９Ｂは、スイッチ９０４において、プロセッサ２(９０１)、プロセッサ６(９０２)、プロセッサ１０(９０３)からプロセッサ１５(９０５)へ送信されたパケットが競合した場合について例示している。スイッチ９０４での出力ポート３の調停回路の状態を図９Ａに図示している。入力ポート０〜２の強度カウンタ９０６〜９０８には、初期値として、プロセッサ９０１、９０２、９０３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加９１０〜９１２に１が、調停参加９１３に０が格納されている。そして、強度合計レジスタ９１４には、調停での強度の合計である３が格納される。スイッチ９０４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度には３が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度カウンタ９０６〜９０８の値はすべて１なので、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００５８】
図１０Ｂは、スイッチ１００４においてパケットが競合した状態を示す図である。図１０Ｂは、スイッチ １００４において、プロセッサ１(１００１)、プロセッサ５(１００２)、プロセッサ９(１００３)からプロセッサ１５(１００５)へ送信されたパケットが競合した場合について例示している。スイッチ１００４での出力ポート３の調停回路の状態を図１０Ａに図示している。入力ポート０〜２の強度カウンタ１００６〜１００８には、初期値として、プロセッサ１００１、１００２、１００３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加１０１０〜１０１２に１が、調停参加１０１３に０が格納されている。そして、強度合計レジスタ１０１４には、調停での強度の合計である３が格納される。スイッチ１００４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度には３が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度カウンタ１００６〜１００８の値はすべて１なので、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００５９】
図１１Ｂは、スイッチ１１０４においてパケットが競合した状態を示す図である。図１１Ｂは、スイッチ１１０４において、プロセッサ３(１１０１)、プロセッサ７(１１０２)、プロセッサ１１(１１０３)からプロセッサ１５(１１０５)へ送信されたパケットが競合した場合について例示している。スイッチ１１０４での出力ポート３の調停回路の状態を図１１Ａに図示している。入力ポート０〜２の強度カウンタ１１０６〜１１０８には、初期値として、プロセッサ１１０１、１１０２、１１０３のそれぞれから送信されたパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート０〜２が調停参加しているので、調停参加 １１１０〜１１１２に１が、調停参加１１１３に０が格納されている。そして、強度合計レジスタ１１１４には、調停での強度の合計である３が格納される。スイッチ １１０４を通過し出力ポート３に出力されるパケットのパケットヘッダの調停での強度には３が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、調停参加しているポート０〜２の強度レジスタ１１０６〜１１０８の値はすべて１なので、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。
【００６０】
図１２Ｂは、スイッチ１２０４においてパケットが競合した状態を示す図である。図１２Ｂは、スイッチ１２０４において、プロセッサ１２(１２０３)とスイッチ１２０１とスイッチ１２０２とから送信されたパケットが競合した場合について例示している。スイッチ１２０４での出力ポート１の調停回路を図１２Ａに図示している。入力ポート０の強度カウンタ１２０６には、初期値として、プロセッサ１２(１２０３)からのパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート２と入力ポート３の強度カウンタ１２０８、１２０９には、初期値として、スイッチ１２０１とスイッチ１２０２からのパケットのパケットヘッダの調停での強度３が格納される。つまり、ここでは、スイッチ１２０１とスイッチ１２０２のそれぞれおいて、パケットが競合して、パケットヘッダの調停での強度が３に更新された場合について例示している。
【００６１】
また、入力ポート０、入力ポート２、入力ポート３が調停参加しているので、調停参加１２１０、１２１２、１２１３に１が、調停参加１２１１に０が格納されている。そして、強度合計レジスタ１２１４には、調停での強度の合計である７が格納される。スイッチ １２０４を通過し出力ポート１に出力されるパケットのパケットヘッダの調停での強度には７が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、参加者の強度カウンタの値は１、３、３となっているので、ステップＳ１０３の後に、強度カウンタの値が１、１、１になるまでは、ステップＳ１０４の処理を実行する。このときに実行されるステップＳ１０４の処理では、入力ポート２と入力ポート３からのパケットが選択される。調停回路３０１は、強度カウンタの値が１、１、１になれば、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。そして、ステップＳ１０７〜Ｓ１１０の処理において、入力ポート０、入力ポート２、入力ポート３からパケットが１つずつ選択される。
【００６２】
図１３Ｂは、スイッチ１３０４においてパケットが競合した状態を示す図である。スイッチ１３０４では、プロセッサ１３(１３０３)とスイッチ１３０１とスイッチ１３０２とから送信されたパケットが競合した場合について例示している。スイッチ１３０４での出力ポート１の調停回路を図１３Ａに図示している。入力ポート０の強度カウンタ１３０６には、初期値として、プロセッサ１３(１３０３)からのパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート２と入力ポート３の強度レジスタ１３０８、１３０９には、初期値として、スイッチ１３０１とスイッチ１３０２からのパケットのパケットヘッダの調停での強度３が格納される。つまり、ここでは、スイッチ１３０１とスイッチ１３０２のそれぞれおいて、パケットが競合して、パケットヘッダの調停での強度が３に更新された場合について例示している。
【００６３】
また、入力ポート０、入力ポート２、入力ポート３が調停参加しているので、調停参加 １３１０、１３１２、１３１３に１が、調停参加 １３１１に０が格納されている。そして、強度合計レジスタ１３１４には、調停での強度の合計である７が格納される。スイッチ １３０４を通過し出力ポート１に出力されるパケットのパケットヘッダの調停での強度には７が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、参加者の強度カウンタの値は１、３、３となっているので、ステップＳ１０３の後に、強度カウンタの値が１、１、１になるまでは、ステップＳ１０４の処理を実行する。このときに実行されるステップＳ１０４の処理では、入力ポート２と入力ポート３からのパケットが選択される。調停回路３０１は、強度カウンタの値が１、１、１になれば、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。そして、ステップＳ１０７〜Ｓ１１０の処理において、入力ポート０、入力ポート２、入力ポート３からパケットが１つずつ選択される。
【００６４】
図１４Ｂは、スイッチ１４０４においてパケットが競合した状態を示す図である。スイッチ１４０４では、プロセッサ１４(１４０３)とスイッチ１４０１とスイッチ１４０２とから送信されたパケットが競合した場合について例示している。スイッチ１４０４での出力ポート１の調停回路を図１４Ａに図示している。入力ポート０の強度カウンタ１４０６には、初期値として、プロセッサ１４(１４０３)からのパケットのパケットヘッダの調停での強度１が格納される。また、入力ポート２と入力ポート３の強度レジスタ１４０８、１４０９には、初期値として、スイッチ１４０１とスイッチ１４０２からのパケットのパケットヘッダの調停での強度７が格納される。つまり、ここでは、スイッチ１４０１とスイッチ１４０２のそれぞれと、それぞれのスイッチの前段のスイッチにおいて、パケットが競合して、パケットヘッダの調停での強度が７に更新された場合について例示している。
【００６５】
また、入力ポート０、入力ポート２、入力ポート３が調停参加しているので、調停参加 １４１０、１４１２、１４１３に１が、調停参加１４１１に０が格納されている。そして、強度合計レジスタ１４１４には、調停での強度の合計である１５が格納される。スイッチ １４０４を通過し出力ポート１に出力されるパケットのパケットヘッダの調停での強度には１５が格納される。調停回路３０１は、図７のステップＳ１０１で強度カウンタを初期化したあとは、参加者の強度カウンタの値は１、７、７となっているので、ステップＳ１０３の後に、強度カウンタの値が１、１、１になるまでは、ステップＳ１０４の処理を実行する。このときに実行されるステップＳ１０４の処理では、入力ポート２と入力ポート３からのパケットが選択される。調停回路３０１は、強度カウンタの値が１、１、１になれば、ステップＳ１０３の後に、ステップＳ１０７の処理を実行する。そして、ステップＳ１０７〜Ｓ１１０の処理において、入力ポート０、入力ポート２、入力ポート３からパケットが１つずつ選択される。
【００６６】
次に、この場合の各プロセッサからプロセッサ１５への到着確率を計算する。それぞれの経由するスイッチ数が異なる、プロセッサ０、プロセッサ１２、プロセッサ１４からのパケットの到着確率を計算する。まず、プロセッサ０からのパケットは、３つのスイッチを経由する。それぞれのスイッチにおいて３つのパケットが競合した場合に、それぞれのスイッチにおいて、プロセッサ０から送信したパケットが選択される確率は、３分の１、７分の３、１５分の７になる。よって、これらの確率の積は、１５分の１になる。次にプロセッサ１２からのパケットは、２つのスイッチを経由する。それぞれのスイッチにおいて３つのパケットが競合した場合に、それぞれのスイッチにおいて、プロセッサ１２から送信したパケットが選択される確率は、７分の１、１５分の７になるよって、これらの確率の積は１５分の１になる。最後にプロセッサ１４からのパケットは、１つのスイッチを経由して１５分の１となる。
【００６７】
このように、本実施の形態では、プロセッサ０〜１４のそれぞれからプロセッサ１５に出力されるパケットのように、それぞれのパケットが経由するスイッチ数が異なってもプロセッサ１５への到着確率が１５分の１となる。したがって、どのプロセッサから出力されるパケットも転送先のプロセッサに到着する確率が同じになることがわかる。つまり、どのプロセッサから出力されるパケットも転送先のプロセッサに到着するまでにかかる時間を一定化することができる。つまり、本発明の第１の実施の形態によれば、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。
【００６８】
発明の第２の実施の形態．
続いて、図１５を参照して、本発明の第２の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部について説明する。図１５は、本発明の第２の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。なお、本発明の第２の実施の形態にかかる並列コンピュータの概要となるデータ転送システムの構成は、発明の第１の実施の形態にかかるデータ転送システムの構成と同様であるため、説明を省略する。
【００６９】
データ転送部６０は、入力ポート６５１〜６５４、出力ポート６５５〜６５８、調停手段６５９及び強度情報通知手段６６０を有する。
入力ポート６５１〜６５４のそれぞれは、複数のデータ転送部５１７〜５３６のうち、いずれかから送信されたデータを入力する。
出力ポート６５５〜６５６のそれぞれは、複数のプロセッサ５０１〜５１６及び複数のデータ転送部５１７〜５３６のうち、いずれかに送信されるデータを出力する。
調停手段６５９は、次の転送先が同じ競合データについて調停を実行する。また、調停手段６５９は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定する。
強度情報通知手段６６０は、複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成する。強度情報通知手段６６０は、生成した強度情報を複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する。
【００７０】
続いて、本発明の第２の実施の形態にかかるデータ転送部６０の処理について説明する。
複数のプロセッサ５０１〜５１６は、初期値を示す強度情報を転送先のデータ転送部に出力する。強度情報通知手段６６０は、複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成する。強度情報通知手段６６０は、生成した強度情報を複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する。
調停手段６５９は、複数のデータ転送部から入力ポートのそれぞれを介して、次の転送先が同じ競合データを受信した場合、受信した競合データの調停を実行する。調停手段６５９は、調停において、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定する。調停手段６５９は、決定した選択割合で、競合データの調停を実行する。
【００７１】
続いて、本発明の第２の実施の形態にかかる並列コンピュータについて詳細に説明する。図１６を参照して、本発明の第２の実施の形態にかかる調停回路６０１について説明する。なお、本発明の第２の実施の形態にかかる並列コンピュータ及びスイッチの構成は、発明の第１の実施の形態にかかる並列コンピュータ及びスイッチの構成と同様であるため、説明を省略する。また、本発明の第２の実施の形態にかかる調停回路６０１の処理についても、図７に示す処理と同様であるため、説明を省略する。
【００７２】
図１６を参照すると、本発明の第２の実施の形態としての並列コンピュータのプロセッサ間ネットワークを構成するスイッチの中の調停回路 ６０１が示されている。第２の実施の形態が第１の実施の形態と異なるのは、調停回路６０１の部分である。本実施の形態の調停回路６０１は、強度計算回路６１５に調停参加信号６２１〜６２４が入力されない点が、第１の実施の形態の調停回路３０１と異なる。
【００７３】
第２の実施の形態の調停回路６０１の強度計算回路６１５は、調停参加の状態を考慮せずに、強度の合計値を計算する。そして、強度計算回路６１５は、算出した強度の合計値を強度合計レジスタ６１６に格納する。調停回路６０１は、次段のスイッチに送出するパケットのパケットヘッダの調停での強度に、強度合計レジスタ６１６に格納された強度の合計値を設定する。調停回路６０１は、例えば、ステップＳ１０２のタイミングで、強度６１７〜６２０の合計値を強度合計レジスタ６１６に格納するようにしてもよい。また、調停回路６０１は、ステップＳ１０２のタイミングで、強度６１７〜６２０のうち、強度が０から０以外の値に変化した強度と、強度合計レジスタ６１６に格納される値との合計値を強度合計レジスタ６１６に格納するようにしてもよい。
【００７４】
以上に説明したように、まず、プロセッサ１０１〜１１６は、パケットの強度に初期値１を設定して出力する。調停回路６０１は、所定の期間内に、入力ポートのそれぞれに入力されたパケットに含まれる強度の合計値を、強度としてパケットに含めて、そのパケットを次段のスイッチのそれぞれに出力するようにしている。つまり、これによって、各スイッチは、パケットが自身に集中する度合いを、強度として次段のスイッチに伝えることができる。
【００７５】
そして、調停回路６０１は、入力ポートのそれぞれに入力されたパケットに含まれる強度が示す値分のパケットを、それぞれの入力ポートから選択して次段に出力するようにしている。つまり、これにより、調停回路６０１は、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができる。
【００７６】
つまり、本発明の第２の実施の形態によれば、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。また、本発明の第２の実施の形態では、入力ＦＩＦＯバッファ２２３〜２２６から強度計算回路６１５に調停参加信号を伝送する信号線が不要となるため、回路規模を抑えることができる。
【００７７】
発明の第３の実施の形態．
続いて、図１７を参照して、本発明の第３の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部について説明する。図１７は、本発明の第３の実施の形態にかかる並列コンピュータのスイッチの概要となるデータ転送部の構成を示す図である。なお、本発明の第３の実施の形態にかかる並列コンピュータの概要となるデータ転送システムの構成は、発明の第１の実施の形態にかかるデータ転送システムの構成と同様であるため、説明を省略する。
【００７８】
データ転送部７０は、入力ポート７５１〜７５４、出力ポート７５５〜７５８、調停手段７５９及び記憶手段７６０を有する。
入力ポート７５１〜７５４のそれぞれは、複数のデータ転送部のうち、いずれかから送信されたデータを入力する。
出力ポート７５５〜７５６のそれぞれは、複数のプロセッサ及び複数のデータ転送部のうち、いずれかに送信されるデータを出力する。
調停手段７５９は、次の転送先が同じ競合データについて調停を実行する。また、調停手段７５９は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定する。
記憶手段７６０は、複数のデータ転送部から自データ転送部にデータが入力される複数の入力ポートのそれぞれについて、前記複数のプロセッサから入力ポートにデータが転送される転送経路数を示す転送経路数情報を格納する。
【００７９】
続いて、本発明の第３の実施の形態にかかるデータ転送部７０の処理について説明する。
調停手段７５９は、複数のデータ転送部から入力ポートのそれぞれを介して、次の転送先が同じ競合データを受信した場合、受信した競合データの調停を実行する。調停手段７５９は、調停において、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定する。調停手段７５９は、決定した選択割合で、競合データの調停を実行する。
【００８０】
続いて、本発明の第３の実施の形態にかかる並列コンピュータについて詳細に説明する。図１８を参照して、本発明の第２の実施の形態にかかるスイッチ７０１について説明する。なお、本発明の第３の実施の形態にかかる並列コンピュータの構成は、発明の第１の実施の形態にかかる並列コンピュータの構成と同様であるため、説明を省略する。本発明の第３の実施の形態にかかる調停回路の構成は、強度計算回路３１５及び強度合計レジスタ３１６を有しない点を除き、発明の第１の実施の形態にかかる並列コンピュータの構成と同様であるため、説明を省略する。また、本発明の第３の実施の形態にかかる調停回路の処理についても、図７に示す処理と同様であるため、説明を省略する。
【００８１】
図１８を参照すると、本発明の第３の実施の形態としての並列コンピュータのプロセッサ間ネットワークを構成するスイッチ７０１が示されている。第３の実施の形態が第１の実施の形態と異なるのは、スイッチ７０１で、強度レジスタ７２３〜７２６に設定する調停での強度をパケットヘッダから読み出して設定するのではなく、スイッチの接続形態からあらかじめ設定しておくことである。
【００８２】
具体的には、それぞれの強度レジスタ７２３〜７２６に、それぞれの強度レジスタ７２３〜７２６に対応する入力ポートに対してプロセッサ１０１〜１１６からパケットが転送される転送経路数を格納する。ここで、図１２Ｂに例示するスイッチ１２０４を例に挙げて説明する。スイッチ１２０４の入力ポート０には、１つのプロセッサ１２からパケットが転送される。したがって、入力ポート０に対応する入力強度レジスタ０(７２３)には１が格納される。スイッチ１２０４の入力ポート１には、１つのプロセッサ１４からパケットが転送される。よって、入力ポート１に対応する入力強度レジスタ１(７２４)には１が格納される。スイッチ１２０４の入力ポート２には、３つのプロセッサ０、４、８からパケットが転送される。よって、入力ポート２に対応する入力強度レジスタ２(７２５)には３が格納される。スイッチ１２０４の入力ポート３には、３つのプロセッサ１、５、９からパケットが転送される。よって、入力ポート３に対応する入力強度レジスタ３(７２６)には３が格納される。
【００８３】
以上に説明したように、強度レジスタ７２３〜７２６には、強度レジスタ７２３〜７２６に対応する入力ポートに入力されるパケットがプロセッサ１０１〜１１６から転送される転送経路数が強度として格納されている。ここで、入力ポートに対してプロセッサ１０１〜１１６からデータが転送される転送経路数が多い場合、その入力ポートに入力されるパケット数も多くなる。つまり、スイッチは、強度レジスタ７２３〜７２６のそれぞれに格納される強度は、入力ポート７０２〜７０５のそれぞれにパケットが集中する度合いとなる。
【００８４】
そして、調停回路７１９〜７２２は、入力ポートのそれぞれに対応する強度レジスタ７２３〜７２６から出力される強度が示す転送経路数分のパケットを、それぞれの入力ポートから選択して次段に出力するようにしている。つまり、これにより、調停回路６０１は、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができる。
【００８５】
つまり、本発明の第３の実施の形態によれば、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。また、本発明の第３の実施の形態では、強度計算回路及び強度合計レジスタと、調停回路７１９〜７２２にいてパケットに強度を設定する処理と、入力ＦＩＦＯメモリ７１０〜７１３において強度レジスタに強度を設定する処理とが不要となるため、回路規模を抑えることができる。また、パケットに調停での強度を格納する領域も不要となるため、プロセス間ネットワークにおいて転送されるデータ量を低減することもできる。
【００８６】
なお、本発明は上記実施の形態に限られたものではなく、趣旨を逸脱しない範囲で適宜変更することが可能である。
【００８７】
プロセッサの数及びプロセス間ネットワークを構成するスイッチの数は、本実施の形態において例示した数に限られない。また、プロセス間ネットワークの構成は、本実施の形態において例示した構成に限られない。つまり、本発明は、本実施の形態において例示したように、スイッチが多段に接続されていないプロセス間ネットワークにも適用することができる。
【００８８】
本発明の第１及び第２の実施の形態では、調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する数を、各入力ポートから受信した強度が示す値として決定しているが、これに限られない。調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度の多さに関する入力ポート間の割合に応じて決定するようにしてもよい。このようにしても、より多くのパケットを出力するスイッチからパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができるため、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。
【００８９】
本発明の第１及び第２の実施の形態では、スイッチは、調停での強度をパケットに含めて出力するようにしているが、これに限られない。例えば、スイッチは、パケットとは、別にそのパケットと対応付けて調停での強度を示す強度情報を出力するようにしてもよい。
【００９０】
本発明の第３の実施の形態では、調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する数を、各入力ポートについての転送経路数情報が示す転送経路数として決定しているが、これに限られない。調停回路は、調停を実行する場合に、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定するようにしてもよい。このようにしても、より多くのパケットが入力される入力ポートから、より多くのパケットを次段に出力するようにすることができるため、プロセッサ間で転送するパケットの転送時間の偏りを低減することができる。
【００９１】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００９２】
（付記１）複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、前記データ転送部は、次の転送先が同じ競合データについて調停を実行する調停手段と、調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定するデータ転送システム。
【００９３】
（付記２）前記強度情報通知手段は、前記調停を行った競合データのそれぞれに対応付けて、当該調停を行った競合データの競合数を示す強度情報を次の転送先に送信し、前記調停手段は、それぞれが複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して次の転送先に送信される競合データについて、前記調停を実行する複数の調停回路を含み、前記調停回路は、前記各入力ポートから受信した強度情報のうち、当該調停回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記選択割合を決定する付記１に記載のデータ転送システム。
【００９４】
（付記３）前記強度情報通知手段は、それぞれが前記複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して送信される競合データのそれぞれに前記強度情報を対応付けて、当該出力ポートを介して次の転送先に送信する複数の強度情報通知回路を含み、前記強度情報通知回路は、当該強度情報通知回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記競合データの競合数を算出する付記２に記載のデータ転送システム。
【００９５】
（付記４）前記調整回路は、前記調停を実行する場合には、それぞれが前記複数の入力ポートのそれぞれに対応し、対応する入力ポートを選択し、その入力ポートから競合データを入力した数をカウントする複数のカウンタを含み、当該複数のカウンタのカウント数のそれぞれが、当該複数のカウンタに対応する入力ポートから受信した強度情報が示す競合数のそれぞれと一致まで、前記複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する付記２又は３に記載のデータ転送システム。
【００９６】
（付記５）前記調停手段は、より多い競合数を示す強度情報を受信した入力ポートからの競合データを優先して、次の転送先に送信する付記１乃至４に記載のデータ転送システム。
【００９７】
（付記６）前記競合データは、データ転送先のプロセッサを示す転送先プロセッサ情報を含むパケットであり、前記データ転送部は、前記パケットに含まれる出力先プロセッサ情報に基づいて、前記パケットをルーティングするスイッチである付記１乃至５のいずれか１項に記載のデータ転送システム。
【００９８】
（付記７）前記強度情報通知手段は、前記調停を行った競合データのそれぞれに、当該調停を行った競合データの競合数を示す強度情報を含めて送信する付記２乃至４のいずれか１項に記載のデータ転送システム。
【００９９】
（付記８）前記データ転送システムは、前記複数のデータ転送部が多段に接続されたプロセス間ネットワークをさらに備えた付記１乃至７のいずれか１項に記載のデータ転送システム。
【符号の説明】
【０１００】
１ 並列コンピュータ
５ データ転送システム
１０ プロセッサ間ネットワーク
２０、６０、７０ データ転送部
１０１、１０２、１０３、１０４、１０５、１０６、１０７、１０８、１０９、１１０、１１１、１１２、１１３、１１４、１１５、１１６、５０１、５０２、５０３、５０４、５０５、５０６、５０７、５０８、５０９、５１０、５１１、５１２、５１３、５１４、５１５、５１６、８０１、８０２，８０３、８０５、９０１、９０２、９０３、９０５、１００１、１００２、１００３、１００５、１１０１、１１０２、１１０３、１１０５、１２０３、１３０３、１４０３、１５０３、１６０１、１６０２、１６０４、１６０５、１６０７、１６０９、１６１０、１８０１、１８０２、１９０１、１９０２、２００１、２００２ プロセッサ
１１７、１１８、１１９、１２０、１２１、１２２、１２３、１２４、１２５、１２６、１２７、１２８、１２９、１３０、１３１、１３２、１３２、１３３、１３４、１３５、１３６、２０１、５１７、５１８、５１９、５２０、５２１、５２２、５２３、５２４、５２５、５２６、５２７、５２８、５２９、５３０、５３１、５３２、５３３、５３４、５３５、５３６、７０１、８０４、９０４、１００４、１１０４、１２０１、１２０２、１２０４、１３０１、１３０２、１３０４、１４０１、１４０２、１４０４、１５０１、１６０４、１６０３、１６０６、１６０８、１７０１、１８０３、１８０４、１８０５、１９０３、１９０４、２００３ スイッチ
２０２、２０３、２０４、２０５、２５１、２５２、２５３、２５４、６５１、６５２、６５３、６５４、７０２、７０３、７０４、７０５、７５１、７５２、７５３、７５４、１７０２、１７０３、１７０４、１７０５ 入力ポート
２０６、２０７、２０８、２０９、２５５、２５６、２５７、２５８、６５５、６５６、６５７、６５８、７０６、７０７、７０８、７０９、７５５、７５６、７５７、７５８、１７０６、１７０７、１７０８、１７０９ 出力ポート
２１０、２１１、２１２、２１３、７１０、７１１、７１２、７１３ 入力ＦＩＦＯメモリ
２１４、７１４、１７１８ クロスバスイッチ
２１５、２１６、２１７、２１８、７１５、７１６、７１７、７１８ 出力ＦＩＦＯメモリ
２１９、２２０、２２１、２２２、３０１、６０１、７１９、７２０、７２１、７２２、１７１９ 調停回路
２２３、２２４、２２５、２２６、７２３、７２４、７２５、７２６ 強度レジスタ
２２７、２２８、２２９、２３０、３１１、３１２、３１３、３１４、６１１、６１２、６１３、６１４、７２７、７２８、７２９、７３０ マルチプレクサ(ＭＵＸ)
２５９、６５９、７５９ 調停手段
２６０、６６０、７６０ 強度情報通知手段
３０２、３０３、３０４、３０５、６０２、６０３、６０４、６０５ 強度カウンタ
３０６、６０６ 選択回路
３０７、３０８、３０９、３１０、６０７、６０８、６０９、６１０ １減算器
３１５、６１５ 強度計算回路
３１６、６１６ 強度合計レジスタ
３１７、３１８、３１９、３２０、６１７、６１８、６１９、６２０ 強度
３２１、３２２、３２３、３２４、６２１、６２２、６２３、６２４ 調停参加信号
４０１ 送り先プロセッサ番号
４０２ 送り元プロセッサ番号
４０３ 調停での強度
４０４ 書き込みアドレス
４０５ データ長
８０６、８０７、８０８、８０９、９０６、９０７、９０８、９０９、１００６、１００７、１００８、１００９、１１０６、１１０７、１１０８、１１０９、１２０６、１２０７、１２０８、１２０９、１３０６、１３０７、１３０８、１３０９、１４０６、１４０７、１４０８、１４０９ 強度カウンタ値
８１０、８１１、８１２、８１３、９１０、９１１、９１２、９１３、１０１０、１０１１、１０１２、１０１３、１１１０、１１１１、１１１２、１１１３、１２１０、１２１１、１２１２、１２１３、１３１０、１３１１、１３１２、１３１３、１４１０、１４１１、１４１２、１４１３ 調停参加信号値
８１４、９１４、１０１４、１１１４、１２１４、１３１４、１４１４ 強度合計レジスタ値
１５０２ 信号線
１７１０、１７１１、１７１２、１７１３、１７１４、１７１５、１７１６、１７１７ ＦＩＦＯメモリ
【特許請求の範囲】
【請求項１】
複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、
前記データ転送部は、
次の転送先が同じ競合データについて調停を実行する調停手段と、
調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する
データ転送システム。
【請求項２】
前記強度情報通知手段は、前記調停を行った競合データのそれぞれに対応付けて、当該調停を行った競合データの競合数を示す強度情報を次の転送先に送信し、
前記調停手段は、それぞれが複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して次の転送先に送信される競合データについて、前記調停を実行する複数の調停回路を含み、
前記調停回路は、前記各入力ポートから受信した強度情報のうち、当該調停回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記選択割合を決定する請求項１に記載のデータ転送システム。
【請求項３】
前記強度情報通知手段は、それぞれが前記複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して送信される競合データのそれぞれに前記強度情報を対応付けて、当該出力ポートを介して次の転送先に送信する複数の強度情報通知回路を含み、
前記強度情報通知回路は、当該強度情報通知回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記競合データの競合数を算出する請求項２に記載のデータ転送システム。
【請求項４】
前記調整回路は、前記調停を実行する場合には、それぞれが前記複数の入力ポートのそれぞれに対応し、対応する入力ポートを選択し、その入力ポートから競合データを入力した数をカウントする複数のカウンタを含み、当該複数のカウンタのカウント数のそれぞれが、当該複数のカウンタに対応する入力ポートから受信した強度情報が示す競合数のそれぞれと一致まで、前記複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する請求項２又は３に記載のデータ転送システム。
【請求項５】
前記調停手段は、より多い競合数を示す強度情報を受信した入力ポートからの競合データを優先して、次の転送先に送信する請求項１乃至４に記載のデータ転送システム。
【請求項６】
前記競合データは、データ転送先のプロセッサを示す転送先プロセッサ情報を含むパケットであり、
前記データ転送部は、前記パケットに含まれる出力先プロセッサ情報に基づいて、前記パケットをルーティングするスイッチである請求項１乃至５のいずれか１項に記載のデータ転送システム。
【請求項７】
複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、
前記プロセッサは、
初期値を示す強度情報を次の転送先に送信し、
前記データ転送部は、
次の転送先が同じ競合データについて調停を実行する調停手段と、
複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成して、複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する強度情報通知手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定する
データ転送システム。
【請求項８】
複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、
前記データ転送部は、
複数のデータ転送部からデータが入力される複数の入力ポートのそれぞれについて、入力ポートに対して前記複数のプロセッサからデータが転送される転送経路数を示す転送経路数情報を格納する記憶手段と、
次に転送する先が同じ競合データについて調停を実行する調停手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定する
データ転送システム。
【請求項９】
それぞれが複数接続され、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行するスイッチであって、
次の転送先が同じ競合データについて調停を実行する調停手段と、
調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する
スイッチ。
【請求項１０】
複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部のそれぞれにおけるデータ転送方法であって、
次の転送先が同じ競合データについて調停を実行する調停ステップと、
調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知ステップと、を備え、
前記調停ステップでは、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する
データ転送方法。
【請求項１】
複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、
前記データ転送部は、
次の転送先が同じ競合データについて調停を実行する調停手段と、
調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する
データ転送システム。
【請求項２】
前記強度情報通知手段は、前記調停を行った競合データのそれぞれに対応付けて、当該調停を行った競合データの競合数を示す強度情報を次の転送先に送信し、
前記調停手段は、それぞれが複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して次の転送先に送信される競合データについて、前記調停を実行する複数の調停回路を含み、
前記調停回路は、前記各入力ポートから受信した強度情報のうち、当該調停回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記選択割合を決定する請求項１に記載のデータ転送システム。
【請求項３】
前記強度情報通知手段は、それぞれが前記複数の出力ポートのそれぞれに対応し、対応する出力ポートを介して送信される競合データのそれぞれに前記強度情報を対応付けて、当該出力ポートを介して次の転送先に送信する複数の強度情報通知回路を含み、
前記強度情報通知回路は、当該強度情報通知回路に対応する出力ポートを介して送信される競合データに対応付けられた強度情報に基づいて、前記競合データの競合数を算出する請求項２に記載のデータ転送システム。
【請求項４】
前記調整回路は、前記調停を実行する場合には、それぞれが前記複数の入力ポートのそれぞれに対応し、対応する入力ポートを選択し、その入力ポートから競合データを入力した数をカウントする複数のカウンタを含み、当該複数のカウンタのカウント数のそれぞれが、当該複数のカウンタに対応する入力ポートから受信した強度情報が示す競合数のそれぞれと一致まで、前記複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する請求項２又は３に記載のデータ転送システム。
【請求項５】
前記調停手段は、より多い競合数を示す強度情報を受信した入力ポートからの競合データを優先して、次の転送先に送信する請求項１乃至４に記載のデータ転送システム。
【請求項６】
前記競合データは、データ転送先のプロセッサを示す転送先プロセッサ情報を含むパケットであり、
前記データ転送部は、前記パケットに含まれる出力先プロセッサ情報に基づいて、前記パケットをルーティングするスイッチである請求項１乃至５のいずれか１項に記載のデータ転送システム。
【請求項７】
複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、
前記プロセッサは、
初期値を示す強度情報を次の転送先に送信し、
前記データ転送部は、
次の転送先が同じ競合データについて調停を実行する調停手段と、
複数のデータ転送部から複数の入力ポートを介して強度情報を受信した場合に、受信した強度情報のそれぞれが示す値の合計値を示す強度情報を生成して、複数の次の転送先のそれぞれに対して複数の出力ポートを介して同じ強度情報を送信する強度情報通知手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す値の多さに関する入力ポート間の割合に応じて決定する
データ転送システム。
【請求項８】
複数のプロセッサと、当該複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部とを備えたデータ転送システムであって、
前記データ転送部は、
複数のデータ転送部からデータが入力される複数の入力ポートのそれぞれについて、入力ポートに対して前記複数のプロセッサからデータが転送される転送経路数を示す転送経路数情報を格納する記憶手段と、
次に転送する先が同じ競合データについて調停を実行する調停手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して複数のデータを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートについての転送経路数情報が示す転送経路数の多さに関する入力ポート間の割合に応じて決定する
データ転送システム。
【請求項９】
それぞれが複数接続され、複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行するスイッチであって、
次の転送先が同じ競合データについて調停を実行する調停手段と、
調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知手段と、を有し、
前記調停手段は、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する
スイッチ。
【請求項１０】
複数のプロセッサに含まれる一のプロセッサから他のプロセッサに対するデータ転送を複数の入力及び出力ポートを介して実行する複数のデータ転送部のそれぞれにおけるデータ転送方法であって、
次の転送先が同じ競合データについて調停を実行する調停ステップと、
調停を行った競合データの競合数を示す強度情報を次の転送先に送信する強度情報通知ステップと、を備え、
前記調停ステップでは、複数のデータ転送部から複数の入力ポートを介して競合データを受信して前記調停を実行する場合には、複数の入力ポートの中でそれぞれの入力ポートを選択し、その入力ポートから競合データを入力する割合を示す選択割合を、各入力ポートから受信した強度情報が示す競合数の多さに関する入力ポート間の割合に応じて決定する
データ転送方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９Ａ】
【図９Ｂ】
【図１０Ａ】
【図１０Ｂ】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８Ａ】
【図８Ｂ】
【図９Ａ】
【図９Ｂ】
【図１０Ａ】
【図１０Ｂ】
【図１１Ａ】
【図１１Ｂ】
【図１２Ａ】
【図１２Ｂ】
【図１３Ａ】
【図１３Ｂ】
【図１４Ａ】
【図１４Ｂ】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【公開番号】特開２０１２−４３３６３（Ｐ２０１２−４３３６３Ａ）
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願番号】特願２０１０−１８６３２７（Ｐ２０１０−１８６３２７）
【出願日】平成２２年８月２３日（２０１０．８．２３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願日】平成２２年８月２３日（２０１０．８．２３）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]