JPH05189307A - 計算機システム - Google Patents
計算機システムInfo
- Publication number
- JPH05189307A JPH05189307A JP4005720A JP572092A JPH05189307A JP H05189307 A JPH05189307 A JP H05189307A JP 4005720 A JP4005720 A JP 4005720A JP 572092 A JP572092 A JP 572092A JP H05189307 A JPH05189307 A JP H05189307A
- Authority
- JP
- Japan
- Prior art keywords
- cache
- memory
- cache memory
- program
- internal
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
Landscapes
- Memory System Of A Hierarchy Structure (AREA)
Abstract
(57)【要約】
【目的】プログラムによってはキャッシュメモリを使用
しないようにもでき、平均アクセス時間を改善してＣＰ
Ｕの性能向上を図ることを目的とする。 【構成】ＣＰＵと内部キャッシュメモリとの間で命令や
データ及び演算結果等をやり取りしながら任意のプログ
ラムを実行する計算機システムにおいて、前記プログラ
ムを実行した場合のキャッシュミス率を予測する予測手
段を備え、所定値を越えるキャッシュミス率が予測され
た場合には、前記内部キャッシュメモリを介すことなく
直接に、主記憶又は該主記憶の上位に位置する外部キャ
ッシュメモリとの間で命令やデータ及び演算結果等をや
り取りすることを特徴とする。
しないようにもでき、平均アクセス時間を改善してＣＰ
Ｕの性能向上を図ることを目的とする。 【構成】ＣＰＵと内部キャッシュメモリとの間で命令や
データ及び演算結果等をやり取りしながら任意のプログ
ラムを実行する計算機システムにおいて、前記プログラ
ムを実行した場合のキャッシュミス率を予測する予測手
段を備え、所定値を越えるキャッシュミス率が予測され
た場合には、前記内部キャッシュメモリを介すことなく
直接に、主記憶又は該主記憶の上位に位置する外部キャ
ッシュメモリとの間で命令やデータ及び演算結果等をや
り取りすることを特徴とする。
Description
【０００１】
【産業上の利用分野】本発明は、計算機システム、特に
内部キャッシュメモリを備える計算機システムに関す
る。一般に、主記憶用のデバイスにはビット単価の安い
ダイナミックラム（ＤＲＡＭ）が用いられる。ところ
で、このＤＲＡＭのアクセス速度は例えばスタティック
ラム（ＳＲＡＭ）に比して遅く、ＣＰＵの性能を充分に
引き出すためには、主記憶とＣＰＵの間に高速動作型の
小容量メモリ（いわゆるキャッシュメモリ）を介在させ
ることが多い。
内部キャッシュメモリを備える計算機システムに関す
る。一般に、主記憶用のデバイスにはビット単価の安い
ダイナミックラム（ＤＲＡＭ）が用いられる。ところ
で、このＤＲＡＭのアクセス速度は例えばスタティック
ラム（ＳＲＡＭ）に比して遅く、ＣＰＵの性能を充分に
引き出すためには、主記憶とＣＰＵの間に高速動作型の
小容量メモリ（いわゆるキャッシュメモリ）を介在させ
ることが多い。
【０００２】
【従来の技術】図７はキャッシュメモリを搭載する従来
の計算機システムの要部概念ブロックである。ここで
は、記憶階層構造を持つ計算機システムを例としてい
る。１はＣＰＵ（central processing unit ）、２は主
記憶であり、これらのＣＰＵ１と主記憶の２間にキャッ
シュメモリ（外部キャッシュ制御装置を含む）３を介在
させると共に、ＣＰＵ１の内部にもキャッシュメモリ
（命令キャッシュメモリ及びデータキャッシュメモリ）
４、５を備える。
の計算機システムの要部概念ブロックである。ここで
は、記憶階層構造を持つ計算機システムを例としてい
る。１はＣＰＵ（central processing unit ）、２は主
記憶であり、これらのＣＰＵ１と主記憶の２間にキャッ
シュメモリ（外部キャッシュ制御装置を含む）３を介在
させると共に、ＣＰＵ１の内部にもキャッシュメモリ
（命令キャッシュメモリ及びデータキャッシュメモリ）
４、５を備える。
【０００３】ＣＰＵ１内部のキャッシュメモリ（以下、
内部キャッシュメモリ）４、５は、例えば２ｋＢ（キロ
バイト）から６４ｋＢ程度の小さな容量であり、ＣＰＵ
１の外部のキャッシュメモリ（２次キャッシュメモリと
も言う。以下、外部キャッシュメモリ）３は、例えば１
２８ｋＢから２ＭＢ（メガバイト）程度の大きな容量で
ある。これらのキャッシュメモリ３、４、５には、アク
セス速度の速い（但し、ビット単価は高い）例えばＳＲ
ＡＭが用いられ、主記憶２にはビット単価の安い（但
し、アクセス速度は遅い）例えばＤＲＡＭが用いられ
る。
内部キャッシュメモリ）４、５は、例えば２ｋＢ（キロ
バイト）から６４ｋＢ程度の小さな容量であり、ＣＰＵ
１の外部のキャッシュメモリ（２次キャッシュメモリと
も言う。以下、外部キャッシュメモリ）３は、例えば１
２８ｋＢから２ＭＢ（メガバイト）程度の大きな容量で
ある。これらのキャッシュメモリ３、４、５には、アク
セス速度の速い（但し、ビット単価は高い）例えばＳＲ
ＡＭが用いられ、主記憶２にはビット単価の安い（但
し、アクセス速度は遅い）例えばＤＲＡＭが用いられ
る。
【０００４】このような構成によれば、内部キャッシュ
メモリ４、５及び外部キャッシュメモリ３を介して主記
憶２をアクセスでき、キャッシュメモリ（特に内部キャ
ッシュメモリ４、５）のアクセス速度でＣＰＵ１の性能
を決めることができる。
メモリ４、５及び外部キャッシュメモリ３を介して主記
憶２をアクセスでき、キャッシュメモリ（特に内部キャ
ッシュメモリ４、５）のアクセス速度でＣＰＵ１の性能
を決めることができる。
【０００５】
【発明が解決しようとする課題】しかしながら、かかる
従来の計算機システムにあっては、ＣＰＵと主記憶の間
に介在するキャッシュメモリ（特に内部キャッシュメモ
リ）を“常に”使用する構成となっていたため、ミスヒ
ット（必要とする命令やデータが存在しない）が頻繁に
発生するようなプログラムをＣＰＵで実行する場合に
は、却ってＣＰＵの性能を低下させてしまうといった問
題点があった。
従来の計算機システムにあっては、ＣＰＵと主記憶の間
に介在するキャッシュメモリ（特に内部キャッシュメモ
リ）を“常に”使用する構成となっていたため、ミスヒ
ット（必要とする命令やデータが存在しない）が頻繁に
発生するようなプログラムをＣＰＵで実行する場合に
は、却ってＣＰＵの性能を低下させてしまうといった問
題点があった。
【０００６】一般に、ＣＰＵの平均アクセス時間（ＣＰ
Ｕがキャッシュメモリからデータを得るのに要する時
間）は、 平均アクセス時間＝アクセス時間＋ミス率×ミスペナル
ティ で与えられ、この平均アクセス時間が短いキャッシュメ
モリほどＣＰＵの性能向上に寄与するが、例えば、アク
セス時間が２サイクル、ミス率が1.00、ペナルティが８
（サイクル）の内部キャッシュメモリの平均アクセス時
間は、 （２＋１．０8）cycl 但し、cyclはサイクル時間。となり、一方、アクセス時
間が３サイクル、ミス率が0.01、ペナルティが９（サイ
クル）の外部キャッシュメモリの平均アクセス時間は、 ３．０９cycl となる。
Ｕがキャッシュメモリからデータを得るのに要する時
間）は、 平均アクセス時間＝アクセス時間＋ミス率×ミスペナル
ティ で与えられ、この平均アクセス時間が短いキャッシュメ
モリほどＣＰＵの性能向上に寄与するが、例えば、アク
セス時間が２サイクル、ミス率が1.00、ペナルティが８
（サイクル）の内部キャッシュメモリの平均アクセス時
間は、 （２＋１．０8）cycl 但し、cyclはサイクル時間。となり、一方、アクセス時
間が３サイクル、ミス率が0.01、ペナルティが９（サイ
クル）の外部キャッシュメモリの平均アクセス時間は、 ３．０９cycl となる。
【０００７】したがって、かかる条件となるようなプロ
グラムを実行する場合は、内蔵キャッシュメモリの平均
アクセス時間の影響で、却ってＣＰＵの性能低下を引き
起こすといった不具合がある。そこで、本発明は、プロ
グラムによってはキャッシュメモリを使用しないように
もでき、平均アクセス時間を改善してＣＰＵの性能向上
を図ることを目的とする。
グラムを実行する場合は、内蔵キャッシュメモリの平均
アクセス時間の影響で、却ってＣＰＵの性能低下を引き
起こすといった不具合がある。そこで、本発明は、プロ
グラムによってはキャッシュメモリを使用しないように
もでき、平均アクセス時間を改善してＣＰＵの性能向上
を図ることを目的とする。
【０００８】
【課題を解決するための手段】本発明は、上記目的を達
成するためその原理図を図１に示すように、ＣＰＵと内
部キャッシュメモリとの間で命令やデータ及び演算結果
等をやり取りしながら任意のプログラムを実行する計算
機システムにおいて、前記プログラムを実行した場合の
キャッシュミス率を予測する予測手段を備え、所定値を
越えるキャッシュミス率が予測された場合には、前記内
部キャッシュメモリを介すことなく直接に、主記憶又は
該主記憶の上位に位置する外部キャッシュメモリとの間
で命令やデータ及び演算結果等をやり取りすることを特
徴とする。
成するためその原理図を図１に示すように、ＣＰＵと内
部キャッシュメモリとの間で命令やデータ及び演算結果
等をやり取りしながら任意のプログラムを実行する計算
機システムにおいて、前記プログラムを実行した場合の
キャッシュミス率を予測する予測手段を備え、所定値を
越えるキャッシュミス率が予測された場合には、前記内
部キャッシュメモリを介すことなく直接に、主記憶又は
該主記憶の上位に位置する外部キャッシュメモリとの間
で命令やデータ及び演算結果等をやり取りすることを特
徴とする。
【０００９】
【作用】本発明では、所定値を越える程度のキャッシュ
ミスが予測されるようなプログラムを実行する場合に、
内部キャッシュメモリを介することなく、ＣＰＵと主記
憶又は外部キャッシュメモリとの間で命令やデータ及び
演算結果が直接にやり取りされる。したがって、かかる
場合の平均アクセス時間が、内部キャッシュメモリより
も容量の大きい例えば外部キャッシュメモリによって決
まり、ＣＰＵの性能向上が図られる。
ミスが予測されるようなプログラムを実行する場合に、
内部キャッシュメモリを介することなく、ＣＰＵと主記
憶又は外部キャッシュメモリとの間で命令やデータ及び
演算結果が直接にやり取りされる。したがって、かかる
場合の平均アクセス時間が、内部キャッシュメモリより
も容量の大きい例えば外部キャッシュメモリによって決
まり、ＣＰＵの性能向上が図られる。
【００１０】
【実施例】以下、本発明の実施例を図面に基づいて説明
する。図２〜図６は本発明に係る計算機システムの一実
施例を示す図である。まず、構成を説明する。図２にお
いて、１０は、特に限定しないが命令・データ分離型の
キャッシュシステムを搭載するＣＰＵであり、整数演算
部１１、浮動小数点演算部１２、レジスタファイル１
３、１４、及び、キャッシュ性能評価部（予測手段）１
５を備えると共に、命令キャッシュ部２０及びデータキ
ャッシュ部３０を備える。
する。図２〜図６は本発明に係る計算機システムの一実
施例を示す図である。まず、構成を説明する。図２にお
いて、１０は、特に限定しないが命令・データ分離型の
キャッシュシステムを搭載するＣＰＵであり、整数演算
部１１、浮動小数点演算部１２、レジスタファイル１
３、１４、及び、キャッシュ性能評価部（予測手段）１
５を備えると共に、命令キャッシュ部２０及びデータキ
ャッシュ部３０を備える。
【００１１】命令キャッシュ部２０は、比較的小容量
（例えば２ｋＢ〜８ｋＢ）で且つ高速動作型のメモリデ
バイス（例えばＳＲＡＭ）を用いたキャッシュメモリ２
１（略号；Ｉ−ＣＡＣＨＥ、以下、内部命令キャッシュ
メモリ）、内部命令キャッシュメモリ用のエントリテー
ブル２２（略号；Ｉ−ＴＬＢ）、命令デコータ２３（略
号；ＤＥＣ）、及び、アドレス生成回路２４（略号；Ａ
ＤＤ）等を含む。
（例えば２ｋＢ〜８ｋＢ）で且つ高速動作型のメモリデ
バイス（例えばＳＲＡＭ）を用いたキャッシュメモリ２
１（略号；Ｉ−ＣＡＣＨＥ、以下、内部命令キャッシュ
メモリ）、内部命令キャッシュメモリ用のエントリテー
ブル２２（略号；Ｉ−ＴＬＢ）、命令デコータ２３（略
号；ＤＥＣ）、及び、アドレス生成回路２４（略号；Ａ
ＤＤ）等を含む。
【００１２】また、データキャッシュ部３０は、これも
比較的小容量（例えば２ｋＢ〜８ｋＢ）で且つ高速動作
型のメモリデバイス（例えばＳＲＡＭ）を用いたキャッ
シュメモリメモリ３１（略号；Ｄ−ＣＡＣＨＥ、以下、
内部データキャッシュメモリ）、内部データキャッシュ
メモリ用のエントリテーブル３２（略号；Ｄ−ＴＬ
Ｂ）、及び、データ切替回路３３（略号；ＳＥＬ）を含
む。
比較的小容量（例えば２ｋＢ〜８ｋＢ）で且つ高速動作
型のメモリデバイス（例えばＳＲＡＭ）を用いたキャッ
シュメモリメモリ３１（略号；Ｄ−ＣＡＣＨＥ、以下、
内部データキャッシュメモリ）、内部データキャッシュ
メモリ用のエントリテーブル３２（略号；Ｄ−ＴＬ
Ｂ）、及び、データ切替回路３３（略号；ＳＥＬ）を含
む。
【００１３】ここで、データ切替回路３３は、通常は、
外部キャッシュメモリ４０と内部データキャッシュメモ
リ３１との間、及び、内部データキャッシュメモリ３１
とレジスタファイル１３、１４の間を接続し、言い換え
れば内部データキャッシュメモリ３１を介してレジスタ
ファイル１３、１４（すなわち整数演算部１１、浮動小
数点演算部１２）と外部キャッシュメモリ４０の間を
“間接的”に接続するが、キャッシュ性能評価部１５に
よって所定のビット情報（キャッシュ使用ビット）に例
えば“１”がセットされたときには、外部キャッシュメ
モリ４０とレジスタファイル１３、１４の間を“直接
的”に接続することができる。なお、ここでは、主記憶
５０の上位に外部キャッシュメモリ４０を位置させる、
いわゆる階層構造型のメモリシステムを例にしている
が、これに限らず、データ切替回路３３と主記憶５０の
間に外部キャッシュメモリが介在しないシステムであっ
てもよい。このシステムの場合には、上記説明中の外部
キャッシュメモリ４０を主記憶５０と読み替えるものと
する。
外部キャッシュメモリ４０と内部データキャッシュメモ
リ３１との間、及び、内部データキャッシュメモリ３１
とレジスタファイル１３、１４の間を接続し、言い換え
れば内部データキャッシュメモリ３１を介してレジスタ
ファイル１３、１４（すなわち整数演算部１１、浮動小
数点演算部１２）と外部キャッシュメモリ４０の間を
“間接的”に接続するが、キャッシュ性能評価部１５に
よって所定のビット情報（キャッシュ使用ビット）に例
えば“１”がセットされたときには、外部キャッシュメ
モリ４０とレジスタファイル１３、１４の間を“直接
的”に接続することができる。なお、ここでは、主記憶
５０の上位に外部キャッシュメモリ４０を位置させる、
いわゆる階層構造型のメモリシステムを例にしている
が、これに限らず、データ切替回路３３と主記憶５０の
間に外部キャッシュメモリが介在しないシステムであっ
てもよい。このシステムの場合には、上記説明中の外部
キャッシュメモリ４０を主記憶５０と読み替えるものと
する。
【００１４】キャッシュ性能評価部１５は、整数演算部
１１や浮動小数点演算部１２で実行予定のプログラムを
評価するもので、例えば実行予定のプログラムが、キ
ャッシュアクセスが極めて頻繁に発生する特定のプログ
ラムである場合、そのプログラムが必要とするデータ
の格納場所が主記憶の幾つかの論理空間に分かれて格納
されている場合、必要とするデータに規則性が見られ
ない場合、内部キャッシュメモリの容量に比べてプロ
グラムサイズが相当に大きい場合、等に該当するか否か
を判定し、該当するときにキャッシュ使用ビットに
“１”をセットする。これらの評価条件〜は、キャ
ッシュミスの発生を予測するための有効な例であり、勿
論、これ以外の評価条件の設定を妨げるものではない。
１１や浮動小数点演算部１２で実行予定のプログラムを
評価するもので、例えば実行予定のプログラムが、キ
ャッシュアクセスが極めて頻繁に発生する特定のプログ
ラムである場合、そのプログラムが必要とするデータ
の格納場所が主記憶の幾つかの論理空間に分かれて格納
されている場合、必要とするデータに規則性が見られ
ない場合、内部キャッシュメモリの容量に比べてプロ
グラムサイズが相当に大きい場合、等に該当するか否か
を判定し、該当するときにキャッシュ使用ビットに
“１”をセットする。これらの評価条件〜は、キャ
ッシュミスの発生を予測するための有効な例であり、勿
論、これ以外の評価条件の設定を妨げるものではない。
【００１５】以上のように、本実施例によれば、実行し
ようとするプログラムを評価してキャッシュミスの発生
を予測し、その予測結果により、内部命令キャッシュメ
モリ３１の使用／不使用を決定して、データ切替回路３
３を操作しているので、ＣＰＵ１０の平均アクセス時間
を改善でき、ＣＰＵ１０（正確にはＣＰＵ内部の整数演
算部１１や浮動小数点演算部１２）の性能を充分に発揮
させることができる。
ようとするプログラムを評価してキャッシュミスの発生
を予測し、その予測結果により、内部命令キャッシュメ
モリ３１の使用／不使用を決定して、データ切替回路３
３を操作しているので、ＣＰＵ１０の平均アクセス時間
を改善でき、ＣＰＵ１０（正確にはＣＰＵ内部の整数演
算部１１や浮動小数点演算部１２）の性能を充分に発揮
させることができる。
【００１６】図３は、キャッシュのミス率を求めるため
の演算アルゴリズムの一例（但し、ダイレクトマップ
用）である。図３において、Ｖ（Ｂ）はメモリ参照命令
の総数、ｕ（Ｂ）はτ回（例えば10,000回）の参照ごと
のメモリ参照数、Ｓは内蔵キャッシュメモリのウエイ
（Way ）当たりのエントリー数、Ｔはメモリ参照命令総
数をτ回で除した値である。このアルゴリズムでは、キ
ャッシュミスの算出に、
の演算アルゴリズムの一例（但し、ダイレクトマップ
用）である。図３において、Ｖ（Ｂ）はメモリ参照命令
の総数、ｕ（Ｂ）はτ回（例えば10,000回）の参照ごと
のメモリ参照数、Ｓは内蔵キャッシュメモリのウエイ
（Way ）当たりのエントリー数、Ｔはメモリ参照命令総
数をτ回で除した値である。このアルゴリズムでは、キ
ャッシュミスの算出に、
【００１７】
【数１】
【００１８】
【数２】
【００１９】
【数３】
【００２０】を用いている。ここで、ダイレクトマップ
用とは、キャッシュメモリのウエイ（Way ）数Ｄに１の
みを適用したことを意味する。以下、図３のアルゴリズ
ムの詳細を説明する。 １．はじめに 一般に、キャッシュメモリの構成や性能は、プロセッサ
の構成や性能に直接影響を及ぼす重大な要因の一つであ
ると考えられている。そのようなキャッシュメモリの性
能評価はプロセッサの仕様を決める際に不可欠である
が、評価の正確さを期するのに必要な全てのパラメータ
を取り込むことは実際上大変難しい。
用とは、キャッシュメモリのウエイ（Way ）数Ｄに１の
みを適用したことを意味する。以下、図３のアルゴリズ
ムの詳細を説明する。 １．はじめに 一般に、キャッシュメモリの構成や性能は、プロセッサ
の構成や性能に直接影響を及ぼす重大な要因の一つであ
ると考えられている。そのようなキャッシュメモリの性
能評価はプロセッサの仕様を決める際に不可欠である
が、評価の正確さを期するのに必要な全てのパラメータ
を取り込むことは実際上大変難しい。
【００２１】しかし、あまりに簡略化したモデルによる
シミュレーションは、現実の性能を反映しなくなり、評
価そのものの信頼性を損なうので、可能な限り実際に近
いシミュレーションを行う必要がある。そのためには、
できるだけ現実に近く、しかも簡潔で且つ本質的なワー
クロード（業務負荷）を設定しなければならない。A.Ag
arwalら（M.Horowitz and J.Hennessy "An Analytical
Cache Model":ACMTransactions on Computer Systems,V
ol 7,No 2 May 1989, 184-215）による「平均値解析法
を用いた解析的なキャッシュモデルによるシミュレーシ
ョン」（以下、論文１）によれば、確率論的手法を用い
ることにより、モデルの定式化を実現し、必要とするパ
ラメータをできるだけ少なくすることができる。 ２．キャッシュ解析的モデル 論文１の解析的キャッシュモデルに関する記述は、概
略、次の４つに分けることができる。
シミュレーションは、現実の性能を反映しなくなり、評
価そのものの信頼性を損なうので、可能な限り実際に近
いシミュレーションを行う必要がある。そのためには、
できるだけ現実に近く、しかも簡潔で且つ本質的なワー
クロード（業務負荷）を設定しなければならない。A.Ag
arwalら（M.Horowitz and J.Hennessy "An Analytical
Cache Model":ACMTransactions on Computer Systems,V
ol 7,No 2 May 1989, 184-215）による「平均値解析法
を用いた解析的なキャッシュモデルによるシミュレーシ
ョン」（以下、論文１）によれば、確率論的手法を用い
ることにより、モデルの定式化を実現し、必要とするパ
ラメータをできるだけ少なくすることができる。 ２．キャッシュ解析的モデル 論文１の解析的キャッシュモデルに関する記述は、概
略、次の４つに分けることができる。
【００２２】キャッシュミスを発生する要因 キャッシュモデルの構築 キャッシュモデルの構築（ブロックサイズを含む） 補足事項 ３−１．キャッシュミスを発生する要因について キャッシュミスを発生する要因は一般に、 要因１：Start-up effects （立ち上げ時の効果） 要因２：Nonstationary behavior （非定常効果） 要因３：Intrinsic interference （内部干渉効果） 要因４：Extrinsic interference （外部干渉効果） である。 ３−１−１．要因１ プロセスがプロセッサ上で最初に実行を開始するとき、
そのプロセスの初期ワークセットをキャッシュメモリに
取り入れる際にキャッシュミスが発生する。このミスが
立ち上げ時の効果を左右する。 ３−１−２．要因２ プロセスにおけるワーキングセットの変化がキャッシュ
ミスを誘発する場合がある。このときに発生するキャッ
シュミスは非定常効果によるものである。本カテゴリー
を用いることにより、キャッシュメモリにおけるワーキ
ングセットの変化に対応した小さな時間間隔にわたる位
相の微妙な変化をモデル化することができる。 ３−１−３．要因３ キャッシュメモリが有限であるため、複数のプログラム
ブロックが同じキャッシュブロックで競合して互いに衝
突することがある。このときに発生するミスは内部干渉
効果によるものであり、内部干渉効果によるミスは、あ
るプロセスのブロックが同じプロセスの衝突しているブ
ロックによりキャッシュメモリからパージされた後にフ
ェッチされるときに発生する。この内部干渉ミス数は、
以下の２要素の積により算出することができる。
そのプロセスの初期ワークセットをキャッシュメモリに
取り入れる際にキャッシュミスが発生する。このミスが
立ち上げ時の効果を左右する。 ３−１−２．要因２ プロセスにおけるワーキングセットの変化がキャッシュ
ミスを誘発する場合がある。このときに発生するキャッ
シュミスは非定常効果によるものである。本カテゴリー
を用いることにより、キャッシュメモリにおけるワーキ
ングセットの変化に対応した小さな時間間隔にわたる位
相の微妙な変化をモデル化することができる。 ３−１−３．要因３ キャッシュメモリが有限であるため、複数のプログラム
ブロックが同じキャッシュブロックで競合して互いに衝
突することがある。このときに発生するミスは内部干渉
効果によるものであり、内部干渉効果によるミスは、あ
るプロセスのブロックが同じプロセスの衝突しているブ
ロックによりキャッシュメモリからパージされた後にフ
ェッチされるときに発生する。この内部干渉ミス数は、
以下の２要素の積により算出することができる。
【００２３】第１の要素：衝突のためにパージポテンシ
ャルを持つプログラムプロックの数 第２の要素：パージポテンシャルを持つ一つのブロック
の衝突する頻度 ３−１−４．要因４ マルチプログラミング、Ｉ／Ｏ、クロック割り込み、又
はマルチキャッシュ時のデータ制御等により発生するミ
スが本カテゴリーに含まれる。ここでは、マルチプログ
ラミングによる外部干渉のみを取り扱うことにする。こ
のときの外部干渉ミスは、内部干渉ミスと同様の手法を
用いることによりモデル化することができる。 ３−２．キャッシュモデルの構築について 固定ブロック長を持つset-associative キャッシュをモ
デル化すると、そのミス率は、Start-up effects、Nons
tationary behavior、Intrinsic interference、及び、
Extrinsic interferenceによるミス率の合計で表され
る。ここで、それぞれの参照は単位時間間隔で表現され
るものと仮定すると共に、この単位時間間隔をｔｇ（ti
me granule）とし、さらに、１ｔｇは一連のτ個の参照
であると仮定する。
ャルを持つプログラムプロックの数 第２の要素：パージポテンシャルを持つ一つのブロック
の衝突する頻度 ３−１−４．要因４ マルチプログラミング、Ｉ／Ｏ、クロック割り込み、又
はマルチキャッシュ時のデータ制御等により発生するミ
スが本カテゴリーに含まれる。ここでは、マルチプログ
ラミングによる外部干渉のみを取り扱うことにする。こ
のときの外部干渉ミスは、内部干渉ミスと同様の手法を
用いることによりモデル化することができる。 ３−２．キャッシュモデルの構築について 固定ブロック長を持つset-associative キャッシュをモ
デル化すると、そのミス率は、Start-up effects、Nons
tationary behavior、Intrinsic interference、及び、
Extrinsic interferenceによるミス率の合計で表され
る。ここで、それぞれの参照は単位時間間隔で表現され
るものと仮定すると共に、この単位時間間隔をｔｇ（ti
me granule）とし、さらに、１ｔｇは一連のτ個の参照
であると仮定する。
【００２４】キャッシュＣは、セット数を表すＳ、セッ
ト当たりのエントリ数１、及びブロックサイズＢにより
記述される。モデルを記述するために必要なパラメータ
を以下で定義する。 τ：単位時間（ｔｇ）当たりに参照される数 Ｔ：プロセスの総時間数（単位はｔｇ） ｕ（Ｂ）：単位時間当たりにプロセスによりアクセスさ
れる一様なメモリブロックの平均数 Ｕ（Ｂ）：プロセスによりアクセスされる一様なメモリ
ブロックの総数 ｍ（Ｃ，ｔ）：キャッシュＣのｔ時間（単位はｔｇ）ま
でのプロセスｉに対するミス率 ３−２−１．Start-up effectsのミス率 単位時間サイズがStart-up周期を含むようにτを決める
とき、Start-up効果によるミスは最初の単位時間（ｔ
ｇ）に含まれる。このときのStart-up効果によるミス
は、
ト当たりのエントリ数１、及びブロックサイズＢにより
記述される。モデルを記述するために必要なパラメータ
を以下で定義する。 τ：単位時間（ｔｇ）当たりに参照される数 Ｔ：プロセスの総時間数（単位はｔｇ） ｕ（Ｂ）：単位時間当たりにプロセスによりアクセスさ
れる一様なメモリブロックの平均数 Ｕ（Ｂ）：プロセスによりアクセスされる一様なメモリ
ブロックの総数 ｍ（Ｃ，ｔ）：キャッシュＣのｔ時間（単位はｔｇ）ま
でのプロセスｉに対するミス率 ３−２−１．Start-up effectsのミス率 単位時間サイズがStart-up周期を含むようにτを決める
とき、Start-up効果によるミスは最初の単位時間（ｔ
ｇ）に含まれる。このときのStart-up効果によるミス
は、
【００２５】
【数４】
【００２６】により求めることができる。 ３−２−３．Nonstationary behaviorのミス率 最初の単位時間に初めて参照されたブロックはキャッシ
ュにフェッチされる。また、次の周期でフェッチされた
ブロックのいくつかのものは参照されずに新しいブロッ
クに置き換えられるであろう。このような新しいブロッ
クに対する最初の参照が非定常効果によるミスの原因で
ある。この非定常効果によるキャッシュミスは、
ュにフェッチされる。また、次の周期でフェッチされた
ブロックのいくつかのものは参照されずに新しいブロッ
クに置き換えられるであろう。このような新しいブロッ
クに対する最初の参照が非定常効果によるミスの原因で
ある。この非定常効果によるキャッシュミスは、
【００２７】
【数５】
【００２８】で求めることができる。 ３−２−４．Intrinsic interferenceのミス率 別のブロックによりキャッシュからパージされた参照す
べきプログラムブロックが内部干渉ミス又は衝突ミスを
誘発する。内部干渉ミスは、静的特性と動的特性との積
を取ることにより算出できる。 ３−２−４−１．静的特性 プログラムブロックは任意のキャッシュセットで一様に
分布していると仮定すし、また、キャッシュはランダム
置換法を採用しているとする。ｄ個のブロックが一つの
キャッシュセットにマップされる確率Ｐ（ｄ）は、図４
に示される。このとき、衝突ポテンシャルを持つブロッ
クの平均数は、
べきプログラムブロックが内部干渉ミス又は衝突ミスを
誘発する。内部干渉ミスは、静的特性と動的特性との積
を取ることにより算出できる。 ３−２−４−１．静的特性 プログラムブロックは任意のキャッシュセットで一様に
分布していると仮定すし、また、キャッシュはランダム
置換法を採用しているとする。ｄ個のブロックが一つの
キャッシュセットにマップされる確率Ｐ（ｄ）は、図４
に示される。このとき、衝突ポテンシャルを持つブロッ
クの平均数は、
【００２９】
【数６】
【００３０】で求めることができる。 ３−２−４−２．動的特性 衝突率ｃを
【００３１】
【数７】
【００３２】と定義すると、Intrinsic interferenceに
よるキャッシュミスは、
よるキャッシュミスは、
【００３３】
【数８】
【００３４】で求めることができる。 ３−２−５．単位ブロックサイズに対するミス率 したがって、単位ブロックサイズに対するミス率は、数
１、数２及び数５より、
１、数２及び数５より、
【００３５】
【数９】
【００３６】で求めることができる。 ３−３．キャッシュモデルの構築（ブロックサイズを含
む）について ブロック長を可変としたset-associative キャッシュを
モデル化すると、ｕ及びＵのブロックサイズへの依存性
は、run lengthの分布とrun 間の空間間隔の分布により
決定される。ここで、runは一連の参照の最大値と定義
される。
む）について ブロック長を可変としたset-associative キャッシュを
モデル化すると、ｕ及びＵのブロックサイズへの依存性
は、run lengthの分布とrun 間の空間間隔の分布により
決定される。ここで、runは一連の参照の最大値と定義
される。
【００３７】Spatial localityを持つプログラムのrun
lengthを表現するために、図５に示すｎ状態のマルコフ
連鎖を用いる。ここで、ｎは最大のrun lengthである。
Ｒ１はrun の初期状態である。最初のｋ個のアドレスが
シーケンシャルであるならば、状態はＲｋに至る。ｆｋ
は次のアドレスがシーケンシャルなｋ個のアドレスであ
る確率である。ここで、導入したｒ状態モデルを２状態
モデルで近似する。これは、run lengthが単位長である
か、またはそれ以外かにより区別する。このときrunのl
engthがＩであることの確率は、以下のように与えられ
る。
lengthを表現するために、図５に示すｎ状態のマルコフ
連鎖を用いる。ここで、ｎは最大のrun lengthである。
Ｒ１はrun の初期状態である。最初のｋ個のアドレスが
シーケンシャルであるならば、状態はＲｋに至る。ｆｋ
は次のアドレスがシーケンシャルなｋ個のアドレスであ
る確率である。ここで、導入したｒ状態モデルを２状態
モデルで近似する。これは、run lengthが単位長である
か、またはそれ以外かにより区別する。このときrunのl
engthがＩであることの確率は、以下のように与えられ
る。
【００３８】
【数１０】
【００３９】また、平均run lengthは、
【００４０】
【数１１】
【００４１】で求めることができる。このとき、単位時
間当たりの一様なrunの数は、 ｕ（１）／Ｉav となる。次に一つのrun 全体をキャッシュに入れたとき
にフェッチされるブロックの集合をcoverと定義し、ま
た、このとき使用されているブロックの数をcoversize
と定義する。coversizeはrun lengthＩとブロックサイ
ズＢを用いて、
間当たりの一様なrunの数は、 ｕ（１）／Ｉav となる。次に一つのrun 全体をキャッシュに入れたとき
にフェッチされるブロックの集合をcoverと定義し、ま
た、このとき使用されているブロックの数をcoversize
と定義する。coversizeはrun lengthＩとブロックサイ
ズＢを用いて、
【００４２】
【数１２】
【００４３】で求めることができる。したがって、ブロ
ックサイズＢが与えられたときの単位ワードｕ（１）に
対するプログラムブロック数は、次のように算出され
る。
ックサイズＢが与えられたときの単位ワードｕ（１）に
対するプログラムブロック数は、次のように算出され
る。
【００４４】
【数１３】
【００４５】以上のことから、ブロックサイズＢが与え
られたときのミス率は、
られたときのミス率は、
【００４６】
【数１４】
【００４７】で求めることができる。 ３−４．Extrinsic interference これまでの説明は、単一のプログラムに対するミスの効
果を定式化したものであった。しかし、現実のシステム
におけるワークロードはマルチプログラムにより構成さ
れる場合が多々ある。そこで、より正確なキャッシュ性
能を得るためには、マルチプログラム化されたキャッシ
ュモデルを採用する必要がある。
果を定式化したものであった。しかし、現実のシステム
におけるワークロードはマルチプログラムにより構成さ
れる場合が多々ある。そこで、より正確なキャッシュ性
能を得るためには、マルチプログラム化されたキャッシ
ュモデルを採用する必要がある。
【００４８】以下の説明において、オペレーティングシ
ステムは一定時間間隔（タイムスライス）でスケジュー
ルを行うラウンドロビン方式を使用すると仮定する。マ
ルチプログラムのレベルをmpl で表し、また、単位タイ
ムスライス当たりのｔｇ時間をｔｓとする。ここで、キ
ャッシュは、物理アドレスによりマッピングされている
と仮定する。このことは、コンテキストスイッチング時
にキャッシュフラッシュしないことを意味する。
ステムは一定時間間隔（タイムスライス）でスケジュー
ルを行うラウンドロビン方式を使用すると仮定する。マ
ルチプログラムのレベルをmpl で表し、また、単位タイ
ムスライス当たりのｔｇ時間をｔｓとする。ここで、キ
ャッシュは、物理アドレスによりマッピングされている
と仮定する。このことは、コンテキストスイッチング時
にキャッシュフラッシュしないことを意味する。
【００４９】時刻ｔｉにおけるプロセスｉに対するミス
率をｍi（Ｃ，ｔi）とする。ここで、carry-over setを
プロセスがスイッチング時にキャッシュに残し、かつ再
度スイッチングされたときに再利用するブロックのset
とする。このcarry-over setのブロックの平均数をＶi
（Ｂ） とする。これはキャッシュサイズで制限される
パラメータであり、
率をｍi（Ｃ，ｔi）とする。ここで、carry-over setを
プロセスがスイッチング時にキャッシュに残し、かつ再
度スイッチングされたときに再利用するブロックのset
とする。このcarry-over setのブロックの平均数をＶi
（Ｂ） とする。これはキャッシュサイズで制限される
パラメータであり、
【００５０】
【数１５】
【００５１】のように表すことができる。ｉ以外の全て
のプロセスのブロック数ｕi'（Ｂ）は、
のプロセスのブロック数ｕi'（Ｂ）は、
【００５２】
【数１６】
【００５３】となる。このときｄ個のブロックが任意の
キャッシュセットに入る確率は、
キャッシュセットに入る確率は、
【００５４】
【数１７】
【００５５】となる。キャッシュはＬＲＵ置換法を採用
しているとき任意のセットにおいてパージされるプロセ
スｉのブロック数は、
しているとき任意のセットにおいてパージされるプロセ
スｉのブロック数は、
【００５６】
【数１８】
【００５７】となる。キャッシュ全体におけるパージさ
れるプロセスｉのブロック数は、
れるプロセスｉのブロック数は、
【００５８】
【数１９】
【００５９】で求めることができる。以上のことから、
マルチプログラムによるミス率は、
マルチプログラムによるミス率は、
【００６０】
【数２０】
【００６１】で求めることができる。 ３−５．補足事項 内部干渉ミス率の算出に用いる衝突率ｃは、定数ではな
くウエイ数１に依存する。ｃ（Ｄ）をD-way set associ
ative キャッシュの衝突率とする。このときあるセット
にマップされているｄ個のプログラムブロック（図６参
照）に対するヒット率は、
くウエイ数１に依存する。ｃ（Ｄ）をD-way set associ
ative キャッシュの衝突率とする。このときあるセット
にマップされているｄ個のプログラムブロック（図６参
照）に対するヒット率は、
【００６２】
【数２１】
【００６３】と表すことができる。但し、数１８はDire
ct Mapキャッシュの衝突率ｃ（１）に考慮されている１
個のブロックを排除している。これよりｄ個のブロック
がマップされているウエイ数１のキャッシュの衝突率ｃ
（Ｄ，ｄ）は、
ct Mapキャッシュの衝突率ｃ（１）に考慮されている１
個のブロックを排除している。これよりｄ個のブロック
がマップされているウエイ数１のキャッシュの衝突率ｃ
（Ｄ，ｄ）は、
【００６４】
【数２２】
【００６５】で求めることができ、この数１９から全て
のｄに対するｃ（Ｄ，ｄ）の平均を算出すると、
のｄに対するｃ（Ｄ，ｄ）の平均を算出すると、
【００６６】
【数２３】
【００６７】を得る。したがって、ミス率の算出に用い
る衝突率を数２０により算出した値「ｃ（Ｄ）」を用い
ることにより、set-associative キャッシュのミス率を
求めることができる。 ４．ワークロード シミュレーションに使用したワークロードについては、
SPISE及びGCCを想定した。これらは、共にSPECベンチマ
ークで用いられるプログラムであり、前者はアナログ回
路シミュレーションのためのプログラム、後者はGNU の
Ｃ言語コンパイラである。J.Hennessy & D.Patterson
著「Computer Architecture A Quantitative Approch」
p.C5によれば、上記ワークロードのメモリ参照率は、 SPICE＝36.14％ GCC＝32.55％ と算出できる。プログラムの総演算数を１００万回と仮
定し、次表１に示すパラメータに固定してシミュレーシ
ョンを行った。なお、メモリ参照数以外のパラメータは
論文１のものを使用している。
る衝突率を数２０により算出した値「ｃ（Ｄ）」を用い
ることにより、set-associative キャッシュのミス率を
求めることができる。 ４．ワークロード シミュレーションに使用したワークロードについては、
SPISE及びGCCを想定した。これらは、共にSPECベンチマ
ークで用いられるプログラムであり、前者はアナログ回
路シミュレーションのためのプログラム、後者はGNU の
Ｃ言語コンパイラである。J.Hennessy & D.Patterson
著「Computer Architecture A Quantitative Approch」
p.C5によれば、上記ワークロードのメモリ参照率は、 SPICE＝36.14％ GCC＝32.55％ と算出できる。プログラムの総演算数を１００万回と仮
定し、次表１に示すパラメータに固定してシミュレーシ
ョンを行った。なお、メモリ参照数以外のパラメータは
論文１のものを使用している。
【００６８】
【００６９】
【発明の効果】本発明によれば、プログラムによっては
キャッシュメモリを使用しないようにもでき、平均アク
セス時間を改善してＣＰＵの性能向上を図ることができ
る。
キャッシュメモリを使用しないようにもでき、平均アク
セス時間を改善してＣＰＵの性能向上を図ることができ
る。
【図１】本発明の原理図である。
【図２】一実施例の概念構成図である。
【図３】一実施例のキャッシュのミス率を求めるための
演算アルゴリズムである。
演算アルゴリズムである。
【図４】ｄ個のブロックが一つのキャッシュセットにマ
ップされる確率Ｐ（ｄ）の説明図である。
ップされる確率Ｐ（ｄ）の説明図である。
【図５】ｎ状態のマルコフ連鎖の図である。
【図６】ｄ個のプログラムブロックを示す図である。
【図７】従来例の概念構成図である。
１０：ＣＰＵ １５：キャッシュ性能評価部（予測手段） ３１：内部データキャッシュ（内部キャッシュメモリ） ４０：外部キャッシュメモリ ５０：主記憶
Claims (1)
- 【請求項１】ＣＰＵと内部キャッシュメモリとの間で命
令やデータ及び演算結果等をやり取りしながら任意のプ
ログラムを実行する計算機システムにおいて、 前記プログラムを実行した場合のキャッシュミス率を予
測する予測手段を備え、 所定値を越えるキャッシュミス率が予測された場合に
は、前記内部キャッシュメモリを介すことなく直接に、
主記憶又は該主記憶の上位に位置する外部キャッシュメ
モリとの間で命令やデータ及び演算結果等をやり取りす
ることを特徴とする計算機システム。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4005720A JPH05189307A (ja) | 1992-01-16 | 1992-01-16 | 計算機システム |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4005720A JPH05189307A (ja) | 1992-01-16 | 1992-01-16 | 計算機システム |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH05189307A true JPH05189307A (ja) | 1993-07-30 |
Family
ID=11618959
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4005720A Withdrawn JPH05189307A (ja) | 1992-01-16 | 1992-01-16 | 計算機システム |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH05189307A (ja) |
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005249735A (ja) * | 2004-03-08 | 2005-09-15 | Advantest Corp | パターン発生器、及び試験装置 |
| US6959359B1 (en) | 1999-07-14 | 2005-10-25 | Hitachi, Ltd. | Software prefetch system and method for concurrently overriding data prefetched into multiple levels of cache |
| US7899992B2 (en) | 2005-02-21 | 2011-03-01 | Panasonic Corporation | Cache circuit and control circuits of a cache memory |
| US9703593B2 (en) | 2012-02-06 | 2017-07-11 | Samsung Electronics Co., Ltd. | Apparatus and method for memory overlay |
| WO2020245872A1 (ja) * | 2019-06-03 | 2020-12-10 | 三菱電機株式会社 | 情報処理装置及び情報処理システム |
-
1992
- 1992-01-16 JP JP4005720A patent/JPH05189307A/ja not_active Withdrawn
Cited By (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6959359B1 (en) | 1999-07-14 | 2005-10-25 | Hitachi, Ltd. | Software prefetch system and method for concurrently overriding data prefetched into multiple levels of cache |
| JP2005249735A (ja) * | 2004-03-08 | 2005-09-15 | Advantest Corp | パターン発生器、及び試験装置 |
| US7899992B2 (en) | 2005-02-21 | 2011-03-01 | Panasonic Corporation | Cache circuit and control circuits of a cache memory |
| US9703593B2 (en) | 2012-02-06 | 2017-07-11 | Samsung Electronics Co., Ltd. | Apparatus and method for memory overlay |
| WO2020245872A1 (ja) * | 2019-06-03 | 2020-12-10 | 三菱電機株式会社 | 情報処理装置及び情報処理システム |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Joseph et al. | Prefetching using markov predictors | |
| CN104636274B (zh) | 数据预取方法以及微处理器 | |
| Kandiraju et al. | Going the distance for TLB prefetching: An application-driven study | |
| Saulsbury et al. | Recency-based TLB preloading | |
| Agarwal et al. | An analytical cache model | |
| US7089370B2 (en) | Apparatus and method for pre-fetching page data using segment table data | |
| US20050071571A1 (en) | Apparatus and method for pre-fetching data to cached memory using persistent historical page table data | |
| US20070130237A1 (en) | Transient cache storage | |
| JP6478843B2 (ja) | 半導体装置及びキャッシュメモリ制御方法 | |
| Zhang et al. | RnR: A software-assisted record-and-replay hardware prefetcher | |
| EP2159706A1 (en) | Operation processing apparatus and operation processing method | |
| Tse et al. | CPU cache prefetching: Timing evaluation of hardware implementations | |
| Butt et al. | The performance impact of kernel prefetching on buffer cache replacement algorithms | |
| Daly et al. | Cache restoration for highly partitioned virtualized systems | |
| Chang et al. | CASA: Contention-aware scratchpad memory allocation for online hybrid on-chip memory management | |
| JPH05189307A (ja) | 計算機システム | |
| EP1869557B1 (en) | Global modified indicator to reduce power consumption on cache miss | |
| Kim et al. | A partitioned on-chip virtual cache for fast processors | |
| Hua et al. | Early resolution of address translation in cache design | |
| Wang et al. | Minimizing area cost of on-chip cache memories by caching address tags | |
| CN117149272A (zh) | 指令处理方法及装置、电子设备 | |
| JPWO2008155812A1 (ja) | プロセッサおよびプリフェッチ支援プログラム | |
| JPH1173329A (ja) | ソフトウエア開発支援システム | |
| JP2002334128A (ja) | 半導体集積回路の消費電力シミュレーション方法 | |
| JP3085267B2 (ja) | メモリアクセス高速化装置 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Withdrawal of application because of no request for examination |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19990408 |