接続情報生成装置、制御方法および制御プログラム
【課題】オーバーヘッドの発生を低減する。
【解決手段】1つの側面では、それぞれ1つのノードが接続された複数の第1転送装置と、各第1転送装置間の通信を中継する複数の第2転送装置との接続に関する情報を生成する接続情報生成装置1である。この接続情報生成装置1は、1つの第1転送装置に接続する第2転送装置の数から1を減算した値を標数とするガロア体の加法表と乗法表とを作成する。そして、接続情報生成装置は、作成した乗法表と加法表とに基づいて、第2転送装置を第1転送装置の組ごとに定めた接続に関する情報を生成する。
【解決手段】1つの側面では、それぞれ1つのノードが接続された複数の第1転送装置と、各第1転送装置間の通信を中継する複数の第2転送装置との接続に関する情報を生成する接続情報生成装置1である。この接続情報生成装置1は、1つの第1転送装置に接続する第2転送装置の数から1を減算した値を標数とするガロア体の加法表と乗法表とを作成する。そして、接続情報生成装置は、作成した乗法表と加法表とに基づいて、第2転送装置を第1転送装置の組ごとに定めた接続に関する情報を生成する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、接続情報生成装置、制御方法および制御プログラムに関する。
【背景技術】
【0002】
従来、複数のノード間で同時に通信を行う際に互いに競合しない通信経路が確保される非閉塞なネットワークの技術が知られている。このような技術の一例として、各ノード間の通信が3つの転送装置を介して行われる非閉塞な3ステージクロス(3 stage Clos)網のネットワークが知られている。
【0003】
図18は、非閉塞な3ステージクロス網のネットワークの一例を説明するための図である。図18に示すネットワーク80は、6つのノード81〜86、第1の転送装置または第3の転送装置として動作するスイッチ87〜89、第2の転送装置として動作するクロスバスイッチ(Crossbar Switch)(以下、「XB」とする)90〜92を有する。
【0004】
またネットワーク80において、各スイッチ87〜89と各XB90〜92とが相互に接続され、各スイッチ87〜89には、それぞれ2つのノードが接続される。ここで、ノードとしては、クラスタを構成するコンピュータ、外部のネットワークと接続されたネットワーク装置等が適用される。
【0005】
このようなネットワーク80のスイッチ87〜89は、ノード間において新たな通信が行われる場合には、他の通信と競合しない通信経路を確保するため、他の通信を中継していないXBを選択する、調停を伴う動的なルーティング処理を実行する。具体的には、スイッチ87〜89は、送信側のノードが接続されたスイッチと受信側のノードが接続されたスイッチとが他の通信に使用していないXBを選択する。そして、スイッチ87〜89は、選択したXBにノード間の新たな通信を中継させる。
【0006】
例えば、スイッチ87は、ノード81とノード86とが新たに通信を行う場合には、自装置とノード86に接続されたスイッチ89とが共に通信に使用していないXBを検索する。この際、スイッチ87は、自装置とスイッチ89がXB91を通信に使用していない場合には、XB91を選択する。その後、スイッチ87は、XB91にノード81とノード86との通信を中継させる。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】特開2007−220100号公報
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかし、上述したスイッチとXBとを相互に接続する技術では、いずれかのノード間において新たな通信が行われる場合には、通信経路の競合を避けるため、調停を伴う動的なルーティング処理を実行する。この結果、ノードが他のノードと通信する際に許容される遅延が短い場合には、調停によって発生するオーバーヘッドが無視できないという問題があった。
【0009】
なお、各スイッチに接続されたノードの数を減らすことで、調停に係るオーバーヘッドを削減する手法が考えられる。しかし、各スイッチに接続されたノードの数を減らして総ノード数の等しい非閉塞なネットワークを構成するには、多くのスイッチを接続することができる大規模なXBが求められる。通常、XBはLSI(Large Scale Integrated Circuit)により実現されるため、多くのスイッチを接続するためには多数のピンが必要となる。
【0010】
従って、このような大規模なXBを入手できない場合に、非閉塞の3ステージクロス網をXBの代替としてネットワークに適用する手法が考えられる。しかし、このようなネットワークにおいても、XBの代替として設置した非閉塞の3ステージクロス網において調停を伴う動的なルーティング処理が行われるため、調停によって発生するオーバーヘッドを削減できない。
【0011】
本願に開示の技術は、調停を伴う動的なルーティング処理を解消し、調停に係るオーバーヘッドの削減を実現する。
【課題を解決するための手段】
【0012】
それぞれ1つのノードが接続された複数の第1転送装置と、各第1転送装置間の通信を中継する複数の第2転送装置との接続に関する情報を生成する接続情報生成装置である。この接続情報生成装置は、1つの第1転送装置に接続する第2転送装置の数に基づく値を標数とするガロア体の加法表と乗法表とを作成する。そして、接続情報生成装置は、作成した乗法表と加法表とに基づいて、第2転送装置を第1転送装置の組ごとに定めた接続に関する情報を生成する。
【発明の効果】
【0013】
調停を伴う動的なルーティング処理を解消し、調停に係るオーバーヘッドの削減を実現する。
【図面の簡単な説明】
【0014】
【図1】図1は、接続表生成装置を説明するための図である。
【図2】図2は、GF(5)の乗法表を説明するための図である。
【図3】図3は、GF(5)の加法表を説明するための図である。
【図4】図4は、GF(8)の乗法表を説明するための図である。
【図5】図5は、GF(8)の加法表を説明するためのである。
【図6】図6は、「p=q=6」の接続表を説明するための図である。
【図7】図7は、実施例1に関わる接続表生成部が生成する「p=6、q=5」の接続表を説明するための図である。
【図8】図8は、「p=4、q=6」の接続表を説明するための図である。
【図9】図9は、GF(2)の乗法表を説明するための図である。
【図10】図10は、GF(2)の加法表を説明するための図である。
【図11】図11は、「p=q=3」の接続表を説明するための図である。
【図12】図12は、接続表に従って作成したネットワークを説明するための図である。
【図13】図13は、実施例1に係る接続表生成装置が実行する処理の流れを説明するためのフローチャートである。
【図14】図14は、ファンアウトスイッチを用いずに、クロスバスイッチのみを用いたクロスバネットワーク構成例を説明するための図である。
【図15】図15は、クロスバスイッチ同士を接続したネットワークを説明するための図である。
【図16】図16は、クロスバスイッチ同士の接続例を説明するための図である。
【図17】図17は、制御プログラムを実行するコンピュータの一例を説明するための図である。
【図18】図18は、非閉塞な3ステージクロス網のネットワークの一例を説明するための図である。
【発明を実施するための形態】
【0015】
以下に添付図面を参照して本願に係る接続情報生成装置、制御方法および制御プログラムについて説明する。
【実施例1】
【0016】
以下の実施例1では、接続情報生成装置の一例を説明する。例えば、接続情報生成装置は、それぞれ1つのノードが接続された複数のファンアウトスイッチ(Fan−out Switch:以下FOと記載する。)と、FO間の通信を中継するクロスバスイッチ(以下XBと記載する。)との接続を示す接続表を作成する。
【0017】
図1は、接続表生成装置の一例を説明するための図である。図1に示すように、接続表生成装置1は、受付部2、N次既約多項式生成部3、乗法表・加法表生成部4、接続表生成部5、出力部6を有する。また、接続表生成装置1の受付部2は、キーボード7と接続されており、後述するように、利用者が指定した数値の入力を受け付ける。また、接続表生成装置1の出力部6は、モニタ8と接続されており、利用者が指定した数値に基づいて生成した接続表をモニタ8に表示する。
【0018】
このような接続表生成装置1は、キーボード7等の入力装置を介して、利用者が入力した各FOに接続することができるXBの数「p」、および、各XBに接続することができるFOの数「q」を取得する。そして、接続表生成装置1は、入力された「p」と「q」に基づいて、複数のFOと複数のXBとの接続表を作成し、作成した接続表をモニタ8に表示させる。
【0019】
以下、接続表生成装置1が各部2〜6を用いて、接続表を作成する処理について詳しく説明する。まず、受付部2は、利用者がキーボード7を用いて入力した各FOに接続することができるXBの数「p」、および、各XBに接続することができるFOの数「q」を取得する。ここで、各FOには1つのノードが接続されるため、「p」は各FOのポート数からノードが接続するポート分である1を減算したものであり、「q」は各XBが有するポートの数となる。換言すると、受付部2は、ネットワークを構築するために利用者が準備することができるXBのポート数「q」とFOのポート数から1を減算した値「p」とを取得する。
【0020】
そして、受付部2は、取得した「p」と「q」とに基づいて、「p=PN+1」、「q=cp」もしくは「q=c(p−1)」を満たす素数「P」、自然数「N」、自然数「c」を算出する。そして、受付部2は、「P」と「N」をN次既約多項式生成部3に通知し、「p」、「q」、「P」、「N」、「c」を接続表生成部5に通知する。
【0021】
また、受付部2は、「p=PN+1」、「q=cp」もしくは「q=c(p−1)」を満たす素数「P」、自然数「N」、整数「c」が存在しない場合には、以下の処理を実行する。すなわち、受付部2は、「p´≦p」、「q´≦q」を満たす適切な「p´」、「q´」について、「p´=PN+1」、「q´=cp´」もしくは「q´=c(p´−1)」を満たす素数「P」、自然数「N」、整数「c」を算出する。その後、受付部2は、「P」と「N」をN次既約多項式生成部3に通知し、「p´」を「p」とし、「q´」を「q」として「p」、「q」、「P」、「N」、「c」を接続表生成部5に通知する。
【0022】
N次既約多項式生成部3は、利用者が入力した「p」および「q」から算出された素数「P」と自然数「N」に基づいて、素数「P」を標数とするガロア体GF(P)上のN次多項式f(X)をGF(P)上既約となるように生成する。そして、N次既約多項式生成部3は、生成したf(X)を乗法表・加法表生成部4に通知する。
【0023】
具体的には、N次既約多項式生成部3は、素数「P」および自然数「N」から以下の式(1)を作成する。ここで、式(1)中のAi(i=0〜N−1)は、0≦Ai<Pを満たす係数である。
【0024】
【数1】
【0025】
ここで、f(X)がGF(P)上既約であるとは、f(X)が以下の式(2)を満たす1次以上の多項式a(X)およびb(X)が存在しないことを言う。
【0026】
【数2】
【0027】
N次既約多項式生成部3は、まずGF(P)上のN次多項式のリストを作成する。次に次数が1〜N−1までのGF(P)上の多項式を全て生成し、生成した多項式の積で表されるN次多項式を先に作成したリストから全て削除する。その後、N次既約多項式生成部3は、リストに残ったN次多項式の1つをN次既約多項式f(X)として乗法表・加法表生成部4に通知する。なお、任意の素数「P」および自然数「N」に対して、既約ではないf(X)が少なくとも1つは存在する。
【0028】
乗法表・加法表生成部4は、N次既約多項式生成部3から通知されたN次既約多項式f(X)を法とし、GF(P)上のN−1次以下の多項式の集合からガロア体GF(PN)の加法表と乗法表とを生成する。つまり、乗法表・加法表生成部4は、利用者が入力した「p」に基づく値「PN」を標数とするガロア体の加法表と乗法表とを生成する。
【0029】
以下、Q=PNとし、乗法表・加法表生成部4が加法表と乗法表とを生成する処理について具体的に説明する。まず、0≦j<Qを満たす任意の整数jは、以下の式(3)によって表現することができる。ここで、式(3)中のBi(i=0〜N−1)は、0≦Bi<Pを満たす係数で、jをP進数で表した場合の各桁の数値である。
【0030】
【数3】
【0031】
式(3)の場合と同様に、GF(P)上のN−1次以下の全ての多項式は、以下の式(4)によって、g(0,X)〜g(Q−1,X)で与えられる。ただし、g(j,P)=jである。
【0032】
【数4】
【0033】
乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して、以下の式(5)に定義する加法を適用することでGF(Q)の加法表を生成する。なお、式(5)中の|+|は、g(i,X)とg(j,X)の和をPで除算した場合の剰余であるGF(P)上の多項式を与える加法を示す記号である。
【0034】
【数5】
【0035】
つまり、乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して式(5)に定義する加法を適用し、式(5)を適用した結果得られる多項式にX=Pを代入した整数値をまとめた加法表を生成する。
【0036】
また、乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して、以下の式(6)に定義する乗法を適用することでGF(Q)の乗法表を生成する。なお、式(6)中の|×|は、g(i,X)とg(j,X)の積をf(X)で除算した場合の剰余を、さらにPで除算した場合の剰余であるGF(P)の多項式を与える乗法を示す記号である。
【0037】
【数6】
【0038】
つまり、乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して式(6)に定義する乗法を適用し、式(6)を適用した結果得られる多項式にX=Pを代入した整数値をまとめた乗法表を作成する。その後、乗法表・加法表生成部4は、生成した加法表と乗法表とを接続表生成部5に送信する。
【0039】
図2は、GF(5)の乗法表を説明するための図である。また、図3は、GF(5)の加法表を説明するための図である。なお、図2および図3に示す表のうち、点線で囲まれた範囲は、実線で囲まれた各セルの行番号および列番号を示す。
【0040】
例えば、乗法表・加法表生成部4は、利用者が「p=q=6」を入力した場合には、図2に示すGF(5)の乗法表を生成し、生成した乗法表を接続表生成部5に送信する。また、乗法表・加法表生成部4は、利用者が「p=q=6」を入力した場合には、図3に示すGF(5)の加法表を生成し、生成した加法表を接続表生成部5に送信する。
【0041】
図2に示すGF(5)の乗法表が有する各セルには、セルの行番号「0〜4」とセルの列番号「0〜4」との積をGF(5)の標数「5」で除算した剰余が格納されている。また、図2に示すように、乗法表の「0」行および「0」列を除く各行および各列には、整数をGF(5)の標数「5」で除算した剰余「0,1,2,3,4」の要素が全て1つずつ含まれる。
【0042】
また、図3に示すGF(5)の加法表が有する各セルには、セルの行番号「0〜4」とセルの列番号「0〜4」との和をGF(5)の標数「5」で除算した剰余が格納されている。また、図3に示すように、加法表の各行および各列には、整数をGF(5)の標数「5」で除算した剰余「0,1,2,3,4」の要素が全て1つずつ含まれる。
【0043】
図4は、GF(8)の乗法表を説明するための図である。また、図5は、GF(8)の加法表を説明するための図である。なお、図4および図5に示す表のうち、点線で囲まれた範囲は、実線で囲まれた各セルの行番号および列番号を示す。
【0044】
例えば、乗法表・加法表生成部4は、利用者が「p=q=9」を入力した場合には、図4に示す標数が「8」のGF(8)の乗法表を生成し、生成した乗法表を接続表生成部5に送信する。また、乗法表・加法表生成部4は、利用者が「p=q=9」を入力した場合には、図5に示す標数が「8」のGF(8)の加法表を生成し、生成した加法表を接続表生成部5に送信する。なお、図4に示す乗法表および図5に示す加法表は、既約多項式f(X)=x3+x+1を法としたGF(8)=GF(23)の乗法表と加法表とに相当する。
【0045】
図4に示すGF(8)の乗法表が有する各セルには、X=2を代入するとセルの行番号iと等しくなるGF(2)上の2次以下の多項式g(i,X)と、同様にセルの列番号jと等しくなる多項式g(j,X)に対し、f(X)=x3+x+1かつP=2として、式(6)の乗法を適用した結果得られる多項式にX=2を代入した整数値が格納されている。この結果、図4に示すように、標数「8」のガロア体GF(8)における乗法表の「0」行および「0」列を除く各行および各列には、「0,1,2,3,4,5,6,7」の要素が全て1つずつ含まれる。
【0046】
また、図5に示すGF(8)の加法表が有する各セルには、X=2を代入するとセルの行番号iと等しくなるGF(2)上の2次以下の多項式g(i,X)と、同様にセルの列番号jと等しくなる多項式g(j,X)に対し、P=2として、式(5)の加法を適用した結果得られる多項式にX=2を代入した整数値が格納されている。この結果、図5に示すように、標数「8」のガロア体GF(8)における加法表の各行および各列には、「0,1,2,3,4,5,6,7」の要素が全て1つずつ含まれる。
【0047】
接続表生成部5は、乗法表・加法表生成部4が生成した加法表と乗法表とに基づいて、複数のFOと複数のXBとの接続表であって、XBに転送されるFOの組を定めた接続表を生成する。
【0048】
具体的には、接続表生成部5は、乗法表・加法表生成部4から乗法表と加法表とを受信する。また、接続表生成部5は、受信した乗法表の任意の一つのセルを選択し、受信した加法表において、乗法表で選択したセルと同じ値が格納された全てのセルに同じ値が格納された旨を表す「○」を格納し、他の全てのセルを空欄とした表を作成する。その後、接続表生成部5は、作成した表を乗法表の選択したセルにマッピングする。続けて、接続表生成装置5は、同様の処理を乗法表の他の全てのセルについて実行し、受信したガロア体の標数Qを2乗した数の行および列を有する、Q2行×Q2列の表を作成する。
【0049】
続けて、接続表生成部5は、先に作成したQ2行×Q2列の表に対し、図2に示す元の乗法表、つまり乗法表・加法表生成部4が生成した乗法表のQ個の列と対応付けたQ個の行を追加し、追加した各行において、図2の乗法表の対応する列に含まれるそれぞれQ個の列に「○」を格納し、他のセルを空欄とした「p=PN+1」かつ「q=PN」である場合の接続表を生成する。この接続表は(Q2+Q)個の行とQ2個の列を有し、各列は(PN+1)個の、各行はPN個の「○」を含む。「p=PN+1」かつ「q=PN」である場合には、接続表生成部5は、生成した接続表を出力部6へ送信する。
【0050】
また、接続表生成部5は、「p=PN+1」かつ「q=c(p−1)」である場合には、先に作成した「p=PN+1」かつ「q=PN」である場合の(Q2+Q)個の行とQ2個の列を有する接続表を行方向に「c−1」回複製することで生成した(Q2+Q)行×cQ2列のセルを有する接続表を出力部6へ送信する。
【0051】
また、接続表生成部5は、「p=q=PN+1」である場合、もしくは「p=PN+1」かつ「q=cp」である場合には、先に作成した「p=PN+1」かつ「q=PN」である場合の接続表に対し、図2に示す元の乗法表、つまり乗法表・加法表生成部4が生成した乗法表のQ個の行と対応付けたQ個の列を追加し、追加した各列において、図2の対応する行に含まれるそれぞれQ個の行に「○」を格納し、他のセルを空欄とした表を作成する。
【0052】
この表は(Q2+Q)個の行と(Q2+Q)個の列を有する。さらに、接続表生成部5は、この(Q2+Q)行×(Q2+Q)列の表に1個の行と1個の列を追加し、各行、各列の「○」の数が(PN+1)個となるよう、追加した1行と1列に「○」を追加して、「p=q=PN+1」である場合の接続表を生成する。この表は、(Q2+Q+1)行×(Q2+Q+1)列の表である。「p=q=PN+1」である場合には、接続表生成部5は、生成した(Q2+Q+1)行×(Q2+Q+1)列の接続表を出力部6へ送信する。
【0053】
また、接続表生成部5は、「p=PN+1」かつ「q=cp」である場合には、先に作成した「p=q=PN+1」である場合の(Q2+Q+1)行×(Q2+Q+1)列の接続表を行方向に「c−1」回複製することで生成した(Q2+Q+1)行×c(Q2+Q+1)列の接続表を出力部6へ送信する。
【0054】
以下、接続表生成部5が実行する処理の例について説明する。まず、「p=PN+1」かつ「q=PN」、もしくは「p=q=PN+1」の場合に接続表を生成する処理の例を説明する。例えば、接続表生成部5は、利用者が「p=6、q=5」、もしくは「p=q=6」を入力した場合には、図2と図3とに示す標数が5のGF(5)の乗法表と加法表とを受信する。このような場合には、接続表生成部5は、図3に示す加法表のうち「0」が格納された全てのセルに「○」を格納するとともに他のセルを空欄とした表を作成し、作成した表を図2に示す乗法表のうち「0」が格納された全てのセルの位置に配置する。
【0055】
また接続表生成部5は、図3に示す加法表のうち「1」が格納された全てのセルに「○」を格納するとともに他のセルを空欄とした表を作成し、作成した表を図2に示す乗法表のうち「1」が格納された全てのセルの位置に配置する。また、接続表生成部5は、他の値「2」、「3」、「4」が格納されたセルについても同様の処理を実行する。この結果、接続表生成部5は、25行×25列の表を作成する。
【0056】
図7は、実施例1に関わる接続表生成部が生成する「p=6、q=5」の場合の接続表を説明するための図である。図7に示す30行×25列の表のうち、太線で囲んだ25行×25列の範囲が図2に示す乗法表と図3に示す加法表とから作成した表である。すなわち、太線は図2に示す元の乗法表の各セルに対応する。接続表生成部5は、この25行×25列の表に対し、当該図2の5個の列と対応付けた5個の行を追加する。そして、接続表生成部5は、追加した各行において、図2の対応する列に含まれるそれぞれ5個の列に「○」を格納して他のセルを空欄とし、図7に示す30行×25列の接続表を生成する。
【0057】
つまり、接続表生成部5は、まず、図7中行番号「25」〜「29」の行を追加する。ここで、図7中行番号「25」の行は、図2に示す元の乗法表の列番号「0」と対応し、図7中行番号「26」の行は、図2の列番号「1」と対応する。また、図7中行番号「27」の行は、図2の列番号「2」と対応し、図7中行番号「28」の行は、図2の列番号「3」と対応する。また、図7中行番号「29」の行は、図2の列番号「4」と対応する。
【0058】
次に、接続表生成部5は、行番号「25」の行については列番号「0」〜「4」のセルに「○」を格納するとともに、行番号「26」の行については列番号「5」〜「9」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成部5は、行番号「27」の行については列番号「10」〜「14」のセルに「○」を格納し、行番号「28」の行については列番号「15」〜「19」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成部5は、行番号「29」の行については列番号「20」〜「24」のセルに「○」を格納し、他のセルを空欄として、30行×25列の接続表を生成する。「p=6、q=5」の場合には、接続表生成部5は、生成した30行×25列の接続表を出力部6へ送信する。これは「p=PN+1」かつ「q=PN」である場合の処理のP=5、N=1の例である。
【0059】
図6は、接続表生成部5が次に生成する「p=q=6」の場合の接続表を説明するための図である。図6に示す31行×31列の表のうち、列番号「0」〜「24」の30行×25列の範囲が図7に示す「p=6、q=5」の場合の接続表である。図7と同様に、太線は図2に示す元の乗法表の各セルに対応する。接続表生成部5は、この30行×25列の表に対し、図2に示す元の乗法表の5個の行と対応付けた行番号「25」〜「29」の5個の列を追加する。そして、接続表生成部5は、追加した各列において、図2の対応する行に含まれるそれぞれ5個の行に「○」を格納して他のセルを空欄とし、30行×30列の表を生成する。
【0060】
つまり、接続表生成部5は、図6に示す例では、列番号「25」については行番号「0」〜「4」、列番号「26」については行番号「5」〜「9」、列番号「27」については行番号「10」〜「14」のセルに○を格納し、他のセルを空欄とする。また、接続表生成部5は、列番号「28」については行番号「15」〜「19」、列番号「29」については行番号「20」〜「24」のセルに○を格納し、他のセルを空欄とした、30行×30列の表を生成する。
【0061】
さらに、接続表生成部5は、この30行×30列の表に行番号「30」の行と列番号「30」の列とを追加する。そして、接続表生成部5は、各行、各列の「○」の数が6個となるよう、追加した行番号「30」の行と列番号「30」の列とが有する各セルに「○」を追加した31行×31列の接続表を生成する。つまり、接続表生成部5は、行番号「30」の行については、列番号「25」〜「30」のセルに「○」を格納し、列番号「30」の列については、行番号「25」〜「29」のセルに「○」を格納する。「p=q=6」である場合には、接続表生成部5は、生成した31行×31列の接続表を出力部6へ送信する。これは「p=q=PN+1」の場合の処理のP=5、N=1の例である。
【0062】
なお、上述した、図2に示す元の乗法表で列を同じくする列同士の対応する行に「○」を格納し、図2で行を同じくする行同士の対応する列に「○」を格納し、他の行を空欄とした表を作成する処理は、例えば、以下のように実現される。
【0063】
接続表生成部5は、Q2行×Q2列の表に対し、(Q+1)個の行と(Q+1)個の列とを追加する。そして、接続表生成部5は、追加した各列について、その行番号が「L<Q2」であるセルのうち、「L」を「Q」で除算した商をQLとすると、その列番号が「Q2+QL」のセルに「○」を格納する。つまり、接続表生成部5は、追加した各列について、図2に示す元の乗法表の対応する行に含まれる各セルに「○」を格納する。
【0064】
また、接続表生成部5は、追加した各行について、その列番号が「C<Q2」であるセルのうち、「C」を「Q」で除算した商をQCとすると、その行番号が「Q2+QC」のセルに「○」を格納する。つまり、接続表生成部5は、追加した各行について、図2に示す元の乗法表の対応する列に含まれる各セルに「○」を格納する。
【0065】
また、接続表生成部5は、追加した各行と追加した各列の交差する各セルについて、行番号又は列番号が「Q2+Q」となるセルに「○」を格納する。つまり、接続表生成部5は、各行および各列のセルに格納された「○」の数が(PN+1)個となるよう、追加した1行と1列に「○」を追加する。
【0066】
例えば、接続表生成部5は、標数が「5」のGF(5)に関わる乗法表と加法表とから25行×25列の接続表を生成する。また、接続標生成部5は、生成した接続表に6個の行と6個の列を追加する。また、接続表生成部5は、行番号が「0〜4」であるセルのうち、「Q2+QL」から算出される列番号「25」のセルに「○」を格納する。また、接続表生成部5は、行番号が「5〜9」であるセルのうち、「Q2+QL」から算出される列番号「26」のセルに「○」を格納する。同様に、接続表生成部5は、各行番号のセルについて、「Q2+QL」で表される列番号のセルに「○」を格納する。
【0067】
また、接続表生成部5は、列番号が「0〜4」であるセルのうち、「Q2+QC」から算出される行番号「25」のセルに「○」を格納する。また、接続表生成部5は、他列番号のセルについても、「Q2+QC」で表される行番号のセルに「○」を格納する。また、接続表生成部5は、行番号が「25〜30」のセルのうち、列番号が「30」であるセルに「○」を格納する。同様に、接続表生成部5は、列番号が「25〜30」のセルのうち行番号が「30」であるセルに「○」を格納する。その後、接続表生成部5は、生成した接続表を出力部6へ送信する。
【0068】
このように、接続表生成部5は、乗法表と加法表とから作成した表と、「Q2+QL」、「Q2+QC」から算出される接続とに基づいて、図6に示す接続表を生成することとしてもよい。
【0069】
ここで、接続表生成部5が作成する接続表においては、各行番号がXBを示し、各列番号がFOを示す。一例を示すと、図6に示す例では、接続表作成部5が作成した接続表は、番号「0」で示されるXBに対して、番号「0」、「5」、「10」、「15」、「20」、「25」で示されるFOを接続する旨を示す。
【0070】
なお、図6中の任意の2列には、共に「○」が格納された同じ行番号の行があり、かつ、この行番号はどの2列に対しても一意に定まる。つまり、図6に従って31個のXBと31個のFOとを接続した場合には、FOの組ごとに通信を中継するXBを一意に定めることができる。
【0071】
次に、「p=PN+1」かつ「q=c(p−1)」である場合に接続表を生成する処理の例を説明する。例えば、利用者が「p=4」、「q=6」を入力した場合には、「p=PN+1」かつ「q=c(p−1)」であり「P=3」、「N=1」、「c=2」となる。
【0072】
このため、接続表生成部5は、乗法表・加法表生成部4からGF(3)の乗法表と加法表とを受信する。接続表生成部5は、GF(3)の乗法表と加法表とを用いて、9行×9列の表を作成する。図8は、「p=4、q=6」の接続表を説明するための図である。図8に示す表において、太線で囲まれた範囲のうち、行番号「0」〜「8」かつ列番号「0」〜「8」の9行×9列の範囲が標数「3」のGF(3)の乗法表と加法表とから作成された表である。
【0073】
また、接続表生成部5は、作成した9行×9列の表に対し、乗法表・加法表生成部4から受信した乗法表の3個の列と対応付けた3個の行を追加し、追加した各行において、対応するもとの乗法表の各列に含まれるそれぞれ3個の列に「○」を格納し、他のセルを空欄とする。つまり、接続表生成部5は、図8に示す例では、行番号「9」〜「11」の行を追加する。そして、接続表生成部5は、行番号「9」の行においては列番号「0」〜「2」のセルに、行番号「10」の行においては列番号「3」〜「5」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成部5は、行番号「11」の行においては列番号「6」〜「8」のセルに「○」を格納し、他のセルを空欄とすることで、12行×9列の表を作成する。
【0074】
その後、接続表生成部5は、作成した12行×9列の表を行方向に「1」回複製した表を作成する。つまり、接続表生成部5は、図8に示す例では、列番号「0」〜「8」の範囲をそのまま列番号「9」〜「17」の範囲に複製した表を生成する。その後、接続表生成部5は、生成した12行×18列の表を出力部6へ送信する。
【0075】
ここで、複製された接続表で同じ位置を示すFOの間については冗長に接続される。
【0076】
また、上述した説明においては、接続表生成部5は、ガロア体の乗法表と加法表とに基づいて表を作成し、作成した表に「p」および「q」に応じた数の行および列を追加することで、接続表を生成した。しかし、接続表生成部5は、「p=q=PN+1」である場合に生成した(Q2+Q+1)行×(Q2+Q+1)列の接続表から、「p」および「q」に応じた数の行および列を削除することで接続表を生成してもよい。
【0077】
つまり、接続表生成部5は、利用者が入力した「p」に基づいて「p=q=PN+1」である際に生成する(Q2+Q+1)行×(Q2+Q+1)列の接続表を生成する。そして、接続表生成部5は、利用者が入力した「p」と「q」とに基づいて、生成した接続表から不要な行および列を削除することで、接続表を生成してもよい。
【0078】
例えば、接続表生成部5は、利用者が「p=6」、「q=5」を入力した場合には、「P=5」、「N=1」として、図6に示した31行×31列の接続表を生成する。次に、接続表生成部5は、作成した31行×31列の接続表のうち、任意の1行を選択し、選択した行が有するセルのうち、「○」が格納されたセルを選択する。そして、接続表生成部5は、31行×31列の接続表から、選択したセルを有する列と、選択した1行とを削除する。
【0079】
図6に示した31行×31列の接続表から行番号「30」の行を選択した場合には、接続表生成部5は、行番号が「30」のセルに「○」が格納された列番号「25」〜「30」までの列と、行番号「30」の行とを接続表から削除する。すると、接続表生成部5は、図7に示す30行×25列の接続表を得る。その後、接続表生成部5は、30行×25列の接続表を出力部6へ送信する。
【0080】
図2に戻って、出力部6は、接続表生成部5によって生成された接続表を受信する。そして、出力部6は、受信した接続表をモニタ8に表示させる。なお、出力部6は、接続表をモニタ8に表示させるだけではなく、例えば、プリンタ等に接続表を示すデータを送信し、接続表をプリンタ等に印刷させてもよい。
【0081】
例えば、受付部2、N次既約多項式生成部3、乗法表・加法表生成部4、接続表生成部5、出力部6とは、電子回路である。ここで、電子回路の例として、ASIC(Application Specific Integrated Circuit)やFPGA(Field Programmable Gate Array)などの集積回路、またはCPU(Central Processing Unit)やMPU(Micro Processing Unit)などを適用する。
【0082】
次に、「p=q=PN+1」の場合に、図6に示した接続表を用いて、接続表生成部5によって生成された接続表により、各FO間の通信を中継するXBが一意に定まる証明を示す。以下の説明では、図6に示す太線で囲まれた5×5個のセルの範囲、つまり、元の乗法表が有する1つのセルに、元の加法表でそのセルと同じ値を持つセル同士に「○」を格納した表をマッピングした範囲を1マスとして説明する。
【0083】
例えば、あるFOの組が2つのXBと冗長に接続されていた場合には、接続表生成部5によって生成された接続表上に、4つの「○」を頂点とし、その各辺が接続表の行と列とに含まれる長方形が存在する。
【0084】
ここで、長方形の1辺が有する2つの頂点が、1つのマスに含まれると仮定する。つまり、元の加法表である同じ値を持つセル同士に「○」を格納した表をマッピングした範囲に2つの「○」を有する行または列があると仮定する。しかし、ガロア体の加法表は、1つの行または1つの列において同じ値が格納されたセルを有しない。つまり、元の加法表からこのように作成した表に2つの「○」を有する行または列は存在しない。この結果、図6上の太線で囲まれた任意の1マスの5×5セルの範囲内に2つの頂点があるという仮定は成立しない。
【0085】
次に、長方形が有する1つの頂点が、接続表のうち加法表と乗法表とから生成された範囲外(以下、外部領域)に存在する場合について説明する。まず、外部領域に「○」を格納する方法から、長方形が有する全ての頂点が外部領域にある長方形が成立しないのは明らかである。また、長方形の1辺が有する1つの頂点が外部領域に存在する場合には、少なくともこの頂点を有する1辺の他の頂点も外部領域に存在することが明らかである。
【0086】
この外部領域に存在する2頂点は、長方形の1辺を構成し、外部領域に「○」を格納する方法から、残る2頂点は共に1つのマスに含まれることとなる。しかし、上述したように、元の加法表、乗法表・加法表生成部4から受信した加法表から作成した表をマッピングした1マスには、2つの頂点があるという仮定が成立しないので、2頂点が外部領域に存在し、2頂点が加法表と乗法表とから生成された範囲に存在する長方形は存在しない。
【0087】
次に、長方形が有する各頂点がそれぞれ異なるマスに存在する場合について説明する。各頂点が存在する各マスについて、元の乗法表、つまり、乗法表・加法表生成部4から受信した乗法表の対応するセルに格納されていた値をそれぞれ「a」、「b」、「c」、「d」と仮定する。ただし、「a」のマスと「d」のマス、および、「b」のマスと「c」のマスとは、それぞれ長方形の対角となる頂点を有するものとする。
【0088】
ここで、「a」のマス、「b」のマス、「c」のマス、「d」のマスは、元の乗法表のそれぞれ異なるセルに対応するため、ガロア体の乗法表から、「a=b=c=d=0」は成立せず、一般性を失わない。このため、「a≠0」とする。
【0089】
長方形の各頂点はそれぞれ異なるマスに存在し、「a≠0」であるから「b≠a」かつ「c≠a」である。また、ガロア体の乗法表の性質から「ad=bc」となる。ここで、接続表が有する全てのマスを重ねると、重ねたマスの中で各頂点は、「a」と「c」、および、「b」と「d」をそれぞれ対角とし、その各辺が加法表の行と列に含まれる長方形あるいは1つの辺を構成する。このため、ガロア体の加法表の性質から「a+d=b+c」となる。
【0090】
ここで、「ad=bc」と「a+d=b+c」とから「(a−b)×(a−c)=0」となるが、「b≠a」かつ「c≠a」と矛盾するので、このような長方形は存在しない。以上より、「p=q=PN+1」の接続表において、FOの組ごとに、接続するXBは一意に定まる。
【0091】
次に、接続表生成装置1が実行する処理の一例について説明する。以下の例では、利用者は、ネットワーク構築のため、3つのポートを有するXBと、4つのポートを有するFO、つまり1つのノードおよび3つのXBに接続可能なFOとを準備するものとする。このような場合には、利用者は、キーボード7を介して「p=q=3」を接続表生成装置1に入力する。
【0092】
このような場合には、接続表生成装置1はf「p=q=3」より「P=2」、「N=1」、を算出し、図9および図10に示すように、標数が「2」であるガロア体GF(2)の乗法表および加法表を生成する。
【0093】
図9は、GF(2)の乗法表を説明するための図である。図9に示すGF(2)の乗法表が有する各セルには、セルの行番号「0〜1」とセルの列番号「0〜1」との積をGF(2)の標数「2」で除算した剰余が格納されている。また、図9に示すように、乗法表の「0」行および「0」列を除く各行および各列には、整数をGF(2)の標数「2」で除算した剰余「0,1」の要素が全て1つずつ含まれる。
【0094】
図10は、GF(2)の加法表を説明するための図である。図10に示すGF(2)の加法表が有する各セルには、セルの行番号「0〜1」とセルの列番号「0〜1」との和をGF(2)の標数「2」で除算した剰余が格納されている。また、図10に示すように、加法表の各行および各列には、整数をGF(2)の標数「2」で除算した剰余「0,1」の要素が全て1つずつ含まれる。
【0095】
また、接続表生成装置1は、図9に示す乗法表が有する「0」が格納された各セルに対して、図10に示す加法表の「0」が格納されたセルに「○」を格納し、他のセルを空欄とした表をマッピングする。また、接続表生成装置1は、乗法表が有する「1」が格納されたセルに対して、加法表の「1」が格納されたセルに「○」を格納し、他のセルを空欄とした表をマッピングした4行×4列の有する表を作成する。
【0096】
図11は、「p=q=3」の接続表を説明するための図である。図11中の太線で示す4行×4列の範囲が、図9に示した乗法表と図10に示した加法表とを用いて作成した表である。続いて、接続表生成装置1は、図9に示す乗法表の列番号「0」の列と対応付けられた行番号「4」と、図9に示す乗法表の列番号「1」の列と対応付けられた行番号「5」の2個の行を追加する。
【0097】
ここで、図9に示す乗法表の列番号「0」の列は、図11に示す列番号「0」および「1」の列となる。このため、接続表生成装置1は、行番号「4」の行については、列番号「0」、「1」のセルに「○」を格納し、他のセルを空欄とする。同様に、図9に示す乗法表の列番号「1」の列は、図11に示す列番号「2」および「3」の列となる。このため、接続表生成装置1は、行番号「5」の行については、列番号「2」、「3」のセルに「○」を格納し、他のセルを空欄とする。
【0098】
次に、接続表生成装置1は、図9に示す乗法表の行番号「0」の行と対応付けられた列番号「4」と図9に示す乗法表の行番号「1」の行と対応付けられた列番号「5」との2個の列を追加する。ここで、図9に示す乗法表の行番号「0」の行は、図11に示す表の行番号「0」、「1」の行となり、図9に示す乗法表の行番号「1」の行は、図11に示す表の行番号「2」、「3」の行となる。このため、接続表生成装置1は、列番号「4」の列については、行番号「0」、「1」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成装置1は、列番号「5」の列については、行番号「2」、「3」のセルに「○」を格納し、他のセルを空欄とする。
【0099】
さらに、接続表生成装置1は、行番号「6」の行と列番号「6」の列とを追加し、「Q2+QL」、「Q2+QC」から各行各列の「○」の数が「3」個となるように、行番号「6」の行と列番号「6」の列とに追加する。つまり、接続表生成装置1は、行番号「6」の行については、列番号「4」、「5」、「6」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成装置1は、列番号「6」の列については、行番号「4」、「5」のセルに「○」を格納し、他のセルを空欄とする。その後、接続表生成装置1は、生成した7行×7列の接続表を出力する。
【0100】
図12は、接続表に従って作成したネットワークを説明するための図である。図12に示す例では、7つのノード10〜16、7つのFO30〜36、7つのXB40〜46を図11に示す接続表に従って接続した。具体的には、各ノード10〜16を各FO30〜36に1つずつ接続する。そして、図11に示す接続表のうち、行番号「0」〜「6」をXB40〜46、列番号「0」〜「6」をFO30〜36と対応付け、「○」が格納されたセルの行番号に対応付けられたXBと列番号に対応付けられたFOとを接続した。
【0101】
なお、各ノード10〜16は、クラスタを構成するコンピュータ、外部のネットワークと接続されたネットワーク装置等である。また、各FO30〜36は、4ポートのファンアウトスイッチであり、各XB40〜46は、3ポートのクロスバスイッチである。
【0102】
例えば、FO30は、データを送信する宛先ノードを示す情報と転送先のXBを示す情報とを対応付けた接続表をあらかじめ記憶する。ノード10は、ノード12にデータを送信する場合には、自装置が接続されたFO30に対して、ノード12を示す識別子を付加したデータをパケットとして送信する。
【0103】
FO30は、自装置に接続されたノード10からパケットを受信した場合には、パケットに付加された識別子から宛先ノード12を判別し、判別した宛先ノード12を示す情報と対応付けて記憶されたXB40を示す情報を接続表から識別する。その後、FO30は、XB40へノード10から受信したパケットを送信する。XB40は、FO30からノード12へのパケットを受信した場合には、受信したパケットをノード12が接続されたFO32へ送信する。その後、FO32は、受信したパケットをノード12へ転送する。
【0104】
[接続表生成装置の処理の流れ]
次に、図13を用いて、接続表生成装置1が実行する処理の流れについて説明する。図13は、実施例1に係る接続表生成装置が実行する処理の流れを説明するためのフローチャートである。接続表生成装置1は、利用者がキーボード7を介して、「p」、「q」を入力したことをトリガとして、処理を開始する。
【0105】
まず、接続表生成装置1は、利用者が入力した「p」、「q」を受け付ける(ステップS101)。次に、接続表生成装置1は、受け付けた「p」、「q」が「p=PN+1」かつ「q=cPN」を満たすか否かを判別する(ステップS102)。そして、接続表生成装置1は、受け付けた「p」、「q」が「p=PN+1」かつ「q=cPN」を満たすと判別した場合には(ステップS102肯定)、「P」および「N」に基づいて、N次既約多項式を生成する(ステップS105)。
【0106】
一方、接続表生成装置1は、「p」、「q」が「p=PN+1」かつ「q=cPN」を満たさないと判別した場合には(ステップS102否定)、「p=PN+1」かつ「q=cp」を満たすか否かを判別する(ステップS103)。そして、接続表生成装置1は、「p」、「q」が「p=PN+1」かつ「q=cp」を満たすと判別した場合には(ステップS103肯定)「P」および「N」に基づいて、N次既約多項式を生成する(ステップS105)。
【0107】
一方、接続表生成装置1は、「p」、「q」が「p=PN+1」かつ「q=cp」を満たさない場合には(ステップS103否定)、「p´≦p」、「q´≦q」、「p´=PN+1」、「q´=cp」となる適切な「p´」、「q´」を選択する(ステップS104)。そして、接続表生成装置1は、「p´=PN+1」、「p´=cPN」となる「P」、「N」に基づいて、N次既約多項式を生成する(ステップS105)。
【0108】
続いて、接続表生成装置1は、生成したN次既約多項式に基づいて、GF(Q=PN)の乗法表と加法表とを生成する(ステップS106)。次に、接続表生成装置1は、生成した乗法表と加法表とからQ2行×Q2列の表を作成する(ステップS107)。次に、接続表生成装置1は、生成したQ2行×Q2列の表に、元の乗法表のQ個の列と対応付けたQ個の行を追加する。そして、接続表生成装置1は、追加した各行において、元の乗法表の対応する列に含まれるそれぞれQ個の列に「○」を格納し、他のセルを空欄とする(Q2+Q)行×Q2列の表を作成する(ステップS108)。
【0109】
次に、接続表生成装置1は、「p=PN+1」かつ「q=cPN」を満たすか否かを判別し(ステップS109)、満たす場合には(ステップS109肯定)、「c≠1」を満たすか否かを判別する(ステップS110)。そして、接続表生成装置1は、「c≠1」を満たす場合には(ステップS110肯定)、作成した(Q2+Q)行×Q2列の表を行方向に「c−1」回複製した(Q2+Q)行×cQ2列の接続表を生成する(ステップS111)。その後、接続表生成装置1は、生成した接続表を出力し(ステップS112)、処理を終了する。また、接続表生成装置1は、「c≠1」を満たさない場合には(ステップS110否定)、(Q2+Q)行×Q2列の接続表を出力し(ステップS112)、処理を終了する。
【0110】
一方、接続表生成装置1は、「p=PN+1」かつ「q=cPN」を満たさない場合には(ステップS109否定)、先に作成した(Q2+Q)行×Q2列の接続表に対し、以下の処理を実行する(ステップS113)。つまり、接続表生成装置1は、元の乗法表のQ個の行と対応付けたQ個の列を追加し、追加した各列において元の乗法表の対応する行に含まれるそれぞれQ個の行に「○」を格納し、他のセルを空欄とした(Q2+Q)行×(Q2+Q)列の表を作成する。
【0111】
次に、接続表生成装置1は、1個の行と1個の列とを追加し、各行各列の「○」の数が「PN+1」となるように、追加した1個の行と1個の列とに「○」を格納する(ステップS114)。この時点で、接続表生成装置1は、(Q2+Q+1)行×(Q2+Q+1)列の接続表を作成している。次に、接続表生成装置1は、「q=cp」とするcが「c≠1」を満たすか否かを判別する(ステップS115)。
【0112】
そして、接続表生成装置1は、cが「c≠1」を満たす場合には(ステップS115肯定)、(Q2+Q+1)行×(Q2+Q+1)列の接続表を行方向にc−1回複製する(ステップS116)。つまり、接続表生成装置1は、(Q2+Q+1)行×c(Q2+Q+1)列の接続表を生成する。その後、接続表生成装置1は、生成した(Q2+Q+1)行×c(Q2+Q+1)列の接続表を出力し(ステップS112)、処理を終了する。
【0113】
一方、接続表生成装置1は、cが「c≠1」を満たさない場合には(ステップS115否定)、(Q2+Q+1)行×(Q2+Q+1)列の接続表を出力し(ステップS112)、処理を終了する。
【0114】
[実施例1の効果]
上述したように、接続表生成装置1は、第1転送装置であるFOのポート数pに基づく値を標数とするガロア体の乗法表と加法表とを作成する。そして、接続表生成装置1は、作成した乗法表と加法表とに基づいて、FOの組ごとに通信を中継するXBを一意に定めた接続表を生成する。
【0115】
このため、接続表生成装置1は、オーバーヘッドの発生を低減できる。つまり、接続表生成装置1が生成した接続表に従って、複数のXBとFOとを接続した場合には、ノード間の通信経路が一意に定まるクロスバネットワークを構築することができる。ここで、各FOは、ノード間の通信経路が一意に定まる場合には、ノード間の通信を中継するXBを選択するルーティング処理を行わずとも、ノード間の通信を中継することができる。この結果、接続表生成装置1は、各FOのルーティング処理を不要とするので、オーバーヘッドの発生を低減できる。
【0116】
また、接続表生成装置1は、各FOと各XBとを相互に接続する従来のクロスバネットワークと比較して、少ない物量でクロスバネットワークを構築するための接続表を作成することができる。以下、接続表生成装置1が少ない物量でクロスバネットワークを構築することができる点について説明する。なお、以下の説明では「p」本のリンクを有するプロセッサをポート数が「q」であるXBにより非閉塞に接続する例について説明するものとし、「p」および「q」は、「p=PN+1」、「q=cPN」を満たすものとする。
【0117】
例えば特許文献1の方法によると、p本のリンクを有するプロセッサとqポートのクロスバスイッチでクロスバネットワークを構築する場合、プロセッサをq/2個ずつ含むp+1個のプロセッサクラスタにより、[(p+1)×p/2]個のクロスバスイッチを使用して、[(p+1)×q/2]個のプロセッサをクロスバ接続可能である。
【0118】
一方、「p」本のリンクを有するプロセッサとは、p個のXBと接続可能なFOに接続されたノードとして考えることができる。そこで、接続表生成装置1によって生成された接続表に基づいて、複数のプロセッサを複数のXBにより接続した場合には、「(p−1)×p」個のXBにより「(p−1)×q」個のプロセッサを接続することができる。
【0119】
つまり、接続表生成装置1が生成した接続表に従って、複数のプロセッサと複数のXBとを接続した場合には、従来と同じポート数のXBを用いて、従来よりも多い数のプロセッサを接続したクロスバネットワークを構築することができる。あるいは、接続表生成装置1が生成した接続表に従って、複数のプロセッサと複数のXBとを接続した場合には、従来と同じ数のプロセッサを接続するクロスバネットワークを少ない資源で構築することができる。
【0120】
また、接続表生成装置1は、乗法表が有する各セルに加法表全体を対応付け、加法表が有する各セルのうち、対応付けた乗法表のセルと同じ値が格納されたセルに接続を示す情報を格納した表を作成する。そして、接続表生成装置1は、作成した表に基づいて、接続表を生成する。このため、接続表生成装置1は、FOの組ごとに通信を中継するXBを一意に定めた接続表を効率的に作成することができる。つまり、接続表生成装置1は、FOの組ごとに通信を中継するXBを定めるための計算等を行わずとも、ネットワークを構築するために用いるXBのポート数に基づくガロア体の乗法表と加法表とに基づいて、容易に接続表を作成することができる。
【0121】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=PN+1」かつ「q=PN」である場合には、標数がQであるガロア体GF(Q)の乗法表と加法表とを用いてQ2行×Q2列の表を作成する。そして、接続表生成装置1は、生成したQ2行×Q2列の表に対し、元の乗法表のQ個の列とそれぞれ対応付けたQ個の行を追加する。その後、接続表生成装置1は、追加したQ個の各行において、元の乗法表の対応する列に含まれるQ個のセルに接続を示す情報を格納する。このため、接続表生成装置1は、容易に接続表を作成することができる。
【0122】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=PN+1」かつ「q=cPN」である場合には、「p=PN+1」かつ「q=PN」である場合に作成した接続表を行方向に「c−1」回複製することで接続表を生成する。このため、接続表生成装置1は、容易に接続表を生成することができる。
【0123】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=q=PN+1」である場合には、「p=PN+1」かつ「q=PN」である場合に作成した接続表に元の乗法表のQ個の行とそれぞれ対応付けたQ個の列を追加する。そして、接続表生成装置1は、追加したQ個の各列において、元の乗法表の対応する行に含まれるQ個のセルに接続を示す情報を格納した表を作成する。さらに、接続表生成装置1は、作成した表に1個の行および列を追加し、各行および各列が有するセルに格納された接続を示す情報の数が「PN+1」となるように、追加した行および列に接続を示す情報を格納する。このため、接続表生成装置1は、容易に接続表を生成することができる。
【0124】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=PN+1」かつ「q=cp」である場合には、「p=q=PN+1」である場合に作成した接続表を行方向に「c−1」回複製することで接続表を生成する。このため、接続表生成装置1は、容易に接続表を作成することができる。
【実施例2】
【0125】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例2として本発明に含まれる他の実施例を説明する。
【0126】
(1)接続表について
接続表生成装置1は、第1の転送装置であるFOと第2の転送装置であるXBとの接続を示す接続表を生成した。しかし、実施例はこれに限定されるものではない。例えば、「p=q=PN+1」を満たす場合には、各FOと各XBとを1対1で対応付けることができる。このため、ポート数が「p+1」のFOとポート数が「q」のXBとをポート数が「p+q−1」のXBに収容する構成も可能である。このため、接続表生成装置1は、それぞれ1つのFOが収容されたXBであって、「p+q−1」個のポートを有するXB同士の接続を示す接続表であって、ノード間の通信経路が一意に定まる接続表を生成してもよい。
【0127】
具体的には、接続表生成装置1は、実施例1において説明した処理と同一の処理を実行する。そして、接続表生成装置1は、各行番号および各列番号を、XBを示す番号として出力する。つまり、接続表生成装置1は、一つのXBが有する複数のポートの一部をFOが有するポートとみなして接続表を生成する。
【0128】
図14は、ファンアウトスイッチを用いずに、クロスバスイッチのみを用いたクロスバネットワーク構成例を説明するための図である。なお、図14に示す点線で結ばれたXBは、同一のXBを示す。図14に示す例では、図12に示したネットワークのうち、各FO30〜36の機能とXB40〜46の機能を、各XB50〜56に収容する。つまり、接続表生成装置1は、各XB50〜56が有する「5」個のポートのうち、「3」個をFO30〜36として、「2」個をXB40〜46として接続表を生成することになる。
【0129】
このように、接続表生成装置1は、入力された「p」および「q」が「p=q=PN+1」を満たす場合には、XB同士の接続を示す接続表を生成してもよい。このような接続表を生成した場合には、接続表生成装置1は、各ノードに接続するFOを不要とするので、ネットワークの構築をさらに容易にすることができる。
【0130】
また、図14に示す各XB50〜56は、ノード10〜16の通信を中継する一つのXBとして動作する。つまり、接続表生成装置1は、「p」および「q」が「p=q=PN+1」を満たす場合には、利用者が準備することができるポート数「q」のXBを用いたネットワークであって、大規模なXBとして動作するネットワークを示す接続表を生成することができる。
【0131】
(2)ネットワークについて
図14のように構築したネットワークは、同様のネットワークとクロスバ接続することによって、1つの大きなXBとして動作することができる。図15は、クロスバスイッチ同士を接続したネットワークを説明するための図である。図15に示す例では、ノード10〜16とノード17〜23がスイッチ60、61を介してクロスバ接続される。
【0132】
また、スイッチ60は、各ポート0〜6にノード10〜16が接続されており、各ポート7〜27にスイッチ61のポート7〜27が接続されている。また、スイッチ61は、各ポート0〜6にノード17〜23が接続されている。
【0133】
図16は、クロスバスイッチ同士の接続例を説明するための図である。図16に示すように、スイッチ60は、図14と同様の接続表に従って接続されるXB70〜76により構築されるクロスバスイッチである。なお、各XB70〜76は、各XB50〜56に3つのポートを追加したXBである。各XB70〜76は、それぞれ1つのポートをポート0〜6として動作させ、残りのポートをポート7〜27として動作させる。なお、スイッチ61は、スイッチ60と同様の構成を有する。
【0134】
スイッチ60とスイッチ61では、それぞれポート7〜9、ポート10〜12、ポート13〜15、ポート16〜18、ポート19〜21、ポート22〜24、ポート25〜27が同じ番号同士で接続されている。つまり、スイッチ60とスイッチ61とは、各XBに追加された3つのポートを介して相互に接続される。
【0135】
例えば、スイッチ60は、ノード10とノード11間の通信を中継する場合には、ノード10から送信されたデータをXB70、XB76、およびXB71を介してノード11へ送信する。つまり、スイッチ60は、各ノード10〜16間の通信を中継する場合には、データをスイッチ60が有する各XB70〜76のうちいずれかのXBを3ホップさせて中継する。
【0136】
また、例えば、スイッチ60は、ノード10とノード18との通信を中継する場合には、ノード18はスイッチ61のポート1に接続することから、まず、ノード18をスイッチ60のポート1に接続するノード11とみなし、ノード10から送信されたデータを、XB70を経由して、XB76からポート25〜27のうち、ノード18に固定的に割り当てた1ポートを介してスイッチ61へ送信する。そして、スイッチ61は、スイッチ60から受信したデータをさらに2ホップさせてノード18へ送信する。
【0137】
なお、ノード17〜23からノード10〜16へのデータの送信についても、同様の処理によって通信が中継される。また、スイッチ60とスイッチ61間においては、ポート7〜27のうち宛先ノードに応じて固定的に割り当てたポートを介してデータを送受信するものとするため、スイッチ60とスイッチ61との間の接続も非閉塞となる。この結果、図15に示すネットワークは、全体としてクロスバネットワークである。
【0138】
上述したようなネットワークの性質から、接続表生成装置1は、以下の処理を行うようにしてもよい。すなわち、接続表生成装置1は、利用者が「p」、「q」を入力した場合には、図14のような「p+q−1」個のXBによるクロスバネットワークを構築するための接続表を生成する。また、接続表生成装置1は、生成した接続表を組み合わせて、図15、図16に示すようなネットワークを示す接続表を生成してもよい。
【0139】
(3)出力形式について
接続表生成装置1は、図6〜図8、11に示すように、行番号を各XBに、列番号を各FOに対応させた表形式の接続表を出力した。しかし、実施例はこれに限定されるものではなく、例えば、図12のように、各FOと各XBとの接続図を出力してもよい。また、接続表生成装置1は、接続を示す情報であれば、任意の形式で出力することができる。
【0140】
(4)プログラム
ところで、実施例1に係る接続表生成装置1、および実施例2に係る接続表生成装置は、ハードウェアを利用して各種の処理を実現する場合を説明した。しかし、実施例はこれに限定されるものではなく、あらかじめ用意されたプログラムを接続表生成装置、又は、コンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図17を用いて、実施例1に示した接続表生成装置1と同様の機能を有するプログラムを実行するコンピュータの一例を説明する。図17は、制御プログラムを実行するコンピュータの一例を説明するための図である。
【0141】
図17に例示されたコンピュータ100は、RAM(Random Access Memory)120、ROM(Read Only Memory)130、HDD(Hard Disk Drive)150がバス170で接続される。また、図17に例示されたコンピュータ100は、CPU(Central Processing Unit)140がバス170で接続される。さらにバス170には、利用者が入力した「p」、「q」を取得し、生成した接続表をモニタ等に出力するためのI/O(Input Output)160が接続される。
【0142】
ROM130には、受付プログラム131、N次既約多項式生成プログラム132、乗法表・加法表生成プログラム133、接続表生成プログラム134、出力プログラム135があらかじめ保持される。CPU140が各プログラム131〜135をROM130から読み出して実行することによって、図17に示す例では、各プログラム131,132は、受付プロセス141、N次既約多項式生成プロセス142として機能するようになる。また、各プログラム133〜135は、乗法表・加法表生成プロセス143、接続表生成プロセス144、出力プロセス145として機能するようになる。なお、各プロセス141〜145は、図1に示した各部2〜6と同様の機能を発揮する。また、各プロセス141〜145は、実施例2に係る接続表生成装置と同等の機能を発揮するようにすることも可能である。
【0143】
なお、本実施例で説明した制御プログラムは、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク(FD)、CD−ROM(Compact Disc Read Only Memory)、MO(Magneto Optical Disc)、DVD(Digital Versatile Disc)などのコンピュータで読取可能な記録媒体に記録される。また、このプログラムは、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【0144】
1 接続表生成装置
2 受付部
3 N次多項式生成部
4 乗法表・加法表生成部
5 接続表生成部
6 出力部
7 キーボード
8 モニタ
10〜23、80〜86 ノード
30〜36 ファンアウトスイッチ(FO)
40〜46、50〜56、70〜76、90〜92 クロスバスイッチ(XB)
60、61、87〜89 スイッチ
【技術分野】
【0001】
本発明は、接続情報生成装置、制御方法および制御プログラムに関する。
【背景技術】
【0002】
従来、複数のノード間で同時に通信を行う際に互いに競合しない通信経路が確保される非閉塞なネットワークの技術が知られている。このような技術の一例として、各ノード間の通信が3つの転送装置を介して行われる非閉塞な3ステージクロス(3 stage Clos)網のネットワークが知られている。
【0003】
図18は、非閉塞な3ステージクロス網のネットワークの一例を説明するための図である。図18に示すネットワーク80は、6つのノード81〜86、第1の転送装置または第3の転送装置として動作するスイッチ87〜89、第2の転送装置として動作するクロスバスイッチ(Crossbar Switch)(以下、「XB」とする)90〜92を有する。
【0004】
またネットワーク80において、各スイッチ87〜89と各XB90〜92とが相互に接続され、各スイッチ87〜89には、それぞれ2つのノードが接続される。ここで、ノードとしては、クラスタを構成するコンピュータ、外部のネットワークと接続されたネットワーク装置等が適用される。
【0005】
このようなネットワーク80のスイッチ87〜89は、ノード間において新たな通信が行われる場合には、他の通信と競合しない通信経路を確保するため、他の通信を中継していないXBを選択する、調停を伴う動的なルーティング処理を実行する。具体的には、スイッチ87〜89は、送信側のノードが接続されたスイッチと受信側のノードが接続されたスイッチとが他の通信に使用していないXBを選択する。そして、スイッチ87〜89は、選択したXBにノード間の新たな通信を中継させる。
【0006】
例えば、スイッチ87は、ノード81とノード86とが新たに通信を行う場合には、自装置とノード86に接続されたスイッチ89とが共に通信に使用していないXBを検索する。この際、スイッチ87は、自装置とスイッチ89がXB91を通信に使用していない場合には、XB91を選択する。その後、スイッチ87は、XB91にノード81とノード86との通信を中継させる。
【先行技術文献】
【特許文献】
【0007】
【特許文献1】特開2007−220100号公報
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかし、上述したスイッチとXBとを相互に接続する技術では、いずれかのノード間において新たな通信が行われる場合には、通信経路の競合を避けるため、調停を伴う動的なルーティング処理を実行する。この結果、ノードが他のノードと通信する際に許容される遅延が短い場合には、調停によって発生するオーバーヘッドが無視できないという問題があった。
【0009】
なお、各スイッチに接続されたノードの数を減らすことで、調停に係るオーバーヘッドを削減する手法が考えられる。しかし、各スイッチに接続されたノードの数を減らして総ノード数の等しい非閉塞なネットワークを構成するには、多くのスイッチを接続することができる大規模なXBが求められる。通常、XBはLSI(Large Scale Integrated Circuit)により実現されるため、多くのスイッチを接続するためには多数のピンが必要となる。
【0010】
従って、このような大規模なXBを入手できない場合に、非閉塞の3ステージクロス網をXBの代替としてネットワークに適用する手法が考えられる。しかし、このようなネットワークにおいても、XBの代替として設置した非閉塞の3ステージクロス網において調停を伴う動的なルーティング処理が行われるため、調停によって発生するオーバーヘッドを削減できない。
【0011】
本願に開示の技術は、調停を伴う動的なルーティング処理を解消し、調停に係るオーバーヘッドの削減を実現する。
【課題を解決するための手段】
【0012】
それぞれ1つのノードが接続された複数の第1転送装置と、各第1転送装置間の通信を中継する複数の第2転送装置との接続に関する情報を生成する接続情報生成装置である。この接続情報生成装置は、1つの第1転送装置に接続する第2転送装置の数に基づく値を標数とするガロア体の加法表と乗法表とを作成する。そして、接続情報生成装置は、作成した乗法表と加法表とに基づいて、第2転送装置を第1転送装置の組ごとに定めた接続に関する情報を生成する。
【発明の効果】
【0013】
調停を伴う動的なルーティング処理を解消し、調停に係るオーバーヘッドの削減を実現する。
【図面の簡単な説明】
【0014】
【図1】図1は、接続表生成装置を説明するための図である。
【図2】図2は、GF(5)の乗法表を説明するための図である。
【図3】図3は、GF(5)の加法表を説明するための図である。
【図4】図4は、GF(8)の乗法表を説明するための図である。
【図5】図5は、GF(8)の加法表を説明するためのである。
【図6】図6は、「p=q=6」の接続表を説明するための図である。
【図7】図7は、実施例1に関わる接続表生成部が生成する「p=6、q=5」の接続表を説明するための図である。
【図8】図8は、「p=4、q=6」の接続表を説明するための図である。
【図9】図9は、GF(2)の乗法表を説明するための図である。
【図10】図10は、GF(2)の加法表を説明するための図である。
【図11】図11は、「p=q=3」の接続表を説明するための図である。
【図12】図12は、接続表に従って作成したネットワークを説明するための図である。
【図13】図13は、実施例1に係る接続表生成装置が実行する処理の流れを説明するためのフローチャートである。
【図14】図14は、ファンアウトスイッチを用いずに、クロスバスイッチのみを用いたクロスバネットワーク構成例を説明するための図である。
【図15】図15は、クロスバスイッチ同士を接続したネットワークを説明するための図である。
【図16】図16は、クロスバスイッチ同士の接続例を説明するための図である。
【図17】図17は、制御プログラムを実行するコンピュータの一例を説明するための図である。
【図18】図18は、非閉塞な3ステージクロス網のネットワークの一例を説明するための図である。
【発明を実施するための形態】
【0015】
以下に添付図面を参照して本願に係る接続情報生成装置、制御方法および制御プログラムについて説明する。
【実施例1】
【0016】
以下の実施例1では、接続情報生成装置の一例を説明する。例えば、接続情報生成装置は、それぞれ1つのノードが接続された複数のファンアウトスイッチ(Fan−out Switch:以下FOと記載する。)と、FO間の通信を中継するクロスバスイッチ(以下XBと記載する。)との接続を示す接続表を作成する。
【0017】
図1は、接続表生成装置の一例を説明するための図である。図1に示すように、接続表生成装置1は、受付部2、N次既約多項式生成部3、乗法表・加法表生成部4、接続表生成部5、出力部6を有する。また、接続表生成装置1の受付部2は、キーボード7と接続されており、後述するように、利用者が指定した数値の入力を受け付ける。また、接続表生成装置1の出力部6は、モニタ8と接続されており、利用者が指定した数値に基づいて生成した接続表をモニタ8に表示する。
【0018】
このような接続表生成装置1は、キーボード7等の入力装置を介して、利用者が入力した各FOに接続することができるXBの数「p」、および、各XBに接続することができるFOの数「q」を取得する。そして、接続表生成装置1は、入力された「p」と「q」に基づいて、複数のFOと複数のXBとの接続表を作成し、作成した接続表をモニタ8に表示させる。
【0019】
以下、接続表生成装置1が各部2〜6を用いて、接続表を作成する処理について詳しく説明する。まず、受付部2は、利用者がキーボード7を用いて入力した各FOに接続することができるXBの数「p」、および、各XBに接続することができるFOの数「q」を取得する。ここで、各FOには1つのノードが接続されるため、「p」は各FOのポート数からノードが接続するポート分である1を減算したものであり、「q」は各XBが有するポートの数となる。換言すると、受付部2は、ネットワークを構築するために利用者が準備することができるXBのポート数「q」とFOのポート数から1を減算した値「p」とを取得する。
【0020】
そして、受付部2は、取得した「p」と「q」とに基づいて、「p=PN+1」、「q=cp」もしくは「q=c(p−1)」を満たす素数「P」、自然数「N」、自然数「c」を算出する。そして、受付部2は、「P」と「N」をN次既約多項式生成部3に通知し、「p」、「q」、「P」、「N」、「c」を接続表生成部5に通知する。
【0021】
また、受付部2は、「p=PN+1」、「q=cp」もしくは「q=c(p−1)」を満たす素数「P」、自然数「N」、整数「c」が存在しない場合には、以下の処理を実行する。すなわち、受付部2は、「p´≦p」、「q´≦q」を満たす適切な「p´」、「q´」について、「p´=PN+1」、「q´=cp´」もしくは「q´=c(p´−1)」を満たす素数「P」、自然数「N」、整数「c」を算出する。その後、受付部2は、「P」と「N」をN次既約多項式生成部3に通知し、「p´」を「p」とし、「q´」を「q」として「p」、「q」、「P」、「N」、「c」を接続表生成部5に通知する。
【0022】
N次既約多項式生成部3は、利用者が入力した「p」および「q」から算出された素数「P」と自然数「N」に基づいて、素数「P」を標数とするガロア体GF(P)上のN次多項式f(X)をGF(P)上既約となるように生成する。そして、N次既約多項式生成部3は、生成したf(X)を乗法表・加法表生成部4に通知する。
【0023】
具体的には、N次既約多項式生成部3は、素数「P」および自然数「N」から以下の式(1)を作成する。ここで、式(1)中のAi(i=0〜N−1)は、0≦Ai<Pを満たす係数である。
【0024】
【数1】
【0025】
ここで、f(X)がGF(P)上既約であるとは、f(X)が以下の式(2)を満たす1次以上の多項式a(X)およびb(X)が存在しないことを言う。
【0026】
【数2】
【0027】
N次既約多項式生成部3は、まずGF(P)上のN次多項式のリストを作成する。次に次数が1〜N−1までのGF(P)上の多項式を全て生成し、生成した多項式の積で表されるN次多項式を先に作成したリストから全て削除する。その後、N次既約多項式生成部3は、リストに残ったN次多項式の1つをN次既約多項式f(X)として乗法表・加法表生成部4に通知する。なお、任意の素数「P」および自然数「N」に対して、既約ではないf(X)が少なくとも1つは存在する。
【0028】
乗法表・加法表生成部4は、N次既約多項式生成部3から通知されたN次既約多項式f(X)を法とし、GF(P)上のN−1次以下の多項式の集合からガロア体GF(PN)の加法表と乗法表とを生成する。つまり、乗法表・加法表生成部4は、利用者が入力した「p」に基づく値「PN」を標数とするガロア体の加法表と乗法表とを生成する。
【0029】
以下、Q=PNとし、乗法表・加法表生成部4が加法表と乗法表とを生成する処理について具体的に説明する。まず、0≦j<Qを満たす任意の整数jは、以下の式(3)によって表現することができる。ここで、式(3)中のBi(i=0〜N−1)は、0≦Bi<Pを満たす係数で、jをP進数で表した場合の各桁の数値である。
【0030】
【数3】
【0031】
式(3)の場合と同様に、GF(P)上のN−1次以下の全ての多項式は、以下の式(4)によって、g(0,X)〜g(Q−1,X)で与えられる。ただし、g(j,P)=jである。
【0032】
【数4】
【0033】
乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して、以下の式(5)に定義する加法を適用することでGF(Q)の加法表を生成する。なお、式(5)中の|+|は、g(i,X)とg(j,X)の和をPで除算した場合の剰余であるGF(P)上の多項式を与える加法を示す記号である。
【0034】
【数5】
【0035】
つまり、乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して式(5)に定義する加法を適用し、式(5)を適用した結果得られる多項式にX=Pを代入した整数値をまとめた加法表を生成する。
【0036】
また、乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して、以下の式(6)に定義する乗法を適用することでGF(Q)の乗法表を生成する。なお、式(6)中の|×|は、g(i,X)とg(j,X)の積をf(X)で除算した場合の剰余を、さらにPで除算した場合の剰余であるGF(P)の多項式を与える乗法を示す記号である。
【0037】
【数6】
【0038】
つまり、乗法表・加法表生成部4は、g(0,X)〜g(Q−1,X)の全ての組み合わせに対して式(6)に定義する乗法を適用し、式(6)を適用した結果得られる多項式にX=Pを代入した整数値をまとめた乗法表を作成する。その後、乗法表・加法表生成部4は、生成した加法表と乗法表とを接続表生成部5に送信する。
【0039】
図2は、GF(5)の乗法表を説明するための図である。また、図3は、GF(5)の加法表を説明するための図である。なお、図2および図3に示す表のうち、点線で囲まれた範囲は、実線で囲まれた各セルの行番号および列番号を示す。
【0040】
例えば、乗法表・加法表生成部4は、利用者が「p=q=6」を入力した場合には、図2に示すGF(5)の乗法表を生成し、生成した乗法表を接続表生成部5に送信する。また、乗法表・加法表生成部4は、利用者が「p=q=6」を入力した場合には、図3に示すGF(5)の加法表を生成し、生成した加法表を接続表生成部5に送信する。
【0041】
図2に示すGF(5)の乗法表が有する各セルには、セルの行番号「0〜4」とセルの列番号「0〜4」との積をGF(5)の標数「5」で除算した剰余が格納されている。また、図2に示すように、乗法表の「0」行および「0」列を除く各行および各列には、整数をGF(5)の標数「5」で除算した剰余「0,1,2,3,4」の要素が全て1つずつ含まれる。
【0042】
また、図3に示すGF(5)の加法表が有する各セルには、セルの行番号「0〜4」とセルの列番号「0〜4」との和をGF(5)の標数「5」で除算した剰余が格納されている。また、図3に示すように、加法表の各行および各列には、整数をGF(5)の標数「5」で除算した剰余「0,1,2,3,4」の要素が全て1つずつ含まれる。
【0043】
図4は、GF(8)の乗法表を説明するための図である。また、図5は、GF(8)の加法表を説明するための図である。なお、図4および図5に示す表のうち、点線で囲まれた範囲は、実線で囲まれた各セルの行番号および列番号を示す。
【0044】
例えば、乗法表・加法表生成部4は、利用者が「p=q=9」を入力した場合には、図4に示す標数が「8」のGF(8)の乗法表を生成し、生成した乗法表を接続表生成部5に送信する。また、乗法表・加法表生成部4は、利用者が「p=q=9」を入力した場合には、図5に示す標数が「8」のGF(8)の加法表を生成し、生成した加法表を接続表生成部5に送信する。なお、図4に示す乗法表および図5に示す加法表は、既約多項式f(X)=x3+x+1を法としたGF(8)=GF(23)の乗法表と加法表とに相当する。
【0045】
図4に示すGF(8)の乗法表が有する各セルには、X=2を代入するとセルの行番号iと等しくなるGF(2)上の2次以下の多項式g(i,X)と、同様にセルの列番号jと等しくなる多項式g(j,X)に対し、f(X)=x3+x+1かつP=2として、式(6)の乗法を適用した結果得られる多項式にX=2を代入した整数値が格納されている。この結果、図4に示すように、標数「8」のガロア体GF(8)における乗法表の「0」行および「0」列を除く各行および各列には、「0,1,2,3,4,5,6,7」の要素が全て1つずつ含まれる。
【0046】
また、図5に示すGF(8)の加法表が有する各セルには、X=2を代入するとセルの行番号iと等しくなるGF(2)上の2次以下の多項式g(i,X)と、同様にセルの列番号jと等しくなる多項式g(j,X)に対し、P=2として、式(5)の加法を適用した結果得られる多項式にX=2を代入した整数値が格納されている。この結果、図5に示すように、標数「8」のガロア体GF(8)における加法表の各行および各列には、「0,1,2,3,4,5,6,7」の要素が全て1つずつ含まれる。
【0047】
接続表生成部5は、乗法表・加法表生成部4が生成した加法表と乗法表とに基づいて、複数のFOと複数のXBとの接続表であって、XBに転送されるFOの組を定めた接続表を生成する。
【0048】
具体的には、接続表生成部5は、乗法表・加法表生成部4から乗法表と加法表とを受信する。また、接続表生成部5は、受信した乗法表の任意の一つのセルを選択し、受信した加法表において、乗法表で選択したセルと同じ値が格納された全てのセルに同じ値が格納された旨を表す「○」を格納し、他の全てのセルを空欄とした表を作成する。その後、接続表生成部5は、作成した表を乗法表の選択したセルにマッピングする。続けて、接続表生成装置5は、同様の処理を乗法表の他の全てのセルについて実行し、受信したガロア体の標数Qを2乗した数の行および列を有する、Q2行×Q2列の表を作成する。
【0049】
続けて、接続表生成部5は、先に作成したQ2行×Q2列の表に対し、図2に示す元の乗法表、つまり乗法表・加法表生成部4が生成した乗法表のQ個の列と対応付けたQ個の行を追加し、追加した各行において、図2の乗法表の対応する列に含まれるそれぞれQ個の列に「○」を格納し、他のセルを空欄とした「p=PN+1」かつ「q=PN」である場合の接続表を生成する。この接続表は(Q2+Q)個の行とQ2個の列を有し、各列は(PN+1)個の、各行はPN個の「○」を含む。「p=PN+1」かつ「q=PN」である場合には、接続表生成部5は、生成した接続表を出力部6へ送信する。
【0050】
また、接続表生成部5は、「p=PN+1」かつ「q=c(p−1)」である場合には、先に作成した「p=PN+1」かつ「q=PN」である場合の(Q2+Q)個の行とQ2個の列を有する接続表を行方向に「c−1」回複製することで生成した(Q2+Q)行×cQ2列のセルを有する接続表を出力部6へ送信する。
【0051】
また、接続表生成部5は、「p=q=PN+1」である場合、もしくは「p=PN+1」かつ「q=cp」である場合には、先に作成した「p=PN+1」かつ「q=PN」である場合の接続表に対し、図2に示す元の乗法表、つまり乗法表・加法表生成部4が生成した乗法表のQ個の行と対応付けたQ個の列を追加し、追加した各列において、図2の対応する行に含まれるそれぞれQ個の行に「○」を格納し、他のセルを空欄とした表を作成する。
【0052】
この表は(Q2+Q)個の行と(Q2+Q)個の列を有する。さらに、接続表生成部5は、この(Q2+Q)行×(Q2+Q)列の表に1個の行と1個の列を追加し、各行、各列の「○」の数が(PN+1)個となるよう、追加した1行と1列に「○」を追加して、「p=q=PN+1」である場合の接続表を生成する。この表は、(Q2+Q+1)行×(Q2+Q+1)列の表である。「p=q=PN+1」である場合には、接続表生成部5は、生成した(Q2+Q+1)行×(Q2+Q+1)列の接続表を出力部6へ送信する。
【0053】
また、接続表生成部5は、「p=PN+1」かつ「q=cp」である場合には、先に作成した「p=q=PN+1」である場合の(Q2+Q+1)行×(Q2+Q+1)列の接続表を行方向に「c−1」回複製することで生成した(Q2+Q+1)行×c(Q2+Q+1)列の接続表を出力部6へ送信する。
【0054】
以下、接続表生成部5が実行する処理の例について説明する。まず、「p=PN+1」かつ「q=PN」、もしくは「p=q=PN+1」の場合に接続表を生成する処理の例を説明する。例えば、接続表生成部5は、利用者が「p=6、q=5」、もしくは「p=q=6」を入力した場合には、図2と図3とに示す標数が5のGF(5)の乗法表と加法表とを受信する。このような場合には、接続表生成部5は、図3に示す加法表のうち「0」が格納された全てのセルに「○」を格納するとともに他のセルを空欄とした表を作成し、作成した表を図2に示す乗法表のうち「0」が格納された全てのセルの位置に配置する。
【0055】
また接続表生成部5は、図3に示す加法表のうち「1」が格納された全てのセルに「○」を格納するとともに他のセルを空欄とした表を作成し、作成した表を図2に示す乗法表のうち「1」が格納された全てのセルの位置に配置する。また、接続表生成部5は、他の値「2」、「3」、「4」が格納されたセルについても同様の処理を実行する。この結果、接続表生成部5は、25行×25列の表を作成する。
【0056】
図7は、実施例1に関わる接続表生成部が生成する「p=6、q=5」の場合の接続表を説明するための図である。図7に示す30行×25列の表のうち、太線で囲んだ25行×25列の範囲が図2に示す乗法表と図3に示す加法表とから作成した表である。すなわち、太線は図2に示す元の乗法表の各セルに対応する。接続表生成部5は、この25行×25列の表に対し、当該図2の5個の列と対応付けた5個の行を追加する。そして、接続表生成部5は、追加した各行において、図2の対応する列に含まれるそれぞれ5個の列に「○」を格納して他のセルを空欄とし、図7に示す30行×25列の接続表を生成する。
【0057】
つまり、接続表生成部5は、まず、図7中行番号「25」〜「29」の行を追加する。ここで、図7中行番号「25」の行は、図2に示す元の乗法表の列番号「0」と対応し、図7中行番号「26」の行は、図2の列番号「1」と対応する。また、図7中行番号「27」の行は、図2の列番号「2」と対応し、図7中行番号「28」の行は、図2の列番号「3」と対応する。また、図7中行番号「29」の行は、図2の列番号「4」と対応する。
【0058】
次に、接続表生成部5は、行番号「25」の行については列番号「0」〜「4」のセルに「○」を格納するとともに、行番号「26」の行については列番号「5」〜「9」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成部5は、行番号「27」の行については列番号「10」〜「14」のセルに「○」を格納し、行番号「28」の行については列番号「15」〜「19」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成部5は、行番号「29」の行については列番号「20」〜「24」のセルに「○」を格納し、他のセルを空欄として、30行×25列の接続表を生成する。「p=6、q=5」の場合には、接続表生成部5は、生成した30行×25列の接続表を出力部6へ送信する。これは「p=PN+1」かつ「q=PN」である場合の処理のP=5、N=1の例である。
【0059】
図6は、接続表生成部5が次に生成する「p=q=6」の場合の接続表を説明するための図である。図6に示す31行×31列の表のうち、列番号「0」〜「24」の30行×25列の範囲が図7に示す「p=6、q=5」の場合の接続表である。図7と同様に、太線は図2に示す元の乗法表の各セルに対応する。接続表生成部5は、この30行×25列の表に対し、図2に示す元の乗法表の5個の行と対応付けた行番号「25」〜「29」の5個の列を追加する。そして、接続表生成部5は、追加した各列において、図2の対応する行に含まれるそれぞれ5個の行に「○」を格納して他のセルを空欄とし、30行×30列の表を生成する。
【0060】
つまり、接続表生成部5は、図6に示す例では、列番号「25」については行番号「0」〜「4」、列番号「26」については行番号「5」〜「9」、列番号「27」については行番号「10」〜「14」のセルに○を格納し、他のセルを空欄とする。また、接続表生成部5は、列番号「28」については行番号「15」〜「19」、列番号「29」については行番号「20」〜「24」のセルに○を格納し、他のセルを空欄とした、30行×30列の表を生成する。
【0061】
さらに、接続表生成部5は、この30行×30列の表に行番号「30」の行と列番号「30」の列とを追加する。そして、接続表生成部5は、各行、各列の「○」の数が6個となるよう、追加した行番号「30」の行と列番号「30」の列とが有する各セルに「○」を追加した31行×31列の接続表を生成する。つまり、接続表生成部5は、行番号「30」の行については、列番号「25」〜「30」のセルに「○」を格納し、列番号「30」の列については、行番号「25」〜「29」のセルに「○」を格納する。「p=q=6」である場合には、接続表生成部5は、生成した31行×31列の接続表を出力部6へ送信する。これは「p=q=PN+1」の場合の処理のP=5、N=1の例である。
【0062】
なお、上述した、図2に示す元の乗法表で列を同じくする列同士の対応する行に「○」を格納し、図2で行を同じくする行同士の対応する列に「○」を格納し、他の行を空欄とした表を作成する処理は、例えば、以下のように実現される。
【0063】
接続表生成部5は、Q2行×Q2列の表に対し、(Q+1)個の行と(Q+1)個の列とを追加する。そして、接続表生成部5は、追加した各列について、その行番号が「L<Q2」であるセルのうち、「L」を「Q」で除算した商をQLとすると、その列番号が「Q2+QL」のセルに「○」を格納する。つまり、接続表生成部5は、追加した各列について、図2に示す元の乗法表の対応する行に含まれる各セルに「○」を格納する。
【0064】
また、接続表生成部5は、追加した各行について、その列番号が「C<Q2」であるセルのうち、「C」を「Q」で除算した商をQCとすると、その行番号が「Q2+QC」のセルに「○」を格納する。つまり、接続表生成部5は、追加した各行について、図2に示す元の乗法表の対応する列に含まれる各セルに「○」を格納する。
【0065】
また、接続表生成部5は、追加した各行と追加した各列の交差する各セルについて、行番号又は列番号が「Q2+Q」となるセルに「○」を格納する。つまり、接続表生成部5は、各行および各列のセルに格納された「○」の数が(PN+1)個となるよう、追加した1行と1列に「○」を追加する。
【0066】
例えば、接続表生成部5は、標数が「5」のGF(5)に関わる乗法表と加法表とから25行×25列の接続表を生成する。また、接続標生成部5は、生成した接続表に6個の行と6個の列を追加する。また、接続表生成部5は、行番号が「0〜4」であるセルのうち、「Q2+QL」から算出される列番号「25」のセルに「○」を格納する。また、接続表生成部5は、行番号が「5〜9」であるセルのうち、「Q2+QL」から算出される列番号「26」のセルに「○」を格納する。同様に、接続表生成部5は、各行番号のセルについて、「Q2+QL」で表される列番号のセルに「○」を格納する。
【0067】
また、接続表生成部5は、列番号が「0〜4」であるセルのうち、「Q2+QC」から算出される行番号「25」のセルに「○」を格納する。また、接続表生成部5は、他列番号のセルについても、「Q2+QC」で表される行番号のセルに「○」を格納する。また、接続表生成部5は、行番号が「25〜30」のセルのうち、列番号が「30」であるセルに「○」を格納する。同様に、接続表生成部5は、列番号が「25〜30」のセルのうち行番号が「30」であるセルに「○」を格納する。その後、接続表生成部5は、生成した接続表を出力部6へ送信する。
【0068】
このように、接続表生成部5は、乗法表と加法表とから作成した表と、「Q2+QL」、「Q2+QC」から算出される接続とに基づいて、図6に示す接続表を生成することとしてもよい。
【0069】
ここで、接続表生成部5が作成する接続表においては、各行番号がXBを示し、各列番号がFOを示す。一例を示すと、図6に示す例では、接続表作成部5が作成した接続表は、番号「0」で示されるXBに対して、番号「0」、「5」、「10」、「15」、「20」、「25」で示されるFOを接続する旨を示す。
【0070】
なお、図6中の任意の2列には、共に「○」が格納された同じ行番号の行があり、かつ、この行番号はどの2列に対しても一意に定まる。つまり、図6に従って31個のXBと31個のFOとを接続した場合には、FOの組ごとに通信を中継するXBを一意に定めることができる。
【0071】
次に、「p=PN+1」かつ「q=c(p−1)」である場合に接続表を生成する処理の例を説明する。例えば、利用者が「p=4」、「q=6」を入力した場合には、「p=PN+1」かつ「q=c(p−1)」であり「P=3」、「N=1」、「c=2」となる。
【0072】
このため、接続表生成部5は、乗法表・加法表生成部4からGF(3)の乗法表と加法表とを受信する。接続表生成部5は、GF(3)の乗法表と加法表とを用いて、9行×9列の表を作成する。図8は、「p=4、q=6」の接続表を説明するための図である。図8に示す表において、太線で囲まれた範囲のうち、行番号「0」〜「8」かつ列番号「0」〜「8」の9行×9列の範囲が標数「3」のGF(3)の乗法表と加法表とから作成された表である。
【0073】
また、接続表生成部5は、作成した9行×9列の表に対し、乗法表・加法表生成部4から受信した乗法表の3個の列と対応付けた3個の行を追加し、追加した各行において、対応するもとの乗法表の各列に含まれるそれぞれ3個の列に「○」を格納し、他のセルを空欄とする。つまり、接続表生成部5は、図8に示す例では、行番号「9」〜「11」の行を追加する。そして、接続表生成部5は、行番号「9」の行においては列番号「0」〜「2」のセルに、行番号「10」の行においては列番号「3」〜「5」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成部5は、行番号「11」の行においては列番号「6」〜「8」のセルに「○」を格納し、他のセルを空欄とすることで、12行×9列の表を作成する。
【0074】
その後、接続表生成部5は、作成した12行×9列の表を行方向に「1」回複製した表を作成する。つまり、接続表生成部5は、図8に示す例では、列番号「0」〜「8」の範囲をそのまま列番号「9」〜「17」の範囲に複製した表を生成する。その後、接続表生成部5は、生成した12行×18列の表を出力部6へ送信する。
【0075】
ここで、複製された接続表で同じ位置を示すFOの間については冗長に接続される。
【0076】
また、上述した説明においては、接続表生成部5は、ガロア体の乗法表と加法表とに基づいて表を作成し、作成した表に「p」および「q」に応じた数の行および列を追加することで、接続表を生成した。しかし、接続表生成部5は、「p=q=PN+1」である場合に生成した(Q2+Q+1)行×(Q2+Q+1)列の接続表から、「p」および「q」に応じた数の行および列を削除することで接続表を生成してもよい。
【0077】
つまり、接続表生成部5は、利用者が入力した「p」に基づいて「p=q=PN+1」である際に生成する(Q2+Q+1)行×(Q2+Q+1)列の接続表を生成する。そして、接続表生成部5は、利用者が入力した「p」と「q」とに基づいて、生成した接続表から不要な行および列を削除することで、接続表を生成してもよい。
【0078】
例えば、接続表生成部5は、利用者が「p=6」、「q=5」を入力した場合には、「P=5」、「N=1」として、図6に示した31行×31列の接続表を生成する。次に、接続表生成部5は、作成した31行×31列の接続表のうち、任意の1行を選択し、選択した行が有するセルのうち、「○」が格納されたセルを選択する。そして、接続表生成部5は、31行×31列の接続表から、選択したセルを有する列と、選択した1行とを削除する。
【0079】
図6に示した31行×31列の接続表から行番号「30」の行を選択した場合には、接続表生成部5は、行番号が「30」のセルに「○」が格納された列番号「25」〜「30」までの列と、行番号「30」の行とを接続表から削除する。すると、接続表生成部5は、図7に示す30行×25列の接続表を得る。その後、接続表生成部5は、30行×25列の接続表を出力部6へ送信する。
【0080】
図2に戻って、出力部6は、接続表生成部5によって生成された接続表を受信する。そして、出力部6は、受信した接続表をモニタ8に表示させる。なお、出力部6は、接続表をモニタ8に表示させるだけではなく、例えば、プリンタ等に接続表を示すデータを送信し、接続表をプリンタ等に印刷させてもよい。
【0081】
例えば、受付部2、N次既約多項式生成部3、乗法表・加法表生成部4、接続表生成部5、出力部6とは、電子回路である。ここで、電子回路の例として、ASIC(Application Specific Integrated Circuit)やFPGA(Field Programmable Gate Array)などの集積回路、またはCPU(Central Processing Unit)やMPU(Micro Processing Unit)などを適用する。
【0082】
次に、「p=q=PN+1」の場合に、図6に示した接続表を用いて、接続表生成部5によって生成された接続表により、各FO間の通信を中継するXBが一意に定まる証明を示す。以下の説明では、図6に示す太線で囲まれた5×5個のセルの範囲、つまり、元の乗法表が有する1つのセルに、元の加法表でそのセルと同じ値を持つセル同士に「○」を格納した表をマッピングした範囲を1マスとして説明する。
【0083】
例えば、あるFOの組が2つのXBと冗長に接続されていた場合には、接続表生成部5によって生成された接続表上に、4つの「○」を頂点とし、その各辺が接続表の行と列とに含まれる長方形が存在する。
【0084】
ここで、長方形の1辺が有する2つの頂点が、1つのマスに含まれると仮定する。つまり、元の加法表である同じ値を持つセル同士に「○」を格納した表をマッピングした範囲に2つの「○」を有する行または列があると仮定する。しかし、ガロア体の加法表は、1つの行または1つの列において同じ値が格納されたセルを有しない。つまり、元の加法表からこのように作成した表に2つの「○」を有する行または列は存在しない。この結果、図6上の太線で囲まれた任意の1マスの5×5セルの範囲内に2つの頂点があるという仮定は成立しない。
【0085】
次に、長方形が有する1つの頂点が、接続表のうち加法表と乗法表とから生成された範囲外(以下、外部領域)に存在する場合について説明する。まず、外部領域に「○」を格納する方法から、長方形が有する全ての頂点が外部領域にある長方形が成立しないのは明らかである。また、長方形の1辺が有する1つの頂点が外部領域に存在する場合には、少なくともこの頂点を有する1辺の他の頂点も外部領域に存在することが明らかである。
【0086】
この外部領域に存在する2頂点は、長方形の1辺を構成し、外部領域に「○」を格納する方法から、残る2頂点は共に1つのマスに含まれることとなる。しかし、上述したように、元の加法表、乗法表・加法表生成部4から受信した加法表から作成した表をマッピングした1マスには、2つの頂点があるという仮定が成立しないので、2頂点が外部領域に存在し、2頂点が加法表と乗法表とから生成された範囲に存在する長方形は存在しない。
【0087】
次に、長方形が有する各頂点がそれぞれ異なるマスに存在する場合について説明する。各頂点が存在する各マスについて、元の乗法表、つまり、乗法表・加法表生成部4から受信した乗法表の対応するセルに格納されていた値をそれぞれ「a」、「b」、「c」、「d」と仮定する。ただし、「a」のマスと「d」のマス、および、「b」のマスと「c」のマスとは、それぞれ長方形の対角となる頂点を有するものとする。
【0088】
ここで、「a」のマス、「b」のマス、「c」のマス、「d」のマスは、元の乗法表のそれぞれ異なるセルに対応するため、ガロア体の乗法表から、「a=b=c=d=0」は成立せず、一般性を失わない。このため、「a≠0」とする。
【0089】
長方形の各頂点はそれぞれ異なるマスに存在し、「a≠0」であるから「b≠a」かつ「c≠a」である。また、ガロア体の乗法表の性質から「ad=bc」となる。ここで、接続表が有する全てのマスを重ねると、重ねたマスの中で各頂点は、「a」と「c」、および、「b」と「d」をそれぞれ対角とし、その各辺が加法表の行と列に含まれる長方形あるいは1つの辺を構成する。このため、ガロア体の加法表の性質から「a+d=b+c」となる。
【0090】
ここで、「ad=bc」と「a+d=b+c」とから「(a−b)×(a−c)=0」となるが、「b≠a」かつ「c≠a」と矛盾するので、このような長方形は存在しない。以上より、「p=q=PN+1」の接続表において、FOの組ごとに、接続するXBは一意に定まる。
【0091】
次に、接続表生成装置1が実行する処理の一例について説明する。以下の例では、利用者は、ネットワーク構築のため、3つのポートを有するXBと、4つのポートを有するFO、つまり1つのノードおよび3つのXBに接続可能なFOとを準備するものとする。このような場合には、利用者は、キーボード7を介して「p=q=3」を接続表生成装置1に入力する。
【0092】
このような場合には、接続表生成装置1はf「p=q=3」より「P=2」、「N=1」、を算出し、図9および図10に示すように、標数が「2」であるガロア体GF(2)の乗法表および加法表を生成する。
【0093】
図9は、GF(2)の乗法表を説明するための図である。図9に示すGF(2)の乗法表が有する各セルには、セルの行番号「0〜1」とセルの列番号「0〜1」との積をGF(2)の標数「2」で除算した剰余が格納されている。また、図9に示すように、乗法表の「0」行および「0」列を除く各行および各列には、整数をGF(2)の標数「2」で除算した剰余「0,1」の要素が全て1つずつ含まれる。
【0094】
図10は、GF(2)の加法表を説明するための図である。図10に示すGF(2)の加法表が有する各セルには、セルの行番号「0〜1」とセルの列番号「0〜1」との和をGF(2)の標数「2」で除算した剰余が格納されている。また、図10に示すように、加法表の各行および各列には、整数をGF(2)の標数「2」で除算した剰余「0,1」の要素が全て1つずつ含まれる。
【0095】
また、接続表生成装置1は、図9に示す乗法表が有する「0」が格納された各セルに対して、図10に示す加法表の「0」が格納されたセルに「○」を格納し、他のセルを空欄とした表をマッピングする。また、接続表生成装置1は、乗法表が有する「1」が格納されたセルに対して、加法表の「1」が格納されたセルに「○」を格納し、他のセルを空欄とした表をマッピングした4行×4列の有する表を作成する。
【0096】
図11は、「p=q=3」の接続表を説明するための図である。図11中の太線で示す4行×4列の範囲が、図9に示した乗法表と図10に示した加法表とを用いて作成した表である。続いて、接続表生成装置1は、図9に示す乗法表の列番号「0」の列と対応付けられた行番号「4」と、図9に示す乗法表の列番号「1」の列と対応付けられた行番号「5」の2個の行を追加する。
【0097】
ここで、図9に示す乗法表の列番号「0」の列は、図11に示す列番号「0」および「1」の列となる。このため、接続表生成装置1は、行番号「4」の行については、列番号「0」、「1」のセルに「○」を格納し、他のセルを空欄とする。同様に、図9に示す乗法表の列番号「1」の列は、図11に示す列番号「2」および「3」の列となる。このため、接続表生成装置1は、行番号「5」の行については、列番号「2」、「3」のセルに「○」を格納し、他のセルを空欄とする。
【0098】
次に、接続表生成装置1は、図9に示す乗法表の行番号「0」の行と対応付けられた列番号「4」と図9に示す乗法表の行番号「1」の行と対応付けられた列番号「5」との2個の列を追加する。ここで、図9に示す乗法表の行番号「0」の行は、図11に示す表の行番号「0」、「1」の行となり、図9に示す乗法表の行番号「1」の行は、図11に示す表の行番号「2」、「3」の行となる。このため、接続表生成装置1は、列番号「4」の列については、行番号「0」、「1」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成装置1は、列番号「5」の列については、行番号「2」、「3」のセルに「○」を格納し、他のセルを空欄とする。
【0099】
さらに、接続表生成装置1は、行番号「6」の行と列番号「6」の列とを追加し、「Q2+QL」、「Q2+QC」から各行各列の「○」の数が「3」個となるように、行番号「6」の行と列番号「6」の列とに追加する。つまり、接続表生成装置1は、行番号「6」の行については、列番号「4」、「5」、「6」のセルに「○」を格納し、他のセルを空欄とする。また、接続表生成装置1は、列番号「6」の列については、行番号「4」、「5」のセルに「○」を格納し、他のセルを空欄とする。その後、接続表生成装置1は、生成した7行×7列の接続表を出力する。
【0100】
図12は、接続表に従って作成したネットワークを説明するための図である。図12に示す例では、7つのノード10〜16、7つのFO30〜36、7つのXB40〜46を図11に示す接続表に従って接続した。具体的には、各ノード10〜16を各FO30〜36に1つずつ接続する。そして、図11に示す接続表のうち、行番号「0」〜「6」をXB40〜46、列番号「0」〜「6」をFO30〜36と対応付け、「○」が格納されたセルの行番号に対応付けられたXBと列番号に対応付けられたFOとを接続した。
【0101】
なお、各ノード10〜16は、クラスタを構成するコンピュータ、外部のネットワークと接続されたネットワーク装置等である。また、各FO30〜36は、4ポートのファンアウトスイッチであり、各XB40〜46は、3ポートのクロスバスイッチである。
【0102】
例えば、FO30は、データを送信する宛先ノードを示す情報と転送先のXBを示す情報とを対応付けた接続表をあらかじめ記憶する。ノード10は、ノード12にデータを送信する場合には、自装置が接続されたFO30に対して、ノード12を示す識別子を付加したデータをパケットとして送信する。
【0103】
FO30は、自装置に接続されたノード10からパケットを受信した場合には、パケットに付加された識別子から宛先ノード12を判別し、判別した宛先ノード12を示す情報と対応付けて記憶されたXB40を示す情報を接続表から識別する。その後、FO30は、XB40へノード10から受信したパケットを送信する。XB40は、FO30からノード12へのパケットを受信した場合には、受信したパケットをノード12が接続されたFO32へ送信する。その後、FO32は、受信したパケットをノード12へ転送する。
【0104】
[接続表生成装置の処理の流れ]
次に、図13を用いて、接続表生成装置1が実行する処理の流れについて説明する。図13は、実施例1に係る接続表生成装置が実行する処理の流れを説明するためのフローチャートである。接続表生成装置1は、利用者がキーボード7を介して、「p」、「q」を入力したことをトリガとして、処理を開始する。
【0105】
まず、接続表生成装置1は、利用者が入力した「p」、「q」を受け付ける(ステップS101)。次に、接続表生成装置1は、受け付けた「p」、「q」が「p=PN+1」かつ「q=cPN」を満たすか否かを判別する(ステップS102)。そして、接続表生成装置1は、受け付けた「p」、「q」が「p=PN+1」かつ「q=cPN」を満たすと判別した場合には(ステップS102肯定)、「P」および「N」に基づいて、N次既約多項式を生成する(ステップS105)。
【0106】
一方、接続表生成装置1は、「p」、「q」が「p=PN+1」かつ「q=cPN」を満たさないと判別した場合には(ステップS102否定)、「p=PN+1」かつ「q=cp」を満たすか否かを判別する(ステップS103)。そして、接続表生成装置1は、「p」、「q」が「p=PN+1」かつ「q=cp」を満たすと判別した場合には(ステップS103肯定)「P」および「N」に基づいて、N次既約多項式を生成する(ステップS105)。
【0107】
一方、接続表生成装置1は、「p」、「q」が「p=PN+1」かつ「q=cp」を満たさない場合には(ステップS103否定)、「p´≦p」、「q´≦q」、「p´=PN+1」、「q´=cp」となる適切な「p´」、「q´」を選択する(ステップS104)。そして、接続表生成装置1は、「p´=PN+1」、「p´=cPN」となる「P」、「N」に基づいて、N次既約多項式を生成する(ステップS105)。
【0108】
続いて、接続表生成装置1は、生成したN次既約多項式に基づいて、GF(Q=PN)の乗法表と加法表とを生成する(ステップS106)。次に、接続表生成装置1は、生成した乗法表と加法表とからQ2行×Q2列の表を作成する(ステップS107)。次に、接続表生成装置1は、生成したQ2行×Q2列の表に、元の乗法表のQ個の列と対応付けたQ個の行を追加する。そして、接続表生成装置1は、追加した各行において、元の乗法表の対応する列に含まれるそれぞれQ個の列に「○」を格納し、他のセルを空欄とする(Q2+Q)行×Q2列の表を作成する(ステップS108)。
【0109】
次に、接続表生成装置1は、「p=PN+1」かつ「q=cPN」を満たすか否かを判別し(ステップS109)、満たす場合には(ステップS109肯定)、「c≠1」を満たすか否かを判別する(ステップS110)。そして、接続表生成装置1は、「c≠1」を満たす場合には(ステップS110肯定)、作成した(Q2+Q)行×Q2列の表を行方向に「c−1」回複製した(Q2+Q)行×cQ2列の接続表を生成する(ステップS111)。その後、接続表生成装置1は、生成した接続表を出力し(ステップS112)、処理を終了する。また、接続表生成装置1は、「c≠1」を満たさない場合には(ステップS110否定)、(Q2+Q)行×Q2列の接続表を出力し(ステップS112)、処理を終了する。
【0110】
一方、接続表生成装置1は、「p=PN+1」かつ「q=cPN」を満たさない場合には(ステップS109否定)、先に作成した(Q2+Q)行×Q2列の接続表に対し、以下の処理を実行する(ステップS113)。つまり、接続表生成装置1は、元の乗法表のQ個の行と対応付けたQ個の列を追加し、追加した各列において元の乗法表の対応する行に含まれるそれぞれQ個の行に「○」を格納し、他のセルを空欄とした(Q2+Q)行×(Q2+Q)列の表を作成する。
【0111】
次に、接続表生成装置1は、1個の行と1個の列とを追加し、各行各列の「○」の数が「PN+1」となるように、追加した1個の行と1個の列とに「○」を格納する(ステップS114)。この時点で、接続表生成装置1は、(Q2+Q+1)行×(Q2+Q+1)列の接続表を作成している。次に、接続表生成装置1は、「q=cp」とするcが「c≠1」を満たすか否かを判別する(ステップS115)。
【0112】
そして、接続表生成装置1は、cが「c≠1」を満たす場合には(ステップS115肯定)、(Q2+Q+1)行×(Q2+Q+1)列の接続表を行方向にc−1回複製する(ステップS116)。つまり、接続表生成装置1は、(Q2+Q+1)行×c(Q2+Q+1)列の接続表を生成する。その後、接続表生成装置1は、生成した(Q2+Q+1)行×c(Q2+Q+1)列の接続表を出力し(ステップS112)、処理を終了する。
【0113】
一方、接続表生成装置1は、cが「c≠1」を満たさない場合には(ステップS115否定)、(Q2+Q+1)行×(Q2+Q+1)列の接続表を出力し(ステップS112)、処理を終了する。
【0114】
[実施例1の効果]
上述したように、接続表生成装置1は、第1転送装置であるFOのポート数pに基づく値を標数とするガロア体の乗法表と加法表とを作成する。そして、接続表生成装置1は、作成した乗法表と加法表とに基づいて、FOの組ごとに通信を中継するXBを一意に定めた接続表を生成する。
【0115】
このため、接続表生成装置1は、オーバーヘッドの発生を低減できる。つまり、接続表生成装置1が生成した接続表に従って、複数のXBとFOとを接続した場合には、ノード間の通信経路が一意に定まるクロスバネットワークを構築することができる。ここで、各FOは、ノード間の通信経路が一意に定まる場合には、ノード間の通信を中継するXBを選択するルーティング処理を行わずとも、ノード間の通信を中継することができる。この結果、接続表生成装置1は、各FOのルーティング処理を不要とするので、オーバーヘッドの発生を低減できる。
【0116】
また、接続表生成装置1は、各FOと各XBとを相互に接続する従来のクロスバネットワークと比較して、少ない物量でクロスバネットワークを構築するための接続表を作成することができる。以下、接続表生成装置1が少ない物量でクロスバネットワークを構築することができる点について説明する。なお、以下の説明では「p」本のリンクを有するプロセッサをポート数が「q」であるXBにより非閉塞に接続する例について説明するものとし、「p」および「q」は、「p=PN+1」、「q=cPN」を満たすものとする。
【0117】
例えば特許文献1の方法によると、p本のリンクを有するプロセッサとqポートのクロスバスイッチでクロスバネットワークを構築する場合、プロセッサをq/2個ずつ含むp+1個のプロセッサクラスタにより、[(p+1)×p/2]個のクロスバスイッチを使用して、[(p+1)×q/2]個のプロセッサをクロスバ接続可能である。
【0118】
一方、「p」本のリンクを有するプロセッサとは、p個のXBと接続可能なFOに接続されたノードとして考えることができる。そこで、接続表生成装置1によって生成された接続表に基づいて、複数のプロセッサを複数のXBにより接続した場合には、「(p−1)×p」個のXBにより「(p−1)×q」個のプロセッサを接続することができる。
【0119】
つまり、接続表生成装置1が生成した接続表に従って、複数のプロセッサと複数のXBとを接続した場合には、従来と同じポート数のXBを用いて、従来よりも多い数のプロセッサを接続したクロスバネットワークを構築することができる。あるいは、接続表生成装置1が生成した接続表に従って、複数のプロセッサと複数のXBとを接続した場合には、従来と同じ数のプロセッサを接続するクロスバネットワークを少ない資源で構築することができる。
【0120】
また、接続表生成装置1は、乗法表が有する各セルに加法表全体を対応付け、加法表が有する各セルのうち、対応付けた乗法表のセルと同じ値が格納されたセルに接続を示す情報を格納した表を作成する。そして、接続表生成装置1は、作成した表に基づいて、接続表を生成する。このため、接続表生成装置1は、FOの組ごとに通信を中継するXBを一意に定めた接続表を効率的に作成することができる。つまり、接続表生成装置1は、FOの組ごとに通信を中継するXBを定めるための計算等を行わずとも、ネットワークを構築するために用いるXBのポート数に基づくガロア体の乗法表と加法表とに基づいて、容易に接続表を作成することができる。
【0121】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=PN+1」かつ「q=PN」である場合には、標数がQであるガロア体GF(Q)の乗法表と加法表とを用いてQ2行×Q2列の表を作成する。そして、接続表生成装置1は、生成したQ2行×Q2列の表に対し、元の乗法表のQ個の列とそれぞれ対応付けたQ個の行を追加する。その後、接続表生成装置1は、追加したQ個の各行において、元の乗法表の対応する列に含まれるQ個のセルに接続を示す情報を格納する。このため、接続表生成装置1は、容易に接続表を作成することができる。
【0122】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=PN+1」かつ「q=cPN」である場合には、「p=PN+1」かつ「q=PN」である場合に作成した接続表を行方向に「c−1」回複製することで接続表を生成する。このため、接続表生成装置1は、容易に接続表を生成することができる。
【0123】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=q=PN+1」である場合には、「p=PN+1」かつ「q=PN」である場合に作成した接続表に元の乗法表のQ個の行とそれぞれ対応付けたQ個の列を追加する。そして、接続表生成装置1は、追加したQ個の各列において、元の乗法表の対応する行に含まれるQ個のセルに接続を示す情報を格納した表を作成する。さらに、接続表生成装置1は、作成した表に1個の行および列を追加し、各行および各列が有するセルに格納された接続を示す情報の数が「PN+1」となるように、追加した行および列に接続を示す情報を格納する。このため、接続表生成装置1は、容易に接続表を生成することができる。
【0124】
また、接続表生成装置1は、受け付けた「p」と「q」とが「p=PN+1」かつ「q=cp」である場合には、「p=q=PN+1」である場合に作成した接続表を行方向に「c−1」回複製することで接続表を生成する。このため、接続表生成装置1は、容易に接続表を作成することができる。
【実施例2】
【0125】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例2として本発明に含まれる他の実施例を説明する。
【0126】
(1)接続表について
接続表生成装置1は、第1の転送装置であるFOと第2の転送装置であるXBとの接続を示す接続表を生成した。しかし、実施例はこれに限定されるものではない。例えば、「p=q=PN+1」を満たす場合には、各FOと各XBとを1対1で対応付けることができる。このため、ポート数が「p+1」のFOとポート数が「q」のXBとをポート数が「p+q−1」のXBに収容する構成も可能である。このため、接続表生成装置1は、それぞれ1つのFOが収容されたXBであって、「p+q−1」個のポートを有するXB同士の接続を示す接続表であって、ノード間の通信経路が一意に定まる接続表を生成してもよい。
【0127】
具体的には、接続表生成装置1は、実施例1において説明した処理と同一の処理を実行する。そして、接続表生成装置1は、各行番号および各列番号を、XBを示す番号として出力する。つまり、接続表生成装置1は、一つのXBが有する複数のポートの一部をFOが有するポートとみなして接続表を生成する。
【0128】
図14は、ファンアウトスイッチを用いずに、クロスバスイッチのみを用いたクロスバネットワーク構成例を説明するための図である。なお、図14に示す点線で結ばれたXBは、同一のXBを示す。図14に示す例では、図12に示したネットワークのうち、各FO30〜36の機能とXB40〜46の機能を、各XB50〜56に収容する。つまり、接続表生成装置1は、各XB50〜56が有する「5」個のポートのうち、「3」個をFO30〜36として、「2」個をXB40〜46として接続表を生成することになる。
【0129】
このように、接続表生成装置1は、入力された「p」および「q」が「p=q=PN+1」を満たす場合には、XB同士の接続を示す接続表を生成してもよい。このような接続表を生成した場合には、接続表生成装置1は、各ノードに接続するFOを不要とするので、ネットワークの構築をさらに容易にすることができる。
【0130】
また、図14に示す各XB50〜56は、ノード10〜16の通信を中継する一つのXBとして動作する。つまり、接続表生成装置1は、「p」および「q」が「p=q=PN+1」を満たす場合には、利用者が準備することができるポート数「q」のXBを用いたネットワークであって、大規模なXBとして動作するネットワークを示す接続表を生成することができる。
【0131】
(2)ネットワークについて
図14のように構築したネットワークは、同様のネットワークとクロスバ接続することによって、1つの大きなXBとして動作することができる。図15は、クロスバスイッチ同士を接続したネットワークを説明するための図である。図15に示す例では、ノード10〜16とノード17〜23がスイッチ60、61を介してクロスバ接続される。
【0132】
また、スイッチ60は、各ポート0〜6にノード10〜16が接続されており、各ポート7〜27にスイッチ61のポート7〜27が接続されている。また、スイッチ61は、各ポート0〜6にノード17〜23が接続されている。
【0133】
図16は、クロスバスイッチ同士の接続例を説明するための図である。図16に示すように、スイッチ60は、図14と同様の接続表に従って接続されるXB70〜76により構築されるクロスバスイッチである。なお、各XB70〜76は、各XB50〜56に3つのポートを追加したXBである。各XB70〜76は、それぞれ1つのポートをポート0〜6として動作させ、残りのポートをポート7〜27として動作させる。なお、スイッチ61は、スイッチ60と同様の構成を有する。
【0134】
スイッチ60とスイッチ61では、それぞれポート7〜9、ポート10〜12、ポート13〜15、ポート16〜18、ポート19〜21、ポート22〜24、ポート25〜27が同じ番号同士で接続されている。つまり、スイッチ60とスイッチ61とは、各XBに追加された3つのポートを介して相互に接続される。
【0135】
例えば、スイッチ60は、ノード10とノード11間の通信を中継する場合には、ノード10から送信されたデータをXB70、XB76、およびXB71を介してノード11へ送信する。つまり、スイッチ60は、各ノード10〜16間の通信を中継する場合には、データをスイッチ60が有する各XB70〜76のうちいずれかのXBを3ホップさせて中継する。
【0136】
また、例えば、スイッチ60は、ノード10とノード18との通信を中継する場合には、ノード18はスイッチ61のポート1に接続することから、まず、ノード18をスイッチ60のポート1に接続するノード11とみなし、ノード10から送信されたデータを、XB70を経由して、XB76からポート25〜27のうち、ノード18に固定的に割り当てた1ポートを介してスイッチ61へ送信する。そして、スイッチ61は、スイッチ60から受信したデータをさらに2ホップさせてノード18へ送信する。
【0137】
なお、ノード17〜23からノード10〜16へのデータの送信についても、同様の処理によって通信が中継される。また、スイッチ60とスイッチ61間においては、ポート7〜27のうち宛先ノードに応じて固定的に割り当てたポートを介してデータを送受信するものとするため、スイッチ60とスイッチ61との間の接続も非閉塞となる。この結果、図15に示すネットワークは、全体としてクロスバネットワークである。
【0138】
上述したようなネットワークの性質から、接続表生成装置1は、以下の処理を行うようにしてもよい。すなわち、接続表生成装置1は、利用者が「p」、「q」を入力した場合には、図14のような「p+q−1」個のXBによるクロスバネットワークを構築するための接続表を生成する。また、接続表生成装置1は、生成した接続表を組み合わせて、図15、図16に示すようなネットワークを示す接続表を生成してもよい。
【0139】
(3)出力形式について
接続表生成装置1は、図6〜図8、11に示すように、行番号を各XBに、列番号を各FOに対応させた表形式の接続表を出力した。しかし、実施例はこれに限定されるものではなく、例えば、図12のように、各FOと各XBとの接続図を出力してもよい。また、接続表生成装置1は、接続を示す情報であれば、任意の形式で出力することができる。
【0140】
(4)プログラム
ところで、実施例1に係る接続表生成装置1、および実施例2に係る接続表生成装置は、ハードウェアを利用して各種の処理を実現する場合を説明した。しかし、実施例はこれに限定されるものではなく、あらかじめ用意されたプログラムを接続表生成装置、又は、コンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図17を用いて、実施例1に示した接続表生成装置1と同様の機能を有するプログラムを実行するコンピュータの一例を説明する。図17は、制御プログラムを実行するコンピュータの一例を説明するための図である。
【0141】
図17に例示されたコンピュータ100は、RAM(Random Access Memory)120、ROM(Read Only Memory)130、HDD(Hard Disk Drive)150がバス170で接続される。また、図17に例示されたコンピュータ100は、CPU(Central Processing Unit)140がバス170で接続される。さらにバス170には、利用者が入力した「p」、「q」を取得し、生成した接続表をモニタ等に出力するためのI/O(Input Output)160が接続される。
【0142】
ROM130には、受付プログラム131、N次既約多項式生成プログラム132、乗法表・加法表生成プログラム133、接続表生成プログラム134、出力プログラム135があらかじめ保持される。CPU140が各プログラム131〜135をROM130から読み出して実行することによって、図17に示す例では、各プログラム131,132は、受付プロセス141、N次既約多項式生成プロセス142として機能するようになる。また、各プログラム133〜135は、乗法表・加法表生成プロセス143、接続表生成プロセス144、出力プロセス145として機能するようになる。なお、各プロセス141〜145は、図1に示した各部2〜6と同様の機能を発揮する。また、各プロセス141〜145は、実施例2に係る接続表生成装置と同等の機能を発揮するようにすることも可能である。
【0143】
なお、本実施例で説明した制御プログラムは、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク(FD)、CD−ROM(Compact Disc Read Only Memory)、MO(Magneto Optical Disc)、DVD(Digital Versatile Disc)などのコンピュータで読取可能な記録媒体に記録される。また、このプログラムは、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【0144】
1 接続表生成装置
2 受付部
3 N次多項式生成部
4 乗法表・加法表生成部
5 接続表生成部
6 出力部
7 キーボード
8 モニタ
10〜23、80〜86 ノード
30〜36 ファンアウトスイッチ(FO)
40〜46、50〜56、70〜76、90〜92 クロスバスイッチ(XB)
60、61、87〜89 スイッチ
【特許請求の範囲】
【請求項1】
それぞれ1つのノードが接続された複数の第1転送装置と、第1転送装置間のデータ通信を中継する複数の第2転送装置との接続を示す接続情報を生成する接続情報生成装置であって、
1つの第1転送装置に接続する第2転送装置の数に基づく値を標数とするガロア体の加法表と乗法表とを作成する表作成部と、
前記表作成部が作成した乗法表と加法表とに基づいて、各第2転送装置に接続される第1転送装置の組を定めた接続情報を生成する接続情報生成部と
を有することを特徴とする接続情報生成装置。
【請求項2】
前記接続情報生成装置において、
前記接続情報生成部は、前記表作成部が作成した乗法表が有する各セルに前記表作成部が作成した加法表を対応付け、前記対応付けた加法表のセルのうち、当該加法表と対応付けた乗法表のセルと同じ値が格納されたセルに第1転送装置と第2転送装置とが接続されることを示す情報を格納した接続表を作成し、作成した接続表に基づいて前記接続情報を生成することを特徴とする請求項1記載の接続情報生成装置。
【請求項3】
前記接続情報生成装置において、
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が1つの第2転送装置に接続する第1転送装置の数に1を加算した値であり、かつ、1つの第2転送装置に接続する第1転送装置の数が素数のべき乗である場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成された接続表に対して、前記乗法表の各列と1対1に対応付けられた複数の行を追加し、前記追加した各行に、前記作成された乗法表の各列のセルに第1転送装置と第2転送装置との接続を示す情報を格納した表を作成し、当該表に基づいて、前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項4】
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が1つの第2転送装置に接続する第1転送装置の数に1を加算した値であり、かつ、1つの第2転送装置に接続する第1転送装置の数が素数のべき乗を整数倍したものである場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成した接続表を行方向に前記整数から1を減算した回数だけ複製した第2の接続表を作成し、前記第2接続表に基づいて前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項5】
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が1つの第2転送装置に接続する第1転送装置の数と同じであり、かつ、第2転送装置に接続する第1転送装置の数が素数のべき乗に1を加算した値である場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成した接続表に対して、前記乗法表の各行と1対1で対応付けられた複数の列を追加し、前記追加した各列に、前記作成された乗法表の各行のセルに第1転送装置の組と第2転送装置との接続を示す情報を格納しさらに1つの行と1つの列とを追加して各行および各列に格納された第1転送装置の組と第2転送装置との接続を示す情報の数が前記素数のべき乗に1を加算した値となるように前記追加した1つの行と1つの列の各セルに第1転送装置と第2転送装置との接続を示す情報を格納した表を作成し、当該表に基づいて前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項6】
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が素数のべき乗に1を加算した値であり、かつ、1つの第2転送装置に接続する第1転送装置の数が素数のべき乗に1を加算した値を整数倍したものである場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成した接続表に対して、前記乗法表の各行と1対1で対応付けられた複数の列を追加し、前記追加した各列に、前記作成された乗法表の各行のセルに第1転送装置の組と第2転送装置との接続を示す情報を格納しさらに1つの行と1つの列とを追加して各行および各列に格納された第1転送装置の組と第2転送装置との接続を示す情報の数が前記素数のべき乗に1を加算した値となるように前記追加した1つの行と1つの列の各セルに第1転送装置と第2転送装置との接続を示す情報を格納した表を作成し、当該作成した表を行方向に前記整数から1を減算した回数だけ複製した第2の接続表を作成し、前記第2接続表に基づいて前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項7】
前記接続情報生成部は、各第2転送装置が有するポートの一部を各第1転送装置が有するポートとみなして前記接続表を作成し、接続情報を生成することを特徴とする請求項1〜6のいずれか1つに記載の接続情報生成装置。
【請求項8】
それぞれ1つのノードが接続された複数の第1転送装置と、前記第1転送装置間のデータを中継する複数の第2転送装置との接続を示す接続情報を生成する接続情報生成装置の制御方法であって、
前記接続情報生成装置が有する表作成部が、第1転送装置に接続する第2転送装置の数を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成装置が有する接続情報生成部が、前記表作成部が作成した乗法表と加法表とに基づいて、第2転送装置に接続される第1転送装置の組を定めた接続情報を生成することを特徴とする接続情報生成装置の制御方法。
【請求項9】
それぞれ1つのノードが接続された複数の第1転送装置と、前記第1転送装置間でデータを中継する複数の第2転送装置との接続を示す接続情報を生成する接続情報生成装置の制御プログラムであって、
コンピュータに、
第1転送装置に接続する第2転送装置の数を標数とするガロア体の加法表と乗法表とを作成させ、
前記表作成部が作成した乗法表と加法表とに基づいて、第2転送装置に接続される第1転送装置の組を定めた接続情報を生成させることを特徴とする接続情報生成装置の制御プログラム。
【請求項1】
それぞれ1つのノードが接続された複数の第1転送装置と、第1転送装置間のデータ通信を中継する複数の第2転送装置との接続を示す接続情報を生成する接続情報生成装置であって、
1つの第1転送装置に接続する第2転送装置の数に基づく値を標数とするガロア体の加法表と乗法表とを作成する表作成部と、
前記表作成部が作成した乗法表と加法表とに基づいて、各第2転送装置に接続される第1転送装置の組を定めた接続情報を生成する接続情報生成部と
を有することを特徴とする接続情報生成装置。
【請求項2】
前記接続情報生成装置において、
前記接続情報生成部は、前記表作成部が作成した乗法表が有する各セルに前記表作成部が作成した加法表を対応付け、前記対応付けた加法表のセルのうち、当該加法表と対応付けた乗法表のセルと同じ値が格納されたセルに第1転送装置と第2転送装置とが接続されることを示す情報を格納した接続表を作成し、作成した接続表に基づいて前記接続情報を生成することを特徴とする請求項1記載の接続情報生成装置。
【請求項3】
前記接続情報生成装置において、
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が1つの第2転送装置に接続する第1転送装置の数に1を加算した値であり、かつ、1つの第2転送装置に接続する第1転送装置の数が素数のべき乗である場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成された接続表に対して、前記乗法表の各列と1対1に対応付けられた複数の行を追加し、前記追加した各行に、前記作成された乗法表の各列のセルに第1転送装置と第2転送装置との接続を示す情報を格納した表を作成し、当該表に基づいて、前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項4】
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が1つの第2転送装置に接続する第1転送装置の数に1を加算した値であり、かつ、1つの第2転送装置に接続する第1転送装置の数が素数のべき乗を整数倍したものである場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成した接続表を行方向に前記整数から1を減算した回数だけ複製した第2の接続表を作成し、前記第2接続表に基づいて前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項5】
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が1つの第2転送装置に接続する第1転送装置の数と同じであり、かつ、第2転送装置に接続する第1転送装置の数が素数のべき乗に1を加算した値である場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成した接続表に対して、前記乗法表の各行と1対1で対応付けられた複数の列を追加し、前記追加した各列に、前記作成された乗法表の各行のセルに第1転送装置の組と第2転送装置との接続を示す情報を格納しさらに1つの行と1つの列とを追加して各行および各列に格納された第1転送装置の組と第2転送装置との接続を示す情報の数が前記素数のべき乗に1を加算した値となるように前記追加した1つの行と1つの列の各セルに第1転送装置と第2転送装置との接続を示す情報を格納した表を作成し、当該表に基づいて前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項6】
前記表作成部は、1つの第1転送装置に接続する第2転送装置の数が素数のべき乗に1を加算した値であり、かつ、1つの第2転送装置に接続する第1転送装置の数が素数のべき乗に1を加算した値を整数倍したものである場合には、当該素数のべき乗を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成部は、前記作成した接続表に対して、前記乗法表の各行と1対1で対応付けられた複数の列を追加し、前記追加した各列に、前記作成された乗法表の各行のセルに第1転送装置の組と第2転送装置との接続を示す情報を格納しさらに1つの行と1つの列とを追加して各行および各列に格納された第1転送装置の組と第2転送装置との接続を示す情報の数が前記素数のべき乗に1を加算した値となるように前記追加した1つの行と1つの列の各セルに第1転送装置と第2転送装置との接続を示す情報を格納した表を作成し、当該作成した表を行方向に前記整数から1を減算した回数だけ複製した第2の接続表を作成し、前記第2接続表に基づいて前記接続情報を生成することを特徴とする請求項2記載の接続情報生成装置。
【請求項7】
前記接続情報生成部は、各第2転送装置が有するポートの一部を各第1転送装置が有するポートとみなして前記接続表を作成し、接続情報を生成することを特徴とする請求項1〜6のいずれか1つに記載の接続情報生成装置。
【請求項8】
それぞれ1つのノードが接続された複数の第1転送装置と、前記第1転送装置間のデータを中継する複数の第2転送装置との接続を示す接続情報を生成する接続情報生成装置の制御方法であって、
前記接続情報生成装置が有する表作成部が、第1転送装置に接続する第2転送装置の数を標数とするガロア体の加法表と乗法表とを作成し、
前記接続情報生成装置が有する接続情報生成部が、前記表作成部が作成した乗法表と加法表とに基づいて、第2転送装置に接続される第1転送装置の組を定めた接続情報を生成することを特徴とする接続情報生成装置の制御方法。
【請求項9】
それぞれ1つのノードが接続された複数の第1転送装置と、前記第1転送装置間でデータを中継する複数の第2転送装置との接続を示す接続情報を生成する接続情報生成装置の制御プログラムであって、
コンピュータに、
第1転送装置に接続する第2転送装置の数を標数とするガロア体の加法表と乗法表とを作成させ、
前記表作成部が作成した乗法表と加法表とに基づいて、第2転送装置に接続される第1転送装置の組を定めた接続情報を生成させることを特徴とする接続情報生成装置の制御プログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【公開番号】特開2012−195789(P2012−195789A)
【公開日】平成24年10月11日(2012.10.11)
【国際特許分類】
【出願番号】特願2011−58563(P2011−58563)
【出願日】平成23年3月16日(2011.3.16)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
【公開日】平成24年10月11日(2012.10.11)
【国際特許分類】
【出願日】平成23年3月16日(2011.3.16)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
[ Back to top ]