(57)【要約】【課題】不要となったコマンドが格納されている領域をコンパクション或いはガーベージコレクションを用いずに解放できるようにする。【解決手段】実施形態によれば、コマンド管理装置のコマンドバッファは、ホストから受信されたコマンドの群を格納する。先入れ先出し手段は、これらのコマンドの群のそれぞれが格納されているコマンドバッファの領域のアドレスを格納するアドレス部を含むエントリの群を備える。先入れ先出し手段のエントリの群にそれぞれ含まれているアドレス部はリング状に接続されており、置換手段を含む。置換手段は、このアドレス部に格納されている第１のアドレスを、フリーアドレス設定手段に保持されている、不要となったコマンドが格納されているコマンドバッファの領域のアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する。【選択図】    図１
2012027718.tif 000002
【特許請求の範囲】
【請求項１】
ホストから受信されたコマンドの群を格納するコマンドバッファと、
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するアドレス部を含むエントリの群を備えた先入れ先出し手段と、
不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスをフリーアドレスとして保持するフリーアドレス設定手段とを具備し、
前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記アドレス部はリング状に接続されており、当該アドレス部は、当該アドレス部に格納されている第１のアドレスを、前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する置換手段を含む
コマンド管理装置。
【請求項２】
前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段のアドレス部のエントリアドレス「ｗｐ」を指し示すライトポインタを更に具備し、
前記置換手段は、当該置換手段を含む前記アドレス部のエントリアドレスが「ｉ」であり、前記フリーアドレスと等しい第３のアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレスが「ｎ」であるものとすると、
前記「ｗｐ」が前記「ｎ」以下である第１の状態において、前記「ｉ」が前記「ｗｐ」以上で、前記「ｎ」以下である第１の条件に合致する第１の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換し、
前記「ｗｐ」が前記「ｎ」より大きい第２の状態において、前記「ｉ」が前記「ｎ」以下であるか、或いは前記「ｗｐ」以上である第２の条件に合致する第２の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換する
請求項１記載のコマンド管理装置。
【請求項３】
前記先入れ先出し手段のエントリ群のそれぞれのアドレス部は、前記アドレスを格納するのに用いられる、所定のクロック信号で動作するフリップフロップを備えている請求項２記載のコマンド管理装置。
【請求項４】
前記エントリアドレスが「ｉ」のアドレス部の前記置換手段は、
前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部の前記フリップフロップに格納されている前記第２のアドレスのいずれか一方を、前記「ｉ」が前記「ｗｐ」に等しいかに応じて選択する第１のセレクタと、
前記第１の場合と前記第２の場合のそれぞれの場合に、前記第１のセレクタによって選択されたアドレスを選択し、前記第１の場合または前記第２の場合のいずれでもない場合に、前記エントリアドレスが「ｉ」のアドレス部の前記フリップフロップに格納されている前記第１のアドレスを選択する第２のセレクタとを備えており、
前記エントリアドレスが「ｉ」のアドレス部の前記フリップフロップは、前記第２のセレクタによって選択されたアドレスを、前記クロック信号に応じて格納する
請求項３記載のコマンド管理装置。
【請求項５】
前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記置換手段を制御する置換制御手段を更に具備し、
前記置換制御手段は、前記先入れ先出し手段の前記エントリの群にそれぞれ対応して設けられる選択制御手段を備え、
前記選択制御手段は、対応する前記エントリのエントリアドレスが「ｉ」である場合、前記第１の場合と前記第２の場合のそれぞれを検出することにより、前記第２のセレクタが前記第１のセレクタによって選択されたアドレスを選択するように制御する
請求項４記載のコマンド管理装置。
【請求項６】
前記選択制御手段は、
前記「ｉ」が前記第１の条件に合致することを検出して第１の検出信号を出力する第１の検出器と、
前記「ｉ」が前記第２の条件に合致することを検出して第２の検出信号を出力する第２の検出器と、
前記第１の状態において前記第１の検出信号を選択し、前記第２の状態において前記第２の検出信号を選択する第３のセレクタとを備えており、
前記第２のセレクタは、前記第３のセレクタによって選択された信号に応じて、前記第１のセレクタによって選択されたアドレスまたは前記第１のアドレスを選択する
請求項５記載のコマンド管理装置。
【請求項７】
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、次に取り出されるべきコマンドが格納されている前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段のアドレス部のエントリアドレス「ｒｐ」を指し示すリードポインタを更に具備し、
前記リードポインタは、前記置換手段による置換時に、当該リードポインタの指すエントリアドレス「ｒｐ」が、前記第１の状態において、前記「ｗｐ」以上で、前記「ｎ」以下であるか、または、前記第２の状態において、前記「ｎ」以下であるか、もしくは前記「ｗｐ」以上である場合、次段のエントリを指し示すように更新される
請求項２記載のコマンド管理装置。
【請求項８】
前記フリーアドレスを、前記先入れ先出し手段のエントリ群のそれぞれのアドレス部に格納されているアドレスと比較することにより、前記フリーアドレスと等しい前記第３のアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレス「ｎ」を検出する検出手段を更に具備する請求項２記載のコマンド管理装置。
【請求項９】
前記検出手段は、
前記先入れ先出し手段のエントリ群にそれぞれ対応して設けられ、前記フリーアドレスを、対応するエントリのアドレス部に格納されているアドレスと比較する比較器の群と、
前記比較器の群のそれぞれの比較結果の組み合わせを、当該組み合わせにおける一致を示す比較結果の位置に応じて前記エントリアドレス「ｎ」に変換する変換器とを備えている
請求項８記載のコマンド管理装置。
【請求項１０】
前記先入れ先出し手段の前記エントリ群のそれぞれのアドレス部には、前記コマンドバッファの異なる領域のアドレスが初期設定される
請求項８記載のコマンド管理装置。
【請求項１１】
ホストから受信されたコマンドの群を管理するコマンド管理装置と、
記憶部と、
前記記憶部にアクセスする処理手段とを具備し、
前記コマンド管理装置は、
ホストから受信されたコマンドの群を格納するコマンドバッファと、
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するアドレス部を含むエントリの群を備えた先入れ先出し手段と、
不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスをフリーアドレスとして保持するフリーアドレス設定手段とを具備し、
前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記アドレス部はリング状に接続されており、当該アドレス部は、当該アドレス部に格納されている第１のアドレスを、前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する置換手段を含み、
前記処理手段は、前記先入れ先出し手段の前記エントリ群のそれぞれのアドレス部に格納されているアドレスをシーケンシャルに読み出して、その読み出されたアドレスに基づいて前記コマンドバッファにアクセスすることにより、当該読み出されたアドレスで指定される前記コマンドバッファ内の領域からコマンドを取り出し、当該取り出されたコマンドに応じて前記記憶部にアクセスする
記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ホストから受信されたコマンドの群を保持・管理する、コマンド管理装置及び同コマンド管理装置を備えた記憶装置に関する。
【背景技術】
【０００２】
磁気ディスクドライブ（ＨＤＤ）、或いはソリッドステートドライブ（ＳＳＤ）のような記憶装置は、一般にホストインタフェース部を備えている。ホストインタフェース部は、ホストと記憶装置との間のデータ転送を制御する。ホストインタフェース部は、コマンド管理装置を備えている。コマンド管理装置は、ホストから転送される、リードコマンド、或いはライトコマンドのようなコマンドを受信して、当該受信されたコマンドをコマンドバッファに格納する。コマンドバッファに格納されたコマンドの群は、コマンド管理装置の管理の下で、格納順に処理部に取り出される。処理部は、取り出されたコマンドを実行する。
【０００３】
コマンドバッファから取り出されたコマンドの実行が完了すると、当該コマンドは不要になる。すると、不要になったコマンドが格納されている、コマンドバッファの領域（以下、不要領域と称する）を解放する必要がある。このような不要領域の解放（つまりコマンドバッファのメンテナンス）は、コンパクション或いはガーベージコレクションのようなソフトウェア処理により実行される。
【０００４】
一方、デジタル通信システムにおいて、受信データを順次格納するデータバッファを備えたバッファ管理サブシステムも知られている。このバッファ管理サブシステムは、データバッファ内の空き領域（つまり不要領域）を指すバッファポインタを格納する先入れ先出し（First-In First-Out）バッファ（以下、バッファポインタＦＩＦＯと称する）を備えている。受信データは、バッファポインタＦＩＦＯから取り出されるバッファポインタによって指定されるデータバッファ内の領域に格納される。データバッファに格納されたデータの群は格納順に取り出され、宛先に転送される。データバッファからデータが取り出されると、当該取り出されたデータが格納されている、データバッファの領域は空き領域なる。そこで、この空き領域を指すバッファポインタがバッファポインタＦＩＦＯに格納される。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０００−９００４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述のコンパクション或いはガーベージコレクションを用いた場合、コマンドバッファ内の不要領域を高速に解放することは難しい。
【０００７】
一方、コマンドバッファに格納されたコマンドの群の実行が完了する順番は、当該コマンドバッファからコマンドの群が取り出される順番と必ずしも一致しない。このため、コマンドバッファに格納されているコマンド群の物理的な並びは、コマンドの群の取り出し順（つまり格納順）に対して時間の経過と共に大きくずれる。したがって、コマンドバッファに格納されたコマンドの群を格納順に取り出す必要のあるコマンド管理装置において、コンパクション或いはガーベージコレクションに代えて、バッファポインタＦＩＦＯを用いることによって、コマンドバッファ内の不要領域を解放することは難しい。
【０００８】
本発明の目的は、不要となったコマンドが格納されている領域をコンパクション或いはガーベージコレクションを用いずに解放することができるコマンド管理装置及び同コマンド管理装置を備えた記憶装置を提供することにある。
【課題を解決するための手段】
【０００９】
実施形態によれば、コマンド管理装置は、コマンドバッファと、先入れ先出し手段と、フリーアドレス設定手段とを具備する。コマンドバッファは、ホストから受信されたコマンドの群を格納する。先入れ先出し手段は、前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納する。フリーアドレス設定手段は、不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスをフリーアドレスとして保持する。前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記アドレス部はリング状に接続されており、当該アドレス部は、当該アドレス部に格納されている第１のアドレスを、前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する置換手段を含む。
【図面の簡単な説明】
【００１０】
【図１】実施形態に係るコマンド管理装置の構成を示すブロック図。
【図２】同実施形態におけるコマンド格納時の動作を説明するための図。
【図３】図２に示したコマンド格納が完了した後の、コマンドヒストリーＦＩＦＯ部の状態を示す図。
【図４】同実施形態におけるコマンド取り出し時の動作を説明するための図。
【図５】図４に示したコマンド取り出しが完了した後の、コマンドヒストリーＦＩＦＯ部の状態を示す図。
【図６】同実施形態におけるコマンドヒストリーＦＩＦＯ部の初期状態の一例を示す図。
【図７】同実施形態における第１の状態のときのアドレス解放を説明するための図。
【図８】同実施形態における第１の状態のときのアドレス解放の具体例を説明するための図。
【図９】同実施形態における第２の状態のときのアドレス解放を説明するための図。
【図１０】同実施形態における第２の状態のときのアドレス解放の具体例を説明するための図。
【図１１】同実施形態における検出回路の構成を示すブロック図。
【図１２】同実施形態におけるアドレスＦＩＦＯ部の０番目のエントリを除くｉ番目のエントリの構成を示す図。
【図１３】同実施形態における「ｉ」が「０」の場合のアドレスＦＩＦＯ部のｉ番目のエントリの構成を示す図。
【図１４】同実施形態におけるフラグＦＩＦＯ部の０番目のエントリを除くｉ番目のエントリの構成を示す図。
【図１５】同実施形態における「ｉ」が「０」の場合のフラグＦＩＦＯ部のｉ番目のエントリの構成を示す図。
【図１６】同実施形態におけるアドレス解放時に、アドレスＦＩＦＯ部のｉ番目のエントリに格納されているアドレスＡがアドレスＢに置換される場合のタイミングチャート。
【図１７】同実施形態における、リードポインタの指し示すコマンドヒストリーＦＩＦＯ部のエントリのアドレス部及びフラグ部を取り出す選択回路の構成を示すブロック図。
【図１８】同実施形態における選択制御回路の構成を示すブロック図。
【発明を実施するための形態】
【００１１】
以下、実施の形態につき図面を参照して説明する。  
図１は一つの実施形態に係るコマンド管理装置の構成を示すブロック図である。
【００１２】
本実施形態において、図１に示すコマンド管理装置１は、磁気ディスクドライブ、或いはソリッドステートドライブのような記憶装置のホストインタフェース部に備えられている。記憶装置は、コマンド管理装置１の他に、処理部２及び記憶部３を備えている。記憶部３は、記憶装置が磁気ディスクドライブであれば、磁気記録媒体及びヘッドを含み、記憶装置がソリッドステートドライブであれば、書き換え可能な不揮発性メモリを含む。
【００１３】
コマンド管理装置１は、コマンドヒストリーＦＩＦＯ部１０とコマンドバッファ２０とを備えている。  
コマンドバッファ２０は、ホストから受信したコマンド群を格納する。コマンドバッファ２０は、Ｎ個のエントリＥＮＴ(0)〜ＥＮＴ(N-1)を有するテーブル（以下、コマンドテーブルと称する）２１から構成される。Ｎは、コマンド管理装置１によって同時に管理されるべきコマンドの最大数から決定される。本実施形態において、Ｎは１２８であり、コマンド管理装置１によって最大１２８個のコマンドが同時に管理される。
【００１４】
コマンドテーブル２１は、メモリを用いて実現される。コマンドテーブル２１の各エントリＥＮＴ(u)（ｕ＝０，１，…１２７）の大きさ（記憶容量）は、受信されるべきコマンドの長さに依存する。ここでは、コマンドが３２ビットバスを介してコマンドテーブル２１内のエントリＥＮＴ(u)に格納され、且つ当該コマンドの長さが８ワード（１ワード＝３２ビット）であるものとする。この場合、コマンドテーブル２１の各エントリＥＮＴ(u)の大きさは、３２ビット×８＝２５６ビットとなる。したがってコマンドテーブル２１は、Ｎが１２８である本実施形態では、３２ビット×８×１２８＝３２７６８ビット＝１０２４ワードのメモリから構成される。
【００１５】
コマンドヒストリーＦＩＦＯ部１０は、コマンドテーブル２１のＮ個（Ｎ＝１２８）のエントリＥＮＴ(0)〜ＥＮＴ(N-1)のそれぞれのアドレス（ＡＤＤＲＥＳＳ）及び当該エントリＥＮＴ(0)〜ＥＮＴ(N-1)のそれぞれにおけるコマンドの格納状態を示すフラグの群を保持・管理する先入れ先出しバッファ部として用いられる。コマンドテーブル２１に格納されたコマンドの群は、コマンドヒストリーＦＩＦＯ部１０の管理の下で格納順に取り出される。コマンドヒストリーＦＩＦＯ部１０は、アドレスＦＩＦＯ部１１、フラグＦＩＦＯ部１２、フリーアドレス設定部１３、検出回路１４及び置換制御回路１５を備えている。
【００１６】
アドレスＦＩＦＯ部１１は、主として、コマンドテーブル２１のＮ個（Ｎ＝１２８）のエントリＥＮＴ(0)〜ＥＮＴ(N-1)のｍビットのアドレスを保持するためのＮ個のｍビットのフリップフロップから構成される。「ｍ」は、「Ｎ−１」までの数字を表すことが可能なバイナリデータのビット数である。本実施形態では、Ｎ−１＝１２７（０ｘ７Ｆ）であるので、ｍ＝７である。
【００１７】
フラグＦＩＦＯ部１２は、主として、上記エントリＥＮＴ(0)〜ＥＮＴ(N-1)のそれぞれにおけるコマンドの格納状態を示すフラグの群を保持するためのＮ個のフリップフロップ組から構成される。Ｎ個のフリップフロップ組の各々は、ｋ個のフラグを保持するための、ｋ個の１ビットのフリップフロップから構成される。ｋは管理されるべきフラグの種類の数から決定される。本実施形態では、管理されるべきフラグの種類は、後述するＲフラグ（未読フラグ）及びＵフラグ（使用中フラグ）の２種類であり、したがってｋ＝２である。しかしｋは、他に管理されるべき種類のフラグが必要ならば増やされてもよく、不要な種類のフラグがあるならば減らされてもよい。
【００１８】
アドレスＦＩＦＯ部１１のＮ個（Ｎ＝１２８）のｍビットのフリップフロップのうちのｖ番目（ｖ＝０，１，…Ｎ−１）のｍビットのフリップフロップと、フラグＦＩＦＯ部１２のＮ個のフリップフロップ組のうちのｖ番目のフリップフロップ組との組み合わせを、アドレスＦＩＦＯ部１１のｖ番目のエントリまたはエントリｖと呼び、ｃｆｉｆｏ[v]のように表現する。また、ｖをｃｆｉｆｏ[v]のアドレス（エントリアドレス）、つまりアドレスＦＩＦＯ部１１及びフラグＦＩＦＯ部１２のアドレス（エントリアドレス）と称する。ｃｆｉｆｏ[v]に対応するアドレスＦＩＦＯ部１１の部分をｃｆｉｆｏ[v]のアドレス部、ｃｆｉｆｏ[v]に対応するフラグＦＩＦＯ部１２の部分をｃｆｉｆｏ[v]のフラグ部と、それぞれ称する。
【００１９】
フリーアドレス設定部１３は、不要になったコマンドがコマンドテーブル２１内の例えばエントリＥＮＴ(u)に格納されている場合、当該エントリＥＮＴ(u)のアドレス「ｕ」を次フリーアドレス（ＮＥＸＴ  ＦＲＥＥ  ＡＤＤＲＥＳＳ）として設定するのに用いられる。フリーアドレス設定部１３は、後述するアドレス解放処理において用いられる。  
検出回路１４及び置換制御回路１５に関する説明は後述する。
【００２０】
コマンドヒストリーＦＩＦＯ部１０はまた、ｍビット（ｍ＝７）のライトポインタｗｐ及びリードポインタｒｐを備えている。  
ライトポインタｗｐは、ホストから転送された、リードコマンド、或いはライトコマンドのようなコマンドをコマンドテーブル２１に格納する際に、当該コマンドが格納されるべきコマンドテーブル２１のエントリのアドレスを格納しているｃｆｉｆｏ[wp]のアドレス「ｗｐ」を指し示す。ライトポインタｗｐによって指定される、ｃｆｉｆｏ[wp]のアドレス部に格納されているアドレスは、書き込みアドレス（ＷＲＩＴＥ  ＡＤＤＲＥＳＳ）としてコマンドヒストリーＦＩＦＯ部１０からコマンドバッファ２０に出力される。
【００２１】
リードポインタｒｐは、コマンドテーブル２１から次に実行されるべきコマンドを取り出す際に用いられる。リードポインタｒｐは、取り出されるべきコマンドが格納されているコマンドテーブル２１のエントリのアドレスを格納しているｃｆｉｆｏ[rp]のアドレス「ｒｐ」を指し示す。リードポインタｒｐによって指定される、ｃｆｉｆｏ[rp]のアドレス部に格納されているアドレスは、読み出しアドレス（ＲＥＡＤ  ＡＤＤＲＥＳＳ）としてコマンドヒストリーＦＩＦＯ部１０から、処理部２に出力される。
【００２２】
処理部２は、コマンドヒストリーＦＩＦＯ部１０から出力される読み出しアドレスを用いて、当該読み出しアドレスで指定されるコマンドテーブル２１内のエントリからコマンドを取り出す。処理部２は取り出されたコマンドを実行する。処理部２は、取り出されたコマンドが、リードコマンドまたはライトコマンドの場合、記憶部３からデータを読み出す、または記憶部３にデータを書き込む。処理部２は、これらの動作を、例えばファームウェア（以下、ＦＷと称する）に従って実行する。
【００２３】
次に、本実施形態におけるコマンド格納時の動作について、図２を参照して説明する。  
今、記憶装置のホストインタフェース部がホストから転送されたコマンドを受信した結果、当該受信されたコマンドをコマンド管理装置１のコマンドテーブル２１に格納するためのコマンド格納動作が行われるものとする。このとき、コマンドヒストリーＦＩＦＯ部１０のライトポインタｗｐが「２０」であり、図２に示すように、当該コマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[20]を指しているものとする。
【００２４】
この場合、ライトポインタｗｐ（＝２０）の指し示すｃｆｉｆｏ[20]が選択される。そして、選択されたｃｆｉｆｏ[20]のアドレス部に格納されているアドレス（図２の例では６５）が、書き込みアドレス（ＷＲＩＴＥ  ＡＤＤＲＥＳＳ）としてコマンドバッファ２０に出力される。これにより、ホストから受信されたコマンドは、書き込みアドレス「６５」によって指定される、コマンドテーブル２１内のエントリＥＮＴ(65)に格納される。コマンドの大きさが８ワードで、当該コマンドをコマンドバッファ２０に転送するのに用いられるバスのデータ幅が３２ビットであるものとすると、コマンドテーブル２１内のエントリＥＮＴ(65)にコマンドを格納するのに、８バスサイクルを要する。
【００２５】
コマンドテーブル２１へのコマンドの格納が完了すると、上記選択されたｃｆｉｆｏ[20]（つまりライトポインタｗｐの指し示すｃｆｉｆｏ[20]）内のＲフラグ（より詳細にはフラグ部内のＲフラグ）及びＵフラグ（より詳細にはフラグ部内のＵフラグ）がそれぞれセットされる。また、ライトポインタｗｐがインクリメントされる。この例では、ライトポインタｗｐが「２０」から「２１」にインクリメントされる。
【００２６】
なお、Ｎ＝１２８の本実施形態のように、「Ｎ−１」が２進数で“１”のみで表される場合であれば、ライトポインタｗｐは、そのときの値に無関係にインクリメントされてよい。しかし「Ｎ−１」が、例えば１５９のように、２進数で“１”のみで表されない場合には、ライトポインタｗｐが「Ｎ−１」を指しているときに限り、当該ライトポインタｗｐはインクリメントされるのではなく、０に戻される。本実施形態では、アドレス「０」はアドレス「Ｎ−１」から連続していると見なすことができる。このことは、リードポインタｒｐについても同様である。つまり本実施形態では、ライトポインタｗｐ及びリードポインタｒｐは、シーケンシャルに更新される。
【００２７】
ライトポインタｗｐの指し示すｃｆｉｆｏ[wp]のアドレス部に格納されたアドレスが「ｕ」であるものとする。この場合、ｃｆｉｆｏ[wp]内のＲフラグは、当該ｃｆｉｆｏ[wp]のアドレス部に格納されたアドレス（以下、対応するアドレスと称する）「ｕ」によって指定される、コマンドテーブル２１内のエントリＥＮＴ(u)に格納されているコマンドが未だ読み出されていないことを示す。ｃｆｉｆｏ[wp]内のＵフラグは、対応するアドレス「ｕ」によって指定される、コマンドテーブル２１内のエントリＥＮＴ(u)に格納されているコマンドの実行が未だ完了していないこと、つまり使用中であることを示す。図２は、ｗｐ＝２０、ｕ＝６５の場合である。
【００２８】
ライトポインタｗｐの指し示すｃｆｉｆｏ[wp]内のＵフラグがセットされているときは、実行完了していないコマンドが新規コマンドで上書きされないように、ホストからのコマンドの受信を制限してもよい。
【００２９】
次に、本実施形態におけるコマンド格納完了時の動作について、図３を参照して説明する。図３は、図２に示したコマンド格納が完了した後の、コマンドヒストリーＦＩＦＯ部１０の状態を示す。
【００３０】
図２に示したコマンド格納が完了した場合、図３に示すように、ｃｆｉｆｏ[20]内のＲフラグ及びＵフラグがセットされ、ライトポインタｗｐは「２０」から「２１」にインクリメントされている。この状態で、ホストから新たにコマンドが受信されると、今度はｃｆｉｆｏ[21]のアドレス部に格納されているアドレス「７４」が書き込みアドレスとしてコマンドバッファ２０へ出力される。これにより、新たに受信されたコマンドはコマンドテーブル２１内のエントリＥＮＴ(74)に格納される。
【００３１】
次に、本実施形態におけるコマンド取り出し時の動作について、図４を参照して説明する。本実施形態では、コマンド取り出しは、処理部２によってＦＷに従って行われる。
【００３２】
今、コマンドヒストリーＦＩＦＯ部１０のリードポインタｒｐが「１」であり、図４に示すように、当該コマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[1]を指しているものとする。
【００３３】
本実施形態では、処理部２が、ある１つのレジスタ領域（以下、ＣＦＩＦＯトップ部と称する）にリードアクセスすると、リードポインタｒｐの指し示すｃｆｉｆｏ[rp]のアドレス部及びフラグ部が、コマンドヒストリーＦＩＦＯ部１０から当該処理部２に出力されるように構成されている。図４の例ではｒｐ＝１であることから、ｃｆｉｆｏ[1]が選択される。ｃｆｉｆｏ[1]のアドレス部にはアドレス「８」が格納されている。このアドレス「８」が、読み出しアドレス（ＲＥＡＤ  ＡＤＤＲＥＳＳ）として処理部２に出力される。処理部２は、この読み出しアドレス「８」を使用する。
【００３４】
処理部２は、コマンドヒストリーＦＩＦＯ部１０から読み出しアドレス「８」が出力される際に、当該コマンドヒストリーＦＩＦＯ部１０から出力されるフラグ部内のＲフラグがセットされているならば、そのアドレス「８」によって指定される、コマンドテーブル２１内のエントリＥＮＴ(8)に格納されているコマンドを未だ取り出していないことを認識できる。そこで処理部２は、ＣＦＩＦＯトップ部にアクセスすることにより、コマンドヒストリーＦＩＦＯ部１０（より詳細には、リードポインタｒｐ（＝１）の指し示すｃｆｉｆｏ[1]）から読み出したアドレス（読み出しアドレス）「８」に基づいて、コマンドテーブル２１にアクセスする。これにより処理部２は、コマンドテーブル２１のエントリＥＮＴ(8)に格納されているコマンドを取り出す。  
処理部２は、コマンド取り出しを完了すると、ｃｆｉｆｏ[1]内のＲフラグをクリア（ここではゼロクリア）し、リードポインタｒｐをインクリメントする。なお、処理部２からのコマンド取り出し完了に応じて、リードポインタｒｐが自動的にインクリメントされる構成としてもよい。同様に、処理部２からのコマンド取り出し完了に応じて、Ｒフラグが自動的にクリアされる構成としてもよい。
【００３５】
次に、本実施形態におけるコマンド取り出し完了時の動作について、図５を参照して説明する。図５は、図４に示したコマンド取り出しが完了した後の、コマンドヒストリーＦＩＦＯ部１０の状態を示す。
【００３６】
図４に示したコマンド取り出しが完了した場合、図５に示すように、ｃｆｉｆｏ[1]内のＲフラグがクリアされ、リードポインタｒｐは「１」から「２」にインクリメントされている。この状態で、処理部２がＣＦＩＦＯトップ部にリードアクセスすると、今度はｃｆｉｆｏ[2]のアドレス部に格納されているアドレス「５４」が読み出しアドレスとして処理部２に出力される。このアドレス「５４」を用いて処理部２は、コマンドテーブル２１のエントリＥＮＴ(54)に格納されているコマンドを取り出すことができる。  
本実施形態によれば、ホストから受信したコマンドの群を、図２乃至図５を参照して説明したような動作によって、その受信順に処理部２が取り出すことができる。
【００３７】
次に、本実施形態におけるコマンドヒストリーＦＩＦＯ部１０の初期状態について、図６を参照して説明する。  
図６に示すように、コマンドヒストリーＦＩＦＯ部１０の初期状態では、全てのｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]内のＲフラグとＵフラグはクリアされている。ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]のアドレス部には、それぞれアドレス「０」〜「１２７」が初期設定される。このように初期状態では、コマンドヒストリーＦＩＦＯ部１０のアドレスＦＩＦＯ部１１には、アドレス「０」〜「１２７」が昇順に整列している。しかし、この並びは、後述するアドレス解放動作の繰り返しに応じて崩れていく。なお、ライトポインタｗｐ及びリードポインタｒｐは、初期状態では、いずれも「０」に設定される。
【００３８】
次に本実施形態における第１の状態でのアドレス解放について、図７を参照して説明する。第１状態とは、後述するｗｐ≦ｎの場合を指す。
【００３９】
コマンドテーブル２１から取り出されたコマンドの実行が完了した場合、当該コマンドは不要になる。また、コマンドテーブル２１に格納されたコマンドを実行せずにアボートする場合にも、当該コマンドは不要になる。ここで、不要になったコマンドが格納されているコマンドテーブル２１のエントリ（領域）がＥＮＴ(u)であり、当該エントリＥＮＴ(u)のアドレス「ｕ」を格納しているコマンドヒストリーＦＩＦＯ部１０内のエントリがエントリ「ｎ」（ｎは０〜１２７のいずれか）、つまりｃｆｉｆｏ[n]であるものとする。この場合、フリーアドレス設定部１３には、アドレス「ｕ」が設定されている。
【００４０】
さて、コマンドテーブル２１のエントリＥＮＴ(u)に格納されているコマンドが不要となった場合、当該エントリＥＮＴ(u)（つまり、不要になったコマンドが格納されているエントリＥＮＴ(u)）を解放する必要がある。アドレス解放とは、このコマンドテーブル２１のエントリＥＮＴ(u)を解放することを指す。また、解放されたコマンドテーブル２１のエントリＥＮＴ(u)のアドレス「ｕ」を、解放されたアドレスと称する。コマンドテーブル２１のエントリＥＮＴ(u)を解放した際には、以下に述べるように、当該エントリＥＮＴ(u)のアドレス「ｕ」も解放される。また、エントリＥＮＴ(u)のアドレス「ｕ」を解放することは、当該アドレス「ｕ」を格納しているｃｆｉｆｏ[n]を解放することと等価である。
【００４１】
本実施形態において、アドレス解放は、処理部２によりＦＷに従って行われる。処理部２によってアドレス解放が行われると、解放されたアドレス「ｕ」が、現在のｃｆｉｆｏ[n]のアドレス部から、ライトポインタｗｐの指し示すコマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[wp]のアドレス部に移される。これによりｃｆｉｆｏ[n]も解放される。また、ホストから次のコマンドが受信された場合、当該次のコマンドは、最後に解放されたアドレス「ｕ」で指定される、コマンドテーブル２１のエントリＥＮＴ(u)に格納される。
【００４２】
以下、処理部２によるアドレス解放の手順について説明する。このアドレス解放は、ＦＷに従って、コマンドヒストリーＦＩＦＯ部１０と協働して行われるが、全てハードウェア（ＨＷ）により行われる構成としてもよい。
【００４３】
処理部２は、解放されるべきアドレス「ｕ」を次フリーアドレス（ＮＥＸＴ  ＦＲＥＥ  ＡＤＤＲＥＳＳ）としてフリーアドレス設定部１３に設定する。そして処理部２は、アドレス解放処理を起動する。
【００４４】
すると、コマンドヒストリーＦＩＦＯ部１０は、ライトポインタｗｐが指し示すｃｆｉｆｏ[wp]のアドレス部を、フリーアドレス設定部１３に設定されている次フリーアドレス「ｕ」に置換する。この置換の詳細については後述する。このとき、ｃｆｉｆｏ[wp]内のＲフラグ及びＵフラグは、いずれもクリアされる（初期値に戻る）。
【００４５】
さて、次フリーアドレス「ｕ」と等しいアドレス「ｕ」は、コマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]のいずれかのアドレス部（前述の例では、ｃｆｉｆｏ[n]のアドレス部）に必ず格納されている。しかし本実施形態において、ｃｆｉｆｏ[wp]のアドレス部の置換に用いられるアドレス「ｕ」は、フリーアドレス設定部１３に設定されている次フリーアドレス「ｕ」であることに注意されたい。
【００４６】
もし、フリーアドレス設定部１３を適用しないならば、ｃｆｉｆｏ[wp]の入力に、ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]のうちのｃｆｉｆｏ[wp]以外の１２７のｃｆｉｆｏの中から、アドレス「ｕ」を格納しているｃｆｉｆｏ[n]のアドレス部を選択する、１２７入力１出力のマルチプレクサの出力を接続する必要がある。ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]のうち、ｃｆｉｆｏ[wp]を除く各ｃｆｉｆｏの入力についても同様である。
【００４７】
このときコマンドヒストリーＦＩＦＯ部１０は、コマンドの群の受信（格納）順にＣＦＩＦＯトップ部を介してアドレスＦＩＦＯ部１１から対応するアドレスが読み出せることを保証するために、コマンドヒストリーＦＩＦＯ部１０のエントリを置換する必要がある。
【００４８】
前述したように、次フリーアドレス「ｕ」と等しいアドレス「ｕ」が格納されている、コマンドヒストリーＦＩＦＯ部１０のエントリが、エントリ「ｎ」、つまりｃｆｉｆｏ[n]であるものとする。もし、「ｗｐ」が「ｎ」以下（ｗｐ≦ｎ）である第１の状態のときは、コマンドヒストリーＦＩＦＯ部１０は、図７に示すように、ｗｐ以上ｎ以下を満足する全てのアドレス「ｉ」（ｗｐ≦ｉ≦ｎ）で指定される、コマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[i]のアドレス部及びフラグ部を、以下のように置換する。ｎを検出するための構成については後述する。図７の例では、ｗｐ＝２、ｎ＝２１である。  
ａ１）ｉ＝ｗｐ
ｉ＝ｗｐでは、コマンドヒストリーＦＩＦＯ部１０は、
新しいｃｆｉｆｏ[i]のアドレス部＝次フリーアドレス「ｕ」
新しいｃｆｉｆｏ[i]内のＲフラグ＝０（Ｒフラグの初期値）
新しいｃｆｉｆｏ[i]内のＵフラグ＝０（Ｕフラグの初期値）
のように置換する。
【００４９】
ａ２）ｉ＝ｗｐ以外のｉ（ｗｐ＜ｉ≦ｎ）
ｗｐ＜ｉ≦ｎでは、コマンドヒストリーＦＩＦＯ部１０は、
新しいｃｆｉｆｏ[i]のアドレス部＝旧ｃｆｉｆｏ[i-1]内のアドレス
新しいｃｆｉｆｏ[i]内のＲフラグ＝旧ｃｆｉｆｏ[i-1]内のＲフラグ
新しいｃｆｉｆｏ[i]内のＵフラグ＝旧ｃｆｉｆｏ[i-1]内のＵフラグ
のように置換する。旧ｃｆｉｆｏ[i-1]内のアドレスとは、置換前に、ｃｆｉｆｏ[i]の前段のｃｆｉｆｏ[i-1]のアドレス部に格納されているアドレスを指す。
【００５０】
また、リードポインタｒｐが、コマンドヒストリーＦＩＦＯ部１０内の置換されるエントリの１つを指している（ｗｐ≦ｒｐ≦ｎ）ときは、処理部２はアドレス解放処理の際に、当該リードポインタｒｐをインクリメントする。なお、リードポインタｒｐが、アドレス解放処理の際に自動的にインクリメントされる構成としてもよい。
【００５１】
次に、上述の第１の状態（ｗｐ≦ｎ）のときのアドレス解放の具体例について、図８を参照して説明する。  
まず、図８に示すように、ライトポインタｗｐが「２」、リードポインタｒｐが「１９」であるものとする。また、フリーアドレス設定部１３に設定されている次フリーアドレス「ｕ」（つまり解放されるべきアドレス）が「３７」であり、この次フリーアドレス「ｕ」と等しいアドレス「３７」が、コマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[21]（ｎ＝２１）のアドレス部に格納されているものとする。このような例では、コマンドヒストリーＦＩＦＯ部１０内の置換されるエントリ「ｉ」の範囲は、図８において矩形８１で示されるように２≦ｉ≦２１である。
【００５２】
この場合、コマンドヒストリーＦＩＦＯ部１０は、図８において矢印８２で示すように、矩形８１で示される範囲に対して、
新しいｃｆｉｆｏ[2]のアドレス部＝次フリーアドレス「ｕ」＝３７
新しいｃｆｉｆｏ[2]内のＲフラグ＝０
新しいｃｆｉｆｏ[2]内のＵフラグ＝０
新しいｃｆｉｆｏ[3]のアドレス部＝旧ｃｆｉｆｏ[2]内のアドレス＝８０
新しいｃｆｉｆｏ[3]内のＲフラグ＝旧ｃｆｉｆｏ[2]内のＲフラグ＝０
新しいｃｆｉｆｏ[3]内のＵフラグ＝旧ｃｆｉｆｏ[2]内のＵフラグ＝０
…
新しいｃｆｉｆｏ[20]のアドレス部＝旧ｃｆｉｆｏ[19]内のアドレス＝２９
新しいｃｆｉｆｏ[20]内のＲフラグ＝旧ｃｆｉｆｏ[19]内のＲフラグ＝１
新しいｃｆｉｆｏ[20]内のＵフラグ＝旧ｃｆｉｆｏ[19]内のＵフラグ＝１
新しいｃｆｉｆｏ[21]のアドレス部＝旧ｃｆｉｆｏ[20]内のアドレス＝１１１
新しいｃｆｉｆｏ[21]内のＲフラグ＝旧ｃｆｉｆｏ[20]内のＲフラグ＝１
新しいｃｆｉｆｏ[21]内のＵフラグ＝旧ｃｆｉｆｏ[20]内のＵフラグ＝１
のように置換する。
【００５３】
コマンドヒストリーＦＩＦＯ部１０内の、２≦ｉ≦２１の範囲に含まれないｃｆｉｆｏ[i]については、何も変わらない。  
また、図８の例では、リードポインタｒｐが「１９」であり、コマンドヒストリーＦＩＦＯ部１０内の置換されるエントリの１つを指している（２≦ｒｐ≦２１）。このため、リードポインタｒｐは「１９」から「２０」にインクリメントされる。
【００５４】
このように本実施形態によれば、使用中（Ｕフラグ＝１）であったコマンドが格納されていた、次フリーアドレス「３７」によって指定されるコマンドテーブル２１内のエントリＥＮＴ(37)と、当該エントリＥＮＴ(37)を指定するアドレス「３７」と、当該アドレス「３７」が格納されているコマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[21]（ｎ＝２１）とが解放される。これにより、ホストから次のコマンドが受信された場合、当該次のコマンドは、コマンドテーブル２１内の解放されたエントリＥＮＴ(37)に格納される。
【００５５】
次に、本実施形態における第２の状態でのアドレス解放について、図９を参照して説明する。第２の状態とは、「ｗｐ」が「ｎ」より大きい場合（ｎ＜ｗｐ）を指す。ここでも、フリーアドレス設定部１３に設定されている次フリーアドレス「ｕ」と等しいアドレス「ｕ」が格納されている、コマンドヒストリーＦＩＦＯ部１０内のエントリがｃｆｉｆｏ[n]であるものとする。
【００５６】
図９の例でも、処理部２によってアドレス解放処理が起動されることにより、コマンドヒストリーＦＩＦＯ部１０は、ライトポインタｗｐが指し示すｃｆｉｆｏ[wp]のアドレス部を、フリーアドレス設定部１３に設定されている次フリーアドレス「ｕ」に置換する。このとき、ｃｆｉｆｏ[wp]内のＲフラグ及びＵフラグは、いずれもクリアされる。
【００５７】
またコマンドヒストリーＦＩＦＯ部１０は、ｎ以下を満足する全てのアドレス「ｉ」（ｉ≦ｎ）と、ｗｐ以上を満足する全てのアドレス「ｉ」（ｗｐ≦ｉ）とで指定される、コマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[i]のアドレス部及びフラグ部を、以下のように置換する。但しアドレス「ｉ」の下限は「０」であり、上限は１２７である。図９の例では、ｗｐ＝１２６、ｎ＝１９である。
【００５８】
ｂ１）ｉ＝ｗｐ
ｉ＝ｗｐでは、コマンドヒストリーＦＩＦＯ部１０は、
新しいｃｆｉｆｏ[i]のアドレス部＝次フリーアドレス「ｕ」
新しいｃｆｉｆｏ[i]内のＲフラグ＝０（Ｒフラグの初期値）
新しいｃｆｉｆｏ[i]内のＵフラグ＝０（Ｕフラグの初期値）
のように置換する。
【００５９】
ｂ２）ｉ＝ｗｐ以外のｉ（ｉ≦ｎまたはｗｐ＜ｉ）
ｉ≦ｎ（０≦ｉ≦ｎ）またはｗｐ＜ｉ（ｗｐ＜ｉ≦１２７）では、コマンドヒストリーＦＩＦＯ部１０は、
新しいｃｆｉｆｏ[i]のアドレス部＝旧ｃｆｉｆｏ[i-1]内のアドレス
新しいｃｆｉｆｏ[i]内のＲフラグ＝旧ｃｆｉｆｏ[i-1]内のＲフラグ
新しいｃｆｉｆｏ[i]内のＵフラグ＝旧ｃｆｉｆｏ[i-1]内のＵフラグ
のように置換する。但し、新しいｃｆｉｆｏ[0]は、旧ｃｆｉｆｏ[127]の内容で置換される。
【００６０】
また、リードポインタｒｐが、コマンドヒストリーＦＩＦＯ部１０内の置換されるエントリの１つを指している（ｒｐ≦ｎまたはｗｐ≦ｒｐ）ときは、処理部２はアドレス解放処理の際に、当該リードポインタｒｐをインクリメントする。
【００６１】
次に、上述の第２の状態（ｎ＜ｗｐ）のときのアドレス解放の具体例について、図１０を参照して説明する。  
まず、図１０に示すように、ライトポインタｗｐが「１２６」、リードポインタｒｐが「１２５」であるものとする。また、フリーアドレス設定部１３に設定されている次フリーアドレス「ｕ」が「２９」であり、この次フリーアドレス「ｕ」と等しいアドレス「２９」が、コマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[19]（ｎ＝１９）のアドレス部に格納されているものとする。このような例では、コマンドヒストリーＦＩＦＯ部１０内の置換されるエントリ「ｉ」の範囲は、図１０において矩形１０１ａで示されるｉ≦１９（０≦ｉ≦１９）と、矩形１０１ｂで示される１２６≦ｉ（１２６≦ｉ≦１２７）である。
【００６２】
この場合、コマンドヒストリーＦＩＦＯ部１０は、図１０において矢印１０２ａで示すように、矩形１０１ａで示される範囲に対しては、
新しいｃｆｉｆｏ[0]のアドレス部＝旧ｃｆｉｆｏ[127]内のアドレス＝７１
新しいｃｆｉｆｏ[0]内のＲフラグ＝旧ｃｆｉｆｏ[127]内のＲフラグ＝０
新しいｃｆｉｆｏ[0]内のＵフラグ＝旧ｃｆｉｆｏ[127]内のＵフラグ＝０
新しいｃｆｉｆｏ[1]のアドレス部＝旧ｃｆｉｆｏ[0]内のアドレス＝１５
新しいｃｆｉｆｏ[1]内のＲフラグ＝旧ｃｆｉｆｏ[0]内のＲフラグ＝０
新しいｃｆｉｆｏ[1]内のＵフラグ＝旧ｃｆｉｆｏ[0]内のＵフラグ＝０
…
新しいｃｆｉｆｏ[19]のアドレス部＝旧ｃｆｉｆｏ[18]内のアドレス＝７４
新しいｃｆｉｆｏ[19]内のＲフラグ＝旧ｃｆｉｆｏ[18]内のＲフラグ＝０
新しいｃｆｉｆｏ[19]内のＵフラグ＝旧ｃｆｉｆｏ[18]内のＵフラグ＝１
のように置換する。
【００６３】
また、コマンドヒストリーＦＩＦＯ部１０は、図１０において矢印１０２ｂで示すように、矩形１０１ｂで示される範囲に対しては、
新しいｃｆｉｆｏ[126]のアドレス部＝次フリーアドレス「ｕ」＝２９
新しいｃｆｉｆｏ[126]内のＲフラグ＝０
新しいｃｆｉｆｏ[126]内のＵフラグ＝０
新しいｃｆｉｆｏ[127]のアドレス部＝旧ｃｆｉｆｏ[126]内のアドレス＝９９
新しいｃｆｉｆｏ[127]内のＲフラグ＝旧ｃｆｉｆｏ[126]内のＲフラグ＝０
新しいｃｆｉｆｏ[127]内のＵフラグ＝旧ｃｆｉｆｏ[126]内のＵフラグ＝０
のように置換する。
【００６４】
コマンドヒストリーＦＩＦＯ部１０内の、２０≦ｉ≦１２５の範囲のｃｆｉｆｏ[i]については、何も変わらない。  
また、図１０の例では、リードポインタｒｐが「１２５」であり、コマンドヒストリーＦＩＦＯ部１０内の置換されるエントリを指していない。このため、リードポインタｒｐはインクリメントされない。
【００６５】
このように本実施形態によれば、使用中（Ｕフラグ＝１）であったコマンドが格納されていた、次フリーアドレス「２９」によって指定されるコマンドテーブル２１内のエントリＥＮＴ(29)と、当該エントリＥＮＴ(29)を指定するアドレス「２９」と、当該アドレス「２９」が格納されているコマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[19]（ｎ＝１９）とが解放される。これにより、ホストから次のコマンドが受信された場合、当該次のコマンドは、コマンドテーブル２１内の解放されたエントリＥＮＴ(29)に格納される。
【００６６】
次に、図１に示される検出回路１４の構成について説明する。  
図１１は、検出回路１４の構成を示すブロック図である。  
検出回路１４は、フリーアドレス設定部１３に設定されている次フリーアドレスと等しいアドレスが格納されている、コマンドヒストリーＦＩＦＯ部１０のエントリ（ｃｆｉｆｏ[n]）のアドレス「ｎ」を検出する。検出回路１４は、１２８個（ｎ＝１２８）の比較器ＣＭＰ[0]〜ＣＭＰ[127]と、変換器１４０とを備えている。
【００６７】
比較器ＣＭＰ[i]（ｉ＝０，１，…１２７）は、フリーアドレス設定部１３に設定されている次フリーアドレスとコマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[i]のアドレス部に格納されているアドレス（つまりｃｆｉｆｏ[i]内のアドレス）とを比較し、１ビットの比較結果を出力する。この比較結果は、“１”のとき次フリーアドレスとｃｆｉｆｏ[i]内のアドレスとが等しいことを示し、“０”のとき当該両アドレスが異なることを示す。
【００６８】
比較器ＣＭＰ[0]〜ＣＭＰ[127]のうち、比較器ＣＭＰ[n]（ｎは０〜１２７のいずれか）が比較結果として“１”を出力したものとする。この場合、変換器１４０は、比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果の組み合わせを、比較器ＣＭＰ[n]に対応するｃｆｉｆｏ[n]のアドレス「ｎ」に変換する。つまり変換器１４０は、比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果の組み合わせのビット列を、当該ビット列における比較結果が“１”の位置に応じて、以下のように変換する。
【００６９】
変換器１４０は、
比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果が
「１２８’ｂ０００００００００００……００００００１」のとき、ｎ＝０
比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果が
「１２８’ｂ０００００００００００……０００００１０」のとき、ｎ＝１
比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果が
「１２８’ｂ０００００００００００……００００１００」のとき、ｎ＝２
…
比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果が
「１２８’ｂ０１０００００００００……０００００００」のとき、ｎ＝１２６
比較器ＣＭＰ[0]〜ＣＭＰ[127]の比較結果が
「１２８’ｂ１００００００００００……０００００００」のとき、ｎ＝１２７
にそれぞれ変換する。なお、「１２８’ｂ」は、後続のビット列が１２８ビットであることを示す。
【００７０】
上述したように、図１１に示す検出回路１４には、次フリーアドレス及びｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]内のアドレスが入力される。しかし、図１では、検出回路１４の入力のうち、ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]内のアドレスは、簡略化のために省略されている。
【００７１】
次に、図１に示されるコマンドヒストリーＦＩＦＯ部１０のアドレスＦＩＦＯ部１１の構成について説明する。前述したようにアドレスＦＩＦＯ部１１は、主として、Ｎ個のｍビットのフリップフロップから構成される。
【００７２】
図１２は、アドレスＦＩＦＯ部１１の０番目のエントリを除くｉ番目のエントリ（ｉ＝１，２，…Ｎ−１）の構成（Ｎ＝１２８）、つまりコマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[i]のアドレス部ＡＤＲ[i]の構成を示すブロック図である。
【００７３】
アドレス部ＡＤＲ[i]は、セレクタ（第１のセレクタ）ＡＳＥＬ１[i]、セレクタ（第２のセレクタ）ＡＳＥＬ２[i]及びｍビット（ｍ＝７）のフリップフロップＡＦＦ[i]を備えている。  
セレクタＡＳＥＬ１[i]は、アドレス部ＡＤＲ[i-1]に含まれているフリップフロップＡＦＦ[i-1]の出力（ｃｆｉｆｏ[i-1]内のアドレス）またはフリーアドレス設定部１３に設定されている次フリーアドレス（ＮＥＸＴ  ＦＲＥＥ  ＡＤＤＲＥＳＳ）のいずれか一方を選択信号ＡＳ１[i]に応じて選択する。選択信号ＡＳ１[i]は、ライトポインタｗｐがアドレス（エントリ）「ｉ」を指している場合（ｉ＝ｗｐ）“１”となり、それ以外の場合（ｉ≠ｗｐ）は“０”となる。セレクタＡＳＥＬ１[i]は、選択信号ＡＳ１[i]が“１”の場合、次フリーアドレスを選択し、選択信号ＡＳ１[i]が“０”の場合、ｃｆｉｆｏ[i-1]内のアドレスを選択する。
【００７４】
セレクタＡＳＥＬ２[i]は、フリップフロップＡＦＦ[i]の出力（ｃｆｉｆｏ[i]内のアドレス）またはセレクタＡＳＥＬ１[i]によって選択されたアドレスのいずれか一方を選択信号ＡＳ２[i]に応じて選択する。選択信号ＡＳ２[i]は、「ｉ」がｃｆｉｆｏ[i]（より詳細には、ｃｆｉｆｏ[i]のアドレス部及びフラグ部）を置換する条件に合致した場合に“１”となり、それ以外は“０”となる。セレクタＡＳＥＬ２[i]は、選択信号ＡＳ２[i]が“１”の場合、セレクタＡＳＥＬ１[i]によって選択されたアドレスを選択し、選択信号ＡＳ２[i]が“０”の場合、ｃｆｉｆｏ[i]内のアドレスを選択する。選択信号ＡＳ２[i]には、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致しているかを示す、後述する条件合致信号ＣＳ[i]が用いられる。
【００７５】
フリップフロップＡＦＦ[i]はｃｆｉｆｏ[i]のアドレス部の主要部を構成している。フリップフロップＡＦＦ[i]は、セレクタＡＳＥＬ２[i]によって選択されたアドレスを、クロック信号ＣＬＫに応じて、ｃｆｉｆｏ[i]のアドレス部に格納されるアドレスとして保持する。セレクタＡＳＥＬ１[i]及びＡＳＥＬ２[i]は、ｃｆｉｆｏ[i]のアドレス部（フリップフロップＡＦＦ[i]）に格納されているアドレスを置換する置換回路ＡＳＵＢ[i]を構成する。
【００７６】
図１３は、「ｉ」が「０」の場合のアドレスＦＩＦＯ部１１のエントリｉの構成、つまりコマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[i]のアドレス部ＡＤＲ[i]の構成を示すブロック図である。
【００７７】
図１３に示すアドレス部ＡＤＲ[i]（ｉ＝０）の構成は、図１２に示すアドレス部ＡＤＲ[i]（ｉ＝１，２，…Ｎ−１）の構成と同様である。但し、図１３に示すアドレス部ＡＤＲ[i]（ｉ＝０）では、セレクタＡＳＥＬ１[i]の一方の入力に、ｃｆｉｆｏ[i-1]内のアドレスではなくて、ｃｆｉｆｏ[N-1]内のアドレス、つまりアドレス部ＡＤＲ[N-1]に含まれているフリップフロップＡＦＦ[N-1]の出力が用いられる。
【００７８】
上述したアドレスＦＩＦＯ部１１の構成から明らかなように、ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[N-1]（Ｎ＝１２８）のアドレス部ＡＤＲ[0]〜ＡＤＲ[N-1]は、リング状に接続されている。このため、アドレス部ＡＤＲ[i]の前段は、ｉ≠０の場合はアドレス部ＡＤＲ[i-1]となり、ｉ＝０の場合はアドレス部ＡＤＲ[N-1]となる。
【００７９】
上述のアドレス部ＡＤＲ[i]（ｉ＝０，１，…Ｎ−１）では、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致していない場合には、フリップフロップＡＦＦ[i]の入力として、当該フリップフロップＡＦＦ[i]の出力が選択される。この場合、フリップフロップＡＦＦ[i]の値、つまりｃｆｉｆｏ[i]のアドレス部の値は保持される。
【００８０】
アドレス解放処理によって、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致すると、ｉ＝ｗｐの場合は、フリップフロップＡＦＦ[i]の入力として、フリーアドレス設定部１３に設定されている次フリーアドレスが選択される。この場合、フリップフロップＡＦＦ[i]の値、つまりｃｆｉｆｏ[i]のアドレス部の値は、次フリーアドレスに置換される。
【００８１】
一方、アドレス解放処理によって、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致しても、ｉ≠ｗｐで、ｉ≠０の場合は、フリップフロップＡＦＦ[i]の入力として、アドレス部ＡＤＲ[i]の前段のアドレス部ＡＤＲ[i-1]内のフリップフロップＡＦＦ[i-1]の値、つまりｃｆｉｆｏ[i-1]のアドレス部に格納されているアドレスが選択される。この場合、フリップフロップＡＦＦ[i]の値、つまりｃｆｉｆｏ[i]のアドレス部の値は、ｃｆｉｆｏ[i-1]のアドレス部に格納されているアドレスに置換される。次に、ｉ≠ｗｐで、ｉ＝０の場合は、フリップフロップＡＦＦ[i]の入力として、アドレス部ＡＤＲ[i]（アドレス部ＡＤＲ[0]）の前段のアドレス部ＡＤＲ[N-1]内のフリップフロップＡＦＦ[N-1]の値、つまりｃｆｉｆｏ[N-1]のアドレス部に格納されているアドレスが選択される。この場合、フリップフロップＡＦＦ[i]の値、つまりｃｆｉｆｏ[i]のアドレス部の値は、ｃｆｉｆｏ[N-1]のアドレス部に格納されているアドレスに置換される。
【００８２】
次に、図１に示されるコマンドヒストリーＦＩＦＯ部１０のフラグＦＩＦＯ部１２の構成について説明する。前述したようにフラグＦＩＦＯ部１２は、主として、Ｎ個（Ｎ＝１２８）のフリップフロップ組から構成され、Ｎ個のフリップフロップ組の各々はｋ個（ｋ＝２）のフラグを保持するために、ｋ個の１ビットのフリップフロップから構成される。つまりフラグＦＩＦＯ部１２は、１種類のフラグにつき、主として、Ｎ個の１ビットのフリップフロップから構成される。
【００８３】
図１４は、フラグＦＩＦＯ部１２の０番目のエントリを除くｉ番目のエントリ（ｉ＝１，２，…Ｎ−１）の構成（Ｎ＝１２８）、つまりコマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[i]のフラグ部ＦＬＧ[i]の構成を示すブロック図である。
【００８４】
フラグ部ＦＬＧ[i]は、セレクタＦＳＥＬ１[i]、セレクタＦＳＥＬ２[i]及びフリップフロップＦＦＦ[i]を備えている。  
セレクタＦＳＥＬ１[i]は、フラグ部ＦＬＧ[i-1]に含まれているフリップフロップＦＦＦ[i-1]の出力（ｃｆｉｆｏ[i-1]のフラグ部に保持されているフラグ、つまりｃｆｉｆｏ[i-1]内のフラグ）またはフラグの初期値“０”のいずれか一方を選択信号ＦＳ１[i]に応じて選択する。選択信号ＦＳ１[i]は、ライトポインタｗｐがアドレス（エントリ）「ｉ」を指している場合（ｉ＝ｗｐ）“１”となり、それ以外の場合（ｉ≠ｗｐ）は“０”となる。選択信号ＦＳ１[i]は、選択信号ＡＳ１[i]に一致する。セレクタＦＳＥＬ１[i]は、選択信号ＦＳ１[i]が“１”の場合、フラグの初期値“０”を選択し、選択信号ＦＳ１[i]が“０”の場合、ｃｆｉｆｏ[i-1]内のフラグを選択する。
【００８５】
セレクタＦＳＥＬ２[i]は、フリップフロップＦＦＦ[i]の出力（ｃｆｉｆｏ[i]内のフラグ）またはセレクタＦＳＥＬ１[i]によって選択されたフラグのいずれか一方を選択信号ＦＳ２[i]に応じて選択する。選択信号ＦＳ２[i]は、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致する場合に“１”となり、それ以外は“０”となる。セレクタＦＳＥＬ２[i]は、選択信号ＦＳ２[i]が“１”の場合、セレクタＦＳＥＬ１[i]によって選択されたフラグを選択し、選択信号ＦＳ２[i]が“０”の場合、ｃｆｉｆｏ[i]内のフラグを選択する。選択信号ＦＳ２[i]には、選択信号ＡＳ２[i]と同様に、条件合致信号ＣＳ[i]が用いられる。
【００８６】
フリップフロップＦＦＦ[i]は、ｃｆｉｆｏ[i]のフラグ部の主要部を構成している。フリップフロップＦＦＦ[i]は、セレクタＦＳＥＬ２[i]によって選択されたフラグを、クロック信号ＣＬＫに応じて、ｃｆｉｆｏ[i]のフラグ部に格納されるフラグとして保持する。セレクタＦＳＥＬ１[i]及びＦＳＥＬ２[i]は、ｃｆｉｆｏ[i]のフラグ部（フリップフロップＦＦＦ[i]）に格納されているフラグを置換する置換回路ＦＳＵＢ[i]を構成する。
【００８７】
図１５は、「ｉ」が「０」の場合のフラグＦＩＦＯ部１２のエントリｉの構成、つまりコマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[i]のフラグ部ＦＬＧ[i]の構成を示す。
【００８８】
図１５に示すフラグ部ＦＬＧ[i]（ｉ＝０）の構成は、図１４に示すフラグ部ＦＬＧ[i]（ｉ＝１，２，…Ｎ−１）の構成と同様である。但し、図１５に示すフラグ部ＦＬＧ[i]（ｉ＝０）では、セレクタＦＳＥＬ１[i]の一方の入力に、ｃｆｉｆｏ[i-1]内のフラグではなくて、ｃｆｉｆｏ[N-1]内のフラグ、つまりフラグ部ＦＬＧ[N-1]に含まれているフリップフロップＦＦＦ[N-1]の出力が用いられる。
【００８９】
上述したフラグＦＩＦＯ部１２の構成から明らかなように、ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[N-1]（Ｎ＝１２８）のフラグ部ＦＬＧ[0]〜ＦＬＧ[N-1]は、リング状に接続されている。このため、フラグ部ＦＬＧ[i]の前段は、ｉ≠０の場合はフラグ部ＦＬＧ[i-1]となり、ｉ＝０の場合はフラグ部ＦＬＧ[N-1]となる。
【００９０】
上述のフラグ部ＦＬＧ[i]（ｉ＝０，１，…Ｎ−１）では、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致していない場合には、フリップフロップＦＦＦ[i]の入力として、当該フリップフロップＦＦＦ[i]の出力が選択される。この場合、フリップフロップＦＦＦ[i]の値、つまりｃｆｉｆｏ[i]のフラグ部の値は保持される。
【００９１】
アドレス解放処理によって、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致すると、ｉ＝ｗｐの場合は、フリップフロップＦＦＦ[i]の入力として、フラグの初期値“０”が選択される。この場合、フリップフロップＦＦＦ[i]の値、つまりｃｆｉｆｏ[i]のフラグ部の値は、初期値“０”となる。
【００９２】
一方、アドレス解放処理によって、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致しても、ｉ≠ｗｐで、ｉ≠０の場合は、フリップフロップＦＦＦ[i]の入力として、フラグ部ＦＬＧ[i]の前段のフラグ部ＦＬＧ[i-1]内のフリップフロップＦＦＦ[i]の値、つまりｃｆｉｆｏ[i-1]のフラグ部に格納されているフラグが選択される。この場合、フリップフロップＦＦＦ[i]の値、つまりｃｆｉｆｏ[i]のフラグ部の値は、ｃｆｉｆｏ[i-1]のフラグ部に格納されているフラグに置換される。次に、ｉ≠ｗｐで、ｉ＝０の場合は、フリップフロップＦＦＦ[i]の入力として、フラグ部ＦＬＧ[i]（フラグ部ＦＬＧ[0]）の前段のフラグ部ＦＬＧ[N-1]内のフリップフロップＦＦＦ[N-1]の値、つまりｃｆｉｆｏ[N-1]のフラグ部に格納されているフラグが選択される。この場合、フリップフロップＦＦＦ[i]の値、つまりｃｆｉｆｏ[i]のフラグ部の値は、ｃｆｉｆｏ[N-1]のフラグ部に格納されているフラグに置換される。  
なお、フラグの初期値は必ずしも“０”でなくてもよく、“１”であっても構わない。
【００９３】
図１６は、本実施形態におけるアドレス解放時に、アドレスＦＩＦＯ部１１のｉ番目のエントリ（アドレス部ＡＤＲ[i]）、つまりｃｆｉｆｏ[i]のアドレス部において、アドレスＡがアドレスＢに置換される場合のタイミングチャートである。
【００９４】
まず、ｃｆｉｆｏ[i]のアドレス部（ＡＤＲ[i]）にアドレスＡが格納されているものとする。この状態で、アドレス解放処理によって、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致すると、ｃｆｉｆｏ[i]のアドレス部に格納されているアドレスＡがアドレスＢに置換される。ここでアドレスＢは、上述したように、次フリーアドレス（ｉ＝ｗｐの場合）、ｃｆｉｆｏ[i-1]内のアドレス（ｉ≠ｗｐで、ｉ≠０の場合）、またはｃｆｉｆｏ[N-1]内のアドレス（ｉ≠ｗｐで、ｉ＝０の場合）である。
【００９５】
図１６のタイミングチャートからも明らかなように、本実施形態によれば、アドレス解放処理（アドレスの置換）は、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致する場合に、後述する置換トリガ信号ＴＲＧが出力されるクロック信号ＣＬＫの１サイクルの期間、選択信号ＡＳ２[i]（及びＦＳ２[i]）に用いられる条件合致信号ＣＳ[i]が“１”に切り替えられるだけで、つまりフリップフロップＡＦＦ[i]の入力を切り替えるだけで、当該クロック信号ＣＬＫの１サイクルで完了する。  
フラグＦＩＦＯ部１２内のフラグ部ＦＬＧ[i]、つまりｃｆｉｆｏ[i]のフラグ部においても、図１６に示すタイミングチャートと同様のタイミングでフラグが置換される。
【００９６】
つまり本実施形態においては、不要となったコマンドが格納されているコマンドテーブル２１内のエントリＥＮＴ(u)、当該エントリＥＮＴ(u)のアドレス「ｕ」、当該エントリＥＮＴ(u)におけるコマンドの格納状態を示すフラグを格納している、コマンドヒストリーＦＩＦＯ部１０内のｃｆｉｆｏ[n]を、コンパクション／カーベージコレクションを用いずに、しかも高速で解放できる。また本実施形態においては、コマンド群の受信（格納）順にアドレスＦＩＦＯ部１１から対応するアドレスが読み出せることを保証するために置換が必要となる、コマンドヒストリーＦＩＦＯ部１０内の置換対象範囲内のエントリ群を、クロック信号ＣＬＫの１サイクルで置換することができる。
【００９７】
図１７は、処理部２によるＣＦＩＦＯトップ部へのリードアクセスに応じてリードポインタｒｐの指し示すコマンドヒストリーＦＩＦＯ部１０のｒｐ番目のエントリ（ｃｆｉｆｏ[rp]）のアドレス部及びフラグ部を取り出す選択回路１７０の構成を示すブロック図である。
【００９８】
図１７に示すように、選択回路１７０は、マルチプレクサ１７１を備えている。マルチプレクサ１７１は、ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]（Ｎ＝１２８の場合）の各々のアドレス部及びフラグ部を入力する。マルチプレクサ１７１は、ｃｆｉｆｏ[0]〜ｃｆｉｆｏ[127]（Ｎ＝１２８の場合）の各々のアドレス部及びフラグ部から、リードポインタｒｐの指し示すｃｆｉｆｏ[rp]のアドレス部及びフラグ部の値を選択する。選択されたｃｆｉｆｏ[rp]のアドレス部及びフラグ部の値は、処理部２に出力される。
【００９９】
次に、図１に示される置換制御回路１５の構成について説明する。置換制御回路１５は、コマンドヒストリーＦＩＦＯ部１０のｃｆｉｆｏ[i]（ｉ＝０，１，…１２７）毎に、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致することを検出する。置換制御回路１５は、この検出結果に応じて、ｃｆｉｆｏ[i]を対象とする置換を制御する。
【０１００】
図１８は、置換制御回路１５に含まれている、選択制御回路ＳＣＮＴ[i]の構成を示すブロック図である。  
選択制御回路ＳＣＮＴ[i]は、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致することを検出することにより、条件合致信号ＣＳ[i]を出力する。条件合致信号ＣＳ[i]は、前述したように選択信号ＡＳ２[i]及びＦＳ２[i]として用いられる。つまり選択制御回路ＳＣＮＴ[i]は、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致することを検出することにより、ｃｆｉｆｏ[i]のアドレス部ＡＤＲ[i]のセレクタＡＳＥＬ２[i]及びｃｆｉｆｏ[i]のフラグ部ＦＬＧ[i]のセレクタＦＳＥＬ２[i]を制御する。
【０１０１】
「ｉ」がｃｆｉｆｏ[i]を置換する条件は、「ｗｐ」と「ｎ」との大小関係によって、第１の条件と第２の条件とに分けられる。ｗｐ≦ｎ（第１の状態）のとき、「ｉ」がｃｆｉｆｏ[i]を置換する条件として第１の条件が用いられる。第１の条件は、「ｉ」がｗｐ≦ｉ≦ｎであることである。ｎ＜ｗｐ（第２の状態）のとき、「ｉ」がｃｆｉｆｏ[i]を置換する条件として第２の条件が用いられる。第２の条件は、「ｉ」がｉ≦ｎ、またはｗｐ≦ｉであることである。
【０１０２】
選択制御回路ＳＣＮＴ[i]は、検出器（第１の検出器）ＤＴＣ１[i]（＃１）と、検出器（第２の検出器）ＤＴＣ２[i]（＃２）と、セレクタ（第３のセレクタ）ＳＥＬ[i]と、アンドゲートＡＮＤ[i]とを備えている。
【０１０３】
検出器ＤＴＣ１[i]は、「ｉ」が、ｗｐ≦ｉ≦ｎであること、つまり第１の条件に合致することを検出する。検出器ＤＴＣ１[i]は、ｗｐ≦ｉ≦ｎであれば“１”の信号を、そうでなければ“０”の信号を出力する。検出器ＤＴＣ２[i]は、「ｉ」が、ｉ≦ｎ、またはｗｐ≦ｉであること、つまり第２の条件に合致することを検出する。検出器ＤＴＣ２[i]は、ｉ≦ｎ、またはｗｐ≦ｉであれば“１”の信号を、そうでなければ“０”の信号を出力する。
【０１０４】
セレクタＳＥＬ[i]は、検出器ＤＴＣ１[i]の出力信号または検出器ＤＴＣ２[i]の出力信号のいずれか一方を、選択信号Ｓ[i]に応じて選択する。選択信号Ｓ[i]は、ｗｐ≦ｎ（第１の状態）の場合に“１”となり、ｎ＜ｗｐ（第２の状態）の場合は“０”となる。セレクタＳＥＬ[i]は、選択信号Ｓ[i]が“１”の場合（ｗｐ≦ｎ）、検出器ＤＴＣ１[i]の出力信号を選択し、選択信号Ｓ[i]が“０”の場合（ｎ＜ｗｐ）、検出器ＤＴＣ２[i]の出力信号を選択する。
【０１０５】
アンドゲートＡＮＤ[i]は、処理部２からの置換トリガ信号ＴＲＧが“１”の期間、セレクタＳＥＬ[i]の出力信号を、「ｉ」がｃｆｉｆｏ[i]を置換する条件に合致しているかを示す条件合致信号ＣＳ[i]として出力する。条件合致信号ＣＳ[i]は、選択信号ＡＳ２[i]及びＦＳ２[i]として用いられる。
【０１０６】
置換制御回路１５は、１２８個の選択制御回路ＳＣＮＴ[i]（Ｎ＝１２８の場合）を備えている。
【０１０７】
以上説明した少なくとも１つの実施形態によれば、不要となったコマンドが格納されている領域をコンパクション或いはガーベージコレクションを用いずに解放することができる。
【０１０８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１０９】
１…コマンド管理装置、１０…コマンドヒストリーＦＩＦＯ部、１１…アドレスＦＩＦＯ部、１２…フラグＦＩＦＯ部、１３…フリーアドレス設定部、１４…検出回路、１５…置換制御回路、２０…コマンドバッファ、２１…コマンドテーブル、１４０…変換器、１７０…選択回路、１７１…マルチプレクサ、ＣＭＰ[0]〜ＣＭＰ[127]…比較器、ＡＦＦ[i]，ＡＦＦ[i-1]，ＡＦＦ[N-1]，ＦＦＦ[i]，ＦＦＦ[i-1]，ＦＦＦ[N-1]…フリップフロップ、ＡＳＥＬ１[i]，ＡＳＥＬ２[i]，ＦＳＥＬ１[i]，ＦＳＥＬ２[i]…セレクタ、ＡＳＵＢ[i]，ＡＳＵＢ[i]…置換回路、ＳＣＮＴ[i]…選択制御回路、ＤＴＣ１[i]，ＤＴＣ２[i]…検出器、ＳＥＬ[i]…セレクタ、ＡＮＤ[i]…アンドゲート。
【図１】
2012027718.tif 000003
【図２】
2012027718.tif 000004
【図３】
2012027718.tif 000005
【図４】
2012027718.tif 000006
【図５】
2012027718.tif 000007
【図６】
2012027718.tif 000008
【図７】
2012027718.tif 000009
【図８】
2012027718.tif 000010
【図９】
2012027718.tif 000011
【図１０】
2012027718.tif 000012
【図１１】
2012027718.tif 000013
【図１２】
2012027718.tif 000014
【図１３】
2012027718.tif 000015
【図１４】
2012027718.tif 000016
【図１５】
2012027718.tif 000017
【図１６】
2012027718.tif 000018
【図１７】
2012027718.tif 000019
【図１８】
2012027718.tif 000020
【手続補正書】
【提出日】平成23年8月3日(2011.8.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ホストから受信されたコマンドの群を格納するコマンドバッファと、
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するエントリの群を備えた先入れ先出し手段と、
前記コマンドバッファ内の１のコマンドが不要となった場合、前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段のエントリのエントリアドレス「ｗｐ」と、前記不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスであるフリーアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレス「ｎ」との大小関係で決まるエントリアドレスの範囲について、前記範囲内のエントリアドレスが「ｉ」のエントリに格納されている第１のアドレスを、前記範囲内のエントリにおける前段のエントリに格納されている第２のアドレスに置換する置換手段と
を具備するコマンド管理装置。
【請求項２】
前記範囲は、前記「ｗｐ」を１の境界とし、
前記置換手段は、前記「ｉ」が前記「ｗｐ」に等しくない場合、前記第１のアドレスを前記第２のアドレスに置換する
請求項１記載のコマンド管理装置。
【請求項３】
前記置換手段は、前記「ｉ」が前記「ｗｐ」に等しい場合、前記第１のアドレスを前記フリーアドレスに置換する
請求項２記載のコマンド管理装置。
【請求項４】
前記「ｗｐ」が前記「ｎ」以下である第１の状態において、前記範囲は、前記「ｗｐ」から前記「ｎ」までであり、
前記「ｗｐ」が前記「ｎ」より大きい第２の状態において、前記範囲は、第１の範囲及び第２の範囲を含み、
前記第１の範囲は、前記エントリの群の先頭エントリのエントリアドレスから前記「ｎ」までであり、
前記第２の範囲は、前記「ｗｐ」から前記エントリの群の最終エントリのエントリアドレスまでであり、
前記先頭アドレスと前記最終エントリとはリング状に接続されている
請求項２記載のコマンド管理装置。
【請求項５】
前記先入れ先出し手段のエントリの群の各々は、前記アドレスを格納するのに用いられ、所定のクロック信号で動作するフリップフロップを備えている請求項２記載のコマンド管理装置。
【請求項６】
前記置換手段は、前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、次に取り出されるべきコマンドが格納されている前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段のエントリのエントリアドレス「ｒｐ」が前記範囲に含まれている場合、前記エントリアドレス「ｒｐ」を前記範囲内の次段のエントリを指し示すように置換する
請求項１記載のコマンド管理装置。
【請求項７】
前記フリーアドレスを、前記先入れ先出し手段のエントリの群のそれぞれに格納されているアドレスと比較することにより、前記エントリアドレス「ｎ」を検出する検出手段を更に具備する請求項１記載のコマンド管理装置。
【請求項８】
前記先入れ先出し手段の前記エントリの群には、前記コマンドバッファの異なる領域のアドレスが初期設定される
請求項１記載のコマンド管理装置。
【請求項９】
ホストから受信されたコマンドの群を管理するコマンド管理装置と、
記憶部と、
前記記憶部にアクセスする処理手段とを具備し、
前記コマンド管理装置は、
ホストから受信されたコマンドの群を格納するコマンドバッファと、
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するエントリの群を備えた先入れ先出し手段と、
前記コマンドバッファ内の１のコマンドが不要となった場合、前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段のエントリのエントリアドレス「ｗｐ」と、前記不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスであるフリーアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレス「ｎ」との大小関係で決まるエントリアドレスの範囲について、前記範囲内のエントリアドレスが「ｉ」のエントリに格納されている第１のアドレスを、前記範囲内のエントリにおける前段のエントリに格納されている第２のアドレスに置換する置換手段とを具備し、
前記処理手段は、前記先入れ先出し手段の前記エントリの群のそれぞれに格納されているアドレスをシーケンシャルに読み出して、その読み出されたアドレスに基づいて前記コマンドバッファにアクセスすることにより、当該読み出されたアドレスで指定される前記コマンドバッファ内の領域からコマンドを取り出し、当該取り出されたコマンドに応じて前記記憶部にアクセスする
記憶装置。
【請求項１０】
前記範囲は、前記「ｗｐ」を１の境界とし、
前記置換手段は、前記「ｉ」が前記「ｗｐ」に等しくない場合、前記第１のアドレスを前記第２のアドレスに置換する
請求項９記載のコマンド管理装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
実施形態によれば、コマンド管理装置は、コマンドバッファと、先入れ先出し手段と、置換手段とを具備する。前記コマンドバッファは、ホストから受信されたコマンドの群を格納する。前記先入れ先出し手段は、前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するエントリの群を備えている。前記置換手段は、前記コマンドバッファ内の１のコマンドが不要となった場合、前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段のエントリのエントリアドレス「ｗｐ」と、前記不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスであるフリーアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレス「ｎ」との大小関係で決まるエントリアドレスの範囲について、前記範囲内のエントリアドレスが「ｉ」のエントリに格納されている第１のアドレスを、前記範囲内のエントリにおける前段のエントリに格納されている第２のアドレスに置換する。
【手続補正書】
【提出日】平成23年10月24日(2011.10.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ホストから受信されたコマンドの群を格納するコマンドバッファと、
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するアドレス部を含むエントリの群を備えた先入れ先出し手段と、
不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスをフリーアドレスとして保持するフリーアドレス設定手段と、
前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段の前記アドレス部のエントリアドレス「ｗｐ」を指し示すライトポインタとを具備し、
前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記アドレス部はリング状に接続されており、当該アドレス部は、当該アドレス部に格納されている第１のアドレスを、前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する置換手段を含み、
前記先入れ先出し手段の前記エントリ群のそれぞれの前記アドレス部には、前記コマンドバッファの異なる領域のアドレスが初期設定され、
前記置換手段は、当該置換手段を含む前記アドレス部のエントリアドレスが「ｉ」であり、前記フリーアドレスと等しい第３のアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレスが「ｎ」であるものとすると、
前記「ｗｐ」が前記「ｎ」以下である第１の状態において、前記「ｉ」が前記「ｗｐ」以上で、前記「ｎ」以下である第１の条件に合致する第１の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換し、
前記「ｗｐ」が前記「ｎ」より大きい第２の状態において、前記「ｉ」が前記「ｎ」以下であるか、或いは前記「ｗｐ」以上である第２の条件に合致する第２の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換する
コマンド管理装置。
【請求項２】
前記先入れ先出し手段のエントリの群のそれぞれの前記アドレス部は、前記アドレスを格納するのに用いられ、所定のクロック信号で動作するフリップフロップを備えている請求項１記載のコマンド管理装置。
【請求項３】
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、次に取り出されるべきコマンドが格納されている前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段の前記アドレス部のエントリアドレス「ｒｐ」を指し示すリードポインタを更に具備し、
前記リードポインタは、前記置換手段による置換時に、当該リードポインタの指すエントリアドレス「ｒｐ」が、前記第１の状態において、前記「ｗｐ」以上で、前記「ｎ」以下であるか、または、前記第２の状態において、前記「ｎ」以下であるか、もしくは前記「ｗｐ」以上である場合、次段のエントリを指し示すように更新される
請求項１記載のコマンド管理装置。
【請求項４】
ホストから受信されたコマンドの群を管理するコマンド管理装置と、
記憶部と、
前記記憶部にアクセスする処理手段とを具備し、
前記コマンド管理装置は、
ホストから受信されたコマンドの群を格納するコマンドバッファと、
前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するアドレス部を含むエントリの群を備えた先入れ先出し手段と、
不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスをフリーアドレスとして保持するフリーアドレス設定手段と、
前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段の前記アドレス部のエントリアドレス「ｗｐ」を指し示すライトポインタとを具備し、
前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記アドレス部はリング状に接続されており、当該アドレス部は、当該アドレス部に格納されている第１のアドレスを、前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する置換手段を含み、
前記先入れ先出し手段の前記エントリ群のそれぞれの前記アドレス部には、前記コマンドバッファの異なる領域のアドレスが初期設定され、
前記置換手段は、当該置換手段を含む前記アドレス部のエントリアドレスが「ｉ」であり、前記フリーアドレスと等しい第３のアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレスが「ｎ」であるものとすると、
前記「ｗｐ」が前記「ｎ」以下である第１の状態において、前記「ｉ」が前記「ｗｐ」以上で、前記「ｎ」以下である第１の条件に合致する第１の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換し、
前記「ｗｐ」が前記「ｎ」より大きい第２の状態において、前記「ｉ」が前記「ｎ」以下であるか、或いは前記「ｗｐ」以上である第２の条件に合致する第２の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換し、
前記処理手段は、前記先入れ先出し手段の前記エントリの群のそれぞれの前記アドレス部に格納されているアドレスをシーケンシャルに読み出して、その読み出されたアドレスに基づいて前記コマンドバッファにアクセスすることにより、当該読み出されたアドレスで指定される前記コマンドバッファ内の領域からコマンドを取り出し、当該取り出されたコマンドに応じて前記記憶部にアクセスする
記憶装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００９
【補正方法】変更
【補正の内容】
【０００９】
実施形態によれば、コマンド管理装置は、コマンドバッファと、先入れ先出し手段と、フリーアドレス設定手段と、ライトポインタとを具備する。前記コマンドバッファは、ホストから受信されたコマンドの群を格納する。前記先入れ先出し手段は、前記コマンドバッファに格納されているコマンドの群を、その格納順に取り出すために、当該コマンドの群のそれぞれが格納されている前記コマンドバッファの領域のアドレスを格納するアドレス部を含むエントリの群を備えている。前記フリーアドレス設定手段は、不要となったコマンドが格納されている前記コマンドバッファの領域のアドレスをフリーアドレスとして保持する。前記ライトポインタは、前記ホストから新たに受信されたコマンドが格納されるべき前記コマンドバッファの領域のアドレスを格納している、前記先入れ先出し手段の前記アドレス部のエントリアドレス「ｗｐ」を指し示す。前記先入れ先出し手段の前記エントリの群にそれぞれ含まれている前記アドレス部はリング状に接続されており、当該アドレス部は、当該アドレス部に格納されている第１のアドレスを、前記フリーアドレス設定手段に保持されている前記フリーアドレスまたは前段のアドレス部に格納されている第２のアドレスのいずれか一方に置換する置換手段を含む。前記先入れ先出し手段の前記エントリ群のそれぞれの前記アドレス部には、前記コマンドバッファの異なる領域のアドレスが初期設定される。前記置換手段は、当該置換手段を含む前記アドレス部のエントリアドレスが「ｉ」であり、前記フリーアドレスと等しい第３のアドレスが格納されている前記先入れ先出し手段のエントリのエントリアドレスが「ｎ」であるものとすると、前記「ｗｐ」が前記「ｎ」以下である第１の状態において、前記「ｉ」が前記「ｗｐ」以上で、前記「ｎ」以下である第１の条件に合致する第１の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換し、前記「ｗｐ」が前記「ｎ」より大きい第２の状態において、前記「ｉ」が前記「ｎ」以下であるか、或いは前記「ｗｐ」以上である第２の条件に合致する第２の場合のうち、前記「ｉ」が前記「ｗｐ」に等しくない場合に、前記エントリアドレスが「ｉ」のアドレス部に格納されている前記第１のアドレスを前段のアドレス部に格納されている前記第２のアドレスに置換する。