(57)【要約】【課題】  画像を単位矩形ブロックごとに格納するブロック構造の画像ではＭＰＥＧ等の画像処理におけるアドレス計算が複雑になる。【解決手段】  アドレスレジスタがアドレスを格納し、ステップレジスタがステップ幅を格納し、ギャップレジスタがギャップ幅を格納し、キャリーポジションレジスタが桁上がり位置を格納し、演算器がアドレスレジスタへステップレジスタの内容を加算し、もしその加算結果がキャリーポジションレジスタが示す桁上がり位置で桁上がりする場合には、さらにアドレスレジスタへギャップレジスタの内容を加算する。【選択図】      図１
2007249515.tif 000002
【特許請求の範囲】
【請求項１】
アドレスを格納する第一の記憶手段と、
ステップ幅を格納する第二の記憶手段と、
ギャップ幅を格納する第三の記憶手段と、
桁上がり位置を格納する第四の記憶手段と、
前記第一の記憶手段へ前記第二の記憶手段の内容を加算し、もしその加算結果が前記第四の記憶手段が示す桁上がり位置で桁上がりする場合には、さらに前記第一の記憶手段へ前記第三の記憶手段の内容を加算する処理を実行する演算器と
を備えたことを特徴とするプロセッサ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は画像のある矩形領域を少ないサイクルでメモリからメモリへコピーすることができるプロセッサに関する。
【背景技術】
【０００２】
静止画処理や動画処理のアルゴリズム（符号化、復号化、ノイズ除去、画像分析）の多くは矩形ブロックごとに処理を行なう。例えば、ＭＰＥＧ（moving picture expert group）標準は、８×８や１６×１６の矩形ブロックを扱う。キャッシュをもつプロセッサで画像を処理する場合、矩形ブロックとキャッシュの相性が悪いことが問題になる。
【０００３】
キャッシュは主記憶のデータを一時的に格納する高速なメモリである。主記憶のデータは３２バイトや６４バイトごとに分割され管理される。３２バイトや６４バイトなどのデータの管理単位をラインと呼ぶ。キャッシュはラインごとにデータを管理する。
【０００４】
通常、画像データは行ごとに主記憶へ格納される。主記憶上には、画像の画素が、左上から始まって、左から右へ、上から下へ、という順序で格納されることになる（図２を参照）。このような画像を行構造の画像と呼ぶことにする。
【０００５】
ラインサイズが３２バイトのキャッシュをもつプロセッサにおいて、画像のある矩形ブロックに含まれる画素を取り出したいとする。画像の一つの画素は１バイトで表されるとする。矩形ブロックの各行内の画素は一つあるいは二つのキャッシュラインに収まる。矩形ブロックの始めの行と次の行はそれぞれ別のキャッシュラインに収まる。矩形ブロックが８×８だとすると、最大で１６個のキャッシュラインに矩形ブロックの画素は分散して収まる。
【０００６】
もしキャッシュが空だとすると、画像のある矩形ブロック８×８をキャッシュに取り込むために１６回のミスヒットが発生する。これは最悪ケースである。矩形ブロック８×８にあるデータは６４バイトなので、キャッシュのラインサイズが３２バイトであることを考えると、最大で１６回のミスヒットは非常に悪い値である。つまり、行構造の画像の矩形ブロックをアクセスするという処理とキャッシュは相性が悪いといえる。
【０００７】
行構造の画像の矩形ブロックをアクセスする処理とキャッシュとの相性が悪いという問題を解決するために、Han Chenらはキャッシュに適した画像のデータ構造を提案した（非特許文献１）。
【０００８】
キャッシュに適した画像のデータ構造とは、画像を単位矩形ブロックごとに格納するデータ構造である（図３を参照）。ここではこのデータ構造をブロック構造と呼ぶ。ブロック構造の画像はＣ言語では以下のような三次元配列で表される。
【０００９】
char buffer_block[BLOCK_NUM][BLOCK_HEIGHT][BLOCK_WIDTH];
【００１０】
ここで、BLOCK_WIDTHは単位矩形ブロックの幅、BLOCK_HEIGHTは単位矩形ブロックの高さ、BLOCK_NUMは画像に含まれる単位矩形ブロックの数である。画像の横幅をPIC_WIDTHとすると、ブロック構造の画像の(X、Y)座標にある画素は以下のように表される。ただしfloor(Z)はZの整数部を返す。%はモジュロ演算子である。
【００１１】
buffer_block [PIC_WIDTH*BLOCK_HEGHT*floor(Y/BLOCK_HEIGHT)+BLOCK_WIDTH*BLOCK_HEIGHT*floor(X/BLOCK_WIDTH)][(Y%BLOCK_HEIGHT)][X%BLOCK_WIDTH];
【００１２】
キャッシュのラインサイズとの相性を良くするために、BLOCK_WIDTH やBLOCK_HEIGHTは２の累乗にした方が良い。例えばＭＰＥＧでは８×８や１６×１６の矩形ブロックを扱うので、BLOCK_HEIGHT=BLOCK_WIDTH=8 とする。キャッシュのラインサイズが３２バイトならば、ＭＰＥＧにおける単位矩形ブロックは２個のキャッシュラインへ収まる。行構造画像の単位矩形ブロックは８個のキャッシュラインへ収まるので、行構造よりもブロック構造の方がキャッシュを有効に利用できると言える。
【００１３】
ＭＰＥＧなどの画像処理に関してブロック構造は行構造よりもキャッシュの利用効率が良いという利点をもつが、アドレス計算が複雑であるという欠点がある。図４を使ってアドレス計算が複雑になることを説明する。アドレス計算の複雑性はブロック構造の画像から任意の位置(X1、Y1)にある矩形ブロックＢを読む場合に現れる。矩形ブロックＢの幅をBLOCK_WIDTH、高さをBLOCK_HEIGHTとする。さらに、X1はBLOCK_WIDTHの倍数ではなく、Y1はBLOCK_HEIGHTの倍数ではないとする。
【００１４】
X1がBLOCK_WIDTHの倍数ではないので、矩形ブロックＢの各行は二つ以上の単位矩形ブロックにまたがっている。同様に、Y1がBLOCK_HEIGHTの倍数ではないので、矩形ブロックＢの各列は二つ以上の単位矩形ブロックにまたがっている。
【００１５】
矩形ブロックＢの行内で単位矩形ブロックが切り替わるということは、画素のアドレスが不連続になるということを意味する。なぜなら、ブロック構造における画像内の各行はBLOCK_WIDTH幅ごとに分割されて、とびとびに主記憶へ格納されるからである。矩形ブロックＢの行内のどの位置でアドレスが不連続になるかは座標X1に依存する。矩形ブロックＢの各行においてアドレスが不連続になるか否かの判定が必要になるので、アドレス計算が複雑になってしまう。
【００１６】
座標(X1、Y1)のメモリ上のアドレスをmとする。図４に示すように、座標Y1の行にある画素のアドレスは右方向へ向かって、m、m+1、m+64-7、、m+64-6、．．．と変化する。アドレスm+1とアドレスm+64-7の間に単位矩形ブロックの境界がある。一方、座標X1の列にある画素のアドレスは下方向へ向かって、m、m+8、m+8*PIC_WIDTH-64+16、m+8*PIC_WIDTH-64+24、．．．と変化する。アドレスm+8とアドレスm+8*PIC_WIDTH-64+16の間に単位矩形ブロックの境界がある。
【００１７】
アドレス計算に関しては明らかにブロック構造よりも行構造のほうが優れている。ブロック構造を選択するなら、キャッシュの利用効率が高まるかわりに、複雑なアドレス計算を受け入れなければならない。
【００１８】
【非特許文献１】Han Chen、et al．、Memory Performance Optimizations for Real-time Software HDTV Decoding、IEEE International Conference on Multimedia and Expo (ICME2002)、Aug．2002．
【発明の開示】
【発明が解決しようとする課題】
【００１９】
ブロック構造の画像にはアドレス計算が複雑になるという問題がある。ブロック構造の画像の任意の(X1、Y1)座標から矩形ブロックＢを読む際に、矩形ブロックＢの行内にアドレス不連続点が現れるため、不連続点か否かを判定する処理が必要となる。
【００２０】
本発明の目的は、上述した従来の技術における課題を解決するプロセッサを提供することにある。
【課題を解決するための手段】
【００２１】
本発明のプロセッサは、アドレスを格納する第一の記憶手段（アドレスレジスタ）と、ステップ幅を格納する第二の記憶手段（ステップレジスタ） と、ギャップ幅を格納する第三の記憶手段（ギャップレジスタ）と、桁上がり位置を格納する第四の記憶手段（キャリーポジションレジスタ）と、前記第一の記憶手段へ前記第二の記憶手段の内容を加算し、もしその加算結果が前記第四の記憶手段が示す桁上がり位置で桁上がりする場合には、さらに前記第一の記憶手段へ前記第三の記憶手段の内容を加算する処理を実行する演算器とを備えたことを特徴とする。
【発明の効果】
【００２２】
本発明の効果は、ブロック構造の画像の任意の座標(X1、Y1)から矩形ブロックＢを読む処理において、矩形ブロックＢの行内に現れるアドレス不連続点の検出処理を隠蔽できることである。
【発明を実施するための最良の形態】
【００２３】
図１を使って本発明を実施するための形態について説明する。本発明は、アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０、演算器５０から構成される。
【００２４】
アドレスレジスタ１０はメモリ上のアドレスを格納するレジスタである。ステップレジスタ２０は演算器５０が参照するステップサイズを格納するレジスタである。ギャップレジスタ３０は演算器５０が参照するギャップサイズを格納するレジスタである。キャリーポジションレジスタ４０は演算器５０が参照する桁上がり位置を格納するレジスタである。演算器５０は、ステップレジスタ２０とギャップレジスタ３０とキャリーポジションレジスタ４０とを参照してアドレスレジスタ１０の内容を更新する演算器である。
【００２５】
演算器５０がアドレスレジスタ１０の内容を更新する手順について説明する。まず、アドレスレジスタ１０へステップレジスタ２０の内容を加算する。次に、この加算によって、アドレスレジスタ１０におけるキャリーポジションレジスタ４０が示すビット位置のビットに変化があるなら、アドレスレジスタ１０へギャップレジスタ３０の内容をさらに加算する。
【実施例１】
【００２６】
本発明の第一の実施例について説明する。この実施例における本発明の構成要素を以下に示す。
【００２７】
アドレスレジスタ１０は３２ビットのレジスタである。バイト単位の３２ビットアドレスがこのレジスタに格納される。
ステップレジスタ２０は１６ビットのレジスタである。演算器５０によってアドレスレジスタ１０へ加算されるステップサイズがこのレジスタに格納される。
ギャップレジスタ３０は１６ビットのレジスタである。演算器５０によってアドレスレジスタ１０へ加算されるギャップサイズがこのレジスタに格納される。
キャリーポジションレジスタ４０は８ビットのレジスタである。演算器５０がアドレスレジスタ１０へステップレジスタ２０の内容を加算した後で、アドレスレジスタ１０のどのビットの変化を検出するかをこのレジスタに格納する。
【００２８】
本実施例における演算器５０の動作を説明する。アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０の初期値を以下のように仮定する。
【００２９】
アドレスレジスタ１０: 0x1111 2234
ステップレジスタ２０: 0x0002
ギャップレジスタ３０: 0x0038
キャリーポジションレジスタ４０: 0x03
【００３０】
この状態で演算器５０を動作させる。まず、演算器５０はアドレスレジスタ１０へステップレジスタ２０の内容を加算する。するとアドレスレジスタ１０は0x1111 2236となる。演算器５０はキャリーポジションレジスタ４０を参照して、アドレスレジスタ１０の対応するビット（ビット３）に変化があるかを検査する。加算前のアドレスレジスタ１０のビット３は１で、加算後のアドレスレジスタ１０のビット３は１である。したがってアドレスレジスタ１０のビット３に変化はない。ビット３に変化はないので、演算器５０はアドレスレジスタ１０へギャップレジスタ３０の内容を加算しない。この結果、アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０の値は以下のようになる。
【００３１】
アドレスレジスタ１０: 0x1111 2236
ステップレジスタ２０: 0x0002
ギャップレジスタ３０: 0x0038
キャリーポジションレジスタ４０: 0x03
【００３２】
続けてこの状態から演算器５０をもう一度動作させる。まず、演算器５０はアドレスレジスタ１０へステップレジスタ２０の内容を加算する。するとアドレスレジスタ１０は0x1111 2238となる。演算器５０はキャリーポジションレジスタ４０を参照して、アドレスレジスタ１０の対応するビット（ビット３）に変化があるかを検査する。加算前のアドレスレジスタ１０のビット３は１で、加算後のアドレスレジスタ１０のビット３は０である。したがってアドレスレジスタ１０のビット３に変化がある。ビット３に変化があるので、演算器５０はアドレスレジスタ１０へギャップレジスタ３０の内容をさらに加算する。この結果、アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０の値は以下のようになる。
【００３３】
アドレスレジスタ１０: 0x1111 2270
ステップレジスタ２０: 0x0002
ギャップレジスタ３０: 0x0038
キャリーポジションレジスタ４０: 0x03
【００３４】
以上のように、第一の実施例は、キャリーポジションレジスタ４０に格納された値にしたがって、データの不連続区間を飛び越えるようにアドレスレジスタ１０を更新する。
【実施例２】
【００３５】
本発明の第二の実施例について説明する。この実施例における本発明の構成要素は第一の実施例と全く同じである。ただし使用目的が第一の実施例とは異なる。第一の実施例はギャップレジスタ３０へ正の値を格納することによって、データの不連続区間を飛び越えるようにアドレスレジスタ１０を更新する。一方、第二の実施例はギャップレジスタ３０へ負の値を格納することによって、リングバッファに適したアドレス更新を可能にする。
【００３６】
本実施例における演算器５０の動作を説明する。本実施例はリングバッファを扱う。リングバッファの開始アドレスを0x1111 2230、リングバッファのサイズを８バイトとする。このリングバッファをアドレス0x1111 2234から２バイトおきにアクセスする。そのために、アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０の初期値を以下のように設定する。キャリーポジションレジスタ４０はリングバッファのサイズを表す。ギャップレジスタ３０はアドレスレジスタ１０をリングバッファの先頭へ巻戻すための値を表す。
【００３７】
アドレスレジスタ１０: 0x1111 2234
ステップレジスタ２０: 0x0002
ギャップレジスタ３０: 0xFFF8
キャリーポジションレジスタ４０: 0x03
【００３８】
この状態で演算器５０を動作させる。まず、演算器５０はアドレスレジスタ１０へステップレジスタ２０の内容を加算する。するとアドレスレジスタ１０は0x1111 2236となる。演算器５０はキャリーポジションレジスタ４０を参照して、アドレスレジスタ１０の対応するビット（ビット３）に変化があるかを検査する。加算前のアドレスレジスタ１０のビット３は１で、加算後のアドレスレジスタ１０のビット３は１である。したがってアドレスレジスタ１０のビット３に変化はない。ビット３に変化はないので、演算器５０はアドレスレジスタ１０へギャップレジスタ３０の内容を加算しない。この結果、アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０の値は以下のようになる。
【００３９】
アドレスレジスタ１０: 0x1111 2236
ステップレジスタ２０: 0x0002
ギャップレジスタ３０: 0xFFF8
キャリーポジションレジスタ４０: 0x03
【００４０】
続けてこの状態から演算器５０をもう一度動作させる。まず、演算器５０はアドレスレジスタ１０へステップレジスタ２０の内容を加算する。するとアドレスレジスタ１０は0x1111 2238となる。演算器５０はキャリーポジションレジスタ４０を参照して、アドレスレジスタ１０の対応するビット（ビット３）に変化があるかを検査する。加算前のアドレスレジスタ１０のビット３は１で、加算後のアドレスレジスタ１０のビット３は０である。したがってアドレスレジスタ１０のビット３に変化がある。ビット３に変化があるので、演算器５０はアドレスレジスタ１０へギャップレジスタ３０の内容をさらに加算する。ただし加算前にギャップレジスタ３０の内容は３２ビットへ符号拡張される。この結果、アドレスレジスタ１０、ステップレジスタ２０、ギャップレジスタ３０、キャリーポジションレジスタ４０の値は以下のようになる。
【００４１】
アドレスレジスタ１０: 0x1111 2230
ステップレジスタ２０: 0x0002
ギャップレジスタ３０: 0xFFF8
キャリーポジションレジスタ４０: 0x03
【００４２】
以上のように、第二の実施例はリングバッファに適したアドレス更新を行なうことができる。
【００４３】
具体的な使用例
あるブロック構造の画像の中の矩形ブロックを読み込む処理について具体的に説明する。二個の単位矩形ブロック８×８からなるブロック構造の画像を仮定する。つまり、この画像の幅は１６で高さは８である。この画像はＣ言語で表すとchar src_buffer[2][8][8];となる。
【００４４】
この画像src_bufferの座標(pos_x、pos_y)から始まる４×４の矩形ブロックをchar dst_buffer[4][4]へコピーする。ただし、４×４の矩形ブロックが画像外にはみ出さないように、0<=pos_x<(16-4)、0<=pos_y<(8-4)と仮定する。この処理をＣ言語で記述すると図５のプログラムになる。
【００４５】
図５のプログラムにおいて__update_addr(_r10、_r20、_r30、_r40) は変数_r10の値を更新する関数である。_r10と_r20の和が_r40が示すビット位置で桁上がりすればこの関数は_r10+_r20+_r30を返し、そうでなければ_r10+_r20を返す。
【００４６】
図６を使ってこの処理の内容を説明する。例えばpos_x=7、pos_y=4ならば図６上の行構造画像の４×４の領域（太い四角で囲まれた領域）を読むことになる。これをブロック構造の画像で考えると、図６下のように太い四角で囲まれた４個の領域を読むことになる。
【００４７】
pos_x=7、pos_y=4の場合、図５の関数copy_block_4x4()は図６に示した１６個の画素を読む。copy_block_4x4()は内部の２重ループでこれらの画素を読む。１６個の画素を四つのグループに分ける。
【００４８】
グループ0: 71、72、73、74
グループ1: 87、88、89、90
グループ2: 103、104、105、106
グループ3: 119、120、121、122
【００４９】
グループ０において、画素71と画素72とは離れた位置にあり、画素72、73、74は連続した領域にある。他のグループの画素にも同様な関係がある。画素72、73、74を順番に読む場合はアドレスを+1ずつ加算するが、画素71から画素72へはアドレスを+64-8+1加算する。どの画素でアドレスのギャップが生じるかはpos_xに依存して変わる。関数__update_addr()は、このようなアドレスのギャップを考慮して次の画素のアドレスを計算する。
【００５０】
関数__update_addr()の処理はまさに本発明のプロセッサが備える演算器５０の処理である。従来のプロセッサは関数__update_addr()を実行するために複数の命令が必要となる。一方、本発明のプロセッサは関数__update_addr()と等価な処理を実行する演算器をもつので、関数__update_addr()を効率良く実行することができる。
【産業上の利用可能性】
【００５１】
本発明は、フィルタ、符号化、復号化などの画像処理を行なう装置に適用できる。
【図面の簡単な説明】
【００５２】
【図１】本発明の構成を示す図である。
【図２】「行構造の画像」を示す図である。
【図３】「ブロック構造の画像」を示す図である。
【図４】「ブロック構造の画像における行方向および列方向の画素アドレスの変化」を示す図である。
【図５】「ブロック構造の画像から矩形ブロック４×４をコピーするプログラム」を示す図である。
【図６】「行構造の画像とブロック構造の画像における画素の対応関係」を示す図である。
【符号の説明】
【００５３】
１０    アドレスレジスタ
２０    ステップレジスタ
３０    ギャップレジスタ
４０    キャリーポジションレジスタ
５０    演算器
【図１】
2007249515.tif 000003
【図２】
2007249515.tif 000004
【図３】
2007249515.tif 000005
【図４】
2007249515.tif 000006
【図５】
2007249515.tif 000007
【図６】
2007249515.tif 000008