Partial Evaluation of Model Transformations

ICSE’12 勉強会
Maintaining Invariant Traceability through
Bidirectional Transformations
Y. Yu, Y. Lin, Z. Hu, S. Hidaka,
H. Kato, and L. Montrieux
担当：名古屋大学渥美
1
Motivating example
(1) モデルから
テンプレートコードを生成
(2) テンプレートコードを改変
・ toString() を toString(String type) に拡張
・ getName() を getID() にリファクタリング
モデルからコードを再
生成した場合に書き換
えられないように
注釈 @generated はモデルから生成
されたことを示すものであり，モデルと
対応付けられている
2
(3) Name ⇒ iD の変更は自動的にモデルに反映 (自動)
(4) モデルからコードを再生成
・変更前の toString が生成される
・ toString(String type) 中の name が iD に変更されない
blinkit
(bidirectional invariant traceability framework)
目的：同時に更新されるモデルとユーザコードのトレーサビリ
ティを確保する
I.
II.
III.
IV.
モデルとテンプレートコードは対応付け
られている
U’ における修正したメソッドには注釈
@generated INV を付ける
U’ と T の差分から U’ を T に変換する
ルールを求める
3. のルールをT’に適用し，TとU’のトレー
サビリティ情報を保持したまま U’ と T’ を
マージしたコードを生成する
3
1
4
2
External Changes
Meaningful Diff
Forward transf.
Backward transf.
GRoundTram: An Integrated Framework for
DevelopingWell-Behaved
Bidirectional Model Transformations
(ASE2011, short paper)
3
Optional Check
Figure 8.
The data ﬂows inside bl i nki t
評価(1/2)
モデル，コードを並行して変更を加えて適切にトレーサビリ
ティを確保できるか?
 クラス数1, 属性数1 のEMFメタモデルを対象
@generated として生成された要素
 クラス: 8
 属性: 48
 メソッド: 10
モデル，生成されたクラスを変更



メソッド9つに対し，注釈を @generated INV に変更し，メッソド
コードを修正
モデルのクラス名，メソッド名を変更
blinkit でそれぞれの変更を正しくマージできることを確認した
4
評価 (2/2)
モデルとコードがような現実的なケースがオープンソースのプロ
ジェクトにあるか?
 GMF プロジェクトの CVS リポジトリから java code を対象に
調査


2005/08/14〜2011/08/13
28,070 リビジョン
• @model 要素 (モデルに対応する Java コード) の変更によ
る影響を受けるリビジョン： 15,223 (54%)
• @generated NOT のメソッド (ユーザコード) から参照され
るモデル要素： 146,415
⇒ 平均 9.61 (146,415/15,223) 個のモデル要素が
@generated NOT メソッドから参照されている
5
ICSE2012勉強会 Session N： Models #2
Slicing MATLAB Simulink Models
(R. Reicherdt ＆ S. Glesner, Proc. ICSE2012, pp.551 - 561)
名古屋大学大学院情報科学研究科旧小林G
小林隆志＆小林孝壽 (M1・インターンシップ中)
※ 図表は上記論文から引用しています．
6
概要
• 背景：Simulinkモデルに対する静的手法は少ない
• 手動レビューや構文チェックのみ or コード生成後に実施
• データフローや制御フローの認識が困難であることが原因
• 提案：スライス技法によるSimulinkモデルの複雑さ削減
• 特徴：Simulink向けの制御依存解析 (データ依存は直感的)
•
CEC (Conditional Execution Contexts)の考慮が肝
• モデル構造や階層を保持 → 他の手法・ツールを適用可能
• 評価：10個のサンプルモデル(57-394ブロック) により評価
• Ave. Forward/Backward Slice Size で特性を議論
• スライス計算の正確さなどは議論していない
7
Simulinkモデル

Simulink：データフロー指向モデル
 ブロックは機能の表現や
モデルの構成に使用される
 ラインは信号の流れを表し，
ブロックの入力と出力に接続する
 EC(実行コンテキスト) を考慮した
シミュレーション

Fig2では，whileブロックの実行は
1サイクルだが，内部(Fig3)では
複数サイクルで実行される．
(1/z が正しく機能する)
condが成り立つ
間は繰り返す
i++
【delay block】
1サイクル前の
値を返す
i += i
i *= i
8
EC(実行コンテキスト)

実行サイクルを制御する単位


モデル全体(=root context)，各Atomicサブシステムが
それぞれに１つもつ
ECに入るとECに含まれる全ての要素が実行される
実行するブロックの順序リストとネストしたECを含む
 他のサブシステム、ブロックとのデータ依存と
親サブシステムのECよりスケジュールされる

root context (EC1)
1:3
1:2
1:1
2:2
2:1
EC2 (for subsystem#1)
3:2
3:1
EC3 (for subsystem#2)
9
Conditional Execution Contexts(CEC)

条件の値を指定する特殊な入力ポートに関連するEC
実行スケジュール
が cond の真偽で
異なる

任意のCECに含まれるノードmは
述語ブロックに制御依存
11
CECの計算

問題点： CECはサブシステム境界を超えて両方向に伝播
Mathwoksが定義．シミュレーション最適化が目的
 条件付きサブシステムSのCECに，Sに含まれていない
ブロックbを追加できる(= 実行サイクルを減らすことができる)
 単純な構文指向アプローチを利用できない


伝播を考慮するアルゴリズムを定義している
サブシステム外のブロックも同じ
EC 2 に入れる (GainとBiasが同ECに)
In1の入力で
In2-4のどれを
出力するか決定
12
評価実験

提案手法に基づくスライシングツールを実装
 モデル解析，制御依存・データ依存の解析，PDG構築
 Forward，Backward走査が可能
 グラフを配色して印刷，スライス以外のブロックの除去


MATLAB IDEで実行可能なM言語スクリプト
10個のケーススタディにより評価
 m1を自身で作成
（57 block）
 m2をプロジェクトパートナーから提供 (227 block)
 残り8個はSimulinkデモモデル (78-394 block)
15
実験結果
FW：forward m：モデル
BW:Backward S(b): bを基準にしたスライス
dd:データ依存
cd：制御依存
dd+cd はddと同程度か, ddより大きなサイズとなる
 条件付き実行に必要なブロックをスライスに追加するため

16
実証研究との比較

[9]：様々なプログラムのスライス


[10]：異なる定義の拡張有限状態機械


AVG BW=28%, FW=26%
AVG BW=39.42%~67.99%
本研究：

AVG BW=54.26%, FW=54.39%
 [9]と大小が逆転している



Simulinkは制御依存があまり含まれない
Constantブロックや大きなフィードバックループを持つ
[9]と比べ大きい
 処理に関係ないVirtualブロック(Portなど)が多い
 フィードバックループ
→多数のブロックによる環状データ依存
[ 9 ] D. Binkley, N. Gold, and M. Harman, “An empirical study of static program slice size,” ACM TOSEM (16)2, 2007
[10] K. Androutsopoulos, et al. “A theoretical and empirical study of EFSM dependence,” Proc. ICSM2009
17
ICSE’12 勉強会 Session N #3
Partial Evaluation of
Model Transformations
A. Razavi
(U. of Waterloo) &
K. Kontogiannis
(National Tech. U. of Athens)
Proc. ICSE2012 pp.562-572
担当：東工大小林
スライド中の図は論文から引用しています．
18
概要

背景：モデル変換(MT)は高コスト


提案：部分評価をベースにした漸次的モデル変換法



MTは新しいモデルを作る時だけではなく，開発プロセス全体で頻繁
に利用されるが，変換コスト(時間)が問題となる．
モデル変換のプログラムを部分評価して得た
残余プログラム＝最適化されたモデル変換プログラム
部分評価対象 = 新たな変更に関係ない要素の変換
評価：QvtMixを用いた変換実験


19
QvtMix: QVT-OM言語用の提案手法のプロトタイプ実装
要素数を3～11Kで変化させ変換の高速化を確認
部分評価

部分評価：


静的に決定できる(入力が予想できる)計算を事前評価し，
実行コストを削減する手法．事前評価できなかった個所は
残余(residual)プログラムと呼ばれる
式による説明



20
言語で書かれた prog が in を入力として実行した場合に out を
出力することを
と表記する
部分評価器
は prog と，事前に決定可能な入力
，
を入力として与え，残余プログラム progsを出力する
つまり，事前に決定できない入力を
とすると
提案手法の概要

Binding Time Analysis(BTA)



Parserが生成したASTに対して，事前決
定できる入力と伝播ルールを使って，
FIXEDかVAR をアノテーションする
式の評価結果をキャッシュして利用
Specializer

21
ASTをトラバースしてFIXEDは評価結果
と置き換える．VARに対してもFIXEDに
関係する部分は書き換える
例題（と実験でのモデル）
22
BTAとSpecializer 実行例:

BookがFIXED


全属性がFIXED


値は変わらない
CompositionがVAR

23
新しいインスタンス
は増えない
インスタンス数が変化する
BTAとSpecializer 実行例:
24
BTAとSpecializer 実行例:
25
評価

例題と同じモデルを
Bookの数を変化させて
速度を評価

要素数100以上での
爆発的な速度増加を
大幅に改善


100まではI/O dominant
FIXEDにする割合を変化
させて効果を評価

26
およそ倍の速度で計算可能
ICSE’12 勉強会 Session N #4
Partial Models: Towards Modeling and
Reasoning with Uncertainty
M. Famelis, R. Salay, and M. Chechik
(U. of Tronto)
Proc. ICSE2012 pp.573-583
担当：東工大小林
スライド中の図は論文から引用しています．
27
概要

不確実性を取り扱うことのできるモデリング手法の提案

この論文での “不確実性(uncertainty)” = “multiple possibilities”


例：「ある属性をどのクラスに持たせるべきか，現時点では判断できない」
対象：モデル＝メタモデルが存在する型付グラフ

28
“Partial Model” = 不確実性を許容するモデル = ノードとエッジの
存在が {True, False, Maybe(実際は論理式)}で表現される．
Reasoning with Partial Models

不確実性を取り除くために候補を選択する手段として
4つの reasoning operations を定義




29
OP1: Construction

複数の候補モデルからPartial Modelを構成する方法

不一致要素をMaybeとして，その論理式を構成する
アルゴリズムで定義
OP2: Verification

Partial Model(ΦM) がプロパティ(Φp)を満たすか確認する方法

SAT問題に変換 (ΦM ∧ Φp と ΦM ∧ ￢Φp を確認)
OP3: Diagnosis

どの候補モデルがプロパティに違反しているかを見つける方法

SAT問題に変換 (OP3a~cの3種類が定義されている)
OP4: Refinement

プロパティに違反している候補モデルを除外する方法

アルゴリズムで定義
評価


RQ1: 伝統的な方法と比べて，提案手法のモデルはで
推論することはどの程度ふさわしい(feasible)か？

E1: ΦM ∧ Φp と ΦM ∧ ￢Φp を確認，時間を比較

モデルサイズ(S,M,L,XL), 不確実性(S,M,L,XL)を変化
実験結果


30
E1: 従来法と比べて
最大29倍高速
OP2, OP3の一部は
大変効果的
評価結果

RQ2: 提案手法は，不確実性の度合いに対してどの程
度の精度(sensitive) か？



E2: ΦM ∧ Φp をもつ partial model(提案手法)，全モデル(従来法)を作
成．時間を比較
モデルサイズ(S,M,L,XL), 不確実性(S,M,L,XL)を変化
実験結果


31
E2: 不確実性の度合いに相関がある
提案手法を使うと遅い．
(モデルサイズが小さいと特に)

Download Report