(57)【要約】【課題】  キャッシュミスを少なくし、データ伝送時間及びデータの転送量を削減することが可能な信号処理装置を提供する。【解決手段】  信号処理装置１は、主メモリ１０の第１メモリ領域１１及び第２メモリ領域１２の第１テーブル１３及び第２テーブル１４を用いてデコード処理を行う。信号処理装置１は、第１テーブル１３及び第２テーブル１４のデータを一時格納するためのキャッシュメモリ３４と、キャッシュメモリ３４を介して第１メモリ領域１１及び第２メモリ領域１２の少なくとも１つにアクセスすることによってデータを読み出すプロセッサ２０と、キャッシュメモリ３４に一時格納する空き領域が不足した場合に、キャッシュメモリ３４に空き領域を確保する制御部５１とを備え、制御部５１は、第１メモリ領域１１のデータが第２メモリ領域１２のデータよりも優先してキャッシュメモリ３４に保持されるように、空き領域を確保する。【選択図】        図１
2005259120.tif 000002
【特許請求の範囲】
【請求項１】
第１及び第２メモリ領域のデータを用いて信号処理を行う信号処理装置であって、
前記データを一時格納するためのキャッシュメモリと、
前記キャッシュメモリを介して前記第１及び第２メモリ領域の少なくとも１つにアクセスすることによって前記データを読み出すアクセス手段と、
前記キャッシュメモリに一時格納する空き領域が不足した場合に、前記キャッシュメモリに空き領域を確保する制御手段とを備え、
前記制御手段は、前記第１メモリ領域のデータが前記第２メモリ領域のデータよりも優先して前記キャッシュメモリに保持されるように、前記空き領域を確保する
ことを特徴とする信号処理装置。
【請求項２】
前記信号処理装置はさらに、前記第１メモリ領域が前記第２メモリ領域よりも強度が強いことを示す強度属性を格納する属性格納手段を備え、
前記制御手段は、前記属性格納手段に格納された強度属性に応じて、前記キャッシュメモリに保持するデータを決定する
ことを特徴とする請求項１記載の信号処理装置。
【請求項３】
前記アクセス手段は、前記第１メモリ領域については、前記第１メモリ領域のデータを前記キャッシュメモリに移してからアクセスし、前記第２メモリ領域については、前記第２メモリ領域のデータを前記キャッシュメモリに移さないでアクセスする
ことを特徴とする請求項１記載の信号処理装置。
【請求項４】
前記第１メモリ領域は、前記第２メモリ領域よりもアクセス頻度が高いデータを格納する
ことを特徴とする請求項１記載の信号処理装置。
【請求項５】
前記第１及び第２メモリ領域は、それぞれ、入力データを一定規則に従って変換するための変換規則を示す第１及び第２テーブルを保持し、
前記制御手段は、前記第２テーブルのデータが前記第１テーブルのデータよりも優先して前記キャッシュメモリから廃棄されるように、前記空き領域を確保する
ことを特徴とする請求項１記載の信号処理装置。
【請求項６】
前記信号処理装置はさらに、前記第１テーブルが前記第２テーブルよりも強度が強いことを示す強度属性を格納する属性格納手段を備え、
前記制御手段は、前記属性格納手段に格納された強度属性に応じて、前記キャッシュメモリから廃棄するデータを決定する
ことを特徴とする請求項５記載の信号処理装置。
【請求項７】
前記信号処理装置は、入力データであるハフマン符号をデコードする装置であり、
前記ハフマン符号は、符号長の最長ビットがＮビットであり、
前記第１テーブルは、ｎを１以上でＮ未満の整数としたときに、ｎビット以下の符号データをデコードするためのテーブルであり、
前記第２テーブルは、前記ｎビットよりも長い符号データをデコードするためのテーブルである
ことを特徴とする請求項５記載の信号処理装置。
【請求項８】
第１及び第２メモリ領域と、前記データを一時格納するためのキャッシュメモリと、前記キャッシュメモリを介して前記第１及び第２メモリ領域にアクセスすることによって前記データを読み出すアクセス手段とを備えるキャッシュメモリ装置のための制御方法であって、
前記キャッシュメモリに一時格納する空き領域が不足した場合に、前記第１メモリ領域のデータが前記第２メモリ領域のデータよりも優先して前記キャッシュメモリに保持されるように、前記空き領域を確保するステップを含む
ことを特徴とするキャッシュメモリの制御方法。
【請求項９】
第１及び第２メモリ領域のデータを用いて信号処理を行う信号処理装置のためのプログラムであって、
請求項８記載の制御方法に含まれるステップをコンピュータに実行させる
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１及び第２メモリ領域のデータを用いて信号処理を行う信号処理装置に関し、特にキャッシュメモリを介して第１及び第２メモリ領域にアクセスし、第１及び第２メモリ領域のデータを読み出すことにより信号処理を行う信号処理装置に関する。
【背景技術】
【０００２】
例えば、音楽データについて例えばＭＰＥＧ−ＡＡＣ規格のハフマンコードブック（例えば、８）を用いてハフマン符号にエンコードし、再生の際にエンコードされた符号をデコードするような信号処理が行われる。
【０００３】
図２２は、ＭＰＥＧ−ＡＡＣ規格のハフマンコードブック８を示している。
このコードブックを用いてどのようにハフマンデコードが行われるか以下説明する。
【０００４】
例えば、ハフマン符号化された入力のビット列が、「０１１１０１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」と続いているとする。
【０００５】
その場合、最初の５ビットが、当該テーブルの最初のエントリ「０１１１０」に合致するので、デコード結果は「０」となり、当該符号長は５ビットであることがわかる。さらに、続くビットが、「１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」となっているので、最初の６ビットが、当該テーブルの４番目のエントリ「１１００００」に合致するので、デコード結果は「３」となり、当該符号長は６ビットであることがわかる。さらに、続くビットが、「１１１１１１０１１０１０００１１１１ｘｘｘｘ」となっているので、最初の９ビットが、当該テーブルの最後から３番目のエントリ「１１１１１１０１１」に合致するので、デコード結果は「６１」となり、当該符号長は９ビットであることがわかる。さらに、続くビットが、「０１０００１１１１ｘｘｘｘ」となっているので、最初の４ビットが、当該テーブルの１１番目のエントリ「０１００」に合致するので、デコード結果は「１０」となり、当該符号長は４ビットであることがわかる。さらに、続くビットが、「０１１１１ｘｘｘｘ」となっているので、最初の５ビットが、当該テーブルの１７番目のエントリ「０１１１１」に合致するので、デコード結果は「１６」となり、当該符号長は５ビットであることがわかる。
【０００６】
このように、ハフマンコードブック８の各行を総当たり方式でサーチすることによりハフマンデコードが行われる。
【０００７】
しかしながら、このデコード方法は、一致するハフマン符号が見つかるまでハフマンコードブック８を何度もサーチする必要があるため、非常に多くの処理時間を必要とするという問題を有している。
【０００８】
このため、本願に係る発明者らは、ハフマンデコード処理を高速に行うための装置を発明した（例えば、特許文献１参照）。
【０００９】
この発明を適用した従来の技術を、ＭＰＥＧ−ＡＡＣ規格のハフマンコードブック８を用いてエンコードされた符号をデコードする過程を例にとり、以下説明する。
【００１０】
図２３は、ハフマンデコード処理を高速に行うための２つのテーブルを示す図である。特に図２３（ａ）は第１テーブル５０００を、図２３（ｂ）は第２テーブル６０００を、それぞれ示している。
【００１１】
これらの第１及び第２テーブル５０００，６０００は、ＳＲＡＭ等のメモリの所定のアドレスに記憶され、デコーダがハフマンコードのビット列に基づいて第１及び第２テーブル５０００，６０００を引くことによりデコード処理が行われる。
【００１２】
この２つの第１及び第２テーブル５０００，６０００を用いる場合、入力のビット列は、以下のようにデコードされる。
【００１３】
例えば、入力のビット列が、先の例と同様「０１１１０１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」と続いている場合、デコーダは、まず最初の６ビットを取り出し、当該６ビットをアドレスとして、第１テーブル５０００を引く。この場合、「０１１１０１」をアドレスとして第１テーブル５０００を引くので、デコーダは、図２３（ａ）中に示される１回目のアクセスポイントα１をアクセスし、符号長が５ビットで、デコード結果が「０」であることがわかる。そして、デコーダは、符号長が５ビットであったので、上記ビット列を５ビット進めると、ビット列は「１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」となる。
【００１４】
次に、デコーダは、先ほどと同様に当該ビット列の最初の６ビットを取り出し、取り出した６ビットをアドレスとして、第１テーブル５０００を引く。この場合、「１１００００」をアドレスとして、第１テーブル５０００を引くので、デコーダは、図２３（ａ）中に示される２回目のアクセスポイントα２をアクセスし、符号長が６ビットで、デコード結果が「３」であることがわかる。そして、符号長が６ビットであったので、上記ビット列を６ビット進めると、ビット列は「１１１１１１０１１０１０００１１１１ｘｘｘｘ」となる。
【００１５】
さらに、デコーダは、先ほどと同様に当該ビット列の最初の６ビットを取り出し、取り出した６ビットをアドレスとして、第１テーブル５０００を引く。この場合、「１１１１１１」をアドレスとして、第１テーブル５０００を引くので、図２３（ａ）中に示される３回目のアクセスポイントα３をアクセスし、未完了記号「１５」、次のアドレスポインタ「１１０００１０」、次に読み込むビット数４を得るので、図２３（ｂ）に示される第２テーブル６０００のアドレス「１１０００１０」にポインタを進め、上記ビット列を６ビット進めた後にさらに４ビットを取得し、当該４ビットをアドレス「１１０００１０」からのインデックスとし第２テーブル６０００を引く。この場合、当該４ビットの値が「０１１０」であるので、図２３（ｂ）中に示される４回目のアクセスポイントα４をアクセスすることになるので、デコーダは、符号長が３ビットで、デコード結果が「６１」であることがわかる。そして、上記符号長が３ビットであったので上記ビット列を３ビット進めると、ビット列は「０１０００１１１１ｘｘｘｘ」となる。
【００１６】
次に、デコーダは、先ほどと同様に当該ビット列の最初の６ビットを取り出し、当該６ビットをアドレスとして、第１テーブル５０００を引く。この場合、「０１０００１」をアドレスとして第１テーブル５０００を引くので、デコーダは、図２３（ａ）中に示される５回目のアクセスポイントα５をアクセスし、符号長が４ビットで、デコード結果で「１０」であることがわかる。上記符号長が４ビットであったので上記ビット列を４ビット進めると、ビット列は「０１１１１ｘｘｘｘ」となる。
【００１７】
次に、デコーダは、先ほどと同様に当該ビット列の最初の６ビットを取り出し、当該６ビットをアドレスとして、第１テーブル５０００を引く。この場合、「０１１１１ｘ」をアドレスとして、第１テーブル５０００を引くので、図２３（ａ）中に示す、６回目のアクセスポイントα６をアクセスし、符号長が５ビットで、デコード結果が「１６」であることがわかる。
【００１８】
上記のような処理過程をみると明らかなように、符号長の短い符号（発生頻度の高い符号）に対しては、１回のテーブルアクセスでハフマンデコードが完了し、符号長の長い符号（発生頻度の低い符号）に対してのみ、２回のテーブルアクセスでハフマンデコードが完了するので、平均として高速な信号処理が実現できる。
【００１９】
上記が、筆者らが発明した従来の技術である。
ところで、近年、携帯電話機などのようなコンピュータ装置においては、電話をしたりするだけでなく、オーディオの再生だけでなく、ビデオを再生したり、メールを送受信したりできるように、多機能化が図られている。
【００２０】
このような複数の機能を実現するために、各機能毎にその機能専用の回路を設けると、回路規模が膨大となる。このため、必要に応じてテーブル等のデータを外部メモリ等に格納し、信号処理に必要なときに外部メモリのデータをキャッシュメモリに格納することで、レスポンスを落とさずに、各機能を実現することが考えられている。
【００２１】
このような、キャッシュメモリを搭載した演算装置（信号処理装置）で、上記のようなハフマンデコード処理を行う場合がある。この場合の従来の技術について述べるが、まず、キャッシュメモリの振る舞いについて、簡単に説明する。
【００２２】
図２４は、主メモリ１０００と、プロセッサ２０００と、キャッシュメモリ装置３０００との関係を示した図である。
【００２３】
キャッシュメモリ装置３０００は、図２４に示されるようにデータを格納するためのキャッシュメモリ３１００と、リプレース制御するための制御部３２００とを備える。
【００２４】
キャッシュメモリ３１００は、ラインと呼ばれる単位でデータが管理される。通常、ラインのサイズは、３２バイトとか１２８バイトといった値であり、キャッシュメモリのサイズは、１６ｋバイトとか３２ｋバイトといった値であるので、キャッシュメモリ３１００は、数百から数千のラインで区切られているが、ここでは、説明を簡明にするために、４つのラインで区切られているものとして説明する。
【００２５】
主メモリ１０００の記憶領域も、当該ラインサイズ毎に区切られる。そして、主メモリ１０００の何番目のラインがキャッシュメモリ３１００のデータエリア３４００のどこに格納されているかということは、キャッシュメモリ３１００内のタグ情報のエリア（タグエリア）３３００で管理される。
【００２６】
この図２４では、主メモリ１０００のＬｉｎｅ１，Ｌｉｎｅ３，Ｌｉｎｅ６，Ｌｉｎｅ８のデータがキャッシュメモリ３１００のデータエリア３４００に格納され、当該ラインを識別するための情報がタグエリア３３００に格納されている状態が示されている。
【００２７】
従って、プロセッサ２０００は、主メモリ１０００の当該ライン（Ｌｉｎｅ１，Ｌｉｎｅ３，Ｌｉｎｅ６，Ｌｉｎｅ８）のデータをアクセスする場合は、キャッシュメモリ３１００をアクセスすることで行える。
【００２８】
しかしながら、例えば主メモリ１０００のＬｉｎｅ９をアクセスする場合は、当該領域が今、キャッシュメモリ３１００に格納されておらず、かつ、既にキャッシュメモリ３１００内に空き領域がないので、キャッシュメモリ３１００に今格納されているいずれかのラインのデータを一旦、主メモリ１０００に書き戻すことによって、キャッシュメモリ３１００に空き領域を確保し、当該空いた領域にＬｉｎｅ９のデータを格納することになる。
【００２９】
このようなキャッシュメモリ３１００を搭載した信号処理装置で、先に説明したハフマンデコード処理を行う場合、例えば、ＭＰＥＧオーディオのＡＡＣ方式の場合、大きなメモリ領域を必要とするので、主メモリ１０００にハフマンデコードに必要なすべてのテーブルデータを格納しておいて、逐次、キャッシュメモリ３１００にデータを移しながらハフマンデコード処理を行うことになる。
【００３０】
なお、ここで、アクセスとは、アドレスを指定してデータを読み出したり、書き込んだりすることを意味する。
【特許文献１】特開２０００−２８６７１７号公報
【発明の開示】
【発明が解決しようとする課題】
【００３１】
しかしながら、キャッシュメモリを用いた信号処理装置で上記に示したハフマンデコード処理を行うと、以下に示すような問題が生じる。
【００３２】
図２５は、キャッシュメモリ３１００を用いてハフマンデコードを行う場合の従来の信号処理装置の構成を示すブロック図である。なお、従来の信号処理装置と、本願発明に係る信号処理装置との相違をより明確にするために、ここでは第１及び第２テーブル５０００，６０００に代えて、後述する第１及び第２テーブル１３，１４を用いた場合について説明する。
【００３３】
信号処理装置は、図２５に示されるように、主メモリ１０００、アクセス手段としてのプロセッサ２０００及びキャッシュメモリ３１００とを備え、主メモリ１０００の第１メモリ領域１００１に第１テーブル１３が格納され、主メモリ１０００の第２メモリ領域１００２に第２テーブル１４が格納されることにより構成される。
【００３４】
第１テーブル１３は、８つのライン（Ｌｉｎｅ０〜Ｌｉｎｅ７）から構成されており、第２テーブル１４は７つのライン（Ｌｉｎｅ８〜Ｌｉｎｅ１４）から構成されている。第１テーブル１３及び第２テーブル１４のそれぞれの具体的内容を、図２，図３にそれぞれ示す。第１テーブル１３及び第２テーブル１４は、従来の技術で先に示した図２３（ａ），図２３（ｂ）と同様のデータを格納したテーブルであるが、キャッシュメモリの構成に併せてラインサイズ毎に区切られている点が異なる。
【００３５】
さて、今、入力のビット列が、先の例と同様に「０１１１０１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」と続いている場合、プロセッサ２０００は、まず、当該ビット列の最初の６ビットをアドレスとして、第１テーブル１３を引く。この場合、「０１１１０１」をアドレスとして、第１テーブル１３を引くが、当該アドレスが図２に示されるようにＬｉｎｅ３にあたるので、当該Ｌｉｎｅ３のデータが主メモリ１０００からキャッシュメモリ３１００に移された後（図２６参照）、プロセッサ２０００は、当該データをアクセスし、符号長が５ビットで、デコード結果が「０」であることがわかる。上記符号長が５ビットであったので、プロセッサ２０００は、上記ビット列を５ビット進める。そうすると、次のビット列は、「１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」となる。
【００３６】
次に、プロセッサ２０００は、先ほどと同様に、当該ビット列の最初の６ビットをアドレスとして、第１テーブル１３を引く。この場合、「１１００００」をアドレスとして、第１テーブル１３を引くが、当該アドレスは、図２に示されるようにＬｉｎｅ６にあたるので、当該Ｌｉｎｅ６のデータが主メモリ１０００からキャッシュメモリ３１００に移された後（図２７参照）、プロセッサ２０００は、当該データをアクセスし、符号長が６ビットで、デコード結果が「３」であることがわかる。上記符号長が６ビットであったので上記ビット列を６ビット進めると、ビット列は「１１１１１１０１１０１０００１１１１ｘｘｘｘ」となる。
【００３７】
さらに、先ほどと同様に、プロセッサ２０００は、当該ビット列の最初の６ビットをアドレスとして、第１テーブル１３を引く。この場合、「１１１１１１」をアドレスとして、第１テーブル１３を引くが、当該アドレスは、図２に示されるようにＬｉｎｅ７にあたるので、プロセッサ２０００は、当該Ｌｉｎｅ７のデータが主メモリ１０００からキャッシュメモリ３１００に移された後（図２８参照）、当該データにアクセスし、未完了記号「１５」、次のアドレスポインタ「１１０００１０」、次に読み込むビット数「４」を得る。
【００３８】
そこで、プロセッサ２０００は、第２テーブル１４のアドレス「１１０００１０」にポインタを進め、上記ビット列を６ビット進めた後に、続く４ビットの値をアドレス「１１０００１０」からのインデックスとし第２テーブル１４を引く。この場合、当該４ビットの値は、「０１１０」であるので、アドレス「１１０００１０」に「０１１０」を足して、次にアクセスするアドレスは「１１０１０００」となる。つまり、プロセッサ２０００は、次のアドレスポインタ「１１０００１０」に「０１１０」を足して、次にアクセスするアドレス「１１０１０００」を算出する。
【００３９】
このアドレスは図３に示されるように、Ｌｉｎｅ１３にあたるので、プロセッサ２０００は、当該Ｌｉｎｅ１３のデータが主メモリ１０００からキャッシュメモリ３１００に移された後（図２９参照）、当該データをアクセスし、符号長が３ビットで、デコード結果が「６１」であることがわかる。上記符号長が３ビットであったので上記ビット列を３ビット進めると、ビット列は「０１０００１１１１ｘｘｘｘ」となる。
【００４０】
次に、先ほどと同様に、プロセッサ２０００は、当該ビット列の最初の６ビットをアドレスとして、第１テーブル１３を引く。この場合、「０１０００１」をアドレスとして、第１テーブル１３を引くが、当該アドレスは、図２に示されるようにＬｉｎｅ２にあたるので、当該Ｌｉｎｅ２のデータが主メモリ１０００からキャッシュメモリ３１００に移された後、当該データにアクセスしようとする。
【００４１】
ところが今、キャッシュメモリに空き領域はない。このようにキャッシュメモリ３１００を埋め尽くしたデータに必要なデータがない場合、すなわちキャッシュミスした場合、制御部３２００は、キャッシュメモリ３１００に格納されているいずれかのラインのデータを主メモリ１０に書き戻し、それによって生じた空き領域に当該Ｌｉｎｅ２のデータを移す必要がある。
【００４２】
このようなキャッシュミスが発生した場合、通常、一番過去にアクセスされたＬｉｎｅが書き戻されるので、この場合、制御部３２００は、Ｌｉｎｅ３を書き戻し（図３０参照）、そこにＬｉｎｅ２のデータを移す（図３１参照）。その後、プロセッサ２０００は、当該Ｌｉｎｅ２のデータをアクセスし、符号長が４ビットで、デコード結果が「１０」であることがわかる。上記符号長が４ビットであったので上記ビット列を４ビット進めると、ビット列は「０１１１１ｘｘｘｘ」となる。
【００４３】
さて次に、先ほどと同様に、プロセッサ２０００は当該ビット列の最初の６ビットをアドレスとして、第１テーブル１３を引く。この場合、「０１１１１ｘ」をアドレスとして、第１テーブル１３を引くが、当該アドレスは、図２に示されるようにＬｉｎｅ３にあたるので、当該Ｌｉｎｅ３のデータを主メモリ１０００からキャッシュメモリ３１００に移した後、当該データにアクセスしようとする。ところが今、キャッシュメモリに空き領域はないので、制御部３２００は、キャッシュメモリ３１００に格納されているいずれかのラインのデータを主メモリ１０００に書き戻し、それによって生じた空き領域に当該Ｌｉｎｅ３のデータを移す。
【００４４】
このようなキャッシュミスが発生した場合、通常、ＬＲＵ方式により一番過去にアクセスされたＬｉｎｅが書き戻されるので、この場合、制御部３２００は、Ｌｉｎｅ６を書き戻し（図３２参照）、そこにＬｉｎｅ３のデータを移す（図３３参照）。その後、プロセッサ２０００は、当該Ｌｉｎｅ３のデータをアクセスし、符号長が５ビットで、デコード結果１６であることがわかる。
【００４５】
なお、上記過程において、上記説明では、Ｌｉｎｅ３のデータや、Ｌｉｎｅ６のデータがキャッシュメモリ３１００から主メモリ１０００に書き戻されるとしたが、本一連の動作の過程では、Ｌｉｎｅ３のデータや、Ｌｉｎｅ６のデータは、キャッシュメモリに格納されている間に値が変化していないので、つまりキャッシュメモリ上での値と主メモリ１０００上での値が同一であるので、従来の多くのキャッシュメモリの制御方法では、書き戻すという動作はなく、Ｌｉｎｅ２のデータをＬｉｎｅ３のデータが格納されていたキャッシュメモリ３１００上に上書きしたり、Ｌｉｎｅ３のデータをＬｉｎｅ６のデータが格納されていたキャッシュメモリ上に上書きする、という処理が行われることになる。
【００４６】
しかしながら、上記過程から明らかなように、ＬＲＵ方式でリプレース対象を決定しているので、キャッシュミスが多発するという問題がある。このようなキャッシュミスの多発は、短い時間の間に、主メモリ１０００とキャッシュメモリ３１００の間でＬｉｎｅ３等のデータ転送が複数回（２回）発生し、データの転送に多大の時間を要し、消費電力も増加するという問題を招く。
【００４７】
このような問題は、デコード処理の場合に限られず、キャッシュメモリを介して第１及び第２メモリ領域にアクセスし、第１及び第２メモリ領域のデータを読み出すことにより信号処理を行う信号処理装置一般にいえることである。
【００４８】
本発明は、このような従来の問題点に鑑みてなされたものであって、キャッシュメモリを用いた信号処理装置において、キャッシュミスを少なくし、データ伝送時間及びデータの転送量を削減することが可能な信号処理装置を提供することを目的とする。
【課題を解決するための手段】
【００４９】
ところで、本願発明者は、キャッシュメモリを用いた従来の技術を解析したところ、デコード処理において第１テーブル１３へのアクセス頻度が８５％で、第２テーブル１４へのアクセス頻度が１５％である。これにも拘わらず、従来ではＬＲＵ方式により第２テーブルのデータをキャッシュメモリに残すアルゴリズムを採用していたため、入れ替えアルゴリズム（Ｒｅｐｌａｃｅｍｅｎｔ  Ａｌｇｏｒｉｔｈｍ）が不適切であることを発見し、本考案を案出するに至った。
【００５０】
そこで、上記目的を達成するために、本発明に係る信号処理装置においては、第１及び第２メモリ領域のデータを用いて信号処理を行う信号処理装置であって、前記データを一時格納するためのキャッシュメモリと、前記キャッシュメモリを介して前記第１及び第２メモリ領域の少なくとも１つにアクセスすることによって前記データを読み出すアクセス手段と、前記キャッシュメモリに一時格納する空き領域が不足した場合に、前記キャッシュメモリに空き領域を確保する制御手段とを備え、前記制御手段は、前記第１メモリ領域のデータが前記第２メモリ領域のデータよりも優先して前記キャッシュメモリに保持されるように、前記空き領域を確保することを特徴とする。
【００５１】
この構成により、第１メモリ領域にアクセス頻度の高いデータを格納しておけば、リプレースメント  アルゴリズムが適切となる。したがって、キャッシュメモリを用いた信号処理装置において、キャッシュミスを少なくし、データ伝送時間及びデータの転送量を削減した信号処理装置を提供することが可能となる。
【００５２】
また、本発明に係る信号処理装置においては、前記信号処理装置はさらに、前記第１メモリ領域が前記第２メモリ領域よりも強度が強いことを示す強度属性を格納する属性格納手段を備え、前記制御手段は、前記属性格納手段に格納された強度属性に応じて、前記キャッシュメモリに保持するデータを決定することを特徴とすることができる。
【００５３】
この構成により、リプレースメント  アルゴリズムが確実に適切となり、第２メモリ領域のデータに対して割り当てられるキャッシュメモリのデータ領域を最小限にすますことができる。
【００５４】
また、本発明に係る信号処理装置においては、前記アクセス手段は、前記第１メモリ領域については、前記第１メモリ領域のデータを前記キャッシュメモリに移してからアクセスし、前記第２メモリ領域については、前記第２メモリ領域のデータを前記キャッシュメモリに移さないでアクセスすることを特徴としてもよい。
【００５５】
この構成により、リプレースメント  アルゴリズムが確実に適切となり、第２メモリ領域のデータに対して割り当てられるキャッシュメモリのデータ領域をなくし、キャッシュメモリデータ領域をすべて第１メモリ領域のデータに対して割り当てることができる。
【００５６】
また、本発明に係る信号処理装置においては、前記第１メモリ領域は、前記第２メモリ領域よりもアクセス頻度が高いデータを格納することを特徴とすることもできる。
【００５７】
この構成により、リプレースメント  アルゴリズムを確実に適切とすることができる。
また、本発明に係る信号処理装置においては、前記第１及び第２メモリ領域は、それぞれ、入力データを一定規則に従って変換するための変換規則を示す第１及び第２テーブルを保持し、前記制御手段は、前記第２テーブルのデータが前記第１テーブルのデータよりも優先して前記キャッシュメモリから廃棄されるように、前記空き領域を確保することを特徴とすることができる。
【００５８】
この構成により、第１メモリ領域にアクセス頻度の高い第１テーブルを格納しておけば、リプレースメント  アルゴリズムが適切となる。したがって、キャッシュメモリを用いた信号処理装置において、キャッシュミスを少なくし、データ伝送時間及びデータの転送量を削減しつつ、入力データを一定規則に従って変換する信号処理装置を提供することが可能となる。
【００５９】
また、本発明に係る信号処理装置においては、前記信号処理装置はさらに、前記第１テーブルが前記第２テーブルよりも強度が強いことを示す強度属性を格納する属性格納手段を備え、前記制御手段は、前記属性格納手段に格納された強度属性に応じて、前記キャッシュメモリから廃棄するデータを決定することを特徴としてもよい。
【００６０】
この構成により、第１メモリ領域にアクセス頻度の高い第１テーブルを格納しておけば、リプレースメント  アルゴリズムが確実に適切となり、第２メモリ領域のデータに対して割り当てられるキャッシュメモリのデータ領域を最小限にすますことができる。
【００６１】
また、本発明に係る信号処理装置においては、前記信号処理装置は、入力データであるハフマン符号をデコードする装置であり、前記ハフマン符号は、符号長の最長ビットがＮビットであり、前記第１テーブルは、ｎを１以上でＮ未満の整数としたときに、ｎビット以下の符号データをデコードするためのテーブルであり、前記第２テーブルは、前記ｎビットよりも長い符号データをデコードするためのテーブルであることを特徴とすることもできる。
【００６２】
この構成により、第１メモリ領域にアクセス頻度の高い符号長の短いハフマン符号デコード用の第１テーブルが格納されるので、リプレースメント  アルゴリズムが確実に適切となり、第２メモリ領域のデータに対して割り当てられるキャッシュメモリのデータ領域を最小限にすますことができる。
【００６３】
なお、本発明は、このような信号処理装置として実現することができるだけでなく、このような信号処理装置が備える特徴的な手段をステップとする信号処理方法として実現したり、それらのステップをコンピュータに実行させるプログラムとして実現したりすることもできる。そして、そのようなプログラムは、ＣＤ−ＲＯＭ等の記録媒体やインターネット等の伝送媒体を介して配信することができるのはいうまでもない。
【発明の効果】
【００６４】
以上の説明から明らかなように、本発明に係る信号処理装置によれば、第１メモリ領域にアクセス頻度の高いデータを格納しておけば、リプレースメント  アルゴリズムが適切となるので、キャッシュメモリを用いた信号処理装置において、キャッシュミスを少なくし、データ伝送時間及びデータの転送量を削減した信号処理装置を提供することが可能となる。
【００６５】
よって、本発明により、キャッシュミスが少なく、データ伝送時間及びデータの転送量を削減した信号処理が可能となり、多機能の携帯電話機などのコンピュータ装置が普及してきた今日における本願発明の実用的価値は極めて高い。
【発明を実施するための最良の形態】
【００６６】
以下、本発明の実施の形態に係る信号処理装置について図面を参照しながら説明する。
＜全体構成＞
（実施の形態１）
図１は、本発明の実施の形態１に係る信号処理装置１の全体構成を示すブロック図である。なお、図１では、信号処理装置１を、図２２のＭＰＥＧ−ＡＡＣ規格のハフマンコードブック（例えば、８）を用いてハフマン符号にエンコードされたビット列をデコードするデコーダとして機能させる場合が図示されている。
【００６７】
図１に示されるように信号処理装置１は、主メモリ１０と、アクセス手段としてのプロセッサ２０と、キャッシュメモリ装置３０等とを備える。
【００６８】
主メモリ１０は、ＤＲＡＭ等により構成され、第１メモリ領域１１に１段階でデコード処理するための１段階用の第１テーブル１３を、第２の領域１２に２段階でデコード処理するための２段階用の第２テーブル１４を、それぞれ記憶する。
【００６９】
キャッシュメモリ装置３０は、ＳＲＡＭ等により構成され、タグエリア、データエリア、データエリアに残る確率の高さである強度の属性を示すウィークフラグＷ、書き戻しの要否を表すダーティフラグＤ等を記憶するキャッシュメモリ３４と、リプレース制御を行う制御部５１と、キャッシュメモリ３４に残る確率の高さを設定するためデータ（属性データ）を格納する属性格納部５２等とを備え、いわゆるＬＲＵ方式によってアクセス順序の古いキャッシュエントリをリプレースするリプレース制御を前提とした上で、リプレース対象を決定するためのアクセス順序を示す順序データを、アクセス順序に反して改変することにより、アクセス頻度の低いデータを保持するキャッシュエントリをリプレース対象としてキャッシュメモリから追い出すよう構成されている。具体的には、アクセス順序が最古であるとみなすことを示すウィークフラグＷをキャッシュエントリに付加することによって、順序データを間接的に改変している。これにより順序データを直接改変する複雑な回路を不要としている。
【００７０】
プロセッサ２０は、デコード処理を開始するにあたって、主メモリ１０の第１メモリ領域１１に第１テーブル１３を、第２メモリ領域１２に第２テーブル１４を書き込んだり、予め定められた属性値設定データに基づいて、属性格納部５２に強度属性を設定したりする。そして、プロセッサ２０は、デコード対象のハフマン符号列をアドレスとしてキャッシュメモリにアクセスすることにより、デコード結果を取得する。
【００７１】
図２は第１テーブル１３の構成を示す図であり、図３は第２テーブル１４の構成を示す図である。
【００７２】
第１テーブル１３及び第２テーブル１４は、入力データを一定規則に従って変換するための変換規則を示すものであり、具体的には、エンコードの際に用いられたハフマンコードブックに対応し、第１メモリ領域１１と第２メモリ領域１２とにそれぞれマップされる。
【００７３】
第１テーブル１３は、ビットストリームから読み出した所定ビット数データに含まれ得る、所定数（６ビット）以下のビット数を有する比較的符号長の短いハフマン符号をデコード結果にデコードするためのテーブルである。また、第２テーブル１４は、短いハフマン符号でデコードが完了しなかった場合に第１テーブル１３により取得されるアドレスポインタと、次の取得点で示されるビット長のハフマン符号とに基づいて算出される所定数を超えるビット数を有する比較的符号長の長いハフマン符号をデコードするためのテーブルである。このように、比較的短いハフマン符号と比較的長いハフマン符号とは、第１テーブル１３及び第２テーブル１４を用いた処理によってデコードされる。
【００７４】
第１テーブル１３は、図２に示されるように、符号長又は未完了記号（ここでは、「１５」）のデータが格納される欄と、デコード結果又は次のアドレスのデータが格納される欄と、次の取得長のデータが格納される欄とから構成される。なお、この第１テーブル１３の左側には、説明の便宜のため、これらのデータが格納されるアドレスと、ラインとが示されている。
【００７５】
第２テーブル１４は、図３に示されるように、符号長のデータが格納される欄と、デコード結果のデータが格納される欄とから構成される。この第２テーブル１４の左側には、説明の便宜のため、アドレスを求めるための次のインデックスデータと、これらのデータが格納されるアドレスと、ラインとが示されている。
【００７６】
なお、ハフマンエンコードにおいては、一般に出現頻度のより高い入力値に対して、より短いハフマン符号が割り当てられ、出現頻度のより低い入力値に対して、より長いハフマン符号が割り当てられる。したがって、デコード処理においては、第２テーブル１４よりも第１テーブル１３の方がアクセス頻度が高いことになる。
【００７７】
図４は、属性格納部５２に格納される属性データの内容の一例を示した図である。
この場合、第１テーブル１３にあたるＬｉｎｅ０からＬｉｎｅ７は強度が大（ウィークフラグＷが「０」）で、第２テーブル１４にあたるＬｉｎｅ８からＬｉｎｅ１４は強度が小（ウィークフラグＷが「１」）であることが示されている。このような強度属性が設定されることにより、適切なリプレイスメント  アルゴリズムが発揮され、キャッシュミスが減少されることになる。
＜キャッシュメモリ装置の具体的構成＞
図５は、キャッシュメモリ装置３０の具体的構成例を示すブロック図である。なお、ここではキャッシュメモリ装置３０の具体例として、４ウェイ・セット・アソシエイティブ方式のキャッシュメモリに本発明を適用した場合の構成について説明する。
【００７８】
図５に示されるように、キャッシュメモリ装置３０は、アドレスレジスタ３１、メモリＩ／Ｆ３２、デコーダ３３、４つのウェイ３４ａ〜３４ｄ（以下「ウェイ０〜３」とも略記する。）、４つの比較器３５ａ〜３５ｄ、４つのアンド回路３６ａ〜３６ｄ、セレクタ３８、セレクタ３９、デマルチプレクサ４１及びキャッシュ制御部４２を備える。キャッシュ制御部４２は、リプレース部４２ａと、Ｗフラグ設定部４２ｂとを含む。
【００７９】
なお、このキャッシュメモリ装置３０の具体例におけるリプレース部４２ａは図１の制御部５１に該当し、Ｗフラグ設定部４２ｂは図１の属性格納部５２に該当する。
【００８０】
アドレスレジスタ３１は、主メモリ１０へのアクセスアドレスを保持するレジスタである。このアクセスアドレスは３２ビットであるものとする。図５に示されるように、アクセスアドレスは、最上位ビットから順に、２１ビットのタグアドレス、４ビットのセットインデックス（図５中のＳＩ）、５ビットのワードインデックス（図５中のＷＩ）を含む。ここで、タグアドレスは、ウェイにマッピングされるメモリ中の領域（そのサイズはセット数×ブロックである）を指す。この領域のサイズは、タグアドレスよりも下位のアドレスビット（Ａ１０〜Ａ０）で定まるサイズつまり２ｋバイトであり、１つのウェイのサイズでもある。セットインデックス（ＳＩ）は、ウェイ０〜３に跨る複数セットの１つを指す。このセット数は、セットインデックスが４ビットなので１６セットある。タグアドレス及びセットインデックスで特定されるキャッシュエントリは、リプレース単位であり、キャッシュメモリに格納されている場合はラインデータ又はラインと呼ばれる。ラインデータのサイズは、セットインデックスよりも下位のアドレスビットで定まるサイズつまり１２８バイトである。１ワードを４バイトとすると、１ラインデータは３２ワードである。ワードインデックス（ＷＩ）は、ラインデータを構成する複数ワード中の１ワードを指す。アドレスレジスタ３１中の最下位２ビット（Ａ１、Ａ０）は、ワードアクセス時には無視される。
【００８１】
メモリＩ／Ｆ３２は、主メモリ１０からキャッシュメモリ装置３０へのデータのロードや、キャッシュメモリ装置３０から主メモリ１０へのデータのライトバック等、キャッシュメモリ装置３０から主メモリ１０をアクセスするためのＩ／Ｆである。
【００８２】
デコーダ３３は、セットインデックスの４ビットをデコードし、４つのウェイ０〜３に跨る１６セット中の１つを選択する。
【００８３】
４つのウェイ０〜３は、同じ構成を有する４つのウェイであり、４×２ｋバイトの容量を有する。各ウェイは、１６個のキャッシュエントリを有する。
【００８４】
図６は、図５に示される１つのキャッシュエントリにおける詳細なビット構成を示す図である。
【００８５】
図６に示されるように、１つのキャッシュエントリは、バリッドフラグＶ０〜Ｖ３、２１ビットのタグ、１２８バイトのラインデータ、ウィークフラグＷ、ダーティフラグＤ０〜Ｄ３を有する。
【００８６】
タグは、２１ビットのタグアドレスのコピーである。
ラインデータは、タグアドレス及びセットインデックスにより特定されるブロック中の１２８バイトデータのコピーであり、３２バイトの４つのサブラインからなる。
【００８７】
バリッドフラグＶ０〜Ｖ３は、４つのサブラインに対応し、サブラインが有効か否かを示す。
【００８８】
ウィークフラグＷは、当該キャッシュエントリのアクセス順序が最も古いものとみなすためのフラグである。つまり、Ｗ＝１のとき、プロセッサ２０からは当該キャッシュエントリにこれ以上読み出しも書き込みもなされないこと、あるいはアクセス頻度が低いことを意味する。また、Ｗ＝１のとき、キャッシュメモリ装置３０においては、リプレース制御に関してアクセス順序が最古であると取り扱うこと、つまり、最弱（ウィーク）のキャシュエントリーであることを意味する。Ｗ＝０のとき、そうでないことを意味する。
【００８９】
ダーティフラグＤ０〜Ｄ３は、４つのサブラインに対応し、そのサブラインにプロセッサ２０から書き込みがあったか否かを示す。つまり、サブライン中にキャッシュされたデータが存在するが、書き込みにより主メモリ１０中のデータと異なるため、主メモリ１０に書き戻すことが必要か否かを示す。
【００９０】
比較器３５ａは、アドレスレジスタ３１中のタグアドレスと、セットインデックスにより選択されたセットに含まれる４つのタグ中のウェイ０のタグとが一致するか否かを比較する。比較器３５ｂ〜３５ｃについても、ウェイ３４ｂ〜３４ｄに対応すること以外は同様である。
【００９１】
アンド回路３６ａは、バリッドフラグと比較器３５ａの比較結果とが一致するか否かを比較する。比較結果が「１」である場合は、アドレスレジスタ３１中のタグアドレス及びセットインデックスに対応するラインデータが存在すること、つまりウェイ０においてヒットしたことを意味する。比較結果が「０」である場合は、キャッシュミスしたことを意味する。アンド回路３６ｂ〜３６ｄについても、ウェイ３４ｂ〜３４ｄに対応すること以外は同様である。その比較結果は、ウェイ１〜３でヒットしたかキャッシュミスしたかを、それぞれ意味する。
【００９２】
セレクタ３８は、選択されたセットにおけるウェイ０〜３のラインデータのうち、ヒットしたウェイのラインデータを選択する。
【００９３】
セレクタ３９は、セレクタ３８により選択された３２ワードのラインデータのうち、ワードインデックスに示される１ワードを選択する。
【００９４】
デマルチプレクサ４１は、キャッシュエントリにデータを書き込む際に、ウェイ０〜３の１つに書き込みデータを出力する。この書き込みデータはワード単位でよい。
【００９５】
キャッシュ制御部４２は、キャッシュメモリ装置３０の全体の制御を行う。特に、Ｗフラグの設定とＷフラグに従うリプレース制御を行う。
【００９６】
図７は、キャッシュ制御部４２の構成を示すブロック図である。
キャッシュ制御部４２は、上記したように図１の制御部５１に該当するリプレース部４２ａと、図１の属性格納部５２に該当するＷフラグ設定部４２ｂとを含む。
【００９７】
リプレース部４２ａは、キャッシュミスによるリプレースに際して、Ｗ＝１が設定されているキャッシュエントリが存在すれば、当該キャッシュエントリのアクセス順序が最も古いとみなしてリプレース対象として選択し、リプレースを行う。
【００９８】
Ｗフラグ設定部４２ｂは、プロセッサ２０からのコマンドに応じてウィークフラグＷを設定する。プロセッサ２０は、もはや書き込みも読み出しもしないキャッシュエントリについてウィークフラグＷの設定を指示するコマンドをキャッシュメモリ装置３０に対して発行する。
【００９９】
図８は、Ｗフラグ設定部４２ｂの構成例を示すブロック図である。
図８に示されるように、Ｗフラグ設定部４２ｂは、コマンドレジスタ４２１、スタートアドレスレジスタ４２２、サイズレジスタ４２３、スタートアライナ４２４、加算器４２５、エンドアライナ４２６、フラグ書換部４２７を備える。
【０１００】
コマンドレジスタ４２１は、プロセッサ２０から直接アクセス可能なレジスタであり、プロセッサ２０により書き込まれたＷフラグ設定コマンドを保持する。
【０１０１】
図９（ａ）に、コマンドレジスタ４２１にコマンドを書き込む命令の一例を示す。
この命令は、通常の転送命令（ｍｏｖ命令）であり、ソースオペランドとしてコマンドを、デスティネーションオペランドとしてコマンドレジスタ（ＣＲ）を指定している。
【０１０２】
図９（ｂ）に、コマンドの一例を示す。このコマンドは、Ｗフラグ設定コマンドを示す特定のコードである。Ｗフラグ設定コマンドは、スタートアドレスレジスタ４２２に保持されたスタートアドレスからサイズレジスタ４２３に保持されたサイズのアドレス範囲に対応するデータを保持するキャッシュエントリに対して、Ｗフラグを設定することを指示するコマンドである。
【０１０３】
スタートアドレスレジスタ４２２は、プロセッサ２０から直接アクセス可能なレジスタであり、プロセッサ２０により書き込まれたスタートアドレスを保持する。このスタートアドレスはＷフラグを設定すべきアドレス範囲の開始位置を示す。
【０１０４】
図９（ｃ）に、スタートアドレスレジスタ４２２にスタートアドレスを書き込む命令の一例を示す。この命令も、図９（ａ）と同様に通常の転送命令（ｍｏｖ命令）である。
【０１０５】
サイズレジスタ４２３は、プロセッサ２０から直接アクセス可能なレジスタであり、プロセッサ２０により書き込まれたサイズを保持する。このサイズは、スタートアドレスからのアドレス範囲を示す。
【０１０６】
図９（ｄ）に、サイズレジスタ４２３にサイズを書き込む命令の一例を示す。この命令も、図９（ａ）と同様に通常の転送命令（ｍｏｖ命令）である。なお、サイズの単位は、バイト数であっても、ライン数（キャッシュエントリ数）であってもよく、予め定められた単位であればよい。
【０１０７】
スタートアライナ４２４は、スタートアドレスをライン境界の位置に調整する。この調整によりプロセッサ２０はラインサイズ及びライン境界とは無関係に任意のアドレスをスタートアドレスとして指定することができる。
【０１０８】
加算器４２５は、スタートアドレスレジスタ４２２に保持されたスタートアドレスとサイズレジスタ４２３に保持されたサイズとを加算する。加算結果は、アドレス範囲の終了位置を指すエンドアドレスである。加算器４２５は、サイズがバイト数指定の場合はバイトアドレスとして加算し、サイズがライン数指定の場合はラインアドレスとして加算すればよい。
【０１０９】
エンドアライナ４２６は、エンドアドレスをライン境界の位置に調整する。この調整によりプロセッサ２０はラインサイズ及びライン境界とは無関係に任意の大きさを上記サイズとして指定することができる。
【０１１０】
図１０に、スタートアライナ４２４及びエンドアライナ４２６の説明図を示す。
図１０において、プロセッサ２０から指定されたスタートアドレスはラインＮの途中の任意の位置を指す。スタートアライナ４２４は、次のライン（Ｎ＋１）の先頭を指すよう調整し、調整後のアドレスをアラインスタートアドレスとして出力する。アラインスタートアドレスが指すラインをスタートラインと呼ぶ。
【０１１１】
また、エンドアドレスはラインＭの途中の任意の位置を指す。エンドアライナ４２６は、直前のライン（Ｍ−１）の先頭を指すよう調整し、調整後のアドレスをアラインエンドアドレスとして出力する。アラインエンドアドレスが指すラインをエンドラインと呼ぶ。
【０１１２】
この場合、スタートライン（ライン（Ｎ＋１））からエンドライン（ライン（Ｍ−１））までの各ライン（キャッシュエントリ）にＷフラグが設定されることになる。このように、スタートアライナ４２４及びエンドアライナ４２６がプロセッサ２０から指定されたスタートアドレスからエンドアドレスまでのアドレス範囲よりも内側にアラインしているのは、ラインＮとラインＭの外側の部分にはプロセッサ２０から読み出し又は書き込みが発生する可能性があるからである。
【０１１３】
フラグ書換部４２７は、アラインスタートアドレスが指すラインからアラインエンドアドレスが指すラインまで（図１０の例ではライン（Ｎ＋１）からライン（Ｍ−１）まで）、キャッシュメモリ装置３０にエントリされていればＷフラグを１に設定する。
＜Ｗフラグ設定処理＞
図１１は、フラグ書換部４２７におけるＷフラグ設定処理の一例を示すフローチャートである。
【０１１４】
フラグ書換部４２７は、コマンドレジスタ４２１にＷフラグ設定コマンドが保持されている場合、スタートラインからエンドラインまでの各ラインアドレスを順に出力しながらループ１の処理（Ｓ８２〜Ｓ８６）を行う。フラグ書換部４２７は、各ラインについて同じ処理を行うので、ここでは１ライン分の処理について説明する。
【０１１５】
すなわち、フラグ書換部４２７は、キャッシュメモリ装置３０がプロセッサ２０からアクセスされていない間に、ラインアドレスをアドレスレジスタ３１に出力し（Ｓ８３）、アドレスレジスタ３１のタグアドレスとキャッシュエントリのタグとを比較器３５ａ〜３５ｄに比較させ、ヒットするかどうかを判定する（Ｓ８４）。さらにフラグ書換部４２７は、ヒットした場合には、ヒットしたキャッシュエントリに対してＷフラグを１にセットし（Ｓ８５）、キャッシュミスした場合には、キャッシュメモリにエントリされていないので、なにもしない。
【０１１６】
これにより、スタートラインからエンドラインまでの各ラインについて、キャッシュメモリ装置３０にエントリされている場合には、Ｗフラグが「１」に設定される。
＜リプレース処理＞
図１２は、リプレース部４２ａにおけるリプレース処理を示すフローチャートである。
【０１１７】
同図１２においてリプレース部４２ａは、メモリアクセスがキャッシュミスしたとき（Ｓ９１）、セットインデックスにより選択されたセットにおける、４つウェイのウィークフラグＷを読み出し（Ｓ９２）、４つのウィークフラグの論理和が１であるか否か、つまりＷ＝１のウェイが存在するか否かを判定する（Ｓ９３）。Ｗ＝１のウェイが存在すると判定された場合、当該キャッシュエントリのアクセス順序が最も古いとみなしてＷ＝１のウェイを１つ選択し（Ｓ９４）、Ｗ＝１のウェイが存在しないと判定された場合、通常のＬＲＵ方式によりウェイを１つ選択する（Ｓ９５）。このとき、ウィークフラグＷが１になっているウェイが複数存在する場合は、リプレース部４２ａはランダムに１つを選択する。
【０１１８】
さらに、リプレース部４２ａは、当該セットにおける選択されたウェイのキャッシュエントリを対象にリプレースし（Ｓ９６）、リプレース後に当該キャッシュエントリのウィークフラグＷを０初期化する（Ｓ９７）。なお、このときバリッドフラグＶ、ダーティフラグＤは、それぞれ１、０に初期化される。
【０１１９】
このように、Ｗ＝１のウェイが存在しない場合、リプレース対象は、通常のＬＲＵ方式により選択される。また、Ｗ＝１のウェイが存在する場合、リプレース対象は、Ｗ＝１のウェイのアクセス順序が最も古いものと取り扱われる結果、Ｗ＝１のウェイのキャッシュエントリが選択される。これにより、アクセス頻度の低いＷ＝１のデータがキャッシュメモリに存在するために生じるキャッシュミスを低減することができる。
【０１２０】
以上説明してきたように、本実施の形態１におけるキャッシュメモリによれば、ウィークフラグＷ＝１のラインは、プロセッサからこれ以上読み出しも書き込みもなされないラインであり、そのアクセス順序が最古として取り扱われる結果、真っ先にリプレース対象として選択される。これによりアクセス頻度の低いデータによるキャッシュミスの誘発を低減することができる。
【０１２１】
また、従来のＬＲＵ方式におけるアクセス順序を示す順序データを直接改変することなく、間接的にＷフラグを付加することによってアクセス順序を改変しているので、複雑なハードウェア回路を追加することなく、実現することができる。
【０１２２】
次いで、信号処理装置１の各部が実行する動作を説明する。
図１３から図１９は、キャッシュメモリ３４に格納されるデータの流れを示した図である。
【０１２３】
本実施の形態１では、図２２のＭＰＥＧ−ＡＡＣ規格のハフマンコードブック８を用いてエンコードされた符号をデコードする信号処理装置１を例にとり説明する。
【０１２４】
なお、従来の信号処理装置との動作の差異を明らかにするために、キャッシュメモリ３４の１つのウェイの４セットだけを使用するものとし、また、入力のビット列が、従来と同様「０１１１０１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」と続いているものとして説明する。
【０１２５】
図１３に示されるように、プロセッサ２０は、まず、当該ビット列の最初の６ビット「０１１１０１」をアドレスとして、第１テーブル１３を引く。この場合、当該アドレス「０１１１０１」がＬｉｎｅ３にあたるので（図２参照）、当該Ｌｉｎｅ３のデータが主メモリ１０からキャッシュメモリ３４に移された後、アドレス「０１１１０１」のデータをアクセスし、符号長５ビットと、デコード結果「０」とを取得する。
【０１２６】
より詳しくは、プロセッサ２０は、キャッシュメモリ装置３０に対して、ビット列の最初の６ビット「０１１１０１」をアドレスとして、リード信号を出力する。「０１１１０１」をアドレスとするリード信号を受信したキャッシュメモリ装置３０は、キャッシュメモリ３４にＬｉｎｅ３のデータが存在しないので、Ｌｉｎｅ３の先頭から最終までをアドレス指定することによりＬｉｎｅ３のデータをキャッシュメモリ３４の１つのセットに書き込む。そして、タグにはＬｉｎｅ３が、Ｗフラグには「０」が、ダーティフラグＤには「０」が書き込まれる。これらの書き込みが終わると、キャッシュメモリ装置３０は、アドレス「０１１１０１」のデータ、符号長５ビットと、デコード結果「０」とをプロセッサ２０に出力する。
【０１２７】
そして、符号長５ビットと、デコード結果「０」とを取得すると、プロセッサ２０は、後の信号処理（逆量子化処理、ＩＭＤＣＴ（Ｉｎｖｅｒｓｅ  Ｍｏｄｉｆｉｅｄ  Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）処理等）を行うためにデコード結果「０」をバッファ等に出力した後、上記符号長が５ビットであったので、上記ビット列を５ビット進める。つまり、取得点Ｐを５ビット移動させる。そうすると、次のビット列は「１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」となる。
【０１２８】
次のビット列が「１１００００１１１１１１０１１０１０００１１１１ｘｘｘｘ」である場合、図１４に示されるように、先ほどと同様に、プロセッサ２０は、当該ビット列の最初の６ビット「１１００００」をアドレスとして、第１テーブル１３を引く。この場合、当該アドレス「１１００００」がＬｉｎｅ６にあたるので（図２参照）、当該Ｌｉｎｅ６のデータが主メモリ１０からキャッシュメモリ３４に移された後（図１４）、当該アドレス「１１００００」のデータをアクセスし、符号長６ビット、デコード結果「３」を取得する。
【０１２９】
なお、タグにはＬｉｎｅ６が、Ｗフラグには「０」が、ダーティフラグＤには「０」が書き込まれる。
【０１３０】
そして、プロセッサ２０は、デコード結果「３」を出力した後、上記符号長が６ビットであったので、上記ビット列を６ビット進める。つまり、取得点Ｐを６ビット移動させる。上記符号長が６ビットであったので、上記ビット列を６ビット進めると、次のビット列は「１１１１１１０１１０１０００１１１１ｘｘｘｘ」となる。
【０１３１】
次のビット列が「１１１１１１０１１０１０００１１１１ｘｘｘｘ」である場合、図１５に示されるように、プロセッサ２０は、先ほどと同様に、当該ビット列の最初の６ビット「１１１１１１」をアドレスとして、第１テーブル１３を引く。この場合、当該アドレス「１１１１１１」がＬｉｎｅ７にあたるので（図２参照）、当該Ｌｉｎｅ７のデータが主メモリ１０からキャッシュメモリ３４に移された後、当該アドレス「１１１１１１」のデータにアクセスし、未完了記号「１５」、次のアドレスポインタ「１１０００１０」、次に読み込むビット数「４」を取得する。
【０１３２】
なお、タグにはＬｉｎｅ７が、Ｗフラグには「０」が、ダーティフラグＤには「０」が書き込まれる。ここで、キャッシュメモリ装置３０のデータの取得動作については、上記の場合と同様であるので、その説明を以下省略する。
【０１３３】
そこで、図３に示した第２テーブル１４のアドレス「１１０００１０」にポインタを進め、上記ビット列を６ビット進めた後に、続く４ビットの値をアドレス「１１０００１０」からのインデックスとし、第２テーブル１４を引く。この場合、当該４ビットの値は、「０１１０」であるので、アドレス「１１０００１０」に「０１１０」を足して、次にアクセスするアドレスは「１１０１０００」となる。
【０１３４】
つまり、プロセッサ２０は、図１６に示されるように、次の４ビット「０１１０」を取得し、先に取得したアドレス「１１０００１０」に次の４ビット「０１１０」を足して、次にアクセスするアドレスを「１１０１０００」を計算する。
【０１３５】
計算が終わると、プロセッサ２０は、計算により得られた「１１０１０００」をアドレスとして、第２テーブル１４を引く。このアドレス「１１０１０００」がＬｉｎｅ１３にあたるので（図３参照）、当該Ｌｉｎｅ１３のデータが主メモリ１０からキャッシュメモリ３４に移された後、プロセッサ２０は、当該データをアクセスし、符号長３ビット、デコード結果「６１」を取得する。
【０１３６】
なお、タグにはＬｉｎｅ１３が、Ｗフラグには「１」が、ダーティフラグＤには「０」が書き込まれる。
【０１３７】
そして、プロセッサ２０は、デコード結果「６１」を出力した後、上記符号長が３ビットであったので、上記ビット列を３ビット進める。つまり、取得点Ｐを６＋３＝９ビット移動させる。取得点Ｐを移動させると、次のビット列は「０１０００１１１１ｘｘｘｘ」となる。
【０１３８】
次のビット列が「０１０００１１１１ｘｘｘｘ」である場合、図１７に示されるように、プロセッサ２０は、先ほどと同様に、当該ビット列の最初の６ビット「０１０００１」をアドレスとして、第１テーブル１３を引く。この場合、当該アドレス「０１０００１」がＬｉｎｅ２にあたるので（図２参照）、当該Ｌｉｎｅ２のデータを主メモリ１０からキャッシュメモリ３４に移した後、当該データにアクセスする必要がある。
【０１３９】
ところで、今、キャッシュメモリ３４に空き領域はないので、キャッシュメモリ３４に格納されているいずれかのラインのデータを主メモリ１０に書き戻し、それによって生じた空き領域に当該Ｌｉｎｅ２のデータを移す必要がある。
【０１４０】
さてここで、制御部５１は、属性格納部５２で指定されている主メモリ１０の第１メモリ領域１１及び第２メモリ領域１２の強度情報に基づいて、キャッシュメモリ３４に格納されているいずれかのラインのデータを主メモリ１０に書き戻すかを決定する。この場合、第１テーブル１３にあたるＬｉｎｅ０からＬｉｎｅ７は強度が大で、第２テーブル１４にあたるＬｉｎｅ８からＬｉｎｅ１４は強度が小であることが示されている（図４参照）。このため、第２テーブル１４のデータで、現在、キャッシュメモリ３４上に格納されているデータを主メモリ１０に書き戻す。つまり現在Ｌｉｎｅ１３のデータがキャッシュメモリ３４に格納されているので、このデータが主メモリ１０に書き戻され（図１７）、それによって生じた空き領域にＬｉｎｅ２のデータが移される（図１８）。
【０１４１】
その後、プロセッサ２０は、当該Ｌｉｎｅ２のデータをアクセスし、符号長４ビット、デコード結果１０を取得する。上記符号長が４ビットであったので上記ビット列を４ビット進めると、ビット列は「０１１１１ｘｘｘｘ」となる。
【０１４２】
この過程において、上記説明では、Ｌｉｎｅ１３のデータがキャッシュメモリ３４から主メモリ１０に書き戻されるとしたが、本一連の動作の過程では、Ｌｉｎｅ１３のデータは、キャッシュメモリ３４に格納されている間に値が変化していないので、つまりキャッシュメモリ３４上での値と主メモリ１０上での値とが同一であるので、従来の多くのキャッシュメモリの制御方法では、書き戻すという動作はなく、Ｌｉｎｅ２のデータをＬｉｎｅ１３のデータ上に上書きする、ということになる。
【０１４３】
すなわち、キャッシュメモリ３４に空きがない場合、従来では、ＬＲＵ方式により、Ｌｉｎｅ３のデータをリプレース対象に決定し、そのライン上にＬｉｎｅ２のデータを上書きしている。これに対して、本実施の形態１の制御部５１は、キャッシュメモリ３４のウィークフラグＷに「１」がセットされているラインをサーチし、Ｌｉｎｅ１３のデータをリプレース対象に決定する。そして、制御部５１は、Ｌｉｎｅ１３のダーティフラグＤの値が「０」のままであるのを確認し、そのライン上にＬｉｎｅ２のデータを上書きするようにしている。
【０１４４】
これにより、アクセス頻度の高いデータがキャッシュメモリ３４に残るので、ヒットの確率が高くなり、キャッシュミスが生じる確率が低くなることになる。
【０１４５】
次のビット列が「０１１１１ｘｘｘｘ」である場合、プロセッサ２０は、先ほどと同様に、当該ビット列の最初の６ビットをアドレスとして、第１テーブル１３を引く。この場合、当該アドレス「０１１１１ｘ」は、Ｌｉｎｅ３にあたる（図２参照）。今、当該Ｌｉｎｅ３のデータは、キャッシュメモリ３４に格納されているので、ヒットし、プロセッサ２０は、直ちに当該アドレス「０１１１１ｘ」のデータをアクセスし、直ちに符号長５ビット、デコード結果１６を取得する。
【０１４６】
この過程においては、先に説明した従来の技術では、キャッシュメモリ３４に空き領域はない場合、通常、一番過去にアクセスされたＬｉｎｅが書き戻されるので、Ｌｉｎｅ３のデータが複数回、主メモリ１０とキャッシュメモリ３４の間で移動を繰り返したが、上記制御部５１（リプレース部４２ａ）と上記属性格納部５２（Ｗフラグ設定部４２ｂ）との働きによって、アクセス頻度の高いデータが優先的にキャッシュメモリ３４のデータエリア上に残るように制御され、結果として、主メモリ１０とキャッシュメモリ３４の間でのデータの移動回数を削減できる。
【０１４７】
以上のように本実施の形態１によれば、主メモリ１０の第１のメモリ領域１１と、第２のメモリ領域１２と、当該メモリ領域１１，１２のデータを一時格納するキャッシュメモリ３４と、キャッシュメモリ３４を介して上記第１、第２のメモリ領域１１，１２にアクセスするためのプロセッサ２０と、上記キャッシュメモリ３４に空き領域が不足した場合、空き領域を確保する制御部５１とを用いて、上記制御部５１において、上記第１のメモリ領域１１のデータ（第１テーブル１３）を優先的にキャッシュメモリ３４に保持するようにしながら空き領域を確保するようにすることによって、主メモリ１０とキャッシュメモリ３４との間の転送回数を削減できることとなる。
【０１４８】
なお、本実施の形態におけるハフマンデコード処理では、第１のメモリ領域１１に１回アクセスすることでデコードが完了するか、第１のメモリ領域１１に１回アクセスした後、第２のメモリ領域１２に１回アクセスすることでデコードが完了するか、の２種類の過程でデコードが完了するような処理について説明したが、必ずしもそのようなものである必要はない。
【０１４９】
例えば、特開２０００−２８６７１７号公報（実施の形態１）で示されるように、１回メモリにアクセスすることでデコードが完了するか、そうでない場合は、さらに１回以上の複数回メモリにアクセスすることでデコードを完了させるという処理であってもよい。その場合、たとえば、１回目にアクセスされる可能性があるメモリ領域を本実施の形態でいうところの第１のメモリ領域１１に割り当て、２回目以降にアクセスされる可能性のあるメモリ領域を本実施の形態でいうところの第２のメモリ領域１２に割り当てればよい。
【０１５０】
あるいは、比較的小さな整数をｍとしたとき、ｍ回目までにアクセスされる可能性があるメモリ領域を本実施の形態でいうところの第１のメモリ領域１１に割り当て、ｍ回目より後にアクセスされる可能性のあるメモリ領域を本実施の形態でいうところの第２のメモリ領域１２に割り当てるという方法もある。
【０１５１】
この場合についても、第１のメモリ領域１１のデータ（第１テーブル５０００）を優先的にキャッシュメモリ３４に保持するようにしながら空き領域を確保するようにすることによって、主メモリ１０とキャッシュメモリ３４との間の転送回数を従来より大幅に削減できることとなる。
【０１５２】
（実施の形態２）
次いで、本発明の実施の形態２に係る信号処理装置２について説明する。
【０１５３】
ところで、実施の形態１の信号処理装置１では、制御部５１を設けて、アクセス頻度の低いデータがキャッシュメモリに残らないようにしている。つまり、信号処理装置１においては、第２テーブル１４のデータをキャッシュメモリ３４に一旦格納し、空きがない場合には第２テーブル１４のデータをリプレースの対象にしている。
【０１５４】
しかしながらそうすると、その分第１テーブル１３のデータがキャッシュメモリ３４に存在する確率が低くなる。すなわち、第１テーブル１３のデータに対する割り当て領域が減ることになる。
【０１５５】
そこで、そもそもアクセス頻度の低いデータがキャッシュメモリに格納されないように制御するようにしている。
【０１５６】
その場合は、図２０に示すような構成になる。
すなわち、図２０に示されるように、信号処理装置２は、主メモリ１０と、プロセッサ２０と、キャッシュメモリを介して主メモリ１０にアクセスする機能と、キャッシュメモリを介さずに主メモリ１０にアクセスする機能とを備えるキャッシュメモリ装置６０とを備え、主メモリ１０の第１メモリ領域１１に格納され、キャッシュメモリを介してアクセスされる第１テーブル１３と、主メモリ１０の第２メモリ領域１２に格納され、キャッシュメモリを介さずにアクセスされる第２テーブル１４とで構成される。
【０１５７】
キャッシュメモリ装置６０は、キャッシュメモリ６１と、制御部６２と、アクセス制御部６３と、属性格納部６４等とからなる。
【０１５８】
キャッシュメモリ６１は、キャッシュメモリ３４からウィークフラグＷを削除した構成である。
【０１５９】
制御部６２は、通常のＬＲＵ方式でリプレース対象を決定する。
属性格納部６４は、プロセッサ２０から出力された属性を設定するコマンドに基づいて強度属性のデータを格納する。
【０１６０】
図２１は、属性格納部６４に格納される属性データの内容の一例を示した図である。
この場合、第１テーブル１３にあたるＬｉｎｅ０からＬｉｎｅ７は強度が大（キャッシュ）で、第２テーブル１４にあたるＬｉｎｅ８からＬｉｎｅ１４は強度が小（ノンキャッシュ）であることが示されている。このような強度属性が設定されることにより、適切なリプレイスメント  アルゴリズムが発揮され、キャッシュミスが減少されることになる。
【０１６１】
アクセス制御部６３は、属性格納部６４に格納されたデータに基づいて、キャッシュメモリ６１を介してアクセスするか、第２テーブル１４にアクセスするかを決定する。具体的には、プロセッサ２０がアクセスするアドレスがＬｉｎｅ０〜Ｌｉｎｅ７の範囲である場合には、アクセス制御部６３は、キャッシュメモリ６１をイネーブルにし、キャッシュメモリ６１を介するＬｉｎｅ０〜Ｌｉｎｅ７のデータの読み出しを仲介する。プロセッサ２０がアクセスするアドレスがＬｉｎｅ８〜Ｌｉｎｅ１４の範囲である場合には、アクセス制御部６３は、キャッシュメモリ６１をディスエーブルにし、主メモリ１０の第２メモリ領域１２に格納された第２テーブル１４の該当アドレスのデータに直接アクセスし、読み出したデータをプロセッサ２０に出力する。
【０１６２】
このような構成により、プロセッサ２０は、第１テーブル１３にアクセスするときは上記キャッシュメモリ６１を介してアクセスし、第２テーブル１４にアクセスするときはキャッシュメモリ６１を介さないでアクセスすることができ、アクセス頻度の低い第２テーブル１４のデータがキャッシュメモリ６１に格納されないようにすることができる。
【０１６３】
これにより、アクセス頻度の高い第１テーブル１３のデータが一度キャッシュメモリに格納されるとそのまま保持される可能が高まり、結果として、主メモリ１０とキャッシュメモリ６１との間の転送回数を削減できることとなる。
＜変形例＞
なお、本発明のキャッシュメモリは、上記の実施の形態１の構成に限るものではなく、種々の変形が可能である。以下、変形例のいくつかについて説明する。
【０１６４】
（１）  上記実施の形態１では、ウィークフラグＷによりアクセス順序が最古であることを示しているが、アクセス順序が最新又は最古でないことを示すものとしてもよい。この場合、リプレース部４２ａは、Ｗ＝１のキャッシュエントリは最古でないとみなして、リプレース対象として選択せず、他のキャッシュエントリを選択する構成とすればよい。最古でないことを示すウィークフラグＷを、アクセス頻度の高いデータあるいはアクセス頻度が中くらいのデータを保持するキャッシュエントリに付加することにより、無駄リプレースを防止することができる。
【０１６５】
（２）  プロセッサ２０が、ウィークフラグＷ＝１の設定とデータの書き込みとを命令する特別なストア命令を実行し、キャッシュ制御部４２は、さらに、特別なストア命令を検出する命令検出部と、当該ストア命令による書き込みの際にＷ＝１に設定するフラグ設定部とを備える構成としてもよい。
【０１６６】
（３）  上記実施の形態１では、４ウェイ・セット・アソシエイティブのキャッシュメモリを例に説明したが、ウェイ数は、いくつでもよい。また、上記実施の形態１では、セット数が１６である例を説明したが、セット数はいくつでもよい。
【０１６７】
（４）  上記実施の形態１では、セット・アソシエイティブのキャッシュメモリを例に説明したが、フル・アソシエイティブ方式のキャッシュメモリであってもよい。
【０１６８】
（５）  上記実施の形態１では、サブラインのサイズをラインのサイズの１／４としているが、１／２、１／８、１／１６等他のサイズでもよい。その場合、各キャッシュエントリは、サブラインと同数のバリッドフラグ及びダーティフラグをそれぞれ保持すればよい。
【０１６９】
（６）  また、上記実施の形態では、音楽データのエンコードデータについて例えばＭＰＥＧ−ＡＡＣ規格のハフマンコードブック（例えば、８）に対応するテーブルを用いてデコードする場合について説明したが、他のコードブックに対応したテーブルを用いてデコードする場合に適用できる。また、ＭＰ３等のエンコードデータをデコードする場合にも適用できる。さらに、圧縮符号化された映像データ等をデコードするような種々の信号処理に適用できるのは、いうまでもない。
【産業上の利用可能性】
【０１７０】
本発明に係る信号処理装置は、キャッシュミスを低減し、キャッシュメモリと主メモリとの間のデータ転送時間・量を削減する効果を有し、プロセッサと記憶装置によって構成される機器、例えば、パーソナルコンピュータ等において有用である。また、デジタル化されたオーディオ信号やビデオ信号をプロセッサと記憶装置によって処理する機器、例えば、デジタルテレビ、ＤＶＤ機器、携帯電話機、携帯情報端末、ヘッドホンステレオ等の用途に応用できる。
【図面の簡単な説明】
【０１７１】
【図１】本発明の実施の形態１に係る信号処理装置１の構成を示す図である。
【図２】第１テーブル１３の内容の一例を示した図である。
【図３】第２テーブル１４の内容の一例を示した図である。
【図４】属性格納部５２が格納するデータ内容の一例を示した図である。
【図５】図１に示されるキャッシュメモリ装置３０の構成例を示すブロック図である。
【図６】キャッシュエントリの詳細なビット構成を示す。
【図７】キャッシュ制御部４２の構成を示すブロック図である。
【図８】Ｗフラグ設定部の構成例を示すブロック図である。
【図９】（ａ）コマンドレジスタにコマンドを書き込む命令の一例を示す図である。（ｂ）コマンドの一例を示す図である。（ｃ）スタートアドレスレジスタにスタートアドレスを書き込む命令の一例を示す図である。（ｄ）サイズレジスタにサイズを書き込む命令の一例を示す図である。
【図１０】スタートアライナ及びエンドアライナの説明図を示す図である。
【図１１】フラグ書換部におけるＷフラグ設定処理の示すフローチャートである。
【図１２】リプレース部におけるリプレース処理を示すフローチャートである。
【図１３】キャッシュメモリに格納されるデータの流れを示した図である。
【図１４】キャッシュメモリに格納されるデータの流れを示した図である。
【図１５】キャッシュメモリに格納されるデータの流れを示した図である。
【図１６】キャッシュメモリに格納されるデータの流れを示した図である。
【図１７】キャッシュメモリに格納されるデータの流れを示した図である。
【図１８】キャッシュメモリに格納されるデータの流れを示した図である。
【図１９】キャッシュメモリに格納されるデータの流れを示した図である。
【図２０】本発明の実施の形態２に係る信号処理装置２の構成を示すブロック図である。
【図２１】属性格納部６４が格納する属性データの内容の一例を示した図である。
【図２２】ＭＰＥＧ−ＡＡＣ規格のハフマンコードブック８を示す図である。
【図２３】（ａ）ハフマンデコード処理を高速に行うための第１テーブル５０００を示す図である。（ｂ）ハフマンデコード処理を高速に行うための第２テーブル６０００を示す図である。
【図２４】キャッシュメモリと主メモリとプロセッサとの関係を示した図である。
【図２５】従来のキャッシュメモリを用いてハフマンデコードを行う場合の構成図である。
【図２６】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図２７】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図２８】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図２９】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図３０】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図３１】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図３２】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【図３３】従来の技術によって、キャッシュメモリに格納されるデータの流れを示した図である。
【符号の説明】
【０１７２】
１０        主メモリ
１１        第１メモリ領域
１２        第２メモリ領域
１３        第１テーブル
１４        第２テーブル
２０        プロセッサ
３０，６０  キャッシュメモリ装置
３４，６１  キャッシュメモリ
５１，６２  制御部
５２，６４  属性格納部
【図１】
2005259120.tif 000003
【図２】
2005259120.tif 000004
【図３】
2005259120.tif 000005
【図４】
2005259120.tif 000006
【図５】
2005259120.tif 000007
【図６】
2005259120.tif 000008
【図７】
2005259120.tif 000009
【図８】
2005259120.tif 000010
【図９】
2005259120.tif 000011
【図１０】
2005259120.tif 000012
【図１１】
2005259120.tif 000013
【図１２】
2005259120.tif 000014
【図１３】
2005259120.tif 000015
【図１４】
2005259120.tif 000016
【図１５】
2005259120.tif 000017
【図１６】
2005259120.tif 000018
【図１７】
2005259120.tif 000019
【図１８】
2005259120.tif 000020
【図１９】
2005259120.tif 000021
【図２０】
2005259120.tif 000022
【図２１】
2005259120.tif 000023
【図２２】
2005259120.tif 000024
【図２３】
2005259120.tif 000025
【図２４】
2005259120.tif 000026
【図２５】
2005259120.tif 000027
【図２６】
2005259120.tif 000028
【図２７】
2005259120.tif 000029
【図２８】
2005259120.tif 000030
【図２９】
2005259120.tif 000031
【図３０】
2005259120.tif 000032
【図３１】
2005259120.tif 000033
【図３２】
2005259120.tif 000034
【図３３】
2005259120.tif 000035