Session K: Concurrency

Session K: Concurrency
ICSE2014 勉強会
担当：東工大情報理工小林隆志 <[email protected]>
References
[K1] CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Yanyan Jiang et al. Proc. ICSE2014, pp.457-467
[K2] Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
Ivan Beschastnikh et al. Proc. ICSE2014, pp.468-479
[K3] Unleashing Concurrency for Irregular Data Structures
Peng Liu and Charles Zhang.
Proc. ICSE2014, pp.480-490
[K4] ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs
Yan Cai et al. Proc.ICSE2014, pp.491-502
1
ICSE2014勉強会 SessionD
2014/7/22
K1
CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Y. Jiang, T. Gu, C. Xu, X. Ma, J. Lu (Nanjing U)

分野：並列プログラム向け Record & Replay tool

種別：動的解析 (Java)，Record & Replay

論文概要：


所感：

2
並列プログラムの実行トレース取得において， read-write依存の
キャッシュを用いて，記録する実行オーバヘッドとログの量を大
幅に削減する手法CAREを提案．
香港科技大チームの既存研究LEAP[FSE2010], Stride[ICSE2012]との
性能比較により優位であることを評価
Replayの正確性を失うのではないか※と思うほどシンプルな発想．
Record & Replayができるところまでしっかり実装して実験してい
る点，改善点がクリアな点が採録のポイント
※ 著者に確認したところ特定の条件では正確ではないが，それはレアケース．
そもそもそれは既存研究でも正確に記録できない問題とのこと
ICSE2014勉強会 SessionD
2014/7/22
K1

CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Y. Jiang, T. Gu, C. Xu, X. Ma, J. Lu (Nanjing U)
並列プログラムの実行トレース取得

LEAP ではスレッド間の変数アクセスの全順序を保存
するために，計装個所でモニタを利用するため実行
オーバヘッドが大きい
Thread #1
Thread #2
x=1
read(x)
この実行順序を
保存するために
モニタを利用
read(x)
3
ICSE2014勉強会 SessionD
2014/7/22
K1

CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Y. Jiang, T. Gu, C. Xu, X. Ma, J. Lu (Nanjing U)
Key Idea: Shared Memory とのアクセスをキャッ
シュし，不要なアクセスのログを取らない
Thread #1
x=1
read(x)
4
d = read(x)
d = read(x)
if ( read(x) is NOT thread-local) {
synchronized(x) {
d=read(x)
log()
}
}
基本方針：
Thread-localのReadは
Lock/Record不要 (リプレイできる)
ICSE2014勉強会 SessionD
2014/7/22
K1

CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Y. Jiang, T. Gu, C. Xu, X. Ma, J. Lu (Nanjing U)
「read(x) is NOT thread-local」はどう判定するか？


基本的な考え方



Optimistic Thread-locality Occurrence Detector
Threadごとに
各変数の値を記録
値に変化が
あったら
NOT Thread-local
いくつか制約があるため
経験則を利用して解決して
いる(Sect 4)
Reprinted from [1] “Fig 2: Illustration of refetching”
5
ICSE2014勉強会 SessionD
2014/7/22
K1

CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Y. Jiang, T. Gu, C. Xu, X. Ma, J. Lu (Nanjing U)
「read(x) is NOT thread-local」はどう判定するか？


基本的な考え方



Optimistic Thread-locality Occurrence Detector
Threadごとに
各変数の値を記録
値に変化が
あったら
NOT Thread-local
いくつか制約があるため
経験則を利用して解決して
いる(Sect 4)
Reprinted from [K1] “Fig 2: Illustration of refetching”
6
ICSE2014勉強会 SessionD
2014/7/22
K1

CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Y. Jiang, T. Gu, C. Xu, X. Ma, J. Lu (Nanjing U)
評価
Reprinted from [K1] “Tab 1: Comparison of CARE and LEAP under benchmark programs”

対LEAPで，ログサイズ，オーバヘッドともに大幅に改善．
2.5%(Tsp) ～ 58.9% (Xalan)
 Log Size 0.3%(Tsp) ～ 65.1% (Batik)
 Overhead

7
対Stride では，XalanでMoldynでオーバーヘッドが悪化
 StrideはSynchronizedせず値を保存するため
ICSE2014勉強会 SessionD
2014/7/22
Session K: Concurrency
ICSE2014 勉強会
担当：東工大情報理工小林隆志 <[email protected]>
References
[K1] CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Yanyan Jiang et al. Proc. ICSE2014, pp.457-467
[K2] Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
Ivan Beschastnikh et al. Proc. ICSE2014, pp.468-479
[K3] Unleashing Concurrency for Irregular Data Structures
Peng Liu and Charles Zhang.
Proc. ICSE2014, pp.480-490
[K4] ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs
Yan Cai et al. Proc.ICSE2014, pp.491-502
8
ICSE2014勉強会 SessionD
2014/7/22
K2
Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
I. Beschastnikh(UBC), Y. Brun(U Mass.), M. D. Ernst, A. Krishnamurthy(U Wash.)

分野：Model inference (Specification Mining, Process discovery)

種別：動的解析，リバースエンジニアリング

論文概要：


並行プログラムのイベントトレースから並行プロセスモデル
(Comm. FSMベース)を復元する手法 CSightを提案．著者らの手法
(FSE2011)を改良．マイニングの際のInvariant情報を活用する部分
がポイント．
復元したCFSMモデルを使って，バグ発見のUser Studyをしている．


所感：

9
バグを含む２システムを，39人の学生が調査
発表が大変わかりやすかった．CFSMを正確に復元できることだ
けでなく，抽出したCFSMがデバッグに役立つという評価 (positive
feedbackだったという内容だが)をしている点が採録のポイントか
ICSE2014勉強会 SessionD
2014/7/22
K2
Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
I. Beschastnikh(UBC), Y. Brun(U Mass.), M. D. Ernst, A. Krishnamurthy(U Wash.)
イベントのtemporal invariants
Time-Space DAG
に変換
Reprinted from [K2] “Fig2. CSight process ﬂow.”
10
ICSE2014勉強会 SessionD
例： Proc1.send() is alwaysfollowed-by Proc2.receive()
① State-based DAG に変換
② Initial Global Model を作成
Invariantsを満たさないなら，
Global モデルを修正して，
Abstractをやり直し
2014/7/22
K2

Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
I. Beschastnikh(UBC), Y. Brun(U Mass.), M. D. Ernst, A. Krishnamurthy(U Wash.)
評価 (復元性能)

Voldemort DHT



11
Unit Test の実行ログを入力に利用
モデルは正しいが，一部復元できていない挙動があった
TCP opening/closing handshake

netcat/dummynet/tcpdump のログを利用

モデルの抽象度に一部問題があった
ICSE2014勉強会 SessionD
Reprinted from [K2] “Fig. 8” and “Fig.9”
2014/7/22
Session K: Concurrency
ICSE2014 勉強会
担当：東工大情報理工小林隆志 <[email protected]>
References
[K1] CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Yanyan Jiang et al. Proc. ICSE2014, pp.457-467
[K2] Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
Ivan Beschastnikh et al. Proc. ICSE2014, pp.468-479
[K3] Unleashing Concurrency for Irregular Data Structures
Peng Liu and Charles Zhang.
Proc. ICSE2014, pp.480-490
[K4] ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs
1
2
Yan Cai et al. Proc.ICSE2014, pp.491-502
ICSE2014勉強会 SessionD
2014/7/22
K3
Unleashing Concurrency for Irregular Data Structures
P. Liu (Wuhan U) and C Zang (Hong Kong Univ of Sci. Tech.)

分野：適切なLock範囲の自動決定

種別：Lockアルゴリズム，パフォーマンス

論文概要：


所感：

13
Multiple Granularity Lockingを導入して，木構造を構成するオブ
ジェクトに対するロックの効率化を行う．既存ライブラリに適用
し，7-20%のspeedup を実現. (Tomcatの例では ConcurrentHashMap
を使用する個所の改善効果により60%速度改善)
DBMS等で利用されている古典的なMultiple Granularity Lockingを
利用するもので，1) (対象の構造は限定的だが)自動的にロック
モードを選択できる点，2) 実装をして性能評価をした点，
が評価されたか？
ICSE2014勉強会 SessionD
2014/7/22
K3

Unleashing Concurrency for Irregular Data Structures
P. Liu (Wuhan U) and C Zang (Hong Kong Univ of Sci. Tech.)
参考：Multiple Granularity Locking


Giant Lock を防ぐために，同一対象に対して，
部分的にロックを取得・拡張することで排他制御を細粒度に
行うための仕組み
弱い順に以下の5つのロックモードが存在する．
 IS (Intention Shared) = 階層に S Lockをかける「意図」
 IX (Intention eXclusive) = 階層に X Lockをかける「意図」
 S (Shared) = DBMSだと Select 用
 SIX (Shared Intention eXclusive) = IXと違いIXでの上書き不可



14
⇒ 今回の手法ではなし
X (eXclusive) = DBMS だと Insert/Update/Delete
S/X Lockが欲しい場合には，上位ノードのIS/IXを
とってから取得することで排他制御．

下位(=部分)を変更しているときに上位(=全体)は変更できない

ロックモード間の上書き可能経路が決まっている (詳細は省略)
ICSE2014勉強会 SessionD
2014/7/22
K3

Unleashing Concurrency for Irregular Data Structures
P. Liu (Wuhan U) and C Zang (Hong Kong Univ of Sci. Tech.)
基本コンセプト

オブジェクトグラフに対して，MGLを適用
Reprinted from [K3] “Fig2. The update of a ﬁeld aﬀects the accesses to the descendant ﬁelds. .”

手法の流れ



Abstract Object Graph (AOG)を構成．
副作用の内容から，MGL tagを割り当て TAOGを作成
TAOGから最適なロックを生成

15
lock.IX().acquire() などをjava.util.concurrentに実装．
ICSE2014勉強会 SessionD
2014/7/22
K3

Unleashing Concurrency for Irregular Data Structures
P. Liu (Wuhan U) and C Zang (Hong Kong Univ of Sci. Tech.)
TAOGの例 ( SynchronizedCache#get() @ Cache4j )
Reprinted from [K3] “Fig7. (a) Tagged AOG produced for the method get,
the number in each node denotes the hashcode of the points-to set
represented by the node.”

16
副作用を与えるかどうかによって，X, IX, IS の
ロックモードが自動的に割り当てられる．
ICSE2014勉強会 SessionD
2014/7/22
K3

Unleashing Concurrency for Irregular Data Structures
P. Liu (Wuhan U) and C Zang (Hong Kong Univ of Sci. Tech.)
性能評価
カーブの形状に着目！
カーブの形状
本手法により並列効果が出ている
に着目！
(適用前は並列化により実行時間が増えている)
適切な並列効果
Reprinted from [K3] “Fig9 Performance comparison for (a) Jgrapht (b) STMBench7 (c) Tomcat (d) Tuplesoup..”

Giant Lockがなくなるため，Thread数(横軸)が増えると，
多くのアプリで実行時間(縦軸)の軽減率が向上
※ (b) だけ縦軸はスループット (上にある方が良い)
17
ICSE2014勉強会 SessionD
2014/7/22
Session K: Concurrency
ICSE2014 勉強会
担当：東工大情報理工小林隆志 <[email protected]>
References
[K1] CARE: Cache Guided Deterministic Replay for Concurrent Java Programs
Yanyan Jiang et al. Proc. ICSE2014, pp.457-467
[K2] Inferring Models of Concurrent Systems from Logs of Their Behavior with Csight
Ivan Beschastnikh et al. Proc. ICSE2014, pp.468-479
[K3] Unleashing Concurrency for Irregular Data Structures
Peng Liu and Charles Zhang.
Proc. ICSE2014, pp.480-490
[K4] ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs
1
8
Yan Cai et al. Proc.ICSE2014, pp.491-502
ICSE2014勉強会 SessionD
2014/7/22
K4
ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs Y. Cai, S. Wu, W.K.Chan (City U. Hong Kong)

分野：デッドロック検出

種別：動的解析

論文概要：


所感：

19
スケジューリング制約を表現するために，happen-before-relation
を拡張した，should-happen-before関係(SHBR)を定義し，デッド
ロックの検出とスケジュール違反のレポートを生成する手法
を提案
専門からちょっと遠いので，正直，新規性がよく読み取れなかっ
た論文．発表もよく分かりませんでした….
ICSE2014勉強会 SessionD
2014/7/22
K4

ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs Y. Cai, S. Wu, W.K.Chan (City U. Hong Kong)
happen-before-relation: 𝑒1 → 𝑒2




)
イベント 𝑒1 , 𝑒2 が同一スレッドで実行され
実行トレースで 𝑒1 , 𝑒2 の准で観測される．
𝑒1 がスレッド 𝑡1 でのロックmの解放で，
𝑒2 がスレッド𝑡2 でのロックmの取得であり，𝑡1 ≠ 𝑡2
Should-happen-before-relation: 𝑒 ⇒ 𝑒𝛼

(論文では
)
あるサイクル𝑐の間にスレッド𝑡1 によって起きた
イベント𝑒𝑖 を 𝜖(𝑐, 𝑡𝑖 ) と表記すると
𝑚 ∈ 𝑊𝑊𝑊𝑊𝑘𝑐 𝑎𝑎𝑎 𝑒 → 𝜖 𝑐, 𝑡 𝑎𝑎𝑎 𝑒𝛼 = 𝜖(𝑐, 𝑡𝛼 )

20
(論文では
つまり，あるロック集合Wlockに属するロックに対して，
一定時間 c で happen-before-relation があること．
ICSE2014勉強会 SessionD
2014/7/22
K4

ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs Y. Cai, S. Wu, W.K.Chan (City U. Hong Kong)
HBR と SHBRの違い
Reprinted from [K4] “Fig3．Examples of Rule1 and Rule2 on Execution2”
21
ICSE2014勉強会 SessionD
2014/7/22
K4

ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs Y. Cai, S. Wu, W.K.Chan (City U. Hong Kong)
SHBR関係の簡約
Reprinted from [K4] “Fig4. Reduction of constraints and selection of nearest scheduling
points with respect to the cycle c 0 and Execution 2 ”
22
ICSE2014勉強会 SessionD
2014/7/22
K4

ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs Y. Cai, S. Wu, W.K.Chan (City U. Hong Kong)
性能評価
Reprinted from [K4] “Tab. 2 : Experimental results comparisons among
PCT, MagicScheduler (MS), DeadlockFuzzer (DF), and ConLock (CL) ”

23
メモリ不足にもならず全ての実行が可能
ICSE2014勉強会 SessionD
2014/7/22
K4

ConLock: A Constraint-Based Approach to Dynamic Checking on Deadlocks
in Multithreaded Programs Y. Cai, S. Wu, W.K.Chan (City U. Hong Kong)
性能評価
全てのDLを検出



24
ICSE2014勉強会 SessionD
Reprinted from [K4] “Tab. 3 and Tab.4”
メモリ不足にもほぼ
ならず全実行が可能
現実的な時間で終了
2014/7/22

Download Report