(57)【特許請求の範囲】
【請求項１】
複数のプロセッサエレメントと、該複数のプロセッサエレメントを結合するネットワークとを有するマルチコアシステムであって、
前記ネットワークは、
前記各プロセッサエレメントから発せられたアクセス及び前記各プロセッサエレメント宛のデータを中継する複数のルータと、
前記各プロセッサエレメントからのアクセスに応じて、該アクセスの対象のデータを要求元のプロセッサエレメント宛に送信するアクセス処理手段と、
を備え、
前記各ルータは、
他のルータ又は前記プロセッサエレメントへ転送したデータ、および、当該データを転送したか否かを示すルーティング経路情報を記憶するキャッシュ機構と、
前記各プロセッサエレメントから発せられたアクセスが転送されてきた際に該アクセスの対象のデータを前記キャッシュ機構に保持している場合には、当該データを前記キャッシュ機構から読み出して要求元のプロセッサエレメント宛に送信する手段と、
を備え、
前記各ルータは、前記キャッシュ機構に保持中のいずれかのデータのルーティング経路情報が、転送先となりうる全てのルータ及びプロセッサエレメントに対してデータを転送済みであることを示す全経路転送済状態となった場合には、当該データが格納されたエントリを、前記ルーティング経路情報が前記全経路転送済状態にないデータが格納されたエントリよりも優先的に書き換えることを特徴とするマルチコアシステム。
【請求項２】
前記アクセス処理手段は、前記複数のプロセッサエレメントによって共有される共有メモリであることを特徴とする請求項１記載のマルチコアシステム。
【請求項３】
前記各ルータのキャッシュ機構は、前記共有メモリのリードオンリー属性の領域に対するリードアクセスの場合、該共有メモリから読み出されたデータを保持することを特徴とする請求項２記載のマルチコアシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、マルチコアシステムに関する。
【背景技術】
【０００２】
従来、複数のプロセッサエレメントと、共有キャッシュメモリとを備えたマルチコアシステムにおいては、各プロセッサと共有キャッシュメモリとは複数のルータを備えたネットワークで接続される（特許文献１参照）。共有キャッシュメモリは、ブリッジを介して外部メモリと接続される。
【０００３】
このようなマルチコアシステムにおいて、各プロセッサエレメントのアクセスは、それぞれ何段かのルータを経由して共有キャッシュメモリに到達する。この場合全てのメモリアクセスが集中するため、通常は共有キャッシュメモリが接続されたルータの負荷が高くなり、これがネットワーク全体のボトルネックとなるという問題がある。
【０００４】
特許文献２には、ＣＰＵと外部装置との間でのデータ転送を中継する通信制御装置にキャッシュを設け、主記憶部のディスクリプタ内のＣＰＵが書き込んだ転送制御情報を読み出して、キャッシュメモリに書き込むことによって、ＣＰＵと通信制御装置との間のデータ転送を効率化することが開示されている。しかし、特許文献２に開示される発明をマルチコアシステムのルータに適用しても、各ルータがキャッシュメモリにデータを書き込もうとして共有キャッシュメモリや外部メモリにアクセスすることとなるため、共有キャッシュメモリに接続されたルータの負荷が高くなってしまうという上記の問題は解決されない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００９−５４０８３号公報
【特許文献２】特開２０００−２０４８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、プロセッサ間ネットワークの特定のルータに負荷が集中することを軽減したマルチコアシステムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
本願発明の一態様によれば、複数のプロセッサエレメントと、該複数のプロセッサエレメントを結合するネットワークとを有するマルチコアシステムであって、ネットワークは、各プロセッサエレメントから発せられたアクセス及び各プロセッサエレメント宛のデータを中継する複数のルータと、各プロセッサエレメントからのアクセスに応じて、該アクセスの対象のデータを要求元のプロセッサエレメント宛に送信するアクセス処理手段と、を備え、各ルータは、他のルータ又はプロセッサエレメントへ転送したデータを保持するキャッシュ機構と、各プロセッサエレメントから発せられたアクセスが転送されてきた際に該アクセスの対象のデータをキャッシュ機構に保持している場合には、当該データをキャッシュ機構から読み出して要求元のプロセッサエレメント宛に送信する手段と、を備えることを特徴とするマルチコアシステムが提供される。
【発明の効果】
【０００８】
本発明によれば、マルチコアシステムのプロセッサ間ネットワークの特定のルータに負荷が集中することを軽減できるという効果を奏する。
【図面の簡単な説明】
【０００９】
【図１】図１は、本発明の第１の実施の形態に係るマルチコアシステムの構成を示すブロック図。
【図２】図２は、第１の実施の形態に係るマルチコアシステムのプロセッサ間ネットワークの概略構成を示す図。
【図３】図３は、ルータ内キャッシュ機構に格納されるデータの構造の一例を示す図。
【図４】図４は、本発明の第２の実施の形態に係るマルチコアシステムでのルータ内キャッシュ機構に格納されるデータの構造の一例を示す図。
【図５】図５は、共有キャッシュメモリに格納されたリードオンリー属性のデータに対してあるプロセッサエレメントがアクセスした状態を示す図。
【図６】図６は、共有キャッシュメモリに格納されたリードオンリー属性のデータに対して別のプロセッサエレメントがアクセスした状態を示す図。
【図７】図７は、共有キャッシュメモリに格納されたリードオンリー属性のデータに対してさらに別のプロセッサエレメントがアクセスした状態を示す図。
【図８】図８は、共有キャッシュメモリに格納されたリードオンリー属性の別のデータに対してあるプロセッサエレメントがアクセスした状態を示す図。
【図９】図９は、発明者が知得した参考例のマルチコアシステムにおけるプロセッサ間ネットワークの概略構成を示す図。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、本発明の実施の形態に係るマルチコアシステムを詳細に説明する。なお、これらの実施の形態により本発明が限定されるものではない。
【００１１】
（第１の実施の形態）
図１は、本発明の第１の実施の形態に係るマルチコアシステムの構成を示すブロック図である。マルチコアシステム１は、複数のプロセッサエレメントＰＥ０〜ＰＥ９と共有キャッシュメモリ１２とが複数のルータを備えたプロセッサ間ネットワーク１１を介して接続された構成である。共有キャッシュメモリ１２は、キャッシュメモリを二つ（Ｍ０、Ｍ１）備えており、ブリッジ１３を介して外部メモリ２へ接続されている。
【００１２】
図２に、本実施の形態に係るマルチコアシステムのプロセッサ間ネットワーク１１の概略構成を示す。プロセッサ間ネットワーク１１は、ルータＲ００〜Ｒ２３が格子点の上に配置されたメッシュ状（格子状）のネットワークトポロジーである。各ルータ００〜Ｒ２３は、キャッシュ機構（ルータ内キャッシュ機構Ｃ００〜Ｃ２３）を備えている。ルータ内キャッシュ機構Ｃ００〜Ｃ２３は、プロセッサエレメントＰＥ０〜ＰＥ９がアクセスするリードオンリーのデータをキャッシュする。ルータ内キャッシュ機構Ｃ００〜Ｃ２３の各々は、一般的なキャッシュメモリと同様に、ＳＲＡＭ（Static Random Access Memory）型のメモリセルとメモリコントローラとを用いて構成可能である。
【００１３】
図３に、ルータ内キャッシュ機構Ｃ００〜Ｃ２３に格納されるデータの構造の一例を示す。ここでは２ウェイのキャッシュを例としているが、特定のウェイ数に限定されることはない。図３に示すように、ルータ内キャッシュ機構Ｃ００〜Ｃ２３は通常のプロセッサの命令キャッシュとほぼ同様の構造でデータを格納しており、ウェイの入れ替え条件を規定するリプレースビットを２ウェイ共通で持ち、有効ビット、タグアドレス、データはウェイごとに持つ。
【００１４】
本実施の形態においては、ルーティングは固定とし、あるプロセッサエレメントがあるキャッシュメモリにアクセスする際の経路は常に一意に決まるものとする。プロセッサエレメントのアクセスやリードデータは、図２に示すプロセッサ間ネットワーク１１内をまず横方向に移動し、その後縦方向に移動するものとする。
【００１５】
具体例を挙げると、プロセッサエレメントＰＥ０又はＰＥ４がキャッシュメモリＭ１にリードアクセスする場合、ＰＥ０／ＰＥ４→Ｒ００→Ｒ０１→Ｒ０２→Ｒ１２→Ｒ２２→Ｍ１という経路でアクセスが伝わる。リードデータは逆に、Ｍ１→Ｒ２２→Ｒ１２→Ｒ０２→Ｒ０１→Ｒ００→ＰＥ０／ＰＥ４という経路でキャッシュメモリＭ１からプロセッサエレメントＰＥ０又はＰＥ４へ伝わる。
【００１６】
別の一例を挙げると、プロセッサエレメントＰＥ２がキャッシュメモリＭ０にリードアクセスする場合は、ＰＥ２→Ｒ０２→Ｒ０１→Ｒ１１→Ｒ２１→Ｍ０という経路でアクセスが伝わる。リードデータは逆に、Ｍ０→Ｒ２１→Ｒ１１→Ｒ０１→Ｒ０２→ＰＥ２という経路でキャッシュメモリＭ０からプロセッサエレメントＰＥ２へ伝わる。
【００１７】
一方、共有キャッシュメモリ１２のリードオンリー属性ではない領域に対するリードアクセスは、全てが共有キャッシュメモリ１２に到達し、共有キャッシュメモリ１２（キャッシュメモリＭ０、Ｍ１）から読み出されたリードデータが要求元（リードアクセスの送信元）のプロセッサエレメントへ戻される。
【００１８】
ルータ内キャッシュ機構Ｃ００〜Ｃ２３は、各プロセッサエレメントＰＥ０〜ＰＥ９のリードアクセスが共有キャッシュメモリ１２のリードオンリー属性の領域に対して行われた場合に動作する。リードアクセスが共有キャッシュメモリ１２のリードオンリー属性の領域に対してであるか否かは、各プロセッサエレメントのＭＭＵ（Memory Management Unit）情報などをリード要求とともに各ルータＲ００〜Ｒ２３に伝えていくことで、ルータＲ００〜Ｒ２３において判断する。
【００１９】
いずれかのプロセッサエレメントが共有キャッシュメモリ１２のリードオンリー属性の領域に対してアクセスした場合、そのアクセスは共有キャッシュメモリ１２に到達するまでに通る各ルータでチェックされる。アクセスを中継するいずれかのルータがアクセスの対象のデータをルータ内キャッシュ機構Ｃ００〜Ｃ２３にキャッシュしている場合には、そのルータは、アクセスの対象のデータをリードデータとして読み出して、アクセス元のプロセッサエレメント宛に送信する。途中のどのルータのルータ内キャッシュ機構Ｃ００〜Ｃ２３にもアクセスの対象のデータが無かった場合には、プロセッサエレメントのリード要求は共有キャッシュメモリ１２（キャッシュメモリＭ０、Ｍ１）まで伝わり、共有キャッシュメモリ１２からリードデータが送信される。
【００２０】
共有キャッシュメモリ１２から送信されたリードデータ（又は、ルータ内キャッシュ機構Ｃ００〜Ｃ２３でヒットしてルータＲ００〜Ｒ２３から送信されたリードデータ）は、リードデータが通る経路上の各ルータＲ００〜Ｒ２３のルータ内キャッシュ機構Ｃ００〜Ｃ２３にキャッシュされる。
【００２１】
このような動作を行うことにより、ルータ内キャッシュ機構Ｃ００〜Ｃ２３でアクセスの対象のデータがヒットした場合には、リードアクセスが共有キャッシュメモリ１２まで到達しないため、共有キャッシュメモリ１２に接続されたルータＲ２１、Ｒ２２で起こるアクセス集中を緩和できる。
【００２２】
比較のために、図９に、発明者が知得した参考例のマルチコアシステムにおけるプロセッサ間ネットワーク１１’の概略構成を示す。これは、図１におけるプロセッサ間ネットワーク１１に相当する構成である。このネットワーク構成においては、各プロセッサエレメントＰＥ０’〜ＰＥ９’から共有キャッシュメモリ１２’（キャッシュメモリＭ０’、Ｍ１’）へのアクセスは、共有キャッシュメモリ１２’と直に接続されているルータ（Ｒ２１’、Ｒ２２’）に集中する。したがって、ルータＲ２１’、Ｒ２２’に高い負荷がかかってネットワーク全体としてのボトルネックとなる。
【００２３】
なお、本実施の形態においては、共有キャッシュメモリ１２のリードオンリー属性の領域に対するリードアクセスと他のアクセス（共有キャッシュメモリ１２のリードオンリー属性ではない領域に対するリードアクセス、ライトアクセス）とでルーティングポリシーを変更しても良い。
例えば、上記の横方向→縦方向のルーティングポリシーを適用する場合、ルータＲ１１は八つのプロセッサエレメント（ＰＥ０〜ＰＥ５、ＰＥ７、ＰＥ８）に関してのアクセス及びデータを中継する可能性があり、ルータＲ２０は一つのプロセッサエレメント（ＰＥ６）に関してのアクセス及びデータを中継する可能性があることとなる。一方、縦方向→横方向のルーティングポリシーを適用した場合には、ルータＲ１１は一つのプロセッサエレメント（ＰＥ１）に関してのアクセス及びデータを中継する可能性があり、ルータＲ２０は四つのプロセッサエレメント（ＰＥ０、ＰＥ４〜ＰＥ６）に関してのアクセス及びデータを中継する可能性があることとなる。したがって、リードオンリー属性の領域に対するリードアクセスと他のアクセスとでルーティングポリシーを変更することで、各ルータＲ００〜Ｒ２３にかかる負荷の差異を低減できる。
【００２４】
また、マルチコアシステム１において、各プロセッサエレメントＰＥ０〜ＰＥ９から外部メモリ２へのアクセスや外部メモリ２から各プロセッサエレメントＰＥ０〜ＰＥ９へのデータの転送は、共有キャッシュメモリ１２及びブリッジ１３を介して行われる。したがって、外部メモリ２へのアクセスに関してもルータ内キャッシュ機構Ｃ００〜Ｃ２３にリードデータをキャッシュすることで、共有キャッシュメモリ１２に直に接続されたルータＲ２１、Ｒ２２に対するアクセス集中を緩和できる。なお、外部メモリ２が共有キャッシュメモリ１２を介さずに接続された構成であっても同様である。
【００２５】
このように、本実施の形態に係るマルチコアシステムは、各ルータにルータ内キャッシュ機構を設けたため、各プロセッサエレメントのリード要求が必ずしも共有キャッシュメモリまで到達するとは限らない。また、ルータ内キャッシュ機構にキャッシュされるデータは、他のルータやプロセッサエレメントへ中継したデータであり、ルータが自発的に共有キャッシュメモリにアクセスしてデータをキャッシュすることはない。このため、共有キャッシュメモリに直に接続されたルータに対するアクセス集中が緩和されるため、プロセッサ間ネットワーク全体としてのボトルネックを解消できる。
【００２６】
（第２の実施の形態）
本発明の第２の実施の形態に係るマルチコアシステムについて説明する。マルチコアシステム全体の構成及びプロセッサ間ネットワークの概略構成は第１の実施の形態と同様である。ただし、本実施の形態においては、ルータ内キャッシュ機構Ｃ００〜Ｃ２３の構造が第１の実施の形態とは相違する。
【００２７】
図４に、ルータ内キャッシュ機構Ｃ００〜Ｃ２３に格納されるデータの構造の一例を示す。本実施の形態においては、各ウェイのエントリごとにルーティング経路ビットを備える。このビットは、リードデータを転送する可能性があるルータ（又はプロセッサエレメント）の数だけあり、どの経路に対してキャッシュエントリのリードデータを転送したかを記憶する。例えば、ルータＲ１１は、リードデータをルータＲ０１、Ｒ１０、Ｒ１２に転送する可能性があるため、これらのルータに対応した３ビットのルーティング経路ビットを各ウェイのエントリに持つ。また、ルータＲ００は、リードデータをプロセッサエレメントＰＥ０、ＰＥ４へ転送する可能性があるため、これらのプロセッサエレメントに対応した２ビットのルーティング経路ビットを各ウェイのエントリに持つ。
【００２８】
ルーティング経路ビットの変化の一例について、図５〜図８を用いて説明する。図５〜図８は、キャッシュメモリＭ０に格納されたリードオンリー属性のデータdataAに対してプロセッサエレメントＰＥ５、ＰＥ１、ＰＥ８が順番にアクセスした後に、キャッシュメモリＭ０に格納されたリードオンリー属性のデータdataBにプロセッサエレメントＰＥ１がアクセスした場合の動作を時系列に沿って示すものである。なお、dataBは、ルータ内キャッシュ機構Ｃ００〜Ｃ２３でdataAと同じエントリに格納されるデータ（エントリアドレスが同一のデータ）であるとする。
【００２９】
図５に、キャッシュメモリＭ０に格納されたリードオンリー属性のデータdataAに対してプロセッサエレメントＰＥ５がアクセスした状態を示す。プロセッサエレメントＰＥ５がdataAにアクセスした際には、リード要求はＰＥ５→Ｒ１０→Ｒ１１→Ｒ２１→Ｍ０と伝わっていき、リードデータはＭ０→Ｒ２１→Ｒ１１→Ｒ１０→ＰＥ５という順番で各ルータを伝わっていく。ルータＲ２１、Ｒ１１、Ｒ１０では、それぞれdataAがルータ内キャッシュ機構に格納される。
【００３０】
ルータＲ１１のルータ内キャッシュ機構Ｃ１１では、dataAが格納されたウェイ／エントリのルーティング経路ビットのルータＲ１０に対応するビットに“１”が入り、他の経路であるルータＲ０１、Ｒ１２に対応するビットには“０”が入る。
【００３１】
図６に、キャッシュメモリＭ０に格納されたリードオンリー属性のデータdataAに対してプロセッサエレメントＰＥ１がアクセスした状態を示す。プロセッサエレメントＰＥ１がdataAにアクセスした際には、リード要求はＰＥ１→Ｒ０１→Ｒ１１と伝わっていき、ルータＲ１１でキャッシュがヒットするため、ルータ内キャッシュ機構Ｃ１１からdataAが読み出され、リードデータはＲ１１→Ｒ０１→ＰＥ１という順番で各ルータを伝わっていく。このとき、ルータＲ０１では、dataAがルータ内キャッシュ機構Ｃ０１に格納される。
【００３２】
ルータＲ１１のルータ内キャッシュ機構Ｃ１１では、dataAが格納されたウェイ／エントリのルーティング経路ビットのルータＲ０１に対応するビットが“０”から“１”へ変更される。
【００３３】
図７に、キャッシュメモリＭ０に格納されたリードオンリー属性のデータdataAに対してプロセッサエレメントＰＥ８がアクセスした状態を示す。プロセッサエレメントＰＥ８がdataAにアクセスした際には、リード要求はＰＥ８→Ｒ１３→Ｒ１２→Ｒ１１と伝わっていき、ルータＲ１１でキャッシュがヒットするため、ルータ内キャッシュ機構Ｃ１１からdataAが読み出され、リードデータはＲ１１→Ｒ１２→Ｒ１３という順番で各ルータを伝わっていく。このとき、ルータＲ１２、Ｒ１３では、dataAがルータ内のキャッシュ機構Ｃ１２、Ｃ１３に格納される。
【００３４】
ルータＲ１１のルータ内キャッシュ機構Ｃ１１では、dataAが格納されたウェイ／エントリのルーティング経路ビットのルータＲ１２に対応するビットが“０”から“１”へ変更される。ルータ内キャッシュ機構Ｃ１１は、このタイミングにおいて、dataAが格納されたウェイ／エントリのルーティング経路ビットが３ビット全て“１”となる。３ビット全てが“１”になったということは、データの転送先となりうるルータ（ルータＲ１０、Ｒ０１、Ｒ１２）にも同じデータがキャッシュされたことを示す。これは、ルータＲ１１のルータ内キャッシュ機構にdataAをキャッシュしておく必要が無くなったことを意味する。
【００３５】
図８に、キャッシュメモリＭ０に格納されたリードオンリー属性のデータdataBに対してプロセッサエレメントＰＥ１がアクセスした状態を示す。プロセッサエレメントＰＥ１がdataBにアクセスした際には、リード要求はＰＥ１→Ｒ０１→Ｒ１１→Ｒ２１→Ｍ０と伝わっていき、リードデータは、Ｍ０→Ｒ２１→Ｒ１１→Ｒ０１→ＰＥ１という順番で各ルータを伝わっていく。ルータＲ２１、Ｒ１１、Ｒ０１では、それぞれdataBがルータ内キャッシュ機構Ｃ２１、Ｃ１１、Ｃ０１に格納される。
【００３６】
この時点では、ルータＲ１０、Ｒ２１に関しては、dataAが格納されたウェイ／エントリのルーティング経路ビットは全て“１”になっていないため、dataBを格納するに当たってデータのリプレースが必要な場合には、リプレースされるデータは、通常のリプレースポリシー（ＬＲＵ（Least Recently Used）など）が適用されて、リプレースビットに基づいて決定される。dataBが格納されたウェイ／エントリのルーティング経路ビットのルータＲ１１又はプロセッサエレメントＰＥ１に対応するビットには“１”が入り、他の経路であるルータＲ２０、Ｒ２２又はルータＲ００、Ｒ０２に対応するビットには“０”が入る。
【００３７】
一方、ルータＲ１１に関しては、ルータ内キャッシュ機構Ｃ１１にdataBを格納する際には、dataAに対応するルーティング経路ビットが３ビット全て“１”となっており、dataAが不要であることが分かっている。このため、dataAが入っているウェイの有効ビットが“０”（無効）となっていない限り、通常のリプレースポリシーとは関係なくdataBは必ずdataAが入っている側のウェイに格納される（換言すると、通常のルーティングポリシーとは無関係にdataAを上書きして消去する）。dataBが格納されたウェイ／エントリのルーティング経路ビットのルータＲ０１に対応するビットには“１”が入り、他の経路であるルータＲ１０、Ｒ１２に対応するビットには“０”が入る。
【００３８】
このように、本実施の形態においては、リードデータの転送先に同じ情報がキャッシュされているか否かをルーティング経路ビットに基づいて判断するため、各ルータのルータ内キャッシュ機構が同じデータを重複して持つことを減らし、ルータ内キャッシュ機構を有効に活用できる。
【００３９】
以上の説明においては、ルーティング経路ビットに基づいて、データのリプレースの優先度を変更する動作について説明したが、任意のルータにおいて、ルーティング経路ビットのうちの所定の割合（例えば過半数）が“１”となったら、その時点でルーティング経路ビットが“０”のルータやプロセッサエレメントへデータを転送するように動作させることも可能である。
【００４０】
なお、上記各実施の形態は本発明の実施の一例であり、本発明はこれらに限定されることはない。
例えば、上記各実施の形態においては、共有キャッシュメモリに直に接続されたルータへのアクセス集中を低減する構成を例としたが、外部メモリ（ブリッジ）や他と比べて稼働率が高いプロセッサエレメントに直に接続されたルータへのアクセスの集中を緩和する構成をとることも可能である。
また、プロセッサ間ネットワークのトポロジーは正方格子状のメッシュ型に限定されることはなく、他の形状（正方格子状ではない任意のメッシュ型、ハイパーキューブ型など）であっても良い。
このように、本発明は様々な変形が可能である。
【符号の説明】
【００４１】
１  マルチコアシステム、２  外部メモリ、１１  プロセッサ間ネットワーク、１２  共有キャッシュメモリ、１３  ブリッジ、ＰＥ０〜ＰＥ９  プロセッサエレメント、Ｒ００〜Ｒ２３  ルータ、Ｃ００〜Ｃ２３  ルータ内キャッシュ機構、Ｍ０、Ｍ１  キャッシュメモリ。
【図１】
0005404433.tif 000002
【図２】
0005404433.tif 000003
【図３】
0005404433.tif 000004
【図４】
0005404433.tif 000005
【図５】
0005404433.tif 000006
【図６】
0005404433.tif 000007
【図７】
0005404433.tif 000008
【図８】
0005404433.tif 000009
【図９】
0005404433.tif 000010