JP3085267B2 - メモリアクセス高速化装置 - Google Patents

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明はメモリアクセス高速
化方法および装置に関し、特に主メモリとキャッシュメ
モリとの間のアクセス速度のギャップを改善してシステ
ム処理性能を向上させるメモリアクセス高速化方法およ
び装置に関する。

【０００２】

【従来の技術】近年、ＬＳＩの集積度向上および高速化
の要求の高まりにより、情報処理装置にキャッシュメモ
リを利用する技術は一般的になっている。キャッシュメ
モリの原理はアクセスのアドレスの局所性を利用して主
記憶の写しを高速かつ小容量のバッファメモリに蓄え、
疑似的に主記憶アクセス速度を向上させることにある。

【０００３】一方で、ＣＰＵのマシンクロックの高速化
に伴って、主記憶装置のアクセス遅延が相対的に大きく
見えるようになりつつあるという問題がある。つまり、
キャッシュメモリにヒットしている間は問題ないが、ひ
とたびキャッシュミスが発生するとデータ取得の遅延が
大きく、性能向上の壁になっていた。

【０００４】また、Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ
Ｃｏｍｐｕｔｉｎｇ（以下、ＨＰＣという。）領域で
は、参照するデータが離散的で、かつ主記憶全体に及ぶ
大量のデータを扱う。このような用途では、主記憶から
読み出したデータを再利用する前に、キャッシュに蓄え
られたデータが他のデータで置き換えられてしまい、ア
クセスのローカリティがあることが前提となっているキ
ャッシュメモリの効果が出にくいという問題点がある。

【０００５】上記のように従来のキャッシュメモリはい
ずれもリクエストを受け取った時点から受動的に動作す
るものであり、キャッシュミスの頻度を減らすことはで
きても無くすことは不可能であった。しかしながら、次
に発生するリクエストを予測できれば、あらかじめ主記
憶装置に対してリクエストを出しておき、キャッシュミ
スによる性能低下を隠すことが可能になる。さらに、キ
ャッシュミスが目立たなくなることにより、従来大きな
面積を占めていたキャッシュの容量を減らすことが可能
になり、マシンクロックの向上およびＬＳＩの面積縮小
にも役立つことになる。

【０００６】このような発想に基づいて従来から改善や
工夫が重ねられている。たとえば、特開平６−５１９８
２号公報では、キャッシュミス中に停止している演算処
理装置を使って、キャッシュミスアドレスから次のアク
セスアドレスを予測する技術について述べられている。

【０００７】この発明のアクセスアドレスの予測は、キ
ャッシュミス時に実行されるハンドラコードを変更する
ことによって様々なシステムに柔軟に対応できるという
利点があるものの、主記憶からデータが戻ってくる時間
内に上記ハンドラコードの実行を完了しなければ、却っ
て処理時間が長くなるいう欠点も伴わせ持つ。

【０００８】また、最近のキャッシュメモリシステムで
は、ノンブロッキングキャッシュの採用により、キャッ
シュミスによる演算処理装置の空き時間そのものを減ら
す技術が普及してきており、本発明に述べられているよ
うな演算処理装置の空き時間を必ずしも確保できないと
いう問題もある。

【０００９】また、特開平４−５２７４１号公報では、
予想されるアドレスのデータを命令により予めキャッシ
ュメモリにロードする技術が説明されている。この発明
では、プログラムによって予め必要なアドレスのデータ
ロードを指示できるので、的確にプログラムすることに
よりキャッシュミスを隠蔽することができ、無駄なキャ
ッシュロードを無くすことができる利点がある。反面、
プログラムを解析し、予想されるアドレスを明示的にキ
ャッシュロードするよう指示する必要があるので、プロ
グラムのチューニングに手間がかかるという欠点を伴わ
せ持つ。

【００１０】また、特開平３−２９２５４８号公報で
は、キャッシュミスに伴い、連続するキャッシュブロッ
クがキャッシュに登録されているかどうかを検査し、登
録されていなければ予めキャッシュにロードする技術に
ついて説明されている。この発明は、非常に単純な構造
で既存のシステムにも導入しやすい利点がある反面、キ
ャッシュミスしたブロックに連続するブロックが使用さ
れる保証が無いばかりか、追い出されたキャッシュブロ
ックにアクセスがある場合には却って性能を低下させる
恐れがある。

【００１１】

【発明が解決しようとする課題】上記のような従来のメ
モリアクセスの方式は、予想されるデータを予め主記憶
から読み出しておく点については共通だが、その実現方
法は、プログラムの書き換えを要する，副作用が大きい
等，導入にあたって困難な点が少なくない。さらに、キ
ャッシュメモリを含めたプロセッサ全体に何らかの手を
加えなければならない点が挙げられる。

【００１２】近年のＨＰＣの分野では、プロセッサから
新規にシステムを開発するよりは、既存のマイクロプロ
セッサを利用してシステムを構築する例が多くなった。
これは、マイクロプロセッサの性能が専用プロセッサに
比べて遜色が無くなったこと、コストパフォーマンスが
優れていること等によるが、ＨＰＣ分野向けにハードウ
ェアのチューニングを施すことが難しくなることも意味
している。

【００１３】本発明の目的は、上記のような点に配慮
し、プログラムの書き替えが不要で、副作用が少なく、
かつ既存のマイクロプロセッサにも応用できるようなメ
モリアクセス高速化方法および装置を提供することにあ
る。

【００１４】

【００１５】

【００１６】

【課題を解決するための手段】本発明のメモリアクセス
高速化装置は、過去のメモリアクセスのアドレス履歴を
保持する第一のバッファと、メモリアクセスの際にその
アドレスと前記第一のバッファに保持されたアドレス履
歴の一部もしくは全部との間の距離を計算する手段と、
前記第一のバッファに記憶されたアドレスとそれ以前の
一個以上のアドレスとの距離および一致回数を保持する
第二のバッファと、新たなメモリアクセスに際しそのア
ドレスと前記第一のバッファに記憶された過去のメモリ
アクセスのアドレスの一つとの距離が前記第二のバッフ
ァに保持されている過去のメモリアクセスに対応した距
離の少なくとも一つと一致する場合にはそのアクセスの
組み合わせに対応する一致回数を記憶する手段と、前記
一致回数があらかじめ定めた回数に達したときに前記距
離で連続したアクセスを発行する手段とを有して構成さ
れる。

【００１７】さらに、本発明のメモリアクセス高速化装
置において、連続してアクセスしたデータが使用されな
いときには前記連続したアクセスを停止する手段を備え
る。

【００１８】さらに、本発明のメモリアクセス高速化装
置は、連続してアクセスしたデータを一時記憶バッファ
に格納しキャッシュメモリには直接格納しないようにし
て構成される。

【００１９】さらに、本発明のメモリアクセス高速化装
置において、前記連続したアクセスの際に例外が発生し
ても前記例外を無視する手段を備える。

【００２０】すなわち、本発明は、主記憶上のデータを
等間隔でアクセスする際に、予測されるデータを予めバ
ッファに読み出す手段を提供する。主記憶上データを等
間隔でアクセスするベクトル的な処理は、科学技術演算
では頻繁に登場する。しかしながら、オペランドアクセ
スは勿論、等間隔のデータアクセスが連続して出るわけ
ではないので、様々な雑音の中から繰り返し同じ間隔で
出力されるアドレスの規則性を高精度で抽出している。

【００２１】

【発明の実施の形態】以下、本発明について図面を参照
しながら説明する。

【００２２】図１は、本発明の原理を示すブロック図で
ある。同図において、本発明によるメモリアクセス高速
化装置は、過去４つ分のメモリアクセスについて、アク
セスアドレスの規則性を調べている。レジスタＤ９，Ｅ
９，Ｆ９，Ｇ９は、請求項３の第一のバッファに相当
し、過去のメモリアクセスアドレスを記憶する。本例で
は、メモリアクセスの度に、レジスタＤ９，Ｅ９，Ｆ
９，Ｇ９がストローブされているため、常に、レジスタ
Ｄ９には１個前、レジスタＥ９には２個前のアクセスア
ドレスが格納されている。

【００２３】新たなメモリアクセスが発生すると、その
メモリアクセスのアドレスと、レジスタＤ９，Ｅ９，Ｆ
９，Ｇ９、即ち過去のメモリアクセスアドレスとの差
（距離）が、減算器Ｄ，Ｅ，Ｆ，Ｇによって計算され
る。計算結果は、請求項３の第二のバッファの一部に相
当するレジスタＤ０，Ｄ１，Ｄ２，Ｄ３に格納されると
共に、過去のメモリアクセス時に計算された距離とも比
較される。

【００２４】例えば、レジスタＤ９と今回のメモリアク
セスアドレスの距離は、レジスタＤ０，Ｄ１，Ｄ２，Ｄ
３に格納されている前々回のメモリアクセスの際に計算
された距離と比較される。一致する距離があれば、今回
と前回，前回と前々回のアクセスで等間隔にメモりアク
セスしていることになり、更に次回も同じ間隔でメモリ
をアクセスする確率が高いことが予測される。

【００２５】距離の一致が検出された場合は、一致回数
バッファのカウント値が＋１され、対応するバッファに
記憶される。図２に示す演算器−０，１，２，３がこの
機能を実現している。

【００２６】図３は演算器−０の動作を示す説明図であ
る。同図において、演算器−０には、比較器Ｃ０，Ｃ
１，Ｃ２，Ｃ３の比較結果が入力されている。メモリア
クセスアドレスの距離が一致しなかった場合には、比較
器の出力が’０’となる。この結果、演算器−０からは
値’１’が出力され、レジスタＤ４にセットされる。す
なわち、バッファに記録されている限りでは、同じメモ
リアクセスアドレスの距離でアクセスしたことは無いこ
とを意味する。

【００２７】メモリアクセスアドレスの距離が一致する
と、比較器の出力が’１’となる。例えば、比較器Ｃ０
でメモリアクセスアドレスの距離が一致すると、レジス
タＤ４にセットされた一致回数バッファのカウント値が
＋１され、結果はレジスタＤ４にセットされる。もとの
レジスタＤ４の値は、レジスタＥ４にコピーされる。

【００２８】この一致回数の値が予め定められた回数を
超えると、図示しない回路により、連続したメモリアク
セス要求が発行される。

【００２９】レジスタＤ０，Ｄ１，Ｄ２，Ｄ３の内容
は、最新のメモリアクセスアドレスの距離が格納される
のと同時に、レジスタＥ０，Ｅ１，Ｅ２，Ｅ３にコピー
される。同時に、レジスタＥ０，Ｅ１，Ｅ２，Ｅ３の値
は、レジスタＦ０，Ｆ１，Ｆ２，Ｆ３にコピーされる。
レジスタＦ０，Ｆ１，Ｆ２，Ｆ３，Ｇ０，Ｇ１，Ｇ２，
Ｇ３についても同様である。

【００３０】以上の動作により、常にレジスタＤ０，Ｄ
１，Ｄ２，Ｄ３にはレジスタＤ９に対応したメモリアク
セスアドレスの距離が常に格納されている。レジスタＥ
０，Ｅ１，Ｅ２，Ｅ３，Ｆ０，Ｆ１，Ｆ２，Ｆ３，Ｇ
０，Ｇ１，Ｇ２，Ｇ３についても同様である。

【００３１】図４（ａ）は、二次元配列の内容を累算し
て一次配列に変換する単純なプログラムの例である。プ
ログラムは２重のＤ０ループから構成されており、内周
のループでは、Ｂ（Ｊ，Ｉ）のＪが１から１０までの範
囲が累算され、Ａ（Ｉ）に代入される。

【００３２】このプログラムをアセンブリ言語に置き換
えると、図４（ｂ）のようになる。ループの最内周はＬ
ＡＢＥＬ２からＥＮＤまでであるが、この間に主記憶装
置からレジスタへのロード命令が式（１）から式（４）
までの４回出現する。式（１），式（２），式（４）
は、ループ最内周で主記憶装置上のアドレスは変化しな
いが、式（３）のアドレスは、毎回変化する。

【００３３】２次元配列の場合、主記憶上のアドレス
は、一般的に図５のようになる。すなわち、Ｂ（１，
１）に続くアドレスはＢ（１，２）になり、配列の１要
素を８Ｂｙｔｅとすると、Ｂ（２，１）はＢ（１，１）
から１０ｘ８Ｂｙｔｅ離れた場所になる。図４に示した
プログラムでは、配列Ｂ（Ｉ，Ｊ）のアクセス順序は図
５の黒色の位置になり、ループを廻る毎に８０Ｂｙｔｅ
離れたアドレスをアクセスすることになる。

【００３４】図６は最内周のループを廻る度に、図１お
よび図２のレジスタ値がどのように変化するかを示した
ものである。変数が格納されている主記憶上のアドレス
は、Ｉの主記憶上のアドレスを０番地，Ｊの主記憶上の
アドレスを８番地，Ａ（Ｉ）の開始アドレスを１００番
地，Ｂ（Ｊ，Ｉ）の開始アドレスを２００番地と仮定す
る。

【００３５】ループの１回目（図６（ａ）参照）では、
バッファに履歴が記録されていないため、特別な動作は
行わない。ループの２回目（図６（ｂ）参照）になる
と、前回のループの履歴が残っているため、１回目のル
ープとは若干動作が異なる。Ｂ（１，１）のアドレス
（２００番地）に続いて、Ａ（１）のアドレス（１００
番地）、Ｉのアドレス（０番地）が１００番地飛びでア
クセスされたため、距離−１００で３回目の連続アクセ
スがあったことが記録されている。このように、必ずし
も規則的なアクセスでなくても、アドレスのアクセス間
隔が等しくなると、等間隔のアクセスとして、バッファ
上に記録が残る。

【００３６】ループの３回目（図６（ｃ）参照）では、
ループ毎に等間隔でアクセスを繰り返しているＢ（Ｊ，
Ｉ）が、等間隔のアクセスとして、レジスタ上に記録さ
れている。１回目のループでは２００番地，２回目のル
ープでは２８０番地，３回目のループでは３６０番地
と、８０番地間隔で規則的なアクセスをしている。ルー
プの４回目（図６（ｄ）参照）になると、一致を検出し
たカウント値が３を示し、次も同じ間隔でアクセスを繰
り返すことが予測される。

【００３７】プロセッサから出力されるアドレスを監視
する限り、等距離で出るリクエストは４回に１回とな
り、単純な回路では、Ｂ（Ｉ，Ｊ）のアドレスの規則性
を見極めることは難しい。本発明のメモリアクセス高速
化方式を採用すれば、このようなケースでも、アクセス
アドレスの規則性から、次にアクセスするアドレスの規
則性を見極めることができる。

【００３８】図７は、本発明のメモリアクセス高速化方
式を採用した情報処理装置の例を示すブロック図であ
る。同図において、プロセッサ１はキャッシュメモリ２
の制御機能を内蔵しているため、外部回路によってキャ
ッシュの内容を書き換えることはできないと仮定した。
このため。アクセスの規則性をもとに、主記憶装置４か
ら先行して読み出したデータは、バッファメモリ３と呼
ばれる一時記憶装置に格納される。

【００３９】前記キャッシュメモリ２のミスが発生する
と、バッファメモリ３内に該当するデータがあるか検索
し、データがバッファメモリ内に存在する場合、主記憶
装置４からデータを読み出すことなくバッファメモリ３
からキャッシュメモリにデータを転送する。主記憶装置
からのデータ読み出しは、一般的にかなり長い時間を要
するため、予めバッファメモリにデータを読み出してお
く本方式は、高速化の効果がある。

【００４０】プロセッサ１とキャッシュメモリ２の間の
バスは、図１の回路に相当するアドレス監視回路５によ
って監視されている。監視しているアドレスに規則性が
検出されたときには、リクエスト生成回路６によって主
記憶装置４の先行読み出し要求が生成される。

【００４１】先行して読み出されたデータが一定期間使
用されない場合は、アクセス規則性の予測が外れたもの
と判断し、リクエスト中止回路７によってリクエストの
生成を中断するが、予測に基づいて主記憶装置から読み
出したデータが実際にプロセッサによって使われている
時には、引き続きリクエストの生成を継続する。

【００４２】アクセス規則性の予測に基づき、主記憶装
置に出されたリクエストが例外を発生することも考えら
れる。プロセッサからのリクエストに伴う記憶アクセス
例外であれば、プロセッサに割り込みをかけて例外処理
を行う必要があるが、アクセス規則性の予測に基づいて
主記憶装置に出力されたリクエストの場合は例外を発生
してはならない。このように、リクエスト元に応じて記
憶アクセス例外を抑止する回路がメモリ例外無効化回路
８である。

【００４３】

【発明の効果】本発明によれば、メモリアクセスのアド
レスを高精度で予測することができるので、キャッシュ
メモリに格納できないような大規模なデータを扱うプロ
グラムでも、キャッシュのヒット率の低下を気にするこ
となく、ＭＰＵの性能をフルに引き出すことができる。

【００４４】すなわち、大規模データを扱うプログラム
では、配列上のデータをある規則（距離）に従って連続
アクセスするケースが多い。連続アクセスのアクセス間
隔は、ソフトウェアを書き換えれば容易に知ることがで
きるが、市販のＭＰＵ上で動作する流通アプリケーショ
ンを移植する際、マシン固有のチューニングを施すのは
容易なことではない。ソフトウェアチューニング無し
に、同じＭＰＵを使う他社のマシンよりも高い性能が出
せれば、差別化の強力な手段となりうる。本発明は、こ
のような差別化の難しい、市販ＭＰＵを使ったシステム
で大きな効果を期待することができる。

【図面の簡単な説明】

【図１】本発明の実施の一形態を示すブロック図。

【図２】本発明の実施の一形態を示すブロック図（つづ
き）。

【図３】演算器の論理を示す説明図。

【図４】アプリケーションプログラムの例を示す説明
図。

【図５】２次元配列の処理動作を示す説明図。

【図６】本発明の動作例を示す説明図。

【図７】本発明を適用した情報処理装置の例を示すブロ
ック図。

【符号の説明】

１ プロセッサ ２ キャッシュメモリ ３ バッファメモリ ４ 主記憶装置 ５ アドレス監視回路 ６ リクエスト生成回路 ７ リクエスト中止回路 ８ メモリ例外無効化回路 Ｃ０〜Ｃ９，ＣＡ〜ＣＦ 比較器 Ｄ０〜Ｄ９，Ｅ０〜Ｅ９，Ｆ０〜Ｆ９，Ｇ０〜Ｇ９
レジスタ

───────────────────────────────────────────────────── フロントページの続き (56)参考文献 特開 平３−63852（ＪＰ，Ａ) 特開 平６−314241（ＪＰ，Ａ) 特開 昭53−134335（ＪＰ，Ａ) 特開 平４−369061（ＪＰ，Ａ) 特開 平６−51982（ＪＰ，Ａ) 特開 平８−161226（ＪＰ，Ａ) 特開 平７−64862（ＪＰ，Ａ) 特開 平６−342403（ＪＰ，Ａ) 特開 平５−181748（ＪＰ，Ａ) 特開 平８−212054（ＪＰ，Ａ) 特開 平６−28180（ＪＰ，Ａ) 特開 平３−102443（ＪＰ，Ａ) 特開 平２−18645（ＪＰ，Ａ) 特表 平７−506921（ＪＰ，Ａ) (58)調査した分野(Int.Cl.⁷，ＤＢ名) G06F 12/08 - 12/12 G06F 9/38 G06F 17/16 G06T 1/60

Claims (4)

(57)【特許請求の範囲】
1. 【請求項１】 過去のメモリアクセスのアドレス履歴を
   保持する第一のバッファと、メモリアクセスの際にその
   アドレスと前記第一のバッファに保持されたアドレス履
   歴の一部もしくは全部との間の距離を計算する手段と、
   前記第一のバッファに記憶されたアドレスとそれ以前の
   一個以上のアドレスとの距離および一致回数を保持する
   第二のバッファと、新たなメモリアクセスに際しそのア
   ドレスと前記第一のバッファに記憶された過去のメモリ
   アクセスのアドレスの一つとの距離が前記第二のバッフ
   ァに保持されている過去のメモリアクセスに対応した距
   離の少なくとも一つと一致する場合にはそのアクセスの
   組み合わせに対応する一致回数を記憶する手段と、前記
   一致回数があらかじめ定めた回数に達したときに前記距
   離で連続したアクセスを発行する手段とを有することを
   特徴とするメモリアクセス高速化装置。
2. 【請求項２】 請求項１記載のメモリアクセス高速化装
   置において、連続してアクセスしたデータが使用されな
   いときには前記連続したアクセスを停止する手段を備え
   ることを特徴とするメモリアクセス高速化装置。
3. 【請求項３】 請求項１または２記載のメモリアクセス
   高速化装置において、連続してアクセスしたデータを一
   時記憶バッファに格納しキャッシュメモリには直接格納
   しないことを特徴とするメモリアクセス高速化装置。
4. 【請求項４】 請求項１または２または３記載のメモリ
   アクセス高速化装置において、連続したアクセスの際に
   例外が発生しても前記例外を無視する手段を備えること
   を特徴とするメモリアクセス高速化装置。