(57)【特許請求の範囲】
【請求項１】
高速デバイスからキャッシュを介して記憶領域を有する低速デバイスにアクセスする階層記憶システムにおけるデバイスアクセス方法において、
２種のアドレス間の変換を行うアドレス変換バッファを、前記高速デバイス、前記低速デバイスおよび前記キャッシュにデータ伝達可能に接続し、
前記低速デバイスの前記記憶領域上に存在する複数のデータのサイズの合計以上の合計サイズを有する仮アドレス用エリアを前記記憶領域上に確保し、
該記憶領域上の各データ毎に、該データと同じサイズのスペースを、前記仮アドレス用エリア上の、前記キャッシュに互いに競合しないで同時に収納できる仮アドレスに割り当て、
前記仮アドレスを必要に応じてデータが格納されている前記記憶領域上のアドレスであるデータアドレスに変換することにより前記仮アドレスによる前記記憶領域上のデータへのアクセスを可能にするように、前記各仮アドレスと該仮アドレスが割り当てられた前記記憶領域上のデータのデータアドレスとを１対１に対応付けて、前記アドレス変換バッファに登録するとともに、
前記キャッシュ上に前記記憶領域上の前記複数のデータのうち全部もしくは一部のデータを前記仮アドレスが示す位置に存在するデータとして記憶せしめ、
これにより、前記アドレス変換バッファおよび前記キャッシュにおいて、前記仮アドレスを使用して検索を行って、前記記憶領域上のデータにアクセスすることを特徴とするデバイスアクセス方法。
【請求項２】
前記階層記憶システムの前記高速デバイスがＣＰＵであり、前記低速デバイスがメモリであることを特徴とする請求項１記載のデバイスアクセス方法。
【請求項３】
前記アドレス変換バッファにおける前記仮アドレスを使用した検索を、
前記仮アドレスの一部の桁の値を識別子とみなし、
前記アドレス変換バッファを前記識別子の種類の数と同じ数のエリアに分割し、
前記各エリアに対して前記識別子を割り当て、
前記仮アドレスの識別子と同じ識別子が割り当てられたエリアに、前記仮アドレスの、前記識別子として用いた桁以外の桁の値を前記データアドレスとともに登録し、
検索時に、
前記仮アドレスの前記識別子により、前記仮アドレスが登録されているエリアを識別し、
次に前記識別子として用いた桁以外の桁の値を用いて、前記識別したエリア内のみの検索を行うことにより行うことを特徴とする請求項１または２記載のデバイスアクセス方法。
【請求項４】
前記アドレス変換バッファへの前記対応付けの登録を、
登録する所定数のデータアドレスが一定の増減値をもつ列をなすとき、
前記列の端のデータアドレスと該データアドレスに対応する前記仮アドレスとを、前記増減値とともに前記アドレス変換バッファに登録し、
前記アドレス変換バッファは、前記端から２番目以降の前記データアドレスの登録に際し、
前記データアドレスを１つ前に登録されたデータアドレスを基準として前記増減値分移動した位置のアドレスとみなし、
前記仮アドレスを１つ前に登録された仮アドレスを基準として対応する前記データアドレスが示すデータのサイズ分移動した位置のアドレスとみなすことにより行うことを特徴とする請求項１から３のいずれか１項記載のデバイスアクセス方法。
【請求項５】
前記アドレス変換バッファに前記対応付けが登録された後、前記高速デバイスが前記アドレス変換バッファおよび前記キャッシュに最初にアクセスするより前に、
前記対応付けをされたデータアドレスが示す位置に存在するデータを、前記仮アドレスが示す位置に存在するデータとして前記キャッシュ上に記憶せしめることを特徴とする請求項１から４のいずれか１項記載のデバイスアクセス方法。
【請求項６】
前記アドレス変換バッファに、前記キャッシュ上のデータに関する情報を保存することを特徴とする請求項１から５いずれか１項記載のデバイスアクセス方法。
【請求項７】
前記キャッシュが、該キャッシュ上のデータが前記高速デバイスによって更新された際に、更新内容を直ちに前記記憶領域上のデータに反映するライトスルー方式で動作するものであることを特徴とする請求項１から６のいずれか１項記載のデバイスアクセス方法。
【請求項８】
前記キャッシュが、該キャッシュ上のデータが前記高速デバイスによって更新された際に、前記キャッシュ上に前記更新が行われたことを記録し、前記キャッシュ上のデータが無効化される前に、更新内容を前記記憶領域上のデータに反映するライトバック方式で動作するものであることを特徴とする請求項１から６のいずれか１項記載のデバイスアクセス方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高速デバイスからキャッシュを介して記憶領域を有する低速デバイスにアクセスする階層記憶システムに関し、特にキャッシュ上のデータの効率的な収納および検索によりデータの参照および更新処理を高速化したデバイスアクセス方法に関するものである。
【０００２】
【従来の技術】
情報処理システムにおいては、高速デバイスが何らかの記憶領域を持つ低速デバイス上のデータを参照または更新する（以下デバイスアクセス、または単にアクセスという）処理が頻繁に行われるため、このデバイスアクセスに要する時間（以下アクセス時間という）の短縮が重要な課題となっている。この課題の解決策として、記憶構造を低速デバイスと高速な一時記憶装置であるキャッシュの階層構造とし、低速デバイスに記憶されるデータの中から、アクセス頻度の高いデータのみを取り出してキャッシュに収納しておく階層記憶システムが知られている。この階層記憶システムは、低速デバイスとキャッシュ上のデータの整合性の取り方によって２つの種類に分類される。一つはキャッシュ上のデータが更新された直後に更新内容を低速デバイス上のデータに反映するライトスルー方式であり、もう一つは、キャッシュ上のデータが更新された時点では更新されたということを記録するに止め、キャッシュ上のデータが無効化される直前に更新内容を低速デバイス上のデータに反映するライトバック方式である。
【０００３】
従来、階層記憶システムでは、高速デバイスはまずキャッシュを検索し、目的のデータを発見できた場合はそのデータを使用し、目的のデータが発見できなかった場合のみ低速デバイスにアクセスする。すなわち、キャッシュ上に目的のデータを発見できる確率が高いほど、平均メモリアクセス時間が短縮されるしくみになっている。この確率は一般にヒット率と呼ばれているが、このヒット率を向上するためには、必要なデータのみをキャッシュに効率よく収納することが必要となる。
【０００４】
一般にキャッシュは複数のラインからなり、その各ラインに設けられたインデックスを用いて検索を行うようになっている。このインデックスは、データのアドレス（以下データアドレス）の一部であるインデックス部と対応しており、各データはデータアドレスのインデックス部と同じインデックスをもつラインに収納されるようになっている。このため従来のアクセス方法では、インデックス部が等しいアドレスは競合し、同時にキャッシュ上に収納することができないという問題があった。各ラインに複数のアドレスを取り込めるようにすることにより、競合が発生する確率を低くすることも可能ではあるが、ハードウェアが複雑になるため十分な高速化は期待できない。
【０００５】
【発明が解決しようとする課題】
したがって、キャッシュ上のデータの収納および検索を効率よく行うことにより、低速デバイスへの平均アクセス時間を短縮するデバイスアクセス方法の実現が要望されている。
【０００６】
本発明は上記課題に鑑みて、アドレスの変換を行うことによりデータ収納時のアドレスの競合をなくし、ハードウェアを複雑化することなくキャッシュの利用率および検索効率を向上したデバイスアクセス方法を提供することを目的とするものである。
【０００７】
【課題を解決するための手段】
この課題を解決するため、本発明によるデバイスアクセス方法は、データアドレスが互いに競合するために同時にキャッシュに収納できない複数のデータに対し、予め確保したエリア上の、競合せずに同時にキャッシュに収納できる仮アドレスを割り当てて、そのデータを仮アドレスにあるものとしてキャッシュに収納することにより競合を回避するものである。
【０００８】
すなわち本発明の方法は、高速デバイスからキャッシュを介して記憶領域を有する低速デバイスにアクセスする階層記憶システムにおけるデバイスアクセス方法において、２種のアドレス間の変換を行うアドレス変換バッファを、前記高速デバイス、前記低速デバイスおよび前記キャッシュにデータ伝達可能に接続し、前記低速デバイスの前記記憶領域上に存在する複数のデータのサイズの合計以上の合計サイズを有する仮アドレス用エリアを前記記憶領域上に確保し、該記憶領域上の各データ毎に、該データと同じサイズのスペースを、前記仮アドレス用エリア上の、前記キャッシュに互いに競合しないで同時に収納できる仮アドレスに割り当て、前記仮アドレスを必要に応じてデータが格納されている前記記憶領域上のアドレスであるデータアドレスに変換することにより前記仮アドレスによる前記記憶領域上のデータへのアクセスを可能にするように、前記各仮アドレスと該仮アドレスが割り当てられた前記記憶領域上のデータのデータアドレスとを１対１に対応付けて、前記アドレス変換バッファに登録するとともに、前記キャッシュ上に前記記憶領域上の前記複数のデータのうち全部もしくは一部のデータを前記仮アドレスが示す位置に存在するデータとして記憶せしめ、これにより、前記アドレス変換バッファおよび前記キャッシュにおいて、前記仮アドレスを使用して検索を行って、前記記憶領域上のデータにアクセスすることを特徴とするものである。
【０００９】
キャッシュを介してアクセスを行う高速デバイスと低速デバイスの関係としては、例えばＣＰＵとメモリ、ＣＰＵと入出力デバイス、メモリとハードディスク、メモリとＣＤ−ＲＯＭなどが挙げられる。さらにキャッシュからメモリへのアクセスを別のキャッシュ（２次キャッシュ）を介して行う場合も考えられる。
【００１０】
本発明の仮アドレスは、キャッシュ収納時の競合を防止するために、処理を行う間、仮に定義されるアドレスであり、仮アドレスの示す位置に実際のデータを配置する必要はない。通常キャッシュには、データアドレスとデータが収納されるが、本発明では仮アドレスとデータが収納され、そのデータは仮アドレスに存在するデータのように扱われる。すなわち実際に処理を行う際は、データアドレスではなく仮アドレスを用いる。
【００１１】
アドレス変換バッファは、仮アドレスとデータアドレスとの対応付けを登録する機能や、与えられた仮アドレスをデータアドレスに変換する変換機能などを備えているものとし、さらに本発明の効果を十分に得るためにはキャッシュと同程度またはそれ以上の速度を有することが望ましい。
【００１２】
仮アドレス用エリアを確保する方法としては、予め割り当てられる仮アドレスの範囲を規定しておく方法、処理プログラムの中で所定の大きさの変数として静的に定義する方法、またはプログラミング言語の機能を利用して動的に確保する方法などがある。前述のようにこのエリアには実際のデータは配置されないが、処理の都合上各データと同じサイズ分のスペースを割り当てておく必要がある。この際、エリアはまとまった一つのエリアである必然性はなく、キャッシュ収納時の競合が発生しないようなアドレスが確保できれば、いくつかにわけて確保してもよい。この場合は、エリアの合計サイズがデータの合計サイズより大きければよい。但し、このエリアのサイズをキャッシュのサイズよりも大きくとった場合は、対象とする全てのデータをキャッシュに収納することは不可能であるため、本発明の効果は十分には得られない。すなわちエリアの合計サイズはキャッシュのサイズと同等またはそれ以下であることが望ましい。
【００１３】
アドレス変換バッファへのアドレスの対応付けの登録は、ソフトウェアまたはハードウェアによって行われる。タイミングとしては仮アドレス用エリア確保より後で、データにアクセスする処理が行われるより前であればいつでもよい。例えば、プログラムの中で仮アドレス用エリアを確保した後に、各々のデータを仮アドレスに対応付け、それぞれアドレス変換バッファが提供するアドレス登録機能を利用して登録を行う。この場合対応づけとはアドレスの対応付けであり、データのコピーを行う必要はない。なお、登録すべき対応付けの数に比べてアドレス変換バッファが小さい場合は、行う処理を複数の処理単位に分割し、各処理単位毎にその処理で使用するデータのアドレス対応付けのみを登録することによりアドレス変換バッファを使い分けることもできる。この際、新たな対応付けでは、現在使用中の仮アドレスを再使用することになるため、キャッシュ上の仮アドレスとデータを一旦無効にする必要がある。このような場合、仮アドレスに対応するデータが現在キャッシュ上に有るか、また有る場合それは低速デバイス上のデータと一致しているかといった情報を、アドレスの対応付けとともにアドレス変換バッファに登録しておけば、キャッシュを検索することなく登録済みの対応付けに対する処理を決定することができ、新たな対応付けの登録処理を迅速に行うことができる。
【００１４】
さらに本発明では、所定の条件下で、登録作業をより高速に行う方法を提供する。すなわち、登録する所定数のデータアドレスが一定の増減値をもつ列をなすとき、列の端のデータアドレスとそのデータアドレスに対応する仮アドレスとを、増減値とともにアドレス変換バッファに登録すれば、端から２番目以降のデータアドレスの登録については、アドレス変換バッファが、データアドレスを１つ前に登録されたデータアドレスを基準として増減値分移動した位置のアドレスとみなし、仮アドレスを１つ前に登録された仮アドレスを基準として対応するデータアドレスが示すデータのサイズ分移動した位置のアドレスとみなして登録を行うようにする。これにより、登録作業が簡素化され、高速化が可能となる。
【００１５】
キャッシュ上に前記データの値を仮アドレスに存在するデータとして記憶せしめる方法としては、実際に仮アドレスがアクセスされた時点で、アドレス変換バッファによりデータアドレスを得てそのデータをアクセスされた仮アドレスとともにキャッシュ上に記憶せしめてもよいが、例えば、アドレス変換バッファへのアドレス対応付けの登録が行われた時点で、実際にそのアドレスがアクセスされる以前に上記と同じ方法で記憶せしめてもよい。前者の場合、本発明の効果が得られるのは２回目以降のアクセスとなるが、後者の場合は最初のアクセスから効果が得られる。
【００１６】
アドレス変換バッファの検索方法としては、仮アドレスの一部の桁の値をインデックスとみなし（以下インデックス部という）、アドレス変換バッファをインデックス部の種類の数と同じ数のエリアに分割し、各エリアに対してインデックスを割り当て、仮アドレスのインデックス部と同じインデックスが割り当てられたエリアに、仮アドレスの、インデックス部以外の桁の値を前記データアドレスとともに登録しておけば、検索時には、仮アドレスのインデックス部により、仮アドレスが登録されているエリアを識別し、次にインデックス部以外の桁の値を用いて、識別したエリア内のみの検索を行うだけでよい。これは、検索の手順としてはキャッシュ検索などに利用される検索手順と同じであるが、検索の対象がアドレス変換バッファの場合、データを各エリアに均等に配置することが可能であるため、データ配置が無作為に行われた場合に比べ、本検索手順の効果は大きくなる。
【００１７】
なおアドレス変換バッファの検索は、キャッシュの検索と並列に行い、キャッシュ上に仮アドレスが示すデータが存在しないことがわかった時点では、既にそのデータのデータアドレスがわかっているようにする。これにより、キャッシュ検索がヒットした場合もミスした場合も、本発明を用いないアクセス方法と同等の時間でアクセスすることができる。すなわち、
（平均アクセス時間）＝（キャッシュヒット時のアクセス時間）×（ヒット率）＋（キャッシュミス時のアクセス時間）  ×（ミス率）
とした場合、ヒット時、ミス時のアクセス時間は従来と同等のまま、ヒット率のみ向上させることになり、結果的に平均アクセス時間を短縮することが可能となる。
【００１８】
本発明によるデバイスアクセス方法は、必ずしもアクセスする全てのデータに対して用いる必要はなく、本発明を用いたいデータのみ、仮アドレスを割り当ててデータアドレスとの登録付けを行えばよい。すなわち、そのシステムの設計者が、行う処理や使用するデバイスの特性に合わせて本発明を使用するデータを決定することができるため、不当に資源が消費されるといったことがなく、無理のない高速化が実現できる。
【００１９】
また、キャッシュは従来通りライトスルー方式で動作するもの、ライトバック方式で動作するもののいずれでも用いることができる。
【００２０】
【発明の効果】
本発明によるデバイスアクセス方法によれば、データアドレスが互いに競合するために同時にキャッシュに収納できない複数のデータに対し、予め確保したエリア上の、競合せずに同時にキャッシュに収納できる仮アドレスを割り当てて、そのデータを仮アドレスにあるものとしてキャッシュに収納することによりキャッシュ上のデータの収納および検索を効率よく行ってキャッシュ検索のヒット率を高めることが可能となるので、低速デバイスへの平均アクセス時間を短縮することができる。情報処理システムにおいては、容量、コスト等の問題から処理速度の遅いデバイスを使わざるを得ないことも多く、キャッシュを最大限に活用した高速デバイスアクセス方法の実用上の効果はきわめて大きい。
【００２１】
【発明の実施の形態】
以下、本発明によるデバイスアクセス方法の実施の形態を図面にもとづいて説明する。
【００２２】
図１は、本発明によるデバイスアクセス方法の全体の構成を示す図である。図１に示すように、本実施の形態ではＣＰＵ１がキャッシュ２を介してメモり３にアクセスする階層記憶システムに、２種のアドレスの変換を行うアドレス変換バッファ４が、ＣＰＵ１、キャッシュ２およびメモリ３とデータ伝達可能に接続されている。本実施の形態では処理の高速化を図るために、伝達手段はデータバス５とアドレスバス６に分け、アドレス変換バッファはアドレスバス６に接続されているが、データバス５とアドレスバス６を物理的に同一のバスとし、アドレス変換バッファをそのバスに接続してもよい。
【００２３】
図２は図１に示したアドレス変換バッファ４の作用を示すものである。本実施の形態では、メモリ３上のデータ８のうち網掛けとなっているものについて本発明によるデバイスアクセス方法が適用されている。メモリ３上にはデータ８のうち網掛けとなっているものの合計サイズ分の仮アドレス用エリア７が確保されている。仮アドレス用エリア７を確保する方法としては、予め割り当てられる仮アドレスの範囲を規定しておく方法、処理プログラムの中で所定の大きさの変数として静的に定義する方法、またはプログラミング言語の機能を利用して動的に確保する方法などがあり、本実施の形態でも場合に応じてこれらの方法を使い分けているが、実際にデータ８へのアクセスが行われる以前に仮アドレス用エリア７が確保されていれば、いずれの方法でもよい。なお、この仮アドレス用エリア７は仮アドレスを定義するためのものであり、スペース９にデータ８はコピーされないが、プログラムの処理の都合上、例えばa[0]とC[0], a[4]とC[1]はそれぞれサイズが等しくなるように確保する必要がある。この際、C[0]のアドレスとC[1]のアドレスはキャッシュ収納時の競合が発生しないような関係にある。この場合a[0]の仮アドレスがC[0]のアドレス、a[4]の仮アドレスがC[1]のアドレスとなる。同様にC[2], C[3]のアドレスも割り当てられている。アドレス変換バッファ４には、仮アドレス用エリアに割り当てられた仮アドレス10と、実際のデータ８が存在する位置を示すデータアドレス11との対応付けが登録される。すなわち、アドレス変換バッファ４は、このようなアドレス対応付け登録機能、および与えられた仮アドレスから対応するデータアドレスを導き出す変換機能を持つ。
【００２４】
以下、このように構成されたアドレス変換バッファを備えた階層記憶システムにおける本発明のデバイスアクセス方法の各種実施の形態を説明する。
【００２５】
図３は、本発明の一実施の形態におけるキャッシュの構造を示す図である。図３に示すキャッシュ２は２つのライン12からなり、各ライン毎にvalid bit 13とdirty bit 14を持つ。valid bit 13はそのラインのデータが有効か否かを示すフラグであり、dirty bit 14は、キャッシュがライトバック方式で動作する場合に存在するもので、そのラインのデータがＣＰＵによって更新されているか否かを示すフラグである。データ８はライン単位で扱われるため通常メモリ上で隣接している複数のデータが一括して収納される。キャッシュにデータを収納する場合には、そのデータを検索するためのアドレスが一緒に収納される。このアドレスは通常はデータアドレスであるが、本発明では、仮アドレス10とデータアドレス11のいずれかが収納される。アドレスは図３に示すように、通常Tag 15、Index 16、Offset 17 の３つの部分に分けて解釈される。Index 16はライン12に対応する。例えば、図３のようにラインが２つしかないキャッシュの場合、Index 16は１ビットあればよく、１ビットで表せる２種類の値、すなわち０と１がそれぞれキャッシュのラインに対応する。Offset 17 は一括してラインに取り込まれた複数のデータ列の中のどの位置にそのデータが存在するかを示し、Tag 15はアドレスのそれ以外の部分とみなすことができ、アドレスとしてキャッシュに収納されるのはこのTag 15の部分である。このようなアドレスの解釈のもとで、キャッシュの検索は以下の手順で行われる。すなわち、検索したいアドレスのIndex 16によりラインを検索し、Tag 15の比較によりそのデータがキャッシュ上に存在するか否かを判断し、さらにそのデータが有効かどうかをvalid bit 13によって判断し、Offset 17 によってデータをみつける。なお、本実施の形態では、あるアドレスが与えられた場合、そのアドレスについてキャッシュ検索と、アドレス変換バッファ検索が同時に行われるため、図３には、アドレス変換バッファの構造についても概要を示す。この構造によれば、あるアドレスが与えられた場合、アドレス変換バッファの検索結果がヒットの場合はデータアドレス11、ミスの場合は与えられたそのままのアドレスがメモリアクセスアドレス18とみなされる。
【００２６】
このような構造を持つキャッシュおよびアドレス変換バッファを用いた場合の本発明の効果を図４に示す。ここでは、a[0]からa[7]までのアドレスが図４に示す位置に存在し、さらにその中の網掛けのデータについて仮アドレスを図４のように割り当てられている。仮アドレスを用いない従来方式でデータa[0]とa[4]が収納される場合、２つのデータのアドレスはインデックスが同じく０のため、同時にはキャッシュに収納されない。よって、a[0]収納後、a[4]へのアクセスが必要になるとa[0]はキャッシュから追い出され、a[4]がキャッシュに収納され、再びa[0]がアクセスされるとa[4]が追い出され、a[0]がキャッシュ上に収納されることになる。これに対し、本発明による方式では、データアドレスを仮アドレスに置き換えることにより、a[0]とa[4]のアドレスのインデックスが異なるものとなるため、２つのデータを同時にキャッシュに収納することが可能となる。
【００２７】
次に、上記図３により説明したキャッシュと異なり、valid bit 13とdirty bit 14をライン毎ではなくデータ毎に持つキャッシュの構造の例を図５に示す。この場合、データの移動や無効化はライン毎ではなく、データ毎に行われる。このような構造を持つキャッシュを用いた場合、本発明では図６に示すような効果が得られる。図６では、図のように配置されたデータのうち網掛けとなっているa[0], a[4], b[0][0], b[1][0]がキャッシュに収納されている。図４の場合と同様、４つのデータのアドレスはインデックスが等しいため、従来方式では、キャッシュ上には一度に一つのデータしか収納されない。ここで図４の場合は、データの無効化や移動がライン毎にしか行われないため、本発明を用いても同時に２つのデータしか収納することができないが、図５の構造を持つキャッシュの場合、データの無効化や移動がデータ毎に行えるため、一度に４つのデータを収納することができ、本発明の効果をさらに高めることができる。
【００２８】
以下、より効果の高い図５の構造を持つキャッシュを用いた実施の形態を中心に説明する。上記のように、仮アドレスを用いたアクセスを行うためには実際のアクセスが生じるより前に、アドレス変換バッファにアドレスの対応付けを登録しておく必要がある。図７、図８はこのアドレス変換バッファへのアドレス対応付け登録処理の流れを示すものである。このうち図７はキャッシュがライトスルー方式で動作するものの場合であり、図８はライトバック方式で動作するものの場合を示す。いずれの場合も、既に登録されているエントリに対して所定の処理を施してから登録を行わなければならない。
【００２９】
図７、図８いずれの場合も、始めに登録したい仮アドレスを使用してアドレス変換バッファにアクセスする。これは、同じ仮アドレスが既に登録済みか否かを確認するためであり、アドレス変換バッファの検索の結果、同じ仮アドレスが見つかった場合は、キャッシュにその仮アドレスが収納されているかどうかを確認し、収納されている場合はそのデータを無効化することにより、その仮アドレスを使用可能にする。その仮アドレスが登録されていなかった場合は、アドレス変換バッファのエントリをリプレースするという形で登録を行うが、この際、リプレースするエントリが使用されていないエントリ、すなわち無効なエントリであればそのまま登録を行うことができる。全てのエントリが有効で空きがない場合は、その中の一つを追い出す形で登録を行わなければならない。この場合、追い出すエントリについては、キャッシュにそのアドレスが収納されているかどうかを確認し、収納されている場合はそのデータを無効化しなければならない。
【００３０】
図７と図８の処理の違いは、図８のライトバックキャッシュの場合はキャッシュに収納されているデータを無効化する前にdirty bit を確認し、dirty bit が１だった場合はキャッシュデータをメモリに反映しなければならないという点である。なお、上記の処理が図３の構造を持つキャッシュを用いた実施の形態で行われる際、ライトスルー方式のキャッシュの場合の処理は、図７と同じになるが、ライトバック方式のキャッシュの場合の処理は、図９に示す処理となる。
【００３１】
次に、アドレス変換バッファへの登録が完了した状態で、データへのアクセスが行われる場合について説明する。
【００３２】
図10から図13は、図５のキャッシュを用いた場合のアクセス処理を示す。この際、図10から図12の処理図には、アドレス変換バッファへの検索に次いでキャッシュの検索が行われているように示されているが、実際のハードウェアの処理としては図３、図５に示したように、検索の対象となるアドレスがアドレス変換バッファとキャッシュに同時に渡されるため、検索は並列に行われる。
【００３３】
はじめに、図10を用いてデータの読込処理について説明する。本発明のデバイスアクセス方法を使用してアクセスを行うデータに関しては、必ずアドレス変換バッファに登録されていることが前提となるため、アドレス変換バッファの検索を行うことにより、検索を行うアドレスが仮アドレスか、あるいはデータアドレスかを識別することができる。すなわち、アドレス変換バッファの検索の結果見つからなかったアドレスは、仮アドレスではなくデータアドレスであり、通常のキャッシュと同じ動作で処理すればよいことになる。アドレス変換バッファの検索結果がヒットで、キャッシュの検索結果がヒットとなる場合には、最も高速なアクセスが実現する。アドレス変換バッファの検索結果はヒットしたが、キャッシュ検索はミスした場合については、そのアドレスは仮アドレスであるといえるので、アドレス変換バッファの変換機能によりその仮アドレスに対応するデータアドレスを得て、そのデータアドレスで再度キャッシュへのアクセスを試みる。データアドレスによる検索結果もミスとなった場合は、メモリにアクセスしてデータを読み出す。データアドレスによる検索結果がヒットとなった場合については２通りの処理がある。図10から図13に示した実施の形態はキャッシュ上に、同じデータが仮アドレスにあるデータとして収納されると同時に、従来通りデータアドレスにあるデータとして収納されることを許さない場合の処理である。この場合、仮アドレスでキャッシュを検索してミスとなったものが、データアドレスで検索してヒットとなることは、明らかに２通りの収納を許していることになるので、データアドレスで収納されているデータを無効化する（19）。しかし、２通りの収納を許す場合は、処理19においてキャッシュデータの無効化は行わない。
【００３４】
次に図11を用いてライトスルー方式で動作するキャッシュを用いた場合のデータの書込み処理について説明する。読込処理と同様、アドレス変換バッファの検索結果がミスの場合は、データアドレスとみなして通常のキャッシュと同様の処理を行う。またアドレス変換バッファの検索結果、キャッシュの検索結果ともにヒットの場合に最も高速なアクセスが実現する。この場合、まずキャッシュのデータを更新し、さらにアドレス変換バッファから読み出したデータアドレスを使用してメモリのデータを更新する。アドレス変換バッファの検索結果はヒットしたが、キャッシュ検索はミスした場合についてもデータ読込みの場合と同様、そのアドレスは仮アドレスであるといえるので、アドレス変換バッファの変換機能によりその仮アドレスに対応するデータアドレスを得て、そのデータアドレスで再度キャッシュへのアクセスを試みる。その結果ヒットした場合はキャッシュのデータを更新した後メモリのデータを更新し、ミスした場合は直接メモリのデータを更新する。
【００３５】
次に図12を用いてライトバック方式で動作するキャッシュを用いた場合のデータの書込処理について説明する。図11の処理に、ライトバック方式の動作に必要なフラグ処理が加わる。なお、同じデータが仮アドレスにあるデータとして収納されると同時に、従来通りデータアドレスにあるデータとして収納されることを許す場合は処理20が異なる。すなわち２通りの収納を許す場合は、キャッシュデータを無効化せずに、更新してもよい。
【００３６】
なお、図13は図10，図12の処理21に相当するもので、ライトバック方式で動作するキャッシュにおいて、キャッシュに新たなデータを収納する際のリプレース動作を示すものである。すなわち、リプレースしようとするキャッシュデータがメモリに反映すべきものかどうかを判断するためにdirty bit を読みとる。従来方式と異なる点は、扱うアドレスが仮アドレスか否かを判断するためにアドレス変換バッファの検索を行い、仮アドレスの場合はバッファの変換機能によりデータアドレスを得てメモリへの反映を行い、データアドレスの場合にはそのアドレスを用いてメモリへの反映を行うという点である。
【００３７】
以上が本実施の形態におけるデバイスアクセス方法の主な流れであるが、次に上記アクセス方法の中で行われている各種処理について、さらに効果的な方法を用いた例について説明する。
【００３８】
はじめに、アドレス変換バッファの検索方法について図14を用いて説明する。アドレス変換バッファの検索方法としては、登録されている仮アドレスを一つ一つ検索しても良いが、図14に示す方法では、アドレスのビットを上位と下位の２つに分け、下位のビットをバッファのラインの選択に使い、そのライン内のタグとそのアドレスのタグとを比較している。これにより、比較を行うためのハードウェアが単純化されるだけでなく処理速度も高速化する。この方法は、検索方法としては従来からキャッシュなどに用いられている方法であるが、アドレス変換バッファの検索に用いた場合、アドレスが競合が発生しないように割り当てられたものであることから、より大きな効果が得られる。
【００３９】
次にアドレス対応付けの登録方法について説明する。本実施の形態では、一定条件を満たしたアドレスの対応付けの登録をより高速に行うために、図15、図16に示す方式を用いることができる。すなわち、登録するデータアドレスが、一定の増減値を持つ列をなす場合に、図15のアドレス変換バッファ４に、仮アドレスとデータアドレスの他に、データアドレスの増減値を登録する。一定の増減値を持たないデータアドレスは増減値を０とすることにより同様に扱うことができる。これにより、最初のアドレス対応付けのみを増減値とともに登録すれば、それ以降の登録については、アドレスをその増減値を元に割り出すことにより、一つ一つ登録しなくても登録を行うことができるようになる。図16に示すように、アドレス変換バッファの検索結果がヒットで、登録されている増減値（インクリメント）が０以外の場合に、次のデータの仮アドレスを、アクセス中の仮アドレスにデータサイズを加えたものとし、次のデータのデータアドレスをアクセス中のデータのデータアドレスにインクリメントを加えたものとし、次のデータのインクリメントをアクセス中のデータのインクリメントとして次のデータの登録を行う。このような登録方法を用いた場合の効果を図17、図18にの効果を示す。図17、図18はＣ言語で書かれたプログラムの一例であり、map は一つの対応付けを登録する命令である。本登録方法を用いない場合（図17）、全ての対応付けについてmap 命令を発行することにより登録を行わなければならないが、本登録方法を用いた場合、図18に示すように最初の１つの対応付けについてのみmap 命令を発行すればよい。
【００４０】
次に、本発明の効果をさらに高めるための自動プリフェッチについて説明する。ここでプリフェッチとは、データを前もってキャッシュ上に収納しておくことをいう。通常キャッシュ上には最初からデータが収納されているわけではなく、最初にデータがアクセスされた際にそのデータがキャッシュ上に収納される。すなわち、キャッシュにヒットする可能性があるのは２回目以降のアクセスであり、１回目については、キャッシュの効果は期待できない。一旦キャッシュに収納されて、他のデータ収納のために追い出された場合も同様で、次にアクセスされるときにはキャッシュの効果は期待できない。これが、図10、図11、図12で示した例の中の、アドレス変換バッファの検索結果がヒットであったのにもかかわらず、キャッシュの検索結果がミスとなる場合に相当する。このケースが発生する確率を減らし、キャッシュヒット率を上げるために、本実施の形態では、図19に示すように新たにプリフェッチコントロールユニットを設け、アドレス変換バッファにアドレスの対応付けが登録されたら、その仮アドレスへのアクセスを待たずに、登録されたデータアドレスを用いてデータにアクセスし、登録された仮アドレスとともにキャッシュに収納するようにする。この際、プリフェッチ処理完了前にデータアクセスが行われないようにするため、図20の処理図に示すようにプリフェッチビットを設け、キャッシュアクセス前にプリフェッチビットを確認し、もし０でなければプリフェッチ処理実行中とみなし、０になるまで待つようにする。図21、図22、図23はプリフェッチ処理を追加した場合のデータの読込処理、書込処理である。仮アドレスによるキャッシュ検索結果がミスの場合に、すぐにデータアドレスによる再検索を行う代わりにプリフェッチビットを確認し、もしプリフェッチ処理が行われている最中、すなわちプリフェッチビットが１であれば、０になるまで待って仮アドレスによる再検索を行う。図22、図23も同様に、それぞれ図11、図12にプリフェッチビット判定処理22を追加している。
【００４１】
次にアドレス対応付けとともにキャッシュ情報を登録するアドレス変換バッファについて説明する。図24と図31は、アドレス変換バッファにアドレスの対応付けとともに、そのアドレスに関係のあるキャッシュデータが有効か、あるいは更新されているかといった付加情報も登録できるアドレス変換バッファである。図24と図31の異なる点は、仮アドレスにあるものとしてキャッシュに収納したデータを、同時に本来のデータアドレスにあるデータとしても収納することに関し、図24の場合はこれを許さず、図31の場合はこれを許すという点である。図31では、これを許したデータアクセスを実現するため、アドレス変換バッファへの登録情報の一つとして、データアドレスによりキャッシュに収納されているデータが有効かどうかを知るためのデータアドレスvalid bit を持つ。このようなアドレス変換バッファを用いることにより、キャッシュにアクセスすることなくキャッシュ内のデータに関する情報が得られるので、無駄な検索処理がなくなる。またこの付加情報として、valid bit を追加したことにより、キャッシュが図３に示した構造を持つものであっても、キャッシュへの書込みやメモリへの反映がデータ毎に行えるので、キャッシュの利用率を著しく高めることができる。
【００４２】
以下、このようなアドレス変換バッファを用いた場合のアクセス方法について説明する。図25から図30は図24のアドレス変換バッファの場合のアクセス処理の流れで、図25はライトスルー方式キャッシュの場合のアドレス対応付け登録処理、図26はライトバック方式キャッシュの場合のアドレス対応付け登録処理、図27はデータ読込処理、図28はライトスルー方式キャッシュの場合の書込処理、図29はライトバック方式キャッシュの場合の書込処理、図30はキャッシュデータリプレース処理を示す。キャッシュ情報をアドレス変換バッファに登録しない場合、例えば図７の対応付け登録処理では、仮アドレスによるアドレス変換バッファの検索結果がヒットである場合にキャッシュの検索を行って、無効化すべきキャッシュデータがあるかどうかを調べている。これに対し、図25のアドレス対応付け登録処理では処理23に示すようにアドレス変換バッファ内の情報を見るだけで無効化すべきキャッシュデータがあるかどうかがわかる。同様に、図32から図35は図31のアドレス変換バッファの場合のアクセス処理の流れで、図32はライトバック方式キャッシュの場合のアドレス対応付け登録処理、図33はデータ読込処理、図34はライトスルー方式キャッシュの場合の書込処理、図35はライトバック方式キャッシュの場合の書込処理を示す。これらは、図25から図30の処理にさらにデータアドレスのvalid bit の判定処理を加えたものである。
【００４３】
このように、各処理について上記のようなさらに効果的な方法を各種用いることにより、さらに高速なメモリアクセスを実現することができる。
【図面の簡単な説明】
【図１】本発明によるデバイスアクセス方法の全体の構成を示す図
【図２】本発明に使用されるアドレス変換バッファの一例の作用を示す図
【図３】本発明に使用されるキャッシュの一例の構造を示す図
【図４】図３のキャッシュを用いた場合の本発明の効果を示す図
【図５】本発明に使用されるキャッシュの他の例の構造を示す図
【図６】図５のキャッシュを用いた場合の本発明の効果を示す図
【図７】図５のキャッシュを用いた場合のアドレス変換バッファへのアドレス対応付け登録処理（ライトスルー方式キャッシュの場合）を示すフローチャート（以下、単に「．．．処理」という）
【図８】図５のキャッシュを用いた場合のアドレス変換バッファへのアドレス対応付け登録処理（ライトバック方式キャッシュの場合）
【図９】図３のキャッシュを用いた場合のアドレス変換バッファへのアドレス対応付け登録処理（ライトバック方式キャッシュの場合）
【図１０】図５のキャッシュを用いた場合のデータの読込処理
【図１１】図５のキャッシュを用いた場合のデータの書込処理（ライトスルー方式の場合）
【図１２】図５のキャッシュを用いた場合のデータの書込処理（ライトバック方式の場合）
【図１３】図５のキャッシュを用いた場合のキャッシュデータリプレース処理
【図１４】本発明に使用されるアドレス変換バッファの検索方法の説明図
【図１５】本発明に使用されるアドレス変換バッファの他の例の作用を示す図（アドレスが一定間隔の場合）
【図１６】図１５のアドレス変換バッファへのアドレス対応付け処理
【図１７】図２のアドレス変換バッファのアドレス対応付け処理
【図１８】図１５のアドレス変換バッファのアドレス対応付け処理
【図１９】プリフェッチ処理を行う場合のアドレス変換バッファの一例の作用を示す説明図
【図２０】自動プリフェッチ処理
【図２１】プリフェッチ処理を行う場合の読込処理
【図２２】プリフェッチ処理を行う場合の書込処理（ライトスルー方式の場合）
【図２３】プリフェッチ処理を行う場合の書込処理（ライトバック方式の場合）
【図２４】アドレス変換バッファの他の例の作用を示す説明図（キャッシュ情報を持つ場合）
【図２５】図２４のアドレス変換バッファを使用した場合のアドレス対応付け登録処理（ライトスルー方式キャッシュの場合）
【図２６】図２４のアドレス変換バッファを使用した場合のアドレス対応付け登録処理（ライトバック方式キャッシュの場合）
【図２７】図２４のアドレス変換バッファを用いた場合のデータの読込処理
【図２８】図２４のアドレス変換バッファを用いた場合のデータの書込処理（ライトスルー方式の場合）
【図２９】図２４のアドレス変換バッファを用いた場合のデータの書込処理（ライトバック方式の場合）
【図３０】図２４のアドレス変換バッファを用いた場合のキャッシュデータリプレース処理
【図３１】本発明に使用されるアドレス変換バッファのさらに他の例の作用を示す図（キャッシュ情報を持つ場合）
【図３２】図３１のアドレス変換バッファを使用した場合のアドレス対応付け登録処理（ライトバック方式キャッシュの場合）
【図３３】図３１のアドレス変換バッファを使用した場合のデータの読込処理
【図３４】図３１のアドレス変換バッファを使用した場合のデータの書込処理（ライトスルー方式の場合）
【図３５】図３１のアドレス変換バッファを使用した場合のデータの書込処理（ライトバック方式の場合）
【符号の説明】
１    ＣＰＵ
２    キャッシュ
３    メモリ
４    アドレス変換バッファ
５    データバス
６    アドレスバス
７    仮アドレス用エリア
８    データ
９    仮アドレスに割り当てられたスペース
１０  仮アドレス
１１  データアドレス
１２  キャッシュライン
１３  valid bit
１４  dirty bit
１５  Tag
１６  Index
１７  Offset
１８  メモリアクセスアドレス
１９  データ読込み時のキャッシュデータ無効化処理
２０  データ書込み時のキャッシュデータ無効化処理
２１  キャッシュデータリプレース処理
２２  プリフェッチビット判定処理
２３  キャッシュ情報による判定処理
【図１】
0003709586.tif 000002
【図２】
0003709586.tif 000003
【図３】
0003709586.tif 000004
【図４】
0003709586.tif 000005
【図５】
0003709586.tif 000006
【図６】
0003709586.tif 000007
【図７】
0003709586.tif 000008
【図８】
0003709586.tif 000009
【図９】
0003709586.tif 000010
【図１０】
0003709586.tif 000011
【図１１】
0003709586.tif 000012
【図１２】
0003709586.tif 000013
【図１３】
0003709586.tif 000014
【図１４】
0003709586.tif 000015
【図１５】
0003709586.tif 000016
【図１６】
0003709586.tif 000017
【図１７】
0003709586.tif 000018
【図１８】
0003709586.tif 000019
【図１９】
0003709586.tif 000020
【図２０】
0003709586.tif 000021
【図２１】
0003709586.tif 000022
【図２２】
0003709586.tif 000023
【図２３】
0003709586.tif 000024
【図２４】
0003709586.tif 000025
【図２５】
0003709586.tif 000026
【図２６】
0003709586.tif 000027
【図２７】
0003709586.tif 000028
【図２８】
0003709586.tif 000029
【図２９】
0003709586.tif 000030
【図３０】
0003709586.tif 000031
【図３１】
0003709586.tif 000032
【図３２】
0003709586.tif 000033
【図３３】
0003709586.tif 000034
【図３４】
0003709586.tif 000035
【図３５】
0003709586.tif 000036