説明

メモリシステム

【課題】キャッシュメモリからフラッシュメモリへのデータ追い出しの処理時間を短縮化すること。
【解決手段】第2の記憶部の入力バッファとして機能する第1の入力バッファと、第3の記憶部の入力バッファとして機能する第2の入力バッファとを備え、コントローラは、第1の記憶部に書き込まれた複数のデータを第1、第2の入力バッファに追い出すキャッシュ追い出し処理と、第1、第2の入力バッファに書き込まれた複数のデータを、第2、第3の記憶部にそれぞれ追い出し、第2の記憶部に書き込まれた複数のデータを第2の入力バッファに追い出す追い出し処理および第3の記憶部内における第3の単位内の有効なデータを第4の単位で複数選択して第3の記憶部内の新たな第3の単位内に書き直すコンパクション処理を含むバッファ追い出し処理とに書き込みステージを分離する。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、不揮発性半導体メモリを備えたメモリシステムに関する。
【背景技術】
【0002】
コンピュータシステムに用いられる外部記憶装置として、NAND型フラッシュメモリなどの不揮発性半導体メモリを搭載したSSD(Solid State Drive)が注目されている。フラッシュメモリは、磁気ディスク装置に比べ、高速、軽量などの利点を有している。
【0003】
SSD内には、複数のフラッシュメモリチップ、ホスト装置からの要求に応じて各フラッシュメモリチップのリード/ライト制御を行うコントローラ、各フラッシュメモリチップとホスト装置との間でデータ転送を行うためのバッファメモリ、電源回路、ホスト装置に対する接続インタフェースなどを備えている(例えば、特許文献1)。
【0004】
不揮発性半導体メモリには、NAND型フラッシュメモリのように、データを記憶させる場合にブロック単位で一度データを消去してからその後に書き込みを行うもの、ページ単位で書き込み/読み出しを行うものなど、消去/書き込み/読み出しの単位が固定されているものがある。
【0005】
一方、パーソナルコンピュータなどのホスト機器がハードディスクをはじめとする2次記憶装置に対してデータの書き込み/読み出しを行う単位は、セクタと呼ばれる。セクタは、半導体記憶装置の消去/書き込み/読み出しの単位とは独立に定められる。
【0006】
例えば、不揮発性半導体メモリのブロックの大きさ(ブロックサイズ)は、512kB、ページの大きさ(ページサイズ)は、4kBであるのに対して、ホスト機器のセクタの大きさ(セクタサイズ)は、512Bのように定められている。
【0007】
このように、不揮発性半導体メモリの消去/書き込み/読み出しの単位は、ホスト機器の書き込み/読み出しの単位よりも大きい場合がある。
【0008】
そこで、不揮発性半導体メモリを用いてハードディスクのようなパーソナルコンピュータの2次記憶装置を構成する場合、ホスト機器としてのパーソナルコンピュータからの小さなサイズのデータは、不揮発性半導体メモリのブロックサイズ、ページサイズに適合させて書き込みを行う必要がある。
【0009】
また、パーソナルコンピュータなどのホスト機器が記録するデータは、時間的局所性、及び領域的局所性を兼ね備えている(例えば、非特許文献1参照。)。そのため、データを記録する際に外部から指定されたアドレスにそのまま記録していくと、特定の領域に短時間に書き換え、すなわち消去処理が集中し、消去回数の偏りが大きくなる。そのため、NAND型フラッシュメモリでは、データ更新箇所を均等に分散させるウェアレベリングと呼ばれる処理が行われる。
【0010】
ウェアレベリング処理では、例えば、ホスト機器から指定される論理アドレスを、データ更新箇所が均等に分散された不揮発性半導体メモリの物理アドレスにアドレス変換している。
【0011】
また、フラッシュメモリとホスト装置との間に、キャッシュメモリを介在させて、フラッシュメモリでの書き込み回数(消去回数)を減らすように構成されたSSDが開示されている(例えば、特許文献2参照。)。キャッシュメモリにホスト装置からの書き込みが発生した際に、キャッシュメモリが満杯の場合は、キャッシュメモリからフラッシュメモリへのデータ追い出しを行ってから、キャッシュメモリにデータを書き込むことになる。
【0012】
また、上述したように、データの消去単位(ブロック)と、データの管理単位が異なる場合、フラッシュメモリの書き換えが進むと、無効な(最新ではない)データによって、ブロックは穴あき状態になる。このような穴あき状態のブロックが増えると、実質的に使用可能なブロックが少なくなり、フラッシュメモリの記憶領域を有効利用できないので、有効な最新のデータを集めて、違うブロックに書き直すコンパクションと呼ばれる処理が行われる(例えば、特許文献3参照。)。
【0013】
このように、キャッシュメモリからフラッシュメモリへのデータ追い出しが発生した際に、フラッシュメモリが穴あき状態にある場合は、コンパクションなどの処理を行ってフラッシュメモリの記憶領域を良好な状態にした後、キャッシュメモリからフラッシュメモリへのデータ追い出しを行うことが考えられる。しかしながら、コンパクション処理などに時間がかかる場合は、キャッシュメモリからフラッシュメモリへのデータ追い出し処理を待たせなくてはならず、この問題を解決するために有効な手法が求められている。
【0014】
【特許文献1】特許第3688835号公報
【特許文献2】特表2007−528079号公報
【特許文献3】特開平8−279295号公報
【非特許文献1】David A. Patterson and John L. Hennessy, “Computer Organization and Design: The Hardware/Software Interface”, Morgan Kaufmann Pub, 2004/8/31
【発明の開示】
【発明が解決しようとする課題】
【0015】
本発明は、キャッシュメモリからフラッシュメモリへのデータ追い出しの処理時間を短縮化することが可能なメモリシステムを提供する。
【課題を解決するための手段】
【0016】
本願発明の一態様に係るメモリシステムは、ホスト装置に対し第1の単位で読み出し/書き込みが行われる揮発性の半導体記憶素子から構成されるキャッシュメモリとしての第1の記憶部と、第2の単位で読み出し/書き込みが行われ、前記第2の単位の2以上の自然数倍である第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第2の記憶部と、前記第3の単位の2以上の自然数分の1である第4の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第3の記憶部と、ホスト装置からの前記第1の単位からなる複数のデータを前記第1の記憶部に書き込む第1の処理と、前記第1の記憶部に書き込まれた複数のデータを前記第2の記憶部に追い出す第2の処理と、前記第1の記憶部に書き込まれた複数のデータを前記第4の単位で前記第3の記憶部に追い出す第3の処理と、前記第2の記憶部に書き込まれた複数のデータを第4の単位で第3の記憶部に追い出す第4の処理とを実行するコントローラとを備えるメモリシステムであって、前記第2の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第2の記憶部の入力バッファとして機能する第1の入力バッファと、前記第4の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第3の記憶部の入力バッファとして機能する第2の入力バッファとをさらに備え、前記コントローラは、前記第1〜第4の処理を、前記第1の記憶部に書き込まれた複数のデータを前記第1、第2の入力バッファに追い出すキャッシュ追い出し処理と、前記第1、第2の入力バッファに書き込まれた複数のデータを、第2、第3の記憶部にそれぞれ追い出し、前記第2の記憶部に書き込まれた複数のデータを第2の入力バッファに追い出す追い出し処理および前記第3の記憶部内における第3の単位内の有効なデータを第4の単位で複数選択して第3の記憶部内の新たな第3の単位内に書き直すコンパクション処理を含むバッファ追い出し処理とに分離したことを特徴とする。
【発明の効果】
【0017】
本発明によれば、キャッシュメモリからフラッシュメモリへのデータ追い出しの処理時間を短縮化することが可能なメモリシステムを提供できる。
【発明を実施するための最良の形態】
【0018】
以下に添付図面を参照して、この発明にかかるメモリシステムの最良な実施の形態を詳細に説明する。
【0019】
(実施の形態)
【0020】
以下、本発明の実施の形態について図面を参照して説明する。なお、以下の説明において、同一の機能および構成を有する要素については、同一符号を付し、重複説明は必要な場合にのみ行う。
【0021】
先ず、本明細書で用いる用語について定義しておく。
・物理ページ: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の実施形態]
【0022】
図1は、SSD(Solid State Drive)100の構成例を示すブロック図である。SSD100は、ATAインタフェース(ATA I/F)2などのメモリ接続インタフェースを介してパーソナルコンピュータあるいはCPUコアなどのホスト装置1と接続され、ホスト装置1の外部メモリとして機能する。また、SSD100は、RS232Cインタフェース(RS232C I/F)などの通信インタフェース3を介して、デバッグ用/製造検査用機器200との間でデータを送受信することができる。SSD100は、不揮発性半導体メモリとしてのNAND型フラッシュメモリ(以下、NANDメモリと略す)10と、コントローラとしてのドライブ制御回路4と、揮発性半導体メモリとしてのDRAM20と、電源回路5と、状態表示用のLED6と、ドライブ内部の温度を検出する温度センサ7と、フューズ8とを備えている。
【0023】
電源回路5は、ホスト装置1側の電源回路から供給される外部直流電源から複数の異なる内部直流電源電圧を生成し、これら内部直流電源電圧をSSD100内の各回路に供給する。また、電源回路5は、外部電源の立ち上がりまたは立ち下がりを検知し、パワーオンリセット信号を生成して、ドライブ制御回路4に供給する。フューズ8は、ホスト装置1側の電源回路とSSD100内部の電源回路5との間に設けられている。外部電源回路から過電流が供給された場合フューズ8が切断され、内部回路の誤動作を防止する。
【0024】
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の容量を有することになる。
【0025】
DRAM20は、ホスト装置1とNANDメモリ10間でのデータ転送用キャッシュおよび作業領域用メモリとして機能する。また、DRAM20の代わりに、FeRAMを使用しても良い。ドライブ制御回路4は、ホスト装置1とNANDメモリ10との間でDRAM20を介してデータ転送制御を行うとともに、SSD100内の各構成要素を制御する。また、ドライブ制御回路4は、状態表示用LED6にステータス表示用信号を供給するとともに、電源回路5からのパワーオンリセット信号を受けて、リセット信号およびクロック信号を自回路内およびSSD100内の各部に供給する機能も有している。
【0026】
各NANDメモリチップは、データ消去の単位である物理ブロックを複数配列して構成されている。図2(a)は、NANDメモリチップに含まれる1個の物理ブロックの構成例を示す回路図である。各物理ブロックは、X方向に沿って順に配列された(p+1)個のNANDストリングを備えている(pは、0以上の整数)。(p+1)個のNANDストリングにそれぞれ含まれる選択トランジスタST1は、ドレインがビット線BL0〜BLpに接続され、ゲートが選択ゲート線SGDに共通接続されている。また、選択トランジスタST2は、ソースがソース線SLに共通接続され、ゲートが選択ゲート線SGSに共通接続されている。
【0027】
各メモリセルトランジスタMTは、半導体基板上に形成された積層ゲート構造を備えたMOSFET(Metal Oxide Semiconductor Field Effect Transistor)から構成される。積層ゲート構造は、半導体基板上にゲート絶縁膜を介在して形成された電荷蓄積層(浮遊ゲート電極)、および電荷蓄積層上にゲート間絶縁膜を介在して形成された制御ゲート電極を含んでいる。メモリセルトランジスタMTは、浮遊ゲート電極に蓄えられる電子の数に応じて閾値電圧が変化し、この閾値電圧の違いに応じてデータを記憶する。メモリセルトランジスタMTは、1ビットを記憶するように構成されていてもよいし、多値(2ビット以上のデータ)を記憶するように構成されていてもよい。
【0028】
また、メモリセルトランジスタMTは、浮遊ゲート電極を有する構造に限らず、MONOS(Metal-Oxide-Nitride-Oxide-Silicon)型など、電荷蓄積層としての窒化膜界面に電子をトラップさせることでしきい値調整可能な構造であってもよい。MONOS構造のメモリセルトランジスタMTについても同様に、1ビットを記憶するように構成されていてもよいし、多値(2ビット以上のデータ)を記憶するように構成されていてもよい。
【0029】
各NANDストリングにおいて、(q+1)個のメモリセルトランジスタMTは、選択トランジスタST1のソースと選択トランジスタST2のドレインとの間に、それぞれの電流経路が直列接続されるように配置されている。すなわち、複数のメモリセルトランジスタMTは、隣接するもの同士で拡散領域(ソース領域若しくはドレイン領域)を共有するような形でY方向に直列接続される。
【0030】
そして、最もドレイン側に位置するメモリセルトランジスタMTから順に、制御ゲート電極がワード線WL0〜WLqにそれぞれ接続されている。従って、ワード線WL0に接続されたメモリセルトランジスタMTのドレインは選択トランジスタST1のソースに接続され、ワード線WLqに接続されたメモリセルトランジスタMTのソースは選択トランジスタST2のドレインに接続されている。
【0031】
ワード線WL0〜WLqは、物理ブロック内のNANDストリング間で、メモリセルトランジスタMTの制御ゲート電極を共通に接続している。つまり、ブロック内において同一行にあるメモリセルトランジスタMTの制御ゲート電極は、同一のワード線WLに接続される。この同一のワード線WLに接続される(p+1)個のメモリセルトランジスタMTは1ページ(物理ページ)として取り扱われ、この物理ページごとにデータの書き込みおよびデータの読み出しが行われる。
【0032】
また、ビット線BL0〜BLpは、ブロック間で、選択トランジスタST1のドレインを共通に接続している。つまり、複数のブロック内において同一列にあるNANDストリングは、同一のビット線BLに接続される。
【0033】
図2(b)は、例えば、1個のメモリセルトランジスタMTに2ビットの記憶を行う4値データ記憶方式でのしきい値分布を示す模式図である。4値データ記憶方式では、上位ページデータ“x”と下位ページデータ“y”で定義される4値データ“xy”の何れか1つをメモリセルトランジスタMTに保持可能である。
【0034】
この、4値データ“xy”は、メモリセルトランジスタMTのしきい値電圧の順に、例えば、データ“11”、“01”、“00”、“10”が割り当てられる。データ“11”は、メモリセルトランジスタMTのしきい値電圧が負の消去状態である。
【0035】
下位ページ書き込み動作においては、データ“11”(消去状態)のメモリセルトランジスタMTに対して選択的に、下位ビットデータ“y”の書き込みによって、データ“10”が書き込まれる。上位ページ書き込み前のデータ“10”のしきい値分布は、上位ページ書き込み後のデータ“01”とデータ“00”のしきい値分布の中間程度に位置しており、上位ページ書き込み後のしきい値分布よりブロードであってもよい。上位ページ書き込み動作においては、データ“11”のメモリセルと、データ“10”のメモリセルに対して、それぞれ選択的に上位ビットデータ“x”の書き込みが行われて、データ“01”およびデータ“00”が書き込まれる。
【0036】
図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が接続されている。
【0037】
第2の回路制御用バス103は、第1の回路制御用バス102に接続されている。第2の回路制御用バス103には、図1に示した温度センサ7からのデータを受けるためのIC回路108、状態表示用LED6にステータス表示用信号を供給するパラレルIO(PIO)回路109、RS232C I/F3を制御するシリアルIO(SIO)回路110が接続されている。
【0038】
ATAインタフェースコントローラ(ATAコントローラ)111、第1のECC(Error Checking and Correction)回路112、NANDコントローラ113、およびDRAMコントローラ114は、データアクセス用バス101と第1の回路制御用バス102との両方に接続されている。ATAコントローラ111は、ATAインタフェース2を介してホスト装置1との間でデータを送受信する。データアクセス用バス101には、データ作業領域作業領域およびファームウェア展開領域として使用されるSRAM115がSRAMコントローラ116を介して接続されている。NANDメモリ10に記憶されているファームウェアは起動時、ブートROM105に記憶されたブート用プログラムによってSRAM115に転送される。
【0039】
NANDコントローラ113は、NANDメモリ10とのインタフェース処理を行うNAND I/F117、第2のECC回路118、およびNANDメモリ10−DRAM20間のアクセス制御を行うDMA転送制御用DMAコントローラ119を備えている。第2のECC回路118は第2の訂正符号のエンコードを行い、また、第1の誤り訂正符合のエンコードおよびデコードを行う。第1のECC回路112は、第2の誤り訂正符号のデコードを行う。第1の誤り訂正符号、第2の誤り訂正符号は、例えば、ハミング符号、BCH(Bose Chaudhuri Hocqenghem)符号、RS(Reed Solomon)符号、或いはLDPC(Low Density Parity Check)符号等であり、第2の誤り訂正符号の訂正能力は、第1の誤り訂正符号の訂正能力よりも高いとする。
【0040】
図1および図3に示したように、NANDメモリ10においては、4つの並列動作要素10a〜10dが各8ビットの4チャネル(4ch)を介して、ドライブ制御回路4内部のNANDコントローラ112に並列接続されている。4つの並列動作要素10a〜10dを単独動作させるか、並列動作させるか、NANDメモリチップの備える倍速モード(Multi Page Program / Multi Page Read / Multi Block Erase)を使用するか否か、という組み合わせにより、下記3種類のアクセスモードが提供される。
(1)8ビットノーマルモード
1chだけ動作させ、8ビット単位でデータ転送を行うモードである。物理ページサイズ(4kB)で書き込み/読み出しが行われる。また、物理ブロックサイズ(512kB)で消去が行われる。1つの物理ブロックに対して1つの論理ブロックが対応付けられ、論理ブロックサイズは512kBとなる。
(2)32ビットノーマルモード
4ch並列で動作させ、32ビット単位でデータ転送を行うモードである。物理ページサイズ×4(16kB)で書き込み/読み出しが行われる。また、物理ブロックサイズ×4(2MB)で消去が行われる。4つの物理ブロックに対して1つの論理ブロックが対応付けられ、論理ブロックサイズは2MBとなる。
(3)32ビット倍速モード
4ch並列で動作させ、更に、NANDメモリチップの倍速モードを利用して書き込み/読み出しを行うモードである。物理ページサイズ×4×2(32kB)で書き込み/読み出しが行われる。また、物理ブロックサイズ×4×2(4MB)で消去が行われる。8つの物理ブロックに対して1つの論理ブロックが対応付けられ、論理ブロックサイズは4MBとなる。
【0041】
4ch並列動作する32ビットノーマルモードまたは32ビット倍速モードでは、並列動作する4または8物理ブロックが、NANDメモリ10としての消去単位となり、並列動作する4または8物理ページが、NANDメモリ10としての書き込み単位および読み出し単位となる。以下の動作では、基本的に32ビット倍速モードを使用し、例えば、1論理ブロック=4MB=2トラック=2ページ=2クラスタ=2セクタとして説明する(i、j、k、lは自然数、かつ、i<j<k<lの関係が成立する)。
【0042】
32ビット倍速モードでアクセスされる論理ブロックは4MB単位であり、8個(2×4ch)の物理ブロック(1物理ブロック=512KB)が対応付けられている。物理ブロック単位で管理されるバッドブロックBBが発生すると、そのバッドブロックBBは使用不可になるので、そのようなときには、論理ブロックに対応付けられた8個の物理ブロックの組み合わせが、バッドブロックBBを含まないように変更される。
【0043】
図4は、プロセッサ104により実現されるファームウェアの機能構成例を示すブロック図である。プロセッサ104により実現されるファームウェアの各機能は、大きく、データ管理部120、ATAコマンド処理部121、セキュリティ管理部122、ブートローダ123、初期化管理部124、デバッグサポート部125に分類される。
【0044】
データ管理部120は、NANDコントローラ112、第1のECC回路114を介して、NANDメモリ10−DRAM20間のデータ転送、NANDメモリ10に関する各種機能を制御する。ATAコマンド処理部121は、ATAコントローラ110、およびDRAMコントローラ113を介して、データ管理部120と協動してDRAM20−ホスト装置1間のデータ転送処理を行う。セキュリティ管理部122は、データ管理部120およびATAコマンド処理部121と協動して各種のセキュリティ情報を管理する。
【0045】
ブートローダ123は、パワーオン時、各管理プログラム(ファームウェア)をNANDメモリ10からSRAM120にロードする。初期化管理部124は、ドライブ制御回路4内の各コントローラ/回路の初期化を行う。デバッグサポート部125は、外部からRS232Cインタフェースを介して供給されたデバッグ用データを処理する。主に、データ管理部120、ATAコマンド処理部121、およびセキュリティ管理部122が、SRAM114に記憶される各管理プログラムをプロセッサ104が実行することによって実現される機能部である。
【0046】
本実施形態では、主としてデータ管理部120が実現する機能について説明する。データ管理部120は、ATAコマンド処理部121が記憶デバイスであるNANDメモリ10やDRAM20に対して要求する機能の提供(ホスト装置からのWrite要求、Cache Flush要求、Read要求等の各種コマンドへの応答)と、アドレス領域とNANDメモリ10との対応関係の管理および管理情報の保護と、DRAM10およびNANDメモリ10を利用した高速で効率の良いデータ読み出し/書き込み機能の提供、NANDメモリ10の信頼性の確保などを行う。
【0047】
図5は、NANDメモリ10およびDRAM20内に形成された機能ブロックを示すものである。ホスト1とNANDメモリ10との間には、DRAM20上に構成されたライトキャッシュ(WC)21およびリードキャッシュ(RC)22が介在している。WC21はホスト装置1からのWriteデータを一時保存し、RC22はNANDメモリ10からのReadデータを一時保存する。NANDメモリ10内の論理ブロックは、書き込み時のNANDメモリ10に対する消去の量を減らすために、データ管理部120により、前段ストレージ領域(FS:Front Storage)12、中段ストレージ領域(IS:Intermediate Storage)13およびメインストレージ領域(MS:Main Storage)11という各管理領域に割り当てられている。FS12は、WC21からのデータを「小さな単位」であるクラスタ単位に管理するものであり、小データを短期間保存する。IS13は、FS12から溢れたデータを「小さな単位」であるクラスタ単位に管理するものであり、小データを長期間保存する。MS11は、WC21、FS12、IS13からのデータを「大きな単位」であるトラック単位で長期間記憶する。例えば、記憶容量は、MS>IS、FS>WCの関係となる。
【0048】
小さな管理単位を、NANDメモリ10の記憶領域全てに適用すると、後述する管理テーブルのサイズが肥大化し、DRAM20に収まらないので、小さな管理単位で管理するのは、最近書き込まれたばかりのデータと、NANDメモリ10への書き込み効率が悪い小さなデータのみとするようにNANDメモリ10の各ストレージを構成している。
【0049】
図6は、WC21からNANDメモリ10への書き込み処理(WR処理)に係わるより詳細な機能ブロック図を示すものである。FS12の前段には、WC21からのデータをバッファリングするFSインプットバッファ(FSIB)12aが設けられている。また、MS11の前段には、WC21、FS12、またはIS13からのデータをバッファリングするMSインプットバッファ(MSIB)11aが設けられている。また、MS11には、トラック前段ストレージ領域(TFS)11bが設けられている。TFS11bは、MSIB11aとMS11の間に介在するFIFO(First in First out)構造を有するバッファであり、TFS11bに記録されたデータは、MSIB11aから直接MS11に書き込まれるデータよりも更新頻度が高いデータである。MS11、MSIB11a、TFS11b、FS12、FSIB12a、およびIS13には、NANDメモリ10内の各論理ブロックの何れかが割り当てられている。
【0050】
つぎに、図5、図6の各構成要素の具体的な機能構成について詳述する。ホスト装置1はSSD100対し、ReadまたはWriteする際には、ATAインタフェースを介して論理アドレスとしてのLBA(Logical Block Addressing)を入力する。LBAは、図7に示すように、セクタ(サイズ:512B)に対して0からの通し番号をつけた論理アドレスである。本実施の形態においては、図5の各構成要素であるWC21、RC22、FS12、IS13、MS11の管理単位として、LBAの下位(l−k+1)ビット目から上位のビット列で構成される論理クラスタアドレスと、LBAの下位(l−i+1)ビットから上位のビット列で構成される論理トラックアドレスとを定義する。1クラスタ=2(l−k)セクタで、1トラック=2(k−i)クラスタである。
【0051】
・リードキャッシュ(RC)22
RC22について説明する。RC22は、ATAコマンド処理部121からのRead要求に対して、NANDメモリ10(FS12、IS13、MS11)からのReadデータを一時的に保存するための領域である。RC22は、本実施形態では例えば、m-line、n-way(mは2(k−i)以上の自然数、nは2以上の自然数)セットアソシアティブ方式で管理されており、1エントリに1クラスタ分のデータを保持できる。論理クラスタアドレスのLSB(k−i)ビットでlineが決定される。なお、RC22は、フルアソシアティブ方式で管理されていても良いし、単純なFIFO方式で管理されていてもよい。
【0052】
・ライトキャッシュ(WC)21
WC21について説明する。WC21は、ATAコマンド処理部121からのWrite要求に対して、ホスト装置1からのWriteデータを一時的に保存するための領域である。m-line、n-way(mは2(k−i)以上の自然数、nは2以上の自然数)セットアソシアティブ方式で管理されており、1エントリに1クラスタ分のデータを保持できる。論理クラスタアドレスのLSB(k−i)ビットでlineが決定される。例えば、way1〜waynの順で書き込み可能なwayが検索される。また、WC21に登録されているトラックは最も古く更新された順が分かるように後述するWCトラック管理テーブル24のFIFO構造によってLRU(Least Recently Used)で管理される。なお、WC21は、フルアソシアティブ方式で管理されていても良い。また、WC21は、RC22とline数、way数が互いに異なっていてもよい。
【0053】
Write要求により書き込まれたデータは、一旦WC21上に格納される。WC21からNANDメモリ10へ追い出すデータの決定方法は以下のルールに従う。
(i)タグによって決定されたlineの書き込み可能なwayが最後の(本実施形態では、n個目の)空きwayだった場合、則ち最後の空きwayが使用される場合は、そのlineに登録されたトラックのうち、LRUに基づいて最も古く更新されたトラックを追い出し確定する。
(ii)WC21に登録されている異なるトラックの個数が所定数を超えた場合、LRU順で、当該トラックに属するWC中のクラスタ数が所定数未満のトラックの追い出しを確定する。
【0054】
以上の方針で追い出すトラックを決定する。その際、追い出すのは同一トラックに含まれる全てのデータであり、追い出されるデータ量が、例えばトラックサイズの50%を超えていればMS11へ、超えていなければFS12へ追い出す。
【0055】
さらに(i)の条件でトラック追い出しが発生した場合で、MS11へ追い出す場合は、追い出されるトラック数が2個(もともと2個以上のときは2i+1個)になるまで、WC21内のトラックのうち上記追い出されるデータ量がトラックサイズの50%を超えるという条件を満たすトラックを上記(i)のポリシーで選択して追い出し候補に追加する。別言すれば、追い出されるトラックが2個未満の場合、WC中のトラックの古いものから2個になるまで、2(k−i−1)個以上有効クラスタをもつトラックを選択して追い出し候補に追加する。
【0056】
また、(i)の条件でトラック追い出しが発生した場合で、FS12に追い出す場合は、追い出されるクラスタ数が2個になるまでWC21内のトラックのうちLRU順に上記追い出されるデータ量がトラックサイズの50%未満であるという条件を満たすトラックを探してそのクラスタを追い出し候補に追加する。別言すれば、WC中のトラックを古い順に辿って2(k−i−1)個未満の有効クラスタしかもたないトラックからクラスタを取り出していき、有効クラスタ数が2(k−i−1)個になったら、それらクラスタをFSIB12aに論理ブロック単位で追い出しする。ただし、2(k−i−1)個見つからなかった場合は、FSIB12aに論理ページ単位で追い出しする。なお、FS12への追い出しを論理ブロック単位とするか、論理ページ単位とするかの有効クラスタ数の閾値は、2(k−i−1)個という1論理ブロック分の値にかぎるわけではなく、1論理ブロック分より若干少ない値であってもよい。
【0057】
また、ATAコマンド処理部121からのCache Flush要求では、WC21の内容が全て、上記と同じ条件(追い出されるデータ量がトラックサイズの50%を超えていればMS11へ、超えていなければFS12へ)で、FS12もしくはMS11に対して追い出される。
【0058】
・前段ストレージ領域(FS)12
つぎに、FS12について説明する。FS12はクラスタ単位でデータを管理されるFIFOである。FS12は、ここを通過しているデータは、後段のIS13よりも更新頻度が高いとみなすためのバッファである。すなわち、FS12のFIFO構造においては、FIFO中を通過中の有効クラスタ(最新クラスタ)は、ホストからの同じアドレスに対する再書き込みがあった場合無効化されるので、FS12を通過中のクラスタは、FS12からIS13やMS11に追い出されたクラスタよりも、更新頻度が高いとみなすことができる。
【0059】
FS12を設けることで、後段のIS13におけるコンパクション処理に更新頻度の高いデータが紛れ込む可能性を低減している。無効化によって古いクラスタを保持していた論理ブロック自体の持つ有効クラスタ数が0となった場合、その論理ブロックは開放され、フリーブロックFBに割り当てられる。また、論理ブロックが無効化された場合、新たなフリーブロックFBを取得し、FS12に割り当てる。
【0060】
WC21からFS12に対してクラスタデータの移動が発生すると、そのクラスタはFSIB12aに割り当てられた論理ブロックに対して書き込まれる。FSIB12a中に全てのページの書き込みが完了したブロックが存在する場合、後述するCIB処理によってそれらのブロックはFSIB12aからFS12にMoveされる。このFSIB12aからFS12へのMoveの際に、FS12のブロック数がFS12として許容される所定の上限値を超えると、最も古いブロックがFS12からIS13またはMS11に追い出されることになる。例えば、トラック内の有効クラスタの割合が50%以上のトラックは、MS11(TFS11b)への書き込みを行い、有効クラスタが残ったブロックを、IS13へMoveする。
【0061】
NANDメモリ10内の構成要素間のデータ移動には、MoveとCopyの二通りがある。Moveは、後述する管理テーブルのポインタの付け替えを行うだけで、実際のデータの書き換えは行わない方法である。Copyは、一方の構成要素に格納されているデータを、ページ単位、トラック単位、ブロック単位で他方の構成要素に実際に書き換える方法である。
【0062】
・中段ストレージ領域(IS)13
つぎに、IS13について説明する。IS13は、FS13と同様にクラスタ単位でデータの管理が行われる。前述したように、IS13に格納されたデータは、更新頻度が低いデータとみなすことができる。FS12からIS13に対して論理ブロックの移動(Move)、すなわちFS12からの追い出しが発生すると、以前FS12の管理対象であった追い出し対象の論理ブロックはポインタの付け替えによりIS13の管理対象ブロックとなる。このFS12からIS13への論理ブロックの移動により、IS13のブロック数がIS13として許容される所定の上限値を超えると、すなわちIS内の書き込み可能なフリーブロックFBの数が閾値を下回ると、IS13からMS11へのデータ追い出しおよびコンパクション処理が実行され、IS13のブロック数は規定値に戻される。
【0063】
IS13では、トラック内の有効クラスタ数を使って以下のような、追い出し処理およびコンパクション処理を、実行する。
・トラックをトラック内の有効クラスタ数×有効クラスタ係数(トラックがMS11内で無効トラックが存在する論理ブロックに存在するか否かによって重み付けされる数であり、存在したほうが存在しない場合より数が大きい)順にソートし、積の値が大きいトラック2i+1個(2論理ブロック分)を集めて論理ブロックサイズの自然数倍にしてMSIB11aに追い出す。
・有効クラスタ数が最も少ない2つの論理ブロックの合計有効クラスタ数が例えば、所定の設定値である2個(1論理ブロック分)以上ある場合は、上のステップを繰り返す(IS内の2つの論理ブロックから、フリーブロックFBを作れるようになるまで行うため)。
・有効クラスタ数の少ない論理ブロックから順にクラスタを2個集め、IS13内でコンパクションを行う。
なお、ここでは有効クラスタ数が最も少ない2つの論理ブロックを選択するとしたが、この数は2つに限定されず、2つ以上の数であればよい。また、所定の設定値は、選択する論路ブロック数よりも1つ少ない論理ブロック数に収容可能なクラスタ数以下であればよい。
【0064】
・メインストレージ領域(MS)11
つぎに、MS11について説明する。MS11はトラック単位でデータの管理を行う。MS11に格納されたデータは、更新頻度が低いとみなすことができる。WC21、FS12、IS13からMS11に対してトラックデータのCopyまたはMoveが発生すると、そのトラックはMSIS11aに割り当てられた論理ブロックに対して書き込まれる。一方で、トラック中の一部のデータ(クラスタ)のみがWC等から書き込まれるような場合には、既存のMS中のトラックデータと新しいデータをマージして新しいトラックデータを作った上でMSIB11aに書き込む、後述する受動マージが行われる。MS11内に無効トラックが蓄積し、MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を越えるような状況が発生すると、コンパクション処理を行って、無効なフリーブロックFBを作る。
【0065】
MS11のコンパクション処理は、例えば、論理ブロック内の有効トラック数のみに注目した以下の方法を実施する。
・有効トラックが少ない論理ブロックから順番に、無効トラックを合わせることによって無効なフリーブロックFBが作れるようになるまで選択する。
・選択した論理ブロックに収容されたトラックを、WC21、FS12、IS13内のデータと統合する受動マージを行いながらコンパクションを実行する。
・2トラック統合できた論理ブロックは、TFS11bに出力し(2トラックMSコンパクション)、2トラックに満たない個数のトラックは、MSIB11aに出力して(2トラック未満コンパクション)、より多くの無効なフリーブロックFBを作る。
【0066】
TFS11bは、トラック単位でデータを管理されるFIFOである。TFS11bは、ここを通過しているデータは、後段のMS11よりも更新頻度が高いとみなすためのバッファである。すなわち、TFS11bのFIFO構造においては、FIFO中を通過中の有効トラック(最新トラック)は、ホストからの同じアドレスに対する再書き込みがあった場合無効化されるので、TFS11bを通過中のトラックは、TFS11bからMS11に追い出されたトラックよりも、更新頻度が高いとみなすことができる。
【0067】
図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により管理される。
【0068】
RC22は、逆引きテーブルであるRCクラスタ管理テーブル23によって管理される。逆引きテーブルでは、記憶デバイスの位置からその位置に記憶されている論理アドレスを検索することができる。WC21は、逆引きテーブルであるWCクラスタ管理テーブル25および正引きテーブルであるWCトラック管理テーブル24によって管理される。正引きテーブルでは、論理アドレスからその論理アドレスに対応するデータが存在する記憶デバイス位置を検索することができる。
【0069】
NANDメモリ10内のFS12(FSIB12a)、IS13、MS11(TFS11b、MSIB11a)は、トラック管理テーブル30、FS/IS管理テーブル40、MS論理ブロック管理テーブル35、FS/IS論理ブロック管理テーブル42、FS/IS内クラスタ管理テーブル44によってその論理アドレスが管理される。また、NANDメモリ10内のFS12(FSIB12a)、IS13、MS11(TFS11b、MSIB11a)は、論物変換テーブル50によって論理アドレスと物理アドレスとの変換が行われる。これらの各管理テーブルは、NANDメモリ10上の領域に記憶されており、SSD100の初期化時にNANDメモリ10からDRAM20上に読み込まれて、使用される。
【0070】
・RCクラスタ管理テーブル23(逆引き)
まず、図9を用いてRCクラスタ管理テーブル23について説明する。RC22は、前述したように、論理クラスタアドレスLSB(k−i)ビットでインデックスされるn-wayセットアソシアティブ方式で管理されている。RCクラスタ管理テーブル23は、RC(クラスタサイズ×m-line×n-way)22の各エントリのタグを管理するためのテーブルであり、各タグは、複数ビットの状態フラグ23aと、論理トラックアドレス23bによって構成されている。状態フラグ23aには、当該エントリを使用しても良いか否か(有効/無効)を示すValidビットの他に、当該エントリがNANDメモリ10からの読み出し待ちか否かを示すビット、当該エントリがATAコマンド処理部121への読み出し待ちか否かを示すビットなどが含まれる。RCクラスタ管理テーブル23は、DRAM20上のタグ記憶位置からLBAに一致する論理トラックアドレスを検索する逆引きテーブルとして機能する。
【0071】
・WCクラスタ管理テーブル25(逆引き)
つぎに、図10を用いてWCクラスタ管理テーブル25について説明する。WC21は、前述したように、論理クラスタアドレスLSB(k−i)ビットでインデックスされるn-wayセットアソシアティブ方式で管理されている。WCクラスタ管理テーブル25は、WC(クラスタサイズ×m-line×n-way)21の各エントリのタグを管理するためのテーブルであり、各タグは、複数ビットの状態フラグ25aと、セクタ位置ビットマップ25bと、論理トラックアドレス25cによって構成されている。
【0072】
状態フラグ25aには、当該エントリを使用しても良いか否か(有効/無効)を示すValidビットの他に、当該エントリがNANDメモリ10への追い出し待ちか否かを示すビット、当該エントリがATAコマンド処理部からの書き込み待ちか否かを示すビットなどが含まれる。セクタ位置ビットマップ25bは、1クラスタに含まれる2(l−k)セクタのうちのどのセクタに有効なデータを保持しているかを2(l−k)ビットに展開して示すものである。このセクタ位置ビットマップ25bによって、WC21において、LBAと同じセクタ単位の管理を行うことができる。WCクラスタ管理テーブル25は、DRAM20上のタグ記憶位置からLBAに一致する論理トラックアドレスを検索する逆引きテーブルとして機能する。
【0073】
・WCトラック管理テーブル24(正引き)
つぎに、図11を用いてWCトラック管理テーブル24について説明する。WCトラック管理テーブル24は、WC21上に格納されているクラスタをトラック単位でまとめた情報を管理するものであり、FIFO的な機能を有するリンクドリスト構造によってトラック間のWC21に登録された順序(LRU)を表現している。なお、WC21で最後に更新された順序によってLRUを表現するようにしてもよい。各リストのエントリは、論理トラックアドレス24a、当該論理トラックアドレスに含まれるWC21中の有効クラスタ数24b、way-lineビットマップ24cおよび次のエントリへのポインタを示すnextポインタ24dから構成されている。WCトラック管理テーブル24は、論理トラックアドレス24aから所要情報を得るので、正引きテーブルとして機能する。
【0074】
way-lineビットマップ24cは、WC21中で当該論理トラックアドレスに含まれる有効クラスタがWC21中のm×nのエントリ中のどのエントリに格納されているか示すマップ情報であり、有効クラスタが格納されているエントリではValidビットが”1”になっている。このway-lineビットマップ24cは、例えば、(1ビット(Valid)+log2nビット(n-way))×mビット(m-line)で構成されている。WCトラック管理テーブル24はリンクドリスト構造を有しており、WC21中に存在する論理トラックアドレスに関する情報のみがエントリされている。
【0075】
・トラック管理テーブル30(正引き)
つぎに、図12を用いてトラック管理テーブル30について説明する。トラック管理テーブル30は、論理トラックアドレス単位でMS11上の論理的なデータ位置を管理するためのテーブルであり、クラスタ単位でFS12やIS13にデータが保持されている場合には、それらに関する基本情報と、詳細情報へのポインタも保持している。論理トラックアドレス30aをインデックスとした配列形式で構成される。論理トラックアドレス30aをインデックスとした各エントリは、クラスタビットマップ30b、論理ブロックID30c+論理ブロック内トラック位置30d、クラスタテーブルポインタ30e、FSクラスタ数30f、ISクラスタ数30gなどの情報で構成されている。トラック管理テーブル30は、論理トラックアドレスをインデックスとして、その論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックID(記憶デバイス位置に対応)などの所要情報を得るので、正引きテーブルとして機能する。
【0076】
クラスタビットマップ30bは、1つの論理トラックアドレス範囲に属する2(k−i)個のクラスタをクラスタアドレス昇順に例えば8分割したビットマップであり、8個の各ビットは、2(k−i−3)個のクラスタアドレスに対応するクラスタがMS11に存在するか、FS12もしくはIS13に存在するかを示している。ビットが“0”の場合は、その検索対象のクラスタは確実にMS11内に存在することを示し、ビットが“1”の場合は、そのクラスタはFS12もしくはIS13に存在する可能性があることを示している。
【0077】
論理ブロックID30cは、当該論理トラックアドレスに対応する論理トラックが記憶されている論理ブロックIDを識別するための情報である。論理ブロック内トラック位置30dは、論理ブロックID30cで指定された論理ブロック中における当該論理トラックアドレス(30a)に対応するトラックの記憶位置を示すものである。1論理ブロックは最大2個の有効トラックで構成されるので、論理ブロック内トラック位置30dは、iビットで2個のトラック位置を識別する。
【0078】
クラスタテーブルポインタ30eは、リンクドリスト構造を有するFS/IS管理テーブル40の各リストの先頭エントリへのポインタである。クラスタビットマップ30bの検索で、当該クラスタがFS12/IS13に存在する可能性があることを示していた場合、クラスタテーブルポインタ30eを用いてFS/IS管理テーブル40の検索を実行する。FSクラスタ数30fは、FS12内に存在する有効クラスタ数を示している。ISクラスタ数30gは、IS13内に存在する有効クラスタ数を示している。
【0079】
・FS/IS管理テーブル40(正引き)
つぎに、図13を用いてFS/IS管理テーブル40について説明する。FS/IS管理テーブル40は、論理クラスタ単位でFS12(FSIB12aも含む)もしくはIS13に保持されているデータの位置を管理するためのテーブルである。図13に示すように、論理トラックアドレス毎に独立したリンクドリスト形式で構成され、各リストの先頭エントリへのポインタは、前述したように、トラック管理テーブル30のクラスタテーブルポインタ30eのフィールドに保持されている。図13では、2つの論理トラックアドレス分のリンクドリストが示されている。各エントリは、論理クラスタアドレス40a、論理ブロックID40b、論理ブロック内クラスタ位置40c、FS/ISブロックID40d、nextポインタ40eから構成されている。FS/IS管理テーブル40は、論理クラスタアドレス40aから、その論理クラスタアドレスに対応する論理クラスタが記憶されている論理ブロックID40b、論理ブロックン内クラスタ位置40c(記憶デバイス位置に対応)などの所要情報を得るので、正引きテーブルとして機能する。
【0080】
論理ブロックID40bは、当該論理クラスタアドレス40aに対応する論理クラスタが記憶されている論理ブロックIDを識別するための情報である。論理ブロック内クラスタ位置40cは、論理ブロックID40bで指定された論理ブロック中における当該論理クラスタアドレス40aに対応するクラスタの記憶位置を示すものである。1論理ブロックは最大2個の有効クラスタで構成されるので、論理ブロック内クラスタ位置40cは、kビットで2位置を識別する。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は、論理トラックアドレス毎にリンクされる同じリスト内の次のエントリへのポインタを示している。
【0081】
・MS論理ブロック管理テーブル35(逆引き)
つぎに、図14を用いてMS論理ブロック管理テーブル35について説明する。MS論理ブロック管理テーブル35は、MS11に用いられている論理ブロックに関する情報(どの論理トラックが記憶されているか、追記可能か等)を一元管理するためのテーブルである。なお、MS論理ブロック管理テーブル35には、FS12(FSIB12も含む)、IS13に所属する論理ブロックに関する情報も登録されている。MS論理ブロック管理テーブル35は、論理ブロックID35aをインデックスとした配列形式で構成され、エントリ数は128GBのNANDメモリ10の場合は、32Kエントリまで持つことができる。各エントリは、2トラック分のトラック管理ポインタ35b、有効トラック数35c、書き込み可能先頭トラック35d、Validフラグ35eから構成されている。このMS論理ブロック管理テーブル35は、記憶デバイス位置に対応する論理ブロックID35aから、この論理ブロックに記憶されている論理トラックアドレスなどの所要情報を得るので、逆引きテーブルとして機能する。
【0082】
トラック管理ポインタ35bは、論理ブロックID35aで指定される当該論理ブロック内の2個のトラック位置毎に対応する論理トラックアドレスを保持する。この論理トラックアドレスを用いて、論理トラックアドレスをインデックスとするトラック管理テーブル30を検索することができる。有効トラック数35cは、論理ブロックID35aで指定される当該論理ブロックに記憶されているトラックのうちの有効なものの個数(最大2個)を示している。書き込み可能先頭トラック位置35dは、論理ブロックID35aで指定される当該論理ブロックが追記中のブロックであった場合における追記可能なトラック先頭位置(0〜2−1、追記終了時は2)を示している。Validフラグ35eは、当該論理ブロックエントリがMS11(MSIB11aも含む)として管理されている場合に“1”である。
【0083】
・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から、この論理ブロックに記憶されている論理クラスタなどの所要情報を得るので、逆引きテーブルとして機能する。
【0084】
論理ブロックID42bには、MS論理ブロック管理テーブル35に登録された論理ブロックの中で、FS12(FSIB12も含む)、IS13に所属している論理ブロックに対応する論理ブロックIDが登録される。ブロック内クラスタテーブル42cには、論理ブロック中の各クラスタ位置にどの論理クラスタアドレスで指定される論理クラスタが記録されているかを示す後述するFS/IS内クラスタ管理テーブル44へのインデックスが登録される。有効クラスタ数42dは、FS/ISブロックID42aで指定される当該論理ブロックに記憶されているクラスタのうちの有効なものの個数(最大2個)を示している。書き込み可能先頭ページ位置42eは、FS/ISブロックID42aで指定される当該論理ブロックが追記中のブロックであった場合における追記可能な先頭ページ位置(0〜2−1、追記終了時は2)を示している。Validフラグ42fは、この論理ブロックエントリがFS12(FSIB12も含む)またはIS13として管理されている場合に“1”である。
【0085】
・FS/IS内クラスタ管理テーブル44(逆引き)
つぎに、図16を用いてFS/IS内クラスタ管理テーブル44について説明する。FS/IS内クラスタ管理テーブル44は、FS12もしくはIS13として利用されている論理ブロック中の各クラスタ位置にどの論理クラスタが記録されているのかを示すテーブルである。1論理ブロックあたり、2ページ×2(k−j)クラスタ=2個のエントリを持ち、当該論理ブロック内のクラスタ位置の0番目〜2−1番目に対応する情報が連続領域に配置される。さらにこの2個の情報を含むテーブルがFS12およびIS13に所属する論理ブロック数(P個)分だけ保持されており、FS/IS論理ブロック管理テーブル42のブロック内クラスタテーブル42cは、このP個のテーブルに対する位置情報(ポインタ)となっている。連続領域に配される各エントリ44aの位置は、1論理ブロック中のクラスタ位置を示し、また各エントリ44aの内容は、当該クラスタ位置にどの論理クラスタが記憶されているかが識別できるように、FS/IS管理テーブル40で管理される該当論理クラスタアドレスを含むリストへのポインタが登録されている。すなわち、エントリ44aは、リンクドリストの先頭を指し示すのではなく、リンクドリスト中の該当論理クラスタアドレスを含む1つのリストへのポインタが登録されている。
【0086】
・論物変換テーブル50(正引き)
つぎに、図17を用いて論物変換テーブル50について説明する。論物変換テーブル50は、論理ブロックID50aをインデックスとした配列形式で構成され、エントリ数は、128GBのNANDメモリ10の場合は、最大32Kエントリまで持つことができる。論物変換テーブル50は、論理ブロックIDと物理ブロックIDとの変換、寿命に関する情報を管理するためのテーブルである。各エントリは、物理ブロックアドレス50b、消去回数50c、読み出し回数50dから構成される。この論物変換テーブル50は、論理ブロックIDから物理ブロックID(物理ブロックアドレス)などの所要情報を得るので、正引きテーブルとして機能する。
【0087】
物理ブロックアドレス50bは、1つの論理ブロックID50aに所属する8個の物理ブロックID(物理ブロックアドレス)を示している。消去回数50cは、当該論理ブロックIDの消去回数を示している。バッドブロック(BB)管理は、物理ブロック(512KB)単位に行われるが、消去回数の管理は、32ビット倍速モードによる1論理ブロック(4MB)単位に管理される。読み出し回数50dは、当該論理ブロックIDの読み出し回数を示している。消去回数50cは、例えば、NAND型フラッシュメモリの書き換え回数を平準化するウェアレベリング処理で利用することが可能である。読み出し回数50dは、リテンション特性の劣化した物理ブロックに保持されるデータの再書き込みを行うリフレッシュ処理で利用することが可能である。
【0088】
図8に示した管理テーブルを管理対象毎にまとめると次のようになる。
RC管理:RCクラスタ管理テーブル
WC管理:WCクラスタ管理テーブル、WCトラック管理テーブル
MS管理:トラック管理テーブル30、MS論理ブロック管理テーブル35
FS/IS管理:トラック管理テーブル30、FS/IS管理テーブル40、MS論理ブロック管理テーブル35、FS/IS論理ブロック管理テーブル42、FS/IS内クラスタ管理テーブル44
【0089】
なお、MS構造管理テーブル(図示せず)において、MS11,MSIB11a、TFS11bを含めたMS領域の構造を管理しており、具体的には、MS11、MSIB11a、TFS11bに割り当てた論理ブロックなどを管理している。また、FS/IS構造管理テーブル(図示せず)において、FS12、FSIB12a、IS13を含めたFS/IS領域の構造を管理しており、具体的には、FS12、FSIB12a、IS13に割り当てた論理ブロックなどを管理している。
【0090】
・Read処理
つぎに、図18に示すフローチャートを参照して、読み出し処理について説明する。ATAコマンド処理部121から、Readコマンドおよび読み出しアドレスとしてのLBAが入力されると、データ管理部120は、図9に示したRCクラスタ管理テーブル23と図10に示したWCクラスタ管理テーブル25を検索する(ステップS100)。具体的には、LBAのクラスタアドレスのLSB(k−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)。
【0091】
データ管理部120は、RC22またはWC21でヒットしなかった場合は(ステップS110)、検索対象のクラスタがNANDメモリ10のどこに格納されているかを検索する。データ管理部120は、まず、図12に示したトラック管理テーブル30を検索する(ステップS120)。トラック管理テーブル30は、論理トラックアドレス30aでインデックスされているため、LBAで指定された論理トラックアドレスに一致する論理トラックアドレス30aのエントリだけをチェックする。
【0092】
まず、チェックしたいLBAの論理クラスタアドレスに基づいてクラスタビットマップ30bから対応するビットを選択する。対応するビットが“0”を示していれば、そのクラスタは確実にMS内に最新のデータが存在していることを意味する(ステップS130)。この場合は、このトラックが存在する論理ブロックIDおよびトラック位置を、同じ論理トラックアドレス30aのエントリ中の論理ブロックID30cと論理ブロック内トラック位置30dから得て、さらにLBAのクラスタアドレスのLSB(k−i)ビットを利用して、トラック位置からのオフセットを算出することで、NANDメモリ10内の当該クラスタアドレスに対応するクラスタデータが格納されている位置を算出することができる。具体的には、論理NAND層管理部120bでは、上記のようにしてトラック管理テーブル30から取得した論理ブロックID30cと論理ブロック内トラック位置30dと、LBAの論理クラスタアドレスのLSB(k−i)ビットを物理NAND層管理部120cに与える。
【0093】
物理NAND層管理部120cでは、論理ブロックID30cに対応する物理ブロックアドレス(物理ブロックID)を、論理ブロックIDをインデックスとしている図17に示す論物変換テーブル50から取得し(ステップS160)、さらに取得した物理ブロックID中のトラック位置(トラック先頭位置)を論理ブロック内トラック位置30dから算出し、さらにLBAのクラスタアドレスのLSB(k−i)ビットから、前記算出した物理ブロックID中のトラック先頭位置からのオフセットを算出することで、物理ブロック中のクラスタデータを取得することができる。NANDメモリ10のMS11から取得されたクラスタデータは、RC22を介してATAコマンド処理部121に送られる(ステップS180)。
【0094】
一方、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)。
【0095】
このFS/IS管理テーブル40の検索によって、検索対象のクラスタが存在しなかった場合は(ステップS150)、再度トラック管理テーブル30のエントリを検索してMS11上の位置を確定する(ステップS170)。
【0096】
・Write処理
つぎに、図19に示すフローチャートを参照して、書き込み処理について説明する。FUA(DRAMキャッシュをバイパスしてNANDへの直接書き込みを行う)でないWriteコマンドにより書き込まれたデータは必ず一旦WC21上に格納され、その後条件に応じてNANDメモリ10に対して書き込まれることになる。書き込み処理では、追い出し処理、コンパクション処理が発生する可能性がある。この実施の形態では、書き込み処理を、ライトキャッシュフラッシュ処理(以下WCF処理)と、クリーンインプットバッファ処理(以下CIB処理)との2ステージに大きく分割している。ステップS300からステップS320までは、ATAコマンド処理部121からのWrite要求からWCF処理までを示しており、ステップS330〜最終ステップまでがCIB処理を示している。
【0097】
WCF処理は、WC21にあるデータをNANDメモリ10(FS12のFSIB12aまたはMS11のMSIB11a)にcopyする処理であり、ATAコマンド処理部121からのWrite要求もしくはCache Flush要求単体は、この処理のみで完結することができる。これにより処理が開始されたATAコマンド処理部121のWrite要求の処理遅延を最大でもWC21の容量分のNANDメモリ10への書き込み時間に限定することができるようになる。
【0098】
CIB処理は、WCF処理によって書き込まれたFSIB12aのデータをFS12にMoveする処理と、WCF処理によって書き込まれたMSIB11aのデータをMS11にMoveする処理とを含む。CIB処理を開始すると、連鎖的にNANDメモリ10内の各構成要素(FS12、IS13、MS11など)間のデータ移動やコンパクション処理が発生する可能性があり、処理全体に要する時間は状態によって大きく変化する。
【0099】
まず、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のクラスタアドレスLSB(k−i)ビットから書き込み先のlineを決定し、決定したlineのn個のwayを検索する。決定したlineのn個のway中に、入力されたLBAと同じ論理トラックアドレス25cが格納されている場合は(ステップS305)、このエントリに上書きするのでこのエントリをクラスタ書き込み用に確保する(Valid(使用不可)→ATAからの書き込み待ち)。
【0100】
そして、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)。
【0101】
一方、決定した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)。
【0102】
また、書き込み可能な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)。
【0103】
以上の処理は、ATAコマンド処理部121からからの書き込み要求が入力された際に、追い出し処理をトリガしなくてもよい場合である。一方、この後の説明は、書き込み要求が入力された時点後に、追い出し処理をトリガする場合である。ステップS305において、決定したline中の書き込み可能なwayが最後のn個目のwayである場合は、前述したWC21からNANDメモリ10へ追い出すデータの決定方法の(i)の箇所で説明した条件、すなわち、
(i) タグによって決定されたlineの書き込み可能なwayが最後の(本実施形態では、n個目の)空きwayだった場合、則ち最後の空きwayが使用される場合は、そのlineに登録されたトラックのうちLRUに基づいて最も古く更新されたトラックを追い出し確定する
に基づいて追い出すトラックすなわちWC21内エントリを選択する。
【0104】
DRAM層管理部120aは、以上の方針で追い出すトラックを決定すると、前述したように、その際追い出すのは同一トラックに含まれるWC21中の全クラスタであり、追い出されるクラスタ量がトラックサイズの50%を超えていれば、すなわち追い出し確定トラックのうちWC中に有効クラスタ数が2(k−i−1)個以上ある場合は、MSIB11aへ追い出しを行い(ステップS310)、超えていなければ、すなわち追い出し確定トラックのうちWC中に有効クラスタ数が2(k−i−1)個未満である場合は、FSIB12aへと追い出す(ステップS315)。WC21からMSIB11aへの追い出し、WC21からFSIB12aへの追い出しの詳細は、後述する。選択された追い出しエントリの状態フラグ25aは、Valid(使用不可)からNANDメモリ10への追い出し待ちに移行される。
【0105】
この追い出し先の判定は、WCトラック管理テーブル24を用いて実行される。すなわち、WCトラック管理テーブル24には、論理トラックアドレス毎に、有効なクラスタ数を示すWCクラスタ数24bのエントリが登録されており、このWCクラスタ数24bのエントリを参照することでWC21からの追い出し先を、FSIB12a、MSIB11aの何れにするかを決定する。また、way−lineビットマップ24cに、当該論理トラックアドレスに所属する全てのクラスタがビットマップ形式で登録されているので、追い出しを行う際には、このway−lineビットマップ24cを参照することで、容易に、追い出すべき各クラスタのWC21での記憶位置を知ることができる。
【0106】
また、上記書き込み処理中または書き込み処理後、前述の下記条件、
(ii)WC21に登録されているトラックの数が所定数を超えた場合、
が成立した場合も、上記同様にしてNANDメモリ10への追い出し処理を実行する。
【0107】
WC→MSIB(Copy)
つぎに、上記有効クラスタ数(有効クラスタ数が2(k−i−1)個以上)に基づく判定によりWC21からMSIB11aへの追い出しが発生したときは、前述したように、次のような手順を実行する(ステップS310)。
1.WCクラスタ管理テーブル25を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ25bを参照し、セクタ位置ビットマップ25bが全て“1”でない場合は、NANDメモリ10に含まれる同一クラスタ中のセクタとマージする、後述のトラック内セクタ穴埋めを行う。また、トラック中のWC21内に存在しないクラスタについてはNANDメモリ10から読み出してマージする、受動マージ処理を実行する。
2.追い出し確定トラックが2個未満の場合、WC21中のトラックの古いものから2個になるまで2(k−i−1)個以上有効クラスタを持つ追い出し確定トラックを追加する。
3.Copyされるトラックが2個以上あれば、2個ずつを組として、MSIB11aに対して論理ブロック単位に書き込みを行う。
4.2個組みに出来なかったトラックをMSIB11aに対してトラック単位に書き込みを行う。
5.Copy終了後に既にFS、IS、MS上に存在していたクラスタ、トラックのうちコピーされたトラックに属するものを無効化する。
【0108】
このようなWC21からMSIB11aへのCopy処理に伴う各管理テーブルの更新処理について説明する。WCクラスタ管理テーブル25中の追い出されたトラックに所属するWC21中の全クラスタに対応するエントリ中の状態フラグ25aはInvalidとされ、この後これらエントリに対する書き込みが可能となる。また、WCトラック管理テーブル24中の追い出されたトラックに対応するリストについては、例えば直前のリストのnextポインタ24dが変更または削除されて、無効化される。
【0109】
一方、WC21からMSIB11aに対するトラック移動が発生すると、これに伴いトラック管理テーブル30およびMS論理ブロック管理テーブル35が更新される。まず、トラック管理テーブル30のインデックスである論理トラックアドレス30aを検索することで、移動されたトラックに対応する論理トラックアドレス30aが既に登録されているか否かを判定する。既に登録されている場合は、該当インデックスのクラスタビットマップ30b(MS11側への移動であるので、該当ビットを全て“0”にする)、論理ブロックID30c+論理ブロック内トラック位置30dのフィールドを更新する。移動されたトラックに対応する論理トラックアドレス30aが未登録の場合は、該当する論理トラックアドレス30aのエントリに対し、クラスタビットマップ30b、論理ブロックID30c+論理ブロック内トラック位置30dを登録する。また、トラック管理テーブル30の変更に応じて、MS論理ブロック管理テーブル35における、論理ブロックID35a、該当トラック管理ポインタ35b、有効トラック数35c、書き込み可能先頭トラック35dなどのエントリを必要に応じて更新する。
【0110】
なお、他の領域(FS12やIS13)等からMS11に対してトラック書き込みが発生した場合、もしくはMS11内部のコンパクション処理によるMS内トラック書き込みが発生した場合、書き込み対象のトラックに含まれるWC21内有効クラスタも同時にMSに書き込まれる。WC21からMS11への書き込みとしてこのような受動的マージも存在する。そのような受動的マージが行われた場合は、それらのクラスタはWC21上から削除(無効化)されることになる。
【0111】
WC→FSIB(Copy)
つぎに、上記有効クラスタ数(有効クラスタ数が2(k−i−1)個未満)に基づく判定によりWC21からFSIB12aへの追い出しが発生したときは、前述したように、次のような手順を実行する。
1.WCクラスタ管理テーブル25における追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ25bを参照し、セクタ位置ビットマップ25bが全て“1”でない場合は、NANDメモリ10に含まれる同一クラスタ中のセクタとマージする、クラスタ内セクタ穴埋めを行う。
2.WC内のトラックを古い順に辿って2(k−i−1)個未満の有効クラスタしか持たないトラックからクラスタを取り出して行き、有効クラスタ数が2個になったらそれら全クラスタをFSIB12aに論理ブロック単位に書き込む。
3.2個見つからなかった場合には、有効クラスタ数が2(k−i−1)個未満の全てのトラックを必要な論理ページ数分だけFSIB12aに書き込む。
4.Copy終了後に既にFS、IS上に存在していたクラスタのうちコピーされたのと同じものを無効化する。
【0112】
このような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の該当個所を更新する。
【0113】
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処理を別々に説明する。
【0114】
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のブロックは無効なトラックを含んだものが発生し、これが繰り返されるとブロックの利用効率が低下して、使用可能な論理ブロックに不足が生じることがある。
【0115】
データ管理部120は、このような事態が発生して、MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を越えるような状況が発生すると、コンパクション処理を行って、無効なフリーブロックFBを作る。無効なフリーブロックFBは、物理NAND層管理部120cに返却される。そして、論理NAND層管理部120bは、MS11に割り当てられている論理ブロックの個数を減らした後、新たに書き込み可能なフリーブロックFBを物理NAND層管理部120cから取得する。コンパクション処理とは、コンパクション対象の論理ブロックが持つ有効クラスタを新しい論理ブロックに集めたり、あるいはコンパクション対象の論理ブロック中の有効トラックを他の論理ブロックにCopyしたりすることで、物理NAND層管理部120cに返却する無効なフリーブロックFBを作り、論理ブロックの利用効率を向上させるための処理である。なお、コンパクションを行う際には、コンパクション対象となったトラック領域に対して、WC、FS、IS上の有効なクラスタが存在する場合、それらを全てマージする受動マージを実行する。また、TFS11bに登録されている論理ブロックについては、コンパクション対象に含めない。
【0116】
以下に、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論理ブロック分(2トラック)ずつCopyしてコンパクションを実施する。なお、コンパクション対象のトラックがWC21、FS12、IS13に有効クラスタを持つ場合にはそれらもマージする。
6.コンパクション元の論理ブロックを無効なフリーブロックFBとする。
7.コンパクションして有効な2トラックで構成された1論理ブロックができたら、TFS11bの先頭にMoveする。
8.論理ブロック内の有効トラックを他の論理ブロックにCopyして、無効なフリーブロックFBが作れる場合は、2トラック未満の個数の有効トラックをMSIB11aに対し、トラック単位で追記書き込みする。
9.コンパクション元の論理ブロックを無効なフリーブロックFBとする。
10.MS11に割り当てられている論理ブロックの個数がMS11として許容されるブロック数の上限値を下回ると、MSコンパクション処理を終了する。
【0117】
FS12のCIB処理
つぎに、FS12でのCIB処理について説明する(ステップS340)。WC21からFSIB12aへのクラスタ書き込み処理によって全ページ書き込み済みの論理ブロックがFSIB12a中に作られた場合、FSIB12a中のそれらのブロックは、FSIB12aからFS12に対してMoveされる。このMoveにともなって複数の論理ブロックで構成されるFIFO構造のFS12から古い論理ブロックが追い出される状況が発生する。
【0118】
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)。
【0119】
IS13のCIB処理
つぎに、IS13でのCIB処理について説明する(ステップS360)。上記したFS12からIS13へのブロック移動によって論理ブロックがIS13に追加されるが、これにともなって複数個の論理ブロックで構成されるIS13に対して管理可能なブロック数の上限を超えてしまう状況が発生する。このような状況が発生した場合、IS13では、まずMS11への1〜複数個の論理ブロックの追い出しを行った後、ISコンパクションを実行する。具体的には、次のような手順を実行する。
1.IS13に含まれるトラックをトラック内の有効クラスタ数×有効クラスタ係数でソートし、積の値が大きいトラック2i+1個(2論理ブロック分)を集めてMSIB11aに追い出す。
2.有効クラスタ数が最も少ない2i+1個の論理ブロックの合計有効クラスタ数が例えば、所定の設定値である2個(1論理ブロック分)以上ある場合は、上のステップを繰り返す。
3.上記の追い出しを行った後、有効クラスタ数の少ない論理ブロックから順にクラスタを2個集め、IS13内でコンパクションを行う。
4.コンパクション元の論理ブロックのうち有効クラスタがなくなったものを無効なフリーブロックFBとして返還する。
なお、IS13からMSIB11aへの追い出しが発生したときには、その直後、MS11での前述したCIB処理が実行される(ステップS370)。
【0120】
図20は、各構成要素間のデータの流れにおける入力と出力の組み合わせ、およびそのデータの流れが何をトリガとして発生するかを示すものである。FS12は、基本的には、WC21からのクラスタ追い出しによってデータが書き込まれるが、WC21からFS12への追い出しに付随してクラスタ内セクタ穴埋め(クラスタ穴埋め)が必要な場合は、FS12、IS13、MS11からのデータがコピーされる。WC21では、WCクラスタ管理テーブル25のタグ中のセクタ位置ビットマップ25bによって当該クラスタアドレス中の2(l−k)個のセクタの有無を識別させることによってセクタ(512B)単位の管理をすることが可能である。これに対し、NANDメモリ10での機能要素であるFS12、IS13の管理単位はクラスタであり、MS11の管理単位は、トラックである。このように、NANDメモリ10での管理単位は、セクタより大きいため、WC21からNANDメモリ10に対して、データを書き込む際に、書き込まれるデータと同一クラスタアドレスのデータがNANDメモリ10中に存在する場合、WC21からNANDメモリ10に書き込まれるクラスタ中のセクタと、NANDメモリ10中に存在する同一クラスタアドレス内のセクタとをマージしてから、NANDメモリ10に書き込む必要がある。
【0121】
この処理が、図20に示したクラスタ内セクタ穴埋め処理(クラスタ穴埋め)と、トラック内セクタ穴埋め(トラック穴埋め)であり、これらの処理を行わないと、正しいデータが読み出せなくなる。そこで、WC21からFSIB12aまたはMSIB11aにデータを追い出す際には、WCクラスタ管理テーブル25を参照し、追い出しを行うクラスタに対応するタグ中のセクタ位置ビットマップ25bを参照し、セクタ位置ビットマップ25bが全て“1”でない場合は、NANDメモリ10に含まれる同一クラスタまたは同一トラック中のセクタとマージする、クラスタ内セクタ穴埋めまたはトラック内セクタ穴埋めを行う。この処理には、DRAM20の作業領域が使用され、DRAM20の作業領域からMSIB11aに書き込まれたり、FSIB12aに書き込まれたりする。
【0122】
IS13は、基本的には、FS12からのブロック追い出しによってデータが書き込まれる(Move)か、IS内部のコンパクションによってデータが書き込まれる。MS11は、全ての箇所からデータが書き込まれ得る。その際、MS11は、トラック単位にしかデータを書き込めないために、MS自身のデータによる穴埋めが発生しうる。また、トラック単位の書き込みを行う際には、他のブロックにある断片化されたデータも受動マージによって書き込まれることになる。さらにMS11は、MSコンパクションによる書き込みもある。なお、受動マージにおいては、WC21、FS12またはIS13の3つの構成要素のうちの1つの構成要素からMS11へのトラック追い出しまたは論理ブロック追い出し(2トラック分の追い出し)が発生した際、1つの構成要素での追い出し対象のトラック(または論理ブロック)に含まれる他の2つの構成要素内の有効クラスタおよびMS11内の有効クラスタが、DRAM20の作業領域に集められて、DRAM20の作業領域から1トラック分のデータとしてMSIB11aに書き込まれる。
【0123】
つぎに、本実施形態をより詳細に説明する。図21は、図6に示したNANDメモリ10の書き込み処理に係わるより詳細な機能構成を示すものである。重複する説明は、省略する。
【0124】
・FS構成
FS部12Qは、FSIB12aとFS12によって構成されている。FS12は、多数の論理ブロック分の容量を有し、論理ブロック単位でFIFO構造が管理されている。FS12の前段には、WC21から追い出されたデータが入力されるFSインプットバッファ(FSIB)12aが設けられている。FSIB12aは、FSフルブロックバッファ(FSFB)12aaと、FS追記バッファ(FS追記IB)12abとを備えている。FSFB12aaは、1〜複数個の論理ブロック分の容量を有し、またFS追記IB12abも1〜複数個の論理ブロック分の容量を有する。WC21からの追い出しデータが1論理ブロック分あればFSFB12aaに対する論理ブロック単位のデータコピーが行われ、そうでなければFS追記IB12abに対して論理ページ単位の追記書き込みが行われる。
【0125】
・IS構成
IS部13Qは、IS13と、ISインプットバッファ(ISIB)13aと、ISコンパクションバッファ13cによって構成されている。ISIB13aは、1〜複数個の論理ブロック分の容量を有し、ISコンパクションバッファ13cは例えば1論理ブロック分の容量を有し、IS13は、多数の論理ブロック分の容量を有する。IS13は、例えば、論理ブロック単位で、FS12と同様、FIFO構造が管理されている。ISコンパクションバッファ13cは、IS部13Qでのコンパクションを行うためのバッファである。
【0126】
前述したように、IS部13Qは、FS部12Qと同様クラスタ単位でデータの管理を行う。FS部12QからIS部13Qに対して論理ブロックの移動、すなわちFS12からの追い出しが発生すると、以前FS部12Qの管理対象であった追い出し対象の論理ブロックはポインタの付け替えによりIS部13(詳細には、ISIB13a)の管理対象ブロックとなる。このFS部12QからIS部13Qへの論理ブロックの移動により、IS13のブロック数が所定の上限値を超えると、IS13からMS部11Qへのデータ追い出しおよびISコンパクション処理が実行され、IS部13Qのブロック数は規定値に戻される。
【0127】
・MS構成
MS部11Qは、MSIB11aと、トラック前段バッファ(TFS)11bと、MS11によって構成されている。MSIB11aは、1〜複数個(この実施の形態では4個)のMSフルブロックインプットバッファ(以下MSFB)11aaと、1〜複数個(この実施の形態では2個)の追記インプットバッファ(以下MS追記IB)11abとを備えている。1つのMSFB11aaは、1論理ブロック分の容量を有する。MSFB11aaは、論理ブロック単位の書き込み時に用いられる。1つのMS追記IB11abは、論理ブロック分の容量を有する。MS追記IB11abは、トラック単位の追記書き込み時に用いられる。
【0128】
MSFB11aaには、WC21から追い出された論理ブロック、またはFS12から追い出された論理ブロック、またはIS13から追い出された論理ブロックがCopyされる。1つのMSFB11aaにCopyされた論理ブロックは、TFS11bを経ることなくMS11に直接Moveされる。このMS11へのMove後は、フリーブロックFBがMSFB11aaとして割り当てられる。
【0129】
MS追記IB11abには、WC21から追い出されたトラック、またはFS12から追い出されたトラックが追記的にCopyされる。このようなトラック単位で追記書き込みされるMS追記IB11abのうちでフルになった論理ブロックは、TFS11bにMoveされる。このTFS11bへのMove後は、フリーブロックFBがMS追記IB11abとして割り当てられる。
【0130】
TFS11bは、前述したように、多数の論理ブロック分の容量を有し、MS追記IB11abとMS11との間に介在するFIFO構造を有するバッファである。FIFO構造を持つTFS11bの入力側には、トラック単位で追記書き込みされるMS追記IB11abのうちでフルになった論理ブロックがMoveされ、またMS11内のコンパクション処理によって形成された論理ブロックが、MSコンパクションバッファ11cからMoveされる。MSコンパクションバッファ11cは、MS11でのコンパクションを行うためのバッファである。なお、MS11内部のコンパクション処理によって、MS内トラックがMSコンパクションバッファ11cに書き込まれる際には、書き込み対象のトラックに含まれるWC21、FS部12Q、IS部13Q内の有効クラスタがDRAM20の作業領域を介してMSコンパクションバッファ11cに書き込まれる、受動マージが行われる。本実施の形態においては、MSIB11aおよびTFS11bに登録されている論理ブロックについては、コンパクション対象に含めない。
【0131】
図22は、データ管理部120のより詳細な機能構成を示すものである。データ管理部120は、前述したように、DRAM20に記憶したデータの管理を行うDRAM層管理部120aと、NANDメモリ10に記憶したデータの管理を行う論理NAND層管理部120bと、NANDメモリ10を物理記憶デバイスとして管理する物理NAND層管理部120cとから構成される。
【0132】
DRAM層管理部120aは、RCクラスタ管理テーブル23、WCクラスタ管理テーブル25、WCトラック管理テーブル24を備え、これら管理テーブに基づいてDRAM層の管理を行う。論理NAND層管理部120bは、トラック管理テーブル30、MSブロック管理テーブル35、FS/IS管理テーブル40、FS/IS論理ブロック管理テーブル42、FS/IS内クラスタ管理テーブル44の他に、MS構造管理テーブル60、FS/IS構造管理テーブル65を備え、これらの管理テーブルに基づいてNANDメモリ10の論理NAND層の管理を行う。物理NAND層管理部120cは、論物変換テーブル50の他に、バッドブロック管理テーブル(BB管理テーブル)200、予約ブロック管理テーブル(RBブロック管理テーブル)210、フリーブロック管理テーブル(FB管理テーブル)220、アクティブブロック管理テーブル(AB管理テーブル)230を備え、これらの管理テーブルを用いてNANDメモリ10の物理NAND層の管理を行う。
【0133】
・物理NAND層
まず、物理NAND層について説明する。前述したように、32ビット倍速モードでは、4ch(ch0、ch1、ch2、ch3)を並列で動作させ、更に、NANDメモリチップの備える倍速モードを利用して消去/書き込み/読み出しを行う。図23に示すように、4つの並列動作要素10a〜10d内の各NANDメモリチップは、例えば、プレーン0、プレーン1の2つの領域(District)に分割されている。なお、分割数は2に限定されるものではない。プレーン0およびプレーン1は、互いに独立した周辺回路(例えば、ロウデコーダ、カラムデコーダ、ページバッファ、データキャッシュ等)を備えており、NANDコントローラ112から入力されるコマンドに基づき、同時に消去/書き込み/読み出しを行うことが可能である。NANDメモリチップの倍速モードでは、上記プレーン0およびプレーン1を並列制御することにより、高速書き込みを実現している。
【0134】
物理ブロックサイズは512kBであるので、32ビット倍速モードでは、4chの並列動作および2つのプレーンに対する同時アクセスにより、その消去単位は512kB×4×2=4MBとなる。すなわち、この32ビット倍速モードでは、結果的に、8プレーンが並列動作することになる。
【0135】
図24は、論物変換テーブル50の他の例を示すものである。図24に示す論物変換テーブル50は、図17に示した論物変換テーブル50に対し、論理ブロックID50aに対応する論理ブロックが消去された時刻を示す消去時刻50eのフィールドが更に追加されている。消去時刻50eとしては、例えば、NANDメモリチップ内の論理ブロックに対して消去動作が行われた回数を計測することで得られる値、或いは、NANDコントローラ112の通電時間等を利用すればよい。消去時刻50eは、後述するFB管理テーブル220でのフリーブロックFB管理に利用される。
【0136】
BB管理テーブル200は、物理ブロック(512kB)単位でバッドブロックBBを管理するためのテーブルである。BB管理テーブル200は、図25に示すように、例えば、4(チャネル)×2(プレーン/チャネル)個のチャネル内プレーン毎に、(物理ブロック数/プレーン)×(NANDメモリチップ数/1並列動作要素)個数分の物理ブロックに関する情報をもつ二次元配列形式で構成されており、各エントリには、各物理ブロックに対する物理ブロックID200aが保持されている。
【0137】
本実施形態の場合、1NANDメモリチップは2GBサイズであり、第1番目のチップのプレーン0には、「0」〜「2047」の物理ブロックIDが割り当てられ、第1番目のチップのプレーン1には、「2048」〜「4095」の物理ブロックIDが割り当てられる。物理NAND層管理部120cは、使用中に発生したバッドブロックBBをBB管理テーブル200に登録する際には、ソートはせずに対応するチャネル内プレーンID(ID#0〜ID#7)の最後尾の有効エントリの直後に順に追加する。
【0138】
RB管理テーブル210は、8個の物理ブロック単位(512kB)で4MB論理ブロックを形成する際に余ったブロック(予約ブロックRB)を管理するためのテーブルであり、BB管理テーブル200と同様のフォーマットで管理される。対応するチャネル内プレーンIDごとにFIFO管理とすることで、最も古く登録された予約ブロックから優先して利用する。
【0139】
FB管理テーブル220は、4MB論理ブロック単位で現在用途未割り当てのフリーブロックFBを管理するためのテーブルであり、フリーブロックFBとなった順にソートされたFIFO形式のリストである。各エントリは、論理ブロックIDを保持する。コンパクション処理などにより、FB管理テーブル220に返却されたフリーブロックFBは、リストの最後尾に追加され、フリーブロックFB割り当ては、リストの先頭ブロックを返すことで行う。
【0140】
FB管理テーブルは、図26に示すように、返却FIFOリスト220aと、割り当てリスト220bとの2段構成になっている。返却FIFOリスト220aは、消去時刻50e順に整列しており、割り当てリスト220bは、消去回数50cの少ない論理ブロックほどリストの先頭に位置する。これは、短い時間間隔で消去動作を繰り返すことを防ぐための構成である。不要になり、FB管理テーブル220に返却された論理ブロックは、返却FIFOリスト220aの最後尾に追加され、一定の期間にここに保持される。
【0141】
返却FIFOリスト220aから押し出された論理ブロックは、その消去回数50cに応じて割り当てリスト220bの途中に挿入される。論理NAND層管理部120bからフリーブロックFBの割り当てを要求されると、論理NAND層管理部120cは、割り当てリスト220bの先頭から取り出し、割り当てを行う。
【0142】
上記FB管理テーブルにより、全ての論理ブロックの消去回数、消去間隔が概ね等しくなるように、消去する論理ブロックを均等に分散させる(ウェアレベリング処理)ことが可能となる。NAND型フラッシュメモリの寿命は、消去回数の他に、消去処理の間隔にも依存しており、その間隔が長いほどリテンション特性が良く、寿命が延びることが知られている。これは、消去間隔が短いとリテンション特性が悪く、寿命が損なわれることも示している。また、短い間隔で書き込みを行ったとしても、相応の長期間消去を行わなければリテンション特性が回復することも知られている。
【0143】
AB管理テーブル230は、フリーブロックFBから割り当てられた、用途が割り当てられた論理ブロック(アクティブブロックAB)のリストであり、FB管理テーブル220と同様に、各エントリは、論理ブロックIDを保持する。登録順序が古い論理ブロックほど先頭に位置することになる。AB管理テーブルは、例えば、リフレッシュ処理に使用される。
【0144】
リフレッシュ処理とは、書き込んだデータの経年変化や読み出し処理に伴うデータ破損であるリードディスターブの影響で、SSD100の誤り訂正能力を超える誤りが発生することを防止するための技術である。具体的には、例えば、誤り訂正能力を超える誤りが発生する前に、記憶してあるデータを読み出して誤り訂正を行い、その後再びNAND型フラッシュメモリにデータを書き直すという処理を行う。例えば、読み出し回数50dの多いブロック、AB管理テーブル230の先頭ブロックなどをリフレッシュ処理の監視対象とすることができる。
【0145】
物理NAND層管理部120cは、以下のような論理ブロック−物理ブロック管理を行う。先ず、図27を用いて論物変換テーブル50を用いた、論理ブロックIDと8個の物理ブロックIDとの対応関係について説明する。
【0146】
前述したように、論物変換テーブル50の物理ブロックID50bのフィールドには、論物変換テーブル50のインデックスである論理ブロックID50aに対応付けられた8個の物理ブロックIDが登録されている。図27は、NANDメモリ10の論理ブロックIDと物理ブロックIDとの対応関係を示すものであり、1つの区画が1物理ブロックを表している。各物理ブロックに物理ブロックIDが割り当てられている。論理ブロックL0は、例えば、1行3列、2行2列、3行2列、4行2列、5行2列、6行2列、7行2列、8行3列の8個の物理ブロックで構成されている。また、破線BL1で囲まれた論理ブロックL1は、例えば、1行4列、2行3列、3行3列、4行3列、5行3列、6行3列、7行3列、8行4列の8個の物理ブロックで構成されているとする。
【0147】
この後、例えば、論理ブロックL1の4行3列の物理ブロックが、記憶領域として使用できないバッドブロックBBとして、BB管理テーブル200に登録されたとする。これを検知した物理NAND層管理部120cは、RB管理テーブル210から、このバッドブロックBBとして登録された物理ブロックと同一チャネルで同一プレーンの予約ブロックRBを当該バッドブロックBBに対する入れ替え候補として選択する。図27の場合は、隣接する4行4列の物理ブロック(予約ブロックRB)が4行3列のBBに対する入れ替え候補として選択されている。
【0148】
物理NAND層管理部120cは、論物変換テーブル50の論理ブロックL1に対応する論理ブロックID50aのエントリを検索し、このエントリ中の物理ブロックID50bのフィールドに含まれる8個の物理ブロックIDのうちの4行3列に対応するバッドブロックBBの物理ブロックIDを、RB管理テーブル210から選択した4行4列のRBに対応する物理アドレスIDに変更する。これにより、この後、論理ブロックL1は、一点鎖線で囲まれた1行4列、2行3列、3行3列、4行4列、5行3列、6行3列、7行3列、8行4列の8個の新たな物理ブロックの組み合わせで構成されることになる。この論理ブロックL1の論理ブロックIDが「L1」であるとする。
【0149】
その後、物理NAND層管理部120cは、FB管理テーブル220から新たなフリーブロックFBを確保する。この確保したフリーブロックFBの論理ブロックIDが「L3」であるとする。物理NAND層管理部120cは、論物変換テーブル50を用いて論理ブロックIDの入れ替えを実行する。具体的には、論理ブロックID「L1」に対し、論理ブロックIDが「L3」である新たなフリーブロックFBに対応付けられた8個の物理ブロックを対応付け、さらに論理ブロックID「L3」に対し、前述の物理ブロックの組み合わせが変更された一点鎖線で囲まれた1行4列、2行3列、3行3列、4行4列、5行3列、6行3列、7行3列、8行4列の8個の物理ブロックを対応付ける。消去回数50c、読み出し回数50d、消去時刻50eも論理ブロックID入れ替えに伴い入れ替える。その後、論理ブロックID「L3」を、FB管理テーブル220に登録する。
【0150】
一方、バッドブロックBBに対して入れ替え可能な予約ブロックRBが存在しない場合には以下のような処理を行う。例えば、論理ブロックL1の4行3列の物理ブロックがバッドブロックBBとしてBB管理テーブル200に登録されたとし、さらに、このバッドブロックBBに対しては同一チャネルかつ同一プレーン内に予約ブロックRBが存在しない場合には、まず、論理ブロックL1内の4行3列を除く、1行4列、2行3列、3行3列、5行3列、6行3列、7行3列、8行4列の7個の物理ブロックをRB管理テーブル210に登録する。その後は、前記同様、FB管理テーブル220から新たなフリーブロックFBを確保し、前記同様の論理ブロックIDの入れ替えを実行した後、FB管理テーブル220から取得した論理ブロックIDを使用不可とする。
【0151】
このように、物理NAND層管理部120cは、バッドブロックBBが発生した場合でも、論理ブロックIDの入れ替えを実行しているので、論理NAND層管理部120bで使用する論理ブロックIDは、バッドブロックBBの発生の前後で変化しない。したがって、複数の物理ブロックの少なくとも1つをバッドブロックとして登録する場合であっても、LBA論理アドレスと論理ブロックとの対応関係は変更されず、論理NAND層管理部120bでの管理テーブルの書き換えのオーバーヘッドを回避することができる。
【0152】
つぎに、32ビット倍速モードでの消去処理について説明する。物理NAND層管理部120cは、NANDメモリ10のデータが論理ブロック単位で消去されるごとに、図24に示す論物変換テーブル50の消去された論理ブロックに対応する論理ブロックID中の消去回数50cのフィールドを1カウントアップするとともに、消去時刻50eを最新のデータに更新する。
【0153】
・論理NAND層
つぎに、図28、図29を用いて論理NAND層での管理に使用されるMS構造管理テーブル60およびFS/IS構造管理テーブル65について説明する。図28に示すMS構造管理テーブル60は、MS部11Qの構造を管理するための領域と、状態情報を保存するための領域とを有する。MS構造管理テーブル60は、MSFB11aa、MS追記IB11ab、TFS11bとして割り当てられた論理ブロックIDを管理するMSバッファ管理テーブル61と、MSコンパクション時のソート処理を高速化するために、有効トラック数が少なくなった論理ブロックIDを保持する有効トラック数別論理ブロックIDリスト62と、状態情報としての最大論理ブロック数MBLおよび有効論理ブロック数VBLを管理する領域63、64とを備える。
【0154】
MS構造管理テーブル60では、MSFB11aa用、MS追記IB11ab用、TFS11b用に、それぞれ所要エントリ数の固定フィールド61a〜61cが用意され、各固定フィールド61a〜61cに論理ブロックIDが記録される。TFS11b用のフィールド61cは、リンクドリスト構造を有し、FIFO構造を有するTFS11bに対するFIFO的な管理が行われている。
【0155】
有効トラック数別論理ブロックIDリスト62では、有効トラック数が1個の論理ブロック用として所要数のエントリが用意され、有効トラック数が2個の論理ブロック用として所要数のエントリが用意され、…、有効トラック数が2−1の論理ブロック用として所要数のエントリが用意されており、各エントリには、論理ブロックIDが記録される。MS論理ブロック管理テーブル35の有効トラック数35cのフィールドがサーチされることによって有効トラック数別論理ブロックIDリスト62は、常に最新の状態に更新される。なお、有効トラック数別論理ブロックIDリスト62には、MSIB11a、TFS11bとしてMSバッファ管理テーブル61に登録されている論理ブロックについては、エントリされない。
【0156】
状態情報としての最大論理ブロック数MBL用の固定フィールド63には、MS部11Qが取得するのを許容されている論理ブロック数である最大論理ブロック数MBLが記録される。状態情報としての有効論理ブロック数VBL用の固定フィールド64には、MS部11Qとして現在管理されている論理ブロック数としての有効論理ブロック数VBLが記録される。
【0157】
図29に示すFS/IS構造管理テーブル65は、FS部12QおよびIS部13Qの構造を管理するための領域を有する。FS/IS構造管理テーブル65は、FSIB12aおよびFS追記IB12abとして割り当てられた論理ブロックIDを管理するFS入力バッファ管理テーブル66と、FS12のFIFO構造を管理するFSFIFO管理テーブル67と、ISIB13aとして割り当てられた論理ブロックIDを管理するIS入力バッファ管理テーブル68と、IS13のFIFO構造を管理するISFIFO管理テーブル69とを備える。
【0158】
FS入力バッファ管理テーブル66は、FSFB12aa用、FS追記IB12ab用に、それぞれ所要エントリ数の固定フィールド66a、66bが用意され、各固定フィールド66a、66bにFS/IS論理ブロック管理テーブル42のインデックスであるFS/ISブロックID42aが登録される。IS入力バッファ管理テーブル68は、ISIB13a用に所要エントリ数の固定フィールドが用意され、各固定フィールドに、FS/ISブロックID42aが登録される。FSFIFO管理テーブル67には、FS12のFIFO構造を形成する論理ブロック数分のエントリが固定フィールドに用意され、FSFIFO管理テーブル67の各固定フィールドには、FS/ISブロックID42aが登録される。ISFIFO管理テーブル69には、IS13のFIFO構造を形成する論理ブロック数分のエントリが固定フィールドに用意され、各固定フィールドには、FS/ISブロックID42aが登録される。
【0159】
つぎに、先の図19を用いて説明した、2ステージ(WCF処理およびCIB処理)に分割された書き込み処理が実行されるときの、WC21からMSIB11aへのCopy処理に伴う各管理テーブルの更新処理を説明する。なお、ここでは、WC21からMS追記IB11abへのトラック単位のCopyが発生した場合について説明する。DRAM層管理部120aでは、WCトラック管理テーブル24を先頭から順にチェックし、追い出し確定トラックに対応する論理トラックアドレス24aが登録されたトラックエントリ中のway−lineビットマップ24cを参照し、way−lineビットマップ24cのm×nのエントリ中のValidビットが“1”のエントリに対応するWCクラスタ管理テーブル25中のエントリにおける状態フラグ25aをValidからNANDへの追い出し待ちにし、論理NAND層管理部120bに対し追い出し要求を通知する。
【0160】
一方、論理NAND層管理部120bでは、図28に示すMS構造管理テーブル60のMSバッファ管理テーブル61および図14に示すMS論理ブロック管理テーブル35を参照し、MS追記IB11abの状態をチェックする。すなわち、MSバッファ管理テーブル61のMS追記IB用のフィールド61bからMS追記IB11abが既に存在していると判断されたときは、MS追記IB用のフィールド61bに登録されている論理ブロックIDについての書き込み可能トラック数に関する情報をMS論理ブロック管理テーブル35の有効トラック数35cのフィールドから取得し、該取得した書き込み可能トラック数をDRAM層管理部120aに通知する。
【0161】
また、論理NAND層管理部120bは、MSバッファ管理テーブル61のMS追記IB用のフィールド61bからMS追記IB11abが存在していないと判断されたときは、物理NAND層管理部120cに対し、フリーブロックFBの獲得要求を出して、フリーブロックFBを該FBとして割り当てられた論理ブロックIDと共に取得する。そして、取得したフリーブロックFBの書き込み可能トラック数2をDRAM層管理部120aに通知する。
【0162】
DRAM層管理部120aでは、論理NAND層管理部120bから通知された書き込み可能トラック数だけ、WCトラック管理テーブル24からトラックを選択し、さらに前述のトラック内セクタ穴埋めと受動マージを行うか否かを判断する。ここでは、トラック内セクタ穴埋めを行う必要はないとする。DRAM層管理部120aは、追い出すトラックがNANDメモリ10に存在しているか否かをチェックして受動マージを行うか否かを調べるために、論理NAND層管理部120bに対し追い出しを行う論理トラックアドレスなどの所要の情報を通知する。
【0163】
この通知を受けると、論理NAND層管理部120bは、トラック管理テーブル30のインデックスである論理トラックアドレス30a、必要な場合はさらにFS/IS管理テーブル40を検索し、NANDメモリ10側に追い出しを行う論理トラックアドレスと同一の論理トラックが存在しているかをサーチし、このサーチ結果を物理NAND層管理部120cに通知する。これによって、物理NAND層管理部120cによって、受動マージを伴うあるいは受動マージを伴わないWC21からMS追記IB11abへの追い出しが行われる。
【0164】
物理NAND層管理部120cから、WC21→MS追記IB11abの追い出し終了が通知されると、論理NAND層管理部120bは、MS追記IB11abとしてあらたなフリーブロックFBを物理NAND層管理部120cから取得した場合は、物理NAND層管理部120cから与えられたフリーブロックFBの論理ブロックIDに対応するMS論理ブロック管理テーブル35のエントリのValidフラグ35eをValidにし、MSバッファ管理テーブル61のMS追記IB用のフィールド61bに論理ブロックIDを登録し、MS構造管理テーブル60の有効論理ブロック数VBLをインクリメントする。
【0165】
また、論理NAND層管理部120bは、トラック管理テーブル30を更新する。すなわち、WC21からMS追記IB11abへ追い出されたトラックに対応する論理トラックアドレス30aのエントリに対し、クラスタビットマップ30b、論理ブロックID30cおよび論理ブロック内トラック位置30dなどの所要情報を登録する。
【0166】
受動マージが行われていない場合は、前述のように、トラック管理テーブル30の対応する論理トラックエントリに所要情報を登録する。また、WC21から追い出された新しいトラックに関するデータをMS論理ブロック管理テーブル35の書き込みを行った論理ブロックIDに対応するエントリに対し登録する。MS論理ブロック管理テーブル35への登録としては、MS論理ブロックに格納されたトラックに対応するトラック管理テーブル30のインデックスとしての論理トラックアドレス(トラック管理ポインタ35b)の更新と、有効トラック数35cの更新と、書込み可能先頭トラック35dの更新などがある。
【0167】
WC21とMS11との受動マージが行われたとすると、トラック管理テーブル30中のマージ元トラックに対応する論理トラックアドレス30aのエントリ中の論理ブロックID30cおよび論理ブロック内トラック位置30dなどの所要情報が更新される。具体的には、論理ブロックID30cがMS11に存在していたときの論理ブロックIDからMS追記IB11abに対応する論理ブロックIDに変更され、論理ブロック内トラック位置30dが追記書き込み状態に応じて変更される。
【0168】
さらに、MS論理ブロック管理テーブル35中のマージ元の論理ブロックに対応するエントリにおけるトラック管理ポインタ35bのフィールドの該当箇所を削除し、有効トラック数35cをデクリメントし、さらにMS構造管理テーブル60の有効トラック数別論理ブロックIDリスト62を更新する。マージ元の論理ブロックに対応するエントリにおける有効トラック数35cがデクリメントにより0になった場合は、MS構造管理テーブル60の有効論理ブロック数VBLをデクリメントし、物理NAND層管理部120cに対しこの書き込み不可能な無効なフリーブロックFBを返却する。そして、この返却した論理ブロックに対応するエントリのValidフラグ35eをInValidにする。さらに、前述と同様にして、WC21から追い出された新しいトラックに関するデータをMS論理ブロック管理テーブル35に登録する。
【0169】
また、物理NAND層管理部120cから、WC21→MS追記IB11abの追い出し終了が通知されたとき、論理NAND層管理部120bは、DRAM層管理部120aに対し追い出し終了を通知する。この通知を受けたDRAM層管理部120aでは、WCクラスタ管理テーブル25中の追い出されたトラックに所属する全クラスタに対応するエントリ中の状態フラグ25aはInvalid(使用可能)とされ、この後これらエントリに対する書き込みが可能となる。また、WCトラック管理テーブル24中の追い出されたトラックに対応するリストについては、例えば直前リストのnextポインタ24dが変更または削除されて、無効化される。
【0170】
つぎに、CIB処理について説明する。WCF処理が終了すると、WCF処理によって書き込まれたFSIB12aのデータをFS12にMoveする処理と、WCF処理によって書き込まれたMSIB11aのデータをMS11またはTFS11bにMoveする処理などを含むCIB処理が実行される。以下、図30のフローチャートを用いてCIB処理の詳細手順について説明する。
【0171】
・MS部11QのCIB処理
まず、図19のステップS330で説明したMS部11Qでの第1回目のCIB処理について詳述する。論理NAND層管理部120bは、MS構造管理テーブル60のMSバッファ管理テーブル61のMSFB用フィールド61a、MS追記IB用のフィールド61bに登録されている論理ブロックIDについての有効トラック数の情報をMS論理ブロック管理テーブル35の有効トラック数35cのフィールドから取得し、MSIB11aのMSFB11aaまたはMS追記IB11abに全トラック書き込み済みのフルになったブロックが一つ以上存在するか否かを調べ(ステップS400)、MSIB11aにフルになったブロックが一つ以上存在する場合に、以下の処理を行う。ステップS400の判定がNOである場合は、手順はステップS440に移行する。
【0172】
ステップS400の判断がYESの場合、論理NAND層管理部120bは、MS論理ブロック管理テーブル35の有効トラック数35cを参照することにより、MS内に有効トラック数35cが0となった無効論理ブロックが存在するか否かを調べ、MS内に無効論理ブロックが存在する場合、該無効論理ブロックを物理NAND層管理部120cに返却する(ステップS405)。返却された無効論理ブロックに対応するMS論理ブロック管理テーブル35のエントリはValidフラグ35eがInValidにされ、MS構造管理テーブル60の有効論理ブロック数VBLがデクリメントされる。つぎに、MSFB11aa中のフルになった論理ブロックは、直接MS11にMoveされ、MS追記IB11ab中のフルになった論理ブロックはTFS11bにMoveされる(ステップS407)。このMove処理は、具体的には、MS構造管理テーブル60のMSバッファ管理テーブル61のMSFB用フィールド61a、MS追記IB用のフィールド61bに登録されている該当する論理ブロックIDを削除するのみである。
【0173】
つぎに、論理NAND層管理部120bは、MS構造管理テーブル60の状態情報としての有効論理ブロック数VBLを最大論理ブロック数MBLと比較する(ステップS410)。この比較の結果、有効論理ブロック数VBLが最大論理ブロック数MBLを越えている場合、論理NAND層管理部120bは、書き込み可能なフリーブロックFBが不足していると判断し、以下のMSコンパクション処理を1ブロックずつ実行して、全て無効なトラックで構成された物理NAND層管理部120cに返却するべき無効論理ブロックを増やし、有効論理ブロック数VBLを最大ブロック数未満MBLとする(ステップS420)。なお、ステップS410の判定において、書き込み可能なFBが不足していない場合は、手順はステップS440に移行される。
【0174】
MSコンパクション処理には、前述したように、2トラックMSコンパクションと、2トラック未満MSコンパクションとの2種類がある。2トラックMSコンパクションでは、MSコンパクションバッファ11cが使用されて、コンパクション後の論理ブロックは、TFS11bの先頭にMoveされる。2トラック未満MSコンパクションでは、トラック単位に、MS追記IB11abにCopyされる。
【0175】
まず、論理NAND層管理部120bは、MS構造管理テーブル60の有効トラック数別論理ブロックIDリスト62を参照することで、有効トラック数の少ない論理ブロックから、トラックを2個集めて、集めたトラックを2個ずつ、書き込み可能なフリーブロックFBとして物理NAND層管理部120cから取得したMSコンパクションバッファ11cに対しCopyする、2トラックMSコンパクションを実行する。
【0176】
具体的には、論理NAND層管理部120bは、物理NAND層管理部120cに対し、フリーブロックFBの獲得要求を出して、フリーブロックFBを該フリーブロックFBとして割り当てられた論理ブロックIDと共に取得する。そして、コンパクション対象として選択した複数のトラックをこのフリーブロックFBにCopyするよう、物理NAND層管理部120cに対し、要求する。なお、このコンパクション対象のトラックがWC21、FS部12Q、IS部13Qに有効クラスタを持つ場合にはそれらもマージしてMSコンパクションバッファ11cに集められる、前述の受動マージが実行される。
【0177】
物理NAND層管理部120cからコンパクションの終了が通知されると、論理NAND層管理部120bは、トラック管理テーブル30のコンパクションが行われたトラックに対応する論理トラックアドレス30aを持つエントリにおける、論理ブロックID30cを物理NAND層管理部120cから取得したフリーブロックFBの論理ブロックIDに更新し、さらに論理ブロック内トラック位置30dを更新する。
【0178】
また、MSコンパクションバッファ11cとして使用した、物理NAND層管理部120cから取得したフリーブロックFBの論理ブロックIDをMS論理ブロック管理テーブル35に新たなエントリとして登録し、エントリ中の各フィールドに所要の情報を登録する。この登録としては、トラック管理ポインタ35bの更新と、有効トラック数35cの更新と、書込み可能先頭トラック35dの更新などがある。
【0179】
また、MS構造管理バッファ60のMSバッファ管理テーブル61のTFS用フィールド61cのFIFO構造(リンクドリスト)の先頭に、MSコンパクションバッファ11cとして使用した論理ブロックIDを登録することで、MSコンパクションの結果、有効な2個のトラックを含む1論理ブロックで構成されたMSコンパクションバッファ11cを、TFS11bの先頭(最も古い位置)にMoveする。なお、TFS11bがフルになったら、最も古い先頭のブロックがMS11にMoveされる。
【0180】
つぎに、MS11中のコンパクション元の古いトラックデータを無効化する。具体的には、MS論理ブロック管理テーブル35中のコンパクション元の論理ブロックに対応するエントリにおけるトラック管理ポインタ35bのフィールドの該当箇所を削除し、有効トラック数35cをデクリメントし、さらにMS構造管理テーブル60の有効トラック数別論理ブロックIDリスト62を更新する。有効トラック数35cがデクリメントにより0になった場合は、MS構造管理テーブル60の有効論理ブロック数VBLをデクリメントし、物理NAND層管理部120cに対しこの無効論理ブロックを返却する。そして、この返却した論理ブロックに対応するMS論理ブロック管理テーブル35のエントリはValidフラグ35eがInValidにされる。
【0181】
このようなコンパクション処理および無効論理ブロックFBの返却処理が終了すると、有効論理ブロック数VBLと最大論理ブロック数MBLを比較し、有効論理ブロック数VBLが最大論理ブロック数MBLを越えている場合は、再度、有効トラックを2個集める2トラックMSコンパクションを実行する。また、有効論理ブロック数VBLが最大論理ブロック数MBLを越えている状態で、有効トラックを2個集める2トラックMSコンパクションが不可能になった場合は、2トラック未満MSコンパクションが実行される。
【0182】
この2トラック未満MSコンパクションでは、コンパクション対象の2トラックに満たない個数のトラックをMS追記IB11abにコピーすることで、無効な2トラックで構成された無効論理ブロックを生成し、生成した無効論理ブロックを物理NAND層管理部120cに返却することで、有効論理ブロック数VBLを減少させる。2トラック未満MSコンパクションについての、管理テーブルの更新については、その説明を省略する。
【0183】
・FS12のCIB処理
つぎに、図19のステップS340で説明したFS12でのCIB処理について詳述する。論理NAND層管理部120bは、FS/IS構造管理テーブル65のFS入力バッファ管理テーブル66のFSFB用フィールド66a、FS追記IB用のフィールド66bに登録されている論理ブロックIDについての有効クラスタ数の情報を、FS/IS論理ブロック管理テーブル32の有効クラスタ数42dのフィールドから取得し、FSIB12aのFSFB12aaまたはFS追記IB12abに全ページ(全クラスタ)書き込み済みのフルになった論理ブロックが一つ以上存在するか否かを調べ(ステップS440)、FSIB12aにフルになった論理ブロックが一つ以上存在する場合に、以下の処理を行う。ステップS440の判定がNOである場合は、手順はここで終了する。
【0184】
ステップS440の判断がYESの場合、論理NAND層管理部120bは、FS/IS構造管理テーブル65およびFS/IS論理ブロック管理テーブル42の有効クラスタ数42dを参照することにより、FS部12Q内に有効クラスタ数42dが0である無効論理ブロックが存在するか否かを調べ、FS部12Q内に無効論理ブロックが存在する場合、該無効論理ブロックを物理NAND層管理部120cに返却する(ステップS445)。
【0185】
返却された論理ブロックのエントリはMS論理ブロック管理テーブル35およびFS/IS論理ブロック管理テーブル42から削除される。つぎに、FSFB12aa中のフルになった論理ブロックは、FS12にMoveされ、FS追記IB12ab中のフルになった論理ブロックもFS12にMoveされる(ステップS447)。このMove処理は、具体的には、FS/IS構造管理テーブル65のFS入力バッファ管理テーブル66のFSFB用フィールド66a、FS追記IB用のフィールド66bに登録されている該当する論理ブロックIDを削除するのみである。
【0186】
つぎに、論理NAND層管理部120bは、FIFO構造を有するFS12の論理ブロック数が、FS12として許容される所定の最大論理ブロック数BLfsmaxを越えているか否かを判断する(ステップS450)。具体的には、FSFIFO管理テーブル67から算出した論理ブロック数が予め設定した最大論理ブロック数BLfsmaxを越えているか否かを判断する。
【0187】
この比較の結果、算出した論理ブロック数が最大論理ブロック数BLfsmaxを越えている場合、論理NAND層管理部120bは、書き込み可能なフリーブロックFBが不足していると判断し、そのときの状態に応じて、以下の、MS11への例えば2論理ブロック分ずつの追い出し処理(ステップS460)と、IS13への1論理ブロック分の追い出し処理を実行する(ステップS500)。なお、ステップS450の判定において、FS12内がフルでない場合は、FS12からMSIB11aへの追い出し処理と、FS12からISIB13aへの追い出し処理を行うことなく、手順をここで終了する。
【0188】
FS12からMSIB11aへの追い出し処理では、まず、FS12からIS部13Qを経ることなくMSIBS11aに直接移動する論理ブロックがあるか否かを判断する(ステップS455)。具体的には、FS12のFIFOの先頭にある最古の論理ブロック中のクラスタを順に1つずつチェックし、当該クラスタが属するトラックがFS部12Q中に何個の有効クラスタを保有しているか、トラック管理テーブル30のFSクラスタ数30fのフィールドを参照して検索する。そして、トラック内有効クラスタ数が所定の閾値(例えば2k−i−1個)以上だった場合、その論理トラックをMSIB11aへの追い出し確定トラックとする。
【0189】
上記の検索は、以下のルートを経る。
1.FS/IS構造管理テーブル65のFSFIFO管理テーブル65からFIFOの先頭にある最古のFS/ISブロックIDを得る。
2.このFS/ISブロックIDに対応するFS/IS論理ブロック管理テーブル42のエントリ中のブロック内クラスタテーブル42cのフィールドからFS/IS内クラスタ管理テーブル44へのインデックスを得る。
3.FS/IS内クラスタ管理テーブル44において、取得したインデックスで指定された1論理ブロック内の各エントリからFS/IS管理テーブル40へのポインタを1つ取得して、FS/IS管理テーブル40の該当リンクに飛ぶ。
4.飛び先の該当リンクが所属する該当論理トラックアドレスを得る。
5.取得した論理トラックアドレスを使ってトラック管理テーブル30の該当エントリ中のFSクラスタ数30fのフィールドをチェックする。
6.3〜5が繰り返される。
【0190】
FS12からMS11への追い出しは、例えば2論理ブロックずつ行われる。すなわち、論理NAND層管理部120bは、上記トラック内有効クラスタ数が所定の閾値(例えば2k−i−1個)以上のトラックを、2論理ブロック分集め、該集めた2論理ブロック分のトラックをMSIB11aのMSFB11aaに追い出す(ステップS460)。この追い出しの際、追い出しトラック中のFS12内に存在しないクラスタについては、WC21、IS部13Q、およびMS11から読み出してマージする前述の受動マージが実行される。
【0191】
ただし、MSIB11aへの追い出し確定トラックが、2論理ブロック分存在しない場合は、1論理ブロックをMSIB11aのMSFB11aaに追い出し、1論理ブロック分に満たない個数のトラックをMS追記IB11abに対してトラック単位に追記書き込みする(ステップS460)。同様に、MSIB11aへの追い出し確定トラックが、1論理ブロック分存在しない場合は、1論理ブロック分に満たない個数のトラックをMS追記IB11abに対してトラック単位に追記書き込みする(ステップS460)。その後、FIFO構造のFS12の先頭論理ブロックに有効なクラスタが残っていない場合には、先頭論理ブロックを無効論理ブロックとして、物理NAND層管理部120cに返却する。
【0192】
・MS11のCIB処理(図19:ステップS350)
このようにして、FSからMSIB11aへの追い出しが発生すると、つぎに、MS部11QのCIB処理が再び実行される(ステップS480)。このステップS480のMS部11QのCIB処理は、先の第1回目のMS部11QでのCIB処理(ステップS400〜S420)と同様なので、重複する説明は省略する。このMS部11QでのCIB処理の後、論理NAND層管理部120bは、FS12からMSIB11aへの追い出し条件が成立するか否かを、前記同様にして調べる(ステップS455)。この追い出し条件が成立すると、前述した、FS12からMSIB11aへの2論理ブロックの追い出し、およびMS11でのCIB処理が、再度実行される。このような処理が、ステップS455の判断がNOになるまで繰り返される。
【0193】
・FS12のCIB処理
ステップS455の判断がNOになると、論理NAND層管理部120bは、つぎに、FS12からISIB13aへの追い出し条件が、成立するか否かを判断する(ステップS490)。具体的には、上記FS12からMSIB11aへの追い出し処理の際に、チェックされたFIFO構造を有するフル状態のFS12の先頭論理ブロックに有効なクラスタが残っている場合に、ステップS490でのFS12からIS13への追い出し条件が成立したとして、FS12からISIB13aへの追い出しを実行する。
【0194】
すなわち、ステップS490で条件が成立した場合は、MSIB11aへの追い出しトラックに含まれないクラスタだけを含む先頭論理ブロックをISIB13aへMoveする(ステップS500)。このステップS500においては、例えば1論理ブロックの追い出しが実行される。そして、状態によっては、その後、ステップS520〜S585の手順を経た後、ステップS590の判断により、ステップS500でのFS12からISIB13aへの追い出しが再度発生することもある。
【0195】
ステップS500での再追い出しがある状態とは、例えば、FSIB12aに複数のフルになった論理ブロックを有するバッファ(FSFB12aaまたはFS追記IB12ab)が存在する状態において、FIFO構造を有するFS12がフルであった場合には、FSIB12aからFS12へのフルになったブロックのMoveに伴い、FS12からMSIB11aまたはISIB13aへの複数のブロックの追い出しが発生する状態である。このような条件下で、FS12からISIB13aへの複数の論理ブロックの追い出しが発生する可能性がある。
【0196】
・ISのCIB処理(図19ステップS360)
つぎに、ステップS490での条件が成立したときに、IS13で行われる追い出し処理およびコンパクション処理の詳細について、図30の他に、図31のフローチャートを参照して説明する。まず、論理NAND層管理部120bは、前記と同様にして、IS部13Q内に無効論理ブロックが存在するか否かを調べ、IS部13Q内に無効論理ブロックが存在する場合、該無効論理ブロックを物理NAND層管理部120cに返却する(ステップS520)。返却された論理ブロックのエントリに対応するMS論理ブロック管理テーブル35およびFS/IS論理ブロック管理テーブル42のエントリはValidフラグ35eおよび42fがそれぞれInValidにされる。
【0197】
つぎに、論理NAND層管理部120bは、FIFO構造を有するIS13の論理ブロック数が、IS13として許容される所定の最大論理ブロック数BLismaxを越えているか否かを判断する(ステップS530)。具体的には、ISFIFO管理テーブル69から算出した論理ブロック数が予め設定した最大論理ブロック数BLismaxを越えているか否かを判断する。
【0198】
この比較の結果、算出した論理ブロック数が最大論理ブロック数BLismaxを越えている場合、論理NAND層管理部120bは、書き込み可能なフリーブロックFBが不足していると判断し、IS13から例えば2論理ブロック分のトラックをMSIB11aのMSFB11aaに追い出す(ステップS540)。なお、ステップS530の判定において、IS13がフルでない場合は、MSIB11aへの追い出し処理などを行うことなく、ISIB13a中のフルになった論理ブロックを、IS13bへMoveする(ステップS585)。
【0199】
ステップS540の追い出しの際には、図12に示したトラック管理テーブル30などを用いて、図31に示す追い出しトラックの選別処理を実行する。図31において、論理NAND層管理部120bは、選別処理(サイクリックサーチ処理、以下単にサーチ処理という)を開始すると(ステップS700)、前回のサーチの際に検索済み最終トラックとしてステップS740において記憶したトラック管理テーブル30のインデックスである論理トラックアドレス30aの次の論理トラックアドレスからサーチを開始する(ステップS710)。
【0200】
サーチが初回(第1サイクル)である場合は、トラック管理テーブル30の最初のエントリからサーチを開始する(ステップS710)。また、ステップS740で記憶した検索済みトラックがトラック管理テーブル30の最終エントリ(図12のトラックn)である場合は、ステップS710での次のトラック検索では、先頭エントリ(図12のトラック0)に戻る。
【0201】
このサーチにおいては、トラック管理テーブル30の当該エントリ中のISクラスタ数30gのフィールド(当該論理トラック中の有効クラスタ数)を参照し、当該エントリIS13内に有効クラスタを保持している場合は、図示しない新規検索トラックリストに当該エントリの論理トラックアドレスを登録する(ステップS720)。つぎに、新規検索トラックリストに登録されたトラックの個数を所定の閾値Lと比較し、登録数が閾値Lより少ない場合は、手順をステップS710に移行し、トラック管理テーブル30の次のエントリを前述と同様にして調べる。
【0202】
このような処理を繰り返すことにより、新規検索トラックリストに閾値L個分の論理トラックアドレスを登録する(ステップS730 Yes)。そして、最後に新規検索トラックリストに登録した論理トラックアドレスに対応するトラック管理テーブル30のエントリ(インデックス)を検索済み最終トラックとして記憶して、今回サイクルの検索を終了する(ステップS740)。
【0203】
つぎに、論理NAND層管理部120bは、前回落選の論理トラック(図示せず)がリストされている落選トラックリストがあるか否かを判断する(ステップS750)。初回サイクルの際は、落選トラックリストが存在しないので、新規検索トラックリストと新規追加ブロック内トラックリスト(図示せず)との2つのリストに基づいて2i+1個の論理トラックを選出する(ステップS760)。新規追加ブロック内トラックリストとは、図30のステップS500で、FS12からIS部13Qに追い出されたブロック(FS/IS構造管理テーブル65のIS入力バッファ管理テーブル68にエントリされている)に含まれるトラックに関するリストである。
【0204】
初回サイクルの際は、このような2つのリストを用いて、追い出し候補の2i+1個のトラックを選出する。この選出には、前述したように、トラック内の有効クラスタ数と、有効クラスタ係数とを用いた選出基準(スコア値)Sが用いられる。
スコア値S=トラック内の有効クラスタ数×有効クラスタ係数
有効クラスタ係数は、トラックがMS部11Q内で無効トラックが存在する論理ブロックに存在するか否かによって重み付けされる数であり、存在したほうが存在しない場合より数が大きいとする。
【0205】
有効クラスタ数は、トラック管理テーブル30のISクラスタ数30gのフィールドを見ることで取得することができる。また、有効クラスタ係数は、トラック管理テーブル30とトラック管理ポインタ35bのフィールドでリンクしているMS論理ブロック管理テーブル35の有効トラック数35cのフィールドを見ることで取得することができる。
【0206】
論理NAND層管理部120bは、新規追加ブロック内トラックリストに含まれる複数のトラックから、上記スコア値Sが上位のM個(所定の設定値)のトラックを選択する。選択されたM個のトラックに、先のサーチによって新規検索トラックリストに登録されたL個のトラックを加え、これらL+M個のトラック中から、スコア値Sが高い2i+1個のトラックを、MS11への追い出しを行うトラックとして選出する。そして、L+M個のトラックのなかで、選出された2i+1個のトラック以外のトラックを、前述の落選トラックリストに登録する。
【0207】
2回目以降のサイクルの際は、落選トラックリストと、新規検索トラックリストと、新規追加ブロック内トラックリストとの3つのリストに基づいて2i+1個のトラックを選出する(ステップS770)。なお、2回目以降の、追い出しを行うか否かは、後述する図30のステップS570の判断に応じて決められる。3つのリストを用いた選出処理では、落選トラックリストに含まれる複数のトラックから、スコア値Sが上位のN個(所定の設定値)のトラックを選択し、新規追加ブロック内トラックリストに含まれる複数のトラックから、スコア値Sが上位のM個(所定の設定値)のトラックを選択し、これらN+M個のトラックに、さらに今回2回目以降のサイクルの際に得られた新規検索トラックリストに登録されたL個のトラックを加え、これらL+M+N個のトラック中から、スコア値Sが高い2i+1個のトラックを、MS11への追い出しを行うトラックとして選出する。そして、L+M+N個の論理トラックのなかで、選出された2i+1個のトラック以外のトラックを、次回サイクルに使用する落選トラックリストに登録する。
【0208】
つぎに、図30のステップS540に戻って説明する。前述のようにして、2論理ブロック分のトラックの追い出し候補が選出されると、論理NAND層管理部120bは、該選出された2論理ブロック分のトラック(すなわち2i+1個のトラック)をMSIB11aのMSFB11aaに追い出す(ステップS540)。この追い出しの際、追い出しトラック中のIS部13Q内に存在しないクラスタについては、WC21およびFS部12、およびMS11から読み出してマージする前述の受動マージが実行される。なお、上記では、有効クラスタ数とMSに穴あきブロックが存在しているか否かの係数とに基づくスコア値Sによって追い出しトラックを選出するようにしているが、有効クラスタ数のみによって追い出しトラックを選出するようにしてもよい。
【0209】
・MSのCIB処理(図19ステップS370)
このようにして、IS13からMSIB11aへの追い出しが発生すると、つぎに、MS11のCIB処理が再び実行される(ステップS560)。このステップS560のMS11のCIB処理は、先の第1回目のMS11でのCIB処理(ステップS400〜S420)と同様なので、重複する説明は省略する。
【0210】
ISのCIB処理
つぎに、論理NAND層管理部120bは、IS13からMSIB11aに対する追い出しを再度実行するか否かを判断する(ステップS570)。すなわち、論理NAND層管理部120bは、MS論理ブロック管理テーブル35およびFS/IS論理ブロック管理テーブル42の有効クラスタ数42dのフィールドなどを用いて、ステップS540での追い出しを行った後のIS13内の論理ブロックを有効クラスタ数の少ない順にソートし、最も有効クラスタ数の少ない2つの論理ブロックの合計有効クラスタ数が、所定の設定値である2個(1論理ブロック分)以上ある場合は、IS13からMSIB11aへの追い出し条件が成立したと判断する(ステップS570)。
【0211】
IS13からMSIB11aへの追い出し条件が成立した場合は、手順をステップS540に移行し、図31のステップS700〜S750およびS770の処理を実行することで、上記の2論理ブロック分の追い出し処理を再度実行する。ステップS570の判断がYESである限り、IS13からMSIB11aへの2論理ブロック分の追い出し処理と、MS11でのCIB処理が繰り返し実行される。そして、ステップS570の判断がNOとなった場合は、IS13でのコンパクション処理が実行される(ステップS580)。
【0212】
ISコンパクション処理では、MS論理ブロック管理テーブル35およびFS/IS論理ブロック管理テーブル42の有効クラスタ数42dのフィールドなどを用いて、IS部13Q内の有効クラスタの少ない論理ブロックから順にクラスタを1論理ブロック分、すなわち2個集め、これら2個のクラスタをISコンパクションバッファ13cにCopyする。このCopy処理が終了すると、論理NAND層管理部120bは、コンパクション元(Copy元)の論理ブロックのうち有効クラスタがなくなったものを無効論理ブロックとして物理NAND層管理部120cに返却し、コンパクション処理によって有効クラスタが詰まった論理ブロックで構成されるISコンパクションバッファ13cをIS13にMoveする。
【0213】
このコンパクションの後、ISIB13a中のフルになった論理ブロックはIS13にMoveされる(ステップS585)。このMove処理は、具体的には、FS/IS構造管理テーブル65のIS入力バッファ管理テーブル68のISIB用フィールドに登録されている該当する論理ブロックIDを削除するのみである。
【0214】
この後、論理NAND層管理部120bは、前述したFS12からISIB13aへの追い出し条件が成立しているか否かを判断し(ステップS590)、このFS12からISIB13aへの追い出し条件が成立している場合は、手順をステップS500に移行し、上述した手順を再度繰り返す。また、論理NAND層管理部120bは、ISコンパクション処理の終了後、FS12からISIB13aへの追い出し条件が成立していないと判断した場合は、これで今回の書き込み処理を終了する。以上が、書き込み処理の詳細である。
【0215】
上記したように、本実施の形態においては、FS12の前段に入力バッファとして機能するFSIB12aを配し、IS本体13bの前段に入力バッファとして機能するISIB13aを配し、MS11の前段に入力バッファとして機能するMSIB11aを配するようにしており、書き込み処理を、WC21からFSIB12aまたはMSIB11aへのデータ追い出し処理を行うWCF処理と、FSIB12aからFS12への追い出し、ISIB13aからIS本体13bへの追い出し、MSIB11aからMS11への追い出し、FS12からISIB13aまたはMSIB11aへの追い出し、IS13からMSIB11aの追い出し、MSコンパクション、ISコンパクションを含むCIB処理との2ステージに分離している。すなわち、各入力バッファ(FSIB12a、ISIB13a、MSIB11a)を設け、該入力バッファによって、書き込みステージを、WC21からNANDメモリ10への書き込み処理(WCF処理)と、NANDメモリ内でのデータ移動処理(CIB処理)との2ステージに分離するようにしており、これにより、NANDメモリ内でのデータ移動処理(CIB処理)に時間がかかる場合でも、WC21からNANDメモリ10への書き込み処理(WCF処理)は、即座に遅延無く実行することができ、WC21からNANDメモリ10への書き込み処理のレイテンシを保証することができる。
【0216】
また、このような2ステージに分離したことにより、WCF処理と、CIB処理を、パイプライン化しかつ並列処理させることが容易になる。これらWCF処理と、CIB処理を並列処理させるようにすれば、CIB処理の処理時間をホスト装置側には隠蔽することができ、書き込み処理をより高速化することが可能となる。
【図面の簡単な説明】
【0217】
【図1】SSDの構成例を示すブロック図。
【図2】NANDメモリチップに含まれる1個のブロックの構成例と、4値データ記憶方式でのしきい値分布を示す図。
【図3】ドライブ制御回路のハードウェア的な内部構成例を示すブロック図。
【図4】プロセッサの機能構成例を示すブロック図。
【図5】NANDメモリおよびDRAM内に形成された機能構成を示すブロック図。
【図6】WCからNANDメモリへの書き込み処理に係わるより詳細な機能ブロック図。
【図7】LBA論理アドレスを示す図。
【図8】データ管理部内の管理テーブルの構成例を示す図。
【図9】RCクラスタ管理テーブルの一例を示す図。
【図10】WCクラスタ管理テーブルの一例を示す図。
【図11】WCトラック管理テーブルの一例を示す図。
【図12】トラック管理テーブルの一例を示す図。
【図13】FS/IS管理テーブルの一例を示す図。
【図14】MS論理ブロック管理テーブルの一例を示す図。
【図15】FS/IS論理ブロック管理テーブルの一例を示す図。
【図16】FS/IS内クラスタ管理テーブルの一例を示す図。
【図17】論物変換テーブルの一例を示す図。
【図18】読み出し処理の動作例を示すフローチャート。
【図19】書き込み処理の動作例を示すフローチャート。
【図20】各構成要素間のデータの流れにおける入力と出力の組み合わおよびその発生要因を示す図。
【図21】WCからNANDメモリへの書き込み処理に係わるさらにより詳細な機能ブロック図。
【図22】データ管理部内の管理テーブルの他の構成例を示す図。
【図23】並列動作要素とプレーンとチャネルの関係を示す図。
【図24】論物変換テーブルの他の例を示す図。
【図25】BB管理テーブルの一例を示す図。
【図26】FB管理テーブルの内部構成例を示す図。
【図27】NANDメモリの論理ブロックと物理ブロックとの対応関係を示す図。
【図28】MS構造管理テーブルの一例を示す図。
【図29】FS/IS構造管理テーブルの一例を示す図。
【図30】書き込み処理の動作例を示す詳細なフローチャート。
【図31】ISの追い出し動作例を示すフローチャート。
【符号の説明】
【0218】
1 ホスト装置、10 NANDメモリ、11、メインストレージ領域(MS)、11a MS入力バッファ(MSIB)、11b トラック前段ストレージ領域(TFS)、12 前段ストレージ領域(FS)、12a FS入力バッファ(FSIB)、13 中段ストレージ領域(IS)、20 DRAM、21 ライトキャッシュ(WC)、22 リードキャッシュ(RC)、120 データ管理部、 120a DRAM層管理部、120b 論理NAND層管理部、120c 物理NAND層管理部。

【特許請求の範囲】
【請求項1】
ホスト装置に対し第1の単位で読み出し/書き込みが行われる揮発性の半導体記憶素子から構成されるキャッシュメモリとしての第1の記憶部と、
第2の単位で読み出し/書き込みが行われ、前記第2の単位の2以上の自然数倍である第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第2の記憶部と、
前記第3の単位の2以上の自然数分の1である第4の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第3の記憶部と、
ホスト装置からの前記第1の単位からなる複数のデータを前記第1の記憶部に書き込む第1の処理と、前記第1の記憶部に書き込まれた複数のデータを前記第2の記憶部に追い出す第2の処理と、前記第1の記憶部に書き込まれた複数のデータを前記第4の単位で前記第3の記憶部に追い出す第3の処理と、前記第2の記憶部に書き込まれた複数のデータを第4の単位で第3の記憶部に追い出す第4の処理とを実行するコントローラと、
を備えるメモリシステムであって、
前記第2の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第2の記憶部の入力バッファとして機能する第1の入力バッファと、
前記第4の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第3の記憶部の入力バッファとして機能する第2の入力バッファと、
をさらに備え、
前記コントローラは、前記第1〜第4の処理を、前記第1の記憶部に書き込まれた複数のデータを前記第1、第2の入力バッファに追い出すキャッシュ追い出し処理と、前記第1、第2の入力バッファに書き込まれた複数のデータを、第2、第3の記憶部にそれぞれ追い出し、前記第2の記憶部に書き込まれた複数のデータを第2の入力バッファに追い出す追い出し処理および前記第3の記憶部内における第3の単位内の有効なデータを第4の単位で複数選択して第3の記憶部内の新たな第3の単位内に書き直すコンパクション処理を含むバッファ追い出し処理とに分離したことを特徴とするメモリシステム。
【請求項2】
ホスト装置に対し第1の単位で読み出し/書き込みが行われる揮発性の半導体記憶素子から構成されるキャッシュメモリとしての第1の記憶部と、
第2の単位で読み出し/書き込みが行われ、前記第2の単位の2以上の自然数倍である第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第2の記憶部と、
前記第3の単位の2以上の自然数分の1である第4の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第3の記憶部と、
前記第2の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成される第4の記憶部と、
ホスト装置からの前記第1の単位からなる複数のデータを前記第1の記憶部に書き込む第1の処理と、前記第1の記憶部に書き込まれた複数のデータを前記第2の記憶部に追い出す第2の処理と、前記第1の記憶部に書き込まれた複数のデータを前記第4の単位で前記第3の記憶部に追い出す第3の処理と、前記第2の記憶部に書き込まれた複数のデータを第4の単位で第3の記憶部に追い出す第4の処理と、前記第2の記憶部に書き込まれた複数のデータを第3の単位で第4の記憶部に追い出す第5の処理と、前記第4の記憶部に書き込まれた複数のデータを第3の単位で第3の記憶部に追い出す第6の処理とを実行するコントローラと、
を備えるメモリシステムであって、
前記第2の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第2の記憶部の入力バッファとして機能する第1の入力バッファと、
前記第4の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第3の記憶部の入力バッファとして機能する第2の入力バッファと、
前記第2の単位で読み出し/書き込みが行われ、前記第3の単位で消去が行われる不揮発性の半導体記憶素子から構成され、前記第4の記憶部の入力バッファとして機能する第3の入力バッファと、
をさらに備え、
前記コントローラは、前記第1〜第6の処理を、前記第1の記憶部に書き込まれた複数のデータを前記第1、第2の入力バッファに追い出すキャッシュ追い出し処理と、前記第1、第2、第3の入力バッファに書き込まれた複数のデータを、第2、第3、第4の記憶部にそれぞれ追い出し、前記第2の記憶部に書き込まれた複数のデータを第2または第3の入力バッファに追い出し、前記第4の記憶部に書き込まれた複数のデータを第2の入力バッファに追い出す追い出し処理、前記第3の記憶部内における第3の単位内の有効なデータを第4の単位で複数選択して第3の記憶部内の新たな第3の単位内に書き直す第3の記憶部でのコンパクション処理および前記第4の記憶部内における第3の単位内の有効なデータを第4の単位の2以上の自然数分の1である第5の単位で複数選択して第4の記憶部内の新たな第3の単位内に書き直す第4の記憶部でのコンパクション処理を含むバッファ追い出し処理とに分離したことを特徴とするメモリシステム。
【請求項3】
前記キャッシュ追い出し処理と、前記バッファ追い出し処理とを並列に実行することを特徴とする請求項1または2に記載のメモリシステム。
【請求項4】
前記第1の単位はセクタであり、前記第2の単位はページであり、前記第3の単位はブロックであり、前記第4の単位はトラックであることを特徴とする請求項1または3に記載のメモリシステム。
【請求項5】
前記第1の単位はセクタであり、前記第2の単位はページであり、前記第3の単位はブロックであり、前記第4の単位はトラックであり、前記第5の単位はクラスタであることを特徴とする請求項2または3に記載のメモリシステム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate


【公開番号】特開2009−211227(P2009−211227A)
【公開日】平成21年9月17日(2009.9.17)
【国際特許分類】
【出願番号】特願2008−51473(P2008−51473)
【出願日】平成20年3月1日(2008.3.1)
【出願人】(000003078)株式会社東芝 (54,554)
【Fターム(参考)】