JP2976418B2 - パターンマッチング処理装置 - Google Patents
パターンマッチング処理装置Info
- Publication number
- JP2976418B2 JP2976418B2 JP4308175A JP30817592A JP2976418B2 JP 2976418 B2 JP2976418 B2 JP 2976418B2 JP 4308175 A JP4308175 A JP 4308175A JP 30817592 A JP30817592 A JP 30817592A JP 2976418 B2 JP2976418 B2 JP 2976418B2
- Authority
- JP
- Japan
- Prior art keywords
- pattern matching
- ram
- memory cell
- cell array
- port
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
- 230000006870 function Effects 0.000 claims description 4
- 238000000034 method Methods 0.000 description 7
- 238000010586 diagram Methods 0.000 description 6
- 238000006243 chemical reaction Methods 0.000 description 3
- 230000000694 effects Effects 0.000 description 2
- 101100325756 Arabidopsis thaliana BAM5 gene Proteins 0.000 description 1
- 101150046378 RAM1 gene Proteins 0.000 description 1
- 101100476489 Rattus norvegicus Slc20a2 gene Proteins 0.000 description 1
- 230000004044 response Effects 0.000 description 1
Landscapes
- Image Input (AREA)
Description
【０００１】
【産業上の利用分野】本発明はパターンマッチング処理
装置に関し、特にパターンマッチング演算機能を有する
Ｖ−ＲＡＭ（ビデオＲＡＭ）装置を用いたパターンマッ
チング処理システムに関するものである。
装置に関し、特にパターンマッチング演算機能を有する
Ｖ−ＲＡＭ（ビデオＲＡＭ）装置を用いたパターンマッ
チング処理システムに関するものである。
【０００２】
【従来の技術】二つのデータのターンマッチング処理を
行う場合、１回のパターンマッチング可能なデー処理量
は高々３２ビット程度であり、この処理をパーソナルコ
ンピータ等のＣＰＵによるソフトウェアにより行うにし
ても、またハードウェア的に行うにしても、やはり処理
ビット数は３２ビット程度の単位で行われる。
行う場合、１回のパターンマッチング可能なデー処理量
は高々３２ビット程度であり、この処理をパーソナルコ
ンピータ等のＣＰＵによるソフトウェアにより行うにし
ても、またハードウェア的に行うにしても、やはり処理
ビット数は３２ビット程度の単位で行われる。
【０００３】
【発明が解決しようとする課題】この様に、従来のパタ
ーンマッチング処理システムでは、一度に処理できるビ
ット量が高々３２ビット程度であるために、多量のデー
タのパターンマッチング処理を行うには、極めて多くの
時間を必要とするという欠点がある。また処理ビット数
を増大すると、回路規模がそれに比例して増大し、ハー
ドウェア的に得策とはならず非実用的であるという欠点
がある。
ーンマッチング処理システムでは、一度に処理できるビ
ット量が高々３２ビット程度であるために、多量のデー
タのパターンマッチング処理を行うには、極めて多くの
時間を必要とするという欠点がある。また処理ビット数
を増大すると、回路規模がそれに比例して増大し、ハー
ドウェア的に得策とはならず非実用的であるという欠点
がある。
【０００４】
【０００５】本発明の目的は、多量のデータの演算を高
速に内部で処理できるＶ−ＲＡＭ装置を使用してパター
ンマッチング処理を一度に多量にかつ高速に行い得るパ
ターンマッチング処理装置を提供することである。
速に内部で処理できるＶ−ＲＡＭ装置を使用してパター
ンマッチング処理を一度に多量にかつ高速に行い得るパ
ターンマッチング処理装置を提供することである。
【０００６】
【０００７】本発明によるパターンマッチング処理装置
は、メモリセルアレイと、前記メモリセルアレイのデー
タの入出力を行うためのレジスタからなる複数個のポー
ト部と、前記ポート部をポート選択指令に応じて択一的
に選択するセレクタと、パターンマッチング演算機能を
有する演算回路と、前記メモリセルアレイ，前記ポート
部，前記演算回路の相互間のデータの授受を外部入出力
選択指令に応じて制御するトランスファゲートとを有
し、前記メモリセルアレイからの第１及び第２の読出し
データを夫々別々のポート部に格納し、このポート部に
格納された第１及び第２の読出しデータを前記演算回路
へ入力してパターンマッチング演算を行い、このパター
ンマッチング演算結果データを前記ポート部１つを介し
て外部へ導出するように構成したＶ−ＲＡＭ装置と、前
記パターンマッチング結果データのマッチング状態を計
数するカウンタ手段と、前記Ｖ−ＲＡＭ装置の演算動作
を制御しつつ前記カウンタ手段によるマッチング状態を
前記Ｖ−ＲＡＭ装置のメモリセルアレイの所定アドレス
へ格納するよう制御する制御手段と、を含むことを特徴
とする。
は、メモリセルアレイと、前記メモリセルアレイのデー
タの入出力を行うためのレジスタからなる複数個のポー
ト部と、前記ポート部をポート選択指令に応じて択一的
に選択するセレクタと、パターンマッチング演算機能を
有する演算回路と、前記メモリセルアレイ，前記ポート
部，前記演算回路の相互間のデータの授受を外部入出力
選択指令に応じて制御するトランスファゲートとを有
し、前記メモリセルアレイからの第１及び第２の読出し
データを夫々別々のポート部に格納し、このポート部に
格納された第１及び第２の読出しデータを前記演算回路
へ入力してパターンマッチング演算を行い、このパター
ンマッチング演算結果データを前記ポート部１つを介し
て外部へ導出するように構成したＶ−ＲＡＭ装置と、前
記パターンマッチング結果データのマッチング状態を計
数するカウンタ手段と、前記Ｖ−ＲＡＭ装置の演算動作
を制御しつつ前記カウンタ手段によるマッチング状態を
前記Ｖ−ＲＡＭ装置のメモリセルアレイの所定アドレス
へ格納するよう制御する制御手段と、を含むことを特徴
とする。
【０００８】
【実施例】以下、本発明の実施例を図面を用いて説明す
る。
る。
【０００９】図１は本発明の実施例によるＶ−ＲＡＭ装
置のブロック図である。メモリセルアレイ１はＶ−ＲＡ
Ｍ装置の基本メモリであり、本例では、４０９６×４０
９６ビットのＲＡＭを用いるものとする。このＲＡＭ１
のアドレス指定はローデコーダ２及びカラムデコーダ３
により行われるようになっている。
置のブロック図である。メモリセルアレイ１はＶ−ＲＡ
Ｍ装置の基本メモリであり、本例では、４０９６×４０
９６ビットのＲＡＭを用いるものとする。このＲＡＭ１
のアドレス指定はローデコーダ２及びカラムデコーダ３
により行われるようになっている。
【００１０】このＶ−ＲＡＭ装置には、ＲＡＭ１の他に
演算回路４が設けられており、４０９６ビットの並列演
算が高速に行われ得るものである。この演算回路４の演
算機能は図２に示すものがあり、図２において、Ｓ１，
Ｓ２は演算すべき各入力ビットの組を示し、外部の４ビ
ット（０〜３）の演算セレクト信号に応じて１６項目
（Ｎｏ．０〜Ｎｏ．１５）のデスティネーション論理出
力を高速に生成する。その他に、ビットシフト機能を有
しており、シフト量及びシフト方向が指定可能である。
演算回路４が設けられており、４０９６ビットの並列演
算が高速に行われ得るものである。この演算回路４の演
算機能は図２に示すものがあり、図２において、Ｓ１，
Ｓ２は演算すべき各入力ビットの組を示し、外部の４ビ
ット（０〜３）の演算セレクト信号に応じて１６項目
（Ｎｏ．０〜Ｎｏ．１５）のデスティネーション論理出
力を高速に生成する。その他に、ビットシフト機能を有
しており、シフト量及びシフト方向が指定可能である。
【００１１】更に、ＲＡＭ１のための入出力ポート６Ａ
〜６Ｄの４個のポート部が設けられており、これ等ポー
ト部６Ａ〜６Ｄは４０９６ビットの幅を有するシリアル
レジスタ構成となっている。
〜６Ｄの４個のポート部が設けられており、これ等ポー
ト部６Ａ〜６Ｄは４０９６ビットの幅を有するシリアル
レジスタ構成となっている。
【００１２】これ等ＲＡＭ１，演算回路４，ポート部６
Ａ〜６Ｄの間にはトランスファゲート５が設けられてお
り、このトランスファゲート５によりＲＡＭ１，演算回
路４，ポート部６Ａ〜６Ｄの間の入出力関係が選択制御
される。
Ａ〜６Ｄの間にはトランスファゲート５が設けられてお
り、このトランスファゲート５によりＲＡＭ１，演算回
路４，ポート部６Ａ〜６Ｄの間の入出力関係が選択制御
される。
【００１３】４個のポート部６Ａ〜６Ｄの一つを選択す
るために、外部からポートセレクト信号が供給されてお
り、このポートセレクト信号に応じてトランスファゲー
ト５との接続関係が択一的に決定され、またこれ等ポー
ト部６Ａ〜６Ｄのいずれの出力を演算回路４への入力と
するかが、ポートセレクト信号に応じて動作するセレク
タ７にて決定される。
るために、外部からポートセレクト信号が供給されてお
り、このポートセレクト信号に応じてトランスファゲー
ト５との接続関係が択一的に決定され、またこれ等ポー
ト部６Ａ〜６Ｄのいずれの出力を演算回路４への入力と
するかが、ポートセレクト信号に応じて動作するセレク
タ７にて決定される。
【００１４】かかる構成のＶ−ＲＡＭ装置を用いたパタ
ーンマッチング処理システムの例を図３のブロック図を
参照しつつ説明する。Ｖ−ＲＡＭ１０が図１に示したＶ
−ＲＡＭ装置であり、ＣＰＵ１１はパターンマッチング
処理全体の制御を行うものであり、このＣＰＵ１１の制
御下において、パターンマッチングコントローラ１３が
実際にＶ−ＲＡＭ１０の動作をコントロールする。
ーンマッチング処理システムの例を図３のブロック図を
参照しつつ説明する。Ｖ−ＲＡＭ１０が図１に示したＶ
−ＲＡＭ装置であり、ＣＰＵ１１はパターンマッチング
処理全体の制御を行うものであり、このＣＰＵ１１の制
御下において、パターンマッチングコントローラ１３が
実際にＶ−ＲＡＭ１０の動作をコントロールする。
【００１５】直並列変換回路１２はクロックに応答して
Ｖ−ＲＡＭ１０のポート６（図１のポート部６Ａ〜６Ｄ
の１つ）の出力を直並列変換して、カウンタ１４へ供給
する。このカウンタ１４は入力データのビット“１”の
合計をカウントするものであり、このカウント結果がパ
ターンマッチングの整合の度合いを示すものとなり、デ
ータバス１５を介してこのカウント結果（マッチング結
果）がＶ−ＲＡＭ１０内の所定領域へ格納される。尚、
１６はアドレスバスである。
Ｖ−ＲＡＭ１０のポート６（図１のポート部６Ａ〜６Ｄ
の１つ）の出力を直並列変換して、カウンタ１４へ供給
する。このカウンタ１４は入力データのビット“１”の
合計をカウントするものであり、このカウント結果がパ
ターンマッチングの整合の度合いを示すものとなり、デ
ータバス１５を介してこのカウント結果（マッチング結
果）がＶ−ＲＡＭ１０内の所定領域へ格納される。尚、
１６はアドレスバスである。
【００１６】図４はＶ−ＲＡＭ１０内のメモリマップの
例を示しており、パターンマッチングすべき入力デー
タ，辞書データ（＃１〜＃ｎ）及びマッチング結果（＃
１〜＃ｎ）が夫々格納され、若しくは格納可能となって
いる。
例を示しており、パターンマッチングすべき入力デー
タ，辞書データ（＃１〜＃ｎ）及びマッチング結果（＃
１〜＃ｎ）が夫々格納され、若しくは格納可能となって
いる。
【００１７】パターンマッチング処理としては、先ず入
力データが読出されてＶ−ＲＡＭ１０内のポートの１つ
であるポート部６Ａへ転送され保持される。次に、パタ
ーンマッチングコントローラ１３に対して、Ｖ−ＲＡＭ
１０内の辞書デー＃１〜＃ｎのマッチングを行うよう指
令が出されると、マッチングコントローラ１３はＶ−Ｒ
ＡＭ１０内の辞書データ＃１をポートの１つであるポー
ト部６Ｂへ転送する。
力データが読出されてＶ−ＲＡＭ１０内のポートの１つ
であるポート部６Ａへ転送され保持される。次に、パタ
ーンマッチングコントローラ１３に対して、Ｖ−ＲＡＭ
１０内の辞書デー＃１〜＃ｎのマッチングを行うよう指
令が出されると、マッチングコントローラ１３はＶ−Ｒ
ＡＭ１０内の辞書データ＃１をポートの１つであるポー
ト部６Ｂへ転送する。
【００１８】演算回路４はポート部６Ａと６Ｂとのデー
タを入力Ｓ１，Ｓ２としてパターンマッチング演算を行
う。このパターンマッチング演算の種類はパターンマッ
チングコントローラ１３の指示により決定される。この
とき、演算回路４は４０９６ビットの演算を一度に実施
することができ、高速処理される。
タを入力Ｓ１，Ｓ２としてパターンマッチング演算を行
う。このパターンマッチング演算の種類はパターンマッ
チングコントローラ１３の指示により決定される。この
とき、演算回路４は４０９６ビットの演算を一度に実施
することができ、高速処理される。
【００１９】パターンマッチング後は、そのマッチング
結果データがポート部６Ａを介して直並列変換部１２へ
入力され、クロックに同期しつつ直列データとしてカウ
ンタ１４へ供給されることになる。このカウンタ１４は
パターンマッチングの度合を計数するものであり、ビッ
ト“１”の数をカウントし、その結果がＶ−ＲＡＭ１０
内のマッチング結果＃１へ格納される。
結果データがポート部６Ａを介して直並列変換部１２へ
入力され、クロックに同期しつつ直列データとしてカウ
ンタ１４へ供給されることになる。このカウンタ１４は
パターンマッチングの度合を計数するものであり、ビッ
ト“１”の数をカウントし、その結果がＶ−ＲＡＭ１０
内のマッチング結果＃１へ格納される。
【００２０】以上の動作が順次辞書データ＃２〜＃ｎに
ついても行われ、全ての処理が終了した時点で、Ｖ−Ｒ
ＡＭ１０内に格納されたマッチング結果＃１〜＃ｎをソ
ートすれば、辞書＃１〜＃ｎのパターンマッチング処理
が全て終了することになる。
ついても行われ、全ての処理が終了した時点で、Ｖ−Ｒ
ＡＭ１０内に格納されたマッチング結果＃１〜＃ｎをソ
ートすれば、辞書＃１〜＃ｎのパターンマッチング処理
が全て終了することになる。
【００２１】尚、上記実施例では、一度にマッチング処
理可能なビット数を４０９６としているが、これに限定
されるものではない。またポート部の数も２個以上複数
あれば良い。
理可能なビット数を４０９６としているが、これに限定
されるものではない。またポート部の数も２個以上複数
あれば良い。
【００２２】
【発明の効果】叙上の如く、本発明によれば、Ｖ−ＲＡ
Ｍ内部に多ビットの演算回路，転送回路（トランスファ
ゲート）及びこの演算結果等を一時格納するための複数
のポート部を設けているので、Ｖ−ＲＡＭ内部において
一度に多ビットの演算を高速に実行できるという効果が
ある。
Ｍ内部に多ビットの演算回路，転送回路（トランスファ
ゲート）及びこの演算結果等を一時格納するための複数
のポート部を設けているので、Ｖ−ＲＡＭ内部において
一度に多ビットの演算を高速に実行できるという効果が
ある。
【００２３】特に、パターンマッチング処理の様に多量
のデータを高速処理する必要があるときに、特に有効と
なり、一つのＩＣに組込まれたＶ−ＲＡＭ内部でのみ、
多量のデータが授受されて、ＩＣ間の転送が不要とな
り、高速性が著しく向上すると共に、回路規模も縮小す
るという効果がある。
のデータを高速処理する必要があるときに、特に有効と
なり、一つのＩＣに組込まれたＶ−ＲＡＭ内部でのみ、
多量のデータが授受されて、ＩＣ間の転送が不要とな
り、高速性が著しく向上すると共に、回路規模も縮小す
るという効果がある。
【図１】本発明の実施例のＶ−ＲＡＭ装置のブロック図
である。
である。
【図２】図１の演算回路の演算の種類を示す図である。
【図３】本発明の実施例のパターンマッチング処理シス
テムを示すブロック図である。
テムを示すブロック図である。
【図４】Ｖ−ＲＡＭ内のメモリマップの例を示す図であ
る。
る。
１ メモリセルアレイ（ＲＡＭ） ２ ローデコーダ ３ カラムデコーダ ４ 演算回路 ５ トランスファゲート ６Ａ〜６Ｄ ポート部 ７ セレクタ １０ Ｖ−ＲＡＭ １１ ＣＰＵ １２ 直並列変換回路 １３ パターンマッチングコントローラ １４ カウンタ
Claims (1)
- 【請求項１】 メモリセルアレイと、前記メモリセルア
レイのデータの入出力を行うためのレジスタからなる複
数個のポート部と、前記ポート部をポート選択指令に応
じて択一的に選択するセレクタと、パターンマッチング
演算機能を有する演算回路と、前記メモリセルアレイ，
前記ポート部，前記演算回路の相互間のデータの授受を
外部入出力選択指令に応じて制御するトランスファゲー
トとを有し、前記メモリセルアレイからの第１及び第２
の読出しデータを夫々別々のポート部に格納し、このポ
ート部に格納された第１及び第２の読出しデータを前記
演算回路へ入力してパターンマッチング演算を行い、こ
のパターンマッチング演算結果データを前記ポート部の
１つを介して外部へ導出するように構成したＶ−ＲＡＭ
装置と、 前記パターンマッチング結果データのマッチング状態を
計数するカウンタ手段と、 前記Ｖ−ＲＡＭ装置の演算動作を制御しつつ前記カウン
タ手段によるマッチング状態を前記Ｖ−ＲＡＭ装置のメ
モリセルアレイの所定アドレスへ格納するよう制御する
制御手段と、 を含むことを特徴とするパターンマッチング処理装置。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4308175A JP2976418B2 (ja) | 1992-10-22 | 1992-10-22 | パターンマッチング処理装置 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4308175A JP2976418B2 (ja) | 1992-10-22 | 1992-10-22 | パターンマッチング処理装置 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH06131448A JPH06131448A (ja) | 1994-05-13 |
| JP2976418B2 true JP2976418B2 (ja) | 1999-11-10 |
Family
ID=17977813
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4308175A Expired - Fee Related JP2976418B2 (ja) | 1992-10-22 | 1992-10-22 | パターンマッチング処理装置 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP2976418B2 (ja) |
Families Citing this family (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| AU2002219838A1 (en) | 2000-11-14 | 2002-05-27 | Coltec Industrial Products Inc | Abrasion-resistant polytetrafluoroethylene tape |
-
1992
- 1992-10-22 JP JP4308175A patent/JP2976418B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH06131448A (ja) | 1994-05-13 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| KR0125623B1 (ko) | 데이타 프로세서 및 데이타 처리방법 | |
| US4490786A (en) | Vector processing unit | |
| JPH0255878B2 (ja) | ||
| JP2947664B2 (ja) | 画像専用半導体記憶装置 | |
| EP1314099B1 (en) | Method and apparatus for connecting a massively parallel processor array to a memory array in a bit serial manner | |
| JP2976418B2 (ja) | パターンマッチング処理装置 | |
| US5603046A (en) | Method for complex data movement in a multi-processor data processing system | |
| JP2002269067A (ja) | 行列演算装置 | |
| JP2514473B2 (ja) | 並列処理装置 | |
| JPH1063647A (ja) | 行列演算装置 | |
| JP2538388B2 (ja) | パタ―ン変換装置 | |
| US5548771A (en) | Multi-processor data processing system having multiple ports coupled to multiple interface circuits | |
| JP2512994B2 (ja) | ベクトルレジスタ | |
| JPH09101889A (ja) | パイプライン演算装置 | |
| JP3039043B2 (ja) | 並列プロセッサ | |
| JP3050321B2 (ja) | マルチポートメモリ | |
| JP2553630B2 (ja) | データ処理装置 | |
| JPH08212168A (ja) | アレイプロセッサ | |
| JPH03196257A (ja) | ベクトル処理装置 | |
| JPH02204861A (ja) | ベクトルデータ処理装置 | |
| JPH05165875A (ja) | ベクトル演算処理装置 | |
| JPS6136866A (ja) | メモリ装置 | |
| JPH0668055A (ja) | ディジタル信号処理装置 | |
| JPH064689A (ja) | リニアアレイ型の並列ｄｓｐプロセッサ | |
| JPH06208454A (ja) | ビット操作回路 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080910 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080910 Year of fee payment: 9 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090910 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090910 Year of fee payment: 10 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100910 Year of fee payment: 11 |
|
| LAPS | Cancellation because of no payment of annual fees |