(57)【特許請求の範囲】
【請求項１】
ワードがプロセッサ中のステージ中を流れるコンピュータ・システム・プロセッサであって、
相互に順次接続された第１の処理エレメントの第１のシリーズであって、その個々の処理エレメントが、そのような第１の処理エレメントの第１のシリーズ中を流れるワードが前記ワードに関係する演算に参与するかどうかを決定するためのものである処理エレメントのシリーズと、
相互に順次接続された第２の処理エレメントの第２のシリーズであって、その個々の処理エレメントが、そのような第２の処理エレメントの第２のシリーズ中を流れるワードに対して演算を行うためのものである処理エレメントのシリーズと、
前記処理エレメント間の通信を実現する結合エレメントの第１のシリーズとを備えており、前記結合エレメントの第１のシリーズが、前記処理エレメントの第１のシリーズと前記処理エレメントの第２のシリーズの間に配置され、個々の結合エレメントの第１のシリーズが、第１の処理エレメントとそれに対応する第２の処理エレメントとの間に結合され、各結合エレメントが、それが結合されている前記処理エレメント間に通信パスを与えるプロセッサ。
【請求項２】
前記ステージ中を流れる前記ワードの各々が部分ワードに分割され、各ワードの１つの部分が、前記第１の処理エレメントの第１のシリーズに供給され、各ワードの第２の部分が、前記第２の処理エレメントの第２のシリーズに供給される請求項１に記載のプロセッサ。
【請求項３】
前記プロセッサのステージが、前記第１の処理エレメントの第１のシリーズのうちの１つと、前記第２の処理エレメントの第２のシリーズのうちの１つと、前記第１の処理エレメントの第１のシリーズのうちの前記１つを前記第２の処理エレメントの第２のシリーズのうちの前記１つに結合する前記結合エレメントの第１のシリーズのうちの１つとを備える請求項２に記載のプロセッサ。
【請求項４】
前記結合エレメントが、前記第１の処理エレメントの第１のシリーズから前記第２の処理エレメントの前記第２のシリーズへのメッセージのために単一方向通信パスを与える請求項３に記載のプロセッサ。
【請求項５】
前記結合エレメントの各々が先入れ先出しレジスタ・セット（ＦＩＦＯ）を備えており、前記ＦＩＦＯが、前記ＦＩＦＯの一方の端を前記第１の処理エレメントの第１のシリーズのうちの１つに結合し、前記ＦＩＦＯの反対の端を前記第２の処理エレメントの第２のシリーズのうちの１つに結合する請求項４に記載のプロセッサ。
【請求項６】
前記ＦＩＦＯが、それが結合されている前記第１の処理エレメントの第１のシリーズのうちの前記１つから先行制御メッセージを受け取り、それらのメッセージを、その反対の端が結合されている前記第２の処理エレメントの第２のシリーズのうちの前記１つに転送し、前記第２の処理エレメントの第２のシリーズのうちの前記１つの処理アクションが、前記先行制御メッセージによって制御される請求項５に記載のプロセッサ。
【請求項７】
前記ＦＩＦＯが、それが結合されている前記第１の処理エレメントの第１のシリーズのうちの前記１つから先行制御メッセージを受け取り、それらのメッセージを、その反対の端が結合されている前記第２の処理エレメントの第２のシリーズのうちの前記１つに転送し、前記第２の処理エレメントの第２のシリーズのうちの前記１つが、それらの先行制御信号を、先行する処理エレメントか後続の処理エレメントのうちの少なくとも一方に供給し、前記先行する処理エレメントか前記後続の処理エレメントのうち前記少なくとも一方の前記処理アクションが、前記先行制御メッセージによって制御される請求項６に記載のプロセッサ。
【請求項８】
前記コンピュータ・システム・プロセッサがカウンターフロー・パイプライン・プロセッサを備える請求項１に記載のプロセッサ。
【請求項９】
ワードがプロセッサ中のステージ中を流れるコンピュータ・システム・プロセッサであって、
相互に順次接続された第１の処理エレメントの第１のシリーズであって、その個々の処理エレメントが、そのような第１の処理エレメントの第１のシリーズ中を流れるワードが前記ワードに関係する演算に参与するかどうかを決定するためのものである処理エレメントのシリーズと、
相互に順次接続された第２の処理エレメントの第２のシリーズであって、その個々の処理エレメントが、前記第１の処理エレメントによって選択されたワードが修正を必要とするかどうかを検証するためのものである処理エレメントのシリーズと、
相互に順次接続された第３の処理エレメントの第３のシリーズであって、その個々の処理エレメントが、そのような第３の処理エレメントの第３のシリーズを通過するワードに対して演算を行うためのものである処理エレメントのシリーズと、
前記第１の処理エレメントの第１のシリーズと前記第２の処理エレメントの第２のシリーズの間に配置された結合エレメントの第１のシリーズであって、結合エレメントの第１のシリーズの個々の結合エレメントが、第１の処理エレメントとそれに対応する第２の処理エレメントとの間に結合され、各結合エレメントが、それが結合されている前記処理エレメント間に通信パスを与える結合エレメントのシリーズと、
前記第２の処理エレメントの第２のシリーズと前記第３の処理エレメントの第３のシリーズとの間に配置された結合エレメントの第２のシリーズであって、結合エレメントの第２のシリーズの個々の結合エレメントが、第２の処理エレメントとそれに対応する第３の処理エレメントとの間に結合され、各結合エレメントが、それが結合されている前記処理エレメント間に通信パスを与える結合エレメントのシリーズとを備えるプロセッサ。
【請求項１０】
前記ステージ中を流れる前記ワードの各々が部分ワードに分割され、各ワードの１つの部分が、前記第１の処理エレメントの第１のシリーズに供給され、各ワードの第２の部分が、前記第２の処理エレメントの第２のシリーズに供給され、各ワードの第３の部分が、前記第３の処理エレメントの第３のシリーズに供給される請求項９に記載のプロセッサ。
【請求項１１】
前記プロセッサのステージが、前記第１の処理エレメントの第１のシリーズのうちの１つと、前記第２の処理エレメントの第２のシリーズのうちの１つと、前記第３の処理エレメントの第３のシリーズのうちの１つと、前記第１の処理エレメントの第１のシリーズのうちの前記１つを前記第２の処理エレメントの第２のシリーズのうちの前記１つに結合する前記結合エレメントの第１のシリーズのうちの１つと、前記第２の処理エレメントの第２のシリーズのうちの前記１つを前記第３の処理エレメントの第３のシリーズのうちの前記１つに結合する前記結合エレメントの第２のシリーズのうちの１つとを備える請求項１０に記載のプロセッサ。
【請求項１２】
前記結合エレメントが、前記第１の処理エレメントの第１のシリーズから前記第２の処理エレメントの前記第２のシリーズへのメッセージ用と、前記第２の処理エレメントの第２のシリーズから前記第３の処理エレメントの前記第３のシリーズへのメッセージ用に単一方向通信パスを与える請求項９に記載のプロセッサ。
【請求項１３】
前記結合エレメントの各々が先入れ先出しレジスタ・セットを備えており、前記先入れ先出しレジスタ・セットが、前記レジスタの一方の端を前記第１の処理エレメントの第１のシリーズのうちの１つに結合し、前記レジスタの反対の端を前記第２の処理エレメントの第２のシリーズのうちの１つに結合する請求項１２に記載のプロセッサ。
【請求項１４】
前記先入れ先出しレジスタ・セットが、それが結合されている前記処理エレメントのうちの前記１つからメッセージを受け取り、それらのメッセージを、その反対の端が結合されている前記処理エレメントのうちの前記１つに転送する請求項１３に記載のプロセッサ。
【請求項１５】
前記第１の処理エレメントの第１のシリーズの各々がＧＥＴ演算を行うように構成された請求項９に記載のプロセッサ。
【請求項１６】
前記第２の処理エレメントの第２のシリーズの各々がＣＨＥＣＫ演算を行うように構成された請求項９に記載のプロセッサ。
【請求項１７】
前記第３の処理エレメントの第３のシリーズの各々がＰＲＯＣＥＳＳ演算を行うように構成された請求項９に記載のプロセッサ。
【請求項１８】
前記コンピュータ・システム・プロセッサがカウンターフロー・パイプライン・プロセッサを備える請求項１０に記載のプロセッサ。
【請求項１９】
前記メッセージが前記処理エレメントのうちの１つから別の前記処理エレメントへの先行制御メッセージを含み、これらの先行制御メッセージを受け取る前記処理エレメントが、これらの先行制御メッセージを受け取る前記処理エレメントに結合された他の処理エレメントの少なくとも１つにそれらを転送する請求項１４に記載のプロセッサ。
【請求項２０】
前記結合エレメントの第１および第２のシリーズの各々が、双方向通信パスを与えて、前記処理エレメントの第１、第２、および第３の間で両方向に情報が流れるようにする請求項９に記載のプロセッサ。
【発明の詳細な説明】
【０００１】
（発明の背景）
本発明はコンピュータ・システムのアーキテクチャに関し、詳細には、パイプライン中を流れるデータをより速く処理するために、カウンターフロー・パイプライン・プロセッサ・アーキテクチャが機能的に異なり、相互接続された「レイヤ」に区分されている非同期コンピュータ・システムに関する。
【０００２】
カウンターフロー・パイプラインはいくつかのステージからなり、ディジタル符号化された「ワード」の２つのフローがこのステージを両方向に流れる。ワードはデータ項目と考えることができ、命令、データ、またはその両方を含めることができる。ここでは説明のために、両方向を北と南と呼ぶ。カウンターフロー・パイプラインの定義特性は、パイプライン中に並行して存在する、北行きに流れるあらゆるワードと南行きに流れるあらゆるワードが、パイプラインのどこかのステージで厳密に１度、相互に遭遇することである。
【０００３】
現在、カウンターフロー・パイプライン・プロセッサはよく知られている。例えば、「Ｃａｓｃａｄｅｄ  Ｍｕｌｔｉｓｔａｇｅ  Ｃｏｕｎｔｅｒｆｌｏｗ  Ｐｒｏｃｅｓｓｏｒ  ｆｏｒ  Ｃａｒｒｙｉｎｇ  Ｄｉｓｔｉｎｃｔ  Ｄａｔａ  ｉｎ  Ｔｗｏ  Ｏｐｐｏｓｉｔｅ  Ｄｉｒｅｃｔｉｏｎｓ」という名称の米国特許第５５７２６９０号を参照されたい。カウンターフロー・パイプライン・プロセッサでは、符号化されたワードにはデータ・ワードおよび命令ワードの２種類がある。データ・ワードは通常、各々がデータ値を符号化した１つまたは複数のデータ部分と、アドレスやタグなど、各々がデータ・ワード中の対応するデータ部を識別する同数の参照部分とからなる。命令ワードは通常、行うべき処理ステップを指定する演算部分と、符号化されたデータを保持するための部分を同数有する１つまたは複数のオペランド参照部分とからなる。オペランド参照部分は、指定された演算に参与するかその影響を受けるかいずれかの種類のワードのデータ部分を識別する。我々の実施態様では、命令ワードは北行きにしか流れず、データ・ワードは南行きにしか流れない。
【０００４】
カウンターフロー・パイプラインのステージは、いずれかのワードのいくつかの部分またはすべての部分を無視して、その他の選択された部分のみを扱うことができる。ステージはまた、ワードの参照部分を検討し、ワードの「アクティブ」部分を変更するか、またはワードを修正せずに渡すことができる。
【０００５】
カウンターフロー・パイプラインのステージは、一方または両方のストリームから得た情報を使用して、いくつかの北行きワードおよび／または南行きワードのアクティブ部分を修正する。ワードが流れるとき、北行きの項目と南行きの項目が、カウンターフロー・パイプラインの特定のステージで相互に遭遇する。ステージは、ワード自体のいずれかの部分に含まれる情報を使用して、あるいは逆向きに流れるストリーム中で遭遇したワードの参照部分またはアクティブ部分からの情報に従って、どちらの種類のワードのアクティブ部分でも変更することができる。
【０００６】
このタスクを達成するために、パイプラインは、南行きワードがどれも皆、どの北行きワードともどこかのステージで確実に遭遇するようにしなければならない。北行きワードと南行きワードがどこかのステージで相互に遭遇するとき、これらを「遭遇ペア」と呼ぶことにする。ワードがどのステージで相互に遭遇するかは重要ではないが、北行きの要素がどれも皆、どの南行きの要素ともどこかのステージで遭遇することが不可欠である。以下に述べる発明は、この結果を効率的に達成するための構造を提供する。
【０００７】
（発明の概要）
本発明は、基本的なカウンターフロー・パイプライン構造の改良に関し、この場合、従来のシステムとは対照的にパイプラインが複数の「レイヤ」中に構築される。以下に述べるが、システムの複数のレイヤ各々が、タスク全体の一部を達成する。各レイヤは、時々、北行きワードの部分と南行きワードの部分を両方とも保持する。
【０００８】
この階層化構造の利点は、カウンターフロー・パイプラインがそのタスクをより速く行うことができることである。各レイヤがタスク全体の特化された部分を他のレイヤと並行して扱うことができるため速度の向上がもたらされる。さらに、後で明白になるであろうが、いくつかのレイヤは、遭遇ペアの部分ではないワードに対するアクションを省略することができ、またさらに、選択された遭遇ペアに対するアクションの省略が可能であると他のレイヤがすでに決定したとき、すなわち予期したとき、そのようなアクションを省略することができる。こうして不要なアクションの省略を予期することにより、システムは、そのタスクをより速く完了させることができる。
【０００９】
本発明の一実施態様では、ワードがカウンターフロー・パイプライン・プロセッサの諸ステージ中を流れるコンピュータ・システムの構造が提供される。この構造は、ステージを通過するワードが遭遇ペアを形成するかどうかをステージごとに決定するための第１レイヤの処理エレメントを含む。この構造はまた、第１レイヤの処理エレメントによって選択されたワードが修正を必要とすること、または遭遇ペア中のデータに関係する演算に参与することになることを検証するための第２レイヤの処理エレメントも含む。また、第１および第２のレイヤからの先行制御情報に基づいてワード自体に対する演算を行うための第３レイヤの処理エレメントも含まれる。様々なレイヤ中の処理エレメントは、結合エレメント、好ましくは「伸縮性のある」エレメント、例えばレイヤ間で先行制御情報のフローをバッファリングする先入れ先出しバッファ・メモリ・ユニット（ＦＩＦＯ）を使用して、相互に結合される。
【００１０】
改善型の性能を実現することに加え、本発明はまた、局所的相対遅延を改善することもできる。さらに、ＦＩＦＯまたはその他の手段によってプロセッサのレイヤ間でバッファリングを実現することにより、決定メッセージがバッファリングされ、それらの導出元であるデータがプロセッサ中で前進することができる。
【００１１】
（具体的な実施形態の説明）
図１に、カウンターフロー・パイプライン・プロセッサのステージを示す。各ステージ５が達成する３つのサブタスクがあり、これらをＧＥＴ、ＣＨＥＣＫ、ＰＲＯＣＥＳＳと呼ぶ。サブタスクについては後でより詳細に述べる。この３つのサブタスクが一緒に、各ステージ５で必要な演算すべてを行う。この３つのサブタスクは、様々な方式で結合することもできるが、後続の説明では別々に扱う。例えば、ＧＥＴ１０サブタスクとＣＨＥＣＫ２０サブタスクを結合し、次いで別個のＰＲＯＣＥＳＳ３０サブタスクと演算させることもでき、また、別個のＧＥＴサブタスクを、ＣＨＥＣＫサブタスクとＰＲＯＣＥＳＳサブタスクを結合したものと演算させることもできる。さらに、各サブタスクをさらに区分し、それによって複数のＣＨＥＣＫサブタスクまたはＰＲＯＣＥＳＳサブタスクが直列または並列で演算するようにすることもできる。
【００１２】
ステージ５の演算を理解するために、ステージがどのように挙動することができるかを考える。北行きワードおよび南行きワードの一様なフル・フローがある場合、ステージは、それに到着した北行きの各ワードを対応する南行きワードと共に処理することになる。これらの状況下では、仮説的なステージ「ｋ」が、ｓ番目の南行きワードと共にｎ番目の北行きワードに作用して、この２つを遭遇ペアとして扱い、ｎ番目の北行きワードを（ｓ＋１）番目の南行きワードと共に処理するタスクは別のステージとする。（ｎ番目、ｓ番目などの指数は、ワードの時間順を指す。）
【００１３】
しかし、パイプラインの演算には、どこかのステージで第１の方向に流れるワードが最大数（または多数）であって逆方向に流れるワードが少ないことがあり得る。この場合、各ステージにとっての戦略は、第１の方向のフローを遅延させて「少ない」逆方向からの要素の到着を末のではなく、一方の（第１の）方向にフローを許可することである。言い換えれば、２つのワードがそのステージにほぼ同時に到着したときだけ、そのステージは遭遇ペアとして処理する。
【００１４】
一方の方向に沢山流れ、逆方向のフローがまばらである場合、ステージは、フローのバランスがより保たれているときとは異なる挙動をとる。ステージは、双方のフローのうちのまばらな方に関連する理由でそのようにする。まばらなフローには、一般に２つの理由の可能性がある。すなわち、フローが輻輳しているか、あるいは流れているワードが途切れながら時折しか到着せず、したがってまばらなフローの方向の多くのステージが占有されていないことになるかのいずれかである。
【００１５】
フローが輻輳している場合、ステージ「ｋ」は、ｎ番目の北行きワードとｓ番目の南行きワードとで遭遇ペアを形成した後、（ｎ＋１）番目の北行きワードとｓ番目の南行きワードで次の遭遇ペアを形成する可能性がある。ワードの輻輳がこの例で南行き方向にあるとき、この例で南行きワードであるワードは、同じステージで、沢山流れてくる方向からの異なるワードを各々が使用するいくつかの遭遇ペアに相次いで参与することができる。
【００１６】
逆に、南行きフローがまばらな場合、ステージ「ｋ」は、ｎ番目の北行きワードとｓ番目の南行きワードから遭遇ペアを形成した後、いくつかの北行きワードを渡し終えるまで別の南行きワードを受け取らないこともできる。この場合、例えば（ｎ＋５）番目の北行きワードと（ｓ＋１）番目の南行きワードで次の遭遇ペアを形成して処理することができる。
【００１７】
カウンターフロー・パイプライン・プロセッサの確立された演算によれば、ステージは、遭遇ペアの部分ではないワードを前方に渡すとき、そのワードを無修正のままにする。一方の方向のフローがまばらな場合、多いフローの方向にある多くのワードは、いくつかのステージ中では遭遇ペアの部分でないため、修正されずにそれらのステージを通過することになる。しかし、一方の方向に流れるあらゆるワードは、パイプライン中を他方の方向に流れるどのワードとも遭遇ペアを形成する機会をどこかのステージで同時に有する。多いフロー方向のワードを修正せずに渡すことにより、パイプラインにとってより高い総スループットが得られる。
【００１８】
各ワード自体は、参照部分および潜在的に「アクティブな」部分からなる。これらの異なる部分は、諸ステージ中で異なる扱いを受ける可能性がある。ＣＨＥＣＫ２０サブタスクは一般に、遭遇ペアの参照部分を扱い、ＰＲＯＣＥＳＳ３０サブタスクは一般に、ペアの「アクティブな」部分を扱う。ＧＥＴ１０サブタスクは、それを通るワードの中に符号化されたどんな値も必要とせずに済み、その代わり、そのステージに到着したワードがあることを示す信号だけを使用する。
【００１９】
各サブタスクを実施する装置は、通常、隣接する北行きステージおよび南行きステージ中の対応するサブタスクと対話して、２本の対向するパイプラインに沿ったワードの適切なフローを維持する役割を担う。各サブタスクは、担当するワード部分を受け取り、それらに作用し、それらを前方に渡す。いくつかの適用例では、これらの部分を修正せずに渡すことになるサブタスクもある。
【００２０】
北行きワードと南行きワードのどちらかがカウンターフロー・パイプライン７を介してステージ５に到着すると、第１の決定ステージ５は、そのワードの「処置」を考えなければならない。ＧＥＴ１０サブタスクは、次の４つの代替例の中から選択してディスポジション決定(disposition decision)を行う。第１に、ステージにあるＧＥＴサブタスクは、特定の北行きワードと特定の南行きワードがそのステージ中で遭遇し、したがってそのステージに対して遭遇ペアを形成することになると決定する場合がある。第２に、ステージにあるＧＥＴサブタスクは、遭遇ペアの形成に適した南行きワードがないために、単に北行きワードを修正せずに渡すことを決定する場合がある。第３に、ＧＥＴサブタスクは、同様の理由で南行きワードを修正せずに渡すことを決定する場合がある。ステージは、遭遇ペアを形成できる都合のよい逆流ワードがないときは、どんなワードでも修正せずに渡す。第４に、どこかのステージで適切な遭遇ペアに対してそれが計算を完了した後で、通常、例えばその計算の結果を北行きに搬送するように、命令ワードが修正される。命令はまた、その結果を生成し、逆に流れる（南行きの）結果ストリーム中にそれを挿入することもできる。
【００２１】
ディスポジション決定を行った後、ＧＥＴ１０サブタスクは、そのディスポジション決定を２通りに使用する。第１に、ＧＥＴ１０サブタスクは、それが担当するワード部分に適切に作用する。例えば、北行きと南行きの両方のワードを捕えるか、あるいは北行きワードだけ、または南行きワードだけを捕える。第２に、ＧＥＴ１０サブタスクは、そのステージ中の他のサブタスク（ＣＨＥＣＫおよびＰＲＯＣＥＳＳ）にメッセージを送り、それらがしかるべく作用できるようにその決定を通知する。このメッセージは、他のサブタスクが再びディスポジション決定を行うことを不要にし、これらのサブタスクが対立するディスポジション決定を行う可能性を回避する。このメッセージは、どのワードのペアを遭遇ペアとして扱い、それらの個々のワード部分のどれを修正せずに渡すべきかを示す。
【００２２】
ＧＥＴ１０サブタスクのディスポジション決定を他のサブタスクに伝えるメッセージの形式は、システムの２つの実施形態、すなわち図１の「順次」実施形態と図２の「並行」実施形態では異なる。順次実施形態では、ＧＥＴ１０サブタスクはワード全体を担う。ＧＥＴ１０サブタスクは、そのディスポジション決定だけでなくワードの必要な部分すべても含むメッセージを他のサブタスクに送る。この実施形態では、ＧＥＴ１０サブタスクは、個々のワードに対するこのようなアクションが遭遇ペアの構成には適時でないこと、または他の何らかの理由で不適当であることをそのディスポジション決定が示した場合、単にそのアクションを回避することもできる。
【００２３】
カウンターフロー・パイプライン・プロセッサでは、いずれかの方向のフロー中を移動する情報を逆方向に流れるストリーム中に挿入することが可能である。例えば、下位レイヤからの決定を搬送するメッセージを保留する命令を保持することができる。この結果、後続の動作に影響するようにＣＨＥＣＫサブタスクおよびＰＲＯＣＥＳＳサブタスクがＧＥＴサブタスクにそれらのアクションを通知することが、いくつかの場合に有益である。少なくともこの状況では、図３に関連して後で考察するレイヤ間の単一方向通信パスの代わりに、双方向通信パスを採用することができる。
【００２４】
ＧＥＴ１０サブタスクは、両方のワードを必要とする後続のアクションがあればそのために、北行きワードと南行きワードの両方の必要な部分が必ずあるように、または必ずすぐにステージ５中に導入されるようにすることを担う。いくつかの場合では、遭遇ペアの形成に使用できる反対方向に流れるワードがないために、ＧＥＴ１０プロセスは、その北行きワードまたは南行きワードの部分を修正せずにカウンターフロー・パイプライン７に渡すことになる。そうするときは、ＣＨＥＣＫ２０サブタスクおよびＰＲＯＣＥＳＳ３０サブタスクにも同様にするように通知する。先に説明したように、ワードを修正せずに渡すことにより、パイプラインの演算全体の速度を上げることができる。
【００２５】
図１では、ＧＥＴ１０サブタスクが図の上部にある。ＧＥＴサブタスクの周りを再循環する矢印１２は、何らかのディスポジション決定に対して（それ以上の）処理が必要ないことを示し、したがってこのステージは、特定の北行きまたは南行きのワードを処理せずに渡すことができる。その下のＣＨＥＣＫ２０サブタスク・ボックスに進む矢印１４は、このステージ中でさらに処理するためにＧＥＴ１０サブタスクが遭遇ペアを識別したことを示すメッセージのパスを表す。この逐次アルゴリズム中で、ＧＥＴ１０サブタスクは、遭遇ペアを形成するワードもＣＨＥＣＫ２０サブタスクに渡し、次いで、次のディスポジション決定の実施に移る前に他のサブタスクの完了を待機する。
【００２６】
ＣＨＥＣＫ２０サブタスクは、北行きワードの１つと南行きワードの１つの遭遇ペアを形成するワードのすべてまたは一部を検討して、さらにアクションが必要かどうかを決定するが、ワード自体には変更を加えない。いくつかの場合では、ＣＨＥＣＫ２０サブタスクは、このワードのペアに対する次のアクションが不適切であることを確認することになる。次の処理が不適切とされるのは、ワードのうちの１つがすでに処理済としてマークされているため２つのワードが適合しないタイプであるため、ワード内のいくつかのフィールドの値が、次のアクションが不要であることを示しているため、または状況に応じたその他の理由からである可能性がある。ほとんどの状況で、ＣＨＥＣＫサブタスクは、次のアクションが不適切であることを見いだすことになる。
【００２７】
図１のＣＨＥＣＫ２０サブタスクからＧＥＴ１０サブタスクへの矢印１５は、何らかの理由でワードが不適合だということがＣＨＥＣＫ２０サブタスクに分かったためにこの遭遇ペアに対する次のアクションが不適切となったときに、ＧＥＴサブタスクが次のディスポジション決定の実施に移ることができることを示す。ＣＨＥＣＫ２０サブタスクからＰＲＯＣＥＳＳ３０サブタスクへの矢印１６は、次のアクションが必要であることを示すメッセージのパスを識別する。通常の場合、ＰＲＯＣＥＳＳサブタスクが行うことのできるアクションに適したワードの遭遇ペアをＣＨＥＣＫサブタスクが検出すれば、その場合に限って制御がＰＲＯＣＥＳＳサブタスクに移る。
【００２８】
カウンターフロー・パイプライン・プロセッサの実施形態では、ＣＨＥＣＫ２０サブタスクは、北行きワードと南行きワードの遭遇ペア中のレジスタ・アドレス・フィールドを検討する。この実施形態では、アドレス・フィールドが合致して、その北行きワードがその南行きワード中で搬送される特定の値を必要とすることを示していれば、その場合に限って次のアクションは適切であり、そうでない場合は、その南行きワードは無効としてマークされなければならない。
【００２９】
図１には単一のＣＨＥＣＫ２０サブタスクしか示していないが、いくつかの実施形態では、一連のいくつかのＣＨＥＣＫサブタスクを採用することもできる。例えば、このようなあるサブタスクが、ＧＥＴ１０サブタスクから提案された遭遇ペアが適したタイプのワード２つを含むかどうかを確認し、次のＣＨＥＣＫ２０サブタスクが、その遭遇ペアのワード２つが次のアクションを有用にするのに適した値を有するかどうかを確認するようにしてもよい。ＣＨＥＣＫ２０サブタスクをさらにサブタスクに分割することは、いくつかの実施形態で有用である。いくつかの場合では、遅延の少ない、より早期のＣＨＥＣＫサブタスクが、それより後のＣＨＥＣＫサブタスクによってワードに対するアクションがさらに行われるのを回避できる可能性がある。
【００３０】
最後のサブタスクは、必要とされる実際の処理を達成するものである。このサブタスクは、図１でＰＲＯＣＥＳＳ３０という名称を付けてあり、当業者によく知られている様々なコピー、論理演算、または算術演算のいずれかを含むことができる。図１中のＰＲＯＣＥＳＳ３０サブタスクの底部からＧＥＴ１０サブタスクにループバックする矢印１７は、処理の完了後にこのステージがＧＥＴサブタスクに制御権を返して次の遭遇ペアを探すことを示す。
【００３１】
図１には単一のＰＲＯＣＥＳＳ３０サブタスクしか示していないが、順にまたは並列に配置したいくつかのＰＲＯＣＥＳＳサブタスクを採用することもできる。例えば、あるＰＲＯＣＥＳＳサブタスクが北行きワード中の値を修正し、別のＰＲＯＣＥＳＳサブタスクが南行きワード中の値を修正するようにしてもよい。
【００３２】
ここまでは、いずれか１つのステージで逐次プロセスとして実施されるアルゴリズムを述べ、図１に示したように逐次形式のアルゴリズムを呈示した。当然、このような逐次アルゴリズムは一般に、並行形式でも実施することができる。このような処理がパイプライン処理と呼ばれることもあるが、後続の記述では、「パイプライン」という語を、メイン・カウンターフロー・パイプライン中の北行きおよび南行きの情報のフローについてのみ用いる。次に述べるＧＥＴ−ＣＨＥＣＫ−ＰＲＯＣＥＳＳアルゴリズムは、メイン・パイプラインの北／南方向と直交するタスク指向情報のフローを必要とする。この先行制御情報の直交フローを述べるために、ディスポジション決定およびメッセージの概念を使用する。
【００３３】
図２は、図１の逐次アルゴリズムの並行実施形態または階層化実施形態の図である。この場合、各サブタスクは、それ自体の処理に必要なワードの北行き部分および南行き部分（図２では「部分ワード」という名称を付けてある）だけを扱う役割を担う。この実施形態では、各ワードの別々の部分が、異なるサブタスク・レイヤを通過する。ＧＥＴ１０プロセスはこの場合、他のプロセス・レイヤにそのディスポジション決定を通知し、それにより、残りのサブタスクがＧＥＴ１０サブタスクから残りのサブタスクに送られるディスポジション決定報告メッセージに完全に従って、遭遇ペアに作用できるように、または遭遇ペアのメンバーでないそれらのワード部分を修正せずに渡せるようにしなければならない。
【００３４】
図２のＧＥＴ１０、ＣＨＥＣＫ２０、およびＰＲＯＣＥＳＳ３０のサブタスクは、図１との関連で述べたのと同じ目的を有する。しかしこの場合、いくつかの相違がある。第１の相違は、図の各ブロック内にある内部矢印１１、２１、３１によって示される。各サブタスクはそれ自体の演算を何度も繰り返し、３つのサブタスクすべては並行して演算する。サブタスクは、通信パス４０および４５を介して、あるサブタスクから次のサブタスクに流れるタスク指向制御メッセージに従って演算するが、これらの通信パスの各々は通常、先入れ先出しレジスタ・セットすなわちＦＩＦＯであり、これは図面中でそのように名称を付けてあり、当技術分野で周知のものである。このようなＦＩＦＯは、その入力端子でメッセージを受信し、その出力端子でそれらを受信順に送ることができ、必要なら、まだ送るべきでないいくつかのメッセージを内部に保持し、それによりメッセージのフローをバッファリングすることができる。
【００３５】
図２の構造と図１の構造の第２の相違は、ＧＥＴ、ＣＨＥＣＫ、ＰＲＯＣＥＳＳのサブタスクからＧＥＴサブタスクに完了メッセージを搬送する矢印１２、１５、１７が省略されていることである。これらの矢印は図１にあり、ＧＥＴサブタスクが次のディスポジション決定の実施に移ることができるときを示していた。図２では、ＦＩＦＯの入力端部および出力端部が信号手段を備えており、これらの信号手段は、入力端部で、別のメッセージ用に空間が利用可能であることを示し、出力端部で、後続のサブタスクのアクションを指示するＦＩＦＯ出力メッセージが利用可能であることを示す。図２では、各サブタスクがその入力ＦＩＦＯからの必要なメッセージを待機し、それ自体のメッセージを入れるためのその出力ＦＩＦＯ中の空間を待機するようにするための手段は暗黙的である。
【００３６】
図２の構造と図１の構造の第３の相違は、図２に示すように、各サブタスクがこの場合、すぐ隣接するステージの対応するサブタスクにそのワード部分を直接通信する役割を担うことである。
【００３７】
図２の並行アルゴリズム実施形態では、ＧＥＴ１０サブタスクがこの場合も、次のアクションに適したワードの遭遇ペアを探してディスポジション決定を行う。しかしこの場合、ＧＥＴ１０サブタスクは、それからＣＨＥＣＫ２０サブタスクまでを通るＦＩＦＯ４０中にそのディスポジション決定の結果をメッセージとして入力する。例えば、ＧＥＴ１０サブタスクは、ｎ番目の北行きワードとｓ番目の南行きワードを遭遇ペアとして共に扱うべきであることが分かった場合、そのことをメッセージとして出力ＦＩＦＯ４０中に記録する。（ｎ＋１）番目の北行きワードを修正せずに渡すことを決定した場合は、そのことを出力ＦＩＦＯ４０中に別のメッセージとして記録する。ディスポジション決定を行って対応するメッセージを出力ＦＩＦＯ４０中に記録した後、ＧＥＴ１０サブタスクは、後続の北行きおよび南行きの部分ワードの検討に移って、このステージが作用すべき次の遭遇ペアを順次検出することができる。
【００３８】
ディスポジション決定を搬送するメッセージに異なる多くの符号化を施すことが可能である。このような符号化の１つは、各ディスポジション決定を順に別々のメッセージとして記録する。例えば、このようなメッセージは、「この北行きワードは無修正で通るべきである」、「この南行きワードは無修正で通るべきである」、または「これらの北行き／南行きワードを遭遇ペアとして扱え」ということを示すことができる。別の符号化は、使用すべき遭遇ペアのシーケンス番号だけを記録することができる。例えば、このようなメッセージは、「２４５番目の北行きワードと３７番目の南行きワードが遭遇ペアを形成する」ということを示すことができる。使用するメッセージ符号化フォーマットの特定の選択は、適用例と、様々な種類のディスポジション決定の相対度数とによって決まる。
【００３９】
したがって、並行実施形態では、ＣＨＥＣＫ２０サブタスクは２種類の情報を受け取る。第１に、ＣＨＥＣＫ２０サブタスクは、それが「チェック」する必要のある北行きワードおよび南行きワードの部分をメイン・カウンターフロー・パイプライン通信パス７から受け取る。第２に、上に図２で示したようなＦＩＦＯ４０を介して、ＧＥＴ１０サブタスクによって行われたディスポジション決定に関する先行制御メッセージも受け取る。
【００４０】
ＦＩＦＯ４０は、完全な北行きワードを修正せずに渡すべきであることを示す引き続く３つのディスポジション決定に対し、ＧＥＴプロセス１０からＣＨＥＣＫプロセス２０にメッセージを送ることができる。したがって、ＣＨＥＣＫ２０サブタスクは、遭遇ペアが次に現れることをＦＩＦＯ４０からのメッセージが示すまで、３つのワードのその部分を修正せずに渡すことになる。別の符号化を使用する場合、ＦＩＦＯ４０からのメッセージは、次の適したペアが２５４番目の北行きワードと３７番目の南行きワードからなることだけを示すことができる。制御情報がこの形式である場合、ＣＨＥＣＫサブタスクは、そのサブタスクを行うべき正しい遭遇ペア部分を得るまで、２５４番目よりも早い北行きワードのその部分があればそれを修正せずに渡すようにし、同様に、３７番目よりも早い南行きワードのその部分があればそれを修正せずに渡すようにする。ＦＩＦＯ４０中のメッセージ符号化が何であれ、ＦＩＦＯからのメッセージは、どの部分ワードを修正せずに渡すか、およびどれをその遭遇ペア部分として扱うかをＣＨＥＣＫプロセスに通知する。余分な北行きワードがある場合、ＧＥＴ１０サブタスクは、それらを修正せずに渡すことを決定し、その出力ＦＩＦＯ４０中でそのように示すことができる。その場合、ＣＨＥＣＫサブタスクは、その部分ワードが素早く次のステージに移れるようにすることになる。
【００４１】
ＧＥＴ１０サブタスクとＣＨＥＣＫ２０サブタスクの間のＦＩＦＯ４０は、どのワードが遭遇ペアを形成し、どのワードを修正せずに渡すべきかを示すメッセージを搬送する。ＣＨＥＣＫ２０サブタスクとＰＲＯＣＥＳＳ３０サブタスクの間のＦＩＦＯ４５は、それと非常に似た情報をＰＲＯＣＥＳＳサブタスクに提供する。このＦＩＦＯ４５中のメッセージに従って、ＰＲＯＣＥＳＳ３０サブタスクは、それが受け取った遭遇ペアの部分ワードを処理するか、あるいはペアにされないその部分ワードを修正せずに渡すことになる。ＣＨＥＣＫサブタスクの目的は、後続の処理を必要とする遭遇ペアの数を削減することである。複数のＣＨＥＣＫサブタスクを使用する場合、各々は、上から提案された遭遇ペアを拒否して、下の後続ステージによる作業を不要にするように試みる。ＰＲＯＣＥＳＳ３０サブタスクは、すべてのＣＨＥＣＫを通過した遭遇ペアのその部分だけに対して、すなわち、処理するよう喚起されたペアの指定部分だけに対して、ＰＲＯＣＥＳＳ３０サブタスクに求められる作業は何でも行う。
【００４２】
図３に、階層型カウンターフロー・パイプライン・プロセッサの４つのステージを示す。これらのステージを、．．．ｋ、ｋ＋１、ｋ＋２、ｋ＋３．．．として表す。各ステージは図で垂直列として表され、各々は、ＧＥＴ、ＣＨＥＣＫ、およびＰＲＯＣＥＳＳのサブタスクを実装している。隣接するステージ間に６本の通信パスがあり、３本は北行きの向きであって５０、５４、５８として表し、３本は南行きの向きであって５２、５６、６０として表す。これらのパスがカウンターフロー・パイプラインを形成する。レイヤ間でディスポジション決定メッセージを搬送するＦＩＦＯ４０および４５もまた図に示す。物理デバイス形式におけるこの構造の実際の配置は、それを実施するのに使用される技術に適した利用可能などんな数の次元でも実現できるが、この構造は、この図によって提案しているような３次元構造で最もよく視覚化される。
【００４３】
前述のように、北行きワードおよび南行きワードは各々、サブタスク・レイヤの必要に適する部分ワードに分割される。ある時点で特定のステージ中のＧＥＴ１０ｂサブタスクがｎ番目の北行きワードおよびｓ番目の南行きワードを扱っている場合、ＣＨＥＣＫ２０ｂサブタスクは同時に、以前のその北行きワードの部分、例えば（ｎ−１）番目の部分と、以前のその南行きワードの部分、例えば（ｓ−１）番目の部分を検討することができる。当然、そのステージ中のＧＥＴ１０ｂサブタスクがもっと早い遭遇ペアを以前に供給していた場合は、ＣＨＥＣＫ２０ｂサブタスクは、（ｎ−４）番目と（ｓ−２）番目をペアとして扱うこともできる。ＧＥＴサブタスクからＣＨＥＣＫサブタスクまでのラグは、サブタスクの相対速度、北行きおよび南行きのカウンターフロー・パイプライン中のワードのフロー、ディスポジション決定、およびサブタスク間でメッセージを搬送するＦＩＦＯ４０の長さに応じてその時々で変化する可能性がある。
【００４４】
また、特定の遭遇ペアに対し、ＣＨＥＣＫ２０ｂサブタスクが通常よりもずっと多くの時間を必要とすることもあり得る。このような場合、ＣＨＥＣＫ２０ｂサブタスクは、ＧＥＴ１０ｂサブタスク中で現在検討中のものを超えて長い間、部分ワードのペアを扱っていることがある。ＧＥＴ１０ｂサブタスクとＣＨＥＣＫ２０ｂサブタスクの間のＦＩＦＯ４０ｂは、特定の適用例が有用とみなすだけの量のディスポジション決定メッセージを格納するのに必要なだけ長くなることになる。いずれか１つのステージの場合に、ＧＥＴ１０サブタスクは、ＣＨＥＣＫ２０サブタスクとの間のＦＩＦＯ４０の長さが許容する限り、ＣＨＥＣＫ２０サブタスクよりも「先を行く」ことができる。同じことは、ＣＨＥＣＫ２０サブタスクとＰＲＯＣＥＳＳ３０サブタスクの間のＦＩＦＯ４５にも当てはまる。ＣＨＥＣＫサブタスクは、隣接するステージからのその部分ワード、およびＰＲＯＣＥＳＳサブタスクとの間のメッセージＦＩＦＯ４５の長さが利用可能である限り、ＰＲＯＣＥＳＳサブタスクよりも先を行くことができる。
【００４５】
１９９６年４月２３日出願の「Ｉｎｔｅｒｌｏｃｋｅｄ  ＦＩＦＯ  Ｃｏｎｔｒｏｌ  Ｃｉｒｃｕｉｔｓ」という名称の、我々の同時係属の米国特許出願第０８／６３６２６０号に開示されている機構を採用して、ＧＥＴ１０サブタスクおよびＣＨＥＣＫ２０サブタスクのアクションと、それらの間のメッセージＦＩＦＯ４０との間で調整を行うことができる。北行きパス５０のワードのフローと、メッセージＦＩＦＯ４０中のメッセージの下向きのフローが共に、上に参照した特許出願に記載の２次元パイプラインを形成する。同様に、南行きパス５２とメッセージＦＩＦＯ４０もまた、２次元パイプラインを形成する。前述の特許出願には、データおよびメッセージのフローをどのように調整するかが記載されている。
【００４６】
ＣＨＥＣＫ２０サブタスクが、メッセージＦＩＦＯ４０が満たしているＣＨＥＣＫ２０サブタスクの作業よりもずっと後れをとった場合、対応するＧＥＴ１０サブタスクは、メッセージＦＩＦＯ中にそのディスポジション決定メッセージ用の空きがそれ以上ないことを見出して、ＣＨＥＣＫサブタスクがメッセージＦＩＦＯを十分に排出して次のディスポジション決定メッセージ用の空きを形成するまで処理を中止する。
【００４７】
各レイヤ内の北行き方向および南行き方向のワードのフローも、適切な制御メッセージが次のサブタスクに利用可能になるまで同様に延期することができる。例えば、北行きの部分ワードがＣＨＥＣＫ２０サブタスクの上の対応するＦＩＦＯ４０からの制御メッセージの前にＣＨＥＣＫ２０サブタスクに到着した場合、この北行きの部分ワードが、このステージ中で作用しなければならない遭遇ペアからのものであるかどうかをそのサブタスクが決定できるように、サブタスク中のこの北行きの部分ワードは、ＧＥＴ１０サブタスクからのメッセージがＦＩＦＯ４０を通過してＣＨＥＣＫ２０サブタスクに届くまで待機しなければならない。この場合も、上に参照した特許出願の教示を使用して、非同期ＦＩＦＯを１次元よりも高い次元で構築することができる。
【００４８】
ＰＲＯＣＥＳＳ３０サブタスクは、ＣＨＥＣＫ２０サブタスクがするのと同様の仕方で、それに対応するＦＩＦＯ４５からメッセージを受け取るが、違う点は、作用すべき遭遇ペアの部分ワードがそれに通知されることがより一層少なく、したがって、その部分ワードのほとんどを修正せずに渡すべき場合がそれに通知されることがより多いことである。ＰＲＯＣＥＳＳサブタスクは、おそらくその部分ワードのほとんどを修正せずに渡すことができる。ただし、そのような部分ワードはＰＲＯＣＥＳＳサブタスクが扱わなければならない遭遇ペアからのものではないことが、対応するＣＨＥＣＫ２０サブタスクから命令されたときに限ってそうすることになる。
【００４９】
より前の例に戻り、ＰＲＯＣＥＳＳサブタスクの２５４番目の北行き部分ワードと３７番目の南行き部分ワードが、対応するＣＨＥＣＫ２０サブタスクを偶然満たす次の遭遇ペアからくると仮定する。このことは、ＣＨＥＣＫサブタスクとＰＲＯＣＥＳＳサブタスクの間のＦＩＦＯ４５中でメッセージとして符号化される。このようなメッセージを受け取ると、ＰＲＯＣＥＳＳ３０サブタスクは、２５４番目よりも前の北行きの部分ワードと、３７番目よりも前の南行きの部分ワードを修正せずに渡すことになるが、作用すべき部分ワードの遭遇ペアとして２５４番目の北行きの部分ワードと３７番目の南行きの部分ワードを両方とも有するまで、それらを保存する。一方、ＣＨＥＣＫサブタスクの２５４番目の北行き部分ワードおよび３７番目の南行き部分ワードがＣＨＥＣＫサブタスクを満たすことができない場合、ＰＲＯＣＥＳＳサブタスクは、それに対応する部分ワードの各々を、それ以上遅延させることなく無修正で指示通りに渡す。
【００５０】
ＧＥＴサブタスクからの制御メッセージが、ＧＥＴサブタスクの２つの部分ワードがこのステージ中の遭遇ペアからのものであることを示すとき、ＣＨＥＣＫサブタスクとＰＲＯＣＥＳＳサブタスクは両方とも、それらの部分ワードを保持し、それらに合致する部分ワードが到着するのを待機する。当然、このような遅延がＣＨＥＣＫサブタスクに課されても、次のアクションにその遭遇ペアが適さないことがＣＨＥＣＫサブタスクに分かった場合は、このような遅延がＰＲＯＣＥＳＳサブタスクには必要ないことが判明することもあり得る。より後のレイヤに対してデータ・フローを遅れさせる必要性を除去することにより、性能に大きな向上がもたらされる。
【００５１】
上に引用した米国特許第５５７２６９０号には、カウンターフロー・パイプライン・システムが記述されている。この図１Ａと、１２列目の２０行目で始まる本文には、データ・パス５０を制御するための制御システム５２が記載されている。この構造を本発明ではさらに改良する。ＧＥＴサブタスクは、ＣＨＥＣＫサブタスク中の部分ワードのフローを制御することを目的とした制御システムの第１部分と考えることができる。さらに、ＧＥＴおよびＣＨＥＣＫのサブタスクは共に、ＰＲＯＣＥＳＳサブタスクを制御および単純化することを目的とした複合制御システムと考えることもできる。
【００５２】
本発明の図２には図３の構造の垂直スライスを示してあるが、図４〜６は、この構造の水平スライスである。図４には、ＧＥＴレイヤ１１０を示す。メインの北行きおよび南行きのデータ・パス５０、５２（カウンターフロー・パイプライン）を、図の左および右に垂直線で示してある。これらのデータ・パスは、ワードがあることをＧＥＴレイヤだけに示す必要がある。ＧＥＴレイヤは、ワードの符号化値には関心を有しない。ＧＥＴレイヤのタスクは、前述のように、北行きと南行きのデータ要素１つずつの遭遇ペアを探してディスポジション決定を行うことである。このような遭遇ペアだけが、他のレイヤによるアクションに適する。ＧＥＴレイヤ１１０は、このような遭遇ペアを、それらの値がＣＨＥＣＫレイヤ１２０によって検討される前に選択する。ＧＥＴレイヤ１１０はその決定を示すメッセージをＦＩＦＯ４０中に入れるが、ＦＩＦＯ４０は、下にある別のレイヤに接続されていることを示すために図では斜めに示してある。最も重要なのは、以前に識別した遭遇ペアを他のレイヤが処理するのと同時にＧＥＴレイヤが次の遭遇ペアの検出に専念でき、したがって処理速度が向上することである。ワードが要素部分ワードに分割されてから適切なレイヤに送られるようにレイヤを構成することによって、従来の非階層化設計で見られるよりもよい並行性が実現される。
【００５３】
諸ステージ中のＧＥＴサブタスクは、北行きワードと南行きワードがすれ違う前に、北行きワードがどれも皆、どの南行きワードともどこかのステージで遭遇ペアを形成することを一括して保証しなければならない。特定のステージにあるＧＥＴレイヤは、北行きワードが到着したことを示すインジケータと、適する可能性のある南行きワードもまた到着したことを示すインジケータを符合させる。次いで、その出力ＦＩＦＯを介して、そのディスポジション決定を示すメッセージを送る。適した南行きワードが到着しない場合、ＧＥＴレイヤは、その出力ＦＩＦＯを介して、後続のレイヤがそれらの北行きワードの部分をすぐに渡すことができることを示す処置メッセージを送る。
【００５４】
したがって、ＧＥＴレイヤの正しい演算には、遭遇ペアを適切に識別することが必要である。ＧＥＴレイヤの適切な演算を保証するためのいくつかの手法が可能であり、その中のいくつかは、ＧＥＴレイヤ内の隣接するステージ間で追加の制御情報を通信することを含む。いくつかの場合では、この通信は、特定の演算サイクル中に北行き部分ワードと南行き部分ワードのどちらがステージ間を通ることができるかを制御する。他の場合では、この通信は、ＧＥＴレイヤ中のどのステージが遭遇ペアに関するステージの間の通信の制御に入るかを決定する。このタスクを適切に達成するには、図４に示すように、隣接するステージ中のＧＥＴサブタスク間に追加の通信パス１１が必要な場合がある。いくつかの非同期実施形態では、ＧＥＴサブタスクが適切に演算するために、１９９６年５月３１日出願の「Ｆａｓｔ  Ａｒｂｉｔｅｒ  ｗｉｔｈ  Ｄｅｃｉｓｉｏｎ  Ｓｔｏｒａｇｅ」という名称の、我々の同時係属の米国特許出願第０８／６５５９９９号に記載されているものなどのアービトレーションもまた必要である。
【００５５】
２つのワードが相互に遭遇するステージの特定の選択はまったく自由裁量の決定であるため、ディスポジション決定の多くの組合せがカウンターフロー・パイプライン・プロセッサの正しい演算を生み出すことになる。しかし、われわれの実験では、ＧＥＴレイヤ１１０レイヤのステージ割当てディスポジション決定がシステム全体の演算速度に大きな影響を及ぼすことが示された。どのステージを各遭遇に割り当てるかの選択が不十分な場合、カウンターフロー・パイプライン中のフローが遅延し、したがって演算が遅れる可能性がある。したがって、ＧＥＴレイヤ中の遅延は、各部分ワードが他のレイヤ中で受けることになる平均遅延をできるだけ忠実にモデリングすることが好ましい。ＧＥＴレイヤの演算が速すぎる場合、ＧＥＴレイヤは、遅延の点から他のレイヤにとって適切でないステージ中でペアを結び付けることになる。演算が遅すぎる場合もまた、不適切なステージをワードの各ペアに選択することになる。ＦＩＦＯ４０、４５中のバッファリングは、システム全体が広範囲な処理継続時間に適応するのを可能にする。
【００５６】
ＧＥＴレイヤ１１０によって行われるディスポジション決定の質は、システムの演算速度だけにしか影響せず、結果の正確さには影響しない。例えば、ＧＥＴレイヤがｎ番目の北行きワードおよびｓ番目の南行きワードを処理するために不適切なステージを選択することによって、不十分なディスポジション決定を行うと仮定する。対応するＣＨＥＣＫサブタスクおよびＰＲＯＣＥＳＳサブタスクは、ｎ番目およびｓ番目の部分ワードが到着するまで、それらの部分ワードの進行を延期することになる。遭遇ステージの不適切な選択は、一方の部分ワード、例えば北行きワードが他方の南行きワードよりもずっと早く到着することを確実に意味する。もっと北のステージを選択した方がよく、そうすればこれら２つの部分ワードはほぼ同時に、より自然に到着し、したがって遅延が回避されたはずである。しかし、各サブタスクが、必要な要素がそれに利用可能になるまでそれに与えられた指示に厳密に従い、必要ならデータ・フローを停止させるため、正しい解答はいずれのケースでも生み出されることを理解されたい。
【００５７】
他の実施態様では、図４のＧＥＴレイヤ中でラッチまたはレジスタ６３、６５を使用することができる。これは、北方向および南方向に流れるデータを正しくバッファリングするのを容易にする。
【００５８】
図５は、ＣＨＥＣＫレイヤ１２０の図である。各ステージ中のチェック・プロセスは、ＣＨＥＣＫという名称を付けた制御ボックスと、このレイヤに関係する北行き部分ワードおよび南行き部分ワードの部分を保持するための、ＲＥＧＩＳＴＥＲという名称を付けたデータ・ラッチまたはレジスタのペア６４、６６で表す。周知のデータ・ラッチが、非同期パイプライン中の記憶手段として機能することができる。２つのＦＩＦＯ４０、４５が、ＣＨＥＣＫ２０に先行制御機能を与えるように接続されている。図５の左に示す入力ＦＩＦＯ４０はＧＥＴレイヤから先行制御メッセージを搬送し、図５の右に示す出力ＦＩＦＯ４５はＰＲＯＣＥＳＳレイヤに次の先行制御メッセージを送る。
【００５９】
各ステージ中に示す比較６７は、ＰＲＯＣＥＳＳレイヤがこの遭遇ペアに作用すべきか否かを決定するために必要なデータ比較を何でも行う論理エレメントを表す。この論理計算の内容は、ステージの特定の適用例によって決まる。米国特許出願第５６００８４８号に記載のカウンターフロー・パイプライン・プロセッサの場合、このテストは、北行きレジスタ・アドレス・フィールド値および南行きレジスタ・アドレス・フィールド値が等しいかをみるためのものである。
【００６０】
図６は、ＰＲＯＣＥＳＳレイヤ１３０の図である。この場合も、北行きおよび南行きの部分ワードを保持するためのラッチまたはレジスタ７２、７４を、ＲＥＧＩＳＴＥＲという名称をつけたボックスとして示す。しかしこの場合は、単一ステージ中の２つのレジスタの間にデータ・パスがある。ＰＲＯＣＥＳＳレイヤの制御回路が、これらのデータ・パス７５、７６を制御する。これらのデータ・パスは、それ自体および／または反対に流れる部分ワードからの情報に従って北行きの部分ワードと南行きの部分ワードのいずれかまたは両方の中のデータ・フィールドを選択的に置換するための、ＰＲＯＣＥＳＳレイヤ中の手段を表す。置換されるデータは、図示しない手段を使用する２つのレジスタ中のデータのどんな論理機能でもよいことを当業者なら理解するであろう。置換されるデータはまた、ＣＨＥＣＫレイヤ１２０から渡された情報を含むこともできる。ＰＲＯＣＥＳＳレイヤ１３０は最終レイヤであるため、出力ＦＩＦＯはない。
【００６１】
図１から６までに関連して述べた本発明による以上のすべての実施態様では、制御情報は、ＦＩＦＯを使用して、様々なレイヤを通して下方に渡された。しかし、本発明には、ＰＲＯＣＥＳＳレイヤやＣＨＥＣＫレイヤなどの下位レイヤが上方のＣＨＥＣＫレイヤまたはＧＥＴレイヤに通信できるような双方向通信パスがレイヤ間にあることが好ましい実施態様もある。このような双方向通信パスにより、ＰＲＯＣＥＳＳレイヤから高位レイヤに中間結果またはその他の結果を転送し返すことができ、したがってそれらの結果が高位レイヤ中の後続の活動に影響することができる。このような状況では、図６に示したＦＩＦＯ４５は、情報が両方向に流れることのできる双方向通信エレメントに置換されることになる。本発明のいくつかの実施態様におけるこの双方向フローを、図６のＦＩＦＯ４５に隣接して示す破線矢印８０で表す。他の図には示していないが、同様の双方向通信エレメントが、図４のＦＩＦＯ４０および図５のＦＩＦＯ４５の代わりに使用されることになる。
【００６２】
以上は、階層化カウンターフロー・パイプライン構造に関する我々の発明の実施形態の記述である。添付の特許請求の範囲およびその等価物にさらに定義する本発明の主旨を逸脱することなく、示した特定の構造からの多くの変形物ができることを理解されたい。例えば、本明細書で述べたモジュールは、イベントが遷移として符号化されると暗黙的に仮定して述べたが、他の符号化もまた可能である。
【図面の簡単な説明】
【図１】  逐次的に実行された場合の、各ステージに対する例示的なアルゴリズムにおける３つのステップを示す図である。
【図２】  並行して実行された場合の、ステージに対する同じ３つのステップを示す図である。
【図３】  各々が３層のレイヤからなる一連のパイプライン・ステージと、北行きワードおよび南行きワード用のデータ通信パスを示す図である。
【図４】  「ＧＥＴ」レイヤと、それを次のレイヤに接続するＦＩＦＯの一部を示す図である。
【図５】  「ＣＨＥＣＫ」レイヤと、それをその前および後のレイヤに接続するＦＩＦＯの一部を示す図である。
【図６】  「ＰＲＯＣＥＳＳ」レイヤと、それを前のレイヤに接続するＦＩＦＯの一部を示す図である。
【図１】
0003990537.tif 000002
【図２】
0003990537.tif 000003
【図３】
0003990537.tif 000004
【図４】
0003990537.tif 000005
【図５】
0003990537.tif 000006
【図６】
0003990537.tif 000007