(57)【特許請求の範囲】
【請求項１】
相互接続された段を含む２方向パイプラインで相互に逆方向に流れるデータ要素を管理するシステムにおいて、
前記パイプラインでの段から段への前記データ要素の移動を制御する回路と、
前記パイプラインを下向きに流れる各データ要素を、その各データ要素と出会った前記パイプラインを上向きに流れてきた各データ要素と相互作用させる回路と、
少なくとも空（Ｅ）、一杯（Ｆ）、上向きに移動するデータ要素が存在する（Ｕ）、下向きに移動するデータ要素が存在する（Ｄ）、およびＣｏｍｐｌｅｔｅの各状態を占めることができる前記パイプライン中の各段の状態を判定する回路と
を備えることを特徴とするシステム。
【請求項２】
さらに、前記パイプラインを下向きに流れる各データ要素を、その各データ要素と出会った前記パイプラインを上向きに流れてきた特定のデータ要素と一度だけ相互作用させる回路を備えることを特徴とする請求項１に記載のシステム。
【請求項３】
相互接続された段を含む２方向パイプラインで相互に逆方向に流れるデータ要素を管理する方法において、
前記パイプラインでの段から段への前記データ要素の移動を管理するステップと、
前記パイプラインを下向きに流れる各データ要素を、前記パイプラインを上向きに流れて前記各データ要素と出会った各データ要素と相互作用させるステップと、
少なくとも空（Ｅ）、一杯（Ｆ）、上向きに移動するデータ要素が存在する（Ｕ）、下向きに移動するデータ要素が存在する（Ｄ）、およびＣｏｍｐｌｅｔｅの各状態を占めることができる前記パイプライン中の各段の状態を判定するステップと、
前記パイプラインでの段から段への前記データ要素の移動を実行するステップと、
を含むことを特徴とする方法。
【請求項４】
さらに、前記パイプラインを下向きに流れる各データ要素を、前記パイプラインを上向きに流れてきて前記各データ要素と出会った特定のデータ要素と一度だけ相互作用させるステップを含むことを特徴とする請求項３に記載の方法。
【請求項５】
さらに、前記パイプラインを下向きに流れる第１のデータ要素の少なくとも一部を、前記パイプラインを上向きに流れてきて前記第１のデータ要素の少なくとも一部が出会った第２のデータ要素の一部と比較するステップを含むことを特徴とする請求項３に記載の方法。
【請求項６】
さらに、前記比較ステップが完了するまで、一杯状態の段からデータ要素が移動するのを妨げるステップを含むことを特徴とする請求項５に記載の方法。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明はコンピュータに関し、さらに詳細には、相互接続された段を含む２方向パイプラインで相互に逆方向に流れるデータ要素を管理するためのシステムに関する。
【０００２】
【従来の技術】
計算パイプラインは何年も前から、信号処理、汎用計算装置、およびその他のディジタル計算アプリケーションで使用されている。計算パイプラインでは、情報がパイプラインを介して主として１つの方向にある段から他の段へ流れ、パイプラインの様々な段で様々な方法で処理される。
計算パイプラインの初期の応用例の１つに、コンピュータ・グラフィック・イメージをレンダリングするためのものがある。この種のパイプラインでは、イメージを表すデータがコンピュータ・メモリから一連の処理段を介して、最終的にコンピュータ・ディスプレイ上に表示される。他の種類の計算パイプラインは一般的に乗算に使用されている。この場合、乗算を構成する多数の加算はパイプラインの段として構成される。被乗数がパイプラインを通過するにつれて、パイプラインの端で完全積が形成されるように、各段で部分積が累積されていく。コンピュータでのパイプラインのこのような使用法では、データ要素は単一の方向にしか流れない。
【０００３】
縮小命令セット・コンピュータ（ＲＩＳＣ）プロセッサも内部パイプラインを使用して命令を実行する。パイプラインの第１段で、命令メモリから命令が取り出される。後ろの段で、命令が様々に復号され、実行され、その答えが記録される。そのようなパイプラインでは、最初の命令で計算されたデータができるだけ早く後の命令に渡されるように、後ろの段の出力を前の段の補助入力に接続する「バイパス」接続があるのが一般的である。バイパス経路がない場合、すべての計算済みデータをレジスタ・ファイルに記録しないかぎり、後ろの命令にアクセスすることはできない。
【０００４】
そのようなＲＩＳＣプロセッサでは、複数のバイパス経路のために重大な設計上の問題が発生する。ほぼあらゆる段からほぼあらゆる前の段へのバイパスが必要とされるので、各段は多数の入力を有する。そのように多数のデータ経路上でデータ・フローを管理する必要によって、そのようなＲＩＳＣコンピュータ用の制御システムを設計することは難しくなっている。各段は入力をその前段から取るか、それとも多数のバイパス経路のうちのどれかから取るかを選択しなければならないので、単一の段の設計でも非常に複雑になる。
【０００５】
今日使用されている大部分の計算装置は同期式であり、外部から提供されるクロック信号を使用して、一連の動作を順次実行する。各動作は、次のクロック事象が到達した後にしか実行されず、すべての部分が動作する場合、厳密に同じ間隔で実行される。
【０００６】
非同期回路では、ローカル条件で許容されるときには、各個別の部分は独立に動作する。ローカル論理機構は、条件が正しいときを検出して適当な動作を開始する。非同期パイプライン中の各段と次の段とが、前記次の段へのデータ転送が適切であると合意するときには、各段は外部クロッキング信号を参照せずにそのようなトランザクションを行う。
【０００７】
同期システム中のバイパス経路構造は２つの理由で望ましくない。第１に、集積回路が大規模になるにつれて、長いバイパス経路での遅延が過度なものになり、より遅いクロック速度が必要になる。第２に、大規模な集積回路では、パイプラインのすべての部分に同じクロック信号を転送することは難しい。パイプラインの異なる部分へのクロック信号のタイミングの差を「クロック・スキュー」と呼ぶ。近くのクロック信号に対してクロックがスキューされているパイプライン中で遠くに位置するソースからきたデータを受け入れることは難しく、あるいは不可能である。
【０００８】
非同期システムでは、その遠くにある部分が、ローカル情報の動作時間とはまったく独立に動作することがあるので、バイパス経路を実施するのは非常に難しい。非同期システム中の遠く離れた段間でデータを移動する際には十分に注意しなければならない。設計上の注意が不十分であると、データ要素が損傷を受け、あるいは失われ、したがって、システムが信頼できないものになることがある。１つには、このタスクの難しさのために、現在、非同期システムはめったに使用されない。
【０００９】
最後に、バイパス構造が存在するには、データがいつ実際にパイプラインで移動するかを慎重に制御する必要がある。今日使用されている大部分のシステムでは、どれかの段がデータを移動できなくなった場合、その段は、それ自体が停止することを他のすべての段に通知し、他のすべての段は待機する。停止信号は、どの段でも発信することができ、かつすべての段に転送しなければならないので、多数の入力項目を含む論理関数だけでなく、冗長な通信経路も伴う。これらは共に遅延の原因となる。したがって、停止信号自体がシステム中のペーシング項目になることがある。
【００１０】
主として設計者が設計が難しいとみなしているため、非同期パイプラインはまれである。幾つかの非同期パイプラインは現在、主として信号処理アプリケーションおよび入出力アプリケーションにおいて先入れ先出しバッファ・メモリで使用されている。特に簡単な形の非同期パイプラインは、米国特許第５１８７８００号および第４８３７７４０号と、Ｍｉｃｒｏｐｉｐｅｌｉｎｅｓと題する文献に記載された。これまでに作成された非同期パイプライン装置では、情報は単一の方向にしか流れず、あるいは情報が複数の方向に流れる場合は、別々の方向用にまったく別々の機構が使用される。そのような構造は、１方向パイプラインを複合した使用法に過ぎない。
【００１１】
今までの所、非同期設計形式の多数のバイパス経路を含むＲＩＳＣコンピュータは、設計者の能力を超えていることが立証されている。今までに設計された非同期ＲＩＳＣ（Ｃａｌｔｅｃｈ、Ｍａｎｃｈｅｓｔｅｒ）で、バイパス経路を不要にしたものはほとんどなく、したがって、不要な遅延および機能低下が発生している。
【００１２】
弾性対非弾性
パイプライン・システムは「弾性」でも「非弾性」でもよい。弾性パイプラインでは、必要に応じて、パイプラインを介して流れるデータのストリーム中のギャップを形成することも、あるいは消すこともできる。一方、非弾性パイプラインでは、「バブル」と呼ばれる規則正しいデータ・ストリーム中のギャップは所定の位置のままである。弾性パイプラインは非弾性パイプラインよりも融通性に富む。たとえば、弾性パイプラインのある段階が特定のデータ要素に作用するのに通常よりも長い時間を必要とする場合、すでに遅延段を通過した他のデータ要素は、結果としてデータ・ストリーム中にギャップを導入することになっても制限なしに自由に進んでいく。したがって、様々な段の処理時間の差は、様々な種類のバッファによって平滑化することができる。しかし、重要なこととして、弾性パイプラインでは既存のデータ要素を削除し、パイプライン内に新しいデータ要素を挿入することができる。弾性パイプラインでは、特定のデータ要素を削除すると単に、後のデータ要素を充填できるギャップが単に残るだけである。同様に、弾性パイプラインはパイプライン中の後の要素の転送を遅延させることによって、新しいデータ要素を自由に挿入することができる。これらの挿入動作および削除動作は、記憶されているデータの特定の部分が画面に表示されず、したがってデータ・ストリームから削除すべきであり、あるいは現在の視点が、表示されているオブジェクトの特定の部分に非常に近いので、前記視点をさらに詳細に表示すべきであることを計算の一部によって判定できるグラフィクス・パイプラインで使用されている。
【００１３】
システムによっては、弾性パイプラインの利益の一部が、「バブル」によって、普通なら非弾性のシステムで得られる。そのような非弾性システムでは、データ要素のストリームが規則正しい間隔で離間される。あるデータ要素が削除されると規則正しい間隔が破壊される。データ要素は、単に削除される代わりに、空白またはバブルと置換される。バブルは、データ要素の位置を保持するが、計算には入らない。非弾性パイプラインは、バブルを導入することによって、削除を処理することができる。ただし、非弾性パイプラインは、このように生成されたギャップを充填するので速度上の利点を得ることはできない。非弾性パイプラインは、既存のバブルと置換しない限り、新しいデータをストリームに挿入することができない。利用できるバブルがないと、新しいデータを挿入することはできなくなる。
【００１４】
パイプライン用のアプリケーション
２つのデータ・ストリームのすべての要素を比較することが望ましい多数のアプリケーションがある。多くのアプリケーションでは、一方の方向に流れるそれぞれのまたはあらゆるデータが他の方向に流れるそれぞれのまたはあらゆるデータと相互作用することが重要である。２つの相互に逆の方向に流れるデータ要素が相互作用なしで通過する場合、そのようなアプリケーションの機能が破壊される恐れがある。たとえば、ワード探索アプリケーションでは、探索中のテキスト中のそれぞれのまたはあらゆるワードが実際に、それぞれのまたはあらゆる探索ワードと突き合わせて試験されることが重要である。「逆同期比較」の語は、本明細書では、パイプラインの何らかの段で一度だけ、相互に逆の方向に進む要素間で相互作用が発生することを意味する。
【００１５】
１つの形の比較回路は、特定のキーワード用の探索テキストに適用される探索エンジンで使用されている。そのようなシステムでは、各キーワードがシステム中の固定段に記憶され、探索すべきテキストが、１方向パイプラインを介してこれらのキーワードを通過する。パイプライン中の各段で、記憶されているワードが通過するワードと比較され、あらゆる一致が報告される。
【００１６】
そのような１方向計算パイプラインは、比較的固定されたデータ・セットを比較的可動のセットと比較することができる。各ステップで計算パイプライン中の段と同じ数の比較が実行され、移動するセットの各要素が順番に、固定セットの各メンバに出会う。
【００１７】
移動するデータ要素が順番にパイプラインの各段に出会うので、各データ要素を一度に１つの場所だけに送ればよく、その場所はデータ要素のソースに近接したもの、すなわち計算パイプラインの前段である。したがって、計算パイプラインは、高スループットを有し、連想メモリなどの代替比較回路よりも必要とされる電力が少ない。
【００１８】
１方向計算パイプライン中の段の数は、固定データ・セットに存在できるデータ要素の数を制限する。通常、固定データ・セットの各要素ごとに１つのセルまたは１つの段があり、移動するセットの新しい要素を比較のために入力するよりも固定セットの要素を変更することの方が比較的難しい。
【００１９】
シストリック・アレイも過去に説明されている。シストリック・アレイ計算装置では、類似の段のアレイは何らかの複雑な計算動作を実行するように最も近い段と通信する。シストリック・アレイでは、当技術分野で一般に理解されているように、隣接する要素間の通信が規則正しいスケジュールで行われる。各段での計算動作は、このデータ転送スケジュールに適合しなければならない。
【００２０】
パイプライン接続は通信システムでも使用されている。たとえば、Ｓｅｉｔｚは、メッセージが特定の発信元から特定の宛先へ進むようにネットワーク中の１つの段から他の段に送られるシステムを説明している。Ｓｅｉｔｚのシステムでのメッセージは両方向へ進むが、２つのフロー中のデータ要素は完全に独立している。ある方向へ流れるメッセージと他の方向へ流れるメッセージの間に相互作用はない。
【００２１】
【発明が解決しようとする課題】
本発明は、両方向のデータ・フローを制御でき、相互に逆の方向に流れるデータ要素がパイプラインの各段で確実に相互作用できるようにする２方向パイプラインを提供する。
【００２２】
【課題を解決するための手段】
本発明は、規則正しい経路に沿った逆方向への不規則なデータ・フローを提供して、後ろの段から前の段へのデータ転送を大幅に簡単にする。本発明によれば、データは、送られるデータ、データが送られる際に通過する特定の段、およびデータに対して実行される予定の動作に応じて、不規則なスケジュールで移動することができる。本発明は、２つのデータ・セットを対称的に扱い、ＲＩＳＣコンピュータ用の非常に簡単で規則正しい構造を形成することができる。パイプライン中の各段は主として、その段の先の段と後ろの段だけと通信する。データ要素は使用される前にいくつかの段を通過することができる。本発明は、ＲＩＳＣコンピュータで共通に見られる複雑な１組のバイパス経路を単一の戻り経路と置換することによって、重要な設計の単純性を得る。直接バイパス経路を介するのではなくいくつかの段を介してデータを送信する遅延は、簡単な設計で高速度が可能なため最小限のものである。
【００２３】
本発明は新規の同期実施態様および非同期実施態様を含む。今日の同期パイプラインは通常、段間のハンドシェーク・プロトコルによって動作する。そのようなハンドシェーク・プロトコルでは、受信側が、新しいデータ要素を収容するための空間があることを送信側に示す。データ要素が利用可能な場合、送信側はそのデータ要素を取るべきであることを受信側に示す。したがって、現在使用中のハンドシェーク・プロトコルでは、データをいつ転送すべきかを決定するのは送信側だけである。この方法は、「バブル」、すなわち普通なら円滑なデータ・フロー中の空の場所に順応する。本発明は、データがいつ、ある段から次の段に移動できるかを、隣接する段が相互にかつ対称的に決定する対称形の通信を含む。
【００２４】
本明細書で開示される相互に逆の方向に流れる計算パイプライン用の非同期実施態様は、情報を非同期にかつ同時に２方向に送る能力が独特である。
【００２５】
本発明は、相互に逆の方向に流れる２つのデータ・ストリーム間の逆同期（ｃｏｕｎｔｅｒｓｙｎｃｈｒｏｃｉｚｅｄ）比較を行うための簡単な対称的機構を記述するものである。この機構が対称的で簡単なものであるため、様々なタスクを実行するための特定の計算装置を接続する豊富な機会が容易に実現され、提供される。逆方向同期比較を行うために特殊な回路が含められている。カウンタフロー・パイプラインの逆同期比較によって、前記パイプラインは最も有用になり、いくつかの利点を提供する。
【００２６】
本発明は大域的機能停止信号の必要をなくす。各段は自立しており、通信する必要があるのは、隣接する段だけである。必要とされるのがローカル通信だけなので、長い接続と、その接続がもたらす遅延および電力消費量とが不要になる。ある段が動作するのにさらに時間が必要である場合、前記ある段は、それに隣接する段がうまく動作するように、前記隣接する段だけに通知する。
【００２７】
本発明は、ローカル制御をこのように使用することによって、非同期システムで使用するのに理想的なものになる。非同期システム中の各段は、それ自体のペースで進み、データを受け入れ、あるいは送る準備ができたことを隣接する段に通知することができる。大域クロックは不要であるが、さらに重要なこととして、大域的制御信号が不要である。バイパス経路を含む同期システムに共通に見られる機能停止信号は不要になる。
【００２８】
本発明は双方向的で、かつ弾性的であるパイプラインを提供する。従来、弾性パイプラインは単一方向だけに流れるものとして説明されてきた。本発明は、他の方向のデータ・フロー中のギャップによって相互作用が不要になる場合に、相互作用のないパイプラインに沿ったどちらかの方向のフローを可能にすることによって、パイプラインの弾性特性を拡張する。
【００２９】
発明の詳細な説明
概要
本発明は、直線状に進む一連の段から成るカウンタフロー・パイプラインを含む。この説明のために、直線状進行が垂直なものとみなされるように上下に重なりあったものとして段を記述する。もちろん、すべての電子システムと同様に、論理的に隣接する段が合理的に近接している限り、空間での段の実際の配置は、段の正しい動作とは無関係である。
【００３０】
パイプライン中の各段は、前記各段に直接隣接する２つの段とどちらの方向へでも通信することができる。通信が双方向的なものなので、情報は１組の段に沿って上向きにも下向きにも流れることができる。
【００３１】
カウンタフロー・パイプラインは、パイプラインを上向きに流れる１組のデータ要素とパイプラインを下向きに流れる他の１組のデータ要素を同時にストリーム化することができる。上向きストリーム化動作と下向きストリーム化動作は独立のものでよい。どちらかのデータ・ストリームのすべてまたは一部は、前記ストリームの始めにそれにデータを送り、前記ストリームの終りにそれからデータを受け入れる機構の必要に応じて移動することも、あるいは静止し続けることもできる。制御機構によってパイプラインが両方向で「弾性的」になるので、データ・ストリームのどちらかまたは両方にギャップが存在することができる。
【００３２】
段間の実際の通信は、任意の好都合な機構に適応させることができる。大部分の場合、通信は、伝達すべき各データ・ビットごとに１本ある適当な１組のワイヤを介して行われる。段間の通信は、データ要素全体を送るために複数のステップを必要とする、一度に１ビットだけ送る直列形でも、あるいは一度に複数ビット送る直列形でもよい。同様に、通信は、電気的手段でも、光学手段でも、音響手段でも、その他の適当な手段でも行うことができる。
【００３３】
カウンタフロー・パイプラインの各段は、一方が順方向に流れるデータ要素用のもので、他方が逆方向に流れるデータ要素用のものである、少なくとも２つのメモリ要素、たとえばレジスタを含む。もちろん、これらのレジスタのどちらかまたは両方は、その方向の規則正しいデータ・フロー中にギャップがある場合、いつでも空になることができる。これらのレジスタが共にデータ要素を含むのは、データが両方向に提供される場合だけである。
【００３４】
２つのストリーム中のデータ要素はサイズが異なっても、あるいは機能が異なってもよい。同様に、２つのストリーム中のビットの意味は、類似するものでも、あるいはまったく異なるものでもよい。上向きフロー用のレジスタは下向きフロー用のレジスタと同じ数のデータ・ビットでも、それより多いデータ・ビットでも、それより少ないデータ・ビットでも収容することができる。大部分の有用なシステムでは、各段中の２つのレジスタ中のビットの数は異なる。さらに、パイプラインの異なる部分は、その処理段でのデータ要素のニーズに合うように、必要に応じてより多くのビットまたはより少ないビットを保持するレジスタをもつことができる。上向きフローは異なる場所で、下向きフローよりも「広く」ても、あるいは「狭く」てもよい。これは、ストリーム中の各データ要素中のビット数を指す。
【００３５】
レジスタ占有の４つの可能な状態がある。どちらのレジスタもデータ要素を含まない場合、その段は「空」（Ｅ）であると言われる。両方のレジスタがデータ要素を含む場合、その段は「一杯」（Ｆ）であると言われる。１つのレジスタだけがデータ要素を含む場合、その段は、話の都合に応じて「半分充填」されているとも、あるいは「半分空」であるとも言われる。半分充填されており、あるいは半分空であるときの段の状態は、存在するデータ要素によって命名することができる。たとえば、この状態は、上向きストリームに関連するレジスタだけがデータ要素を含む場合は「上向き」（Ｕ）と言われ、下向きストリームに関連するレジスタだけがデータ要素を含む場合は「下向き」（Ｄ）と言われる。したがって、段は、状態「Ｅ」、状態「Ｆ」、状態「Ｕ」、あるいは状態「Ｄ」であると言うことができる。
【００３６】
段間の通信回路は、１）ある段中の上向きレジスタから次の段中の上向きレジスタへの上向きと、２）ある段中の下向きレジスタから前の段中の下向きレジスタへの下向きの２つの方向にデータを送るように働く。レジスタと通信回路は共に、２つのストリームのデータ要素がパイプラインの一方の端から他方の端へ流れる際に通過する経路を提供する。上向きデータ・ストリームはパイプラインの最下段に流れ込み、最上段から流出し、下向きデータ・ストリームはパイプラインの最上段に流れ込み、最下段から流出する。
【００３７】
両方のストリーム用の制御回路は対称的なものである。上向きストリーム用の制御回路は、下向きストリーム用の制御回路と対称的であり、制御中の段の上および下にある段の役割は、明らかに逆のものである。ラベル以外では、どちらが上向きストリームを制御して、どちらが下向きストリームを制御するかに関して制御回路を区別する必要はない。
【００３８】
２つのストリーム上で発生するサイズ、意味、および処理は異なるものでよいが、２つのストリームは共に可動であり、同様に制御することができる。連想メモリや、１つの可動データ・セットおよび１つの比較的固定されたデータ・セットを提供する現在使用中の通常のパイプライン・プロセッサと異なり、カウンタフロー計算パイプラインは、２つの同様に可動のデータ・ストリームの相互作用を可能にする。
【００３９】
カウンタフロー・パイプラインの各段は、必要に応じて比較回路を含むことができる。両方のデータ要素が存在し、状態（Ｆ）である場合、そのような比較回路は上向きフローのデータ要素のすべてまたはある部分を、下向きフローのデータ要素のすべてまたはある部分と比較することができる。どちらかまたは両方のデータ要素が欠けている場合、比較回路は遊休状態のままである。一般に、そのような比較回路が、データ要素の「タグ」部分または「アドレス」部分と呼ばれるデータ要素の一部しか比較しないことは有用である。データ要素の他の部分は比較の結果に応じて様々な方法で処理することができる。大部分の使用法では、各段は、「逆同期比較」の特性が得られるように比較回路を含む。
【００４０】
「一致」の語は、本明細書では比較の成功を示すために使用されているが、比較が多数の形を取れることを理解されたい。「一致」の語は、比較によって、試験中のデータ要素の２つの部分のＩＤをビットごとにシークされることを含意するように思えるが、ビットごとの一致は単なる比較の最も簡単な形であり、２つのデータ・ストリーム間のデータ処理をいつ行うべきかを記述するために使用するための最も簡単なキーワードを提供する。さらに複雑なシステムでは、順方向ストリームのデータ要素のすべてまたはある部分が数学的な意味で、逆のストリームのデータ要素のすべてまたはある部分よりも大きいときにも「一致」が発生する。たとえば、より多い、より少ない、ゼロ、範囲外など、どんな数学演算でも使用することができる。マスクの下の比較など通常のものと、一方のデータ要素中の真のバイナリ・ビットの数が他方のデータ要素中の真のバイナリ・ビットの数を超えた場合に一致を宣言することなど、特殊なものとの両方を含め、どんな種類の論理演算でも使用することができる。一般に、一致は、一方にある要素と他方にある要素の間の特定の関係に関して試験する。当業者なら、「一致」と呼ぶことができる条件の範囲を迅速に拡張し、したがって次の処理を構想することができよう。
【００４１】
通常、上向きストリーム中のデータ要素を下向きストリーム中のデータ要素と比較する目的は、それらのデータ要素の一方または両方に応じ、あるいはそれに影響を与える何らかの動作が必要とされるかどうか、あるいは許可されるかどうかを判定することである。特定の動作は、一方または両方のデータ要素に存在する特定のビット・パターンに応じるものでも、あるいは２つの要素中のビット・パターン間の特定の関係の発生に応じるものでもよい。そのような比較の結果として何らかの動作が必要とされる場合、それを「一致」と呼ぶ。
【００４２】
カウンタフロー計算パイプライン段内での比較の結果として「一致」が見つかったとき、その段は、どちらかまたは両方のデータ・ストリーム中のデータを修正することができる。多数の種類の修正が可能である。特定の形の修正が本発明によって制限されることはない。なぜなら、本発明はそのような修正をすべて含み、あるいは修正をまったく含まないからである。特定の形の修正は、現在の処理タスクのニーズに合うように設計される。
【００４３】
一致があるときに実行すべき１つの簡単な形の修正は、一方のデータ要素または各データ要素中の１つのバイナリ・タグを真状態にすることである。そのようにマーク付けされたデータ要素は、カウンタフロー処理パイプラインを介した流れの終りに達したとき、特殊な処理を受けるものとして選択することができる。一致が発生したときに実行すべき他の簡単な形の修正は、一方のデータ要素の指定の部分を他方のデータ要素の指定の部分にコピーすることである。そのようなコピー動作では、選択された情報が一方のデータ・ストリームから他方のデータ・ストリームに移動することができる。実行すべき他の形の修正は、パイプラインの次の段が一方のデータ要素を無視し、あるいはデータ・ストリームから削除できるように、一致が発生したときに前記データ要素の１つに無効のマークを付けることである。一致があるときに実行すべき他の形の修正は、２つのストリームのデータ要素に対する数学演算または論理演算を含むことができる。当業者には、２つのデータ要素のすべてまたは一部に対して様々な演算が可能であることが明らかになろう。
【００４４】
カウンタフロー計算パイプラインのどんな段でも、他方のストリームのデータ要素を参照せずに、一方または他方、あるいは両方のデータ・ストリームのデータ要素に対して通常のディジタル処理を実行できることも構想される。ある段での計算の形は、他の段で行われる計算の種類に類似するものでも、類似しないものでもよい。これに関しては、段が同じものである必要はない。たとえば、特定の段は順方向ストリームの各データ要素の２つの部分を加算し、同じデータ要素の一部としてその和を記録することができる。そのような動作は、他方のストリームのデータ要素の存在に依存する必要がなく、したがって、計算パイプラインで現在共通的に行われている処理に類似している。他方のストリームの要素に無関係な一方のストリームの要素に対して実行しなければならない特殊な動作があることがある。
【００４５】
いくつかのデータ処理動作は、「一致」があるときしか実行されない。そのような動作は、一致した２つのデータ要素の値に対する数学計算を含むことができる。これらの動作は、一方のデータ要素のデータの他方のデータ要素への代入を含むことができる。これらの動作は、適当な妥当性検査マーカ・ビットの状態を変更することによって、一方または他方のデータ要素中のデータを有効化または無効化することを含むこともできる。当業者なら、非常に広範囲の可能なデータ処理動作が可能であり、それらが異なるタスクに望ましいことを理解されよう。
【００４６】
本発明の非常に有用な特徴は、完全で非冗長な比較を保証できることである。「完全比較」とは、上向きストリームからの特定のデータ要素が下向きストリームからのデータ要素を通過する場合、２つのデータ要素がカウンタフロー計算パイプラインの少なくとも１つの段を同時に占めて、比較が行われることを意味する。そのような２つのデータ要素は、相互に通過する際に必ずある段で出会う。２つのデータ要素が共にカウンタフロー計算パイプラインの同じ段を占めるとき、この段は「一杯」（Ｆ）であり、２つの要素を比較することができる。したがって、完全比較特性によって、一方のストリームのあらゆる要素は、それが通過する他方のストリームの各要素と少なくとも一度だけ比較される。
【００４７】
「非冗長比較」とは、順方向ストリームの各データ要素が逆のストリームの各データ要素と多くて一度だけ比較されることを意味する。本明細書で説明するカウンタフロー計算パイプラインは、すでに他方のストリームのデータ要素に出会った一方のストリームの各データ要素が二度と前記他方のストリームのデータ要素に出会わないようにすることができる。
【００４８】
カウンタフロー計算パイプラインの完全特性と非冗長特性は協力して、一方のストリームの各データ要素が一度だけ他方のストリームの各データ要素に出会うようにすることができる。本明細書で説明するカウンタフロー計算パイプラインの完全特性および非冗長特性（「逆同期比較」）によって、このパイプラインは様々な計算タスクに有用になる。
【００４９】
比較のためにカウンタフロー・パイプラインに提供される制御回路は、相互に逆の方向に流れる２つの別々のパイプラインと、カウンタフロー・パイプラインを区別する。相互に並行であるが逆の方向に流れる２つの別々なパイプラインの場合、上向きに流れるデータ要素は、下向きに流れるデータ要素と共に同じ段を占めることなしに、前記下向きに流れるデータ要素を通過することがある。これが起こる可能性があるのは、２つのデータ要素が、隣接する段を占めており、次いで、一瞬のうちに場所を交換する場合である。２つのデータ要素は、互いを通過したが、実際に相互作用することはできない。カウンタフロー・パイプラインは、これが発生するのを防ぐための特定の回路を含む。
【００５０】
２つのデータ・ストリームのどちらかまたは両方から不要なデータ要素を削除できるようにする本発明の拡張について以下で説明する。削除は、２つのデータ・ストリームの要素間の比較によって一方または他方のデータ・ストリームのデータ要素が古くなる場合に有用である。削除は本発明の同期実施態様でも非同期実施態様でも有効であるが、同期実施態様では「バブル」を導入することができる。
【００５１】
２つのデータ要素のどちらかまたは両方に新しいデータ要素を挿入できるようにする本発明の他の拡張について以下で説明する。新しいデータ要素を一方または他方のストリームに挿入することは、現在のデータ要素に対する計算が次の処理を必要とする新しいデータ要素を生成する場合に有用である。上向きストリーム中のデータ要素に対して行われた計算に応答し、かつその結果として下向きストリームにデータ要素を挿入することがいくつかのアプリケーションで有用であることが分かっている。基本パイプラインが対称的なものなので、もちろん、下向きストリームで発生した事象に応答して上向きストリームにデータ要素を挿入することも可能である。
【００５２】
本明細書で説明するカウンタフロー・パイプラインは、分岐構造として形成することができる。最も簡単な形の分岐構造は簡単な分岐である。分岐よりも下には単一のカウンタフロー・パイプラインしかない。分岐よりも上には、右パイプラインおよび左パイプラインと呼ばれる２つの別々なカウンタフロー・パイプラインがある。このシステムはＹの文字に類似している。当業者なら、カウンタフロー・パイプラインの対称性のために、どんな分岐構造または結合構造を可能にするにも、そのような簡単な分岐の説明で十分であることを認識されよう。上に２つのパイプラインがあり、下に単一のパイプラインがある構造は、「Ｙ」構造を上下逆にしたものに過ぎない。当業者なら、２本よりも多い枝を含む多方向枝および結合が可能であることを認識されよう。
【００５３】
分岐の下から上向きに流れるデータは、分岐の何らかの規則に応じて左または右、あるいはその両方へ送ることができる。そのような規則は、データ要素自体の何らかの顕著な特性を使用してデータ要素を方向付けることができる。たとえば、英語を表す要素を一方のパイプラインに送り込み、フランス語を表す要素を他方のパイプラインに送り込むことができる。２つの出力パイプの代替使用、ランダム選択、どの出力パイプラインがあまりビジーでないかに基づく選択、各パイプを介した各要素の一部の送信の使用を含む他の規則も可能である。
【００５４】
下向きに流れるストリームは分岐で出会う。この場合も、どのようにこれら２つのストリームの要素を単一のストリームとして組み合わせるかについて選択しなければならない。当業者には明らかなように、代替サービス、到着順に基づくサービス、データ内容に基づくサービス、要素の対としての組合せ、相互のデータの連合を含む様々な規則が可能である。どんな特定の分岐でも、それが上向きフローを分割するために使用する規則と、下向きフローを組み合わせるために使用する規則によって特徴付けることができる。
【００５５】
大部分のパイプラインでは、各段を、上向きバウンド・データ用の単一のレジスタと下向きバウンド・データ用の他のレジスタとを有するものとみなすと好都合である。しかし、パイプラインの単一の段が、一方または他方、あるいは両方の方向に進むデータ用の複数のレジスタを有することも可能である。そのようなシステムは、段に存在するいくつかの上向きバウンド・データ値をそれぞれ、各下向きバウンド値とうまく比較できるように、複数の比較が可能でなければならない。
【００５６】
パイプラインの特定の段は、パイプラインの外部からの信号を受け入れることができる。そのような信号は、時刻などの特殊データをパイプラインに送り、あるいはパイプラインの動作を修正することができる。たとえば、特定の段は、特定の計算を行い、あるいは特定のデータを送る前に何らかの外部事象を待つことができる。そのような機構を使用して外部メモリ・システムからデータを受け入れることは特に有用である。
【００５７】
同様に、パイプラインの特定の段は外部装置に信号を送ることができる。したがって、パイプラインの特定の段は、オペレータに特定の条件を警告するように豆電球やブザーなど何らかの物理装置を制御することができる。そのような機構を使用して外部メモリ・システムにデータおよびアドレスを送ることは特に有用である。
【００５８】
パイプラインへのそのような外部接続を一方の側の機能が非常に限られたパイプライン分岐とみなすことができる。しかし、そのような各接続を特殊ケースとみなした方が簡単であることが多い。当業者なら、本明細書で説明する制御システムが広範囲のそのような外部装置を制御するように適応できることを認識されよう。
【００５９】
外部装置はパイプラインのいくつかの段に接続することができる。たとえば、メモリ装置はパイプラインの１つの段から命令を受け取り、答えを他の段に送ることができる。鉄道の本線上の側線（待避線）に類似しているため、そのような接続を本明細書では「側線」と呼ぶ。
【００６０】
側線は、外部プロセスがメイン・パイプラインで、ある段から次の段へデータを移動するのにかかる時間よりも長い時間を必要とするときに常に有用である。側線は、データがメイン・パイプラインに沿って移動している間にそのタスクを実行し、進行中のデータのニーズに一致するようにパイプライン中の適当な点で答えを送る。たとえば、メモリ側線は、メモリ値を必要とするデータ要素がメイン・パイプラインに沿って移動している間に、必要とされる値を外部メモリで探す。同様に、数学側線は、メイン・パイプラインで他の動作が実行されている間に、何らかの難しい数学関数、たとえば除算を計算することができる。そのようなメモリおよび数学側線は、カウンタフロー・パイプラインの比較的高い速度を多数の有用な計算動作のより低い速度に一致させるための機能を提供する。
【００６１】
同期法および非同期法
本発明は、カウンタフロー計算パイプラインの同期実施態様と非同期実施態様を共に包含する。同期実施態様では、データがパイプラインのある段から次の段へ移動する場合、「クロック」と呼ばれる外部タイミング信号が到達したときだけそのように移動する。同期実施態様では、データはクロック信号間で静止したままである。同期実施態様では、データを収容する空間が次の宛先にない場合も、データは静止したままである。同期実施態様では、送信側段と受信側段が、場合に応じてデータを上向きまたは下向きに送るためにどのクロック事象を使用するかに関して合意する。
【００６２】
カウンタフロー計算パイプラインの非同期実施態様では、送信側段と受信側段とが、データがどんな外部クロック信号からも独立に段間で移動すべきであることに合意すると必ず、データはそのように移動する。非同期実施態様では、順方向ストリームの各データ要素は、そのデータ要素用の空間が次の段にでき、そのデータ要素がもはやこの段では必要とされなくなり、かつローカル回路が許可した直後に、順方向に自由に移動する。逆のストリームの各データ要素は、そのデータ要素用の空間が前の段にでき、ローカル回路が許可した直後に、逆方向に自由に移動する。
【００６３】
本発明の非常に有用な態様は、本発明が、データ移動の非同期ローカル制御または非クロック・ローカル制御と共に「逆同期比較」と呼ばれる完全非冗長特性を提供できることである。
【００６４】
【実施例】
図１、図２、図３で、段２０、３０、または４０は上下に重ねられており、データは、このように形成されたパイプラインを介して「上向き」または「下向き」に流れる。この文脈での「上向き」および「下向き」の語は、図中の方向だけを指し、実システム中の実際のフロー方向に偶然類似しているに過ぎない。本発明のこの説明全体にわたって、「上向き」および「下向き」は単に、データ・フローの２つの方向の有用な区別を提供するために使用される。
【００６５】
本発明は、順方向データ・フローおよび逆方向データ・フローを提供するように２方向に通信する１組の類似の段用の制御機構を設けている。最も一般的な形の本発明のブロック図を図１に示す。図１に示したように、段Ｎ、段Ｎ−１、段Ｎ＋１などのラベルの付けられたデータ・パイプライン５０のいくつかの段２０がある。これらのデータ段はデータ経路２２、２４、２６によって２方向に通信する。場合によっては、上下方向の通信は、２４や２６など別々の経路上のものでも、２２で示したように可逆的に使用される単一の経路上のものでも、これらの構成を組み合わせたものでもよい。
【００６６】
これらの段用の制御システム５２は、制御システムと段を接続する制御経路２８中の制御信号によって段と相互作用する。いくつかの制御信号は、制御システムから段へ流れ、段の動作を制御するように働く。他の制御信号は、段の状態または段のデータ内容に関する情報を示すように段から制御システムに流れる。
【００６７】
図１の構成が図示のためのものに過ぎないことを認識されたい。図１に示したデータ経路のうちのいくつかをなくすことができ、いくつかのデータ経路は他のデータ経路よりも多くの情報を運ぶことができ、図示していない特殊データ経路を含めることができる。本発明は、当業者には明らかな多数のそのような変形例を構想するものである。
【００６８】
制御システム５２は段を介した規則正しいデータ・フローを提供する。データ要素は、段間で両方向に流れることができ、別々の時に流れることも、あるいは異なる段間で同時に流れることもできる。
【００６９】
制御システム５２は、データ経路を介して一方の方向に流れるデータと他方の方向に流れるデータとの逆同期比較を行う。
【００７０】
他の形の本発明では、制御システムが段自体に分散される。図２に示したように、パイプラインは幅の広い矢印で示したデータ経路３２および３６を含む１組の類似の段３０と、それらの間を流れる、幅の狭い矢印で示した制御経路３４とで構成することができる。図２では、上向きおよび下向きのデータ・フローのために別々のデータ経路が示されている。図３では、両方向のデータ・フローのために共通データ経路４２が使用されている。図１、１Ｂ、１Ｃに示したように、２０、３０、または４０として識別され、段Ｎ、段Ｎ−１、段Ｎ＋１などのラベルの付けられたパイプラインのいくつかの段がある。
【００７１】
図２に示したように、段は、データ経路３２によって上向きに、データ経路３６によって下向きに通信する。データ経路は、多数のデータ・ビットを平行に運べることを示すように二重矢印で描かれている。上向きストリーム用のデータ要素は、下部入力ポート３１で前記ストリームに入り、上部出口ポート３３から出る。下向きストリーム用のデータ要素は、上部入力ポート３５で前記ストリームに入り、下部出口ポート３７から出る。
【００７２】
図２に示したデータ通信経路に平行にかつこの経路の他に制御経路３４もある。この経路は、制御信号が段の動作を制御するために各方向に流れることができることを示すように幅が狭い二重矢印で示されている。二重矢印は、制御信号が上向きおよび下向き両方の別々の経路を流れることを示すものである。制御経路は、各制御がデータ通信経路で情報の規則正しいフローを提供できるように隣接する段に関する情報を各段中の制御システムに示す。
【００７３】
後で、実施態様によっては、上向きおよび下向きのデータ移動が異なる時に行われなければならないため、同じデータ経路を使用できることが分かる。場合によっては、図３に示したように、上向き通信にも、下向き通信にも、同じデータ経路４２を使用することが望ましい。この場合、上向きに流れるデータ要素にも、下向きに流れるデータ要素にも、単一の双方向データ経路４２が使用される。制御経路４４は段間で制御信号を伝達する。
【００７４】
カウンタフロー計算パイプラインの単一の段の構成要素を図４に示す。各段は、上向きデータ・ストリームのデータ要素を収容するためのメモリ要素、たとえばレジスタ６０と、下向きデータ・ストリームのデータ要素を収容するための第２のレジスタ６６とを備えている。レジスタ６０および６６はそれぞれ、各段をそれに隣接する段に接続するデータ通信経路３２および３６に接続されている。データ要素は、これらの通信経路に沿ってある段中のレジスタから隣接する段中のレジスタに流れる。レジスタ６０および６６のサイズの差によって示唆されるように、２つのレジスタは、同じ量の情報を保持する必要も、同じ数のビットを保持する必要もない。
【００７５】
単一の段中の各レジスタは、データ要素を含むことができ、あるいは空であってもよい。図４で構想される実施例では、各レジスタ用のマーカ・フリップ・フロップ６２および６４が、レジスタが一杯であるか、それとも空であるかを示すために使用されている。マーカ・フリップ・フロップ６２は、１または０にセットされた場合、それぞれ、上向きレジスタ６０中にデータ要素があること、あるいはないことを示す。マーカ・フリップ・フロップ６４は、１または０にセットされた場合、それぞれ、下向きレジスタ６６中にデータ要素があること、あるいはないことを示す。
【００７６】
これら２つのマーカ・フリップ・フロップの状態は協力して、段の４つの異なる状態を示す。このうちで最も容易に挙げられるのは、それぞれ、２つのマーカ・ビットが共に１に、あるは０にセットされることによって示される「一杯」（Ｆ）および「空」（Ｅ）である。他の２つの状態は、単一のデータ要素だけが存在するとき、すなわち、段が「半分充填されている」ときに発生し、下向きに移動するデータ要素が存在するか、それとも上向きに移動するデータが存在するかに応じてそれぞれ（Ｄ）および（Ｕ）と呼ばれる。
【００７７】
カウンタフロー計算パイプラインの実施例によっては、レジスタ６０および６６の空状態および一杯状態をそれぞれマーカ・フリップ・フロップ６２および６４以外の機構で判定することができる。たとえば、米国特許第４８３７７４０号に記載されたように、非同期システムでは、レジスタの一杯状態または空状態を示す信号をレジスタの２つの制御信号の排他的論理和として導くことができる。この形のマーカはカウンタフロー計算パイプラインで使用することもできる。
【００７８】
各段中の制御回路６８はレジスタ６０および６６と、フリップ・フロップ６２および６４とに接続されている。カウンタフロー計算パイプラインの各段は、図５に示した比較回路を含むこともできる。この図で、図４の上向きレジスタ６０は２つの部分６０ａおよび６０ｂに分割され、図４の下向きレジスタ６６は２つの部分６６ａおよび６６ｂに分割されている。各レジスタの一方または両方の部分では、通信経路入力または比較計算ブロック７２からデータを取れるように、マルチプレクサ７０および７６が入力に接続されている。レジスタ、マルチプレクサ、および外部制御信号はすべて、制御回路６８によって管理される。大部分のアプリケーションでは、あらゆる段が、カウンタフロー・パイプラインに対して可能な「逆同期比較」特性を提供するために少なくとも最小比較回路を含む。
【００７９】
図５に示したように、比較計算ブロック７２の一部である比較回路は、上向きレジスタ６０の一部６０ａを下向きレジスタ６６の一部６６ａと比較することができる。もちろん、比較は、必要に応じて、これより多い、または少ない量を包含することも、あるいは場合によってはどちらかのレジスタのすべてを包含することもできる。図５で特定の部分を示したのは図示のために過ぎない。図５で、このような比較回路は、それぞれデータ経路７１および７７に沿って提供される各レジスタ中の情報の約半分に作用するものとして示されている。しかし、本発明の様々な実施例で、このような回路は、現在の計算タスクに応じてレジスタで利用可能なデータのいくらかを利用することができる。
【００８０】
比較計算ブロック７２中の比較回路は、何らかの数学比較または論理比較を実行し、１つまたは複数の「一致」条件を検出することができる。これらの一致条件は制御経路７６に沿って制御回路に報告される。これらの一致条件は、２つのレジスタ内の何らかのデータ・フィールドのビットごとの比較に基づいて計算することができる。たとえば、上向きバウンドの英語の第１文字が下向きバウンド英語の第１文字に一致した場合に一致を宣言することができる。一方のレジスタの何らかのフィールドの数学値が他方のレジスタ中のフィールドの値を超えた場合に一致を宣言することもできる。当業者には、異なる目的のために検出できる様々な「一致」条件が認識されよう。
【００８１】
異なる目的のために複数の一致条件をもつことも可能であり、時には有用である。ある種の一致では、上向きバウンド・データ要素が修正され、他の種類の一致では、下向きバウンド・データ要素が修正される。修正の量および種類は、検出された特定の種類の「一致」によって制御することができる。
【００８２】
このような一致条件の制御下で、レジスタの内容を修正するための回路を活動させる。図５で、このような修正回路は比較計算ブロック７２からのデータ出力を含む。このブロックからの出力データは、その入力のどんな計算可能な関数でもよい。したがって、データ経路７５に沿って上向きバウンド・データ経路中のマルチプレクサ７０に送られる値は、上向きレジスタだけのデータ値または下向きレジスタだけのデータ値の任意の組合せでも、あるいは両方のレジスタのデータ値の何らかの組合せでもよい。同様に、データ経路７３に沿って下向きバウンド・データ経路中のマルチプレクサ７６に送られる値は、上向きレジスタだけのデータ値または下向きレジスタだけのデータ値の任意の組合せでも、あるいは両方のレジスタのデータ値の何らかの組合せでもよい。
【００８３】
具体的には、図５に示した修正回路は、一方のレジスタから他方のレジスタのすべてまたは一部にデータをコピーできる可能性を含む。マルチプレクサ７０が上向きバウンド・レジスタ６０の一部６０ａにしか信号を供給しないことは、実際の回路をそのように制限するものではない。当業者なら、そのようなレジスタの固定部分６０ｂおよびマルチプレクサによって供給される部分６０ａの相対サイズが、特定のアプリケーションのニーズを満たすように任意に選択できることを直ちに認識されよう。同様に、図５で、上向きバウンド・レジスタの同じ部分６０ａがデータ比較計算回路７２への入力としても、修正すべき部分としても使用されているように見えるが、これは実際の設計を制限するためのものではない。当業者なら、上向きバウンド・レジスタ６０のどんな部分でもデータ計算比較回路への入力として使用でき、レジスタ６０の他のどんな部分でもマルチプレクサに接続でき、これら２つの部分を重ね合わせる場合、どんな所望の方法ででもそれを行えることを認識されよう。
【００８４】
図５に示した修正回路は、１つのレジスタだけの内容に対して実行できる様々な特殊動作を表す。図５の回路は、２つのレジスタの内容を組み合わせ、その結果それらの一方または両方を修正する回路も表す。当業者なら、そのような修正回路がいくつでもカウンタフロー処理パイプラインに含められることを直ちに認識されよう。図示したものは、使用できる様々な可能な計算構成を示すためのものに過ぎない。
【００８５】
カウンタフロー計算パイプラインの段の動作は制御システムによって制御される。この制御システムは、図４および図５中に６８として示したように、パイプラインの特定の段に対してローカルであってよい。
【００８６】
基本カウンタフロー計算パイプラインに好ましい制御システムは、図６を参照すると最もよく理解することができる。この状態図中の５つの円は、カウンタフロー計算パイプラインの単一の段が使用中に通過できる５つの主な状態を表す。これらの主な状態のうちで、４つ、すなわち（Ｆ）、（Ｅ）、（Ｄ）、（Ｕ）についてはすでに述べた。これらの名前は完全に任意のものである。もちろん、使用した特定の名前は本発明の動作とは無関係である。
【００８７】
図６の矢印は、説明中の単一の段の基本状態の可能な変化を表す。したがって、たとえば、「ｇｅｔ  ｕｐ」のラベルが付けられた矢印で示した新しい上向きバウンド・データ要素が到着すると、状態は（Ｅ）から（Ｕ）に、あるいは（Ｄ）から（Ｆ）に変化することができる。同様に、「ｇｅｔ  ｄｏｗｎ」のラベルが付けられた矢印で示した新しい下向きバウンド・データ要素が到着すると、状態は（Ｅ）から（Ｄ）に、あるいは（Ｕ）から（Ｆ）に変化することができる。同様に、「ｐａｓｓ  ｕｐ」のラベルが付けられた矢印で示した上向きバウンド・データ要素が離れると、状態は（Ｕ）から（Ｅ）に変化することができる。同様に、「ｐａｓｓ  ｄｏｗｎ」のラベルが付けられた矢印で示した下向きバウンド・データ要素が離れると、状態は（Ｄ）から（Ｅ）に変化することができる。
【００８８】
図６に示した状態間の遷移については一部を上記で説明した。下記は到着するデータの完全な説明である。空（Ｅ）のとき、カウンタフロー計算パイプラインの各段は、どちらかのデータ・ストリームからデータ要素を得ることができる。したがって、図６で空（Ｅ）状態になる状態遷移は２つある。これらは以下のとおりである。１）段は、上向きデータ要素を得た場合は状態（Ｕ）に入る。２）段は、下向きデータ要素を得た場合は状態（Ｄ）に入る。図に示したように、段は、（Ｄ）状態から、上向きに流れるデータ要素を引き続き得て一杯（Ｆ）になることができ、同様に、（Ｕ）状態から、下向きに流れるデータ要素を引き続き得て同様に一杯（Ｆ）になることができることに留意されたい。空状態から、上向きに流れるデータ要素と下向きに流れるデータ要素が同時に到着し、したがってシステムが状態（Ｅ）から直接状態（Ｆ）に移動する可能性もある。この可能性は、その動作が２つのデータ要素が別々に到着することによって包摂されるので、図では、点線として示されている。図６は、段が一杯（Ｆ）にならない限り、まだ占められていないどちらかまたは両方のレジスタにデータ要素を受け入れることができることを忠実に報告している。
【００８９】
データ要素が段から離れることはさらに制限される。図６で状態（Ｆ）からは（Ｃ）以外のどの状態に至る矢印もない。したがって、下向きに流れるデータ値しか含まない場合、段は状態（Ｄ）であり、その要素データを送って状態（Ｅ）に移る。同様に、段は上向きに流れるデータ値しか含まない場合、状態（Ｕ）であり、そのデータ要素を送って状態（Ｅ）に移る。両方のデータ要素を有する場合、段は状態（Ｆ）であるが、比較が完了して状態（Ｃ）になるまでどちらのデータ要素も送ることができない。図６の状態図は、段が状態（Ｆ）に達した後、状態（Ｃ）に達するまで、データ要素が離れることを禁止されることを示す。
【００９０】
パイプラインの適切な機能を理解するには、「Ｃｏｍｐｌｅｔｅ」を表す（Ｃ）と呼ばれる図６の状態図の第５の状態を理解する必要がある。
【００９１】
状態図の状態（Ｆ）から状態（Ｃ）への遷移は、２つのデータ要素に対する比較動作を含む。状態（Ｆ）に達すると、同時に両方のデータ要素が存在し、それらを比較しなければならない。比較が完了して、「一致」条件のどれかによって必要とされるあらゆる動作が完了すると、システムはＣｏｍｐｌｅｔｅの場合と同様に状態（Ｃ）に達したと言われ、データ要素は自由に離れることができる。本発明の好ましい実施例はこれらの状態遷移を忠実に実施する。これらの状態遷移をうまく実施すると、カウンタフロー・パイプラインのある種のアプリケーションで非常に有用な「逆同期比較」と呼ばれる完全非冗長比較特性が得られる。
【００９２】
カウンタフロー計算パイプラインの段がどの状態を占めるかは３つのフリップ・フロップによって示すことができ、そのうちの２つは図４に示されている。図４に示した２つのマーカ・ビット６２、６４は、２つのレジスタが占有されているかどうかを示すことができる。Ｃｏｍｐｌｅｔｅ状態（Ｃ）に到達したかどうかを報告するには第３のインディケータが必要である。段の状態を示すために使用できる多数の機構がある。たとえば、本発明の非同期実施例では、後述するように、いくつかの制御信号から状態を導くことができる。当業者なら、５つの基本状態を区別するための多数の多様な機構を認識されよう。さらに、後で分かるように、５つの基本状態はそれぞれ、さらに多数の二次状態に分割することができる。カウンタフロー計算パイプラインのある種のアプリケーションに重要なことは、これら５つの基本状態が異なるものであり、かつカウンタフロー・パイプラインが「逆同期比較」特性を提供できるように、それらの状態間の遷移が図６に示した特性を有することである。
【００９３】
図６の状態図に示した規則に従ってデータを規則正しく送るために、カウンタフロー計算パイプラインの各段ごとの制御システム中に、あるいは段間に特殊回路を含めることができる。図６の状態図がより簡単なものである場合、データの上向きフローおよび下向きフロー用の別々の制御を使用することができる。しかし、図６の状態図では、各段は、一杯になった後、データをどちらかの方向に送る前に、一致または比較と、それに伴うデータ修正動作とを完了しておかなければならない。当業者なら、多数のそのような制御回路を構想することができる。それらのうちの２つを以下で説明する。そのうちの１つは同期実施例用のものであり、１つは非同期実施例用のものである。
【００９４】
同期制御
段間の通信に特定の焦点が当てられた図７に同期形の制御を示す。各段は、図に示した発信回路８０および８２を使用して隣接する段にそれ自体の存在を通知する。これらの発信回路はそれぞれ、スラッシュと、報告中の段階の状態を完全に説明するには３ビットの情報を提供することが好ましいことを示すための数字「３」でマーク付けされている。クロック７８によって提供されるクロック・パルス間の間隔中に、各段は、それ自体とそれに隣接する段の間にある通信経路でデータが移動すべきかどうかを判定し、データが移動すべきである場合に、転送が上向きであるべきか、それとも下向きであるべきかを判定するのに必要なすべての情報を有する。２つの隣接する段のそれぞれには、可能な５つの状態の積に対応する２５のケースしかない。２つの段の組合わされた状態は、それらの別々の状態を表し、下の段の状態を最初に記録する、２つの文字で指定される。したがって、たとえば（Ｅ、Ｄ）は、下の段が空であり、上の段が下向きバウンド・データを有することを意味する。
【００９５】
これらの２５の可能な状態対のうちで、上向きデータ・フローが可能なのは状態対（Ｕ、Ｅ）、（Ｃ、Ｅ）、（Ｕ、Ｄ）、および（Ｃ、Ｄ）だけである。上の段中の下向きバウンド・データと、下の段中の利用可能な上向きバウンド・データ用の空間を有するのはこれらの状態だけでなので、上向きフローが可能なのはこれらの状態だけである。同様に、下向きデータ転送が可能なのは状態対（Ｅ、Ｄ）、（Ｅ、Ｃ）、（Ｕ、Ｄ）、および（Ｕ、Ｃ）だけである。状態対（Ｕ、Ｄ）では、上向きまたは下向きデータ転送が可能であるが、一方のデータ移動または他方のデータ移動を選択しなければならない。両方のデータ移動を同時に可能にすると、上向きバウンド・データ要素と下向きバウンド・データ要素は場所を交換し、どちらかの段で比較されることなしに進むおそれがある。これは、パイプラインが完全比較を行うことを妨げ、したがって「逆同期比較」特性を破壊する。
【００９６】
次いで、同期制御は、隣接する段の組合わされた状態に基づいてデータをいつ移動するかを決定することができる。ケース（Ｕ、Ｄ）では、両方の段が同じ決定を下さなければならない。その決定が、常にデータを上向きに送るか、常にデータを下向きに送るか、またはそれらを交互に選択するか、あるいは他の何らかの規則に従うかである制御を設計することができる。両方の段が規則に合意する限り、どんな規則でも機能する。
【００９７】
非同期制御
本発明の非同期実施例はいくぶんさらに複雑である。基本的な違いは、図６の状態図に固有のものである。段は状態（Ｄ）から下向きにデータを送ることができるが、上向きデータ要素が到着した後、それによって段は状態（Ｆ）になり、もはや下向きバウンド・データを送ることができなくなる。したがって、制御システムは、他のデータ経路で他のデータ要素が非同期的に到着したときにあるデータ要素を送るのが妥当かどうかを明確に決定する準備をしなければならない。この決定は、段に隣接する通信経路を下向きバウンド方向に使用すべきか、それとも上向きバウンド方向に使用すべきかに関する決定である。
【００９８】
この必要を理解すると、必要とされる制御を理解するのがより簡単になる。必要とされる決定を下す１つの方法は、上向きバウンド・データと下向きバウンド・データとが衝突した場合に明確な答えを提供するための各通信経路をもつアービタ回路を置くことである。そのような衝突は（Ｕ、Ｄ）状態、すなわち、同期制御の場合と同様に、下の段が上向きに通信することができ、上の段が下向きに通信することができるときに発生する。しかし、非同期システムは、優先順位またはサービス順序だけに基づいてデータをどの方向に移動するかを決定することはできない。最近データがまったく通過しておらず、その場合に、上向きバウンド通信および下向きバウンド通信を求める要求が突然、ほとんど同じ瞬間に到着することがあるので、この決定はより複雑である。
【００９９】
非同期システムの当業者は、ほとんど同時に到着した互いに衝突する要求は慎重に扱わなければならないことをよく理解している。この種の衝突に対処するアービタ回路は当技術分野で周知である。適切なアービタ回路は、Ｃｈａｒｌｅｓ  Ｌ．  Ｓｅｉｔｚ著の「Ｉｄｅａｓ  ａｂｏｕｔ  Ａｒｂｉｔｅｒｓ」（雑誌、Ｌａｍｂｄａ、１９８０年第１四半期）または米国特許第４３９８１０５号に記載されている。
【０１００】
図８は、好ましい非同期設計のシステム・ブロック図を示す。信号がどちらの方向に流れるべきかに関するあらゆる衝突を解決するためのアービタを組み込んだ「ＣＯＰ」８９が各段対の間にある。段は、制御経路８４および８５に沿ってその希望をＣＯＰを示す。これらの制御経路は、スラッシュと、図６の状態に対応して少なくとも３つの状態ビットを示さなければならないことを示すための数字３とでマーク付けされている。ＣＯＰは、アービタを使用して段間のデータの流れを方向付け、次に上向き通信経路３２を使用すべきか、それとも下向き通信経路３６を使用すべきかを、通信経路８６および８８を介して各段に通知する。ＣＯＰは実際のデータ・フローに参加する必要がなく、単に、データを上向きまたは下向きに移動する許可を隣接する段に与える。送信側と受信側はデータ経路３２および３６を使用してデータを伝達し、受信側と送信側の間には、データ・フローの細部を制御するためのあらゆる制御経路が必要である。図８では、上向きデータ・フローと下向きデータ・フローの間の決定を下すのに必要とされる制御経路しか図示されていない。選択されたデータ経路３２または３６に沿ってデータ・フローを制御するには、図示していない追加制御経路が必要である。
【０１０１】
制御システムの一実施例はＣＯＰとの間で以下の信号を使用する。これらの信号は、前記で引用した論文Ｍｉｃｒｏｐｉｐｅｌｉｎｅｓに記載された事象信号であり、図１３に見ることができる。
下向き制御経路８４で：
ＡＵ？  自分が、上向きに流れるデータ要素を受け入れることができる。
ＰＤ？  自分が、下向きに流れるデータ要素を送ることができる。
ＣＤ    自分の制御システムは他の通信の準備ができている。
上向き制御経路８５で：
ＰＵ？  自分が、上向きに流れるデータ要素を送ることができる。
ＡＤ？  自分が、下向きに流れるデータ要素を受け入れることができる。
ＣＵ    自分の制御システムは他の通信の準備ができている。
ＣＯＰからの出力：
ＧＵ！  相手が、上向きに通信することができる（制御線８６）
ＧＤ！  相手が、下向きに通信することができる（制御線８８）
【０１０２】
名前に「？」が含む信号と、ＣＤ信号およびＣＵ信号とは、２つの段が通信する準備ができていることをＣＯＰに示す。ＣＯＰは、どちらの方向に通信を行うかを決定し、名前に「！」を含む信号によって、どうすべきかを２つの段に通知する。これらの信号の制御下で段はその動作をうまく実行することができる。
【０１０３】
当業者なら、そのような設計で様々な通信プロトコルおよび機構が可能であることを認識されよう。たとえば、米国特許第４８３７７４０号で構想されたようにデータの通信は簡単な制御「事象」を伴うことができる。「四相」制御システムを使用することもできる。図８は上向きに流れるデータと下向きに流れるデータ用の別々のデータ経路を示すが、データは一度に１つの方向にしか流れないので、共通の１組の可逆ワイヤをこの通信のために共用することができる。同様に、通信は、順次通信として一度に１ビットずつ、あるいはバイト単位で、各部分ごとに行うこともできる。そのような順次化または部分順次化は、必要とされるデータ・ワイヤの数を減らすために選択できるが、もちろん、それによって通信は低速になる。
【０１０４】
システムは、完全状態（Ｃ）に達する前にデータ要素が離れるのを妨げることが好ましい。この制限は、追加完了信号または「自由」信号をＣＯＰに提供することによって適応させる。ＣＯＰは、２つの段が共に他の通信事象の準備ができていることを宣言した場合だけ通信する許可を与える。図８に示した制御経路８４および８５の一部であるＣＤ信号およびＣＵ信号は、この情報をＣＯＰに提供する。ＣＯＰは、「？」信号を適当に組み合わせることによって要求されたときだけ、およびＣＯＰ自体が受信したＣＤ信号およびＣＵ信号が、両方の段が他の通信動作の準備ができていることを示すときだけ、データが通過できるようにする。
【０１０５】
ＣＯＰの動作
図８のＣＯＰは、アービタを使用して実施することができる。次に、アービタの動作について説明する。図９は、使用できるアービタの状態図である。１ないし８と呼ばれる８つの状態がある。これらの状態の間に、Ｒ１、Ｒ２、Ｇ１、Ｇ２、Ｃと呼ばれる１６個の遷移がある。アービタの動作は以下のとおりである。アービタは、いつでも、あるいは場合によっては、まったく同時に到着できる要求信号Ｒ１およびＲ２に応答して、サービスを１回だけ許可する。アービタはＧ１出力またはＧ２出力（両方のことはない）上で信号を送ることによって、サービスを許可したことを示す。要求が衝突する１つのケースでは、状態４を離れ、Ｇ１信号を生成するか、それともＧ２信号を生成するかを決定するのに調停が必要とされる。当業者に周知の特殊回路は、そのような決定を明確に下し、不安定状態が終わるまで決定の発表を延期することによって不安定状態によって引き起こされる不確実性をなくす。
【０１０６】
図１０は、この形のアービタをどうしたらＣＯＰ回路８９に含めることができるかを示す。３つのＭｕｌｌｅｒ  Ｃ要素９２、９４、９６は図のように着信制御信号を組み合わせる。Ｍｕｌｌｅｒ  Ｃ要素９２は、ＡＵ？信号とＰＵ？信号を組み合わせてアービタへのＲ１要求を形成する。この組合せは、アービタが許可すればデータが上向きに流れることができることを示す。同様に、Ｍｕｌｌｅｒ  Ｃ要素９６は、ＡＤ？信号とＰＤ？信号を組み合わせてアービタへのＲ２要求を形成する。この組合せは、アービタが許可すればデータが下向きに流れることができることを示す。これら２つのＭｕｌｌｅｒ  Ｃ要素の入力上のバブルは、最初、パイプラインが完全に空のときに、あらゆる段がデータ入力を受け入れる準備ができていることを示す。
【０１０７】
Ｍｕｌｌｅｒ  Ｃ要素９４は、ＣＤ信号とＣＵ信号を組み合わせてアービタ用のＣ信号を提供する。この組合せは、両方の段が他の通信事象の準備ができていることをアービタに示す。
【０１０８】
段内の非同期制御
段内の簡単な形の非同期制御を図１１に示す。この図で、上向きバウンド・レジスタＵＲＥＧ６０および下向きバウンド・レジスタ６６は、米国特許第５１８７８００号に記載された遷移制御レジスタとして実施される。そのようなレジスタは、２つの制御入力上の事象によって制御される。図１１のレジスタ６０および６６では、これら２つの入力が区別されている。なぜなら、それらの一方がボックスの辺から入り、他方が隅から入るからである。ボックスの辺から事象が入ると、レジスタはその時にそれ自体を通過しているあらゆるデータを取り込む。データが取り込まれると、ボックスの遠い辺で事象出力が生成される。したがって、たとえば、図１１の左下にあるＡＵ！入力上に事象が着信すると、ＵＲＥＧは１）Ｕｉｎデータ入力で提示されるデータを取り込み、したがってＵｉｎの値の以後の変化がＵｏｕｔ出力でのデータ出力に影響を及ぼすのを防ぎ、２）次いでＰＵ！出力制御経路上で出力を生成する。
【０１０９】
ボックスの隅に入るように示した制御入力上の事象によって、レジスタはデータに対する保持を解放して透過的になる。したがって、たとえば図１１の左上にあるＰＵ！入力に入力事象が到着すると、ＵＲＥＧ６０は透過的になり、続いてＵｉｎデータ入力からＵｏｕｔデータ出力へデータをコピーする。
【０１１０】
図１１に示した制御信号の動作の理解を助けるために、事象発信の重要な特性を簡単に検討する。この要約は参考文献では拡張された形で与えらえれている。この形の発信では、ワイヤの電気状態の変化が事象を発信するが、変化の方向は、ＨＩからＬＯでも、ＬＯからＨＩでも良く、重要ではない。図１１で１０１などの円として表された通常の排他的論理和ゲートＸＯＲは、この形の発信用の「ＯＲ」機能を提供する。というのは、ＸＯＲ回路が、どちらかの入力のあらゆる状態に対して、その出力状態を変更するからである。図１１の図を読む際に、円として描かれたＸＯＲのどちらかの入力に到着した事象が直ちに出力に送られることを想起すると有用である。
【０１１１】
１０２などのＭｕｌｌｅｒ  Ｃ要素は事象用のＡＮＤ機能を提供する。Ｍｕｌｌｅｒ  Ｃ要素の出力状態は、両方の入力がＨＩになったときだけＨＩに変化し、両方の入力がＬＯになった後だけ再びＬＯに変化する。１つの入力がＨＩであり、他方の入力がＬＯである場合、Ｍｕｌｌｅｒ  Ｃ要素はその前の状態を想起して保持する。したがって、事象がＭｕｌｌｅｒ  Ｃ要素から出力されるには、第１の入力上の事象入力と第２の入力上の事象入力が共に必要である。図１１の図を読む際に、Ｍｕｌｌｅｒ  Ｃ要素１０２からの出力事象には、前記要素の２つの入力端子のそれぞれの入力事象、すなわち、２つのＸＯＲ要素１０１および１０３の出力としての入力事象が必要であることを想起すると有用である。
【０１１２】
第３のタイプの事象制御装置のセレクタ１０７を図１１に示す。この装置は、下部端子上で受け取る入力の値に応じて、左側の入力端子から、「ｔ」および「ｆ」と呼ばれる２つの右側の端子のうちの１つへ入力事象を送る。この機能を実行するのに適した回路は当業者に周知である。セレクタ１０７は、ＭｕｌｌｅｒＣ要素１０２から事象を得ると、ＸＸと呼ばれるワイヤに接続されたｔ出力、またはＹＹと呼ばれるワイヤに接続されたｆ出力上で出力事象を生成する。セレクタがどちらの出力を選択するかは、「ｒｅｇｉｓｔｅｒ  ｉｓ  ｆｕｌｌ」と呼ばれる信号が真であるか、それとも偽であるかに依存する。この信号はＵＲＥＧにデータが存在するかどうかを報告するように生成される。
【０１１３】
次に、図１１の制御回路の動作について説明する。この段よりも下のＣＯＰによって通信が１方向にしかできないことを想起されたい。選択された方向は、図１３に関して説明するように、図１１の回路へのＡＵ！入力またはＰＤ！入力によって、この制御回路に示される。したがって、下の段との各通信ごとに、２つの入力ＡＵ！およびＰＤ！のうちの１つしか到着しない。ＸＯＲ回路１０３は、その出力が、下の通信経路で通信が行われたことを示すように、これらの事象を組み合わせる。同様に、この段よりも上のＣＯＰの動作のために、２つの入力事象ＰＵ！およびＡＤ！のうちの１つしか発生することができない。したがって、ＸＯＲ回路１０１がこれらの事象を組み合わせるので、この回路の出力は、上の通信経路上で通信が行われたことを示す。したがって、Ｍｕｌｌｅｒ  Ｃ要素１０２からの出力事象は、上の通信事象と下の通信事象が共に発生したことを示す。
【０１１４】
空（Ｅ）状態から始まる図１１に示した段が与えられている場合、ＭＵｌｌｅｒ  Ｃ要素の出力は段の状態に関する多量の情報を提供する。具体的には、ＭＵｌｌｅｒ  Ｃ要素出力が、この段よりも上と下の両方で通信が行われたことを示すので、段は状態（Ｅ）または状態（Ｆ）でなければならない。段は、以下の３つの状況では状態（Ｅ）になる。１）以前に状態（Ｅ）であり、上向きデータ要素が下および左上から到着した。２）以前に状態（Ｅ）であり、下向きデータ要素が上および左下から到着した。３）以前に状態Ｃ）であり、両方のデータが、１つは上向きに、１つは下向きに離れた。段は、以下の３つの状況では状態（Ｆ）になる。４）以前に状態（Ｅ）であり、上向きデータ要素と下向きデータ要素が共に、一方は上から、他方は下から到着した。５）以前に状態（Ｆ）であり、上向きデータ要素が離れ、他のものと置換された。６）以前に状態Ｆ）であり、下向きデータ要素が離れ、他のものと置換された。
【０１１５】
セレクタ１０７は、一杯状態（Ｆ）に対応するものと空状態（Ｅ）に対応するものとにＭｕｌｌｅｒ  Ｃ要素１０２の出力事象を分離する。ＹＹと呼ばれるワイヤ上の事象は空状態に達したことに対応し、ＸＸと呼ばれるワイヤ上の事象は一杯状態に達したことに対応する。一杯状態に達したときは常に、段は図５で説明したＣＯＭＰのラベルが付けられたｌｏｚｅｎｇｅ  １０５によって示される一致計算プロセスを実行すべきである。このプロセスは黒い線で示したように、両方のレジスタからのデータを使用する。ＣＯＭＰプロセスが終了するとき、段は完全状態（Ｃ）に達している。ＣＯＭＰ  ｌｏｚｅｎｇｅ  １０５の制御出力は、ＣＵ信号およびＣＤ信号を生成するＸＯＲ回路１０６に接続されている。これらの信号は、段が次の通信事象の準備ができていることを報告する。
【０１１６】
分岐
図１２は、分岐するカウンタフロー・パイプラインのブロック図である。パイプラインの段Ｎの真上に分岐点がある。図２のように以前に段Ｎよりも上の位置を占めていた段Ｎ＋１の場所に、この場合は、Ｎ＋１（Ａ）およびＮ＋１（Ｂ）の２つのそのような段があることに留意されたい。
【０１１７】
分岐点では、上向きデータ経路、下向きデータ経路、および制御経路の修正が必要である。分岐点で、それよりも上の２つのパイプラインで上向きデータ・フロー経路を供給するように上向きデータ・フロー経路１１４が分割する。分岐点で、２つの下向きデータ・フロー経路３６Ａおよび３６Ｂは、いくつかの方法のうちの１つで組み合わせられる。図１２には、マルチプレクサ１１０を使用して単一の下向きデータ・フロー経路３６を分岐点よりも下に供給することを示した。しかし、３６Ａおよび３６Ｂからのデータが、１）加算、２）連結、３）ブール結合、４）図１２に示した選択を含むが、これらに限らない任意の論理的な方法で組み合わせることができることを認識されたい。
【０１１８】
分岐点よりも上および下からの制御信号は、前記点よりも上および下にある段の動作を制御する制御ブロック１１２で組み合わせられる。
【０１１９】
分岐点では異なる制御回路が異なる動作を生成する。特定の制御回路を特徴付けるには、前記制御回路が上向きバウンド・データおよび下向きバウンド・データをどのように扱うかを検討しなければならない。従来、上向きバウンド・データを交互に２つの上向きバウンド経路に方向付けること、上向きバウンド・データを両方の経路に方向付けること、データ自体の何らかの特性に応じて上向きバウンド・データを一方または他方の経路に方向付けること、上向きバウンド・データを自由に受け入れるどちらかの経路に前記データを方向付けることを含むいくつかの可能な変形例が議論されている。非同期実施態様では、この最後の方法では調停が必要である。
【０１２０】
下向きフローを組み合わせることはわずかにさらに複雑にである。非同期実施態様では、上からのデータを組み合わせる大部分の形態で調停が必要である。調停を必要としない１つの形態は、両方の下向きバウンド経路からのデータ要素を単一のより大きな下向きバウンド・パッケージとして組み合わせて、段Ｎ＋１（Ａ）からも段Ｎ＋１（Ｂ）からもデータが利用可能になるまで待機する。他の方法は、データを交互に、あるいは到着順に組み合わせる。当業者なら、様々な組合せ手法のどれでも可能であることを直ちに理解されよう。
【０１２１】
大部分のパイプラインでは、上向きバウンド・データ用の単一のレジスタと下向きバウンド・データ用の他のレジスタとを有するものと各段をみなすと好都合である。しかし、パイプラインの単一の段が、１方向または他方向、あるいは両方向に進むデータ用の複数のレジスタを有することも可能である。そのようなシステムは、段中に存在するいくつかの上向きバウンド・データ値をそれぞれ、各下向きバウンド値とうまく比較できるように、複数の比較ができなければならない。
【０１２２】
本明細書で説明するカウンタフロー・パイプラインはいろいらな方法が利用できる。このうちの特定の１つは、本出願と同じ日に出願され、本出願人に譲渡され、引用によって本明細書に合体された「Ｃｏｕｎｔｅｒｆｌｏｗ  Ｐｉｐｅｌｉｎｅ  Ｐｒｏｃｅｓｓｏｒ」と題する関連特許出願に記載されている。本明細書で説明するカウンタフロー・パイプラインを使用できる他の応用例は、テキスト比較エンジン、信号プロセッサ、コンボルーション・エンジン、アソシエーティブ・メモリ、インベントリ参照エンジン、遺伝子一致やタンパク質構造分析などの微生物アプリケーションを含むがこれらに限らない。
【０１２３】
好ましい具体例
レジスタ
カウンタフロー・パイプラインの好ましい実施例は、すでに図１１に示したデータ経路構成を使用する。２つの事象制御レジスタ６０および６６は、上向きバウンド・データ要素および下向きバウンド・データ要素を保持するように働く。これらのレジスタは、図示し、かつ前述した事象信号によって制御される。
【０１２４】
比較回路
カウンタフロー・パイプラインの好ましい実施例は、すでに図５で一般的な語で説明した比較を使用する。装置の一実施例では、３２ビットの各データ要素は、８ビットのレジスタ番号またはアドレスを伴う。このようなレジスタ番号は比較回路によって比較され、一致が検出された場合、レジスタ値に対して様々な動作が実行される。具体的には、一方のデータ経路から他方のデータ経路へレジスタ値をコピーすることも、続いてストリームから削除できるようにレジスタ値にマーク付けすることもできる。
【０１２５】
非同期通信経路
カウンタフロー計算パイプラインの非同期実施例用の段間のインタフェース機構は特に簡単なものである。この機構は、ある段から次の段へデータを送る動作が自動的に行われると仮定する。図８中のＣＯＰは、ＧＵ！信号とＧＤ！信号が共にＣＯＰよりも上の段と下の段とに進むことによって示したように、通信が可能であることを送信側装置と受信側装置の両方に通知する。
【０１２６】
実際は、非同期通信における送信側と受信側自体に通信のタイミングを制御させるのがよい。したがって、カウンタフロー・パイプラインの好ましい実施例は、図１３に示した発信経路を使用する。信号経路ＧＵ！およびＧＤ！は、送信側装置が通信チャネルへのアクセスを許可されたことを前記送信側装置に通知するためにＣＯＰによって使用される。実際の通信の制御では、発信経路ＰＵ！およびＡＵ！を使用して上向きデータ・フローを制御し、ＰＤ！およびＡＤ！を使用して下向きデータ・フローを制御する。点線で示したように、送信側装置はＧＵ！信号またはＧＤ！信号からそれぞれＡＵ！信号またはＡＤ！信号を生成する。したがって、図１３に示した接続によって導かれる動作は、図８に関して前述した機能を実行するが、図１３に示した接続は実際の通信機能を規則正しく完了する。
【０１２７】
図１３の構成は追加利点を有する。図３で構想されたように、上向き通信経路と下向き通信経路の間のデータ経路ワイヤを共用する必要がある場合、下の段はＧＵ！信号を許可として使用してデータを前記経路の共通のワイヤ上に置き、適当な遅延の後に、ＡＵ！信号を発行することができる。同様に、上の段はＧＤ！信号を許可として使用してデータを前記経路の共通のワイヤ上に置き、適当な遅延の後に、ＡＤ！信号を発行することができる。、
【０１２８】
当業者なら、機能が類似している他のインタフェースをどのように作成したらよいかを認識されよう。たとえば、さらに複雑な通信プロトコルを使用して、データ要素を送ることができる。たとえば、１方向または両方向の通信を一部、順次通信にして、それによって、段間で必要とされるデータ・ワイヤを少なくすることができる。この場合、追加制御ワイヤが必要とされることがある。図１３で、どの方向に通信すべきかに関する決定機能を通信タスク自体と分離した。図１３によって、当業者には、様々な通信機構をどのように提供したらよいかは明らかである。
【０１２９】
非同期制御
図１１に示した制御機構は、カウンタフロー・パイプラインの好ましい実施例の基礎を形成する。既存のデータ要素を削除することも、新しいデータ要素をデータ・ストリームに導入することもない段の場合、この形の制御で十分である。じきに分かるように、完全制御機構は、データ項目を挿入し削除することができるこの基本制御システム装置を追加することによって作成することができる。
【０１３０】
同様に、すでに図９および図１０で説明したＣＯＰ用の制御システムは、好ましい実施例に十分なものである。
【０１３１】
図１４は、各部分に分解された完全段３０の内部をさらに詳細に示す。好ましい実施例では、どちらかの方向に流れるデータをデータ・ストリームから削除することができる。上向き削除回路１２６および下向き削除回路１２０はこのために示されている。この段のこれらの部分中の制御機構については、後で図１５に関して説明する。好ましい実施例では、上向きに流れるデータは、ある種の状況下で、下向きに流れるストリームにデータを導入することができる。好ましい実施例では、新しいデータが上向きストリームに導入されることはない。したがって、図１４で、この段の部分１２４は下向きストリームにデータを挿入するために示されている。この段のこの部分用の制御機構については後で図１６に関して説明する。他のストリームに作用するようにひっくり返されてラベルを変更された同じ部分を使用して上向きストリームにデータを挿入することが望ましいアプリケーションでは、そのようにすることができる。挿入ボックスの動作の詳細については後で説明する。
【０１３２】
削除用回路
図１５は、１つの削除装置、たとえば１２６の詳細図を示す。この装置は、上向きに流れる情報を削除するように構成されている。下向きに流れる情報用の装置も同じであるが、下向きに流れるデータ向けに制御信号を修正するようにひっくり返されてラベルを変更される。削除装置がどのように動作するかを理解するには、段間の通信でハンドシェーク信号が使用されることを想起されたい。図１３に示したように、上向きデータ・フローの場合、ＣＯＰは、データを送信する下の段が動作できることを前記下の段に通知する。ＣＯＰは、このためにＧＵ！信号を使用する。下の段は、上向きバウンド・データ線３２上に、送るべきデータを置き、次いで、ＡＵ！信号を使用して、データの準備ができていることを上の段に通知する。上の段がデータを取り込むと、下の段が首尾よくデータを送ったことを示すＰＵ！信号を下の段に返す。
【０１３３】
削除装置は、制御信号に作用し、データにはまったく作用しない。削除装置は上の段と下の段を共にフール（ｆｏｏｌ）することによって機能する。削除装置は、ＡＵ！信号が上の段に到達するのを妨げ、それによって下の段が上の段にデータを送ろうとしたことを上の段が分からないようにすることによって上の段をフールする。削除装置は、上の段がデータを受け取った場合に行うのとまったく同じようにＡＵ！信号に応答してＰＵ！信号を返すことによって、上の段が、実際はデータを受け入れていないときに、受け入れたと下の段に思い込ませる。
【０１３４】
図１５の回路はこれを行う。通常の送信の場合、セレクタ１３０は、下から上の段へＡＵ！信号を送る。この動作で、セレクタはＡＵ！経路上で下から事象を受け取り、図の１番上でＡＵ！制御経路から出るように、「０」のラベルが付けられた端子から送り出す。しかし、データを削除する場合、セレクタはＫのラベルが付けられたサイド入力１３６に沿ってそのように通知される。Ｋ信号は、以後のデータ要素を削除または「キル」すべきであることをセレクタに通知する。データ要素を削除すべきである場合、セレクタはそのＡＵ！入力事象をその「１」出力に方向付ける。前記入力事象は前記「１」出力で３つのＸＯＲブロック１３２、１３４、１３８に進む。これらのＸＯＲブロックは通常の通信の場合、上から下へ事象を送る。また、これらのＸＯＲブロックは、セレクタの「１」出力によって刺激されたときに前記ブロックのそれぞれの出力の偽出力を生成する。
【０１３５】
挿入用回路
挿入装置１２４を図１６に示す。図１６で、挿入装置の制御経路はブロック１２４ａとして示され、データ経路はブロック１２４ｂとして示されている。この挿入装置は上向きに流れるストリームから下向きに流れるストリームにデータを挿入することができる。内容は同じであるが、他のデータ経路に作用するようにひっくり返された類似の回路を使用して、下向きストリームから上向きストリームにデータを挿入することもできる。この図では、そのような回路を図示していないが、当業者なら、以下の説明からそのような回路がどのように動作するかを理解できよう。
【０１３６】
挿入回路データ経路１２４ｂは、下向きに流れるデータ・ストリームに挿入すべき新しいデータ要素を保持するための余分なレジスタ１４０を含む。このレジスタは、下向きバウンド・データ・ストリームに挿入すべきデータ要素を上向きバウンド・データ・レジスタ６０から受け取る。挿入回路は、この新しいデータ、または下向きに流れるデータ経路３６に沿って上から下向きにくる正規データを選択するマルチプレクサ１４１も含む。
【０１３７】
本明細書で説明する制御機構では、上向きのデータ・フローは、下向きに流れるストリームへのデータ要素の挿入が完了するまで、挿入装置１２４中で遅延させられる。上向きに流れるデータが上の段に送られるのは、下向きストリームへの新たな挿入の後に限られる。新しいデータを同時に下向きに送り、上向きに流れるデータが進めるようにする挿入装置を構想することができる。
【０１３８】
挿入装置用の制御回路１２４ａは２つの部分から成る。セレクタ１４２およびＸＯＲ１４４が一方の部分を形成し、「優先順位ブレンダ」１４８が他方の部分を形成する。セレクタ１４２の事象入力は、下からくるＡＵ！信号からのものである。この信号は、有効なデータが下からくることを示す。このデータのうちのあるものを下向きストリームに挿入すべきかどうかは、セレクタのデータ入力１４３上の真Ｇ信号または偽Ｇ信号の存在によってセレクタに示される。データを挿入すべきでない場合、挿入装置１２４はまったく動作しない。この場合、セレクタはＡＵ！制御経路上で下からきた事象をＸＯＲ要素１４４を介してＡＵ！制御出力経路に送る。同様に、上からきたＣＤ入力はＸＯＲ装置１４９によって下のＣＤ制御出力に送られる。同様に、優先順位ブレンダ１４８は、ＰＤ！入力およびＰＤ？入力上の事象間の直接接続をそれに対応するＰＤ！出力およびＰＤ？出力に提供するように働く。
【０１３９】
次に、挿入が行われる予定であることをセレクタデータ入力１４３に入った信号Ｇが示すときに何が起こるかを検討する。ＡＵ！入力からセレクタに到着した事象は「１」出力に送られる。これによって、優先順位ブレンダのＰＧ？入力へ事象が送られ、ＸＯＲ装置１４６を介して、挿入すべきデータをレジスタ１４０から出力データ経路３６上に送るようにマルチプレクサ１４１が切り替えられる。遅延要素１４５は、データ経路がセットアップを完了できるようにするのに十分な遅延の後、それ自体の出力をＸＯＲ１４９に送り、したがって、図の下部にあるＣＤ出力経路上で出力を生成する。
【０１４０】
優先順位ブレンダのジョブは、挿入を行うのに適した制御信号を生成することである。通常、優先順位ブレンダは、その右側でのＰＤ？信号およびＰＤ！信号の配置によって示されるように、それらの信号を直接、スルー接続する。しかし、優先順位ブレンダは、ＰＧ？入力によって活動化されたとき、ＰＤ？出力がまだ生成されていない場合にこの出力を生成する。優先順位ブレンダは続いて、ＰＤ！出力ではなくＰＧ！出力に第１のＰＤ！応答を送る。
【０１４１】
挿入装置よりも下の段は、挿入装置によってデータ・ストリームに挿入されたデータと、挿入装置よりも上の段から送られたデータとの違いを区別することができない。どちらの場合も、ＰＤ？信号およびＰＤ！信号は、ＣＤ信号と同様に妥当に順序付けられる。したがって、マルチプレクサ１４１によって出力データ・ワイヤ３６に送られたレジスタ１４０からのデータは下の段に送られる。前述のようにこの動作が完了すると、ＰＤ！事象が下から受け取られる。優先順位ブレンダはこのＰＤ！事象を優先順位ブレンダ自体のＰＧ！出力へ送る。この場合、優先順位ブレンダは２つのことを行う。第１に、ＸＯＲ装置１４６に到着したときに、優先順位ブレンダはマルチプレクサ１４１をスルー位置に切り替える。第２に、優先順位ブレンダは、ＸＯＲ１４４を介して、最終的に、図の１番上にあるＡＵ！出力上の事象が最終的に、上向きバウンド・データが到着したことを上の段に通知できるようにする。
【０１４２】
状態図
段のすべての要素がアセンブルされると、非常に多くの事象が同時に発生することができる。図６の５つの状態によって記述された正常なデータ・フローの他に、データを削除し、あるいはデータをストリームに挿入できることによってさらに多くの状態が可能になる。これらの状態は、上向きまたは下向きに流れるデータを削除できるためと、新しいデータを挿入できるために発生する。図１７の状態図は、完全なカウンタフロー・パイプラインの単一の段が経験する可能性がある可能な１組の状態を概略的に示す。
【０１４３】
まず、図１７の図が図６の図の一般的特性を有するが、図６の各状態は複数の二次状態に分解されていることに留意されたい。たとえば、図６の１番上にある状態（Ｅ）は、図１７では４つの状態、すなわち番号０、４、３、１５に分解されているように見える。実際は、図６の状態図は図１７の状態図の部分集合であり、図１７中の状態を適切に組み合わせた場合、図６の状態図ができる。
【０１４４】
図１７の状態図は特定のパイプライン・システムの特定の設計から得たものである。この図で、文字「Ｉ」を含む符号は上向きバウンド・データを指し、文字「Ｒ」を含む符号は下向きバウンド・データを指す。この状態図は、上向きバウンド・ストリームから下向きバウンド・ストリームへのデータの挿入に対処する上で関与する状態を詳細に示す。ＯＫＩおよびＰＩ！はそれぞれ、上向きバウンド・データを受け入れて送ることを指す。ＯＫＲおよびＰＲＩはそれぞれ、下向きバウンド・データを受け入れて送ることを指す。ＧＲＥは、上向きバウンド・データ要素の結果として新しい下向きバウンド・データ要素を挿入する必要を指す。この必要は、上向きバウンド要素が到着した直後に分かる。ＮＧＲＥはそのような必要がないことを指す。ＧＲＭは、上向きバウンド要素と下向きバウンド要素を比較した結果として新しい下向きバウンド・データを挿入する必要を発見したことを指す。ＮＧＲＭはそのような必要がないことを示す。ＰＧは、新たに生成された要素を下向きストリームの一部として送る動作である。ＸＸは、上向き要素と下向き要素が共に存在すること、すなわち、状態（Ｆ）に到達したことを検出したことを指す。ＹＹは、おそらく、下向きに流れるストリームに新しい要素を挿入する場合を除き、段が空であることを検出したことを指す。
【０１４５】
これらの符号を念頭に置いて、図１７の状態図を解釈することができる。新たに生成された要素を送るとき（ＰＧ）、外側リングの状態２、３、４、５、６、８、９、１０がすべて、内側リングの状態に至ることに留意されたい。下向きストリームで新しい要素を生成しなければならないことを示すＧＲＥが発生できるのは、上向きに流れる要素が存在するときだけである。同様に、ＧＲＭが発生できるのは、上向きに流れる要素と下向きに流れる要素が共に存在するときだけである。
【０１４６】
図１７の状態図は、システムの挿入回路および削除回路に対する動作のある種の規則を仮定している。動作の他の規則が必要とされる場合、図１７に類似しているが同じではない状態図を描くことができる。当業者なら、そのような状態図は一般に、本明細書で説明するものなど複雑なシステムの動作を記述するために使用されていることを認識されよう。
【０１４７】
図１７の状態図を実施するための非同期制御機構の設計は簡単なものである。当業者なら、多数の状態コード化のうちのどれでも可能であることを認識されよう。たとえば、状態は、図４の２つのマーカ・ビット６２および６４と、生成された結果の存在を示すためのビットと、現在存在する上向きに流れるデータ要素がすでに、新しい下向きに流れる要素を生成しており、したがって他の下向き流れる要素を生成しないことを示すためのビットと、最後に、比較動作が終了したことを示すためのビットとによってコード化することができる。そのような同期制御の設計は当技術分野の範囲内である。
【０１４８】
しかし、非同期制御の設計はそれほど容易なものではない。図１３に、単一の段をどのように、異なる動作を別々に実行する構成部分に分解したらよいかが示されている。もちろん、他の設計も可能である。特定の設計を示すことによって実施態様を単一の設計に限定することは本明細書の趣旨ではない。本出願人はむしろ、必要な完全非冗長比較を提供する多数の設計のどれでも使用できることを指摘する。
【図面の簡単な説明】
【図１】１組のデータ経路段を操作するカウンタフロー・パイプライン制御のブロック図である。
【図２】段、上向きデータ・フロー経路および下向きデータ・フロー経路、ならびに段間の制御通信経路を示すカウンタフロー・パイプラインのブロック図である。
【図３】双方向データ経路を使用するカウンタフロー・パイプラインのブロック図である。
【図４】レジスタの状態を示すためのマーカ・フリップ・フロップを含む簡単なカウンタフロー・パイプラインの単一の段内のレジスタ手段および制御手段のブロック図である。
【図５】カウンタフロー・パイプラインの単一の段内のレジスタ手段および比較手段ならびにデータ計算装置のブロック図である。
【図６】５つの主要な状態を示すカウンタフロー・パイプラインの単一の段の状態図である。
【図７】カウンタフロー・パイプラインの同期実施態様用の可能な１組の通信信号およびクロッキング信号の詳細図である。
【図８】各段間にある「ＣＯＰ」のラベルの付いた調停装置を示すカウンタフロー・パイプラインの非同期実施態様のブロック図である。
【図９】８つの状態を示すＣＯＰで使用されるアービタの状態図である。
【図１０】図９のアービタを使用するＣＯＰの可能な実施態様のブロック図である。
【図１１】レジスタ手段が一杯であるときと、調停機構を解放すべきときを検出するための機構を示すカウンタフロー計算パイプラインの非同期実施態様の１つの段に必要とされる制御機構のブロック図である。
【図１２】分岐パイプラインのブロック図である。分岐点よりも上には、２つのカウンタフロー・パイプラインがあり、下には単一のパイプラインしかない。分岐点で上向きデータ・フロー経路が分割され、下向きデータ・フローが組み合わされる。
【図１３】実施例用の非同期実施態様のブロック図である。上向き通信および下向き通信が実際にどのように行われているかに関してさらに詳細に示す。
【図１４】削除、挿入、および比較用の経路に分解された非同期カウンタフロー・パイプラインの単一の段のブロック図である。
【図１５】実施例の削除部分に必要とされる制御機構の図である。
【図１６】データ・ストリームに挿入すべきデータを保持するための特別レジスタ手段を含むカウンタフロー・パイプラインの挿入部分のブロック図である。
【図１７】挿入および削除用の事象を示すカウンタフロー・パイプラインのある実施態様の単一の段の状態図である。
【符号の説明】
２０  段、  ２４  データ経路、  ２８  制御経路、  ３１  入力ポート、
３３  出口ポート、  ４２  双方向データ経路、  ５０  データ・パイプライン、  ５２  制御システム、  ６０  レジスタ、  ６２  マーカ・フリップ・フロップ、  ７０  マルチプレクサ、  ７２  比較計算ブロック、  ７８  クロック、  ８０  発信回路。
【図１】
0003588487.tif 000002
【図２】
0003588487.tif 000003
【図３】
0003588487.tif 000004
【図４】
0003588487.tif 000005
【図５】
0003588487.tif 000006
【図６】
0003588487.tif 000007
【図７】
0003588487.tif 000008
【図８】
0003588487.tif 000009
【図９】
0003588487.tif 000010
【図１０】
0003588487.tif 000011
【図１１】
0003588487.tif 000012
【図１２】
0003588487.tif 000013
【図１３】
0003588487.tif 000014
【図１４】
0003588487.tif 000015
【図１５】
0003588487.tif 000016
【図１６】
0003588487.tif 000017
【図１７】
0003588487.tif 000018