(57)【特許請求の範囲】
【請求項１】
論理アドレスを、複数のセクタにより構成される複数のページを備えるＮＡＮＤ型フラッシュメモリのアクセスに用いるための物理アドレスに変換するための論理物理アドレス変換テーブルの制御方法において、
ＲＡＭ内の前記論理物理アドレス変換テーブルに、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットとして、或るページの１セクタを指示するセクタアドレスを含むアドレスセットを、Ｍ（全ページ数より少ない整数）セット格納し、
前記アドレスセットの１セット毎に、前回の参照時からの経過時間と参照回数とを参照頻度情報とし、前回の参照時からの経過時間が最も長いアドレスセットの参照回数を基準として、各アドレスセット参照回数の重み付けを行い、
前記重み付けの結果に基づき入れ換えの対象を決定することにより、１セット毎のアドレスセットの入れ換えを制御することを特徴とする
論理物理アドレス変換テーブルの制御方法。
【請求項２】
重み付けの結果が閾値を超えるアドレスセットを入れ換えの対象とし、閾値を超えるアドレスセットが無い場合には、前回の参照時からの経過時間が最も長いアドレスセットを入れ換えの対象として決定することを特徴とする請求項１に記載の論理物理アドレス変換テーブルの制御方法。
【請求項３】
複数のセクタにより構成される複数のページを備えるＮＡＮＤ型フラッシュメモリと、
論理アドレスを前記ＮＡＮＤ型フラッシュメモリのアクセスに用いる物理アドレスに変換する論理物理アドレス変換テーブルとして記憶するＲＡＭを備え、前記ＮＡＮＤ型フラッシュメモリをアクセス制御するコントローラと
を具備するメモリ装置において、
前記ＲＡＭには、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットとして、或るページの１セクタを指示するセクタアドレスを含むアドレスセットが、Ｍ（全ページ数より少ない整数）セット設けられた論理物理アドレス変換テーブルが記憶され、
前記アドレスセットの１セット毎に、前回の参照時からの経過時間と参照回数とを参照頻度情報とし、前回の参照時からの経過時間が最も長いアドレスセットの参照回数を基準として、各アドレスセット参照回数の重み付けを行い、重み付けの結果に基づき入れ換えの対象を決定することにより、１セット毎のアドレスセットの入れ換えを制御するテーブル制御手段を具備することを特徴とするメモリ装置。
【請求項４】
前記テーブル制御手段は、重み付けの結果が閾値を超えるアドレスセットを入れ換えの対象とし、閾値を超えるアドレスセットが無い場合には、前回の参照時からの経過時間が最も長いアドレスセットを入れ換えの対象として決定することを特徴とする請求項３に記載のメモリ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＮＡＮＤ型フラッシュメモリをアクセス制御するために用いる、論理物理アドレス変換テーブルの制御方法及び、その制御方法を用いたメモリ装置に関するものである。
【背景技術】
【０００２】
ＮＡＮＤ型フラッシュメモリは、ページという単位でデータの読出しと書込みが可能であり、複数のページを備えている。ただし、上書きができないメモリであるため、ＮＡＮＤ型フラッシュメモリには、ＦＡＴなどのファイルシステムの管理情報が保存されていなくともドライバとしては論理物理アドレス変換テーブルを具備するので、このファイル管理情報を論理アドレスから物理アドレスへの変換を行う論理物理アドレス変換テーブルとして、ＲＡＭに格納して用いている。
【０００３】
従来の論理物理アドレス変換テーブルは、ページ単位で論理アドレスと物理アドレスの変換を行うものであり、図８に示すように、ＮＡＮＤ型フラッシュメモリの全ページ分の変換データがＲＡＭに書込まれていた。このような構成によれば、大容量のＲＡＭが必要となる問題がある。特に近年においてはＮＡＮＤ型フラッシュメモリのプロセスの進化に伴って、ＮＡＮＤ型フラッシュメモリの大容量化が進んでおり、これに対応するためには、極めて大容量のＲＡＭが必要となっている。
【０００４】
これに対し、図９に示すように、ＮＡＮＤ型フラッシュメモリの全ページ分の変換データから一部分の変換データを取り出し、論理物理アドレス変換テーブルとしてＲＡＭに書込むものが知られている。これによれば、ＲＡＭの容量を、ＮＡＮＤ型フラッシュメモリの全ページの一部分に対応するものとすることができ、小容量のＲＡＭで済ますことが可能である。
【０００５】
しかしながら、上記のような論理物理アドレス変換テーブルを用いると、ＮＡＮＤ型フラッシュメモリのアクセス時に用いる論理アドレスと物理アドレスのセットが、上記論理物理アドレス変換テーブルに存在していないケースがあり、このようなケースを如何にして減少させるかが課題である。
【０００６】
特許文献１には、限られたＲＡＭ容量によってアクセス頻度の高い領域へのアクセス速度を上げることを目的として、不揮発性記憶装置を複数のエリアに分割し、エリア単位でアドレス変換テーブルをＲＡＭに展開するようにし、アクセス頻度により少なくとも１つのエリアのアドレス変換テーブルをＲＡＭに展開するようにし、他の少なくとも１つのエリアについては、アクセス履歴によりエリアを決定して、アドレス変換テーブルをＲＡＭに展開するようにすることが開示されている。
【０００７】
また、特許文献２には、キャッシュメモリのエントリのサイズを、実ページサイズの１／Ｎ（整数）として、実際に取り扱うデータサイズとすることにより、ヒット率を上げ、アクセスのオーバーヘッドを少なくすることが開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特願２００３−２５６２６９号公報
【特許文献２】特願２００７−３４９４４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上記の特許文献１の技術によれば、アクセス頻度が高いＦＡＴなどが格納されたエリアをＲＡＭに展開するので、アクセス速度を上げることができ、履歴により最も過去にアクセスされたエリアをＲＡＭから破棄するので、不要なエリアのアドレス変換テーブルがＲＡＭに存在するという無駄を無くすことができる。
【００１０】
しかしながら、分割したエリアの大きさに制限は設けられていないものの、ＦＡＴなどが格納されたアクセス頻度が高いことが知られたエリアを１つのエリアとしていることから、複数ページ分のアドレス変換テーブルが１エリアのアドレス変換テーブルとなっており、ある程度容量の大きなＲＡＭが必要である。
【００１１】
しかし、アクセス頻度が高いことが知られたエリアのアドレス変換テーブルを破棄しないことが、現実にアクセス頻度が高いエリアのアドレス変換テーブルがＲＡＭに残っていることの絶対的な保障とはならない。また、最も過去にアクセスされたエリアをＲＡＭから破棄することから、最も過去にアクセスされたエリアがその後にアクセスされたかについては無関係にＲＡＭから破棄される虞がある。
【００１２】
また、特許文献２の発明によれば、キャッシュメモリのエントリのサイズを、実ページサイズの１／Ｎ（整数）とするから、アドレス変換テーブルの容量を大きくする必要がないという利点がある。しかしながら、アドレス変換テーブルは、アクセス履歴や頻度を考慮した設計となっておらず、ミスヒットが多くなりアクセスのオーバーヘッドが大きくなるという問題がある。
【００１３】
本発明は上記のようなＮＡＮＤ型フラッシュメモリをアクセス制御するために用いる、論理物理アドレス変換テーブルの制御方法及び、その制御方法を用いたメモリ装置の現状に鑑みてなされたもので、その目的は、論理物理アドレス変換テーブルを格納するＲＡＭの容量を小さくすることが可能であり、しかも、アクセスのオーバーヘッドを少なくすることが可能な論理物理アドレス変換テーブルの制御方法及び、その制御方法を用いたメモリ装置を提供することである。
【課題を解決するための手段】
【００１４】
本発明に係る論理物理アドレス変換テーブルの制御方法は、論理アドレスを、複数のセクタにより構成される複数のページを備えるＮＡＮＤ型フラッシュメモリのアクセスに用いるための物理アドレスに変換するための論理物理アドレス変換テーブルの制御方法において、ＲＡＭ内の前記論理物理アドレス変換テーブルに、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットとして、或るページの１セクタを指示するセクタアドレスを含むアドレスセットを、Ｍ（全ページ数より少ない整数）セット格納し、前記アドレスセットの１セット毎に、前回の参照時からの経過時間と参照回数とを参照頻度情報とし、前回の参照時からの経過時間が最も長いアドレスセットの参照回数を基準として、各アドレスセット参照回数の重み付けを行い、前記重み付けの結果に基づき入れ換えの対象を決定することにより、１セット毎のアドレスセットの入れ換えを制御することを特徴とする。
【００１９】
本発明に係る論理物理アドレス変換テーブルの制御方法では、重み付けの結果が閾値を超えるアドレスセットを入れ換えの対象とし、閾値を超えるアドレスセットが無い場合には、前回の参照時からの経過時間が最も長いアドレスセットを入れ換えの対象として決定することを特徴とする。
【００２０】
本発明に係るメモリ装置は、複数のセクタにより構成される複数のページを備えるＮＡＮＤ型フラッシュメモリと、論理アドレスを前記ＮＡＮＤ型フラッシュメモリのアクセスに用いる物理アドレスに変換する論理物理アドレス変換テーブルとして記憶するＲＡＭを備え、前記ＮＡＮＤ型フラッシュメモリをアクセス制御するコントローラとを具備するメモリ装置において、前記ＲＡＭには、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットとして、或るページの１セクタを指示するセクタアドレスを含むアドレスセットが、Ｍ（全ページ数より少ない整数）セット設けられた論理物理アドレス変換テーブルが記憶され、前記アドレスセットの１セット毎に、前回の参照時からの経過時間と参照回数とを参照頻度情報とし、前回の参照時からの経過時間が最も長いアドレスセットの参照回数を基準として、各アドレスセット参照回数の重み付けを行い、重み付けの結果に基づき入れ換えの対象を決定することにより、１セット毎のアドレスセットの入れ換えを制御するテーブル制御手段を具備することを特徴とする。
【００２５】
本発明に係るメモリ装置では、前記テーブル制御手段は、重み付けの結果が閾値を超えるアドレスセットを入れ換えの対象とし、閾値を超えるアドレスセットが無い場合には、前回の参照時からの経過時間が最も長いアドレスセットを入れ換えの対象として決定することを特徴とする。                                                                                        
【発明の効果】
【００２６】
本発明によれば、ＲＡＭ内の論理物理アドレス変換テーブルに、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットとして、或るページの１セクタを指示するセクタアドレスを含むアドレスセットを、Ｍ（全ページ数より少ない整数）セット格納しているので、論理物理アドレス変換テーブルを格納するＲＡＭの容量を小さくすることが可能である。しかも、アドレスセットの１セット毎の参照頻度情報に基づき、１セット毎のアドレスセットの入れ換えを制御するので、アクセスのオーバーヘッドを少なくすることが可能である。
【図面の簡単な説明】
【００２７】
【図１】本発明の実施形態に係るメモリ装置の構成を示すブロック図。
【図２】ＮＡＮＤ型フラッシュメモリのブロックとページとセクタの関係を示す図。
【図３】本発明の実施形態に係るメモリ装置に備えられる論理物理アドレス変換テーブルの構成を示す図。
【図４】本発明の実施形態に係る論理物理アドレス変換テーブルの制御方法で用いられる参照頻度情報を示す図。
【図５】本発明の実施形態に係る論理物理アドレス変換テーブルの制御方法で用いられる参照頻度情報を示す図。
【図６】本発明の実施形態に係る論理物理アドレス変換テーブルの制御方法で用いられる参照頻度情報に関する重み付けにより得られる重みを示す図。
【図７】本発明の実施形態に係る論理物理アドレス変換テーブルの制御方法の処理を示すフローチャート。
【図８】従来の全面展開による論理物理アドレス変換テーブルの構成を示す図。
【図９】従来の一部展開による論理物理アドレス変換テーブルの構成を示す図。
【発明を実施するための形態】
【００２８】
以下、添付図面を参照して本発明に係る論理物理アドレス変換テーブルの制御方法及び、その制御方法を用いたメモリ装置の実施形態を説明する。各図において、同一の構成要素には同一の符号を付して、重複する説明を省略する。図１に、実施形態に係るメモリ装置のブロック図を示す。メモリ装置は、ＮＡＮＤ型フラッシュメモリ１と、このＮＡＮＤ型フラッシュメモリ１を制御するコントローラ２とを備えている。
【００２９】
ＮＡＮＤ型フラッシュメモリ１は、図２に示すように、消去の単位であるブロック＃０〜＃ｎが備えられており、各ブロック＃０〜＃ｎは、複数のページ＃００〜＃０ｎｍから構成されている。各ページ＃００〜＃ｎｍは、読み書きの単位である。更に、各ページ＃００〜＃ｎｍは、複数のセクタ＃０００〜＃ｎｍｋにより構成されている。例えば、１ページのセクタ数ｋを８とすることができる。
【００３０】
コントローラ２には、ＲＡＭにより構成される論理物理アドレス変換テーブル２１が備えられている。このＲＡＭは、論理アドレスを上記ＮＡＮＤ型フラッシュメモリ１のアクセスに使用する物理アドレスに変換する論理物理アドレス変換テーブル２１を記憶しておくためのメモリである。また、コントローラ２には、ホストとのインタフェース機能が備えられており、メモリ装置は、コントローラ２のインタフェース機能によってホスト（コンピュータ）と接続される。
【００３１】
論理物理アドレス変換テーブル２１は、論理アドレスを、複数のセクタにより構成される複数のページを備えるＮＡＮＤ型フラッシュメモリのアクセスに用いるための物理アドレスに変換するものである。ＲＡＭの論理物理アドレス変換テーブル２１は、図３に示すように、１つの論理アドレスを或るページの１セクタを指示するセクタアドレスに変換するアドレスセットが、Ｍ（全ページ数より少ない整数）セット含まれたものとしてＲＡＭ内に構成されている。つまり、１アドレスセットの物理アドレスは、ページアドレスで構成されている（ページ内の物理セクタは連続である）。
【００３２】
コントローラ２には、コントローラ２内の図示しないプロセッサの動作によって実現されるテーブル制御手段２２が備えられている。テーブル制御手段２２は、上記アドレスセットの１セット毎の参照頻度情報に基づき、１セット毎のアドレスセットの入れ換えを制御するものである。
【００３３】
テーブル制御手段２２は、参照頻度情報を、前回の参照時からの経過時間として制御を行う。例えば、前回の参照時からの経過時間が最も長いアドレスセットを入れ換えの対象とする。従って、例えばホストからデータアクセス要求があった場合において、与えられた論理アドレスを用いて論理物理アドレス変換テーブル２１を参照したが、ヒットしなかった場合には、ＮＡＮＤ型フラッシュメモリ１に格納されている前述のファイル管理情報（論理アドレスを上記ＮＡＮＤ型フラッシュメモリ１のアクセスに使用する物理アドレスに変換する情報などであり、ＦＡＴ（FILE ALLOCATION TABLE）などと称される）を参照して、所要の物理アドレスを得てアクセスを行うと共に、論理物理アドレス変換テーブル２１の更新を行う。
【００３４】
テーブル制御手段２２は、参照頻度情報を、参照回数として制御を行っても良い。例えば、テーブル制御手段２２は、論理物理アドレス変換テーブル２１に対する参照毎に参照されたアドレスセットのカウンタを１インクリメントしておく。論理物理アドレス変換テーブル２１を参照したときに、ヒットしなかった場合には、上記カウンタのカウント値が最も小さいアドレスセットを入れ換えの対象としても良い。つまり、カウンタのカウント値が最小のアドレスセットを消去し、このアドレスセットに代えてアクセスに用いた前述のファイル管理情報のアドレスセットを書込むようにできる。
【００３５】
アドレスセット＃１、＃２、＃３、・・・、＃Ｍが論理物理アドレス変換テーブル２１（ＲＡＭ）に格納されている。或るときに、図４に示すように、それぞれの参照回数が、３３、４３、５、・・・、６７であり、アドレスセット＃３の「５」が最小であるとすると、アドレスセット＃３を消去し、このアドレスセット＃３に代えてアクセスに用いた前述のファイル管理情報の新たなアドレスセットを書込むようにすることができる。
【００３６】
テーブル制御手段２２は、参照頻度情報を、前回の参照時からの経過時間と参照回数としても良い。例えば、テーブル制御手段２２は、論理物理アドレス変換テーブル２１に対する参照毎に参照されたアドレスセットのカウンタを１インクリメントしておくと共に、アドレスセット毎にタイマを設けて、論理物理アドレス変換テーブル２１の書込み時にスタートさせ、参照があるとリセットスタートさせることができる。
【００３７】
入れ換えの対象を決定する場合には、前回の参照時からの経過時間が閾値を超えているアドレスセットを求め、複数の場合には参照回数が最も少ないアドレスセットを対象とすることができる。または、参照回数が閾値より少ないアドレスセットを求め、複数の場合には前回の参照時からの経過時間が最大のアドレスセットを対象とすることができる。或いは、アドレスセット毎に、前回の参照時からの経過時間を、参照回数で割り算して、最小の値となったアドレスセットを対象とすることができる。
【００３８】
また、前回の参照時からの経過時間が最も長いアドレスセットの参照回数を基準（基準値）として、各アドレスセット参照回数の重み付けを行い、重み付けの結果に基づき入れ換えの対象を決定するようにしても良い。例えば、各アドレスセット参照回数から上記基準値を引いた値、或いは各アドレスセット参照回数を上記基準値により割り算した値が、最も小さいアドレスセットを入れ換えの対象として決定することができる。
【００３９】
更に、テーブル制御手段２２は、論理物理アドレス変換テーブル２１に対する参照毎に参照されたアドレスセットのカウンタを１インクリメントし且つ参照されなかったアドレスセットのカウンタを１ディクリメントしておくと共に、アドレスセット毎にタイマを設けて、論理物理アドレス変換テーブル２１の書込み時にスタートさせ、参照があるとリセットスタートさせるようにしても良い。
【００４０】
上記のように参照頻度情報を、前回の参照時からの経過時間と参照回数とした場合には、次のように、前回の参照時からの経過時間が最も長いアドレスセットの参照回数を基準として、各アドレスセット参照回数の重み付けを行い、重み付けの結果に基づき入れ換えの対象を決定することができる。
【００４１】
例えば、論理物理アドレス変換テーブル２１に、図５に示すように、ＡからＥのアドレスセットが記憶されており、前回の参照時からの経過時間が、１０秒、３０秒、５０秒、２０秒、４０秒であるとすれば、参照順位は、１、３、５、２、４である。また、前述のような参照回数のカウンタ値が、ＡからＥの順に、＋１０、−５、＋２０、＋９、＋５０であったとする。
【００４２】
そこで、上記のように重み付けする場合の基準は、経過時間が最も長いアドレスセットＣとなる。重み付けの処理は、基準のアドレスセットＣのカウント値「＋２０」から、それぞれのアドレスセットのカウント値を引き算して、重み付けの結果である「重み」を求める。ＡからＥのアドレスセット重み付けの結果である「重み」は、図６に示すように、それぞれ、＋１０、＋２５、０、＋１１、−３０となる。
【００４３】
上記それぞれの「重み」と閾値（ここでは、＋２０）を比較し、閾値を超える「重み」のアドレスセットを入れ換えの対象と決定する。本例では、アドレスセットＢが閾値（＋２０）を超えているので、入れ換えの対象と決定される。なお、閾値を超える「重み」のアドレスセットが無い場合には、基準のアドレスセットを入れ換えの対象と決定する。また、閾値を超える「重み」のアドレスセットが複数の場合には、「重み」が大きな方を、「重み」が同一であれば、論理アドレスが上位（或いは、下位）の方を、それぞれ入れ換えの対象とすることができる。
【００４４】
以上のような処理を行うテーブル制御手段２２を備えるメモリ装置は、例えばホストからのデータアクセス要求がなされた場合に、図７に示すようなフローチャートに対応するプログラムによって動作を行う。
【００４５】
データアクセス要求によってスタートとなり、与えられた論理アドレスに基づき論理物理アドレス変換テーブル２１をアクセスする（Ｓ１１）。アクセスによりヒットしたかを検出し（Ｓ１２）、ヒットした場合には、論理物理アドレス変換テーブル２１より求めた物理アドレスによりＮＡＮＤ型フラッシュメモリ１をアクセスする（Ｓ１３）。このとき、参照頻度情報（参照回数）を更新する（Ｓ１４）。
【００４６】
一方、上記ステップＳ１２において、ミスヒットが検出されると、ＮＡＮＤ型フラッシュメモリ１に格納されている前述のファイル管理情報を参照して、所要の物理アドレスを得てアクセスを行う（Ｓ１５）。更に、参照頻度情報として、参照回数を更新し、前回の参照時からの経過時間を求める（Ｓ１６）。
【００４７】
ステップＳ１６に続いて、参照頻度情報に基づき入れ換えの対象アドレスセットを求め（Ｓ１７）、論理物理アドレス変換テーブル２１から対象アドレスセットを消去する（Ｓ１８）。更に、消去したＲＡＭのエリアに、ステップＳ１５におけるアクセスの際に用いたアドレスセットを格納して（Ｓ１９）、エンドとなる。
【００４８】
以上のようにして、本実施形態の論理物理アドレス変換テーブルの制御方法及び、その制御方法を用いたメモリ装置によれば、論理物理アドレス変換テーブル２１に、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットとして、或るページの１セクタを指示するセクタアドレスを含むアドレスセットを、Ｍ（全ページ数より少ない整数）セットＲＡＭ内に格納したので、ＲＡＭの容量をＮＡＮＤ型フラッシュメモリの容量より小さなものとすることができる。
【００４９】
また、１つの論理アドレスを１つの物理アドレスに変換するアドレスセットが、或るページの１セクタを指示するものであるため、セクタ単位で不連続な物理アドレスを論理物理アドレス変換テーブル２１に格納することができ、しかも、アドレスセットの１セット毎の参照頻度情報に基づき、１セット毎のアドレスセットの入れ換えを制御するので、論理物理アドレス変換テーブル２１には、論理アドレス変換の際にヒットする確率が高いアドレスセットが格納されるようになり、ＮＡＮＤ型フラッシュメモリのランダムなセクタを高速でアクセスすることが可能となる。
【符号の説明】
【００５０】
１  ＮＡＮＤ型フラッシュメモリ
２  コントローラ
２１  論理物理アドレス変換テーブル
２２  テーブル制御手段
【図１】
0006429197.tif 000002
【図２】
0006429197.tif 000003
【図３】
0006429197.tif 000004
【図４】
0006429197.tif 000005
【図５】
0006429197.tif 000006
【図６】
0006429197.tif 000007
【図７】
0006429197.tif 000008
【図８】
0006429197.tif 000009
【図９】
0006429197.tif 000010