スライドサンプル

LIME: A Framework for Debugging
Load Imbalance in Multi-threaded
Execution
Jungju Oh, Christopher J. Hughes, Guru Venkataramani
Riding the Design Wave I セッション
担当：肥後芳樹（大阪大学）
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
1
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
研究の背景
• マルチコアのCPUが増えている
– クロック数の向上スピードは遅い
– 1CPUあたりのコア数はどんどん増えている
• スケーラビリティの高いシステムを構築するために
は，マルチコアCPUの資源をうまく使う必要がある
– Dynamic Task Schedulingを使う手もあるけど，それ自体
のオーバーヘッドがかなり高い
紹介論文の図2（負荷不均衡の例）
• スレッド間の負荷不均衡をプロ
グラマに提示する手法が必要！
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
2
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
貢献
• ソースコードのどの部分が負荷不均衡の原
因になっているのかを提示するシステム
（LIME）の開発
– 各スレッドでループの回数が違う
– ハードウェアとの関連（キャッシュの有無等）
• SPLASH-2とPARSECのベンチマークプログ
ラム（有名？）から負荷不均衡の検出
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
3
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
LIMEの概要
• 2種類のプロファイラを用いる
– SESC：ハードウェアとの間のいろんな情報を収集可能，し
かし，速度遅い
– Pin：制御フローの情報のみ収集，速度速い
• 大まかな処理の手順
– STEP１：関連のありそうなイベントをまとめる
– STEP2：各グループ内でリーダーを特定する．リーダーと
はこのグループによる負荷不均衡の中心的な役割をして
いるイベント
– STEP3：重回帰分析を行うことにより，どのリーダーがプロ
グラムの負荷不均衡に支配的であるかを特定
– STEP4：STEP3の結果をランク付けして表示
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
4
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
評価
• 15個のベンチマーク，スレッドの数を8,16,32,64個で実行し，
LIMEで監視
• SESCを使った場合の評価では，平均で，制御フローにより
1.3個，キャッシュミスにより，2.1個の不可不均衡が発生して
いた
• Pinを使った場合の評価では，制御フローにより負荷不均衡
を高速に見つけれた
• キャッシュミスの指摘の正しさは，「キャッシュミスが起こらな
かったこと」にして，負荷不均衡が軽減されていることを確認
• 制御フローの指摘の正しさは，1つ１つ手作業により精査した．
論文中では，3つの事例を紹介
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
5
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
Synthesis of Live Behaviour
Models for Fallible Domains
Nicolas D’lpplito, Victor Braberman, Nir Piterman,
Sebastian Uchitel
Riding the Design Wave I セッション
担当：肥後芳樹（大阪大学）
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
6
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
制御設計（Controller synthesis）の例
• 旅行代理店は，以下の既存システムを組み合わせ
ることにより，パック旅行を販売したい
– 飛行機チケット販売システム
– レンタカー予約システム
– ホテル予約システム
紹介論文の図1（レンタカー予約システム）
• 統合したシステムはさまざまな問題に対応しないと
いけない
– 飛行機が予約できなかった場合には，レンタカーとホテル
の予約はしない等
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
7
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
研究の背景
• 既存のコンポーネントを自動的に，安全に組
み合わせたい
– 特に，service-oriented なアーキテクチャでは
• 最近注目を集めている自己適応型（selfadaptive）システムでは，制御設計はとても大
事な技術
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
8
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
手法の特徴
• 基礎的な要求工学のベストプラクティスに従う
– システムが動作する環境に明確な仮定を置く
– Controlledとmonitorアクションの分離
• 2ページ前の図の実線と破線
• 計算複雑度は多項式時間
– 既存手法は指数時間
• ユーザは，GR(1)やSGR(1)を用いて仕様を書く
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
9
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
評価
• 既存手法の評価で使われた課題を，既存手
法よりも正しくモデル化できるかを評価
• 4つの課題について，定性的な評価，時間に
ついては評価なし
– 4つの課題に対して，「このように扱うと提案手法
でうまくできるよ」と書いている，と思う．．．
• 感想：論文としての完成度はいまいち
– 高い知識を要求，表記ミス，変な文章
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
10
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
Coverage Guided Systematic
Concurrency Testing
Chao Wang, Mahmoud Said, Aarti Gupta
Riding the Design Wave I セッション
担当：肥後芳樹（大阪大学）
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
11
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
背景
• メモリ共有型マルチスレッドプログラムのデ
バッグは困難を極める
• 全てのインターリーブ（スレッド間のやり取り）
の組み合わせを網羅的にテストするのは無
理
• 既存手法もスケーラビリティが高くない
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
12
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
貢献
• （既存手法に比べて）スケーラビリティの高い
手法を提案
• ちゃんとしたツールを作っている（ような印象）
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
13
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
手法概要
• STEP1：正しい結果を得ることが分かっている
テストケースを実行し，その動的な情報（共有
メモリにアクセスする命令の順番等）を収集
• STEP2：命令の順番に当てはまらないテスト
ケースを生成
– 正しい結果を得ることが出来れば，生成したテス
トケース中の命令の順番も，次回以降のテスト
ケース生成に用いる
– 抽象化を行いスレッド数が多くても実行時間が極
端に増えないようにしている
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
14
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/
評価
• 既存手法DPOR，PCBとの比較
– 実行時間
– 見つけるべきバグを見つけれるか
• 結果
– 提案手法は最も高速
• 既存手法はスレッド数が多くなると指数的に時間がか
かるが，提案手法の時間増加は穏やか
– 既存手法は見つけたが提案手法が見つけれな
かったバグはない
2015/10/1
ICSE'11勉強会 Riding the Design Wave I セッション
15
KUSUMOTO LABORATORY - Software Design Laboratory
Department of Computer Science, Graduate School of Information Science and Technology, Osaka University. http://sdl.ist.osaka-u.ac.jp/

Download Report