(57)【特許請求の範囲】
【請求項１】
ブロックを複数個有する不揮発性半導体メモリと、
前記不揮発性半導体メモリへの書き込みの際に、有効データを含まないブロックであるフリーブロックを１乃至複数個前記不揮発性半導体メモリから選択するブロック選択部と、
前記選択されたフリーブロックに書き込みを行う書き込み制御部と、
を備え、
前記ブロック選択部は、
前記不揮発性半導体メモリに含まれるフリーブロックを、並列動作可能なブロックの集合単位を用いて複数本のフリーブロック管理リストに分類したリスト部と、
通常優先度でフリーブロックを取得する際に、フリーブロック数が第１の閾値より多く存在するフリーブロック管理リストからフリーブロックを取得するよう動作する第１のフリーブロック選択部と、
高優先度でフリーブロックを取得する際に、フリーブロック数が第１の閾値より多く存在するフリーブロック管理リストおよびフリーブロック数が第１の閾値より多く存在しないフリーブロック管理リストからフリーブロックを取得するよう動作する第２のフリーブロック選択部と、
を備えることを特徴とするメモリシステム。
【請求項２】
前記リスト部は、前記不揮発性半導体メモリに含まれる、有効データを含むブロックであるアクティブブロックを前記ブロックの集合単位を用いて分類した複数本のアクティブブロック管理リストをさらに有し、
フリーブロック数が第２の閾値より少ないフリーブロック管理リストに対応するアクティブブロックリストのアクティブブロックのデータを、フリーブロック数が、第２の閾値以上の第３の閾値より多いフリーブロック管理リストのフリーブロックに移動するブロック移動部をさらに備えることを特徴とする請求項１に記載のメモリシステム。
【請求項３】
前記第１のフリーブロック選択部は、所定の論理アドレス範囲内に有効データが所定割合より多い高密度データを前記不揮発性半導体メモリに書き込む際に動作し、
前記第２のフリーブロック選択部は、所定の論理アドレス範囲内に有効データが所定割合より少ない低密度データを前記不揮発性半導体メモリに書き込む際に動作することを特徴とする請求項１または２に記載のメモリシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不揮発性半導体メモリを備えたメモリシステムに関するものである。
【背景技術】
【０００２】
ＮＡＮＤ型フラッシュメモリを備えたメモリシステムは、複数のチップを並列駆動することで転送性能を向上させている。特許文献１では、複数のプレーンを有するＮＡＮＤ型フラッシュメモリにおいて、各プレーンでの初期不良ブロックの個数に関係なく、各プレーンでの空きブロック数の下限値が均等になるように制御することで、各プレーンにおいて、書き込み済みのデータを書き換える際のプレーン内のブロックスワップ用として使用する空きブロックが無くなることを防止している。
【０００３】
しかしながら、特許文献１における空きブロック数の下限値は、後発的な不良ブロック発生を考慮して設定された値であり、後発的な不良ブロックが発生しない限り、確保された空きブロックが有効利用されることはない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−１９９９０５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、書き込み並列度の低下を防止可能なメモリシステムを提供する。
【課題を解決するための手段】
【０００６】
本願発明の一態様にかかるメモリシステムによれば、ブロックを複数個有する不揮発性半導体メモリと、前記不揮発性半導体メモリへの書き込みの際に、有効データを含まないブロックであるフリーブロックを１乃至複数個前記不揮発性半導体メモリから選択するブロック選択部と、前記選択されたフリーブロックに書き込みを行う書き込み制御部とを備え、前記ブロック選択部は、前記不揮発性半導体メモリに含まれるフリーブロックを、並列動作可能なブロックの集合単位を用いて複数本のフリーブロック管理リストに分類したリスト部と、通常優先度でフリーブロックを取得する際に、フリーブロック数が第１の閾値より多く存在するフリーブロック管理リストからフリーブロックを取得するよう動作する第１のフリーブロック選択部と、高優先度でフリーブロックを取得する際に、フリーブロック数が第１の閾値より多く存在するフリーブロック管理リストおよびフリーブロック数が第１の閾値より多く存在しないフリーブロック管理リストからフリーブロックを取得するよう動作する第２のフリーブロック選択部とを備えることを特徴とする。
【発明の効果】
【０００７】
本発明によれば、書き込み並列度の低下を防止可能なメモリシステムを提供できる。
【図面の簡単な説明】
【０００８】
【図１】図１は、ＳＳＤの構成例を示すブロック図である。
【図２】図２は、ＮＡＮＤコントローラとＮＡＮＤメモリとの接続態様を示す図である。
【図３】図３は、ＮＡＮＤコントローラの内部構成例を示すブロック図である。
【図４】図４は、ＮＡＮＤメモリの物理的構成を示す図である。
【図５】図５は、ＮＡＮＤメモリおよびＲＡＭ内に形成された機能構成を示すブロック図である。
【図６】図６は、ＬＢＡ論理アドレスを示す図である。
【図７】図７は、比較例による動的ブロック割り当て方式を概念的に示す図である。
【図８】図８は、比較例による動的ブロック割り当て方式を概念的に示す図である。
【図９】図９は、第１の実施形態の要部構成を示す機能ブロック図である。
【図１０】図１０は、フリーブロックリストおよびアクティブブロックリストを示す図である
【図１１】図１１は、書き込み動作の全体的流れを示すフローチャートである。
【図１２】図１２は、通常優先度でのフリーブロック選択手順を示すフローチャートである。
【図１３】図１３は、高優先度でのフリーブロック選択手順を示すフローチャートである。
【図１４】図１４は、第１の実施形態の要部構成を示す機能ブロック図である。
【図１５】図１５は、第２の実施形態の動作手順を示すフローチャートである。
【図１６】図１６は、パーソナルコンピュータの外観を示す斜視図である。
【図１７】図１７は、パーソナルコンピュータの機能構成例を示す図である。
【発明を実施するための形態】
【０００９】
以下に添付図面を参照して、本発明の実施の形態にかかるメモリシステムを詳細に説明する。なお、これらの実施の形態により本発明が限定されるものではない。
【００１０】
ＮＡＮＤ型フラッシュメモリに求められる性能の一つとして、ホスト機器が指定する論理アドレスが基本的に連続する書き込みであるシーケンシャルライト(逐次書き込み)時のデータ転送性能（以下、シーケンシャルライト性能）がある。シーケンシャルライト性能を上げるためには、同時に複数のチップを駆動するなどして、できるだけ書き込み並列数を上げることが重要になる。
【００１１】
また、ＮＡＮＤ型フラッシュメモリでは、ホスト機器が指定するデータの論理アドレスと、ＮＡＮＤ型フラッシュメモリ上での実際の記憶領域である物理アドレスとの関係を、データ更新の都度動的に関係付ける論物変換方式が採用されることがある。この論物変換方式では、空きブロックを複数のグループに分類し、並列に書き込みができる組み合わせで各グループから空きブロックを選択して並列処理を実現するが、ホスト機器が指定するデータのアドレスによっては、特定のグループのブロックに選択が集中し、選択が集中したグループのブロックが無くなり、その結果、並列に書き込みができる組み合わせで空きブロックの選択ができず、並列度が低下する可能性がある。
【００１２】
［第１の実施形態］
図１は、メモリシステムの一例としてのＳＳＤ（Solid  State  Drive）１００の構成例を示すブロック図である。ＳＳＤ１００は、ＳＳＤコントローラとしてのドライブ制御回路４と、不揮発性半導体メモリとしてのＮＡＮＤ型フラッシュメモリ（以下、ＮＡＮＤメモリと略す）１０と、バッファメモリ、作業用メモリ領域などとして機能する例えば揮発性半導体メモリで構成されるＲＡＭ２０と、ＡＴＡインタフェース（ＡＴＡ  Ｉ／Ｆ）２などのメモリ接続インタフェースなどを備えている。ＳＳＤ１００は、ＡＴＡ  Ｉ／Ｆ２を介してパーソナルコンピュータあるいはＣＰＵコアなどのホスト装置（以下、ホストと略す）１と接続され、ホスト１の外部メモリとして機能する。
【００１３】
ＮＡＮＤメモリ１０は、ホスト１によって指定されたユーザデータを記憶したり、ＲＡＭ２０で管理される管理情報をバックアップ用に記憶したりする。ＮＡＮＤメモリ１０は、複数のメモリセルがマトリクス状に配列されたメモリセルアレイを有し、個々のメモリセルは上位ページ及び下位ページを使用して多値記憶が可能である。ＮＡＮＤメモリ１０は、複数のメモリチップによって構成され、各メモリチップは、データ消去の単位である物理ブロックを複数配列して構成される。また、ＮＡＮＤメモリ１０では、物理ページごとにデータの書き込み及びデータの読み出しが行われる。物理ブロックは、複数の物理ページによって構成されている。図１では、ＮＡＮＤメモリ１０は、４チャネル（４ｃｈ：ｃｈ０〜ｃｈ３）を介して、ドライブ制御回路４内部のＮＡＮＤコントローラ１１３に並列接続されており、４つのチャネル並列動作要素１０ａ〜１０ｄを並列動作させることが可能である。チャネル数は４つに限らず、任意のチャネル数を採用可能である。
【００１４】
ＲＡＭ２０は、データ転送用、管理情報記録用または作業領域用の記憶部として使用される。具体的には、データ転送用の記憶部（データ転送用バッファ）としては、ホスト１から書込要求があったデータをＮＡＮＤメモリ１０に書込む前に一時的に保存したり、ホスト１から読出要求があったデータをＮＡＮＤメモリ１０から読出して一時的に保存したりするために使用される。また、管理情報記録用の記憶部としては、ＮＡＮＤメモリ１０に記憶されるデータの格納位置などを管理するための管理情報（ＮＡＮＤメモリ１０に記憶されている各種管理テーブルが起動時などに展開された管理テーブル、これら管理テーブルの変更差分情報であるログなど）を格納するために使用される。
【００１５】
ドライブ制御回路４は、ホスト１とＮＡＮＤメモリ１０との間でＲＡＭ２０を介してデータ転送制御を行うとともに、ＳＳＤ１００内の各構成要素を制御する。
【００１６】
ドライブ制御回路４は、データアクセス用バス１０１、回路制御用バス１０２を備えている。回路制御用バス１０２には、ドライブ制御回路４全体を制御するプロセッサ１０４が接続されている。回路制御用バス１０２には、ＮＡＮＤメモリ１０に記憶された各管理プログラム（ＦＷ：ファームウエア）をブートするブート用プログラムが格納されたブートＲＯＭ１０５がＲＯＭコントローラ１０６を介して接続されている。
【００１７】
ＡＴＡインタフェースコントローラ（ＡＴＡコントローラ）１１１、ＮＡＮＤコントローラ１１３、及びＲＡＭコントローラ１１４は、データアクセス用バス１０１と回路制御用バス１０２との両方に接続されている。ＡＴＡコントローラ１１１は、ＡＴＡインタフェース２を介してホスト１との間でコマンド（ライト、リード、フラッシュなど）およびデータなどを送受信する。データアクセス用バス１０１には、データ作業領域及びファームウェア展開領域として使用されるＳＲＡＭ１１５がＳＲＡＭコントローラ１１６を介して接続されている。ＮＡＮＤメモリ１０に記憶されているファームウェアは起動時、ブートＲＯＭ１０５に記憶されたブート用プログラムによってＳＲＡＭ１１５に転送される。
【００１８】
ＲＡＭコントローラ１１４は、プロセッサ１０４とＲＡＭ２０とのインタフェース処理などを実行する。ＮＡＮＤコントローラ１１３は、プロセッサ１０４とＮＡＮＤメモリ１０とのインタフェース処理、ＮＡＮＤメモリ１０−ＲＡＭ２０間のデータ転送制御、誤り訂正符号のエンコード／デコード処理などを実行する。
【００１９】
図２は、ＮＡＮＤコントローラ１１３とＮＡＮＤメモリ１０との接続態様を示すものである。ＮＡＮＤメモリ１０は、前述したように、複数個のチャネル並列動作要素１０ａ〜１０ｄによって構成されている。各チャネル並列動作要素１０ａ〜１０ｄは、バンクインターリーブが可能な複数のバンク（図２では４バンク、Ｂａｎｋ０〜Ｂａｎｋ３）によって構成されており、各チャネル並列動作要素１０ａ〜１０ｄ内の各々のバンクは、複数のメモリチップ（図２では、２メモリチップ、Ｃｈｉｐ０、Ｃｈｉｐ１）によって構成されている。
【００２０】
図２に示すように、ＮＡＮＤコントローラ１１３は、複数のチャネルを有し、各チャネルでは、コントロールＩ／Ｏ信号（ＣｔｒｌＩ／Ｏ）を共有する複数のメモリチップを４本のチップイネーブル信号（ＣＥ）でバンク毎に個別に制御する。また、複数のチャネルを跨って４本のレディ／ビジー信号（ＲｙＢｙ）を共有し、レディ／ビジー信号（ＲｙＢｙ）を共有する各チャネルのメモリチップが同時に動作するように制御を行う。レディ／ビジー信号（ＲｙＢｙ）を共有するメモリチップ群をバンクと呼び、各々のバンクは独立して書き込み／読み出し／消去動作を行うことが可能である。
【００２１】
図３は、ＮＡＮＤコントローラ１１３の内部構成例を示すものである。ＮＡＮＤコントローラ１１３では、各チャネルを独立して動作させるために、チャネル毎に、ＤＭＡコントローラ（ＤＭＡＣ）５０と、誤り訂正回路（ＥＣＣ）５１、コマンド発行を行うＮＡＮＤインタフェース（ＮＡＮＤＩ／Ｆ）５２を備える。各ＮＡＮＤＩ／Ｆ５２には、４バンク分のチップイネーブル信号ＣＥ（ＣＥ０〜ＣＥ３）が接続され、アクセスするバンクに応じてＣＥ信号（ＣＥ０〜ＣＥ３）を制御する。また、４バンクを独立して動作させるために、バンク毎に共通接続されたＲｙＢｙ信号を監視してバンクの状態を管理するバンクコントローラ（ＢＡＮＫ−Ｃ）５３を４つ備える。ＢＡＮＫ−Ｃ５３は、それぞれのバンクに対する要求をキューイングする機能を備え、各バンクへの要求がある場合にチャネルの使用権を確保し、自らが管理するバンクへの読み出し／書き込み／消去要求を実行する。調停制御回路５４は、ＮＡＮＤＩ／Ｆ５２及びＢＡＮＫ−Ｃ５３を監視し、各バンクのチャネル使用権を所定の規則に従って調停する。
【００２２】
図４は、ＮＡＮＤメモリ１０のより詳細な内部構成を示すものである。図４では、チャネル数を（Ｍ＋１）個として示し、バンク数をＮ＋１個として示し、チップ数をＫ＋１個として示した。図４に示すように、各メモリチップ（ｃｈｉｐ０〜ｃｈｉｐＫ）は、例えば、それぞれ複数の物理ブロックを含むプレーン０（ｐｌａｎｅ０）、プレーン１（ｐｌａｎｅ１）の２つの領域（District）に分割されている。プレーン０及びプレーン１は、互いに独立した周辺回路（例えば、ロウデコーダ、カラムデコーダ、ページバッファ、データキャッシュ等）を備えており、倍速モードを使用することで、同時に消去／書き込み／読み出しを行うことが可能である。すなわち、同じプレーン内の複数の物理ブロック同士は並列にアクセスできないが、異なるプレーンに属する物理ブロック同士は並列にアクセス可能である。メモリチップ内のプレーン数は２個に限らず、任意である。また、１個のメモリチップは、図４で拡大して示すように、複数の物理ブロックで構成されている（図４ではＸ＋１個の物理ブロック）。
【００２３】
このように、ＮＡＮＤメモリ１０では、複数のチャネルによる並列動作、複数のバンクによる並列動作、複数のプレーンを用いた倍速モードによる並列動作が可能であり、チャネル数を４、バンク数を４、プレーン数を２とした場合、最大３２個の物理ブロックを並列動作させることが可能となる。
【００２４】
図５は、ＮＡＮＤメモリ１０およびＲＡＭ２０内に形成された機能ブロックを示すものである。ホスト１とＮＡＮＤメモリ１０との間には、ＲＡＭ２０上に構成されたライトバッファ（ＷＢ）２１およびリードバッファ（ＲＢ）２２が介在している。ＷＢ２１はホスト１からのWriteデータを一時保存し、ＲＢ２２はＮＡＮＤメモリ１０からのReadデータを一時保存する。ＮＡＮＤメモリ１０内のブロックは、書き込み時のＮＡＮＤメモリ１０に対する消去の量を減らすために、プロセッサ１０４により、中間ストレージ領域（ＶＳ）１２、およびメインストレージ領域（ＭＳ）１１という各管理領域に割り当てられている。ＶＳ１２は、ＷＢ２１からのデータを「小さな単位」であるクラスタ単位に管理するものである。ＭＳ１１は、ＷＢ２１、ＶＳ１２からのデータを「大きな単位」であるトラック単位で管理する。
【００２５】
つぎに、図５の各構成要素の具体的な機能構成について説明する。ホスト１はＳＳＤ１００に対し、ReadまたはWriteする際には、ＡＴＡインタフェース２を介して論理アドレスとしてのＬＢＡ（Logical  Block  Addressing）を入力する。ＬＢＡは、図６に示すように、セクタ（サイズ：５１２Ｂ）に対して０からの通し番号をつけた論理アドレスである。本実施の形態においては、図５の各構成要素であるＷＢ２１、ＲＢ２２、ＶＳ１２、ＭＳ１１の管理単位として、ＬＢＡの下位（ｓ＋１）ビット目から上位のビット列で構成されるクラスタアドレスと、ＬＢＡの下位（ｓ＋ｔ＋１）ビットから上位のビット列で構成されるトラックアドレスとを定義する。
【００２６】
トラックと論理ブロックのサイズは同じであってもよいし、トラックサイズが論理ブロックのサイズより小さくてもよい。論理ブロックとは、ＮＡＮＤメモリ１０のチップ上の物理ブロックを複数組み合わせて構成される仮想的なブロックのことであり、この実施の形態では、論理ブロックは１つの物理ブロックを最大、並列チャネル数分（この場合、図１に示すように最大４ｃｈ）まとめた単位のことをいう。また、論理ブロックを構成する物理ブロックは、バンクインターリーブを有効利用するため、同じバンクに属する物理ブロックから選択される。クラスタサイズはセクタサイズ以上であり、例えば、クラスタサイズは論理ページサイズより小さく設定される。論理ページも同様であり、１つの物理ページを最大、並列チャネル数分まとめた単位のことをいう。トラックサイズは、クラスタサイズの２以上の自然数倍であるとする。
【００２７】
ＮＡＮＤメモリ１０では、前述したように、複数のバンクによる並列動作、複数のプレーンを用いた倍速モードによる並列動作が可能である。したがって、論理ブロック単位に考えた場合、ＮＡＮＤメモリ１０では、バンクによる並列動作、プレーンを用いた並列動作を行うことにより、論理ブロックを複数個並列動作させることができる。
【００２８】
・リードバッファ（ＲＢ）２２
ＲＢ２２は、ホスト１からのRead要求に対して、ＮＡＮＤメモリ１０（ＶＳ１２、ＭＳ１１）からのReadデータを一時的に保存するための領域であり、キャッシュメモリ機能を持たせるようにしてもよい。ホスト１へのデータ転送は、基本的に、ＲＢ２２から行う。ＷＢ２１に最新のデータがある場合は、ＷＢ２１からホスト１へデータ転送が行われる。
【００２９】
・ライトバッファ（ＷＢ）２１
ＷＢ２１は、ホスト１からのWrite要求に対して、ホスト１からのWriteデータを一時的に保存するための領域であり、キャッシュメモリ機能を持たせるようにしてもよい。ＷＢ２１上のデータは、クラスタ単位で管理し、書き込みと有効データの管理はセクタ単位で行う。ＷＢ２１のリソースが不足した場合、ＷＢ２１の記憶データをＮＡＮＤメモリ１０に追い出す。この追い出しの際、ＷＢ２１上で有効クラスタの多いトラック（高密度トラック）は、ＭＳ１１へ追い出され、ＷＢ２１上で有効クラスタの少ないトラック（低密度トラック）は、ＶＳ１２へ追い出される。高密度データとは、所定の論理アドレス範囲内に有効データが所定割合より多いデータであり、低密度データとは、所定の論理アドレス範囲内に有効データが所定割合より少ないデータである。
【００３０】
・メインストレージ領域（ＭＳ）１１
ＭＳ１１はトラック単位でデータの管理が行われ、ほとんどのユーザデータが格納される。ＷＢ２１上で有効クラスタの多いトラック（高密度トラック：有効クラスタが所定の閾値α以上あるトラック）は、ＷＢ１２から直接ＭＳ１１に書き込まれる。その他、ＭＳ１１には、ＶＳ１２で管理しきれなくなったデータが入力される。ＭＳ１１に入力されたトラックと同一ＬＢＡのトラックについてはＭＳ１１の論理ブロック内で無効化し、この論理ブロックを解放する。ＭＳ１１に入力されたトラックと同一ＬＢＡのトラックに属するクラスタについては、ＶＳ１２内で無効化し、論理ブロック内の全クラスタが無効になった論理ブロックは解放する。
【００３１】
・中間ストレージ領域（ＶＳ）１２
ＶＳ１２はクラスタ単位でデータを管理される例えばＦＩＦＯ構造のバッファであり、入力は複数のクラスタをまとめた論理ページ単位で行われる。ＶＳ１２には、ＷＢ２１上で有効クラスタの少ないトラック（低密度トラック：有効クラスタが所定の閾値α未満のトラック）が書き込まれる。ＶＳ１２は、例えば、データの書き込み順序で論理ブロックが並んだＦＩＦＯ構造となっている。ＶＳ１２に存在するクラスタと同一ＬＢＡのクラスタがＶＳ１２に入力された場合、ＶＳ１２内のクラスタを無効化するだけでよく、書き換え動作を伴わない。ＶＳ１２に入力されたクラスタと同一ＬＢＡのクラスタについては、論理ブロック内で無効化し、論理ブロック内の全クラスタが無効になった論理ブロックは解放する。ＶＳ１２の容量が飽和した場合、ＶＳ１２内のクラスタをトラックに統合して、ＭＳ１１へ追い出す。
【００３２】
このようにＮＡＮＤメモリ１０のストレージ領域は、ＭＳ１１とＶＳ１２とに分けて管理されているので、ＬＢＡアドレスが基本的には連続する書き込みであるシーケンシャルライトによるデータは高密度データとして主にＭＳ１１に書き込まれ、ＬＢＡアドレスが連続しないランダムな書き込みであるランダムライトによるデータは低密度データとして主にＶＳ１２に書き込まれる。
【００３３】
ここで、第１の実施形態では、論理ブロックを、フリーブロックＦＢ、アクティブブロックＡＢとして区別して管理する。フリーブロックＦＢとは、内部に有効データを含まない、用途未割り当ての論理ブロックのことである。アクティブブロックＡＢとは、内部に有効データを含み、用途が割り当てられた（例えば、ＶＳ１２、ＭＳ１１に割り当てられた）論理ブロックのことである。ホスト１との間で使用されるＬＢＡとしての論理アドレスと、実際のＮＡＮＤメモリ１０上での記憶位置を示す物理アドレスとの関係がブロック単位に管理されている。ＳＳＤ１００では、論理アドレスと物理アドレスとの関係は予め静的に決定されておらず、データの書込み時に動的に関係付けられる論物変換方式が採用されている。
【００３４】
例えば、同じＬＢＡアドレス上のデータを上書きする場合は、つぎのようなブロック交換が行われる。論理アドレスＡ１に有効なデータが保存されており、記憶領域としてはブロックＢ１が使用されていたとする。ホスト１から論理アドレスＡ１のデータ（サイズはブロックと同じとする）を上書きするコマンドを受信した場合、フリーブロックＦＢ（ブロックＢ２とする）を１個確保し、そのフリーブロックＦＢにホスト１から受信したデータを書き込む。その後、論理アドレスＡ１とブロックＢ２を関係付ける。その結果、ブロックＢ２はアクティブブロックＡＢになり、ブロックＢ１に保存されたデータは無効になるためブロックＢ１はフリーブロックＦＢとなる。このように、ＳＳＤ１００では、同じ論理アドレスＡ１のデータであっても、実際の記録領域として使用されるブロックは書込みの度に変化する。
【００３５】
フリーブロックＦＢは、ＦＢ管理リストによって管理されている。ＦＢ管理リストは、例えば、フリーブロックＦＢとなった時間順やブロックの消去回数順にソートされたＦＩＦＯ形式のリストであり、各エントリには、ブロック識別子が保持される。アクティブブロックＡＢからフリーブロックＦＢとなったフリーブロックＦＢは、ＦＢ管理リストに追加され、フリーブロックＦＢが使用される際には、ＦＢ管理リストから取り出される。ＦＢ管理リストでは、全ての論理ブロックの消去回数、消去間隔を概ね等しくするウェアレベリング処理が実行されている。
【００３６】
次に、本実施形態の要部について説明する。本実施形態においては、ＶＳ１２とＭＳ１１でのフリーブロックＦＢの割り当て管理を分離し、ＭＳ１１には優先的にフリーブロックＦＢを割り当てる。
【００３７】
最初に、比較例について説明する。ＮＡＮＤメモリ１０は、書き込み速度が遅いため、ＳＳＤ１００では、前述したように、チャネル、プレーン、バンクによる並列動作を可能にして、転送性能を向上させている。シーケンシャルライト時に論理ブロックの書き込み並列数を確保する最も簡単な方法は、ＬＢＡの順序と並列に書き込めるバンク、プレーンの順序を固定するＬＢＡ固定割り当て方式を採用し、常に最大並列数で書けるようにすることである。しかし、この方式では、特定のＬＢＡに対する書き込みが繰り返されると、特定のプレーンの消去回数が増加し、製品寿命が短くなってしまう可能性がある。
【００３８】
そこで、ＬＢＡとバンク／チップ／プレーンの割り当てを動的に可変するＬＢＡ動的ブロック割り当て方式が考えられる。この方式では、図７に示すように、並列書き込み可能なプレーンの組（プレーン単位で構成された並列書き込み可能な複数本のＦＢ管理リスト）を作り、書き込み要求がくるたびに並列に書き込めるブロックをラウンドロビンで新たなデータに割り当てていく。空白の四角は、フリーブロックＦＢを示し、「０」が挿入された四角は、ＬＢＡアドレス「０」のデータが格納されたブロックであるとする。図７では、ホストにおいて、４つのスレッドがシーケンシャルライトを行った状態を示しており、第１スレッドのＬＢＡアドレスが「０，１，２，３，…」、第２スレッドのＬＢＡアドレスが「８，９，１０，１１，…」、第３スレッドのＬＢＡアドレスが「１６，１７，１８，１９，…」、第４スレッドのＬＢＡアドレスが「２４，２５，２６，２７，…」であるとし、ＳＳＤ１００には、ホスト１から図示のような順番でデータが入力されたとする。図７では、データの入力順にラウンドロビンによってプレーンが選択され、ＬＢＡアドレスは各プレーンに分散されている。
【００３９】
このように、ラウンドロビン方式を用いた場合、通常の利用では、ＬＢＡアドレスは各プレーンに確率的に分散するが、書き込みパターンに依存してプレーンごとのブロック使用数が偏る場合がある。ブロックの使用数が偏り、特定のプレーンからブロックが確保できなくなると、書き込みの並列数が偏り、転送性能が低下してしまう。
【００４０】
図８は、ＬＢＡ動的ブロック割り当て方式を用いた場合でも、特定のＬＢＡパターンによってプレーンごとのブロック使用数が偏る場合を示している。まず、最初、全プレーンに対するシーケンシャルライト（全面シーケンシャルライト）を行ったとする。単純なランドロビンを用いた場合、図８（ａ）に示すように、ＬＢＡ固定割り当て方式と同様のマッピングとなる。つぎに、特定プレーン（この場合はプレーン０）に存在するブロックのみを更新する書き込みが発生したとする。すなわち、プレーン０のブロックには、８の倍数の論理アドレス「０，８，１６，２４，…」のデータが格納されており、８の倍数の論理アドレス「０，８，１６，２４，…」に対する更新書き込みが発生したとする。ＬＢＡ動的ブロック割り当て方式では、前述したように、同じ論理アドレスのデータであっても、実際の記録領域として使用されるブロックは書込みの度に変化するので、図８（ｂ）に示すように、更新書き込みのデータは、各プレーンのブロックに分散されて書き込まれ、これに伴い、全面シーケンシャルライトのときにデータが書き込まれたプレーン０のブロックは、フリーブロックＦＢとして解放されていく。この結果、プレーン０のみにフリーブロックＦＢが集中し、プレーン０以外のプレーンでは、ブロックの解放（アクティブブロックのフリーブロック化）が発生しないので、フリーブロックが枯渇してしまう。このように、ＬＢＡ動的ブロック割り当て方式を用いた場合でも、書き込みパターンによっては、特定のプレーンの使用数が多くなり、書き込み並列度が下がってしまう可能性がある。
【００４１】
前述したように、ＬＢＡアドレスが基本的には連続する書き込みであるシーケンシャルライトによるデータは高密度データとして主にＭＳ１１に書き込まれ、ＬＢＡアドレスが連続しないランダムな書き込みであるランダムライトによるデータは低密度データとして主にＶＳ１２に書き込まれる。シーケンシャルライトが行われるＭＳ１１には、シーケンシャルライト性能を向上させるために、書き込み並列数を上げることが要求されるので、ＬＢＡ固定割り当て方式を採用することも考えられるが、この方式では、前述したように、特定のＬＢＡに対する書き込みが繰り返されると、特定のプレーンの消去回数が増加し、製品寿命が短くなってしまう可能性がある。
【００４２】
以上のことから、本実施形態においては、ＶＳ１２とＭＳ１１の双方で、動的ブロック割り当て方式を採用し、ＶＳ１２とＭＳ１１でのフリーブロックＦＢの割り当て管理を分離し、ＭＳ１１には優先的にフリーブロックＦＢを割り当てることで、シーケンシャルライトのときのブロック並列度の低下を防止する。
【００４３】
図９は、第１の実施形態の要部構成を示す機能ブロック図である。コントローラ５は、データ読出部６０、データ書込部６１、データ管理部６２を備え、これらの機能要素は前述したファームウェアによって実現される。コントローラ５を、コントローラ５で実現すべき機能が回路として組み込まれたＳｏＣ（System-on-a-chip）で構成してもよい。コントローラ５には、バスを介して、前述したＡＴＡコントローラ１１１、ライトバッファ２１、ＮＡＮＤメモリ１０が接続されている。
【００４４】
データ管理部６２は、ホスト１との間で使用されるＬＢＡとしての論理アドレスと、実際のＮＡＮＤメモリ１０上での記憶位置を示す物理アドレスとの論物関係を管理する。論理アドレスと物理アドレスとの関係は予め静的に決定されておらず、データの書込み時に動的に関係付けられる前述した論物変換方式が採用されている。
【００４５】
データ読出部６０は、ＡＴＡコントローラ１１１からリードコマンド受信を通知されると、データ管理部６２にコマンドで指定されたアドレスに対応するブロックを検索させ、検索されたブロックからデータをリードバッファ（ＲＢ）２２（図５参照）に読み出す。データ読出部６０は、その後コマンドで指定された範囲のデータをホスト１に送信するようにＡＴＡコントローラ１１１を制御する。
【００４６】
データ書込部６１は、ＡＴＡコントローラ１１１からライトコマンド受信を通知されると、ライトバッファ（ＷＢ）２１の空き領域を確保して、ホスト１からデータを受信するようにＡＴＡコントローラ１１１を制御する。データ書込部６１は、その後ライトバッファ（ＷＢ）２１に十分な書込みデータが蓄積されてデータ追い出しが必要になると、ブロック管理部７０に対しデータ書込みに必要な数のフリーブロックＦＢを確保する要求を出し、ブロック管理部７０で確保されたブロックにデータを書き込む。その後、データ書込部６１は、データ管理部６２に対して、アドレスとブロックの対応関係を登録するよう要求する。
【００４７】
ブロック管理部７０は、フリーブロック選択部７１、フリーブロック管理部８０、アクティブブロック管理部９０を備え、ブロックの管理と、データ書込み時に使用するフリーブロックＦＢの選択と、アクティブブロックＡＢの選択を行う。
【００４８】
フリーブロック管理部８０は、フリーブロックＦＢを管理するものであり、プレーン毎にフリーブロックＦＢを管理するための複数本のフリーブロックリスト（ＦＢリスト）を有する。ＦＢリストは、前述した管理情報として、ＲＡＭ２０に記憶されて使用される。各フリーブロックは、自身が属するプレーンに対応するフリーブロックリストにより管理される。ＦＢリストの詳細な形態としては、各フリーブロックＦＢに対応するブロック識別子を含むブロック情報をノードとしてつなぐリスト形態がある。フリーブロックリストにブロックをつなぐ順序は、単純なＦＩＦＯとしてもよいし、ブロックの消去回数でソートした順番でつないでもよい。
【００４９】
アクティブブロック管理部９０は、アクティブブロックＡＢを管理するものであり、プレーン毎にアクティブブロックＡＢを管理する複数本のアクティブブロックリスト（ＡＢリスト）を有する。ＡＢリストは、前述した管理情報として、ＲＡＭ２０に記憶されて使用される。各アクティブブロックは、自身が属するプレーンに対応するアクティブブロックリストにより管理される。ＡＢリストの詳細な形態としては、各アクティブブロックＡＢに対応するブロック識別子を含むブロック情報をノードとしてつなぐリスト形態がある。ＡＢリストにブロックをつなぐ順序は、単純なＦＩＦＯとし、確保された順番にソートされるようにする。確保された順序が判定できるのであれば、双方向リストの構造などでもよく、ＦＩＦＯなどの構造に限らない。
【００５０】
フリーブロック選択部７１は、データ書込部６１から要求されたフリーブロック数βを確保するよう、フリーブロック管理部８０で管理される複数本のＦＢリストから要求数βのフリーブロックＦＢを選択する。フリーブロック選択部７１が並列書込み可能なフリーブロックＦＢの組を選択する際には、所定の順序規則に従いＦＢリストを選択し、選択したＦＢリストからフリーブロックＦＢを取得する。
【００５１】
本実施形態では、論理ブロックを、例えば、各チャネルから同一のバンク番号／チップ番号／プレーン番号を持つ物理ブロックを集めて構成する。即ち、本実施形態では、論理ブロックを構成する物理ブロックの組み合わせ方に関して、下記（１）乃至（４）の制約を設ける。
（１）各チャネルの物理ブロックを１つずつ選択すること。
（２）各チャネルの物理ブロックは、同じチップ番号に属する物理ブロックから選択すること。
（３）各チャネルの物理ブロックは、同じプレーン番号に属する物理ブロックから選択すること。
（４）同一バンク内の物理ブロックを選択すること。
したがって、論理ブロックは、バンク毎に、チップ毎に、プレーン毎に分類可能になる。また、図１０に示すように、ＦＢリスト８０−０〜８０−７は、それぞれ、同一のバンク番号、チップ番号、プレーン番号を持つ論理ブロックのリストとして構成される。
【００５２】
順序規則は、その順にＦＢリストを選択すれば、並列書込み可能な組のフリーブロックＦＢが取得できる順序であることが望ましい。
【００５３】
例えば、バンク数が４個、各バンク内のチップ数が１個、各チップ内のプレーン数が２個の場合（チップ数は全体で４個）、全体で８個のプレーンが存在し、それらのプレーン間では全て並列書込みが可能である。この場合、各プレーンからフリーブロックを１個ずつ選択すれば、最大で８並列での書込みが可能である。この場合、各プレーンに対応するフリーブロックリストに０から７までの識別子を付けて、
｛０，１，２，３，４，５，６，７｝
という長さ８の順序規則を作る。この順序規則を繰り返せば、どの位置からフリーブロックリストの選択を開始したとしても、最大８並列書込み可能なフリーブロックを選択できる。例えば位置４から始まった場合でも｛４，５，６，７，０，１，２，３｝とフリーブロックリストを選択すればよい。
【００５４】
並列書込み可能なプレーンの組に制約がある場合には、並列書込みできないプレーンが順序規則の中でできる限り距離を置くように配置すればよい。例えば、上記同様チップ数は全体で４個ではあるが、バンク数が２個、各バンク内のチップ数が２個、各チップ内のプレーン数が２個の場合、すなわち、各チップは２個ずつ組で２個のバンクを構成しており、同じバンクに属するチップは並列書込みできない制約がある場合を考える。この場合、全体で８個のプレーンが存在しているが、最大並列度は４である。この時、各プレーンを「Ｂ（バンク番号）Ｃ（バンク内チップ番号）Ｐ（チップ内プレーン番号）」と表記すると、図１０に示すように、
｛Ｂ０Ｃ０Ｐ０，Ｂ０Ｃ０Ｐ１，Ｂ１Ｃ０Ｐ０，Ｂ１Ｃ０Ｐ１，
Ｂ０Ｃ１Ｐ０，Ｂ０Ｃ１Ｐ１，Ｂ１Ｃ１Ｐ０，Ｂ１Ｃ１Ｐ１｝
という順序規則を作ればよい。
【００５５】
図１０においては、同じバンクに属するチップは並列書込みできないので、ＦＢリスト８０−０〜８０−３に所属する４つのフリーブロックＦＢは並列動作可能である。また、ＦＢリスト８０−４〜８０−７に所属する４つのフリーブロックＦＢも並列動作可能である。ＦＢリスト８０−２〜８０−５に所属する４つのフリーブロックＦＢも並列動作可能である。ＦＢリスト８０−６〜８０−１に所属する４つのフリーブロックＦＢも並列動作可能である。しかし、ＦＢリスト８０−０〜８０−１に所属するフリーブロックＦＢとＦＢリスト８０−４〜８０−５に所属するフリーブロックＦＢとは並列動作不可能であり、ＦＢリスト８０−２〜８０−３に所属するフリーブロックＦＢとＦＢリスト８０−６〜８０−７に所属するフリーブロックＦＢとは並列動作不可能であり、これらは順序規則の中で距離をおいて配置している。
【００５６】
また、図１０においては、アクティブブロックリスト９０−０〜９０−７も示されている。各プレーンのＦＢリスト８０−１〜８０−７から取得されたフリーブロックのブロック識別子は、同じプレーンのＡＢリスト９０−１〜９０−７に繋がれて、アクティブブロックＡＢとして登録される。
【００５７】
フリーブロック選択部７１は、順序規則上で何番目の選択かを示す情報を保持する。この情報は、順序規則に従いＦＢリストの順序列を作成した場合の、順序列上の位置を示すことから、位置情報Ｐと呼ぶ。また、フリーブロック選択部７１は、順序規則と位置情報Ｐに従いＦＢリストを選択するリスト選択部と、フリーブロック選択後に位置情報Ｐを更新する位置情報更新部を持つ。リスト選択部および位置情報更新部は、優先度別に、高優先処理部と通常優先処理部の２組が備えられている。
【００５８】
本実施形態では、書込み時の転送能力を確保するため、ホストから受信した書込みデータを一時的にライトバッファ２１に蓄積し、十分な量のデータが溜まってからＮＡＮＤメモリ１０の複数のフリーブロックに並列書込みを行う。ＮＡＮＤメモリ１０への書き込みに際しては、ライトバッファ２１からの追い出し対象（フラッシュ対象）となるデータの粒度（高密度、低密度）に応じて、書込み先（ＭＳ１１かＶＳ１２か）を変更する方式が使用される。この様な方式については、特願２００９−５３５１６１号において詳細に説明されている。例えば、シーケンシャルライトでは、連続した（高密度の）大きなデータとなり、ブロック単位でまとめてできるだけ大きな並列度を確保してＭＳ１１に並列に書き込む。
【００５９】
予備ブロック数情報９５は、各ＦＢリストで予備ブロックとして確保しておくフリーブロック数を保持する。この確保しておくフリーブロック数をＲとする。この予備ブロックは、高優先リスト選択部７２でのみ使用可能であり、通常優先リスト選択部７４は、使用することができない。
【００６０】
高優先リスト選択部７２は、データ書込部６１から高優先度の指定があったときに動作し、データ書込部６１から要求されたフリーブロック数βを確保すべく、ＦＢリストの選択を行う。高優先リスト選択部７２は、ＦＢリストからフリーブロックＦＢを選択する際、各ＦＢリストに確保された予備ブロックを使用することができる。高優先位置情報更新部７３は、高優先リスト選択部７２が動作しているとき、順序規則の位置情報Ｐの更新を行う。
【００６１】
通常優先リスト選択部７４は、データ書込部６１から通常優先度の指定があったときに動作し、データ書込部６１から要求されたフリーブロック数βを確保すべく、ＦＢリストの選択を行う。通常優先リスト選択部７４は、ＦＢリストからフリーブロックＦＢを選択する際、各ＦＢリストに確保された予備ブロックを使用することができない。通常優先位置情報更新部７５は、通常優先リスト選択部７４が動作しているとき、順序規則の位置情報Ｐの更新を行う。なお、高優先位置情報更新部７３および通常優先位置情報更新部７５を設け、高優先および通常優先の際の位置情報Ｐの更新を独立に行うようにしたが、高優先および通常優先の際の位置情報Ｐの更新を共通化してもよい。
【００６２】
つぎに、図１１にしたがって書込み処理の全体的な手順の概要について説明する。ＡＴＡコントローラ１１１は、ホスト１からコマンドを受信した場合（ステップＳ１００）、受信したコマンドがライトコマンドであるか否かを判断する（ステップＳ１１０）。ＡＴＡコントローラ１１１は、ライトコマンド以外のコマンドである場合は、受信したコマンドに応じた処理を実行する（ステップＳ１２０）。
【００６３】
ＡＴＡコントローラ１１１は、受信したコマンドがライトコマンドである場合は、以下の処理を実行する。まず、ＡＴＡコントローラ１１１は、コントローラ５にライトコマンド受信を通知する（ステップＳ１３０）。この通知によって、コントローラ５のデータ書込部６１がライトバッファ２１内に書込みデータを受信する領域を確保し、確保した領域へデータを受信するようにＡＴＡコントローラ１１１に指示を出す（ステップＳ１４０）。つぎに、ＡＴＡコントローラ１１１がホスト１から書込みデータを受信し、受信したデータをライトバッファ２１上の指示された領域へ格納する（ステップＳ１５０）。つぎに、データ書込部６１が、ライトバッファ２１の蓄積データを所定のフラッシュ閾値と比較することで、ライトバッファ２１上に充分なデータが蓄積されているか否かを判断し（ステップＳ１６０）、ライトバッファ２１上に充分なデータが蓄積されていない場合は、手順をステップＳ１００に移行させ、コマンド待ちの状態に戻る。
【００６４】
ライトバッファ２１にフラッシュ閾値以上のデータが蓄積されていた場合は、データ書込部６１は、ライトバッファ２１からＮＡＮＤメモリ１０へのデータ追い出しに必要なフリーブロック数β（要求数β）を計算する（ステップＳ１７０）。データ書込部６１は、追い出すデータの粒度（密度）を判定し、データの粒度が細かい場合は（低密度の場合は）、通常優先度を指定し、データの粒度が粗い場合は（高密度の場合は）、高優先度を指定し、必要なフリーブロック数βとともに、ブロック管理部７０にフリーブロックＦＢを要求する（ステップＳ１８０）。
【００６５】
ブロック管理部７０は、要求数β以下の並列書込み可能なフリーブロックの組を選択して、選択したフリーブロックをデータ書込部６１に通知する（ステップＳ１９０）。ブロック管理部では、ＦＢリストから選択したフリーブロックＦＢをアクティブブロックＡＢとし、対応する同じプレーンのＡＢリストにつなぐ（ステップＳ２００）。このステップＳ１９０での処理については、後で詳述する。
【００６６】
データ書込部６１は、ライトバッファ２１上のデータを、ブロック管理部７０から通知されたフリーブロックに並列に書き込むようにＲＡＭコントローラ１１４およびＮＡＮＤコントローラ１１３（図１参照）に要求する。ＲＡＭコントローラ１１４は、ライトバッファ２１からのデータ読み出しを実行し、ＮＡＮＤコントローラ１１３は、ライトバッファ２１から読み出されたデータを、確保された並列度をもってＮＡＮＤメモリ１０に書込む（ステップＳ２１０）。
【００６７】
データ書込部６１は、ＮＡＮＤメモリ１０に書き込んだデータの論理アドレスとブロックの物理アドレスとの対応関係を登録するようデータ管理部６２に要求する。データ管理部６２は、データ書込みが行われた論理アドレスとブロックの論物関係を登録し（ステップＳ２２０）、さらにデータ書込みが行われた論理アドレスに以前対応付けられていたアクティブブロックＡＢをＡＢリストから取り除き、フリーブロックＦＢとして管理するようブロック管理部へ通知する（ステップＳ２３０）。ブロック管理部７０は、データ管理部６２から通知されたフリーブロックが属するプレーンに対応するＦＢリストを特定し、通知されたフリーブロックをＦＢリストにつなぐ。
【００６８】
データ書き込み部６１は、ステップＳ１９０で選択された並列書き込み可能なフリーブロックの個数が、要求数βに達したか否かを判断する（ステップＳ２４０）。換言すれば、データ書き込み部６１は、ライトバッファ２１からＮＡＮＤメモリ１０へ追い出す必要のあるデータが残っているか否かを判断する。並列書き込み可能なフリーブロックの個数が要求数βに達していなければ、ステップＳ１７０に戻り、要求数βを再計算する。要求数βに達していれば、ライトバッファ２１からＮＡＮＤメモリ１０へのデータ追い出し処理を終了する。
【００６９】
つぎに、図１１のステップＳ１８０で通常優先度が指定されたときのブロック管理部７０の動作手順を図１２に従って説明する。なお、データ書込部６１からのフリーブロック要求数をβ（要求数β）とする。
【００７０】
通常優先リスト選択部７４は、通常優先位置情報更新部７５から位置情報Ｐを取得する（ステップＳ３００）。この位置情報Ｐは、前回の通常優先でのフリーブロック選択での順序規則の終了位置の次の位置である。通常優先リスト選択部７４は、取得した位置情報Ｐから開始した場合の最大並列度ｍを計算する（ステップＳ３１０）。例えば、図１０に示したＦＢリスト構造において、前述したように、ＦＢリスト８０−０からフリーブロックＦＢの取得を開始した場合は、ＦＢリスト８０−０からＦＢリスト８０−３までの４つのＦＢリストを選択することが可能で、最大並列度は４となるが、ＦＢリスト８０−１からフリーブロックＦＢの取得を開始した場合は、ＦＢリスト８０−１からＦＢリスト８０−３までの３つのＦＢリストしか選択することができず、最大並列度は３となる。つぎに、通常優先リスト選択部７４は、ブロック取得数ｎｂ＝０とし、リスト選択回数ｉ＝０とする（ステップＳ３２０，Ｓ３３０）。
【００７１】
通常優先リスト選択部７４は、位置情報Ｐに対応するＦＢリスト（Ｐ）にフリーブロックＦＢが予備ブロック数情報９５として設定されたＲ個以上残っているか否かを判定する（ステップＳ３４０）。この判定でフリーブロックがＲ個未満である場合は、通常優先リスト選択部７４は、このＦＢリスト（Ｐ）からフリーブロックＦＢの取得を行わず、手順をステップＳ３７０に移行する。ステップＳ３４０の判定で、ＦＢリスト（Ｐ）にフリーブロックがＲ個以上ある場合は、通常優先リスト選択部７４は、ＦＢリスト（Ｐ）から、フリーブロックＦＢを取得する（ステップＳ３５０）。つぎに、通常優先リスト選択部７４は、ブロック取得数ｎｂを＋１し、リスト選択回数ｉを＋１する（ステップＳ３６０、Ｓ３７０）。
【００７２】
つぎに、通常優先リスト選択部７４は、位置情報Ｐを＋１して、位置情報Ｐを次の位置に更新する（ステップＳ３８０）。位置情報Ｐが順序規則の最終位置を越えた場合は、位置情報Ｐを順序規則の先頭に設定する。つぎに、通常優先リスト選択部７４は、ブロック取得数ｎｂが要求数βに達したか否かを判定し（ステップＳ３９０）、ｎｂ＝βである場合は、処理を終了する。また、通常優先リスト選択部７４は、リスト選択回数ｉが計算した最大並列度ｍに達したか否かを判定し（ステップＳ３９５）、ｉ＝ｍである場合は、処理を終了する。このようにして、ｎｂ＝βまたはｉ＝ｍが成立するまで、位置情報Ｐを更新しながらＦＢリスト（Ｐ）からフリーブロックを取得する。
【００７３】
このように、通常優先リスト選択部７４は、ＦＢリストからフリーブロックＦＢを選択する際、各ＦＢリストに確保された予備ブロックを使用することができない。
【００７４】
つぎに、図１１のステップＳ１８０で高優先度が指定されたときのブロック管理部７０の動作手順を図１３に従って説明する。データ書込部６１からのフリーブロック要求数をβ（要求数β）とする。
【００７５】
高優先リスト選択部７２は、高優先位置情報更新部７３から位置情報Ｐを取得する（ステップＳ４００）。この位置情報Ｐは、前回の高優先でのフリーブロック選択での順序規則の終了位置の次の位置である。高優先リスト選択部７２は、取得した位置情報Ｐから開始した場合の最大並列度ｍを計算する（ステップＳ４１０）。つぎに、高優先リスト選択部７２は、ブロック取得数ｎｂ＝０とし、リスト選択回数ｉ＝０とする（ステップＳ４２０，Ｓ４３０）。
【００７６】
高優先リスト選択部７２は、位置情報Ｐに対応するＦＢリスト（Ｐ）にフリーブロックＦＢがあるか否かを判定する（ステップＳ４４０）。この判定でフリーブロックがない場合は、高優先リスト選択部７２は、このＦＢリスト（Ｐ）からフリーブロックＦＢの取得を行わず、手順をステップＳ４７０に移行する。ステップＳ４４０の判定で、ＦＢリスト（Ｐ）にフリーブロックがある場合は、通常優先リスト選択部７４は、ＦＢリスト（Ｐ）から、フリーブロックＦＢを取得する（ステップＳ４５０）。つぎに、高優先リスト選択部７２は、ブロック取得数ｎｂを＋１し、リスト選択回数ｉを＋１する（ステップＳ４６０、Ｓ４７０）。
【００７７】
つぎに、高優先リスト選択部７２は、位置情報Ｐを＋１して、位置情報Ｐを次の位置に更新する（ステップＳ４８０）。位置情報Ｐが順序規則の最終位置を越えた場合は、位置情報Ｐを順序規則の先頭に設定する。つぎに、高優先リスト選択部７２は、ブロック取得数ｎｂが要求数βに達したか否かを判定し（ステップＳ４９０）、ｎｂ＝βである場合は、処理を終了する。また、高優先リスト選択部７２は、リスト選択回数ｉが計算した最大並列度ｍに達したか否かを判定し（ステップＳ４９５）、ｉ＝ｍである場合は、処理を終了する。このようにして、ｎｂ＝βまたはｉ＝ｍが成立するまで、位置情報Ｐを更新しながらＦＢリスト（Ｐ）からフリーブロックを取得する。
【００７８】
このように、高優先リスト選択部７２は、ＦＢリストからフリーブロックＦＢを選択する際、各ＦＢリストに確保された予備ブロックを使用することができる。
【００７９】
なお、ステップＳ３１０、Ｓ４１０において最大並列度を計算する際、β＞ｍのとき、位置情報Ｐを例えば順序規則の先頭のプレーンのＦＢリストに対応する位置にするなど、位置情報Ｐを変更して、できるだけ最大並列度を確保するように制御してもよい。
【００８０】
また、上記では、ＦＢリストを選ぶ際に、単純なラウンドロビン方式を採用したが、例えば、各バンク／チップ／プレーンで発生したバッドブロックＢＢの個数（ＢＢ数）に逆対応する値（例えばＢＢ数の逆数）や各バンク／チップ／プレーンで利用可能な論理ブロック数(フリーブロックＦＢの数とアクティブブロックＡＢの数との総和)や各ＦＢリストに属するブロックの個数などで重み付けしたラウンドロビン方式により、フリーブロックＦＢを取得するリストを選ぶようにしてもよい。バッドブロックＢＢとは、誤りが多いなど記憶領域として使用できない物理ブロックのことであり、例えば、消去動作が正常に終了しなかった物理ブロックがバッドブロックＢＢとして登録される。このように、重み付けしたラウンドロビン方式によりフリーブロックＦＢを取得するリストを選ぶ方式については、特願２００９−３０２９９号において詳細に説明されている。
【００８１】
このように第１の実施形態では、ＬＢＡ動的ブロック割り当て方式によるフリーブロックリスト管理を採用し、各フリーブロックリストに、所定個数Ｒの予備ブロックを残しておき、これら予備ブロックは、ＮＡＮＤメモリ１０に高密度データの書込みが行われる場合に使用され、低密度データの書込みが行われる場合には、使用されないようにしたので、特定プレーンに存在するブロックのみを更新するような特殊な書き込みが発生したとしても、高密度トラックの書込みが行われるシーケンシャルライトの際の書込み並列度を低下させることなく、高速アクセスが可能となる。
【００８２】
なお、予備ブロック数の設定値Ｒは、各フリーブロックリスト内のバッドブロックＢＢの個数などに応じて異ならせてもよい。
【００８３】
［第２の実施形態］
つぎに、この発明の第２の実施形態について説明する。第１の実施形態での手法を用いてもフリーブロック数が各ＦＢリスト間で偏ることは避けられない。そこで、第２の実施形態では、ブロックの使用数がプレーン間（ＦＢリスト間）で偏ってしまった場合には、ホスト１からアクセスのない時間を利用して、ブロックの使用数が多いプレーンから、少ないプレーンにデータを移動し、各プレーンにおいて、ブロックの使用数が一定以下になるようにする。
【００８４】
図１４は、第２の実施形態の要部構成を示す機能ブロック図である。図１４では、図９に示したコントローラ５にブロック移動部７８を追加している。その他の構成要素は、図９に示したものと同様であり、重複する説明は省略する。
【００８５】
ブロック移動部７８は、フリーブロックの少なくなったプレーンに対応するアクティブブロックリストからアクティブブロックＡＢを解放し、解放したブロックをＦＢリストに補充する処理を行う。ブロック移動部７８は、どのフリーブロックリストに対して処理を行うかを記録するリスト位置情報７９を持つ。
【００８６】
第２の実施形態において、書込み処理の全体的な手順は、図１１を用いて説明した手順と同様であり、重複する説明は省略する。以下、図１５にしたがって、ブロック移動部７８でのデータ移動処理の手順を説明する。
【００８７】
ブロック移動部７８は、まず、リスト位置情報７９の位置情報Ｐ＝０とする（ステップＳ５００）。ブロック移動部７８は、位置情報Ｐに対応するＦＢリスト（Ｐ）にフリーブロックが（Ｒ−１）個以上残っているか否かを判定する（ステップＳ５１０）。この判定で、ＦＢリスト（Ｐ）にフリーブロックが（Ｒ−１）個以上残っていない場合、ブロック移動部７８は、同じ位置情報ＰのＡＢリスト（Ｐ）から、最も古いアクティブブロックＡＢを取得する（ステップＳ５２０）。さらに、ブロック移動部７８は、取得したアクティブブロックＡＢをＡＢリスト（Ｐ）から削除する（ステップＳ５３０）。
【００８８】
つぎに、ブロック移動部７８は、ＲＡＭ２０の作業領域に、取得したアクティブブロックＡＢの記憶データを読み出す（ステップＳ５４０）。つぎに、ブロック移動部７８は、通常優先度を指定して、フリーブロック選択部７１にフリーブロックを１つ要求する。通常優先リスト選択部７４は、図１２の手順にしたがって、フリーブロックＦＢを１つ選択する。通常優先リスト選択部７４でのＦＢリスト選択では、前述したように、フリーブロックがＲ個以上残っていないＦＢリストは選択されないので、通常優先リスト選択部７４は、ステップＳ５１０の判断がＮＯとなったＦＢリストとは異なるＦＢリストからフリーブロックを選択する。通常優先リスト選択部７４は、選択したフリーブロックのブロック識別子をブロック移動部７８に通知する（ステップＳ５５０）。
【００８９】
ブロック移動部７８は、ブロック識別子が通知されたフリーブロックに対し、ＲＡＭ２０の作業領域に読み出されたアクティブブロックＡＢの記憶データを書き込む（ステップＳ５６０）。つぎに、ブロック移動部７８は、ステップＳ５２０で選択した位置情報ＰのアクティブブロックＡＢをフリーブロックとして、同じ位置情報ＰをもつＦＢリスト（Ｐ）につなぐ（ステップＳ５７０）。さらに、ブロック移動部７８は、ステップＳ５５０で取得されたフリーブロックＦＢを、そのフリーブロックが属するプレーンに対応するＦＢリストにつなぐ（ステップＳ５８０）。つぎに、ブロック移動部７８は、同じ位置情報Ｐに対応するＦＢリスト（Ｐ）にフリーブロックが（Ｒ−１）個以上残っているか否かを再度判定し（ステップＳ５１０）、ＦＢリスト（Ｐ）にフリーブロックが（Ｒ−１）個以上残っていない場合は、ステップＳ５１０の判断がＹＥＳとなるまで、ステップＳ５２０〜Ｓ５８０の処理を繰り返す。
【００９０】
ステップＳ５１０において、フリーブロックが（Ｒ−１）個以上残っていると判定された場合は、ブロック移動部７８は、位置情報Ｐを＋１などして、位置情報Ｐを次の位置に更新する（ステップＳ５９０）。つぎに、ブロック移動部７８は、位置情報ＰがＦＢリストの最終位置になったか否かを判定し（ステップＳ６００）、位置情報ＰがＦＢリストの最終位置になるまで、上記の処理を繰り返す。位置情報ＰがＦＢリストの最終位置になった場合は、処理を終了する。
【００９１】
なお、ステップＳ５２０でのアクティブブロックの選択時に、選択された最も古いアクティブブロックＡＢが書き込まれて間もないブロックと予想できる場合は、このアクティブブロックＡＢを選択せずに、他の位置情報ＰをもつＡＢリストからアクティブブロックを選択するようにしてもよい。すなわち、短期にアクティブブロックが解放されると予想できるＡＢリストに対しては、リスト間のデータ移動処理を行わなくてもフリーブロックが増加することが期待できるため、ステップ５２０でのアクティブブロックの選択時に、そのアクティブブロックリストに対する選択を中止して、手順をステップＳ５９０に移行させることもできる。予想は、つぎのような方法で行うことができる。
【００９２】
アクティブブロックリスト毎に、当該アクティブリストに対する更新の度に＋１インクリメントされるシーケンスカウントＣを持たせ、フリーブロックにデータを書き込み、アクティブブロックリストにつなぐ際に、そのブロックにその時点のカウントＣを結びつける。以下、あるブロックｂに結びついたカウントＣをＢＣ（ｂ）と記述する。カウントＣと、アクティブブロックリスト中の最も古いブロックＡＢのＢＣ（ＡＢ）の差が小さいほど、アクティブブロックＡＢは最近書かれたものと判定でき、例えば、あるプレーンの全ブロックを順番に使う場合には、その差は、アクティブブロックリストの長さと等しくなる関係となる。
【００９３】
したがって、ステップＳ５２０で、最も古いアクティブブロックＡＢを選択したときに、ＢＣ（ＡＢ）とアクティブブロックリストのカウントＣを比較し、差が閾値以下である場合には、このアクティブブロックＡＢが最近書き込まれたと判定し、そのアクティブブロックリストからのアクティブブロックの解放をスキップし、ステップＳ５９０に移るようにする。閾値としては、アクティブブロックリストの長さに一定の係数を乗じた値などを用いてもよい。
【００９４】
このように第２の実施形態では、フリーブロック数が閾値（Ｒ−１）より少ないフリーブロック管理リストに対応するアクティブブロックリストのアクティブブロックのデータを、フリーブロック数が閾値Ｒ以上あるフリーブロック管理リストから選択したフリーブロックに移動するようにしたので、フリーブロックが少ないフリーブロックリストにフリーブロックが補充され、フリーブロック数が各フリーブロックリスト間で偏ることが回避でき、各フリーブロックリストでＲ個以上の予備ブロックを常に確保することが可能となり、動的ブロック割り当て方式においても、シーケンシャルライト性能の低下が発生し難くなる。
【００９５】
なお、図１５のステップＳ５１０で、閾値として（Ｒ−１）個を使用しているが、閾値はＲ未満の他の数値でもよい。この場合、各フリーブロックリストに常に確保される予備ブロックの数もＲよりも少なくなる。
【００９６】
なお、ブロック移動部７８でのデータ移動処理は、ホスト１からアクセスの無い時間を利用して行ってもよいし、ブロック移動部７８が、いずれかのプレーンに対応するＦＢリストにおいてフリーブロック数が（Ｒ−１）個を下回ったことを検知した場合に、他の処理よりも優先的に行ってもよい。
【００９７】
なお、上記第１、第２の実施の形態では、ＮＡＮＤメモリ１０は、複数のチャネルによってチャネル並列動作が可能に構成したが、単一チャネルでＮＡＮＤメモリ１０とドライブ制御回路４とを接続してもよい。また、上記第１、第２の実施の形態では、複数の物理ブロックにより論理ブロックを構成し、論理ブロック単位でフリーブロックリストを管理するとしたが、論理ブロックを構成せず、論理ブロック単位でフリーブロックリストを管理してもよい。
【００９８】
また、上記第１、第２の実施の形態では、フリーブロックリストを、チャネル、バンク、チップ、プレーンを使用して複数本に分類するようにしたが、不揮発性半導体メモリの仕様に応じて、チャネル、バンク、チップ、プレーンのうちの１つ以上を使用してフリーブロックリストを複数本に分類するようにしてもよい。また、フリーブロックリストの分類単位は、チャネル、バンク、チップ、プレーンに限らず、ブロックを並列動作可能なブロックの集合単位であれば、他の任意の集合単位を使用してもよい。
【００９９】
また、上記第１、第２の実施の形態では、データが高密度データであるか低密度データであるかに応じて高優先、通常優先のフリーブロック選択を行うようにしたが、他の選択基準に基づき高優先、通常優先の切り替え選択を行うようにしてもよい。例えば、ホスト１が書き込みの際にシーケンシャルライトであるかランダムライトであるかを指定する情報を付加することができるならば、シーケンシャルライトが指定されている場合は高優先、ランダムライトが指定されている場合は通常優先と判断し、切り替え選択を行うようにしてもよい。
【０１００】
また、例えば、管理テーブルの変更差分情報であるログなど、予めサイズが小さいことが分かっているデータについては、通常優先と判断するようにしてもよい。また、スタンドバイ状態に入るためにライトバッファ２１からＮＡＮＤ１０へデータを退避する場合など、高いデータ転送速度が必要とされる場合は、全てのデータを高優先と判断するようにしてもよい。また、上記第１、第２の実施の形態では、高優先及び通常優先の２つの優先度でフリーブロックリストの管理を行うこととしたが、優先度を３つ以上に分けて管理してもよい。
【０１０１】
［第３の実施の形態］
図１６は、ＳＳＤ１００を搭載したパーソナルコンピュータ１２００の一例を示す斜視図である。パーソナルコンピュータ１２００は、本体１２０１、及び表示ユニット１２０２を備えている。表示ユニット１２０２は、ディスプレイハウジング１２０３と、このディスプレイハウジング１２０３に収容された表示装置１２０４とを備えている。
【０１０２】
本体１２０１は、筐体１２０５と、キーボード１２０６と、ポインティングデバイスであるタッチパッド１２０７とを備えている。筐体１２０５内部には、メイン回路基板、ＯＤＤ（Optical  Disk  Device）ユニット、カードスロット、及びＳＳＤ１００等が収容されている。
【０１０３】
カードスロットは、筐体１２０５の周壁に隣接して設けられている。周壁には、カードスロットに対向する開口部１２０８が設けられている。ユーザは、この開口部１２０８を通じて筐体１２０５の外部から追加デバイスをカードスロットに挿抜することが可能である。
【０１０４】
ＳＳＤ１００は、従来のＨＤＤの置き換えとして、パーソナルコンピュータ１２００内部に実装された状態として使用してもよいし、パーソナルコンピュータ１２００が備えるカードスロットに挿入した状態で、追加デバイスとして使用してもよい。
【０１０５】
図１７は、ＳＳＤを搭載したパーソナルコンピュータのシステム構成例を示している。パーソナルコンピュータ１２００は、ＣＰＵ１３０１、ノースブリッジ１３０２、主メモリ１３０３、ビデオコントローラ１３０４、オーディオコントローラ１３０５、サウスブリッジ１３０９、ＢＩＯＳ−ＲＯＭ１３１０、ＳＳＤ１００、ＯＤＤユニット１３１１、エンベデッドコントローラ／キーボードコントローラＩＣ（ＥＣ／ＫＢＣ）１３１２、及びネットワークコントローラ１３１３等を備えている。
【０１０６】
ＣＰＵ１３０１は、パーソナルコンピュータ１２００の動作を制御するために設けられたプロセッサであり、ＳＳＤ１００から主メモリ１３０３にロードされるオペレーティングシステム（ＯＳ）を実行する。更に、ＯＤＤユニット１３１１が、装填された光ディスクに対して読出し処理及び書込み処理の少なくとも１つの処理の実行を可能にした場合に、ＣＰＵ１３０１は、それらの処理の実行をする。
【０１０７】
また、ＣＰＵ１３０１は、ＢＩＯＳ−ＲＯＭ１３１０に格納されたシステムＢＩＯＳ（Basic  Input  Output  System）も実行する。尚、システムＢＩＯＳは、パーソナルコンピュータ１２００内のハードウェア制御のためのプログラムである。
【０１０８】
ノースブリッジ１３０２は、ＣＰＵ１３０１のローカルバスとサウスブリッジ１３０９との間を接続するブリッジデバイスである。ノースブリッジ１３０２には、主メモリ１３０３をアクセス制御するメモリコントローラも内蔵されている。
【０１０９】
また、ノースブリッジ１３０２は、ＡＧＰ（Accelerated  Graphics  Port）バス１３１４等を介してビデオコントローラ１３０４との通信、及びオーディオコントローラ１３０５との通信を実行する機能も有している。
【０１１０】
主メモリ１３０３は、プログラムやデータを一時的に記憶し、ＣＰＵ１３０１のワークエリアとして機能する。主メモリ１３０３は、例えばＲＡＭから構成される。
【０１１１】
ビデオコントローラ１３０４は、パーソナルコンピュータ１２００のディスプレイモニタとして使用される表示ユニット１２０２を制御するビデオ再生コントローラである。
【０１１２】
オーディオコントローラ１３０５は、パーソナルコンピュータ１２００のスピーカ１３０６を制御するオーディオ再生コントローラである。
【０１１３】
サウスブリッジ１３０９は、ＬＰＣ（Low  Pin  Count）バス上の各デバイス、及びＰＣＩ（Peripheral  Component  Interconnect）バス１３１５上の各デバイスを制御する。また、サウスブリッジ１３０９は、各種ソフトウェア及びデータを格納する記憶装置であるＳＳＤ１００を、ＡＴＡインタフェースを介して制御する。
【０１１４】
パーソナルコンピュータ１２００は、セクタ単位でＳＳＤ１００へのアクセスを行う。ＡＴＡインタフェースを介して、書き込みコマンド、読出しコマンド、キャッシュフラッシュコマンド等がＳＳＤ１００に入力される。
【０１１５】
また、サウスブリッジ１３０９は、ＢＩＯＳ−ＲＯＭ１３１０、及びＯＤＤユニット１３１１をアクセス制御するための機能も有している。
【０１１６】
ＥＣ／ＫＢＣ１３１２は、電力管理のためのエンベデッドコントローラと、キーボード（ＫＢ）１２０６及びタッチパッド１２０７を制御するためのキーボードコントローラとが集積された１チップマイクロコンピュータである。
【０１１７】
このＥＣ／ＫＢＣ１３１２は、ユーザによるパワーボタンの操作に応じてパーソナルコンピュータ１２００の電源をＯＮ／ＯＦＦする機能を有している。ネットワークコントローラ１３１３は、例えばインターネット等の外部ネットワークとの通信を実行する通信装置である。
【符号の説明】
【０１１８】
１  ホスト装置、２  ＡＴＡインタフェース、４  ドライブ制御回路、５  コントローラ１０  ＮＡＮＤメモリ、２１  ライトバッファ、６０  データ読出部、６１  データ書込部、６２  データ管理部、７０  ブロック管理部、７１  フリーブロック選択部、７２  高優先リスト選択部、７３  高優先位置情報更新部、７４  通常優先リスト選択部、７８  ブロック移動部、８０  フリーブロック管理部、８０−１〜８０−ｎ  フリーブロックリスト、９０  アクティブブロック管理部、９０−１〜９０−ｎ    アクティブブロックリスト、ＡＢ  アクティブブロック、ＦＢ  フリーブロック。
【図１】
0005404483.tif 000002
【図２】
0005404483.tif 000003
【図３】
0005404483.tif 000004
【図４】
0005404483.tif 000005
【図５】
0005404483.tif 000006
【図６】
0005404483.tif 000007
【図７】
0005404483.tif 000008
【図８】
0005404483.tif 000009
【図９】
0005404483.tif 000010
【図１０】
0005404483.tif 000011
【図１１】
0005404483.tif 000012
【図１２】
0005404483.tif 000013
【図１３】
0005404483.tif 000014
【図１４】
0005404483.tif 000015
【図１５】
0005404483.tif 000016
【図１６】
0005404483.tif 000017
【図１７】
0005404483.tif 000018