"セクタ単位の書き込みデータを保持可能なキャッシュメモリと、ページ単位でデータ書き込みを行い、前記ページ単位の2以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第1の管理単位でデータを記憶する第1の手段、前記不揮発性半導体メモリにおいて前記第1の管理単位の2以上の自然数倍である第2の管理単位でデータを記憶する第2の手段、前記キャッシュメモリに保持されるデータを前記第1の管理単位のアドレスで管理する第3の手段、及び前記キャッシュメモリに保持されるデータを前記第2の管理単位のアドレスで管理する第4の手段を有するコントローラと、を具備し、前記キャッシュメモリは、前記第1の管理単位のアドレスでラインが決定され且つ各ラインは複数のウェイを有し、各々のエントリに前記第1の管理単位のアドレスに含まれるデータを保持可能なセットアソシアティブ方式で管理され、前記第1の手段は、前記第1の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第1の管理単位のデータの記憶位置とを関連付ける情報を含む第1の管理テーブルを備え、前記第2の手段は、前記第2の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第2の管理単位のデータの記憶位置を関連付ける情報を含む第2の管理テーブルを備え、前記第3の手段は、前記エントリに登録された前記第1の管理単位のアドレス中で前記セクタ単位の有効データが保持されている位置を示す情報及び当該第1の管理単位のアドレスが所属する前記第2の管理単位のアドレスを含む第3の管理テーブルを備え、前記第4の手段は、前記キャッシュメモリにおける前記第2の管理単位のアドレス間の登録順序を示す情報、前記キャッシュメモリにおいて前記第2の管理単位のアドレスに含まれる前記第1の管理単位のデータの個数、及び前記キャッシュメモリにおいて前記第2の管理単位のアドレス中で前記第1の管理単位の有効データが保持されている位置を含む第4の管理テーブルを備え、前記コントローラは、前記キャッシュメモリに保持されるデータが所属する前記第2の管理単位のアドレスの個数が所定の閾値を超えた場合、または、前記キャッシュメモリへのデータ書き込み処理を実行する際に前記第2の管理テーブルにおいて最後の空きウェイが使用される場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行し、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する場合に、前記第4の管理テーブルに登録された順序が最も古い前記第2の管理単位のアドレスを選択し、前記キャッシュメモリにおいて当該第2の管理単位のアドレスに含まれるデータを追い出し処理の対象とし、追い出し対象として選択した前記第2の管理単位のアドレスに含まれる前記第1の管理単位のデータの個数が前記キャッシュメモリにおいて所定の閾値未満である場合は、前記第1の管理単位のデータとして前記不揮発性半導体メモリに記憶し、前記キャッシュメモリにおいて所定の閾値以上である場合は、前記第2の管理単位のデータとして前記不揮発性半導体メモリに記憶する、ことを特徴とするメモリシステム。セクタ単位の書き込みデータを保持可能なキャッシュメモリと、ページ単位でデータ書き込みを行い、前記ページ単位の2以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第1の管理単位でデータを記憶する第1の手段及び前記第1の管理単位の2以上の自然数倍である第2の管理単位でデータを記憶する第2の手段を有するコントローラと、を具備し、前記コントローラは、前記キャッシュメモリに保持されるデータを、前記第1の管理単位のアドレスで管理する第3の手段及び前記第2の管理単位のアドレスで管理する第4の手段を有し、前記キャッシュメモリに保持されるデータが所属する前記第2の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する、ことを特徴とするメモリシステム。前記コントローラは、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行する場合に、前記第4の手段に登録された順序が最も古い前記第2の管理単位のアドレスを選択し、当該第2の管理単位のアドレスに含まれるデータを追い出し処理の対象とすることを特徴とする請求項2に記載のメモリシステム。前記第1の手段は、前記第1の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第1の管理単位のデータの記憶位置とを関連付ける情報を含む第1の管理テーブルを備えることを特徴とする請求項2に記載のメモリシステム。前記第2の手段は、前記第2の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第2の管理単位のデータの記憶位置を関連付ける情報を含む第2の管理テーブルを備えることを特徴とする請求項2に記載のメモリシステム。前記キャッシュメモリは、前記第1の管理単位のアドレスでラインが決定され且つ各ラインは複数のウェイを有し、各々のエントリに前記第1の管理単位のアドレスに含まれるデータを保持可能なセットアソシアティブ方式で管理され、前記第3の手段は、前記エントリに登録された前記第1の管理単位のアドレス中で前記セクタ単位の有効データが保持されている位置を示す情報及び当該第1の管理単位のアドレスが所属する前記第2の管理単位のアドレスを含む第3の管理テーブルを備えることを特徴とする請求項2に記載のメモリシステム。前記第4の手段は、前記キャッシュメモリにおける前記第2の管理単位のアドレス間の登録順序を示す情報、前記キャッシュメモリにおいて前記第2の管理単位のアドレスに含まれる前記第1の管理単位のデータの個数、及び前記キャッシュメモリにおいて前記第2の管理単位のアドレス中で前記第1の管理単位の有効データが保持されている位置を含む第4の管理テーブルを備えることを特徴とする請求項2に記載のメモリシステム。前記コントローラは、前記キャッシュメモリへのデータ書き込み処理を実行する際に前記第2の管理テーブルにおいて最後の空きウェイが使用される場合、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項6に記載のメモリシステム。前記コントローラは、前記第2の管理単位のアドレス毎に前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項7に記載のメモリシステム。前記コントローラは、追い出し対象として選択した前記第2の管理単位のアドレスに含まれる前記第1の管理単位のデータの個数が前記キャッシュメモリにおいて所定の閾値未満である場合は、前記第1の管理単位のデータとして前記不揮発性半導体メモリに記憶し、前記キャッシュメモリにおいて所定の閾値以上である場合は、前記第2の管理単位のデータとして前記不揮発性半導体メモリに記憶することを特徴とする請求項9に記載のメモリシステム。セクタ単位の書き込みデータを保持可能なキャッシュメモリと、ページ単位でデータ書き込みを行い、前記ページ単位の2以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第1の管理単位でデータを記憶する第1の手段及び前記第1の管理単位の2以上の自然数倍である第2の管理単位でデータを記憶する第2の手段を有するコントローラと、を具備し、前記キャッシュメモリは、前記第1の管理単位のアドレスでラインが決定され且つ各ラインは複数のウェイを有し、各々のエントリに前記第1の管理単位のアドレスに含まれるデータを保持可能なセットアソシアティブ方式で管理され、前記コントローラは、前記キャッシュメモリへのデータ書き込み処理を実行する際に最後の空きウェイが使用される場合、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とするメモリシステム。前記コントローラは、前記キャッシュメモリに保持されるデータを、前記第1の管理単位のアドレスで管理する第3の手段及び前記第2の管理単位のアドレスで管理する第4の手段を有することを特徴とする請求項11に記載のメモリシステム。前記第1の手段は、前記第1の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第1の管理単位のデータの記憶位置とを関連付ける情報を含む第1の管理テーブルを備えることを特徴とする請求項11に記載のメモリシステム。前記第2の手段は、前記第2の管理単位のアドレスと前記不揮発性半導体メモリにおける前記第2の管理単位のデータの記憶位置を関連付ける情報を含む第2の管理テーブルを備えることを特徴とする請求項11に記載のメモリシステム。前記第3の手段は、前記エントリに登録された前記第1の管理単位のアドレス中で前記セクタ単位の有効データが保持されている位置を示す情報及び当該第1の管理単位のアドレスが所属する前記第2の管理単位のアドレスを含む第3の管理テーブルを備えることを特徴とする請求項12に記載のメモリシステム。前記第4の手段は、前記キャッシュメモリにおける前記第2の管理単位のアドレス間の登録順序を示す情報、前記キャッシュメモリにおいて前記第2の管理単位のアドレスに含まれる前記第1の管理単位のデータの個数、及び前記キャッシュメモリにおいて前記第2の管理単位のアドレス中で前記第1の管理単位の有効データが保持されている位置を含む第4の管理テーブルを備えることを特徴とする請求項12に記載のメモリシステム。前記コントローラは、前記キャッシュメモリに保持されるデータが所属する前記第2の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項12に記載のメモリシステム。前記コントローラは、前記第2の管理単位のアドレス毎に前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする請求項12に記載のメモリシステム。前記コントローラは、追い出し対象として選択した前記第2の管理単位のアドレスに含まれる前記第1の管理単位のデータの個数が前記キャッシュメモリにおいて所定の閾値未満である場合は、前記第1の管理単位のデータとして前記不揮発性半導体メモリに記憶し、前記キャッシュメモリにおいて所定の閾値以上である場合は、前記第2の管理単位のデータとして前記不揮発性半導体メモリに記憶することを特徴とする請求項18に記載のメモリシステム。前記不揮発性半導体メモリは、NAND型フラッシュメモリであることを特徴とする請求項1乃至請求項19に記載のメモリシステム。本発明は、ライトキャッシュの管理テーブルのためのメモリ量を削減するとともに、ライトキャッシュの管理テーブルによる検索処理の高速化を図るメモリシステムを提供することを目的とする。本願発明の一態様によれば、セクタ単位の書き込みデータを保持可能なキャッシュメモリと、ページ単位でデータ書き込みを行い、前記ページ単位の2以上の自然数倍であるブロック単位でデータ消去を行う不揮発性半導体メモリと、前記不揮発性半導体メモリにおいて前記セクタ単位の自然数倍である第1の管理単位でデータを記憶する第1の手段及び前記第1の管理単位の2以上の自然数倍である第2の管理単位でデータを記憶する第2の手段を有するコントローラと、を具備し、前記コントローラは、前記キャッシュメモリに保持されるデータを、前記第1の管理単位のアドレスで管理する第3の手段及び前記第2の管理単位のアドレスで管理する第4の手段を有し、前記キャッシュメモリに保持されるデータが所属する前記第2の管理単位のアドレスの個数が所定の閾値を超えた場合に、前記キャッシュメモリから前記不揮発性半導体メモリへのデータ追い出し処理を実行することを特徴とする。本発明によれば、追い出し処理の判断を高速に行うことができ、書き込み処理を高速化することができ、また管理テーブル量を削減することができる。以下に添付図面を参照して、この発明にかかるメモリシステムの最良な実施の形態を詳細に説明する。実施の形態以下、本発明の実施の形態について図面を参照して説明する。なお、以下の説明において、同一の機能および構成を有する要素については、同一符号を付し、重複説明は必要な場合にのみ行う。先ず、本明細書で用いる用語について定義しておく。物理ページ:NANDメモリチップ内部において一括して書き込み/読み出しが可能な単位のこと。物理ページサイズは、例えば4kB。ただし、主データユーザデータなどに対してSSD内で付加される誤り訂正符号などの冗長ビットは含まないものとする。通常、4kB冗長ビット例えば、数10Bが同時にメモリセルに書き込まれる単位となるが、説明の便宜上、上記のように定義する。論理ページ:SSD内で設定される書き込み/読み出し単位であり、1以上の物理ページに対応付けられている。論理ページサイズは、例えば8ビットノーマルモードでは、4kB、32ビット倍速モードでは、32kB。ただし、冗長ビットは含まないものとする。物理ブロック:NANDメモリチップ内部において独立して消去可能な最小単位のことであり、複数の物理ページから構成される。物理ブロックサイズは、例えば512kB。ただし、主データに対してSSD内で付加される誤り訂正符号などの冗長ビットは含まないものとする。通常、512kB冗長ビット例えば、数10kBが同時に消去される単位となるが、説明の便宜上、上記のように定義する。論理ブロック:SSD内で設定される消去単位であり、1以上の物理ブロックに対応付けられている。論理ブロックサイズは、例えば8ビットノーマルモードでは、512kB、32ビット倍速モードでは、4MB。ただし、冗長ビットは含まないものとする。セクタ:ホストからの最小アクセス単位のこと。セクタサイズは、例えば512B。クラスタ:SSD内で小さなデータを管理する管理単位。クラスタサイズはセクタサイズ以上であり、クラスタサイズの2以上の自然数倍が論理ページサイズとなるように定められる。トラック:SSD内で大きなデータを管理する管理単位。クラスタサイズの2以上の自然数倍がトラックサイズに、かつ、トラックサイズの2以上の自然数倍が論理ブロックサイズとなるように定められる。フリーブロックFB:用途未割り当てのNAND型フラッシュメモリ上の論理ブロックのこと。用途を割り当てる際に消去してから使用する。バッドブロックBB:NAND型フラッシュメモリ上の、誤りが多いなど記憶領域として使用できない物理ブロックのこと。例えば、消去動作が正常に終了しなかった物理ブロックがバッドブロックBBとして登録される。書き込み効率:所定期間内における、ホストから書き込んだデータ量に対する、論理ブロックの消去量の統計値のこと。小さいほどNAND型フラッシュメモリの消耗度が小さい。有効クラスタ:最新のデータを保持しているクラスタ。無効クラスタ:最新ではないデータを保持しているクラスタ。有効トラック:最新のデータを保持しているトラック。無効トラック:最新ではないデータを保持しているトラック。コンパクション:管理対象内の論理ブロックから、有効クラスタや有効トラックのみを取り出して、新しい論理ブロックに書き直すこと。[第1の実施形態]図1は、SSDSolidStateDrive100の構成例を示すブロック図である。SSD100は、ATAインタフェースATAI/F2などのメモリ接続インタフェースを介してパーソナルコンピュータあるいはCPUコアなどのホスト装置1と接続され、ホスト装置1の外部メモリとして機能する。また、SSD100は、RS232CインタフェースRS232CI/Fなどの通信インタフェース3を介して、デバッグ用/製造検査用機器200との間でデータを送受信することができる。SSD100は、不揮発性半導体メモリとしてのNAND型フラッシュメモリ以下、NANDメモリと略す10と、コントローラとしてのドライブ制御回路4と、揮発性半導体メモリとしてのDRAM20と、電源回路5と、状態表示用のLED6と、ドライブ内部の温度を検出する温度センサ7と、フューズ8とを備えている。電源回路5は、ホスト装置1側の電源回路から供給される外部直流電源から複数の異なる内部直流電源電圧を生成し、これら内部直流電源電圧をSSD100内の各回路に供給する。また、電源回路5は、外部電源の立ち上がりまたは立ち下がりを検知し、パワーオンリセット信号を生成して、ドライブ制御回路4に供給する。フューズ8は、ホスト装置1側の電源回路とSSD100内部の電源回路5との間に設けられている。外部電源回路から過電流が供給された場合フューズ8が切断され、内部回路の誤動作を防止する。NANDメモリ10は、この場合、4並列動作を行う4つの並列動作要素10a~10dを有し、1つの並列動作要素は、2つのNANDメモリパッケージを有する。各NANDメモリパッケージは、積層された複数のNANDメモリチップ例えば、1チップ=2GBによって構成されている。図1の場合は、各NANDメモリパッケージは、積層された4枚のNANDメモリチップによって構成されており、NANDメモリ10は64GBの容量を有する。各NANDメモリパッケージが、積層された8枚のNANDメモリチップによって構成されている場合は、NANDメモリ10は128GBの容量を有することになる。DRAM20は、ホスト装置1とNANDメモリ10間でのデータ転送用キャッシュおよび作業領域用メモリとして機能する。また、DRAM20の代わりに、FeRAMを使用しても良い。ドライブ制御回路4は、ホスト装置1とNANDメモリ10との間でDRAM20を介してデータ転送制御を行うとともに、SSD100内の各構成要素を制御する。また、ドライブ制御回路4は、状態表示用LED6にステータス表示用信号を供給するとともに、電源回路5からのパワーオンリセット信号を受けて、リセット信号およびクロック信号を自回路内およびSSD100内の各部に供給する機能も有している。各NANDメモリチップは、データ消去の単位である物理ブロックを複数配列して構成されている。図2aは、NANDメモリチップに含まれる1個の物理ブロックの構成例を示す回路図である。各物理ブロックは、X方向に沿って順に配列されたp1個のNANDストリングを備えているpは、0以上の整数。p1個のNANDストリングにそれぞれ含まれる選択トランジスタST1は、ドレインがビット線BL0~BLpに接続され、ゲートが選択ゲート線SGDに共通接続されている。また、選択トランジスタST2は、ソースがソース線SLに共通接続され、ゲートが選択ゲート線SGSに共通接続されている。各メモリセルトランジスタMTは、半導体基板上に形成された積層ゲート構造を備えたMOSFETMetalOxideSemiconductorFieldEffectTransistorから構成される。積層ゲート構造は、半導体基板上にゲート絶縁膜を介在して形成された電荷蓄積層浮遊ゲート電極、および電荷蓄積層上にゲート間絶縁膜を介在して形成された制御ゲート電極を含んでいる。メモリセルトランジスタMTは、浮遊ゲート電極に蓄えられる電子の数に応じて閾値電圧が変化し、この閾値電圧の違いに応じてデータを記憶する。メモリセルトランジスタMTは、1ビットを記憶するように構成されていてもよいし、多値2ビット以上のデータを記憶するように構成されていてもよい。また、メモリセルトランジスタMTは、浮遊ゲート電極を有する構造に限らず、MONOSMetalOxideNitrideOxideSilicon型など、電荷蓄積層としての窒化膜界面に電子をトラップさせることでしきい値調整可能な構造であってもよい。MONOS構造のメモリセルトランジスタMTについても同様に、1ビットを記憶するように構成されていてもよいし、多値2ビット以上のデータを記憶するように構成されていてもよい。各NANDストリングにおいて、q1個のメモリセルトランジスタMTは、選択トランジスタST1のソースと選択トランジスタST2のドレインとの間に、それぞれの電流経路が直列接続されるように配置されている。すなわち、複数のメモリセルトランジスタMTは、隣接するもの同士で拡散領域ソース領域若しくはドレイン領域を共有するような形でY方向に直列接続される。そして、最もドレイン側に位置するメモリセルトランジスタMTから順に、制御ゲート電極がワード線WL0~WLqにそれぞれ接続されている。従って、ワード線WL0に接続されたメモリセルトランジスタMTのドレインは選択トランジスタST1のソースに接続され、ワード線WLqに接続されたメモリセルトランジスタMTのソースは選択トランジスタST2のドレインに接続されている。ワード線WL0~WLqは、物理ブロック内のNANDストリング間で、メモリセルトランジスタMTの制御ゲート電極を共通に接続している。つまり、ブロック内において同一行にあるメモリセルトランジスタMTの制御ゲート電極は、同一のワード線WLに接続される。この同一のワード線WLに接続されるp1個のメモリセルトランジスタMTは1ページ物理ページとして取り扱われ、この物理ページごとにデータの書き込みおよびデータの読み出しが行われる。また、ビット線BL0~BLpは、ブロック間で、選択トランジスタST1のドレインを共通に接続している。つまり、複数のブロック内において同一列にあるNANDストリングは、同一のビット線BLに接続される。図2bは、例えば、1個のメモリセルトランジスタMTに2ビットの記憶を行う4値データ記憶方式でのしきい値分布を示す模式図である。4値データ記憶方式では、上位ページデータxと下位ページデータyで定義される4値データxyの何れか1つをメモリセルトランジスタMTに保持可能である。この、4値データxyは、メモリセルトランジスタMTのしきい値電圧の順に、例えば、データ11、01、00、10が割り当てられる。データ11は、メモリセルトランジスタMTのしきい値電圧が負の消去状態である。下位ページ書き込み動作においては、データ11消去状態のメモリセルトランジスタMTに対して選択的に、下位ビットデータyの書き込みによって、データ10が書き込まれる。上位ページ書き込み前のデータ10のしきい値分布は、上位ページ書き込み後のデータ01とデータ00のしきい値分布の中間程度に位置しており、上位ページ書き込み後のしきい値分布よりブロードであってもよい。上位ページ書き込み動作においては、データ11のメモリセルと、データ10のメモリセルに対して、それぞれ選択的に上位ビットデータxの書き込みが行われて、データ01およびデータ00が書き込まれる。図3は、ドライブ制御回路4のハードウェア的な内部構成例を示すブロック図である。ドライブ制御回路4は、データアクセス用バス101、第1の回路制御用バス102、および第2の回路制御用バス103を備えている。第1の回路制御用バス102には、ドライブ制御回路4全体を制御するプロセッサ104が接続されている。第1の回路制御用バス102には、NANDメモリ10に記憶された各管理プログラムFW:ファームウエアをブートするブート用プログラムが格納されたブートROM105がROMコントローラ106を介して接続されている。また、第1の回路制御用バス102には、図1に示した電源回路5からのパワーオンリセット信号を受けて、リセット信号およびクロック信号を各部に供給するクロックコントローラ107が接続されている。第2の回路制御用バス103は、第1の回路制御用バス102に接続されている。第2の回路制御用バス103には、図1に示した温度センサ7からのデータを受けるためのI2C回路108、状態表示用LED6にステータス表示用信号を供給するパラレルIOPIO回路109、RS232CI/F3を制御するシリアルIOSIO回路110が接続されている。ATAインタフェースコントローラATAコントローラ111、第1のECCErrorCheckingandCorrection回路112、NANDコントローラ113、およびDRAMコントローラ114は、データアクセス用バス101と第1の回路制御用バス102との両方に接続されている。ATAコントローラ111は、ATAインタフェース2を介してホスト装置1との間でデータを送受信する。データアクセス用バス101には、データ作業領域作業領域およびファームウェア展開領域として使用されるSRAM115がSRAMコントローラ116を介して接続されている。NANDメモリ10に記憶されているファームウェアは起動時、ブートROM105に記憶されたブート用プログラムによってSRAM115に転送される。NANDコントローラ113は、NANDメモリ10とのインタフェース処理を行うNANDI/F117、第2のECC回路118、およびNANDメモリ10-DRAM20間のアクセス制御を行うDMA転送制御用DMAコントローラ119を備えている。第2のECC回路118は第2の訂正符号のエンコードを行い、また、第1の誤り訂正符合のエンコードおよびデコードを行う。第1のECC回路112は、第2の誤り訂正符号のデコードを行う。第1の誤り訂正符号、第2の誤り訂正符号は、例えば、ハミング符号、BCHBoseChaudhuriHocqenghem符号、RS符号、或いはLDPCLowDensityParityCheck符号等であり、第2の誤り訂正符号の訂正能力は、第1の誤り訂正符号の訂正能力よりも高いとする。図1および図3に示したように、NANDメモリ10においては、4つの並列動作要素10a~10dが各8ビットの4チャネル4chを介して、ドライブ制御回路4内部のNANDコントローラ112に並列接続されている。4つの並列動作要素10a~10dを単独動作させるか、並列動作させるか、NANDメモリチップの備える倍速モードMultiPageProgramMultiPageReadMultiBlockEraseを使用するか否か、という組み合わせにより、下記3種類のアクセスモードが提供される。18ビットノーマルモード1chだけ動作させ、8ビット単位でデータ転送を行うモードである。物理ページサイズ4kBで書き込み/読み出しが行われる。また、物理ブロックサイズ512kBで消去が行われる。1つの物理ブロックに対して1つの論理ブロックが対応付けられ、論理ブロックサイズは512kBとなる。232ビットノーマルモード4ch並列で動作させ、32ビット単位でデータ転送を行うモードである。物理ページサイズ×416kBで書き込み/読み出しが行われる。また、物理ブロックサイズ×42MBで消去が行われる。4つの物理ブロックに対して1つの論理ブロックが対応付けられ、論理ブロックサイズは2MBとなる。332ビット倍速モード4ch並列で動作させ、更に、NANDメモリチップの倍速モードを利用して書き込み/読み出しを行うモードである。物理ページサイズ×4×232kBで書き込み/読み出しが行われる。また、物理ブロックサイズ×4×24MBで消去が行われる。8つの物理ブロックに対して1つの論理ブロックが対応付けられ、論理ブロックサイズは4MBとなる。4ch並列動作する32ビットノーマルモードまたは32ビット倍速モードでは、並列動作する4または8物理ブロックが、NANDメモリ10としての消去単位となり、並列動作する4または8物理ページが、NANDメモリ10としての書き込み単位および読み出し単位となる。以下の動作では、基本的に32ビット倍速モードを使用し、例えば、1論理ブロック=4MB=2iトラック=2jページ=2kクラスタ=2lセクタとして説明するi、j、k、lは自然数、かつ、i<j<k<lの関係が成立する。32ビット倍速モードでアクセスされる論理ブロックは4MB単位であり、8個2×4chの物理ブロック1物理ブロック=512KBが対応付けられている。物理ブロック単位で管理されるバッドブロックBBが発生すると、そのバッドブロックBBは使用不可になるので、そのようなときには、論理ブロックに対応付けられた8個の物理ブロックの組み合わせが、バッドブロックBBを含まないように変更される。図4は、プロセッサ104により実現されるファームウェアの機能構成例を示すブロック図である。プロセッサ104により実現されるファームウェアの各機能は、大きく、データ管理部120、ATAコマンド処理部121、セキュリティ管理部122、ブートローダ123、初期化管理部124、デバッグサポート部125に分類される。データ管理部120は、NANDコントローラ112、第1のECC回路114を介して、NANDメモリ10-DRAM20間のデータ転送、NANDメモリ10に関する各種機能を制御する。ATAコマンド処理部121は、ATAコントローラ110、およびDRAMコントローラ113を介して、データ管理部120と協動してDRAM20-ホスト装置1間のデータ転送処理を行う。セキュリティ管理部122は、データ管理部120およびATAコマンド処理部121と協動して各種のセキュリティ情報を管理する。ブートローダ123は、パワーオン時、各管理プログラムファームウェアをNANDメモリ10からSRAM120にロードする。初期化管理部124は、ドライブ制御回路4内の各コントローラ/回路の初期化を行う。デバッグサポート部125は、外部からRS232Cインタフェースを介して供給されたデバッグ用データを処理する。主に、データ管理部120、ATAコマンド処理部121、およびセキュリティ管理部122が、SRAM114に記憶される各管理プログラムをプロセッサ104が実行することによって実現される機能部である。本実施形態では、主としてデータ管理部120が実現する機能について説明する。データ管理部120は、ATAコマンド処理部121が記憶デバイスであるNANDメモリ10やDRAM20に対して要求する機能の提供ホスト装置からのWrite要求、CacheFlush要求、Read要求等の各種コマンドへの応答と、アドレス領域とNANDメモリ10との対応関係の管理および管理情報の保護と、DRAM10およびNANDメモリ10を利用した高速で効率の良いデータ読み出し/書き込み機能の提供、NANDメモリ10の信頼性の確保などを行う。図5は、NANDメモリ10およびDRAM20内に形成された機能ブロックを示すものである。ホスト1とNANDメモリ10との間には、DRAM20上に構成されたライトキャッシュWC21およびリードキャッシュRC22が介在している。WC21はホスト装置1からのWriteデータを一時保存し、RC22はNANDメモリ10からのReadデータを一時保存する。NANDメモリ10内の論理ブロックは、書き込み時のNANDメモリ10に対する消去の量を減らすために、データ管理部120により、前段ストレージ領域FS:FrontStorage12、中段ストレージ領域ISIntermediateStorage13およびメインストレージ領域MS:MainStorage11という各管理領域に割り当てられている。FS12は、WC21からのデータを小さな単位であるクラスタ単位に管理するものであり、小データを短期間保存する。IS13は、FS12から溢れたデータを小さな単位であるクラスタ単位に管理するものであり、小データを長期間保存する。MS11は、WC21、FS12、IS13からのデータを大きな単位であるトラック単位で長期間記憶する。例えば、記憶容量は、MS>IS、FS>WCの関係となる。小さな管理単位を、NANDメモリ10の記憶領域全てに適用すると、後述する管理テーブルのサイズが肥大化し、DRAM20に収まらないので、小さな管理単位で管理するのは、最近書き込まれたばかりのデータと、NANDメモリ10への書き込み効率が悪い小さなデータのみとするようにNANDメモリ10の各ストレージを構成している。図6は、WC21からNANDメモリ10への書き込み処理WR処理に係わるより詳細な機能ブロック図を示すものである。FS12の前段には、WC21からのデータをバッファリングするFSインプットバッファFSIB12aが設けられている。また、MS11の前段には、WC21、FS12、またはIS13からのデータをバッファリングするMSインプットバッファMSIB11aが設けられている。また、MS11には、トラック前段ストレージ領域TFS11bが設けられている。TFS11bは、MSIB11aとMS11の間に介在するFIFOFirstinFirstout構造を有するバッファであり、TFS11bに記録されたデータは、MSIB11aから直接MS11に書き込まれるデータよりも更新頻度が高いデータである。MS11、MSIB11a、TFS11b、FS12、FSIB12a、およびIS13には、NANDメモリ10内の各論理ブロックの何れかが割り当てられている。つぎに、図5、図6の各構成要素の具体的な機能構成について詳述する。ホスト装置1はSSD100対し、ReadまたはWriteする際には、ATAインタフェースを介して論理アドレスとしてのLBALogicalBlockAddressingを入力する。LBAは、図7に示すように、セクタサイズ:512Bに対して0からの通し番号をつけた論理アドレスである。本実施の形態においては、図5の各構成要素であるWC21、RC22、FS12、IS13、MS11の管理単位として、LBAの下位l-k1ビット目から上位のビット列で構成される論理クラスタアドレスと、LBAの下位l-i1ビットから上位のビット列で構成される論理トラックアドレスとを定義する。1クラスタ=2l-kセクタで、1トラック=2k-iクラスタである。リードキャッシュRC22RC22について説明する。RC22は、ATAコマンド処理部121からのRead要求に対して、NANDメモリ10FS12、IS13、MS11からのReadデータを一時的に保存するための領域である。RC22は、本実施形態では例えば、mline、nwaymは2k-i以上の自然数、nは2以上の自然数セットアソシアティブ方式で管理されており、1エントリに1クラスタ分のデータを保持できる。論理クラスタアドレスのLSBk-iビットでlineが決定される。なお、RC22は、フルアソシアティブ方式で管理されていても良いし、単純なFIFO方式で管理されていてもよい。ライトキャッシュWC21WC21について説明する。WC21は、ATAコマンド処理部121からのWrite要求に対して、ホスト装置1からのWriteデータを一時的に保存するための領域である。mline、nwaymは2k-i以上の自然数、nは2以上の自然数セットアソシアティブ方式で管理されており、1エントリに1クラスタ分のデータを保持できる。論理クラスタアドレスのLSBk-iビットでlineが決定される。例えば、way1~waynの順で書き込み可能なwayが検索される。また、WC21に登録されているトラックは最も古く更新された順が分かるように後述するWCトラック管理テーブル24のFIFO構造によってLRULeastRecentlyUsedで管理される。なお、WC21は、フルアソシアティブ方式で管理されていても良い。また、WC21は、RC22とline数、way数が互いに異なっていてもよい。Write要求により書き込まれたデータは、一旦WC21上に格納される。WC21からNANDメモリ10へ追い出すデータの決定方法は以下のルールに従う。iタグによって決定されたlineの書き込み可能なwayが最後の空きwayだった場合、則ち最後の空きwayが使用される場合は、そのlineに登録されたトラックのうち、LRUに基づいて最も古く更新されたトラックを追い出し確定する。iiWC21に登録されている異なるトラックの個数が所定数を超えた場合、LRU順で、当該トラックに属するWC中のクラスタ数が所定数未満のトラックの追い出しを確定する。以上の方針で追い出すトラックを決定する。その際、追い出すのは同一トラックに含まれる全てのデータであり、追い出されるデータ量が、例えばトラックサイズの50を超えていればMS11へ、超えていなければFS12へ追い出す。さらにiの条件でトラック追い出しが発生した場合で、MS11へ追い出す場合は、追い出されるトラック数が2i個もともと2i個以上のときは2i1個になるまで、WC21内のトラックのうち上記追い出されるデータ量がトラックサイズの50を超えるという条件を満たすトラックを上記のポリシーで選択して追い出し候補に追加する。別言すれば、追い出されるトラックが2i個未満の場合、WC中のトラックの古いものから2i個になるまで、2k-i-1個以上有効クラスタをもつトラックを選択して追い出し候補に追加する。また、iの条件でトラック追い出しが発生した場合で、FS12に追い出す場合は、追い出されるクラスタ数が2k個になるまでWC21内のトラックのうちLRU順に上記追い出されるデータ量がトラックサイズの50未満であるという条件を満たすトラックを探してそのクラスタを追い出し候補に追加する。別言すれば、WC中のトラックを古い順に辿って2k-i-1個未満の有効クラスタしかもたないトラックからクラスタを取り出していき、有効クラスタ数が2k-i-1個になったら、それらクラスタをFSIB12aに論理ブロック単位で追い出しする。ただし、2k-i-1個見つからなかった場合は、FSIB12aに論理ページ単位で追い出しする。なお、FS12への追い出しを論理ブロック単位とするか、論理ページ単位とするかの有効クラスタ数の閾値は、2k-i-1個という1論理ブロック分の値にかぎるわけではなく、1論理ブロック分より若干少ない値であってもよい。また、ATAコマンド処理部121からのCacheFlush要求では、WC21の内容が全て、上記と同じ条件追い出されるデータ量がトラックサイズの50を超えていればMS11へ、超えていなければFS12へで、FS12もしくはMS11に対して追い出される。前段ストレージ領域FS12つぎに、FS12について説明する。FS12はクラスタ単位でデータを管理されるFIFOである。FS12は、ここを通過しているデータは、後段のIS13よりも更新頻度が高いとみなすためのバッファである。すなわち、FS12のFIFO構造においては、FIFO中を通過中の有効クラスタ最新クラスタは、ホストからの同じアドレスに対する再書き込みがあった場合無効化されるので、FS12を通過中のクラスタは、FS12からIS13やMS11に追い出されたクラスタよりも、更新頻度が高いとみなすことができる。FS12を設けることで、後段のIS13におけるコンパクション処理に更新頻度の高いデータが紛れ込む可能性を低減している。無効化によって古いクラスタを保持していた論理ブロック自体の持つ有効クラスタ数が0となった場合、その論理ブロックは開放され、フリーブロックFBに割り当てられる。また、論理ブロックが無効化された場合、新たなフリーブロックFBを取得し、FS12に割り当てる。WC21からFS12に対してクラスタデータの移動が発生すると、そのクラスタはFSIB12aに割り当てられた論理ブロックに対して書き込まれる。FSIB12a中に全てのページの書き込みが完了したブロックが存在する場合、後述するCIB処理によってそれらのブロックはFSIB12aからFS12にMoveされる。このFSIB12aからFS12へのMoveの際に、FS12のブロック数がFS12として許容される所定の上限値を超えると、最も古いブロックがFS12からIS13またはMS11に追い出されることになる。例えば、トラック内の有効クラスタの割合が50以上のトラックは、MS11TFS11bへの書き込みを行い、有効クラスタが残ったブロックを、IS13へMoveする。NANDメモリ10内の構成要素間のデータ移動には、MoveとCopyの二通りがある。Moveは、後述する管理テーブルのポインタの付け替えを行うだけで、実際のデータの書き換えは行わない方法である。Copyは、一方の構成要素に格納されているデータを、ページ単位、トラック単位、ブロック単位で他方の構成要素に実際に書き換える方法である。中段ストレージ領域IS13つぎに、IS13について説明する。IS13は、FS13と同様にクラスタ単位でデータの管理が行われる。前述したように、IS13に格納されたデータは、更新頻度が低いデータとみなすことができる。FS12からIS13に対して論理ブロックの移動Move、すなわちFS12からの追い出しが発生すると、以前FS12の管理対象であった追い出し対象の論理ブロックはポインタの付け替えによりIS13の管理対象ブロックとなる。このFS12からIS13への論理ブロックの移動により、IS13のブロック数がIS13として許容される所定の上限値を超えると、すなわちIS内の書き込み可能なフリーブロックFBの数が閾値を下回ると、IS13からMS11へのデータ追い出しおよびコンパクション処理が実行され、IS13のブロック数は規定値に戻される。IS13では、トラック内の有効クラスタ数を使って以下のような、追い出し処理およびコンパクション処理を、実行する。トラックをトラック内の有効クラスタ数×有効クラスタ係数順にソートし、積の値が大きいトラック2i1個を集めて論理ブロックサイズの自然数倍にしてMSIB11aに追い出す。有効クラスタ数が最も少ない2つの論理ブロックの合計有効クラスタ数が例えば、所定の設定値である2k個1論理ブロック分以上ある場合は、上のステップを繰り返す。有効クラスタ数の少ない論理ブロックから順にクラスタを2k個集め、IS13内でコンパクションを行う。なお、ここでは有効クラスタ数が最も少ない2つの論理ブロックを選択するとしたが、この数は2つに限定されず、2つ以上の数であればよい。また、所定の設定値は、選択する論路ブロック数よりも1つ少ない論理ブロック数に収容可能なクラスタ数以下であればよい。メインストレージ領域MS11つぎに、MS11について説明する。MS11はトラック単位でデータの管理を行う。MS11に格納されたデータは、更新頻度が低いとみなすことができる。WC21、FS12、IS13からMS11に対してトラックデータのCopyまたはMoveが発生すると、そのトラックはMSIS11aに割り当てられた論理ブロックに対して書き込まれる。一方で、トラック中の一部のデータクラスタのみがWC等から書き込まれるような場合には、既存のMS中のトラックデータと新しいデータをマージして新しいトラックデータを作った上でMSIB11aに書き込む、後述する受動マージが行われる。MS11内に無効トラックが蓄積し、MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を越えるような状況が発生すると、コンパクション処理を行って、無効なフリーブロックFBを作る。MS11のコンパクション処理は、例えば、論理ブロック内の有効トラック数のみに注目した以下の方法を実施する。有効トラックが少ない論理ブロックから順番に、無効トラックを合わせることによって無効なフリーブロックFBが作れるようになるまで選択する。選択した論理ブロックに収容されたトラックを、WC21、FS12、IS13内のデータと統合する受動マージを行いながらコンパクションを実行する。2iトラック統合できた論理ブロックは、TFS11bに出力し2iトラックMSコンパクション、2iトラックに満たない個数のトラックは、MSIB11aに出力して2iトラック未満コンパクション、より多くの無効なフリーブロックFBを作る。TFS11bは、トラック単位でデータを管理されるFIFOである。TFS11bは、ここを通過しているデータは、後段のMS11よりも更新頻度が高いとみなすためのバッファである。すなわち、TFS11bのFIFO構造においては、FIFO中を通過中の有効トラック最新トラックは、ホストからの同じアドレスに対する再書き込みがあった場合無効化されるので、TFS11bを通過中のトラックは、TFS11bからMS11に追い出されたトラックよりも、更新頻度が高いとみなすことができる。図8は、データ管理部120が図5および図6に示した各構成要素を制御管理するための管理テーブルを示すものである。データ管理部120は、前述したように、ATAコマンド処理部121とNANDメモリ10とをブリッジする機能を有し、DRAM20に記憶したデータの管理を行うDRAM層管理部120aと、NANDメモリ10に記憶したデータの管理を行う論理NAND層管理部120bと、NANDメモリ10を物理記憶デバイスとして管理する物理NAND層管理部120cとから構成される。RCクラスタ管理テーブル23、WCトラック管理テーブル24、WCクラスタ管理テーブル25は、DRAM層管理部120aにより制御される。トラック管理テーブル30、FS/IS管理テーブル40、MS論理ブロック管理テーブル35、FS/IS論理ブロック管理テーブル42、FS/IS内クラスタ管理テーブル44は、論理NAND層管理部120bにより管理される。論物変換テーブル50は、物理NAND層管理部120cにより管理される。RC22は、逆引きテーブルであるRCクラスタ管理テーブル23によって管理される。逆引きテーブルでは、記憶デバイスの位置からその位置に記憶されている論理アドレスを検索することができる。WC21は、逆引きテーブルであるWCクラスタ管理テーブル25および正引きテーブルであるWCトラック管理テーブル24によって管理される。正引きテーブルでは、論理アドレスからその論理アドレスに対応するデータが存在する記憶デバイス位置を検索することができる。NANDメモリ10内のFS12FSIB12a、IS13、MS11TFS11b、MSIB11aは、トラック管理テーブル30、FS/IS管理テーブル40、MS論理ブロック管理テーブル35、FS/IS論理ブロック管理テーブル42、FS/IS内クラスタ管理テーブル44によってその論理アドレスが管理される。また、NANDメモリ10内のFS12FSIB12a、IS13、MS11TFS11b、MSIB11aは、論物変換テーブル50によって論理アドレスと物理アドレスとの変換が行われる。これらの各管理テーブルは、NANDメモリ10上の領域に記憶されており、SSD100の初期化時にNANDメモリ10からDRAM20上に読み込まれて、使用される。RCクラスタ管理テーブル23逆引きまず、図9を用いてRCクラスタ管理テーブル23について説明する。RC22は、前述したように、論理クラスタアドレスLSBk-iビットでインデックスされるnwayセットアソシアティブ方式で管理されている。RCクラスタ管理テーブル23は、RCクラスタサイズ×mline×nway22の各エントリのタグを管理するためのテーブルであり、各タグは、複数ビットの状態フラグ23aと、論理トラックアドレス23bによって構成されている。状態フラグ23aには、当該エントリを使用しても良いか否か有効/無効を示すValidビットの他に、当該エントリがNANDメモリ10からの読み出し待ちか否かを示すビット、当該エントリがATAコマンド処理部121への読み出し待ちか否かを示すビットなどが含まれる。RCクラスタ管理テーブル23は、DRAM20上のタグ記憶位置からLBAに一致する論理トラックアドレスを検索する逆引きテーブルとして機能する。WCクラスタ管理テーブル25逆引きつぎに、図10を用いてWCクラスタ管理テーブル25について説明する。WC21は、前述したように、論理クラスタアドレスLSBk-iビットでインデックスされるnwayセットアソシアティブ方式で管理されている。WCクラスタ管理テーブル25は、WCクラスタサイズ×mline×nway21の各エントリのタグを管理するためのテーブルであり、各タグは、複数ビットの状態フラグ25aと、セクタ位置ビットマップ25bと、論理トラックアドレス25cによって構成されている。状態フラグ25aには、当該エントリを使用しても良いか否か有効/無効を示すValidビットの他に、当該エントリがNANDメモリ10への追い出し待ちか否かを示すビット、当該エントリがATAコマンド処理部からの書き込み待ちか否かを示すビットなどが含まれる。セクタ位置ビットマップ25bは、1クラスタに含まれる2l-kセクタのうちのどのセクタに有効なデータを保持しているかを2l-kビットに展開して示すものである。このセクタ位置ビットマップ25bによって、WC21において、LBAと同じセクタ単位の管理を行うことができる。WCクラスタ管理テーブル25は、DRAM20上のタグ記憶位置からLBAに一致する論理トラックアドレスを検索する逆引きテーブルとして機能する。WCトラック管理テーブル24正引きつぎに、図11を用いてWCトラック管理テーブル24について説明する。WCトラック管理テーブル24は、WC21上に格納されているクラスタをトラック単位でまとめた情報を管理するものであり、FIFO的な機能を有するリンクドリスト構造によってトラック間のWC21に登録された順序LRUを表現している。なお、WC21で最後に更新された順序によってLRUを表現するようにしてもよい。各リストのエントリは、論理トラックアドレス24a、当該論理トラックアドレスに含まれるWC21中の有効クラスタ数24b、waylineビットマップ24cおよび次のエントリへのポインタを示すnextポインタ24dから構成されている。WCトラック管理テーブル24は、論理トラックアドレス24aから所要情報を得るので、正引きテーブルとして機能する。waylineビットマップ24cは、WC21中で当該論理トラックアドレスに含まれる有効クラスタがWC21中のm×nのエントリ中のどのエントリに格納されているか示すマップ情報であり、有効クラスタが格納されているエントリではValidビットが1になっている。このwaylineビットマップ24cは、例えば、1ビットValidlog2nビットnway×mビットmlineで構成されている。WCトラック管理テーブル24はリンクドリスト構造を有しており、WC21中に存在する論理トラックアドレスに関する情報のみがエントリされている。トラック管理テーブル30正引きつぎに、図12を用いてトラック管理テーブル30について説明する。トラック管理テーブル30は、論理トラックアドレス単位でMS11上の論理的なデータ位置を管理するためのテーブルであり、クラスタ単位でFS12やIS13にデータが保持されている場合には、それらに関する基本情報と、詳細情報へのポインタも保持している。論理トラックアドレス30aをインデックスとした配列形式で構成される。論理トラックアドレス30aをインデックスとした各エントリは、クラスタビットマップ30b、論理ブロックID30c論理ブロック内トラック位置30d、クラスタテーブルポインタ30e、FSクラスタ数30f、ISクラスタ数30gなどの情報で構成されている。トラック管理テーブル30は、論理トラックアドレスをインデックスとして、その論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックID記憶デバイス位置に対応などの所要情報を得るので、正引きテーブルとして機能する。クラスタビットマップ30bは、1つの論理トラックアドレス範囲に属する2k-i個のクラスタをクラスタアドレス昇順に例えば8分割したビットマップであり、8個の各ビットは、2k-i-3個のクラスタアドレスに対応するクラスタがMS11に存在するか、FS12もしくはIS13に存在するかを示している。ビットが0の場合は、その検索対象のクラスタは確実にMS11内に存在することを示し、ビットが1の場合は、そのクラスタはFS12もしくはIS13に存在する可能性があることを示している。論理ブロックID30cは、当該論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックIDを識別するための情報である。論理ブロック内トラック位置30dは、論理ブロックID30cで指定された論理ブロック中における当該論理トラックアドレス30aに対応するトラックの記憶位置を示すものである。1論理ブロックは最大2i個の有効トラックで構成されるので、論理ブロック内トラック位置30dは、iビットで2i個のトラック位置を識別する。クラスタテーブルポインタ30eは、リンクドリスト構造を有するFS/IS管理テーブル40の各リストの先頭エントリへのポインタである。クラスタビットマップ30bの検索で、当該クラスタがFS12/IS13に存在する可能性があることを示していた場合、クラスタテーブルポインタ30eを用いてFS/IS管理テーブル40の検索を実行する。FSクラスタ数30fは、FS12内に存在する有効クラスタ数を示している。ISクラスタ数30gは、IS13内に存在する有効クラスタ数を示している。FS/IS管理テーブル40正引きつぎに、図13を用いてFS/IS管理テーブル40について説明する。FS/IS管理テーブル40は、論理クラスタ単位でFS12FSIB12aも含むもしくはIS13に保持されているデータの位置を管理するためのテーブルである。図13に示すように、論理トラックアドレス毎に独立したリンクドリスト形式で構成され、各リストの先頭エントリへのポインタは、前述したように、トラック管理テーブル30のクラスタテーブルポインタ30eのフィールドに保持されている。図13では、2つの論理トラックアドレス分のリンクドリストが示されている。各エントリは、論理クラスタアドレス40a、論理ブロックID40b、論理ブロック内クラスタ位置40c、FS/ISブロックID40d、nextポインタ40eから構成されている。FS/IS管理テーブル40は、論理クラスタアドレス40aから、その論理クラスタアドレスに対応する論理クラスタが記憶されている論理ブロックID40b、論理ブロックン内クラスタ位置40c記憶デバイス位置に対応などの所要情報を得るので、正引きテーブルとして機能する。論理ブロックID40bは、当該論理クラスタアドレス40aに対応する論理クラスタが記憶されている論理ブロックIDを識別するための情報である。論理ブロック内クラスタ位置40cは、論理ブロックID40bで指定された論理ブロック中における当該論理クラスタアドレス40aに対応するクラスタの記憶位置を示すものである。1論理ブロックは最大2k個の有効クラスタで構成されるので、論理ブロック内クラスタ位置40cは、kビットで2k位置を識別する。FS/ISブロックID40dは、後述するFS/IS論理ブロック管理テーブル42のインデックスであるFS/ISブロックIDが登録されている。FS/ISブロックIDは、FS12またはIS13に所属する論理ブロックを識別するための情報であり、このFS/IS管理テーブル40でのFS/ISブロックID40dは、後述するFS/IS論理ブロック管理テーブル42とのリンクのために登録されている。nextポインタ40eは、論理トラックアドレス毎にリンクされる同じリスト内の次のエントリへのポインタを示している。MS論理ブロック管理テーブル35逆引きつぎに、図14を用いてMS論理ブロック管理テーブル35について説明する。MS論理ブロック管理テーブル35は、MS11に用いられている論理ブロックに関する情報どの論理トラックが記憶されているか、追記可能か等を一元管理するためのテーブルである。なお、MS論理ブロック管理テーブル35には、FS12FSIB12も含む、IS13に所属する論理ブロックに関する情報も登録されている。MS論理ブロック管理テーブル35は、論理ブロックID35aをインデックスとした配列形式で構成され、エントリ数は128GBのNANDメモリ10の場合は、32Kエントリまで持つことができる。各エントリは、2iトラック分のトラック管理ポインタ35b、有効トラック数35c、書き込み可能先頭トラック35d、Validフラグ35eから構成されている。このMS論理ブロック管理テーブル35は、記憶デバイス位置に対応する論理ブロックID35aから、この論理ブロックに記憶されている論理トラックアドレスなどの所要情報を得るので、逆引きテーブルとして機能する。トラック管理ポインタ35bは、論理ブロックID35aで指定される当該論理ブロック内の2i個のトラック位置毎に対応する論理トラックアドレスを保持する。この論理トラックアドレスを用いて、論理トラックアドレスをインデックスとするトラック管理テーブル30を検索することができる。有効トラック数35cは、論理ブロックID35aで指定される当該論理ブロックに記憶されているトラックのうちの有効なものの個数最大2i個を示している。書き込み可能先頭トラック位置35dは、論理ブロックID35aで指定される当該論理ブロックが追記中のブロックであった場合における追記可能なトラック先頭位置0~2i-1、追記終了時は2iを示している。Validフラグ35eは、当該論理ブロックエントリがMS11MSIB11aも含むとして管理されている場合に1である。FS/IS論理ブロック管理テーブル42逆引きつぎに、図15を用いてFS/IS論理ブロック管理テーブル42について説明する。FS/IS論理ブロック管理テーブル42は、FS/ISブロックID42aをインデックスとした配列形式で構成され、FS12またはIS13として利用されている論理ブロックに関する情報論理ブロックIDとの対応、FS/IS内クラスタ管理テーブル44へのインデックス、追記可能か等を管理するためのテーブルである。FS/IS論理ブロック管理テーブル42は、主にFS/IS管理テーブル40中のFS/ISブロックID40dを用いてアクセスされる。各エントリは、論理ブロックID42b、ブロック内クラスタテーブル42c、有効クラスタ数42d、書き込み可能先頭ページ42e、Validフラグ42fから構成されている。このMS論理ブロック管理テーブル35は、記憶デバイス位置に対応するFS/ISブロックID42aから、この論理ブロックに記憶されている論理クラスタなどの所要情報を得るので、逆引きテーブルとして機能する。論理ブロックID42bには、MS論理ブロック管理テーブル35に登録された論理ブロックの中で、FS12FSIB12も含む、IS13に所属している論理ブロックに対応する論理ブロックIDが登録される。ブロック内クラスタテーブル42cには、論理ブロック中の各クラスタ位置にどの論理クラスタアドレスで指定される論理クラスタが記録されているかを示す後述するFS/IS内クラスタ管理テーブル44へのインデックスが登録される。有効クラスタ数42dは、FS/ISブロックID42aで指定される当該論理ブロックに記憶されているクラスタのうちの有効なものの個数最大2k個を示している。書き込み可能先頭ページ位置42eは、FS/ISブロックID42aで指定される当該論理ブロックが追記中のブロックであった場合における追記可能な先頭ページ位置0~2j-1、追記終了時は2jを示している。Validフラグ42fは、この論理ブロックエントリがFS12FSIB12も含むまたはIS13として管理されている場合に1である。FS/IS内クラスタ管理テーブル44逆引きつぎに、図16を用いてFS/IS内クラスタ管理テーブル44について説明する。FS/IS内クラスタ管理テーブル44は、FS12もしくはIS13として利用されている論理ブロック中の各クラスタ位置にどの論理クラスタが記録されているのかを示すテーブルである。1論理ブロックあたり、2jページ×2k-jクラスタ=2k個のエントリを持ち、当該論理ブロック内のクラスタ位置の0番目~2k-1番目に対応する情報が連続領域に配置される。さらにこの2k個の情報を含むテーブルがFS12およびIS13に所属する論理ブロック数P個分だけ保持されており、FS/IS論理ブロック管理テーブル42のブロック内クラスタテーブル42cは、このP個のテーブルに対する位置情報ポインタとなっている。連続領域に配される各エントリ44aの位置は、1論理ブロック中のクラスタ位置を示し、また各エントリ44aの内容は、当該クラスタ位置にどの論理クラスタが記憶されているかが識別できるように、FS/IS管理テーブル40で管理される該当論理クラスタアドレスを含むリストへのポインタが登録されている。すなわち、エントリ44aは、リンクドリストの先頭を指し示すのではなく、リンクドリスト中の該当論理クラスタアドレスを含む1つのリストへのポインタが登録されている。論物変換テーブル50正引きつぎに、図17を用いて論物変換テーブル50について説明する。論物変換テーブル50は、論理ブロックID50aをインデックスとした配列形式で構成され、エントリ数は、128GBのNANDメモリ10の場合は、最大32Kエントリまで持つことができる。論物変換テーブル50は、論理ブロックIDと物理ブロックIDとの変換、寿命に関する情報を管理するためのテーブルである。各エントリは、物理ブロックアドレス50b、消去回数50c、読み出し回数50dから構成される。この論物変換テーブル50は、論理ブロックIDから物理ブロックID物理ブロックアドレスなどの所要情報を得るので、正引きテーブルとして機能する。物理ブロックアドレス50bは、1つの論理ブロックID50aに所属する8個の物理ブロックID物理ブロックアドレスを示している。消去回数50cは、当該論理ブロックIDの消去回数を示している。バッドブロックBB管理は、物理ブロック512KB単位に行われるが、消去回数の管理は、32ビット倍速モードによる1論理ブロック4MB単位に管理される。読み出し回数50dは、当該論理ブロックIDの読み出し回数を示している。消去回数50cは、例えば、NAND型フラッシュメモリの書き換え回数を平準化するウェアレベリング処理で利用することが可能である。読み出し回数50dは、リテンション特性の劣化した物理ブロックに保持されるデータの再書き込みを行うリフレッシュ処理で利用することが可能である。図8に示した管理テーブルを管理対象毎にまとめると次のようになる。RC管理:RCクラスタ管理テーブルWC管理:WCクラスタ管理テーブル、WCトラック管理テーブルMS管理:トラック管理テーブル30、MS論理ブロック管理テーブル35FSIS管理:トラック管理テーブル30、FSIS管理テーブル40、MS論理ブロック管理テーブル35、FSIS論理ブロック管理テーブル42、FSIS内クラスタ管理テーブル44なお、MS構造管理テーブル図示せずにおいて、MS11,MSIB11a、TFS11bを含めたMS領域の構造を管理しており、具体的には、MS11、MSIB11a、TFS11bに割り当てた論理ブロックなどを管理している。また、FSIS構造管理テーブル図示せずにおいて、FS12、FSIB12a、IS13を含めたFSIS領域の構造を管理しており、具体的には、FS12、FSIB12a、IS13に割り当てた論理ブロックなどを管理している。Read処理つぎに、図18に示すフローチャートを参照して、読み出し処理について説明する。ATAコマンド処理部121から、Readコマンドおよび読み出しアドレスとしてのLBAが入力されると、データ管理部120は、図9に示したRCクラスタ管理テーブル23と図10に示したWCクラスタ管理テーブル25を検索するステップS100。具体的には、LBAのクラスタアドレスのLSBk-iビット図7参照に対応するlineをRCクラスタ管理テーブル23とWCクラスタ管理テーブル25から選択し、選択したlineの各wayにエントリされている論理トラックアドレス23b、25cをLBAのトラックアドレスと比較しステップS110、一致したwayが存在している場合は、キャッシュヒットとし、ヒットしたRCクラスタ管理テーブル23またはWCクラスタ管理テーブル25の該当line、該当wayに対応するWC21またはRC22のデータを読み出して、ATAコマンド処理部121に送るステップS115。データ管理部120は、RC22またはWC21でヒットしなかった場合はステップS110、検索対象のクラスタがNANDメモリ10のどこに格納されているかを検索する。データ管理部120は、まず、図12に示したトラック管理テーブル30を検索するステップS120。トラック管理テーブル30は、論理トラックアドレス30aでインデックスされているため、LBAで指定された論理トラックアドレスに一致する論理トラックアドレス30aのエントリだけをチェックする。まず、チェックしたいLBAの論理クラスタアドレスに基づいてクラスタビットマップ30bから対応するビットを選択する。対応するビットが0を示していれば、そのクラスタは確実にMS内に最新のデータが存在していることを意味するステップS130。この場合は、このトラックが存在する論理ブロックIDおよびトラック位置を、同じ論理トラックアドレス30aのエントリ中の論理ブロックID30cと論理ブロック内トラック位置30dから得て、さらにLBAのクラスタアドレスのLSBk-iビットを利用して、トラック位置からのオフセットを算出することで、NANDメモリ10内の当該クラスタアドレスに対応するクラスタデータが格納されている位置を算出することができる。具体的には、論理NAND層管理部120bでは、上記のようにしてトラック管理テーブル30から取得した論理ブロックID30cと論理ブロック内トラック位置30dと、LBAの論理クラスタアドレスのLSBk-iビットを物理NAND層管理部120cに与える。物理NAND層管理部120cでは、論理ブロックID30cに対応する物理ブロックアドレス物理ブロックIDを、論理ブロックIDをインデックスとしている図17に示す論物変換テーブル50から取得しステップS160、さらに取得した物理ブロックID中のトラック位置トラック先頭位置を論理ブロック内トラック位置30dから算出し、さらにLBAのクラスタアドレスのLSBk-iビットから、前記算出した物理ブロックID中のトラック先頭位置からのオフセットを算出することで、物理ブロック中のクラスタデータを取得することができる。NANDメモリ10のMS11から取得されたクラスタデータは、RC22を介してATAコマンド処理部121に送られるステップS180。一方、LBAのクラスタアドレスに基づくクラスタビットマップ30bの検索で、対応するビットが1を示していた場合は、そのクラスタがFS12またはIS13に格納されている可能性があるステップS130。この場合は、トラック管理テーブル30の該当する論理トラックアドレス30aのエントリ中のクラスタテーブルポインタ30eのエントリを取り出し、このポインタを用いてFS/IS管理テーブル40の該当する論理トラックアドレスに対応するリンクドリストを順次検索するステップS140。具体的には、該当する論理トラックアドレスのリンクドリスト中のLBAの論理クラスタアドレスに一致する論理クラスタアドレス40aのエントリを検索し、一致する論理クラスタアドレス40aのエントリが存在した場合はステップS150、一致したリスト中の論理ブロックID40bおよび論理ブロック内クラスタ位置40cを取得し、前述と同様にして、論物変換テーブル50を用いて物理ブロック中のクラスタデータを取得するステップS160、S180。具体的には、取得した論理ブロックIDに対応する物理ブロックアドレス物理ブロックIDを、論物変換テーブル50から取得しステップS160、さらに取得した物理ブロックID中のクラスタ位置を、論理ブロック内クラスタ位置40cのエントリから取得した論理ブロック内クラスタ位置から算出することで、物理ブロック中のクラスタデータを取得することができる。NANDメモリ10のFS12またはIS13から取得されたクラスタデータは、RC22を介してATAコマンド処理部121に送られるステップS180。このFS/IS管理テーブル40の検索によって、検索対象のクラスタが存在しなかった場合はステップS150、再度トラック管理テーブル30のエントリを検索してMS11上の位置を確定するステップS170。Write処理つぎに、図19に示すフローチャートを参照して、書き込み処理について説明する。FUADRAMキャッシュをバイパスしてNANDへの直接書き込みを行うでないWriteコマンドにより書き込まれたデータは必ず一旦WC21上に格納され、その後条件に応じてNANDメモリ10に対して書き込まれることになる。書き込み処理では、追い出し処理、コンパクション処理が発生する可能性がある。この実施の形態では、書き込み処理を、ライトキャッシュフラッシュ処理以下WCF処理と、クリーンインプットバッファ処理以下CIB処理との2ステージに大きく分割している。ステップS300からステップS320までは、ATAコマンド処理部121からのWrite要求からWCF処理までを示しており、ステップS330~最終ステップまでがCIB処理を示している。WCF処理は、WC21にあるデータをNANDメモリ10FS12のFSIB12aまたはMS11のMSIB11aにcopyする処理であり、ATAコマンド処理部121からのWrite要求もしくはCacheFlush要求単体は、この処理のみで完結することができる。これにより処理が開始されたATAコマンド処理部121のWrite要求の処理遅延を最大でもWC21の容量分のNANDメモリ10への書き込み時間に限定することができるようになる。CIB処理は、WCF処理によって書き込まれたFSIB12aのデータをFS12にMoveする処理と、WCF処理によって書き込まれたMSIB11aのデータをMS11にMoveする処理とを含む。CIB処理を開始すると、連鎖的にNANDメモリ10内の各構成要素FS12、IS13、MS11など間のデータ移動やコンパクション処理が発生する可能性があり、処理全体に要する時間は状態によって大きく変化する。まず、WCF処理の詳細について説明する。ATAコマンド処理部121から、Writeコマンドおよび書き込みアドレスとしてのLBAが入力されると、DRAM層管理部120は、図10に示したWCクラスタ管理テーブル25を検索するステップS300,S305。WC21の状態は、図10に示したWCクラスタ管理テーブル25の状態フラグ25a例えば3ビットによって規定されている。状態フラグ25aは、最も典型的には、Invalid使用可能→ATAからの書き込み待ち→Valid使用不可→NANDへの追い出し待ち→Invalid使用可能という順に状態が遷移していく。まず、LBAのクラスタアドレスLSBk-iビットから書き込み先のlineを決定し、決定したlineのn個のwayを検索する。決定したlineのn個のway中に、入力されたLBAと同じ論理トラックアドレス25cが格納されている場合はステップS305、このエントリに上書きするのでこのエントリをクラスタ書き込み用に確保するValid使用不可→ATAからの書き込み待ち。そして、DRAM層管理部120aは、該当エントリに対応するDRAMアドレスをATAコマンド処理部121に通知する。ATAコマンド処理部121による書き込みが終了すると、WCクラスタ管理テーブル25の該当エントリの状態フラグ25aをValid使用不可にし、さらにセクタ位置ビットマップ25bおよび論理トラックアドレス25cの欄に所要のデータを登録する。また、WCトラック管理テーブル24を更新する。具体的には、WCトラック管理テーブル24の各リスト中に既に登録済みの論理トラックアドレス24aと同じLBAアドレスが入力された場合は、該当するリストのWCクラスタ数24b、way-lineビットマップ24cを更新するとともに、当該リストが最新のリストとなるようにnextポインタ24dを変更する。また、WCトラック管理テーブル24の各リスト中に登録済みの論理トラックアドレス24aと異なるLBAアドレスが入力された場合は、新たに新しい論理トラックアドレス24a、WCクラスタ数24b、way-lineビットマップ24c、nextポインタ24dの各エントリを有するリストを作成し、最新のリストとして登録する。以上のようなテーブル更新を行って、書き込み処理が完了するステップS320。一方、決定したlineのn個のway中に、入力されたLBAと同じ論理トラックアドレス25cが格納されていない場合は、NANDメモリへの追い出しが必要であるか否かを判断するステップS305。すなわち、まず、決定したline中の書き込み可能なwayが最後のn個目のwayであるか否かを判断する。書き込み可能なwayとは、Invalid使用可能の状態フラグ25aをもつwayかあるいはValid使用不可でかつNANDへの追い出し待ちの状態フラグ25aを持つwayである。状態フラグ25aが、NANDへの追い出し待ちであるとは、追い出しが開始されて追い出しの終了待ちであることを意味する。そして、書き込み可能なwayが最後のn個目のwayでない場合であって、かつ書き込み可能なwayが、Invalid使用可能の状態フラグ25aをもつwayである場合は、このエントリをクラスタ書き込み用に確保するInvalid使用可能→ATAからの書き込み待ち。そして、該当エントリに対応するDRAMアドレスをATAコマンド処理部121に通知し、ATAコマンド処理部121によって書き込みを実行させる。そして、前記同様、WCクラスタ管理テーブル25およびWCトラック管理テーブル24を更新するステップS320。また、書き込み可能なwayが最後のn個目のwayでない場合であって、かつ書き込み可能なwayが、Valid使用不可でかつNANDへの追い出し待ちの状態フラグ25aを持つwayである場合は、このエントリをクラスタ書き込み用に確保するValid使用不可でかつNANDへの追い出し待ち→Valid使用不可でかつNANDへの追い出し待ちかつATAからの書き込み待ち。そして、追い出しが終了すると、状態フラグ25aをATAからの書き込み待ちにし、さらに、該当エントリに対応するDRAMアドレスをATAコマンド処理部121に通知し、ATAコマンド処理部121によって書き込みを実行させる。そして、前記同様、WCクラスタ管理テーブル25およびWCトラック管理テーブル24を更新するステップS320。以上の処理は、ATAコマンド処理部121からからの書き込み要求が入力された際に、追い出し処理をトリガしなくてもよい場合である。一方、この後の説明は、書き込み要求が入力された時点後に、追い出し処理をトリガする場合である。ステップS305において、決定したline中の書き込み可能なwayが最後のn個目のwayである場合は、前述したWC21からNANDメモリ10へ追い出すデータの決定方法のiの箇所で説明した条件、すなわち、iタグによって決定されたlineの書き込み可能なwayが最後の空きwayだった場合、則ち最後の空きwayが使用される場合は、そのlineに登録されたトラックのうちLRUに基づいて最も古く更新されたトラックを追い出し確定する、に基づいて追い出すトラックすなわちWC21内エントリを選択する。DRAM層管理部120aは、以上の方針で追い出すトラックを決定すると、前述したように、その際追い出すのは同一トラックに含まれるWC21中の全クラスタであり、追い出されるクラスタ量がトラックサイズの50を超えていれば、すなわち追い出し確定トラックのうちWC中に有効クラスタ数が2k-i-1個以上ある場合は、MSIB11aへ追い出しを行いステップS310、超えていなければ、すなわち追い出し確定トラックのうちWC中に有効クラスタ数が2k-i-1個未満である場合は、FSIB12aへと追い出すステップS315。WC21からMSIB11aへの追い出し、WC21からFSIB12aへの追い出しの詳細は、後述する。選択された追い出しエントリの状態フラグ25aは、Valid使用不可からNANDメモリ10への追い出し待ちに移行される。この追い出し先の判定は、WCトラック管理テーブル24を用いて実行される。すなわち、WCトラック管理テーブル24には、論理トラックアドレス毎に、有効なクラスタ数を示すWCクラスタ数24bのエントリが登録されており、このWCクラスタ数24bのエントリを参照することでWC21からの追い出し先を、FSIB12a、MSIB11aの何れにするかを決定する。また、way-lineビットマップ24cに、当該論理トラックアドレスに所属する全てのクラスタがビットマップ形式で登録されているので、追い出しを行う際には、このway-lineビットマップ24cを参照することで、容易に、追い出すべき各クラスタのWC21での記憶位置を知ることができる。また、上記書き込み処理中または書き込み処理後、前述の下記条件、iiWC21に登録されているトラックの数が所定数を超えた場合、が成立した場合も、上記同様にしてNANDメモリ10への追い出し処理を実行する。WC→MSIBCopyつぎに、上記有効クラスタ数有効クラスタ数が2k-i-1個以上に基づく判定によりWC21からMSIB11aへの追い出しが発生したときは、前述したように、次のような手順を実行するステップS310。1WCクラスタ管理テーブル25を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ25bを参照し、セクタ位置ビットマップ25bが全て1でない場合は、NANDメモリ10に含まれる同一クラスタ中のセクタとマージする、後述のクラスタ内セクタ穴埋めを行う。また、トラック中のWC21内に存在しないクラスタについてはNANDメモリ10から読み出してマージする、受動マージ処理を実行する。2.追い出し確定トラックが2i個未満の場合、WC21中のトラックの古いものから2i個になるまで2k-i-1個以上有効クラスタを持つ追い出し確定トラックを追加する。3.Copyされるトラックが2i個以上あれば、2i個ずつを組として、MSIB11aに対して論理ブロック単位に書き込みを行う。4.2i個組みに出来なかったトラックをMSIB11aに対してトラック単位に書き込みを行う。5.Copy終了後に既にFS、IS、MS上に存在していたクラスタ、トラックのうちコピーされたトラックに属するものを無効化する。このようなWC21からMSIB11aへのCopy処理に伴う各管理テーブルの更新処理について説明する。WCクラスタ管理テーブル25中の追い出されたトラックに所属するWC21中の全クラスタに対応するエントリ中の状態フラグ25aはInvalidとされ、この後これらエントリに対する書き込みが可能となる。また、WCトラック管理テーブル24中の追い出されたトラックに対応するリストについては、例えば直前のリストのnextポインタ24dが変更または削除されて、無効化される。一方、WC21からMSIB11aに対するトラック移動が発生すると、これに伴いトラック管理テーブル30およびMS論理ブロック管理テーブル35が更新される。まず、トラック管理テーブル30のインデックスである論理トラックアドレス30aを検索することで、移動されたトラックに対応する論理トラックアドレス30aが既に登録されているか否かを判定する。既に登録されている場合は、該当インデックスのクラスタビットマップ30bMS11側への移動であるので、該当ビットを全て0にする、論理ブロックID30c論理ブロック内トラック位置30dのフィールドを更新する。移動されたトラックに対応する論理トラックアドレス30aが未登録の場合は、該当する論理トラックアドレス30aのエントリに対し、クラスタビットマップ30b、論理ブロックID30c論理ブロック内トラック位置30dを登録する。また、トラック管理テーブル30の変更に応じて、MS論理ブロック管理テーブル35における、論理ブロックID35a、該当トラック管理ポインタ35b、有効トラック数35c、書き込み可能先頭トラック35dなどのエントリを必要に応じて更新する。なお、他の領域FS12やIS13等からMS11に対してトラック書き込みが発生した場合、もしくはMS11内部のコンパクション処理によるMS内トラック書き込みが発生した場合、書き込み対象のトラックに含まれるWC21内有効クラスタも同時にMSに書き込まれる。WC21からMS11への書き込みとしてこのような受動的マージも存在する。そのような受動的マージが行われた場合は、それらのクラスタはWC21上から削除無効化されることになる。WC→FSIBCopyつぎに、上記有効クラスタ数有効クラスタ数が2k-i-1個未満に基づく判定によりWC21からFSIB12aへの追い出しが発生したときは、前述したように、次のような手順を実行する。1.WCクラスタ管理テーブル25における追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ25bを参照し、セクタ位置ビットマップ25bが全て1でない場合は、NANDメモリ10に含まれる同一クラスタ中のセクタとマージする、クラスタ内セクタ穴埋めを行う。2.WC内のトラックを古い順に辿って2k-i-1個未満の有効クラスタしか持たないトラックからクラスタを取り出して行き、有効クラスタ数が2k個になったらそれら全クラスタをFSIB12aに論理ブロック単位に書き込む。3.2k個見つからなかった場合には、有効クラスタ数が2k-i-1個未満の全てのトラックを必要な論理ページ数分だけFSIB12aに書き込む。4.Copy終了後に既にFS、IS上に存在していたクラスタのうちコピーされたのと同じものを無効化する。このようなWC21からFSIB12aへのCopy処理に伴う各管理テーブルの更新処理について説明する。WCクラスタ管理テーブル25中の追い出されたトラックに所属するWC21中の全クラスタに対応するエントリ中の状態フラグ25aはInvalidとされ、この後これらエントリに対する書き込みが可能となる。また、WCトラック管理テーブル24中の追い出されたトラックに対応するリストについては、例えば直前のリストのnextポインタ24dが変更または削除されて、無効化される。一方、WC21からFSIB12aに対するクラスタ移動が発生すると、これに伴いトラック管理テーブル30のクラスタテーブルポインタ30e、FSクラスタ数30fなどを更新するとともに、FS/IS管理テーブル40の論理ブロックID40b、論理ブロック内クラスタ位置40cなどを更新する。なお、もともとFS12に存在していなかったクラスタについては、FS/IS管理テーブル40のリンクドリストへのリストが追加される。この更新に伴い、MS論理ブロック管理テーブル35、FS/IS論理ブロック管理テーブル42、およびFS/IS内クラスタ管理テーブル44の該当個所を更新する。CIB処理上記のようなWCF処理が終了すると、つぎに、論理NAND層管理部120bは、WCF処理によって書き込まれたFSIB12aのデータをFS12にMoveする処理と、WCF処理によって書き込まれたMSIB11aのデータをMS11にMoveする処理などを含むCIB処理を実行する。CIB処理を開始すると、前述したように、連鎖的に各ブロック間のデータ移動やコンパクション処理が発生する可能性があり、処理全体に要する時間は状態によって大きく変化する。このCIB処理においては、基本的には、先ずMS11でのCIB処理が行われステップS330、つぎに、FS12でのCIB処理が行われステップS340、つぎに再びMS11でのCIB処理が行われステップS350、つぎにIS13でのCIB処理が行われステップS360、最後に再びMS11でのCIB処理が行われるステップS370。なお、FS12からMSIB11aへの追い出し処理、あるいはFS12からIS13への追い出し処理、あるいはIS13からMSIB11aへの追い出し処理の際に、手順にループが発生した場合は、上記順番通りにならない場合もある。MS11、FS12およびIS13でのCIB処理を別々に説明する。MS11のCIB処理まず、MS11でのCIB処理について説明するステップS330。WC21、FS12、IS13からMS11に対してトラックデータの移動が発生すると、そのトラックデータはMSIB11aに書き込まれる。MSIB11aへの書き込み完了後は、前述したように、トラック管理テーブル30を更新してトラックが配置される論理ブロックID30cとブロック内トラック位置30dなどを変更するMove。MSIB11aに新たなトラックデータが書き込まれた場合、もともとMS11もしくはTFS11bに存在していたトラックデータは無効化される。この無効化処理は、MS論理ブロック管理テーブル35における古いトラック情報が保存されていた論理ブロックのエントリからトラックを無効化することで実現する。具体的には、MS論理ブロック管理テーブル35の該当エントリ中のトラック管理ポインタ35bのフィールド中の該当トラックのポインタが削除され、有効トラック数が-1される。このトラック無効化によって1論理ブロック中の全てのトラックが無効になった場合は、Validフラグ35eが無効化される。このような無効化などにより、MS11のブロックは無効なトラックを含んだものが発生し、これが繰り返されるとブロックの利用効率が低下して、使用可能な論理ブロックに不足が生じることがある。データ管理部120は、このような事態が発生して、MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を越えるような状況が発生すると、コンパクション処理を行って、無効なフリーブロックFBを作る。無効なフリーブロックFBは、物理NAND層管理部120cに返却される。そして、論理NAND層管理部120bは、MS11に割り当てられている論理ブロックの個数を減らした後、新たに書き込み可能なフリーブロックFBを物理NAND層管理部120cから取得する。コンパクション処理とは、コンパクション対象の論理ブロックが持つ有効クラスタを新しい論理ブロックに集めたり、あるいはコンパクション対象の論理ブロック中の有効トラックを他の論理ブロックにCopyしたりすることで、物理NAND層管理部120cに返却する無効なフリーブロックFBを作り、論理ブロックの利用効率を向上させるための処理である。なお、コンパクションを行う際には、コンパクション対象となったトラック領域に対して、WC、FS、IS上の有効なクラスタが存在する場合、それらを全てマージする受動マージを実行する。また、TFS11bに登録されている論理ブロックについては、コンパクション対象に含めない。以下に、MSIB11aにフルに成ったブロックが存在する場合を発生条件とした、MSIB11aからMS11またはTFS11bへの追い出しとコンパクション処理の一例について具体的に説明する。1.MS論理ブロック管理テーブル35のValidフラグ35eを参照することにより、MS11内に無効となった論理ブロックが存在する場合、そのブロックを無効なフリーブロックFBとする。2.MSIB11aでフルに成った論理ブロックをMS11に追い出す。具体的には、前述したMS構造管理テーブル図示せずを更新して、該当論理ブロックをMSIB管理下からMS管理下に移し変える。3.MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を越えるような状況が発生するか否かを判断し、発生している場合に、以下のMSコンパクションを実行する。4.MS論理ブロック管理テーブル35の有効トラック数35cのフィールドなどを参照することにより、TFS11bに含まれない論理ブロックのうち無効にされたトラックを持つものを、有効トラック数でソートする。5.有効トラック数の少ない論理ブロックから、トラックを集めてコンパクションを実施する。この際にまず、1論理ブロック分2iトラックずつCopyしてコンパクションを実施する。なお、コンパクション対象のトラックがWC21、FS12、IS13に有効クラスタを持つ場合にはそれらもマージする。6.コンパクション元の論理ブロックを無効なフリーブロックFBとする。7.コンパクションして有効な2iトラックで構成された1論理ブロックができたら、TFS11bの先頭にMoveする。8.論理ブロック内の有効トラックを他の論理ブロックにCopyして、無効なフリーブロックFBが作れる場合は、2iトラック未満の個数の有効トラックをMSIB11aに対し、トラック単位で追記書き込みする。9.コンパクション元の論理ブロックを無効なフリーブロックFBとする。10.MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を下回ると、MSコンパクション処理を終了する。FS12のCIB処理つぎに、FS12でのCIB処理について説明するステップS340。WC21からFSIB12aへのクラスタ書き込み処理によって全ページ書き込み済みの論理ブロックがFSIB12a中に作られた場合、FSIB12a中のそれらのブロックは、FSIB12aからFS12に対してMoveされる。このMoveにともなって複数の論理ブロックで構成されるFIFO構造のFS12から古い論理ブロックが追い出される状況が発生する。FSIB12aからFS12に対する追い出しおよびFS12からのブロック追い出しは、具体的には、次のように実現される。1.FS/IS論理ブロック管理テーブル42のValidフラグ35eなどを参照することにより、FS12内に無効となった論理ブロックが存在する場合、そのブロックを無効なフリーブロックFBとする。2.FSIB12aでフルに成ったブロックをFS12に追い出す。具体的には、前述したFS/IS構造管理テーブル図示せずを更新して、該当ブロックをFSIB管理下からFS管理下に移し変える。3.FS12に割り当てられている論理ブロックの個数がFS12として許容されるブロック数の上限値を越えるような状況が発生するか否かを判断し、発生している場合に、以下の追い出しを実行する。4.まず追い出し対象の最古の論理ブロック中のクラスタデータのうちIS13に移動せずに、直接MS11に移動すべきものを決定する実際には、MSの管理単位がトラックであるので、トラック単位での決定。ア追い出し対象の論理ブロック中の有効クラスタをページの先頭から順にスキャンする。イクラスタが属するトラックがFS中に何個の有効クラスタを保有しているか、トラック管理テーブル30のFSクラスタ数30fのフィールドを参照して検索する。ウトラック内有効クラスタ数が所定の閾値例えば2k-i個の50以上だった場合、そのトラックをMSへの追い出し候補とする。5.MS11に追い出すべきトラックをMSIB11aに対して書き込む。6.追い出しトラックが残っている場合、さらにMSIB11への追い出しを実行する。7.上記2~4の処理の後も追い出し対象の論理ブロックに有効なクラスタが存在している場合、この論理ブロックをIS13にMoveする。なお、FS12からMSIB11aへの追い出しが発生したときには、その直後、MS11での前述したCIB処理が実行されるステップS350。IS13のCIB処理つぎに、IS13でのCIB処理について説明するステップS360。上記したFS12からIS13へのブロック移動によって論理ブロックがIS13に追加されるが、これにともなって複数個の論理ブロックで構成されるIS13に対して管理可能なブロック数の上限を超えてしまう状況が発生する。このような状況が発生した場合、IS13では、まずMS11への1~複数個の論理ブロックの追い出しを行った後、ISコンパクションを実行する。具体的には、次のような手順を実行する。1.IS13に含まれるトラックをトラック内の有効クラスタ数×有効クラスタ係数でソートし、積の値が大きいトラック2i1個を集めてMSIB11aに追い出す。2.有効クラスタ数が最も少ない2i1個の論理ブロックの合計有効クラスタ数が例えば、所定の設定値である2k個1論理ブロック分以上ある場合は、上のステップを繰り返す。3.上記の追い出しを行った後、有効クラスタ数の少ない論理ブロックから順にクラスタを2k個集め、IS13内でコンパクションを行う。4.コンパクション元の論理ブロックのうち有効クラスタがなくなったものを無効なフリーブロックFBとして返還する。なお、IS13からMSIB11aへの追い出しが発生したときには、その直後、MS11での前述したCIB処理が実行されるステップS370。図20は、各構成要素間のデータの流れにおける入力と出力の組み合わせ、およびそのデータの流れが何をトリガとして発生するかを示すものである。FS12は、基本的には、WC21からのクラスタ追い出しによってデータが書き込まれるが、WC21からFS12への追い出しに付随してクラスタ内セクタ穴埋めクラスタ穴埋めが必要な場合は、FS12、IS13、MS11からのデータがコピーされる。WC21では、WCクラスタ管理テーブル25のタグ中のセクタ位置ビットマップ25bによって当該クラスタアドレス中の2l-k個のセクタの有無を識別させることによってセクタ512B単位の管理をすることが可能である。これに対し、NANDメモリ10での機能要素であるFS12、IS13の管理単位はクラスタであり、MS11の管理単位は、トラックである。このように、NANDメモリ10での管理単位は、セクタより大きいため、WC21からNANDメモリ10に対して、データを書き込む際に、書き込まれるデータと同一クラスタアドレスのデータがNANDメモリ10中に存在する場合、WC21からNANDメモリ10に書き込まれるクラスタ中のセクタと、NANDメモリ10中に存在する同一クラスタアドレス内のセクタとをマージしてから、NANDメモリ10に書き込む必要がある。この処理が、図20に示したクラスタ内セクタ穴埋め処理クラスタ穴埋めと、トラック内セクタ穴埋めトラック穴埋めであり、これらの処理を行わないと、正しいデータが読み出せなくなる。そこで、WC21からFSIB12aまたはMSIB11aにデータを追い出す際には、WCクラスタ管理テーブル25を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ25bを参照し、セクタ位置ビットマップ25bが全て1でない場合は、NANDメモリ10に含まれる同一クラスタまたは同一トラック中のセクタとマージする、クラスタ内セクタ穴埋めまたはトラック内セクタ穴埋めを行う。この処理には、DRAM20の作業領域が使用され、DRAM20の作業領域からMSIB11aに書き込まれたり、FSIB12aに書き込まれたりする。IS13は、基本的には、FS12からのブロック追い出しによってデータが書き込まれるMoveか、IS内部のコンパクションによってデータが書き込まれる。MS11は、全ての箇所からデータが書き込まれ得る。その際、MS11は、トラック単位にしかデータを書き込めないために、MS自身のデータによる穴埋めが発生しうる。また、トラック単位の書き込みを行う際には、他のブロックにある断片化されたデータも受動マージによって書き込まれることになる。さらにMS11は、MSコンパクションによる書き込みもある。なお、受動マージにおいては、WC21、FS12またはIS13の3つの構成要素のうちの1つの構成要素からMS11へのトラック追い出しまたは論理ブロック追い出し2iトラック分の追い出しが発生した際、1つの構成要素での追い出し対象のトラックまたは論理ブロックに含まれる他の2つの構成要素内の有効クラスタおよびMS11内の有効クラスタが、DRAM20の作業領域に集められて、DRAM20の作業領域から1トラック分のデータとしてMSIB11aに書き込まれる。つぎに、本実施の形態の要部について説明する。前述したように、WC21の管理には、図10に示したWCクラスタ管理テーブル25と、図11に示したWCトラック管理テーブル24が使用される。WCクラスタ管理テーブル25は、前述したように、セットアソシアティブ方式でWC21の各エントリのタグをクラスタ単位に管理するためのテーブルであり、各タグに、通常の論理トラックアドレス25cの他に、複数ビットの状態フラグ25aと、セクタ位置ビットマップ25bとを追加している。また、WCトラック管理テーブル24は、前述したように、WC21上に格納されているクラスタをトラック単位でまとめた情報を管理するものであり、FIFO的な機能を有するリンクドリスト構造によって論理トラックアドレス間のWC21に登録された順序LRUを表現しており、各エントリには、当該論理トラックアドレスに含まれるWC21中の有効クラスタ数を示すWCクラスタ数24bと、WC21中で当該論理トラックアドレスに含まれる有効クラスタがWC21中のm×nのエントリ中のどのエントリに格納されているか示すWaylineビットマップ24cおよび次の論理トラックアドレスの位置を示すnextポインタ24dとが含まれる。WC21への書き込み処理が終了すると、WCトラック管理テーブル24においては、前述したように、該当する論理トラックアドレス24a、WCクラスタ数、way-lineビットマップ24cなどがデータ管理部120の論理NAND層120bによって更新されると共に、論理トラックアドレス間のWC21に登録された順序がリンクドリストのFIFO構造によって変更される。WC21への書き込みの際、前述したiの条件、すなわち最後の空きwayが使用されるという条件が成立した場合は、LRU順にリンクしているWCトラック管理テーブル24を検索することで、該当lineに登録されたトラックのうち、最も古く更新されたトラックを追い出し確定するが、この追い出しの際、追い出しを確定した同一トラックに含まれる全てのWC21内のクラスタを追い出し確定とする。WCトラック管理テーブル24のway-lineビットマップ24cには、当該論理トラックアドレスに所属する全てのクラスタがビットマップ形式で登録されているので、このway-lineビットマップ24cを参照することで、容易に、追い出すべき各クラスタのWC21での記憶位置を知ることができ、追い出し処理を高速化することができる。また、WRコマンド処理中に、前述したiiの条件、すなわちWC21に登録されているトラックの数異なる論理トラックアドレスの個数が所定数を超えるという条件が成立した場合は、LRU順で、当該トラックに属するWC中のクラスタ数が所定数未満のトラックの追い出しを確定するようにしているが、iiの条件は、WCトラック管理テーブル24に登録されたリストの個数、則ちWC21に登録されている論理トラックアドレス24aの個数を計数することで、簡単に導出することができる。また、iiの条件が成立した場合にも、追い出しを確定した同一トラックに含まれる全てのWC21内のクラスタを追い出し確定とするが、この追い出しの際にも、このway-lineビットマップ24cを参照することで、容易に、追い出すべき各クラスタのWC21での記憶位置を知ることができ、追い出し処理を高速化することができる。さらに、当該トラックに属するWC中のクラスタ数が所定数未満のトラックを検索する際には、WCトラック管理テーブル24のWCクラスタ数24bのフィールドを参照することで、容易かつ高速に該当トラックを決定することができる。追い出し処理がトリガされると、前述したように、その際追い出すのは同一トラックに含まれるWC21中の全クラスタであり、追い出されるクラスタ量がトラックサイズの50を超えていればMS11のMSIB11aへ、超えていなければFS12のFSIB12aへと追い出す。この追い出し先の判定にも、WCトラック管理テーブル24のWCクラスタ数24bのフィールドを参照することでWC21からの追い出し先を、FSIB12a、MSIB11aの何れにするかを容易に即座に決定することができ、追い出し処理を高速することができる。このように本実施の形態においては、WCトラック管理テーブル24によって、論理トラックアドレス間のWC21に登録された時間的順序、論理トラックアドレス内の有効クラスタ数、論理トラックアドレスに所属する各クラスタのWC21での記憶位置などを含む論理トラックアドレス毎の情報の管理を行うようにしているので、WC21での書き込み処理、追い出し処理を高速化することができ、またWC21の管理テーブルのためのメモリ量を削減することができる。また、本実施の形態においては、WRコマンド処理中に、最後の空きwayが使用された場合に、WC21での追い出しを行うようにしているので、wayが満杯になる前に追い出しが行われることになり、これにより書き込み処理の待ち時間が極端に長くなる状態がなくなり、書き込み処理の高速化に寄与する。また、本実施の形態においては、nwayのセットアソシアティブのキャッシュ構成において、WC21に登録されている論理トラックの数が所定数を超えた場合に、WCでの追い出しを行うようにしているので、登録される論理トラック数が増加して追い出し処理に時間がかかるようになる前に追い出しが行われることになり、これにより書き込み処理の待ち時間が極端に長くなる状態がなくなり、書き込み処理の高速化に寄与する。"