最悪実行時間
 |
最悪実行時間（さいあくじっこうじかん、英: Worst-case execution time, WCET）は、特定のハードウェアで特定の計算タスクを実行するのにかかる最長の時間を指す。最悪実行時間を知ることは、リアルタイムシステムのタイミング解析にとって最重要とされている。
概要[編集]
タイミング解析は一般に次の2つのレベルで行われる。
- WCET 解析
- 高レベル/システムレベルの解析
WCET 解析は、個々のタスクの実行時間を扱う。このレベルでは、対象タスクに関すること以外は無視される。タスクはスケジューリング上ブロックされることがないと見なされ、割り込まれることもないと想定される（これらの影響はスケジュール可能性解析で扱う）。
高レベルでは、システム内の個々のプログラムに関する WCET 解析の結果を用いて、システム全体の性能を解析する。複数のタスクが1つのCPUで実行され、リソースを奪い合う。従って、リソースにアクセスする際にブロックされる可能性がある。このレベルの典型的な解析手法をスケジュール可能性解析という。これには例えば、固定優先度解析やレートモノトニックスケジューリング解析などがある。スケジュール可能性解析の厳密性や精度は WCET 解析の正確さに依存する。WCET 値が悲観的（実際にシステムとして実行中にありうる実行時間よりも大きい予測値）な場合、スケジューラは各タスクに実際に必要な時間以上の時間を割り当てざるをえなくなるだろう。
静的 WCET 解析ツールを使ってプログラムのタスクの構造を決定する助けとすることができる。これは、ソースコードや実行ファイルを逆アセンブルしたものを対象とした解析ツールである。それとは別に実際のハードウェアに関する情報を使って低レベルな解析を行うことも必要である。これらの解析結果を統合することで、対象タスクを対象ハードウェア上で実行したときにかかる最悪実行時間が求められる。
低レベルな静的 WCET 解析は、CPUの性能向上のためのアーキテクチャ上の様々な機能が存在するため、非常に複雑になっている。命令/データキャッシュ、分岐予測、パイプライン処理といった要素を考慮する必要がある。解析において、これらのアーキテクチャ上の機能を考慮することで、厳密な WCET 値が決定できる。
1980年代末ごろから静的解析手法の研究が盛んに行われているが、近年では動的解析あるいは実測による手法も研究が盛んになってきた。そのような手法を採用する研究者の動機としては、コンピュータ（特にCPU関連）がモデル化するには複雑になりすぎており、モデル化による誤差が大きくなってきたことが挙げられる。一方実測に基づく手法も、測定の際に最悪ケースとなるような環境を与えられるかどうかに依存しており、正確でない可能性がある。実測ベースの手法では、短いコード部分（ブロック単位）の実行時間を測定し、コード全体の最悪実行時間は実測結果を統合した上で静的解析で求めるのが一般的である。これは、基本ブロックのWCETは容易に測定可能だが、全体として最悪ケースとなるような状況を実際につくり出すのは難しいという考え方に基づいている。
産業界では、リアルタイム性がそれほど厳密に要求されないシステムでは、全体を実測して安全マージンを加えるという手法が採られてきた。また、クリティカルなシステムでは、ハードウェアが単純な場合、人手による静的解析が行われてきた。近年、産業界でも WCET を自動的に計算する手法が注目されてきている。人手による解析では、ハードウェアの複雑化が問題となってきており、安全マージンをどう決めるかも困難になってきている。
関連項目[編集]
参考文献[編集]
 |