JPH0535656A - データ検索方式 - Google Patents

Abstract

(57)【要約】 【目的】 ＤＭＡコントロ−ラを有する計算機システム
において、デ−タの検索時間を短縮するデータ検索方式
を提供する。 【構成】 計算機システムに、ＣＰＵＩ／Ｆ８、ＤＭＡ
Ｉ／Ｆ９、ＣＰＵＩ／Ｆ１０、検索デ−タレジスタ群１
１、コンパレ−タ群１２、ＦＩＦＯバッファ１３、ＡＮ
Ｄゲ−ト１４、一致アドレススタック制御部１５、検索
デ−タ数レジスタ１６、回数コンパレ−タ１７及び一致
アドレススタック１８から構成されるハードウエアを付
加し、ＣＰＵが検索デ−タ及び検索デ−タの要求回数を
検索デ−タ数レジスタ１６に設定し、ＤＭＡコントロー
ラが主記憶メモリ上の指定された領域のデ−タをＦＩＦ
Ｏバッファ１３に流し、検索デ−タレジスタ群１１とＦ
ＩＦＯバッファ１３のデ−タをコンパレ−タ群１２によ
り複数個のデ−タを同時比較し、検索デ−タと一致した
一連のデータのアドレスと個数を求める。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、ダイレクトメモリアク
セス（以下、「ＤＭＡ」と称する）コントロ−ラを有す
る計算機システムにおける主記憶メモリ上のデ−タ検索
方式に関するものである。

【０００２】

【従来技術】従来技術によるデ−タの検索手順を図３に
示す。従来計算機システムにおいて主記憶上の複数バイ
トにより構成されるデ−タ又は文字列を検索する場合プ
ログラムによって主記憶上のデ−タを１バイトずつリ−
ドし、検索したいデ−タを１バイトずつ順次比較するこ
とにより行っていた。図３は、上記のようなプログラム
によって、主記憶上のａ0番地からａ1番地の範囲でｎバ
イトよりなる検索デ−タ（Ｄ0、Ｄ1、Ｄ2．．．Ｄn-1）
をＭ個まで検索し、一致するデ−タを持つ主記憶内の先
頭番地をｓ0番地から始まる主記憶に格納する場合の動
作を示すフロ−チャ−トである。

【０００３】図中でＩＸ，ＩＹ、ＩＺ,ＩＺa は、計算
機内のＣＰＵのインデックスレジスタであり、それぞれ
次のような意味を持つ、ＩＸは現在検索中のアドレスを
示す。ＩＹはＩＸのアドレスで、デ−タの１バイト目Ｄ
0 が一致した場合、残りのＤ1〜Ｄn-1を比較するための
アドレスＩＸ＋１〜ＩＸ＋ｎ-1を示す。ＩＺは検索中の
結果、一致するデ−タを持つアドレスの先頭番地を格納
する主記憶上のアドレスを示す。ＩＺa は、検索結果一
致したデ−タの個数を表す。

【０００４】ｒ0 はＣＰＵの汎用レジスタであり、この
フロ−チャ−トの中では、現在Ｄ１〜 Ｄn-1 の何バイ
ト目を比較中であるかを示す。まずＩＸ，ＩＺ，ＩＺａ
の値を初期値ａ0,ｓ0，０に設定する（ステップＳＴ
１）。ステップＳＴ２〜ステップＳＴ４がこのプログラ
ムのメインル−プであり、ＩＸの値をインクリメントし
ながら検索デ−タの１バイト目Ｄ0と一致するかどうか
を調べる（ステップＳＴ２）。一致しなかった場合に
は、ＩＸをインクリメント（ステップＳＴ３）し、ＩＸ
がアドレスの終了値ａ1に達した時点で、このル−プは
終了する（ステップＳＴ４）。

【０００５】一致した場合には、更に１〜ｎ-1バイトの
内容を１バイトづつ読みだし比較する。ＩＹ，ｒ0 に初
期値を設定する（ステップＳＴ５）。ＩＹ，ｒ0 をイン
クリメントし（ステップＳＴ６）、１〜ｎ-1バイトの比
較が全て終了した場合（ステップＳＴ７）には、検索デ
−タが発見されたものとしてその時のＩＸの値をＩＺが
示す位置に格納し、ＩＺ，ＩＺａをインクリメントする
（ｂはｒ0 番目の１デ−タのビット数をバイト換算した
もの）（ステップＳＴ９）。ここでｒ0がｎ-1に達する
前に検索デ−タと異なるデ−タと現れた場合には、この
ル−プから抜けてステップＳＴ２〜ステップＳＴ４のメ
インル−プにもどる（ステップＳＴ８）。

【０００６】ここで、ＩＺa の値が設定値Ｍより大であ
れば、検索を中断し（ステップＳＴ１０）Ｍ以下であれ
ば、更に次のアドレスの検索に移る（ステップＳＴ１
１）。以上のようにして、ａ0〜ａ1 の範囲の検索が終
了するか、又はＭ個のデ−タ一致が発見されることによ
って、このフロ−は終了する。ここでＩＺa は発見され
た一致デ−タの個数であり（ｓ０）〜（ｓ0＋ＩＺａ−
１）番地にそのデ−タの先頭番地が格納される。

【０００７】

【発明が解決しようとする課題】しかしながら、以上述
べた方法での主記憶へのアクセス回数ａｃは式（１）で
表されるような値となり、理論上の最小値であるａ1−
ａ0＋１回以上となる。 ａｃ＝（ａ1−ａ0＋１）・（１＋ｈｒ・ｎｒ）．．．．．（１） ａｃ：主記憶アクセス回数 ａ1−ａ0：検索される主記憶の範囲のアドレス。 ｈｒ：０バイト目が一致するが１〜ｎのどれかで不一致
となる確率。 ｎｒ：ｈｒの場合に不一致となる位置の平均（１≦ｎｒ
＜ｎ） また、プログラムによる方式の為、ＣＰＵは、検索の為
の主記憶アクセス以外にプログラムのコ−ドのフェッチ
等を行うため、時間がかかる。しかも検索中に他の処理
を行うことが出来ないという問題点があった。

【０００８】本発明は上述の点に鑑みてなされたもの
で、上記問題点を解決しデ−タ検索時の主記憶のアクセ
ス回数の増加を防ぐため、ＤＭＡ機能とファーストイン
ファーストアウト（以下「ＦＩＦＯ」と称する）バッフ
ァと複数バイトのコンパレ−タの組合せによるハ−ドウ
ェアを設けることによって、主記憶のアクセス回数を最
小限にし、デ−タ検索を高速に行えるようにすることを
目的とする。

【０００９】

【課題を解決するための手段】上記課題を解決するため
本発明は、図１に示すようにＤＭＡコントローラを有す
る計算機システムにおいて、検索デ−タを設定する検索
デ−タレジスタ群、主記憶より対象とする一連のデ−タ
を読みだし格納するＦＩＦＯバッファ、その両者のデ−
タを同時に比較するコンパレ−タ群、一致回数及び一致
アドレスを求める一致アドレススタック制御部、一致ア
ドレスを格納する一致アドレススタック、検索デ−タの
要求回数を設定する検索デ−タ数レジスタ、回数コンパ
レ−タより構成されるハ−ドウェアを設け、複数バイト
からなるデ−タを検索する場合に、ＤＭＡアクセスによ
って主記憶よりデ−タを引き出し、そのデ−タをＦＩＦ
Ｏバッファ内に格納し、ＦＩＦＯバッファ内の複数バイ
トのデ−タを検索デ−タと同時に比較する機能を設けた
ものである。

【００１０】

【作用】本発明では、複数バイトのデ−タの比較をハ−
ドウェアによって同時に行えるようにしたため、図３の
フロ−チャ−トのステップＳＴ５〜ステップＳＴ８のル
−プが無用となり、従来のプログラム方式によるメモリ
アクセス回数（ａ1−ａ0＋１）（１＋ｈｒ・ｎｒ）をａ
0−ａ1＋１に減少させることが出来る。また、ＤＭＡコ
ントロ−ラによってデ−タをアクセスするため、ＣＰＵ
に時間的な余裕が出来る。

【００１１】

【実施例】以下本発明の一実施例を図面に基づいて詳細
に説明する。図２は本発明データ検索方式を適用する計
算機システムの構成を示すブロック図である。図示する
ように本計算機システムは、ＣＰＵ１、ＤＭＡコントロ
−ラ２、主記憶装置３及び本発明により付加された付加
ハ−ドウェア４を具備する。アドレスバス５、デ−タバ
ス６、ＤＭＡＩ／Ｆ信号７、ＣＰＵＩ／Ｆ信号８、ＤＭ
ＡＣＩ／Ｆ信号９ａで結ばれている。

【００１２】デ−タ検索は、ＣＰＵ１がＣＰＵＩ／Ｆ信
号８によって本発明により付加した付加ハ−ドウェア４
に検索するデ−タ、最大検索デ−タ数を設定し、ＤＭＡ
ＣＩ／Ｆ信号９ａによってＤＭＡコントロ−ラ２に検索
するアドレス範囲を設定し、ＣＰＵＩ／Ｆ信号８によっ
て付加ハ−ドウェア４を起動することによって行われ
る。起動した付加ハ−ドウェア４はＤＭＡＩ／Ｆ信号７
によってＤＭＡコントロ−ラ２にデ−タを要求する。Ｄ
ＭＡコントロ−ラ２はアドレスバス５によって主記憶装
置３にアドレスを与え、主記憶装置３がそのアドレスに
応じたデ−タの値を出すとＤＭＡＩ／Ｆ信号７によって
付加ハ−ドウェア４にデ−タが出ていることを伝える。

【００１３】付加ハ−ドウェア４は主記憶装置３からの
デ−タの値を取り込んで、検索デ−タとの比較を行い一
致したときのアドレスバス５上のアドレスを内部に蓄え
る。検索が終了すると付加ハ−ドウェア４からＣＰＵＩ
／Ｆ信号８によってＣＰＵ１に通知される。検索結果
は、付加ハ−ドウェア４の内部に蓄えられたアドレスの
値をアドレスバス５を通してリ−ドすることによってＣ
ＰＵ１に与えられる。

【００１４】図１は、図２の本発明の付加ハ−ドウェア
４の内部構造を示すブロック図である。付加ハ−ドウェ
ア４は、ＤＭＡＩ／Ｆ９、ＣＰＵＩ／Ｆ１０、検索デ−
タレジスタ群１１、コンパレ−タ群１２、ＦＩＦＯバッ
ファ１３、コンパレ−タ群１２の全出力のＡＮＤゲ−ト
１４、一致アドレススタック１８の制御部で一致アドレ
ススタック制御部１５、検索デ−タ数レジスタ１６、回
数コンパレ−タ１７で構成される。

【００１５】ＣＰＵからの設定は、ＣＰＵＩ／Ｆ１０に
よって検索デ−タレジスタ群１１、検索デ−タ数レジス
タ１６に対して行われる。検索デ−タレジスタ群１１に
は検索されるデ−タが記憶される。検索デ−タレジスタ
群１１は検索デ−タ１９と有効ビット２０からなる複数
のレジスタから構成される。有効ビット２０が設定され
ていない検索デ−タは、比較の対象にしない。従って途
中で比較の対象としない文字を含んだ任意長の文字列の
検索が可能である。起動するとＤＭＡＩ／Ｆ９によって
ＤＭＡ要求応答の制御が行われ、メモリからのデ−タが
ＦＩＦＯバッファ１３に蓄積される。ＦＩＦＯバッファ
１３はＦＩＦＯとして動作し、デ−タは矢印のように上
から下へ流れる。下からはみ出したデ−タは読み捨てら
れる。ＦＩＦＯバッファ１３内のデ−タは、デ−タが一
個読まれる毎に検索デ−タレジスタ群１１内の有効ビッ
ト２０がセットされた検索デ−タ１９と、コンパレ−タ
群１２によって比較される。この比較は、ＦＩＦＯバッ
ファ１３内の全デ−タに対して同時に行われる。

【００１６】コンパレ−タ群１２の出力はＡＮＤゲ−ト
１４にとおってＡＮＤをとられ、全デ−タが一致した場
合は一致アドレススタック制御部１５に伝えられる。一
致アドレススタック制御部１５内には全デ−タの一致回
数を示すレジスタがありＡＮＤゲ−ト１４による信号に
応じて、そのレジスタの値に応じた一致アドレススタッ
ク１８内の位置にその時のアドレスバス上にあるアドレ
ス値（最終デ−タの番地）が記録される。レジスタの値
は、回数コンパレ−タ１７によって検索デ−タ数レジス
タ１６と比較され、一致するか又は一致アドレススタッ
ク１８が全部使用された場合に検索は終了となる。どち
らでもない場合にはＤＭＡコントロ−ラの停止によって
終了となる。

【００１７】図４に、この方式による検索をプログラム
によって行ったとした場合のフロ−チャ−トを示す。図
４から分かるように複数デ−タの比較がステップＳＴ２
２の１ステップで行われるため従来方式の図３に比べて
単純なル−プによって高速な検索が行われる。図３のフ
ロ−チャ−トのル−プＳＴ２，ＳＴ５，ＳＴ６，ＳＴ
７，ＳＴ８の各ステップをハ−ドウェアで同時に行うよ
うにしたもので、ここで分かるようにメモリアクセス回
数は最小限のａ1 −ａ0 ＋１回となる。なお当然ながら
プログラムによる方式では、複数デ−タの同時比較が出
来ないため、このフロ−を実現するにはハ−ドウェアが
必要となる。

【００１８】

【発明の効果】以上、詳細に説明したように本発明によ
れば、下記のような効果が期待される。（１）複数バイ
トのデ−タの比較をハ−ドウェアによって同時に行える
ようにした為、従来のプログラム方式によるメモリアク
セス回数を減少｛（ａ1 −ａ0＋１）（１＋ｈｒ・ｎ
ｒ）から（ａ1−a0＋１）｝回に減少させることが出来
る。

【００１９】（２）また、ＤＭＡ機能を利用しているた
め、ＣＰＵがプログラムの命令コ−ドのフェッチ等にか
かる時間も不要となり、デ−タ検索中にＣＰＵが別の処
理を行うことが出来るという利点がある。

【図面の簡単な説明】

【図１】本発明による付加ハ−ドウェアブロク図であ
る。

【図２】本発明によるシステムブロック図である。

【図３】従来技術のプログラムによるデ−タ検索のフロ
−チャ−トである。

【図４】本発明の方式をプログラムに置き換えた場合の
フロ−チャ−トである。

【符号の説明】

１ ＣＰＵ ２ ＤＭＡコントロ−ラ ３ 主記憶装置 ４ 付加ハ−ドウェア ５ アドレスバス ６ デ−タバス ７ ＤＭＡＩ／Ｆ信号 ８ ＣＰＵＩ／Ｆ ９ ＤＭＡＩ／Ｆ ９ａ ＤＭＡＩ／Ｆ信号 １０ ＣＰＵＩ／Ｆ １１ 検索デ−タレジスタ群 １２ コンパレ−タ群 １３ ＦＩＦＯバッファ １４ ＡＮＤゲ−ト １５ 一致アドレススタック制御部 １６ 検索デ−タ数レジスタ １７ 回数コンパレ−タ １８ 一致アドレススタック １９ 検索デ−タ ２０ 有効ビット

Claims (1)

1. 【特許請求の範囲】 【請求項１】 ＣＰＵ、ダイレクトメモリアクセス（Ｄ
   ＭＡ）コントロ−ラ及び主記憶メモリを有する計算機シ
   ステムのデ−タ検索方式において、 検索デ−タを設定する検索デ−タレジスタ群、前記主記
   憶メモリより対象とする一連のデ−タを読みだし、格納
   するファーストインファーストアウト（ＦＩＦＯ）バッ
   ファ、この両者のデ−タを同時に比較するコンパレ−タ
   群、一致回数及び一致アドレスを求める一致アドレスス
   タック制御部、一致アドレスを格納する一致アドレスス
   タック、検索デ−タの要求回数を設定する検索デ−タ数
   レジスタ、一致回数を比較する回数コンパレ−タより構
   成されるハードウェアを設け、 前記ＣＰＵが検索デ−タ及び検索デ−タの要求回数を設
   定し、前記ＤＭＡコントローラが前記主記憶メモリ上の
   指定された領域のデ−タを前記ＦＩＦＯバッファに流
   し、前記検索デ−タレジスタ群と前記ＦＩＦＯバッファ
   のデ−タを前記コンパレ−タ群により複数個のデ−タを
   同時比較し、前記検索デ−タと一致した一連のデ−タの
   アドレスと個数を求めることを特徴とするデ−タ検索方
   式。