(57)【特許請求の範囲】
【請求項１】
複数の記憶領域を有する記憶装置と、
前記記憶領域を複数含むブロック毎に、各ブロックに含まれる記憶領域を識別する物理アドレスに対応する論理アドレスのうち所定条件を満たす論理アドレスを検索開始位置として設定する開始位置設定部と、
前記論理アドレスと前記物理アドレスとの対応を表す変換テーブルの前記検索開始位置から論理アドレスを所定の順序で選択していく選択部と、
前記選択部により選択された論理アドレスに対応付けられた物理アドレスを、前記変換テーブルから取得する取得部と、
所定の条件を用いて、前記取得部により取得された物理アドレスが示す記憶領域に格納されたデータを移動させるか否かを判定する判定部と、
前記判定部が、前記データを移動させると判定した場合は、前記取得部により取得された物理アドレスが示す記憶領域に格納されたデータを、他の記憶領域に移動させる移動部と、
前記変換テーブルに格納された物理アドレスのうち、前記選択部により選択された論理アドレスに対応付けられた物理アドレスを、前記他の記憶領域を示す物理アドレスに更新する更新部と
を有することを特徴とする情報処理装置。
【請求項２】
前記開始位置設定部は、各前記ブロックの物理アドレスに対応する前記記憶領域の論理アドレスのうち最小の論理アドレスを検索開始位置とし、
前記選択部は、大きくなる順に論理アドレスを選択していく
ことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記開始位置設定部は、各前記ブロックの物理アドレスに対応する前記記憶領域の論理アドレスのうち最大の論理アドレスを検索開始位置とし、
前記選択部は、小さくなる順に論理アドレスを選択していく
ことを特徴とする請求項１に記載の情報処理装置。
【請求項４】
前記判定部は、前記ブロックにおける有効なデータを格納している前記記憶領域の数が閾値より少ない場合に、データを移動すると判定することを特徴とする請求項１に記載の情報処理装置。
【請求項５】
前記選択部は、有効なデータを格納している前記記憶領域が閾値以下のブロックを選択し、選択したブロックの検索開始位置から論理アドレスを所定の順番に選択し、
前記判定部は、物理アドレスが前記選択部により取得されたブロックに含まれる場合に、データを移動すると判定する
ことを特徴とする請求項１に記載の情報処理装置。
【請求項６】
記憶領域を複数含むブロック毎に、各ブロックに含まれる記憶領域を識別する物理アドレスに対応する論理アドレスのうち所定条件を満たす論理アドレスを検索開始位置として設定する開始位置設定部と、
前記論理アドレスと前記物理アドレスとの対応を表す変換テーブルの前記検索開始位置から論理アドレスを所定の順序で選択していく選択部と、
前記選択部により選択された論理アドレスに対応付けられた物理アドレスを、前記変換テーブルから取得する取得部と、
所定の条件を用いて、前記取得部により取得された物理アドレスが示す記憶領域に格納されたデータを移動させるか否かを判定する判定部と、
前記判定部が、前記データを移動させると判定した場合は、前記取得部により取得された物理アドレスが示す記憶領域に格納されたデータを、他の記憶領域に移動させる移動部と、
前記変換テーブルに格納された物理アドレスのうち、前記選択部により選択された論理アドレスに対応付けられた物理アドレスを、前記他の記憶領域を示す物理アドレスに更新する更新部と
を有することを特徴とする制御回路。
【請求項７】
記憶領域を複数含むブロック毎に、各ブロックに含まれる記憶領域を識別する物理アドレスに対応する論理アドレスのうち所定条件を満たす論理アドレスを検索開始位置として設定し、
前記論理アドレスと前記物理アドレスとの対応を表す変換テーブルの前記検索開始位置から論理アドレスを所定の順序で選択し、
選択した論理アドレスに対応付けられた物理アドレスを、前記変換テーブルから取得し、
所定の条件を用いて、取得した物理アドレスが示す記憶領域に格納されたデータを移動させるか否かを判定し、
前記データを移動させると判定した場合は、取得した物理アドレスが示す記憶領域に格納されたデータを、他の記憶領域に移動し、
前記変換テーブルに格納された物理アドレスのうち、選択した論理アドレスに対応付けられた物理アドレスを、前記他の記憶領域を示す物理アドレスに更新する
処理をコンピュータに実行させることを特徴とする制御プログラム。
【請求項８】
記憶領域を複数含むブロック毎に、各ブロックに含まれる記憶領域を識別する物理アドレスに対応する論理アドレスのうち所定条件を満たす論理アドレスを検索開始位置として設定し、
前記論理アドレスと前記物理アドレスとの対応を表す変換テーブルの前記検索開始位置から論理アドレスを所定の順序で選択し、
選択した論理アドレスに対応付けられた物理アドレスを、前記変換テーブルから取得し、
所定の条件を用いて、取得した物理アドレスが示す記憶領域に格納されたデータを移動させるか否かを判定し、
前記データを移動させると判定した場合は、取得した物理アドレスが示す記憶領域に格納されたデータを、他の記憶領域に移動し、
前記変換テーブルに格納された物理アドレスのうち、選択した論理アドレスに対応付けられた物理アドレスを、前記他の記憶領域を示す物理アドレスに更新する
ことを特徴とする制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、制御回路、制御プログラム、及び制御方法に関する。
【背景技術】
【０００２】
従来、磁気ディスクよりも高速に動作する不揮発性メモリを用いた情報処理装置が知られている。このような情報処理システムの一例として、ＮＡＮＤフラッシュメモリデバイスをストレージ等の記憶装置として使用する情報処理装置が知られている。なお、以下の説明では、ＮＡＮＤフラッシュメモリデバイスをＮＡＮＤデバイスと記載する。【０００３】
ここで、ＮＡＮＤデバイスは、データの記憶領域である物理ページ単位でデータの書込み、読出し、データの更新に係る移動を行い、複数の物理ページを含む物理ブロック単位でデータの消去を行う。このため、ＮＡＮＤデバイスは、有効なデータと無効なデータとが混在した物理ブロックを有する場合がある。また、ＮＡＮＤデバイスは、データを消去する際に素子が劣化するので、頻繁に更新されるデータが書込まれた物理ページと、あまり更新されないデータが書込まれた物理ページとでは、素子が劣化する速度にばらつきが発生する。【０００４】
このため、各物理ブロックに対するデータの書込み状況やデータの書込時刻に応じて、各物理ブロックに書込まれたデータの移動を実行し、データの整理や劣化の平準化を行うＮＡＮＤコントローラが知られている。例えば、ＮＡＮＤコントローラは、物理ブロックごとに、各物理ページのデータが有効であるか否かを示す情報と、最後にデータが書き込まれた時刻を示す情報とが格納された管理情報テーブルを有する。【０００５】
そして、ＮＡＮＤコントローラは、管理情報テーブルを参照し、物理ブロックごとに、有効なデータの数やデータが書込まれてから経過した時間に応じて、データを移動させるか否かを判定する。その後、ＮＡＮＤコントローラは、データを移動させると判定した場合は、物理ブロックに書込まれた有効なデータを、予備ブロックの物理ページに移動し、選択した物理ブロックのデータを消去することで、新たな予備ブロックの確保や、劣化の平準化を行う。【０００６】
また、ＮＡＮＤコントローラは、情報処理装置が実行するシステムがデータの指定に用いる論理アドレスを、データが格納された物理ページを示す物理アドレスに変換するアドレス変換テーブルを有する。そして、ＮＡＮＤコントローラは、データの移動を行った場合は、データの移動元、および、データの移動先を示す物理アドレスを用いて、アドレス変換テーブルの更新を行う。【０００７】
例えば、従来技術として、以下のような技術がある。ＮＡＮＤコントローラは、物理アドレスを論理アドレスに逆変換するアドレス逆変換テーブルを用いて、データの移動元を示す物理アドレスを論理アドレスに逆変換する。そして、ＮＡＮＤコントローラは、アドレス変換テーブルに格納された物理アドレスのうち、逆変換された論理アドレスをインデックスとする物理アドレスを、データの移動先を示す物理アドレスに書き換える。【０００８】
また、フラッシュメモリへのアクセス速度を向上させるために、論理的に連続する複数のデータの書き込み先の記憶領域を特定して、複数のデータを分散して書き込む従来技術がある。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２００９−００３７８４号公報
【特許文献２】特開２００３−１５９４４号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した物理ブロックごとにデータを移動させるか否かを判定する技術では、データの移動元、および、データの移動先を示す物理アドレスを用いて、アドレス変換テーブルの更新を行う。かかる処理を行うため、例えば、ＮＡＮＤコントローラは、データの移動元を示す物理アドレスから論理アドレスに逆変換するアドレス逆変換テーブルを有するので、回路規模が増大するという問題がある。また、複数のデータを分散して書き込む従来技術を用いても、物理アドレスから論理アドレスへの変換については考慮されておらず、アドレス逆変換テーブルの使用を回避することは困難である。【００１１】
開示の技術は、上記に鑑みてなされたものであって、ＮＡＮＤコントローラの回路規模を抑えつつアクセス性能を向上させる情報処理装置、制御回路、制御プログラム、及び制御方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
本願の開示する情報処理装置、制御回路、制御プログラム、及び制御方法は、一つの態様において、記憶装置は、複数の記憶領域を有する。開始位置設定部は、前記記憶領域を複数含むブロック毎に、各ブロックに含まれる記憶領域を識別する物理アドレスに対応する論理アドレスのうち所定条件を満たす論理アドレスを検索開始位置として設定する。選択部は、前記論理アドレスと前記物理アドレスとの対応を表す変換テーブルの前記検索開始位置から論理アドレスを所定の順序で選択していく。取得部は、前記選択部が選択した論理アドレスに対応付けられた物理アドレスを前記変換テーブルから取得する。判定部は、所定の条件を用いて、前記取得部が取得した物理アドレスが示す記憶領域に格納されたデータを移動させるか否かを判定する。移動部は、前記判定部が、前記データを移動させると判定した場合は、前記取得部が取得した物理アドレスが示す記憶領域に格納されたデータを、他の記憶領域に移動させる。更新部は、前記変換テーブルに格納された物理アドレスのうち、前記選択部が選択した論理アドレスに対応付けられた物理アドレスを、前記他の記憶領域を示す物理アドレスに更新する。
【発明の効果】
【００１３】
本願の開示する情報処理装置、制御回路、制御プログラム、及び制御方法の一つの態様によれば、ＮＡＮＤコントローラの回路規模を抑えつつアクセス性能を向上させることができるという効果を奏する。
【図面の簡単な説明】
【００１４】
【図１】図１は、実施例１に係る情報処理装置の概略構成図である。
【図２】図２は、メモリアクセスの一例を説明するための図である。
【図３】図３は、実施例１に係るＮＡＮＤコントローラのブロック図である。
【図４】図４は、実施例１に係るアドレス変換テーブルの一例の図である。
【図５】図５は、実施例１に係る管理情報テーブルの一例の図である。
【図６】図６は、実施例１に係るＮＡＮＤコントローラが実行する処理の一例を説明するための図である。
【図７】図７は、実施例１に係るＮＡＮＤコントローラが実行する処理のフローチャートである。
【図８】図８は、実施例１に係る管理情報テーブルの最小論理アドレスの更新処理のフローチャートである。
【図９】図９は、実施例２に係る管理情報テーブルの一例の図である。
【図１０】図１０は、実施例２に係るＮＡＮＤコントローラが実行する処理のフローチャートである。
【図１１】図１１は、実施例２に係る管理情報テーブルの最大論理アドレスの更新処理のフローチャートである。
【図１２】図１２は、制御プログラムを実行するＮＡＮＤコントローラの一例の図である。
【発明を実施するための形態】
【００１５】
以下に、本願の開示する情報処理装置、制御回路、制御プログラム、及び制御方法の実施例を図面に基づいて詳細に説明する。なお、以下の実施例により本願の開示する情報処理装置、制御回路、制御プログラム、及び制御方法が限定されるものではない。
【実施例１】
【００１６】
図１は、実施例１に係る情報処理装置の概略構成図である。情報処理装置１は、複数のメモリ２ａ及び２ｂ、複数のＣＰＵ（Central  Processing  Unit）３ａ及び３ｂ、Ｉ／Ｏ（Input  Output）ハブ４、並びに、複数のＳＳＤ（Solid  State  Drive）５ａ及び５ｂを有する。また、ＳＳＤ５ａは、ＮＡＮＤコントローラ６ａ及び複数のＮＡＮＤデバイス７ａ〜１０ａを有する。【００１７】
また、ＳＳＤ５ｂは、ＮＡＮＤコントローラ６ｂ及び複数のＮＡＮＤデバイス７ｂ〜１０ｂを有する。なお、以下の説明では、ＳＳＤ５ｂ、ＮＡＮＤコントローラ６ｂ、及び複数のＮＡＮＤデバイス７ｂ〜１０ｂは、ＳＳＤ５ａ、ＮＡＮＤコントローラ６ａ、及び複数のＮＡＮＤデバイス７ａ〜１０ａと同様の機能を発揮するものとして、説明を省略する。【００１８】
各メモリ２ａ及び２ｂは、各ＣＰＵ３ａ及び３ｂが演算処理に用いるデータを記憶する記憶装置である。また、各ＣＰＵ３ａ及び３ｂは、メモリ２ａ及び２ｂが記憶するデータを用いて、各種演算処理を行う演算処理装置である。例えば、ＣＰＵ３ａ及び３ｂは、ＮＵＭＡ（Non-Uniform  Memory  Access）の技術を用いて、メモリ２ａ及び２ｂが記憶するデータを取得し、取得したデータを用いて演算処理を実行する。【００１９】
また、ＣＰＵ３ａ及び３ｂは、Ｉ／Ｏハブ４を介して、各ＳＳＤ５ａ及び５ｂが記憶するデータを取得し、取得したデータを用いて演算処理を実行する。詳細には、ＣＰＵ３ａは、ＳＳＤ５ａに対し、データの読出し要求や書込み要求を発行し、各ＮＡＮＤデバイス７ａ〜１０ａからデータの読出しや書込みを行う。例えば、ＣＰＵ３ａは、ＳＳＤ５ａに対し、読出し対象となるデータを指定する論理アドレスが格納された読出し要求を発行する。また、ＣＰＵ３ａは、データの書込み先を指定する論理アドレスと、書込み対象となるデータとが格納された書込み要求を発行する。【００２０】
ＮＡＮＤデバイス７ａは、各種データを記憶する不揮発性メモリである。詳細には、ＮＡＮＤデバイス７ａは、データの記憶領域である物理ページを複数有し、物理ページ単位でデータの書込みを行う。また、ＮＡＮＤデバイス７ａは、複数の物理ページを有する物理ブロックを複数有し、ブロック単位でデータの消去を行う。ここで、１つの物理ページは、例えば、８キロバイトの記憶容量を有し、１つの物理ブロックは、例えば、１２８の物理ページを有する。【００２１】
ＮＡＮＤコントローラ６ａは、各ＮＡＮＤデバイス７ａ〜１０ａに対してアクセスし、データの読出しや書込みを行う。例えば、ＮＡＮＤコントローラ６ａは、データが記憶された記憶領域を各ＣＰＵ３ａ及び３ｂが指定する際に用いる論理アドレスと、データが格納されたＮＡＮＤデバイス７ａ〜１０ａの記憶領域を示す物理アドレスとを対応付けたアドレス変換テーブルを有する。【００２２】
そして、ＮＡＮＤコントローラ６ａは、読出し要求とともに論理アドレスを受信すると、アドレス変換テーブルを用いて、論理アドレスと対応付けられた物理アドレスを識別し、識別した物理アドレスが示す記憶領域からデータの読出しを行う。その後、ＮＡＮＤコントローラ６ａは、Ｉ／Ｏハブ４を介して、読出したデータをＣＰＵ３ａに送信する。【００２３】
なお、以下の説明では、理解を容易にするため、各物理ページの先頭アドレスとなる論理アドレスを単に論理アドレスと記載し、各物理ページの先頭アドレスとなる物理アドレスを単に物理アドレスと記載する。また、情報処理装置１が実行するシステムは、各物理ページの先頭アドレスとなる論理アドレスに対する読出し要求や書込み要求を発行するものとする。【００２４】
例えば、ＮＡＮＤコントローラ６ａは、ＮＡＮＤデバイス７ａ〜１０ａが、複数のブロックを有し、各ブロックに２ｑ個の物理ページが含まれている場合は、以下の処理を行う。まず、ＮＡＮＤコントローラ６ａは、論理アドレスの下位ｑビットを論理的な１つのブロック内において、物理ページを識別するための論理ページ番号とし、残りの論理アドレスの上位ｐビットを論理的な１つのブロックを示す論理ブロックアドレスとする。【００２５】
また、ＮＡＮＤコントローラ６ａは、物理アドレスの上位ｐビットを物理的な１つのブロックを示す物理ブロックアドレスとし、物理アドレスの下位ｑビットを物理的な１つのブロック内において、各物理ページを識別するための物理ページ番号とする。つまり、ＮＡＮＤコントローラ６ａは、論理アドレスを、論理ブロックを示す論理ブロックアドレスと、論理ページを論理ブロックごとに示す論理ページ番号とに分割する。また、ＮＡＮＤコントローラ６ａは、物理アドレスを、物理ブロックを示す物理ブロックアドレスと、物理ページを物理ブロックごとに示す物理ページ番号とに分割する。【００２６】
以下、図２を用いて、ＮＡＮＤコントローラ６ａが実行するメモリアクセスの一例について説明する。図２は、メモリアクセスの一例を説明するための図である。なお、図２に示す例では、理解を容易にするため、ブロック数を「８」とし、各ブロック内の物理ページ数が「４」のＮＡＮＤデバイス７ａについて記載した。また、図２に示す例では、ＮＡＮＤコントローラ６ａが、論理ブロックアドレスと物理ブロックアドレスとを対応付けたアドレス変換テーブルを用いて、ＮＡＮＤデバイス７ａ〜１０ａが有する物理ページ単位でデータの書込みを行う処理について記載した。【００２７】
例えば、ＮＡＮＤコントローラ６ａは、図２中（ａ）に示すように、ＣＰＵ３ａが実行するファイルシステムから、論理ブロックアドレス「ＬＢ００」の論理ページ番号「３」、すなわち論理アドレス「Ｌ０００３」に書き込み要求を発行する。すると、ＮＡＮＤコントローラ６ａは、アドレス変換テーブルを用いて、論理アドレス「Ｌ０００３」に対応付けられた物理アドレス「Ｐ０４０３」を取得し、図２中（ｂ）に示すように、更新前のデータが格納されている物理ページを識別する。【００２８】
続いて、ＮＡＮＤコントローラ６ａは、図２中（ｃ）に示すように、物理アドレス「Ｐ０４０３」が示す物理ページのデータを読出し、読み出したデータを書込み対象のデータに更新し、更新後のデータを予備ブロックの空き物理ページに格納する。詳細な例を挙げると、ＮＡＮＤコントローラ６ａは、図２中（ｄ）に示すように、物理アドレス「Ｐ０８００」が示す物理ページに更新後のデータを格納する。その後、ＮＡＮＤコントローラ６ａは、図２中（ｅ）に示すように、論理アドレス「Ｌ０００３」と対応付けられていた物理アドレス「Ｐ０４０３」を「Ｐ０８００」に更新し、処理を終了する。【００２９】
ここで、ＮＡＮＤデバイス７ａ〜１０ａに格納されたデータに対し、物理ページ単位で書込みや移動を行う場合は、１つの物理ブロック内に有効なデータと無効なデータとが混在する場合がある。例えば、図２に示す例では、ＮＡＮＤコントローラ６ａは、論理アドレス「Ｌ０００３」が示すデータを更新する際、物理ブロックアドレス「Ｂ０４」が示す物理ブロック内のデータを無効化する。そして、ＮＡＮＤコントローラ６ａは、更新後のデータを物理ブロックアドレス「Ｂ０８」が示す物理ブロックに格納する。このため、物理ブロックアドレス「Ｂ０４」が示す物理ブロックには、有効なデータと無効なデータとが混在する。【００３０】
ここで、ＮＡＮＤデバイス７ａ〜１０ａは、無効なデータが格納された物理ページに対してデータの上書きを行うことができず、あらかじめデータを消去した予備ブロックにデータの書込みを行う。しかしながら、有効なデータと無効なデータとが混在する物理ブロックが増えると、新たにデータを書き込む予備ブロックを確保できなくなる。また、ＮＡＮＤデバイス７ａ〜１０ａは、データを保持するための素子を有する。かかる素子は、データの消去を行う際に劣化が進行し、劣化が進むと、電荷を適切に保持することができなくなる。【００３１】
そこで、従来のＮＡＮＤコントローラは、有効なデータを整理して新たな予備ブロックを確保するデータ移動制御を実行する。【００３２】
ここで、ＮＡＮＤコントローラ６ａは、ガベージコレクション処理などのデータ移動制御を実行した場合は、データの移動に応じて、アドレス変換テーブルの更新を行う。しかしながら、ＮＡＮＤコントローラ６ａは、管理情報テーブルのページバリッドなどを用いて、物理ブロック毎に、データを移動させるか否かを判定する。このため、ＮＡＮＤコントローラ６ａは、データ移動制御を行った後、データの移動元物理アドレスを識別できるが、データの移動元物理アドレスに対応する論理アドレスを識別できない。【００３３】
そこで、ＮＡＮＤコントローラ６ａに以下の処理を行わせることが考えられる。まず、ＮＡＮＤコントローラ６ａは、データの移動を行うブロックを特定する。そして、ＮＡＮＤコントローラ６ａは、アドレス変換テーブルを参照し、論理アドレスを１つ選択する。次に、ＮＡＮＤコントローラ６ａは、選択した論理アドレスと対応付けられた物理アドレスをアドレス変換テーブルから取得する。そして、ＮＡＮＤコントローラ６ａは、管理情報テーブルを用いて、取得した物理アドレスが示す物理ページを含む物理ブロックがデータの移動を行うブロックか否かを判定する。その後、ＮＡＮＤコントローラ６ａは、データの移動を行った場合は、アドレス変換テーブルに格納された物理アドレスのうち、選択した論理アドレスと対応付けられた物理アドレスを、移動先物理アドレスに更新する。ＮＡＮＤコントローラ６ａは、以上の処理を、アドレス変換テーブルの最初の論理アドレスから順に繰り返し行っていくことで、データの移動を行うブロックの全てのページのデータ移動を完了することができる。しかし、アドレス変換テーブルの最初の論理アドレスから順番にデータの移動判定を行う場合、最大で全ての論理アドレスに対して処理を行うことになり、データの移動処理に多大な時間が掛かってしまう。【００３４】
そこで、本実施例に係る情報処理装置は、ブロック毎に最小の論理アドレスを特定し、その最小の論理アドレスを該当ブロックの検索開始アドレスとすることで、データ移動の判定の処理数を減らしてデータ移動処理に係る時間を短縮し、アクセス性能の低下を防ぐ。この最小論理アドレスが、「検索開始位置」の一例にあたる。【００３５】
以下、図３を用いて、ＮＡＮＤコントローラ６ａについて説明する。図３は、実施例１に係るＮＡＮＤコントローラのブロック図である。図３に示す例では、ＮＡＮＤコントローラ６ａは、テーブル記憶部１１、リクエスタインターフェース部１２、リクエスト調停部１３、及びテーブル制御部１４を有する。また、ＮＡＮＤコントローラ６ａは、デバイスアクセス制御部１５、巡回参照制御部１６、及びデータ移動制御部１７を有する。また、テーブル記憶部１１は、アドレス変換テーブル１８及び管理情報テーブル１９を記憶する。【００３６】
まず、図４、図５を参照して、テーブル記憶部１１が記憶するアドレス変換テーブル１８と、管理情報テーブル１９に格納された情報について説明する。図４は、実施例１に係るアドレス変換テーブルの一例の図である。図４に示すように、アドレス変換テーブル１８には、論理アドレスと有効フラグと物理アドレスとが対応付けて格納されている。ここで、有効フラグとは、対応付けられた物理アドレスが示す物理ページに格納されたデータが有効なデータであるか否かを示すバリッドビットである。【００３７】
例えば、図４に示す例では、アドレス変換テーブル１８には、論理アドレス「Ｌ００００」と、有効フラグ「０」と、物理アドレス「Ｐ００１１」とが対応付けて格納されている。すなわち、アドレス変換テーブル１８は、物理アドレス「Ｐ００１１」が示すブロックに論理アドレス「Ｌ００００」が指定する有効なデータが格納されていない旨を示す。【００３８】
同様に、図４に示す例では、アドレス変換テーブル１８には、論理アドレス「Ｌ０００１」と、有効フラグ「０」と、物理アドレス「Ｐ００３２」とが対応付けて格納されている。また、アドレス変換テーブル１８には、論理アドレス「Ｌ０００２」と、有効フラグ「１」と、物理アドレス「Ｐ０００３」とが対応付けて格納されている。また、アドレス変換テーブル１８には、論理アドレス「Ｌ０００３」と、有効フラグ「１」と、物理ブロックアドレス「Ｐ０００１」とが対応付けて格納されている。すなわち、アドレス変換テーブル１８は、物理アドレス「Ｐ０００３」及び「Ｐ０００１」に格納されたデータが有効なデータである旨を示す。【００３９】
次に、図５を用いて、管理情報テーブル１９に格納される情報について説明する。図５は、実施例１に係る管理情報テーブルの一例の図である。図５に示すように、管理情報テーブル１９には、物理ブロックアドレス、有効ページ数、及び最小論理アドレスが対応付けて格納される。【００４０】
ここで、有効ページ数とは、対応付けられた物理ブロックアドレスが示す物理ブロックに含まれる有効なデータを有するページの数である。例えば、管理情報テーブル１９は、１つの物理ブロックに、ｎ個の有効ページが含まれる場合は、有効ページ数はｎとなる。【００４１】
また、最小論理アドレスとは、物理ブロックアドレスが示すブロックに含まれるページの各物理アドレスに対応する論理アドレスの中で最小のアドレスである。【００４２】
例えば、図５に示す例では、管理情報テーブル１９には、物理ブロックアドレス「Ｂ００」と、有効ページ数「１１」と、最小論理アドレス「Ｌ００１２」とが対応付けて格納される。すなわち、管理情報テーブル１９は、物理ブロックアドレス「Ｂ００」が示す物理ブロックに含まれる物理ページのうち、１１個のページが有効であることを示す。また、管理情報テーブル１９は、物理ブロックアドレス「Ｂ００」に対応する論理アドレスの中で、最小の論理アドレスが「Ｌ００１２」であることを示す。【００４３】
さらに、図５に示す例では、管理情報テーブル１９には、物理ブロックアドレス「Ｂ０１」には、有効ページがなく、最小論理アドレスも設定されていない。ここで、最小論理アドレスが設定されていない場合、本実施例では、論理アドレス全体の中で最も小さい論理アドレスである「Ｌ００００」を初期値として設定する。また、管理情報テーブル１９には、物理ブロックアドレス「Ｂ０２」と、有効ページ数「２３」と、最小論理アドレス「Ｌ００００」とが対応付けて格納される。また、管理情報テーブル１９には、物理ブロックアドレス「Ｂ０３」と、有効ページ数「４１」と、最小論理アドレス「Ｌ０１０３」とが対応付けて格納される。なお、管理情報テーブル１９には、他にも、物理ブロックアドレス、有効ページ数、及び最小論理アドレスが対応付けて格納されているものとする。【００４４】
図３に戻り、リクエスタインターフェース部１２は、ＣＰＵ３ａ及び３ｂからのＮＡＮＤデバイス７ａ〜１０ａに対するリクエストのインターフェースである。例えば、リクエスタインターフェース部１２は、論理アドレスを含む読出し要求をＣＰＵ３ａ又は３ｂからＩ／Ｏハブ４を介して受信する。その場合、リクエスタインターフェース部１２は、読出し要求をリクエスト調停部１３に出力する。また、リクエスタインターフェース部１２は、ＮＡＮＤデバイス７ａ〜１０ａから読出したデータをリクエスト調停部１３から受信すると、読出し要求の発行元となるＣＰＵ３ａ又は３ｂに対してデータを送信する。【００４５】
また、リクエスタインターフェース部１２は、ＮＡＮＤデバイス７ａ〜１０ａに対して書き込むデータ及び書込み対象となるデータの論理アドレスとを含む書込み要求をＣＰＵ３ａ及び３ｂから受信する。この場合、リクエスタインターフェース部１２は、受信した書込み要求をリクエスト調停部１３に出力する。また、リクエスタインターフェース部１２は、リクエスト調停部１３から、データ書込みが完了した旨の応答を受信すると、受信した応答を、書込み要求の発行元となるＣＰＵ３ａ又は３ｂに対して、応答を送信する。【００４６】
リクエスト調停部１３は、リクエスタインターフェース部１２、データ移動制御部１７、巡回参照制御部１６が発行する各種リクエストの調停を行う。詳細には、リクエスト調停部１３は、読出し要求又は書込み要求をリクエスタインターフェース部１２から受信する。また、リクエスト調停部１３は、ＮＡＮＤデバイス７ａ〜１０ａが記憶するデータを、現在記憶するブロックから他のブロックに移動するよう要求する移動要求をデータ移動制御部１７から受信する。また、リクエスト調停部１３は、物理ブロック内のデータを消去するよう要求する消去要求をデータ移動制御部１７から受信する。また、リクエスト調停部１３は、管理情報テーブル１９の参照を要求するテーブル参照要求を巡回参照制御部１６から受信する。【００４７】
そして、リクエスト調停部１３は、リクエスタインターフェース部１２、データ移動制御部１７及び巡回参照制御部１６から受信する読出し要求、書込み要求、移動要求、消去要求及びテーブル参照要求の調停を行う。例えば、リクエスト調停部１３は、ＣＰＵ３ａ及び３ｂからＮＡＮＤデバイス７ａ〜１０ａに対するデータの読出しや書込みが阻害されないよう、リクエスタインターフェース部１２が発行する読出し要求及び書込み要求を最優先で実行する。また、例えば、リクエスト調停部１３は、移動要求を消去要求及びテーブル参照要求よりも優先して実行し、消去要求をテーブル参照要求よりも優先して実行する。なお、リクエスト調停部１３が各要求を調停するルールについては、上述した処理に限定されるものではなく、任意のルールを適用してよい。【００４８】
以下、リクエスト調停部１３が読出し要求、書込み要求、移動要求、消去要求及びテーブル参照要求を受信した際に実行する処理の一例を説明する。例えば、リクエスト調停部１３は、読出し要求を受信すると、読出し要求に含まれる論理アドレスをテーブル制御部１４に出力する。そして、リクエスト調停部１３は、読出し対象となる物理アドレスをテーブル制御部１４から受信すると、受信した物理アドレスを格納した読出し要求をデバイスアクセス制御部１５へ発行する。その後、リクエスト調停部１３は、読出し対象となるデータをデバイスアクセス制御部１５から受信すると、受信したデータをリクエスタインターフェース部１２へ出力する。【００４９】
また、リクエスト調停部１３は、書込み要求を受信すると、書込み要求に含まれる論理アドレスをテーブル制御部１４に出力する。この結果、リクエスト調停部１３は、書込み対象のデータが新たなデータである場合は、データが格納されていない予備ブロックのうち、データの書込み先となるページの物理アドレスをテーブル制御部１４から受信する。【００５０】
その後、リクエスト調停部１３は、テーブル制御部１４から受信した物理アドレスと、書込み対象のデータとを含む書込み要求とをデバイスアクセス制御部１５へ発行する。また、リクエスト調停部１３は、デバイスアクセス制御部１５からデータの書込みが完了した旨の応答を受信すると、データの書込み先となるページの物理アドレス及び書込み要求に含まれる論理アドレスを含むテーブル更新要求をテーブル制御部１４へ出力する。そして、リクエスト調停部１３は、テーブルの更新が終了した旨の応答をテーブル制御部１４から受信した場合は、書込み要求に対する応答をリクエスタインターフェース部１２へ出力する。【００５１】
また、リクエスト調停部１３は、書込みがデータの更新を目的とする場合は、更新元のデータが格納されたページの物理アドレスを更新元物理アドレスとしてテーブル制御部１４から受信する。また、リクエスト調停部１３は、予備ブロックに含まれるページの物理アドレス、すなわちデータの書込み先となるページの物理アドレスを更新先物理アドレスとしてテーブル制御部１４から受信する。【００５２】
そして、リクエスト調停部１３は、更新元物理アドレス及び更新先物理アドレスをテーブル制御部１４から受信した場合は、データの更新を要求する更新要求をデバイスアクセス制御部１５へ発行する。詳細には、リクエスト調停部１３は、更新元物理アドレス、更新先物理アドレス、及び書き込むデータを含む更新要求をデバイスアクセス制御部１５へ発行する。【００５３】
また、リクエスト調停部１３は、データの書込みが完了した旨の応答をデバイスアクセス制御部１５から受信すると、更新元物理アドレス、更新先物理アドレス、及び書込み要求に含まれる論理アドレスを含むテーブル更新要求をテーブル制御部１４へ出力する。その後、リクエスト調停部１３は、テーブル更新要求に対する応答をテーブル制御部１４から受信すると、データの書込みが完了した旨の応答をリクエスタインターフェース部１２へ出力する。【００５４】
また、リクエスト調停部１３は、移動させるデータが格納された物理ページの物理アドレスである移動元物理アドレス及び移動させるデータを指定するための論理アドレスを含む移動要求をデータ移動制御部１７などから受信する。また、リクエスト調停部１３は、テーブル制御部１４への問い合わせなどを行い、データの移動先となる物理ページの物理アドレスを移動先物理アドレスとして取得する。【００５５】
そして、リクエスト調停部１３は、移動元物理アドレス及び移動先物理アドレスを含む移動要求をデバイスアクセス制御部１５に発行する。また、リクエスト調停部１３は、データの移動が完了した旨の応答をデバイスアクセス制御部１５から受信する。そして、リクエスト調停部１３は、データ移動制御部１７から受信した移動対象のデータを指定する論理アドレス、移動先物理アドレス、及び移動元物理アドレスを含むテーブル更新要求をテーブル制御部１４へ出力する。その後、リクエスト調停部１３は、テーブル更新要求に対する応答をテーブル制御部１４から受信した場合は、データの移動が完了した旨の応答をデータ移動制御部１７へ出力する。【００５６】
また、リクエスト調停部１３は、データの消去対象となる物理ブロックを示す物理ブロックアドレスを含む消去要求をデータ移動制御部１７などから受信する。リクエスト調停部１３は、消去要求を受信すると、受信した消去要求をデバイスアクセス制御部１５へ発行する。そして、リクエスト調停部１３は、データの消去が完了した旨の応答をデバイスアクセス制御部１５から受信すると、消去要求に格納された物理ブロックアドレスを含むテーブル更新要求をテーブル制御部１４へ出力する。そして、リクエスト調停部１３は、データの更新が終了した旨の応答をテーブル制御部１４から受信した場合は、データの消去が完了した旨の応答をデータ移動制御部１７へ出力する。【００５７】
また、リクエスト調停部１３は、テーブル参照要求を巡回参照制御部１６から受信した場合は、アドレス変換テーブル１８と管理情報テーブル１９の参照要求をテーブル制御部１４へ送信する。そして、リクエスト調停部１３は、アドレス変換テーブル１８及び管理情報テーブル１９をテーブル制御部１４から受信すると、受信したアドレス変換テーブル１８及び管理情報テーブル１９を巡回参照制御部１６に出力する。【００５８】
テーブル制御部１４は、論理アドレスを物理アドレスに変換する。例えば、テーブル制御部１４は、読出し要求に格納された論理アドレスをリクエスト調停部１３から受信すると、受信した論理アドレスと対応付けられた物理アドレスをアドレス変換テーブル１８から取得する。そして、テーブル制御部１４は、取得した物理アドレスをリクエスト調停部１３へ出力する。【００５９】
また、テーブル制御部１４は、書込み要求に格納された論理アドレスをリクエスト調停部１３から受信すると、アドレス変換テーブル１８を参照し、受信した論理アドレスに有効フラグ「１」が対応付けられているか判定する。そして、テーブル制御部１４は、受信した論理アドレスに有効フラグ「０」が対応付けられている場合、すなわち、書込み対象のデータが新たなデータである場合は、以下の処理を実行する。【００６０】
まず、テーブル制御部１４は、管理情報テーブル１９を参照し、データが格納されていない物理ブロック、すなわち、予備ブロックを識別する。例えば、テーブル制御部１４は、管理情報テーブル１９を参照し、対応付けられた有効ページ数がすべて「０」である物理ブロックを検索し、検出した物理ブロックを予備ブロックとする。そして、テーブル制御部１４は、予備ブロックに含まれる物理ページの物理アドレスをリクエスト調停部１３へ出力する。【００６１】
なお、テーブル制御部１４は、一度予備ブロックを識別すると、識別した予備ブロックに含まれる物理ページの全ての物理ページにデータが書込まれるまで、同一の予備ブロックに含まれる物理ページの物理アドレスを出力する。詳細には、テーブル制御部１４は、予備ブロックに含まれる物理ページのうち、データが書込まれていない物理ページの物理アドレスを、物理ページ番号の順に出力する。そして、テーブル制御部１４は、予備ブロックに含まれる全ての物理ページにデータが書込まれた場合は、管理情報テーブル１９を参照して、新たな予備ブロックを識別する。【００６２】
一方、テーブル制御部１４は、受信した論理アドレスに有効フラグ「１」が対応付けられている場合、すなわち、書込みがデータの更新を目的とする場合は、以下の処理を実行する。まず、テーブル制御部１４は、受信した論理アドレスと対応付けられた物理アドレスを更新元物理アドレスとしてリクエスト調停部１３へ出力する。また、テーブル制御部１４は、予備ブロックを識別し、識別した予備ブロックに含まれる物理ページのうち、データが格納されていない物理ページの物理アドレスを更新先物理アドレスとしてリクエスト調停部１３へ出力する。【００６３】
また、テーブル制御部１４は、リクエスト調停部１３が移動要求を受信した際には、移動先物理アドレスの問い合わせをリクエスト調停部１３から受ける。この場合、テーブル制御部１４は、予備ブロックを識別し、識別した予備ブロックに含まれる物理ページのうち、データが格納されていない物理ページの物理アドレスを移動先物理アドレスとしてリクエスト調停部１３へ出力する。【００６４】
また、テーブル制御部１４は、データの書込み、移動、又は消去に応じて、アドレス変換テーブル１８及び管理情報テーブル１９の更新を行う。例えば、テーブル制御部１４は、リクエスト調停部１３が新たなデータの書込みを行う場合は、データの書込み先となる物理ページの物理アドレス及び書込み要求に含まれる論理アドレスを含むテーブル更新要求を受信する。【００６５】
この場合、テーブル制御部１４は、データの書込み先となる物理ページの物理アドレス及び論理アドレスをテーブル更新要求から抽出する。そして、テーブル制御部１４は、アドレス変換テーブル１８における抽出した論理アドレスと対応付けられた有効フラグを「１」に更新する。また、テーブル制御部１４は、抽出した論理アドレスに対応付けて、抽出した物理アドレスをアドレス変換テーブル１８に格納する。【００６６】
また、テーブル制御部１４は、抽出した物理アドレスが示す物理ブロックアドレスに対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ増やす。また、テーブル制御部１４は、抽出したエントリの最小論理アドレスを管理情報テーブル１９から取得する。そして、テーブル制御部１４は、書き込むデータの論理アドレスが取得した最小論理アドレスより小さいか否かを判定する。書き込むデータの論理アドレスが取得した最小論理アドレスより小さい場合、テーブル制御部１４は、書き込むデータの論理アドレスを抽出したエントリの最小論理アドレスに書き込む。その後、テーブル制御部１４は、テーブル更新要求に対する応答をリクエスト調停部１３に出力する。【００６７】
また、テーブル制御部１４は、リクエスト調停部１３がデータの更新を行う場合は、更新元物理アドレス、更新先物理アドレス及び書込み要求に含まれる論理アドレスを含むテーブル更新要求をリクエスト調停部１３から受信する。この場合、テーブル制御部１４は、テーブル更新要求から更新元物理アドレス、更新先物理アドレス、及び論理アドレスを抽出する。そして、テーブル制御部１４は、アドレス変換テーブル１８における抽出した論理アドレスと対応付けられた物理アドレスを抽出した更新先物理アドレスに更新する。【００６８】
また、テーブル制御部１４は、更新元物理アドレスに対応する物理ブロックアドレスと対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ減らす。【００６９】
次に、テーブル制御部１４は、更新先物理ブロックアドレスと対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ増やす。また、テーブル制御部１４は、抽出したエントリの最小論理アドレスを管理情報テーブル１９から取得する。そして、テーブル制御部１４は、更新するデータの論理アドレスが取得した最小論理アドレスより小さいか否かを判定する。更新するデータの論理アドレスが取得した最小論理アドレスより小さい場合、テーブル制御部１４は、更新するデータの論理アドレスを抽出したエントリの最小論理アドレスに書き込む。その後、テーブル制御部１４は、テーブル更新要求に対する応答をリクエスト調停部１３に出力する。【００７０】
また、テーブル制御部１４は、リクエスト調停部１３がデータの移動を行う場合は、移動元物理アドレス、移動先物理アドレス、及び移動対象のデータを指定する論理アドレスを含むテーブル更新要求を受信する。この場合、テーブル制御部１４は、テーブル更新要求から移動元物理アドレス、移動先物理アドレス、及び論理アドレスを抽出する。そして、テーブル制御部１４は、アドレス変換テーブル１８を参照し、抽出した論理アドレスと対応付けられた物理アドレスを抽出した移動先物理アドレスに更新する。【００７１】
また、テーブル制御部１４は、移動元物理アドレスに対応する物理ブロックアドレスと対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ減らす。【００７２】
次に、テーブル制御部１４は、移動先物理ブロックアドレスと対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ増やす。また、テーブル制御部１４は、抽出したエントリの最小論理アドレスを管理情報テーブル１９から取得する。そして、テーブル制御部１４は、移動するデータの論理アドレスが取得した最小論理アドレスより小さいか否かを判定する。移動するデータの論理アドレスが取得した最小論理アドレスより小さい場合、テーブル制御部１４は、移動するデータの論理アドレスを抽出したエントリの最小論理アドレスに書き込む。その後、テーブル制御部１４は、テーブル更新要求に対する応答をリクエスト調停部１３に出力する。【００７３】
また、テーブル制御部１４は、リクエスト調停部１３がデータの消去を行う場合は、消去要求に格納された物理ブロックアドレスを含むテーブル更新要求をリクエスト調停部１３から受信する。そして、テーブル制御部１４は、指定された物理ブロックアドレスに対応するエントリの最小論理アドレスを初期値に設定する。その後、テーブル制御部１４は、テーブル更新要求に対する応答をリクエスト調停部１３に出力する。【００７４】
また、テーブル制御部１４は、テーブル参照要求を受信した場合は、テーブル記憶部１１からアドレス変換テーブル１８と管理情報テーブル１９とを取得する。そして、テーブル制御部１４は、取得した管理情報テーブル１９をリクエスト調停部１３に出力する。なお、テーブル制御部１４は、例えば、情報処理装置１が実行するシステムから、論理アドレスとデータとの対応付けを解消する旨の指示を受けると、アドレス変換テーブル１８における対象となる論理アドレスと対応付けられた有効フラグを「０」に更新する。【００７５】
デバイスアクセス制御部１５は、リクエスト調停部１３からの各種リクエストに従って、ＮＡＮＤデバイス７ａ〜１０ａに対するデバイスアクセスを実行する。例えば、デバイスアクセス制御部１５は、物理アドレスを含む読出し要求をリクエスト調停部１３から受信する。この場合、デバイスアクセス制御部１５は、ＮＡＮＤデバイス７ａ〜１０ａが有するページのうち、読出し要求に格納されていた物理アドレスが示すページに格納されたデータの読み出しを実行する。そして、デバイスアクセス制御部１５は、読み出したデータをリクエスト調停部１３へ出力する。【００７６】
また、例えば、デバイスアクセス制御部１５は、物理アドレス及び書込み対象のデータを含む書込み要求をリクエスト調停部１３から受信する。この場合、デバイスアクセス制御部１５は、書込み要求に含まれる物理アドレスが示す物理ページに書込み対象のデータを格納する。その後、デバイスアクセス制御部１５は、データの書込みを終了した旨の応答をリクエスト調停部１３へ出力する。【００７７】
また、例えば、デバイスアクセス制御部１５は、更新元物理アドレス、更新先物理アドレス、及び書き込むデータを含む更新要求をリクエスト調停部１３から受信する。この場合、デバイスアクセス制御部１５は、更新元物理アドレスが示す物理ページのデータを読み出す。続いて、デバイスアクセス制御部１５は、読み出したデータを更新要求に含まれるデータに更新する。そして、デバイスアクセス制御部１５は、更新したデータを更新先物理アドレスが示す物理ページに格納する。その後、デバイスアクセス制御部１５は、データの書込みを終了した旨の応答をリクエスト調停部１３へ出力する。【００７８】
また、デバイスアクセス制御部１５は、移動元物理アドレス及び移動先物理アドレスを含む移動要求をリクエスト調停部１３から受信する。この場合、デバイスアクセス制御部１５は、移動元物理アドレスが示す物理ページからデータを読出し、読出したデータを移動先物理アドレスが示す物理ページに格納する。その後、デバイスアクセス制御部１５は、データの移動を終了した旨の応答をリクエスト調停部１３へ出力する。【００７９】
また、デバイスアクセス制御部１５は、データの消去対象となる物理ブロックを示す物理ブロックアドレスを含む消去要求をリクエスト調停部１３から受信する。この場合、デバイスアクセス制御部１５は、消去要求に含まれる物理ブロックアドレスが示す物理ブロックに格納されたデータを消去し、データの消去が完了した旨の応答をリクエスト調停部１３へ出力する。【００８０】
巡回参照制御部１６は、所定のタイミングで、巡回参照制御を実行する。例えば、巡回参照制御部１６は、所定の時間間隔、所定の時刻、又は情報処理装置１が実行するアプリケーションプログラムの指示などを契機として、巡回参照制御を実行する。【００８１】
以下、巡回参照制御部１６が実行する巡回参照制御の処理内容について説明する。巡回参照制御部１６は、論理アドレス選択部１６１、物理アドレス取得部１６２、及び判定部１６３を有している。【００８２】
論理アドレス選択部１６１は、アドレス変換テーブル１８及び管理情報テーブル１９の参照要求をリクエスト調停部１３へ出力する。そして、論理アドレス選択部１６１は、リクエスト調停部１３からアドレス変換テーブル１８及び管理情報テーブル１９を受信する。【００８３】
次に、論理アドレス選択部１６１は、管理情報テーブル１９から有効ページ数が閾値よりも小さい物理ブロックを１つ特定する。次に、論理アドレス選択部１６１は、特定した物理ブロックにおける最小論理アドレスを取得する。そして、論理アドレス選択部１６１は、最小論理アドレスに検索ポインタを設定する。その後、論理アドレス選択部１６１は、最小論理アドレスを物理アドレス取得部１６２へ出力する。【００８４】
その後、論理アドレス選択部１６１は、次の論理アドレスの選択の指示を判定部１６３から受けると、検索ポインタを１つ増加させて、次に大きいアドレスを有する論理アドレスを移動判定処理の対象として新たに選択する。そして、論理アドレス選択部１６１は、選択した論理アドレスを物理アドレス取得部１６２へ出力する。すなわち、論理アドレス選択部１６１は、最小論理アドレスを検索開始アドレスとしてアドレスが大きくなる順に論理アドレスを１つずつ選択していく。【００８５】
物理アドレス取得部１６２は、論理アドレスを論理アドレス選択部１６１から取得する。そして、物理アドレス取得部１６２は、アドレス変換テーブル１８を参照し、選択した論理アドレスと対応付けられた物理アドレスを取得する。そして、物理アドレス取得部１６２は、取得した物理アドレスを判定部１６３へ出力する。【００８６】
判定部１６３は、物理アドレスを物理アドレス取得部１６２から取得する。そして、判定部１６３は、取得した物理アドレスで示されるページが特定した物理ブロックに含まれているか否かを判定する。【００８７】
取得した物理アドレスが特定した物理ブロックの物理ブロックアドレスに含まれていない場合、判定部１６３は次の論理アドレスの選択を論理アドレス選択部１６１に指示する。【００８８】
これに対して、取得した物理アドレスを有するページが特定した物理ブロックに含まれている場合、判定部１６３は、取得した物理アドレスに対応するアドレス変換テーブル１８の有効フラグが「１」であるか否かを確認する。判定部１６３は、有効フラグが「０」の場合、次の論理アドレスの選択を論理アドレス選択部に指示する。【００８９】
これに対して、判定部１６３は、有効フラグが「１」の場合、取得した物理アドレス及び選択した論理アドレスの組をデータ移動制御部１７へ出力する。そして、判定部１６３は、データ移動が完了すると、取得した物理ブロックに未だ有効ページがあるか否かを判定する。例えば、判定部１６３は、データの移動を行った際に、管理情報テーブル１９における取得した物理ブロックの有効ページ数から１をデクリメントしていき、有効ページ数が０になった場合に、有効ページがなくなったと判定する。【００９０】
有効ページが未だある場合、判定部１６３は、次の論理アドレスの選択を論理アドレス選択部に指示する。【００９１】
有効ページがなくなった、すなわち、データの移動により物理ブロックが空になったと判定した場合、判定部１６３は、取得した物理アドレス、選択した論理アドレス、及びブロックが空になる旨を示すラストフラグの組をデータ移動制御部１７へ出力する。【００９２】
巡回参照制御部１６は、選択した物理ブロックにおけるデータの移動及びブロックの消去を行い空き容量を作成した後、予め決められた閾値以上の空き容量が確保できたか否かを判定する。閾値以上の空き容量が確保できていない場合、巡回参照制御部１６は、新たに物理ブロックを選択して以上の処理を繰り返す。予め決められた閾値以上の空き容量が確保できた場合、巡回参照制御部１６は、ガベージコレクションの処理を終了する。【００９３】
データ移動制御部１７は、データの移動を行う。具体的には、データ移動制御部１７は、巡回参照制御部１６から、論理アドレス及び物理アドレスの組、又は、論理アドレス、物理アドレス、及びラストフラグとの組を受信する。【００９４】
データ移動制御部１７は、論理アドレス及び物理アドレスの組を巡回参照制御部１６の判定部１６３から受信した場合、受信した組に含まれる物理アドレスを移動元物理アドレスとする。そして、データ移動制御部１７は、移動元物理アドレスと、受信した組に含まれる論理アドレスとを含む移動要求をリクエスト調停部１３へ出力する。その後、データ移動制御部１７は、データの移動が完了した旨の応答をリクエスト調停部１３から受信すると、受信した組に含まれる物理アドレスが示す物理ページのデータ移動処理を終了する。【００９５】
一方、データ移動制御部１７は、論理アドレス、物理アドレス、及びラストフラグの組を巡回参照制御部１６の判定部１６３から受信した場合、受信した組に含まれる物理アドレスを移動元物理アドレスとする。そして、データ移動制御部１７は、移動元物理アドレス及び受信した組に含まれる論理アドレスを含む移動要求をリクエスト調停部１３へ出力する。その後、データ移動制御部１７は、データの移動が完了した旨の応答を受信すると、受信した組に含まれる物理ブロックアドレスを含む消去要求をリクエスト調停部１３へ出力する。そして、データ移動制御部１７は、データの消去が完了した旨の応答をリクエスト調停部１３から受信すると、受信した組に含まれる物理アドレスが示す物理ページのデータ移動処理を終了する。【００９６】
例えば、データ移動制御部１７は、論理アドレス「Ｌ０００１」と、物理アドレス「Ｐ００３２」と、ラストフラグとの組を巡回参照制御部１６の判定部１６３から受信する。かかる場合は、データ移動制御部１７は、移動元物理アドレス「Ｐ００３２」と、論理アドレス「Ｌ０００１」とを含む移動要求をリクエスト調停部１３に出力する。そして、データ移動制御部１７は、データの移動が完了した旨の応答を受信した場合は、物理アドレス「Ｐ００３２」を含む物理ブロックアドレスの消去要求をリクエスト調停部１３に出力する。この結果、ＮＡＮＤコントローラ６ａは、物理アドレス「Ｐ００３２」を含む物理ブロックアドレスが示す物理ブロックのデータを消去し、新たな予備ブロックとする。【００９７】
なお、例えば、リクエスタインターフェース部１２、リクエスト調停部１３、テーブル制御部１４、デバイスアクセス制御部１５、巡回参照制御部１６、データ移動制御部１７とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路、またはＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などを適用する。【００９８】
また、テーブル記憶部１１とは、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（flash  memory）などの半導体メモリ素子などの記憶装置である。【００９９】
次に、図６を参照して、本実施例に係るＮＡＮＤコントローラ６ａが実行する処理をまとめて説明する。図６は、実施例１に係るＮＡＮＤコントローラが実行する処理の一例を説明するための図である。【０１００】
例えば、ＮＡＮＤコントローラ６ａは、図６中（Ａ）に示すように、管理情報テーブル１９を参照し、有効ページ数が閾値以下の物理ブロックを選択する。次に、ＮＡＮＤコントローラ６ａは、選択した物理ブロックの検索開始アドレスを管理情報テーブル１９から取得する。【０１０１】
次に、ＮＡＮＤコントローラ６ａは、図６中（Ｂ）に示すように、検索開始アドレスから順番に論理アドレスを取得し、取得した論理アドレスと対応付けられた物理アドレスをアドレス変換テーブル１８から取得する。そして、ＮＡＮＤコントローラ６ａは、取得した物理アドレスから物理ブロックアドレスを特定する。そして、ＮＡＮＤコントローラ６ａは、図６中（Ｃ）に示すように、管理情報テーブル１９を参照し、特定した物理ブロックアドレスが選択した物理ブロックのアドレスに含まれているか否かを判定する。ＮＡＮＤコントローラ６ａは、特定した物理ブロックアドレスが選択した物理ブロックのアドレスに含まれている場合、その物理ブロックに格納されているデータを移動させると判定する。【０１０２】
そして、ＮＡＮＤコントローラ６ａは、物理ブロックのデータを移動させると判定した場合は、図６中（Ｄ）に示すように、データ移動制御を実行する。具体的には、ＮＡＮＤコントローラ６ａは、アドレス変換テーブル１８の有効フラグを用いて、有効なデータが格納された物理ページを特定し、特定した物理ページを示す物理アドレスを移動元物理アドレスとする。また、ＮＡＮＤコントローラ６ａは、管理情報テーブル１９から予備ブロックの物理アドレスを移動先物理アドレスとして取得する。そして、ＮＡＮＤコントローラ６ａは、選択した論理アドレス、移動元物理アドレス、および、移動先物理アドレスを用いて、データ移動制御を実行する。【０１０３】
詳細には、ＮＡＮＤコントローラ６ａは、図６中（Ｅ）に示すように、移動元物理アドレスと移動先物理アドレスとを用いて、データの移動に係るデバイスアクセス制御を実行する。この結果、ＮＡＮＤコントローラ６ａは、図６中（Ｆ）に示すように、移動元物理アドレスが示す物理ページに格納されたデータを、移動先物理アドレスが示す物理ページに移動させる。そして、ＮＡＮＤコントローラ６ａは、図６中（Ｇ）及び（Ｈ）に示すように、データの移動に係る応答を受信する。【０１０４】
すると、ＮＡＮＤコントローラ６ａは、図６中（Ｉ）に示すように、データの移動に応じて、管理情報テーブル１９の更新を行う。また、ＮＡＮＤコントローラ６ａは、図６中（Ｊ）に示すように、アドレス変換テーブル１８が記憶する物理アドレスのうち、選択した論理アドレスと対応付けられた物理アドレスを移動先物理アドレスに更新する。【０１０５】
すなわち、ＮＡＮＤコントローラ６ａは、物理ブロック毎にデータを移動させるか判定するのではなく、論理アドレス毎にデータを移動させるか否かを判定する。このため、ＮＡＮＤコントローラ６ａは、移動元物理アドレスを論理アドレスに変換するアドレス逆変換テーブルを有さずとも、アドレス変換テーブル１８の更新を行うことができる。この結果、ＮＡＮＤコントローラ６ａは、回路規模を縮小することができる。また、検索開始位置より大きい論理アドレスに対してのみ、データの移動判定を行うので、ＮＡＮＤコントローラ６ａは、データの移動判定の処理の時間を短縮できる。【０１０６】
次に、図７を参照して、ＮＡＮＤコントローラ６ａが実行する処理の流れについて説明する。図７は、実施例１に係るＮＡＮＤコントローラが実行する処理のフローチャートである。ＮＡＮＤコントローラ６ａは、所定の時間が経過した場合や、ソフトウェアからの指示を受けた場合は、図７に示すデータ移動制御を実行する。【０１０７】
巡回参照制御部１６の論理ブロック選択部１６１は、物理ブロックを一つ選択し、管理情報テーブル１９における選択した物理ブロックの有効ページ数を検索する（ステップＳ１０１）。【０１０８】
そして、巡回参照制御部１６の論理ブロック選択部１６１は、選択した物理ブロックの有効ページ数が閾値未満か否を判定する（ステップＳ１０２）。有効ページ数が閾値以上の場合（ステップＳ１０２：否定）、巡回参照制御部１６は、ステップＳ１０１へ戻る。【０１０９】
これに対して、有効ページ数が閾値未満の場合（ステップＳ１０２：肯定）、巡回参照制御部１６の論理ブロック選択部１６１は、選択した物理ブロックの最小論理アドレスを管理情報テーブル１９から取得する。そして、巡回参照制御部１６の論理ブロック選択部１６１は、取得した最小論理アドレスに検索ポインタをセットする（ステップＳ１０３）。【０１１０】
次に、巡回参照制御部１６の物理ブロック取得部１６２は、検索ポインタが示す論理アドレスに対応する物理アドレスをアドレス変換テーブル１８から取得して、取得した物理アドレスを移動判定対象の物理アドレスとする（ステップＳ１０４）。【０１１１】
次に、巡回参照制御部１６の判定部１６３は、移動判定対象の物理アドレスを有するページが選択した物理ブロックに含まれているか否かを判定する（ステップＳ１０５）。選択した物理ブロックに含まれていない場合（ステップＳ１０５：否定）、巡回参照制御部１６の論理ブロック選択部１６１は、検索ポインタを１つインクリメントして検索ポインタを更新する（ステップＳ１０９）。【０１１２】
一方、選択した物理ブロックに含まれる場合（ステップＳ１０５：肯定）、巡回参照制御部１６の判定部１６３は、移動判定対象の物理アドレスを有するページに有効データが格納されているか否かをアドレス変換テーブル１８から判定する（ステップＳ１０６）。有効データが格納されていない場合（ステップＳ１０６：否定）、巡回参照制御部１６の判定部１６３は、検索ポインタを１つインクリメントして検索ポインタを更新し（ステップＳ１０９）、ステップＳ１０４へ戻る。【０１１３】
これに対して、有効データが格納されている場合（ステップＳ１０６：肯定）、巡回参照制御部１６の判定部１６３は、取得した物理アドレスを移動対象の物理アドレスとする。そして、巡回参照制御部１６の判定部１６３は、移動対象の物理アドレス及びそれに対応する論理アドレスの組をデータ移動制御部１７へ出力する。データ移動制御部１７は、データの移動要求をリクエスト調停部１３へ出力し、移動対象の物理アドレスからデータを移動さる。また、テーブル制御部１４は、アドレス変換テーブル１８の論理アドレスに関連付けられた物理アドレスを変更し、アドレス変換テーブル１８を更新する。さらに、巡回参照制御部１６の判定部１６３は、管理情報テーブル１９における選択した物理ブロックの有効ページ数を１つ減らして、管理情報テーブル１９を更新する（ステップＳ１０７）。【０１１４】
次に、巡回参照制御部１６の判定部１６３は、選択した物理ブロックの有効ページ数が０になったか否かを判定する（ステップＳ１０８）。有効ページ数が０でない場合（ステップＳ１０８：否定）、巡回参照制御部１６の論理ブロック選択部１６１は、検索ポインタを１つインクリメントして検索ポインタを更新する（ステップＳ１０９）。【０１１５】
これに対して、有効ページ数が０の場合（ステップＳ１０８：肯定）、巡回参照制御部１６の判定部１６３は、ラストフラグをデータ移動制御部１７へ出力する。データ移動制御部１７は、移動対象の物理アドレスを含む物理ブロックの消去命令をリクエスト調停部１３へ送信し、その物理ブロックを消去させる。また、巡回参照制御部１６は、管理情報テーブル１９における選択した物理ブロックに対応する最小論理アドレスを初期値に設定して管理情報テーブル１９を更新する（ステップＳ１１０）。【０１１６】
その後、巡回参照制御部１６は、空き容量が閾値以下か否かを判定する（ステップＳ１１１）。空き容量が閾値以下の場合（ステップＳ１１１：肯定）、巡回参照制御部１６は、ステップＳ１０１へ戻る。これに対して、空き容量が閾値より大きい場合（ステップＳ１１１：否定）、ＮＡＮＤコントローラ６ａは、データの移動制御の処理を終了する。【０１１７】
次に、図８を参照して、本実施例に係る管理情報テーブル１９の最小論理アドレスの更新処理について説明する。図８は、実施例１に係る管理情報テーブルの最小論理アドレスの更新処理のフローチャートである。【０１１８】
テーブル制御部１４は、リクエスト調停部１３が書き込み命令をリクエスタインターフェース部１２から受信したか否かを判定する（ステップＳ２０１）。書き込み命令を受信していない場合（ステップＳ２０１：否定）、テーブル制御部１４は、最小論理アドレスの更新処理を終了する。【０１１９】
これに対して、書き込み命令を受信した場合（ステップＳ２０１：肯定）、テーブル制御部１４は、書き込み命令でデータの格納先として指定された物理アドレスを含む物理ブロックを管理情報テーブル１９から検索する（ステップＳ２０２）。【０１２０】
次に、テーブル制御部１４は、検索した物理ブロックの最小論理アドレスを管理情報テーブル１９から取得する（ステップＳ２０３）。【０１２１】
そして、テーブル制御部１４は、データの格納先の論理アドレスが取得した最小論理アドレス未満か否かを判定する（ステップＳ２０４）。データの格納先の論理アドレスが取得した最小論理アドレス以上の場合（ステップＳ２０４：否定）、テーブル制御部１４は、最小論理アドレスの更新処理を終了する。【０１２２】
これに対して、データの格納先の論理アドレスが取得した最小論理アドレス未満の場合（ステップＳ２０４：肯定）、テーブル制御部１４は、検索した物理ブロックの最小論理アドレスをデータの格納先の論理アドレスに更新する（ステップＳ２０５）。【０１２３】
以上に説明したように、本実施例に係る情報処理装置は、ガベージコレクションを行う場合に、対象の物理ブロックの最小論理アドレスを検索開始位置として、論理アドレスが増える順序で物理アドレスを検索し、データ移動を行うか否かを判定する。これにより、物理アドレスから論理アドレスを検索する逆引きのテーブルを用いずにガベージコレクションが行え、ＮＡＮＤコントローラの回路規模を抑えることができる。また、最小論理アドレスより小さい論理アドレスについてはデータの移動判定を省略できるので、ガベージコレクションの時間を短縮でき、アクセス性能を向上させることができる。
【実施例２】
【０１２４】
次に、実施例２に係るＮＡＮＤコントローラについて説明する。本実施例に係るＮＡＮＤコントローラは、検索開始位置として最大論理アドレスを用いることが実施例１と異なる。そこで、以下では、最大論理アドレスの設定及び最大論理アドレスを検索開始位置とした場合のデータ移動の判定について主に説明する。本実施例に係るＮＡＮＤコントローラ６ａのブロック図も図３で表される。以下の説明では、実施例１と同じ機能を有する各部については説明を省略する。【０１２５】
図９は、実施例２に係る管理情報テーブルの一例の図である。図９に示すように、管理情報テーブル１９には、物理ブロックアドレス、有効ページ数、及び最大論理アドレスが対応付けて格納される。【０１２６】
最大論理アドレスとは、物理ブロックアドレスが示すブロックに含まれるページの各物理アドレスに対応する論理アドレスの中で最大のアドレスである。【０１２７】
例えば、図９に示す例では、管理情報テーブル１９には、物理ブロックアドレス「Ｂ００」と、有効ページ数「１１」と、最小論理アドレス「Ｌｆｆ０ｅ」とが対応付けて格納される。すなわち、管理情報テーブル１９は、物理ブロックアドレス「Ｂ００」が示す物理ブロックに含まれる物理ページのうち、１１個のページが有効であることを示す。また、管理情報テーブル１９は、物理ブロックアドレス「Ｂ００」に対応する論理アドレスの中で、最大の論理アドレスが「Ｌｆｆ０ｅ」であることを示す。【０１２８】
さらに、図９に示す例では、管理情報テーブル１９における物理ブロックアドレス「Ｂ０１」には、有効ページがなく、最大論理アドレスも設定されていない。ここで、最大論理アドレスが設定されていない場合、本実施例では、論理アドレス全体の中で最も大きい論理アドレスである「Ｌｆｆｆｆ」を初期値として設定する。【０１２９】
テーブル制御部１４は、リクエスト調停部１３が新たなデータの書込みを行う場合、テーブル更新要求から取得した物理アドレスが示す物理ブロックアドレスに対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ増やす。また、テーブル制御部１４は、抽出したエントリの最大論理アドレスを管理情報テーブル１９から取得する。そして、テーブル制御部１４は、書き込むデータの論理アドレスが取得した最大論理アドレスより大きいか否かを判定する。書き込むデータの論理アドレスが取得した最大論理アドレスより大きい場合、テーブル制御部１４は、書き込むデータの論理アドレスを抽出したエントリの最大論理アドレスに書き込む。【０１３０】
同様に、テーブル制御部１４は、リクエスト調停部１３がデータの更新を行う場合、更新先物理ブロックアドレスと対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ増やす。また、テーブル制御部１４は、抽出したエントリの最大論理アドレスを管理情報テーブル１９から取得する。そして、テーブル制御部１４は、更新するデータの論理アドレスが取得した最大論理アドレスより大きいか否かを判定する。更新するデータの論理アドレスが取得した最大論理アドレスより大きい場合、テーブル制御部１４は、更新するデータの論理アドレスを抽出したエントリの最大論理アドレスに書き込む。【０１３１】
また、テーブル制御部１４は、リクエスト調停部１３がデータの移動を行う場合、移動先物理ブロックアドレスと対応付けられたエントリを管理情報テーブル１９から抽出する。そして、テーブル制御部１４は、抽出したエントリの有効ページ数を１つ増やす。また、テーブル制御部１４は、抽出したエントリの最大論理アドレスを管理情報テーブル１９から取得する。そして、テーブル制御部１４は、移動するデータの論理アドレスが取得した最大論理アドレスより大きいか否かを判定する。移動するデータの論理アドレスが取得した最大論理アドレスより大きい場合、テーブル制御部１４は、移動するデータの論理アドレスを抽出したエントリの最大論理アドレスに書き込む。【０１３２】
巡回参照制御部１６の論理ブロック選択部１６１は、アドレス変換テーブル１８及び管理情報テーブル１９の参照要求をリクエスト調停部１３へ出力する。そして、論理ブロック選択部１６１は、リクエスト調停部１３からアドレス変換テーブル１８及び管理情報テーブル１９を受信する。【０１３３】
そして、論理ブロック選択部１６１は、管理情報テーブル１９から有効ページ数が閾値よりも小さい物理ブロックを１つ特定する。次に、論理ブロック選択部１６１は、特定した物理ブロックにおける最大論理アドレスを取得する。そして、論理アドレス選択部１６１は、最大論理アドレスに検索ポインタを設定する。その後、論理アドレス選択部１６１は、最大論理アドレスを物理アドレス取得部１６２へ出力する。【０１３４】
その後、論理アドレス選択部１６１は、判定部１６３から次の論理アドレスの取得の指示を受けると、検索ポインタを１つ減少させて、次に小さいアドレスを有する論理アドレスを移動判定処理の対象として新たに選択する。そして、論理アドレス選択部１６１は、選択した論理アドレスを物理アドレス取得部１６２へ出力する。すなわち、論理アドレス選択部１６１は、最大論理アドレスを検索開始アドレスとしてアドレスが小さくなる順に論理アドレスを１つずつ選択していく。この最大論理アドレスが、「検索開始位置」の一例にあたる。【０１３５】
巡回参照制御部１６の物理ブロック取得部１６２及び判定部１６１は、実施例１と同様に動作する。【０１３６】
次に、図１０を参照して、ＮＡＮＤコントローラ６ａが実行する処理の流れについて説明する。図１０は、実施例２に係るＮＡＮＤコントローラが実行する処理のフローチャートである。ＮＡＮＤコントローラ６ａは、所定の時間が経過した場合や、ソフトウェアからの指示を受けた場合は、図１０に示すデータ移動制御を実行する。【０１３７】
巡回参照制御部１６の論理ブロック選択部１６１は、物理ブロックを一つ選択し、管理情報テーブル１９における選択した物理ブロックの有効ページ数を検索する（ステップＳ３０１）。【０１３８】
そして、巡回参照制御部１６の論理ブロック選択部１６１は、選択した物理ブロックの有効ページ数が閾値未満か否かを判定する（ステップＳ３０２）。有効ページ数が閾値以上の場合（ステップＳ３０２：否定）、巡回参照制御部１６の論理ブロック選択部１６１は、ステップＳ３０１へ戻る。【０１３９】
これに対して、有効ページ数が閾値未満の場合（ステップＳ３０２：肯定）、巡回参照制御部１６の論理ブロック選択部１６１は、選択した物理ブロックの最大論理アドレスを管理情報テーブル１９から取得する。そして、巡回参照制御部１６の論理ブロック選択部１６１は、取得した最大論理アドレスに検索ポインタをセットする（ステップＳ３０３）。【０１４０】
次に、巡回参照制御部１６の物理ブロック取得部１６２は、検索ポインタが示す論理アドレスに対応する物理アドレスをアドレス変換テーブル１８から取得して、取得した物理アドレスを移動判定対象の物理アドレスとする（ステップＳ３０４）。【０１４１】
次に、巡回参照制御部１６の判定部１６３は、移動判定対象の物理アドレスを有するページが選択した物理ブロックに含まれているか否かを判定する（ステップＳ３０５）。選択した物理ブロックに含まれていない場合（ステップＳ３０５：否定）、巡回参照制御部１６の論理ブロック選択部１６１は、検索ポインタを１つデクリメントして検索ポインタを更新し（ステップＳ３０９）、ステップＳ３０４へ戻る。【０１４２】
一方、選択した物理ブロックに含まれる場合（ステップＳ３０５：肯定）、巡回参照制御部１６の判定部１６３は、移動判定対象の物理アドレスを有するページに有効データが格納されているか否かをアドレス変換テーブル１８から判定する（ステップＳ３０６）。有効データが格納されていない場合（ステップＳ３０６：否定）、巡回参照制御部１６の論理ブロック選択部１６１は、検索ポインタを１つデクリメントして検索ポインタを更新する（ステップＳ３０９）。【０１４３】
これに対して、有効データが格納されている場合（ステップＳ３０６：肯定）、巡回参照制御部１６の判定部１６３は、取得した物理アドレスを移動対象の物理アドレスとする。そして、巡回参照制御部１６の判定部１６３は、移動対象の物理アドレス及びそれに対応する論理アドレスの組をデータ移動制御部１７へ出力する。データ移動制御部１７は、データの移動要求をリクエスト調停部１３へ出力し、移動対象の物理アドレスからデータを移動させる。また、テーブル制御部１４は、アドレス変換テーブル１８の論理アドレスに関連付けられた物理アドレスを変更し、アドレス変換テーブル１８を更新する。さらに、巡回参照制御部１６は、管理情報テーブル１９における選択した物理ブロックの有効ページ数を１つ減らすことで、管理情報テーブル１９を更新する（ステップＳ３０７）。【０１４４】
次に、巡回参照制御部１６の判定部１６３は、選択した物理ブロックの有効ページ数が０になったか否かを判定する（ステップＳ３０８）。有効ページ数が０でない場合（ステップＳ３０８：否定）、巡回参照制御部１６の選択部１６１は、検索ポインタを１つデクリメントして検索ポインタを更新する（ステップＳ３０９）。【０１４５】
これに対して、有効ページ数が０の場合（ステップＳ３０８：肯定）、巡回参照制御部１６の判定部１６３は、ラストフラグをデータ移動制御部１７へ出力する。データ移動制御部１７は、移動対象の物理アドレスを含む物理ブロックの消去命令をリクエスト調停部１３へ送信し、その物理ブロックを消去させる。巡回参照制御部１６は、管理情報テーブル１９における選択した物理ブロックに対応する最大論理アドレスを初期値（例えば、０ｘｆｆｆｆ）に設定して管理情報テーブル１９を更新する（ステップＳ３１０）。【０１４６】
その後、巡回参照制御部１６は、空き容量が閾値以下か否かを判定する（ステップＳ３１１）。空き容量が閾値以下の場合（ステップＳ３１１：肯定）、巡回参照制御部１６は、ステップＳ３０１へ戻る。これに対して、空き容量が閾値より大きい場合（ステップＳ３１１：否定）、ＮＡＮＤコントローラ６ａは、データの移動制御の処理を終了する。【０１４７】
次に、図１１を参照して、本実施例に係る管理情報テーブル１９の最大論理アドレスの更新処理について説明する。図１１は、実施例２に係る管理情報テーブルの最大論理アドレスの更新処理のフローチャートである。【０１４８】
テーブル制御部１４は、リクエスト調停部１３が書き込み命令をリクエスタインターフェース部１２から受信したか否かを判定する（ステップＳ４０１）。書き込み命令を受信していない場合（ステップＳ４０１：否定）、テーブル制御部１４は、最大論理アドレスの更新処理を終了する。【０１４９】
これに対して、書き込み命令を受信した場合（ステップＳ４０１：肯定）、テーブル制御部１４は、書き込み命令でデータの格納先として指定された論理アドレスを基に、実際にデータが格納されている物理アドレスを含む物理ブロックを管理情報テーブル１９から検索する（ステップＳ４０２）。【０１５０】
次に、テーブル制御部１４は、検索した物理ブロックの最大論理アドレスを管理情報テーブル１９から取得する（ステップＳ４０３）。【０１５１】
そして、テーブル制御部１４は、データの格納先の論理アドレスが取得した最大論理アドレスより大きいか否かを判定する（ステップＳ４０４）。データの格納先の論理アドレスが取得した最大論理アドレス以下の場合（ステップＳ４０４：否定）、テーブル制御部１４は、最大論理アドレスの更新処理を終了する。【０１５２】
これに対して、データの格納先の論理アドレスが取得した最大論理アドレスより大きい場合（ステップＳ４０４：肯定）、テーブル制御部１４は、検索した物理ブロックの最大論理アドレスをデータの格納先の論理アドレスに更新する（ステップＳ４０５）。【０１５３】
以上に説明したように、本実施例に係る情報処理装置は、ガベージコレクションなどのデータ移動を行う場合に、対象の物理ブロックの最大論理アドレスを検索開始位置として、論理アドレスが増える順序で物理アドレスを検索し、データ移動を行うか否かを判定する。この場合も、最大論理アドレスより大きい論理アドレスについてはデータの移動判定を省略できるので、データの移動の時間を短縮でき、アクセス性能を向上させることができる。【０１５４】
また、以上に説明した各実施例では、データ移動を行う物理ブロックを特定し、その物理ブロックに含まれるページの物理アドレスに対応する論理アドレスか否かの判定を行ったが、処理の順番はこれに限らない。例えば、論理アドレスを管理テーブルの中から選び対応する物理アドレスを特定した後に、その物理アドレスを有するページを含む物理ブロックが移動対象となる物理ブロックか否かを判定して、データ移動の処理を行ってもよい。【０１５５】
図１２は、制御プログラムを実行するＮＡＮＤコントローラの一例の図である。図１２に示すように、ＮＡＮＤコントローラ６ｅは、ＣＰＵ４０、デバイスアクセス制御部１５を有する。また、ＣＰＵ４０は、メモリデバイス１１ａと接続される。なお、メモリデバイス１１ａは、ＮＡＮＤコントローラ６ｅに内蔵されるメモリであってもよい。【０１５６】
メモリデバイス１１ａには、アドレス変換テーブル１８、管理情報テーブル１９があらかじめ記憶される。ここで、ＣＰＵ４０が制御プログラム３０を読出して展開して実行することにより、制御プログラム３０は、以下の様に機能する。すなわち、制御プログラム３０は、ＣＰＵ４０をテーブル制御部３１、リクエスト調停部３２、巡回参照制御部３３、データ移動制御部３４として動作させる。ここで、テーブル制御部３１、リクエスト調停部３２、巡回参照制御部３３、及びデータ移動制御部３４は、図３に示すテーブル制御部１４、リクエスト調停部１３、巡回参照制御部１６、データ移動制御部１７と同様の機能を発揮する。【０１５７】
なお、ＮＡＮＤコントローラ６ｅは、ＣＰＵではなく、例えばＭＰＵやＦＰＧＡ等の演算装置を用いて制御プログラム３０を実行しても良い。また、上記の制御プログラム３０については、例えば、メモリデバイス１１ａや、ＮＡＮＤデバイス７ａ〜１０ａに記憶させてもよいし、他の方法でＣＰＵ４０に実行させてもよい。例えば、フレキシブルディスク、いわゆるＦＤ（Flexible  Disk）、ＣＤ（Compact  Disk）−ＲＯＭ、ＤＶＤ（Digital  Versatile  Disk）、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」に各プログラムを記憶させる。【０１５８】
そして、ＮＡＮＤコントローラ６ｅが各ＣＰＵ４０を介して、これらの可搬用の物理媒体から各プログラムを取得して実行するようにしてもよい。また、公衆回線、インターネット、ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）などを介して他のコンピュータまたはサーバ装置などに記憶させた各プログラムを取得して実行するようにしてもよい。
【符号の説明】
【０１５９】
１  情報処理装置
２ａ，２ｂ  メモリ
３ａ，３ｂ，４０  ＣＰＵ
４  Ｉ／Ｏハブ
５ａ，５ｂ  ＳＳＤ
６ａ，６ｂ，６ｅ  ＮＡＮＤコントローラ
７ａ〜１０ａ，７ｂ〜１０ｂ  ＮＡＮＤデバイス
１１  テーブル記憶部
１２  リクエスタインターフェース部
１３，３２  リクエスト調停部
１４，３１  テーブル制御部
１５  デバイスアクセス制御部
１６，３３  巡回参照制御部
１７，３４  データ移動制御部
１８  アドレス変換テーブル
１９  管理情報テーブル
３０  制御プログラム
１６１  論理アドレス選択部
１６２  物理アドレス取得部
１６３  判定部
【図１】
0005967307.tif 000002
【図２】
0005967307.tif 000003
【図３】
0005967307.tif 000004
【図４】
0005967307.tif 000005
【図５】
0005967307.tif 000006
【図６】
0005967307.tif 000007
【図７】
0005967307.tif 000008
【図８】
0005967307.tif 000009
【図９】
0005967307.tif 000010
【図１０】
0005967307.tif 000011
【図１１】
0005967307.tif 000012
【図１２】
0005967307.tif 000013