(57)【要約】【課題】  メモリからデータを効率的に読出すための技術を提供すること。【解決手段】  第１および第２メモリを有するメモリ装置ＬＵＴアドレス生成部１０３は、入力データに対応するアドレスを生成し、キャッシュ制御部１０４は、キャッシュ部１１第２のメモリに記憶されているデータに対応するアドレスと、前記ＬＵＴアドレス生成部１０３により生成されたアドレスとを比較する。また、メモリ装置キャッシュ制御部１０４は、前記生成されたアドレスに対応するデータを、第２のメモリキャッシュ部１１から読出す。しまた、キャッシュ制御部１０４は、アドレスの比較結果に応じて、比較するアドレスのビット数を決定する。なお、メモリ装置は、生成されたアドレスに対応するデータが前記第２のメモリキャッシュ部１１に記憶されていない場合、対応するデータを、第１のメモリ１０２から読出す。【選択図】  図１
2007087372.tif 000002
【特許請求の範囲】
【請求項１】
メモリ装置であって、
第１のメモリ手段と、
第２のメモリ手段と、
入力データに対応するアドレスを生成する生成手段と、
前記第２のメモリ手段に記憶されているデータに対応するアドレスと、前記生成手段により生成されたアドレスとを比較する比較手段と、
前記生成手段により生成されたアドレスに対応するデータを、前記第２のメモリ手段から読み出す読み出し手段と、
前記比較手段による比較結果に応じて、前記比較手段が比較するアドレスのビット数を決定する決定手段とを備え、
前記読み出し手段は、前記生成手段により生成されたアドレスに対応するデータが前記第２のメモリ手段に記憶されていない場合、対応するデータを前記第１のメモリ手段から読み出すことを特徴とするメモリ装置。
【請求項２】
前記比較手段は、前記第２のメモリ手段に記憶されているデータに対応するアドレスと、前記生成手段により生成されたアドレスの上位アドレスとを比較することを特徴とする請求項１に記載のメモリ装置。
【請求項３】
前記比較手段は、前記第２のメモリ手段に記憶されているデータに対応するアドレスの上位アドレスを、当該上位アドレスに続く下位アドレスに対応して記憶する第３の記憶手段を有することを特徴とする請求項１に記載のメモリ装置。
【請求項４】
前記比較手段は、前記生成手段により生成されたアドレスのうちの、第１の所定ビット位置から第２の所定ビット位置までの範囲において、比較するアドレス以外をマスクするマスク手段を有することを特徴とする請求項３に記載のメモリ装置。
【請求項５】
前記決定手段は、前記比較手段による比較結果の比率に応じて、前記比較手段が比較するアドレスのビット数を決定することを特徴とする請求項１に記載のメモリ装置。
【請求項６】
前記決定手段は、前記比較手段が比較するアドレスの下位ビット数を決定することを特徴とする請求項１に記載のメモリ装置。
【請求項７】
第１および第２メモリを有するメモリ装置のメモリ制御方法であって、
入力データに対応するアドレスを生成する生成工程と、
前記第２のメモリに記憶されているデータに対応するアドレスと、前記生成されたアドレスとを比較する比較工程と、
前記生成されたアドレスに対応するデータを、前記第２のメモリから読み出す読み出し工程と、
前記比較結果に応じて、前記比較するアドレスのビット数を決定する決定工程とを備え、
前記読み出し工程では、前記生成されたアドレスに対応するデータが前記第２のメモリに記憶されていない場合、対応するデータを前記第１のメモリから読み出すことを特徴とするメモリ装置のメモリ制御方法。
【請求項８】
前記比較工程では、前記第２のメモリに記憶されているデータに対応するアドレスと、前記生成されたアドレスの上位アドレスとを比較することを特徴とする請求項７に記載のメモリ制御方法。
【請求項９】
前記比較工程では、前記第２のメモリに記憶されているデータに対応するアドレスの上位アドレスを、当該上位アドレスに続く下位アドレスに対応して第３のメモリに記憶する工程を備えることを特徴とする請求項７に記載のメモリ制御方法。
【請求項１０】
前記比較工程では、前記生成されたアドレスのうちの、第１の所定ビット位置から第２の所定ビット位置までの範囲において、比較するアドレス以外をマスクするマスク工程を備えることを特徴とする請求項９に記載のメモリ制御方法。
【請求項１１】
前記決定工程では、前記比較結果の比率に応じて、前記比較するアドレスのビット数を決定することを特徴とする請求項７に記載のメモリ制御方法。
【請求項１２】
前記決定工程では、前記比較するアドレスの下位ビット数を決定することを特徴とする請求項７に記載のメモリ制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ装置、およびメモリ制御方法に関するものである。
【背景技術】
【０００２】
近年、入力デバイスとしては、スキャナ、ビデオカメラなどが普及している。一方、出力デバイスとしては、インクジェット、染料熱昇華型あるいは電子写真などの方式を用いた、各種カラープリンタが普及している。これらのカラー入出力デバイスは、それぞれ固有の色空間（デバイス色空間）を有している。入力デバイスで読み取ったデータを出力デバイスにて印刷（表示）するには、入力デバイスの色空間を出力デバイスの色空間に変換する処理（“色空間変換”と呼ぶ）が必要となる。
【０００３】
例えば、スキャナで読み取ったＲＧＢ画像データを印刷する場合、先ず、スキャナのＲＧＢ色空間から標準ＲＧＢ色空間（例えばAdobe Systems社提唱のAdobeRGB）に変換する。その後、プリンタの色材（インクまたはトナー）の色空間であるシアン、マゼンタ、イエローおよびブラックで構成されるCMYK色空間への変換が行われる。
【０００４】
また、同じRGB色空間においても、例えばスキャナおよびモニタのRGB色空間など、それら色空間特性（色再現範囲）が異なる場合は色変換が行われる。具体的には、スキャナで読み込んだ画像をモニタに表示する際に、カラーマッチングのために、スキャナRGB色空間からモニタRGB色空間への変換が必要になる。
【０００５】
こうした色変換処理の手法の一構成として、３次元ルックアップテーブル(3D-LUT)と補間演算を組み合わせた色変換手法がある。その補間演算手法として、特許文献１や特許文献２等に開示された四面体補間が補間演算方法として知られている。
しかしながら、上記3D-LUT＋補間による色変換方法では、色変換の精度を向上させるために３D-LUTの１軸当たりの格子点数（以下「グリッド数」と記す）を増加させると、LUTの容量は３次元では３乗で増加する。また、色再現性向上の為にRGB以外の色フィルタを追加したデジタルカメラも登場しており、この場合、上記LUTの容量はグリッド数の４乗となり、膨大なメモリ容量が必要となる。
【０００６】
一方、プリンタ等の出力装置においても、色再現性や階調性、粒状性の改善の為、多数の色材（インク）を用いるものがあり、この場合のLUT容量は色材の数に比例して増加する。
【０００７】
そこで、上記LUTのコスト削減の為、LUTを階層化し、低コストではあるものの低速度のストレージ（メモリ）にLUTの全データを格納し、演算に必要な部分のみを高速なキャッシュにロードする色変換方法が検討されている。
【０００８】
しかしながら、このようなキャッシュ機構では、入力データの性質によって、効率が悪い場合があった。例えば、プリンタにおいては入力データとして、文字・線画、写真、グラフィックス等性質の異なるオブジェクトを取り扱う。しかし、文字・線画においては使用される色数はかなり少なく、色の連続性も少ないが、タグのエントリ数が十分にないと、ヒット率が悪く効率が悪い。一方、写真、ＣＧ等においては緩やかなグラデーション部が多く、画素間の相関性が高いが、タグのエントリ数が多いと、キャッシュのフィル効率が悪く、データ変換効率が悪い。
【特許文献１】特開昭53-123201号公報
【特許文献２】特開2000-22973号公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、メモリからデータを効率的に読出すことを目的とする。
【課題を解決するための手段】
【００１０】
本発明は、メモリ装置であって、第１のメモリ手段、第２のメモリ手段、入力データに対応するアドレスを生成する生成手段、前記第２のメモリ手段に記憶されているデータに対応するアドレスと、前記生成手段により生成されたアドレスとを比較する比較手段、前記生成手段により生成されたアドレスに対応するデータを、前記第２のメモリ手段から読出す読出し手段、前記比較手段の比較結果に応じて、前記比較手段が比較するアドレスのビット数を決定する決定手段を有し、前記読出し手段は、前記生成手段により生成されたアドレスに対応するデータが前記第２のメモリ手段に記憶されていない場合、対応するデータを、前記第１のメモリ手段から読出すメモリ装置を提供することを目的とする。
【００１１】
また、本発明は、第１および第２メモリを有するメモリ装置におけるメモリ制御方法であって、入力データに対応するアドレスを生成し、前記第２のメモリに記憶されているデータに対応するアドレスと、前記生成されたアドレスとを比較し、前記生成されたアドレスに対応するデータを、前記第２のメモリから読出し、前記比較結果に応じて、前記比較するアドレスのビット数を決定する方法であって、前記読出しステップでは、前記生成されたアドレスに対応するデータが前記第２のメモリに記憶されていない場合、対応するデータを、前記第１のメモリから読出す方法を提供することを目的とする。
【００１２】
また、本発明は、以下の実施形態の説明から明らかになるであろう。
【発明の効果】
【００１３】
本発明の構成により、メモリからデータを効率的に読出すことができ、処理パフォーマンスを向上させることができる。
【発明を実施するための最良の形態】
【００１４】
以下添付図面を参照して、本発明を好適な実施形態に従って詳細に説明する。
【００１５】
本実施形態に係るデータ処理装置（メモリ装置）は、ＬＵＴ（ルックアップテーブル）を保持している。そして更に本実施形態に係るデータ処理装置（メモリ装置）は、ＬＵＴが保持するデータ（ＬＵＴデータ）のうち、入力データに対応するＬＵＴデータを読み出し、読み出したＬＵＴデータについて所定の変換処理（補間処理）を施して外部に出力する。
【００１６】
図１は、本実施形態に係るデータ処理装置（メモリ装置）のハードウェア構成を示すブロック図である。
【００１７】
メモリ１０２には、ＬＵＴ１９９のデータが格納されている。以降では、ＬＵＴ１９９に登録されたデータを「ＬＵＴデータ」と呼称する。
【００１８】
ＬＵＴアドレス生成部１０３は、外部から入力されたデータ（Input_data）に基づいて、後述するＬＵＴアドレスを生成する。通常、ＬＵＴアドレスは、入力されたデータ（Input_data）における各入力軸（例えば、ＲＧＢ）の上位ビットにて生成される。生成したＬＵＴアドレスは後段のキャッシュ制御部１０４に送出する。
【００１９】
キャッシュ制御部１０４は、ＬＵＴアドレス生成部１０３から受けたＬＵＴアドレスで特定されるメモリ１０２（ＬＵＴ１９９）内のアドレスに保持されているデータが、既に、キャッシュ制御部１０４自身が有するキャッシュメモリ（キャッシュ部１１内のデータメモリ４）内に格納されているか否かを判断する。そして格納されていると判断した場合には、格納しているこのデータを後段の補間部１０５に送出する。
【００２０】
一方、格納されていないと判断した場合には、キャッシュ制御部１０４は、メモリアドレス生成部１０１に要求し、入力データに応じてメモリアドレス生成部１０１にて生成された、メモリ１０２内のアドレスに保持されているデータを読み出して、後段の補間部１０５に送出する。キャッシュ制御部１０４の詳細な動作については後述する。
【００２１】
通常、メモリ１０２のアドレスはLUTアドレスにメモリ１０２のベースアドレスを加算することにより簡単に求まる。しかし、１７グリッドのＬＵＴのように各軸の格子点数が２のべき乗でない場合は、無駄なメモリ空間を無くすため、メモリアドレスの生成に複雑な演算が必要な場合もある。
【００２２】
補間部１０５は、キャッシュ制御部１０４から送出されたデータを、入力データInput_dataの各軸の下位ビットより加重平均し、変換されたデータを得る。
【００２３】
ヒット率判定部１０６は、キャッシュのヒット率を判定する。ヒット率（ヒット情報）は、キャッシュのタグアドレスとラインアドレスのビット幅の割り当てを変更する為に用いられる。
【００２４】
次に、キャッシュ制御部１０４について説明する。
【００２５】
図２は、キャッシュ制御部１０４のハードウェア構成を示すブロック図である。同図に示す如く、キャッシュ制御部１０４は、キャッシュ部１１と制御部１２とで構成されている。また、キャッシュ部１１は、ビット分割部１、タグメモリ２、比較部３、データメモリ４、マスク部５により構成されている。
【００２６】
先ず、キャッシュ部１１について説明する。キャッシュ部１１は、ここではダイレクトマッピング方式のキャッシュとして動作する。
【００２７】
ビット分割部１には上述の通り、上記ＬＵＴアドレス生成部１０３により生成されたＬＵＴアドレスが入力される。図２に示す如く、このＬＵＴアドレス（ａｄｄｒｅｓｓ）は１５ビットで表現されるものとする。ビット分割部１は、この１５ビットのＬＵＴアドレスを上位アドレス［１４：ａ］と下位アドレス［ａ−１：０］とに分割する。
【００２８】
図３に示す如く、ＬＵＴアドレス［１４：０］は上位アドレス［１４：ａ］と下位アドレス［ａ−１：０］とで構成され、下位アドレス［ａ−１：０］はタグアドレスとラインアドレスとで構成されている。従って、ビット分割部１は、ＬＵＴアドレスを上位アドレス部分と、下位アドレス部分（タグアドレスとラインアドレス）とに分割する。図３は、ＬＵＴアドレスの構成例を示す図である。なお、タグアドレスのビット数は、可変である。
【００２９】
通常、アドレスの連続性（データのフィル効率）を考慮し、ＬＵＴアドレスの下位アドレスがデータメモリ４のエントリ（アドレス）にマッピングされ、このＬＵＴアドレスの上位アドレス［１４：ａ］がタグメモリ２に格納される。
【００３０】
タグメモリ２は、データメモリ４に格納されているデータに対応するＬＵＴアドレスの上位アドレス［１４：ａ］が格納されている。後述するように、タグメモリ２は、ビット分割部１から受けた上位アドレスを保持する。データメモリ４は、ビット分割部１から受けた下位アドレスと、ビット分割部１に入力されたＬＵＴアドレスで特定されるＬＵＴ１９９内のＬＵＴデータとのセットを保持する。
【００３１】
ここで、タグメモリ２のアドレスのビット幅（タグアドレスが取りうる最大ビット幅）を（ａ−ｂ）ビット、データメモリ４のアドレスのビット幅をａビットとする。
【００３２】
比較部３は、タグメモリ２から読出された、データメモリ４に記憶されているデータに対応するＬＵＴアドレスの上位アドレス［１４：ａ］と、今回ビット分割部１を介して入力されたＬＵＴアドレスの上位アドレス［１４：ａ］とを比較する。そして、タグメモリ２に蓄積されているＬＵＴアドレスの上位アドレスと、今回ビット分割部１を介して入力されたＬＵＴアドレスの上位アドレスとが一致するか否かを判断する。
【００３３】
その結果、一致すれば、比較部３は、キャッシュにヒットしたと判定し、その旨をヒット率判定部１０６に通知する。この場合、ヒット率判定部１０６はヒット率を上げる。そして、データメモリ４が保持するデータのうち、今回ビット分割部１を介して入力されたＬＵＴアドレスの下位アドレス［ａ−１：０］と対応して格納されているＬＵＴデータをデータメモリ４から読み出す。そして、比較部３は、読み出したこのＬＵＴデータを補間部１０５に出力すると共に、この判定結果を制御部１２に出力する。
【００３４】
一方、比較部３は、一致しなければ、その旨をヒット率判定部１０６に通知する。この場合、ヒット率判定部１０６はヒット率を下げる。また、一致しない旨は制御部１２にも通知する。制御部１２は、この通知を受けると、ＬＵＴ１９９が保持するＬＵＴデータのうち、今回のＬＵＴアドレスで特定されるＬＵＴデータをＬＵＴ１９９から読み出す（それをメモリアドレス生成部１０１に要求する）。そして、読み出したＬＵＴデータ（Fill data）をデータメモリ４に格納すると共に、補間部１０５に出力する。
【００３５】
なお、読み出したＬＵＴデータをデータメモリ４に格納する際には、今回ビット分割部１に入力されたＬＵＴアドレスの下位アドレス［ａ−１：０］と対応してデータメモリ４に格納すると共に、マスク部５の出力に対応してこのＬＵＴアドレスの上位アドレス［１４：ａ］をタグメモリ２に格納する。すなわち、タグメモリ２は、データメモリ４に記憶されているデータに対応するアドレスの上位アドレス［１４：ａ］を、当該上位アドレスに続く下位アドレス（タグアドレス）に対応して記憶する。
【００３６】
なお、通常はタグメモリ２に格納されているアドレスが正しいかどうかを示すダーティビットもタグメモリ２に格納されている。例えば、タグメモリ２から読み出したデータ（上位アドレス）とＬＵＴアドレスの上位アドレスとの比較のみでキャッシュのヒットを判定した場合を考える。その場合、データメモリ４に何も格納されていなくとも、タグメモリ２から読み出したデータがたまたま入力されたＬＵＴアドレスと一致してしまうと、比較部３でキャッシュにヒットしたと判定され、無関係なデータが出力されてしまう。
【００３７】
これを防止するため、タグメモリ２にダーティビット（または有効ビット）を設ける。そして、初期化時にダーティビットをセット（有効ビットをリセット）し、正しいデータがデータメモリ４に格納された時に、このアドレスのダーティビットをリセット（有効ビットをセット）するようにする。このダーティビット（有効ビット）をモニタすることで、タグメモリ２に格納されているアドレスが正しいかどうかを判定するのである。なお、現実には存在しない（使用しない）アドレスがある場合は、そのアドレスを初期化時にタグメモリ２に格納することでも、上記誤動作は防止できる。
【００３８】
なお、上記ダーティビット（有効ビット）は、タグの初期化を省略するため、タグとは別のメモリ（またはレジスタ）に構成しても良い。この場合、キャッシュの初期化はダーティビット（有効ビット）の初期化のみでよい。
【００３９】
また、キャッシュのフィル効率を上げるため、通常は所定単位（「ライン」と呼ぶ）でキャッシュのフィルが行われる。このようにフィルを行う場合は、タグメモリ２のエントリ数が削減される（所定単位が１６ならｂ＝４となり下位４ビットがタグメモリ２のアドレス入力から削除される）。すなわち、この場合、下位４ビットを除いたアドレスが一致するデータは、全て、データメモリ４に記憶されている。
【００４０】
次に、キャッシュのヒット率に応じて、ＬＵＴアドレスの下位アドレスを構成するタグアドレスとラインアドレスのそれぞれのビット幅を制御する為のヒット率判定部１０６、及びキャッシュ制御部１０４の動作について説明する。本実施形態では、プレスキャンなしの場合について説明する。
【００４１】
キャッシュ制御部１０４の動作開始時には、タグアドレスのビット幅を最小の構成にする。つまり、図３に示すように、タグアドレスのビット幅が最小の構成の場合には、タグアドレスのビット幅を（ａ−ｃ）ビット、ラインアドレスのビット幅をｃビットとする。
【００４２】
マスク部５は、ビット分割部１から受けた下位アドレス［ａ−１：０］のうち、タグメモリ２のアドレスのビット幅である（ａ−ｂ）の下位（ｃ−ｂ）ビットを０にマスクする。つまり、図４に示すように、タグメモリ２のアドレスは、タグアドレス以外は０になる。このことから、タグメモリ２は図５に示されているように、タグメモリ２のｄとｅというような部分的な（飛び飛びの）アドレスに上位アドレスを格納する。図４は、マスク部５によるマスク処理を説明する図である。図５は、タグメモリ２のメモリマップを示す図である。マスク部５は、ＬＵＴアドレスのうちの、タグメモリのアドレス（第１の所定ビット位置から第２の所定ビット位置までの範囲［ａ−１：ｂ］）において、比較するアドレス（タグアドレス）以外をマスクする。
【００４３】
ヒット率判定部１０６は、キャッシュのヒット率を監視しており、ヒット率が下がることで平均サイクル数が所定値以下になった場合、その旨をキャッシュ制御部１０４の制御部１２に通知し、タグアドレスのビット幅を増加させる。例えば、キャッシュのフィルにかかるサイクル数をＦ、ヒット率をＨ、平均サイクル数の閾値をＴｈとすると
Ｆ×（１−Ｈ）＋１×Ｈ≦Ｔｈ  （式１）
を満たさない場合、タグアドレスのビット幅を増やす。例えば、平均サイクル数を４以下に設定したい場合、Ｔｈ＝４となり、このときのキャッシュのフィルにかかるサイクル数Fを５０とすると上記（式１）は
Ｈ≧（５０−４）／（５０−１）＝０．９３８７７５・・
となり、ヒット率が約９３.９％以上必要なことが分かる。なお、上記ヒット率の算出にはダーティビットがセットされているアドレスは含まないものとする。これは、初期状態ではキャッシュにデータが格納されていないため、ダーティビットがセットされているアドレスもカウントしてしまうとヒット率が低くなってしまうためである。また、本実施例では、局所的な変動要因の切換タイミングを考慮し、ある程度の画素数の変換が終わった後、所定画素数単位でビット幅の切換の判定を行う。
【００４４】
ここで、ヒット率が上記（式１）を満たさなかった場合には、図６に示すように、タグアドレスのビット幅を（ａ−ｃ＋１）ビット、ラインアドレスのビット幅を（ｃ−１）ビットにする。図６は、タグアドレスのビット幅を変更した後のＬＵＴアドレスの構成例を示す図である。
【００４５】
つまり、マスク部５は、タグメモリ２のアドレスのビット幅である（ａ−ｂ）ビットの下位（ｃ−ｂ−１）ビットを０にマスクする。このことから、タグアドレスは１ビット増えるので、タグメモリ２に格納できるアドレス（エントリ）が増えて、図７に示すように、ｆ、ｇというアドレスに上位アドレスを格納することができる。図７は、タグアドレスのビット幅を変更した後のＬＵＴアドレスに対するタグメモリ２のメモリマップを示す図である。
【００４６】
ただし、１ビット増やした時のｆ、ｇのタグアドレス（エントリ）に対応するデータは無効である。従って、増やしたビットが１であるタグアドレス（エントリ）のダーティビットをセットする必要がある。もしくは、増やしたビット以外のアドレスが一致するアドレスで、増やしたビットが０であるタグアドレス（エントリ）に格納されている上位アドレスを、増やしたビットが１であるタグアドレス（エントリ）にコピーして、増やしたビットが１となるタグアドレス（エントリ）のダーティビットをリセットする必要がある。なお、初期状態ではダーティビットがセットされているので、そのままでも誤動作はしない。例えば、図７の例では、ｄに格納されているデータをｆ、ｅに格納されているデータをｇにコピーして、ｆ、ｇのダーティビットをリセットする。
【００４７】
このようにして、ヒット率が上記（式１）を満たすまで、タグアドレスのビット幅を増やしていく。ただし、図８に示すように、タグアドレスの入力ビット幅が（ａ−ｂ）ビット、ラインアドレスのビット幅がｂビットになったら、タグアドレスのビット幅が最大の構成になる。従って、このような場合には、上記（式１）が満たされなくても、タグアドレス、ラインアドレスの割り当ては変更しない。
【００４８】
このようにして、ヒット率が設定した閾値を超えるまで、タグアドレスのビット幅を増やし続け、ラインアドレスのビット幅を減らし続ける。このような操作を行うことにより、キャッシュのリフィル効率を含めたデータ変換処理全体の改善することができる。
【００４９】
なお、先述のように、キャッシュのリフィル単位は、ライン単位である。すなわち、キャッシュがミスヒットした場合、上位アドレス［１４：ａ］とタグアドレスが共通するデータを、メモリ１０２（ＬＵＴ１９９）から読出し、タグアドレスとラインアドレスに対応させて、データメモリ４に格納する。
【００５０】
図９は、ＬＵＴアドレス生成部１０３により１つのＬＵＴアドレスを生成した際に、キャッシュ制御部１０４、及びヒット率判定部１０６が行う処理のフローチャートである。
【００５１】
先ず、ＬＵＴアドレス生成部１０３は、入力データに対応するＬＵＴアドレス［１４：０］を生成する（ステップＳ９０１）。次に、ビット分割部１は、ＬＵＴアドレス生成部１０３により生成されたＬＵＴアドレスを上位アドレス［１４：ａ］と下位アドレス［ａ−１：０］とに分割する（ステップＳ９０２）。
【００５２】
マスク部５は、ビット分割部１から出力されたＬＵＴアドレスの下位アドレス［ａ−１：ｂ］の下位所定ビット数分（タグアドレス以外のビット）をマスクし出力する。タグメモリ２は、マスク部５の出力により指定されるアドレスのデータを出力する。比較部３は、今回ビット分割部１を介して入力されたＬＵＴアドレスの上位アドレス［１４：ａ］とタグメモリ２から出力されたデータが一致するか否かをチェックする（ステップＳ９０３）。
【００５３】
すなわち、比較部３は、データメモリ４に記憶されているデータに対応するアドレスと、ＬＵＴアドレス生成部１０３により生成されたアドレスとを比較する。ここで、タグメモリ２からは、入力されたタグアドレスに記憶されている上位アドレスが読出されるので、比較部３は、結果的には、ＬＵＴアドレスのうち、上位アドレスとタグアドレスが一致するデータが、データメモリ４に記憶されているか、判断している。
【００５４】
その結果、一致しなければ、比較部３は、キャッシュにヒットしていないと判定し、処理をステップＳ９０４に進める。そして、制御部１２は、ＬＵＴ１９９が保持するＬＵＴデータのうち、今回メモリアドレス生成部１０１により生成されたメモリアドレスで特定されるＬＵＴデータをＬＵＴ１９９から読み出す（それをメモリアドレス生成部１０１に要求する）。そして、読み出したＬＵＴデータをデータメモリ４に格納する。
【００５５】
なお、読み出したＬＵＴデータをデータメモリ４に格納する際には、今回ビット分割部１から入力されたＬＵＴアドレスの下位アドレス［ａ−１：０］と対応させてデータメモリ４に格納する。それと共に、マスク部５の出力と対応させて、このＬＵＴアドレスの上位アドレス［１４：ａ］をタグメモリ２に格納する。そして、ＬＵＴ１９９から読み出したＬＵＴデータを補間部１０５に出力する（ステップＳ９０５）。前記比較部３は、ＬＵＴアドレスに対応するデータがデータメモリ４に記憶されていない場合、対応するデータを、メモリ１０２（ＬＵＴ１９９）から読出し、補間部１０５に出力する。
【００５６】
一方、比較部３は、一致すれば、キャッシュにヒットしたと判定し、処理をステップＳ９０６に進める。そして、データメモリ４が保持するデータのうち、今回新たにビット分割部１を介して入力されたＬＵＴアドレスの下位アドレス［ａ−１：０］に対応して格納されているＬＵＴデータを読み出し、読み出したこのＬＵＴデータを補間部１０５に出力する。すなわち、比較部３は、ＬＵＴアドレスに対応するデータを、データメモリ４から読出し、補間部１０５に出力する。
【００５７】
なお、一致するものがある／ないの何れの場合にも、その旨はヒット率判定部１０６に通知され、ヒット率判定部１０６は、ヒット率を求める。
【００５８】
次に、ヒット率判定部１０６は、キャッシュのヒット率を取得する（ステップＳ９０７）。そして、ヒット率が所定値以下になった場合、制御部１２は、タグアドレスのビット幅を増加させることで、タグアドレスとラインアドレスのビット幅を決定する（ステップＳ９０９）。すなわち、制御部１２は、比較部３の比較結果に応じて、比較部３が比較するアドレスのビット数を決定する。なお、比較部３が比較するのは、上位アドレス［１４：ａ］とタグアドレスの両方について、比較を行う。
【００５９】
ここで決定したビット幅は、マスク部５にも通知され、タグアドレスにおいてマスク部分を決定する際にも用いられる。
【００６０】
以上、プレスキャンを行わないものとして説明した。プレスキャン有り（または同一画像の変換）の場合は、プレスキャン時にタグアドレスのビット幅、ラインアドレスのビット幅を決定する。そして、タグアドレスとラインアドレスのビット幅を確定した後、本スキャンの処理を行う。
【００６１】
なお、本実施形態では、タグが最小エントリ数の時のラインに格納されるデータは、ＬＵＴ空間上で連続するデータが格納されるようになっていることが望ましい。また、データメモリ４の容量は一定なので、データメモリ４のアドレス入力は上記タグアドレスのビット幅が変動しても変わらない。
【００６２】
従って、タグメモリ２へ格納されるＬＵＴアドレスの上位アドレスのビット幅も変わらない。
【００６３】
なお、マスクされているタグメモリアドレスの上位ビットの変化の頻度が所定値以下となった場合は、タグアドレスのビット幅を減らすようにしても良い。なお、減らしたビットが１となるタグアドレスに格納されているＬＵＴアドレスの上位アドレスと、減らしたビットが０となるタグアドレスに格納されているＬＵＴアドレスの上位アドレスとが異なる場合、次の処理が必要となる。即ち、減らしたビットが０となるタグアドレスのダーティビットをセットする必要がある。
【００６４】
なお、ここで説明したキャッシュ構成に拠らず、公知のキャッシュ構成（例えば２ウエイ・セット・アソシアティブ方式等）を用いても上記実施形態が成立することは自明である。
【００６５】
以上、本発明を好ましい実施形態に基づいて説明したが、本発明は、上記実施形態に限定されるものではなく、クレームの範囲内において、種々の変形が可能である。
【図面の簡単な説明】
【００６６】
【図１】本発明の第１の実施形態に係るデータ処理装置のハードウェア構成を示すブロック図である。
【図２】キャッシュ制御部１０４のハードウェア構成を示すブロック図である。
【図３】ＬＵＴアドレスの構成例を示す図である。
【図４】マスク部５によるマスク処理を説明する図である。
【図５】タグメモリ２のメモリマップを示す図である。
【図６】タグアドレスのビット幅を変更した後のＬＵＴアドレスの構成例を示す図である。
【図７】タグアドレスのビット幅を変更した後のＬＵＴアドレスに対するタグメモリ２のメモリマップを示す図である。
【図８】タグアドレスのビット幅変更処理の終了条件を説明する図である。
【図９】ＬＵＴアドレス生成部１０３により１つのＬＵＴアドレスを生成した際に、キャッシュ制御部１０４、及びヒット率判定部１０６が行う処理のフローチャートである。
【図１】
2007087372.tif 000003
【図２】
2007087372.tif 000004
【図３】
2007087372.tif 000005
【図４】
2007087372.tif 000006
【図５】
2007087372.tif 000007
【図６】
2007087372.tif 000008
【図７】
2007087372.tif 000009
【図８】
2007087372.tif 000010
【図９】
2007087372.tif 000011