(57)【要約】  本発明は、分散型組み込みシステムの自動合成のためのコンピュータに実装された方法に関する。システムによって処理されるタスクは、複数の処理ユニットを有するハードウェア構造に、タスクの既定の時間制限を満たすようにマッピングされる。方法は、（ａ）タスクを、以下のサブステップを用いて複数の処理ユニットに割り当てるステップであって、サブステップが、（ａａ）処理ユニットにタスクを割り当てるステップと、（ｂｂ）出力イベント密度を決定するステップと、（ｃｃ）次のタスクに向かう出力密度と閾値とを比較し、イベント密度が閾値未満の場合、次のタスクを同じ処理ユニットに割り当て、イベント密度が閾値以下の場合、次のタスクを別の処理ユニットに割り当てるステップと、（ｄｄ）すべてのタスクが処理ユニットに割り当てられるまで、（ａａ）から（ｄｄ）のステップを繰り返すステップと、を含むステップと、（ｂ）処理ユニットに対する所与のタスク割り当てのコストが、既定のソリューション基準を満たしているか否かをチェックするステップと、（ｃ）処理ユニットに対する新たなタスクの割り当てに関し、タスクが既定のソリューション基準を満たすまで、ステップ（ａ）から（ｂ）を繰り返すステップと、（ｄ）タスクに割り当てられた処理ユニットのオペレーショナルシステムのプロセスに、タスクを割り当てるステップと、（ｅ）処理ユニットのオペレーショナルシステムのプロセスに対する所与のタスク割り当てが、タスクの既定の時間基準を満たしているかをチェックするステップと、（ｆ）タスクの既定の時間基準が満たされている場合、処理ユニットのオペレーショナルシステムのプロセスに対する所与のタスク割り当てに関連するコストを計算するステップと、（ｇ）処理中のソリューションのコストが既定のソリューション基準を満たすまで、処理ユニットへの新しいタスク割り当てに関し、ステップ（ａ）から（ｃ）を繰り返すか、あるいは、割り当てられた処理ユニットのオペレーショナルシステムのプロセスへの新しいタスク割り当てに関し、ステップ（ｄ）から（ｆ）を繰り返すステップと、を含む。【選択図】図１【特許請求の範囲】
【請求項１】
分散型組み込みシステムの自動合成のためにコンピュータに実装された方法であって、
前記システムに処理されるタスクが、前記タスクの既定の時間基準を満たすように、複数の処理ユニットを有するハードウェア構造にマッピングされ、
前記方法が、
（ａ）以下のサブステップにより、前記タスクを前記複数の処理ユニットに割り当てるステップ、
１．タスクをハードウェアに割り当てるサブステップ、
２．出力密度を表す、タスクの出力データストリームおよびアクティベーションを決定するサブステップ、
３．次のタスクへの出力密度を閾値と比較し、前記出力密度が前記閾値を超える場合、前記次のタスクを同じハードウェアに割り当て、前記出力密度が前記閾値以下の場合、前記次のタスクを別のハードウェアに割り当てるサブステップ、
４．全てのタスクが割り当てられるまで処理を実行するサブステップ、
（ｂ）前記処理ユニットへの所与のタスク割り当てのコストが、既定のソリューション基準を満たしているか否かをチェックするステップ、
（ｃ）新しいタスクの前記処理ユニットへの割り当てに対し、タスクが既定のコスト基準を満たすまで、（ａ）から（ｂ）のステップを繰り返すステップ、
（ｄ）前記タスクを、前記タスクに割り当てられた前記処理ユニットのオペレーショナルシステムのプロセスに割り当てるステップと、
（ｅ）前記処理ユニットの前記オペレーショナルシステムの前記プロセスへの所与のタスク割り当てが、タスクの既定の時間基準を満たしているかをチェックするステップ、
（ｆ）前記タスクの前記既定の時間基準が満たされている場合、前記処理ユニットの前記オペレーショナルシステムの前記プロセスへの所与のタスク割り当てについてコストを計算するステップ、および
（ｇ）処理中のソリューションのコストが既定の解決基準を満たすまで、前記処理ユニットへの新しいタスク割り当てに対するステップ（ａ）から（ｃ）の繰り返し、または、前記割り当てられた処理ユニットのオペレーショナルシステムのプロセスへの新しいタスク割り当てに対するステップ（ｄ）から（ｆ）の繰り返しを行うステップ、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記ステップ（ｇ）の前記方法ステップの前記繰り返しが、最適化発見手法（ｏｐｔｉｍｉｚａｔｉｏｎ  ｈｅｕｒｉｓｔｉｃｓ）に依存することを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、前記割り当てられた処理ユニットの前記運用システムの前記プロセスへのタスクの割り当ての前記ステップ（ｄ）が、タスクイベントの前記入力および出力密度を解析するためのイベントスペクトル解析ステップを含むことを特徴とする方法。
【請求項４】
請求項３に記載の方法において、前記イベントスペクトル解析ステップが、タスク間のデータ依存性を考慮することを特徴とする方法。
【請求項５】
請求項４に記載の方法において、前記プロセスへの前記タスクの容認される割り当ての場合、前記タスクのイベントの決定された出力密度は、後続のタスクのイベントの可能な入力密度以下であることを特徴とする方法。
【請求項６】
請求項３乃至５のいずれかに記載の方法において、前記割り当てられた処理ユニットの前記プロセスへ前記タスクを割り当てる前記ステップは、タスクが前記イベント入力および出力密度に応じて、パーティションに分割されるタスク分割ステップを含み、次のステップでは、分割されたタスクは、前記割り当てられた処理ユニットの前記プロセスに割り当てられることを特徴とする方法。
【請求項７】
請求項６に記載の方法において、前記タスク分割ステップは、前記タスクの前記イベントの入力密度および／または出力密度と既定の閾値とを比較することを含むことを特徴とする方法。
【請求項８】
請求項１乃至７のいずれかに記載の方法において、複数のプロセスが１つのプロセスに結合されることを特徴とする方法。
【請求項９】
請求項１乃至８のいずれかに記載の方法において、複数のタスクが１つのプロセスにある場合、または複数のプロセスが１つのプロセスにある場合、または複数のプロセスが１つの処理ユニットにある場合、一連の前記複数のタスクまたは前記複数のプロセスは、スケジューリング方法によって決定されることを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、前記スケジューリング方法は、時間制御または優先度制御されたスケジューリング方法であることを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、前記スケジューリング方法は、タイムスロットベースのスケジューリング方法であることを特徴とする方法。
【請求項１２】
請求項１乃至１１のいずれかに記載の方法において、前記処理ユニットの前記オペレーショナルシステムの前記プロセスの前記所与のタスク割り当てが、前記タスクの前記既定の時間基準を満たしているかをチェックするために、数学的実時間演算方法が用いられることを特徴とする方法。
【請求項１３】
請求項１乃至１１のいずれかに記載の方法において、前記処理ユニットの前記オペレーショナルシステムの前記プロセスの前記所与のタスク割り当てが、前記タスクの前記既定の時間基準を満たしているかをチェックするために、タスク計算方法が用いられることを特徴とする方法。
【請求項１４】
請求項１乃至１３のいずれかに記載の方法において、前記処理ユニットはプロセッサであることを特徴とする方法。
【請求項１５】
請求項１乃至１４のいずれかに記載の方法において、ステップ（ｄ）の前記コスト計算は、少なくとも１つの前記処理ユニットのエネルギー消費、電力消費、動作温度、またはチップ面積を考慮することを特徴とする方法。
【請求項１６】
請求項１乃至１５のいずれかに記載の方法において、前記ソリューション基準は、前記コストが既定のコスト閾値未満であるかを考慮することを特徴とする方法。
【請求項１７】
請求項１乃至１５のいずれかに記載の方法において、前記ソリューション基準は、コストミニマムが見つかったか否かを考慮することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散型組み込みシステムの自動合成のためのコンピュータに実装された方法に関し、システムによって処理されるタスクが、複数の処理ユニットを有するハードウェア構造に、タスクの既定の時間制限を満たすようにマッピングされる方法に関する。
【背景技術】
【０００２】
分散型組み込みシステムの自動合成の方法は、長く研究されてきた。この研究の概略が、“F. S1omka: Mehrkriterienoptimierung vertei1ter Echtzeitsysteme mit Tabu-Search, doctoral thesis, engineering department of the university of Erlangen-Nuremberg, Fortschritt-Bericht VDI, series 20, no.353, VDI-Verlag, Dusseldorf, 2002”に記載されている。このようなシステム合成の目的は、システムで処理される個々のタスクを、ハードウェアアーキテクチャにマッピングすることである。そのため、どのタスクをどのプロセッサで実行するかを、決定する必要がある。この合成の目的は、所与の量のタスクを、最小限のハードウェア構造によって処理することである。ほとんどの場合、タスクは所定の時間制限を満たさなければならず、時間制限はタスクの流れから特定される場合もある。ソフトウェアタスクのためのインフラストラクチャと、オペレーティング・システムとを含むハードウェアアーキテクチャは、この境界条件、および更に特定される境界条件、例えばチップ面積で表されることが多い、最小コストでのエネルギー消費、電力消費、動作温度の観点から、実装する必要がある。ほとんどのジョブにおいて、タスクは、厳密な、または発見的（ｈｅｕｒｉｓｔｉｃ）な最適化方法によって、プロセッサに割り当てられ、この段階で、特定された境界条件を満たしているか否かがチェックされる。タスクのプロセッサへの割り当ては、十分に小規模なハードウェアアーキテクチャが見つかるか、サーチが終了するまで、最適化方法によってシステマティックに変更される。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
自動車製造業者（ＯＥＭ）は、電気および電子フィールドにおける異なるタスクを、機能図としてモデル化する。機能図はブロックを含み、各ブロックは特定の機能を定義する。各ブロックは、１つのタスクを実現してもよい。ブロックにおけるデータ入力および出力は相互に接続されており、ブロック間のデータの流れを示している。機能的な正確さのために、ブロックが時系列で処理され、定められた時間制限の条件が満たされることが重要となる。第一のステップでは、自動車製造業者は、制御装置のシステムアーキテクチャ（ＣＰＵの数および種類、周辺機器、メモリサイズ等）、特にソフトウェアアーキテクチャ（スケジューリング方法、プロセスナンバー、割込処理ルーチン（ＩＳＲ）、ＩＳＲ／プロセス優先度等）に関する詳細な知識を持たずに、ブロックを複数の制御装置に対して分配する。制御装置へのブロック分配の複雑さとヒストリカル制限（ｈｉｓｔｏｒｉｃａｌ  ｒｅｓｔｒｉｃｔｉｏｎ）のために、この最適化により得られる解は多くの場合、準最適解である。時間制限は、十分に考慮されていない。第二のステップでは、制御装置のサプライヤの目的は、特に、定められた時間制限を満たす制御装置のシステムアーキテクチャを考案することである。第一のステップにおいて誤った分配が選択された場合の問題点の１つ目は、制御装置の実時間基準が満たされないことである。２つ目は、実時間性能を達成するために必要な最適化方法の開発が非常に複雑になることである。３つ目は、第一のステップでの最適解の観点から、ハードウェアのオーバーサイジングが必要となることである。１つ目の問題点は、製品リコールを招いて信頼を失う原因となる恐れがあり、一方、２つ目と３つ目の問題点は、コストの増加につながる。
【課題を解決するための手段】
【０００４】
本発明の目的は、組み込みシステムによって処理されるタスクを、複数の処理ユニットを有するハードウェア構造に、タスクの既定の時間制限が満たされるようにマッピングすることである。この目的は、請求項の特徴によって達成される。
【発明の効果】
【０００５】
本発明は、分散型組み込みシステムの自動合成のためのコンピュータに実装された方法に関し、システムにおいて処理されるタスクが、複数の処理ユニットを有するハードウェア構造に、タスクの既定の時間制限を満たすようにマッピングされる方法に関する。本方法は、以下のステップを含む。
（ａ）以下のサブステップによって、複数の処理ユニットにタスクを割り当てる。
（ａａ）ハードウェアにタスクを割り当てる。
（ｂｂ）出力されるデータストリームおよびアクティベーション（出力密度等）を決定する。
（ｃｃ）次のタスクに向かう出力密度と閾値とを比較し、出力密度が閾値を超える場合は次のタスクを同じハードウェアに割り当て、出力密度が閾値以下の場合は他のハードウェアに割り当てる。
（ｄｄ）すべてのタスクが割り当てられるまで、ステップ（ａａ）からステップ（ｃｃ）までを繰り返す。
（ｂ）処理ユニットに対する所与のタスク割り当てのコストが、既定のソリューション基準を満たしているかをチェックする。
（ｃ）処理ユニットに対する新たなタスク割り当てに関し、タスクが既定のコスト基準を満たすまで、ステップ（ａ）からステップ（ｂ）までを繰り返す。
（ｄ）タスクに割り当てられた処理ユニットのオペレーショナルシステムのプロセスに、タスクを割り当てる。
（ｅ）処理ユニットのオペレーショナルシステムのプロセスに対する所与のタスク割り当てが、タスクの既定の時間制限を満たしているかをチェックする。
（ｆ）タスクの既定の時間制限が満たされている場合、処理ユニットのオペレーショナルシステムのプロセスに対する所与のタスク割り当てに関連するコストを計算する。
（ｇ）所与のソリューションのコストが既定のソリューション基準を満たすまで、処理ユニットへの新たなタスク割り当てに関し、ステップ（ａ）からステップ（ｃ）までを繰り返すか、あるいは、割り当てられた処理ユニットのオペレーショナルシステムのプロセスへの新たなタスク割り当てに関し、ステップ（ｄ）からステップ（ｆ）までを繰り返す。
【０００６】
好ましくは、ステップ（ｇ）の方法ステップの繰り返しは、最適化発見手法（ｏｐｔｉｍｉｓａｔｉｏｎ  ｈｅｕｒｉｓｔｉｃｓ）に依存する。
【０００７】
ハードウェアへのタスク分配ステップにおいては、データの相互依存およびイベント密度を考慮する。タスク間におけるデータの相互依存は、タスクの実行のアクティベーションから識別される。
【０００８】
割り当てられた処理ユニットのオペレーショナルシステムのプロセスへのタスク割り当てステップ（ｄ）は、好ましくは、データ依存性およびアクティベーションの入力密度および出力密度を解析するための、イベントのスペクトル解析のステップを含む。ここで、後続のタスクへのデータ出力およびアクティベーション出力におけるイベント密度は、イベントスペクトル解析ステップにおけるタスクのアクティベーションのイベント密度から決定されることが好ましい。さらに、プロセス（ｄ）へのタスクの容認される割り当ての場合、タスクのイベントの決定された出力密度は、後続のタスクのイベントの可能な入力密度以下であることが好ましい。
【０００９】
割り当てられた処理ユニットのプロセスへのタスク割り当てステップ（ｄ）は、好ましくはタスク分割ステップを含む。タスク分割ステップにおいて、タスクは、イベント入力密度およびイベント出力密度に応じてパーティションに分割され、次のステップでは、パーティションのタスクは割り当てられた処理ユニットのプロセスに割り当てられる。さらに、タスク分割ステップは、好ましくは、タスクのイベント入力および／または出力密度と既定の閾値との比較を含む。閾値および比較演算子は、仕様として、ユーザによって提供されるか、あるいはあらかじめ設定される。
【００１０】
複数のプロセスは、１つのプロセスに結合されることが好ましい。
【００１１】
さらに、１つのプロセスに複数のタスクがある場合、または１つのプロセスに複数のプロセスがある場合、または１つの処理ユニットに複数のプロセスがある場合は、一連の複数のタスクあるいは複数のプロセスは、スケジューリング方法によって決定されることが好ましい。このようなスケジューリング方法は、時間制御された、または優先度制御された、またはタイムスロットベースの、スケジューリング方法であることが好ましい。
【００１２】
数学的実時間計算方法あるいはタスク計算方法を用いて、処理ユニットのオペレーショナルシステムのプロセスへの所与のタスク割り当てが、タスクの既定の時間制限を満たしているかをチェックすることが好ましい。
【００１３】
ステップ（ｆ）で行われるコスト計算は、少なくとも１つの処理ユニットのエネルギー消費、電力消費、動作温度、またはチップ面積を考慮することが好ましい。
【００１４】
処理ユニットは、プロセッサであることが好ましい。
【００１５】
さらに、コストが既定のコスト閾値未満の場合、あるいはコストミニマムが見つかった場合には、ソリューション基準を考慮することが好ましい。
【図面の簡単な説明】
【００１６】
【図１】本発明の一実施形態に係るマッピング方法を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、本発明の好ましい実施形態のフローチャートを示す添付の図面に基づき、本発明をさらに詳細に説明する。
【００１８】
自明的なアプローチとは異なり、本最適化方法は、タスクがプロセスに割り当てられ、プロセスがハードウェアに割り当てられるといった、更なるレベルの処理によって単純に補足されるものではない。
【００１９】
本発明による方法は、異なるアプローチを採用している。まずは従来の方法と同様、タスクは各プロセッサに割り当てられる。
【００２０】
処理ユニットへのタスクの割り当ては、タスクグラフの境界ノードから始める。センサによってアクティブにされた、あるいはデータを供給されたタスクは、好ましくは、センサに接続された処理ユニットに割り当てられる。アクターも同様である。この最初の割り当てによって、選択された処理ユニットでのタスクの実行時間を決定することができる。アクティベーションの実行時間およびイベント密度によって、出力されるデータの依存性のイベント密度および後続のタスクのアクティベーションを、イベントスペクトル解析を利用して決定することができる(参考： F. Bodmann, K. Albers, F. S1omka: Analyzing the Timing Characteristics of Task Activations, Proceedings of the first IEEE Symposium on Industrial Embedded Systems (SIES,October 2006, and D.Albers, F.Bodmann, F. S1omka: Hierarchical Event Streams and Event Dependency Graphs: A New Computational Model for Embedded Real-Time Systems. IEEE Proceedings of the 18th Euromicro Conference on Real-Time Systems, July 2006)。入力および出力されるイベント密度は、プロセスに結びついたタスクの動的インタフェース仕様を表している (参考： F .S1omka, F. Bodmann, K. Albers: Analytische Transaktionsmodellierung. EDA Workshop, Hanover, VDI-Verlag, Juni 2007)。割り当てられたタスクから別のタスクへのエッジのそれぞれには、重みが与えられる。重みは、イベント毎に送信されるデータサイズに対応する。アクティベーション・エッジは、送信可能な最小データサイズに対応する重みを割り当てられる。２つのタスク間のパラレルエッジは１つのエッジに結合されて、それらの重みは加算される。
【００２１】
エッジの重みとイベント密度との積は、定められた閾値と比較される。値が高く閾値を超える場合、後続のタスクは同じ処理ユニットに割り当てられる。値が低い場合、後続のタスクは異なる処理ユニットに割り当てられる。更なる通信タスクが導入されて、２つの処理ユニットを接続する通信リソースに割り当てられる。これは、すべてのタスクが処理ユニットに割り当てられるまで繰り返される。
【００２２】
次のステップでは、上記のようにして得られた分配が、所与のコスト基準を満たしているかをチェックする。満たしていなければ、分配は拒絶され、再開される。次のステップでは、タスクはオペレーショナルシステムのプロセスに割り当てられる。使用可能な動的インタフェース仕様は、ここで使用してもよい。“K. Albers, F. S1omka: Efficient Feasibility Analysis for Real-Time Systems with EDF Scheduling. Proceedings of the Design Automation and Test Conference in Europe (DATE 05), 2005, and K. Albers, F. S1omka: An Event Stream Driven Approximation for the Analysis of Real-Time Systems. 16th Euromicro Conference on Real-Time Systems, IEEE Computer Society Press, Catania, 2004”に記載された解析技術によって、入力および出力密度が、関連するタスクのデータ依存性によって一致するかをチェックする。これは、タスクの出力密度が、後続のタスクの予想される入力密度以下の場合である。イベント密度によって、タスク分割を実行することができる。可能ならば、依存性によって高密度に結びついたタスクは、１つのパーティションに移動する。イベントの密度は、分割および、タスクのプロセスへの割り当てのための近さを示す尺度の一種である。定められた閾値に従って、タスク分割を続けるか否か、また、どのように続けるかを決定することができる。タスク分割がこれらの基準を満たしていることが確認されると、個々のタスクは、プロセスへと結合される。異なる階層からなすプロセス構造は、確実に許容されるものである。従って、複数のプロセスを１つのプロセスに結合することができる。複数のタスクが１つのプロセスに結合した場合、または複数のプロセスが１つのプロセスに結合された場合、または複数のプロセスが１つのプロセッサによって実行された場合、個々のタスクおよび一連のプロセスは、スケジューリング方法によって決定される必要がある。異なる種類の方法を用いることが可能であり、最も一般的なものは、時間制御スケジューリング（ＥＤＦ）、優先度制御スケジューリング（ＲＭＳ／ＤＭＳ）、またはタイムスロットベース（ＴＤＭＡ，  Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）スケジューリングである。所与のハードウェアの割り当ておよびタスクの割り当てに基づいて、時間制限の順守は、数学的実時間演算によって検証される(参考：Ernesto Wandeler: Modular Performance Analysis and Interface-Based Design for Embedded Real-Time Systems. PhD Thesis, Computer Engineering and Networks  Laboratory, ETH Zurich, Switzerland, September 2006)。あるいは、“K. Albers, S. Kollmann, F. Bodmann, F. Slomka. Advanced Hierarchical Event-Stream Model and the Real-Time Calculus. Internal report,289-vts-63281, Ulm University, 2008”に記載されているように、タスク計算方法を用いてもよい。
【００２３】
以下に、本発明による方法を、図１に基づいた好ましい実施形態によって、ステップごとに説明する。
【００２４】
ステップ１において、最初に、タスクおよびオプションのハードウェアへのタスクの割り当てが選択される。この割り当てを受けて、出力密度を示す、このタスクのデータストリームおよびアクティベーションは、ステップ２において決定される。ステップ３における終了基準は、全てのタスクが割り当てられたか否かである。否であれば、ステップ４において、まだ割り当てられていないタスクの中から次のタスクが選択される。ステップ５で、割り当てられたタスクから次に選択されたタスクへの出力密度が、ユーザ定義の閾値と比較される。出力密度が閾値を超えていれば、次のタスクは、同じハードウェアに割り当てられる（ステップ７）。出力密度が閾値以下であれば、タスクは別のハードウェアに割り当てられる（ステップ６）。全てのタスクが割り当てられるまで（ステップ３の結果が“ｙｅｓ”になるまで）、以上のステップが実行される。
【００２５】
ステップ８で、コストがチェックされユーザ定義の基準と比較される。この基準が満たされていない場合、最適化アルゴリズムがステップ９において含まれ、ステップ１からステップ８が繰り返される。よって、新しいタスクを処理ユニットに割り当てる際には、タスクが既定のコスト基準を満たすまで、ステップ１からステップ８が繰り返される。
【００２６】
ステップ１０において、タスクは、タスクに割り当てられた処理ユニットのオペレーショナルシステムのプロセスに割り当てられる。ステップ１１において、実時間スケジューリング解析が実行される。ステップ１２において、処理ユニットのオペレーショナルシステムのプロセスへの所与のタスク割り当てが、タスクの既定の時間基準を満たしているかをチェックする。満たしていれば、処理ユニットのオペレーショナルシステムのプロセスへの所与のタスク割り当てに関連するコストを計算する。満たしていなければ、新しいタスクの処理ユニットへの割り当てに対してステップ１からステップ８が（時間閾値を超えている場合）、もしくは、ステップ９から開始して、新しいタスクの、割り当てられた処理ユニットのオペレーショナルシステムのプロセスへの割り当てに対してステップ１からステップ８が（時間閾値未満の場合）、処理中のソリューションのコストが既定のソリューション基準を満たすまで繰り返される。後者の方法は、最適化ステップ、すなわちステップ１６を含む。
【００２７】
ステップ１３で、システムがパレート最適（Ｐａｒｅｔｏ  ｏｐｔｉｍａｌ）か否かがチェックされる。パレート最適であれば、ソリューションはステップ１４で保存される。
【００２８】
最終的に、ステップ１５において、既定の数の最適解に達したか否かがチェックされる。
【図１】
2013515988.tif 000002
【手続補正書】
【提出日】平成24年11月9日(2012.11.9)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
分散型組み込みシステムの自動合成のためにコンピュータに実装された方法であって、
前記システムに処理されるタスクが、前記タスクの既定の時間基準を満たすように、複
数の処理ユニットを有するハードウェア構造にマッピングされ、
前記方法が、
（ａ）以下のサブステップにより、前記タスクを前記複数の処理ユニットに割り当て
るステップ、
１．タスクをハードウェアに割り当てるサブステップ、
２．出力密度を表す、タスクの出力データストリームおよびアクティベーション
を決定するサブステップ、
３．次のタスクへの出力密度を閾値と比較し、前記出力密度が前記閾値を超える
場合、前記次のタスクを同じハードウェアに割り当て、前記出力密度が前記閾値以下の場
合、前記次のタスクを別のハードウェアに割り当てるサブステップ、
４．全てのタスクが割り当てられるまで１．から３．のサブステップを繰り返す
サブステップ、
（ｂ）前記処理ユニットへの所与のタスク割り当てのコストが、既定のソリューショ
ン基準を満たしているか否かをチェックするステップ、
（ｃ）新しいタスクの前記処理ユニットへの割り当てに対し、タスクが既定のコスト
基準を満たすまで、（ａ）から（ｂ）のステップを繰り返すステップ、
（ｄ）前記タスクを、前記タスクに割り当てられた前記処理ユニットのオペレーショ
ナルシステムのプロセスに割り当てるステップと、
（ｅ）前記処理ユニットの前記オペレーショナルシステムの前記プロセスへの所与の
タスク割り当てが、タスクの既定の時間基準を満たしているかをチェックするステップ、
（ｆ）前記タスクの前記既定の時間基準が満たされている場合、前記処理ユニットの
前記オペレーショナルシステムの前記プロセスへの所与のタスク割り当てについてコスト
を計算するステップ、および
（ｇ）処理中のソリューションのコストが既定の解決基準を満たすまで、前記処理ユ
ニットへの新しいタスク割り当てに対するステップ（ａ）から（ｃ）の繰り返し、または
、前記割り当てられた処理ユニットのオペレーショナルシステムのプロセスへの新しいタ
スク割り当てに対するステップ（ｄ）から（ｆ）の繰り返しを行うステップ、
を含むことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記ステップ（ｇ）の前記方法ステップの前記繰り返
しが、最適化発見手法（ｏｐｔｉｍｉｚａｔｉｏｎ  ｈｅｕｒｉｓｔｉｃｓ）に依存する
ことを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、前記割り当てられた処理ユニットの前記運用
システムの前記プロセスへのタスクの割り当ての前記ステップ（ｄ）が、タスクイベント
の前記入力および出力密度を解析するためのイベントスペクトル解析ステップを含むこと
を特徴とする方法。
【請求項４】
請求項３に記載の方法において、前記イベントスペクトル解析ステップが、タスク間の
データ依存性を考慮することを特徴とする方法。
【請求項５】
請求項４に記載の方法において、前記プロセスへの前記タスクの容認される割り当ての
場合、前記タスクのイベントの決定された出力密度は、後続のタスクのイベントの可能な
入力密度以下であることを特徴とする方法。
【請求項６】
請求項３乃至５のいずれかに記載の方法において、前記割り当てられた処理ユニットの
前記プロセスへ前記タスクを割り当てる前記ステップは、タスクが前記イベント入力およ
び出力密度に応じて、パーティションに分割されるタスク分割ステップを含み、次のステ
ップでは、分割されたタスクは、前記割り当てられた処理ユニットの前記プロセスに割り
当てられることを特徴とする方法。
【請求項７】
請求項６に記載の方法において、前記タスク分割ステップは、前記タスクの前記イベン
トの入力密度および／または出力密度と既定の閾値とを比較することを含むことを特徴と
する方法。
【請求項８】
請求項１乃至７のいずれかに記載の方法において、複数のプロセスが１つのプロセスに
結合されることを特徴とする方法。
【請求項９】
請求項１乃至８のいずれかに記載の方法において、複数のタスクが１つのプロセスにあ
る場合、または複数のプロセスが１つのプロセスにある場合、または複数のプロセスが１
つの処理ユニットにある場合、一連の前記複数のタスクまたは前記複数のプロセスは、ス
ケジューリング方法によって決定されることを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、前記スケジューリング方法は、時間制御または優先度
制御されたスケジューリング方法であることを特徴とする方法。
【請求項１１】
請求項９に記載の方法において、前記スケジューリング方法は、タイムスロットベース
のスケジューリング方法であることを特徴とする方法。
【請求項１２】
請求項１乃至１１のいずれかに記載の方法において、前記処理ユニットの前記オペレー
ショナルシステムの前記プロセスの前記所与のタスク割り当てが、前記タスクの前記既定
の時間基準を満たしているかをチェックするために、数学的実時間演算方法が用いられる
ことを特徴とする方法。
【請求項１３】
請求項１乃至１１のいずれかに記載の方法において、前記処理ユニットの前記オペレー
ショナルシステムの前記プロセスの前記所与のタスク割り当てが、前記タスクの前記既定
の時間基準を満たしているかをチェックするために、タスク計算方法が用いられることを
特徴とする方法。
【請求項１４】
請求項１乃至１３のいずれかに記載の方法において、前記処理ユニットはプロセッサで
あることを特徴とする方法。
【請求項１５】
請求項１乃至１４のいずれかに記載の方法において、ステップ（ｄ）の前記コスト計算
は、少なくとも１つの前記処理ユニットのエネルギー消費、電力消費、動作温度、または
チップ面積を考慮することを特徴とする方法。
【請求項１６】
請求項１乃至１５のいずれかに記載の方法において、前記ソリューション基準は、前記
コストが既定のコスト閾値未満であるかを考慮することを特徴とする方法。
【請求項１７】
請求項１乃至１５のいずれかに記載の方法において、前記ソリューション基準は、コス
トミニマムが見つかったか否かを考慮することを特徴とする方法。