リソース制約下における組込みソフト ウェアの性能検証および最適化方法 広島市立大学 大学院情報科学研究科システム工学専攻 中田明夫倉田和哉百々太市 1
提案技術の概要 組込みシステムの開発 厳しいリソース制約 (CPU, ネットワークなど ) 非機能要求 ( リアルタイム性など ) の達成 開発プロセスにおける設計段階 性能問題を発見することが困難 実装段階で性能問題が発覚 設計の手戻りが発生 設計段階での性能検証手法 [1] を提案 ( 非特許 ) 性能要求を満たすだけでは不十分 性能要求を満たしたうえでの, 低コスト化, 低消費電力化につながる最適化手法 [2] を提案 ( 特許出願中 ) [1] 百々太市, 中田明夫, プリエンティブスケジューリングによりリソースを共有する複数タスク動作仕様の性能検証, 組込みシステムシンポジウム (ESS2010) 論文集, pp.107-112, 2010. [2] 中田明夫, 倉田和哉, 百々太市, タイムバジェット最適化装置及び最適化方法, 特願 2012-33489( 平成 24 年 2 月 20 日出願 ) 2
性能検証手法の概要 ソフトウェア仕様モデルから性能検証モデルへ変換および性能検証 [1] ソフトウェア仕様モデル 複数タスク動作仕様 単位時間に処理できるデータ数 スループット要求 性能検証 スループット要求を満たすか否か? ( Yes/No ) 変換 優先権付きストップウォッチペトリネット 性能検証モデル [1] 百々太市, 中田明夫, プリエンティブスケジューリングによりリソースを共有する複数タスク動作仕様の性能検証, 組込みシステムシンポジウム (ESS2010) 論文集, pp.107-112, 2010. 3
複数タスク動作仕様 タスクグラフ 周期的入力 ( スループット要求 ) タスク 並列 (10) τ 2 Input(100) τ 1 par τ 3 τ 4 (20) (5) (5) タイムバジェット ( タスクの処理に使用可能な時間の割り当て ) choice (20) (30) τ 5 τ 6 endchoice 選択 選択合流 τ 1 τ 2 τ 6 τ 3 τ 4 τ 5 τ 7 リソース割り当て 固定優先度 (FP) resource1 1 個 τ 1 >τ 2 >τ 6 早い者勝ち (FIFO) resource2 1 個 並列合流 join τ 7 output 4 (10) 出力 複数タスクの順序関係や並列 選択などの制御構造を有向非閉路グラフとして表現 各タスクの実行に必要なリソース, 総リソース数, およびリソース競合を解決するスケジューリング方式の指定
優先権付きストップウォッチペトリネット : プレース : トークン : トランジション : アーク : 優先度 : ストップウォッチアーク p0 p1 p2 入力プレース t0 t1 経過時間を保持再び計測を開始計測をストップ計測開始 [3,5] [1,3] [0,6] [0,3] [1,8] [3,5] [1,3] [0,2] 時間計測開始 優先度 時間ペトリネット (TPN) 並列的 非同期的 分散的な実時間システムを表すためのモデル 時間的振る舞いをモデル化可能 p4 ストップウォッチペトリネット (SwPN) 時間の計測を途中で止めたり, また再スタートさせたりすることが可能 プリエンプティブスケジューリング出力プレースをモデル化可能 5 p3 優先権付きペトリネット (PrPN) トランジションの組に対して優先度を設定可能 固定優先度スケジューリングをモデル化可能
タスクの PrSwPN への変換 τ 1 (10,30) 変換方法の特徴 : タスク内部の動作を捨象 検証の効率化 タスク スケジューラ リソースを分離 柔軟な組合せが可能スケジューラ : FIFO( 早い者勝ち ) FP( 固定優先度プリエンプティブ ) FP-np( 固定優先度ノンプリエンプティブ ) など 6
スループット性能検証手法 error [100,100] input p0 2 assertion システムの処理 システムが p0 からトークンを得ることによって表現 システム p0 に 2 個のプレース システムの処理能力が入力に追い付いていない スループット要求を満たす error プレースにトークンが入らない スループット要求を満たさない error プレースにトークンが入る 到達可能性解析に帰着 7
到達可能性解析 検証ツール The TINA Toolbox ( 既存 ) 動作仕様 指定したプレースにトークンが入る可能性があるか否か検証可能 ペトリネット 8
評価方法 性能検証の効率評価 1 リソース数を 5~20, タスク数を 30~50 まで変えた複数タスク動作仕様をランダムに 10 個ずつ生成 2 PrSwPN に変換し平均検証時間を測定 検証には既存ツール The TINA Toolbox を使用 検証結果はスループット制約を [ 満たす / 満たさない / 検証不能 ] で示される 生成したタスクのパラメータ スループット要求 タイムバジェット 100[ 入力 /s] 1~10[s] 9
効率評価の結果 タスク数に概ね比例し検証時間が増加 いずれの場合も数十秒で検証完了 10
性能を保持した タイムバジェット最適化 全体のスループット性能を満たす範囲内で, 各タスクのタイムバジェット ( タスクの処理に使用可能な時間の割り当て ) を自動的に改善 正確には局所最適化 ( 初期解から最も近く これ以上改善できない解を探索 ) タイムバジェットが長くなれば より低性能のリソースで同じ性能が実現可能 11
タイムバジェット最適化方針 レイテンシ ( 個々のデータが入力されてから出力されるまでの遅延 ) 要求に対する余裕時間を各タスクに効果的に配分することにより, 各タスクのタイムバジェットを最適化 最悪レイテンシ t1 t2 t3 t4 t5 t6 余裕時間 入力 出力 レイテンシ要求 入力 t t t t t t1 t2 t3 t4 t5 t6 1 2 3 4 5 12 t6 出力レイテンシ要求
レイテンシ要求が追加された仕様 タスクグラフ 周期的入力 ( スループット要求 ) タスク 並列 (10) τ 2 並列合流 Input(100) τ 1 par τ 3 τ 4 (20) (5) (5) タイムバジェット選択 choice (20) (30) τ 5 τ 6 (10) endchoice τ 7 選択合流 τ 1 τ 2 τ 6 τ 3 τ 4 τ 5 τ 7 リソース割り当て 固定優先度 (FP) resource1 1 個 τ 1 >τ 2 >τ 6 早い者勝ち (FIFO) resource2 1 個 join output(200) 出力 ( レイテンシ要求 ) 2012/11/9 新技術説明会 13
タイムバジェット配分方針 仮定 : 各タスクの処理時間はリソースの性能に比例 リソースをより低性能に そのリソースを使用するタスク群の処理時間は同じ割合だけ増加 タイムバジェット配分方針 性能要求 (= スループット要求 & レイテンシ要求 ) を満たす限り 同じリソースを使用するタスク群のタイムバジェットを同じ割合だけ増やす 14
性能検証手法の改良 ソフトウェア仕様モデル 複数タスク動作仕様 変換 スループット要求 レイテンシ要求 優先権付きストップウォッチペトリネット 性能検証 性能検証モデル 性能要求を満たすか否か? ( Yes/No ) 15
[1,1] 最悪レイテンシ計測および 4 秒経過後 [1,1] レイテンシ性能検証 [1,1] 5 秒経過 5 秒経過後 [1,1] 入力から出力までのレイテンシ要求が 6 秒以内のシステムの例 レイテンシ要求違反 [0,0] 出力 4 秒経過しなかった 3 秒経過後 4 秒経過 [1,1] レイテンシ :3 秒 計測可能 6 秒経過 [1,1] 計測完了 [0,0] 計測開始 システム (PrSwPN) 3 秒経過 [1,1] 1 秒経過 入力 2012/11/9 2 秒経過後 1 秒経過後 2 秒経過新技術説明会 16
最適化の手順 1 同じリソースを共有するタスクのタイムバジェットを一定率増加させた動作仕様を各リソース毎に生成 2 各動作仕様を性能検証モデルに変換 3 生成された各モデルを性能検証 4 検証の結果 性能要求を a. いずれかが満たす場合, 最悪レイテンシが最も小さいものを新しい動作仕様として選択し最初から繰り返す b. すべて満たさない場合, 最適化を終了 入力の動作仕様 17
タスクグラフ 実験 : 使用する例題 Input(100) リソース割り当て τ 1 (10, 200) τ 1 τ 2 固定優先度 (FP) r1 1 個 par τ 6 τ > 2 > τ1 τ 6 τ 2 (30, 200) τ 3 τ 4 (20, 200) (15, 200) τ 5 (20, 200) τ 3 τ 4 早い者勝ち (FIFO) r2 1 個 スループット要求 :10[ 入力 /s] join (100msに1 回入力 ) レイテンシ要求 :200[ms] 以内 τ 6 (25, 200) 増加率 f :5[%] 0.5 [%] 実験環境 CPU:Intel Xeon E5607 (2.27GHz) output(200) メモリ :4.00GB OS:Windows7(x86) Professional SP1 PrSwPN 検証ツール :TINA 2.10.0 18 τ 5
性能検証モデルへの変換 プレース数 1153, トランジション数 2159 19
実験結果 (1/2) 最適化前 最適化後 スループット要求を満たすか否か? Yes Yes 最悪レイテンシ 90 197 タスク名 実行に必要なリソース 最適化前のタイムバジェット 最適化後のタイムバジェット τ1 r1 10 24.5 τ2 r1 30 73.5 τ3 r2 20 27.9 τ4 r2 15 20.25 τ5 r2 20 27.9 τ6 r1 25 61.25 最適化にかかった総時間 : 約 70 秒程度 ( 検証回数 45 回 最大検証時間 1.5 秒 ) r1 を共有するタスクのタイムバジェットの増加率 :145.0[%] r2 を共有するタスクのタイムバジェットの増加率 :39.5[%] 20
実験結果 (2/2) (20, 200) 最適化前 最適化後 21
考察 リソース r1,r2 を共有するタスクのタイムバジェットをそれぞれ 145.0%,39.5% 増加させても, 最適化前と同性能のモデルを得ることができた 同じ性能要求に対して, タイムバジェットがより大きくなるため, より低性能の CPU やネットワークを使用可能 22
まとめ 各タスクのリソース制約とタイムバジェットが指定されたマルチタスクソフトウェアの動作仕様と性能要求 ( スループット要求およびレイテンシ要求 ) が与えられたとき, 性能要求を満たす範囲で各タスクのタイムバジェットを緩和することにより局所最適化を行う手法を提案 同じ性能要求に対して, タイムバジェットがより大きくなるため, より低性能の CPU やネットワークを使用可能 23
問い合わせ先 広島市立大学社会連携センター連携推進室長 ( 特認教授 ) 社会連携コーディネーター野村啓治 TEL:082-830-1764 FAX:082-830-1545 E-Mail:k-nomura@hiroshima-cu.ac.jp 24