(57)【特許請求の範囲】
【請求項１】
処理対象の画像を記憶するメモリと該画像をアクセス可能な演算装置との間に前記画像の一部を記憶するキャッシュメモリを有する画像処理装置において、画像のプリフェッチを行った時に該プリフェッチの効果を算出するプリフェッチ効果算出手段と、前記プリフェッチ効果算出手段で算出されたプリフェッチの効果が有効であると判断された時のみ画像のプリフェッチを行うキャッシュ制御手段を有し、前記キャッシュメモリは、キャッシュ・エントリがプリフェッチによってフェッチされたものか否かを記録するプリフェッチ・フラグをキャッシュ・タグとして有しおり、前記プリフェッチ効果算出手段は、選択されたキャッシュ・エントリに対応する前記プリフェッチ・フラグがプリフェッチによってフェッチされたものであることを示しているとき、プリフェッチされたキャッシュ・データがその後キャッシュ・ヒットしたかキャッシュ・ミスしたかを計数し、その差を予め設定しておいた閾値と比較することによりプリフェッチの効果を判断することを特徴とする画像処理装置。
【請求項２】
さらに画像のプリフェッチを行うか否かを指定する画像プリフェッチ指定手段を有し、前記キャッシュ制御手段は、前記画像プリフェッチ指定手段により画像のプリフェッチが指定されかつ前記プリフェッチ効果算出手段で算出されたプリフェッチの効果が有効であると判断された時のみ画像のプリフェッチを行うことを特徴とする請求項１に記載の画像処理装置。
【請求項３】
さらに、画像のプリフェッチを行うか否かを指定する画像プリフェッチ指定手段と、複数のプリフェッチ先アドレスの中から１つを選択するプリフェッチ方式指定手段を有し、前記キャッシュ制御手段は、前記画像プリフェッチ指定手段により画像のプリフェッチが指定された時は前記プリフェッチ方式指定手段により指定されたプリフェッチ先アドレスを用いて画像のプリフェッチを行うことを特徴とする請求項１または請求項２に記載の画像処理装置。
【請求項４】
さらに、前記画像の水平方向の画素幅を記憶する画像幅指定手段を有し、前記プリフェッチ方式指定手段は、前記画像プリフェッチ指定手段により画像のプリフェッチが指定された時に、プリフェッチ先アドレスとして、前記演算装置が最後にアクセスしたメモリアドレスに前記キャッシュメモリのラインサイズを加算したアドレスか、前記演算装置が最後にアクセスしたメモリアドレスに前記画像幅指定手段が示す値を加算したアドレスのいずれかを指定することを特徴とする請求項３に記載の画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理において画像データの読み込みに関して、メモリアクセスを高速化かつ最適化するキャッシュ制御手段を備えた画像処理装置、及びそのような画像処理装置に用いて好適なキャッシュメモリに関するものである。
【０００２】
【従来の技術】
近年、マルチメディア技術の発展により計算機が扱わなければならないデータ量が飛躍的に伸びており、特に画像においては高解像度で高速な処理が要求されている。画像データはそのデータ量が膨大なために、旧来は補助記憶から画像の一部を主記憶に転送してから処理を行っていたが、近年の主記憶の容量の増大により画像データを主記憶に配置して処理することが一般的となっている。
【０００３】
一方、キャッシュシステムとは、小容量ながら主記憶に比べて高速なメモリ（これをキャッシュメモリと呼ぶ）を演算装置と主記憶との間に配置し、マイクロプロセッサ等の演算装置のメモリアクセスの局所性を利用してメモリアクセスを高速化するシステムである。ここで演算装置のメモリアクセスの局所性とは、ある時間に参照されたデータならびにそのデータの近傍のデータが近い時間に参照される確率が高いことである。この性質を利用し、一度主記憶にアクセスした時に、アクセスしたデータならびにその近傍のデータをキャッシュメモリにもコピーしておく。そうすれば、次にそのデータをアクセスする時に、そのデータがキャッシュメモリに存在していれば、アクセス時間の遅い主記憶にアクセスせずに、アクセス時間の速いキャッシュメモリにアクセスできる。そのため、結果としてメモリアクセスが高速化される。ここで、必要とするデータがキャッシュメモリに存在することをキャッシュ・ヒットと呼び、必要とするデータがキャッシュメモリに存在しないことをキャッシュ・ミスあるいはキャッシュ・ミスヒットと呼ぶ。また、キャッシュ・ヒットする確率をキャッシュ・ヒット率あるいは単にヒット率と言い、ヒット率が高いほど主記憶にアクセスする必要がないのでメモリアクセスが高速化される。
【０００４】
ところで、画像処理、特にプリンタなどへの出力を目的とする画像処理では、ラスタスキャン順の処理やブロックスキャン順の処理などが多く行われる。ラスタスキャン順の処理は、画像をページ上の左上の画素から右上の画素方向に処理し、１ライン下がって、また左から右方向に処理し、ページの１番下のラインに向かって処理するといった順序で各画素の処理を行うものである。例えば、レーザープリンタやディスプレイ装置への出力、予測符号化や誤差拡散による中間調処理などの処理がある。また、ブロックスキャン順の処理は、画像をページ上の左上の画素ブロックから右上の画素ブロック方向に処理し、１ブロックライン下がって、また左から右方向に処理し、ページの１番下のブロックラインに向かって処理するといった順序でブロック単位に処理を行うものである。例えば、２次元ＤＣＴ（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ：離散コサイン変換）やＪＰＥＧ圧縮などの処理がある。
【０００５】
上述のようにキャッシュメモリは小容量であり、画像処理で扱うデータ量がキャッシュメモリに比較して膨大なことは言うまでもない。そのため、キャッシュメモリには画像データの一部のみを格納しておくことになる。しかし、上述のようなラスタスキャン順の処理やブロックスキャン順の処理を行う場合には、画像データを主記憶からキャッシュメモリに転送しても転送されたデータはすぐに必要がなくなってしまうことが多い。そのため、一般的なアプリケーションに比べてヒット率が高くないことが知られている。
【０００６】
このような画像処理におけるメモリアクセスの性質、すなわち上述のようなラスタスキャン順やブロックスキャン順のメモリアクセスに適応した従来のキャッシュ技術として、例えば特開平６−１８０６６９号公報に記載されている技術がある。この文献では、キャッシュミス時に、主記憶上では不連続となるが、表示画面上ではキャッシュミスを引き起こしたデータの周辺画素となるデータをキャッシュメモリに転送することを提案している。しかし、この提案では、キャッシュミスを引き起こしたデータのメモリアドレスと、そのデータの直上あるいは直下のデータのメモリアドレスとの間の相対アドレスを指定することができないので、処理すべき画像サイズの変更や画像解像度の変更に対してはまったく効果がない。また、キャッシュミスを引き起こしてから、周辺データを転送する方式なので、ラスタスキャン順の処理やブロックスキャン順の処理ではすぐにキャッシュミスを引き起こしてしまう。さらに、ラスタスキャン順あるいはブロックスキャン順以外のメモリアクセスが発生すると、アクセスしたメモリアドレスをもとに所定のアドレスのデータを読み出してしまうなどといった問題もある。
【０００７】
また、例えば特開平９−１０１９１５号公報に記載されている技術も同様の効果を狙ったものである。通常、キャッシュメモリのエントリの選択に使われるインデクス部とキャッシュライン中のデータを選択するバイト・セレクト部は連続しているが、この間にタグ部の一部を挿入する。これによって、主記憶上では不連続となるが、表示画面上では周辺画素となるデータを多くキャッシュメモリに保持できるようにしている。しかし、この技術においても、画像サイズの変更や画像解像度の変更に対して考慮されておらず、また、キャッシュミスを引き起こしてから、周辺データを転送する方式なので、ラスタスキャン処理やブロックスキャン処理ではすぐにキャッシュミスを引き起こしてしまう。
【０００８】
一方、特開平８−１２３７２７号公報に記載されている技術では、現在のメモリアクセスのメモリアドレスと前回のメモリアクセスのメモリアドレスとの差分を、現在のメモリアクセスのメモリアドレスに加算することで次回のメモリアクセスのメモリアドレスを予測する。そして、予測したメモリアドレスのデータをあらかじめキャッシュメモリに転送する方式を提案している。この方式では、画素データが必要となる前に、そのデータをキャッシュメモリに転送しておく方式であるので、上述の２つの従来の技術よりもラスタスキャン順の処理ならびにブロックスキャン順の処理に優れている。しかし、この方式では、ある画素ブロックの処理中にその他のメモリエリアへのアクセスが行われると、今後あまり使われそうにないデータをキャッシュにコピーしてしまい、かえってヒット率を損なう可能性が大きいという問題がある。
【０００９】
【発明が解決しようとする課題】
本発明は、上述した事情に鑑みてなされたもので、画像処理において高いキャッシュ・ヒット率を得ることにより、メモリアクセスを高速化し、高速な画像処理を実現する画像処理装置を提供することを目的とするものである。またそのような画像処理装置に用いて好適なキャッシュメモリを提供することを目的とするものである。
【００１０】
【課題を解決するための手段】
本発明は、キャッシュメモリを有する画像処理装置であって、プリフェッチの機能を有している。そして、画像のプリフェッチを行った時に、そのプリフェッチの効果をプリフェッチ効果算出手段で算出し、算出されたプリフェッチの効果が有効であると判断された時のみ画像のプリフェッチを行う。さらにキャッシュメモリとして、キャッシュ・エントリがプリフェッチによってフェッチされたものか否かを記録するプリフェッチ・フラグをキャッシュ・タグとして有し、プリフェッチ効果算出手段は、選択されたキャッシュ・エントリに対応する前記プリフェッチ・フラグがプリフェッチによってフェッチされたものであることを示しているとき、プリフェッチされたキャッシュ・データがその後キャッシュ・ヒットしたかキャッシュ・ミスしたかを計数し、その差を予め設定しておいた閾値と比較することによりプリフェッチの効果を判断することを特徴としている。
【００１１】
このように、プリフェッチ機能を有しているので、例えば画像のラスタスキャン順の処理ならびにブロックスキャン順の処理においては、次にアクセスされるであろう画像データがキャッシュメモリに転送されているので、次のメモリアクセス時にはキャッシュ・ヒットし、メモリアクセスを高速化することができる。さらに本発明では、プリフェッチを行うことが効果があるか否かを判断してプリフェッチを行うので、プリフェッチが有効に機能しなくなるとプリフェッチを中止し、不要なデータをキャッシュメモリへコピーしないようにする。これによって、キャッシュメモリを有効に利用し、ヒット率を損なわないようにしている。
【００１２】
また、画像のプリフェッチを行うか否かを指定する画像プリフェッチ指定手段を設け、画像プリフェッチ指定手段により画像のプリフェッチが指定され、かつプリフェッチ効果算出手段で算出されたプリフェッチの効果が有効であると判断された時のみ画像のプリフェッチを行うことができる。例えばある画素ブロックの処理中にその他のメモリエリアへのアクセスが行われる場合や、プリフェッチの効果が有効でない場合に、プリフェッチ指定手段をプリフェッチを行わない指定にしておくことによって、不要なデータのキャッシュメモリへのコピーを防止し、キャッシュメモリのヒット率を損なわないようにすることができる。
【００１３】
また本発明は、複数のプリフェッチ先アドレスの中から１つを選択するプリフェッチ方式指定手段を設け、プリフェッチ時にはプリフェッチ方式指定手段により指定されたプリフェッチ先アドレスを用いて画像のプリフェッチを行うように構成することができる。プリフェッチ先アドレスとしては、例えば、演算装置が最後にアクセスしたメモリアドレスにキャッシュメモリのラインサイズを加算したアドレスが考えられる。このプリフェッチ先アドレスは、ラスタスキャン順の処理に有効である。また、別のプリフェッチ先アドレスとして、例えば演算装置が最後にアクセスしたメモリアドレスに画像の水平方向の画素幅を加算したアドレスが考えられる。このプリフェッチ先アドレスは、ブロックスキャン順の処理に有効である。
【００１４】
【発明の実施の形態】
図１は、本発明の画像処理装置の実施の一形態を示す原理的構成図である。図中、１はメモリアドレス、２はアドレスラッチ、３は画素幅指定レジスタ、４はキャッシュライン・オフセット、５はキャッシュ制御回路、６，７はマルチプレクサ、８はキャッシュメモリ、９はヒット判定回路、１０はデータセレクタ、１１はキャッシュ入力アドレスの上位部分、１２はキャッシュ入力アドレスの中位部分、１３はキャッシュ入力アドレスの下位部分、１４はプリフェッチ効果算出回路、１５はプリフェッチ指定レジスタ、１６はデータバス、１７は加算器、２１は演算装置である。
【００１５】
演算装置２１から出力される現在のメモリアドレス１は、アドレスラッチ２及びマルチプレクサ７に入力される。アドレスラッチ２は、演算装置２１から出力される現在のメモリアドレス１をラッチする。
【００１６】
画素幅指定レジスタ３は、処理対象の１ページの画像の幅をバイト単位で指定した値を保持する。すなわち、（１スキャンラインに並ぶ画素数×１画素あたりのバイト数）の値を保持する。値の設定は、例えば演算装置２１や他の制御手段によって行ったり、特定の用途では固定した値が設定されてもよい。
【００１７】
キャッシュライン・オフセット４は、後述するキャッシュメモリ８のキャッシュ・ライン・サイズをバイト単位であらわした値である。通常、キャッシュメモリ８の構成によってキャッシュ・ライン・サイズは固定されているので、このキャッシュライン・オフセット４は固定値として与えればよい。
【００１８】
キャッシュ制御回路５は、キャッシュメモリ８に関する従来より行われている各種の制御を行う。さらに、後述するプリフェッチ指定レジスタ１５ならびにプリフェッチ効果算出回路１４の出力する値により、プリフェッチを行うか否かを決定する。プリフェッチを行う場合には、プリフェッチ先アドレスとして、アドレスラッチ２の値に画素幅指定レジスタ３の値を加算したものか、あるいは、アドレスラッチ２の値にキャッシュライン・オフセット４の値を加算したもののいずれかを選択する。そして、選択したプリフェッチ先アドレスがキャッシュ・ミスヒットであれば、主記憶からのデータをプリフェッチしてキャッシュメモリ８にコピーを行う。
【００１９】
マルチプレクサ６は、画素幅指定レジスタ３に設定されている値か、キャッシュライン・オフセット４の値かを、キャッシュ制御回路５の制御に従って選択し、出力する。
【００２０】
マルチプレクサ７は、現在のメモリアドレス１か、加算器１７から出力されるプリフェッチ先アドレスのいずれかを、キャッシュ制御回路５の制御に従って選択し、出力する。
【００２１】
キャッシュメモリ８は、複数のキャッシュ・エントリを有しており、また、ヒット判定回路９及びデータセレクタ１０等を有している。各キャッシュ・エントリは、アドレスや各種制御フラグを保持するタグ部と、キャッシュデータを保持するデータ部により構成されている。タグ部に設けられている各種フラグの中には、そのキャッシュ・エントリが有効か無効かを示すバリッドフラグ（Ｖ）やそのキャッシュ・エントリがプリフェッチされたものかどうかを示すプリフェッチ・フラグ（Ｐ）などがある。データ部は、それぞれのキャッシュ・エントリにおいてこの例ではワードＷ０〜Ｗ７の８ワード分のキャッシュデータを格納可能な例を示している。１ワード４バイトとしたとき、キャッシュ・ライン・サイズは３２となる。この値がキャッシュライン・オフセット４として設定される。もちろん、データ部に格納可能なキャッシュデータのワード数やバイト数は任意である。
【００２２】
また、キャッシュメモリ８への入力となるメモリアドレスは、マルチプレクサ７から出力される。このメモリアドレスは、上位アドレス１１、中位アドレス１２、下位アドレス１３に分割されてキャッシュメモリ８に入力される。中位アドレス１２は、キャッシュメモリ８の中から１つのキャッシュ・エントリを選択するために使用される。そして中位アドレス１２が選択したキャッシュ・エントリのタグ部中のアドレスがヒット判定回路９に、またデータ部のキャッシュデータがデータセレクタ１０に出力される。また上位アドレス１１は、ヒット判定回路９に入力される。さらに下位アドレス１３は、データセレクタ１０に入力される。
【００２３】
ヒット判定回路９は、上位アドレス１１と、中位アドレス１２が選択したキャッシュ・エントリのタグ部中のアドレスの値とを比較し、等しいか否かを判断する。等しければキャッシュ・ヒット、等しくなければキャッシュ・ミスとなる。この判定結果は、データセレクタ１０に出力されるとともに、プリフェッチ効果算出回路１４にも出力される。また、図示していないが、ヒット判定回路９の判定結果はキャッシュ制御回路５にも通知され、例えばメモリアドレス１によるアクセスがキャッシュ・ミスの場合には、主記憶へのアクセス及びキャッシュメモリ８へのデータのコピーが行われる。
【００２４】
データセレクタ１０は、中位アドレス１２が選択したキャッシュ・エントリがキャッシュ・ヒットであった時に、下位アドレス１３に従ってそのキャッシュ・エントリのデータ部の中から１ワード（あるいは１バイト）のデータを選択する。キャッシュ・ヒットか否かは、ヒット判定回路９の判定結果を用いる。
【００２５】
プリフェッチ効果算出回路１４は、プリフェッチの効果を算出する。図２は、プリフェッチ効果算出回路１４の一例の説明図である。図中、３１はアップダウン・カウンタ、３２，３３はＡＮＤ回路、３４は反転回路、３５は比較器、３６はラッチである。ここでは一例としてアップダウン・カウンタ３１によって構成した例を示している。アップダウン・カウンタ３１には、例えば演算装置２１や他の制御装置からオフセット値を予めロードしておくことが可能である。
【００２６】
中位アドレス１２により選択されたキャッシュ・エントリのプリフェッチ・フラグ（Ｐ）の値がＡＮＤ回路３２，３３に入力されており、また、ヒット判定回路９の判定結果がＡＮＤ回路３２に、また反転回路３４を介してＡＮＤ回路３３に入力されている。ここではキャッシュ・ヒットの場合に１，キャッシュ・ミスの場合に０がヒット判定回路９から出力されるものとしている。選択されたキャッシュ・エントリのプリフェッチ・フラグ（Ｐ）が“１”かつキャッシュ・ヒットの場合、ＡＮＤ回路３２の出力が“１”となり、アップダウン・カウンタ３１を＋１する。選択されたキャッシュ・エントリのプリフェッチ・フラグ（Ｐ）が“１”かつキャッシュ・ミスの場合、ＡＮＤ回路３３の出力が“１”となり、アップダウン・カウンタ３１を−１する。比較器３５は、アップダウン・カウンタ３１の値と所定の値（図２では“０”）とを比較し、比較結果を出力する。ここではアップダウン・カウンタ３１の値が所定の値“０”と等しくなると“１”を出力する。ラッチ３６は、比較器３５から出力される比較結果をラッチする。ラッチ３６はクリア機能付きである。ラッチ３６によってラッチされている値がプリフェッチ禁止信号としてキャッシュ制御回路５及び演算装置２１などに出力される。
【００２７】
このようなプリフェッチ効果算出回路１４の構成によって、プリフェッチしたキャッシュ・エントリがキャッシュ・ヒットすれば値が大きくなる。また、数回程度キャッシュ・ミスが生じても値はそれほど変化しないので、例えば画像以外の領域がアクセスされても、プリフェッチが乱れることはない。キャッシュ・ミスが続く場合は値は小さくなってゆく。例えば所定の値（“０”）になると、プリフェッチ禁止信号が出力され、プリフェッチは有効ではないものと判断することができる。ラッチ３６のクリアによって、プリフェッチ禁止信号を解除することができる。
【００２８】
なお、上述のようなプリフェッチ効果算出回路１４の構成において、例えばアップダウン・カウンタ３１の上限や下限を設定可能に構成することができる。例えば上限を制御することによって、キャッシュ・ミスの場合の感度を調節することが可能である。また、例えばプリフェッチ指定レジスタ１５によりプリフェッチが禁止されている場合には上述のアップダウン・カウンタ３１の動作を停止し、プリフェッチの効果の算出を制御可能に構成してもよい。もちろん、プリフェッチの効果を判断する方法はほかにもあり、どのような方法を用いるかは任意である。
【００２９】
図１に戻り、プリフェッチ指定レジスタ１５は、プリフェッチを行うか否かの指定、ならびに、プリフェッチを行うとすれば、プリフェッチ先アドレスとして、アドレスラッチ２に格納された前回参照のメモリアドレスに画素幅指定レジスタ３の値を加算するか、キャッシュライン・オフセット４の値を加算するかを選択するための指定を保持する。これらの指定は、例えば演算装置２１あるいはその他の制御装置から行うことができる。例えば画像以外の領域をアクセスする際にプリフェッチを行わない指定を行っておけば、余計なデータをプリフェッチしてキャッシュメモリ８を無駄に消費することはなく、ヒット率を向上させることができる。
【００３０】
データバス１６は、主記憶に接続され、主記憶とのデータの転送を行う。また、演算装置２１とも接続しておくことができ、このデータバス１６を介してキャッシュ・ヒットしたときのデータを演算装置２１に転送することができる。なお、主記憶とのデータ転送と、演算装置２１とのデータ転送を別のバスを用いて行うこともできる。
【００３１】
加算器１７は、マルチプレクサ６で選択した画素幅指定レジスタ３の値あるいはキャッシュライン・オフセット４の値と、アドレスラッチ２に格納されているメモリアドレスを加算し、プリフェッチ先アドレスを算出する。算出したプリフェッチ先アドレスはマルチプレクサ７へ出力される。
【００３２】
図３は、本発明の画像処理装置の実施の一形態における動作の一例を示すフローチャートである。ここでは主にキャッシュ制御回路５の動作を中心にして説明する。なお、予めプリフェッチ効果算出回路１４には適当な初期値をロードしておく。また、例えばプリフェッチ先アドレスとして、アドレスラッチ２に格納された前回参照のメモリアドレスに画素幅指定レジスタ３の値を加算したアドレスを用いる場合には、処理対象の画像が決定した時点で画素幅指定レジスタ３に値を設定しておく。さらに、少なくともメモリアクセスの前までにプリフェッチ指定レジスタ１５の設定を行っておくものとする。
【００３３】
キャッシュ制御回路５は、演算装置２１によりメモリリードアクセスが発生するたびに起動され、例えば図３に示すような動作を行う。演算装置２１によりメモリリードアクセスが発生すると、Ｓ４１において、キャッシュ制御回路５はマルチプレクサ７に対して演算装置２１からのメモリアドレス１を選択させる。そしてメモリアドレス１の中位アドレス１２によってキャッシュメモリ８内のキャッシュ・エントリが選択される。選択されたキャッシュ・エントリのタグ部中のアドレスがヒット判定回路９へ、またデータ部のデータがデータセレクタ１０へそれぞれ入力される。
【００３４】
Ｓ４２において、ヒット判定回路９は、中位アドレス１２によって選択されたキャッシュ・エントリのタグ部中のアドレスと上位アドレス１１とを比較し、キャッシュ・ヒットしたか否かを判定する。キャッシュ・ヒットであれば、Ｓ４４において、データセレクタ１０は、中位アドレス１２によって選択されたキャッシュ・エントリのデータ部中のデータのうち、低位アドレス１３によって指定されているデータ（ワードあるいはバイト）を選択して、演算装置２１へ転送する。さらにキャッシュ・ヒットした場合には、中位アドレス１２によって選択されたキャッシュ・エントリのタグ部中のプリフェッチ・フラグ（Ｐ）が“１”であれば、プリフェッチ効果算出回路１４中の図２に示すアップダウン・カウンタ３１が＋１される。
【００３５】
また、キャッシュ・ミスであった時は、Ｓ４３において、まず主記憶から、メモリアドレス１によって要求されているデータを含むキャッシュ・ライン・サイズだけのデータ、この例では８ワード（３２バイト）のデータをバースト転送してキャッシュメモリ８にコピーする。その後、Ｓ４４において、コピーしたデータの中から低位アドレス１３によって指定されているデータ（ワードあるいはバイト）をデータセレクタ１０で選択して、演算装置２１へ転送する。さらにキャッシュ・ミスの場合には、中位アドレス１２によって選択されたキャッシュ・エントリのタグ部中のプリフェッチ・フラグ（Ｐ）が“１”であれば、プリフェッチ効果算出回路１４中の図２に示すアップダウン・カウンタ３１が−１される。
【００３６】
データを演算装置２１へ転送した後、Ｓ４５において、キャッシュ制御回路５はプリフェッチ指定レジスタ１５の値を調べて、プリフェッチの指定の有無を判定する。ここではプリフェッチ指定レジスタ１５の値が“０”であればプリフェッチ禁止、“０”以外であれば値に応じたプリフェッチ先アドレスを指定してプリフェッチを行うものとする。プリフェッチ指定レジスタ１５の値が“０”であれば、プリフェッチ禁止なので処理を終了し、次のアクセスを待つアイドル状態となる。
【００３７】
プリフェッチ指定レジスタ１５の値が“０”でなければ、さらにＳ４６において、プリフェッチの有効性を判定する。プリフェッチの有効性の判定は、プリフェッチ効果算出回路１４の出力により行う。上述のように、キャッシュ・ヒットしているとアップダウン・カウンタ３１がカウントアップしているので比較器３５はプリフェッチが有効であることを示すため“０”を出力している。プリフェッチしてきたデータに対してキャッシュ・ミスの割合が大きくなっていくと、アップダウン・カウンタ３１の値が減ってゆき、“０”にまで到達すると比較器３５の出力が“１”になり、ラッチ３６がそれを記憶してプリフェッチ禁止信号として“１”を出力する。このプリフェッチ禁止信号が“１”のとき、プリフェッチは有効でないと判定することができる。
【００３８】
プリフェッチ禁止信号として“１”が出力され、プリフェッチは有効でないと判定された場合には、Ｓ４７において、キャッシュ制御回路５はプリフェッチ指定レジスタ１５に値“０”を書き込んで、以降のプリフェッチを禁止し、それ以降プリフェッチを行わない。また、それと同時に、プリフェッチ禁止信号は演算装置２１などにより参照可能なレジスタにも入力されており、プリフェッチが禁止されたことがレジスタに記録される。そして処理を終了し、次のアクセスを待つアイドル状態となる。
【００３９】
なお、このプリフェッチの禁止状態は、例えば演算装置２１などによって図２に示すプリフェッチ効果算出回路１４のラッチ３６をクリアするまで維持される。また、プリフェッチ禁止信号が出力されていることを知った演算装置２１などでは、プリフェッチ指定レジスタ１５に前回とは異なるプリフェッチ先を指定し、ラッチ３６をゼロクリアすることで、前回とは異なる新たなプリフェッチ先アドレスによるプリフェッチを再開することも可能である。
【００４０】
Ｓ４６でプリフェッチが有効に働いていると判断された場合には、プリフェッチを実行するために、Ｓ４８においてプリフェッチ先アドレスを決定する。プリフェッチ先アドレスの決定は、プリフェッチ指定レジスタ１５に設定されている値により行う。ここでは一例として、プリフェッチ指定レジスタの値が“１”であれば、プリフェッチ先アドレスとして、アドレスラッチ２に格納された前回参照のメモリアドレスにキャッシュライン・オフセット４の値を加算したものとし、プリフェッチ指定レジスタの値が“２”であれば、プリフェッチ先アドレスとして、アドレスラッチ２に格納された前回参照のメモリアドレスに画素幅指定レジスタ３の値を加算したものとする。すなわちこの例では、キャッシュ制御回路５は、プリフェッチ指定レジスタ１５の値が“１”であればマルチプレクサ６に対してキャッシュライン・オフセット４の値を選択させ、プリフェッチ指定レジスタ１５の値が“２”であれば画素幅指定レジスタ３の値を選択させる。選択されたいずれかの値と、アドレスラッチ２に保持されている前回参照したときのメモリアドレスが加算器１７で加算され、プリフェッチ先アドレスとなる。
【００４１】
さらにキャッシュ制御回路５は、マルチプレクサ７を制御して加算器１７の出力であるプリフェッチ先アドレスを選択させる。これによってプリフェッチ先アドレスによるキャッシュメモリ８の参照が行われる。すなわち、プリフェッチ先アドレスの中位アドレス１２によってキャッシュメモリ８内のキャッシュ・エントリが選択される。選択されたキャッシュ・エントリのタグ部中のアドレスがヒット判定回路９へ入力される。Ｓ４９において、ヒット判定回路９は、プリフェッチ先アドレスの中位アドレス１２によって選択されたキャッシュ・エントリのタグ部中のアドレスと、プリフェッチ先アドレスの上位アドレス１１とを比較し、キャッシュ・ヒットしたか否かを判定する。キャッシュ・ヒットであれば、プリフェッチすべきデータは既にキャッシュメモリ８に存在しているので、改めてプリフェッチすることなく処理を終了し、次のアクセスを待つアイドル状態となる。
【００４２】
また、プリフェッチ先アドレスによるキャッシュメモリ８の参照がキャッシュ・ミスであった時は、Ｓ５０において、主記憶からプリフェッチ先アドレスのデータを含むキャッシュ・ライン・サイズだけのデータ、この例では８ワード（３２バイト）のデータをキャッシュメモリ８にコピーする。その際、キャッシュ・エントリのタグ部中のプリフェッチ・フラグ（Ｐ）に“１”をセットして、そのキャッシュ・エントリがプリフェッチによりコピーされたものであることを示しておく。その後、処理を終了し、次のアクセスを待つアイドル状態となる。
【００４３】
なお、図示はしていないが、Ｓ４５〜Ｓ４８の処理中に演算装置２１からのメモリリードアクセスがあった時には、途中の処理を中止して、改めて図３に示す処理を開始する。これはプリフェッチよりも、演算装置２１からのメモリアクセス要求の方がメモリアクスに対する優先度が高いためである。
【００４４】
以下、本発明の画像処理装置の実施の一形態を利用した具体例について説明する。まず、ラスタスキャン順の処理の具体例として、簡単な予測符号化を行う際の画像データの処理について説明する。図４は、予測符号化における画素の処理順の説明図、図５は、１画素の予測符号化の処理を行う際に参照する画素の一例の説明図である。予測符号化では、注目画素を近隣の画素値から予測し、その予測誤差をハフマン符号化するものである。図５に示す例では、注目画素Ｘを近隣画素Ａ，Ｂ，Ｃ，Ｄから予測する例を示している。このような注目画素Ｘである１画素の処理が終了すると、注目画素Ｘ並びに近隣画素Ａ，Ｂ，Ｃ，Ｄが右に１画素分だけずれていく。図４には注目画素Ｘの移動を示しており、図中の実線の矢印で示すように、ライン方向にメモリアドレスはシーケンシャルに増えてゆく。なお、各々の画素は８ビット（１バイト）のデータ長を持っているものとする。
【００４５】
この時、図５に示す近隣画素Ｄは、既に直前に処理を行っているので、特別の場合でない限りキャッシュメモリ８中に存在している。近隣画素Ａ，Ｂ，Ｃについては、キャッシュメモリ８の容量が画素幅（１ライン分の画素のデータ長）に比較して十分大きければ、あるいは画素幅が小さければ、キャッシュメモリ８中に存在する可能性が高い。また、参照画素Ｘと同じライン上でＸより右側の画素は近い将来必ず参照される。
【００４６】
このような時は、プリフェッチ指定レジスタ１５に値“１”を指定し、プリフェッチ先アドレスとして、アドレスラッチ２に格納された前回参照のメモリアドレスにキャッシュライン・オフセット４の値を加算したものを選択してプリフェッチを行う設定とする。上述のようにキャッシュライン・オフセット４は、１つのキャッシュ・エントリに保持される連続した領域のバイト数であり、上述の例ではキャッシュライン・オフセットが３２バイトである。つまり前回参照アドレス＋３２がプリフェッチ先アドレスとなる。
【００４７】
図６は、予測符号化におけるキャッシュメモリの動作の一例の説明図である。１画素が１バイトであれば、上述の例では１つのキャッシュ・エントリに３２画素分のデータが格納されるので、同じキャッシュ・エントリに格納されている３２画素について予測符号化しているときには、キャッシュ・ヒットする。例えば図６において▲２▼〜▲３▼までの画素を処理している間は、同じキャッシュ・エントリ内であるのでキャッシュ・ヒットする。このときプリフェッチ効果算出回路１４は、アップダウン・カウンタ３１が増加し、プリフェッチの効果があるものと判断している。
【００４８】
この３２画素の処理を行っている間に、次の３２画素分のデータがプリフェッチされる。具体的には▲１▼の画素の処理から▲２▼の画素の処理に移り、▲２▼の画素のデータがリードアクセスされたときに、▲４▼の画素から３２画素分のデータがプリフェッチされる。そのため、１つのキャッシュ・エントリに格納されている３２画素分のデータを処理した後は、別のキャッシュ・エントリに次の３２画素分のデータが格納されている。図６に示す例では、▲３▼の画素の処理終了時点ではすでに▲４▼の画素を含む３２画素分のデータがキャッシュメモリ８内に存在する。そのため、別のキャッシュ・エントリに格納されている画素のデータ（例えば▲４▼の画素）に処理が移行しても、キャッシュ・ヒットが続くことになる。さらに、例えばラインの終端の画素と次のラインの始端の画素とが連続あるいはキャッシュ・ライン・サイズの範囲内のアドレスに配置されている場合には、参照画素Ｘが次のラインに移ってもキャッシュ・ヒットが続くことになる。
【００４９】
このようにして、ラスタスキャン順の処理において、新たに参照する画素のデータはプリフェッチによって予めキャッシュメモリ８にコピーされているので、高いヒット率を確保し、高速なメモリアクセスによって処理速度を向上することができる。
【００５０】
次に、ブロックライン順の処理の一例として、２次元ＤＣＴ演算を行う場合について説明する。図７は、２次元ＤＣＴ演算を行う際の画像データのアクセス順の一例の説明図である。２次元ＤＣＴ演算は、所定のブロック毎に処理を進めてゆく。例えば図７（Ａ）では各マス目が１つのブロックを示しており、１つのブロックを処理すると、その右隣のブロックの処理を行う。このようなブロック毎の処理が右端まで達したら、ブロックの大きさだけ下に移動し、再びブロック単位で左から右へ処理を行ってゆく。
【００５１】
また各ブロック内では、ラインごとに左の画素から右の画素へ順次処理を行ってゆく。図７（Ｂ）に示す例では各マス目が画素を示し、８×８画素を１つのブロックとした例を示している。ブロック内では矢線で示すように上のラインの左から右へ、右端まで達したら下のラインへという順で処理が行われる。そして、このような８×８画素のブロックを処理してから右隣のブロック（あるいは次のブロックラインの左端のブロック）の処理に移る。
【００５２】
このようなブロックライン順の処理を行う時は、プリフェッチ指定レジスタ１５に値“２”を指定し、画素幅指定レジスタ３にはページの水平方向の幅をバイト数で指定する。これにより、（前回参照アドレス＋指定された画素幅）がプリフェッチ先アドレスとなる。
【００５３】
すなわち、図７（Ｂ）における最初のラインの８画素を処理しているとき、プリフェッチによって２行目のラインを含むデータがキャッシュメモリ８にコピーされている。そのため、最初のラインの８画素の処理が終了して２行目のラインに処理が移行しても、そのままキャッシュ・ヒットが続くことになる。同様に２行目のラインを処理している間に、３行目のラインがプリフェッチされる。このようにして、１ブロックを処理している間、キャッシュ・ヒットが続き、メモリアクセスを高速化し、ひいては処理の高速化を実現することができる。
【００５４】
なお、２次元ＤＣＴ演算では、８×８画素ブロックの１行目から８行目までの８画素ずつにアクセスしたあと、今度は直交する方向、すなわち８×８画素ブロックの１列目から８列目までの８画素ずつにアクセスする。しかし、この時にはすでに８×８画素ブロック全体がキャッシュメモリ８に存在するので、キャッシュ・ヒットし、高速なアクセスを行うことができる。
【００５５】
さらに、上述の例ではキャッシュ・エントリに３２画素分のデータを格納可能であるので、１ブロックの各行のデータをプリフェッチしたとき、４ブロック分のデータがキャッシュメモリ８にコピーされている。そのため、連続する最大４ブロック内のデータアクセスについてはキャッシュ・ヒットすることになる。また、これを超えて最初のアクセスにおいてはキャッシュ・ミスが発生するが、１回のキャッシュ・ミスではプリフェッチ効果算出回路１４においてプリフェッチの有効性は否定されないので、そのままプリフェッチ動作が続けられることになる。
【００５６】
もちろん、キャッシュライン・オフセット４の値を用いたプリフェッチ先アドレスの指定を組み合わせて用いることも可能である。例えば最初のブロックで８ライン分のデータをキャッシュメモリ８にコピーしたら、それ以降のブロックの処理中に次の３２画素毎の８ライン分のデータをキャッシュメモリ８にプリフェッチさせるように制御することができる。
【００５７】
上述の画像処理の具体例は一例であって、各種のラスタスキャン順あるいはブロックスキャン順の処理に対して、本発明を利用することによって、メモリアクセスを高速化し、処理時間を短縮することが可能である。
【００５８】
【発明の効果】
以上の説明から明らかなように、本発明によれば、画像処理における画像アクセスの特性に基づきプリフェッチを行うことで少ないキャッシュメモリでもキャッシュ・ヒット率を高めることができ、それにより高速なメモリアクセスを提供する画像処理装置を実現できる。また、少数のキャッシュ・ミスが発生してもそれによってプリフェッチの動作を変更することなく行うので、例えば画像処理以外のアクセスが発生してもそれによる影響を受けにくいという利点がある。さらに、キャッシュ・ミスが多発する場合には、プリフェッチの動作を禁止し、プリフェッチによるキャッシュ・ヒット率の低下を防止することができる。本発明ではこれらのほかにも、詳述したように各種の効果がある。
【図面の簡単な説明】
【図１】  本発明の画像処理装置の実施の一形態を示す原理的構成図である。
【図２】  プリフェッチ効果算出回路１４の一例の説明図である。
【図３】  本発明の画像処理装置の実施の一形態における動作の一例を示すフローチャートである。
【図４】  予測符号化における画素の処理順の説明図である。
【図５】  １画素の予測符号化の処理を行う際に参照する画素の一例の説明図である。
【図６】  予測符号化におけるキャッシュメモリの動作の一例の説明図である。
【図７】  ２次元ＤＣＴ演算を行う際の画像データのアクセス順の一例の説明図である。
【符号の説明】
１…メモリアドレス、２…アドレスラッチ、３…画素幅指定レジスタ、４…キャッシュライン・オフセット、５…キャッシュ制御回路、６，７…マルチプレクサ、８…キャッシュメモリ、９…ヒット判定回路、１０…データセレクタ、１１…キャッシュ入力アドレスの上位部分、１２…キャッシュ入力アドレスの中位部分、１３…キャッシュ入力アドレスの下位部分、１４…プリフェッチ効果算出回路、１５…プリフェッチ指定レジスタ、１６…データバス、１７…加算器、２１…演算装置、３１…アップダウン・カウンタ、３２，３３…ＡＮＤ回路、３４…反転回路、３５…比較器、３６…ラッチ。
【図１】
0004072665.tif 000002
【図２】
0004072665.tif 000003
【図３】
0004072665.tif 000004
【図４】
0004072665.tif 000005
【図５】
0004072665.tif 000006
【図６】
0004072665.tif 000007
【図７】
0004072665.tif 000008