プログラムの命令を実行する装置および命令をキャッシュするシステム
【課題】キャッシュ・メモリに命令をキャッシュする場合における保持内容の冗長さを減少させ、効率の良いキャッシュ・システムを実現する。
【解決手段】命令フェッチ・ユニット１０と、命令キャッシュ２０と、命令とこの命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持するマクロ・キャッシュ部３０と、命令キャッシュ２０におけるキャッシュ・ヒットの頻度が高い命令をマクロ・キャッシュ部３０に保持させるマクロ登録判断部４０と、を備える。マクロ・キャッシュ部３０は、マクロ登録判断部４０により保持するように指示された命令と同一の命令を既に保持している場合は、その命令を指定するアドレスを、既に保持しているその命令と関連付けて保持し、マクロ登録判断部４０により保持するように指示された命令と同一の命令を保持していない場合は、その命令とその命令を指定するアドレスとを関連付けて保持する。
【解決手段】命令フェッチ・ユニット１０と、命令キャッシュ２０と、命令とこの命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持するマクロ・キャッシュ部３０と、命令キャッシュ２０におけるキャッシュ・ヒットの頻度が高い命令をマクロ・キャッシュ部３０に保持させるマクロ登録判断部４０と、を備える。マクロ・キャッシュ部３０は、マクロ登録判断部４０により保持するように指示された命令と同一の命令を既に保持している場合は、その命令を指定するアドレスを、既に保持しているその命令と関連付けて保持し、マクロ登録判断部４０により保持するように指示された命令と同一の命令を保持していない場合は、その命令とその命令を指定するアドレスとを関連付けて保持する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理装置（プロセッサ）およびそのキャッシュ・システムに関し、特に命令を保持（キャッシュ）するキャッシュ・システムに関する。
【背景技術】
【０００２】
コンピュータにおいて、処理速度を向上させる手段として、キャッシュ・メモリを設けることが一般的に行われている。キャッシュ・メモリは、アクセス速度の高速なメモリであり、メイン・メモリから読み出したデータをキャッシュ・メモリに一時的に保持（キャッシュ）する。処理装置（プロセッサ）は、取得しようとするデータがキャッシュ・メモリに存在している場合には、アクセス速度の遅いメイン・メモリにアクセスすることなくキャッシュ・メモリからデータを取得する。
【０００３】
処理装置が使用するキャッシュ・メモリとしては、通常、プログラムの命令を保持する命令キャッシュ（インストラクション・キャッシュ）と、処理対象のデータを保持するデータ・キャッシュとが用意される。キャッシュ・メモリは、キャッシュ・ラインと呼ばれる単位でデータを保持する。命令キャッシュの場合、保持されるデータは命令列（Instructions）である。
【０００４】
ところで、プロセッサの実行コードは、キャッシュ・ラインのサイズ程度の短い命令列で見ると、同じコード列になる場合が多い。例えば、タスク切り替え時のレジスタの退避命令や、インライン展開されたコード等は、同じコード列になり易い。このため、命令キャッシュは、同じ命令列が多重に保持され、キャッシュ内容が冗長になる場合が多い（例えば、非特許文献１、２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Marios Kleanthous他、「Dynamically Detecting Cache-Content-Duplication in Instruction Caches」、Department of Computer Science University of Cyprus、February 2007、TR-07-03、[URL]http://www.cs.ucy.ac.cy/carch/xi/trs/tr-07-03.pdf
【非特許文献２】Marios Kleanthous他、「The Duplication of Content in Instruction Caches and its Performance Implications」、Department of Computer Science University of Cyprus、January 2005、CS-TR-01-2005、[URL] http://www.cs.ucy.ac.cy/carch/xi/trs/Cache_Content_Duplication-tr.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００６】
命令キャッシュは、キャッシュ・ラインにおいて同じ命令列が多重に保持（キャッシュ）されることにより、保持した内容が冗長になる場合が多い。
そこで、本発明は、キャッシュ・メモリに命令を保持（キャッシュ）する場合における保持内容の冗長さを減少させ、効率の良いキャッシュ・システムを実現することを目的とする。
【課題を解決するための手段】
【０００７】
上記の目的を達成するため、本発明は、次のような装置として実現される。この装置は、プログラムの命令を読み込んで実行する装置であって、メイン・メモリ上のアドレスにより指定した命令を読み込む命令フェッチ・ユニットと、この命令フェッチ・ユニットにより読み込まれた命令を保持する第１のキャッシュ・メモリと、命令とこの命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、命令フェッチ・ユニットから取得したアドレスに基づき、アドレスに関連付けられた命令を特定する第２のキャッシュ・メモリと、第１のキャッシュ・メモリに保持された命令のうち、命令フェッチ・ユニットにより読み込まれた回数が予め定められた閾値を超えた命令を、第２のキャッシュ・メモリに保持させる、判断部と、命令フェッチ・ユニットが読み込もうとする命令が第１のキャッシュ・メモリおよび第２のキャッシュ・メモリのいずれにも保持されている場合に、命令の読み込み元として第２のキャッシュ・メモリを選択する選択部と、を備える。
そして、第２のキャッシュ・メモリは、判断部により保持するように指示された命令と同一の命令を既に保持している場合は、その命令を指定するアドレスを、既に保持しているその命令と関連付けて保持し、判断部により保持するように指示された命令と同一の命令を保持していない場合は、その命令とその命令を指定するアドレスとを関連付けて保持する。
また、第２のキャッシュ・メモリに保持された命令と同一のアドレスにおける命令は、第１のキャッシュ・メモリから消去される。
【０００８】
さらに好適には、第２のキャッシュ・メモリは、ＳＲＡＭ（Static Random Access Memory）にて構成される。
【０００９】
また、上記の目的を達成する他の本発明は、次のようなシステムとして実現される。このシステムは、プログラムの命令をキャッシュするシステムにおいて、アドレスを指定されてメイン・メモリから読み込まれた命令をキャッシュする第１のキャッシュ手段と、この第１のキャッシュ手段にキャッシュされた命令のうち、所定の条件を満足する命令をキャッシュする第２のキャッシュ手段と、読み込まれる対象の命令が第１のキャッシュ手段および第２のキャッシュ手段のいずれにもキャッシュされている場合に、この命令の読み込み元を選択する選択手段と、を備える。そして、第２のキャッシュ手段は、命令とこの命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、読み込み手段から取得したアドレスに基づき、アドレスに関連付けられた命令を特定する。
【００１０】
より詳細には、第２のキャッシュ手段は、キャッシュしようとする命令と同一の命令を既に保持している場合は、この命令を指定するアドレスを、既に保持している命令と関連付けて保持し、キャッシュしようとする命令と同一の命令を保持していない場合は、この命令とこの命令を指定するアドレスとを関連付けて保持する。
【００１１】
また、より好適には、第２のキャッシュ手段は、第１のキャッシュ手段にキャッシュされた命令のうち、読み込み要求に対してヒットした回数が予め定められた閾値を超えた命令をキャッシュする。
さらに好適には、第２のキャッシュ手段にキャッシュされた命令と同一のアドレスにおけるこの命令は、第１のキャッシュ手段から消去される。
そして、さらに好適には、選択手段は、読み込まれる対象の命令が第１のキャッシュ手段および第２のキャッシュ手段のいずれにもキャッシュされている場合に、第２のキャッシュ手段から読み込むことを選択する。
【発明の効果】
【００１２】
本発明によれば、キャッシュ・メモリに命令を保持（キャッシュ）する場合における保持内容の冗長さを減少させ、効率の良いキャッシュ・システムを実現することができる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態によるキャッシュ・システムの構成例を示す図である。
【図２】本実施形態のマクロ・キャッシュ部の構成例を示す図である。
【図３】本実施形態の命令判断部を実現する論理回路の構成例を示す図である。
【図４】本実施形態の命令判断部の動作例を示すフローチャートである。
【図５】本実施形態のマクロ登録判断部を実現する論理回路の構成例を示す図である。
【図６】本実施形態のマクロ登録判断部の動作を示すフローチャートである。
【図７】本実施形態における命令読み込み時のＣＰＵの動作を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照して、本発明の実施形態について詳細に説明する。
プロセッサの実行コードは、ＪＩＴ（Just In Time）のような特殊な例外を除き、メイン・メモリ上での書き換えが発生せず、命令を格納するためにアロケートされたアドレスが変わることもない。すなわち、メイン・メモリ上のアドレスに対して命令が一意に決まる。これに基づき、本実施形態は、アドレスに関連づけされたマクロとして命令列を特定するキャッシュ・システムを実現する。なお、本実施形態では、従来の命令キャッシュ（キャッシュ・メモリ）を用いたキャッシュ・システムに対する付加的な構成として、上記のマクロによるキャッシュ・システムを構成する場合を例として説明する。
【００１５】
＜システム構成＞
図１は、本実施形態によるキャッシュ・システムの構成例を示す図である。
図１に示す構成例において、処理装置（プロセッサ）であるＣＰＵ（Central Processing Unit）１００は、チップ上のバス（オン・チップ・バス）２００に接続されている。図示のように、本実施形態のＣＰＵ１００は、命令フェッチ・ユニット１０と、第１のキャッシュ手段としての命令キャッシュ２０とを備える。また、ＣＰＵ１００は、第２のキャッシュ手段として、マクロ・キャッシュ部３０と、マクロ登録判断部４０とを備え、さらに読み込み対象選択部５０とを備える。なお、図１には、ＣＰＵ１００の構成のうち、本実施形態に関わる構成のみを記載している。
【００１６】
命令フェッチ・ユニット１０は、ＣＰＵ１００がプログラムの処理を実行するために命令を読み込む（フェッチする）。命令の取得は、取得しようとする命令のメイン・メモリ（図示せず）上のアドレスを指定することによって行われる。命令フェッチ・ユニット１０は、取得しようとする命令が、命令キャッシュ２０に保持（キャッシュ）されているか、またはマクロ・キャッシュ部３０にマクロ３１（後述）として登録されている場合（キャッシュ・ヒットに相当）には、これらから命令を取得する。一方、取得しようとする命令が命令キャッシュ２０にもマクロ・キャッシュ部３０にも存在しない場合（キャッシュ・ミスに相当）には、メイン・メモリにアクセスして命令を取得する。
【００１７】
命令キャッシュ２０は、一般的なキャッシュ・メモリにおける命令キャッシュである。すなわち、ＣＰＵ１００が処理を実行するためにメイン・メモリから命令（命令列）を読み込むと、読み込まれた命令（命令列）は命令キャッシュ２０に保持され、次にＣＰＵ１００が同様の処理を実行する際に当該命令が命令キャッシュ２０から読み込まれる。命令キャッシュ２０としては、例えば連想メモリ（Content Addressable Memory；ＣＡＭ）をタグとして使ったＳＲＡＭが用いられる。
【００１８】
マクロ・キャッシュ部３０は、命令フェッチ・ユニット１０がフェッチする命令列を、メイン・メモリ上の当該命令列のアドレスと関連付けたマクロ３１として保持（キャッシュ）する。このマクロ３１は、キャッシュ対象の命令列ごとに作成される。マクロ・キャッシュ部３０には、命令キャッシュ２０に保持された命令のうち、マクロ登録判断部４０により登録対象とされた命令列が保持される。マクロ・キャッシュ部３０およびマクロ３１の詳細については後述する。
【００１９】
マクロ登録判断部４０は、命令キャッシュ２０に保持されている命令列をマクロ・キャッシュ部３０に登録するか否かを判断する。本実施形態において、マクロ登録判断部４０は、命令キャッシュ２０における命令列ごとのキャッシュ・ヒットの頻度（命令フェッチ・ユニット１０により読み込まれる頻度）に基づいて、命令列をマクロ・キャッシュ部３０に登録するか否かを判断する。マクロ登録判断部４０の機能および動作の詳細については後述する。
【００２０】
読み込み対象選択部５０は、同一の命令列が命令キャッシュ２０とマクロ・キャッシュ部３０の両方に保持されている場合に、どちらから読み込むかを選択する。本実施形態では、命令フェッチ・ユニット１０が読み込もうとする命令列がマクロ・キャッシュ部３０に保持されている場合は、マクロ・キャッシュ部３０から命令列を読み込む。具体的には、例えば、命令フェッチ・ユニット１０が読み込もうとする命令列をマクロ・キャッシュ部３０が保持している場合に、マクロ・キャッシュ部３０が、マクロ・キャッシュ部３０からの読み込みを選択するように読み込み対象選択部５０へ指示する。
【００２１】
＜マクロ・キャッシュ部３０の構成＞
図２は、マクロ・キャッシュ部３０の構成例を示す図である。
図２に示すように、マクロ・キャッシュ部３０は、複数（図示の例ではｎ個）のマクロ３１を含む。個々のマクロ３１は、１つの命令列とこの命令列に関連付けられたアドレスとを保持するマクロ保持手段３１ａと、マクロ３１にアドレスを登録するための命令判断部３２とを備える。命令判断部３２の機能および動作の詳細については後述する。
【００２２】
マクロ保持手段３１ａには、上記のように、命令列とこの命令列に関連付けられたアドレスとが保持される。このマクロ保持手段３１ａは、一つの命令列に対して、複数のアドレスを関連付けて保持することができるように構成される。命令列およびアドレスを保持する記憶手段（メモリ）としては、一般的なキャッシュ・メモリに用いられる連想メモリではなく、例えばＳＲＡＭ（Static Random Access Memory）が用いられる。
【００２３】
また上記のように、マクロ３１には、命令キャッシュ２０に保持された命令列が、所定の条件を満足する場合に登録される。そのため、マクロ保持手段３１ａに保持される命令列のサイズは、通常は、命令キャッシュ２０のキャッシュ・ラインのサイズと等しくなる。ただし、マクロ保持手段３１ａに登録できる命令列のサイズは、このサイズに限定されない。システムの仕様等に応じて、他のサイズで命令列を保持するようにしても良い。マクロ・キャッシュ部３０に設けられるマクロ３１の数や、マクロ３１における命令列に関連付けが可能なアドレスの数は、マクロ保持手段３１ａを実現する記憶手段の記憶容量やシステムの仕様等に基づいて決定される。
【００２４】
図３は、命令判断部３２を実現する論理回路の構成例を示す図である。
図３に示すように、命令判断部３２は、比較対象の命令を選択するセレクタ３２ａと、選択された命令を比較するコンパレータ３２ｂと、一致した命令の数を計数するカウンタ３２ｃとを備える。
【００２５】
セレクタ３２ａは、マクロ３１のマクロ保持手段３１ａに保持されている命令列を構成する個々の命令（命令フェッチ・ユニット１０がフェッチする命令単位）を、コンパレータ３２ｂによる比較の対象とするために、先頭から順次選択する。
【００２６】
コンパレータ３２ｂは、命令フェッチ・ユニット１０により命令キャッシュ２０から読み出された命令列を取得する。そして、取得した命令列とセレクタ３２ａにより選択された命令とを比較する。
【００２７】
カウンタ３２ｃは、コンパレータ３２ｂによる比較で一致した命令の数を計数し、その計数を元にセレクタ３２ａにどの命令と比較するかを指示する。カウンタ３２ｃの初期値は「１」であり、マクロ保持手段３１ａに登録されている命令列を構成する命令の数「ｍ」まで計数する。例えば、命令コードが１バイトで、キャッシュ・ラインのサイズが３２バイトであれば、ｍ＝３２である。
【００２８】
図４は、命令判断部３２の動作例を示すフローチャートである。
図４を参照すると、命令判断部３２は、まず、命令フェッチ・ユニット１０が取得しようとする命令が命令キャッシュ２０においてヒットした場合に、命令キャッシュ２０から読み出された命令を取得する（ステップ４０１、４０２）。そして、命令判断部３２は、セレクタ３２ａにより、マクロ保持手段３１ａに保持されている命令列のうち先頭の命令を比較対象として選択する（ステップ４０３）。次に、命令判断部３２は、コンパレータ３２ｂにより、ステップ４０２で取得した命令とステップ４０３で選択した命令とを比較する（ステップ４０４）。比較した命令が一致しない場合は、処理を終了する（ステップ４０５）。
【００２９】
ステップ４０４で比較した命令が一致した場合、命令判断部３２は、カウンタ３２ｃの値を調べる（ステップ４０５、４０６）。カウンタ３２ｃの値が「ｍ」でなければ、命令判断部３２は、カウンタ３２ｃの値を１加算する（ステップ４０７、４０８）。そして、命令判断部３２は、セレクタ３２ａにより、マクロ保持手段３１ａに保持されている命令列を構成する命令のうち次の命令を選択し（ステップ４０９）、命令キャッシュ２０から次の命令が読み出されるのを待つ（ステップ４１０）。命令キャッシュ２０から次の命令が読み出されたならば、命令判断部３２は、ステップ４０４以降の処理を繰り返す。
【００３０】
ステップ４０６、４０７で、カウンタ３２ｃの値が「ｍ」である場合、命令キャッシュ２０から読み出されたｍ個の命令の組（命令列）が、マクロ保持手段３１ａに保持されている命令列と一致したことを意味する。そこで、命令判断部３２は、一致した命令列を構成する命令のうち、最初に命令キャッシュ２０においてヒットした命令のアドレスを、マクロ保持手段３１ａに登録する（ステップ４０７、４１１）。そして、マクロ保持手段３１ａに登録した命令列を命令キャッシュ２０から消去する（ステップ４１１）。
【００３１】
＜マクロ登録判断部４０の構成＞
図５は、マクロ登録判断部４０を実現する論理回路の構成例を示す図である。
図５に示すように、マクロ登録判断部４０は、判断対象となるアドレスを取り込むためのセレクタ４０ａと、取り込んだアドレスの出現頻度を調べるためのコンパレータ４０ｂおよびアドレス履歴テーブル４０ｃとを備える。
【００３２】
セレクタ４０ａは、命令フェッチ・ユニット１０が取得しようとする命令が命令キャッシュ２０においてヒットしたことを条件として、命令フェッチ・ユニット１０により指定されたアドレス（取得しようとする命令のアドレス）を取り込む。
【００３３】
コンパレータ４０ｂは、セレクタ４０ａにより取り込まれたアドレスと、アドレス履歴テーブル４０ｃに登録されているアドレスとを比較する。そして、セレクタ４０ａにより取り込まれたアドレスがアドレス履歴テーブル４０ｃに登録されていなければ、そのアドレスを新規にアドレス履歴テーブル４０ｃに登録する。一方、セレクタ４０ａにより取り込まれたアドレスがアドレス履歴テーブル４０ｃに登録されている場合、コンパレータ４０ｂは、そのアドレスが命令フェッチ・ユニット１０による取得対象となった回数を示すフラグ・データ（図５の「Ｆ」）を更新する。
【００３４】
アドレス履歴テーブル４０ｃは、以前に命令フェッチ・ユニット１０が取得しようとした命令のアドレスと、そのアドレスが命令フェッチ・ユニット１０による取得対象となった回数を示すフラグ・データとを含むテーブルである。コンパレータ４０ｂによる比較の結果、セレクタ４０ａにより取り込まれたアドレスがアドレス履歴テーブル４０ｃに登録されていなければ、そのアドレスが新規に登録される。一方、コンパレータ４０ｂによる比較の結果、セレクタ４０ａにより取り込まれたアドレスが既にアドレス履歴テーブル４０ｃに登録されていれば、そのアドレスのフラグ・データの値が１加算される（更新）。このアドレス履歴テーブル４０ｃは、例えば、マクロ３１のマクロ保持手段３１ａと共通のＳＲＡＭに記憶される。アドレス履歴テーブル４０ｃに登録可能なアドレスおよびフラグ・データの数（エントリ数）は、アドレス履歴テーブル４０ｃを記憶する記憶手段の記憶容量やシステムの仕様等に基づいて決定される。
【００３５】
図６は、マクロ登録判断部４０の動作を示すフローチャートである。
図６を参照すると、マクロ登録判断部４０は、まず、命令フェッチ・ユニット１０が取得しようとする命令が命令キャッシュ２０においてヒットした場合に、セレクタ４０ａにより、命令フェッチ・ユニット１０が指定したアドレス（取得しようとする命令のアドレス）を取り込む（ステップ６０１、６０２）。
【００３６】
次に、マクロ登録判断部４０は、コンパレータ４０ｂにより、ステップ６０２で取得したアドレスがアドレス履歴テーブル４０cに登録されているか否かを判断する（ステップ６０３）。ステップ６０２で取得したアドレスがアドレス履歴テーブル４０cに登録されていない場合、次にマクロ登録判断部４０は、アドレス履歴テーブル４０ｃに登録可能な数のアドレスが既に登録されている（Table full）か否かを判断する（ステップ６０４）。そして、アドレス履歴テーブル４０ｃに空きがあるならば、ステップ６０２で取得したアドレスをアドレス履歴テーブル４０ｃに登録する（ステップ６０５）。
【００３７】
また、アドレス履歴テーブル４０ｃに空きがない場合、マクロ登録判断部４０は、既にアドレス履歴テーブル４０ｃに登録されているアドレスのうちで、特定のアドレスを消去してテーブルの空きエントリを確保する（ステップ６０６）。そして、ステップ６０２で取得したアドレスをアドレス履歴テーブル４０ｃに登録する（ステップ６０５）。なお、アドレス履歴テーブル４０ｃから消去するアドレスは、最も古いアドレス（最先に登録されたアドレス）、フラグ・データの更新のない期間が最も長いアドレス、登録されてから一定期間が経過したフラグ・データの更新回数が一定以下であるアドレス等、予め定められた条件に従って特定すれば良い。
【００３８】
一方、ステップ６０２で取得したアドレスがアドレス履歴テーブル４０cに登録されている場合、マクロ登録判断部４０は、そのアドレスのフラグ・データの値を１加算する（ステップ６０７）。そして、更新後のフラグ・データの値が予め設定された閾値に達したか否かを判断する（ステップ６０８）。ここで、閾値の値は、システムの仕様等に応じて適当に設定される。
【００３９】
フラグ・データが閾値に達していない場合は、マクロ登録判断部４０による処理が終了し、命令キャッシュ２０における次のキャッシュ・ヒットを待つ。一方、フラグ・データが閾値に達した場合、マクロ登録判断部４０は、そのアドレスをマクロ３１として登録するように、マクロ・キャッシュ部３０に指示する（ステップ６０９）。
【００４０】
マクロ・キャッシュ部３０は、マクロ登録判断部４０からの指示を受け付けると、マクロ３１の登録処理を行う。すなわち、各マクロ３１において、図４に示した命令判断部３２による処理が行われる。そして、処理対象となったアドレスに対応する命令列が、既にマクロ３１として登録されている場合、そのマクロ３１にアドレスが追加登録される。一方、処理対象となったアドレスに対応する命令列がマクロ３１として登録されていない場合は、その命令列に関するマクロ３１が新たに作成される。
【００４１】
＜キャッシュ・システムの動作＞
次に、上記のように構成されたキャッシュ・システムを備えたＣＰＵ１００における、命令フェッチ・ユニット１０による命令読み込み時の動作について説明する。
図７は、命令読み込み時のＣＰＵ１００の動作を示すフローチャートである。
命令フェッチ・ユニット１０は、実行しようとする命令を読み込む場合、その命令のメイン・メモリ上におけるアドレスを指定する。このアドレスの情報は、命令フェッチ・ユニット１０から命令キャッシュ２０、マクロ・キャッシュ部３０およびマクロ登録判断部４０に供給される。これにより、命令キャッシュ２０、マクロ・キャッシュ部３０およびマクロ登録判断部４０は、読み込み対象の命令を特定するアドレスを取得する（ステップ７０１）。
【００４２】
命令キャッシュ２０およびマクロ・キャッシュ部３０は、取得したアドレスに基づき、命令フェッチ・ユニット１０が取得しようとする命令を保持（キャッシュ）しているか否かを判断する（ステップ７０２）。ここで、取得したアドレスの命令をマクロ・キャッシュ部３０が保持していた場合、その命令を命令キャッシュ２０が保持しているか否かに関わらず、マクロ・キャッシュ部３０から命令フェッチ・ユニット１０へ命令が読み込まれる（ステップ７０３、７０４）。これは、読み込み対象選択部５０の選択による。
【００４３】
また、取得したアドレスの命令をマクロ・キャッシュ部３０が保持しておらず、命令キャッシュ２０が保持していた場合、命令キャッシュ２０から命令フェッチ・ユニット１０へ命令が読み込まれる（ステップ７０３、７０５、７０６）。このとき、マクロ登録判断部４０が、この命令をマクロ・キャッシュ部３０に登録するか否かを判断する（図６を参照）。そして、マクロ・キャッシュ部３０への登録条件（例えば、図６のステップ６０８に示した読み込み頻度）を満足するならば、マクロ・キャッシュ部３０への登録が行われる（ステップ７０７、７０８）。ここで、登録対象の命令が、異なるアドレスに関連付けられて既にマクロ・キャッシュ部３０に登録されている命令であれば、その命令を登録したマクロ３１に、ステップ７０１で取得したアドレスが追加登録される（図４を参照）。一方、登録対象の命令がマクロ・キャッシュ部３０に未登録であるならば、その命令のマクロ３１が新たに作成されて、ステップ７０１で取得したアドレスが登録される。
【００４４】
命令フェッチ・ユニット１０が読み込もうとする命令が、マクロ・キャッシュ部３０にも命令キャッシュ２０にも保持されていない場合、命令フェッチ・ユニット１０は、メイン・メモリにアクセスして、指定したアドレスの命令を読み込む（ステップ７０３、７０５、７０９）。この命令は、命令キャッシュ２０に保持（キャッシュ）され（ステップ７１０）、次回の命令フェッチ・ユニット１０による読み込みの際は、命令キャッシュ２０から読み込まれる（ステップ７０５でＹｅｓとなる）。
【００４５】
以上説明したように、本実施形態は、命令キャッシュ２０に保持された命令のうち、所定の条件を満足する命令について、命令キャッシュ２０とは別に用意されたキャッシュ手段であるマクロ・キャッシュ部３０に登録して保持する。そして、マクロ・キャッシュ部３０は、１つの命令と複数のアドレスとを関連付け可能なマクロ３１により、メイン・メモリ上の異なるアドレスに格納された同一の命令を１つのマクロ３１で管理する。一方、命令キャッシュ２０では、従来と同様に、同一の命令であってもアドレスが異なれば個別に保持される。このため、メイン・メモリにおいて複数のアドレスに格納された同一の命令列が本実施形態のキャッシュ・システムにより保持される場合、マクロ・キャッシュ部３０に登録されると、命令キャッシュ２０に保持されるよりも冗長性が抑制される。
【００４６】
例えば、３２ＫＢ（ケーバイト）の命令キャッシュ２０を実装し、命令キャッシュ２０に保持される命令の冗長率（保持されている命令のうち、同一の命令が異なるアドレスで保持されている割合）が１０％である場合を想定する。この冗長率１０％は、非特許文献１、２に基づいて仮定した値である。本実施形態のマクロ・キャッシュ部３０を設けない場合、命令キャッシュ２０の実効キャッシュ・サイズは、概算で２８．８ＫＢ（＝３２ＫＢ×０．９）である。一方、本実施形態のマクロ・キャッシュ部３０を設けた場合、所定の条件を満たす命令列は、マクロ・キャッシュ部３０に登録されて命令キャッシュ２０から除かれる。そして、複数の相異なるアドレスに格納された重複する命令列は、マクロ・キャッシュ部３０においては１つのマクロ３１に登録される。そのため、本実施形態は、マクロ・キャッシュ部３０を設けない場合と比較して、命令キャッシュ２０の実効キャッシュ・サイズを、本来の記憶容量である３２ＫＢにより近づけることができ、キャッシュ効率を向上させることができる。
【００４７】
また、本実施形態は、命令キャッシュ２０に保持された命令の読み込み（キャッシュ・ヒット）頻度に基づいてマクロ・キャッシュ部３０に登録する命令列を決定し、動的にマクロ３１を作成する。このため、一度メイン・メモリから読み込まれた命令を直ちに保持する命令キャッシュ２０や従来のキャッシュ・システムと比較して、再利用率の高い命令列をマクロ３１として登録することができ、キャッシュ効率をさらに向上させることができる。
【００４８】
また、本実施形態のマクロ・キャッシュ部３０は、命令キャッシュ２０とは異なる仕組みにより命令列を保持するため、通常のキャッシュ・メモリとして使用されるような連想メモリ（ＣＡＭ）を使ったタグ方式ではなく、一般的なＳＲＡＭを用いて実現することができる。そのため、単純にキャッシュ・メモリの記憶容量を増やす場合と比較して、コスト（費用）の増加を抑制することができる。
【００４９】
以上、本実施形態について説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、種々の変更または改良を加えたものも、本発明の技術的範囲に含まれることは、特許請求の範囲の記載から明らかである。
例えば、上記実施形態では、マクロ・キャッシュ部３０に命令列を登録した場合に、直ちに命令キャッシュ２０から対応する命令列を消去することとしたが、直ちに消去するのではなく、マクロ・キャッシュ部３０に登録した後の所定のタイミングで消去するようにしても構わない。
【符号の説明】
【００５０】
１０…命令フェッチ・ユニット、２０…命令キャッシュ、３０…マクロ・キャッシュ部、３１…マクロ、３１ａ…マクロ保持手段、３２…命令判断部、４０…マクロ登録判断部、５０…読み込み対象選択部
【技術分野】
【０００１】
本発明は、処理装置（プロセッサ）およびそのキャッシュ・システムに関し、特に命令を保持（キャッシュ）するキャッシュ・システムに関する。
【背景技術】
【０００２】
コンピュータにおいて、処理速度を向上させる手段として、キャッシュ・メモリを設けることが一般的に行われている。キャッシュ・メモリは、アクセス速度の高速なメモリであり、メイン・メモリから読み出したデータをキャッシュ・メモリに一時的に保持（キャッシュ）する。処理装置（プロセッサ）は、取得しようとするデータがキャッシュ・メモリに存在している場合には、アクセス速度の遅いメイン・メモリにアクセスすることなくキャッシュ・メモリからデータを取得する。
【０００３】
処理装置が使用するキャッシュ・メモリとしては、通常、プログラムの命令を保持する命令キャッシュ（インストラクション・キャッシュ）と、処理対象のデータを保持するデータ・キャッシュとが用意される。キャッシュ・メモリは、キャッシュ・ラインと呼ばれる単位でデータを保持する。命令キャッシュの場合、保持されるデータは命令列（Instructions）である。
【０００４】
ところで、プロセッサの実行コードは、キャッシュ・ラインのサイズ程度の短い命令列で見ると、同じコード列になる場合が多い。例えば、タスク切り替え時のレジスタの退避命令や、インライン展開されたコード等は、同じコード列になり易い。このため、命令キャッシュは、同じ命令列が多重に保持され、キャッシュ内容が冗長になる場合が多い（例えば、非特許文献１、２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Marios Kleanthous他、「Dynamically Detecting Cache-Content-Duplication in Instruction Caches」、Department of Computer Science University of Cyprus、February 2007、TR-07-03、[URL]http://www.cs.ucy.ac.cy/carch/xi/trs/tr-07-03.pdf
【非特許文献２】Marios Kleanthous他、「The Duplication of Content in Instruction Caches and its Performance Implications」、Department of Computer Science University of Cyprus、January 2005、CS-TR-01-2005、[URL] http://www.cs.ucy.ac.cy/carch/xi/trs/Cache_Content_Duplication-tr.pdf
【発明の概要】
【発明が解決しようとする課題】
【０００６】
命令キャッシュは、キャッシュ・ラインにおいて同じ命令列が多重に保持（キャッシュ）されることにより、保持した内容が冗長になる場合が多い。
そこで、本発明は、キャッシュ・メモリに命令を保持（キャッシュ）する場合における保持内容の冗長さを減少させ、効率の良いキャッシュ・システムを実現することを目的とする。
【課題を解決するための手段】
【０００７】
上記の目的を達成するため、本発明は、次のような装置として実現される。この装置は、プログラムの命令を読み込んで実行する装置であって、メイン・メモリ上のアドレスにより指定した命令を読み込む命令フェッチ・ユニットと、この命令フェッチ・ユニットにより読み込まれた命令を保持する第１のキャッシュ・メモリと、命令とこの命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、命令フェッチ・ユニットから取得したアドレスに基づき、アドレスに関連付けられた命令を特定する第２のキャッシュ・メモリと、第１のキャッシュ・メモリに保持された命令のうち、命令フェッチ・ユニットにより読み込まれた回数が予め定められた閾値を超えた命令を、第２のキャッシュ・メモリに保持させる、判断部と、命令フェッチ・ユニットが読み込もうとする命令が第１のキャッシュ・メモリおよび第２のキャッシュ・メモリのいずれにも保持されている場合に、命令の読み込み元として第２のキャッシュ・メモリを選択する選択部と、を備える。
そして、第２のキャッシュ・メモリは、判断部により保持するように指示された命令と同一の命令を既に保持している場合は、その命令を指定するアドレスを、既に保持しているその命令と関連付けて保持し、判断部により保持するように指示された命令と同一の命令を保持していない場合は、その命令とその命令を指定するアドレスとを関連付けて保持する。
また、第２のキャッシュ・メモリに保持された命令と同一のアドレスにおける命令は、第１のキャッシュ・メモリから消去される。
【０００８】
さらに好適には、第２のキャッシュ・メモリは、ＳＲＡＭ（Static Random Access Memory）にて構成される。
【０００９】
また、上記の目的を達成する他の本発明は、次のようなシステムとして実現される。このシステムは、プログラムの命令をキャッシュするシステムにおいて、アドレスを指定されてメイン・メモリから読み込まれた命令をキャッシュする第１のキャッシュ手段と、この第１のキャッシュ手段にキャッシュされた命令のうち、所定の条件を満足する命令をキャッシュする第２のキャッシュ手段と、読み込まれる対象の命令が第１のキャッシュ手段および第２のキャッシュ手段のいずれにもキャッシュされている場合に、この命令の読み込み元を選択する選択手段と、を備える。そして、第２のキャッシュ手段は、命令とこの命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、読み込み手段から取得したアドレスに基づき、アドレスに関連付けられた命令を特定する。
【００１０】
より詳細には、第２のキャッシュ手段は、キャッシュしようとする命令と同一の命令を既に保持している場合は、この命令を指定するアドレスを、既に保持している命令と関連付けて保持し、キャッシュしようとする命令と同一の命令を保持していない場合は、この命令とこの命令を指定するアドレスとを関連付けて保持する。
【００１１】
また、より好適には、第２のキャッシュ手段は、第１のキャッシュ手段にキャッシュされた命令のうち、読み込み要求に対してヒットした回数が予め定められた閾値を超えた命令をキャッシュする。
さらに好適には、第２のキャッシュ手段にキャッシュされた命令と同一のアドレスにおけるこの命令は、第１のキャッシュ手段から消去される。
そして、さらに好適には、選択手段は、読み込まれる対象の命令が第１のキャッシュ手段および第２のキャッシュ手段のいずれにもキャッシュされている場合に、第２のキャッシュ手段から読み込むことを選択する。
【発明の効果】
【００１２】
本発明によれば、キャッシュ・メモリに命令を保持（キャッシュ）する場合における保持内容の冗長さを減少させ、効率の良いキャッシュ・システムを実現することができる。
【図面の簡単な説明】
【００１３】
【図１】本実施形態によるキャッシュ・システムの構成例を示す図である。
【図２】本実施形態のマクロ・キャッシュ部の構成例を示す図である。
【図３】本実施形態の命令判断部を実現する論理回路の構成例を示す図である。
【図４】本実施形態の命令判断部の動作例を示すフローチャートである。
【図５】本実施形態のマクロ登録判断部を実現する論理回路の構成例を示す図である。
【図６】本実施形態のマクロ登録判断部の動作を示すフローチャートである。
【図７】本実施形態における命令読み込み時のＣＰＵの動作を示すフローチャートである。
【発明を実施するための形態】
【００１４】
以下、添付図面を参照して、本発明の実施形態について詳細に説明する。
プロセッサの実行コードは、ＪＩＴ（Just In Time）のような特殊な例外を除き、メイン・メモリ上での書き換えが発生せず、命令を格納するためにアロケートされたアドレスが変わることもない。すなわち、メイン・メモリ上のアドレスに対して命令が一意に決まる。これに基づき、本実施形態は、アドレスに関連づけされたマクロとして命令列を特定するキャッシュ・システムを実現する。なお、本実施形態では、従来の命令キャッシュ（キャッシュ・メモリ）を用いたキャッシュ・システムに対する付加的な構成として、上記のマクロによるキャッシュ・システムを構成する場合を例として説明する。
【００１５】
＜システム構成＞
図１は、本実施形態によるキャッシュ・システムの構成例を示す図である。
図１に示す構成例において、処理装置（プロセッサ）であるＣＰＵ（Central Processing Unit）１００は、チップ上のバス（オン・チップ・バス）２００に接続されている。図示のように、本実施形態のＣＰＵ１００は、命令フェッチ・ユニット１０と、第１のキャッシュ手段としての命令キャッシュ２０とを備える。また、ＣＰＵ１００は、第２のキャッシュ手段として、マクロ・キャッシュ部３０と、マクロ登録判断部４０とを備え、さらに読み込み対象選択部５０とを備える。なお、図１には、ＣＰＵ１００の構成のうち、本実施形態に関わる構成のみを記載している。
【００１６】
命令フェッチ・ユニット１０は、ＣＰＵ１００がプログラムの処理を実行するために命令を読み込む（フェッチする）。命令の取得は、取得しようとする命令のメイン・メモリ（図示せず）上のアドレスを指定することによって行われる。命令フェッチ・ユニット１０は、取得しようとする命令が、命令キャッシュ２０に保持（キャッシュ）されているか、またはマクロ・キャッシュ部３０にマクロ３１（後述）として登録されている場合（キャッシュ・ヒットに相当）には、これらから命令を取得する。一方、取得しようとする命令が命令キャッシュ２０にもマクロ・キャッシュ部３０にも存在しない場合（キャッシュ・ミスに相当）には、メイン・メモリにアクセスして命令を取得する。
【００１７】
命令キャッシュ２０は、一般的なキャッシュ・メモリにおける命令キャッシュである。すなわち、ＣＰＵ１００が処理を実行するためにメイン・メモリから命令（命令列）を読み込むと、読み込まれた命令（命令列）は命令キャッシュ２０に保持され、次にＣＰＵ１００が同様の処理を実行する際に当該命令が命令キャッシュ２０から読み込まれる。命令キャッシュ２０としては、例えば連想メモリ（Content Addressable Memory；ＣＡＭ）をタグとして使ったＳＲＡＭが用いられる。
【００１８】
マクロ・キャッシュ部３０は、命令フェッチ・ユニット１０がフェッチする命令列を、メイン・メモリ上の当該命令列のアドレスと関連付けたマクロ３１として保持（キャッシュ）する。このマクロ３１は、キャッシュ対象の命令列ごとに作成される。マクロ・キャッシュ部３０には、命令キャッシュ２０に保持された命令のうち、マクロ登録判断部４０により登録対象とされた命令列が保持される。マクロ・キャッシュ部３０およびマクロ３１の詳細については後述する。
【００１９】
マクロ登録判断部４０は、命令キャッシュ２０に保持されている命令列をマクロ・キャッシュ部３０に登録するか否かを判断する。本実施形態において、マクロ登録判断部４０は、命令キャッシュ２０における命令列ごとのキャッシュ・ヒットの頻度（命令フェッチ・ユニット１０により読み込まれる頻度）に基づいて、命令列をマクロ・キャッシュ部３０に登録するか否かを判断する。マクロ登録判断部４０の機能および動作の詳細については後述する。
【００２０】
読み込み対象選択部５０は、同一の命令列が命令キャッシュ２０とマクロ・キャッシュ部３０の両方に保持されている場合に、どちらから読み込むかを選択する。本実施形態では、命令フェッチ・ユニット１０が読み込もうとする命令列がマクロ・キャッシュ部３０に保持されている場合は、マクロ・キャッシュ部３０から命令列を読み込む。具体的には、例えば、命令フェッチ・ユニット１０が読み込もうとする命令列をマクロ・キャッシュ部３０が保持している場合に、マクロ・キャッシュ部３０が、マクロ・キャッシュ部３０からの読み込みを選択するように読み込み対象選択部５０へ指示する。
【００２１】
＜マクロ・キャッシュ部３０の構成＞
図２は、マクロ・キャッシュ部３０の構成例を示す図である。
図２に示すように、マクロ・キャッシュ部３０は、複数（図示の例ではｎ個）のマクロ３１を含む。個々のマクロ３１は、１つの命令列とこの命令列に関連付けられたアドレスとを保持するマクロ保持手段３１ａと、マクロ３１にアドレスを登録するための命令判断部３２とを備える。命令判断部３２の機能および動作の詳細については後述する。
【００２２】
マクロ保持手段３１ａには、上記のように、命令列とこの命令列に関連付けられたアドレスとが保持される。このマクロ保持手段３１ａは、一つの命令列に対して、複数のアドレスを関連付けて保持することができるように構成される。命令列およびアドレスを保持する記憶手段（メモリ）としては、一般的なキャッシュ・メモリに用いられる連想メモリではなく、例えばＳＲＡＭ（Static Random Access Memory）が用いられる。
【００２３】
また上記のように、マクロ３１には、命令キャッシュ２０に保持された命令列が、所定の条件を満足する場合に登録される。そのため、マクロ保持手段３１ａに保持される命令列のサイズは、通常は、命令キャッシュ２０のキャッシュ・ラインのサイズと等しくなる。ただし、マクロ保持手段３１ａに登録できる命令列のサイズは、このサイズに限定されない。システムの仕様等に応じて、他のサイズで命令列を保持するようにしても良い。マクロ・キャッシュ部３０に設けられるマクロ３１の数や、マクロ３１における命令列に関連付けが可能なアドレスの数は、マクロ保持手段３１ａを実現する記憶手段の記憶容量やシステムの仕様等に基づいて決定される。
【００２４】
図３は、命令判断部３２を実現する論理回路の構成例を示す図である。
図３に示すように、命令判断部３２は、比較対象の命令を選択するセレクタ３２ａと、選択された命令を比較するコンパレータ３２ｂと、一致した命令の数を計数するカウンタ３２ｃとを備える。
【００２５】
セレクタ３２ａは、マクロ３１のマクロ保持手段３１ａに保持されている命令列を構成する個々の命令（命令フェッチ・ユニット１０がフェッチする命令単位）を、コンパレータ３２ｂによる比較の対象とするために、先頭から順次選択する。
【００２６】
コンパレータ３２ｂは、命令フェッチ・ユニット１０により命令キャッシュ２０から読み出された命令列を取得する。そして、取得した命令列とセレクタ３２ａにより選択された命令とを比較する。
【００２７】
カウンタ３２ｃは、コンパレータ３２ｂによる比較で一致した命令の数を計数し、その計数を元にセレクタ３２ａにどの命令と比較するかを指示する。カウンタ３２ｃの初期値は「１」であり、マクロ保持手段３１ａに登録されている命令列を構成する命令の数「ｍ」まで計数する。例えば、命令コードが１バイトで、キャッシュ・ラインのサイズが３２バイトであれば、ｍ＝３２である。
【００２８】
図４は、命令判断部３２の動作例を示すフローチャートである。
図４を参照すると、命令判断部３２は、まず、命令フェッチ・ユニット１０が取得しようとする命令が命令キャッシュ２０においてヒットした場合に、命令キャッシュ２０から読み出された命令を取得する（ステップ４０１、４０２）。そして、命令判断部３２は、セレクタ３２ａにより、マクロ保持手段３１ａに保持されている命令列のうち先頭の命令を比較対象として選択する（ステップ４０３）。次に、命令判断部３２は、コンパレータ３２ｂにより、ステップ４０２で取得した命令とステップ４０３で選択した命令とを比較する（ステップ４０４）。比較した命令が一致しない場合は、処理を終了する（ステップ４０５）。
【００２９】
ステップ４０４で比較した命令が一致した場合、命令判断部３２は、カウンタ３２ｃの値を調べる（ステップ４０５、４０６）。カウンタ３２ｃの値が「ｍ」でなければ、命令判断部３２は、カウンタ３２ｃの値を１加算する（ステップ４０７、４０８）。そして、命令判断部３２は、セレクタ３２ａにより、マクロ保持手段３１ａに保持されている命令列を構成する命令のうち次の命令を選択し（ステップ４０９）、命令キャッシュ２０から次の命令が読み出されるのを待つ（ステップ４１０）。命令キャッシュ２０から次の命令が読み出されたならば、命令判断部３２は、ステップ４０４以降の処理を繰り返す。
【００３０】
ステップ４０６、４０７で、カウンタ３２ｃの値が「ｍ」である場合、命令キャッシュ２０から読み出されたｍ個の命令の組（命令列）が、マクロ保持手段３１ａに保持されている命令列と一致したことを意味する。そこで、命令判断部３２は、一致した命令列を構成する命令のうち、最初に命令キャッシュ２０においてヒットした命令のアドレスを、マクロ保持手段３１ａに登録する（ステップ４０７、４１１）。そして、マクロ保持手段３１ａに登録した命令列を命令キャッシュ２０から消去する（ステップ４１１）。
【００３１】
＜マクロ登録判断部４０の構成＞
図５は、マクロ登録判断部４０を実現する論理回路の構成例を示す図である。
図５に示すように、マクロ登録判断部４０は、判断対象となるアドレスを取り込むためのセレクタ４０ａと、取り込んだアドレスの出現頻度を調べるためのコンパレータ４０ｂおよびアドレス履歴テーブル４０ｃとを備える。
【００３２】
セレクタ４０ａは、命令フェッチ・ユニット１０が取得しようとする命令が命令キャッシュ２０においてヒットしたことを条件として、命令フェッチ・ユニット１０により指定されたアドレス（取得しようとする命令のアドレス）を取り込む。
【００３３】
コンパレータ４０ｂは、セレクタ４０ａにより取り込まれたアドレスと、アドレス履歴テーブル４０ｃに登録されているアドレスとを比較する。そして、セレクタ４０ａにより取り込まれたアドレスがアドレス履歴テーブル４０ｃに登録されていなければ、そのアドレスを新規にアドレス履歴テーブル４０ｃに登録する。一方、セレクタ４０ａにより取り込まれたアドレスがアドレス履歴テーブル４０ｃに登録されている場合、コンパレータ４０ｂは、そのアドレスが命令フェッチ・ユニット１０による取得対象となった回数を示すフラグ・データ（図５の「Ｆ」）を更新する。
【００３４】
アドレス履歴テーブル４０ｃは、以前に命令フェッチ・ユニット１０が取得しようとした命令のアドレスと、そのアドレスが命令フェッチ・ユニット１０による取得対象となった回数を示すフラグ・データとを含むテーブルである。コンパレータ４０ｂによる比較の結果、セレクタ４０ａにより取り込まれたアドレスがアドレス履歴テーブル４０ｃに登録されていなければ、そのアドレスが新規に登録される。一方、コンパレータ４０ｂによる比較の結果、セレクタ４０ａにより取り込まれたアドレスが既にアドレス履歴テーブル４０ｃに登録されていれば、そのアドレスのフラグ・データの値が１加算される（更新）。このアドレス履歴テーブル４０ｃは、例えば、マクロ３１のマクロ保持手段３１ａと共通のＳＲＡＭに記憶される。アドレス履歴テーブル４０ｃに登録可能なアドレスおよびフラグ・データの数（エントリ数）は、アドレス履歴テーブル４０ｃを記憶する記憶手段の記憶容量やシステムの仕様等に基づいて決定される。
【００３５】
図６は、マクロ登録判断部４０の動作を示すフローチャートである。
図６を参照すると、マクロ登録判断部４０は、まず、命令フェッチ・ユニット１０が取得しようとする命令が命令キャッシュ２０においてヒットした場合に、セレクタ４０ａにより、命令フェッチ・ユニット１０が指定したアドレス（取得しようとする命令のアドレス）を取り込む（ステップ６０１、６０２）。
【００３６】
次に、マクロ登録判断部４０は、コンパレータ４０ｂにより、ステップ６０２で取得したアドレスがアドレス履歴テーブル４０cに登録されているか否かを判断する（ステップ６０３）。ステップ６０２で取得したアドレスがアドレス履歴テーブル４０cに登録されていない場合、次にマクロ登録判断部４０は、アドレス履歴テーブル４０ｃに登録可能な数のアドレスが既に登録されている（Table full）か否かを判断する（ステップ６０４）。そして、アドレス履歴テーブル４０ｃに空きがあるならば、ステップ６０２で取得したアドレスをアドレス履歴テーブル４０ｃに登録する（ステップ６０５）。
【００３７】
また、アドレス履歴テーブル４０ｃに空きがない場合、マクロ登録判断部４０は、既にアドレス履歴テーブル４０ｃに登録されているアドレスのうちで、特定のアドレスを消去してテーブルの空きエントリを確保する（ステップ６０６）。そして、ステップ６０２で取得したアドレスをアドレス履歴テーブル４０ｃに登録する（ステップ６０５）。なお、アドレス履歴テーブル４０ｃから消去するアドレスは、最も古いアドレス（最先に登録されたアドレス）、フラグ・データの更新のない期間が最も長いアドレス、登録されてから一定期間が経過したフラグ・データの更新回数が一定以下であるアドレス等、予め定められた条件に従って特定すれば良い。
【００３８】
一方、ステップ６０２で取得したアドレスがアドレス履歴テーブル４０cに登録されている場合、マクロ登録判断部４０は、そのアドレスのフラグ・データの値を１加算する（ステップ６０７）。そして、更新後のフラグ・データの値が予め設定された閾値に達したか否かを判断する（ステップ６０８）。ここで、閾値の値は、システムの仕様等に応じて適当に設定される。
【００３９】
フラグ・データが閾値に達していない場合は、マクロ登録判断部４０による処理が終了し、命令キャッシュ２０における次のキャッシュ・ヒットを待つ。一方、フラグ・データが閾値に達した場合、マクロ登録判断部４０は、そのアドレスをマクロ３１として登録するように、マクロ・キャッシュ部３０に指示する（ステップ６０９）。
【００４０】
マクロ・キャッシュ部３０は、マクロ登録判断部４０からの指示を受け付けると、マクロ３１の登録処理を行う。すなわち、各マクロ３１において、図４に示した命令判断部３２による処理が行われる。そして、処理対象となったアドレスに対応する命令列が、既にマクロ３１として登録されている場合、そのマクロ３１にアドレスが追加登録される。一方、処理対象となったアドレスに対応する命令列がマクロ３１として登録されていない場合は、その命令列に関するマクロ３１が新たに作成される。
【００４１】
＜キャッシュ・システムの動作＞
次に、上記のように構成されたキャッシュ・システムを備えたＣＰＵ１００における、命令フェッチ・ユニット１０による命令読み込み時の動作について説明する。
図７は、命令読み込み時のＣＰＵ１００の動作を示すフローチャートである。
命令フェッチ・ユニット１０は、実行しようとする命令を読み込む場合、その命令のメイン・メモリ上におけるアドレスを指定する。このアドレスの情報は、命令フェッチ・ユニット１０から命令キャッシュ２０、マクロ・キャッシュ部３０およびマクロ登録判断部４０に供給される。これにより、命令キャッシュ２０、マクロ・キャッシュ部３０およびマクロ登録判断部４０は、読み込み対象の命令を特定するアドレスを取得する（ステップ７０１）。
【００４２】
命令キャッシュ２０およびマクロ・キャッシュ部３０は、取得したアドレスに基づき、命令フェッチ・ユニット１０が取得しようとする命令を保持（キャッシュ）しているか否かを判断する（ステップ７０２）。ここで、取得したアドレスの命令をマクロ・キャッシュ部３０が保持していた場合、その命令を命令キャッシュ２０が保持しているか否かに関わらず、マクロ・キャッシュ部３０から命令フェッチ・ユニット１０へ命令が読み込まれる（ステップ７０３、７０４）。これは、読み込み対象選択部５０の選択による。
【００４３】
また、取得したアドレスの命令をマクロ・キャッシュ部３０が保持しておらず、命令キャッシュ２０が保持していた場合、命令キャッシュ２０から命令フェッチ・ユニット１０へ命令が読み込まれる（ステップ７０３、７０５、７０６）。このとき、マクロ登録判断部４０が、この命令をマクロ・キャッシュ部３０に登録するか否かを判断する（図６を参照）。そして、マクロ・キャッシュ部３０への登録条件（例えば、図６のステップ６０８に示した読み込み頻度）を満足するならば、マクロ・キャッシュ部３０への登録が行われる（ステップ７０７、７０８）。ここで、登録対象の命令が、異なるアドレスに関連付けられて既にマクロ・キャッシュ部３０に登録されている命令であれば、その命令を登録したマクロ３１に、ステップ７０１で取得したアドレスが追加登録される（図４を参照）。一方、登録対象の命令がマクロ・キャッシュ部３０に未登録であるならば、その命令のマクロ３１が新たに作成されて、ステップ７０１で取得したアドレスが登録される。
【００４４】
命令フェッチ・ユニット１０が読み込もうとする命令が、マクロ・キャッシュ部３０にも命令キャッシュ２０にも保持されていない場合、命令フェッチ・ユニット１０は、メイン・メモリにアクセスして、指定したアドレスの命令を読み込む（ステップ７０３、７０５、７０９）。この命令は、命令キャッシュ２０に保持（キャッシュ）され（ステップ７１０）、次回の命令フェッチ・ユニット１０による読み込みの際は、命令キャッシュ２０から読み込まれる（ステップ７０５でＹｅｓとなる）。
【００４５】
以上説明したように、本実施形態は、命令キャッシュ２０に保持された命令のうち、所定の条件を満足する命令について、命令キャッシュ２０とは別に用意されたキャッシュ手段であるマクロ・キャッシュ部３０に登録して保持する。そして、マクロ・キャッシュ部３０は、１つの命令と複数のアドレスとを関連付け可能なマクロ３１により、メイン・メモリ上の異なるアドレスに格納された同一の命令を１つのマクロ３１で管理する。一方、命令キャッシュ２０では、従来と同様に、同一の命令であってもアドレスが異なれば個別に保持される。このため、メイン・メモリにおいて複数のアドレスに格納された同一の命令列が本実施形態のキャッシュ・システムにより保持される場合、マクロ・キャッシュ部３０に登録されると、命令キャッシュ２０に保持されるよりも冗長性が抑制される。
【００４６】
例えば、３２ＫＢ（ケーバイト）の命令キャッシュ２０を実装し、命令キャッシュ２０に保持される命令の冗長率（保持されている命令のうち、同一の命令が異なるアドレスで保持されている割合）が１０％である場合を想定する。この冗長率１０％は、非特許文献１、２に基づいて仮定した値である。本実施形態のマクロ・キャッシュ部３０を設けない場合、命令キャッシュ２０の実効キャッシュ・サイズは、概算で２８．８ＫＢ（＝３２ＫＢ×０．９）である。一方、本実施形態のマクロ・キャッシュ部３０を設けた場合、所定の条件を満たす命令列は、マクロ・キャッシュ部３０に登録されて命令キャッシュ２０から除かれる。そして、複数の相異なるアドレスに格納された重複する命令列は、マクロ・キャッシュ部３０においては１つのマクロ３１に登録される。そのため、本実施形態は、マクロ・キャッシュ部３０を設けない場合と比較して、命令キャッシュ２０の実効キャッシュ・サイズを、本来の記憶容量である３２ＫＢにより近づけることができ、キャッシュ効率を向上させることができる。
【００４７】
また、本実施形態は、命令キャッシュ２０に保持された命令の読み込み（キャッシュ・ヒット）頻度に基づいてマクロ・キャッシュ部３０に登録する命令列を決定し、動的にマクロ３１を作成する。このため、一度メイン・メモリから読み込まれた命令を直ちに保持する命令キャッシュ２０や従来のキャッシュ・システムと比較して、再利用率の高い命令列をマクロ３１として登録することができ、キャッシュ効率をさらに向上させることができる。
【００４８】
また、本実施形態のマクロ・キャッシュ部３０は、命令キャッシュ２０とは異なる仕組みにより命令列を保持するため、通常のキャッシュ・メモリとして使用されるような連想メモリ（ＣＡＭ）を使ったタグ方式ではなく、一般的なＳＲＡＭを用いて実現することができる。そのため、単純にキャッシュ・メモリの記憶容量を増やす場合と比較して、コスト（費用）の増加を抑制することができる。
【００４９】
以上、本実施形態について説明したが、本発明の技術的範囲は上記実施形態に記載の範囲には限定されない。上記実施形態に、種々の変更または改良を加えたものも、本発明の技術的範囲に含まれることは、特許請求の範囲の記載から明らかである。
例えば、上記実施形態では、マクロ・キャッシュ部３０に命令列を登録した場合に、直ちに命令キャッシュ２０から対応する命令列を消去することとしたが、直ちに消去するのではなく、マクロ・キャッシュ部３０に登録した後の所定のタイミングで消去するようにしても構わない。
【符号の説明】
【００５０】
１０…命令フェッチ・ユニット、２０…命令キャッシュ、３０…マクロ・キャッシュ部、３１…マクロ、３１ａ…マクロ保持手段、３２…命令判断部、４０…マクロ登録判断部、５０…読み込み対象選択部
【特許請求の範囲】
【請求項１】
プログラムの命令を読み込んで実行する装置において、
メイン・メモリ上のアドレスにより指定した命令を読み込む命令フェッチ・ユニットと、
前記命令フェッチ・ユニットにより読み込まれた命令を保持する第１のキャッシュ・メモリと、
命令と当該命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、前記命令フェッチ・ユニットから取得したアドレスに基づき、当該アドレスに関連付けられた命令を特定する第２のキャッシュ・メモリと、
前記第１のキャッシュ・メモリに保持された命令のうち、所定の条件を満足する命令を前記第２のキャッシュ・メモリに保持させる、判断部と、
前記命令フェッチ・ユニットが読み込もうとする命令が前記第１のキャッシュ・メモリおよび前記第２のキャッシュ・メモリのいずれにも保持されている場合に、当該命令の読み込み元を選択する選択部と、
を備える、装置。
【請求項２】
前記第２のキャッシュ・メモリは、
前記判断部により保持するように指示された命令と同一の命令を既に保持している場合は、当該命令を指定する前記アドレスを、既に保持している当該命令と関連付けて保持し、
前記判断部により保持するように指示された命令と同一の命令を保持していない場合は、当該命令と当該命令を指定する前記アドレスとを関連付けて保持する、請求項１に記載の装置。
【請求項３】
前記判断部は、前記第１のキャッシュ・メモリに保持された命令のうち、前記命令フェッチ・ユニットにより読み込まれた回数が予め定められた閾値を超えた命令を、前記第２のキャッシュ・メモリに保持させる、請求項１または請求項２に記載の装置。
【請求項４】
前記第２のキャッシュ・メモリに保持された命令と同一のアドレスにおける当該命令は、前記第１のキャッシュ・メモリから消去される、請求項１乃至請求項３のいずれかに記載の装置。
【請求項５】
前記第２のキャッシュ・メモリは、ＳＲＡＭ（Static Random Access Memory）である、請求項１乃至請求項４のいずれかに記載の装置。
【請求項６】
前記選択部は、前記命令フェッチ・ユニットが読み込もうとする命令が前記第１のキャッシュ・メモリおよび前記第２のキャッシュ・メモリのいずれにも保持されている場合に、当該第２のキャッシュ・メモリから読み込むことを選択する、請求項１乃至請求項５のいずれかに記載の装置。
【請求項７】
プログラムの命令を読み込んで実行する装置において、
メイン・メモリ上のアドレスにより指定した命令を読み込む命令フェッチ・ユニットと、
前記命令フェッチ・ユニットにより読み込まれた命令を保持する第１のキャッシュ・メモリと、
命令と当該命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、前記命令フェッチ・ユニットから取得したアドレスに基づき、当該アドレスに関連付けられた命令を特定する第２のキャッシュ・メモリと、
前記第１のキャッシュ・メモリに保持された命令のうち、前記命令フェッチ・ユニットにより読み込まれた回数が予め定められた閾値を超えた命令を、前記第２のキャッシュ・メモリに保持させる、判断部と、
前記命令フェッチ・ユニットが読み込もうとする命令が前記第２のキャッシュ・メモリに保持されている場合に、当該命令の読み込み元として当該第２のキャッシュ・メモリを選択する選択部と、を備え、
前記第２のキャッシュ・メモリは、
前記判断部により保持するように指示された命令と同一の命令を既に保持している場合は、当該命令を指定する前記アドレスを、既に保持している当該命令と関連付けて保持し、
前記判断部により保持するように指示された命令と同一の命令を保持していない場合は、当該命令と当該命令を指定する前記アドレスとを関連付けて保持し、
前記第２のキャッシュ・メモリに保持された命令と同一のアドレスにおける当該命令は、前記第１のキャッシュ・メモリから消去される、装置。
【請求項８】
プログラムの命令をキャッシュするシステムにおいて、
メイン・メモリ上のアドレスを指定されて当該メイン・メモリから読み込まれた命令をキャッシュする第１のキャッシュ手段と、
前記第１のキャッシュ手段にキャッシュされた命令のうち、所定の条件を満足する命令をキャッシュする第２のキャッシュ手段と、
読み込まれる対象の命令が前記第１のキャッシュ手段および前記第２のキャッシュ手段のいずれにもキャッシュされている場合に、当該命令の読み込み元を選択する選択手段と、を備え、
前記第２のキャッシュ手段は、命令と当該命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、命令を読み込むために指定されたアドレスに基づき、当該アドレスに関連付けられた命令を特定する、システム。
【請求項９】
前記第２のキャッシュ手段は、
キャッシュしようとする命令と同一の命令を既に保持している場合は、当該命令を指定する前記アドレスを、既に保持している当該命令と関連付けて保持し、
キャッシュしようとする命令と同一の命令を保持していない場合は、当該命令と当該命令を指定する前記アドレスとを関連付けて保持する、請求項８に記載のシステム。
【請求項１０】
前記第２のキャッシュ手段は、前記第１のキャッシュ手段にキャッシュされた命令のうち、読み込み要求に対してヒットした回数が予め定められた閾値を超えた命令をキャッシュする、請求項８または請求項９に記載のシステム。
【請求項１１】
前記第２のキャッシュ手段にキャッシュされた命令と同一のアドレスにおける当該命令は、前記第１のキャッシュ手段から消去される、請求項８乃至請求項１０のいずれかに記載のシステム。
【請求項１２】
前記選択手段は、読み込まれる対象の命令が前記第１のキャッシュ手段および前記第２のキャッシュ手段のいずれにもキャッシュされている場合に、当該第２のキャッシュ手段から読み込むことを選択する、請求項８乃至請求項１１のいずれかに記載のシステム。
【請求項１】
プログラムの命令を読み込んで実行する装置において、
メイン・メモリ上のアドレスにより指定した命令を読み込む命令フェッチ・ユニットと、
前記命令フェッチ・ユニットにより読み込まれた命令を保持する第１のキャッシュ・メモリと、
命令と当該命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、前記命令フェッチ・ユニットから取得したアドレスに基づき、当該アドレスに関連付けられた命令を特定する第２のキャッシュ・メモリと、
前記第１のキャッシュ・メモリに保持された命令のうち、所定の条件を満足する命令を前記第２のキャッシュ・メモリに保持させる、判断部と、
前記命令フェッチ・ユニットが読み込もうとする命令が前記第１のキャッシュ・メモリおよび前記第２のキャッシュ・メモリのいずれにも保持されている場合に、当該命令の読み込み元を選択する選択部と、
を備える、装置。
【請求項２】
前記第２のキャッシュ・メモリは、
前記判断部により保持するように指示された命令と同一の命令を既に保持している場合は、当該命令を指定する前記アドレスを、既に保持している当該命令と関連付けて保持し、
前記判断部により保持するように指示された命令と同一の命令を保持していない場合は、当該命令と当該命令を指定する前記アドレスとを関連付けて保持する、請求項１に記載の装置。
【請求項３】
前記判断部は、前記第１のキャッシュ・メモリに保持された命令のうち、前記命令フェッチ・ユニットにより読み込まれた回数が予め定められた閾値を超えた命令を、前記第２のキャッシュ・メモリに保持させる、請求項１または請求項２に記載の装置。
【請求項４】
前記第２のキャッシュ・メモリに保持された命令と同一のアドレスにおける当該命令は、前記第１のキャッシュ・メモリから消去される、請求項１乃至請求項３のいずれかに記載の装置。
【請求項５】
前記第２のキャッシュ・メモリは、ＳＲＡＭ（Static Random Access Memory）である、請求項１乃至請求項４のいずれかに記載の装置。
【請求項６】
前記選択部は、前記命令フェッチ・ユニットが読み込もうとする命令が前記第１のキャッシュ・メモリおよび前記第２のキャッシュ・メモリのいずれにも保持されている場合に、当該第２のキャッシュ・メモリから読み込むことを選択する、請求項１乃至請求項５のいずれかに記載の装置。
【請求項７】
プログラムの命令を読み込んで実行する装置において、
メイン・メモリ上のアドレスにより指定した命令を読み込む命令フェッチ・ユニットと、
前記命令フェッチ・ユニットにより読み込まれた命令を保持する第１のキャッシュ・メモリと、
命令と当該命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、前記命令フェッチ・ユニットから取得したアドレスに基づき、当該アドレスに関連付けられた命令を特定する第２のキャッシュ・メモリと、
前記第１のキャッシュ・メモリに保持された命令のうち、前記命令フェッチ・ユニットにより読み込まれた回数が予め定められた閾値を超えた命令を、前記第２のキャッシュ・メモリに保持させる、判断部と、
前記命令フェッチ・ユニットが読み込もうとする命令が前記第２のキャッシュ・メモリに保持されている場合に、当該命令の読み込み元として当該第２のキャッシュ・メモリを選択する選択部と、を備え、
前記第２のキャッシュ・メモリは、
前記判断部により保持するように指示された命令と同一の命令を既に保持している場合は、当該命令を指定する前記アドレスを、既に保持している当該命令と関連付けて保持し、
前記判断部により保持するように指示された命令と同一の命令を保持していない場合は、当該命令と当該命令を指定する前記アドレスとを関連付けて保持し、
前記第２のキャッシュ・メモリに保持された命令と同一のアドレスにおける当該命令は、前記第１のキャッシュ・メモリから消去される、装置。
【請求項８】
プログラムの命令をキャッシュするシステムにおいて、
メイン・メモリ上のアドレスを指定されて当該メイン・メモリから読み込まれた命令をキャッシュする第１のキャッシュ手段と、
前記第１のキャッシュ手段にキャッシュされた命令のうち、所定の条件を満足する命令をキャッシュする第２のキャッシュ手段と、
読み込まれる対象の命令が前記第１のキャッシュ手段および前記第２のキャッシュ手段のいずれにもキャッシュされている場合に、当該命令の読み込み元を選択する選択手段と、を備え、
前記第２のキャッシュ手段は、命令と当該命令が格納されたメイン・メモリ上における１または複数のアドレスとを関連付けて保持し、命令を読み込むために指定されたアドレスに基づき、当該アドレスに関連付けられた命令を特定する、システム。
【請求項９】
前記第２のキャッシュ手段は、
キャッシュしようとする命令と同一の命令を既に保持している場合は、当該命令を指定する前記アドレスを、既に保持している当該命令と関連付けて保持し、
キャッシュしようとする命令と同一の命令を保持していない場合は、当該命令と当該命令を指定する前記アドレスとを関連付けて保持する、請求項８に記載のシステム。
【請求項１０】
前記第２のキャッシュ手段は、前記第１のキャッシュ手段にキャッシュされた命令のうち、読み込み要求に対してヒットした回数が予め定められた閾値を超えた命令をキャッシュする、請求項８または請求項９に記載のシステム。
【請求項１１】
前記第２のキャッシュ手段にキャッシュされた命令と同一のアドレスにおける当該命令は、前記第１のキャッシュ手段から消去される、請求項８乃至請求項１０のいずれかに記載のシステム。
【請求項１２】
前記選択手段は、読み込まれる対象の命令が前記第１のキャッシュ手段および前記第２のキャッシュ手段のいずれにもキャッシュされている場合に、当該第２のキャッシュ手段から読み込むことを選択する、請求項８乃至請求項１１のいずれかに記載のシステム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２０１３−１０９５８８（Ｐ２０１３−１０９５８８Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５４２８０（Ｐ２０１１−２５４２８０）
【出願日】平成２３年１１月２１日（２０１１．１１．２１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【復代理人】
【識別番号】１００１０４８８０
【弁理士】
【氏名又は名称】古部 次郎
【復代理人】
【識別番号】１００１１８２０１
【弁理士】
【氏名又は名称】千田 武
【復代理人】
【識別番号】１００１１８１０８
【弁理士】
【氏名又は名称】久保 洋之
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月２１日（２０１１．１１．２１）
【出願人】（３９０００９５３１）インターナショナル・ビジネス・マシーンズ・コーポレーション (4,084)
【氏名又は名称原語表記】ＩＮＴＥＲＮＡＴＩＯＮＡＬ ＢＵＳＩＮＥＳＳ ＭＡＣＨＩＮＥＳ ＣＯＲＰＯＲＡＴＩＯＮ
【復代理人】
【識別番号】１００１０４８８０
【弁理士】
【氏名又は名称】古部 次郎
【復代理人】
【識別番号】１００１１８２０１
【弁理士】
【氏名又は名称】千田 武
【復代理人】
【識別番号】１００１１８１０８
【弁理士】
【氏名又は名称】久保 洋之
【Ｆターム（参考）】
[ Back to top ]