(57)【特許請求の範囲】
【請求項１】
所定のパターンからなる探索リスト、及び所定の処理済みパターンからなる処理済みリストを保持する記憶手段と、
送られてきたパターンに対する解の探索を行う複数の演算手段と、
前記記憶手段に保持された探索リストから、分配するパターンを粒度単位に展開するパターン展開手段と、
前記粒度単位に展開されたパターン、及び前記処理済みリストの重複を検索して重複のあるパターンを破棄するパターン検索手段と、
前記パターン検索手段から送られてきた重複がないパターンを前記複数の演算手段に分配する制御手段と、
前記制御手段から送られてきた前記パターン検索手段の検索時間、及び前記各演算手段の演算時間の比率に基づいて粒度の大きさを決定し、前記パターン展開手段へ粒度変更の指示を出す粒度変更手段と
を備えたことを特徴とするパターン分配装置。
【請求項２】
所定のパターンからなる探索リスト、及び所定の処理済みパターンからなる処理済みリストを保持する記憶手段と、
送られてきたパターンに対する解の探索を行う複数の演算手段と、
前記記憶手段に保持された探索リストから、分配するパターンを粒度単位に展開するパターン展開手段と、
前記粒度単位に展開されたパターン、及び前記処理済みリストの重複を検索して重複のあるパターンを破棄するパターン検索手段と、
前記パターン検索手段から送られてきた重複がないパターンを前記複数の演算手段に分配する制御手段と、
前記パターン展開手段から送られてきた前記処理済みリストの大きさ、及びパターンの重複度の比率に基づいて粒度の大きさを決定し、前記パターン展開手段へ粒度変更の指示を出す粒度変更手段と
を備えたことを特徴とするパターン分配装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、ｎ個の要素からなる組み合わせパターンを探索する際に、その探索範囲に制約がある場合にパターンの分配を行うパターン分配装置に関するものであり、特に、並列計算機による暗号鍵探索問題における鍵の分配や組み合わせ探索問題におけるパターンの分配を行うパターン分配装置に関するものである。
【０００２】
【従来の技術】
本発明の代表的な適用例は、暗号鍵探索である。この暗号鍵探索において、解読対象の入手暗号文とそれに対応する想定平文、および、暗号化方法の知識が手元にあるとき、全ての組み合わせの暗号鍵候補を用いて想定平文を暗号化し、その暗号化結果を入手暗号文と比較し、一致すれば暗号化に用いたその時の候補鍵が求める暗号鍵である。このような暗号鍵の探索方法を、全数探索と称する。
【０００３】
例えば、米国等で標準的に使用されているブロック暗号であるＤＥＳ（Data Encryption Standard）暗号では暗号鍵長が５６ビットであるため、すべての鍵候補を試すために、２の５６乗通りの暗号化を１ブロック６４ビットの平文に対して行わなくてはならないので、時間が非常にかかる。
【０００４】
暗号鍵長が５６ビットよりも更に長い６４ビットや１２８ビットになると、現在の計算機技術や回路技術を駆使し、巨大な装置を構成しても、全数探索法は長大な時間がかかり、現実的な探索法とは言えなくなる。ところが、暗号鍵もしくはその元になるデータを人が指定する場合、パスワードに代表されるように、覚えやすく、短めのデータが使われる傾向にある。
【０００５】
また、通常、可読文字でしかも特殊文字を除いたものが使われる。即ち、６４ビットや１２８ビットの鍵長で認められる全てのビットパターンの内、人は意図せずに非常に限られたパターンの中から選んで、それを鍵としていることになる。
【０００６】
従って、全数探索法に代えて、パスワードに用いられそうな人名、地名などの語句をデータベースなどに蓄えておき、これらを全数探索における候補鍵と同様に順次暗号回路に与えて、暗号鍵探索を行う方法が考えられる。これをパスワード攻撃と称する。
【０００７】
このパスワード攻撃の場合、人名、地名などを蓄えたデータベース上の語句そのものだけを候補鍵としてしまうと、人名、地名などを少し変形したり、文字を追加したりした鍵を発見することが困難になる。
【０００８】
一方、少し変形したパターンも含めて全てデータベース上の鍵候補とその類似の候補鍵も合せて探索するために、鍵を構成するビット列の中の一部は固定し、他は任意の値を順次当てはめていくことにより候補鍵のパターンを発生させて鍵探索を行うことが考えられる。このように、鍵を構成するビット列の中の一部を通常の値もしくは文字で指定し、一部を任意の値、文字、もしくは文字列を示すワイルドカード（＊、？）で指定する方法を「ワイルドカードによる指定方法」と呼ぶこととし、また、この探索方法を「ワイルドカードによる範囲限定探索」と呼称することとする。
【０００９】
一般的には、暗号鍵の探索を「ワイルドカードによる範囲限定探索」で行う場合でも、処理時間に膨大な時間がかかるため、並列処理により高速に処理を行う。
【００１０】
従来のパターン分配装置について図面を参照しながら説明する。図１５は、従来のパターン分配装置の構成を示す図である。この図１５は、「ワイルドカードによる範囲限定探索」を行うためのパターン分配装置の構成を示す。
【００１１】
また、図３は、探索範囲がワイルドカードにより指定されたパターンのリストの例を示す図である。これ以降、このようなワイルドカードにより指定されたパターンのリストを「探索リスト」と呼称する。
【００１２】
図１５において、９１はワイルドカード指定されたパターンを後述する各演算手段に分配する制御手段、９２は図３のような探索リストを保持する記憶手段、９３ａ〜９３ｄは制御手段９１から送られたパターンに対する演算処理を行う演算手段である。
【００１３】
つぎに、従来のパターン分配装置の動作について図面を参照しながら説明する。
【００１４】
実際の動作においては、制御手段９１が記憶手段９２の探索リストの中から１つのパターンを取り出し、演算手段９３ａ〜９３ｄのうち演算処理を行っていない演算手段に分配する。各演算手段９３ａ〜９３ｄでは、割り当てられたパターンを展開して任意指定された要素を実際の値、もしくは文字に置き換えて処理を行う。制御手段９１は、各演算手段９３ａ〜９３ｄを監視し、割り当てられたパターンの処理の終了した演算手段に新たにパターンを分配する。
【００１５】
【発明が解決しようとする課題】
ワイルドカードによりパターンを指定した探索リストを展開した場合、一般的に、探索パターンの重複が発生する。例えば、図３に示す探索リストの探索パターン１の“ＡＢ＊”を展開した“ＡＢＣＡＡＡＡＡ"というパターンは、探索パターン３の“＊ＢＣ＊”を展開することによっても作ることができる。このように、探索リストに重複が生じる。
【００１６】
このような重複を避けて処理の効率化を行うため、図１５に示すような装置で処理を行う前に、あらかじめ探索リストを重複の全くない（もしくは重複の少ない）探索リストに置き換えることが考えられる。しかし、このような置き換えは、一般的に、非常に困難である。
【００１７】
また、置き換えたとしても、探索リストの中のパターンの数が増大し、個々のパターンの粒度が細分化されることが予想される。この場合、制御手段９１と各演算手段９３ａ〜９３ｄとの間の通信頻度が増加する。このため、演算手段９１が１つのパターンを処理するのにかかる時間よりも、通信にかかる時間の方が大きくなる状況が発生し、処理効率が低下する。
【００１８】
また、分配するパターンの粒度がまちまちになるため、一部の演算手段、もしくはある時間において通信の偏りが生じることになり、通信の負荷が増加する。特に、図１５に示す制御手段９１と演算手段９３ａ〜９３ｄがネットワーク等で接続されている場合は、データの通信に時間がかかるため、通信負荷による影響が大きくなる。
【００１９】
さらに、暗号の鍵探索に限らず、一般的な組み合わせ最適化問題や組み合わせ探索問題においても、ワイルドカードによる範囲限定探索を、複数の演算手段を用いて並列に行う場合には、上述と同様の問題点があった。
【００２０】
この発明は、前述した問題点を解決するためになされたもので、ワイルドカードによる範囲限定探索を複数の演算手段を用いて並列に処理する場合に、通信頻度、通信負荷を一定に抑えて、効率的に処理を行うことができるパターン分配装置を得ることを目的とする。
【００２７】
【課題を解決するための手段】
この発明の請求項１に係るパターン分配装置は、所定のパターンからなる探索リスト、及び所定の処理済みパターンからなる処理済みリストを保持する記憶手段と、送られてきたパターンに対する解の探索を行う複数の演算手段と、前記記憶手段に保持された探索リストから、分配するパターンを粒度単位に展開するパターン展開手段と、前記粒度単位に展開されたパターン、及び前記処理済みリストの重複を検索して重複のあるパターンを破棄するパターン検索手段と、前記パターン検索手段から送られてきた重複がないパターンを前記複数の演算手段に分配する制御手段と、前記制御手段から送られてきた前記パターン検索手段の検索時間、及び前記各演算手段の演算時間の比率に基づいて粒度の大きさを決定し、前記パターン展開手段へ粒度変更の指示を出す粒度変更手段とを備えたものである。
【００２８】
この発明の請求項２に係るパターン分配装置は、所定のパターンからなる探索リスト、及び所定の処理済みパターンからなる処理済みリストを保持する記憶手段と、送られてきたパターンに対する解の探索を行う複数の演算手段と、前記記憶手段に保持された探索リストから、分配するパターンを粒度単位に展開するパターン展開手段と、前記粒度単位に展開されたパターン、及び前記処理済みリストの重複を検索して重複のあるパターンを破棄するパターン検索手段と、前記パターン検索手段から送られてきた重複がないパターンを前記複数の演算手段に分配する制御手段と、前記パターン展開手段から送られてきた前記処理済みリストの大きさ、及びパターンの重複度の比率に基づいて粒度の大きさを決定し、前記パターン展開手段へ粒度変更の指示を出す粒度変更手段とを備えたものである。
【００２９】
【発明の実施の形態】
実施の形態１．
この発明の実施の形態１に係るパターン分配装置について図面を参照しながら説明する。図１は、この発明の実施の形態１に係るパターン分配装置の構成を示す図である。なお、各図中、同一符号は同一又は相当部分を示す。
【００３０】
図１において、１は本パターン分配装置、２は探索リストを保持する記憶手段、３は記憶手段２の中の探索リストから、ワイルドカード指定されたパターンを一つ取り出して粒度単位に解候補を展開作成するパターン展開手段、４はパターン展開手段３で展開されたパターンを受け取り、記憶手段２の中の探索リストとの重複検索を行い、重複する場合はそのパターンを破棄し、重複がない場合はパターンを後述する制御手段に送るパターン検索手段、５はパターン検索手段４から送られてきたパターンを後述するパターン保持手段もしくは各演算手段７ａ〜７ｄに割り当てる制御手段、６はパターン制御手段５から送られてきたパターンを一時的に保持するパターン保持手段、７ａ〜７ｄは制御手段５から送られてきたパターンに対する解の探索を行う演算手段である。
【００３１】
なお、制御手段５と演算手段７ａ〜７ｄは、ネットワーク等で接続されており、通信にある程度の時間がかかるものとする。
【００３２】
つぎに、この実施の形態１に係るパターン分配装置の動作について図面を参照しながら説明する。
【００３３】
図２は、この発明の実施の形態１に係るパターン分配装置の概略動作を示すフローチャートである。また、図３は、探索範囲がワイルドカードにより指定されたパターンのリストの例を示す図である。
【００３４】
図３において、探索リストの中の“＊”は０個以上の任意数の文字をあらわし、“？”は１個の任意の文字を示す。また、これ以降、各要素が実際の文字で表されたパターンであっても、要素の一部が“＊”や“？”等のワイルドカードで表されたパターンであっても、総称して“パターン”と呼称することとする。
【００３５】
さらに、図４、図５、図６、及び図７は、図３に示す探索リストの探索パターンを展開した例を示す図である。
【００３６】
なお、あらかじめ、記憶手段２に探索リストが保持されているものとする。
【００３７】
ステップ２０１において、制御手段５は、パターン保持手段６に空きがある場合に、パターン展開手段３にパターンを送るように指示を出す（図２のステップ１０１）。また、制御手段５は、演算手段７ａ〜７ｄを監視して、処理待ち状態の演算手段があるかどうかを判断する。処理待ち状態の演算手段がある場合は、パターン保持手段６からパターンを取り出し、その演算手段にパターンを分配する。パターン保持手段６にパターンがない場合は、パターンが送られてくるのを待ち受ける。
【００３８】
次に、ステップ２０２において、パターン展開手段３は、記憶手段２の中の探索リストからワイルドカード指定されたパターンを一つ取り出し、そのパターンの要素を、図４のように“？”等に置き換えて、定められた数の要素に展開して保持する（図２のステップ１０２、１０７、１０９）。すでに展開して保持しているパターンがある場合は、この処理は行わない。また、記憶手段２の中の探索リストを全て取り出して演算が完了した場合は、全体の処理を終了する（図２のステップ１０８）。
【００３９】
次に、ステップ２０３において、パターン展開手段３は、展開したパターンの一部の要素を実際の文字に置き換え、その他の要素を“？”のままで残すことにより、定められた大きさの粒度の単位に置き換える（図２のステップ１０３）。また、パターンが粒度単位に満たない場合は、適切な大きさのパターンに変換する。その後、粒度単位に置き換えられたパターンをパターン検索手段４に送る。変換を行ったパターンは、「変更有り」の情報も付加情報としてパターン検索手段４に送る。
【００４０】
次に、ステップ２０４において、パターン検索手段４は、粒度単位のパターンと探索リストの中にあるパターンのうちすでに処理を行ったパターンのリスト（以降、処理済みリストと呼称する。）との重複検索を行う（図２のステップ１０４）。検索の結果により、次のステップ２０４ａ、もしくはステップ２０４ｂのうちのいずれかの処理を行う。
【００４１】
ステップ２０４ａにおいて、探索リストの処理が完了したパターンの中に重複するものがあると判断された場合、パターン検索手段４は、送られてきたパターンを破棄する（図２のステップ１１０）。その後、パターン展開手段３に新たなパターンを送るように指示を出す。この場合、重複のないパターンが得られるまで、ステップ２０２〜２０４までの処理を繰り返す。
【００４２】
ステップ２０４ｂにおいて、重複がないと判断された場合は、パターン検索手段４は送られてきたパターンを制御手段５に送る（図２のステップ１０５、１０６）。また、重複無しと判断されたパターンが変更有りのパターンの場合、処理済みのパターンとして変更後のパターンを、記憶手段２の中の処理済みリストに追加する（図２のステップ１１１）。
【００４３】
次に、ステップ２０５において、制御手段５は、送られてきたパターンを、演算手段７ａ〜７ｄの内で現在処理待ち状態の演算手段がある場合は、その演算手段に分配する。演算手段７ａ〜７ｄに処理待ち状態のものがない場合は、パターン保持手段６にパターンを格納する。
【００４４】
そして、ステップ２０６において、演算手段７ａ〜７ｄでは、送られてきたパターンの要素の内、ワイルドカードで指定された要素の全てを実際の文字に置き換えて展開し、展開した各パターンについて演算を実行する。展開したすべてのパターンの演算が終了した場合は、処理待ち状態になる。
【００４５】
また、ステップ２０４でのパターンの重複検索には、さまざまな方法が考えられるが、一例として、その手順を示す。処理済みリストの全てのパターンに対して以下の操作を行う。
【００４６】
なお、以降、パターン展開手段３から送られてきた検索を行う粒度単位のパターンを「対象パターン」と呼称し、処理済みリストの検索されるパターンを「被検索パターン」と呼称する。また、パターンの要素のうち、実際の文字で指定された要素を「決定要素」、ワイルドカードで指定された要素を「未決定要素」と呼称する。
【００４７】
ステップ２１１において、被検索パターンの決定要素のうちの１個を、対象パターンの決定要素のうちの１個に当てはめる。当てはめられる場合はステップ２１２の処理を行う。当てはまらない場合は、ステップ２１４の処理を行う。
【００４８】
次に、ステップ２１２において、被検索パターンのその他の決定要素を、被検索パターンの決定要素に順次当てはめる。被検索パターンの全ての決定要素を当てはめることができる場合、ステップ２１３の処理を行う。全ての決定要素を当てはめることができない場合は、ステップ２１４の処理を行う。
【００４９】
次に、ステップ２１３において、被検索パターンの未決定要素を全て対象パターンの残りの要素に置き換えられるなら、対象パターンは被検索パターンと重複する。そうでない場合は、ステップ２１４の処理を行う。
【００５０】
そして、ステップ２１４において、考えうる全ての組み合わせに対して、ステップ２１１〜２１３の操作を繰り返す。当てはまる組み合わせがない場合は、対象パターンは被検索パターンと重複しない。
【００５１】
本パターン分配装置は、以上の動作を繰り返すことによって動作し、パターンを各演算手段に分配する。
【００５２】
次に、図４〜図８に示す例に従って、各部の動作を説明する。この例では、パターンの要素の数を８としている。また、パターンの各要素はＡ〜Ｚまでの文字であるとする。また、各演算手段に転送するパターンは、パターン内の要素の３つが未決定要素字で、残り５つが決定要素の状態を最小の粒度として各演算手段７ａ〜７ｄに転送する事にする。粒度に関しては、以下で例を用いて説明する。また、パターン保持手段６は、パターンを４個まで格納可能なＦＩＦＯ（First-in First-out）とする。
【００５３】
ケース１
まず、ケース１として重複を除去する例について、図３〜図５を用いて説明する。この例では、図３の探索リストにあるパターンを処理するものとする。
【００５４】
まず、ステップ３０１において、制御手段５は、処理の開始時に、パターン保持手段６に空きがあるため、パターン展開手段３にパターン要求の指示を出す。また、演算手段７ａ〜７ｄを監視して、全ての演算手段が処理待ち状態のため、制御手段５はパターンの待ち受け状態になる。
【００５５】
次に、ステップ３０２において、パターン展開手段３は、記憶手段２の中の探索リストから探索パターン１の“ＡＢ＊”を取り出し、それを図４のように“？”等に置き換えて展開して保持する。なお、図４の例は全て要素の数を８とし、要素数が８に満たない“ＡＢ"等のパターンは処理しないものとする。
【００５６】
次に、ステップ３０３において、パターン展開手段３は、図４の展開パターン１の“ＡＢ？？？？？？"をパターン内の要素の３つが任意文字の状態に展開する。これを示したものが図４の“粒度単位のパターン”であり、展開パターン１の“ＡＢ？？？？？？"は、粒度単位パターン１−１"ＡＢＡＡＡ？？？"、粒度単位パターン１−２"ＡＢＡＡＢ？？？"、・・・に展開される。これらのパターンの内、粒度単位パターン１−１"ＡＢＡＡＡ？？？"をパターン検索手段４に送る。
【００５７】
次に、ステップ３０４において、パターン検索手段４では、粒度単位のパターンと探索リストの中で既に処理の完了したパターンとの重複検索を行う。この時点では、処理の完了したパターンが存在しないため、粒度単位パターン１−１"ＡＢＡＡＡ？？？"は「重複無し」と判断され、制御手段５に送られる。
【００５８】
次に、ステップ３０５において、制御手段５は、粒度単位パターン１−１を演算手段７ａ〜７ｄの内の演算手段７ａに送る。この演算手段７ａでは、粒度単位パターン１−１"ＡＢＡＡＡ？？？"の“？？？"に当たる要素を文字に展開して、各パターンの演算を順次行う。
【００５９】
次に、ステップ３０６において、制御手段５は、パターン保持手段６に空きがある限り、パターン展開手段３にパターンの要求を出す。送られてきたパターンは、演算手段７ａ〜７ｄが処理待ち状態の場合は、その演算手段に送られ、演算手段７ａ〜７ｄが全て処理中の場合は、パターン保持手段６に送られる。このようにして、順次、粒度単位パターン１−２、１−３、・・・を演算手段７ａ〜７ｄに分配する。また、展開パターン１に対応する全ての粒度単位パターンの転送が完了した場合は、順次、展開パターン２、３・・・のパターンを粒度単位パターンに展開して同様の処理を行う。
【００６０】
次に、ステップ３０７において、探索パターン１に対応するパターンを全て分配した場合、パターン展開手段３は、探索パターン１を記憶手段２の処理済みリストに追加する。その後、同様にして、探索パターン２、探索パターン３、・・・の処理を継続する。
【００６１】
次に、ステップ３０８において、探索パターン３"＊ＢＣ＊”を展開した例が図５である。図５において、粒度単位パターン２−１"ＡＢＣＡＡ？？？”が、パターン検索手段４に送られて一致検索を行った場合、処理済みリストの探索パターン１と一致していると判断される。このため、粒度単位パターン２−１"ＡＢＣＡＡ？？？”は破棄される。同様にして、以下処理済みリストの中のパターンに一致しているものがある場合、パターン検索手段４はそのパターンを重複有りと判断し破棄する。
【００６２】
このようにして、ステップ３０９において、探索パターンの重複を取り除きながら、各演算手段７ａ〜７ｄにパターンを分配していく。
【００６３】
また、重複検索についても具体的に上記のケース１のステップ２０８を例に示す。
【００６４】
この場合、探索パターン１"ＡＢ＊”が被検索パターン、粒度単位パターン２−１"ＡＢＣＡＡ？？？”が対象パターンにあたる。以下の手順で検索が行われる。
【００６５】
まず、ステップ３１１において、探索パターン１"ＡＢ＊”の“Ａ"と一致する要素を粒度単位パターン２−１"ＡＢＣＡＡ？？？”の左から順に探す。粒度単位パターン２−１の１番目の要素がそれにあたる。
【００６６】
次に、ステップ３１２において、探索パターン１の残りの決定要素である“Ｂ"が粒度単位パターン２−１に当てはめられるか調べる。粒度単位パターン２−１の２番目の要素がそれにあたる。
【００６７】
そして、ステップ３１３において、探索パターン１の未決定要素である“＊”が粒度単位パターン２−１の残りの要素に置き換えられるか調べる。探索パターン１"ＡＢ＊”を変形して“ＡＢ？？？？？？”とすれば、粒度単位パターン２−１に置き換え可能になる。このため、粒度単位パターン２−１は探索パターン１と重複する。
【００６８】
ケース２
次に、ケース２として、最小粒度に満たないパターンを処理する例について、図６、及び図７を用いて説明する。この例では、図６の探索リストにあるパターンを処理するものとする。
【００６９】
最初のステップ４０１は、上記のケース１のステップ３０１と同じである。
【００７０】
次に、ステップ４０２において、パターン展開手段３は、記憶手段２の中の探索リストから探索パターン１の“ＡＢＣＡＡＡ＊”を取り出し、それを図４のケース１のように“？”等に置き換えて展開して保持する。この場合は、図６の探索パターン１"ＡＢＣＡＡＡ＊”は、展開パターン１"ＡＢＣＡＡＡ？？”に展開される。
【００７１】
次に、ステップ４０３において、図６の展開パターン１"ＡＢＣＡＡＡ？？”は、パターン内の２要素が任意文字であり、粒度単位未満である。このようなパターンを処理する場合、パターン展開手段３は、展開パターン１"ＡＢＣＡＡＡ？？”を、粒度単位の大きさになるように、粒度単位パターン１−１"ＡＢＣＡＡ？？？”に変換し、パターン検索手段４に送る。この時、粒度単位パターン１−１は変更されているため、「変更有り」の情報も送られる。
【００７２】
次に、ステップ４０４において、パターン検索手段４では、粒度単位パターン１−１の重複検索を行う。この場合、重複はないため、粒度単位パターン１−１は、「重複無し、変更有り」と判断される。このため、粒度単位パターン１−１は、制御手段５に送られ、記憶手段２の中の処理済みリストに追加パターン１"ＡＢＣＡＡ？？？”が追加される。
【００７３】
次に、ステップ４０５において、探索パターン１に対応するパターンを全て分配した場合、パターン展開手段３は、探索パターン１を記憶手段２の処理済みリストに追加する。
【００７４】
次に、ステップ４０６において、探索パターン１の処理後に、探索パターン２"＊ＢＣ＊”を展開した例が図７である。図７において、粒度単位パターン２−１"ＡＢＣＡＡ？？？”が、パターン検索手段４に送られて一致検索を行った場合、処理済みリストの探索パターン１と一致していると判断する。このため、粒度単位パターン２−１"ＡＢＣＡＡ？？？”は、破棄される。
【００７５】
このようにして、ステップ４０７において、探索パターンの重複を取り除きながら、各演算手段７ａ〜７ｄにパターンを分配していく。
【００７６】
ケース３
上記のケース１、及び２では、要素数８に満たない文字は無視して処理を行っていなかった。処理によっては、要素数が指定された値に満たない文字も何らかの文字で補填して処理を行う場合もありうる。この例について、図８を用いて説明する。以下では、パターンの要素の数を８とし、パターンの各要素はＡ〜Ｚまでの文字か空白（スペース）を示す“△”であるとする。他は、上記ケース１と同じである。
【００７７】
最初のステップ５０１は、上記のケース１のステップ３０１と同じである。
【００７８】
次に、ステップ５０２において、パターン展開手段３は、記憶手段２の中の探索リストから探索パターン１の“ＡＢ＊”を取り出し、それを図４のケース１のように“？”等に置き換えて展開して保持する。また、“＊”は任意数の文字を示しているため、ここでは“ＡＢ"のように要素数が８個に満たないものも処理する。このような、場合は、“ＡＢ"を“△△△△△△ＡＢ"のように要素数が８個になるように補填する。
【００７９】
次に、ステップ５０３〜５０６までは、上記のケース１のステップ３０３〜３０６と同じである。
【００８０】
次に、ステップ５０７において、図８の展開パターン５"△△△△ＡＢ？？”は、パターン内の２要素が任意文字であり、粒度単位未満である。このようなパターンを処理する場合、パターン展開手段３は、展開パターン５“△△△△ＡＢ？？”を、粒度単位の大きさになるように、“△△△△Ａ？？？”に変換し、パターン検索手段４に送る。また、パターン展開手段３は、記憶手段２の中の処理済みリストに、処理完了済みのパターンとしてパターン“△△△△Ａ？？？”を追加する。
【００８１】
次に、ステップ５０８において、同様にして、図８の展開パターン６"△△△△△ＡＢ？”も粒度単位の大きさになるように、“△△△△△？？？”に変換する。変換後のパターンはパターン検索手段４に送られ、重複無し、変更有りと判断される。このため、“△△△△△？？？”が制御手段５に送られる。また、記憶手段２の処理済みリストにパターン“△△△△△？？？”が追加される。
【００８２】
次に、ステップ５０９において、同様にして、図８の展開パターン７"△△△△△△ＡＢ"も粒度単位の大きさになるように、“△△△△△？？？”に変換する。この場合、変換後のパターンはパターン検索手段４に送られるが、処理済みリストの中の追加パターン２と一致するものとして重複有りと判断される。このため、パターン“△△△△△？？？”は破棄される。このため、パターン検索手段４がパターン展開手段３に新たなパターンを要求し、処理が継続される。
【００８３】
そして、ステップ５１０において、これ以降の処理は、ケース１のステップ３０７以降と同じである。
【００８４】
なお、本例では空白を示す“△”で補填を行っているが、ヌル文字、０などの使用者によりあらかじめ定められた文字で補填してもよい。また、図８の例では、文字の左側に“△”を補填しているが、右側に“△”を補填する場合もありうる。さらには、“ＡＢ"のような、定められた要素数に満たないものは破棄するという場合もありうる。どのような処理を採用するかは使用者によりあらかじめ定められているものとする。
【００８５】
また、上記の説明では、パターン内の要素が文字であるとして説明を行ったが、各要素が数字や何らかのデータであっても機能や動作に全く問題はない。
【００８６】
このようにして、パターンを粒度単位で展開して重複の検索を行うことにより、パターンの重複を効果的に除去することができる。また、粒度単位未満のパターンをそのまま演算手段で送ったとしても、通信のオーバヘッド等により、粒度単位でパターンを演算手段に送った場合の処理時間と同程度になる場合がある。このため、粒度単位でパターンを送った方が処理時間が同程度で、それ以降のパターンで重複がある場合に、重複するパターンを簡単に除くことができる。このため、重複するパターンでの無駄な処理を省くことができ、装置の処理性能を上げることができる。
【００８７】
実施の形態２．
この発明の実施の形態２に係るパターン分配装置について図面を参照しながら説明する。
【００８８】
この発明の実施の形態２に係るパターン分配装置の構成は、図１に示す上記実施の形態１と同様である。
【００８９】
上記実施の形態１では、パターン展開手段３において、粒度単位まで展開したパターンをパターン検索手段４に送り、重複検索を行っていた。これに対して、粒度単位まで展開する前の中間状態のパターンをパターン検索手段４に送り、重複するパターンを破棄するようにしてもよい。
【００９０】
つぎに、この実施の形態２に係るパターン分配装置の動作について図面を参照しながら説明する。図９は、この発明の実施の形態２に係るパターン分配装置のパターン展開例を示す図である。
【００９１】
ステップ６０１、及び６０２の動作は、上記実施の形態１のステップ２０１、及び２０２と同じであり、ステップ６０３以降の動作が次のようになる。
【００９２】
次に、ステップ６０３において、パターン展開手段３は、展開したパターンの一部の要素を置き換える。置き換える際には、一度に粒度単位に置き換えずに、段階的に置き換えを行う。置き換えられたパターンをパターン検索手段４に送る。パターンが粒度単位に満たない場合の処理は、上記実施の形態１のステップ２０３と同じである。
【００９３】
次に、ステップ６０４において、パターン検索手段４では、パターンと処理済みリストとの重複検索を行う。検索の結果により、以下のステップ６０４ａ〜６０４ｃのうちのいずれかの処理を行う。
【００９４】
ステップ６０４ａにおいて、探索リストの処理が完了したパターンの中に完全に重複するものがあると判断された場合、パターン検索手段４は、送られてきたパターンを破棄し、パターン展開手段３には「パターンが破棄された」旨の情報を返す。
【００９５】
ステップ６０４ｂにおいて、重複がないと判断された場合は、パターン検索手段４は、送られてきたパターンを「重複無し」の情報と共にパターン展開手段３に返す。また、重複無しと判断されたパターンが変更有りのパターンの場合、処理済みのパターンとして変更後のパターンを、記憶手段２の中の処理済みリストに追加する。
【００９６】
ステップ６０４ｃにおいて、パターンの一部が重複していると判断された場合は、パターン検索手段４は、送られてきたパターンを「一部重複有り」の情報と共にパターン展開手段３に返す。
【００９７】
次に、ステップ６０５において、パターン展開手段３は、ステップ６０４での結果により、以下の処理を行う。
【００９８】
ステップ６０５ａにおいて、パターン検索手段４でパターンが破棄された場合は、次のパターンに対してステップ６０３以降の処理を行う。
【００９９】
ステップ６０５ｂにおいて、「重複無し」としてパターンが返ってきた場合は、そのパターンを粒度単位まで展開し、粒度単位まで展開したパターンを順次、制御手段５に送る。
【０１００】
ステップ６０５ｃにおいて、「一部重複有り」としてパターンが返ってきた場合は、そのパターンをステップ６０３のように段階的に置き換え、ステップ６０３〜６０５までの操作を行う。重複の無い、粒度単位のパターンが得られるまで、この操作を繰り返す。
【０１０１】
ステップ６０６において、これ以降の動作は、上記実施の形態１の２０５以降と同じである。
【０１０２】
次に、図４、及び図９を例に各部の動作を説明する。この例において、パターンの要素の数、パターンの各要素の文字等は、上記実施の形態１のケース１と同じである。
【０１０３】
この例では、上記の実施の形態１のケース１と同様に、図４の探索リストにあるパターンを処理するものとする。
【０１０４】
ステップ６１１〜６１７までの処理は、上記実施の形態１のケース１と同じである。
【０１０５】
次に、ステップ６１８において、探索パターン３"＊ＢＣ＊”を展開した例が図９である。図９において、展開パターン２を段階的に置き換えた、中間パターン２−１"ＡＢＣ？？？？？”が、パターン検索手段４に送られて一致検索を行った場合、処理済みリストの探索パターン１と一致していると判断される。このため、中間パターン２−１"ＡＢＣ？？？？？”は破棄される。
【０１０６】
次に、ステップ６１９において、次の中間パターン２−２“ＢＢＣ？？？？？”をパターン検索手段４に送り一致検索を行った場合、「重複無し」と判断される。このため、中間パターン２−２"ＢＢＣ？？？？？”は、パターン展開手段３で粒度単位まで置き換えられ、順次、制御手段５に送られる。
【０１０７】
このようにして、ステップ６２０において、探索パターンの重複を取り除きながら、各演算手段７ａ〜７ｄにパターンを分配していく。
【０１０８】
本パターン分配装置は、以上の動作を繰り返すことによって動作し、パターンを各演算手段に分配する。また、上記の説明では、パターンの中間状態が１つであったが、中間状態が階層的に複数合っても機能や動作に全く問題はない。
【０１０９】
このようにして、中間状態のパターンの重複の検索を行うことにより、上記実施の形態１の場合に比べて余分な検索回数を減らすことができる。
【０１１０】
実施の形態３．
この発明の実施の形態３に係るパターン分配装置について図面を参照しながら説明する。図１０は、この発明の実施の形態３に係るパターン分配装置の構成を示す図である。
【０１１１】
上記実施の形態１では、パターン検索手段４が一つであった。これに対して、演算手段の処理時間に比べて、パターン検索手段４での処理時間が長い場合、複数個のパターン検索手段をもうけてもよい。
【０１１２】
図１０において、４ａ、及び４ｂは実施の形態１と同じパターン検索手段である。それ以外は、実施の形態１の場合と同じである。
【０１１３】
つぎに、この実施の形態３に係るパターン分配装置の動作について図面を参照しながら説明する。
【０１１４】
ステップ７０１〜７０２までの動作は、上記実施の形態１のステップ２０１〜２０２と同じであり、ステップ７０３以降の動作が次のようになる。
【０１１５】
次に、ステップ７０３において、パターン展開手段３において、粒度単位に置き換えられたパターンをパターン検索手段４ａに送る。もし、パターン検索手段４ａが検索中の場合は、パターン検索手段４ｂにパターンを送る。パターン検索手段４ａ、４ｂともに検索中の場合は、いずれかのパターン検索手段での検索が終了するまでパターンを保持する。その後、検索が終了したパターン検索手段に保持しているパターンを転送する。それ以外の動作は、実施の形態１のステップ２０３の動作と同じである。
【０１１６】
次に、ステップ７０４において、パターン検索手段４ａ、４ｂそれぞれの動作は、実施の形態１のステップ２０４と同じである。
【０１１７】
さらに、ステップ７０５〜７０６での動作は、実施の形態１の２０５〜２０６と同じである。
【０１１８】
本パターン分配装置は、以上の動作を繰り返すことによって動作し、パターンを各演算手段に分配する。このようにして、複数のパターン検索手段をもうけることにより、パターン検索手段での処理時間を短縮することができ、装置全体の動作効率を上げることができる。
【０１１９】
実施の形態４．
この発明の実施の形態４に係るパターン分配装置について図面を参照しながら説明する。図１１は、この発明の実施の形態４に係るパターン分配装置の構成を示す図である。
【０１２０】
上記実施の形態１では、パターン検索を処理済みリストの中のパターンに対して逐次行っていた。これに対して、パターンのリストから検索用のハッシュ表を作成し、このハッシュ表に対して検索を行うようにしてもよい。
【０１２１】
図１１において、８は記憶手段２の中の処理済みリストからハッシュ表を作成するハッシュ表作成手段である。それ以外は、実施の形態１の場合と同じである。
【０１２２】
つぎに、この実施の形態４に係るパターン分配装置の動作について図面を参照しながら説明する。
【０１２３】
ステップ８０１〜８０３までの動作は、上記実施の形態１の２０１〜２０３と同じであり、ステップ８０４以降の動作が次のようになる。
【０１２４】
次に、ステップ８０３において、ハッシュ表作成手段８は、記憶手段２の処理済みリストのパターンを取得し、ハッシュ表を作成する。すでに、ハッシュ表が作成してある場合は、新たに追加されたパターンだけを記憶手段２の処理済みリストから取得し、ハッシュ表に追加する。ハッシュ表作成手段８は、作成したハッシュ表をパターン検索手段４に渡す。また、作成したハッシュ表は、ハッシュ表作成手段８で保持される。
【０１２５】
次に、ステップ８０４において、パターン検索手段４は、ハッシュ表を使って、重複検索を行う。それ以外の処理は、実施の形態１のステップ２０４と同じである。
【０１２６】
そして、ステップ８０５において、以降の処理は、実施の形態１の２０５以降と同じである。
【０１２７】
また、ハッシュ表の形式は、さまざまな方法が考えられるが、その一例を図１２に示す。
【０１２８】
なお、図１２の例では、実施の形態１のように、パターンの要素の数を８としている。また、パターンの各要素はＡ〜Ｚまでの文字であるとする。
【０１２９】
図１２では、処理済みリストのパターンを２個の決定要素で分類（カテゴリ分け）する。図１２の“ＡＡ”とあるカテゴリは、「“Ａ”という要素をもち、（間に何らかの要素を含むに関らず）次に“Ａ”のくるパターン」を示す。この場合、２つの要素の間に何らかの要素が含まれてもよいものとする。このため、探索パターン２の“Ｅ＊Ｃ＊”はカテゴリ“ＥＣ”に、探索パターン５の“Ｂ＊ＥＣ＊”はカテゴリ“ＢＣ”とカテゴリ“ＥＣ”に分類される。
【０１３０】
また、例えば、探索パターン４の“＊Ｃ”のように決定要素が２要素未満のものは、未決定要素を置き換えた場合に分類可能な全てのカテゴリに振り分ける。この場合、探索パターン４の“＊Ｃ”は、カテゴリ“ＡＣ”、カテゴリ“ＢＣ”、カテゴリ“ＥＣ”等の対応する全てのカテゴリに振り分けられる。
【０１３１】
実際に、パターン検索手段４でハッシュ表を用いてパターンを検索する場合の例を示す。
【０１３２】
ハッシュ表で検索を行う場合は、対象パターンの決定要素の中の２要素の組み合わせ全てに対してハッシュ表に検索をかけ、カテゴリに分類する。各カテゴリ内の被検索パターンに対しては、実施の形態１で示したような検索を逐次行う。
【０１３３】
例えば、パターン“ＡＢＡＡＡ？？？”を対象パターンとして検索する場合、カテゴリ“ＡＡ”、“ＡＢ”、“ＢＡ”に分類される。その後、各カテゴリ内の被検索パターン“ＡＢ＊”等に対して対象パターンとの重複検索を行う。
【０１３４】
このようにして、ハッシュ表を用いて検索を行うことにより、対応するカテゴリのパターンに対してだけ重複検索を行えばよく、無駄な検索を省き高速な検索を行うことができる。
【０１３５】
実施の形態５．
この発明の実施の形態５に係るパターン分配装置について図面を参照しながら説明する。図１３は、この発明の実施の形態５に係るパターン分配装置の構成を示す図である。
【０１３６】
上記実施の形態１では、パターン検索手段４での検索が終了するまで、処理を行うパターンが得られなかった。これに対して、演算手段が処理待ち状態になった場合に、パターン検索手段４での検索が途中であっても、検索を中止しパターンを得られるようにしてもよい。
【０１３７】
図１３において、９は制御手段５からのパターン要求を受けて、パターン検索手段４に検索中止指示を出す検索中止手段である。それ以外は、実施の形態１の場合と同じである。
【０１３８】
つぎに、この実施の形態５に係るパターン分配装置の動作について図面を参照しながら説明する。
【０１３９】
ステップ９０１において、制御手段５は、処理待ち状態の演算手段があり、パターン保持手段６にパターンがない場合は、検索中止手段９にパターン要求の指示を出す。それ以外の処理は、実施の形態１のステップ２０１と同じである。
【０１４０】
次に、ステップ９０２〜９０３の動作は、実施の形態１の２０２〜２０３と同じである。
【０１４１】
次に、ステップ９０４において、検索中止手段９は、制御手段５からパターン要求の指示があった場合、パターン検索手段４が実行中であれば、検索中止の指示を出す。また、パターン検索手段４が実行中でなければ、実行を開始するまでパターン検索手段４の動作を監視し、動作開始時に検索中止の指示を出す。
【０１４２】
次に、ステップ９０５において、パターン検索手段４では、粒度単位のパターンと処理済みリストとの重複検索を実施の形態１のステップ２０４と同じように行う。ただし、検索中止手段９から検索中止の指示があった場合は、即座に検索を中止し、検索途中のパターンを制御手段５に送る。このパターンは、重複のないパターンとして扱われ、必要ならば探索リストへの追加等の処理が、実施の形態１のステップ２０４のように行われる。
【０１４３】
次に、ステップ９０６において、制御手段５は、送られてきたパターンを、演算手段７ａ〜７ｄの内で現在、処理待ち状態の演算手段がある場合は、その演算手段に分配する。演算手段７ａ〜７ｄに処理待ち状態のものがない場合は、パターン保持手段６にパターンを格納する。
【０１４４】
そして、ステップ９０７において、演算手段７ａ〜７ｄでは、送られてきたパターンの要素の内、ワイルドカードで指定された要素の全てを実際の文字に置き換えて展開し、展開した各パターンについて演算を実行する。展開したすべてのパターンの演算が終了した場合は、処理待ち状態になる。
【０１４５】
本パターン分配装置は、以上の動作を繰り返すことによって動作し、パターンを各演算手段に分配する。このようにして、検索中止手段９をもうけることにより、演算手段のパターンの要求に対して、最小の遅延時間で対応することができる。この場合は、パターンの重複を許容することになるが、パターン検索手段４での処理時間を短縮することができ、演算手段の待ち時間を減らすことができるため、全体的なパターンの重複の度合いや粒度の大きさによっては、装置全体の動作効率を上げることができる。
【０１４６】
実施の形態６．
この発明の実施の形態６に係るパターン分配装置について図面を参照しながら説明する。図１４は、この発明の実施の形態６に係るパターン分配装置の構成を示す図である。
【０１４７】
上記実施の形態１では、粒度の大きさをあらかじめ決められたものとしていた。これに対して、検索の処理のかかる時間と、各演算手段での演算にかかる時間の比率により、粒度を自動的に変更するようににしてもよい。
【０１４８】
図１４において、１０は制御手段５からパターン検索手段４での検索時間と、演算手段での演算時間の情報を得て、粒度の変更の指示を出す粒度変更手段である。それ以外は、上記実施の形態１の場合と同じである。
【０１４９】
つぎに、この実施の形態６に係るパターン分配装置の動作について図面を参照しながら説明する。
【０１５０】
ステップ１００１において、制御手段５は、パターン展開手段３にパターンの要求を出す際に、その時刻を記録する。それ以外は、上記実施の形態１のステップ２０１と同じである。
【０１５１】
次に、ステップ２０２〜２０４までの動作は、実施の形態１と同じである。
【０１５２】
次に、ステップ１００５において、制御手段５は、送られてきたパターンを受け取った時刻を記録し、パターン要求を出した時刻との差を取り、それを検索時間として保持する。パターン要求時からパターンを受け取るまでの間に別のパターン要求を出した場合は、対応するパターンの時刻から検索時間を計測する。また、制御手段５は、パターンを各演算手段７ａ〜７ｄに分配した際に、その時刻を記録する。それ以外の処理は、実施の形態１と同じである。
【０１５３】
次に、ステップ１００６において、このステップの処理は、実施の形態１のステップ２０６と同じである。
【０１５４】
次に、ステップ１００７において、各演算手段７ａ〜７ｄが処理待ち状態になった場合に、制御手段５はその時刻を記録し、対応するパターンの投入時の時刻と差をとり、それを演算時間とする。制御手段５は、計測した検索時間と演算時間を逐次、粒度変更手段１０に送る。
【０１５５】
次に、ステップ１００８において、粒度変更手段１０は、検索時間と演算時間の比をとり、その比が定められた値以上になった場合（検索時間が演算時間に比べて大きくなった場合）は、粒度を大きくするようパターン展開手段３に指示を出す。また、比が定められた値以下になった場合（検索時間が演算時間に比べて極端に小さくなった場合）には、粒度を小さくするようパターン展開手段３に指示を出す。
【０１５６】
そして、ステップ１００９において、パターン展開手段３は、粒度変更の指示を粒度変更手段１０から受け取った場合には、粒度を変更しそれ以降のパターンを展開、置き換える場合にその粒度を使用する。
【０１５７】
本パターン分配装置は、以上の動作を繰り返すことによって動作し、パターンを各演算手段に分配する。また、上記実施の形態６において、数個のパターンに対する検索時間、もしくは演算時間の平均をとるようにし、その平均時間に対して比を求めるようにしてもよい。
【０１５８】
パターンの重複をできるだけ除去するためには粒度を小さく取ったほうがよいが、検索時間が増加する。また、データの転送頻度を減らして装置の効率を上げるためには、粒度を大きく取った方がよい。上記のようにして、粒度変更手段１０を設けることにより、検索時間と演算時間の比から処理に見合った粒度を設定できる。
【０１５９】
実施の形態７．
この発明の実施の形態７に係るパターン分配装置について図面を参照しながら説明する。この発明の実施の形態７に係るパターン分配装置の構成は、上記実施の形態６と同様である。
【０１６０】
上記実施の形態６では、検索時間と演算時間の比から粒度の大きさ決定していた。これに対して、処理済リストの大きさと重複度合いにより、粒度を自動的に変更するようににしてもよい。
【０１６１】
つぎに、この実施の形態７に係るパターン分配装置の動作について図面を参照しながら説明する。
【０１６２】
ステップ１１０１及び１１０２の動作は、実施の形態１のステップ２０１及び２０２と同じである。
【０１６３】
次に、ステップ１１０３において、パターン展開手段３は、展開したパターンをそのまま、パターン検索手段４に送る。
【０１６４】
次に、ステップ１１０４において、パターン検索手段４では、パターンと処理済リストとの重複検索を行う。検索の結果により、ステップ１１０４ａ、１１０４ｂ、及び１１０４ｃのうちのいずれかの処理を行う。
【０１６５】
ステップ１１０４ａの動作は、実施の形態１のステップ２０４ａと同じである。
【０１６６】
ステップ１１０４ｂにおいて、重複がないと判断された場合は、パターン検索手段４は、送られてきたパターンを「重複度０」の情報と共にパターン展開手段３に返す。
【０１６７】
ステップ１１０４ｃにおいて、パターンの一部が重複している場合には、一部重複のあるパターンの数を数え、その数を重複度とする。その後、そのパターンと重複度の情報をパターン展開手段３に返す。
【０１６８】
次に、ステップ１１０５において、パターン展開手段３は、パターン検索手段４からパターンが返ってきた場合、そのパターンに対応する重複度と、記憶手段２にある処理済リストの中のパターンの数を粒度変更手段１０に送る。
【０１６９】
次に、ステップ１１０６において、粒度変更手段１０は、重複度と処理済リストの数から使用する粒度を算出する。粒度の算出には、例えば、あらかじめ決められた重複度と処理済リストの数からなる算出式を用いてもよい。また、重複度と処理済リストからなるテーブル等を用いて粒度を算出するようにしてもよい。この算出された粒度は、パターン展開手段３に送られる。
【０１７０】
次に、ステップ１１０７において、パターン展開手段３は、粒度変更手段１０から送られてきた粒度を用いて、パターンを置き換える。それ以外の処理は、実施の形態１のステップ２０３と同じである。
【０１７１】
そして、ステップ１１０８において、これ以降の処理は、実施の形態１のステップ２０４以降の処理と同じである。
【０１７２】
本パターン分配装置は、以上の動作を繰り返すことによって動作し、パターンを各演算手段に分配する。パターンの重複を探索する場合、重複するものが多いパターンは細かい粒度で検索を行った方がよいが、粒度を細かくすると演算処理時間に対する検索時間が大きくなる。また、処理済みリストの数が多い場合は検索に時間がかかるので、粒度を大きくした方がよい。上記のようにして、粒度変更手段１０において、処理済みリストと重複度から粒度を求めることにより、検索時間と演算時間に見合った粒度を設定できる。
【０１７９】
【発明の効果】
この発明の請求項１に係るパターン分配装置は、以上説明したとおり、所定のパターンからなる探索リスト、及び所定の処理済みパターンからなる処理済みリストを保持する記憶手段と、送られてきたパターンに対する解の探索を行う複数の演算手段と、前記記憶手段に保持された探索リストから、分配するパターンを粒度単位に展開するパターン展開手段と、前記粒度単位に展開されたパターン、及び前記処理済みリストの重複を検索して重複のあるパターンを破棄するパターン検索手段と、前記パターン検索手段から送られてきた重複がないパターンを前記複数の演算手段に分配する制御手段と、前記制御手段から送られてきた前記パターン検索手段の検索時間、及び前記各演算手段の演算時間の比率に基づいて粒度の大きさを決定し、前記パターン展開手段へ粒度変更の指示を出す粒度変更手段とを備えたので、検索時間と演算時間の比から処理に見合った粒度を設定できるという効果を奏する。
【０１８０】
この発明の請求項２に係るパターン分配装置は、以上説明したとおり、所定のパターンからなる探索リスト、及び所定の処理済みパターンからなる処理済みリストを保持する記憶手段と、送られてきたパターンに対する解の探索を行う複数の演算手段と、前記記憶手段に保持された探索リストから、分配するパターンを粒度単位に展開するパターン展開手段と、前記粒度単位に展開されたパターン、及び前記処理済みリストの重複を検索して重複のあるパターンを破棄するパターン検索手段と、前記パターン検索手段から送られてきた重複がないパターンを前記複数の演算手段に分配する制御手段と、前記パターン展開手段から送られてきた前記処理済みリストの大きさ、及びパターンの重複度の比率に基づいて粒度の大きさを決定し、前記パターン展開手段へ粒度変更の指示を出す粒度変更手段とを備えたので、検索時間と演算時間の比から処理に見合った粒度を設定できるという効果を奏する。
【図面の簡単な説明】
【図１】  この発明の実施の形態１に係るパターン分配装置の構成を示すブロック図である。
【図２】  この発明の実施の形態１に係るパターン分配装置の動作を示すフローチャートである。
【図３】  この発明の実施の形態１に係るパターン分配装置の探索リスト例を示す図である。
【図４】  この発明の実施の形態１に係るパターン分配装置のパターンの展開例を示す図である。
【図５】  この発明の実施の形態１に係るパターン分配装置のパターンの展開例を示す図である。
【図６】  この発明の実施の形態１に係るパターン分配装置のパターンの展開例を示す図である。
【図７】  この発明の実施の形態１に係るパターン分配装置のパターンの展開例を示す図である。
【図８】  この発明の実施の形態１に係るパターン分配装置のパターンの展開例を示す図である。
【図９】  この発明の実施の形態２に係るパターン分配装置のパターンの展開例を示す図である。
【図１０】  この発明の実施の形態３に係るパターン分配装置の構成を示すブロック図である。
【図１１】  この発明の実施の形態４に係るパターン分配装置の構成を示すブロック図である。
【図１２】  この発明の実施の形態４に係るパターン分配装置のハッシュ表例を示す図である。
【図１３】  この発明の実施の形態５に係るパターン分配装置の構成を示すブロック図である。
【図１４】  この発明の実施の形態６及び実施の形態７に係るパターン分配装置の構成を示すブロック図である。
【図１５】  従来パターン分配装置の構成を示すブロック図である。
【符号の説明】
１  パターン分配装置、２  記憶手段、３  パターン展開手段、４、４ａ、４ｂ  パターン検索手段、５  制御手段、６  パターン保持手段、７ａ、７ｂ、７ｃ、７ｄ  演算手段、８  ハッシュ表作成手段、９  検索中止手段、１０  粒度変更手段。
【図１】
0003961775.tif 000002
【図２】
0003961775.tif 000003
【図３】
0003961775.tif 000004
【図４】
0003961775.tif 000005
【図５】
0003961775.tif 000006
【図６】
0003961775.tif 000007
【図７】
0003961775.tif 000008
【図８】
0003961775.tif 000009
【図９】
0003961775.tif 000010
【図１０】
0003961775.tif 000011
【図１１】
0003961775.tif 000012
【図１２】
0003961775.tif 000013
【図１３】
0003961775.tif 000014
【図１４】
0003961775.tif 000015
【図１５】
0003961775.tif 000016