JP3703304B2 - Data transfer method between nodes and data transfer method between computers - Google Patents

Description

となる。
一方で、一種類のデータをブロードキャストする場合は、片側転送のみで構成され、回数はlog(メモリ数)である。
一般の種類を転送する場合は少なくとも一種類のデータを放送型通信によって転送する場合よりも転送回数は多いはずである。
一種類のデータを放送型通信によって転送する場合よりも転送回数はlog(メモリ数)なので、

となる。
式（１）と式（２）を合わせることにより、最適な転送回数はlog(メモリの数)である。
【００８３】
（２）．次に、片側転送と違い、相互転送はデータを持つメモリ数を増やさない。従って、相互転送は{log(データの種類数)/log(2)}回を越えて行なおうとしても、データを全部のメモリに転送することができない。
よって、相互転送の回数は最大で{log(データの種類数)/log(2)}回となる。
「従来の技術」の項において、相互転送の説明の箇所で書いたように、相互転送の回数をできる限り多くとるようにすると効率がよい。
従って、相互転送は{log(データの種類数)/log(2)}回行うのがよい。
残りの転送は、データを持つメモリ数を増やす片側転送によって構成される。 各データについてデータの種類数を増やすメモリ数は、(メモリ数)/(データの種類数)である。
これを、「従来の技術」の項で説明したRecursive Broadcast Algorithmに倣って片側転送によって構成すると、{(log 〔 ( メモリ数 )/( データの種類数 ) 〕 }回となる。
このようにして、相互転送の{log(データの種類数)/log(2)}回と片側転送の{(log 〔 ( メモリ数 )/( データの種類数 ) 〕 }回を足し合わせて、{(log(メモリ数)/log(2)}回という、（１）に示した回数になる。
【００８４】
次に、{(log 〔 ( メモリ数 )/( データの種類数 ) 〕 }回の片側転送と、{log(データの種類数)/log(2)}回の相互転送とについて、それらの順番が問題になる。
ここで、全ての片側転送を先にしたほうが効率が良い理由を説明する。
相互転送とは違い、片側転送はデータを持つメモリ数を増やす。
また、相互転送が効率が高いので、できる限り多くのメモリが相互転送できればメモリ全体として効率の高い転送を行うことになる。
よって、できる限り先に片側転送を行っておいてデータを持つメモリ数を増やしておいてから、相互転送すれば、全体の転送効率が最も高くなる。
このような理由から、先に片側転送を全て行い、その後に相互転送を行う。
【００８５】
図１は、並列計算機において本発明のデータ転送を実行する場合に、各計算機において行われる処理内容を示すフローチャートである。
ステップ１０１において、最適データ転送を開始する。
ステップ１０２において、メモリ数Ｎ(Ｍ)（計算機数に同じ）の入力をする。 ステップ１０３において、データの種類数Ｎ(Ｄ)の入力をし、また、転送するデータがどのメモリに格納されているかを示すデータ格納場所の情報を入力する。
各計算機には、メモリ数Ｎ(Ｍ)とデータの種類数Ｎ(Ｄ)とデータ格納場所情報との組合せにより決まるデータ転送順序パターンのテーブルが各組合せ対応に用意されており、このテーブルに従ってデータが順次転送される。
まず、ステップ１０４において、｛ｌｏｇ〔 ( Ｎ ( Ｍ )) ／ ( Ｎ ( Ｄ )) 〕｝回の片側転送を行う。
次いで、ステップ１０５において、｛ｌｏｇ(Ｎ(Ｄ))／ｌｏｇ(２)｝回の相互転送を行う。
ステップ１０６において、最適データ転送を終了する。
【００８６】
さらに、もう一つの具体例として、次の場合について詳細に述べる。
すなわち、１６台のメモリを使用し、そのうち８台のメモリにそれぞれ異なる同じ大きさのデータがあるとき、すなわち、メモリM(1)〜メモリM(16)のうち、メモリM(1)にはデータD(1)が、メモリM(2)にはデータD(2)が、メモリM(3)にはデータD(3)が、メモリM(4)にはデータD(4)が、メモリM(5)にはデータD(5)が、メモリM(6)にはデータD(6)が、メモリM(7)にはデータD(7)が、メモリM(8)にはデータD(8)がある場合に、データ全てがすべてのメモリにあるように転送する。
すなわち、データD(1)、データD(2)、データD(3)、データD(4)、データD(5)、データD(6)、データD(7)、データD(8)が、メモリM(1)〜メモリM(16)にあるようにデータ転送する時、最適なデータ転送方式について具体的に説明する。
この場合のデータ転送方法は、前述したデータ転送方法の一般の場合の説明に基づき、最初に片側転送が１回、その後に相互転送が３回となる。
【００８７】
次に、図７３から図８１を用いて具体的に説明する。
図７３は転送前の状況を表す。
データD(1)がメモリM(1)にあり、データD(2)がメモリM(2)にあり、データD(3)がメモリM(3)にあり、データD(4)がメモリM(4)にあり、データD(5)がメモリM(5)にあり、データD(6)がメモリM(6)にあり、データD(7)がメモリM(7)にあり、データD(8)がメモリM(8)にある。
【００８８】
図７４は第一回目の転送を表す。
メモリM(1)のデータD(1)をメモリM(9)に片側転送（70201）する。
メモリM(2)のデータD(2)をメモリM(10)に片側転送（70202）する。
メモリM(3)のデータD(3)をメモリM(11)に片側転送（70203）する。
メモリM(4)のデータD(4)をメモリM(12)に片側転送（70204）する。
メモリM(5)のデータD(5)をメモリM(13)に片側転送（70205）する。
メモリM(6)のデータD(6)をメモリM(14)に片側転送（70206）する。
メモリM(7)のデータD(7)をメモリM(15)に片側転送（70207）する。
メモリM(8)のデータD(8)をメモリM(16)に片側転送（70208）する。
【００８９】
図７５は第一回目の転送後の状況を表す。
データD(1)がメモリM(1)とメモリM(9)にあり、
データD(2)がメモリM(2)とメモリM(10)にあり、
データD(3)がメモリM(3)とメモリM(11)にあり、
データD(4)がメモリM(4)とメモリM(12)にあり、
データD(5)がメモリM(5)とメモリM(13)にあり、
データD(6)がメモリM(6)とメモリM(14)にあり、
データD(7)がメモリM(7)とメモリM(15)にあり、
データD(8)がメモリM(8)とメモリM(16)にある。
【００９０】
図７６は第二回目の転送を表す。
メモリM(1)にあるデータD(1)をメモリM(2)に、メモリM(2)にあるデータD(2)をメモリM(1)に、それぞれ転送（70401、70402）、すなわち相互転送する。
メモリM(3)にあるデータD(3)をメモリM(4)に、メモリM(4)にあるデータD(4)をメモリM(3)に、それぞれ転送（70403、70404）、すなわち相互転送する。
メモリM(5)にあるデータD(5)をメモリM(6)に、メモリM(6)にあるデータD(6)をメモリM(5)に、それぞれ転送（70405、70406）、すなわち相互転送する。
メモリM(7)にあるデータD(7)をメモリM(8)に、メモリM(8)にあるデータD(8)をメモリM(7)に、それぞれ転送（70407、70408）、すなわち相互転送する。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（70409、70410）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（70411、70412）、すなわち相互転送する。
メモリM(13)にあるデータD(5)をメモリM(14)に、メモリM(14)にあるデータD(6)をメモリM(13)に、それぞれ転送（70413、70414）、すなわち相互転送する。
メモリM(15)にあるデータD(7)をメモリM(16)に、メモリM(16)にあるデータD(8)をメモリM(15)に、それぞれ転送（70415、70416）、すなわち相互転送する。
【００９１】
図７７は第二回目の転送後の状況を表す。
データD(1)がメモリM(1)、メモリM(2)、メモリM(9)、メモリM(10)にあり、
データD(2)がメモリM(1)、メモリM(2)、メモリM(9)、メモリM(10)にあり、
データD(3)がメモリM(3)、メモリM(4)、メモリM(11)、メモリM(12)にあり、
データD(4)がメモリM(3)、メモリM(4)、メモリM(11)、メモリM(12)にあり、
データD(5)がメモリM(5)、メモリM(6)、メモリM(13)、メモリM(14)にあり、
データD(6)がメモリM(5)、メモリM(6)、メモリM(13)、メモリM(14)にあり、
データD(7)がメモリM(7)、メモリM(8)、メモリM(15)、メモリM(16)にあり、
データD(8)がメモリM(7)、メモリM(8)、メモリM(15)、メモリM(16)にある。
【００９２】
図７８は第三回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(3)に、メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(1)に、それぞれ転送（70601、70602）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(4)に、メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(2)に、それぞれ転送（70603、70604）、すなわち相互転送する。
メモリM(5)にあるデータD(5)とデータD(6)をまとめてメモリM(7)に、メモリM(7)にあるデータD(5)とデータD(6)をまとめてメモリM(5)に、それぞれ転送（70605、70606）、すなわち相互転送する。
メモリM(6)にあるデータD(5)とデータD(6)をまとめてメモリM(8)に、メモリM(8)にあるデータD(5)とデータD(6)をまとめてメモリM(6)に、それぞれ転送（70607、70608）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（70609、70610）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（70611、70612）、すなわち相互転送する。
メモリM(13)にあるデータD(5)とデータD(6)をまとめてメモリM(15)に、メモリM(15)にあるデータD(5)とデータD(6)をまとめてメモリM(13)に、それぞれ転送（70613、70614）、すなわち相互転送する。
メモリM(14)にあるデータD(5)とデータD(6)をまとめてメモリM(16)に、メモリM(16)にあるデータD(5)とデータD(6)をまとめてメモリM(14)に、それぞれ転送（70615、70616）、すなわち相互転送する。
【００９３】
図７９は第三回目の転送後の状況を表す。
データD(1)がメモリM(1)、メモリM(2)、メモリM(3)、メモリM(4)、メモリM(9)、メモリM(10)、メモリM(11)、メモリM(12)にあり、
データD(2)がメモリM(1)、メモリM(2)、メモリM(3)、メモリM(4)、メモリM(9)、メモリM(10)、メモリM(11)、メモリM(12)にあり、
データD(3)がメモリM(1)、メモリM(2)、メモリM(3)、メモリM(4)、メモリM(9)、メモリM(10)、メモリM(11)、メモリM(12)にあり、
データD(4)がメモリM(1)、メモリM(2)、メモリM(3)、メモリM(4)、メモリM(9)、メモリM(10)、メモリM(11)、メモリM(12)にあり、
データD(5)がメモリM(5)、メモリM(6)、メモリM(7)、メモリM(8)、メモリM(13)、メモリM(14)、メモリM(15)、メモリM(16)にあり、
データD(6)がメモリM(5)、メモリM(6)、メモリM(7)、メモリM(8)、メモリM(13)、メモリM(14)、メモリM(15)、メモリM(16)にあり、
データD(7)がメモリM(5)、メモリM(6)、メモリM(7)、メモリM(8)、メモリM(13)、メモリM(14)、メモリM(15)、メモリM(16)にあり、
データD(8)がメモリM(5)、メモリM(6)、メモリM(7)、メモリM(8)、メモリM(13)、メモリM(14)、メモリM(15)、メモリM(16)にある。
【００９４】
図８０は第四回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(5)に、メモリM(5)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(1)に、それぞれ転送（70801、70802）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(6)に、メモリM(6)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(2)に、それぞれ転送（70803、70804）、すなわち相互転送する。
メモリM(3)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(7)に、メモリM(7)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(3)に、それぞれ転送（70805、70806）、すなわち相互転送する。
メモリM(4)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(8)に、メモリM(8)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(4)に、それぞれ転送（70807、70808）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(13)に、メモリM(13)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(9)に、それぞれ転送（70809、70810）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(14)に、メモリM(14)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(10)に、それぞれ転送（70811、70812）、すなわち相互転送する。
メモリM(11)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(15)に、メモリM(15)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(11)に、それぞれ転送（70813、70814）、すなわち相互転送する。
メモリM(12)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(16)に、メモリM(16)にあるデータD(5)とデータD(6)とデータD(7)とデータD(8)をまとめてメモリM(12)に、それぞれ転送（70815、70816）、すなわち相互転送する。
図８１は転送終了後の状態を表す。
【００９５】
【発明の効果】
本発明によれば、メモリとメモリの組みが複数あるような計算機において一つあるいは複数のデータがそれぞれ異なるメモリにある場合に、全部のデータが全部のメモリ上にあるようにデータ転送を行いたい時に、片側通信と相互通信の最適な組み合わせることにより、最短の実行時間によって、目的とするデータ転送を達成することができる。
【図面の簡単な説明】
【図１】データ転送を実行する場合に、各計算機において行われる処理のフローチャートを示す図である。
【図２】片側転送の処理内容を示す図である。
【図３】相互転送の処理内容を示す図である。
【図４】放送型転送の初期状態を示す図である。
【図５】放送型転送の第一段の転送を示す図である。
【図６】放送型転送の第一段の転送後の状態を示す図である。
【図７】放送型転送の第二段の転送を示す図である。
【図８】放送型転送の第二段の転送後の状態を示す図である。
【図９】放送型転送の初期状態を表に示す図である。
【図１０】放送型転送の第一段の転送を表に示す図である。
【図１１】放送型転送の第一段の転送後の状態を表に示す図である。
【図１２】放送型転送の第二段の転送を表に示す図である。
【図１３】放送型転送の第二段の転送後の状態を表に示す図である。
【図１４】ネットワーク上の転送経路により接続された２つのノードを示す図である。
【図１５】図１４で示したデータ転送の形態を製品として実現している一例である並列計算機の転送ハードウェアの特徴を示す図である。
【図１６】商品データの例を示す図である。
【図１７】売上データの例を示す図である。
【図１８】並列データベースの構成例を示す
【図１９】１６メモリ、４種類データの最適転送の初期状態を示す図である。
【図２０】１６メモリ、４種類データの最適転送の第一回目の転送を示す図である。
【図２１】１６メモリ、４種類データの最適転送の第一回目の転送後を示す図である。
【図２２】１６メモリ、４種類データの最適転送の第二回目の転送を示す図である。
【図２３】１６メモリ、４種類データの最適転送の第二回目の転送後を示す図である。
【図２４】１６メモリ、４種類データの最適転送の第三回目の転送を示す図である。
【図２５】１６メモリ、４種類データの最適転送の第三回目の転送後を示す図である。
【図２６】１６メモリ、４種類データの最適転送の第四回目の転送を示す図である。
【図２７】１６メモリ、４種類データの最適転送の第四回目の転送後を示す図である。
【図２８】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図２９】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図３０】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図３１】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図３２】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図３３】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図３４】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図３５】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図３６】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図３７】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図３８】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図３９】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図４０】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図４１】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図４２】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図４３】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図４４】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図４５】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図４６】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図４７】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図４８】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図４９】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図５０】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図５１】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図５２】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図５３】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図５４】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図５５】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図５６】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図５７】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図５８】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図５９】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図６０】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図６１】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図６２】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図６３】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図６４】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図６５】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図６６】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図６７】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図６８】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図６９】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図７０】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図７１】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図７２】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図７３】１６メモリ、８種類データの最適転送の初期状態を示す図である。
【図７４】１６メモリ、８種類データの最適転送の第一回目の転送を示す図である。
【図７５】１６メモリ、８種類データの最適転送の第一回目の転送後を示す図である。
【図７６】１６メモリ、８種類データの最適転送の第二回目の転送を示す図である。
【図７７】１６メモリ、８種類データの最適転送の第二回目の転送後を示す図である。
【図７８】１６メモリ、８種類データの最適転送の第三回目の転送を示す図である。
【図７９】１６メモリ、８種類データの最適転送の第三回目の転送後を示す図である。
【図８０】１６メモリ、８種類データの最適転送の第四回目の転送を示す図である。
【図８１】１６メモリ、８種類データの最適転送の第四回目の転送後を示す図である。
【符号の説明】
１４０１、１４０８ 出力口
１４０２、１４０７ 入力口
１４０３、１４０９ データ
１４０４、１４１０ ノード
１４０５、１４０６ 転送経路
１４１１、１４１２ プロセッサ
１５０１〜１５０４、１８０１〜１８０４ クロスバー
１５０５、１５０７、１５０９、１５１１、１８０５、１８０７、１８０９、１８１１ スイッチ
１５０６、１５０８、１５１０、１５１２、１８０６、１８０８、１８１０、１８１２ ノード[0001]
BACKGROUND OF THE INVENTION
The present invention relates to a data transfer method in a computer system having a large number of memories, and relates to an effective use method of a network.
[0002]
[Prior art]
As a conventional technique, a conventional communication system technique and a conventional network hardware technique will be described.
References related to communication system technology and network hardware include "Parallel Computer Architecture" written by Shushi Okugawa (Corona), and "Computer Architecture and Configuration Method" written by Kisaburo Nakazawa (Asakura Shoten).
Conventional communication system technologies include one-sided communication (FIG. 2), mutual communication (FIG. 3), and broadcast type communication (FIGS. 4 to 13). One-side communication is also called one-side transfer, mutual communication is called mutual transfer, and broadcast-type communication is called broadcast-type transfer.
[0003]
One-side communication is a communication method in which data in one memory is transferred to the other memory.
As shown in FIG. 2, this is a communication method in which data (203) is transferred (204) from one memory (201) to another memory (201).
Also called PING-PONG communication, POINT-TO-PINT communication, PIER-TO-PIER communication.
[0004]
Mutual communication is a communication method in which data in two memories are simultaneously transferred to each other.
As shown in FIG. 3, in the communication system, data (303) and data (304) respectively sent to one memory (301) and another memory (302) are sent to each other and simultaneously (305) (306). It is also called EXCHANGE communication.
Mutual communication can also be configured by performing one-sided communication sequentially from each direction. That is, first, transfer (305) is performed, and then transfer (306) is performed.
If there is only one transfer path between the two memories, the only way is to perform one-sided communication sequentially.
[0005]
However, typical parallel computers such as SR2201 (Hitachi) often have two or more paths. This is because it does not cost much to implement two or more hardware.
Therefore, using mutual communication that transfers data in both directions at once, more data can be transferred per unit time than when one-side communication is performed sequentially.
Accordingly, when data is transferred using mutual communication as much as possible, data can be transferred more efficiently.
[0006]
Broadcast communication is a communication method in which data in one memory is stored in all other memories. It is also called BROADCAST (broadcast) communication.
When broadcasting one type of data, it is composed of only one-side communication, and the number of times is log (the number of memories).
This is called the Recursive Broadcast Algorithm (reference: R. Ponnusamy: Scheduling Regular and Irregular Communications Patterns on the CM-5: Supercomputing '92).
[0007]
This method will be specifically described with reference to FIGS.
First, assume that FIG. 4 shows the situation before transfer.
Assume that there are a total of four memories (401) (402) (403) (404). It is assumed that there is data (405) in the memory (401). This data is transferred so as to be in the remaining memories (402) (403) (404).
[0008]
FIG. 5 shows the first transfer.
Of the four memories (501) (502) (503) (504), the data (505) is transferred (506) from the memory (501) to the memory (502).
FIG. 6 shows after the first transfer.
Of the four memories (601), (602), (603), and (604), the data (605) is in the memory (601) and the data (606) is in the memory (602).
[0009]
FIG. 7 shows the second transfer.
Data (705) is transferred (706) from the memory (701) to the memory (703) in the four memories (701) (702) (703) (704), and at the same time, the data (707) is transferred from the memory (702) to the memory (703). Transfer (708) to (704).
FIG. 8 shows a situation where the transfer is completed.
The four memories (801) (802) (803) (804) have data (805) (806) (807) (808), respectively.
The above is a specific example of a broadcast composed of one-sided communication called Recursive Broadcast Algorithm.
[0010]
Here, a description will be given of the above transfer method in the form of a table for the case where the number of types of data increases in the later description.
9 to 13 correspond to this.
Assume that the data described with reference to FIGS. 4 to 8 is data D (2).
FIG. 9 shows a situation in which data D (2) is in memory M (1), is not on any memory other than memory M (1), and no other data is on any memory.
FIG. 9 corresponds to FIG. Assume that the data (405) in FIG. 4 corresponds to the data D (2) in FIG.
The memory (401) in FIG. 4 is the memory M (1) in FIG. 9, the memory (402) in FIG. 4 is in the memory M (2) in FIG. 9, and the memory (403) in FIG. 3), the memory (404) in FIG. 4 corresponds to the memory M (4) in FIG.
[0011]
FIG. 10 corresponds to FIG.
The memory (501) in FIG. 5 is the memory M (1) in FIG. 10, the memory (502) in FIG. 5 is in the memory M (2) in FIG. 10, and the memory (503) in FIG. 3), the memory (504) in FIG. 5 corresponds to the memory M (4) in FIG.
Assume that data (505) in FIG. 5 corresponds to data D (2) in FIG. The transfer (506) in FIG. 5 corresponds to the transfer (1001) in FIG.
[0012]
FIG. 11 corresponds to FIG.
[0013]
The memory (601) in FIG. 6 is the memory M (1) in FIG. 11, the memory (602) in FIG. 6 is in the memory M (2) in FIG. 11, and the memory (603) in FIG. 3), the memory (604) in FIG. 6 corresponds to the memory M (4) in FIG.
Assume that the data (605) in FIG. 6 corresponds to the data D (2) in the memory M (1) in FIG.
Assume that the data (606) in FIG. 6 corresponds to the data D (2) in the memory M (2) in FIG.
[0014]
FIG. 12 corresponds to FIG.
7 is the memory M (1) in FIG. 12, the memory (702) in FIG. 7 is the memory M (2) in FIG. 12, and the memory (703) in FIG. 3), the memory (704) in FIG. 7 corresponds to the memory M (4) in FIG.
Assume that data (705) in FIG. 7 corresponds to data D (2) in the memory M (1) in FIG.
Assume that data (707) in FIG. 7 corresponds to data D (2) in the memory M (2) in FIG.
The transfer (706) in FIG. 7 corresponds to the transfer (1201) in FIG. The transfer (708) in FIG. 7 corresponds to the transfer (1202) in FIG.
[0015]
FIG. 13 corresponds to FIG.
[0016]
The memory (801) in FIG. 8 is the memory M (1) in FIG. 13, the memory (802) in FIG. 8 is in the memory M (2) in FIG. 13, and the memory (803) in FIG. 3), the memory (804) in FIG. 8 corresponds to the memory M (4) in FIG.
Assume that data (805) in FIG. 8 corresponds to data D (2) in the memory M (1) in FIG.
Assume that data (806) in FIG. 8 corresponds to data D (2) in the memory M (2) in FIG.
Assume that the data (807) in FIG. 8 corresponds to the data D (2) in the memory M (3) in FIG.
Assume that the data (808) in FIG. 8 corresponds to the data D (2) in the memory M (4) in FIG.
This completes the description of the transfer method in the form of a table.
This concludes the description of the conventional communication system technology.
[0017]
Next, conventional network hardware technology will be described.
Typical examples include hypercrossbar networks and torus networks.
The hyper crossbar network is adopted in the parallel computer SR2201 (Hitachi), and the torus type network is adopted in other parallel computers.
In particular, in the parallel computer SR2201, which employs a hypercrossbar network, the transfer speed between arbitrary memories is almost the same, and in the case of isotropic transfer such as transfer sent next to a virtual one-dimensional address, Since there is no collision, the transmission speed does not deteriorate and communication can always be performed with a constant performance (reference: "Architecture and Performance of the Hitachi SR2201 Massively Parallel Processor System" in Proceedings of the 11th International Parallel Processing Symposium, Geneva, Switzerland, April 1-5, 1997).
Therefore, it is possible to construct an optimum communication based on a model in which any isotropic mutual transfer has a constant transfer speed if the memories do not overlap.
In addition, if the transfer speed between arbitrary memories is almost the same, and any isotropic mutual transfer does not overlap the memory, NIA (Network Interface Adapter) And the technology called SC (Storage Controller) plays an important role.
[0018]
[Problems to be solved by the invention]
A computer system that satisfies the condition that the transfer performance between two arbitrary memories connected to a network is the same, and the transfer amount per unit time in mutual communication is larger than the transfer amount per unit time in one-side communication Considering the construction of a method for performing the following data transfer in the shortest time.
The data transfer is as follows: (1) The number N (M) of all the memories used is a power of 2. (2) The data type N (D) is about the number N (M) of all the memories used. (3) N (D) types of data are all the same amount of data, and (4) N (D) types of data are in different memories. , The data is transferred so that all N (D) types of data are in all N (M) memories.
When a plurality of data are in different memories, a technique for transmitting data to all memories at an optimum number of times so that communication paths do not compete by skillfully transferring data at the same time has not been clear.
[0019]
SLJohnsonn et al's "Optimum Broadcasting and Personalized Communication in Hypercubes" (IEEE Transactions on Computers Vol.38, No.9, Sept. 1989) discusses an optimal transfer method based on the Hamming distance. The network model is old and cannot be applied to the above computer system.
Further, it cannot be applied to the above general data transfer.
Fujitsu's Horie et al., “Optimum All-to-All Communication in Torus Networks” (Parallel Processing Symposium JSPP92) (Patent: JP 5-151181) assumes a torus network model and cannot be applied to the above computer systems. .
Further, it cannot be applied to the above general data transfer.
[0020]
In the method of broadcasting one data and then broadcasting another data, as the number of types of data increases, it takes a longer transfer time, which has a great adverse effect on the overall performance.
When performing large-scale calculations with an increased number of memories, it is well known that long transfer times have a significant effect on overall performance, and there is a strong need for efficient data transfer. .
However, it has not been clarified what kind of transfer method is effective and how the optimum method is configured.
An object of the present invention is to provide an optimum data transfer method for executing data transfer in a minimum time so that all data to be transferred are on all memories.
[0021]
[Means for Solving the Problems]
  In order to achieve the above object, the present invention provides:
  In a network having M nodes (where M is a power of 2) that can perform one-sided transfer and mutual transfer of data between nodes, and each has a memory, D (where 1 <D <M, (D is a divisor of M) A node-to-node data transfer method for transferring each data in the memory of nodes to all other nodes,
  The transfer of each data between the nodes is as follows:(Log (M / D))After performing one-sided transfer, (logD / log2) times of mutual transfer is performed.
[0022]
  Further, in a parallel computer in which M computers (where M is a power of 2) that can perform one-sided transfer and mutual transfer of data between computers and each have a memory are connected by a network, D (where 1 < D <M, where D is a divisor of M) is an inter-computer data transfer method for transferring each data in the memory of the computer to all other computers, and the transfer of each data between the computers is as follows:(Log (M / D))After performing one-sided transfer, (logD / log2) times of mutual transfer is performed.
[0023]
DETAILED DESCRIPTION OF THE INVENTION
The present invention relates to data transfer between a plurality of nodes connected by a network, and first, structural features that each node should have will be described.
FIG. 14 shows two nodes connected by a transfer path on the network.
Each of the nodes 1404 and 1410 includes processors 1411 and 1412 and data 1403 and 1409 stored in the memory, respectively.
Each node has double transfer paths so that bidirectional data transfer can be performed simultaneously so that bidirectional data transfer and one-sided data transfer can be performed as transfer between nodes. Routes 1405 and 1406 are included.
Further, each node has output ports 1401 and 1408 and input ports 1402 and 1407.
When data transfer between two nodes is one-side data transfer (hereinafter referred to as “one-side transfer”), data 1403 of the node 1404 receives a command from the processor 1411 and transfers from the output port 1401 to the transfer path 1405 and the input port 1407. And the data 1409 of the node 1410 is transferred from the output port 1408 to the transfer path 1406 and the input port 1402 to the node 1404 using only one transfer path in response to an instruction from the processor 1412.
In the case of bidirectional data transfer (hereinafter referred to as mutual transfer), the data 1403 of the node 1404 receives an instruction from the processor 1411, passes from the output port 1401 to the node 1410 through the transfer path 1405 and the input port 1407, and simultaneously to the node 1410. Data 1409 is transferred from the output port 1408 through the transfer path 1406 and the input port 1402 to the node 1404 using both transfer paths in response to an instruction from the processor 1412.
[0024]
Next, a parallel computer which is an example of a system to which the present invention is applied will be described.
FIG. 15 is a diagram showing the characteristics of transfer hardware of a parallel computer, which is an example of realizing the data transfer mode shown in FIG. 14 as a product.
1501 to 1504 are crossbars, 1505, 1507, 1509, and 1511 switches, and 1506, 1508, 1510, and 1512 are nodes (computers). Each node has an output port and an input port shown in FIG. 14 and is a node capable of bidirectional data transfer.
The mutual transfer between the node 1506 and the node 1510 includes a crossbar 1501 which is a transfer path capable of mutual transfer, a switch 1505 and a switch 1509 capable of simultaneously inputting and outputting to the crossbar, and these switches are respectively connected to the node 1505. This is realized by having a configuration in which 1509 can simultaneously input and output.
In addition, mutual transfer between the node 1508 and the node 1512 includes a crossbar 1502 which is a transfer path capable of mutual transfer, a switch 1507 and a switch 1511 capable of simultaneously inputting and outputting to the crossbar, and each of these switches is a node. This is achieved by having a configuration that allows input and output to 1508 and 1512 simultaneously.
The mutual transfer between the node 1506 and the node 1508 is similarly performed by the crossbar 1503, the switch 1505, and the switch 1507, and the mutual transfer between the node 1510 and the node 1512 is similarly performed by the crossbar 1504, the switch 1509, and the switch 1511.
[0025]
Next, a parallel database as another example of a system to which the present invention is applied will be described.
FIG. 18 shows a configuration example of a parallel database.
Similar to FIG. 15, it has a network configuration including switches 1805, 1807, 1809, 1811 and crossbars 1801, 1802, 1803, 1804.
For example, if there is product data on discs 1806 and 1808, and there is sales data on all discs 1806, 1808, 1810, 1812, the product data is transferred to all discs 1806, 1808, 1810, 1812 There is a case of searching for each data. The present invention is applied as a method for transferring product data at this time.
FIG. 16 is an example of the product data, and data relating to the product itself such as product ID and product name is compiled in a table.
FIG. 17 is an example of the sales data, and data relating to sales such as a slip ID, a product ID, and the date and time when the product was sold are collected as a table.
There is a system for searching what products are sold when these two pieces of data are stored. When there is a large amount of data, the data is stored in a plurality of discs.
In such a case, a parallel database is applied.
[0026]
Next, a specific example in which the present invention is applied to data transfer in a parallel computer will be described. Note that the present invention is not limited to parallel computers.
That is, a case of a parallel computer composed of 16 computers each having a memory will be described. In the following description, the description will be made mainly on the memory.
As shown in FIG. 19, when there are four different memories of the same size among the 16 memories, that is, among the memories M (1) to M (16), the memory M (9 ) Is data D (1), memory M (10) is data D (2), memory M (11) is data D (3), memory M (12) is data D (4) If there is, transfer all data so that it is in all memory.
That is, when data D (1), data D (2), data D (3), and data D (4) are transferred so that they are in memory M (1) to memory M (16), the optimum data The transfer method will be specifically described.
[0027]
First, a case where the data transfer method of the present invention is applied, that is, a case where one-side transfer is performed twice first and then mutual transfer (bidirectional data transfer) is performed twice will be described.
This will be described with reference to FIGS.
FIG. 19 shows the situation before transfer.
Data D (1) is stored in memory M (9), data D (2) is stored in memory M (10), data D (3) is stored in memory M (11), and data D (4) is stored in memory M (12). It is in.
[0028]
FIG. 20 shows the first transfer.
Data D (1) in memory M (9) is transferred to memory M (1) on one side (10201)
Data D (2) in memory M (10) is transferred to memory M (2) on one side (10202)
Data D (3) in memory M (11) is transferred to memory M (3) on one side (10203)
Data D (4) in the memory M (12) is transferred to one side (10204) to the memory M (4).
[0029]
FIG. 21 shows the situation after the first transfer.
Data D (1) is in memory M (9) and memory M (1)
Data D (2) is in memory M (10) and memory M (2)
Data D (3) is in memory M (11) and memory M (3)
Data D (4) is in memory M (12) and memory M (4).
[0030]
FIG. 22 shows the second transfer.
Data D (1) in memory M (1) is transferred to memory M (5) on one side (10401)
Data D (2) in memory M (2) is transferred to memory M (6) on one side (10402)
Data D (3) in memory M (3) is transferred to memory M (7) on one side (10403)
Data D (4) in memory M (4) is transferred to memory M (8) on one side (10404)
Data D (1) in memory M (9) is transferred to memory M (13) on one side (10405)
Data D (2) in memory M (10) is transferred to memory M (14) on one side (10406)
Data D (3) in memory M (11) is transferred to memory M (15) on one side (10407)
Data D (4) in the memory M (12) is transferred to one side (10408) to the memory M (16).
[0031]
FIG. 23 shows the situation after the second transfer.
Data D (1) is in memory M (1), memory M (5), memory M (9) and memory M (13),
Data D (2) is in memory M (2), memory M (6), memory M (10) and memory M (14),
Data D (3) is in memory M (3), memory M (7), memory M (11) and memory M (15),
Data D (4) is stored in the memory M (4), the memory M (8), the memory M (12), and the memory M (16).
[0032]
FIG. 24 shows the third transfer.
Data D (1) in the memory M (1) is transferred to the memory M (2), and data D (2) in the memory M (2) is transferred to the memory M (1) (10601, 10602), that is, mutual Forward.
Data D (3) in the memory M (3) is transferred to the memory M (4), and data D (4) in the memory M (4) is transferred to the memory M (3) (10603, 10604), that is, mutual Forward.
Data D (1) in the memory M (5) is transferred to the memory M (6), and data D (2) in the memory M (6) is transferred to the memory M (5) (10605, 10606), that is, mutual Forward.
The data D (3) in the memory M (7) is transferred to the memory M (8) and the data D (4) in the memory M (8) is transferred to the memory M (7) (10607, 10608), that is, mutual Forward.
Data D (1) in the memory M (9) is transferred to the memory M (10), and data D (2) in the memory M (10) is transferred to the memory M (9) (10609, 10610), that is, mutual Forward.
Data D (3) in the memory M (11) is transferred to the memory M (12), and data D (4) in the memory M (12) is transferred to the memory M (11) (10611, 10612), that is, mutual Forward.
Data D (1) in the memory M (13) is transferred to the memory M (14), and data D (2) in the memory M (14) is transferred to the memory M (13) (10613, 10614), that is, mutual Forward.
Data D (3) in the memory M (15) is transferred to the memory M (16), and data D (4) in the memory M (16) is transferred to the memory M (15) (10615, 10616), that is, mutual Forward.
[0033]
FIG. 25 shows the situation after the third transfer.
[0034]
Data D (1) is memory M (1), memory M (2), memory M (5), memory M (6), memory M (9), memory M (10), memory M (13), memory M (14)
Data D (2) is memory M (1), memory M (2), memory M (5), memory M (6), memory M (9), memory M (10), memory M (13), memory M (14)
Data D (3) is memory M (3), memory M (4), memory M (7), memory M (8), memory M (11), memory M (12), memory M (15), memory M (16)
Data D (4) is memory M (3), memory M (4), memory M (7), memory M (8), memory M (11), memory M (12), memory M (15), memory M It is in (16).
[0035]
FIG. 26 shows the fourth transfer.
[0036]
Data D (1) and data D (2) in memory M (1) are combined into memory M (3), and data D (3) and data D (4) in memory M (3) are combined into memory Transfer to M (1) (10801, 10802), that is, transfer to each other.
Data D (1) and data D (2) in memory M (2) are combined into memory M (4), and data D (3) and data D (4) in memory M (4) are combined into memory Transfer to M (2) (10803, 10804), that is, transfer to each other.
Data D (1) and data D (2) in memory M (5) are combined into memory M (7), and data D (3) and data D (4) in memory M (7) are combined into memory Transfer to M (5) (10805, 10806), that is, transfer to each other.
Data D (1) and data D (2) in memory M (6) are combined into memory M (8), and data D (3) and data D (4) in memory M (8) are combined into memory Transfer to M (6) (10807, 10808), that is, transfer to each other.
Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer to M (9) (10809, 10810), that is, transfer to each other.
Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer (10811, 10812) to M (10), that is, transfer to each other.
Data D (1) and data D (2) in memory M (13) are combined into memory M (15), and data D (3) and data D (4) in memory M (15) are combined into memory Transfer to M (13) (10813, 10814), that is, transfer to each other.
Data D (1) and data D (2) in memory M (14) are combined into memory M (16), and data D (3) and data D (4) in memory M (16) are combined into memory Transfer to M (14) (10815, 10816), that is, transfer to each other.
FIG. 27 shows a state in which all transfers have been completed.
[0037]
Although the case where the data transfer method of the present invention is applied has been described above, the communication between the 16 memories and the four types of data includes two one-side transfers and two mutual transfers.
There are a total of six combinations of the one-side transfer and the mutual transfer because they are permutation combinations that combine two out of four.
In particular,
(1 set) One side-One side-Mutual-Mutual
(Set of 2) One side-Mutual-One side-Mutual
(Set of 3) one side-mutual-mutual-one side
(Set of 4) Mutual-Mutual-One side-One side
(5 pairs) Mutual-one side-mutual-one side
(6 pairs) Mutual-one side-one side-mutual
These are six.
Among these, (one set) is a case where the present invention is applied.
Hereinafter, (group 2) to (group 6) to which the present invention is not applied will be described with reference to FIGS.
[0038]
First, (two sets) will be described.
FIG. 28 shows the situation before transfer.
FIG. 29 shows the first transfer.
Data in memory M (9) is transferred to M (1) on one side (20201).
Data in the memory M (10) is transferred to one side (20202) to M (2).
Data in the memory M (11) is transferred to the M (3) one side (20203).
Data in the memory M (12) is transferred to the M (4) on one side (20204).
[0039]
FIG. 30 shows the situation after the first transfer.
Data D (1) is in memory M (1) and memory M (9)
Data D (2) is in memory M (2) and memory M (10)
Data D (3) is in memory M (3) and memory M (11)
Data D (4) is in memory M (4) and memory M (12).
[0040]
FIG. 31 shows the second transfer.
Data D (1) in the memory M (1) is transferred to the memory M (2), and data D (2) in the memory M (2) is transferred to the memory M (1) (20401, 20402), that is, mutual Forward.
Data D (3) in the memory M (3) is transferred to the memory M (4), and data D (4) in the memory M (4) is transferred to the memory M (3) (20403, 20404), that is, mutual Forward.
Data D (1) in the memory M (9) is transferred to the memory M (10), and data D (2) in the memory M (10) is transferred to the memory M (9) (20405, 20406), that is, mutual Forward.
Data D (3) in the memory M (11) is transferred to the memory M (12), and data D (4) in the memory M (12) is transferred to the memory M (11) (20407, 20408), that is, mutual Forward.
[0041]
FIG. 32 shows the situation after the second transfer.
Data D (1) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (2) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (3) is in memory M (3), memory M (4), memory M (11) and memory M (12),
The data D (4) is stored in the memory M (3), the memory M (4), the memory M (11), and the memory M (12).
[0042]
FIG. 33 shows the third transfer.
Data D (1) and data D (2) in the memory M (1) are collectively transferred to the memory M (5) on one side (20601).
Data D (1) and data D (2) in the memory M (2) are collectively transferred to the memory M (6) on one side (20602).
Data D (3) and data D (4) in the memory M (3) are collectively transferred to the memory M (7) on one side (20603).
Data D (3) and data D (4) in the memory M (4) are collectively transferred to the memory M (8) on one side (20604).
Data D (1) and data D (2) in the memory M (9) are collectively transferred to the memory M (13) on one side (20605).
Data D (1) and data D (2) in the memory M (10) are collectively transferred to the memory M (14) on one side (20606).
Data D (3) and data D (4) in the memory M (11) are collectively transferred to the memory M (15) on one side (20607).
Data D (3) and data D (4) in the memory M (12) are collectively transferred to the memory M (16) on one side (20608).
[0043]
FIG. 34 shows the situation after the third transfer.
Data D (1) is memory M (1), memory M (2), memory M (5), memory M (6), memory M (9), memory M (10), memory M (13), and memory M. (14)
Data D (2) is stored in memory M (1), memory M (2), memory M (5), memory M (6), memory M (9), memory M (10), memory M (13), and memory M. (14)
Data D (3) is memory M (3), memory M (4), memory M (7), memory M (8), memory M (11), memory M (12), memory M (15), and memory M. (16)
Data D (4) is stored in memory M (3), memory M (4), memory M (7), memory M (8), memory M (11), memory M (12), memory M (15), and memory M. It is in (16).
[0044]
FIG. 35 shows the fourth transfer.
Data D (1) and data D (2) in memory M (1) are combined into memory M (3), and data D (3) and data D (4) in memory M (3) are combined into memory Transfer to M (1) (20801, 20802), that is, transfer to each other.
Data D (1) and data D (2) in memory M (2) are combined into memory M (4), and data D (3) and data D (4) in memory M (4) are combined into memory Transfer to M (2) (20803, 20804), that is, transfer to each other.
Data D (1) and data D (2) in memory M (5) are combined into memory M (7), and data D (3) and data D (4) in memory M (7) are combined into memory Transfer to M (5) (20805, 20806), that is, transfer to each other.
Data D (1) and data D (2) in memory M (6) are combined into memory M (8), and data D (3) and data D (4) in memory M (8) are combined into memory Transfer to M (6) (20807, 20808), that is, transfer to each other.
Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer (20809, 20810) to M (9), that is, transfer to each other.
Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer to M (10) (20811, 20812), that is, transfer to each other.
Data D (1) and data D (2) in memory M (13) are combined into memory M (15), and data D (3) and data D (4) in memory M (15) are combined into memory Transfer to M (13) (20813, 20814), that is, transfer to each other.
Data D (1) and data D (2) in memory M (14) are combined into memory M (16), and data D (3) and data D (4) in memory M (16) are combined into memory Transfer to M (14) (20815, 20816), that is, transfer to each other.
FIG. 36 shows a situation where all transfers have been completed.
[0045]
Next, (set of 3) will be described.
FIG. 37 shows the situation before transfer.
FIG. 38 shows the first transfer.
The data in the memory M (9) is transferred to one side (30201) to M (1).
Data in the memory M (10) is transferred to one side (30202) to M (2).
Data in the memory M (11) is transferred to one side (30203) to M (3).
The data in the memory M (12) is transferred to one side (30204) to M (4).
[0046]
FIG. 39 shows the situation after the first transfer.
Data D (1) is in memory M (1) and memory M (9)
Data D (2) is in memory M (2) and memory M (10)
Data D (3) is in memory M (3) and memory M (11)
Data D (4) is in memory M (4) and memory M (12).
[0047]
FIG. 40 shows the second transfer.
Data D (1) in the memory M (1) is transferred to the memory M (2), and data D (2) in the memory M (2) is transferred to the memory M (1) (30401, 30402), that is, mutual Forward.
Data D (3) in the memory M (3) is transferred to the memory M (4), and data D (4) in the memory M (4) is transferred to the memory M (3) (30403, 30404), that is, mutual Forward.
Data D (1) in the memory M (9) is transferred to the memory M (10), and data D (2) in the memory M (10) is transferred to the memory M (9) (30405, 30406), that is, mutual Forward.
Data D (3) in the memory M (11) is transferred to the memory M (12), and data D (4) in the memory M (12) is transferred to the memory M (11) (30407, 30408), that is, mutual Forward.
[0048]
FIG. 41 shows the situation after the second transfer.
Data D (1) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (2) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (3) is in memory M (3), memory M (4), memory M (11) and memory M (12),
The data D (4) is stored in the memory M (3), the memory M (4), the memory M (11), and the memory M (12).
[0049]
FIG. 42 shows the third transfer.
Data D (1) and data D (2) in memory M (1) are combined into memory M (3), and data D (3) and data D (4) in memory M (3) are combined into memory Transfer to M (1) (30601, 30602), that is, transfer to each other.
Data D (1) and data D (2) in memory M (2) are combined into memory M (4), and data D (3) and data D (4) in memory M (4) are combined into memory Transfer to M (2) (30603, 30604), that is, transfer to each other.
Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer to M (9) (30605, 30606), that is, transfer to each other.
Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer to M (10) (30607, 30608), that is, transfer to each other.
[0050]
FIG. 43 shows the situation after the third transfer.
Data D (1) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. It is in (12).
Data D (2) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. It is in (12).
Data D (3) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. It is in (12).
Data D (4) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. It is in (12).
[0051]
FIG. 44 shows the fourth transfer.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (1) are collectively transferred to the memory M (5) on one side.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (2) are collectively transferred to the memory M (6).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (3) are collectively transferred to the memory M (7) on one side.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (4) are collectively transferred to the memory M (8) on one side.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (9) are collectively transferred to the memory M (13).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (10) are collectively transferred to the memory M (14).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (11) are collectively transferred to the memory M (15).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (12) are collectively transferred to the memory M (16) on one side.
FIG. 45 shows a situation where all transfers have been completed.
[0052]
Next, (set of 4) will be described.
FIG. 46 shows the situation before transfer.
FIG. 47 shows the first transfer.
Data D (1) in the memory M (9) is transferred to the memory M (10), and data D (2) in the memory M (10) is transferred to the memory M (9) (40201, 40202), that is, mutual Forward.
Data D (3) in the memory M (11) is transferred to the memory M (12), and data D (4) in the memory M (12) is transferred to the memory M (11) (40203, 40204), that is, mutual Forward.
[0053]
FIG. 48 shows the situation after the first transfer.
Data D (1) is in memory M (9) and memory M (10)
Data D (2) is in memory M (9) and memory M (10)
Data D (3) is in memory M (11) and memory M (12)
Data D (4) is stored in the memory M (11) and the memory M (12).
[0054]
FIG. 49 shows the second transfer.
Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer to M (9) (40401, 40403), that is, transfer to each other.
Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer to M (10) (40402, 40404), that is, transfer to each other.
[0055]
FIG. 50 shows the situation after the second transfer.
Data D (1) is in memory M (9), memory M (10), memory M (11) and memory M (12),
Data D (2) is in memory M (9), memory M (10), memory M (11) and memory M (12),
Data D (3) is in memory M (9), memory M (10), memory M (11) and memory M (12),
Data D (4) is stored in the memory M (9), the memory M (10), the memory M (11), and the memory M (12).
[0056]
FIG. 51 shows the third transfer.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (9) are collectively transferred to the memory M (1) (40601).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (10) are collectively transferred to the memory M (2) (40602).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (11) are collectively transferred to the memory M (3) (40603).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (12) are collectively transferred to the memory M (4) (40604).
[0057]
FIG. 52 shows the situation after the third transfer.
Data D (1) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. (12)
Data D (2) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. (12)
Data D (3) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. (12)
Data D (4) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. It is in (12).
[0058]
FIG. 53 shows the fourth transfer.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (1) are collectively transferred to the memory M (5) on one side (40801).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (2) are collectively transferred to the memory M (6) (40802).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (3) are collectively transferred to the memory M (7) (40803).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (4) are collectively transferred to the memory M (8) (40804).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (9) are collectively transferred to the memory M (13) (40805).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (10) are collectively transferred to the memory M (14) on one side (40806).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (11) are collectively transferred to the memory M (15) (40807).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (12) are collectively transferred to the memory M (16) (40808).
FIG. 54 shows a situation where all transfers have been completed.
[0059]
Next, (set of 5) will be described.
FIG. 55 shows the situation before transfer.
FIG. 56 shows the first transfer.
The data D (1) in the memory M (9) is transferred to the memory M (10) and the data D (2) in the memory M (10) is transferred to the memory M (9) (50201, 50202), that is, mutually Forward.
Data D (3) in the memory M (11) is transferred to the memory M (12), and data D (4) in the memory M (12) is transferred to the memory M (11) (50203, 50204), that is, mutual Forward.
[0060]
FIG. 57 shows the situation after the first transfer.
Data D (1) is in memory M (9) and memory M (10)
Data D (2) is in memory M (9) and memory M (10)
Data D (3) is in memory M (11) and memory M (12)
Data D (4) is stored in the memory M (11) and the memory M (12).
[0061]
FIG. 58 shows the second transfer.
Data D (1) and data D (2) in the memory M (9) are collectively transferred to the memory M (1) on one side (50401).
Data D (1) and data D (2) in the memory M (10) are collectively transferred to the memory M (2) on one side (50402).
Data D (3) and data D (4) in the memory M (11) are collectively transferred to the memory M (3) on one side (50403).
Data D (3) and data D (4) in the memory M (12) are collectively transferred to the memory M (4) on one side (50404).
[0062]
FIG. 59 shows the situation after the second transfer.
Data D (1) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (2) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (3) is in memory M (3), memory M (4), memory M (11) and memory M (12),
The data D (4) is stored in the memory M (3), the memory M (4), the memory M (11), and the memory M (12).
[0063]
FIG. 60 shows the third transfer.
Data D (1) and data D (2) in memory M (1) are combined into memory M (3), and data D (3) and data D (4) in memory M (3) are combined into memory Transfer to M (1) (50601, 50602), that is, transfer to each other.
Data D (1) and data D (2) in memory M (2) are combined into memory M (4), and data D (3) and data D (4) in memory M (4) are combined into memory Transfer to M (2) (50603, 50604), that is, transfer to each other.
Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer to M (9) (50605, 50606), that is, transfer to each other.
Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer to M (10) (50607, 50608), that is, transfer to each other.
[0064]
FIG. 61 shows the situation after the third transfer.
Data D (1) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. (12)
Data D (2) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. (12)
Data D (3) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. (12)
Data D (4) is stored in memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), and memory M. It is in (12).
[0065]
FIG. 62 shows the fourth transfer.
Data D (1), data D (2), data D (3), and data D (4) in the memory M (1) are collectively transferred to the memory M (5) (50801).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (2) are collectively transferred to the memory M (6) (50802).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (3) are collectively transferred to the memory M (7) (50803).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (4) are collectively transferred to the memory M (8) (50804).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (9) are collectively transferred to the memory M (13) (50805).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (10) are collectively transferred to the memory M (14) (50806).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (11) are collectively transferred to the memory M (15) (50807).
Data D (1), data D (2), data D (3), and data D (4) in the memory M (12) are collectively transferred to the memory M (16) (50808).
FIG. 63 shows a situation where all transfers have been completed.
[0066]
Next, (6 sets) will be described.
FIG. 64 shows the situation before transfer.
FIG. 65 shows the first transfer.
Data D (1) in the memory M (9) is transferred to the memory M (10), and data D (2) in the memory M (10) is transferred to the memory M (9) (60201, 60202), that is, mutual Forward.
The data D (3) in the memory M (11) is transferred to the memory M (12) and the data D (4) in the memory M (12) is transferred to the memory M (11) (60203, 60204), that is, mutual Forward.
[0067]
FIG. 66 shows the situation after the first transfer.
Data D (1) is in memory M (9) and memory M (10)
Data D (2) is in memory M (9) and memory M (10)
Data D (3) is in memory M (11) and memory M (12)
Data D (4) is stored in the memory M (11) and the memory M (12).
[0068]
FIG. 67 shows the second transfer.
Data D (1) and data D (2) in the memory M (9) are collectively transferred to the memory M (1) (60401).
Data D (1) and data D (2) in the memory M (10) are collectively transferred to the memory M (2) (60402).
Data D (3) and data D (4) in the memory M (11) are collectively transferred to the memory M (3) on one side (60403).
Data D (3) and data D (4) in the memory M (12) are collectively transferred to the memory M (4) on one side (60404).
[0069]
FIG. 68 shows the situation after the second transfer.
Data D (1) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (2) is in memory M (1), memory M (2), memory M (9) and memory M (10),
Data D (3) is in memory M (3), memory M (4), memory M (11) and memory M (12),
The data D (4) is stored in the memory M (3), the memory M (4), the memory M (11), and the memory M (12).
[0070]
FIG. 69 shows the third transfer.
Data D (1) and data D (2) in the memory M (1) are collectively transferred to the memory M (5) on one side (60601).
Data D (1) and data D (2) in the memory M (2) are collectively transferred to the memory M (6) (60602).
Data D (3) and data D (4) in the memory M (3) are collectively transferred to the memory M (7) on one side (60603).
Data D (3) and data D (4) in the memory M (4) are collectively transferred to the memory M (8) on one side (60604).
Data D (1) and data D (2) in the memory M (9) are collectively transferred to the memory M (13) on one side (60605).
Data D (1) and data D (2) in the memory M (10) are collectively transferred to the memory M (14) (60606).
Data D (3) and data D (4) in the memory M (11) are collectively transferred to the memory M (15) (60607).
Data D (3) and data D (4) in the memory M (12) are collectively transferred to the memory M (16) (60608).
[0071]
FIG. 70 shows the situation after the third transfer.
Data D (1) is memory M (1), memory M (2), memory M (5), memory M (6), memory M (9), memory M (10), memory M (13), and memory M. (14)
Data D (2) is stored in memory M (1), memory M (2), memory M (5), memory M (6), memory M (9), memory M (10), memory M (13), and memory M. (14)
Data D (3) is memory M (3), memory M (4), memory M (7), memory M (8), memory M (11), memory M (12), memory M (15), and memory M. (16)
Data D (4) is stored in memory M (3), memory M (4), memory M (7), memory M (8), memory M (11), memory M (12), memory M (15), and memory M. It is in (16).
[0072]
FIG. 71 shows the fourth transfer.
Data D (1) and data D (2) in memory M (1) are combined into memory M (3), and data D (3) and data D (4) in memory M (3) are combined into memory Transfer to M (1) (60801, 60802), that is, transfer to each other.
Data D (1) and data D (2) in memory M (2) are combined into memory M (4), and data D (3) and data D (4) in memory M (4) are combined into memory Transfer to M (2) (60803, 60804), that is, transfer to each other.
Data D (1) and data D (2) in memory M (5) are combined into memory M (7), and data D (3) and data D (4) in memory M (7) are combined into memory Transfer to M (5) (60805, 60806), that is, transfer to each other.
Data D (1) and data D (2) in memory M (6) are combined into memory M (8), and data D (3) and data D (4) in memory M (8) are combined into memory Transfer to M (6) (60807, 60808), that is, transfer to each other.
Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer to M (9) (60809, 60810), that is, transfer to each other.
Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer to M (10) (60811, 60812), that is, transfer to each other.
Data D (1) and data D (2) in memory M (13) are combined into memory M (15), and data D (3) and data D (4) in memory M (15) are combined into memory Transfer to M (13) (60813, 60814), that is, transfer to each other.
Data D (1) and data D (2) in memory M (14) are combined into memory M (16), and data D (3) and data D (4) in memory M (16) are combined into memory Transfer to M (14) (60815, 60816), that is, transfer to each other.
FIG. 72 shows a situation where all transfers have been completed.
This completes the description of (group 2) to (group 6).
[0073]
Now, it will be described that (1 set) is a more efficient transfer method than (2 set) to (6 set).
The communication speed is generally divided into a preparation time for communication and a time during actual communication.
From (1 set) to (6 set), the number of transfers is all four, so the preparation time for communication is the same. However, the communication time is different.
In general, it may be considered that the time required for communication increases linearly as the amount of data to be communicated increases.
For the sake of simplicity, the transfer time for one type of data is 1 second.
[0074]
(1 set)
The first transfer takes 1 second because each memory sends one data.
The second transfer takes 1 second because each memory sends one data.
The third transfer takes 1 second because each memory sends one data.
The second transfer takes 2 seconds because each memory sends two data.
Therefore, the total is 5 seconds.
[0075]
  (2 sets)
  The first transfer takes 1 second because each memory sends one data.
  The second transfer takes 1 second because each memory sends one data.
  In the third transfer, each memorytwo2 seconds to send one data.
  The second transfer takes 2 seconds because each memory sends two data.
  Therefore, the total is 6 seconds.
[0076]
  (Group 3)
  The first transfer takes 1 second because each memory sends one data.
  The second transfer takes 1 second because each memory sends one data.
  In the third transfer, each memorytwo2 seconds to send one data.
  In the fourth transfer, each memoryFour4 seconds to send one data.
  Therefore, the total is 8 seconds.
[0077]
  (4 sets)
  The first transfer takes 1 second because each memory sends one data.
  In the second transfer, each memorytwo2 seconds to send one data.
  In the third transfer, each memoryFour4 seconds to send one data.
  In the fourth transfer, each memoryFour4 seconds to send one data.
  Therefore, the total is 11 seconds.
[0078]
  (5 sets)
  The first transfer takes 1 second because each memory sends one data.
  In the second transfer, each memorytwo2 seconds to send one data.
  In the third transfer, each memorytwo2 seconds to send one data.
  In the fourth transfer, each memoryFour4 seconds to send one data.
  Therefore, the total is 9 seconds.
[0079]
  (6 sets)
  The first transfer takes 1 second because each memory sends one data.
  In the second transfer, each memorytwo2 seconds to send one data.
  In the third transfer, each memorytwo2 seconds to send one data.
  The second transfer takes 2 seconds because each memory sends two data.
  Therefore, the total is 7 seconds.
[0080]
Therefore, 5 seconds (one set) is the fastest.
Here, the one-side transfer and the mutual transfer are made the same speed, but the same (one set) is the fastest even at different speeds.
This is because the time required for mutual transfer is the same in any group, and the length of time is determined by the size of one-sided transfer.
[0081]
  Next, a general case of the data transfer method of the present invention will be described.
  That is, the number of memories is N (M), N (M) is a power of 2, the number of data types is N (D), N (D) is a divisor of the number of memories, and The data transfer method of the present invention when 1 and N (M) are not described.
  In the data transfer method of the present invention in which one or a plurality of data are in different memories, all the data is in all the memories. ) / log (2) times. This number is the optimum number.
  In the data transfer method of the present invention, first,{(log [ ( Number of memory ) / ( Number of data types ) ] }One-sided transfer is performed, and then {log (number of types of data) / log (2)} times of mutual transfer is performed.
[0082]
Next, the reason why the data transfer time can be minimized by adopting the data transfer method of the present invention will be described below.
(1). When the number of data types N (D) is the largest, that is, when N (D) is equal to the number of memories N (M), this is called a global cast, and all transfers in this case consist of mutual transfers. The The number of mutual transfers is log (the number of memories).
The optimum number of transfers when the number of data types is small is smaller than when the number of data types is the largest.
Therefore,

It becomes.
On the other hand, when broadcasting one type of data, it is configured by only one-sided transfer, and the number of times is log (number of memories).
When transferring a general type, the number of transfers should be higher than when transferring at least one type of data by broadcast communication.
Since the number of transfers is log (number of memories) than when transferring one type of data by broadcast communication,

It becomes.
By combining Expressions (1) and (2), the optimum number of transfers is log (the number of memories).
[0083]
  (2). Next, unlike single-sided transfer, mutual transfer does not increase the number of memories with data. Therefore, even if the mutual transfer is performed more than {log (number of types of data) / log (2)} times, the data cannot be transferred to the entire memory.
  Therefore, the maximum number of mutual transfers is {log (number of types of data) / log (2)} times.
  As described in the explanation of mutual transfer in the section of “Prior Art”, it is efficient to increase the number of mutual transfers as much as possible.
  Therefore, the mutual transfer should be performed {log (number of types of data) / log (2)} times.
  The remaining transfers are configured by one-sided transfer that increases the number of memories with data. The number of memories that increase the number of types of data for each data is (number of memories) / (number of types of data).
  If this is configured by one-sided transfer following the Recursive Broadcast Algorithm described in the section “Prior Art”,{(log [ ( Number of memory ) / ( Number of data types ) ] }Times.
  In this way, {log (number of data types) / log (2)} times of mutual transfer and one-sided transfer{(log [ ( Number of memory ) / ( Number of data types ) ] }The total number of times is {(log (number of memories) / log (2)} times, which is the number shown in (1).
[0084]
  next,{(log [ ( Number of memory ) / ( Number of data types ) ] }The order of both one-side transfers and {log (number of types of data) / log (2)} times is a problem.
  Here, the reason why it is more efficient to perform all one-side transfer first will be described.
  Unlike mutual transfer, one-sided transfer increases the number of memories with data.
  In addition, since the mutual transfer is highly efficient, if as many memories as possible can be mutually transferred, the entire memory can be transferred with high efficiency.
  Therefore, if the one-side transfer is performed first as much as possible to increase the number of memories having data and then the mutual transfer is performed, the overall transfer efficiency becomes the highest.
  For this reason, all the one-side transfers are performed first, and then the mutual transfers are performed.
[0085]
  FIG. 1 is a flowchart showing the contents of processing performed in each computer when the data transfer of the present invention is executed in the parallel computer.
  In step 101, optimum data transfer is started.
  In step 102, the number of memories N (M) (same as the number of computers) is input. In step 103, the number of data types N (D) is input, and data storage location information indicating in which memory the data to be transferred is stored is input.
  Each computer has a table of data transfer order patterns determined by the combination of the number of memories N (M), the number of data types N (D), and data storage location information for each combination. Are transferred sequentially.
  First, in step 104,{Log [ ( N ( M )) / ( N ( D )) ]}One-sided transfer.
  Next, in step 105, mutual transfer is performed {log (N (D)) / log (2)} times.
  In step 106, the optimum data transfer is terminated.
[0086]
Furthermore, the following case will be described in detail as another specific example.
That is, when 16 memories are used, and 8 of them have different data of the same size, that is, the memory M (1) among the memories M (1) to M (16) Data D (1), data M (2) in memory M (2), data D (3) in memory M (3), data D (4) in memory M (4), memory Data D (5) is stored in M (5), data D (6) is stored in memory M (6), data D (7) is stored in memory M (7), and data D is stored in memory M (8). (8) If there is, transfer so that all data is in all memory.
That is, data D (1), data D (2), data D (3), data D (4), data D (5), data D (6), data D (7), data D (8) The optimum data transfer method when data is transferred as in the memories M (1) to M (16) will be specifically described.
In this case, the data transfer method is based on the general description of the data transfer method described above, with one-side transfer being performed once and then mutual transfer being performed three times.
[0087]
  Next, figure73From figure81This will be specifically described with reference to FIG.
  Figure73Indicates the situation before transfer.
  Data D (1) is in memory M (1), data D (2) is in memory M (2), data D (3) is in memory M (3), and data D (4) is in memory M (4), data D (5) is in memory M (5), data D (6) is in memory M (6), data D (7) is in memory M (7), data D (8) is in the memory M (8).
[0088]
  Figure74Represents the first transfer.
  Data D (1) in the memory M (1) is transferred to one side (70201) to the memory M (9).
  Data D (2) in the memory M (2) is transferred to one side (70202) to the memory M (10).
  Data D (3) in the memory M (3) is transferred to one side (70203) to the memory M (11).
  Data D (4) in the memory M (4) is transferred to one side (70204) to the memory M (12).
  Data D (5) in the memory M (5) is transferred to one side (70205) to the memory M (13).
  Data D (6) in the memory M (6) is transferred to one side (70206) to the memory M (14).
  Data D (7) in the memory M (7) is transferred to the memory M (15) on one side (70207).
  Data D (8) in the memory M (8) is transferred to one side (70208) to the memory M (16).
[0089]
  Figure75Indicates the situation after the first transfer.
  Data D (1) is in memory M (1) and memory M (9)
Data D (2) is in memory M (2) and memory M (10)
Data D (3) is in memory M (3) and memory M (11)
Data D (4) is in memory M (4) and memory M (12)
Data D (5) is in memory M (5) and memory M (13)
Data D (6) is in memory M (6) and memory M (14)
Data D (7) is in memory M (7) and memory M (15)
Data D (8) is stored in the memory M (8) and the memory M (16).
[0090]
  Figure76Represents the second transfer.
  The data D (1) in the memory M (1) is transferred to the memory M (2), and the data D (2) in the memory M (2) is transferred to the memory M (1) (70401, 70402), that is, mutual Forward.
  Data D (3) in the memory M (3) is transferred to the memory M (4), and data D (4) in the memory M (4) is transferred to the memory M (3) (70403, 70404), that is, mutual Forward.
  Data D (5) in the memory M (5) is transferred to the memory M (6), and data D (6) in the memory M (6) is transferred to the memory M (5) (70405, 70406), that is, mutual Forward.
  Data D (7) in the memory M (7) is transferred to the memory M (8), and data D (8) in the memory M (8) is transferred to the memory M (7) (70407, 70408), that is, mutual Forward.
  Data D (1) in the memory M (9) is transferred to the memory M (10), and data D (2) in the memory M (10) is transferred to the memory M (9) (70409, 70410), that is, mutual Forward.
  The data D (3) in the memory M (11) is transferred to the memory M (12) and the data D (4) in the memory M (12) is transferred to the memory M (11) (70411, 70412), that is, mutual Forward.
  Data D (5) in the memory M (13) is transferred to the memory M (14), and data D (6) in the memory M (14) is transferred to the memory M (13) (70413, 70414), that is, mutual Forward.
  Data D (7) in the memory M (15) is transferred to the memory M (16), and data D (8) in the memory M (16) is transferred to the memory M (15) (70415, 70416), that is, mutual Forward.
[0091]
  Figure77Indicates the situation after the second transfer.
  Data D (1) is in memory M (1), memory M (2), memory M (9), memory M (10),
Data D (2) is in memory M (1), memory M (2), memory M (9), memory M (10),
Data D (3) is in memory M (3), memory M (4), memory M (11), memory M (12),
Data D (4) is in memory M (3), memory M (4), memory M (11), memory M (12),
Data D (5) is in memory M (5), memory M (6), memory M (13), memory M (14),
Data D (6) is in memory M (5), memory M (6), memory M (13), memory M (14),
Data D (7) is in memory M (7), memory M (8), memory M (15), memory M (16),
Data D (8) is stored in the memory M (7), the memory M (8), the memory M (15), and the memory M (16).
[0092]
  Figure78Represents the third transfer.
  Data D (1) and data D (2) in memory M (1) are combined into memory M (3), and data D (3) and data D (4) in memory M (3) are combined into memory Transfer to M (1) (70601, 70602), that is, transfer to each other.
  Data D (1) and data D (2) in memory M (2) are combined into memory M (4), and data D (3) and data D (4) in memory M (4) are combined into memory Transfer to M (2) (70603, 70604), that is, transfer to each other.
  Data D (5) and data D (6) in memory M (5) are combined into memory M (7), and data D (5) and data D (6) in memory M (7) are combined into memory Transfer to M (5) (70605, 70606), that is, transfer to each other.
  Data D (5) and data D (6) in memory M (6) are combined into memory M (8), and data D (5) and data D (6) in memory M (8) are combined into memory Transfer to M (6) (70607, 70608), that is, transfer to each other.
  Data D (1) and data D (2) in memory M (9) are combined into memory M (11), and data D (3) and data D (4) in memory M (11) are combined into memory Transfer to M (9) (70609, 70610), that is, transfer to each other.
  Data D (1) and data D (2) in memory M (10) are combined into memory M (12), and data D (3) and data D (4) in memory M (12) are combined into memory Transfer to M (10) (70611, 70612), that is, transfer to each other.
  Data D (5) and data D (6) in memory M (13) are combined into memory M (15), and data D (5) and data D (6) in memory M (15) are combined into memory Transfer to M (13) (70613, 70614), that is, transfer to each other.
  Data D (5) and data D (6) in memory M (14) are combined into memory M (16), and data D (5) and data D (6) in memory M (16) are combined into memory Transfer to M (14) (70615, 70616), that is, transfer to each other.
[0093]
  Figure79Indicates the situation after the third transfer.
  Data D (1) is memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), memory M (12)
Data D (2) is memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), memory M (12)
Data D (3) is memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), memory M (12)
Data D (4) is memory M (1), memory M (2), memory M (3), memory M (4), memory M (9), memory M (10), memory M (11), memory M (12)
Data D (5) is memory M (5), memory M (6), memory M (7), memory M (8), memory M (13), memory M (14), memory M (15), memory M (16)
Data D (6) is memory M (5), memory M (6), memory M (7), memory M (8), memory M (13), memory M (14), memory M (15), memory M (16)
Data D (7) is memory M (5), memory M (6), memory M (7), memory M (8), memory M (13), memory M (14), memory M (15), memory M (16)
Data D (8) is memory M (5), memory M (6), memory M (7), memory M (8), memory M (13), memory M (14), memory M (15), memory M It is in (16).
[0094]
  Figure80Represents the fourth transfer.
  Data D (1), data D (2), data D (3), and data D (4) in memory M (1) are combined into memory M (5) and data D (in memory M (5) 5), data D (6), data D (7), and data D (8) are transferred together (70801, 70802), ie, transferred to the memory M (1).
  Data D (1), data D (2), data D (3), and data D (4) in memory M (2) are combined into memory M (6) and data D (in memory M (6) 5), data D (6), data D (7), and data D (8) are transferred together (70803, 70804), that is, transferred to the memory M (2).
  Data D (1), data D (2), data D (3), and data D (4) in memory M (3) are combined into memory M (7), and data D (in memory M (7) 5), data D (6), data D (7), and data D (8) are transferred together to the memory M (3) (70805, 70806), that is, mutually transferred.
  Data D (1), data D (2), data D (3), and data D (4) in memory M (4) are combined into memory M (8) and data D (in memory M (8) 5), data D (6), data D (7), and data D (8) are transferred together to the memory M (4) (70807, 70808), that is, mutually transferred.
  Data D (1), data D (2), data D (3), and data D (4) in memory M (9) are combined into memory M (13) and data D (in memory M (13) 5), data D (6), data D (7), and data D (8) are collectively transferred to the memory M (9) (70809, 70810), that is, mutually transferred.
  The data D (1), data D (2), data D (3), and data D (4) in the memory M (10) are combined into the memory M (14), and the data D ( 5), data D (6), data D (7), and data D (8) are transferred together to the memory M (10) (70811, 70812), that is, mutually transferred.
  The data D (1), data D (2), data D (3), and data D (4) in the memory M (11) are collectively stored in the memory M (15), and the data D ( 5), data D (6), data D (7), and data D (8) are transferred together (70813, 70814), that is, transferred to the memory M (11).
  Data D (1), data D (2), data D (3), and data D (4) in the memory M (12) are collectively stored in the memory M (16), and the data D ( 5), data D (6), data D (7), and data D (8) are transferred together to the memory M (12) (70815, 70816), that is, mutually transferred.
  Figure81Indicates the state after the transfer ends.
[0095]
【The invention's effect】
According to the present invention, when one or a plurality of data is in different memories in a computer having a plurality of memory and memory combinations, it is desired to perform data transfer so that all the data is in all the memories. Sometimes, the optimal combination of one-sided communication and mutual communication can achieve the desired data transfer with the shortest execution time.
[Brief description of the drawings]
FIG. 1 is a diagram illustrating a flowchart of processing performed in each computer when data transfer is executed.
FIG. 2 is a diagram illustrating processing contents of one-side transfer.
FIG. 3 is a diagram illustrating processing contents of mutual transfer.
FIG. 4 is a diagram illustrating an initial state of broadcast type transfer.
FIG. 5 is a diagram showing a first stage transfer of a broadcast type transfer.
FIG. 6 is a diagram illustrating a state after transfer in the first stage of broadcast-type transfer.
FIG. 7 is a diagram illustrating second-stage transfer of broadcast-type transfer.
FIG. 8 is a diagram illustrating a state after the second-stage transfer of the broadcast type transfer.
FIG. 9 is a table showing an initial state of broadcast type transfer.
FIG. 10 is a table showing first-stage transfer of broadcast type transfer.
FIG. 11 is a table showing a state after transfer in the first stage of broadcast type transfer.
FIG. 12 is a table showing second-stage transfer of broadcast type transfer.
FIG. 13 is a table showing a state after transfer in the second stage of broadcast type transfer.
FIG. 14 is a diagram illustrating two nodes connected by a transfer path on a network.
15 is a diagram showing characteristics of transfer hardware of a parallel computer, which is an example of realizing the form of data transfer shown in FIG. 14 as a product.
FIG. 16 is a diagram illustrating an example of product data.
FIG. 17 is a diagram illustrating an example of sales data.
FIG. 18 shows a configuration example of a parallel database.
FIG. 19 is a diagram illustrating an initial state of optimal transfer of 16 memories and four types of data.
FIG. 20 is a diagram illustrating a first transfer of 16 memories and optimal transfer of four types of data.
FIG. 21 is a diagram illustrating the first transfer after the first transfer of 16 memories and four types of data.
FIG. 22 is a diagram illustrating a second transfer of the optimal transfer of 16 memories and four types of data.
FIG. 23 is a diagram showing a state after the second transfer of the optimal transfer of 16 memories and four types of data.
FIG. 24 is a diagram illustrating a third transfer of the 16-memory, optimal transfer of four types of data.
FIG. 25 is a diagram showing a state after the third transfer of 16 memories and the optimum transfer of four types of data.
FIG. 26 is a diagram illustrating a fourth transfer of the 16-memory, four-type data optimum transfer.
FIG. 27 is a diagram illustrating a state after the fourth transfer of the optimal transfer of 16 memories and four types of data.
FIG. 28 is a diagram illustrating an initial state of non-optimal transfer with 16 memories and four types of data.
FIG. 29 is a diagram illustrating a first transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 30 is a diagram illustrating a first non-optimal transfer with 16 memories and four types of data after the first transfer.
FIG. 31 is a diagram illustrating a second transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 32 is a diagram showing a second non-optimal transfer with 16 memories and four types of data after the second transfer.
FIG. 33 is a diagram illustrating a third transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 34 is a diagram illustrating a third memory after the third transfer of 16 memories and four types of data that is not optimal.
FIG. 35 is a diagram illustrating a fourth transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 36 is a diagram illustrating a fourth non-optimal transfer with 16 memories and four types of data after the fourth transfer.
FIG. 37 is a diagram illustrating an initial state of non-optimal transfer with 16 memories and four types of data.
FIG. 38 is a diagram illustrating a first transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 39 is a diagram illustrating a first non-optimal transfer with 16 memories and four types of data after the first transfer.
FIG. 40 is a diagram illustrating a second transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 41 is a diagram showing a second non-optimal transfer with 16 memories and four types of data after the second transfer.
FIG. 42 is a diagram illustrating a third transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 43 is a diagram illustrating a third memory after the third transfer of 16 memories and four types of data that is not optimal.
FIG. 44 is a diagram illustrating a fourth transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 45 is a diagram illustrating a fourth non-optimal transfer with 16 memories and four types of data after the fourth transfer.
FIG. 46 is a diagram illustrating an initial state of non-optimal transfer with 16 memories and four types of data.
FIG. 47 is a diagram illustrating a first transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 48 is a diagram showing a first non-optimal transfer with 16 memories and four types of data after the first transfer.
FIG. 49 is a diagram illustrating a second transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 50 is a diagram illustrating a second non-optimal transfer with 16 memories and four types of data after the second transfer.
FIG. 51 is a diagram showing a third transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 52 is a diagram illustrating a third non-optimal transfer with 16 memories and four types of data after the third transfer.
FIG. 53 is a diagram showing a fourth transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 54 is a diagram illustrating a fourth non-optimal transfer with 16 memories and four types of data after the fourth transfer.
FIG. 55 is a diagram illustrating an initial state of non-optimal transfer with 16 memories and four types of data.
FIG. 56 is a diagram illustrating a first transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 57 is a diagram illustrating a first non-optimal transfer with 16 memories and four types of data after the first transfer.
FIG. 58 is a diagram illustrating a second transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 59 is a diagram showing a second non-optimal transfer with 16 memories and four types of data after the second transfer.
FIG. 60 is a diagram illustrating a third transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 61 is a diagram illustrating a third non-optimal transfer with 16 memories and four types of data after the third transfer.
FIG. 62 is a diagram illustrating a fourth transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 63 is a diagram illustrating a fourth non-optimal transfer with 16 memories and four types of data after the fourth transfer.
FIG. 64 is a diagram illustrating an initial state of non-optimal transfer with 16 memories and four types of data.
FIG. 65 is a diagram illustrating a first transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 66 is a diagram illustrating a first non-optimal transfer with 16 memories and four types of data after the first transfer.
FIG. 67 is a diagram illustrating a second transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 68 is a diagram showing a second non-optimal transfer with 16 memories and four types of data after the second transfer.
FIG. 69 is a diagram showing a third transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 70 is a diagram illustrating a third non-optimal transfer with 16 memories and four types of data after the third transfer.
FIG. 71 is a diagram illustrating a fourth transfer of non-optimal transfer with 16 memories and four types of data.
FIG. 72 is a diagram illustrating a fourth non-optimal transfer with 16 memories and four types of data after the fourth transfer.
FIG. 73 is a diagram illustrating an initial state of optimal transfer of 16 memories and 8 types of data.
FIG. 74 is a diagram illustrating a first transfer of optimal transfer of 16 memories and 8 types of data.
FIG. 75 is a diagram illustrating a state after the first transfer of the optimal transfer of 16 memories and 8 types of data.
FIG. 76 is a diagram illustrating a second transfer of optimal transfer of 16 memories and 8 types of data.
FIG. 77 is a diagram showing a state after the second transfer of the optimal transfer of 16 memories and 8 types of data.
FIG. 78 is a diagram showing a third transfer of optimal transfer of 16 memories and 8 types of data.
FIG. 79 is a diagram showing a state after the third transfer of the optimal transfer of 16 memories and 8 types of data.
FIG. 80 is a diagram illustrating a fourth transfer of optimal transfer of 16 memories and 8 types of data.
FIG. 81 is a diagram showing a state after the fourth transfer of the optimal transfer of 16 memories and 8 types of data.
[Explanation of symbols]
1401, 1408 output port
1402, 1407 Input port
1403, 1409 data
1404, 1410 nodes
1405, 1406 Transfer route
1411 and 1412 processors
1501-1504, 1801-1804 Crossbar
1505, 1507, 1509, 1511, 1805, 1807, 1809, 1811 switch
1506, 1508, 1510, 1512, 1806, 1808, 1810, 1812 nodes

Claims (2)

One-sided transfer that has M nodes (where M is a power of 2) having individual memories, and transfers data in the memory of one node to the memory of the other node, and each of the two nodes In a network in which data in a memory can be transferred to each other at the same time and the transfer amount per unit time in the mutual transfer is larger than the transfer amount per unit time in the one-side transfer, D (where 1 < A node-to-node data transfer method for transferring each data in the memory of a node of D <M, where D is a divisor of M) to all other nodes,
In the inter-node transfer method, each data is transferred between the nodes by performing log (M / D) one-side transfer and then performing (log D / log 2) mutual transfer. M computers (in which M is a power of 2) having individual memories are connected by a hyper crossbar network, and the data in the memory of one computer is transferred to the memory of the other computer between these computers. D computers (where 1 <D <M and D is a divisor of M) in a parallel computer that can perform one-sided transfer and mutual transfer that simultaneously transfers data in the memories of two computers to each other A computer-to-computer data transfer method for transferring each data in the memory to all other nodes,
The computer-to-computer data transfer method is characterized in that each data is transferred between the computers after log (M / D) one-sided transfer and then (logD / log2) mutual transfer.

Images