JPH01318165A - 回路パターン検索方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要〕 回路中から与えられた回路構造にマツチする部分を検索
する回路パターン検索方式に関し、被検索回路を分割し
て複数のプロセッサ・エレメントに割り当て、ノード情
報および制御フラグ情報を順次全プロセッサ・エレメン
トに通知して並列的にバクーンマソチを行い、該当回路
パターンを高速に検索することを目的とし、 回路素子データを保持する回路素子データ保持部と、制
御フラグ情報およびノード情報を保持するフラグ・ノー
ド情報保持部と、回路素子データ保持部に保持されてい
る回路素子データとフラグ・ノード情報保持部に保持さ
れているノード情報とが一牧するか否かを比較する比較
回路とをそれぞれ持つ複数のプロセッサ・エレメントを
備え、ホストが被検索回路を複数に分割した各回路素子
データを各プロセッサ・エレメントにそれぞれ割り当て
て上記回路素子データ保持部に書き込んだ後、検索回路
構造のノー］゛情報および制御フラグ情報を１ｌｌｉ次
全プロセッサ・エレメントに通知して上記フラグ・ノー
ド情報保持部に格納し、このフラグ・ノード情報保持部
に格納されたノード情報と、上記回路素子データ保持部
に保持されている回路素子データとを上記比較回路によ
って全プロセッサ・エレメントで並列に比較して、一致
すると判別した該当プロセッサ・エレメントが当該通知
したノード情報を取り込むと共にフラグ・ノード情報保
持部に格納した制御フラグ情報に対応して、マツチ１３
号を該当プロセッサエレメント、ホストに通知、あるい
は他のプロセッサ・エレメントからのマツチ通知を受け
るまで待機することにより、被検索回路からマツチする
部分を同時に複数検索するように構成する。

〔産業上の利用分野〕

本発明は、論理素子およびその論理的接続関係を複数の
プロセッサエレメントに割り当て、ホスト計Ｘ機から送
出した検索すべき回路構造にマツチする回路部分を検出
する回路パターン検索方式％式％ 論理回路の自動合成は、論理回路素子のネットワーク内
のある回路パターンを、より適切な構成に変換すること
を基本的な処理としている。この処理において、ある素
子の接続の前後関係や素子の属性を評価し、より小さい
素子からなる回路構成に分解することは比較的に取り扱
い易いが、複数の素子からなる回路パターンを見出すこ
とは不ｉ）意であり多くの時間を要する。このため、合
成処理性能の向上を図るために、回路パターンの検索の
高速化が望まれている。

〔従来の技術〕

従来、上逮した複数の素子からなる回路パターンを見出
す問題に対しては、各部分回路パターンのノードと、実
際の回路データである素子との比較を１ステツプづつ行
っている。例えば入力の組み合せを許さない木構造の比
較において、第５図に示すように、被検索論理回路を構
成するある素子ａ０に着目し、これと照合パターンＰ０
とを比較してマツチすれば更に入力側の素子ａｌｌと照
合パターンの入力側ノードｐＨ、入力側の素子ａ１□と
照合パターンの入力側ノードＰ１□などに対して同様の
比較を進める。そして、回路パターンの全体が論理回路
の部分にマツチすると判明した場合、このマツチした部
分を取り出し、例えばマツチした回路構造を持つＬＳＩ
のユニットセルで置き換えるなどしている。一方、マツ
チに失敗すると、論理回路内の他の素子に着目し、同様
に゛？マツチる部分があるか否かを検索するようにして
いる。

〔発明が解決しようとする課題〕

従って、複数の回路素子からなるバクーン同士を比較す
る場合、上記従来の手法は一般に回路の素子数の指数オ
ーダの時間が必要となってしまうという問題がある。ま
た、回路内に指定された回路パターンと同一の構造を持
つ部分力１Ｕ数存在した場合、逐次的に見出していたた
め、いわば並列的に見出すことができず、迅速に検索処
理し得ないという問題がある。

本発明は、被検索回路を分割して複数のプロセッサ・エ
レメントに割り当て、ノード情報および制御フラグ情報
を順次全プロセッサ・エレメントに通知して並列的にバ
クーンマソチを行い、該当回路パターンを高速に検索す
ることを目的としている。

〔課題を解決する手段〕

第１図は本発明の原理ブロック図を示す。

第１図において、ＰＥ（プロセッサ・エレメント）ｌは
、被検索回路を複数に分割して割り当てられた回路素子
データに対して、通知されたパターンがマツチするか否
かを比較などするものである。

回路素子データ保持部２は、ホストが被検索回路を複数
に分割し、当該ＰＥＩに割り当てた回路素子データを保
持するものである。

フラグ・ノード情報保持部３は、ホストが全ＰＥｌに送
信した制御フラグ情報および検索する回路構造における
素子の満たすべき条件を納めるノード情報を保持するも
のである。

比較回路４は、回路素子データ保持部２に保持されてい
る予め割り当てられた回路素子データと、ホストから送
信されてフラグ・ノード情報保持部３に保持されている
ノード情報とが一致（マツチ）するか否かを比較するも
のである。

制御装置５は、ホスト、他のＰＥＩとの間の通信などを
行うものである。

〔作用〕

本発明は、第１図に示すように、図示外のホストが、被
検索回路を複数に分割してこれを各ＰＥ１に通知して回
路素子データ保持部２に保持させた後、ノード情報およ
び制御フラグ情報を全ＰＥ１に送信してフラグ・ノード
情報保持部３に保持させ、比較回路４が回路素子データ
保持部２に保持されている回路素子データと、フラグ・
ノード情報保持部３に保持されているノード情報とが一
致するか否かを比較し、一致（マツチ）していると判別
した場合に、当該ノード情報を取り込み、更に制御フラ
グ情報の指示に対応して、他のＰＥ１、ポストにマツチ
通知、あるいは他のＰＥＩからマツチ通知を受けるまで
待機するようにしている。

従って、ホストが被検索回路を分割して複数の１”’Ｅ
ｌに割り当て、検索しようとする回路構造のノード情報
を順次全ＰＥＩに送信し、一致したＰＥ１が指示された
他のＰＥＩ、ホスト、あるいは他のＰＥＩからのマツチ
通知があるまで待機などすることにより、被検索回路か
らノード（検索しようとする回路パターン）に合致する
パターンを並列かつ同時に複数検索することが可能とな
る。

〔実施例〕

次に、第２図フローチャートを用いて本発明の１実施例
の構成および動作を詳細に説明する。

第２図（イ）を用いてホストの処理を説明する。

第２図（イ）において、■は、回路素子データを全ＰＥ
Ｉに書き込む。これは、ホストが被検索回路を分割、例
えば第３図ＰＥｆｌ＋ないしＰ　Ｅ　（３）中に記載す
るように分割し、各ＰＥ（１１ないしＰＥ（３１にそれ
ぞれ図示のように書き込むことを意味している。この回
路素子データは、例えばＰＥ（３１に示すように、回路
素子の機能“ＡＮＤ　（論理積回路）”および接続関係
“Ｘ、Ｙ、Ｚ　（端子Ｘ、Ｙ、Ｚに接続されている接続
先情報）°から構成されている。この回路素子データは
、第１図回路素子データ保持部２に書き込まれて保持さ
れる。

■は、ノード情報を順次全ＰＥＩに放送する。

これは、比較する回路構造の構成要素、例えば第３図ホ
スト１中が持つ検索回路構造１２の構成要素１２−１中
に記載したものの先頭から順次１つづつ取り出し、第４
図ノード・フラグ情ｔａ例中の第１行ないし第３行のＰ
、　、Ｐ、いｐｅｇに格納したノード情報を、順次全Ｐ
ＥＩに送信することを意味している。この送信されたノ
ード情報は、第１図フラグ・ノード情報保持部３に取り
込まれ、保持される。

■は、該当ＰＥＩからマツチ信号をうける。これは、■
の送信に対応して、マツチしたＰＥＩからマツチ通知を
受けることを意味している。これにより、ホストは、被
検索回路中のいずれのパターンとマツチしたかを知るこ
とができる。

第２図（ロ）を用いてプロセッサ・エレメント（ＰＥ）
ｌの処理を説明する。

第２図（ロ）において、■は、送信されたノード情報と
回路素子データとを比較する。これは、第２図（イ）■
で回路素子データ保持部２に書き込まれて保持されてい
る回路素子データと、第２図（イ）■でフラグ・ノード
情報保持部３に取り込まれて保持されているノード情報
とが一致するか否かを、全ＰＥ１が並列にそれぞれ比較
することを意味している。ＭａｔｃｈＬ、た場合（マツ
チした場合）には、■を実行する。Ｎｏｔ　　Ｍａｔｃ
ｈした場合（マツチしない場合）には、［相］で次の比
較のためにスタートに戻る。

＠は、入力側の部分回路の比較を行う必要があるか否か
を判別する。これは、第２図（イ）■で送信されノード
・フラグ情報中の制御フラグ情報を参照して、入力側の
部分回路との比較が指示されたか否かを判別することを
意味している。例えばマツチした第４図ノード・フラグ
情報中の第１行目の先頭の記載−ａｉｔ−ａｌｌ−ｉｎ
ｐｕｔ　ＰＥ”のように、他のＰＥＩからのマツチ信号
の通知を待つように指定されたか否かを判別することで
ある。ＹＥＳの場合には、■で指定に応じて全部／一部
のマツチ信号を待つ、ＮＯの場合には、■を実行する。

［相］は、伝達の向きはいずれかを判別する。Ｔｏｌ（
ｏｓｔの場合（伝達の向きがホストの場合）には、■で
マツチ１３号をホストへ送出する。一方、Ｔｏ　０ｕｔ
ｐｕＬの場合（伝達の向きが他のＰＥＩの場合）には、
マツチ信号を他のＰＥＩへ送出する。

以上のように、第２図（イ）■で被検索回路を分割して
各ＰＩＥ１に割り当て、■で検索しようとするパターン
に関するノード・フラグ情報を順次全ＰＥＩに送信して
一斉に比較させ、該当ＰＥＩがこのノード・フラグ情報
を取り込むと共に当該ノード・フラグ情報で指定された
ＰＥ１、ホストなどにマツチ信号を送出することを繰り
返すことにより、複数のＰＥＩが並列かつ同時に複数の
パターンを検索することが可能となる。

次に、第３図および第４図を用いて、本発明の１実施例
構成の具体例を説明する。

第１に、第３図において、ＰＥ口）、Ｐ　Ｅ　（２）、
ＰＥ（３）中に記載するように、ホスト１１が被検索回
路を分割して各ＰＥに割り当て、各ＰＥの回路素子デー
タ保持部２に書き込む（第２図（イ）■）。

これにより、各ＰＥはそれぞれ該当素子パターン（例え
ばＡＮＤ　（論理積回路））および接続関係情報（例え
ば入力端子がＸ、Ｚ、出力端子がＹ）を持つこととなる
。

第２に、第３図において、ホス）１１中に記載するよう
に、検索しようとする検索回路構造１２の構成要素１２
−１を図示Ｐ０、Ｐ、１、ｐ＋ｚのように分割し、これ
に接続関係を付与して作成した第４図ノード・フラグ情
報から、１つづつ順番に取り出して全ＰＥＩに送信する
（第２図（ロ）■）。

第３に、各ＰＥにおけるステップｌとして、ホスト１１
から第４図第１行目に記載した（ｗａｉｔ−ａｌｌ−ｉ
ｎｐｕｔ　ＰＥ　　ｎｏｔｉｆｙ−ｈｏｓｔ　ｔ　Ｐｏ
）　・（１１Ｐ　＠　”（ＡＮＤ　Ｘ＋ｙ＋２）（Ｘ＋
Ｌ２は変数）・・・・・（２）の通知を受けた第３図Ｐ
Ｅ（３１の比較回路４は、ホストから放送された（ＡＮ
Ｄχ＋ＬＺ）　　・・・・（３）予め割り当てられた（
ＡＮＤ　Ｘ、Ｙ、Ｚ）（Ｘ、Ｙ、Ｚは定数）・・・・・
・・・・・・・・・・・・・・・（４）とが一致（マツ
チ）することを比較して検出する。

この比較結果として 変数×・Ｘ（定数）・・・・・・・・・・・・・（５）
変数ｙ＝Ｙ（定数）・・・・・・・・・・・・・（６）
変数ｚ＝Ｘ（定数）・・パ・・・・・・・・・・（７）
を得る。そして、式（１）に記載された先頭の“−ａｉ
ｔ−ａｌｌ−ｉｎｐｕｔ　ｐｔ″によって他のＰＥから
のマツチ信号の通知を待つと共に、これら式（５）、（
６）の結果を関連する接続先のＰ　Ｒ（１１、ＰＥ（２
１に図示点線を用いて示すように通知する。

第４に、各ＰＥにおけるステップ２として、ホスト１１
から第４図第２行目に記載した（ｎｏ−Ｗａｉｔ　ｎｏ
ｔｉｆｙ−ｏｕｔｐｕｔ−ＰＥ　１ｆ−ｎｏ−ｂｒａｎ
ｃｈ　　Ｐ５．）・・・・・・・・・・・・・・・・・
・・（８）Ｐ＋＋＝（ＡＮＤ　ｗｔｘ、ｖ）（ｗ、ｘ＋
ｖは変数）・・・・・（９）の通知を受けた第３　［ｆ
ｆｌ　Ｐ　Ｅ　ｆｉｌの比較回路４は、ホストから送信
された（ＡＮＤ　ｗ、ｘ＋ν）・・・・αｌ予め割り当
てられた（ＡＮＤ　Ｗ、Ｘ、Ｖ）（Ｗ、Ｘ、Ｖは定数）
・・・・・・・・・・・・・・・・・・・・Ｑｌｌとが
一致（マツチ）することを比較して検出する。

この比較結果として 変数−・−（定数）・・・・・・・・・・・・・ａｚ変
数ν・Ｖ（定数）・・・・・・・・・・・・・α湯を得
る。そして、武（８）に記載された先頭の“ｎｏ−ｗａ
ｉｔ”によって他のＰＥからのマツチ信号の通知を待つ
ことなく、マツチ信号を図示点線を用いて示すよ・うに
該当する出力接続先のＰＥ（１）に通知する。

第５に、各ＰＥにおけるステップ３として、第４と同様
にして、ホストから第４図第３行目に記載した （ｎｏ−Ｗａｉｔ　ｎｏｔｉｆｙ−ｏｕｔｐｕｔ−ＰＨ
１ｆ−ｎｏ−ｂｒａｎｃｈ　　Ｐｌｔ）　　・・・・・
・・・・・・・・・・・・・・０すＰ　＋＋；（ＡＮＤ
　ｔ、ｚ、ｓ）　（ｔ、ｚ＋ｓは変数）・・−・・Ｑ９
の通知を受けた第３図ＰＥｆ２＋の比較回路４は、ホス
トから放送された（ＡＮＤ　ｔ、ｚ、ｓ）　　・・・・
αｅ予め割り当てられた（ＡＮＤ　Ｔ、２．５）（Ｔ、
Ｚ、Ｓは定数）・・・・・・・・・・・・・・・・・・
・・αηとがマツチすることを比較して検出する。この
比較結果として 変数ｔ＝Ｔ（定数）・・・・・・・・・・・・・０鴫変
数５＝Ｓ（定数）・・・・・・・・・・・・・Ｑ１を得
る。そして、式Ｑ４１に記載された先頭の“ｎｏ＞ａｉ
ｔ”によって他のＰＥからのマツチ信号の通知を待つこ
となく、マツチ信号を図示点線を用いて示すように該当
する出力接続先のＰＥｆｌ）に通知する。

第６に、第４でＰＥｆｌｌ、第５でＰ　Ｅ　（２１から
マ・フチ１エ号の通知を受けたＰ　Ｅ　＋３１は、式（
１１で指定された“ｎｏｔｉｆｙ−ｈｏｓｔ″に対応し
てホストにこのマ・ノチ信号の通知を行う。

以上の処理によって、ホストは各ＰＥからのマツチ信号
の通知に基づいて、予め分割して各ＰＥに割り当てたパ
ターンに対して、検索回路構造（検索回路パターン）１
２と一致するパターンがいずれの部分であるかを並列的
に知ることが可能となる。

第４図は比較回路のノード・フラグ情報例を示す。ここ
で、”ｗａｉｔ−ａｌｌ−ｉｎｐｕｔ　ｒ’Ｅ”は、全
ての他のＰＥからのマツチ信号の通知を待つ必要がる旨
を表す。“ｎｏ−ｗａｉｔ″は、他のＰＥからのマツチ
信号の通知を待つ必要がない旨を表す、“ｎｏｔｉｆｙ
−ｈ。

ｓｔ”は、マツチ信号をホストに通知する旨を表す。

“ｎｏｔｉｆｙ−ｏｕｔｐｕｔ−ＰＥは、マツチ信号を
該当接続先のＰＥに通知する旨を表す。Ｐｏ　、Ｐ＋＋
、Ｐ＋□は、第３図ホスト１１の検索回路構造１２を構
成する構成要素１２−１を表す。

〔発明の効果〕 以上説明したように、本発明によれば、ホストが被検索
回路を分割して複数のＰＥに割り当て、検索しようとす
る検索回路構造を順次全ＰＥに送信し、一致したＩ’Ｅ
が指定された他のＰＥ、ホストにマツチ通知、あるいは
他のＰＥからの入力情報があるまで待機などして並列処
理する構成を採用しているため、被検索回路から所定の
回路パターンに合致するパターンを並列かつ同時に複数
組、高速に検索することができる。

【図面の簡単な説明】

第１図は本発明の原理ブロック図、第２図は本発明の動
作説明フローチャート、第３図は本発明の詳細な説明図
、第４図は比較回路のノード・フラグ情報例、第５１２
］は従来の回路部分構造の比較説明図を示す。 図中、ｌはＰＥ（プロセッサニレメンｌ−）、２は回路
素子データ保持部、３はフラグ・ノード情報保持部、４
は比較回路、５は制ｉ１１装置、１１はホスト、１２は
検索回路構造、１２−１は構成要素を表す。

Claims (1)

1. 【特許請求の範囲】 回路中から与えられた回路構造にマッチする部分を検索
   する回路パターン検索方式において、回路素子データを
   保持する回路素子データ保持部（２）と、 制御フラグ情報およびノード情報を保持するフラグ・ノ
   ード情報保持部（３）と、 回路素子データ保持部（２）に保持されている回路素子
   データとフラグ・ノード情報保持部（３）に保持されて
   いるノード情報とが一致するか否かを比較する比較回路
   （４）とをそれぞれ持つ複数のプロセッサ・エレメント
   （１）を備え、 ホストが被検索回路を複数に分割した各回路素子データ
   を各プロセッサ・エレメント（１）にそれぞれ割り当て
   て上記回路素子データ保持部（２）に書き込んだ後、検
   索回路構造のノード情報および制御フラグ情報を順次全
   プロセッサ・エレメント（１）に通知して上記フラグ・
   ノード情報保持部（３）に格納し、このフラグ・ノード
   情報保持部（３）に格納されたノード情報と、上記回路
   素子データ保持部（２）に保持されている回路素子デー
   タとを上記比較回路（４）によって全プロセッサ・エレ
   メント（１）で並列に比較して、一致すると判別した該
   当プロセッサ・エレメント（１）が当該通知したノード
   情報を取り込むと共にフラグ・ノード情報保持部（３）
   に格納した制御フラグ情報に対応して、マッチ信号を該
   当プロセッサエレメント、ホストに通知、あるいは他の
   プロセッサ・エレメントからのマッチ通知を受けるまで
   待機することにより、被検索回路からマッチする部分を
   同時に複数検索するように構成したことを特徴とする回
   路パターン検索方式。