(57)【要約】【課題】      本願発明は、簡単なハードウェア機構により実現可能であり、さらに、全体としてだけでなく部分的にも同期処理を実現可能な同期処理回路等を提案する。【解決手段】  本願発明に係る同期処理回路は、ツリー構造の複数のノードを用いて複数の処理手段の一部又は全部の同期処理を行う。ツリー構造のノードには、最下位に位置して前記複数の処理手段にそれぞれ対応する複数の葉ノード３と、最上位に位置する根ノード７と、根ノード７及び葉ノード３以外の複数の内部ノード５が含まれる。このツリー構造において、子ノードから親ノードに対して論理値を通知するだけでなく、親ノードから子ノードに対しても論理値を通知する。各内部ノード５は、親ノードに対して、内部ノード５の子ノードから通知された論理値を論理演算して得られた論理値を通知するか、又は、親ノードから通知される論理値の否定を通知するかを選択する内部ノード選択部を備える。【選択図】  図１
2014063278.tif 000002
【特許請求の範囲】
【請求項１】
ツリー構造の複数のノードを用いて複数の処理手段の一部又は全部の同期処理を行う同期処理回路であって、
前記ツリー構造のノードには、最下位に位置して前記複数の処理手段にそれぞれ対応する複数の葉ノードと、最上位に位置する根ノードと、前記根ノード及び前記葉ノード以外の複数の内部ノードが含まれ、
前記ツリー構造において、子ノードから親ノードに対して論理値を通知するだけでなく、親ノードから子ノードに対しても論理値を通知するものであり、
前記各内部ノードが、親ノードに対して、当該内部ノードの子ノードから通知された論理値を論理演算して得られた論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する内部ノード選択手段を備える、同期処理回路。
【請求項２】
前記各葉ノードが、親ノードに対して、当該葉ノードに対応する処理手段が同期ポイントに到達したか否かを示す論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する葉ノード選択手段を備える、請求項１記載の同期処理回路。
【請求項３】
当該同期処理回路は、バリア完了待ち／受付可能状態とバリア完了通知待ち状態との間で状態遷移するものであり、
前記対応する処理手段が同期ポイントに到達したか否かを示す論理値を通知する前記葉ノードは、親ノードに対して、
前記バリア完了待ち／受付可能状態において、対応する処理手段が同期ポイントに到達したことを示す論理値として同期状態論理値を通知し、同期ポイントには到達していないことを示す論理値として前記同期状態論理値とは異なる非同期状態論理値を通知し、
前記バリア完了通知待ち状態において、親ノードから前記同期処理論理値を通知された場合、前記非同期状態論理値を通知するものであり、
前記根ノード及び前記親ノードから通知される論理値の否定を通知する内部ノードは、
前記バリア完了待ち／受付可能状態において、全ての子ノードが前記同期状態論理値を通知する場合に、子ノードに対して、前記同期状態論理値を通知して、前記バリア完了通知待ち状態に遷移し、
前記バリア完了通知待ち状態において、全ての子ノードから前記非同期状態論理値を通知された場合に、前記バリア完了待ち／受付可能状態に遷移するものである、請求項２記載の同期処理回路。
【請求項４】
前記各内部ノードにおいて折り返しを行うか否かを示す情報を記憶する折返し記憶手段と、
前記各葉ノードにおいてマスクを行うか否かを示す情報を記憶するマスク記憶手段と、
前記各葉ノードが、親ノードに対して、前記マスク記憶手段に記憶された情報に応じて、当該葉ノードに対応する処理手段が同期ポイントに到達したか否かを示す論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する葉ノード選択手段を備え、
前記各内部ノードの前記内部ノード選択手段は、前記折返し記憶手段に記憶された情報に応じて選択し、
前記根ノードは、子ノードに対して、当該内部ノードの子ノードから通知された論理値を論理演算して得られた論理値を通知する、請求項２又は３に記載の同期処理回路。
【請求項５】
前記ツリー構造は複数存在し、各ツリー構造において、他のツリー構造とは独立して同期処理を行う、請求項１から４のいずれかに記載の同期処理回路。
【請求項６】
前記各内部ノードは、前記ツリー構造の構成を動的に変更するための構成変更処理同期機構を備え、
前記構成変更処理同期機構は、
親ノードに対して、自ノード及び全ての子ノードが同期要求中の場合、親ノードに同期要求を送り、
子ノードに対して、いずれかの子ノードから同期要求中に親ノードへの同期要求を行っていて、かつ、完了していない場合は、同期完了していないことを示す論理値を送り、それ以外では異なる論理値を送るものである、請求項１から５のいずれかに記載の同期処理回路。
【請求項７】
ツリー構造の複数のノードを用いて複数の処理手段の一部又は全部の同期処理を行う同期処理回路における同期処理方法であって、
前記ツリー構造において、子ノードから親ノードに対して論理値を通知するだけでなく、親ノードから子ノードに対しても論理値を通知するものであり、
前記同期処理回路が備える内部ノード選択手段が、前記ツリー構造において親ノード及び子ノードが存在する内部ノードが、前記親ノードに対して、当該内部ノードの子ノードから通知された論理値を論理演算して得られた論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する選択ステップを含む同期処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、同期処理回路及び同期処理方法に関し、特に、ツリー構造により複数の処理手段の一部又は全部の同期状態を判断する同期処理回路等に関する。
【背景技術】
【０００２】
プロセス技術やハードウェア技術、ソフトウェア技術等の進歩により、チップ上に複数のプロセッサコア（以下、「コア」と略す。）を搭載したマルチコアプロセッサが広く普及するに至った。さらに、より多くのコアを搭載した、メニーコアプロセッサについても研究が及んでおり、例えば100個のコアを搭載した商用化チップも存在する。
【０００３】
メニーコアプロセッサ等において、高い実効性能を実現するためには、搭載したコアの数に見合っただけの並列性を活用できなければならない。例えば画像処理や科学技術計算のように極めて高い並列性が内在する場合においては、コアの稼働率を高めることができる。しかしながら、十分な並列性が抽出できない場合が多く存在する。したがって、メニーコアプロセッサの応用範囲を拡大しその普及を図るためには、プログラム内並列性のみならず、プログラム間並列性をも積極的に活用しなければならない。すなわち、メニーコアプロセッサにおいては、効率的なマルチスレッド・マルチプログラム実行環境の実現が極めて重要となる。具体的には、ＯＳ、メール、ゲーム、コンパイラなどの複数ソフトウェアが同時に動作する組込みシステムや、複数ユーザが異なるジョブを投入するデータセンター・サーバ応用が考えられる。
【０００４】
並列化された複数のプログラムを同時に実行する場合の課題として、コア間での同期処理の高効率化が挙げられる。同期は、コア間の歩調を合わせるために必要である。例えば、複数のコアがメモリやバスなどの共通資源を使用する際にアクセス順序を決めるときや、複数のコアが同時に動作を開始したい場合などに実行される。ここで、ある同期に参加するコアの集合をコアグループと呼ぶ。一般に、並列化プログラムの実行に使用するコアの数は、当該プログラムに内在する並列性の度合いに大きく依存する。これに加え、複数のプログラムが同時に実行される状況においては、複数のコアグループそれぞれが同期処理を発行する場合もある。したがって、メニーコアプロセッサにおいては、複数の様々なコアグループに対して独立かつ並列に実行可能な同期機構の実現が必要となる。
【０００５】
同期手法の代表的なものの一つとして、バリア同期がある。これは、同期の対象となる各コアが実行するプログラム中に、対象コア全てが許可を出すまで停止する指示を埋め込むことにより同期を実現する手法である。バリア同期は、MPI、OpenMP、pthread等の多くの並列コンピューティング環境に実装されている。バリア同期は、一般に、専用ハードウェアの追加なしに実現可能である。
【０００６】
HPC分野で使用されるような大規模システムにおいては、ハードウェアバリア機構が実装されていることが多い。例えば、大規模システムにおいては、システムに比して小規模かつ高速なハードウェアバリア機能を実装している（非特許文献１〜３参照）。特許文献１及び２は、ツリー・ネットワーク構造を利用して同期等を実現するものである。
【０００７】
また、オンチップマルチコア・メニーコアプロセッサ用の研究も行われている（非特許文献４〜６参照）。Villaら（非特許文献４参照）は、コア間データ通信用のNoCに回路追加を行ってバリアの高速化を行っている。Itoら（非特許文献５参照）及びHoeerら（非特許文献６参照）は、専用のネットワークを用いてバリア同期を行っている。（
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特表２００４−５２９４１４号公報
【特許文献２】特表２００４−５３６３７２号公報
【非特許文献】
【０００９】
【非特許文献１】Gara，A.、外１３名，Overview  of  the  Blue  Gene/L  system  architecture，IBM  Journal  of  Research  and  Development，Vol．49，No．2，pp.195-212，2005.
【非特許文献２】Habata，S.、外３名，Hardware  system  of  the  Earth  Simulator，Parallel  Computing，Vol．30，No．12，pp.1287-1313，2004.
【非特許文献３】Ajima，Y.，外２名，Tofu：A  6d  mesh/torus  interconnect  for  exascale  computers，Computer，Vol．42，No．11，pp.36-40，2009.
【非特許文献４】Villa，O.、外２名，Efficiency  and  scalability  of  barrier  synchronization  on  NoC  based  many-core  architectures，Proceedings  of  the  2008  international  conference  on  Compilers，architectures  and  synthesis  for  embedded  systems（Altman，E.，ed.），Atlanta，GA，USA，ACM，ACM，pp.81-90，2008.
【非特許文献５】Ito，M.、外１６名，An  8640  MIPS  SoC  with  Independent  Power-Off  Control  of  8  CPUs  and  8  RAMs  by  An  Automatic  Parallelizing  Compiler，2008  IEEE  International  Solid-State  Circuits  Conference  Digest  of  Technical  Papers（Fujino，L.C.，ed.)，San  Francisco，CA，IEEE，S  Digital  Publishing  Inc，pp.90-598，2008.
【非特許文献６】Hoefler，T.、外３名，Adding  Low-Cost  Hardware  Barrier  Support  to  Small  Commodity  Clusters，19th  International  Conference  on  Architecture  and  Computing  Systems  −ARCS06，pp.343-350，2006.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、バリア同期は、数多くのコアが参加する場合には、バリア同期に要する時間が大きくなり、頻繁に使用するとソフトウェア実行性能の低下要因となる。さらに、各コアのバリア処理完了時刻に大きくばらつきが発生して、事前のチューニングが期待通りに反映されなくなる、などの問題が発生する。
【００１１】
そのため、HPC分野で使用されるような大規模システムにおいては、ハードウェアバリア機構が実装されていることが多い。しかしながら、大規模システムでのハードウェアバリア機構（非特許文献１乃至３、特許文献１及び２参照）は、筺体間やチップ間を繋ぐ長距離ネットワークを制御する多機能なネットワークコントローラの存在を前提として設計されている。そのため、回路規模が大きく、そのままメニーコアプロセッサのハードウェアバリアとして使用することは難しい。また、大規模システムでは、配線コスト低減を目的として、ハードウェアバリアで使用するネットワークを他の通信機能と共有している。そのため、常に最短レイテンシでのバリア同期実行は期待できない。
【００１２】
また、Villaらの手法（非特許文献４参照）は、ネットワークをデータと共用している。そのため、バリア同期のレイテンシは固定にならない。Itoら（非特許文献５参照）及びHoeflerら（非特許文献６参照）の手法は、いずれも、ネットワーク内のコアのグループ分けをハードウェア回路によって行う機能は持っていない。
【００１３】
そこで、本願発明は、簡単なハードウェア機構により実現可能であり、さらに、全体としてだけでなく部分的にも同期処理を実現可能な同期処理回路等を提案することを目的とする。
【課題を解決するための手段】
【００１４】
本願発明の第１の観点は、ツリー構造の複数のノードを用いて複数の処理手段の一部又は全部の同期処理を行う同期処理回路であって、前記ツリー構造のノードには、最下位に位置して前記複数の処理手段にそれぞれ対応する複数の葉ノードと、最上位に位置する根ノードと、前記根ノード及び前記葉ノード以外の複数の内部ノードが含まれ、前記ツリー構造において、子ノードから親ノードに対して論理値を通知するだけでなく、親ノードから子ノードに対しても論理値を通知するものであり、前記各内部ノードが、親ノードに対して、当該内部ノードの子ノードから通知された論理値を論理演算して得られた論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する内部ノード選択手段を備えるものである。
【００１５】
本願発明の第２の観点は、第１の観点の同期処理回路であって、前記各葉ノードが、親ノードに対して、当該葉ノードに対応する処理手段が同期ポイントに到達したか否かを示す論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する葉ノード選択手段を備えるものである。
【００１６】
本願発明の第３の観点は、第２の観点の同期処理回路であって、当該同期処理回路は、バリア完了待ち／受付可能状態とバリア完了通知待ち状態との間で状態遷移するものであり、前記対応する処理手段が同期ポイントに到達したか否かを示す論理値を通知する前記葉ノードは、親ノードに対して、前記バリア完了待ち／受付可能状態において、対応する処理手段が同期ポイントに到達したことを示す論理値として同期状態論理値を通知し、同期ポイントには到達していないことを示す論理値として前記同期状態論理値とは異なる非同期状態論理値を通知し、前記バリア完了通知待ち状態において、親ノードから前記同期処理論理値を通知された場合、前記非同期状態論理値を通知するものであり、前記根ノード及び前記親ノードから通知される論理値の否定を通知する内部ノードは、前記バリア完了待ち／受付可能状態において、全ての子ノードが前記同期状態論理値を通知する場合に、子ノードに対して、前記同期状態論理値を通知して、前記バリア完了通知待ち状態に遷移し、前記バリア完了通知待ち状態において、全ての子ノードから前記非同期状態論理値を通知された場合に、前記バリア完了待ち／受付可能状態に遷移するものである。
【００１７】
本願発明の第４の観点は、第２又は第３の観点の同期処理回路であって、前記各内部ノードにおいて折り返しを行うか否かを示す情報を記憶する折返し記憶手段と、前記各葉ノードにおいてマスクを行うか否かを示す情報を記憶するマスク記憶手段と、前記各葉ノードが、親ノードに対して、前記マスク記憶手段に記憶された情報に応じて、当該葉ノードに対応する処理手段が同期ポイントに到達したか否かを示す論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する葉ノード選択手段を備え、前記各内部ノードの前記内部ノード選択手段は、前記折返し記憶手段に記憶された情報に応じて選択し、前記根ノードは、子ノードに対して、当該内部ノードの子ノードから通知された論理値を論理演算して得られた論理値を通知するものである。
【００１８】
本願発明の第５の観点は、第１から第４のいずれかの観点の同期処理回路であって、前記ツリー構造は複数存在し、各ツリー構造において、他のツリー構造とは独立して同期処理を行うものである。
【００１９】
本願発明の第６の観点は、第１から第５のいずれかの観点の同期処理回路であって、前記各内部ノードは、前記ツリー構造の構成を動的に変更するための構成変更処理同期機構を備え、前記構成変更処理同期機構は、親ノードに対して、自ノード及び全ての子ノードが同期要求中の場合、親ノードに同期要求を送り、子ノードに対して、いずれかの子ノードから同期要求中に親ノードへの同期要求を行っていて、かつ、完了していない場合は、同期完了していないことを示す論理値を送り、それ以外では異なる論理値を送るものである。
【００２０】
本願発明の第７の観点は、ツリー構造の複数のノードを用いて複数の処理手段の一部又は全部の同期処理を行う同期処理回路における同期処理方法であって、前記ツリー構造において、子ノードから親ノードに対して論理値を通知するだけでなく、親ノードから子ノードに対しても論理値を通知するものであり、前記同期処理回路が備える内部ノード選択手段が、前記ツリー構造において親ノード及び子ノードが存在する内部ノードが、前記親ノードに対して、当該内部ノードの子ノードから通知された論理値を論理演算して得られた論理値を通知するか、又は、当該親ノードから通知される論理値の否定を通知するかを選択する選択ステップを含むものである。
【００２１】
なお、ノードは、ハードウェア・モジュールであり、根ノード及び内部ノードにおける論理演算は、バリア完了待ち／受付可能状態では、例えば、子ノードから通知された論理値が、全て、同期ポイントに到達したものを示す値である場合には、その同期ポイントに到達したことを示す論理値とし、そうでない場合には異なる論理値とするものである。これにより、折返し設定でない内部ノードは、親ノードに対して、コアグループ内の当該内部ノードの子ノードが全て同期ポイントに到達したことを通知する。そして、根ノード及び折返し設定がされた内部ノードは、コアグループ内の処理手段における処理が同期ポイントに到達したと判定し、各葉ノードに対して、同期処理完了通知の信号を送り、バリア完了通知待ち状態に遷移することができる。また、バリア完了通知待ち状態では、例えば、葉ノードから通知された論理値が、全て、葉ノードの同期設定レジスタがリセットされたことを示す論理値であれば、葉ノードの同期設定レジスタがリセットされたことを示す論理値とし、そうでない場合には異なる論理値とするものである。これにより、根ノード及び折返し設定がされた内部ノードは、コアグループ内の処理手段の同期設定レジスタが全てリセットされたと判定し、バリア完了待ち／受付可能状態に遷移することができる。
【００２２】
また、根ノード及び内部ノードにおいて論理演算により得られた論理値を、それぞれの根ノード及び内部ノードの状態とし、内部ノード及び葉ノードにおいて、直近の親ノードの状態を記憶する親ノード状態記憶手段を設け、折り返し又はマスクを行うときには、親ノード状態記憶手段に記憶された論理値の否定を通知するようにしてもよい。
【００２３】
また、第３の観点の同期処理回路において、前記子ノードから通知された論理値を論理演算して得られた論理値を通知する前記内部ノードは、親ノードに対して、前記バリア完了待ち／受付可能状態において、全ての子ノードが前記同期状態論理値を通知する場合に、前記同期状態論理値を通知し、子ノードのいずれかが前記非同期状態論理値を通知する場合に、前記非同期状態論理値を通知するものであり、前記バリア完了通知待ち状態において、全ての子ノードが前記非同期状態論理値を通知する場合に、前記非同期状態論理値を通知するものであり、子ノードのいずれかが前記同期状態論理値を通知する場合に、前記同期状態論理値を通知するものであり、前記根ノード及び前記親ノードから通知される論理値の否定を通知する内部ノードは、前記バリア完了待ち／受付可能状態において、子ノードのいずれかが前記非同期状態論理値を通知する場合に、子ノードに対して、前記非同期状態論理値を通知し、全ての子ノードが前記同期状態論理値を通知する場合に、子ノードに対して、前記同期状態論理値を通知して、前記バリア完了通知待ち状態に遷移し、前記バリア完了通知待ち状態において、子ノードのいずれかが前記同期状態論理値を通知する場合に、子ノードに対して、前記同期状態論理値を通知し、全ての子ノードが前記非同期状態論理値を通知する場合に、子ノードに対して、前記非同期状態論理値を通知して、前記バリア完了待ち／受付可能状態に遷移するものであってもよい。
【発明の効果】
【００２４】
本願発明の各観点によれば、複数のノードがツリー構造に接続するというシンプルな構造であり、小規模・小レイテンシ・ばらつきの無いハードウェアバリアを可能にする。さらに、簡単な機能追加（例えば、折返しや、第３の観点のマスク）により、バリアネットワークの分割を可能にする。さらに、バリア回路の複数実装（第５の観点の多重化）により、バリアに参加するコアの組み合わせに柔軟性を持たせることが可能になる。よって、多様なプロセスが動作するであろうメニーコアプロセッサにおいても対応可能な柔軟なハードウェアバリア機構を実現することが可能になる。さらに、第６の観点にあるように、ツリー構造は、同期機構を応用して、各ノードが、分散して、全ノードで構成変更が実施されたかを確認して、動的に構成を変更することを実現することができる。なお、構成変更を必要としない同期サブツリーネットワークに対しては、同一設定で新たな設定を行うことにより、現在行っているバリア同期処理を継続することが可能になっている。そのため、本機能によりバリアネットワーク内に新たなバリアグループを動的に生成することが可能になる。
【００２５】
なお、例えば特許文献１及び２には、ツリー・ネットワーク構造を利用して同期等を実現することが記載されている。しかしながら、例えばパルス信号等を利用するものであり、上からの折返しをするものではないと評価することができる。本願発明の各観点は、上から折り返すことに技術的特徴が認められるものである。
【図面の簡単な説明】
【００２６】
【図１】本願発明に係る同期処理回路の一例の概要を示すブロック図である。
【図２】図１の葉ノード３のハードウェア構成の一例を示す図である。
【図３】提案するバリア機構の状態遷移を示す図である。
【図４】図１の内部ノード５のハードウェア構成の一例を示す図である。
【図５】８個の葉ノード４１1，…，４１8を有するバリアネットワークを４分割した例を示す図である。
【図６】バリア機構の状態遷移の一例を示す図である。
【図７】図４の内部ノード５における同期回路３１の一例であるハードウェア構成を示す図である。
【図８】８ノードからなるバリアネットワークを２つ使用して、２つのグループに分割した例を示す図である。
【図９】動的な構成変更を実現するための葉ノードの構成変更処理同期機構の一例を示す図である。
【図１０】動的な構成変更を実現するための内部ノードの構成変更処理同期機構の一例を示す図である。
【図１１】実験においてノードの構成変更を行うコアの割り当てを示す図である。
【図１２】実験においてバリア同期時間を測定するために使用した評価用プログラムを示す図である。
【図１３】実験における測定対象を示す図である。
【発明を実施するための形態】
【００２７】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例１】
【００２８】
図１は、本願発明に係る同期処理回路の一例の概要を示すブロック図である。図１を参照して、本願発明に係るハードウェアバリア機構（以下、「バリア機構」と略す。）の基本構造と動作を説明する。
【００２９】
本実施例では、固定的なコアグループを対象とする。本実施例のバリア機構の実現には、以下のハードウェア要素が必要となる。
【００３０】
バリア専用の双方向二分木ネットワークをバリアネットワークという。図１は、４コアでコアグループを構成した場合の例を示す。コア１1，…，１4（以下、符号の添え字は、複数（又は、複数のもののいずれか）を意味する場合には省略する場合もある。）は、プロセッサコア（「コア」と略す。）（本願請求項の「処理手段」の一例）である。図１では、４つの場合を例にして示している。
【００３１】
同期処理回路は、葉ノード３（本願請求項の「葉ノード」の一例）と、内部ノード５（本願請求項の「内部ノード」の一例）と、根ノード７（本願請求項の「根ノード」の一例）と、折返し記憶部９1，９2（本願請求項の「折返し記憶手段」の一例）と、マスク記憶部１１1，…，１１4（本願請求項の「マスク記憶手段」の一例）を備える。
【００３２】
葉ノード３は、各コアに追加されるハードウェア・モジュールである。同期設定レジスタ及び同期状態表示レジスタという２種類の１ビット・レジスタを有する。同期設定レジスタは、当該コアがバリア同期の完了待ち状態にあるか否かを指示するレジスタである。当該コアのプログラム実行が同期ポイントに到達すると‘１’にセットされる。また、同期状態表示レジスタがリセットされると‘０’にリセットされる。同期状態表示レジスタは、根ノード７が管理するバリア機構状態レジスタの複製を保持するレジスタである。
【００３３】
図２（ａ）は、葉ノード３のハードウェア構成の一例を示す図である。葉ノード３は、切り離し（マスク）機能をサポートする。マスク機能は、葉ノード３に対して適用される設定であり、葉ノード３に対応するコア１がバリアに参加するか否かを指定する。本実施例では、図１のマスク記憶部１１に、各葉ノード３のマスク機能の有効／無効を示す情報が記憶されている。葉ノード３は、同期設定レジスタ２１と、同期状態表示レジスタ２３と、否定演算部２５と、セレクタ２７（本願請求項の「葉ノード選択手段」の一例）を備える。セレクタ２７は、マスク記憶部１１におけるマスクの有効／無効の設定に応じて、同期設定レジスタ２１の値か、又は、同期状態表示レジスタ２３の値を否定演算部２５により否定したものかを選択して親ノードに通知する。すなわち、バリア機構内部では、マスクが有効であれば、葉ノード３は、親ノードに対して、同期設定レジスタ２１の値を送信する（図２（ｂ）参照）。一方、無効な場合には、葉ノード３は、親ノードに対して、同期状態表示レジスタ２３の反転値を出力することで、上位のノードに対する影響を排除する（図２（ｃ）参照）。
【００３４】
根ノード７は、コアグループにおける同期処理実行状態を管理するハードウェア・モジュールである。根ノード７の管理対象コアグループは、子孫の葉ノードのうち、マスク記憶部１１によりマスク機能が無効な葉ノードを除いたものである。図１の例では、マスク機構が有効な場合（マスク機能を使用していない場合）には、根ノード７が管理するコアグループは、葉ノード３1〜３4である。管理下にある葉ノード３から同期設定レジスタ値を集計し、全てのコア１が同期ポイントに到達したか否かを判定する。内部には１ビットの同期状態レジスタを有する。
【００３５】
提案するバリア機構には、バリア完了待ち／受付可能状態とバリア完了通知待ち状態という２つの状態があり、同期状態レジスタにより現状態を表す。状態遷移を図３に示す。バリア完了待ち／受付可能状態（図３のW_SET）は、コアグループに属するコア１が同期処理を実行中、又は、次のバリア同期処理を実行可能な状態である。このとき、同期状態レジスタは‘０’にリセットされる。バリア完了通知待ち状態（図３のW_RST）は、バリア同期が完了し、全葉ノードに対して完了通知をブロードキャストしている状態である。このとき、同期状態レジスタは‘１’にセットされる。
【００３６】
内部ノード５は、根ノード７と葉ノード３の中間に位置するハードウェア・モジュールである。本実施例では、内部構造は根ノード７と同じであるとする。内部ノード５は、バリアネットワークを分割して複数コアグループの同期処理を実現する場合には、各コアグループの最上位の内部ノード５は、折返し機能が有効とされ、当該コアグループの根ノードとして動作する。
【００３７】
図４（ａ）は、内部ノード５のハードウェア構成の一例を示す図である。内部ノード５は、折返し機能をサポートする。折返し機能は、内部ノード５に対して適用される設定であり、上位のノードのコアグループのバリアに参加するか否かを指定する。本実施例では、図１の折返し記憶部９に、各内部ノード５の折返し機能の有効／無効を示す情報が記憶されている。内部ノード５は、同期回路３１と、同期状態表示レジスタ３３と、否定演算部３５と、セレクタ３７（本願請求項の「内部ノード選択手段」の一例）と、セレクタ３９を備える。同期回路３１は、例えば、バリア完了待ち／受付可能状態では、子ノードから通知された論理値が、全て、同期ポイントに到達したものを示す値である場合には、その同期ポイントに到達したことを示す論理値とし、そうでない場合には異なる論理値とするものである。同期回路３１は、例えば、バリア完了通知待ち状態では、葉ノードから通知された論理値が、全て、葉ノードの同期設定レジスタがリセットされたことを示す論理値であれば、葉ノードの同期設定レジスタがリセットされたことを示す論理値とし、そうでない場合には異なる論理値とするものである。セレクタ３７は、折返し記憶部９における折返しの有効／無効の設定に応じて、同期状態表示レジスタ３３の値を否定演算部３５により否定したものか（図４（ｂ）参照）、又は、同期回路３１から出力された論理値か（図４（ｃ）参照）を選択して親ノードに通知する。セレクタ３９は、折返し記憶部９における折返しの有効／無効の設定に応じて、同期回路３１から出力された論理値か（図４（ｂ）参照）、又は、親ノードから通知された論理値か（図４（ｃ）参照）を選択して子ノードに通知する。
【００３８】
本実施例では、内部ノード５は、根ノード７と同じハードウェア構成を採る。したがって、内部ノード５は、根ノード７と同一の機能を有することが可能である。そこで、ある内部ノードを根ノードとして動作させることで、バリアネットワークを複数の部分木に分割する。図５は、８個の葉ノード４１1，…，４１8を有するバリアネットワークを４分割した例である。各葉ノード４１の数字は、マスクの有無を示す。‘０’はマスク有効を示し、‘１’はマスク無効を示す。内部ノード４３1〜４３6及び根ノード４５の数字は、折返しの有無を示す。‘０’は折返し、‘１’は折り返さないことを示す。図５の葉ノード４１1，４１2及び４１8は、コアグループＡを構成している。図５の葉ノード４１3及び４１4は、コアグループＢを構成している。コアグループＢでは、親ノードとなる内部ノード４１2に対して折返し機能を適用することで、根ノードとして動作させる。図５の葉ノード４１5及び４１6は、コアグループＣを構成している。コアグループＣでは、親ノードとなる内部ノード４１3に対して折返し機能を適用することで、根ノードとして動作させる。図５の葉ノード４１7は、コアグループＤを構成している。
【００３９】
図４（ｂ）に示すように、内部ノードに対して折返し機能が適用されると、子ノードから回送された信号（同期設定レジスタの値）の論理演算結果を親ノードには回送せず、同期処理完了通知信号として子ノードに転送する。例えば、両方の子ノードが同期ポイントに到達した場合には、対応する同期設定レジスタが‘１’にセットされ、これらの論理積がとられる。この結果が、当該子ノードに対して同期処理完了通知信号としてフィードバックされる。また、親ノードに対しては、親ノードから回送されてきた同期処理完了通知信号の反転値を転送することで、上位（根ノードに近い方）のノードに対する影響を排除する。このように部分木を用いて小規模なバリアネットワークを複数構成することにより、各コアグループは独立かつ並列にバリア同期処理を行うことができるようになる。
【００４０】
まず、図６及び図７を参照して、折返し機能及びマスク機能を使用しない場合について、バリア機構の動作を説明する。図６は、バリア機構の状態が「バリア完了待ち／受付可能状態」である場合から、状態を遷移して、再度、「バリア完了待ち／受付可能状態」になるまでを示す。
【００４１】
図６において、内部ノード５３及び根ノード５５（図６の丸）内の数字は、スラッシュの左は同期設定レジスタの値を示し、スラッシュの右は状態出力値を示す。葉ノード５１（図６の四角）内の数字は、スラッシュの左は同期設定レジスタの値を示し、スラッシュの右は状態表示レジスタの値を示す。
【００４２】
図６（ａ）において、バリア機構の初期状態は「バリア完了待ち／受付可能状態」であり、全ての葉ノード５１の同期設定レジスタの初期値は‘０’とする（つまり、次のバリアを実行可能な状態である）。
【００４３】
同期処理において、葉ノード５１3に対応するコアが同期ポイントに到達したとする。このとき、当該コアの同期設定レジスタが‘１’に設定される。コア２の同期設定レジスタの値が、内部ノード５３2に送信される。このとき、他方の子ノードの同期設定レジスタの値がセットされていなければ、同期待ち状態を継続する（図６（ｂ））。
【００４４】
コア５１4が同期ポイントに到達し、同期設定レジスタが‘１’に設定される。これにより、内部ノード５３2は、親ノード５５（ここでは根ノード）に対して、同期設定レジスタの値を伝搬させる（図６（ｃ））。
【００４５】
葉ノード５１1及び５１2に対応するコアが同期ポイントに到達すると、内部ノード５３1は、根ノード５５に対して同期設定レジスタの値を伝搬させる。根ノード５５は全てのコアが同期ポイントに到達したと判定する。これにより、各葉ノードに対して同期処理完了通知の信号を送り、バリア完了通知待ち状態に遷移する（図６（ｄ））。
【００４６】
各葉ノードは、根ノードからバリア完了通知を受け取った後、同期設定レジスタを‘０’にリセットし、これが根ノードへと伝搬する（図６（ｅ））。
【００４７】
根ノード５５は、全ての葉ノード５１の同期設定レジスタの値がリセットされたことを判定し、バリア機構の状態をバリア完了待ち／受付可能状態にする。これにより、次の新たなバリア同期を受け付けることが可能となる（図６（ａ））。
【００４８】
図７は、図４の内部ノード５における同期回路３１の一例を示す図である。同期回路３１は、論理積演算部６１と、論理和演算部６３と、セレクタ６５と、同期記憶部６７を備える。論理積演算部６１は、子ノードから入力した同期設定レジスタの値の論理積をとる。論理和演算部６３は、子ノードから入力した同期設定レジスタの値の論理和をとる。セレクタ６５は、同期記憶部６７に記憶された値に基づき、論理積演算部６１の出力と論理和演算部６３の出力のいずれかを選択するものである。同期記憶部６７は、セレクタ６５の出力値を記憶する。図７にあるように、内部ノード５は、バリア完了待ち／受付可能状態の場合には、２つの子ノードから入力した同期設定レジスタの値の論理積をとる。一方、バリア完了通知待ち状態の場合には、これらの値の論理和を親ノードに回送する。これらの値が根に向かって伝搬することにより、根ノードは全ての葉ノードの状況を把握することができる。
【００４９】
折返し機能及びマスク機能により、続設定情報を変更して、バリアネットワークを論理的に分割し、一つのバリアネットワーク内で複数のバリア同期を実行できるように拡張することができる。
【００５０】
各ノードの動作は、折返し機能が有効な内部ノードについては、子ノードに対しては図６における根ノードと同じものとなる。折返し機能が無効な内部ノードについては、図６における内部ノードと同じものとなる。マスク機能が有効な葉ノードについては、図６における葉ノードと同じものとなる。
【００５１】
折返し機能が有効な内部ノード及びマスク機能が無効な葉ノードは、親ノードに対して、親ノードのコアグループが「バリア完了待ち／受付可能状態」であれば、同期ポイントに到達したことを示す論理値を通知し、「バリア完了通知待ち状態」であれば、同期設定レジスタをリセットしたことを示す論理値を通知することとなり、上位（根ノードに近い方）のノードに対する影響を排除する。
【００５２】
これにより、マルチプログラム実行環境下等において、複数の様々なコアグループに対して独立かつ並列に実行可能な同期処理をサポートすることが可能になる。
【００５３】
さらに、図８にあるように、多重化により、柔軟性を拡大することができる。マスク・折返しによる設定では、部分木単位のグループ構成以外は行えない。そのため、それ以外のグループ構成には、バリアネットワークを複数用意すること（多重化）により対応する。図８は、８ノードからなるバリアネットワークを２つ使用して、葉ノード６１1、６１3、６１5及び６１7と、葉ノード６１2、６１4，６１6及び６１8で組分けされた、２つのグループに分割した例を示す。各ネットワークにおけるノードは、独立して動作する。
【００５４】
本願発明のバリア機構は、折返し機能、マスク機能及び多重化を組み合わせることによって、少レイテンシでばらつきのないハードウェアバリアを、様々なノードの組み合わせで実行することを可能にする。すなわち、メニーコアプロセッサ等で利用することができ、柔軟性を有する新しいハードウェアバリア方式を実現することができる。具体的には、（１）低レイテンシでばらつきが小さく、（２）バリアネットワークの分割を可能にし、かつ、（３）小規模な回路量で実現できるハードウェアバリア機構である。また、この小規模なバリアネットワークを複数用意することで、多様なプロセスが動作するであろうメニーコアプロセッサにおいても対応可能な柔軟なハードウェアバリア機構を実現することができる。
【００５５】
続いて、図９及び１０を参照して、バリア機構の動的な構成変更の一例について説明する。図９及び図１０は、それぞれ、動的な構成変更を実現するための葉ノード及び内部ノードの構成変更処理同期機構の一例を示す。なお、図９及び１０は、ノード間にFFが入っていない例である。FFが入っている場合には、親ノードから出力が遅れるため、更新レジスタの変更タイミングを適宜調整することにより、実現することができる。
【００５６】
図９及び１０のバリア機構は、各ノードに分散して設定することにより、構成変更の並列処理を可能とし、さらに、構成変更の高速化を図っている。さらに、本バリア機構は、構成変更の確認を補助するための構成変更処理同期機構を備えている。この構成変更処理同期機構は、各ノードが、全ノードで構成変更が実施されたかを確認するための機構である。これは、バリア同期機構を応用することにより実現されている。すなわち、(1)各ノードは、構成変更を指示するための構成設定入力、及び、全ノード構成変更が行われたことを確認するための構成状態出力を持ち、(2)構成設定値を入力すると同時に構成設定入力に'1' を入力し、(3)構成状態出力が'0'になるまで待つ。このような一連の処理を行うことにより、構成設定が全ノードで実施されたことが確認でき、以降は新たな構成設定によるバリア同期および再度の構成設定が可能になる。
【００５７】
構成変更を必要としない同期サブツリーネットワークに対しては、同一設定で新たな設定を行うことにより、現在行っているバリア同期処理を継続することが可能になっている。そのため、本機能によりバリアネットワーク内に新たなバリアグループを動的に生成することが可能になる。
【００５８】
動的構成変更機構は、バリア同期機構と同様に葉ノードと内部ノード（根ノード）の組み合わせで、全ノードの構成設定入力を確認し結果を広報する。バリア同期機構と異なり、折り返しやマスクのハードウェアはもたず、ネットワークの全ノード間の同期を取る。また、同期完了確認から同期待ちへの状態遷移は、動的構成変更機構内で実施している。さらに同期要求入力信号はパルス信号である。
【００５９】
図９の葉ノードは、論理和演算部７３と、論理積演算部７５と、更新レジスタ７７を備える。図９の葉ノードは、同期の要求を行っている間（更新要求='1'又は更新レジスタ='1'）、親ノードに'1'を送る。すなわち、論理和演算部７３は、更新レジスタ７７に記憶された値と更新要求の論理和を演算する。親ノードからは、同期完了していない場合には'1'、完了している場合には'0'が返る。論理積演算部７５は、親ノードに通知する値と親ノードから通知された値との論理積を演算する。論理積演算部７５の演算結果が状態出力となる。状態出力は、葉ノードが同期要求中で親ノードが同期処理中の場合は'1'、それ以外では'0'となる。更新レジスタ７７は、論理積演算部７５の演算結果を記憶する。
【００６０】
図１０の内部ノードは、論理和演算部８１と、論理積演算部８３、８５、８７及び８９と、論理和演算部９１及び９３と、否定演算部９５と、更新レジスタ９７を備える。図１０の内部ノードでは、子ノードに対して、いずれかの子ノードから同期要求中に親ノードへの同期要求を行っていてかつ完了していない場合は'1'を返し、それ以外の場合には'0'を返す。親ノードに対しては、自ノード及び全ての子ノードが同期要求中の場合、親ノードに同期要求のため'1'を送る。根ノードと内部ノードの違いは、根ノードの場合同期を取る親ノードが存在しないため、親ノードからの値として常に'0'（同期完了）が送られてくることである。
【００６１】
すなわち、論理和演算部８１は、更新レジスタ９７に記憶された値と更新要求との論理和を演算する。論理積演算部８３は、子ノードから通知された値の論理積を演算する。論理積演算部８５は、論理和演算部８１と論理積演算部８３の出力の論理積を演算して、親ノードに通知する。否定演算部９５は、親ノードに通知した値の否定を演算する。親ノードからは、同期完了していない場合には'1'、完了している場合には'0'が返る。論理和演算部９３は、親ノードから通知された値と否定演算部９５の演算結果との論理和を演算する。論理積演算部８７は、論理和演算部９３の演算結果と論理和演算部８１の出力との論理積を演算する。更新レジスタ９７は、論理積演算部８７の演算結果を記憶する。論理和演算部９１は、子ノードから通知された値の論理和を演算する。論理積演算部８９は、論理和演算部９１と９３の演算結果の論理積を演算し、子ノードへ通知する。
【００６２】
構成設定を変更する場合のソフトウェアの処理について説明する。動的構成変更機構について、ソフトウェアとのインターフェイスは、バリア制御レジスタ（ＢＲＣ）を介して行うこととする。ＢＲＣのビットには、ＲＥＴ、ＭＳＫ、ＳＹＮ及びＳＴＴが含まれる。ここで、ＲＥＴ、ＭＳＫ、ＳＹＮ及びＳＴＴは、複数のビットを含む。各ビットは、バリアネットワーク番号に対応する。ＲＥＴ、ＭＳＫ及びＳＹＮは、それぞれ、折返し情報、マスク情報及び同期制御である。ＳＴＴは、書込時は書き込み先を選択し、１は構成情報（ＲＥＴ／ＭＳＫ）、０は同期制御（ＳＹＮ）を書き込む。読出時は同期状態を示し、１は同期完了、０は同期リセット完了を示す。
【００６３】
構成設定を変更する場合には、STTビットに１、RET/MSKに構成情報を書き込む。構成設定を行うバリアネットワークでは、自ノードの設定に変更が無い場合にも書き込みを行わなければならない。構成設定の実施中はSTTビットが１になる。構成設定が完了した場合にはSTTビットが０になり、以降は同期セットが可能になる。構成設定を行った後は、バリアネットワークはリセットされ、同期セット待ち状態になる。
【００６４】
構成設定の完了を待たずに他のバリアネットワークの操作をする場合には、構成設定中のネットワークに対しては同期制御かつ同期リセットをセットしなければならない。BRCレジスタの読み込みだけでは、構成設定中の状態か否かはわからないので、ソフトウェア的に記憶しておく必要がある。構成設定時にSYN=0にしておけば、read-modify-writeすることで構成設定中にバリア同期が開始されることはない。
【００６５】
続いて、本願発明のバリア機構の評価を、バリア同期時間の測定及び回路規模の計数によって行う。本評価では、メニーコアアーキテクチャ評価環境であるSMYLEref（グェンチュオンソン、外４名，FPGAを用いたメニーコアアーキテクチャSMYLErefの評価環境の構築，情報処理学会研究報告，Vol．198，No．15，pp.1-7，2012.参照）のRTL設計を使用した。SMYLErefは、MIPS  R3000アーキテクチャをベースとした複数のコアをバス結合でクラスタ構成し、多数のクラスタを２次元メッシュのオンチップネットワークで結合したアーキテクチャとなっている。本実験では、１クラスタ、16コアのモデルを作成し、16個のコアに対して8つのバリアネットワークを実装した。また、バリア制御のために各コア内にレジスタを実装し、各コアがレジスタを読み書きすることによって、バリア同期を実施可能にした。レジスタは、自コアが使用する葉ノード及び15ある内部ノードと根ノードのうち、一つの構成及び同期を制御する（図１１）。
【００６６】
まず、バリア同期時間測定について説明する。図１２は、バリア同期時間を測定するために使用した評価用プログラムを示す。本評価用プログラムは、最初に各コアが担当する、葉ノード及び内部ノードのマスク情報及び折返し情報をレジスタに書込む（barrier  cong関数）。次にバリア同期の実行（barrier関数）を2回繰り返す。バリア関数を2回実行するのは、関数のプログラムをキャッシュに載せることと、全てのコアが同時に計測対象のバリア関数実行を開始するためである。
【００６７】
barrier関数内では以下の処理を行う。すなわち、（１）状態表示が'0'になるまでレジスタの読込を繰り返す（check  barrier  reset）。（２）同期設定='1'をレジスタに書き込む（barrier  sync  set）。（３）状態表示が'1'になるまでレジスタの読込を繰り返す（check  barrier  set）。（４）同期設定='0'をレジスタに書込む（barrier  sync  reset）。
【００６８】
バリア同期時間としては、2回目のbarrier関数実行に要したクロックサイクル数を計測した。計測は、xilinx社製RTLシミュレータISIM（0.40d版）を使用して行った。また、比較ためにハードウェアバリアを使用しないテストプログラム2種に対しても計測を行った。これらのテストでは、2回目のバリア関数実行前にハードウェアバリア関数を2回実行して、全コアが同時にバリア関数を実行できるようにしている。2種のプログラムは、それぞれ、バリア同期の手法（Wilkinson, B.、外１名，Parallel  Programming：Techniques  and  Applications  Using  Networked  Workstations  and  Parallel  Computers，Prentice  Hall，Upper  Saddle  River，NJ，USA，1999.）が異なっており、一方は小ノード数向けのmaster-slave方式、もう一方は中以上のノード数向けのbuttery方式用いている。
【００６９】
表１は、16コア全てがバリア同期に参加した時の計測結果を示す。単位は、クロックサイクルである。表中の‘種別’は測定対象の種別で、‘HW’はハードウェアバリア、‘MS’はMaster-Slave 方式、‘BUT’はbuttery方式を示す。‘開始最速’、‘開始最遅’、‘完了最速’及び‘完了最遅’は、それぞれ、開始最速を起点とした相対経過クロックサイクル数を示す（図１３）。‘開始最速’はbarrier関数の実行開始が最も早かったコアの相対経過クロックサイクル数で、表中ではここを起点とするため、全ての種別において値は0 となる。‘開始最遅’は、barrier関数の実行開始が最も遅かったコアの相対経過クロック数を示し、‘完了最速’は、barrier関数の完了が最も速かったコア、完了最遅は最も遅かったコアの相対経過クロック数を示す。‘完了-完了’は完了最速と完了最遅のクロック差を示す。‘完了最遅’の値を関数実行レイテンシ、‘完了-完了’をコア間のばらつきと考えると、HWは、MSに対してレイテンシを1/87に、ばらつきを1/79に、BUTに対してはレイテンシを1/66に、ばらつきを1/30に改善している。
【００７０】
【表１】
2014063278.tif 000003
【００７１】
続いて、回路規模評価について説明する。回路規模は、Xilinx社製の論理合成ツールxst（ISE  13.10.40版）を使用して求めた。合成対象FPGAにはVertex-6（ML605評価ボード）を指定している。
【００７２】
表２にバリア同期時間測定に使用したSMYLErefモデルの合成結果、及び、そこからハードウェアバリア部分のみを取り出した合成結果を示す。表中の'Type'は計数された対象で、'LUT'はLUT、'Reg'はレジスタ、'RAM'は36Kbit  RAM(ブロックRAM) を示す。また、'BAR'はバリア同期部分、'SMYLE'はSMYLErefの合成結果を表す。'BAR/S-MYLE'はLUT、Reg及びRAMそれぞれについてSMYLEに対するBARの百分率である。BAR/SMYLEはコアの増加によっては変わらないが、クラスタが増加すれば減少する。コア当たり32KByte程度のメモリに必要な面積のことも鑑みると、SMYRErefメニーコアプロセッサに対してバリアのハードウェア回路は十分に小規模であると考えられる。
【００７３】
【表２】
2014063278.tif 000004
【００７４】
以上より、本実施例では、小規模なハードウェアバリア回路にバリアネットワーク分割機能を持たせ、さらにネットワークを多重化することにより、高速、安定かつ、柔軟なバリア同期を実現する手法を説明した。
【００７５】
実験では、バリア同期時間評価において、ハードウェアバリア機構を使用した場合レイテンシが1/66、ばらつきは1/30となり、提案手法の有効性が示された。また、回路規模評価では、ハードウェアバリア回路はメニーコアプロセッサ全体に対して、LUT数で1,3%、レジスタ数で1.8%であり、小規模なものとなっている。
【符号の説明】
【００７６】
１  コア，３  葉ノード，５  内部ノード，９  折返し記憶部，１１  マスク記憶部，２１  同期設定レジスタ，２３  同期状態表示レジスタ，２５  否定演算部，２７  セレクタ，３１  同期回路，３３  同期状態表示レジスタ，３５  否定演算部，３７  セレクタ，４１  葉ノード，４３  内部ノード，４５  根ノード，５１  葉ノード，５３  内部ノード，５５  根ノード，６１  論理積演算部，６３  論理和演算部，６５  セレクタ，６７  同期記憶部，７１  葉ノード，７３  論理和演算部，７５  論理積演算部，７７  更新レジスタ，８１  論理和演算部，８３、８５、８７、８９  論理積演算部，９１  ９３  論理和演算部，９５  否定演算部，９７  更新レジスタ
【図１】
2014063278.tif 000005
【図２】
2014063278.tif 000006
【図３】
2014063278.tif 000007
【図４】
2014063278.tif 000008
【図５】
2014063278.tif 000009
【図６】
2014063278.tif 000010
【図７】
2014063278.tif 000011
【図８】
2014063278.tif 000012
【図９】
2014063278.tif 000013
【図１０】
2014063278.tif 000014
【図１１】
2014063278.tif 000015
【図１２】
2014063278.tif 000016
【図１３】
2014063278.tif 000017