JPH0695348B2 - テンプレートマッチング用アドレス生成装置 - Google Patents

Description

【発明の詳細な説明】 ［産業上の利用分野］ この発明は、テンプレートマッチング用アドレス生成装
置に関し、特にデータフロー型情報処理装置のデータ対
生成部において行なわれるテンプレートマッチングのた
めのアドレスを生成する装置に関する。

［従来の技術］ 第５図は従来のデータフロー型情報処理装置の一例を示
すブロック図である。また、第６図は同装置におけるデ
ータパケットのフィールド構成を示す図である。

第５図において、プログラム記憶手段１はデータフロー
プログラムを記憶しており、第６図における入力データ
パケットの先行情報に基づいたアドレス指定によって、
次位の先行情報および次位の命令情報が読出され、当該
各読出情報を前記入力データパケットの先行フィールド
および命令フィールドに格納して出力するものである。
データ対生成手段２はプログラム記憶手段１から出力さ
れるデータパケットの待合わせ、すなわちカラー情報お
よび先行情報が一致する異なる２つのデータパケットの
検出を行ない、当該カラー情報および先行情報が一致す
る２つのデータパケットのうち一方のデータパケットの
データフィールドに格納されたオペランドデータを他方
のデータパケットに付加（データフィールドを追加す
る）して出力するものである。演算処理手段３はデータ
対生成手段２から出力されるデータパケットに対して所
定の演算処理を施し、その結果を入力データパケットの
データフィールドに格納して上記プログラム記憶手段１
に出力するものである。なお、４および５はプログラム
記憶手段１とデータ対生成手段２とをつなぐデータ伝送
路である。６はデータ対生成手段２と演算処理手段３と
をつなぐデータ伝送路である。さらに、７は演算処理手
段３とプログラム記憶手段１とをつなぐデータ伝送路で
ある。

データパケットがプログラム記憶手段１→データ対生成
手段２→演算処理手段３→プログラム記憶手段１…とま
わり続けることにより、プログラム記憶手段１に記憶さ
れたデータフロープログラムに基づいて演算処理が進行
する。

また、第７図にプログラム記憶手段１における記憶内容
のフィールド構成の一部を示す。さらに、第８図にデー
タ対生成手段２の一例であるマッチングメモリのフィー
ルド構成を示す。

従来、この種の情報処理装置では、情報処理学会第34回
全国大会講演論文集2Q−７、249頁〜20頁（昭和62年）
に見られるように、データ対生成手段２としてマッチン
グメモリを使用してテンプレートマッチングを行なう場
合、マッチングメモリへのアクセスに対して第６図に示
すカラーフィールドの内容（第１のテンプレートパター
ン）および先行フィールドの内容（第２のテンプレート
パターン）にハッシュ演算を施して得られる値をアドレ
ス（これのハッシュアドレスという）として用いること
により、当該マッチングメモリの物理的アドレス空間の
有効利用が図られている。すなわち、上記第１のテンプ
レートパターンおよび第２のテンプレートパターンのそ
れぞれの全ビットを組合わせてアドレスを生成すると、
マッチングメモリのアドレス数が膨大なものとなり、装
置が大型かつ複雑なものとなってしまう。そこで、上記
第１のテンプルートパターンの一部と第２のテンプレー
トパターンの一部とを抜き出し組合わせてマッチングメ
モリのアドレスを生成すること（この特許では、これを
ハッシュ演算という）により、マッチングンメモリのア
ドレス数の低減を図っている。

［発明が解決しようとする課題］ ところで、上記のように複数のテンプレートパターンの
それぞれの一部の組合わせからなるパターンをマッチン
グンメモリのアドレスに対応させてテンプレートマッチ
ングを行なう従来の方式では、各テンプレートから抜き
出すビット数はそれぞれ固定的に定められていた。

しかしながら、各テンプレートパターンが必要とするア
ドレス数（ビット数に対応）はアプリケーションによっ
て固定的でなく、他方マッチングメモリのアドレスの総
数は容易に変えられないため、従来のテンプレートマッ
チング方式では同一のハッシュアドレスを有する異なる
複数のデータがアクセス競合（これをハッシュ衝突とい
う）を起こすことが多くなり、テンプレートマッチング
の効率が低下するという問題点があった。

この発明は、上記のような従来のものの問題点を解消す
るためになされたもので、アプリケーションの変更に対
しても柔軟に対応でき、常に効率の良いテンプレートマ
ッチングを行ない得るようなテンプレートマッチング用
アドレス生成装置を提供することを目的とする。

［課題を解決するための手段］ この発明に係るテンプレートマッチング用アドレス生成
装置は、複数のテンプレートパターンのそれぞれの一部
の組合わせからなるパターンをアドレスとしてマッチン
グメモリをアクセスしテンプレートマッチングを行なう
情報処理装置において、マッチングメモリのアドレスを
生成する際に外部から入力された制御データに基づいて
複数のテンプレートパターンの混合比率を変更するため
の手段を備えるようにしたものである。

［作用］ この発明においては、アプリケーションの変更に応じて
各テンプレートパターンの混合比率を変更することによ
り、アプリケーションごとに適切なテンプレートパター
ンとマッチングメモリのアドレスの割当てを柔軟に変更
することができ、テンプレートマッチングの効率を上げ
ることができる。

［実施例］ 第１図はこの発明の一実施例の構成を示す概略ブロック
図である。図において、この実施例では、Ｎビットを有
する第１のテンプレートパターン（たとえばカラー情
報）T1の下位n1ビットt1と、N2ビットを有する第２のテ
ンプレートパターン（たとえば先行情報）T2の下位n2ビ
ットt2とから記憶手段（マッチングメモリ）20のアドレ
スを生成する装置として構成されている。上記t1のうち
下位ｊビットt1bおよび上記t2のうち下位ｋビットt2bは
それぞれ記憶手段20に直接与えられる。また、t1のうち
上位ｍビットt1aおよびt2のうち上記ｍビットt2aはそれ
ぞれアドレス割当部10に与えられる。このアドレス割当
部10は、外部からの制御データ（たとえばアプリケーシ
ョンの変更に応じて切換えられる）30に応じて上記t1a
とt2aを組合わせ、ｍビットのアドレス信号t3を生成す
るものである。記憶手段20は、第１のテンプレートパタ
ーンT1からのアドレス信号t1bと第２のテンプレートパ
ターンT2からのアドレス信号t2bとアドレス割当部10か
らのアドレス信号t3とを組合わせて得られるアドレスデ
ータによってアクセスされる構成となっている。したが
って、記憶手段20は上記組合わせによって得られるアド
レスデータと１対１に対応するアドレスを有している。

なお、上記実施例において各テンプレートパターンおよ
び記憶手段20のアドレスデータのビット数は任意に設定
し得るが、以下にはt1a,t2aおよびt3がそれぞれ有する
ｍビットを３ビットとして上記実施例のさらに詳細な構
成を説明する。

第２図および第３図は、第１図に示すアドレス割当部10
の回路構成の一例を示す図である。まず、第２図に示す
ごとく、２ビットの制御データ30（A0,A1）は、NORゲー
ト11,インバータ12およびNANDゲート13によって３ビッ
トの制御データB0,B1,B2に変換される。なお、入力制御
データA0,A1と変換後の制御データB0,B1,B2との対応関
係を第４図に示しておく。

次に、第３図に示すごとく、クロックドゲート14a,14b,
14cには、それぞれ、第１図に示す第１のテンプレート
パターンT1のt1aから得られる３ビットのアドレス信号C
10,C11,C12が入力される。また、クロックドゲート15a,
15b,15cには、それぞれ、第１図に示す第２のテンプレ
ートパターンT2のt2aから得られるアドレス信号C20,C2
1,C22が入力される。第２図に示す回路によって得られ
た３ビットの制御データB0,B1,B2は、それぞれ、クロッ
クドゲート14a,14b,14cの各クロック端子にそのまま与
えられるとともに、クロックドゲート15a,15b,15cの各
クロック端子に反転して与えられる。クロックドゲート
14aおよび15aの出力、14bおよび15bの出力、14cおよび1
5cの出力は、それぞれ統合されて前記アドレス信号t3の
D0,D1,D2となる。

上記のような構成において、クロックドゲート14a,14b,
14cは、それぞれ、制御データB0,B1,B2がたとえばハイ
レベルのときにビット入力C10,C11,C12を通過させる。
一方、クロックドゲート15a,15b,15cは、それぞれ、制
御データB0,B1,B2がたとえばローレベルのときビット入
力C20,C21,C22を通過させる。したがって、制御データB
0,B1,B2とアドレス信号D0,D1,D2との関係は第４図に示
すごとくになる。すなわち、アドレス割当部10は、制御
データ30に応じて、アドレス信号C10,C11,C12およびア
ドレス信号C20,C21,C22を適当な比率で混合し、３ビッ
トのアドレス信号D0,D1,D2を作成する。これによって、
アプリケーションの変更に応じて第１のテンプレートパ
ターンT1と第２のテンプレートパターンT2とが記憶手段
20のアドレスに対して占める割合を変応することがで
き、常にアプリケーションに応じた適切なアドレスを生
成することができる。その結果、記憶手段20においてい
わゆるハッシュ衝突を起こす確立が少なくなり、テンプ
レートマッチングの効率を高めることができる。

［発明の効果］ 以上のように、この発明によれば、アプリケーションご
とに適切なテンプレートパターンとマッチングメモリの
アドレスの割当を柔軟に変更することができ、テンプレ
ートマッチングの効率を上げることができる。

【図面の簡単な説明】

第１図はこの発明の一実施例の構成を示す概略ブロック
図である。 第２図および第３図は第１図に示すアドレス割当部10の
構成の一例を示す回路図である。 第４図はアドレス割当部10に入力される２ビットの制御
データA0,A1と第２図に示す回路で作成される３ビット
の制御データB0,B1,B2との関係およびこれら制御データ
とアドレス割当部10から出力される３ビットのアドレス
信号D0,D1,D2との関係を示す図である。 第５図は従来のデータフロー型情報処理装置の一例の構
成を示すブロック図である。 第６図は第５図の従来装置におけるデータパケットのフ
ィールド構成を示す図である。 第７図は第５図の従来装置におけるプログラム記憶手段
の記憶内容のフィールド構成の一部を示す図である。 第８図は第５図の従来装置におけるデータ対生成手段の
マッチングメモリのフィールド構成を示す図である。 図において、１はプログラム記憶手段、２はデータ対生
成手段、３は演算処理手段、T1は第１のテンプレートパ
ターン、T2は第２のテンプレートパターン、10はアドレ
ス割当部、20は記憶手段、30は制御データを示す。

Claims (1)

【特許請求の範囲】
1. 【請求項１】複数のテンプレートパターンのそれぞれの
   一部の組合わせからなるパターンをアドレスとしてマッ
   チングメモリをアクセスしテンプレートマッチングを行
   なう情報処理装置において、 前記マッチングメモリのアドレスを生成する際に、外部
   から入力される制御データに基づいて、前記複数のテン
   プレートパターンの混合比率を変更するための手段を備
   える、テンプレートマッチング用アドレス生成装置。