(57)【要約】【課題】コンパクション用途の記憶エリアを必要とすることなく、コンパクションのためのデータ読み出しを高速化できるようにする。【解決手段】実施形態によれば、有効クラスタ検索手段は、コンパクションのために、第１のブロック群からチャネル別に有効クラスタ群を順次検索する。リードコマンド生成手段は、チャネル別に検索された有効クラスタ群のうち、第２のブロックに同時に書き込み可能なクラスタの数に対応し、且つ第１の数のチャネル群内の第２の数のチャネル群に対応する、第２のブロックに移動されるべき有効クラスタ群を並列に読み出すのに用いられるリードコマンド群を生成する。コマンド投入手段はリードコマンド群をメモリインタフェースに投入する。決定手段は、次に生成されるべきリードコマンド群に対応する第２の数のチャネル群を、リードコマンド群投入の状況に基づいて決定する。【選択図】      図１
2012248109.tif 000002
【特許請求の範囲】
【請求項１】
第１の数のチャネル群を介してアクセスされるメモリと、
前記メモリに前記第１の数のチャネル群を介して並列にアクセスするメモリインタフェースと、
第１のブロック群から第２のブロックに有効クラスタ群を移動するコンパクションのために、前記第１のブロック群から前記チャネル別に有効クラスタ群を順次検索する有効クラスタ検索手段と、
前記チャネル別に検索された有効クラスタ群のうち、前記第２のブロックに同時に書き込み可能なクラスタの数に対応し、且つ前記第１の数のチャネル群内の第２の数のチャネル群に対応する、前記第２のブロックに移動されるべき有効クラスタ群を並列に読み出すのに用いられるリードコマンド群を生成するリードコマンド生成手段と、
前記リードコマンド群を、前記第２の数のチャネル群を介して前記メモリインタフェースに投入するコマンド投入手段と、
次に生成されるべきリードコマンド群に対応する前記第２の数のチャネル群を、リードコマンド群投入の状況に基づいて決定する決定手段と
を具備することを特徴とするメモリ装置。
【請求項２】
前記リードコマンド群投入の状況を、前回前記メモリインタフェースに投入されたリードコマンド群の最終リードコマンドに対応する第１のチャネルの位置に基づいて管理するチャネル管理手段を更に具備し、
前記決定手段は、前記第１のチャネルの位置に基づいて前記第２の数のチャネル群の先頭の第２のチャネルを決定する
請求項１記載のメモリ装置。
【請求項３】
前記決定手段は、ラウンドロビン方式に基づき、前記第１の数のチャネル群内で前記第１のチャネルの次のチャネルを前記第２のチャネルとして決定し、
前記コマンドリスト生成手段は、前記第２チャネルに投入されるべきリードコマンドから順に前記リードコマンド群を生成する
請求項２記載のメモリ装置。
【請求項４】
前記リードコマンド群投入の状況を、前回までの前記チャネル別の進捗に基づいて管理するチャネル管理手段を更に具備し、
前記決定手段は、最も進捗が進んでいるチャネルが除外されるように、前記第２の数のチャネル群を決定する
請求項１記載のメモリ装置。
【請求項５】
前記リードコマンド群投入の状況を、前回までの前記チャネル別の進捗に基づいて管理するチャネル管理手段を更に具備し、
前記決定手段は、最も進捗が遅れているチャネルが含まれるように、前記第２の数のチャネル群を決定する
請求項１または４のいずれか一項に記載のメモリ装置。
【請求項６】
第１の数のチャネル群を介してアクセスされるメモリと、前記メモリに前記第１の数のチャネル群を介して並列にアクセスするメモリインタフェースとを備えたメモリ装置において、第１のブロック群から第２のブロックに有効クラスタ群を移動するコンパクションのためのリードコマンド群生成方法であって、
前記第１のブロック群から前記チャネル別に有効クラスタ群を順次検索し、
前記チャネル別に検索された有効クラスタ群のうち、前記第２のブロックに同時に書き込み可能なクラスタの数に対応し、且つ前記第１の数のチャネル群内の第２の数のチャネル群に対応する、前記第２のブロックに移動されるべき有効クラスタ群を並列に読み出すのに用いられるリードコマンド群を生成し、
前記リードコマンド群を、前記第２の数のチャネル群を介して前記メモリインタフェースに投入し、
次に生成されるべきリードコマンド群に対応する前記第２の数のチャネル群を、リードコマンド群投入の状況に基づいて決定する
リードコマンド群生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、マルチチャネルを有するメモリ装置及び同装置におけるコンパクションのためのリードコマンド群生成方法に関する。
【背景技術】
【０００２】
ＮＡＮＤフラッシュメモリは、データを書き込む前に、例えばブロック単位でデータを消去する処理が必要な不揮発性メモリとして知られている。ＮＡＮＤフラッシュメモリでは一般に、データ消去の単位とデータ書き込みの単位とが異なる。このように、データ消去の単位とデータ書き込みの単位とが異なる、ＮＡＮＤフラッシュメモリに代表される不揮発性メモリでは、データの書き換えが進むと、無効な（最新でない）データによって、ブロック（論理ブロック）は穴あき状態となる。すると、不揮発性メモリの記憶領域を有効活用するため、コンパクションと呼ばれる処理が行われる。コンパクションとは、疎密度になったブロック内の有効データを集めて別ブロックに書き直す処理である。
【０００３】
このコンパクションの処理時間を短縮するために、従来から種々の手法が提案されている。例えば、データサイズの管理単位の異なる複数の記憶エリアを用いて、段階的に有効データを移動させていく手法が提案されている。
【０００４】
一方、上述のＮＡＮＤフラッシュメモリに代表される不揮発性メモリを備え、複数のアクセスコマンドを並列に実行するマルチチャネルを有するメモリ装置も知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１７６７０２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上記したように、従来技術では、コンパクション処理の高速化のために専用の記憶エリアを必要とする。
【０００７】
本発明の目的は、コンパクション用途の記憶エリアを必要とすることなく、コンパクションのためのデータ読み出しを高速化できる、マルチチャネルを有するメモリ装置及び同装置におけるコンパクションのためのリードコマンド群生成方法を提供することである。
【課題を解決するための手段】
【０００８】
実施形態によれば、メモリ装置は、メモリと、メモリインタフェースと、有効クラスタ検索手段と、リードコマンド生成手段と、コマンド投入手段と、決定手段とを具備する。前記メモリは、第１の数のチャネル群を介してアクセスされる。前記メモリインタフェースは、前記メモリに前記第１の数のチャネル群を介して並列にアクセスする。前記有効クラスタ検索手段は、第１のブロック群から第２のブロックに有効クラスタ群を移動するコンパクションのために、前記第１のブロック群から前記チャネル別に有効クラスタ群を順次検索する。前記リードコマンド生成手段は、前記チャネル別に検索された有効クラスタ群のうち、前記第２のブロックに同時に書き込み可能なクラスタの数に対応し、且つ前記第１の数のチャネル群内の第２の数のチャネル群に対応する、前記第２のブロックに移動されるべき有効クラスタ群を並列に読み出すのに用いられるリードコマンド群を生成する。前記コマンド投入手段は、前記リードコマンド群を、前記第２の数のチャネル群を介して前記メモリインタフェースに投入する。前記決定手段は、次に生成されるべきリードコマンド群に対応する前記第２の数のチャネル群を、リードコマンド群投入の状況に基づいて決定する。
【図面の簡単な説明】
【０００９】
【図１】実施形態に係るマルチチャネルを有するメモリ装置の典型的な構成を示すブロック図。
【図２】同実施形態で適用されるブロックリスト群の構成の一例を示す図。
【図３】同実施形態で適用される論理ブロックの構成の一例を示す図。
【図４】同実施形態で適用されるコンパクション処理の典型的な手順を説明するためのフローチャート。
【図５】同実施形態で適用されるチャネル別の有効クラスタ群の検索の例を説明するための図。
【図６】同実施形態で適用される論理アドレス及び物理アドレスのフォーマットの例を示す図。
【発明を実施するための形態】
【００１０】
以下、実施の形態につき図面を参照して説明する。  
図１は実施形態に係るマルチチャネルを有するメモリ装置の典型的な構成を示すブロック図である。本実施形態において、図１に示すメモリ装置１０は、例えばホスト（図示せず）と接続されている。ホストは、メモリ装置１０を当該ホストの記憶装置として利用する。
【００１１】
メモリ装置１０は、ＮＡＮＤフラッシュメモリ１１とＮＡＮＤコントローラ１２とを備えている。本実施形態においてメモリ装置１０は、ＮＡＮＤフラッシュメモリ１１を利用したソリッドステートドライブ（ＳＳＤ）であるものとする。ＮＡＮＤフラッシュメモリ１１は、ユーザデータを記憶するための記憶媒体である。ＮＡＮＤフラッシュメモリ１１は、複数のＮＡＮＤフラッシュメモリチップを備えており、複数のアクセスコマンドに応じてＮＡＮＤコントローラ１２によって複数のチャネル（つまりマルチチャネル）を介して並列にアクセス可能なように構成されている。なお、メモリ装置１０がＳＳＤである必要はない。また、複数のアクセスコマンドに応じて複数のチャネルを介して並列にアクセス可能であれば、ＮＡＮＤフラッシュメモリ１１に代えて、ＮＡＮＤフラッシュメモリ以外のメモリを用いても構わない。このメモリも、ＮＡＮＤフラッシュメモリと同様に、データ消去の単位とデータ書き込みの単位とが異なるものとする。
【００１２】
ＮＡＮＤコントローラ１２は、ホストからの要求に応じてＮＡＮＤフラッシュメモリ１１にアクセスする。ＮＡＮＤコントローラ１２はまた、例えばコンパクション処理のような、ブロック単位でのメモリアクセス処理のために、ＮＡＮＤフラッシュメモリ１１にアクセスする。
【００１３】
ＮＡＮＤコントローラー１２は、ＮＡＮＤインタフェース２１と、制御部２２と、コンパクション部２３と、ブロック管理部２４とを備えている。ＮＡＮＤインタフェース２１、制御部２２、コンパクション部２３及びブロック管理部２４は、内部バス２５を介して相互接続されている。
【００１４】
ＮＡＮＤインタフェース２１は、ＮＡＮＤフラッシュメモリ１１と、制御部２２及びコンパクション部２３（特にコンパクション部２３内のコマンド投入部３５）との間で情報を授受する。本実施形態においてＮＡＮＤインタフェース２１は、１６のチャネル０，１，…，１５を有しているものとする。チャネル０，１，…，１５のチャネル番号は、それぞれ、０，１，…，１５（１０進数表現）である。チャネル０，１，…，１５の各々は、２つのプレーン０，１に接続されている。プレーン０，１のプレーン番号は、それぞれ０，１である。また、１論理ブロックは６４のページ（論理ページ）０，１，…，６３で構成されるものとする。
【００１５】
本実施形態では、ライト処理及びリード処理は、いずれも１６チャネル並列に実行可能である。特にライト処理は、ページ単位に実行可能である。つまり、チャネルｐ（１６進数表現で、ｐ＝０，１，…，Ｆ）（１０進数表現では、ｐ＝０，１，…，１５）を介してのライト処理では、２（プレーン）×２クラスタ（＝４クラスタ）を同時に書き込むことができる。これに対してリード処理は、１６チャネル並列に、クラスタ単位で実行可能である。つまり、チャネルｐを介してのリード処理では、１ページあたり４クラスタが、プレーン位置及びクラスタ位置を切り替えることに基づいて、１クラスタずつ４回に分けて実行される。
【００１６】
ＮＡＮＤインタフェース２１は、エラー訂正符号（ＥＣＣ）で訂正不能なエラーが発生した場合に、エラー箇所をチャネル間のデータに基づいて訂正する。この訂正を、チャネル間誤り訂正（ＩＣＰ訂正）と呼ぶ。本実施形態では、論理ブロック内の論理ページ毎に、対応するページのＩＣＰ訂正を可能とするために、１６チャネルのうちの１チャネルを、ＩＣＰ訂正のための誤り訂正データの格納に割り当てている。この誤り訂正データの格納に割り当てられるチャネルは、論理ページ毎に所定の順序で変更されるものとするが、特定のチャネルであっても構わない。ＩＣＰ訂正のための誤り訂正データは、他の１５チャネルに格納される対応する論理ページのデータに基づいて生成される、例えばパリティデータ（チャネル間パリティデータ）である。ＮＡＮＤインタフェース２１は、このパリティデータを用いて、ＥＣＣ訂正不能な有効クラスタを含む論理ページのエラー箇所を修復するためのＩＣＰ訂正を行う。
【００１７】
制御部２２は、内部バス２５に接続された、コンパクション部２３及びブロック管理部２４のようなモジュール群を制御する。
【００１８】
コンパクション部２３は、複数のブロック（論理ブロック）の有効なデータ（より詳細には、有効なクラスタ群）を集めて、別のブロックに書き直すコンパクションを実行する。コンパクション部２３は、ブロックリスト管理部３１と、有効クラスタ検索部３２と、コマンドリスト生成部３３と、チャネル管理部３４と、コマンド投入部３５と、フリーブロックリスト管理部３６とから構成される。
【００１９】
ブロックリスト管理部３１は、コンパクションの候補となるブロックの群及びコンパクション処理中のブロックの群を各々リスト構造にて管理する。ブロックリスト管理部３１が、コンパクションの目的（種類）毎に、コンパクション候補ブロック群のリスト（コンパクション候補ブロックリスト）を保持してもよい。本実施形態では、コンパクションの目的として３種類を想定している。この３種類は、通常のコンパクション（第１のコンパクション）と、エラー修復を目的とするコンパクション（第２のコンパクション）と、ウェアレベリングを目的とするコンパクション（第３のコンパクション）である。
【００２０】
ブロックリスト管理部３１は、第１のコンパクションのために、未使用の待機状態にあるブロック（つまりフリーブロック）の数を確認する。フリーブロックは、ブロック管理部２４によって管理されている。フリーブロックの数が規定数に満たないならば、ブロックリスト管理部３１はフリーブロック枯渇状態を回避すべく、第１のコンパクションを開始する。
【００２１】
ブロックリスト管理部３１はまた、第２のコンパクションのために、定期的に、リード動作を伴うブロック毎の診断を行う。エラービットが規定値を超えて多くなったならば、ブロックリスト管理部３１は、対応するブロックのデータを、他のブロックに移動（退避）する。第２のコンパクションは、パトロールリフレッシュとも呼ばれる。
【００２２】
メモリ装置１０の寿命は、各ブロックの消去回数及び消去時間間隔に依存する。そこで、メモリ装置１０の延命のために、全ブロックの疲弊度を平準化する必要がある。この平準化をウェアレベリングと呼ぶ。このウェアレベリング目的のコンパクション（つまり第３のコンパクション）は、図示せぬウェアレベリング部にて、ウェアレベリングが必要と判定された場合に開始される。
【００２３】
フリーブロックリスト管理部３６は、コンパクションのための全有効クラスタの移動（移動要求の実行）が完了したブロックの群（つまり、フリーブロックの候補となるブロックの群）を、リスト構造（フリーブロックリスト）にて管理する。
【００２４】
図２は、本実施形態においてブロックリスト管理部３１及びコマンドリスト生成部３３によって保持・管理されるブロックリスト群の構成の一例を示す。  
図２において、コンパクション候補ブロックリスト２０１は、第１のコンパクション目的に適用可能なコンパクション候補ブロック（Ｂｌｋ）群のリストである。コンパクション候補ブロックリスト２０２は、第２のコンパクション目的に適用可能なコンパクション候補ブロック群のリストである。コンパクション候補ブロックリスト２０３は、第３のコンパクション目的に適用可能なコンパクション候補ブロック群のリストである。コンパクション処理ブロックリスト２０４は、コンパクション処理中のブロック群のリストである。ブロックリスト２０１〜２０４は、ブロックリスト管理部３１（より詳細には、ＤＲＡＭのようなメモリ内の、ブロックリスト管理部３１に割り当てられている領域）に保持される。
【００２５】
フリーブロック候補リスト２０５は、上述のフリーブロックの候補となるブロック（フリーブロック候補）の群のリストである。
【００２６】
ブロックリスト管理部３１は、３種類のコンパクション目的に対応したコンパクション候補ブロックリスト２０１〜２０３に、当該目的に基づいて優先順位を付す。この優先順位に基づいて、ブロックリスト管理部３１は、コンパクション処理ブロックリスト２０４を生成する。図２のコンパクション処理ブロックリスト２０４の例では、１度にコンパクションの対象とするブロック数を３つとした場合を示している。コンパクションが進んで現在処理中のブロック群が減少すると、ブロックリスト管理部３１は、上述の優先順位に従って、随時コンパクション候補ブロックリスト２０１〜２０３のいずれかからコンパクション処理ブロックリスト２０４に、コンパクションの対象とするブロックを図２において矢印２０６で示すように補充（移動）する。
【００２７】
フリーブロックリスト管理部３６は、コンパクション処理ブロックリスト２０４で管理されるブロック群のうち全有効クラスタの移動が完了したブロックを、フリーブロック候補として図２において矢印２０６で示すようにフリーブロック候補リスト２０５に移動する。その後、フリーブロック候補リスト２０５に移動されたブロックのフリーブロック化を実施すべく、フリーブロックリスト管理部３６はその旨をブロック管理部２４へ通知する。
【００２８】
なお本実施形態において、上述のコンパクション候補ブロックリスト２０１〜２０３、コンパクション処理ブロックリスト２０４及びフリーブロック候補リスト２０５で直接管理されるのは、ブロックを識別するためのブロックＩＤである。
【００２９】
図３は、同実施形態において適用される論理ブロックの構成の一例を示す。  
本実施形態で適用される論理ブロックは、図３に示すように、ページ０〜６３の６４ページ（論理ページ）から構成される。各ページは、６４クラスタから構成される。つまり、１論理ブロックは、４，０９６（６４×６４）のクラスタＣ００００，Ｃ０００１，Ｃ０００２，Ｃ０００３，Ｃ１０００，Ｃ１００１，Ｃ１００２，Ｃ１００３，…，ＣＦ３Ｆ０，ＣＦ３Ｆ１，ＣＦ３Ｆ２，ＣＦ３Ｆ３から構成される。
【００３０】
論理ブロック内の１つのクラスタをＣｐｑｒｓのように表記する。ここで、ｐ（０，１，…，Ｆ）は、クラスタＣｐｑｒｓが属するチャネルのチャネル番号を示す１桁の１６進数であり、ｑｒ（００，０１，…，３Ｆ）は、クラスタＣｐｑｒｓが属するページのページ番号を示す２桁の１６進数である。ｓ（０，１，２，３）は、クラスタＣｐｑｒｓが属するチャネル内の、それぞれプレーン位置のプレーン番号及びクラスタ位置のクラスタ番号の組み合わせ（プレーン−クラスタ番号）を示す１桁の１６進数である。
【００３１】
ｓ＝０はプレーン番号０とクラスタ番号０との組み合わせを、ｓ＝１はプレーン番号０とクラスタ番号１との組み合わせを、それぞれ示す。ｓ＝２はプレーン番号１とクラスタ番号０との組み合わせを、ｓ＝３はプレーン番号１とクラスタ番号１との組み合わせを、それぞれ示す。
【００３２】
論理ブロック内のクラスタＣｐｑｒｓは、チャネル番号ｐ、ページ番号ｑｒ及びプレーン−クラスタ番号ｓの組み合わせによって特定される。クラスタＣｐｑｒｓは、チャネル番号ｐのチャネル内の、プレーン−クラスタ番号ｓによって示されるプレーン位置の、プレーン−クラスタ番号ｓによって示されるクラスタ位置に書き込まれている。
【００３３】
本実施形態では、１論理ブロックに３２の物理ブロックが割り当てられる。３２の物理ブロックは、１６のチャネル０，１，…，１５のそれぞれプレーン０，１に対応する。各物理ブロックは、１ページ当たり２クラスタから構成される。
【００３４】
次に、図１に示すメモリ装置１０のＮＡＮＤコントローラ１２内のコンパクション部２３によるコンパクション処理の典型的な手順について、図４のフローチャートを参照して説明する。
【００３５】
まず、コンパクション部２３のコマンドリスト生成部３３は開始チャネル設定手段として機能して、後述するコマンドリスト生成の起点となるチャネル（以下、開始チャネルと称する）のチャネル番号（以下、開始コマンドチャネル番号と称する）ＳＣＮを初期チャネル番号に設定する（ステップ４０１）。この初期チャネル番号は、例えばコンパクション処理の開始時に、チャネル管理部３４によって決定されて、コマンドリスト生成部３３に通知されるものとする。ここでは、初期チャネル番号は０であり、チャネル０を示すものとする。
【００３６】
有効クラスタ検索部３２は、コンパクション処理ブロックリスト２０４で管理されるブロック（論理ブロック）群から、コンパクションに用いられる有効クラスタ群をチャネルｐ別に検索する（ステップ４０２）。有効クラスタ検索部３２は、このチャネルｐ別に有効クラスタ群を検索するために、チャネルｐ毎に検索ポインタＰｐを保持する。
【００３７】
図５は、同実施形態において適用される有効クラスタ検索部３２によるチャネルｐ毎の有効クラスタ群の典型的な検索を説明するための図である。図５には、コンパクション処理中の２つのブロック（論理ブロック）５１及び５２が示されている。ブロック５１及び５２は、図２に示すコンパクション処理ブロックリスト２０４内の３つのブロックのうちの先頭から２つのブロックである。コンパクション処理ブロックリスト２０４内の最終ブロックは、図５では省略されている。図５において、矢印Ａ０，Ａ１，…，Ａ１５は、チャネル０，１，…１５における検索ポインタＰ０，Ｐ１，…Ｐ１５の移動経路を示す。つまり矢印Ａ０，Ａ１，…，Ａ１５は、チャネル０，１，…１５における有効クラスタ検索の順序を示す。
【００３８】
有効クラスタ検索部３２は、例えばチャネル０（ｐ＝０）であれば、検索ポインタＰ０に基づいて、矢印Ａ０で示されるように、クラスタＣ００００，Ｃ０００１，Ｃ０００２，Ｃ０００３，Ｃ００１０，Ｃ００１１…の順に当該クラスタが有効であるかを確認する。本実施形態では、この確認は、制御部２２を介して後述するビットマップを間接的に参照することにより行われるものとする。しかし有効クラスタ検索部３２が直接ビットマップを参照してもよい。有効クラスタ検索部３２は、１つのクラスタについて当該クラスタが有効であるかを確認する都度、検索ポインタＰ０をチャネル０内の次のクラスタを指すように進める。
【００３９】
ステップ４０２において有効クラスタ検索部３２は、無効クラスタをスキップし、有効クラスタが最大４個検索されるまでチャネルｐ別の検索を続ける。有効クラスタ検索部３２は、この検索において、ＮＵＬＬ物理ブロック内の対応するクラスタ（以下、ＮＵＬＬクラスタと称する）もスキップする。ＮＵＬＬ物理ブロックとは、ＮＡＮＤフラッシュメモリ１１の経時変化により、エラー率が規定値を超えた物理ブロックを指す。有効クラスタ、無効クラスタ及びＮＵＬＬ物理ブロックは、後述するようにブロック管理部２４によって管理される。
【００４０】
有効クラスタ検索部３２によって検索される有効クラスタの数の最大値４は、チャネルｐに対応するクラスタ数に一致する。通常は、検索される有効クラスタの数は、この最大値４に一致する。但し、コンパクションに用いられる最後の有効クラスタ群（または有効クラスタ）を検索する場合、検索される有効クラスタの数が４に満たないこともある。
【００４１】
本実施形態では前述したように、ブロック（論理ブロック）内のページ（論理ページ）毎に、対応するページのＩＣＰ訂正を可能とするために、１６チャネルのうちの１チャネルを、ＩＣＰ訂正のための誤り訂正データ（チャネル間パリティデータ）の格納に割り当てている。このチャネル間パリティデータの格納に割り当てられるチャネルをパリティチャネルと呼ぶ。本実施形態では、パリティチャネルはページ毎に変更される。コンパクション処理では、複数のブロック内の有効クラスタ群を集めて別ブロックに移動する（書き直す）際に、ページ毎にチャネル間パリティデータが生成される。このため、パリティチャネル内のクラスタは、コンパクション処理では不要である。
【００４２】
そこで有効クラスタ検索部３２は、上述のチャネルｐ別の検索において、無効クラスタ及びＮＵＬＬクラスタだけでなく、パリティチャネル内の対応するクラスタ（以下、パリティクラスタと称する）もスキップする。ページ毎のパリティチャネルは、ブロック管理部２４によって管理される。
【００４３】
図５の例では、チャネル０における有効クラスタの検索が最も進んでおり、ブロック５２のページ０まで進んでいるものとする。これに対して、例えばチャネル１，１５における有効クラスタの検索は、ブロック５１のページ６３までしか進んでいない。このように、有効クラスタの検索の進捗に、チャネル間でばらつきが生じる。これにより、後述するコンパクションリードコマンド群の生成（投入）の進捗も、チャネル間でばらつきが生じる。なお、チャネル０における有効クラスタの検索が最も進んでいる理由は、例えばブロック５１において、チャネル０に対応するクラスタ群に含まれる有効クラスタ群の数が他のチャネルに比べて少ないためである。但し本実施形態では、後述するようにチャネル間の進捗のばらつきを低減する手法を適用している。
【００４４】
ブロック管理部２４は、ブロック（論理ブロック）毎に、当該ブロックに割り当てられている３２の物理ブロックを、例えばブロック管理テーブルにより管理する。ブロック管理テーブルは、ブロック管理部２４（より詳細には、ＤＲＡＭのようなメモリ内の、ブロック管理部２４に割り当てられている領域）に保持される。本実施形態では、ブロック管理部２４は、物理ブロックがＮＵＬＬ物理ブロックであるかをブロック管理テーブルにより管理する。ブロック管理部２４はまた、物理ブロックに対応するページ（論理ページ）０〜６３のチャネル毎に、パリティチャネルであるかをブロック管理テーブルにより管理する。
【００４５】
ブロック管理部２４は更に、ブロックのページ毎に、当該ページを構成する６４のクラスタが有効クラスタであるか或いは無効クラスタであるかを、ビットマップ（ビットマップテーブル）により管理する。１ページに対応するビットマップは、６４のクラスタに対応する６４ビットで構成され、ブロック管理部２４（より詳細には、ＤＲＡＭのようなメモリ内の、ブロック管理部２４に割り当てられている領域）に保持される。本実施形態では、１ブロックにつき、６４のビットマップが用いられる。
【００４６】
コマンドリスト生成部３３は、有効クラスタ検索部３２によってチャネル別に検索された有効クラスタ群に基づいて、コンパクションリードのためのリードコマンド（以下、コンパクションリードコマンドと称する）の群のセット（コンパクションリードコマンドセット）を生成する（ステップ４０３）。コンパクションリードコマンドセットは、有効クラスタの移動先（つまりコンパクション先）のブロック（論理ブロック）のページ単位に生成される。有効クラスタの移動先のブロックには、フリーブロックリスト管理部３６によって管理されているフリーブロックが用いられる。この場合、有効クラスタの移動先として用いられるブロックは、フリーブロックリストから外される。
【００４７】
コンパクションリードコマンド群の各々は、１有効クラスタの読み出しを指定する。ＮＡＮＤインタフェース２１は、コンパクションリードコマンド群を、１クラスタ単位で最大１６チャネル並列に実行可能である。このため、コンパクションリードコマンドセットに含まれるチャネル別のコンパクションリードコマンドの数は最大４である。
【００４８】
本実施形態においてＮＡＮＤインタフェース２１は、コンパクションリードコマンド群の実行によりＮＡＮＤフラッシュメモリ１１から読み出したデータに基づいて、自動的にページ（論理ページ）単位でライトコマンドを生成する。前述したように、１ページは６４クラスタから構成される。したがって、本実施形態のように１６チャネルのうちの１つを、ページ毎にパリティチャネルに割り当てる場合、ＮＡＮＤインタフェース２１は最大６０クラスタを１５（６０／４）のチャネルを介してＮＡＮＤフラッシュメモリ１１に同時に書き込むことができる。更に、データ移動先のブロックにＮＵＬＬ物理ブロックが存在する場合は、６０クラスタからＮＵＬＬ物理ブロック数×４クラスタを減算した値が、同時に書き込み可能な最大クラスタ数Ｎとなる。Ｎに対応するチャネルの数はＮ／４である。
【００４９】
そこで、上記ステップ４０３においてコマンドリスト生成部３３は、前記の条件に基づいて算出された最大クラスタ数Ｎに到達するまで、開始コマンドチャネル番号ＳＣＮの示すチャネル（ここではチャネル０）から順に有効クラスタ群を読み出すためのコンパクションリードコマンド群を生成する。コンパクションリードコマンド群の各々は、読み出されるべき（移動されるべき）クラスタを指定する物理アドレスを含む。このコンパクションリードコマンド群の生成のために、コマンドリスト生成部３３は、読み出されるべきクラスタを指定する論理アドレスを物理アドレスに変換する。
【００５０】
図６は、本実施形態で適用される論理アドレス及び物理アドレスのフォーマットの例を示す。論理アドレスは、対応するクラスタが属する論理ブロックの論理ブロックＩＤと、ページ番号、プレーン番号、チャネル番号及びクラスタ番号とから構成される。論理アドレスは、メモリ装置１０にＮＡＮＤフラッシュメモリ１１が用いられている本実施形態では、論理ＮＡＮＤクラスタアドレスとも呼ばれる。物理アドレスは、対応するクラスタが属する物理ブロックを識別するための物理ブロックＩＤと、プレーン番号、ページ番号、クラスタ番号及びセクタ番号とから構成される。この物理アドレスは、物理ＮＡＮＤクラスタアドレスとも呼ばれる。論理アドレスから物理アドレスへの変換には、周知の論理−物理アドレス変換テーブル（以下、論物変換テーブルと称する）が用いられる。論物変換テーブルは、図示せぬテーブル管理部によって保持・管理されている。
【００５１】
コマンドリスト生成部３３は、生成されたコンパクションリードコマンド群のセット、つまりコンパクションリードコマンドセット（コマンドリスト）をコマンド投入部３５に与える。コマンドリスト生成部３３はまた、コマンドリスト中の最終コンパクションリードコマンドの指定するクラスタが属するチャネルのチャネル番号（以下、最終コマンドチャネル番号と称する）を、チャネル管理部３４に通知する。
【００５２】
コマンド投入部３５は、コマンドリスト生成部３３から受け取ったコンパクションリードコマンドセットに含まれているコンパクションリードコマンド群を、チャネル番号を異にする例えばＮ／４個のコンパクションリードコマンド群を単位にＮＡＮＤインタフェース２１に投入する（ステップ４０４）。ＮＡＮＤインタフェース２１に投入されたコンパクションリードコマンド群は、当該ＮＡＮＤインタフェース２１内のコマンドキュー（図示せず）に格納される。
【００５３】
ＮＡＮＤインタフェース２１は、コマンドキューから格納順に、Ｎ／４個のコンパクションリードコマンド群を取り出す。ＮＡＮＤインタフェース２１は、取り出されたＮ／４個のコンパクションリードコマンド群に基づき、それぞれ対応するチャネルを介してＮＡＮＤフラッシュメモリ１１に並列にアクセスする。これによりＮＡＮＤインタフェース２１は、ＮＡＮＤフラッシュメモリ１１からＮ／４個のクラスタ（有効クラスタ）を並列に読み出す。ＮＡＮＤインタフェース２１は、以上の動作を４回繰り返すことにより、移動先ブロックの１ページに書き込まれるべきＮ個のクラスタを取得する（ステップ４０５）。
【００５４】
ＮＡＮＤインタフェース２１は、取得したＮのクラスタを、移動先ブロックの対応するページにチャネル別、プレーン別、及びクラスタ位置別に書き込むためのライトコマンド（以下、コンパクションライトコマンドと称する）の群のセット（コンパクションライトコマンドセット）を生成する。コンパクションライトコマンドセットは、バリティチャネルに対応する４個のクラスタを、プレーン別、及びクラスタ位置別に並列に書き込むための４個のコンパクションライトコマンドも含む。コンパクションライトコマンド群の各々は、クラスタが書き込まれるべき位置を指定する物理アドレスを含む。このコンパクションライトコマンド群の生成のために、ＮＡＮＤインタフェース２１は、クラスタが書き込まれるべき位置を指定する論理アドレスを物理アドレスに変換する。ＮＡＮＤインタフェース２１は、生成されたコンパクションライトコマンドセットに基づいてＮＡＮＤフラッシュメモリ１１に並列にアクセスすることにより、ステップ４０５で取得されたＮ個のクラスタを移動先ブロックに同時に書き込む（ステップ４０６）。これにより、コンパクションのための１回の処理が終了する。
【００５５】
制御部２２は、移動先ブロックに移動されるべき有効クラスタが残っているを判定する（ステップ４０７）。もし、移動されるべき有効クラスタが残っているならば（ステップ４０７のＹｅｓ）、制御部２２はコマンドリスト生成部３３に制御を渡す。するとコマンドリスト生成部３３は開始チャネル決定手段として機能する。そしてコマンドリスト生成部３３は、次のコマンドリスト（コンパクションリードコマンドセット）の生成のために、コンパクションリードコマンド群投入の状況に基づいて、次の開始コマンドチャネル番号を決定する（ステップ４０８）。コンパクションリードコマンド群投入の状況は、チャネル別の有効クラスタ群の検索の状況に対応する。
【００５６】
本実施形態では、コンパクションリードコマンド群投入の状況は、チャネル管理部３４によって管理される。チャネル管理部３４は、このコンパクションリードコマンド群投入の状況を、例えばコマンドリスト生成部３３によって通知された最終コマンドチャネル番号に基づいて管理する。この最終コマンドチャネル番号は、最も最近に（前回）ＮＡＮＤインタフェース２１に投入されたリードコマンド群の最終コンパクションリードコマンドに対応するチャネル（より詳細には、最終コンパクションリードコマンドの指定するクラスタが属するチャネル）のチャネル番号である。
【００５７】
そこでコマンドリスト生成部３３は、次の開始コマンドチャネル番号を決定するために、チャネル管理部３４から最終コマンドチャネル番号を受け取る。コマンドリスト生成部３３は、受け取った最終コマンドチャネル番号に基づき、次の開始コマンドチャネル番号を決定すると、ステップ４０９に進む。ステップ４０９においてコマンドリスト生成部３３は、再び開始チャネル設定手段として機能して、開始コマンドチャネル番号ＳＣＮを、決定された次の開始コマンドチャネル番号に更新する。本実施形態では、この開始コマンドチャネル番号ＳＣＮはラウンドロビン方式に基づいて、次のように決定される。
【００５８】
１回目の有効クラスタ検索においてチャネル０〜１４が処理対象であり、チャネル０から順にチャネル１４まで、対応するコンパクションリードコマンドが生成されたものとする。つまり、１回目の処理における最終コマンドチャネル番号が１４であったものとする。この場合、コマンドリスト生成部３３は、次（２回目）の開始コマンドチャネル番号ＳＣＮとして、１回目の処理における最終コマンドチャネル番号１４に後続するチャネル番号１５を決定する。これにより上記ステップ４０９では、開始コマンドチャネル番号ＳＣＮが、０（初期値）から１５に更新される。最終コマンドチャネル番号ＳＣＮがチャネル０〜１５の最後のチャネルを示す１５である場合、ラウンドロビン方式を適用する本実施形態では、次の開始コマンドチャネル番号ＳＣＮは０となる。
【００５９】
さて、開始コマンドチャネル番号ＳＣＮが１５に更新されると（ステップ４０９）、有効クラスタ検索部３２は、チャネルｐ別に、検索ポインタＰｐに基づく有効クラスタ検索を再び開始する（ステップ４０２）。これによりコマンドリスト生成部３３は、２回目の処理（ステップ４０３）において、チャネル１５、チャネル０、チャネル１…の順に、Ｎmzx個のコンパクションリードコマンドを生成する。
【００６０】
なお、チャネル管理部３４が決定手段として機能することにより、当該チャネル管理部３４が次の開始コマンドチャネル番号ＳＣＮをラウンドロビン方式に基づいて決定してもよい。つまりチャネル管理部３４が上記ステップ４０８を実行してもよい。この場合、チャネル管理部３４が、決定された開始コマンドチャネル番号ＳＣＮをコマンドリスト生成部３３に通知すればよい。また、コマンドリスト生成部３３及びチャネル管理部３４とは独立の決定手段が、次の開始コマンドチャネル番号ＳＣＮを決定してもよい。
【００６１】
更に、チャネル管理部３４が開始チャネル設定手段として機能して、上記ステップ４０１を実行してもよい。つまり１回目の処理のために、当該１回目の処理の開始時のような適切なタイミングで、チャネル管理部３４が開始コマンドチャネル番ＳＣＮ号を初期設定してもよい。同様に、チャネル管理部３４が上記ステップ４０９を実行してもよい。
【００６２】
このように本実施形態においては、穴あき状態にある複数のブロックから読み出されるべき有効クラスタが、チャネル別に先頭ページから順に検索される。このため本実施形態によれば、コンパクションのために有効クラスタを複数のチャネルを介して並列に読み出す処理の並列度を高めることができる。つまり、有効クラスタ読み出しの並列度を高めることができる。これにより、有効クラスタの移動のための専用の記憶エリアを必要とすることなく、コンパクション処理全体に要する時間を短縮できる。
【００６３】
ここで、本実施形態とは異なって、穴あき状態にある複数のブロックを、全チャネルにまたがって、ページ単位で先頭ページから順に検索するものとする。穴あき状態にあるブロックでは、同一ページ内で有効クラスタが存在しない多くのチャネルが出現する可能性が高い。このようなページでは、有効クラスタ読み出しの並列度が低減する。このような状況は、複数のブロックの全ページに亘って発生する可能性が高いため、コンパクション処理全体に要する時間が長くなる。
【００６４】
しかも本実施形態では、１回の並列リード処理毎に、開始コマンドチャネル番号ＳＣＮが、ラウンドロビン方式に基づき、先行する開始コマンドチャネル番号に後続するチャネル番号に切り替えられる。これにより、前回の並列リード処理で用いられなかったチャネルが、次の並列リード処理で優先的に利用される。このため、チャネル別に有効クラスタを検索をしていながら、チャネル間の進捗ばらつきを低減した状態で、有効クラスタ読み出しの並列度を高めることができる。よって、コンパクション処理全体に要する時間を一層短縮することができる。
【００６５】
なお、チャネル間の進捗ばらつきを低減するための手法は、上記実施形態に限らない。例えば、開始コマンドチャネル番号ＳＣＮの示すチャネルの進捗が、１６のチャネルの中で最も進んでいる場合、開始コマンドチャネルを更に次のチャネルに変更してもよい。また、開始コマンドチャネル番号ＳＣＮをランダムに決定してもよい。
【００６６】
更に、チャネル管理部３４が、コンパクションリードコマンド群投入の状況を、前回までの前記チャネル別の進捗に基づいて管理してもよい。この場合、決定手段（決定手段として機能するチャネル管理部３４またはコマンドリスト生成部３３）は、最も進捗が進んでいるチャネルが除外されるように、生成されるべきＮ個のコンパクションリードコマンド群に対応するチャネル群を決定すればよい。また、最も進捗が遅れているチャネルが含まれるように、決定手段が上述のチャネル群を決定してもよい。更に、最も進捗が進んでいるチャネルが除外され、且つ最も進捗が遅れているチャネルが含まれるように、決定手段上述のチャネル群を決定してもよい。
【００６７】
以上説明した少なくとも１つの実施形態によれば、コンパクション用途の記憶エリアを必要とすることなく、コンパクションのためのデータ読み出しを高速化できる、マルチチャネルを有するメモリ装置及び同装置におけるコンパクションのためのリードコマンド群生成方法を提供することができる。
【００６８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００６９】
１０…メモリ装置、１１…ＮＡＮＤフラッシュメモリ（メモリ）、１２…ＮＡＮＤコントローラ、２１…ＮＡＮＤインタフェース（メモリインタフェース）、２２…制御部、２３…コンパクション部、２４…ブロック管理部、２５…内部バス、３１…ブロックリスト管理部、３２…有効クラスタ検索部、３３…コマンドリスト生成部（決定手段）、３４…チャネル管理部（決定手段）、３５…コマンド投入部、３６…フリーブロックリスト管理部。
【図１】
2012248109.tif 000003
【図２】
2012248109.tif 000004
【図３】
2012248109.tif 000005
【図４】
2012248109.tif 000006
【図５】
2012248109.tif 000007
【図６】
2012248109.tif 000008