(57)【特許請求の範囲】
【請求項１】
ホストとメモリサブシステムとを備えた情報処理装置であって、
前記ホストは、前記メモリサブシステムへデータに対応するタグ情報とともに書き込み命令または消去命令を発行し、前記データを処理する情報処理回路を備え、
前記タグ情報は、
前記ホストのデータ処理単位であるグループを識別する情報、前記ホストのデータ処理ステップであるスーパーステップを識別する情報、前記ホストが処理するデータの種類を識別するデータ種類識別子を含み、
前記メモリサブシステムは、
第２のメモリを管理する管理情報を記憶した第１のメモリと、
データ消去単位のサイズがデータ書き込み単位のサイズより大きく、前記データを記憶する前記第２のメモリと、
前記データ消去単位のｎ倍（ｎは自然数）を管理単位とする前記管理情報に基づいて、同一の前記タグ情報のデータを同一の前記管理単位へ書き込み、異なる前記タグ情報のデータを異なる前記管理単位へ書き込むメモリサブシステム制御回路と、を備えたこと
を特徴とする情報処理装置。
【請求項２】
前記管理情報は、前記データの前記第２のメモリにおけるアドレスと、前記データに対応する前記タグ情報との関係付けを含み、テーブルに記憶したことを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記管理情報は、前記タグ情報と、前記タグ情報に対応するデータが書き込まれる前記管理単位との関係付けを含み、テーブルに記憶したことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記メモリサブシステムは、
前記第２のメモリよりも高速にアクセス可能な前記第１のメモリと、
不揮発性メモリである前記第２のメモリと、を備えたこと
を特徴とする請求項１〜３のいずれか１項に記載の情報処理装置。
【請求項５】
前記メモリサブシステムは、
前記第２のメモリのブロックを管理する管理情報を記憶した前記第１のメモリと、
データ消去単位である前記ブロックを複数含み、書き込み単位であるページを前記ブロックの中に複数含む前記第２のメモリと、
前記管理情報を参照して前記ブロックを特定し、計算により前記ページを特定する前記メモリサブシステム制御回路と、を備えたこと
を特徴とする請求項１〜４のいずれか１項に記載の情報処理装置。
【請求項６】
ホストとメモリサブシステムとを備えた情報処理装置であって、
前記ホストは、前記メモリサブシステムへ書き込み命令または消去命令を発行し、前記メモリサブシステムの中のメモリのデータ消去単位のｎ倍（ｎは自然数）を管理単位とし、タグ情報と前記管理単位とを管理情報により関係付け、データを処理する情報処理回路を備え、
前記タグ情報は、
前記ホストのデータ処理単位であるグループを識別する情報、前記ホストのデータ処理ステップであるスーパーステップを識別する情報、前記ホストが処理するデータの種類を識別するデータ種類識別子を含み、
前記メモリサブシステムは、
前記データ消去単位のサイズがデータ書き込み単位のサイズより大きく、前記データを記憶する前記メモリと、
前記ホストの前記書き込み命令により、同一の前記タグ情報のデータを同一の前記管理単位へ書き込み、異なる前記タグ情報のデータを異なる前記管理単位へ書き込むメモリサブシステム制御回路と、を備えたこと
を特徴とする情報処理装置。
【請求項７】
前記メモリサブシステムは、
前記メモリよりも高速にアクセス可能な第１のメモリと、
不揮発性メモリである前記メモリと、を備えたこと
を特徴とする請求項６に記載の情報処理装置。
【請求項８】
前記ホストは、前記管理情報を参照して前記メモリのブロックを特定し、計算により前記メモリのページを特定する情報処理回路を備え、
前記メモリサブシステムは、データ消去単位である前記ブロックを複数含み、書き込み単位である前記ページを前記ブロックの中に複数含む前記メモリを備えたこと
を特徴とする請求項６または７に記載の情報処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、不揮発性メモリを用いて大規模データの高速処理に適した情報処理装置に関するものである。
【背景技術】
【０００２】
近年の大規模データの増加に応じて、大規模データを安価に低消費電力で記憶できる大容量不揮発性メモリの使用が望まれている。また、大規模データの処理では多くのデータを読み書きする必要があるため、読み書きの高速化も望まれている。【０００３】
これに対し、従来の不揮発性メモリを用いた記憶装置では、データ消去単位（ブロック）がデータ書き込み単位より大きく、不要なデータであってもデータの上書きができないため、ブロックが必要なデータと不要なデータで満たされるとそのままでは新しいデータを書き込めない。そこで、ホストから記憶装置へ新しいデータを書き込む際、書き込み可能な領域が不足すると、記憶装置は、物理的に散在する必要なデータをそれぞれのブロックから読み出したのち、データを読み出したブロックを消去し、読み出したデータを消去されたブロックへ書き戻していた。これにより消去されたブロックの書き戻されたデータ以外の領域を書き込み可能な領域として確保するのが一般的であった。この処理はガーベッジコレクションと呼ばれている。【０００４】
また、特許文献１には、不揮発性メモリを用いた記憶装置に対し、ホストはファイルデータを消去した段階で、そのファイル名もしくはアドレスを記憶装置へ通知し、記憶装置はホストから消去を通知された段階でデータを無効化し、記憶装置は消去対象のブロックに無効化したデータのみしかない場合にガーベッジコレクションを実行せず、単に消去する技術が開示されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８-１９８２０８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
不揮発性メモリを用いた記憶装置ではガーベッジコレクションが必要であり、ガーベッジコレクションの処理中はホストの読み書きの処理が待たされて記憶装置の性能低下を招くと共に、ガーベッジコレクションそのものが書き込み処理を含むため、書き込み回数に上限のある記憶装置の寿命劣化を招く。【０００７】
また、上記の特許文献１に開示された技術では消去ブロックに無効化したデータのみしかない場合にはガーベッジコレクションを不要とするものの、必ずしも消去ブロックが無効化したデータで満たされるとは限らないため、依然としてガーベッジコレクションの発生は回避できず、ガーベッジコレクションの課題を解決できていない。【０００８】
そこで、本発明の目的は、安価で大容量な不揮発性メモリにおけるガーベッジコレクションの発生を排除することにより、不揮発性メモリを用いた記憶装置のデータ読み書きを高速化すると共に、記憶装置の寿命を延ばすことにある。
【課題を解決するための手段】
【０００９】
本発明にかかる情報処理装置は、ホストとメモリサブシステムとを備えた情報処理装置であって、前記ホストは、前記メモリサブシステムへデータに対応するタグ情報とともに書き込み命令または消去命令を発行し、前記データを処理する情報処理回路を備え、前記メモリサブシステムは、第２のメモリを管理する管理情報を記憶した第１のメモリと、データ消去単位のサイズがデータ書き込み単位のサイズより大きく、前記データを記憶する前記第２のメモリと、前記データ消去単位のｎ倍（ｎは自然数）を管理単位とする前記管理情報に基づいて、同一の前記タグ情報のデータを同一の前記管理単位へ書き込み、異なる前記タグ情報のデータを異なる前記管理単位へ書き込むメモリサブシステム制御回路と、を備えたことを特徴とする。【００１０】
また、本発明にかかる情報処理装置は、前記ホストが、前記メモリサブシステムへ前記タグ情報とともに読み出し命令を発行する前記情報処理回路を備え、前記メモリサブシステムは、同一の前記タグ情報に対応するデータを、前記第２のメモリから読み出し、前記ホストに転送する前記メモリサブシステム制御回路を備えたことを特徴とする。【００１１】
また、本発明にかかる情報処理装置は、前記メモリサブシステムが、同一の前記タグ情報に対応するデータを、前記第２のメモリから消去する前記メモリサブシステム制御回路を備えたことを特徴とする。【００１２】
そして、本発明にかかる情報処理装置は、前記メモリサブシステムが、前記第２のメモリよりも高速にアクセス可能な前記第１のメモリと、不揮発性メモリである前記第２のメモリと、を備えたことを特徴とする。
【発明の効果】
【００１３】
本発明によれば、大規模データの解析などに必要な大規模なメモリ空間を不揮発性メモリで安価に提供でき、かつ、その場合でも、消去単位のｎ倍の管理単位で読み書き消去をするため、不揮発性メモリにおけるガーベッジコレクションの発生を排除できる。これにより高速なデータの読み書きを実現することができると共に、不揮発性メモリの寿命を延ばせる。
【図面の簡単な説明】
【００１４】
【図１】サーバ（情報処理装置）の構成の例を示す図である。
【図２】サーバ内のメモリサブシステムの構成の例を示す図である。
【図３】メモリサブシステム内の不揮発性メモリのチップ、ブロック、ページの構成と読み書き消去の処理対象の例を示す図である。
【図４】サーバの処理対象であり、大規模データであるグラフの例を示す図である。
【図５】サーバにおいて実行されるグラフ解析処理のシーケンスの例を示す図である。
【図６】ホストが扱う論理アドレスとデータとの対応関係の例を示す図である。
【図７】ホストからメモリサブシステムへ送信される情報の例を示す図である。
【図８】不揮発性メモリのチップ、ブロックとスーパーステップ、グループに属するデータとの対応関係の例を示す図である。
【図９】データ管理テーブルの例を示す図である。
【図１０】不揮発性メモリへの書き込みのチップ、ブロック、ページの順番の例を示す図である。
【図１１】異なるグループにおける書き込み開始チップの相違の例を示す図である。
【図１２】異なるグループにおける書き込み開始チャネルの相違の例を示す図である。
【図１３】サーバにおけるデータ書き込み処理の例を示すフローチャートである。
【図１４】不揮発性メモリの状態管理テーブルの例を示す図である。
【図１５】サーバにおけるデータ読み出し処理の例を示すフローチャートである。
【図１６】サーバおけるデータ消去処理の例を示すフローチャートである。
【図１７】不揮発性メモリにおけるデータ処理の例を示すフローチャートである。
【図１８】不揮発性メモリの書き込みデータ量の管理テーブルの例を示す図である。
【図１９】不揮発性メモリの書き込みデータ量とページとの対応関係の例を示す図である。
【発明を実施するための形態】
【００１５】
以下に添付図面を参照して、好ましいサーバ（情報処理装置）の実施の形態を詳細に説明する。
＜Ａ．サーバの構成＞
まず、サーバ(SVR)０１０１の構成について、図１と図２を用いて説明する。図1に、情報処理装置であるサーバ０１０１全体の構成を示す。サーバ０１０１は、複数のホスト (Host(1)〜Host(N))０１０２と、全てのホスト０１０２を接続するインターコネクト(Interconnect) ０１０３と、それぞれのホスト０１０２に接続された複数のメモリサブシステム(MSS(1)〜MSS(N))０１０４とから構成される。
【００１６】
ホスト０１０２は、情報処理回路(CPU)０１０５と、この情報処理回路０１０５に接続された1個以上のメモリ(DRAM)０１０６から構成される。情報処理回路０１０５はメモリ０１０６から情報を読み込み、情報を書き込むことにより処理を実行する。
【００１７】
全てのホスト０１０２はインターコネクト０１０３を介して互いに通信することができる。また、ホスト０１０２はそれぞれ接続されたメモリサブシステム０１０４と互いに通信することができる。
【００１８】
メモリサブシステム０１０４は、それぞれ1個のメモリサブシステム制御回路(MSC)０１０７と1個以上の不揮発性メモリ(NVM)０１０８ と1個以上のメモリ(DRAM)０１０９から構成される。メモリサブシステム制御回路０１０７ はホスト０１０２、不揮発性メモリ０１０８、メモリ０１０９と互いに通信することができる。
【００１９】
メモリサブシステム０１０４の中のメモリ０１０９は管理情報などを格納するメモリであり、高速なDRAMが好ましいが、DRAM以外にMRAM、相変化メモリ、SRAM、NORフラッシュメモリ、ReRAMなどのランダムアクセスメモリでもよい。また、不揮発性メモリ０１０８へ書き込むデータと読み出すデータとを一時的に記憶して不揮発性メモリ０１０８のキャッシュとして使用してもよい。不揮発性メモリ０１０８はホスト０１０２から書き込まれたデータを格納するメモリであり、安価で大容量なNANDフラッシュメモリ、相変化メモリ、ReRAMなどのデータ消去単位のサイズがデータ書き込み単位のサイズ以上であるメモリである。
【００２０】
ホスト０１０２はメモリサブシステム０１０４を使用して処理するデータにタグ番号を付加し、メモリサブシステム制御回路０１０７は不揮発性メモリ０１０８の消去単位を管理して、同一のタグ番号の付加されたデータを不揮発性メモリ０１０８の同一の消去単位へ書き込む。この処理のシーケンスは図６を用いて後で説明する。なお、ホスト０１０２がメモリサブシステム制御回路０１０７に相当する機能を備え、消去単位の管理及びタグ番号との対応付けをメモリサブシステム０１０４の中ではなくホスト０１０２の中で行ってもよい。
【００２１】
図２はメモリサブシステム０１０４をさらに詳細に示したものである。
【００２２】
メモリサブシステム０１０４は、1個のメモリサブシステム制御回路０１０７と、不揮発性メモリ不揮発性メモリ(NVM(1,1)〜NVM(i,j))０１０８ と、メモリ(DRAM (1)〜DRAM(p))０１０９とから構成される（i、j、pは自然数）。メモリサブシステム制御回路０１０７は、メモリアクセス制御回路（DMAC）０２０１とコマンドバッファ（C-BF）０２０２と、データバッファ（D-BF）０２０３と、アドレスバッファ（A-BF）０２０４と、タグバッファ（T-BF）０２０５と、レジスタ（RG）０２０６と、ガーベッジコレクション排除制御ブロック（GCLS_CB）０２０７と、不揮発性メモリ制御回路（NVMC(1)〜NVMC(i)）０２０８と、DRAM制御回路（DRAMC(1)〜DRAMC(p)）０２０９とから構成される。
【００２３】
メモリアクセス制御回路０２０１は、図1におけるホスト０１０２と、コマンドバッファ０２０２と、データバッファ０２０３と、アドレスバッファ０２０４と、タグバッファ０２０５と、レジスタ０２０６と接続されており、接続先間の通信を中継する。コマンドバッファ０２０２、データバッファ０２０３、アドレスバッファ０２０４、タグバッファ０２０５、レジスタ０２０６のぞれぞれはガーベッジコレクション排除制御ブロック０２０７とも接続されており、コマンドバッファ０２０２は、データの読み出し命令、書き込み命令、消去命令を一時的に格納するバッファであり、データバッファ０２０３は、読み書きされるデータを一時的に格納するバッファである。アドレスバッファ０２０４は、ホスト０１０２からの読み出し、書き込み及び消去命令におけるデータのアドレスを一時的に格納するバッファである。なお、データのサイズも一時的に格納することができる。
【００２４】
タグバッファ０２０５は、ホスト０１０２からの読み出し、書き込み及び消去命令におけるデータのグループ(Gr.)の番号、スーパーステップ(S.S.)の番号、書き込み順(order)の番号、データ種類識別子(IDX)などのタグ番号を一時的に格納するバッファである。グループとスーパーステップについては図５を用いて後で説明し、書き込み順については図６、図１０などを用いて後で説明し、データ種類識別子については図９などを用いて後で説明する。ただし、タグ番号はこれらの番号などに限定されるものではなく、これ以外の番号であってもよいし、例えば書き込み順の番号などが無くてもよい。タグ番号は不揮発性メモリ０１０８の消去単位内のすべてのデータにおいて同一の番号であり、異なるタグ番号に対応するデータは、不揮発性メモリ０１０８の異なる消去単位内に格納されていればよい。このようなタグ番号であるから、タグ番号そのものは書き込み順や不揮発性メモリ０１０８の物理アドレスなどを含み、タグ番号が同一の番号であるという基準が書き込み順や物理アドレスとは関係なく、不揮発性メモリ０１０８の消去単位として同一であるというものでもよい。
【００２５】
レジスタ０２０６は、ホスト０１０２が設定するガーベッジコレクション排除制御ブロック０２０７の処理に必要な制御情報を格納して、ガーベッジコレクション排除制御ブロック０２０７から読み出し可能とするレジスタである。
【００２６】
ガーベッジコレクション排除制御ブロック０２０７は、レジスタ０２０６、コマンドバッファ０２０２、データバッファ０２０３、アドレスバッファ０２０４、タグバッファ０２０５と通信し、不揮発性メモリ制御回路０２０８とDRAM制御回路０２０９を制御するものである。
【００２７】
不揮発性メモリ制御回路（NVMC(1)〜NVMC(i)）０２０８は、不揮発性メモリ（NVM(i,1)〜NVM(i,j)）０１０８に接続されており、接続された不揮発性メモリ０１０８のデータ読み出しと、データの書き込みと、データの消去を行う。ここで、iは1〜iの自然数であってチャネル番号を表し、複数のチャネル０２１０はそれぞれ独立して通信できるデータ転送バス(I/O)０２１２を備える。１つのチャネルi(Ch i)０２１０に属するj個の不揮発性メモリ(NVM(i,1), NVM(i,2), …, NVM(i,j))０１０８は、データ転送バス０２１２を共有する。また、各チャネルに属するj個の不揮発性メモリ０１０８は、メモリとしては独立しているため、不揮発性メモリ制御回路０２０８からの命令を独立に処理することができる。j個の不揮発性メモリ０１０８は、不揮発性メモリ制御回路０２０８から物理的に近い順にウェイ(Way1, Way2, …, Wayj)０２１１に属する。各不揮発性メモリ０１０８がデータ処理中か否かを、不揮発性メモリ制御回路０２０８は、各不揮発性メモリ０１０８に接続されたレディービジー線(RY/BY)０２１３の信号を読むことで判定することができる。不揮発性メモリ制御回路０２０８は、ガーベッジコレクション排除制御ブロック０２０７と接続され、互いに通信できる。
【００２８】
DRAM制御回路（DRAMC(1)〜DRAMC(p)）０２０９は、それぞれメモリ（DRAM(1)〜DRAM(p)）０１０９に接続され、メモリ０１０９からのデータ読み出しとメモリ０１０９へのデータの書き込みを行う。また、DRAM制御回路０２０９は、ガーベッジコレクション排除制御ブロック０２０７と接続され、互いに通信できる。
＜Ｂ．不揮発性メモリの構造と読み書き消去処理＞
次に、図３を用いて、不揮発性メモリ０１０８内の構成及びデータの読み出しと書き込みと消去の処理を説明する。それぞれの不揮発性メモリ０１０８は、N_br個のブロック(BLK)０３０１から構成され、各ブロック０３０１はN_pg個のページ(PG)０３０２から構成される。ここで、N_brとN_pgは自然数である。例えば、不揮発性メモリ０１０８である容量8GB/chipのNANDフラッシュメモリにおける1ブロック０３０１のデータサイズが1MBで、1ページ０３０２のデータサイズが8kBの時、N_br=8k=(8GB/1MB)であり、N_pg=128=(1MB/8kB)である。
【００２９】
不揮発性メモリ０１０８に格納されたデータはページ０３０２の単位で読み出され、不揮発性メモリ０１０８へデータを書き込む際はページ０３０２の単位で書き込む。また、不揮発性メモリ０１０８に格納されたデータはブロック０３０１の単位で消去される。不揮発性メモリ０１０８にデータを書き込む際、データの上書きはできない。したがって、例えば図３において消去されたブロック０３０３内のページ(PG_e)０３０４へデータを書き込むことはできるが、既にデータが書き込まれたページ(PG_d)０３０５には新しいデータを書き込むことはできない。以上をまとめると不揮発性メモリ０１０８は以下の２つの特徴を有する。
【００３０】
特徴１：消去単位(ブロック０３０１)のデータサイズは書き込み単位(ページ０３０２)のデータサイズ以上である。
【００３１】
特徴２：データが既に書き込まれたページ０３０５などには新しいデータを上書きできない。
【００３２】
以下、サーバ０１０１の処理について、大規模グラフ解析を例に挙げて説明する。まず、図４、５を用いて、サーバ０１０１で取り扱うグラフの例とそのグラフデータの解析シーケンスの例を説明する。 
＜Ｃ．グラフとグラフ解析シーケンス＞
図４は、サーバ０１０１で取り扱うグラフの一例を示す図である。ここで例として挙げるグラフは、グラフの頂点０４０１に各頂点を一意に特定する頂点番号が割り当てられており、２つの頂点を繋ぐ一本のグラフの辺は、その２つの頂点の間に関係性があることを表す。グラフの各頂点０４０１が解析対象のグラフデータとなる。一般にグラフ解析の対象となるグラフの頂点０４０１は膨大な数となるため、複数の頂点０４０１は割り当てられた頂点番号に応じてグループに分けられ、グループごとに頂点０４０１すなわちグラフデータを解析する。
【００３３】
図５にサーバ０１０１におけるグラフ解析のシーケンスを示す。メモリサブシステム０１０７内の不揮発性メモリ０１０８には、グラフデータ(Graph)及びグラフ解析の結果(Result)が格納され、グラフデータ及びグラフ解析の結果は、グループに分割されて読み書きされて処理される。以下のシーケンスは、Ｎ個のホスト０１０２及びメモリサブシステム０１０４において、同時並行的に実行される。
【００３４】
時刻１：まず、メモリサブシステム０１０４は不揮発性メモリ０１０８に格納されたグループ1のグラフデータを読み出し(Read Gr.1)０５０１、ホスト０１０２へ送付する(Send)０５０２。
【００３５】
時刻２：次に、ホスト０１０２は、メモリサブシステム０１０４から送られてきたグループ１のグラフデータを解析する(Analyze Gr.1)０５０３。これと並行して、メモリサブシステム０１０４は、次にホスト０１０２で解析されるグループ２のグラフデータを読み出す（０５０４）。これらと並行して、メモリサブシステム０１０４は、グループ１のグラフデータを消去する（０５０５）。このグループ１のグラフデータはホストによる解析の後、二度と使われないため、このタイミングで消去が可能である。
【００３６】
時刻３：それぞれのホスト０１０２は、グループ１のグラフ解析の結果を他のホスト０１０２へ伝える。各ホスト０１０２は他のホスト０１０２から送られてきたグラフ解析の結果をグループごとに分類してメモリサブシステム０１０４へ送付する。メモリサブシステム０１０４はホスト０１０２から送付されたグループごとのグラフ解析の結果を不揮発性メモリ０１０８に書き込む(Write Gr. at random)０５０６。すなわち、ホスト０１０２からは不揮発性メモリ０１０８の書き込み単位である１ページ０３０２ごと、グループ番号がランダムな順でメモリサブシステム０１０４へデータを送付する。
【００３７】
以上のシーケンスをグループ順に繰り返し、全てのグループ１〜Ｍの処理の終了後、処理終了の確認のため、ホスト(Host(1)〜Host(N))０１０２間で同期が実行される(SYNC)。この一連のグループ１〜Ｍの処理及び同期をスーパーステップ(S.S.)と呼び、同期の後、再度グループ１から順に処理は繰り返される。前のスーパーステップでメモリサブシステム０１０４に書き込まれたグラフ解析の結果はグラフデータとなって、次のスーパーステップで読み出される。グラフ解析はこのスーパーステップの繰り返しによって実行される。
＜Ｄ．ホストとメモリサブシステム間の通信＞ 
図６、７を用いて、ホスト０１０２とメモリサブシステム０１０４の間の通信を説明する。図６に示すように、ホスト０１０２はメモリサブシステム０１０４内に格納されるデータを論理アドレス(LA)で管理する。グラフ解析において、ホスト０１０２は不揮発性メモリ０１０８の書き込み単位であるページ０３０２ごと、グループ番号がランダムな順でメモリサブシステム０１０４にデータを書き込む。その際、各グループデータの書き込み先論理アドレスは、グループごとホスト０１０２によって定められた管理単位(LAunit_host)で管理する。ホスト０１０２は、各グループのデータをメモリサブシステム０１０４へ送付する順に、各LAunit_hostの論理アドレスの先頭から順に埋めてゆき、グループごとにページ０３０２の単位の書き込み順(order)を付けて管理する。
【００３８】
図７は、ホスト０１０２がメモリサブシステム０１０４へ読み出し、書き込み、及び消去命令を送る際に、メモリサブシステム０１０４へ送付する情報を示す図である。
（ａ） 読み出し
ホスト０１０２がメモリサブシステム０１０４内のデータの読み出し命令を発行する際(Read)、ホスト０１０２はメモリサブシステム０１０４へ読み出すデータのスーパーステップ(S.S.)の番号と、グループ(Gr.)の番号と、データ種類識別子(IDX)を送付する。もしくは、ホスト０１０２はメモリサブシステム０１０４へ論理アドレス(Adr)及び読み出しデータサイズ(size)を送付する。データ種類識別子は、メモリサブシステム０１０４が異なるグラフデータを区別したり、グラフデータとグラフ解析の結果を区別したり、頂点番号を区別したりする際に用いられる付加情報である。メモリサブシステム０１０４は、ホスト０１０２から送付された上記情報を基に、データを読み出し、ホスト０１０２へ読み出したデータを返す。
（ｂ） 書き込み
ホスト０１０２がメモリサブシステム０１０４へデータ書き込み命令を発行する際(Write)、ホスト０１０２はメモリサブシステム０１０４へ書き込みデータのスーパーステップ(S.S.)の番号と、グループ(Gr.)の番号と、データ種類識別子(IDX)と、グループ内の書き込み順(order)と、書き込みデータ(data)と、必要に応じて、論理アドレス(Adr)と書き込みデータサイズ(size)を送付する。メモリサブシステム０１０４はホスト０１０２から送付された上記情報を基に、データを不揮発性メモリ０１０８へ書き込む。なお、グループ内の書き込み順はタグ番号に含めなくてもよい。
（ｃ）消去
ホスト０１０２がメモリサブシステム０１０４内のデータの消去命令を発行する際(Erase)、ホスト０１０２はメモリサブシステム０１０４へ消去するデータのスーパーステップ(S.S.)の番号とグループ(Gr.)の番号とデータ種類識別子(IDX)を送付する。もしくは、ホスト０１０２はメモリサブシステム０１０４へ論理アドレス(Adr)及び消去するデータサイズ(size)を送付する。メモリサブシステム０１０４は、ホスト０１０２から送付された上記情報を基に、データを消去する。
＜Ｅ．メモリサブシステムでのデータ管理方法＞ 
図８〜１２を用いて、メモリサブシステム０１０４内でのデータの管理方法を説明する。図８に示すように、メモリサブシステム制御回路０１０７は各スーパーステップ及びグループの番号ごとに、データを複数の不揮発性メモリ０１０８のブロック０３０１から構成される管理単位(PAunit_ctrl)に割り当ててレジスタ０２０６に格納する。図８の例では、チャネル(Ch.１〜i)及び２つのウェイ０２１１に属する２ｉ個の不揮発性メモリ０１０８の各ブロックをまとめて一つのPAunit_ctrlとし、同じPAunit_ctrlには同一スーパーステップ且つ同一グループのデータのみが格納され。異なるスーパーステップもしくは異なるグループのデータは異なるPAunit_ctrlに格納されて、図５のシーケンスにしたがって並列に処理される。図８では１つのPAunit_ctrlを２つのウェイ０２１１としたが、３つ以上としてもよい。異なるチャネル０２１０には異なる不揮発性メモリ０１０８が異なるデータ転送バス０２１２で接続されているため、複数の不揮発性メモリ０１０８を同時に動作させることができ、異なるウェイ０２１１ではデータ転送バス０２１２を共用するものの、異なる不揮発性メモリ０１０８を同時に動作させることができるので、高速なデータ転送を実現できる。また、一つのPAunit_ctrlを消去しても異なるスーパーステップもしくは異なるグループのブロック０３０１へは影響しないため、ガーベージコレクションを必要としないので、高速なデータ転送を実現できる。そして、高速なデータ転送により高速なグラフ解析を実現できる。
【００３９】
LAunit_hostとPAunit_ctrlで管理するため、メモリ０１０９に格納したテーブル(GR_PA)０９００、テーブル(LA_GR)０９１０、テーブル(GR_PTR)１８００、テーブル(PBA_ST)１４００を使用するが、まずテーブル(GR_PA)０９００とテーブル(LA_GR)０９１０を説明し、テーブル(GR_PTR)１８００とテーブル(PBA_ST)１４００についてはそれぞれ図１８と図１４を用いて後で説明する。
【００４０】
データのスーパーステップ及びグループの番号と、データの格納されるウェイ及びブロックの番号の対応は、図９（ａ）に示すテーブル(GR_PA)０９００によって管理される。また、論理アドレスと、各スーパーステップ及びグループの番号との対応は、図９（ｂ）のテーブル(LA_GR)０９１０によって管理される。これらのテーブル０９００、０９１０は、グラフデータとグラフ解析の結果すなわちデータ種類識別子の内容などに応じて一つずつ用意してもよい。
【００４１】
スーパーステップ及びグループの番号とデータ種類識別子(IDX)が与えられれば、メモリサブシステム制御回路０１０７はテーブル(GR_PA)０９００を用いて、対応するデータが格納されるPAunit_ctrlを構成する不揮発性メモリ０１０８の最初のウェイ(Way_S)とそのウェイ(Way_S)における最初のブロック番号(PBA_S)０９０３から最後のウェイ(Way_E)とそのウェイ(Way_E)における最後のブロック番号(PBA_E)０９０４を特定できる。図９（ａ）においてスーパーステップの番号が１、グループの番号が１、データ種類識別子がグラフ解析の結果の場合、最初のウェイ(Way_S)が１であり、ウェイ(Way_S)が１における最初のブロック番号(PBA_S)は０ｘ３３（１６進数で３３）である。一つのスーパーステップとグループとデータ種類識別子に対応するデータが１つのPAunit_ctrlに収まらず、複数のPAunit_ctrlにまたがる場合は、テーブル(GR_PA)０９００に、それぞれのPAunit_ctrlにおけるウェイの番号やブロックの番号を順に格納し、ウェイ(Way_S(1))０９０３の次のPAunit_ctrlの先頭はウェイ(Way_S(2))０９０５などとする。すなわち、ウェイ(Way_S(1)〜Way_E(1))とウェイ(Way_S(2)〜Way_E(2))とはそれぞれ１つのPAunit_ctrlに対応する。
また、データの論理アドレスが与えられれば、メモリサブシステム制御回路０１０７は、テーブル(LA_GR)０９１０を用いて、データが属するスーパーステップ及びグループの番号とデータ種類識別子を判定できる。テーブル(LA_GR)０９１０におけるエントリ(LAunit_host)は、ホストによる論理アドレスの管理単位であるLAunit_hostの番号であり、該当する論理アドレスのデータが、各スーパーステップ及びグループの番号で何番目のデータに対応するかはOrder_LA_hostの値となる。
【００４２】
次に、メモリサブシステム制御回路０１０７のPAunit_ctrl内でのデータの配置を図１０〜１２を用いて説明する。まず、スーパーステップの番号がk、グループの番号が１のデータの配置の例を示す。メモリサブシステム制御回路０１０７はホスト０１０２からの書き込み順(order)に、ページ０３０２一つごとに不揮発性メモリ０１０８を分散させて書き込む。図１１（ａ）に示すように、order=[1] １１０１のデータは、不揮発性メモリ(1,Way_S)０１０８のブロック(BLK)の番号が PBA_Sのページ(PG)の番号が１である図１０のページ１００１に格納され、order=[2] １１０２のデータは、次のチャネル(Ch.2)に属する不揮発性メモリ(2,Way_S)の同一ブロック番号(PBA_S)、且つ同一ページ番号(1)のページ１００２に格納される。
【００４３】
以下同様に、order=[i] １１０３のデータは、不揮発性メモリ(i,Way_S)の同一ブロック番号(PBA_S)の同一ページ番号(1)のページ１００３に格納される。次のorder=[i+1]のデータは、次のウェイ(Way_S+1)のブロック番号(PBA_(S+1))、同一ページ番号(1)に格納される。以下、order=[iP]のデータまで順番に各不揮発性メモリの各ブロックの同一ページ番号に格納される（１１０４、１００４）。ただし、iPは一つのPAunit_ctrlに割り当てられる不揮発性メモリ０１０８の数を表し、iP=i×(Way_E-Way_S+1)である。order=[iP]以降は、各不揮発性メモリ０１０８の次のページ番号のページ１００５などに、order=[1]〜[iP]と同じ順番にデータが格納される。以上のような規則で格納されるため、ページの番号は計算することもできる。
【００４４】
以上ではグループの番号が1のデータを説明した。この場合、order=[1]のデータはチャネル(Ch.1)の不揮発性メモリ０１０８に格納されたが、グループの番号が異なるデータに関しては、order=[1]のデータを書き込む不揮発性メモリ０１０８のチャネルの番号を異なるように配置する。例えば、グループの番号が３のデータを格納する場合、図１１（ａ）のNVM chip１１０５に対して図１１（ｂ）のNVM chip１１０６に示すようにorder=[1]のデータはチャネル(Ch.3)の不揮発性メモリ(3,Way_S’)から書き込まれる。以下後続のデータorder=[2],[3],…は、チャネル(ch.4,5,…)の順に格納される。
【００４５】
一般的には、図１２に示すように、グループの番号がAのorder=[1]のデータの格納先の不揮発性メモリ０１０８が属するチャネル(Ch.)０２１０の番号は、StCh_GrAで表され、この値はStCh_GrA=A%i+1(Aをチャネル０２１０の個数iで割った時の余り+1)で決定される。グループの番号が１の場合はStCh_Gr1 １２０１となり、グループの番号が３の場合はStCh_Gr3 １２０２となる。ここで、グループの番号の異なるデータに関してウェイ(Way_SとWay_S’)、ブロック(PBA_SとPBA_S’)は必ずしも異なる必要はない。以上のような規則で格納されるため、チャネルの番号は計算することもできる。
【００４６】
サーバ０１０１がグラフ処理を行う際のメモリサブシステム０１０４の処理を図１３〜図１９を用いて説明する。
＜Ｆ．グラフ解析におけるメモリサブシステム制御回路の処理＞
（１）メモリサブシステムの制御に必要なデータの入力
グラフ解析を実行するホスト０１０２は、グラフ解析の前に、メモリサブシステム０１０４の制御に必要なデータを、メモリサブシステム０１０４のレジスタ０２０６に書き込む。メモリサブシステム０１０４の制御に必要なデータは、ホスト０１０２による論理アドレスの管理単位であるLAunit_host、スーパーステップやグループの数、グラフデータのデータサイズ、（異なるグラフを区別するために必要な）グラフデータの識別子、グラフの頂点数や辺の数などであり、グラフの最短経路探索の場合は、最短経路を求めたい２頂点、すなわち、始点と終点を特定する情報なども含まれる。
（２）データ書き込み処理
データの書き込みにおけるメモリサブシステム制御回路０１０７の処理を、図１３、１４に基づいて説明する。
【００４７】
図１３に書き込み処理のフローチャートを示す。メモリサブシステム制御回路０１０７内のメモリアクセス制御回路０２０１は、ホスト０１０２の管理するメモリ０１０６内に格納されたデータ書き込み命令と、書き込みデータのスーパーステップの番号と、グループの番号と、データ種類識別子と、グループ内の書き込み順をメモリサブシステム０１０４に転送する。必要に応じて、上記と合わせて、書き込みデータと、書き込みデータの論理アドレスと、書き込みデータのサイズも転送する。次に、メモリアクセス制御回路０２０１は、書き込み命令をコマンドバッファ０２０２へ格納し、スーパーステップの番号と、グループの番号と、データ種類識別子と、グループ内の書き込み順の番号をタグバッファ０２０５に格納する。なお、書き込み順の番号はタグバッファ０２０５以外のバッファに格納してもよい。メモリアクセス制御回路０２０１は、必要に応じて、書き込みデータをデータバッファ０２０３に格納し、書き込みデータの論理アドレスと、書き込みデータのサイズをアドレスバッファ０２０４に格納する(Step1(Send to MSS)１３０１)。
次に、ガーベッジコレクション排除制御ブロック０２０７は、バッファからグループ内の書き込み順の番号を読み、ホスト０１０２が定めた論理アドレスの管理単位であるLAunit_hostをレジスタ０２０６から読む。この結果、もし次に書き込むデータの論理アドレスLAが、ホスト０１０２の定めた論理アドレスLAの管理単位であるLAunit_hostの先頭となる場合(Step2(LAunit_host full)１３０２がYes)、Step3 １３０３へ進む。一方、もし、次に書き込むデータの論理アドレスが、LAunit_hostの先頭とならない場合(Step2(LAunit_host full)１３０２がNo)、Step8 １３０８へ進む。例えば、ページのデータサイズが8kBであり、LAunit_hostが1MBであるとすると、1MB/8kB=128となるので、order=[128×n+1](nは自然数)の場合はStep2 １３０２のLAunit_host fullがYesとなり、それ以外はNoとなる。
【００４８】
次に、Step3 １３０３では、ガーベッジコレクション排除制御ブロック０２０７がバッファからグループ内の書き込み順の番号を読み、ガーベッジコレクション排除制御ブロック０２０７が定めた物理アドレスの管理単位であるPAunit_ctrlをレジスタ０２０６から読む。この結果、もし次に書き込むデータが、PAunit_ctrlの先頭となる場合(Step3(PAunit_ctrl full)１３０３がYes)、Step4 １３０４へ進む。一方、もし、次に書き込むデータが、PAunit_ctrlの先頭とならない場合(Step3(PAunit_ctrl full)１３０３がNo)、Step7 １３０７へ進む。例えば、ページのデータサイズが8kBであり、PAunit_ctrlが32MBであるとすると、32MB/8kB=4096となるので、order=[4096×n+1](nは自然数)の場合、Step3 １３０３のPAunit_ctrl fullはYesとなり、それ以外はNoとなる。
次に、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９へ読み出し命令を送り、メモリ０１０９に格納されたテーブル(PBA_ST)１４００を読み出す(Step4(Read PBA_ST)１３０４)。図１４に示すように、テーブル(PBA_ST)１４００は、各ウェイ、ブロック(Way, PBA)１４０１に対して物理ブロックの状態(Status of PBA)１４０２と、消去回数(Cycle_erase)１４０３を記録する。物理ブロックの状態(Status of PBA)１４０２は、「０:使用不可(不良ブロック)」、「１:データ消去済」、「２:ホストに読まれたデータなし(読み出し前)」、「３:ホストに読まれたデータあり(読み出し中)」、「４:未読データ無し(読み出し完)」、「５:データ書き込み先として確保済み」などが記録される。
【００４９】
ガーベッジコレクション排除制御ブロック０２０７は、テーブル(PBA_ST)１４００の物理ブロックの状態(Status of PBA)１４０２を参照し、データ消去済となっているブロックを新たなPAunit_ctrlに割り当てる(Step5(Alloc. PAunit_ctrl)１３０５)。
Step5 １３０５の後、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータの書き込み命令を発行し、メモリ０１０９に格納されたテーブル(PBA_ST)１４００の物理ブロックの状態(Status of PBA)１４０２を更新し、新たに割り当てられた物理ブロックを「５：データ書き込み先として確保済み」とする。また、ガーベッジコレクション排除制御ブロック０２０７は、同様にDRAM制御回路０２０９にデータの書き込み命令を発行し、図９（ａ）に示されたテーブル(GR_PA)０９００を更新し、Step5 １３０５で新たに確保されたPAunit_ctrlを記録する。また、もし書き込みデータの論理アドレスがアドレスバッファ０２０４に格納されていた場合は、図９（ｂ）に示されたテーブル(LA_GR)０９１０も更新する(Step6(Update table)１３０６)。
【００５０】
Step7 １３０７では、書き込みデータの論理アドレスがアドレスバッファに格納されていた場合、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータの書き込み命令を発行し、メモリ０１０９に格納された図９（ｂ）に示されたテーブル(LA_GR)０９１０を更新する。
【００５１】
次に、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９へ読み出し命令を送り、メモリ０１０９に格納されたテーブル(GR_PA)０９００を読み出す(Step8(Read GR_PA)１３０８)。
Step8 １３０８の後、ガーベッジコレクション排除制御ブロック０２０７は、タグバッファ０２０５からスーパーステップの番号と、グループの番号と、データ種類識別子を読み出し、バッファからグループ内の書き込み順の番号を読み出す。また、ガーベッジコレクション排除制御ブロック０２０７は、Step8 １３０８で読み出したテーブル(GR_PA)０９００を参照し、データ書き込み先の不揮発性メモリのウェイとブロックなど及びページを決定する(Step9(Det. Chip_Page)１３０９)。
最後に、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ書き込み命令を発行し、ホスト０１０２からのデータ書き込み命令をコマンドバッファ０２０２からメモリ０１０９に転送し、スーパーステップの番号とグループの番号とデータ種類識別子をタグバッファ０２０５からメモリ０１０９に転送し、グループ内の書き込み順(order)をバッファ０５からメモリ０１０９に転送する。これらと一緒に、ガーベッジコレクション排除制御ブロック０２０７は、データ書き込み先の不揮発性メモリ０１０８のウェイとブロックなどとページなどもメモリ０１０９に転送する。また、必要に応じて、ガーベッジコレクション排除制御ブロック０２０７は、書き込みデータをデータバッファ０２０３からメモリ０１０９に転送し、書き込みデータの論理アドレスと書き込みデータのサイズをアドレスバッファからメモリ０１０９に転送する(Step10(To DRAM)１３１０)。
（３）データ読み出し処理
データの読み出しにおけるメモリサブシステム制御回路０２０７の処理を、図１５に基づいて説明する。
【００５２】
メモリサブシステム制御回路０１０７内のメモリアクセス制御回路０２０１は、ホスト０１０２の管理するメモリ０１０６内に格納されたデータ読み出し命令と、読み出しデータのスーパーステップの番号と、グループの番号と、データ種類識別子をメモリサブシステム０１０４に転送する。次に、メモリアクセス制御回路０２０１は、読み出し命令をコマンドバッファ０２０２へ格納し、スーパーステップの番号とグループの番号とデータ種類識別子をタグバッファ０２０５に格納する(Step1(Send to MSS)１５０１)。もしくは、まず、メモリアクセス制御回路０２０１は、ホスト０１０２の管理するメモリ０１０６内に格納されたデータ読み出し命令及び読み出しデータの論理アドレスとデータサイズをメモリサブシステム０１０４に転送し、その後、読み出しデータの論理アドレスと、読み出しデータのサイズをアドレスバッファ０２０４に格納する(Step1(Send to MSS)１５０１)。
【００５３】
次に、ガーベッジコレクション排除制御ブロック０２０７は、タグバッファを参照し、読み出しデータのスーパーステップの番号と、グループの番号と、データ種類識別子がホスト０１０２から転送されているか確認する(Step2(SS&GR?)１５０２)。その結果、これらがタグバッファ０２０５に格納されていればStep4 １５０４に進み(Step2 １５０２がYes)、格納されていなければStep3 １５０３に進む(Step2 １５０２がNo)。
Step3 １５０３では、ガーベッジコレクション排除制御ブロック０２０７が、アドレスバッファ０２０４から読み出しデータの論理アドレスと読み出しデータのサイズを読み出す。その後、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ読み出し命令を発行して図９（ｂ）に示されたテーブル(LA_GR)０９１０をメモリ０１０９から読み出し(Step3(Read LA_GR for Read Data)１５０３)、テーブル(LA_GR)０９１０に基づいて読み出しデータのスーパーステップの番号とグループの番号とデータ種類識別子を特定し、タグバッファ０２０５へ格納する。
【００５４】
次に、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ読み出し命令を発行し、図９（ａ）に示されたテーブル(GR_PA)０９００をメモリ０１０９から読み出す(Step4(Read GR_PA for Read Data)１５０４)。
【００５５】
ガーベッジコレクション排除制御ブロック０２０７は、タグバッファ０２０５からスーパーステップの番号と、グループの番号と、データ種類識別子を読み出す。そして、ガーベッジコレクション排除制御ブロック０２０７は、Step4 １５０４で読み出したテーブル(GR_PA)０９００を参照し、データ読み出し先の不揮発性メモリのウェイとブロック及びページを決定する(Step5(Det. Chip_Page)１５０５)。
【００５６】
最後に、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ書き込み命令を発行し、ホスト０１０２からのデータ読み出し命令をコマンドバッファからメモリ０１０９に転送し、スーパーステップの番号とグループの番号とデータ種類識別子をタグバッファ０２０５からメモリ０１０９に転送する。これらと一緒に、ガーベッジコレクション排除制御ブロック０２０７は、データ読み出し先の不揮発性メモリ０１０８のウェイとブロックなどとページなどもメモリ０１０９に転送する。また、必要に応じて、ガーベッジコレクション排除制御ブロック０２０７は、読み出しデータの論理アドレスとデータサイズをアドレスバッファ０２０４からメモリ０１０９に転送する(Step6(To DRAM)１５０６)。
（４）データ消去処理
データの消去におけるメモリサブシステム制御回路０１０７の処理を図１６に基づいて説明する。
【００５７】
メモリサブシステム制御回路０１０７内のメモリアクセス制御回路０２０１は、ホスト０１０２の管理するメモリ０１０６内に格納されたデータ消去命令及び消去するデータのスーパーステップの番号とグループの番号とデータ種類識別子をメモリサブシステム０１０４に転送する。次に、メモリアクセス制御回路０２０１は消去命令をコマンドバッファ０２０２へ格納し、スーパーステップの番号とグループの番号とデータ種類識別子をタグバッファ０２０５に格納する(Step1(Send to MSS)１６０１)。もしくは、まず、メモリアクセス制御回路０２０１は、ホスト０１０２の管理するメモリ０１０６内に格納されたデータ消去命令及び消去するデータの論理アドレスとデータサイズをメモリサブシステム０１０４に転送し、その後、消去するデータの論理アドレスとデータサイズをアドレスバッファに格納する(Step1(Send to MSS)１６０１)。
【００５８】
次に、ガーベッジコレクション排除制御ブロック０２０７は、タグバッファ０２０５を参照し、消去するデータのスーパーステップの番号とグループの番号とデータ種類識別子がホスト０１０２から転送されているか確認する(Step2(SS&GR?)１６０２)。その結果、これらがタグバッファ０２０５に格納されていればStep4 １６０４に進み(Step2  １６０２がYes)、格納されていなければStep3 １６０３に進む(Step2 １６０２がNo)。
Step3 １６０３では、ガーベッジコレクション排除制御ブロック０２０７は、アドレスバッファ０２０４から消去するデータの論理アドレスと、データサイズを読み出す。その後、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ読み出し命令を発行し、図９（ｂ）に示されたテーブル(LA_GR)０９１０をメモリ０１０９から読み出し(Step3(Read LA_GR for Erase Data)１６０３)、消去するデータのスーパーステップの番号とグループの番号とデータ種類識別子を特定してタグバッファ０２０５へ格納する。
【００５９】
次に、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ読み出し命令を発行し、図９（ａ）に示されたテーブル(GR_PA)０９００をメモリ０１０９から読み出す(step4(Read GR_PA for Erase Data)１６０４)。
【００６０】
ガーベッジコレクション排除制御ブロック０２０７は、タグバッファ０２０５からスーパーステップの番号とグループの番号とデータ種類識別子を読み出す。また、ガーベッジコレクション排除制御ブロック０２０７は、Step4 １６０４で読み出したテーブル(GR_PA)０９００を参照してデータ消去先の不揮発性メモリのウェイ及びブロックなどを決定する(Step5(Det. Chip_BLK)１６０５)。
【００６１】
ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９にデータ書き込み命令を発行し、ホスト０１０２からのデータ消去命令を、コマンドバッファからメモリ０１０９に転送し、スーパーステップの番号とグループの番号とデータ種類識別子をタグバッファからメモリ０１０９に転送する。これらと一緒に、ガーベッジコレクション排除制御ブロック０２０７は、データ消去先の不揮発性メモリ０１０８のウェイとブロックなどもメモリ０１０９に転送する。また、必要に応じて、ガーベッジコレクション排除制御ブロック０２０７は、消去するデータの論理アドレスとデータサイズをアドレスバッファ０２０４からメモリ０１０９に転送する(Step6(To DRAM)１６０６)。
（５）不揮発性メモリにおけるデータ処理
不揮発性メモリ０１０８におけるメモリサブシステム制御回路０１０７のデータ処理を図１７〜１９に基づいて説明する。
【００６２】
図１７に上記（２）〜（４）の処理によりメモリ０１０９へ書き込まれた書き込み命令、読み出し命令、消去命令を不揮発性メモリ０１０８に適用する処理のフローチャートを示す。まず、ガーベッジコレクション排除制御ブロック０２０７は、各チャネル０２１０の不揮発性メモリ制御回路０２０８へ、不揮発性メモリ０１０８の状態を確認する命令を発行する。命令を受け、各チャネル０２１０の不揮発性メモリ制御回路０２０８は、それぞれのチャネル０２１０に属する各不揮発性メモリ０１０８に接続されたレディービジー線０２１３の信号を読み、処理が行われていない不揮発性メモリ０１０８の番号(Ch, Way)をガーベッジコレクション排除制御ブロック０２０７へ返す(Step1 (Find idle chip)１７０１)。
Step1 １７０１の結果を受け、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に読み出し命令を発行し、メモリ０１０９から処理が行われていない不揮発性メモリ０１０８宛の書き込み命令と読み出し命令と消去命令を読み出す。ガーベッジコレクション排除制御ブロック０２０７は、１つの不揮発性メモリ０１０８あたり、優先度の最も高い命令を１つ選び出し(Step2(Det. priority)１７０２)、その命令を各不揮発性メモリ制御回路０２０８に送る(Step3(CMD to NVMC)１７０３)。不揮発性メモリ０１０８へのデータ書き込み命令の場合、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に読み出し命令を発行し、メモリ０１０９から書き込むデータを読み出し、書き込み命令と一緒に不揮発性メモリ制御回路０２０８に送る。
各チャネル０２１０の不揮発性メモリ制御回路０２０８は、各不揮発性メモリ０１０８における処理が終わったことを確認次第、処理終了をガーベッジコレクション排除制御ブロック０２０７へ通知する(Step4(Receive from NVMC)１７０４)。データ読み出しの場合、読み出されたデータも、不揮発性メモリ制御回路０２０８から、ガーベッジコレクション排除制御ブロック０２０７へ送られる。ガーベッジコレクション排除制御ブロック０２０７は、読み出されたデータをメモリアクセス制御回路０２０１へ送る。または、必要に応じて、ガーベッジコレクション排除制御ブロック０２０７ は、DRAM制御回路０２０９に書き込み命令を発行し、メモリ０１０９へ読み出されたデータを転送する。その後、メモリアクセス制御回路０２０１は読み出されたデータをホスト０１０２へ送る。
【００６３】
最後に、ガーベッジコレクション排除制御ブロック０２０７は、メモリ０１０９に格納されたテーブルを更新する(step5(Update table)１７０５)。更新されるテーブルは、不揮発性メモリ０１０８での処理内容によって異なる。以下読み出し、書き込み、消去処理に分けて説明する。
（ｉ）データ読み出しにおけるテーブルの更新
ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に読み出し命令を発行し、メモリ０１０９に格納された図１４に示すテーブル(PBA_ST)１４００を読み出す。そして、データの読み出し先の不揮発性メモリ０１０８のウェイ、ブロック(Way, PBA)１４０１に対応するブロックの状態(Status of PBA)１４０３を「２：読み出し前」から「３：読み出し中」または「３：読み出し中」から「４：読み出し完」などに更新する。その後、ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に書き込み命令を発行し、更新されたテーブル(PBA_ST)１４００をメモリ０１０９に書き戻す。
（ii）データ書き込みにおけるテーブルの更新
ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に読み出し命令を発行し、メモリ０１０９に格納された図１８に示すテーブル(GR_PTR)１８００と、書き込まれるデータのスーパーステップの番号と、グループの番号と、データ種類識別子と、グループ内の書き込み順を読み出す。以上の情報を用いて、ガーベッジコレクション排除制御ブロック０２０７は、テーブル(GR_PTR)１８００の書き込みページポインタ(Ptr)１８０４のうち、書き込みデータのスーパーステップ(S.S.)１８０１の番号とグループ(Gr.)１８０２の番号とデータ種類識別子(IDX)１８０３に対応するページポインタ１８０４のP_R か P_Gを更新する。P_R(1,1)１８０５のRはデータ種類識別子１８０３のResultを表し、(1,1)はスーパーステップ１８０１の番号が１であってグループの番号が１であることを表す。P_G(1,1)１８０６のGはデータ種類識別子１８０３がGraphであることを表す。ここで、図１９にテーブル(GR_PTR)１８００の書き込みページポインタ１８０４と不揮発性メモリ０１０８の物理ブロック０３０１及びページ０３０２との関係を示す。図１９に示すように、スーパーステップが k、グループが１の解析結果データにおける書き込みページポインタP_R(k,1)１９０１が、不揮発性メモリ(1,Way_S)０１０８のブロック(BLK PBA_S)の最後のページ(PG N_pg)１９０２となるとき、このスーパーステップk、グループ１の解析結果データは既にP_R(k,1)ページ分書き込み済みであることを示す。1ページ分のデータを書き込むごとに、ガーベッジコレクション排除制御ブロック０２０７は、このP_R(k,1)を1ずつ増やす。
(iii)データ消去におけるテーブルの更新
ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に読み出し命令を発行し、テーブル(GR_PA)０９００とテーブル(LA_GR)０９１０とテーブル(PBA_ST)１４００を読み出し、消去されるデータのスーパーステップの番号とグループの番号とデータ種類識別子を読み出す。ガーベッジコレクション排除制御ブロック０２０７は、あるスーパーステップ及びグループの番号のデータが全て消去された場合、テーブル(GR_PA)０９００及びテーブル(LA_GR)０９１０を更新する。また、テーブル(PBA_ST)１４００の対応するブロックの状態(Status of PBA)１４０３を「１：消去済み」に更新する。ガーベッジコレクション排除制御ブロック０２０７は、DRAM制御回路０２０９に書き込み命令を発行し、更新されたテーブル(GR_PA)０９００、テーブル(LA_GR)０９１０、テーブル(PBA_ST)１４００をメモリ０１０９に書き戻す。
＜Ｇ．効果のまとめ＞
以上説明した構成及び処理により得られる主な効果は以下の通りである。
【００６４】
大容量で安価なメモリを使用可能とすることで、大規模データを処理する際に必要な大規模なメモリを安価に提供でき、かつ、その場合でもメモリに対して高速なデータアクセスを行うことができる。すなわち、大規模データの高速処理を行うサーバにおいて、DRAMなどよりビットコストが安価なNANDフラッシュメモリなどの不揮発性メモリにデータを格納し、かつ、その場合でもデータに対応したタグ番号を用いて不揮発性メモリを制御することによって、不揮発性メモリにおけるガーベッジコレクションを排除し、高速なデータアクセスが可能になる。さらに、データ処理を実行するホストがデータのアドレスやサイズを指定しなくても、タグ番号を指定するだけでデータを不揮発性メモリへ書き込んだり、不揮発性メモリからデータを読み出してホストに送ったり、不揮発性メモリのデータを消去することができる。
【００６５】
また、以上の説明では、データ処理を行うホスト０１０２、不揮発性メモリ０１０８、及び不揮発性メモリ０１０８を管理するメモリサブシステム制御回路０１０７から構成されるサーバ０１０１の例を挙げたが、サーバ０１０１はデータ解析及び不揮発性メモリ０１０８を管理するホスト０１０２、不揮発性メモリ０１０８、及びホスト０１０２の管理にしたがうメモリサブシステム制御回路とから構成してもよい。また、大規模グラフを頂点番号に応じて複数のグループ(Gr.)に分割して解析する例を挙げたが、取り扱う大規模データ処理は上記の例に限定されるものではなく、MapReduce処理において、Keyに応じて(keyとvalueで制御された)大規模データを複数のグループ(Gr.)に分割して、上記処理と同様にメモリ処理を行ってもよい。また、ソースコード上で大きな配列を確保する大規模データベース処理アプリケーションにおいて、同一配列を同一グループ(Gr.)とみなして上記メモリ処理を実行しても良く、また、上記処理の適用範囲は、大規模データベースの検索及びデータ抽出などを行う場合も含まれる。そして、これらの処理においても大規模データを高速に読み書きできるため、大規模データ処理を高速化できる。
【００６６】
以上、添付図面を参照して具体的に説明したが、好ましい実施の形態は以上の説明に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【符号の説明】
【００６７】
０１０１  サーバ
０１０２  ホスト
０１０３  インターコネクト
０１０４  メモリサブシステム(MSS)
０１０５  情報処理回路(CPU)
０１０６、０１０９  メモリ(DRAM)
０１０７  メモリサブシステム制御回路(MSC)
０１０８  不揮発性メモリ(NVM)
０２０１  メモリアクセス制御回路(DMAC)
０２０２  コマンドバッファ(C-BF)
０２０３  データバッファ(D-BF)
０２０４  アドレスバッファ(A-BF)
０２０５  タグバッファ(T-BF)
０２０６  レジスタ(RG)
０２０７  ガーベッジコレクション排除制御ブロック(GCLS_CB)
０２０８  不揮発性メモリ制御回路(NVMC)
０２０９  DRAM制御回路(DRAMC)
０２１０  チャネル(Ch 1〜i)
０２１１  ウェイ(Way 1〜j)
０３０１  ブロック(BLK)
０３０２  ページ(PG)
０９００  テーブル(GR_PA)
０９１０  テーブル(LA_GR)
１４００  テーブル(PBA_ST)
１８００  テーブル(GR_PTR)
【図１】
0005969130.tif 000002
【図２】
0005969130.tif 000003
【図３】
0005969130.tif 000004
【図４】
0005969130.tif 000005
【図５】
0005969130.tif 000006
【図６】
0005969130.tif 000007
【図７】
0005969130.tif 000008
【図８】
0005969130.tif 000009
【図９】
0005969130.tif 000010
【図１０】
0005969130.tif 000011
【図１１】
0005969130.tif 000012
【図１２】
0005969130.tif 000013
【図１３】
0005969130.tif 000014
【図１４】
0005969130.tif 000015
【図１５】
0005969130.tif 000016
【図１６】
0005969130.tif 000017
【図１７】
0005969130.tif 000018
【図１８】
0005969130.tif 000019
【図１９】
0005969130.tif 000020