(57)【要約】      （修正有）【課題】半導体記憶チップへの書き込み回数が増大するのを抑制する半導体記憶制御装置を提供する。【解決手段】半導体記憶チップの有する記憶領域のうち消去された記憶領域で書き込みがまだ行なわれていない記憶位置に所定の単位の第１データを各々書き込む。第３テーブル及びこのサブセットである第２テーブルは、半導体記憶チップにおける第１データの記憶位置を示す物理アドレスを有し、第１テーブルは、論理アドレスを示す情報の一部と、第２テーブルが記憶される記憶領域の中で物理アドレスが記憶される記憶領域を特定する第１の特定情報又は第３テーブルが記憶される記憶領域の中で前記物理アドレスが記憶される記憶領域を特定する第２の特定情報とを対応付けた情報を有する。第１テーブルを揮発性メモリに記録して、第２テーブルを前記揮発性メモリに記録するか、または、第１テーブルを揮発性メモリに記録して第３テーブルを不揮発性メモリに記録する。【選択図】図１
2012068863.tif 000002
【特許請求の範囲】
【請求項１】
情報処理装置で用いられる論理アドレスが指定されて書き込みが要求されたデータである書込要求データを半導体記憶チップへ書き込む半導体記憶制御装置であって、
前記書込要求データは、１つ以上の所定の単位の第１データを有し、
物理アドレスは、半導体記憶チップにおける前記第１データの記憶位置を示す情報であり、
第１テーブル及び第２テーブルは揮発性のメモリに記憶され、
第３テーブルは不揮発性のメモリに記憶され、前記半導体記憶チップにおける前記第１データの記憶位置を示す前記物理アドレスを有し、
前記第２テーブルは、前記第３テーブルのサブセットであり、前記半導体記憶チップにおける前記第１データの記憶位置を示す前記物理アドレスを有し、
前記第１テーブルは、前記論理アドレスを示す情報の一部と、前記第２テーブルが記憶される記憶領域の中で前記物理アドレスが記憶される記憶領域を特定する第１の特定情報とを対応付けた情報、または、前記論理アドレスを示す情報の一部と、前記第３テーブルが記憶される記憶領域の中で前記物理アドレスが記憶される記憶領域を特定する第２の特定情報とを対応付けた情報を有し、
前記書込要求データを受け付ける受付部と、
前記第１データと、前記半導体記憶チップの有する記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない記憶位置に前記第１データを各々書き込む制御部と、
前記第１テーブルを前記揮発性メモリに記録して、前記第２テーブルを前記揮発性メモリに記録するか、または、前記第１テーブルを前記揮発性メモリに記録して、前記第３テーブルを前記不揮発性メモリに記録する記録部とを備える
ことを特徴とする半導体記憶制御装置。
【請求項２】
前記記録部は、前記制御部が前記第１データを前記半導体記憶チップに書き込んだ場合、前記物理アドレスを前記第２テーブルが記憶される記憶領域に記録し、所定の条件が成立した場合、前記第２テーブルの有する前記物理アドレスを前記第３テーブルが記憶される記憶領域に記録する
ことを特徴とする請求項１に記載の半導体記憶制御装置。
【請求項３】
前記記録部は、所定の条件が成立した場合、前記第２テーブルの有する前記物理アドレスを前記第３テーブルが記憶される記憶領域に記録する際、前記物理アドレスと、前記第３テーブルが記憶される記憶領域の中で当該物理アドレスを記録する第１記憶領域に既に記憶されている他の物理アドレスとをマージして、マージした各前記物理アドレスを前記第１記憶領域に記録する
ことを特徴とする請求項２に記載の半導体記憶制御装置。
【請求項４】
前記記録部は、前記情報処理装置から第１論理アドレスが指定された前記書込要求データが受け付けられた場合且つ前記第１論理アドレスを示す情報の一部と前記第２の特定情報とを対応付けた情報を前記第１テーブルが既に有する場合、前記第２の特定情報によって特定される前記記憶領域に記憶されている各物理アドレスを、前記第２テーブルが記憶される記憶領域に記録し、前記第１論理アドレスを示す情報の一部と、前記各物理アドレスが記憶された前記記憶領域を特定する前記第１の特定情報とを対応付けた情報を前記第１テーブルが記憶される記憶領域に記録する
ことを特徴とする請求項１乃至３のいずれか一項に記載の半導体記憶制御装置。
【請求項５】
前記記録部は、前記第３テーブルが記憶される記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない記憶位置に前記物理アドレスを書き込むことにより、前記第３テーブルが記憶される記憶領域に前記物理アドレスを記録する
ことを特徴とする請求項１乃至４のいずれか一項に記載の半導体記憶制御装置。
【請求項６】
前記記録部は、更に、前記第３テーブルが記憶される記憶領域の中で、前記第１テーブルの有する前記情報によって対応付けられた前記第２の特定情報によって特定されない記憶領域に記憶されている第２物理アドレスを、消去が行われた新たな記憶領域に書き込むことにより、ガベージコレクションを行う
ことを特徴とする請求項５に記載の半導体記憶制御装置。
【請求項７】
前記第３テーブルは、前記半導体記憶チップに記憶される
ことを特徴とする請求項１乃至６のいずれか一項に記載の半導体記憶制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、半導体記憶制御装置に関する。
【背景技術】
【０００２】
不揮発性の半導体記憶チップで最も広く使われているのはNAND型のフラッシュメモリ（NANDフラッシュメモリという）である。NANDフラッシュメモリでは、最小の記録単位はページであり、ページ単位での書き込みが行われる。ページは消去してからでないと書き込みができない。また、消去はページ毎にすることはできず、予め定められた複数ページの単位（ブロック）で消去される。もし、半導体記憶チップの上位装置であるホストからデータの書き込みが要求される際に指定されるアドレス(論理アドレスという)と、NANDフラッシュメモリにおいて当該データを書き込みするページ（物理アドレスという）とを固定した関係とすると、データの書き込みが要求される度にブロックを消去し、消去済みのブロックにデータの書き込みを行う。この時、同ブロック中のデータの書き込みが起こらなかったページも同時に消去されてしまうので、消去されてしまうページに書き込まれていたデータを例えばＤＲＡＭなどの他のメモリに一度移動させ、ブロックを消去してから、書き込みが要求されたデータと他のメモリに移動させたデータとを合わせて書き込む方法が考えられる。
【０００３】
一方、上記のように、論理アドレスと物理アドレスとを固定した関係とすると、論理アドレスの書き込み回数の偏りがそのまま物理アドレスの書き込み回数の偏りとなり、特定の物理アドレスの領域に書き込みが集中することが起こり得る。NAND型のフラッシュメモリでは、書き込み回数が多くなると、素子が疲労するという特性があり、記憶領域の全域にわたって書き込み回数をなるべく均質に保ち、システムの寿命を長くしたいという要請がある。記憶領域の全域にわたって書き込み回数をなるべく均質に保つためには、領域ごとの書き込み回数を管理し、書き込み回数の少ない領域に書き込みを行うように、論理アドレスと物理アドレスの関係を管理する。
【０００４】
以上に述べた方法で、書き込みを行ったデータをホストからの要求に応じて読み出すためには、ホストから指定された論理アドレスのデータが、NANDフラッシュメモリ上で実際に記憶されている記憶位置（物理アドレス）がどこかを判断する必要がある。このため、論理アドレスと物理アドレスとの対応関係を示す変換テーブルを備える必要がある。論理アドレスと物理アドレスとの対応関係を示すための単位としては、NANDフラッシュメモリのページサイズに合わせるのが効率的であるが、ページサイズは例えば4Kbyteであり比較的小さい。例えば、256GBの論理アドレス空間を4Kbyte単位で区切ると、変換テーブルにおいて64Mega個のエントリが必要であるが、変換テーブルのエントリを１エントリ当たり4Byteとすると、変換テーブルには256MBの容量が必要になる。このため、変換テーブルのサイズが大きくなる（例えば非特許文献１参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】“A Buffer Management Scheme for Improving Random Writes in Flash Storage”  http://www.usenix.org/events/fast08/tech/full_papers/kim/kim_html/
【発明の概要】
【発明が解決しようとする課題】
【０００６】
変換テーブルは一般にランダムアクセス性に優れたDRAM(（Dynamic Random Access Memory）やSRAM(Static Random Access Memory)が使用されるが、変換テーブルのサイズが大きいと、これらの揮発性のメモリの容量を多く必要とする。メモリの容量を大きくすることはコスト面で問題が生じる恐れがある。また、変換テーブル全体をNANDフラッシュメモリ自体に持つと、変換テーブルの更新の度にNANDフラッシュメモリ上に書き込みが生じることになる。このため、NANDフラッシュメモリ上に対する書き込み回数を増大させ、半導体記憶システムの信頼性を低下させる恐れがある。
【０００７】
本発明は、上記に鑑みてなされたものであって、半導体記憶チップへの書き込み回数が増大するのを抑制し且つ安価に構成可能な半導体記憶制御装置を提供することを目的とする。
【課題を解決するための手段】
【０００８】
実施形態の半導体記憶制御装置は、情報処理装置で用いられる論理アドレスが指定されて書き込みが要求されたデータである書込要求データを半導体記憶チップへ書き込む半導体記憶制御装置であって、前記書込要求データは、１つ以上の所定の単位の第１データを有し、物理アドレスは、半導体記憶チップにおける前記第１データの記憶位置を示す情報であり、第１テーブル及び第２テーブルは揮発性のメモリに記憶され、第３テーブルは不揮発性のメモリに記憶され、前記半導体記憶チップにおける前記第１データの記憶位置を示す前記物理アドレスを有し、前記第２テーブルは、前記第３テーブルのサブセットであり、前記半導体記憶チップにおける前記第１データの記憶位置を示す前記物理アドレスを有し、前記第１テーブルは、前記論理アドレスを示す情報の一部と、前記第２テーブルが記憶される記憶領域の中で前記物理アドレスが記憶される記憶領域を特定する第１の特定情報とを対応付けた情報、または、前記論理アドレスを示す情報の一部と、前記第３テーブルが記憶される記憶領域の中で前記物理アドレスが記憶される記憶領域を特定する第２の特定情報とを対応付けた情報を有し、前記書込要求データを受け付ける受付部と、前記第１データと、前記半導体記憶チップの有する記憶領域のうち消去が行なわれた記憶領域で書き込みがまだ行なわれていない記憶位置に前記第１データを各々書き込む制御部と、前記第１テーブルを前記揮発性メモリに記録して、前記第２テーブルを前記揮発性メモリに記録するか、または、前記第１テーブルを前記揮発性メモリに記録して、前記第３テーブルを前記不揮発性メモリに記録する記録部とを備える。
【図面の簡単な説明】
【０００９】
【図１】一実施の形態の半導体記憶システムのハードウェア構成を例示する図。
【図２】コンパクションを説明するための概念図。
【図３】半導体記憶制御装置５０において実現される機能を例示する図。
【図４】正引きテーブルのデータ構成を例示する図。
【図５】一実施の形態に係る正引きテーブルの構成を模式的に示す図。
【図６】論理アドレスと１次テーブルのデータ構成との関係を説明するための図。
【図７】３次テーブルの構成を例示する図。
【図８】ビットベクタテーブルのデータ構成を例示する図。
【図９】書き込み対象データを例示する図。
【図１０】ラウンドロビンにより行う書き込みを説明するための図。
【図１１】書き込み対象データの書き込みを行う処理の手順を示すフローチャート。
【図１２】書き込み対象データが書き込まれていく様子を時刻と共に例示する図。
【図１３】データの読み出しを行う処理の手順を示すフローチャート。
【図１４】コンパクションの処理の手順を示すフローチャート。
【発明を実施するための形態】
【００１０】
まず、本実施の形態にかかる半導体記憶制御装置を含む半導体記憶システムのハードウェア構成について図１を用いて説明する。半導体記憶システムは、半導体記憶制御装置５０と、半導体記憶素子（ＮＡＮＤ）５８Ａ〜５８Ｄとが接続されて構成される。半導体記憶制御装置５０は、プロセッサ５１と、ＢｏｏｔＲＯＭ（Reed Only Memory）５２と、ＳＡＴＡ／ＳＡＳインタフェース５５と、メモリコントローラ５３と、ＳＲＡＭ(Static Random Access Memory)５４と、ＮＡＮＤコントローラ５７Ａ〜５７Ｄと、これらを接続するバス５６とを備える。ＮＡＮＤコントローラ５７Ａ〜５７ＤにはそれぞれＮＡＮＤ５８Ａ〜５８Ｄが接続される。尚、ＮＡＮＤコントローラ５７Ａ〜５７Ｄを各々区別する必要がない場合、単に、ＮＡＮＤコントローラ５７と記載する場合がある。また、ＮＡＮＤ５８Ａ〜５８Ｄを各々区別する必要がない場合、単に、ＮＡＮＤ５８と記載する場合がある。
【００１１】
ＳＡＴＡ／ＳＡＳインタフェース５５は、プロセッサ５１の制御の下、半導体記憶制御装置５０の上位装置であるホストとの通信を制御する。ＢｏｏｔＲＯＭ５２は、電源の投入時に実行されるプログラムを記憶する。各種システムプログラムは、ＮＡＮＤ５８に記憶されている。プロセッサ５１は、電源の投入時にＢｏｏｔＲＯＭ５２からプログラムを読み出してこれを実行し、当該プログラムに従って、ＮＡＮＤ５８に記憶された各種システムプログラムをＳＲＡＭ５４に転送し、ＳＲＡＭ５４上のシステムプログラムを実行することにより、半導体記憶制御装置５０全体を制御して、各種機能を実現させる。具体的には、プロセッサ５１は、ＳＡＴＡ／ＳＡＳインタフェース５５を介して、ホストから送信されたコマンドを解釈し、当該コマンドに応じて、ＮＡＮＤ５８へのデータの書き込みやＮＡＮＤ５８からのデータの読み出しを制御する。
【００１２】
メモリコントローラ５３は、ＳＲＡＭ５４への書き込み又は読み込みの制御を行う。ＳＲＡＭ５４は、各種データや各種プログラムを記憶する。本実施の形態においては、ＳＲＡＭ５４は、後述する正引きテーブルの一部と、ビットベクタテーブルとを記憶する。ＮＡＮＤコントローラ５７は、ＮＡＮＤ５８の制御を行うものであり、誤り訂正回路を含む。
【００１３】
ＮＡＮＤ５８は、半導体記憶チップに相当し、例えば、NAND型のフラッシュメモリで用いられる記憶素子である。このようなＮＡＮＤ５８は、ランダムな読み書きができず、ページと呼ばれる単位で読み書きが可能で、複数ページがまとまってブロックと呼ばれる単位の記憶領域を構成する。ここでは、１ページ４KB、６４ページで１ブロックとする。１つのＮＡＮＤ５８はこのブロックが複数集まって構成される。尚、本実施の形態においては、図１に示されるように、ＮＡＮＤ５８の数を４つとしている。これらの各ＮＡＮＤ５８Ａ〜５８Ｄに対して各々１つのチャネル（ＣＨ０〜ＣＨ３）を割り当てる。尚、後述するように、半導体記憶制御装置５０は、ホストから書き込みが要求されたデータがページのサイズより大きい場合にはこれを複数に分割し、分割したページ単位のデータ（分割データという）を各チャネルＣＨ０〜ＣＨ３に割り当てて、書き込みを行う。
【００１４】
ここで、ＮＡＮＤ５８への書き込み方式について説明する。従来より、NAND型の半導体記憶素子では、追記方式が採用されている。この追記方式では、書き込みの前に、ブロックを消去する必要がある。ブロックの消去とは、ブロックに記憶されているデータを消去すること、例えばブロックを構成する記憶領域の全てのビットの値を「１」にすることである。半導体記憶制御装置５０では、このような消去をブロック単位で行ない、消去済みのブロックに対してページ単位で書き込みを行う。即ち、NAND型のＮＡＮＤ５８においては、消去済みのブロックのうち書き込みがまだ行われていないページに対して順次書き込みが可能であり、既に書き込みが行なわれたページに対する上書きが不可能である。また、ホストからの要求に応じたデータの書き込みは、ホストで用いられる論理アドレス（Logical Block Address:LBA）で指定される。一方、ＮＡＮＤ５８へのデータの書き込みは、ＮＡＮＤ５８の物理的な記憶位置（物理アドレス（Physical Block Address:PBA）という）に、論理アドレスとは無関係に、ページの昇順に書き込みが行なわれる。即ち、データの書き込みの要求の際にいかなる論理アドレスが指定されても、ブロック内で一定の順序でページに書き込みが行なわれる。尚、書き込み対象のデータがページのサイズに満たない場合には、対象とする部分を含むページのデータが読み出され、書き込み対象とマージしてページのサイズにしてからページ単位で書き込みが行われ、ページのサイズより大きいデータは複数ページに分解されてから割り当てられたブロックに分配されてページ単位で書き込みが行われる。論理アドレスと物理アドレスとの対応関係は、後述する正引きテーブルに記憶される。そして、データの書き込み要求において指定された論理アドレスが再度指定されて新たなデータの書き込みがホストから要求されると、半導体記憶制御装置５０は、消去済みのブロックの書き込みがまだ行なわれていないページに対して新たなデータの書き込みを行う。このとき、当該論理アドレスに対応して前回書き込みが行われたページを無効にして、新たなデータの書き込みが行われたページを有効にする。
【００１５】
ここで、無効とは物理アドレスの位置を論理アドレスが指していないということをいい、有効とは物理アドレスの位置を論理アドレスが指していることをいう。つまり、データの無効とは、あるデータが記憶されている記憶領域の物理アドレスの位置を論理アドレスが指していないことをいい、データの有効とは、あるデータが記憶されている記憶領域の物理アドレスの位置を論理アドレスが指していることをいう。ページの無効とは、あるページに対応する記憶領域の物理アドレスの位置を論理アドレスが指していないことをいい、ページの有効とは、あるページに対応する記憶領域の物理アドレスの位置を論理アドレスが指していることをいう。
【００１６】
この追記方式において、書き込みを続けることにより、無効にされたページが増えてくると、ＮＡＮＤ５８において書き込みを実現可能な容量（実現容量という）が少なくなってくる。そして、書き込みが可能な新規の消去済みのブロック、即ち、消去後に書き込みがまだ行なわれていないブロック（フリーブロックという）が少なくなり、各チャネルでフリーブロックの確保が不可能になった時点で書き込み不能となってしまう。これを防ぐために、半導体記憶制御装置５０は、適当なタイミングでガベージコレクションを行なう。ＮＡＮＤ５８において行なうガベージコレクションは、特にコンパクションという。図２は、コンパクションを説明するための概念図である。半導体記憶制御装置５０は、無効にされたページを含むブロックのうち、無効にされていない物理アドレスに書き込まれたデータ（有効データという）を集めて新たにフリーブロックに書き直すことにより、有効データを移動させる。その後、半導体記憶制御装置５０は、当該ブロックに対して消去を行うことにより、新たなフリーブロックを生成する。半導体記憶制御装置５０は、このようなコンパクションを行なうことにより、書き込みが不能になったブロックが新たに書き込み可能になって、フリーブロックを確保することが可能になる。また、移動により有効データが書き込まれたブロックにおいても、書き込みがまだ行なわれていないページがあればそのページに新たに書き込みが可能である。
【００１７】
尚、コンパクションを行うためには少なくとも１つのフリーブロックが必要になるが、これは、ＮＡＮＤ５８において実装された容量（実装容量という）より、書き込みを実際に実現可能な容量が少ないことを意味している。本実施の形態においては、実装容量と実現容量との差を余裕容量と呼んでいる。余裕容量が小さい時は、半導体記憶制御装置５０は、コンパクションを頻繁に行わなければならず、その性能に与えるインパクトが大きい。
【００１８】
次に、半導体記憶制御装置５０において実現される機能について図３を用いて説明する。半導体記憶制御装置５０は、ホストインタフェース部６０と、バッファ制御部６１と、アドレス変換部６２と、ＣＨ振り分け部６３と、コンパクション候補検出部６４と、管理テーブル更新部６５と、ＮＡＮＤ制御部６６Ａ〜６６Ｄと、データバッファ６７と、コンパクションｒｅａｄキュー６８と、管理テーブル６９とを有する。ホストインタフェース部６０の機能は、プロセッサ５１がプログラムを実行することと、ＳＡＴＡ／ＳＡＳインタフェース５５の機能とにより実現される。アドレス変換部６２と、ＣＨ振り分け部６３と、管理テーブル更新部６５と、コンパクション候補検出部６４と、バッファ制御部６１との各機能は、プロセッサ５１がプログラムを実行することにより実現される。ＮＡＮＤ制御部６６Ａ〜６６Ｄの各機能は、ＮＡＮＤコントローラ５７Ａ〜５７Ｄに各々対応しており、プロセッサ５１がプログラムを実行することと、ＮＡＮＤ制御部６６Ａ〜６６Ｄに各々対応するＮＡＮＤコントローラ５７Ａ〜５７Ｄの機能とにより実現される。これらのＮＡＮＤ制御部６６Ａ〜６６Ｄは、上述したチャネルＣＨ０〜ＣＨ３が各々割り当てられたＮＡＮＤ５８Ａ〜５８Ｄに１対１対応しているが、これらを各々区別する必要がない場合には、単にＮＡＮＤ制御部６６と記載する場合がある。データバッファ６７と、コンパクションｒｅａｄキュー６８とは、例えば、ＳＲＡＭ５４上に確保される記憶領域である。管理テーブル６９は、後に詳述するが、ＳＲＡＭ５４上とＮＡＮＤ５８上とに記憶される情報である。
【００１９】
ホストインタフェース部６０は、ホストと半導体記憶制御装置５０との通信を制御するインタフェースである。ホストインタフェース部６０は、ホストから送信されたコマンドを受信し、当該コマンドによって論理アドレスが指定されたデータの書き込みが要求されている場合、当該コマンド（ｗｒｉｔｅコマンドという）を後述のアドレス変換部６２に送る。その際、書き込みが要求されたデータのサイズがページのサイズ以下であれば、当該データを後述のバッファ制御部６１に送り、当該データのサイズがページのサイズより大きい場合、当該データをページ単位に分割し、分割したデータ（分割データという）をバッファ制御部６１に送る。これは論理アドレスと物理アドレスとの変換をページ単位で行っているためである。例えば、128KBのデータを4KBのデータ３２個にホストインタフェース部６０は分割する。尚、ｗｒｉｔｅコマンドに応じてバッファ制御部６１に送られるデータ又は分割データを、説明の便宜上、書き込み対象データと記載する。
【００２０】
また、ホストインタフェース部６０は、ホストから送信されたコマンドによって論理アドレスが指定されたデータの読み出しが要求されている場合、読み出しが要求されたデータがページのサイズ以下であれば、当該コマンド（ｒｅａｄコマンドという）をアドレス変換部６２に送る。読み出しが要求されたデータがページのサイズより大きい場合、ホストインタフェース部６０は、読み出す対象のデータがページ単位になるように読み出しを分解したコマンド（ｒｅａｄコマンド）をアドレス変換部６２に送る。このとき、ホストインタフェース部６０は、ホストから送信されたコマンドにより指定された論理アドレスを用いて、読み出し対象の各データの論理アドレスを各々計算し、計算した各論理アドレスのデータの読み出しを要求するｒｅａｄコマンドをアドレス変換部６２に送る。そして、ホストインタフェース部６０は、後述するバッファ制御部６１によってデータバッファ６７の指定の領域に記憶された読み出し対象のデータを読み出し、ホストに送信する。
【００２１】
管理テーブル６９は、正引きテーブルと、ビットベクタテーブルとを含む。正引きテーブルとは、書き込み対象データの論理アドレスと、ＮＡＮＤ５８において当該書き込み対象データの書き込まれる物理的な記憶位置を示す物理アドレスとの対応関係を示す。このような正引きテーブルは、ホストから指定された論理アドレスに対応するデータが記憶されているＮＡＮＤ５８上の記憶位置を示す物理アドレスを特定する際に用いられる。
【００２２】
図４は、正引きテーブルのデータ構成を概念的に示す図である。同図に示されるように、正引きテーブルのエントリは、論理アドレスをインデックスとして、チャネルに付与された番号（チャネル番号）と、物理ブロックに付与された番号（物理ブロック番号）と、ページに付与されたページ番号とから構成される。各書き込み対象データの論理アドレスは、ホストからのデータの書き込みの要求において指定される論理アドレスに基づいて各々計算される。チャネルの番号は、ここでは、ＣＨ０〜ＣＨ３とし、当該論理アドレスに対応するデータが記憶されている物理ブロックのあるＮＡＮＤ５８がいずれのチャネルに接続されているかを示す。そしてページ番号は、当該論理アドレスに対応するデータが、チャネル番号及び物理ブロック番号で特定される物理ブロックの中のどのページに記憶されているかを示す。尚、ページ番号としては、例えば、物理アドレスの順に付与されるものであっても良いし、ページの物理アドレス自体が付与されても良い。
【００２３】
正引きテーブルは、データの読み出しの度に参照され、ホストからの要求やコンパクションによりＮＡＮＤ５８へのデータの書き込みが発生する度に、更新される。正引きテーブルがどのように参照されたり更新されたりするかは後述するが、参照頻度や更新頻度が高いため、一般的にはＤＲＡＭやＳＲＡＭなどの揮発性のメモリを用いて実装される。しかしながら、例えば256GBの容量のＮＡＮＤ５８を4KB単位で管理すると、「256G/4K=64M」の数のエントリを有する正引きテーブルが必要で、正引きテーブルの１エントリを4Bにした場合は全部で「64M*4B=256MB」の容量の揮発性のメモリを実装しなければならない。また、更に容量の大きいＮＡＮＤ５８を実現するためには、容量に比例した揮発性のメモリを実装しなければならないという制約が存在する。本実施の形態では、揮発性のメモリの容量を減らし、揮発性のメモリと比べて容量当たりの単価が安いＮＡＮＤ５８と揮発性のメモリとを組み合わせて正引きテーブルを構成することでコストを抑えることを可能にする。即ち、本実施の形態では、正引きテーブルとして論理アドレス及び物理アドレスの対応関係を示すための情報の一部をＳＲＡＭ５４に記憶させ、一部をＮＡＮＤ５８に記憶させることで、正引きテーブルを構成するために必要な揮発性のメモリの容量を少なくする。
【００２４】
具体的には、正引きテーブルを、揮発性メモリに記憶させる１次テーブル及び２次テーブルと、ＮＡＮＤ５８に記憶させる３次テーブルとで構成する。２次テーブルは、ＮＡＮＤ５８におけるデータの記憶位置を示す物理アドレスを有する情報である。３次テーブルは、ＮＡＮＤ５８におけるデータの記憶位置を示す物理アドレスを有する情報である。１次テーブルは、論理アドレスを示す情報の一部と、２次テーブルが記憶される記憶領域の中で前理アドレスが記憶される記憶領域を特定する特定情報とを対応付けた情報、または、論理アドレスを示す情報の一部と、３次テーブルが記憶される記憶領域の中で物理アドレスが記憶される記憶領域を特定する特定情報とを対応付けた情報を有する情報である。図５は、本実施の形態に係る正引きテーブルの構成を模式的に示す図である。１次テーブルでは、記憶領域がチャンクという単位で区切られ、１チャンク分の記憶領域が１エントリとして割り当てられる。例として、１チャンクを１MBとし、１エントリを4Bとすると、256GBのＮＡＮＤ５８に対して１次テーブルの容量は「256GB/1MB*4B=1MB」となる。具体的に、１次テーブルの各エントリは、図６に例示されるように、論理アドレスの上位１８ビットと、２次テーブルが記憶される記憶領域の中で当該論理アドレスに対応する物理アドレスが記憶される記憶領域を特定する特定情報又は３次テーブルが記憶される記憶領域の中で当該論理アドレスに対応する物理アドレスが記憶される記憶領域を特定する特定情報とを対応付けて示す。このエントリの数は256K個となる。尚、対応するデータに対してまだ一度もアクセスしたことがない論理アドレスに対しては、特定情報として、「FFFFFFFFF」という値が示される。これは、２次テーブル及び３次テーブルに対応するエントリがないことを示す。尚、論理アドレスとして29bitしか使用していないので、アクセスしたことがあるエントリがこの値を示すことはない。
【００２５】
３次テーブルが記憶される記憶領域には、以下に説明する２次テーブルを介してページ単位で各エントリの情報が記憶される。図７は、３次テーブルの構成を例示する図である。３次テーブルの各エントリは、１次テーブルのインデックスである論理アドレスの上位１８ビットによって一意に選択され、３ビット目から１０ビット目までの中位８ビットによって１MBのチャンク内に存在する256個のクラスタ位置が特定され、その位置に当該論理アドレスに対応する物理アドレスが記憶される。３次テーブルのエントリの数は、チャンクのサイズ１MBに対して４KBのクラスタが1MB/4KB=256であることから、１次テーブルの１エントリ当たり256個である。この１次テーブルの１エントリにおいて論理アドレスの上位１８ビットに対応して１つの記憶領域を特定する特定情報が示されている。３次テーブルにおいてこの１つの領域に、256個の物理アドレスが論理アドレスの順に並んでおり、論理アドレスの３ビット目から１０ビット目までの中位８ビットをオフセットとして、当該オフセットに対応する記憶位置（アドレス）の4Bに物理アドレスが記憶される。尚、３次テーブルのエントリの各情報は、複数のＮＡＮＤ５８にラウンドロビンで書き込まれる。このような３次テーブルをＳＬＣで構成すれば、３次テーブルへの書き込みにともなう速度のオーバーヘッドを低減することが可能である。尚、まだ一度もアクセスされたことのないデータの物理アドレスは３次テーブルには存在しないので、３次テーブルによって、ＮＡＮＤ５８の容量に書き込み可能な全てのデータに対する論理アドレス及び物理アドレスの対応関係が示されるわけではない。
【００２６】
２次テーブルは、３次テーブルのサブセットであり、３次テーブルのキャッシュとして機能するものであり、揮発性のメモリ例えばＳＲＡＭ５４やＤＲＡＭ（不図示）を使用して構成する。その容量は３次テーブルの容量以下である。２次テーブルの各エントリは、１次テーブルのインデックスである論理アドレスの上位１８ビットによって一意に選択され、３ビット目から１０ビット目までの中位８ビットによって１MBのチャンク内に存在する256個のクラスタ位置が特定され、その位置に当該論理アドレスに対応する物理アドレスが記憶される。図７に例示されるように、２次テーブルにおいて、３次テーブルと同様に、１次テーブルの１つのエントリにおいて論理アドレスの上位１８ビットに対応する特定情報によって特定される記憶領域に、物理アドレスが論理アドレスの順に並んでおり、論理アドレスの３ビット目から１０ビット目までの中位８ビットをオフセットとして、当該オフセットに対応する記憶位置（アドレス）の4Bに物理アドレスが記憶される。２次テーブルのエントリの情報は、所定の条件が成立する度に、３次テーブルが記憶される記憶領域に書き込まれる。所定の条件とは、例えば、２次テーブルが記憶される記憶領域に書き込まれた複数のエントリのサイズが、ページサイズである4KBやその倍数（例えば64KB）になることである。３次テーブルが記憶される記憶領域への書き込みは、ＮＡＮＤ５８への書き込みであるので、半導体記憶制御装置５０の電源がOFFされても論理アドレス及び物理アドレスの対応関係が保持される。また、２次テーブルの１エントリは１KBであり、ＮＡＮＤ５８のページサイズが４KBであることから最悪の状態でも４回の書き込みでNAND５８の１ページの書き込みとなり、書き込み毎に３次テーブルを更新することに比べると、ＮＡＮＤ５８に記憶される３次テーブルが記憶される記憶領域への書き込みの回数を低減することができる。
【００２７】
次に、ビットベクタテーブルについて図８を用いて説明する。ビットベクタテーブルは、書き込み対象データが書き込まれるチャネルＣＨ０〜ＣＨ３の各物理ブロックについて、当該物理ブロックに含まれるページのうち有効なデータが書き込まれているページ（有効ページという）がどのページかを、ページ順に２値で示すテーブルである。ページ毎に２値を示すものをビットベクタという。ビットベクタの値が「１」であれば、そのページが有効ページであることを示し、「０」であれば、そのページが有効ページではない(無効である)ことを示す。初期状態においては、ビットベクタの値は全て「０」である。
【００２８】
本実施の形態においては、書き込み対象データが書き込まれるチャネルはチャネルＣＨ０〜ＣＨ３の４つであり、１物理ブロック当たり６４ページとすると、対応するビットベクタは、６４個となる。同図に示されるように、このようなビットベクタテーブルでは、各チャネルＣＨ０〜ＣＨ３の物理ブロック番号がインデックスとして用いられる。ビットベクタテーブルは、物理ブロック番号と、各物理ブロックに含まれる各ページに対するビットベクタと、カウンタとを、物理ブロック毎に含む。同図においては、左から、チャネルＣＨ０の１番目のページ、２番目のページ、…、チャネルＣＨ０の最後のページ、次の行がチャネルＣＨ１の1番目のページ、２番目のページ…、チャネルＣＨ１の最後のページ、…、というように、チャネルＣＨ０〜ＣＨ３の各物理ブロックの各ページの順にビットベクタが配置される。カウンタは、値が「１」であるビットベクタの総数を示す。ビットベクタの値が「１」であるページは有効ページであるから、このカウンタは、論理ブロック内の有効ページの数を示す（以降、有効ページ数カウンタと呼ぶ）。このような構成において、ビットベクタテーブルは、ホストからのデータの書き込みの要求がある度に、更新される。どのように更新されるかは後述する。
【００２９】
図３の説明に戻る。アドレス変換部６２は、ホストインタフェース部６０からコマンドを受け取り、当該コマンドがｒｅａｄコマンドである場合、当該ｒｅａｄコマンドで指定された論理アドレスを用いて管理テーブル６９のうち正引きテーブルを参照し、当該ｒｅａｄコマンドで読み出しが要求されたデータが書き込まれているチャネル及びページの物理アドレスを特定する。具体的には、アドレス変換部６２は、当該論理アドレスの上位１８ビットを用いて１次テーブルのエントリを参照し、当該論理アドレスの上位１８ビットに対応付けられている特定情報を用いて、当該論理アドレス及び物理アドレスの対応関係が２次テーブルが記憶される記憶領域又は３次テーブルが記憶される記憶領域に記憶されているか否かを判断し、当該判断の結果に応じて、２次テーブルが記憶される記憶領域又は３次テーブルが記憶される記憶領域から当該論理アドレスに対応する物理アドレスを読み出すことで、当該チャネル及び物理アドレスを特定する。
【００３０】
そして、アドレス変換部６２は、特定したチャネル及び物理アドレスを指定してデータの読み出しを要求するコマンドを、ＣＨ振り分け部６３を介してＮＡＮＤ制御部６６に送る。一方、ホストインタフェース部６０から受け取ったコマンドがｗｒｉｔｅコマンドである場合、アドレス変換部６２は、当該ｗｒｉｔｅコマンドを後述のＣＨ振り分け部６３に送る。
【００３１】
また、アドレス変換部６２は、後述のコンパクションｒｅａｄキュー６８に記憶されたコンパクションｒｅａｄコマンドに応じて、正引きテーブルを参照して、当該コンパクションｒｅａｄコマンドによって物理アドレスが指定された有効ページのデータ（有効データ）の読み出しを要求するコマンドを、当該有効データのある物理ブロックを含むＮＡＮＤ５８が接続されたチャネルに対応するＮＡＮＤ制御部６６に送る。当該有効データは、ＮＡＮＤ制御部６６を介してＮＡＮＤ５８から読み出され、バッファ制御部６１を介してデータバッファ６７に記憶される。アドレス変換部６２は、この有効データの書き込みを要求するコマンド（コンパクションｗｒｉｔｅコマンドという）をＣＨ振り分け部６３に送る。
【００３２】
ＣＨ振り分け部６３は、アドレス変換部６２からコマンドを受け取り、当該コマンドがｗｒｉｔｅコマンドである場合、書き込み対象データを書き込む対象のチャネルを決定する。例えば、ＣＨ振り分け部６３は、４KB毎にラウンドロビンにより書き込みを行うようにし、ラウンドロビンの順番に応じて、書き込む対象のチャネルを決定する。そして、ＣＨ振り分け部６３は、書き込み対象データの書き込みを要求するコマンドを、決定したチャネルに対応するＮＡＮＤ制御部６６に送る。一方、アドレス変換部６２からのコマンドによって、チャネル及び物理アドレスが指定されたデータの読み出しが要求されている場合、指定されたチャネルに対応するＮＡＮＤ制御部６６に対して物理アドレスを指定してデータの読み出しを要求するコマンドを送る。また、アドレス変換部６２から受け取ったコマンドがコンパクションｗｒｉｔｅコマンドである場合、ＣＨ振り分け部６３は、ラウンドロビンの順番に応じて、書き込む対象のチャネルを決定し、有効データの書き込みを要求するコマンドを、決定したチャネルに対応するＮＡＮＤ制御部６６に送る。
【００３３】
ＮＡＮＤ制御部６６は、ＣＨ振り分け部６３からコマンドを受け取り、当該コマンドに従って、対応するＮＡＮＤ５８にアクセスする。具体的には、当該コマンドによって、データの書き込みが要求されている場合、ＮＡＮＤ制御部６６は、バッファ制御部６１を介して書き込み対象データを取得して、当該書き込み対象データをＮＡＮＤ５８に書き込む。この書き込みにおいて、ＮＡＮＤ制御部６６は、対応するＮＡＮＤ５８の消去済みのブロックのうち書き込みがまだ行なわれていないページ毎に書き込みの記憶位置を順次示すよう追記ポインタを設定し、追記ポインタによって示される記憶位置のページに書き込み対象データを書き込み、その後、書き込みを行なったページに続く次のページであって書き込みがまだ行われていないページの記憶位置を示すよう追記ポインタを更新する。従って、追記ポインタは順次次の書き込み記憶位置を示すようにその値が変化する。例えば、追記ポインタは、各チャネルにおいて15ビットの物理アドレスによりブロックが識別され、ブロック内に64ページある場合、合計15+6=21ビットで構成される。
【００３４】
ここで、書き込み対象データのデータ構成について説明する。ＮＡＮＤ制御部６６は、書き込み対象データ自体の誤りを検出して訂正するための誤り訂正符号（ページＥＣＣという）及びｗｒｉｔｅコマンドによって指定された論理アドレスを当該書き込み対象データに付加する。尚、ページＥＣＣには、データの誤りを検出するＣＲＣ符号等の符号と、データの誤りを訂正するＥＣＣ符号等の符号とが含まれるものとする。図９は、ページＥＣＣが付加された書き込み対象データを例示する図である。上述のように決定された各チャネルのＮＡＮＤ５８において、ＮＡＮＤ制御部６６は、このようなページＥＣＣ及び論理アドレスを付加した書き込み対象データを、上述のように決定された各チャネルのＮＡＮＤ５８内の追記ポインタにより示されるページに書き込む。尚、書き込み対象データはページ単位の大きさであるが、ＮＡＮＤ５８のページサイズは、書き込み対象データにページＥＣＣ及び論理アドレスが付加された全体の大きさに相当するものとする。また、各分割データの論理アドレスは、ｗｒｉｔｅコマンドによって指定された論理アドレスに基づいてＮＡＮＤ制御部６６が各々計算する。
【００３５】
次に、複数の分割データが書き込み対象データとしてラウンドロビンによりチャネルＣＨ０〜ＣＨ３で書き込みが行われる様子について説明する。図１０は、ラウンドロビンにより行う書き込みを説明するための図である。尚、図の簡略化のため、分割データに対して付加された論理アドレスの図示を省略している。同図に示されるように、時刻Ｔ１でチャネルＣＨ０に対して最初の分割データＤ１の書き込みが行われ、時刻Ｔ２でチャネルＣＨ１に対して次の分割データＤ２の書き込みが行われるというように、チャネルＣＨ０〜ＣＨ３までラウンドロビンで順に分割データの書き込みが行われる。更なる分割データの書き込みの際には、チャネルＣＨ０から順にランドロビンで書き込みが行われる。このように、ラウンドロビンにより分割データの書き込みが行われることにより、書き込みがチャネル間で略均等になる。尚、同図の例では、時刻の経過と共に各チャネルに順に書き込みを行う様子が図示されているが、これに限らず、２つ以上のチャネルに同時に書き込みを行うようにしても良い。
【００３６】
図３の説明に戻る。また、ＮＡＮＤ制御部６６は、アドレス変換部６２から受け取ったコマンドによって、物理アドレスが指定された有効ページのデータ（有効データ）の読み出しが要求されている場合、当該物理アドレスを用いてＮＡＮＤ５８内の当該物理アドレスに対応するページに書き込まれたデータを読み出してこれをバッファ制御部６１に送り、これをデータバッファ６７に記憶させる。尚、ＮＡＮＤ制御部６６は、ＮＡＮＤ５８から読み出した当該データに誤りがある場合、これを検出して訂正する。データの誤りを検出して訂正する方法については後述する。また、ＣＨ振り分け部６３から受け取ったコマンドによって、有効データの書き込みが要求されている場合、ＮＡＮＤ制御部６６は、バッファ制御部６１を介して書き込み対象の有効データを取得して、当該有効データをＮＡＮＤ５８に書き込む。
【００３７】
コンパクション候補検出部６４は、管理テーブル６９に含まれるビットベクタテーブルを参照して、コンパクションの候補とする論理ブロックを決定し、当該論理ブロックのうち有効ページの物理アドレスを指定して当該有効ページの読み出しを要求するコマンド（コンパクションｒｅａｄコマンドという）をコンパクションｒｅａｄキュー６８に送る。
【００３８】
書き込み対象データ又は読み出したデータを記憶するのがデータバッファ６７である。コンパクションｒｅａｄキュー６８は、コンパクションの際に有効ページの読み出しを要求するコマンドを記憶する先入れ先出し型のバッファである。
【００３９】
バッファ制御部６１は、データバッファ６７を複数の領域として管理し、コマンドに対応したデータを記憶させる領域を管理する。具体的には、バッファ制御部６１は、ｗｒｉｔｅコマンドに応じてホストインタフェース部６０から送られた書き込み対象データをデータバッファ６７に記憶させ、ＣＨ振り分け部６３により書き込み対象として決定されたチャネルに対応するＮＡＮＤ制御部６６に該当の書き込み対象データを送る。当該書き込み対象データは、ＮＡＮＤ制御部６６を介してＮＡＮＤ５８に書き込まれる。また、バッファ制御部６１は、ｒｅａｄコマンドに応じて、ＮＡＮＤ制御部６６から送られたデータをデータバッファ６７の指定の領域に記憶させ、その後ホストインタフェース部６０に送る。当該データはホストインタフェース部６０を介してホストに送信される。また、バッファ制御部６１は、コンパクションｒｅａｄコマンドに応じて、ＮＡＮＤ制御部６６を介してＮＡＮＤ５８から読み出されたデータをデータバッファ６７に記憶させる。
【００４０】
管理テーブル更新部６５は、論理アドレスが指定されたデータの書き込みを要求するコマンド（ｗｒｉｔｅコマンド）がホストから受信された場合、正引きテーブルを参照すると共に、ビットベクタテーブルを更新し、更に、正引きテーブルを更新する。具体的には、管理テーブル更新部６５は、まず、正引きテーブルを参照して、当該論理アドレスに対応する物理アドレス、即ち、当該論理アドレスに対応するデータがどの物理ブロックのページに書き込まれているかを検索する。このとき、管理テーブル更新部６５は、論理アドレスの上位１８ビットを用いて正引きテーブルの１次テーブルのエントリを参照し、当該論理アドレスの上位１８ビットに対応付けられている特定情報を用いて、当該論理アドレス及び物理アドレスの対応関係が２次テーブルが記憶される記憶領域又は３次テーブルが記憶される記憶領域に記憶されているか否かを判断する。論理アドレスの上位１８ビットに対する特定情報によって「FFFFFFFFF」という値が示される場合、即ち、当該論理アドレス及び物理アドレスの対応関係が２次テーブルが記憶される記憶領域及び３次テーブルが記憶される記憶領域のいずれにも記憶されていない場合、当該論理アドレスへのデータの書き込みが今回まで行なわれていないことになる。この場合、管理テーブル更新部６５は、当該論理アドレスの上位１８ビットと、当該論理アドレスに対応する物理アドレスを記憶させる２次テーブルが記憶される記憶領域を特定する特定情報とを対応付けた情報を有するよう１次テーブルを更新する。また、管理テーブル更新部６５は、２次テーブルが記憶される記憶領域に当該論理アドレスに対応するエントリを記録する。即ち、管理テーブル更新部６５は、２次テーブルが記憶される記憶領域に、当該論理アドレスの３ビット目から１０ビット目までの中位８ビットをオフセットとして、当該オフセットに対応する記憶位置（アドレス）の4Bに当該論理アドレスに対応する物理アドレスを書き込むことにより、第２テーブルが記憶される記憶領域にエントリを記録する。また、管理テーブル更新部６５は、ビットベクタテーブル内の、書き込み対象データを書き込むページに対応するビットベクタの値を「１」にする。書き込み対象データを書き込むページ、すなわち物理アドレスは、追記ポインタにより示される。そして、管理テーブル更新部６５は、当該ページの存在する物理ブロックの有効ページ数カウンタの値を１インクリメントする。
【００４１】
一方、１次テーブルのエントリの特定情報により、論理アドレスの上位１８ビットに対して当該論理アドレス及び物理アドレスの対応関係が２次テーブル又は３次テーブルのいずれかによって示されている場合、当該論理アドレスに対応するデータの書き込みが以前に行なわれていることになる。当該論理アドレス及び物理アドレスの対応関係が２次テーブルによって示される場合には、管理テーブル更新部６５は、１次テーブルを更新せずに、２次テーブルにおいて、当該論理アドレスに対応するエントリに、書き込み対象データを書き込む先の物理アドレスを記録する。当該論理アドレス及び物理アドレスの対応関係が３次テーブルによって示される場合には、管理テーブル更新部６５は、当該３次テーブルが記憶される記憶領域において当該論理アドレスに対応する物理アドレスを示すエントリを２次テーブルが記憶される記憶領域に記録することにより、当該記憶領域に記憶された各エントリを３次テーブルから２次テーブルに移動させる。更に、管理テーブル更新部６５は、２次テーブル上の該当するエントリを、書き込み対象の物理アドレスで更新する。そして、管理テーブル更新部６５は、１次テーブルにおいて、当該各エントリによって示される物理アドレスに各々対応する論理アドレスの上位１８ビットに対して、移動先の物理アドレスが記憶される２次テーブル上の記憶領域を示す特定情報を対応付けることにより１次テーブルを更新する。書き込み対象データを書き込むページ、すなわち物理アドレスは、追記ポインタにより示される。
【００４２】
尚、当該論理アドレス及び物理アドレスの対応関係が２次テーブル又は３次テーブルのいずれかによって示されている場合には、今回のｗｒｉｔｅコマンドにより、以前に書き込みが行なわれたデータを無効にする必要がある。この場合、管理テーブル更新部６５は、ｗｒｉｔｅコマンドで指定された論理アドレスで参照した正引きテーブルのエントリに記憶されている物理アドレスのページに対応するビットベクタの値を「０」にする。あわせて管理テーブル更新部６５は、当該ページの存在する物理ブロックの有効ページ数カウンタの値を１デクリメントする。また、管理テーブル更新部６５は、書き込み対象データを書き込むページに対応するビットベクタの値を「１」にし、当該ページの存在する物理ブロックの有効ページ数カウンタの値を１インクリメントする。このようにデータの書き込みが行なわれる度に更新することで、ビットベクタテーブルと有効ページ数カウンタとは有効ページの記憶位置及びその数を常に示している。
【００４３】
ところで、上述したように、２次テーブルは、キャッシュとして機能するため、通常のキャッシュと同様に、キャッシュの領域は制限されており、容量を一定以内に保つ必要がある。キャッシュの領域が定められた範囲を超えたら、エントリのうち一部を追い出して、新たな領域を確保しなければならない。２次テーブルのエントリの追い出しは３次テーブルに対して管理テーブル更新部６５が行う。追い出すエントリを選択する方法は、従来のキャッシュで良く知られているようなLRUアルゴリズムや、もっとも古いエントリを選択して追い出すFIFOアルゴリズムなどを利用すれば良い。２次テーブルから３次テーブルへのエントリの追い出し（書き込み）は、ＮＡＮＤ５８の書き込みサイズに合わせて行う。例えば、４KBのページサイズの１６倍の64KB毎を追い出しの単位とした場合、２次テーブルのエントリは一つ１KBであるから、６４個のエントリが一度に追い出される。３次テーブルが記憶される記憶領域への記録は、ページ単位で追記方式により行う。この例では１６ページが一度に書き込まれる。管理テーブル更新部６５は、２次テーブルにおいて追い出しの候補のエントリを選択したら、追い出しの候補のエントリを、３次テーブルにおいて書き込む対象の64個のエントリに既に記憶されている記録内容とマージして、マージしたものを３次テーブルの新しい記憶領域へ書き込む。このとき、管理テーブル更新部６５は、２次テーブルから追い出したエントリによって示される物理アドレスが対応付けられていた論理アドレスの上位１８ビットの１次テーブルのエントリが、３次テーブルが記憶される記憶領域の中で当該論理アドレスに対応する物理アドレスが記憶される記憶領域を特定する特定情報と対応付けられるように、１次テーブルにおいて当該エントリを更新する。尚、３次テーブルのエントリを記憶させるＮＡＮＤ５８は１つに限らず、複数のＮＡＮＤ５８に記憶されるようにすることが望ましい。即ち、管理テーブル更新部６５は、１回の追い出しで１つのＮＡＮＤ５８の64KBの記憶領域に書き込みを行うが、４KB毎にラウンドロビンで書き込み対象のＮＡＮＤ５８を決定して決定したＮＡＮＤ５８に書き込みを行なう。このような構成によれば、３次テーブルに関する書き込みに関し、複数のＮＡＮＤ５８で均等に書き込みが行なわれるようにすることができる。
【００４４】
次に、本実施の形態にかかる半導体記憶制御装置５０の行う処理の手順について説明する。まず、ホストからのｗｒｉｔｅコマンドに応じて半導体記憶制御装置５０がＮＡＮＤ５８に書き込み対象データの書き込みを行う処理の手順について図１１を用いて説明する。尚、半導体記憶制御装置５０は、書き込みを始める前には、各チャネルにおいてフリーブロックである物理ブロックを各々予め確保しておく。そして、半導体記憶制御装置５０は、各チャネルの先頭の物理ブロックの１番目のページを示すように各チャネルの追記ポインタを設定する。そして、半導体記憶制御装置５０は、論理アドレスが指定されたデータの書き込みを要求するｗｒｉｔｅコマンドをホストから受信すると（ステップＳ１）、ｗｒｉｔｅコマンドにより書き込みが要求されたデータのサイズがページのサイズ以下であるか否かを判断する（ステップＳ２）。当該データのサイズがページのサイズ以下である場合（ステップＳ２：ＹＥＳ）、半導体記憶制御装置５０は、当該データ（書き込み対象データ）をデータバッファ６７に記憶させる（ステップＳ４）。一方、ｗｒｉｔｅコマンドにより書き込みが要求されたデータのサイズがページのサイズより大きい場合（ステップＳ２：ＮＯ）、半導体記憶制御装置５０は、当該データをページ単位で分割し（ステップＳ３）、分割したデータ（分割データ：書き込み対象データ）をデータバッファ６７に記録する（ステップＳ４）。
【００４５】
そして、半導体記憶制御装置５０は、ｗｒｉｔｅコマンドにより指定された論理アドレスに基づいて正引きテーブルを参照して、書き込み対象データの論理アドレスに対応する物理アドレスが既に記憶されている場合、当該物理アドレスを古い物理アドレスとして例えばＳＲＡＭ５４に記憶させる（ステップＳ５）。また、半導体記憶制御装置５０は、書き込み対象データを書き込むチャネルをラウンドロビンにより決定し（ステップＳ６）、決定した各チャネルのＮＡＮＤ５８において追記ポインタで示されるページに、ページＥＣＣ及び論理アドレスを各々付加した各書き込み対象データを書き込む（ステップＳ７）。そして、半導体記憶制御装置５０は、各チャネルに関して、書き込み対象データを書き込んだページに続く次のページであって書き込みがまだ行われていないページを示すよう追記ポインタを更新する（ステップＳ８）。
【００４６】
図１２は、チャネルＣＨ０について、分割データが書き込み対象データとして書き込まれていく様子を時刻毎に示した図である。まず、時刻ｔ０では、フリーブロックが確保されている状態が示されている。時刻ｔ１では、最初の分割データＤ１が、時刻ｔ０で確保されたフリーブロックの最初（先頭又は最後尾）のページに書き込まれ、時刻ｔ２では、ラウンドロビンによりチャネルＣＨ０に新たに決定された分割データＤ６が２番目のページに書き込まれる。同様に、時刻ｔ３では、３番目のページに分割データＤ１１が書き込まれ、時刻ｔ４では、４番目のページに分割データＤ１６が書き込まれる。このように、分割データを書き込むページは、論理アドレスとは無関係に、ブロック内の昇順に決定される。そして追記ポインタは、この順に書き込むページを示すように、書き込みが行われる度に設定される。本実施の形態においては、ラウンドロビンで各チャネルへの書き込みが均等に行われるため、図７で示されるように、各チャネルにおいて追記ポインタが示すページの番号は、最大で１の差である。そして、論理ブロックの最後のページに書き込みが終了したときには、各チャネルの追記ポインタの示すページの番号は、同じになる。
【００４７】
以上のように、ホストからのｗｒｉｔｅコマンドにより指定された論理アドレスがどのような値であっても、書き込み対象データを書き込むページの物理アドレスが一定の順序で割り当てられ、当該ページにデータの書き込みが行なわれる。
【００４８】
図１１の説明に戻る。書き込み対象データの書き込みに伴って、半導体記憶制御装置５０は、書き込み対象データの論理アドレスと、書き込み対象データを書き込んだページの物理アドレスとの対応関係を正引きテーブルに書き込むことによりこれらを記録する（ステップＳ９）。これらを記録する具体的な方法は上述の構成欄で説明した通りである。書き込み対象データが分割データである場合、分割データは、ページ単位であるから、指定された論理アドレスに対してページのサイズを順次加算した値を各分割データの論理アドレスとして半導体記憶制御装置５０は計算する。そして、半導体記憶制御装置５０は、論理アドレスと、書き込み対象データを今回書き込んだチャネルのチャネル番号、物理ブロックの物理ブロック番号及びページのページ番号を正引きテーブルに書き込むことによりこれらを記録する。尚、上述の例では、ページ番号は、更新する前の追記ポインタの下位6ビットにより示されるから、ページ番号にはこの値を用いれば良い。半導体記憶制御装置５０は、書き込み対象データの書き込みを行う度、正引きテーブルを更新する。
【００４９】
更に、半導体記憶制御装置５０は、ビットベクタテーブルを参照して、ステップＳ５でＳＲＡＭ５４に記憶させた古い物理アドレスのページに対応するビットベクタの値を「０」にし、当該ページの存在する物理ブロックの有効ページ数カウンタの値を１デクリメントする（ステップＳ１０）。古い物理アドレスとは、即ち、ステップＳ１０で受信されたｗｒｉｔｅコマンドが指定する論理アドレスで、以前にデータが書き込まれたページを示している。このため、当該ページに書き込まれたデータを無効にするため、ビットベクタの値を「０」にして、当該ページの存在する物理ブロックの有効ページの数カウンタの値を１つ減らしている。また、半導体記憶制御装置５０は、ビットベクタテーブルにおいて、ステップＳ７で書き込み対象データを書き込んだページに対応するビットベクタの値を「１」にし、当該ページの属する物理ブロックの有効ページ数カウンタの値を１インクリメントする（ステップＳ１１）。以上のようにして、半導体記憶制御装置５０は、書き込み対象データの書き込みに伴って、ビットベクタテーブルを更新する。
【００５０】
そして、追記ポインタが全てのチャネル（ＣＨ０〜ＣＨ３）でブロックの最後に達して、新たな書き込みを行うことができなくなった場合、半導体記憶制御装置５０は、新たな各チャネルでフリーブロックを確保する。新たなフリーブロックへの分割データの書き込みについても上述の通りである。
【００５１】
次に、ホストからのｒｅａｄコマンドに応じて半導体記憶制御装置５０がＮＡＮＤ５８からデータの読み出しを行う処理の手順について図１３を用いて説明する。半導体記憶制御装置５０は、論理アドレスが指定されたデータの読み出しを要求するｒｅａｄコマンドをホストから受信すると（ステップＳ２０）、ｒｅａｄコマンドにより読み出しが要求されたデータのサイズがページのサイズ以下であるか否かを判断する（ステップＳ２１）。当該データのサイズがページのサイズ以下である場合（ステップＳ２１：ＹＥＳ）、半導体記憶制御装置５０は、ｒｅａｄコマンドにより指定された論理アドレスを用いて正引きテーブルを参照して、読み出しの対象のチャネル、物理ブロック及びページを特定する（ステップＳ２３）。これらを特定する具体的な方法は上述の構成欄で説明した通りである。そして、半導体記憶制御装置５０は、特定したチャネルに対応するＮＡＮＤ５８から該当のデータを読み出す（ステップＳ２４）。
【００５２】
一方、ｒｅａｄコマンドにより読み出しが要求されたデータのサイズがページのサイズより大きい場合（ステップＳ２１：ＮＯ）、半導体記憶制御装置５０は、読み出す対象のデータがページ単位になるように読み出しを分解する。即ち、半導体記憶制御装置５０は、ｒｅａｄコマンドにより指定された論理アドレスを用いて、読み出し対象の各データの論理アドレスを各々計算する（ステップＳ２２）。そして、半導体記憶制御装置５０は、計算した各論理アドレスを使って正引きテーブルを参照して、読み出しの対象のチャネル、物理ブロック及びページを各々特定する（ステップＳ２３）。そして、半導体記憶制御装置５０は、特定したチャネルに対応するＮＡＮＤ５８から該当のデータを各々読み出す（ステップＳ２４）。
【００５３】
ステップＳ２４で読み出したデータの正当性は、データに付加されたページＥＣＣで担保される。即ち、半導体記憶制御装置５０は、読み出したデータに付加されたページＥＣＣを使って、当該データの誤りを検出してこれを訂正することが可能である。しかし、ページＥＣＣで訂正できない誤りがある場合、ＮＡＮＤ５８に故障が生じて、データに異常が発生している可能性がある。このような場合には（ステップＳ２５：ＮＯ）、半導体記憶制御装置５０は、ＮＡＮＤ５８に故障が生じた旨を示す通知情報をホストに送信する（ステップＳ２８）。
【００５４】
ステップＳ２４で読み出したデータに誤りがない場合には（ステップＳ２５：ＹＥＳ）、半導体記憶制御装置５０は、当該データをデータバッファ６７の指定の領域に記憶させ、ステップＳ２７に進む。また、ステップＳ２４で読み出したデータに誤りがあっても、半導体記憶制御装置５０は、ページＥＣＣを用いて当該データを訂正した後（ステップＳ２６）、訂正したデータをデータバッファ６７の指定の領域に記憶させ、ステップＳ２７に進む。ステップＳ２７では、半導体記憶制御装置５０は、データバッファ６７の指定の領域に記憶されたデータをホストに送信する。
【００５５】
尚、ステップＳ２０で受信されたｒｅａｄコマンドにより複数のデータの読み出しが要求された場合、各々指定された論理アドレスに応じて、半導体記憶制御装置５０は、異なる各チャネルの物理ブロックからデータを読み出す場合も有り得る。このように、データの読み出し時には各チャネルで独立なアクセスが可能であるので、ホストからの要求に応じてデータを読み出してこれを応答性良くホストに送信することができる。
【００５６】
次に、コンパクションの対象の物理ブロックに書き込まれている有効データをフリーブロックに移動する処理の手順について図１４を用いて説明する。半導体記憶制御装置５０は、有効ページの数の値の最大値として「Ｍ＝４０９６」を設定し、ビットベクタテーブルにおける物理ブロック毎のエントリのインデックスとして「Ｋ＝０」を設定する（ステップＳ４０）。そして、半導体記憶制御装置５０は、ビットベクタテーブルを参照して、物理ブロック毎の有効ページ数カウンタの値を順番に１つ読み出し（ステップＳ４１）、当該カウンタの値がＭより小さいか否かを判断する（ステップＳ４２）。当該有効ページ数カウンタの値がＭ以上である場合（ステップＳ４２：ＮＯ）、ステップＳ４４に進む。当該有効ページ数カウンタの値がＭより小さい場合（ステップＳ４２：ＹＥＳ）、半導体記憶制御装置５０は、Ｍの値を当該カウンタの値に置き換え、ステップＳ４１で当該有効ページ数カウンタの値を読み出したエントリのインデックスの値をＫとして（ステップＳ４３）、ステップＳ４４に進む。
【００５７】
ステップＳ４４では、半導体記憶制御装置５０は、ビットベクタテーブルの全ての物理ブロックについて有効ページ数カウンタの値を読み出したか否かを判断し、全ての論理ブロックについて有効ページ数カウンタの値を読み出していない場合（ステップＳ４４：ＮＯ）、Ｋの値を１インクリメントして（ステップＳ４８）、ステップＳ４１に戻る。ステップＳ４１では、半導体記憶制御装置５０は、ビットベクタテーブルで、Ｋの順番であってまだ読み出していない物理ブロックの有効ページ数カウンタの値を読み出すことになる。一方、全ての物理ブロックについて有効ページ数カウンタの値を読み出した場合（ステップＳ４４：ＹＥＳ）、半導体記憶制御装置５０は、Ｋの値を、コンパクションの候補の物理ブロックのインデックスとして設定する。そして、半導体記憶制御装置５０は、インデックスＫで示される各物理ブロックについて、ビットベクタテーブルのビットベクタが「１」を示すページ（有効ページ）に記憶されているデータ（有効データ）を特定し、当該有効データをデータバッファ６７に全て読み出す。また、半導体記憶制御装置５０は、当該有効データに付加されている論理アドレスを抽出する（ステップＳ４５）。
【００５８】
そして、半導体記憶制御装置５０は、ステップＳ４５で読み出した各有効データの書き込みを、上述のｗｉｒｔｅコマンドに応じて行うデータの書き込みと同様にして行う（ステップＳ４６）。即ち、半導体記憶制御装置５０は、当該有効データを書き込むチャネルをチャネルＣＨ０〜ＣＨ３からラウンドロビンで決定し、各チャネルのＮＡＮＤ５８の消去済みのブロックのうち追記ポインタで示されるページに、当該有効データを書き込む。その後、半導体記憶制御装置５０は、有効データを書き込んだページに続く次のページであって書き込みがまだ行われていないページを示すよう追記ポインタを更新する。また、半導体記憶制御装置５０は、書き込んだ有効データに付加されている論理アドレスと、当該有効データを書き込んだページの物理アドレスとの対応関係を正引きテーブルに書き込んで更新する。正引きテーブルを更新する方法は上述の構成欄で説明した通りである。このように、コンパクションにおいても正引きテーブルを更新することで、データの論理アドレスと物理アドレスとの対応関係を常に正しく保持することができる。また、データに論理アドレスが付加されていることで、コンパクションの際に、当該論理アドレスと当該データが書き込まれる物理アドレスとの対応関係を容易に更新することが可能になる。
【００５９】
そして、データバッファ６７に読み出した全ての有効ページのデータについてデータバッファ６７からの読み出しが終了して（ステップＳ４７：ＹＥＳ）、ＮＡＮＤ５８に書き込みが終了すると、半導体記憶制御装置５０は、コンパクションの候補としたチャネルＣＨ０〜ＣＨ３の各物理ブロックに対して消去を行い、コンパクションの処理を終了する。
【００６０】
尚、コンパクションの処理を行うタイミングは、例えば、データの書き込みの要求があったときにフリーブロックの数をチェックし、その数が所定数以下となったときなどであれば良い。
【００６１】
以上のように、ホストから指定される論理アドレス及びデータが半導体記憶素子に記憶されている物理アドレスの対応関係を示す正引きテーブルを、半導体記憶素子などの不揮発性のメモリ及び容量の小さく安価なＳＲＡＭなどの揮発性のメモリで組み合わせて構成する。これにより、半導体記憶制御装置５０が揮発性のメモリとしてＳＲＡＭの他ＤＲＡＭを備えないようにすることができ、半導体記憶制御装置５０を安価に構成することができる。また、正引きテーブルの一部としてＳＲＡＭ５４に記憶させた２次テーブルを、正引きテーブルの一部としてＮＡＮＤ５８に記憶させた３次テーブルのキャッシュとして用いることで、ＮＡＮＤ５８に書き込まれたデータの論理アドレス及び物理アドレスの対応関係を全て保持可能にしつつ、ＮＡＮＤ５８への書き込み回数を抑えることができ、半導体記憶システムの寿命への悪影響を抑えることができる。
【００６２】
また、本実施の形態においては、ビットベクタテーブルを有することにより、コンパクションを効率良く高速で行うことが可能になる。コンパクションを行うためには、半導体記憶制御装置５０は、ブロック中有効データが書き込まれている有効ページがどのページであるかを識別し、当該有効ページに対応する論理アドレスを求めて、当該有効データを移動し、当該論理アドレスと移動先のページの物理アドレスとを対応付ける更新処理が必要となる。有効ページの識別及び物理アドレスの更新は、正引きテーブルを介して行うことは可能である。しかし、正引きテーブルは、論理アドレスをインデックスとした検索に最適化されて構成されている。このため、コンパクションを行う際に正引きテ―ブルを介して有効ページの識別及び物理アドレスの更新を行うことは、検索の時間的ペナルティーが大きくかかってしまう。
【００６３】
また、コンパクションの対象となる論理ブロックは、有効ページ数が少ないものが望ましい。その理由は、コンパクションによって有効ページを移動することで、多くのフリーブロックができるからである。有効ページ数が少ない論理ブロックを選択するためには、値が「１」であるビットベクタの数が少ないエントリを選択すれば良い。値が「１」であるビットベクタの数を数えるためには、例えば、Population演算（ワード中の「１」が立っているビット数を数える）を実装すれば良いが、エントリのビット幅が大きいと（例では３２０ビット）１サイクルで計算を行うのが困難になる。そのため、本実施の形態においては、半導体記憶制御装置５０は、ビットベクタの値の変化に応じて、図５に示される有効ページ数カウンタの値を更新し、コンパクションの対象となる論理ブロックを検索する際には、ビットベクタテーブルの有効ページ数カウンタの値が最小であるエントリを検索することにより、該当の論理ブロックを求める。有効ページ数カウンタの値が最小であるエントリの検索は、全ての論理ブロックに関するエントリの有効ページ数カウンタの値を各々１回読み出すことにより可能である。従って、本実施の形態における半導体記憶制御装置５０では、ビットベクタテーブルを参照することで、有効ページ数の少ない論理ブロックを容易に検索することができ、コンパクションを効率良く高速で行うことが可能になる。
【００６４】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化することができる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成することができる。例えば、実施形態に示される全構成要素からいくつかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせても良い。
【００６５】
上述した実施の形態において、半導体記憶制御装置５０で実行される各種プログラムを、インターネット等のネットワークに接続されたコンピュータ上に格納し、ネットワーク経由でダウンロードさせることにより提供するように構成しても良い。また当該各種プログラムを、インストール可能な形式又は実行可能な形式のファイルでＣＤ−ＲＯＭ、フレキシブルディスク（ＦＤ）、ＣＤ−Ｒ、ＤＶＤ（Digital Versatile Disk）等のコンピュータで読み取り可能な記録媒体に記録してコンピュータプログラムプロダクトとして提供するように構成しても良い。
【００６６】
上述した実施の形態において、プロセッサ５１の機能の一部をハードウェアによって実現させるようにしても良い。また、半導体記憶制御装置５０は、プロセッサ５１を複数備え、複数のプロセッサ５１により上述の機能が実現されるように構成しても良い。このような構成によれば、処理の高速化が図れる。
【００６７】
上述した実施の形態において、ページＥＣＣとしてはページ単位のデータ毎にＥＣＣ符号を付加しているが、ページより小さな単位（例として５１２バイトのセクター単位）でＥＣＣ符号を付加することも可能である。
【００６８】
上述した実施の形態において、半導体記憶制御装置５０に接続されるＮＡＮＤ５８の数は４つであるとしたが、接続されるＮＡＮＤの数はこれに限らない。
【００６９】
上述した実施の形態において、半導体記憶制御装置５０のメモリコントローラ５３に接続されるメモリはＳＲＡＭ５４であるとしたが、これに限らず、ＤＲＡＭであっても良いし、ＳＲＡＭ及びＤＲＡＭの両方であっても良い。この場合、正引きテーブルの一部（１次テーブル、２次テーブル及び３次テーブルのうち少なくとも１つ）が、ＤＲＡＭに記憶されるようにしても良い。
【００７０】
上述した実施の形態において、チャネルとＮＡＮＤ５８とは１対１対応させるようにしたが、これに限らず、チャネルとＮＡＮＤ５８とが１対多対応させる、即ち、１つのチャネルに対して複数のＮＡＮＤ５８が割り当てられるようにしても良い。この場合、各ＮＡＮＤ５８にはこれらを識別するための識別番号を付与するようにする。論物変換テーブルには、チャネル毎の各ブロックについて、この識別番号及び物理アドレスを記録するようにする。例えば、各チャネルに８個の半導体記憶素子に割り当てられる場合、各半導体記憶素子を識別するのに3ビット、各半導体記憶素子に含まれる4096個のブロックを識別するのに12ビットで合計15ビットを、チャネル毎の各ブロックの識別番号及び物理アドレスとして論物変換テーブルに記録するようにする。
【００７１】
上述した実施の形態において、データやページの無効又は有効を表現する方法として、ビットベクタを利用した例について説明したが、これに限られない。例えばあるブロックを選択し、ページを順に選んで、選んだページを指す論理アドレスが存在するときはそのページを有効とし、選んだページを指す論理アドレスが存在しないときはそのページを無効と判断する。論理アドレスが存在するかどうかは、正引きテーブルを順にアクセスし、選んだページを指すかどうか確認する方法を用いても良いし、物理アドレスから、論理アドレスへの逆引きテーブルを構成しておいて、物理アドレスに対応する論理アドレスが存在するかどうかを確認しても良い。
【００７２】
上述した実施の形態において、３次テーブルに対して、適当なタイミングでコンパクションを行うことが望ましい。３次テーブルのエントリのうち、有効データが記憶されている物理アドレスを示すエントリは、その物理アドレスを有する３次テーブルが記憶される記憶領域を特定する特定情報が１次テーブルのエントリにより示されている。逆に、３次テーブルのエントリにおいて、その物理アドレスを有する３次テーブルが記憶される記憶領域を特定する特定情報が１次テーブルのエントリにより示されていない場合には、当該物理アドレスに記憶されているデータは無効であり、３次テーブルにおける当該エントリは無効である。３次テーブルへの書き込みが追記方式によるものである場合、無効なエントリが増えてくると、ＮＡＮＤ５８において書き込みを実現可能な容量（実現容量）が少なくなってくる。このため、３次テーブルに対しても適当なタイミングでコンパクションを行うことで、３次テーブルの使用領域を一定の範囲に収めることができる。尚、半導体記憶制御装置５０は、３次テーブルに対してコンパクションを行って、有効なエントリを移動させたとき、当該エントリの移動前の記憶領域を特定する特定情報を示す１次テーブルのエントリにおいて当該エントリの移動後の記憶領域を特定する特定情報を示すように１次テーブルを更新する。
【００７３】
また、尚、コンパクションの効率を高め、半導体記憶制御装置５０における処理速度の低下へのインパクトを小さくするためには、３次テーブルの使用領域を大きくとり、コンパクション時の効率を高くすることが望ましい。
【００７４】
上述した実施の形態においては。３次テーブルは、ＮＡＮＤ５８に記憶されるようにしたが、これに限らず、不揮発性のメモリに記憶されるようにすれば良い。
【符号の説明】
【００７５】
５０  半導体記憶制御装置
５１  プロセッサ
５２  ＢｏｏｔＲＯＭ
５３  メモリコントローラ
５４  ＳＲＡＭ
５５  ＳＡＴＡ／ＳＡＳインタフェース
５６  バス
５７，５７Ａ〜５７Ｄ  ＮＡＮＤコントローラ
５８，５８Ａ〜５８Ｄ  ＮＡＮＤ
６０  ホストインタフェース部
６１  バッファ制御部
６２  アドレス変換部
６３  ＣＨ振り分け部
６４  コンパクション候補検出部
６５  管理テーブル更新部
６６，６６Ａ〜６６Ｄ  ＮＡＮＤ制御部
６７  データバッファ
６８  コンパクションＲｅａｄキュー
６９  管理テーブル
【図１】
2012068863.tif 000003
【図２】
2012068863.tif 000004
【図３】
2012068863.tif 000005
【図４】
2012068863.tif 000006
【図５】
2012068863.tif 000007
【図６】
2012068863.tif 000008
【図７】
2012068863.tif 000009
【図８】
2012068863.tif 000010
【図９】
2012068863.tif 000011
【図１０】
2012068863.tif 000012
【図１１】
2012068863.tif 000013
【図１２】
2012068863.tif 000014
【図１３】
2012068863.tif 000015
【図１４】
2012068863.tif 000016