(57)【要約】【課題】フルメッシュで接続された並列計算機システムにおいて、簡易な制御でありながら通信の利用効率を高くし、並列計算における通信時間を短縮する。【解決手段】送信ノード７０４と受信ノード７０５との間を直接接続する直接リンク７０１と、送信ノードと受信ノードとの間を、送信ノード、受信ノード以外の折り返しノード７０６を経由して接続する１ホップリンク７０２と、送信ノードから受信ノードへデータを転送する際、直接リンクのみを使用するリンクと、１ホップリンクのみを使用するリンクと、直接リンクと１ホップリンクとを組み合わせて使用するリンクとの中から、送信ノードと受信ノードとを接続するリンクを選定する通信制御部７０３と、を備えた。【選択図】図４４
2020046713.tif 000002
【特許請求の範囲】
【請求項１】
送信ノードと受信ノードとの間を直接接続する直接リンクと、
前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクと、
前記送信ノードから前記受信ノードへデータを転送する際、前記直接リンクのみを使用するリンクと、前記１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードと前記受信ノードとを接続するリンクを選定する通信制御手段と、
を備えた並列計算機システム。
【請求項２】
前記通信制御手段は、前記直接リンクのみを使用するデータの転送において未使用のノードを前記折り返しノードとして選定する、請求項１に記載の並列計算機システム。
【請求項３】
前記折り返しノードは、前記送信ノードから送信されたデータを前記受信ノードへ転送する折り返し手段を備える、請求項１又は２に記載の並列計算機システム。
【請求項４】
並列計算プログラムを実行する制御手段をさらに備え、前記通信制御手段が、前記送信ノードと前記受信ノードとを接続するリンクとして前記１ホップリンクを選定するとき、前記折り返し手段は、前記制御手段を介すことなく、前記送信ノードから送信されたデータを前記受信ノードへ転送する、請求項３に記載の並列計算機システム。
【請求項５】
前記通信制御手段と前記折り返し手段とは、単一の集積素子に搭載されており、前記通信制御手段は前記折り返し手段を制御する、請求項３又は４に記載の並列計算機システム。
【請求項６】
前記通信制御手段は、前記送信ノードと前記受信ノードと間で転送されるデータ量に応じて、前記直接リンクのみを使用するリンクと、前記１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記転送に要する時間が短いリンクを、前記送信ノードと前記受信ノードとを接続するリンクとして選定する、請求項１から５の何れか１項に記載の並列計算機システム。
【請求項７】
前記送信ノード、前記受信ノード、及び前記折り返しノードのそれぞれは計算ノードであり、前記通信制御手段は、前記計算ノード間の通信の状況を管理する通信管理テーブルと、前記計算ノード間を繋ぐすべてのリンクの使用状況を管理するリンク管理テーブルとを格納する、請求項１から６の何れか１項に記載の並列計算機システム。
【請求項８】
少なくともＮ台（Ｎは３以上の整数）の前記計算ノードが、光ファイバを介して前記直接リンクを用いて個別にすべて接続されたフルメッシュ接続で構成され、前記通信制御手段は、前記通信管理テーブルに格納された前記計算ノード間の通信の状況と、前記リンク管理テーブルに格納された前記計算ノード間を繋ぐすべてのリンクの使用状況とに基づいて、前記通信が１対１通信の場合、１≦Ｋ≦Ｎ−２、マルチキャスト通信の場合、１≦Ｋ≦Ｎ、レデュース又はオールレデュース通信の場合、１≦Ｋ≦Ｎ、をそれぞれ満たすＫ台の折り返しノードを選定する、請求項７に記載の並列計算機システム。
【請求項９】
送信ノードと受信ノードとの間を直接接続する直接リンクのみを使用するリンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードから前記受信ノードへデータを転送する際、前記送信ノードと前記受信ノードとを接続するリンクを選定する工程を備えた並列計算機システムの制御方法。
【請求項１０】
コンピュータに、
送信ノードと受信ノードとの間を直接接続する直接リンクのみを使用するリンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードから前記受信ノードへデータを転送する際、前記送信ノードと前記受信ノードとを接続するリンクを選定する処理を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、並列計算機システム、並列計算機システムの制御方法、及びプログラムに関する。
【背景技術】
【０００２】
並列計算機システムでは、複数のＣＰＵ（Central Processing Unit）コアを使用して並列に計算を行うことで、プログラムを高速に実行することができる。ここで、図４５を参照しつつ、関連する並列計算機システムの構成例について説明する。図４５は、関連する並列計算機システムの構成例を示す図である。
並列計算機システム１００を構成する計算ノード１０１−1から１０１−８（以下の説明において、単に計算ノード１０１ともいう。）は、少なくとも、単数又は複数の演算コアを有するプロセッサと、そのプロセッサに広帯域で接続されたメモリとを有する。そして、関連する並列計算機システム１００は、図４５に示すように、複数の計算ノード１０１の各々が、リンク１０２を介して電気スイッチ１０３と接続される。そして、この複数の計算ノード１０１は並列計算を行う。なお、図４５には、フラットなツリー型のネットワークを記載しているが、リング型、トーラス型など複数のトポロジーが使われる。
【０００３】
並列計算では、２つの計算ノード間で行う１対１通信の高速化だけでなく、３つ以上の計算ノード間で同時にデータをやりとりする集合通信の高速化が重要となる。集合通信には、例えば、次のようなものが存在する。
まず、集合通信には、データを複数の計算ノードに分配するマルチキャストやブロードキャスト（以下、この２つをマルチキャストとして表現する。）がある。また、集合通信には、各計算ノードにあるデータを、１つ又は複数の計算ノードに集め、かつ、演算も行うレデュース又はオールレデュースがある。さらに、集合通信には、１つの計算ノードにある異なるデータを、それぞれ別の計算ノードに配送するスキャタがある。そして、集合通信には、各計算ノードにある異なるデータを１つの計算ノードに集めるギャザがある。さらに、集合通信には、複数の計算ノード間で異なるデータをやり取りするオールトゥーオール（全交換）等がある。
なお、マルチキャストとレデュース（オールレデュース）、及び、スキャタとギャザは、演算を除く通信は逆過程であり、通信時間は同じである。
【０００４】
人工知能の１つであるディープラーニングの並列計算学習を例に、具体的に使われる集合通信を紹介する。ディープラーニングの並列計算を使った学習方法として、モデルパラレルとデータパラレルとの２つがある。モデルパラレルは、ニューラルネットワーク自体を分割するものである。そして、モデルパラレルは、それぞれ異なる計算ノード１０１で計算を行う。モデルパラレルは、各ニューラルネットワークの層毎に、演算結果をオールギャザする。そして、モデルパラレルは、各計算ノードで演算結果を共有する。
一方、データパラレルは、入力する複数のデータを分割するものである。データパラレルは、複数の計算ノード１０１で同一のニューラルネットワークの計算を行う。この場合、ニューラルネットワークのパラメータを最適化するために、データパラレルでは、パラメータの変化分をギャザやレデュースで１つの計算ノードに集める。そして、データパラレルは、パラメータ自体を複数の計算ノードにマルチキャストする。
【０００５】
一般に、各計算ノード１０１と電気スイッチ１０３間とのリンク１０２の帯域幅を増やすことで、通信時間を短くすることができる。しかし、一度に複数の通信を行う集合通信では、ネットワーク内で輻輳が発生し易くなる。また、一度に複数の通信を行う集合通信では、最悪、データの一部が損失してしまう。この場合、データを再送する必要がある。そして、データを再送する場合、データのやり取りでさらに時間がかかってしまう。そのため、リンク１０２の帯域幅を増やしても、集合通信は高速化されない。
【０００６】
集合通信の高速化方法として、図４６に示すように、ツリー構造で複数のステップに分けて順に通信を行うことで、輻輳を回避する方法がある。しかし、この方法では、通信回数の増加が問題となる。例えば、１回の通信における遅延がＬであると仮定すると、集合通信でＭ回の通信ステップが必要な場合、集合通信全体ではＭ×Ｌと大きな遅延が発生してしまう。図４６に示すように、既存の計算ノード１０１として、計算ノード１０１−１から１０１−Ｎ（図４６の場合、Ｎ＝８）のＮ台が繋がったツリー構造のネットワークでは、通信ステップ回数Ｍは少なくともｌｏｇ2Ｎに比例する。したがって、この通信ステップ回数Ｍによる遅延の増加は無視できない。なお、リング型やトーラス型のネットワークの通信ステップ回数Ｍは、さらに大きい。
【０００７】
この問題に対し、ＩＢＭ（登録商標）らは、制御用に、通信回数が少ない低遅延なネットワークを別途用意する方法を提案している（特許文献１）。これは、データ通信用のネットワーク以外に、通信ステップ回数Ｍの小さい制御用の専用ネットワークを用意する方法である。具体的には、専用ネットワークを用いてメモリアクセス（リード／ライト）に関する指示書を事前に配布することとしている。これにより、より早くメッセージの受信に向けたメモリの準備が可能となる。その結果、通信の遅延が削減される。
さらに通信回数を削減する方法として、以下のような提案もされている。それは、例えば、すべての計算ノード間を直接繋ぐフルメッシュで接続する方法である。この方法では、集合通信を１回で実現することとしている。電気配線でフルメッシュ接続を実現する場合、配線数が非常に大きくなることが課題であった。しかし、周回性ＡＷＧ（Arrayed Waveguide Grating）を用いることで、少ない配線数でフルメッシュ接続を実現する方法が提案されている（特許文献２、特許文献３）。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許出願公開第２０１１／２７０９４２号明細書
【特許文献２】特許第３２９２８４３号公報
【特許文献３】米国特許第０９４０１７７４号明細書
【特許文献４】特許第３５６８８７８号公報
【非特許文献】
【０００９】
【非特許文献１】原田啓司、外３名，“スター型ＷＤＭシステムの開発”，［online］，平成１５年１０月，ＮＴＴ技術ジャーナル，［平成２９年５月２日検索］，インターネット＜URL：http://www.ntt.co.jp/journal/0310/files/jn200310046.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【００１０】
特許文献１に記載された技術は、複数のネットワークを用意する必要がある。そのため、ネットワークのコストが大きくなる。また、特許文献１に記載された技術は、複数のネットワークを同時に管理する必要がある。そのため、管理コストが大きくなる。特に、並列計算機システムでは、高速に並列処理する必要がある。そのため、ネットワーク間の高度な同期が必要である。しかし、この同期にかかる時間も、通信の遅延に付加されてしまう。
【００１１】
一方、特許文献２、特許文献３に記載されたフルメッシュ接続されたシステムにおける課題は、１対１通信の帯域が小さいことである。図４７に、Ｎ台の計算ノード３０１がフルメッシュ接続された並列計算機システム３００の例を示す（図４７の場合、Ｎ＝８）。それぞれの計算ノード３００−ｘ（ｘは１以上の整数）からは、Ｎ−１本の双方向リンク３０２が出ている。このＮ−１本の双方向リンク３０２は、それぞれ異なる計算ノード３０１に接続される。例えば、１リンクの一方向あたりの帯域が２０Ｇｂｐｓの場合、１つの計算ノード３０１から出る総帯域は１４０Ｇｂｐｓと大きくなる。しかし、各計算ノード３０１間のリンクの帯域は、僅か２０Ｇｂｐｓと小さい。
【００１２】
通常のネットワークを用いた通信は、データに付加される送信先のアドレス情報に基づいて、経路が最短となる１つのリンクを使う。例えば、計算ノード１  ３０１−１から計算ノード５  ３０１−５へ１対１通信でメッセージを送ろうとした場合、ネットワークは計算ノード５  ３０１−５のアドレス情報に基づいてリンク３５１の１本だけを使用して通信する。その間、他の６本のリンク３５２から３５７は待機状態にある。したがって、リンクの利用効率が悪い。
ＮＴＴ（登録商標）らは、トラフィックが増加した場合に、超過した分のトラフィックを、別の経路に迂回する方法を提案している（特許文献４）。しかし、この方法は、帯域不足による輻輳が生じてから、迂回路を考慮したネットワークの再設計を行うものである。したがって、その再設計に多大な時間が必要である。そのため、並列計算には活用できない。
【００１３】
本発明は、上述した課題を鑑み、フルメッシュで接続された並列計算機システムにおいて、簡易な制御でありながら通信の利用効率を高くし、並列計算における通信時間を短縮するという課題を解決する並列計算機システム、並列計算機システムの制御方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本発明の並列計算機システムは、送信ノードと受信ノードとの間を直接接続する直接リンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクと、前記送信ノードから前記受信ノードへデータを転送する際、前記直接リンクのみを使用するリンクと、前記１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードと前記受信ノードとを接続するリンクを選定する通信制御手段と、を備える。
【００１５】
また、本発明の並列計算機システムの制御方法は、送信ノードと受信ノードとの間を直接接続する直接リンクのみを使用するリンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードから前記受信ノードへデータを転送する際、前記送信ノードと前記受信ノードとを接続するリンクを選定する工程を備える。
【００１６】
さらに、本発明のプログラムは、コンピュータに、送信ノードと受信ノードとの間を直接接続する直接リンクのみを使用するリンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードから前記受信ノードへデータを転送する際、前記送信ノードと前記受信ノードとを接続するリンクを選定する処理を実行させる。
【発明の効果】
【００１７】
本発明によれば、フルメッシュで接続された並列計算機システムにおいて、簡易な制御でありながら通信の利用効率を高くし、並列計算における通信時間を短縮することが可能な並列計算機システム、並列計算機システムの制御方法、及びプログラムを提供できる。
【図面の簡単な説明】
【００１８】
【図１】第１実施形態の並列計算機システムの構成の一例を示す模式図である。
【図２】第１実施形態の並列計算機システムでの１ホップリンクを用いた１対１通信の一例を示す模式図である。
【図３】第１実施形態の１対１通信における通信時間がデータサイズに依存する一例を示す図である。
【図４Ａ】第１実施形態の並列計算機システムのメインの計算ノードの制御フローの一例を示す図である。
【図４Ｂ】第１実施形態の提案並列計算機システムのその他の計算ノードの制御フローの一例を示す図である。
【図５】第２実施形態の並列計算機システムの構成の一例を示す模式図である。
【図６】第２実施形態の並列計算機システムでの１ホップリンクを用いた１対１通信の一例を示す模式図である。
【図７】第２実施形態の１対１通信における通信時間がデータサイズに依存する一例を示す図である。
【図８】第３実施形態の並列計算機システムの構成の一例を示す模式図である。
【図９】第３実施形態の分散スイッチと折り返し機能部の構成の一例を示す模式図である。
【図１０】第３実施形態の計算ノード間通信におけるパケット構成の一例を示す模式図である。
【図１１】第３実施形態のマルチキャスト通信における高速化手法の一例を示す図である。
【図１２】第３実施形態のマルチキャスト通信における分散スイッチ結線例の送信ノードの第１ステップについて説明する図である。
【図１３】第３実施形態のマルチキャスト通信における分散スイッチ結線例の送信ノードの第２ステップについて説明する図である。
【図１４】第３実施形態のマルチキャスト通信における分散スイッチ結線例の受信ノードの第１ステップについて説明する図である。
【図１５】第３実施形態のマルチキャスト通信における分散スイッチ結線例の受信ノードの第２ステップについて説明する図である。
【図１６】第３実施形態のマルチキャスト通信における通信時間がデータサイズに依存する一例を示す図である。
【図１７】第３実施形態の通信管理テーブルの一例を示す図である。
【図１８】第３実施形態のリンク管理テーブルの一例を示す図である。
【図１９】第３実施形態の通信制御フロー全体像の一例を示す図である。
【図２０】第３実施形態の新規通信発生時の通信制御フローの一例を示す図である。
【図２１】第３実施形態のリンク検証と通信開始の判断の制御フローの一例を示す図である。
【図２２】第３実施形態の通信管理テーブルの一例を示す図である。
【図２３】第３実施形態のリンク管理テーブルの一例を示す図である。
【図２４】第３実施形態の通信管理テーブルの一例を示す図である。
【図２５】第３実施形態のリンク管理テーブルの一例を示す図である。
【図２６】第３実施形態の通信完了時の通信制御フローの一例を示す図である。
【図２７】第３実施形態の通信管理テーブルの１つの通信が完了したときの一例を示す図である。
【図２８】第３実施形態のリンク管理テーブルの１つの通信が完了したときの一例を示す図である。
【図２９】第３実施形態の複数プログラム実行時のスキャタのデータの流れの一例を示す図である。
【図３０】第４実施形態の並列計算機システムの構成の一例を示す模式図である。
【図３１】第４実施形態の分散スイッチの構成の一例を示す模式図である。
【図３２Ａ】第４実施形態のレデュースのデータの流れの一例を示す図である。
【図３２Ｂ】第４実施形態のオールレデュースのデータの流れの一例を示す図である。
【図３３】第４実施形態のレデュースの最初の通信での分散スイッチのデータの流れの一例を示す図である。
【図３４】第４実施形態のレデュースの２回目の通信での分散スイッチのデータの流れの一例を示す図である。
【図３５】第４実施形態のレデュース又はオールレデュースにおける通信時間がデータサイズに依存性する一例を示す図である。
【図３６】第５実施形態の分散スイッチの構成の一例を示す模式図である。
【図３７】第５実施形態のレデュース又はオールレデュースにおける通信時間がデータサイズに依存する一例を示す図である。
【図３８】第６実施形態の１対１通信におけるデータの流れの一例を示す図である。
【図３９】第６実施形態のマルチキャスト通信におけるデータの流れの一例を示す図である。
【図４０】第６実施形態のマルチキャスト通信における通信時間がデータサイズに依存する一例を示す図である。
【図４１Ａ】第６実施形態のレデュースにおけるデータの流れの一例を示す図である。
【図４１Ｂ】第６実施形態のオールレデュースにおけるデータの流れの一例を示す図である。
【図４２】第６実施形態のリンク検証と通信開始の判断の制御フローの一例を示す図である。
【図４３】第７実施形態の並列計算機システムの構成の一例を示す模式図である。
【図４４】第８実施形態の並列計算機システムの構成の一例を示す模式図である。
【図４５】関連する並列計算機システムの構成例を示す図である。
【図４６】関連する並列計算機システムでの集合通信の高速化方法の例を示す図である。
【図４７】フルメッシュ接続された並列計算機システムの一例を示す模式図である。
【発明を実施するための形態】
【００１９】
（第１実施形態）
以下、図面を参照しながら本発明の第１の実施形態について詳しく説明する。
【００２０】
図１は、本発明の第１実施形態の並列計算機システム４００システムの構成の一例を示す模式図である。簡単のため、計算ノードの台数Ｎは４台とする。並列計算機システム４００において、Ｎ台の計算ノード４０１の各々が、複数の送受信器４０３と接続されている。また、並列計算機システム４００は、Ｎ台の計算ノード４０１の各々が、複数のケーブル４０２で直接繋がれたシステムである。そして、計算ノード４０１は、少なくともプロセッサ／メモリ４５１と、通信制御部４５２とを有する。
【００２１】
通信制御部４５２は、計算ノード４０１が１対１の通信を行うとき、使用するリンクを決定する機能を有する。ここで、直接リンクと１ホップリンクとについて説明する。直接リンクとは、異なる２つ以上の計算ノード間のデータの通信において、１つ以上の直接接続された計算ノード間のリンクである。また、１ホップリンクとは、１つ以上の１台の計算ノードを経由したリンクである。そして、通信制御部４５２は、異なる２つ以上の計算ノード間のデータの通信において、直接リンクのみを使用するリンクと、１ホップリンクのみを使用するリンクと、直接リンクと１ホップリンクとを組み合わせて使用するリンクとの中から、計算ノード間を接続するリンクを決定する機能を有する。
【００２２】
例えば、通信制御部４５２は、異なる２つ以上の計算ノード間のデータ通信において、計算ノード間で転送されるデータ量に応じて、使用するリンクを決定するようにしてもよい。すなわち、異なる２つ以上の計算ノード間で転送されるデータ量に応じて、直接リンクのみを使用するリンクと、１ホップリンクのみを使用するリンクと、直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、転送に要する時間が短いリンクを、計算ノード間を接続するリンクとして決定する。
また、通信制御部４５２は、異なる２つ以上の計算ノード間のデータの通信において、直接リンクと、１ホップリンクとの組み合わせの中から、通信時間が短くなる１つ以上のリンクからなるリンク群を選定する機能も有する。
【００２３】
例えば、計算ノード４０１−２から計算ノード４０１−４へ大容量（＞８０ｋｂｉｔ）のデータを送る場合、図２に示すように、通信制御部４５２は、直接リンク５００だけでなく、本来１対１通信とは関係しない計算ノード４０１−１、４０１−３を折り返しノードに設定する。そして、通信制御部４５２は、折り返しノードを経由する１ホップリンク５０１、５０２も使用する決定を行う。また、通信制御部４５２は、小容量（≦８０ｋｂｉｔ）のデータを送る場合、直接リンク５００のみを使用する決定を行う。なお、データサイズが大容量か小容量かを判断する基準は、通信制御部４５２が、事前に１対１通信のデータサイズと通信時間との関係を計測した上で決定する。
このように、本実施形態では、データのサイズに基づいて１ホップリンクを適用するかどうかを判断することとしている。これにより、データのサイズに依存することなく高速な並列計算機システムを提供することができる。
【００２４】
図３に、本実施形態での１対１通信の通信時間とデータサイズとの関係を示す。比較例のフルメッシュ接続された並列計算機システム３００（図４７）では、データサイズが大きいと、直接リンクの帯域に律速されデータ通信時間が長くなっている。しかし、本実施形態では、１ホップリンク５０１、５０２を最大（Ｎ−２）個活用することができる。その結果、直接リンクと合わせて（Ｎ−１）倍の広帯域化が可能である。これにより、本実施形態では、比較例よりもデータ通信時間を１／（Ｎ−１）に短縮できた。
【００２５】
なお、図１では、計算ノード４０１内の機能をブロックで示している。しかしながら、各機能部は、個別のデバイス又はチップである必要はない。例えば、通信制御部４５２は、プロセッサ／メモリ４５１のチップの中にあっても良い。
また、プロセッサ／メモリ４５１は、周知の構成を適用することが可能である。例えば、プロセッサ／メモリ４５１は、複数の大容量ＤＤＲ４  ＳＤＲＡＭ（Double-Data-Rate4 Synchronous Dynamic Random Access Memory）メモリが接続されたＩｎｔｅｌ（登録商標）のＸＥＯＮ（登録商標）などのプロセッサとすることができる。あるいは、より多くの演算コアが搭載されたＸＥＯＮ  Ｐｈｉなどのプロセッサとすることもできる。さらには、Ｉｎｔｅｌのプロセッサに接続された、ＨＢＭ（High Bandwidth Memory）などの広帯域Ｉ／Ｏ（Input/Output）で接続された広帯域メモリを有するＧＰＧＰＵ（General‐Purpose computing on Graphics Processing Units）プロセッサとすることもできる。プロセッサ／メモリ４５１として、如何なる構成を採用したとしても、本発明を限定するものではない。
以上説明したように、本実施形態によれば、フルメッシュで接続された並列計算機システムにおいて、１ホップリンクを活用したリンクの広帯域化が可能となる。その結果、通信時間が短縮されるという効果が得られる。
【００２６】
（第１実施形態の制御方法）
本実施形態では、瞬時に未使用のリンクを選定することができるように、計算ノード４０１−１の１台をメインの計算ノードとしている。そして、本実施形態では、計算ノード４０１のプロセッサ／メモリ４５１が、すべての計算ノード４０１間の通信と、リンクの使用状況とを管理している。図４Ａに、メインの計算ノード４０１−１の制御フローの一例を示す。図４Ｂに、その他の計算ノード４０１の制御フローの一例を示す。
【００２７】
（フロー：Ｆ０１）
まず、メインの計算ノード４０１−１の動作について説明する。図４Ａにおいて、メインの計算ノード４０１−１は、プロセッサ／メモリ４５１において動作する並列計算プログラムを実行する。並列計算プログラム実行中に計算ノード４０１間の通信が必要となったとき、プロセッサ／メモリ４５１は、通信制御部４５２にその通信の内容を提示する。そして、通信制御部４５２はその通信の内容を確認する。
【００２８】
（フロー：Ｆ０２）
メインの計算ノード４０１−１の通信制御部４５２は、実施する通信の内容とリンクの使用状況とに基づいて、通信に使用するリンク群（以下、通信リンク群という。）を選定する。通信リンク群の選定として、通信制御部４５２は、先ず、直接リンクを選定する。
次に、１対１の通信の場合、通信制御部４５２は、送信ノードからのリンクと受信ノードへのリンクとが未使用な計算ノード４０１を折り返しノードとする。そして、通信制御部４５２は、その折り返しノードを経由する送信ノードから受信ノードへのリンクを１ホップリンクとする。このように、通信制御部４５２は、利用できる１つ以上の１ホップリンクを選定する。
直接リンクと１ホップリンクとの何れか一方しか使えない場合、通信制御部４５２は、その使用可能なリンクを通信リンク群に選定する。一方、直接リンクと１ホップリンクとが両方使える場合、通信制御部４５２は、通信リンク群を以下のように選定する。直接リンクのみでの通信時間が、直接リンクと１ホップリンクとの両方を使って通信するときの通信時間よりも短い場合、通信制御部４５２は、直接リンクのみを通信リンク群に選定する。直接リンクのみでの通信時間が、直接リンクと１ホップリンクとの両方を使って通信するときの通信時間よりも長い場合、通信制御部４５２は、直接リンクと１ホップリンクとの両方を通信リンク群に選定する。
【００２９】
（フロー：Ｆ０３）
その後、メインの計算ノード４０１−１の通信制御部４５２は、通信リンク群を使って通信をするための通信指示書を作成する。通信制御部４５２は、作成した通信指示書をその他の計算ノード４０１に送付する。メインの計算ノード４０１−１が送付する通信指示書に記載された通信リンク群は他の通信で使用中の可能性もある。したがって、この通信指示書を送付する場合には専用のヘッダを用意する。そして、通信指示書を送付する通信方式は、他の通信よりも優先する方式とする。次に、その他の計算ノード４０１の動作について説明する。図４Ｂにおいて、通信指示書を受信するその他の計算ノード４０１の通信制御部４５２は、この専用のヘッダを確認すると、優先して通信指示書の動作を実行する（フロー：Ｆ０４）。なお、計算ノード４０１はフルメッシュ接続である。ここで、フルメッシュ接続とは、計算ノード４０１が、光ファイバを介して、上記した直接リンクを用いて個別にすべて接続された状態をいう。したがって、メインの計算ノード４０１−１は、一度にすべての計算ノード４０１に対して通信指示書を送付できる。さらに、通信指示書は、各計算ノード４０１で使用するリンクに関する指示だけでよい。したがって、通信指示書のデータサイズは、送受のリンク数である２Ｎ程度と小さい。そのため、通信指示書の送付に要する時間は短い。また、通信指示書の送付が与えるデータ通信への時間軸上の影響は無視できる。
【００３０】
（フロー：Ｆ０４、Ｆ０５）
メインの計算ノード４０１−１以外の他の計算ノード４０１の通信制御部４５２は、メインの計算ノード４０１−１から送付された通信指示書を受信する。そして、他の計算ノード４０１の通信制御部４５２は、使用するリンクを確認する。さらに、他の計算ノード４０１の通信制御部４５２は、自身に対して発せられた通信指示と併せてプロセッサ／メモリ４５１を設定する。このようにして、他の計算ノード４０１の通信制御部４５２は、通信の準備を行う。
【００３１】
（フロー：Ｆ０６）
その後、メインの計算ノード４０１−１及びその他の計算ノード４０１は、通信の準備が完了後、通信指示書にしたがった計算ノード間の通信を実施する。
【００３２】
このように、フロー：Ｆ０１からフロー:Ｆ０６に記載の各フローを実行することで、Ｎ台の計算ノード４０１がフルメッシュで接続された並列計算機システムにおいて、１ホップリンクを活用するシステムを提供することができる。この並列計算機システム４００では、折り返しノードの数Ｋを、１≦Ｋ≦Ｎ−２まで設定することができる。本実施形態では、図３に示すように、直接リンクと合わせて、１対１通信の帯域幅を最大Ｎ−１倍まで向上できる。なお、本実施形態では、通信指示書を送付する際に専用のヘッダを用意するものとして説明を行っている。しかしながら、通信指示書を送付する方式は、他の方式であっても良い。例えば、通信指示書を送付するメインの計算ノード４０１−１が、並列計算を行う方式を採用するようにしても良い。これにより、専用のヘッダを用意する必要が無くなる。その結果、通信指示書の送付時間のさらなる削減が可能になる。
【００３３】
（第２実施形態）
以下、図面を参照しながら本発明の第２実施形態について詳しく説明する。
【００３４】
図５は、本発明の第２実施形態の並列計算機システム８００の構成の一例を示す模式図である。簡単のため、計算ノードの台数Ｎは４台で示す。第２実施形態の並列計算機システム８００の第１実施形態と異なる点は、各計算ノード８０１が、分散スイッチ８５３と折り返し機能部８５４とを有する点である。
【００３５】
図６に、第２実施形態において１ホップリンクを使用した１対１通信のときのデータの流れを示す。第１実施形態と同様に、第２実施形態においても、直接リンク９００だけでなく、本来１対１通信とは関係しない計算ノード８０１−１、８０１−３を折り返す１ホップリンク９０１、９０２も通信リンク群として使用する。この折り返しは、新たに追加した分散スイッチ８５３と折り返し機能部８５４とを用いてデータを折り返すこととしている。このデータの折り返しは、プロセッサ／メモリ８５１の外部で行っている。したがって、通信の負荷が、プロセッサ／メモリ８５１で行われる計算に与える影響を最小限に抑えることができる。さらに、データの折り返しは、プロセッサ／メモリ８５１のメモリを介さないで行っている。したがって、１ホップリンクでの遅延時間を２．１μｓｅｃまで削減することができる。
なお、第１実施形態のように１ホップリンクでメモリを介する場合、直接リンクと比較して２回分の遅延時間が加わる。その結果、４μｓｅｃの遅延が生じる。本実施形態の１ホップリンクではメモリを介していない。図７に示すように、第１実施形態ではデータサイズが８０ｋｂｉｔ以上でないと１ホップリンク適用の効果（データ転送時間の短縮化）を得ることができなかった。これに対して、本実施形態では、データサイズがより小さい２０ｋｂｉｔ以上であってもデータ転送時間の短縮化を図ることができる。すなわち、小さいデータサイズであっても十分通信時間を短くすることができる。そのため、データサイズに依存することなく１ホップリンクを活用して通信を行うようにしても良い。
以上説明したように、本実施形態によれば、演算などを行うプロセッサ／メモリを介すことなく、１ホップリンクを活用した遅延の小さい通信を実現することができる。
【００３６】
（第３実施形態）
以下、図面を参照しながら本発明の第３実施形態について詳しく説明する。
【００３７】
図８は、本発明の第３実施形態の並列計算機システム１１００の構成の一例を示す模式図である。簡単のため、計算ノード数Ｎは４としている。本実施形態は、すべての計算ノード１１０１が、同じプログラムが動作しながら並列計算を行うＭＰＩ（Message Passing Interface）を使用する方式としている。ＭＰＩとは、並列コンピューティングを利用するための標準化された規格である。また、ＭＰＩとは、１つの計算ノードにおけるインターフェースに関する規格である。なお、ＭＰＩ以外に、他の周知の構成を適用することも可能であり、如何なる構成を採用したとしても、本発明を限定するものではない。
【００３８】
並列計算機システム１１００は、計算ノード１１０１間を接続する送受信器として、λ１、λ２、λ３といった波長が異なる光送受信器１１０３−１、１１０３−２、１１０３−３を有する。さらに、並列計算機システム１１００は、複数の波長の光信号を波長多重するＡＷＧ１１０２−１を有する。また、並列計算機システム１１００は、複数の波長の光信号を波長多重するＡＷＧ１１０２−１を接続する周回性ＡＷＧ１１０２−３を有する。そして、並列計算機システム１１００は、ＡＷＧ１１０２−１と周回性ＡＷＧ１１０２−３との間を接続する光ファイバ１１０２−２を有する。
【００３９】
光送受信器１１０３の波長は、特許文献１から特許文献３、及び非特許文献１に開示されているように、周回性ＡＷＧ１１０２−３のルーティング特性に合わせて決定される。そして、各計算ノード１１０１間をフルメッシュ接続している。図４７に示した関連するフルメッシュ接続の計算機システム３００では、光ファイバは約Ｎ2本必要である。そのため、Ｎが大きいほど光ファイバの本数が非常に多くなる。その結果、ネットワークの構築コストが莫大となっていた。これに対して、本実施形態の並列計算機システム１１００では、光ファイバ１１０２−２の本数を２Ｎ本に抑えることができる。その結果、ネットワーク構築コストを大幅に削減することができる。なお、周回性ＡＷＧ１１０２−３は、ポート数を４０×４０まで容易に拡張することが可能である。したがって、本実施形態でも、計算ノード数Ｎを４０台まで対応することが可能である。なお、特許文献３に開示されている方式を採用することで、Ｎを８０台、１２０台と拡大することができる。
このように、本実施形態では、計算ノードを、周回性ＡＷＧに対してＡＷＧと光ファイバとを介して接続する構成としている。これにより、計算ノードがフルメッシュで接続された並列計算機システムよりも光ファイバの本数を削減することが可能になる。さらに、配線コストを低減することができる。
【００４０】
また、並列計算機システム１１００は、通信制御部１１５２と分散スイッチ１１５３とを１つの集積素子上に搭載している。そして、通信制御部１１５２から分散スイッチ１１５３を直接、かつ、高速に制御できる構造としている。さらに、通信制御部１１５２内にメモリを有している。このメモリは、並列計算機システム１１００で発生する通信を管理する通信管理テーブル１１５５と、計算ノード間を繋ぐ全リンクを管理するためのリンク管理テーブル１１５６とを格納する。通信制御部１１５２は、これらの管理テーブルに高速にアクセスする。そして、通信制御部１１５２は、分散スイッチ１１５３を使用したリンクの選定を行う。本実施形態では、数１０ナノ秒といった高速なリンクの選定動作を実現できた。
このように、本実施形態によれば、通信制御部１１５２が、分散スイッチ１１５３と、通信管理テーブル１１５５と、リンク管理テーブル１１５６とに高速にアクセスすることができる。これにより、瞬時にリンクの選定と設定とを行うことができる。
【００４１】
なお、プロセッサ／メモリ１１５１と分散スイッチ１１５３との間は、共通バスで接続している。また、共通バスのポートは、接続される計算ノード数と同じＮ−１個用意している。これにより、他のＮ−１個の計算ノード１１０１間で、独立にリンク制御を行うことができる。さらに、他のＮ−１個の計算ノード１１０１間で、メモリを介した高速なメッセージのやり取りを実現することができる。なお、プロセッサ／メモリ１１５１と分散スイッチ１１５３とを、プロセッサ−分散スイッチ１１５３を組み合わせたものと、メモリ−分散スイッチ１１５３を組み合わせたものとを、それぞれ独立のバスで接続しても良い。この場合、後述する分散スイッチ１１５３内に用意されるクロスバースイッチのスイッチ規模が大きくなる。しかしながら、バスの制御が不要となるため、通信の遅延を小さくすることができる。
【００４２】
図９に分散スイッチ１１５３と折り返し機能部１１５４との構成の一例を示す。
【００４３】
折り返し機能部１１５４は、ポート１１５４−１と、分配器１１５４−２と、Ｎ個の出力ポート１１５４−Ｎとを有する。ポート１１５４−１は、分散スイッチ１１５３から信号を入力する。分配器１１５４−２は、入力された信号をＮ分配する（図９の場合、Ｎ＝４）。出力ポート１１５４−Ｎは、再び分散スイッチ１１５３にデータを戻す。
Ｎ個の出力ポート１１５４−Ｎのうち、Ｎ−１個の出力ポート１１５４−３は、他の計算ノード１１０１にデータを送信するためのものである。残りの１個の出力ポート１１５４−４は、自計算ノード１１０１にデータを戻すためのものである。これにより、メモリの書き換えなしで、高速に、複数のデータを同時に折り返す機能を実現している。
【００４４】
分散スイッチ１１５３は、送信用クロスバースイッチ１２０１と、受信用クロスバースイッチ１２０２との、２つのクロスバースイッチを有する。
【００４５】
送信用クロスバースイッチ１２０１の入力ポートのうち、Ｎ−１個の入力ポート１２０１−１は、プロセッサ／メモリ１１５１と接続する。残りのＮ−１個の入力ポート１２０１−２は、折り返し機能部１１５４の出力ポートであるＮ−１個の出力ポート１１５４−３と接続する。そして、送信用クロスバースイッチ１２０１の出力ポートのうち、Ｎ−１個の出力ポート１２０１−３は、外部の計算ノード１１０１と接続する光送受信器１１０３の送信機と接続する。そして、１個の出力ポート１２０１−４は、受信用クロスバースイッチ１２０２の入力ポートの１つである１２０２−１と接続する。受信用クロスバースイッチ１２０２のその他の入力ポートのうち１個の入力ポート１２０２−２は、折り返し機能部１１５４の出力ポート１１５４−４と接続する。そして、受信用クロスバースイッチ１２０２の残りのＮ−１個の入力ポート１２０２−３は、外部のＮ−１台の計算ノード１１０１と接続するＮ−１台の光送受信器１１０３の受信機と接続する。受信用クロスバースイッチ１２０２のＮ−１個の出力ポート１２０２−４は、プロセッサ／メモリ１１５１と接続する。受信用クロスバースイッチ１２０２の残りの１個の出力ポート１２０２−５は、折り返し機能部１１５４の入力ポート１１５４−１と接続する。
【００４６】
通信制御部１１５２（図８）は、計算ノード１１０１間の通信が必要なデータに対して、適切なサイズにパケット化する。また、通信制御部１１５２は、計算ノード１１０１間通信用の制御信号を付加する機能と、それを読み込む機能とを有する。制御信号を付加する機能と制御信号を読み込む機能とを実現するため、送信用クロスバースイッチ１２０１の入力ポート１２０１−１のプロセッサ／メモリ１１５１に対向する側には、バッファＡを配置している。また、受信用クロスバースイッチ１２０２の入力ポート１２０２−３の計算ノード１１０１に対向する側には、バッファＢを配置している。
図１０に、計算ノード１１０１間通信用の制御信号の構成の一例を示す。計算ノード１１０１間通信において付加する制御信号は、図１０に示すように、通信管理番号１３０１と、ステップ番号１３０２と、リンク管理情報１３０３と、送信プロセスＩＤ番号１３０４とを有する。なお、図１０のペイロード内に、必要なメッセージなどのデータを入力する。また、図１０のＦＣＳ（フレームチェックシーケンス）は、データの誤り検出及び訂正に用いるためのものである。図１０に示す制御信号は、計算ノード１１０１が最初にプロセッサ／メモリ１１５１からデータを取り出すときにのみ付加する形態とする。そして、この制御信号は、計算ノード１１０１において１ホップリンクで折り返すときにも変更しないこととしている。これにより、１ホップリンクを用いた折り返しに基づいて発生する遅延を最小限に抑えることとしている。
【００４７】
図１０に示す通信管理番号１３０１は、通信制御部１１５２（図８）が通信管理テーブル１１５５で管理する番号の１つである。この番号を用いることで、計算ノード１１０１と、通信の種類、送信ノード、受信ノード等の情報とが紐付けされる。通信管理番号１３０１は、番号管理を行うため１０ビット分用意し、１０２４個までの通信を管理できるようにしている。通信管理番号１３０１を１０ビット分用意しているのは、数十の計算ノード１１０１を有する並列計算機システム１１００で同時に発生する通信数は、精々数百程度であるからである。
【００４８】
図１０に示すステップ番号１３０２は、送信するデータが、１ホップリンクを用いた折り返しにおいて、ホップ前の通信データなのか、ホップ後の通信データなのかを判別するためのものである。ステップ番号１３０２として、１ビット分用意している。
【００４９】
図１０に示すリンク管理情報１３０３は、自計算ノード１１０１が接続しているすべての送信リンクの稼働状況を示すものである。リンク管理情報１３０３として、送信リンクが未使用であるか稼動中であるかを示す１ビットのデータ（未使用：０、稼働中：１）を使用する。各計算ノード１１０１は、他の計算ノード１１０１から得たリンク管理情報１３０３と、自計算ノード１１０１のリンク管理情報１３０３とを、リンク管理テーブル１１５６に常時反映させる。
本実施形態では、自計算ノード１１０１から得た送信リンクの稼働状況といった少ない情報のみで、すべての計算ノード１１０１は、すべての送信リンクを常時把握することができる。例えば、３２台の計算ノード１１０１が１本ずつフルメッシュ接続された並列計算機システムでは、総リンク数である約１０００本の稼働状況を、１通信あたり３１ビットといった少ないリンク管理情報１３０２を用いることで管理することができる。
通常の分散型のシステムでは、並列計算プログラムによっては、他の計算ノードが設定した通信に基づいて輻輳が発生し、大きな遅延が発生する場合がある。これに対して、本実施形態の送信リンク管理を用いれば、輻輳のない低遅延な通信システムを実現することができる。本実施形態の管理方法は、複数の並列計算プログラムが同時に動作する場合においても適用することができる。
【００５０】
図１０に示す送信プロセスＩＤ番号１３０４は、ＭＰＩ通信で規定されるパラメータである。送信プロセスＩＤ番号１３０４は、受信側で、そのデータが必要とするデータか否かを確認するための番号である。本実施形態では単精度で扱うものとし、３２ビット分用意している。
【００５１】
図１０に示すパケットのサイズは、通常の電気スイッチを用いた信号の通過時間よりも短い時間として、約５０ナノ秒とした。本実施形態では、関連する並列計算機システム（図４５）において計算ノードの間に設けられていた電気スイッチ１０３をなくしている。この電気スイッチを用いた信号の通過時間よりも短い時間で、すべてのリンクの使用状況を把握できるようにしている。これにより、リンクを管理することで生じる遅延時間は、電気スイッチを使用したシステムと同等にすることができた。また、本実施形態では、追加される制御信号の情報量は１００ビットと小さい。したがって、各計算ノード間のリンクの通信速度が２５Ｇｂｐｓである場合であっても、図１０に示すパケットにおける制御信号の割合は１０％以下に小さくすることができる。
このように、本実施形態では、すべてのリンクの使用状況を容易に判別することとしている。これにより、他の通信においてリンクが使用されているため通信を行うことができないといった輻輳の生じないネットワークを実現することができる。
【００５２】
また、通信制御部１１５２には、付加された制御信号の組み合わせに応じたクロスバースイッチ１２０１、１２０２の状態を事前に登録する図示しない経路管理テーブルも用意している。経路管理テーブルを用いることで、瞬時に、クロスバースイッチ１２０１、１２０２の設定を反映することができる。
【００５３】
図１１に、計算ノード１  １１０１−１を送信ノードとし、すべての計算ノード１１０１−１、２、３、４を折り返しノードと受信ノードとの双方に設定したときの、大きなデータをマルチキャストする場合のデータの流れを示す。計算ノード１  １１０１−１は、自計算ノード１１０１−１から自計算ノード１１０１−１へデータ１を送った上でデータを折り返すこととしている。すなわち、計算ノード１  １１０１−１を折り返しノードとしている。データの流れは、以下の（１）から（５）の各ステップとなる。
（１）送信ノードでデータをＫ分割する。本実施形態では、Ｋ＝４である。図１１の場合、送信ノード１１０１−１は、データを、データ１からデータ４に分割する。
（２）送信ノードからすべての折り返しノードへ、分割されたデータ（以下、分割データという。）が個別に送信される。図１１の場合、送信ノード１１０１−１から折り返しノード１１０１−２に対してデータ２が送信される。送信ノード１１０１−１から折り返しノード１１０１−３に対してデータ３が送信される。送信ノード１１０１−１から折り返しノード１１０１−４に対してデータ４が送信される。そして、各折り返しノードにおいて、送信ノード１１０１−１から送信された分割データを受信する。
（３）各折り返しノード（計算ノード）の分散スイッチ１１５３は、分割データをプロセッサ／メモリ１１５１に送信する。分散スイッチ１１５３は、分割データを複製する。各折り返しノードがＮ台にマルチキャストする場合、分割データを複製する数は、送信ノードと自計算ノードとの２台分を引いたＮ−２個とする。計算ノード１  １１０１−１だけは、送信ノードと自計算ノードとが同一であるため、分割データを複製する数は、Ｎ−１個となる。
（４）各折り返しノードは、複製した分割データを、送信ノードと自計算ノード以外の他の受信ノードへ再送信する。図１１の場合、折り返しノード１１０１−２は、受信ノード１１０１−３に対してデータ２を送信する。折り返しノード１１０１−２は、受信ノード１１０１−４に対してデータ２を送信する。折り返しノード１１０１−３は、受信ノード２に対してデータ３を送信する。折り返しノード１１０１−３は、受信ノード４に対してデータ３を送信する。折り返しノード１１０１−４は、受信ノード２に対してデータ４を送信する。折り返しノード１１０１−４は、受信ノード３に対してデータ４を送信する。一方、他の受信ノードでは、そのデータを受信する。
（５）各受信ノードでは、受信したデータをプロセッサ／メモリ１１５１に送信する。
【００５４】
上記各ステップ（１）から（５）における分散スイッチ１１５３の状態を、送信ノード１１０１−１と、受信ノード１１０１−２、１１０１−３、１１０１−４とに分けて具体的に説明する。
【００５５】
まず、送信（計算）ノード１１０１−１の分散スイッチ１１５３の状態について説明する。図１２に、上記（１）から（２）の各ステップにおける状態を示す。送信用クロスバースイッチ１２０１は、プロセッサ／メモリ１１５１から受信したデータを、各受信（折り返し）ノード１１０１に送信するため、光送受信器１１０３の送信器に接続するように設定される。そして、Ｎ分割したデータのうち、Ｎ−１個を別個に各受信ノード１１０１に送信する。例えば、データ２は、計算ノード２  １１０１−２に送信し、データ３は、計算ノード３  １１０１−３に送信する。この動作はスキャタと同様である。そして、ステップ（２）が終了した後、次のステップ（３）に向けて、送信用クロスバースイッチ１２０１は、図１３に示すように設定される。プロセッサ／メモリ１１５１から、未だ送信していないデータ１をマルチキャストで送信する。そのため、結線１６０１を使用して、一度、受信用クロスバースイッチ１２０２に送信した後、結線１６０２を使用して、折り返し機能部１１５４に送信する。折り返し機能部１１５４においてデータを複製する。そして折り返し機能部１１５４は、複製したデータを、それぞれ結線１６０３を使用して各受信ノード１１０１−２、１１０１−３、１１０１−４へ送信する。
【００５６】
次に、受信（計算）ノード１１０１−２、１１０１−３、１１０１−４の分散スイッチ１１５３の状態について説明する。図１４に、上記（２）から（４）の各ステップにおける状態を示す。図１４は、送信ノード１１０１−１と光送受信器１１０３−１とが接続されている状態を示している。光送受信器１１０３−１から入力した信号は、結線１７０１を使用して折り返し機能部１１５４に入力する。折り返し機能部１１５４に入力した信号は複製される。その後、結線１７０２を使用して別の計算ノードと接続された光送受信器１１０３−２、１１０３−３に送信されて折り返される。このとき、折り返し機能部１１５４で複製されたデータの１つは、再度受信用クロスバースイッチ１２０２に入り、結線１７０３を介してプロセッサ／メモリ１１５１に送られる。
【００５７】
次に、（５）のステップでの分散スイッチ１１５３の状態を図１５に示す。送信ノード１１０１−１から入力したデータ１は、結線１８０１でプロセッサ／メモリ１１５１に受信される。また、１ホップリンクして入ってくる光送受信器１１０３−２、１１０３−３から入力したデータは、結線１８０２で直接プロセッサ／メモリ１１５１に受信される。なお、（２）から（４）と（５）のデータの経路の切り替えは、通信制御部１１５２が、図１０に示した制御信号におけるステップ番号１３０２の違いに基づいて判別して切り替える。これにより、通信制御部１１５２は、瞬時に（２）の通信が終了したことを判断し、分散スイッチ１１５３の設定を遅延なく変更できる。
本実施形態では、図４７に示した関連するフルメッシュ接続時の遅延時間（２μｓｅｃ）と略同じ遅延時間を実現することができる。したがって、より小さいメッセージサイズで通信時間の高速化を実現することができた（遅延時間は２.１μｓｅｃ以内）。
このように、本実施形態では、１ホップリンクの折り返し時に、データの複製を行うこととしている。これにより、遅延が小さい１ホップリンクを実現することができる。さらに、マルチキャストやレデュースのさらなる通信時間の削減が可能になる。
【００５８】
図１６に、本実施形態でのマルチキャスト通信におけるデータ転送時間とデータ転送量との関係の一例を示したものである。図１６に示すように、第１実施形態ではデータサイズが８０ｋｂｉｔ以上でないと１ホップリンク適用の効果（データ転送時間の短縮化）を得ることができなかった。これに対して、本実施形態では、送信ノードを含めた折り返しノードの数Ｋが最大値であるＮのとき、１ホップリンクを活用することで、データサイズの大きいマルチキャスト通信の通信時間を約２／Ｎ倍に短縮できた。さらに、遅延を小さく抑えることで、Ｎ＝８でデータ転送量４ｋｂｉｔと小さいデータサイズでも通信時間の短縮を実現できた。
【００５９】
（第３実施形態の制御方法）
本実施形態では、各計算ノードで、同じ並列計算プログラムを同時に実行する制御方法を実装した。本実施形態の制御方法を実現する上で、通信管理テーブル１１５５と、リンク管理テーブル１１５６とを通信制御部１１５２内に用意することとしている。そして、通信制御部１１５２から通信管理テーブル１１５５とリンク管理テーブル１１５６とに対して高速にアクセスできるようにした。
【００６０】
図１７に通信管理テーブル１１５５の一例を示す。このテーブルは、実際に稼働している計算ノード１１０１間の通信の状況を管理するものである。管理するパラメータは、通信管理番号１１５５−０と、ＭＰＩ通信のプログラムで各通信の記述に使われるパラメータと、通信状態１１５５−１０とである。本実施形態で管理するＭＰＩ通信関連のパラメータは、通信種類１１５５−１と、送信ノード１１５５−２と、受信ノード１１５５−３と、コミュニケータ１１５５−４と、送信アドレス１１５５−５と、受信アドレス１１５５−６と、データ個数１１５５−７と、データ精度１１５５−８と、ＩＤ番号１１５５−９とである。また、通信状態１１５５−１０は、通信中か、待機かを管理する。なお、コミュニケータ１１５５−４は、事前に設定される計算ノード１１０１の組み合わせの定数である。例えば、ＭＰＩ＿ＣＯＭＭ＿ＷＯＲＬＤ（以下、ＷＯＲＬＤと表記する。）は、プログラムの開始時に走る全プロセス（全計算ノード）からなるグループである。
【００６１】
新規に通信を追加するときは、通信管理テーブル１１５５の行の末尾にその通信内容を追加する。通信が終了したとき、その追加した行を削除する。そして、削除した行の下に記載されていた通信内容の行を上に詰めていく方式としている。これにより、通信が発生した順序を、通信管理テーブル１１５５の行で管理することができる。また、通信の発生に伴うパラメータの数を低減することができる。
【００６２】
また、１対１通信に関しては、通信方式を分けて管理するのでなく、１つの通信として通信管理テーブル１１５５上の１行で管理することとしている。ＭＰＩ通信の１対１通信には、データの送受信を保証できるブロッキング方式や、ユーザ自身がデータの送受信を保証する必要のあるノンブロッキング方式など複数の方式がある。この方式の違いは、リンクが占有されるという点で共通している。したがって、通信管理テーブル１１５５上で区分する必要はない。これにより、通信管理テーブル１１５５上の通信種類１１５５−１のパラメータ数を低減することができる。さらに、管理する通信の数を低減することができる。その結果、高速な制御を実現することができる。
このように、本実施形態では、ＭＰＩを一例とする並列コンピューティング利用するための標準化された規格においても、すべてのリンクの使用状況を、少ない制御データのやり取りに基づいて容易に判別することができる。これにより、通信の遅延を小さくできる。
【００６３】
図１８に、リンク管理テーブル１１５６の一例を示す。このテーブルは、送信ノード１１５６−１と、受信ノード１１５６−２と、利用状況１１５６−３と、１ホップ経由ノード１１５６−４との４つの項目を有する。送信ノード１１５６−１と受信ノード１１５６−２とには、すべての組み合わせを用意している。これにより、すべてのリンクを管理することとしている。そして、利用状況１１５６−３には、通信で使用中の場合、図１７の通信管理テーブル１１５５上の通信管理番号１１５５−０を記録することとしている。また、１ホップリンクを高速に選択することができるように、各リンクが、さらに１ホップ追加したときに接続できる１ホップ経由ノード１１５６−４を、予めリンク管理テーブル１１５６上に用意している。なお、図１８のリンク管理テーブル１１５６上の利用状況１１５６−３の中に、１ホップリンクか直接リンクかについてカッコの中に記載している。しかしながら、利用状況１１５６−３には、図１７の通信管理テーブル１１５５の通信管理番号１１５５−０が記録されているので、このカッコ書きはなくてもよい。
【００６４】
図１９に、本実施形態の制御フローを示す。ステップＳ１９１の処理において、プロセッサ／メモリ１１５１は、計算ノード１１０１発生したイベントを確認する。ステップ１９２の処理において、プロセッサ／メモリ１１５１は、並列計算プログラム実行中に新規通信が発生した、又は通信が完了したかどうかを判断する。プロセッサ／メモリ１１５１が、新規通信が発生したと判断すると、ステップＳ１９３の処理へ移行する。プロセッサ／メモリ１１５１が、通信が完了したと判断すると、ステップＳ１９４の処理へ移行する。
【００６５】
ステップＳ１９３の処理において、並列計算プログラム実行中に新規にメッセージ通信が発生した場合、通信制御部１１５２は、新規通信発生イベントを実行する。ステップＳ１９４の処理において、並列計算プログラム実行中に新規のメッセージ通信が完了（終了）した場合、通信制御部１１５２は、通信完了イベントを実行する。なお、ステップＳ１９３の処理、又はステップＳ１９４の処理は、並列計算プログラムを実行するすべての計算ノード１１０１が行う。また、この２つのイベントが発生した場合にのみ、通信制御部１１５２を動作させるようにすればよい。この２つのイベントが発生しないその他の状態では、通信制御部１１５２を低消費電力状態で待機させるようにしている。これにより、実効的な消費電力量を削減することができる。
このように、本実施形態では、新規通信発生イベントが発生した場合、又は通信完了イベントが発生した場合にのみ、通信制御部１１５２を動作させ、このイベントが発生しない他の状態では、通信制御部１１５２を低消費電力状態で待機させるようにしている。これにより、通信制御部１１５２を常時稼働する必要がない。その結果、通信制御部１１５２を低消費電力で待機させることができる。
【００６６】
図２０に、図１９のステップＳ１９３における、新規通信発生イベントの制御フローを示す。まず、初めに、ステップＳ２０１の処理において、通信制御部１１５２は、通信管理テーブル１１５５の更新を行う。通信制御部１１５２は、プロセッサ／メモリ１１５１から入力される新規通信に関する指示を、通信管理テーブル１１５５の最後尾の行（以下、この行をＸ行目とする。）に書き込む。これにより、通信管理テーブル１１５５の最後尾（Ｘ行目）に項目が追加される。
【００６７】
次に、ステップＳ２０２の処理において、通信制御部１１５２は、通信状態の確認を行う。通信制御部１１５２は、通信管理テーブル１１５５のＸ−１行目に記載されている通信状態１１５５−１０を確認する。ステップＳ２０３の処理において、通信制御部１１５２は、通信管理テーブル１１５５の通信状態１１５５−１０が、通信中であるか待機中であるかを確認する。
通信制御部１１５２が、通信状態１１５５−１０が待機中であることを確認すると、ステップＳ２１０の処理、すなわち、待機中のフローへ移行する。待機中のフローでは、ステップＳ２１０の処理において、通信制御部１１５２は、通信管理テーブル１１５５の通信状態１１５５−１０を待機に変更する。そして処理を終了する。
一方、通信制御部１１５２が、通信状態１１５５−１０が通信中であることを確認すると、ステップＳ２０４の処理、すなわち、リンク検証と通信開始の判断のフローへ移行する。なお、通信制御部１１５２が、他に通信が無いことを確認した場合、すなわち、新規に発生した通信以外に他の通信がないことを確認した場合（Ｘ＝１の場合）も、ステップＳ２０４の処理へ移行する。
【００６８】
図２１に、図２０のステップＳ２０４におけるリンク検証と通信開始の判断の制御フローを示す。この制御は、通信管理テーブル１１５５のＸ行目の通信に対して実行する。
まず、ステップＳ２１１の処理において、通信制御部１１５２は、直接リンクの選定を行う。通信制御部１１５２は、通信管理テーブル１１５５の、送信ノード１１５５−２と受信ノード１１５５−３とに記載されている計算ノードを、直接接続されるリンクとして選定する。集合通信の場合、通信管理テーブル１１５５の送信ノード１１５５−２と受信ノード１１５５−３とには、コミュニケータが指定されている。この場合、通信制御部１１５２は、コミュニケータに含まれるすべてのノードをリンクとして選定する。
【００６９】
次に、ステップＳ２１２の処理において、通信制御部１１５２は、通信種類の確認を行う。ステップＳ２１３の処理において、通信制御部１１５２は、通信種類が１対１通信とマルチキャスト通信であるか、その他の通信であるかを確認する。通信制御部１１５２が、通信種類がその他の通信、すなわち、１対１通信とマルチキャスト通信以外の通信であることを確認すると、ステップＳ２１９の処理へ移行する。すなわち、通信制御部１１５２は、通信種類が１対１通信とマルチキャスト通信以外の通信に対しては、特に何も行わない。通信種類が、１対１通信とマルチキャスト通信以外の通信である場合、後述するステップＳ２１９の通信リンク群の選定の処理へ移行する。一方、通信制御部１１５２が、通信種類が１対１通信とマルチキャスト通信であることを確認すると、ステップＳ２１４の１ホップリンクの選定の処理へ移行する。
【００７０】
ステップＳ２１４の処理において、通信制御部１１５２は、１ホップリンクの選定を行う。まず、通信制御部１１５２は、通信管理テーブル１１５５の送信ノード１１５５−２と同じリンクを、リンク管理テーブル１１５６の送信ノード１１５６−１の中から抽出する。通信制御部１１５２は、その中から、リンク管理テーブル１１５６の１ホップ経由ノード１１５６−４の中に、通信管理テーブル１１５５の受信ノード１１５５−３と同じノードが含まれるリンクを選定する。そして、通信制御部１１５２は、その選定したリンクを、１ホップリンクの最初のステップのリンク（１ｈｏｐ１ｓｔ）とする。通信制御部１１５２が、１ホップリンクの最初のステップのリンク（１ｈｏｐ１ｓｔ）として選定したリンクの受信ノードが、折り返しノードとなる。さらに、この折り返しノードが送信ノードとなり、かつ、通信管理テーブル１１５５の受信ノード１１５５−３と同じ受信ノードの組み合わせのリンクを、通信制御部１１５２は、次のステップのリンク（１ｈｏｐ２ｎｄ）として選定する。本実施形態では、折り返しノードの数Ｋは、最大になるすべての１ホップリンクを選定する。
【００７１】
次に、ステップＳ２１５の処理において、通信制御部１１５２は、１ホップリンクの利用判断を行う。これは、通信制御部１１５２が、実際に通信を行う通信リンク群として、直接リンクからなるリンク群を用いるか、１ホップリンクを含むリンク群を活用するかを判断する。この判断は、通信制御部１１５２が、通信時間を短縮できるか否かに基づいて判断する。本実施形態では、以下の簡易な計算式が成り立つときに、通信制御部１１５２は、１ホップリンクを含むリンク群を活用するものとする。
≪１対１通信≫
（データ個数）×（１データサイズ）＜（Ｋ−１）×Ｂ×（Ｔ1−Ｔ0）／（Ｋ−２）
≪マルチキャスト通信≫
（データ個数）×（１データサイズ）＜Ｋ×Ｂ×（Ｔ1−Ｔ0）／（Ｋ−２）
Ｋ：折り返しノードの数（１対１通信ではＮ−２、マルチキャスト通信ではＮ）
Ｂ：１リンクあたりの帯域幅
Ｔ1：１ホップリンクにおける遅延時間
Ｔ0：直接リンクにおける遅延時間
【００７２】
ここで、計算式の左辺はデータサイズである。（データ個数）と（１データサイズ）として、通信管理テーブル１１５５のデータ個数１１５７−７とデータ精度１１５５−８とを用いる。一方、計算式の右辺は、１ホップリンクを適用したときに増加する遅延時間で、どれだけのデータが遅れるかを示す近似値である。Ｂ、Ｔ1、Ｔ0は、並列計算機システムを構築したときに事前に評価した数値を用いた。なお、この≪マルチキャスト通信≫の計算式の関係は、レデュース又はオールレデュースに対しても適用することができる。また、本実施形態において、データサイズは、実際のデータを想定して記載している。しかしながら、データサイズは、８Ｂ１０Ｂのような符号化方式などでは、データサイズがより大きくなる場合がある。そのため、符号化方式などでデータが増える割合を考慮しても良い。
【００７３】
１ホップリンクの利用判断は、さらに計算式を簡略化して判断を高速にすることができる。例えば、本実施形態では、折り返しノードの数Ｋは、最大になるすべての１ホップリンクを選定することとしている。すなわち、Ｋは採り得る最大値としているため、上記計算式における（Ｋ−１）／（Ｋ−２）やＫ／（Ｋ−２）は略１となる。そこで、Ｋに依存しない以下の関係式で判断するようにしても良い。
（データ個数）×（データ精度）＜Ｂ×（Ｔ1−Ｔ0）
さらに、第１又は第２実施形態で説明したのと同様に、事前に、１ホップリンクの方が高速になるメッセージサイズを事前に見積もっておく。そして、そのメッセージサイズに基づいて、通信制御部１１５２が判断するようにしても良い。
【００７４】
次に、ステップＳ２１６の処理において、通信制御部１１５２は、１ホップリンクを利用するか利用しないかの判断を行う。通信制御部１１５２が１ホップリンクを利用すると判断した場合、ステップＳ２１８の処理へ移行する。ステップＳ２１８の処理において、通信制御部１１５２は、直接リンクと１ホップリンクとの両方を通信リンク群として選定する。一方、通信制御部１１５２が１ホップリンクを利用しないと判断した場合、ステップＳ２１７の処理へ移行する。ステップＳ２１７の処理において、通信制御部１１５２は、直接リンクのみを通信リンク群とする。なお、通信リンク群とは、実際に通信を行うリンクの集合体である。
【００７５】
また、上記したように、ステップＳ２１２の処理における通信種類の確認において、１対１通信とマルチキャスト通信以外の通信を確認した場合、ステップＳ２１９の処理において、通信制御部１１５２は、直接リンクのみを通信リンク群として選定する。
【００７６】
次に、ステップＳ２２０の処理において、通信制御部１１５２は、使用状況の確認を行う。通信制御部１１５２は、選定した通信リンク群のすべてのリンクの使用状況を、リンク管理テーブル１１５６の利用状況１１５６−３を用いて確認する。ステップＳ２２１の処理において、通信制御部１１５２は、利用状況がすべて未使用であるか使用中があるかを確認する。通信制御部１１５２は、利用状況がすべて未使用であることを確認すると、ステップＳ２２２の処理へ移行する。ステップＳ２２２の処理において、通信制御部１１５２は、通信開始Ｙｅｓを選定する。一方、通信制御部１１５２は、使用状況に１つでも使用中のリンクがあることを確認すると、ステップＳ２２３の処理へ移行する。ステップＳ２２３の処理において、通信制御部１１５２は、通信開始Ｎｏを選定する。そして、図２０のステップＳ２０４におけるリンク検証と通信開始の判断の制御フローを終了する。本制御方法を用いることで、使用できる折り返しノードの数が少ない場合、通信制御部１１５２は、そのノードを選択しないで済むことになる。したがって、データサイズの大きな通信に対して、常時高速な通信を提供することができる。
【００７７】
図２０のステップＳ２０４におけるリンク検証と通信開始の判断のフローに戻る。ステップＳ２０４の処理において、通信制御部１１５２が通信開始Ｙｅｓ（図２１のステップＳ２２２）を選定すると、ステップＳ２０６のリンク管理テーブル変更の処理へ移行する。具体的には、通信制御部１１５２は、リンク管理テーブル１１５６の利用状況１１５６−３に、通信管理テーブル１１５５の通信管理番号１１５５−０を記載する。その後、ステップＳ２０７の分散スイッチ変更の処理へ移行する。ここで、通信制御部１１５２は、通信リンク群を用いた通信を行うことができるように分散スイッチ１１５３の設定を行う。その後、ステップＳ２０８の処理へ移行する。ここで、通信制御部１１５２は、通信開始の処理を実行する。その後、ステップＳ２０９の処理へ移行する。ここで、通信制御部１１５２は、通信管理テーブルの変更を実行する。具体的には、通信制御部１１５２は、通信管理テーブル１１５５のＸ行目の通信状態１１５５−１０を通信中に変更する。
【００７８】
一方、ステップＳ２０５の処理において、通信制御部１１５２が通信開始Ｎｏ（図２１のステップＳ２２３）を選定すると、ステップＳ２１０の処理へ移行する。ここで、通信制御部１１５２は、通信管理テーブルの変更を実行する。具体的には、通信制御部１１５２は、通信管理テーブル１１５５のＸ行目の通信状態１１５５−１０を待機に変更する。
【００７９】
例えば、以下の３つの通信がほぼ同時に順番に発生した場合の本実施形態の制御フローを用いた管理テーブルの変化を以下に示す。
通信Ａ：計算ノード１から計算ノード２への１対１通信（データ個数：５０００）
通信Ｂ：計算ノード１からＷＯＲＬＤへのスキャタ（データ個数：５０００）
通信Ｃ：計算ノード３からＷＯＲＬＤへのマルチキャスト通信（データ個数：５０）
【００８０】
通信Ａは、他に通信が無い状態で新規に発生する通信である。そのため、通信Ａは、図２０のステップＳ２０４におけるリンク検証と通信開始の判断のフローを行った上で通信が行われる。また、データ個数が多いため、図２１のステップＳ２１５の処理における１ホップリンクの利用判断のフローにおいて、通信制御部１１５２は、次のような判断を行う。すなわち、通信制御部１１５２は、ステップＳ２１６の処理において、１ホップリンクを利用すると判断する。そして、ステップＳ２１８の処理において、通信制御部１１５２は、通信リンク群を選定する。その結果、通信制御部１１５２は、図１７に示す通信管理テーブル１１５５と、図１８に示すリンク管理テーブル１１５６の（リンク名）１−２とに記載された形式で通信を管理する。
【００８１】
次に、通信Ａの直後に通信Ｂが発生した場合を考える。通信Ｂが発生した場合、直前の通信Ａは通信中である。したがって、通信Ｂは、図２０のステップＳ２０４におけるリンク検証と通信開始の判断のフローを行った上で通信が行われる。図２１のステップＳ２１５の処理における１ホップリンクの利用判断のフローにおいて、通信制御部１１５２は、次のような判断を行う。すなわち、通信制御部１１５２は、ステップＳ２１６の処理において、１ホップリンクを利用しないと判断する。そして、ステップＳ２１７の処理において、通信制御部１１５２は、直接リンクのみを通信リンク群として選定する。これは、通信種類がスキャタであることに基づくものである。通信制御部１１５２が選定した直接リンクは、通信Ａで使用されていない。したがって、通信Ｂに対して直接リンクを利用することが可能である。そのため、通信制御部１１５２は、ステップＳ２２０の処理における使用状況の確認において、使用状況がすべて未使用であることを確認する。そして、ステップＳ２２２の処理へ移行し、通信Ｂは通信開始Ｙｅｓとなる。その結果、通信制御部１１５２は、図２２に示す通信管理テーブル１１５５と、図２３に示すリンク管理テーブル１１５６の（リンク名）２−１、２−３、２−４とに記載された形式で通信を管理する。
【００８２】
次に、通信Ｂの直後に通信Ｃが発生した場合を考える。通信Ｃが発生した場合、直前の通信Ｂは通信中である。したがって、通信Ｃは、図２０のステップＳ２０４におけるリンク検証と通信開始の判断のフローを行った上で通信が行われる。図２１のステップＳ２１５の処理における１ホップリンクの利用判断のフローにおいて、通信制御部１１５２は、次のような判断を行う。すなわち、通信制御部１１５２は、ステップＳ２１６の処理において、１ホップリンクを利用すると判断する。そして、ステップＳ２１８の処理において、通信制御部１１５２は、１ホップリンクを通信リンク群として選定する。これは、通信種類がマルチキャスト通信であることに基づくものである。ただし、通信Ｃのデータ個数は５０と小さい。したがって、通信制御部１１５２は、図２５のリンク管理テーブル１１５６に示すように、計算ノード３が送信ノード（１１５６−１）となる３つの直接リンクを通信リンク群として選定する。しかしながら、この３つの直接リンクの中で、計算ノード２が受信ノード（１１５６−２）となるリンクは通信Ａが使用中である。このため、本実施形態では通信Ｃは待機となる。その結果、通信制御部１１５２は、図２４に示す通信管理テーブル１１５５と、図２５に示すリンク管理テーブル１１５６の（リンク名）３−１、３−２、３−４とに記載された形式で通信を管理する。
【００８３】
次に、図２６に示す通信が終了した場合の制御フローについて説明する。通信が終了すると、図１０で説明した制御信号のリンク管理情報１３０３に基づいて、すべての計算ノード１１０１は、通信が終了したことを認識する。その後、ステップＳ２６１の処理において、各計算ノード１１０１は、通信管理テーブル１１５５から終了した通信を削除する。そして、各計算ノード１１０１は、通信管理テーブル１１５５から削除した通信の下に記載されている通信を上段にシフトする。
【００８４】
その後、ステップＳ２６２の処理において、通信制御部１１５２は、通信管理テーブル１１５５の最上段に記載されている（通信順の最も小さい）待機状態の通信を選択する。そして、通信制御部１１５２は、ステップＳ２６３のリンク検証と通信開始の判断の処理を実行する。ステップＳ２６４の処理において、通信制御部１１５２は、通信を開始するか否かを判断する。ステップＳ２６４の処理において、通信制御部１１５２が、通信開始Ｙｅｓと判断した場合、ステップＳ２６５の処理へ移行する。ステップＳ２６５の処理では、図２０で説明したステップＳ２０６の処理と同様に、通信制御部１１５２は、リンク管理テーブル１１５６を変更した上で通信を開始する。ステップＳ２６３の処理におけるリンク検証と通信開始の判断のフローは、待機状態（ステップＳ２７１）へ移行するか、その他の待機状態にある通信の開始状態（ステップＳ２６５）へ移行するかを繰り返し実行する。
【００８５】
図２６のステップＳ２６６からステップＳ２６８の処理及びステップＳ２７１の処理は、図２０において説明したステップＳ２０７からステップＳ２０９の処理及びステップＳ２１０の処理と同様であるので、詳細な説明を省略する。図２６のステップＳ２６９の処理において、通信制御部１１５２は、待機状態の確認を行う。ステップＳ２７０の処理において、通信制御部１１５２は、待機状態であるか否かを判断する。通信制御部１１５２が、待機状態である（ステップＳ２７０：Ｙｅｓ）と判断すると、ステップＳ２６２の処理へ移行する。通信制御部１１５２が、待機状態でない（ステップＳ２７０：Ｎｏ）と判断すると、処理を終了する。
【００８６】
例えば、通信管理テーブル１１５５が図２４に示す状態にあり、リンク管理テーブル１１５６が図２５に示す状態にある場合に、通信Ａが終了したときの通信管理テーブル１１５５の状態を図２７に示す。また、通信Ａが終了したときにリンク管理テーブル１１５６の状態を図２８に示す。通信Ａが終了するため、通信Ｃで使用する計算ノード３が送信ノード（１１５６−１）となる３つの直接リンク（３−１、３−２、３−４）がすべて利用可能になる。そのため、待機状態にあった通信Ｃが開始され、次のイベントが発生するまで待機状態となる。
【００８７】
並列計算プログラムは逐次方式で記載されている。したがって、通信の優先順位は時間順になる。本実施形態の制御方法では、通信制御部１１５２は、通信管理テーブル１１５５の上段に記載されている通信から優先的に通信の可否を判断する。したがって、優先順位の高い通信を実行することができる。
【００８８】
なお、本実施形態では、１ホップリンクの活用を、１対１通信とマルチキャスト通信との２つのみを例に挙げて説明した。これに対して、２つ以上のアプリケーションを、異なる計算ノードのグループ間で実施する場合、他のクループ内の通信に対しても同じ制御フローを適用することができる。例えば、２つのグループＡ、Ｂに対して計算ノード１１０１を分けた状態で、１つのグループに対してスキャタを適用した場合のデータの流れを図２９に示す。グループＡは、計算ノード１  １１０１−１、計算ノード２  １１０１−２、計算ノード３  １１０１−３、計算ノード４  １１０１−４を有する。グループＢは、計算ノード５  １１０１−５、計算ノード６  １１０１−６、計算ノード７  １１０１−７、計算ノード８  １１０１−８を有する。
【００８９】
グループＡとグループＢとを独立したグループに分けて並列計算を行う場合について説明する。図２９は、計算ノード１  １１０１−１にあるデータ２−１、データ２−２を計算ノード２  １１０１−２へ、データ３−１、データ３−２を計算ノード３  １１０１−３へ、データ４−１、データ４−２を計算ノード４  １１０１−４へ送るスキャタの結果である。
【００９０】
各グループ間において１ホップリンクも独立して行うこととしている。そのため、図２９に示すように、各ノードへの通信として、１ホップリンクと直接リンクとの２本を利用することとしている。そのため、メッセージサイズの大きいスキャタでは、２倍の高速化を実現することができる。
このように、本実施形態では、複数の並列計算プログラムを同時に実行させた状態であっても、リンクの使用状況を管理することとしている。これにより、１ホップリンクによる通信時間を削減することができる。さらに、１ホップリンクをスキャタ、ギャザなどの集合通信にも適用させている。これにより、通信時間を削減することができる。
【００９１】
（第４実施形態）
以下、図面を参照しながら本発明の第４実施形態について詳しく説明する。
【００９２】
図３０は、本発明の第４実施形態の並列計算機システム２５００の構成の一例を示す模式図である。簡単のため、計算ノードの台数Ｎは４台で示す。第４実施形態の並列計算機システム２５００の第３実施形態と異なる点は、各計算ノード２５０１の分散スイッチ２５５３に、図８に示した折り返し機能部１１５４を融合した点である。
【００９３】
図３１は、分散スイッチ２５５３の構成の一例を示す模式図である。第３実施形態と同様に、クロスバースイッチは、送信用クロスバースイッチ２６０１と、受信用クロスバースイッチ２６０２とを有する。ただし、送信用クロスバースイッチ２６０１の内部は、各入力ポートに１×（Ｎ−１）の分配部２６０３を、各出力ポートに（Ｎ−１）×１のスイッチ部２６０４を配置した構成としている。これにより、クロスバースイッチとしての動作だけでなく、任意のポートに入力されたデータを、複数のポートに出力する分配動作が可能となる。
【００９４】
折り返し機能を実現するため、まず、バッファＢの後段に、Ｎ−１個の１×Ｍの分配部２６０５と、Ｍ個の（Ｎ−１）×１のスイッチ部２６０６とを配置している。そして、分配部２６０５とスイッチ部２６０６とを互いに接続している。ただし、図３１の場合、Ｎ＝４、Ｍ＝２としている。そして、送信側のバッファＡの後段にも、（Ｎ−１）個のＭ×１のスイッチ部２６０７を配置している。そして、プロセッサ／メモリ２５５１から入力されるポートと、送信用クロスバースイッチ２６０１の１つのポートとを接続できる構成としている。送信用クロスバースイッチ２６０１の１つのポートは、Ｍ個の１ホップリンク用のスイッチ部２６０６を用いて選択することとしている。これにより、Ｍ個の１ホップリンクのための折り返しを実現している。
ここで、Ｍは、１ホップリンクを使用する通信を同時に実行する数である。Ｍを増加させることで１ホップリンクを実行する通信数を増加させることができる。その結果、ネットワークの利用効率を高くすることが可能になる。なお、上記した第３実施形態は、Ｍ＝１の場合である。
【００９５】
また、バッファＢの後段の１×Ｍの分配部２６０５の出力の中の１つを、受信用クロスバースイッチ２６０２に接続することとしている。これにより、上記した第３実施形態と同様に、送信するデータを、１ホップリンクを用いて折り返す場合と、自計算ノード２５０１へ格納する場合との両方を同時に実現している。
【００９６】
本実施形態の構成を用いることで、第３実施形態の分散スイッチ１１５３と折り返し機能部１１５４との両方の機能を実現することができた。これにより、第３実施形態で説明したマルチキャスト通信の高速化を、本実施形態においても実現することができる。
【００９７】
さらに、本実施形態では、レデュース、オールレデュースの高速化も実現している。この２つの集団通信は、第３実施形態のマルチキャスト通信とは逆過程の集団通信である。本実施形態のように、分散スイッチに折り返し機能を設けるだけで高速化を実現することができる。
このように、本実施形態では、１対１通信、マルチキャスト、レデュース、及びオールレデュースについて、１ホップリンクを使用して高速化を図ることができる。
【００９８】
図３２Ａは、すべての計算ノード１  ２５０１−１、計算ノード２  ２５０１−２、計算ノード３  ２５０１−３、計算ノード４  ２５０１−４が送信ノードとなり、１つの受信ノード１  ２５０１−１にデータを集めて演算するレデュースのデータの流れの一例を示す図である。
図３２Ｂは、すべての計算ノード１  ２５０１−１、計算ノード２  ２５０１−２、計算ノード３  ２５０１−３、計算ノード４  ２５０１−４が送信ノードと受信ノードとなり、すべての計算ノード計算ノード１  ２５０１−１、計算ノード２  ２５０１−２、計算ノード３  ２５０１−３、計算ノード４  ２５０１−４にデータを集めて演算するオールレデュースのデータの流れの一例を示す図である。
第３実施形態のマルチキャスト通信の場合と同様に、折り返しノードはすべての計算ノード２５０１としている。そして、折り返しノードの数Ｋは、計算ノード数Ｎ（＝４）とした。また、送信するデータは、各計算ノード２５０１の行に記載している。例えば、計算ノード１  ２５０１−１の初期状態の保有データは［１、３、５、７］であり、計算ノード２  ２５０１−２の初期データは［１、２、３、４］である。
【００９９】
レデュース又はオールレデュースにおける通信は、以下の（１）から（５）の各ステップの順となる。
（１）各計算ノード２５０１において、送信するデータを、同じ方法でＫ（＝Ｎ）分割する。
（２）各計算ノード２５０１において、分割されたデータ（以下、分割データという。）のそれぞれを、別々の折り返しノードへ向けて送信する。そして、各折り返しノードでは、各計算ノードから送信された分割データを受信する。このときの分散スイッチ２５５３の状態の一例を図３３に示す。
（３）各折り返しノードは、受信した分割データと、自計算ノード分として残されたデータとを用いて、各列のデータ毎にレデュースで指定された演算を行う。本実施形態では、和算の例を示している。そして、各折り返しノードは、演算結果を折り返す。
（４）レデュースの場合、各折り返しノードは、折り返した演算結果を、受信ノードに再送信する。オールレデュースの場合、演算結果を、自計算ノード以外のすべての受信ノードに再送信する。一方、受信ノードは、各折り返しノードから再送信されたデータを受信する。このときの分散スイッチ２５５３の状態の一例を図３４に示す。分散スイッチ２５５３の送信用クロスバースイッチ２６０１は分配動作を行う。送信用クロスバースイッチ２６０１は、演算結果を他の複数の受信ノードに送付する。
（５）受信ノードでは、受け取ったデータをプロセッサ／メモリ２５５１に送信する。
【０１００】
図３５は、本実施形態におけるレデュース又はオールレデュースを行ったときのデータ転送時間とデータ転送量との関係の一例を示したものである。データ転送量は、指定されたすべてのデータの容量である。マルチキャスト通信の場合と同様に、容量が大きいデータは、１／Ｎに小さくしたデータを２回に分けて通信する１ホップリンクを活用することができる。したがって、比較例よりも通信時間を約２／Ｎに短縮することができた。ただし、１ホップリンクの遅延に関しては、折り返しノードにおいて一度演算を行うため、プロセッサ／メモリ２５５１にデータを渡す必要がある。そのため、１ホップリンクでの遅延時間は、直接通信の場合と比較して約２倍の４μｓｅｃとなった。
このように、本実施形態によれば、レデュースの演算を高速に行うことができる。さらに、１ホップリンクにおいて、１回目の通信の後、直ちに２回目の演算結果の送信が可能になる。これにより、演算時間と通信時間との並列化に伴って生ずる演算時間と、演算に伴って生ずる遅延とを削減することができる。なお、ここで示したオールレデュースの通信手順と逆の手順を踏むことで、送信ノードが異なる複数のマルチキャストを同時に実行することも可能である。
【０１０１】
（第５実施形態）
以下、図面を参照しながら本発明の第５実施形態について詳しく説明する。
【０１０２】
図３６は、第５実施形態の分散スイッチの構成の一例を示す模式図である。本実施形態の並列計算機システムは、第４実施形態と同じ構成を有している。ただし、図３６に示すように、分散スイッチ３１５３の構成が第４実施形態と異なっている。具体的には、分散スイッチ３１５３の内部に、レデュース用の演算部３１８１を有している。
演算部３１８１は、第４実施形態の分散スイッチ２５５３内に配置されたスイッチ部２６０６の１つを置き換えたものである。演算部３１８１は、他の計算ノードからデータを同時に入力できる構成を有している。また、演算部３１８１は、自計算ノードで保有するデータも加えて演算を行う。したがって、自計算ノードのデータを入力するための結線３１８２と、計算結果を戻す結線３１８３とを追加している。さらに、計算結果を他の計算ノードに配布するための出力ポート３１８４を用意している。また、この演算部３１８１は、レデュースで指定される計算に特化した演算部である。したがって、演算部３１８は、高速に演算を実行することができる。ただし、この演算部３１８の構成は、本発明の本質的部分ではないので、詳細な説明は省略する。
【０１０３】
分散スイッチ３１５３にレデュースに特化した演算機能を設けたことに伴い、図示しない通信制御部は、容易に１ホップリンクにおける最初の通信と２回目の通信とを瞬時に切り替えることが可能になる。その結果、１ホップリンクでの遅延時間を２．４μｓｅｃと小さくすることができた。
図３７は、本実施形態におけるレデュース又はオールレデュースを行ったときのデータ転送時間とデータ転送量との関係の一例を示したものである。第４実施形態では、１ホップリンクを用いた通信時間の削減効果は、データ転送量が７０ｋｂｉｔ以上の場合に現れた。これに対して、本実施形態では、２０ｋｂｉｔといった小さいメッセージサイズでも通信時間の短縮を実現することができた。
【０１０４】
（第６実施形態）
以下、図面を参照しながら本発明の第６の実施形態について詳しく説明する。
【０１０５】
本実施形態の並列計算機システムは、上記した第１実施形態から第５実施形態と異なり、使用可能なリンクがある場合、そのリンクを使用して通信を行う制御方法を導入している。また、マルチキャスト通信の場合、送信ノードを折り返しノードに含めないこととしている。これにより、通信時間の短縮を実現している。したがって、１ホップリンクを活用するときの通信方法と、第３実施形態の図２０のステップＳ２０４で説明したリンク検証と通信開始の判断の処理、及び図２１の制御フローを変更している。
【０１０６】
（第６実施形態の通信手順）
まず、本実施形態における、１対１、マルチキャスト、レデュース、オールレデュースの各通信方法の手順と効果について説明する。通信方法の特徴は、使用可能なリンクがある場合、そのリンクを使用して通信を開始することができるようにすることである。具体的には、１ホップリンクでデータを折り返す計算ノード（折り返しノード）の数Ｋが上限値よりも小さい値であっても、通信を実行することができるようにしたことである。そして、折り返す計算ノード（折り返しノード）の数Ｋは、各通信方法において、以下のように定めている。１対１通信の場合、１≦Ｋ≦Ｎ−２、マルチキャスト通信の場合、１≦Ｋ≦Ｎ−１、レデュース又はオールレデュース通信の場合、１≦Ｋ≦Ｎとしている。ただし、Ｎは並列計算機システム内の計算ノードの数である。なお、上記した第１実施形態から第５実施形態では、折り返す計算ノード（折り返しノード）の数Ｋは、最大値の場合にのみ１ホップリンクを利用することができ、最大値以外では待機状態になっていた。
【０１０７】
図３８は、第６実施形態の１対１通信におけるデータの流れの一例を示す図である。具体的には、送信ノードが計算ノード１  ２５０１−１、受信ノードが計算ノード２  ２５０１−２であり、計算ノード３  ２５０１−３のみを折り返しノードとして使用する場合の１対１通信におけるデータの流れを示したものである。データの流れは、以下の（１）から（５）の各ステップとなる。
（１）送信ノード１  ２５０１−１においてデータを分割する。分割数は、直接リンクを使用することができる場合はＫ＋１となる。分割数は、直接リンクを使用することができない場合はＫとなる。本実施形態の場合、直接リンクを使用することができるため、２分割する。
（２）（スキャタ）送信ノード１  ２５０１−１から、受信ノード２  ２５０１−２と、Ｋ台の折り返しノード３  ２５０１−３とに対して、送信ノード１  ２５０１−１において分割されたデータ（以下、分割データという。）が個別に送信される。そして、受信ノード２  ２５０１−２と、折り返しノード３  ２５０１−３とにおいて、送信ノード１  ２５０１−１から送信された分割データを個別に受信する。
（３）受信ノード２  ２５０１−２は、受信したデータをそのまま図示しないプロセッサ／メモリに送信する。一方、折り返しノード３  ２５０１−３は、受信したデータを図示しない分散スイッチと折り返し機能部とを使用して折り返す。
（４）（ギャザ）折り返しノード３  ２５０１−３は、折り返したデータを受信ノード２  ２５０１−２へ再送信する。一方、受信ノード２  ２５０１−２は、Ｋ台の折り返しノード３  ２５０１−３から再送信されたデータを同時に受信する。
（５）受信ノード２  ２５０１−２は、受信したデータを図示しないプロセッサ／メモリへ送信する。
このデータの流れは、各計算ノード２５０１の通信制御部の指示の下実行される。本実施形態によれば、図４７に示した関連するフルメッシュ接続の場合よりも、１対１通信にかかる時間は１／Ｋ倍に短縮できた。
【０１０８】
なお、ステップ（２）で分割されたデータの送付先は、並列計算機システム全体で統一したルールに基づいて行っている。本実施形態では、分割されたデータ列のうち、列番号の小さい番号のデータ群ほど、計算ノード２５０１の番号の低い折り返しノードに送信することとしている。この統一されたルールに基づいて、ステップ（５）でデータを受信した受信ノード２  ２５０１−２は、各折り返しノードから受信したデータが、分割データのどの位置のデータであるかを判断することができる。その位置に応じて、受信ノード２  ２５０１−２は、プロセッサ／メモリにデータを送ることができる。この動作は、以下説明するマルチキャスト、レデュース、オールレデュース、及び上記説明した実施形態においても同様に行っている。
【０１０９】
図３９は、第６実施形態のマルチキャストにおけるデータの流れの一例を示す図である。具体的には、１台の送信ノード１  ２５０１−１から、送信ノード１  ２５０１−１を含むＸ台（１≦Ｘ≦Ｎ）の計算ノード２５０１にマルチキャストする場合であり、計算ノード２  ２５０１−２と計算ノード３  ２５０１−３とを折り返しノードとして使用する場合（Ｋ＝２）のデータの流れを示したものである。データの流れは、以下の（１）から（５）の各ステップとなる。図３９の場合、Ｎ＝４、Ｋ＝２、Ｘ＝４としている。
（１）送信ノード１  ２５０１−１においてデータを分割する。分割数は、データを折り返す折り返しノードの数Ｋである。本実施形態の場合、Ｋ＝２であり、２分割する。
（２）（スキャタ）送信ノード１  ２５０１−１からすべての折り返しノード２  ２５１０−２、折り返しノード３  ２５０１−３に対して分割されたデータ（以下、分割データという。）が個別に送信される。そして、各折り返しノード２  ２５０１−２、折り返しノード３  ２５０１−３において、送信ノード１  ２５０１−１から送信された分割データを受信する。
（３）各折り返しノード２  ２５０１−２、折り返しノード３  ２５０１−３は、受信した分割データを図示しないプロセッサ／メモリへ送る。折り返しノード２  ２５０１−２は、受信した分割データを、送信ノード１  ２５０１−１と自計算ノードとを除く受信ノード３  ２５０１−３、受信ノード４  ２５０１−４へ分配して折り返す。折り返しノード３  ２５０１−３は、受信した分割データを、送信ノード１  ２５０１−１と自計算ノードとを除く受信ノード２  ２５０１−２、受信ノード４  ２５０１−４へ分配して折り返す。
（４）（オールギャザ）各折り返しノード２  ２５０１−２は、折り返したデータを個別に、送信ノード１  ２５０１−２と自計算ノードを除く受信ノード３  ２５０１−３、受信ノード４  ２５０１−４とへ個別に再送信する。折り返しノード３  ２５０１−３は、折り返したデータを個別に、送信ノード１  ２５０１−２と自計算ノードを除く受信ノード２  ２５０１−２、受信ノード４  ２５０１−４とへ個別に再送信する。一方、送信ノード１  ２５０１−１を除く受信ノード２  ２５０１−２、受信ノード３  ２５０１−３、受信ノード４  ２５０１−４で、再送信されたデータを受信する。
（５）送信ノード１  ２５０１−１を除く受信ノード２  ２５０１−２、受信ノード３  ２５０１−３、受信ノード４  ２５０１−４は、受け取ったデータを図示しないプロセッサ／メモリに送信する。
このデータの流れは、各計算ノード２５０１の通信制御部の指示の下行われる。本実施形態によれば、図４７に示した関連するフルメッシュネットワークの場合よりも、通信時間は１／Ｋ倍に短縮できた。これは、上記した第３実施形態における方法よりも高い改善効果である。図４０は、本実施形態におけるマルチキャストを行ったときのデータ転送時間とデータ転送量との関係の一例を示したものである。図４０の場合、Ｎ＝８、Ｋ＝７としている。第３実施形態では、データサイズが大きいときの比較例からの改善効果は約１／４倍の短縮であったが、本実施形態では１／７倍まで短縮することができた。
【０１１０】
図４１Ａは、第６実施形態のレデュースにおけるデータの流れの一例を示す図である。具体的には、Ｙ台（１≦Ｙ≦Ｎ）の計算ノード１  ２５０１−１、計算ノード２  ２５０１−２、計算ノード３  ２５０１−３、計算ノード４  ２５０１−４が送信ノードとなり、１つの受信ノード２５０１−１にデータを集めて演算するレデュースのデータの流れを示したものである。
図４１Ｂは、第６実施形態のオールレデュースにおけるデータの流れの一例を示す図である。具体的には、Ｙ台（１≦Ｙ≦Ｎ）の計算ノード１  ２５０１−１、計算ノード２  ２５０１−２、計算ノード３  ２５０１−３、計算ノード４  ２５０１−４が送信ノードと受信ノードとなり、データを集めて演算するオールレデュースのデータの流れを示したものでる。データの流れは、以下の（１）から（５）の各ステップとなる。
なお、図４１Ａ、図４１Ｂ共に、計算ノード２  ２５０１−２と計算ノード３  ２５０１−３とが折り返しノードである場合の例である。データの流れは、以下の（１）から（５）の各ステップとなる。
（１）各計算ノード２５０１において、送信するデータを、同じ方法でＫ分割する。
（２）（オールトゥーオール（全交換））各計算ノード２５０１において、分割されたデータ（以下、分割データという。）が個別に折り返しノードへ向けて送信される。そして、各折り返しノードにおいて、各計算ノード２５０１から送信された分割データを個別に受信する。
（３）各折り返しノードは、集められたデータと自計算ノード分に残されたデータとを用いて、各列のデータ毎にレデュースで指定された演算を行う。本実施形態では和算の例を示している。そして、演算結果を、自計算ノードを除く受信ノードの数だけ折り返して分配する。
（４）（ギャザ、オールギャザ）レデュースの場合、各折り返しノードは、折り返した演算結果を受信ノードに再送信する。オールレデュースの場合、各折り返しノードは、折り返した演算結果を自計算ノード以外のすべての受信ノードに再送信する。一方、受信ノードではそのデータを個別に受信する。
（５）受信ノードでは、受け取ったデータを図示しないプロセッサ／メモリに送信する。
このデータの流れは、各計算ノード２５０１の通信制御部の指示の下行われる。本実施形態によれば、図４７に示した関連するフルメッシュネットワークの場合よりも、レデュースの通信にかかる時間はＫ／２倍に改善できた。
【０１１１】
（第６実施形態の制御フロー）
本実施形態では、第３実施形態の図２０に示した制御フローのうち、ステップＳ２０４のリンク検証と通信開始の判断の処理において行われる図２１に示す処理を変更している。図４２に、本実施形態の、リンク検証と通信開始の判断の制御フローを示す。
【０１１２】
まず、ステップＳ４２１の処理において、通信制御部１１５２は、通信種類の確認を行う。次に、通信制御部１１５２は、リンクの選定を行う。ただし、直接リンクの選定は、通信管理テーブル１１５５の送信ノード１１５５−２と受信ノード１１５５−３との組み合わせに基づいて選定することができる。したがって、第３実施形態と同様に、直接リンクの選定から行うようにしても良い。
【０１１３】
次に、通信制御部１１５２は、ステップＳ４２２の処理において、リンク利用状況の確認と直接リンクの選定を行う。通信制御部１１５２は、通信管理テーブル１１５５で管理されている送信ノード１１５５−２と受信ノード１１５５−３とが、直接結ばれる直接リンクをすべてピックアップする。その上で、通信制御部１１５２は、リンク管理テーブル１１５６も用いて利用状況を確認する。このとき、使用中のリンクが１つでも存在する場合、通信制御部１１５２は、リンクの選定を失敗したと判断する。
【０１１４】
次に、通信制御部１１５２は、ステップＳ４２３の処理において、リンク利用状況の確認と１ホップリンクの選定を行う。図４２の場合、先ず、ステップＳ４２１の通信種類の確認の処理において、通信制御部１１５２は、１対１通信、マルチキャスト通信、レデュース、及びオールレデュースについて選定を行う。また、通信制御部１１５２は、１ホップリンクでデータが折り返される折り返しノードを選定する。これにより、通信制御部１１５２は、その折り返しノードを経由する１ホップリンクについて選定を行う。その他の通信の場合、通信制御部１１５２は、リンクの選定を失敗したと判断する。この場合、通信制御部１１５２は、直接リンクのみで通信するかどうかを判断する。
【０１１５】
１対１通信における選定方法は、第３実施形態の場合と同様に、通信制御部１１５２は、リンク管理テーブル１１５６の１ホップ経由ノード１１５６−４を使用して、接続可能な１ホップリンクを特定する。その後、通信制御部１１５２は、リンク管理テーブル１１５６の利用状況１１５６−３に基づいて、１回目と２回目との両方のリンクが未使用である計算ノードを折り返しノードとして選定する。そして、通信制御部１１５２は、折り返しノードが関係するリンクを１ホップリンクとして選定する。
【０１１６】
マルチキャスト通信における選定方法は、第３実施形態の場合と同様に、通信制御部１１５２は、リンク管理テーブル１１５６の１ホップ経由ノード１１５６−４を使用して、接続可能な１ホップリンクを特定する。その後、通信制御部１１５２は、リンク管理テーブル１１５６の利用状況１１５６−３に基づいて、１回目の送信ノードからのリンクが未使用であり、かつ、２回目の送信ノードと自計算ノードを除くすべての受信ノードとのリンクが未使用な計算ノードを折り返しノードとして選定する。そして、通信制御部１１５２は、折り返しノードが関係するリンクを１ホップリンクとして選定する。
【０１１７】
レデュースにおける選定方法は、第３実施形態の場合と同様に、通信制御部１１５２は、リンク管理テーブル１１５６の１ホップ経由ノード１１５６−４を使用して、接続可能な１ホップリンクを特定する。その後、通信制御部１１５２は、リンク管理テーブル１１５６の利用状況１１５６−３に基づいて、１回目のすべての送信ノードからのリンクが未使用であり、かつ、２回目の受信ノードとのリンクも未使用な計算ノードを折り返しノードとして選定する。そして、通信制御部１１５２は、折り返しノードが関係するリンクを１ホップリンクとして選定する。
【０１１８】
オールレデュースにおける選定方法は、第３実施形態の場合と同様に、通信制御部１１５２は、リンク管理テーブル１１５６の１ホップ経由ノード１１５６−４を使用して、接続可能な１ホップリンクを特定する。その後、通信制御部１１５２は、リンク管理テーブル１１５６の利用状況１１５６−３に基づいて、１回目のすべての送信ノードからのリンクが未使用であり、かつ、２回目の自計算ノードを除くすべての受信ノードとのリンクも未使用な計算ノードを折り返しノードとして選定する。そして、通信制御部１１５２は、折り返しノードが関係するリンクを１ホップリンクとして選定する。
【０１１９】
その後、ステップＳ４２４の処理におけるリンクの選定結果にしたがって、３つの場合に分かれる。
【０１２０】
ステップＳ４２４の処理において、直接リンクと１ホップリンクとの両方の選定が失敗した場合、ステップＳ４２７の処理へ移行する。通信制御部１１５２は、通信開始Ｎｏを選択する。
【０１２１】
ステップＳ４２４の処理において、直接リンクと１ホップリンクとの何れか一方のみの選定が成功している場合、ステップＳ４２６の処理へ移行する。ステップＳ４２６の処理において、通信制御部１１５２は、選定に成功した方のリンクを、実際に通信を行う通信リンク群として選定する。そして、ステップＳ４３１の処理へ移行し、通信制御部１１５２は、通信開始Ｙｅｓを選択する。
【０１２２】
ステップＳ４２５の処理において、直接リンクと１ホップリンクとの両方の選定が成功している場合、ステップＳ４２５の処理へ移行する。ステップＳ４２５の処理において、通信制御部１１５２は、１ホップリンクの利用判断を行った上で、通信リンク群を選定する。ステップＳ４２５における１ホップリンクの利用判断の処理では、第３実施形態における図２１のステップＳ２１５の処理と同様に、以下の条件に基づいて１ホップリンクを利用するか利用しないかを判断する。
【０１２３】
≪１対１通信、マルチキャスト≫
（データ個数）×（１データサイズ）＜（Ｋ−１）×Ｂ×（Ｔ1−Ｔ0）／（Ｋ−２）
≪レデュース、オールレデュース≫
（データ個数）×（１データサイズ）＜Ｋ×Ｂ×（Ｔ1−Ｔ0）／（Ｋ−２）
Ｋ：折り返しノードの数
Ｂ：１リンクあたりの帯域幅
Ｔ1：１ホップリンクにおける遅延時間
Ｔ0：直接リンクにおける遅延時間
【０１２４】
そして、ステップＳ４２８の処理において、通信制御部１１５２が１ホップリンクを利用すると判断した場合、ステップＳ４２９の処理へ移行する。ステップＳ４２９の処理において、通信制御部１１５２は、直接リンクと１ホップリンクとの両方を通信に用いる通信リンク群として選定する。一方、ステップＳ４２８の処理において、１ホップリンクを利用しないと判断した場合、ステップＳ４３０の処理へ移行する。ステップＳ４３０の処理において、通信制御部１１５２は、直接リンクのみを通信リンク群として選定する。その後、ステップＳ４３１の処理へ移行する。ステップＳ４３１の処理において、通信制御部１１５２は、通信開始Ｙｅｓとする。そして、図４２に示すリンク検証と通信開始の判断の制御フローを終了する。
【０１２５】
本実施形態のリンク検証と通信開始の判断の制御フロー（図４２）と、第３実施形態で説明した制御フロー（図２１）とを組み合わせることで、通信を待機させることなく開始することができる。それは、直接リンクと１ホップリンクとにおいて使用することが可能なリンクがある場合に、特に顕著である。これにより、複数の通信が同時に多発するアプリケーションにおいて、通信の待機時間を減らすことができる。また、その結果、トータルの通信時間を削減することができる。
【０１２６】
人工知能の１つであるディープラーニングの学習などは、多くの計算ノード間の集合通信が定期的に起こるものである。このようなアプリケーションでは、第３実施形態で説明したように、１つの集合通信をできるだけ高効率に実行する方が通信時間を削減することができる。そこで、アプリケーションに応じて、第３実施形態で説明したようなＫを最大値で固定した制御と、本実施形態で説明したＫを可変にする制御とを切り替えることが好ましい。本実施形態の制御方法では、ステップＳ４２３におけるリンク利用状況の確認と１ホップリンクの選定において、Ｋの範囲を指定する機構を設けることとしている。その結果、様々なアプリケーションにおいて通信時間の短縮が可能な制御を実現することができる。
【０１２７】
（第７実施形態）
以下、図面を参照しながら本発明の第７実施形態について詳しく説明する。
【０１２８】
図４３は、第７実施形態の並列計算機システムの構成の一例を示す模式図である。本実施形態では、各計算ノード３８０１間の通信帯域を増やすため、分散スイッチ３８５３と折り返し機能部３８５４とを、計算ノード３８０１毎に２個用意している。そして、分散スイッチ３８５３と折り返し機能部３８５４との組合せの各々を、周回性ＡＷＧ３８０２−１と周回性ＡＷＧ３８０２−２とにそれぞれ接続している。また、図示しない通信制御部は１つだけ用意している。そして、１つの通信管理テーブルリンク３８５５とリンク管理テーブル３８５６とを用いて、同時に２つの分散スイッチ３８５３を制御することしている。これにより、通信制御部を増加することなく、並列計算機システム３８００の計算ノード３８０１間の通信時間の短縮を実現することができた。
【０１２９】
（第８実施形態）
以下、図面を参照しながら本発明の第８実施形態について詳しく説明する。
図４４は、第８実施形態の並列計算機システムの構成の一例を示す模式図である。本実施形態の並列計算機システム７００は、直接リンク７０１と、１ホップリンク７０２と、通信制御部７０３とを有する。
直接リンク７０１は、送信ノード７０４と受信ノード７０５との間を直接接続するリンクである。
１ホップリンク７０２は、送信ノード７０４と受信ノード７０５との間を、送信ノード７０４、受信ノード７０５以外の折り返しノード７０６を経由して接続するリンクである。
通信制御部７０３は、送信ノード７０４から受信ノード７０５へデータを転送する際、直接リンク７０１のみを使用するリンクと、１ホップリンク７０２のみを使用するリンクと、直接リンク７０１と１ホップリンク７０２とを組み合わせて使用するリンクとの中から、送信ノード７０４と受信ノード７０５とを接続するリンクを選定する。
【０１３０】
本実施形態では、通信制御部７０３が、送信ノード７０４から受信ノード７０５へデータを転送する際、直接リンク７０１のみを使用するリンクと、１ホップリンク７０２のみを使用するリンクと、直接リンク７０１と１ホップリンク７０２とを組み合わせて使用するリンクとの中から、送信ノード７０４と受信ノード７０５とを接続するリンクを選定する。これにより、フルメッシュで接続された並列計算機システムにおいて、簡易な制御でありながら通信の利用効率を高くし、並列計算における通信時間を短縮することができるのである。
【０１３１】
なお、並列計算機システムを構成する計算ノードのプロセッサ／メモリに格納されているコンピュータプログラムは、記録媒体で提供されてもよく、また、インターネット等のネットワークを介して提供されてもよい。記録媒体は、コンピュータ使用可能媒体又はコンピュータ可読媒体であって、磁気、光、電子、電磁気、赤外線などを用いて情報の記録又は読み取りが可能な媒体を含む。そのような媒体として、例えば、半導体メモリ、半導体または固体の記憶装置、磁気テープ、取外し可能なコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ（Random Access Memory））、読出し専用メモリ（ＲＯＭ（Read Only Memory））、磁気ディスク、光ディスク、光磁気ディスクなどがある。
【０１３２】
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。例えば、並列計算プログラムをコンパイルするときに、通信制御部が行う判定機能の一部を事前に決定しておくことで、通信の遅延をさらに小さくすることも可能である。
【０１３３】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
［付記１］
送信ノードと受信ノードとの間を直接接続する直接リンクと、
前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクと、
前記送信ノードから前記受信ノードへデータを転送する際、前記直接リンクのみを使用するリンクと、前記１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードと前記受信ノードとを接続するリンクを選定する通信制御手段と、
を備えた並列計算機システム。
［付記２］
前記通信制御手段は、前記直接リンクのみを使用するデータの転送において未使用のノードを前記折り返しノードとして選定する、付記１に記載の並列計算機システム。
［付記３］
前記折り返しノードは、前記送信ノードから送信されたデータを前記受信ノードへ転送する折り返し手段を備える、付記１又は２に記載の並列計算機システム。
［付記４］
並列計算プログラムを実行する制御手段をさらに備え、前記通信制御手段が、前記送信ノードと前記受信ノードとを接続するリンクとして前記１ホップリンクを選定するとき、前記折り返し手段は、前記制御手段を介すことなく、前記送信ノードから送信されたデータを前記受信ノードへ転送する、付記３に記載の並列計算機システム。
［付記５］
前記通信制御手段と前記折り返し手段とは、単一の集積素子に搭載されており、前記通信制御手段は前記折り返し手段を制御する、付記３又は４に記載の並列計算機システム。
［付記６］
前記通信制御手段は、前記送信ノードと前記受信ノードと間で転送されるデータ量に応じて、前記直接リンクのみを使用するリンクと、前記１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記転送に要する時間が短いリンクを、前記送信ノードと前記受信ノードとを接続するリンクとして選定する、付記１から５の何れか１項に記載の並列計算機システム。
［付記７］
前記送信ノード、前記受信ノード、及び前記折り返しノードのそれぞれは計算ノードであり、前記通信制御手段は、前記計算ノード間の通信の状況を管理する通信管理テーブルと、前記計算ノード間を繋ぐすべてのリンクの使用状況を管理するリンク管理テーブルとを格納する、付記１から６の何れか１項に記載の並列計算機システム。
［付記８］
少なくともＮ台（Ｎは３以上の整数）の前記計算ノードが、光ファイバを介して前記直接リンクを用いて個別にすべて接続されたフルメッシュ接続で構成され、前記通信制御手段は、前記通信管理テーブルに格納された前記計算ノード間の通信の状況と、前記リンク管理テーブルに格納された前記計算ノード間を繋ぐすべてのリンクの使用状況とに基づいて、前記通信が１対１通信の場合、１≦Ｋ≦Ｎ−２、マルチキャスト通信の場合、１≦Ｋ≦Ｎ、レデュース又はオールレデュース通信の場合、１≦Ｋ≦Ｎ、をそれぞれ満たすＫ台の折り返しノードを選定する、付記７に記載の並列計算機システム。
［付記９］
前記フルメッシュ接続されているＮ台の計算ノードのうち、１台の計算ノードをメインの計算ノードとし、前記メインの計算ノードの制御手段は、前記計算ノード間の通信の状況と、前記計算ノードを繋ぐすべてのリンクの使用状況とを管理する、付記８に記載の並列計算機システム。
［付記１０］
前記通信制御手段は、前記計算ノード間を繋ぐすべてのリンクの稼働状況を他の計算ノードから取得し、前記すべてのリンクの稼働状況を把握する、付記７に記載の並列計算機システム。
［付記１１］
前記並列計算プログラムの実行中に、前記計算ノード間に新規な通信が発生した状態又は前記計算ノード間の通信が完了した状態で、前記通信制御手段は動作状態に移行し、前記計算ノード間に新規な通信が発生した状態又は前記計算ノード間の通信が完了した状態以外の状態で、前記通信制御手段は待機状態に移行する、付記７に記載の並列計算機システム。
［付記１２］
前記計算ノードは、周回性ＡＷＧ（Arrayed Waveguide Grating）に対して、ＡＷＧと光ファイバとを介して接続される、付記７に記載の並列計算機システム。
［付記１３］
前記計算ノードを複数のグループに分け、前記複数グループの各々において前記並列計算プログラムを実行するとき、前記通信制御手段は、自グループ内の計算ノードを経由する直接リンクと、他グループ内の計算ノードを経由する１ホップリンクとを、前記リンクとして選定する、付記７に記載の並列計算機システム。
［付記１４］
送信ノードと受信ノードとの間を直接接続する直接リンクのみを使用するリンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードから前記受信ノードへデータを転送する際、前記送信ノードと前記受信ノードとを接続するリンクを選定する工程を備えた並列計算機システムの制御方法。
［付記１５］
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、１台の送信ノードから他の１台の受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いた１対１通信を行うとき、通信リンクとしてＫ台（１≦Ｋ≦Ｎ−２）の折り返しノードを経由するＫ個の１ホップリンクと、Ｌ台（Ｌ＝０又は１）の前記送信ノードと前記受信ノードとの間を直接接続する直接リンクとを用い、各計算ノードは通信制御手段の指示の下、
（１）前記送信ノードで、通信するデータを（Ｋ＋Ｌ）で分割する工程と、
（２）前記送信ノードで、分割した（Ｋ＋Ｌ）個のデータをＫ台の折り返しノードとＬ台の受信ノードとに個別に送信する工程と、各前記Ｋ台の折り返しノードと前記Ｌ台の受信ノードで、前記分割した（Ｋ＋Ｌ）個のデータの１つを、個別に受信する工程と、
（３）各前記Ｋ台の折り返しノードで、受信したデータを折り返す工程と、前記Ｌ台の受信ノードで、受信したデータをそのまま並列計算プログラムを実行する制御手段へ送る工程と、
（４）各前記Ｋ台の折り返しノードで、折り返されたデータを前記受信ノードへ再送信する工程と、前記Ｋ台の折り返しノードから再送信されたデータを、前記受信ノードで受信する工程と、
（５）前記受信ノードで、受信したデータを前記制御手段に送る工程と、
を備える、並列計算機システムの制御方法。
［付記１６］
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、１台の送信ノードから、前記送信ノードを含むＸ台（１≦Ｘ≦Ｎ）の受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いてマルチキャスト通信を行うとき、通信リンクとして、前記送信ノードを含まないＫ台（１≦Ｋ≦Ｎ−１）の折り返しノードを経由する１ホップリンクを用い、各計算ノードは通信制御手段の指示の下、
（１）前記送信ノードで、通信するデータをＫで分割する工程と、
（２）前記送信ノードで、分割したＫ個のデータをＫ台の折り返しノードに個別に送信する工程と、前記Ｋ台の折り返しノードで、前記分割したＫ個のデータの１つを、個別に受信する工程と、
（３）前記Ｋ台の折り返しノードで、受信したデータを、並列計算プログラムを実行する制御手段へ送ると共に、受信したデータを、前記送信ノードと自計算ノードを除く受信ノードの数だけ分配して折り返す工程と、
（４）前記Ｋ台の折り返しノードで、折り返したデータを、前記送信ノードと前記自計算ノードを除く受信ノードへ再送信する工程と、前記Ｋ台の折り返しノードから再送信された各データを、前記送信ノードを含まない各受信ノードで受信する工程と、
（５）前記送信ノードを含まない各受信ノードで、受信したデータを前記制御手段に送る工程と、
を備える、並列計算機システムの制御方法。
［付記１７］
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、Ｙ台（１≦Ｙ≦Ｎ）の送信ノードから、１台の受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いてレデュース通信を行うとき、通信リンクとして、Ｋ台（１≦Ｋ≦Ｎ）の折り返しノードを経由する１ホップリンクを用い、各計算ノードは通信制御手段の指示の下、
（１）各送信ノードで、通信するデータをＫで分割する工程と、
（２）各送信ノードで、分割したＫ個のデータをＫ台の折り返しノードに個別に送信する工程と、前記Ｋ台の折り返しノードで、前記分割したＫ個のデータの１つを、個別に受信する工程と、
（３）前記Ｋ台の折り返しノードで、自計算ノードに残されたデータと受信したデータとを使ってレデュースの演算を行う工程と、その演算結果を折り返す工程と、
（４）前記Ｋ台の折り返しノードで、演算結果を前記受信ノードに送信する工程と、Ｋ台の折り返しノードからの各演算結果を、前記受信ノードで受信する工程と、
（５）前記受信ノードで、受信したデータを、並列計算プログラムを実行する制御手段に送る工程と、
を備える、並列計算機システムの制御方法。
［付記１８］
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、Ｙ台（１≦Ｙ≦Ｎ）の計算ノードが、送信ノード、及び、受信ノードの両方となり、前記送信ノードから前記受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いてオールレデュース通信を行うとき、通信リンクとして、Ｋ台（１≦Ｋ≦Ｎ）の折り返しノードを経由する１ホップリンクを用い、各計算ノードは通信制御手段の指示の下、
（１）各送信ノードで、通信するデータをＫで分割する工程と、
（２）各送信ノードで、分割したＫ個のデータをＫ台の折り返しノードに個別に送信する工程と、前記Ｋ台の折り返しノードで、前記分割したＫ個のデータの１つを、個別に受信する工程と、
（３）前記Ｋ台の折り返しノードで、自計算ノードに残されたデータと受信したデータを使ってレデュースの演算を行う工程と、自計算ノードを除く受信ノードの数だけ演算結果を分配して折り返す工程と、
（４）前記Ｋ台の折り返しノードで、自計算ノードを除く受信ノードに演算結果を送信する工程と、Ｋ台の折り返しノードからの各演算結果を、各受信ノードで受信する工程と、
（５）各受信ノードで、受信したデータを、並列計算プログラムを実行する制御手段に送る工程と、
を備える、並列計算機システムの制御方法。
［付記１９］
コンピュータに、
送信ノードと受信ノードとの間を直接接続する直接リンクのみを使用するリンクと、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクのみを使用するリンクと、前記直接リンクと前記１ホップリンクとを組み合わせて使用するリンクとの中から、前記送信ノードから前記受信ノードへデータを転送する際、前記送信ノードと前記受信ノードとを接続するリンクを選定する処理を実行させるためのプログラム。
［付記２０］
コンピュータに、
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、１台の送信ノードから他の１台の受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いた１対１通信を行うとき、通信リンクとしてＫ台（１≦Ｋ≦Ｎ−２）の折り返しノードを経由するＫ個の１ホップリンクと、Ｌ台（Ｌ＝０又は１）の前記送信ノードと前記受信ノードとを直接接続する直接リンクとを用い、各計算ノードは通信制御手段の指示の下、
（１）前記送信ノードで、通信するデータを（Ｋ＋Ｌ）で分割する処理と、
（２）前記送信ノードで、分割した（Ｋ＋Ｌ）個のデータをＫ台の折り返しノードとＬ台の受信ノードとに個別に送信する処理と、各前記Ｋ台の折り返しノードと前記Ｌ台の受信ノードで、前記分割した（Ｋ＋Ｌ）個のデータの１つを、個別に受信する処理と、
（３）各前記Ｋ台の折り返しノードで、受信したデータを折り返す処理と、前記Ｌ台の受信ノードで、受信したデータをそのまま並列計算プログラムを実行する制御手段へ送る処理と、
（４）各前記Ｋ台の折り返しノードで、折り返されたデータを前記受信ノードへ再送信する処理と、前記Ｋ台の折り返しノードから再送信されたデータを、前記受信ノードで受信する処理と、
（５）前記受信ノードで、受信したデータを前記制御手段に送る処理と、を実行させるためのプログラム。
［付記２１］
コンピュータに、
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、１台の送信ノードから、前記送信ノードを含むＸ台（１≦Ｘ≦Ｎ）の受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いてマルチキャスト通信を行うとき、通信リンクとして、前記送信ノードを含まないＫ台（１≦Ｋ≦Ｎ−１）の折り返しノードを経由する１ホップリンクを用い、各計算ノードは通信制御手段の指示の下、
（１）前記送信ノードで、通信するデータをＫで分割する処理と、
（２）前記送信ノードで、分割したＫ個のデータをＫ台の折り返しノードに個別に送信する処理と、前記Ｋ台の折り返しノードで、前記分割したＫ個のデータの１つを、個別に受信する処理と、
（３）前記Ｋ台の折り返しノードで、受信したデータを、並列計算プログラムを実行する制御手段へ送ると共に、受信したデータを、前記送信ノードと自計算ノードを除く受信ノードの数だけ分配して折り返す処理と、
（４）前記Ｋ台の折り返しノードで、折り返したデータを、前記送信ノードと前記自計算ノードを除く受信ノードへ再送信する処理と、前記Ｋ台の折り返しノードから再送信された各データを、前記送信ノードを含まない各受信ノードで受信する処理と、
（５）前記送信ノードを含まない各受信ノードで、受信したデータを前記制御手段に送る処理と、を実行させるためのプログラム。
［付記２２］
コンピュータに、
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、Ｙ台（１≦Ｙ≦Ｎ）の送信ノードから、１台の受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いてレデュース通信を行うとき、通信リンクとして、Ｋ台（１≦Ｋ≦Ｎ）の折り返しノードを経由する１ホップリンクを用い、各計算ノードは通信制御手段の指示の下、
（１）各送信ノードで、通信するデータをＫで分割する処理と、
（２）各送信ノードで、分割したＫ個のデータをＫ台の折り返しノードに個別に送信する処理と、前記Ｋ台の折り返しノードで、前記分割したＫ個のデータの１つを、個別に受信する処理と、
（３）前記Ｋ台の折り返しノードで、自計算ノードに残されたデータと受信したデータとを使ってレデュースの演算を行う処理と、その演算結果を折り返す処理と、
（４）前記Ｋ台の折り返しノードで、演算結果を前記受信ノードに送信する処理と、Ｋ台の折り返しノードからの各演算結果を、前記受信ノードで受信する処理と、
（５）前記受信ノードで、受信したデータを、並列計算プログラムを実行する制御手段に送る処理と、を実行させるためのプログラム。
［付記２３］
コンピュータに、
少なくともＮ台（Ｎは３以上の整数）の計算ノードの間が光ファイバを介して個別にすべて直接接続されたフルメッシュ接続で構成され、前記計算ノードのうち、Ｙ台（１≦Ｙ≦Ｎ）の計算ノードが、送信ノード、及び、受信ノードの両方となり、前記送信ノードから前記受信ノードへ、前記送信ノードと前記受信ノードとの間を、前記送信ノード、前記受信ノード以外の折り返しノードを経由して接続する１ホップリンクを用いてオールレデュース通信を行うとき、通信リンクとして、Ｋ台（１≦Ｋ≦Ｎ）の折り返しノードを経由する１ホップリンクを用い、各計算ノードは通信制御手段の指示の下、
（１）各送信ノードで、通信するデータをＫで分割する処理と、
（２）各送信ノードで、分割したＫ個のデータをＫ台の折り返しノードに個別に送信する処理と、前記Ｋ台の折り返しノードで、前記分割したＫ個のデータの１つを、個別に受信する処理と、
（３）前記Ｋ台の折り返しノードで、自計算ノードに残されたデータと受信したデータを使ってレデュースの演算を行う処理と、自計算ノードを除く受信ノードの数だけ演算結果を分配して折り返す処理と、
（４）前記Ｋ台の折り返しノードで、自計算ノードを除く受信ノードに演算結果を送信する処理と、Ｋ台の折り返しノードからの各演算結果を、各受信ノードで受信する処理と、
（５）各受信ノードで、受信したデータを、並列計算プログラムを実行する制御手段に送る処理と、を実行させるためのプログラム。
【符号の説明】
【０１３４】
４００、７００、８００、１１００、２５００、３８００    並列計算機システム
４０１−１〜４０１−４、８０１−１〜８０１−４、１１０１−１〜１１０１−４、２５０１−１〜２５０１−４、３８０１−１〜３８０１−４    計算ノード
４０２、８０２    ケーブル
４０３、８０３    送受信器
４５１、８５１、１１５１、２５５１、３１５１    プロセッサ／メモリ
４５２、７０３、８５２、１１５２、２５５２    通信制御部
５００、７０１    直接リンク
５０１、５０２、７０２、９０１、９０２    １ホップリンク
７０４、１１５５−２、１１５６−１    送信ノード
７０５、１１５５−３、１１５６−２    受信ノード
７０６    折り返しノード
８５３、１１５３、２５５３、３１５３    分散スイッチ
８５４、１１５４、３８５４    折り返し機能部
１１０２−１、２５０２−１    ＡＷＧ
１１０２−２、２５０２−２    光ファイバ
１１０２−３、２５０２−３    周回性ＡＷＧ
１１０３−１〜１１０３−３、２５０３−１〜２５０３−３    光送受信器
１１５５、２５５５、３８５５    通信管理テーブル
１１５５−０、１３０１    通信管理番号
１１５５−１    通信種類
１１５５−４    コミュニケータ
１１５５−５    送信アドレス
１１５５−６    受信アドレス
１１５５−７    データ個数
１１５５−８    データ精度
１１５５−９    ＩＤ番号
１１５５−１０    通信状態
１１５６、２５５６、３８５６    リンク管理テーブル
１２０１、２６０１    送信用クロスバースイッチ
１１５４−１、１２０１−１、１２０１−２、１２０２−１、１２０２−２、１２０２−３    入力ポート
１１５４−２    分配器
１１５４−３、１１５４−４、１１５４−Ｎ、１２０１−３、１２０１−４、１２０２−４、１２０２−５、３１８４    出力ポート
１１５６−３    利用状況
１１５６−４    １ホップ経由ノード
１２０２、２６０２    受信用クロスバースイッチ
２６０３、２６０５    分配部
２６０４、２６０６、２６０７    スイッチ部
１３０２    ステップ番号
１３０３    リンク管理情報
１３０４    通信プロセスＩＤ番号
１６０１、１６０２、１６０３、１７０１、１７０２、１７０３、１８０１、１８０２、３１８２、３１８３    結線
【図１】
2020046713.tif 000003
【図２】
2020046713.tif 000004
【図３】
2020046713.tif 000005
【図４Ａ】
2020046713.tif 000006
【図４Ｂ】
2020046713.tif 000007
【図５】
2020046713.tif 000008
【図６】
2020046713.tif 000009
【図７】
2020046713.tif 000010
【図８】
2020046713.tif 000011
【図９】
2020046713.tif 000012
【図１０】
2020046713.tif 000013
【図１１】
2020046713.tif 000014
【図１２】
2020046713.tif 000015
【図１３】
2020046713.tif 000016
【図１４】
2020046713.tif 000017
【図１５】
2020046713.tif 000018
【図１６】
2020046713.tif 000019
【図１７】
2020046713.tif 000020
【図１８】
2020046713.tif 000021
【図１９】
2020046713.tif 000022
【図２０】
2020046713.tif 000023
【図２１】
2020046713.tif 000024
【図２２】
2020046713.tif 000025
【図２３】
2020046713.tif 000026
【図２４】
2020046713.tif 000027
【図２５】
2020046713.tif 000028
【図２６】
2020046713.tif 000029
【図２７】
2020046713.tif 000030
【図２８】
2020046713.tif 000031
【図２９】
2020046713.tif 000032
【図３０】
2020046713.tif 000033
【図３１】
2020046713.tif 000034
【図３２Ａ】
2020046713.tif 000035
【図３２Ｂ】
2020046713.tif 000036
【図３３】
2020046713.tif 000037
【図３４】
2020046713.tif 000038
【図３５】
2020046713.tif 000039
【図３６】
2020046713.tif 000040
【図３７】
2020046713.tif 000041
【図３８】
2020046713.tif 000042
【図３９】
2020046713.tif 000043
【図４０】
2020046713.tif 000044
【図４１Ａ】
2020046713.tif 000045
【図４１Ｂ】
2020046713.tif 000046
【図４２】
2020046713.tif 000047
【図４３】
2020046713.tif 000048
【図４４】
2020046713.tif 000049
【図４５】
2020046713.tif 000050
【図４６】
2020046713.tif 000051
【図４７】
2020046713.tif 000052