Hybrid Tracking of Cross-Thread Dependences in Parallel Programs
Dynamic analysis techniques are explored in this research for error detection and performance enhancement in parallel programs. The study combines pessimistic and optimistic tracking of cross-thread dependences to address issues like data race detection and atomicity violation. The proposed hybrid tracking approach aims to improve the overall efficiency of detecting and controlling cross-thread dependences, ultimately enhancing the program's performance.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Drinking from Both Glasses: Combining Pessimistic and Optimistic Tracking of Cross- Thread Dependences MAN CAO MAN CAO MINJIA ZHANG ARITRA SENGUPTA MICHAEL D. BOND PPoPP 2016 1
Dynamic Analyses for Parallel Programs Error detection Data Race Detector Atomicity Violation Detector Programming model Transactional Memory Enforcement of Strong Memory Model Debugging Record & Replay Deterministic Execution 2
Dynamic Analyses for Parallel Programs Error detection Data Race Detector Atomicity Violation Detector Programming model Transactional Memory Enforcement of Strong Memory Model Debugging Record & Replay Deterministic Execution Bad performance! 3
Dynamic Analyses for Parallel Programs Error detection Data Race Detector Atomicity Violation Detector Programming model Transactional Memory Enforcement of Strong Memory Model Debugging Record & Replay Deterministic Execution Bad performance! Difficulties? 4
Cross-thread dependences T1 T2 o.f = = o.f 5
Cross-thread dependences T1 T2 o.f = = o.f Tracking cross-thread dependences 6
Cross-thread dependences T1 T2 o.f = = o.f Tracking cross-thread dependences Detecting Controlling 7
Outline Dynamic Analyses and Cross-thread Dependences Pessimistic Tracking Optimistic Tracking Our approach Hybrid Tracking Evaluation 8
Pessimistic Tracking Per-object metadata: o.state last writer/reader thread 9
Pessimistic Tracking Per-object metadata: o.state last writer/reader thread At each object access: rd/wr o.f 10
Pessimistic Tracking Per-object metadata: o.state last writer/reader thread At each object access: Check o.state Analysis-specific work rd/wr o.f Update o.state 11
Pessimistic Tracking Per-object metadata: o.state last writer/reader thread At each object access: Check o.state Analysis-specific work Atomic rd/wr o.f Update o.state 12
Pessimistic Tracking Per-object metadata: o.state last writer/reader thread At each object access: Lock o.state Check o.state Analysis-specific work rd/wr o.f Update o.state Unlock o.state 13
Pessimistic Tracking Per-object metadata: o.state last writer/reader thread At each object access: Lock o.state Check o.state Analysis-specific work NOT program locks rd/wr o.f Update o.state Unlock o.state 14
Pessimistic Tracking Lock o.state wr o.f Unlock o.state Lock o.state rd o.f Unlock o.state 15
Pessimistic Tracking Lock o.state Synchronization and write metadata wr o.f Unlock o.state Lock o.state rd o.f Unlock o.state 16
Performance of Pessimistic Tracking Alone 29,000 1,300 500 450 400 340% 350 Overhead (%) 300 250 200 150 100 50 0 17
Outline Dynamic Analyses and Cross-thread Dependences Pessimistic Tracking Optimistic Tracking Our approach Hybrid Tracking Evaluation 18
Optimistic Tracking Biased reader-writer lock for o.state 19
Optimistic Tracking Biased reader-writer lock for o.state Avoid synchronization for non-conflicting accesses 20
Optimistic Tracking Biased reader-writer lock for o.state Avoid synchronization for non-conflicting accesses Heavyweight coordination for conflicting accesses 21
Optimistic Tracking T1 T2 o.state: WrExT1 write check wr o.f 22
Optimistic Tracking T1 T2 o.state: WrExT1 write check wr o.f o.state: WrExT1 read check 23
Optimistic Tracking T1 T2 o.state: WrExT1 write check wr o.f o.state: WrExT1 read check Analysis-specific work 24
Optimistic Tracking T1 T2 o.state: WrExT1 write check wr o.f o.state: WrExT1 read check Analysis-specific work safe point change state o.state RdExT2 rd o.f 25
Performance of Optimistic Tracking Alone 410 140 290 500 130 290 240 29,000 1,300 120 340 120 100 80 Overhead (%) Pessimistic Tracking 60 40 Optimistic Tracking 28% 20 0 26
Performance of Optimistic Tracking Alone 410 140 290 500 130 290 240 29,000 1,300 120 340 120 100 80 Overhead (%) Pessimistic Tracking 60 40 Optimistic Tracking 28% 20 0 27
Cost of Different Tracking Pessimistic Optimistic Same state 47 Coordination 9200 150 In CPU cycles Averaged across all programs 28
Optimistic tracking performs best if there are few conflicting accesses. 29
Pessimistic tracking is cheaper for conflicting accesses. 30
Drink from both glasses? Goal Optimistic tracking for most non-conflicting accesses Pessimistic tracking for most conflicting accesses 31
Outline Dynamic Analyses and Cross-thread Dependences Pessimistic Tracking Optimistic Tracking Our approach Hybrid Tracking Evaluation 32
Outline Dynamic Analyses and Cross-thread Dependences Pessimistic Tracking Optimistic Tracking Our approach Hybrid Tracking Hybrid State Model Adaptive Policy Evaluation 33
Outline Dynamic Analyses and Cross-thread Dependences Pessimistic Tracking Challenging! Optimistic Tracking Our approach Hybrid Tracking Hybrid State Model Adaptive Policy Evaluation 34
Outline Dynamic Analyses and Cross-thread Dependences Pessimistic Tracking Optimistic Tracking Our approach Hybrid Tracking Hybrid State Model Deferred Unlocking Adaptive Policy Evaluation 35
Pessimistic-Optimistic Mismatch Optimistic Tracking Pessimistic Tracking write check Lock o.state wr o.f read check rd/wr o.f safe point change state Unlock o.state rd o.f 36
Pessimistic-Optimistic Mismatch (#1) Optimistic Tracking Pessimistic Tracking write check Lock o.state wr o.f read check rd/wr o.f safe point change state Unlock o.state rd o.f No unlock! 37
Pessimistic-Optimistic Mismatch (#1) Optimistic Tracking Pessimistic Tracking write check Lock o.state wr o.f read check rd/wr o.f safe point change state Unlock o.state Conditional unlock? rd o.f No unlock! 38
Pessimistic-Optimistic Mismatch (#2) Optimistic Tracking Pessimistic Tracking write check Lock o.state wr o.f read check Atomic Atomic rd/wr o.f safe point change state Unlock o.state rd o.f 39
Pessimistic-Optimistic Mismatch (#2) Optimistic Tracking Pessimistic Tracking write check Lock o.state wr o.f read check Atomic Atomic rd/wr o.f safe point change state Unlock o.state Atomicity granularity may affect specific analysis rd o.f 40
Pessimistic-Optimistic Mismatch (#2) Optimistic Tracking Pessimistic Tracking write check Lock o.state wr o.f read check Atomic Atomic rd/wr o.f safe point change state Unlock o.state Atomicity granularity may affect specific analysis rd o.f Conditional unlock 41
Key Insights Coarsening atomicity granularity for pessimistic tracking 42
Key Insights Coarsening atomicity granularity for pessimistic tracking Program synchronization may hint at cross-thread dependences 43
Addressing Pessimistic- Optimistic Mismatch Defer unlocking of pessimistic state Till program synchronization release operation (PSRO) 44
Addressing Pessimistic- Optimistic Mismatch Defer unlocking of pessimistic state Till program synchronization release operation (PSRO) Reader-writer locking 45
Addressing Pessimistic- Optimistic Mismatch Defer unlocking of pessimistic state Till program synchronization release operation (PSRO) Reader-writer locking Fall back to coordination on contention when locking a state 46
Deferred Unlocking Example 1 synchronized (m) { Lock o.state wr o.f Unlock all states } synchronized (m) { Lock o.state rd o.f 47
Deferred Unlocking Example 2 synchronized (m) { Lock o.state wr o.f Lock o.state safe point Unlock all states } rd o.f 48
