(57)【要約】【課題】  入力データのヒット率に基づいてキャッシュ機能のタグアドレスのビット幅を可変に制御する。【解決手段】  キャッシュ機構によりメモリ上のルックアップテーブル（ＬＵＴ）データをキャッシュし、入力データのデータ変換を行う際に、キャッシュ機構によりキャッシュしたデータの有効性に基づいて入力データのヒット率を判定する。判定されたヒット率に基づいて、ＬＵＴの下位アドレスを分割したタグアドレスのビット幅を可変に制御する。【選択図】      図２
2008123060.tif 000002
【特許請求の範囲】
【請求項１】
キャッシュ機構によりメモリ上のルックアップテーブル（ＬＵＴ）データをキャッシュし、入力データのデータ変換を行うデータ変換装置であって、
前記キャッシュ機構によりキャッシュしたデータの有効性に基づいて前記入力データのヒット率を判定するヒット率判定手段と、
前記ＬＵＴの下位アドレスをタグアドレスとラインアドレスとに分割し、分割したタグアドレスのビット幅を可変に制御するビット幅制御手段とを有し、
前記ビット幅制御手段は、前記ビット率判定手段で判定されたヒット率に基づいて前記タグアドレスのビット幅を可変に制御することを特徴とするデータ変換装置。
【請求項２】
前記タグアドレスのビット幅は、動作開始時には最小ビット幅に設定されることを特徴とする請求項１記載のデータ変換装置。
【請求項３】
前記ビット幅制御手段は、前記ヒット率が予め決められた値以下になった場合に、前記タグアドレスのビット幅を増加させることを特徴とする請求項１又は２記載のデータ変換装置。
【請求項４】
前記ビット幅制御手段は、前記タグアドレスのビット幅を最大ビット幅まで増加させることを特徴とする請求項１乃至３の何れか一項記載のデータ変換装置。
【請求項５】
キャッシュ機構によりメモリ上のルックアップテーブル（ＬＵＴ）データをキャッシュし、入力データのデータ変換を行うデータ変換装置の制御方法であって、
前記キャッシュ機構によりキャッシュしたデータの有効性に基づいて前記入力データのヒット率を判定するヒット率判定工程と、
前記ＬＵＴの下位アドレスをタグアドレスとラインアドレスとに分割し、分割したタグアドレスのビット幅を可変に制御するビット幅制御工程とを有し、
前記ビット幅制御工程は、前記ビット率判定工程で判定されたヒット率に基づいて前記タグアドレスのビット幅を可変に制御することを特徴とするデータ変換装置の制御方法。
【請求項６】
請求項５記載のデータ変換装置の制御方法をコンピュータに実行させるためのプログラム。
【請求項７】
請求項６記載のプログラムを格納したコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ機構によりメモリ上のルックアップテーブル（ＬＵＴ）データをキャッシュしてデータ変換を行うデータ変換装置及びその制御方法に関するものである。
【背景技術】
【０００２】
近年、画像や映像を入力する入力機器として、スキャナ、ビデオカメラなどが普及している。一方、画像を出力する出力機器として、インクジェット、染料熱昇華型或いは電子写真などの方式を用いたカラープリンタやカラーディスプレイが普及している。
【０００３】
これらの入出力機器は、それぞれ固有の色空間（デバイス色空間）を有しており、入力機器で読み取ったデータを出力機器にて印刷（表示）するには、入力機器の色空間を出力機器の色空間に変換する処理（“色空間変換”と呼ぶ）が必要となる。例えば、スキャナで読み取ったＲＧＢ画像データを印刷する場合、スキャナのＲＧＢ色空間から標準ＲＧＢ色空間（例えばAdobeRGB）へ変換される。その後、プリンタの色材（インク又はトナー）の色空間であるシアン、マゼンタ、イエロー、ブラックで構成されるＣＭＹＫ色空間への変換が行われる。
【０００４】
また、同じＲＧＢ色空間でも、例えばスキャナやモニタのように、色空間の色空間特性（色再現範囲）が異なる場合には色変換が行われる。具体的には、スキャナで読み込んだ画像をモニタに表示する場合、スキャナＲＧＢ色空間からモニタＲＧＢ色空間への色変換処理（カラーマッチング）が必要になる。
【０００５】
この色変換処理の手法の一構成として、３次元ルックアップテーブル（３Ｄ−ＬＵＴ）と補間演算を組み合わせた色変換手法がある。この補間演算として、演算量及び隣接する直方体間での色の連続性、グレー軸の再現特性の良好さから四面体補間が提案されている（例えば、特許文献１及び２参照）。
【０００６】
しかしながら、３Ｄ−ＬＵＴ及び補間演算による色変換方法では、色変換の精度を向上させるため、３Ｄ−ＬＵＴの１軸当たりの格子点数（以下「グリッド数」と記す）を増加させると、ＬＵＴの容量は３次元では３乗で増加する。
【０００７】
また、色再現性を向上させるため、ＲＧＢ以外の色フィルタを追加したデジタルカメラも登場しており、この場合、ＬＵＴの容量はグリッド数の４乗となり、膨大なメモリ容量が必要となる。
【０００８】
一方、プリンタ等の出力装置においても、色再現性や階調性、粒状性を向上させるために、多数の色材（インク）を用いるものがあり、この場合のＬＵＴ容量は色材の数に比例して増加する。
【０００９】
そこで、ＬＵＴのコスト削減のため、ＬＵＴを階層化し、ＬＵＴの全データを低コストだが低速度のメモリに格納し、演算に必要な部分のみ、高速なキャッシュにロードして、コストパフォーマンスを満足する色変換方法が提案されている。
【特許文献１】特開昭53-123201号公報
【特許文献２】特開2000-22973号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかしながら、上記従来のキャッシュ機構では、キャッシュのタグアドレスのビット幅（エントリ数）が固定であるため、入力データの性質に合わせた最適化が困難であった。例えば、出力機器のプリンタでは、入力データとして、文字・線画、写真、コンピュータグラフィックス（ＣＧ）など性質の異なるオブジェクトを取り扱っている。しかし、文字・線画で使用される色数はかなり少なく、色の連続性も少ないので、タグのエントリ数を増やした方がヒット率が上がり効率が良い。
【００１１】
一方、写真、ＣＧなどでは、緩やかなグラデーション部が多く、画素間の相関性が高いので、タグのエントリ数を減らした方がキャッシュのフィル効率が上がりデータ変換効率が良い。
【００１２】
本発明は、入力データのヒット率に基づいてキャッシュ機能のタグアドレスのビット幅を可変に制御することを目的とする。
【課題を解決するための手段】
【００１３】
本発明は、キャッシュ機構によりメモリ上のルックアップテーブル（ＬＵＴ）データをキャッシュし、入力データのデータ変換を行うデータ変換装置であって、前記キャッシュ機構によりキャッシュしたデータの有効性に基づいて前記入力データのヒット率を判定するヒット率判定手段と、前記ＬＵＴの下位アドレスをタグアドレスとラインアドレスとに分割し、分割したタグアドレスのビット幅を可変に制御するビット幅制御手段とを有し、前記ビット幅制御手段は、前記ビット率判定手段で判定されたヒット率に基づいて前記タグアドレスのビット幅を可変に制御することを特徴とする。
【００１４】
また、本発明は、キャッシュ機構によりメモリ上のルックアップテーブル（ＬＵＴ）データをキャッシュし、入力データのデータ変換を行うデータ変換装置の制御方法であって、前記キャッシュ機構によりキャッシュしたデータの有効性に基づいて前記入力データのヒット率を判定するヒット率判定工程と、前記ＬＵＴの下位アドレスをタグアドレスとラインアドレスとに分割し、分割したタグアドレスのビット幅を可変に制御するビット幅制御工程とを有し、前記ビット幅制御工程は、前記ビット率判定工程で判定されたヒット率に基づいて前記タグアドレスのビット幅を可変に制御することを特徴とする。
【発明の効果】
【００１５】
本発明によれば、入力データのヒット率に基づいてキャッシュ機能のタグアドレスのビット幅を可変に制御することにより、データ変換効率を向上させることができる。
【発明を実施するための最良の形態】
【００１６】
以下、図面を参照しながら発明を実施するための最良の形態について詳細に説明する。
【００１７】
図１は、キャッシュ機構を用いたデータ変換装置の全体構成を示すブロック図である。ここでは、データとキャッシュとメモリの全体を説明する。
【００１８】
通常、ルックアップテーブル（ＬＵＴ）はメモリ１０２上に格納されており、入力データからメモリアドレス生成部１０１を通してアドレスが生成され、必要な格子点のデータが読み出される。ここで、メモリ１０２へのアクセスを軽減するため、或いは高速化するために、キャッシュ機構が採用されることが多い。
【００１９】
図１に示すように、ＬＵＴアドレス生成部１０３は、入力データからメモリ１０２上のＬＵＴアドレスを生成する。ここで、ＬＵＴアドレス生成部１０３は、ＬＵＴアドレスを各入力軸の上位ビットとして生成する。キャッシュ部１０４は、内部のタグに格納されている情報（タグ情報）に基づき、既にキャッシュメモリにデータが格納されているか否かを判断する。キャッシュメモリにデータが格納されていると判断した場合は、キャッシュメモリに格納されているデータを出力する。
【００２０】
一方、キャッシュメモリにデータが格納されていないと判断した場合は、キャッシュ部１０４からメモリアドレス生成部１０１へリクエストが出される。このリクエストにより、メモリアドレス生成部１０１は入力データに対応するメモリアドレスを生成する。このメモリアドレスによりメモリ１０２上のＬＵＴがアクセスされ、必要な格子点のデータがキャッシュ部１０４に読み出される。一方、キャッシュ部１０４は、読み出されたデータをキャッシュに格納すると共にタグ情報をタグメモリに格納する。そして、メモリ１０２より読み出されたデータを補間部１０５に出力する。
【００２１】
ここで、メモリ１０２へのメモリアドレスは、ＬＵＴアドレスにメモリ１０２のベースアドレスを加算することにより簡単に求まる。しかし、１７グリッドのＬＵＴのように、各軸の格子点数が２のべき乗でない場合には、無駄なメモリ空間を無くすために、メモリアドレスの生成に複雑な演算が必要な場合もある。
【００２２】
補間部１０５は、キャッシュ部１０４より出力された格子点データを各軸の下位ビットより加重平均し、補間したデータを出力する。
【００２３】
ヒット率判定部１０６は、キャッシュ部１０４のデータの有効性に基づいてヒット率を判定し、判定結果に従ってキャッシュメモリのタグアドレスとラインアドレスのビット幅の割り当てを変更する指示をキャッシュ部１０４に出力する。
【００２４】
図２は、図１に示すキャッシュ部１０４の構成の一例を示す図である。図２において、２０１はキャッシュメモリ、２０２はキャッシュ制御部である。また、キャッシュメモリ２０１において、２１１はビット分割部、２１２はタグメモリ、２１３は比較部、２１４はデータメモリである。
【００２５】
尚、タグメモリ２１２には、タグアドレスのビット幅（エントリ数）が最大時に必要とされる容量が確保されている。
【００２６】
ここでは、ＬＵＴアドレスのビット幅を１５ビットであるとする。また、データメモリ２１４のアドレスのビット幅をａビットとし、タグメモリ２１２のアドレスのビット幅をａ−ｂビットとする。尚、ｂはキャッシュフィルが行われる所定単位（ライン）によって決定されるビット幅である。例えば、所定単位が１６ならｂ＝４となる。
【００２７】
また、キャッシュメモリ２０１は、ここでは、ダイレクトマッピング方式のキャッシュとして動作する。従って、ビット分割部２１１にてＬＵＴアドレスはデータメモリ２１４（タグメモリ２１２）のアドレス入力とそれ以外に分割される。通常、アドレスの連続性（データのフィル効率）を考慮し、ＬＵＴアドレスの下位ビットがデータメモリ２１４のエントリ（アドレス）にマッピングされる。
【００２８】
タグメモリ２１２には、データメモリ２１４に格納されているデータに対応するＬＵＴアドレスの上位アドレスが格納されている。ここで、比較部２１３がタグメモリ２１２に格納されているＬＵＴアドレスの上位アドレスと、入力されたＬＵＴアドレスの上位アドレスとを比較する。一致した場合は、キャッシュにヒットしたと判定し、キャッシュ制御部２０２に判定信号（ＨＩＴ）を出力する。このＨＩＴにより、キャッシュ制御部２０２はデータメモリ２１４からデータを出力するように制御する。
【００２９】
一方、一致しなかった場合は、不一致の判定がキャッシュ制御部２０２に通知される。この場合、キャッシュ制御部２０２はメモリ１０２より該当アドレスのデータを読み出し、データメモリ２１４に新しいデータを格納し、タグメモリ２１２に新しい上位アドレスを格納する。
【００３０】
尚、タグメモリ２１２には、タグメモリ２１２に格納されているＬＵＴアドレスの上位アドレスが正しいか否かを示す有効ビットも格納されている。例えば、上述の比較のみでキャッシュのヒットを判定した場合、データメモリ２１４に何も格納されていなくとも、上位アドレスが偶然一致すれば、キャッシュにヒットしたと判定され、無関係なデータが出力されてしまう。これを防止するため、タグメモリ２１２に有効ビットを設け、初期化時にリセットし、正しいデータがデータメモリ２１４に格納された時に、該当アドレスの有効ビットをセットするようにする。この有効ビットをモニタすることで、タグメモリ２１２に格納されているアドレスが正しいか否かを判定することができる。
【００３１】
尚、現実には存在しない（使用しない）アドレスがある場合は、そのアドレスを初期化時にタグメモリ２１２に格納することでも、上述の誤動作は防止できる。
【００３２】
また、上述の有効ビットはタグの初期化を省略するために、タグとは別のメモリ（又はレジスタ）に構成しても良い。この場合、キャッシュの初期化は有効ビットの初期化のみで良い。
【００３３】
また、キャッシュのフィル効率を上げるために、通常は所定単位（「ライン」と呼ぶ）でキャッシュのフィルが行われる。この場合は、タグメモリ２１２のエントリ数が削減される（所定単位が１６ならｂ＝４となり下位４ビットがタグメモリ２１２のアドレス入力から削除される）。
【００３４】
次に、本実施形態におけるキャッシュ部１０４の動作を説明する。まず、プレスキャンなしの場合について説明する。
【００３５】
キャッシュ部１０４の動作開始時には、タグアドレスのビット幅を最小の構成にする。つまり、図３に示すように、タグアドレスのビット幅をａ−ｃビット、ラインアドレスのビット幅をｃビットとする。
【００３６】
尚、図４に示すように、実際にタグメモリ２１２に入力されるアドレスのビット幅は、最大構成時の（ａ−ｂ）ビットとしている。
【００３７】
また、リフィル時に、タグメモリ２１２に上位アドレスを書き込む場合、タグアドレスをインクリメントしながら同じ上位アドレスを書き込む。図５に示すように、例えばタグメモリ２１２の最大ビット数（ａ−ｂ）が８ビット、タグメモリ２１２の現在のビット数（ａ−ｃ）が５ビットの場合、タグメモリ２１２のアドレス10000011に上位アドレスｄを格納する。タグアドレスの上位５ビットが10000となる全てのメモリ領域に上位アドレスｄを書き込む。即ち、タグメモリ２１２に入力するアドレスが10000000〜10000111の間に上位アドレスｄを書き込んでいく。
【００３８】
キャッシュ制御部２０２は、キャッシュのヒット率を監視しており、ヒット率が下がり１画素当たりの平均サイクル数が所定の値以下になった場合、タグアドレスのビット幅を増加させる。例えば、キャッシュのフィルにかかるサイクル数をＦ、ヒット率をＨ、平均サイクル数の閾値をＴｈとし、以下の式１を満たさない場合、タグアドレスのビット幅を増やす。
【００３９】
F×(1-H)+1×H≦Th  （式１）
例えば、平均サイクル数を４以下に設定したい場合、閾値Ｔｈは４となり、このときのキャッシュのフィルにかかるサイクル数Ｆを５０とすると、上記式１は以下の値となり、ヒット率が約93.9％以上必要なことが分かる。
【００４０】
H≧(50-4)/(50-1)=0.938775…
尚、ヒット率の算出には、有効ビットがセットされていないアドレスは含まないものとする。これは、初期状態ではキャッシュにデータが格納されていないため、有効ビットがセットされていないアドレスもカウントしてしまうと、ヒット率が低くなってしまうためである。また、局所的な変動要因の切換タイミングを考慮し、ある程度の画素数の変換が終わった後、所定画素数単位でビット幅の切換の判定を行うのが現実的である。
【００４１】
ここで、ヒット率が上記式１を満たさなかった場合には、図６に示すように、タグアドレスのビット幅を（ａ−ｃ＋１）ビット、ラインアドレスのビット幅を（ｃ−１）ビットにする。
【００４２】
このようにしても、タグメモリ２１２に格納されている上位アドレスと、データメモリ２１４に格納されているデータとは対応が取れているので、既に書き込まれているタグを無効にする必要はない。即ち、タグアドレスの上位ビットが同じ領域に同じ上位アドレスを書き込んでいるので、タグアドレスのビット幅を変えても、その書き込まれたデータを使うことができる。
【００４３】
次に、図７に示すように、アドレス10000110に上位アドレスｅを格納する場合は、タグアドレスの上位ビットが100001となる全ての領域に上位アドレスｅを格納する。つまり、タグメモリ２１２に入力するアドレスが10000100〜10000111の間に上位アドレスｅを書き込んでいく。
【００４４】
このようにして、ヒット率が上記式１を満たすまで、タグアドレスのビット幅を増やしていく。但し、上記式１が満たされなくても、タグアドレスの入力ビット幅が（ａ−ｂ）ビット、ラインアドレスのビット幅がｂビットの場合、タグアドレスのビット幅が最大の構成になる（図８参照）。この場合は、タグアドレス、ラインアドレスの割り当ては変更しない。
【００４５】
このようにして、ヒット率が設定された閾値を超えるまで、タグアドレスのビット幅を増やし続け、ラインアドレスのビット幅を減らし続ける。上述のような操作を行うことにより、キャッシュのリフィル効率を含めたデータ変換処理全体の最適化が行われる。
【００４６】
以上、プレスキャンなしの場合を説明したが、プレスキャン有り（又は同一画像の変換）の場合には、プレスキャン時にタグアドレスのビット幅、ラインアドレスのビット幅を決定する。タグアドレスとラインアドレスのビット幅を確定した後、本スキャンの処理を行うので、処理シーケンスが簡単になる。
【００４７】
尚、本実施形態では、タグが最小エントリ数の時のラインに格納されるデータはＬＵＴ空間上で連続するデータが格納されるようになっていることが望ましい。
【００４８】
また、データメモリ２１４の容量は一定なので、データメモリ２１４のアドレス入力はタグアドレスのビット幅が変動しても変わらない。従って、タグメモリ２１２へ格納されるＬＵＴ上位アドレスのビット幅も変わらない。
【００４９】
尚、タグアドレスの上位ビットの変化の頻度が所定の値以下となった場合は、タグアドレスのビット幅を減少し、ラインアドレスのビット幅を増加するようにしても良い。この場合も格納されている上位アドレスとデータメモリ２１４に格納されているデータは対応が取れているので、既に書き込まれているタグを無効にする必要はない。
【００５０】
このように、本実施形態におけるキャッシュ制御部２０２は、ＬＵＴの下位アドレスを分割したタグアドレスのビット幅を可変に制御するビット幅制御を行うものである。
【００５１】
本発明は、上述したキャッシュ構成だけに限らず、２ウェイ・セット・アソシアティブ方式など、公知のキャッシュ構成を用いることも可能である。
【００５２】
尚、本実施形態の機能を実現するソフトウェアのプログラムコードを格納した記憶媒体を、システム或いは装置に供給し、そのシステム或いは装置のコンピュータ（ＣＰＵ若しくはＭＰＵ）が記憶媒体に格納されたプログラムコードを読出し実行する。これによっても、本発明の目的が達成されることは言うまでもない。
【００５３】
この場合、記憶媒体から読出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを格納した記憶媒体は本発明を構成することになる。
【００５４】
このプログラムコードを供給するための記憶媒体として、例えばフレキシブルディスク，ハードディスク，光ディスク，光磁気ディスク，ＣＤ−ＲＯＭ，ＣＤ−Ｒ，磁気テープ，不揮発性のメモリカード，ＲＯＭなどを用いることができる。
【００５５】
また、コンピュータが読出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、次の場合も含まれることは言うまでもない。即ち、プログラムコードの指示に基づき、コンピュータ上で稼働しているＯＳ（オペレーティングシステム）などが実際の処理の一部又は全部を行い、その処理により前述した実施形態の機能が実現される場合である。
【００５６】
更に、記憶媒体から読出されたプログラムコードがコンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書込む。その後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部又は全部を行い、その処理により前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【図面の簡単な説明】
【００５７】
【図１】キャッシュ機構を用いたデータ変換装置の全体構成を示すブロック図である。
【図２】図１に示すキャッシュ部１０４の構成の一例を示す図である。
【図３】本実施形態におけるＬＵＴアドレスの構成の一例を示す図である。
【図４】本実施形態におけるタグメモリ２１２のアドレスの構成の一例を示す図である。
【図５】本実施形態におけるタグメモリ２１２の構成の一例を示す図である。
【図６】本実施形態におけるタグアドレスのビット幅を変えた状態を示す図である。
【図７】図６に示すビット幅のタグメモリ２１２の構成の一例を示す図である。
【図８】本実施形態におけるタグメモリのビット幅を最大に変えた状態を示す図である。
【符号の説明】
【００５８】
１０１  メモリアドレス生成部
１０２  メモリ
１０３  ＬＵＴアドレス生成部
１０４  キャッシュ部
１０５  補間部
１０６  ヒット率判定部
２０１  キャッシュメモリ
２０２  キャッシュ制御部
２１１  ビット分割部
２１２  タグメモリ
２１３  比較部
２１４  データメモリ
【図１】
2008123060.tif 000003
【図２】
2008123060.tif 000004
【図３】
2008123060.tif 000005
【図４】
2008123060.tif 000006
【図５】
2008123060.tif 000007
【図６】
2008123060.tif 000008
【図７】
2008123060.tif 000009
【図８】
2008123060.tif 000010