(57)【要約】【課題】非同期に発生する複数の検索要求を同時に処理することにより、低コストで複数の検索要求に対する全体の検索処理時間を大幅に短縮すること。【解決手段】Ｍ個（図１では３個）の検索要求部１０に対応して設けられ受け付けた検索要求の開始から終了までを処理する要求処理部２１と、少なくとも１つの要求処理部２１から検索読み出し要求を受けると検索対象データを記憶する共有メモリ２８から検索対象データを順次読み出す順次アクセス部２６と、要求処理部２１にそれぞれ対応して設けられ順次アクセス部２６で読み出された検索対象データが検索要求で与えられたそれぞれの検索条件と一致するかを判定し結果を対応する要求処理部２１へ通知する一致判定部２３とを有し、検索要求を並列処理することを特徴とする。【選択図】      図１
2004287963.tif 000002
【特許請求の範囲】
【請求項１】
Ｍ（Ｍ≧２）個の検索要求元に対応してＭ個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると検索対象データを記憶する共有メモリから検索対象データを順次読み出す順次アクセス部と、要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部で読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部とを有し、検索要求を並列処理することを特徴とする検索装置。
【請求項２】
各検索要求で共用する検索対象データを記憶する共有メモリと、Ｍ（Ｍ≧２）個の検索要求元に対応してＭ個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると共有メモリから検索対象データを順次読み出す順次アクセス部と、Ｍ個の要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部で読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部とを有し、
各要求処理部はそれぞれ任意の時点で検索を開始しそれぞれの時点で検索を終了し、共通に読み出された検索対象データとそれぞれ一致判定することにより検索要求を並列処理することを特徴とする検索装置。
【請求項３】
前記要求処理部は、検索要求を受け付けると、その時点の前記共有メモリのアドレスを保持し、検索要求に付随する検索条件を前記一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を検索要求元へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を検索要求元に返すことを特徴とする請求項１又は２の検索装置。
【請求項４】
Ｍ（Ｍ≧３）個の検索要求元に対してＮ（Ｍ＞Ｎ≧２）個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると検索対象データを記憶する共有メモリから検索対象データを順次読み出す順次アクセス部と、要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部から読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部と、Ｍ個の検索要求元からの検索要求を随時受け付けて予め決められた手法により処理中でない要求処理部へ割り付ける要求調停部とを有し、検索要求を並列処理することを特徴とする検索装置。
【請求項５】
各検索要求で共用する検索対象データを記憶する共有メモリと、Ｍ（Ｍ≧２）個の検索要求元に対応してＮ（Ｍ＞Ｎ≧２）個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると共有メモリから検索対象データを順次読み出す順次アクセス部と、Ｍ個の要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部で読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部と、Ｍ個の検索要求元からの検索要求を随時受け付けて予め決められた手法により処理中でない要求処理部へ割り付ける要求調停部とを有し、
各要求処理部はそれぞれ任意の時点で検索を開始しそれぞれの時点で検索を終了し、共通に読み出された検索対象データとそれぞれ一致判定することにより検索要求を並列処理することを特徴とする検索装置。
【請求項６】
前記要求処理部は、検索要求を受け付けると、その時点の前記共有メモリのアドレスを保持し、検索要求に付随する検索条件を前記一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を要求調停部へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を要求調停部に返すことを特徴とする請求項４又は５の検索装置。
【請求項７】
前記順次アクセス部は、共有メモリから検索対象データを読み出すアドレスを格納する検索ポインタを有し、前記要求処理部は検索要求を開始する際の検索ポインタの値を保持するポインタ保持部を有して検索ポインタが一巡してポインタ保持部の値と一致したときに検索の終了を検出することを特徴とする請求項乃至６のいずれかの検索装置。
【請求項８】
前記一致判定部は検索要求で与えられた検索条件を保持する条件保持部と、順次アクセス部から送られた検索対象データが条件保持部に保持された検索条件と一致するか判定する比較部とを有することを特徴とする請求項１乃至６のいずれかの検索装置。
【請求項９】
検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を検索要求元へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を有し、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように要求処理手順を並列して実行することを特徴とする検索方法。
【請求項１０】
検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致終了通知を検索要求元へ返すとともに検索読み出し要求を終了し、
一致しない場合は次の比較結果の判定を繰り返し共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を有し、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように要求処理手順を並列して実行することを特徴とする検索方法。
【請求項１１】
Ｍ個の検索要求元の１つから検索要求を受け付けると一致判定部の数Ｎ（Ｍ＞Ｎ≧２）を越えない範囲で検索要求を前記要求処理手順に割り付けて前記要求処理手順を並列に実行させることを特徴とする請求項９又は１０の検索方法。
【請求項１２】
検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を検索要求元へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように並列してコンピュータに実行させることを特徴とするプログラム。
【請求項１３】
検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致終了通知を検索要求元へ返すとともに検索読み出し要求を終了し、
一致しない場合は次の比較結果の判定を繰り返し共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように並列してコンピュータに実行させることを特徴とするプログラム。
【請求項１４】
Ｍ個の検索要求元の１つから検索要求を受け付けると一致判定部の数Ｎ（Ｍ＞Ｎ≧２）を越えない範囲で検索要求を前記要求処理手順に割り付けて前記要求処理手順を並列してコンピュータに実行させることを特徴とする請求項１２又は１３のプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は検索装置、検索方法、及びプログラムに関し、特に非同期に発生する検索要求を受け付けて並列処理する技術に関する。
【０００２】
【従来の技術】
従来の検索装置における検索の技術について図６のブロック図を参照して説明する。従来の検索装置８０は、検索要求をする検索要求部７０（図６では３つ接続している）の要求を受け付けて処理する要求処理部８１と、検索対象データを記憶する共有メモリ８８と、検索対象データの登録を行うアクセス要求部８９と、要求処理部８１又はアクセス要求部８９からの要求を受けて共有メモリ８８への読み出しや書き込みのアクセスを制御するメモリアクセス部８６と、検索条件を保持する条件保持部８４と共有メモリ８８から読み出した検索対象データと条件保持部８４に保持される検索条件との比較を行う比較部８５とを有する一致判定部８３とを含んでいる。
【０００３】
要求処理部８１は検索処理中でないときに検索要求部７０のいずれか１つ例えば検索要求部７０−１から検索条件を含んだ検索要求を受け付けると、条件保持部８４へ受け付けた検索条件を設定し、共有メモリ８８の検索対象データを記憶している検索対象データ領域の先頭アドレスに対して読み出し要求する。メモリアクセス部８６は読み出し要求を受けると検索対象データを読み出して一致判定部８３へ送る。
【０００４】
一致判定部８３は比較部８５の比較結果を要求処理部８１へ返す。要求処理部８１は比較結果が検索条件に一致した場合には一致したことを要求元の検索要求部７０−１に返却して処理を終了する。検索条件に一致した結果が得られないときは読み出しアドレスを更新して検索対象データ領域の最後まで読み出し要求を繰り返して一致が得られなければ該当無しとして要求元の検索要求部７０−１に返却して処理を終了する。このように処理が終了した後、要求処理部８１は次の検索要求を検索要求部７０のいずれかから受け付けて検索処理を実行するように動作し、複数の検索要求を並列して処理するものではない。
【０００５】
また、例えば、２つ以上の比較データに対していずれかの比較データと一致するかという検索条件のような比較データが複数ある検索条件での検索時間を短縮する技術としては、特開昭５６−１７４５７号公報では比較回路を２つ有して２つの比較データに対する比較を同時に実行する技術が開示されている。ここで、２つの比較データは１つの検索要求に伴って与えられ同時に開始・終了するものであって、開始・終了時間がずれることはない。
【０００６】
【特許文献１】
特開昭５６−１７４５７号公報
【０００７】
【発明が解決しようとする課題】
従来の検索処理の技術では、複雑な検索条件を同時に処理することにより検索時間を短縮することは可能であったが、同じ検索対象のデータに対する複数の検索要求を同時に処理できなかったため、多数の検索要求が集中した場合に検索要求に対する検索結果を得るまでの時間が全体的に長くなってしまうという問題があった。
【０００８】
また、多数の検索要求に対する処理時間を短縮するための構成として、図５の共有メモリ８８と一致判定部８３と要求処理部８１とを一組としこの組を複数設ける構成が考えられるが、検索対象データの量が大きくなると共有メモリ８８の容量も大きくなり共有メモリ８８を複数設けることによるコストが大きくなってしまう。
【０００９】
本発明の目的は、同じ検索対象のデータに対する非同期に発生する複数の検索要求を同時に処理することにより、低コストで複数の検索要求に対する全体の検索処理時間を大幅に短縮した検索装置、検索方法、及びプログラムを提供することにある。
【００１０】
【課題を解決するための手段】
本発明の第１の検索装置は、Ｍ（Ｍ≧２）個の検索要求元に対応してＭ個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると検索対象データを記憶する共有メモリから検索対象データを順次読み出す順次アクセス部と、要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部で読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部とを有し、検索要求を並列処理することを特徴とする。
【００１１】
本発明の第２の検索装置は、各検索要求で共用する検索対象データを記憶する共有メモリと、Ｍ（Ｍ≧２）個の検索要求元に対応してＭ個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると共有メモリから検索対象データを順次読み出す順次アクセス部と、Ｍ個の要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部で読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部とを有し、
各要求処理部はそれぞれ任意の時点で検索を開始しそれぞれの時点で検索を終了し、共通に読み出された検索対象データとそれぞれ一致判定することにより検索要求を並列処理することを特徴とする。
【００１２】
本発明の第３の検索装置は、本発明の第１又は第２の検索装置において、前記要求処理部は、検索要求を受け付けると、その時点の前記共有メモリのアドレスを保持し、検索要求に付随する検索条件を前記一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を検索要求元へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を検索要求元に返すことを特徴とする。
【００１３】
本発明の第４の検索装置は、Ｍ（Ｍ≧３）個の検索要求元に対してＮ（Ｍ＞Ｎ≧２）個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると検索対象データを記憶する共有メモリから検索対象データを順次読み出す順次アクセス部と、
要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部から読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部と、Ｍ個の検索要求元からの検索要求を随時受け付けて予め決められた手法により処理中でない要求処理部へ割り付ける要求調停部とを有し、検索要求を並列処理することを特徴とする。
【００１４】
本発明の第５の検索装置は、各検索要求で共用する検索対象データを記憶する共有メモリと、Ｍ（Ｍ≧２）個の検索要求元に対応してＮ（Ｍ＞Ｎ≧２）個設けられ受け付けた検索要求の開始から終了までを処理する要求処理部と、少なくとも１つの要求処理部から検索読み出し要求を受けると共有メモリから検索対象データを順次読み出す順次アクセス部と、Ｍ個の要求処理部にそれぞれ対応してＭ個設けられ順次アクセス部で読み出された検索対象データが検索要求で与えられた検索条件と一致するかを判定し結果を対応する要求処理部へ通知する一致判定部と、Ｍ個の検索要求元からの検索要求を随時受け付けて予め決められた手法により処理中でない要求処理部へ割り付ける要求調停部とを有し、
各要求処理部はそれぞれ任意の時点で検索を開始しそれぞれの時点で検索を終了し、共通に読み出された検索対象データとそれぞれ一致判定することにより検索要求を並列処理することを特徴とする。
【００１５】
本発明の第６の検索装置は、本発明の第４又は第５の検索装置において、前記要求処理部は、検索要求を受け付けると、その時点の前記共有メモリのアドレスを保持し、検索要求に付随する検索条件を前記一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を要求調停部へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を要求調停部に返すことを特徴とする。
【００１６】
本発明の第７の検索装置は、本発明の第１乃至第６のいずれかの検索装置において、前記順次アクセス部は、共有メモリから検索対象データを読み出すアドレスを格納する検索ポインタを有し、前記要求処理部は検索要求を開始する際の検索ポインタの値を保持するポインタ保持部を有して検索ポインタが一巡してポインタ保持部の値と一致したときに検索の終了を検出することを特徴とする。
【００１７】
本発明の第８の検索装置は、本発明の第１乃至第６のいずれかの検索装置において、前記一致判定部は検索要求で与えられた検索条件を保持する条件保持部と、順次アクセス部から送られた検索対象データが条件保持部に保持された検索条件と一致するか判定する比較部とを有することを特徴とする。
【００１８】
本発明の第１の検索方法は、検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を検索要求元へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を有し、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように要求処理手順を並列して実行することを特徴とする。
【００１９】
本発明の第２の検索方法は、検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致終了通知を検索要求元へ返すとともに検索読み出し要求を終了し、
一致しない場合は次の比較結果の判定を繰り返し共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を有し、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように要求処理手順を並列して実行することを特徴とする。
【００２０】
本発明の第３の検索方法は、本発明の第１又は第２の検索方法において、Ｍ個の検索要求元の１つから検索要求を受け付けると一致判定部の数Ｎ（Ｍ＞Ｎ≧２）を越えない範囲で検索要求を前記要求処理手順に割り付けて前記要求処理手順を並列に実行させることを特徴とする。
【００２１】
本発明の第１のプログラムは、検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致通知を検索要求元へ返し、一致しない場合は次の比較結果の判定を繰り返し、
共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索の終了を検出し検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように並列してコンピュータに実行させることを特徴とする。
【００２２】
本発明の第２のプログラムは、検索要求を受け付けると、その時点の検索対象データを記憶する共有メモリのアドレスを保持し、検索要求に付随する検索条件を共有メモリから読み出した検索対象データと与えられた検索条件と比較する一致判定部に設定した後検索読み出し要求を開始し、
順次共有メモリから読み出された検索対象データが一致判定部で比較された比較結果を受け取ると、比較結果を判定して一致した場合は一致終了通知を検索要求元へ返すとともに検索読み出し要求を終了し、
一致しない場合は次の比較結果の判定を繰り返し共有メモリからの読み出しアドレスが保持している読み出しアドレスと一致した時点で検索読み出し要求を終了し、検索終了通知を検索要求元に返す要求処理手順を、
共有メモリから読み出した検索対象データを共通して使用しながら複数の一致判定部でそれぞれの検索要求に伴う検索条件にて比較するように並列してコンピュータに実行させることを特徴とする。
【００２３】
本発明の第３のプログラムは、本発明の第１又は第２のプログラムにおいて、Ｍ個の検索要求元の１つから検索要求を受け付けると一致判定部の数Ｎ（Ｍ＞Ｎ≧２）を越えない範囲で検索要求を前記要求処理手順に割り付けて前記要求処理手順を並列してコンピュータに実行させることを特徴とする。
【００２４】
【発明の実施の形態】
次に、本発明の第１の実施の形態について図面を参照して詳細に説明する。図１は本発明の第１の実施の形態の構成を示すブロック図である。本発明の第１の実施の形態の構成は、検索要求をする複数の検索要求部１０と検索装置２０とからなる。
【００２５】
検索要求部１０は、図１では検索要求部１０−１、検索要求部１０−２、検索要求部１０−３の３つを示しているが接続数を限定するものではなく２つ以上であればよい。また、検索要求部１０は、検索要求を受け付けて検索装置２０に送り、検索結果を返す装置であり、検索装置２０とのインターフェースは図１のように独立していてもよく、或いは、ネットワークのように通信路を共用して接続する構成であってもかまわないし、或いは、複数の検索要求部１０の検索要求を１カ所でまとめる装置を介して検索装置２０に接続するような構成であってもかまわない。
【００２６】
また、検索要求部１０は検索要求する装置と１対１に対応することなく、検索要求者とし１つの装置から複数の検索要求を並列に実行する形態でも、適用が可能である。その場合検索結果は検索要求部１０の装置宛ではなく検索要求部１０の検索要求者宛に返すことになる。
【００２７】
検索装置２０は、要求処理部２１と、一致判定部２３と、順次アクセス部２６と、共有メモリ２８と、アクセス要求部２９とを有する。共有メモリ２８は各検索要求部１０からの検索要求に対する検索対象データを共有して記憶するメモリである。アクセス要求部２９は、検索対象データを共有メモリ２８に登録したり参照したりする。
【００２８】
要求処理部２１と一致判定部２３はそれぞれ同じものを検索要求部１０に対応して複数設けており、図１の構成では検索要求部１０−１、検索要求部１０−２、検索要求部１０−３にそれぞれ対応して、要求処理部２１−１、要求処理部２１−２、要求処理部２１−３と、一致判定部２３−１、一致判定部２３−２、一致判定部２３−３とが設けられている。
【００２９】
順次アクセス部２６は、共有メモリ２８の検索アドレスを保持する検索ポインタ２７を有し、アクセス要求部２９からの要求を処理する場合はアクセス要求部２９からのアドレスに基づいて共有メモリ２８へ読み出しまたは書き込みの動作を行い、要求処理部２１からの要求を処理する場合は、検索ポインタ２７に基づいて共有メモリ２８をアクセスし読み出したデータを各一致判定部２３へ送る。なお、要求処理部２１−１、要求処理部２１−２、要求処理部２１−３からの要求は論理和により要求の有無が判定され、少なくとも１つの検索処理部２１の要求があれば検索動作が実行され、全ての要求が無くなれば実行されない。
【００３０】
なお、検索ポインタ２７は、共有メモリ２８から検索のための読み出しをする度に次の読み出しアドレスとなるように内容を更新される。なお、共有メモリ２８に格納される検索対象データの領域の最後まで達した場合はその領域の先頭アドレスになるように更新し、領域全体の検索ができるようにする。
【００３１】
一致判定部２３は、検索条件を保持する検索条件保持部２４と、共有メモリ２８からの読み出しデータと検索条件保持部２４に保持する比較データとを検索条件に基づいて一致するか比較し比較結果を要求処理部２１へ通知する比較部２５とを有する。ここで、検索条件保持部２４は複数の検索条件を保持し、比較部２５は同時に複数の比較データと読み出しデータとの比較を実行する検索条件で比較しても良いが、複数の比較データを同時に比較する技術は従来知られているので説明は省略する。
【００３２】
要求処理部２１は、検索開始時の検索ポインタ２７の値を保持するポインタ保持部２２を有し検索の開始と終了を含む検索処理の手順を制御する。この検索処理の手順はプログラムで実現するが、例えばＬＳＩ内の回路のようなハードウェアの回路で実現してもかまわない。ポインタ保持部２２は、検索要求部１０に対応して設けられ、図１の構成では検索要求部１０−１、検索要求部１０−２、検索要求部１０−３にそれぞれ対応して、ポインタ保持部２２−１、ポインタ保持部２２−２、ポインタ保持部２２−３が設けられる。
【００３３】
また、要求処理部２１は、検索を開始すると検索ポインタ２７の更新毎に検索ポインタ２７の値とポインタ保持部２２の値を比較し一致したことにより共有メモリ２８の全対象データの検索が終了したことを検出し検索の終了を検出する。また、要求処理部２１は、対応する検索要求部１０から受け付けた検索要求に含まれる検索条件を対応する一致判定部２３の検索条件保持部２４へ設定する。
【００３４】
次に、本発明の第１の実施の形態の動作について図面を参照して説明する。まず、検索対象となるデータは、アクセス要求部２９から事前に共有メモリ２８内の領域に登録される。また、登録後の検索対象データの追加、変更、削除等の処理もアクセス要求部２９から実行される。
【００３５】
次に検索要求部１０−１の検索要求の動作を例に説明する。まず検索要求部１０−１の検索要求は１対１に対応して設けられた要求処理部２１−１で受け付けられる。図２は要求処理部２１−１の動作を示したフローチャートである。要求処理部２１−２と要求処理部２１−３も図２のフローチャートと同様に動作し、それぞれ並列して動作が可能である。以降、要求処理部２１−１の動作を中心に図２を参照して説明する。
【００３６】
まず、要求処理部２１−１は検索要求に含まれる検索条件を一致判定部２３−１の条件保持部２４−１に設定する（Ｓ４１）。検索条件や検索条件との比較方法については限定しない。続いて現在の検索ポインタ２７の値を順次アクセス部２６から読み出してポインタ保持部２２−１へ格納し保持する（Ｓ４２）。次に検索読み出し要求を順次アクセス部２６へ送る（Ｓ４３）。
【００３７】
ここで順次アクセス部２６の動作について説明する。順次アクセス部２６は要求処理部２１−１、要求処理部２１−２、要求処理部２１−３の各検索読み出し要求の論理和をとって要求処理部２１からの要求と判断する。図３は順次アクセス部２６の動作を示したフローチャートである。順次アクセス部２６は図３の動作をプログラムで実現しても良いし、ハードウェアの回路で実現しても良く限定しない。
【００３８】
図３を参照すると、順次アクセス部２６はアクセス要求部２９からの要求があると（Ｓ５１）、アクセス要求部２９からのアクセス要求を受け付けて処理する（Ｓ５２）。例えば、検索対象データの登録のように書き込み要求を受けると共有メモリ２８の受け付けたアドレスに受け付けた検索対象データを書き込む。読み出し要求の際は受け付けたアドレスのデータを共有メモリ２８から読み出してアクセス要求部２９へ返す。
【００３９】
アクセス要求部２９からの要求がない場合は、要求処理部２１からの要求が有るか調べ（Ｓ５３）、要求処理部２１からの要求が有ると検索ポインタ２７を予め決められたアドレス分進めるように更新して（Ｓ５４）、検索ポインタ２７が保持するアドレスに従って共有メモリ２８から検索対象データを読み出し、一致判定部２３−１、一致判定部２３−２、一致判定部２３−３へ送る（Ｓ５５）。
【００４０】
ここでは、アクセス要求部２９からの要求はないものとする。順次アクセス部２６は要求処理部２１−１からの検索読み出し要求を受けて、検索ポインタ２７を更新し、共有メモリ２８から検索対象データを読み出して各一致判定部２３へ送る。
【００４１】
一致判定部２３−１は検索対象データを受け取ると、比較部２５−１で条件保持部２４−１に保持される比較データと検索対象データとを条件に従って検索条件に一致するか否か比較し比較結果を要求処理部２１−１へ通知する。
【００４２】
ここで、要求処理部２１−２でも検索が実行されている場合は、同じ共有メモリ２８からの読み出しデータに対して図示しないが一致判定部２３−２の比較部２５で図示しない条件保持部２４の内容に従って比較し、比較結果を要求処理部２１−２へ通知する。要求処理部２１−３が検索実行している場合も同様に一致判定部２３−３から検索結果が要求処理部２１−３へ通知される。
【００４３】
要求処理部２１−１はステップＳ４３で検索読み出し検索ポインタ２７が更新されたことにより検索対象データの読み出しが実行されることを確認した後（Ｓ４４）、一致判定部２３−１からの比較結果の通知を待って（Ｓ４５）、比較結果を確認し（Ｓ４６）、結果が一致であれば一致を検出したことを検索要求部１０−１へ通知する（Ｓ４７）。一致検出の通知には一致検出されたときの検索ポインタ２７の値である共有メモリ２８のアドレスやその読み出しデータ等の情報を付加することがあるが限定するものではない。
【００４４】
ステップＳ４６で一致が検出されなかった場合、又はステップＳ４７に続いて、要求処理部２１−１は検索ポインタ２７とポインタ保持部２２−１との比較により検索ポインタ２７が一巡し全ての検索対象データについて検索が終了したか判定し（Ｓ４８）、終了していなければステップＳ４４へ戻って検索を継続し、終了していれば検索終了を検索要求部１０−１へ通知し順次アクセス部２６への検索読み出し要求を終了する（Ｓ４９）。
【００４５】
順次アクセス部２６は、要求処理部２１−１からの検索読み出し要求が終了した際、他の要求処理部２１からの検索読み出し要求がなければ検索対象データの読み出しを停止し、検索ポインタ２７の更新を停止するか、又は初期値（例えば検索対象データの格納領域の先頭アドレス）等の値に設定し直しても良い。要求処理部２１−１からの検索読み出し要求が終了した際、他の要求処理部２１からの検索読み出し要求が継続していれば、順次アクセス部２６は検索動作を継続し、検索ポインタ２７を更新して次の検索対象データの読み出しを行う。
【００４６】
ステップＳ４７の処理で、検索対象データと検索の特性により、２つ以上の一致が起こらないような場合には、検索要求部１０−１へ一致検出の通知を行った後に、順次アクセス部２６への検索読み出し要求を終了して検索を終了するようにしても良い。例えば、一意に割り振られたネットワークアドレスのような番号を比較対象とする検索対象データが共有メモリ２８に登録され、その番号の全一致を検索条件として検索が行われる場合等がこれに相当する。一方、全一致ではなく部分一致の検索の場合は２つ以上一致することがあるのでこの場合は一致が検出されても検索を続行すればよい。
【００４７】
また、検索ポインタ２７はアドレスをインクリメントする場合を説明したが、デクリメントするようにしても良いし、他の更新方法でも良い。また、検索要求部１０の数は３つの場合を示しているがその数を制限するものではない。
【００４８】
以上の説明では、要求処理部２１−１の動作を中心に説明したが、検索要求部１０から非同期に行われる検索要求はそれぞれ対応する要求処理部２１で受け付けられてその時点の検索ポインタ２７の値を開始アドレスとして検索を実行し、それぞれの要求処理部２１で終了処理をできるようにしたので、非同期に行われる検索要求部１０からの検索要求を並列して処理ができる。
【００４９】
以上のように、多数の検索要求が集中して各検索要求部１０から発行されても、共有メモリ２８への読み出し要求と読み出しデータを１回にまとめて処理することにより全体の処理時間を大幅に短縮することができる。図１の構成では従来に比べて３つの検索要求を並列処理できるので検索処理能力が最大３倍となる。検索要求部１０の数をＭとすれば最大でＭ倍の検索処理が可能となるが、それに応じて要求処理部２１と一致判定部２３との組もＭだけ設ける必要がある。
【００５０】
次に本発明の第２の実施の形態について説明する。図４は本発明の第２の実施の形態の構成を示したブロック図である。図４を参照すると検索装置６０は第１の実施の形態の検索装置２０と比べて、要求調停部６１が追加されていることに特徴があり、図１の構成要素と同じ構成要素については図１と同じ番号を付与している。
【００５１】
第２の実施の形態では、Ｍ個の検索要求部１０に対して、要求処理部２１と一致判定部２３の組をＮ（Ｍ＞Ｎ）組設け、Ｍ個の検索要求部１０からの検索要求を最大Ｎ個まで並列処理するようにしている。図４では、４つの検索要求部１０に対して、要求処理部２１−１と一致判定部２３−１の組と、要求処理部２１−２と一致判定部２３−２の組の２組を設けている。
【００５２】
検索装置６０は、第１の実施の形態の検索装置２０に比べて要求調停部６１が検索要求部１０と要求処理部２１との間に新たに追加されており、他の構成要素は同じであるので、要求調停部６１を中心に説明し、他の構成要素についての説明は省略する。
【００５３】
要求調停部６１は、４つの検索要求部１０からの検索要求の有無と、要求処理部２１−１と要求処理部２１−２とがそれぞれ検索処理中の状態か否かを確認して、どの検索要求をどの要求処理部２１に割り付けるかを決め、要求処理部２１からの検索結果の通知を受けて要求元の検索要求部１０に転送する。要求調停部６１は、これらの処理をプログラムで実現しても良いし、ハードウェアの回路で実現しても良い。
【００５４】
次に、本発明の第２の実施の形態の動作を説明する。要求調停部６１の動作を示したフローチャートである図５を参照して説明する。初期状態は検索処理が実行されていない状態とし、具体例で説明していく。
【００５５】
まず、要求調停部６１は、検索要求部１０−１から検索要求Ａを受け付けると（Ｓ９１）、要求処理部２１の状態を調べる（Ｓ９２）。どちらの要求処理部２１も処理中ではなく空き状態なので、次に他に検索要求が待ち合わせているかを調べる（Ｓ９３）。他に検索要求はないので空き状態の要求処理部２１−１へ検索要求Ａを送り、要求処理部２１−１に割り付けた検索要求の要求元が検索要求部１０−１であることを記憶しておく（Ｓ９５）。要求処理部２１−１は検索要求Ａを受け付けると第１の実施の形態で説明したように検索処理を開始する。
【００５６】
次に要求調停部６１は、検索要求部１０−２から検索要求Ｂを受け付けると（Ｓ９１）、要求処理部２１の状態を調べる（Ｓ９２）。要求処理部２１−２が空き状態なので、次に他に検索要求が待ち合わせているかを調べる（Ｓ９３）。他に待ち合わせている検索要求はないので空き状態の要求処理部２１−２へ検索要求Ｂを送り要求元情報を記憶しておく（Ｓ９５）。要求処理部２１−２は第１の実施の形態で説明したように検索要求Ｂの処理を開始する。
【００５７】
さらに、検索要求部１０−３から検索要求Ｃを受け付けると（Ｓ９１）、要求調停部６１は、要求処理部２１が全て検索処理中であるため、要求処理部２１の１つが終了するのを待ち合わせる（Ｓ９２）。この状態でさらに検索要求部１０−４から検索要求Ｄを受け付けると（Ｓ９１）、要求調停部６１は、要求処理部２１が全て検索処理中であるため、要求処理部２１の１つが終了するのを待ち合わせる（Ｓ９２）。
【００５８】
次に、要求処理部２１−１が検索要求Ａの処理を終了すると終了通知を要求調停部６１に返す。要求調停部６１は終了通知を受けると記憶している情報に基づいて要求元の検索要求部１０−１へ終了通知を転送する。
【００５９】
要求処理部２１−１の検索終了により（Ｓ９２）、要求調停部６１は次に要求処理部２１−１へ割り付ける検索要求を決定する。待ち合わせ中の検索要求が２つ以上有るか調べ（Ｓ９３）、この場合検索要求Ｃと検索要求Ｄと２つが待ち合わせていれば予め決められた方法によって調停して１つを選択し（この場合は検索要求Ｃを選択するものとする）（Ｓ９４）、検索要求Ｃを要求処理部２１−１へ送り、要求元情報を記憶しておく（Ｓ９５）。ステップ９３の時点で検索要求Ｃのみであれば調停は不要でステップＳ９５を実行する。
【００６０】
このように、第２の実施の形態では、任意のＮ個の検索要求を並列処理することにより、従来に比べて最大でＮ倍の検索処理が可能となる。図４の構成では検索要求を２つ並列処理できるので従来に比べて最大２倍の検索要求を処理できる。特に、検索要求部１０が多数になった場合、全ての検索要求が競合する確率が低いような場合は、第２の実施の形態では第１の実施の形態に比べてハードウェア量が少なくなりより経済的に検索時間の短縮が可能となる。
【００６１】
図４では、検索要求部１０の数を４、要求処理部２１と一致判定部２３との組の数を２としたが、これらの数はシステムの特性、利用特性、経済面の条件等を勘案して決めればよい。また、例えば性能最優先であれば第１の実施の形態のように要求処理部２１と一致判定部２３との組の数を検索要求部１０の数と同数とすればよいし、経済面を優先するなら第２の実施の形態で要求処理部２１と一致判定部２３との組の数を小さくするようにすればよく、それぞれの使用環境に応じて第１又は第２の実施の形態を選択すればよい。
【００６２】
【発明の効果】
本発明は、検索対象データを格納する共有メモリへの読み出しを複数の検索要求でまとめて１つにし、読み出したデータをそれぞれの検索条件で並列して判定するようにしたので、低コストで複数の検索要求の全体の検索時間を大幅に短縮することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態の構成の一例を示したブロック図である。
【図２】本発明の要求処理部２１の動作の一例を示したフローチャートである。
【図３】本発明の順次アクセス部２６の動作の一例を示したフローチャートである。
【図４】本発明の第２の実施の形態の構成の一例を示したブロック図である。
【図５】本発明の第２の実施の形態の要求調停部６１の動作の一例を示したフローチャートである。
【図６】従来の検索装置の構成の一例を示したブロック図である。
【符号の説明】
１０    検索要求部
７０    検索要求部
２０    検索装置
２１    要求処理部
２２    ポインタ保持部
２３    一致判定部
２４    条件保持部
２５    比較部
２６    順次アクセス部
２７    検索ポインタ
２８    共有メモリ
２９    アクセス要求部
６０    検索装置
６１    要求調停部
７０    検索要求部
８０    検索装置
８１    要求処理部
８３    一致判定部
８４    条件保持部
８５    比較部
８６    メモリアクセス部
８８    共有メモリ
８９    アクセス要求部
【図１】
2004287963.tif 000003
【図２】
2004287963.tif 000004
【図３】
2004287963.tif 000005
【図４】
2004287963.tif 000006
【図５】
2004287963.tif 000007
【図６】
2004287963.tif 000008