Loading article…
計算タスクの最悪実行時間（WCET）とは、特定のハードウェアプラットフォーム上でタスクを実行するのにかかる最大時間のことです。
最悪実行時間は、一般的に信頼性の高いリアルタイムシステムで使用されます。このようなシステムでは、ソフトウェアの最悪実行時のタイミング挙動を理解することが、信頼性や正しい機能動作にとって重要となるからです。
例えば、車両のエンジン動作を制御するコンピュータシステムは、特定の時間内に入力に応答する必要があるかもしれません。応答時間を構成する要素の一つは、ソフトウェアの実行時間です。したがって、ソフトウェアの最悪実行時間を特定できれば、システム設計者は、スケジューラビリティ解析などの他の手法と組み合わせて、システムが十分な速さで応答するようにすることができます。
WCETは多くのリアルタイムシステムに適用できる可能性を秘めていますが、実際には、WCETの保証は主に高い信頼性や安全性が求められるリアルタイムシステムで利用されています。例えば、航空機搭載ソフトウェアにおいては、DO178Cの6.3.4項でソフトウェアに対する一定の配慮が求められています。自動車システムにおけるソフトウェアの利用拡大も、ソフトウェアのWCET分析の必要性を高めています。
システム設計においては、WCETはスケジューラビリティ解析への入力としてよく用いられるが、クリティカルシステムにおけるWCETのより一般的な用途は、 ARINC 653のようなパーティションスケジューリングシステムにおいて、事前に割り当てられたタイミングバジェットが侵害されないことを保証することである。
組み込みコンピューティングの黎明期から、組み込みソフトウェア開発者は以下のいずれかを使用してきました。
これらの手法にはいずれも限界がある。エンドツーエンド測定では、最長パスを達成するためにソフトウェアテストに大きな負担がかかる。命令数を数える方法は、単純なソフトウェアとハードウェアにしか適用できない。どちらの場合も、テストされていないコード、ハードウェア性能の近似値、またはミスを考慮するために、誤差範囲が設けられることが多い。20%の誤差範囲がよく用いられるが、この数値には「前回はうまくいった」という過去の経験に基づく信頼性以外に、ほとんど根拠がない。
ソフトウェアとハードウェアの複雑化に伴い、ツールによるサポートの必要性が高まっています。複雑性は、静的解析と計測の両方において、ますます大きな問題となっています。許容誤差の範囲をどの程度にすべきか、またソフトウェアシステムのテストがどの程度適切に行われているかを判断するのは困難です。テスト中に達成された最高値に基づくシステム安全性の議論は広く用いられていますが、ソフトウェアとハードウェアの予測可能性が低下するにつれて、その正当性を証明することが難しくなっています。
将来的には、安全性が極めて重要なシステムにおいては、静的解析と計測に基づく解析の両方を用いて解析を行うことが求められるようになる可能性が高い。
解析によって最悪実行時間（WCET）を求める問題は、停止問題と同等であるため、一般的には解決不可能である。幸いなことに、エンジニアが通常WCETを求めようとするようなシステムでは、ソフトウェアは構造がしっかりしており、必ず終了し、解析可能である。
WCET を求めるほとんどの方法は近似値 (不確実性がある場合に通常は切り上げ) を伴うため、実際には正確な WCET 自体は入手不可能とみなされることが多い。代わりに、WCET を求めるさまざまな手法によって WCET の推定値が得られる。[ 1 ]これらの推定値は通常悲観的であり、推定 WCET は実際の WCET (通常は望ましい値) よりも高いことがわかっている。WCET 分析に関する多くの研究は、分析における悲観性を減らし、推定値がシステム設計者にとって価値のあるほど十分に低くなるようにすることに焦点を当てている。
WCET分析は通常、単一のスレッド、タスク、またはプロセスの実行時間を指します。しかし、最新のハードウェア、特にマルチコア環境では、システム内の他のタスクがキャッシュ、メモリライン、その他のハードウェア機能を共有している場合、特定のタスクのWCETに影響を与える可能性があります。さらに、ブロッキングや割り込みなどのタスクスケジューリングイベントは、特定のシステムで発生する可能性がある場合は、WCET分析で考慮する必要があります。したがって、WCET分析が適用される状況を考慮することが重要です。
上記の手動手法以外にも、WCETを計算するための自動化された手法は数多く存在します。これらには以下が含まれます。
静的WCETツールは、コンピュータソフトウェアをハードウェア上で直接実行することなく、ソフトウェアを解析することでWCETを推定しようとするものです。静的解析技術は1980年代後半からこの分野の研究を支配してきましたが、産業界ではエンドツーエンドの測定手法が標準的な手法でした。
静的解析ツールは、ソースコードまたは逆アセンブルされたバイナリ実行ファイルに対して、プログラムのタスクの構造を高レベルで解析します。また、タスクが実行される実際のハードウェアのタイミング情報（すべての固有の機能を含む）を利用して、低レベルでも解析を行います。これら2種類の解析を組み合わせることで、ツールは特定のハードウェアプラットフォーム上で特定のタスクを実行するのに必要な時間の上限を算出します。
低レベルでは、プロセッサの平均性能を向上させるアーキテクチャ上の機能（例えば、命令キャッシュ／データキャッシュ、分岐予測、命令パイプラインなど）が存在するため、静的なWCET解析は複雑になります。これらの最新のアーキテクチャ上の機能を解析に使用するタイミングモデルに組み込むと、厳密なWCET境界を決定することは可能ではありますが、ますます困難になります。
そのため、欧州航空安全機関などの認証機関は、モデル検証スイートに依存している。
静的解析は、比較的単純なハードウェアに対しては良好な結果をもたらしてきましたが、静的解析の潜在的な限界として、ハードウェア（特にCPU）が極めて複雑な構造となり、モデル化が困難になっていることが挙げられます。具体的には、モデリングプロセスにおいて、チップ設計の誤り、ドキュメントの不足、ドキュメントの誤り、モデル作成の誤りなど、複数の要因からエラーが発生する可能性があります。これらの要因により、モデルが実際のハードウェアで観測される動作とは異なる動作を予測してしまうケースが生じます。通常、動作を正確に予測できない場合は、悲観的な結果が用いられますが、その結果、実行時に得られる値よりもはるかに大きなWCET推定値が得られる可能性があります。
マルチコアプロセッサでは、厳密な静的WCET推定値を得ることは特に困難である。
静的解析の様々な手法を実装した商用および学術的なツールが数多く存在する。
測定ベースおよびハイブリッドアプローチでは、通常、実際のハードウェア上で短いコードセグメントの実行時間を測定し、それらをより高レベルの分析で組み合わせます。ツールはソフトウェアの構造（ループ、分岐など）を考慮して、より大きなプログラムの最悪実行時間（WCET）を推定します。その根拠は、複雑なソフトウェアで最長パスをテストするのは難しいが、そのソフトウェアの多くの小さなコンポーネントで最長パスをテストする方が容易であるという点にあります。最悪ケースの影響は、分析において他の最悪ケースイベントと組み合わせるために、テスト中に一度だけ発生すれば十分です。
通常、ソフトウェアの小さなセクションは、計測（ソフトウェアにマーカーを追加する）などの手法や、デバッガやCPUハードウェアトレースモジュールなどのハードウェアサポートを使用して自動的に測定できます。これらのマーカーによって実行トレースが生成され、プログラム内でたどられたパスと、さまざまなポイントが実行された時刻の両方が含まれます。トレースは分析され、プログラムの各部分が実行にかかった最大時間、各ループで観測された最大反復時間、およびテストされていないソフトウェア部分があるかどうか（コードカバレッジ）が判断されます。
測定に基づくWCET解析は、単純なハードウェアと複雑なハードウェアの両方で良好な結果をもたらしていますが、静的解析と同様に、マルチコア環境では、あるコアが別のコアに与える影響を明確に定義することが難しいため、過度に悲観的な結果になることがあります。測定の限界は、テスト中に最悪のケースの影響を観察することに依存している点です（必ずしも同時に観察するとは限りません）。最悪のケースの影響が実際にテストされているかどうかを判断するのは難しい場合があります。
測定に基づく様々な分析手法を実装した、商用および学術用のツールが数多く存在する。
最も活発な研究グループは、米国（ミシガン大学）、スウェーデン（メーラダーレン、リンシェーピング）、ドイツ（ザールブリュッケン、ドルトムント、ブラウンシュバイク）、フランス（トゥールーズ、サクレー、レンヌ）、オーストリア（ウィーン）、英国（ヨーク大学、Rapita Systems Ltd）、イタリア（ボローニャ）、スペイン（カンタブリア、バレンシア）、スイス（チューリッヒ）にあります。最近では、コードレベルのタイミング解析というテーマは、米国（ノースカロライナ、フロリダ）、カナダ、オーストラリア、バングラデシュ（MBI LAB、RDS）、サウジアラビア王国UQU（HISE LAB）、シンガポール、インド（IITマドラス、IIScバンガロール）の研究グループによって、ヨーロッパ以外でも注目を集めています。
第1回国際WCETツールチャレンジは2006年秋に開催されました。メーラダーレン大学が主催し、組み込みシステム設計の卓越ネットワークARTIST2が後援しました。このチャレンジの目的は、最悪実行時間の分析におけるさまざまなアプローチを検証し、比較することでした。タスクのWCETの安全な上限を決定できる利用可能なすべてのツールとプロトタイプが参加しました。最終結果[ 2 ]は、2006年11月にキプロスのパフォスで開催されたISoLA 2006国際シンポジウムで発表されました。
2008年に第2回チャレンジが開催された。[ 3 ]