JP5778640B2 - フレーム検索処理装置および方法 - Google Patents

Description

本発明は、フレーム転送技術に関し、特に入力フレームに応じた処理を決めるための検索を行うフレーム検索処理技術に関する。

ルータやスイッチ、ブリッジにおいてフレームの転送や廃棄、優先制御などを行う場合、入力フレームに応じた処理を決めるため、予め設定されている検索条件と一致するフレームを検索する検索処理が必要である。検索処理は、入力フレームから検索に必要な情報、例えば、ＩＰアドレス等のフレームのヘッダ情報（以下、フレーム情報とする）を抽出し、フレーム情報を検索条件と比較することで結果を出力する。

フレーム検索処理を実現する手法の一つに入力されたフレーム情報と全検索条件とを照合するフレーム検索処理装置がある（非特許文献１）。このフレーム検索処理装置は、複数の検索条件を記憶している検索テーブル（メモリ）と、フレーム情報と検索テーブルのデータを比較し一致判定を行う比較回路とを備えている。検索処理では、フレーム情報が入力されると、検索テーブルへのアクセスを開始し、１クロックサイクル毎に検索条件を読み出し、フレーム情報と比較する。全検索条件との比較が終了した後、結果が出力される。

このフレーム検索処理装置では、読み出した検索条件のビット列と、１つ前に読み出した検索条件との値が異なる場合は、各ビットの信号線の変化（「０」→「１」または「１」→「０」）により電力を消費する。各ビットの信号線の変化による電力消費を低減する手法として、ハミング距離に基づくデータのソートを実行する方法として特許文献１がある。特許文献１では、メモリから読み出すデータの時系列上のハミング距離が最も小さくなるように読み出しデータの順序を並び替えてデータ受け取り側へ伝送し、読み出しデータを並び替え前の読み出し要求順番にデータを再び並び替える。

特開２００７−１４０８５８号公報

M.Urano，T.Kawamura，S.Ohteru，H.Suto，K.Kawai，R.Kusaba，N.Miura，J.Kato，A.Miyazaki，T.Hatano，S.Yasuda，N.Tanaka，S.Shigematsu，M.Nakanishi，T.Shibata，"The 10G-EPON OLT and ONU LSIs for the coexistence of 10G-EPON and GE-PON toward the next FTTH era"，2011 Symposium on VLSI Circuits(VLSIC)，pp.132-133，15-17 June 2011

しかしながら、従来の検索処理装置では、比較する検索条件の順番に制約はなく、ランダムに並べられていたため、信号線の変化による電力消費が必ずしも削減されるものではなかった。また、特許文献１では、読み出す順序が事前に把握できないため、読み出し時のみならず読み出し直後にもソート処理が必要である。そのため、並び替えに必要なバッファやソート処理分のオーバーヘッドが大きくなり、また、一連のメモリアクセス毎にソート処理が必要であるため遅延が増大するという問題点があった。

本発明はこのような課題を解決するためのものであり、フレーム検索処理に要する消費電力を削減できるフレーム検索処理技術を提供することを目的としている。

このような目的を達成するために、本発明にかかるフレーム検索処理装置は、処理対象となるフレームから抽出したフレーム情報を、予め検索テーブルに記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索するフレーム検索処理装置であって、複数の検索条件を予め記憶する前記検索テーブルと、前記検索テーブルから前記検索条件を順次読み出して前記フレーム情報との照合する検索処理を実行し、当該フレーム情報とこれら検索条件との適合有無を示す検索結果を出力する１つ以上の比較回路と、前記検索テーブルに記憶されている前記検索条件について、連続して読み出される２つの検索条件の符号間距離の総和が小さくなる順序で並び替えるためのソート処理を実行するソート処理部と、前記検索テーブルに対する新規検索条件の登録完了を示す外部からの新規登録通知に応じて、前記ソート処理の実行を前記ソート処理部へ指示するソート制御部とを備え、前記検索条件のうち、１つの前記フレーム情報と照合する際に前記検索テーブルから順に読み出される検索条件は、前記符号間距離の総和が小さくなる順序で前記検索テーブルに記憶されている。

また、上記フレーム検索処理装置の一構成例は、前記検索テーブルが、前記検索条件の読み出し・書き込みを並行して実行可能な記憶領域面として、前記検索処理時に前記比較回路での照合に用いる検索条件を記憶するための運用面と、前記ソート処理の対象となる検索条件を記憶するための待機面とを有し、前記ソート処理部は、前記ソート処理時には、前記検索テーブルのうち前記待機面に記憶されている前記検索条件について前記ソート処理を実行し、前記ソート処理部での前記ソート処理の完了に応じて、前記検索テーブルのうち、前記待機面を新たな運用面とするとともに、前記運用面を新たな待機面する切り替えを行う切替制御部をさらに備えている。

また、上記フレーム検索処理装置の一構成例は、前記比較回路として複数の比較回路を備え、前記比較回路における前記検索処理の実行状況に基づいて、これら比較回路のうち前記検索処理を開始可能ないずれか１つの比較回路へ、前記フレーム情報を分配する振り分け回路と、前記フレーム情報を内部バッファに一時的に蓄積し、前記比較回路のうちのいずれかで前記検索処理を開始可能な場合であって、かつ、前記ソート処理部において前記ソート処理が実行されていない場合に、当該内部バッファから前記フレーム情報を取得して前記振り分け回路へ出力するフレーム情報バッファとをさらに備えている。

また、本発明にかかるフレーム検索処理方法は、処理対象となるフレームから抽出したフレーム情報を、予め検索テーブルに記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索するフレーム検索処理装置で用いられるフレーム検索処理方法であって、前記検索テーブルが、複数の検索条件を予め記憶する記憶ステップと、１つ以上の比較回路が、前記検索テーブルから前記検索条件を順次読み出して前記フレーム情報との照合する検索処理を実行し、当該フレーム情報とこれら検索条件との適合有無を示す検索結果を出力する比較ステップと、ソート処理部が、前記検索テーブルに記憶されている前記検索条件について、連続して読み出される２つの検索条件の符号間距離の総和が小さくなる順序で並び替えるためのソート処理を実行するソート処理ステップと、ソート制御部が、前記検索テーブルに対する新規検索条件の登録完了を示す外部からの新規登録通知に応じて、前記ソート処理の実行を前記ソート処理部へ指示するソート制御ステップとを備え、前記検索条件のうち、１つの前記フレーム情報と照合する際に前記検索テーブルから順に読み出される検索条件は、前記符号間距離の総和が小さくなる順序で前記検索テーブルに記憶されている。

また、上記フレーム検索処理装置の一構成例は、前記検索テーブルが、前記検索条件の読み出し・書き込みを並行して実行可能な記憶領域面として、前記検索処理時に前記比較回路での照合に用いる検索条件を記憶するための運用面と、前記ソート処理の対象となる検索条件を記憶するための待機面とを有し、前記ソート処理ステップは、前記ソート処理時には、前記検索テーブルのうち前記待機面に記憶されている前記検索条件について前記ソート処理を実行し、切替制御部が、前記ソート処理部での前記ソート処理の完了に応じて、前記検索テーブルのうち、前記待機面を新たな運用面とするとともに、前記運用面を新たな待機面する切り替えを行う切り替え制御ステップをさらに備えている。

また、上記フレーム検索処理装置の一構成例は、前記比較回路として複数の比較回路を備え、振り分け回路が、前記比較回路における前記検索処理の実行状況に基づいて、これら比較回路のうち前記検索処理を開始可能ないずれか１つの比較回路へ、前記フレーム情報を分配する振り分けステップと、フレーム情報バッファが、前記フレーム情報を内部バッファに一時的に蓄積し、前記比較回路のうちのいずれかで前記検索処理を開始可能な場合であって、かつ、前記ソート処理部において前記ソート処理が実行されていない場合に、当該内部バッファから前記フレーム情報を取得して前記振り分け回路へ出力するバッファステップとをさらに備えている。

本発明によれば、これにより、入力されたフレーム情報と、検索テーブル内の各検索条件とを比較するために、検索テーブルから各検索条件を順に読み出す場合、連続して読み出される２つの検索条件間の符号間距離の総和が小さいことから、これら検索条件を示すデータを続けて読み出した際の各ビットの変化が低減される。
したがって、処理対象となるフレームから抽出したフレーム情報を、予め検索テーブルに記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索する際、これら検索条件の読み出しに要する消費電力が低減されるため、全体として、このようなフレーム検索処理に要する消費電力を削減することが可能となる。

第１の実施の形態にかかるフレーム検索処理装置の構成を示すブロック図である。 第１の実施の形態にかかる検索テーブルの構成例である。 第１の実施の形態にかかる検索テーブルの他の構成例である。 第１の実施の形態にかかるフレーム情報書き込み動作を示すフローチャートである。 第１の実施の形態にかかるフレーム情報読み出し動作を示すフローチャートである。 第１の実施の形態にかかるソートシステムの概要を示す説明図である。 第１の実施の形態にかかるソート制御動作を示すフローチャートである。 第１の実施の形態にかかるソート処理動作を示すフローチャートである。 第１の実施の形態にかかるソート動作の例を示すフローチャートである。 総ハミング距離と消費電力と関係例を示すグラフである。 第１の実施の形態にかかる総ハミング距離の低減例を示す説明図である。 第２の実施の形態にかかるフレーム検索処理装置の構成を示すブロック図である。 第２の実施の形態にかかるフレーム情報読み出し動作を示すフローチャートである。 第２の実施の形態にかかるソート処理動作を示すフローチャートである。 第２の実施の形態にかかる検索テーブル面切り替え動作を示すフローチャートである。

次に、本発明の実施の形態について図面を参照して説明する。
［第１の実施の形態］
まず、図１を参照して、本発明の第１の実施の形態にかかるフレーム検索処理装置１０について説明する。図１は、第１の実施の形態にかかるフレーム検索処理装置の構成を示すブロック図である。

このフレーム検索処理装置１０は、処理対象となるフレームから抽出したフレーム情報を、予め検索テーブルに記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索する機能を有している。実際には、フレーム検索処理装置１０は、独立したＬＳＩとして実現され、あるいは通信用ＬＳＩに組み込まれる。

フレーム検索処理装置１０には、主な処理回路部として、検索テーブル１、比較回路２１〜２Ｎ、振り分け回路３、フレーム情報バッファ４、ソート処理部５、およびソート制御部６が設けられている。

検索テーブル１は、検索条件を記憶する半導体メモリからなり、各メモリアドレスにＭ個（Ｍは２以上の整数）の検索条件を予め記憶する機能を有している。この際、１つのフレーム情報と照合する際に検索テーブル１から順に読み出される検索条件は、連続して読み出される２つの検索条件の符号間距離の総和が小さくなる順序で検索テーブル１に記憶されている。

比較回路２１〜２Ｎは、Ｎ個（Ｎは１以上の整数）の比較回路からなり、検索テーブル１から検索条件を順次読み出してフレーム情報との照合する検索処理を実行し、当該フレーム情報とこれら検索条件との適合有無を示す検索結果を出力する機能を有している。
フレーム情報としては、処理対象となるフレームのうち、例えば、ヘッダ情報に含まれるＩＰアドレスやＭＡＣアドレス、さらにはペイロード部の一部に格納された制御情報など、各種の情報が用いられる。

振り分け回路３は、Ｎが２以上、つまり比較回路２１〜２Ｎが並列化されている場合、複数のフレーム情報を並列的に検索処理するために、入力されたフレーム情報を比較回路２１〜２Ｎのうちのいずれか１つに分配する機能を有している。
フレーム情報バッファ４は、入力されたフレーム情報を一時的に蓄積して振り分け回路３へ出力することで送出制御を行う機能を有している。

ソート処理部５は、検索テーブル１に記憶されている各検索条件について、符号間距離（ハミング距離）の総和、すなわち総ハミング距離が小さくなる順序で並び替えるためのソート処理を実行する機能を有している。
ソート制御部６は、検索テーブル１に対する新規検索条件の登録完了を示す外部からの新規登録通知に応じて、ソート処理の実行をソート処理部５へ指示する機能を有している。

総ハミング距離とは、１つのフレーム情報の検索処理で読み出される全検索条件において、連続して読み出される２つの検索条件間の符号間の距離（ハミング距離）の総和であり、つまり、１つのフレーム情報の検索処理において読み出される検索条件の符号の変化（「０」→「１」または「１」→「０」）の総和である。

［第１の実施の形態の動作］
次に、本実施の形態にかかるフレーム検索処理装置１０の動作について説明する。

まず、図２を参照して、検索テーブル１の詳細な構成について記述する。図２は、第１の実施の形態にかかる検索テーブルの構成例である。
検索テーブル１には、各メモリアドレスにＭ個（Ｍは２以上の整数）の検索条件が予め登録されている。各比較回路２１〜２Ｎへ検索条件が分配されるとき、各比較回路２１〜２Ｎは、メモリアドレスを指定することにより、検索テーブル１から検索条件を１クロックサイクルで読み出す。１クロックサイクルで検索テーブル１から読み出された検索条件は全ての比較回路２１〜２Ｎへ送られる。そして、各比較回路２１〜２Ｎは、比較終了後に、検索テーブル１から読み出した検索条件を消去し、検索テーブル１から次検索条件を１クロックサイクルで読み出す。

こうして、各比較回路２１〜２Ｎは、検索テーブル１から検索条件を読み出してフレーム情報との比較を行うことを繰り返し、検索テーブル１の全検索条件（Ｍ個）とフレーム情報とを比較し終えたとき、すなわち、Ｍクロックサイクル経過後に、検索結果（比較結果）を出力する。そして、各比較回路２１〜２Ｎは、検索結果の出力後、検索処理のために記憶していたフレーム情報を消去する。

図３は、第１の実施の形態にかかる検索テーブルの他の構成例である。検索テーブル１は、上記の構成に限らず、例えば図３のように、全検索条件数（Ｍ個）をＬ個（Ｌは１以上の整数）のテーブルに分割する構成もある。この場合、Ｍ／Ｌクロックサイクル経過後に、検索結果を出力する。

次に、図４を参照して、フレーム検索処理装置１０の外部より入力されたフレーム情報をフレーム情報バッファ４へ書き込むときの動作を説明する。図４は、第１の実施の形態にかかるフレーム情報書き込み動作を示すフローチャートである。

フレーム情報バッファ４は、フレーム情報が入力されると、まず内部バッファの空き情報を取得して（ステップ１００）、空きがあるかどうかを確認する（ステップ１０１）。内部バッファに空きがある場合（ステップ１０１：ＹＥＳ）、フレーム情報を内部バッファへ書き込み（ステップ１０２）、一連の動作を終了する。内部バッファに空きがない場合（ステップ１０１：ＮＯ）、入力されたフレーム情報を廃棄し（ステップ１０３）、一連の動作を終了する。フレーム情報バッファ４は、以上の処理をフレーム情報が入力される度に行う。

次に、図５を参照して、フレーム情報バッファ４からフレーム情報を読み出し、振り分け回路３へ出力するときの動作を説明する。図５は、第１の実施の形態にかかるフレーム情報読み出し動作を示すフローチャートである。
フレーム情報を出力する場合、比較回路２１〜２Ｎに空きがあることを示す比較回路２１〜２Ｎからの出力許可が必要となる。

まず、フレーム情報バッファ４は、比較回路２１〜２Ｎから空き有無情報を取得し（ステップ１１０）、出力許可があるか否かに基づき比較回路２１〜２Ｎに空きがあるかどうかを確認する（ステップ１１１）。この空き有無情報は、比較回路２１〜２Ｎのうちの検索処理を開始可能な状態、すなわち空き状態にある比較回路が存在するか否かを示す情報であり、例えば各比較回路２１〜２Ｎから、検索処理の実行状況として、検索処理実行中に出力される検索処理中情報を、論理積することにより得られる。
空き有無情報が、全ての比較回路２１〜２Ｎに空きがないことを示している場合（ステップ１１１：ＮＯ）、フレーム情報バッファ４は、フレーム情報を出力せずに一連の動作を終了する。

一方、空き有無情報が少なくとも１つの比較回路に空きがあることを示している場合（ステップ１１１：ＹＥＳ）、フレーム情報バッファ４は、ソート処理中であるか否かを示すソート制御部６からの処理中情報を取得する（ステップ１１２）。この処理中情報は、ソート処理部５に対してソート処理の実行を指示してから、ソート処理部５からソート処理完了が通知されるまでの期間について、ソート処理中を示す情報であり、ソート制御部６から出力される。

ここで、処理中情報がソート処理中であることを示している場合（ステップ１１３：ＮＯ）、フレーム情報バッファ４は、フレーム情報を出力せずに一連の動作を終了する。
また、処理中情報がソート処理中でないことを示している場合（ステップ１１３：ＹＥＳ）、フレーム情報バッファ４は、振り分け回路３へフレーム情報を出力し（ステップ１１４）、一連の動作を終了する。

なお、ソート処理中は検索処理が停止するため、フレーム情報バッファ４は、ソート処理中に外部から入力されたフレーム情報を蓄積する。なお、ソート処理中にフレーム情報が入力された場合はソート処理を中断し、検索処理を再開することもある。

次に、図６を参照して、検索条件のソート制御方法について詳細に説明する。図６は、第１の実施の形態にかかるソートシステムの概要を示す説明図である。
検索条件のソートシステムは、ソート制御部６とソート処理部５から構成される。
ソート制御部６は、検索処理中のフレーム情報の有無や新規検索条件の登録を監視し、所定の条件を満たした場合に、ソート処理部５へソート処理実行を指示する。
ソート処理部５は、ソート制御部６からのソート処理実行指示を契機にして、検索条件１Ａを読み込み、所定のソート処理を実行し、ソート後の検索条件１Ｂを出力する。

ソート処理部５では、検索条件のソート処理を行い、検索テーブル１への書き込み許可が得られるまでソート処理後の検索条件を中間ファイル１Ｃで保持することもある。中間ファイル１Ｃは、フレーム検索処理装置１０の内部または外部に設けられたメモリで記憶される。

次に、図７を参照して、ソート制御部６について詳細に説明する。図７は、第１の実施の形態にかかるソート制御動作を示すフローチャートである。
ソート制御部６は、所定の条件を満たした場合に、ソート処理部５へソート処理実行を指示する。

検索テーブル１に新規検索条件を登録する場合、外部の上位装置から検索テーブル１に対して、新規検索条件が登録される。この際、検索テーブル１に対する新規検索条件の登録完了を示す新規登録通知が、外部の上位装置からソート制御部６へ入力される。
まず、ソート制御部６は、外部から入力される新規登録通知に応じて、新規検索条件の登録の有無を確認し（ステップ１２０）、新規検索条件の登録がある場合（ステップ１２０：ＹＥＳ）、検索処理中のフレーム情報の有無、およびフレーム情報バッファ４におけるフレーム情報の蓄積を確認する（ステップ１２１，１２２）

検索処理中のフレーム情報の有無は、例えば、各比較回路２１〜２Ｎから検索処理実行中に出力される検索処理中情報を、論理和することにより得られる。これにより、比較回路２１〜２Ｎで検索処理が実行されているかどうか、すなわち検索テーブル１内の検索条件をソートしてはいけない状況にあるかどうかが確認される。
フレーム情報バッファ４におけるフレーム情報の蓄積は、例えば、内部バッファでフレーム情報を１つ以上蓄積されている場合に、フレーム情報バッファ４から出力されるフレーム情報蓄積中情報により確認される。これにより、優先して実行すべき比較回路２１〜２Ｎで検索処理が存在しており、検索テーブル１内の検索条件に対するソート処理を後回しにすべき状況かどうかが確認される。

ここで、検索処理中のフレーム情報がなく（ステップ１２１：ＮＯ）、かつフレーム情報バッファ４にフレーム情報の蓄積がない場合に（ステップ１２２：ＮＯ）、ソート制御部６は、ソート処理実行を指示して（ステップ１２３）、一連の動作を終了する。
一方、検索処理中のフレーム情報がある場合や（ステップ１２１：ＹＥＳ）、フレーム情報バッファ４にフレーム情報の蓄積がある場合（ステップ１２２：ＹＥＳ）、ソート制御部６は、ソート処理実行の命令は出さずに、一連の動作を終了する。

なお、ソート制御の方法は上記に限らず、新規検索条件の登録数が所定の数に達したか否かを判定基準として動作に追加し、所定の数に達した場合にソート処理実行を指示することもある。この場合、ソート処理実行の頻度を調整できるため、頻繁に検索条件の登録・削除がある場合に、頻繁なソート処理による電力の増加を抑える効果がある。
また、ソート制御部６が、現在の検索テーブル１に記憶される検索条件の総ハミング距離を取得し、総ハミング距離が所定数以上であるか否かを判定する処理を上記動作に追加し、総ハミング距離が所定数以上である場合、ソート処理実行を指示することもある。
また、ソート制御部６が、新規検索条件の登録時に、ソート処理前の検索テーブル１に記憶される検索条件の総ハミング距離と、ソート処理後の総ハミング距離とを取得し、両者の差分が所定の値以上である場合に検索テーブル１を更新することもある。

次に、図８を参照して、ソート処理部５について詳細に説明する。図８は、第１の実施の形態にかかるソート処理動作を示すフローチャートである。
ソート処理部５は、ソート制御部６からのソート処理実行の指示を契機に、ソート処理を実行する。

まず、ソート処理部５は、検索テーブル１から検索条件を読み出し（ステップ１３０）、所定のソート処理を実行する（ステップ１３１）。このソート処理の内容については後述する。ソート処理部５は、このソート処理で順次得られるソート結果を、一時的に中間ファイルで保持する（ステップ１３２）。

全検索条件のソートが完了した時点で（ステップ１３３：ＹＥＳ）、ソート処理部５は、中間ファイルに保持されているソート結果を検索テーブル１へ書き込んで更新し（ステップ１３４）、一連の動作を終了する。
なお、検索テーブル１からの書き込み許可がある場合、ソート処理部５が、ソート途中の検索条件を中間ファイルで保持することなく検索テーブル１へ書き込むことで更新することもある。この際、書き込み許可は、比較回路２１〜２Ｎからの検索条件の読み出し中に検索テーブル１から出力される読み出し中情報により確認してもよく、あるいは、各比較回路２１〜２Ｎから検索処理実行中に出力される検索処理中情報を、論理和することにより確認してもよい。

次に、図９を参照して、ソート処理部５における検索条件のソート動作について説明する。図９は、第１の実施の形態にかかるソート動作を示すフローチャートである。
総ハミング距離が最小となる検索条件のソートは、全ての検索条件を１回ずつ選択し最初の検索条件へ戻るという制約条件下において、総ハミング距離が最短になる順番を探索することである。ソートの方法の最適解は現実的な計算時間で厳密な最適解を求めることが困難であることが知られているが、近似解法が存在する。近似解法の１つとして、最近傍法（Ｎｅａｒｅｓｔ Ｎｅｉｇｈｂｏｒ法、以下、ＮＮ法）がある。本実施の形態では、基本的なソート動作として、ＮＮ法に基づくソート動作の例を示す。

まず、ソート処理部５は、ソートの対象となる各検索条件のうちから、最初の検索条件を適当に（任意に）選択する（ステップ１４０）。次に、ソート処理部５は、選択中の検索条件と未選択の各検索条件とのハミング距離を計算し（ステップ１４１）、未選択の検索条件の中から、選択中の検索条件と最もハミング距離の近い検索条件を選択する（ステップ１４２）。このとき、条件を満たす検索条件が複数存在する場合は、記憶されていたメモリアドレスの若い番号を優先することとする。なお、各検索条件間のハミング距離の計算は、ステップ１４０の前にすべて実行しておいてもよい。

次に、全ての検索条件が選択されたか否かを判定し（ステップ１４３）、全検索条件の選択が終了していない場合（ステップ１４３：ＮＯ）、ソート処理部５は、ステップ１４１へ戻って、再度、ハミング距離を計算し、未選択の検索条件の中から、現在の検索条件と最もハミング距離の近い検索条件を選択する。
一方、全ての検索条件が選択された場合（ステップ１４３：ＹＥＳ）、ソート処理部５は、一連の動作を終了する。

なお、総ハミング距離を低減するソート動作は上記に限らず、ソート動作における最初に選択する検索条件を変更して複数回ソートを実行し、最も総ハミング距離が小さいソート結果を採用する動作もある。また、組み合わせ最適化問題に対する近似解法には、最近追加法（Ｎｅａｒｅｓｔ Ａｄｄｉｔｉｏｎ Ｍｅｔｈｏｄ法）や局所探索法などが知られており、それらを適用することもある。

また、近似解法のうち複数の近似解法を組み合わせて用いる動作もある。また、複数の検索条件に共通する部分がある場合、例えば、検索条件の上位または下位数ビットが同じ値などの場合は、検索条件の値の異なる部分を対象として、つまり同じ値の部分を無視して、２つの検索条件間のハミング距離と定義し、ソートを行うこともある。

また、新規に登録された検索条件と既に登録されている検索条件とのハミング距離を計算し、最もハミング距離が小さくなる箇所に新規検索条件を登録する方法もある。この場合、全検索条件を対象にソート処理を実施せずに済むため、ソート処理の簡略化が図れ、処理時間が低減する。
また、検索条件が削除された場合には、ソート処理を実施しないこともある。この場合、検索条件の削除にともなうソート処理の実施が不要になるため、ソート処理の実施回数を削減できる効果がある。

また、総ハミング距離と消費電力との間には、一定の相関関係が存在する。図１０は、総ハミング距離と消費電力と関係例を示すグラフである。ここでは、横軸が総ハミング距離を示し、縦軸が消費電力の増分を示しており、任意のフレーム検索処理装置において、ＮＮ法を用いてソートした検索条件を用いて、フレーム検索処理を実行した際に実測された消費電力の増分がプロットされている。これによれば、総ハミング距離の増加に応じて消費電力の増分が単調増加していることが分かる。

実際に、検索条件をソートする場合、総ハミング距離が最小となるソート結果を得るには、無視できない長さの計算時間を要し、総ハミング距離が最小ではなく、ある程度小さいソート結果でよければ、この計算時間を短縮できる。フレーム情報に対する検索処理を遅延させることなく実行するには、計算時間を短くすべきであり、これにより、ソート処理時に消費する電力も削減できる。

フレーム検索処理装置１０に関する図１０のグラフを予め求めておき、目標となる消費電力の削減量を設定すれば、これを実現するために必要となる総ハミング距離の目標値を求めることができる。
したがって、ソート処理部５において、ソート処理方法やそのパラメータを切り替え選択するなどして、総ハミング距離が最小ではなく、この目標値以下となるよう、検索条件をソートすればよいことになる。これにより、検索条件のソートに要する計算時間を短縮でき、結果として、フレーム情報に対する検索処理の遅延を削減できるとともに、検索条件のソートに要する消費電力も削減できる。

次に、図１１を参照して、検索テーブル１に記憶される検索条件のソート処理の実行による総ハミング距離が低減する例を説明する。図１１は、第１の実施の形態にかかる総ハミング距離の低減例を示す説明図である。

前述のように、フレーム検索処理装置１０では、１クロックサイクル毎に異なるメモリアドレスから検索条件を読み出す。このとき、読み出した検索条件の各ビットで、１つ前に読み出した検索条件との値が異なると、各ビットの信号線のスイッチングが生じ、電力を消費する。この電力は、２つの検索条件間のハミング距離に依存する。なお、本実施の形態では、検索条件はメモリアドレス順に巡回的に読み出されるため、予め読み出す順番が把握される。また、本実施の形態では、必ずしも第１のメモリアドレスから検索条件を読み出す必要はなく、つまりフレーム情報と検索条件との比較順番に制約がなく、比較する順番によって得られる検索結果が異なることがない。

本実施の形態では、予め検索条件を読み出す順番が把握できることを利用して、順不同に並べられた検索条件を、読み出す検索条件の各ビットの信号線の変化（「０」→「１」または「１」→「０」）が最も小さくなるように、つまり、ハミング距離の総和（総ハミング距離）が低減するようにソート処理を実行する。

図１１では、検索条件がそれぞれ８ビット長であり、全検索条件数が６、すなわちＭ＝６、ＮＮ法に基づくソート動作によりソートした場合の例を示している。
すなわち、ソート前のメモリアドレス＃２に記憶される検索条件（１１１０１０１０）は、ソート処理の結果、メモリアドレス＃４に記憶され、ソート前のメモリアドレス＃３に記憶される検索条件（０１１１０１０１）は、ソート処理の結果、メモリアドレス＃２に記憶される。

また、ソート前のメモリアドレス＃４に記憶される検索条件（１０１１１０１０）は、ソート処理の結果、メモリアドレス＃５に記憶され、ソート前のメモリアドレス＃５に記憶される検索条件（０１０１１１０１）は、ソート処理の結果、メモリアドレス＃３に記憶され、ソート前のメモリアドレス＃１および＃６に記憶される検索条件（１１０１０１０１および１０１０１１１０）は、ソート後も記憶されるメモリアドレスに変更は無い。

次に、ソート前後における、２つの検索条件間のハミング距離の変化について説明する。ソート前では、メモリアドレス順に検索条件を読み出した場合、直前の検索条件とのハミング距離はそれぞれ「６」ｂｉｔであり、検索条件の読み出しサイクルが一巡したとき、つまり１つのフレーム情報の検索処理が終了したとき、ハミング距離の総和（総ハミング距離）は「３６」ｂｉｔである。

一方、ソート後では、メモリアドレス＃１と＃２、＃２と＃３、＃４と＃５、＃５と＃６の間でハミング距離が「２」ｂｉｔであったために、総ハミング距離は「２０」ｂｉｔである。なお、ソート前後において、メモリアドレス順に読み出した場合の検索条件の読み出し順番は変化するが、検索条件に変化はないため、比較回路２１〜２Ｎが出力する検索結果は変化しない。

以上のように、本実施の形態では、検索条件をソートすることで、フレーム情報の検索処理に必要である検索テーブル１へのアクセス動作により消費する電力を削減することができる。例えば、１つのフレーム情報の検索において、各１２８ｂｉｔ、５１２個の検索条件と比較するフレーム検索処理装置１０において、総ハミング距離が「０」ｂｉｔ、すなわち全検索条件が同じ値である場合と、総ハミング距離が「６５５３６」ｂｉｔ（１２８ｂｉｔ×５１２個の検索条件）、すなわち毎クロックサイクル異なる値を読み出す場合とでは、消費電力は４５ｍＷ程度増加する。

［第１の実施の形態の効果］
このように、本実施の形態は、複数の検索条件を、各メモリアドレスに予め記憶する検索テーブル１と、この検索テーブル１から検索条件を順次読み出してフレーム情報との照合する検索処理を実行し、当該フレーム情報とこれら検索条件との適合有無を示す検索結果を出力する１つ以上の比較回路２１〜２Ｎ（Ｎは１以上の整数）とを備え、検索条件のうち、１つのフレーム情報と照合する際に検索テーブル１から順に読み出される検索条件が、連続して読み出される２つの検索条件の符号間距離の総和が小さくなる順序で検索テーブル１に記憶されているものである。

これにより、入力されたフレーム情報と、検索テーブル１内の各検索条件とを比較するために、検索テーブル１から各検索条件を順に読み出す場合、連続して読み出される２つの検索条件間の符号間距離の総和が小さいことから、これら検索条件を示すデータを続けて読み出した際の各ビットの変化が低減される。
したがって、処理対象となるフレームから抽出したフレーム情報を、予め検索テーブル１に記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索する際、これら検索条件の読み出しに要する消費電力が低減されるため、全体として、このようなフレーム検索処理に要する消費電力を削減することが可能となる。

また、本実施の形態において、ソート処理部５が、検索テーブル１に記憶されている検索条件について、符号間距離の総和が小さくなる順序で並び替えるためのソート処理を実行し、ソート制御部６が、検索テーブル１に対する新規検索条件の登録完了を示す外部からの新規登録通知に応じて、ソート処理の実行をソート処理部５へ指示するようにしてもよい。
これにより、検索テーブル１に対する新規検索条件の登録に応じて、検索条件がソートされるため、検索テーブル１内の検索条件に関する符号間距離の総和を小さく保つことができる。したがって、新規検索条件が登録された後についても、フレーム検索処理に要する消費電力を削減した状態に維持することが可能となる。

さらに、本実施の形態において、複数の比較回路２１〜２Ｎを備え、振り分け回路３が、比較回路２１〜２Ｎにおける検索処理の実行状況に基づいて、これら比較回路２１〜２Ｎのうち検索処理を開始可能ないずれか１つの比較回路へ、フレーム情報を分配し、フレーム情報バッファ４が、フレーム情報を内部バッファに一時的に蓄積し、比較回路２１〜２Ｎのうちのいずれかで検索処理を開始可能な場合であって、かつ、ソート処理部５においてソート処理が実行されていない場合に、当該内部バッファからフレーム情報を取得して振り分け回路３へ出力するようにしてもよい。

これにより、ソート処理部５でのソート処理による、検索テーブル１の検索条件へのアクセスとの競合を調停しつつ、順次入力されるフレーム情報に対する検索処理を、各比較回路２１〜２Ｎで並列的に実行することができ、スループットを高めることができる。

次に、前述した特許文献１との相違点について説明する。特許文献１では、メモリから出力するデータの時系列上のハミング距離が最も小さくなるようにメモリ出力データの順序をソートしてデータ受け取り側へ伝送し、読み出したデータをソート前のデータの順番に戻す。つまり、読み出す順序が事前に把握できないため、読み出し時にソート処理が必要であり、遅延の増加が生じる。

それに対し、本発明では検索テーブル１からの検索条件の読み出しはメモリアドレスの順番に従うため、検索条件の読み出し順番を事前に把握できる。そのため、検索テーブル１から読み出される前に、つまり検索テーブル１に記憶されている段階から読み出すメモリアドレス順に並べたときの総ハミング距離が最小になるようにソートすることができる。

また、特許文献１では、メモリアクセス毎に出力データのソート処理を実行するが、本実施の形態では、ソート制御により、ソートの頻度を低減するため、頻繁なソート処理の実行による検索処理の遅延の増加や、ソート処理の実行に伴う消費電力の増加を抑えることができる。
また、一般に、フレーム検索処理装置に入力されるフレーム情報は時々刻々と変化する（非固定）のに対し、検索テーブル１に登録される検索条件は、比較的固定である。そのため、メモリから読み出すときにソート処理を実行するのではなく、予めソート処理を実行し、総ハミング距離が低減したデータを一定期間使用することができる効果がある。

なお、検索テーブル１の総ハミング距離を低減する方法は上記に限らない。例えば、読み出す検索条件内に、この検索条件が有効であるか否かを示す有効ビットが含まれる場合、有効ビットが無効である検索条件には直前に読み出す検索条件と同じ値、または次に有効になる検索条件と同じ値を設定しておくことで、総ハミング距離を低減することもある。

また、本実施の形態では、メモリアドレス順に検索条件を読み出す例を示したが、検索条件の読み出し順番は上記に限らない。例えば、読み出す順番に配列したメモリアドレスを記憶したテーブルを別途設け、テーブルに記憶されたメモリアドレス順に検索条件を読み出すこともある。この場合、メモリアドレスをソートすることで、読み出す検索条件の総ハミング距離を低減する。

また、本実施の形態では、検索テーブル１のソート処理中は検索処理を停止する例を示したが、ソート制御方法は上記に限らず、検索処理中でもソート処理を実施する制御方法もある。例えば、検索テーブル１に登録可能な最大の検索条件数（Ｍ）よりも、有効ビットが有効な検索条件の数が少ない場合、つまり、検索テーブル１に空きがある場合、まず有効な条件をコピーし、次に有効ビットを有効にする。検索条件の読み出しが一巡した後、次に、元の検索条件の有効ビットを無効にする。上記によれば、一時的に同じ検索条件を２回読み出すことになるが、検索結果に影響なく、また検索処理を停止することなくソート制御ができる。

［第２の実施の形態］
次に、図１２を参照して、本発明の第２の実施の形態にかかるフレーム検索処理装置１０について説明する。図１２は、第２の実施の形態にかかるフレーム検索処理装置の構成を示すブロック図である。

第１の実施の形態と異なる点は、検索テーブル１が、各メモリアドレスにＭ個（Ｍは２以上の整数）の検索条件を予め記憶するとともに、検索条件の読み出し・書き込みを並行して実行可能な記憶領域面である、Ｌ個の面（Ｌは２以上の整数）から構成されており、検索テーブル１のこれら面の切り替え制御を行う切替制御部６を備える点である。検索テーブル１については、例えば、複数のバンクを有するマルチポートメモリなど、一般的な半導体メモリを用いればよい。

Ｌが２である場合は、実際に検索処理に用いられ、各比較回路２１〜２Ｎへ検索条件を分配する面（以下、運用面）に加えて、新規検索条件の登録や、検索条件のソート処理用に用いる待機用の面（以下、待機面）を備えていることに相当する。
ソート処理部５は、ソート処理時には、検索テーブル１のうち待機面に記憶されている検索条件についてソート処理を実行する。

切替制御部７は、ソート処理部５でのソート処理の完了に応じて、検索テーブル１のうち、待機面を新たな運用面とするとともに、運用面を新たな待機面する切り替えを行う機能を有している。
本実施の形態にかかるこのほかの構成については、第１の実施の形態と同様であり、ここでの説明は省略する。

［第２の実施の形態の動作］
次に、本実施の形態にかかるフレーム検索処理装置１０の動作として、検索テーブル１が運用面と待機面で構成される場合、つまりＬが２の場合を用いて、第１の実施の形態と異なる点を中心に詳細に説明する。

まず、図１３を参照して、フレーム情報バッファ４からフレーム情報を読み出し、振り分け回路３へ出力するときの動作を詳細に説明する。図１３は、第２の実施の形態にかかるフレーム情報読み出し動作を示すフローチャートである。
フレーム情報の出力では比較回路２１〜２Ｎに空きがあることを示す比較回路２１〜２Ｎからの出力許可が必要である。この場合、第１の実施の形態と異なり、ソート処理中でも運用面を用いて検索処理を実行できるためソート制御部６からの処理中情報の確認が不要である。

まず、フレーム情報バッファ４は、比較回路２１〜２Ｎから空き有無情報を取得し（ステップ２００）、出力許可があるか否かに基づき比較回路２１〜２Ｎに空きがあるかどうかを確認する（ステップ２０１）。この空き有無情報は、比較回路２１〜２Ｎのうちの検索処理を開始可能な状態、すなわち空き状態にある比較回路が存在するか否かを示す情報であり、例えば各比較回路２１〜２Ｎから、検索処理の実行状況として、検索処理実行中に出力される検索処理中情報を、論理積することにより得られる。

空き有無情報が、全ての比較回路２１〜２Ｎに空きがないことを示している場合（ステップ２０１：ＮＯ）、フレーム情報バッファ４は、フレーム情報を出力せずに一連の動作を終了する。
一方、空き有無情報が少なくとも１つの比較回路に空きがあることを示している場合（ステップ２０１：ＹＥＳ）、フレーム情報バッファ４は、振り分け回路３へフレーム情報を出力し（ステップ２０２）、一連の動作を終了する。

次に、図１４を参照して、検索条件のソート処理の動作を詳細に説明する。図１４は、第２の実施の形態にかかるソート処理動作を示すフローチャートである。
ソート処理部５は、ソート制御部６からのソート処理実行の指示を契機に、ソート処理を実行する。

まず、ソート処理部５は、検索テーブル１の待機面から検索条件を読み出し（ステップ２１０）、所定のソート処理を実行する（ステップ２１１）。このソート処理の内容については、第１の実施の形態と同様である。
ソート処理部５は、このソート処理で順次得られるソート結果を、待機面へ書き込み（ステップ２１２）、全検索条件のソートが完了した時点で、一連の動作を終了する。

所定の条件を満たしている場合、面の切り替えを行うことで、検索テーブル１を更新する。面の切り替え制御については後述する。
本実施の形態では、ソート処理の実行中でも検索処理を継続することができるため、ソート処理の実行に伴う遅延の増大を抑える効果がある。なお、検索テーブル１の待機面への書き込み許可が得られるまでは中間ファイルで保持することもある。また、ソート処理に伴う検索条件の読み込みは、運用面または待機面から行う。

次に、図１５を参照して、切替制御部７について詳細に説明する。図１５は、第２の実施の形態にかかる検索テーブル面切り替え動作を示すフローチャートである。

まず、切替制御部７は、ソート処理部５でのソート処理が完了したか否かを確認する（ステップ２２０）。ソート処理の完了については、例えば、前述したソート制御部６からの処理中情報を用いればよい。
ここで、ソート処理が完了している場合（ステップ２２０：ＹＥＳ）、切替制御部７は、検索処理中のフレーム情報の有無を確認する（ステップ２２１）。検索処理中のフレーム情報の有無については、例えば、前述した比較回路２１〜２Ｎからの検索処理中情報の論理和を用いればよい。

検索処理中のフレーム情報がない場合（ステップ２２１：ＮＯ）、切替制御部７は、検索テーブル１のうち、待機面を新たな運用面とするとともに、運用面を新たな待機面する切り替えを行い（ステップ２２２）、一連の動作を終了する。
一方、ソート処理が完了していない場合や（ステップ２２０：ＮＯ）、検索中のフレーム情報がある場合（ステップ２２１：ＹＥＳ）、切替制御部７は、検索テーブル１の面の切り替えを実行せずに、一連の動作を終了する。

切替制御部７は、ソート処理部５がソート処理を行うごとに、以上の処理を実行する。なお、ソート制御は上記に限らず、例えば、待機面と運用面の切り替えが実行される直前に、待機面の検索条件のソート処理を実行することもある。

［第２の実施の形態の効果］
このように、本実施の形態では、検索テーブル１に、検索条件の読み出し・書き込みを並行して実行可能な記憶領域面として、検索処理時に比較回路２１〜２Ｎでの照合に用いる検索条件を記憶するための運用面と、ソート処理の対象となる検索条件を記憶するための待機面とを設け、ソート処理部５が、ソート処理時には、検索テーブル１のうち待機面に記憶されている検索条件についてソート処理を実行し、切替制御部７が、ソート処理部５でのソート処理の完了に応じて、検索テーブル１のうち、待機面を新たな運用面とするとともに、運用面を新たな待機面する切り替えを行うようにしたものである。

これにより、待機面を利用してソート処理が実行されるため、ソート処理中でも検索処理の実行が可能となり、遅延時間の増大を抑えることができる。また、検索条件のソート処理に伴う遅延時間増大の抑制により、ソート処理中に入力されたフレーム情報を蓄積するためのフレーム情報バッファ４などのオーバーヘッドを最小限にすることができる。このため、振り分け回路３の前段に設けられているフレーム情報バッファ４の容量の増大を抑えることも可能となる。

第１、第２の実施の形態で説明したフレーム検索処理装置１０は、例えばＣＰＵ、記憶装置及びインタフェースを備えたコンピュータと、これらのハードウェア資源を制御するプログラムによって実現することができる。ＣＰＵは、記憶装置に格納されたプログラムに従って第１、第２の実施の形態で説明した処理を実行する。

［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。

１０…フレーム検索処理装置、１…検索テーブル、２１〜２Ｎ…比較回路、３…振り分け回路、４…フレーム情報バッファ、５…ソート処理部、６…ソート制御部、７…切替制御部。

Claims (6)

1. 処理対象となるフレームから抽出したフレーム情報を、予め検索テーブルに記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索するフレーム検索処理装置であって、
   複数の検索条件を予め記憶する前記検索テーブルと、
   前記検索テーブルから前記検索条件を順次読み出して前記フレーム情報との照合する検索処理を実行し、当該フレーム情報とこれら検索条件との適合有無を示す検索結果を出力する１つ以上の比較回路と、
   前記検索テーブルに記憶されている前記検索条件について、連続して読み出される２つの検索条件の符号間距離の総和が小さくなる順序で並び替えるためのソート処理を実行するソート処理部と、
   前記検索テーブルに対する新規検索条件の登録完了を示す外部からの新規登録通知に応じて、前記ソート処理の実行を前記ソート処理部へ指示するソート制御部とを備え、
   前記検索条件のうち、１つの前記フレーム情報と照合する際に前記検索テーブルから順に読み出される検索条件は、前記符号間距離の総和が小さくなる順序で前記検索テーブルに記憶されている
   ことを特徴とするフレーム検索処理装置。
2. 請求項１記載のフレーム検索処理装置において、
   前記検索テーブルは、前記検索条件の読み出し・書き込みを並行して実行可能な記憶領域面として、前記検索処理時に前記比較回路での照合に用いる検索条件を記憶するための運用面と、前記ソート処理の対象となる検索条件を記憶するための待機面とを有し、
   前記ソート処理部は、前記ソート処理時には、前記検索テーブルのうち前記待機面に記憶されている前記検索条件について前記ソート処理を実行し、
   前記ソート処理部での前記ソート処理の完了に応じて、前記検索テーブルのうち、前記待機面を新たな運用面とするとともに、前記運用面を新たな待機面する切り替えを行う切替制御部をさらに備える
   ことを特徴とするフレーム検索処理装置。
3. 請求項１または２に記載のフレーム検索処理装置において、
   前記比較回路として複数の比較回路を備え、
   前記比較回路における前記検索処理の実行状況に基づいて、これら比較回路のうち前記検索処理を開始可能ないずれか１つの比較回路へ、前記フレーム情報を分配する振り分け回路と、
   前記フレーム情報を内部バッファに一時的に蓄積し、前記比較回路のうちのいずれかで前記検索処理を開始可能な場合であって、かつ、前記ソート処理部において前記ソート処理が実行されていない場合に、当該内部バッファから前記フレーム情報を取得して前記振り分け回路へ出力するフレーム情報バッファと
   をさらに備えることを特徴とするフレーム検索処理装置。
4. 処理対象となるフレームから抽出したフレーム情報を、予め検索テーブルに記憶されている複数の検索条件と順に照合することにより、これら検索条件のいずれかと適合したフレームを検索するフレーム検索処理装置で用いられるフレーム検索処理方法であって、
   前記検索テーブルが、複数の検索条件を予め記憶する記憶ステップと、
   １つ以上の比較回路が、前記検索テーブルから前記検索条件を順次読み出して前記フレーム情報との照合する検索処理を実行し、当該フレーム情報とこれら検索条件との適合有無を示す検索結果を出力する比較ステップと、
   ソート処理部が、前記検索テーブルに記憶されている前記検索条件について、連続して読み出される２つの検索条件の符号間距離の総和が小さくなる順序で並び替えるためのソート処理を実行するソート処理ステップと、
   ソート制御部が、前記検索テーブルに対する新規検索条件の登録完了を示す外部からの新規登録通知に応じて、前記ソート処理の実行を前記ソート処理部へ指示するソート制御ステップとを備え、
   前記検索条件のうち、１つの前記フレーム情報と照合する際に前記検索テーブルから順に読み出される検索条件は、前記符号間距離の総和が小さくなる順序で前記検索テーブルに記憶されている
   ことを特徴とするフレーム検索処理方法。
5. 請求項４記載のフレーム検索処理方法において、
   前記検索テーブルは、前記検索条件の読み出し・書き込みを並行して実行可能な記憶領域面として、前記検索処理時に前記比較回路での照合に用いる検索条件を記憶するための運用面と、前記ソート処理の対象となる検索条件を記憶するための待機面とを有し、
   前記ソート処理ステップは、前記ソート処理時には、前記検索テーブルのうち前記待機面に記憶されている前記検索条件について前記ソート処理を実行し、
   切替制御部が、前記ソート処理部での前記ソート処理の完了に応じて、前記検索テーブルのうち、前記待機面を新たな運用面とするとともに、前記運用面を新たな待機面する切り替えを行う切り替え制御ステップをさらに備える
   ことを特徴とするフレーム検索処理方法。
6. 請求項４または５に記載のフレーム検索処理方法において、
   前記比較回路として複数の比較回路を備え、
   振り分け回路が、前記比較回路における前記検索処理の実行状況に基づいて、これら比較回路のうち前記検索処理を開始可能ないずれか１つの比較回路へ、前記フレーム情報を分配する振り分けステップと、
   フレーム情報バッファが、前記フレーム情報を内部バッファに一時的に蓄積し、前記比較回路のうちのいずれかで前記検索処理を開始可能な場合であって、かつ、前記ソート処理部において前記ソート処理が実行されていない場合に、当該内部バッファから前記フレーム情報を取得して前記振り分け回路へ出力するバッファステップと
   をさらに備えることを特徴とするフレーム検索処理方法。

Images