マルチプロセッサ
【課題】キャッシュラインの転送時の消費電力を低減したマルチプロセッサを提供する。
【解決手段】メインメモリ2と、その記憶データを一時記憶するL1キャッシュメモリ11a〜11dを備える複数のプロセッサユニット1a〜1dと、L1キャッシュメモリ11a〜11dのコヒーレンシを管理するCMU3とを備え、CMU3は、L1キャッシュメモリに格納されたキャッシュラインのタグを格納するL1タグキャッシュ33a〜33dと、プロセッサユニット1a〜1dからのリフィル要求に応じてインターベンション転送を行うCMUコントローラ31と、インターベンション転送を監視することによって、転送先別に転送元を予測するPIU32とを有し、CMUコントローラ31は、PIU32の予測結果が得られた後は、予測された転送元に対応するタグキャッシュのみを活性化して、リフィル要求に対応するキャッシュラインがキャッシュされているかを判別する。
【解決手段】メインメモリ2と、その記憶データを一時記憶するL1キャッシュメモリ11a〜11dを備える複数のプロセッサユニット1a〜1dと、L1キャッシュメモリ11a〜11dのコヒーレンシを管理するCMU3とを備え、CMU3は、L1キャッシュメモリに格納されたキャッシュラインのタグを格納するL1タグキャッシュ33a〜33dと、プロセッサユニット1a〜1dからのリフィル要求に応じてインターベンション転送を行うCMUコントローラ31と、インターベンション転送を監視することによって、転送先別に転送元を予測するPIU32とを有し、CMUコントローラ31は、PIU32の予測結果が得られた後は、予測された転送元に対応するタグキャッシュのみを活性化して、リフィル要求に対応するキャッシュラインがキャッシュされているかを判別する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、キャッシュメモリを備えたプロセッサを複数備え、各プロセッサのキャッシュメモリ間でキャッシュコヒーレンシを保つマルチプロセッサに関する。
【背景技術】
【0002】
従来、キャッシュメモリを備えたプロセッサを複数有するマルチプロセッサにおいて、任意のプロセッサでキャッシュミスが発生した場合、マルチプロセッサ内でキャッシュコヒーレンシを管理するコヒーレンシ管理ユニットは、各プロセッサのキャッシュメモリに対応して設けられた全てのタグメモリを活性化し、リフィル対象となるキャッシュラインの有無を確認していた。
【0003】
また、リフィル対象となるキャッシュラインの有無を確認した結果、リフィル対象となるキャッシュラインが複数のキャッシュメモリ内に存在した場合、コヒーレンシ管理ユニットは、キャッシュミスしたキャッシュメモリへキャッシュラインを転送する際にマルチプロセッサ内(キャッシュメモリ、共有バス、調停回路等)で消費される消費電力を考慮に入れずにキャッシュラインの転送を行っていた。
【0004】
しかしながら、従来技術では、リフィル対象となるキャッシュラインの有無の確認や、キャッシュラインの転送は、消費電力の観点からは非効率的であるという問題があった。
【0005】
共有メモリマルチプロセッサにおいて、コヒーレンシを維持するデータブロックに対してライト動作を行う際に、データを共有化していたため無効化されるプロセッサをシフトレジスタに格納し、ライト結果を予測先のプロセッサに転送して性能の向上を図る技術が特許文献1に開示されているが、あるデータブロックにライトが発生したタイミングで投機的に予測を行い、実際に必要とされる前に転送するため、予測の精度が低く、必ずしも性能向上に繋がらないという問題があった。
【先行技術文献】
【特許文献】
【0006】
【特許文献1】特開2002−49600号公報
【発明の概要】
【発明が解決しようとする課題】
【0007】
本発明は、キャッシュメモリ間でのキャッシュラインの転送時の消費電力を低減したマルチプロセッサを提供することを目的とする。
【課題を解決するための手段】
【0008】
本願発明の一態様によれば、主記憶装置と、主記憶装置の記憶データを一時記憶するキャッシュメモリを夫々備え、主記憶装置を共有する複数のプロセッサと、複数のプロセッサのキャッシュメモリのコヒーレンシを管理するコヒーレンシ管理ユニットと、を備え、コヒーレンシ管理ユニットは、キャッシュメモリの各々に対応して設けられ、対応するキャッシュメモリにキャッシュされたキャッシュデータのタグを格納する複数のタグキャッシュと、プロセッサからのリフィル要求に応じて、複数のタグキャッシュを参照してリフィル要求に対応するキャッシュデータがキャッシュされたキャッシュメモリを判別し、判別したキャッシュメモリを転送元としリフィル要求元のキャッシュメモリを転送先としてリフィル要求に対応するキャッシュデータの転送を行うデータ転送手段と、キャッシュメモリ間のキャッシュデータの転送の監視に基づく所定の予測処理を行うことで、転送先別に一つの転送元を仮決定する仮決定手段とを有し、データ転送手段は、仮決定手段の仮決定結果が得られた後は、キャッシュデータの転送を行う際、仮決定した一つの転送元に対応するタグキャッシュのみを活性化し、活性化されたタグキャッシュのみを参照してリフィル要求に対応するキャッシュデータがキャッシュされているか否かを判別することを特徴とするマルチプロセッサが提供される。
【発明の効果】
【0009】
本発明によれば、キャッシュメモリ間でのキャッシュラインの転送時の消費電力を低減したマルチプロセッサを提供できるという効果を奏する。
【図面の簡単な説明】
【0010】
【図1】図1は、本発明の第1の実施の形態にかかるマルチプロセッサの構成を示す図。
【図2】図2は、第1の実施の形態にかかるマルチプロセッサが四つのプロセッサユニットでプログラムを並列実行する場合の動作の流れを示す図。
【図3】図3は、プロセッサユニットが、処理対象となるデータへアクセスし、キャッシュミスを起こした状態を示す図。
【図4】図4は、キャッシュメモリラインをリフィル要求元であるプロセッサユニットへとインターベンション転送する状態を示す図。
【図5】図5は、PIUがインターベンション予測モードへ切り替わった後でのインターベンション転送時の動作を示す図。
【図6】図6は、2段階閾値方式によるインターベンション予測モードの解除方式を示す図。
【図7】図7は、インターバルカウンタを用いたインターベンション予測モードの解除方式を示す図。
【図8】図8は、各プロセッサユニットにインターベンション予測ユニットを分散配置したマルチプロセッサの構成の一例を示す図。
【図9】図9は、本発明の第2の実施の形態にかかるマルチプロセッサの構成を示す図。
【図10】図10は、第2の実施の形態にかかるマルチプロセッサが二つのプロセッサユニットでプログラムを並列実行する場合の動作の流れを示す図。
【図11】図11は、キャッシュメモリラインをリフィル要求元であるプロセッサユニットへとインターベンション転送する状態を示す図。
【図12】図12は、プロセッサユニットが、処理対象となるデータへアクセスし、キャッシュミスを起こした状態を示す図。
【図13】図13は、キャッシュメモリラインをリフィル要求元であるプロセッサユニットへとインターベンション転送する状態を示す図。
【図14】図14は、PIUがインターベンション予測モードへ切り替わった後でのインターベンション転送時の動作を示す図。
【図15】図15は、本発明の第3の実施の形態にかかるマルチプロセッサの構成を示す図。
【図16】図16は、インターベンション転送が行われ、PIカウンタの対応するプロセッサペアのカウンタがインクリメントされる状態を示す図。
【図17】図17は、インターベンション転送が行われ、PIカウンタの対応するプロセッサペアのカウンタがインクリメントされる状態を示す図。
【図18】図18は、インターベンション予測モードが有効になった状態においては、一つのL1タグキャッシュのみを引くことでヒットを得た状態を示す図。
【図19】図19は、各プロセッサユニット、CMU、メインメモリをリングバスによって接続したマルチプロセッサの構成の一例を示す図。
【図20】図20は、リングバス形態のマルチプロセッサにおけるインターベンション転送の様子を示す図。
【図21】図21は、リングバス形態のマルチプロセッサにおけるインターベンション転送の様子を示す図。
【図22】図22は、本発明の第4の実施の形態にかかるマルチプロセッサの構成を示す図。
【図23】図23は、プロセッサユニットが同じメモリ領域に対して、「sc」によってメモリ領域へのロック変数を書き込む際の様子を示す図。
【図24】図24は、インターベンション予測モードがオンした後に、L1キャッシュメモリでキャッシュミスが発生した様子を示す図。
【発明を実施するための形態】
【0011】
以下に添付図面を参照して、本発明の実施の形態にかかるマルチプロセッサを詳細に説明する。なお、これらの実施の形態により本発明が限定されるものではない。
【0012】
(第1の実施の形態)
図1は、本発明の第1の実施の形態にかかるマルチプロセッサの構成を示す図である。
マルチプロセッサは、プロセッサユニット1(1a〜1d)、メインメモリ2、及びコヒーレンシマネージメントユニット3(CMU:Coherency Management Unit)を有する。なお、以下の説明においては、必要に応じてプロセッサユニット1a、1b、1c、1dをそれぞれPU−A、PU−B、PU−C、PU−Dと省略して表記する。
【0013】
プロセッサユニット1a〜1dは、演算処理及び命令実行を司っており、内部にはL1キャッシュメモリ(1次キャッシュメモリ)11a〜11dを備えている。L1キャッシュメモリ11a〜11dは、データフィールド及びタグフィールドを含んだキャッシュラインを格納している。プロセッサユニット1a〜1dは、自身が内包するL1キャッシュメモリ11a〜11dに対するアクセス時には、キャッシュライン中に含まれるタグに基づいてキャッシュヒット/キャッシュミスを判断し、キャッシュヒットの場合にはヒットしたキャッシュライン中のデータに対してアクセスし、キャッシュミスの場合にはリフィル要求をCMU3へ出力する。なお、プロセッサユニット1a〜1dが仮想アドレスを使用する場合、L1キャッシュメモリ11a〜11d内のタグは仮想アドレスで表されることとなる。
【0014】
CMU3は、マルチプロセッサ内部のキャッシュコヒーレンシを管理する。CMU3は、CMUコントローラ31、インターベンション予測ユニット(PIU:Predicting Intervention Unit )32、L1タグキャッシュ33(33a〜33d)、L2キャッシュメモリ(2次キャッシュメモリ)34、L2タグキャッシュ35を有する。
【0015】
L1タグキャッシュ33a〜33dは、L1キャッシュメモリ11a〜11dのそれぞれに対応して設けられており、L1キャッシュメモリ11a〜11dにおけるタグ(アドレス)を記憶する。また、L2キャッシュメモリ34は、データを記憶し、L2タグキャッシュ35は、そのタグ(L2キャッシュメモリ34におけるアドレス)を記憶する。なお、プロセッサユニット1a〜1dが仮想アドレスを使用する場合でも、L1タグキャッシュ33a〜33d内のタグは実アドレスで表されるため、CMU3はメモリ管理ユニット(MMU:Memory Management Unit)を備えた構成となり、MMUにおいて仮想アドレスと実アドレスとの変換を行うこととなる。
CMUコントローラ31は、CMU3の制御系統を担う。具体的には、プロセッサユニット1a〜1dからのリフィル要求に応じてタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)を参照して、キャッシュヒット/キャッシュミスを得る。そして、キャッシュヒット時には、ヒットしたキャッシュメモリを転送元として、リフィル要求元のプロセッサユニットへのキャッシュラインの転送を行う。一方、キャッシュミス発生時にはメインメモリ2を転送元として、リフィル要求元のプロセッサユニットへのキャッシュラインの転送を行う。また、CMUコントローラ31は、プロセッサユニット1a〜1dによるライト動作が行われた場合やキャッシュライン転送を行った場合にL1タグキャッシュ33a〜33dを最新のタグ情報に更新する処理や、スヌープ制御(複数のキャッシュメモリによって共有されているアドレスに対して任意のキャッシュメモリが更新を行う場合、そのアドレスはダーティであるとして共有している他のキャッシュメモリの該当ラインを無効化する処理等)なども行う。PIU32は、スヌープ制御に伴うL1キャッシュメモリ11a〜11d間でのキャッシュラインの転送(以下、インターベンション転送という。)の傾向を予測する。
【0016】
なお、L1キャッシュメモリ11a〜11dについても、L2キャッシュメモリ34と同様に、データだけ記憶する構成とすることも可能である。ただし、この場合には、プロセッサユニット1a〜1dが内包するL1キャッシュメモリ11a〜11dに対してアクセスする場合にも、CMUコントローラ31においてキャッシュヒット/キャッシュミスを判断する必要があるため、CMU3の負荷が増大してしまう。このため、L1キャッシュメモリ11a〜11dには、データとともにタグを記憶させておき、プロセッサユニット1a〜1dでキャッシュミスが発生した場合にのみCMU3へリフィル要求を出力することが好ましい。
【0017】
PIU32は、内部にインターベンション予測用カウンタ(PIカウンタ)321を有する。PIカウンタ321の内部には、各プロセッサユニット間のインターベンション転送に対応したカウンタや、予測モードオンに切り替わる閾値を記憶する記憶装置が存在しており、プロセッサ間転送の組ごとにカウントが可能である。四つのプロセッサユニット1a〜1dを備えたシステムにおいては、プロセッサユニット1a〜1dのいずれに関してもインターベンション転送元となりうるのは、L1キャッシュメモリ11a〜11d及びL2キャッシュメモリ34の五つであるから、PIカウンタ321は、5×4=20通りの転送を個別にカウントする。すなわち、PIカウンタ321は、PU−A←PU−A、PU−A←PU−B、PU−A←PU−C、PU−A←PU−D、PU−A←L2、PU−B←PU−A、PU−B←PU−B、PU−B←PU−C、PU−B←PU−D、PU−B←L2、PU−C←PU−A、PU−C←PU−B、PU−C←PU−C、PU−C←PU−D、PU−C←L2、PU−D←PU−A、PU−D←PU−B、PU−D←PU−C、PU−D←PU−D、PU−D←L2の20通りのインターベンション転送を個別にカウントする。
【0018】
なお、マルチプロセッサの構成の一般性を鑑み、CMU3内部にL2キャッシュメモリ34及びL2タグキャッシュ35を配置したが、これらが存在していなくても良く、必要に応じて省略することも可能である。
【0019】
さらに、CMU3と各プロセッサ1やメインメモリ2との接続方法は、図1とは異なる方式、例えばバス接続であっても良い。
【0020】
また、図1においては、マルチプロセッサ内にプロセッサが四つ(1a〜1d)配置された構成を示したが、プロセッサの数は2以上であれば任意である。これは、キャッシュラインの転送は、異なるL1キャッシュメモリ間での転送に限定される訳ではなく、同一のL1キャッシュメモリ内で行われる可能性があるためである。すなわち、プロセッサ数が2のマルチプロセッサであっても、リフィル対象となるキャッシュラインの有無を確認するためには、マルチプロセッサ内の複数のキャッシュメモリのタグメモリを活性化する必要があるためである。
具体例を挙げてより詳しく説明すると、プロセッサが仮想アドレスを使用する場合、L1キャッシュメモリでキャッシュミスが発生した際にプロセッサユニットから送出されるリフィル要求は、キャッシュラインが仮想アドレスで指定されることとなる。そして、MMUにおいて仮想アドレスを実アドレスに変換した結果、所望のメモリラインがリフィル要求の送出元のプロセッサのL1キャッシュメモリに存在することが判明する場合もある。この場合には、同一のプロセッサユニットのL1キャッシュメモリ内でキャッシュラインの転送が行われる。
従って、プロセッサ数が2、且つ二次キャッシュを省略した構成であっても、インターベンション転送の転送元は一義に定まらず、リフィル対象となるキャッシュラインの有無を確認するためには、マルチプロセッサ内の全キャッシュメモリのタグメモリを活性化する必要がある。
【0021】
続いて、PIU32の予測方式について、説明する。
図2に、本実施形態にかかるマルチプロセッサが四つのプロセッサユニット1a〜1dでプログラムを並列実行する場合の動作の流れを示す。ここで、プログラム内にオペレーション0〜3の処理が存在し、それぞれをプロセッサユニット1a〜1dが処理を担当するものとする。この場合、各プロセッサユニット1は、処理対象となるデータや、処理を行うための命令コードをメインメモリ2から自己の内部に存在するL1キャッシュメモリ11a〜11dに取り込むことで処理の高速化を図る。
【0022】
図2の処理フローからも明らかなように、プロセッサユニット1a〜1cで処理を終えたキャッシュデータは、次の処理を行うプロセッサユニット1b〜1dに転送され、次のプロセッサユニット1b〜1dで後続の処理を行う。なお、実際には、キャッシュデータは、次のプロセッサユニット1b〜1dにおけるキャッシュミスとインターベンション転送を伴うリフィル動作とによって転送される。
【0023】
ここでは、プロセッサユニット1aでオペレーション0の処理を終えたデータを含むキャッシュラインが、後続のオペレーション1の処理を行うプロセッサユニット1bに転送され、処理を続けるという動作を説明する。
【0024】
図3は、プロセッサユニット1bが、処理対象となるデータへアクセスし(実際には、プロセッサユニット1b内のL1キャッシュメモリ11bへアクセスし)、キャッシュミスを起こした状態を示している。ここで、L1キャッシュメモリ11bのリフィルを行うため、プロセッサユニット1bからのリフィル要求がCMU3に通達される。CMUコントローラ31は、CMU3内部に存在するタグキャッシュメモリへアクセスし、要求されたキャッシュラインがマルチプロセッサ内に存在するか否かを判断する。この時点では、PIU32による転送の予測はされていないため、CMUコントローラ31は全てのタグキャッシュメモリ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)にアクセスする必要がある。図中に網掛けで示す部分が、ハードウェア(ロジック・メモリなど、以下、HW(HardWare)と略記する。)が駆動されて電力を消費している部分である。全タグキャッシュへのアクセスとアドレス比較との結果、要求されたキャッシュラインがプロセッサユニット1a内のL1キャッシュメモリ11aに存在することが判明する。プロセッサユニット1bの前段の処理を行うプロセッサユニット1a内のL1キャッシュ11aに存在する可能性が高いことは、プログラム実行フローからも明らかである。
【0025】
続いて、CMUコントローラ31は、図4に示すように、L1キャッシュメモリ11a内のキャッシュメモリラインをリフィル要求元であるプロセッサユニット1bへとインターベンション転送する。この際に、PIカウンタ321の値をインクリメントする。図4においては、プロセッサユニット1aからプロセッサユニット1bへとキャッシュラインのインターベンション転送が発生したため、20個のカウンタのうちのPU−AからPU−Bへのインターベンション転送に対応する「PUb←PUa予測用カウンタ」がインクリメントされる。
【0026】
PIU32は、PIカウンタ321の値に基づいて、アクセス先となるキャッシュメモリを限定する「インターベンション予測モード」へ切り替わることで、特定プロセッサ(L1キャッシュメモリ)ペア間のインターベンション転送時におけるHW駆動率を低下させ、マルチプロセッサの消費電力を低減させる。なお、以下の説明では、「インターベンション予測モード」へ切り替わった後の状態のことを、「インターベンション予測モードが有効である。」という。
【0027】
ここで、PIU32がインターベンション予測モードへ切り替わるためには、PIカウンタ321のカウンタ値が「インターベンション予測モードオン閾値(以下、予測モードオン閾値)」を超える必要がある。図2に示す処理フローのように、プロセッサユニット1aからプロセッサユニット1bへ処理とともにキャッシュデータが受け継がれて処理が行われる場合、プロセッサユニット1aからプロセッサユニット1bへのインターベンション転送が多発するため、カウンタ値が予測モードオン閾値を超えることが想定される。
【0028】
図5は、過去に行われたインターベンション転送によってPIカウンタ321のPUb←PUa予測用カウンタ値が予測モードオン閾値を超え、PIU32がインターベンション予測モードへ切り替わった後の動作(換言すると、インターベンション予測モードが有効である場合の動作)を示している。図5において、プロセッサユニット1bのL1キャッシュメモリ11bでキャッシュミスが発生し、CMU3にリフィル要求が届いている。この時、PIU32はインターベンション予測モードにあり、L1キャッシュメモリ11bが要求するキャッシュラインは、L1キャッシュメモリ11aに存在すると予測する。予測の無い状態では全てのタグキャッシュを読み出す必要があるが、PIU32の予測に従ってL1キャッシュメモリ11aに関連したL1タグキャッシュ33aのみを読み出すことで、消費電力の低減が達成されている。
【0029】
図2に示すような処理フローにおいては、高い確率で予測が当たり、L1タグキャッシュ33aからヒットが得られる。CMUコントローラ31によってヒットが確認できた後、L1キャッシュメモリ11aからL1キャッシュメモリ11bへとキャッシュラインのインターベンション転送が行われる。
【0030】
次に、有効になったインターベンション予測モードを解除する方式について説明する。
インターベンション予測モードの解除方式の例としては、
・2段階閾値による解除方式。
・インターバルカウンタによる解除方式。
・予測失敗による解除方式。
が挙げられる。
【0031】
まず、2段階閾値による解除方式について説明する。この場合には、図6に示すように、PIカウンタ321は、2段階の閾値を設定可能に構成する。PIU32内のPIカウンタ321が予測モードオン閾値「Mode_on_Th」を超える(又は同値に達する)ことでPIU32のインターベンション予測モードが有効に変わり、逆にインターベンション予測モードオフ閾値(以下、予測モードオフ閾値。)「Mode_off_Th」を下回る(又は同値に達する)ことで、インターベンション予測モードが無効に変わる。PIカウンタ321は、測定対象となるプロセッサユニットから特定ペア間のプロセッサユニットでインターベンション転送が行われる際にインクリメントされ、測定対象となるプロセッサユニットから異なるプロセッサユニットへインターベンション転送が行われるとデクリメントされる。例えば、PUb←PUa予測用カウンタは、プロセッサユニット1bからキャッシュミスによるリフィル要求がCMU3に届いた際にインターベンション転送元がプロセッサユニット1aであればインクリメントされ、プロセッサユニット1a以外であればデクリメントされる。ここで、予測モードオフ閾値「Mode_off_Th」は、予測モードオン閾値「Mode_on_Th」と同値又は小さい値であるならばその値は任意である。
【0032】
次に、インターバルカウンタによる解除方式について説明する。この解除方式を採用する場合には、図7に示すように、PIカウンタ321は2段階の閾値を設定可能に構成するとともに、PIU32内部にインターバルカウンタ324を設けておく。インターバルカウンタ324は、一定時間の経過とともにPIカウンタ321のカウンタ値をデクリメントする。
特定ペア間でインターベンション転送が起こり、PIカウンタ321がインクリメントされる点は上記同様であるが、時間の経過とともにPIカウンタ321のカウンタ値をインターバルカウンタ324によってデクリメントすることで、時間的局所性を鑑みる。すなわち、実行後長時間が経過したインターベンション転送に基づいた予測は精度が低い可能性があるため、インターバルカウンタ324によって時間経過とともにPIカウンタ321を無効化の方向にバイアスすることで、予測の精度を担保する。
【0033】
次に、予測失敗による解除方式について説明する。この解除方式は、インターベンション予測モードが有効になった後、一度でも予測が失敗したらインターベンション予測モードを無効にする(及びPIカウンタ321を0クリアする)コンサバティブな方式である。
インターベンション転送の予測に失敗した場合には、全キャッシュメモリのタグメモリを活性化した上で転送対象となるキャッシュラインの存在を確認し直さなければならないため、消費電力及び処理時間が増加してしまう。本解除方式では、一度でも予測が失敗したらインターベンション予測モードを無効にするため、繰り返し予測が外れることがない。これにより、消費電力及び処理時間の増加を防止できる。
【0034】
なお、上記のように、インターベンション転送の回数を複数のプロセッサペア間で個別に計測し、インターベンション予測モードのON/OFFを切り替える場合、転送元が異なる複数のプロセッサペアに関してインターベンション転送予測カウンタのカウンタ値が予測モードオン閾値を越える可能性がある。例えば、PUb←PUa予測用カウンタ及びPUb←Puc予測用カウンタの両方が予測モードオン閾値を超えた状態となる可能性がある。このような状態においてCMU3がどのプロセッサペアに関するインターベンション予測モードを採用するかの選択方式の一例について具体例を五つ挙げて説明する。ただし、下記の方式に限るものではない。
・あるプロセッサペアに関してインターベンション予測モードがオンとなった場合には、PIU32が他のプロセッサペアに関するPIカウンタ321を停止させる。
・あるプロセッサペアに関してインターベンション予測モードがオンになった場合、PIU32は、それ以降にPIカウンタ321のカウンタ値が予測モードオン閾値を超えた(又は同値に達した)プロセッサペアについては、予測モードオン閾値を超えた(同値に達した)時間が早い順に高い優先度を設定し、現在オンとなっているインターベンション予測モードが解除された時点で、最も優先度が高いプロセッサペアのインターベンション予測モードをオンにする。
・プロセッサペアの優先度を予め設定しておき、PIカウンタ321のカウンタ値が予測モードオン閾値を超えた(又は同値に達した)プロセッサペアの中で最も優先度の高いプロセッサペアのインターベンション予測モードをオンとする。(例:「PUb←PUa」>「PUb←PUc」>「PUb>PUd」)
・PIカウンタ321のカウンタ値の予測モードオン閾値に対する超過分が大きいほど高い優先度をプロセッサペアに設定し、最も優先度が高いプロセッサペアのインターベンション予測モードをオンとする。
・時間的に直近で予測が当たったプロセッサペアのインターベンション予測モードをオンとする。
【0035】
このように、本実施形態にかかるマルチプロセッサは、プロセッサ間のインターベンション転送の傾向を予測し、転送対象のキャッシュラインが存在すると予測されるキャッシュメモリに関するタグメモリのみを起動してキャッシュラインの有無を確認する。よって、特定のプロセッサ(L1キャッシュメモリ)ペア間のインターベンション転送時におけるHW駆動率を低下させ、マルチプロセッサの消費電力を低減できる。
しかも、実際にキャッシュミスが発生して、プロセッサがキャッシュラインを要求するタイミングに予測を立てるため、予測の精度が高く、予測の外れに伴う消費電力の増加や処理時間の増大を招きにくい。
【0036】
なお、上記の説明においては、PIU32がCMU3内に集約された構成を例としたが、図8に示すように、各プロセッサユニット1にDPIU(Distributed Predicting Intervention Uint)13a〜13dとしてインターベンション予測ユニットを分散配置し、各DPIU13a〜13dには、各プロセッサユニット1a〜1dに関連したカウンタ(プロセッサユニット1bなら、PU−B←PU−A、PU−B←PU−B、PU−B←PU−C、PU−B←PU−D、PU−B←L2のインターベンション転送に関連する五つ)を配備することで、上記同様の予測アルゴリズムを実現可能である。
【0037】
図8は、プロセッサユニット1bのL1キャッシュメモリ11bでキャッシュミスが発生し、DPIU13bの予測により「PUb←PUa」のカウンタが予測モードオン閾値を超えているため、プロセッサユニット1aからのインターベンション転送を予測し、プロセッサユニット1a内のL1タグキャッシュ12aを引くことによってキャッシュヒットを得て、キャッシュラインをL1キャッシュメモリ11aからL1キャッシュメモリ11bにリフィルしている。
このように、インターベンション予測ユニットを各プロセッサユニットに分散配置した場合でも、CMU3内に集約して配置した場合と同様の効果が得られる。これは、他の実施の形態に関しても同様である。
【0038】
(第2の実施の形態)
図9は、本発明の第2の実施の形態にかかるマルチプロセッサの構成を示す図である。第1の実施の形態のマルチプロセッサとほぼ同様の構成であるが、インターベンションパターン格納部325をさらに有する点で相違する。
また、PIカウンタ321内の各カウンタは、プロセッサペアではなく、インターベンション転送パターン(2回以上のインターベンション転送からなるパターン)に対応したパターンカウンタとなっている。
【0039】
インターベンションパターン格納部325には、特定のインターベンション転送パターンが格納されている。一例として、特定のプロセッサユニットを巡回するようにインターベンション転送が行われるパターンや、特定のプロセッサユニット間を往復するようにインターベンション転送が行われるパターンがある。
前者の具体例としては、
・PU−A→PU−B→PU−A
・PU−A→PU−B→PU−C→PU−A
・PU−A→PU−B→PU−D→PU−A
・PU−A→PU−B→PU−C→PU−D→PU−A
・PU−A→PU−B→PU−D→PU−C→PU−A
などが挙げられる。
一方、後者の具体例としては、
・PU−A→PU−B→PU−A
・PU−A→PU−B→PU−C→PU−B→PU−A
・PU−A→PU−B→PU−D→PU−B→PU−A
・PU−A→PU−B→PU−C→PU−D→PU−C→PU−B→PU−A
・PU−A→PU−B→PU−D→PU−C→PU−D→PU−B→PU−A
などが挙げられる。
【0040】
インターベンションパターン格納部325には、上記のようなインターベンション転送パターンが格納されており、格納されているパターンと一致するインターベンション転送が発生すると、PIカウンタ321の各エントリに対応したパターンカウンタをインクリメントする。なお、インターベンション転送パターンをパターンカウンタと一対一で対応させても良いし、複数のパターンを一つのカウンタに割り当てて(例えば、PU−A→PU−B→PU−C→PU−AとPU−A→PU−B→PU−D→PU−Aのような類似するパターンを一つのカウンタを割り当てて)カウントしても良い。
【0041】
PIU32は、PIカウンタ321のパターンカウンタが予測モードオン閾値を超える(又は同値に達する)とインターベンション予測モードをオンし、予測モードオフ閾値を下回る(又は同値に達する)とインターベンション予測モードをオフする。なお、インターベンション予測モードの解除については、上記第1の実施の形態と同様に、インターバルカウンタを用いる方式や、予測失敗による即解除方式をとることも可能である。
【0042】
インターベンション転送パターンとのマッチングを取る方式としては、アドレスを比較せずに単にインターベンション転送の順番を追ってパターンのマッチングを取る方式と、同じアドレスに対するインターベンション転送の順番を追ってパターンとのマッチングを取る方式とのいずれも適用可能である。同じアドレスに対するインターベンション転送の順番を追う場合は、同じアドレスに対してパターン順序のインターベンション転送が発生して初めてパターン発生とみなす。
【0043】
図10に、本実施の形態にかかるマルチプロセッサの動作の一例として、二つのプロセッサユニット1a、1bでプログラムを並列実行する場合の動作の流れを示す。ここで、プログラム内にオペレーション0〜3の処理が存在し、オペレーション0、2の処理はプロセッサユニット1aが、オペレーション1、3の処理はプロセッサユニット1bが担当するものとする。この場合、プロセッサユニット1a、1bは、処理対象となるデータや、処理を行うための命令コードをメインメモリ2から自己の内部に存在するL1キャッシュメモリ11a、11bに取り込むことで処理の高速化を図る。
【0044】
ここでは、プロセッサユニット1aでオペレーション0の処理を終えたデータを含むキャッシュラインが、後続のオペレーション1の処理を行うプロセッサユニット1bに転送され、オペレーション1の処理を終えたキャッシュラインが再びプロセッサユニット1aに転送されて、オペレーション2以降の処理を続ける動作を説明する。ここで、インターベンションパターン格納部325には、L1キャッシュメモリ11a→L1キャッシュメモリ11b→L1キャッシュメモリ11aのパターンが格納されているものとする。
【0045】
プロセッサユニット1aによるオペレーション0を終えたキャッシュラインを、プロセッサユニット1bが読み込もうとする際、キャッシュラインはL1キャッシュメモリ11aに存在するため、L1キャッシュメモリ11bではキャッシュミスが発生する。そこで、プロセッサユニット1bは、CMU3へリフィル要求を発行し、CMUコントローラ31は、CMU3の内部にある全てのタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)にアクセスすることで、所望のキャッシュラインがL1キャッシュメモリ11aに存在することを認識する(図3と同様)。
【0046】
その後、図11に示すように、L1キャッシュメモリ11aからキャッシュラインがL1キャッシュメモリ11bへインターベンション転送される。第1の実施の形態の場合は、L1キャッシュメモリ11aからL1キャッシュメモリ11bへのインターベンション転送が行われた段階でPIカウンタ321のPUb←PUa予測用カウンタがインクリメントされていたが、本実施の形態の場合は、この段階ではPIカウンタ321のパターンカウンタをインクリメントしない。
【0047】
その後、プロセッサユニット1b(L1キャッシュメモリ11b)でオペレーション1の処理を終えたキャッシュラインは、オペレーション2の処理を行うべくプロセッサユニット1a(L1キャッシュメモリ11a)からアクセスされる。この時点で、キャッシュラインはL1キャッシュメモリ11bに存在するため、図12に示すように、L1キャッシュメモリ11aではキャッシュミスが発生する。プロセッサユニット1aからのリフィル要求は、CMU3に達するが、この時点でPIU32の予測モードはオフ状態であるため、CMU3は全てのタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)を読み込み、要求対象のキャッシュラインが存在するL1タグキャッシュ33bにヒットを得る。その後、図13に示すように、L1キャッシュメモリ11bから要求元のL1キャッシュメモリ11aへインターベンション転送によってキャッシュラインが送られる。
【0048】
キャッシュラインがL1キャッシュメモリ11a→L1キャッシュメモリ11b→L1キャッシュメモリ11aと往来した時点で、インターベンションパターン格納部325に格納されているパターンと一致するため、PIカウンタ321の「PU−A→PU−B→PU−A」のパターンカウンタがインクリメントされる。
【0049】
図10に示したプログラム処理フローのように、プロセッサユニット1aとプロセッサユニット1bとで交互にプログラム処理を行う場合、プロセッサユニット1aとプロセッサユニット1bとの間のインターベンション転送の往来が多発するため、PIカウンタ321の「PU−A→PU−B→PU−A」のパターンカウンタのカウンタ値が予測モードオン閾値を超えることが想定される。
【0050】
図14は、過去に行われたインターベンション転送の往来によってカウンタ値が閾値を超え、PIU32がインターベンション予測モードに切り替わった後の動作(換言すると、インターベンション予測モードが有効である場合の動作)を示している。この時、PIU32はインターベンション予測モードにあり、L1キャッシュメモリ11bが要求するキャッシュラインはL1キャッシュメモリ11aにあると予測する。予測の無い状態では全てのタグキャッシュを読み出す必要があるが、PIU32の予測に従ってL1キャッシュメモリ11aに関連したL1タグキャッシュ33aのみを読み出すことで、消費電力の低減が達成されている。
【0051】
図10に示すようなプログラム処理フローにおいては、高い確率で予測が当たり、L1タグキャッシュ33aからキャッシュヒットが得られる。CMUコントローラ31によりヒットが確認できた後、L1キャッシュメモリ11aからL1キャッシュメモリ11bへとキャッシュラインのインターベンション転送が行われる。複数のパターンカウンタのカウンタ値が予測モードオン閾値を越えた場合に、どのパターンに関するインターベンション予測モードを採用するかは、第1の実施の形態と同様の動作によって選択可能である。
【0052】
なお、インターベンション転送パターンによっては、インターベンション転送の転送元の候補となるキャッシュメモリが複数存在することも考えられる。具体例を挙げると、「PU−A→PU−B→PU−D→PU−B→PU−A」という転送パターンの場合には、パターンの最初のPU−A→PU−Bというインターベンション転送と、三番目のPU−D→PU−Bというインターベンション転送とは、いずれもL1キャッシュメモリ11bを転送先とするインターベンション転送である。したがって、CMUコントローラ31は、プロセッサユニット1bからリフィル要求を受けた場合に、パターンの1番目のインターベンション転送に対応するリフィル要求であるか、3番目のインターベンション転送に対応するリフィル要求であるかを判別する必要がある。換言すると、CMUコントローラ31は、プロセッサユニット1bからリフィル要求を受けた場合、インターベンション転送の転送元を、L1キャッシュメモリ11bと予測するべきか、L1キャッシュメモリ11dと予測するべきかを判断する必要がある。
【0053】
インターベンション転送の転送元を特定する方法の一例を挙げるとCMUコントローラ31が、パターンの最初のインターベンション転送に該当するリフィル要求を受けた時点からパターン終了までの間、リフィル要求によって指定されたアドレスについて何回インターベンション転送を行ったかを記憶してもよい。具体例として挙げた転送パターンでは、パターン中の1回目のインターベンション転送であるか、3回目のインターベンション転送であるかを判別することで、転送元となるキャッシュメモリを特定できる。
【0054】
また、CMUコントローラ31が、パターンの最初のインターベンション転送に該当するリフィル要求を受けた時点からパターン終了までの間、リフィル要求によって指定されたアドレスについての各々のキャッシュメモリからのリフィル要求の数を記憶しても良い。具体例に挙げた転送パターンでは、あるアドレスに対するプロセッサユニット1bによる最初のリフィル要求であるか2回目のリフィル要求であるかを判別することで、転送元となるキャッシュメモリを特定できる。
【0055】
なお、CMUコントローラ31が転送元の候補となる複数のキャッシュメモリに対応する各タグを活性化してもよい。具体例として挙げた転送パターンでは、プロセッサユニット1bからのリフィル要求を受けた場合に、CMUコントローラ31はL1タグキャッシュ33a、33dを活性化して読み出しても良い。この場合には、CMU3がプロセッサユニット1bからリフィル要求を受けた場合に、パターンの1番目のインターベンション転送のものであるか、パターンの3番目のインターベンション転送のものであるかをCMUコントローラ31が判別する必要はなくなる。
【0056】
本実施の形態においては、特定のプロセッサペアでのインターベンション転送の回数ではなく、所定のインターベンション転送パターンとの一致回数に基づいてインターベンション予測モードのON/OFFを切り替えるため、第1の実施の形態と比較してより厳しい条件で予測を行うこととなる。したがって、インターベンション転送の予測の精度が高まるため、予測が外れることによって消費電力や処理時間が増大することを抑えることができる。
【0057】
(第3の実施の形態)
図15は、本発明の第3の実施の形態にかかるマルチプロセッサの構成を示す図である。
上記第1、第2の実施の形態においては、マルチプロセッサ内のキャッシュラインやデータの流れに基づいてインターベンション転送の予測を行っていたが、本実施形態においては、マルチプロセッサ内のハードウェア構成や消費電力を考慮してインターベンション転送を予測する。
マルチプロセッサの構成は第1の実施形態とほぼ同様であるが、予測ユニットであるPIU32が、内部にバイアスユニット323をさらに有する点で相違する。なお、PIカウンタ321については、第1の実施の形態と同様であり、プロセッサペアに対応するカウンタを備えている。
【0058】
バイアスユニット323は、PIカウンタ321の各プロセッサペアに対応するカウンタが予測モードオン閾値を超えるか否かの判定を行う論理への一定のバイアスをかける働きをする。
例を挙げると、過去にプロセッサユニット1aからプロセッサユニット1bに5回のインターベンション転送が行われており、「PUb←PUa」のカウンタ値として記憶されているとする。また一方で、過去にプロセッサユニット1cからプロセッサユニット1bに6回のインターベンション転送が行われており、「PUb←PUc」のカウンタ値として記憶されているとする。ここで、両者の予測モードオン閾値(Th)が共に8だったとする。この時のバイアスユニット323が「PUb←PUa」に「×2倍」のバイアスを、「PUb←PUc」に「×1倍」のバイアス(実質の無バイアス)をかけたとする。この場合、プロセッサユニット1aからプロセッサユニット1bへのインターベンション転送は、過去のインターベンション転送の回数はプロセッサユニット1cに比べて少ないが、PUb←PUaのカウンタのカウンタ値が予測モードオンの閾値を超えるため、(5回×2倍=10回>閾値(8回))、プロセッサユニット1bを転送先とするインターベンション転送予測としてプロセッサユニット1aが転送元として予測される。
【0059】
図15のように両者へのバイアスが無い状態では、両者とも閾値を超えていないため、プロセッサユニット1bからキャッシュミスのリフィル要求が届いた際に、CMUコントローラ31は全てのタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)を読み、L1タグキャッシュ33aとL1タグキャッシュ33cとにキャッシュヒットを得る(既に、同じキャッシュラインをL1キャッシュメモリ11aとL1キャッシュメモリ11cとでシェアしている状況)。ここで、L1キャッシュメモリ11aからインターベンション転送するか、L1キャッシュメモリ11cからインターベンション転送するかは、プロセッサユニット1の実装状態に依存する。
【0060】
L1キャッシュメモリ11aが選択されれば、図16に示すように、L1キャッシュメモリ11aからL1キャッシュメモリ11bへインターベンション転送が行われ、PIU32内のPIカウンタ321の対応するプロセッサペアのカウンタがインクリメントされる。一方、L1キャッシュメモリ11cが選択されれば、図17に示すように、L1キャッシュメモリ11cからL1キャッシュメモリ11bへインターベンション転送が行われ、PIU32内のPIカウンタの対応するプロセッサペアのカウンタがインクリメントされる。この場合、L1キャッシュメモリ11aの持つキャッシュラインとL1キャッシュメモリ11cの持つキャッシュラインとは同じであるため、L1キャッシュメモリ11bに達するキャッシュライン情報は同じであり、キャッシュのコヒーレンシは保たれる。しかし、インターベンション転送に伴う消費電力は、L1キャッシュメモリ11cからL1キャッシュメモリ11bへの転送を行った方が大きくなる(システム上におけるプロセッサ間の距離が遠く、転送時に駆動を要する不図示のハードウェア数も増加するため。)。そこで、バイアスユニット323によって、L1キャッシュメモリ11a側に一定のバイアスをかけることで、PIU32がL1キャッシュメモリ11aからのインターベンション予測モードへ切り替わることを容易にし、消費電力の少ないL1キャッシュメモリ11aからL1キャッシュメモリ11bへのインターベンション転送を促すことができる。
【0061】
図18に、バイアスユニット323によってL1キャッシュメモリ11aに関するインターベンション予測モードが有効になった状態を示す。インターベンション予測モードが有効になった状態においては、PIU32に従いL1タグキャッシュ33aのみを引くことでヒットを得て、インターベンション転送に伴う消費電力が少ないL1キャッシュメモリ11aからL1キャッシュメモリ11bへの転送を行うことができる。
【0062】
このように、より消費電力の少ないインターベンション転送の予測モードへの切り替えに対して、バイアスユニット323によって一定の優先度を与えることで、マルチプロセッサ全体としての消費電力を低減できる。また、バイアスユニット323が無い構成であっても、PIU32内のPIカウンタ321の予測モードオン閾値を、転送に伴う消費電力の少ないプロセッサユニット間では低く設定することで、消費電力の少ないインターベンション転送への切り替えの優先度を高めることができる。
【0063】
以上の説明においては、複数のプロセッサユニット1がCMU3を介して連結されたマルチプロセッサを例としたが、その接続形態は任意である。他の接続方法の一形態として、図19に、各プロセッサユニット1、CMU3、メインメモリ2をリングバスによって接続する構成を示す。また、図20、図21に、リングバス形態のマルチプロセッサにおけるインターベンション転送の様子を示す。図示するように、プロセッサユニット1aからプロセッサユニット1bへのインターベンション転送に比べ、プロセッサユニット1cからプロセッサユニット1bへのインターベンション転送は、リングバス上の距離も遠く、同時に消費電力も高いことがうかがえる。このようなリングバス形態のマルチプロセッサに対しても、上記のバイアスユニット323を設けたり、予測モードオン閾値を個別に設定するなどすることにより、消費電力が少ないインターベンション転送に対して優先度を持たせることが可能となる。
【0064】
(第4の実施の形態)
図22は、本発明の第4の実施の形態にかかるマルチプロセッサの構成を示す図である。第1〜第3の実施の形態のマルチプロセッサとの構成の相違は、PIU32がPIカウンタ321の代わりにLocked Adder記憶装置322(322a〜322d)を備える点である。Locked Adder記憶装置322a〜322dは、各プロセッサユニットからのll命令によってロックを試みたアドレスを格納する。各プロセッサユニットに対応するLocked Adder記憶装置322a〜322dが記憶するアドレスの数は任意であり、一つに限られない(実装では、ハードウェアコストとのトレードオフによって記憶数が決まる。)。
【0065】
複数のプロセッサユニットがメモリ空間を共有してプログラム処理を行う場合、ある一定の処理区間において、他のプロセッサユニットの介入を許容できない「排他的処理実行」が必要なケースが存在する。この場合、プロセッサユニットは、以下のようなシーケンスを行うことで一定のメモリ領域を扱うためのロック変数(1:ロック、0:アンロック)を獲得した後に排他制御を行い、処理後にロック変数とともにメモリ領域を解放する。
==<排他制御の実行フロー>==========
[Retry]
ld R0,RA
bnez R0 [Retry]
movi R0,1
ll R1,RA
sc R0,RA
beqz R0 [Retry]
〜〜排他処理〜〜
movi R0,0
suc R0,RA
========================
【0066】
ここで、上記フローにおける各実行命令について説明する。「ld(Load)」は、メモリ領域から値を読み込む命令であり、上記フローではロック変数を格納するメモリアドレスRAから、現状のロック変数の値をレジスタR0に読み込んでいる。「bnez(Branch Not Equal Zero)」は、レジスタの値が0と一致しない場合に、指定先のラベルに分岐する命令であり、上記フローにおいては読み出したロック変数が0(アンロック)でない場合は、[Retry]ラベルまで戻ってフローをやり直す。「movi(Move Immediately)」は、即値を指定のアドレスに格納する命令であり、上記フローではレジスタR0に値1を格納している。「ll(Load Locked)」は、指定されたメモリアドレスから値を読み込むと同時に、「自プロセッサがこの領域をロックするべくアクセス中である」というロック指示子(及びアドレス)を登録する命令であり、上記フローでは、レジスタRAで指定されたメモリアドレスからR1へ値を読み出すとともに、指示子(及びアドレス)を登録している。llに続く「sc(Store Conditional)」は、「ロック指示子を登録後に他のプロセッサが同じ領域にアクセスを行っていない」ことを条件に、指定されたメモリ領域に値を書き込む命令であり、上記フローでは、レジスタRAで指定されたメモリアドレスへR0(値は1)の格納を試み、成功(1)又は失敗(0)として結果をR0に格納している。「beqz(Branch Equal Zero)」は、レジスタの値が0と一致する場合に指定先のラベルに分岐する命令であり、上記フローではsc命令の成功・失敗の結果が0(失敗)の場合は[Retry]ラベルに戻ってフローをやり直す。
ここまでの処理を終えた時点で、上記のフローを行ったプロセッサユニットは、排他的にロック変数とそれに対応したメモリ領域とを獲得しているため、一連の排他処理を行う。排他処理を行った後は、ロック変数を解放すべく値0を「suc(Store Unconditional)」によって無条件に書き込み、ロック変数をアンロック(値0)に戻して領域を解放している。
【0067】
なお、上記のフローは、“COMPUTER ARCHITECTURE A QUANTITATIVE APPROACH 2nd Edition”、John L Hennessy & David A Patterson著に説明されているように公知のものである。
【0068】
以下、排他処理のフローにリンクしたインターベンション予測方式について説明する。排他制御を伴うプログラム実行は、さらに下記の三つに分類される。
(1)「sc」に連動したインターベンション予測方式
(2)「ll」に連動したインターベンション予測方式
(3)「ld」に連動したインターベンション予測方式
【0069】
(1)の「sc」に連動したインターベンション予測方式について説明する。
プロセッサユニット1aが上記フローによってあるメモリ領域を確保して排他処理を行い、解放したとする。その後、プロセッサユニット1bが同じメモリ領域に対して上記フローを実行し、「sc」によってメモリ領域へのロック変数を書き込む際の様子を図23に示す。
図23において、プロセッサユニット1bがsc命令を実行し、PIU32内のLocked Adder記憶装置322a〜322dを確認している。プロセッサBのロック指示子(及びアドレス)を確認し、プロセッサユニット1bがll命令を発行した以降に、他のプロセッサユニットが同じアドレスに配置されたロック変数を同時に確保していないことを確認する。また、同時に、他のプロセッサユニットによって現在確保されているロック変数又は過去に確保されたロック変数のアドレスと、現在プロセッサユニット1bが確保するロック変数のアドレスとが一致するか否かを判定する。このケースでは、プロセッサユニット1aが確保したロック変数を、プロセッサユニット1aでの使用後にプロセッサユニット1bが使用するために確保するため、図23に示したように、PU−A Locked Adder記憶装置322aに記憶されているアドレスとプロセッサユニット1bがscによって確保しようとするロック変数のアドレスとが一致(ヒット)する。
【0070】
この時点で、PIU32は、「プロセッサユニット1bは、プロセッサユニット1aが排他的に使用していたメモリ領域を継承して使用する」ことを検知できたため、以降のプロセッサユニット1b(L1キャッシュメモリ11b)からのキャッシュミスによって要求されるキャッシュラインは、同じ領域を使用していたプロセッサユニット1a内のL1キャッシュメモリ11aに存在すると予測し、インターベンション予測モードをオンにする。
【0071】
インターベンション予測モードがオンした後に、L1キャッシュメモリ11bでキャッシュミスが発生した様子を図24に示す。インターベンション予測モードがオンした状態では、PIU32は、L1キャッシュメモリ11bから要求されるキャッシュラインがL1キャッシュメモリ11aに存在すると予測し、CMU3内のL1キャッシュメモリ11aに関するL1タグキャッシュ33aにのみアクセスし、キャッシュヒットを得ている。このように、排他制御のために用いる命令とアドレスの一致とによりプロセッサ間のインターベンション転送を予測できる。
【0072】
次に、上記(2)の「ll」に連動したインターベンション予測方式について説明する。
上記(1)の「sc」に連動したインターベンション予測方式では、排他制御フローのsc命令に連動してロック変数を確保するアドレスの比較を行っていたが、本方式ではフローの前半にll命令でロック変数へのアクセスを試行した段階で、他のプロセッサユニットが確保したロック変数のアドレスとの比較を行う。これは、scによって最終的にロック変数を確保したプロセッサユニットに対してのみならず、ll命令によってロック変数の確保を試みたものの、sc命令の段階でロック変数を確保できなかったプロセッサユニットに対しても有効にインターベンション転送の予測を行う方式である。
【0073】
次に、上記(3)の「ld」に連動したインターベンション予測方式について説明する。
本方式では、フローの始めにld命令でロック変数の値を確認するためにアクセスした段階で、他のプロセッサユニットが確保したロック変数のアドレスとの比較を行う。これは、まだロック変数の確保を試みてはいないが、今後試みるであろうプロセッサユニットに対してもインターベンション転送の予測を行う方式である。また、本方式のようにld命令に限らず、単に他のプロセッサユニットが確保したロック変数のアドレスに対して、何らかのメモリアクセスを行った段階で、インターベンション予測に反映する(制限を緩める)方式も考えられる。
【0074】
排他制御フローの領域解放にリンクした解除方式について説明する。上記のように、インターベンション予測モードへの切り替えは、排他制御実行フローにおいて、排他処理に移る複数の段階で(ld、ll、scにリンクした形で)各命令にリンクさせることが可能であるが、インターベンション予測モードの解除は、「排他処理」後にロック変数を解放する「suc」命令にリンクさせる。すなわち、あるプロセッサユニットが他のプロセッサユニットが用いていたロック変数とメモリ領域とを継承して排他処理を行っている間は、インターベンション予測モードを有効に保ち、その領域を解放する手順(ここではsuc命令によるロック変数の解除)とともにインターベンション予測モードを無効化する。
【0075】
このように、本実施の形態においては、排他制御フローの命令にリンクさせてインターベンション予測モードのオン・オフを切り替え、転送対象のキャッシュラインが存在すると予測されるキャッシュメモリに関するタグメモリのみを起動してキャッシュラインの有無を確認する。よって、特定のプロセッサ(L1キャッシュメモリ)ペア間のインターベンション転送時におけるHW駆動率を低下させ、マルチプロセッサの消費電力を低減できる。
【0076】
なお、上記各実施の形態は本発明の好適な実施の一例であり、本発明はこれらに限定されることなく、様々な変形が可能である。すなわち、上記の各実施の形態は、当該分野の技術者によって、上記説明の要綱に基づき多様なマルチプロセッサに対して修正可能であり、上記の説明は当該分野に対する開示内容として広く理解されるべきであり、本発明を限定するものではない。
【符号の説明】
【0077】
1 プロセッサユニット、2 メインメモリ、3 CMU、11 L1キャッシュメモリ、32 PIU、33 L1タグキャッシュ、34 L2キャッシュメモリ、35 L2タグキャッシュ、321 PIカウンタ、323 バイアスユニット、324 インターバルカウンタ、325 インターベンションパターン格納部。
【技術分野】
【0001】
本発明は、キャッシュメモリを備えたプロセッサを複数備え、各プロセッサのキャッシュメモリ間でキャッシュコヒーレンシを保つマルチプロセッサに関する。
【背景技術】
【0002】
従来、キャッシュメモリを備えたプロセッサを複数有するマルチプロセッサにおいて、任意のプロセッサでキャッシュミスが発生した場合、マルチプロセッサ内でキャッシュコヒーレンシを管理するコヒーレンシ管理ユニットは、各プロセッサのキャッシュメモリに対応して設けられた全てのタグメモリを活性化し、リフィル対象となるキャッシュラインの有無を確認していた。
【0003】
また、リフィル対象となるキャッシュラインの有無を確認した結果、リフィル対象となるキャッシュラインが複数のキャッシュメモリ内に存在した場合、コヒーレンシ管理ユニットは、キャッシュミスしたキャッシュメモリへキャッシュラインを転送する際にマルチプロセッサ内(キャッシュメモリ、共有バス、調停回路等)で消費される消費電力を考慮に入れずにキャッシュラインの転送を行っていた。
【0004】
しかしながら、従来技術では、リフィル対象となるキャッシュラインの有無の確認や、キャッシュラインの転送は、消費電力の観点からは非効率的であるという問題があった。
【0005】
共有メモリマルチプロセッサにおいて、コヒーレンシを維持するデータブロックに対してライト動作を行う際に、データを共有化していたため無効化されるプロセッサをシフトレジスタに格納し、ライト結果を予測先のプロセッサに転送して性能の向上を図る技術が特許文献1に開示されているが、あるデータブロックにライトが発生したタイミングで投機的に予測を行い、実際に必要とされる前に転送するため、予測の精度が低く、必ずしも性能向上に繋がらないという問題があった。
【先行技術文献】
【特許文献】
【0006】
【特許文献1】特開2002−49600号公報
【発明の概要】
【発明が解決しようとする課題】
【0007】
本発明は、キャッシュメモリ間でのキャッシュラインの転送時の消費電力を低減したマルチプロセッサを提供することを目的とする。
【課題を解決するための手段】
【0008】
本願発明の一態様によれば、主記憶装置と、主記憶装置の記憶データを一時記憶するキャッシュメモリを夫々備え、主記憶装置を共有する複数のプロセッサと、複数のプロセッサのキャッシュメモリのコヒーレンシを管理するコヒーレンシ管理ユニットと、を備え、コヒーレンシ管理ユニットは、キャッシュメモリの各々に対応して設けられ、対応するキャッシュメモリにキャッシュされたキャッシュデータのタグを格納する複数のタグキャッシュと、プロセッサからのリフィル要求に応じて、複数のタグキャッシュを参照してリフィル要求に対応するキャッシュデータがキャッシュされたキャッシュメモリを判別し、判別したキャッシュメモリを転送元としリフィル要求元のキャッシュメモリを転送先としてリフィル要求に対応するキャッシュデータの転送を行うデータ転送手段と、キャッシュメモリ間のキャッシュデータの転送の監視に基づく所定の予測処理を行うことで、転送先別に一つの転送元を仮決定する仮決定手段とを有し、データ転送手段は、仮決定手段の仮決定結果が得られた後は、キャッシュデータの転送を行う際、仮決定した一つの転送元に対応するタグキャッシュのみを活性化し、活性化されたタグキャッシュのみを参照してリフィル要求に対応するキャッシュデータがキャッシュされているか否かを判別することを特徴とするマルチプロセッサが提供される。
【発明の効果】
【0009】
本発明によれば、キャッシュメモリ間でのキャッシュラインの転送時の消費電力を低減したマルチプロセッサを提供できるという効果を奏する。
【図面の簡単な説明】
【0010】
【図1】図1は、本発明の第1の実施の形態にかかるマルチプロセッサの構成を示す図。
【図2】図2は、第1の実施の形態にかかるマルチプロセッサが四つのプロセッサユニットでプログラムを並列実行する場合の動作の流れを示す図。
【図3】図3は、プロセッサユニットが、処理対象となるデータへアクセスし、キャッシュミスを起こした状態を示す図。
【図4】図4は、キャッシュメモリラインをリフィル要求元であるプロセッサユニットへとインターベンション転送する状態を示す図。
【図5】図5は、PIUがインターベンション予測モードへ切り替わった後でのインターベンション転送時の動作を示す図。
【図6】図6は、2段階閾値方式によるインターベンション予測モードの解除方式を示す図。
【図7】図7は、インターバルカウンタを用いたインターベンション予測モードの解除方式を示す図。
【図8】図8は、各プロセッサユニットにインターベンション予測ユニットを分散配置したマルチプロセッサの構成の一例を示す図。
【図9】図9は、本発明の第2の実施の形態にかかるマルチプロセッサの構成を示す図。
【図10】図10は、第2の実施の形態にかかるマルチプロセッサが二つのプロセッサユニットでプログラムを並列実行する場合の動作の流れを示す図。
【図11】図11は、キャッシュメモリラインをリフィル要求元であるプロセッサユニットへとインターベンション転送する状態を示す図。
【図12】図12は、プロセッサユニットが、処理対象となるデータへアクセスし、キャッシュミスを起こした状態を示す図。
【図13】図13は、キャッシュメモリラインをリフィル要求元であるプロセッサユニットへとインターベンション転送する状態を示す図。
【図14】図14は、PIUがインターベンション予測モードへ切り替わった後でのインターベンション転送時の動作を示す図。
【図15】図15は、本発明の第3の実施の形態にかかるマルチプロセッサの構成を示す図。
【図16】図16は、インターベンション転送が行われ、PIカウンタの対応するプロセッサペアのカウンタがインクリメントされる状態を示す図。
【図17】図17は、インターベンション転送が行われ、PIカウンタの対応するプロセッサペアのカウンタがインクリメントされる状態を示す図。
【図18】図18は、インターベンション予測モードが有効になった状態においては、一つのL1タグキャッシュのみを引くことでヒットを得た状態を示す図。
【図19】図19は、各プロセッサユニット、CMU、メインメモリをリングバスによって接続したマルチプロセッサの構成の一例を示す図。
【図20】図20は、リングバス形態のマルチプロセッサにおけるインターベンション転送の様子を示す図。
【図21】図21は、リングバス形態のマルチプロセッサにおけるインターベンション転送の様子を示す図。
【図22】図22は、本発明の第4の実施の形態にかかるマルチプロセッサの構成を示す図。
【図23】図23は、プロセッサユニットが同じメモリ領域に対して、「sc」によってメモリ領域へのロック変数を書き込む際の様子を示す図。
【図24】図24は、インターベンション予測モードがオンした後に、L1キャッシュメモリでキャッシュミスが発生した様子を示す図。
【発明を実施するための形態】
【0011】
以下に添付図面を参照して、本発明の実施の形態にかかるマルチプロセッサを詳細に説明する。なお、これらの実施の形態により本発明が限定されるものではない。
【0012】
(第1の実施の形態)
図1は、本発明の第1の実施の形態にかかるマルチプロセッサの構成を示す図である。
マルチプロセッサは、プロセッサユニット1(1a〜1d)、メインメモリ2、及びコヒーレンシマネージメントユニット3(CMU:Coherency Management Unit)を有する。なお、以下の説明においては、必要に応じてプロセッサユニット1a、1b、1c、1dをそれぞれPU−A、PU−B、PU−C、PU−Dと省略して表記する。
【0013】
プロセッサユニット1a〜1dは、演算処理及び命令実行を司っており、内部にはL1キャッシュメモリ(1次キャッシュメモリ)11a〜11dを備えている。L1キャッシュメモリ11a〜11dは、データフィールド及びタグフィールドを含んだキャッシュラインを格納している。プロセッサユニット1a〜1dは、自身が内包するL1キャッシュメモリ11a〜11dに対するアクセス時には、キャッシュライン中に含まれるタグに基づいてキャッシュヒット/キャッシュミスを判断し、キャッシュヒットの場合にはヒットしたキャッシュライン中のデータに対してアクセスし、キャッシュミスの場合にはリフィル要求をCMU3へ出力する。なお、プロセッサユニット1a〜1dが仮想アドレスを使用する場合、L1キャッシュメモリ11a〜11d内のタグは仮想アドレスで表されることとなる。
【0014】
CMU3は、マルチプロセッサ内部のキャッシュコヒーレンシを管理する。CMU3は、CMUコントローラ31、インターベンション予測ユニット(PIU:Predicting Intervention Unit )32、L1タグキャッシュ33(33a〜33d)、L2キャッシュメモリ(2次キャッシュメモリ)34、L2タグキャッシュ35を有する。
【0015】
L1タグキャッシュ33a〜33dは、L1キャッシュメモリ11a〜11dのそれぞれに対応して設けられており、L1キャッシュメモリ11a〜11dにおけるタグ(アドレス)を記憶する。また、L2キャッシュメモリ34は、データを記憶し、L2タグキャッシュ35は、そのタグ(L2キャッシュメモリ34におけるアドレス)を記憶する。なお、プロセッサユニット1a〜1dが仮想アドレスを使用する場合でも、L1タグキャッシュ33a〜33d内のタグは実アドレスで表されるため、CMU3はメモリ管理ユニット(MMU:Memory Management Unit)を備えた構成となり、MMUにおいて仮想アドレスと実アドレスとの変換を行うこととなる。
CMUコントローラ31は、CMU3の制御系統を担う。具体的には、プロセッサユニット1a〜1dからのリフィル要求に応じてタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)を参照して、キャッシュヒット/キャッシュミスを得る。そして、キャッシュヒット時には、ヒットしたキャッシュメモリを転送元として、リフィル要求元のプロセッサユニットへのキャッシュラインの転送を行う。一方、キャッシュミス発生時にはメインメモリ2を転送元として、リフィル要求元のプロセッサユニットへのキャッシュラインの転送を行う。また、CMUコントローラ31は、プロセッサユニット1a〜1dによるライト動作が行われた場合やキャッシュライン転送を行った場合にL1タグキャッシュ33a〜33dを最新のタグ情報に更新する処理や、スヌープ制御(複数のキャッシュメモリによって共有されているアドレスに対して任意のキャッシュメモリが更新を行う場合、そのアドレスはダーティであるとして共有している他のキャッシュメモリの該当ラインを無効化する処理等)なども行う。PIU32は、スヌープ制御に伴うL1キャッシュメモリ11a〜11d間でのキャッシュラインの転送(以下、インターベンション転送という。)の傾向を予測する。
【0016】
なお、L1キャッシュメモリ11a〜11dについても、L2キャッシュメモリ34と同様に、データだけ記憶する構成とすることも可能である。ただし、この場合には、プロセッサユニット1a〜1dが内包するL1キャッシュメモリ11a〜11dに対してアクセスする場合にも、CMUコントローラ31においてキャッシュヒット/キャッシュミスを判断する必要があるため、CMU3の負荷が増大してしまう。このため、L1キャッシュメモリ11a〜11dには、データとともにタグを記憶させておき、プロセッサユニット1a〜1dでキャッシュミスが発生した場合にのみCMU3へリフィル要求を出力することが好ましい。
【0017】
PIU32は、内部にインターベンション予測用カウンタ(PIカウンタ)321を有する。PIカウンタ321の内部には、各プロセッサユニット間のインターベンション転送に対応したカウンタや、予測モードオンに切り替わる閾値を記憶する記憶装置が存在しており、プロセッサ間転送の組ごとにカウントが可能である。四つのプロセッサユニット1a〜1dを備えたシステムにおいては、プロセッサユニット1a〜1dのいずれに関してもインターベンション転送元となりうるのは、L1キャッシュメモリ11a〜11d及びL2キャッシュメモリ34の五つであるから、PIカウンタ321は、5×4=20通りの転送を個別にカウントする。すなわち、PIカウンタ321は、PU−A←PU−A、PU−A←PU−B、PU−A←PU−C、PU−A←PU−D、PU−A←L2、PU−B←PU−A、PU−B←PU−B、PU−B←PU−C、PU−B←PU−D、PU−B←L2、PU−C←PU−A、PU−C←PU−B、PU−C←PU−C、PU−C←PU−D、PU−C←L2、PU−D←PU−A、PU−D←PU−B、PU−D←PU−C、PU−D←PU−D、PU−D←L2の20通りのインターベンション転送を個別にカウントする。
【0018】
なお、マルチプロセッサの構成の一般性を鑑み、CMU3内部にL2キャッシュメモリ34及びL2タグキャッシュ35を配置したが、これらが存在していなくても良く、必要に応じて省略することも可能である。
【0019】
さらに、CMU3と各プロセッサ1やメインメモリ2との接続方法は、図1とは異なる方式、例えばバス接続であっても良い。
【0020】
また、図1においては、マルチプロセッサ内にプロセッサが四つ(1a〜1d)配置された構成を示したが、プロセッサの数は2以上であれば任意である。これは、キャッシュラインの転送は、異なるL1キャッシュメモリ間での転送に限定される訳ではなく、同一のL1キャッシュメモリ内で行われる可能性があるためである。すなわち、プロセッサ数が2のマルチプロセッサであっても、リフィル対象となるキャッシュラインの有無を確認するためには、マルチプロセッサ内の複数のキャッシュメモリのタグメモリを活性化する必要があるためである。
具体例を挙げてより詳しく説明すると、プロセッサが仮想アドレスを使用する場合、L1キャッシュメモリでキャッシュミスが発生した際にプロセッサユニットから送出されるリフィル要求は、キャッシュラインが仮想アドレスで指定されることとなる。そして、MMUにおいて仮想アドレスを実アドレスに変換した結果、所望のメモリラインがリフィル要求の送出元のプロセッサのL1キャッシュメモリに存在することが判明する場合もある。この場合には、同一のプロセッサユニットのL1キャッシュメモリ内でキャッシュラインの転送が行われる。
従って、プロセッサ数が2、且つ二次キャッシュを省略した構成であっても、インターベンション転送の転送元は一義に定まらず、リフィル対象となるキャッシュラインの有無を確認するためには、マルチプロセッサ内の全キャッシュメモリのタグメモリを活性化する必要がある。
【0021】
続いて、PIU32の予測方式について、説明する。
図2に、本実施形態にかかるマルチプロセッサが四つのプロセッサユニット1a〜1dでプログラムを並列実行する場合の動作の流れを示す。ここで、プログラム内にオペレーション0〜3の処理が存在し、それぞれをプロセッサユニット1a〜1dが処理を担当するものとする。この場合、各プロセッサユニット1は、処理対象となるデータや、処理を行うための命令コードをメインメモリ2から自己の内部に存在するL1キャッシュメモリ11a〜11dに取り込むことで処理の高速化を図る。
【0022】
図2の処理フローからも明らかなように、プロセッサユニット1a〜1cで処理を終えたキャッシュデータは、次の処理を行うプロセッサユニット1b〜1dに転送され、次のプロセッサユニット1b〜1dで後続の処理を行う。なお、実際には、キャッシュデータは、次のプロセッサユニット1b〜1dにおけるキャッシュミスとインターベンション転送を伴うリフィル動作とによって転送される。
【0023】
ここでは、プロセッサユニット1aでオペレーション0の処理を終えたデータを含むキャッシュラインが、後続のオペレーション1の処理を行うプロセッサユニット1bに転送され、処理を続けるという動作を説明する。
【0024】
図3は、プロセッサユニット1bが、処理対象となるデータへアクセスし(実際には、プロセッサユニット1b内のL1キャッシュメモリ11bへアクセスし)、キャッシュミスを起こした状態を示している。ここで、L1キャッシュメモリ11bのリフィルを行うため、プロセッサユニット1bからのリフィル要求がCMU3に通達される。CMUコントローラ31は、CMU3内部に存在するタグキャッシュメモリへアクセスし、要求されたキャッシュラインがマルチプロセッサ内に存在するか否かを判断する。この時点では、PIU32による転送の予測はされていないため、CMUコントローラ31は全てのタグキャッシュメモリ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)にアクセスする必要がある。図中に網掛けで示す部分が、ハードウェア(ロジック・メモリなど、以下、HW(HardWare)と略記する。)が駆動されて電力を消費している部分である。全タグキャッシュへのアクセスとアドレス比較との結果、要求されたキャッシュラインがプロセッサユニット1a内のL1キャッシュメモリ11aに存在することが判明する。プロセッサユニット1bの前段の処理を行うプロセッサユニット1a内のL1キャッシュ11aに存在する可能性が高いことは、プログラム実行フローからも明らかである。
【0025】
続いて、CMUコントローラ31は、図4に示すように、L1キャッシュメモリ11a内のキャッシュメモリラインをリフィル要求元であるプロセッサユニット1bへとインターベンション転送する。この際に、PIカウンタ321の値をインクリメントする。図4においては、プロセッサユニット1aからプロセッサユニット1bへとキャッシュラインのインターベンション転送が発生したため、20個のカウンタのうちのPU−AからPU−Bへのインターベンション転送に対応する「PUb←PUa予測用カウンタ」がインクリメントされる。
【0026】
PIU32は、PIカウンタ321の値に基づいて、アクセス先となるキャッシュメモリを限定する「インターベンション予測モード」へ切り替わることで、特定プロセッサ(L1キャッシュメモリ)ペア間のインターベンション転送時におけるHW駆動率を低下させ、マルチプロセッサの消費電力を低減させる。なお、以下の説明では、「インターベンション予測モード」へ切り替わった後の状態のことを、「インターベンション予測モードが有効である。」という。
【0027】
ここで、PIU32がインターベンション予測モードへ切り替わるためには、PIカウンタ321のカウンタ値が「インターベンション予測モードオン閾値(以下、予測モードオン閾値)」を超える必要がある。図2に示す処理フローのように、プロセッサユニット1aからプロセッサユニット1bへ処理とともにキャッシュデータが受け継がれて処理が行われる場合、プロセッサユニット1aからプロセッサユニット1bへのインターベンション転送が多発するため、カウンタ値が予測モードオン閾値を超えることが想定される。
【0028】
図5は、過去に行われたインターベンション転送によってPIカウンタ321のPUb←PUa予測用カウンタ値が予測モードオン閾値を超え、PIU32がインターベンション予測モードへ切り替わった後の動作(換言すると、インターベンション予測モードが有効である場合の動作)を示している。図5において、プロセッサユニット1bのL1キャッシュメモリ11bでキャッシュミスが発生し、CMU3にリフィル要求が届いている。この時、PIU32はインターベンション予測モードにあり、L1キャッシュメモリ11bが要求するキャッシュラインは、L1キャッシュメモリ11aに存在すると予測する。予測の無い状態では全てのタグキャッシュを読み出す必要があるが、PIU32の予測に従ってL1キャッシュメモリ11aに関連したL1タグキャッシュ33aのみを読み出すことで、消費電力の低減が達成されている。
【0029】
図2に示すような処理フローにおいては、高い確率で予測が当たり、L1タグキャッシュ33aからヒットが得られる。CMUコントローラ31によってヒットが確認できた後、L1キャッシュメモリ11aからL1キャッシュメモリ11bへとキャッシュラインのインターベンション転送が行われる。
【0030】
次に、有効になったインターベンション予測モードを解除する方式について説明する。
インターベンション予測モードの解除方式の例としては、
・2段階閾値による解除方式。
・インターバルカウンタによる解除方式。
・予測失敗による解除方式。
が挙げられる。
【0031】
まず、2段階閾値による解除方式について説明する。この場合には、図6に示すように、PIカウンタ321は、2段階の閾値を設定可能に構成する。PIU32内のPIカウンタ321が予測モードオン閾値「Mode_on_Th」を超える(又は同値に達する)ことでPIU32のインターベンション予測モードが有効に変わり、逆にインターベンション予測モードオフ閾値(以下、予測モードオフ閾値。)「Mode_off_Th」を下回る(又は同値に達する)ことで、インターベンション予測モードが無効に変わる。PIカウンタ321は、測定対象となるプロセッサユニットから特定ペア間のプロセッサユニットでインターベンション転送が行われる際にインクリメントされ、測定対象となるプロセッサユニットから異なるプロセッサユニットへインターベンション転送が行われるとデクリメントされる。例えば、PUb←PUa予測用カウンタは、プロセッサユニット1bからキャッシュミスによるリフィル要求がCMU3に届いた際にインターベンション転送元がプロセッサユニット1aであればインクリメントされ、プロセッサユニット1a以外であればデクリメントされる。ここで、予測モードオフ閾値「Mode_off_Th」は、予測モードオン閾値「Mode_on_Th」と同値又は小さい値であるならばその値は任意である。
【0032】
次に、インターバルカウンタによる解除方式について説明する。この解除方式を採用する場合には、図7に示すように、PIカウンタ321は2段階の閾値を設定可能に構成するとともに、PIU32内部にインターバルカウンタ324を設けておく。インターバルカウンタ324は、一定時間の経過とともにPIカウンタ321のカウンタ値をデクリメントする。
特定ペア間でインターベンション転送が起こり、PIカウンタ321がインクリメントされる点は上記同様であるが、時間の経過とともにPIカウンタ321のカウンタ値をインターバルカウンタ324によってデクリメントすることで、時間的局所性を鑑みる。すなわち、実行後長時間が経過したインターベンション転送に基づいた予測は精度が低い可能性があるため、インターバルカウンタ324によって時間経過とともにPIカウンタ321を無効化の方向にバイアスすることで、予測の精度を担保する。
【0033】
次に、予測失敗による解除方式について説明する。この解除方式は、インターベンション予測モードが有効になった後、一度でも予測が失敗したらインターベンション予測モードを無効にする(及びPIカウンタ321を0クリアする)コンサバティブな方式である。
インターベンション転送の予測に失敗した場合には、全キャッシュメモリのタグメモリを活性化した上で転送対象となるキャッシュラインの存在を確認し直さなければならないため、消費電力及び処理時間が増加してしまう。本解除方式では、一度でも予測が失敗したらインターベンション予測モードを無効にするため、繰り返し予測が外れることがない。これにより、消費電力及び処理時間の増加を防止できる。
【0034】
なお、上記のように、インターベンション転送の回数を複数のプロセッサペア間で個別に計測し、インターベンション予測モードのON/OFFを切り替える場合、転送元が異なる複数のプロセッサペアに関してインターベンション転送予測カウンタのカウンタ値が予測モードオン閾値を越える可能性がある。例えば、PUb←PUa予測用カウンタ及びPUb←Puc予測用カウンタの両方が予測モードオン閾値を超えた状態となる可能性がある。このような状態においてCMU3がどのプロセッサペアに関するインターベンション予測モードを採用するかの選択方式の一例について具体例を五つ挙げて説明する。ただし、下記の方式に限るものではない。
・あるプロセッサペアに関してインターベンション予測モードがオンとなった場合には、PIU32が他のプロセッサペアに関するPIカウンタ321を停止させる。
・あるプロセッサペアに関してインターベンション予測モードがオンになった場合、PIU32は、それ以降にPIカウンタ321のカウンタ値が予測モードオン閾値を超えた(又は同値に達した)プロセッサペアについては、予測モードオン閾値を超えた(同値に達した)時間が早い順に高い優先度を設定し、現在オンとなっているインターベンション予測モードが解除された時点で、最も優先度が高いプロセッサペアのインターベンション予測モードをオンにする。
・プロセッサペアの優先度を予め設定しておき、PIカウンタ321のカウンタ値が予測モードオン閾値を超えた(又は同値に達した)プロセッサペアの中で最も優先度の高いプロセッサペアのインターベンション予測モードをオンとする。(例:「PUb←PUa」>「PUb←PUc」>「PUb>PUd」)
・PIカウンタ321のカウンタ値の予測モードオン閾値に対する超過分が大きいほど高い優先度をプロセッサペアに設定し、最も優先度が高いプロセッサペアのインターベンション予測モードをオンとする。
・時間的に直近で予測が当たったプロセッサペアのインターベンション予測モードをオンとする。
【0035】
このように、本実施形態にかかるマルチプロセッサは、プロセッサ間のインターベンション転送の傾向を予測し、転送対象のキャッシュラインが存在すると予測されるキャッシュメモリに関するタグメモリのみを起動してキャッシュラインの有無を確認する。よって、特定のプロセッサ(L1キャッシュメモリ)ペア間のインターベンション転送時におけるHW駆動率を低下させ、マルチプロセッサの消費電力を低減できる。
しかも、実際にキャッシュミスが発生して、プロセッサがキャッシュラインを要求するタイミングに予測を立てるため、予測の精度が高く、予測の外れに伴う消費電力の増加や処理時間の増大を招きにくい。
【0036】
なお、上記の説明においては、PIU32がCMU3内に集約された構成を例としたが、図8に示すように、各プロセッサユニット1にDPIU(Distributed Predicting Intervention Uint)13a〜13dとしてインターベンション予測ユニットを分散配置し、各DPIU13a〜13dには、各プロセッサユニット1a〜1dに関連したカウンタ(プロセッサユニット1bなら、PU−B←PU−A、PU−B←PU−B、PU−B←PU−C、PU−B←PU−D、PU−B←L2のインターベンション転送に関連する五つ)を配備することで、上記同様の予測アルゴリズムを実現可能である。
【0037】
図8は、プロセッサユニット1bのL1キャッシュメモリ11bでキャッシュミスが発生し、DPIU13bの予測により「PUb←PUa」のカウンタが予測モードオン閾値を超えているため、プロセッサユニット1aからのインターベンション転送を予測し、プロセッサユニット1a内のL1タグキャッシュ12aを引くことによってキャッシュヒットを得て、キャッシュラインをL1キャッシュメモリ11aからL1キャッシュメモリ11bにリフィルしている。
このように、インターベンション予測ユニットを各プロセッサユニットに分散配置した場合でも、CMU3内に集約して配置した場合と同様の効果が得られる。これは、他の実施の形態に関しても同様である。
【0038】
(第2の実施の形態)
図9は、本発明の第2の実施の形態にかかるマルチプロセッサの構成を示す図である。第1の実施の形態のマルチプロセッサとほぼ同様の構成であるが、インターベンションパターン格納部325をさらに有する点で相違する。
また、PIカウンタ321内の各カウンタは、プロセッサペアではなく、インターベンション転送パターン(2回以上のインターベンション転送からなるパターン)に対応したパターンカウンタとなっている。
【0039】
インターベンションパターン格納部325には、特定のインターベンション転送パターンが格納されている。一例として、特定のプロセッサユニットを巡回するようにインターベンション転送が行われるパターンや、特定のプロセッサユニット間を往復するようにインターベンション転送が行われるパターンがある。
前者の具体例としては、
・PU−A→PU−B→PU−A
・PU−A→PU−B→PU−C→PU−A
・PU−A→PU−B→PU−D→PU−A
・PU−A→PU−B→PU−C→PU−D→PU−A
・PU−A→PU−B→PU−D→PU−C→PU−A
などが挙げられる。
一方、後者の具体例としては、
・PU−A→PU−B→PU−A
・PU−A→PU−B→PU−C→PU−B→PU−A
・PU−A→PU−B→PU−D→PU−B→PU−A
・PU−A→PU−B→PU−C→PU−D→PU−C→PU−B→PU−A
・PU−A→PU−B→PU−D→PU−C→PU−D→PU−B→PU−A
などが挙げられる。
【0040】
インターベンションパターン格納部325には、上記のようなインターベンション転送パターンが格納されており、格納されているパターンと一致するインターベンション転送が発生すると、PIカウンタ321の各エントリに対応したパターンカウンタをインクリメントする。なお、インターベンション転送パターンをパターンカウンタと一対一で対応させても良いし、複数のパターンを一つのカウンタに割り当てて(例えば、PU−A→PU−B→PU−C→PU−AとPU−A→PU−B→PU−D→PU−Aのような類似するパターンを一つのカウンタを割り当てて)カウントしても良い。
【0041】
PIU32は、PIカウンタ321のパターンカウンタが予測モードオン閾値を超える(又は同値に達する)とインターベンション予測モードをオンし、予測モードオフ閾値を下回る(又は同値に達する)とインターベンション予測モードをオフする。なお、インターベンション予測モードの解除については、上記第1の実施の形態と同様に、インターバルカウンタを用いる方式や、予測失敗による即解除方式をとることも可能である。
【0042】
インターベンション転送パターンとのマッチングを取る方式としては、アドレスを比較せずに単にインターベンション転送の順番を追ってパターンのマッチングを取る方式と、同じアドレスに対するインターベンション転送の順番を追ってパターンとのマッチングを取る方式とのいずれも適用可能である。同じアドレスに対するインターベンション転送の順番を追う場合は、同じアドレスに対してパターン順序のインターベンション転送が発生して初めてパターン発生とみなす。
【0043】
図10に、本実施の形態にかかるマルチプロセッサの動作の一例として、二つのプロセッサユニット1a、1bでプログラムを並列実行する場合の動作の流れを示す。ここで、プログラム内にオペレーション0〜3の処理が存在し、オペレーション0、2の処理はプロセッサユニット1aが、オペレーション1、3の処理はプロセッサユニット1bが担当するものとする。この場合、プロセッサユニット1a、1bは、処理対象となるデータや、処理を行うための命令コードをメインメモリ2から自己の内部に存在するL1キャッシュメモリ11a、11bに取り込むことで処理の高速化を図る。
【0044】
ここでは、プロセッサユニット1aでオペレーション0の処理を終えたデータを含むキャッシュラインが、後続のオペレーション1の処理を行うプロセッサユニット1bに転送され、オペレーション1の処理を終えたキャッシュラインが再びプロセッサユニット1aに転送されて、オペレーション2以降の処理を続ける動作を説明する。ここで、インターベンションパターン格納部325には、L1キャッシュメモリ11a→L1キャッシュメモリ11b→L1キャッシュメモリ11aのパターンが格納されているものとする。
【0045】
プロセッサユニット1aによるオペレーション0を終えたキャッシュラインを、プロセッサユニット1bが読み込もうとする際、キャッシュラインはL1キャッシュメモリ11aに存在するため、L1キャッシュメモリ11bではキャッシュミスが発生する。そこで、プロセッサユニット1bは、CMU3へリフィル要求を発行し、CMUコントローラ31は、CMU3の内部にある全てのタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)にアクセスすることで、所望のキャッシュラインがL1キャッシュメモリ11aに存在することを認識する(図3と同様)。
【0046】
その後、図11に示すように、L1キャッシュメモリ11aからキャッシュラインがL1キャッシュメモリ11bへインターベンション転送される。第1の実施の形態の場合は、L1キャッシュメモリ11aからL1キャッシュメモリ11bへのインターベンション転送が行われた段階でPIカウンタ321のPUb←PUa予測用カウンタがインクリメントされていたが、本実施の形態の場合は、この段階ではPIカウンタ321のパターンカウンタをインクリメントしない。
【0047】
その後、プロセッサユニット1b(L1キャッシュメモリ11b)でオペレーション1の処理を終えたキャッシュラインは、オペレーション2の処理を行うべくプロセッサユニット1a(L1キャッシュメモリ11a)からアクセスされる。この時点で、キャッシュラインはL1キャッシュメモリ11bに存在するため、図12に示すように、L1キャッシュメモリ11aではキャッシュミスが発生する。プロセッサユニット1aからのリフィル要求は、CMU3に達するが、この時点でPIU32の予測モードはオフ状態であるため、CMU3は全てのタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)を読み込み、要求対象のキャッシュラインが存在するL1タグキャッシュ33bにヒットを得る。その後、図13に示すように、L1キャッシュメモリ11bから要求元のL1キャッシュメモリ11aへインターベンション転送によってキャッシュラインが送られる。
【0048】
キャッシュラインがL1キャッシュメモリ11a→L1キャッシュメモリ11b→L1キャッシュメモリ11aと往来した時点で、インターベンションパターン格納部325に格納されているパターンと一致するため、PIカウンタ321の「PU−A→PU−B→PU−A」のパターンカウンタがインクリメントされる。
【0049】
図10に示したプログラム処理フローのように、プロセッサユニット1aとプロセッサユニット1bとで交互にプログラム処理を行う場合、プロセッサユニット1aとプロセッサユニット1bとの間のインターベンション転送の往来が多発するため、PIカウンタ321の「PU−A→PU−B→PU−A」のパターンカウンタのカウンタ値が予測モードオン閾値を超えることが想定される。
【0050】
図14は、過去に行われたインターベンション転送の往来によってカウンタ値が閾値を超え、PIU32がインターベンション予測モードに切り替わった後の動作(換言すると、インターベンション予測モードが有効である場合の動作)を示している。この時、PIU32はインターベンション予測モードにあり、L1キャッシュメモリ11bが要求するキャッシュラインはL1キャッシュメモリ11aにあると予測する。予測の無い状態では全てのタグキャッシュを読み出す必要があるが、PIU32の予測に従ってL1キャッシュメモリ11aに関連したL1タグキャッシュ33aのみを読み出すことで、消費電力の低減が達成されている。
【0051】
図10に示すようなプログラム処理フローにおいては、高い確率で予測が当たり、L1タグキャッシュ33aからキャッシュヒットが得られる。CMUコントローラ31によりヒットが確認できた後、L1キャッシュメモリ11aからL1キャッシュメモリ11bへとキャッシュラインのインターベンション転送が行われる。複数のパターンカウンタのカウンタ値が予測モードオン閾値を越えた場合に、どのパターンに関するインターベンション予測モードを採用するかは、第1の実施の形態と同様の動作によって選択可能である。
【0052】
なお、インターベンション転送パターンによっては、インターベンション転送の転送元の候補となるキャッシュメモリが複数存在することも考えられる。具体例を挙げると、「PU−A→PU−B→PU−D→PU−B→PU−A」という転送パターンの場合には、パターンの最初のPU−A→PU−Bというインターベンション転送と、三番目のPU−D→PU−Bというインターベンション転送とは、いずれもL1キャッシュメモリ11bを転送先とするインターベンション転送である。したがって、CMUコントローラ31は、プロセッサユニット1bからリフィル要求を受けた場合に、パターンの1番目のインターベンション転送に対応するリフィル要求であるか、3番目のインターベンション転送に対応するリフィル要求であるかを判別する必要がある。換言すると、CMUコントローラ31は、プロセッサユニット1bからリフィル要求を受けた場合、インターベンション転送の転送元を、L1キャッシュメモリ11bと予測するべきか、L1キャッシュメモリ11dと予測するべきかを判断する必要がある。
【0053】
インターベンション転送の転送元を特定する方法の一例を挙げるとCMUコントローラ31が、パターンの最初のインターベンション転送に該当するリフィル要求を受けた時点からパターン終了までの間、リフィル要求によって指定されたアドレスについて何回インターベンション転送を行ったかを記憶してもよい。具体例として挙げた転送パターンでは、パターン中の1回目のインターベンション転送であるか、3回目のインターベンション転送であるかを判別することで、転送元となるキャッシュメモリを特定できる。
【0054】
また、CMUコントローラ31が、パターンの最初のインターベンション転送に該当するリフィル要求を受けた時点からパターン終了までの間、リフィル要求によって指定されたアドレスについての各々のキャッシュメモリからのリフィル要求の数を記憶しても良い。具体例に挙げた転送パターンでは、あるアドレスに対するプロセッサユニット1bによる最初のリフィル要求であるか2回目のリフィル要求であるかを判別することで、転送元となるキャッシュメモリを特定できる。
【0055】
なお、CMUコントローラ31が転送元の候補となる複数のキャッシュメモリに対応する各タグを活性化してもよい。具体例として挙げた転送パターンでは、プロセッサユニット1bからのリフィル要求を受けた場合に、CMUコントローラ31はL1タグキャッシュ33a、33dを活性化して読み出しても良い。この場合には、CMU3がプロセッサユニット1bからリフィル要求を受けた場合に、パターンの1番目のインターベンション転送のものであるか、パターンの3番目のインターベンション転送のものであるかをCMUコントローラ31が判別する必要はなくなる。
【0056】
本実施の形態においては、特定のプロセッサペアでのインターベンション転送の回数ではなく、所定のインターベンション転送パターンとの一致回数に基づいてインターベンション予測モードのON/OFFを切り替えるため、第1の実施の形態と比較してより厳しい条件で予測を行うこととなる。したがって、インターベンション転送の予測の精度が高まるため、予測が外れることによって消費電力や処理時間が増大することを抑えることができる。
【0057】
(第3の実施の形態)
図15は、本発明の第3の実施の形態にかかるマルチプロセッサの構成を示す図である。
上記第1、第2の実施の形態においては、マルチプロセッサ内のキャッシュラインやデータの流れに基づいてインターベンション転送の予測を行っていたが、本実施形態においては、マルチプロセッサ内のハードウェア構成や消費電力を考慮してインターベンション転送を予測する。
マルチプロセッサの構成は第1の実施形態とほぼ同様であるが、予測ユニットであるPIU32が、内部にバイアスユニット323をさらに有する点で相違する。なお、PIカウンタ321については、第1の実施の形態と同様であり、プロセッサペアに対応するカウンタを備えている。
【0058】
バイアスユニット323は、PIカウンタ321の各プロセッサペアに対応するカウンタが予測モードオン閾値を超えるか否かの判定を行う論理への一定のバイアスをかける働きをする。
例を挙げると、過去にプロセッサユニット1aからプロセッサユニット1bに5回のインターベンション転送が行われており、「PUb←PUa」のカウンタ値として記憶されているとする。また一方で、過去にプロセッサユニット1cからプロセッサユニット1bに6回のインターベンション転送が行われており、「PUb←PUc」のカウンタ値として記憶されているとする。ここで、両者の予測モードオン閾値(Th)が共に8だったとする。この時のバイアスユニット323が「PUb←PUa」に「×2倍」のバイアスを、「PUb←PUc」に「×1倍」のバイアス(実質の無バイアス)をかけたとする。この場合、プロセッサユニット1aからプロセッサユニット1bへのインターベンション転送は、過去のインターベンション転送の回数はプロセッサユニット1cに比べて少ないが、PUb←PUaのカウンタのカウンタ値が予測モードオンの閾値を超えるため、(5回×2倍=10回>閾値(8回))、プロセッサユニット1bを転送先とするインターベンション転送予測としてプロセッサユニット1aが転送元として予測される。
【0059】
図15のように両者へのバイアスが無い状態では、両者とも閾値を超えていないため、プロセッサユニット1bからキャッシュミスのリフィル要求が届いた際に、CMUコントローラ31は全てのタグキャッシュ(L1タグキャッシュ33a〜33d、L2タグキャッシュ35)を読み、L1タグキャッシュ33aとL1タグキャッシュ33cとにキャッシュヒットを得る(既に、同じキャッシュラインをL1キャッシュメモリ11aとL1キャッシュメモリ11cとでシェアしている状況)。ここで、L1キャッシュメモリ11aからインターベンション転送するか、L1キャッシュメモリ11cからインターベンション転送するかは、プロセッサユニット1の実装状態に依存する。
【0060】
L1キャッシュメモリ11aが選択されれば、図16に示すように、L1キャッシュメモリ11aからL1キャッシュメモリ11bへインターベンション転送が行われ、PIU32内のPIカウンタ321の対応するプロセッサペアのカウンタがインクリメントされる。一方、L1キャッシュメモリ11cが選択されれば、図17に示すように、L1キャッシュメモリ11cからL1キャッシュメモリ11bへインターベンション転送が行われ、PIU32内のPIカウンタの対応するプロセッサペアのカウンタがインクリメントされる。この場合、L1キャッシュメモリ11aの持つキャッシュラインとL1キャッシュメモリ11cの持つキャッシュラインとは同じであるため、L1キャッシュメモリ11bに達するキャッシュライン情報は同じであり、キャッシュのコヒーレンシは保たれる。しかし、インターベンション転送に伴う消費電力は、L1キャッシュメモリ11cからL1キャッシュメモリ11bへの転送を行った方が大きくなる(システム上におけるプロセッサ間の距離が遠く、転送時に駆動を要する不図示のハードウェア数も増加するため。)。そこで、バイアスユニット323によって、L1キャッシュメモリ11a側に一定のバイアスをかけることで、PIU32がL1キャッシュメモリ11aからのインターベンション予測モードへ切り替わることを容易にし、消費電力の少ないL1キャッシュメモリ11aからL1キャッシュメモリ11bへのインターベンション転送を促すことができる。
【0061】
図18に、バイアスユニット323によってL1キャッシュメモリ11aに関するインターベンション予測モードが有効になった状態を示す。インターベンション予測モードが有効になった状態においては、PIU32に従いL1タグキャッシュ33aのみを引くことでヒットを得て、インターベンション転送に伴う消費電力が少ないL1キャッシュメモリ11aからL1キャッシュメモリ11bへの転送を行うことができる。
【0062】
このように、より消費電力の少ないインターベンション転送の予測モードへの切り替えに対して、バイアスユニット323によって一定の優先度を与えることで、マルチプロセッサ全体としての消費電力を低減できる。また、バイアスユニット323が無い構成であっても、PIU32内のPIカウンタ321の予測モードオン閾値を、転送に伴う消費電力の少ないプロセッサユニット間では低く設定することで、消費電力の少ないインターベンション転送への切り替えの優先度を高めることができる。
【0063】
以上の説明においては、複数のプロセッサユニット1がCMU3を介して連結されたマルチプロセッサを例としたが、その接続形態は任意である。他の接続方法の一形態として、図19に、各プロセッサユニット1、CMU3、メインメモリ2をリングバスによって接続する構成を示す。また、図20、図21に、リングバス形態のマルチプロセッサにおけるインターベンション転送の様子を示す。図示するように、プロセッサユニット1aからプロセッサユニット1bへのインターベンション転送に比べ、プロセッサユニット1cからプロセッサユニット1bへのインターベンション転送は、リングバス上の距離も遠く、同時に消費電力も高いことがうかがえる。このようなリングバス形態のマルチプロセッサに対しても、上記のバイアスユニット323を設けたり、予測モードオン閾値を個別に設定するなどすることにより、消費電力が少ないインターベンション転送に対して優先度を持たせることが可能となる。
【0064】
(第4の実施の形態)
図22は、本発明の第4の実施の形態にかかるマルチプロセッサの構成を示す図である。第1〜第3の実施の形態のマルチプロセッサとの構成の相違は、PIU32がPIカウンタ321の代わりにLocked Adder記憶装置322(322a〜322d)を備える点である。Locked Adder記憶装置322a〜322dは、各プロセッサユニットからのll命令によってロックを試みたアドレスを格納する。各プロセッサユニットに対応するLocked Adder記憶装置322a〜322dが記憶するアドレスの数は任意であり、一つに限られない(実装では、ハードウェアコストとのトレードオフによって記憶数が決まる。)。
【0065】
複数のプロセッサユニットがメモリ空間を共有してプログラム処理を行う場合、ある一定の処理区間において、他のプロセッサユニットの介入を許容できない「排他的処理実行」が必要なケースが存在する。この場合、プロセッサユニットは、以下のようなシーケンスを行うことで一定のメモリ領域を扱うためのロック変数(1:ロック、0:アンロック)を獲得した後に排他制御を行い、処理後にロック変数とともにメモリ領域を解放する。
==<排他制御の実行フロー>==========
[Retry]
ld R0,RA
bnez R0 [Retry]
movi R0,1
ll R1,RA
sc R0,RA
beqz R0 [Retry]
〜〜排他処理〜〜
movi R0,0
suc R0,RA
========================
【0066】
ここで、上記フローにおける各実行命令について説明する。「ld(Load)」は、メモリ領域から値を読み込む命令であり、上記フローではロック変数を格納するメモリアドレスRAから、現状のロック変数の値をレジスタR0に読み込んでいる。「bnez(Branch Not Equal Zero)」は、レジスタの値が0と一致しない場合に、指定先のラベルに分岐する命令であり、上記フローにおいては読み出したロック変数が0(アンロック)でない場合は、[Retry]ラベルまで戻ってフローをやり直す。「movi(Move Immediately)」は、即値を指定のアドレスに格納する命令であり、上記フローではレジスタR0に値1を格納している。「ll(Load Locked)」は、指定されたメモリアドレスから値を読み込むと同時に、「自プロセッサがこの領域をロックするべくアクセス中である」というロック指示子(及びアドレス)を登録する命令であり、上記フローでは、レジスタRAで指定されたメモリアドレスからR1へ値を読み出すとともに、指示子(及びアドレス)を登録している。llに続く「sc(Store Conditional)」は、「ロック指示子を登録後に他のプロセッサが同じ領域にアクセスを行っていない」ことを条件に、指定されたメモリ領域に値を書き込む命令であり、上記フローでは、レジスタRAで指定されたメモリアドレスへR0(値は1)の格納を試み、成功(1)又は失敗(0)として結果をR0に格納している。「beqz(Branch Equal Zero)」は、レジスタの値が0と一致する場合に指定先のラベルに分岐する命令であり、上記フローではsc命令の成功・失敗の結果が0(失敗)の場合は[Retry]ラベルに戻ってフローをやり直す。
ここまでの処理を終えた時点で、上記のフローを行ったプロセッサユニットは、排他的にロック変数とそれに対応したメモリ領域とを獲得しているため、一連の排他処理を行う。排他処理を行った後は、ロック変数を解放すべく値0を「suc(Store Unconditional)」によって無条件に書き込み、ロック変数をアンロック(値0)に戻して領域を解放している。
【0067】
なお、上記のフローは、“COMPUTER ARCHITECTURE A QUANTITATIVE APPROACH 2nd Edition”、John L Hennessy & David A Patterson著に説明されているように公知のものである。
【0068】
以下、排他処理のフローにリンクしたインターベンション予測方式について説明する。排他制御を伴うプログラム実行は、さらに下記の三つに分類される。
(1)「sc」に連動したインターベンション予測方式
(2)「ll」に連動したインターベンション予測方式
(3)「ld」に連動したインターベンション予測方式
【0069】
(1)の「sc」に連動したインターベンション予測方式について説明する。
プロセッサユニット1aが上記フローによってあるメモリ領域を確保して排他処理を行い、解放したとする。その後、プロセッサユニット1bが同じメモリ領域に対して上記フローを実行し、「sc」によってメモリ領域へのロック変数を書き込む際の様子を図23に示す。
図23において、プロセッサユニット1bがsc命令を実行し、PIU32内のLocked Adder記憶装置322a〜322dを確認している。プロセッサBのロック指示子(及びアドレス)を確認し、プロセッサユニット1bがll命令を発行した以降に、他のプロセッサユニットが同じアドレスに配置されたロック変数を同時に確保していないことを確認する。また、同時に、他のプロセッサユニットによって現在確保されているロック変数又は過去に確保されたロック変数のアドレスと、現在プロセッサユニット1bが確保するロック変数のアドレスとが一致するか否かを判定する。このケースでは、プロセッサユニット1aが確保したロック変数を、プロセッサユニット1aでの使用後にプロセッサユニット1bが使用するために確保するため、図23に示したように、PU−A Locked Adder記憶装置322aに記憶されているアドレスとプロセッサユニット1bがscによって確保しようとするロック変数のアドレスとが一致(ヒット)する。
【0070】
この時点で、PIU32は、「プロセッサユニット1bは、プロセッサユニット1aが排他的に使用していたメモリ領域を継承して使用する」ことを検知できたため、以降のプロセッサユニット1b(L1キャッシュメモリ11b)からのキャッシュミスによって要求されるキャッシュラインは、同じ領域を使用していたプロセッサユニット1a内のL1キャッシュメモリ11aに存在すると予測し、インターベンション予測モードをオンにする。
【0071】
インターベンション予測モードがオンした後に、L1キャッシュメモリ11bでキャッシュミスが発生した様子を図24に示す。インターベンション予測モードがオンした状態では、PIU32は、L1キャッシュメモリ11bから要求されるキャッシュラインがL1キャッシュメモリ11aに存在すると予測し、CMU3内のL1キャッシュメモリ11aに関するL1タグキャッシュ33aにのみアクセスし、キャッシュヒットを得ている。このように、排他制御のために用いる命令とアドレスの一致とによりプロセッサ間のインターベンション転送を予測できる。
【0072】
次に、上記(2)の「ll」に連動したインターベンション予測方式について説明する。
上記(1)の「sc」に連動したインターベンション予測方式では、排他制御フローのsc命令に連動してロック変数を確保するアドレスの比較を行っていたが、本方式ではフローの前半にll命令でロック変数へのアクセスを試行した段階で、他のプロセッサユニットが確保したロック変数のアドレスとの比較を行う。これは、scによって最終的にロック変数を確保したプロセッサユニットに対してのみならず、ll命令によってロック変数の確保を試みたものの、sc命令の段階でロック変数を確保できなかったプロセッサユニットに対しても有効にインターベンション転送の予測を行う方式である。
【0073】
次に、上記(3)の「ld」に連動したインターベンション予測方式について説明する。
本方式では、フローの始めにld命令でロック変数の値を確認するためにアクセスした段階で、他のプロセッサユニットが確保したロック変数のアドレスとの比較を行う。これは、まだロック変数の確保を試みてはいないが、今後試みるであろうプロセッサユニットに対してもインターベンション転送の予測を行う方式である。また、本方式のようにld命令に限らず、単に他のプロセッサユニットが確保したロック変数のアドレスに対して、何らかのメモリアクセスを行った段階で、インターベンション予測に反映する(制限を緩める)方式も考えられる。
【0074】
排他制御フローの領域解放にリンクした解除方式について説明する。上記のように、インターベンション予測モードへの切り替えは、排他制御実行フローにおいて、排他処理に移る複数の段階で(ld、ll、scにリンクした形で)各命令にリンクさせることが可能であるが、インターベンション予測モードの解除は、「排他処理」後にロック変数を解放する「suc」命令にリンクさせる。すなわち、あるプロセッサユニットが他のプロセッサユニットが用いていたロック変数とメモリ領域とを継承して排他処理を行っている間は、インターベンション予測モードを有効に保ち、その領域を解放する手順(ここではsuc命令によるロック変数の解除)とともにインターベンション予測モードを無効化する。
【0075】
このように、本実施の形態においては、排他制御フローの命令にリンクさせてインターベンション予測モードのオン・オフを切り替え、転送対象のキャッシュラインが存在すると予測されるキャッシュメモリに関するタグメモリのみを起動してキャッシュラインの有無を確認する。よって、特定のプロセッサ(L1キャッシュメモリ)ペア間のインターベンション転送時におけるHW駆動率を低下させ、マルチプロセッサの消費電力を低減できる。
【0076】
なお、上記各実施の形態は本発明の好適な実施の一例であり、本発明はこれらに限定されることなく、様々な変形が可能である。すなわち、上記の各実施の形態は、当該分野の技術者によって、上記説明の要綱に基づき多様なマルチプロセッサに対して修正可能であり、上記の説明は当該分野に対する開示内容として広く理解されるべきであり、本発明を限定するものではない。
【符号の説明】
【0077】
1 プロセッサユニット、2 メインメモリ、3 CMU、11 L1キャッシュメモリ、32 PIU、33 L1タグキャッシュ、34 L2キャッシュメモリ、35 L2タグキャッシュ、321 PIカウンタ、323 バイアスユニット、324 インターバルカウンタ、325 インターベンションパターン格納部。
【特許請求の範囲】
【請求項1】
主記憶装置と、
前記主記憶装置の記憶データを一時記憶するキャッシュメモリを夫々備え、前記主記憶装置を共有する複数のプロセッサと、
前記複数のプロセッサのキャッシュメモリのコヒーレンシを管理するコヒーレンシ管理ユニットと、
を備え、
前記コヒーレンシ管理ユニットは、
前記キャッシュメモリの各々に対応して設けられ、対応するキャッシュメモリにキャッシュされたキャッシュデータのタグを格納する複数のタグキャッシュと、
前記プロセッサからのリフィル要求に応じて、前記複数のタグキャッシュを参照して前記リフィル要求に対応するキャッシュデータがキャッシュされたキャッシュメモリを判別し、判別したキャッシュメモリを転送元としリフィル要求元のキャッシュメモリを転送先として前記リフィル要求に対応するキャッシュデータの転送を行うデータ転送手段と、
前記キャッシュメモリ間のキャッシュデータの転送の監視に基づく所定の予測処理を行うことで、転送先別に一つの転送元を仮決定する仮決定手段とを有し、
前記データ転送手段は、前記仮決定手段の仮決定結果が得られた後は、前記キャッシュデータの転送を行う際、前記仮決定した一つの転送元に対応するタグキャッシュのみを活性化し、活性化されたタグキャッシュのみを参照してリフィル要求に対応するキャッシュデータがキャッシュされているか否かを判別することを特徴とするマルチプロセッサ。
【請求項2】
前記仮決定手段は、転送先別に、所定の転送回数に最も早く到達した転送元を判別し、判別した転送元を転送先別の一つの転送元として仮決定することを特徴とする請求項1記載のマルチプロセッサ。
【請求項3】
前記仮決定手段は、同じキャッシュラインについての連続的な2回以上の転送を含む複数の転送パターンのうちで、所定の実行回数に最も早く到達した転送パターンを判別し、判別した転送パターン中に含まれる転送元、転送先の関係から、転送先別の一つの転送元を仮決定することを特徴とする請求項1記載のマルチプロセッサ。
【請求項4】
前記データ転送手段は、前記リフィル要求に対応するキャッシュデータがキャッシュされたキャッシュメモリが複数個判別された場合は、キャッシュデータの転送の際のデータ転送経路が短いキャッシュメモリを優先的に選択することを特徴とする請求項1から3のいずれか1項記載のマルチプロセッサ。
【請求項5】
前記仮決定手段は、当該キャッシュメモリを転送先とした前記仮決定結果を得た後に、該仮決定結果とは転送元が相違し転送先が一致するキャッシュデータの転送が前記データ転送手段によって所定回数行われた場合には、当該キャッシュメモリを転送先とする転送元の仮決定を取り消すことを特徴とする請求項1から4のいずれか1項記載のマルチプロセッサ。
【請求項6】
前記仮決定手段は、所定時間が経過するごとに、前記仮決定結果とは転送元が相違し転送先が一致するキャッシュデータの転送が1回行われたとみなすことを特徴とする請求項5記載のマルチプロセッサ。
【請求項7】
前記仮決定手段は、前記複数のプロセッサが前記主記憶装置上のメモリ空間を共有してプログラム処理を行う際に、いずれかのプロセッサが排他制御の下に管理していたメモリ空間を他のプロセッサが継承した場合に、該他のプロセッサが備えるキャッシュメモリを転送先とするキャッシュデータの転送における転送元を前記メモリ空間の継承元のプロセッサが備えるキャッシュメモリと仮決定することを特徴とする請求項1記載のマルチプロセッサ。
【請求項8】
前記仮決定手段は、前記他のプロセッサが前記メモリ空間を解放した場合には、前記他のプロセッサが備えるキャッシュメモリを転送先とするキャッシュデータの転送における転送元を、前記メモリ空間の継承元のプロセッサが備えるキャッシュメモリとする仮決定を取り消すことを特徴とする請求項7記載のマルチプロセッサ。
【請求項9】
前記複数のプロセッサ間で共有される共有キャッシュメモリを有し、
該共有キャッシュメモリが、前記仮決定手段によるキャッシュデータの転送元の仮決定の対象に含まれることを特徴とする請求項1から8のいずれか1項記載のマルチプロセッサ。
【請求項1】
主記憶装置と、
前記主記憶装置の記憶データを一時記憶するキャッシュメモリを夫々備え、前記主記憶装置を共有する複数のプロセッサと、
前記複数のプロセッサのキャッシュメモリのコヒーレンシを管理するコヒーレンシ管理ユニットと、
を備え、
前記コヒーレンシ管理ユニットは、
前記キャッシュメモリの各々に対応して設けられ、対応するキャッシュメモリにキャッシュされたキャッシュデータのタグを格納する複数のタグキャッシュと、
前記プロセッサからのリフィル要求に応じて、前記複数のタグキャッシュを参照して前記リフィル要求に対応するキャッシュデータがキャッシュされたキャッシュメモリを判別し、判別したキャッシュメモリを転送元としリフィル要求元のキャッシュメモリを転送先として前記リフィル要求に対応するキャッシュデータの転送を行うデータ転送手段と、
前記キャッシュメモリ間のキャッシュデータの転送の監視に基づく所定の予測処理を行うことで、転送先別に一つの転送元を仮決定する仮決定手段とを有し、
前記データ転送手段は、前記仮決定手段の仮決定結果が得られた後は、前記キャッシュデータの転送を行う際、前記仮決定した一つの転送元に対応するタグキャッシュのみを活性化し、活性化されたタグキャッシュのみを参照してリフィル要求に対応するキャッシュデータがキャッシュされているか否かを判別することを特徴とするマルチプロセッサ。
【請求項2】
前記仮決定手段は、転送先別に、所定の転送回数に最も早く到達した転送元を判別し、判別した転送元を転送先別の一つの転送元として仮決定することを特徴とする請求項1記載のマルチプロセッサ。
【請求項3】
前記仮決定手段は、同じキャッシュラインについての連続的な2回以上の転送を含む複数の転送パターンのうちで、所定の実行回数に最も早く到達した転送パターンを判別し、判別した転送パターン中に含まれる転送元、転送先の関係から、転送先別の一つの転送元を仮決定することを特徴とする請求項1記載のマルチプロセッサ。
【請求項4】
前記データ転送手段は、前記リフィル要求に対応するキャッシュデータがキャッシュされたキャッシュメモリが複数個判別された場合は、キャッシュデータの転送の際のデータ転送経路が短いキャッシュメモリを優先的に選択することを特徴とする請求項1から3のいずれか1項記載のマルチプロセッサ。
【請求項5】
前記仮決定手段は、当該キャッシュメモリを転送先とした前記仮決定結果を得た後に、該仮決定結果とは転送元が相違し転送先が一致するキャッシュデータの転送が前記データ転送手段によって所定回数行われた場合には、当該キャッシュメモリを転送先とする転送元の仮決定を取り消すことを特徴とする請求項1から4のいずれか1項記載のマルチプロセッサ。
【請求項6】
前記仮決定手段は、所定時間が経過するごとに、前記仮決定結果とは転送元が相違し転送先が一致するキャッシュデータの転送が1回行われたとみなすことを特徴とする請求項5記載のマルチプロセッサ。
【請求項7】
前記仮決定手段は、前記複数のプロセッサが前記主記憶装置上のメモリ空間を共有してプログラム処理を行う際に、いずれかのプロセッサが排他制御の下に管理していたメモリ空間を他のプロセッサが継承した場合に、該他のプロセッサが備えるキャッシュメモリを転送先とするキャッシュデータの転送における転送元を前記メモリ空間の継承元のプロセッサが備えるキャッシュメモリと仮決定することを特徴とする請求項1記載のマルチプロセッサ。
【請求項8】
前記仮決定手段は、前記他のプロセッサが前記メモリ空間を解放した場合には、前記他のプロセッサが備えるキャッシュメモリを転送先とするキャッシュデータの転送における転送元を、前記メモリ空間の継承元のプロセッサが備えるキャッシュメモリとする仮決定を取り消すことを特徴とする請求項7記載のマルチプロセッサ。
【請求項9】
前記複数のプロセッサ間で共有される共有キャッシュメモリを有し、
該共有キャッシュメモリが、前記仮決定手段によるキャッシュデータの転送元の仮決定の対象に含まれることを特徴とする請求項1から8のいずれか1項記載のマルチプロセッサ。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【公開番号】特開2011−54077(P2011−54077A)
【公開日】平成23年3月17日(2011.3.17)
【国際特許分類】
【出願番号】特願2009−204380(P2009−204380)
【出願日】平成21年9月4日(2009.9.4)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】
【公開日】平成23年3月17日(2011.3.17)
【国際特許分類】
【出願日】平成21年9月4日(2009.9.4)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】
[ Back to top ]