リソース制約下における組込みソフトウェアの性能検証および最適化方法

Hiroshima City Univ.

リソース制約下における組込みソフト

ウェアの性能検証および最適化方法

広島市立大学

大学院情報科学研究科 システム工学専攻

中田 明夫 倉田 和哉 百々 太市

2012/11/9 新技術説明会 1

提案技術の概要

• 組込みシステムの開発

– 厳しいリソース制約(CPU,ネットワークなど)

– 非機能要求(リアルタイム性など)の達成

• 開発プロセスにおける設計段階

– 性能問題を発見することが困難

 実装段階で性能問題が発覚⇒

設計の手戻りが発生

設計段階での性能検証手法

[1]

_{を提案（非特許）}

• 性能要求を満たすだけでは不十分

性能要求を満たしたうえでの，低コスト化，低消費電

力化につながる最適化手法

[2]

_{を提案（特許出願中）}

2012/11/9 2 [1] 百々太市，中田明夫, ”プリエンティブスケジューリングによりリソースを共有する複数タスク動作仕様の性能検証” ,組込みシス テムシンポジウム(ESS2010)論文集, pp.107－112, 2010. 新技術説明会 [2] 中田明夫, 倉田和哉, 百々太市,”タイムバジェット最適化装置及び最適化方法”,特願2012-33489（平成24年2月20日出願）

Hiroshima City Univ.

性能検証手法の概要

 ソフトウェア仕様モデルから性能検証モデルへ変換および

性能検証[1]

2012/11/9 3 変換 優先権付きストップウォッチペトリネット スループット要求 性能検証 スループット要求を満たすか否か？ （ Yes/No ） 複数タスク動作仕様 単位時間に 処理できる データ数 [1] 百々太市，中田明夫, ”プリエンティブスケジューリングによりリソースを共有する複数タスク動作仕様の性能 検証” ,組込みシステムシンポジウム(ESS2010)論文集, pp.107－112, 2010. ソフトウェア仕様モデル 性能検証モデル 新技術説明会

複数タスク動作仕様

2012/11/9 4 2

τ

τ

3 4

τ

par

join

choice 5

τ

τ

₆ 7

τ

1

τ

2

τ

1

τ

6

τ

resource1 ×1個 固定優先度（FP） 3

τ

4

τ

5

τ

7

τ

resource2 ×1個 早い者勝ち（FIFO） (20) (5) (10) (20) ₍₃₀₎ (10)

endchoice

(5) Input(100)

output

タイムバジェット (タスクの処理に使用可能な 時間の割り当て) タスク 周期的入力 （スループット 要求） タスクグラフ リソース割り当て 並列合流 並列 選択 選択合流 出力

複数タスクの順序関係や並列・選択などの制

御構造を有向非閉路グラフとして表現

各タスクの実行に必要なリ ソース，総リソース数，および リソース競合を解決するスケ ジューリング方式の指定 τ1>τ2>τ6 新技術説明会

Hiroshima City Univ.

優先権付きストップウォッチペトリネット

2012/11/9 5

○：プレース ●：トークン □：トランジション

：アーク

[1,8]

入力プレース

出力プレース

時間ペトリネット(TPN)

・・・並列的・非同期的・分散的な実時

間システムを表すためのモデル

 時間的振る舞いをモデル化可能

t0

t1

p0

p1

p2

p3

p4

[

0,6

]

時間計測開始

計測開始

[3,5]

優先度

計測をストップ

[

0,3

]

経過時間を保持

再び計測を開始

優先権付きペトリネット(PrPN)

・・・トランジションの組に対して優先

度を設定可能

 固定優先度スケジューリングをモ

デル化可能

ストップウォッチペトリネット(SwPN)

・・・時間の計測を途中で止めたり，

また再スタートさせたりすることが可

能

 プリエンプティブスケジューリング

をモデル化可能

[

1,3

]

[1,8]

[3,5]

[

1,3

]

[

0,2

]

：優先度

：ストップウォッチアーク

新技術説明会

タスクのPrSwPNへの変換

2012/11/9 6 (10,30) 1

τ

新技術説明会 変換方法の特徴： •タスク内部の動作を捨象  検証の効率化 •タスク、スケジューラ、リソースを分離  柔軟な組合せが可能 スケジューラ： FIFO(早い者勝ち)、FP(固定優先度プリエンプティブ)、 FP-np(固定優先度ノンプリエンプティブ）、など

Hiroshima City Univ.

スループット性能検証手法

2012/11/9 7

input

[100,100]

assertion

システム

error

2

•スループット要求を満たす⇒errorプレースにトークンが入らない

•スループット要求を満たさない⇒errorプレースにトークンが入る

システムの処理

・・・システムがp0からトークンを得

ることによって表現

p0に2個のプレース

・・・システムの処理能力が入力に

追い付いていない

p0

新技術説明会

 到達可能性解析に帰着

到達可能性解析

2012/11/9 8

動作仕様

ペトリネット

検証ツール The TINA Toolbox （既存）

新技術説明会

指定したプレースにトークンが

入る可能性があるか否か検証可能

Hiroshima City Univ.

性能検証の効率評価

• 評価方法

① リソース数を5~20，タスク数を30~50まで変えた複数

タスク動作仕様をランダムに10個ずつ生成

② PrSwPNに変換し平均検証時間を測定

 検証には既存ツールThe TINA Toolboxを使用

– 検証結果はスループット制約を[満たす/満たさない/検証不能]で示され

る

 生成したタスクのパラメータ

2012/11/9 新技術説明会 9 スループット要求

_{タイムバジェット}

100[入力/s]

1~10[s]

効率評価の結果

• タスク数に概ね比例し検証時間が増加

• いずれの場合も数十秒で検証完了

Hiroshima City Univ.

性能を保持した

タイムバジェット最適化

全体のスループット性能を満たす範囲内で，各

タスクのタイムバジェット

_{(タスクの処理に使用可}

能な時間の割り当て)

を自動的に改善

 正確には局所最適化（初期解から最も近く、これ以上改

善できない解を探索）

タイムバジェットが長くなれば、より低性能のリ

ソースで同じ性能が実現可能

2012/11/9 新技術説明会 11

出力

タイムバジェット最適化方針

• レイテンシ(個々のデータが入力されてから出力

されるまでの遅延)要求に対する余裕時間を各タ

スクに効果的に配分することにより，各タスクの

タイムバジェットを最適化

2012/11/9 12 レイテンシ要求 入力

t1

t2

t3

t4 t5

t6

余裕時間

t1

t

t2

t3

t4

t5

t6

1

t

2

t

3

t

4

t

5

t6

入力 _出力 レイテンシ要求 新技術説明会 最悪レイテンシ

Hiroshima City Univ.

レイテンシ要求が追加された仕様

2012/11/9 13 2

τ

τ

3 4

τ

par

join

choice 5

τ

τ

₆ 7

τ

1

τ

2

τ

1

τ

6

τ

resource1 ×1個 固定優先度（FP） 3

τ

4

τ

5

τ

7

τ

resource2 ×1個 早い者勝ち（FIFO） (20) (5) (10) (20) ₍₃₀₎ (10)

endchoice

(5) Input(100)

output

(200)

タイムバジェット タスク 周期的入力 （スループット 要求） タスクグラフ リソース割り当て 並列合流 並列 選択 選択合流 出力(レイテンシ要求) τ1>τ2>τ6 新技術説明会

タイムバジェット配分方針

• 仮定：各タスクの処理時間はリソースの性能に比

例

– リソースをより低性能に  そのリソースを使用するタ

スク群の処理時間は同じ割合だけ増加

• タイムバジェット配分方針

– 性能要求（＝スループット要求＆レイテンシ要

求）を満たす限り、同じリソースを使用するタス

ク群のタイムバジェットを同じ割合だけ増やす

2012/11/9 新技術説明会 14

Hiroshima City Univ.

性能検証手法の改良

2012/11/9 15 変換 優先権付きストップウォッチペトリネット スループット要求 性能検証 性能要求を満たすか否か？ （ Yes/No ） 複数タスク動作仕様 ソフトウェア仕様モデル 性能検証モデル レイテンシ要求 新技術説明会

最悪レイテンシ計測および

レイテンシ性能検証

2012/11/9 16

システム

(PrSwPN)

出力

入力

計測可能 1秒経過 [1,1] 1秒経過後 2秒経過 [1,1] 2秒経過後 3秒経過 3秒経過後 4秒経過 4秒経過後 5秒経過 5秒経過後 6秒経過 [1,1] [1,1] [1,1] [1,1] レイテンシ要求違反 計測完了 計測開始 [0,0] [0,0]

入力から出力までのレイテンシ要求

が6秒以内のシステムの例

レイテンシ：3秒

[1,1] 4秒経過 しなかった 新技術説明会

Hiroshima City Univ.

最適化の手順

① 同じリソースを共有するタス

クのタイムバジェットを一定

率増加させた動作仕様を各

リソース毎に生成

② 各動作仕様を性能検証モデ

ルに変換

③ 生成された各モデルを性能

検証

④ 検証の結果、性能要求を

a.

いずれかが満たす場合，最悪

レイテンシが最も小さいものを

新しい動作仕様として選択し

最初から繰り返す

b.

すべて満たさない場合，最適

化を終了

2012/11/9 17

入力の動作仕様

新技術説明会

実験：使用する例題

2012/11/9 18 2

τ

τ

3 4

τ

par

join

5

τ

6

τ

1

τ

2

τ

1

τ

6

τ

r1×1個 固定優先度（FP） 3

τ

4

τ

5

τ

r2×1個 早い者勝ち（FIFO） (10, 200) (20, 200) (30, 200) (20, 200) (25, 200) (15, 200) Input(100)

output(200)

タスクグラフ リソース割り当て 6 1 2

τ

τ

τ

>

>

スループット要求：_10[入力/s] （100msに1回入力） レイテンシ要求：200[ms]以内 増加率 f ：5[%]  0.5 [%]

CPU：Intel Xeon E5607 (2.27GHz)

メモリ：4.00GB

OS:Windows7(x86) Professional SP1

PrSwPN検証ツール：TINA 2.10.0

実験環境

Hiroshima City Univ.

性能検証モデルへの変換

2012/11/9 19

プレース数1153, トランジション数2159

新技術説明会

実験結果(1/2)

2012/11/9 20

最適化前

最適化後

スループット要求を満たすか否か？

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

r1を共有するタスクのタイムバジェットの増加率 ：145.0[%] r2を共有するタスクのタイムバジェットの増加率 ：39.5[%] 新技術説明会 最適化にかかった総 時間： 約70秒程度 (検証回数45回、最大 検証時間1.5秒）

Hiroshima City Univ.

実験結果(2/2)

2012/11/9 21

最適化前

最適化後

(20, 200) 新技術説明会

考察

• リソースr1，r2を共有するタスクのタイムバ

ジェットをそれぞれ145.0％，39.5％増加さ

せても，最適化前と同性能のモデルを得る

ことができた

同じ性能要求に対して，タイムバジェットがより

大きくなるため，より低性能のCPUやネット

ワークを使用可能

2012/11/9 新技術説明会 22

Hiroshima City Univ.

まとめ

• 各タスクのリソース制約とタイムバジェットが

指定されたマルチタスクソフトウェアの動作

仕様と性能要求（スループット要求およびレ

イテンシ要求）が与えられたとき，性能要求

を満たす範囲で各タスクのタイムバジェット

を緩和することにより局所最適化を行う手法

を提案

• 同じ性能要求に対して，タイムバジェットがよ

り大きくなるため，より低性能のCPUやネット

ワークを使用可能

2012/11/9 新技術説明会 23

問い合わせ先

広島市立大学 社会連携センター

連携推進室長（特認教授）

社会連携コーディネーター 野村 啓治

TEL:082-830-1764 FAX：082-830-1545

E-Mail:k-nomura@hiroshima-cu.ac.jp

2012/11/9 新技術説明会 24