(57)【要約】【課題】ホストからのデータの書き込みの要求に対する応答速度を著しく低下させることなく、追記方式におけるガベージコレクションを行うことが可能な半導体記憶装置を提供する。【解決手段】半導体記憶装置は、追記方式によって、ホストから論理アドレスが指定されたデータの書き込みの要求に応じて、半導体記憶チップに対してデータの書き込みを行ない、コンパクションにより、半導体記憶チップに対して有効データの書き込みを行なう。半導体記憶装置は、ホストからの要求に応じた書き込みの頻度とコンパクションにおける書き込みの頻度とを、予め設定された割合に応じて調整する。【選択図】図１
2011192260.tif 000002
【特許請求の範囲】
【請求項１】
複数の記憶領域を有する半導体記憶チップと、
情報処理装置から論理アドレスと対応付けられたデータである第１データの書き込みの要求を受け、前記半導体記憶チップの記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない位置に、前記第１データを書き込む第１書き込みを行う第１書き込み制御部と、
前記第１データを書き込んだ位置を示す物理アドレスと、前記第１データに対応する前記論理アドレスとの対応関係を示す対応関係情報を記憶する第１記憶部と、
既に書き込まれているデータである第２データに対応する前記論理アドレスと同じ論理アドレスと対応付けられたデータである第３データの書き込みの要求を受け、前記半導体記憶チップの記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない位置に、前記第３データを書き込む第２書き込み制御部と、
前記第２書き込み制御部により前記第３データの書き込みが行なわれた場合、前記対応関係情報を、前記論理アドレスと前記第３データに対する前記物理アドレスとの対応関係を示す前記対応関係情報に更新する第１更新部と、
前記第２データが書き込まれていた前記半導体記憶チップの記憶領域において、無効でない第４データを、消去が行われた新たな前記記憶領域に書き込む第２書き込みを行うことにより、ガベージコレクションを行う第２書き込み制御部と、
前記情報処理装置からの要求に応じた前記第１書き込みの頻度と前記ガベージコレクションにおける前記第２書き込みの頻度とを、予め設定された割合に応じて調整する頻度調整部とを備えることを特徴とする半導体記憶装置。
【請求項２】
前記頻度調整部は、
前記割合が設定されるレジスタと、
前記レジスタに設定された前記割合、前記第１書き込みが行なわれた頻度及び前記第２書き込みが行なわれた頻度に応じて、前記第１書き込み又は前記第２書き込みを行なうかを決定する決定部と、
前記決定部の決定に応じて、前記第１書き込みを前記第１書き込み制御部に行なわせる又は前記第２書き込みを前記第２書き込み制御部に行なわせる選択部とを有する
ことを特徴とする請求項１に記載の半導体記憶装置。
【請求項３】
前記物理アドレスに書き込まれたデータが無効であるか否かを示す情報である無効情報を記憶する第２記憶部と、
前記第２書き込み制御部により前記第３のデータの書き込みが行なわれた場合、前記無効情報を、前記第２データが無効であることを示す情報に変更する変更部とを更に備える
ことを特徴とする請求項１に記載の半導体記憶装置。
【請求項４】
書き込まれていた全てデータについて前記無効情報が無効であることを示す情報に変更された前記記憶領域であって書き込みがまだ行なわれていない前記記憶領域の数に応じて、前記割合の設定を更新する第２更新部を更に備える
ことを特徴とする請求項３に記載の半導体記憶装置。
【請求項５】
前記半導体記憶チップにおいて、消去が行なわれた前記記憶領域で書き込みを行なうべき位置を示すポインタを設定する設定部を更に備え、
前記設定部は、前記半導体記憶チップの記憶領域への書き込みが行われた場合、当該書き込みが行われた位置に続く新たな位置を示すよう前記ポインタを更新する
ことを特徴とする請求項１乃至４のいずれか一項に記載の半導体記憶装置。
【請求項６】
前記第１書き込み制御部は、
書き込みが要求された前記第１データのサイズが所定の単位より大きい場合、当該第１データを所定の単位毎に分割する分割部と、
分割された各前記第１データを、前記半導体記憶チップの記憶領域に各々書き込む書き込み部とを有する
ことを特徴とする請求項１乃至５のいずれか一項に記載の半導体記憶装置。
【請求項７】
前記頻度調整部は、前記所定の単位毎の前記第１書き込みの頻度と前記ガベージコレクションにおける第２書き込みの頻度とを、前記割合に応じて調整する
ことを特徴とする請求項６に記載の半導体記憶装置。
【請求項８】
前記物理アドレスに書き込まれたデータが無効であるか否かを示す情報である無効情報を記憶する第２記憶部と、
前記第２書き込み制御部により前記第３のデータの書き込みが行なわれた場合、前記無効情報を、前記第２データが無効であることを示す情報に変更する変更部とを更に備え、
前記所定の単位は、ページであり、
分割された各前記第１データは、ページ毎のデータであり、
前記第２記憶部は、前記記憶領域においてどのページが無効でないかを示す前記無効情報を記憶し、
前記変更部は、前記無効情報を、前記第２データが書き込まれていたページが無効であることを示す情報に変更する
ことを特徴とする請求項６又は７に記載の半導体記憶装置。
【請求項９】
前記第２書き込み制御部は、前記記憶領域において、前記無効情報によって無効でないことが示される前記ページに書き込まれた前記第４データを、消去が行われた新たな前記記憶領域に書き込むことにより、ガベージコレクションを行う
ことを特徴とする請求項８に記載の半導体記憶装置。
【請求項１０】
前記第２書き込み制御部は、前記記憶領域に対して、無効でない前記ページの新たな前記記憶領域への書き込みが終了した後、消去を行なう
ことを特徴とする請求項７乃至９のいずれか一項に記載の半導体記憶装置。
【請求項１１】
前記第１書き込み制御部は、所定の単位毎に分割され且つ前記論理アドレスが付加された前記第１データを前記半導体記憶チップの記憶領域に書き込み、
前記第１更新部は、前記ガベージコレクションが行なわれることにより、無効でない前記ページに書き込まれた前記第４データが新たな前記記憶領域に書き込まれた場合、当該第４データに付加された前記論理アドレスの前記対応関係情報を、当該論理アドレスと、新たな前記記憶領域において当該第４データが書き込まれた位置を示す新たな前記物理アドレスとの対応関係を示す対応関係情報に更新する
ことを特徴とする請求項７乃至１０のいずれか一項に記載の半導体記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、半導体記憶装置に関する。
【背景技術】
【０００２】
半導体記憶チップを用いた半導体記憶装置は、半導体記憶チップの一種であるNAND型のフラッシュメモリ（NANDメモリという）の容量の増大から、近年広く普及している。NANDメモリへの書き込みでは、書き込みの前に、NANDメモリを消去する必要がある。NANDメモリの消去はブロック単位、例えば、５１２KB単位で行われる。これは半導体記憶装置の上位装置であるホストからの要求に応じて行う書き込みで比較的多いデータのサイズである４KBに対して極めて大きい。４KBは、ブロックより小さい単位である例えばページのサイズに相当する。もし、データの書き込みに対して毎回消去が行われてしまうと、４KBのページ単位の書き込みに対して５１２KBのブロック単位の消去が行われることとなる。
【０００３】
一方、NANDメモリは、半導体記憶チップの特性として消去回数に上限が設定されており、この上限を超えることは信頼性の観点から望ましいことではない。消去回数を抑制するために、従来では、例えば、ファイルシステムやデータベースに古くから用いられてきたログドストラクチャが用いてられている(例えば、非特許文献１参照)。この技術では、ホストから指定された論理アドレス（Logical Block Address:LBA）とは無関係に、消去済みのブロックに４KBのページ単位でデータの書き込みをページの順に行ない、書き込みを行なった物理的な記憶位置を示す物理アドレス（Physical Block Address:PBA）と論理アドレスとの対応関係を記憶して、これを用いてデータの読み出しを行う。この方式を追記方式と呼ぶ。
【０００４】
ところで、同じ論理アドレスに対して異なるデータの書き込みの要求が複数行われることがある。これらの異なるデータが書き込まれるページは、基本的には異なる。そして、古いデータ（無効データという）が書き込まれたページは、無効となり、新たなデータ（有効データという）が書き込まれたページが有効となる。無効データの数が増えると、NANDメモリにおいて書き込みを実現可能な容量（実現容量という）が次第に少なくなってくる。そして、書き込みが可能な新規の消去済みのブロック、即ち、消去後に書き込みがまだ行なわれていないブロック（フリーブロックという）を確保できなくなると、書き込みが不能となってしまう。これを防ぐために、半導体記憶装置は、無効データの含まれているブロックの有効データを集めて新たにフリーブロックに書き直すことにより有効データを移動して、有効データを移動したブロックを無効データのみ含むブロックとして消去を行い、新たにフリーブロックを生成するガベージコレクションを行なう。追記方式によってNANDメモリにおいて行なうガベージコレクションは、特にコンパクションという。半導体記憶装置は、このようなコンパクションを行なうことにより、書き込みが不能になったブロックが新たに書き込み可能になって、フリーブロックを確保することが可能になる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Mendel Rosenblum,JohnK. Ousterhout ”The LFS Storage Manager” Summer ’90 SENIX Technical Conference, Anaheim,California, June 1990.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来では、フリーブロックがなくなった場合あるいはなくなる寸前にコンパクションを行っていた。しかし、コンパクションを行う時には有効データの読み出しと書き込みのため、NANDメモリのバンド幅を圧迫し、ホストからのデータの書き込みの要求に対する応答速度が著しく低下する恐れがあった。
【０００７】
本発明の一側面は、ホストからのデータの書き込みの要求に対する応答速度を著しく低下させることなく、追記方式におけるガベージコレクションを行うことが可能な半導体記憶装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
実施形態の半導体記憶装置は、複数の記憶領域を有する半導体記憶チップと、情報処理装置から論理アドレスと対応付けられたデータである第１データの書き込みの要求を受け、前記半導体記憶チップの記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない位置に、前記第１データを書き込む第１書き込みを行う第１書き込み制御部と、前記第１データを書き込んだ位置を示す物理アドレスと、前記第１データに対応する前記論理アドレスとの対応関係を示す対応関係情報を記憶する第１記憶部と、既に書き込まれているデータである第２データに対応する前記論理アドレスと同じ論理アドレスと対応付けられたデータである第３データの書き込みの要求を受け、前記半導体記憶チップの記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない位置に、前記第３データを書き込む第２書き込み制御部と、前記第２書き込み制御部により前記第３データの書き込みが行なわれた場合、前記対応関係情報を、前記論理アドレスと前記第３データに対する前記物理アドレスとの対応関係を示す前記対応関係情報に更新する第１更新部と、前記第２書き込み制御部により前記第３のデータの書き込みが行なわれた場合、前記第２データが書き込まれていた前記半導体記憶チップの記憶領域において、無効でない第４データを、消去が行われた新たな前記記憶領域に書き込む第２書き込みを行うことにより、ガベージコレクションを行う第２書き込み制御部と、前記情報処理装置からの要求に応じた前記第１書き込みの頻度と前記ガベージコレクションにおける前記第２書き込みの頻度とを、予め設定された割合に応じて調整する頻度調整部とを備えることを特徴とする。
【図面の簡単な説明】
【０００９】
【図１】一実施の形態の半導体記憶装置５０のハードウェア構成を例示する図。
【図２】書き込み対象データが書き込まれていく様子を時刻と共に例示する図。
【図３】コンパクションを説明するための概念図。
【図４】半導体記憶装置５０において実現される機能を例示する図。
【図５】正引きテーブルのデータ構成を例示する図。
【図６】ビットベクタテーブルのデータ構成を例示する図。
【図７】頻度調整値の更新例を説明するための図。
【図８】書き込み対象データを例示する図。
【図９】頻度調整処理の手順を示すフローチャート。
【図１０】頻度調整値更新処理の手順を示すフローチャート。
【図１１】頻度調整機能がある場合とない場合とを比較するための図。
【発明を実施するための形態】
【００１０】
以下に添付図面を参照して、この発明にかかる半導体記憶装置の実施の形態を詳細に説明する。
【００１１】
まず、本実施の形態にかかる半導体記憶装置のハードウェア構成について図１を用いて説明する。半導体記憶装置５０は、プロセッサ５１と、ＢｏｏｔＲＯＭ（Reed Only Memory）５２と、ＳＡＴＡ／ＳＡＳインタフェース５５と、メモリコントローラ５３と、ＤＲＡＭ（Dynamic Random Access Memory）５４と、ＮＡＮＤコントローラ５７Ａ〜５７Ｆと、半導体記憶素子（ＮＡＮＤ）５８Ａ〜５８Ｆと、これらを接続するバス５６とを備える。尚、ＮＡＮＤコントローラ５７Ａ〜５７Ｆを各々区別する必要がない場合、単に、ＮＡＮＤコントローラ５７と記載する場合がある。また、半導体記憶素子５８Ａ〜５８Ｆを各々区別する必要がない場合、単に、半導体記憶素子５８と記載する場合がある。
【００１２】
ＳＡＴＡ／ＳＡＳインタフェース５５は、プロセッサ５１の制御の下、半導体記憶装置５０の上位装置であるホストとの通信を制御する。ＢｏｏｔＲＯＭ５２は、電源の投入時に実行されるプログラムを記憶する。各種システムプログラムは、半導体記憶素子５８に記憶されている。プロセッサ５１は、電源の投入時にＢｏｏｔＲＯＭ５２からプログラムを読み出してこれを実行し、当該プログラムに従って、半導体記憶素子５８に記憶された各種システムプログラムをＤＲＡＭ５４に転送し、ＤＲＡＭ５４上のシステムプログラムを実行することにより、半導体記憶装置５０全体を制御して、各種機能を実現させる。具体的には、プロセッサ５１は、ＳＡＴＡ／ＳＡＳインタフェース５５を介して、ホストから送信されたコマンドを解釈し、当該コマンドに応じて、半導体記憶素子５８へのデータの書き込みや半導体記憶素子５８からのデータの読み出しを制御する。
【００１３】
メモリコントローラ５３は、ＤＲＡＭ５４の制御を行う。ＤＲＡＭ５４は、各種データや各種プログラムを記憶する。本実施の形態においては、ＤＲＡＭ５４は、後述する正引きテーブルと、ビットベクタテーブルとを記憶する。ＮＡＮＤコントローラ５７は、半導体記憶素子５８の制御を行うものであり、誤り訂正回路を含む。
【００１４】
半導体記憶素子５８は、半導体チップに相当し、例えば、NAND型のフラッシュメモリで用いられる記憶素子である。このような半導体記憶素子５８は、ランダムな読み書きができず、ページと呼ばれる単位で読み書きが可能で、複数ページがまとまってブロックと呼ばれる単位の記憶領域を構成する。ここでは、１ページ４KB、６４ページで１ブロックとする。１つの半導体記憶素子５８はこのブロックが複数あつまって構成される。尚、本実施の形態においては、図１に示されるように、半導体記憶素子５８の数を６つとしている。これらの各半導体記憶素子５８Ａ〜５８Ｆに対して各々１つのチャネル（ＣＨ０〜ＣＨ５）を割り当てる。尚、後述するように、半導体記憶装置５０は、ホストから書き込みが要求されたデータがページのサイズより大きい場合にはこれを複数に分割し、分割したページ単位のデータ（分割データという）を各チャネルＣＨ０〜ＣＨ５に割り当てて、書き込みを行う。
【００１５】
ここで、半導体記憶素子５８への書き込み方式について図２を用いて説明する。従来より、NAND型の半導体記憶素子では、上述したように、追記方式が採用されている。この追記方式では、書き込みの前に、ブロックを消去する必要がある。ブロックの消去とは、ブロックを構成する全てのビットの値を「１」にすることである。半導体記憶装置５０では、このような消去をブロック単位で行ない、消去済みのブロックに対してページ単位で書き込みを行う。即ち、NAND型の半導体記憶素子５８においては、消去済みのブロックのうち書き込みがまだ行われていないページに対して順次書き込みが可能であり、既に書き込みが行なわれたページに対する上書きが不可能である。また、ホストからの要求に応じたデータの書き込みは、ホストで用いられる論理アドレスで指定される。一方、半導体記憶素子５８へのデータの書き込みは、半導体記憶素子５８の物理アドレスにより、論理アドレスとは無関係に、ページの昇順に書き込みが行なわれる。具体的には、図２に示されるように、あるチャネルにおいて、時刻ｔ１では、最初のデータＡが、時刻ｔ０で確保された消去済みのブロックの最初（先頭又は最後尾）のページに書き込まれ、時刻ｔ２では、当該チャネルに新たに決定されたデータＢが２番目のページに書き込まれる。同様に、時刻ｔ３では、３番目のページにデータＣが書き込まれ、時刻ｔ４では、４番目のページに分割データＤが書き込まれる。このようにデータが書き込まれる記憶位置を示す物理アドレスと論理アドレスとの対応関係は、後述する正引きテーブルに記憶される。そして、データの書き込み要求において指定された論理アドレスが再度指定されて新たなデータの書き込みがホストから要求されると、半導体記憶装置５０は、消去済みのブロックの書き込みがまだ行なわれていないページに対して新たなデータの書き込みを行う。このとき、当該論理アドレスに対応して前回書き込みが行われたページを無効にして、新たなデータの書き込みが行われたページを有効にする。
【００１６】
ここで、無効とは物理アドレスの位置を論理アドレスが指していないということをいい、有効とは物理アドレスの位置を論理アドレスが指していることをいう。つまり、データの無効とは、あるデータが記憶されている記憶領域の物理アドレスの位置を論理アドレスが指していないことをいい、データの有効とは、あるデータが記憶されている記憶領域の物理アドレスの位置を論理アドレスが指していることをいう。ページの無効とは、あるページに対応する記憶領域の物理アドレスの位置を論理アドレスが指していないことをいい、ページの有効とは、あるページに対応する記憶領域の物理アドレスの位置を論理アドレスが指していることをいう。
【００１７】
この無効、有効を表現する方法として、上述の例では、ビットベクタを利用した例を示しているが、これに限られない。例えばあるブロックを選択し、ページを順に選んで、選んだページを指す論理アドレスが存在するときはそのページを有効とし、選んだページを指す論理アドレスが存在しないときはそのページを無効と判断する。論理アドレスが存在するかどうかは、正引きテーブルを順にアクセスし、選んだページを指すかどうか確認する方法を用いても良いし、物理アドレスから、論理アドレスへの逆引きテーブルを構成しておいて、物理アドレスに対応する論理アドレスが存在するかどうかを確認しても良い。
【００１８】
この追記方式において、半導体記憶装置５０では、上述したフリーブロックを確保するために、図３に例示されるように、コンパクションを行う。尚、同図に示されるように、移動により有効データが書き込まれたブロックにおいても、書き込みがまだ行なわれていないページがあればそのページに新たに書き込みが可能である。このようなコンパクションを行うためには少なくとも一つのフリーブロックが必要になるが、これは、NAND型の半導体記憶素子５８において実装されている容量（実装容量という）より、書き込みを実際に実現可能な容量が少ないことを意味している。本実施の形態においては、実装容量と実現容量との差を余裕容量と呼んでいる。余裕容量が小さい時は、半導体記憶装置５０は、コンパクションを頻繁に行わなければならず、その性能に与えるインパクトが大きい。
【００１９】
次に、半導体記憶装置５０において実現される機能について図４を用いて説明する。半導体記憶装置５０は、ホストインタフェース部６０と、バッファ制御部６１と、アドレス変換部６２と、ＣＨ振り分け部６３と、コンパクション候補検出部６４と、管理テーブル更新部６５と、ＮＡＮＤ制御部６６Ａ〜６６Ｆと、データバッファ６７と、コンパクションキュー６８と、管理テーブル６９と、ホストキュー７０と、頻度調整部７７とを有する。頻度調整部７７は、ホスト書き込みコンパクション書き込み選択部７１と、条件判定決定部７２と、ホスト書き込みカウンタ７３と、コンパクション書き込みカウンタ７４と、頻度レジスタ７５と、頻度レジスタ更新部７６とを有する。ホストインタフェース部６０の機能は、プロセッサ５１がプログラムを実行することと、ＳＡＴＡ／ＳＡＳインタフェース５５の機能とにより実現される。アドレス変換部６２と、ＣＨ振り分け部６３と、管理テーブル更新部６５と、コンパクション候補検出部６４と、バッファ制御部６１と、ホスト書き込みコンパクション書き込み選択部７１と、条件判定決定部７２と、ホスト書き込みカウンタ７３と、コンパクション書き込みカウンタ７４と、頻度レジスタ更新部７６との各機能は、プロセッサ５１がプログラムを実行することにより実現される。ＮＡＮＤ制御部６６Ａ〜６６Ｆの各機能は、ＮＡＮＤコントローラ５７Ａ〜５７Ｆに各々対応しており、プロセッサ５１がプログラムを実行することと、ＮＡＮＤ制御部６６Ａ〜６６Ｆに各々対応するＮＡＮＤコントローラ５７Ａ〜５７Ｆの機能とにより実現される。これらのＮＡＮＤ制御部６６Ａ〜６６Ｆは、上述したチャネルＣＨ０〜ＣＨ５が各々割り当てられた半導体記憶素子５８Ａ〜５８Ｆに１対１対応しているが、これらを各々区別する必要がない場合には、単にＮＡＮＤ制御部６６と記載する場合がある。データバッファ６７と、コンパクションキュー６８と、管理テーブル６９と、ホストキュー７０と、頻度レジスタ７５とは、例えば、ＤＲＡＭ５４上に記憶されるものである。
【００２０】
ホストインタフェース部６０は、ホストと半導体記憶装置５０との通信を制御するインタフェースである。ホストインタフェース部６０は、ホストから送信されたコマンドを受信し、当該コマンドによって論理アドレスが指定されたデータの書き込みが要求されている場合、当該コマンド（ｗｒｉｔｅコマンドという）をホストキュー７０に記憶させ、書き込みが要求されたデータのサイズがページのサイズ以下である場合、当該データを後述のバッファ制御部６１に送り、当該データのサイズがページのサイズより大きい場合、当該データをページ単位に分割し、分割したデータ（分割データという）をバッファ制御部６１に送る。これは論理アドレスと物理アドレスとの変換をページ単位で行っているためである。例えば、１２８ＫＢのデータを４ＫＢのデータ３２個にホストインタフェース部６０は分割する。尚、ｗｒｉｔｅコマンドに応じてバッファ制御部６１に送られるデータ又は分割データを、説明の便宜上、書き込み対象データと記載する。
【００２１】
管理テーブル６９は、正引きテーブル（ＬＢＡテーブル）と、ビットベクタテーブルとを含む。正引きテーブルとは、書き込み対象データの論理アドレスと、半導体記憶素子５８において当該書き込み対象データの書き込まれる物理的な記憶位置を示す物理アドレスとの対応関係を示すテーブルである。このような正引きテーブルは、ホストから指定された論理アドレスに対応するデータが記憶されている半導体記憶装置５８上の位置を示す物理アドレスを特定する際に用いられる。図５は、正引きテーブルのデータ構成を例示する図である。同図に示されるように、正引きテーブルのエントリは、論理アドレスをインデックスとして、これと、ブロックの番号（ブロック番号という）、チャネルの番号及びページに付与されたページ番号とをエントリとから構成される。各書き込み対象データの論理アドレスは、ホストからのデータの書き込みの要求において指定される論理アドレスに基づいて各々計算される。ブロック番号は、例えば、先頭から順にブロックに付与される。チャネルの番号は、ここでは、ＣＨ０〜ＣＨ５とし、当該論理アドレスに対応するデータが記憶されている物理ブロックのある半導体記憶素子５８がいずれのチャネルに接続されているかを示す。そしてページ番号は、当該論理アドレスに対応するデータが、ブロック番号及びチャネル番号で特定される物理ブロックの中のどのページに記憶されているかを示す。尚、ページ番号としては、例えば、物理アドレスの順に付与されるものであっても良いし、ページの物理アドレス自体が付与されても良い。このような正引きテーブルは、書き込み対象データが半導体記憶素子５８に書き込まれる度に、更新される。どのように更新されるかは後述する。
【００２２】
次に、ビットベクタテーブルについて図６を用いて説明する。ビットベクタテーブルは、各チャネルの各ブロックについて、当該ブロックに含まれるページのうち有効なデータが書き込まれているページ（有効ページという）がどのページかを２値でページ順に示すテーブルである。ページ毎に２値を示すものをビットベクタという。ビットベクタの値が「１」であれば、そのページが有効ページであることを示し、「０」であれば、そのページが有効ページではない(無効である)ページであることを示す。初期状態においては、ビットベクタの値は全て「０」である。本実施の形態においては、１ブロック当たり６４ページとしたとき、対応するビットベクタは、１つのブロック当たり６４個となる。同図に示されるように、このようなビットベクタテーブルは、上述したブロック番号をインデックスとして、これと、当該ブロック番号の付与されたブロックに各々含まれる各ページに対するビットベクタと、カウンタとをブロック毎に含む。カウンタは、値が「１」であるビットベクタの総数を示す。ビットベクタの値が「１」であるページは有効ページであるから、このカウンタは、論理ブロック内の有効ページの数を示す（以降、有効ページ数カウンタと呼ぶ）。このような構成において、ビットベクタテーブルは、ホストからのデータの書き込みの要求がある度に、更新される。どのように更新されるかは後述する。
【００２３】
図４の説明に戻る。コンパクション候補検出部６４は、管理テーブル６９に含まれるビットベクタテーブルを参照して、コンパクションの候補とするブロックを決定し、当該論理ブロックのうち有効ページの物理アドレスを指定して当該有効ページの読み出しを要求するコマンド（コンパクションｒｅａｄコマンドという）をアドレス変換部６２に送る。
【００２４】
データバッファ６７は、書き込み対象データを記憶するバッファである。コンパクションキュー６８は、コンパクションの際に有効データの書き込みを要求するコマンド（コンパクションｗｒｉｔｅコマンドという）を記憶する先入れ先出し型のバッファである。ホストキュー７０は、ホストからのｗｒｉｔｅコマンドを記憶する先入れ先出し型のバッファである。
【００２５】
頻度調整部７７は、ホストからのｗｒｉｔｅコマンドに応じた書き込みの頻度と、コンパクションにおける書き込みの頻度とを、後述の頻度レジスタ７５に設定された頻度調整値に応じて調整する。この機能を実現させるための具体的な機能は以下の通りである。ホスト書き込みカウンタ７３は、ホストからのｗｒｉｔｅコマンドに応じて行なわれた書き込みの回数をページ単位で計算する。コンパクション書き込みカウンタ７４は、コンパクションｗｒｉｔｅコマンドに応じて行われた書き込みの回数をページ単位で計算する。
【００２６】
頻度レジスタ７５は、ホストからのｗｒｉｔｅコマンドに応じた書き込みの頻度と、コンパクションにおける書き込みの頻度とを調整するための頻度調整値が設定されるレジスタである。例えば、頻度レジスタ７５には、ホストからのｗｒｉｔｅコマンドに応じた書き込みの回数とコンパクションにおける書き込みの回数との割合として、前者の書き込みの回数に対する後者の書き込みの回数の比が頻度調整値として設定される。即ち、頻度レジスタ７５には、ホストからのｗｒｉｔｅコマンドに応じた書き込みがＭ（Ｍ：正整数）回行われると、コンパクションにおける書き込みがＮ（Ｎ：正整数）回行われるように頻度設定値（Ｎ／Ｍ）が設定される。
【００２７】
頻度レジスタ更新部７６は、頻度レジスタ７５の頻度調整値の設定を更新する。具体的には、頻度レジスタ更新部７６は、フリーブロックの数に応じて、頻度調整値を更新する。図７は、頻度調整値の更新例を説明するための図である。フリーブロックが少なくなり、その数が下限閾値を下回った場合、頻度レジスタ更新部７６は、例えば、頻度調整値を「３」に設定し、ホストからのｗｒｉｔｅコマンドに応じた書き込みの３倍のコンパクションにおける書き込みが実行されるようにする。コンパクションにおける書き込みが多く実行されると、コンパクションの結果としてフリーブロックが増え、その数が増える。フリーブロックの数が下限閾値から上限閾値の間にある場合、頻度レジスタ７５は、頻度調整値を「２」に設定し、ホストからのｗｒｉｔｅコマンドに応じた書き込みの２倍のコンパクションにおける書き込みが実行されるようにする。コンパクションの結果、フリーブロックの数が上限閾値を越えた場合、頻度レジスタ更新部７６は、頻度調整値を「０」に設定し、ホストからのｗｒｉｔｅコマンドに応じた書き込みのみが実行されるようにする。尚、下限閾値より上限閾値は大きい値であり、これらの値は予め定められてＤＲＡＭ５４に記憶されているものとする。なお、ホスト書き込みカウンタ７２および、コンパクション書き込みカウンタ７４は、頻度レジスタ７５に設定された値に達するとリセットされる。例えば、頻度調整値「３」の場合、ホスト書き込みカウンタ７２は「１」、コンパクション書き込みカウンタ７４が「３」で双方ともリセットされる。
【００２８】
条件判定決定部７２は、頻度レジスタ７５に設定された頻度調整値、ホスト書き込みカウンタ７３によって計算された値及びコンパクション書き込みカウンタ７４によって計算された値に応じて、ホストからのｗｒｉｔｅコマンドに応じた書き込みを行なうか又はコンパクションにおける書き込みを行なうかを決定し、いずれを決定したかを示す決定結果をホスト書き込みコンパクション書き込み選択部７１に送る。
【００２９】
ホスト書き込みコンパクション書き込み選択部７１は、条件判定決定部７２から決定結果を受け取り、ホストからのｗｒｉｔｅコマンドに応じた書き込みを行なうことが決定されたことが決定結果により示される場合、ホストキュー７０からｗｒｉｔｅコマンドを取り出して、これをＣＨ振り分け部６３に送る。即ち、この場合、ホスト書き込みコンパクション書き込み選択部７１は、ＣＨ振り分け部６３を介して、ホストからのｗｒｉｔｅコマンドに応じた書き込みをＮＡＮＤ制御部６６に行なわせる。一方、コンパクションにおける書き込みを行なうことが決定されたことが決定結果により示される場合、コンパクションキュー６８からコンパクションｗｒｉｔｅコマンドを取り出し、これをＣＨ振り分け部６３に送る。即ち、この場合、ホスト書き込みコンパクション書き込み選択部７１は、ＣＨ振り分け部６３を介して、コンパクションにおける書き込みをＮＡＮＤ制御部６６に行なわせる。
【００３０】
図４の説明に戻る。アドレス変換部６２は、コンパクション候補検出部６４からコンパクションｒｅａｄコマンドを受け取り、正引きテーブルを参照して、当該コンパクションｒｅａｄコマンドによって物理アドレスで指定された有効ページのデータ（有効データ）の読み出しを要求するコマンドを、当該有効ページのある物理ブロックを含む半導体記憶素子５８が接続されたチャネルに対応するＮＡＮＤ制御部６６に送る。当該有効データは、ＮＡＮＤ制御部６６を介して半導体記憶素子５８から読み出され、バッファ制御部６１を介してデータバッファ６７に記憶される。アドレス変換部６２は、この有効データの書き込みを要求するコマンド（コンパクションｗｒｉｔｅコマンド）をコンパクションキュー６８に記憶させる。
【００３１】
ＣＨ振り分け部６３は、ホスト書き込みコンパクション書き込み選択部７１からコマンドを受け取り、当該コマンドがｗｒｉｔｅコマンドである場合、書き込み対象データを書き込む対象のチャネルを決定する。例えば、ＣＨ振り分け部６３は、４ＫＢ毎にラウンドロビンにより書き込みを行うようにし、ラウンドロビンの順番に応じて、書き込み先のチャネルを決定する。そして、ＣＨ振り分け部６３は、書き込み対象データの書き込みを要求するコマンドを、決定したチャネルに対応するＮＡＮＤ制御部６６に送る。また、ホスト書き込みコンパクション書き込み選択部７１から受け取ったコマンドがコンパクションｗｒｉｔｅコマンドである場合、ＣＨ振り分け部６３は、書き込み先のチャネルを決定し、有効データの書き込みを要求するコマンドを、決定したチャネルに対応するＮＡＮＤ制御部６６に送る。
【００３２】
ＮＡＮＤ制御部６６は、ＣＨ振り分け部６３からコマンドを受け取り、当該コマンドに従って、対応する半導体記憶素子５８にアクセスする。具体的には、当該コマンドによって、データの書き込みが要求されている場合、ＮＡＮＤ制御部６６は、バッファ制御部６１を介して書き込み対象データを取得して、当該書き込み対象データを半導体記憶素子５８に書き込む。この書き込みにおいて、ＮＡＮＤ制御部６６は、対応する半導体記憶素子５８の消去済みのブロックのうち書き込みがまだ行なわれていないページ毎に書き込みの位置を順次示すよう追記ポインタを設定し、追記ポインタによって示される位置のページに書き込み対象データを書き込み、その後、新たなページの位置を示すよう追記ポインタを更新する。従って、追記ポインタは順次次の書き込み位置を示すようにその値が変化する。例えば、追記ポインタは、各チャネルにおいて15ビットの物理アドレスによりブロックが識別され、ブロック内に64ページある場合、合計15+6=21ビットで構成される。
【００３３】
ここで、書き込み対象データのデータ構成について説明する。ＮＡＮＤ制御部６６は、書き込み対象データ自体の誤りを検出して訂正するための誤り訂正符号（ページＥＣＣという）及びｗｒｉｔｅコマンドによって指定された論理アドレスを当該書き込み対象データに付加する。尚、ページＥＣＣには、データの誤りを検出するＣＲＣ符号等の符号と、データの誤りを訂正するＥＣＣ符号等の符号とが含まれるものとする。ページＥＣＣにＣＲＣ符号も含む理由は、ＥＣＣ符号によりデータの誤りを訂正できない場合は誤訂正の可能性もあるからである。図８は、冗長部分が付加された書き込み対象データを例示する図である。上述のように決定された各チャネルの半導体記憶素子５８において、ＮＡＮＤ制御部６６は、このようなページＥＣＣ及び論理アドレスを付加した書き込み対象データを、追記ポインタにより示される半導体記憶素子５８内のページに書き込む。尚、書き込み対象データはページ単位の大きさであるが、半導体記憶素子５８のページサイズは、書き込み対象データにページＥＣＣ及び論理アドレスが付加された全体の大きさに相当するものとする。また、各分割データの論理アドレスは、ｗｒｉｔｅコマンドによって指定された論理アドレスに基づいてＮＡＮＤ制御部６６が各々計算する。
【００３４】
また、ＮＡＮＤ制御部６６は、アドレス変換部６２から受け取ったコマンドによって、物理アドレスが指定された有効ページのデータ（有効データ）の読み出しが要求されている場合、当該物理アドレスを用いて半導体記憶素子５８内の当該物理アドレスに対応するページに書き込まれたデータを読み出して、これをデータバッファ６７に記憶させる。また、ＣＨ振り分け部６３から受け取ったコマンドによって、有効データの書き込みが要求されている場合、ＮＡＮＤ制御部６６は、バッファ制御部６１を介して書き込み対象の有効データを取得して、当該有効データを半導体記憶素子５８に書き込む。
【００３５】
バッファ制御部６１は、データバッファ６７を複数の領域として管理し、コマンドに対応したデータを記憶させる領域を管理する。具体的には、バッファ制御部６１は、ｗｒｉｔｅコマンドに応じてホストインタフェース部６０から送られた書き込み対象データをデータバッファ６７に記憶させ、ＣＨ振り分け部６３により書き込み対象として決定されたチャネルに対応するＮＡＮＤ制御部６６に該当の書き込み対象データを送る。当該書き込み対象データは、ＮＡＮＤ制御部６６を介して半導体記憶素子５８に書き込まれる。また、バッファ制御部６１は、コンパクションｒｅａｄコマンドに応じて、ＮＡＮＤ制御部６６を介して半導体記憶素子５８から読み出されたデータをデータバッファ６７に記憶させ、記憶させたデータをＮＡＮＤ制御部６６に転送し、半導体記憶素子５８に書き込む。
【００３６】
管理テーブル更新部６５は、論理アドレスが指定されたデータの書き込みを要求するコマンド（ｗｒｉｔｅコマンド）がホストから受信された場合、正引きテーブルを参照すると共に、ビットベクタテーブルを更新し、更に、正引きテーブルを更新する。具体的には、管理テーブル更新部６５は、まず、正引きテーブルを参照して、当該論理アドレスに対応する物理アドレス、即ち、当該論理アドレスに対応するデータがどのブロックのページに書き込まれているかを検索する。当該論理アドレスに対応する物理アドレスが正引きテーブルに記憶されていない場合は、当該論理アドレスに対応するデータの書き込みは今回まで行なわれていないことになる。この場合、管理テーブル更新部６５は、当該論理アドレスに対応するデータを書き込む対象のページに対するビットベクタの値を「１」にする。データを書き込む対象のページは、追記ポインタにより示される。また、管理テーブル更新部６５は、当該ページの含まれるブロックに対応する有効ページ数カウンタの値を１インクリメントする。
【００３７】
一方、管理テーブル更新部６５が正引きテーブルを参照したときに当該論理アドレスに対応する物理アドレスが正引きテーブルに記憶されている場合、当該論理アドレスに対応するデータの書き込みが以前に行なわれていることになる。この場合、今回のｗｒｉｔｅコマンドにより、以前に書き込みが行なわれたデータを無効にする必要がある。このため、管理テーブル更新部６５は、ｗｒｉｔｅコマンドにより指定された論理アドレスで参照した正引きテーブルのエントリに記憶されている物理アドレスのページ対応するビットベクタの値を「０」にする。当該ページの存在する物理ブロックが関連付けられたる論理ブロックの有効ページ数カウンタの値を１デクリメントする。また、管理テーブル更新部６５は、書き込み対象データを書き込むページに対応するビットベクタの値を「１」にし、当該ページの存在する物理ブロックが関連付けられた論理ブロックの有効ページ数カウンタの値を１インクリメントする。このようにデータの書き込みが行なわれる度に更新することで、ビットベクタテーブルと有効ページ数カウンタとは有効ページの位置及びその数を常に示している。最後に管理テーブル更新部６５は、当該論理アドレスに対応する正引きテーブルのエントリに、書き込み対象データを書き込む先の物理アドレスを記録する。
このようなビットベクタテーブルは、データの書き込みが行なわれる度に更新されることで、有効ページ及びその数を常に示している。また、コンパクションを行った際には、管理テーブル更新部６５は、有効データを移動した先のページの物理アドレスを正引きテーブルにおいて更新する。
【００３８】
次に、本実施の形態にかかる半導体記憶装置５０の行う処理の手順について説明する。まず、頻度調整処理の手順について図９を用いて説明する。尚、頻度レジスタ７５の頻度調整値は「Ｎ／Ｍ」が設定されているものとする。半導体記憶装置５０は、ホストキュー７０にｗｒｉｔｅコマンドがあるか否かを判断する（ステップＳ１）。ｗｒｉｔｅコマンドがない場合（ステップＳ１：ＮＯ）、ステップＳ１に戻る。ｗｒｉｔｅコマンドがある場合（ステップＳ１：ＹＥＳ）、半導体記憶装置５０は、ホストからのｗｒｉｔｅコマンドに応じた書き込みを行なうことを決定し、ホストキュー７０から１つのｗｒｉｔｅコマンドを取り出し、当該ｗｒｉｔｅコマンドにより書き込みが要求されたデータのサイズがページのサイズ以下である場合、当該データ（書き込み対象データ）をデータバッファ６７に記憶させ、ｗｒｉｔｅコマンドにより書き込みが要求されたデータのサイズがページのサイズより大きい場合、当該データをページ単位で分割し、分割したデータ（分割データ：書き込み対象データ）をデータバッファ６７に記憶させる。
【００３９】
そして、半導体記憶装置５０は、書き込み対象データの書き込みをページ単位で１回行なう（ステップＳ２）。具体的には、半導体記憶装置５０は、ｗｒｉｔｅコマンドにより指定された論理アドレスに基づいて正引きテーブルを参照して、書き込み対象データの論理アドレスに対応する物理アドレスが既に記憶されている場合、当該物理アドレスを古い物理アドレスとして例えばＤＲＡＭ５４に記憶させる。また、半導体記憶装置５０は、書き込み対象データを書き込むチャネルを決定し、決定したチャネルの半導体記憶素子５８において追記ポインタで示されるページに、ページＥＣＣ及び論理アドレスを各々付加した書き込み対象データを書き込む。そして、半導体記憶装置５０は、書き込み対象データを書き込んだページに続く次のページであって書き込みがまだ行われていないページを示すよう追記ポインタを更新する。また、半導体記憶装置５０は、書き込み対象データの論理アドレスと、書き込み対象データを書き込んだページの物理アドレスとの対応関係を、図５に例示した正引きテーブルに記録する。書き込み対象データが分割データである場合、半導体記憶装置５０は、各分割データの物理アドレスを、ｗｒｉｔｅコマンドにより指定された論理アドレスに基づいて各々計算する。分割データは、ページ単位であるから、指定された論理アドレスに対してページのサイズを順次加算した値を各分割データの論理アドレスとして半導体記憶装置５０は計算する。そして、半導体記憶装置５０は、論理アドレスと、書き込み対象データを各々書き込んだ各チャネルのブロックに付与されたブロック番号と、書き込み対象データを今回書き込んだチャネルの番号及びページ番号とを正引きテーブルに記録する。半導体記憶装置５０は、このようにして正引きテーブルを更新する。更に、半導体記憶装置５０は、ビットベクタテーブルを参照して、ステップＳ２でＤＲＡＭ５４に記憶させた古い物理アドレスのページに対応するビットベクタの値を「０」にし、当該ページの含まれるブロックの有効ページ数カウンタの値を１デクリメントする。古い物理アドレスとは、即ち、ｗｒｉｔｅコマンドにより指定された論理アドレスに対応して以前にデータが書き込まれているページを示している。このため、当該ページに書き込まれたデータを無効にするため、ビットベクタの値を「０」にして、当該ページの含まれるブロックの有効ページの数を１つ減らしている。また、半導体記憶装置５０は、ビットベクタテーブルにおいて、書き込み対象データを書き込んだページに対応するビットベクタの値を「１」にし、当該ページの含まれるブロックの有効ページ数カウンタの値を１インクリメントする。半導体記憶装置５０は、このようにしてビットベクタテーブルを更新する。
【００４０】
その後、半導体記憶装置５０は、ホスト書き込みカウンタ７３の値を１インクリメントし、当該値が「Ｍ」になったか否かを判断する(ステップＳ３)。当該値が「Ｍ」ではない場合(ステップＳ３：ＮＯ)、ステップＳ１に戻る。尚、半導体記憶装置５０は、ホストからのｗｒｉｔｅコマンドにより書き込みが要求されたデータをページ単位に分割した場合、まだ書き込みを行なっていない分割データがあれば、ステップＳ２に戻って、分割データ毎の書き込みを行なう。即ち、半導体記憶装置５０は、ページ単位の分割データ毎に１回ずつステップＳ２の処理を行う。
【００４１】
一方、ホスト書き込みカウンタ７３の値が「Ｍ」である場合(ステップＳ３：ＹＥＳ)、半導体記憶装置５０は、ホスト書き込みカウンタ７３の値を「０」に初期化すると共に、コンパクションにおける書き込みを行なうことを決定し、コンパクションキュー６８にコンパクションｗｒｉｔｅコマンドがあるか否かを判断する（ステップＳ４）。コンパクションｗｒｉｔｅコマンドがない場合（ステップＳ４：ＮＯ）、ステップＳ４に戻る。コンパクションｗｒｉｔｅコマンドがある場合（ステップＳ４：ＹＥＳ）、半導体記憶装置５０は、１つのコンパクションｗｒｉｔｅコマンドを取り出して、当該コンパクションｗｒｉｔｅコマンドに応じて、有効データの書き込みをページ単位で１回行なう（ステップＳ５）。この書き込みはステップＳ２と同様である。尚、有効データに対応する論理アドレスは、当該有効データに付加されているものを用いる。
【００４２】
その後、半導体記憶装置５０は、コンパクション書き込みカウンタ７４の値を１インクリメントし、当該値が「Ｎ」になったか否かを判断する(ステップＳ６)。当該値が「Ｎ」ではない場合(ステップＳ６：ＮＯ)、ステップＳ４に戻る。当該値が「Ｎ」である場合(ステップＳ６：ＹＥＳ)、半導体記憶装置５０は、コンパクション書き込みカウンタ７４の値を「０」に初期化すると共に、コンパクションの候補となるブロックがあるか否かを判断する（ステップＳ７）。具体的には、半導体記憶装置５０は、ビットベクタテーブルの有効ページ数カウンタの値を参照して、その値が所定の値以下のブロック、即ち、有効ページ数が所定の値より少ないブロックがあるか否かを判断する。そして、該当のブロックがなかった場合（ステップＳ７：ＮＯ）、処理を終了する。一方、該当のブロックがあった場合（ステップＳ７：ＹＥＳ）、半導体記憶装置５０は、当該ブロックをコンパクションの候補とし、当該ブロックについてビットベクタテーブルのビットベクタが「１」を示すページ（有効ページ）に記憶されているデータ（有効データ）を特定し、当該有効データをデータバッファ６７に全て読み出す。また、半導体記憶装置５０は、当該有効データに付加されている論理アドレスを抽出する。そして、半導体記憶装置５０は、読み出した各有効データの書き込みを要求するコンパクションｗｉｒｔｅコマンドをコンパクションキュー６８に記憶させて、ステップＳ１に戻る。
【００４３】
以上のように、ホストからの要求に応じた書き込みと、コンパクションにおける書き込みとを予め設定された頻度調整値に応じて切り替えて行う。即ち、本実施の形態においては、コンパクションによって新たなフリーブロックが生成されるのを待機するのではなく、ホストからの要求に応じた書き込みの頻度と、コンパクションにおける書き込みの頻度とが調整され、いずれかの書き込みが適宜切り替えられる。そのため、ホストからの要求に応じた書き込みがコンパクションの終了を待って行われるためにレーテンシが増大する恐れを回避することができる。
【００４４】
図１１は、本実施の形態に係る頻度調整処理を行う機能（頻度調整機能）がある場合と当該頻度調整機能がない場合とでホストからの要求に応じた書き込みのバンド幅の相違を時間の経過と共に例示する図である。同図の上段に示されるように、頻度調整機能がない場合、コンパクションにおける書き込みが行なわれている間は、複数ページに亘って各有効データの書き込みが行なわれるため、ホストからの要求に応じた書き込みが長時間に亘って中断され得る。一方、本実施の形態のように頻度調整機能がある場合、同図の下段に示されるように、頻度調整値に応じて、例えば、ホストからの要求に応じた書き込みを１ページ行なうと、コンパクションにおける書き込みを２ページ行なう、というように書き込みが交互に切り替えられる。このため、ホストからの要求に応じた書き込みが長時間に亘って中断される恐れを回避することができる。従って、本実施の形態によれば、ホストからのデータの書き込みの要求に対する応答速度を著しく低下させることなく、コンパクションを行うことが可能になる。
【００４５】
次に、コンパクションにおける書き込みの頻度を変更するための頻度調整値更新処理の手順について図１０を用いて説明する。半導体記憶装置５０は、フリーブロックの数が上限閾値以下であるか否かを判断する（ステップＳ２０）。フリーブロックの数が上限閾値より大きい場合（ステップＳ２０：ＮＯ）、半導体記憶装置５０は、頻度レジスタ７５の頻度調整値を「０」に設定する、即ち、ホストからのｗｒｉｔｅコマンドに応じた書き込み１回に対してコンパクションにおける書き込みの回数を「０」にして、コンパクションにおける書き込みが行なわれないように頻度調整値を設定する（ステップＳ２１）。フリーブロックの数が上限閾値以下である場合（ステップＳ２０：ＹＥＳ）、半導体記憶装置５０は、フリーブロックの数が下限閾値以上であるか否かを判断する（ステップＳ２２）。フリーブロックの数が下限閾値以上である場合（ステップＳ２２：ＹＥＳ）、半導体記憶装置５０は、頻度レジスタ７５の頻度調整値を「２」に設定する、即ち、ホストからのｗｒｉｔｅコマンドに応じた書き込み１回に対してコンパクションにおける書き込みが２回行なわれるように頻度調整値を設定する（ステップＳ２３）。フリーブロックの数が下限閾値より小さい場合（ステップＳ２２：ＮＯ）、半導体記憶装置５０は、頻度レジスタ７５の頻度調整値を「３」に設定する、即ち、ホストからのｗｒｉｔｅコマンドに応じた書き込み１回に対してコンパクションにおける書き込みが３回行なわれるように頻度調整値を設定する（ステップＳ２４）。以上のようにして、半導体記憶装置５０は、フリーブロックの数に応じて、頻度調整値を更新する。
【００４６】
以上のように、頻度調整値をフリーブロックの数に応じてダイナミックに更新する。即ち、フリーブロックの数が下限閾値より少なくなった場合には、コンパクションにおける書き込みがより多く行われるよう頻度調整値を更新する。これにより、コンパクションが頻繁に行われ、その結果フリーブロックを増やすことができる。逆にフリーブロックの数が上限閾値より多くなった場合には、コンパクションにおける書き込みが行なわれないように頻度調整値を更新する。これにより、無駄にコンパクションが行われることなく、ホストからの要求に応答性良く応じることができる。このように、消去済みブロックの数に応じて、頻度調整値を更新して、追記方式におけるコンパクションの頻度を調整することで、ホストからのデータの書き込みの要求に対する応答速度を極端に悪化させないようにすることができる。
【００４７】
即ち、本実施の形態によれば、ホストからのデータの書き込みの要求に対する応答速度を著しく低下させることなく、追記方式におけるガベージコレクションを行うことが可能になる。
【００４８】
[変形例]
なお、本発明は前記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、前記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。また、以下に例示するような種々の変形が可能である。
【００４９】
上述した実施の形態において、半導体記憶装置５０で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供するように構成しても良い。
【００５０】
上述した実施の形態において、正引きテーブル及びビットベクタテーブルは、ＤＲＡＭ５４に記憶されるようにしたが、これに限らず、例えば、半導体記憶素子５８に記憶され、プロセッサ５１がこれらのテーブルを使用する際にＤＲＡＭ５４にキャッシュするようにしても良い。
【００５１】
上述した実施の形態において、ページECCとしてはページ単位のデータ毎にECC符号を付加しているが、ページより小さな単位（例として５１２バイトのセクター単位）でECC符号を付加することも可能である。
【００５２】
上述した実施の形態において、半導体記憶装置５０は、ホストからのｗｒｉｔｅコマンドに応じた書き込みと、コンパクションにおける書き込みとはページ単位を１回として各々行なうようにしたが、これに限らない。例えば、２ページの書き込みを１回とするようにしても良いし、ページ以外の単位での書き込みを１回とするようにしても良い。
【００５３】
上述した実施の形態において、チャネルと半導体記憶素子５８とは１対１対応させるようにしたが、これに限らず、チャネルと半導体記憶素子５８とが１対多対応させる、即ち、１つのチャネルに対して複数の半導体記憶素子５８が割り当てられるようにしても良い。この場合、各半導体記憶素子５８にはこれらを識別するための識別番号を付与するようにする。正引きテーブルには、チャネル毎の各ブロックについて、この識別番号及びブロック番号を記録するようにする。例えば、各チャネルに８個の半導体記憶素子に割り当てられる場合、各半導体記憶素子を識別するのに3ビット、各半導体記憶素子に含まれる4096個のブロックを識別するのに12ビットで合計15ビットを、識別番号及びブロック番号を正引きテーブルに記録するようにする。
【００５４】
上述した実施の形態において、半導体記憶装置５０は、半導体記憶素子５８を複数備えるようにしたが、これに限らず、半導体記憶素子５８を１つのみ備えるようにしても良い。
【００５５】
上述した実施の形態において、半導体記憶装置５０は、半導体記憶素子５８に書き込むデータに論理アドレスが付加するようにしたが、これを付加するのではなく、半導体記憶素子５８に書き込まれたデータの物理アドレスと、当該データの論理アドレスとの対応関係を示す物論変換テーブルを更に備えるようにしても良い。そして、コンパクションの際に、半導体記憶装置５０は、半導体記憶素子５８から読み出した有効データの物理アドレスを用いて、正引きテーブルを参照して、当該物理アドレスに対応する論理アドレスを取得し、これを用いて、コンパクションに伴う正引きテーブルの更新を行うようにすれば良い。
【００５６】
上述した実施の形態において、頻度調整値の設定や更新は、上述の例に限らない。また、半導体記憶装置５０は、頻度レジスタ更新部７６を備えず、頻度調整値を固定値にして、頻度調整値を更新しないようにしても良い。
【００５７】
上述した実施の形態において、ホストからのｗｒｉｔｅコマンドに応じた書き込みを行なう書き込み制御部及びコンパクションにおける書き込みを行なう書き込み制御部が、ＮＡＮＤ制御部６６であるように構成したが、これらの各書き込みを各々異なる書き込み制御部が行うように構成しても良い。
【符号の説明】
【００５８】
５０  半導体記憶装置
５１  プロセッサ
５２  ＢｏｏｔＲＯＭ
５３  メモリコントローラ
５４  ＤＲＡＭ
５５  ＳＡＴＡ／ＳＡＳインタフェース
５６  バス
５７，５７Ａ〜５７Ｆ  ＮＡＮＤコントローラ
５８，５８Ａ〜５８Ｆ  半導体記憶素子
６０  ホストインタフェース部
６１  バッファ制御部
６２  アドレス変換部
６３  ＣＨ振り分け部
６４  コンパクション候補検出部
６５  管理テーブル更新部
６６，６６Ａ〜６６Ｆ  ＮＡＮＤ制御部
６７  データバッファ
６８  コンパクションキュー
６９  管理テーブル
７０  ホストキュー
７１  ホスト書き込みコンパクション書き込み選択部
７２  条件判定決定部
７３  ホスト書き込みカウンタ
７４  コンパクション書き込みカウンタ
７５  頻度レジスタ
７６  頻度レジスタ更新部
７７  頻度調整部
【図１】
2011192260.tif 000003
【図２】
2011192260.tif 000004
【図３】
2011192260.tif 000005
【図４】
2011192260.tif 000006
【図５】
2011192260.tif 000007
【図６】
2011192260.tif 000008
【図７】
2011192260.tif 000009
【図８】
2011192260.tif 000010
【図９】
2011192260.tif 000011
【図１０】
2011192260.tif 000012
【図１１】
2011192260.tif 000013