(57)【要約】本発明は、データパイプラインの管理システムに関し、特に、プロデューサおよびコンシューマの両方が、パイプラインへ非同期にアクセスする必要があり、データが非アトミックであり、最後の完全な（および有効な）受信メッセージだけが関連性があり、さらに、パイプラインからの読出し／パイプラインへの書込みを一旦開始したデータは、完全に処理しなければならない、という状況における、単方向データパイプラインに対する最小メモリソリューションに関する。本発明によるデータパイプライン管理システムは、最低３つのエントリの循環キュー、および、最低限６ビット（２×２＋２×１）に収めることができるインデックスの組として実現される、付加的なハンドシェーク機構として実装することができる。プロデューサおよびコンシューマの両方とも、キューにおけるそれらの位置を示す２ビットのインデックスと、特別な状況を示す１ビットの２進値とを有する。両パーティとも、全てのインデックスを読出すことができるが、それら独自に、すなわち、プロデューサはＰおよびｗｒａｐＰのみ、コンシューマはＣおよびｗｒａｐＣのみ書込むことができる。また、ハンドシェーク機構に対する一連の規則を提供する。
2008542897.tif 000002
【特許請求の範囲】
【請求項１】
プロデューサおよびコンシューマと、データ転送用の単方向パイプラインとを備え、前記パイプラインにおける全てのエントリは、前記プロデューサおよびコンシューマがアクセス可能であり、最後のエントリのみが有効で、かつ前記パイプラインへの読出しおよび書込み動作が非同期であるデータパイプライン管理システムにおいて、前記パイプラインが、少なくとも３つのエントリの循環キューとして実現され、さらに、ハンドシェーク機構が、最低６ビットに収まるインデックスの組として用立てられることを特徴とするデータパイプライン管理システム。
【請求項２】
請求項１に記載のデータパイプライン管理システムにおいて、
前記インデックスの組が、プロデューサおよびコンシューマのそれぞれに対する、前記キューにおけるそれらの位置を示す２ビットのインデックスと、プロデューサおよびコンシューマのそれぞれに対する、特別な状況を示す１ビットの２進値とを有することを特徴とするデータパイプライン管理システム。
【請求項３】
請求項１または２に記載のデータパイプライン管理システムにおいて、
前記キューが、共有メモリであることを特徴とするデータパイプライン管理システム。
【請求項４】
請求項１〜３のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記データが非アトミックであることを特徴とするデータパイプライン管理システム。
【請求項５】
請求項１〜４のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記パイプラインが、エントリが３つの循環キューとして実現されることを特徴とするデータパイプライン管理システム。
【請求項６】
請求項１〜５のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記パイプラインが、エントリが４つの循環キューとして実現されることを特徴とするデータパイプライン管理システム。
【請求項７】
請求項１〜６のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記ハンドシェーク機構が、６ビットに収まる一組のインデックスとして設けられることを特徴とするデータパイプライン管理システム。
【請求項８】
請求項１〜７のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記プロデューサをマイクロコントローラとし、かつ、前記コンシューマをサブシステムとするか、または、前記プロデューサをサブシステムとし、かつ、前記コンシューマをマイクロコントローラとすることを特徴とするデータパイプライン管理システム。
【請求項９】
請求項１〜８のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記プロデューサをマイクロコントローラとし、かつ、前記コンシューマをフレックスレイ・データリンク・コントローラとするか、または、前記プロデューサをフレックスレイ・データリンク・コントローラとし、かつ、前記コンシューマをマイクロコントローラとすることを特徴とするデータパイプライン管理システム。
【請求項１０】
請求項１〜９のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記プロデューサをマイクロコントローラとし、かつ、前記コンシューマをローカル・インターコネクト・コントローラとするか、または、前記プロデューサをローカル・インターコネクト・コントローラとし、かつ、前記コンシューマをマイクロコントローラとすることを特徴とするデータパイプライン管理システム。
【請求項１１】
請求項１〜１０のいずれか一項に記載のデータパイプライン管理システムにおいて、
前記プロデューサをマイクロコントローラとし、かつ、前記コンシューマをコントローラ・エリア・ネットワーク・コントローラとするか、または、前記プロデューサをコントローラ・エリア・ネットワーク・コントローラとし、かつ、前記コンシューマをマイクロコントローラとすることを特徴とするデータパイプライン管理システム。
【請求項１２】
プロデューサおよびコンシューマと、データ転送用の単方向パイプラインとを備え、前記パイプラインにおける全てのエントリは、前記プロデューサおよびコンシューマによってアクセス可能であり、最後のエントリのみが有効で、かつ、パイプラインの読出しおよび書込み動作が非同期であるような、データパイプライン管理システムの使用方法において、当該方法が、
‐  少なくとも３つのエントリの循環キューを用立てるステップと、
‐  前記プロデューサおよび前記コンシューマのそれぞれに関連し、前記キューにおけるそれぞれの位置を示す２ビットのインデックスと、前記プロデューサおよび前記コンシューマのそれぞれに関連し、特別な状況を示す１ビットの２進値とを有する、最低限６ビットに収まるインデックスの組として、ハンドシェーク機構を用立てるステップと、
‐  前記プロデューサの２ビットのインデックスを対応する値に設定することによって、キューエントリを前記プロデューサに属するものとしてマークし、かつ前記コンシューマが当該エントリから読出せないようにするステップと、
‐  前記コンシューマの２ビットのインデックスを対応する値に設定することによって、キューエントリを前記コンシューマに属するものとしてマークし、かつ前記プロデューサが当該エントリに書込めないようにするステップと、さらに、
‐  前記プロデューサが、先にインデックスを書込み後に更新する機構を使用し、かつ、前記コンシューマが、先にインデックスを更新し後に読出す機構を使用しているキューにアクセスするステップと、
を含むことを特徴とするデータパイプライン管理システムの使用方法。
【請求項１３】
請求項１２に記載のデータパイプライン管理システムの使用方法において、
前記プロデューサは、それ固有のインデックスの組である２ビットのインデックスＰおよび１ビットの２進値ｗｒａｐＰの変更のみ可能とし、さらに、前記プロデューサが前記キューへアクセスするステップが：
‐  前記コンシューマの２ビットのインデックスＣが、前記プロデューサの２ビットのインデックスＰ＋１に等しい場合、すなわちＣ＝Ｐ＋１の場合には、前記プロデューサが、当該プロデューサの２ビットのインデックスＰに関連する前記キューエントリに書込み、さらに、前記プロデューサの２ビットのインデックスＰをＰ＋２に設定し、前記プロデューサの１ビットの２進値ｗｒａｐＰを、前記コンシューマの前記１ビットの２進値ｗｒａｐＣの否定、すなわちｗｒａｐＰ＝！ｗｒａｐＣに設定するステップと、
‐  Ｃ！＝Ｐ＋１の場合には、Ｐを書込み、さらに、次のインデックス値を、Ｐ＝Ｐ＋１、ｗｒａｐＰ＝ｗｒａｐＣに設定するステップと；
に追従することを特徴とする、データパイプライン管理システムの使用方法。
【請求項１４】
請求項１２または１３に記載のデータパイプライン管理システムの使用方法において、
前記コンシューマは、それ固有のインデックスの組である前記２ビットのインデックスＣおよび前記１ビットの２進値ｗｒａｐＣの変更のみ可能であり、さらに、前記コンシューマが前記キューへアクセスするステップが：
‐  Ｃ＝＝ＰかつｗｒａｐＰ＝＝ｗｒａｐＣである場合は、更新も読出しも実行せず、
‐  Ｃ＝＝Ｐ−１かつｗｒａｐＰ＝＝ｗｒａｐＣである場合は、最も新しいデータインデックス値を、Ｃ＝Ｃ，ｗｒａｐＣ＝ｗｒａｐＣに設定して、Ｃの読出しを実行し、続いて、ｗｒａｐＣ＝＝ｗｒａｐＰの場合は、最も新しいデータインデックス値をＣ＝Ｃ＋１に、さもなければ、Ｃ＝Ｃ，ｗｒａｐＣ＝ｗｒａｐＣに設定することを含む、読出し後の更新が続き、
‐  Ｃ！＝Ｐ−１かつｗｒａｐＰ＝＝ｗｒａｐＣの場合は、最も新しいデータインデックス値を、Ｃ＝Ｐ−１，ｗｒａｐＣ＝ｗｒａｐＣに設定して、Ｃの読出しを実行し、さらに；
‐  Ｃ！＝Ｐ−１かつｗｒａｐＰ！＝ｗｒａｐＣの場合には、最も新しいデータインデックス値を、Ｃ＝Ｐ，ｗｒａｐＣ＝ｗｒａｐＰに設定して、読出しを実行しない、
ステップに追従することを特徴とする、データパイプライン管理システムの使用方法。
【請求項１５】
請求項１２〜１４のいずれか一項に記載のデータパイプライン管理システムの使用方法において、前記コンシューマのインデックスを、読出しの後にも更新することを特徴とするデータパイプライン管理システムの使用方法。
【請求項１６】
請求項１２〜１５のいずれか一項に記載のデータパイプライン管理システムの使用方法において、前記キューが空になった場合、すなわち、Ｃ＝＝ＰおよびｗｒａｐＰ＝＝ｗａｒｐＣの場合に、前記プロデューサを優先することを特徴とするデータパイプライン管理システムの使用方法。
【請求項１７】
コンピュータ可読記憶媒体およびそれに組み込まれたコンピュータ・プログラム機構を含み、コンピュータ装置と共に使用するコンピュータ・プログラムであって、前記コンピュータ・プログラム機構が、前記プログラムを前記コンピュータ装置のメモリにローディングする際に、請求項１２〜１６のいずれか一項に記載のステップを実行することによって、複数のタンパク質のサンプルシーケンスが整列するように構成したモジュールを含む、コンピュータ・プログラム。
【請求項１８】
請求項１２〜１６のいずれか一項に記載の方法を実行するように構成した、コンピュータ装置。
【請求項１９】
請求項１〜１６のいずれか一項に記載のシステムまたは方法を実施するための命令を格納する、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データパイプラインの管理システムに関し、特に、プロデューサおよびコンシューマの両方が、パイプラインへ非同期にアクセスする必要があり、データが非アトミックであり、最後の完全な（および有効な）受信メッセージだけが関連し、さらに、パイプラインからの読出し／パイプラインへの書込みを一旦開始したデータは、完全に処理しなければならない、という状況における、単方向データパイプラインに対する最小メモリソリューションに関する。
【０００２】
ホストプロセッサおよび多数のサブシステムを備える典型的なコンピュータシステムでは、サブシステムへのデータ転送、およびサブシステムからのデータ転送を必要とする。サブシステム間のデータ転送は、ネットワーキングアプリケーションにおいて、しばしばボトルネックとなることが知られている。プロセッサおよびサブシステムは、競合する他のサブシステムまたはプロセッサのタスクのために、インターフェース・バスでの同期コネクションを確立することができなくなる。
【０００３】
特許文献１は、プロセッサに、オペレーションを指定するためのパラメータを非同期に送信および受信可能とさせる、バス・インターフェースの分散パイプを開示している。そのシステムでは、プロセッサおよびサブシステムにおけるメモリが、共有メモリとして用いられ、その共有メモリは、分散型の先入れ先出し（ＦＩＦＯ）循環キューとして構成されている。通信は、要求、応答、および状態情報を表す付加的な自己記述制御エレメントを、パイプに入れることによって行われる。ＦＩＦＯ環境では、古いエントリは、それらが利用できる最新のエントリとなる際に読出されることになるため、高いキュー深度および多くのメモリ要件を必要とする。
【０００４】
本発明は、プロトコルハンドラが、マイクロコントローラと一体化される、ネットワーキングアプリケーションを背景とする。マイクロコントローラは、ネットワーク構成でプロトコルハンドラをプログラムし、さらに、パイプラインをセットアップして、それを介して、データの、プロトコルハンドラへの受け渡しおよび／またはプロトコルハンドラからの受信を行う。リーダおよびライタによる、パイプラインへのデータアクセスは、互いに非同期である。ネットワーク構成は、オンザフライで適合させなければならないこともあるため、ネットワーク構成データおよびデータパイプラインは、プロトコルハンドラそれ自体よりも、むしろ、共有メモリに入れる。このことにより、共有すべきデータのサイズにおける制限が克服される。
【０００５】
マイクロコントローラおよびプロトコルハンドラの両方とも、アトミックアクセス用の共有メモリ領域へ、排他的にアクセスすることができる。このマイクロコントローラに対するアトミックとは、３２ビットのアクセスのことを意味する。しかしながら、２つのアトミックアクセス間にて、他方のパーティが、それ自体のアクセスで割り込むおそれがある。ネットワーク構成データおよびパイプラインにおけるデータの両方とも、（潜在的に）非アトミックである。
【０００６】
データパイプラインは、どちらの方向にもすることができるが、各データパイプラインは、マイクロコントローラのみに読出され、かつ、プロトコルハンドラによって書込まれるか、あるいは、プロトコルハンドラのみに読出され、マイクロコントローラによって書込まれる。この場合、各パイプラインは、１つのプロデューサと１つのコンシューマが存在するだけである。
【０００７】
プロトコルは、メッセージが全部そろった後で、かつ（それがプロトコルハンドラから来たものである場合にのみ）、その有効なメッセージを読取ることができ、その最後の完全なメッセージのみが関連することを要求する。完全に受信されているが、まだ読取られていない他の全てのメッセージは、関連しない。これは、ＦＩＦＯ（先入れ先出し）のような、標準的なキューイング機構とはかなり異なる。この最後のメッセージは、コンシューマだけに排他的に利用されなければならず、かつ、プロデューサに到来するどんな新規のメッセージによっても上書きされてはならない。逆の場合で、まだ完全に受信されていない（かつ検証されていない）着信メッセージを読出すのを開始することができない。
【０００８】
このような問題に対する解決策は、パイプラインを、出入りするデータの比率に応じて深度が決定されるキューとして、必要な大きさにすることである。しかしながらこれは、決定的ではなく、読出しおよび書込み速度が大きく異なる場合は、キューの深度が非常に大きくなり、その結果、メモリ要件が非常に大きくなるか、または、ＣＰＵの負荷が非常に大きくなってしまう。
【０００９】
【特許文献１】米国特許５３２５４９２号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明の目的は、データパイプライン管理システム、およびハンドシェーク機構と共にごく小容量のメモリを用いる、そのシステムの使用方法を提供することにある。
【課題を解決するための手段】
【００１１】
上述の目的を達成するための本発明の一実施態様によれば、プロデューサおよびコンシューマと、データ転送用の単方向パイプラインとを備え、パイプラインにおける全てのエントリは、プロデューサおよびコンシューマがアクセス可能であり、最後のエントリのみが有効で、かつパイプラインへの読出しおよび書込み動作が非同期であるデータパイプライン管理システムにおいて、前記パイプラインが、少なくとも３つのエントリの循環キューとして実現され、さらに、ハンドシェーク機構が、最低６ビットに収まるインデックスの組として用立てられることを特徴とする、データパイプライン管理システムが提供される。前記インデックスの組は、プロデューサおよびコンシューマのそれぞれに対する、前記キューにおけるそれらの位置を示す２ビットのインデックスと、プロデューサおよびコンシューマのそれぞれに対する、特別な状況を示す１ビットの２進値とを有する。前記キューは共有メモリとするのが好適であり、さらに、前記データは非アトミックとすることができる。
【００１２】
好適例において、前記パイプラインは、エントリが３つの循環キューとして実現する。この例は、メモリ要件が最低限に削減されるという利点を有する。
【００１３】
前記プロデューサはマイクロコントローラとし、かつ、前記コンシューマはサブシステムとするか、あるいは、その逆とするのが好適である。
【００１４】
他の好適例では、前記プロデューサはマイクロコントローラとし、かつ、前記コンシューマはフレックスレイ・データリンク・コントローラ（FlexRay（登録商標） Data Link controller）とするか、あるいは、その逆とする。
【００１５】
他の好適例では、前記プロデューサはマイクロコントローラとし、かつ、前記コンシューマは、ローカル・インターコネクト・コントローラとするか、あるいは、その逆とする。
【００１６】
さらに他の好適例では、前記プロデューサはマイクロコントローラとし、かつ、前記コンシューマはコントローラ・エリア・ネットワーク・コントローラとするか、あるいは、その逆とする。
【００１７】
上述した好適例の利点は、増え続ける負荷のために効率的なデータパイプライン管理が重要となっている自動車用の用途に、本発明によるデータパイプライン管理システムを利用できることにある。
【００１８】
また、それに応じて、プロデューサおよびコンシューマと、データ転送用単方向パイプラインとを備え、パイプラインにおける全てのエントリが、プロデューサおよびコンシューマによってアクセス可能であり、最後のエントリのみが有効で、かつ、パイプラインの読出しおよび書込み動作が非同期であるような、データパイプライン管理システムの使用方法が提供され、当該方法は、
‐  少なくとも３つのエントリの循環キューを用立てるステップと、
‐  前記プロデューサおよび前記コンシューマのそれぞれに関連し、前記キューにおけるそれぞれの位置を示す２ビットのインデックスと、前記プロデューサおよび前記コンシューマのそれぞれに関連し、特別な状況を示す１ビットの２進値とを有する、最低限６ビットに収まるインデックスの組として、ハンドシェーク機構を用立てるステップと、
‐  前記プロデューサの２ビットのインデックスを対応する値に設定することによって、キューエントリを前記プロデューサに属するものとしてマークし、かつ前記コンシューマが、当該エントリから読出せないようにするステップと、
‐  前記コンシューマの２ビットのインデックスを対応する値に設定することによって、キューエントリを前記コンシューマに属するものとしてマークし、かつ前記プロデューサが、当該エントリに書込めないようにするステップと、さらに、
‐  前記プロデューサが、ライト・ファースト−アップデート・レーター（write first-update later）機構（先にインデックスを書込み後に更新する機構）を使用し、かつ、前記コンシューマが、アップデート・インデックス・ファースト−リード・レーター（update indices first-read later）機構（先にインデックスを更新し後に読出す機構）を使用しているキューにアクセスするステップと、
を含むことを特徴とする。
【００１９】
本発明による方法は、データのロスを防ぎながら、効率的なデータパイプライン管理のための最小メモリソリューションを、有利に使用可能とする。
【００２０】
前記プロデューサは、それ固有のインデックスの組である２ビットのインデックスＰおよび１ビットの２進値ｗｒａｐＰの変更のみ可能とし、さらに、前記プロデューサが前記キューへアクセスするステップが：
‐  前記コンシューマの２ビットのインデックスＣが、前記プロデューサの２ビットのインデックスＰ＋１に等しい場合、すなわちＣ＝Ｐ＋１の場合には、前記プロデューサが、当該プロデューサの２ビットのインデックスＰに関連する前記キューエントリに書込み、さらに、前記プロデューサの２ビットのインデックスＰをＰ＋２に設定し、前記プロデューサの１ビットの２進値ｗｒａｐＰを、前記コンシューマの前記１ビットの２進値ｗｒａｐＣの否定、すなわちｗｒａｐＰ＝！ｗｒａｐＣに設定するステップと；
‐  Ｃ！＝Ｐ＋１の場合には、Ｐを書込み、さらに、次のインデックス値を、Ｐ＝Ｐ＋１、ｗｒａｐＰ＝ｗｒａｐＣに設定するステップと；
に追従するようにする。
【００２１】
前記コンシューマは、それ固有のインデックスの組である前記２ビットのインデックスＣおよび前記１ビットの２進値ｗｒａｐＣの変更のみ可能であり、さらに、前記コンシューマが前記キューへアクセスするステップが：
‐  Ｃ＝＝ＰかつｗｒａｐＰ＝＝ｗｒａｐＣである場合は、更新も読出しも実行せず、
‐  Ｃ＝＝Ｐ−１かつｗｒａｐＰ＝＝ｗｒａｐＣである場合は、最も新しいデータインデックス値を、Ｃ＝Ｃ，ｗｒａｐＣ＝ｗｒａｐＣに設定して、Ｃの読出しを実行し、続いて、ｗｒａｐＣ＝＝ｗｒａｐＰの場合は、最も新しいデータインデックス値をＣ＝Ｃ＋１に、さもなければＣ＝Ｃ，ｗｒａｐＣ＝ｗｒａｐＣに設定することを含む、読出し後の更新が続き、
‐  Ｃ！＝Ｐ−１かつｗｒａｐＰ＝＝ｗｒａｐＣの場合は、最も新しいデータインデックス値を、Ｃ＝Ｐ−１，ｗｒａｐＣ＝ｗｒａｐＣに設定して、Ｃの読出しを実行し、さらに；
‐  Ｃ！＝Ｐ−１かつｗｒａｐＰ！＝ｗｒａｐＣの場合には、最も新しいデータインデックス値を、Ｃ＝Ｐ，ｗｒａｐＣ＝ｗｒａｐＰに設定して、読出しを実行しない、ステップに追従するようにする。
【００２２】
キューが空になった場合は、前記プロデューサが優先されるのが有利である。
【００２３】
本発明のこれらおよび他の目的、特徴、および利点を、添付図面に示す本発明の好適実施例の、これ以降の詳細な説明により明らかにしていく。
【００２４】
以下、本発明の実施例を、添付図面を参照して説明する。
【発明を実施するための最良の形態】
【００２５】
図１は、本発明によるデータパイプライン管理システム１００を示しており、このシステムは、ハンドシェーク機構１６とともにデータ転送用単方向キュー１４を介して、互いに接続されるプロデューサ１０およびコンシューマ１２を備えており、前記キューにおける全てのエントリは、プロデューサ１０およびコンシューマ１２がアクセス可能であり、最後のエントリのみが有効で、かつ、前記パイプラインへの読出しおよび書込み動作は非同期である。本発明によるデータパイプライン管理システムは、最低３つのエントリ２０のキュー１４として実現することができ、かつ、最低６ビット（２×２＋２×１）に収めることができるインデックスの組１８として、付加的なハンドシェーク機構１６を実現することができる。
【００２６】
プロデューサ１０およびコンシューマ１２の両方とも、キューにおけるそれらの存在場所を示す、対応するインデックスがＰおよびＣにラベル付けされた２ビットのインデックス、ならびに、ｗｒａｐＰおよびｗｒａｐＣで示す、特別な状況を示す１ビットの２進値を有する。両方とも、全てのインデックスを読出すことができるが、それら自体は、すなわち、プロデューサ１０は、ＰおよびｗｒａｐＰのみ、コンシューマ１２は、ＣおよびｗｒａｐＣのみを書込むことができる。
【００２７】
キュー１４は、あらゆる作用に対して、エントリ０が最後の後に続く、すなわち、キューのサイズが最小の３である場合は、エントリ０がエントリ２の後に続くことを意味する循環キュー１４としてみなされる。次のアルゴリズムにおいて、インデックスが２で、かつそのインデックスが１づつ増加する場合は０となり、あるいは、インデックスが２づつ増加する場合は、１となる。
【００２８】
インデックス１８の管理の背景にある考え方は、各エンティティが、それぞれが、必要とするエントリへの排他的アクセスを有しなければならない、という事に基づく。従って、それぞれのインデックスを任意の値に設定することによって、プロデューサ１０は、インデックスをそれ自体のものとしてマークし、かつ、コンシューマ１２をブロックして、そのエントリから読出せないようにする。コンシューマ１２についても、エントリが、読出しのためにマークされ、プロデューサ１０が、そのエントリへの書込みをブロックされること以外は同様である。両方のインデックスが同じ値を有する場合は、プロデューサ１０が優先される。これは、キュー１４が空になった場合にのみ生じることになる。
【００２９】
これは要するに、プロデューサ１０が、「ライト・ファースト−アップデート・インデックス・レーター（Write First-Update Indices Later）」機構を有する一方で、コンシューマ１２が、「アップデート・インデックス・ファースト−リード・レーター（Update Indices First-Read Later）」機構を有することを示す。なお、コンシューマ１２が、そのインデックスを読出しの後にも更新する必要があるという例外が、１つだけ存在する。
【００３０】
本発明による最小メモリソリューションは、キュー１４に対してエントリをただ３つだけ用いるものであり、１つをコンシューマ１２が、１つをプロデューサ１０が、もう１つをバッファ用として用いることができる。しかしながら、そのような最小メモリソリューションは、あらゆる場合にデータが失われないようにするために、精巧なハンドシェーク機構１６を必要とする。大部分のＦＩＦＯとは対照的に、パイプライン全体をメモリマップするので、ハンドシェーク機構１６なしで、どちらの側からも全てのエントリを読出すことができる。各通信パーティの両方が、読出すべくアクセス可能であるが、それぞれが、それ自体のインデックスの組のみを書込むことができるような、キューインデックスの組を、各パーティに対して用いることで、それぞれが、読出すべきおよび／または書込むべき次のエントリを、決定することができる。本発明の効果は、バスアーキテクチャによって、２つのパーティがメモリへ同時にアクセスしないようにすることである。
【００３１】
表１および２は、キュー１４へアクセスするための規則を示している。表１は、プロデューサからキュー１４へのアクセスを示し、ここで、プロデューサ１０は、それ自体のインデックスの組、すなわちＰおよびｗｒａｐＰの変更のみ行うことができる。ＣがＰ＋１に等しい場合は、Ｐの値に関連するキューエントリへの、Ｐの書込みが行われ、次のインデックス値が、Ｐ＝Ｐ＋２に設定され、さらに、ｗｒａｐＰが、ｗｒａｐＣの否定（！ｗｒａｐＣ）に設定される。状況２において、ＣがＰ＋１と等しくない場合、すなわち、記号“！＝”が“等しくない”を意味するとして、Ｃ！＝Ｐ＋１の場合は、Ｐの書込みが行われ、次いで、ＰがＰ＋１に、ｗｒａｐＰがｗｒａｐＣに設定される。
【００３２】
【表１】
2008542897.tif 000003
【００３３】
表２は、コンシューマ１２がキューにアクセスするための規則を示している。コンシューマ１２も、それ自体のインデックスの組、すなわち、２ビットのインデックスＣおよび２進値ｗｒａｐＣの変更のみ行うことができる。表２の列１の、状況３において、ＣはＰに全く等しく（Ｃ＝＝Ｐ）、かつｗｒａｐＰもｗｒａｐＣに全く等しく（ｗｒａｐＰ＝＝ｗｒａｐＣ）、キュー１４が空で、従って、何の読出しも実行されない状況を示している。しかしながら、ＣがＰ−１に等しく、かつｗｒａｐＰがｗｒａｐＣに等しい場合は、読出しが実行される。一般的に、読出しは、インデックスを更新した後に実行される。この非常に特別な状況においては、読出しおよび読出し後の更新が行われるまで、インデックスは変更されない。ｗｒａｐＣがｗｒａｐＰに等しい場合には、ＣはＣ＋１に設定され、その他の場合には、ＣおよびｗｒａｐＣは変更されないままである。読出し動作は、非アトミックであってもよいため、読出し動作の期間中に書込み動作が行われ、後にインデックスの変更が必要となることがある。ＣがＰ−１に等しく、かつｗｒａｐＰがｗｒａｐＣに等しくない場合（状況５）にも、Ｃの読出しが実行される。読出し前に更新される最新のインデックス値は、Ｃ＝Ｃ−１となり、ｗｒａｐＣは変更されない。ＣがＰ−１に等しくなく、かつｗｒａｐＰとｗｒａｐＣとが等しいような状況６においては、ｗｒａｐＣは、変更されず、ＣはＰ−１に設定され、さらに、Ｃの読出しが起こる。ＣがＰ−１に等しくなく、さらにまた、ｗｒａｐＰがｗｒａｐＣに等しくない場合は、読出しは起こらず、従って、最新のデータインデックス値は、Ｃ＝Ｐとなり、さらに、ｗｒａｐＣがｗｒａｐＣに等しくなる。
【００３４】
【表２】
2008542897.tif 000004
【００３５】
図１および２は、キュー１４が、３つのエントリ、すなわち０，１および２の最小長の場合に対する、本発明によるインデックス１８およびキューエントリ２０を示す図である。これは、プロデューサ１０およびコンシューマ１２の両方が、パイプライン１４への非同期アクセスを必要とし、データを非アトミックとすることができ、最後の完全な（および有効な）受信メッセージのみが関連し、さらに、パイプラインからのデータの読出しおよび／またはパイプラインへのデータの書込みが一旦開始すると、そのデータは、完全に処理しなければならない、という状況における、単方向データパイプライン管理のための、最小メモリソリューションである。なお、本発明によるキュー１４は、循環キューとする。
【００３６】
図２は、コンシューマ１２によってキュー１４を読出すためのアルゴリズムの結果を示す図である。第１列の開始位置では、全てのインデックス、すなわちｗｒａｐＰ，ｗｒａｐＣ，ＣおよびＰは、全てゼロとなっている。これは、表２の状況３に相当する。読出しは起こらず、更新は実行されず、かつ、キューのエレメント０は、この状況において優先されるプロデューサ１０（Ｐ）に属するものとしてマークされており、キュー１４は空となっている。
【００３７】
第２列では、ｗｒａｐＣ，ＣおよびｗｒａｐＰはゼロ、Ｐは１であり、言い換えれば、Ｃ＝Ｐ−１、かつｗｒａｐＰがｗｒａｐＣに等しく、これは、表２の状況４に相当する。開始位置において、Ｃが０に等しいため、キューのエントリ０はコンシューマ１２のエントリとしてマークされ、さらに、Ｐが１に等しいため、エントリ１は、プロデューサ１０のエントリとしてマークされている。Ｃの読出しが起こり、キュー１４のエレメント０を空にし、変更する。読出し後の更新が起こり、ｗｒａｐＣがｗｒａｐＰに等しいため、ＣがＣ＋１に設定される。ここで、キュー１４のエントリ１は、コンシューマ１２によってマークされる。
【００３８】
第３列は、表２の状況６に相当する。ｗｒａｐＣ，ＣおよびｗｒａｐＰは、全てゼロであるが、Ｐは２であり、すなわち、Ｃは、Ｐ−１に等しくなく、ｗｒａｐＣは、ｗｒａｐＰに等しい。従って、キューエントリ０がコンシューマ１２に関連し、かつ、キューエントリ２がプロデューサ１０に関連するコンフィギュレーションで始めるとする。最新のインデックス値は、Ｃ＝Ｐ−１、すなわち１であり、ｗｒａｐＣは、不変のままである。この際、キューのエレメント０は、読出しによって空にされて変化し、エレメント１がコンシューマ１２に関連付けられる。
【００３９】
図２の第７列は、キュー１４の循環性が効果的な状況を示す。ここでは、Ｐと、ｗｒａｐＣおよびｗｒａｐＰの両方とがゼロであるが、Ｃが２であり、すなわち、キュー１４のエレメント０がプロデューサ１０によってマークされ、エレメント２がコンシューマ１２によってマークされている。これは、表２の状況４に相当する。キューが循環型のため、ＣはＰ−１に等しく、実際には−１となるか、あるいは、循環キューにおいては２となる。Ｃの読出しが実行され、Ｃが、Ｃ＋１、すなわち２＋１に設定され、このＣは、エントリが３つの循環キューにおいては、０となる。
【００４０】
表１および２には、それぞれ、書込みまたは読出しの後には決して起こり得ない状況を、起こり得ることのある状況とともに示してある。
【００４１】
図３は、キュー１４に書込むための、同様のプロセスを示している。第１列は、表１の状況２に相当する。Ｃがゼロ、かつＰがゼロである。この場合、Ｐが優先される。ＣがＰ＋１に等しくなく、エントリ０へのＰの書込みが起こり、従って、ここで、エレメント１は、プロデューサ１０に対してマークされ、一方で、情報が書込まれているエレメント０は、コンシューマ１２により読出されるようにラベル付けされているため、プロデューサ１０の書込みがブロックされる。従って、次のインデックス値は、Ｐ＝１かつｗｒａｐＰ＝ｗｒａｐＣとなる。
【００４２】
図４および５は、エントリが３つ以上、ここでは、エントリを４つ有するキュー１４における、同様の状況を示す図である。例えば、図４における第１列は、図２の第１列における構成、すなわち、表２に記載した状況３に相当する。
【００４３】
本発明によるアルゴリズムは、特定のプロトコルに限られるものではない。本発明によるアルゴリズムは、以下の条件、すなわち：単方向パイプライン１４、このパイプライン１４における全てのエントリ２０に、プロデューサ１０およびコンシューマ１２がアクセス可能であり、最後のエントリのみが有効で、かつ、読出しおよび書込み動作が非同期である、という条件が検証されている、データ転送を要する一般的なアプリケーションに用いることができる。通信データは、命令、パラメータ、またはシステムに関連する任意の情報を含むことができる。
【００４４】
データパイプライン管理システム１００は、サブシステムを有する任意のホストコンピュータシステムに用いることができる。ホストコンピュータをプロデューサ１０、サブシステムをコンシューマ１２とするか、または、その逆とする。データパイプライン管理システム１００は、ホストと、そのホストに、本発明によるデータパイプライン管理システム１００を介してリンクした多数のサブシステムとを備えるアプリケーションにおいて、用いることもできる。
【００４５】
本発明によるデータパイプライン管理システム１００は、自動車向けの通信システムに用いるのが好適である。例えば、フレックスレイ（FlexRay（登録商標））は、自動車向けの、エラー耐性に優れたシリアルの高速バスである。好適な実施例において、本発明は、マイクロコントローラ間、例えば、ＡＲＭ９と、フレックスレイ・データ・リンク・コントローラ（FlexRay（登録商標） Data Link Controller）DLCとの間の通信に用いられる。この実施例においては、マイクロコントローラをプロデューサ１０とし、DLCをコンシューマ１２とするか、あるいはその逆とする。しかしながら、ローカル・インターコネクト・ネットワーク（Local Interconnect Network）（LIN）コントローラ、またはコントローラ・エリア・ネットワーク（Contoroller Area Network）（CAN）コントローラのような、他の任意のデータリンクコントローラを適用することも可能である。
【００４６】
本発明を、具体的な実施例とともに説明してきたが、種々の修正、変更および変形を、当業者が考えうることは明らかである。従って、上述の実施例は例示にすぎず、制限するものではない。添付の請求の範囲から逸脱することなく、多くの代わりの実施例を設計することが可能である。
【図面の簡単な説明】
【００４７】
【図１】本発明によるデータパイプライン管理システムの概略図である。
【図２】キュー寸法が最小の３つの場合における、本発明によるデータパイプライン管理システムの、読出し前および読出し後のインデックスおよびキューの概略図である。
【図３】キュー寸法が最小の３つの場合における、本発明によるデータパイプライン管理システムの、書込み前および書込み後のインデックスおよびキューの概略図である。
【図４】キュー寸法が４つの場合における、本発明によるデータパイプライン管理システムの、読出し前および読出し後のインデックスおよびキューの概略図である。
【図５】キュー寸法が４つの場合における、本発明によるデータパイプライン管理システムの、書込み前および書込み後のインデックスおよびキューの概略図である。
【符号の説明】
【００４８】
１００  データパイプライン管理システム
１０  プロデューサ
１２  コンシューマ
１４  パイプライン／キュー
１６  ハンドシェーク機構
１８  インデックスの組
２０  キューエントリ
【図１】
2008542897.tif 000005
【図２】
2008542897.tif 000006
【図３】
2008542897.tif 000007
【図４−１】
2008542897.tif 000008
【図４−２】
2008542897.tif 000009
【図５−１】
2008542897.tif 000010
【図５−２】
2008542897.tif 000011
【国際調査報告】
2008542897.tif 000012
2008542897.tif 000013