(57)【要約】  【課題】  低速メモリの他に高速のキャッシュメモリを使用して処理の高速化を図ったメモリアクセス装置において、さらなる高速化を図る。  【解決手段】  低速メモリ２０から読み出したデータがアドレスと見なせるか否かをアドレス判定部５０で判定し、アドレスと見なせるときそのデータをアドレスとして先読みアドレスＦＩＦＯ６０に格納し、低速メモリ２０がアクセスされていないときに先読みアドレスＦＩＦＯ６０に格納されたアドレスにより低速メモリ２０から対応するデータを読み出してキャッシュメモリ３０に格納しておく。【選択図】  図１
2005301792.tif 000002
【特許請求の範囲】
【請求項１】
低速メモリおよび高速のキャッシュメモリのアクセス単位がプロセッサのアクセス単位よりも大きいメモリアクセス方法において、
前記低速メモリから読み出したデータがアドレスと見なせるとき、該アドレスと見なせるデータをバッファに格納し、前記低速メモリがアクセスされていないときに前記バッファに格納されたアドレスにより前記低速メモリから対応するデータを読み出して前記キャッシュメモリに予め格納しておくことを特徴とするメモリアクセス方法。
【請求項２】
請求項１に記載のメモリアクセス方法において、
前記データがアドレスと見なせるか否かの判定基準として、「奇数は有効なアドレスではない」、「あり得ないアドレスははじく」、「読み出したデータとそのときのアドレスが一定の距離にあればそれをアドレスとみなす」、「予めアドレス情報を与えておく」のいずれか１つ又は２つ以上の組合せ又はそれらを含むものを使用することを特徴とするメモリアクセス方法。
【請求項３】
プロセッサと、低速メモリと、高速のキャッシュメモリと、前記低速メモリから読み出したデータがアドレスと見なせるか否かを判定するアドレス判定部と、該アドレス判定部がアドレスと判定したときの前記低速メモリからの読み出しデータをアドレスとして格納するバッファと、前記プロセッサの読み出し指令に応じて前記低速メモリの読み出し並びに前記キャッシュメモリの読み出しおよび書き込みを制御する読出／書込制御回路とを具備し、且つ前記低速メモリおよび前記キャッシュメモリのアクセス単位が前記プロセッサのアクセス単位よりも大きいメモリアクセス装置であって、
前記バッファにアドレスとしてのデータがあり且つ前記低速メモリがアクセスされていないとき、前記バッファに格納されているアドレスにより前記低速メモリからデータを読み出して前記キャッシュメモリに書き込むことを特徴とするメモリアクセス装置。
【請求項４】
請求項３に記載のメモリアクセス装置において、
前記アドレス判定部は、アドレス判定基準として、「奇数は有効なアドレスではない」、「あり得ないアドレスははじく」、「読み出したデータとそのときのアドレスが一定の距離にあればそれをアドレスとみなす」、「予めアドレス判定部に情報を与えておく」のいずれか１つ又は２つ以上の組合せ又はそれらを含むものを使用することを特徴とするメモリアクセス装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低速メモリから読み出したデータがアドレスのように見える場合に、そのアドレスに対応するデータを低速メモリから先読みしてキャッシュメモリに格納しておくことで処理の高速化を図るメモリアクセス方法および装置に関するものである。
【背景技術】
【０００２】
半導体プロセスの進歩により、マイクロプロセッサに代表される論理回路は、高速化の一途をたどっている。論理回路と同様に記憶回路（メモリ）も高速化を続けているが、高速化に適しているスタティックメモリは高集積化（大容量化）に適さず、高密度化（大容量化）に適しているダイナミックメモリは高速化に適していない。
【０００３】
そこで、上記の様な問題を解決すべく、キャッシュメモリを用いたメモリアクセス方法が開発されている。このメモリアクセス方法は、大容量の低速メモリ（ダイナミックメモリ）と小容量の高速メモリ（スタティックメモリ）を組み合わせるもので、小容量の高速メモリはキャッシュメモリと呼ばれる。一般的に、プロセッサによるメモリアクセスにはアクセスの連続性（特に、プログラムアクセス）、アクセスの局所性（プログラムアクセス、データアクセス）がある事が知られている。これは、換言すれば、ある時点でアクセスされたメモリアドレスの近傍のアドレスは、近い将来にアクセスされる可能性が高いと言う事である。
【０００４】
これを読み出しの例で説明する。まず、メモリのアクセス単位をプロセッサが論理的に要求する単位よりも大きくしておく。プロセッサが任意のデータを読み出す際に、その近傍のデータを同時に読み出し、近傍のデータをそのアドレスとともにキャッシュメモリに一時的に格納しておく。この時、キャッシュメモリに一時的に格納されたデータは、近い将来にプロセッサがアクセスする可能性が高いと考えられるデータである。それ以降の時刻において、プロセッサが読み出しを要求したアドレスとそのデータが、そのキャッシュメモリに格納されている場合、プロセッサは低速メモリでは無くキャッシュメモリからデータを読み出す事が可能になり、その結果、プロセッサは高速に処理を行う事ができるようになる。
【０００５】
プロセッサのメモリアクセスはプログラムアクセスとデータアクセスの二種に分類することができる。一般にプログラムはメモリ上に連続的に配置されるため、前述した様なキャッシュメモリの効果は比較的大きい。また非連続的なアクセスが生じる場合でも、通常それは分岐命令であり、分岐命令をプロセッサが実行前に認識し先読みを行う事でキャッシュメモリの効果を維持する事ができる。
【０００６】
これに対して、プロセッサが読み出すデータはメモリ上にばらばらに配置されることが多く、プログラムに比較すると連続性、局所性は小さく、キャッシュメモリの効果も小さくなる傾向がある。
【０００７】
そこで、この問題を解決するために、疑似命令を使用してデータの先読みを行う方法が提案されている（例えば、特許文献１参照）。
【０００８】
【特許文献１】特開２０００−０５６９７０号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、疑似命令を使用する方法はプログラマがデータアクセスを制御する事が可能な場合に限られ、一般的なデータのランダムアクセスにおいて効果を発揮するものではない。
【００１０】
本発明の目的は、メモリ上にランダムに配置されたデータであっても、疑似命令を使用することなく、後で使用する確率が高いデータであればこれを先読みしてキャッシュメモリに格納しておくことで、処理の高速化を図ったメモリアクセス方法および装置を提供することである。
【課題を解決するための手段】
【００１１】
請求項１にかかる発明のメモリアクセス方法は、低速メモリおよび高速のキャッシュメモリのアクセス単位がプロセッサのアクセス単位よりも大きいメモリアクセス方法において、低速メモリから読み出したデータがアドレスと見なせるとき、該アドレスと見なせるデータをバッファに格納し、前記低速メモリがアクセスされていないときに前記バッファに格納されたアドレスにより前記低速メモリから対応するデータを読み出してキャッシュメモリに予め格納しておくことを特徴とする。
【００１２】
請求項２にかかる発明は、請求項１に記載のメモリアクセス方法において、前記データがアドレスと見なせるか否かの判定基準として、「奇数は有効なアドレスではない」、「あり得ないアドレスははじく」、「読み出したデータとそのときのアドレスが一定の距離にあればそれをアドレスとみなす」、「予めアドレス情報を与えておく」のいずれか１つ又は２つ以上の組合せ又はそれらを含むものを使用することを特徴とする。
【００１３】
請求項３にかかる発明のメモリアクセス装置は、プロセッサと、低速メモリと、高速のキャッシュメモリと、前記低速メモリから読み出したデータがアドレスと見なせるか否かを判定するアドレス判定部と、該アドレス判定部がアドレスと判定したときの前記低速メモリからの読み出しデータをアドレスとして格納するバッファと、前記プロセッサの読み出し指令に応じて前記低速メモリの読み出し並びに前記キャッシュメモリの読み出しおよび書き込みを制御する読出／書込制御回路とを具備し、且つ前記低速メモリおよび前記キャッシュメモリのアクセス単位が前記プロセッサのアクセス単位よりも大きいメモリアクセス装置であって、前記バッファにアドレスとしてのデータがあり且つ前記低速メモリがアクセスされていないとき、前記バッファに格納されているアドレスにより前記低速メモリからデータを読み出して前記キャッシュメモリに書き込むことを特徴とする。
【００１４】
請求項４にかかる発明は、請求項３に記載のメモリアクセス装置において、前記アドレス判定部は、アドレス判定基準として、「奇数は有効なアドレスではない」、「あり得ないアドレスははじく」、「読み出したデータとそのときのアドレスが一定の距離にあればそれをアドレスとみなす」、「予めアドレス判定部に情報を与えておく」のいずれか１つ又は２つ以上の組合せ又はそれらを含むものを使用することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、低速メモリから読み出したデータがアドレスと見なせるとき、そのデータを一時格納して低速メモリがアクセスされていないときにそのアドレスに対応するデータを読み出してキャッシュメモリに予め格納するので、ランダムデータの先読みを実現でき、プロセッサの処理を高速化する事ができる。
【発明を実施するための最良の形態】
【００１６】
本発明では、低速メモリから読み出したデータがアドレスの様に見える場合、そのデータをアドレスとみなして、低速メモリが他からアクセスされていないときに、そのアドレスに応じたデータを低速メモリから先読みしキャッシュメモリに格納する。データがアドレスに見えるか否かの判定は、アドレス判定部で行い、その判定基準は「奇数は有効なアドレスではない」、「あり得ないアドレスははじく」、「読み出したデータとそのときのアドレスが一定の距離にあればそれをアドレスとみなす」、「予めアドレス判定部に情報を与える」のいずれか１つ又は２つ以上の組合せ又はそれらを含むものとする。
【実施例】
【００１７】
図１に本発明の１つの実施例のメモリアクセス装置の構成を示す。ここでは、読み出し動作について説明するために、通常、プロセッサやメモリが持つ制御の一部は割愛している。１０はプロセッサ、２０はダイナミックメモリからなる低速メモリ、３０はスタティックメモリからなるキャッシュメモリ、４０は読出／書込制御回路、５０はアドレス判定部、６０はバッファとしての先読みアドレスＦＩＦＯ、７０，８０はセレクタである。
【００１８】
プロセッサ１０は、アドレス端子１１、読み出しや書き込み制御のためのＲ／Ｗ制御端子１２、データ入力端子１３等を具備し、Ｒ／Ｗ制御端子１２を読み出しモードに設定してアドレス端子１１からアドレスを出力してデータ入力端子１３にデータを取り込む。
【００１９】
低速メモリ２０は、アドレス端子２１、読み出しや書き込み制御のためのＲ／Ｗ制御端子２２、データ出力端子２３等を具備し、Ｒ／Ｗ制御端子２２を読み出しモードに設定してアドレス端子２１からアドレスを入力すると、データ出力端子２３からデータを出力する。
【００２０】
読出／書込制御回路４０は、プロセッサ１０、キャッシュメモリ３０、先読みアドレスＦＩＦＯ６０の状態に基づき、セレクタ７０，８０の切替制御、低速メモリ２０とキャッシュメモリ３０の書き込みや読み出しの制御を行う。具体的な制御については後述する。
【００２１】
キャッシュメモリ３０は、一度読み出したデータや命令を一時保持する高速メモリであり、通常の読み出し／書き込みに加え、アドレスで示されたデータの有無を「cache hit」として出力する機能を持つ。
【００２２】
アドレス判定部５０は本発明の特徴たる構成要素であり、低速メモリ２０から読み出したデータがアドレスであるか否かを判定し、アドレスであると判定した場合にそのアドレスを書き込む書込信号（write）を先読みアドレスＦＩＦＯ６０に出力する。
【００２３】
先読みアドレスＦＩＦＯ６０は、通常のＦＩＦＯメモリであり、アドレス判定部５０で判定された先読みすべきアドレスを保持する。先読みアドレスＦＩＦＯ６０内に先読みアドレスが存在する場合は、「データ有り」の信号を読出／書込制御回路４０に出力する。
【００２４】
次に、読出／書込制御回路４０の動作について説明する。図２はプロセッサ１０が読出モードのときの読出／書込制御回路４０の動作１のフローチャートである。まず、読出／書込制御回路４０はキャッシュメモリ３０を調査して、当該読み出すべきデータがそのキャッシュメモリ３０にある場合は、そのキャッシュメモリ３０から「cache hit」が出力するので、これを受信するとセレクタ８０をキャッシュメモリ３０側に切り替えてから、そのキャッシュメモリ３０からデータを読み出し、プロセッサ１０に出力させる。当該読み出すべきデータがそのキャッシュメモリ３０にない場合は、そのキャッシュメモリ３０から「cache hit」が出力しないので、セレクタ７０，８０を低速メモリ２０側に切り替えてから、その低速メモリ２０からデータを読み出し、プロセッサ１０に出力するとともに、その読み出したデータをキャッシュメモリ３０に登録し、次回からはキャッシュメモリ３０から読み出せるようにする。
【００２５】
図３は先読みアドレスＦＩＦＯ６０にデータ（アドレスと見なしたデータ）があるときの読出／書込制御回路４０の動作２のフローチャートである。このときは、先読みアドレスＦＩＦＯ６０にデータがあり且つプロセッサ１０が低速メモリ２０とやりとり（アクセス）を行っていない場合に、その低速メモリ２０から当該アドレスのデータを読み出しキャッシュメモリ３０に登録する。
【００２６】
以上の図２で示す動作と図３で示す動作は、同時に行う事が可能である。従って、プロセッサ１０がメモリアクセスをしていない期間はもちろん、プロセッサ１０がメモリアクセスを行っている場合でもキャッシュメモリ３０内のデータを読み出す場合においては低速メモリ２０を使用していないので、先読みアドレスＦＩＦＯ６０に格納されたアドレスに従って低速メモリ２０からのデータ読み出しとキャッシュメモリ２０への格納を行う事ができる。
【００２７】
ここで、低速メモリ２０、キャッシュメモリ３０のアクセス単位はプロセッサ１０のアクセス単位より大きく、プロセッサ１０の１ワードに対して４ワードでアクセスする事ができるものとする。
【００２８】
図４は、ある時点における低速メモリ２０内のデータ構造を示したものである。ここに示したのは一般的な線型リスト構造である。線型リストの各要素は４ワードから構成され、第１ワード（＋０）にはｋｅｙデータが、第２ワード（＋１）には次の要素のアドレスが、第３ワード（＋２）以降にはその他のデータが格納されている。ここで、ｋｅｙ１，ｋｅｙ２，ｄａｔａ１，ｄａｔａ２，ｄａｔａ３，ｄａｔａ４，・・・はアドレスとみなす事ができないようなデータであるとする。
【００２９】
このデータを処理するプログラムは図５の様に動作する。図４のデータに対し図５のプログラムを動作させたときの図１の回路の動作を図６のタイムチャートを参照しながら説明する。ただし、低速メモリ２０の読み出しレイテンシは数単位時間（数クロック時間）、キャッシュメモリ３０のレイテンシは１単位時間（１クロック時間）とする。また、キャッシュメモリ３０、先読みアドレスＦＩＦＯ６０は空であるとする。
【００３０】
ｔ＝ｔｏにおいて、プロセッサ１０はアドレスｐの読み出しを指示する。キャッシュメモリ３０は空なので読出／書込制御回路４０は低速メモリ２０からデータを読み出す。前述した様に低速メモリ２０からは４ワード単位で読み出し、アドレスｐのデータｋｅｙ１はプロセッサ１０に入力され、アドレスｐ，ｐ＋１，ｐ＋２，Ｐ＋３のデータｋｅｙ１，ｑ，ｄａｔａ１，ｄａｔａ２はキャッシュメモリ３０に格納される。
【００３１】
アドレスｐ，ｐ＋１，ｐ＋２，Ｐ＋３から読み出されたデータｋｅｙ１，ｑ，ｄａｔａ１，ｄａｔａ２はアドレス判定部５０に入力され、アドレスとみなせるかどうかの判定が行われる。この例ではｑをアドレスとみなす事ができるため、先読みアドレスＦＩＦＯ６０にｑが格納される。
【００３２】
ｔ＝ｔａにおいて、プロセッサ１０はアドレスｐ＋１の読み出しを指示する。この時アドレスｐ＋１のデータｑはキャッシュメモリ３０に格納されているので、読出／書込制御回路４０は低速メモリ２０にアクセスする事なく、キャッシュメモリ３０からデータｑをプロセッサ１０に出力する。
【００３３】
また、この時、低速メモリ２０がアクセスされておらず、先読みアドレスＦＩＦＯ６０はｑを格納しているので、読出／書込制御回路４０は低速メモリ２０からアドレスｑ，ｑ＋１，ｑ＋２，ｑ＋３のデータｋｅｙ２，ｑ２，ｄａｔａ３，ｄａｔａ４の読み出しを開始する。この読み出しはｔ＝ｔａ＋１において完了する。
【００３４】
ｔ＝ｔａ＋１，ｔ＝ｔａ＋２と時間が経過すると、プロセッサはデータｄａｔａ１，ｄａｔａ２を順次読み出すが、キャッシュメモリ３０にデータがあるためそれらは全て１単位時間で読み出しが完了する。ここまでにかかる時間は、従来技術と同様である。時刻ｔ＝ｔｂ以降、本発明の効果があらわれる。
【００３５】
ｔ＝ｔｂにおいてプロセッサ１０は次の要素を処理すべくアドレスｑの読み出しを行う。前記したようにアドレスｑの内容は時刻ｔ＝ｔａにおいてキャッシュメモリ３０に格納ずみであるので、１単位時間で読み出しが完了する。ｔ＝ｔｂ＋１以降も同様である。
【００３６】
本発明を実施していなければ、アドレスｐからのアクセスの後にアドレスｑからのアクセスが生じることは知ることが出来ず、図７のタイムチャートに示すように、アドレスｑのデータ読み出しには低速メモリ２０の読み出しレイテンシ時間が必要であるが、本発明を実施することで、上述した様に低速メモリ２０のアクセスにかかる時間を隠蔽し、プロセッサ１０が高速に動作する事を達成できる。
【００３７】
続いてアドレス判定部５０の判定方法の例を述べる。その第１の判定基準は「奇数は有効なアドレスでは無い」というものである。説明を容易にするため図１乃至図５の説明では単純化したが、一般のプロセッサでは奇数アドレスよりのデータ読み出しを行わない。多くのプロセッサでは４の倍数のアドレスを利用する。従って、読み出したアドレスが４の倍数でなければそれはアドレスではありえない。それ以外の場合においてアドレスであると判定すれば良い。
【００３８】
第２の判定基準は「あり得ないアドレスははじく」というものである。プロセッサ１０が処理する事ができるデータ幅に対し、実際に塔載される低速メモリ２０の容量は小さい場合が多い。たとえばプロセッサ１０が３２ビットでアドレッシング可能であっても塔載する低速メモリ２０の総量が２０ビットであれば、アドレスの上位１２ビットは必ず０になる。この様な場合、データの上位１２ビットが０か否かでアドレスかどうかの判定が可能である。
【００３９】
第３の判定基準は「読み出したデータとそのときのアドレスが一定の距離にあれば、そこをアドレスとみなす」というものである。読み出したアドレスと読み出したデータの差が小さい、すなわちデータをアドレスと見なした場合の距離が小さい場合は、そのデータはアドレスとして使われる可能性が高いと考えることができるので、アドレスとして判定できる。
【００４０】
第４の判定基準は「予めアドレス判定部に情報を与える」というものである。アドレス判定部５０にレジスタを設け、そのレジスタにとりうるアドレスの範囲を設定し、読み出したデータがアドレスの範囲と一致したら、アドレスとして判定する。
【００４１】
以上の第１〜第４の判定基準はその２以上を組み合わせることで、より正確な判定が可能となる。もちろんこれら以外のアドレス判定基準を使用しても構わない。本発明を実施する際は、その実施対象の装置の特性に合わせてアドレス判定部５０を構成すれば良い。
【図面の簡単な説明】
【００４２】
【図１】本発明の実施例のメモリアクセス装置のブロック図である。
【図２】読出／書込制御回路の動作１のフローチャートである。
【図３】読出／書込制御回路の動作２のフローチャートである。
【図４】低速メモリに格納したデータ構造の例の説明図である。
【図５】図４のデータを処理するプログラムの説明図である。
【図６】図５のプログラムを本実施例で処理するときのタイムチャートである。
【図７】図５のプログラムを従来方法で処理するときのタイムチャートである。
【符号の説明】
【００４３】
１０：プロセッサ、１１：アドレス端子、１２：Ｒ／Ｗ制御端子、１３：データ入力端子
２０：低速メモリ、２１：アドレス端子、２２：Ｒ／Ｗ制御端子、２３：データ出力端子
３０：キャッシュメモリ
４０：読出／書込制御回路
５０：アドレス判定部
６０：先読みアドレスＦＩＦＯ
７０，８０：セレクタ
【図１】
2005301792.tif 000003
【図２】
2005301792.tif 000004
【図３】
2005301792.tif 000005
【図４】
2005301792.tif 000006
【図５】
2005301792.tif 000007
【図６】
2005301792.tif 000008
【図７】
2005301792.tif 000009