(57)【特許請求の範囲】
【請求項１】
個々のメモリを有するＭ個（但し、Ｍは２のべき乗数）のノードを有し、一方のノードのメモリにあるデータを他方のノードのメモリに転送する片側転送と、二つのノードのそれぞれのメモリにあるデータを同時に互いに転送しあう相互転送ができ、且つ前記相互転送における単位時間あたりの転送量が前記片側転送における単位時間あたりの転送量よりも大きいネットワークにおいて、Ｄ個（但し、１＜Ｄ＜Ｍで、ＤはＭの約数）のノードのメモリ中の各データを他の全てのノードに転送するノード間データ転送方法であって、
前記ノード間での前記各データの転送は、ｌｏｇ（Ｍ／Ｄ）回の片側転送行った後、（ｌｏｇＤ／ｌｏｇ２）回の相互転送を行うことを特徴とするノード間転送方法。
【請求項２】
個々のメモリを有するＭ個（但し、Ｍは２のべき乗数）の計算機がハイパークロスバーネットワークにより接続され、それらの計算機間では、一方の計算機のメモリにあるデータを他方の計算機のメモリに転送する片側転送と、二つの計算機のそれぞれのメモリにあるデータを同時に互いに転送しあう相互転送ができる並列計算機において、Ｄ個（但し、１＜Ｄ＜Ｍで、ＤはＭの約数）の計算機のメモリ中の各データを他の全てのノードに転送する計算機間データ転送方法であって、
前記計算機間での前記各データの転送は、ｌｏｇ（Ｍ／Ｄ）回の片側転送行った後、（ｌｏｇＤ／ｌｏｇ２）回の相互転送を行うことを特徴とする計算機間データ転送方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メモリが多数ある計算機システムにおけるデータ転送方式に関し、ネットワークの効果的な利用方法に関する。
【０００２】
【従来の技術】
従来の技術として、従来の通信方式技術と、従来のネットワークハードウェア技術を説明する。
通信方式技術並びにネットワークハードウェアに関する参照文献として、奥川峻史著「並列計算機アーキテクチャ」（コロナ社）、中澤喜三郎著「計算機アーキテクチャと構成方法」（朝倉書店）がある。
従来の通信方式技術として、片側通信（図２）、相互通信（図３）、放送型通信（図４から図１３）などがあった。片側通信は片側転送とも、相互通信は相互転送とも、放送型通信は放送型転送とも呼ぶことにする。
【０００３】
片側通信とは、一方のメモリにあるデータをもう一方のメモリ上に転送する通信方式である。
図２のように、あるメモリ（201）からもう一つのメモリ（201）へ、データ（203）を転送（204）させる通信方式である。
PING-PONG通信、POINT-TO-PINT通信、PIER-TO-PIER通信などとも呼ばれている。
【０００４】
相互通信とは、二つのメモリにあるデータを同時に互いに転送しあう通信方式である。
図３のように、あるメモリ（301）ともう一つのメモリ（302）にそれぞれあるデータ（303）とデータ（304）をそれぞれ互いに、しかも同時に送り合う（305）（306）通信方式である。EXCHANGE通信とも呼ばれている。
相互通信は、片側通信を逐次に各々の方向から行うことでも構成できる。即ち、まず転送（305）を行ってから、転送（306）を行う。
もしも二つのメモリの間の転送用の経路が一つしかなければ、片側通信を逐次に行うしか方法がない。
【０００５】
しかし、SR2201（日立製作所）など代表的な並列計算機では、二つ以上の経路を持つものが多い。これは、二つ以上のハードウェアの実装を行なってもコストがあまりかからないからである。
そこで、一度に双方向でデータを転送する相互通信を用いると、片側通信を逐次に行うよりも、単位時間当たりにより多くのデータを転送できる。
従って、できる限り相互通信を使ってデータの転送を行うと、より効率の高いデータの転送ができるようになる。
【０００６】
放送型通信とは、ある一つのメモリにあるデータを、他の全てのメモリにあるようにする通信方式である。BROADCAST（ブロードキャスト）通信とも呼ばれている。
一種類のデータをブロードキャストする場合は、片側通信のみで構成され、回数はlog(メモリ数)である。
これは、Recursive Broadcast Algorithm （参考文献；R. Ponnusamy：Scheduling Regular and Irregular Communications Patterns on the CM-5：Supercomputing '92）と呼ばれている。
【０００７】
この方式について、図４から図８を用いて具体的に説明する。
まず、図４が転送前の状況であるとする。
使用するメモリが（401）（402）（403）（404）の合計４つあるとする。そのうちメモリ（401）にデータ（405）があるとする。このデータを残りのメモリ（402）（403）（404）にあるように転送を行うのである。
【０００８】
図５は第一回目の転送を示す。
４つのメモリ（501）（502）（503）（504）のうち、メモリ（501）からメモリ（502）にデータ（505）を転送（506）する。
図６は第一回目の転送後を示す。
４つのメモリ（601）（602）（603）（604）のうち、データ（605）がメモリ（601）に、データ（606）がメモリ（602）にあるようになった。
【０００９】
図７は第二回目の転送を示す。
４つのメモリ（701）（702）（703）（704）においてデータ（705）をメモリ（701）からメモリ（703）へ転送（706）し、それと同時にデータ（707）をメモリ（702）からメモリ（704）へ転送（708）する。
図８は転送が終了した状況を示す。
４つのメモリ（801）（802）（803）（804）に、それぞれデータ（805）（806）（807）（808）がある。
以上が、Recursive Broadcast Algorithmと呼ばれる、片側通信から構成されるブロードキャストの具体例であった。
【００１０】
ここで後の説明でデータの種類数が増えた時のために上記の転送方式を表の形式にしたものを説明する。
図９から図１３がそれにあたる。
図４から図８で説明したデータが、データD(2)であったとする。
図９はデータD(2)がメモリM(1)にあり、メモリM(1)以外のどのメモリ上にもなく、その他のデータはどのメモリ上にもない、という状況を示す。
図９は図４に対応する。図４のデータ（405）が、図９のデータD(2)にあたるとする。
図４のメモリ（401）は図９のメモリM(1)に、図４のメモリ（402）は図９のメモリM(2)に、図４のメモリ（403）は図９のメモリM(3)に、図４のメモリ（404）は図９のメモリM(4)に対応する。
【００１１】
図１０は図５に対応する。
図５のメモリ（501）は図１０のメモリM(1)に、図５のメモリ（502）は図１０のメモリM(2)に、図５のメモリ（503）は図１０のメモリM(3)に、図５のメモリ（504）は図１０のメモリM(4)に対応する。
図５のデータ（505）が、図１０のデータD(2)にあたるとする。図５の転送（506）は、図１０の転送（1001）に対応する。
【００１２】
図１１は図６に対応する。
【００１３】
図６のメモリ（601）は図１１のメモリM(1)に、図６のメモリ（602）は図１１のメモリM(2)に、図６のメモリ（603）は図１１のメモリM(3)に、図６のメモリ（604）は図１１のメモリM(4)に対応する。
図６のデータ（605）が、図１１のメモリM(1)にあるデータD(2)にあたるとする。
図６のデータ（606）が、図１１のメモリM(2)にあるデータD(2)にあたるとする。
【００１４】
図１２は図７に対応する。
図７のメモリ（701）は図１２のメモリM(1)に、図７のメモリ（702）は図１２のメモリM(2)に、図７のメモリ（703）は図１２のメモリM(3)に、図７のメモリ（704）は図１２のメモリM(4)に対応する。
図７のデータ（705）が、図１２のメモリM(1)にあるデータD(2)にあたるとする。
図７のデータ（707）が、図１２のメモリM(2)にあるデータD(2)にあたるとする。
図７の転送（706）は、図１２の転送（1201）に対応する。図７の転送（708）は、図１２の転送（1202）に対応する。
【００１５】
図１３は図８に対応する。
【００１６】
図８のメモリ（801）は図１３のメモリM(1)に、図８のメモリ（802）は図１３のメモリM(2)に、図８のメモリ（803）は図１３のメモリM(3)に、図８のメモリ（804）は図１３のメモリM(4)に対応する。
図８のデータ（805）が、図１３のメモリM(1)にあるデータD(2)にあたるとする。
図８のデータ（806）が、図１３のメモリM(2)にあるデータD(2)にあたるとする。
図８のデータ（807）が、図１３のメモリM(3)にあるデータD(2)にあたるとする。
図８のデータ（808）が、図１３のメモリM(4)にあるデータD(2)にあたるとする。
以上で転送方式を表の形式にしたものの説明を終わる。
これで、従来の通信方式技術の説明を終わる。
【００１７】
次に、従来のネットワークハードウェア技術を説明する。
ハイパクロスバーネットワーク、トーラス型ネットワークが代表的なものとしてある。
ハイパクロスバネットワークは並列計算機SR2201（日立製作所）において採用されており、トーラス型ネットワークは他の並列計算機において採用されている。
特に、ハイパクロスバネットワークを採用している並列計算機SR2201では、任意のメモリ間の転送速度がほぼ同じであり、また、仮想的な一次元アドレスの隣に送る転送などの等方転送の場合、完全に衝突が起きないため、転送速度の劣化はおこらず、常に一定の性能で通信することができる（参考文献  藤井ら著「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）。
従って、どの等方な相互転送もメモリが重ならなければ、一定の転送速度である、というモデルの元、最適な通信を構築できるようになっている。
なお、任意のメモリ間の転送速度がほぼ同じであり、また、どの等方な相互転送もメモリが重ならなければ、一定の転送速度である通信を実現する上で、NIA(Network Interface Adapter)と、SC(Storage Controller)という技術が重要な役割を果たしている。
【００１８】
【発明が解決しようとする課題】
ネットワークに接続された任意の２つのメモリ間での転送性能が同じであり、相互通信における単位時間当たりの転送量が、片側通信における単位時間当たりの転送量よりも大きい、という条件を満たす計算機システムにおいて、次のようなデータ転送を最短の時間で行う方法を構築することを考察する。
そのデータ転送とは、（１）使用する全メモリの数N(M)が２のべき乗である、（２）データの種類N(D)が、使用する全メモリの数N(M)の約数であって、かつ１とN(M)ではない、（３）N(D)種類のデータは全部同じデータ量である、（４）N(D)種類のデータはそれぞれ異なるメモリ上にある、という４つの条件の元、N(D)種類のデータ全部がN(M)個のすべてのメモリにあるようにデータ転送するものをいう。
複数のデータが異なるメモリにある場合、巧く同時にデータを転送することで、通信経路が競合しないように、かつ最適な回数で全メモリにデータを送信する技術が明確ではなかった。
【００１９】
S.L.Johnsonnらの「Optimum Broadcasting and Personalized Communication in Hypercubes」（IEEE Transactions on Computers Vol.38, No.9, Sept. 1989）では、ハミング距離に基づいた最適な転送方式が検討されているが、扱っているネットワークモデルが古いものであり、上記の計算機システムには適用できない。
また、上記の一般的なデータ転送に対する適用もできない。
富士通の堀江らによる「トーラスネットワークにおける最適全対全通信」（並列処理シンポジウムJSPP92）（対応特許：特開平5-151181）では、トーラスネットワークモデルを前提にしており、上記の計算機システムには適用できない。
また、上記の一般的なデータ転送に対する適用もできない。
【００２０】
一つのデータをブロードキャストして、それからもう一つのデータをブロードキャストしていくという方式では、データの種類が増えると転送時間が多くかかってしまい、全体の性能に関して大きな悪影響を及ぼしていた。
メモリの台数を増やして大規模な計算を行う場合では、特に転送にかかる時間が長いと全体の性能に大きく影響を及ぼすことがよく知られており、データ転送の効率化が強く求められている。
しかし、どのような転送方式が有効か、最適な方式はどのように構成されるかが明らかになっていなかった。
本発明の目的は、転送すべき全部のデータが全部のメモリ上にあるようにするデータ転送を最小の時間で実行する最適なデータ転送方法を提供することにある。
【００２１】
【課題を解決するための手段】
上記の目的を達成するため、本発明は、
ノード間でデータの片側転送と相互転送ができ且つ個々にメモリを有するＭ個（但し、Ｍは２のべき乗数）のノードを有するネットワークおいて、Ｄ個（但し、１＜Ｄ＜Ｍで、ＤはＭの約数）のノードのメモリ中の各データを他の全てのノードに転送するノード間データ転送方法であって、
前記ノード間での前記各データの転送は、（ｌｏｇ（Ｍ／Ｄ））回の片側転送を行った後、（ｌｏｇＤ／ｌｏｇ２）回の相互転送を行うようにしている。
【００２２】
また、計算機間でデータの片側転送と相互転送ができ且つ個々にメモリを有するＭ個（但し、Ｍは２のべき乗数）の計算機をネットワークにより接続した並列計算機において、Ｄ個（但し、１＜Ｄ＜Ｍで、ＤはＭの約数）の計算機のメモリ中の各データを他の全ての計算機に転送する計算機間データ転送方法であって、  前記計算機間での前記各データの転送は、（ｌｏｇ（Ｍ／Ｄ））回の片側転送を行った後、（ｌｏｇＤ／ｌｏｇ２）回の相互転送を行うようにしている。
【００２３】
【発明の実施の形態】
本発明は、ネットワークにより接続された複数のノード間におけるデータの転送に関する発明であり、まず、各ノードが備えるべき構成上の特徴について説明する。
図１４は、ネットワーク上の転送経路により接続された２つのノードを示す。
各ノード1404、1410は、それぞれプロセッサ1411、1412とメモリ上に格納されたデータ1403、1409を有する。
そして、ノード間の転送として双方向のデータ転送と片側方向のデータ転送を行うことができるように、各ノードは双方向のデータ転送を同時に行えるように転送経路が２重になっており、転送経路1405、1406を有する。
さらに、各ノードは出力口1401、1408と入力口1402、1407を有するようにしている。
２つのノード間でのデータ転送は、片側方向のデータ転送（以下、片側転送という）の場合は、ノード1404のデータ1403はプロセッサ1411からの命令を受け出力口1401から転送経路1405、入力口1407を通りノード1410へ、あるいはノード1410のデータ1409はプロセッサ1412からの命令を受け出力口1408から転送経路1406、入力口1402を通りノード1404へと、一方の転送経路のみを用いて転送される。
双方向のデータ転送（以下、相互転送という）の場合は、ノード1404のデータ1403はプロセッサ1411からの命令を受け出力口1401から転送経路1405、入力口1407を通りノード1410へ、同時にノード1410のデータ1409はプロセッサ1412からの命令を受け出力口1408から転送経路1406、入力口1402を通りノード1404へと、両方の転送経路を用いて転送される。
【００２４】
次に、本発明が適用されるシステムの一例である並列計算機について説明する。
図１５は、図１４で示したデータ転送の形態を製品として実現している一例である並列計算機の転送ハードウェアの特徴を示した図である。
1501〜1504はクロスバー、1505、1507、1509、1511スイッチ、1506、1508、1510、1512はノード（計算機）である。各ノードは、図１４に示した出力口、入力口を有し双方向のデータ転送ができるノードである。
ノード1506とノード1510の相互転送は、相互転送の可能な転送経路であるクロスバー1501と、そのクロスバーに入出力が同時に可能なスイッチ1505とスイッチ1509、さらに、それらのスイッチはそれぞれノード1505と1509に同時に入出力が可能な構成となっていることによって実現されている。
また、ノード1508とノード1512の相互転送は、相互転送の可能な転送経路であるクロスバー1502と、そのクロスバーに入出力が同時に可能なスイッチ1507とスイッチ1511、さらに、それらのスイッチはそれぞれノード1508と1512に同時に入出力が可能な構成となっていることによって実現されている。
また、ノード1506とノード1508の相互転送もクロスバー1503とスイッチ1505とスイッチ1507によって同様に行われ、ノード1510とノード1512の相互転送もクロスバー1504とスイッチ1509とスイッチ1511によって同様に行われる。
【００２５】
次に、本発明が適用されるシステムの他の一例である並列データベースについて説明する。
図１８は、並列データベースの構成例を示す。
図１５と同様に、スイッチ1805、1807、1809、1811と、クロスバー1801、1802、1803、1804からなるネットワーク構成をもつ。
ディスク1806と1808に例えば、商品データがあり、全部のディスク1806、1808、1810、1812に例えば、売上データがある場合、商品データを全部のディスク1806、1808、1810、1812に転送して商品ＩＤごとのデータをサーチする場合がある。この時に商品データを転送する方式として本発明が適用される。
図１６は、上記商品データの例であり、商品ＩＤ、商品名など商品そのものに関するデータが表としてまとめられている。
図１７は、上記売上データの例であり、伝票ＩＤ、商品ＩＤおよび商品が売られた日時など売上に関するデータが表としてまとめられている。
これらの２つのデータから、どんな製品がいつ売られたかを検索するシステムがあり、データが大量にある時、データは複数のディスクに分けて格納される。
このような場合に、並列データベースが適用される。
【００２６】
次に、並列計算機におけるデータ転送に本発明を適用した具体例について説明する。なお、並列計算機に限られるものではない。
すなわち、それぞれメモリを有する１６台の計算機からなる並列計算機の場合について説明する。なお、以下の説明では、メモリを主体にして説明する。
図１９に示すように、１６台のメモリの内、４台のメモリにそれぞれ異なる同じ大きさのデータがあるとき、すなわち、メモリM(1)〜メモリM(16)のうち、メモリM(9)にはデータD(1)が、メモリM(10)にはデータD(2)が、メモリM(11)にはデータD(3)が、メモリM(12)にはデータD(4)がある場合に、データ全てがすべてのメモリにあるように転送する。
すなわち、データD(1)、データD(2)、データD(3)、データD(4)が、メモリM(1)〜メモリM(16)にあるようにデータ転送する時、最適なデータ転送方法について具体的に説明する。
【００２７】
まず、本発明のデータ転送方法を適用した場合、すなわち、最初に片側転送を２回、その後に相互転送（双方向のデータ転送）を２回する場合について説明する。
図１９から図２７によって説明する。
図１９は転送前の状況を表す。
データD(1)はメモリM(9)に、データD(2)はメモリM(10)に、データD(3)はメモリM(11)に、データD(4)はメモリM(12)にある。
【００２８】
図２０は第一回目の転送を表す。
メモリM(9)にあるデータD(1)をメモリM(1)に片側転送（10201）し、
メモリM(10)にあるデータD(2)をメモリM(2)に片側転送（10202）し、
メモリM(11)にあるデータD(3)をメモリM(3)に片側転送（10203）し、
メモリM(12)にあるデータD(4)をメモリM(4)に片側転送（10204）する。
【００２９】
図２１は第一回目の転送後の状況を表す。
データD(1)はメモリM(9)とメモリM(1)にあり、
データD(2)はメモリM(10)とメモリM(2)にあり、
データD(3)はメモリM(11)とメモリM(3)にあり、
データD(4)はメモリM(12)とメモリM(4)にある。
【００３０】
図２２は第二回目の転送を表す。
メモリM(1)にあるデータD(1)をメモリM(5)に片側転送（10401）し、
メモリM(2)にあるデータD(2)をメモリM(6)に片側転送（10402）し、
メモリM(3)にあるデータD(3)をメモリM(7)に片側転送（10403）し、
メモリM(4)にあるデータD(4)をメモリM(8)に片側転送（10404）し、
メモリM(9)にあるデータD(1)をメモリM(13)に片側転送（10405）し、
メモリM(10)にあるデータD(2)をメモリM(14)に片側転送（10406）し、
メモリM(11)にあるデータD(3)をメモリM(15)に片側転送（10407）し、
メモリM(12)にあるデータD(4)をメモリM(16)に片側転送（10408）する。
【００３１】
図２３は第二回目の転送後の状況を表す。
データD(1)はメモリM(1)とメモリM(5)とメモリM(9)とメモリM(13)にあり、
データD(2)はメモリM(2)とメモリM(6)とメモリM(10)とメモリM(14)にあり、
データD(3)はメモリM(3)とメモリM(7)とメモリM(11)とメモリM(15)にあり、
データD(4)はメモリM(4)とメモリM(8)とメモリM(12)とメモリM(16)にある。
【００３２】
図２４は第三回目の転送を表す。
メモリM(1)にあるデータD(1)をメモリM(2)に、メモリM(2)にあるデータD(2)をメモリM(1)に、それぞれ転送（10601、10602）、すなわち相互転送する。
メモリM(3)にあるデータD(3)をメモリM(4)に、メモリM(4)にあるデータD(4)をメモリM(3)に、それぞれ転送（10603、10604）、すなわち相互転送する。
メモリM(5)にあるデータD(1)をメモリM(6)に、メモリM(6)にあるデータD(2)をメモリM(5)に、それぞれ転送（10605、10606）、すなわち相互転送する。
メモリM(7)にあるデータD(3)をメモリM(8)に、メモリM(8)にあるデータD(4)をメモリM(7)に、それぞれ転送（10607、10608）、すなわち相互転送する。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（10609、10610）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（10611、10612）、すなわち相互転送する。
メモリM(13)にあるデータD(1)をメモリM(14)に、メモリM(14)にあるデータD(2)をメモリM(13)に、それぞれ転送（10613、10614）、すなわち相互転送する。
メモリM(15)にあるデータD(3)をメモリM(16)に、メモリM(16)にあるデータD(4)をメモリM(15)に、それぞれ転送（10615、10616）、すなわち相互転送する。
【００３３】
図２５は第三回目の転送後の状況を表す。
【００３４】
データD(1)はメモリM(1)、メモリM(2)、メモリM(5)、メモリM(6)、メモリM(9)、メモリM(10)、メモリM(13)、メモリM(14)にあり、
データD(2)はメモリM(1)、メモリM(2)、メモリM(5)、メモリM(6)、メモリM(9)、メモリM(10)、メモリM(13)、メモリM(14)にあり、
データD(3)はメモリM(3)、メモリM(4)、メモリM(7)、メモリM(8)、メモリM(11)、メモリM(12)、メモリM(15)、メモリM(16)にあり、
データD(4)はメモリM(3)、メモリM(4)、メモリM(7)、メモリM(8)、メモリM(11)、メモリM(12)、メモリM(15)、メモリM(16)にある。
【００３５】
図２６は第四回目の転送を表す。
【００３６】
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(3)に、メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(1)に、それぞれ転送（10801、10802）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(4)に、メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(2)に、それぞれ転送（10803、10804）、すなわち相互転送する。
メモリM(5)にあるデータD(1)とデータD(2)をまとめてメモリM(7)に、メモリM(7)にあるデータD(3)とデータD(4)をまとめてメモリM(5)に、それぞれ転送（10805、10806）、すなわち相互転送する。
メモリM(6)にあるデータD(1)とデータD(2)をまとめてメモリM(8)に、メモリM(8)にあるデータD(3)とデータD(4)をまとめてメモリM(6)に、それぞれ転送（10807、10808）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（10809、10810）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（10811、10812）、すなわち相互転送する。
メモリM(13)にあるデータD(1)とデータD(2)をまとめてメモリM(15)に、メモリM(15)にあるデータD(3)とデータD(4)をまとめてメモリM(13)に、それぞれ転送（10813、10814）、すなわち相互転送する。
メモリM(14)にあるデータD(1)とデータD(2)をまとめてメモリM(16)に、メモリM(16)にあるデータD(3)とデータD(4)をまとめてメモリM(14)に、それぞれ転送（10815、10816）、すなわち相互転送する。
図２７は全ての転送が終了した状態を表す。
【００３７】
以上、本発明のデータ転送方法を適用した場合について説明したが、この１６のメモリと４種類のデータでの通信は、片側転送を２回と相互転送を２回で構成される。
この片側転送と相互転送の組みは４回の内、２回を組み合わせる順列組み合わせであるから、合計６通りある。
具体的には、
（１の組）片側ー片側ー相互ー相互
（２の組）片側ー相互ー片側ー相互
（３の組）片側ー相互ー相互ー片側
（４の組）相互ー相互ー片側ー片側
（５の組）相互ー片側ー相互ー片側
（６の組）相互ー片側ー片側ー相互
の６つである。
このうち、（１の組）が上記本発明を適用した場合である。
以下に、本発明を適用しない（２の組）から（６の組）について、図２８から図７２を用いて説明する。
【００３８】
まず、（２の組）について説明する。
図２８は転送前の状況を表す。
図２９は第一回目の転送を表す。
メモリM(9)にあるデータをM(1)に片側転送（20201）する。
メモリM(10)にあるデータをM(2)に片側転送（20202）する。
メモリM(11)にあるデータをM(3)に片側転送（20203）する。
メモリM(12)にあるデータをM(4)に片側転送（20204）する。
【００３９】
図３０は第一回目の転送後の状況を表す。
データD(1)はメモリM(1)とメモリM(9)にあり、
データD(2)はメモリM(2)とメモリM(10)にあり、
データD(3)はメモリM(3)とメモリM(11)にあり、
データD(4)はメモリM(4)とメモリM(12)にある。
【００４０】
図３１は第二回目の転送を表す。
メモリM(1)にあるデータD(1)をメモリM(2)に、メモリM(2)にあるデータD(2)をメモリM(1)に、それぞれ転送（20401、20402）、すなわち相互転送する。
メモリM(3)にあるデータD(3)をメモリM(4)に、メモリM(4)にあるデータD(4)をメモリM(3)に、それぞれ転送（20403、20404）、すなわち相互転送する。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（20405、20406）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（20407、20408）、すなわち相互転送する。
【００４１】
図３２は第二回目の転送後の状況を表す。
データ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)にある。
【００４２】
図３３は第三回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(5)に片側転送（20601）する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(6)に片側転送（20602）する。
メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(7)に片側転送（20603）する。
メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(8)に片側転送（20604）する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(13)に片側転送（20605）する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(14)に片側転送（20606）する。
メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(15)に片側転送（20607）する。
メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(16)に片側転送（20608）する。
【００４３】
図３４は第三回目の転送後の状況を表す。
データD(1)がメモリM(1)とメモリM(2)とメモリM(5)とメモリM(6)とメモリM(9)とメモリM(10)とメモリM(13)とメモリM(14)にあり、
データD(2)がメモリM(1)とメモリM(2)とメモリM(5)とメモリM(6)とメモリM(9)とメモリM(10)とメモリM(13)とメモリM(14)にあり、
データD(3)がメモリM(3)とメモリM(4)とメモリM(7)とメモリM(8)とメモリM(11)とメモリM(12)とメモリM(15)とメモリM(16)にあり、
データD(4)がメモリM(3)とメモリM(4)とメモリM(7)とメモリM(8)とメモリM(11)とメモリM(12)とメモリM(15)とメモリM(16)にある。
【００４４】
図３５は第四回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(3)に、メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(1)に、それぞれ転送（20801、20802）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(4)に、メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(2)に、それぞれ転送（20803、20804）、すなわち相互転送する。
メモリM(5)にあるデータD(1)とデータD(2)をまとめてメモリM(7)に、メモリM(7)にあるデータD(3)とデータD(4)をまとめてメモリM(5)に、それぞれ転送（20805、20806）、すなわち相互転送する。
メモリM(6)にあるデータD(1)とデータD(2)をまとめてメモリM(8)に、メモリM(8)にあるデータD(3)とデータD(4)をまとめてメモリM(6)に、それぞれ転送（20807、20808）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（20809、20810）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（20811、20812）、すなわち相互転送する。
メモリM(13)にあるデータD(1)とデータD(2)をまとめてメモリM(15)に、メモリM(15)にあるデータD(3)とデータD(4)をまとめてメモリM(13)に、それぞれ転送（20813、20814）、すなわち相互転送する。
メモリM(14)にあるデータD(1)とデータD(2)をまとめてメモリM(16)に、メモリM(16)にあるデータD(3)とデータD(4)をまとめてメモリM(14)に、それぞれ転送（20815、20816）、すなわち相互転送する。
図３６は全ての転送が終了した状況を表す。
【００４５】
次に、（３の組）について説明する。
図３７は転送前の状況を表す。
図３８は第一回目の転送を表す。
メモリM(9)にあるデータをM(1)に片側転送（30201）する。
メモリM(10)にあるデータをM(2)に片側転送（30202）する。
メモリM(11)にあるデータをM(3)に片側転送（30203）する。
メモリM(12)にあるデータをM(4)に片側転送（30204）する。
【００４６】
図３９は第一回目の転送後の状況を表す。
データD(1)はメモリM(1)とメモリM(9)にあり、
データD(2)はメモリM(2)とメモリM(10)にあり、
データD(3)はメモリM(3)とメモリM(11)にあり、
データD(4)はメモリM(4)とメモリM(12)にある。
【００４７】
図４０は第二回目の転送を表す。
メモリM(1)にあるデータD(1)をメモリM(2)に、メモリM(2)にあるデータD(2)をメモリM(1)に、それぞれ転送（30401、30402）、すなわち相互転送する。
メモリM(3)にあるデータD(3)をメモリM(4)に、メモリM(4)にあるデータD(4)をメモリM(3)に、それぞれ転送（30403、30404）、すなわち相互転送する。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（30405、30406）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（30407、30408）、すなわち相互転送する。
【００４８】
図４１は第二回目の転送後の状況を表す。
データ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)にある。
【００４９】
図４２は第三回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(3)に、メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(1)に、それぞれ転送（30601、30602）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(4)に、メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(2)に、それぞれ転送（30603、30604）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（30605、30606）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（30607、30608）、すなわち相互転送する。
【００５０】
図４３は第三回目の転送後の状況を表す。
データ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)にある。
【００５１】
図４４は第四回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(5)に片側転送する。
メモリM(2)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(6)に片側転送する。
メモリM(3)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(7)に片側転送する。
メモリM(4)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(8)に片側転送する。
メモリM(9)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(13)に片側転送する。
メモリM(10)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(14)に片側転送する。
メモリM(11)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(15)に片側転送する。
メモリM(12)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(16)に片側転送する。
図４５は全ての転送が終了した状況を表す。
【００５２】
次に、（４の組）について説明する。
図４６は転送前の状況を表す。
図４７は第一回目の転送を表す。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（40201、40202）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（40203、40204）、すなわち相互転送する。
【００５３】
図４８は第一回目の転送後の状況を表す。
データD(1)がメモリM(9)とメモリM(10)にあり、
データD(2)がメモリM(9)とメモリM(10)にあり、
データD(3)がメモリM(11)とメモリM(12)にあり、
データD(4)がメモリM(11)とメモリM(12)にある。
【００５４】
図４９は第二回目の転送を表す。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（40401、40403）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（40402、40404）、すなわち相互転送する。
【００５５】
図５０は第二回目の転送後の状況を表す。
データD(1)がメモリM(9)とメモリM(10)とメモリM(11)とメモリM(12)にあり、
データD(2)がメモリM(9)とメモリM(10)とメモリM(11)とメモリM(12)にあり、
データD(3)がメモリM(9)とメモリM(10)とメモリM(11)とメモリM(12)にあり、
データD(4)がメモリM(9)とメモリM(10)とメモリM(11)とメモリM(12)にある。
【００５６】
図５１は第三回目の転送を表す。
メモリM(9)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(1)に片側転送（40601）する。
メモリM(10)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(2)に片側転送（40602）する。
メモリM(11)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(3)に片側転送（40603）する。
メモリM(12)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(4)に片側転送（40604）する。
【００５７】
図５２は第三回目の転送後の状況を表す。
データ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)にある。
【００５８】
図５３は第四回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(5)に片側転送（40801）する。
メモリM(2)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(6)に片側転送（40802）する。
メモリM(3)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(7)に片側転送（40803）する。
メモリM(4)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(8)に片側転送（40804）する。
メモリM(9)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(13)に片側転送（40805）する。
メモリM(10)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(14)に片側転送（40806）する。
メモリM(11)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(15)に片側転送（40807）する。
メモリM(12)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(16)に片側転送（40808）する。
図５４は全ての転送が終了した状況を表す。
【００５９】
次に、（５の組）について説明する。
図５５は転送前の状況を表す。
図５６は第一回目の転送を表す。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（50201、50202）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（50203、50204）、すなわち相互転送する。
【００６０】
図５７は第一回目の転送後の状況を表す。
データD(1)がメモリM(9)とメモリM(10)にあり、
データD(2)がメモリM(9)とメモリM(10)にあり、
データD(3)がメモリM(11)とメモリM(12)にあり、
データD(4)がメモリM(11)とメモリM(12)にある。
【００６１】
図５８は第二回目の転送を表す。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(1)に片側転送（50401）する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(2)に片側転送（50402）する。
メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(3)に片側転送（50403）する。
メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(4)に片側転送（50404）する。
【００６２】
図５９は第二回目の転送後の状況を表す。
データ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)にある。
【００６３】
図６０は第三回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(3)に、メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(1)に、それぞれ転送（50601、50602）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(4)に、メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(2)に、それぞれ転送（50603、50604）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（50605、50606）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（50607、50608）、すなわち相互転送する。
【００６４】
図６１は第三回目の転送後の状況を表す。
データ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)にある。
【００６５】
図６２は第四回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(5)に片側転送（50801）する。
メモリM(2)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(6)に片側転送（50802）する。
メモリM(3)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(7)に片側転送（50803）する。
メモリM(4)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(8)に片側転送（50804）する。
メモリM(9)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(13)に片側転送（50805）する。
メモリM(10)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(14)に片側転送（50806）する。
メモリM(11)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(15)に片側転送（50807）する。
メモリM(12)にあるデータD(1)とデータD(2)とデータD(3)とデータD(4)をまとめてメモリM(16)に片側転送（50808）する。
図６３は全ての転送が終了した状況を表す。
【００６６】
次に、（６の組）について説明する。
図６４は転送前の状況を表す。
図６５は第一回目の転送を表す。
メモリM(9)にあるデータD(1)をメモリM(10)に、メモリM(10)にあるデータD(2)をメモリM(9)に、それぞれ転送（60201、60202）、すなわち相互転送する。
メモリM(11)にあるデータD(3)をメモリM(12)に、メモリM(12)にあるデータD(4)をメモリM(11)に、それぞれ転送（60203、60204）、すなわち相互転送する。
【００６７】
図６６は第一回目の転送後の状況を表す。
データD(1)がメモリM(9)とメモリM(10)にあり、
データD(2)がメモリM(9)とメモリM(10)にあり、
データD(3)がメモリM(11)とメモリM(12)にあり、
データD(4)がメモリM(11)とメモリM(12)にある。
【００６８】
図６７は第二回目の転送を表す。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(1)に片側転送（60401）する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(2)に片側転送（60402）する。
メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(3)に片側転送（60403）する。
メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(4)に片側転送（60404）する。
【００６９】
図６８は第二回目の転送後の状況を表す。
データ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)にある。
【００７０】
図６９は第三回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(5)に片側転送（60601）する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(6)に片側転送（60602）する。
メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(7)に片側転送（60603）する。
メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(8)に片側転送（60604）する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(13)に片側転送（60605）する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(14)に片側転送（60606）する。
メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(15)に片側転送（60607）する。
メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(16)に片側転送（60608）する。
【００７１】
図７０は第三回目の転送後の状況を表す。
データD(1)がメモリM(1)とメモリM(2)とメモリM(5)とメモリM(6)とメモリM(9)とメモリM(10)とメモリM(13)とメモリM(14)にあり、
データD(2)がメモリM(1)とメモリM(2)とメモリM(5)とメモリM(6)とメモリM(9)とメモリM(10)とメモリM(13)とメモリM(14)にあり、
データD(3)がメモリM(3)とメモリM(4)とメモリM(7)とメモリM(8)とメモリM(11)とメモリM(12)とメモリM(15)とメモリM(16)にあり、
データD(4)がメモリM(3)とメモリM(4)とメモリM(7)とメモリM(8)とメモリM(11)とメモリM(12)とメモリM(15)とメモリM(16)にある。
【００７２】
図７１は第四回目の転送を表す。
メモリM(1)にあるデータD(1)とデータD(2)をまとめてメモリM(3)に、メモリM(3)にあるデータD(3)とデータD(4)をまとめてメモリM(1)に、それぞれ転送（60801、60802）、すなわち相互転送する。
メモリM(2)にあるデータD(1)とデータD(2)をまとめてメモリM(4)に、メモリM(4)にあるデータD(3)とデータD(4)をまとめてメモリM(2)に、それぞれ転送（60803、60804）、すなわち相互転送する。
メモリM(5)にあるデータD(1)とデータD(2)をまとめてメモリM(7)に、メモリM(7)にあるデータD(3)とデータD(4)をまとめてメモリM(5)に、それぞれ転送（60805、60806）、すなわち相互転送する。
メモリM(6)にあるデータD(1)とデータD(2)をまとめてメモリM(8)に、メモリM(8)にあるデータD(3)とデータD(4)をまとめてメモリM(6)に、それぞれ転送（60807、60808）、すなわち相互転送する。
メモリM(9)にあるデータD(1)とデータD(2)をまとめてメモリM(11)に、メモリM(11)にあるデータD(3)とデータD(4)をまとめてメモリM(9)に、それぞれ転送（60809、60810）、すなわち相互転送する。
メモリM(10)にあるデータD(1)とデータD(2)をまとめてメモリM(12)に、メモリM(12)にあるデータD(3)とデータD(4)をまとめてメモリM(10)に、それぞれ転送（60811、60812）、すなわち相互転送する。
メモリM(13)にあるデータD(1)とデータD(2)をまとめてメモリM(15)に、メモリM(15)にあるデータD(3)とデータD(4)をまとめてメモリM(13)に、それぞれ転送（60813、60814）、すなわち相互転送する。
メモリM(14)にあるデータD(1)とデータD(2)をまとめてメモリM(16)に、メモリM(16)にあるデータD(3)とデータD(4)をまとめてメモリM(14)に、それぞれ転送（60815、60816）、すなわち相互転送する。
図７２は全ての転送が終了した状況を表す。
以上で（２の組）から（６の組）の説明を終わる。
【００７３】
さて、これら（２の組）から（６の組）よりも（１の組）がより効率的な転送方式であることを説明する。
通信の速度は、一般に通信のための準備時間と、実際に通信している時間に分けられる。
（１の組）から（６の組）は転送の回数は全て４回なので通信のための準備の時間は同じである。しかし、通信している時間は異なってくる。
一般に、通信するデータの量が大きい程、通信に要する時間は線形に増えていくとみなしてよい。
簡単に説明するため、一種類のデータの転送時間を１秒とする。
【００７４】
（１の組）では、
第一回目の転送では各メモリが一つのデータを送るので１秒。
第二回目の転送では各メモリが一つのデータを送るので１秒。
第三回目の転送では各メモリが一つのデータを送るので１秒。
第四回目の転送では各メモリが二つのデータを送るので２秒。
よって合計５秒である。
【００７５】
（２の組）では、
第一回目の転送では各メモリが一つのデータを送るので１秒。
第二回目の転送では各メモリが一つのデータを送るので１秒。
第三回目の転送では各メモリが二つのデータを送るので２秒。
第四回目の転送では各メモリが二つのデータを送るので２秒。
よって合計６秒である。
【００７６】
（３の組）では、
第一回目の転送では各メモリが一つのデータを送るので１秒。
第二回目の転送では各メモリが一つのデータを送るので１秒。
第三回目の転送では各メモリが二つのデータを送るので２秒。
第四回目の転送では各メモリが四つのデータを送るので４秒。
よって合計８秒である。
【００７７】
（４の組）では、
第一回目の転送では各メモリが一つのデータを送るので１秒。
第二回目の転送では各メモリが二つのデータを送るので２秒。
第三回目の転送では各メモリが四つのデータを送るので４秒。
第四回目の転送では各メモリが四つのデータを送るので４秒。
よって合計１１秒である。
【００７８】
（５の組）では、
第一回目の転送では各メモリが一つのデータを送るので１秒。
第二回目の転送では各メモリが二つのデータを送るので２秒。
第三回目の転送では各メモリが二つのデータを送るので２秒。
第四回目の転送では各メモリが四つのデータを送るので４秒。
よって合計９秒である。
【００７９】
（６の組）では、
第一回目の転送では各メモリが一つのデータを送るので１秒。
第二回目の転送では各メモリが二つのデータを送るので２秒。
第三回目の転送では各メモリが二つのデータを送るので２秒。
第四回目の転送では各メモリが二つのデータを送るので２秒。
よって合計７秒である。
【００８０】
従って、５秒の（１の組）が最も速い。
ここでは、片側転送と相互転送を同じ速さとしたが、違う速さでも同じように（１の組）が最も速い。
なぜなら、どの組でも相互転送にかかる時間は同じであり、片側転送の大小で時間の長短が決まるからである。
【００８１】
次に、本発明のデータ転送方法の一般の場合について説明する。
すなわち、メモリ数がＮ(Ｍ)で、Ｎ(Ｍ)が２のべき乗の数であり、データの種類数がＮ(Ｄ)で、Ｎ(Ｄ)はメモリ数の約数であって、かつ１とＮ(Ｍ)ではない場合の本発明のデータ転送方法について説明する。
一つあるいは複数のデータがそれぞれ異なるメモリにある場合に、全部のデータが全部のメモリ上にあるようにする本発明のデータ転送方法では、相互転送と片側転送とを、合計でlog(メモリ数)/log(2)の回数行なう。この回数が最適な回数である。
そして、本発明のデータ転送方法では、さらに、最初に{(log〔(メモリ数)/(データの種類数)〕}回の片側転送を行い、次いで、{log(データの種類数)/log(2)}回の相互転送を行う。
【００８２】
次に、本発明のデータ転送方法を取ることにより、何故、データの転送時間を最短にすることができるかについて以下に説明する。
（１）．データの種類数N(D)が最も多い場合、つまりN(D)とメモリ数N(M)が等しい場合、これはグローバルキャストと呼ばれており、この場合の転送は全て相互転送から構成される。その相互転送の回数がlog(メモリ数)である。
データの種類数が少ない場合の最適な転送回数は、最もデータの種類数が多い場合よりも少ない。
したがって、
0003703304.tif 000002
となる。
一方で、一種類のデータをブロードキャストする場合は、片側転送のみで構成され、回数はlog(メモリ数)である。
一般の種類を転送する場合は少なくとも一種類のデータを放送型通信によって転送する場合よりも転送回数は多いはずである。
一種類のデータを放送型通信によって転送する場合よりも転送回数はlog(メモリ数)なので、
0003703304.tif 000003
となる。
式（１）と式（２）を合わせることにより、最適な転送回数は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）、すなわち相互転送する。
図８１は転送終了後の状態を表す。
【００９５】
【発明の効果】
本発明によれば、メモリとメモリの組みが複数あるような計算機において一つあるいは複数のデータがそれぞれ異なるメモリにある場合に、全部のデータが全部のメモリ上にあるようにデータ転送を行いたい時に、片側通信と相互通信の最適な組み合わせることにより、最短の実行時間によって、目的とするデータ転送を達成することができる。
【図面の簡単な説明】
【図１】データ転送を実行する場合に、各計算機において行われる処理のフローチャートを示す図である。
【図２】片側転送の処理内容を示す図である。
【図３】相互転送の処理内容を示す図である。
【図４】放送型転送の初期状態を示す図である。
【図５】放送型転送の第一段の転送を示す図である。
【図６】放送型転送の第一段の転送後の状態を示す図である。
【図７】放送型転送の第二段の転送を示す図である。
【図８】放送型転送の第二段の転送後の状態を示す図である。
【図９】放送型転送の初期状態を表に示す図である。
【図１０】放送型転送の第一段の転送を表に示す図である。
【図１１】放送型転送の第一段の転送後の状態を表に示す図である。
【図１２】放送型転送の第二段の転送を表に示す図である。
【図１３】放送型転送の第二段の転送後の状態を表に示す図である。
【図１４】ネットワーク上の転送経路により接続された２つのノードを示す図である。
【図１５】図１４で示したデータ転送の形態を製品として実現している一例である並列計算機の転送ハードウェアの特徴を示す図である。
【図１６】商品データの例を示す図である。
【図１７】売上データの例を示す図である。
【図１８】並列データベースの構成例を示す
【図１９】１６メモリ、４種類データの最適転送の初期状態を示す図である。
【図２０】１６メモリ、４種類データの最適転送の第一回目の転送を示す図である。
【図２１】１６メモリ、４種類データの最適転送の第一回目の転送後を示す図である。
【図２２】１６メモリ、４種類データの最適転送の第二回目の転送を示す図である。
【図２３】１６メモリ、４種類データの最適転送の第二回目の転送後を示す図である。
【図２４】１６メモリ、４種類データの最適転送の第三回目の転送を示す図である。
【図２５】１６メモリ、４種類データの最適転送の第三回目の転送後を示す図である。
【図２６】１６メモリ、４種類データの最適転送の第四回目の転送を示す図である。
【図２７】１６メモリ、４種類データの最適転送の第四回目の転送後を示す図である。
【図２８】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図２９】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図３０】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図３１】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図３２】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図３３】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図３４】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図３５】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図３６】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図３７】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図３８】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図３９】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図４０】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図４１】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図４２】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図４３】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図４４】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図４５】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図４６】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図４７】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図４８】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図４９】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図５０】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図５１】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図５２】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図５３】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図５４】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図５５】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図５６】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図５７】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図５８】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図５９】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図６０】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図６１】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図６２】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図６３】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図６４】１６メモリ、４種類データのある最適でない転送の初期状態を示す図である。
【図６５】１６メモリ、４種類データのある最適でない転送の第一回目の転送を示す図である。
【図６６】１６メモリ、４種類データのある最適でない転送の第一回目の転送後を示す図である。
【図６７】１６メモリ、４種類データのある最適でない転送の第二回目の転送を示す図である。
【図６８】１６メモリ、４種類データのある最適でない転送の第二回目の転送後を示す図である。
【図６９】１６メモリ、４種類データのある最適でない転送の第三回目の転送を示す図である。
【図７０】１６メモリ、４種類データのある最適でない転送の第三回目の転送後を示す図である。
【図７１】１６メモリ、４種類データのある最適でない転送の第四回目の転送を示す図である。
【図７２】１６メモリ、４種類データのある最適でない転送の第四回目の転送後を示す図である。
【図７３】１６メモリ、８種類データの最適転送の初期状態を示す図である。
【図７４】１６メモリ、８種類データの最適転送の第一回目の転送を示す図である。
【図７５】１６メモリ、８種類データの最適転送の第一回目の転送後を示す図である。
【図７６】１６メモリ、８種類データの最適転送の第二回目の転送を示す図である。
【図７７】１６メモリ、８種類データの最適転送の第二回目の転送後を示す図である。
【図７８】１６メモリ、８種類データの最適転送の第三回目の転送を示す図である。
【図７９】１６メモリ、８種類データの最適転送の第三回目の転送後を示す図である。
【図８０】１６メモリ、８種類データの最適転送の第四回目の転送を示す図である。
【図８１】１６メモリ、８種類データの最適転送の第四回目の転送後を示す図である。
【符号の説明】
１４０１、１４０８  出力口
１４０２、１４０７  入力口
１４０３、１４０９  データ
１４０４、１４１０  ノード
１４０５、１４０６  転送経路
１４１１、１４１２  プロセッサ
１５０１〜１５０４、１８０１〜１８０４  クロスバー
１５０５、１５０７、１５０９、１５１１、１８０５、１８０７、１８０９、１８１１  スイッチ
１５０６、１５０８、１５１０、１５１２、１８０６、１８０８、１８１０、１８１２  ノード
【図１】
0003703304.tif 000004
【図２】
0003703304.tif 000005
【図３】
0003703304.tif 000006
【図４】
0003703304.tif 000007
【図５】
0003703304.tif 000008
【図６】
0003703304.tif 000009
【図７】
0003703304.tif 000010
【図８】
0003703304.tif 000011
【図９】
0003703304.tif 000012
【図１０】
0003703304.tif 000013
【図１１】
0003703304.tif 000014
【図１２】
0003703304.tif 000015
【図１３】
0003703304.tif 000016
【図１４】
0003703304.tif 000017
【図１５】
0003703304.tif 000018
【図１６】
0003703304.tif 000019
【図１７】
0003703304.tif 000020
【図１８】
0003703304.tif 000021
【図１９】
0003703304.tif 000022
【図２０】
0003703304.tif 000023
【図２１】
0003703304.tif 000024
【図２２】
0003703304.tif 000025
【図２３】
0003703304.tif 000026
【図２４】
0003703304.tif 000027
【図２５】
0003703304.tif 000028
【図２６】
0003703304.tif 000029
【図２７】
0003703304.tif 000030
【図２８】
0003703304.tif 000031
【図２９】
0003703304.tif 000032
【図３０】
0003703304.tif 000033
【図３１】
0003703304.tif 000034
【図３２】
0003703304.tif 000035
【図３３】
0003703304.tif 000036
【図３４】
0003703304.tif 000037
【図３５】
0003703304.tif 000038
【図３６】
0003703304.tif 000039
【図３７】
0003703304.tif 000040
【図３８】
0003703304.tif 000041
【図３９】
0003703304.tif 000042
【図４０】
0003703304.tif 000043
【図４１】
0003703304.tif 000044
【図４２】
0003703304.tif 000045
【図４３】
0003703304.tif 000046
【図４４】
0003703304.tif 000047
【図４５】
0003703304.tif 000048
【図４６】
0003703304.tif 000049
【図４７】
0003703304.tif 000050
【図４８】
0003703304.tif 000051
【図４９】
0003703304.tif 000052
【図５０】
0003703304.tif 000053
【図５１】
0003703304.tif 000054
【図５２】
0003703304.tif 000055
【図５３】
0003703304.tif 000056
【図５４】
0003703304.tif 000057
【図５５】
0003703304.tif 000058
【図５６】
0003703304.tif 000059
【図５７】
0003703304.tif 000060
【図５８】
0003703304.tif 000061
【図５９】
0003703304.tif 000062
【図６０】
0003703304.tif 000063
【図６１】
0003703304.tif 000064
【図６２】
0003703304.tif 000065
【図６３】
0003703304.tif 000066
【図６４】
0003703304.tif 000067
【図６５】
0003703304.tif 000068
【図６６】
0003703304.tif 000069
【図６７】
0003703304.tif 000070
【図６８】
0003703304.tif 000071
【図６９】
0003703304.tif 000072
【図７０】
0003703304.tif 000073
【図７１】
0003703304.tif 000074
【図７２】
0003703304.tif 000075
【図７３】
0003703304.tif 000076
【図７４】
0003703304.tif 000077
【図７５】
0003703304.tif 000078
【図７６】
0003703304.tif 000079
【図７７】
0003703304.tif 000080
【図７８】
0003703304.tif 000081
【図７９】
0003703304.tif 000082
【図８０】
0003703304.tif 000083
【図８１】
0003703304.tif 000084