(57)【要約】データバンクに格納されているデータを探索するための規則がレジスタ（２）内に記憶されているように、及びこれらの規則がほぼ同時に処理可能であるように、少なくとも２つのレジスタ（２）を有するチップ（１）を備えたデータを処理するための回路が、データバンクの探索の最適化を考慮して時間的に構成されている。
2004533033.tif 000002
【特許請求の範囲】
【請求項１】
少なくとも２つのレジスタ（２）を有するチップ（１）を備えたデータを処理する回路において、
データバンクに格納されたデータを探索するための規則がレジスタ（２）内に記憶されていること、及び、これらの規則は、ほぼ同時に処理可能であることを特徴とする回路。
【請求項２】
規則は、１サイクル又は多数のサイクル内に処理可能であることを特徴とする請求項１に記載の回路。
【請求項３】
規則は、論理式及び／又は範囲の定義及び／又はワイルドカードを有することを特徴とする請求項１又は２に記載の回路。
【請求項４】
論理式は、ＯＲ結合及び／又はＡＮＤ結合及び／又はＮＯＴ結合を有する請求項３に記載の回路。
【請求項５】
データバンクを探索するための規則は、レジスト（２）内に記憶されていることを特徴とする請求項１〜４のいずれか１項に記載の回路。
【請求項６】
データバンクのデータは、データ記憶器（３）内に記憶されていることを特徴とする請求項１〜５のいずれか１項に記載の回路。
【請求項７】
データ記憶器（３）は、ＲＡＭ又はＦＩＦＯとして構成されていることを特徴とする請求項６に記載の回路。
【請求項８】
少なくとも１つのデータ記憶器（４）が、チップ（１）上に配置されていることを特徴とする請求項１〜７のいずれか１項に記載の回路。
【請求項９】
データバンクのデータが、特にデータ記憶器（３）から１つ又は複数のデータレジスタ（４）内に移動可能であることを特徴とする請求項８に記載の回路。
【請求項１０】
データレジスタ（４）の数は、データバンクを探索するための規則が記憶されているレジスタ（２）の数に等しいことを特徴とする請求項８又は９に記載の回路。
【請求項１１】
データは、少なくとも１つのエンコーダ（５）によって符号化可能であることを特徴とする請求項１〜１０のいずれか１項に記載の回路。
【請求項１２】
データは、１つ又は複数のエンコーダ（５）によってｎビットの符号に符号化可能であることを特徴とする請求項１１に記載の回路。
【請求項１３】
規則は、レジスタ（２）内で１つ又は多数の比較器（６）によって１つ又は複数のデータ（４）からのデータと比較可能であることを特徴とする請求項８〜１２のいずれか１項に記載の回路。
【請求項１４】
１つのレジスタ（２），１つのデータレジスタ（４），場合によっては１つのエンコーダ（５）及び１つの比較器（６）が、１つの個別符号要素（１４，１４′）に統合されている請求項８〜１３のいずれか１項に記載の回路。
【請求項１５】
多数の個別符号要素（１４，１４′）が、並列に接続されて及び／又は互いに平行にチップ（１）上に配置されていることを特徴とする請求項１４に記載の回路。
【請求項１６】
比較器（６）の出力信号が、加算器（７）によって加算可能であることを特徴とする請求項１３〜１５のいずれか１項に記載の回路。
【請求項１７】
加算器（７）は、カスケードされたモジュール、特に加算器及び／又は加算ユニットから構成されていることを特徴とする請求項１６に記載の回路。
【請求項１８】
加算器（７）の出力信号が、比較操作を実行するユニット（８）によって閾値と比較可能であることを特徴とする請求項１６又は１７に記載の回路。
【請求項１９】
閾値は、可変にプリセット可能であることを特徴とする請求項１８に記載の回路。
【請求項２０】
閾値を超えた場合、データ記憶器（３）内で検出されたデータのアドレス及び／又は検出されたデータが、アドレスポインタ（９）によって結果記憶器（１０）内に出力可能であることを特徴とする請求項１８又は１９に記載の回路。
【請求項２１】
アドレス（７）の出力信号が、データ記憶器（３）内で検出されたデータのアドレス及び／又は検出されたデータに割当て可能であるか及び／又は結果記憶器（１０）内に出力可能であることを特徴とする請求項２０に記載の回路。
【請求項２２】
ホストコンピュータ（１２）は、インターフェース（１１）を介して回路及び／又はチップ（１）に接続可能であることを特徴とする請求項１〜２１のいずれか１項に記載の回路。
【請求項２３】
データを探索するための規則が、ホストコンピュータ（１２）によってレジスタ（２）内に読込み可能であることを特徴とする請求項２２に記載の回路。
【請求項２４】
データ記憶器（３）内で検出されたデータのアドレス及び／又は検出されたデータが、ホストコンピュータ（１２）によって読取り可能であることを特徴とする請求項２２又は２３に記載の回路。
【請求項２５】
チップ（１）及び／又はデータ記憶器（３）及び／又はアドレスポインタ（９）及び／又は結果記憶器（１０）及び／又はインターフェース（１１）が、少なくとも１つのボード（１３）上に配置されていることを特徴とする請求項１，２４，６，２０，２１，２２〜２４のいずれか１項に記載の回路。
【請求項２６】
データ記憶器（３）及び／又はデータポインタ（９）及び／又はアドレスポインタ（９）及び／又は結果記憶器（１０）及び／又はインターフェース（１１）が、チップ（１）上に配置されていることを特徴とする請求項１〜２５，６，２０，２１のいずれか１項に記載の回路。
【請求項２７】
データは、データ記憶器（３）から平行に読取り可能であることを特徴とする請求項１〜２６，６のいずれか１項に記載の回路。
【請求項２８】
平行な構成は、データ記憶器（３）内で及び／又はボード（１３）上で実現可能であることを特徴とする請求項２７又は２５に記載の回路。
【請求項２９】
データが、データ記憶器（３）内で並びに／又はチップ及び／若しくはボード（１３）上に組込まれたマルチプレクサによって結合可能であることを特徴とする請求項２７，２８，２５のいずれか１項に記載の回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、少なくとも２つのレジスタを有するチップを備えたデータを処理するための回路に関する。
【背景技術】
【０００２】
少なくとも２つのレジスタを有するチップを備えたデータを処理するため回路が公知である。データバンクに格納されたデータを探索するソフトウェアも公知である。この場合、これらのデータは、一般に個別の符号から構成されている。一般にこの探索は、一般に用いられているコンピュータでプログラムをシーケンス処理することによって実行されている。
【０００３】
このようなソフトウェア的な実行は、プロセッサのクロック周波数自体が非常に速くてもこのプログラムに必要な命令のシーケンス処理が非常に長いトータル時間を必要とするという点で特に問題である。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明の課題は、データバンクの探索が時間的に最適であるデータを処理する回路を提供することにある。
【課題を解決するための手段】
【０００５】
この課題は、本発明により、請求項１に記載の特徴を有するデータを処理するための回路によって解決される。したがって、データバンクに格納されたデータを探索するための規則がレジスタ内に記憶されていて、これらの規則がほぼ同時に処理可能であるように、データを処理するためのこの回路が構成されていてかつ改良されている。
【０００６】
本発明の方法では、従来の方法とは違って、データバンクに格納されているデータをソフトウェア的に探索する必要はなくて、探索がハードウェア的に実行されることによって、非常に速い探索が実現され得ることがまず第１に分かる。さらに本発明のその他の方法では、データバンクを探索するのに必要な探索モデルを規定する規則がレジスタ内に記憶されなければならないこと、及び、規則がほぼ同時に処理する必要があり、例えば順次的に処理されてはならないことが分かる。この場合、データがどのような種類のものであるかは問題ではない。例えば、インターネット用のインテリジェント探索機械装置の回路に対して使用することが考えられる。例えばデータを収集し分析する軍事的な産業の分野での全く別の使用可能性も確かに可能である。本発明の回路は、確かに特に好適な方法で分子生物学のいろいろな分野に、例えば遺伝子モチーフやタンパク質モチーフの探索で適している。各データの探索速度が、規則をほぼ同時に処理することによって著しく上昇できる。
【０００７】
データの特に速い探索に関しては、規則が１つのサイクル又は多数のサイクル内で処理可能である。
【０００８】
特に要求の多い複雑な探索モデルを考慮した場合、規則は、論理式及び／又は範囲の定義及び／又はワイルドカード関数を含む。この場合、ワイルドカード関数は、１つの出力信号が符号ごとに生成されることを可能にする。この場合、探索モデルには、個々の符号のほかに符号の組み合わせ、例えば全ての語及び／又は数もある。付加的に又は代わりに、規則は、Regular-Expression関数を含んでもよい。論理式の場合、特にＯＲ結合及びＡＮＤ／ＮＯＴ結合を特に簡単に実現することができる。
【０００９】
データバンクを実行するための探索が符号化されレジスタ内に記憶されることがさらな
る利点である。このとき、これらのレジスタは、２n ビット分の幅を有する。このことは、複雑な探索モデルの実行と検出を特に簡単に実現する。
【００１０】
特にコンパクトな構成の範囲内では、データバンクのデータがデータ記憶器内に記憶され得る。特に簡単な構成では、このデータ記憶器はＲＡＭ又はＦＩＦＯとして構成できる。
【００１１】
データの探索を特に簡単に実現するため、少なくとも１つのデータレジスタをチップ上に配置してもよい。この場合、データバンクのデータが、特にデータ記憶器から１つの又は複数のデータレジスタ内に移動可能である。このデータレジスタは、符号の数に応じて２n ビットの幅でもよい。このとき、データバンクのデータが、連続してこのデータレジスタ内にシフトされ得るか及び／又はこのデータレジスタをシフトされ得る。
【００１２】
特に簡単でかつ特に時間を最適にする探索を考慮した場合、データレジスタの数を、データバンクの探索のための規則が記憶されているレジスタの数に等しくしてもよい。これによって、全ての規則が平行にかつ１つのサイクル内で処理されることを特に簡単な方法で可能にする。このとき、回路構成のこの平行性はいわば２次元的である。すなわち一方では、ウィンドーが表示され、データの一部の全ての符号の位置又は符号の組み合わせの位置の比較が同時に可能になり、他方では規則によって規定されたいろいろな符号又は符号の組み合わせが、各符号の位置又は符号の組み合わせの位置に対して検出され得る。
【００１３】
さらに非常に簡単な構成を考慮した場合、データが少なくとも１つのエンコーダによって符号化可能である。この場合、データが、１つのエンコーダ又は複数のエンコーダによって２n ビットの１つの符号にコード化可能である。探索すべきデータのこの符号化は、データと規則との特に簡単な比較を可能にする。その結果、１サイクル内で複雑な探索モデルを特に速く検出することが可能になる。
【００１４】
さらに時間を最適にした構成を考慮した場合、レジスタは、１つ又は多数の比較器を用いて１つ又は多数のデータレジスタからデータを移動可能である。この又はこれらの比較器は、場合によってはこのときに符号化された規則と符号化されたデータとをビットごとに比較し、１つのビットで一致したときに１つの出力信号を生成する。その代わりに、個々のビットの比較をＡＮＤゲートを用いて実現することも可能になる。
【００１５】
チップの特に簡単な構成の範囲内では、１つのレジスタ，１つのデータレジスタ，１つのエンコーダ及び１つの比較器がそれぞれ１つの個別符号要素に統合してもよい。その代わりに、１つの個別符号要素が、１つだけのレジスタ，１つのデータレジスタ及び１つの比較器を有してもよい。このとき、データがデータレジスタ内に移動される前に、これらのデータを符号化するため、エンコーダを個別符号要素の前に接続してもよい。
【００１６】
個別符号要素は、特に機能的な構成に関して並列に接続でき、特にチップ上に配置できる。ほとんどの信号がパイプライン状に回路に流れるので、この接続と配置は、複雑でない回路構成で実現される。このとき、同時に探索可能なデータの一部又は−データの一部の全ての符号の位置の比較が同時に可能になる−ウィンドーの大きさが、並列に接続された個別符号要素の数によって決定される。
【００１７】
次いで、これらの比較器の出力信号が、加算器によって加算可能である。これによって、探索されたデータが見つけ出そうとするデータにどの程度一致するかに関する情報を得ることが可能になる。
【００１８】
特に機能的な構成を考慮した場合、加算器は、カスケードモジュールから、特に加算器及び／又は加算器レジスタから構成できる。このことは、比較器からの多数の出力信号を加算することを特に簡単な方法で可能にする。この場合、比較すべき符号又は符号の組み合わせの数は、個々の加算器の物理的な制限によって限定されない。
【００１９】
データの特に変更可能な探索の範囲内では、加算器の出力信号が、比較操作を実行するユニット、例えば比較器によって１つの閾値と比較可能である。この加算器の出力信号は、特に好ましい方法ではｎビットの１語でもよい。この場合、この閾値は、特に柔軟な構成の範囲内で変更可能にプリセット可能であり、例えばこの閾値が実際のサイクル内で探索されたデータが見つけ出そうとするデータに一致する百分率を示すように、この閾値は設定される。
【００２０】
閾値を超えた場合、検出されたデータの記憶器アドレス及び／又は検出されたデータが、アドレスポインタによって結果記憶器内に出力可能である。したがって、このアドレスポインタは、実際のサイクル内にデータレジスタ内に存在するデータのアドレスをデータ記憶器内で追跡した。
【００２１】
データの可能なその他の処理を考慮した場合、加算器の出力信号が、データ記憶器内で検出されたデータのアドレス及び／又はデータに割当て可能であり、及び／又は結果記憶器内に出力可能である。したがって、例えば、もう１つの閾値を超えた出力信号だけが考慮されることによって、既に実行された探索をさらに限定することを可能にする。
【００２２】
特にオペレータに親切な構成を考慮した場合、ホストコンピュータが、インターフェースを介して回路及び／又はチップに接続可能である。このとき、ホストコンピュータを用いて、例えばデータを探索するための規則をレジスタ内に及び／又はデータ記憶器内のデータに読込み可能である。その代わりに又は付加的に、検出されたデータのアドレス及び／又は検出されたデータ並びに加算器の出力信号が、ホストコンピュータを用いて読取り可能である。ここでは、このホストコンピュータは、商業的に入手可能なＰＣでよい。
【００２３】
特にコンパクトな構成を考慮した場合、チップ及び／又はデータ記憶器及び／又はアドレスポインタ及び／又は結果記憶器及び／又はインターフェースは、少なくとも1 枚のボード上に配置され得る。確かに、多数のチップ及び／又は多数のデータ記憶器を互いに接続すること、及び／又は1 枚のボード上に配置することも可能である。その代わりに、データ記憶器及び／又はアドレアスポインタ及び／又は結果記憶器及び／又はインターフェースをチップ上に配置してもよい。
【００２４】
処理速度をさらに最適にするため、及び回路に接続しているバスの帯域幅の制限をなくすため、データをデータ記憶器から平行に読取り可能である。この場合、この平行な構成は、データ記憶器内で及び／又はボード上で実現できる。このとき、データが、例えば平行にデータ記憶器から読取られ得る。これによって、読取り速度が上昇する。データ記憶器内に及び／又はチップ上に及び／又はボード上に組込まれたマルチプレクサによって、データが結合され得、次いでデータレジスタ内に移動され得る。この場合、入力接点の数が、並行性係数(Parallelitaetsfaktor)だけ上昇し、必要な帯域幅が確かに同じ係数だけ減少した。
【００２５】
本発明のモデルを好適な方法で構成し改良するといういろいろな可能性が存在する。これに対しては、一方では請求項１に従属する請求項及び他方ではデータを処理する本発明の回路の好適な実施の形態の図面に基づく以下の説明に記載されている。本発明の回路の好適な実施の形態の図面に基づいた説明と関連して、モデルの一般に好適な構成とその他の構成も説明する。
【発明を実施するための最良の形態】
【００２６】
図1 及び図2 はそれぞれ、−ここでは完全に示さなかった−32個のレジスタ２を有するチップ１を備えたデータを処理する回路の実施の形態を示す。
【００２７】
本発明の方法では、データバンクに格納されているデータを探索するための規則が、レジスタ２内に記憶されている。これらの規則は、同時に処理可能である。
【００２８】
探索モデルを規定するこれらの規則は、これらの実施の形態では論理式，範囲の定義及びワイルドカード関数である。これらの論理式には、これらの実施の形態ではＯＲ結合とＡＮＤ／ＮＯＴ結合がある。データバンクを探索するための規則は、符号化されてレジスタ２内に記憶されている。この場合、図1 ，２中に示された符号は、論理式「ＢorＷorＹ」に相当する。
【００２９】
データバンクのデータが、データ記憶器３内に記憶されている。このデータ記憶器３は、これらの実施の形態ではＲＡＭとして構成されている。
【００３０】
データレジスタ４が、チップ１上に配置されている。データバンクのデータが、データ記憶器３からデータレジスタ４内に移動可能である。データレジスタ４の数は、レジスタ２の数に等しい。データを探索するための規則がレジスタ２内に記憶されている。すなわち、32符合長さのデータセットが、１サイクルごとにこれらの規則と比較され得る。
【００３１】
図２の実施の形態では、データがエンコーダ５によって符号化される。この場合、エンコーダは、ｎ／２n エンコーダである。このエンコーダは、データをｎビットの１つの符号に符号化する。次いで、これらのデータは、比較器６によってレジスタ２内の規則とビットごとに比較され、一致したときに１つの出力信号を生成する。
【００３２】
１つのレジスタ２，１つのデータレジスタ４，１つの比較器６及び図２の実施の形態では１つのエンコーダ５がそれぞれ、１つの個別符号要素１４，１４′に統合されている。これらの個別符号要素１４，１４′は、並列に接続されていて、さらに互いに平行にチップ１上に配置されている。
【００３３】
比較器６の出力信号が、加算器７によって加算され、この加算器７の出力信号−この場合では４ビット語−が、比較操作を実行するユニット８によって１つの閾値と比較される。この閾値は、データが見つけ出されたデータにどの程度一致するかを評価する可能性を提供し、かつオペレータによって可変にプリセット可能である。
【００３４】
閾値を超えた場合、データ記憶器３内で検出されたデータのアドレスが、アドレスポインタ９によって結果記憶器１０内に記憶される。
【００３５】
回路の関数の実行が、図３中に示されている。複数のデータが、データレジスタにこれらのデータをシフトさせ、そしてこれらのデータを規則によってプリセットされている探索モデルによって探索される。比較器の出力信号は、調べられた符号が規則と一致するかどうかを示す。出力信号の和が、調べられたデータと見つけ出されたデータとの一致に関する目安である。何故なら、この一致は、どれだけの符号が探索モデルに一致するかを示すからである。１つの可変な閾値と比較することによって、検出されたデータのアドレスを記憶するトリガー信号が、いろいろな大きさの一致度で生成される。
【００３６】
図４及び図５は、図１及び図２の実施の形態の個別符号要素の構成を概略的に示す。１つのレジスタ２，１つのデータレジスタ４，１つの比較器６及び図２の実施の形態では１つのエンコーダ５が、個別符号要素１４，１４′内に統合されている。これらの個別符号要素１４，１４′は、チップ１上で平行であり、かつ互いに並列に接続されて配置されている。
【００３７】
図６は、ボード１３を示す。チップ１，データ記憶器３及びインターフェース１０が、このボード１３上に配置されている。ホストコンピュータ１２−ここでは商業的に入手可能なＰＣ−が、インターフェース１１を介して回路に接続可能である。ホストコンピュータ１２によって、まずデータを探索するための規則がレジスタ２内に読込まれ、次いでデータがデータ記憶器３内に読込まれる。付加的に、閾値がホストコンピュータ１２によってプリセットされる。そして、検出されたデータのアドレスが、結果記憶器１０から読取られ、検出されたデータが、データ記憶器３から読取られる。
【００３８】
さらなる詳細に関しては、繰返しを避けるため、共通の説明を参照のこと。
【００３９】
上述した実施の形態は、専ら要求されるモデルを検討するために使用され、これらのモデルは、これらの実施の形態に限定されないことは自明である。
【図面の簡単な説明】
【００４０】
【図１】データを処理する本発明の回路の実施の形態を概略図で示す。
【図２】本発明の回路のもう１つの実施の形態を概略図で示す。
【図３】本発明の回路内の関数の実行を概略的に示す。
【図４】図1 の本発明の回路の個別符号要素を概略図で示す。
【図５】図２の本発明の回路の個別符号要素を概略図で示す。
【図６】本発明の回路の可能な構成を概略図で示す。
【符号の説明】
【００４１】
１    チップ
２    レジスタ
３    データ記憶器
４    データレジスタ
５    エンコーダ
６    比較器
７    加算器
８    比較ユニット
９    アドレスポインタ
１０  結果記憶器
１１  インターフェース
１２  ホストコンピュータ
１３  ボード
１４  単一文字要素
１４′単一文字要素
【図３】
2004533033.tif 000003
【国際公開パンフレット】
2004533033.tif 000004
2004533033.tif 000005
2004533033.tif 000006
2004533033.tif 000007
2004533033.tif 000008
2004533033.tif 000009
2004533033.tif 000010
2004533033.tif 000011
2004533033.tif 000012
2004533033.tif 000013
2004533033.tif 000014
2004533033.tif 000015
2004533033.tif 000016
2004533033.tif 000017
2004533033.tif 000018
2004533033.tif 000019
2004533033.tif 000020
2004533033.tif 000021
2004533033.tif 000022
2004533033.tif 000023
2004533033.tif 000024
【国際公開パンフレット（コレクトバージョン）】
2004533033.tif 000025
2004533033.tif 000026
【国際調査報告】
2004533033.tif 000027
2004533033.tif 000028
2004533033.tif 000029
2004533033.tif 000030
2004533033.tif 000031
2004533033.tif 000032
2004533033.tif 000033
2004533033.tif 000034