半導体記憶装置、情報処理装置
【課題】処理量が少ないデータ転送が可能なメモリシステムを提供する。
【解決手段】半導体記憶装置は、メモリ(14)と、制御部(12, 13)を含む。メモリは、データと、データを特定するための検索キーとデータが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持する。制御部は、第1コマンドを受け取ると、第1コマンドが検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを出力し、第1コマンドが実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを出力する。
【解決手段】半導体記憶装置は、メモリ(14)と、制御部(12, 13)を含む。メモリは、データと、データを特定するための検索キーとデータが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持する。制御部は、第1コマンドを受け取ると、第1コマンドが検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを出力し、第1コマンドが実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを出力する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明の実施形態は、半導体記憶装置、情報処理装置に関する。
【背景技術】
【0002】
連想メモリが知られている。連想メモリではないメモリに対しては、ホストは、メモリ中のデータを、このデータが記憶されているメモリ中の領域のアドレスにより特定する。一方、連想メモリでは、データに関連付けられているメタデータ(キー)を指定してメモリ中のデータを特定する。複数のメタデータに対する論理演算を通じて読み出されるデータを特定することが考えられる。このような複数のメタデータに対する演算を含んだデータ読み出しは、演算等の処理の量が多い。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2002−279785号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
処理量が少ないデータ転送が可能な半導体記憶装置を提供しようとするものである。
【課題を解決するための手段】
【0005】
一実施形態によるメモリシステムは、半導体記憶装置は、メモリと、制御部を含む。メモリは、データと、データを特定するための検索キーとデータが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持する。制御部は、第1コマンドを受け取ると、第1コマンドが検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを出力し、第1コマンドが実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを出力する。
【図面の簡単な説明】
【0006】
【図1】第1実施形態に係るメモリシステムのブロック図。
【図2】メタデータテーブルのフォーマットを例示する図。
【図3】第1実施形態に係るメモリシステムの動作を示す図。
【図4】第1実施形態に係るメモリシステムの動作を示すフローチャート。
【図5】第2実施形態に係るメモリシステムのブロック図。
【図6】第2実施形態に係るメモリシステムの動作を示す図。
【図7】第2実施形態に係るメモリシステムの動作を示すフローチャート。
【図8】第2実施形態に係るメモリシステムの動作主体のバリエーションを示す図。
【図9】第3実施形態に係るメモリシステムのブロック図。
【図10】第3実施形態に係るメモリシステムの動作を示す図。
【図11】第3実施形態に係るメモリシステムの動作を示すフローチャート。
【図12】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【図13】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【図14】第4実施形態に係るメモリシステムがサポートするコマンドのパラメータの例を示す図。
【図15】第4実施形態に係るメモリシステムのブロック図。
【図16】第4実施形態に係るメモリシステムの一動作を示す図。
【図17】第4実施形態に係るメモリシステムの一動作を示す図。
【図18】第4実施形態に係るメモリシステムの一動作を示す図。
【図19】第4実施形態に係るメモリシステムの一動作を示す図。
【図20】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【図21】第4実施形態に係るメモリシステムの一動作を示す図。
【図22】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【発明を実施するための形態】
【0007】
実施形態の説明に先立ち、連想メモリについて簡単に説明する。連想メモリにアクセスするホストは、メモリにデータを書き込むために、データにメタデータ(キー)を付する。キーは、例えば、書き込み対象のデータ(書き込みデータ)中に含まれる単語、拡張子等の様々なタイプのものを含み得、複数個のキーを含み得る。ホストは、任意の方法により書き込みデータに付されるキーを生成する。ホストは、連想メモリへのデータ書き込みのために、例えばputコマンドを用いる。ホストは、putコマンドとともに、書き込みデータとキーを連想メモリに供給する。連想メモリは、書き込みデータに加えて、メタデータテーブルを保持している。メタデータテーブルは、キーに関する様々なデータの集合であり、1つのデータ(例えばファイル)データごとに1つのエントリを有し、このようなエントリを複数個含んでいる。メモリを制御するコントローラは、書き込みデータおよびキーを受け取ると、書き込みデータをメモリの空き領域に保持し、メタデータテーブル中の空きエントリにキーおよびこのキーとセットになっている書き込みデータが保持される領域を特定するためのアドレスを書き込む。各エントリには、有効/無効を示す情報が設けられており、無効のエントリを探すことによって空きエントリが見つかる。
【0008】
連想メモリからのデータの読み出しを望むホストは、例えばホストのユーザによって入力されたキーを用いてデータを特定する。データ読み出しには、例えばgetコマンドが用いられる。ホストは、getコマンドとともにキーを連想メモリに供給する。連想メモリは、この検索対象のキーを受け取ると、この検索キーを含んだエントリを検索する。そして、発見された全エントリ中に記載のアドレスに保持されている全てのデータをホストに送信する。
【0009】
連想メモリ中のデータの消去を望むホストは、deleteコマンドを使用する。ホストは、deleteコマンドとともにキーを連想メモリに供給する。連想メモリは、deleteコマンドを受け取ると、検索キーを含むエントリを見つける。連想メモリは、見つけられたエントリの有効/無効表示を無効にする。
【0010】
ユーザは、連想メモリに対して、1つの検索キーを直接的に用いる代わりに、1つまたは複数の検索キーに対する論理演算を用いて高度な検索を行なうことを望む場合がある。より具体的には、複数の検索キーを用いた検索があり得る。そのような検索では、メモリは、まず、1つ目の検索キーを含んだエントリを見つけ、見つかった全エントリの各々に対応するデータがホストに送信される。次に、メモリは、2つ目の検索キーを含んだエントリを見つけ、見つかった全エントリの各々に対応するデータをホストに送信する。ホストは、こうして全検索キーについてのデータを受け取る。次いで、ホストは、受け取ったデータの中から、全ての検索キーについてヒットしたデータを例えばAND演算により見つける。ここで言うAND演算とは、1つ目の検索キーについてのデータの集合と、2つ目の検索キーについてのデータの集合との共通集合を抽出する集合演算を指す。こうして、ホストは、検索対象の全てのキーを含んだデータを抽出する。
【0011】
以上のようなAND演算を含む論理演算の実行のために、ホストおよびメモリは大量の処理を必要とする。また、ホストでの論理演算の結果不要となるデータであってもメモリからホストに転送される。さらに、メモリにおいてヒットしたエントリに対応するデータが次々と長期間にわたってメモリからホストに転送されるので、その間、ホストにおける他の処理は遅延され得る。以上のように、処理負荷および効率の点で改善が望まれる。以上の説明は、AND演算に対するものであるが、その他の論理演算(例えばOR演算)等についても同様である。ここで言うOR演算とは、1つ目の検索キーについてのデータの集合と、2つ目の検索キーについてのデータの集合との和集合を抽出する集合演算を指す。後述のNOT演算についても同様で、検索キーについてのデータの補集合を指す。
【0012】
以下に、このような知見に基づいて構成された実施形態について図面を参照して説明する。なお、以下の説明において、略同一の機能及び構成を有する構成要素については、同一符号を付し、重複説明は必要な場合にのみ行う。また、以下に示すいずれの実施形態も、その実施形態の技術的思想を具体化するための装置や方法を例示するものであって、諸実施形態の技術的思想は下記の実例に限定されない。実施形態の技術的思想は、特許請求の範囲において、種々の変更を加えることができる。
【0013】
また、いずれの機能ブロック(モジュール)も、ハードウェア、コンピュータソフトウェアのいずれかまたは両者を組み合わせたものとして実現されることが可能である。このため、各ブロックがこれらのいずれでもあることが明確となるように、概してそれらの機能の観点から以下に説明する。このような機能が、ハードウェアとして実行されるか、またはソフトウェアとして実行されるかは任意である。当業者は、具体的な実施態様ごとに、種々の方法でこれらの機能を実現し得るが、いずれの実現の手法も実施形態の範疇に含まれる。また、各機能ブロックが、以下の具体例のように区別されていることは必須ではない。例えば、一部の機能が以下の説明において例示されている機能ブロックとは別の機能ブロックによって実行されてもよい。さらに、例示の機能ブロックがさらに細かい機能サブブロックに分割されていてもよい。どの機能ブロックによって特定されるかによって実施形態は限定されない。
【0014】
(第1実施形態)
図1は、第1実施形態に係るメモリシステム(半導体記憶装置、情報処理装置)のブロック図である。図1に示されるように、メモリシステム1は、ホスト装置(以下、単にホストと称する)2と通信する。ホスト2は、CPU(central processing unit)21、RAM(random access memory)22等を含んでいる。RAMは、例えばDRAM(dynamic random access memory)である。CPU21は、バス23によってRAM22と接続されている。CPU21は、ROM等のストレージからRAM22上に読み出された制御プログラムに従って所定の処理を実行する。各処理は、CPU21と制御プログラムによって実現されるモジュールによって実行される。モジュールには、少なくとも、コマンド生成モジュール24、論理演算モジュール26が含まれる。図では、便宜上、これらのモジュールは、ホスト2内においてCPU21およびRAMから独立して描かれている。
【0015】
メモリシステム1は、ハードウェア上の構成として、例えばプロセッサ、RAM、ROMを有する。動作の際、ROMに格納されている制御プログラム(命令)がRAM上に読み出される。プロセッサは、このプログラムに従って所定の処理を実行する。以下に述べるメモリシステム1中のメモリ以外の諸機能ブロックは、RAM上の制御プログラムに従ってCPUによって実行されることによって実現される。または、機能ブロックは専用のハードウェア(チップ等)によって実現されもよい。
【0016】
メモリシステム1は、ホストインターフェース11、ローカルコントローラ12、メモリコントローラ13、メモリ14を含んでいる。ホストインターフェース11は、バス23によってCPU21(またはCPU21およびプログラムにより実現されるホスト2中のインターフェースモジュール)と接続されている。ホストインターフェース11は、メモリシステム1とホスト2との間のインターフェースを取るのに必要なハードウェア、ソフトウェアからなる。ホストインターフェース11は、メモリシステム1とホスト2とが通信するのに必要な様々な取り決めを規定し、ホスト2(またはホスト2中のインターフェースモジュール)およびホストインターフェース11がと相互に認識可能な各種のコマンドの組を備えている。
【0017】
ホストインターフェース11は、DMA(direct memory access)コントローラ16を含んでいる。DMAコントローラ16は、プロセッサを介さずに何らかの2つの領域間でのデータの転送を司る。DMAコントローラ16は、実アドレスの指定を通じてデータを特定する。実アドレスとは、物理アドレスおよび論理アドレスのいずれかを指す。
【0018】
ローカルコントローラ12は、ホストインターフェース11と通信可能に接続されている。ローカルコントローラ12は、ホスト2から受け取ったコマンドを解析し、コマンドにより命じられる処理を実行するための様々なタスクを作成する。ローカルコントローラ12およびホストインターフェース11は、上記のput、get、deleteコマンドをサポートしており、さらに後述のコマンドを全てサポートしている。ローカルコントローラ12は、メモリコントローラ13と通信可能に接続されている。ローカルコントローラ12は、コマンド解析モジュール31、転送モジュール32、検索モジュール33、メモリ制御モジュール34、判断モジュール35等を含んでいる。各モジュールは、後述のローカルコントローラ12の対応する特定の処理の実行を担う。
【0019】
メモリコントローラ13は、ローカルコントローラ12からメモリ14が関与するタスクを受け取り、タスクを実行するための指示をメモリ14に送信する。すなわち、メモリコントローラ13は、メモリ14への特定のデータの書き込み、メモリ14からの特定のデータの読み出し、メモリ14中の特定のデータの消去を、メモリ14用のコマンドおよび処理手順に従って実行する。
【0020】
メモリコントローラ13は、CAM(content addressable memory(連想メモリ))モジュール17を含んでいる。CAMモジュール17は、ホストからの検索キーを用いるコマンドを実際に実行するためのデータの書き込み、読み出し、消去等をメモリ14に対して実行する。CAMモジュール17は、専用のハードウェアによって実現されてもよいし、メモリシステム1中のRAM上の制御プログラムにメモリシステム1中のプロセッサの動作が従うことを通じて実現されてもよい。メモリコントローラ13はまた、レジスタ/バッファ18を含んでいる。レジスタ/バッファ18は、メモリコントローラ13による何らかの処理の最中のデータを一時的に保持する。
【0021】
メモリ14は、メモリコントローラ13と通信可能に接続されている。メモリ14は、種々のタイプの不揮発性のメモリのうちの任意のものにより実現される。そのようなメモリには、例えばNAND型フラッシュメモリが含まれる。NAND型フラッシュメモリは、ページ単位でデータを書き込みおよび読み出す。ページは、複数の直列接続されたメモリセルの集合のメモリ空間からなり、固有の物理アドレスを割り当てられている。また、NAND型フラッシュメモリは、ブロック単位でデータを消去する。各ブロックは、連続する物理アドレスを有する複数のページからなる。各メモリセルは、いわゆる積層ゲート構造のMOSFET(metal oxide semiconductor field effect transistor)からなる。各セルトランジスタは、浮遊ゲート電極に蓄えられる電子の数に応じて閾値電圧が変化し、この閾値電圧の違いに応じた情報を記憶する。メモリ14はまたバッファを含んでいる。
【0022】
メモリ14がNAND型フラッシュメモリである場合、メモリ14は、SLC(single level cell)タイプであっても、MLC(multi level cell)タイプであってもよい。SLCタイプは、1つのセルが1ビットのデータを保持する。MLCタイプは、1つのセルが2ビット以上のデータを保持する。メモリ14は、1セル当たり1または複数ビットのデータを保持および読み出すことができるように構成されている。メモリ14は、1つに限らず複数のメモリチップを含んでいてもよい。チップごとに、または各チップ中の領域ごとに、SLCタイプまたはMLCタイプとしての使用が分けられていてもよい。
【0023】
メモリ14は、データ本体(ファイル等)を保持するファイル領域41と、メタデータを保持するCAMデータ領域42を含んでいる。CAMデータ領域42は、連想メモリの機能に用いられるメタデータテーブルを保持する。これらの領域は、例えばメモリ14中の利用可能な全ブロックのうちのいくつかを専用に用いることで実現することができる。
【0024】
メモリ14がNAND型フラッシュメモリである場合、書き込み済みのデータを上書きすることは禁止されている等の制約が存在する。そこで、ローカルコントローラ12からの指示を遂行するために、アドレスの変換を実行および管理する場合がある。具体的には、メモリコントローラ13は、ローカルコントローラ12から受け取ったデータに付された論理アドレスと、当該データを保持するファイル領域中の領域の物理アドレスと、の間の変換テーブルを作成し、これを用いる。変換テーブルは、論物変換テーブルなどとして当業者に知られている。メモリ41への上書きに相当する処理は、メモリコントローラ13によって、変換テーブルを用いて間接的に遂行される。
【0025】
メタデータテーブルは、例えば図2に示されるようなフォーマットを有する。図2に示されるように、メタデータテーブルは、複数のエントリを有する。各エントリは、個別のデータと関連付けられている。1つのエントリは、このエントリに対応するデータと関連付けられている1または複数のキーと、このデータが保持されているファイル領域41中の領域を特定するためのアドレスと、エントリの有効/無効表示を少なくとも含んでいる。キーとして、様々な要素を用いることができる。例えば、データに含まれる単語、データのファイル名、データの拡張子、書き換え頻度等が含まれる。
【0026】
次に、図3および図4を参照して、メモリシステム1の動作について説明する。各機能ブロックのさらなる詳細事項についても同時に記述する。
【0027】
図3は、第1実施形態に係るメモリシステムの動作を概略的に示している。図4は、第1実施形態に係るメモリシステムの動作を概略的に示しており、図3に対応するフローチャートである。図3および図4に示されるように、ホスト2は、key1、key2、key3を検索キーとして含むデータの検索の依頼を受けたとする。この依頼は、コマンドget(key1&key2&key3)の実行に相当する。このような依頼に対して、ホスト2のコマンド生成モジュール24は、この依頼を複数の別のコマンドに翻訳、すなわち、当該依頼を実現するためのコマンドを生成する。具体的には、コマンドfind(key1&key2&key3)と、コマンドread(ヒット/ミスビット列)に分解する。findコマンドは、コマンド中で指定されている検索キーをキーとして含むか否かを有効な全てのエントリごとに示したビットの集合の出力を命じるコマンドである。コマンドread(ヒット/ミスビット列)は、readコマンド中のビット列により特定されるエントリに対応するデータ(エントリ中に記載のアドレスにより特定されるファイル領域41中の領域中のデータ)をホスト2に送信することを命じるコマンドである。これらの2種のコマンドについては、後に詳述する。
【0028】
コマンド生成モジュール24は、find(key1&key2&key3)コマンドを、さらに、検索キーごとのfindコマンドに分解する。本例では、コマンドfind(key1)、find(key2)、find(key3)に分解する。得られたコマンドは、ホスト2中の制御モジュールの制御によって順次メモリシステム1に送信される。メモリシステム1は、ホストインターフェース11を介してローカルコントローラ12において、コマンドfind(key1)、find(key2)、find(key3)を受け取る(ステップS1)。なお、ローカルコントローラ12(コマンド解析モジュール31)によってfind(key1&key2&key3)コマンドが受け取られ、次いでコマンドfind(key1)、find(key2)、find(key3)に分解されてもよい。ホストインターフェース11およびローカルコントローラ12は、findコマンドおよびreadコマンドをサポートしている。
【0029】
ローカルコントローラ12(検索モジュール33、メモリ制御モジュール34)は、1つ目のfindコマンドを、メモリコントローラ13への処理を通じて実行する。より具体的には、メモリコントローラ13は、CAMモジュール17を通じて、find(key1)コマンドを得ると、CAMデータ領域42中のメタデータテーブル51にアクセスして検索キーkey1を含む有効なエントリを見つける。そして見つかった1または複数のエントリを特定するビット列を生成する(ステップS2)。このビット列の各ビットは1つのエントリに対応しており、対応するエントリのヒット/ミスを示しており、ヒット/ミスビット列53と称する。
【0030】
ヒット/ミスビット列53の生成は、例えば、まずメタデータテーブル51中の各エントリを順次CAMモジュール17に読み出すことと、各エントリ中の記述と検索キー(現在は、key1)との比較によって検索キーを含むエントリを発見することを含む。そのために、例えばCAMモジュール17は、メモリコントローラ13を通じてメモリシステム1中のRAMにエントリを順次読み出し、読み出されたエントリ中の記述と検索キーとを比較する。そして、ヒットしたエントリを特定する情報を順次例えばレジスタ/バッファ18で保持してヒット/ミスビット列53を生成する。図中の要素52は、各エントリについての有効/無効表示である。
【0031】
メモリ14のみでCAMの機能を実現できる場合がある。すなわち、メモリ14は内部にCAMデータ領域42中の全エントリに対する検索キー比較回路を持ち、メモリ14に検索キーを入力すると、メモリ14から検索キーが含まれるかの判定結果すなわちヒット/ミスビット列が出力される。このようなメモリ14が用いられる場合、CAMモジュール17は、検索キーをメモリ14に指定して返ってきたヒット/ミスビット列をレジスタ/バッファ18で保持すればよい。
【0032】
次に、CAMモジュール17は、ローカルコントローラ12(転送モジュール32)およびホストインターフェース11を通じて、ヒット/ミスビット列53をホスト2に送信する(ステップS3)。ホスト2は、受信した、1つ目の検索キーkey1についてのヒット/ミスビット列53を例えばRAM22上で保持する。
【0033】
次に、ローカルコントローラ12(判断モジュール35)は、全てのfindコマンドが実行されたかを判断する(ステップS4)。未処理のfindコマンドがあると、未処理のfindコマンドが無くなるまでステップS2、S3が繰り返される。本例では、CAMモジュール17は、2つ目のfindコマンド(すなわち検索キーkey2についてのfindコマンド)を、1つ目のfindコマンドと同様に実行する。実行の結果、検索キーkey2についてのヒット/ミスビット列53が生成され、ホスト1によって保持される。同様に、検索キーkey3についてのヒット/ミスビット列53が生成され、ホスト2によって保持される。
【0034】
全ての検索キーについてのfindコマンドの処理が終了すると、処理はステップS5に移行する。ステップS5において、論理演算モジュール26は、RAM22をワークメモリとして用いて、検索キーkey1、key2、key3の各々についてのヒット/ミスビット列53のANDを計算する。AND処理の結果、演算ヒット/ミスビット列を得る。演算ヒット/ミスビット列は、検索キーkey1、key2、key3の全てを含むメタデータテーブルのエントリを示すビット列からなる。
【0035】
次に、コマンド生成モジュール24は、コマンドread(hit/missビット列)を生成し、ホスト2はこのコマンドをメモリシステム1に送信する(ステップS5)。readコマンド中では、演算ヒット/ミスビット列が指定されている。ローカルコントローラ12(メモリ制御モジュール34)は、このreadコマンドを受け取ると、メモリコントローラ13を通じて、対応するエントリによって特定されるファイル領域41中の領域中のデータをホスト2に送信する(ステップS6)。すなわち、ホストインターフェース11を介してローカルコントローラ12によって受け取られたreadコマンドが解析され、解析の結果に基づいてメモリコントローラ13はCAMデータ領域42中の各エントリに対応するアドレスを順次読み出す。次いで、メモリコントローラ13は、読み出されたエントリ中のアドレスに対応するファイル領域41中の領域からデータを順次読み出し、ローカルコントローラ12およびホストインターフェース11を介してホスト2に転送する。
【0036】
ここまでの説明では、複数の検索キーがANDで結ばれている例を説明したが、ORの場合もANDの場合と同様に処理される。すなわち、OR検索の場合は、ホスト2でORの対象の検索キーについてのヒット/ミスビット列同士のOR演算が行なわれて、演算ヒット/ミスビット列が生成される。
【0037】
以上説明したように、第1実施形態によれば、論理演算を含んだデータ出力は、検索キーを含むエントリを示すヒット/ミスビット列のメモリシステム1からの出力、ホスト2による複数のビット列に対する論理演算、演算ヒット/ミスビット列に対応するデータのメモリシステム1からの出力として実行される。このため、各検索キーのみを含むデータ自体がメモリシステム1から出力されず、検索キーを含むエントリを特定するビット列および検索キーに対する論理演算を反映するデータのみが出力される。よって、データ転送量が減り、全体として高効率な検索キーによるデータ出力が可能となる。
【0038】
(第2実施形態)
第2実施形態も、第1実施形態と同じく、検索キーに対する論理演算を含んだ検索に関する。
【0039】
第2実施形態に係るメモリシステムの構成は、ローカルコントローラ12の構成を除いて第1実施形態と同じである。図5は、第2実施形態に係るメモリシステムのブロック図である。図5に示されるように、第2実施形態のローカルコントローラ12は、第1実施形態での全モジュールに加えて論理演算モジュール61を含んでいる。
【0040】
図6は、第2実施形態に係るメモリシステムの動作を概略的に示している。図7は、第2実施形態に係るメモリシステムの動作を概略的に示しており、図6に対応するフローチャートである。図6および図7に示されるように、ホスト2は、検索キーに対する論理演算を含むデータの検索の依頼を受けたとする。このような依頼には、具体例として、キーkey1とkey2のAND、またはkey1とkey2のOR、またはkey1のNOTを指定するgetコマンドが含まれる。依頼の受領に対して、コマンド生成モジュール24は、findコマンド、andコマンド(または論理演算に基づいてorコマンドまたはnotコマンド)、readコマンドに分割する。図6は、andコマンドを含むケースを示している。and(またはorまたはnot)コマンドについては後述する。ローカルコントローラ12は、得られたコマンドをホスト2から受け取る。(ステップS11)。または、ローカルコントローラ12(コマンド解析モジュール31)が検索キーに対する論理演算を含んだgetコマンドを受け取ってfindコマンド、andまたはorまたはnotコマンド、readコマンドに分割してもよい。
【0041】
まず、メモリコントローラ13(検索モジュール33)は、1または複数の検索キーについてfindコマンドにより指示される処理に類似の処理を行なう。すなわち、検索モジュール33は、CAMモジュール17に1つ目の検索キーkey1についてのヒット/ミスビット列の生成を指示する。CAMモジュール17は、ステップS2を実行して検索キーkey1についてのヒット/ミスビット列53を生成する。第2実施形態の場合、生成されたヒット/ミスビット列53は、レジスタ/バッファ18に保持され、メモリシステム1から出力されない(ステップS13)。
【0042】
次に、論理演算モジュール52(または判断モジュール35)は、続くコマンドの種類を識別する(ステップS14)。コマンドがreadコマンドである場合、処理はステップS22に移行する。論理演算コマンドがnotコマンドである場合、処理はステップS15に移行する。ステップS15において、論理演算モジュール61は、ヒット/ミスビット列53の全ビットを反転して、得られた演算ヒット/ミスビット列をレジスタ/バッファ18に保持する(ステップS15)。
【0043】
論理演算コマンドがandコマンドまたはorコマンドである場合、検索モジュール33は、検索キーkey1についてのfindコマンドに続いて、andコマンドまたはorコマンドを受け取る。andコマンドまたはorコマンドは、それぞれkey1とともにANDまたはOR演算の対象である検索キーkey2を指定している。andまたはorコマンドの受信により、検索モジュール33の指示に応答してCAMモジュール17は検索キーkey2についてのヒット/ミスビット列53を生成する(ステップS17)。論理演算モジュール61は、andコマンドおよびorコマンドのいずれを受信したかに基づいて、レジスタ/バッファ18に保持されている検索キーkey1についてのヒット/ミスビット列53と、key2についてのヒット/ミスビット列53に対してANDまたはOR演算を行なう。論理演算モジュール61は、得られた演算ヒット/ミスビット列で、レジスタ/バッファ18に保持されていた検索キーkey1についてのヒット/ミスビット列を更新する(ステップS18)。
【0044】
次に、受信した論理演算コマンドの終了/未終了が判断される(ステップS21)。全ての論理演算が完了していない場合、処理はステップS14に戻る。一方、全ての論理演算が完了していれば、メモリ制御モジュール34は、演算ヒット/ミスビット列についてのreadコマンドを実行する(ステップS22)。すなわち、メモリ制御モジュール34は、メモリコントローラ13を通じて、演算ヒット/ミスビット列により特定されるエントリ中のアドレスに対応するファイル領域41中の領域からデータを読み出す。読み出されたデータは、ローカルコントローラ12およびホストインターフェース11を介してホスト2に送信される。
【0045】
ここまでの説明では、ヒット/ミスビット列および演算ヒット/ミスビット列がいずれもレジスタ/バッファ18に保持される例を説明した。これは、メモリ14がCAM機能を備えていない例に対応し、図8(a)に対応する。右上がりのハッチングはヒット/ミスビット列を生成する要素を示し、右下がりのハッチングは演算ヒット/ミスビット列を生成する要素を示す。図8(a)の例では、ヒットミスビット列はメモリコントローラ13(CAMモジュール17)によって生成され、演算ヒット/ミスビット列はローカルコントローラ12(検索モジュール33)によって生成される。レジスタ/バッファ18にCAMモジュールの機能が統合されていてハードウェアとして実現されていてもよいし、CAMモジュール17がソフトウェアとして実現されていてもよい。一方、メモリ14がCAM機能を備えている場合、ヒット/ミスビット列はメモリ14によって生成され、例えばページバッファにおいて保持される。これは、図8(b)に対応する。図8(b)の例では、メモリ14がローカルコントローラ12およびメモリコントローラ13の指示に従って、各検索キーkeyについてのヒット/ミスビット列を生成し、これらに対する演算ヒット/ミスビット列がローカルコントローラ12によって生成され、レジスタ/バッファ18において保持される。
【0046】
第2実施形態の以上説明した以外の記述については、第1実施形態のものが全て当てはまる。
【0047】
以上述べたように、第2実施形態によれば、検索キーに対する論理演算を含んだデータ出力の指示は、メモリシステム1によって、検索キーを含むエントリの検索、ヒット/ミスビット列に対する論理演算、演算ヒット/ミスビット列に対応するデータ出力として実行される。これらの処理は全て、メモリシステム1において実行される。このため、個々の検索キーを含むデータ自体がメモリシステム1から出力されず、よって、データ転送量が減り、全体として高効率な検索キーによるデータ出力が可能となる。
【0048】
(第3実施形態)
第3実施形態は、複数のコマンドの並列処理に関し、第2実施形態に対して付加的に用いられる。
【0049】
第3実施形態に係るメモリシステムの構成は、ローカルコントローラ12の構成を除いて第1、第2実施形態と同じである。図9は、第3実施形態に係るメモリシステムのブロック図である。図9に示されるように、第3実施形態のローカルコントローラ12は、第2実施形態での全モジュールに加えてID識別モジュール71を含んでいる。
【0050】
図10は、第3実施形態に係るメモリシステムの動作を概略的に示している。図11は、第3実施形態に係るメモリシステムの動作を概略的に示しており、図10に対応するフローチャートである。図10および図11に示されるように、ホスト2のコマンド生成モジュール24は、各コマンドにIDを含める。IDは、図では、各コマンド中の最初に配置されているパラメータ(0または1を例示)である。特に、第1、第2実施形態のように検索キーに対する論理演算を含むgetコマンドがfindコマンド、論理演算コマンド、readコマンドの組合せにより実現される場合、1つのgetコマンド実行のための一連の複数コマンドに共通のIDが付される。図10では、論理演算コマンドは例としてandコマンドであり、より具体的には、第1のgetコマンド(ID=0)は、検索キーkey1、key3のANDを指定しており、第2のgetコマンド(ID=1)は、検索キーkey2、key4のANDを指定している。
【0051】
まず、コマンド生成モジュール24は、IDを指定しつつ、getコマンドによる処理を実現するための一連のコマンドを生成する。すなわち、まず、各getコマンド用の1つ目の検索キーkey1、2についてのfindコマンドを生成する。すなわち、ID=0およびkey1を指定するfindコマンドと、ID=1およびkey2を指定するfindコマンドを生成する。次いで、ID=0およびkey3を指定するandコマンドと、ID=1およびkey4を指定するandコマンドを生成する。さらに、ID=0を指定するreadコマンドと、ID=1を指定するreadコマンドを生成する。ホスト2は、これらのコマンドをメモリシステム1に送信する。これらのコマンドの送信の順番は、少なくとも同じIDを付されたコマンドについて、findコマンド、andコマンド、readコマンドの順が保たれていればよい。このように共通のIDを付された複数コマンドの送信順が保たれていれば、別IDを付されたコマンドが間に挿入されていても構わない。したがって、コマンドの生成の順序も、送信の順序が保たれていれば上記の例に限られない。
【0052】
ローカルコントローラ12は、生成されたコマンドを受け取る(ステップS31)。または、ローカルコントローラ12(コマンド解析モジュール31)が検索キーに対する論理演算を含んだ第1のgetコマンド(key1、key3)と第2のgetコマンド(キーkey2、key4)を受け取って、IDを指定しつつfindコマンド、andまたはorまたはnotコマンド、readコマンドに分割してもよい。この例の場合、コマンド解析モジュール31が、下位モジュールとしてID付与モジュールを含んでいてもよい。
【0053】
ID識別モジュール71は、受け取ったコマンドのIDを識別する(ステップS32)。次いで、コマンド解析モジュール31は、識別されたIDについて、コマンドの種類を識別する(ステップS33)。findコマンドが受け取られた場合、CAMモジュール17は、検索キーについてのヒット/ミスビット列53を生成する(ステップS41)。メモリ14がCAM機能を備えている場合は、ヒット/ミスビット列53はメモリ14により生成される。以下の記述でも、ヒット/ミスビット列53は、実施の態様に基づいてCAMモジュール17およびメモリ14の任意の方で生成されるものとする。次に、得られたヒット/ミスビット列53が、レジスタ/バッファ18中の指定されたID用の部分に保持される(ステップS42)。このように、レジスタ/バッファ18は、IDごとに相互に独立する部分を含んでいる。ステップS41、S42は、IDが特定されていることを除いて、第1、第2実施形態のステップS2、S13と同じである。
【0054】
notコマンドが受け取られた場合、論理演算モジュール61は、レジスタ/バッファ18中の指定されたID用の部分に保持されているヒット/ミスビット列53の全ビットを反転して、得られた演算ヒット/ミスビット列53をレジスタ/バッファ18中の指定されたID用の部分に保持する(ステップS44)。ステップS43、S44は、IDが特定されていることを除いて、第2実施形態のステップS15と同じである。
【0055】
andコマンドまたはorコマンドが受け取られた場合、CAMモジュール17は、検索キーについてのヒット/ミスビット列53を生成する(ステップS45)。論理演算モジュール61は、andコマンドおよびorコマンドのいずれを受信したかに基づいて、得られたヒット/ミスビット列53と、コマンドにて指定されているIDと同じID用のレジスタ/バッファ18の部分に保持されているヒット/ミスビット列とに対して、ANDまたはOR演算を行なう。論理演算モジュール61は、得られた演算ヒット/ミスビット列で、指定ID用のレジスタ/バッファ18の部分に保持されていたヒット/ミスビット列を更新する(ステップS46)。ステップS45、S46は、IDが特定されていることを除いて、第2実施形態のステップS17、S18と同じである。
【0056】
readコマンドが受け取られた場合、メモリ制御モジュール34は、指定されたIDについての演算ヒット/ミスビット列により特定されるエントリ中のアドレスからデータを読み出す(ステップS47)。読み出されたデータは、ローカルコントローラ12およびホストインターフェース11を介してホスト2に送信される。
【0057】
ステップS42、S44、S46、S47に続いて、判断モジュール35は、全てのコマンドに対する処理が完了したかを判断する(ステップS51)。未処理のコマンドがある場合、ステップS33、S41〜S47が実行される。図10の例では、ID=0および1の両方について、findコマンド、andコマンド、readコマンドが実行される。この結果、最終的に、検索キーkey1、3の両方を含むデータ、および検索キーkey2、4の両方を含むデータがホスト2に送信される。図10では、2つのIDが並行して処理される例を示すが、3つ以上のIDについてもここまでの説明と同じ原理に則って実行されることが可能である。
【0058】
以上述べたように、第3実施形態によれば、第2実施形態と同じく、検索キーに対する論理演算を含んだデータ出力の指示は、メモリシステム1によって、検索キーを含むエントリの検索、ヒット/ミスビット列に対する論理演算、演算ヒット/ミスビット列に対応するデータ出力として実行される。このため、第2実施形態と同じ利点を得られる。
【0059】
また、第3実施形態によれば、各コマンドがIDにより識別される。このため、第2実施形態のように、検索キーに対する論理演算を含んだデータ出力指示が複数のコマンドにより実行される場合であっても、検索キーに対する論理演算を含んだデータ出力を複数個並列に実行できる。
【0060】
(第4実施形態)
第4実施形態はコマンドの拡張に関する。
【0061】
図12および図13は、第4実施形態に係るメモリシステムおよびホストがサポートするコマンドを例示している。より具体的には、図12および図13は、第4実施形態に係るgetコマンドにより指定されるパラメータおよび例を示している。図12に示されるように、getコマンドは、パラメータとして、key、key_type、target、search_space、summary_types、ranking_method、size、bufferを含んでいる。または、図13に示されるように、パラメータsize、bufferに代えてhead、numberを含んでいる。
【0062】
パラメータkeyは、検索キーである。パラメータkeyとして、対応するデータに付されるメタデータだけでなく、拡張子を含んだファイル名とすることもできる。具体的には、例えばfile. wmv、file. txtのような形態で指定される。
【0063】
パラメータkey_typeは、検索キーの形態を明示しており、より具体的には検索キーが例えば文字データ、画像データ、音声データであることに基づいてそれぞれtext、image、audio等の文字列を含んでいる。パラメータkeyとしてファイル名を用いている場合、パラメータkey_typeとしてfilenameが指定される。
【0064】
また、パラメータkey_typeとしてcolorを指定することもできる。その場合、パラメータkeyとして、例えばvideo、image、text、書き換え頻度レベル(書き換え頻度レベル1、2、3、…)等が指定される。値colorは、カラー情報に関する値である。カラー情報とは、対象とするデータの書き換え頻度情報(そのデータ/ファイル等がユーザやホストによってどのくらいの頻度で更新されるかの情報)やデータの種類を示す情報である。例えば、カラー情報をエントリに含めておくことにより、複数のタイプのメモリ14がメモリシステム1に含まれている場合にカラー情報に基づいてデータを格納するメモリ14を適切に決定できる。具体的には、パラメータkey_typeにcolorが指定されている場合、パラメータkeyに設定されている値video、image、text等に基づいて、格納先がメモリコントローラ13により決定される。格納先の選択については後述する。
【0065】
パラメータtargetは、getコマンドが検索の対象とするデータの種類を明示する。データ種類の判定は、例えば拡張子により行なうことができる。パラメータtargetとして、具体的には、例えばwebpage、file、doc、image、audio、videoの指定が可能である。
【0066】
パラメータsearch_spaceは、getコマンドが検索の対象とする空間を指定しており、探索空間に基づいて例えばweb、disk、memory等の文字列を含んでいる。webはインターネットを介して閲覧可能な対象を探索空間として指定する。diskはメモリ14およびハードディスク、ネットワークディスク等の、ホストからアクセス可能なディスクを探索空間として指定する。どのディスクを検索するか、ディスク内のどのディレクトリを検索するかの指定も含まれ得る。memoryは、RAM22およびメモリ14を含むメモリアドレス空間が指定されていることを意味し、後述のDMAに使用する。探索空間の指定は、本実施形態に係るgetコマンドをメモリシステム1以外の領域を指定できるように適応させるためのものである。すなわち、上にも説明したように、パラメータtargetとして、webまたはメモリ14以外の領域を対象とするdiskまたはメモリを含むgetコマンドは、そのようなコマンドを受け取った構成素が、ウェブまたは構成素に接続されているハードディスク等のディスクまたはRAM等のメモリアドレス空間を探索空間として指定する。
【0067】
パラメータsummary_typesは、検索結果の要約の種類のリストを明示する。このパラメータは、検索結果のデータが大きい場合に、ホスト側で検索結果の吟味/取捨選択にかかる時間を軽減するために、各検索データを端的に表す要約データを付することができるようにするものである。パラメータranking_methodは、検索されたエントリに順位を付する際に順位が何に基づくかを指定する。一般に、複数の見つかったエントリが存在するため、ホスト2が所望のものを早い段階で取得できるように、エントリに順位を付する。パラメータsizeは、ホスト2中のバッファ(例えばRAM22により実現される)のサイズを明示する。パラメータbufferは、ホスト2中のバッファの先頭アドレスを指定する。メモリシステム1は、ヒットしたエントリにより特定される全データのうちで、パラメータranking_methodにより指定される基準に基づいて付された順位の高いものから順に、パラメータsizeによって指定されるサイズを越えない範囲で、パラメータbufferによって指定されるホスト2中のバッファに出力する。ホスト2に出力されない分のデータは、メモリシステム1中の例えばバッファ/レジスタ18において保持される。または、ホスト2に出力される分だけのデータが随時メモリ14から読み出されるとしてもよい。メモリシステム1は、ホスト2からこの最初の分のデータの受信が完了した旨の通知を受け取ると、続きの分のデータを出力する。
【0068】
パラメータheadは、パラメータranking_methodに指定される基準に基づいて順位が付された検索結果データの何番目からデータを受信するかを指定する。パラメータnumberは、検索結果データを最大何個受信するかを指定する。パラメータheadおよびnumberは、パラメータsizeおよびbufferとは異なり、出力を要求されるデータの大きさを順位付き検索結果の開始位置および個数によって指定する。例えば、パラメータhead=1, number=10とすれば検索結果データの1位から10位までが順に出力される。head=11, number=10として再度getコマンドを発行すれば11位から20位までの検索結果が得られる。
【0069】
図14は、第4実施形態に係るgetコマンド(図12、図13)のパラメータの一例を示している。2行目はwebから(search_space=web)"toshiba"に関連する(key="toshiba")画像を(target=image)、テキスト検索する(key_type=text)場合を示しており、検索結果の要約としては縮小版の画像であるサムネイル画像を(summary_types=[thumbnail])、検索結果の順位付けとしてはページランク(ranking_method=page_rank)を指定している。3行目はディスク領域の"/home/"で示されるディレクトリ以下から(search_space=disk"/home/")、"toshiba"に関連する(key="toshiba")ファイルを(target=file)、テキスト検索する(key_type=text)場合を示しており、検索結果の要約としてはファイルのサイズと更新日時を(summary_types=[file_size, modified_date]、検索結果の順位付けとしてはファイルの新しいものから古いものへ順位をつける(ranking_method=new_to_old)ことを指定している。4行目はある開始アドレスから一定サイズのデータを読み書きするDMA転送を検索コマンドとして実現する例で、メモリアドレス空間から(search_space=memory)、バイナリデータを(target=binary_data)、先頭アドレス0x0123abcd以上の(key>=0x0123abcd)アドレスを検索して(key_type=address)、アドレス順に出力する(ranking_method=address)ことを指定している。要約は出力しない(summary_types=null)。DMA転送については図17、18の説明に付随して後述する。
【0070】
第4実施形態に係るメモリシステムの構成は、ローカルコントローラ12の構成を除いて第1実施形態と同じである。図15は、第4実施形態に係るメモリシステムのブロック図である。図15に示されるように、第4実施形態のローカルコントローラ12は、第1実施形態での全モジュールに加えて順位計算モジュール81を含んでいる。第4実施形態は、第2、第3実施形態とも組み合わせることが可能である。このため、第4実施形態のローカルコントローラ12は、論理演算モジュール61(図5)およびID識別モジュール71(図9)を含んでいてもよい。
【0071】
図16は、第4実施形態に係るメモリシステムの一動作を概略的に示している。より具体的には、図16は、パラメータranking_methodの指定によるメモリシステム1の応答を示している。図16および図17に示されるように、CAMモジュール17は、第4実施形態に係るgetコマンドの受信に応答して、パラメータkeyによって指定される検索キーを含んだ有効エントリを見つける。次に、順位計算モジュール81は、パラメータranking_methodにより指定される基準に基づいて、ヒットしたエントリの順位を計算する。そして、ローカルコントローラ12は、各エントリに付された順位に基づいて、順位の小さい方から順に、対応するデータをホスト2に出力する。
【0072】
次に、図17〜図19を参照して、パラメータの種々の設定の例を説明する。図17、図18〜図19は、第4実施形態に係るメモリシステムの一動作を概略的に示している。図17、図18は、パラメータの設定を適切に組み合わせることによって、通常のデータ読み出し、すなわち読み出しデータのアドレスとサイズを指定したデータ読み出し(DMA転送による読み出しに相当)を、getコマンドによって実現できることを説明する図である。ただし、このようなgetコマンドを用いたアドレス指定によるデータ読み出しのために、CAMモジュール17はエントリが検索キーを含むかどうかの完全一致だけでなく、大小関係の判定もできるように構成されている。また、エントリはkeyとして論理アドレスを含んでいる。このようなデータ格納は、後述のputコマンドにより実現可能であり、また、そもそも各エントリは自明なキーとして論理アドレスを含むとしてもよい。論理アドレスは、ホスト2によりデータに割り当てられるアドレスである。
【0073】
図17に示されるように、ホスト2は、getコマンドを用いたアドレス指定によるデータ読み出しのために、パラメータkeyとして先頭アドレス以上を対象とすることを示すパラメータおよびパラメータranking_methodとしてaddressを指定するgetコマンドをメモリシステム1に供給する。ここでいう先頭アドレスは論理アドレスである。CAMモジュール17は、このようなgetコマンドの受信に応答して、検索キー、すなわち先頭アドレス以上の論理アドレスを有するエントリを見つける。次に、順位計算モジュール81は、ヒットしたエントリに対して論理アドレスの昇順に順位を付する(論理アドレスそのものを順位としてもよい)。そして、メモリコントローラ13は、エントリの順位に従って、対応するデータを出力する。これにより、先頭アドレスを含んだエントリのデータから論理アドレス順にデータが出力される。または、パラメータkey=allと(全エントリヒット)と指定し、パラメータranking_methodをaddr < 先頭アドレス ? ∞ : addrとすることによっても可能である。すなわち、論理アドレスが指定された先頭アドレスより小さければ順位を無限大として、先頭アドレス以上であればその論理アドレスを順位とする。このようなパラメータの指定により、先頭アドレスより小さいアドレスを含むエントリは順位が無限大になって、実質的にメモリシステム1から出力されない。以上のようなパラメータの指定により、getコマンドを用いたアドレス指定によるデータ読み出しが可能である。したがって、メモリシステム1に、DMAコントローラ16を介してDMAの機能をサポートさせることが可能である。
【0074】
また、図18に示されるように、図17のパラメータ指定のうち、ranking_methodを、例えばaddr %4 < 2 ? addr: 0と変える。このように指定すれば、図17を参照して説明したようにパラメータkeyにより指定された先頭アドレスにより特定されたエントリから、特定の個数ごとのエントリにのみ順位が付される。図の例では、4つごとに最初の2個のエントリのみが順位割付の対象とされる。このような指定を用いれば、例えば、画像データのうちの特定の領域のみを転送することができる(ブロック転送(BLT)に相当)。
【0075】
また、図19に示されるように、完全一致や大小関係では扱えない類似検索もできる。この場合は、パラメータkey=feature 1、パラメータranking_method=dinstanceと指定される。feature 1は、画像または動画データ等の任意の特徴を記述する具体的な特徴ベクトルである。feature 1の具体例として、例えば、グレースケール画像の場合、画素値ヒストグラム等が挙げられる。CAMモジュール17は、このようなgetコマンドの受信に応答して、検索キーを含むエントリを見つける。ただし、パラメータranking_method=dinstanceの場合、全エントリがヒットして扱われ、以下に述べるように、順位計算モジュール81は、distanceに基づいてヒットしたエントリに順位を付する。distanceは、例えば、検索キー(特徴ベクトル)と各エントリ中の特徴ベクトルを用いて算出することができる。具体的には、例えば、検索キー中のベクトル要素とエントリの対応する要素同士の差に基づいた算出が可能である。より具体的には、distanceは、(x1−y1)2+(x2−y2)2+…+(xn−yn)2とすることができる。ここで、x1およびy1は、検索キーおよびある比較対象のエントリの同じベクトル要素である。x2およびy2は、x1およびy1とは異なるベクトル要素である。xnおよびynについても同様である。メモリコントローラ13は、付された順位に基づいて(すなわち検索キーに対する類似の程度が高い順序で)、各エントリ中のデータをホスト2に送信する。
【0076】
図20は、第4実施形態に係るメモリシステムおよびホストがサポートするコマンドを例示している。より具体的には、図20は、第4実施形態に係るputコマンドにより指定されるパラメータおよび例を示している。図20に示されるように、putコマンドは、パラメータとして、key、key_type、target、search_space、ranking_method、head、size、bufferを含んでいる。パラメータkey、key_type、target、ranking_methodについてはgetコマンドの定義と同じである。パラメータsearch_spaceは、データをどこに格納するかをgetコマンドと同様の手法で指定する。putコマンドの実行は、簡単には空きエントリにキーとデータを追加すればよいが、これから追加しようとするキーに対応するエントリが既にメモリ14内にある場合にはそれらを上書きすることも考えられる。そこで、putコマンドの実行に当たり、ローカルコントローラ12はまず指定されたパラメータを用いて検索を行い、ヒットしたエントリの特定と順位付けまでを行う。パラメータheadは、順位付け後のヒットしたエントリの先頭のエントリから何番目のエントリ以降を上書き対象とするかを指定する。パラメータhead=5とすれば、ヒットしたエントリの先頭から5番目以降の各エントリにより特定されるデータが更新対象である。head=1とすれば全てが上書きされ、head=∞とすれば上書きは行われず空きエントリに書き込まれる。パラメータsizeは、書き込みデータのサイズを指定する。パラメータbufferは、ホスト2中のバッファの先頭アドレスを指定する。putコマンドにより書き込まれるデータはこのホスト2中のバッファから読み出される。このような定義のputコマンドを用いたアドレス指定によるデータ書き込み(更新)について図21を参照して説明する。
【0077】
図21は、第4実施形態に係るメモリシステムの一動作を概略的に示している。図21に示されるように、ホスト2は、パラメータkey>=更新対象のデータの論理アドレス(すなわち先頭アドレス)およびパラメータranking_method=addressを指定するputコマンドをメモリシステム1に供給する。CAMモジュール17は、このようなputコマンドの受信に応答して、getコマンドと同様に、先頭アドレスを検索キーとしてそれ以上の論理アドレスを含むエントリを見つける。次に、順位計算モジュール81は、やはりgetコマンドと同様に、ヒットしたエントリに対して、パラメータranking_methodにより指定される基準に基づいて順位を付する。ranking_method=addressに従い、各エントリに対して、論理アドレスが順位として付される。こうしてヒットしかつ順位付けされた複数エントリのうちの先頭から何番目のエントリ以降のエントリに対応するデータが書かれるかが、パラメータheadにより指定される。具体的には、パラメータhead=0としておけば、ヒットしたエントリの先頭からの各エントリ中に記載のファイル領域41のアドレス中のデータが上書きされる。こうして特定された複数エントリにより特定されるファイル領域41中の部分に、メモリ制御モジュール34およびメモリコントローラ13はデータを書き込む。こうして、putコマンドを用いてアドレス指定による(通常の)データの書き込み(DMA転送によるデータ書き込みに相当)を行なえる。
【0078】
書き込みの際、カラー情報に基づいて、格納先をメモリコントローラ13により選択することが可能である。不揮発性メモリには一般に書き換え回数の限界があり、SLC、MLCなどのメモリのタイプにより書き換え耐性が異なる。そこで、パラメータcolorを参照して書き換え頻度が低いことが期待されるデータについては書き換え耐性の小さなタイプのメモリに、書き換え頻度が高いことが予測されるデータについては書き換え耐性の高いタイプのメモリに格納することでメモリシステム1全体の寿命を伸ばすことができる。例えば、書き換え頻度の低い画像または動画データは書き換耐性の低い(一方で、容量効率の良い)MLCタイプのNAND型フラッシュメモリに格納され、より頻度の高いたとえばテキストデータは書き換え耐性の高いSLCタイプのNAND型フラッシュメモリに格納される。なお、カラー情報は、明示的にkey_type=colorとして指定されたものからだけでなく、上述のようにパラメータkeyとしてファイル名を用いている場合にはファイル名の拡張子からも判断できる。例えばファイル名がfile.wmvであれば動画データであると判断し、MLCタイプのNAND型フラッシュメモリに格納し、ファイル名がfile.txtであればテキストデータであると判断し、SLCタイプのNAND型フラッシュメモリに格納することができる。
【0079】
図22は、第4実施形態に係るメモリシステムおよびホストがサポートするコマンドを例示している。より具体的には、図22は、第4実施形態に係るadd_keyコマンドにより指定されるパラメータを示している。add_keyコマンドは、書き込み済みのエントリにキーを追加するためのものである。add_keyコマンドは、パラメータとして、key、key_type、target、search_space、ranking_method、head、number、key _to_add、key _to_add_typeを含んでいる。パラメータkey、key _type、target、serch_space、ranking_methodについては、getコマンドと同じである。パラメータheadは、putコマンドと同じである。パラメータnumberは、パラメータheadで指定されたエントリから幾つのエントリを処理対象とするかを指定する。パラメータkey _to_addは追加されるキーを記述している。パラメータkey _to_add_typeは、追加されるキーの形態を明示する。
【0080】
CAMモジュール17は、add_keyコマンドの受信に応答して、getコマンドと同様に、検索キーを含むエントリを見つける。次に、順位計算モジュール81は、やはりgetコマンドと同様に、ヒットしたエントリに対して、パラメータranking_methodにより指定される基準に基づいて順位を付する。次に、ローカルコントローラ12は、順位付けされた複数エントリの先頭からパラメータheadにより指定される数だけ大きいエントリからパラメータnumberにより指定される個数の連続するエントリを特定する。次に、メモリ制御モジュール34およびメモリコントローラ13は、このように特定された複数エントリに、パラメータkey_to_addにおいて記述されているキー、およびパラメータkey _to_add_typeにおいて記述されているキー形態を付加する。add_keyコマンドを使用すれば、キーのみの追加を要求されたデータを新たなエントリとして登録することなく、既にメモリ14に存在するデータに対してキーの追加が可能である。add_keyコマンドによりキーを追加されるエントリは、本実施形態の一用法として図21に説明したアドレス指定により書き込まれたエントリだけでなく、第1〜第3実施形態で説明したように一般的なキーとともに書き込まれたエントリも対象である。
【0081】
以上説明したように、第4実施形態に係るメモリシステムによれば、getコマンドおよびputコマンドは、パラメータranking_methodを始め、様々なパラメータを含んでいる。これにより、検索の範囲を限定し、要約や順位を付す手段が提供され、ホスト側での検索結果の吟味/取捨選択を容易にするメモリシステムが提供できる。また、このようなコマンドを用いて、パラメータkeyとして当該1つのデータの先頭アドレスを付するとともに、パラメータranking_methodとしてaddressを指定すれば、getまたはputコマンドを用いたアドレス指定によるデータの書き込みおよび読み出しが可能である。すなわち、検索キーを指定したデータの読み書きとアドレスを指定したデータの読み書きを共通のコマンド体系でサポートできる。
【0082】
その他、各実施形態は、上記のものに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で、種々に変形することが可能である。さらに、上記実施形態には種々の段階が含まれており、開示される複数の構成要件における適宜な組み合わせにより種々の実施形態が抽出され得る。例えば、上記各実施形態に示される全構成要件から幾つかの構成要件が削除されても、この構成要件が削除された構成が実施形態として抽出され得る。
【符号の説明】
【0083】
1…メモリシステム、2…ホスト、11…ホストインターフェース、12…ローカルコントローラ、13…メモリコントローラ、14…メモリ、16…DMAコントローラ、17…CAMモジュール、18…レジスタ/バッファ、21…CPU、22…RAM、23…バス、24…コマンド生成モジュール、26…論理演算モジュール、31…コマンド解析モジュール、32…転送モジュール、33…検索モジュール、34…メモリ制御モジュール、35…判断モジュール、41…ファイル領域、42…CAMデータ領域、51…メタデータテーブル、52…有効/無効表示、53…ヒット/ミスビット列、61…論理演算モジュール、71…ID識別モジュール、81…順位計算モジュール。
【技術分野】
【0001】
本発明の実施形態は、半導体記憶装置、情報処理装置に関する。
【背景技術】
【0002】
連想メモリが知られている。連想メモリではないメモリに対しては、ホストは、メモリ中のデータを、このデータが記憶されているメモリ中の領域のアドレスにより特定する。一方、連想メモリでは、データに関連付けられているメタデータ(キー)を指定してメモリ中のデータを特定する。複数のメタデータに対する論理演算を通じて読み出されるデータを特定することが考えられる。このような複数のメタデータに対する演算を含んだデータ読み出しは、演算等の処理の量が多い。
【先行技術文献】
【特許文献】
【0003】
【特許文献1】特開2002−279785号公報
【発明の概要】
【発明が解決しようとする課題】
【0004】
処理量が少ないデータ転送が可能な半導体記憶装置を提供しようとするものである。
【課題を解決するための手段】
【0005】
一実施形態によるメモリシステムは、半導体記憶装置は、メモリと、制御部を含む。メモリは、データと、データを特定するための検索キーとデータが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持する。制御部は、第1コマンドを受け取ると、第1コマンドが検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを出力し、第1コマンドが実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを出力する。
【図面の簡単な説明】
【0006】
【図1】第1実施形態に係るメモリシステムのブロック図。
【図2】メタデータテーブルのフォーマットを例示する図。
【図3】第1実施形態に係るメモリシステムの動作を示す図。
【図4】第1実施形態に係るメモリシステムの動作を示すフローチャート。
【図5】第2実施形態に係るメモリシステムのブロック図。
【図6】第2実施形態に係るメモリシステムの動作を示す図。
【図7】第2実施形態に係るメモリシステムの動作を示すフローチャート。
【図8】第2実施形態に係るメモリシステムの動作主体のバリエーションを示す図。
【図9】第3実施形態に係るメモリシステムのブロック図。
【図10】第3実施形態に係るメモリシステムの動作を示す図。
【図11】第3実施形態に係るメモリシステムの動作を示すフローチャート。
【図12】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【図13】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【図14】第4実施形態に係るメモリシステムがサポートするコマンドのパラメータの例を示す図。
【図15】第4実施形態に係るメモリシステムのブロック図。
【図16】第4実施形態に係るメモリシステムの一動作を示す図。
【図17】第4実施形態に係るメモリシステムの一動作を示す図。
【図18】第4実施形態に係るメモリシステムの一動作を示す図。
【図19】第4実施形態に係るメモリシステムの一動作を示す図。
【図20】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【図21】第4実施形態に係るメモリシステムの一動作を示す図。
【図22】第4実施形態に係るメモリシステムがサポートするコマンドを例示する図。
【発明を実施するための形態】
【0007】
実施形態の説明に先立ち、連想メモリについて簡単に説明する。連想メモリにアクセスするホストは、メモリにデータを書き込むために、データにメタデータ(キー)を付する。キーは、例えば、書き込み対象のデータ(書き込みデータ)中に含まれる単語、拡張子等の様々なタイプのものを含み得、複数個のキーを含み得る。ホストは、任意の方法により書き込みデータに付されるキーを生成する。ホストは、連想メモリへのデータ書き込みのために、例えばputコマンドを用いる。ホストは、putコマンドとともに、書き込みデータとキーを連想メモリに供給する。連想メモリは、書き込みデータに加えて、メタデータテーブルを保持している。メタデータテーブルは、キーに関する様々なデータの集合であり、1つのデータ(例えばファイル)データごとに1つのエントリを有し、このようなエントリを複数個含んでいる。メモリを制御するコントローラは、書き込みデータおよびキーを受け取ると、書き込みデータをメモリの空き領域に保持し、メタデータテーブル中の空きエントリにキーおよびこのキーとセットになっている書き込みデータが保持される領域を特定するためのアドレスを書き込む。各エントリには、有効/無効を示す情報が設けられており、無効のエントリを探すことによって空きエントリが見つかる。
【0008】
連想メモリからのデータの読み出しを望むホストは、例えばホストのユーザによって入力されたキーを用いてデータを特定する。データ読み出しには、例えばgetコマンドが用いられる。ホストは、getコマンドとともにキーを連想メモリに供給する。連想メモリは、この検索対象のキーを受け取ると、この検索キーを含んだエントリを検索する。そして、発見された全エントリ中に記載のアドレスに保持されている全てのデータをホストに送信する。
【0009】
連想メモリ中のデータの消去を望むホストは、deleteコマンドを使用する。ホストは、deleteコマンドとともにキーを連想メモリに供給する。連想メモリは、deleteコマンドを受け取ると、検索キーを含むエントリを見つける。連想メモリは、見つけられたエントリの有効/無効表示を無効にする。
【0010】
ユーザは、連想メモリに対して、1つの検索キーを直接的に用いる代わりに、1つまたは複数の検索キーに対する論理演算を用いて高度な検索を行なうことを望む場合がある。より具体的には、複数の検索キーを用いた検索があり得る。そのような検索では、メモリは、まず、1つ目の検索キーを含んだエントリを見つけ、見つかった全エントリの各々に対応するデータがホストに送信される。次に、メモリは、2つ目の検索キーを含んだエントリを見つけ、見つかった全エントリの各々に対応するデータをホストに送信する。ホストは、こうして全検索キーについてのデータを受け取る。次いで、ホストは、受け取ったデータの中から、全ての検索キーについてヒットしたデータを例えばAND演算により見つける。ここで言うAND演算とは、1つ目の検索キーについてのデータの集合と、2つ目の検索キーについてのデータの集合との共通集合を抽出する集合演算を指す。こうして、ホストは、検索対象の全てのキーを含んだデータを抽出する。
【0011】
以上のようなAND演算を含む論理演算の実行のために、ホストおよびメモリは大量の処理を必要とする。また、ホストでの論理演算の結果不要となるデータであってもメモリからホストに転送される。さらに、メモリにおいてヒットしたエントリに対応するデータが次々と長期間にわたってメモリからホストに転送されるので、その間、ホストにおける他の処理は遅延され得る。以上のように、処理負荷および効率の点で改善が望まれる。以上の説明は、AND演算に対するものであるが、その他の論理演算(例えばOR演算)等についても同様である。ここで言うOR演算とは、1つ目の検索キーについてのデータの集合と、2つ目の検索キーについてのデータの集合との和集合を抽出する集合演算を指す。後述のNOT演算についても同様で、検索キーについてのデータの補集合を指す。
【0012】
以下に、このような知見に基づいて構成された実施形態について図面を参照して説明する。なお、以下の説明において、略同一の機能及び構成を有する構成要素については、同一符号を付し、重複説明は必要な場合にのみ行う。また、以下に示すいずれの実施形態も、その実施形態の技術的思想を具体化するための装置や方法を例示するものであって、諸実施形態の技術的思想は下記の実例に限定されない。実施形態の技術的思想は、特許請求の範囲において、種々の変更を加えることができる。
【0013】
また、いずれの機能ブロック(モジュール)も、ハードウェア、コンピュータソフトウェアのいずれかまたは両者を組み合わせたものとして実現されることが可能である。このため、各ブロックがこれらのいずれでもあることが明確となるように、概してそれらの機能の観点から以下に説明する。このような機能が、ハードウェアとして実行されるか、またはソフトウェアとして実行されるかは任意である。当業者は、具体的な実施態様ごとに、種々の方法でこれらの機能を実現し得るが、いずれの実現の手法も実施形態の範疇に含まれる。また、各機能ブロックが、以下の具体例のように区別されていることは必須ではない。例えば、一部の機能が以下の説明において例示されている機能ブロックとは別の機能ブロックによって実行されてもよい。さらに、例示の機能ブロックがさらに細かい機能サブブロックに分割されていてもよい。どの機能ブロックによって特定されるかによって実施形態は限定されない。
【0014】
(第1実施形態)
図1は、第1実施形態に係るメモリシステム(半導体記憶装置、情報処理装置)のブロック図である。図1に示されるように、メモリシステム1は、ホスト装置(以下、単にホストと称する)2と通信する。ホスト2は、CPU(central processing unit)21、RAM(random access memory)22等を含んでいる。RAMは、例えばDRAM(dynamic random access memory)である。CPU21は、バス23によってRAM22と接続されている。CPU21は、ROM等のストレージからRAM22上に読み出された制御プログラムに従って所定の処理を実行する。各処理は、CPU21と制御プログラムによって実現されるモジュールによって実行される。モジュールには、少なくとも、コマンド生成モジュール24、論理演算モジュール26が含まれる。図では、便宜上、これらのモジュールは、ホスト2内においてCPU21およびRAMから独立して描かれている。
【0015】
メモリシステム1は、ハードウェア上の構成として、例えばプロセッサ、RAM、ROMを有する。動作の際、ROMに格納されている制御プログラム(命令)がRAM上に読み出される。プロセッサは、このプログラムに従って所定の処理を実行する。以下に述べるメモリシステム1中のメモリ以外の諸機能ブロックは、RAM上の制御プログラムに従ってCPUによって実行されることによって実現される。または、機能ブロックは専用のハードウェア(チップ等)によって実現されもよい。
【0016】
メモリシステム1は、ホストインターフェース11、ローカルコントローラ12、メモリコントローラ13、メモリ14を含んでいる。ホストインターフェース11は、バス23によってCPU21(またはCPU21およびプログラムにより実現されるホスト2中のインターフェースモジュール)と接続されている。ホストインターフェース11は、メモリシステム1とホスト2との間のインターフェースを取るのに必要なハードウェア、ソフトウェアからなる。ホストインターフェース11は、メモリシステム1とホスト2とが通信するのに必要な様々な取り決めを規定し、ホスト2(またはホスト2中のインターフェースモジュール)およびホストインターフェース11がと相互に認識可能な各種のコマンドの組を備えている。
【0017】
ホストインターフェース11は、DMA(direct memory access)コントローラ16を含んでいる。DMAコントローラ16は、プロセッサを介さずに何らかの2つの領域間でのデータの転送を司る。DMAコントローラ16は、実アドレスの指定を通じてデータを特定する。実アドレスとは、物理アドレスおよび論理アドレスのいずれかを指す。
【0018】
ローカルコントローラ12は、ホストインターフェース11と通信可能に接続されている。ローカルコントローラ12は、ホスト2から受け取ったコマンドを解析し、コマンドにより命じられる処理を実行するための様々なタスクを作成する。ローカルコントローラ12およびホストインターフェース11は、上記のput、get、deleteコマンドをサポートしており、さらに後述のコマンドを全てサポートしている。ローカルコントローラ12は、メモリコントローラ13と通信可能に接続されている。ローカルコントローラ12は、コマンド解析モジュール31、転送モジュール32、検索モジュール33、メモリ制御モジュール34、判断モジュール35等を含んでいる。各モジュールは、後述のローカルコントローラ12の対応する特定の処理の実行を担う。
【0019】
メモリコントローラ13は、ローカルコントローラ12からメモリ14が関与するタスクを受け取り、タスクを実行するための指示をメモリ14に送信する。すなわち、メモリコントローラ13は、メモリ14への特定のデータの書き込み、メモリ14からの特定のデータの読み出し、メモリ14中の特定のデータの消去を、メモリ14用のコマンドおよび処理手順に従って実行する。
【0020】
メモリコントローラ13は、CAM(content addressable memory(連想メモリ))モジュール17を含んでいる。CAMモジュール17は、ホストからの検索キーを用いるコマンドを実際に実行するためのデータの書き込み、読み出し、消去等をメモリ14に対して実行する。CAMモジュール17は、専用のハードウェアによって実現されてもよいし、メモリシステム1中のRAM上の制御プログラムにメモリシステム1中のプロセッサの動作が従うことを通じて実現されてもよい。メモリコントローラ13はまた、レジスタ/バッファ18を含んでいる。レジスタ/バッファ18は、メモリコントローラ13による何らかの処理の最中のデータを一時的に保持する。
【0021】
メモリ14は、メモリコントローラ13と通信可能に接続されている。メモリ14は、種々のタイプの不揮発性のメモリのうちの任意のものにより実現される。そのようなメモリには、例えばNAND型フラッシュメモリが含まれる。NAND型フラッシュメモリは、ページ単位でデータを書き込みおよび読み出す。ページは、複数の直列接続されたメモリセルの集合のメモリ空間からなり、固有の物理アドレスを割り当てられている。また、NAND型フラッシュメモリは、ブロック単位でデータを消去する。各ブロックは、連続する物理アドレスを有する複数のページからなる。各メモリセルは、いわゆる積層ゲート構造のMOSFET(metal oxide semiconductor field effect transistor)からなる。各セルトランジスタは、浮遊ゲート電極に蓄えられる電子の数に応じて閾値電圧が変化し、この閾値電圧の違いに応じた情報を記憶する。メモリ14はまたバッファを含んでいる。
【0022】
メモリ14がNAND型フラッシュメモリである場合、メモリ14は、SLC(single level cell)タイプであっても、MLC(multi level cell)タイプであってもよい。SLCタイプは、1つのセルが1ビットのデータを保持する。MLCタイプは、1つのセルが2ビット以上のデータを保持する。メモリ14は、1セル当たり1または複数ビットのデータを保持および読み出すことができるように構成されている。メモリ14は、1つに限らず複数のメモリチップを含んでいてもよい。チップごとに、または各チップ中の領域ごとに、SLCタイプまたはMLCタイプとしての使用が分けられていてもよい。
【0023】
メモリ14は、データ本体(ファイル等)を保持するファイル領域41と、メタデータを保持するCAMデータ領域42を含んでいる。CAMデータ領域42は、連想メモリの機能に用いられるメタデータテーブルを保持する。これらの領域は、例えばメモリ14中の利用可能な全ブロックのうちのいくつかを専用に用いることで実現することができる。
【0024】
メモリ14がNAND型フラッシュメモリである場合、書き込み済みのデータを上書きすることは禁止されている等の制約が存在する。そこで、ローカルコントローラ12からの指示を遂行するために、アドレスの変換を実行および管理する場合がある。具体的には、メモリコントローラ13は、ローカルコントローラ12から受け取ったデータに付された論理アドレスと、当該データを保持するファイル領域中の領域の物理アドレスと、の間の変換テーブルを作成し、これを用いる。変換テーブルは、論物変換テーブルなどとして当業者に知られている。メモリ41への上書きに相当する処理は、メモリコントローラ13によって、変換テーブルを用いて間接的に遂行される。
【0025】
メタデータテーブルは、例えば図2に示されるようなフォーマットを有する。図2に示されるように、メタデータテーブルは、複数のエントリを有する。各エントリは、個別のデータと関連付けられている。1つのエントリは、このエントリに対応するデータと関連付けられている1または複数のキーと、このデータが保持されているファイル領域41中の領域を特定するためのアドレスと、エントリの有効/無効表示を少なくとも含んでいる。キーとして、様々な要素を用いることができる。例えば、データに含まれる単語、データのファイル名、データの拡張子、書き換え頻度等が含まれる。
【0026】
次に、図3および図4を参照して、メモリシステム1の動作について説明する。各機能ブロックのさらなる詳細事項についても同時に記述する。
【0027】
図3は、第1実施形態に係るメモリシステムの動作を概略的に示している。図4は、第1実施形態に係るメモリシステムの動作を概略的に示しており、図3に対応するフローチャートである。図3および図4に示されるように、ホスト2は、key1、key2、key3を検索キーとして含むデータの検索の依頼を受けたとする。この依頼は、コマンドget(key1&key2&key3)の実行に相当する。このような依頼に対して、ホスト2のコマンド生成モジュール24は、この依頼を複数の別のコマンドに翻訳、すなわち、当該依頼を実現するためのコマンドを生成する。具体的には、コマンドfind(key1&key2&key3)と、コマンドread(ヒット/ミスビット列)に分解する。findコマンドは、コマンド中で指定されている検索キーをキーとして含むか否かを有効な全てのエントリごとに示したビットの集合の出力を命じるコマンドである。コマンドread(ヒット/ミスビット列)は、readコマンド中のビット列により特定されるエントリに対応するデータ(エントリ中に記載のアドレスにより特定されるファイル領域41中の領域中のデータ)をホスト2に送信することを命じるコマンドである。これらの2種のコマンドについては、後に詳述する。
【0028】
コマンド生成モジュール24は、find(key1&key2&key3)コマンドを、さらに、検索キーごとのfindコマンドに分解する。本例では、コマンドfind(key1)、find(key2)、find(key3)に分解する。得られたコマンドは、ホスト2中の制御モジュールの制御によって順次メモリシステム1に送信される。メモリシステム1は、ホストインターフェース11を介してローカルコントローラ12において、コマンドfind(key1)、find(key2)、find(key3)を受け取る(ステップS1)。なお、ローカルコントローラ12(コマンド解析モジュール31)によってfind(key1&key2&key3)コマンドが受け取られ、次いでコマンドfind(key1)、find(key2)、find(key3)に分解されてもよい。ホストインターフェース11およびローカルコントローラ12は、findコマンドおよびreadコマンドをサポートしている。
【0029】
ローカルコントローラ12(検索モジュール33、メモリ制御モジュール34)は、1つ目のfindコマンドを、メモリコントローラ13への処理を通じて実行する。より具体的には、メモリコントローラ13は、CAMモジュール17を通じて、find(key1)コマンドを得ると、CAMデータ領域42中のメタデータテーブル51にアクセスして検索キーkey1を含む有効なエントリを見つける。そして見つかった1または複数のエントリを特定するビット列を生成する(ステップS2)。このビット列の各ビットは1つのエントリに対応しており、対応するエントリのヒット/ミスを示しており、ヒット/ミスビット列53と称する。
【0030】
ヒット/ミスビット列53の生成は、例えば、まずメタデータテーブル51中の各エントリを順次CAMモジュール17に読み出すことと、各エントリ中の記述と検索キー(現在は、key1)との比較によって検索キーを含むエントリを発見することを含む。そのために、例えばCAMモジュール17は、メモリコントローラ13を通じてメモリシステム1中のRAMにエントリを順次読み出し、読み出されたエントリ中の記述と検索キーとを比較する。そして、ヒットしたエントリを特定する情報を順次例えばレジスタ/バッファ18で保持してヒット/ミスビット列53を生成する。図中の要素52は、各エントリについての有効/無効表示である。
【0031】
メモリ14のみでCAMの機能を実現できる場合がある。すなわち、メモリ14は内部にCAMデータ領域42中の全エントリに対する検索キー比較回路を持ち、メモリ14に検索キーを入力すると、メモリ14から検索キーが含まれるかの判定結果すなわちヒット/ミスビット列が出力される。このようなメモリ14が用いられる場合、CAMモジュール17は、検索キーをメモリ14に指定して返ってきたヒット/ミスビット列をレジスタ/バッファ18で保持すればよい。
【0032】
次に、CAMモジュール17は、ローカルコントローラ12(転送モジュール32)およびホストインターフェース11を通じて、ヒット/ミスビット列53をホスト2に送信する(ステップS3)。ホスト2は、受信した、1つ目の検索キーkey1についてのヒット/ミスビット列53を例えばRAM22上で保持する。
【0033】
次に、ローカルコントローラ12(判断モジュール35)は、全てのfindコマンドが実行されたかを判断する(ステップS4)。未処理のfindコマンドがあると、未処理のfindコマンドが無くなるまでステップS2、S3が繰り返される。本例では、CAMモジュール17は、2つ目のfindコマンド(すなわち検索キーkey2についてのfindコマンド)を、1つ目のfindコマンドと同様に実行する。実行の結果、検索キーkey2についてのヒット/ミスビット列53が生成され、ホスト1によって保持される。同様に、検索キーkey3についてのヒット/ミスビット列53が生成され、ホスト2によって保持される。
【0034】
全ての検索キーについてのfindコマンドの処理が終了すると、処理はステップS5に移行する。ステップS5において、論理演算モジュール26は、RAM22をワークメモリとして用いて、検索キーkey1、key2、key3の各々についてのヒット/ミスビット列53のANDを計算する。AND処理の結果、演算ヒット/ミスビット列を得る。演算ヒット/ミスビット列は、検索キーkey1、key2、key3の全てを含むメタデータテーブルのエントリを示すビット列からなる。
【0035】
次に、コマンド生成モジュール24は、コマンドread(hit/missビット列)を生成し、ホスト2はこのコマンドをメモリシステム1に送信する(ステップS5)。readコマンド中では、演算ヒット/ミスビット列が指定されている。ローカルコントローラ12(メモリ制御モジュール34)は、このreadコマンドを受け取ると、メモリコントローラ13を通じて、対応するエントリによって特定されるファイル領域41中の領域中のデータをホスト2に送信する(ステップS6)。すなわち、ホストインターフェース11を介してローカルコントローラ12によって受け取られたreadコマンドが解析され、解析の結果に基づいてメモリコントローラ13はCAMデータ領域42中の各エントリに対応するアドレスを順次読み出す。次いで、メモリコントローラ13は、読み出されたエントリ中のアドレスに対応するファイル領域41中の領域からデータを順次読み出し、ローカルコントローラ12およびホストインターフェース11を介してホスト2に転送する。
【0036】
ここまでの説明では、複数の検索キーがANDで結ばれている例を説明したが、ORの場合もANDの場合と同様に処理される。すなわち、OR検索の場合は、ホスト2でORの対象の検索キーについてのヒット/ミスビット列同士のOR演算が行なわれて、演算ヒット/ミスビット列が生成される。
【0037】
以上説明したように、第1実施形態によれば、論理演算を含んだデータ出力は、検索キーを含むエントリを示すヒット/ミスビット列のメモリシステム1からの出力、ホスト2による複数のビット列に対する論理演算、演算ヒット/ミスビット列に対応するデータのメモリシステム1からの出力として実行される。このため、各検索キーのみを含むデータ自体がメモリシステム1から出力されず、検索キーを含むエントリを特定するビット列および検索キーに対する論理演算を反映するデータのみが出力される。よって、データ転送量が減り、全体として高効率な検索キーによるデータ出力が可能となる。
【0038】
(第2実施形態)
第2実施形態も、第1実施形態と同じく、検索キーに対する論理演算を含んだ検索に関する。
【0039】
第2実施形態に係るメモリシステムの構成は、ローカルコントローラ12の構成を除いて第1実施形態と同じである。図5は、第2実施形態に係るメモリシステムのブロック図である。図5に示されるように、第2実施形態のローカルコントローラ12は、第1実施形態での全モジュールに加えて論理演算モジュール61を含んでいる。
【0040】
図6は、第2実施形態に係るメモリシステムの動作を概略的に示している。図7は、第2実施形態に係るメモリシステムの動作を概略的に示しており、図6に対応するフローチャートである。図6および図7に示されるように、ホスト2は、検索キーに対する論理演算を含むデータの検索の依頼を受けたとする。このような依頼には、具体例として、キーkey1とkey2のAND、またはkey1とkey2のOR、またはkey1のNOTを指定するgetコマンドが含まれる。依頼の受領に対して、コマンド生成モジュール24は、findコマンド、andコマンド(または論理演算に基づいてorコマンドまたはnotコマンド)、readコマンドに分割する。図6は、andコマンドを含むケースを示している。and(またはorまたはnot)コマンドについては後述する。ローカルコントローラ12は、得られたコマンドをホスト2から受け取る。(ステップS11)。または、ローカルコントローラ12(コマンド解析モジュール31)が検索キーに対する論理演算を含んだgetコマンドを受け取ってfindコマンド、andまたはorまたはnotコマンド、readコマンドに分割してもよい。
【0041】
まず、メモリコントローラ13(検索モジュール33)は、1または複数の検索キーについてfindコマンドにより指示される処理に類似の処理を行なう。すなわち、検索モジュール33は、CAMモジュール17に1つ目の検索キーkey1についてのヒット/ミスビット列の生成を指示する。CAMモジュール17は、ステップS2を実行して検索キーkey1についてのヒット/ミスビット列53を生成する。第2実施形態の場合、生成されたヒット/ミスビット列53は、レジスタ/バッファ18に保持され、メモリシステム1から出力されない(ステップS13)。
【0042】
次に、論理演算モジュール52(または判断モジュール35)は、続くコマンドの種類を識別する(ステップS14)。コマンドがreadコマンドである場合、処理はステップS22に移行する。論理演算コマンドがnotコマンドである場合、処理はステップS15に移行する。ステップS15において、論理演算モジュール61は、ヒット/ミスビット列53の全ビットを反転して、得られた演算ヒット/ミスビット列をレジスタ/バッファ18に保持する(ステップS15)。
【0043】
論理演算コマンドがandコマンドまたはorコマンドである場合、検索モジュール33は、検索キーkey1についてのfindコマンドに続いて、andコマンドまたはorコマンドを受け取る。andコマンドまたはorコマンドは、それぞれkey1とともにANDまたはOR演算の対象である検索キーkey2を指定している。andまたはorコマンドの受信により、検索モジュール33の指示に応答してCAMモジュール17は検索キーkey2についてのヒット/ミスビット列53を生成する(ステップS17)。論理演算モジュール61は、andコマンドおよびorコマンドのいずれを受信したかに基づいて、レジスタ/バッファ18に保持されている検索キーkey1についてのヒット/ミスビット列53と、key2についてのヒット/ミスビット列53に対してANDまたはOR演算を行なう。論理演算モジュール61は、得られた演算ヒット/ミスビット列で、レジスタ/バッファ18に保持されていた検索キーkey1についてのヒット/ミスビット列を更新する(ステップS18)。
【0044】
次に、受信した論理演算コマンドの終了/未終了が判断される(ステップS21)。全ての論理演算が完了していない場合、処理はステップS14に戻る。一方、全ての論理演算が完了していれば、メモリ制御モジュール34は、演算ヒット/ミスビット列についてのreadコマンドを実行する(ステップS22)。すなわち、メモリ制御モジュール34は、メモリコントローラ13を通じて、演算ヒット/ミスビット列により特定されるエントリ中のアドレスに対応するファイル領域41中の領域からデータを読み出す。読み出されたデータは、ローカルコントローラ12およびホストインターフェース11を介してホスト2に送信される。
【0045】
ここまでの説明では、ヒット/ミスビット列および演算ヒット/ミスビット列がいずれもレジスタ/バッファ18に保持される例を説明した。これは、メモリ14がCAM機能を備えていない例に対応し、図8(a)に対応する。右上がりのハッチングはヒット/ミスビット列を生成する要素を示し、右下がりのハッチングは演算ヒット/ミスビット列を生成する要素を示す。図8(a)の例では、ヒットミスビット列はメモリコントローラ13(CAMモジュール17)によって生成され、演算ヒット/ミスビット列はローカルコントローラ12(検索モジュール33)によって生成される。レジスタ/バッファ18にCAMモジュールの機能が統合されていてハードウェアとして実現されていてもよいし、CAMモジュール17がソフトウェアとして実現されていてもよい。一方、メモリ14がCAM機能を備えている場合、ヒット/ミスビット列はメモリ14によって生成され、例えばページバッファにおいて保持される。これは、図8(b)に対応する。図8(b)の例では、メモリ14がローカルコントローラ12およびメモリコントローラ13の指示に従って、各検索キーkeyについてのヒット/ミスビット列を生成し、これらに対する演算ヒット/ミスビット列がローカルコントローラ12によって生成され、レジスタ/バッファ18において保持される。
【0046】
第2実施形態の以上説明した以外の記述については、第1実施形態のものが全て当てはまる。
【0047】
以上述べたように、第2実施形態によれば、検索キーに対する論理演算を含んだデータ出力の指示は、メモリシステム1によって、検索キーを含むエントリの検索、ヒット/ミスビット列に対する論理演算、演算ヒット/ミスビット列に対応するデータ出力として実行される。これらの処理は全て、メモリシステム1において実行される。このため、個々の検索キーを含むデータ自体がメモリシステム1から出力されず、よって、データ転送量が減り、全体として高効率な検索キーによるデータ出力が可能となる。
【0048】
(第3実施形態)
第3実施形態は、複数のコマンドの並列処理に関し、第2実施形態に対して付加的に用いられる。
【0049】
第3実施形態に係るメモリシステムの構成は、ローカルコントローラ12の構成を除いて第1、第2実施形態と同じである。図9は、第3実施形態に係るメモリシステムのブロック図である。図9に示されるように、第3実施形態のローカルコントローラ12は、第2実施形態での全モジュールに加えてID識別モジュール71を含んでいる。
【0050】
図10は、第3実施形態に係るメモリシステムの動作を概略的に示している。図11は、第3実施形態に係るメモリシステムの動作を概略的に示しており、図10に対応するフローチャートである。図10および図11に示されるように、ホスト2のコマンド生成モジュール24は、各コマンドにIDを含める。IDは、図では、各コマンド中の最初に配置されているパラメータ(0または1を例示)である。特に、第1、第2実施形態のように検索キーに対する論理演算を含むgetコマンドがfindコマンド、論理演算コマンド、readコマンドの組合せにより実現される場合、1つのgetコマンド実行のための一連の複数コマンドに共通のIDが付される。図10では、論理演算コマンドは例としてandコマンドであり、より具体的には、第1のgetコマンド(ID=0)は、検索キーkey1、key3のANDを指定しており、第2のgetコマンド(ID=1)は、検索キーkey2、key4のANDを指定している。
【0051】
まず、コマンド生成モジュール24は、IDを指定しつつ、getコマンドによる処理を実現するための一連のコマンドを生成する。すなわち、まず、各getコマンド用の1つ目の検索キーkey1、2についてのfindコマンドを生成する。すなわち、ID=0およびkey1を指定するfindコマンドと、ID=1およびkey2を指定するfindコマンドを生成する。次いで、ID=0およびkey3を指定するandコマンドと、ID=1およびkey4を指定するandコマンドを生成する。さらに、ID=0を指定するreadコマンドと、ID=1を指定するreadコマンドを生成する。ホスト2は、これらのコマンドをメモリシステム1に送信する。これらのコマンドの送信の順番は、少なくとも同じIDを付されたコマンドについて、findコマンド、andコマンド、readコマンドの順が保たれていればよい。このように共通のIDを付された複数コマンドの送信順が保たれていれば、別IDを付されたコマンドが間に挿入されていても構わない。したがって、コマンドの生成の順序も、送信の順序が保たれていれば上記の例に限られない。
【0052】
ローカルコントローラ12は、生成されたコマンドを受け取る(ステップS31)。または、ローカルコントローラ12(コマンド解析モジュール31)が検索キーに対する論理演算を含んだ第1のgetコマンド(key1、key3)と第2のgetコマンド(キーkey2、key4)を受け取って、IDを指定しつつfindコマンド、andまたはorまたはnotコマンド、readコマンドに分割してもよい。この例の場合、コマンド解析モジュール31が、下位モジュールとしてID付与モジュールを含んでいてもよい。
【0053】
ID識別モジュール71は、受け取ったコマンドのIDを識別する(ステップS32)。次いで、コマンド解析モジュール31は、識別されたIDについて、コマンドの種類を識別する(ステップS33)。findコマンドが受け取られた場合、CAMモジュール17は、検索キーについてのヒット/ミスビット列53を生成する(ステップS41)。メモリ14がCAM機能を備えている場合は、ヒット/ミスビット列53はメモリ14により生成される。以下の記述でも、ヒット/ミスビット列53は、実施の態様に基づいてCAMモジュール17およびメモリ14の任意の方で生成されるものとする。次に、得られたヒット/ミスビット列53が、レジスタ/バッファ18中の指定されたID用の部分に保持される(ステップS42)。このように、レジスタ/バッファ18は、IDごとに相互に独立する部分を含んでいる。ステップS41、S42は、IDが特定されていることを除いて、第1、第2実施形態のステップS2、S13と同じである。
【0054】
notコマンドが受け取られた場合、論理演算モジュール61は、レジスタ/バッファ18中の指定されたID用の部分に保持されているヒット/ミスビット列53の全ビットを反転して、得られた演算ヒット/ミスビット列53をレジスタ/バッファ18中の指定されたID用の部分に保持する(ステップS44)。ステップS43、S44は、IDが特定されていることを除いて、第2実施形態のステップS15と同じである。
【0055】
andコマンドまたはorコマンドが受け取られた場合、CAMモジュール17は、検索キーについてのヒット/ミスビット列53を生成する(ステップS45)。論理演算モジュール61は、andコマンドおよびorコマンドのいずれを受信したかに基づいて、得られたヒット/ミスビット列53と、コマンドにて指定されているIDと同じID用のレジスタ/バッファ18の部分に保持されているヒット/ミスビット列とに対して、ANDまたはOR演算を行なう。論理演算モジュール61は、得られた演算ヒット/ミスビット列で、指定ID用のレジスタ/バッファ18の部分に保持されていたヒット/ミスビット列を更新する(ステップS46)。ステップS45、S46は、IDが特定されていることを除いて、第2実施形態のステップS17、S18と同じである。
【0056】
readコマンドが受け取られた場合、メモリ制御モジュール34は、指定されたIDについての演算ヒット/ミスビット列により特定されるエントリ中のアドレスからデータを読み出す(ステップS47)。読み出されたデータは、ローカルコントローラ12およびホストインターフェース11を介してホスト2に送信される。
【0057】
ステップS42、S44、S46、S47に続いて、判断モジュール35は、全てのコマンドに対する処理が完了したかを判断する(ステップS51)。未処理のコマンドがある場合、ステップS33、S41〜S47が実行される。図10の例では、ID=0および1の両方について、findコマンド、andコマンド、readコマンドが実行される。この結果、最終的に、検索キーkey1、3の両方を含むデータ、および検索キーkey2、4の両方を含むデータがホスト2に送信される。図10では、2つのIDが並行して処理される例を示すが、3つ以上のIDについてもここまでの説明と同じ原理に則って実行されることが可能である。
【0058】
以上述べたように、第3実施形態によれば、第2実施形態と同じく、検索キーに対する論理演算を含んだデータ出力の指示は、メモリシステム1によって、検索キーを含むエントリの検索、ヒット/ミスビット列に対する論理演算、演算ヒット/ミスビット列に対応するデータ出力として実行される。このため、第2実施形態と同じ利点を得られる。
【0059】
また、第3実施形態によれば、各コマンドがIDにより識別される。このため、第2実施形態のように、検索キーに対する論理演算を含んだデータ出力指示が複数のコマンドにより実行される場合であっても、検索キーに対する論理演算を含んだデータ出力を複数個並列に実行できる。
【0060】
(第4実施形態)
第4実施形態はコマンドの拡張に関する。
【0061】
図12および図13は、第4実施形態に係るメモリシステムおよびホストがサポートするコマンドを例示している。より具体的には、図12および図13は、第4実施形態に係るgetコマンドにより指定されるパラメータおよび例を示している。図12に示されるように、getコマンドは、パラメータとして、key、key_type、target、search_space、summary_types、ranking_method、size、bufferを含んでいる。または、図13に示されるように、パラメータsize、bufferに代えてhead、numberを含んでいる。
【0062】
パラメータkeyは、検索キーである。パラメータkeyとして、対応するデータに付されるメタデータだけでなく、拡張子を含んだファイル名とすることもできる。具体的には、例えばfile. wmv、file. txtのような形態で指定される。
【0063】
パラメータkey_typeは、検索キーの形態を明示しており、より具体的には検索キーが例えば文字データ、画像データ、音声データであることに基づいてそれぞれtext、image、audio等の文字列を含んでいる。パラメータkeyとしてファイル名を用いている場合、パラメータkey_typeとしてfilenameが指定される。
【0064】
また、パラメータkey_typeとしてcolorを指定することもできる。その場合、パラメータkeyとして、例えばvideo、image、text、書き換え頻度レベル(書き換え頻度レベル1、2、3、…)等が指定される。値colorは、カラー情報に関する値である。カラー情報とは、対象とするデータの書き換え頻度情報(そのデータ/ファイル等がユーザやホストによってどのくらいの頻度で更新されるかの情報)やデータの種類を示す情報である。例えば、カラー情報をエントリに含めておくことにより、複数のタイプのメモリ14がメモリシステム1に含まれている場合にカラー情報に基づいてデータを格納するメモリ14を適切に決定できる。具体的には、パラメータkey_typeにcolorが指定されている場合、パラメータkeyに設定されている値video、image、text等に基づいて、格納先がメモリコントローラ13により決定される。格納先の選択については後述する。
【0065】
パラメータtargetは、getコマンドが検索の対象とするデータの種類を明示する。データ種類の判定は、例えば拡張子により行なうことができる。パラメータtargetとして、具体的には、例えばwebpage、file、doc、image、audio、videoの指定が可能である。
【0066】
パラメータsearch_spaceは、getコマンドが検索の対象とする空間を指定しており、探索空間に基づいて例えばweb、disk、memory等の文字列を含んでいる。webはインターネットを介して閲覧可能な対象を探索空間として指定する。diskはメモリ14およびハードディスク、ネットワークディスク等の、ホストからアクセス可能なディスクを探索空間として指定する。どのディスクを検索するか、ディスク内のどのディレクトリを検索するかの指定も含まれ得る。memoryは、RAM22およびメモリ14を含むメモリアドレス空間が指定されていることを意味し、後述のDMAに使用する。探索空間の指定は、本実施形態に係るgetコマンドをメモリシステム1以外の領域を指定できるように適応させるためのものである。すなわち、上にも説明したように、パラメータtargetとして、webまたはメモリ14以外の領域を対象とするdiskまたはメモリを含むgetコマンドは、そのようなコマンドを受け取った構成素が、ウェブまたは構成素に接続されているハードディスク等のディスクまたはRAM等のメモリアドレス空間を探索空間として指定する。
【0067】
パラメータsummary_typesは、検索結果の要約の種類のリストを明示する。このパラメータは、検索結果のデータが大きい場合に、ホスト側で検索結果の吟味/取捨選択にかかる時間を軽減するために、各検索データを端的に表す要約データを付することができるようにするものである。パラメータranking_methodは、検索されたエントリに順位を付する際に順位が何に基づくかを指定する。一般に、複数の見つかったエントリが存在するため、ホスト2が所望のものを早い段階で取得できるように、エントリに順位を付する。パラメータsizeは、ホスト2中のバッファ(例えばRAM22により実現される)のサイズを明示する。パラメータbufferは、ホスト2中のバッファの先頭アドレスを指定する。メモリシステム1は、ヒットしたエントリにより特定される全データのうちで、パラメータranking_methodにより指定される基準に基づいて付された順位の高いものから順に、パラメータsizeによって指定されるサイズを越えない範囲で、パラメータbufferによって指定されるホスト2中のバッファに出力する。ホスト2に出力されない分のデータは、メモリシステム1中の例えばバッファ/レジスタ18において保持される。または、ホスト2に出力される分だけのデータが随時メモリ14から読み出されるとしてもよい。メモリシステム1は、ホスト2からこの最初の分のデータの受信が完了した旨の通知を受け取ると、続きの分のデータを出力する。
【0068】
パラメータheadは、パラメータranking_methodに指定される基準に基づいて順位が付された検索結果データの何番目からデータを受信するかを指定する。パラメータnumberは、検索結果データを最大何個受信するかを指定する。パラメータheadおよびnumberは、パラメータsizeおよびbufferとは異なり、出力を要求されるデータの大きさを順位付き検索結果の開始位置および個数によって指定する。例えば、パラメータhead=1, number=10とすれば検索結果データの1位から10位までが順に出力される。head=11, number=10として再度getコマンドを発行すれば11位から20位までの検索結果が得られる。
【0069】
図14は、第4実施形態に係るgetコマンド(図12、図13)のパラメータの一例を示している。2行目はwebから(search_space=web)"toshiba"に関連する(key="toshiba")画像を(target=image)、テキスト検索する(key_type=text)場合を示しており、検索結果の要約としては縮小版の画像であるサムネイル画像を(summary_types=[thumbnail])、検索結果の順位付けとしてはページランク(ranking_method=page_rank)を指定している。3行目はディスク領域の"/home/"で示されるディレクトリ以下から(search_space=disk"/home/")、"toshiba"に関連する(key="toshiba")ファイルを(target=file)、テキスト検索する(key_type=text)場合を示しており、検索結果の要約としてはファイルのサイズと更新日時を(summary_types=[file_size, modified_date]、検索結果の順位付けとしてはファイルの新しいものから古いものへ順位をつける(ranking_method=new_to_old)ことを指定している。4行目はある開始アドレスから一定サイズのデータを読み書きするDMA転送を検索コマンドとして実現する例で、メモリアドレス空間から(search_space=memory)、バイナリデータを(target=binary_data)、先頭アドレス0x0123abcd以上の(key>=0x0123abcd)アドレスを検索して(key_type=address)、アドレス順に出力する(ranking_method=address)ことを指定している。要約は出力しない(summary_types=null)。DMA転送については図17、18の説明に付随して後述する。
【0070】
第4実施形態に係るメモリシステムの構成は、ローカルコントローラ12の構成を除いて第1実施形態と同じである。図15は、第4実施形態に係るメモリシステムのブロック図である。図15に示されるように、第4実施形態のローカルコントローラ12は、第1実施形態での全モジュールに加えて順位計算モジュール81を含んでいる。第4実施形態は、第2、第3実施形態とも組み合わせることが可能である。このため、第4実施形態のローカルコントローラ12は、論理演算モジュール61(図5)およびID識別モジュール71(図9)を含んでいてもよい。
【0071】
図16は、第4実施形態に係るメモリシステムの一動作を概略的に示している。より具体的には、図16は、パラメータranking_methodの指定によるメモリシステム1の応答を示している。図16および図17に示されるように、CAMモジュール17は、第4実施形態に係るgetコマンドの受信に応答して、パラメータkeyによって指定される検索キーを含んだ有効エントリを見つける。次に、順位計算モジュール81は、パラメータranking_methodにより指定される基準に基づいて、ヒットしたエントリの順位を計算する。そして、ローカルコントローラ12は、各エントリに付された順位に基づいて、順位の小さい方から順に、対応するデータをホスト2に出力する。
【0072】
次に、図17〜図19を参照して、パラメータの種々の設定の例を説明する。図17、図18〜図19は、第4実施形態に係るメモリシステムの一動作を概略的に示している。図17、図18は、パラメータの設定を適切に組み合わせることによって、通常のデータ読み出し、すなわち読み出しデータのアドレスとサイズを指定したデータ読み出し(DMA転送による読み出しに相当)を、getコマンドによって実現できることを説明する図である。ただし、このようなgetコマンドを用いたアドレス指定によるデータ読み出しのために、CAMモジュール17はエントリが検索キーを含むかどうかの完全一致だけでなく、大小関係の判定もできるように構成されている。また、エントリはkeyとして論理アドレスを含んでいる。このようなデータ格納は、後述のputコマンドにより実現可能であり、また、そもそも各エントリは自明なキーとして論理アドレスを含むとしてもよい。論理アドレスは、ホスト2によりデータに割り当てられるアドレスである。
【0073】
図17に示されるように、ホスト2は、getコマンドを用いたアドレス指定によるデータ読み出しのために、パラメータkeyとして先頭アドレス以上を対象とすることを示すパラメータおよびパラメータranking_methodとしてaddressを指定するgetコマンドをメモリシステム1に供給する。ここでいう先頭アドレスは論理アドレスである。CAMモジュール17は、このようなgetコマンドの受信に応答して、検索キー、すなわち先頭アドレス以上の論理アドレスを有するエントリを見つける。次に、順位計算モジュール81は、ヒットしたエントリに対して論理アドレスの昇順に順位を付する(論理アドレスそのものを順位としてもよい)。そして、メモリコントローラ13は、エントリの順位に従って、対応するデータを出力する。これにより、先頭アドレスを含んだエントリのデータから論理アドレス順にデータが出力される。または、パラメータkey=allと(全エントリヒット)と指定し、パラメータranking_methodをaddr < 先頭アドレス ? ∞ : addrとすることによっても可能である。すなわち、論理アドレスが指定された先頭アドレスより小さければ順位を無限大として、先頭アドレス以上であればその論理アドレスを順位とする。このようなパラメータの指定により、先頭アドレスより小さいアドレスを含むエントリは順位が無限大になって、実質的にメモリシステム1から出力されない。以上のようなパラメータの指定により、getコマンドを用いたアドレス指定によるデータ読み出しが可能である。したがって、メモリシステム1に、DMAコントローラ16を介してDMAの機能をサポートさせることが可能である。
【0074】
また、図18に示されるように、図17のパラメータ指定のうち、ranking_methodを、例えばaddr %4 < 2 ? addr: 0と変える。このように指定すれば、図17を参照して説明したようにパラメータkeyにより指定された先頭アドレスにより特定されたエントリから、特定の個数ごとのエントリにのみ順位が付される。図の例では、4つごとに最初の2個のエントリのみが順位割付の対象とされる。このような指定を用いれば、例えば、画像データのうちの特定の領域のみを転送することができる(ブロック転送(BLT)に相当)。
【0075】
また、図19に示されるように、完全一致や大小関係では扱えない類似検索もできる。この場合は、パラメータkey=feature 1、パラメータranking_method=dinstanceと指定される。feature 1は、画像または動画データ等の任意の特徴を記述する具体的な特徴ベクトルである。feature 1の具体例として、例えば、グレースケール画像の場合、画素値ヒストグラム等が挙げられる。CAMモジュール17は、このようなgetコマンドの受信に応答して、検索キーを含むエントリを見つける。ただし、パラメータranking_method=dinstanceの場合、全エントリがヒットして扱われ、以下に述べるように、順位計算モジュール81は、distanceに基づいてヒットしたエントリに順位を付する。distanceは、例えば、検索キー(特徴ベクトル)と各エントリ中の特徴ベクトルを用いて算出することができる。具体的には、例えば、検索キー中のベクトル要素とエントリの対応する要素同士の差に基づいた算出が可能である。より具体的には、distanceは、(x1−y1)2+(x2−y2)2+…+(xn−yn)2とすることができる。ここで、x1およびy1は、検索キーおよびある比較対象のエントリの同じベクトル要素である。x2およびy2は、x1およびy1とは異なるベクトル要素である。xnおよびynについても同様である。メモリコントローラ13は、付された順位に基づいて(すなわち検索キーに対する類似の程度が高い順序で)、各エントリ中のデータをホスト2に送信する。
【0076】
図20は、第4実施形態に係るメモリシステムおよびホストがサポートするコマンドを例示している。より具体的には、図20は、第4実施形態に係るputコマンドにより指定されるパラメータおよび例を示している。図20に示されるように、putコマンドは、パラメータとして、key、key_type、target、search_space、ranking_method、head、size、bufferを含んでいる。パラメータkey、key_type、target、ranking_methodについてはgetコマンドの定義と同じである。パラメータsearch_spaceは、データをどこに格納するかをgetコマンドと同様の手法で指定する。putコマンドの実行は、簡単には空きエントリにキーとデータを追加すればよいが、これから追加しようとするキーに対応するエントリが既にメモリ14内にある場合にはそれらを上書きすることも考えられる。そこで、putコマンドの実行に当たり、ローカルコントローラ12はまず指定されたパラメータを用いて検索を行い、ヒットしたエントリの特定と順位付けまでを行う。パラメータheadは、順位付け後のヒットしたエントリの先頭のエントリから何番目のエントリ以降を上書き対象とするかを指定する。パラメータhead=5とすれば、ヒットしたエントリの先頭から5番目以降の各エントリにより特定されるデータが更新対象である。head=1とすれば全てが上書きされ、head=∞とすれば上書きは行われず空きエントリに書き込まれる。パラメータsizeは、書き込みデータのサイズを指定する。パラメータbufferは、ホスト2中のバッファの先頭アドレスを指定する。putコマンドにより書き込まれるデータはこのホスト2中のバッファから読み出される。このような定義のputコマンドを用いたアドレス指定によるデータ書き込み(更新)について図21を参照して説明する。
【0077】
図21は、第4実施形態に係るメモリシステムの一動作を概略的に示している。図21に示されるように、ホスト2は、パラメータkey>=更新対象のデータの論理アドレス(すなわち先頭アドレス)およびパラメータranking_method=addressを指定するputコマンドをメモリシステム1に供給する。CAMモジュール17は、このようなputコマンドの受信に応答して、getコマンドと同様に、先頭アドレスを検索キーとしてそれ以上の論理アドレスを含むエントリを見つける。次に、順位計算モジュール81は、やはりgetコマンドと同様に、ヒットしたエントリに対して、パラメータranking_methodにより指定される基準に基づいて順位を付する。ranking_method=addressに従い、各エントリに対して、論理アドレスが順位として付される。こうしてヒットしかつ順位付けされた複数エントリのうちの先頭から何番目のエントリ以降のエントリに対応するデータが書かれるかが、パラメータheadにより指定される。具体的には、パラメータhead=0としておけば、ヒットしたエントリの先頭からの各エントリ中に記載のファイル領域41のアドレス中のデータが上書きされる。こうして特定された複数エントリにより特定されるファイル領域41中の部分に、メモリ制御モジュール34およびメモリコントローラ13はデータを書き込む。こうして、putコマンドを用いてアドレス指定による(通常の)データの書き込み(DMA転送によるデータ書き込みに相当)を行なえる。
【0078】
書き込みの際、カラー情報に基づいて、格納先をメモリコントローラ13により選択することが可能である。不揮発性メモリには一般に書き換え回数の限界があり、SLC、MLCなどのメモリのタイプにより書き換え耐性が異なる。そこで、パラメータcolorを参照して書き換え頻度が低いことが期待されるデータについては書き換え耐性の小さなタイプのメモリに、書き換え頻度が高いことが予測されるデータについては書き換え耐性の高いタイプのメモリに格納することでメモリシステム1全体の寿命を伸ばすことができる。例えば、書き換え頻度の低い画像または動画データは書き換耐性の低い(一方で、容量効率の良い)MLCタイプのNAND型フラッシュメモリに格納され、より頻度の高いたとえばテキストデータは書き換え耐性の高いSLCタイプのNAND型フラッシュメモリに格納される。なお、カラー情報は、明示的にkey_type=colorとして指定されたものからだけでなく、上述のようにパラメータkeyとしてファイル名を用いている場合にはファイル名の拡張子からも判断できる。例えばファイル名がfile.wmvであれば動画データであると判断し、MLCタイプのNAND型フラッシュメモリに格納し、ファイル名がfile.txtであればテキストデータであると判断し、SLCタイプのNAND型フラッシュメモリに格納することができる。
【0079】
図22は、第4実施形態に係るメモリシステムおよびホストがサポートするコマンドを例示している。より具体的には、図22は、第4実施形態に係るadd_keyコマンドにより指定されるパラメータを示している。add_keyコマンドは、書き込み済みのエントリにキーを追加するためのものである。add_keyコマンドは、パラメータとして、key、key_type、target、search_space、ranking_method、head、number、key _to_add、key _to_add_typeを含んでいる。パラメータkey、key _type、target、serch_space、ranking_methodについては、getコマンドと同じである。パラメータheadは、putコマンドと同じである。パラメータnumberは、パラメータheadで指定されたエントリから幾つのエントリを処理対象とするかを指定する。パラメータkey _to_addは追加されるキーを記述している。パラメータkey _to_add_typeは、追加されるキーの形態を明示する。
【0080】
CAMモジュール17は、add_keyコマンドの受信に応答して、getコマンドと同様に、検索キーを含むエントリを見つける。次に、順位計算モジュール81は、やはりgetコマンドと同様に、ヒットしたエントリに対して、パラメータranking_methodにより指定される基準に基づいて順位を付する。次に、ローカルコントローラ12は、順位付けされた複数エントリの先頭からパラメータheadにより指定される数だけ大きいエントリからパラメータnumberにより指定される個数の連続するエントリを特定する。次に、メモリ制御モジュール34およびメモリコントローラ13は、このように特定された複数エントリに、パラメータkey_to_addにおいて記述されているキー、およびパラメータkey _to_add_typeにおいて記述されているキー形態を付加する。add_keyコマンドを使用すれば、キーのみの追加を要求されたデータを新たなエントリとして登録することなく、既にメモリ14に存在するデータに対してキーの追加が可能である。add_keyコマンドによりキーを追加されるエントリは、本実施形態の一用法として図21に説明したアドレス指定により書き込まれたエントリだけでなく、第1〜第3実施形態で説明したように一般的なキーとともに書き込まれたエントリも対象である。
【0081】
以上説明したように、第4実施形態に係るメモリシステムによれば、getコマンドおよびputコマンドは、パラメータranking_methodを始め、様々なパラメータを含んでいる。これにより、検索の範囲を限定し、要約や順位を付す手段が提供され、ホスト側での検索結果の吟味/取捨選択を容易にするメモリシステムが提供できる。また、このようなコマンドを用いて、パラメータkeyとして当該1つのデータの先頭アドレスを付するとともに、パラメータranking_methodとしてaddressを指定すれば、getまたはputコマンドを用いたアドレス指定によるデータの書き込みおよび読み出しが可能である。すなわち、検索キーを指定したデータの読み書きとアドレスを指定したデータの読み書きを共通のコマンド体系でサポートできる。
【0082】
その他、各実施形態は、上記のものに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で、種々に変形することが可能である。さらに、上記実施形態には種々の段階が含まれており、開示される複数の構成要件における適宜な組み合わせにより種々の実施形態が抽出され得る。例えば、上記各実施形態に示される全構成要件から幾つかの構成要件が削除されても、この構成要件が削除された構成が実施形態として抽出され得る。
【符号の説明】
【0083】
1…メモリシステム、2…ホスト、11…ホストインターフェース、12…ローカルコントローラ、13…メモリコントローラ、14…メモリ、16…DMAコントローラ、17…CAMモジュール、18…レジスタ/バッファ、21…CPU、22…RAM、23…バス、24…コマンド生成モジュール、26…論理演算モジュール、31…コマンド解析モジュール、32…転送モジュール、33…検索モジュール、34…メモリ制御モジュール、35…判断モジュール、41…ファイル領域、42…CAMデータ領域、51…メタデータテーブル、52…有効/無効表示、53…ヒット/ミスビット列、61…論理演算モジュール、71…ID識別モジュール、81…順位計算モジュール。
【特許請求の範囲】
【請求項1】
データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
第1コマンドを受け取ると、前記第1コマンドが前記検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを出力し、前記第1コマンドが前記実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを出力する制御部と、
を具備することを特徴とする半導体記憶装置。
【請求項2】
DMAコントローラをさらに具備し、前記実アドレスを特定する第1コマンドは、前記DMAコントローラにより発行されることを特徴とする請求項1に記載の半導体記憶装置。
【請求項3】
前記第1コマンドは、検索条件を特定可能であり、前記制御部は前記検索条件に基づいた順番でデータを出力することを特徴とする請求項1または2に記載の半導体記憶装置。
【請求項4】
データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
第2コマンドを受け取ると前記検索情報の複数のエントリから前記第2コマンドにより特定される検索キーを含むエントリを特定するデータを外部に出力し、さらに第3コマンドを受け取ると前記第3コマンドにより特定されるエントリに対応するデータを外部に出力する制御部と、
を具備することを特徴とする半導体記憶装置。
【請求項5】
コマンド解析部をさらに具備し、前記コマンド解析部は、検索キーを特定し、この検索キーに対応するデータを前記メモリから読み出すための第4コマンドを受け取り、前記第4コマンドに基づいて前記第2コマンドと前記第3コマンドを生成することを特徴とする請求項4に記載の半導体記憶装置。
【請求項6】
データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
第5コマンドを受け取ると前記検索情報の複数のエントリから前記第5コマンドにより特定される検索キーを含むエントリに対応する第1データ集合を特定し、さらに第6コマンドを受け取ると前記第6コマンドにより特定される検索キーを含むエントリに対応する第2データ集合を特定し、かつ前記第6コマンドにより指定される集合演算を前記第1データ集合と前記第2データ集合に対して実行し、出力する制御部と、
を具備することを特徴とする半導体記憶装置。
【請求項7】
ID付与部をさらに備え、前記ID付与部は、前記第5コマンド及び前記第6コマンドにより実行される複数の集合演算が並列に実行される場合に、それぞれの集合演算を実行する前記第5コマンドおよび第6コマンドの組に対してIDを付与することを特徴とする請求項6に記載の半導体記憶装置。
【請求項8】
前記検索キーは、少なくとも前記データ中に含まれる単語、データのファイル名、前記ファイル名の拡張子、データの書き換え頻度を含むことを特徴とする請求項1乃至7いずれか1項に記載の半導体記憶装置。
【請求項9】
前記エントリは前記データ毎に備えられ、1つのエントリに複数の検索キーを含むことを特徴とする請求項1乃至8いずれか1項に記載の半導体記憶装置。
【請求項10】
ホスト機器と、
前記ホスト機器と接続された半導体記憶装置を備え、
前記半導体記憶装置は、データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
前記ホスト機器から第1コマンドを受け取ると、前記第1コマンドが前記検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを前記ホスト機器に出力し、前記第1コマンドが前記実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを前記ホスト機器に出力する制御部と、
を具備することを特徴とする情報処理装置。
【請求項11】
前記半導体記憶装置は、DMAコントローラをさらに具備し、前記実アドレスを特定する第1コマンドは、前記DMAコントローラにより発行されることを特徴とする請求項10に記載の情報処理装置。
【請求項1】
データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
第1コマンドを受け取ると、前記第1コマンドが前記検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを出力し、前記第1コマンドが前記実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを出力する制御部と、
を具備することを特徴とする半導体記憶装置。
【請求項2】
DMAコントローラをさらに具備し、前記実アドレスを特定する第1コマンドは、前記DMAコントローラにより発行されることを特徴とする請求項1に記載の半導体記憶装置。
【請求項3】
前記第1コマンドは、検索条件を特定可能であり、前記制御部は前記検索条件に基づいた順番でデータを出力することを特徴とする請求項1または2に記載の半導体記憶装置。
【請求項4】
データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
第2コマンドを受け取ると前記検索情報の複数のエントリから前記第2コマンドにより特定される検索キーを含むエントリを特定するデータを外部に出力し、さらに第3コマンドを受け取ると前記第3コマンドにより特定されるエントリに対応するデータを外部に出力する制御部と、
を具備することを特徴とする半導体記憶装置。
【請求項5】
コマンド解析部をさらに具備し、前記コマンド解析部は、検索キーを特定し、この検索キーに対応するデータを前記メモリから読み出すための第4コマンドを受け取り、前記第4コマンドに基づいて前記第2コマンドと前記第3コマンドを生成することを特徴とする請求項4に記載の半導体記憶装置。
【請求項6】
データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
第5コマンドを受け取ると前記検索情報の複数のエントリから前記第5コマンドにより特定される検索キーを含むエントリに対応する第1データ集合を特定し、さらに第6コマンドを受け取ると前記第6コマンドにより特定される検索キーを含むエントリに対応する第2データ集合を特定し、かつ前記第6コマンドにより指定される集合演算を前記第1データ集合と前記第2データ集合に対して実行し、出力する制御部と、
を具備することを特徴とする半導体記憶装置。
【請求項7】
ID付与部をさらに備え、前記ID付与部は、前記第5コマンド及び前記第6コマンドにより実行される複数の集合演算が並列に実行される場合に、それぞれの集合演算を実行する前記第5コマンドおよび第6コマンドの組に対してIDを付与することを特徴とする請求項6に記載の半導体記憶装置。
【請求項8】
前記検索キーは、少なくとも前記データ中に含まれる単語、データのファイル名、前記ファイル名の拡張子、データの書き換え頻度を含むことを特徴とする請求項1乃至7いずれか1項に記載の半導体記憶装置。
【請求項9】
前記エントリは前記データ毎に備えられ、1つのエントリに複数の検索キーを含むことを特徴とする請求項1乃至8いずれか1項に記載の半導体記憶装置。
【請求項10】
ホスト機器と、
前記ホスト機器と接続された半導体記憶装置を備え、
前記半導体記憶装置は、データと、前記データを特定するための検索キーと前記データが格納されている実アドレスと対応付けたエントリを複数含む検索情報と、を保持するメモリと、
前記ホスト機器から第1コマンドを受け取ると、前記第1コマンドが前記検索キーを特定する場合はこの検索キーを含むエントリに対応するデータを前記ホスト機器に出力し、前記第1コマンドが前記実アドレスを特定する場合はこの実アドレスを含むエントリに対応するデータを前記ホスト機器に出力する制御部と、
を具備することを特徴とする情報処理装置。
【請求項11】
前記半導体記憶装置は、DMAコントローラをさらに具備し、前記実アドレスを特定する第1コマンドは、前記DMAコントローラにより発行されることを特徴とする請求項10に記載の情報処理装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【公開番号】特開2013−30254(P2013−30254A)
【公開日】平成25年2月7日(2013.2.7)
【国際特許分類】
【出願番号】特願2011−167042(P2011−167042)
【出願日】平成23年7月29日(2011.7.29)
【出願人】(000003078)株式会社東芝 (54,554)
【公開日】平成25年2月7日(2013.2.7)
【国際特許分類】
【出願日】平成23年7月29日(2011.7.29)
【出願人】(000003078)株式会社東芝 (54,554)
[ Back to top ]