(57)【特許請求の範囲】
【請求項１】
各々データを保持する複数の記憶素子と、
前記複数の記憶素子のそれぞれに対応して設けられ、前記複数の記憶素子を直列に接続して前記データに順序関係を持たせる複数の選択回路と、
データの挿入又は削除の位置を指定する位置選択信号と固定値との加算及び減算の一方の演算を行い、前記演算結果によるイネーブル信号を生成し、前記イネーブル信号で、前記記憶素子へのデータの保持又は前段の前記記憶素子のデータでの更新を制御する更新制御回路とを有し、
前記データの挿入時、前記位置選択信号により前記複数の選択回路を制御し、挿入するデータで、前記位置選択信号が指定する位置の記憶素子を更新する
ことを特徴とするリスト構造制御回路。
【請求項２】
前記選択回路は、
前記挿入の指示に応じて、対応する記憶素子の前段の記憶素子のデータ又は対応する記憶素子の後段の記憶素子のデータのいずれかを選択する第１の選択回路と、
前記位置選択信号により、前記第１の選択回路の出力と前記挿入するデータのいずれかを選択する第２の選択回路とを有する
ことを特徴とする請求項１のリスト構造制御回路。
【請求項３】
前記更新制御回路は、前記位置選択信号と前記固定値との加算又は減算を行うキャリーセレクトアダー回路を有する
ことを特徴とする請求項１のリスト構造制御回路。
【請求項４】
前記記憶素子は、
メモリと、
前記イネーブル信号により更新データで前記メモリを更新する更新回路とを有する
ことを特徴とする請求項１のリスト構造制御回路。
【請求項５】
前記複数の記憶素子の各々のエントリ番号と使用したエントリ番号とを比較し、前記位置選択信号を前記更新制御回路に出力する位置選択回路を更に有し、
前記更新制御回路は、削除指示に応じて、前記位置選択信号で指定された前記記憶素子のエントリ番号を削除し、且つ前記削除されたエントリ番号を前記複数の記憶素子の最終段の記憶素子に挿入して、ＬＲＵ動作を行う
ことを特徴とする請求項１のリスト構造制御回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、リスト構造制御回路に関する。
【背景技術】
【０００２】
リスト構造を用いたデータ表現は、ソフトウェア処理における基本的な手法の1つである。図２５乃至図２８は、従来のリスト構造の制御の説明図である。図２５は、片方向リンク・リストの説明図である。図２６は、両方向リンク・リストの説明図である。ソフトウェアでリスト構造のデータ管理を実行するには、メモリ上のデータとリンク情報とをまとめた構造体（要素）Ｅ１〜Ｅ３を用いて管理する。図２５、図２６に示すように、この構造体Ｅ１〜Ｅ３には、データ本体と、リンク先の構造体を示すポインタとが定義される。図２５に示す、片方向リンク・リストの場合には、次の構造体のアドレスを示すポインタが１つ、構造体に定義される。図２６に示す、双方向リンク・リストの場合には、次の構造体と、前の構造体を示すポインタが２つ、構造体に定義される。
【０００３】
リスト構造は、データの並びに意味があり（つまり順列）、かつ頻繁にデータの挿入、削除が繰り返される場合に、有効なデータ構造である。例えば、データを挿入する場合には、図２７のように、挿入するデータ前後の構造体Ｅ２，Ｅ３のポインタと、挿入するデータに対応する構造体Ｅ４のポインタとを書き換えるだけで良い。又、データを削除する場合には、図２８に示すように、削除する構造体Ｅ２にリンクする構造体Ｅ１，Ｅ３のポインタを書き換えのみである。
【０００４】
このリンク・リスト方式は、リストの先頭からＮ番目の要素にアクセスするためには、先頭からＮ−１回リンクを辿る必要があり、探索に時間がかかるという欠点がある。
【０００５】
一方、同様の処理に対してアレイ構造を利用する事もできる。アレイ構造は、データの並びに意味があり（つまり順列）、データの挿入、削除が行われない場合に有効なデータ構造である。リスト構造と異なり、どの要素も1回の参照で直接アクセスできるという利点があり、データに対してランダムアクセスが必要となる場合に有効な構造である。しかし、挿入、削除を行う場合には、挿入位置、あるいは削除位置から後ろのデータを全て１つずつ後ろ、または手前にコピーする処理が必要となり、要素数に比例した処理時間が必要となる。
【０００６】
以上からリスト構造とアレイ構造は用途に応じたトレードオフの関係にあり、いずれもソフトウェアにおけるアルゴリズムとデータ構造の基本であり、ソフトウェア上のリスト構造処理の提案が、なされている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２００８−５３０６８９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ソフトウェアにおけるリスト制御処理においては、データの挿入、削除操作に、リストを構成する多数の構造体の書き換え処理が必要となり、頻繁な操作を行うには、処理サイクルが長くなる。又、先頭からＮ番目の要素を調べる、といった操作には、先頭から順にリストを辿る操作が必要となるため、リストの規模に比例した処理時間が必要となる。
【０００９】
従って、本発明の目的は、ハードウェア化しても、高速なリスト操作を実現するリスト構造制御回路を提供することにある。
【課題を解決するための手段】
【００１０】
この目的の達成のため、リスト構造制御回路は、各々データを保持する複数の記憶素子と、前記複数の記憶素子のそれぞれに対応して設けられ、前記複数の記憶素子を直列に接続して前記データに順序関係を持たせる複数の選択回路と、データの挿入又は削除の位置を指定する位置選択信号と固定値との加算及び減算の一方の演算を行い、前記演算結果によるイネーブル信号を生成し、前記イネーブル信号で、前記記憶素子へのデータの保持又は前段の前記記憶素子のデータでの更新を制御する更新制御回路とを有し、前記データの挿入時、前記位置選択信号により前記複数の選択回路を制御し、挿入するデータで、前記位置選択信号が指定する位置の記憶素子を更新する。
【発明の効果】
【００１１】
複数の記憶素子を、選択回路を介し直列接続し、挿入又は削除の位置を指定する位置選択信号と固定値との加算及び減算の一方の演算結果で、記憶素子に、データの保持又は前段の前記記憶素子のデータでの更新を制御するため、高速なリスト操作を行うハードウェアを実現できる。
【図面の簡単な説明】
【００１２】
【図１】本発明のリスト構造制御回路の一実施の形態のブロック図である。
【図２】図１の記憶素子ネットワークの説明図である。
【図３】図２の記憶素子ネットワークの挿入動作の説明図である。
【図４】図２の記憶素子ネットワークの削除動作の説明図である。
【図５】図２の記憶素子ネットワークの削除及び挿入動作の説明図である。
【図６】図１の更新制御回路を加算器構成とした場合の遅延時間の説明図である。
【図７】図１の記憶素子ネットワークの回路図である。
【図８】図７の記憶エレメントの第１の実施の形態の回路図である。
【図９】図１の記憶エレメントの第２の実施の形態の回路である。
【図１０】図１の更新制御回路の第１の実施の形態の構成図である。
【図１１】図１０の更新制御回路の回路図である。
【図１２】図１１のハーフアダー（Half Adder）の回路図である。
【図１３】図１１のフルアダー（Full Adder）の回路図である。
【図１４】図１１の回路を、ＣＳＡ(Carry Select Adder)で構成した例の回路図である。
【図１５】図１の更新制御回路の第２の実施の形態の構成図である。
【図１６】図１５の更新制御回路の回路図である。
【図１７】図１乃至図１６のリスト構造制御回路の挿入動作の説明図である。
【図１８】図１乃至図１６のリスト構造制御回路の削除動作の説明図である。
【図１９】図１乃至図１８で説明したリスト構造制御回路を用いたＬＲＵ回路の一実施の形態のブロック図である。
【図２０】図１９の位置選択回路のブロック図である。
【図２１】比較例としての優先度表を用いたＬＲＵの説明図である。
【図２２】優先度表を用いたＬＲＵと、リストを用いる本実施の形態のハードウェア実装コストの比較を示す説明図である。
【図２３】図１９乃至図２０のＬＲＵ回路を適用した調停回路の構成図である。
【図２４】図１９乃至図２０のＬＲＵ回路を適用したキャッシュリプレース回路の構成図である。
【図２５】従来のソフトウェアによる片方向リンク・リストの説明図である。
【図２６】従来のソフトウェアによる両方向リンク・リストの説明図である。
【図２７】従来のリンク・リストを用いた挿入処理の説明図である。
【図２８】従来のリンク・リストを用いた削除処理の説明図である。
【発明を実施するための形態】
【００１３】
以下、実施の形態の例を、リスト構造制御回路、記憶素子ネットワーク、更新制御回路、リスト構造制御回路の動作、リスト構造制御回路を使用したＬＲＵ、リスト構造制御回路を使用した調停回路、リスト構造制御回路を使用したキャッシュリプレース回路、他の実施の形態の順で説明するが、開示の回路構成は、この実施の形態に限られない。
【００１４】
（リスト構造制御回路）
図１は、本発明のリスト構造制御回路の一実施の形態のブロック図、図２〜図６は、図１の記憶素子ネットワークの説明図である。
【００１５】
図１において、リスト構造制御回路１は、複数の記憶エレメント（Element）２０，２１、・・・２Ｎを直列に接続して構成された記憶素子ネットワーク２と、データの挿入・削除に応じて、記憶素子ネットワーク２の各記憶エレメント内の値を保持するか、あるいは記憶素子ネットワーク２の各記憶エレメントが保持する情報を更新するかを制御する更新制御回路３と、記憶素子ネットワーク２から削除したデータを外部に出力するための選択回路４とを有する。
【００１６】
更新制御回路３は、データの挿入または削除の操作を選択する指定信号（図１の「挿入か削除かの選択指定」に対応、以下、「操作選択信号」という）と、データの挿入または削除の操作の位置を指定する指定信号（図１の「挿入・削除位置の指定」に対応、以下、「操作位置」あるいは「選択信号」という）と、挿入する際のデータとを、制御インタフェースとして、入力する。また、選択回路４は、記憶素子ネットワーク２から削除したデータを、外部へ通知する。なお、削除したデータを外部に通知することにより、単なるデータの削除ではなく、任意位置のデータを取り出して、外部で利用する、といった用途にも、リスト構造制御回路１を用いる事ができる。
【００１７】
記憶素子ネットワーク２は、順序関係を持つデータを保持するために、複数の記憶エレメント２０，２１、・・・２Ｎをネットワークで接続した順序回路で構成され、１クロックにつき、１回のデータ挿入またはデータ削除を実現する。更新制御回路３は加減算回路を有し、外部から入力された操作位置ＳＥＬ［Ｎ：０］から各記憶エレメント２０、２１、・・・、２Ｎのイネーブル信号Ｅ［Ｎ：０］（Ｅ［０］〜Ｅ［Ｎ−１］）を生成し、操作選択信号と操作位置ＳＥＬ［Ｎ：０］とイネーブル信号Ｅ［Ｎ：０］とを、各記憶エレメント２０，２１、・・・、２Ｎに出力する。また、更新制御回路３は、操作選択信号が挿入指示を示している場合は、挿入データを出力して、各記憶エレメントの更新を行うなど、データ挿入、データ削除の制御を行う。
【００１８】
図１の記憶素子ネットワーク２を説明する。ハードウェア処理においては、動的に確保される記憶空間の扱い、即ち、構成を変更するのは難しい。このため、ハードウェアに、図２５〜図２８で示したソフトウェアで実行するリストをそのままの形で実装する事は難しい。この実施の形態では、ハードウェアの並列性を活用し、ソフトウェアで表現する配列（アレイ）構造を用いてリスト処理を実現するものである。
【００１９】
図２に示すように、記憶素子ネットワーク２は、データ１からデータＮが、順に並ぶように、個々のデータを記憶する各記憶エレメント２０〜２Ｎ−１を接続する構造である。ある場所（ここでは、データ２の場所）にデータ１．５を挿入したい場合には、図３に示すように、データ１．５の挿入箇所（データ２を記憶する記憶エレメント２１）より後ろのデータ全てについて、一段後ろの記憶エレメントへデータを移動し、空いた記憶エレメントに新たな要素であるデータ１．５を書き込めばよい。
【００２０】
ソフトウェア処理においては、データを挿入するための空き場所を作るための移動処理を１要素ずつ逐次処理する必要があるため、挿入処理には要素数に比例した処理時間が必要となる。ソフトウェア処理でリスト構造を用いるのは、この移動処理の処理コスト（時間）を避けるためであるが、ハードウェアにおいては、移動処理が全要素について同時に行う事ができるため、この処理時間が問題とはならない。
【００２１】
要素削除は、図４に示すように、図３と同様に各要素に対する移動処理が並列に実施できる。例えば、データ２を削除する場合には、削除箇所つまりデータ２より後ろのデータ全てについて、一段前の記憶エレメントへデータを移動する。又、記憶素子ネットワーク２がＬＲＵ（Least Recently Used）回路を構成する場合には、図５に示すように、使用したデータ２を記憶素子ネットワーク２の最後の位置に移動し、使用したデータ２の位置より後ろのデータ全てについて、一段前の記憶エレメントへデータを移動する。
【００２２】
このように、ハードウェアにおけるリスト構造は、配列構造を用いて実装すれば良い事になる。これは配列のメリットも同時に使える事を意味し、順列中のＮ番目の要素についても、先頭要素から順に辿ることなく参照可能である。
【００２３】
このハードウェア構造において、例えば、データ４に対してデータ３の値を移動するのは、データ２の位置に要素を挿入する場合、データ３の位置に要素を挿入する場合、あるいはデータ４の位置に要素を挿入する場合など、いくつかの条件を想定することができる。即ち、記憶素子ネットワーク２を構成する要素数が増えると、条件もまた要素数の増加に比例して増える事になる。ハードウェアにとって条件の増加はすなわち論理段数の増加であり、1サイクルの処理に必要となる時間が増加する、つまり動作周波数が低下する事を意味する。
【００２４】
このデータの挿入や削除に伴うデータの移動を制御する回路遅延は、記憶素子ネットワーク２の要素数に比例して大きくなる。この回路遅延を小さくし、回路規模を必要最小限に抑えるため、更新制御回路３は、リスト構造の更新制御を加算器あるいは減算器をベースとした制御で実現する。これにより、大規模なリスト構造を高速かつ省コストに実装するが可能となる。
【００２５】
更新制御回路３には、例えば、ＣＳＡ（Carry Save Adder or Carry Select Adder）を用いることが好ましい。ＣＳＡは、大規模な加減算に対しても、回路を最適化することで高速に処理が可能な回路を生成可能である。図６は、加減算の桁数と回路の遅延の関係図である。データのエントリ数は、加減算の桁数に対応し、エントリが増加した場合においても論理の複雑さは変わる事がない。図６は、論理合成により生成される回路の遅延を示している。エントリ数の増加とともに遅延は飽和に近づく。このため、データのエントリ数が増加しても、回路遅延を最小限に抑えることが可能となる。
【００２６】
（記憶素子ネットワーク）
次に、記憶素子ネットワーク２を、説明する。図７は、図１の記憶素子ネットワーク及び選択回路の回路図、図８は、図７の記憶エレメントの第１の実施の形態の回路図、図９は、図１の記憶エレメントの第２の実施の形態の回路図である。
【００２７】
図７に示すように、記憶素子ネットワーク２は、Ｎ個の記憶エレメント２０〜２Ｎ−１を直列接続して構成された順序回路である。記憶エレメント２０が、記憶素子ネットワーク２の先頭段であり、記憶エレメント２Ｎ−１が、記憶素子ネットワーク２の最終段であり、その間の記憶エレメント２１〜２Ｎ−２が、記憶素子ネットワーク２の中間段である。
【００２８】
図７は、記憶素子ネットワーク２のエントリ数が、Ｎの場合の例を示した。又、図７では、データの挿入か削除かの選択を指定する信号としてinsert/removeを、データの挿入・削除の位置を指定する信号として選択信号ＳＥＬ［Ｎ−１：０］を定義している。但し、先頭段の選択信号ＳＥＬ［０］の指定は，回路制御に不要であり、図７には表れていない。更に、イネーブル信号ＥＮ［Ｎ−１：０］は、更新制御回路３によって制御される信号であり、個々の記憶エレメントに対応するイネーブル信号ＥＮがアサートされたタイミングのみ、その記憶エレメントのデータが更新される。
【００２９】
先頭段の記憶エレメント２０は、第１のマルチプレクサ５０−０と、第１のマルチプレクサ５０−０の出力を受ける第１の記憶素子５２−０とを有する。第１のマルチプレクサ５０−０は、入力する挿入／削除信号insert/removeの値により、挿入エントリ（データ）と次段の記憶素子５２−１の出力とのいずれかを選択して出力する。挿入／削除信号は、「１」のときに挿入（insert）指示を、「０」の場合に削除（remove）指示を示す。第１のマルチプレクサ５０−０は、挿入指示では挿入エントリを選択して第１の記憶素子５２−０に出力する一方、削除指示では、次段の記憶素子５２−１の出力を選択し、第１の記憶素子５２−０に出力する。
【００３０】
２段目の記憶エレメント２１は、第２のマルチプレクサ５４−１と、第３のマルチプレクサ５６−１と、第３のマルチプレクサ５６−１の出力を受ける第２の記憶素子５２−１とを有する。
【００３１】
第２のマルチプレクサ５４−１は、１段目選択信号ＳＥＬ［１］により、記憶素子５２−０の出力と挿入エントリとのいずれかを選択する。第２のマルチプレクサ５４−１は、１段目選択信号ＳＥＬ［１］が「１」（選択）の場合、挿入エントリを選択して第３のマルチプレクサ５６−１に出力する。一方、第２のマルチプレクサ５４−１は、１段目選択信号ＳＥＬ［１］が「０」（非選択）の場合、第１の記憶素子５２−０の出力を選択し、第３のマルチプレクサ５６−１に出力する。
【００３２】
第３のマルチプレクサ５６−１は、挿入／削除信号insert/removeの値により、第２のマルチプレクサ５４−１の出力と次段の記憶素子５２−２の出力とのいずれかを選択する。
【００３３】
第３のマルチプレクサ５６−１は、挿入指示で、第２のマルチプレクサ５４−１の出力を選択して第２の記憶素子５２−１に出力する。一方、第３のマルチプレクサ５６−１は、削除指示で、次段の記憶素子５２−２の出力を選択し、第２の記憶素子５２−１に出力する。
【００３４】
３段目の記憶エレメント２２は、第２のマルチプレクサ５４−２と、第３のマルチプレクサ５６−２と、第３のマルチプレクサ５６−２の出力を受ける第３の記憶素子５２−２とを有する。以下、４段目〜Ｎ−１段目の記憶エレメント２３〜２Ｎ−２も同様の構成である。又、３段目〜Ｎ−１段目の記憶エレメント２３〜２Ｎ−２も、２段目の記憶エレメント２１と同一の動作を行う。
【００３５】
最終Ｎ段目の記憶エレメント２Ｎ−１は、第３のマルチプレクサ５６−Ｎ−１と、第３のマルチプレクサ５６−Ｎ−１の出力を受ける第Ｎ−１の記憶素子５２−Ｎ−１とを有する。第３のマルチプレクサ５６−Ｎ−１は、Ｎ段目選択信号ＳＥＬ［Ｎ］の値により、第Ｎ−１段目の記憶素子５２−Ｎ−２の出力と挿入エントリとのいずれかを選択する。第３のマルチプレクサ５６−Ｎ−１は、Ｎ段目選択信号ＳＥＬ［Ｎ］が「１」（選択）の場合、挿入エントリを選択して第Ｎ−１の記憶素子５２−Ｎ−１に出力する一方、Ｎ段目選択信号ＳＥＬ［Ｎ］が「０」（非選択）の場合、前段の記憶素子５２−Ｎ−２の出力を選択し、第Ｎ−１の記憶素子５２−Ｎ−１に出力する。
【００３６】
各記憶素子５２−０〜５２−Ｎ−１は、それぞれデータ入力端子とイネーブル制御信号の入力端子を持ち、対応するイネーブル信号ＥＮがアサートされたサイクルのみ、入力データで更新される。それ以外の場合には、記憶素子５２−０〜５２−Ｎ−１は、現状値を保持する。また、各記憶素子の出力は、マルチプレクサ４０に供給される。
【００３７】
図８は、記憶素子５２−０〜５２−Ｎ−１の第１の実施の形態の回路図であり、クロック・ゲーティングを用いた回路を示す。図８において、記憶素子５２−０〜５２−Ｎ−１は、クロック入力で、更新データを格納するメモリ６０と、イネーブル信号ＥＮとクロックの論理積を演算するアンド回路６２とを有する。メモリ６０は、例えば、フリップフロップ（ＦＦ：Flip Flop）回路からなる。メモリ６０は、イネーブル信号ＥＮがアサートされているタイミングのみクロックが入力し、クロック入力によって更新データで保持する値が更新される。
【００３８】
図９は、記憶素子５２−０〜５２−Ｎ−１の第２の実施の形態の回路図であり、マルチプレクサを用いた回路を示す。図９において、記憶素子５２−０〜５２−Ｎ−１は、クロック入力でデータを更新するメモリ６０と、イネーブル信号ＥＮを選択信号とし、入力する更新データとメモリ６０のデータとのいずれかを選択するマルチプレクサ６４とを有する。メモリ６０は、例えば、フリップフロップ（ＦＦ：Flip Flop）回路からなる。
【００３９】
メモリ６０は、自分の出力する値をマルチプレクサ６４に帰還入力し、自身の出力する値で更新するか、入力された更新データで値を更新するかを、マルチプレクサ６４の選択信号ＥＮにより制御する。図９では、イネーブル信号ＥＮがアサートされた時に、更新データが選択され、それ以外の場合は、帰還された自身の値により、メモリ６０のデータが更新（保持）される。
【００４０】
図７に戻り、選択回路４は、各記憶エレメント５２−０〜５２−Ｎ−１の出力が入力するマルチプレクサ４０と、セレクタ４２とを有する。マルチプレクサ４０は、位置選択信号ＳＥＬ［Ｎ−１：０］で指定された記憶エレメントの出力を選択する。セレクタ４２は、マルチプレクサ４０の出力と最終段の記憶エレメント５２−Ｎ−１の出力を受け、削除（Remove）が指示されると、マルチプレクサ４０の出力を、挿入（insert）が指示されると、最終段の記憶エレメント５２−Ｎ−１の出力を選択し、出力する。
【００４１】
（更新制御回路）
次に、更新制御回路を説明する。図１０は、図１の更新制御回路の第１の実施の形態の構成図、図１１は、図１０の更新制御回路の回路図、図１２は、図１１のハーフアダー（Half Adder）の回路図、図１３は、図１１のフルアダー（Full Adder）の回路図、図１４は、図１１のＣＳＡ回路を最適化した例の回路図である。
【００４２】
図１０に示すように、更新制御回路３は、Ｎビットの位置選択信号ＳＥＬ［Ｎ−１：０］とＮビットの「１」（“１１１、・・、１１１”）を加算するＮビットの加算器（Adder）３０と、Ｎビットの加算器３０からの加算結果を反転し、Ｎビットのイネーブル信号ＥＮ［Ｎ−１：０］を出力する反転回路３２とを有する。
【００４３】
この更新制御回路３は、以下の生成ルールで、イネーブル信号ＥＮを生成する。先ず、位置選択信号ＳＥＬは、位置ｋを示す位置選択信号ＳＥＬ［ｋ］＝１の場合には、他の位置を示す位置選択信号ＳＥＬ［ｌ］＝０（但し、ｌ！＝ｋ）である。この位置選択信号から生成されるイネーブル信号は、ｍ番目の記憶エレメント２ｍのイネーブル信号ＥＮ［ｍ］＝０（但し、ｍ＜ｋ）、その他の記憶エレメントのイネーブル信号ＥＮ［ｎ］＝１（但し、ｎ≧ｋ）である。
【００４４】
更新制御回路３は、この条件を満たすイネーブル信号ＥＮを生成するために、加算を含めた以下の式の計算を行う。
【００４５】
【数１】
0005445147.tif 000002
【００４６】
即ち、Ｎ個のエントリに対して、Ｎビットで全てのビットが「１」である固定値（２Ｎ−１）に対し、位置選択信号ＳＥＬ［Ｎ−１：０］を加算し、最上位桁の繰り上がり（Carry）を無視して、論理反転する。例えば、４ビット（bit）の例では、以下の加算結果を得る。
【００４７】
【数２】
0005445147.tif 000003
【００４８】
このように、4’b1111 + SEL[3:0]（4’b0010）の加算結果として5’b10001を得る。最上位の桁上がりbitを無視して、加算結果の論理値を反転すればEN[3:0]=4’b1110を得る。
【００４９】
図１１〜図１３により、ＣＳＡ回路を例に、具体的に説明する。図１１に示すように、更新制御回路３は、位置選択信号ＳＥＬ［０］が入力されるハーフアダー３０−０と、各々前段のアダーのキャリー出力ＣＯ［０］〜ＣＯ［Ｎ−１］と位置選択信号ＳＥＬ［１］〜［Ｎ−１］とが入力されるフルアダー３０−１〜３０−Ｎ−１とを有する。ハーフアダー３０−０、フルアダー３０−１〜３０−Ｎ−１の各々には、値「１」が入力される。なお、図１１の回路構成は、リップル・キャリー・アダー（Ripple Carry Adder）と呼ばれる回路構成である。
【００５０】
図１２に示すように、ハーフアダー３０−０は、入力Ａ，Ｂ（図１１では、Ａ＝「１」とＳＥＬ［０］の一方、Ｂ＝「１」とＳＥＬ［０］の他方）の論理積を計算し、キャリー（図１１では、Ｃ
ＡＲＲＹ＝ＣＯ［０］）を出力するアンド回路（ＡＮＤ）３０Ａと、入力Ａ，ＢのＥＯＲ（Exclusive OR）を計算し、サム（ＳＵＭ、図１１では、Ｓ［０］）を出力するＥＯＲ回路（ＡＮＤ）３０Ｂとを有する。
【００５１】
又、図１３に示すように、フルアダー３０−１〜３０−Ｎ−１は、入力Ａ，Ｂの論理積を計算するアンド回路３０Ｅと、入力Ａ，Ｂの論理和を計算するオア回路３０Ｃと、オア回路３０Ｃの出力と入力Ｃとの論理積を計算するアンド回路（ＡＮＤ）３０Ｄと、アンド回路３０Ｅと３０Ｄの出力の論理積を計算し、キャリーを出力するアンド回路（ＡＮＤ）３０Ｆとを有する。
【００５２】
更に、フルアダー３０−１〜３０−Ｎ−１は、入力Ａ，ＢのＥＯＲ（Exclusive OR）を計算するＥＯＲ回路（ＡＮＤ）３０Ｇと、ＥＯＲ回路３０Ｇの出力と入力ＣとのＥＯＲ（Exclusive OR）を計算し、サム（ＳＵＭ）を出力するＥＯＲ回路（ＡＮＤ）３０Ｈとを有する。
【００５３】
図１２、図１３において、入力Ａ，Ｂが、図１１の位置選択信号ＳＥＬ、値「１」であり、図１３において、入力Ｃが、図１１のキャリーに対応する。このようなＣＳＡ構成により、回路遅延を最小限とし、多数のエントリのイネーブル信号を生成できる。
【００５４】
図１４は、図１１のＣＳＡ回路を、遅延時間を考慮した変形例を示す。図１４において、図１１と同一のものは、同一の記号で示してある。図１４では、ＣＳＡ回路を、位置選択信号ＳＥＬ［０］〜［ｋ−１］のグループＡと、位置選択信号［ｋ］〜［Ｎ−１］のグループＢ，Ｃに分けている。グループＢは、キャリーが「０」の場合に、グループＣは、キャリーが「１」の場合に対応する。
【００５５】
即ち、グループＡは、位置選択信号ＳＥＬ［０］が入力されるハーフアダー３０−０と、各々前段のアダーのキャリー出力ＣＯ［０］〜ＣＯ［Ｋ−２］と位置選択信号ＳＥＬ［１］〜［Ｋ−１］が入力されるフルアダー３０−１〜３０−Ｋ−１とを有する。ハーフアダー３０−０、フルアダー３０−１〜３０−Ｋ−１の各々には、値「１」が入力される。
【００５６】
グループＢ、Ｃは、各々前段のアダーのキャリー出力と位置選択信号ＳＥＬ［Ｋ］〜［Ｎ−１］が入力されるフルアダー３０−Ｋ〜３０−Ｎ−１とを有する。但し、グループＢの先頭のフルアダー３０−Ｋには、キャリー入力として「０」を、グループＣの先頭のフルアダー３０−Ｋには、キャリー入力として「１」を入力する。
【００５７】
そして、グループＢ、Ｃの出力を、グループＡの最終段のフルアダー３０−Ｋ−１のキャリーＣＯ［Ｋ−１］で選択するマルチプレクサ３４を設ける。このように構成すると、グループＢ，Ｃで、グループＡの最終段のフルアダー３０−Ｋ−１のキャリーＣＯ［Ｋ−１］が、各々「０」、「１」の場合の加算を並行して行うため、キャリー出力がフルアダー３０−Ｎ−１まで伝播するのを待たず、イネーブル信号ＥＮを生成できる。このため、キャリー伝搬距離を半分に抑えて、回路遅延時間を小さくできる。このＣＳＡ回路は、Carry Select Adderと呼ばれている。
【００５８】
図１５は、図１の更新制御回路の第２の実施の形態の構成図、図１６は、図１５の更新制御回路の回路図である。図１５は、ＣＳＡを、減算器で構成した例である。図１５に示すように、更新制御回路３は、Ｎビットの位置選択信号［Ｎ−１：０］と、Ｎビットの「０」（“０００、・・、０００”）を加算するＮビットの減算器（Subtractor）３８を有する。
【００５９】
この更新制御回路３は、以下の生成ルールで、イネーブル信号ＥＮを生成する。図１１と同様に、位置選択信号ＳＥＬは、位置ｋを示す位置選択信号ＳＥＬ［ｋ］＝１の場合には、他の位置を示す位置選択信号ＳＥＬ［ｌ］＝０（但し、ｌ！＝ｋ）である。この位置選択信号から生成されるイネーブル信号は、ｍ番目の記憶エレメント２ｍのイネーブル信号ＥＮ［ｍ］＝０（但し、ｍ＜ｋ）、その他の記憶エレメントのイネーブル信号ＥＮ［ｎ］＝１（但し、ｎ≧ｋ）である。
【００６０】
更新制御回路３は、減算により、この条件を満たすイネーブル信号ＥＮを生成するために、減算を含めた以下の式の計算を行う。
【００６１】
【数３】
0005445147.tif 000004
【００６２】
即ち、Ｎ個のエントリに対して、Ｎビットで全てのビットが「０」である固定値（２Ｎ）に対し、位置選択信号ＳＥＬを加算し、最上位桁の繰り上がり（Carry）を無視する。例えば、４ビット（bit）の例では、以下の減算結果を得る。
【００６３】
【数４】
0005445147.tif 000005
【００６４】
図１６により、ＣＳＡ回路を例に、具体的に説明する。更新制御回路３は、位置選択信号ＳＥＬ［０］が入力されるハーフ減算器（ハーフサブトラクタ：Half Subtractor）３８−０と、各々前段の減算器のキャリー出力ＣＯ［０］〜ＣＯ［Ｎ−１］と位置選択信号ＳＥＬ［１］〜［Ｎ−１］とが入力されるフル減算器（フルサブトラクタ：Full Subtractor）３８−１〜３８−Ｎ−１とを有する。ハーフ減算器３８−０、フル減算器３８−１〜３８−Ｎ−１の各々には、値「０」が入力される。
【００６５】
図１６の減算器の構成では、図１１の反転回路を削減できるため、回路規模を小さくでき、且つ動作周波数を向上できる。
【００６６】
（リスト構造制御回路の動作）
次に、リスト構造制御回路の動作を説明する。図１７は、図１乃至図１６のリスト構造制御回路の挿入動作の説明図、図１８は、図１乃至図１６のリスト構造制御回路の削除動作の説明図である。図１７では、図７の構成において、挿入動作に関連する部分のみを示し、図１８では、図７の構成において、削除動作に関連する部分のみを示す。又、説明の簡略化のため、図１７及び図１８では、Ｎ＝４である４段の記憶エレメントの構成で説明する。
【００６７】
図７において、insert/remove信号が「０」（remove）であるか「１」(insert)であるかの違いにより、それぞれ、図１７または図１８の回路構成がアクティブとなる。この例では、insert/remove信号が「１」の時に図１７の回路の要素が、「０」の時に図１８の回路の要素が有効になるとする。
【００６８】
入力するinsert/remove信号が「１」の時には、図７に示したように、マルチプレクサ５０−０，５６−１，５６−２・・・は、挿入エントリ（データ）を選択する。このため、図１７に示すように、記憶エレメント５２−０〜５２−３は、それぞれマルチプレクサ５４−１，５４−２，５４−３を介して、順番に接続されることになる。
【００６９】
つまり、図１７は、データ挿入時に動作する記憶素子ネットワークの要素を抜き出して示した図面であるが、データ挿入時には、次段の記憶エレメントが保持するデータは記憶エレメントへの入力対象としては選択されない。従って、図７に示したマルチプレクサ５０−０は、データ挿入が必要となる場合に挿入エントリを選択する動作のみを実行することになり、マルチプレクサ５６−１，５６−２・・・は前段の記憶エレメントから出力されるデータのみを選択動作を実行することになる。つまりデータ挿入時には、マルチプレクサ５０−０、５６−１，５６−２・・・は実質的にデータを選択していないと見なすことができる。従って、図１７に示した回路構成には、マルチプレクサ５０−０，５６−１，５６−２・・・に相当する要素は示されていない。
【００７０】
記憶エレメント５２−１〜５２−３の入力側に設けられたマルチプレクサ５４−１，５４−２，５４−３は、位置選択信号ＳＥＬで選ばれた場合には、図示右側から入力する挿入エントリの値を、選ばれなかった場合には、図示左側から入力する前段の記憶エレメントのデータを出力する。
【００７１】
例えば、０番目の記憶エレメント５２−０にデータを挿入する場合には、更新制御回路３は、位置選択信号ＳＥＬ［３：０］＝ 4’b0001と、イネーブル信号ＥＮ［３：０］＝4’b1111を生成し、位置選択信号ＳＥＬ［１］＝０，ＳＥＬ［２］＝ＳＥＬ［３］＝０、イネーブル信号ＥＮ［０］＝ＥＮ［１］＝ＥＮ［２］＝ＥＮ［３］＝１を出力する。
【００７２】
その結果、記憶エレメント５２−０は挿入エントリで更新され、他の記憶エレメント５２−１〜５２−３はそれぞれ、前段の記憶エレメント５２−０〜５２−２の値でデータが更新される。即ち、データの先頭に、新たにデータが挿入された形となる。末尾のデータは押し出される形でエントリから削除される。この際のデータは、制御インタフェースの出力として定義される削除したデータとして出力しても良い。
【００７３】
同様にして、１番目の記憶エレメント５２−１にデータを挿入する場合には、更新制御回路３は、位置選択信号ＳＥＬ［３：０］＝4’b0010と、イネーブル信号ＥＮ［３：０］＝4’b1110を生成し、位置選択信号ＳＥＬ［１］＝１，ＳＥＬ［２］＝ＳＥＬ［３］＝０、イネーブル信号ＥＮ［０］＝０、イネーブル信号ＥＮ［１］＝ＥＮ［２］＝ＥＮ［３］＝１を出力する。
【００７４】
その結果、記憶エレメント５２−０は更新されず、現状の値を維持する。一方、記憶エレメント５２−１は挿入エントリで更新され、他の記憶エレメント５２−２〜５２−３は、前段の記憶エレメント５２−１〜５２−２の値でデータが更新される。
【００７５】
このように、更新制御回路３は、位置選択信号ＳＥＬで指定されたビット位置と、それより下位のビット位置の信号を「１」とした信号をイネーブル信号ＥＮとして生成する。
【００７６】
同様にして、insert/remove信号が「０」の時には、図７に示したように、マルチプレクサ５０−０，５６−１，５６−２・・・は、挿入エントリ（データ）を選択せず、次段の記憶エレメントの出力を選択する。このため、図１８に示すように、記憶エレメント５２−０〜５２−３は、位置選択信号ＳＥＬで、指定されたマルチプレクサ５６−１，５６−２，５６−３で、マルチプレクサ５０−０，５４−１，５４−２からの前段の記憶エレメントの出力を選択する各記憶エレメント５２−０〜５２−Ｎ−１は、イネーブル信号ＥＮで指示された場合に、対応するマルチプレクサ５６−１〜５６−Ｎ−１から出力されたデータを格納する。
【００７７】
なお、データ削除時には、マルチプレクサ５０−０，５４−１〜５４−Ｎ−１は挿入データを選択されない。つまり、各マルチプレクサ５０−０、５４−１，５４−２〜５４−Ｎ−１に入力する位置選択信号ＳＥＬは、図７の例では全て０となる。言い換えると、データ削除時には位置選択信号ＳＥＬは固定値であるのと同等となり、マルチプレクサ５０−０，５４−１〜５４−Ｎ−１は実質的に動作しないと見なすことができる。そのため、図１８に示した回路構成には、マルチプレクサ５０−０，５４−１，５４−２〜５４−Ｎ−１に相当する要素は示されていない。
【００７８】
例えば、図１８に示した回路で、記憶エレメント５２−１のデータを削除する場合には、更新制御回路３は、イネーブル信号ＥＮ［３：０］＝4’b1110を生成し、イネーブル信号ＥＮ［０］＝０、イネーブル信号ＥＮ［１］＝ＥＮ［２］＝ＥＮ［３］＝１を出力する。
【００７９】
その結果、記憶エレメント５２−０は、更新されず、現状の値を維持する。記憶エレメント５２−２、５２−３は、それぞれ対応する前段の記憶エレメント５２−１，５２−２に対して、保持しているデータを出力する。記憶エレメント５２−１〜５２−２は、後段の記憶エレメント５２−２〜５２−３から出力されたデータの値で更新される。即ち、図４で示した削除動作を実行する。この場合、最終段の記憶エレメント５２−３は空きとなるが、制御インタフェースで定義した挿入するデータを同時に追記する事にしても良い。あるいはエントリの個数をカウントし、現在の個数内のエントリのみ有効とするような動的にエントリ数が増減するような回路を構成する事もできる。
【００８０】
又、他の記憶エレメントからデータを削除する場合も同様に処理すればよい。
【００８１】
（リスト構造制御回路を使用したＬＲＵ）
図１９は、図１乃至図１８で説明したリスト構造制御回路を用いたＬＲＵ回路の一実施の形態のブロック図、図２０は、図１９の位置選択回路のブロック図、図２１は、比較例としての優先度表を用いたＬＲＵの説明図、図２２は、優先度表を用いたＬＲＵと、リストを用いる本実施の形態とのハードウェア実装コストの比較を示す説明図である。
【００８２】
図１９において、ＬＲＵ回路７は、図１乃至図１８で説明したリスト構造制御回路１と、位置選択回路６とを有する。ＬＲＵは、Least Recently Usedの略であり、もっとも遠い過去に使われたエントリを選び出すための回路である。この回路の実装にはリスト構造が適しており、図５で説明したように、利用されたエントリをリストから抜き出して、リストの末尾に追加する事で、リストの先頭は、もっとも遠い過去に使われたエントリとなる。
【００８３】
図１９において、図１乃至図１８で説明したものと同一のものは、同一の記号で示してある。図１９において、リスト構造制御回路１の構成及び動作は、図１乃至図１８で説明したものと同一である。但し、図５で説明したように、リスト構造制御回路１は、削除操作及び削除されたエントリの挿入操作を行う。又、ＬＲＵにより管理する情報はエントリ番号で管理し、このエントリ番号が、記憶素子ネットワーク２に記憶されるデータである。
【００８４】
例えば、記憶素子ネットワーク２に１６エントリがある場合には、“4’b000”〜“4’b1111”の４ビット値がエントリ番号のデータとして表される。記憶素子ネットワーク２には、適当なエントリ番号の初期値として、“4’b0000”〜“4’b1111”を順番に格納しておく。この初期値は、本質的な影響を持たない。重複のない一意の並びであれば良い。
【００８５】
ＬＲＵはアクセスした順にエントリを並べる事で実現されるため、アクセスの度に、アクセスしたエントリを最新エントリとして更新する。ここでのアクセスとは具体的な操作をさす言葉ではなく、ＬＲＵを何に対して用いるかにより、このアクセスという言葉の意味する動作は異なる。
【００８６】
例えば、エントリ“4’b0010”を最新エントリとしてＬＲＵを再構成する場合、位置選択回路６は、更新制御回路３に、“4’b0010”のエントリが格納されている記憶素子ネットワーク２上の位置及び当該エントリの削除を指示する。前述の削除動作により、選択したエントリが削除され、削除データとしてエントリ番号が選択回路４から出力される。このエントリ番号を、入力データとして更新制御回路３に帰還する。これにより、前述のリスト構造制御回路１の説明で説明したように、エントリの末尾に削除したデータを記憶素子ネットワーク２に追記するようにリスト構造制御回路１が動作する。
【００８７】
このような動作を実行するため、図１９の例では、指定したエントリを削除し、リストの末尾へ移動するという操作が実現できる。よって、このリストは最終アクセスが最も古いエントリを先頭として、古い順にエントリが並んだリスト構造となり得る。最も古いエントリはリストの先頭の値を参照すれば良く、最新のエントリを得るためにはリストの末尾の値を参照すれば良い。
【００８８】
図２０により、位置選択回路６を説明する。位置選択回路６は、記憶素子ネットワーク２の全ての記憶エレメントに保持されたデータ（ＬＩＳＴ［０］〜ＬＩＳＴ［３］）を参照し、更新したいエントリ番号（ＥＮＴＲＹ  ＩＤ）と記憶エレメントに保持されたデータとの比較、一致検出を行う比較回路６０−１〜６０−４を有する。比較回路６０−１〜６０−４でエントリ番号が一致したエントリ位置が、削除対象のエントリ（図１８の最新とするエントリ位置）となり、対応する比較回路から位置選択信号（ＳＥＬ［ｎ］）が出力される。
【００８９】
この比較回路６０−１〜６０−３は、リスト構造制御回路１の内部に設けても良く、その場合には、インタフェースとしてエントリ位置指定ではなく、エントリ値指定となる。
【００９０】
一方、ＬＲＵの方式として、優先度表による制御がある。図２１は、優先度表によるＬＲＵの説明図である。図２１に示すように、優先度表は、例えば、４つの対象エントリＡ，Ｂ，Ｃ，Ｄに対し、優先度を示すマトリック表を使用する。図２１では、マトリックス表の「＞」または「＜」で示すように、エントリＡが、エントリＢ，Ｃ，Ｄより優先度が高く、エントリＢは、エントリＣより優先度が高く、エントリＤより優先度が低い。又、エントリＣは、エントリＤより優先度が低い。
【００９１】
優先度表を実装する場合、エントリ数の二乗に比例するハードウェアコストが必要となるため、多くのエントリを持つＬＲＵの実装は困難とされてきた。そのため、擬似ＬＲＵといった、ハードウェアコストは小さいが、正確にはＬＲＵとなっていないような回路を近似的に用いる工夫が必要である。
【００９２】
優先度表を用いる場合には、ｎ個のエントリに対して、ｎ（ｎ−１）／２ビットの優先度情報が必要である。図２１のように、優先度表は、縦軸と横軸をそれぞれ不等号の左辺と右辺として考え、それぞれの組み合わせの優先度をマトリクス上の不等号で示している。マトリクスの対角は自分対自分なので考えなくてもよく、この表は転置しても変わらない（対角線上で対象である）。
【００９３】
このため、優先度表に必要となるビットサイズは、以下の式で表される。
【００９４】
【数５】
0005445147.tif 000006
【００９５】
不等号の「＜」「＞」はそれぞれ任意に「０」又は「１」の２値として実装する。
【００９６】
図２２は、ＬＲＵの実装方式について、優先度表を用いた方式（Matrix）と、本実施の形態のリストを用いる方式（List）とのそれぞれのハードウェア実装数（回路規模＝コスト）を示す。図２２に示すように、優先度表を用いた方式では、回路規模はエントリサイズの二乗に比例する。一方、本実施の形態のリスト方式では、ｎｌｏｇ２ｎの回路規模で実装する事が可能である。又、エントリ数が二桁を超えた場合に、本実施の形態のリスト方式が、優先度表を用いた方式よりも小規模のハードウェアで実装可能である事がわかる。
【００９７】
（リスト構造制御回路を使用した調停回路）
図２３は、図１９乃至図２０のＬＲＵ回路を用いた調停回路の一実施の形態のブロック図である。図２３中、図１乃至図２０で説明したものと同一のものは、同一の記号で示してある。リスト構造制御回路１、ＬＲＵ回路７は、図１乃至図２０で説明した構成及び動作と同一の動作を行うが、ＬＲＵの要素としては、要求元の管理番号を用いる。
【００９８】
調停回路８は、複数の要求を受け、ＬＲＵ回路７を参照して、要求の調停を行う。調停回路８は、要求を受けた場合に、ＬＲＵ回路７の記憶ネットワーク２の各記憶エレメントの管理番号を参照し、最も古いエントリから順番に高い優先度を与えて要求の調停を行う。そして、調停回路８は、調停により許可を発行した際、許可を発行した要求元の管理番号を用いて、ＬＲＵ回路７を更新する。更新動作は、前述のＬＲＵ回路７の例と同一である。
【００９９】
このように、ＬＲＵを用いた調停回路についても、調停に参加する要求元の数が多い場合にでも、ハードウェアに実装が可能である。
【０１００】
（リスト構造制御回路を使用したキャッシュリプレース回路）
図２４は、図１９乃至図２０のＬＲＵ回路を用いたキャッシュリプレース回路の一実施の形態のブロック図である。図２４中、図１乃至図２０で説明したものと同一のものは、同一の記号で示してある。リスト構造制御回路１、ＬＲＵ回路７は、図１乃至図２０で説明した構成及び動作と同一の動作を行う。
【０１０１】
キャッシュメモリのヒット、ミスヒットを判定するキャッシュコントローラには、キャッシュメモリのリプレースを行うキャッシュエントリ制御回路９が設けられる。この実施の形態では、キャッシュリプレースに図１９乃至図２０のＬＲＵ回路７を用いる。
【０１０２】
キャッシュエントリ制御回路９は、キャッシュがヒットした際には、該当エントリ番号をＬＲＵ回路７に贈り、ＬＲＵ回路７により更新する。キャッシュエントリ制御回路９は、キャッシュミスヒットした際には、ＬＲＵ回路７の最も古いエントリ番号をリプレース対象として、選択する。
【０１０３】
キャッシュリプレース回路において、ＬＲＵ回路は性能が良いが、大規模なＬＲＵが実装困難である。疑似的なＬＲＵ回路では、正確なＬＲＵの動作をしない代わりに、高速あるいは小規模の回路で実現できるような工夫が必要である。このため、本実施の形態のＬＲＵ回路７と比べると、キャッシュリプレースの性能の低下は避けられない。本実施の形態では、大規模なエントリ数に対しても、正確なＬＲＵを提供できる。
【０１０４】
（他の実施の形態）
前述の実施の形態では、記憶ネットワーク２を、図７の回路構成で説明したが、他のネットワーク構成を適用できる。又、マルチプレクサによる接続回路を例に説明したが、他の回路を用いて、接続回路を構成しても良い。更に、更新制御回路３も、他の形態の加算器、減算器の構成を適用できる。
【０１０５】
以上、本発明を実施の形態により説明したが、本発明の趣旨の範囲内において、本発明は、種々の変形が可能であり、本発明の範囲からこれらを排除するものではない。
【０１０６】
（付記１）
各々データを保持する複数の記憶素子と、前記複数の記憶素子のそれぞれに対応して設けられ、前記複数の記憶素子を直列に接続して前記データに順序関係を持たせる複数の選択回路と、データの挿入又は削除の位置を指定する位置選択信号と固定値との加算及び減算の一方の演算を行い、前記演算結果によるイネーブル信号を生成し、前記イネーブル信号で、前記記憶素子へのデータの保持又は前段の前記記憶素子のデータでの更新を制御する更新制御回路とを有し、前記データの挿入時、前記位置選択信号により前記複数の選択回路を制御し、挿入するデータで、前記位置指定信号が指定する位置の記憶素子を更新することを特徴とするリスト構造制御回路。
【０１０７】
（付記２）
前記選択回路は、前記挿入の指示に応じて、対応する記憶素子の前段の記憶素子のデータ又は対応する記憶素子の後段の記憶素子のデータのいずれかを選択する第１の選択回路と、前記位置選択信号により、前記第１の選択回路の出力と前記挿入するデータのいずれかを選択する第２の選択回路とを有することを特徴とする付記１のリスト構造制御回路。
【０１０８】
（付記３）
前記更新制御回路は、前記位置選択信号と前記固定値との加算又は減算を行うキャリーセレクトアダー回路を有することを特徴とする付記１のリスト構造制御回路。
【０１０９】
（付記４）
前記更新制御回路は、前記キャリーセレクトアダー回路の出力を反転し、前記複数の記憶素子の制御信号を出力する反転回路を更に有することを特徴とする付記３のリスト構造制御回路。
【０１１０】
（付記５）
前記更新制御回路において、前記キャリーセレクトアダー回路は、前記位置選択信号の各ビットの値に、値「１」を加算し、前記更新制御回路はさらに、前記キャリーセレクトアダー回路の出力を反転し、前記複数の記憶素子の制御信号を出力する反転回路とを有することを特徴とする付記３のリスト構造制御回路。
【０１１１】
（付記６）
前記更新制御回路において、前記キャリーセレクトアダー回路は、前記位置選択信号の各ビットの値に、値「０」を減算することを特徴とする付記３のリスト構造制御回路。
【０１１２】
（付記７）
前記記憶素子は、メモリと、前記イネーブル信号により更新データで前記メモリを更新する更新回路とを有することを特徴とする付記１のリスト構造制御回路。
【０１１３】
（付記８）
前記更新回路は、前記イネーブル信号とクロックとの論理積を演算し、前記メモリのクロックを前記記憶素子に入力するアンド回路を有することを特徴とする付記７のリスト構造制御回路。
【０１１４】
（付記９）
前記更新回路は、前記イネーブル信号に応じて、前記メモリの出力と更新データとのいずれかを選択し、前記メモリに出力するマルチプレクサを有することを特徴とする付記７のリスト構造制御回路。
【０１１５】
（付記１０）
前記複数の記憶素子の各々のエントリ番号と使用したエントリ番号とを比較し、前記位置選択信号を前記更新制御回路に出力する位置選択回路を更に有し、前記更新制御回路は、削除指示に応じて、前記位置選択信号で指定された前記記憶素子のエントリ番号を削除し、且つ前記削除されたエントリ番号を前記複数の記憶素子の最終段の記憶素子に挿入して、ＬＲＵ動作を行うことを特徴とする付記１のリスト構造制御回路。
【産業上の利用可能性】
【０１１６】
複数の記憶素子を、選択回路を介し直列接続し、挿入又は削除の位置を指定する位置選択信号と固定値との加算及び減算の一方の演算結果で、記憶素子に、データの保持又は前段の前記記憶素子のデータでの更新を制御するため、順序関係をもった大規模なデータ構造に対して、データの挿入、削除の動作をハードウェアで実現でき、高速かつ省コストな回路を提供できる。又、大規模化に追随して、実装可能である。
【符号の説明】
【０１１７】
１  リスト構造制御回路
２  記憶素子ネットワーク
３  更新制御回路
４  選択回路
２０〜２Ｎ  記憶エレメント
３０  加算器
３２  反転回路
３８  減算器
５０−０、５４−１〜５４−２、５６−１〜５６−Ｎ−１  マルチプレクサ（接続回路）
５２−０〜５２−Ｎ−１  記憶素子
【図１】
0005445147.tif 000007
【図２】
0005445147.tif 000008
【図３】
0005445147.tif 000009
【図４】
0005445147.tif 000010
【図５】
0005445147.tif 000011
【図７】
0005445147.tif 000012
【図８】
0005445147.tif 000013
【図９】
0005445147.tif 000014
【図１０】
0005445147.tif 000015
【図１１】
0005445147.tif 000016
【図１２】
0005445147.tif 000017
【図１３】
0005445147.tif 000018
【図１４】
0005445147.tif 000019
【図１５】
0005445147.tif 000020
【図１６】
0005445147.tif 000021
【図１７】
0005445147.tif 000022
【図１８】
0005445147.tif 000023
【図１９】
0005445147.tif 000024
【図２０】
0005445147.tif 000025
【図２３】
0005445147.tif 000026
【図２４】
0005445147.tif 000027
【図２５】
0005445147.tif 000028
【図２６】
0005445147.tif 000029
【図２７】
0005445147.tif 000030
【図２８】
0005445147.tif 000031
【図６】
0005445147.tif 000032
【図２１】
0005445147.tif 000033
【図２２】
0005445147.tif 000034