ICSE'11勉強会 Riding the Design Wave I セッション

Presentation on theme: "ICSE'11勉強会 Riding the Design Wave I セッション"— Presentation transcript:

1 ICSE'11勉強会 Riding the Design Wave I セッション
LIME: A Framework for Debugging Load Imbalance in Multi-threaded Execution Jungju Oh, Christopher J. Hughes, Guru Venkataramani Riding the Design Wave I セッション 担当：肥後芳樹（大阪大学） ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

2 ICSE'11勉強会 Riding the Design Wave I セッション
研究の背景 マルチコアのCPUが増えている クロック数の向上スピードは遅い 1CPUあたりのコア数はどんどん増えている スケーラビリティの高いシステムを構築するためには，マルチコアCPUの資源をうまく使う必要がある Dynamic Task Schedulingを使う手もあるけど，それ自体のオーバーヘッドがかなり高い スレッド間の負荷不均衡をプロ グラマに提示する手法が必要！ 紹介論文の図2（負荷不均衡の例） ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

3 ICSE'11勉強会 Riding the Design Wave I セッション
貢献 ソースコードのどの部分が負荷不均衡の原因になっているのかを提示するシステム（LIME）の開発 各スレッドでループの回数が違う ハードウェアとの関連（キャッシュの有無等） SPLASH-2とPARSECのベンチマークプログラム（有名？）から負荷不均衡の検出 ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

4 ICSE'11勉強会 Riding the Design Wave I セッション
LIMEの概要 2種類のプロファイラを用いる SESC：ハードウェアとの間のいろんな情報を収集可能，しかし，速度遅い Pin：制御フローの情報のみ収集，速度速い 大まかな処理の手順 STEP１：関連のありそうなイベントをまとめる STEP2：各グループ内でリーダーを特定する．リーダーとはこのグループによる負荷不均衡の中心的な役割をしているイベント STEP3：重回帰分析を行うことにより，どのリーダーがプログラムの負荷不均衡に支配的であるかを特定 STEP4：STEP3の結果をランク付けして表示 ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

5 ICSE'11勉強会 Riding the Design Wave I セッション
評価 15個のベンチマーク，スレッドの数を8,16,32,64個で実行し，LIMEで監視 SESCを使った場合の評価では，平均で，制御フローにより1.3個，キャッシュミスにより，2.1個の不可不均衡が発生していた Pinを使った場合の評価では，制御フローにより負荷不均衡を高速に見つけれた キャッシュミスの指摘の正しさは，「キャッシュミスが起こらなかったこと」にして，負荷不均衡が軽減されていることを確認 制御フローの指摘の正しさは，1つ１つ手作業により精査した．論文中では，3つの事例を紹介 ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

6 Synthesis of Live Behaviour Models for Fallible Domains
Nicolas D’lpplito, Victor Braberman, Nir Piterman, Sebastian Uchitel Riding the Design Wave I セッション 担当：肥後芳樹（大阪大学） ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

7 制御設計（Controller synthesis）の例
旅行代理店は，以下の既存システムを組み合わせることにより，パック旅行を販売したい 飛行機チケット販売システム レンタカー予約システム ホテル予約システム 統合したシステムはさまざまな問題に対応しないといけない 飛行機が予約できなかった場合には，レンタカーとホテルの予約はしない等 紹介論文の図1（レンタカー予約システム） ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

8 ICSE'11勉強会 Riding the Design Wave I セッション
研究の背景 既存のコンポーネントを自動的に，安全に組み合わせたい 特に，service-oriented なアーキテクチャでは 最近注目を集めている自己適応型（self-adaptive）システムでは，制御設計はとても大事な技術 ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

9 ICSE'11勉強会 Riding the Design Wave I セッション
手法の特徴 基礎的な要求工学のベストプラクティスに従う システムが動作する環境に明確な仮定を置く Controlledとmonitorアクションの分離 2ページ前の図の実線と破線 計算複雑度は多項式時間 既存手法は指数時間 ユーザは，GR(1)やSGR(1)を用いて仕様を書く ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

10 ICSE'11勉強会 Riding the Design Wave I セッション
評価 既存手法の評価で使われた課題を，既存手法よりも正しくモデル化できるかを評価 4つの課題について，定性的な評価，時間については評価なし 4つの課題に対して，「このように扱うと提案手法でうまくできるよ」と書いている，と思う．．． 感想：論文としての完成度はいまいち 高い知識を要求，表記ミス，変な文章 ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

11 Coverage Guided Systematic Concurrency Testing
Chao Wang, Mahmoud Said, Aarti Gupta Riding the Design Wave I セッション 担当：肥後芳樹（大阪大学） ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

12 ICSE'11勉強会 Riding the Design Wave I セッション
背景 メモリ共有型マルチスレッドプログラムのデバッグは困難を極める 全てのインターリーブ（スレッド間のやり取り）の組み合わせを網羅的にテストするのは無理 既存手法もスケーラビリティが高くない ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

13 ICSE'11勉強会 Riding the Design Wave I セッション
貢献 （既存手法に比べて）スケーラビリティの高い手法を提案 ちゃんとしたツールを作っている（ような印象） ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

14 ICSE'11勉強会 Riding the Design Wave I セッション
手法概要 STEP1：正しい結果を得ることが分かっているテストケースを実行し，その動的な情報（共有メモリにアクセスする命令の順番等）を収集 STEP2：命令の順番に当てはまらないテストケースを生成 正しい結果を得ることが出来れば，生成したテストケース中の命令の順番も，次回以降のテストケース生成に用いる 抽象化を行いスレッド数が多くても実行時間が極端に増えないようにしている ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2

15 ICSE'11勉強会 Riding the Design Wave I セッション
評価 既存手法DPOR，PCBとの比較 実行時間 見つけるべきバグを見つけれるか 結果 提案手法は最も高速 既存手法はスレッド数が多くなると指数的に時間がかかるが，提案手法の時間増加は穏やか 既存手法は見つけたが提案手法が見つけれなかったバグはない ICSE'11勉強会 Riding the Design Wave I セッション 2019/12/2