(57)【特許請求の範囲】
【請求項１】
時間制御される分散型コンピュータシステムによりファンクションモジュールを実行するための最適化された流れ図（Ｐ）を生成する方法であって、
前記分散型コンピュータシステムはFlexRay標準に基づくものであり、構造的な要素の集合として、FlexRayバスを介して接続された少なくとも２つの計算ノードを有しており、機能的な要素として、FTComタスク（＝FTComトランスミッタ、FTComレシーバ）および伝送タスクおよびアプリケーションタスクおよび信号およびメッセージを有しており、
前記の構造的および機能的な要素である計算ノードおよびタスク（ｅi，ｅ1,i，ｅ2,i）は、少なくとも１つの要素クラス（Ｅi，Ｅ1，Ｅ2）に属しており、該要素（ｅi，ｅ1,i，ｅ2,i）は少なくとも部分的に依存関係におかれており、少なくともFTComタスクの要素クラスが存在している、
最適化された流れ図（Ｐ）を生成する方法において、
データ処理装置は、前記FTComタスクの要素クラスにおける要素（ｅi，ｅ1,i，ｅ2,i）間の単純な依存関係および複雑な依存関係を識別してクラス分けし、該要素（ｅi，ｅ1,i，ｅ2,i）を、前記単純な依存関係および複雑な依存関係の対応する依存クラス（Ａi，Ａ1，Ａ2）に対応づけ、
前記データ処理装置は、
ａ）複数のタスクの時間または順序の変更、
ｂ）計算ノードへのタスクの割り当ての変更、
ｃ）複数のタスクの統合による新たなタスクの形成
のうち少なくとも１つを含むコーディネートを、少なくとも１つの依存クラス（Ａi，Ａ1，Ａ2）に対応づけられた要素である計算ノード及びタスク（ｅi，ｅ1,i，ｅ2,i）に対し実行し、その際、複数のFTComタスクが同じタイプ（FTComトランスミッタ、FTComレシーバ）であるとき、同じ計算ノードに割り当て可能であるとき、同じ送信ノードと受信ノードをもつとき、及び同じスタート時点を有するときは、該複数のFTComタスクを、単純な依存性をもつ依存クラスに対応づけてコーディネートし、
前記コーディネートを通じて複数の流れ図（Ｐ′）を生成し、
前記データ処理装置は、流れ図の設計目的に依存する品質判定基準に基づき前記複数の流れ図（Ｐ′）を評価して、最適化された流れ図（Ｐ）を選択し、
前記最適化された流れ図（Ｐ）がまえもって定められた境界条件（Ｒ）を満たしている場合は、該最適化された流れ図を最終的な最適化された流れ図（Ｐ）として特定し、
前記最適化された流れ図（Ｐ）がまえもって定められた境界条件（Ｒ）を満たしていない場合は、前記最適化された流れ図（Ｐ）を基礎として、前記コーディネート及び前記生成、並びに、前記評価及び前記選択を繰り返す、
ことを特徴とする、
最適化された流れ図（Ｐ）を生成する方法。
【請求項２】
請求項１記載の方法において、
前記データ処理装置は、少なくとも１つの依存クラス（Ａ1）の要素（ｅ1,i）を完全にコーディネートしてから、少なくとも１つの別の依存クラス（Ａ2）の要素（ｅ2,i）をコーディネートすることを特徴とする方法。
【請求項３】
請求項１または２記載の方法において、
前記データ処理装置は、少なくとも１つの依存クラス（Ａi，Ａ1，Ａ2）の要素（ｅi，ｅ1,i，ｅ2,i）のコーディネートにおいて、１つの要素クラス（Ｅi，Ｅ1，Ｅ2）に属する要素を別個にコーディネートし、またはそれぞれ異なる複数の要素クラス（Ｅi，Ｅ1，Ｅ2）の要素（ｅi，ｅ1,i，ｅ2,i）を組み合わせてコーディネートすることを特徴とする方法。
【請求項４】
請求項１から３のいずれか１項記載の方法において、
前記データ処理装置は、バスの負荷、流れ図の周期時間、伝送すべきメッセージ数、必要とされる計算ノード数、（部分）機能の最悪実行時間（WCET）のうち、少なくとも１つの品質判定基準を最適化のために用いることを特徴とする方法。
【請求項５】
請求項１から４のいずれか１項記載の方法において、
前記データ処理装置は、少なくとも１つの依存クラス（Ａi，Ａ1，Ａ2）内で最適化を繰り返し実行し、各反復ステップにおいて前記依存クラス（Ａi，Ａ1，Ａ2）の選択された要素（ｅi，ｅ1,i，ｅ2,i）をコーディネートし、該依存クラス（Ａi，Ａ1，Ａ2）においてコーディネート可能なすべての要素（ｅi，ｅ1,i，ｅ2,i）がコーディネートされるまでの回数だけ、前記反復ステップを実行することを特徴とする方法。
【請求項６】
請求項５記載の方法において、
前記データ処理装置は、前記反復ステップのうち少なくとも１つのステップを、１つの依存クラス（Ａi，Ａ1，Ａ2）から選択されたそれぞれ別の要素を用いて複数回実行し、該ステップに続く反復ステップを、実行済みの反復ステップにおいて最良の最適化結果を達成したコーディネート済みの選択された要素を用いて続けることを特徴とする方法。
【請求項７】
請求項１から６のいずれか１項記載の方法において、
前記データ処理装置は、前記流れ図（Ｐ）の最適化中、まえもって定められたおよび／またはシステムに内在する境界条件（Ｒ）の遵守をチェックすることを特徴とする方法。
【請求項８】
請求項１記載の方法において、
前記データ処理装置は、前記単純な依存性のクラスにおける要素のコーディネートを前記複雑な依存性のクラスにおける要素のコーディネートの前に行なうことを特徴とする方法。
【請求項９】
請求項１記載の方法において、
前記データ処理装置は、複数のFTComタスクが同じタイプ（FTComトランスミッタ、FTComレシーバ）であるとき、同じアプリケーションノードに割り当てることができるとき、および該複数のFTComのスタートタイムインターバルがオーバラップしているとき、該複数のFTComタスクを、複雑な依存性をもつ依存クラスに対応づけてコーディネートすることを特徴とする方法。
【請求項１０】
請求項１または９記載の方法において、
前記データ処理装置は、複数の伝送タスクの共通の信号がFlexRayメッセージ（フレーム）の最大長を超えていないとき、および前記複数の伝送タスクのスタート時点が同一であるとき、該複数の伝送タスクを、単純な依存性をもつ依存クラスに割り当ててコーディネートすることを特徴とする方法。
【請求項１１】
請求項９または１０記載の方法において、
前記データ処理装置は、複数の伝送タスクの共通の信号がFlexRayメッセージ（フレーム）の最大長を超えていないとき、同じ送信側アプリケーションノードに割り当てることができるとき、および前記複数の伝送タスクのスタートタイムインターバルがオーバラップしているとき、該複数の伝送タスクを、複雑な依存性をもつ依存クラスに割り当ててコーディネートすることを特徴とする方法。
【請求項１２】
請求項９または１０記載の方法において、
前記データ処理装置は、付加的に、複数の伝送タスクおよび／または複数のFTComタスクのスタート時点が所定の値よりも大きく互いに異なっていなければ、該複数の伝送タスクまたは該複数のFTComタスクを、複雑な依存性をもつ依存クラスに対応づけてコーディネートすることを特徴とする方法。
【請求項１３】
時間制御される分散型コンピュータシステムによりファンクションモジュールを実行するための最適化された流れ図（Ｐ）を生成するためのコンピュータプログラムであって、
前記分散型コンピュータシステムはFlexRay標準に基づくものであり、構造的な要素の集合として、FlexRayバスを介して接続された少なくとも２つの計算ノードを有しており、機能的な要素として、FTComタスク（＝FTComトランスミッタ、FTComレシーバ）および伝送タスクおよびアプリケーションタスクおよび信号および／またはメッセージを有しており、
前記の構造的および機能的な要素である計算ノードおよびタスク（ｅi，ｅ1,i，ｅ2,i）は、少なくとも１つの要素クラス（Ｅi，Ｅ1，Ｅ2）に属しており、該要素（ｅi，ｅ1,i，ｅ2,i）は少なくとも部分的に依存関係におかれており、少なくともFTComタスクの要素クラスが存在している、
最適化された流れ図（Ｐ）を生成するためのコンピュータプログラムにおいて、
データ処理装置が、前記FTComタスクの要素クラスにおける要素（ｅi，ｅ1,i，ｅ2,i）間の単純な依存関係および複雑な依存関係を識別してクラス分けし、該要素（ｅi，ｅ1,i，ｅ2,i）を、前記単純な依存関係および複雑な依存関係の対応する依存クラス（Ａi，Ａ1，Ａ2）に対応づける手順と、
前記データ処理装置が、
ａ）複数のタスクの時間または順序の変更、
ｂ）計算ノードへのタスクの割り当ての変更、
ｃ）複数のタスクの統合による新たなタスクの形成
のうち少なくとも１つを含むコーディネートを、少なくとも１つの依存クラス（Ａi，Ａ1，Ａ2）に対応づけられた要素である計算ノードおよびタスク（ｅi，ｅ1,i，ｅ2,i）に対し実行し、その際、複数のFTComタスクが同じタイプ（FTComトランスミッタ、FTComレシーバ）であるとき、同じ計算ノードに割り当て可能であるとき、同じ送信ノードと受信ノードをもつとき、および同じスタート時点を有するときは、該複数のFTComタスクを、単純な依存性をもつ依存クラスに対応づけてコーディネートする手順と、
前記コーディネートを通じて複数の流れ図（Ｐ′）を生成する手順と、
前記データ処理装置が、流れ図の設計目的に依存する品質判定基準に基づき前記複数の流れ図（Ｐ′）を評価して、最適化された流れ図（Ｐ）を選択する手順と、
前記最適化された流れ図（Ｐ）がまえもって定められた境界条件（Ｒ）を満たしている場合は、該最適化された流れ図を最終的な最適化された流れ図（Ｐ）として特定する手順と、
前記最適化された流れ図（Ｐ）がまえもって定められた境界条件（Ｒ）を満たしていない場合は、前記最適化された流れ図（Ｐ）を基礎として、前記コーディネートおよび前記生成、並びに、前記評価および前記選択を繰り返す手順とを実行する、
ことを特徴とする、
最適化された流れ図（Ｐ）を生成するためのコンピュータプログラム。
【請求項１４】
時間制御される分散型コンピュータシステムによりファンクションモジュールを実行するための最適化された流れ図（Ｐ）を生成するためのコンピュータプログラムが格納された記憶媒体であって、
前記分散型コンピュータシステムはFlexRay標準に基づくものであり、構造的な要素の集合として、FlexRayバスを介して接続された少なくとも２つの計算ノードを有しており、機能的な要素として、FTComタスク（＝FTComトランスミッタ、FTComレシーバ）および伝送タスクおよびアプリケーションタスクおよび信号およびメッセージを有しており、
前記の構造的および機能的な要素である計算ノードおよびタスク（ｅi，ｅ1,i，ｅ2,i）は、少なくとも１つの要素クラス（Ｅi，Ｅ1，Ｅ2）に属しており、該要素（ｅi，ｅ1,i，ｅ2,i）は少なくとも部分的に依存関係におかれており、少なくともFTComタスクの要素クラスが存在している、
最適化された流れ図（Ｐ）を生成するためのコンピュータプログラムが格納された記憶媒体において、
前記コンピュータプログラムにより、
データ処理装置が、前記FTComタスクの要素クラスにおける要素（ｅi，ｅ1,i，ｅ2,i）間の単純な依存関係および複雑な依存関係を識別してクラス分けし、該要素（ｅi，ｅ1,i，ｅ2,i）を、前記単純な依存関係および複雑な依存関係の対応する依存クラス（Ａi，Ａ1，Ａ2）に対応づける手順と、
前記データ処理装置が、
ａ）複数のタスクの時間または順序の変更、
ｂ）計算ノードへのタスクの割り当ての変更、
ｃ）複数のタスクの統合による新たなタスクの形成
のうち少なくとも１つを含むコーディネートを、少なくとも１つの依存クラス（Ａi，Ａ1，Ａ2）に対応づけられた要素である計算ノード及びタスク（ｅi，ｅ1,i，ｅ2,i）に対し実行し、その際、複数のFTComタスクが同じタイプ（FTComトランスミッタ、FTComレシーバ）であるとき、同じ計算ノードに割り当て可能であるとき、同じ送信ノードと受信ノードをもつとき、および同じスタート時点を有するときは、該複数のFTComタスクを、単純な依存性をもつ依存クラスに対応づけてコーディネートする手順と、
前記コーディネートを通じて複数の流れ図（Ｐ′）を生成する手順と、
前記データ処理装置は、流れ図の設計目的に依存する品質判定基準に基づき前記複数の流れ図（Ｐ′）を評価して、最適化された流れ図（Ｐ）を選択する手順と、
前記最適化された流れ図（Ｐ）がまえもって定められた境界条件（Ｒ）を満たしている場合は、該最適化された流れ図を最終的な最適化された流れ図（Ｐ）として特定する手順と、
前記最適化された流れ図（Ｐ）がまえもって定められた境界条件（Ｒ）を満たしていない場合は、前記最適化された流れ図（Ｐ）を基礎として、前記コーディネート及び前記生成、並びに、前記評価及び前記選択を繰り返す手順、
とを実行することを特徴とする、
最適化された流れ図（Ｐ）を生成するためのコンピュータプログラムが格納された記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時間制御される分散型コンピュータシステムによって機能を実行するための最適化された流れ図を生成する方法に関する。この場合、分散型コンピュータシステムおよび機能は少なくとも１つの要素クラスの（たとえば構造的および機能的な）複数の要素から成る集合を有しており、これらの要素は（少なくとも部分的に）互いに依存関係にある。さらに本発明は、上述の方法を実施するためのコンピュータプログラムにも関する。
【０００２】
ここで対象とする形式の分散型コンピュータシステムはかなり以前から知られており、このようなシステムはほとんどすべての技術分野において利用されることが多くなっており、殊に空間的に広がった複合的ないしは複雑なプロセスに対し広い意味で制御を及ぼすべき分野において利用が増大している。
【０００３】
現在の測定技術システム、閉ループ制御技術システムおよび開ループ制御技術システムにおいては、分散されたセンサ機構およびアクチュエータ機構を備えた中央コンピュータシステムが分散型コンピュータシステムに置き換えられることがかなり多く、このような分散型コンピュータシステムの場合、空間的に分散された複数の計算ノードがプロセス制御のタスクを担っており、個々の計算ノードを介してダイレクトに、つまり短い経路で、対応するセンサおよびアクチュエータを用いて、制御すべきプロセスと結びつけられている。通常、１つのプロセス全体を構成するローカルなサブプロセスは機能的に互いに結合されているので、それらのサブプロセスに対応づけられた計算ノードをデータチャネルを介して互いに接続するのが有用であるし、あるいはそれどころか必要であり、このようにすることでたとえば計算ノードすべてが利用できるわけではないプロセスを記述する状態量を各計算ノード間で交換することができ、したがってそれらをローカルで任意の計算ノードからプロセス制御のために利用することができる。
【０００４】
適用分野に応じて分散型コンピュータシステムに対し様々な要求が課されており、それらの要求はたとえば、データチャネルを介したデータスループット、アーキテクチャおよび機能の点での拡張性、通信のセキュリティないしはフォールトトレランス、分散型コンピュータシステムに実装される機能の安全なタイムスケジューリング性能、さらにはデータチャネルの物理的伝送媒体などである。
【０００５】
分散型コンピュータシステムに対する部分的には相反するこのような要求に基づき、これまでに様々なシステムが構築されてきた。それらのシステムは上述の要求をまったく異なる手法で達成するものであり、たとえばここで挙げるとすればLIN, CAN, TTCAN, MOST, Bluetooth, Byteflight, TTP, FlexRayなどである。
【０００６】
上述の例からわかるように、分散型コンピュータシステムの計算ノードを電子的な経路を介して一般的な意味で計算を実行可能な任意の技術的なユニットとすることができるし、計算ノードをセンサとアクチュエータが接続された制御装置とすることもでき、さらには簡単な家庭用インストレーションシステムにおける性能のかなり低いフィールド機器あるいはシミュレーションコンピュータにおけるきわめて高性能のモジュールとしてもよい。
【０００７】
分散型コンピュータシステムにおける計算ノードの適用分野および正確な技術的形態はあまり重要ではないのと同様、各計算ノードを接続するデータチャネルの形態も重要ではない。ここで重要なのは、計算ノードが（物理的におよび利用される通信プロトコルの点で任意に構成された）データチャネルを介してメッセージを交換できる点だけである。
【０００８】
セキュリティ要求を厳しくしたダイナミックスの高い分野（KFZ, Avionik, X-by-Wireアプリケーション）では、TTCAN (Time-Triggered CAN), TTP (Time-Triggered Protocol), FlexRayといった時間制御される分散型コンピュータシステムが頻繁に適用されるようになってきており、個々の計算ノードにおける機能実行および各計算ノード間のデータチャネルを介したデータ交換に係わる上記システムの時間特性を（少なくとも一部では）スケジューリング可能および設定可能であるので、時間特性も保証することができる。
【０００９】
時間制御される分散型コンピュータシステムのデータチャネルを介した通信を所定の時間配分でイベント制御することもたしかに可能であって、すなわち偶発的あるいはランダムなイベントやプロセスのために任意のやり方によりデータチャネルをうまく規定された特定のタイムインターバル（タイムスライス、スロット）で占有させることもできるけれども、分散型コンピュータシステムの各計算ノード間における情報交換のためのデータチャネルの占有は別のタイムインターバルで固定的にスケジューリングないしはプラニングされている。つまり、各計算ノードにおける機能および各計算ノード間で行われる通信をイベントトリガにより実行するためには設定されていないタイムスペースにおいて、まえもって厳密に定められた計算ノードは、厳密に規定された時点でのみ厳密に定義されたメッセージを厳密に規定されたターゲットへ送信することを許可されており、各計算ノード間におけるイベントトリガ型のデータ交換はそのような時点では抑圧されるので、これを確実に行うこともできる。これらの特性ゆえに、時間制御される分散型コンピュータシステムはたとえば時間的に離散した走査システムの実現にも適している。このような走査システムが基礎とするのは、（たとえば他の計算ノードの）目下の入力値の受信、出力値／信号の計算ならびに出力値の送出を厳格に周期的なシーケンスで行うことである。
【００１０】
時間制御されるコンピュータシステムの時間特性の設定は一般に流れ図ないしはフローチャート（スケジュール）を通して行われ、この流れ図には、分散型コンピュータシステムのうちいずれの要素を決められたいずれの時間シーケンスにおいて実行するのか、さらにこのコンピュータシステムによって実行すべき機能のいずれの要素を実行するのかが厳密に規定されている。
【００１１】
容易に想像できるとおりこの種の流れ図の設計は、たとえば機能要素つまりサブファンクションを構造要素つまり計算ノードもしくは１つの計算ノードのサブユニットに対応づけるために、あるいはたとえば機能要素を時間的に互いに並置するために、膨大な数の自由度があることから、把握および解決がきわめて難しい問題となっており、殊に何らかの有効なソリューションをその流れ図について可能なすべてのソリューションの集合から見つけ出そうとする場合だけでなく、特定の判定基準に従い最適なソリューションを見つけ出す場合も、きわめて困難な問題となっている。
【００１２】
従来技術により知られているのはたとえば、この種の流れ図の設計を容易にするためにグラフィカルなプラニングエディタないしはスケジューリングエディタを利用することである。このようなスケジューリングエディタによって、スケジューリングすべき分散型コンピュータシステムにおける個々の構造要素および機能要素をビジュアルなかたちでグラフィカルに互いに関連づけて、１つの時間シーケンス全体とすることができる。ただしこの場合、スケジューリングは付加的にいわゆる最悪実行時間分析Worst-Case-Execution-Time-Analyse (WCET-Analyse)により支援され、その結果が特定の計算ノードにおいて１つの機能（アプリケーション、通信）を実行するのに必要とされる時間の記述となる（Ringler, T.:" Entwicklungswerkzeug fuer zeitgesteuerte Systeme（時間制御システム用開発ツール）", Automotive Engineering Partners, 6/2001, p.54-56）。
【００１３】
また、最適化された流れ図を自動生成するために遺伝的アルゴリズムを利用することも知られている（DE 102 11 517 A1）。この方法は、ある流れ図について可能な１つのソリューションからスタートし、その流れ図を複数のランダムプロセスないしは偶発的なプロセスにより変更する。それらのランダムプロセスから取得された複数の流れ図に対するさらに別の可能なソリューションに対し品質評価が行われ、その際に最も適切な１つまたは複数の流れ図に対しさらに別のランダムバリエーション、評価ならびに選択が行われる。このプロセスを続行することにより、１つの任意の完全な初期ソリューションからスタートして、すなわち時間制御される分散型コンピュータシステムのすべての要素をその機能とともに含むソリューションから出発して、サーチプロセスが最終的に中止されるまで繰り返し「いっそう良好な」ソリューションが見つけ出される。この方法において欠点となるのはたとえば、流れ図について１つまたは複数の（完全な）ソリューションが最適化の出発点として存在していなければならず、その際、スタートソリューションを評価することはできない点にあり、また、スタートソリューションをどのようにして見つけ出すべきであるのかも不確かである。
【００１４】
本発明の課題は、分散型コンピュータシステムのための最適化された流れ図の生成にあたり、これまで述べてきた欠点を少なくとも部分的に回避することにある。
【００１５】
本発明によれば上述の課題は、分散型コンピュータシステムおよび機能が少なくとも１つの要素クラスの複数の要素から成る集合を有し各要素が少なくとも部分的に依存関係にある、時間制御される分散型コンピュータシステムにより機能を実行するための最適化された流れ図の生成方法において、各要素間の依存性を識別しクラス分けして、各要素を対応する依存クラスに割り当て、流れ図の最適化を少なくとも１つの依存クラスの要素をコーディネートすることにより行うことによって解決される。
【００１６】
従来技術により知られている方法とは異なり本発明による方法によれば、分散型コンピュータシステムの要素と分散型コンピュータシステムにおいて実行すべき機能の要素の分析が先に行われる。分散型コンピュータシステムの要素とはたとえばその計算ノードであり、場合によっては別個に応答可能な計算ノードのサブユニットたとえばＩ／Ｏグループ、ＣＰＵ、通信コントローラおよびデータチャネルインタフェースなどである。
【００１７】
時間制御される分散型コンピュータシステムにおいて実行すべき機能の要素とはファンクションモジュールであって、そのようなファンクションモジュールに該当するのは、たとえば制御アルゴリズムなどのアプリケーションの計算、分散型コンピュータシステムにおける他の計算ノードとの時間制御される通信の実行たとえば時間制御されるメッセージの送信および受信である。これらの構造的および機能的な要素を対応する要素クラスに対応づけることができ、このようにすることでたとえば、信号送信の役割を担うすべての機能的要素により送信ファンクションの要素クラスが形成され、計算ノードにおけるアプリケーションの計算の役割を担うすべての要素によりアプリケーションファンクションの要素クラスが形成される。
【００１８】
本発明による方法は特定の要素クラスに合わせて規定されたものではないし、それらに限定されるものでもなく、むしろ多種多様な任意の要素クラスを形成することができ、要素クラスの定義は本発明による方法のユーザの役目である。
【００１９】
本発明により明らかにされたのは、要素クラスの各要素は互いに依存している可能性があり、つまり互いにある特定の関係におかれているかもしれないし、あるいはまったく関係がないかもしれないことであり、このことは同じ要素クラスに属する要素についても異なる要素クラスに属する要素についてもあてはまる。
【００２０】
たとえばアプリケーションファンクションの要素クラスに属する要素は、最初のアプリケーションファンクションを利用して算出された出力値が他のアプリケーションファンクションの入力値として用いられる場合には、互いに依存している。したがって別のアプリケーションファンクションの出力値を入力値として利用するアプリケーションファンクションの依存クラスと、そのような入力値には依存していないアプリケーションファンクションの依存クラスとを区別することができる。
【００２１】
時間制御される分散型コンピュータシステムの要素およびその機能を所定の依存性判定基準に従いクラス分けする一方、その結果として得られた依存クラスにより、さらには少なくとも１つの依存クラスに要素のコーディネートを制限することにより、本発明によれば流れ図の最適化を要素の有用な部分集合のみのコーディネートにより開始することができる。本発明による方法のためには、従来技術により知られている方法とは異なり、すでに存在する完全な流れ図から出発する必要はなく、要素の部分集合だけを最適化していくことで流れ図を段階的に発展させていくことができる。
【００２２】
ここで「要素のコーディネート」とはごく一般に、プロセスａ）複数の要素の編成／統合の変更、プロセスｂ）この変更の評価、ならびにプロセスｃ）１つまたは複数の変更の選択のことである。複数の要素の編成の変更を単に複数の要素の時間または位置に関する再ソートとすることができが、これに加えて、編成された複数の要素の統合により新たな１つの要素を形成することもできる。
【００２３】
複数の要素の編成の変更それ自体は、決定論的な最適化方法において最適化法自体により定められている。これに対し確率論的な最適化法を適用し遺伝的アルゴリズムも利用する場合、要素編成の複数の変更がランダムイベントごとに行われ、ついで得られた複数の変更が品質判定基準の適用により評価される。次に、１つまたは複数の最良の最適化結果が以降のコーディネートステップにおいて漸次、改善されていく。
【００２４】
要素のコーディネートによる流れ図最適化のための品質判定基準として様々な量が適しており、適切な１つの品質判定基準の選択は最終的に、最適化された流れ図の生成にとって重要であるとみなされる設計目的に依存する。可能な品質判定基準をたとえば、バスの負荷、流れ図の持続時間ないしは周期時間、伝送すべきメッセージの個数、必要とされる計算ノードの個数、コンピュータシステムにおいて実行すべき機能もしくは計算ノードにおいて実行すべきサブ機能の最悪実行時間に基づくものとすることができる。
【００２５】
本発明の第１の有利な実施形態によれば本発明による方法は、少なくとも１つの依存クラスの要素が完全にコーディネートされてから、別の依存クラスの要素がコーディネートされるように構成されている。ここで「完全に」という表現を絶対的なものとして、ないしはまったく完全なものとして捉えるべきではない。それというのも、実際には要素をすべてはコーディネートできないことが十分に起こり得るからである。したがって「完全に」とは、「実行可能であるかぎりまたは問題が容認されるかぎり完全に」という意味で捉えるべきである。このような措置により、本発明による方法により得られた流れ図最適化の明快さが、意味の与えられた要素の部分集合（依存クラス）のコーディネートにより首尾一貫して維持される。このようなやり方で１つの依存クラスのコーディネートから新たな依存クラスへと移るとき、すでにコーディネートされた依存クラスの要素をコーディネートにおいてもはや考慮する必要がなく、それらの要素は同様に部分的に設計された流れ図における固定ポイントとして扱われる。
【００２６】
本発明による方法のさらに別の有利な実施例によれば、少なくとも１つの依存クラスにおける要素のコーディネートにあたり、それぞれ同じ要素クラスに属する要素が別個にコーディネートされる。このやり方は特定の要素クラスにおいて、たとえば同種の通信機能のコーディネートにおいて、殊に有利であると判明した。このことが好適となるのは、複数の送信ファンクションが同一のノードから同一のノードへ重なり合ったタイムインターバル内でメッセージとしてまとめられた信号を送る場合である。このケースでは、各信号を別個に１つの固有のメッセージによりデータチャネルを介して送信する必要はなく、ただ１つのメッセージに複数の信号が統合されるようになり、このただ１つのメッセージは、合成信号のために単一のメッセージ（フレーム）内にスペースがあるかぎり、単一の送信ファンクションによって送信することができる。
【００２７】
これに対し本発明による方法の別の有利な実施例によれば、要素のコーディネートにあたりそれぞれ異なる要素クラスの要素を組み合わせてコーディネートするのが有利である。これについて例を挙げると、アプリケーションファンクションの要素クラスに属する要素が計算ノードの要素クラスに属する要素といっしょに組み合わせられてコーディネートされる。このようにして組み合わせられたコーディネートによらなければ、特定の計算ノードと結びついているアプリケーションファンクションを本来設定されていたものとは異なる計算ノードへ割り当てることができない。
【００２８】
少なくとも１つの依存クラス内で最適化を反復して実行すれば、本発明による方法を殊に明快なかたちで実行することができる。この場合、各ステップでは依存クラスの選択された要素すなわち部分集合だけがコーディネートされる。ここで有利であるのは、依存クラスのすべての要素がコーディネートされるまでの回数だけ、もしくは依存クラスの別の要素がもはやコーディネート不可能となるまでの回数だけ、反復ステップが実行される。ここでも実際にすべての要素がコーディネートされるか否かは、提起されている問題に左右される。
【００２９】
依存クラスの複数の要素から第１の選択対象を決めることにより、本発明による方法を用いて理論的に達成可能なソリューションの量ないしは集合が制限される。なぜならば、この依存クラスに属する第１の選択対象の要素と、この依存クラスに属するこれらの要素に続く部分集合の要素のコーディネートすなわち交換、対応づけ、融合は不可能だからである。
【００３０】
本発明による方法の１つの別の実施形態によれば、１つの反復ステップ内で１つの依存クラスに属する他の選択要素を用いてそれぞれ複数回、コーディネートを実行し、後続の反復ステップを、それよりも前の反復ステップで最良の最適化結果を達成したコーディネート済みの選択要素を用いて続ければ、１つの最適化された流れ図のソリューション集合全体から比較的多くのソリューション集合を得ることができる。基本的に、本発明による方法のこの変形実施形態によれば流れ図の最終的な最適化結果を、各反復ステップにおいてただ１つの選択要素を用いて処理した場合よりも向上させることができるが、本発明による方法を実施するためにはそれ相応に実行時間が長くなることを考慮しなければならない。
【００３１】
本発明による方法のさらに別の有利な実施形態によれば流れ図の最適化中、達成された（部分）結果に対して一貫性チェックが実行され、このチェックは殊に、まえもって定められた境界条件および／またはシステムに内在する境界条件の遵守のチェックに向けられたものである。ユーザによりたとえば、ある特定のアプリケーションファンクションがコンピュータネットワークのある特定の計算ノードにおいて計算されるように設定することができる。たとえばこのことが有用となる可能性があるのは、このアプリケーションファンクションの計算結果を該当する計算ノードにおける特定のＩ／Ｏインタフェースを介してダイレクトに出力すべき場合であり、これはたとえばこの計算ノードだけしかこのＩ／Ｏインタフェースを利用できないなどの理由による。一貫性チェックが失敗に終わった場合には先行の最適化ステップもしくはコーディネートステップが廃棄され、変更された別のコーディネートステップと置き換えられる。
【００３２】
本発明による方法の１つの有利な実施形態によれば、時間制御された分散型コンピュータシステムもしくはそのコンピュータシステムに実装された機能の要素または選択された要素は、単純な依存性のクラスあるいは複雑な依存性のクラスに対応づけられる。単純な依存性には、それぞれ別の要素の状態または出力値には左右されないすべての要素が存在する。
【００３３】
たとえば２つのアプリケーションファンクションが単に１つの第３のアプリケーションファンクションだけしか供給しないのであれば、これら両方のアプリケーションファンクションは単純な依存関係にある。ただし第１のアプリケーションファンクションが間接的に第２のアプリケーションファンクションを介して第３のアプリケーションファンクションを供給するのであれば、第１のアプリケーションファンクションと第２のアプリケーションファンクションは複雑な依存関係にある。
【００３４】
単純な依存性のクラスと複雑な依存性のクラスを区別するのが有用であるのは、互いに単純にしか依存し合っていない要素は実際に任意に対応づけもしくは統合によりコーディネートできるからである。これに対し互いに複雑に依存し合っている要素は、たとえば同時に実行するという意味においては、統合することはできない。なぜならば、これらの要素における１つ要素を他の要素よりも前に適時に実行しなければならず、そのようにすることで他の要素が第１の要素の状態もしくは出力をその計算に利用できるようになるからである。
【００３５】
本発明による方法の上述の実施例において格別有利であるのは、単純な依存性のクラスにおける要素のコーディネートを複雑な依存性のクラスにおける要素のコーディネートの前に行うことである。
【００３６】
１つの有利な実施例によれば本発明による方法は、FlexRay標準をベースとしFlexRayバスを介して接続された少なくとも２つの計算ノードを有する時間制御される分散型コンピュータシステムによって利用される。この場合、流れ図の最適化に利用される要素クラスには、FTComタスク、伝送タスク、アプリケーションタスク、信号、メッセージならびに計算ノードというクラスのうち少なくとも１つのクラスが含まれており、その際、FTComタスクのクラスはFTComトランスミッタタスクとFTComレシーバタスクというクラスに分けられている。ここで使用した用語は、FlexRayシステムのハードウェアコンポーネントおよびソフトウェアコンポーネントにおける一般的な名称である。
【００３７】
FTComタスクは、計算ノード側でその計算ノードに割り当てられている通信コントローラのバッファへの書き込みまたはバッファからの読み出しに用いられるのに対し、伝送タスクはバス側におけるメッセージ伝送に用いられる。用語「タスク」とは、ここではオペレーションシステムのタスクという意味で狭く捉えるべきでなく、つまりオペレーションシステムによりスケジューリング可能および実行可能な最小単位という意味で捉えるべきではなく、むしろ抽象的なファンクションの意味でも捉えることができる。この場合、この種のファンクションはスケジューリングに従い（オペレーションシステムの）タスクとして個別に実行され、あるいは既述のコーディネートを行った後で複数のファンクションがいっしょにまとめられて（オペレーションシステムの）タスクとして実行される。
【００３８】
FlexRayシステムにおける流れ図の最適化にあたり最大限に可能なフレキシビリティを達成する目的で、コーディネートの準備処理のためにFlexRayシステムの信号各々に１つの固有のFlexRayメッセージが割り当てられ、このメッセージは１つの固有のFTComタスクと結びつけられている。このようにするだけで、流れ図を最適化するための最大限の自由度が確保される。
【００３９】
これまで述べてきた方法の１つの格別有利な実施形態によれば、複数のFTComタスクが同じタイプ（FTComトランスミッタまたはFTComレシーバ）であるとき、それらを同じアプリケーションノードに割り当てることができるとき、および送信側計算ノードと受信側計算ノードの同じペアを有するとき、もしくは同じ送信ノードと受信ノードを有するとき、それら複数のFTComタスクは単純な依存性の依存クラスに対応づけられてコーディネートされる。最も簡単なケースでは、同じ特性を有するFTComタスクがコーディネートされるのは、それらのスタート時点が一致している場合である。
【００４０】
これに対し、複数のFTComタスクが上述のように同じタイプ（FTComトランスミッタ、FTComレシーバ）であるとき、それらを同じアプリケーションノードに割り当てることができるとき、およびそれらのFTComのスタートタイムインターバルがオーバラップしているとき、それら複数のFTComタスクは複雑な依存性をもつ依存クラスに対応づけられてコーディネートされる。
【００４１】
これに加えて有用となる可能性のあるのは、FTComタスクのコーディネートをそれらのスタート時点と結びつけることである。本発明による方法の格別有利な実施形態によれば、FTComタスクのスタート時点が所定の値よりも互いに大きくは隔たっていないときだけ、それらのFTComタスクがコーディネートされる。その際、たとえば本発明による方法のユーザがこの値を設定可能であり、最も簡単なケースではスタート時点の一致が要求される。
【００４２】
バスを介したメッセージの伝送をコーディネートするという役割に従い、第１に伝送タスクの共通の信号がFlexRayメッセージの最大長を超えていなければ、それらの伝送タスクを単純な依存性をもつ依存クラスに対応づけてコーディネートすることができる。この場合、FlexRayメッセージの長さは任意に選定できるものではなく、FlexRayプロトコルにより設定されており、その際、１つのFlexRayメッセージに複数の信号をバンドリングすることができ、つまりFlexRayメッセージを伝送すべき複数の信号のためのいわば１つのフレームとすることができる。これに加えて伝送タスクが同じスタート時点を有しているならば殊に、単純な依存性をもつ依存クラスへの対応づけが行われる。
【００４３】
複数の伝送タスクの共通の信号がFlexRayメッセージ（フレーム）の最大長を超えていないとき、それらを同じ送信側アプリケーションノードに割り当てることができるとき、およびそれらがオーバラップしたスタートタイムインターバルを有するとき、それら複数の伝送タスクは所期のように複雑な依存性をもつ依存クラスに割り当てられてコーディネートされる。本発明による方法の１つの有利な実施形態によれば、伝送タスクのコーディネートもそれらのスタート時点と結びつけられる。このケースでは、複数の伝送タスクのスタート時点が所定の値たとえばユーザ側で設定された値よりも互いに大きく隔たっていなければ、それらの伝送タスクがコーディネートされる。
【００４４】
１つの独自の着想によれば本発明はさらに、データ処理装置において実行されたときに既述の方法におけるステップを実行するためのコンピュータプログラムにも関する。
【００４５】
詳細には、本発明による方法ならびに本発明によるコンピュータプログラムを構成し発展させる数多くの可能性がある。これについては、請求項１および請求項１８に従属する請求項とともに図面を参照した以下の実施例の説明も参照されたい。
【００４６】
図１は、本発明による方法の有利な実施例による流れ図の最適化について示す図である。
【００４７】
図２は、時間制御される分散型コンピュータシステムのための流れ図を示す図である。
【００４８】
図３は、本発明による方法の別の有利な実施例による流れ図の最適化について示す図である。
【００４９】
図４ａ、図４ｂは、各要素の単純な依存性および複雑な依存性を示す図である。
【００５０】
図５は、本発明による方法のさらに別の有利な実施例による流れ図の最適化について示す図である。
【００５１】
図１には、本発明による方法の基本コンポーネントに関する概略が示されている。この方法は一般にデータ処理装置により実行され、この方法を利用して、図示されていない分散型コンピュータシステムにより機能を実行するために最適化された流れ図Ｐを生成することができる。
【００５２】
分散型コンピュータシステムおよび機能は構造的および機能的な要素ｅ1,i，ｅ2,iの集合を有しており、これらはこの実施例では単に２つの要素クラスＥ1，Ｅ2に対応づけられている。要素ｅ1,i，ｅ2,iは、時間制御される分散型コンピュータシステムとこのコンピュータシステムにより実現すべき機能を表す。要素ｅ1,i，ｅ2,iを互いに依存関係におくことができ、一般的な事例ではそれぞれ異なる要素クラスの要素ｅ1,i，ｅ2,i間でも依存関係を成立させることができる。
【００５３】
図１に示されている実施例の場合、要素ｅ1,i，ｅ2,iはデータベース１ａのデータベースエントリとして既知のものである。第１のステップ１ｂにおいて、要素ｅ1,i，ｅ2,i間の依存関係が識別され、この依存関係がクラス分けされ、要素ｅ1,i，ｅ2,iが対応する依存クラスＡ1，Ａ2に対応づけられる。
【００５４】
図示されている実施例の場合、２つの要素クラスＥ1，Ｅ2と２つの依存クラスＡ1，Ａ2がたまたま存在している。ただし一般には要素クラスＥiの個数と依存クラスＡiの個数には依存関係は一切存在しない。単一のクラスＥiにおける要素ｅiが複数の依存クラスＡiに対応づけられる場合もあるし、多数の要素クラスＥiにおける要素ｅiが単一の依存クラスＡiとのみ単一の依存関係にあるだけの場合もある。
【００５５】
図１に示されている実施例では、要素クラスＥ1はアプリケーションファンクションクラス（三角形のシンボル）であり、要素クラスＥ2は時間制御される分散型コンピュータシステムにおける計算ノードのクラス（正方形のシンボル）である。第２のステップ１ｃには流れ図Ｐの最適化が描かれており、この最適化は少なくとも１つの依存クラスＡiにおける要素ｅ1,i，ｅ2,iのコーディネートにより行われ、図示の実施例によれば第２のステップ１ｃにおける最適化は、依存クラスＡ1に属する要素ｅ1,i，ｅ2,iのコーディネートにより行われる。
【００５６】
ここで要素のコーディネートとは基本的に要素ｅiの再ソート、割り当ておよび統合ないしは融合のことであり、図１に示されている実施例の場合、要素ｅ1,i，ｅ2,iのコーディネートは、流れ図Ｐ′における依存クラスＡ1に属する要素ｅ1,i（アプリケーションファンクション）の順序を変更すること、およびこれらの要素を依存クラスＡ1に属する要素ｅ2,i（計算ノード）に割り当てることにより行われる。図１に示されている方法はさらに、依存クラスＡ1の要素ｅ1,i，ｅ2,iが完全にコーディネートされてから、別の依存クラスＡ2の要素ｅ1,i，ｅ2,iがコーディネートされるように構成されている。
【００５７】
図１に示されている第２のステップ１ｃによれば、要素ｅ1,i，ｅ2,iのコーディネートは、決定論的な要素も確率論的な要素ないしは進化論的な要素も有する最適化法により行われる。「決定論的」であるのは、どの要素がコーディネート可能であるかの決定が一定のルールもしくは条件に基づきチェックされるからであり、「確率論的」であるのは、たとえばコーディネートの可能性についてチェックされる要素の選択がランダムな選択だからである。この場合、１つの流れ図Ｐにおいて得られた複数のバリエーションＰ′が品質判定基準により評価されるが、このことについては詳しくは示されていない。最適化が終了すると、もしくは中止されると、適用された方法の結果として最終的に１つの最適化された流れ図Ｐが生成される（ステップ１ｄ参照）。
【００５８】
図１に示されている実施例の場合、最適化ソリューションを算出するための品質判定基準としてバスの時間的な負荷が利用される。これに対し本発明による方法のここには示されていない別の実施例によれば品質判定基準は、流れ図Ｐの周期期間、伝送すべきメッセージの個数、必要とされる計算ノードの個数、計算ノードにおける機能全体もしくは部分機能の最悪実行時間に基づく。
【００５９】
図１、図３および図５を理解しやすくするために、図２には時間制御される分散型コンピュータシステムで頻繁に利用されるような流れ図が示されている。時間ｔはタイムインターバルＳ1〜Ｓ5に分けられている。この場合、これらのタイムインターバルＳ1〜Ｓ5の期間は固定的に定められており、もしくはまえもって固定的に設定する必要がある。縦軸も同様にそれぞれ異なるセクションＢ，ｅ1,1，ｅ1,2およびｅ1,3に分割されている。この場合、最も下のセクションＢは、時間制御される分散型コンピュータシステムのデータチャネルにおける通信をシンボリックに表しており、その上に位置するセクションｅ1,1，ｅ1,2およびｅ1,3は、分散型コンピュータシステムの他の要素つまり計算ノードにおけるスケジューリングされたアクティビティないしは活動を表している。
【００６０】
さらに図２に示されているように、２つのアプリケーションファンクションｅ2,1，ｅ2,2がノードｅ1,1において実行され、タイムインターバルＳ2の最後に処理されるメッセージを伴う送信ファンクションｅ3がタイムインターバルＳ3においてデータチャネルＢを占有する。ノードｅ1,1からデータチャネルＢを介してノードｅ1,3へ向けたメッセージ伝送は、伝送ファンクションｅ5の管轄である。これに続いて、計算ノードｅ1,3において実行される受信ファンクションｅ4がこのメッセージを受け取り、ついでこのメッセージは同じ計算ノードに格納されているアプリケーションファンクションｅ2,3により引き続き利用される。
【００６１】
FlexRay標準による用語の使い方によれば、図２において要素ｅ2,1，ｅ2,2，ｅ2,3はアプリケーションタスクであり、ｅ3およびｅ4はFTComタスク（厳密にはFTComトランスミッタタスクおよびFTComレシーバタスク）であり、これらの役割は、計算ノードから送信すべきまたは計算ノードにより受信すべきメッセージを計算ノードにおける通信コントローラのバッファに書き込むこともしくはそのバッファから読み出すことである。要素ｅ5は伝送タスクであり、このタスクは時間制御されるFlexRayバスを介してメッセージを伝送する役割を担う。
【００６２】
図３に示した実施例は、図１の実施例と同様の前提状況を有している。データベース３ａにとって要素ｅ1,i，ｅ2,iは既知であり、これらを要素クラスＥ1，Ｅ2に対応づけることができる。第１のステップ３ｂにおいて、要素ｅ1,i，ｅ2,i間の依存関係が識別され、この依存関係がクラス分けされ、ついで要素ｅ1,i，ｅ2,iが依存クラスＡ1，Ａ2に対応づけられる。ただし図３による方法が図１による方法と異なる点は、これに続いてステップ３ｃが設けられていることである。
【００６３】
図３によるステップ３ｃが格別な点は、依存クラスＡ1における要素ｅ1,i，ｅ2,iのコーディネートにあたり、はじめに要素クラスＥ1，Ｅ2のうち一方の要素クラスここでは要素クラスＥ1に属する要素ｅ1,i，ｅ2,iだけが別個にコーディネートされてから、他の要素クラスの要素がコーディネートされることである。ステップ３ｃにおいて依存クラスＡ1属する要素ｅ1,iがコーディネートされ、このコーディネートにはこれらの要素ｅ1,iの時間的な順序の変更および統合（黒で塗りつぶされた三角形）が含まれる。これに対しステップ３ｄにおいては、依存クラスＡ1に属する要素ｅ2,i（正方形）がコーディネートされる。
【００６４】
図３の実施例からよくわかるように、最適化ステップ３ｃ，３ｄの各々で得られた流れ図Ｐに対するサブソリューションＰ′が、いかなる変更点もなく何ら変更されずに、後続の最適化ステップに引き継がれる。
【００６５】
本発明による方法のさらに別の有利な実施形態によれば、依存クラスＡiには少なくとも、単純な依存性のクラスと複雑な依存性のクラスが含まれている。これについては別個には描かれていないが、この実施形態によれば、単純な依存性のクラスにおける要素のコーディネートは複雑な依存性のクラスにおける要素のコーディネートの前に行われる。
【００６６】
図４は、単純な依存性と複雑な依存性の概念を説明する図である。図４ａには要素ｅ1,1，ｅ1,2，ｅ1,3が示されており、これらは互いに関連しており、つまり要素ｅ1,1，ｅ1,2は要素1,3にそれぞれ信号を供給する。すぐにわかるように、要素ｅ1,1とｅ1,2の間には必然的な処理順序が存在しないことから、これらの要素を互いに無関係に実行させることができる。要素ｅ1,3の処理時点に対し時間的な設定（デッドライン）が存在する場合のみ、（要素ｅ1,3の最悪実行時間とｅ1,1，ｅ1,2とｅ1,3の間のメッセージ伝送を差し引いて）この時点より前に要素ｅ1,1およびｅ1,2を実行する必要がある。この種の要素は単純な依存関係にある。それというのもこれらの要素はそれぞれ他の要素の状態または初期値には左右されないからである。
【００６７】
これに対し図４ｂに示されている要素ｅ1,1，ｅ1,2，ｅ1,3は複雑な関係におかれている。なぜならばこれらの要素の処理順序は、各要素の指定された相互作用から必然的に生じたものだからである。つまりこの場合、最初に要素ｅ1,1が計算され、ついで要素ｅ1,2が計算されてから、最終的に要素ｅ1,3を計算することができるからである。このような事例では、各要素を任意にコーディネートすることができない。
【００６８】
図５には、本発明による方法のさらに別の実施例が示されている。やはりこの場合も、時間制御される分散型コンピュータシステムの要素ｅiがデータベース５ａに格納されており、さらに境界条件Ｒも格納されている。境界条件Ｒにはたとえば、アプリケーションファンクションと計算ノードの固定的な対応づけ、特定の機能の再実行に対する最大周期期間、特定の（部分）機能の実行と他の多数の設定との間の絶対間隔などが属する可能性がある。他の境界条件は本来の意味での設定ではなく、時間制御される分散型コンピュータシステムの装備に関する所定の特徴に拠るものにすぎず、これらの特徴とはたとえば、計算ノードにおける常に制約された計算能力、あるいは各計算ノード間で交換されるメッセージのためのデータチャネルにおける制約された伝送キャパシティなどである。
【００６９】
図５の第１のステップ５ｂにおいて要素ｅiが周知のように依存クラスＡiに割り当てられ、図示の事例では単純な依存性のクラスＡ1と複雑な依存性のクラスＡ2とに割り当てられる。
【００７０】
次のステップ５ｃにおいて、最初に１つの依存クラスＡiの要素ここでは単純な依存性のクラスＡ1の要素がコーディネートされる（Ｋ（Ａ1））。このコーディネートを１つのステップでまたは繰り返し複数のステップで実行することができる。ステップ５ｄにおいて、最適化された流れ図Ｐに関して各々達成されたサブソリューションＰ′が、境界条件Ｒを満たしていないかについてチェックされる。境界条件Ｒを満たしていないならば、コンフリクトのあるサブソリューションＰ′が廃棄され、ループ５ｈを経て、依存クラスＡ1の要素に対するコーディネートプロセスＫ（Ａ1）に戻る。流れ図ＰのためのサブソリューションＰ′にコンフリクトはないけれども、依存クラスＡ1の要求された要素ｅiがまだ全部はコーディネートされていないのであれば、同様にループ５ｈが適用される。
【００７１】
依存クラスＡ1におけるすべての要素ｅiが最終的にコーディネートされたならば、複雑な依存性をもつ依存クラスＡ2の要素ｅiが同様のやり方で処理され、この処理はステップ５ｃ，５ｄにより得られた流れ図ＰのためのサブソリューションＰ′に基づき行われる。
【００７２】
ステップ５ｃと５ｄにより得られたサブソリューションＰ′を用いても、流れ図Ｐのためのコンフリクトのないソリューションあるいは許容できるソリューションをステップ５ｅおよび５ｆにおいて見つけられない場合には、図５に示されているように、ループ５ｊを経て依存クラスＡ1の要素のコーディネートへと戻り、そこにおいて流れ図Ｐのための別のサブソリューションＰ′を計算し、このサブソリューションが流れ図Ｐのためのソリューションを計算するための出発点として再びステップ５ｅおよび５ｆにおいて用いられる。この方法の結果として得られるのは、生成され最適化された流れ図Ｐであり、図示の実施例ではこの流れ図Ｐがデータベース５ｇに格納される。
【図面の簡単な説明】
【００７３】
【図１】本発明による方法の有利な実施例による流れ図の最適化について示す図
【図２】時間制御される分散型コンピュータシステムのための流れ図を示す図
【図３】本発明による方法の別の有利な実施例による流れ図の最適化について示す図
【図４】各要素の単純な依存性および複雑な依存性を示す図
【図５】本発明による方法のさらに別の有利な実施例による流れ図の最適化について示す図
【図１】
0005404060.tif 000002
【図２】
0005404060.tif 000003
【図３】
0005404060.tif 000004
【図４ａ】
0005404060.tif 000005
【図４ｂ】
0005404060.tif 000006
【図５】
0005404060.tif 000007